1 //! This code is kind of an alternate way of doing subtyping,
2 //! supertyping, and type equating, distinct from the `combine.rs`
3 //! code but very similar in its effect and design. Eventually the two
4 //! ought to be merged. This code is intended for use in NLL and chalk.
6 //! Here are the key differences:
8 //! - This code may choose to bypass some checks (e.g., the occurs check)
9 //! in the case where we know that there are no unbound type inference
10 //! variables. This is the case for NLL, because at NLL time types are fully
11 //! inferred up-to regions.
12 //! - This code uses "universes" to handle higher-ranked regions and
13 //! not the leak-check. This is "more correct" than what rustc does
14 //! and we are generally migrating in this direction, but NLL had to
17 //! Also, this code assumes that there are no bound types at all, not even
18 //! free ones. This is ok because:
19 //! - we are not relating anything quantified over some type variable
20 //! - we will have instantiated all the bound type vars already (the one
21 //! thing we relate in chalk are basically domain goals and their
24 use crate::infer::InferCtxt;
25 use crate::infer::{ConstVarValue, ConstVariableValue};
26 use crate::traits::DomainGoal;
27 use rustc::ty::error::TypeError;
28 use rustc::ty::fold::{TypeFoldable, TypeVisitor};
29 use rustc::ty::relate::{self, Relate, RelateResult, TypeRelation};
30 use rustc::ty::subst::GenericArg;
31 use rustc::ty::{self, InferConst, Ty, TyCtxt};
32 use rustc_data_structures::fx::FxHashMap;
36 pub enum NormalizationStrategy {
41 pub struct TypeRelating<'me, 'tcx, D>
43 D: TypeRelatingDelegate<'tcx>,
45 infcx: &'me InferCtxt<'me, 'tcx>,
47 /// Callback to use when we deduce an outlives relationship
50 /// How are we relating `a` and `b`?
52 /// - Covariant means `a <: b`.
53 /// - Contravariant means `b <: a`.
54 /// - Invariant means `a == b.
55 /// - Bivariant means that it doesn't matter.
56 ambient_variance: ty::Variance,
58 /// When we pass through a set of binders (e.g., when looking into
59 /// a `fn` type), we push a new bound region scope onto here. This
60 /// will contain the instantiated region for each region in those
61 /// binders. When we then encounter a `ReLateBound(d, br)`, we can
62 /// use the De Bruijn index `d` to find the right scope, and then
63 /// bound region name `br` to find the specific instantiation from
64 /// within that scope. See `replace_bound_region`.
66 /// This field stores the instantiations for late-bound regions in
68 a_scopes: Vec<BoundRegionScope<'tcx>>,
70 /// Same as `a_scopes`, but for the `b` type.
71 b_scopes: Vec<BoundRegionScope<'tcx>>,
74 pub trait TypeRelatingDelegate<'tcx> {
75 /// Push a constraint `sup: sub` -- this constraint must be
76 /// satisfied for the two types to be related. `sub` and `sup` may
77 /// be regions from the type or new variables created through the
79 fn push_outlives(&mut self, sup: ty::Region<'tcx>, sub: ty::Region<'tcx>);
81 /// Push a domain goal that will need to be proved for the two types to
82 /// be related. Used for lazy normalization.
83 fn push_domain_goal(&mut self, domain_goal: DomainGoal<'tcx>);
85 /// Creates a new universe index. Used when instantiating placeholders.
86 fn create_next_universe(&mut self) -> ty::UniverseIndex;
88 /// Creates a new region variable representing a higher-ranked
89 /// region that is instantiated existentially. This creates an
90 /// inference variable, typically.
92 /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then
93 /// we will invoke this method to instantiate `'a` with an
94 /// inference variable (though `'b` would be instantiated first,
95 /// as a placeholder).
96 fn next_existential_region_var(&mut self, was_placeholder: bool) -> ty::Region<'tcx>;
98 /// Creates a new region variable representing a
99 /// higher-ranked region that is instantiated universally.
100 /// This creates a new region placeholder, typically.
102 /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then
103 /// we will invoke this method to instantiate `'b` with a
104 /// placeholder region.
105 fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx>;
107 /// Creates a new existential region in the given universe. This
108 /// is used when handling subtyping and type variables -- if we
109 /// have that `?X <: Foo<'a>`, for example, we would instantiate
110 /// `?X` with a type like `Foo<'?0>` where `'?0` is a fresh
111 /// existential variable created by this function. We would then
112 /// relate `Foo<'?0>` with `Foo<'a>` (and probably add an outlives
113 /// relation stating that `'?0: 'a`).
114 fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>;
116 /// Define the normalization strategy to use, eager or lazy.
117 fn normalization() -> NormalizationStrategy;
119 /// Enables some optimizations if we do not expect inference variables
120 /// in the RHS of the relation.
121 fn forbid_inference_vars() -> bool;
124 #[derive(Clone, Debug)]
125 struct ScopesAndKind<'tcx> {
126 scopes: Vec<BoundRegionScope<'tcx>>,
127 kind: GenericArg<'tcx>,
130 #[derive(Clone, Debug, Default)]
131 struct BoundRegionScope<'tcx> {
132 map: FxHashMap<ty::BoundRegion, ty::Region<'tcx>>,
135 #[derive(Copy, Clone)]
136 struct UniversallyQuantified(bool);
138 impl<'me, 'tcx, D> TypeRelating<'me, 'tcx, D>
140 D: TypeRelatingDelegate<'tcx>,
143 infcx: &'me InferCtxt<'me, 'tcx>,
145 ambient_variance: ty::Variance,
147 Self { infcx, delegate, ambient_variance, a_scopes: vec![], b_scopes: vec![] }
150 fn ambient_covariance(&self) -> bool {
151 match self.ambient_variance {
152 ty::Variance::Covariant | ty::Variance::Invariant => true,
153 ty::Variance::Contravariant | ty::Variance::Bivariant => false,
157 fn ambient_contravariance(&self) -> bool {
158 match self.ambient_variance {
159 ty::Variance::Contravariant | ty::Variance::Invariant => true,
160 ty::Variance::Covariant | ty::Variance::Bivariant => false,
166 value: &ty::Binder<impl TypeFoldable<'tcx>>,
167 universally_quantified: UniversallyQuantified,
168 ) -> BoundRegionScope<'tcx> {
169 let mut scope = BoundRegionScope::default();
171 // Create a callback that creates (via the delegate) either an
172 // existential or placeholder region as needed.
173 let mut next_region = {
174 let delegate = &mut self.delegate;
175 let mut lazy_universe = None;
176 move |br: ty::BoundRegion| {
177 if universally_quantified.0 {
178 // The first time this closure is called, create a
179 // new universe for the placeholders we will make
181 let universe = lazy_universe.unwrap_or_else(|| {
182 let universe = delegate.create_next_universe();
183 lazy_universe = Some(universe);
187 let placeholder = ty::PlaceholderRegion { universe, name: br };
188 delegate.next_placeholder_region(placeholder)
190 delegate.next_existential_region_var(true)
195 value.skip_binder().visit_with(&mut ScopeInstantiator {
196 next_region: &mut next_region,
197 target_index: ty::INNERMOST,
198 bound_region_scope: &mut scope,
204 /// When we encounter binders during the type traversal, we record
205 /// the value to substitute for each of the things contained in
206 /// that binder. (This will be either a universal placeholder or
207 /// an existential inference variable.) Given the De Bruijn index
208 /// `debruijn` (and name `br`) of some binder we have now
209 /// encountered, this routine finds the value that we instantiated
210 /// the region with; to do so, it indexes backwards into the list
211 /// of ambient scopes `scopes`.
212 fn lookup_bound_region(
213 debruijn: ty::DebruijnIndex,
214 br: &ty::BoundRegion,
215 first_free_index: ty::DebruijnIndex,
216 scopes: &[BoundRegionScope<'tcx>],
217 ) -> ty::Region<'tcx> {
218 // The debruijn index is a "reverse index" into the
219 // scopes listing. So when we have INNERMOST (0), we
220 // want the *last* scope pushed, and so forth.
221 let debruijn_index = debruijn.index() - first_free_index.index();
222 let scope = &scopes[scopes.len() - debruijn_index - 1];
224 // Find this bound region in that scope to map to a
225 // particular region.
229 /// If `r` is a bound region, find the scope in which it is bound
230 /// (from `scopes`) and return the value that we instantiated it
231 /// with. Otherwise just return `r`.
232 fn replace_bound_region(
235 first_free_index: ty::DebruijnIndex,
236 scopes: &[BoundRegionScope<'tcx>],
237 ) -> ty::Region<'tcx> {
238 debug!("replace_bound_regions(scopes={:?})", scopes);
239 if let ty::ReLateBound(debruijn, br) = r {
240 Self::lookup_bound_region(*debruijn, br, first_free_index, scopes)
246 /// Push a new outlives requirement into our output set of
248 fn push_outlives(&mut self, sup: ty::Region<'tcx>, sub: ty::Region<'tcx>) {
249 debug!("push_outlives({:?}: {:?})", sup, sub);
251 self.delegate.push_outlives(sup, sub);
254 /// Relate a projection type and some value type lazily. This will always
255 /// succeed, but we push an additional `ProjectionEq` goal depending
256 /// on the value type:
257 /// - if the value type is any type `T` which is not a projection, we push
258 /// `ProjectionEq(projection = T)`.
259 /// - if the value type is another projection `other_projection`, we create
260 /// a new inference variable `?U` and push the two goals
261 /// `ProjectionEq(projection = ?U)`, `ProjectionEq(other_projection = ?U)`.
262 fn relate_projection_ty(
264 projection_ty: ty::ProjectionTy<'tcx>,
267 use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
268 use crate::traits::WhereClause;
269 use rustc_span::DUMMY_SP;
271 match value_ty.kind {
272 ty::Projection(other_projection_ty) => {
273 let var = self.infcx.next_ty_var(TypeVariableOrigin {
274 kind: TypeVariableOriginKind::MiscVariable,
277 self.relate_projection_ty(projection_ty, var);
278 self.relate_projection_ty(other_projection_ty, var);
283 let projection = ty::ProjectionPredicate { projection_ty, ty: value_ty };
285 .push_domain_goal(DomainGoal::Holds(WhereClause::ProjectionEq(projection)));
291 /// Relate a type inference variable with a value type. This works
292 /// by creating a "generalization" G of the value where all the
293 /// lifetimes are replaced with fresh inference values. This
294 /// genearlization G becomes the value of the inference variable,
295 /// and is then related in turn to the value. So e.g. if you had
296 /// `vid = ?0` and `value = &'a u32`, we might first instantiate
297 /// `?0` to a type like `&'0 u32` where `'0` is a fresh variable,
298 /// and then relate `&'0 u32` with `&'a u32` (resulting in
299 /// relations between `'0` and `'a`).
301 /// The variable `pair` can be either a `(vid, ty)` or `(ty, vid)`
302 /// -- in other words, it is always a (unresolved) inference
303 /// variable `vid` and a type `ty` that are being related, but the
304 /// vid may appear either as the "a" type or the "b" type,
305 /// depending on where it appears in the tuple. The trait
306 /// `VidValuePair` lets us work with the vid/type while preserving
307 /// the "sidedness" when necessary -- the sidedness is relevant in
308 /// particular for the variance and set of in-scope things.
309 fn relate_ty_var<PAIR: VidValuePair<'tcx>>(
312 ) -> RelateResult<'tcx, Ty<'tcx>> {
313 debug!("relate_ty_var({:?})", pair);
315 let vid = pair.vid();
316 let value_ty = pair.value_ty();
318 // FIXME(invariance) -- this logic assumes invariance, but that is wrong.
319 // This only presently applies to chalk integration, as NLL
320 // doesn't permit type variables to appear on both sides (and
321 // doesn't use lazy norm).
322 match value_ty.kind {
323 ty::Infer(ty::TyVar(value_vid)) => {
324 // Two type variables: just equate them.
325 self.infcx.inner.borrow_mut().type_variables.equate(vid, value_vid);
329 ty::Projection(projection_ty) if D::normalization() == NormalizationStrategy::Lazy => {
330 return Ok(self.relate_projection_ty(projection_ty, self.infcx.tcx.mk_ty_var(vid)));
336 let generalized_ty = self.generalize_value(value_ty, vid)?;
337 debug!("relate_ty_var: generalized_ty = {:?}", generalized_ty);
339 if D::forbid_inference_vars() {
340 // In NLL, we don't have type inference variables
341 // floating around, so we can do this rather imprecise
342 // variant of the occurs-check.
343 assert!(!generalized_ty.has_infer_types());
346 self.infcx.inner.borrow_mut().type_variables.instantiate(vid, generalized_ty);
348 // The generalized values we extract from `canonical_var_values` have
349 // been fully instantiated and hence the set of scopes we have
350 // doesn't matter -- just to be sure, put an empty vector
352 let old_a_scopes = ::std::mem::take(pair.vid_scopes(self));
354 // Relate the generalized kind to the original one.
355 let result = pair.relate_generalized_ty(self, generalized_ty);
357 // Restore the old scopes now.
358 *pair.vid_scopes(self) = old_a_scopes;
360 debug!("relate_ty_var: complete, result = {:?}", result);
364 fn generalize_value<T: Relate<'tcx>>(
368 ) -> RelateResult<'tcx, T> {
369 let universe = self.infcx.probe_ty_var(for_vid).unwrap_err();
371 let mut generalizer = TypeGeneralizer {
373 delegate: &mut self.delegate,
374 first_free_index: ty::INNERMOST,
375 ambient_variance: self.ambient_variance,
376 for_vid_sub_root: self.infcx.inner.borrow_mut().type_variables.sub_root_var(for_vid),
380 generalizer.relate(&value, &value)
384 /// When we instantiate a inference variable with a value in
385 /// `relate_ty_var`, we always have the pair of a `TyVid` and a `Ty`,
386 /// but the ordering may vary (depending on whether the inference
387 /// variable was found on the `a` or `b` sides). Therefore, this trait
388 /// allows us to factor out common code, while preserving the order
390 trait VidValuePair<'tcx>: Debug {
391 /// Extract the inference variable (which could be either the
392 /// first or second part of the tuple).
393 fn vid(&self) -> ty::TyVid;
395 /// Extract the value it is being related to (which will be the
396 /// opposite part of the tuple from the vid).
397 fn value_ty(&self) -> Ty<'tcx>;
399 /// Extract the scopes that apply to whichever side of the tuple
400 /// the vid was found on. See the comment where this is called
401 /// for more details on why we want them.
402 fn vid_scopes<D: TypeRelatingDelegate<'tcx>>(
404 relate: &'r mut TypeRelating<'_, 'tcx, D>,
405 ) -> &'r mut Vec<BoundRegionScope<'tcx>>;
407 /// Given a generalized type G that should replace the vid, relate
408 /// G to the value, putting G on whichever side the vid would have
410 fn relate_generalized_ty<D>(
412 relate: &mut TypeRelating<'_, 'tcx, D>,
413 generalized_ty: Ty<'tcx>,
414 ) -> RelateResult<'tcx, Ty<'tcx>>
416 D: TypeRelatingDelegate<'tcx>;
419 impl VidValuePair<'tcx> for (ty::TyVid, Ty<'tcx>) {
420 fn vid(&self) -> ty::TyVid {
424 fn value_ty(&self) -> Ty<'tcx> {
430 relate: &'r mut TypeRelating<'_, 'tcx, D>,
431 ) -> &'r mut Vec<BoundRegionScope<'tcx>>
433 D: TypeRelatingDelegate<'tcx>,
438 fn relate_generalized_ty<D>(
440 relate: &mut TypeRelating<'_, 'tcx, D>,
441 generalized_ty: Ty<'tcx>,
442 ) -> RelateResult<'tcx, Ty<'tcx>>
444 D: TypeRelatingDelegate<'tcx>,
446 relate.relate(&generalized_ty, &self.value_ty())
450 // In this case, the "vid" is the "b" type.
451 impl VidValuePair<'tcx> for (Ty<'tcx>, ty::TyVid) {
452 fn vid(&self) -> ty::TyVid {
456 fn value_ty(&self) -> Ty<'tcx> {
462 relate: &'r mut TypeRelating<'_, 'tcx, D>,
463 ) -> &'r mut Vec<BoundRegionScope<'tcx>>
465 D: TypeRelatingDelegate<'tcx>,
470 fn relate_generalized_ty<D>(
472 relate: &mut TypeRelating<'_, 'tcx, D>,
473 generalized_ty: Ty<'tcx>,
474 ) -> RelateResult<'tcx, Ty<'tcx>>
476 D: TypeRelatingDelegate<'tcx>,
478 relate.relate(&self.value_ty(), &generalized_ty)
482 impl<D> TypeRelation<'tcx> for TypeRelating<'me, 'tcx, D>
484 D: TypeRelatingDelegate<'tcx>,
486 fn tcx(&self) -> TyCtxt<'tcx> {
490 // FIXME(oli-obk): not sure how to get the correct ParamEnv
491 fn param_env(&self) -> ty::ParamEnv<'tcx> {
492 ty::ParamEnv::empty()
495 fn tag(&self) -> &'static str {
499 fn a_is_expected(&self) -> bool {
503 fn relate_with_variance<T: Relate<'tcx>>(
505 variance: ty::Variance,
508 ) -> RelateResult<'tcx, T> {
509 debug!("relate_with_variance(variance={:?}, a={:?}, b={:?})", variance, a, b);
511 let old_ambient_variance = self.ambient_variance;
512 self.ambient_variance = self.ambient_variance.xform(variance);
514 debug!("relate_with_variance: ambient_variance = {:?}", self.ambient_variance);
516 let r = self.relate(a, b)?;
518 self.ambient_variance = old_ambient_variance;
520 debug!("relate_with_variance: r={:?}", r);
525 fn tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
526 let a = self.infcx.shallow_resolve(a);
528 if !D::forbid_inference_vars() {
529 b = self.infcx.shallow_resolve(b);
536 match (&a.kind, &b.kind) {
537 (_, &ty::Infer(ty::TyVar(vid))) => {
538 if D::forbid_inference_vars() {
539 // Forbid inference variables in the RHS.
540 bug!("unexpected inference var {:?}", b)
542 self.relate_ty_var((a, vid))
546 (&ty::Infer(ty::TyVar(vid)), _) => self.relate_ty_var((vid, b)),
548 (&ty::Projection(projection_ty), _)
549 if D::normalization() == NormalizationStrategy::Lazy =>
551 Ok(self.relate_projection_ty(projection_ty, b))
554 (_, &ty::Projection(projection_ty))
555 if D::normalization() == NormalizationStrategy::Lazy =>
557 Ok(self.relate_projection_ty(projection_ty, a))
561 debug!("tys(a={:?}, b={:?}, variance={:?})", a, b, self.ambient_variance);
563 // Will also handle unification of `IntVar` and `FloatVar`.
564 self.infcx.super_combine_tys(self, a, b)
573 ) -> RelateResult<'tcx, ty::Region<'tcx>> {
574 debug!("regions(a={:?}, b={:?}, variance={:?})", a, b, self.ambient_variance);
576 let v_a = self.replace_bound_region(a, ty::INNERMOST, &self.a_scopes);
577 let v_b = self.replace_bound_region(b, ty::INNERMOST, &self.b_scopes);
579 debug!("regions: v_a = {:?}", v_a);
580 debug!("regions: v_b = {:?}", v_b);
582 if self.ambient_covariance() {
583 // Covariance: a <= b. Hence, `b: a`.
584 self.push_outlives(v_b, v_a);
587 if self.ambient_contravariance() {
588 // Contravariant: b <= a. Hence, `a: b`.
589 self.push_outlives(v_a, v_b);
597 a: &'tcx ty::Const<'tcx>,
598 mut b: &'tcx ty::Const<'tcx>,
599 ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> {
600 let a = self.infcx.shallow_resolve(a);
602 if !D::forbid_inference_vars() {
603 b = self.infcx.shallow_resolve(b);
607 ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => {
608 // Forbid inference variables in the RHS.
609 bug!("unexpected inference var {:?}", b)
611 // FIXME(invariance): see the related FIXME above.
612 _ => self.infcx.super_combine_consts(self, a, b),
620 ) -> RelateResult<'tcx, ty::Binder<T>>
627 // for<'a> fn(&'a u32) -> &'a u32 <:
628 // fn(&'b u32) -> &'b u32
634 // fn(&'a u32) -> &'a u32 <:
635 // for<'b> fn(&'b u32) -> &'b u32
638 // We therefore proceed as follows:
640 // - Instantiate binders on `b` universally, yielding a universe U1.
641 // - Instantiate binders on `a` existentially in U1.
643 debug!("binders({:?}: {:?}, ambient_variance={:?})", a, b, self.ambient_variance);
645 if !a.skip_binder().has_escaping_bound_vars() && !b.skip_binder().has_escaping_bound_vars()
647 // Fast path for the common case.
648 self.relate(a.skip_binder(), b.skip_binder())?;
649 return Ok(a.clone());
652 if self.ambient_covariance() {
653 // Covariance, so we want `for<..> A <: for<..> B` --
654 // therefore we compare any instantiation of A (i.e., A
655 // instantiated with existentials) against every
656 // instantiation of B (i.e., B instantiated with
659 let b_scope = self.create_scope(b, UniversallyQuantified(true));
660 let a_scope = self.create_scope(a, UniversallyQuantified(false));
662 debug!("binders: a_scope = {:?} (existential)", a_scope);
663 debug!("binders: b_scope = {:?} (universal)", b_scope);
665 self.b_scopes.push(b_scope);
666 self.a_scopes.push(a_scope);
668 // Reset the ambient variance to covariant. This is needed
669 // to correctly handle cases like
671 // for<'a> fn(&'a u32, &'a u3) == for<'b, 'c> fn(&'b u32, &'c u32)
673 // Somewhat surprisingly, these two types are actually
674 // **equal**, even though the one on the right looks more
675 // polymorphic. The reason is due to subtyping. To see it,
676 // consider that each function can call the other:
678 // - The left function can call the right with `'b` and
679 // `'c` both equal to `'a`
681 // - The right function can call the left with `'a` set to
682 // `{P}`, where P is the point in the CFG where the call
683 // itself occurs. Note that `'b` and `'c` must both
684 // include P. At the point, the call works because of
685 // subtyping (i.e., `&'b u32 <: &{P} u32`).
686 let variance = ::std::mem::replace(&mut self.ambient_variance, ty::Variance::Covariant);
688 self.relate(a.skip_binder(), b.skip_binder())?;
690 self.ambient_variance = variance;
692 self.b_scopes.pop().unwrap();
693 self.a_scopes.pop().unwrap();
696 if self.ambient_contravariance() {
697 // Contravariance, so we want `for<..> A :> for<..> B`
698 // -- therefore we compare every instantiation of A (i.e.,
699 // A instantiated with universals) against any
700 // instantiation of B (i.e., B instantiated with
701 // existentials). Opposite of above.
703 let a_scope = self.create_scope(a, UniversallyQuantified(true));
704 let b_scope = self.create_scope(b, UniversallyQuantified(false));
706 debug!("binders: a_scope = {:?} (universal)", a_scope);
707 debug!("binders: b_scope = {:?} (existential)", b_scope);
709 self.a_scopes.push(a_scope);
710 self.b_scopes.push(b_scope);
712 // Reset ambient variance to contravariance. See the
713 // covariant case above for an explanation.
715 ::std::mem::replace(&mut self.ambient_variance, ty::Variance::Contravariant);
717 self.relate(a.skip_binder(), b.skip_binder())?;
719 self.ambient_variance = variance;
721 self.b_scopes.pop().unwrap();
722 self.a_scopes.pop().unwrap();
729 /// When we encounter a binder like `for<..> fn(..)`, we actually have
730 /// to walk the `fn` value to find all the values bound by the `for`
731 /// (these are not explicitly present in the ty representation right
732 /// now). This visitor handles that: it descends the type, tracking
733 /// binder depth, and finds late-bound regions targeting the
734 /// `for<..`>. For each of those, it creates an entry in
735 /// `bound_region_scope`.
736 struct ScopeInstantiator<'me, 'tcx> {
737 next_region: &'me mut dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
738 // The debruijn index of the scope we are instantiating.
739 target_index: ty::DebruijnIndex,
740 bound_region_scope: &'me mut BoundRegionScope<'tcx>,
743 impl<'me, 'tcx> TypeVisitor<'tcx> for ScopeInstantiator<'me, 'tcx> {
744 fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> bool {
745 self.target_index.shift_in(1);
746 t.super_visit_with(self);
747 self.target_index.shift_out(1);
752 fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
753 let ScopeInstantiator { bound_region_scope, next_region, .. } = self;
756 ty::ReLateBound(debruijn, br) if *debruijn == self.target_index => {
757 bound_region_scope.map.entry(*br).or_insert_with(|| next_region(*br));
767 /// The "type generalize" is used when handling inference variables.
769 /// The basic strategy for handling a constraint like `?A <: B` is to
770 /// apply a "generalization strategy" to the type `B` -- this replaces
771 /// all the lifetimes in the type `B` with fresh inference
772 /// variables. (You can read more about the strategy in this [blog
775 /// As an example, if we had `?A <: &'x u32`, we would generalize `&'x
776 /// u32` to `&'0 u32` where `'0` is a fresh variable. This becomes the
777 /// value of `A`. Finally, we relate `&'0 u32 <: &'x u32`, which
778 /// establishes `'0: 'x` as a constraint.
780 /// As a side-effect of this generalization procedure, we also replace
781 /// all the bound regions that we have traversed with concrete values,
782 /// so that the resulting generalized type is independent from the
785 /// [blog post]: https://is.gd/0hKvIr
786 struct TypeGeneralizer<'me, 'tcx, D>
788 D: TypeRelatingDelegate<'tcx>,
790 infcx: &'me InferCtxt<'me, 'tcx>,
792 delegate: &'me mut D,
794 /// After we generalize this type, we are going to relative it to
795 /// some other type. What will be the variance at this point?
796 ambient_variance: ty::Variance,
798 first_free_index: ty::DebruijnIndex,
800 /// The vid of the type variable that is in the process of being
801 /// instantiated. If we find this within the value we are folding,
802 /// that means we would have created a cyclic value.
803 for_vid_sub_root: ty::TyVid,
805 /// The universe of the type variable that is in the process of being
806 /// instantiated. If we find anything that this universe cannot name,
807 /// we reject the relation.
808 universe: ty::UniverseIndex,
811 impl<D> TypeRelation<'tcx> for TypeGeneralizer<'me, 'tcx, D>
813 D: TypeRelatingDelegate<'tcx>,
815 fn tcx(&self) -> TyCtxt<'tcx> {
819 // FIXME(oli-obk): not sure how to get the correct ParamEnv
820 fn param_env(&self) -> ty::ParamEnv<'tcx> {
821 ty::ParamEnv::empty()
824 fn tag(&self) -> &'static str {
828 fn a_is_expected(&self) -> bool {
832 fn relate_with_variance<T: Relate<'tcx>>(
834 variance: ty::Variance,
837 ) -> RelateResult<'tcx, T> {
839 "TypeGeneralizer::relate_with_variance(variance={:?}, a={:?}, b={:?})",
843 let old_ambient_variance = self.ambient_variance;
844 self.ambient_variance = self.ambient_variance.xform(variance);
847 "TypeGeneralizer::relate_with_variance: ambient_variance = {:?}",
848 self.ambient_variance
851 let r = self.relate(a, b)?;
853 self.ambient_variance = old_ambient_variance;
855 debug!("TypeGeneralizer::relate_with_variance: r={:?}", r);
860 fn tys(&mut self, a: Ty<'tcx>, _: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
861 use crate::infer::type_variable::TypeVariableValue;
863 debug!("TypeGeneralizer::tys(a={:?})", a);
866 ty::Infer(ty::TyVar(_)) | ty::Infer(ty::IntVar(_)) | ty::Infer(ty::FloatVar(_))
867 if D::forbid_inference_vars() =>
869 bug!("unexpected inference variable encountered in NLL generalization: {:?}", a);
872 ty::Infer(ty::TyVar(vid)) => {
873 let variables = &mut self.infcx.inner.borrow_mut().type_variables;
874 let vid = variables.root_var(vid);
875 let sub_vid = variables.sub_root_var(vid);
876 if sub_vid == self.for_vid_sub_root {
877 // If sub-roots are equal, then `for_vid` and
878 // `vid` are related via subtyping.
879 debug!("TypeGeneralizer::tys: occurs check failed");
880 return Err(TypeError::Mismatch);
882 match variables.probe(vid) {
883 TypeVariableValue::Known { value: u } => {
887 TypeVariableValue::Unknown { universe: _universe } => {
888 if self.ambient_variance == ty::Bivariant {
889 // FIXME: we may need a WF predicate (related to #54105).
892 let origin = *variables.var_origin(vid);
894 // Replacing with a new variable in the universe `self.universe`,
895 // it will be unified later with the original type variable in
896 // the universe `_universe`.
897 let new_var_id = variables.new_var(self.universe, false, origin);
899 let u = self.tcx().mk_ty_var(new_var_id);
900 debug!("generalize: replacing original vid={:?} with new={:?}", vid, u);
907 ty::Infer(ty::IntVar(_)) | ty::Infer(ty::FloatVar(_)) => {
908 // No matter what mode we are in,
909 // integer/floating-point types must be equal to be
914 ty::Placeholder(placeholder) => {
915 if self.universe.cannot_name(placeholder.universe) {
917 "TypeGeneralizer::tys: root universe {:?} cannot name\
918 placeholder in universe {:?}",
919 self.universe, placeholder.universe
921 Err(TypeError::Mismatch)
927 _ => relate::super_relate_tys(self, a, a),
935 ) -> RelateResult<'tcx, ty::Region<'tcx>> {
936 debug!("TypeGeneralizer::regions(a={:?})", a);
938 if let ty::ReLateBound(debruijn, _) = a {
939 if *debruijn < self.first_free_index {
944 // For now, we just always create a fresh region variable to
945 // replace all the regions in the source type. In the main
946 // type checker, we special case the case where the ambient
947 // variance is `Invariant` and try to avoid creating a fresh
948 // region variable, but since this comes up so much less in
949 // NLL (only when users use `_` etc) it is much less
952 // As an aside, since these new variables are created in
953 // `self.universe` universe, this also serves to enforce the
954 // universe scoping rules.
956 // FIXME(#54105) -- if the ambient variance is bivariant,
957 // though, we may however need to check well-formedness or
958 // risk a problem like #41677 again.
960 let replacement_region_vid = self.delegate.generalize_existential(self.universe);
962 Ok(replacement_region_vid)
967 a: &'tcx ty::Const<'tcx>,
968 _: &'tcx ty::Const<'tcx>,
969 ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> {
971 ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => {
972 bug!("unexpected inference variable encountered in NLL generalization: {:?}", a);
974 ty::ConstKind::Infer(InferConst::Var(vid)) => {
975 let variable_table = &mut self.infcx.inner.borrow_mut().const_unification_table;
976 let var_value = variable_table.probe_value(vid);
977 match var_value.val.known() {
978 Some(u) => self.relate(&u, &u),
980 let new_var_id = variable_table.new_key(ConstVarValue {
981 origin: var_value.origin,
982 val: ConstVariableValue::Unknown { universe: self.universe },
984 Ok(self.tcx().mk_const_var(new_var_id, a.ty))
988 _ => relate::super_relate_consts(self, a, a),
996 ) -> RelateResult<'tcx, ty::Binder<T>>
1000 debug!("TypeGeneralizer::binders(a={:?})", a);
1002 self.first_free_index.shift_in(1);
1003 let result = self.relate(a.skip_binder(), a.skip_binder())?;
1004 self.first_free_index.shift_out(1);
1005 Ok(ty::Binder::bind(result))