diff options
Diffstat (limited to 'vendor/chalk-ir-0.80.0/src/zip.rs')
-rw-r--r-- | vendor/chalk-ir-0.80.0/src/zip.rs | 543 |
1 files changed, 543 insertions, 0 deletions
diff --git a/vendor/chalk-ir-0.80.0/src/zip.rs b/vendor/chalk-ir-0.80.0/src/zip.rs new file mode 100644 index 000000000..94cc18828 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/zip.rs @@ -0,0 +1,543 @@ +//! Traits for "zipping" types, walking through two structures and checking that they match. + +use crate::fold::Fold; +use crate::*; +use std::fmt::Debug; +use std::sync::Arc; + +/// When we zip types, we basically traverse the structure, ensuring +/// that it matches. When we come to types/lifetimes, we invoke the +/// callback methods in the zipper to match them up. Primarily used +/// during unification or similar operations. +/// +/// So e.g. if you had `A: Eq<B>` zipped with `X: Eq<Y>`, then the zipper +/// would get two callbacks, one pairing `A` and `X`, and the other pairing +/// `B` and `Y`. +/// +/// For things other than types/lifetimes, the zip impls will +/// guarantee equality. So e.g. if you have `A: Eq<B>` zipped with `X: +/// Ord<Y>`, you would wind up with an error, no matter what zipper +/// you are using. This is because the traits `Eq` and `Ord` are +/// represented by two distinct `ItemId` values, and the impl for +/// `ItemId` requires that all `ItemId` in the two zipped values match +/// up. +pub trait Zipper<I: Interner> { + /// Indicates that the two types `a` and `b` were found in matching spots. + fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()>; + + /// Indicates that the two lifetimes `a` and `b` were found in matching spots. + fn zip_lifetimes( + &mut self, + variance: Variance, + a: &Lifetime<I>, + b: &Lifetime<I>, + ) -> Fallible<()>; + + /// Indicates that the two consts `a` and `b` were found in matching spots. + fn zip_consts(&mut self, variance: Variance, a: &Const<I>, b: &Const<I>) -> Fallible<()>; + + /// Zips two values appearing beneath binders. + fn zip_binders<T>( + &mut self, + variance: Variance, + a: &Binders<T>, + b: &Binders<T>, + ) -> Fallible<()> + where + T: Clone + HasInterner<Interner = I> + Zip<I> + Fold<I, Result = T>; + + /// Zips two substs + fn zip_substs( + &mut self, + ambient: Variance, + variances: Option<Variances<I>>, + a: &[GenericArg<I>], + b: &[GenericArg<I>], + ) -> Fallible<()> + where + Self: Sized, + { + for (i, (a, b)) in a.iter().zip(b.iter()).enumerate() { + let variance = variances + .as_ref() + .map(|v| v.as_slice(self.interner())[i]) + .unwrap_or(Variance::Invariant); + Zip::zip_with(self, ambient.xform(variance), a, b)?; + } + Ok(()) + } + + /// Retrieves the interner from the underlying zipper object + fn interner(&self) -> I; + + /// Retrieves the `UnificationDatabase` from the underlying zipper object + fn unification_database(&self) -> &dyn UnificationDatabase<I>; +} + +impl<'f, Z, I> Zipper<I> for &'f mut Z +where + I: Interner, + Z: Zipper<I>, +{ + fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> { + (**self).zip_tys(variance, a, b) + } + + fn zip_lifetimes( + &mut self, + variance: Variance, + a: &Lifetime<I>, + b: &Lifetime<I>, + ) -> Fallible<()> { + (**self).zip_lifetimes(variance, a, b) + } + + fn zip_consts(&mut self, variance: Variance, a: &Const<I>, b: &Const<I>) -> Fallible<()> { + (**self).zip_consts(variance, a, b) + } + + fn zip_binders<T>(&mut self, variance: Variance, a: &Binders<T>, b: &Binders<T>) -> Fallible<()> + where + T: Clone + HasInterner<Interner = I> + Zip<I> + Fold<I, Result = T>, + { + (**self).zip_binders(variance, a, b) + } + + fn interner(&self) -> I { + Z::interner(*self) + } + + fn unification_database(&self) -> &dyn UnificationDatabase<I> { + (**self).unification_database() + } +} + +/// The `Zip` trait walks two values, invoking the `Zipper` methods where +/// appropriate, but otherwise requiring strict equality. +/// +/// See `Zipper` trait for more details. +/// +/// To implement the trait, typically you would use one of the macros +/// like `eq_zip!`, `struct_zip!`, or `enum_zip!`. +pub trait Zip<I>: Debug +where + I: Interner, +{ + /// Uses the zipper to walk through two values, ensuring that they match. + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()>; +} + +impl<'a, T: ?Sized + Zip<I>, I: Interner> Zip<I> for &'a T { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + <T as Zip<I>>::zip_with(zipper, variance, a, b) + } +} + +impl<I: Interner> Zip<I> for () { + fn zip_with<Z: Zipper<I>>(_: &mut Z, _: Variance, _: &Self, _: &Self) -> Fallible<()> { + Ok(()) + } +} + +impl<T: Zip<I>, I: Interner> Zip<I> for Vec<T> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + <[T] as Zip<I>>::zip_with(zipper, variance, a, b) + } +} + +impl<T: Zip<I>, I: Interner> Zip<I> for [T] { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + if a.len() != b.len() { + return Err(NoSolution); + } + + for (a_elem, b_elem) in a.iter().zip(b) { + Zip::zip_with(zipper, variance, a_elem, b_elem)?; + } + + Ok(()) + } +} + +impl<T: Zip<I>, I: Interner> Zip<I> for Arc<T> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + <T as Zip<I>>::zip_with(zipper, variance, a, b) + } +} + +impl<T: Zip<I>, I: Interner> Zip<I> for Box<T> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + <T as Zip<I>>::zip_with(zipper, variance, a, b) + } +} + +impl<T: Zip<I>, U: Zip<I>, I: Interner> Zip<I> for (T, U) { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + Zip::zip_with(zipper, variance, &a.0, &b.0)?; + Zip::zip_with(zipper, variance, &a.1, &b.1)?; + Ok(()) + } +} + +impl<I: Interner> Zip<I> for Ty<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + zipper.zip_tys(variance, a, b) + } +} + +impl<I: Interner> Zip<I> for Lifetime<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + zipper.zip_lifetimes(variance, a, b) + } +} + +impl<I: Interner> Zip<I> for Const<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + zipper.zip_consts(variance, a, b) + } +} +impl<I: Interner, T> Zip<I> for Binders<T> +where + T: Clone + HasInterner<Interner = I> + Zip<I> + Fold<I, Result = T>, +{ + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + zipper.zip_binders(variance, a, b) + } +} + +/// Generates a Zip impl that requires the two values be +/// equal. Suitable for atomic, scalar values. +macro_rules! eq_zip { + ($I:ident => $t:ty) => { + impl<$I: Interner> Zip<$I> for $t { + fn zip_with<Z: Zipper<$I>>( + _zipper: &mut Z, + _variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + if a != b { + return Err(NoSolution); + } + Ok(()) + } + } + }; +} + +eq_zip!(I => AdtId<I>); +eq_zip!(I => TraitId<I>); +eq_zip!(I => AssocTypeId<I>); +eq_zip!(I => OpaqueTyId<I>); +eq_zip!(I => GeneratorId<I>); +eq_zip!(I => ForeignDefId<I>); +eq_zip!(I => FnDefId<I>); +eq_zip!(I => ClosureId<I>); +eq_zip!(I => QuantifierKind); +eq_zip!(I => PhantomData<I>); +eq_zip!(I => PlaceholderIndex); +eq_zip!(I => ClausePriority); +eq_zip!(I => Mutability); +eq_zip!(I => Scalar); + +impl<T: HasInterner<Interner = I> + Zip<I>, I: Interner> Zip<I> for InEnvironment<T> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + Zip::zip_with(zipper, variance, &a.environment, &b.environment)?; + Zip::zip_with(zipper, variance, &a.goal, &b.goal)?; + Ok(()) + } +} + +impl<I: Interner> Zip<I> for Environment<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + assert_eq!(a.clauses.len(interner), b.clauses.len(interner)); // or different numbers of clauses + Zip::zip_with( + zipper, + variance, + a.clauses.as_slice(interner), + b.clauses.as_slice(interner), + )?; + Ok(()) + } +} + +impl<I: Interner> Zip<I> for Goals<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?; + Ok(()) + } +} + +impl<I: Interner> Zip<I> for ProgramClauses<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?; + Ok(()) + } +} + +impl<I: Interner> Zip<I> for Constraints<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?; + Ok(()) + } +} + +impl<I: Interner> Zip<I> for QuantifiedWhereClauses<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?; + Ok(()) + } +} + +// Annoyingly, Goal cannot use `enum_zip` because some variants have +// two parameters, and I'm too lazy to make the macro account for the +// relevant name mangling. +impl<I: Interner> Zip<I> for Goal<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, a.data(interner), b.data(interner)) + } +} + +// I'm too lazy to make `enum_zip` support type parameters. +impl<I: Interner> Zip<I> for VariableKind<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + match (a, b) { + (VariableKind::Ty(a), VariableKind::Ty(b)) if a == b => Ok(()), + (VariableKind::Lifetime, VariableKind::Lifetime) => Ok(()), + (VariableKind::Const(ty_a), VariableKind::Const(ty_b)) => { + Zip::zip_with(zipper, variance, ty_a, ty_b) + } + (VariableKind::Ty(_), _) + | (VariableKind::Lifetime, _) + | (VariableKind::Const(_), _) => panic!("zipping things of mixed kind"), + } + } +} + +impl<I: Interner> Zip<I> for GenericArg<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, a.data(interner), b.data(interner)) + } +} + +impl<I: Interner> Zip<I> for ProgramClause<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, a.data(interner), b.data(interner)) + } +} + +impl<I: Interner> Zip<I> for TraitRef<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, &a.trait_id, &b.trait_id)?; + zipper.zip_substs( + variance, + None, + a.substitution.as_slice(interner), + b.substitution.as_slice(interner), + ) + } +} + +impl<I: Interner> Zip<I> for ProjectionTy<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, &a.associated_ty_id, &b.associated_ty_id)?; + zipper.zip_substs( + variance, + None, + a.substitution.as_slice(interner), + b.substitution.as_slice(interner), + ) + } +} + +impl<I: Interner> Zip<I> for OpaqueTy<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + Zip::zip_with(zipper, variance, &a.opaque_ty_id, &b.opaque_ty_id)?; + zipper.zip_substs( + variance, + None, + a.substitution.as_slice(interner), + b.substitution.as_slice(interner), + ) + } +} + +impl<I: Interner> Zip<I> for DynTy<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + Zip::zip_with( + zipper, + variance.xform(Variance::Invariant), + &a.bounds, + &b.bounds, + )?; + Zip::zip_with( + zipper, + variance.xform(Variance::Contravariant), + &a.lifetime, + &b.lifetime, + )?; + Ok(()) + } +} + +impl<I: Interner> Zip<I> for FnSubst<I> { + fn zip_with<Z: Zipper<I>>( + zipper: &mut Z, + variance: Variance, + a: &Self, + b: &Self, + ) -> Fallible<()> { + let interner = zipper.interner(); + // Parameters + for (a, b) in a.0.as_slice(interner)[..a.0.len(interner) - 1] + .iter() + .zip(b.0.as_slice(interner)[..b.0.len(interner) - 1].iter()) + { + Zip::zip_with(zipper, variance.xform(Variance::Contravariant), a, b)?; + } + // Return type + Zip::zip_with( + zipper, + variance, + a.0.iter(interner).last().unwrap(), + b.0.iter(interner).last().unwrap(), + )?; + Ok(()) + } +} |