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