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