compiler/rustc_middle/src/ty/fold.rs

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