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