From 64d98f8ee037282c35007b64c2649055c56af1db Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:19:03 +0200 Subject: Merging upstream version 1.68.2+dfsg1. Signed-off-by: Daniel Baumann --- vendor/chalk-solve/src/infer/canonicalize.rs | 237 ---- vendor/chalk-solve/src/infer/instantiate.rs | 111 -- vendor/chalk-solve/src/infer/invert.rs | 174 --- vendor/chalk-solve/src/infer/test.rs | 422 ------- vendor/chalk-solve/src/infer/ucanonicalize.rs | 336 ------ vendor/chalk-solve/src/infer/unify.rs | 1448 ------------------------- vendor/chalk-solve/src/infer/var.rs | 152 --- 7 files changed, 2880 deletions(-) delete mode 100644 vendor/chalk-solve/src/infer/canonicalize.rs delete mode 100644 vendor/chalk-solve/src/infer/instantiate.rs delete mode 100644 vendor/chalk-solve/src/infer/invert.rs delete mode 100644 vendor/chalk-solve/src/infer/test.rs delete mode 100644 vendor/chalk-solve/src/infer/ucanonicalize.rs delete mode 100644 vendor/chalk-solve/src/infer/unify.rs delete mode 100644 vendor/chalk-solve/src/infer/var.rs (limited to 'vendor/chalk-solve/src/infer') diff --git a/vendor/chalk-solve/src/infer/canonicalize.rs b/vendor/chalk-solve/src/infer/canonicalize.rs deleted file mode 100644 index ddec0515d..000000000 --- a/vendor/chalk-solve/src/infer/canonicalize.rs +++ /dev/null @@ -1,237 +0,0 @@ -use crate::debug_span; -use chalk_derive::FallibleTypeFolder; -use chalk_ir::fold::shift::Shift; -use chalk_ir::fold::{TypeFoldable, TypeFolder}; -use chalk_ir::interner::{HasInterner, Interner}; -use chalk_ir::*; -use std::cmp::max; -use tracing::{debug, instrument}; - -use super::{InferenceTable, ParameterEnaVariable}; - -impl InferenceTable { - /// Given a value `value` with variables in it, replaces those variables - /// with their instantiated values; any variables not yet instantiated are - /// replaced with a small integer index 0..N in order of appearance. The - /// result is a canonicalized representation of `value`. - /// - /// Example: - /// - /// ?22: Foo - /// - /// would be quantified to - /// - /// Canonical { value: `?0: Foo`, binders: [ui(?22), ui(?23)] } - /// - /// where `ui(?22)` and `ui(?23)` are the universe indices of `?22` and - /// `?23` respectively. - /// - /// A substitution mapping from the free variables to their re-bound form is - /// also returned. - pub fn canonicalize(&mut self, interner: I, value: T) -> Canonicalized - where - T: TypeFoldable, - T: HasInterner, - { - debug_span!("canonicalize", "{:#?}", value); - let mut q = Canonicalizer { - table: self, - free_vars: Vec::new(), - max_universe: UniverseIndex::root(), - interner, - }; - let value = value - .try_fold_with(&mut q, DebruijnIndex::INNERMOST) - .unwrap(); - let free_vars = q.free_vars.clone(); - - Canonicalized { - quantified: Canonical { - value, - binders: q.into_binders(), - }, - free_vars, - } - } -} - -#[derive(Debug)] -pub struct Canonicalized { - /// The canonicalized result. - pub quantified: Canonical, - - /// The free existential variables, along with the universes they inhabit. - pub free_vars: Vec>, -} - -#[derive(FallibleTypeFolder)] -struct Canonicalizer<'q, I: Interner> { - table: &'q mut InferenceTable, - free_vars: Vec>, - max_universe: UniverseIndex, - interner: I, -} - -impl<'q, I: Interner> Canonicalizer<'q, I> { - fn into_binders(self) -> CanonicalVarKinds { - let Canonicalizer { - table, - free_vars, - interner, - .. - } = self; - CanonicalVarKinds::from_iter( - interner, - free_vars - .into_iter() - .map(|p_v| p_v.map(|v| table.universe_of_unbound_var(v))), - ) - } - - fn add(&mut self, free_var: ParameterEnaVariable) -> usize { - self.max_universe = max( - self.max_universe, - self.table.universe_of_unbound_var(*free_var.skip_kind()), - ); - - self.free_vars - .iter() - .position(|v| v.skip_kind() == free_var.skip_kind()) - .unwrap_or_else(|| { - let next_index = self.free_vars.len(); - self.free_vars.push(free_var); - next_index - }) - } -} - -impl<'i, I: Interner> TypeFolder for Canonicalizer<'i, I> { - fn as_dyn(&mut self) -> &mut dyn TypeFolder { - self - } - - fn fold_free_placeholder_ty( - &mut self, - universe: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Ty { - let interner = self.interner; - self.max_universe = max(self.max_universe, universe.ui); - universe.to_ty(interner) - } - - fn fold_free_placeholder_lifetime( - &mut self, - universe: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Lifetime { - let interner = self.interner; - self.max_universe = max(self.max_universe, universe.ui); - universe.to_lifetime(interner) - } - - fn fold_free_placeholder_const( - &mut self, - ty: Ty, - universe: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Const { - let interner = self.interner; - self.max_universe = max(self.max_universe, universe.ui); - universe.to_const(interner, ty) - } - - fn forbid_free_vars(&self) -> bool { - true - } - - #[instrument(level = "debug", skip(self))] - fn fold_inference_ty( - &mut self, - var: InferenceVar, - kind: TyVariableKind, - outer_binder: DebruijnIndex, - ) -> Ty { - let interner = self.interner; - match self.table.probe_var(var) { - Some(ty) => { - let ty = ty.assert_ty_ref(interner); - debug!("bound to {:?}", ty); - ty.clone() - .fold_with(self, DebruijnIndex::INNERMOST) - .shifted_in_from(interner, outer_binder) - } - None => { - // If this variable is not yet bound, find its - // canonical index `root_var` in the union-find table, - // and then map `root_var` to a fresh index that is - // unique to this quantification. - let free_var = - ParameterEnaVariable::new(VariableKind::Ty(kind), self.table.unify.find(var)); - - let bound_var = BoundVar::new(DebruijnIndex::INNERMOST, self.add(free_var)); - debug!(position=?bound_var, "not yet unified"); - TyKind::BoundVar(bound_var.shifted_in_from(outer_binder)).intern(interner) - } - } - } - - #[instrument(level = "debug", skip(self))] - fn fold_inference_lifetime( - &mut self, - var: InferenceVar, - outer_binder: DebruijnIndex, - ) -> Lifetime { - let interner = self.interner; - match self.table.probe_var(var) { - Some(l) => { - let l = l.assert_lifetime_ref(interner); - debug!("bound to {:?}", l); - l.clone() - .fold_with(self, DebruijnIndex::INNERMOST) - .shifted_in_from(interner, outer_binder) - } - None => { - let free_var = - ParameterEnaVariable::new(VariableKind::Lifetime, self.table.unify.find(var)); - let bound_var = BoundVar::new(DebruijnIndex::INNERMOST, self.add(free_var)); - debug!(position=?bound_var, "not yet unified"); - LifetimeData::BoundVar(bound_var.shifted_in_from(outer_binder)).intern(interner) - } - } - } - - #[instrument(level = "debug", skip(self, ty))] - fn fold_inference_const( - &mut self, - ty: Ty, - var: InferenceVar, - outer_binder: DebruijnIndex, - ) -> Const { - let interner = self.interner; - match self.table.probe_var(var) { - Some(c) => { - let c = c.assert_const_ref(interner); - debug!("bound to {:?}", c); - c.clone() - .fold_with(self, DebruijnIndex::INNERMOST) - .shifted_in_from(interner, outer_binder) - } - None => { - let free_var = ParameterEnaVariable::new( - VariableKind::Const(ty.clone()), - self.table.unify.find(var), - ); - let bound_var = BoundVar::new(DebruijnIndex::INNERMOST, self.add(free_var)); - debug!(position = ?bound_var, "not yet unified"); - bound_var - .shifted_in_from(outer_binder) - .to_const(interner, ty) - } - } - } - - fn interner(&self) -> I { - self.interner - } -} diff --git a/vendor/chalk-solve/src/infer/instantiate.rs b/vendor/chalk-solve/src/infer/instantiate.rs deleted file mode 100644 index 161271f23..000000000 --- a/vendor/chalk-solve/src/infer/instantiate.rs +++ /dev/null @@ -1,111 +0,0 @@ -use chalk_ir::fold::*; -use chalk_ir::interner::HasInterner; -use std::fmt::Debug; -use tracing::instrument; - -use super::*; - -impl InferenceTable { - /// Given the binders from a canonicalized value C, returns a - /// substitution S mapping each free variable in C to a fresh - /// inference variable. This substitution can then be applied to - /// C, which would be equivalent to - /// `self.instantiate_canonical(v)`. - pub(super) fn fresh_subst( - &mut self, - interner: I, - binders: &[CanonicalVarKind], - ) -> Substitution { - Substitution::from_iter( - interner, - binders.iter().map(|kind| { - let param_infer_var = kind.map_ref(|&ui| self.new_variable(ui)); - param_infer_var.to_generic_arg(interner) - }), - ) - } - - /// Variant on `instantiate` that takes a `Canonical`. - pub fn instantiate_canonical(&mut self, interner: I, bound: Canonical) -> T - where - T: HasInterner + TypeFoldable + Debug, - { - let subst = self.fresh_subst(interner, bound.binders.as_slice(interner)); - subst.apply(bound.value, interner) - } - - /// Instantiates `arg` with fresh existential variables in the - /// given universe; the kinds of the variables are implied by - /// `binders`. This is used to apply a universally quantified - /// clause like `forall X, 'Y. P => Q`. Here the `binders` - /// argument is referring to `X, 'Y`. - fn instantiate_in( - &mut self, - interner: I, - universe: UniverseIndex, - binders: impl Iterator>, - arg: T, - ) -> T - where - T: TypeFoldable, - { - let binders: Vec<_> = binders - .map(|pk| CanonicalVarKind::new(pk, universe)) - .collect(); - let subst = self.fresh_subst(interner, &binders); - subst.apply(arg, interner) - } - - /// Variant on `instantiate_in` that takes a `Binders`. - #[instrument(level = "debug", skip(self, interner))] - pub fn instantiate_binders_existentially(&mut self, interner: I, arg: Binders) -> T - where - T: TypeFoldable + HasInterner, - { - let (value, binders) = arg.into_value_and_skipped_binders(); - - let max_universe = self.max_universe; - self.instantiate_in( - interner, - max_universe, - binders.iter(interner).cloned(), - value, - ) - } - - #[instrument(level = "debug", skip(self, interner))] - pub fn instantiate_binders_universally(&mut self, interner: I, arg: Binders) -> T - where - T: TypeFoldable + HasInterner, - { - let (value, binders) = arg.into_value_and_skipped_binders(); - - let mut lazy_ui = None; - let mut ui = || { - lazy_ui.unwrap_or_else(|| { - let ui = self.new_universe(); - lazy_ui = Some(ui); - ui - }) - }; - let parameters: Vec<_> = binders - .iter(interner) - .cloned() - .enumerate() - .map(|(idx, pk)| { - let placeholder_idx = PlaceholderIndex { ui: ui(), idx }; - match pk { - VariableKind::Lifetime => { - let lt = placeholder_idx.to_lifetime(interner); - lt.cast(interner) - } - VariableKind::Ty(_) => placeholder_idx.to_ty(interner).cast(interner), - VariableKind::Const(ty) => { - placeholder_idx.to_const(interner, ty).cast(interner) - } - } - }) - .collect(); - Subst::apply(interner, ¶meters, value) - } -} diff --git a/vendor/chalk-solve/src/infer/invert.rs b/vendor/chalk-solve/src/infer/invert.rs deleted file mode 100644 index e5bc3590c..000000000 --- a/vendor/chalk-solve/src/infer/invert.rs +++ /dev/null @@ -1,174 +0,0 @@ -use chalk_derive::FallibleTypeFolder; -use chalk_ir::fold::shift::Shift; -use chalk_ir::fold::{TypeFoldable, TypeFolder}; -use chalk_ir::interner::HasInterner; -use chalk_ir::interner::Interner; -use chalk_ir::*; -use rustc_hash::FxHashMap; - -use super::canonicalize::Canonicalized; -use super::{EnaVariable, InferenceTable}; - -impl InferenceTable { - /// Converts `value` into a "negation" value -- meaning one that, - /// if we can find any answer to it, then the negation fails. For - /// goals that do not contain any free variables, then this is a - /// no-op operation. - /// - /// If `value` contains any existential variables that have not - /// yet been assigned a value, then this function will return - /// `None`, indicating that we cannot prove negation for this goal - /// yet. This follows the approach in Clark's original - /// [negation-as-failure paper][1], where negative goals are only - /// permitted if they contain no free (existential) variables. - /// - /// [1]: https://www.doc.ic.ac.uk/~klc/NegAsFailure.pdf - /// - /// Restricting free existential variables is done because the - /// semantics of such queries is not what you expect: it basically - /// treats the existential as a universal. For example, consider: - /// - /// ```rust,ignore - /// struct Vec {} - /// struct i32 {} - /// struct u32 {} - /// trait Foo {} - /// impl Foo for Vec {} - /// ``` - /// - /// If we ask `exists { not { Vec: Foo } }`, what should happen? - /// If we allow negative queries to be definitively answered even when - /// they contain free variables, we will get a definitive *no* to the - /// entire goal! From a logical perspective, that's just wrong: there - /// does exists a `T` such that `not { Vec: Foo }`, namely `i32`. The - /// problem is that the proof search procedure is actually trying to - /// prove something stronger, that there is *no* such `T`. - /// - /// An additional complication arises around free universal - /// variables. Consider a query like `not { !0 = !1 }`, where - /// `!0` and `!1` are placeholders for universally quantified - /// types (i.e., `TyKind::Placeholder`). If we just tried to - /// prove `!0 = !1`, we would get false, because those types - /// cannot be unified -- this would then allow us to conclude that - /// `not { !0 = !1 }`, i.e., `forall { not { X = Y } }`, but - /// this is clearly not true -- what if X were to be equal to Y? - /// - /// Interestingly, the semantics of existential variables turns - /// out to be exactly what we want here. So, in addition to - /// forbidding existential variables in the original query, the - /// `negated` query also converts all universals *into* - /// existentials. Hence `negated` applies to `!0 = !1` would yield - /// `exists { X = Y }` (note that a canonical, i.e. closed, - /// result is returned). Naturally this has a solution, and hence - /// `not { !0 = !1 }` fails, as we expect. - /// - /// (One could imagine converting free existentials into - /// universals, rather than forbidding them altogether. This would - /// be conceivable, but overly strict. For example, the goal - /// `exists { not { ?T: Clone }, ?T = Vec }` would come - /// back as false, when clearly this is true. This is because we - /// would wind up proving that `?T: Clone` can *never* be - /// satisfied (which is false), when we only really care about - /// `?T: Clone` in the case where `?T = Vec`. The current - /// version would delay processing the negative goal (i.e., return - /// `None`) until the second unification has occurred.) - pub fn invert(&mut self, interner: I, value: T) -> Option - where - T: TypeFoldable + HasInterner, - { - let Canonicalized { - free_vars, - quantified, - .. - } = self.canonicalize(interner, value); - - // If the original contains free existential variables, give up. - if !free_vars.is_empty() { - return None; - } - - // If this contains free universal variables, replace them with existentials. - assert!(quantified.binders.is_empty(interner)); - let inverted = quantified - .value - .try_fold_with(&mut Inverter::new(interner, self), DebruijnIndex::INNERMOST) - .unwrap(); - Some(inverted) - } - - /// As `negated_instantiated`, but canonicalizes before - /// returning. Just a convenience function. - pub fn invert_then_canonicalize(&mut self, interner: I, value: T) -> Option> - where - T: TypeFoldable + HasInterner, - { - let snapshot = self.snapshot(); - let result = self.invert(interner, value); - let result = result.map(|r| self.canonicalize(interner, r).quantified); - self.rollback_to(snapshot); - result - } -} - -#[derive(FallibleTypeFolder)] -struct Inverter<'q, I: Interner> { - table: &'q mut InferenceTable, - inverted_ty: FxHashMap>, - inverted_lifetime: FxHashMap>, - interner: I, -} - -impl<'q, I: Interner> Inverter<'q, I> { - fn new(interner: I, table: &'q mut InferenceTable) -> Self { - Inverter { - table, - inverted_ty: FxHashMap::default(), - inverted_lifetime: FxHashMap::default(), - interner, - } - } -} - -impl<'i, I: Interner> TypeFolder for Inverter<'i, I> { - fn as_dyn(&mut self) -> &mut dyn TypeFolder { - self - } - - fn fold_free_placeholder_ty( - &mut self, - universe: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Ty { - let table = &mut self.table; - self.inverted_ty - .entry(universe) - .or_insert_with(|| table.new_variable(universe.ui)) - .to_ty(TypeFolder::interner(self)) - .shifted_in(TypeFolder::interner(self)) - } - - fn fold_free_placeholder_lifetime( - &mut self, - universe: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Lifetime { - let table = &mut self.table; - self.inverted_lifetime - .entry(universe) - .or_insert_with(|| table.new_variable(universe.ui)) - .to_lifetime(TypeFolder::interner(self)) - .shifted_in(TypeFolder::interner(self)) - } - - fn forbid_free_vars(&self) -> bool { - true - } - - fn forbid_inference_vars(&self) -> bool { - true - } - - fn interner(&self) -> I { - self.interner - } -} diff --git a/vendor/chalk-solve/src/infer/test.rs b/vendor/chalk-solve/src/infer/test.rs deleted file mode 100644 index 2ac35f027..000000000 --- a/vendor/chalk-solve/src/infer/test.rs +++ /dev/null @@ -1,422 +0,0 @@ -#![cfg(test)] - -use super::unify::RelationResult; -use super::*; -use chalk_integration::interner::ChalkIr; -use chalk_integration::{arg, lifetime, ty}; - -// We just use a vec of 20 `Invariant`, since this is zipped and no substs are -// longer than this -#[derive(Debug)] -struct TestDatabase; -impl UnificationDatabase for TestDatabase { - fn fn_def_variance(&self, _fn_def_id: FnDefId) -> Variances { - Variances::from_iter(ChalkIr, [Variance::Invariant; 20].iter().copied()) - } - - fn adt_variance(&self, _adt_id: AdtId) -> Variances { - Variances::from_iter(ChalkIr, [Variance::Invariant; 20].iter().copied()) - } -} - -#[test] -fn universe_error() { - // exists(A -> forall(X -> A = X)) ---> error - let interner = ChalkIr; - let mut table: InferenceTable = InferenceTable::new(); - let environment0 = Environment::new(interner); - let a = table.new_variable(U0).to_ty(interner); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &ty!(placeholder 1), - ) - .unwrap_err(); -} - -#[test] -fn cycle_error() { - // exists(A -> A = foo A) ---> error - let interner = ChalkIr; - let mut table: InferenceTable = InferenceTable::new(); - let environment0 = Environment::new(interner); - let a = table.new_variable(U0).to_ty(interner); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &ty!(apply (item 0) (expr a)), - ) - .unwrap_err(); - - // exists(A -> A = for<'a> A) - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &ty!(function 1 (infer 0)), - ) - .unwrap_err(); -} - -#[test] -fn cycle_indirect() { - // exists(A -> A = foo B, A = B) ---> error - let interner = ChalkIr; - let mut table: InferenceTable = InferenceTable::new(); - let environment0 = Environment::new(interner); - let a = table.new_variable(U0).to_ty(interner); - let b = table.new_variable(U0).to_ty(interner); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &ty!(apply (item 0) (expr b)), - ) - .unwrap(); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &b, - ) - .unwrap_err(); -} - -#[test] -fn universe_error_indirect_1() { - // exists(A -> forall(X -> exists(B -> B = X, A = B))) ---> error - let interner = ChalkIr; - let mut table: InferenceTable = InferenceTable::new(); - let environment0 = Environment::new(interner); - let a = table.new_variable(U0).to_ty(interner); - let b = table.new_variable(U1).to_ty(interner); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &b, - &ty!(placeholder 1), - ) - .unwrap(); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &b, - ) - .unwrap_err(); -} - -#[test] -fn universe_error_indirect_2() { - // exists(A -> forall(X -> exists(B -> B = A, B = X))) ---> error - let interner = ChalkIr; - let mut table: InferenceTable = InferenceTable::new(); - let environment0 = Environment::new(interner); - let a = table.new_variable(U0).to_ty(interner); - let b = table.new_variable(U1).to_ty(interner); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &b, - ) - .unwrap(); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &b, - &ty!(placeholder 1), - ) - .unwrap_err(); -} - -#[test] -fn universe_promote() { - // exists(A -> forall(X -> exists(B -> A = foo(B), A = foo(i32)))) ---> OK - let interner = ChalkIr; - let mut table: InferenceTable = InferenceTable::new(); - let environment0 = Environment::new(interner); - let a = table.new_variable(U0).to_ty(interner); - let b = table.new_variable(U1).to_ty(interner); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &ty!(apply (item 0) (expr b)), - ) - .unwrap(); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &ty!(apply (item 0) (apply (item 1))), - ) - .unwrap(); -} - -#[test] -fn universe_promote_bad() { - // exists(A -> forall(X -> exists(B -> A = foo(B), B = X))) ---> error - let interner = ChalkIr; - let mut table: InferenceTable = InferenceTable::new(); - let environment0 = Environment::new(interner); - let a = table.new_variable(U0).to_ty(interner); - let b = table.new_variable(U1).to_ty(interner); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &ty!(apply (item 0) (expr b)), - ) - .unwrap(); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &b, - &ty!(placeholder 1), - ) - .unwrap_err(); -} - -#[test] -fn projection_eq() { - // exists(A -> A = Item0<::foo>) - // ^^^^^^^^^^^^ Can A repeat here? For now, - // we say no, but it's an interesting question. - let interner = ChalkIr; - let mut table: InferenceTable = InferenceTable::new(); - let environment0 = Environment::new(interner); - let a = table.new_variable(U0).to_ty(interner); - - // expect an error ("cycle during unification") - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &a, - &ty!(apply (item 0) (projection (item 1) (expr a))), - ) - .unwrap_err(); -} - -const U0: UniverseIndex = UniverseIndex { counter: 0 }; -const U1: UniverseIndex = UniverseIndex { counter: 1 }; -const U2: UniverseIndex = UniverseIndex { counter: 2 }; - -fn make_table() -> InferenceTable { - let mut table: InferenceTable = InferenceTable::new(); - let _ = table.new_universe(); // U1 - let _ = table.new_universe(); // U2 - table -} - -#[test] -fn quantify_simple() { - let interner = ChalkIr; - let mut table = make_table(); - let _ = table.new_variable(U0); - let _ = table.new_variable(U1); - let _ = table.new_variable(U2); - - assert_eq!( - table - .canonicalize(interner, ty!(apply (item 0) (infer 2) (infer 1) (infer 0))) - .quantified, - Canonical { - value: ty!(apply (item 0) (bound 0) (bound 1) (bound 2)), - binders: CanonicalVarKinds::from_iter( - interner, - vec![ - CanonicalVarKind::new(VariableKind::Ty(TyVariableKind::General), U2), - CanonicalVarKind::new(VariableKind::Ty(TyVariableKind::General), U1), - CanonicalVarKind::new(VariableKind::Ty(TyVariableKind::General), U0), - ] - ), - } - ); -} - -#[test] -fn quantify_bound() { - let interner = ChalkIr; - let mut table = make_table(); - let environment0 = Environment::new(interner); - - let v0 = table.new_variable(U0).to_ty(interner); - let v1 = table.new_variable(U1).to_ty(interner); - let v2a = table.new_variable(U2).to_ty(interner); - let v2b = table.new_variable(U2).to_ty(interner); - - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &v2b, - &ty!(apply (item 1) (expr v1) (expr v0)), - ) - .unwrap(); - - assert_eq!( - table - .canonicalize( - interner, - ty!(apply (item 0) (expr v2b) (expr v2a) (expr v1) (expr v0)) - ) - .quantified, - Canonical { - value: ty!(apply (item 0) (apply (item 1) (bound 0) (bound 1)) (bound 2) (bound 0) (bound 1)), - binders: CanonicalVarKinds::from_iter( - interner, - vec![ - CanonicalVarKind::new(VariableKind::Ty(TyVariableKind::General), U1), - CanonicalVarKind::new(VariableKind::Ty(TyVariableKind::General), U0), - CanonicalVarKind::new(VariableKind::Ty(TyVariableKind::General), U2), - ] - ), - } - ); -} - -#[test] -fn quantify_ty_under_binder() { - let interner = ChalkIr; - let mut table = make_table(); - let v0 = table.new_variable(U0); - let v1 = table.new_variable(U0); - let _r2 = table.new_variable(U0); - - // Unify v0 and v1. - let environment0 = Environment::new(interner); - table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &v0.to_ty(interner), - &v1.to_ty(interner), - ) - .unwrap(); - - // Here: the `function` introduces 3 binders, so in the result, - // `(bound 3)` references the first canonicalized inference - // variable. -- note that `infer 0` and `infer 1` have been - // unified above, as well. - assert_eq!( - table - .canonicalize( - interner, - ty!(function 3 (apply (item 0) (bound 1) (infer 0) (infer 1) (lifetime (infer 2)))) - ) - .quantified, - Canonical { - value: ty!(function 3 (apply (item 0) (bound 1) (bound 1 0) (bound 1 0) (lifetime (bound 1 1)))), - binders: CanonicalVarKinds::from_iter( - interner, - vec![ - CanonicalVarKind::new(VariableKind::Ty(TyVariableKind::General), U0), - CanonicalVarKind::new(VariableKind::Lifetime, U0) - ] - ), - } - ); -} - -#[test] -fn lifetime_constraint_indirect() { - let interner = ChalkIr; - let mut table: InferenceTable = InferenceTable::new(); - let _ = table.new_universe(); // U1 - - let _t_0 = table.new_variable(U0); - let _l_1 = table.new_variable(U1); - - let environment0 = Environment::new(interner); - - // Here, we unify '?1 (the lifetime variable in universe 1) with - // '!1. - let t_a = ty!(apply (item 0) (lifetime (placeholder 1))); - let t_b = ty!(apply (item 0) (lifetime (infer 1))); - let RelationResult { goals } = table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &t_a, - &t_b, - ) - .unwrap(); - assert!(goals.is_empty()); - - // Here, we try to unify `?0` (the type variable in universe 0) - // with something that involves `'?1`. Since `'?1` has been - // unified with `'!1`, and `'!1` is not visible from universe 0, - // we will replace `'!1` with a new variable `'?2` and introduce a - // (likely unsatisfiable) constraint relating them. - let t_c = ty!(infer 0); - let RelationResult { goals } = table - .relate( - interner, - &TestDatabase, - &environment0, - Variance::Invariant, - &t_c, - &t_b, - ) - .unwrap(); - assert_eq!(goals.len(), 2); - assert_eq!( - format!("{:?}", goals[0]), - "InEnvironment { environment: Env([]), goal: \'?2: \'!1_0 }", - ); - assert_eq!( - format!("{:?}", goals[1]), - "InEnvironment { environment: Env([]), goal: \'!1_0: \'?2 }", - ); -} diff --git a/vendor/chalk-solve/src/infer/ucanonicalize.rs b/vendor/chalk-solve/src/infer/ucanonicalize.rs deleted file mode 100644 index b44880e37..000000000 --- a/vendor/chalk-solve/src/infer/ucanonicalize.rs +++ /dev/null @@ -1,336 +0,0 @@ -use crate::debug_span; -use chalk_derive::FallibleTypeFolder; -use chalk_ir::fold::{TypeFoldable, TypeFolder}; -use chalk_ir::interner::{HasInterner, Interner}; -use chalk_ir::visit::{TypeVisitable, TypeVisitor}; -use chalk_ir::*; -use std::ops::ControlFlow; - -use super::InferenceTable; - -impl InferenceTable { - pub fn u_canonicalize(interner: I, value0: &Canonical) -> UCanonicalized - where - T: Clone + HasInterner + TypeFoldable + TypeVisitable, - T: HasInterner, - { - debug_span!("u_canonicalize", "{:#?}", value0); - - // First, find all the universes that appear in `value`. - let mut universes = UniverseMap::new(); - - for universe in value0.binders.iter(interner) { - universes.add(*universe.skip_kind()); - } - - value0.value.visit_with( - &mut UCollector { - universes: &mut universes, - interner, - }, - DebruijnIndex::INNERMOST, - ); - - // Now re-map the universes found in value. We have to do this - // in a second pass because it is only then that we know the - // full set of universes found in the original value. - let value1 = value0 - .value - .clone() - .try_fold_with( - &mut UMapToCanonical { - universes: &universes, - interner, - }, - DebruijnIndex::INNERMOST, - ) - .unwrap(); - let binders = CanonicalVarKinds::from_iter( - interner, - value0 - .binders - .iter(interner) - .map(|pk| pk.map_ref(|&ui| universes.map_universe_to_canonical(ui).unwrap())), - ); - - UCanonicalized { - quantified: UCanonical { - universes: universes.num_canonical_universes(), - canonical: Canonical { - value: value1, - binders, - }, - }, - universes, - } - } -} - -#[derive(Debug)] -pub struct UCanonicalized { - /// The canonicalized result. - pub quantified: UCanonical, - - /// A map between the universes in `quantified` and the original universes - pub universes: UniverseMap, -} - -pub trait UniverseMapExt { - fn add(&mut self, universe: UniverseIndex); - fn map_universe_to_canonical(&self, universe: UniverseIndex) -> Option; - fn map_universe_from_canonical(&self, universe: UniverseIndex) -> UniverseIndex; - fn map_from_canonical(&self, interner: I, canonical_value: &Canonical) -> Canonical - where - T: Clone + TypeFoldable + HasInterner, - T: HasInterner, - I: Interner; -} -impl UniverseMapExt for UniverseMap { - fn add(&mut self, universe: UniverseIndex) { - if let Err(i) = self.universes.binary_search(&universe) { - self.universes.insert(i, universe); - } - } - - /// Given a universe U that appeared in our original value, return - /// the universe to use in the u-canonical value. This is done by - /// looking for the index I of U in `self.universes`. We will - /// return the universe with "counter" I. This effectively - /// "compresses" the range of universes to things from - /// `0..self.universes.len()`. If the universe is not present in the map, - /// we return `None`. - fn map_universe_to_canonical(&self, universe: UniverseIndex) -> Option { - self.universes - .binary_search(&universe) - .ok() - .map(|index| UniverseIndex { counter: index }) - } - - /// Given a "canonical universe" -- one found in the - /// `u_canonicalize` result -- returns the original universe that - /// it corresponded to. - fn map_universe_from_canonical(&self, universe: UniverseIndex) -> UniverseIndex { - if universe.counter < self.universes.len() { - self.universes[universe.counter] - } else { - // If this universe is out of bounds, we assume an - // implicit `forall` binder, effectively, and map to a - // "big enough" universe in the original space. See - // comments on `map_from_canonical` for a detailed - // explanation. - let difference = universe.counter - self.universes.len(); - let max_counter = self.universes.last().unwrap().counter; - let new_counter = max_counter + difference + 1; - UniverseIndex { - counter: new_counter, - } - } - } - - /// Returns a mapped version of `value` where the universes have - /// been translated from canonical universes into the original - /// universes. - /// - /// In some cases, `value` may contain fresh universes that are - /// not described in the original map. This occurs when we return - /// region constraints -- for example, if we were to process a - /// constraint like `for<'a> 'a == 'b`, where `'b` is an inference - /// variable, that would generate a region constraint that `!2 == - /// ?0`. (This constraint is typically not, as it happens, - /// satisfiable, but it may be, depending on the bounds on `!2`.) - /// In effect, there is a "for all" binder around the constraint, - /// but it is not represented explicitly -- only implicitly, by - /// the presence of a U2 variable. - /// - /// If we encounter universes like this, which are "out of bounds" - /// from our original set of universes, we map them to a distinct - /// universe in the original space that is greater than all the - /// other universes in the map. That is, if we encounter a - /// canonical universe `Ux` where our canonical vector is (say) - /// `[U0, U3]`, we would compute the difference `d = x - 2` and - /// then return the universe `3 + d + 1`. - /// - /// The important thing is that we preserve (a) the relative order - /// of universes, since that determines visibility, and (b) that - /// the universe we produce does not correspond to any of the - /// other original universes. - fn map_from_canonical(&self, interner: I, canonical_value: &Canonical) -> Canonical - where - T: Clone + TypeFoldable + HasInterner, - T: HasInterner, - I: Interner, - { - debug_span!("map_from_canonical", ?canonical_value, universes = ?self.universes); - - let binders = canonical_value - .binders - .iter(interner) - .map(|cvk| cvk.map_ref(|&universe| self.map_universe_from_canonical(universe))); - - let value = canonical_value - .value - .clone() - .try_fold_with( - &mut UMapFromCanonical { - interner, - universes: self, - }, - DebruijnIndex::INNERMOST, - ) - .unwrap(); - - Canonical { - binders: CanonicalVarKinds::from_iter(interner, binders), - value, - } - } -} - -/// The `UCollector` is a "no-op" in terms of the value, but along the -/// way it collects all universes that were found into a vector. -struct UCollector<'q, I> { - universes: &'q mut UniverseMap, - interner: I, -} - -impl TypeVisitor for UCollector<'_, I> { - type BreakTy = (); - - fn as_dyn(&mut self) -> &mut dyn TypeVisitor { - self - } - - fn visit_free_placeholder( - &mut self, - universe: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> ControlFlow<()> { - self.universes.add(universe.ui); - ControlFlow::Continue(()) - } - - fn forbid_inference_vars(&self) -> bool { - true - } - - fn interner(&self) -> I { - self.interner - } -} - -#[derive(FallibleTypeFolder)] -struct UMapToCanonical<'q, I: Interner> { - interner: I, - universes: &'q UniverseMap, -} - -impl<'i, I: Interner> TypeFolder for UMapToCanonical<'i, I> { - fn as_dyn(&mut self) -> &mut dyn TypeFolder { - self - } - - fn forbid_inference_vars(&self) -> bool { - true - } - - fn fold_free_placeholder_ty( - &mut self, - universe0: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Ty { - let ui = self - .universes - .map_universe_to_canonical(universe0.ui) - .expect("Expected UCollector to encounter this universe"); - PlaceholderIndex { - ui, - idx: universe0.idx, - } - .to_ty(TypeFolder::interner(self)) - } - - fn fold_free_placeholder_lifetime( - &mut self, - universe0: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Lifetime { - let universe = self - .universes - .map_universe_to_canonical(universe0.ui) - .expect("Expected UCollector to encounter this universe"); - - PlaceholderIndex { - ui: universe, - idx: universe0.idx, - } - .to_lifetime(TypeFolder::interner(self)) - } - - fn fold_free_placeholder_const( - &mut self, - ty: Ty, - universe0: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Const { - let universe = self - .universes - .map_universe_to_canonical(universe0.ui) - .expect("Expected UCollector to encounter this universe"); - - PlaceholderIndex { - ui: universe, - idx: universe0.idx, - } - .to_const(TypeFolder::interner(self), ty) - } - - fn interner(&self) -> I { - self.interner - } -} - -#[derive(FallibleTypeFolder)] -struct UMapFromCanonical<'q, I: Interner> { - interner: I, - universes: &'q UniverseMap, -} - -impl<'i, I: Interner> TypeFolder for UMapFromCanonical<'i, I> { - fn as_dyn(&mut self) -> &mut dyn TypeFolder { - self - } - - fn fold_free_placeholder_ty( - &mut self, - universe0: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Ty { - let ui = self.universes.map_universe_from_canonical(universe0.ui); - PlaceholderIndex { - ui, - idx: universe0.idx, - } - .to_ty(TypeFolder::interner(self)) - } - - fn fold_free_placeholder_lifetime( - &mut self, - universe0: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Lifetime { - let universe = self.universes.map_universe_from_canonical(universe0.ui); - PlaceholderIndex { - ui: universe, - idx: universe0.idx, - } - .to_lifetime(TypeFolder::interner(self)) - } - - fn forbid_inference_vars(&self) -> bool { - true - } - - fn interner(&self) -> I { - self.interner - } -} diff --git a/vendor/chalk-solve/src/infer/unify.rs b/vendor/chalk-solve/src/infer/unify.rs deleted file mode 100644 index 10086e651..000000000 --- a/vendor/chalk-solve/src/infer/unify.rs +++ /dev/null @@ -1,1448 +0,0 @@ -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 InferenceTable { - pub fn relate( - &mut self, - interner: I, - db: &dyn UnificationDatabase, - environment: &Environment, - variance: Variance, - a: &T, - b: &T, - ) -> Fallible> - where - T: ?Sized + Zip, - { - 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, - environment: &'t Environment, - goals: Vec>>, - interner: I, - db: &'t dyn UnificationDatabase, -} - -#[derive(Debug)] -pub struct RelationResult { - pub goals: Vec>>, -} - -impl<'t, I: Interner> Unifier<'t, I> { - fn new( - interner: I, - db: &'t dyn UnificationDatabase, - table: &'t mut InferenceTable, - environment: &'t Environment, - ) -> 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(mut self, variance: Variance, a: &T, b: &T) -> Fallible> - where - T: ?Sized + Zip, - { - 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, b: &Ty) -> 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 { T }` with some other forall type `forall { 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, - ) -> 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, - b: &Binders, - ) -> Fallible<()> - where - T: Clone + TypeFoldable + HasInterner + Zip, - '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 `::Item` or `impl Trait` with some other - /// type `ty`. If the variance is `Invariant`, creates a goal like - /// - /// ```notrust - /// AliasEq(::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, - ty: &Ty, - ) -> 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, - universe_index: UniverseIndex, - variance: Variance, - ) -> Ty { - 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, - universe_index: UniverseIndex, - variance: Variance, - ) -> Lifetime { - 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, universe_index: UniverseIndex) -> Const { - 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, - universe_index: UniverseIndex, - variance: Variance, - ) -> GenericArg { - 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 Option>( - &mut self, - substitution: &Substitution, - universe_index: UniverseIndex, - get_variance: F, - ) -> Substitution { - 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 Variance>( - &mut self, - substitution: &Substitution, - universe_index: UniverseIndex, - get_variance: F, - ) -> Substitution { - 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, - ) -> 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, - b: &Lifetime, - ) -> 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, - 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, - b: &'a Const, - ) -> 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) -> 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, b: Lifetime) { - 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, b: Ty) { - 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 for Unifier<'i, I> { - fn zip_tys(&mut self, variance: Variance, a: &Ty, b: &Ty) -> Fallible<()> { - debug!("zip_tys {:?}, {:?}, {:?}", variance, a, b); - self.relate_ty_ty(variance, a, b) - } - - fn zip_lifetimes( - &mut self, - variance: Variance, - a: &Lifetime, - b: &Lifetime, - ) -> Fallible<()> { - self.relate_lifetime_lifetime(variance, a, b) - } - - fn zip_consts(&mut self, variance: Variance, a: &Const, b: &Const) -> Fallible<()> { - self.relate_const_const(variance, a, b) - } - - fn zip_binders(&mut self, variance: Variance, a: &Binders, b: &Binders) -> Fallible<()> - where - T: Clone + HasInterner + Zip + TypeFoldable, - { - // 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 { - self.db - } -} - -struct OccursCheck<'u, 't, I: Interner> { - unifier: &'u mut Unifier<'t, I>, - var: EnaVariable, - universe_index: UniverseIndex, -} - -impl<'u, 't, I: Interner> OccursCheck<'u, 't, I> { - fn new( - unifier: &'u mut Unifier<'t, I>, - var: EnaVariable, - universe_index: UniverseIndex, - ) -> Self { - OccursCheck { - unifier, - var, - universe_index, - } - } -} - -impl<'i, I: Interner> FallibleTypeFolder for OccursCheck<'_, 'i, I> { - type Error = NoSolution; - - fn as_dyn(&mut self) -> &mut dyn FallibleTypeFolder { - self - } - - fn try_fold_free_placeholder_ty( - &mut self, - universe: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Fallible> { - 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, - universe: PlaceholderIndex, - _outer_binder: DebruijnIndex, - ) -> Fallible> { - 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> { - let interner = self.interner(); - if self.universe_index < ui.ui { - // Scenario is like: - // - // exists 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> { - 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, - var: InferenceVar, - _outer_binder: DebruijnIndex, - ) -> Fallible> { - 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 exists ?C = Foo - // - // 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> { - // 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 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 - } -} diff --git a/vendor/chalk-solve/src/infer/var.rs b/vendor/chalk-solve/src/infer/var.rs deleted file mode 100644 index 3fbf92002..000000000 --- a/vendor/chalk-solve/src/infer/var.rs +++ /dev/null @@ -1,152 +0,0 @@ -use chalk_ir::cast::Cast; -use chalk_ir::interner::Interner; -use chalk_ir::*; -use ena::unify::{UnifyKey, UnifyValue}; -use std::cmp::min; -use std::fmt; -use std::marker::PhantomData; -use std::u32; - -/// Wrapper around `chalk_ir::InferenceVar` for coherence purposes. -/// An inference variable represents an unknown term -- either a type -/// or a lifetime. The variable itself is just an index into the -/// unification table; the unification table maps it to an -/// `InferenceValue`. -/// -/// Inference variables can be in one of two states (represents by the variants -/// of an `InferenceValue`): -/// -/// - Unbound(`ui`). In this case, the value of the variable is not yet known. We carry -/// along a universe index `ui` that tracks the universe in which the variable was -/// created; this determines what names may appear in the variable's value. -/// - In this state, we do **not** track the kind of this variable -/// (i.e., whether it represents a type or a lifetime). There is -/// no need: if it represents a lifetime, for example, then there -/// should only ever be constraints that relate it to other -/// lifetimes, or use it in lifetime position. -/// - Bound. In this case, the value of the variable is known. We -/// carry along the value. We discard the universe index in which -/// the variable was created, since that was only needed to help us -/// reject illegal values. Once the value of a variable is known, it -/// can never change. -/// - The value we actually store for variables is a -/// `ir::GenericArg`, and hence it does carry along the kind of the -/// variable via the enum variant. However, we should always know -/// the kind of the variable from context, and hence we typically -/// "downcast" the resulting variable using -/// e.g. `value.ty().unwrap()`. -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct EnaVariable { - var: InferenceVar, - phantom: PhantomData, -} - -impl From for EnaVariable { - fn from(var: InferenceVar) -> EnaVariable { - EnaVariable { - var, - phantom: PhantomData, - } - } -} - -impl From> for InferenceVar { - fn from(ena_var: EnaVariable) -> InferenceVar { - ena_var.var - } -} - -impl EnaVariable { - /// Convert this inference variable into a type. When using this - /// method, naturally you should know from context that the kind - /// of this inference variable is a type (we can't check it). - pub fn to_ty_with_kind(self, interner: I, kind: TyVariableKind) -> Ty { - self.var.to_ty(interner, kind) - } - - /// Same as `to_ty_with_kind`, but the kind is set to `TyVariableKind::General`. - /// This should be used instead of `to_ty_with_kind` when creating a new - /// inference variable (when the kind is not known). - pub fn to_ty(self, interner: I) -> Ty { - self.var.to_ty(interner, TyVariableKind::General) - } - - /// Convert this inference variable into a lifetime. When using this - /// method, naturally you should know from context that the kind - /// of this inference variable is a lifetime (we can't check it). - pub fn to_lifetime(self, interner: I) -> Lifetime { - self.var.to_lifetime(interner) - } - - /// Convert this inference variable into a const. When using this - /// method, naturally you should know from context that the kind - /// of this inference variable is a const (we can't check it). - pub fn to_const(self, interner: I, ty: Ty) -> Const { - self.var.to_const(interner, ty) - } -} - -impl UnifyKey for EnaVariable { - type Value = InferenceValue; - - fn index(&self) -> u32 { - self.var.index() - } - - fn from_index(u: u32) -> Self { - EnaVariable::from(InferenceVar::from(u)) - } - - fn tag() -> &'static str { - "EnaVariable" - } -} - -/// The value of an inference variable. We start out as `Unbound` with a -/// universe index; when the inference variable is assigned a value, it becomes -/// bound and records that value. See `EnaVariable` for more details. -#[derive(Clone, Debug, PartialEq, Eq)] -pub enum InferenceValue { - Unbound(UniverseIndex), - Bound(GenericArg), -} - -impl InferenceValue { - pub fn from_ty(interner: I, ty: Ty) -> Self { - InferenceValue::Bound(ty.cast(interner)) - } - - pub fn from_lifetime(interner: I, lifetime: Lifetime) -> Self { - InferenceValue::Bound(lifetime.cast(interner)) - } - - pub fn from_const(interner: I, constant: Const) -> Self { - InferenceValue::Bound(constant.cast(interner)) - } -} - -impl UnifyValue for InferenceValue { - type Error = (InferenceValue, InferenceValue); - - fn unify_values( - a: &InferenceValue, - b: &InferenceValue, - ) -> Result, (InferenceValue, InferenceValue)> { - match (a, b) { - (&InferenceValue::Unbound(ui_a), &InferenceValue::Unbound(ui_b)) => { - Ok(InferenceValue::Unbound(min(ui_a, ui_b))) - } - (bound @ &InferenceValue::Bound(_), &InferenceValue::Unbound(_)) - | (&InferenceValue::Unbound(_), bound @ &InferenceValue::Bound(_)) => Ok(bound.clone()), - (&InferenceValue::Bound(_), &InferenceValue::Bound(_)) => { - panic!("we should not be asked to unify two bound things") - } - } - } -} - -impl fmt::Debug for EnaVariable { - fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> { - write!(fmt, "{:?}", self.var) - } -} -- cgit v1.2.3