| use std::mem; |
| |
| use rustc_data_structures::sso::SsoHashMap; |
| use rustc_data_structures::stack::ensure_sufficient_stack; |
| use rustc_hir::def_id::DefId; |
| use rustc_middle::bug; |
| use rustc_middle::ty::error::TypeError; |
| use rustc_middle::ty::{ |
| self, AliasRelationDirection, InferConst, Term, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, |
| TypeVisitableExt, TypeVisitor, TypingMode, |
| }; |
| use rustc_span::Span; |
| use tracing::{debug, instrument, warn}; |
| |
| use super::{ |
| PredicateEmittingRelation, Relate, RelateResult, StructurallyRelateAliases, TypeRelation, |
| }; |
| use crate::infer::type_variable::TypeVariableValue; |
| use crate::infer::unify_key::ConstVariableValue; |
| use crate::infer::{InferCtxt, RegionVariableOrigin, relate}; |
| |
| #[derive(Copy, Clone, Eq, PartialEq, Debug)] |
| enum TermVid { |
| Ty(ty::TyVid), |
| Const(ty::ConstVid), |
| } |
| |
| impl From<ty::TyVid> for TermVid { |
| fn from(value: ty::TyVid) -> Self { |
| TermVid::Ty(value) |
| } |
| } |
| |
| impl From<ty::ConstVid> for TermVid { |
| fn from(value: ty::ConstVid) -> Self { |
| TermVid::Const(value) |
| } |
| } |
| |
| impl<'tcx> InferCtxt<'tcx> { |
| /// The idea is that we should ensure that the type variable `target_vid` |
| /// is equal to, a subtype of, or a supertype of `source_ty`. |
| /// |
| /// For this, we will instantiate `target_vid` with a *generalized* version |
| /// of `source_ty`. Generalization introduces other inference variables wherever |
| /// subtyping could occur. This also does the occurs checks, detecting whether |
| /// instantiating `target_vid` would result in a cyclic type. We eagerly error |
| /// in this case. |
| /// |
| /// This is *not* expected to be used anywhere except for an implementation of |
| /// `TypeRelation`. Do not use this, and instead please use `At::eq`, for all |
| /// other usecases (i.e. setting the value of a type var). |
| #[instrument(level = "debug", skip(self, relation))] |
| pub fn instantiate_ty_var<R: PredicateEmittingRelation<InferCtxt<'tcx>>>( |
| &self, |
| relation: &mut R, |
| target_is_expected: bool, |
| target_vid: ty::TyVid, |
| instantiation_variance: ty::Variance, |
| source_ty: Ty<'tcx>, |
| ) -> RelateResult<'tcx, ()> { |
| debug_assert!(self.inner.borrow_mut().type_variables().probe(target_vid).is_unknown()); |
| |
| self.instantiate_var( |
| relation, |
| target_is_expected, |
| target_vid.into(), |
| instantiation_variance, |
| source_ty.into(), |
| ) |
| } |
| |
| /// Instantiates the const variable `target_vid` with the given constant. |
| /// |
| /// This also tests if the given const `ct` contains an inference variable which was previously |
| /// unioned with `target_vid`. If this is the case, inferring `target_vid` to `ct` |
| /// would result in an infinite type as we continuously replace an inference variable |
| /// in `ct` with `ct` itself. |
| /// |
| /// This is especially important as unevaluated consts use their parents generics. |
| /// They therefore often contain unused args, making these errors far more likely. |
| /// |
| /// A good example of this is the following: |
| /// |
| /// ```compile_fail,E0308 |
| /// #![feature(generic_const_exprs)] |
| /// |
| /// fn bind<const N: usize>(value: [u8; N]) -> [u8; 3 + 4] { |
| /// todo!() |
| /// } |
| /// |
| /// fn main() { |
| /// let mut arr = Default::default(); |
| /// arr = bind(arr); |
| /// } |
| /// ``` |
| /// |
| /// Here `3 + 4` ends up as `ConstKind::Unevaluated` which uses the generics |
| /// of `fn bind` (meaning that its args contain `N`). |
| /// |
| /// `bind(arr)` now infers that the type of `arr` must be `[u8; N]`. |
| /// The assignment `arr = bind(arr)` now tries to equate `N` with `3 + 4`. |
| /// |
| /// As `3 + 4` contains `N` in its args, this must not succeed. |
| /// |
| /// See `tests/ui/const-generics/occurs-check/` for more examples where this is relevant. |
| #[instrument(level = "debug", skip(self, relation))] |
| pub(crate) fn instantiate_const_var<R: PredicateEmittingRelation<InferCtxt<'tcx>>>( |
| &self, |
| relation: &mut R, |
| target_is_expected: bool, |
| target_vid: ty::ConstVid, |
| source_ct: ty::Const<'tcx>, |
| ) -> RelateResult<'tcx, ()> { |
| // FIXME(generic_const_exprs): Occurs check failures for unevaluated |
| // constants and generic expressions are not yet handled correctly. |
| debug_assert!( |
| self.inner.borrow_mut().const_unification_table().probe_value(target_vid).is_unknown() |
| ); |
| |
| self.instantiate_var( |
| relation, |
| target_is_expected, |
| target_vid.into(), |
| ty::Invariant, |
| source_ct.into(), |
| ) |
| } |
| |
| #[instrument(level = "debug", skip(self, relation))] |
| fn instantiate_var<R: PredicateEmittingRelation<Self>>( |
| &self, |
| relation: &mut R, |
| target_is_expected: bool, |
| target_vid: TermVid, |
| instantiation_variance: ty::Variance, |
| source_term: Term<'tcx>, |
| ) -> RelateResult<'tcx, ()> { |
| // Generalize `source_term` depending on the current variance. As an example, assume |
| // `?target <: &'x ?1`, where `'x` is some free region and `?1` is an inference |
| // variable. |
| // |
| // Then the `generalized_term` would be `&'?2 ?3`, where `'?2` and `?3` are fresh |
| // region/type inference variables. |
| // |
| // We then relate `generalized_term <: source_term`, adding constraints like `'x: '?2` and |
| // `?1 <: ?3`. |
| let Generalization { value_may_be_infer: generalized_term } = self.generalize( |
| relation.span(), |
| relation.structurally_relate_aliases(), |
| target_vid, |
| instantiation_variance, |
| source_term, |
| )?; |
| |
| // Constrain `b_vid` to the generalized type `generalized_term`. |
| self.union_var_term(target_vid, generalized_term); |
| |
| // Finally, relate `generalized_term` to `source_term`, as described in previous comment. |
| // |
| // FIXME(#16847): This code is non-ideal because all these subtype |
| // relations wind up attributed to the same spans. We need |
| // to associate causes/spans with each of the relations in |
| // the stack to get this right. |
| if generalized_term.is_infer() { |
| // This happens for cases like `<?0 as Trait>::Assoc == ?0`. |
| // We can't instantiate `?0` here as that would result in a |
| // cyclic type. We instead delay the unification in case |
| // the alias can be normalized to something which does not |
| // mention `?0`. |
| if self.next_trait_solver() { |
| let (lhs, rhs, direction) = match instantiation_variance { |
| ty::Invariant => { |
| (generalized_term, source_term, AliasRelationDirection::Equate) |
| } |
| ty::Covariant => { |
| (generalized_term, source_term, AliasRelationDirection::Subtype) |
| } |
| ty::Contravariant => { |
| (source_term, generalized_term, AliasRelationDirection::Subtype) |
| } |
| ty::Bivariant => unreachable!("bivariant generalization"), |
| }; |
| |
| relation.register_predicates([ty::PredicateKind::AliasRelate(lhs, rhs, direction)]); |
| } else { |
| let Some(source_alias) = source_term.to_alias_term() else { |
| bug!("generalized `{source_term:?} to infer, not an alias"); |
| }; |
| match source_alias.kind(self.tcx) { |
| ty::AliasTermKind::ProjectionTy | ty::AliasTermKind::ProjectionConst => { |
| // FIXME: This does not handle subtyping correctly, we could |
| // instead create a new inference variable `?normalized_source`, emitting |
| // `Projection(normalized_source, ?ty_normalized)` and |
| // `?normalized_source <: generalized_term`. |
| relation.register_predicates([ty::ProjectionPredicate { |
| projection_term: source_alias, |
| term: generalized_term, |
| }]); |
| } |
| // The old solver only accepts projection predicates for associated types. |
| ty::AliasTermKind::InherentTy |
| | ty::AliasTermKind::FreeTy |
| | ty::AliasTermKind::OpaqueTy => { |
| return Err(TypeError::CyclicTy(source_term.expect_type())); |
| } |
| ty::AliasTermKind::InherentConst |
| | ty::AliasTermKind::FreeConst |
| | ty::AliasTermKind::UnevaluatedConst => { |
| return Err(TypeError::CyclicConst(source_term.expect_const())); |
| } |
| } |
| } |
| } else { |
| // NOTE: The `instantiation_variance` is not the same variance as |
| // used by the relation. When instantiating `b`, `target_is_expected` |
| // is flipped and the `instantiation_variance` is also flipped. To |
| // constrain the `generalized_term` while using the original relation, |
| // we therefore only have to flip the arguments. |
| // |
| // ```ignore (not code) |
| // ?a rel B |
| // instantiate_ty_var(?a, B) # expected and variance not flipped |
| // B' rel B |
| // ``` |
| // or |
| // ```ignore (not code) |
| // A rel ?b |
| // instantiate_ty_var(?b, A) # expected and variance flipped |
| // A rel A' |
| // ``` |
| match generalized_term.kind() { |
| ty::TermKind::Ty(_) => { |
| if target_is_expected { |
| relation.relate(generalized_term, source_term)?; |
| } else { |
| debug!("flip relation"); |
| relation.relate(source_term, generalized_term)?; |
| } |
| } |
| ty::TermKind::Const(_) => { |
| // Override consts to always be invariant |
| if target_is_expected { |
| relation.relate_with_variance( |
| ty::Invariant, |
| ty::VarianceDiagInfo::default(), |
| generalized_term, |
| source_term, |
| )?; |
| } else { |
| relation.relate_with_variance( |
| ty::Invariant, |
| ty::VarianceDiagInfo::default(), |
| source_term, |
| generalized_term, |
| )?; |
| } |
| } |
| } |
| } |
| |
| Ok(()) |
| } |
| |
| /// This is a thin wrapper around inserting into the var tables. You probably want |
| /// [`Self::instantiate_var`] instead, which calls this method. |
| fn union_var_term(&self, l: TermVid, r: ty::Term<'tcx>) { |
| match (l, r.kind()) { |
| (TermVid::Ty(l), ty::TermKind::Ty(r)) => { |
| if let Some(r) = r.ty_vid() { |
| self.inner.borrow_mut().type_variables().equate(l, r) |
| } else { |
| self.inner.borrow_mut().type_variables().instantiate(l, r) |
| } |
| } |
| (TermVid::Const(l), ty::TermKind::Const(r)) => { |
| if let Some(r) = r.ct_vid() { |
| self.inner.borrow_mut().const_unification_table().union(l, r) |
| } else { |
| self.inner |
| .borrow_mut() |
| .const_unification_table() |
| .union_value(l, ConstVariableValue::Known { value: r }) |
| } |
| } |
| _ => bug!("mismatched term kinds in generalize: {l:?}, {r:?}"), |
| } |
| } |
| |
| /// Attempts to generalize `source_term` for the type variable `target_vid`. |
| /// This checks for cycles -- that is, whether `source_term` references `target_vid`. |
| fn generalize( |
| &self, |
| span: Span, |
| structurally_relate_aliases: StructurallyRelateAliases, |
| target_vid: TermVid, |
| ambient_variance: ty::Variance, |
| source_term: Term<'tcx>, |
| ) -> RelateResult<'tcx, Generalization<Term<'tcx>>> { |
| assert!(!source_term.has_escaping_bound_vars()); |
| let (for_universe, root_vid) = match target_vid { |
| TermVid::Ty(ty_vid) => { |
| (self.try_resolve_ty_var(ty_vid).unwrap_err(), TermVid::Ty(self.root_var(ty_vid))) |
| } |
| TermVid::Const(ct_vid) => ( |
| self.try_resolve_const_var(ct_vid).unwrap_err(), |
| TermVid::Const(self.inner.borrow_mut().const_unification_table().find(ct_vid).vid), |
| ), |
| }; |
| |
| let mut generalizer = Generalizer { |
| infcx: self, |
| span, |
| structurally_relate_aliases, |
| root_vid, |
| for_universe, |
| root_term: source_term, |
| ambient_variance, |
| in_alias: false, |
| cache: Default::default(), |
| }; |
| |
| let value_may_be_infer = generalizer.relate(source_term, source_term)?; |
| Ok(Generalization { value_may_be_infer }) |
| } |
| } |
| |
| /// Finds the max universe present |
| struct MaxUniverse { |
| max_universe: ty::UniverseIndex, |
| } |
| |
| impl MaxUniverse { |
| fn new() -> Self { |
| MaxUniverse { max_universe: ty::UniverseIndex::ROOT } |
| } |
| |
| fn max_universe(self) -> ty::UniverseIndex { |
| self.max_universe |
| } |
| } |
| |
| impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxUniverse { |
| fn visit_ty(&mut self, t: Ty<'tcx>) { |
| if let ty::Placeholder(placeholder) = t.kind() { |
| self.max_universe = self.max_universe.max(placeholder.universe); |
| } |
| |
| t.super_visit_with(self) |
| } |
| |
| fn visit_const(&mut self, c: ty::Const<'tcx>) { |
| if let ty::ConstKind::Placeholder(placeholder) = c.kind() { |
| self.max_universe = self.max_universe.max(placeholder.universe); |
| } |
| |
| c.super_visit_with(self) |
| } |
| |
| fn visit_region(&mut self, r: ty::Region<'tcx>) { |
| if let ty::RePlaceholder(placeholder) = r.kind() { |
| self.max_universe = self.max_universe.max(placeholder.universe); |
| } |
| } |
| } |
| |
| /// The "generalizer" is used when handling inference variables. |
| /// |
| /// The basic strategy for handling a constraint like `?A <: B` is to |
| /// apply a "generalization strategy" to the term `B` -- this replaces |
| /// all the lifetimes in the term `B` with fresh inference variables. |
| /// (You can read more about the strategy in this [blog post].) |
| /// |
| /// As an example, if we had `?A <: &'x u32`, we would generalize `&'x |
| /// u32` to `&'0 u32` where `'0` is a fresh variable. This becomes the |
| /// value of `A`. Finally, we relate `&'0 u32 <: &'x u32`, which |
| /// establishes `'0: 'x` as a constraint. |
| /// |
| /// [blog post]: https://is.gd/0hKvIr |
| struct Generalizer<'me, 'tcx> { |
| infcx: &'me InferCtxt<'tcx>, |
| |
| span: Span, |
| |
| /// Whether aliases should be related structurally. If not, we have to |
| /// be careful when generalizing aliases. |
| structurally_relate_aliases: StructurallyRelateAliases, |
| |
| /// The vid of the type variable that is in the process of being |
| /// instantiated. If we find this within the value we are folding, |
| /// that means we would have created a cyclic value. |
| root_vid: TermVid, |
| |
| /// The universe of the type variable that is in the process of being |
| /// instantiated. If we find anything that this universe cannot name, |
| /// we reject the relation. |
| for_universe: ty::UniverseIndex, |
| |
| /// The root term (const or type) we're generalizing. Used for cycle errors. |
| root_term: Term<'tcx>, |
| |
| /// After we generalize this type, we are going to relate it to |
| /// some other type. What will be the variance at this point? |
| ambient_variance: ty::Variance, |
| |
| /// This is set once we're generalizing the arguments of an alias. |
| /// |
| /// This is necessary to correctly handle |
| /// `<T as Bar<<?0 as Foo>::Assoc>::Assoc == ?0`. This equality can |
| /// hold by either normalizing the outer or the inner associated type. |
| in_alias: bool, |
| |
| cache: SsoHashMap<(Ty<'tcx>, ty::Variance, bool), Ty<'tcx>>, |
| } |
| |
| impl<'tcx> Generalizer<'_, 'tcx> { |
| /// Create an error that corresponds to the term kind in `root_term` |
| fn cyclic_term_error(&self) -> TypeError<'tcx> { |
| match self.root_term.kind() { |
| ty::TermKind::Ty(ty) => TypeError::CyclicTy(ty), |
| ty::TermKind::Const(ct) => TypeError::CyclicConst(ct), |
| } |
| } |
| |
| /// Create a new type variable in the universe of the target when |
| /// generalizing an alias. |
| fn next_var_for_alias_of_kind(&self, alias: ty::AliasTerm<'tcx>) -> ty::Term<'tcx> { |
| if alias.kind(self.cx()).is_type() { |
| self.infcx.next_ty_var_in_universe(self.span, self.for_universe).into() |
| } else { |
| self.infcx.next_const_var_in_universe(self.span, self.for_universe).into() |
| } |
| } |
| |
| /// An occurs check failure inside of an alias does not mean |
| /// that the types definitely don't unify. We may be able |
| /// to normalize the alias after all. |
| /// |
| /// We handle this by lazily equating the alias and generalizing |
| /// it to an inference variable. In the new solver, we always |
| /// generalize to an infer var unless the alias contains escaping |
| /// bound variables. |
| /// |
| /// Correctly handling aliases with escaping bound variables is |
| /// difficult and currently incomplete in two opposite ways: |
| /// - if we get an occurs check failure in the alias, replace it with a new infer var. |
| /// This causes us to later emit an alias-relate goal and is incomplete in case the |
| /// alias normalizes to type containing one of the bound variables. |
| /// - if the alias contains an inference variable not nameable by `for_universe`, we |
| /// continue generalizing the alias. This ends up pulling down the universe of the |
| /// inference variable and is incomplete in case the alias would normalize to a type |
| /// which does not mention that inference variable. |
| fn generalize_alias_term( |
| &mut self, |
| alias: ty::AliasTerm<'tcx>, |
| ) -> Result<Term<'tcx>, TypeError<'tcx>> { |
| // We do not eagerly replace aliases with inference variables if they have |
| // escaping bound vars, see the method comment for details. However, when we |
| // are inside of an alias with escaping bound vars replacing nested aliases |
| // with inference variables can cause incorrect ambiguity. |
| // |
| // cc trait-system-refactor-initiative#110 |
| if self.infcx.next_trait_solver() && !alias.has_escaping_bound_vars() && !self.in_alias { |
| return Ok(self.next_var_for_alias_of_kind(alias)); |
| } |
| |
| let is_nested_alias = mem::replace(&mut self.in_alias, true); |
| let result = match self.relate(alias, alias) { |
| Ok(alias) => Ok(alias.to_term(self.cx())), |
| Err(e) => { |
| if is_nested_alias { |
| return Err(e); |
| } else { |
| let mut visitor = MaxUniverse::new(); |
| alias.visit_with(&mut visitor); |
| let infer_replacement_is_complete = |
| self.for_universe.can_name(visitor.max_universe()) |
| && !alias.has_escaping_bound_vars(); |
| if !infer_replacement_is_complete { |
| warn!("may incompletely handle alias type: {alias:?}"); |
| } |
| |
| debug!("generalization failure in alias"); |
| Ok(self.next_var_for_alias_of_kind(alias)) |
| } |
| } |
| }; |
| self.in_alias = is_nested_alias; |
| result |
| } |
| } |
| |
| impl<'tcx> TypeRelation<TyCtxt<'tcx>> for Generalizer<'_, 'tcx> { |
| fn cx(&self) -> TyCtxt<'tcx> { |
| self.infcx.tcx |
| } |
| |
| fn relate_ty_args( |
| &mut self, |
| a_ty: Ty<'tcx>, |
| _: Ty<'tcx>, |
| def_id: DefId, |
| a_args: ty::GenericArgsRef<'tcx>, |
| b_args: ty::GenericArgsRef<'tcx>, |
| mk: impl FnOnce(ty::GenericArgsRef<'tcx>) -> Ty<'tcx>, |
| ) -> RelateResult<'tcx, Ty<'tcx>> { |
| let args = if self.ambient_variance == ty::Invariant { |
| // Avoid fetching the variance if we are in an invariant |
| // context; no need, and it can induce dependency cycles |
| // (e.g., #41849). |
| relate::relate_args_invariantly(self, a_args, b_args) |
| } else { |
| let tcx = self.cx(); |
| let variances = tcx.variances_of(def_id); |
| relate::relate_args_with_variances(self, variances, a_args, b_args) |
| }?; |
| if args == a_args { Ok(a_ty) } else { Ok(mk(args)) } |
| } |
| |
| #[instrument(level = "debug", skip(self, variance, b), ret)] |
| fn relate_with_variance<T: Relate<TyCtxt<'tcx>>>( |
| &mut self, |
| variance: ty::Variance, |
| _info: ty::VarianceDiagInfo<TyCtxt<'tcx>>, |
| a: T, |
| b: T, |
| ) -> RelateResult<'tcx, T> { |
| let old_ambient_variance = self.ambient_variance; |
| self.ambient_variance = self.ambient_variance.xform(variance); |
| debug!(?self.ambient_variance, "new ambient variance"); |
| // Recursive calls to `relate` can overflow the stack. For example a deeper version of |
| // `ui/associated-consts/issue-93775.rs`. |
| let r = ensure_sufficient_stack(|| self.relate(a, b)); |
| self.ambient_variance = old_ambient_variance; |
| r |
| } |
| |
| #[instrument(level = "debug", skip(self, t2), ret)] |
| fn tys(&mut self, t: Ty<'tcx>, t2: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { |
| assert_eq!(t, t2); // we are misusing TypeRelation here; both LHS and RHS ought to be == |
| |
| if let Some(&result) = self.cache.get(&(t, self.ambient_variance, self.in_alias)) { |
| return Ok(result); |
| } |
| |
| // Check to see whether the type we are generalizing references |
| // any other type variable related to `vid` via |
| // subtyping. This is basically our "occurs check", preventing |
| // us from creating infinitely sized types. |
| let g = match *t.kind() { |
| ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { |
| bug!("unexpected infer type: {t}") |
| } |
| |
| ty::Infer(ty::TyVar(vid)) => { |
| let mut inner = self.infcx.inner.borrow_mut(); |
| let vid = inner.type_variables().root_var(vid); |
| if TermVid::Ty(vid) == self.root_vid { |
| // If sub-roots are equal, then `root_vid` and |
| // `vid` are related via subtyping. |
| Err(self.cyclic_term_error()) |
| } else { |
| let probe = inner.type_variables().probe(vid); |
| match probe { |
| TypeVariableValue::Known { value: u } => { |
| drop(inner); |
| self.relate(u, u) |
| } |
| TypeVariableValue::Unknown { universe } => { |
| match self.ambient_variance { |
| // Invariant: no need to make a fresh type variable |
| // if we can name the universe. |
| ty::Invariant => { |
| if self.for_universe.can_name(universe) { |
| return Ok(t); |
| } |
| } |
| |
| // We do need a fresh type variable otherwise. |
| ty::Bivariant | ty::Covariant | ty::Contravariant => (), |
| } |
| |
| let origin = inner.type_variables().var_origin(vid); |
| let new_var_id = |
| inner.type_variables().new_var(self.for_universe, origin); |
| // Record that `vid` and `new_var_id` have to be subtypes |
| // of each other. This is currently only used for diagnostics. |
| // To see why, see the docs in the `type_variables` module. |
| inner.type_variables().sub_unify(vid, new_var_id); |
| // If we're in the new solver and create a new inference |
| // variable inside of an alias we eagerly constrain that |
| // inference variable to prevent unexpected ambiguity errors. |
| // |
| // This is incomplete as it pulls down the universe of the |
| // original inference variable, even though the alias could |
| // normalize to a type which does not refer to that type at |
| // all. I don't expect this to cause unexpected errors in |
| // practice. |
| // |
| // We only need to do so for type and const variables, as |
| // region variables do not impact normalization, and will get |
| // correctly constrained by `AliasRelate` later on. |
| // |
| // cc trait-system-refactor-initiative#108 |
| if self.infcx.next_trait_solver() |
| && !matches!(self.infcx.typing_mode(), TypingMode::Coherence) |
| && self.in_alias |
| { |
| inner.type_variables().equate(vid, new_var_id); |
| } |
| |
| debug!("replacing original vid={:?} with new={:?}", vid, new_var_id); |
| Ok(Ty::new_var(self.cx(), new_var_id)) |
| } |
| } |
| } |
| } |
| |
| ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => { |
| // No matter what mode we are in, |
| // integer/floating-point types must be equal to be |
| // relatable. |
| Ok(t) |
| } |
| |
| ty::Placeholder(placeholder) => { |
| if self.for_universe.can_name(placeholder.universe) { |
| Ok(t) |
| } else { |
| debug!( |
| "root universe {:?} cannot name placeholder in universe {:?}", |
| self.for_universe, placeholder.universe |
| ); |
| Err(TypeError::Mismatch) |
| } |
| } |
| |
| ty::Alias(data) => match self.structurally_relate_aliases { |
| StructurallyRelateAliases::No => { |
| self.generalize_alias_term(data.into()).map(|v| v.expect_type()) |
| } |
| StructurallyRelateAliases::Yes => relate::structurally_relate_tys(self, t, t), |
| }, |
| |
| _ => relate::structurally_relate_tys(self, t, t), |
| }?; |
| |
| self.cache.insert((t, self.ambient_variance, self.in_alias), g); |
| Ok(g) |
| } |
| |
| #[instrument(level = "debug", skip(self, r2), ret)] |
| fn regions( |
| &mut self, |
| r: ty::Region<'tcx>, |
| r2: ty::Region<'tcx>, |
| ) -> RelateResult<'tcx, ty::Region<'tcx>> { |
| assert_eq!(r, r2); // we are misusing TypeRelation here; both LHS and RHS ought to be == |
| |
| match r.kind() { |
| // Never make variables for regions bound within the type itself, |
| // nor for erased regions. |
| ty::ReBound(..) | ty::ReErased => { |
| return Ok(r); |
| } |
| |
| // It doesn't really matter for correctness if we generalize ReError, |
| // since we're already on a doomed compilation path. |
| ty::ReError(_) => { |
| return Ok(r); |
| } |
| |
| ty::RePlaceholder(..) |
| | ty::ReVar(..) |
| | ty::ReStatic |
| | ty::ReEarlyParam(..) |
| | ty::ReLateParam(..) => { |
| // see common code below |
| } |
| } |
| |
| // If we are in an invariant context, we can re-use the region |
| // as is, unless it happens to be in some universe that we |
| // can't name. |
| if let ty::Invariant = self.ambient_variance { |
| let r_universe = self.infcx.universe_of_region(r); |
| if self.for_universe.can_name(r_universe) { |
| return Ok(r); |
| } |
| } |
| |
| Ok(self |
| .infcx |
| .next_region_var_in_universe(RegionVariableOrigin::Misc(self.span), self.for_universe)) |
| } |
| |
| #[instrument(level = "debug", skip(self, c2), ret)] |
| fn consts( |
| &mut self, |
| c: ty::Const<'tcx>, |
| c2: ty::Const<'tcx>, |
| ) -> RelateResult<'tcx, ty::Const<'tcx>> { |
| assert_eq!(c, c2); // we are misusing TypeRelation here; both LHS and RHS ought to be == |
| |
| match c.kind() { |
| ty::ConstKind::Infer(InferConst::Var(vid)) => { |
| // If root const vids are equal, then `root_vid` and |
| // `vid` are related and we'd be inferring an infinitely |
| // deep const. |
| if TermVid::Const( |
| self.infcx.inner.borrow_mut().const_unification_table().find(vid).vid, |
| ) == self.root_vid |
| { |
| return Err(self.cyclic_term_error()); |
| } |
| |
| let mut inner = self.infcx.inner.borrow_mut(); |
| let variable_table = &mut inner.const_unification_table(); |
| match variable_table.probe_value(vid) { |
| ConstVariableValue::Known { value: u } => { |
| drop(inner); |
| self.relate(u, u) |
| } |
| ConstVariableValue::Unknown { origin, universe } => { |
| if self.for_universe.can_name(universe) { |
| Ok(c) |
| } else { |
| let new_var_id = variable_table |
| .new_key(ConstVariableValue::Unknown { |
| origin, |
| universe: self.for_universe, |
| }) |
| .vid; |
| |
| // See the comment for type inference variables |
| // for more details. |
| if self.infcx.next_trait_solver() |
| && !matches!(self.infcx.typing_mode(), TypingMode::Coherence) |
| && self.in_alias |
| { |
| variable_table.union(vid, new_var_id); |
| } |
| Ok(ty::Const::new_var(self.cx(), new_var_id)) |
| } |
| } |
| } |
| } |
| // FIXME: Unevaluated constants are also not rigid, so the current |
| // approach of always relating them structurally is incomplete. |
| // |
| // FIXME: replace the StructurallyRelateAliases::Yes branch with |
| // `structurally_relate_consts` once it is fully structural. |
| ty::ConstKind::Unevaluated(uv) => match self.structurally_relate_aliases { |
| // Hack: Fall back to old behavior if GCE is enabled (it used to just be the Yes |
| // path), as doing this new No path breaks some GCE things. I expect GCE to be |
| // ripped out soon so this shouldn't matter soon. |
| StructurallyRelateAliases::No if !self.cx().features().generic_const_exprs() => { |
| self.generalize_alias_term(uv.into()).map(|v| v.expect_const()) |
| } |
| _ => { |
| let ty::UnevaluatedConst { def, args } = uv; |
| let args = self.relate_with_variance( |
| ty::Invariant, |
| ty::VarianceDiagInfo::default(), |
| args, |
| args, |
| )?; |
| Ok(ty::Const::new_unevaluated(self.cx(), ty::UnevaluatedConst { def, args })) |
| } |
| }, |
| ty::ConstKind::Placeholder(placeholder) => { |
| if self.for_universe.can_name(placeholder.universe) { |
| Ok(c) |
| } else { |
| debug!( |
| "root universe {:?} cannot name placeholder in universe {:?}", |
| self.for_universe, placeholder.universe |
| ); |
| Err(TypeError::Mismatch) |
| } |
| } |
| _ => relate::structurally_relate_consts(self, c, c), |
| } |
| } |
| |
| #[instrument(level = "debug", skip(self), ret)] |
| fn binders<T>( |
| &mut self, |
| a: ty::Binder<'tcx, T>, |
| _: ty::Binder<'tcx, T>, |
| ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> |
| where |
| T: Relate<TyCtxt<'tcx>>, |
| { |
| let result = self.relate(a.skip_binder(), a.skip_binder())?; |
| Ok(a.rebind(result)) |
| } |
| } |
| |
| /// Result from a generalization operation. This includes |
| /// not only the generalized type, but also a bool flag |
| /// indicating whether further WF checks are needed. |
| #[derive(Debug)] |
| struct Generalization<T> { |
| /// When generalizing `<?0 as Trait>::Assoc` or |
| /// `<T as Bar<<?0 as Foo>::Assoc>>::Assoc` |
| /// for `?0` generalization returns an inference |
| /// variable. |
| /// |
| /// This has to be handled with care as it can |
| /// otherwise very easily result in infinite |
| /// recursion. |
| pub value_may_be_infer: T, |
| } |
