Introduce ty_fold mechanism and port our various folders to use

it. This should eventually be merged with the Subst trait.

3 files changed, 411 insertions, 334 deletions

diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index 009745ff2ad..a13248f2480 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -10,10 +10,11 @@
 
 // Type substitutions.
 
-
 use middle::ty;
+use middle::ty_fold;
+use middle::ty_fold::TypeFolder;
 use syntax::opt_vec::OptVec;
-use util::ppaux::Repr;
+use std::at_vec;
 
 ///////////////////////////////////////////////////////////////////////////
 // Public trait `Subst`
@@ -33,39 +34,43 @@ pub trait Subst {
 // to all subst methods but ran into trouble due to the limitations of
 // our current method/trait matching algorithm. - Niko
 
-trait EffectfulSubst {
-    fn effectfulSubst(&self, tcx: ty::ctxt, substs: &ty::substs) -> Self;
-}
-
 impl Subst for ty::t {
     fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::t {
         if ty::substs_is_noop(substs) {
-            return *self;
+            *self
         } else {
-            return self.effectfulSubst(tcx, substs);
+            let mut folder = SubstFolder {tcx: tcx, substs: substs};
+            folder.fold_ty(*self)
         }
     }
 }
 
-impl EffectfulSubst for ty::t {
-    fn effectfulSubst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::t {
-        if !ty::type_needs_subst(*self) {
-            return *self;
+struct SubstFolder<'self> {
+    tcx: ty::ctxt,
+    substs: &'self ty::substs
+}
+
+impl<'self> TypeFolder for SubstFolder<'self> {
+    fn tcx(&self) -> ty::ctxt { self.tcx }
+
+    fn fold_region(&mut self, r: ty::Region) -> ty::Region {
+        r.subst(self.tcx, self.substs)
+    }
+
+    fn fold_ty(&mut self, t: ty::t) -> ty::t {
+        if !ty::type_needs_subst(t) {
+            return t;
         }
 
-        match ty::get(*self).sty {
+        match ty::get(t).sty {
             ty::ty_param(p) => {
-                substs.tps[p.idx]
+                self.substs.tps[p.idx]
             }
             ty::ty_self(_) => {
-                substs.self_ty.expect("ty_self not found in substs")
+                self.substs.self_ty.expect("ty_self not found in substs")
             }
             _ => {
-                ty::fold_regions_and_ty(
-                    tcx, *self,
-                    |r| r.subst(tcx, substs),
-                    |t| t.effectfulSubst(tcx, substs),
-                    |t| t.effectfulSubst(tcx, substs))
+                ty_fold::super_fold_ty(self, t)
             }
         }
     }
@@ -80,6 +85,12 @@ impl<T:Subst> Subst for ~[T] {
     }
 }
 
+impl<T:Subst> Subst for @[T] {
+    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> @[T] {
+        at_vec::map(*self, |t| t.subst(tcx, substs))
+    }
+}
+
 impl<T:Subst> Subst for OptVec<T> {
     fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> OptVec<T> {
         self.map(|t| t.subst(tcx, substs))
@@ -134,7 +145,8 @@ impl Subst for ty::RegionSubsts {
 
 impl Subst for ty::BareFnTy {
     fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::BareFnTy {
-        ty::fold_bare_fn_ty(self, |t| t.subst(tcx, substs))
+        let mut folder = SubstFolder {tcx: tcx, substs: substs};
+        folder.fold_bare_fn_ty(self)
     }
 }
 
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 09f24b327f4..9d6ad4d8bf6 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -21,6 +21,8 @@ use middle::resolve_lifetime;
 use middle::ty;
 use middle::subst::Subst;
 use middle::typeck;
+use middle::ty_fold;
+use middle::ty_fold::TypeFolder;
 use middle;
 use util::ppaux::{note_and_explain_region, bound_region_ptr_to_str};
 use util::ppaux::{trait_store_to_str, ty_to_str, vstore_to_str};
@@ -983,7 +985,7 @@ pub fn mk_ctxt(s: session::Session,
 
 // Interns a type/name combination, stores the resulting box in cx.interner,
 // and returns the box as cast to an unsafe ptr (see comments for t above).
-fn mk_t(cx: ctxt, st: sty) -> t {
+pub fn mk_t(cx: ctxt, st: sty) -> t {
     // Check for primitive types.
     match st {
         ty_nil => return mk_nil(),
@@ -992,6 +994,8 @@ fn mk_t(cx: ctxt, st: sty) -> t {
         ty_int(i) => return mk_mach_int(i),
         ty_uint(u) => return mk_mach_uint(u),
         ty_float(f) => return mk_mach_float(f),
+        ty_char => return mk_char(),
+        ty_bot => return mk_bot(),
         _ => {}
     };
 
@@ -1338,224 +1342,70 @@ pub fn maybe_walk_ty(ty: t, f: &fn(t) -> bool) {
     }
 }
 
-pub fn fold_sty_to_ty(tcx: ty::ctxt, sty: &sty, foldop: &fn(t) -> t) -> t {
-    mk_t(tcx, fold_sty(sty, foldop))
+// Folds types from the bottom up.
+pub fn fold_ty(cx: ctxt, t0: t, fldop: &fn(t) -> t) -> t {
+    let mut f = ty_fold::BottomUpFolder {tcx: cx, fldop: fldop};
+    f.fold_ty(t0)
 }
 
-pub fn fold_sig(sig: &FnSig, fldop: &fn(t) -> t) -> FnSig {
-    let args = sig.inputs.map(|arg| fldop(*arg));
-
-    FnSig {
-        bound_lifetime_names: sig.bound_lifetime_names.clone(),
-        inputs: args,
-        output: fldop(sig.output),
-        variadic: sig.variadic
-    }
+pub fn walk_regions_and_ty(cx: ctxt,
+                           ty: t,
+                           fldr: &fn(r: Region),
+                           fldt: &fn(t: t))
+                           -> t {
+    ty_fold::RegionFolder::general(cx,
+                                   |r| { fldr(r); r },
+                                   |t| { fldt(t); t }).fold_ty(ty)
 }
 
-pub fn fold_bare_fn_ty(fty: &BareFnTy, fldop: &fn(t) -> t) -> BareFnTy {
-    BareFnTy {sig: fold_sig(&fty.sig, fldop),
-              abis: fty.abis,
-              purity: fty.purity}
+pub fn fold_regions(cx: ctxt,
+                    ty: t,
+                    fldr: &fn(r: Region) -> Region)
+                    -> t {
+    ty_fold::RegionFolder::regions(cx, fldr).fold_ty(ty)
 }
 
-fn fold_sty(sty: &sty, fldop: &fn(t) -> t) -> sty {
-    fn fold_substs(substs: &substs, fldop: &fn(t) -> t) -> substs {
-        substs {regions: substs.regions.clone(),
-                self_ty: substs.self_ty.map(|t| fldop(t)),
-                tps: substs.tps.map(|t| fldop(*t))}
-    }
+// Substitute *only* type parameters.  Used in trans where regions are erased.
+pub fn subst_tps(tcx: ctxt, tps: &[t], self_ty_opt: Option<t>, typ: t) -> t {
+    let mut subst = TpsSubst { tcx: tcx, self_ty_opt: self_ty_opt, tps: tps };
+    return subst.fold_ty(typ);
 
-    match *sty {
-        ty_box(ref tm) => {
-            ty_box(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
-        }
-        ty_uniq(ref tm) => {
-            ty_uniq(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
-        }
-        ty_ptr(ref tm) => {
-            ty_ptr(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
-        }
-        ty_unboxed_vec(ref tm) => {
-            ty_unboxed_vec(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
-        }
-        ty_evec(ref tm, vst) => {
-            ty_evec(mt {ty: fldop(tm.ty), mutbl: tm.mutbl}, vst)
-        }
-        ty_enum(tid, ref substs) => {
-            ty_enum(tid, fold_substs(substs, fldop))
-        }
-        ty_trait(did, ref substs, st, mutbl, bounds) => {
-            ty_trait(did, fold_substs(substs, fldop), st, mutbl, bounds)
-        }
-        ty_tup(ref ts) => {
-            let new_ts = ts.map(|tt| fldop(*tt));
-            ty_tup(new_ts)
-        }
-        ty_bare_fn(ref f) => {
-            ty_bare_fn(fold_bare_fn_ty(f, fldop))
-        }
-        ty_closure(ref f) => {
-            let sig = fold_sig(&f.sig, fldop);
-            ty_closure(ClosureTy {
-                sig: sig,
-                purity: f.purity,
-                sigil: f.sigil,
-                onceness: f.onceness,
-                region: f.region,
-                bounds: f.bounds,
-            })
-        }
-        ty_rptr(r, ref tm) => {
-            ty_rptr(r, mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
-        }
-        ty_struct(did, ref substs) => {
-            ty_struct(did, fold_substs(substs, fldop))
-        }
-        ty_nil | ty_bot | ty_bool | ty_char | ty_int(_) | ty_uint(_) | ty_float(_) |
-        ty_estr(_) | ty_type | ty_opaque_closure_ptr(_) | ty_err |
-        ty_opaque_box | ty_infer(_) | ty_param(*) | ty_self(_) => {
-            (*sty).clone()
-        }
+    pub struct TpsSubst<'self> {
+        tcx: ctxt,
+        self_ty_opt: Option<t>,
+        tps: &'self [t],
     }
-}
 
-// Folds types from the bottom up.
-pub fn fold_ty(cx: ctxt, t0: t, fldop: &fn(t) -> t) -> t {
-    let sty = fold_sty(&get(t0).sty, |t| fold_ty(cx, fldop(t), |t| fldop(t)));
-    fldop(mk_t(cx, sty))
-}
-
-pub fn walk_regions_and_ty(
-    cx: ctxt,
-    ty: t,
-    walkr: &fn(r: Region),
-    walkt: &fn(t: t) -> bool) {
-
-    if (walkt(ty)) {
-        fold_regions_and_ty(
-            cx, ty,
-            |r| { walkr(r); r },
-            |t| { walk_regions_and_ty(cx, t, |r| walkr(r), |t| walkt(t)); t },
-            |t| { walk_regions_and_ty(cx, t, |r| walkr(r), |t| walkt(t)); t });
-    }
-}
+    impl<'self> TypeFolder for TpsSubst<'self> {
+        fn tcx(&self) -> ty::ctxt { self.tcx }
 
-pub fn fold_regions_and_ty(
-    cx: ctxt,
-    ty: t,
-    fldr: &fn(r: Region) -> Region,
-    fldfnt: &fn(t: t) -> t,
-    fldt: &fn(t: t) -> t) -> t {
-
-    fn fold_substs(
-        substs: &substs,
-        fldr: &fn(r: Region) -> Region,
-        fldt: &fn(t: t) -> t)
-     -> substs {
-        let regions = match substs.regions {
-            ErasedRegions => ErasedRegions,
-            NonerasedRegions(ref regions) => {
-                NonerasedRegions(regions.map(|r| fldr(*r)))
+        fn fold_ty(&mut self, t: ty::t) -> ty::t {
+            if self.tps.len() == 0u && self.self_ty_opt.is_none() {
+                return t;
             }
-        };
 
-        substs {
-            regions: regions,
-            self_ty: substs.self_ty.map(|t| fldt(t)),
-            tps: substs.tps.map(|t| fldt(*t))
-        }
-    }
+            let tb = ty::get(t);
+            if self.self_ty_opt.is_none() && !tbox_has_flag(tb, has_params) {
+                return t;
+            }
 
-    let tb = ty::get(ty);
-    match tb.sty {
-      ty::ty_rptr(r, mt) => {
-        let m_r = fldr(r);
-        let m_t = fldt(mt.ty);
-        ty::mk_rptr(cx, m_r, mt {ty: m_t, mutbl: mt.mutbl})
-      }
-      ty_estr(vstore_slice(r)) => {
-        let m_r = fldr(r);
-        ty::mk_estr(cx, vstore_slice(m_r))
-      }
-      ty_evec(mt, vstore_slice(r)) => {
-        let m_r = fldr(r);
-        let m_t = fldt(mt.ty);
-        ty::mk_evec(cx, mt {ty: m_t, mutbl: mt.mutbl}, vstore_slice(m_r))
-      }
-      ty_enum(def_id, ref substs) => {
-        ty::mk_enum(cx, def_id, fold_substs(substs, fldr, fldt))
-      }
-      ty_struct(def_id, ref substs) => {
-        ty::mk_struct(cx, def_id, fold_substs(substs, fldr, fldt))
-      }
-      ty_trait(def_id, ref substs, st, mutbl, bounds) => {
-        let st = match st {
-            RegionTraitStore(region) => RegionTraitStore(fldr(region)),
-            st => st,
-        };
-        ty::mk_trait(cx, def_id, fold_substs(substs, fldr, fldt), st, mutbl, bounds)
-      }
-      ty_bare_fn(ref f) => {
-          ty::mk_bare_fn(cx, BareFnTy {
-            sig: fold_sig(&f.sig, fldfnt),
-            purity: f.purity,
-            abis: f.abis.clone(),
-          })
-      }
-      ty_closure(ref f) => {
-          ty::mk_closure(cx, ClosureTy {
-            region: fldr(f.region),
-            sig: fold_sig(&f.sig, fldfnt),
-            purity: f.purity,
-            sigil: f.sigil,
-            onceness: f.onceness,
-            bounds: f.bounds,
-          })
-      }
-      ref sty => {
-        fold_sty_to_ty(cx, sty, |t| fldt(t))
-      }
-    }
-}
+            match ty::get(t).sty {
+                ty_param(p) => {
+                    self.tps[p.idx]
+                }
 
-// n.b. this function is intended to eventually replace fold_region() below,
-// that is why its name is so similar.
-pub fn fold_regions(
-    cx: ctxt,
-    ty: t,
-    fldr: &fn(r: Region, in_fn: bool) -> Region) -> t {
-    fn do_fold(cx: ctxt, ty: t, in_fn: bool,
-               fldr: &fn(Region, bool) -> Region) -> t {
-        debug!("do_fold(ty={}, in_fn={})", ty_to_str(cx, ty), in_fn);
-        if !type_has_regions(ty) { return ty; }
-        fold_regions_and_ty(
-            cx, ty,
-            |r| fldr(r, in_fn),
-            |t| do_fold(cx, t, true,  |r,b| fldr(r,b)),
-            |t| do_fold(cx, t, in_fn, |r,b| fldr(r,b)))
-    }
-    do_fold(cx, ty, false, fldr)
-}
+                ty_self(_) => {
+                    match self.self_ty_opt {
+                        None => self.tcx.sess.bug("ty_self unexpected here"),
+                        Some(self_ty) => self_ty
+                    }
+                }
 
-// Substitute *only* type parameters.  Used in trans where regions are erased.
-pub fn subst_tps(cx: ctxt, tps: &[t], self_ty_opt: Option<t>, typ: t) -> t {
-    if tps.len() == 0u && self_ty_opt.is_none() { return typ; }
-    let tb = ty::get(typ);
-    if self_ty_opt.is_none() && !tbox_has_flag(tb, has_params) { return typ; }
-    match tb.sty {
-        ty_param(p) => tps[p.idx],
-        ty_self(_) => {
-            match self_ty_opt {
-                None => cx.sess.bug("ty_self unexpected here"),
-                Some(self_ty) => {
-                    subst_tps(cx, tps, self_ty_opt, self_ty)
+                _ => {
+                    ty_fold::super_fold_ty(self, t)
                 }
             }
         }
-        ref sty => {
-            fold_sty_to_ty(cx, sty, |t| subst_tps(cx, tps, self_ty_opt, t))
-        }
     }
 }
 
@@ -2727,55 +2577,6 @@ pub fn index_sty(sty: &sty) -> Option<mt> {
     }
 }
 
-/**
- * Enforces an arbitrary but consistent total ordering over
- * free regions.  This is needed for establishing a consistent
- * LUB in region_inference. */
-impl cmp::TotalOrd for FreeRegion {
-    fn cmp(&self, other: &FreeRegion) -> Ordering {
-        cmp::cmp2(&self.scope_id, &self.bound_region,
-                  &other.scope_id, &other.bound_region)
-    }
-}
-
-impl cmp::TotalEq for FreeRegion {
-    fn equals(&self, other: &FreeRegion) -> bool {
-        *self == *other
-    }
-}
-
-/**
- * Enforces an arbitrary but consistent total ordering over
- * bound regions.  This is needed for establishing a consistent
- * LUB in region_inference. */
-impl cmp::TotalOrd for bound_region {
-    fn cmp(&self, other: &bound_region) -> Ordering {
-        match (self, other) {
-            (&ty::br_self, &ty::br_self) => cmp::Equal,
-            (&ty::br_self, _) => cmp::Less,
-
-            (&ty::br_anon(ref a1), &ty::br_anon(ref a2)) => a1.cmp(a2),
-            (&ty::br_anon(*), _) => cmp::Less,
-
-            (&ty::br_named(ref a1), &ty::br_named(ref a2)) => a1.name.cmp(&a2.name),
-            (&ty::br_named(*), _) => cmp::Less,
-
-            (&ty::br_cap_avoid(ref a1, @ref b1),
-             &ty::br_cap_avoid(ref a2, @ref b2)) => cmp::cmp2(a1, b1, a2, b2),
-            (&ty::br_cap_avoid(*), _) => cmp::Less,
-
-            (&ty::br_fresh(ref a1), &ty::br_fresh(ref a2)) => a1.cmp(a2),
-            (&ty::br_fresh(*), _) => cmp::Less,
-        }
-    }
-}
-
-impl cmp::TotalEq for bound_region {
-    fn equals(&self, other: &bound_region) -> bool {
-        *self == *other
-    }
-}
-
 pub fn node_id_to_trait_ref(cx: ctxt, id: ast::NodeId) -> @ty::TraitRef {
     match cx.trait_refs.find(&id) {
        Some(&t) => t,
@@ -3684,7 +3485,6 @@ fn lookup_locally_or_in_crate_store<V:Clone>(
     load_external: &fn() -> V) -> V
 {
     /*!
-     *
      * Helper for looking things up in the various maps
      * that are populated during typeck::collect (e.g.,
      * `cx.methods`, `cx.tcache`, etc).  All of these share
@@ -3694,8 +3494,8 @@ fn lookup_locally_or_in_crate_store<V:Clone>(
      * the crate loading code (and cache the result for the future).
      */
 
-    match map.find(&def_id) {
-        Some(&ref v) => { return (*v).clone(); }
+    match map.find_copy(&def_id) {
+        Some(v) => { return v; }
         None => { }
     }
 
@@ -3733,7 +3533,7 @@ pub fn method(cx: ctxt, id: ast::DefId) -> @Method {
 
 pub fn trait_method_def_ids(cx: ctxt, id: ast::DefId) -> @~[DefId] {
     lookup_locally_or_in_crate_store(
-        "methods", id, cx.trait_method_def_ids,
+        "trait_method_def_ids", id, cx.trait_method_def_ids,
         || @csearch::get_trait_method_def_ids(cx.cstore, id))
 }
 
@@ -4359,77 +4159,56 @@ pub fn ty_params_to_tys(tcx: ty::ctxt, generics: &ast::Generics) -> ~[t] {
 
 /// Returns an equivalent type with all the typedefs and self regions removed.
 pub fn normalize_ty(cx: ctxt, t: t) -> t {
-    fn normalize_mt(cx: ctxt, mt: mt) -> mt {
-        mt { ty: normalize_ty(cx, mt.ty), mutbl: mt.mutbl }
-    }
-    fn normalize_vstore(vstore: vstore) -> vstore {
-        match vstore {
-            vstore_fixed(*) | vstore_uniq | vstore_box => vstore,
-            vstore_slice(_) => vstore_slice(re_static)
-        }
-    }
-
-    match cx.normalized_cache.find(&t) {
-      Some(&t) => return t,
-      None => ()
-    }
-
-    let t = match get(t).sty {
-        ty_evec(mt, vstore) =>
-            // This type has a vstore. Get rid of it
-            mk_evec(cx, normalize_mt(cx, mt), normalize_vstore(vstore)),
+    let u = TypeNormalizer(cx).fold_ty(t);
+    return u;
 
-        ty_estr(vstore) =>
-            // This type has a vstore. Get rid of it
-            mk_estr(cx, normalize_vstore(vstore)),
+    struct TypeNormalizer(ctxt);
 
-        ty_rptr(_, mt) =>
-            // This type has a region. Get rid of it
-            mk_rptr(cx, re_static, normalize_mt(cx, mt)),
+    impl TypeFolder for TypeNormalizer {
+        fn tcx(&self) -> ty::ctxt { **self }
 
-        ty_closure(ref closure_ty) => {
-            mk_closure(cx, ClosureTy {
-                region: ty::re_static,
-                ..(*closure_ty).clone()
-            })
-        }
-
-        ty_enum(did, ref r) => {
-            match (*r).regions {
-                NonerasedRegions(_) => {
-                    // trans doesn't care about regions
-                    mk_enum(cx, did, substs {regions: ty::ErasedRegions,
-                                             self_ty: None,
-                                             tps: (*r).tps.clone()})
+        fn fold_ty(&mut self, t: ty::t) -> ty::t {
+            match self.tcx().normalized_cache.find_copy(&t) {
+                Some(u) => {
+                    return u;
                 }
-                ErasedRegions => {
-                    t
+                None => {
+                    let t_norm = ty_fold::super_fold_ty(self, t);
+                    self.tcx().normalized_cache.insert(t, t_norm);
+                    return t_norm;
                 }
             }
         }
 
-        ty_struct(did, ref r) => {
-            match (*r).regions {
-                NonerasedRegions(_) => {
-                    // Ditto.
-                    mk_struct(cx, did, substs {regions: ty::ErasedRegions,
-                                               self_ty: None,
-                                               tps: (*r).tps.clone()})
-                }
-                ErasedRegions => {
-                    t
-                }
+        fn fold_vstore(&mut self, vstore: vstore) -> vstore {
+            match vstore {
+                vstore_fixed(*) | vstore_uniq | vstore_box => vstore,
+                vstore_slice(_) => vstore_slice(re_static)
             }
         }
 
-        _ =>
-            t
-    };
+        fn fold_region(&mut self, _: ty::Region) -> ty::Region {
+            ty::re_static
+        }
+
+        fn fold_substs(&mut self,
+                       substs: &substs)
+                       -> substs {
+            substs { regions: ErasedRegions,
+                     self_ty: ty_fold::fold_opt_ty(self, substs.self_ty),
+                     tps: ty_fold::fold_ty_vec(self, substs.tps) }
+        }
 
-    let sty = fold_sty(&get(t).sty, |t| { normalize_ty(cx, t) });
-    let t_norm = mk_t(cx, sty);
-    cx.normalized_cache.insert(t, t_norm);
-    return t_norm;
+        fn fold_sig(&mut self,
+                    sig: &ty::FnSig)
+                    -> ty::FnSig {
+            // The binder-id is only relevant to bound regions, which
+            // are erased at trans time.
+            ty::FnSig { binder_id: ast::DUMMY_NODE_ID,
+                        inputs: ty_fold::fold_ty_vec(self, sig.inputs),
+                        output: self.fold_ty(sig.output) }
+        }
+    }
 }
 
 pub trait ExprTyProvider {
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
new file mode 100644
index 00000000000..dc4fca0176a
--- /dev/null
+++ b/src/librustc/middle/ty_fold.rs
@@ -0,0 +1,286 @@
+// Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Generalized type folding mechanism.
+
+use middle::ty;
+use util::ppaux::Repr;
+
+pub trait TypeFolder {
+    fn tcx(&self) -> ty::ctxt;
+
+    fn fold_ty(&mut self, t: ty::t) -> ty::t {
+        super_fold_ty(self, t)
+    }
+
+    fn fold_mt(&mut self, t: &ty::mt) -> ty::mt {
+        super_fold_mt(self, t)
+    }
+
+    fn fold_trait_ref(&mut self, t: &ty::TraitRef) -> ty::TraitRef {
+        super_fold_trait_ref(self, t)
+    }
+
+    fn fold_sty(&mut self, sty: &ty::sty) -> ty::sty {
+        super_fold_sty(self, sty)
+    }
+
+    fn fold_substs(&mut self,
+                   substs: &ty::substs)
+                   -> ty::substs {
+        super_fold_substs(self, substs)
+    }
+
+    fn fold_sig(&mut self,
+                sig: &ty::FnSig)
+                -> ty::FnSig {
+        super_fold_sig(self, sig)
+    }
+
+    fn fold_bare_fn_ty(&mut self,
+                       fty: &ty::BareFnTy)
+                       -> ty::BareFnTy {
+        ty::BareFnTy { sig: self.fold_sig(&fty.sig),
+                       abis: fty.abis,
+                       purity: fty.purity }
+    }
+
+    fn fold_closure_ty(&mut self,
+                       fty: &ty::ClosureTy)
+                       -> ty::ClosureTy {
+        ty::ClosureTy {
+            region: self.fold_region(fty.region),
+            sig: self.fold_sig(&fty.sig),
+            purity: fty.purity,
+            sigil: fty.sigil,
+            onceness: fty.onceness,
+            bounds: fty.bounds,
+        }
+    }
+
+    fn fold_region(&mut self, r: ty::Region) -> ty::Region {
+        r
+    }
+
+    fn fold_vstore(&mut self, vstore: ty::vstore) -> ty::vstore {
+        super_fold_vstore(self, vstore)
+    }
+
+    fn fold_trait_store(&mut self, s: ty::TraitStore) -> ty::TraitStore {
+        super_fold_trait_store(self, s)
+    }
+}
+
+pub fn fold_opt_ty<T:TypeFolder>(this: &mut T,
+                                 t: Option<ty::t>)
+                                 -> Option<ty::t> {
+    t.map(|t| this.fold_ty(t))
+}
+
+pub fn fold_ty_vec<T:TypeFolder>(this: &mut T,
+                                 tys: &[ty::t])
+                                 -> ~[ty::t] {
+    tys.map(|t| this.fold_ty(*t))
+}
+
+pub fn super_fold_ty<T:TypeFolder>(this: &mut T,
+                                   t: ty::t)
+                                   -> ty::t {
+    ty::mk_t(this.tcx(), this.fold_sty(&ty::get(t).sty))
+}
+
+pub fn super_fold_substs<T:TypeFolder>(this: &mut T,
+                                       substs: &ty::substs)
+                                       -> ty::substs {
+    let regions = match substs.regions {
+        ty::ErasedRegions => {
+            ty::ErasedRegions
+        }
+        ty::NonerasedRegions(ref regions) => {
+            ty::NonerasedRegions(regions.map(|r| this.fold_region(*r)))
+        }
+    };
+
+    ty::substs { regions: regions,
+                 self_ty: fold_opt_ty(this, substs.self_ty),
+                 tps: fold_ty_vec(this, substs.tps), }
+}
+
+pub fn super_fold_sig<T:TypeFolder>(this: &mut T,
+                                    sig: &ty::FnSig)
+                                    -> ty::FnSig {
+    ty::FnSig { binder_id: sig.binder_id,
+                inputs: fold_ty_vec(this, sig.inputs),
+                output: this.fold_ty(sig.output),
+                variadic: sig.variadic }
+}
+
+pub fn super_fold_trait_ref<T:TypeFolder>(this: &mut T,
+                                          t: &ty::TraitRef)
+                                          -> ty::TraitRef {
+    ty::TraitRef {
+        def_id: t.def_id,
+        substs: this.fold_substs(&t.substs)
+    }
+}
+
+pub fn super_fold_mt<T:TypeFolder>(this: &mut T,
+                                   mt: &ty::mt) -> ty::mt {
+    ty::mt {ty: this.fold_ty(mt.ty),
+            mutbl: mt.mutbl}
+}
+
+pub fn super_fold_sty<T:TypeFolder>(this: &mut T,
+                                    sty: &ty::sty) -> ty::sty {
+    match *sty {
+        ty::ty_box(ref tm) => {
+            ty::ty_box(this.fold_mt(tm))
+        }
+        ty::ty_uniq(ref tm) => {
+            ty::ty_uniq(this.fold_mt(tm))
+        }
+        ty::ty_ptr(ref tm) => {
+            ty::ty_ptr(this.fold_mt(tm))
+        }
+        ty::ty_unboxed_vec(ref tm) => {
+            ty::ty_unboxed_vec(this.fold_mt(tm))
+        }
+        ty::ty_evec(ref tm, vst) => {
+            ty::ty_evec(this.fold_mt(tm),
+                        this.fold_vstore(vst))
+        }
+        ty::ty_enum(tid, ref substs) => {
+            ty::ty_enum(tid, this.fold_substs(substs))
+        }
+        ty::ty_trait(did, ref substs, st, mutbl, bounds) => {
+            ty::ty_trait(did,
+                     this.fold_substs(substs),
+                     this.fold_trait_store(st),
+                     mutbl,
+                     bounds)
+        }
+        ty::ty_tup(ref ts) => {
+            ty::ty_tup(fold_ty_vec(this, *ts))
+        }
+        ty::ty_bare_fn(ref f) => {
+            ty::ty_bare_fn(this.fold_bare_fn_ty(f))
+        }
+        ty::ty_closure(ref f) => {
+            ty::ty_closure(this.fold_closure_ty(f))
+        }
+        ty::ty_rptr(r, ref tm) => {
+            ty::ty_rptr(this.fold_region(r),
+                        ty::mt {ty: this.fold_ty(tm.ty),
+                                mutbl: tm.mutbl})
+        }
+        ty::ty_struct(did, ref substs) => {
+            ty::ty_struct(did,
+                          this.fold_substs(substs))
+        }
+        ty::ty_estr(vst) => {
+            ty::ty_estr(this.fold_vstore(vst))
+        }
+        ty::ty_nil | ty::ty_bot | ty::ty_bool | ty::ty_char |
+        ty::ty_int(_) | ty::ty_uint(_) |
+        ty::ty_float(_) | ty::ty_type |
+        ty::ty_opaque_closure_ptr(_) |
+        ty::ty_err | ty::ty_opaque_box | ty::ty_infer(_) |
+        ty::ty_param(*) | ty::ty_self(_) => {
+            (*sty).clone()
+        }
+    }
+}
+
+pub fn super_fold_vstore<T:TypeFolder>(this: &mut T,
+                                       vstore: ty::vstore)
+                                       -> ty::vstore {
+    match vstore {
+        ty::vstore_fixed(i) => ty::vstore_fixed(i),
+        ty::vstore_uniq => ty::vstore_uniq,
+        ty::vstore_box => ty::vstore_box,
+        ty::vstore_slice(r) => ty::vstore_slice(this.fold_region(r)),
+    }
+}
+
+pub fn super_fold_trait_store<T:TypeFolder>(this: &mut T,
+                                            trait_store: ty::TraitStore)
+                                            -> ty::TraitStore {
+    match trait_store {
+        ty::UniqTraitStore      => ty::UniqTraitStore,
+        ty::BoxTraitStore       => ty::BoxTraitStore,
+        ty::RegionTraitStore(r) => ty::RegionTraitStore(this.fold_region(r)),
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
+// Some sample folders
+
+pub struct BottomUpFolder<'self> {
+    tcx: ty::ctxt,
+    fldop: &'self fn(ty::t) -> ty::t,
+}
+
+impl<'self> TypeFolder for BottomUpFolder<'self> {
+    fn tcx(&self) -> ty::ctxt { self.tcx }
+
+    fn fold_ty(&mut self, ty: ty::t) -> ty::t {
+        let t1 = super_fold_ty(self, ty);
+        (self.fldop)(t1)
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
+// Region folder
+
+pub struct RegionFolder<'self> {
+    tcx: ty::ctxt,
+    fld_t: &'self fn(ty::t) -> ty::t,
+    fld_r: &'self fn(ty::Region) -> ty::Region,
+}
+
+impl<'self> RegionFolder<'self> {
+    pub fn general(tcx: ty::ctxt,
+                   fld_r: &'self fn(ty::Region) -> ty::Region,
+                   fld_t: &'self fn(ty::t) -> ty::t)
+                   -> RegionFolder<'self> {
+        RegionFolder {
+            tcx: tcx,
+            fld_t: fld_t,
+            fld_r: fld_r
+        }
+    }
+
+    pub fn regions(tcx: ty::ctxt,
+                   fld_r: &'self fn(ty::Region) -> ty::Region)
+                   -> RegionFolder<'self> {
+        fn noop(t: ty::t) -> ty::t { t }
+
+        RegionFolder {
+            tcx: tcx,
+            fld_t: noop,
+            fld_r: fld_r
+        }
+    }
+}
+
+impl<'self> TypeFolder for RegionFolder<'self> {
+    fn tcx(&self) -> ty::ctxt { self.tcx }
+
+    fn fold_ty(&mut self, ty: ty::t) -> ty::t {
+        debug!("RegionFolder.fold_ty({})", ty.repr(self.tcx()));
+        let t1 = super_fold_ty(self, ty);
+        (self.fld_t)(t1)
+    }
+
+    fn fold_region(&mut self, r: ty::Region) -> ty::Region {
+        debug!("RegionFolder.fold_region({})", r.repr(self.tcx()));
+        (self.fld_r)(r)
+    }
+}