src/librustc/infer/nll_relate/mod.rs

   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.
   5 //!
   6 //! Here are the key differences:
   7 //!
   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
  15 //!   get there first.
  16 //!
  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
  22 //!   constituents)
  23
  24 use crate::infer::InferCtxt;
  25 use crate::ty::fold::{TypeFoldable, TypeVisitor};
  26 use crate::ty::relate::{self, Relate, RelateResult, TypeRelation};
  27 use crate::ty::subst::Kind;
  28 use crate::ty::{self, Ty, TyCtxt};
  29 use crate::ty::error::TypeError;
  30 use crate::traits::DomainGoal;
  31 use rustc_data_structures::fx::FxHashMap;
  32
  33 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
  34 pub enum NormalizationStrategy {
  35     Lazy,
  36     Eager,
  37 }
  38
  39 pub struct TypeRelating<'me, 'gcx: 'tcx, 'tcx: 'me, D>
  40 where
  41     D: TypeRelatingDelegate<'tcx>,
  42 {
  43     infcx: &'me InferCtxt<'me, 'gcx, 'tcx>,
  44
  45     /// Callback to use when we deduce an outlives relationship
  46     delegate: D,
  47
  48     /// How are we relating `a` and `b`?
  49     ///
  50     /// - Covariant means `a <: b`.
  51     /// - Contravariant means `b <: a`.
  52     /// - Invariant means `a == b.
  53     /// - Bivariant means that it doesn't matter.
  54     ambient_variance: ty::Variance,
  55
  56     /// When we pass through a set of binders (e.g., when looking into
  57     /// a `fn` type), we push a new bound region scope onto here. This
  58     /// will contain the instantiated region for each region in those
  59     /// binders. When we then encounter a `ReLateBound(d, br)`, we can
  60     /// use the De Bruijn index `d` to find the right scope, and then
  61     /// bound region name `br` to find the specific instantiation from
  62     /// within that scope. See `replace_bound_region`.
  63     ///
  64     /// This field stores the instantiations for late-bound regions in
  65     /// the `a` type.
  66     a_scopes: Vec<BoundRegionScope<'tcx>>,
  67
  68     /// Same as `a_scopes`, but for the `b` type.
  69     b_scopes: Vec<BoundRegionScope<'tcx>>,
  70 }
  71
  72 pub trait TypeRelatingDelegate<'tcx> {
  73     /// Push a constraint `sup: sub` -- this constraint must be
  74     /// satisfied for the two types to be related. `sub` and `sup` may
  75     /// be regions from the type or new variables created through the
  76     /// delegate.
  77     fn push_outlives(&mut self, sup: ty::Region<'tcx>, sub: ty::Region<'tcx>);
  78
  79     /// Push a domain goal that will need to be proved for the two types to
  80     /// be related. Used for lazy normalization.
  81     fn push_domain_goal(&mut self, domain_goal: DomainGoal<'tcx>);
  82
  83     /// Creates a new universe index. Used when instantiating placeholders.
  84     fn create_next_universe(&mut self) -> ty::UniverseIndex;
  85
  86     /// Creates a new region variable representing a higher-ranked
  87     /// region that is instantiated existentially. This creates an
  88     /// inference variable, typically.
  89     ///
  90     /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then
  91     /// we will invoke this method to instantiate `'a` with an
  92     /// inference variable (though `'b` would be instantiated first,
  93     /// as a placeholder).
  94     fn next_existential_region_var(&mut self) -> ty::Region<'tcx>;
  95
  96     /// Creates a new region variable representing a
  97     /// higher-ranked region that is instantiated universally.
  98     /// This creates a new region placeholder, typically.
  99     ///
 100     /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then
 101     /// we will invoke this method to instantiate `'b` with a
 102     /// placeholder region.
 103     fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx>;
 104
 105     /// Creates a new existential region in the given universe. This
 106     /// is used when handling subtyping and type variables -- if we
 107     /// have that `?X <: Foo<'a>`, for example, we would instantiate
 108     /// `?X` with a type like `Foo<'?0>` where `'?0` is a fresh
 109     /// existential variable created by this function. We would then
 110     /// relate `Foo<'?0>` with `Foo<'a>` (and probably add an outlives
 111     /// relation stating that `'?0: 'a`).
 112     fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>;
 113
 114     /// Define the normalization strategy to use, eager or lazy.
 115     fn normalization() -> NormalizationStrategy;
 116
 117     /// Enables some optimizations if we do not expect inference variables
 118     /// in the RHS of the relation.
 119     fn forbid_inference_vars() -> bool;
 120 }
 121
 122 #[derive(Clone, Debug)]
 123 struct ScopesAndKind<'tcx> {
 124     scopes: Vec<BoundRegionScope<'tcx>>,
 125     kind: Kind<'tcx>,
 126 }
 127
 128 #[derive(Clone, Debug, Default)]
 129 struct BoundRegionScope<'tcx> {
 130     map: FxHashMap<ty::BoundRegion, ty::Region<'tcx>>,
 131 }
 132
 133 #[derive(Copy, Clone)]
 134 struct UniversallyQuantified(bool);
 135
 136 impl<'me, 'gcx, 'tcx, D> TypeRelating<'me, 'gcx, 'tcx, D>
 137 where
 138     D: TypeRelatingDelegate<'tcx>,
 139 {
 140     pub fn new(
 141         infcx: &'me InferCtxt<'me, 'gcx, 'tcx>,
 142         delegate: D,
 143         ambient_variance: ty::Variance,
 144     ) -> Self {
 145         Self {
 146             infcx,
 147             delegate,
 148             ambient_variance,
 149             a_scopes: vec![],
 150             b_scopes: vec![],
 151         }
 152     }
 153
 154     fn ambient_covariance(&self) -> bool {
 155         match self.ambient_variance {
 156             ty::Variance::Covariant | ty::Variance::Invariant => true,
 157             ty::Variance::Contravariant | ty::Variance::Bivariant => false,
 158         }
 159     }
 160
 161     fn ambient_contravariance(&self) -> bool {
 162         match self.ambient_variance {
 163             ty::Variance::Contravariant | ty::Variance::Invariant => true,
 164             ty::Variance::Covariant | ty::Variance::Bivariant => false,
 165         }
 166     }
 167
 168     fn create_scope(
 169         &mut self,
 170         value: &ty::Binder<impl TypeFoldable<'tcx>>,
 171         universally_quantified: UniversallyQuantified,
 172     ) -> BoundRegionScope<'tcx> {
 173         let mut scope = BoundRegionScope::default();
 174
 175         // Create a callback that creates (via the delegate) either an
 176         // existential or placeholder region as needed.
 177         let mut next_region = {
 178             let delegate = &mut self.delegate;
 179             let mut lazy_universe = None;
 180             move |br: ty::BoundRegion| {
 181                 if universally_quantified.0 {
 182                     // The first time this closure is called, create a
 183                     // new universe for the placeholders we will make
 184                     // from here out.
 185                     let universe = lazy_universe.unwrap_or_else(|| {
 186                         let universe = delegate.create_next_universe();
 187                         lazy_universe = Some(universe);
 188                         universe
 189                     });
 190
 191                     let placeholder = ty::PlaceholderRegion { universe, name: br };
 192                     delegate.next_placeholder_region(placeholder)
 193                 } else {
 194                     delegate.next_existential_region_var()
 195                 }
 196             }
 197         };
 198
 199         value.skip_binder().visit_with(&mut ScopeInstantiator {
 200             next_region: &mut next_region,
 201             target_index: ty::INNERMOST,
 202             bound_region_scope: &mut scope,
 203         });
 204
 205         scope
 206     }
 207
 208     /// When we encounter binders during the type traversal, we record
 209     /// the value to substitute for each of the things contained in
 210     /// that binder. (This will be either a universal placeholder or
 211     /// an existential inference variable.) Given the De Bruijn index
 212     /// `debruijn` (and name `br`) of some binder we have now
 213     /// encountered, this routine finds the value that we instantiated
 214     /// the region with; to do so, it indexes backwards into the list
 215     /// of ambient scopes `scopes`.
 216     fn lookup_bound_region(
 217         debruijn: ty::DebruijnIndex,
 218         br: &ty::BoundRegion,
 219         first_free_index: ty::DebruijnIndex,
 220         scopes: &[BoundRegionScope<'tcx>],
 221     ) -> ty::Region<'tcx> {
 222         // The debruijn index is a "reverse index" into the
 223         // scopes listing. So when we have INNERMOST (0), we
 224         // want the *last* scope pushed, and so forth.
 225         let debruijn_index = debruijn.index() - first_free_index.index();
 226         let scope = &scopes[scopes.len() - debruijn_index - 1];
 227
 228         // Find this bound region in that scope to map to a
 229         // particular region.
 230         scope.map[br]
 231     }
 232
 233     /// If `r` is a bound region, find the scope in which it is bound
 234     /// (from `scopes`) and return the value that we instantiated it
 235     /// with. Otherwise just return `r`.
 236     fn replace_bound_region(
 237         &self,
 238         r: ty::Region<'tcx>,
 239         first_free_index: ty::DebruijnIndex,
 240         scopes: &[BoundRegionScope<'tcx>],
 241     ) -> ty::Region<'tcx> {
 242         if let ty::ReLateBound(debruijn, br) = r {
 243             Self::lookup_bound_region(*debruijn, br, first_free_index, scopes)
 244         } else {
 245             r
 246         }
 247     }
 248
 249     /// Push a new outlives requirement into our output set of
 250     /// constraints.
 251     fn push_outlives(&mut self, sup: ty::Region<'tcx>, sub: ty::Region<'tcx>) {
 252         debug!("push_outlives({:?}: {:?})", sup, sub);
 253
 254         self.delegate.push_outlives(sup, sub);
 255     }
 256
 257     /// Relate a projection type and some value type lazily. This will always
 258     /// succeed, but we push an additional `ProjectionEq` goal depending
 259     /// on the value type:
 260     /// - if the value type is any type `T` which is not a projection, we push
 261     ///   `ProjectionEq(projection = T)`.
 262     /// - if the value type is another projection `other_projection`, we create
 263     ///   a new inference variable `?U` and push the two goals
 264     ///   `ProjectionEq(projection = ?U)`, `ProjectionEq(other_projection = ?U)`.
 265     fn relate_projection_ty(
 266         &mut self,
 267         projection_ty: ty::ProjectionTy<'tcx>,
 268         value_ty: ty::Ty<'tcx>
 269     ) -> Ty<'tcx> {
 270         use crate::infer::type_variable::TypeVariableOrigin;
 271         use crate::traits::WhereClause;
 272         use syntax_pos::DUMMY_SP;
 273
 274         match value_ty.sty {
 275             ty::Projection(other_projection_ty) => {
 276                 let var = self.infcx.next_ty_var(TypeVariableOrigin::MiscVariable(DUMMY_SP));
 277                 self.relate_projection_ty(projection_ty, var);
 278                 self.relate_projection_ty(other_projection_ty, var);
 279                 var
 280             }
 281
 282             _ => {
 283                 let projection = ty::ProjectionPredicate {
 284                     projection_ty,
 285                     ty: value_ty,
 286                 };
 287                 self.delegate.push_domain_goal(
 288                     DomainGoal::Holds(WhereClause::ProjectionEq(projection))
 289                 );
 290                 value_ty
 291             }
 292         }
 293     }
 294
 295     /// Relate a type inference variable with a value type.
 296     fn relate_ty_var(
 297         &mut self,
 298         vid: ty::TyVid,
 299         value_ty: Ty<'tcx>
 300     ) -> RelateResult<'tcx, Ty<'tcx>> {
 301         debug!("relate_ty_var(vid={:?}, value_ty={:?})", vid, value_ty);
 302
 303         match value_ty.sty {
 304             ty::Infer(ty::TyVar(value_vid)) => {
 305                 // Two type variables: just equate them.
 306                 self.infcx.type_variables.borrow_mut().equate(vid, value_vid);
 307                 return Ok(value_ty);
 308             }
 309
 310             ty::Projection(projection_ty)
 311                 if D::normalization() == NormalizationStrategy::Lazy =>
 312             {
 313                 return Ok(self.relate_projection_ty(projection_ty, self.infcx.tcx.mk_var(vid)));
 314             }
 315
 316             _ => (),
 317         }
 318
 319         let generalized_ty = self.generalize_value(value_ty, vid)?;
 320         debug!("relate_ty_var: generalized_ty = {:?}", generalized_ty);
 321
 322         if D::forbid_inference_vars() {
 323             // In NLL, we don't have type inference variables
 324             // floating around, so we can do this rather imprecise
 325             // variant of the occurs-check.
 326             assert!(!generalized_ty.has_infer_types());
 327         }
 328
 329         self.infcx.type_variables.borrow_mut().instantiate(vid, generalized_ty);
 330
 331         // The generalized values we extract from `canonical_var_values` have
 332         // been fully instantiated and hence the set of scopes we have
 333         // doesn't matter -- just to be sure, put an empty vector
 334         // in there.
 335         let old_a_scopes = ::std::mem::replace(&mut self.a_scopes, vec![]);
 336
 337         // Relate the generalized kind to the original one.
 338         let result = self.relate(&generalized_ty, &value_ty);
 339
 340         // Restore the old scopes now.
 341         self.a_scopes = old_a_scopes;
 342
 343         debug!("relate_ty_var: complete, result = {:?}", result);
 344         result
 345     }
 346
 347     fn generalize_value<T: Relate<'tcx>>(
 348         &mut self,
 349         value: T,
 350         for_vid: ty::TyVid
 351     ) -> RelateResult<'tcx, T> {
 352         let universe = self.infcx.probe_ty_var(for_vid).unwrap_err();
 353
 354         let mut generalizer = TypeGeneralizer {
 355             infcx: self.infcx,
 356             delegate: &mut self.delegate,
 357             first_free_index: ty::INNERMOST,
 358             ambient_variance: self.ambient_variance,
 359             for_vid_sub_root: self.infcx.type_variables.borrow_mut().sub_root_var(for_vid),
 360             universe,
 361         };
 362
 363         generalizer.relate(&value, &value)
 364     }
 365 }
 366
 367 impl<D> TypeRelation<'me, 'gcx, 'tcx> for TypeRelating<'me, 'gcx, 'tcx, D>
 368 where
 369     D: TypeRelatingDelegate<'tcx>,
 370 {
 371     fn tcx(&self) -> TyCtxt<'me, 'gcx, 'tcx> {
 372         self.infcx.tcx
 373     }
 374
 375     fn tag(&self) -> &'static str {
 376         "nll::subtype"
 377     }
 378
 379     fn a_is_expected(&self) -> bool {
 380         true
 381     }
 382
 383     fn relate_with_variance<T: Relate<'tcx>>(
 384         &mut self,
 385         variance: ty::Variance,
 386         a: &T,
 387         b: &T,
 388     ) -> RelateResult<'tcx, T> {
 389         debug!(
 390             "relate_with_variance(variance={:?}, a={:?}, b={:?})",
 391             variance, a, b
 392         );
 393
 394         let old_ambient_variance = self.ambient_variance;
 395         self.ambient_variance = self.ambient_variance.xform(variance);
 396
 397         debug!(
 398             "relate_with_variance: ambient_variance = {:?}",
 399             self.ambient_variance
 400         );
 401
 402         let r = self.relate(a, b)?;
 403
 404         self.ambient_variance = old_ambient_variance;
 405
 406         debug!("relate_with_variance: r={:?}", r);
 407
 408         Ok(r)
 409     }
 410
 411     fn tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
 412         let a = self.infcx.shallow_resolve(a);
 413
 414         if !D::forbid_inference_vars() {
 415             b = self.infcx.shallow_resolve(b);
 416         }
 417
 418         match (&a.sty, &b.sty) {
 419             (_, &ty::Infer(ty::TyVar(vid))) => {
 420                 if D::forbid_inference_vars() {
 421                     // Forbid inference variables in the RHS.
 422                     bug!("unexpected inference var {:?}", b)
 423                 } else {
 424                     self.relate_ty_var(vid, a)
 425                 }
 426             }
 427
 428             (&ty::Infer(ty::TyVar(vid)), _) => self.relate_ty_var(vid, b),
 429
 430             (&ty::Projection(projection_ty), _)
 431                 if D::normalization() == NormalizationStrategy::Lazy =>
 432             {
 433                 Ok(self.relate_projection_ty(projection_ty, b))
 434             }
 435
 436             (_, &ty::Projection(projection_ty))
 437                 if D::normalization() == NormalizationStrategy::Lazy =>
 438             {
 439                 Ok(self.relate_projection_ty(projection_ty, a))
 440             }
 441
 442             _ => {
 443                 debug!(
 444                     "tys(a={:?}, b={:?}, variance={:?})",
 445                     a, b, self.ambient_variance
 446                 );
 447
 448                 // Will also handle unification of `IntVar` and `FloatVar`.
 449                 self.infcx.super_combine_tys(self, a, b)
 450             }
 451         }
 452     }
 453
 454     fn regions(
 455         &mut self,
 456         a: ty::Region<'tcx>,
 457         b: ty::Region<'tcx>,
 458     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 459         debug!(
 460             "regions(a={:?}, b={:?}, variance={:?})",
 461             a, b, self.ambient_variance
 462         );
 463
 464         let v_a = self.replace_bound_region(a, ty::INNERMOST, &self.a_scopes);
 465         let v_b = self.replace_bound_region(b, ty::INNERMOST, &self.b_scopes);
 466
 467         debug!("regions: v_a = {:?}", v_a);
 468         debug!("regions: v_b = {:?}", v_b);
 469
 470         if self.ambient_covariance() {
 471             // Covariance: a <= b. Hence, `b: a`.
 472             self.push_outlives(v_b, v_a);
 473         }
 474
 475         if self.ambient_contravariance() {
 476             // Contravariant: b <= a. Hence, `a: b`.
 477             self.push_outlives(v_a, v_b);
 478         }
 479
 480         Ok(a)
 481     }
 482
 483     fn binders<T>(
 484         &mut self,
 485         a: &ty::Binder<T>,
 486         b: &ty::Binder<T>,
 487     ) -> RelateResult<'tcx, ty::Binder<T>>
 488     where
 489         T: Relate<'tcx>,
 490     {
 491         // We want that
 492         //
 493         // ```
 494         // for<'a> fn(&'a u32) -> &'a u32 <:
 495         //   fn(&'b u32) -> &'b u32
 496         // ```
 497         //
 498         // but not
 499         //
 500         // ```
 501         // fn(&'a u32) -> &'a u32 <:
 502         //   for<'b> fn(&'b u32) -> &'b u32
 503         // ```
 504         //
 505         // We therefore proceed as follows:
 506         //
 507         // - Instantiate binders on `b` universally, yielding a universe U1.
 508         // - Instantiate binders on `a` existentially in U1.
 509
 510         debug!(
 511             "binders({:?}: {:?}, ambient_variance={:?})",
 512             a, b, self.ambient_variance
 513         );
 514
 515         if self.ambient_covariance() {
 516             // Covariance, so we want `for<..> A <: for<..> B` --
 517             // therefore we compare any instantiation of A (i.e., A
 518             // instantiated with existentials) against every
 519             // instantiation of B (i.e., B instantiated with
 520             // universals).
 521
 522             let b_scope = self.create_scope(b, UniversallyQuantified(true));
 523             let a_scope = self.create_scope(a, UniversallyQuantified(false));
 524
 525             debug!("binders: a_scope = {:?} (existential)", a_scope);
 526             debug!("binders: b_scope = {:?} (universal)", b_scope);
 527
 528             self.b_scopes.push(b_scope);
 529             self.a_scopes.push(a_scope);
 530
 531             // Reset the ambient variance to covariant. This is needed
 532             // to correctly handle cases like
 533             //
 534             //     for<'a> fn(&'a u32, &'a u3) == for<'b, 'c> fn(&'b u32, &'c u32)
 535             //
 536             // Somewhat surprisingly, these two types are actually
 537             // **equal**, even though the one on the right looks more
 538             // polymorphic. The reason is due to subtyping. To see it,
 539             // consider that each function can call the other:
 540             //
 541             // - The left function can call the right with `'b` and
 542             //   `'c` both equal to `'a`
 543             //
 544             // - The right function can call the left with `'a` set to
 545             //   `{P}`, where P is the point in the CFG where the call
 546             //   itself occurs. Note that `'b` and `'c` must both
 547             //   include P. At the point, the call works because of
 548             //   subtyping (i.e., `&'b u32 <: &{P} u32`).
 549             let variance = ::std::mem::replace(&mut self.ambient_variance, ty::Variance::Covariant);
 550
 551             self.relate(a.skip_binder(), b.skip_binder())?;
 552
 553             self.ambient_variance = variance;
 554
 555             self.b_scopes.pop().unwrap();
 556             self.a_scopes.pop().unwrap();
 557         }
 558
 559         if self.ambient_contravariance() {
 560             // Contravariance, so we want `for<..> A :> for<..> B`
 561             // -- therefore we compare every instantiation of A (i.e.,
 562             // A instantiated with universals) against any
 563             // instantiation of B (i.e., B instantiated with
 564             // existentials). Opposite of above.
 565
 566             let a_scope = self.create_scope(a, UniversallyQuantified(true));
 567             let b_scope = self.create_scope(b, UniversallyQuantified(false));
 568
 569             debug!("binders: a_scope = {:?} (universal)", a_scope);
 570             debug!("binders: b_scope = {:?} (existential)", b_scope);
 571
 572             self.a_scopes.push(a_scope);
 573             self.b_scopes.push(b_scope);
 574
 575             // Reset ambient variance to contravariance. See the
 576             // covariant case above for an explanation.
 577             let variance =
 578                 ::std::mem::replace(&mut self.ambient_variance, ty::Variance::Contravariant);
 579
 580             self.relate(a.skip_binder(), b.skip_binder())?;
 581
 582             self.ambient_variance = variance;
 583
 584             self.b_scopes.pop().unwrap();
 585             self.a_scopes.pop().unwrap();
 586         }
 587
 588         Ok(a.clone())
 589     }
 590 }
 591
 592 /// When we encounter a binder like `for<..> fn(..)`, we actually have
 593 /// to walk the `fn` value to find all the values bound by the `for`
 594 /// (these are not explicitly present in the ty representation right
 595 /// now). This visitor handles that: it descends the type, tracking
 596 /// binder depth, and finds late-bound regions targeting the
 597 /// `for<..`>.  For each of those, it creates an entry in
 598 /// `bound_region_scope`.
 599 struct ScopeInstantiator<'me, 'tcx: 'me> {
 600     next_region: &'me mut dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 601     // The debruijn index of the scope we are instantiating.
 602     target_index: ty::DebruijnIndex,
 603     bound_region_scope: &'me mut BoundRegionScope<'tcx>,
 604 }
 605
 606 impl<'me, 'tcx> TypeVisitor<'tcx> for ScopeInstantiator<'me, 'tcx> {
 607     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> bool {
 608         self.target_index.shift_in(1);
 609         t.super_visit_with(self);
 610         self.target_index.shift_out(1);
 611
 612         false
 613     }
 614
 615     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 616         let ScopeInstantiator {
 617             bound_region_scope,
 618             next_region,
 619             ..
 620         } = self;
 621
 622         match r {
 623             ty::ReLateBound(debruijn, br) if *debruijn == self.target_index => {
 624                 bound_region_scope
 625                     .map
 626                     .entry(*br)
 627                     .or_insert_with(|| next_region(*br));
 628             }
 629
 630             _ => {}
 631         }
 632
 633         false
 634     }
 635 }
 636
 637 /// The "type generalize" is used when handling inference variables.
 638 ///
 639 /// The basic strategy for handling a constraint like `?A <: B` is to
 640 /// apply a "generalization strategy" to the type `B` -- this replaces
 641 /// all the lifetimes in the type `B` with fresh inference
 642 /// variables. (You can read more about the strategy in this [blog
 643 /// post].)
 644 ///
 645 /// As an example, if we had `?A <: &'x u32`, we would generalize `&'x
 646 /// u32` to `&'0 u32` where `'0` is a fresh variable. This becomes the
 647 /// value of `A`. Finally, we relate `&'0 u32 <: &'x u32`, which
 648 /// establishes `'0: 'x` as a constraint.
 649 ///
 650 /// As a side-effect of this generalization procedure, we also replace
 651 /// all the bound regions that we have traversed with concrete values,
 652 /// so that the resulting generalized type is independent from the
 653 /// scopes.
 654 ///
 655 /// [blog post]: https://is.gd/0hKvIr
 656 struct TypeGeneralizer<'me, 'gcx: 'tcx, 'tcx: 'me, D>
 657 where
 658     D: TypeRelatingDelegate<'tcx> + 'me,
 659 {
 660     infcx: &'me InferCtxt<'me, 'gcx, 'tcx>,
 661
 662     delegate: &'me mut D,
 663
 664     /// After we generalize this type, we are going to relative it to
 665     /// some other type. What will be the variance at this point?
 666     ambient_variance: ty::Variance,
 667
 668     first_free_index: ty::DebruijnIndex,
 669
 670     /// The vid of the type variable that is in the process of being
 671     /// instantiated. If we find this within the value we are folding,
 672     /// that means we would have created a cyclic value.
 673     for_vid_sub_root: ty::TyVid,
 674
 675     /// The universe of the type variable that is in the process of being
 676     /// instantiated. If we find anything that this universe cannot name,
 677     /// we reject the relation.
 678     universe: ty::UniverseIndex,
 679 }
 680
 681 impl<D> TypeRelation<'me, 'gcx, 'tcx> for TypeGeneralizer<'me, 'gcx, 'tcx, D>
 682 where
 683     D: TypeRelatingDelegate<'tcx>,
 684 {
 685     fn tcx(&self) -> TyCtxt<'me, 'gcx, 'tcx> {
 686         self.infcx.tcx
 687     }
 688
 689     fn tag(&self) -> &'static str {
 690         "nll::generalizer"
 691     }
 692
 693     fn a_is_expected(&self) -> bool {
 694         true
 695     }
 696
 697     fn relate_with_variance<T: Relate<'tcx>>(
 698         &mut self,
 699         variance: ty::Variance,
 700         a: &T,
 701         b: &T,
 702     ) -> RelateResult<'tcx, T> {
 703         debug!(
 704             "TypeGeneralizer::relate_with_variance(variance={:?}, a={:?}, b={:?})",
 705             variance, a, b
 706         );
 707
 708         let old_ambient_variance = self.ambient_variance;
 709         self.ambient_variance = self.ambient_variance.xform(variance);
 710
 711         debug!(
 712             "TypeGeneralizer::relate_with_variance: ambient_variance = {:?}",
 713             self.ambient_variance
 714         );
 715
 716         let r = self.relate(a, b)?;
 717
 718         self.ambient_variance = old_ambient_variance;
 719
 720         debug!("TypeGeneralizer::relate_with_variance: r={:?}", r);
 721
 722         Ok(r)
 723     }
 724
 725     fn tys(&mut self, a: Ty<'tcx>, _: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
 726         use crate::infer::type_variable::TypeVariableValue;
 727
 728         debug!("TypeGeneralizer::tys(a={:?})", a,);
 729
 730         match a.sty {
 731             ty::Infer(ty::TyVar(_)) | ty::Infer(ty::IntVar(_)) | ty::Infer(ty::FloatVar(_))
 732                 if D::forbid_inference_vars() =>
 733             {
 734                 bug!(
 735                     "unexpected inference variable encountered in NLL generalization: {:?}",
 736                     a
 737                 );
 738             }
 739
 740             ty::Infer(ty::TyVar(vid)) => {
 741                 let mut variables = self.infcx.type_variables.borrow_mut();
 742                 let vid = variables.root_var(vid);
 743                 let sub_vid = variables.sub_root_var(vid);
 744                 if sub_vid == self.for_vid_sub_root {
 745                     // If sub-roots are equal, then `for_vid` and
 746                     // `vid` are related via subtyping.
 747                     debug!("TypeGeneralizer::tys: occurs check failed");
 748                     return Err(TypeError::Mismatch);
 749                 } else {
 750                     match variables.probe(vid) {
 751                         TypeVariableValue::Known { value: u } => {
 752                             drop(variables);
 753                             self.relate(&u, &u)
 754                         }
 755                         TypeVariableValue::Unknown { universe: _universe } => {
 756                             if self.ambient_variance == ty::Bivariant {
 757                                 // FIXME: we may need a WF predicate (related to #54105).
 758                             }
 759
 760                             let origin = *variables.var_origin(vid);
 761
 762                             // Replacing with a new variable in the universe `self.universe`,
 763                             // it will be unified later with the original type variable in
 764                             // the universe `_universe`.
 765                             let new_var_id = variables.new_var(self.universe, false, origin);
 766
 767                             let u = self.tcx().mk_var(new_var_id);
 768                             debug!(
 769                                 "generalize: replacing original vid={:?} with new={:?}",
 770                                 vid,
 771                                 u
 772                             );
 773                             return Ok(u);
 774                         }
 775                     }
 776                 }
 777             }
 778
 779             ty::Infer(ty::IntVar(_)) |
 780             ty::Infer(ty::FloatVar(_)) => {
 781                 // No matter what mode we are in,
 782                 // integer/floating-point types must be equal to be
 783                 // relatable.
 784                 Ok(a)
 785             }
 786
 787             ty::Placeholder(placeholder) => {
 788                 if self.universe.cannot_name(placeholder.universe) {
 789                     debug!(
 790                         "TypeGeneralizer::tys: root universe {:?} cannot name\
 791                         placeholder in universe {:?}",
 792                         self.universe,
 793                         placeholder.universe
 794                     );
 795                     Err(TypeError::Mismatch)
 796                 } else {
 797                     Ok(a)
 798                 }
 799             }
 800
 801             _ => {
 802                 relate::super_relate_tys(self, a, a)
 803             }
 804         }
 805     }
 806
 807     fn regions(
 808         &mut self,
 809         a: ty::Region<'tcx>,
 810         _: ty::Region<'tcx>,
 811     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 812         debug!("TypeGeneralizer::regions(a={:?})", a,);
 813
 814         if let ty::ReLateBound(debruijn, _) = a {
 815             if *debruijn < self.first_free_index {
 816                 return Ok(a);
 817             }
 818         }
 819
 820         // For now, we just always create a fresh region variable to
 821         // replace all the regions in the source type. In the main
 822         // type checker, we special case the case where the ambient
 823         // variance is `Invariant` and try to avoid creating a fresh
 824         // region variable, but since this comes up so much less in
 825         // NLL (only when users use `_` etc) it is much less
 826         // important.
 827         //
 828         // As an aside, since these new variables are created in
 829         // `self.universe` universe, this also serves to enforce the
 830         // universe scoping rules.
 831         //
 832         // FIXME(#54105) -- if the ambient variance is bivariant,
 833         // though, we may however need to check well-formedness or
 834         // risk a problem like #41677 again.
 835
 836         let replacement_region_vid = self.delegate.generalize_existential(self.universe);
 837
 838         Ok(replacement_region_vid)
 839     }
 840
 841     fn binders<T>(
 842         &mut self,
 843         a: &ty::Binder<T>,
 844         _: &ty::Binder<T>,
 845     ) -> RelateResult<'tcx, ty::Binder<T>>
 846     where
 847         T: Relate<'tcx>,
 848     {
 849         debug!("TypeGeneralizer::binders(a={:?})", a,);
 850
 851         self.first_free_index.shift_in(1);
 852         let result = self.relate(a.skip_binder(), a.skip_binder())?;
 853         self.first_free_index.shift_out(1);
 854         Ok(ty::Binder::bind(result))
 855     }
 856 }