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