src/librustc/infer/nll_relate/mod.rs

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