compiler/rustc_middle/src/ty/fold.rs

   1 //! Generalized type folding mechanism. The setup is a bit convoluted
   2 //! but allows for convenient usage. Let T be an instance of some
   3 //! "foldable type" (one which implements `TypeFoldable`) and F be an
   4 //! instance of a "folder" (a type which implements `TypeFolder`). Then
   5 //! the setup is intended to be:
   6 //!
   7 //!     T.fold_with(F) --calls--> F.fold_T(T) --calls--> T.super_fold_with(F)
   8 //!
   9 //! This way, when you define a new folder F, you can override
  10 //! `fold_T()` to customize the behavior, and invoke `T.super_fold_with()`
  11 //! to get the original behavior. Meanwhile, to actually fold
  12 //! something, you can just write `T.fold_with(F)`, which is
  13 //! convenient. (Note that `fold_with` will also transparently handle
  14 //! things like a `Vec<T>` where T is foldable and so on.)
  15 //!
  16 //! In this ideal setup, the only function that actually *does*
  17 //! anything is `T.super_fold_with()`, which traverses the type `T`.
  18 //! Moreover, `T.super_fold_with()` should only ever call `T.fold_with()`.
  19 //!
  20 //! In some cases, we follow a degenerate pattern where we do not have
  21 //! a `fold_T` method. Instead, `T.fold_with` traverses the structure directly.
  22 //! This is suboptimal because the behavior cannot be overridden, but it's
  23 //! much less work to implement. If you ever *do* need an override that
  24 //! doesn't exist, it's not hard to convert the degenerate pattern into the
  25 //! proper thing.
  26 //!
  27 //! A `TypeFoldable` T can also be visited by a `TypeVisitor` V using similar setup:
  28 //!
  29 //!     T.visit_with(V) --calls--> V.visit_T(T) --calls--> T.super_visit_with(V).
  30 //!
  31 //! These methods return true to indicate that the visitor has found what it is
  32 //! looking for, and does not need to visit anything else.
  33 use crate::mir;
  34 use crate::ty::{self, flags::FlagComputation, Binder, Ty, TyCtxt, TypeFlags};
  35 use rustc_hir as hir;
  36 use rustc_hir::def_id::DefId;
  37
  38 use rustc_data_structures::fx::FxHashSet;
  39 use rustc_data_structures::sso::SsoHashSet;
  40 use std::collections::BTreeMap;
  41 use std::fmt;
  42 use std::ops::ControlFlow;
  43
  44 /// This trait is implemented for every type that can be folded.
  45 /// Basically, every type that has a corresponding method in `TypeFolder`.
  46 ///
  47 /// To implement this conveniently, use the derive macro located in `rustc_macros`.
  48 pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
  49     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error>;
  50     fn fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
  51         self.super_fold_with(folder)
  52     }
  53
  54     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>;
  55     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
  56         self.super_visit_with(visitor)
  57     }
  58
  59     /// Returns `true` if `self` has any late-bound regions that are either
  60     /// bound by `binder` or bound by some binder outside of `binder`.
  61     /// If `binder` is `ty::INNERMOST`, this indicates whether
  62     /// there are any late-bound regions that appear free.
  63     fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool {
  64         self.visit_with(&mut HasEscapingVarsVisitor { outer_index: binder }).is_break()
  65     }
  66
  67     /// Returns `true` if this `self` has any regions that escape `binder` (and
  68     /// hence are not bound by it).
  69     fn has_vars_bound_above(&self, binder: ty::DebruijnIndex) -> bool {
  70         self.has_vars_bound_at_or_above(binder.shifted_in(1))
  71     }
  72
  73     fn has_escaping_bound_vars(&self) -> bool {
  74         self.has_vars_bound_at_or_above(ty::INNERMOST)
  75     }
  76
  77     fn definitely_has_type_flags(&self, tcx: TyCtxt<'tcx>, flags: TypeFlags) -> bool {
  78         self.visit_with(&mut HasTypeFlagsVisitor { tcx: Some(tcx), flags }).break_value()
  79             == Some(FoundFlags)
  80     }
  81
  82     #[instrument(level = "trace")]
  83     fn has_type_flags(&self, flags: TypeFlags) -> bool {
  84         self.visit_with(&mut HasTypeFlagsVisitor { tcx: None, flags }).break_value()
  85             == Some(FoundFlags)
  86     }
  87     fn has_projections(&self) -> bool {
  88         self.has_type_flags(TypeFlags::HAS_PROJECTION)
  89     }
  90     fn has_opaque_types(&self) -> bool {
  91         self.has_type_flags(TypeFlags::HAS_TY_OPAQUE)
  92     }
  93     fn references_error(&self) -> bool {
  94         self.has_type_flags(TypeFlags::HAS_ERROR)
  95     }
  96     fn potentially_has_param_types_or_consts(&self) -> bool {
  97         self.has_type_flags(
  98             TypeFlags::HAS_KNOWN_TY_PARAM
  99                 | TypeFlags::HAS_KNOWN_CT_PARAM
 100                 | TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS,
 101         )
 102     }
 103     fn definitely_has_param_types_or_consts(&self, tcx: TyCtxt<'tcx>) -> bool {
 104         self.definitely_has_type_flags(
 105             tcx,
 106             TypeFlags::HAS_KNOWN_TY_PARAM | TypeFlags::HAS_KNOWN_CT_PARAM,
 107         )
 108     }
 109     fn has_infer_regions(&self) -> bool {
 110         self.has_type_flags(TypeFlags::HAS_RE_INFER)
 111     }
 112     fn has_infer_types(&self) -> bool {
 113         self.has_type_flags(TypeFlags::HAS_TY_INFER)
 114     }
 115     fn has_infer_types_or_consts(&self) -> bool {
 116         self.has_type_flags(TypeFlags::HAS_TY_INFER | TypeFlags::HAS_CT_INFER)
 117     }
 118     fn needs_infer(&self) -> bool {
 119         self.has_type_flags(TypeFlags::NEEDS_INFER)
 120     }
 121     fn has_placeholders(&self) -> bool {
 122         self.has_type_flags(
 123             TypeFlags::HAS_RE_PLACEHOLDER
 124                 | TypeFlags::HAS_TY_PLACEHOLDER
 125                 | TypeFlags::HAS_CT_PLACEHOLDER,
 126         )
 127     }
 128     fn potentially_needs_subst(&self) -> bool {
 129         self.has_type_flags(
 130             TypeFlags::KNOWN_NEEDS_SUBST | TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS,
 131         )
 132     }
 133     fn definitely_needs_subst(&self, tcx: TyCtxt<'tcx>) -> bool {
 134         self.definitely_has_type_flags(tcx, TypeFlags::KNOWN_NEEDS_SUBST)
 135     }
 136     /// "Free" regions in this context means that it has any region
 137     /// that is not (a) erased or (b) late-bound.
 138     fn has_free_regions(&self, tcx: TyCtxt<'tcx>) -> bool {
 139         self.definitely_has_type_flags(tcx, TypeFlags::HAS_KNOWN_FREE_REGIONS)
 140     }
 141
 142     fn has_erased_regions(&self) -> bool {
 143         self.has_type_flags(TypeFlags::HAS_RE_ERASED)
 144     }
 145
 146     /// True if there are any un-erased free regions.
 147     fn has_erasable_regions(&self, tcx: TyCtxt<'tcx>) -> bool {
 148         self.definitely_has_type_flags(tcx, TypeFlags::HAS_KNOWN_FREE_REGIONS)
 149     }
 150
 151     /// Indicates whether this value definitely references only 'global'
 152     /// generic parameters that are the same regardless of what fn we are
 153     /// in. This is used for caching.
 154     ///
 155     /// Note that this function is pessimistic and may incorrectly return
 156     /// `false`.
 157     fn is_known_global(&self) -> bool {
 158         !self.has_type_flags(TypeFlags::HAS_POTENTIAL_FREE_LOCAL_NAMES)
 159     }
 160
 161     /// Indicates whether this value references only 'global'
 162     /// generic parameters that are the same regardless of what fn we are
 163     /// in. This is used for caching.
 164     fn is_global(&self, tcx: TyCtxt<'tcx>) -> bool {
 165         !self.definitely_has_type_flags(tcx, TypeFlags::HAS_KNOWN_FREE_LOCAL_NAMES)
 166     }
 167
 168     /// True if there are any late-bound regions
 169     fn has_late_bound_regions(&self) -> bool {
 170         self.has_type_flags(TypeFlags::HAS_RE_LATE_BOUND)
 171     }
 172
 173     /// Indicates whether this value still has parameters/placeholders/inference variables
 174     /// which could be replaced later, in a way that would change the results of `impl`
 175     /// specialization.
 176     fn still_further_specializable(&self) -> bool {
 177         self.has_type_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE)
 178     }
 179 }
 180
 181 impl TypeFoldable<'tcx> for hir::Constness {
 182     fn super_fold_with<F: TypeFolder<'tcx>>(self, _: &mut F) -> Result<Self, F::Error> {
 183         Ok(self)
 184     }
 185     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _: &mut V) -> ControlFlow<V::BreakTy> {
 186         ControlFlow::CONTINUE
 187     }
 188 }
 189
 190 /// The `TypeFolder` trait defines the actual *folding*. There is a
 191 /// method defined for every foldable type. Each of these has a
 192 /// default implementation that does an "identity" fold. Within each
 193 /// identity fold, it should invoke `foo.fold_with(self)` to fold each
 194 /// sub-item.
 195 pub trait TypeFolder<'tcx>: Sized {
 196     type Error = !;
 197
 198     fn tcx<'a>(&'a self) -> TyCtxt<'tcx>;
 199
 200     fn fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, Self::Error>
 201     where
 202         T: TypeFoldable<'tcx>,
 203     {
 204         t.super_fold_with(self)
 205     }
 206
 207     fn fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 208         t.super_fold_with(self)
 209     }
 210
 211     fn fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 212         r.super_fold_with(self)
 213     }
 214
 215     fn fold_const(
 216         &mut self,
 217         c: &'tcx ty::Const<'tcx>,
 218     ) -> Result<&'tcx ty::Const<'tcx>, Self::Error> {
 219         c.super_fold_with(self)
 220     }
 221
 222     fn fold_predicate(
 223         &mut self,
 224         p: ty::Predicate<'tcx>,
 225     ) -> Result<ty::Predicate<'tcx>, Self::Error> {
 226         p.super_fold_with(self)
 227     }
 228
 229     fn fold_mir_const(
 230         &mut self,
 231         c: mir::ConstantKind<'tcx>,
 232     ) -> Result<mir::ConstantKind<'tcx>, Self::Error> {
 233         bug!("most type folders should not be folding MIR datastructures: {:?}", c)
 234     }
 235 }
 236
 237 pub trait TypeVisitor<'tcx>: Sized {
 238     type BreakTy = !;
 239     /// Supplies the `tcx` for an unevaluated anonymous constant in case its default substs
 240     /// are not yet supplied.
 241     ///
 242     /// Returning `None` for this method is only recommended if the `TypeVisitor`
 243     /// does not care about default anon const substs, as it ignores generic parameters,
 244     /// and fetching the default substs would cause a query cycle.
 245     ///
 246     /// For visitors which return `None` we completely skip the default substs in `ty::Unevaluated::super_visit_with`.
 247     /// This means that incorrectly returning `None` can very quickly lead to ICE or other critical bugs, so be careful and
 248     /// try to return an actual `tcx` if possible.
 249     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>>;
 250
 251     fn visit_binder<T: TypeFoldable<'tcx>>(
 252         &mut self,
 253         t: &Binder<'tcx, T>,
 254     ) -> ControlFlow<Self::BreakTy> {
 255         t.super_visit_with(self)
 256     }
 257
 258     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 259         t.super_visit_with(self)
 260     }
 261
 262     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 263         r.super_visit_with(self)
 264     }
 265
 266     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 267         c.super_visit_with(self)
 268     }
 269
 270     fn visit_unevaluated_const(&mut self, uv: ty::Unevaluated<'tcx>) -> ControlFlow<Self::BreakTy> {
 271         uv.super_visit_with(self)
 272     }
 273
 274     fn visit_predicate(&mut self, p: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
 275         p.super_visit_with(self)
 276     }
 277 }
 278
 279 ///////////////////////////////////////////////////////////////////////////
 280 // Some sample folders
 281
 282 pub struct BottomUpFolder<'tcx, F, G, H>
 283 where
 284     F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 285     G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
 286     H: FnMut(&'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx>,
 287 {
 288     pub tcx: TyCtxt<'tcx>,
 289     pub ty_op: F,
 290     pub lt_op: G,
 291     pub ct_op: H,
 292 }
 293
 294 impl<'tcx, F, G, H> TypeFolder<'tcx> for BottomUpFolder<'tcx, F, G, H>
 295 where
 296     F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 297     G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
 298     H: FnMut(&'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx>,
 299 {
 300     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 301         self.tcx
 302     }
 303
 304     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 305         let t = ty.super_fold_with(self)?;
 306         Ok((self.ty_op)(t))
 307     }
 308
 309     fn fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 310         let r = r.super_fold_with(self)?;
 311         Ok((self.lt_op)(r))
 312     }
 313
 314     fn fold_const(
 315         &mut self,
 316         ct: &'tcx ty::Const<'tcx>,
 317     ) -> Result<&'tcx ty::Const<'tcx>, Self::Error> {
 318         let ct = ct.super_fold_with(self)?;
 319         Ok((self.ct_op)(ct))
 320     }
 321 }
 322
 323 ///////////////////////////////////////////////////////////////////////////
 324 // Region folder
 325
 326 impl<'tcx> TyCtxt<'tcx> {
 327     /// Folds the escaping and free regions in `value` using `f`, and
 328     /// sets `skipped_regions` to true if any late-bound region was found
 329     /// and skipped.
 330     pub fn fold_regions<T>(
 331         self,
 332         value: T,
 333         skipped_regions: &mut bool,
 334         mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
 335     ) -> T
 336     where
 337         T: TypeFoldable<'tcx>,
 338     {
 339         value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f)).into_ok()
 340     }
 341
 342     /// Invoke `callback` on every region appearing free in `value`.
 343     pub fn for_each_free_region(
 344         self,
 345         value: &impl TypeFoldable<'tcx>,
 346         mut callback: impl FnMut(ty::Region<'tcx>),
 347     ) {
 348         self.any_free_region_meets(value, |r| {
 349             callback(r);
 350             false
 351         });
 352     }
 353
 354     /// Returns `true` if `callback` returns true for every region appearing free in `value`.
 355     pub fn all_free_regions_meet(
 356         self,
 357         value: &impl TypeFoldable<'tcx>,
 358         mut callback: impl FnMut(ty::Region<'tcx>) -> bool,
 359     ) -> bool {
 360         !self.any_free_region_meets(value, |r| !callback(r))
 361     }
 362
 363     /// Returns `true` if `callback` returns true for some region appearing free in `value`.
 364     pub fn any_free_region_meets(
 365         self,
 366         value: &impl TypeFoldable<'tcx>,
 367         callback: impl FnMut(ty::Region<'tcx>) -> bool,
 368     ) -> bool {
 369         struct RegionVisitor<'tcx, F> {
 370             tcx: TyCtxt<'tcx>,
 371             /// The index of a binder *just outside* the things we have
 372             /// traversed. If we encounter a bound region bound by this
 373             /// binder or one outer to it, it appears free. Example:
 374             ///
 375             /// ```
 376             ///    for<'a> fn(for<'b> fn(), T)
 377             /// ^          ^          ^     ^
 378             /// |          |          |     | here, would be shifted in 1
 379             /// |          |          | here, would be shifted in 2
 380             /// |          | here, would be `INNERMOST` shifted in by 1
 381             /// | here, initially, binder would be `INNERMOST`
 382             /// ```
 383             ///
 384             /// You see that, initially, *any* bound value is free,
 385             /// because we've not traversed any binders. As we pass
 386             /// through a binder, we shift the `outer_index` by 1 to
 387             /// account for the new binder that encloses us.
 388             outer_index: ty::DebruijnIndex,
 389             callback: F,
 390         }
 391
 392         impl<'tcx, F> TypeVisitor<'tcx> for RegionVisitor<'tcx, F>
 393         where
 394             F: FnMut(ty::Region<'tcx>) -> bool,
 395         {
 396             type BreakTy = ();
 397
 398             fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 399                 Some(self.tcx)
 400             }
 401
 402             fn visit_binder<T: TypeFoldable<'tcx>>(
 403                 &mut self,
 404                 t: &Binder<'tcx, T>,
 405             ) -> ControlFlow<Self::BreakTy> {
 406                 self.outer_index.shift_in(1);
 407                 let result = t.as_ref().skip_binder().visit_with(self);
 408                 self.outer_index.shift_out(1);
 409                 result
 410             }
 411
 412             fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 413                 match *r {
 414                     ty::ReLateBound(debruijn, _) if debruijn < self.outer_index => {
 415                         ControlFlow::CONTINUE
 416                     }
 417                     _ => {
 418                         if (self.callback)(r) {
 419                             ControlFlow::BREAK
 420                         } else {
 421                             ControlFlow::CONTINUE
 422                         }
 423                     }
 424                 }
 425             }
 426
 427             fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 428                 // We're only interested in types involving regions
 429                 if ty.flags().intersects(TypeFlags::HAS_POTENTIAL_FREE_REGIONS) {
 430                     ty.super_visit_with(self)
 431                 } else {
 432                     ControlFlow::CONTINUE
 433                 }
 434             }
 435         }
 436
 437         value
 438             .visit_with(&mut RegionVisitor { tcx: self, outer_index: ty::INNERMOST, callback })
 439             .is_break()
 440     }
 441 }
 442
 443 /// Folds over the substructure of a type, visiting its component
 444 /// types and all regions that occur *free* within it.
 445 ///
 446 /// That is, `Ty` can contain function or method types that bind
 447 /// regions at the call site (`ReLateBound`), and occurrences of
 448 /// regions (aka "lifetimes") that are bound within a type are not
 449 /// visited by this folder; only regions that occur free will be
 450 /// visited by `fld_r`.
 451
 452 pub struct RegionFolder<'a, 'tcx> {
 453     tcx: TyCtxt<'tcx>,
 454     skipped_regions: &'a mut bool,
 455
 456     /// Stores the index of a binder *just outside* the stuff we have
 457     /// visited.  So this begins as INNERMOST; when we pass through a
 458     /// binder, it is incremented (via `shift_in`).
 459     current_index: ty::DebruijnIndex,
 460
 461     /// Callback invokes for each free region. The `DebruijnIndex`
 462     /// points to the binder *just outside* the ones we have passed
 463     /// through.
 464     fold_region_fn:
 465         &'a mut (dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx> + 'a),
 466 }
 467
 468 impl<'a, 'tcx> RegionFolder<'a, 'tcx> {
 469     #[inline]
 470     pub fn new(
 471         tcx: TyCtxt<'tcx>,
 472         skipped_regions: &'a mut bool,
 473         fold_region_fn: &'a mut dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
 474     ) -> RegionFolder<'a, 'tcx> {
 475         RegionFolder { tcx, skipped_regions, current_index: ty::INNERMOST, fold_region_fn }
 476     }
 477 }
 478
 479 impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx> {
 480     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 481         self.tcx
 482     }
 483
 484     fn fold_binder<T: TypeFoldable<'tcx>>(
 485         &mut self,
 486         t: ty::Binder<'tcx, T>,
 487     ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
 488         self.current_index.shift_in(1);
 489         let t = t.super_fold_with(self);
 490         self.current_index.shift_out(1);
 491         t
 492     }
 493
 494     #[instrument(skip(self), level = "debug")]
 495     fn fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 496         match *r {
 497             ty::ReLateBound(debruijn, _) if debruijn < self.current_index => {
 498                 debug!(?self.current_index, "skipped bound region");
 499                 *self.skipped_regions = true;
 500                 Ok(r)
 501             }
 502             _ => {
 503                 debug!(?self.current_index, "folding free region");
 504                 Ok((self.fold_region_fn)(r, self.current_index))
 505             }
 506         }
 507     }
 508 }
 509
 510 ///////////////////////////////////////////////////////////////////////////
 511 // Bound vars replacer
 512
 513 /// Replaces the escaping bound vars (late bound regions or bound types) in a type.
 514 struct BoundVarReplacer<'a, 'tcx> {
 515     tcx: TyCtxt<'tcx>,
 516
 517     /// As with `RegionFolder`, represents the index of a binder *just outside*
 518     /// the ones we have visited.
 519     current_index: ty::DebruijnIndex,
 520
 521     fld_r: Option<&'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a)>,
 522     fld_t: Option<&'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a)>,
 523     fld_c: Option<&'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx> + 'a)>,
 524 }
 525
 526 impl<'a, 'tcx> BoundVarReplacer<'a, 'tcx> {
 527     fn new(
 528         tcx: TyCtxt<'tcx>,
 529         fld_r: Option<&'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a)>,
 530         fld_t: Option<&'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a)>,
 531         fld_c: Option<&'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx> + 'a)>,
 532     ) -> Self {
 533         BoundVarReplacer { tcx, current_index: ty::INNERMOST, fld_r, fld_t, fld_c }
 534     }
 535 }
 536
 537 impl<'a, 'tcx> TypeFolder<'tcx> for BoundVarReplacer<'a, 'tcx> {
 538     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 539         self.tcx
 540     }
 541
 542     fn fold_binder<T: TypeFoldable<'tcx>>(
 543         &mut self,
 544         t: ty::Binder<'tcx, T>,
 545     ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
 546         self.current_index.shift_in(1);
 547         let t = t.super_fold_with(self);
 548         self.current_index.shift_out(1);
 549         t
 550     }
 551
 552     fn fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 553         match *t.kind() {
 554             ty::Bound(debruijn, bound_ty) if debruijn == self.current_index => {
 555                 if let Some(fld_t) = self.fld_t.as_mut() {
 556                     let ty = fld_t(bound_ty);
 557                     return Ok(ty::fold::shift_vars(self.tcx, &ty, self.current_index.as_u32()));
 558                 }
 559             }
 560             _ if t.has_vars_bound_at_or_above(self.current_index) => {
 561                 return t.super_fold_with(self);
 562             }
 563             _ => {}
 564         }
 565         Ok(t)
 566     }
 567
 568     fn fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 569         match *r {
 570             ty::ReLateBound(debruijn, br) if debruijn == self.current_index => {
 571                 if let Some(fld_r) = self.fld_r.as_mut() {
 572                     let region = fld_r(br);
 573                     return if let ty::ReLateBound(debruijn1, br) = *region {
 574                         // If the callback returns a late-bound region,
 575                         // that region should always use the INNERMOST
 576                         // debruijn index. Then we adjust it to the
 577                         // correct depth.
 578                         assert_eq!(debruijn1, ty::INNERMOST);
 579                         Ok(self.tcx.mk_region(ty::ReLateBound(debruijn, br)))
 580                     } else {
 581                         Ok(region)
 582                     };
 583                 }
 584             }
 585             _ => {}
 586         }
 587         Ok(r)
 588     }
 589
 590     fn fold_const(
 591         &mut self,
 592         ct: &'tcx ty::Const<'tcx>,
 593     ) -> Result<&'tcx ty::Const<'tcx>, Self::Error> {
 594         match *ct {
 595             ty::Const { val: ty::ConstKind::Bound(debruijn, bound_const), ty }
 596                 if debruijn == self.current_index =>
 597             {
 598                 if let Some(fld_c) = self.fld_c.as_mut() {
 599                     let ct = fld_c(bound_const, ty);
 600                     return Ok(ty::fold::shift_vars(self.tcx, &ct, self.current_index.as_u32()));
 601                 }
 602             }
 603             _ if ct.has_vars_bound_at_or_above(self.current_index) => {
 604                 return ct.super_fold_with(self);
 605             }
 606             _ => {}
 607         }
 608         Ok(ct)
 609     }
 610 }
 611
 612 impl<'tcx> TyCtxt<'tcx> {
 613     /// Replaces all regions bound by the given `Binder` with the
 614     /// results returned by the closure; the closure is expected to
 615     /// return a free region (relative to this binder), and hence the
 616     /// binder is removed in the return type. The closure is invoked
 617     /// once for each unique `BoundRegionKind`; multiple references to the
 618     /// same `BoundRegionKind` will reuse the previous result. A map is
 619     /// returned at the end with each bound region and the free region
 620     /// that replaced it.
 621     ///
 622     /// This method only replaces late bound regions and the result may still
 623     /// contain escaping bound types.
 624     pub fn replace_late_bound_regions<T, F>(
 625         self,
 626         value: Binder<'tcx, T>,
 627         mut fld_r: F,
 628     ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
 629     where
 630         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 631         T: TypeFoldable<'tcx>,
 632     {
 633         let mut region_map = BTreeMap::new();
 634         let mut real_fld_r =
 635             |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br));
 636         let value = value.skip_binder();
 637         let value = if !value.has_escaping_bound_vars() {
 638             value
 639         } else {
 640             let mut replacer = BoundVarReplacer::new(self, Some(&mut real_fld_r), None, None);
 641             value.fold_with(&mut replacer).into_ok()
 642         };
 643         (value, region_map)
 644     }
 645
 646     /// Replaces all escaping bound vars. The `fld_r` closure replaces escaping
 647     /// bound regions; the `fld_t` closure replaces escaping bound types and the `fld_c`
 648     /// closure replaces escaping bound consts.
 649     pub fn replace_escaping_bound_vars<T, F, G, H>(
 650         self,
 651         value: T,
 652         mut fld_r: F,
 653         mut fld_t: G,
 654         mut fld_c: H,
 655     ) -> T
 656     where
 657         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 658         G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 659         H: FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx>,
 660         T: TypeFoldable<'tcx>,
 661     {
 662         if !value.has_escaping_bound_vars() {
 663             value
 664         } else {
 665             let mut replacer =
 666                 BoundVarReplacer::new(self, Some(&mut fld_r), Some(&mut fld_t), Some(&mut fld_c));
 667             value.fold_with(&mut replacer).into_ok()
 668         }
 669     }
 670
 671     /// Replaces all types or regions bound by the given `Binder`. The `fld_r`
 672     /// closure replaces bound regions while the `fld_t` closure replaces bound
 673     /// types.
 674     pub fn replace_bound_vars<T, F, G, H>(
 675         self,
 676         value: Binder<'tcx, T>,
 677         mut fld_r: F,
 678         fld_t: G,
 679         fld_c: H,
 680     ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
 681     where
 682         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 683         G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 684         H: FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx>,
 685         T: TypeFoldable<'tcx>,
 686     {
 687         let mut region_map = BTreeMap::new();
 688         let real_fld_r = |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br));
 689         let value = self.replace_escaping_bound_vars(value.skip_binder(), real_fld_r, fld_t, fld_c);
 690         (value, region_map)
 691     }
 692
 693     /// Replaces any late-bound regions bound in `value` with
 694     /// free variants attached to `all_outlive_scope`.
 695     pub fn liberate_late_bound_regions<T>(
 696         self,
 697         all_outlive_scope: DefId,
 698         value: ty::Binder<'tcx, T>,
 699     ) -> T
 700     where
 701         T: TypeFoldable<'tcx>,
 702     {
 703         self.replace_late_bound_regions(value, |br| {
 704             self.mk_region(ty::ReFree(ty::FreeRegion {
 705                 scope: all_outlive_scope,
 706                 bound_region: br.kind,
 707             }))
 708         })
 709         .0
 710     }
 711
 712     pub fn shift_bound_var_indices<T>(self, bound_vars: usize, value: T) -> T
 713     where
 714         T: TypeFoldable<'tcx>,
 715     {
 716         self.replace_escaping_bound_vars(
 717             value,
 718             |r| {
 719                 self.mk_region(ty::ReLateBound(
 720                     ty::INNERMOST,
 721                     ty::BoundRegion {
 722                         var: ty::BoundVar::from_usize(r.var.as_usize() + bound_vars),
 723                         kind: r.kind,
 724                     },
 725                 ))
 726             },
 727             |t| {
 728                 self.mk_ty(ty::Bound(
 729                     ty::INNERMOST,
 730                     ty::BoundTy {
 731                         var: ty::BoundVar::from_usize(t.var.as_usize() + bound_vars),
 732                         kind: t.kind,
 733                     },
 734                 ))
 735             },
 736             |c, ty| {
 737                 self.mk_const(ty::Const {
 738                     val: ty::ConstKind::Bound(
 739                         ty::INNERMOST,
 740                         ty::BoundVar::from_usize(c.as_usize() + bound_vars),
 741                     ),
 742                     ty,
 743                 })
 744             },
 745         )
 746     }
 747
 748     /// Returns a set of all late-bound regions that are constrained
 749     /// by `value`, meaning that if we instantiate those LBR with
 750     /// variables and equate `value` with something else, those
 751     /// variables will also be equated.
 752     pub fn collect_constrained_late_bound_regions<T>(
 753         self,
 754         value: &Binder<'tcx, T>,
 755     ) -> FxHashSet<ty::BoundRegionKind>
 756     where
 757         T: TypeFoldable<'tcx>,
 758     {
 759         self.collect_late_bound_regions(value, true)
 760     }
 761
 762     /// Returns a set of all late-bound regions that appear in `value` anywhere.
 763     pub fn collect_referenced_late_bound_regions<T>(
 764         self,
 765         value: &Binder<'tcx, T>,
 766     ) -> FxHashSet<ty::BoundRegionKind>
 767     where
 768         T: TypeFoldable<'tcx>,
 769     {
 770         self.collect_late_bound_regions(value, false)
 771     }
 772
 773     fn collect_late_bound_regions<T>(
 774         self,
 775         value: &Binder<'tcx, T>,
 776         just_constraint: bool,
 777     ) -> FxHashSet<ty::BoundRegionKind>
 778     where
 779         T: TypeFoldable<'tcx>,
 780     {
 781         let mut collector = LateBoundRegionsCollector::new(self, just_constraint);
 782         let result = value.as_ref().skip_binder().visit_with(&mut collector);
 783         assert!(result.is_continue()); // should never have stopped early
 784         collector.regions
 785     }
 786
 787     /// Replaces any late-bound regions bound in `value` with `'erased`. Useful in codegen but also
 788     /// method lookup and a few other places where precise region relationships are not required.
 789     pub fn erase_late_bound_regions<T>(self, value: Binder<'tcx, T>) -> T
 790     where
 791         T: TypeFoldable<'tcx>,
 792     {
 793         self.replace_late_bound_regions(value, |_| self.lifetimes.re_erased).0
 794     }
 795
 796     /// Rewrite any late-bound regions so that they are anonymous. Region numbers are
 797     /// assigned starting at 0 and increasing monotonically in the order traversed
 798     /// by the fold operation.
 799     ///
 800     /// The chief purpose of this function is to canonicalize regions so that two
 801     /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become
 802     /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and
 803     /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization.
 804     pub fn anonymize_late_bound_regions<T>(self, sig: Binder<'tcx, T>) -> Binder<'tcx, T>
 805     where
 806         T: TypeFoldable<'tcx>,
 807     {
 808         let mut counter = 0;
 809         let inner = self
 810             .replace_late_bound_regions(sig, |_| {
 811                 let br = ty::BoundRegion {
 812                     var: ty::BoundVar::from_u32(counter),
 813                     kind: ty::BrAnon(counter),
 814                 };
 815                 let r = self.mk_region(ty::ReLateBound(ty::INNERMOST, br));
 816                 counter += 1;
 817                 r
 818             })
 819             .0;
 820         let bound_vars = self.mk_bound_variable_kinds(
 821             (0..counter).map(|i| ty::BoundVariableKind::Region(ty::BrAnon(i))),
 822         );
 823         Binder::bind_with_vars(inner, bound_vars)
 824     }
 825 }
 826
 827 pub struct ValidateBoundVars<'tcx> {
 828     bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
 829     binder_index: ty::DebruijnIndex,
 830     // We may encounter the same variable at different levels of binding, so
 831     // this can't just be `Ty`
 832     visited: SsoHashSet<(ty::DebruijnIndex, Ty<'tcx>)>,
 833 }
 834
 835 impl<'tcx> ValidateBoundVars<'tcx> {
 836     pub fn new(bound_vars: &'tcx ty::List<ty::BoundVariableKind>) -> Self {
 837         ValidateBoundVars {
 838             bound_vars,
 839             binder_index: ty::INNERMOST,
 840             visited: SsoHashSet::default(),
 841         }
 842     }
 843 }
 844
 845 impl<'tcx> TypeVisitor<'tcx> for ValidateBoundVars<'tcx> {
 846     type BreakTy = ();
 847
 848     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 849         // Anonymous constants do not contain bound vars in their substs by default.
 850         None
 851     }
 852
 853     fn visit_binder<T: TypeFoldable<'tcx>>(
 854         &mut self,
 855         t: &Binder<'tcx, T>,
 856     ) -> ControlFlow<Self::BreakTy> {
 857         self.binder_index.shift_in(1);
 858         let result = t.super_visit_with(self);
 859         self.binder_index.shift_out(1);
 860         result
 861     }
 862
 863     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 864         if t.outer_exclusive_binder < self.binder_index
 865             || !self.visited.insert((self.binder_index, t))
 866         {
 867             return ControlFlow::BREAK;
 868         }
 869         match *t.kind() {
 870             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
 871                 if self.bound_vars.len() <= bound_ty.var.as_usize() {
 872                     bug!("Not enough bound vars: {:?} not found in {:?}", t, self.bound_vars);
 873                 }
 874                 let list_var = self.bound_vars[bound_ty.var.as_usize()];
 875                 match list_var {
 876                     ty::BoundVariableKind::Ty(kind) => {
 877                         if kind != bound_ty.kind {
 878                             bug!(
 879                                 "Mismatched type kinds: {:?} doesn't var in list {:?}",
 880                                 bound_ty.kind,
 881                                 list_var
 882                             );
 883                         }
 884                     }
 885                     _ => {
 886                         bug!("Mismatched bound variable kinds! Expected type, found {:?}", list_var)
 887                     }
 888                 }
 889             }
 890
 891             _ => (),
 892         };
 893
 894         t.super_visit_with(self)
 895     }
 896
 897     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 898         match r {
 899             ty::ReLateBound(index, br) if *index == self.binder_index => {
 900                 if self.bound_vars.len() <= br.var.as_usize() {
 901                     bug!("Not enough bound vars: {:?} not found in {:?}", *br, self.bound_vars);
 902                 }
 903                 let list_var = self.bound_vars[br.var.as_usize()];
 904                 match list_var {
 905                     ty::BoundVariableKind::Region(kind) => {
 906                         if kind != br.kind {
 907                             bug!(
 908                                 "Mismatched region kinds: {:?} doesn't match var ({:?}) in list ({:?})",
 909                                 br.kind,
 910                                 list_var,
 911                                 self.bound_vars
 912                             );
 913                         }
 914                     }
 915                     _ => bug!(
 916                         "Mismatched bound variable kinds! Expected region, found {:?}",
 917                         list_var
 918                     ),
 919                 }
 920             }
 921
 922             _ => (),
 923         };
 924
 925         r.super_visit_with(self)
 926     }
 927 }
 928
 929 ///////////////////////////////////////////////////////////////////////////
 930 // Shifter
 931 //
 932 // Shifts the De Bruijn indices on all escaping bound vars by a
 933 // fixed amount. Useful in substitution or when otherwise introducing
 934 // a binding level that is not intended to capture the existing bound
 935 // vars. See comment on `shift_vars_through_binders` method in
 936 // `subst.rs` for more details.
 937
 938 struct Shifter<'tcx> {
 939     tcx: TyCtxt<'tcx>,
 940     current_index: ty::DebruijnIndex,
 941     amount: u32,
 942 }
 943
 944 impl Shifter<'tcx> {
 945     pub fn new(tcx: TyCtxt<'tcx>, amount: u32) -> Self {
 946         Shifter { tcx, current_index: ty::INNERMOST, amount }
 947     }
 948 }
 949
 950 impl TypeFolder<'tcx> for Shifter<'tcx> {
 951     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 952         self.tcx
 953     }
 954
 955     fn fold_binder<T: TypeFoldable<'tcx>>(
 956         &mut self,
 957         t: ty::Binder<'tcx, T>,
 958     ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
 959         self.current_index.shift_in(1);
 960         let t = t.super_fold_with(self);
 961         self.current_index.shift_out(1);
 962         t
 963     }
 964
 965     fn fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 966         match *r {
 967             ty::ReLateBound(debruijn, br) => {
 968                 if self.amount == 0 || debruijn < self.current_index {
 969                     Ok(r)
 970                 } else {
 971                     let debruijn = debruijn.shifted_in(self.amount);
 972                     let shifted = ty::ReLateBound(debruijn, br);
 973                     Ok(self.tcx.mk_region(shifted))
 974                 }
 975             }
 976             _ => Ok(r),
 977         }
 978     }
 979
 980     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 981         match *ty.kind() {
 982             ty::Bound(debruijn, bound_ty) => {
 983                 if self.amount == 0 || debruijn < self.current_index {
 984                     Ok(ty)
 985                 } else {
 986                     let debruijn = debruijn.shifted_in(self.amount);
 987                     Ok(self.tcx.mk_ty(ty::Bound(debruijn, bound_ty)))
 988                 }
 989             }
 990
 991             _ => ty.super_fold_with(self),
 992         }
 993     }
 994
 995     fn fold_const(
 996         &mut self,
 997         ct: &'tcx ty::Const<'tcx>,
 998     ) -> Result<&'tcx ty::Const<'tcx>, Self::Error> {
 999         if let ty::Const { val: ty::ConstKind::Bound(debruijn, bound_ct), ty } = *ct {
1000             if self.amount == 0 || debruijn < self.current_index {
1001                 Ok(ct)
1002             } else {
1003                 let debruijn = debruijn.shifted_in(self.amount);
1004                 Ok(self
1005                     .tcx
1006                     .mk_const(ty::Const { val: ty::ConstKind::Bound(debruijn, bound_ct), ty }))
1007             }
1008         } else {
1009             ct.super_fold_with(self)
1010         }
1011     }
1012 }
1013
1014 pub fn shift_region<'tcx>(
1015     tcx: TyCtxt<'tcx>,
1016     region: ty::Region<'tcx>,
1017     amount: u32,
1018 ) -> ty::Region<'tcx> {
1019     match region {
1020         ty::ReLateBound(debruijn, br) if amount > 0 => {
1021             tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), *br))
1022         }
1023         _ => region,
1024     }
1025 }
1026
1027 pub fn shift_vars<'tcx, T>(tcx: TyCtxt<'tcx>, value: T, amount: u32) -> T
1028 where
1029     T: TypeFoldable<'tcx>,
1030 {
1031     debug!("shift_vars(value={:?}, amount={})", value, amount);
1032
1033     value.fold_with(&mut Shifter::new(tcx, amount)).into_ok()
1034 }
1035
1036 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
1037 struct FoundEscapingVars;
1038
1039 /// An "escaping var" is a bound var whose binder is not part of `t`. A bound var can be a
1040 /// bound region or a bound type.
1041 ///
1042 /// So, for example, consider a type like the following, which has two binders:
1043 ///
1044 ///    for<'a> fn(x: for<'b> fn(&'a isize, &'b isize))
1045 ///    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope
1046 ///                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~  inner scope
1047 ///
1048 /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the
1049 /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner
1050 /// fn type*, that type has an escaping region: `'a`.
1051 ///
1052 /// Note that what I'm calling an "escaping var" is often just called a "free var". However,
1053 /// we already use the term "free var". It refers to the regions or types that we use to represent
1054 /// bound regions or type params on a fn definition while we are type checking its body.
1055 ///
1056 /// To clarify, conceptually there is no particular difference between
1057 /// an "escaping" var and a "free" var. However, there is a big
1058 /// difference in practice. Basically, when "entering" a binding
1059 /// level, one is generally required to do some sort of processing to
1060 /// a bound var, such as replacing it with a fresh/placeholder
1061 /// var, or making an entry in the environment to represent the
1062 /// scope to which it is attached, etc. An escaping var represents
1063 /// a bound var for which this processing has not yet been done.
1064 struct HasEscapingVarsVisitor {
1065     /// Anything bound by `outer_index` or "above" is escaping.
1066     outer_index: ty::DebruijnIndex,
1067 }
1068
1069 impl<'tcx> TypeVisitor<'tcx> for HasEscapingVarsVisitor {
1070     type BreakTy = FoundEscapingVars;
1071
1072     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
1073         // Anonymous constants do not contain bound vars in their substs by default.
1074         None
1075     }
1076
1077     fn visit_binder<T: TypeFoldable<'tcx>>(
1078         &mut self,
1079         t: &Binder<'tcx, T>,
1080     ) -> ControlFlow<Self::BreakTy> {
1081         self.outer_index.shift_in(1);
1082         let result = t.super_visit_with(self);
1083         self.outer_index.shift_out(1);
1084         result
1085     }
1086
1087     #[inline]
1088     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
1089         // If the outer-exclusive-binder is *strictly greater* than
1090         // `outer_index`, that means that `t` contains some content
1091         // bound at `outer_index` or above (because
1092         // `outer_exclusive_binder` is always 1 higher than the
1093         // content in `t`). Therefore, `t` has some escaping vars.
1094         if t.outer_exclusive_binder > self.outer_index {
1095             ControlFlow::Break(FoundEscapingVars)
1096         } else {
1097             ControlFlow::CONTINUE
1098         }
1099     }
1100
1101     #[inline]
1102     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
1103         // If the region is bound by `outer_index` or anything outside
1104         // of outer index, then it escapes the binders we have
1105         // visited.
1106         if r.bound_at_or_above_binder(self.outer_index) {
1107             ControlFlow::Break(FoundEscapingVars)
1108         } else {
1109             ControlFlow::CONTINUE
1110         }
1111     }
1112
1113     fn visit_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
1114         // we don't have a `visit_infer_const` callback, so we have to
1115         // hook in here to catch this case (annoying...), but
1116         // otherwise we do want to remember to visit the rest of the
1117         // const, as it has types/regions embedded in a lot of other
1118         // places.
1119         match ct.val {
1120             ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => {
1121                 ControlFlow::Break(FoundEscapingVars)
1122             }
1123             _ => ct.super_visit_with(self),
1124         }
1125     }
1126
1127     #[inline]
1128     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
1129         if predicate.inner.outer_exclusive_binder > self.outer_index {
1130             ControlFlow::Break(FoundEscapingVars)
1131         } else {
1132             ControlFlow::CONTINUE
1133         }
1134     }
1135 }
1136
1137 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
1138 struct FoundFlags;
1139
1140 // FIXME: Optimize for checking for infer flags
1141 struct HasTypeFlagsVisitor<'tcx> {
1142     tcx: Option<TyCtxt<'tcx>>,
1143     flags: ty::TypeFlags,
1144 }
1145
1146 impl std::fmt::Debug for HasTypeFlagsVisitor<'tcx> {
1147     fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1148         self.flags.fmt(fmt)
1149     }
1150 }
1151
1152 impl<'tcx> TypeVisitor<'tcx> for HasTypeFlagsVisitor<'tcx> {
1153     type BreakTy = FoundFlags;
1154     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
1155         bug!("we shouldn't call this method as we manually look at ct substs");
1156     }
1157
1158     #[inline]
1159     #[instrument(level = "trace")]
1160     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
1161         let flags = t.flags();
1162         trace!(t.flags=?t.flags());
1163         if flags.intersects(self.flags) {
1164             ControlFlow::Break(FoundFlags)
1165         } else {
1166             match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1167                 true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, t),
1168                 _ => ControlFlow::CONTINUE,
1169             }
1170         }
1171     }
1172
1173     #[inline]
1174     #[instrument(skip(self), level = "trace")]
1175     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
1176         let flags = r.type_flags();
1177         trace!(r.flags=?flags);
1178         if flags.intersects(self.flags) {
1179             ControlFlow::Break(FoundFlags)
1180         } else {
1181             ControlFlow::CONTINUE
1182         }
1183     }
1184
1185     #[inline]
1186     #[instrument(level = "trace")]
1187     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
1188         let flags = FlagComputation::for_const(c);
1189         trace!(r.flags=?flags);
1190         if flags.intersects(self.flags) {
1191             ControlFlow::Break(FoundFlags)
1192         } else {
1193             match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1194                 true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, c),
1195                 _ => ControlFlow::CONTINUE,
1196             }
1197         }
1198     }
1199
1200     #[inline]
1201     #[instrument(level = "trace")]
1202     fn visit_unevaluated_const(&mut self, uv: ty::Unevaluated<'tcx>) -> ControlFlow<Self::BreakTy> {
1203         let flags = FlagComputation::for_unevaluated_const(uv);
1204         trace!(r.flags=?flags);
1205         if flags.intersects(self.flags) {
1206             ControlFlow::Break(FoundFlags)
1207         } else {
1208             match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1209                 true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, uv),
1210                 _ => ControlFlow::CONTINUE,
1211             }
1212         }
1213     }
1214
1215     #[inline]
1216     #[instrument(level = "trace")]
1217     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
1218         let flags = predicate.inner.flags;
1219         trace!(predicate.flags=?flags);
1220         if flags.intersects(self.flags) {
1221             ControlFlow::Break(FoundFlags)
1222         } else {
1223             match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1224                 true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, predicate),
1225                 _ => ControlFlow::CONTINUE,
1226             }
1227         }
1228     }
1229 }
1230
1231 struct UnknownConstSubstsVisitor<'tcx> {
1232     tcx: TyCtxt<'tcx>,
1233     flags: ty::TypeFlags,
1234 }
1235
1236 impl<'tcx> UnknownConstSubstsVisitor<'tcx> {
1237     /// This is fairly cold and we don't want to
1238     /// bloat the size of the `HasTypeFlagsVisitor`.
1239     #[inline(never)]
1240     pub fn search<T: TypeFoldable<'tcx>>(
1241         visitor: &HasTypeFlagsVisitor<'tcx>,
1242         v: T,
1243     ) -> ControlFlow<FoundFlags> {
1244         if visitor.flags.intersects(TypeFlags::MAY_NEED_DEFAULT_CONST_SUBSTS) {
1245             v.super_visit_with(&mut UnknownConstSubstsVisitor {
1246                 tcx: visitor.tcx.unwrap(),
1247                 flags: visitor.flags,
1248             })
1249         } else {
1250             ControlFlow::CONTINUE
1251         }
1252     }
1253 }
1254
1255 impl<'tcx> TypeVisitor<'tcx> for UnknownConstSubstsVisitor<'tcx> {
1256     type BreakTy = FoundFlags;
1257     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
1258         bug!("we shouldn't call this method as we manually look at ct substs");
1259     }
1260
1261     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
1262         if t.flags().intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1263             t.super_visit_with(self)
1264         } else {
1265             ControlFlow::CONTINUE
1266         }
1267     }
1268
1269     #[inline]
1270     fn visit_unevaluated_const(&mut self, uv: ty::Unevaluated<'tcx>) -> ControlFlow<Self::BreakTy> {
1271         if uv.substs_.is_none() {
1272             self.tcx
1273                 .default_anon_const_substs(uv.def.did)
1274                 .visit_with(&mut HasTypeFlagsVisitor { tcx: Some(self.tcx), flags: self.flags })
1275         } else {
1276             ControlFlow::CONTINUE
1277         }
1278     }
1279
1280     #[inline]
1281     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
1282         if predicate.inner.flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1283             predicate.super_visit_with(self)
1284         } else {
1285             ControlFlow::CONTINUE
1286         }
1287     }
1288 }
1289
1290 impl<'tcx> TyCtxt<'tcx> {
1291     /// This is a HACK(const_generics) and should probably not be needed.
1292     /// Might however be perf relevant, so who knows.
1293     ///
1294     /// FIXME(@lcnr): explain this function a bit more
1295     pub fn expose_default_const_substs<T: TypeFoldable<'tcx>>(self, v: T) -> T {
1296         v.fold_with(&mut ExposeDefaultConstSubstsFolder { tcx: self }).into_ok()
1297     }
1298 }
1299
1300 struct ExposeDefaultConstSubstsFolder<'tcx> {
1301     tcx: TyCtxt<'tcx>,
1302 }
1303
1304 impl<'tcx> TypeFolder<'tcx> for ExposeDefaultConstSubstsFolder<'tcx> {
1305     fn tcx(&self) -> TyCtxt<'tcx> {
1306         self.tcx
1307     }
1308
1309     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
1310         if ty.flags().intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1311             ty.super_fold_with(self)
1312         } else {
1313             Ok(ty)
1314         }
1315     }
1316
1317     fn fold_predicate(
1318         &mut self,
1319         pred: ty::Predicate<'tcx>,
1320     ) -> Result<ty::Predicate<'tcx>, Self::Error> {
1321         if pred.inner.flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1322             pred.super_fold_with(self)
1323         } else {
1324             Ok(pred)
1325         }
1326     }
1327 }
1328
1329 /// Collects all the late-bound regions at the innermost binding level
1330 /// into a hash set.
1331 struct LateBoundRegionsCollector<'tcx> {
1332     tcx: TyCtxt<'tcx>,
1333     current_index: ty::DebruijnIndex,
1334     regions: FxHashSet<ty::BoundRegionKind>,
1335
1336     /// `true` if we only want regions that are known to be
1337     /// "constrained" when you equate this type with another type. In
1338     /// particular, if you have e.g., `&'a u32` and `&'b u32`, equating
1339     /// them constraints `'a == 'b`. But if you have `<&'a u32 as
1340     /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those
1341     /// types may mean that `'a` and `'b` don't appear in the results,
1342     /// so they are not considered *constrained*.
1343     just_constrained: bool,
1344 }
1345
1346 impl LateBoundRegionsCollector<'tcx> {
1347     fn new(tcx: TyCtxt<'tcx>, just_constrained: bool) -> Self {
1348         LateBoundRegionsCollector {
1349             tcx,
1350             current_index: ty::INNERMOST,
1351             regions: Default::default(),
1352             just_constrained,
1353         }
1354     }
1355 }
1356
1357 impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector<'tcx> {
1358     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
1359         Some(self.tcx)
1360     }
1361
1362     fn visit_binder<T: TypeFoldable<'tcx>>(
1363         &mut self,
1364         t: &Binder<'tcx, T>,
1365     ) -> ControlFlow<Self::BreakTy> {
1366         self.current_index.shift_in(1);
1367         let result = t.super_visit_with(self);
1368         self.current_index.shift_out(1);
1369         result
1370     }
1371
1372     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
1373         // if we are only looking for "constrained" region, we have to
1374         // ignore the inputs to a projection, as they may not appear
1375         // in the normalized form
1376         if self.just_constrained {
1377             if let ty::Projection(..) | ty::Opaque(..) = t.kind() {
1378                 return ControlFlow::CONTINUE;
1379             }
1380         }
1381
1382         t.super_visit_with(self)
1383     }
1384
1385     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
1386         // if we are only looking for "constrained" region, we have to
1387         // ignore the inputs of an unevaluated const, as they may not appear
1388         // in the normalized form
1389         if self.just_constrained {
1390             if let ty::ConstKind::Unevaluated(..) = c.val {
1391                 return ControlFlow::CONTINUE;
1392             }
1393         }
1394
1395         c.super_visit_with(self)
1396     }
1397
1398     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
1399         if let ty::ReLateBound(debruijn, br) = *r {
1400             if debruijn == self.current_index {
1401                 self.regions.insert(br.kind);
1402             }
1403         }
1404         ControlFlow::CONTINUE
1405     }
1406 }