src/librustc/middle/ty/fold.rs

   1 // Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Generalized type folding mechanism. The setup is a bit convoluted
  12 //! but allows for convenient usage. Let T be an instance of some
  13 //! "foldable type" (one which implements `TypeFoldable`) and F be an
  14 //! instance of a "folder" (a type which implements `TypeFolder`). Then
  15 //! the setup is intended to be:
  16 //!
  17 //!     T.fold_with(F) --calls--> F.fold_T(T) --calls--> super_fold_T(F, T)
  18 //!
  19 //! This way, when you define a new folder F, you can override
  20 //! `fold_T()` to customize the behavior, and invoke `super_fold_T()`
  21 //! to get the original behavior. Meanwhile, to actually fold
  22 //! something, you can just write `T.fold_with(F)`, which is
  23 //! convenient. (Note that `fold_with` will also transparently handle
  24 //! things like a `Vec<T>` where T is foldable and so on.)
  25 //!
  26 //! In this ideal setup, the only function that actually *does*
  27 //! anything is `super_fold_T`, which traverses the type `T`. Moreover,
  28 //! `super_fold_T` should only ever call `T.fold_with()`.
  29 //!
  30 //! In some cases, we follow a degenerate pattern where we do not have
  31 //! a `fold_T` nor `super_fold_T` method. Instead, `T.fold_with`
  32 //! traverses the structure directly. This is suboptimal because the
  33 //! behavior cannot be overridden, but it's much less work to implement.
  34 //! If you ever *do* need an override that doesn't exist, it's not hard
  35 //! to convert the degenerate pattern into the proper thing.
  36
  37 use middle::region;
  38 use middle::subst;
  39 use middle::ty::{self, Binder, Ty, HasTypeFlags, RegionEscape};
  40
  41 use std::fmt;
  42 use util::nodemap::{FnvHashMap, FnvHashSet};
  43
  44 ///////////////////////////////////////////////////////////////////////////
  45 // Two generic traits
  46
  47 /// The TypeFoldable trait is implemented for every type that can be folded.
  48 /// Basically, every type that has a corresponding method in TypeFolder.
  49 pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
  50     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self;
  51 }
  52
  53 /// The TypeFolder trait defines the actual *folding*. There is a
  54 /// method defined for every foldable type. Each of these has a
  55 /// default implementation that does an "identity" fold. Within each
  56 /// identity fold, it should invoke `foo.fold_with(self)` to fold each
  57 /// sub-item.
  58 pub trait TypeFolder<'tcx> : Sized {
  59     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
  60
  61     /// Invoked by the `super_*` routines when we enter a region
  62     /// binding level (for example, when entering a function
  63     /// signature). This is used by clients that want to track the
  64     /// Debruijn index nesting level.
  65     fn enter_region_binder(&mut self) { }
  66
  67     /// Invoked by the `super_*` routines when we exit a region
  68     /// binding level. This is used by clients that want to
  69     /// track the Debruijn index nesting level.
  70     fn exit_region_binder(&mut self) { }
  71
  72     fn fold_binder<T>(&mut self, t: &Binder<T>) -> Binder<T>
  73         where T : TypeFoldable<'tcx>
  74     {
  75         // FIXME(#20526) this should replace `enter_region_binder`/`exit_region_binder`.
  76         super_fold_binder(self, t)
  77     }
  78
  79     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
  80         super_fold_ty(self, t)
  81     }
  82
  83     fn fold_mt(&mut self, t: &ty::TypeAndMut<'tcx>) -> ty::TypeAndMut<'tcx> {
  84         super_fold_mt(self, t)
  85     }
  86
  87     fn fold_trait_ref(&mut self, t: &ty::TraitRef<'tcx>) -> ty::TraitRef<'tcx> {
  88         super_fold_trait_ref(self, t)
  89     }
  90
  91     fn fold_substs(&mut self,
  92                    substs: &subst::Substs<'tcx>)
  93                    -> subst::Substs<'tcx> {
  94         super_fold_substs(self, substs)
  95     }
  96
  97     fn fold_fn_sig(&mut self,
  98                    sig: &ty::FnSig<'tcx>)
  99                    -> ty::FnSig<'tcx> {
 100         super_fold_fn_sig(self, sig)
 101     }
 102
 103     fn fold_output(&mut self,
 104                       output: &ty::FnOutput<'tcx>)
 105                       -> ty::FnOutput<'tcx> {
 106         super_fold_output(self, output)
 107     }
 108
 109     fn fold_bare_fn_ty(&mut self,
 110                        fty: &ty::BareFnTy<'tcx>)
 111                        -> ty::BareFnTy<'tcx>
 112     {
 113         super_fold_bare_fn_ty(self, fty)
 114     }
 115
 116     fn fold_closure_ty(&mut self,
 117                        fty: &ty::ClosureTy<'tcx>)
 118                        -> ty::ClosureTy<'tcx> {
 119         super_fold_closure_ty(self, fty)
 120     }
 121
 122     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 123         r
 124     }
 125
 126     fn fold_existential_bounds(&mut self, s: &ty::ExistentialBounds<'tcx>)
 127                                -> ty::ExistentialBounds<'tcx> {
 128         super_fold_existential_bounds(self, s)
 129     }
 130
 131     fn fold_autoref(&mut self, ar: &ty::AutoRef<'tcx>) -> ty::AutoRef<'tcx> {
 132         super_fold_autoref(self, ar)
 133     }
 134
 135     fn fold_item_substs(&mut self, i: ty::ItemSubsts<'tcx>) -> ty::ItemSubsts<'tcx> {
 136         super_fold_item_substs(self, i)
 137     }
 138 }
 139
 140 ///////////////////////////////////////////////////////////////////////////
 141 // "super" routines: these are the default implementations for TypeFolder.
 142 //
 143 // They should invoke `foo.fold_with()` to do recursive folding.
 144
 145 pub fn super_fold_binder<'tcx, T, U>(this: &mut T,
 146                                      binder: &Binder<U>)
 147                                      -> Binder<U>
 148     where T : TypeFolder<'tcx>, U : TypeFoldable<'tcx>
 149 {
 150     this.enter_region_binder();
 151     let result = Binder(binder.0.fold_with(this));
 152     this.exit_region_binder();
 153     result
 154 }
 155
 156 pub fn super_fold_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 157                                                 ty: Ty<'tcx>)
 158                                                 -> Ty<'tcx> {
 159     let sty = match ty.sty {
 160         ty::TyBox(typ) => {
 161             ty::TyBox(typ.fold_with(this))
 162         }
 163         ty::TyRawPtr(ref tm) => {
 164             ty::TyRawPtr(tm.fold_with(this))
 165         }
 166         ty::TyArray(typ, sz) => {
 167             ty::TyArray(typ.fold_with(this), sz)
 168         }
 169         ty::TySlice(typ) => {
 170             ty::TySlice(typ.fold_with(this))
 171         }
 172         ty::TyEnum(tid, ref substs) => {
 173             let substs = substs.fold_with(this);
 174             ty::TyEnum(tid, this.tcx().mk_substs(substs))
 175         }
 176         ty::TyTrait(box ty::TraitTy { ref principal, ref bounds }) => {
 177             ty::TyTrait(box ty::TraitTy {
 178                 principal: principal.fold_with(this),
 179                 bounds: bounds.fold_with(this),
 180             })
 181         }
 182         ty::TyTuple(ref ts) => {
 183             ty::TyTuple(ts.fold_with(this))
 184         }
 185         ty::TyBareFn(opt_def_id, ref f) => {
 186             let bfn = f.fold_with(this);
 187             ty::TyBareFn(opt_def_id, this.tcx().mk_bare_fn(bfn))
 188         }
 189         ty::TyRef(r, ref tm) => {
 190             let r = r.fold_with(this);
 191             ty::TyRef(this.tcx().mk_region(r), tm.fold_with(this))
 192         }
 193         ty::TyStruct(did, ref substs) => {
 194             let substs = substs.fold_with(this);
 195             ty::TyStruct(did, this.tcx().mk_substs(substs))
 196         }
 197         ty::TyClosure(did, ref substs) => {
 198             let s = substs.fold_with(this);
 199             ty::TyClosure(did, s)
 200         }
 201         ty::TyProjection(ref data) => {
 202             ty::TyProjection(data.fold_with(this))
 203         }
 204         ty::TyBool | ty::TyChar | ty::TyStr |
 205         ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
 206         ty::TyError | ty::TyInfer(_) |
 207         ty::TyParam(..) => {
 208             ty.sty.clone()
 209         }
 210     };
 211     this.tcx().mk_ty(sty)
 212 }
 213
 214 pub fn super_fold_substs<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 215                                                     substs: &subst::Substs<'tcx>)
 216                                                     -> subst::Substs<'tcx> {
 217     let regions = match substs.regions {
 218         subst::ErasedRegions => {
 219             subst::ErasedRegions
 220         }
 221         subst::NonerasedRegions(ref regions) => {
 222             subst::NonerasedRegions(regions.fold_with(this))
 223         }
 224     };
 225
 226     subst::Substs { regions: regions,
 227                     types: substs.types.fold_with(this) }
 228 }
 229
 230 pub fn super_fold_fn_sig<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 231                                                     sig: &ty::FnSig<'tcx>)
 232                                                     -> ty::FnSig<'tcx>
 233 {
 234     ty::FnSig { inputs: sig.inputs.fold_with(this),
 235                 output: sig.output.fold_with(this),
 236                 variadic: sig.variadic }
 237 }
 238
 239 pub fn super_fold_output<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 240                                                     output: &ty::FnOutput<'tcx>)
 241                                                     -> ty::FnOutput<'tcx> {
 242     match *output {
 243         ty::FnConverging(ref ty) => ty::FnConverging(ty.fold_with(this)),
 244         ty::FnDiverging => ty::FnDiverging
 245     }
 246 }
 247
 248 pub fn super_fold_bare_fn_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 249                                                         fty: &ty::BareFnTy<'tcx>)
 250                                                         -> ty::BareFnTy<'tcx>
 251 {
 252     ty::BareFnTy { sig: fty.sig.fold_with(this),
 253                    abi: fty.abi,
 254                    unsafety: fty.unsafety }
 255 }
 256
 257 pub fn super_fold_closure_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 258                                                         fty: &ty::ClosureTy<'tcx>)
 259                                                         -> ty::ClosureTy<'tcx>
 260 {
 261     ty::ClosureTy {
 262         sig: fty.sig.fold_with(this),
 263         unsafety: fty.unsafety,
 264         abi: fty.abi,
 265     }
 266 }
 267
 268 pub fn super_fold_trait_ref<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 269                                                        t: &ty::TraitRef<'tcx>)
 270                                                        -> ty::TraitRef<'tcx>
 271 {
 272     let substs = t.substs.fold_with(this);
 273     ty::TraitRef {
 274         def_id: t.def_id,
 275         substs: this.tcx().mk_substs(substs),
 276     }
 277 }
 278
 279 pub fn super_fold_mt<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 280                                                 mt: &ty::TypeAndMut<'tcx>)
 281                                                 -> ty::TypeAndMut<'tcx> {
 282     ty::TypeAndMut {ty: mt.ty.fold_with(this),
 283             mutbl: mt.mutbl}
 284 }
 285
 286 pub fn super_fold_existential_bounds<'tcx, T: TypeFolder<'tcx>>(
 287     this: &mut T,
 288     bounds: &ty::ExistentialBounds<'tcx>)
 289     -> ty::ExistentialBounds<'tcx>
 290 {
 291     ty::ExistentialBounds {
 292         region_bound: bounds.region_bound.fold_with(this),
 293         builtin_bounds: bounds.builtin_bounds,
 294         projection_bounds: bounds.projection_bounds.fold_with(this),
 295     }
 296 }
 297
 298 pub fn super_fold_autoref<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 299                                                      autoref: &ty::AutoRef<'tcx>)
 300                                                      -> ty::AutoRef<'tcx>
 301 {
 302     match *autoref {
 303         ty::AutoPtr(r, m) => {
 304             let r = r.fold_with(this);
 305             ty::AutoPtr(this.tcx().mk_region(r), m)
 306         }
 307         ty::AutoUnsafe(m) => ty::AutoUnsafe(m)
 308     }
 309 }
 310
 311 pub fn super_fold_item_substs<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 312                                                          substs: ty::ItemSubsts<'tcx>)
 313                                                          -> ty::ItemSubsts<'tcx>
 314 {
 315     ty::ItemSubsts {
 316         substs: substs.substs.fold_with(this),
 317     }
 318 }
 319
 320 ///////////////////////////////////////////////////////////////////////////
 321 // Some sample folders
 322
 323 pub struct BottomUpFolder<'a, 'tcx: 'a, F> where F: FnMut(Ty<'tcx>) -> Ty<'tcx> {
 324     pub tcx: &'a ty::ctxt<'tcx>,
 325     pub fldop: F,
 326 }
 327
 328 impl<'a, 'tcx, F> TypeFolder<'tcx> for BottomUpFolder<'a, 'tcx, F> where
 329     F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 330 {
 331     fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
 332
 333     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 334         let t1 = super_fold_ty(self, ty);
 335         (self.fldop)(t1)
 336     }
 337 }
 338
 339 ///////////////////////////////////////////////////////////////////////////
 340 // Region folder
 341
 342 impl<'tcx> ty::ctxt<'tcx> {
 343     /// Collects the free and escaping regions in `value` into `region_set`. Returns
 344     /// whether any late-bound regions were skipped
 345     pub fn collect_regions<T>(&self,
 346         value: &T,
 347         region_set: &mut FnvHashSet<ty::Region>)
 348         -> bool
 349         where T : TypeFoldable<'tcx>
 350     {
 351         let mut have_bound_regions = false;
 352         self.fold_regions(value, &mut have_bound_regions,
 353                           |r, d| { region_set.insert(r.from_depth(d)); r });
 354         have_bound_regions
 355     }
 356
 357     /// Folds the escaping and free regions in `value` using `f`, and
 358     /// sets `skipped_regions` to true if any late-bound region was found
 359     /// and skipped.
 360     pub fn fold_regions<T,F>(&self,
 361         value: &T,
 362         skipped_regions: &mut bool,
 363         mut f: F)
 364         -> T
 365         where F : FnMut(ty::Region, u32) -> ty::Region,
 366               T : TypeFoldable<'tcx>,
 367     {
 368         value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f))
 369     }
 370 }
 371
 372 /// Folds over the substructure of a type, visiting its component
 373 /// types and all regions that occur *free* within it.
 374 ///
 375 /// That is, `Ty` can contain function or method types that bind
 376 /// regions at the call site (`ReLateBound`), and occurrences of
 377 /// regions (aka "lifetimes") that are bound within a type are not
 378 /// visited by this folder; only regions that occur free will be
 379 /// visited by `fld_r`.
 380
 381 pub struct RegionFolder<'a, 'tcx: 'a> {
 382     tcx: &'a ty::ctxt<'tcx>,
 383     skipped_regions: &'a mut bool,
 384     current_depth: u32,
 385     fld_r: &'a mut (FnMut(ty::Region, u32) -> ty::Region + 'a),
 386 }
 387
 388 impl<'a, 'tcx> RegionFolder<'a, 'tcx> {
 389     pub fn new<F>(tcx: &'a ty::ctxt<'tcx>,
 390                   skipped_regions: &'a mut bool,
 391                   fld_r: &'a mut F) -> RegionFolder<'a, 'tcx>
 392         where F : FnMut(ty::Region, u32) -> ty::Region
 393     {
 394         RegionFolder {
 395             tcx: tcx,
 396             skipped_regions: skipped_regions,
 397             current_depth: 1,
 398             fld_r: fld_r,
 399         }
 400     }
 401 }
 402
 403 impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx>
 404 {
 405     fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
 406
 407     fn enter_region_binder(&mut self) {
 408         self.current_depth += 1;
 409     }
 410
 411     fn exit_region_binder(&mut self) {
 412         self.current_depth -= 1;
 413     }
 414
 415     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 416         match r {
 417             ty::ReLateBound(debruijn, _) if debruijn.depth < self.current_depth => {
 418                 debug!("RegionFolder.fold_region({:?}) skipped bound region (current depth={})",
 419                        r, self.current_depth);
 420                 *self.skipped_regions = true;
 421                 r
 422             }
 423             _ => {
 424                 debug!("RegionFolder.fold_region({:?}) folding free region (current_depth={})",
 425                        r, self.current_depth);
 426                 (self.fld_r)(r, self.current_depth)
 427             }
 428         }
 429     }
 430 }
 431
 432 ///////////////////////////////////////////////////////////////////////////
 433 // Late-bound region replacer
 434
 435 // Replaces the escaping regions in a type.
 436
 437 struct RegionReplacer<'a, 'tcx: 'a> {
 438     tcx: &'a ty::ctxt<'tcx>,
 439     current_depth: u32,
 440     fld_r: &'a mut (FnMut(ty::BoundRegion) -> ty::Region + 'a),
 441     map: FnvHashMap<ty::BoundRegion, ty::Region>
 442 }
 443
 444 impl<'tcx> ty::ctxt<'tcx> {
 445     pub fn replace_late_bound_regions<T,F>(&self,
 446         value: &Binder<T>,
 447         mut f: F)
 448         -> (T, FnvHashMap<ty::BoundRegion, ty::Region>)
 449         where F : FnMut(ty::BoundRegion) -> ty::Region,
 450               T : TypeFoldable<'tcx>,
 451     {
 452         debug!("replace_late_bound_regions({:?})", value);
 453         let mut replacer = RegionReplacer::new(self, &mut f);
 454         let result = value.skip_binder().fold_with(&mut replacer);
 455         (result, replacer.map)
 456     }
 457
 458
 459     /// Replace any late-bound regions bound in `value` with free variants attached to scope-id
 460     /// `scope_id`.
 461     pub fn liberate_late_bound_regions<T>(&self,
 462         all_outlive_scope: region::CodeExtent,
 463         value: &Binder<T>)
 464         -> T
 465         where T : TypeFoldable<'tcx>
 466     {
 467         self.replace_late_bound_regions(value, |br| {
 468             ty::ReFree(ty::FreeRegion{scope: all_outlive_scope, bound_region: br})
 469         }).0
 470     }
 471
 472     /// Flattens two binding levels into one. So `for<'a> for<'b> Foo`
 473     /// becomes `for<'a,'b> Foo`.
 474     pub fn flatten_late_bound_regions<T>(&self, bound2_value: &Binder<Binder<T>>)
 475                                          -> Binder<T>
 476         where T: TypeFoldable<'tcx>
 477     {
 478         let bound0_value = bound2_value.skip_binder().skip_binder();
 479         let value = self.fold_regions(bound0_value, &mut false,
 480                                       |region, current_depth| {
 481             match region {
 482                 ty::ReLateBound(debruijn, br) if debruijn.depth >= current_depth => {
 483                     // should be true if no escaping regions from bound2_value
 484                     assert!(debruijn.depth - current_depth <= 1);
 485                     ty::ReLateBound(ty::DebruijnIndex::new(current_depth), br)
 486                 }
 487                 _ => {
 488                     region
 489                 }
 490             }
 491         });
 492         Binder(value)
 493     }
 494
 495     pub fn no_late_bound_regions<T>(&self, value: &Binder<T>) -> Option<T>
 496         where T : TypeFoldable<'tcx> + RegionEscape
 497     {
 498         if value.0.has_escaping_regions() {
 499             None
 500         } else {
 501             Some(value.0.clone())
 502         }
 503     }
 504
 505     /// Replace any late-bound regions bound in `value` with `'static`. Useful in trans but also
 506     /// method lookup and a few other places where precise region relationships are not required.
 507     pub fn erase_late_bound_regions<T>(&self, value: &Binder<T>) -> T
 508         where T : TypeFoldable<'tcx>
 509     {
 510         self.replace_late_bound_regions(value, |_| ty::ReStatic).0
 511     }
 512
 513     /// Rewrite any late-bound regions so that they are anonymous.  Region numbers are
 514     /// assigned starting at 1 and increasing monotonically in the order traversed
 515     /// by the fold operation.
 516     ///
 517     /// The chief purpose of this function is to canonicalize regions so that two
 518     /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become
 519     /// structurally identical.  For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and
 520     /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization.
 521     pub fn anonymize_late_bound_regions<T>(&self, sig: &Binder<T>) -> Binder<T>
 522         where T : TypeFoldable<'tcx>,
 523     {
 524         let mut counter = 0;
 525         Binder(self.replace_late_bound_regions(sig, |_| {
 526             counter += 1;
 527             ty::ReLateBound(ty::DebruijnIndex::new(1), ty::BrAnon(counter))
 528         }).0)
 529     }
 530 }
 531
 532 impl<'a, 'tcx> RegionReplacer<'a, 'tcx> {
 533     fn new<F>(tcx: &'a ty::ctxt<'tcx>, fld_r: &'a mut F) -> RegionReplacer<'a, 'tcx>
 534         where F : FnMut(ty::BoundRegion) -> ty::Region
 535     {
 536         RegionReplacer {
 537             tcx: tcx,
 538             current_depth: 1,
 539             fld_r: fld_r,
 540             map: FnvHashMap()
 541         }
 542     }
 543 }
 544
 545 impl<'a, 'tcx> TypeFolder<'tcx> for RegionReplacer<'a, 'tcx>
 546 {
 547     fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
 548
 549     fn enter_region_binder(&mut self) {
 550         self.current_depth += 1;
 551     }
 552
 553     fn exit_region_binder(&mut self) {
 554         self.current_depth -= 1;
 555     }
 556
 557     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 558         if !t.has_regions_escaping_depth(self.current_depth-1) {
 559             return t;
 560         }
 561
 562         super_fold_ty(self, t)
 563     }
 564
 565     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 566         match r {
 567             ty::ReLateBound(debruijn, br) if debruijn.depth == self.current_depth => {
 568                 debug!("RegionReplacer.fold_region({:?}) folding region (current_depth={})",
 569                        r, self.current_depth);
 570                 let fld_r = &mut self.fld_r;
 571                 let region = *self.map.entry(br).or_insert_with(|| fld_r(br));
 572                 if let ty::ReLateBound(debruijn1, br) = region {
 573                     // If the callback returns a late-bound region,
 574                     // that region should always use depth 1. Then we
 575                     // adjust it to the correct depth.
 576                     assert_eq!(debruijn1.depth, 1);
 577                     ty::ReLateBound(debruijn, br)
 578                 } else {
 579                     region
 580                 }
 581             }
 582             r => r
 583         }
 584     }
 585 }
 586
 587 ///////////////////////////////////////////////////////////////////////////
 588 // Region eraser
 589 //
 590 // Replaces all free regions with 'static. Useful in contexts, such as
 591 // method probing, where precise region relationships are not
 592 // important. Note that in trans you should use
 593 // `common::erase_regions` instead.
 594
 595 pub struct RegionEraser<'a, 'tcx: 'a> {
 596     tcx: &'a ty::ctxt<'tcx>,
 597 }
 598
 599 pub fn erase_regions<'tcx, T: TypeFoldable<'tcx>>(tcx: &ty::ctxt<'tcx>, t: T) -> T {
 600     let mut eraser = RegionEraser { tcx: tcx };
 601     t.fold_with(&mut eraser)
 602 }
 603
 604 impl<'a, 'tcx> TypeFolder<'tcx> for RegionEraser<'a, 'tcx> {
 605     fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
 606
 607     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 608         if !t.has_erasable_regions() {
 609             return t;
 610         }
 611
 612         super_fold_ty(self, t)
 613     }
 614
 615     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 616         // because whether or not a region is bound affects subtyping,
 617         // we can't erase the bound/free distinction, but we can
 618         // replace all free regions with 'static
 619         match r {
 620             ty::ReLateBound(..) | ty::ReEarlyBound(..) => r,
 621             _ => ty::ReStatic
 622         }
 623     }
 624 }
 625
 626 ///////////////////////////////////////////////////////////////////////////
 627 // Region shifter
 628 //
 629 // Shifts the De Bruijn indices on all escaping bound regions by a
 630 // fixed amount. Useful in substitution or when otherwise introducing
 631 // a binding level that is not intended to capture the existing bound
 632 // regions. See comment on `shift_regions_through_binders` method in
 633 // `subst.rs` for more details.
 634
 635 pub fn shift_region(region: ty::Region, amount: u32) -> ty::Region {
 636     match region {
 637         ty::ReLateBound(debruijn, br) => {
 638             ty::ReLateBound(debruijn.shifted(amount), br)
 639         }
 640         _ => {
 641             region
 642         }
 643     }
 644 }
 645
 646 pub fn shift_regions<'tcx, T:TypeFoldable<'tcx>>(tcx: &ty::ctxt<'tcx>,
 647                                                  amount: u32, value: &T) -> T {
 648     debug!("shift_regions(value={:?}, amount={})",
 649            value, amount);
 650
 651     value.fold_with(&mut RegionFolder::new(tcx, &mut false, &mut |region, _current_depth| {
 652         shift_region(region, amount)
 653     }))
 654 }