chalk_solve/infer/

unify.rs

use super::var::*;
use super::*;
use crate::debug_span;
use chalk_ir::cast::Cast;
use chalk_ir::fold::{FallibleTypeFolder, TypeFoldable};
use chalk_ir::interner::{HasInterner, Interner};
use chalk_ir::zip::{Zip, Zipper};
use chalk_ir::UnificationDatabase;
use std::fmt::Debug;
use tracing::{debug, instrument};

impl<I: Interner> InferenceTable<I> {
    pub fn relate<T>(
        &mut self,
        interner: I,
        db: &dyn UnificationDatabase<I>,
        environment: &Environment<I>,
        variance: Variance,
        a: &T,
        b: &T,
    ) -> Fallible<RelationResult<I>>
    where
        T: ?Sized + Zip<I>,
    {
        let snapshot = self.snapshot();
        match Unifier::new(interner, db, self, environment).relate(variance, a, b) {
            Ok(r) => {
                self.commit(snapshot);
                Ok(r)
            }
            Err(e) => {
                self.rollback_to(snapshot);
                Err(e)
            }
        }
    }
}

struct Unifier<'t, I: Interner> {
    table: &'t mut InferenceTable<I>,
    environment: &'t Environment<I>,
    goals: Vec<InEnvironment<Goal<I>>>,
    interner: I,
    db: &'t dyn UnificationDatabase<I>,
}

#[derive(Debug)]
pub struct RelationResult<I: Interner> {
    pub goals: Vec<InEnvironment<Goal<I>>>,
}

impl<'t, I: Interner> Unifier<'t, I> {
    fn new(
        interner: I,
        db: &'t dyn UnificationDatabase<I>,
        table: &'t mut InferenceTable<I>,
        environment: &'t Environment<I>,
    ) -> Self {
        Unifier {
            environment,
            table,
            goals: vec![],
            interner,
            db,
        }
    }

    /// The main entry point for the `Unifier` type and really the
    /// only type meant to be called externally. Performs a
    /// relation of `a` and `b` and returns the Unification Result.
    #[instrument(level = "debug", skip(self))]
    fn relate<T>(mut self, variance: Variance, a: &T, b: &T) -> Fallible<RelationResult<I>>
    where
        T: ?Sized + Zip<I>,
    {
        Zip::zip_with(&mut self, variance, a, b)?;
        let interner = self.interner();
        let mut goals = self.goals;
        let table = self.table;
        // Sometimes we'll produce a lifetime outlives goal which we later solve by unification
        // Technically, these *will* get canonicalized to the same bound var and so that will end up
        // as a goal like `^0.0 <: ^0.0`, which is trivially true. But, we remove those *here*, which
        // might help caching.
        goals.retain(|g| match g.goal.data(interner) {
            GoalData::SubtypeGoal(SubtypeGoal { a, b }) => {
                let n_a = table.ty_root(interner, a);
                let n_b = table.ty_root(interner, b);
                let a = n_a.as_ref().unwrap_or(a);
                let b = n_b.as_ref().unwrap_or(b);
                a != b
            }
            _ => true,
        });
        Ok(RelationResult { goals })
    }

    /// Relate `a`, `b` with the variance such that if `variance = Covariant`, `a` is
    /// a subtype of `b`.
    fn relate_ty_ty(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> {
        let interner = self.interner;

        let n_a = self.table.normalize_ty_shallow(interner, a);
        let n_b = self.table.normalize_ty_shallow(interner, b);
        let a = n_a.as_ref().unwrap_or(a);
        let b = n_b.as_ref().unwrap_or(b);

        debug_span!("relate_ty_ty", ?variance, ?a, ?b);

        if a.kind(interner) == b.kind(interner) {
            return Ok(());
        }

        match (a.kind(interner), b.kind(interner)) {
            // Relating two inference variables:
            // First, if either variable is a float or int kind, then we always
            // unify if they match. This is because float and ints don't have
            // subtype relationships.
            // If both kinds are general then:
            // If `Invariant`, unify them in the underlying ena table.
            // If `Covariant` or `Contravariant`, push `SubtypeGoal`
            (&TyKind::InferenceVar(var1, kind1), &TyKind::InferenceVar(var2, kind2)) => {
                if matches!(kind1, TyVariableKind::General)
                    && matches!(kind2, TyVariableKind::General)
                {
                    // Both variable kinds are general; so unify if invariant, otherwise push subtype goal
                    match variance {
                        Variance::Invariant => self.unify_var_var(var1, var2),
                        Variance::Covariant => {
                            self.push_subtype_goal(a.clone(), b.clone());
                            Ok(())
                        }
                        Variance::Contravariant => {
                            self.push_subtype_goal(b.clone(), a.clone());
                            Ok(())
                        }
                    }
                } else if kind1 == kind2 {
                    // At least one kind is not general, but they match, so unify
                    self.unify_var_var(var1, var2)
                } else if kind1 == TyVariableKind::General {
                    // First kind is general, second isn't, unify
                    self.unify_general_var_specific_ty(var1, b.clone())
                } else if kind2 == TyVariableKind::General {
                    // Second kind is general, first isn't, unify
                    self.unify_general_var_specific_ty(var2, a.clone())
                } else {
                    debug!(
                        "Tried to unify mis-matching inference variables: {:?} and {:?}",
                        kind1, kind2
                    );
                    Err(NoSolution)
                }
            }

            // Unifying `forall<X> { T }` with some other forall type `forall<X> { U }`
            (&TyKind::Function(ref fn1), &TyKind::Function(ref fn2)) => {
                if fn1.sig == fn2.sig {
                    Zip::zip_with(
                        self,
                        variance,
                        &fn1.clone().into_binders(interner),
                        &fn2.clone().into_binders(interner),
                    )
                } else {
                    Err(NoSolution)
                }
            }

            (&TyKind::Placeholder(ref p1), &TyKind::Placeholder(ref p2)) => {
                Zip::zip_with(self, variance, p1, p2)
            }

            // Unifying two dyn is possible if they have the same bounds.
            (&TyKind::Dyn(ref qwc1), &TyKind::Dyn(ref qwc2)) => {
                Zip::zip_with(self, variance, qwc1, qwc2)
            }

            (TyKind::BoundVar(_), _) | (_, TyKind::BoundVar(_)) => panic!(
                "unification encountered bound variable: a={:?} b={:?}",
                a, b
            ),

            // Unifying an alias type with some other type `U`.
            (_, &TyKind::Alias(ref alias)) => self.relate_alias_ty(variance.invert(), alias, a),
            (&TyKind::Alias(ref alias), _) => self.relate_alias_ty(variance, alias, b),

            (&TyKind::InferenceVar(var, kind), ty_data) => {
                let ty = ty_data.clone().intern(interner);
                self.relate_var_ty(variance, var, kind, &ty)
            }
            (ty_data, &TyKind::InferenceVar(var, kind)) => {
                // We need to invert the variance if inference var is `b` because we pass it in
                // as `a` to relate_var_ty
                let ty = ty_data.clone().intern(interner);
                self.relate_var_ty(variance.invert(), var, kind, &ty)
            }

            (TyKind::Error, _) | (_, TyKind::Error) => Ok(()),

            // This would correspond to unifying a `fn` type with a non-fn
            // type in Rust; error.
            (&TyKind::Function(_), _) | (_, &TyKind::Function(_)) => Err(NoSolution),

            // Cannot unify (e.g.) some struct type `Foo` and a placeholder like `T`
            (_, &TyKind::Placeholder(_)) | (&TyKind::Placeholder(_), _) => Err(NoSolution),

            // Cannot unify `dyn Trait` with things like structs or placeholders
            (_, &TyKind::Dyn(_)) | (&TyKind::Dyn(_), _) => Err(NoSolution),

            (TyKind::Adt(id_a, substitution_a), TyKind::Adt(id_b, substitution_b)) => {
                if id_a != id_b {
                    return Err(NoSolution);
                }
                self.zip_substs(
                    variance,
                    Some(self.unification_database().adt_variance(*id_a)),
                    substitution_a.as_slice(interner),
                    substitution_b.as_slice(interner),
                )
            }
            (
                TyKind::AssociatedType(id_a, substitution_a),
                TyKind::AssociatedType(id_b, substitution_b),
            ) => {
                if id_a != id_b {
                    return Err(NoSolution);
                }
                self.zip_substs(
                    variance,
                    None, // TODO: AssociatedType variances?
                    substitution_a.as_slice(interner),
                    substitution_b.as_slice(interner),
                )
            }
            (TyKind::Scalar(scalar_a), TyKind::Scalar(scalar_b)) => {
                Zip::zip_with(self, variance, scalar_a, scalar_b)
            }
            (TyKind::Str, TyKind::Str) => Ok(()),
            (TyKind::Tuple(arity_a, substitution_a), TyKind::Tuple(arity_b, substitution_b)) => {
                if arity_a != arity_b {
                    return Err(NoSolution);
                }
                self.zip_substs(
                    variance,
                    Some(Variances::from_iter(
                        self.interner,
                        std::iter::repeat(Variance::Covariant).take(*arity_a),
                    )),
                    substitution_a.as_slice(interner),
                    substitution_b.as_slice(interner),
                )
            }
            (
                TyKind::OpaqueType(id_a, substitution_a),
                TyKind::OpaqueType(id_b, substitution_b),
            ) => {
                if id_a != id_b {
                    return Err(NoSolution);
                }
                self.zip_substs(
                    variance,
                    None,
                    substitution_a.as_slice(interner),
                    substitution_b.as_slice(interner),
                )
            }
            (TyKind::Slice(ty_a), TyKind::Slice(ty_b)) => Zip::zip_with(self, variance, ty_a, ty_b),
            (TyKind::FnDef(id_a, substitution_a), TyKind::FnDef(id_b, substitution_b)) => {
                if id_a != id_b {
                    return Err(NoSolution);
                }
                self.zip_substs(
                    variance,
                    Some(self.unification_database().fn_def_variance(*id_a)),
                    substitution_a.as_slice(interner),
                    substitution_b.as_slice(interner),
                )
            }
            (
                TyKind::Ref(mutability_a, lifetime_a, ty_a),
                TyKind::Ref(mutability_b, lifetime_b, ty_b),
            ) => {
                if mutability_a != mutability_b {
                    return Err(NoSolution);
                }
                // The lifetime is `Contravariant`
                Zip::zip_with(
                    self,
                    variance.xform(Variance::Contravariant),
                    lifetime_a,
                    lifetime_b,
                )?;
                // The type is `Covariant` when not mut, `Invariant` otherwise
                let output_variance = match mutability_a {
                    Mutability::Not => Variance::Covariant,
                    Mutability::Mut => Variance::Invariant,
                };
                Zip::zip_with(self, variance.xform(output_variance), ty_a, ty_b)
            }
            (TyKind::Raw(mutability_a, ty_a), TyKind::Raw(mutability_b, ty_b)) => {
                if mutability_a != mutability_b {
                    return Err(NoSolution);
                }
                let ty_variance = match mutability_a {
                    Mutability::Not => Variance::Covariant,
                    Mutability::Mut => Variance::Invariant,
                };
                Zip::zip_with(self, variance.xform(ty_variance), ty_a, ty_b)
            }
            (TyKind::Never, TyKind::Never) => Ok(()),
            (TyKind::Array(ty_a, const_a), TyKind::Array(ty_b, const_b)) => {
                Zip::zip_with(self, variance, ty_a, ty_b)?;
                Zip::zip_with(self, variance, const_a, const_b)
            }
            (TyKind::Closure(id_a, substitution_a), TyKind::Closure(id_b, substitution_b)) => {
                if id_a != id_b {
                    return Err(NoSolution);
                }
                self.zip_substs(
                    variance,
                    None,
                    substitution_a.as_slice(interner),
                    substitution_b.as_slice(interner),
                )
            }
            (TyKind::Coroutine(id_a, substitution_a), TyKind::Coroutine(id_b, substitution_b)) => {
                if id_a != id_b {
                    return Err(NoSolution);
                }
                self.zip_substs(
                    variance,
                    None,
                    substitution_a.as_slice(interner),
                    substitution_b.as_slice(interner),
                )
            }
            (
                TyKind::CoroutineWitness(id_a, substitution_a),
                TyKind::CoroutineWitness(id_b, substitution_b),
            ) => {
                if id_a != id_b {
                    return Err(NoSolution);
                }
                self.zip_substs(
                    variance,
                    None,
                    substitution_a.as_slice(interner),
                    substitution_b.as_slice(interner),
                )
            }
            (TyKind::Foreign(id_a), TyKind::Foreign(id_b)) => {
                Zip::zip_with(self, variance, id_a, id_b)
            }

            (_, _) => Err(NoSolution),
        }
    }

    /// Unify two inference variables
    #[instrument(level = "debug", skip(self))]
    fn unify_var_var(&mut self, a: InferenceVar, b: InferenceVar) -> Fallible<()> {
        let var1 = EnaVariable::from(a);
        let var2 = EnaVariable::from(b);
        self.table
            .unify
            .unify_var_var(var1, var2)
            .expect("unification of two unbound variables cannot fail");
        Ok(())
    }

    /// Unify a general inference variable with a specific inference variable
    /// (type kind is not `General`). For example, unify a `TyVariableKind::General`
    /// inference variable with a `TyVariableKind::Integer` variable, resulting in the
    /// general inference variable narrowing to an integer variable.

    #[instrument(level = "debug", skip(self))]
    fn unify_general_var_specific_ty(
        &mut self,
        general_var: InferenceVar,
        specific_ty: Ty<I>,
    ) -> Fallible<()> {
        self.table
            .unify
            .unify_var_value(
                general_var,
                InferenceValue::from_ty(self.interner, specific_ty),
            )
            .unwrap();

        Ok(())
    }

    #[instrument(level = "debug", skip(self))]
    fn relate_binders<'a, T>(
        &mut self,
        variance: Variance,
        a: &Binders<T>,
        b: &Binders<T>,
    ) -> Fallible<()>
    where
        T: Clone + TypeFoldable<I> + HasInterner<Interner = I> + Zip<I>,
        't: 'a,
    {
        // for<'a...> T == for<'b...> U
        //
        // if:
        //
        // for<'a...> exists<'b...> T == U &&
        // for<'b...> exists<'a...> T == U

        // for<'a...> T <: for<'b...> U
        //
        // if
        //
        // for<'b...> exists<'a...> T <: U

        let interner = self.interner;

        if let Variance::Invariant | Variance::Contravariant = variance {
            let a_universal = self
                .table
                .instantiate_binders_universally(interner, a.clone());
            let b_existential = self
                .table
                .instantiate_binders_existentially(interner, b.clone());
            Zip::zip_with(self, Variance::Contravariant, &a_universal, &b_existential)?;
        }

        if let Variance::Invariant | Variance::Covariant = variance {
            let b_universal = self
                .table
                .instantiate_binders_universally(interner, b.clone());
            let a_existential = self
                .table
                .instantiate_binders_existentially(interner, a.clone());
            Zip::zip_with(self, Variance::Covariant, &a_existential, &b_universal)?;
        }

        Ok(())
    }

    /// Relate an alias like `<T as Trait>::Item` or `impl Trait` with some other
    /// type `ty`. If the variance is `Invariant`, creates a goal like
    ///
    /// ```notrust
    /// AliasEq(<T as Trait>::Item = U) // associated type projection
    /// AliasEq(impl Trait = U) // impl trait
    /// ```
    /// Otherwise, this creates a new variable `?X`, creates a goal like
    /// ```notrust
    /// AliasEq(Alias = ?X)
    /// ```
    /// and relates `?X` and `ty`.
    #[instrument(level = "debug", skip(self))]
    fn relate_alias_ty(
        &mut self,
        variance: Variance,
        alias: &AliasTy<I>,
        ty: &Ty<I>,
    ) -> Fallible<()> {
        let interner = self.interner;
        match variance {
            Variance::Invariant => {
                self.goals.push(InEnvironment::new(
                    self.environment,
                    AliasEq {
                        alias: alias.clone(),
                        ty: ty.clone(),
                    }
                    .cast(interner),
                ));
                Ok(())
            }
            Variance::Covariant | Variance::Contravariant => {
                let var = self
                    .table
                    .new_variable(UniverseIndex::root())
                    .to_ty(interner);
                self.goals.push(InEnvironment::new(
                    self.environment,
                    AliasEq {
                        alias: alias.clone(),
                        ty: var.clone(),
                    }
                    .cast(interner),
                ));
                self.relate_ty_ty(variance, &var, ty)
            }
        }
    }

    #[instrument(level = "debug", skip(self))]
    fn generalize_ty(
        &mut self,
        ty: &Ty<I>,
        universe_index: UniverseIndex,
        variance: Variance,
    ) -> Ty<I> {
        let interner = self.interner;
        match ty.kind(interner) {
            TyKind::Adt(id, substitution) => {
                let variances = if matches!(variance, Variance::Invariant) {
                    None
                } else {
                    Some(self.unification_database().adt_variance(*id))
                };
                let get_variance = |i| {
                    variances
                        .as_ref()
                        .map(|v| v.as_slice(interner)[i])
                        .unwrap_or(Variance::Invariant)
                };
                TyKind::Adt(
                    *id,
                    self.generalize_substitution(substitution, universe_index, get_variance),
                )
                .intern(interner)
            }
            TyKind::AssociatedType(id, substitution) => TyKind::AssociatedType(
                *id,
                self.generalize_substitution(substitution, universe_index, |_| variance),
            )
            .intern(interner),
            TyKind::Scalar(scalar) => TyKind::Scalar(*scalar).intern(interner),
            TyKind::Str => TyKind::Str.intern(interner),
            TyKind::Tuple(arity, substitution) => TyKind::Tuple(
                *arity,
                self.generalize_substitution(substitution, universe_index, |_| variance),
            )
            .intern(interner),
            TyKind::OpaqueType(id, substitution) => TyKind::OpaqueType(
                *id,
                self.generalize_substitution(substitution, universe_index, |_| variance),
            )
            .intern(interner),
            TyKind::Slice(ty) => {
                TyKind::Slice(self.generalize_ty(ty, universe_index, variance)).intern(interner)
            }
            TyKind::FnDef(id, substitution) => {
                let variances = if matches!(variance, Variance::Invariant) {
                    None
                } else {
                    Some(self.unification_database().fn_def_variance(*id))
                };
                let get_variance = |i| {
                    variances
                        .as_ref()
                        .map(|v| v.as_slice(interner)[i])
                        .unwrap_or(Variance::Invariant)
                };
                TyKind::FnDef(
                    *id,
                    self.generalize_substitution(substitution, universe_index, get_variance),
                )
                .intern(interner)
            }
            TyKind::Ref(mutability, lifetime, ty) => {
                let lifetime_variance = variance.xform(Variance::Contravariant);
                let ty_variance = match mutability {
                    Mutability::Not => Variance::Covariant,
                    Mutability::Mut => Variance::Invariant,
                };
                TyKind::Ref(
                    *mutability,
                    self.generalize_lifetime(lifetime, universe_index, lifetime_variance),
                    self.generalize_ty(ty, universe_index, ty_variance),
                )
                .intern(interner)
            }
            TyKind::Raw(mutability, ty) => {
                let ty_variance = match mutability {
                    Mutability::Not => Variance::Covariant,
                    Mutability::Mut => Variance::Invariant,
                };
                TyKind::Raw(
                    *mutability,
                    self.generalize_ty(ty, universe_index, ty_variance),
                )
                .intern(interner)
            }
            TyKind::Never => TyKind::Never.intern(interner),
            TyKind::Array(ty, const_) => TyKind::Array(
                self.generalize_ty(ty, universe_index, variance),
                self.generalize_const(const_, universe_index),
            )
            .intern(interner),
            TyKind::Closure(id, substitution) => TyKind::Closure(
                *id,
                self.generalize_substitution(substitution, universe_index, |_| variance),
            )
            .intern(interner),
            TyKind::Coroutine(id, substitution) => TyKind::Coroutine(
                *id,
                self.generalize_substitution(substitution, universe_index, |_| variance),
            )
            .intern(interner),
            TyKind::CoroutineWitness(id, substitution) => TyKind::CoroutineWitness(
                *id,
                self.generalize_substitution(substitution, universe_index, |_| variance),
            )
            .intern(interner),
            TyKind::Foreign(id) => TyKind::Foreign(*id).intern(interner),
            TyKind::Error => TyKind::Error.intern(interner),
            TyKind::Dyn(dyn_ty) => {
                let DynTy { bounds, lifetime } = dyn_ty;
                let lifetime = self.generalize_lifetime(
                    lifetime,
                    universe_index,
                    variance.xform(Variance::Contravariant),
                );

                let bounds = bounds.map_ref(|value| {
                    let iter = value.iter(interner).map(|sub_var| {
                        sub_var.map_ref(|clause| {
                            match clause {
                                WhereClause::Implemented(trait_ref) => {
                                    let TraitRef {
                                        ref substitution,
                                        trait_id,
                                    } = *trait_ref;
                                    let substitution = self.generalize_substitution_skip_self(
                                        substitution,
                                        universe_index,
                                        |_| Some(variance),
                                    );
                                    WhereClause::Implemented(TraitRef {
                                        substitution,
                                        trait_id,
                                    })
                                }
                                WhereClause::AliasEq(alias_eq) => {
                                    let AliasEq { alias, ty: _ } = alias_eq;
                                    let alias = match alias {
                                        AliasTy::Opaque(opaque_ty) => {
                                            let OpaqueTy {
                                                ref substitution,
                                                opaque_ty_id,
                                            } = *opaque_ty;
                                            let substitution = self.generalize_substitution(
                                                substitution,
                                                universe_index,
                                                |_| variance,
                                            );
                                            AliasTy::Opaque(OpaqueTy {
                                                substitution,
                                                opaque_ty_id,
                                            })
                                        }
                                        AliasTy::Projection(projection_ty) => {
                                            let ProjectionTy {
                                                ref substitution,
                                                associated_ty_id,
                                            } = *projection_ty;
                                            // TODO: We should be skipping "self", which
                                            // would be the first element of
                                            // "trait_params" if we had a
                                            // `RustIrDatabase` to call
                                            // `split_projection` on...
                                            // let (assoc_ty_datum, trait_params, assoc_type_params) = s.db().split_projection(&self);
                                            let substitution = self.generalize_substitution(
                                                substitution,
                                                universe_index,
                                                |_| variance,
                                            );
                                            AliasTy::Projection(ProjectionTy {
                                                substitution,
                                                associated_ty_id,
                                            })
                                        }
                                    };
                                    let ty =
                                        self.table.new_variable(universe_index).to_ty(interner);
                                    WhereClause::AliasEq(AliasEq { alias, ty })
                                }
                                WhereClause::TypeOutlives(_) => {
                                    let lifetime_var = self.table.new_variable(universe_index);
                                    let lifetime = lifetime_var.to_lifetime(interner);
                                    let ty_var = self.table.new_variable(universe_index);
                                    let ty = ty_var.to_ty(interner);
                                    WhereClause::TypeOutlives(TypeOutlives { ty, lifetime })
                                }
                                WhereClause::LifetimeOutlives(_) => {
                                    unreachable!("dyn Trait never contains LifetimeOutlive bounds")
                                }
                            }
                        })
                    });
                    QuantifiedWhereClauses::from_iter(interner, iter)
                });

                TyKind::Dyn(DynTy { bounds, lifetime }).intern(interner)
            }
            TyKind::Function(fn_ptr) => {
                let FnPointer {
                    num_binders,
                    sig,
                    ref substitution,
                } = *fn_ptr;

                let len = substitution.0.len(interner);
                let vars = substitution.0.iter(interner).enumerate().map(|(i, var)| {
                    if i < len - 1 {
                        self.generalize_generic_var(
                            var,
                            universe_index,
                            variance.xform(Variance::Contravariant),
                        )
                    } else {
                        self.generalize_generic_var(
                            substitution.0.as_slice(interner).last().unwrap(),
                            universe_index,
                            variance,
                        )
                    }
                });

                let substitution = FnSubst(Substitution::from_iter(interner, vars));

                TyKind::Function(FnPointer {
                    num_binders,
                    sig,
                    substitution,
                })
                .intern(interner)
            }
            TyKind::Placeholder(_) | TyKind::BoundVar(_) => {
                debug!("just generalizing to the ty itself: {:?}", ty);
                // BoundVar and PlaceHolder have no internal values to be
                // generic over, so we just relate directly to it
                ty.clone()
            }
            TyKind::Alias(_) => {
                let ena_var = self.table.new_variable(universe_index);
                ena_var.to_ty(interner)
            }
            TyKind::InferenceVar(_var, kind) => {
                if matches!(kind, TyVariableKind::Integer | TyVariableKind::Float) {
                    ty.clone()
                } else if let Some(ty) = self.table.normalize_ty_shallow(interner, ty) {
                    self.generalize_ty(&ty, universe_index, variance)
                } else if matches!(variance, Variance::Invariant) {
                    ty.clone()
                } else {
                    let ena_var = self.table.new_variable(universe_index);
                    ena_var.to_ty(interner)
                }
            }
        }
    }

    #[instrument(level = "debug", skip(self))]
    fn generalize_lifetime(
        &mut self,
        lifetime: &Lifetime<I>,
        universe_index: UniverseIndex,
        variance: Variance,
    ) -> Lifetime<I> {
        if matches!(lifetime.data(self.interner), LifetimeData::BoundVar(_))
            || matches!(variance, Variance::Invariant)
        {
            lifetime.clone()
        } else {
            self.table
                .new_variable(universe_index)
                .to_lifetime(self.interner)
        }
    }

    #[instrument(level = "debug", skip(self))]
    fn generalize_const(&mut self, const_: &Const<I>, universe_index: UniverseIndex) -> Const<I> {
        let data = const_.data(self.interner);
        if matches!(data.value, ConstValue::BoundVar(_)) {
            const_.clone()
        } else {
            self.table
                .new_variable(universe_index)
                .to_const(self.interner, data.ty.clone())
        }
    }

    fn generalize_generic_var(
        &mut self,
        sub_var: &GenericArg<I>,
        universe_index: UniverseIndex,
        variance: Variance,
    ) -> GenericArg<I> {
        let interner = self.interner;
        (match sub_var.data(interner) {
            GenericArgData::Ty(ty) => {
                GenericArgData::Ty(self.generalize_ty(ty, universe_index, variance))
            }
            GenericArgData::Lifetime(lifetime) => GenericArgData::Lifetime(
                self.generalize_lifetime(lifetime, universe_index, variance),
            ),
            GenericArgData::Const(const_value) => {
                GenericArgData::Const(self.generalize_const(const_value, universe_index))
            }
        })
        .intern(interner)
    }

    /// Generalizes all but the first
    #[instrument(level = "debug", skip(self, get_variance))]
    fn generalize_substitution_skip_self<F: Fn(usize) -> Option<Variance>>(
        &mut self,
        substitution: &Substitution<I>,
        universe_index: UniverseIndex,
        get_variance: F,
    ) -> Substitution<I> {
        let interner = self.interner;
        let vars = substitution.iter(interner).enumerate().map(|(i, sub_var)| {
            if i == 0 {
                sub_var.clone()
            } else {
                let variance = get_variance(i).unwrap_or(Variance::Invariant);
                self.generalize_generic_var(sub_var, universe_index, variance)
            }
        });
        Substitution::from_iter(interner, vars)
    }

    #[instrument(level = "debug", skip(self, get_variance))]
    fn generalize_substitution<F: Fn(usize) -> Variance>(
        &mut self,
        substitution: &Substitution<I>,
        universe_index: UniverseIndex,
        get_variance: F,
    ) -> Substitution<I> {
        let interner = self.interner;
        let vars = substitution.iter(interner).enumerate().map(|(i, sub_var)| {
            let variance = get_variance(i);
            self.generalize_generic_var(sub_var, universe_index, variance)
        });

        Substitution::from_iter(interner, vars)
    }

    /// Unify an inference variable `var` with some non-inference
    /// variable `ty`, just bind `var` to `ty`. But we must enforce two conditions:
    ///
    /// - `var` does not appear inside of `ty` (the standard `OccursCheck`)
    /// - `ty` does not reference anything in a lifetime that could not be named in `var`
    ///   (the extended `OccursCheck` created to handle universes)
    #[instrument(level = "debug", skip(self))]
    fn relate_var_ty(
        &mut self,
        variance: Variance,
        var: InferenceVar,
        var_kind: TyVariableKind,
        ty: &Ty<I>,
    ) -> Fallible<()> {
        let interner = self.interner;

        match (var_kind, ty.is_integer(interner), ty.is_float(interner)) {
            // General inference variables can unify with any type
            (TyVariableKind::General, _, _)
            // Integer inference variables can only unify with integer types
            | (TyVariableKind::Integer, true, _)
            // Float inference variables can only unify with float types
            | (TyVariableKind::Float, _, true) => {
            },
            _ => return Err(NoSolution),
        }

        let var = EnaVariable::from(var);

        // Determine the universe index associated with this
        // variable. This is basically a count of the number of
        // `forall` binders that had been introduced at the point
        // this variable was created -- though it may change over time
        // as the variable is unified.
        let universe_index = self.table.universe_of_unbound_var(var);
        // let universe_index = self.table.max_universe();

        debug!("relate_var_ty: universe index of var: {:?}", universe_index);

        debug!("trying fold_with on {:?}", ty);
        let ty1 = ty
            .clone()
            .try_fold_with(
                &mut OccursCheck::new(self, var, universe_index),
                DebruijnIndex::INNERMOST,
            )
            .map_err(|e| {
                debug!("failed to fold {:?}", ty);
                e
            })?;

        // "Generalize" types. This ensures that we aren't accidentally forcing
        // too much onto `var`. Instead of directly setting `var` equal to `ty`,
        // we just take the outermost structure we _know_ `var` holds, and then
        // apply that to `ty`. This involves creating new inference vars for
        // everything inside `var`, then calling `relate_ty_ty` to relate those
        // inference vars to the things they generalized with the correct
        // variance.

        // The main problem this solves is that lifetime relationships are
        // relationships, not just eq ones. So when solving &'a u32 <: U,
        // generalizing we would end up with U = &'a u32. Instead, we want
        // U = &'b u32, with a lifetime constraint 'a <: 'b. This matters
        // especially when solving multiple constraints - for example, &'a u32
        // <: U, &'b u32 <: U (where without generalizing, we'd end up with 'a
        // <: 'b, where we really want 'a <: 'c, 'b <: 'c for some 'c).

        // Example operation: consider `ty` as `&'x SomeType`. To generalize
        // this, we create two new vars `'0` and `1`. Then we relate `var` with
        // `&'0 1` and `&'0 1` with `&'x SomeType`. The second relation will
        // recurse, and we'll end up relating `'0` with `'x` and `1` with `SomeType`.
        let generalized_val = self.generalize_ty(&ty1, universe_index, variance);

        debug!("var {:?} generalized to {:?}", var, generalized_val);

        self.table
            .unify
            .unify_var_value(
                var,
                InferenceValue::from_ty(interner, generalized_val.clone()),
            )
            .unwrap();
        debug!("var {:?} set to {:?}", var, generalized_val);

        self.relate_ty_ty(variance, &generalized_val, &ty1)?;

        debug!(
            "generalized version {:?} related to original {:?}",
            generalized_val, ty1
        );

        Ok(())
    }

    fn relate_lifetime_lifetime(
        &mut self,
        variance: Variance,
        a: &Lifetime<I>,
        b: &Lifetime<I>,
    ) -> Fallible<()> {
        let interner = self.interner;

        let n_a = self.table.normalize_lifetime_shallow(interner, a);
        let n_b = self.table.normalize_lifetime_shallow(interner, b);
        let a = n_a.as_ref().unwrap_or(a);
        let b = n_b.as_ref().unwrap_or(b);

        debug_span!("relate_lifetime_lifetime", ?variance, ?a, ?b);

        match (a.data(interner), b.data(interner)) {
            (&LifetimeData::InferenceVar(var_a), &LifetimeData::InferenceVar(var_b)) => {
                let var_a = EnaVariable::from(var_a);
                let var_b = EnaVariable::from(var_b);
                debug!(?var_a, ?var_b);
                self.table.unify.unify_var_var(var_a, var_b).unwrap();
                Ok(())
            }

            (
                &LifetimeData::InferenceVar(a_var),
                &LifetimeData::Placeholder(PlaceholderIndex { ui, .. }),
            ) => self.unify_lifetime_var(variance, a_var, b, ui),

            (
                &LifetimeData::Placeholder(PlaceholderIndex { ui, .. }),
                &LifetimeData::InferenceVar(b_var),
            ) => self.unify_lifetime_var(variance.invert(), b_var, a, ui),

            (&LifetimeData::InferenceVar(a_var), &LifetimeData::Erased)
            | (&LifetimeData::InferenceVar(a_var), &LifetimeData::Static)
            | (&LifetimeData::InferenceVar(a_var), &LifetimeData::Error) => {
                self.unify_lifetime_var(variance, a_var, b, UniverseIndex::root())
            }

            (&LifetimeData::Erased, &LifetimeData::InferenceVar(b_var))
            | (&LifetimeData::Static, &LifetimeData::InferenceVar(b_var))
            | (&LifetimeData::Error, &LifetimeData::InferenceVar(b_var)) => {
                self.unify_lifetime_var(variance.invert(), b_var, a, UniverseIndex::root())
            }

            (&LifetimeData::Static, &LifetimeData::Static)
            | (&LifetimeData::Erased, &LifetimeData::Erased) => Ok(()),

            (&LifetimeData::Static, &LifetimeData::Placeholder(_))
            | (&LifetimeData::Static, &LifetimeData::Erased)
            | (&LifetimeData::Placeholder(_), &LifetimeData::Static)
            | (&LifetimeData::Placeholder(_), &LifetimeData::Placeholder(_))
            | (&LifetimeData::Placeholder(_), &LifetimeData::Erased)
            | (&LifetimeData::Erased, &LifetimeData::Static)
            | (&LifetimeData::Erased, &LifetimeData::Placeholder(_)) => {
                if a != b {
                    self.push_lifetime_outlives_goals(variance, a.clone(), b.clone());
                    Ok(())
                } else {
                    Ok(())
                }
            }

            (LifetimeData::Error, _) | (_, LifetimeData::Error) => Ok(()),
            (LifetimeData::BoundVar(_), _) | (_, LifetimeData::BoundVar(_)) => panic!(
                "unification encountered bound variable: a={:?} b={:?}",
                a, b
            ),

            (LifetimeData::Phantom(..), _) | (_, LifetimeData::Phantom(..)) => unreachable!(),
        }
    }

    #[instrument(level = "debug", skip(self))]
    fn unify_lifetime_var(
        &mut self,
        variance: Variance,
        var: InferenceVar,
        value: &Lifetime<I>,
        value_ui: UniverseIndex,
    ) -> Fallible<()> {
        let var = EnaVariable::from(var);
        let var_ui = self.table.universe_of_unbound_var(var);
        if var_ui.can_see(value_ui) && matches!(variance, Variance::Invariant) {
            debug!("{:?} in {:?} can see {:?}; unifying", var, var_ui, value_ui);
            self.table
                .unify
                .unify_var_value(
                    var,
                    InferenceValue::from_lifetime(self.interner, value.clone()),
                )
                .unwrap();
            Ok(())
        } else {
            debug!(
                "{:?} in {:?} cannot see {:?}; pushing constraint",
                var, var_ui, value_ui
            );
            self.push_lifetime_outlives_goals(
                variance,
                var.to_lifetime(self.interner),
                value.clone(),
            );
            Ok(())
        }
    }

    fn relate_const_const<'a>(
        &mut self,
        variance: Variance,
        a: &'a Const<I>,
        b: &'a Const<I>,
    ) -> Fallible<()> {
        let interner = self.interner;

        let n_a = self.table.normalize_const_shallow(interner, a);
        let n_b = self.table.normalize_const_shallow(interner, b);
        let a = n_a.as_ref().unwrap_or(a);
        let b = n_b.as_ref().unwrap_or(b);

        debug_span!("relate_const_const", ?variance, ?a, ?b);

        let ConstData {
            ty: a_ty,
            value: a_val,
        } = a.data(interner);
        let ConstData {
            ty: b_ty,
            value: b_val,
        } = b.data(interner);

        self.relate_ty_ty(variance, a_ty, b_ty)?;

        match (a_val, b_val) {
            // Unifying two inference variables: unify them in the underlying
            // ena table.
            (&ConstValue::InferenceVar(var1), &ConstValue::InferenceVar(var2)) => {
                debug!(?var1, ?var2, "relate_ty_ty");
                let var1 = EnaVariable::from(var1);
                let var2 = EnaVariable::from(var2);
                self.table
                    .unify
                    .unify_var_var(var1, var2)
                    .expect("unification of two unbound variables cannot fail");
                Ok(())
            }

            // Unifying an inference variables with a non-inference variable.
            (&ConstValue::InferenceVar(var), &ConstValue::Concrete(_))
            | (&ConstValue::InferenceVar(var), &ConstValue::Placeholder(_)) => {
                debug!(?var, ty=?b, "unify_var_ty");
                self.unify_var_const(var, b)
            }

            (&ConstValue::Concrete(_), &ConstValue::InferenceVar(var))
            | (&ConstValue::Placeholder(_), &ConstValue::InferenceVar(var)) => {
                debug!(?var, ty=?a, "unify_var_ty");
                self.unify_var_const(var, a)
            }

            (&ConstValue::Placeholder(p1), &ConstValue::Placeholder(p2)) => {
                Zip::zip_with(self, variance, &p1, &p2)
            }

            (&ConstValue::Concrete(ref ev1), &ConstValue::Concrete(ref ev2)) => {
                if ev1.const_eq(a_ty, ev2, interner) {
                    Ok(())
                } else {
                    Err(NoSolution)
                }
            }

            (&ConstValue::Concrete(_), &ConstValue::Placeholder(_))
            | (&ConstValue::Placeholder(_), &ConstValue::Concrete(_)) => Err(NoSolution),

            (ConstValue::BoundVar(_), _) | (_, ConstValue::BoundVar(_)) => panic!(
                "unification encountered bound variable: a={:?} b={:?}",
                a, b
            ),
        }
    }

    #[instrument(level = "debug", skip(self))]
    fn unify_var_const(&mut self, var: InferenceVar, c: &Const<I>) -> Fallible<()> {
        let interner = self.interner;
        let var = EnaVariable::from(var);

        // Determine the universe index associated with this
        // variable. This is basically a count of the number of
        // `forall` binders that had been introduced at the point
        // this variable was created -- though it may change over time
        // as the variable is unified.
        let universe_index = self.table.universe_of_unbound_var(var);

        let c1 = c.clone().try_fold_with(
            &mut OccursCheck::new(self, var, universe_index),
            DebruijnIndex::INNERMOST,
        )?;

        debug!("unify_var_const: var {:?} set to {:?}", var, c1);
        self.table
            .unify
            .unify_var_value(var, InferenceValue::from_const(interner, c1))
            .unwrap();

        Ok(())
    }

    /// Relate `a`, `b` such that if `variance = Covariant`, `a` is a subtype of
    /// `b` and thus `a` must outlive `b`.
    fn push_lifetime_outlives_goals(&mut self, variance: Variance, a: Lifetime<I>, b: Lifetime<I>) {
        debug!(
            "pushing lifetime outlives goals for a={:?} b={:?} with variance {:?}",
            a, b, variance
        );
        if matches!(variance, Variance::Invariant | Variance::Contravariant) {
            self.goals.push(InEnvironment::new(
                self.environment,
                WhereClause::LifetimeOutlives(LifetimeOutlives {
                    a: a.clone(),
                    b: b.clone(),
                })
                .cast(self.interner),
            ));
        }
        if matches!(variance, Variance::Invariant | Variance::Covariant) {
            self.goals.push(InEnvironment::new(
                self.environment,
                WhereClause::LifetimeOutlives(LifetimeOutlives { a: b, b: a }).cast(self.interner),
            ));
        }
    }

    /// Pushes a goal of `a` being a subtype of `b`.
    fn push_subtype_goal(&mut self, a: Ty<I>, b: Ty<I>) {
        let subtype_goal = GoalData::SubtypeGoal(SubtypeGoal { a, b }).intern(self.interner());
        self.goals
            .push(InEnvironment::new(self.environment, subtype_goal));
    }
}

impl<'i, I: Interner> Zipper<I> for Unifier<'i, I> {
    fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> {
        debug!("zip_tys {:?}, {:?}, {:?}", variance, a, b);
        self.relate_ty_ty(variance, a, b)
    }

    fn zip_lifetimes(
        &mut self,
        variance: Variance,
        a: &Lifetime<I>,
        b: &Lifetime<I>,
    ) -> Fallible<()> {
        self.relate_lifetime_lifetime(variance, a, b)
    }

    fn zip_consts(&mut self, variance: Variance, a: &Const<I>, b: &Const<I>) -> Fallible<()> {
        self.relate_const_const(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>,
    {
        // The binders that appear in types (apart from quantified types, which are
        // handled in `unify_ty`) appear as part of `dyn Trait` and `impl Trait` types.
        //
        // They come in two varieties:
        //
        // * The existential binder from `dyn Trait` / `impl Trait`
        //   (representing the hidden "self" type)
        // * The `for<..>` binders from higher-ranked traits.
        //
        // In both cases we can use the same `relate_binders` routine.

        self.relate_binders(variance, a, b)
    }

    fn interner(&self) -> I {
        self.interner
    }

    fn unification_database(&self) -> &dyn UnificationDatabase<I> {
        self.db
    }
}

struct OccursCheck<'u, 't, I: Interner> {
    unifier: &'u mut Unifier<'t, I>,
    var: EnaVariable<I>,
    universe_index: UniverseIndex,
}

impl<'u, 't, I: Interner> OccursCheck<'u, 't, I> {
    fn new(
        unifier: &'u mut Unifier<'t, I>,
        var: EnaVariable<I>,
        universe_index: UniverseIndex,
    ) -> Self {
        OccursCheck {
            unifier,
            var,
            universe_index,
        }
    }
}

impl<'i, I: Interner> FallibleTypeFolder<I> for OccursCheck<'_, 'i, I> {
    type Error = NoSolution;

    fn as_dyn(&mut self) -> &mut dyn FallibleTypeFolder<I, Error = Self::Error> {
        self
    }

    fn try_fold_free_placeholder_ty(
        &mut self,
        universe: PlaceholderIndex,
        _outer_binder: DebruijnIndex,
    ) -> Fallible<Ty<I>> {
        let interner = self.interner();
        if self.universe_index < universe.ui {
            debug!(
                "OccursCheck aborting because self.universe_index ({:?}) < universe.ui ({:?})",
                self.universe_index, universe.ui
            );
            Err(NoSolution)
        } else {
            Ok(universe.to_ty(interner)) // no need to shift, not relative to depth
        }
    }

    fn try_fold_free_placeholder_const(
        &mut self,
        ty: Ty<I>,
        universe: PlaceholderIndex,
        _outer_binder: DebruijnIndex,
    ) -> Fallible<Const<I>> {
        let interner = self.interner();
        if self.universe_index < universe.ui {
            Err(NoSolution)
        } else {
            Ok(universe.to_const(interner, ty)) // no need to shift, not relative to depth
        }
    }

    #[instrument(level = "debug", skip(self))]
    fn try_fold_free_placeholder_lifetime(
        &mut self,
        ui: PlaceholderIndex,
        _outer_binder: DebruijnIndex,
    ) -> Fallible<Lifetime<I>> {
        let interner = self.interner();
        if self.universe_index < ui.ui {
            // Scenario is like:
            //
            // exists<T> forall<'b> ?T = Foo<'b>
            //
            // unlike with a type variable, this **might** be
            // ok.  Ultimately it depends on whether the
            // `forall` also introduced relations to lifetimes
            // nameable in T. To handle that, we introduce a
            // fresh region variable `'x` in same universe as `T`
            // and add a side-constraint that `'x = 'b`:
            //
            // exists<'x> forall<'b> ?T = Foo<'x>, where 'x = 'b

            let tick_x = self.unifier.table.new_variable(self.universe_index);
            self.unifier.push_lifetime_outlives_goals(
                Variance::Invariant,
                tick_x.to_lifetime(interner),
                ui.to_lifetime(interner),
            );
            Ok(tick_x.to_lifetime(interner))
        } else {
            // If the `ui` is higher than `self.universe_index`, then we can name
            // this lifetime, no problem.
            Ok(ui.to_lifetime(interner)) // no need to shift, not relative to depth
        }
    }

    fn try_fold_inference_ty(
        &mut self,
        var: InferenceVar,
        kind: TyVariableKind,
        _outer_binder: DebruijnIndex,
    ) -> Fallible<Ty<I>> {
        let interner = self.interner();
        let var = EnaVariable::from(var);
        match self.unifier.table.unify.probe_value(var) {
            // If this variable already has a value, fold over that value instead.
            InferenceValue::Bound(normalized_ty) => {
                let normalized_ty = normalized_ty.assert_ty_ref(interner);
                let normalized_ty = normalized_ty
                    .clone()
                    .try_fold_with(self, DebruijnIndex::INNERMOST)?;
                assert!(!normalized_ty.needs_shift(interner));
                Ok(normalized_ty)
            }

            // Otherwise, check the universe of the variable, and also
            // check for cycles with `self.var` (which this will soon
            // become the value of).
            InferenceValue::Unbound(ui) => {
                if self.unifier.table.unify.unioned(var, self.var) {
                    debug!(
                        "OccursCheck aborting because {:?} unioned with {:?}",
                        var, self.var,
                    );
                    return Err(NoSolution);
                }

                if self.universe_index < ui {
                    // Scenario is like:
                    //
                    // ?A = foo(?B)
                    //
                    // where ?A is in universe 0 and ?B is in universe 1.
                    // This is OK, if ?B is promoted to universe 0.
                    self.unifier
                        .table
                        .unify
                        .unify_var_value(var, InferenceValue::Unbound(self.universe_index))
                        .unwrap();
                }

                Ok(var.to_ty_with_kind(interner, kind))
            }
        }
    }

    fn try_fold_inference_const(
        &mut self,
        ty: Ty<I>,
        var: InferenceVar,
        _outer_binder: DebruijnIndex,
    ) -> Fallible<Const<I>> {
        let interner = self.interner();
        let var = EnaVariable::from(var);
        match self.unifier.table.unify.probe_value(var) {
            // If this variable already has a value, fold over that value instead.
            InferenceValue::Bound(normalized_const) => {
                let normalized_const = normalized_const.assert_const_ref(interner);
                let normalized_const = normalized_const
                    .clone()
                    .try_fold_with(self, DebruijnIndex::INNERMOST)?;
                assert!(!normalized_const.needs_shift(interner));
                Ok(normalized_const)
            }

            // Otherwise, check the universe of the variable, and also
            // check for cycles with `self.var` (which this will soon
            // become the value of).
            InferenceValue::Unbound(ui) => {
                if self.unifier.table.unify.unioned(var, self.var) {
                    return Err(NoSolution);
                }

                if self.universe_index < ui {
                    // Scenario is like:
                    //
                    // forall<const A> exists<const B> ?C = Foo<B>
                    //
                    // where A is in universe 0 and B is in universe 1.
                    // This is OK, if B is promoted to universe 0.
                    self.unifier
                        .table
                        .unify
                        .unify_var_value(var, InferenceValue::Unbound(self.universe_index))
                        .unwrap();
                }

                Ok(var.to_const(interner, ty))
            }
        }
    }

    fn try_fold_inference_lifetime(
        &mut self,
        var: InferenceVar,
        outer_binder: DebruijnIndex,
    ) -> Fallible<Lifetime<I>> {
        // a free existentially bound region; find the
        // inference variable it corresponds to
        let interner = self.interner();
        let var = EnaVariable::from(var);
        match self.unifier.table.unify.probe_value(var) {
            InferenceValue::Unbound(ui) => {
                if self.universe_index < ui {
                    // Scenario is like:
                    //
                    // exists<T> forall<'b> exists<'a> ?T = Foo<'a>
                    //
                    // where ?A is in universe 0 and `'b` is in universe 1.
                    // This is OK, if `'b` is promoted to universe 0.
                    self.unifier
                        .table
                        .unify
                        .unify_var_value(var, InferenceValue::Unbound(self.universe_index))
                        .unwrap();
                }
                Ok(var.to_lifetime(interner))
            }

            InferenceValue::Bound(l) => {
                let l = l.assert_lifetime_ref(interner);
                let l = l.clone().try_fold_with(self, outer_binder)?;
                assert!(!l.needs_shift(interner));
                Ok(l)
            }
        }
    }

    fn forbid_free_vars(&self) -> bool {
        true
    }

    fn interner(&self) -> I {
        self.unifier.interner
    }
}