blob: 585ff661d1732858f1eeaa84b5b139dc05edfc79 [file] [log] [blame]
//! Traits for "zipping" types, walking through two structures and checking that they match.
use crate::fold::TypeFoldable;
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> + TypeFoldable<I>;
/// 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> + TypeFoldable<I>,
{
(**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> + TypeFoldable<I>,
{
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 => CoroutineId<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
Zip::zip_with(
zipper,
variance.xform(Variance::Contravariant),
&a.0.as_slice(interner)[..a.0.len(interner) - 1],
&b.0.as_slice(interner)[..b.0.len(interner) - 1],
)?;
// Return type
Zip::zip_with(
zipper,
variance,
a.0.iter(interner).last().unwrap(),
b.0.iter(interner).last().unwrap(),
)?;
Ok(())
}
}