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