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             _ if ct.has_vars_bound_at_or_above(self.current_index) => ct.super_fold_with(self),
 449             _ => ct,
 450         }
 451     }
 452 }
 453
 454 impl<'tcx> TyCtxt<'tcx> {
 455     /// Replaces all regions bound by the given `Binder` with the
 456     /// results returned by the closure; the closure is expected to
 457     /// return a free region (relative to this binder), and hence the
 458     /// binder is removed in the return type. The closure is invoked
 459     /// once for each unique `BoundRegionKind`; multiple references to the
 460     /// same `BoundRegionKind` will reuse the previous result. A map is
 461     /// returned at the end with each bound region and the free region
 462     /// that replaced it.
 463     ///
 464     /// # Panics
 465     ///
 466     /// This method only replaces late bound regions. Any types or
 467     /// constants bound by `value` will cause an ICE.
 468     pub fn replace_late_bound_regions<T, F>(
 469         self,
 470         value: Binder<'tcx, T>,
 471         mut fld_r: F,
 472     ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
 473     where
 474         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 475         T: TypeFoldable<'tcx>,
 476     {
 477         let mut region_map = BTreeMap::new();
 478         let real_fld_r = |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br));
 479         let value = self.replace_late_bound_regions_uncached(value, real_fld_r);
 480         (value, region_map)
 481     }
 482
 483     pub fn replace_late_bound_regions_uncached<T, F>(
 484         self,
 485         value: Binder<'tcx, T>,
 486         mut fld_r: F,
 487     ) -> T
 488     where
 489         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 490         T: TypeFoldable<'tcx>,
 491     {
 492         let mut fld_t = |b| bug!("unexpected bound ty in binder: {b:?}");
 493         let mut fld_c = |b, ty| bug!("unexpected bound ct in binder: {b:?} {ty}");
 494         let value = value.skip_binder();
 495         if !value.has_escaping_bound_vars() {
 496             value
 497         } else {
 498             let mut replacer = BoundVarReplacer::new(self, &mut fld_r, &mut fld_t, &mut fld_c);
 499             value.fold_with(&mut replacer)
 500         }
 501     }
 502
 503     /// Replaces all escaping bound vars. The `fld_r` closure replaces escaping
 504     /// bound regions; the `fld_t` closure replaces escaping bound types and the `fld_c`
 505     /// closure replaces escaping bound consts.
 506     pub fn replace_escaping_bound_vars_uncached<T, F, G, H>(
 507         self,
 508         value: T,
 509         mut fld_r: F,
 510         mut fld_t: G,
 511         mut fld_c: H,
 512     ) -> T
 513     where
 514         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 515         G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 516         H: FnMut(ty::BoundVar, Ty<'tcx>) -> ty::Const<'tcx>,
 517         T: TypeFoldable<'tcx>,
 518     {
 519         if !value.has_escaping_bound_vars() {
 520             value
 521         } else {
 522             let mut replacer = BoundVarReplacer::new(self, &mut fld_r, &mut fld_t, &mut fld_c);
 523             value.fold_with(&mut replacer)
 524         }
 525     }
 526
 527     /// Replaces all types or regions bound by the given `Binder`. The `fld_r`
 528     /// closure replaces bound regions, the `fld_t` closure replaces bound
 529     /// types, and `fld_c` replaces bound constants.
 530     pub fn replace_bound_vars_uncached<T, F, G, H>(
 531         self,
 532         value: Binder<'tcx, T>,
 533         fld_r: F,
 534         fld_t: G,
 535         fld_c: H,
 536     ) -> T
 537     where
 538         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 539         G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 540         H: FnMut(ty::BoundVar, Ty<'tcx>) -> ty::Const<'tcx>,
 541         T: TypeFoldable<'tcx>,
 542     {
 543         self.replace_escaping_bound_vars_uncached(value.skip_binder(), fld_r, fld_t, fld_c)
 544     }
 545
 546     /// Replaces any late-bound regions bound in `value` with
 547     /// free variants attached to `all_outlive_scope`.
 548     pub fn liberate_late_bound_regions<T>(
 549         self,
 550         all_outlive_scope: DefId,
 551         value: ty::Binder<'tcx, T>,
 552     ) -> T
 553     where
 554         T: TypeFoldable<'tcx>,
 555     {
 556         self.replace_late_bound_regions_uncached(value, |br| {
 557             self.mk_region(ty::ReFree(ty::FreeRegion {
 558                 scope: all_outlive_scope,
 559                 bound_region: br.kind,
 560             }))
 561         })
 562     }
 563
 564     pub fn shift_bound_var_indices<T>(self, bound_vars: usize, value: T) -> T
 565     where
 566         T: TypeFoldable<'tcx>,
 567     {
 568         self.replace_escaping_bound_vars_uncached(
 569             value,
 570             |r| {
 571                 self.mk_region(ty::ReLateBound(
 572                     ty::INNERMOST,
 573                     ty::BoundRegion {
 574                         var: ty::BoundVar::from_usize(r.var.as_usize() + bound_vars),
 575                         kind: r.kind,
 576                     },
 577                 ))
 578             },
 579             |t| {
 580                 self.mk_ty(ty::Bound(
 581                     ty::INNERMOST,
 582                     ty::BoundTy {
 583                         var: ty::BoundVar::from_usize(t.var.as_usize() + bound_vars),
 584                         kind: t.kind,
 585                     },
 586                 ))
 587             },
 588             |c, ty| {
 589                 self.mk_const(ty::ConstS {
 590                     kind: ty::ConstKind::Bound(
 591                         ty::INNERMOST,
 592                         ty::BoundVar::from_usize(c.as_usize() + bound_vars),
 593                     ),
 594                     ty,
 595                 })
 596             },
 597         )
 598     }
 599
 600     /// Replaces any late-bound regions bound in `value` with `'erased`. Useful in codegen but also
 601     /// method lookup and a few other places where precise region relationships are not required.
 602     pub fn erase_late_bound_regions<T>(self, value: Binder<'tcx, T>) -> T
 603     where
 604         T: TypeFoldable<'tcx>,
 605     {
 606         self.replace_late_bound_regions(value, |_| self.lifetimes.re_erased).0
 607     }
 608
 609     /// Rewrite any late-bound regions so that they are anonymous. Region numbers are
 610     /// assigned starting at 0 and increasing monotonically in the order traversed
 611     /// by the fold operation.
 612     ///
 613     /// The chief purpose of this function is to canonicalize regions so that two
 614     /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become
 615     /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and
 616     /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization.
 617     pub fn anonymize_late_bound_regions<T>(self, sig: Binder<'tcx, T>) -> Binder<'tcx, T>
 618     where
 619         T: TypeFoldable<'tcx>,
 620     {
 621         let mut counter = 0;
 622         let inner = self
 623             .replace_late_bound_regions(sig, |_| {
 624                 let br = ty::BoundRegion {
 625                     var: ty::BoundVar::from_u32(counter),
 626                     kind: ty::BrAnon(counter),
 627                 };
 628                 let r = self.mk_region(ty::ReLateBound(ty::INNERMOST, br));
 629                 counter += 1;
 630                 r
 631             })
 632             .0;
 633         let bound_vars = self.mk_bound_variable_kinds(
 634             (0..counter).map(|i| ty::BoundVariableKind::Region(ty::BrAnon(i))),
 635         );
 636         Binder::bind_with_vars(inner, bound_vars)
 637     }
 638 }
 639
 640 ///////////////////////////////////////////////////////////////////////////
 641 // Shifter
 642 //
 643 // Shifts the De Bruijn indices on all escaping bound vars by a
 644 // fixed amount. Useful in substitution or when otherwise introducing
 645 // a binding level that is not intended to capture the existing bound
 646 // vars. See comment on `shift_vars_through_binders` method in
 647 // `subst.rs` for more details.
 648
 649 struct Shifter<'tcx> {
 650     tcx: TyCtxt<'tcx>,
 651     current_index: ty::DebruijnIndex,
 652     amount: u32,
 653 }
 654
 655 impl<'tcx> Shifter<'tcx> {
 656     pub fn new(tcx: TyCtxt<'tcx>, amount: u32) -> Self {
 657         Shifter { tcx, current_index: ty::INNERMOST, amount }
 658     }
 659 }
 660
 661 impl<'tcx> TypeFolder<'tcx> for Shifter<'tcx> {
 662     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 663         self.tcx
 664     }
 665
 666     fn fold_binder<T: TypeFoldable<'tcx>>(
 667         &mut self,
 668         t: ty::Binder<'tcx, T>,
 669     ) -> ty::Binder<'tcx, T> {
 670         self.current_index.shift_in(1);
 671         let t = t.super_fold_with(self);
 672         self.current_index.shift_out(1);
 673         t
 674     }
 675
 676     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 677         match *r {
 678             ty::ReLateBound(debruijn, br) => {
 679                 if self.amount == 0 || debruijn < self.current_index {
 680                     r
 681                 } else {
 682                     let debruijn = debruijn.shifted_in(self.amount);
 683                     let shifted = ty::ReLateBound(debruijn, br);
 684                     self.tcx.mk_region(shifted)
 685                 }
 686             }
 687             _ => r,
 688         }
 689     }
 690
 691     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 692         match *ty.kind() {
 693             ty::Bound(debruijn, bound_ty) => {
 694                 if self.amount == 0 || debruijn < self.current_index {
 695                     ty
 696                 } else {
 697                     let debruijn = debruijn.shifted_in(self.amount);
 698                     self.tcx.mk_ty(ty::Bound(debruijn, bound_ty))
 699                 }
 700             }
 701
 702             _ => ty.super_fold_with(self),
 703         }
 704     }
 705
 706     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 707         if let ty::ConstKind::Bound(debruijn, bound_ct) = ct.kind() {
 708             if self.amount == 0 || debruijn < self.current_index {
 709                 ct
 710             } else {
 711                 let debruijn = debruijn.shifted_in(self.amount);
 712                 self.tcx.mk_const(ty::ConstS {
 713                     kind: ty::ConstKind::Bound(debruijn, bound_ct),
 714                     ty: ct.ty(),
 715                 })
 716             }
 717         } else {
 718             ct.super_fold_with(self)
 719         }
 720     }
 721 }
 722
 723 pub fn shift_region<'tcx>(
 724     tcx: TyCtxt<'tcx>,
 725     region: ty::Region<'tcx>,
 726     amount: u32,
 727 ) -> ty::Region<'tcx> {
 728     match *region {
 729         ty::ReLateBound(debruijn, br) if amount > 0 => {
 730             tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), br))
 731         }
 732         _ => region,
 733     }
 734 }
 735
 736 pub fn shift_vars<'tcx, T>(tcx: TyCtxt<'tcx>, value: T, amount: u32) -> T
 737 where
 738     T: TypeFoldable<'tcx>,
 739 {
 740     debug!("shift_vars(value={:?}, amount={})", value, amount);
 741
 742     value.fold_with(&mut Shifter::new(tcx, amount))
 743 }