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 /*!
  12  * Generalized type folding mechanism. The setup is a bit convoluted
  13  * but allows for convenient usage. Let T be an instance of some
  14  * "foldable type" (one which implements `TypeFoldable`) and F be an
  15  * instance of a "folder" (a type which implements `TypeFolder`). Then
  16  * the setup is intended to be:
  17  *
  18  *     T.fold_with(F) --calls--> F.fold_T(T) --calls--> super_fold_T(F, T)
  19  *
  20  * This way, when you define a new folder F, you can override
  21  * `fold_T()` to customize the behavior, and invoke `super_fold_T()`
  22  * to get the original behavior. Meanwhile, to actually fold
  23  * something, you can just write `T.fold_with(F)`, which is
  24  * convenient. (Note that `fold_with` will also transparently handle
  25  * things like a `Vec<T>` where T is foldable and so on.)
  26  *
  27  * In this ideal setup, the only function that actually *does*
  28  * anything is `super_fold_T`, which traverses the type `T`. Moreover,
  29  * `super_fold_T` should only ever call `T.fold_with()`.
  30  *
  31  * In some cases, we follow a degenerate pattern where we do not have
  32  * a `fold_T` nor `super_fold_T` method. Instead, `T.fold_with`
  33  * traverses the structure directly. This is suboptimal because the
  34  * behavior cannot be overriden, but it's much less work to implement.
  35  * If you ever *do* need an override that doesn't exist, it's not hard
  36  * to convert the degenerate pattern into the proper thing.
  37  */
  38
  39 use middle::subst;
  40 use middle::subst::VecPerParamSpace;
  41 use middle::ty::{mod, Ty};
  42 use middle::traits;
  43 use middle::typeck;
  44 use std::rc::Rc;
  45 use syntax::owned_slice::OwnedSlice;
  46 use util::ppaux::Repr;
  47
  48 ///////////////////////////////////////////////////////////////////////////
  49 // Two generic traits
  50
  51 /// The TypeFoldable trait is implemented for every type that can be folded.
  52 /// Basically, every type that has a corresponding method in TypeFolder.
  53 pub trait TypeFoldable<'tcx> {
  54     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self;
  55 }
  56
  57 /// The TypeFolder trait defines the actual *folding*. There is a
  58 /// method defined for every foldable type. Each of these has a
  59 /// default implementation that does an "identity" fold. Within each
  60 /// identity fold, it should invoke `foo.fold_with(self)` to fold each
  61 /// sub-item.
  62 pub trait TypeFolder<'tcx> {
  63     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
  64
  65     /// Invoked by the `super_*` routines when we enter a region
  66     /// binding level (for example, when entering a function
  67     /// signature). This is used by clients that want to track the
  68     /// Debruijn index nesting level.
  69     fn enter_region_binder(&mut self) { }
  70
  71     /// Invoked by the `super_*` routines when we exit a region
  72     /// binding level. This is used by clients that want to
  73     /// track the Debruijn index nesting level.
  74     fn exit_region_binder(&mut self) { }
  75
  76     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
  77         super_fold_ty(self, t)
  78     }
  79
  80     fn fold_mt(&mut self, t: &ty::mt<'tcx>) -> ty::mt<'tcx> {
  81         super_fold_mt(self, t)
  82     }
  83
  84     fn fold_trait_ref(&mut self, t: &ty::TraitRef<'tcx>) -> ty::TraitRef<'tcx> {
  85         super_fold_trait_ref(self, t)
  86     }
  87
  88     fn fold_sty(&mut self, sty: &ty::sty<'tcx>) -> ty::sty<'tcx> {
  89         super_fold_sty(self, sty)
  90     }
  91
  92     fn fold_substs(&mut self,
  93                    substs: &subst::Substs<'tcx>)
  94                    -> subst::Substs<'tcx> {
  95         super_fold_substs(self, substs)
  96     }
  97
  98     fn fold_fn_sig(&mut self,
  99                 sig: &ty::FnSig<'tcx>)
 100                 -> ty::FnSig<'tcx> {
 101         super_fold_fn_sig(self, sig)
 102     }
 103
 104     fn fold_output(&mut self,
 105                       output: &ty::FnOutput<'tcx>)
 106                       -> ty::FnOutput<'tcx> {
 107         super_fold_output(self, output)
 108     }
 109
 110     fn fold_bare_fn_ty(&mut self,
 111                        fty: &ty::BareFnTy<'tcx>)
 112                        -> ty::BareFnTy<'tcx>
 113     {
 114         super_fold_bare_fn_ty(self, fty)
 115     }
 116
 117     fn fold_closure_ty(&mut self,
 118                        fty: &ty::ClosureTy<'tcx>)
 119                        -> ty::ClosureTy<'tcx> {
 120         super_fold_closure_ty(self, fty)
 121     }
 122
 123     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 124         r
 125     }
 126
 127     fn fold_trait_store(&mut self, s: ty::TraitStore) -> ty::TraitStore {
 128         super_fold_trait_store(self, s)
 129     }
 130
 131     fn fold_existential_bounds(&mut self, s: ty::ExistentialBounds)
 132                                -> ty::ExistentialBounds {
 133         super_fold_existential_bounds(self, s)
 134     }
 135
 136     fn fold_autoref(&mut self, ar: &ty::AutoRef<'tcx>) -> ty::AutoRef<'tcx> {
 137         super_fold_autoref(self, ar)
 138     }
 139
 140     fn fold_item_substs(&mut self, i: ty::ItemSubsts<'tcx>) -> ty::ItemSubsts<'tcx> {
 141         super_fold_item_substs(self, i)
 142     }
 143
 144     fn fold_obligation(&mut self, o: &traits::Obligation<'tcx>)
 145                        -> traits::Obligation<'tcx> {
 146         super_fold_obligation(self, o)
 147     }
 148 }
 149
 150 ///////////////////////////////////////////////////////////////////////////
 151 // TypeFoldable implementations.
 152 //
 153 // Ideally, each type should invoke `folder.fold_foo(self)` and
 154 // nothing else. In some cases, though, we haven't gotten around to
 155 // adding methods on the `folder` yet, and thus the folding is
 156 // hard-coded here. This is less-flexible, because folders cannot
 157 // override the behavior, but there are a lot of random types and one
 158 // can easily refactor the folding into the TypeFolder trait as
 159 // needed.
 160
 161 impl<'tcx> TypeFoldable<'tcx> for () {
 162     fn fold_with<F:TypeFolder<'tcx>>(&self, _: &mut F) -> () {
 163         ()
 164     }
 165 }
 166
 167 impl<'tcx, T:TypeFoldable<'tcx>, U:TypeFoldable<'tcx>> TypeFoldable<'tcx> for (T, U) {
 168     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> (T, U) {
 169         (self.0.fold_with(folder), self.1.fold_with(folder))
 170     }
 171 }
 172
 173 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Option<T> {
 174     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Option<T> {
 175         self.as_ref().map(|t| t.fold_with(folder))
 176     }
 177 }
 178
 179 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Rc<T> {
 180     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Rc<T> {
 181         Rc::new((**self).fold_with(folder))
 182     }
 183 }
 184
 185 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Vec<T> {
 186     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Vec<T> {
 187         self.iter().map(|t| t.fold_with(folder)).collect()
 188     }
 189 }
 190
 191 impl<'tcx, T:TypeFoldable<'tcx>> TypeFoldable<'tcx> for ty::Binder<T> {
 192     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Binder<T> {
 193         folder.enter_region_binder();
 194         let result = ty::bind(self.value.fold_with(folder));
 195         folder.exit_region_binder();
 196         result
 197     }
 198 }
 199
 200 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for OwnedSlice<T> {
 201     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> OwnedSlice<T> {
 202         self.iter().map(|t| t.fold_with(folder)).collect()
 203     }
 204 }
 205
 206 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for VecPerParamSpace<T> {
 207     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> VecPerParamSpace<T> {
 208
 209         // Things in the Fn space take place under an additional level
 210         // of region binding relative to the other spaces. This is
 211         // because those entries are attached to a method, and methods
 212         // always introduce a level of region binding.
 213
 214         let result = self.map_enumerated(|(space, index, elem)| {
 215             if space == subst::FnSpace && index == 0 {
 216                 // enter new level when/if we reach the first thing in fn space
 217                 folder.enter_region_binder();
 218             }
 219             elem.fold_with(folder)
 220         });
 221         if result.len(subst::FnSpace) > 0 {
 222             // if there was anything in fn space, exit the region binding level
 223             folder.exit_region_binder();
 224         }
 225         result
 226     }
 227 }
 228
 229 impl<'tcx> TypeFoldable<'tcx> for ty::TraitStore {
 230     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TraitStore {
 231         folder.fold_trait_store(*self)
 232     }
 233 }
 234
 235 impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
 236     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Ty<'tcx> {
 237         folder.fold_ty(*self)
 238     }
 239 }
 240
 241 impl<'tcx> TypeFoldable<'tcx> for ty::BareFnTy<'tcx> {
 242     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::BareFnTy<'tcx> {
 243         folder.fold_bare_fn_ty(self)
 244     }
 245 }
 246
 247 impl<'tcx> TypeFoldable<'tcx> for ty::ClosureTy<'tcx> {
 248     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ClosureTy<'tcx> {
 249         folder.fold_closure_ty(self)
 250     }
 251 }
 252
 253 impl<'tcx> TypeFoldable<'tcx> for ty::mt<'tcx> {
 254     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::mt<'tcx> {
 255         folder.fold_mt(self)
 256     }
 257 }
 258
 259 impl<'tcx> TypeFoldable<'tcx> for ty::FnOutput<'tcx> {
 260     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::FnOutput<'tcx> {
 261         folder.fold_output(self)
 262     }
 263 }
 264
 265 impl<'tcx> TypeFoldable<'tcx> for ty::FnSig<'tcx> {
 266     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::FnSig<'tcx> {
 267         folder.fold_fn_sig(self)
 268     }
 269 }
 270
 271 impl<'tcx> TypeFoldable<'tcx> for ty::sty<'tcx> {
 272     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::sty<'tcx> {
 273         folder.fold_sty(self)
 274     }
 275 }
 276
 277 impl<'tcx> TypeFoldable<'tcx> for ty::TraitRef<'tcx> {
 278     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TraitRef<'tcx> {
 279         folder.fold_trait_ref(self)
 280     }
 281 }
 282
 283 impl<'tcx> TypeFoldable<'tcx> for ty::Region {
 284     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Region {
 285         folder.fold_region(*self)
 286     }
 287 }
 288
 289 impl<'tcx> TypeFoldable<'tcx> for subst::Substs<'tcx> {
 290     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> subst::Substs<'tcx> {
 291         folder.fold_substs(self)
 292     }
 293 }
 294
 295 impl<'tcx> TypeFoldable<'tcx> for ty::ItemSubsts<'tcx> {
 296     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ItemSubsts<'tcx> {
 297         ty::ItemSubsts {
 298             substs: self.substs.fold_with(folder),
 299         }
 300     }
 301 }
 302
 303 impl<'tcx> TypeFoldable<'tcx> for ty::AutoRef<'tcx> {
 304     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::AutoRef<'tcx> {
 305         folder.fold_autoref(self)
 306     }
 307 }
 308
 309 impl<'tcx> TypeFoldable<'tcx> for typeck::MethodOrigin<'tcx> {
 310     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> typeck::MethodOrigin<'tcx> {
 311         match *self {
 312             typeck::MethodStatic(def_id) => {
 313                 typeck::MethodStatic(def_id)
 314             }
 315             typeck::MethodStaticUnboxedClosure(def_id) => {
 316                 typeck::MethodStaticUnboxedClosure(def_id)
 317             }
 318             typeck::MethodTypeParam(ref param) => {
 319                 typeck::MethodTypeParam(typeck::MethodParam {
 320                     trait_ref: param.trait_ref.fold_with(folder),
 321                     method_num: param.method_num
 322                 })
 323             }
 324             typeck::MethodTraitObject(ref object) => {
 325                 typeck::MethodTraitObject(typeck::MethodObject {
 326                     trait_ref: object.trait_ref.fold_with(folder),
 327                     object_trait_id: object.object_trait_id,
 328                     method_num: object.method_num,
 329                     real_index: object.real_index
 330                 })
 331             }
 332         }
 333     }
 334 }
 335
 336 impl<'tcx> TypeFoldable<'tcx> for typeck::vtable_origin<'tcx> {
 337     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> typeck::vtable_origin<'tcx> {
 338         match *self {
 339             typeck::vtable_static(def_id, ref substs, ref origins) => {
 340                 let r_substs = substs.fold_with(folder);
 341                 let r_origins = origins.fold_with(folder);
 342                 typeck::vtable_static(def_id, r_substs, r_origins)
 343             }
 344             typeck::vtable_param(n, b) => {
 345                 typeck::vtable_param(n, b)
 346             }
 347             typeck::vtable_unboxed_closure(def_id) => {
 348                 typeck::vtable_unboxed_closure(def_id)
 349             }
 350             typeck::vtable_error => {
 351                 typeck::vtable_error
 352             }
 353         }
 354     }
 355 }
 356
 357 impl<'tcx> TypeFoldable<'tcx> for ty::BuiltinBounds {
 358     fn fold_with<F: TypeFolder<'tcx>>(&self, _folder: &mut F) -> ty::BuiltinBounds {
 359         *self
 360     }
 361 }
 362
 363 impl<'tcx> TypeFoldable<'tcx> for ty::ExistentialBounds {
 364     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ExistentialBounds {
 365         folder.fold_existential_bounds(*self)
 366     }
 367 }
 368
 369 impl<'tcx> TypeFoldable<'tcx> for ty::ParamBounds<'tcx> {
 370     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ParamBounds<'tcx> {
 371         ty::ParamBounds {
 372             region_bounds: self.region_bounds.fold_with(folder),
 373             builtin_bounds: self.builtin_bounds.fold_with(folder),
 374             trait_bounds: self.trait_bounds.fold_with(folder),
 375         }
 376     }
 377 }
 378
 379 impl<'tcx> TypeFoldable<'tcx> for ty::TypeParameterDef<'tcx> {
 380     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TypeParameterDef<'tcx> {
 381         ty::TypeParameterDef {
 382             name: self.name,
 383             def_id: self.def_id,
 384             space: self.space,
 385             index: self.index,
 386             associated_with: self.associated_with,
 387             bounds: self.bounds.fold_with(folder),
 388             default: self.default.fold_with(folder),
 389         }
 390     }
 391 }
 392
 393 impl<'tcx> TypeFoldable<'tcx> for ty::RegionParameterDef {
 394     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::RegionParameterDef {
 395         ty::RegionParameterDef {
 396             name: self.name,
 397             def_id: self.def_id,
 398             space: self.space,
 399             index: self.index,
 400             bounds: self.bounds.fold_with(folder)
 401         }
 402     }
 403 }
 404
 405 impl<'tcx> TypeFoldable<'tcx> for ty::Generics<'tcx> {
 406     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Generics<'tcx> {
 407         ty::Generics {
 408             types: self.types.fold_with(folder),
 409             regions: self.regions.fold_with(folder),
 410         }
 411     }
 412 }
 413
 414 impl<'tcx> TypeFoldable<'tcx> for ty::GenericBounds<'tcx> {
 415     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::GenericBounds<'tcx> {
 416         ty::GenericBounds {
 417             types: self.types.fold_with(folder),
 418             regions: self.regions.fold_with(folder),
 419         }
 420     }
 421 }
 422
 423 impl<'tcx> TypeFoldable<'tcx> for ty::UnsizeKind<'tcx> {
 424     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::UnsizeKind<'tcx> {
 425         match *self {
 426             ty::UnsizeLength(len) => ty::UnsizeLength(len),
 427             ty::UnsizeStruct(box ref k, n) => ty::UnsizeStruct(box k.fold_with(folder), n),
 428             ty::UnsizeVtable(ty::TyTrait{ref principal, bounds}, self_ty) => {
 429                 ty::UnsizeVtable(
 430                     ty::TyTrait {
 431                         principal: principal.fold_with(folder),
 432                         bounds: bounds.fold_with(folder),
 433                     },
 434                     self_ty.fold_with(folder))
 435             }
 436         }
 437     }
 438 }
 439
 440 impl<'tcx> TypeFoldable<'tcx> for traits::Obligation<'tcx> {
 441     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::Obligation<'tcx> {
 442         folder.fold_obligation(self)
 443     }
 444 }
 445
 446 impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::VtableImplData<'tcx, N> {
 447     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableImplData<'tcx, N> {
 448         traits::VtableImplData {
 449             impl_def_id: self.impl_def_id,
 450             substs: self.substs.fold_with(folder),
 451             nested: self.nested.fold_with(folder),
 452         }
 453     }
 454 }
 455
 456 impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::VtableBuiltinData<N> {
 457     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableBuiltinData<N> {
 458         traits::VtableBuiltinData {
 459             nested: self.nested.fold_with(folder),
 460         }
 461     }
 462 }
 463
 464 impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Vtable<'tcx, N> {
 465     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::Vtable<'tcx, N> {
 466         match *self {
 467             traits::VtableImpl(ref v) => traits::VtableImpl(v.fold_with(folder)),
 468             traits::VtableUnboxedClosure(d, ref s) => {
 469                 traits::VtableUnboxedClosure(d, s.fold_with(folder))
 470             }
 471             traits::VtableParam(ref p) => traits::VtableParam(p.fold_with(folder)),
 472             traits::VtableBuiltin(ref d) => traits::VtableBuiltin(d.fold_with(folder)),
 473         }
 474     }
 475 }
 476
 477 impl<'tcx> TypeFoldable<'tcx> for traits::VtableParamData<'tcx> {
 478     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableParamData<'tcx> {
 479         traits::VtableParamData {
 480             bound: self.bound.fold_with(folder),
 481         }
 482     }
 483 }
 484
 485 ///////////////////////////////////////////////////////////////////////////
 486 // "super" routines: these are the default implementations for TypeFolder.
 487 //
 488 // They should invoke `foo.fold_with()` to do recursive folding.
 489
 490 pub fn super_fold_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 491                                                 t: Ty<'tcx>)
 492                                                 -> Ty<'tcx> {
 493     let sty = t.sty.fold_with(this);
 494     ty::mk_t(this.tcx(), sty)
 495 }
 496
 497 pub fn super_fold_substs<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 498                                                     substs: &subst::Substs<'tcx>)
 499                                                     -> subst::Substs<'tcx> {
 500     let regions = match substs.regions {
 501         subst::ErasedRegions => {
 502             subst::ErasedRegions
 503         }
 504         subst::NonerasedRegions(ref regions) => {
 505             subst::NonerasedRegions(regions.fold_with(this))
 506         }
 507     };
 508
 509     subst::Substs { regions: regions,
 510                     types: substs.types.fold_with(this) }
 511 }
 512
 513 pub fn super_fold_fn_sig<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 514                                                     sig: &ty::FnSig<'tcx>)
 515                                                     -> ty::FnSig<'tcx>
 516 {
 517     this.enter_region_binder();
 518     let result = super_fold_fn_sig_contents(this, sig);
 519     this.exit_region_binder();
 520     result
 521 }
 522
 523 pub fn super_fold_fn_sig_contents<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 524                                                              sig: &ty::FnSig<'tcx>)
 525                                                              -> ty::FnSig<'tcx>
 526 {
 527     ty::FnSig { inputs: sig.inputs.fold_with(this),
 528                 output: sig.output.fold_with(this),
 529                 variadic: sig.variadic }
 530 }
 531
 532 pub fn super_fold_output<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 533                                                     output: &ty::FnOutput<'tcx>)
 534                                                     -> ty::FnOutput<'tcx> {
 535     match *output {
 536         ty::FnConverging(ref ty) => ty::FnConverging(ty.fold_with(this)),
 537         ty::FnDiverging => ty::FnDiverging
 538     }
 539 }
 540
 541 pub fn super_fold_bare_fn_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 542                                                         fty: &ty::BareFnTy<'tcx>)
 543                                                         -> ty::BareFnTy<'tcx>
 544 {
 545     ty::BareFnTy { sig: fty.sig.fold_with(this),
 546                    abi: fty.abi,
 547                    fn_style: fty.fn_style }
 548 }
 549
 550 pub fn super_fold_closure_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 551                                                         fty: &ty::ClosureTy<'tcx>)
 552                                                         -> ty::ClosureTy<'tcx>
 553 {
 554     ty::ClosureTy {
 555         store: fty.store.fold_with(this),
 556         sig: fty.sig.fold_with(this),
 557         fn_style: fty.fn_style,
 558         onceness: fty.onceness,
 559         bounds: fty.bounds.fold_with(this),
 560         abi: fty.abi,
 561     }
 562 }
 563
 564 pub fn super_fold_trait_ref<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 565                                                        t: &ty::TraitRef<'tcx>)
 566                                                        -> ty::TraitRef<'tcx>
 567 {
 568     this.enter_region_binder();
 569     let result = super_fold_trait_ref_contents(this, t);
 570     this.exit_region_binder();
 571     result
 572 }
 573
 574 pub fn super_fold_trait_ref_contents<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 575                                                                 t: &ty::TraitRef<'tcx>)
 576                                                                 -> ty::TraitRef<'tcx>
 577 {
 578     ty::TraitRef {
 579         def_id: t.def_id,
 580         substs: t.substs.fold_with(this),
 581     }
 582 }
 583
 584 pub fn super_fold_mt<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 585                                                 mt: &ty::mt<'tcx>)
 586                                                 -> ty::mt<'tcx> {
 587     ty::mt {ty: mt.ty.fold_with(this),
 588             mutbl: mt.mutbl}
 589 }
 590
 591 pub fn super_fold_sty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 592                                                  sty: &ty::sty<'tcx>)
 593                                                  -> ty::sty<'tcx> {
 594     match *sty {
 595         ty::ty_uniq(typ) => {
 596             ty::ty_uniq(typ.fold_with(this))
 597         }
 598         ty::ty_ptr(ref tm) => {
 599             ty::ty_ptr(tm.fold_with(this))
 600         }
 601         ty::ty_vec(typ, sz) => {
 602             ty::ty_vec(typ.fold_with(this), sz)
 603         }
 604         ty::ty_open(typ) => {
 605             ty::ty_open(typ.fold_with(this))
 606         }
 607         ty::ty_enum(tid, ref substs) => {
 608             ty::ty_enum(tid, substs.fold_with(this))
 609         }
 610         ty::ty_trait(box ty::TyTrait { ref principal, bounds }) => {
 611             ty::ty_trait(box ty::TyTrait {
 612                 principal: (*principal).fold_with(this),
 613                 bounds: bounds.fold_with(this),
 614             })
 615         }
 616         ty::ty_tup(ref ts) => {
 617             ty::ty_tup(ts.fold_with(this))
 618         }
 619         ty::ty_bare_fn(ref f) => {
 620             ty::ty_bare_fn(f.fold_with(this))
 621         }
 622         ty::ty_closure(ref f) => {
 623             ty::ty_closure(box f.fold_with(this))
 624         }
 625         ty::ty_rptr(r, ref tm) => {
 626             ty::ty_rptr(r.fold_with(this), tm.fold_with(this))
 627         }
 628         ty::ty_struct(did, ref substs) => {
 629             ty::ty_struct(did, substs.fold_with(this))
 630         }
 631         ty::ty_unboxed_closure(did, ref region, ref substs) => {
 632             ty::ty_unboxed_closure(did, region.fold_with(this), substs.fold_with(this))
 633         }
 634         ty::ty_bool | ty::ty_char | ty::ty_str |
 635         ty::ty_int(_) | ty::ty_uint(_) | ty::ty_float(_) |
 636         ty::ty_err | ty::ty_infer(_) |
 637         ty::ty_param(..) => {
 638             (*sty).clone()
 639         }
 640     }
 641 }
 642
 643 pub fn super_fold_trait_store<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 644                                                          trait_store: ty::TraitStore)
 645                                                          -> ty::TraitStore {
 646     match trait_store {
 647         ty::UniqTraitStore => ty::UniqTraitStore,
 648         ty::RegionTraitStore(r, m) => {
 649             ty::RegionTraitStore(r.fold_with(this), m)
 650         }
 651     }
 652 }
 653
 654 pub fn super_fold_existential_bounds<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 655                                                                 bounds: ty::ExistentialBounds)
 656                                                                 -> ty::ExistentialBounds {
 657     ty::ExistentialBounds {
 658         region_bound: bounds.region_bound.fold_with(this),
 659         builtin_bounds: bounds.builtin_bounds,
 660     }
 661 }
 662
 663 pub fn super_fold_autoref<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 664                                                      autoref: &ty::AutoRef<'tcx>)
 665                                                      -> ty::AutoRef<'tcx>
 666 {
 667     match *autoref {
 668         ty::AutoPtr(r, m, None) => ty::AutoPtr(this.fold_region(r), m, None),
 669         ty::AutoPtr(r, m, Some(ref a)) => {
 670             ty::AutoPtr(this.fold_region(r), m, Some(box super_fold_autoref(this, &**a)))
 671         }
 672         ty::AutoUnsafe(m, None) => ty::AutoUnsafe(m, None),
 673         ty::AutoUnsafe(m, Some(ref a)) => {
 674             ty::AutoUnsafe(m, Some(box super_fold_autoref(this, &**a)))
 675         }
 676         ty::AutoUnsize(ref k) => ty::AutoUnsize(k.fold_with(this)),
 677         ty::AutoUnsizeUniq(ref k) => ty::AutoUnsizeUniq(k.fold_with(this)),
 678     }
 679 }
 680
 681 pub fn super_fold_item_substs<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
 682                                                          substs: ty::ItemSubsts<'tcx>)
 683                                                          -> ty::ItemSubsts<'tcx>
 684 {
 685     ty::ItemSubsts {
 686         substs: substs.substs.fold_with(this),
 687     }
 688 }
 689
 690 pub fn super_fold_obligation<'tcx, T:TypeFolder<'tcx>>(this: &mut T,
 691                                                        obligation: &traits::Obligation<'tcx>)
 692                                                        -> traits::Obligation<'tcx>
 693 {
 694     traits::Obligation {
 695         cause: obligation.cause,
 696         recursion_depth: obligation.recursion_depth,
 697         trait_ref: obligation.trait_ref.fold_with(this),
 698     }
 699 }
 700
 701 ///////////////////////////////////////////////////////////////////////////
 702 // Higher-ranked things
 703
 704 /**
 705  * Designates a "binder" for late-bound regions.
 706  */
 707 pub trait HigherRankedFoldable<'tcx>: Repr<'tcx> {
 708     /// Folds the contents of `self`, ignoring the region binder created
 709     /// by `self`.
 710     fn fold_contents<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self;
 711 }
 712
 713 impl<'tcx> HigherRankedFoldable<'tcx> for ty::FnSig<'tcx> {
 714     fn fold_contents<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::FnSig<'tcx> {
 715         super_fold_fn_sig_contents(folder, self)
 716     }
 717 }
 718
 719 impl<'tcx> HigherRankedFoldable<'tcx> for ty::TraitRef<'tcx> {
 720     fn fold_contents<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TraitRef<'tcx> {
 721         super_fold_trait_ref_contents(folder, self)
 722     }
 723 }
 724
 725 impl<'tcx, T:TypeFoldable<'tcx>+Repr<'tcx>> HigherRankedFoldable<'tcx> for ty::Binder<T> {
 726     fn fold_contents<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Binder<T> {
 727         ty::bind(self.value.fold_with(folder))
 728     }
 729 }
 730
 731 impl<'tcx, T:HigherRankedFoldable<'tcx>> HigherRankedFoldable<'tcx> for Rc<T> {
 732     fn fold_contents<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Rc<T> {
 733         Rc::new((**self).fold_contents(folder))
 734     }
 735 }
 736
 737 ///////////////////////////////////////////////////////////////////////////
 738 // Some sample folders
 739
 740 pub struct BottomUpFolder<'a, 'tcx: 'a> {
 741     pub tcx: &'a ty::ctxt<'tcx>,
 742     pub fldop: |Ty<'tcx>|: 'a -> Ty<'tcx>,
 743 }
 744
 745 impl<'a, 'tcx> TypeFolder<'tcx> for BottomUpFolder<'a, 'tcx> {
 746     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 747
 748     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 749         let t1 = super_fold_ty(self, ty);
 750         (self.fldop)(t1)
 751     }
 752 }
 753
 754 ///////////////////////////////////////////////////////////////////////////
 755 // Region folder
 756
 757 /// Folds over the substructure of a type, visiting its component
 758 /// types and all regions that occur *free* within it.
 759 ///
 760 /// That is, `Ty` can contain function or method types that bind
 761 /// regions at the call site (`ReLateBound`), and occurrences of
 762 /// regions (aka "lifetimes") that are bound within a type are not
 763 /// visited by this folder; only regions that occur free will be
 764 /// visited by `fld_r`.
 765 ///
 766 /// (The distinction between "free" and "bound" is represented by
 767 /// keeping track of each `FnSig` in the lexical context of the
 768 /// current position of the fold.)
 769 pub struct RegionFolder<'a, 'tcx: 'a> {
 770     tcx: &'a ty::ctxt<'tcx>,
 771     current_depth: uint,
 772     fld_r: |ty::Region, uint|: 'a -> ty::Region,
 773 }
 774
 775 impl<'a, 'tcx> RegionFolder<'a, 'tcx> {
 776     pub fn new(tcx: &'a ty::ctxt<'tcx>, fld_r: |ty::Region, uint|: 'a -> ty::Region)
 777                -> RegionFolder<'a, 'tcx> {
 778         RegionFolder {
 779             tcx: tcx,
 780             current_depth: 1,
 781             fld_r: fld_r,
 782         }
 783     }
 784 }
 785
 786 impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx> {
 787     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 788
 789     fn enter_region_binder(&mut self) {
 790         self.current_depth += 1;
 791     }
 792
 793     fn exit_region_binder(&mut self) {
 794         self.current_depth -= 1;
 795     }
 796
 797     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 798         match r {
 799             ty::ReLateBound(debruijn, _) if debruijn.depth < self.current_depth => {
 800                 debug!("RegionFolder.fold_region({}) skipped bound region (current depth={})",
 801                        r.repr(self.tcx()), self.current_depth);
 802                 r
 803             }
 804             _ => {
 805                 debug!("RegionFolder.fold_region({}) folding free region (current_depth={})",
 806                        r.repr(self.tcx()), self.current_depth);
 807                 (self.fld_r)(r, self.current_depth)
 808             }
 809         }
 810     }
 811 }
 812
 813 ///////////////////////////////////////////////////////////////////////////
 814 // Region eraser
 815 //
 816 // Replaces all free regions with 'static. Useful in trans.
 817
 818 pub struct RegionEraser<'a, 'tcx: 'a> {
 819     tcx: &'a ty::ctxt<'tcx>,
 820 }
 821
 822 pub fn erase_regions<'tcx, T: TypeFoldable<'tcx>>(tcx: &ty::ctxt<'tcx>, t: T) -> T {
 823     let mut eraser = RegionEraser { tcx: tcx };
 824     t.fold_with(&mut eraser)
 825 }
 826
 827 impl<'a, 'tcx> TypeFolder<'tcx> for RegionEraser<'a, 'tcx> {
 828     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 829
 830     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 831         match r {
 832             ty::ReLateBound(..) | ty::ReEarlyBound(..) => r,
 833             _ => ty::ReStatic
 834         }
 835     }
 836 }
 837
 838 ///////////////////////////////////////////////////////////////////////////
 839 // Region shifter
 840 //
 841 // Shifts the De Bruijn indices on all escaping bound regions by a
 842 // fixed amount. Useful in substitution or when otherwise introducing
 843 // a binding level that is not intended to capture the existing bound
 844 // regions. See comment on `shift_regions_through_binders` method in
 845 // `subst.rs` for more details.
 846
 847 pub fn shift_region(region: ty::Region, amount: uint) -> ty::Region {
 848     match region {
 849         ty::ReLateBound(debruijn, br) => {
 850             ty::ReLateBound(debruijn.shifted(amount), br)
 851         }
 852         _ => {
 853             region
 854         }
 855     }
 856 }
 857
 858 pub fn shift_regions<'tcx, T:TypeFoldable<'tcx>+Repr<'tcx>>(tcx: &ty::ctxt<'tcx>,
 859                                                             amount: uint, value: &T) -> T {
 860     debug!("shift_regions(value={}, amount={})",
 861            value.repr(tcx), amount);
 862
 863     value.fold_with(&mut RegionFolder::new(tcx, |region, _current_depth| {
 864         shift_region(region, amount)
 865     }))
 866 }
 867