src/librustc/infer/nll_relate/mod.rs

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