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