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 crate::ty
::error
::TypeError
;
28 use crate::ty
::fold
::{TypeFoldable, TypeVisitor}
;
29 use crate::ty
::relate
::{self, Relate, RelateResult, TypeRelation}
;
30 use crate::ty
::subst
::GenericArg
;
31 use crate::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
.type_variables
.borrow_mut().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
.type_variables
.borrow_mut().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
.type_variables
.borrow_mut().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
);
532 match (&a
.kind
, &b
.kind
) {
533 (_
, &ty
::Infer(ty
::TyVar(vid
))) => {
534 if D
::forbid_inference_vars() {
535 // Forbid inference variables in the RHS.
536 bug
!("unexpected inference var {:?}", b
)
538 self.relate_ty_var((a
, vid
))
542 (&ty
::Infer(ty
::TyVar(vid
)), _
) => self.relate_ty_var((vid
, b
)),
544 (&ty
::Projection(projection_ty
), _
)
545 if D
::normalization() == NormalizationStrategy
::Lazy
=>
547 Ok(self.relate_projection_ty(projection_ty
, b
))
550 (_
, &ty
::Projection(projection_ty
))
551 if D
::normalization() == NormalizationStrategy
::Lazy
=>
553 Ok(self.relate_projection_ty(projection_ty
, a
))
557 debug
!("tys(a={:?}, b={:?}, variance={:?})", a
, b
, self.ambient_variance
);
559 // Will also handle unification of `IntVar` and `FloatVar`.
560 self.infcx
.super_combine_tys(self, a
, b
)
569 ) -> RelateResult
<'tcx
, ty
::Region
<'tcx
>> {
570 debug
!("regions(a={:?}, b={:?}, variance={:?})", a
, b
, self.ambient_variance
);
572 let v_a
= self.replace_bound_region(a
, ty
::INNERMOST
, &self.a_scopes
);
573 let v_b
= self.replace_bound_region(b
, ty
::INNERMOST
, &self.b_scopes
);
575 debug
!("regions: v_a = {:?}", v_a
);
576 debug
!("regions: v_b = {:?}", v_b
);
578 if self.ambient_covariance() {
579 // Covariance: a <= b. Hence, `b: a`.
580 self.push_outlives(v_b
, v_a
);
583 if self.ambient_contravariance() {
584 // Contravariant: b <= a. Hence, `a: b`.
585 self.push_outlives(v_a
, v_b
);
593 a
: &'tcx ty
::Const
<'tcx
>,
594 mut b
: &'tcx ty
::Const
<'tcx
>,
595 ) -> RelateResult
<'tcx
, &'tcx ty
::Const
<'tcx
>> {
596 let a
= self.infcx
.shallow_resolve(a
);
598 if !D
::forbid_inference_vars() {
599 b
= self.infcx
.shallow_resolve(b
);
603 ty
::ConstKind
::Infer(InferConst
::Var(_
)) if D
::forbid_inference_vars() => {
604 // Forbid inference variables in the RHS.
605 bug
!("unexpected inference var {:?}", b
)
607 // FIXME(invariance): see the related FIXME above.
608 _
=> self.infcx
.super_combine_consts(self, a
, b
),
616 ) -> RelateResult
<'tcx
, ty
::Binder
<T
>>
623 // for<'a> fn(&'a u32) -> &'a u32 <:
624 // fn(&'b u32) -> &'b u32
630 // fn(&'a u32) -> &'a u32 <:
631 // for<'b> fn(&'b u32) -> &'b u32
634 // We therefore proceed as follows:
636 // - Instantiate binders on `b` universally, yielding a universe U1.
637 // - Instantiate binders on `a` existentially in U1.
639 debug
!("binders({:?}: {:?}, ambient_variance={:?})", a
, b
, self.ambient_variance
);
641 if self.ambient_covariance() {
642 // Covariance, so we want `for<..> A <: for<..> B` --
643 // therefore we compare any instantiation of A (i.e., A
644 // instantiated with existentials) against every
645 // instantiation of B (i.e., B instantiated with
648 let b_scope
= self.create_scope(b
, UniversallyQuantified(true));
649 let a_scope
= self.create_scope(a
, UniversallyQuantified(false));
651 debug
!("binders: a_scope = {:?} (existential)", a_scope
);
652 debug
!("binders: b_scope = {:?} (universal)", b_scope
);
654 self.b_scopes
.push(b_scope
);
655 self.a_scopes
.push(a_scope
);
657 // Reset the ambient variance to covariant. This is needed
658 // to correctly handle cases like
660 // for<'a> fn(&'a u32, &'a u3) == for<'b, 'c> fn(&'b u32, &'c u32)
662 // Somewhat surprisingly, these two types are actually
663 // **equal**, even though the one on the right looks more
664 // polymorphic. The reason is due to subtyping. To see it,
665 // consider that each function can call the other:
667 // - The left function can call the right with `'b` and
668 // `'c` both equal to `'a`
670 // - The right function can call the left with `'a` set to
671 // `{P}`, where P is the point in the CFG where the call
672 // itself occurs. Note that `'b` and `'c` must both
673 // include P. At the point, the call works because of
674 // subtyping (i.e., `&'b u32 <: &{P} u32`).
675 let variance
= ::std
::mem
::replace(&mut self.ambient_variance
, ty
::Variance
::Covariant
);
677 self.relate(a
.skip_binder(), b
.skip_binder())?
;
679 self.ambient_variance
= variance
;
681 self.b_scopes
.pop().unwrap();
682 self.a_scopes
.pop().unwrap();
685 if self.ambient_contravariance() {
686 // Contravariance, so we want `for<..> A :> for<..> B`
687 // -- therefore we compare every instantiation of A (i.e.,
688 // A instantiated with universals) against any
689 // instantiation of B (i.e., B instantiated with
690 // existentials). Opposite of above.
692 let a_scope
= self.create_scope(a
, UniversallyQuantified(true));
693 let b_scope
= self.create_scope(b
, UniversallyQuantified(false));
695 debug
!("binders: a_scope = {:?} (universal)", a_scope
);
696 debug
!("binders: b_scope = {:?} (existential)", b_scope
);
698 self.a_scopes
.push(a_scope
);
699 self.b_scopes
.push(b_scope
);
701 // Reset ambient variance to contravariance. See the
702 // covariant case above for an explanation.
704 ::std
::mem
::replace(&mut self.ambient_variance
, ty
::Variance
::Contravariant
);
706 self.relate(a
.skip_binder(), b
.skip_binder())?
;
708 self.ambient_variance
= variance
;
710 self.b_scopes
.pop().unwrap();
711 self.a_scopes
.pop().unwrap();
718 /// When we encounter a binder like `for<..> fn(..)`, we actually have
719 /// to walk the `fn` value to find all the values bound by the `for`
720 /// (these are not explicitly present in the ty representation right
721 /// now). This visitor handles that: it descends the type, tracking
722 /// binder depth, and finds late-bound regions targeting the
723 /// `for<..`>. For each of those, it creates an entry in
724 /// `bound_region_scope`.
725 struct ScopeInstantiator
<'me
, 'tcx
> {
726 next_region
: &'me
mut dyn FnMut(ty
::BoundRegion
) -> ty
::Region
<'tcx
>,
727 // The debruijn index of the scope we are instantiating.
728 target_index
: ty
::DebruijnIndex
,
729 bound_region_scope
: &'me
mut BoundRegionScope
<'tcx
>,
732 impl<'me
, 'tcx
> TypeVisitor
<'tcx
> for ScopeInstantiator
<'me
, 'tcx
> {
733 fn visit_binder
<T
: TypeFoldable
<'tcx
>>(&mut self, t
: &ty
::Binder
<T
>) -> bool
{
734 self.target_index
.shift_in(1);
735 t
.super_visit_with(self);
736 self.target_index
.shift_out(1);
741 fn visit_region(&mut self, r
: ty
::Region
<'tcx
>) -> bool
{
742 let ScopeInstantiator { bound_region_scope, next_region, .. }
= self;
745 ty
::ReLateBound(debruijn
, br
) if *debruijn
== self.target_index
=> {
746 bound_region_scope
.map
.entry(*br
).or_insert_with(|| next_region(*br
));
756 /// The "type generalize" is used when handling inference variables.
758 /// The basic strategy for handling a constraint like `?A <: B` is to
759 /// apply a "generalization strategy" to the type `B` -- this replaces
760 /// all the lifetimes in the type `B` with fresh inference
761 /// variables. (You can read more about the strategy in this [blog
764 /// As an example, if we had `?A <: &'x u32`, we would generalize `&'x
765 /// u32` to `&'0 u32` where `'0` is a fresh variable. This becomes the
766 /// value of `A`. Finally, we relate `&'0 u32 <: &'x u32`, which
767 /// establishes `'0: 'x` as a constraint.
769 /// As a side-effect of this generalization procedure, we also replace
770 /// all the bound regions that we have traversed with concrete values,
771 /// so that the resulting generalized type is independent from the
774 /// [blog post]: https://is.gd/0hKvIr
775 struct TypeGeneralizer
<'me
, 'tcx
, D
>
777 D
: TypeRelatingDelegate
<'tcx
>,
779 infcx
: &'me InferCtxt
<'me
, 'tcx
>,
781 delegate
: &'me
mut D
,
783 /// After we generalize this type, we are going to relative it to
784 /// some other type. What will be the variance at this point?
785 ambient_variance
: ty
::Variance
,
787 first_free_index
: ty
::DebruijnIndex
,
789 /// The vid of the type variable that is in the process of being
790 /// instantiated. If we find this within the value we are folding,
791 /// that means we would have created a cyclic value.
792 for_vid_sub_root
: ty
::TyVid
,
794 /// The universe of the type variable that is in the process of being
795 /// instantiated. If we find anything that this universe cannot name,
796 /// we reject the relation.
797 universe
: ty
::UniverseIndex
,
800 impl<D
> TypeRelation
<'tcx
> for TypeGeneralizer
<'me
, 'tcx
, D
>
802 D
: TypeRelatingDelegate
<'tcx
>,
804 fn tcx(&self) -> TyCtxt
<'tcx
> {
808 // FIXME(oli-obk): not sure how to get the correct ParamEnv
809 fn param_env(&self) -> ty
::ParamEnv
<'tcx
> {
810 ty
::ParamEnv
::empty()
813 fn tag(&self) -> &'
static str {
817 fn a_is_expected(&self) -> bool
{
821 fn relate_with_variance
<T
: Relate
<'tcx
>>(
823 variance
: ty
::Variance
,
826 ) -> RelateResult
<'tcx
, T
> {
828 "TypeGeneralizer::relate_with_variance(variance={:?}, a={:?}, b={:?})",
832 let old_ambient_variance
= self.ambient_variance
;
833 self.ambient_variance
= self.ambient_variance
.xform(variance
);
836 "TypeGeneralizer::relate_with_variance: ambient_variance = {:?}",
837 self.ambient_variance
840 let r
= self.relate(a
, b
)?
;
842 self.ambient_variance
= old_ambient_variance
;
844 debug
!("TypeGeneralizer::relate_with_variance: r={:?}", r
);
849 fn tys(&mut self, a
: Ty
<'tcx
>, _
: Ty
<'tcx
>) -> RelateResult
<'tcx
, Ty
<'tcx
>> {
850 use crate::infer
::type_variable
::TypeVariableValue
;
852 debug
!("TypeGeneralizer::tys(a={:?})", a
);
855 ty
::Infer(ty
::TyVar(_
)) | ty
::Infer(ty
::IntVar(_
)) | ty
::Infer(ty
::FloatVar(_
))
856 if D
::forbid_inference_vars() =>
858 bug
!("unexpected inference variable encountered in NLL generalization: {:?}", a
);
861 ty
::Infer(ty
::TyVar(vid
)) => {
862 let mut variables
= self.infcx
.type_variables
.borrow_mut();
863 let vid
= variables
.root_var(vid
);
864 let sub_vid
= variables
.sub_root_var(vid
);
865 if sub_vid
== self.for_vid_sub_root
{
866 // If sub-roots are equal, then `for_vid` and
867 // `vid` are related via subtyping.
868 debug
!("TypeGeneralizer::tys: occurs check failed");
869 return Err(TypeError
::Mismatch
);
871 match variables
.probe(vid
) {
872 TypeVariableValue
::Known { value: u }
=> {
876 TypeVariableValue
::Unknown { universe: _universe }
=> {
877 if self.ambient_variance
== ty
::Bivariant
{
878 // FIXME: we may need a WF predicate (related to #54105).
881 let origin
= *variables
.var_origin(vid
);
883 // Replacing with a new variable in the universe `self.universe`,
884 // it will be unified later with the original type variable in
885 // the universe `_universe`.
886 let new_var_id
= variables
.new_var(self.universe
, false, origin
);
888 let u
= self.tcx().mk_ty_var(new_var_id
);
889 debug
!("generalize: replacing original vid={:?} with new={:?}", vid
, u
);
896 ty
::Infer(ty
::IntVar(_
)) | ty
::Infer(ty
::FloatVar(_
)) => {
897 // No matter what mode we are in,
898 // integer/floating-point types must be equal to be
903 ty
::Placeholder(placeholder
) => {
904 if self.universe
.cannot_name(placeholder
.universe
) {
906 "TypeGeneralizer::tys: root universe {:?} cannot name\
907 placeholder in universe {:?}",
908 self.universe
, placeholder
.universe
910 Err(TypeError
::Mismatch
)
916 _
=> relate
::super_relate_tys(self, a
, a
),
924 ) -> RelateResult
<'tcx
, ty
::Region
<'tcx
>> {
925 debug
!("TypeGeneralizer::regions(a={:?})", a
);
927 if let ty
::ReLateBound(debruijn
, _
) = a
{
928 if *debruijn
< self.first_free_index
{
933 // For now, we just always create a fresh region variable to
934 // replace all the regions in the source type. In the main
935 // type checker, we special case the case where the ambient
936 // variance is `Invariant` and try to avoid creating a fresh
937 // region variable, but since this comes up so much less in
938 // NLL (only when users use `_` etc) it is much less
941 // As an aside, since these new variables are created in
942 // `self.universe` universe, this also serves to enforce the
943 // universe scoping rules.
945 // FIXME(#54105) -- if the ambient variance is bivariant,
946 // though, we may however need to check well-formedness or
947 // risk a problem like #41677 again.
949 let replacement_region_vid
= self.delegate
.generalize_existential(self.universe
);
951 Ok(replacement_region_vid
)
956 a
: &'tcx ty
::Const
<'tcx
>,
957 _
: &'tcx ty
::Const
<'tcx
>,
958 ) -> RelateResult
<'tcx
, &'tcx ty
::Const
<'tcx
>> {
960 ty
::ConstKind
::Infer(InferConst
::Var(_
)) if D
::forbid_inference_vars() => {
961 bug
!("unexpected inference variable encountered in NLL generalization: {:?}", a
);
963 ty
::ConstKind
::Infer(InferConst
::Var(vid
)) => {
964 let mut variable_table
= self.infcx
.const_unification_table
.borrow_mut();
965 let var_value
= variable_table
.probe_value(vid
);
966 match var_value
.val
.known() {
967 Some(u
) => self.relate(&u
, &u
),
969 let new_var_id
= variable_table
.new_key(ConstVarValue
{
970 origin
: var_value
.origin
,
971 val
: ConstVariableValue
::Unknown { universe: self.universe }
,
973 Ok(self.tcx().mk_const_var(new_var_id
, a
.ty
))
977 _
=> relate
::super_relate_consts(self, a
, a
),
985 ) -> RelateResult
<'tcx
, ty
::Binder
<T
>>
989 debug
!("TypeGeneralizer::binders(a={:?})", a
);
991 self.first_free_index
.shift_in(1);
992 let result
= self.relate(a
.skip_binder(), a
.skip_binder())?
;
993 self.first_free_index
.shift_out(1);
994 Ok(ty
::Binder
::bind(result
))