diff options
Diffstat (limited to 'vendor/chalk-solve-0.87.0/src/infer/unify.rs')
-rw-r--r-- | vendor/chalk-solve-0.87.0/src/infer/unify.rs | 1448 |
1 files changed, 1448 insertions, 0 deletions
diff --git a/vendor/chalk-solve-0.87.0/src/infer/unify.rs b/vendor/chalk-solve-0.87.0/src/infer/unify.rs new file mode 100644 index 000000000..10086e651 --- /dev/null +++ b/vendor/chalk-solve-0.87.0/src/infer/unify.rs @@ -0,0 +1,1448 @@ +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) + } + + // 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::Generator(id_a, substitution_a), TyKind::Generator(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::GeneratorWitness(id_a, substitution_a), + TyKind::GeneratorWitness(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) + } + (TyKind::Error, TyKind::Error) => Ok(()), + + (_, _) => 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::Generator(id, substitution) => TyKind::Generator( + *id, + self.generalize_substitution(substitution, universe_index, |_| variance), + ) + .intern(interner), + TyKind::GeneratorWitness(id, substitution) => TyKind::GeneratorWitness( + *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) => { + self.unify_lifetime_var(variance, a_var, b, UniverseIndex::root()) + } + + (&LifetimeData::Erased, &LifetimeData::InferenceVar(b_var)) + | (&LifetimeData::Static, &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::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 + } +} |