compiler/rustc_middle/src/ty/fold.rs

   1 //! A folding traversal mechanism for complex data structures that contain type
   2 //! information.
   3 //!
   4 //! This is a modifying traversal. It consumes the data structure, producing a
   5 //! (possibly) modified version of it. Both fallible and infallible versions are
   6 //! available. The name is potentially confusing, because this traversal is more
   7 //! like `Iterator::map` than `Iterator::fold`.
   8 //!
   9 //! This traversal has limited flexibility. Only a small number of "types of
  10 //! interest" within the complex data structures can receive custom
  11 //! modification. These are the ones containing the most important type-related
  12 //! information, such as `Ty`, `Predicate`, `Region`, and `Const`.
  13 //!
  14 //! There are three groups of traits involved in each traversal.
  15 //! - `TypeFoldable`. This is implemented once for many types, including:
  16 //!   - Types of interest, for which the the methods delegate to the
  17 //!     folder.
  18 //!   - All other types, including generic containers like `Vec` and `Option`.
  19 //!     It defines a "skeleton" of how they should be folded.
  20 //! - `TypeSuperFoldable`. This is implemented only for each type of interest,
  21 //!   and defines the folding "skeleton" for these types.
  22 //! - `TypeFolder`/`FallibleTypeFolder. One of these is implemented for each
  23 //!   folder. This defines how types of interest are folded.
  24 //!
  25 //! This means each fold is a mixture of (a) generic folding operations, and (b)
  26 //! custom fold operations that are specific to the folder.
  27 //! - The `TypeFoldable` impls handle most of the traversal, and call into
  28 //!   `TypeFolder`/`FallibleTypeFolder` when they encounter a type of interest.
  29 //! - A `TypeFolder`/`FallibleTypeFolder` may call into another `TypeFoldable`
  30 //!   impl, because some of the types of interest are recursive and can contain
  31 //!   other types of interest.
  32 //! - A `TypeFolder`/`FallibleTypeFolder` may also call into a `TypeSuperFoldable`
  33 //!   impl, because each folder might provide custom handling only for some types
  34 //!   of interest, or only for some variants of each type of interest, and then
  35 //!   use default traversal for the remaining cases.
  36 //!
  37 //! For example, if you have `struct S(Ty, U)` where `S: TypeFoldable` and `U:
  38 //! TypeFoldable`, and an instance `s = S(ty, u)`, it would be folded like so:
  39 //! ```text
  40 //! s.fold_with(folder) calls
  41 //! - ty.fold_with(folder) calls
  42 //!   - folder.fold_ty(ty) may call
  43 //!     - ty.super_fold_with(folder)
  44 //! - u.fold_with(folder)
  45 //! ```
  46 use crate::mir;
  47 use crate::ty::{self, Binder, Ty, TyCtxt, TypeVisitable};
  48 use rustc_hir::def_id::DefId;
  49
  50 use std::collections::BTreeMap;
  51
  52 /// This trait is implemented for every type that can be folded,
  53 /// providing the skeleton of the traversal.
  54 ///
  55 /// To implement this conveniently, use the derive macro located in
  56 /// `rustc_macros`.
  57 pub trait TypeFoldable<'tcx>: TypeVisitable<'tcx> {
  58     /// The entry point for folding. To fold a value `t` with a folder `f`
  59     /// call: `t.try_fold_with(f)`.
  60     ///
  61     /// For most types, this just traverses the value, calling `try_fold_with`
  62     /// on each field/element.
  63     ///
  64     /// For types of interest (such as `Ty`), the implementation of method
  65     /// calls a folder method specifically for that type (such as
  66     /// `F::try_fold_ty`). This is where control transfers from `TypeFoldable`
  67     /// to `TypeFolder`.
  68     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error>;
  69
  70     /// A convenient alternative to `try_fold_with` for use with infallible
  71     /// folders. Do not override this method, to ensure coherence with
  72     /// `try_fold_with`.
  73     fn fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
  74         self.try_fold_with(folder).into_ok()
  75     }
  76 }
  77
  78 // This trait is implemented for types of interest.
  79 pub trait TypeSuperFoldable<'tcx>: TypeFoldable<'tcx> {
  80     /// Provides a default fold for a type of interest. This should only be
  81     /// called within `TypeFolder` methods, when a non-custom traversal is
  82     /// desired for the value of the type of interest passed to that method.
  83     /// For example, in `MyFolder::try_fold_ty(ty)`, it is valid to call
  84     /// `ty.try_super_fold_with(self)`, but any other folding should be done
  85     /// with `xyz.try_fold_with(self)`.
  86     fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(
  87         self,
  88         folder: &mut F,
  89     ) -> Result<Self, F::Error>;
  90
  91     /// A convenient alternative to `try_super_fold_with` for use with
  92     /// infallible folders. Do not override this method, to ensure coherence
  93     /// with `try_super_fold_with`.
  94     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
  95         self.try_super_fold_with(folder).into_ok()
  96     }
  97 }
  98
  99 /// This trait is implemented for every infallible folding traversal. There is
 100 /// a fold method defined for every type of interest. Each such method has a
 101 /// default that does an "identity" fold. Implementations of these methods
 102 /// often fall back to a `super_fold_with` method if the primary argument
 103 /// doesn't satisfy a particular condition.
 104 ///
 105 /// A blanket implementation of [`FallibleTypeFolder`] will defer to
 106 /// the infallible methods of this trait to ensure that the two APIs
 107 /// are coherent.
 108 pub trait TypeFolder<'tcx>: FallibleTypeFolder<'tcx, Error = !> {
 109     fn tcx<'a>(&'a self) -> TyCtxt<'tcx>;
 110
 111     fn fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Binder<'tcx, T>
 112     where
 113         T: TypeFoldable<'tcx>,
 114     {
 115         t.super_fold_with(self)
 116     }
 117
 118     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 119         t.super_fold_with(self)
 120     }
 121
 122     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 123         r.super_fold_with(self)
 124     }
 125
 126     fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> {
 127         c.super_fold_with(self)
 128     }
 129
 130     fn fold_unevaluated(&mut self, uv: ty::Unevaluated<'tcx>) -> ty::Unevaluated<'tcx> {
 131         uv.super_fold_with(self)
 132     }
 133
 134     fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
 135         p.super_fold_with(self)
 136     }
 137
 138     fn fold_mir_const(&mut self, c: mir::ConstantKind<'tcx>) -> mir::ConstantKind<'tcx> {
 139         bug!("most type folders should not be folding MIR datastructures: {:?}", c)
 140     }
 141 }
 142
 143 /// This trait is implemented for every folding traversal. There is a fold
 144 /// method defined for every type of interest. Each such method has a default
 145 /// that does an "identity" fold.
 146 ///
 147 /// A blanket implementation of this trait (that defers to the relevant
 148 /// method of [`TypeFolder`]) is provided for all infallible folders in
 149 /// order to ensure the two APIs are coherent.
 150 pub trait FallibleTypeFolder<'tcx>: Sized {
 151     type Error;
 152
 153     fn tcx<'a>(&'a self) -> TyCtxt<'tcx>;
 154
 155     fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, Self::Error>
 156     where
 157         T: TypeFoldable<'tcx>,
 158     {
 159         t.try_super_fold_with(self)
 160     }
 161
 162     fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 163         t.try_super_fold_with(self)
 164     }
 165
 166     fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 167         r.try_super_fold_with(self)
 168     }
 169
 170     fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> {
 171         c.try_super_fold_with(self)
 172     }
 173
 174     fn try_fold_unevaluated(
 175         &mut self,
 176         c: ty::Unevaluated<'tcx>,
 177     ) -> Result<ty::Unevaluated<'tcx>, Self::Error> {
 178         c.try_super_fold_with(self)
 179     }
 180
 181     fn try_fold_predicate(
 182         &mut self,
 183         p: ty::Predicate<'tcx>,
 184     ) -> Result<ty::Predicate<'tcx>, Self::Error> {
 185         p.try_super_fold_with(self)
 186     }
 187
 188     fn try_fold_mir_const(
 189         &mut self,
 190         c: mir::ConstantKind<'tcx>,
 191     ) -> Result<mir::ConstantKind<'tcx>, Self::Error> {
 192         bug!("most type folders should not be folding MIR datastructures: {:?}", c)
 193     }
 194 }
 195
 196 // This blanket implementation of the fallible trait for infallible folders
 197 // delegates to infallible methods to ensure coherence.
 198 impl<'tcx, F> FallibleTypeFolder<'tcx> for F
 199 where
 200     F: TypeFolder<'tcx>,
 201 {
 202     type Error = !;
 203
 204     fn tcx<'a>(&'a self) -> TyCtxt<'tcx> {
 205         TypeFolder::tcx(self)
 206     }
 207
 208     fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, !>
 209     where
 210         T: TypeFoldable<'tcx>,
 211     {
 212         Ok(self.fold_binder(t))
 213     }
 214
 215     fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, !> {
 216         Ok(self.fold_ty(t))
 217     }
 218
 219     fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, !> {
 220         Ok(self.fold_region(r))
 221     }
 222
 223     fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, !> {
 224         Ok(self.fold_const(c))
 225     }
 226
 227     fn try_fold_unevaluated(
 228         &mut self,
 229         c: ty::Unevaluated<'tcx>,
 230     ) -> Result<ty::Unevaluated<'tcx>, !> {
 231         Ok(self.fold_unevaluated(c))
 232     }
 233
 234     fn try_fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> Result<ty::Predicate<'tcx>, !> {
 235         Ok(self.fold_predicate(p))
 236     }
 237
 238     fn try_fold_mir_const(
 239         &mut self,
 240         c: mir::ConstantKind<'tcx>,
 241     ) -> Result<mir::ConstantKind<'tcx>, !> {
 242         Ok(self.fold_mir_const(c))
 243     }
 244 }
 245
 246 ///////////////////////////////////////////////////////////////////////////
 247 // Some sample folders
 248
 249 pub struct BottomUpFolder<'tcx, F, G, H>
 250 where
 251     F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 252     G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
 253     H: FnMut(ty::Const<'tcx>) -> ty::Const<'tcx>,
 254 {
 255     pub tcx: TyCtxt<'tcx>,
 256     pub ty_op: F,
 257     pub lt_op: G,
 258     pub ct_op: H,
 259 }
 260
 261 impl<'tcx, F, G, H> TypeFolder<'tcx> for BottomUpFolder<'tcx, F, G, H>
 262 where
 263     F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 264     G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
 265     H: FnMut(ty::Const<'tcx>) -> ty::Const<'tcx>,
 266 {
 267     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 268         self.tcx
 269     }
 270
 271     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 272         let t = ty.super_fold_with(self);
 273         (self.ty_op)(t)
 274     }
 275
 276     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 277         let r = r.super_fold_with(self);
 278         (self.lt_op)(r)
 279     }
 280
 281     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 282         let ct = ct.super_fold_with(self);
 283         (self.ct_op)(ct)
 284     }
 285 }
 286
 287 ///////////////////////////////////////////////////////////////////////////
 288 // Region folder
 289
 290 impl<'tcx> TyCtxt<'tcx> {
 291     /// Folds the escaping and free regions in `value` using `f`, and
 292     /// sets `skipped_regions` to true if any late-bound region was found
 293     /// and skipped.
 294     pub fn fold_regions<T>(
 295         self,
 296         value: T,
 297         mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
 298     ) -> T
 299     where
 300         T: TypeFoldable<'tcx>,
 301     {
 302         value.fold_with(&mut RegionFolder::new(self, &mut f))
 303     }
 304 }
 305
 306 /// Folds over the substructure of a type, visiting its component
 307 /// types and all regions that occur *free* within it.
 308 ///
 309 /// That is, `Ty` can contain function or method types that bind
 310 /// regions at the call site (`ReLateBound`), and occurrences of
 311 /// regions (aka "lifetimes") that are bound within a type are not
 312 /// visited by this folder; only regions that occur free will be
 313 /// visited by `fld_r`.
 314
 315 pub struct RegionFolder<'a, 'tcx> {
 316     tcx: TyCtxt<'tcx>,
 317
 318     /// Stores the index of a binder *just outside* the stuff we have
 319     /// visited.  So this begins as INNERMOST; when we pass through a
 320     /// binder, it is incremented (via `shift_in`).
 321     current_index: ty::DebruijnIndex,
 322
 323     /// Callback invokes for each free region. The `DebruijnIndex`
 324     /// points to the binder *just outside* the ones we have passed
 325     /// through.
 326     fold_region_fn:
 327         &'a mut (dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx> + 'a),
 328 }
 329
 330 impl<'a, 'tcx> RegionFolder<'a, 'tcx> {
 331     #[inline]
 332     pub fn new(
 333         tcx: TyCtxt<'tcx>,
 334         fold_region_fn: &'a mut dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
 335     ) -> RegionFolder<'a, 'tcx> {
 336         RegionFolder { tcx, current_index: ty::INNERMOST, fold_region_fn }
 337     }
 338 }
 339
 340 impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx> {
 341     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 342         self.tcx
 343     }
 344
 345     fn fold_binder<T: TypeFoldable<'tcx>>(
 346         &mut self,
 347         t: ty::Binder<'tcx, T>,
 348     ) -> ty::Binder<'tcx, T> {
 349         self.current_index.shift_in(1);
 350         let t = t.super_fold_with(self);
 351         self.current_index.shift_out(1);
 352         t
 353     }
 354
 355     #[instrument(skip(self), level = "debug")]
 356     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 357         match *r {
 358             ty::ReLateBound(debruijn, _) if debruijn < self.current_index => {
 359                 debug!(?self.current_index, "skipped bound region");
 360                 r
 361             }
 362             _ => {
 363                 debug!(?self.current_index, "folding free region");
 364                 (self.fold_region_fn)(r, self.current_index)
 365             }
 366         }
 367     }
 368 }
 369
 370 ///////////////////////////////////////////////////////////////////////////
 371 // Bound vars replacer
 372
 373 /// Replaces the escaping bound vars (late bound regions or bound types) in a type.
 374 struct BoundVarReplacer<'a, 'tcx> {
 375     tcx: TyCtxt<'tcx>,
 376
 377     /// As with `RegionFolder`, represents the index of a binder *just outside*
 378     /// the ones we have visited.
 379     current_index: ty::DebruijnIndex,
 380
 381     fld_r: &'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a),
 382     fld_t: &'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a),
 383     fld_c: &'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> ty::Const<'tcx> + 'a),
 384 }
 385
 386 impl<'a, 'tcx> BoundVarReplacer<'a, 'tcx> {
 387     fn new(
 388         tcx: TyCtxt<'tcx>,
 389         fld_r: &'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a),
 390         fld_t: &'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a),
 391         fld_c: &'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> ty::Const<'tcx> + 'a),
 392     ) -> Self {
 393         BoundVarReplacer { tcx, current_index: ty::INNERMOST, fld_r, fld_t, fld_c }
 394     }
 395 }
 396
 397 impl<'a, 'tcx> TypeFolder<'tcx> for BoundVarReplacer<'a, 'tcx> {
 398     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 399         self.tcx
 400     }
 401
 402     fn fold_binder<T: TypeFoldable<'tcx>>(
 403         &mut self,
 404         t: ty::Binder<'tcx, T>,
 405     ) -> ty::Binder<'tcx, T> {
 406         self.current_index.shift_in(1);
 407         let t = t.super_fold_with(self);
 408         self.current_index.shift_out(1);
 409         t
 410     }
 411
 412     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 413         match *t.kind() {
 414             ty::Bound(debruijn, bound_ty) if debruijn == self.current_index => {
 415                 let ty = (self.fld_t)(bound_ty);
 416                 ty::fold::shift_vars(self.tcx, ty, self.current_index.as_u32())
 417             }
 418             _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self),
 419             _ => t,
 420         }
 421     }
 422
 423     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 424         match *r {
 425             ty::ReLateBound(debruijn, br) if debruijn == self.current_index => {
 426                 let region = (self.fld_r)(br);
 427                 if let ty::ReLateBound(debruijn1, br) = *region {
 428                     // If the callback returns a late-bound region,
 429                     // that region should always use the INNERMOST
 430                     // debruijn index. Then we adjust it to the
 431                     // correct depth.
 432                     assert_eq!(debruijn1, ty::INNERMOST);
 433                     self.tcx.mk_region(ty::ReLateBound(debruijn, br))
 434                 } else {
 435                     region
 436                 }
 437             }
 438             _ => r,
 439         }
 440     }
 441
 442     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 443         match ct.kind() {
 444             ty::ConstKind::Bound(debruijn, bound_const) if debruijn == self.current_index => {
 445                 let ct = (self.fld_c)(bound_const, ct.ty());
 446                 ty::fold::shift_vars(self.tcx, ct, self.current_index.as_u32())
 447             }
 448             _ => ct.super_fold_with(self),
 449         }
 450     }
 451 }
 452
 453 impl<'tcx> TyCtxt<'tcx> {
 454     /// Replaces all regions bound by the given `Binder` with the
 455     /// results returned by the closure; the closure is expected to
 456     /// return a free region (relative to this binder), and hence the
 457     /// binder is removed in the return type. The closure is invoked
 458     /// once for each unique `BoundRegionKind`; multiple references to the
 459     /// same `BoundRegionKind` will reuse the previous result. A map is
 460     /// returned at the end with each bound region and the free region
 461     /// that replaced it.
 462     ///
 463     /// # Panics
 464     ///
 465     /// This method only replaces late bound regions. Any types or
 466     /// constants bound by `value` will cause an ICE.
 467     pub fn replace_late_bound_regions<T, F>(
 468         self,
 469         value: Binder<'tcx, T>,
 470         mut fld_r: F,
 471     ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
 472     where
 473         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 474         T: TypeFoldable<'tcx>,
 475     {
 476         let mut region_map = BTreeMap::new();
 477         let real_fld_r = |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br));
 478         let value = self.replace_late_bound_regions_uncached(value, real_fld_r);
 479         (value, region_map)
 480     }
 481
 482     pub fn replace_late_bound_regions_uncached<T, F>(
 483         self,
 484         value: Binder<'tcx, T>,
 485         mut fld_r: F,
 486     ) -> T
 487     where
 488         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 489         T: TypeFoldable<'tcx>,
 490     {
 491         let mut fld_t = |b| bug!("unexpected bound ty in binder: {b:?}");
 492         let mut fld_c = |b, ty| bug!("unexpected bound ct in binder: {b:?} {ty}");
 493         let value = value.skip_binder();
 494         if !value.has_escaping_bound_vars() {
 495             value
 496         } else {
 497             let mut replacer = BoundVarReplacer::new(self, &mut fld_r, &mut fld_t, &mut fld_c);
 498             value.fold_with(&mut replacer)
 499         }
 500     }
 501
 502     /// Replaces all escaping bound vars. The `fld_r` closure replaces escaping
 503     /// bound regions; the `fld_t` closure replaces escaping bound types and the `fld_c`
 504     /// closure replaces escaping bound consts.
 505     pub fn replace_escaping_bound_vars_uncached<T, F, G, H>(
 506         self,
 507         value: T,
 508         mut fld_r: F,
 509         mut fld_t: G,
 510         mut fld_c: H,
 511     ) -> T
 512     where
 513         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 514         G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 515         H: FnMut(ty::BoundVar, Ty<'tcx>) -> ty::Const<'tcx>,
 516         T: TypeFoldable<'tcx>,
 517     {
 518         if !value.has_escaping_bound_vars() {
 519             value
 520         } else {
 521             let mut replacer = BoundVarReplacer::new(self, &mut fld_r, &mut fld_t, &mut fld_c);
 522             value.fold_with(&mut replacer)
 523         }
 524     }
 525
 526     /// Replaces all types or regions bound by the given `Binder`. The `fld_r`
 527     /// closure replaces bound regions, the `fld_t` closure replaces bound
 528     /// types, and `fld_c` replaces bound constants.
 529     pub fn replace_bound_vars_uncached<T, F, G, H>(
 530         self,
 531         value: Binder<'tcx, T>,
 532         fld_r: F,
 533         fld_t: G,
 534         fld_c: H,
 535     ) -> T
 536     where
 537         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 538         G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 539         H: FnMut(ty::BoundVar, Ty<'tcx>) -> ty::Const<'tcx>,
 540         T: TypeFoldable<'tcx>,
 541     {
 542         self.replace_escaping_bound_vars_uncached(value.skip_binder(), fld_r, fld_t, fld_c)
 543     }
 544
 545     /// Replaces any late-bound regions bound in `value` with
 546     /// free variants attached to `all_outlive_scope`.
 547     pub fn liberate_late_bound_regions<T>(
 548         self,
 549         all_outlive_scope: DefId,
 550         value: ty::Binder<'tcx, T>,
 551     ) -> T
 552     where
 553         T: TypeFoldable<'tcx>,
 554     {
 555         self.replace_late_bound_regions_uncached(value, |br| {
 556             self.mk_region(ty::ReFree(ty::FreeRegion {
 557                 scope: all_outlive_scope,
 558                 bound_region: br.kind,
 559             }))
 560         })
 561     }
 562
 563     pub fn shift_bound_var_indices<T>(self, bound_vars: usize, value: T) -> T
 564     where
 565         T: TypeFoldable<'tcx>,
 566     {
 567         self.replace_escaping_bound_vars_uncached(
 568             value,
 569             |r| {
 570                 self.mk_region(ty::ReLateBound(
 571                     ty::INNERMOST,
 572                     ty::BoundRegion {
 573                         var: ty::BoundVar::from_usize(r.var.as_usize() + bound_vars),
 574                         kind: r.kind,
 575                     },
 576                 ))
 577             },
 578             |t| {
 579                 self.mk_ty(ty::Bound(
 580                     ty::INNERMOST,
 581                     ty::BoundTy {
 582                         var: ty::BoundVar::from_usize(t.var.as_usize() + bound_vars),
 583                         kind: t.kind,
 584                     },
 585                 ))
 586             },
 587             |c, ty| {
 588                 self.mk_const(ty::ConstS {
 589                     kind: ty::ConstKind::Bound(
 590                         ty::INNERMOST,
 591                         ty::BoundVar::from_usize(c.as_usize() + bound_vars),
 592                     ),
 593                     ty,
 594                 })
 595             },
 596         )
 597     }
 598
 599     /// Replaces any late-bound regions bound in `value` with `'erased`. Useful in codegen but also
 600     /// method lookup and a few other places where precise region relationships are not required.
 601     pub fn erase_late_bound_regions<T>(self, value: Binder<'tcx, T>) -> T
 602     where
 603         T: TypeFoldable<'tcx>,
 604     {
 605         self.replace_late_bound_regions(value, |_| self.lifetimes.re_erased).0
 606     }
 607
 608     /// Rewrite any late-bound regions so that they are anonymous. Region numbers are
 609     /// assigned starting at 0 and increasing monotonically in the order traversed
 610     /// by the fold operation.
 611     ///
 612     /// The chief purpose of this function is to canonicalize regions so that two
 613     /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become
 614     /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and
 615     /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization.
 616     pub fn anonymize_late_bound_regions<T>(self, sig: Binder<'tcx, T>) -> Binder<'tcx, T>
 617     where
 618         T: TypeFoldable<'tcx>,
 619     {
 620         let mut counter = 0;
 621         let inner = self
 622             .replace_late_bound_regions(sig, |_| {
 623                 let br = ty::BoundRegion {
 624                     var: ty::BoundVar::from_u32(counter),
 625                     kind: ty::BrAnon(counter),
 626                 };
 627                 let r = self.mk_region(ty::ReLateBound(ty::INNERMOST, br));
 628                 counter += 1;
 629                 r
 630             })
 631             .0;
 632         let bound_vars = self.mk_bound_variable_kinds(
 633             (0..counter).map(|i| ty::BoundVariableKind::Region(ty::BrAnon(i))),
 634         );
 635         Binder::bind_with_vars(inner, bound_vars)
 636     }
 637 }
 638
 639 ///////////////////////////////////////////////////////////////////////////
 640 // Shifter
 641 //
 642 // Shifts the De Bruijn indices on all escaping bound vars by a
 643 // fixed amount. Useful in substitution or when otherwise introducing
 644 // a binding level that is not intended to capture the existing bound
 645 // vars. See comment on `shift_vars_through_binders` method in
 646 // `subst.rs` for more details.
 647
 648 struct Shifter<'tcx> {
 649     tcx: TyCtxt<'tcx>,
 650     current_index: ty::DebruijnIndex,
 651     amount: u32,
 652 }
 653
 654 impl<'tcx> Shifter<'tcx> {
 655     pub fn new(tcx: TyCtxt<'tcx>, amount: u32) -> Self {
 656         Shifter { tcx, current_index: ty::INNERMOST, amount }
 657     }
 658 }
 659
 660 impl<'tcx> TypeFolder<'tcx> for Shifter<'tcx> {
 661     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 662         self.tcx
 663     }
 664
 665     fn fold_binder<T: TypeFoldable<'tcx>>(
 666         &mut self,
 667         t: ty::Binder<'tcx, T>,
 668     ) -> ty::Binder<'tcx, T> {
 669         self.current_index.shift_in(1);
 670         let t = t.super_fold_with(self);
 671         self.current_index.shift_out(1);
 672         t
 673     }
 674
 675     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 676         match *r {
 677             ty::ReLateBound(debruijn, br) => {
 678                 if self.amount == 0 || debruijn < self.current_index {
 679                     r
 680                 } else {
 681                     let debruijn = debruijn.shifted_in(self.amount);
 682                     let shifted = ty::ReLateBound(debruijn, br);
 683                     self.tcx.mk_region(shifted)
 684                 }
 685             }
 686             _ => r,
 687         }
 688     }
 689
 690     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 691         match *ty.kind() {
 692             ty::Bound(debruijn, bound_ty) => {
 693                 if self.amount == 0 || debruijn < self.current_index {
 694                     ty
 695                 } else {
 696                     let debruijn = debruijn.shifted_in(self.amount);
 697                     self.tcx.mk_ty(ty::Bound(debruijn, bound_ty))
 698                 }
 699             }
 700
 701             _ => ty.super_fold_with(self),
 702         }
 703     }
 704
 705     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 706         if let ty::ConstKind::Bound(debruijn, bound_ct) = ct.kind() {
 707             if self.amount == 0 || debruijn < self.current_index {
 708                 ct
 709             } else {
 710                 let debruijn = debruijn.shifted_in(self.amount);
 711                 self.tcx.mk_const(ty::ConstS {
 712                     kind: ty::ConstKind::Bound(debruijn, bound_ct),
 713                     ty: ct.ty(),
 714                 })
 715             }
 716         } else {
 717             ct.super_fold_with(self)
 718         }
 719     }
 720 }
 721
 722 pub fn shift_region<'tcx>(
 723     tcx: TyCtxt<'tcx>,
 724     region: ty::Region<'tcx>,
 725     amount: u32,
 726 ) -> ty::Region<'tcx> {
 727     match *region {
 728         ty::ReLateBound(debruijn, br) if amount > 0 => {
 729             tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), br))
 730         }
 731         _ => region,
 732     }
 733 }
 734
 735 pub fn shift_vars<'tcx, T>(tcx: TyCtxt<'tcx>, value: T, amount: u32) -> T
 736 where
 737     T: TypeFoldable<'tcx>,
 738 {
 739     debug!("shift_vars(value={:?}, amount={})", value, amount);
 740
 741     value.fold_with(&mut Shifter::new(tcx, amount))
 742 }