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