make nominal types optionally parameterized by a self region.

Issue #2201.

45 files changed, 1326 insertions, 934 deletions

diff --git a/src/librustsyntax/ast.rs b/src/librustsyntax/ast.rs
index 477a22773da..ff581b6dbf5 100644
--- a/src/librustsyntax/ast.rs
+++ b/src/librustsyntax/ast.rs
@@ -646,20 +646,28 @@ type item = {ident: ident, attrs: [attribute],
              id: node_id, node: item_, span: span};
 
 #[auto_serialize]
+enum region_param {
+    rp_none,
+    rp_self
+}
+
+#[auto_serialize]
 enum item_ {
     item_const(@ty, @expr),
     item_fn(fn_decl, [ty_param], blk),
     item_mod(_mod),
     item_native_mod(native_mod),
-    item_ty(@ty, [ty_param]),
-    item_enum([variant], [ty_param]),
+    item_ty(@ty, [ty_param], region_param),
+    item_enum([variant], [ty_param], region_param),
     item_res(fn_decl /* dtor */, [ty_param], blk /* dtor body */,
-             node_id /* dtor id */, node_id /* ctor id */),
+             node_id /* dtor id */, node_id /* ctor id */,
+             region_param),
     item_class([ty_param], /* ty params for class */
                [iface_ref],   /* ifaces this class implements */
                [@class_member], /* methods, etc. */
                                /* (not including ctor) */
-               class_ctor
+               class_ctor,
+               region_param
                ),
     item_iface([ty_param], [ty_method]),
     item_impl([ty_param], option<@ty> /* iface */,
diff --git a/src/librustsyntax/ast_util.rs b/src/librustsyntax/ast_util.rs
index db7d753fffd..ddfb9e6de16 100644
--- a/src/librustsyntax/ast_util.rs
+++ b/src/librustsyntax/ast_util.rs
@@ -149,7 +149,7 @@ fn is_exported(i: ident, m: _mod) -> bool {
     for m.items.each {|it|
         if it.ident == i { local = true; }
         alt it.node {
-          item_enum(variants, _) {
+          item_enum(variants, _, _) {
             for variants.each {|v|
                 if v.node.name == i {
                    local = true;
diff --git a/src/librustsyntax/ext/auto_serialize.rs b/src/librustsyntax/ext/auto_serialize.rs
index c834692b5b0..a6700b566a3 100644
--- a/src/librustsyntax/ext/auto_serialize.rs
+++ b/src/librustsyntax/ext/auto_serialize.rs
@@ -102,11 +102,11 @@ fn expand(cx: ext_ctxt,
 
     vec::flat_map(in_items) {|in_item|
         alt in_item.node {
-          ast::item_ty(ty, tps) {
+          ast::item_ty(ty, tps, _) {
             [filter_attrs(in_item)] + ty_fns(cx, in_item.ident, ty, tps)
           }
 
-          ast::item_enum(variants, tps) {
+          ast::item_enum(variants, tps, _) {
             [filter_attrs(in_item)] + enum_fns(cx, in_item.ident,
                                                in_item.span, variants, tps)
           }
diff --git a/src/librustsyntax/fold.rs b/src/librustsyntax/fold.rs
index 5658aef8a7e..6e4d89eb5c0 100644
--- a/src/librustsyntax/fold.rs
+++ b/src/librustsyntax/fold.rs
@@ -265,36 +265,42 @@ fn noop_fold_item_underscore(i: item_, fld: ast_fold) -> item_ {
           }
           item_mod(m) { item_mod(fld.fold_mod(m)) }
           item_native_mod(nm) { item_native_mod(fld.fold_native_mod(nm)) }
-          item_ty(t, typms) { item_ty(fld.fold_ty(t),
-                                      fold_ty_params(typms, fld)) }
-          item_enum(variants, typms) {
+          item_ty(t, typms, rp) { item_ty(fld.fold_ty(t),
+                                          fold_ty_params(typms, fld),
+                                          rp) }
+          item_enum(variants, typms, r) {
             item_enum(vec::map(variants, fld.fold_variant),
-                      fold_ty_params(typms, fld))
+                      fold_ty_params(typms, fld),
+                      r)
           }
-          item_class(typms, ifaces, items, ctor) {
+          item_class(typms, ifaces, items, ctor, rp) {
               let ctor_body = fld.fold_block(ctor.node.body);
               let ctor_decl = fold_fn_decl(ctor.node.dec, fld);
               let ctor_id   = fld.new_id(ctor.node.id);
-              item_class(typms, vec::map(ifaces, {|p|
-                              {path: fld.fold_path(p.path),
-                               id: fld.new_id(p.id)}}),
-                         vec::map(items, fld.fold_class_item),
-                         {node: {body: ctor_body,
-                                 dec: ctor_decl,
-                                 id: ctor_id with ctor.node}
-                             with ctor})
+              item_class(
+                  typms,
+                  vec::map(ifaces, {|p|
+                      {path: fld.fold_path(p.path),
+                       id: fld.new_id(p.id)}}),
+                  vec::map(items, fld.fold_class_item),
+                  {node: {body: ctor_body,
+                          dec: ctor_decl,
+                          id: ctor_id with ctor.node}
+                   with ctor},
+                  rp)
           }
           item_impl(tps, ifce, ty, methods) {
             item_impl(tps, option::map(ifce, fld.fold_ty), fld.fold_ty(ty),
                       vec::map(methods, fld.fold_method))
           }
           item_iface(tps, methods) { item_iface(tps, methods) }
-          item_res(decl, typms, body, did, cid) {
+          item_res(decl, typms, body, did, cid, rp) {
             item_res(fold_fn_decl(decl, fld),
                      fold_ty_params(typms, fld),
                      fld.fold_block(body),
                      fld.new_id(did),
-                     fld.new_id(cid))
+                     fld.new_id(cid),
+                     rp)
           }
         };
 }
diff --git a/src/librustsyntax/parse/parser.rs b/src/librustsyntax/parse/parser.rs
index ae2e2e9a184..8b1fc2d6ada 100644
--- a/src/librustsyntax/parse/parser.rs
+++ b/src/librustsyntax/parse/parser.rs
@@ -1992,6 +1992,7 @@ fn parse_item_impl(p: parser, attrs: [ast::attribute]) -> @ast::item {
 fn parse_item_res(p: parser, attrs: [ast::attribute]) -> @ast::item {
     let lo = p.last_span.lo;
     let ident = parse_value_ident(p);
+    let rp = parse_region_param(p);
     let ty_params = parse_ty_params(p);
     expect(p, token::LPAREN);
     let arg_ident = parse_value_ident(p);
@@ -2010,7 +2011,8 @@ fn parse_item_res(p: parser, attrs: [ast::attribute]) -> @ast::item {
          cf: ast::return_val,
          constraints: []};
     ret mk_item(p, lo, dtor.span.hi, ident,
-                ast::item_res(decl, ty_params, dtor, p.get_id(), p.get_id()),
+                ast::item_res(decl, ty_params, dtor,
+                              p.get_id(), p.get_id(), rp),
                 attrs);
 }
 
@@ -2035,6 +2037,7 @@ fn parse_iface_ref_list(p:parser) -> [ast::iface_ref] {
 fn parse_item_class(p: parser, attrs: [ast::attribute]) -> @ast::item {
     let lo = p.last_span.lo;
     let class_name = parse_value_ident(p);
+    let rp = parse_region_param(p);
     let ty_params = parse_ty_params(p);
     let class_path = ident_to_path_tys(p, class_name, ty_params);
     let ifaces : [ast::iface_ref] = if eat_word(p, "implements")
@@ -2057,11 +2060,11 @@ fn parse_item_class(p: parser, attrs: [ast::attribute]) -> @ast::item {
       some((ct_d, ct_b, ct_s)) {
           ret mk_item(p, lo, p.last_span.hi, class_name,
                       ast::item_class(ty_params, ifaces, ms,
-                         {node: {id: ctor_id,
-                                 self_id: p.get_id(),
-                                 dec: ct_d,
-                                 body: ct_b},
-                          span: ct_s}), attrs); }
+                                      {node: {id: ctor_id,
+                                              self_id: p.get_id(),
+                                              dec: ct_d,
+                                              body: ct_b},
+                                       span: ct_s}, rp), attrs); }
        /*
          Is it strange for the parser to check this?
        */
@@ -2236,17 +2239,23 @@ fn parse_type_decl(p: parser) -> {lo: uint, ident: ast::ident} {
 
 fn parse_item_type(p: parser, attrs: [ast::attribute]) -> @ast::item {
     let t = parse_type_decl(p);
+    let rp = parse_region_param(p);
     let tps = parse_ty_params(p);
     expect(p, token::EQ);
     let ty = parse_ty(p, false);
     let mut hi = p.span.hi;
     expect(p, token::SEMI);
-    ret mk_item(p, t.lo, hi, t.ident, ast::item_ty(ty, tps), attrs);
+    ret mk_item(p, t.lo, hi, t.ident, ast::item_ty(ty, tps, rp), attrs);
+}
+
+fn parse_region_param(p: parser) -> ast::region_param {
+    if eat(p, token::BINOP(token::AND)) {ast::rp_self} else {ast::rp_none}
 }
 
 fn parse_item_enum(p: parser, attrs: [ast::attribute]) -> @ast::item {
     let lo = p.last_span.lo;
     let id = parse_ident(p);
+    let rp = parse_region_param(p);
     let ty_params = parse_ty_params(p);
     let mut variants: [ast::variant] = [];
     // Newtype syntax
@@ -2265,7 +2274,7 @@ fn parse_item_enum(p: parser, attrs: [ast::attribute]) -> @ast::item {
                      id: p.get_id(),
                      disr_expr: none});
         ret mk_item(p, lo, ty.span.hi, id,
-                    ast::item_enum([variant], ty_params), attrs);
+                    ast::item_enum([variant], ty_params, rp), attrs);
     }
     expect(p, token::LBRACE);
 
@@ -2301,7 +2310,7 @@ fn parse_item_enum(p: parser, attrs: [ast::attribute]) -> @ast::item {
         p.fatal("discriminator values can only be used with a c-like enum");
     }
     ret mk_item(p, lo, p.last_span.hi, id,
-                ast::item_enum(variants, ty_params), attrs);
+                ast::item_enum(variants, ty_params, rp), attrs);
 }
 
 fn parse_fn_ty_proto(p: parser) -> ast::proto {
diff --git a/src/librustsyntax/print/pprust.rs b/src/librustsyntax/print/pprust.rs
index 29557785fc7..d5be2d12bc9 100644
--- a/src/librustsyntax/print/pprust.rs
+++ b/src/librustsyntax/print/pprust.rs
@@ -125,10 +125,10 @@ fn test_fun_to_str() {
 }
 
 fn res_to_str(decl: ast::fn_decl, name: ast::ident,
-              params: [ast::ty_param]) -> str {
+              params: [ast::ty_param], rp: ast::region_param) -> str {
     let buffer = io::mem_buffer();
     let s = rust_printer(io::mem_buffer_writer(buffer));
-    print_res(s, decl, name, params);
+    print_res(s, decl, name, params, rp);
     end(s); // Close the head box
     end(s); // Close the outer box
     eof(s.s);
@@ -454,11 +454,12 @@ fn print_item(s: ps, &&item: @ast::item) {
         print_native_mod(s, nmod, item.attrs);
         bclose(s, item.span);
       }
-      ast::item_ty(ty, params) {
+      ast::item_ty(ty, params, rp) {
         ibox(s, indent_unit);
         ibox(s, 0u);
         word_nbsp(s, "type");
         word(s.s, item.ident);
+        print_region_param(s, rp);
         print_type_params(s, params);
         end(s); // end the inner ibox
 
@@ -468,7 +469,7 @@ fn print_item(s: ps, &&item: @ast::item) {
         word(s.s, ";");
         end(s); // end the outer ibox
       }
-      ast::item_enum(variants, params) {
+      ast::item_enum(variants, params, rp) {
         let newtype =
             vec::len(variants) == 1u &&
                 str::eq(item.ident, variants[0].node.name) &&
@@ -478,6 +479,7 @@ fn print_item(s: ps, &&item: @ast::item) {
             word_space(s, "enum");
         } else { head(s, "enum"); }
         word(s.s, item.ident);
+        print_region_param(s, rp);
         print_type_params(s, params);
         space(s.s);
         if newtype {
@@ -500,9 +502,10 @@ fn print_item(s: ps, &&item: @ast::item) {
             bclose(s, item.span);
         }
       }
-      ast::item_class(tps,ifaces,items,ctor) {
+      ast::item_class(tps,ifaces,items,ctor, rp) {
           head(s, "class");
           word_nbsp(s, item.ident);
+          print_region_param(s, rp);
           print_type_params(s, tps);
           word_space(s, "implements");
           commasep(s, inconsistent, ifaces, {|s, p|
@@ -584,8 +587,8 @@ fn print_item(s: ps, &&item: @ast::item) {
         for methods.each {|meth| print_ty_method(s, meth); }
         bclose(s, item.span);
       }
-      ast::item_res(decl, tps, body, dt_id, ct_id) {
-        print_res(s, decl, item.ident, tps);
+      ast::item_res(decl, tps, body, dt_id, ct_id, rp) {
+        print_res(s, decl, item.ident, tps, rp);
         print_block(s, body);
       }
     }
@@ -593,9 +596,10 @@ fn print_item(s: ps, &&item: @ast::item) {
 }
 
 fn print_res(s: ps, decl: ast::fn_decl, name: ast::ident,
-             typarams: [ast::ty_param]) {
+             typarams: [ast::ty_param], rp: ast::region_param) {
     head(s, "resource");
     word(s.s, name);
+    print_region_param(s, rp);
     print_type_params(s, typarams);
     popen(s);
     word_space(s, decl.inputs[0].ident + ":");
@@ -1401,6 +1405,13 @@ fn print_bounds(s: ps, bounds: @[ast::ty_param_bound]) {
     }
 }
 
+fn print_region_param(s: ps, rp: ast::region_param) {
+    alt rp {
+      ast::rp_self { word(s.s, "&") }
+      ast::rp_none { }
+    }
+}
+
 fn print_type_params(s: ps, &&params: [ast::ty_param]) {
     if vec::len(params) > 0u {
         word(s.s, "<");
diff --git a/src/librustsyntax/visit.rs b/src/librustsyntax/visit.rs
index 20d85e08989..8aad3778880 100644
--- a/src/librustsyntax/visit.rs
+++ b/src/librustsyntax/visit.rs
@@ -15,7 +15,7 @@ enum vt<E> { mk_vt(visitor<E>), }
 enum fn_kind {
     fk_item_fn(ident, [ty_param]), //< an item declared with fn()
     fk_method(ident, [ty_param], @method),
-    fk_res(ident, [ty_param]),
+    fk_res(ident, [ty_param], region_param),
     fk_anon(proto),  //< an anonymous function like fn@(...)
     fk_fn_block,     //< a block {||...}
     fk_ctor(ident, [ty_param], node_id /* self id */,
@@ -24,7 +24,7 @@ enum fn_kind {
 
 fn name_of_fn(fk: fn_kind) -> ident {
     alt fk {
-      fk_item_fn(name, _) | fk_method(name, _, _) | fk_res(name, _)
+      fk_item_fn(name, _) | fk_method(name, _, _) | fk_res(name, _, _)
           | fk_ctor(name, _, _, _) { name }
       fk_anon(_) | fk_fn_block { "anon" }
     }
@@ -32,7 +32,7 @@ fn name_of_fn(fk: fn_kind) -> ident {
 
 fn tps_of_fn(fk: fn_kind) -> [ty_param] {
     alt fk {
-      fk_item_fn(_, tps) | fk_method(_, tps, _) | fk_res(_, tps)
+      fk_item_fn(_, tps) | fk_method(_, tps, _) | fk_res(_, tps, _)
           | fk_ctor(_, tps, _, _) { tps }
       fk_anon(_) | fk_fn_block { [] }
     }
@@ -118,12 +118,15 @@ fn visit_item<E>(i: @item, e: E, v: vt<E>) {
         for nm.view_items.each {|vi| v.visit_view_item(vi, e, v); }
         for nm.items.each {|ni| v.visit_native_item(ni, e, v); }
       }
-      item_ty(t, tps) { v.visit_ty(t, e, v); v.visit_ty_params(tps, e, v); }
-      item_res(decl, tps, body, dtor_id, _) {
-        v.visit_fn(fk_res(i.ident, tps), decl, body, i.span,
+      item_ty(t, tps, rp) {
+        v.visit_ty(t, e, v);
+        v.visit_ty_params(tps, e, v);
+      }
+      item_res(decl, tps, body, dtor_id, _, rp) {
+        v.visit_fn(fk_res(i.ident, tps, rp), decl, body, i.span,
                    dtor_id, e, v);
       }
-      item_enum(variants, tps) {
+      item_enum(variants, tps, _) {
         v.visit_ty_params(tps, e, v);
         for variants.each {|vr|
             for vr.node.args.each {|va| v.visit_ty(va.ty, e, v); }
@@ -137,7 +140,7 @@ fn visit_item<E>(i: @item, e: E, v: vt<E>) {
             visit_method_helper(m, e, v)
         }
       }
-      item_class(tps, ifaces, members, ctor) {
+      item_class(tps, ifaces, members, ctor, _) {
           v.visit_ty_params(tps, e, v);
           for members.each {|m|
              v.visit_class_item(m, e, v);
diff --git a/src/rustc/metadata/astencode.rs b/src/rustc/metadata/astencode.rs
index c845eb6c03a..0ef8dfa1243 100644
--- a/src/rustc/metadata/astencode.rs
+++ b/src/rustc/metadata/astencode.rs
@@ -143,8 +143,8 @@ fn visit_ids(item: ast::inlined_item, vfn: fn@(ast::node_id)) {
         visit_item: fn@(i: @ast::item) {
             vfn(i.id);
             alt i.node {
-              ast::item_res(_, _, _, d_id, c_id) { vfn(d_id); vfn(c_id); }
-              ast::item_enum(vs, _) { for vs.each {|v| vfn(v.node.id); } }
+              ast::item_res(_, _, _, d_id, c_id, _) { vfn(d_id); vfn(c_id); }
+              ast::item_enum(vs, _, _) { for vs.each {|v| vfn(v.node.id); } }
               _ {}
             }
         },
@@ -209,7 +209,7 @@ fn visit_ids(item: ast::inlined_item, vfn: fn@(ast::node_id)) {
                 vfn(parent_id.node);
               }
               visit::fk_item_fn(_, tps) |
-              visit::fk_res(_, tps) {
+              visit::fk_res(_, tps, _) {
                 vec::iter(tps) {|tp| vfn(tp.id)}
               }
               visit::fk_method(_, tps, m) {
@@ -679,7 +679,10 @@ impl helpers for ebml::writer {
                     self.emit_bounds(ecx, bs)
                 }
             }
-            self.emit_rec_field("ty", 0u) {||
+            self.emit_rec_field("rp", 1u) {||
+                ast::serialize_region_param(self, tpbt.rp)
+            }
+            self.emit_rec_field("ty", 2u) {||
                 self.emit_ty(ecx, tpbt.ty);
             }
         }
@@ -848,6 +851,11 @@ impl decoder for ebml::doc {
 
 impl decoder for ebml::ebml_deserializer {
     fn read_ty(xcx: extended_decode_ctxt) -> ty::t {
+        // Note: regions types embed local node ids.  In principle, we
+        // should translate these node ids into the new decode
+        // context.  However, we do not bother, because region types
+        // are not used during trans.
+
         tydecode::parse_ty_data(
             self.parent.data, xcx.dcx.cdata.cnum, self.pos, xcx.dcx.tcx,
             xcx.tr_def_id(_))
@@ -870,7 +878,10 @@ impl decoder for ebml::ebml_deserializer {
                 bounds: self.read_rec_field("bounds", 0u) {||
                     @self.read_to_vec {|| self.read_bounds(xcx) }
                 },
-                ty: self.read_rec_field("ty", 1u) {||
+                rp: self.read_rec_field("rp", 1u) {||
+                    ast::deserialize_region_param(self)
+                },
+                ty: self.read_rec_field("ty", 2u) {||
                     self.read_ty(xcx)
                 }
             }
diff --git a/src/rustc/metadata/common.rs b/src/rustc/metadata/common.rs
index b74d1149d76..33ae58d3a05 100644
--- a/src/rustc/metadata/common.rs
+++ b/src/rustc/metadata/common.rs
@@ -84,6 +84,8 @@ const tag_path_elt_name: uint = 0x43u;
 const tag_item_field: uint = 0x44u;
 const tag_class_mut: uint = 0x45u;
 
+const tag_region_param: uint = 0x46u;
+
 // used to encode crate_ctxt side tables
 enum astencode_tag { // Reserves 0x50 -- 0x6f
     tag_ast = 0x50,
diff --git a/src/rustc/metadata/csearch.rs b/src/rustc/metadata/csearch.rs
index b19473b60fe..0b7dada4f2d 100644
--- a/src/rustc/metadata/csearch.rs
+++ b/src/rustc/metadata/csearch.rs
@@ -157,7 +157,7 @@ fn get_field_type(tcx: ty::ctxt, class_id: ast::def_id,
                  class_id, def)});
     #debug("got field data %?", the_field);
     let ty = decoder::item_type(def, the_field, tcx, cdata);
-    ret {bounds: @[], ty: ty};
+    ret {bounds: @[], rp: ast::rp_none, ty: ty};
 }
 
 fn get_impl_iface(tcx: ty::ctxt, def: ast::def_id)
diff --git a/src/rustc/metadata/decoder.rs b/src/rustc/metadata/decoder.rs
index 06881630bc2..0fed31c20bc 100644
--- a/src/rustc/metadata/decoder.rs
+++ b/src/rustc/metadata/decoder.rs
@@ -15,6 +15,7 @@ import syntax::print::pprust;
 import cmd=cstore::crate_metadata;
 import middle::trans::common::maps;
 import util::ppaux::ty_to_str;
+import ebml::deserializer;
 
 export get_class_fields;
 export get_symbol;
@@ -176,6 +177,18 @@ fn item_ty_param_bounds(item: ebml::doc, tcx: ty::ctxt, cdata: cmd)
     @bounds
 }
 
+fn item_ty_region_param(item: ebml::doc) -> ast::region_param {
+    alt ebml::maybe_get_doc(item, tag_region_param) {
+      some(rp_doc) {
+        let dsr = ebml::ebml_deserializer(rp_doc);
+        ast::deserialize_region_param(dsr)
+      }
+      none { // not all families of items have region params
+        ast::rp_none
+      }
+    }
+}
+
 fn item_ty_param_count(item: ebml::doc) -> uint {
     let mut n = 0u;
     ebml::tagged_docs(item, tag_items_data_item_ty_param_bounds,
@@ -272,12 +285,14 @@ fn lookup_def(cnum: ast::crate_num, data: @[u8], did_: ast::def_id) ->
 
 fn get_type(cdata: cmd, id: ast::node_id, tcx: ty::ctxt)
     -> ty::ty_param_bounds_and_ty {
+
     let item = lookup_item(id, cdata.data);
     let t = item_type({crate: cdata.cnum, node: id}, item, tcx, cdata);
     let tp_bounds = if family_has_type_params(item_family(item)) {
         item_ty_param_bounds(item, tcx, cdata)
     } else { @[] };
-    ret {bounds: tp_bounds, ty: t};
+    let rp = item_ty_region_param(item);
+    ret {bounds: tp_bounds, rp: rp, ty: t};
 }
 
 fn get_type_param_count(data: @[u8], id: ast::node_id) -> uint {
diff --git a/src/rustc/metadata/encoder.rs b/src/rustc/metadata/encoder.rs
index 0ffb3a5d456..dfefe8d78b7 100644
--- a/src/rustc/metadata/encoder.rs
+++ b/src/rustc/metadata/encoder.rs
@@ -16,6 +16,7 @@ import middle::ast_map;
 import syntax::attr;
 import driver::session::session;
 import std::serialization::serializer;
+import std::ebml::serializer;
 
 export encode_metadata;
 export encoded_ty;
@@ -40,6 +41,12 @@ fn encode_def_id(ebml_w: ebml::writer, id: def_id) {
     ebml_w.wr_tagged_str(tag_def_id, def_to_str(id));
 }
 
+fn encode_region_param(ebml_w: ebml::writer, rp: region_param) {
+    ebml_w.wr_tag(tag_region_param) {||
+        serialize_region_param(ebml_w, rp)
+    }
+}
+
 fn encode_named_def_id(ebml_w: ebml::writer, name: str, id: def_id) {
     ebml_w.wr_tag(tag_paths_data_item) {||
         encode_name(ebml_w, name);
@@ -132,14 +139,14 @@ fn encode_module_item_paths(ebml_w: ebml::writer, ecx: @encode_ctxt,
                                             index);
             ebml_w.end_tag();
           }
-          item_ty(_, tps) {
+          item_ty(_, tps, _) {
             add_to_index(ebml_w, path, index, it.ident);
             ebml_w.start_tag(tag_paths_data_item);
             encode_name(ebml_w, it.ident);
             encode_def_id(ebml_w, local_def(it.id));
             ebml_w.end_tag();
           }
-          item_res(_, tps, _, _, ctor_id) {
+          item_res(_, tps, _, _, ctor_id, _) {
             add_to_index(ebml_w, path, index, it.ident);
             ebml_w.start_tag(tag_paths_data_item);
             encode_name(ebml_w, it.ident);
@@ -151,7 +158,7 @@ fn encode_module_item_paths(ebml_w: ebml::writer, ecx: @encode_ctxt,
             encode_def_id(ebml_w, local_def(it.id));
             ebml_w.end_tag();
           }
-          item_class(_, _, items, ctor) {
+          item_class(_, _, items, ctor, _) {
             add_to_index(ebml_w, path, index, it.ident);
             ebml_w.start_tag(tag_paths_data_item);
             encode_name(ebml_w, it.ident);
@@ -165,7 +172,7 @@ fn encode_module_item_paths(ebml_w: ebml::writer, ecx: @encode_ctxt,
                                       index);
             ebml_w.end_tag();
           }
-          item_enum(variants, tps) {
+          item_enum(variants, _, _) {
             add_to_index(ebml_w, path, index, it.ident);
             ebml_w.start_tag(tag_paths_data_item);
             encode_name(ebml_w, it.ident);
@@ -480,7 +487,8 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::writer, item: @item,
                         index: @mut [entry<int>], path: ast_map::path) {
 
     let tcx = ecx.ccx.tcx;
-    let must_write = alt item.node { item_enum(_, _) { true } _ { false } };
+    let must_write =
+        alt item.node { item_enum(_, _, _) { true } _ { false } };
     if !must_write && !ecx.ccx.reachable.contains_key(item.id) { ret; }
 
     fn add_to_index_(item: @item, ebml_w: ebml::writer,
@@ -528,7 +536,7 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::writer, item: @item,
         encode_path(ebml_w, path, ast_map::path_name(item.ident));
         ebml_w.end_tag();
       }
-      item_ty(_, tps) {
+      item_ty(_, tps, rp) {
         add_to_index();
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, local_def(item.id));
@@ -537,26 +545,28 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::writer, item: @item,
         encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
         encode_name(ebml_w, item.ident);
         encode_path(ebml_w, path, ast_map::path_name(item.ident));
+        encode_region_param(ebml_w, rp);
         ebml_w.end_tag();
       }
-      item_enum(variants, tps) {
+      item_enum(variants, tps, rp) {
         add_to_index();
-        ebml_w.start_tag(tag_items_data_item);
-        encode_def_id(ebml_w, local_def(item.id));
-        encode_family(ebml_w, 't');
-        encode_type_param_bounds(ebml_w, ecx, tps);
-        encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
-        encode_name(ebml_w, item.ident);
-        for variants.each {|v|
-            encode_variant_id(ebml_w, local_def(v.node.id));
+        ebml_w.wr_tag(tag_items_data_item) {||
+            encode_def_id(ebml_w, local_def(item.id));
+            encode_family(ebml_w, 't');
+            encode_type_param_bounds(ebml_w, ecx, tps);
+            encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
+            encode_name(ebml_w, item.ident);
+            for variants.each {|v|
+                encode_variant_id(ebml_w, local_def(v.node.id));
+            }
+            astencode::encode_inlined_item(ecx, ebml_w, path, ii_item(item));
+            encode_path(ebml_w, path, ast_map::path_name(item.ident));
+            encode_region_param(ebml_w, rp);
         }
-        astencode::encode_inlined_item(ecx, ebml_w, path, ii_item(item));
-        encode_path(ebml_w, path, ast_map::path_name(item.ident));
-        ebml_w.end_tag();
         encode_enum_variant_info(ecx, ebml_w, item.id, variants,
                                  path, index, tps);
       }
-      item_class(tps, _ifaces, items,ctor) {
+      item_class(tps, _ifaces, items, ctor, rp) {
         /* First, encode the fields and methods
            These come first because we need to write them to make
            the index, and the index needs to be in the item for the
@@ -573,6 +583,7 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::writer, item: @item,
         encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
         encode_name(ebml_w, item.ident);
         encode_path(ebml_w, path, ast_map::path_name(item.ident));
+        encode_region_param(ebml_w, rp);
         /* FIXME: encode ifaces */
         /* Encode def_ids for each field and method
          for methods, write all the stuff get_iface_method
@@ -605,7 +616,7 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::writer, item: @item,
         encode_index(ebml_w, bkts, write_int);
         ebml_w.end_tag();
       }
-      item_res(_, tps, _, _, ctor_id) {
+      item_res(_, tps, _, _, ctor_id, rp) {
         add_to_index();
         let fn_ty = node_id_to_type(tcx, ctor_id);
 
@@ -620,6 +631,7 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::writer, item: @item,
             encode_symbol(ecx, ebml_w, item.id);
         }
         encode_path(ebml_w, path, ast_map::path_name(item.ident));
+        encode_region_param(ebml_w, rp);
         ebml_w.end_tag();
 
         *index += [{val: ctor_id, pos: ebml_w.writer.tell()}];
@@ -732,7 +744,7 @@ fn encode_info_for_items(ecx: @encode_ctxt, ebml_w: ebml::writer,
                 encode_info_for_item(ecx, ebml_w, i, index, *pt);
                 /* encode ctor, then encode items */
                 alt i.node {
-                  item_class(tps,_,_,ctor) {
+                  item_class(tps, _, _, ctor, _) {
                    /* this is assuming that ctors aren't inlined...
                       probably shouldn't assume that */
                    #debug("encoding info for ctor %s %d", i.ident,
diff --git a/src/rustc/metadata/tydecode.rs b/src/rustc/metadata/tydecode.rs
index 590f3d33d4b..139840f5616 100644
--- a/src/rustc/metadata/tydecode.rs
+++ b/src/rustc/metadata/tydecode.rs
@@ -182,6 +182,65 @@ fn parse_vstore(st: @pstate) -> ty::vstore {
     st.tcx.sess.unimpl("tydecode::parse_vstore");
 }
 
+fn parse_substs(st: @pstate, conv: conv_did) -> ty::substs {
+    let self_r = parse_opt(st) {|| parse_region(st) };
+
+    assert next(st) == '[';
+    let mut params: [ty::t] = [];
+    while peek(st) != ']' { params += [parse_ty(st, conv)]; }
+    st.pos = st.pos + 1u;
+
+    ret {self_r: self_r, tps: params};
+}
+
+fn parse_bound_region(st: @pstate) -> ty::bound_region {
+    alt check next(st) {
+      's' { ty::br_self }
+      'a' { ty::br_anon }
+      '[' { ty::br_named(parse_str(st, ']')) }
+    }
+}
+
+fn parse_region(st: @pstate) -> ty::region {
+    alt check next(st) {
+      'b' {
+        ty::re_bound(parse_bound_region(st))
+      }
+      'f' {
+        assert next(st) == '[';
+        let id = parse_int(st);
+        assert next(st) == '|';
+        let br = parse_bound_region(st);
+        assert next(st) == ']';
+        ty::re_free(id, br)
+      }
+      's' {
+        let id = parse_int(st);
+        assert next(st) == '|';
+        ty::re_scope(id)
+      }
+      't' {
+        ty::re_static
+      }
+    }
+}
+
+fn parse_opt<T>(st: @pstate, f: fn() -> T) -> option<T> {
+    alt check next(st) {
+      'n' { none }
+      's' { some(f()) }
+    }
+}
+
+fn parse_str(st: @pstate, term: char) -> str {
+    let mut result = "";
+    while peek(st) != term {
+        result += str::from_byte(next_byte(st));
+    }
+    next(st);
+    ret result;
+}
+
 fn parse_ty(st: @pstate, conv: conv_did) -> ty::t {
     alt check next(st) {
       'n' { ret ty::mk_nil(st.tcx); }
@@ -209,10 +268,9 @@ fn parse_ty(st: @pstate, conv: conv_did) -> ty::t {
       't' {
         assert (next(st) == '[');
         let def = parse_def(st, conv);
-        let mut params: [ty::t] = [];
-        while peek(st) != ']' { params += [parse_ty(st, conv)]; }
-        st.pos = st.pos + 1u;
-        ret ty::mk_enum(st.tcx, def, params);
+        let substs = parse_substs(st, conv);
+        assert next(st) == ']';
+        ret ty::mk_enum(st.tcx, def, substs);
       }
       'x' {
         assert (next(st) == '[');
@@ -250,11 +308,7 @@ fn parse_ty(st: @pstate, conv: conv_did) -> ty::t {
         assert (next(st) == '[');
         let mut fields: [ty::field] = [];
         while peek(st) != ']' {
-            let mut name = "";
-            while peek(st) != '=' {
-                name += str::from_byte(next_byte(st));
-            }
-            st.pos = st.pos + 1u;
+            let name = parse_str(st, '=');
             fields += [{ident: name, mt: parse_mt(st, conv)}];
         }
         st.pos = st.pos + 1u;
@@ -275,10 +329,9 @@ fn parse_ty(st: @pstate, conv: conv_did) -> ty::t {
         assert (next(st) == '[');
         let def = parse_def(st, conv);
         let inner = parse_ty(st, conv);
-        let mut params: [ty::t] = [];
-        while peek(st) != ']' { params += [parse_ty(st, conv)]; }
-        st.pos = st.pos + 1u;
-        ret ty::mk_res(st.tcx, def, inner, params);
+        let substs = parse_substs(st, conv);
+        assert next(st) == ']';
+        ret ty::mk_res(st.tcx, def, inner, substs);
       }
       'X' {
         ret ty::mk_var(st.tcx, ty::ty_vid(parse_int(st) as uint));
@@ -326,10 +379,9 @@ fn parse_ty(st: @pstate, conv: conv_did) -> ty::t {
           #debug("saw a [");
           let did = parse_def(st, conv);
           #debug("parsed a def_id %?", did);
-          let mut params: [ty::t] = [];
-          while peek(st) != ']' { params += [parse_ty(st, conv)]; }
+          let substs = parse_substs(st, conv);
           assert (next(st) == ']');
-          ret ty::mk_class(st.tcx, did, params);
+          ret ty::mk_class(st.tcx, did, substs);
       }
       c { #error("unexpected char in type string: %c", c); fail;}
     }
diff --git a/src/rustc/metadata/tyencode.rs b/src/rustc/metadata/tyencode.rs
index 5815dbf87a5..9c63337970c 100644
--- a/src/rustc/metadata/tyencode.rs
+++ b/src/rustc/metadata/tyencode.rs
@@ -100,18 +100,25 @@ fn enc_mt(w: io::writer, cx: @ctxt, mt: ty::mt) {
     }
     enc_ty(w, cx, mt.ty);
 }
-fn enc_bound_region(w: io::writer, br: ty::bound_region) {
-    alt br {
-      ty::br_self { w.write_char('s') }
-      ty::br_anon { w.write_char('a') }
-      ty::br_named(s) {
-        w.write_char('[');
-        w.write_str(s);
-        w.write_char(']')
+
+fn enc_opt<T>(w: io::writer, t: option<T>, enc_f: fn(T)) {
+    alt t {
+      none { w.write_char('n') }
+      some(v) {
+        w.write_char('s');
+        enc_f(v);
       }
     }
 }
-fn enc_region(w: io::writer, r: ty::region) {
+
+fn enc_substs(w: io::writer, cx: @ctxt, substs: ty::substs) {
+    enc_opt(w, substs.self_r) { |r| enc_region(w, cx, r) }
+    w.write_char('[');
+    for substs.tps.each { |t| enc_ty(w, cx, t); }
+    w.write_char(']');
+}
+
+fn enc_region(w: io::writer, cx: @ctxt, r: ty::region) {
     alt r {
       ty::re_bound(br) {
         w.write_char('b');
@@ -130,18 +137,29 @@ fn enc_region(w: io::writer, r: ty::region) {
         w.write_int(nid);
         w.write_char('|');
       }
-      ty::re_var(id) {
-        w.write_char('v');
-        w.write_uint(id.to_uint());
-        w.write_char('|');
-      }
       ty::re_static {
         w.write_char('t');
       }
+      ty::re_var(_) {
+        // these should not crop up after typeck
+        cx.tcx.sess.bug("Cannot encode region variables");
+      }
     }
 }
 
-fn enc_vstore(w: io::writer, v: ty::vstore) {
+fn enc_bound_region(w: io::writer, br: ty::bound_region) {
+    alt br {
+      ty::br_self { w.write_char('s') }
+      ty::br_anon { w.write_char('a') }
+      ty::br_named(s) {
+        w.write_char('[');
+        w.write_str(s);
+        w.write_char(']')
+      }
+    }
+}
+
+fn enc_vstore(w: io::writer, cx: @ctxt, v: ty::vstore) {
     w.write_char('/');
     alt v {
       ty::vstore_fixed(u)  {
@@ -156,7 +174,7 @@ fn enc_vstore(w: io::writer, v: ty::vstore) {
       }
       ty::vstore_slice(r) {
         w.write_char('&');
-        enc_region(w, r);
+        enc_region(w, cx, r);
       }
     }
 }
@@ -193,11 +211,11 @@ fn enc_sty(w: io::writer, cx: @ctxt, st: ty::sty) {
         }
       }
       ty::ty_str { w.write_char('S'); }
-      ty::ty_enum(def, tys) {
+      ty::ty_enum(def, substs) {
         w.write_str("t[");
         w.write_str(cx.ds(def));
         w.write_char('|');
-        for tys.each {|t| enc_ty(w, cx, t); }
+        enc_substs(w, cx, substs);
         w.write_char(']');
       }
       ty::ty_iface(def, tys) {
@@ -217,17 +235,17 @@ fn enc_sty(w: io::writer, cx: @ctxt, st: ty::sty) {
       ty::ty_ptr(mt) { w.write_char('*'); enc_mt(w, cx, mt); }
       ty::ty_rptr(r, mt) {
         w.write_char('&');
-        enc_region(w, r);
+        enc_region(w, cx, r);
         enc_mt(w, cx, mt);
       }
       ty::ty_evec(mt, v) {
         w.write_char('V');
         enc_mt(w, cx, mt);
-        enc_vstore(w, v);
+        enc_vstore(w, cx, v);
       }
       ty::ty_estr(v) {
         w.write_char('v');
-        enc_vstore(w, v);
+        enc_vstore(w, cx, v);
       }
       ty::ty_vec(mt) { w.write_char('I'); enc_mt(w, cx, mt); }
       ty::ty_rec(fields) {
@@ -243,12 +261,12 @@ fn enc_sty(w: io::writer, cx: @ctxt, st: ty::sty) {
         enc_proto(w, f.proto);
         enc_ty_fn(w, cx, f);
       }
-      ty::ty_res(def, ty, tps) {
+      ty::ty_res(def, ty, substs) {
         w.write_str("r[");
         w.write_str(cx.ds(def));
         w.write_char('|');
         enc_ty(w, cx, ty);
-        for tps.each {|t| enc_ty(w, cx, t); }
+        enc_substs(w, cx, substs);
         w.write_char(']');
       }
       ty::ty_var(id) {
@@ -277,7 +295,7 @@ fn enc_sty(w: io::writer, cx: @ctxt, st: ty::sty) {
         w.write_char(']');
       }
       ty::ty_opaque_box { w.write_char('B'); }
-      ty::ty_class(def, tys) {
+      ty::ty_class(def, substs) {
           #debug("~~~~ %s", "a[");
           w.write_str("a[");
           let s = cx.ds(def);
@@ -285,7 +303,7 @@ fn enc_sty(w: io::writer, cx: @ctxt, st: ty::sty) {
           w.write_str(s);
           #debug("~~~~ %s", "|");
           w.write_str("|");
-          for tys.each {|t| enc_ty(w, cx, t); }
+          enc_substs(w, cx, substs);
           #debug("~~~~ %s", "]");
           w.write_char(']');
       }
diff --git a/src/rustc/middle/alias.rs b/src/rustc/middle/alias.rs
index 2dc09a9a60a..de591b9cc4e 100644
--- a/src/rustc/middle/alias.rs
+++ b/src/rustc/middle/alias.rs
@@ -503,7 +503,7 @@ fn ty_can_unsafely_include(cx: ctx, needle: unsafe_ty, haystack: ty::t,
         } { ret true; }
         alt ty::get(haystack).struct {
           ty::ty_enum(_, ts) {
-            for ts.each {|t|
+            for ts.tps.each {|t|
                 if helper(tcx, needle, t, mutbl) { ret true; }
             }
             ret false;
@@ -565,10 +565,11 @@ fn copy_is_expensive(tcx: ty::ctxt, ty: ty::t) -> bool {
           ty::ty_fn(_) { 4u }
           ty::ty_str | ty::ty_vec(_) | ty::ty_param(_, _) { 50u }
           ty::ty_uniq(mt) { 1u + score_ty(tcx, mt.ty) }
-          ty::ty_enum(_, ts) | ty::ty_tup(ts) {
-            let mut sum = 0u;
-            for ts.each {|t| sum += score_ty(tcx, t); }
-            sum
+          ty::ty_enum(_, substs) {
+            substs.tps.foldl(0u) { |sum, t| sum + score_ty(tcx, t) }
+          }
+          ty::ty_tup(ts) {
+            ts.foldl(0u) { |sum, t| sum + score_ty(tcx, t) }
           }
           ty::ty_rec(fs) {
             let mut sum = 0u;
diff --git a/src/rustc/middle/ast_map.rs b/src/rustc/middle/ast_map.rs
index 89059eb86dd..ab7a884eaeb 100644
--- a/src/rustc/middle/ast_map.rs
+++ b/src/rustc/middle/ast_map.rs
@@ -183,13 +183,13 @@ fn map_item(i: @item, cx: ctx, v: vt) {
             map_method(impl_did, extend(cx, i.ident), m, cx);
         }
       }
-      item_res(decl, tps, _, dtor_id, ctor_id) {
+      item_res(decl, tps, _, dtor_id, ctor_id, _) {
         cx.map.insert(ctor_id, node_ctor(i.ident, tps,
                                          res_ctor(decl, ctor_id, i.span),
                                          item_path));
         cx.map.insert(dtor_id, node_item(i, item_path));
       }
-      item_enum(vs, _) {
+      item_enum(vs, _, _) {
         for vs.each {|v|
             cx.map.insert(v.node.id, node_variant(
                 v, i, extend(cx, i.ident)));
@@ -204,7 +204,7 @@ fn map_item(i: @item, cx: ctx, v: vt) {
             cx.map.insert(nitem.id, node_native_item(nitem, abi, @cx.path));
         }
       }
-      item_class(_, _, items, ctor) {
+      item_class(_, _, items, ctor, _) {
           let d_id = ast_util::local_def(i.id);
           let p = extend(cx, i.ident);
           for items.each {|ci|
diff --git a/src/rustc/middle/check_const.rs b/src/rustc/middle/check_const.rs
index 26e6c2bc469..e73cb0fb5fc 100644
--- a/src/rustc/middle/check_const.rs
+++ b/src/rustc/middle/check_const.rs
@@ -22,7 +22,7 @@ fn check_item(sess: session, ast_map: ast_map::map, def_map: resolve::def_map,
         v.visit_expr(ex, true, v);
         check_item_recursion(sess, ast_map, def_map, it);
       }
-      item_enum(vs, _) {
+      item_enum(vs, _, _) {
         for vs.each {|var|
             option::iter(var.node.disr_expr) {|ex|
                 v.visit_expr(ex, true, v);
diff --git a/src/rustc/middle/infer.rs b/src/rustc/middle/infer.rs
index 568a97947dc..568fd830e40 100644
--- a/src/rustc/middle/infer.rs
+++ b/src/rustc/middle/infer.rs
@@ -538,11 +538,21 @@ impl unify_methods for infer_ctxt {
         sub(self).tys(a, b).chain {|_t| ok(()) }
     }
 
+    fn sub_regions(a: ty::region, b: ty::region) -> ures {
+        sub(self).regions(a, b).chain {|_t| ok(()) }
+    }
+
     fn eq_tys(a: ty::t, b: ty::t) -> ures {
         self.sub_tys(a, b).then {||
             self.sub_tys(b, a)
         }
     }
+
+    fn eq_regions(a: ty::region, b: ty::region) -> ures {
+        self.sub_regions(a, b).then {||
+            self.sub_regions(b, a)
+        }
+    }
 }
 
 impl resolve_methods for infer_ctxt {
@@ -905,6 +915,7 @@ iface combine {
     fn contratys(a: ty::t, b: ty::t) -> cres<ty::t>;
     fn tys(a: ty::t, b: ty::t) -> cres<ty::t>;
     fn tps(as: [ty::t], bs: [ty::t]) -> cres<[ty::t]>;
+    fn substs(as: ty::substs, bs: ty::substs) -> cres<ty::substs>;
     fn fns(a: ty::fn_ty, b: ty::fn_ty) -> cres<ty::fn_ty>;
     fn flds(a: ty::field, b: ty::field) -> cres<ty::field>;
     fn modes(a: ast::mode, b: ast::mode) -> cres<ast::mode>;
@@ -921,6 +932,41 @@ enum sub = infer_ctxt;  // "subtype", "subregion" etc
 enum lub = infer_ctxt;  // "least upper bound" (common supertype)
 enum glb = infer_ctxt;  // "greatest lower bound" (common subtype)
 
+fn super_substs<C:combine>(
+    self: C, a: ty::substs, b: ty::substs) -> cres<ty::substs> {
+
+    fn eq_opt_regions(infcx: infer_ctxt,
+                      a: option<ty::region>,
+                      b: option<ty::region>) -> cres<option<ty::region>> {
+        alt (a, b) {
+          (none, none) {
+            ok(none)
+          }
+          (some(a), some(b)) {
+            infcx.eq_regions(a, b);
+            ok(some(a))
+          }
+          (_, _) {
+            // If these two substitutions are for the same type (and
+            // they should be), then the type should either
+            // consistenly have a region parameter or not have a
+            // region parameter.
+            infcx.tcx.sess.bug(
+                #fmt["substitution a had opt_region %s and \
+                      b had opt_region %s",
+                     a.to_str(infcx),
+                     b.to_str(infcx)]);
+          }
+        }
+    }
+
+    self.tps(a.tps, b.tps).chain { |tps|
+        eq_opt_regions(self.infcx(), a.self_r, b.self_r).chain { |self_r|
+            ok({self_r: self_r, tps: tps})
+        }
+    }
+}
+
 fn super_tps<C:combine>(
     self: C, as: [ty::t], bs: [ty::t]) -> cres<[ty::t]> {
 
@@ -1057,9 +1103,9 @@ fn super_tys<C:combine>(
         ok(a)
       }
 
-      (ty::ty_enum(a_id, a_tps), ty::ty_enum(b_id, b_tps))
+      (ty::ty_enum(a_id, a_substs), ty::ty_enum(b_id, b_substs))
       if a_id == b_id {
-        self.tps(a_tps, b_tps).chain {|tps|
+        self.substs(a_substs, b_substs).chain {|tps|
             ok(ty::mk_enum(tcx, a_id, tps))
         }
       }
@@ -1071,10 +1117,10 @@ fn super_tys<C:combine>(
         }
       }
 
-      (ty::ty_class(a_id, a_tps), ty::ty_class(b_id, b_tps))
+      (ty::ty_class(a_id, a_substs), ty::ty_class(b_id, b_substs))
       if a_id == b_id {
-        self.tps(a_tps, b_tps).chain {|tps|
-            ok(ty::mk_class(tcx, a_id, tps))
+        self.substs(a_substs, b_substs).chain {|substs|
+            ok(ty::mk_class(tcx, a_id, substs))
         }
       }
 
@@ -1124,11 +1170,12 @@ fn super_tys<C:combine>(
         }
       }
 
-      (ty::ty_res(a_id, a_t, a_tps), ty::ty_res(b_id, b_t, b_tps))
+      (ty::ty_res(a_id, a_t, a_substs),
+       ty::ty_res(b_id, b_t, b_substs))
       if a_id == b_id {
         self.tys(a_t, b_t).chain {|t|
-            self.tps(a_tps, b_tps).chain {|tps|
-                ok(ty::mk_res(tcx, a_id, t, tps))
+            self.substs(a_substs, b_substs).chain {|substs|
+                ok(ty::mk_res(tcx, a_id, t, substs))
             }
         }
       }
@@ -1299,6 +1346,10 @@ impl of combine for sub {
         super_fns(self, a, b)
     }
 
+    fn substs(as: ty::substs, bs: ty::substs) -> cres<ty::substs> {
+        super_substs(self, as, bs)
+    }
+
     fn tps(as: [ty::t], bs: [ty::t]) -> cres<[ty::t]> {
         super_tps(self, as, bs)
     }
@@ -1470,6 +1521,10 @@ impl of combine for lub {
         super_fns(self, a, b)
     }
 
+    fn substs(as: ty::substs, bs: ty::substs) -> cres<ty::substs> {
+        super_substs(self, as, bs)
+    }
+
     fn tps(as: [ty::t], bs: [ty::t]) -> cres<[ty::t]> {
         super_tps(self, as, bs)
     }
@@ -1656,6 +1711,10 @@ impl of combine for glb {
         super_fns(self, a, b)
     }
 
+    fn substs(as: ty::substs, bs: ty::substs) -> cres<ty::substs> {
+        super_substs(self, as, bs)
+    }
+
     fn tps(as: [ty::t], bs: [ty::t]) -> cres<[ty::t]> {
         super_tps(self, as, bs)
     }
diff --git a/src/rustc/middle/mutbl.rs b/src/rustc/middle/mutbl.rs
index 45d0beeab81..35561c56e65 100644
--- a/src/rustc/middle/mutbl.rs
+++ b/src/rustc/middle/mutbl.rs
@@ -30,18 +30,18 @@ fn expr_root_(tcx: ty::ctxt, ctor_self: option<node_id>,
                          outer_t: t}];
                 t = mt.ty;
               }
-              ty::ty_res(_, inner, tps) {
+              ty::ty_res(_, inner, substs) {
                 ds += [@{mutbl: false, kind: unbox(false), outer_t: t}];
-                t = ty::substitute_type_params(tcx, tps, inner);
+                t = ty::subst(tcx, substs, inner);
               }
-              ty::ty_enum(did, tps) {
+              ty::ty_enum(did, substs) {
                 let variants = ty::enum_variants(tcx, did);
                 if vec::len(*variants) != 1u ||
                        vec::len(variants[0].args) != 1u {
                     break;
                 }
                 ds += [@{mutbl: false, kind: unbox(false), outer_t: t}];
-                t = ty::substitute_type_params(tcx, tps, variants[0].args[0]);
+                t = ty::subst(tcx, substs, variants[0].args[0]);
               }
               _ { break; }
             }
@@ -216,7 +216,7 @@ fn visit_expr(ex: @expr, &&cx: @ctx, v: visit::vt<@ctx>) {
 
 fn visit_item(item: @item, &&cx: @ctx, v: visit::vt<@ctx>) {
     alt item.node {
-      item_class(tps, _, items, ctor) {
+      item_class(tps, _, items, ctor, _) {
          v.visit_ty_params(tps, cx, v);
          vec::map::<@class_member, ()>(items,
              {|i| v.visit_class_item(i, cx, v); });
diff --git a/src/rustc/middle/region.rs b/src/rustc/middle/region.rs
index e27d41d4ee0..53c52cf9fc2 100644
--- a/src/rustc/middle/region.rs
+++ b/src/rustc/middle/region.rs
@@ -143,16 +143,7 @@ import std::list::list;
 import std::map;
 import std::map::hashmap;
 
-/* Represents the type of the most immediate parent node. */
-enum parent {
-    pa_fn_item(ast::node_id),
-    pa_block(ast::node_id),
-    pa_nested_fn(ast::node_id),
-    pa_item(ast::node_id),
-    pa_call(ast::node_id),
-    pa_alt(ast::node_id),
-    pa_crate
-}
+type parent = option<ast::node_id>;
 
 /* Records the parameter ID of a region name. */
 type binding = {node_id: ast::node_id,
@@ -167,43 +158,11 @@ type region_map = {
     local_blocks: hashmap<ast::node_id,ast::node_id>
 };
 
-type region_scope = @{
-    node_id: ast::node_id,
-    kind: region_scope_kind
-};
-
-enum region_scope_kind {
-    rsk_root,
-    rsk_body(region_scope),
-    rsk_self(region_scope),
-    rsk_binding(region_scope, @mut [binding])
-}
-
-fn root_scope(node_id: ast::node_id) -> region_scope {
-    @{node_id: node_id, kind: rsk_root}
-}
-
-impl methods for region_scope {
-    fn body_subscope(node_id: ast::node_id) -> region_scope {
-        @{node_id: node_id, kind: rsk_body(self)}
-    }
-
-    fn binding_subscope(node_id: ast::node_id) -> region_scope {
-        @{node_id: node_id, kind: rsk_binding(self, @mut [])}
-    }
-
-    fn self_subscope(node_id: ast::node_id) -> region_scope {
-        @{node_id: node_id, kind: rsk_self(self)}
-    }
-}
-
 type ctxt = {
     sess: session,
     def_map: resolve::def_map,
     region_map: @region_map,
 
-    scope: region_scope,
-
     parent: parent
 };
 
@@ -269,40 +228,8 @@ fn nearest_common_ancestor(region_map: @region_map, scope_a: ast::node_id,
     }
 }
 
-fn get_inferred_region(cx: ctxt, sp: syntax::codemap::span) -> ty::region {
-    // We infer to the caller region if we're at item scope
-    // and to the block region if we're at block scope.
-    //
-    // TODO: What do we do if we're in an alt?
-
-    ret alt cx.parent {
-      pa_fn_item(_) | pa_nested_fn(_) { ty::re_bound(ty::br_anon) }
-      pa_block(node_id) | pa_call(node_id) | pa_alt(node_id) {
-        ty::re_scope(node_id)
-      }
-      pa_item(_) { ty::re_bound(ty::br_anon) }
-      pa_crate { cx.sess.span_bug(sp, "inferred region at crate level?!"); }
-    }
-}
-
-fn opt_parent_id(cx: ctxt) -> option<ast::node_id> {
-    alt cx.parent {
-      pa_fn_item(parent_id) |
-      pa_item(parent_id) |
-      pa_block(parent_id) |
-      pa_alt(parent_id) |
-      pa_call(parent_id) |
-      pa_nested_fn(parent_id) {
-        some(parent_id)
-      }
-      pa_crate {
-        none
-      }
-    }
-}
-
 fn parent_id(cx: ctxt, span: span) -> ast::node_id {
-    alt opt_parent_id(cx) {
+    alt cx.parent {
       none {
         cx.sess.span_bug(span, "crate should not be parent here");
       }
@@ -313,7 +240,7 @@ fn parent_id(cx: ctxt, span: span) -> ast::node_id {
 }
 
 fn record_parent(cx: ctxt, child_id: ast::node_id) {
-    alt opt_parent_id(cx) {
+    alt cx.parent {
       none { /* no-op */ }
       some(parent_id) {
         cx.region_map.parents.insert(child_id, parent_id);
@@ -326,8 +253,7 @@ fn resolve_block(blk: ast::blk, cx: ctxt, visitor: visit::vt<ctxt>) {
     record_parent(cx, blk.node.id);
 
     // Descend.
-    let new_cx: ctxt = {parent: pa_block(blk.node.id),
-                        scope: cx.scope.body_subscope(blk.node.id)
+    let new_cx: ctxt = {parent: some(blk.node.id)
                         with cx};
     visit::visit_block(blk, new_cx, visitor);
 }
@@ -361,21 +287,15 @@ fn resolve_expr(expr: @ast::expr, cx: ctxt, visitor: visit::vt<ctxt>) {
     record_parent(cx, expr.id);
     alt expr.node {
       ast::expr_fn(_, _, _, _) | ast::expr_fn_block(_, _) {
-        let new_cx = {parent: pa_nested_fn(expr.id),
-                      scope: cx.scope.binding_subscope(expr.id)
-                      with cx};
+        let new_cx = {parent: some(expr.id) with cx};
         visit::visit_expr(expr, new_cx, visitor);
       }
       ast::expr_call(_, _, _) {
-        let new_cx = {parent: pa_call(expr.id),
-                      scope: cx.scope.binding_subscope(expr.id)
-                      with cx};
+        let new_cx = {parent: some(expr.id) with cx};
         visit::visit_expr(expr, new_cx, visitor);
       }
       ast::expr_alt(subexpr, _, _) {
-        let new_cx = {parent: pa_alt(expr.id),
-                      scope: cx.scope.binding_subscope(expr.id)
-                      with cx};
+        let new_cx = {parent: some(expr.id) with cx};
         visit::visit_expr(expr, new_cx, visitor);
       }
       _ {
@@ -392,27 +312,7 @@ fn resolve_local(local: @ast::local, cx: ctxt, visitor: visit::vt<ctxt>) {
 
 fn resolve_item(item: @ast::item, cx: ctxt, visitor: visit::vt<ctxt>) {
     // Items create a new outer block scope as far as we're concerned.
-    let {parent, scope} = {
-        alt item.node {
-          ast::item_fn(_, _, _) | ast::item_enum(_, _) {
-            {parent: pa_fn_item(item.id),
-             scope: cx.scope.binding_subscope(item.id)}
-          }
-          ast::item_impl(_, _, _, _) | ast::item_class(_, _, _, _) {
-            {parent: pa_item(item.id),
-             scope: cx.scope.self_subscope(item.id)}
-          }
-          _ {
-            {parent: pa_item(item.id),
-             scope: root_scope(item.id)}
-          }
-        }
-    };
-
-    let new_cx: ctxt = {parent: parent,
-                        scope: scope
-                        with cx};
-
+    let new_cx: ctxt = {parent: some(item.id) with cx};
     visit::visit_item(item, new_cx, visitor);
 }
 
@@ -422,8 +322,7 @@ fn resolve_crate(sess: session, def_map: resolve::def_map, crate: @ast::crate)
                     def_map: def_map,
                     region_map: @{parents: map::int_hash(),
                                   local_blocks: map::int_hash()},
-                    scope: root_scope(0),
-                    parent: pa_crate};
+                    parent: none};
     let visitor = visit::mk_vt(@{
         visit_block: resolve_block,
         visit_item: resolve_item,
diff --git a/src/rustc/middle/resolve.rs b/src/rustc/middle/resolve.rs
index 5a15529e775..4fff72fcc8b 100644
--- a/src/rustc/middle/resolve.rs
+++ b/src/rustc/middle/resolve.rs
@@ -434,7 +434,7 @@ fn resolve_names(e: @env, c: @ast::crate) {
           non-class items
          */
         alt i.node {
-           ast::item_class(_, ifaces, _, _) {
+           ast::item_class(_, ifaces, _, _, _) {
              /* visit the iface paths... */
              for ifaces.each {|p|
                maybe_insert(e, p.id,
@@ -559,7 +559,7 @@ fn visit_item_with_scope(e: @env, i: @ast::item, sc: scopes, v: vt<scopes>) {
             v.visit_ty(m.decl.output, msc, v);
         }
       }
-      ast::item_class(tps, ifaces, members, ctor) {
+      ast::item_class(tps, ifaces, members, ctor, _) {
         visit::visit_ty_params(tps, sc, v);
         // Can maybe skip this now that we require self on class fields
         let class_scope = cons(scope_item(i), @sc);
@@ -613,7 +613,7 @@ fn visit_fn_with_scope(e: @env, fk: visit::fn_kind, decl: ast::fn_decl,
     // for f's constrs in the table.
     for decl.constraints.each {|c| resolve_constr(e, c, sc, v); }
     let scope = alt fk {
-      visit::fk_item_fn(_, tps) | visit::fk_res(_, tps) |
+      visit::fk_item_fn(_, tps) | visit::fk_res(_, tps, _) |
       visit::fk_method(_, tps, _) | visit::fk_ctor(_, tps, _, _)
          { scope_bare_fn(decl, id, tps) }
       visit::fk_anon(ast::proto_bare) { scope_bare_fn(decl, id, []) }
@@ -1019,7 +1019,7 @@ fn lookup_in_scope(e: env, sc: scopes, sp: span, name: ident, ns: namespace,
               ast::item_impl(tps, _, _, _) {
                 if ns == ns_type { ret lookup_in_ty_params(e, name, tps); }
               }
-              ast::item_enum(_, tps) | ast::item_ty(_, tps) {
+              ast::item_enum(_, tps, _) | ast::item_ty(_, tps, _) {
                 if ns == ns_type { ret lookup_in_ty_params(e, name, tps); }
               }
               ast::item_iface(tps, _) {
@@ -1036,7 +1036,7 @@ fn lookup_in_scope(e: env, sc: scopes, sp: span, name: ident, ns: namespace,
               ast::item_native_mod(m) {
                 ret lookup_in_local_native_mod(e, it.id, sp, name, ns);
               }
-              ast::item_class(tps, _, members, ctor) {
+              ast::item_class(tps, _, members, ctor, _) {
                   if ns == ns_type {
                     ret lookup_in_ty_params(e, name, tps);
                   }
@@ -1210,7 +1210,7 @@ fn lookup_in_block(e: env, name: ident, sp: span, b: ast::blk_, pos: uint,
               }
               ast::decl_item(it) {
                 alt it.node {
-                  ast::item_enum(variants, _) {
+                  ast::item_enum(variants, _, _) {
                     if ns == ns_type {
                         if str::eq(it.ident, name) {
                             ret some(ast::def_ty(local_def(it.id)));
@@ -1309,10 +1309,10 @@ fn found_def_item(i: @ast::item, ns: namespace) -> option<def> {
       ast::item_native_mod(_) {
         if ns == ns_module { ret some(ast::def_native_mod(local_def(i.id))); }
       }
-      ast::item_ty(_, _) | item_iface(_, _) | item_enum(_, _) {
+      ast::item_ty(_, _, _) | item_iface(_, _) | item_enum(_, _, _) {
         if ns == ns_type { ret some(ast::def_ty(local_def(i.id))); }
       }
-      ast::item_res(_, _, _, _, ctor_id) {
+      ast::item_res(_, _, _, _, ctor_id, _) {
         alt ns {
           ns_val {
             ret some(ast::def_fn(local_def(ctor_id), ast::impure_fn));
@@ -1321,7 +1321,7 @@ fn found_def_item(i: @ast::item, ns: namespace) -> option<def> {
           _ { }
         }
       }
-      ast::item_class(_, _, _, _) {
+      ast::item_class(_, _, _, _, _) {
           if ns == ns_type {
             ret some(ast::def_class(local_def(i.id)));
           }
@@ -1614,12 +1614,12 @@ fn index_mod(md: ast::_mod) -> mod_index {
     for md.items.each {|it|
         alt it.node {
           ast::item_const(_, _) | ast::item_fn(_, _, _) | ast::item_mod(_) |
-          ast::item_native_mod(_) | ast::item_ty(_, _) |
-          ast::item_res(_, _, _, _, _) |
+          ast::item_native_mod(_) | ast::item_ty(_, _, _) |
+          ast::item_res(_, _, _, _, _, _) |
           ast::item_impl(_, _, _, _) | ast::item_iface(_, _) {
             add_to_index(index, it.ident, mie_item(it));
           }
-          ast::item_enum(variants, _) {
+          ast::item_enum(variants, _, _) {
             add_to_index(index, it.ident, mie_item(it));
             let mut variant_idx: uint = 0u;
             for variants.each {|v|
@@ -1629,7 +1629,7 @@ fn index_mod(md: ast::_mod) -> mod_index {
                 variant_idx += 1u;
             }
           }
-          ast::item_class(tps, _, items, ctor) {
+          ast::item_class(tps, _, items, ctor, _) {
               // add the class name itself
               add_to_index(index, it.ident, mie_item(it));
               // add the constructor decl
@@ -1763,7 +1763,7 @@ fn check_item(e: @env, i: @ast::item, &&x: (), v: vt<()>) {
         ensure_unique(*e, i.span, ty_params, {|tp| tp.ident},
                       "type parameter");
       }
-      ast::item_enum(_, ty_params) {
+      ast::item_enum(_, ty_params, _) {
         ensure_unique(*e, i.span, ty_params, {|tp| tp.ident},
                       "type parameter");
       }
@@ -1837,7 +1837,7 @@ fn check_block(e: @env, b: ast::blk, &&x: (), v: vt<()>) {
               }
               ast::decl_item(it) {
                 alt it.node {
-                  ast::item_enum(variants, _) {
+                  ast::item_enum(variants, _, _) {
                     add_name(types, it.span, it.ident);
                     for variants.each {|v|
                         add_name(values, v.span, v.node.name);
@@ -1849,10 +1849,10 @@ fn check_block(e: @env, b: ast::blk, &&x: (), v: vt<()>) {
                   ast::item_const(_, _) | ast::item_fn(_, _, _) {
                     add_name(values, it.span, it.ident);
                   }
-                  ast::item_ty(_, _) | ast::item_iface(_, _) {
+                  ast::item_ty(_, _, _) | ast::item_iface(_, _) {
                     add_name(types, it.span, it.ident);
                   }
-                  ast::item_res(_, _, _, _, _) {
+                  ast::item_res(_, _, _, _, _, _) {
                     add_name(types, it.span, it.ident);
                     add_name(values, it.span, it.ident);
                   }
@@ -2030,7 +2030,7 @@ fn check_exports(e: @env) {
           some(ms) {
             let maybe_id = list_search(ms) {|m|
                 alt m {
-                  mie_item(@{node: item_enum(_, _), id, _}) { some(id) }
+                  mie_item(@{node: item_enum(_, _, _), id, _}) { some(id) }
                   _ { none }
                 }
             };
diff --git a/src/rustc/middle/trans/alt.rs b/src/rustc/middle/trans/alt.rs
index 3ce6d9ed62a..71aa0c0e9cc 100644
--- a/src/rustc/middle/trans/alt.rs
+++ b/src/rustc/middle/trans/alt.rs
@@ -263,11 +263,10 @@ fn extract_variant_args(bcx: block, pat_id: ast::node_id,
     let _icx = bcx.insn_ctxt("alt::extract_variant_args");
     let ccx = bcx.fcx.ccx;
     let enum_ty_substs = alt check ty::get(node_id_type(bcx, pat_id)).struct {
-      ty::ty_enum(id, tps) { assert id == vdefs.enm; tps }
+      ty::ty_enum(id, substs) { assert id == vdefs.enm; substs.tps }
     };
     let mut blobptr = val;
     let variants = ty::enum_variants(ccx.tcx, vdefs.enm);
-    let mut args = [];
     let size = ty::enum_variant_with_id(ccx.tcx, vdefs.enm,
                                         vdefs.var).args.len();
     if size > 0u && (*variants).len() != 1u {
@@ -275,14 +274,12 @@ fn extract_variant_args(bcx: block, pat_id: ast::node_id,
             PointerCast(bcx, val, T_opaque_enum_ptr(ccx));
         blobptr = GEPi(bcx, enumptr, [0, 1]);
     }
-    let mut i = 0u;
     let vdefs_tg = vdefs.enm;
     let vdefs_var = vdefs.var;
-    while i < size {
-        args += [GEP_enum(bcx, blobptr, vdefs_tg, vdefs_var,
-                          enum_ty_substs, i)];
-        i += 1u;
-    }
+    let args = vec::from_fn(size) { |i|
+        GEP_enum(bcx, blobptr, vdefs_tg, vdefs_var,
+                 enum_ty_substs, i)
+    };
     ret {vals: args, bcx: bcx};
 }
 
diff --git a/src/rustc/middle/trans/base.rs b/src/rustc/middle/trans/base.rs
index add02f56151..60524186404 100644
--- a/src/rustc/middle/trans/base.rs
+++ b/src/rustc/middle/trans/base.rs
@@ -297,7 +297,7 @@ fn GEP_enum(bcx: block, llblobptr: ValueRef, enum_id: ast::def_id,
     assert ix < variant.args.len();
 
     let arg_lltys = vec::map(variant.args, {|aty|
-        type_of(ccx, ty::substitute_type_params(ccx.tcx, ty_substs, aty))
+        type_of(ccx, ty::subst_tps(ccx.tcx, ty_substs, aty))
     });
     let typed_blobptr = PointerCast(bcx, llblobptr,
                                     T_ptr(T_struct(arg_lltys)));
@@ -686,8 +686,8 @@ fn make_drop_glue(bcx: block, v0: ValueRef, t: ty::t) {
       ty::ty_evec(_, ty::vstore_uniq) | ty::ty_estr(ty::vstore_uniq) {
         free_ty(bcx, Load(bcx, v0), t)
       }
-      ty::ty_res(did, inner, tps) {
-        trans_res_drop(bcx, v0, did, inner, tps)
+      ty::ty_res(did, inner, substs) {
+        trans_res_drop(bcx, v0, did, inner, substs.tps)
       }
       ty::ty_fn(_) {
         closure::make_fn_glue(bcx, v0, t, drop_ty)
@@ -735,7 +735,7 @@ fn trans_res_drop(bcx: block, rs: ValueRef, did: ast::def_id,
                   inner_t: ty::t, tps: [ty::t]) -> block {
     let _icx = bcx.insn_ctxt("trans_res_drop");
     let ccx = bcx.ccx();
-    let inner_t_s = ty::substitute_type_params(ccx.tcx, tps, inner_t);
+    let inner_t_s = ty::subst_tps(ccx.tcx, tps, inner_t);
 
     let drop_flag = GEPi(bcx, rs, [0, 0]);
     with_cond(bcx, IsNotNull(bcx, Load(bcx, drop_flag))) {|bcx|
@@ -911,7 +911,7 @@ fn iter_structural_ty(cx: block, av: ValueRef, t: ty::t,
             let v_id = variant.id;
             for vec::each(args) {|a|
                 let llfldp_a = GEP_enum(cx, a_tup, tid, v_id, tps, j);
-                let ty_subst = ty::substitute_type_params(ccx.tcx, tps, a.ty);
+                let ty_subst = ty::subst_tps(ccx.tcx, tps, a.ty);
                 cx = f(cx, llfldp_a, ty_subst);
                 j += 1u;
             }
@@ -943,19 +943,20 @@ fn iter_structural_ty(cx: block, av: ValueRef, t: ty::t,
             cx = f(cx, llfld_a, arg);
         }
       }
-      ty::ty_res(_, inner, tps) {
+      ty::ty_res(_, inner, substs) {
         let tcx = cx.tcx();
-        let inner1 = ty::substitute_type_params(tcx, tps, inner);
+        let inner1 = ty::subst(tcx, substs, inner);
         let llfld_a = GEPi(cx, av, [0, 1]);
         ret f(cx, llfld_a, inner1);
       }
-      ty::ty_enum(tid, tps) {
+      ty::ty_enum(tid, substs) {
         let variants = ty::enum_variants(cx.tcx(), tid);
         let n_variants = (*variants).len();
 
         // Cast the enums to types we can GEP into.
         if n_variants == 1u {
-            ret iter_variant(cx, av, variants[0], tps, tid, f);
+            ret iter_variant(cx, av, variants[0],
+                             substs.tps, tid, f);
         }
 
         let ccx = cx.ccx();
@@ -979,15 +980,16 @@ fn iter_structural_ty(cx: block, av: ValueRef, t: ty::t,
                                        int::to_str(variant.disr_val, 10u));
             AddCase(llswitch, C_int(ccx, variant.disr_val), variant_cx.llbb);
             let variant_cx =
-                iter_variant(variant_cx, llunion_a_ptr, variant, tps, tid, f);
+                iter_variant(variant_cx, llunion_a_ptr, variant,
+                             substs.tps, tid, f);
             Br(variant_cx, next_cx.llbb);
         }
         ret next_cx;
       }
-      ty::ty_class(did, tps) {
+      ty::ty_class(did, substs) {
           // a class is like a record type
         let mut i: int = 0;
-        for vec::each(ty::class_items_as_fields(cx.tcx(), did, tps)) {|fld|
+        for vec::each(ty::class_items_as_fields(cx.tcx(), did, substs)) {|fld|
             let llfld_a = GEPi(cx, av, [0, i]);
             cx = f(cx, llfld_a, fld.mt.ty);
             i += 1;
@@ -1617,17 +1619,17 @@ fn autoderef(cx: block, v: ValueRef, t: ty::t) -> result_t {
             t1 = mt.ty;
             v1 = v;
           }
-          ty::ty_res(did, inner, tps) {
-            t1 = ty::substitute_type_params(ccx.tcx, tps, inner);
+          ty::ty_res(did, inner, substs) {
+            t1 = ty::subst(ccx.tcx, substs, inner);
             v1 = GEPi(cx, v1, [0, 1]);
           }
-          ty::ty_enum(did, tps) {
+          ty::ty_enum(did, substs) {
             let variants = ty::enum_variants(ccx.tcx, did);
             if (*variants).len() != 1u || variants[0].args.len() != 1u {
                 break;
             }
             t1 =
-                ty::substitute_type_params(ccx.tcx, tps, variants[0].args[0]);
+                ty::subst(ccx.tcx, substs, variants[0].args[0]);
             v1 = PointerCast(cx, v1, T_ptr(type_of(ccx, t1)));
           }
           _ { break; }
@@ -1939,7 +1941,7 @@ fn monomorphic_fn(ccx: @crate_ctxt, fn_id: ast::def_id, real_substs: [ty::t],
     let (pt, name) = alt map_node {
       ast_map::node_item(i, pt) {
         alt i.node {
-          ast::item_res(_, _, _, dtor_id, _) {
+          ast::item_res(_, _, _, dtor_id, _, _) {
             item_ty = ty::node_id_to_type(ccx.tcx, dtor_id);
           }
           _ {}
@@ -1958,7 +1960,7 @@ fn monomorphic_fn(ccx: @crate_ctxt, fn_id: ast::def_id, real_substs: [ty::t],
       ast_map::node_ctor(nm, _, _, pt) { (pt, nm) }
       _ { fail "unexpected node type"; }
     };
-    let mono_ty = ty::substitute_type_params(ccx.tcx, substs, item_ty);
+    let mono_ty = ty::subst_tps(ccx.tcx, substs, item_ty);
     let llfty = type_of_fn_from_ty(ccx, mono_ty);
 
     let pt = *pt + [path_name(ccx.names(name))];
@@ -1972,7 +1974,8 @@ fn monomorphic_fn(ccx: @crate_ctxt, fn_id: ast::def_id, real_substs: [ty::t],
         set_inline_hint_if_appr(i.attrs, lldecl);
         trans_fn(ccx, pt, decl, body, lldecl, no_self, psubsts, fn_id.node);
       }
-      ast_map::node_item(@{node: ast::item_res(d, _, body, d_id, _), _}, _) {
+      ast_map::node_item(
+          @{node: ast::item_res(d, _, body, d_id, _, _), _}, _) {
         trans_fn(ccx, pt, d, body, lldecl, no_self, psubsts, d_id);
       }
       ast_map::node_native_item(i, _, _) {
@@ -1990,7 +1993,7 @@ fn monomorphic_fn(ccx: @crate_ctxt, fn_id: ast::def_id, real_substs: [ty::t],
       ast_map::node_method(mth, impl_def_id, _) {
         set_inline_hint_if_appr(mth.attrs, lldecl);
         let selfty = ty::node_id_to_type(ccx.tcx, mth.self_id);
-        let selfty = ty::substitute_type_params(ccx.tcx, substs, selfty);
+        let selfty = ty::subst_tps(ccx.tcx, substs, selfty);
         trans_fn(ccx, pt, mth.decl, mth.body, lldecl,
                  impl_self(selfty), psubsts, fn_id.node);
       }
@@ -2048,7 +2051,7 @@ fn maybe_instantiate_inline(ccx: @crate_ctxt, fn_id: ast::def_id)
             ccx.external.insert(parent_id, some(item.id));
             let mut my_id = 0;
             alt check item.node {
-              ast::item_enum(_, _) {
+              ast::item_enum(_, _, _) {
                 let vs_here = ty::enum_variants(ccx.tcx, local_def(item.id));
                 let vs_there = ty::enum_variants(ccx.tcx, parent_id);
                 vec::iter2(*vs_here, *vs_there) {|here, there|
@@ -2056,14 +2059,16 @@ fn maybe_instantiate_inline(ccx: @crate_ctxt, fn_id: ast::def_id)
                     ccx.external.insert(there.id, some(here.id.node));
                 }
               }
-              ast::item_res(_, _, _, _, ctor_id) { my_id = ctor_id; }
+              ast::item_res(_, _, _, _, ctor_id, _) {
+                my_id = ctor_id;
+              }
             }
             trans_item(ccx, *item);
             local_def(my_id)
           }
           csearch::found(ast::ii_method(impl_did, mth)) {
             ccx.external.insert(fn_id, some(mth.id));
-            let {bounds: impl_bnds, ty: impl_ty} =
+            let {bounds: impl_bnds, rp: _, ty: impl_ty} =
                 ty::lookup_item_type(ccx.tcx, impl_did);
             if (*impl_bnds).len() + mth.tps.len() == 0u {
                 let llfn = get_item_val(ccx, mth.id);
@@ -2264,8 +2269,8 @@ fn trans_rec_field_inner(bcx: block, val: ValueRef, ty: ty::t,
                          field: ast::ident, sp: span) -> lval_result {
     let fields = alt ty::get(ty).struct {
             ty::ty_rec(fs) { fs }
-            ty::ty_class(did,ts) {
-                ty::class_items_as_fields(bcx.tcx(), did, ts) }
+            ty::ty_class(did, substs) {
+                ty::class_items_as_fields(bcx.tcx(), did, substs) }
             // Constraint?
             _ { bcx.tcx().sess.span_bug(sp, "trans_rec_field:\
                  base expr has non-record type"); }
@@ -4379,7 +4384,9 @@ fn trans_class_ctor(ccx: @crate_ctxt, path: path, decl: ast::fn_decl,
   // kludgy -- this wouldn't be necessary if the typechecker
   // special-cased constructors, then we could just look up
   // the ctor's return type.
-  let rslt_ty =  ty::mk_class(ccx.tcx, parent_id, psubsts.tys);
+  let rslt_ty =  ty::mk_class(ccx.tcx, parent_id,
+                              dummy_substs(psubsts.tys));
+
   // Make the fn context
   let fcx = new_fn_ctxt_w_id(ccx, path, llctor_decl, ctor_id,
                                    some(psubsts), some(sp));
@@ -4397,7 +4404,7 @@ fn trans_class_ctor(ccx: @crate_ctxt, path: path, decl: ast::fn_decl,
   let selfptr = alloc_ty(bcx_top, rslt_ty);
   // initialize fields to zero
   let fields = ty::class_items_as_fields(bcx_top.tcx(), parent_id,
-                                         psubsts.tys);
+                                         dummy_substs(psubsts.tys));
   let mut bcx = bcx_top;
   // Initialize fields to zero so init assignments can validly
   // drop their LHS
@@ -4450,7 +4457,7 @@ fn trans_item(ccx: @crate_ctxt, item: ast::item) {
       ast::item_impl(tps, _, _, ms) {
         impl::trans_impl(ccx, *path, item.ident, ms, tps);
       }
-      ast::item_res(decl, tps, body, dtor_id, ctor_id) {
+      ast::item_res(decl, tps, body, dtor_id, ctor_id, _) {
         if tps.len() == 0u {
             let llctor_decl = get_item_val(ccx, ctor_id);
             trans_res_ctor(ccx, *path, decl, ctor_id, none, llctor_decl);
@@ -4463,7 +4470,7 @@ fn trans_item(ccx: @crate_ctxt, item: ast::item) {
       ast::item_mod(m) {
         trans_mod(ccx, m);
       }
-      ast::item_enum(variants, tps) {
+      ast::item_enum(variants, tps, _) {
         if tps.len() == 0u {
             let degen = variants.len() == 1u;
             let vi = ty::enum_variants(ccx.tcx, local_def(item.id));
@@ -4487,7 +4494,7 @@ fn trans_item(ccx: @crate_ctxt, item: ast::item) {
         };
         native::trans_native_mod(ccx, native_mod, abi);
       }
-      ast::item_class(tps, _ifaces, items, ctor) {
+      ast::item_class(tps, _ifaces, items, ctor, _) {
         if tps.len() == 0u {
           let psubsts = {tys: ty::ty_params_to_tys(ccx.tcx, tps),
                          // FIXME: vtables have to get filled in depending
@@ -4495,7 +4502,7 @@ fn trans_item(ccx: @crate_ctxt, item: ast::item) {
                          vtables: none,
                          bounds: @[]};
           trans_class_ctor(ccx, *path, ctor.node.dec, ctor.node.body,
-                         get_item_val(ccx, ctor.node.id), psubsts,
+                           get_item_val(ccx, ctor.node.id), psubsts,
                            ctor.node.id, local_def(item.id), ctor.span);
         }
         // If there are ty params, the ctor will get monomorphized
@@ -4684,7 +4691,7 @@ fn get_item_val(ccx: @crate_ctxt, id: ast::node_id) -> ValueRef {
                 set_inline_hint_if_appr(i.attrs, llfn);
                 llfn
               }
-              ast::item_res(_, _, _, dtor_id, _) {
+              ast::item_res(_, _, _, dtor_id, _, _) {
                 // Note that the destructor is associated with the item's id,
                 // not the dtor_id. This is a bit counter-intuitive, but
                 // simplifies ty_res, which would have to carry around two
@@ -4726,7 +4733,7 @@ fn get_item_val(ccx: @crate_ctxt, id: ast::node_id) -> ValueRef {
             assert v.node.args.len() != 0u;
             let pth = *pth + [path_name(enm.ident), path_name(v.node.name)];
             let llfn = alt check enm.node {
-              ast::item_enum(_, _) {
+              ast::item_enum(_, _, _) {
                 register_fn(ccx, v.span, pth, id)
               }
             };
@@ -4747,7 +4754,7 @@ fn get_item_val(ccx: @crate_ctxt, id: ast::node_id) -> ValueRef {
 fn trans_constant(ccx: @crate_ctxt, it: @ast::item) {
     let _icx = ccx.insn_ctxt("trans_constant");
     alt it.node {
-      ast::item_enum(variants, _) {
+      ast::item_enum(variants, _, _) {
         let vi = ty::enum_variants(ccx.tcx, {crate: ast::local_crate,
                                              node: it.id});
         let mut i = 0;
diff --git a/src/rustc/middle/trans/common.rs b/src/rustc/middle/trans/common.rs
index 268719c9dc5..2cdea6ce8eb 100644
--- a/src/rustc/middle/trans/common.rs
+++ b/src/rustc/middle/trans/common.rs
@@ -882,7 +882,7 @@ fn node_id_type(bcx: block, id: ast::node_id) -> ty::t {
     let tcx = bcx.tcx();
     let t = ty::node_id_to_type(tcx, id);
     alt bcx.fcx.param_substs {
-      some(substs) { ty::substitute_type_params(tcx, substs.tys, t) }
+      some(substs) { ty::subst_tps(tcx, substs.tys, t) }
       _ { assert !ty::type_has_params(t); t }
     }
 }
@@ -894,7 +894,7 @@ fn node_id_type_params(bcx: block, id: ast::node_id) -> [ty::t] {
     let params = ty::node_id_to_type_params(tcx, id);
     alt bcx.fcx.param_substs {
       some(substs) {
-        vec::map(params) {|t| ty::substitute_type_params(tcx, substs.tys, t) }
+        vec::map(params) {|t| ty::subst_tps(tcx, substs.tys, t) }
       }
       _ { params }
     }
@@ -910,6 +910,10 @@ fn field_idx_strict(cx: ty::ctxt, sp: span, ident: ast::ident,
         }
 }
 
+fn dummy_substs(tps: [ty::t]) -> ty::substs {
+    {self_r: some(ty::re_bound(ty::br_self)), tps: tps}
+}
+
 //
 // Local Variables:
 // mode: rust
diff --git a/src/rustc/middle/trans/debuginfo.rs b/src/rustc/middle/trans/debuginfo.rs
index 5406ec7ce98..ce71a568c62 100644
--- a/src/rustc/middle/trans/debuginfo.rs
+++ b/src/rustc/middle/trans/debuginfo.rs
@@ -747,7 +747,7 @@ fn create_function(fcx: fn_ctxt) -> @metadata<subprogram_md> {
     let (ident, ret_ty, id) = alt cx.tcx.items.get(fcx.id) {
       ast_map::node_item(item, _) {
         alt item.node {
-          ast::item_fn(decl, _, _) | ast::item_res(decl, _, _, _, _) {
+          ast::item_fn(decl, _, _) | ast::item_res(decl, _, _, _, _, _) {
             (item.ident, decl.output, item.id)
           }
           _ { fcx.ccx.sess.span_bug(item.span, "create_function: item \
diff --git a/src/rustc/middle/trans/impl.rs b/src/rustc/middle/trans/impl.rs
index 21cefac65a8..fe545a9a4fd 100644
--- a/src/rustc/middle/trans/impl.rs
+++ b/src/rustc/middle/trans/impl.rs
@@ -178,7 +178,7 @@ fn resolve_vtable_in_fn_ctxt(fcx: fn_ctxt, vt: typeck::vtable_origin)
         let tys = alt fcx.param_substs {
           some(substs) {
             vec::map(tys, {|t|
-                ty::substitute_type_params(fcx.ccx.tcx, substs.tys, t)
+                ty::subst_tps(fcx.ccx.tcx, substs.tys, t)
             })
           }
           _ { tys }
@@ -244,7 +244,7 @@ fn make_impl_vtable(ccx: @crate_ctxt, impl_id: ast::def_id, substs: [ty::t],
     let ifce_id = ty::ty_to_def_id(option::get(ty::impl_iface(tcx, impl_id)));
     let has_tps = (*ty::lookup_item_type(ccx.tcx, impl_id).bounds).len() > 0u;
     make_vtable(ccx, vec::map(*ty::iface_methods(tcx, ifce_id), {|im|
-        let fty = ty::substitute_type_params(tcx, substs,
+        let fty = ty::subst_tps(tcx, substs,
                                              ty::mk_fn(tcx, im.fty));
         if (*im.tps).len() > 0u || ty::type_has_vars(fty) {
             C_null(T_ptr(T_nil()))
diff --git a/src/rustc/middle/trans/reachable.rs b/src/rustc/middle/trans/reachable.rs
index 863549f458e..05cc2224384 100644
--- a/src/rustc/middle/trans/reachable.rs
+++ b/src/rustc/middle/trans/reachable.rs
@@ -84,7 +84,7 @@ fn traverse_public_item(cx: ctx, item: @item) {
               for vec::each(nm.items) {|item| cx.rmap.insert(item.id, ()); }
           }
       }
-      item_res(_, tps, blk, _, _) {
+      item_res(_, tps, blk, _, _, _) {
         // resources seem to be unconditionally inlined
         traverse_inline_body(cx, blk);
       }
@@ -102,7 +102,7 @@ fn traverse_public_item(cx: ctx, item: @item) {
             }
         }
       }
-      item_class(tps, _ifaces, items, ctor) {
+      item_class(tps, _ifaces, items, ctor, _) {
         cx.rmap.insert(ctor.node.id, ());
         for vec::each(items) {|item|
             alt item.node {
@@ -117,7 +117,8 @@ fn traverse_public_item(cx: ctx, item: @item) {
             }
         }
       }
-      item_const(_, _) | item_ty(_, _) | item_enum(_, _) | item_iface(_, _) {}
+      item_const(_, _) | item_ty(_, _, _) |
+      item_enum(_, _, _) | item_iface(_, _) {}
     }
 }
 
@@ -152,7 +153,9 @@ fn traverse_all_resources(cx: ctx, crate_mod: _mod) {
         visit_item: {|i, cx, v|
             visit::visit_item(i, cx, v);
             alt i.node {
-              item_res(_, _, _, _, _) { traverse_public_item(cx, i); }
+              item_res(_, _, _, _, _, _) {
+                traverse_public_item(cx, i);
+              }
               _ {}
             }
         }
diff --git a/src/rustc/middle/trans/shape.rs b/src/rustc/middle/trans/shape.rs
index e031cf2462d..effb71c0c8c 100644
--- a/src/rustc/middle/trans/shape.rs
+++ b/src/rustc/middle/trans/shape.rs
@@ -315,7 +315,9 @@ fn shape_of(ccx: @crate_ctxt, t: ty::t, ty_param_map: [uint]) -> [u8] {
         add_substr(s, shape_of(ccx, unit_ty, ty_param_map));
         s
       }
-      ty::ty_enum(did, tps) {
+      ty::ty_enum(did, substs) {
+        let tps = substs.tps;
+
         alt enum_kind(ccx, did) {
           // FIXME: For now we do this.
           tk_unit { [s_variant_enum_t(ccx.tcx)] }
@@ -437,8 +439,9 @@ fn shape_of(ccx: @crate_ctxt, t: ty::t, ty_param_map: [uint]) -> [u8] {
         add_substr(s, shape_of(ccx, tm.ty, ty_param_map));
         s
       }
-      ty::ty_res(did, raw_subt, tps) {
-        let subt = ty::substitute_type_params(ccx.tcx, tps, raw_subt);
+      ty::ty_res(did, raw_subt, substs) {
+        let subt = ty::subst(ccx.tcx, substs, raw_subt);
+        let tps = substs.tps;
         let ri = {did: did, tps: tps};
         let id = interner::intern(ccx.shape_cx.resources, ri);
 
@@ -651,7 +654,7 @@ fn llalign_of(cx: @crate_ctxt, t: TypeRef) -> ValueRef {
 fn static_size_of_enum(cx: @crate_ctxt, t: ty::t) -> uint {
     if cx.enum_sizes.contains_key(t) { ret cx.enum_sizes.get(t); }
     alt ty::get(t).struct {
-      ty::ty_enum(tid, subtys) {
+      ty::ty_enum(tid, substs) {
         // Compute max(variant sizes).
         let mut max_size = 0u;
         let variants = ty::enum_variants(cx.tcx, tid);
@@ -659,7 +662,7 @@ fn static_size_of_enum(cx: @crate_ctxt, t: ty::t) -> uint {
             let tup_ty = simplify_type(cx.tcx,
                                        ty::mk_tup(cx.tcx, variant.args));
             // Perform any type parameter substitutions.
-            let tup_ty = ty::substitute_type_params(cx.tcx, subtys, tup_ty);
+            let tup_ty = ty::subst(cx.tcx, substs, tup_ty);
             // Here we possibly do a recursive call.
             let this_size =
                 llsize_of_real(cx, type_of::type_of(cx, tup_ty));
@@ -690,8 +693,8 @@ fn simplify_type(tcx: ty::ctxt, typ: ty::t) -> ty::t {
           ty::ty_estr(ty::vstore_uniq) | ty::ty_estr(ty::vstore_box) |
           ty::ty_ptr(_) | ty::ty_rptr(_,_) { nilptr(tcx) }
           ty::ty_fn(_) { ty::mk_tup(tcx, [nilptr(tcx), nilptr(tcx)]) }
-          ty::ty_res(_, sub, tps) {
-            let sub1 = ty::substitute_type_params(tcx, tps, sub);
+          ty::ty_res(_, sub, substs) {
+            let sub1 = ty::subst(tcx, substs, sub);
             ty::mk_tup(tcx, [ty::mk_int(tcx), simplify_type(tcx, sub1)])
           }
           ty::ty_evec(_, ty::vstore_slice(_)) |
diff --git a/src/rustc/middle/trans/type_of.rs b/src/rustc/middle/trans/type_of.rs
index eef0f0b5101..7f11108edde 100644
--- a/src/rustc/middle/trans/type_of.rs
+++ b/src/rustc/middle/trans/type_of.rs
@@ -89,8 +89,8 @@ fn type_of(cx: @crate_ctxt, t: ty::t) -> TypeRef {
       }
       ty::ty_fn(_) { T_fn_pair(cx, type_of_fn_from_ty(cx, t)) }
       ty::ty_iface(_, _) { T_opaque_iface(cx) }
-      ty::ty_res(_, sub, tps) {
-        let sub1 = ty::substitute_type_params(cx.tcx, tps, sub);
+      ty::ty_res(_, sub, substs) {
+        let sub1 = ty::subst(cx.tcx, substs, sub);
         ret T_struct([T_i8(), type_of(cx, sub1)]);
       }
       ty::ty_param(_, _) { T_typaram(cx.tn) }
diff --git a/src/rustc/middle/trans/type_use.rs b/src/rustc/middle/trans/type_use.rs
index c7f09c9dc5f..59ae4ec6d04 100644
--- a/src/rustc/middle/trans/type_use.rs
+++ b/src/rustc/middle/trans/type_use.rs
@@ -65,7 +65,7 @@ fn type_uses_for(ccx: @crate_ctxt, fn_id: def_id, n_tps: uint)
     };
     alt check map_node {
       ast_map::node_item(@{node: item_fn(_, _, body), _}, _) |
-      ast_map::node_item(@{node: item_res(_, _, body, _, _), _}, _) |
+      ast_map::node_item(@{node: item_res(_, _, body, _, _, _), _}, _) |
       ast_map::node_method(@{body, _}, _, _) {
         handle_body(cx, body);
       }
@@ -107,13 +107,12 @@ fn type_needs_inner(cx: ctx, use: uint, ty: ty::t,
             alt ty::get(ty).struct {
               ty::ty_fn(_) | ty::ty_ptr(_) | ty::ty_rptr(_, _) |
               ty::ty_box(_) | ty::ty_iface(_, _) { false }
-              ty::ty_enum(did, tps) {
+              ty::ty_enum(did, substs) {
                 if option::is_none(list::find(enums_seen, {|id| id == did})) {
                     let seen = list::cons(did, @enums_seen);
                     for vec::each(*ty::enum_variants(cx.ccx.tcx, did)) {|v|
                         for vec::each(v.args) {|aty|
-                            let t = ty::substitute_type_params(cx.ccx.tcx,
-                                                               tps, aty);
+                            let t = ty::subst(cx.ccx.tcx, substs, aty);
                             type_needs_inner(cx, use, t, seen);
                         }
                     }
@@ -153,7 +152,7 @@ fn mark_for_expr(cx: ctx, e: @expr) {
         }
       }
       expr_path(_) {
-        option::iter(cx.ccx.tcx.node_type_substs.find(e.id)) {|ts|
+        cx.ccx.tcx.node_type_substs.find(e.id).iter {|ts|
             let id = ast_util::def_id_of_def(cx.ccx.tcx.def_map.get(e.id));
             vec::iter2(type_uses_for(cx.ccx, id, ts.len()), ts) {|uses, subst|
                 type_needs(cx, uses, subst)
diff --git a/src/rustc/middle/tstate/pre_post_conditions.rs b/src/rustc/middle/tstate/pre_post_conditions.rs
index 16578d8b1f3..03f5a56a1c0 100644
--- a/src/rustc/middle/tstate/pre_post_conditions.rs
+++ b/src/rustc/middle/tstate/pre_post_conditions.rs
@@ -48,8 +48,8 @@ fn find_pre_post_item(ccx: crate_ctxt, i: item) {
       }
       item_mod(m) { find_pre_post_mod(m); }
       item_native_mod(nm) { find_pre_post_native_mod(nm); }
-      item_ty(_, _) | item_enum(_, _) | item_iface(_, _) { ret; }
-      item_res(_, _, body, dtor_id, _) {
+      item_ty(_, _, _) | item_enum(_, _, _) | item_iface(_, _) { ret; }
+      item_res(_, _, body, dtor_id, _, _) {
         let fcx =
             {enclosing: ccx.fm.get(dtor_id),
              id: dtor_id,
@@ -57,7 +57,7 @@ fn find_pre_post_item(ccx: crate_ctxt, i: item) {
              ccx: ccx};
         find_pre_post_fn(fcx, body);
       }
-      item_class(_,_,_,_) {
+      item_class(_,_,_,_,_) {
           fail "find_pre_post_item: shouldn't be called on item_class";
       }
       item_impl(_, _, _, ms) {
diff --git a/src/rustc/middle/ty.rs b/src/rustc/middle/ty.rs
index 3c7421b2fd2..fd87173005b 100644
--- a/src/rustc/middle/ty.rs
+++ b/src/rustc/middle/ty.rs
@@ -61,7 +61,7 @@ export sequence_element_type;
 export sort_methods;
 export stmt_node_id;
 export sty;
-export substitute_type_params;
+export subst, subst_tps, substs_is_noop, substs;
 export t;
 export new_ty_hash;
 export enum_variants, substd_enum_variants;
@@ -281,6 +281,23 @@ enum bound_region {
     br_named(str) // A named region parameter.
 }
 
+type opt_region = option<region>;
+
+// The type substs represents the kinds of things that can be substituted into
+// a type.  There may be at most one region parameter (self_r), along with
+// some number of type parameters (tps).
+//
+// The region parameter is present on nominative types (enums, resources,
+// classes) that are declared as having a region parameter.  If the type is
+// declared as `enum foo&`, then self_r should always be non-none.  If the
+// type is declared as `enum foo`, then self_r will always be none.  In the
+// latter case, typeck::ast_ty_to_ty() will reject any references to `&T` or
+// `&self.T` within the type and report an error.
+type substs = {
+    self_r: opt_region,
+    tps: [t]
+};
+
 // NB: If you change this, you'll probably want to change the corresponding
 // AST structure in front/ast::rs as well.
 enum sty {
@@ -292,7 +309,7 @@ enum sty {
     ty_float(ast::float_ty),
     ty_str,
     ty_estr(vstore),
-    ty_enum(def_id, [t]),
+    ty_enum(def_id, substs),
     ty_box(mt),
     ty_uniq(mt),
     ty_vec(mt),
@@ -302,8 +319,8 @@ enum sty {
     ty_rec([field]),
     ty_fn(fn_ty),
     ty_iface(def_id, [t]),
-    ty_class(def_id, [t]),
-    ty_res(def_id, t, [t]),
+    ty_class(def_id, substs),
+    ty_res(def_id, t, substs),
     ty_tup([t]),
 
     ty_var(ty_vid), // type variable during typechecking
@@ -389,7 +406,9 @@ fn param_bounds_to_kind(bounds: param_bounds) -> kind {
     kind
 }
 
-type ty_param_bounds_and_ty = {bounds: @[param_bounds], ty: t};
+type ty_param_bounds_and_ty = {bounds: @[param_bounds],
+                               rp: ast::region_param,
+                               ty: t};
 
 type type_cache = hashmap<ast::def_id, ty_param_bounds_and_ty>;
 
@@ -475,7 +494,13 @@ fn mk_t_with_id(cx: ctxt, st: sty, o_def_id: option<ast::def_id>) -> t {
       ty_opaque_box {}
       ty_param(_, _) { has_params = true; }
       ty_var(_) | ty_self(_) { has_vars = true; }
-      ty_enum(_, tys) | ty_iface(_, tys) | ty_class(_, tys) {
+      ty_enum(_, substs) | ty_class(_, substs) {
+        for substs.tps.each {|tt|
+            derive_flags(has_params, has_vars, has_regions, tt);
+        }
+        substs.self_r.iter { |_i| has_regions = true; }
+      }
+      ty_iface(_, tys) {
         for tys.each {|tt|
             derive_flags(has_params, has_vars, has_regions, tt);
         }
@@ -506,9 +531,9 @@ fn mk_t_with_id(cx: ctxt, st: sty, o_def_id: option<ast::def_id>) -> t {
         }
         derive_flags(has_params, has_vars, has_regions, f.output);
       }
-      ty_res(_, tt, tps) {
+      ty_res(_, tt, substs) {
         derive_flags(has_params, has_vars, has_regions, tt);
-        for tps.each {|tt|
+        for substs.tps.each {|tt|
             derive_flags(has_params, has_vars, has_regions, tt);
         }
       }
@@ -553,8 +578,8 @@ fn mk_estr(cx: ctxt, t: vstore) -> t {
     mk_t(cx, ty_estr(t))
 }
 
-fn mk_enum(cx: ctxt, did: ast::def_id, tys: [t]) -> t {
-    mk_t(cx, ty_enum(did, tys))
+fn mk_enum(cx: ctxt, did: ast::def_id, substs: substs) -> t {
+    mk_t(cx, ty_enum(did, substs))
 }
 
 fn mk_box(cx: ctxt, tm: mt) -> t { mk_t(cx, ty_box(tm)) }
@@ -602,12 +627,13 @@ fn mk_iface(cx: ctxt, did: ast::def_id, tys: [t]) -> t {
     mk_t(cx, ty_iface(did, tys))
 }
 
-fn mk_class(cx: ctxt, class_id: ast::def_id, tys: [t]) -> t {
-    mk_t(cx, ty_class(class_id, tys))
+fn mk_class(cx: ctxt, class_id: ast::def_id, substs: substs) -> t {
+    mk_t(cx, ty_class(class_id, substs))
 }
 
-fn mk_res(cx: ctxt, did: ast::def_id, inner: t, tps: [t]) -> t {
-    mk_t(cx, ty_res(did, inner, tps))
+fn mk_res(cx: ctxt, did: ast::def_id,
+          inner: t, substs: substs) -> t {
+    mk_t(cx, ty_res(did, inner, substs))
 }
 
 fn mk_var(cx: ctxt, v: ty_vid) -> t { mk_t(cx, ty_var(v)) }
@@ -657,8 +683,10 @@ fn maybe_walk_ty(ty: t, f: fn(t) -> bool) {
       ty_ptr(tm) | ty_rptr(_, tm) {
         maybe_walk_ty(tm.ty, f);
       }
-      ty_enum(_, subtys) | ty_iface(_, subtys) | ty_class(_, subtys)
-       | ty_self(subtys) {
+      ty_enum(_, substs) | ty_class(_, substs) {
+        for substs.tps.each {|subty| maybe_walk_ty(subty, f); }
+      }
+      ty_iface(_, subtys) |ty_self(subtys) {
         for subtys.each {|subty| maybe_walk_ty(subty, f); }
       }
       ty_rec(fields) {
@@ -669,9 +697,9 @@ fn maybe_walk_ty(ty: t, f: fn(t) -> bool) {
         for ft.inputs.each {|a| maybe_walk_ty(a.ty, f); }
         maybe_walk_ty(ft.output, f);
       }
-      ty_res(_, sub, tps) {
+      ty_res(_, sub, substs) {
         maybe_walk_ty(sub, f);
-        for tps.each {|tp| maybe_walk_ty(tp, f); }
+        for substs.tps.each {|tp| maybe_walk_ty(tp, f); }
       }
       ty_constr(sub, _) { maybe_walk_ty(sub, f); }
       ty_uniq(tm) { maybe_walk_ty(tm.ty, f); }
@@ -683,6 +711,11 @@ fn fold_sty_to_ty(tcx: ty::ctxt, sty: sty, foldop: fn(t) -> t) -> t {
 }
 
 fn fold_sty(sty: sty, fldop: fn(t) -> t) -> sty {
+    fn fold_substs(substs: substs, fldop: fn(t) -> t) -> substs {
+        {self_r: substs.self_r,
+         tps: substs.tps.map { |t| fldop(t) }}
+    }
+
     alt sty {
       ty_box(tm) {
         ty_box({ty: fldop(tm.ty), mutbl: tm.mutbl})
@@ -699,8 +732,8 @@ fn fold_sty(sty: sty, fldop: fn(t) -> t) -> sty {
       ty_evec(tm, vst) {
         ty_evec({ty: fldop(tm.ty), mutbl: tm.mutbl}, vst)
       }
-      ty_enum(tid, subtys) {
-        ty_enum(tid, vec::map(subtys) {|t| fldop(t) })
+      ty_enum(tid, substs) {
+        ty_enum(tid, fold_substs(substs, fldop))
       }
       ty_iface(did, subtys) {
         ty_iface(did, vec::map(subtys) {|t| fldop(t) })
@@ -728,9 +761,9 @@ fn fold_sty(sty: sty, fldop: fn(t) -> t) -> sty {
         let new_output = fldop(f.output);
         ty_fn({inputs: new_args, output: new_output with f})
       }
-      ty_res(did, subty, tps) {
-        let new_tps = vec::map(tps) {|ty| fldop(ty) };
-        ty_res(did, fldop(subty), new_tps)
+      ty_res(did, subty, substs) {
+        ty_res(did, fldop(subty),
+               fold_substs(substs, fldop))
       }
       ty_rptr(r, tm) {
         ty_rptr(r, {ty: fldop(tm.ty), mutbl: tm.mutbl})
@@ -738,9 +771,8 @@ fn fold_sty(sty: sty, fldop: fn(t) -> t) -> sty {
       ty_constr(subty, cs) {
         ty_constr(fldop(subty), cs)
       }
-      ty_class(did, tps) {
-        let new_tps = vec::map(tps) {|ty| fldop(ty) };
-        ty_class(did, new_tps)
+      ty_class(did, substs) {
+        ty_class(did, fold_substs(substs, fldop))
       }
       ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
       ty_str | ty_estr(_) | ty_type | ty_opaque_closure_ptr(_) |
@@ -765,6 +797,61 @@ fn fold_ty_var(cx: ctxt, t0: t, fldop: fn(ty_vid) -> t) -> t {
     }
 }
 
+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 {
+
+        {self_r: substs.self_r.map { |r| fldr(r) },
+         tps: substs.tps.map { |t| fldt(t) }}
+    }
+
+    let tb = ty::get(ty);
+    alt tb.struct {
+      ty::ty_rptr(r, mt) {
+        let m_r = fldr(r);
+        let m_t = fldt(mt.ty);
+        ty::mk_rptr(cx, m_r, {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, {ty: m_t, mutbl: mt.mutbl}, vstore_slice(m_r))
+      }
+      ty_enum(def_id, substs) {
+        ty::mk_enum(cx, def_id, fold_substs(substs, fldr, fldt))
+      }
+      ty_class(def_id, substs) {
+        ty::mk_class(cx, def_id, fold_substs(substs, fldr, fldt))
+      }
+      ty_res(def_id, t, substs) {
+        ty::mk_res(cx, def_id, fldt(t),
+                   fold_substs(substs, fldr, fldt))
+      }
+      sty @ ty_fn(_) {
+        fold_sty_to_ty(cx, sty) {|t|
+            fldfnt(t)
+        }
+      }
+      sty {
+        fold_sty_to_ty(cx, sty) {|t|
+            fldt(t)
+        }
+      }
+    }
+}
+
 // n.b. this function is intended to eventually replace fold_region() below,
 // that is why its name is so similar.
 fn fold_regions(
@@ -774,36 +861,13 @@ fn fold_regions(
 
     fn do_fold(cx: ctxt, ty: t, in_fn: bool,
                fldr: fn(region, bool) -> region) -> t {
-        let tb = ty::get(ty);
-        if !tb.has_regions { ret ty; }
-        alt tb.struct {
-          ty::ty_rptr(r, mt) {
-            let m_r = fldr(r, in_fn);
-            let m_t = do_fold(cx, mt.ty, in_fn, fldr);
-            ty::mk_rptr(cx, m_r, {ty: m_t, mutbl: mt.mutbl})
-          }
-          ty_estr(vstore_slice(r)) {
-            let m_r = fldr(r, in_fn);
-            ty::mk_estr(cx, vstore_slice(m_r))
-          }
-          ty_evec(mt, vstore_slice(r)) {
-            let m_r = fldr(r, in_fn);
-            let m_t = do_fold(cx, mt.ty, in_fn, fldr);
-            ty::mk_evec(cx, {ty: m_t, mutbl: mt.mutbl}, vstore_slice(m_r))
-          }
-          sty @ ty_fn(_) {
-            fold_sty_to_ty(cx, sty) {|t|
-                do_fold(cx, t, true, fldr)
-            }
-          }
-          sty {
-            fold_sty_to_ty(cx, sty) {|t|
-                do_fold(cx, t, in_fn, fldr)
-            }
-          }
-        }
+        if !type_has_regions(ty) { ret ty; }
+        fold_regions_and_ty(
+            cx, ty,
+            { |r| fldr(r, in_fn) },
+            { |t| do_fold(cx, t, true, fldr) },
+            { |t| do_fold(cx, t, in_fn, fldr) })
     }
-
     do_fold(cx, ty, false, fldr)
 }
 
@@ -842,13 +906,63 @@ fn fold_region(cx: ctxt, t0: t, fldop: fn(region, bool) -> region) -> t {
     do_fold(cx, t0, false, fldop)
 }
 
-fn substitute_type_params(cx: ctxt, substs: [ty::t], typ: t) -> t {
-    if substs.len() == 0u { ret typ; }
-    let tb = get(typ);
+// Substitute *only* type parameters.  Used in trans where regions are erased.
+fn subst_tps(cx: ctxt, tps: [t], typ: t) -> t {
+    if tps.len() == 0u { ret typ; }
+    let tb = ty::get(typ);
     if !tb.has_params { ret typ; }
     alt tb.struct {
-      ty_param(idx, _) { substs[idx] }
-      s { mk_t(cx, fold_sty(s) {|t| substitute_type_params(cx, substs, t)}) }
+      ty_param(idx, _) { tps[idx] }
+      sty { fold_sty_to_ty(cx, sty) {|t| subst_tps(cx, tps, t) } }
+    }
+}
+
+fn substs_is_noop(substs: substs) -> bool {
+    substs.tps.len() == 0u && substs.self_r.is_none()
+}
+
+fn substs_to_str(cx: ctxt, substs: substs) -> str {
+    #fmt["substs(self_r=%s, tps=%?)",
+         substs.self_r.map_default("none", { |r| region_to_str(cx, r) }),
+         substs.tps.map { |t| ty_to_str(cx, t) }]
+}
+
+fn subst(cx: ctxt,
+         substs: substs,
+         typ: t) -> t {
+
+    if substs_is_noop(substs) { ret typ; }
+    #debug["subst(substs=%s, typ=%s)",
+           substs_to_str(cx, substs),
+           ty_to_str(cx, typ)];
+    let r = do_subst(cx, substs, typ);
+    #debug["  r = %s", ty_to_str(cx, r)];
+    ret r;
+
+    fn do_subst(cx: ctxt,
+                substs: substs,
+                typ: t) -> t {
+        let tb = get(typ);
+        if !tb.has_params && !tb.has_regions { ret typ; }
+        alt tb.struct {
+          ty_param(idx, _) { substs.tps[idx] }
+          _ {
+            fold_regions_and_ty(
+                cx, typ,
+                { |r|
+                    alt r {
+                      re_bound(br_self) {
+                        option::get(substs.self_r)
+                      }
+                      _ {
+                        r
+                      }
+                    }
+                },
+                { |t| do_subst(cx, substs, t) },
+                { |t| do_subst(cx, substs, t) })
+          }
+        }
     }
 }
 
@@ -862,7 +976,7 @@ fn type_is_bool(ty: t) -> bool { get(ty).struct == ty_bool }
 
 fn type_is_structural(ty: t) -> bool {
     alt get(ty).struct {
-      ty_rec(_) | ty_class(_,_) | ty_tup(_) | ty_enum(_, _) | ty_fn(_) |
+      ty_rec(_) | ty_class(_, _) | ty_tup(_) | ty_enum(_, _) | ty_fn(_) |
       ty_iface(_, _) | ty_res(_, _, _) | ty_evec(_, vstore_fixed(_))
       | ty_estr(vstore_fixed(_)) { true }
       _ { false }
@@ -994,8 +1108,8 @@ fn type_needs_drop(cx: ctxt, ty: t) -> bool {
         for flds.each {|f| if type_needs_drop(cx, f.mt.ty) { accum = true; } }
         accum
       }
-      ty_class(did, ts) {
-        for vec::each(ty::class_items_as_fields(cx, did, ts)) {|f|
+      ty_class(did, substs) {
+        for vec::each(ty::class_items_as_fields(cx, did, substs)) {|f|
             if type_needs_drop(cx, f.mt.ty) { accum = true; }
         }
         accum
@@ -1005,12 +1119,12 @@ fn type_needs_drop(cx: ctxt, ty: t) -> bool {
         for elts.each {|m| if type_needs_drop(cx, m) { accum = true; } }
         accum
       }
-      ty_enum(did, tps) {
+      ty_enum(did, substs) {
         let variants = enum_variants(cx, did);
         for vec::each(*variants) {|variant|
             for variant.args.each {|aty|
                 // Perform any type parameter substitutions.
-                let arg_ty = substitute_type_params(cx, tps, aty);
+                let arg_ty = subst(cx, substs, aty);
                 if type_needs_drop(cx, arg_ty) { accum = true; }
             }
             if accum { break; }
@@ -1064,10 +1178,10 @@ fn type_needs_unwind_cleanup_(cx: ctxt, ty: t,
           ty_rec(_) | ty_tup(_) | ty_ptr(_) {
             true
           }
-          ty_enum(did, tps) {
+          ty_enum(did, substs) {
             for vec::each(*enum_variants(cx, did)) {|v|
                 for v.args.each {|aty|
-                    let t = substitute_type_params(cx, tps, aty);
+                    let t = subst(cx, substs, aty);
                     needs_unwind_cleanup |=
                         type_needs_unwind_cleanup_(cx, t, tycache,
                                                    encountered_box);
@@ -1211,7 +1325,7 @@ fn type_kind(cx: ctxt, ty: t) -> kind {
         lowest
       }
       // Enums lower to the lowest of their variants.
-      ty_enum(did, tps) {
+      ty_enum(did, substs) {
         let mut lowest = kind_sendable;
         let variants = enum_variants(cx, did);
         if vec::len(*variants) == 0u {
@@ -1220,7 +1334,7 @@ fn type_kind(cx: ctxt, ty: t) -> kind {
             for vec::each(*variants) {|variant|
                 for variant.args.each {|aty|
                     // Perform any type parameter substitutions.
-                    let arg_ty = substitute_type_params(cx, tps, aty);
+                    let arg_ty = subst(cx, substs, aty);
                     lowest = lower_kind(lowest, type_kind(cx, arg_ty));
                     if lowest == kind_noncopyable { break; }
                 }
@@ -1316,11 +1430,11 @@ fn is_instantiable(cx: ctxt, r_ty: t) -> bool {
             false
           }
 
-          ty_class(did, tps) {
+          ty_class(did, substs) {
             vec::push(*seen, did);
             let r = vec::any(lookup_class_fields(cx, did)) {|f|
                 let fty = ty::lookup_item_type(cx, f.id);
-                let sty = substitute_type_params(cx, tps, fty.ty);
+                let sty = subst(cx, substs, fty.ty);
                 type_requires(cx, seen, r_ty, sty)
             };
             vec::pop(*seen);
@@ -1331,9 +1445,9 @@ fn is_instantiable(cx: ctxt, r_ty: t) -> bool {
             false
           }
 
-          ty_res(did, sub, tps) {
+          ty_res(did, sub, substs) {
             vec::push(*seen, did);
-            let sty = substitute_type_params(cx, tps, sub);
+            let sty = subst(cx, substs, sub);
             let r = type_requires(cx, seen, r_ty, sty);
             vec::pop(*seen);
             r
@@ -1349,12 +1463,12 @@ fn is_instantiable(cx: ctxt, r_ty: t) -> bool {
             false
           }
 
-          ty_enum(did, tps) {
+          ty_enum(did, substs) {
             vec::push(*seen, did);
             let vs = enum_variants(cx, did);
             let r = vec::len(*vs) > 0u && vec::all(*vs) {|variant|
                 vec::any(variant.args) {|aty|
-                    let sty = substitute_type_params(cx, tps, aty);
+                    let sty = subst(cx, substs, aty);
                     type_requires(cx, seen, r_ty, sty)
                 }
             };
@@ -1380,10 +1494,10 @@ fn type_structurally_contains(cx: ctxt, ty: t, test: fn(sty) -> bool) ->
     let sty = get(ty).struct;
     if test(sty) { ret true; }
     alt sty {
-      ty_enum(did, tps) {
+      ty_enum(did, substs) {
         for vec::each(*enum_variants(cx, did)) {|variant|
             for variant.args.each {|aty|
-                let sty = substitute_type_params(cx, tps, aty);
+                let sty = subst(cx, substs, aty);
                 if type_structurally_contains(cx, sty, test) { ret true; }
             }
         }
@@ -1401,8 +1515,8 @@ fn type_structurally_contains(cx: ctxt, ty: t, test: fn(sty) -> bool) ->
         }
         ret false;
       }
-      ty_res(_, sub, tps) {
-        let sty = substitute_type_params(cx, tps, sub);
+      ty_res(_, sub, substs) {
+        let sty = subst(cx, substs, sub);
         ret type_structurally_contains(cx, sty, test);
       }
       ty_evec(mt, vstore_fixed(_)) {
@@ -1485,13 +1599,13 @@ fn type_is_pod(cx: ctxt, ty: t) -> bool {
       ty_str | ty_box(_) | ty_uniq(_) | ty_vec(_) | ty_fn(_) |
       ty_iface(_, _) | ty_rptr(_,_) | ty_opaque_box { result = false; }
       // Structural types
-      ty_enum(did, tps) {
+      ty_enum(did, substs) {
         let variants = enum_variants(cx, did);
         for vec::each(*variants) {|variant|
             let tup_ty = mk_tup(cx, variant.args);
 
             // Perform any type parameter substitutions.
-            let tup_ty = substitute_type_params(cx, tps, tup_ty);
+            let tup_ty = subst(cx, substs, tup_ty);
             if !type_is_pod(cx, tup_ty) { result = false; }
         }
       }
@@ -1507,8 +1621,8 @@ fn type_is_pod(cx: ctxt, ty: t) -> bool {
       ty_evec(mt, vstore_fixed(_)) {
         result = type_is_pod(cx, mt.ty);
       }
-      ty_res(_, inner, tps) {
-        result = type_is_pod(cx, substitute_type_params(cx, tps, inner));
+      ty_res(_, inner, substs) {
+        result = type_is_pod(cx, subst(cx, substs, inner));
       }
       ty_constr(subt, _) { result = type_is_pod(cx, subt); }
       ty_param(_, _) { result = false; }
@@ -1530,7 +1644,7 @@ fn type_is_enum(ty: t) -> bool {
 // constructors
 fn type_is_c_like_enum(cx: ctxt, ty: t) -> bool {
     alt get(ty).struct {
-      ty_enum(did, tps) {
+      ty_enum(did, substs) {
         let variants = enum_variants(cx, did);
         let some_n_ary = vec::any(*variants, {|v| vec::len(v.args) > 0u});
         ret !some_n_ary;
@@ -1562,15 +1676,15 @@ fn type_autoderef(cx: ctxt, t: t) -> t {
     loop {
         alt get(t1).struct {
           ty_box(mt) | ty_uniq(mt) | ty::ty_rptr(_, mt) { t1 = mt.ty; }
-          ty_res(_, inner, tps) {
-            t1 = substitute_type_params(cx, tps, inner);
+          ty_res(_, inner, substs) {
+            t1 = subst(cx, substs, inner);
           }
-          ty_enum(did, tps) {
+          ty_enum(did, substs) {
             let variants = enum_variants(cx, did);
             if vec::len(*variants) != 1u || vec::len(variants[0].args) != 1u {
                 break;
             }
-            t1 = substitute_type_params(cx, tps, variants[0].args[0]);
+            t1 = subst(cx, substs, variants[0].args[0]);
           }
           _ { break; }
         }
@@ -1627,6 +1741,10 @@ fn hash_type_structure(st: sty) -> uint {
           re_bot        { 4u }
         }
     }
+    fn hash_substs(h: uint, substs: substs) -> uint {
+        let h = hash_subtys(h, substs.tps);
+        h + substs.self_r.map_default(0u, hash_region)
+    }
     alt st {
       ty_nil { 0u } ty_bool { 1u }
       ty_int(t) {
@@ -1646,10 +1764,9 @@ fn hash_type_structure(st: sty) -> uint {
       }
       ty_estr(_) { 16u }
       ty_str { 17u }
-      ty_enum(did, tys) {
+      ty_enum(did, substs) {
         let mut h = hash_def(18u, did);
-        for tys.each {|typ| h = hash_subty(h, typ); }
-        h
+        hash_substs(h, substs)
       }
       ty_box(mt) { hash_subty(19u, mt.ty) }
       ty_evec(mt, _) { hash_subty(20u, mt.ty) }
@@ -1679,9 +1796,9 @@ fn hash_type_structure(st: sty) -> uint {
         let mut h = (46u << 2u) + hash_region(region);
         hash_subty(h, mt.ty)
       }
-      ty_res(did, sub, tps) {
+      ty_res(did, sub, substs) {
         let mut h = hash_subty(hash_def(18u, did), sub);
-        hash_subtys(h, tps)
+        hash_substs(h, substs)
       }
       ty_constr(t, cs) {
         let mut h = hash_subty(36u, t);
@@ -1698,10 +1815,9 @@ fn hash_type_structure(st: sty) -> uint {
       ty_opaque_closure_ptr(ck_box) { 42u }
       ty_opaque_closure_ptr(ck_uniq) { 43u }
       ty_opaque_box { 44u }
-      ty_class(did, tys) {
-          let mut h = hash_def(45u, did);
-          for tys.each {|typ| h = hash_subty(h, typ); }
-          h
+      ty_class(did, substs) {
+        let mut h = hash_def(45u, did);
+        hash_substs(h, substs)
       }
     }
 }
@@ -1997,7 +2113,7 @@ fn ty_sort_str(cx: ctxt, t: t) -> str {
         ty_to_str(cx, t)
       }
 
-      ty_enum(_, _) { "enum" }
+      ty_enum(id, _) { #fmt["enum %s", item_path_str(cx, id)] }
       ty_box(_) { "@-ptr" }
       ty_uniq(_) { "~-ptr" }
       ty_evec(_, _) | ty_vec(_) { "vector" }
@@ -2005,9 +2121,9 @@ fn ty_sort_str(cx: ctxt, t: t) -> str {
       ty_rptr(_, _) { "&-ptr" }
       ty_rec(_) { "record" }
       ty_fn(_) { "fn" }
-      ty_iface(_, _) { "iface" }
-      ty_class(_, _) { "class" }
-      ty_res(_, _, _) { "resource" }
+      ty_iface(id, _) { #fmt["iface %s", item_path_str(cx, id)] }
+      ty_class(id, _) { #fmt["class %s", item_path_str(cx, id)] }
+      ty_res(id, _, _) { #fmt["resource %s", item_path_str(cx, id)] }
       ty_tup(_) { "tuple" }
       ty_var(_) { "variable" }
       ty_param(_, _) { "type parameter" }
@@ -2148,15 +2264,15 @@ fn ty_to_def_id(ty: t) -> ast::def_id {
 type variant_info = @{args: [t], ctor_ty: t, name: str,
                       id: ast::def_id, disr_val: int};
 
-fn substd_enum_variants(cx: ctxt, id: ast::def_id, tps: [ty::t])
-    -> [variant_info] {
+fn substd_enum_variants(cx: ctxt,
+                        id: ast::def_id,
+                        substs: substs) -> [variant_info] {
     vec::map(*enum_variants(cx, id)) { |variant_info|
         let substd_args = vec::map(variant_info.args) {|aty|
-            substitute_type_params(cx, tps, aty)
+            subst(cx, substs, aty)
         };
 
-        let substd_ctor_ty =
-            substitute_type_params(cx, tps, variant_info.ctor_ty);
+        let substd_ctor_ty = subst(cx, substs, variant_info.ctor_ty);
 
         @{args: substd_args, ctor_ty: substd_ctor_ty with *variant_info}
     }
@@ -2214,6 +2330,7 @@ fn enum_variants(cx: ctxt, id: ast::def_id) -> @[variant_info] {
       some(variants) { ret variants; }
       _ { /* fallthrough */ }
     }
+
     let result = if ast::local_crate != id.crate {
         @csearch::get_enum_variants(cx, id)
     } else {
@@ -2221,13 +2338,15 @@ fn enum_variants(cx: ctxt, id: ast::def_id) -> @[variant_info] {
         // check the disr_expr if it exists), this code should likely be
         // moved there to avoid having to call eval_const_expr twice.
         alt cx.items.get(id.node) {
-          ast_map::node_item(@{node: ast::item_enum(variants, _), _}, _) {
+          ast_map::node_item(@{node: ast::item_enum(variants, _, _), _}, _) {
             let mut disr_val = -1;
             @vec::map(variants, {|variant|
                 let ctor_ty = node_id_to_type(cx, variant.node.id);
-                let arg_tys = if vec::len(variant.node.args) > 0u {
-                    vec::map(ty_fn_args(ctor_ty), {|a| a.ty})
-                } else { [] };
+                let arg_tys = {
+                    if vec::len(variant.node.args) > 0u {
+                        ty_fn_args(ctor_ty).map { |a| a.ty }
+                    } else { [] }
+                };
                 alt variant.node.disr_expr {
                   some (ex) {
                     // FIXME: issue #1417
@@ -2287,7 +2406,8 @@ fn lookup_item_type(cx: ctxt, did: ast::def_id) -> ty_param_bounds_and_ty {
 // Look up a field ID, whether or not it's local
 // Takes a list of type substs in case the class is generic
 fn lookup_field_type(tcx: ctxt, class_id: def_id, id: def_id,
-                     substs: [ty::t]) -> ty::t {
+                     substs: substs) -> ty::t {
+
     let t = if id.crate == ast::local_crate {
         node_id_to_type(tcx, id.node)
     }
@@ -2304,7 +2424,7 @@ fn lookup_field_type(tcx: ctxt, class_id: def_id, id: def_id,
            }
         }
     };
-    substitute_type_params(tcx, substs, t)
+    subst(tcx, substs, t)
 }
 
 // Look up the list of field names and IDs for a given class
@@ -2314,7 +2434,7 @@ fn lookup_class_fields(cx: ctxt, did: ast::def_id) -> [field_ty] {
     alt cx.items.find(did.node) {
        some(ast_map::node_item(i,_)) {
          alt i.node {
-           ast::item_class(_, _, items, _) {
+           ast::item_class(_, _, items, _, _) {
                class_field_tys(items)
            }
            _ { cx.sess.bug("class ID bound to non-class"); }
@@ -2356,7 +2476,7 @@ pure fn is_public(f: field_ty) -> bool {
 fn lookup_class_method_ids(cx: ctxt, did: ast::def_id)
     : is_local(did) -> [{name: ident, id: node_id, privacy: privacy}] {
     alt cx.items.find(did.node) {
-       some(ast_map::node_item(@{node: item_class(_,_,items,_), _}, _)) {
+       some(ast_map::node_item(@{node: item_class(_,_,items,_,_), _}, _)) {
          let (_,ms) = split_class_items(items);
          vec::map(ms, {|m| {name: m.ident, id: m.id,
                          privacy: m.privacy}})
@@ -2406,8 +2526,8 @@ fn class_field_tys(items: [@class_member]) -> [field_ty] {
 // Return a list of fields corresponding to the class's items
 // (as if the class was a record). trans uses this
 // Takes a list of substs with which to instantiate field types
-fn class_items_as_fields(cx:ctxt, did: ast::def_id, substs: [ty::t])
-    -> [field] {
+fn class_items_as_fields(cx:ctxt, did: ast::def_id,
+                         substs: substs) -> [field] {
     let mut rslt = [];
     for lookup_class_fields(cx, did).each {|f|
        // consider all instance vars mut, because the
diff --git a/src/rustc/middle/typeck.rs b/src/rustc/middle/typeck.rs
index b3e407b0c47..d13a23fccb9 100644
--- a/src/rustc/middle/typeck.rs
+++ b/src/rustc/middle/typeck.rs
@@ -1,4 +1,4 @@
-import result::result;
+import result::{result, extensions};
 import syntax::{ast, ast_util};
 import ast::spanned;
 import syntax::ast_util::{local_def, respan, split_class_items};
@@ -12,7 +12,7 @@ import middle::ty;
 import middle::ty::{arg, field, node_type_table, mk_nil,
                     ty_param_bounds_and_ty, lookup_public_fields};
 import middle::ty::{ty_vid, region_vid, vid};
-import util::ppaux::ty_to_str;
+import util::ppaux::{ty_to_str, region_to_str};
 import std::smallintmap;
 import std::smallintmap::map;
 import std::map;
@@ -69,7 +69,7 @@ type class_map = hashmap<ast::node_id, ty::t>;
 
 // a list of mapping from in-scope-region-names ("isr") to the
 // corresponding ty::region
-type isr_alist = @list<(str, ty::region)>;
+type isr_alist = @list<(ty::bound_region, ty::region)>;
 
 type fn_ctxt =
     // var_bindings, locals and next_var_id are shared
@@ -112,7 +112,7 @@ type fn_ctxt =
      // eventually be resolved to some concrete type (which might itself be
      // type parameter).
      node_types: smallintmap::smallintmap<ty::t>,
-     node_type_substs: hashmap<ast::node_id, [ty::t]>,
+     node_type_substs: hashmap<ast::node_id, ty::substs>,
 
      ccx: @crate_ctxt};
 
@@ -153,24 +153,29 @@ fn lookup_def(fcx: @fn_ctxt, sp: span, id: ast::node_id) -> ast::def {
     lookup_def_ccx(fcx.ccx, sp, id)
 }
 
+fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
+    {bounds: @[], rp: ast::rp_none, ty: t}
+}
+
 // Returns the type parameter count and the type for the given definition.
 fn ty_param_bounds_and_ty_for_def(fcx: @fn_ctxt, sp: span, defn: ast::def) ->
-   ty_param_bounds_and_ty {
+    ty_param_bounds_and_ty {
+
     alt defn {
       ast::def_arg(nid, _) {
         assert (fcx.locals.contains_key(nid));
         let typ = ty::mk_var(fcx.ccx.tcx, lookup_local(fcx, sp, nid));
-        ret {bounds: @[], ty: typ};
+        ret no_params(typ);
       }
       ast::def_local(nid, _) {
         assert (fcx.locals.contains_key(nid));
         let typ = ty::mk_var(fcx.ccx.tcx, lookup_local(fcx, sp, nid));
-        ret {bounds: @[], ty: typ};
+        ret no_params(typ);
       }
       ast::def_self(_) {
         alt fcx.self_ty {
           some(self_ty) {
-            ret {bounds: @[], ty: self_ty};
+            ret no_params(self_ty);
           }
           none {
               fcx.ccx.tcx.sess.span_bug(sp, "def_self with no self_ty");
@@ -181,6 +186,7 @@ fn ty_param_bounds_and_ty_for_def(fcx: @fn_ctxt, sp: span, defn: ast::def) ->
         // Crust functions are just u8 pointers
         ret {
             bounds: @[],
+            rp: ast::rp_none,
             ty: ty::mk_ptr(
                 fcx.ccx.tcx,
                 {
@@ -195,7 +201,7 @@ fn ty_param_bounds_and_ty_for_def(fcx: @fn_ctxt, sp: span, defn: ast::def) ->
       ast::def_binding(nid) {
         assert (fcx.locals.contains_key(nid));
         let typ = ty::mk_var(fcx.ccx.tcx, lookup_local(fcx, sp, nid));
-        ret {bounds: @[], ty: typ};
+        ret no_params(typ);
       }
       ast::def_ty(_) | ast::def_prim_ty(_) {
         fcx.ccx.tcx.sess.span_fatal(sp, "expected value but found type");
@@ -212,36 +218,41 @@ fn ty_param_bounds_and_ty_for_def(fcx: @fn_ctxt, sp: span, defn: ast::def) ->
 
 // Instantiates the given path, which must refer to an item with the given
 // number of type parameters and type.
-fn instantiate_path(fcx: @fn_ctxt, pth: @ast::path,
-                    tpt: ty_param_bounds_and_ty, sp: span,
+fn instantiate_path(fcx: @fn_ctxt,
+                    pth: @ast::path,
+                    tpt: ty_param_bounds_and_ty,
+                    sp: span,
                     id: ast::node_id) {
     let ty_param_count = vec::len(*tpt.bounds);
     let ty_substs_len = vec::len(pth.node.types);
-    if ty_substs_len > 0u {
-        if ty_param_count == 0u {
-            fcx.ccx.tcx.sess.span_fatal
-                (sp, "this item does not take type parameters");
-        } else if ty_substs_len > ty_param_count {
-            fcx.ccx.tcx.sess.span_fatal
-                (sp, "too many type parameters provided for this item");
-        } else if ty_substs_len < ty_param_count {
-            fcx.ccx.tcx.sess.span_fatal
-                (sp, "not enough type parameters provided for this item");
-        }
-        if ty_param_count == 0u {
-            fcx.ccx.tcx.sess.span_fatal(
-                sp, "this item does not take type parameters");
-        }
-        let substs = vec::map(pth.node.types, {|aty|
-            fcx.to_ty(aty)
-        });
-        fcx.write_ty_substs(id, tpt.ty, substs);
-    } else if ty_param_count > 0u {
-        let vars = fcx.next_ty_vars(ty_param_count);
-        fcx.write_ty_substs(id, tpt.ty, vars);
+
+    // For now, there is no way to explicitly specify the region bound.
+    // This will have to change eventually.
+    let self_r = alt tpt.rp {
+      ast::rp_self { some(fcx.next_region_var()) }
+      ast::rp_none { none }
+    };
+
+    let tps = if ty_substs_len == 0u {
+        fcx.next_ty_vars(ty_param_count)
+    } else if ty_param_count == 0u {
+        fcx.ccx.tcx.sess.span_err
+            (sp, "this item does not take type parameters");
+        fcx.next_ty_vars(ty_param_count)
+    } else if ty_substs_len > ty_param_count {
+        fcx.ccx.tcx.sess.span_err
+            (sp, "too many type parameters provided for this item");
+        fcx.next_ty_vars(ty_param_count)
+    } else if ty_substs_len < ty_param_count {
+        fcx.ccx.tcx.sess.span_err
+            (sp, "not enough type parameters provided for this item");
+        fcx.next_ty_vars(ty_param_count)
     } else {
-        fcx.write_ty(id, tpt.ty);
-    }
+        pth.node.types.map { |aty| fcx.to_ty(aty) }
+    };
+
+    let substs = {self_r: self_r, tps: tps};
+    fcx.write_ty_substs(id, tpt.ty, substs);
 }
 
 // Type tests
@@ -358,20 +369,54 @@ impl of ast_conv for @fn_ctxt {
 }
 
 iface region_scope {
-    fn anon_region() -> ty::region;
-    fn named_region(id: str) -> option<ty::region>;
+    fn anon_region() -> result<ty::region, str>;
+    fn named_region(id: str) -> result<ty::region, str>;
 }
 
-enum base_rscope { base_rscope }
-impl of region_scope for base_rscope {
-    fn anon_region() -> ty::region { ty::re_bound(ty::br_anon) }
-    fn named_region(_id: str) -> option<ty::region> { none }
+enum empty_rscope { empty_rscope }
+impl of region_scope for empty_rscope {
+    fn anon_region() -> result<ty::region, str> {
+        result::err("region types are not allowed here")
+    }
+    fn named_region(_id: str) -> result<ty::region, str> {
+        result::err("region types are not allowed here")
+    }
+}
+
+enum type_rscope = ast::region_param;
+impl of region_scope for type_rscope {
+    fn anon_region() -> result<ty::region, str> {
+        alt *self {
+          ast::rp_self {
+            result::ok(ty::re_bound(ty::br_self))
+          }
+          ast::rp_none {
+            result::err("to use region types here, the containing type \
+                         must be declared with a region bound")
+          }
+        }
+    }
+    fn named_region(id: str) -> result<ty::region, str> {
+        if id == "self" {
+            self.anon_region()
+        } else {
+            result::err("named regions other than `self` are not \
+                         allowed as part of a type declaration")
+        }
+    }
 }
 
 impl of region_scope for @fn_ctxt {
-    fn anon_region() -> ty::region { self.next_region_var() }
-    fn named_region(id: str) -> option<ty::region> {
-        self.in_scope_regions.find(id)
+    fn anon_region() -> result<ty::region, str> {
+        result::ok(self.next_region_var())
+    }
+    fn named_region(id: str) -> result<ty::region, str> {
+        alt self.in_scope_regions.find(ty::br_named(id)) {
+          some(r) { result::ok(r) }
+          none {
+            result::err(#fmt["named region `%s` not in scope here", id])
+          }
+        }
     }
 }
 
@@ -381,17 +426,11 @@ fn in_anon_rscope<RS: region_scope copy>(self: RS, r: ty::region)
     @anon_rscope({anon: r, base: self as region_scope})
 }
 impl of region_scope for @anon_rscope {
-    fn anon_region() -> ty::region { self.anon }
-    fn named_region(id: str) -> option<ty::region> {
-        self.base.named_region(id)
+    fn anon_region() -> result<ty::region, str> {
+        result::ok(self.anon)
     }
-}
-
-enum self_rscope { self_rscope }
-impl of region_scope for self_rscope {
-    fn anon_region() -> ty::region { ty::re_bound(ty::br_self) }
-    fn named_region(id: str) -> option<ty::region> {
-        if id == "self" {some(self.anon_region())} else {none}
+    fn named_region(id: str) -> result<ty::region, str> {
+        self.base.named_region(id)
     }
 }
 
@@ -401,40 +440,41 @@ fn in_binding_rscope<RS: region_scope copy>(self: RS) -> @binding_rscope {
     @binding_rscope({base: base})
 }
 impl of region_scope for @binding_rscope {
-    fn anon_region() -> ty::region { ty::re_bound(ty::br_anon) }
-    fn named_region(id: str) -> option<ty::region> {
-        let nr = self.base.named_region(id);
-        alt nr {
-          some(r) { some(r) }
-          none { some(ty::re_bound(ty::br_named(id))) }
+    fn anon_region() -> result<ty::region, str> {
+        result::ok(ty::re_bound(ty::br_anon))
+    }
+    fn named_region(id: str) -> result<ty::region, str> {
+        self.base.named_region(id).chain_err {|_e|
+            result::ok(ty::re_bound(ty::br_named(id)))
         }
     }
 }
 
-fn ast_region_to_region<AC: ast_conv, RS: region_scope copy>(
-    self: AC, rscope: RS, span: span, a_r: ast::region) -> ty::region {
+fn get_region_reporting_err(tcx: ty::ctxt,
+                            span: span,
+                            res: result<ty::region, str>) -> ty::region {
 
-    alt a_r.node {
-      ast::re_anon {
-        rscope.anon_region()
-      }
-      ast::re_named(id) {
-        alt rscope.named_region(id) {
-          some(r) { r }
-          none {
-            self.tcx().sess.span_err(
-                span,
-                #fmt["named region `%s` not in scope here", id]);
-            rscope.anon_region()
-          }
-        }
-      }
-      ast::re_static {
+    alt res {
+      result::ok(r) { r }
+      result::err(e) {
+        tcx.sess.span_err(span, e);
         ty::re_static
       }
     }
 }
 
+fn ast_region_to_region<AC: ast_conv, RS: region_scope>(
+    self: AC, rscope: RS, span: span, a_r: ast::region) -> ty::region {
+
+    let res = alt a_r.node {
+      ast::re_anon { rscope.anon_region() }
+      ast::re_named(id) { rscope.named_region(id) }
+      ast::re_static { result::ok(ty::re_static) }
+    };
+
+    get_region_reporting_err(self.tcx(), span, res)
+}
+
 // Parses the programmer's textual representation of a type into our
 // internal notion of a type. `getter` is a function that returns the type
 // corresponding to a definition ID:
@@ -452,30 +492,34 @@ fn ast_ty_to_ty<AC: ast_conv, RS: region_scope copy>(
         path_id: ast::node_id, args: [@ast::ty]) -> ty::t {
 
         let tcx = self.tcx();
-        let {bounds, ty} = self.get_item_ty(id);
-
-        // The type of items may include a reference to the bound anon region.
-        // Replace it with the current binding for that region in this
-        // context.
-        //
-        // n.b. Ordinarily, one should do all substitutions at once to avoid
-        // capture problems.  But in this instance it is ok to substitute for
-        // the bound region first and then type parameters second, as the
-        // bound region cannot be replaced with a type parameter.
-        let ty = subst_anon_region(tcx, rscope.anon_region(), ty);
-
-        // The typedef is type-parametric. Do the type substitution.
+        let {bounds, rp, ty} = self.get_item_ty(id);
+
+        // If the type is parameterized by the self region, then replace self
+        // region with the current anon region binding (in other words,
+        // whatever & would get replaced with).
+        let self_r = alt rp {
+          ast::rp_none { none }
+          ast::rp_self {
+            let res = rscope.anon_region();
+            let r = get_region_reporting_err(self.tcx(), sp, res);
+            some(r)
+          }
+        };
+
+        // Convert the type parameters supplied by the user.
         if vec::len(args) != vec::len(*bounds) {
             tcx.sess.span_fatal(
-                sp, "wrong number of type arguments for a \
-                     polymorphic type");
+                sp, #fmt["wrong number of type arguments, \
+                          expected %u but found %u",
+                         vec::len(*bounds),
+                         vec::len(args)]);
         }
-        let param_bindings = args.map { |t| ast_ty_to_ty(self, rscope, t) };
-        #debug("substituting(%? into %?)",
-               vec::map(param_bindings) {|t| ty_to_str(tcx, t)},
-               ty_to_str(tcx, ty));
-        let ty = ty::substitute_type_params(tcx, param_bindings, ty);
-        write_substs_to_tcx(tcx, path_id, param_bindings);
+        let tps = args.map { |t| ast_ty_to_ty(self, rscope, t) };
+
+        // Perform the substitution and store the tps for future ref.
+        let substs = {self_r: self_r, tps: tps};
+        let ty = ty::subst(tcx, substs, ty);
+        write_substs_to_tcx(tcx, path_id, substs.tps);
         ret ty;
     }
 
@@ -636,24 +680,29 @@ fn ty_of_item(ccx: @crate_ctxt, it: @ast::item)
     }
     alt it.node {
       ast::item_const(t, _) {
-        let typ = ccx.to_ty(t);
-        let tpt = {bounds: @[], ty: typ};
+        let typ = ccx.to_ty(empty_rscope, t);
+        let tpt = no_params(typ);
         tcx.tcache.insert(local_def(it.id), tpt);
         ret tpt;
       }
       ast::item_fn(decl, tps, _) {
-        ret ty_of_fn(ccx, decl, tps, local_def(it.id));
+        let bounds = ty_param_bounds(ccx, tps);
+        let tofd = ty_of_fn_decl(ccx, empty_rscope, ast::proto_bare, decl);
+        let tpt = {bounds: bounds,
+                   rp: ast::rp_none, // functions do not have a self
+                   ty: ty::mk_fn(ccx.tcx, tofd)};
+        ccx.tcx.tcache.insert(local_def(it.id), tpt);
+        ret tpt;
       }
-      ast::item_ty(t, tps) {
+      ast::item_ty(t, tps, rp) {
         alt tcx.tcache.find(local_def(it.id)) {
           some(tpt) { ret tpt; }
           none { }
         }
-        // Tell ast_ty_to_ty() that we want to perform a recursive
-        // call to resolve any named types.
+
         let tpt = {
             let ty = {
-                let t0 = ccx.to_ty(t);
+                let t0 = ccx.to_ty(type_rscope(rp), t);
                 // Do not associate a def id with a named, parameterized type
                 // like "foo<X>".  This is because otherwise ty_to_str will
                 // print the name as merely "foo", as it has no way to
@@ -662,38 +711,39 @@ fn ty_of_item(ccx: @crate_ctxt, it: @ast::item)
                     ty::mk_with_id(tcx, t0, def_id)
                 }
             };
-            {bounds: ty_param_bounds(ccx, tps), ty: ty}
+            {bounds: ty_param_bounds(ccx, tps), rp: rp, ty: ty}
         };
         tcx.tcache.insert(local_def(it.id), tpt);
         ret tpt;
       }
-      ast::item_res(decl, tps, _, _, _) {
-        let {bounds, params} = mk_ty_params(ccx, tps);
-        let t_arg = ty_of_arg(ccx, base_rscope, decl.inputs[0]);
-        let t = ty::mk_res(tcx, local_def(it.id), t_arg.ty, params);
-        let t_res = {bounds: bounds, ty: t};
+      ast::item_res(decl, tps, _, _, _, rp) {
+        let {bounds, substs} = mk_substs(ccx, tps, rp);
+        let t_arg = ty_of_arg(ccx, empty_rscope, decl.inputs[0]);
+        let t = ty::mk_res(tcx, local_def(it.id), t_arg.ty, substs);
+        let t_res = {bounds: bounds, rp: rp, ty: t};
         tcx.tcache.insert(local_def(it.id), t_res);
         ret t_res;
       }
-      ast::item_enum(_, tps) {
+      ast::item_enum(_, tps, rp) {
         // Create a new generic polytype.
-        let {bounds, params} = mk_ty_params(ccx, tps);
-        let t = ty::mk_enum(tcx, local_def(it.id), params);
-        let tpt = {bounds: bounds, ty: t};
+        let {bounds, substs} = mk_substs(ccx, tps, rp);
+        let t = ty::mk_enum(tcx, local_def(it.id), substs);
+        let tpt = {bounds: bounds, rp: rp, ty: t};
         tcx.tcache.insert(local_def(it.id), tpt);
         ret tpt;
       }
       ast::item_iface(tps, ms) {
         let {bounds, params} = mk_ty_params(ccx, tps);
         let t = ty::mk_iface(tcx, local_def(it.id), params);
-        let tpt = {bounds: bounds, ty: t};
+        // NDM iface/impl regions
+        let tpt = {bounds: bounds, rp: ast::rp_none, ty: t};
         tcx.tcache.insert(local_def(it.id), tpt);
         ret tpt;
       }
-      ast::item_class(tps,_,_,_) {
-          let {bounds,params} = mk_ty_params(ccx, tps);
-          let t = ty::mk_class(tcx, local_def(it.id), params);
-          let tpt = {bounds: bounds, ty: t};
+      ast::item_class(tps, _, _, _, rp) {
+          let {bounds,substs} = mk_substs(ccx, tps, rp);
+          let t = ty::mk_class(tcx, local_def(it.id), substs);
+          let tpt = {bounds: bounds, rp: rp, ty: t};
           tcx.tcache.insert(local_def(it.id), tpt);
           ret tpt;
       }
@@ -713,36 +763,35 @@ fn ty_of_native_item(ccx: @crate_ctxt, it: @ast::native_item)
 
 type next_region_param_id = { mut id: uint };
 
-fn collect_named_regions_in_tys(
+fn collect_bound_regions_in_tys(
     tcx: ty::ctxt,
     isr: isr_alist,
     tys: [ty::t],
-    to_r: fn(str) -> ty::region) -> isr_alist {
+    to_r: fn(ty::bound_region) -> ty::region) -> isr_alist {
 
     tys.foldl(isr) { |isr, t|
-        collect_named_regions_in_ty(tcx, isr, t, to_r)
+        collect_bound_regions_in_ty(tcx, isr, t, to_r)
     }
 }
 
-fn collect_named_regions_in_ty(
-    _tcx: ty::ctxt,
+fn collect_bound_regions_in_ty(
+    tcx: ty::ctxt,
     isr: isr_alist,
     ty: ty::t,
-    to_r: fn(str) -> ty::region) -> isr_alist {
+    to_r: fn(ty::bound_region) -> ty::region) -> isr_alist {
 
     fn append_isr(isr: isr_alist,
-                  to_r: fn(str) -> ty::region,
+                  to_r: fn(ty::bound_region) -> ty::region,
                   r: ty::region) -> isr_alist {
         alt r {
           ty::re_free(_, _) | ty::re_static | ty::re_scope(_) |
-          ty::re_var(_) | ty::re_bound(ty::br_anon) |
-          ty::re_bound(ty::br_self) {
+          ty::re_var(_) {
             isr
           }
-          ty::re_bound(br @ ty::br_named(id)) {
-            alt isr.find(id) {
+          ty::re_bound(br) {
+            alt isr.find(br) {
               some(_) { isr }
-              none { @cons((id, to_r(id)), isr) }
+              none { @cons((br, to_r(br)), isr) }
             }
           }
         }
@@ -750,20 +799,14 @@ fn collect_named_regions_in_ty(
 
     let mut isr = isr;
 
-    ty::maybe_walk_ty(ty) {|t|
-        alt ty::get(t).struct {
-          // do not walk fn contents
-          ty::ty_fn(_) { false }
-
-          // collect named regions into the isr list
-          ty::ty_evec(_, ty::vstore_slice(r)) |
-          ty::ty_estr(ty::vstore_slice(r)) |
-          ty::ty_rptr(r, _) { isr = append_isr(isr, to_r, r); true }
-
-          // otherwise just walk the types
-          _ { true }
-        }
-    }
+    // Using fold_regions is inefficient, because it constructs new types, but
+    // it avoids code duplication in terms of locating all the regions within
+    // the various kinds of types.  This had already caused me several bugs
+    // so I decided to switch over.
+    ty::fold_regions(tcx, ty) { |r, in_fn|
+        if !in_fn { isr = append_isr(isr, to_r, r); }
+        r
+    };
 
     ret isr;
 }
@@ -781,36 +824,34 @@ fn replace_bound_self(
 fn replace_bound_regions(
     tcx: ty::ctxt,
     span: span,
-    anon_r: ty::region,
     isr: isr_alist,
     ty: ty::t) -> ty::t {
 
     ty::fold_regions(tcx, ty) { |r, in_fn|
         alt r {
-          ty::re_bound(ty::br_named(id)) {
-            alt isr.find(id) {
+          // As long as we are not within a fn() type, `&T` is mapped to the
+          // free region anon_r.  But within a fn type, it remains bound.
+          ty::re_bound(ty::br_anon) if in_fn { r }
+
+          ty::re_bound(br) {
+            alt isr.find(br) {
               // In most cases, all named, bound regions will be mapped to
               // some free region.
               some(fr) { fr }
 
               // But in the case of a fn() type, there may be named regions
               // within that remain bound:
-              none { assert in_fn; r }
+              none if in_fn { r }
+              none {
+                tcx.sess.span_bug(
+                    span,
+                    #fmt["Bound region not found in \
+                          in_scope_regions list: %s",
+                         region_to_str(tcx, r)]);
+              }
             }
           }
 
-          // As long as we are not within a fn() type, `&T` is mapped to the
-          // free region anon_r.  But within a fn type, it remains bound.
-          ty::re_bound(ty::br_anon) if !in_fn { anon_r }
-          ty::re_bound(ty::br_anon) { r }
-
-          // The &self region is special.  Any bound references to self should
-          // have already been replaced using replace_bound_self() when
-          // this function is called.
-          ty::re_bound(ty::br_self) {
-            tcx.sess.span_bug(span, "Bound self region found");
-          }
-
           // Free regions like these just stay the same:
           ty::re_static |
           ty::re_scope(_) |
@@ -870,25 +911,13 @@ fn ty_of_fn_decl<AC: ast_conv, RS: region_scope copy>(
     }
 }
 
-fn ty_of_fn(ccx: @crate_ctxt,
-            decl: ast::fn_decl,
-            ty_params: [ast::ty_param],
-            def_id: ast::def_id) -> ty::ty_param_bounds_and_ty {
-
-    let bounds = ty_param_bounds(ccx, ty_params);
-    let tofd = ty_of_fn_decl(ccx, base_rscope, ast::proto_bare, decl);
-    let tpt = {bounds: bounds, ty: ty::mk_fn(ccx.tcx, tofd)};
-    ccx.tcx.tcache.insert(def_id, tpt);
-    ret tpt;
-}
-
 fn ty_of_native_fn_decl(ccx: @crate_ctxt,
                         decl: ast::fn_decl,
                         ty_params: [ast::ty_param],
                         def_id: ast::def_id) -> ty::ty_param_bounds_and_ty {
 
     let bounds = ty_param_bounds(ccx, ty_params);
-    let rb = in_binding_rscope(base_rscope);
+    let rb = in_binding_rscope(empty_rscope);
     let input_tys = vec::map(decl.inputs) { |a| ty_of_arg(ccx, rb, a) };
     let output_ty = ast_ty_to_ty(ccx, rb, decl.output);
 
@@ -897,7 +926,7 @@ fn ty_of_native_fn_decl(ccx: @crate_ctxt,
                                    output: output_ty,
                                    ret_style: ast::return_val,
                                    constraints: []});
-    let tpt = {bounds: bounds, ty: t_fn};
+    let tpt = {bounds: bounds, rp: ast::rp_none, ty: t_fn};
     ccx.tcx.tcache.insert(def_id, tpt);
     ret tpt;
 }
@@ -909,21 +938,23 @@ fn ty_param_bounds(ccx: @crate_ctxt,
         alt ccx.tcx.ty_param_bounds.find(param.id) {
           some(bs) { bs }
           none {
-            let bounds = @vec::map(*param.bounds) { |b|
+            let bounds = @vec::flat_map(*param.bounds) { |b|
                 alt b {
-                  ast::bound_send { ty::bound_send }
-                  ast::bound_copy { ty::bound_copy }
+                  ast::bound_send { [ty::bound_send] }
+                  ast::bound_copy { [ty::bound_copy] }
                   ast::bound_iface(t) {
-                    let ity = ccx.to_ty(t);
+                    let ity = ccx.to_ty(empty_rscope, t);
                     alt ty::get(ity).struct {
-                      ty::ty_iface(_, _) {}
+                      ty::ty_iface(_, _) {
+                        [ty::bound_iface(ity)]
+                      }
                       _ {
-                        ccx.tcx.sess.span_fatal(
+                        ccx.tcx.sess.span_err(
                             t.span, "type parameter bounds must be \
                                      interface types");
+                        []
                       }
                     }
-                    ty::bound_iface(ity)
                   }
                 }
             };
@@ -934,66 +965,50 @@ fn ty_param_bounds(ccx: @crate_ctxt,
     }
 }
 
-fn ty_of_method(ccx: @crate_ctxt, m: @ast::method) -> ty::method {
+fn ty_of_method(ccx: @crate_ctxt,
+                m: @ast::method,
+                rp: ast::region_param) -> ty::method {
     {ident: m.ident, tps: ty_param_bounds(ccx, m.tps),
-     fty: ty_of_fn_decl(ccx, base_rscope, ast::proto_bare, m.decl),
+     fty: ty_of_fn_decl(ccx, type_rscope(rp), ast::proto_bare, m.decl),
      purity: m.decl.purity, privacy: m.privacy}
 }
 
 fn ty_of_ty_method(self: @crate_ctxt, m: ast::ty_method) -> ty::method {
     {ident: m.ident,
      tps: ty_param_bounds(self, m.tps),
-     fty: ty_of_fn_decl(self, base_rscope, ast::proto_bare, m.decl),
+     fty: ty_of_fn_decl(self, empty_rscope, ast::proto_bare, m.decl),
      // assume public, because this is only invoked on iface methods
      purity: m.decl.purity, privacy: ast::pub}
 }
 
-// A wrapper around ast_ty_to_ty_crate that handles ty_infer.
-fn ast_ty_to_ty_infer(fcx: @fn_ctxt, &&ast_ty: @ast::ty) -> option<ty::t> {
-    alt ast_ty.node {
-      ast::ty_infer { none }
-      _ { some(fcx.to_ty(ast_ty)) }
-    }
-}
-
-
 // Functions that write types into the node type table
 fn write_ty_to_tcx(tcx: ty::ctxt, node_id: ast::node_id, ty: ty::t) {
     #debug["write_ty_to_tcx(%d, %s)", node_id, ty_to_str(tcx, ty)];
     smallintmap::insert(*tcx.node_types, node_id as uint, ty);
 }
-fn write_substs_to_tcx(tcx: ty::ctxt, node_id: ast::node_id,
+fn write_substs_to_tcx(tcx: ty::ctxt,
+                       node_id: ast::node_id,
                        +substs: [ty::t]) {
     if substs.len() > 0u {
         tcx.node_type_substs.insert(node_id, substs);
     }
 }
-fn write_ty_substs_to_tcx(tcx: ty::ctxt, node_id: ast::node_id, ty: ty::t,
-                   +substs: [ty::t]) {
-    if substs.len() == 0u {
-        write_ty_to_tcx(tcx, node_id, ty);
-    } else {
-        let ty = ty::substitute_type_params(tcx, substs, ty);
-        write_ty_to_tcx(tcx, node_id, ty);
-        write_substs_to_tcx(tcx, node_id, substs);
-    }
-}
 
 impl methods for @crate_ctxt {
-    fn to_ty(ast_ty: @ast::ty) -> ty::t {
-        ast_ty_to_ty(self, base_rscope, ast_ty)
-    }
-
-    fn to_self_ty(ast_ty: @ast::ty) -> ty::t {
-        ast_ty_to_ty(self, self_rscope, ast_ty)
+    fn to_ty<RS: region_scope copy>(rs: RS, ast_ty: @ast::ty) -> ty::t {
+        ast_ty_to_ty(self, rs, ast_ty)
     }
 }
 
 impl methods for isr_alist {
-    fn find(id: str) -> option<ty::region> {
+    fn get(br: ty::bound_region) -> ty::region {
+        option::get(self.find(br))
+    }
+
+    fn find(br: ty::bound_region) -> option<ty::region> {
         for list::each(*self) { |isr|
-            let (isr_id, isr_r) = isr;
-            if isr_id == id { ret some(isr_r); }
+            let (isr_br, isr_r) = isr;
+            if isr_br == br { ret some(isr_r); }
         }
         ret none;
     }
@@ -1009,18 +1024,17 @@ impl methods for @fn_ctxt {
                node_id, ty_to_str(self.tcx(), ty), self.tag()];
         self.node_types.insert(node_id as uint, ty);
     }
-    fn write_substs(node_id: ast::node_id, +substs: [ty::t]) {
-        self.node_type_substs.insert(node_id, substs);
-    }
-    fn write_ty_substs(node_id: ast::node_id, ty: ty::t, +substs: [ty::t]) {
-        if substs.len() == 0u {
-            self.write_ty(node_id, ty)
-        } else {
-            let ty = ty::substitute_type_params(self.tcx(), substs, ty);
-            self.write_ty(node_id, ty);
-            self.write_substs(node_id, substs);
+    fn write_substs(node_id: ast::node_id, +substs: ty::substs) {
+        if !ty::substs_is_noop(substs) {
+            self.node_type_substs.insert(node_id, substs);
         }
     }
+    fn write_ty_substs(node_id: ast::node_id, ty: ty::t,
+                       +substs: ty::substs) {
+        let ty = ty::subst(self.tcx(), substs, ty);
+        self.write_ty(node_id, ty);
+        self.write_substs(node_id, substs);
+    }
     fn write_nil(node_id: ast::node_id) {
         self.write_ty(node_id, ty::mk_nil(self.tcx()));
     }
@@ -1052,7 +1066,7 @@ impl methods for @fn_ctxt {
           }
         }
     }
-    fn node_ty_substs(id: ast::node_id) -> [ty::t] {
+    fn node_ty_substs(id: ast::node_id) -> ty::substs {
         alt self.node_type_substs.find(id) {
           some(ts) { ts }
           none {
@@ -1063,7 +1077,7 @@ impl methods for @fn_ctxt {
           }
         }
     }
-    fn opt_node_ty_substs(id: ast::node_id) -> option<[ty::t]> {
+    fn opt_node_ty_substs(id: ast::node_id) -> option<ty::substs> {
         self.node_type_substs.find(id)
     }
     fn next_ty_var_id() -> ty_vid {
@@ -1109,6 +1123,17 @@ fn mk_ty_params(ccx: @crate_ctxt, atps: [ast::ty_param])
      })}
 }
 
+fn mk_substs(ccx: @crate_ctxt, atps: [ast::ty_param], rp: ast::region_param)
+    -> {bounds: @[ty::param_bounds], substs: ty::substs} {
+
+    let {bounds, params} = mk_ty_params(ccx, atps);
+    let self_r = alt rp {
+      ast::rp_self { some(ty::re_bound(ty::br_self)) }
+      ast::rp_none { none }
+    };
+    {bounds: bounds, substs: {self_r: self_r, tps: params}}
+}
+
 fn compare_impl_method(tcx: ty::ctxt, sp: span, impl_m: ty::method,
                        impl_tps: uint, if_m: ty::method, substs: [ty::t],
                        self_ty: ty::t) -> ty::t {
@@ -1134,12 +1159,13 @@ fn compare_impl_method(tcx: ty::ctxt, sp: span, impl_m: ty::method,
             }
         });
         let impl_fty = ty::mk_fn(tcx, {inputs: auto_modes with impl_m.fty});
+
         // Add dummy substs for the parameters of the impl method
         let substs = substs + vec::from_fn(vec::len(*if_m.tps), {|i|
             ty::mk_param(tcx, i + impl_tps, {crate: 0, node: 0})
         });
         let mut if_fty = ty::mk_fn(tcx, if_m.fty);
-        if_fty = ty::substitute_type_params(tcx, substs, if_fty);
+        if_fty = ty::subst_tps(tcx, substs, if_fty);
         if_fty = fixup_self_full(tcx, if_fty, substs, self_ty, impl_tps);
         require_same_types(
             tcx, sp, impl_fty, if_fty,
@@ -1167,7 +1193,7 @@ fn fixup_self_full(cx: ty::ctxt, mty: ty::t, m_substs: [ty::t],
             // context.
             let mut substs = vec::map(tps) {|t|
                 let f = fixup_self_full(cx, t, m_substs, selfty, impl_n_tps);
-                ty::substitute_type_params(cx, m_substs, f)
+                ty::subst_tps(cx, m_substs, f)
             };
 
             // Add extra substs for impl type parameters.
@@ -1185,7 +1211,7 @@ fn fixup_self_full(cx: ty::ctxt, mty: ty::t, m_substs: [ty::t],
             }
 
             // And then instantiate the self type using all those.
-            ty::substitute_type_params(cx, substs, selfty)
+            ty::subst_tps(cx, substs, selfty)
           }
           _ {
               t
@@ -1212,7 +1238,7 @@ fn fixup_self_param(fcx: @fn_ctxt, mty: ty::t, m_substs: [ty::t],
             // context.
             let mut substs = vec::map(tps) {|t|
                 let f = fixup_self_param(fcx, t, m_substs, selfty, sp);
-                ty::substitute_type_params(tcx, m_substs, f)
+                ty::subst_tps(tcx, m_substs, f)
             };
 
             // Simply ensure that the type parameters for the self
@@ -1251,7 +1277,6 @@ fn instantiate_bound_regions(tcx: ty::ctxt, region: ty::region, &&ty: ty::t)
     }
 }
 
-
 // Item collection - a pair of bootstrap passes:
 //
 // (1) Collect the IDs of all type items (typedefs) and store them in a table.
@@ -1263,9 +1288,11 @@ fn instantiate_bound_regions(tcx: ty::ctxt, region: ty::region, &&ty: ty::t)
 // We then annotate the AST with the resulting types and return the annotated
 // AST, along with a table mapping item IDs to their types.
 mod collect {
-    fn get_enum_variant_types(ccx: @crate_ctxt, enum_ty: ty::t,
+    fn get_enum_variant_types(ccx: @crate_ctxt,
+                              enum_ty: ty::t,
                               variants: [ast::variant],
-                              ty_params: [ast::ty_param]) {
+                              ty_params: [ast::ty_param],
+                              rp: ast::region_param) {
         let tcx = ccx.tcx;
 
         // Create a set of parameter types shared among all the variants.
@@ -1277,17 +1304,19 @@ mod collect {
             } else {
                 // As above, tell ast_ty_to_ty() that trans_ty_item_to_ty()
                 // should be called to resolve named types.
+                let rs = type_rscope(rp);
                 let args = variant.node.args.map { |va|
-                    {mode: ast::expl(ast::by_copy),
-                     ty: ccx.to_ty(va.ty)}
+                    let arg_ty = ccx.to_ty(rs, va.ty);
+                    {mode: ast::expl(ast::by_copy), ty: arg_ty}
                 };
-                // FIXME: this will be different for constrained types
-                ty::mk_fn(tcx,
-                          {proto: ast::proto_box,
-                           inputs: args, output: enum_ty,
-                           ret_style: ast::return_val, constraints: []})
+                ty::mk_fn(tcx, {proto: ast::proto_box,
+                                inputs: args,
+                                output: enum_ty,
+                                ret_style: ast::return_val,
+                                constraints: []})
             };
             let tpt = {bounds: ty_param_bounds(ccx, ty_params),
+                       rp: ast::rp_none,
                        ty: result_ty};
             tcx.tcache.insert(local_def(variant.node.id), tpt);
             write_ty_to_tcx(tcx, variant.node.id, result_ty);
@@ -1307,25 +1336,28 @@ mod collect {
                   ty_of_ty_method(ccx, m)
               };
           }
-          ast_map::node_item(@{node: ast::item_class(_,_,its,_), _}, _) {
+          ast_map::node_item(@{node: ast::item_class(_,_,its,_,rp), _}, _) {
               let (_,ms) = split_class_items(its);
               // All methods need to be stored, since lookup_method
               // relies on the same method cache for self-calls
               store_methods::<@ast::method>(ccx, id, ms) {|m|
-                  ty_of_method(ccx, m)
+                  ty_of_method(ccx, m, rp)
               };
           }
         }
     }
 
-    fn check_methods_against_iface(ccx: @crate_ctxt, tps: [ast::ty_param],
-                                   selfty: ty::t, t: @ast::ty,
+    fn check_methods_against_iface(ccx: @crate_ctxt,
+                                   tps: [ast::ty_param],
+                                   rp: ast::region_param,
+                                   selfty: ty::t,
+                                   t: @ast::ty,
                                    ms: [@ast::method]) {
 
         let tcx = ccx.tcx;
         let i_bounds = ty_param_bounds(ccx, tps);
-        let my_methods = convert_methods(ccx, ms, i_bounds, some(selfty));
-        let iface_ty = ccx.to_ty(t);
+        let my_methods = convert_methods(ccx, ms, rp, i_bounds, selfty);
+        let iface_ty = ccx.to_ty(empty_rscope, t);
         alt ty::get(iface_ty).struct {
           ty::ty_iface(did, tys) {
             // Store the iface type in the type node
@@ -1352,9 +1384,11 @@ mod collect {
                         if_m, tys, selfty);
                     let old = tcx.tcache.get(local_def(id));
                     if old.ty != mt {
-                        tcx.tcache.insert(local_def(id),
-                                          {bounds: old.bounds,
-                                           ty: mt});
+                        tcx.tcache.insert(
+                            local_def(id),
+                            {bounds: old.bounds,
+                             rp: old.rp,
+                             ty: mt});
                         write_ty_to_tcx(tcx, id, mt);
                     }
                   }
@@ -1372,37 +1406,32 @@ mod collect {
       }
     }
 
-    fn convert_class_item(ccx: @crate_ctxt, v: ast_util::ivar) {
-        /* we want to do something here, b/c within the
-         scope of the class, it's ok to refer to fields &
-        methods unqualified */
-
+    fn convert_class_item(ccx: @crate_ctxt,
+                          rp: ast::region_param,
+                          v: ast_util::ivar) {
         /* they have these types *within the scope* of the
          class. outside the class, it's done with expr_field */
-        let tt = ccx.to_self_ty(v.ty);
+        let tt = ccx.to_ty(type_rscope(rp), v.ty);
         #debug("convert_class_item: %s %?", v.ident, v.id);
         write_ty_to_tcx(ccx.tcx, v.id, tt);
     }
 
-    fn convert_methods(ccx: @crate_ctxt, ms: [@ast::method],
+    fn convert_methods(ccx: @crate_ctxt,
+                       ms: [@ast::method],
+                       rp: ast::region_param,
                        i_bounds: @[ty::param_bounds],
-                       maybe_self: option<ty::t>)
+                       self_ty: ty::t)
         -> [{mty: ty::method, id: ast::node_id, span: span}] {
 
         let tcx = ccx.tcx;
         vec::map(ms) { |m|
-            alt maybe_self {
-              some(selfty) {
-                write_ty_to_tcx(tcx, m.self_id, selfty);
-              }
-             _ {}
-           }
+            write_ty_to_tcx(tcx, m.self_id, self_ty);
             let bounds = ty_param_bounds(ccx, m.tps);
-            let mty = ty_of_method(ccx, m);
+            let mty = ty_of_method(ccx, m, rp);
             let fty = ty::mk_fn(tcx, mty.fty);
-            tcx.tcache.insert(local_def(m.id),
-                              {bounds: @(*i_bounds + *bounds),
-                               ty: fty});
+            tcx.tcache.insert(
+                local_def(m.id),
+                {bounds: @(*i_bounds + *bounds), rp: rp, ty: fty});
             write_ty_to_tcx(tcx, m.id, fty);
             {mty: mty, id: m.id, span: m.span}
         }
@@ -1419,36 +1448,45 @@ mod collect {
                 for m.items.each { |item| check_intrinsic_type(ccx, item); }
             }
           }
-          ast::item_enum(variants, ty_params) {
+          ast::item_enum(variants, ty_params, rp) {
             let tpt = ty_of_item(ccx, it);
             write_ty_to_tcx(tcx, it.id, tpt.ty);
-            get_enum_variant_types(ccx, tpt.ty, variants, ty_params);
+            get_enum_variant_types(ccx, tpt.ty, variants,
+                                   ty_params, rp);
           }
           ast::item_impl(tps, ifce, selfty, ms) {
             let i_bounds = ty_param_bounds(ccx, tps);
-            let selfty = ccx.to_self_ty(selfty);
+            // NDM iface/impl regions
+            let selfty = ccx.to_ty(empty_rscope, selfty);
             write_ty_to_tcx(tcx, it.id, selfty);
             tcx.tcache.insert(local_def(it.id),
-                              {bounds: i_bounds, ty: selfty});
+                              {bounds: i_bounds,
+                               rp: ast::rp_none, // NDM iface/impl regions
+                               ty: selfty});
             alt ifce {
               some(t) {
-                check_methods_against_iface(ccx, tps, selfty, t, ms);
+                check_methods_against_iface(
+                    ccx, tps, ast::rp_none, // NDM iface/impl regions
+                    selfty, t, ms);
               }
               _ {
                 // Still have to do this to write method types
                 // into the table
-                convert_methods(ccx, ms, i_bounds, some(selfty));
+                convert_methods(
+                    ccx, ms, ast::rp_none, // NDM iface/impl regions
+                    i_bounds, selfty);
               }
             }
           }
-          ast::item_res(decl, tps, _, dtor_id, ctor_id) {
-            let {bounds, params} = mk_ty_params(ccx, tps);
+          ast::item_res(decl, tps, _, dtor_id, ctor_id, rp) {
+            let {bounds, substs} = mk_substs(ccx, tps, rp);
             let def_id = local_def(it.id);
-            let t_arg = ty_of_arg(ccx, base_rscope, decl.inputs[0]);
-            let t_res = ty::mk_res(tcx, def_id, t_arg.ty, params);
+            let t_arg = ty_of_arg(ccx, type_rscope(rp), decl.inputs[0]);
+            let t_res = ty::mk_res(tcx, def_id, t_arg.ty, substs);
+
             let t_ctor = ty::mk_fn(tcx, {
                 proto: ast::proto_box,
-                inputs: [{mode: ast::expl(ast::by_copy) with t_arg}],
+                inputs: [{mode: ast::expl(ast::by_copy), ty: t_arg.ty}],
                 output: t_res,
                 ret_style: ast::return_val, constraints: []
             });
@@ -1460,8 +1498,12 @@ mod collect {
             write_ty_to_tcx(tcx, it.id, t_res);
             write_ty_to_tcx(tcx, ctor_id, t_ctor);
             tcx.tcache.insert(local_def(ctor_id),
-                              {bounds: bounds, ty: t_ctor});
-            tcx.tcache.insert(def_id, {bounds: bounds, ty: t_res});
+                              {bounds: bounds,
+                               rp: ast::rp_none,
+                               ty: t_ctor});
+            tcx.tcache.insert(def_id, {bounds: bounds,
+                                       rp: ast::rp_none,
+                                       ty: t_res});
             write_ty_to_tcx(tcx, dtor_id, t_dtor);
           }
           ast::item_iface(_, ms) {
@@ -1469,57 +1511,68 @@ mod collect {
             write_ty_to_tcx(tcx, it.id, tpt.ty);
             ensure_iface_methods(ccx, it.id);
           }
-          ast::item_class(tps, ifaces, members, ctor) {
-              // Write the class type
-              let tpt = ty_of_item(ccx, it);
-              write_ty_to_tcx(tcx, it.id, tpt.ty);
-              // Write the ctor type
-              let t_ctor =
-                  ty::mk_fn(tcx,
-                            ty_of_fn_decl(ccx, base_rscope,
-                                          ast::proto_any,
-                                          ctor.node.dec));
-              write_ty_to_tcx(tcx, ctor.node.id, t_ctor);
-              tcx.tcache.insert(local_def(ctor.node.id),
-                                   {bounds: tpt.bounds, ty: t_ctor});
-              ensure_iface_methods(ccx, it.id);
-              /* FIXME: check for proper public/privateness */
-              // Write the type of each of the members
-              let (fields, methods) = split_class_items(members);
-              for fields.each {|f|
-                 convert_class_item(ccx, f);
-              }
-              // The selfty is just the class type
-              let selfty = ty::mk_class(tcx, local_def(it.id),
-                                        mk_ty_params(ccx, tps).params);
-              // Need to convert all methods so we can check internal
-              // references to private methods
-              convert_methods(ccx, methods, @[], some(selfty));
-              /*
-                Finally, check that the class really implements the ifaces
-                that it claims to implement.
-               */
-              for ifaces.each {|ifce|
+          ast::item_class(tps, ifaces, members, ctor, rp) {
+            // Write the class type
+            let tpt = ty_of_item(ccx, it);
+            write_ty_to_tcx(tcx, it.id, tpt.ty);
+            // Write the ctor type
+            let t_ctor =
+                ty::mk_fn(tcx,
+                          ty_of_fn_decl(ccx,
+                                        empty_rscope,
+                                        ast::proto_any,
+                                        ctor.node.dec));
+            write_ty_to_tcx(tcx, ctor.node.id, t_ctor);
+            tcx.tcache.insert(local_def(ctor.node.id),
+                              {bounds: tpt.bounds,
+                               rp: ast::rp_none, // NDM self->anon
+                               ty: t_ctor});
+            ensure_iface_methods(ccx, it.id);
+            /* FIXME: check for proper public/privateness */
+            // Write the type of each of the members
+            let (fields, methods) = split_class_items(members);
+            for fields.each {|f|
+                convert_class_item(ccx, rp, f);
+            }
+            // The selfty is just the class type
+            let {bounds:_, substs} = mk_substs(ccx, tps, rp);
+            let selfty = ty::mk_class(tcx, local_def(it.id), substs);
+            // Need to convert all methods so we can check internal
+            // references to private methods
+
+            // NDM to TJC---I think we ought to be using bounds here, not @[].
+            // But doing so causes errors later on.
+            convert_methods(ccx, methods, rp, @[], selfty);
+
+            /*
+            Finally, check that the class really implements the ifaces
+            that it claims to implement.
+            */
+            for ifaces.each { |ifce|
                 alt lookup_def_tcx(tcx, it.span, ifce.id) {
-                   ast::def_ty(t_id) {
-                     let t = ty::lookup_item_type(tcx, t_id).ty;
-                     alt ty::get(t).struct {
-                        ty::ty_iface(_,_) {
-                          write_ty_to_tcx(tcx, ifce.id, t);
-                            check_methods_against_iface(ccx, tps, selfty,
-                               @{id: ifce.id,
-                                 node: ast::ty_path(ifce.path, ifce.id),
-                                 span: ifce.path.span},
-                               methods);
-                        }
-                        _ { tcx.sess.span_fatal(ifce.path.span,
-                           "can only implement interface types"); }
-                     }
-                   }
-                   _ { tcx.sess.span_err(ifce.path.span, "not an interface \
-                           type"); }
-                };
-              }
+                  ast::def_ty(t_id) {
+                    let t = ty::lookup_item_type(tcx, t_id).ty;
+                    alt ty::get(t).struct {
+                      ty::ty_iface(_,_) {
+                        write_ty_to_tcx(tcx, ifce.id, t);
+                        check_methods_against_iface(
+                            ccx, tps, rp, selfty,
+                            @{id: ifce.id,
+                              node: ast::ty_path(ifce.path, ifce.id),
+                              span: ifce.path.span},
+                            methods);
+                      }
+                      _ {
+                        tcx.sess.span_fatal(
+                            ifce.path.span,
+                            "can only implement interface types");
+                      }
+                    }
+                  }
+                  _ { tcx.sess.span_err(ifce.path.span, "not an interface \
+                                                         type"); }
+                }
+            }
           }
           _ {
             // This call populates the type cache with the converted type
@@ -1577,10 +1630,10 @@ fn do_autoderef(fcx: @fn_ctxt, sp: span, t: ty::t) -> ty::t {
             }
             t1 = inner.ty;
           }
-          ty::ty_res(_, inner, tps) {
-            t1 = ty::substitute_type_params(fcx.ccx.tcx, tps, inner);
+          ty::ty_res(_, inner, substs) {
+            t1 = ty::subst(fcx.ccx.tcx, substs, inner);
           }
-          ty::ty_enum(did, tps) {
+          ty::ty_enum(did, substs) {
             // Watch out for a type like `enum t = @t`.  Such a type would
             // otherwise infinitely auto-deref.  This is the only autoderef
             // loop that needs to be concerned with this, as an error will be
@@ -1595,9 +1648,7 @@ fn do_autoderef(fcx: @fn_ctxt, sp: span, t: ty::t) -> ty::t {
             if vec::len(*variants) != 1u || vec::len(variants[0].args) != 1u {
                 ret t1;
             }
-            t1 =
-                ty::substitute_type_params(fcx.ccx.tcx, tps,
-                                           variants[0].args[0]);
+            t1 = ty::subst(fcx.ccx.tcx, substs, variants[0].args[0]);
           }
           _ { ret t1; }
         }
@@ -1613,7 +1664,7 @@ fn resolve_type_vars_if_possible(fcx: @fn_ctxt, typ: ty::t) -> ty::t {
 
 // Demands - procedures that require that two types unify and emit an error
 // message if they don't.
-type ty_param_substs_and_ty = {substs: [ty::t], ty: ty::t};
+type ty_param_substs_and_ty = {substs: ty::substs, ty: ty::t};
 
 fn require_same_types(
     tcx: ty::ctxt,
@@ -1669,30 +1720,6 @@ fn are_compatible(fcx: @fn_ctxt, expected: ty::t, actual: ty::t) -> bool {
 }
 
 
-// Returns the types of the arguments to a enum variant.
-fn variant_arg_types(ccx: @crate_ctxt, _sp: span, vid: ast::def_id,
-                     enum_ty_params: [ty::t]) -> [ty::t] {
-    let mut result: [ty::t] = [];
-    let tpt = ty::lookup_item_type(ccx.tcx, vid);
-    alt ty::get(tpt.ty).struct {
-      ty::ty_fn(f) {
-        // N-ary variant.
-        for f.inputs.each {|arg|
-            let arg_ty =
-                ty::substitute_type_params(ccx.tcx, enum_ty_params, arg.ty);
-            result += [arg_ty];
-        }
-      }
-      _ {
-        // Nullary variant. Do nothing, as there are no arguments.
-      }
-    }
-    /* result is a vector of the *expected* types of all the fields */
-
-    ret result;
-}
-
-
 // Type resolution: the phase that finds all the types in the AST with
 // unresolved type variables and replaces "ty_var" types with their
 // substitutions.
@@ -1734,14 +1761,14 @@ mod writeback {
             write_ty_to_tcx(tcx, id, t);
             alt fcx.opt_node_ty_substs(id) {
               some(substs) {
-                let mut new_substs = [];
-                for substs.each {|subst|
+                let mut new_tps = [];
+                for substs.tps.each {|subst|
                     alt resolve_type_vars_in_type(fcx, sp, subst) {
-                      some(t) { new_substs += [t]; }
+                      some(t) { new_tps += [t]; }
                       none { wbcx.success = false; ret none; }
                     }
                 }
-                write_substs_to_tcx(tcx, id, new_substs);
+                write_substs_to_tcx(tcx, id, new_tps);
               }
               none {}
             }
@@ -1959,14 +1986,6 @@ type pat_ctxt = {
     pat_region: ty::region
 };
 
-fn subst_anon_region(tcx: ty::ctxt,
-                     with_r: ty::region,
-                     ty: ty::t) -> ty::t {
-    ty::fold_regions(tcx, ty) {|r, in_fn|
-        if !in_fn && r == ty::re_bound(ty::br_anon) {with_r} else {r}
-    }
-}
-
 // Helper for the other universally_quantify_*() routines.  Extracts the bound
 // regions from bound_tys and then replaces those same regions with fresh
 // variables in `sty`, returning the resulting type.
@@ -1979,12 +1998,11 @@ fn universally_quantify_from_sty(fcx: @fn_ctxt,
            bound_tys.map {|x| fcx.ty_to_str(x) }];
     indent {||
         let tcx = fcx.tcx();
-        let isr = collect_named_regions_in_tys(tcx, @nil, bound_tys) { |_id|
+        let isr = collect_bound_regions_in_tys(tcx, @nil, bound_tys) { |_id|
             fcx.next_region_var()
         };
-        let anon_r = fcx.next_region_var();
         ty::fold_sty_to_ty(fcx.ccx.tcx, sty) { |t|
-            replace_bound_regions(tcx, span, anon_r, isr, t)
+            replace_bound_regions(tcx, span, isr, t)
         }
     }
 }
@@ -2012,18 +2030,6 @@ fn universally_quantify_before_call(fcx: @fn_ctxt,
     // introduce a level of binding.  In this case, we want to process the
     // types bound by the function but not by any nested functions.
     // Therefore, we match one level of structure.
-    //
-    // Specifically what we do is:
-    // - Find the set of named regions that appear in arguments, return
-    //   type, etc. We use collect_named_regions_in_ty(), which
-    //   returns a free version of the region---not quite what we want.
-    //
-    // - So then we map the resulting map so that we each bound region
-    //   will be mapped to a fresh variable.
-    //
-    // - Finally, we can use fold_sty_to_ty() and replace_bound_regions()
-    //   to replace the bound regions as well as the bound anonymous region.
-    //   We have to use fold_sty_to_ty() to ignore the outer fn().
     alt structure_of(fcx, span, ty) {
       sty @ ty::ty_fn(fty) {
         let all_tys = fty.inputs.map({|a| a.ty}) + [fty.output];
@@ -2056,19 +2062,20 @@ fn check_pat_variant(pcx: pat_ctxt, pat: @ast::pat, path: @ast::path,
 
     // Take the enum type params out of `expected`.
     alt structure_of(pcx.fcx, pat.span, expected) {
-      ty::ty_enum(_, expected_tps) {
+      ty::ty_enum(_, expected_substs) {
         // check that the type of the value being matched is a subtype
         // of the type of the pattern:
         let pat_ty = fcx.node_ty(pat.id);
         demand::suptype(fcx, pat.span, pat_ty, expected);
 
-        // Get the number of arguments in this enum variant.
-        let arg_types = variant_arg_types(pcx.fcx.ccx, pat.span,
-                                          v_def_ids.var, expected_tps);
-        let arg_types = vec::map(arg_types) {|t|
-            // NDM---is this reasonable?
-            instantiate_bound_regions(pcx.fcx.ccx.tcx, pcx.pat_region, t)
+        // Get the expected types of the arguments.
+        let arg_types = {
+            let vinfo =
+                ty::enum_variant_with_id(
+                    tcx, v_def_ids.enm, v_def_ids.var);
+            vinfo.args.map { |t| ty::subst(tcx, expected_substs, t) }
         };
+
         let subpats_len = subpats.len(), arg_len = arg_types.len();
         if arg_len > 0u {
             // N-ary variant.
@@ -2079,14 +2086,14 @@ fn check_pat_variant(pcx: pat_ctxt, pat: @ast::pat, path: @ast::path,
                              if subpats_len == 1u { "" } else { "s" },
                              arg_len,
                              if arg_len == 1u { "" } else { "s" }];
-                tcx.sess.span_err(pat.span, s);
+                tcx.sess.span_fatal(pat.span, s);
             }
 
             vec::iter2(subpats, arg_types) {|subpat, arg_ty|
                 check_pat(pcx, subpat, arg_ty);
             }
         } else if subpats_len > 0u {
-            tcx.sess.span_err
+            tcx.sess.span_fatal
                 (pat.span, #fmt["this pattern has %u field%s, \
                                  but the corresponding variant has no fields",
                                 subpats_len,
@@ -2095,10 +2102,10 @@ fn check_pat_variant(pcx: pat_ctxt, pat: @ast::pat, path: @ast::path,
         }
       }
       _ {
-        tcx.sess.span_err
+        tcx.sess.span_fatal
             (pat.span,
              #fmt["mismatched types: expected enum but found `%s`",
-                  ty_to_str(tcx, expected)]);
+                  fcx.ty_to_str(expected)]);
       }
     }
 }
@@ -2345,8 +2352,10 @@ fn impl_self_ty(fcx: @fn_ctxt, did: ast::def_id) -> ty_param_substs_and_ty {
          raw_ty: ity.ty}
     };
 
-    let substs = fcx.next_ty_vars(n_tps);
-    let substd_ty = ty::substitute_type_params(tcx, substs, raw_ty);
+    let self_r = none; // NDM iface/impl regions
+    let tps = fcx.next_ty_vars(n_tps);
+    let substs = {self_r: self_r, tps: tps};
+    let substd_ty = ty::subst(tcx, substs, raw_ty);
     {substs: substs, ty: substd_ty}
 }
 
@@ -2375,8 +2384,8 @@ impl methods for lookup {
           ty::ty_iface(did, tps) {
             self.method_from_iface(did, tps)
           }
-          ty::ty_class(did, tps) {
-            self.method_from_class(did, tps)
+          ty::ty_class(did, substs) {
+            self.method_from_class(did, substs)
           }
           _ {
             none
@@ -2413,9 +2422,12 @@ impl methods for lookup {
               }
 
               some(pos) {
-                  ret some(self.write_mty_from_m(
-                      some(self.self_ty), bound_tps, ifce_methods[pos],
-                      method_param(iid, pos, n, iface_bnd_idx)));
+                let bound_substs = { // NDM iface/impl regions
+                    self_r: none, tps: bound_tps
+                };
+                ret some(self.write_mty_from_m(
+                    some(self.self_ty), bound_substs, ifce_methods[pos],
+                    method_param(iid, pos, n, iface_bnd_idx)));
               }
             }
         }
@@ -2445,15 +2457,19 @@ impl methods for lookup {
                      boxed iface");
             }
 
+            let iface_substs = { // NDM iface/impl regions
+                self_r: none, tps: iface_tps
+            };
+
             ret some(self.write_mty_from_m(
-                none, iface_tps, m,
+                none, iface_substs, m,
                 method_iface(did, i)));
         }
 
         ret none;
     }
 
-    fn method_from_class(did: ast::def_id, class_tps: [ty::t])
+    fn method_from_class(did: ast::def_id, class_substs: ty::substs)
         -> option<method_origin> {
 
         let ms = *ty::iface_methods(self.tcx(), did);
@@ -2473,7 +2489,7 @@ impl methods for lookup {
                 self.tcx(), did, self.m_name, self.expr.span);
 
             ret some(self.write_mty_from_m(
-                none, class_tps, m,
+                none, class_substs, m,
                 method_static(m_declared)));
         }
 
@@ -2484,7 +2500,8 @@ impl methods for lookup {
         if did.crate == ast::local_crate {
             alt check self.tcx().items.get(did.node) {
               ast_map::node_method(m, _, _) {
-                let mt = ty_of_method(self.fcx.ccx, m);
+                // NDM iface/impl regions
+                let mt = ty_of_method(self.fcx.ccx, m, ast::rp_none);
                 ty::mk_fn(self.tcx(), {proto: ast::proto_box with mt.fty})
               }
             }
@@ -2551,7 +2568,7 @@ impl methods for lookup {
     }
 
     fn write_mty_from_m(self_ty_sub: option<ty::t>,
-                        self_substs: [ty::t],
+                        self_substs: ty::substs,
                         m: ty::method,
                         origin: method_origin) -> method_origin {
         let tcx = self.fcx.ccx.tcx;
@@ -2565,7 +2582,7 @@ impl methods for lookup {
     }
 
     fn write_mty_from_fty(self_ty_sub: option<ty::t>,
-                          self_substs: [ty::t],
+                          self_substs: ty::substs,
                           n_tps_m: uint,
                           fty: ty::t,
                           origin: method_origin) -> method_origin {
@@ -2596,7 +2613,8 @@ impl methods for lookup {
             }
         };
 
-        let all_substs = self_substs + m_substs;
+        let all_substs = {self_r: self_substs.self_r,
+                          tps: self_substs.tps + m_substs};
         self.fcx.write_ty_substs(self.node_id, fty, all_substs);
 
         // FIXME--this treatment of self and regions seems wrong.  As a rule
@@ -2610,7 +2628,7 @@ impl methods for lookup {
         if has_self && !option::is_none(self_ty_sub) {
             let fty = self.fcx.node_ty(self.node_id);
             let fty = fixup_self_param(
-                self.fcx, fty, all_substs, self_ty_sub.get(),
+                self.fcx, fty, all_substs.tps, self_ty_sub.get(),
                 self.expr.span);
             self.fcx.write_ty(self.node_id, fty);
         }
@@ -2630,7 +2648,7 @@ impl methods for lookup {
 // FIXME: privacy flags
 fn lookup_field_ty(tcx: ty::ctxt, class_id: ast::def_id,
                    items:[ty::field_ty], fieldname: ast::ident,
-                   substs: [ty::t]) -> option<ty::t> {
+                   substs: ty::substs) -> option<ty::t> {
 
     let o_field = vec::find(items, {|f| f.ident == fieldname});
     option::map(o_field) {|f|
@@ -3083,7 +3101,7 @@ fn check_expr_with_unifier(fcx: @fn_ctxt,
               ty::ty_box(inner) { oper_t = inner.ty; }
               ty::ty_uniq(inner) { oper_t = inner.ty; }
               ty::ty_res(_, inner, _) { oper_t = inner; }
-              ty::ty_enum(id, tps) {
+              ty::ty_enum(id, substs) {
                 let variants = ty::enum_variants(tcx, id);
                 if vec::len(*variants) != 1u ||
                        vec::len(variants[0].args) != 1u {
@@ -3092,8 +3110,7 @@ fn check_expr_with_unifier(fcx: @fn_ctxt,
                                         "with a single variant which has a "
                                             + "single argument");
                 }
-                oper_t =
-                    ty::substitute_type_params(tcx, tps, variants[0].args[0]);
+                oper_t = ty::subst(tcx, substs, variants[0].args[0]);
               }
               ty::ty_ptr(inner) {
                 oper_t = inner.ty;
@@ -3493,7 +3510,7 @@ fn check_expr_with_unifier(fcx: @fn_ctxt,
               _ {}
             }
           }
-          ty::ty_class(base_id, params) {
+          ty::ty_class(base_id, substs) {
               // This is just for fields -- the same code handles
               // methods in both classes and ifaces
 
@@ -3512,7 +3529,7 @@ fn check_expr_with_unifier(fcx: @fn_ctxt,
               else {
                   lookup_public_fields(tcx, base_id)
               };
-              alt lookup_field_ty(tcx, base_id, cls_items, field, params) {
+              alt lookup_field_ty(tcx, base_id, cls_items, field, substs) {
                  some(field_ty) {
                     // (2) look up what field's type is, and return it
                     // FIXME: actually instantiate any type params
@@ -3801,8 +3818,10 @@ fn check_instantiable(tcx: ty::ctxt,
     }
 }
 
-fn check_enum_variants(ccx: @crate_ctxt, sp: span, vs: [ast::variant],
-                      id: ast::node_id) {
+fn check_enum_variants(ccx: @crate_ctxt,
+                       sp: span,
+                       vs: [ast::variant],
+                       id: ast::node_id) {
     // FIXME: this is kinda a kludge; we manufacture a fake function context
     // and statement context for checking the initializer expression.
     let rty = ty::node_id_to_type(ccx.tcx, id);
@@ -4005,25 +4024,30 @@ fn check_fn(ccx: @crate_ctxt,
 
     let tcx = ccx.tcx;
 
-    // See big comment in region.rs.
     let isr = {
+        // Find the list of in-scope regions.  These are derived from the
+        // various regions that are bound in the argument, return, and self
+        // types.  For each of those bound regions, we will create a mapping
+        // to a free region tied to the node_id of this function.  For an
+        // in-depth discussion of why we must distinguish bound/free regions,
+        // see the big comment in region.rs.
         let all_tys = arg_tys + [ret_ty] + self_ty.to_vec();
         let old_isr = option::map_default(old_fcx, @nil) {
             |fcx| fcx.in_scope_regions };
-        collect_named_regions_in_tys(tcx, old_isr, all_tys) {
-            |id| ty::re_free(fid, ty::br_named(id)) }
+        collect_bound_regions_in_tys(tcx, old_isr, all_tys) {
+            |br| ty::re_free(fid, br) }
     };
-    let anon_r = ty::re_free(fid, ty::br_anon);
-    let self_r = ty::re_free(fid, ty::br_self);
-    let arg_tys = arg_tys.map {|arg_ty|
-        let arg_ty = replace_bound_self(tcx, self_r, arg_ty);
-        replace_bound_regions(tcx, body.span, anon_r, isr, arg_ty)
+
+    // Replace the bound regions that appear in the arg tys, ret ty, etc with
+    // the free versions we just collected.
+    let arg_tys = arg_tys.map {
+        |arg_ty| replace_bound_regions(tcx, body.span, isr, arg_ty)
     };
-    let ret_ty = replace_bound_self(tcx, self_r, ret_ty);
-    let ret_ty = replace_bound_regions(tcx, body.span, anon_r, isr, ret_ty);
-    let self_ty = option::map(self_ty) {|self_ty|
-        let self_ty = replace_bound_self(tcx, self_r, self_ty);
-        replace_bound_regions(tcx, body.span, anon_r, isr, self_ty)
+    let ret_ty = {
+        replace_bound_regions(tcx, body.span, isr, ret_ty)
+    };
+    let self_ty = option::map(self_ty) {
+        |self_ty| replace_bound_regions(tcx, body.span, isr, self_ty)
     };
 
     #debug["check_fn(arg_tys=%?, ret_ty=%?, self_ty=%?)",
@@ -4031,8 +4055,8 @@ fn check_fn(ccx: @crate_ctxt,
            ty_to_str(tcx, ret_ty),
            option::map(self_ty) {|st| ty_to_str(tcx, st) }];
 
-    // If old_fcx is some(...), this is a block fn { |x| ... }.
-    // In that case, the purity is inherited from the context.
+    // Create the function context.  This is either derived from scratch or,
+    // in the case of function expressions, based on the outer context.
     let fcx: @fn_ctxt = {
         let {infcx, locals, tvc, rvc, purity,
              node_types, node_type_substs} = alt old_fcx {
@@ -4184,16 +4208,20 @@ fn check_method(ccx: @crate_ctxt, method: @ast::method, self_ty: ty::t) {
     check_bare_fn(ccx, method.decl, method.body, method.id, some(self_ty));
 }
 
-fn class_types(ccx: @crate_ctxt, members: [@ast::class_member]) -> class_map {
+fn class_types(ccx: @crate_ctxt, members: [@ast::class_member],
+               rp: ast::region_param) -> class_map {
+
     let rslt = int_hash::<ty::t>();
-    for members.each {|m|
+    let rs = type_rscope(rp);
+    for members.each { |m|
       alt m.node {
          ast::instance_var(_,t,_,id,_) {
-           rslt.insert(id, ccx.to_ty(t));
+           rslt.insert(id, ccx.to_ty(rs, t));
          }
          ast::class_method(mth) {
-             rslt.insert(mth.id, ty::mk_fn(ccx.tcx,
-                ty_of_method(ccx, mth).fty));
+           rslt.insert(mth.id,
+                       ty::mk_fn(ccx.tcx,
+                                 ty_of_method(ccx, mth, rp).fty));
          }
       }
     }
@@ -4213,24 +4241,26 @@ fn check_class_member(ccx: @crate_ctxt, class_t: ty::t,
 fn check_item(ccx: @crate_ctxt, it: @ast::item) {
     alt it.node {
       ast::item_const(_, e) { check_const(ccx, it.span, e, it.id); }
-      ast::item_enum(vs, _) { check_enum_variants(ccx, it.span, vs, it.id); }
+      ast::item_enum(vs, _, _) {
+        check_enum_variants(ccx, it.span, vs, it.id);
+      }
       ast::item_fn(decl, tps, body) {
         check_bare_fn(ccx, decl, body, it.id, none);
       }
-      ast::item_res(decl, tps, body, dtor_id, _) {
+      ast::item_res(decl, tps, body, dtor_id, _, rp) {
         check_instantiable(ccx.tcx, it.span, it.id);
         check_bare_fn(ccx, decl, body, dtor_id, none);
       }
       ast::item_impl(tps, _, ty, ms) {
-        let self_ty = ccx.to_self_ty(ty);
+        let self_ty = ccx.to_ty(empty_rscope, ty); // NDM iface/impl regions
         let self_region = ty::re_free(it.id, ty::br_self);
         let self_ty = replace_self_region(ccx.tcx, self_region, self_ty);
         for ms.each {|m| check_method(ccx, m, self_ty);}
       }
-      ast::item_class(tps, ifaces, members, ctor) {
+      ast::item_class(tps, ifaces, members, ctor, rp) {
           let cid = some(it.id), tcx = ccx.tcx;
           let class_t = ty::node_id_to_type(tcx, it.id);
-          let members_info = class_types(ccx, members);
+          let members_info = class_types(ccx, members, rp);
           // can also ditch the enclosing_class stuff once we move to self
           // FIXME
           let class_ccx = @{enclosing_class_id:cid,
@@ -4330,7 +4360,7 @@ mod vtable {
             for vec::each(*bounds[i]) {|bound|
                 alt bound {
                   ty::bound_iface(i_ty) {
-                    let i_ty = ty::substitute_type_params(tcx, tys, i_ty);
+                    let i_ty = ty::subst_tps(tcx, tys, i_ty);
                     result += [lookup_vtable(fcx, isc, sp, ty, i_ty,
                                              allow_unsafe)];
                   }
@@ -4398,7 +4428,7 @@ mod vtable {
                           _ { false }
                         };
                         if match {
-                            let {substs: vars, ty: self_ty} =
+                            let {substs: substs, ty: self_ty} =
                                 impl_self_ty(fcx, im.did);
                             let im_bs =
                                 ty::lookup_item_type(tcx, im.did).bounds;
@@ -4409,6 +4439,7 @@ mod vtable {
                                         sp, "multiple applicable implemen\
                                              tations in scope");
                                 } else {
+                                    let vars = substs.tps;
                                     connect_iface_tps(fcx, sp, vars,
                                                       iface_tps, im.did);
                                     let params = vec::map(vars, {|t|
@@ -4456,7 +4487,7 @@ mod vtable {
                          iface_tys: [ty::t], impl_did: ast::def_id) {
         let tcx = fcx.ccx.tcx;
         let ity = option::get(ty::impl_iface(tcx, impl_did));
-        let iface_ty = ty::substitute_type_params(tcx, impl_tys, ity);
+        let iface_ty = ty::subst_tps(tcx, impl_tys, ity);
         alt check ty::get(iface_ty).struct {
           ty::ty_iface(_, tps) {
             vec::iter2(tps, iface_tys,
@@ -4470,13 +4501,15 @@ mod vtable {
         alt ex.node {
           ast::expr_path(_) {
             alt fcx.opt_node_ty_substs(ex.id) {
-              some(ts) {
+              some(substs) {
+                let ts = substs.tps; // NDM regions for iface/impls
                 let did = ast_util::def_id_of_def(cx.tcx.def_map.get(ex.id));
                 let item_ty = ty::lookup_item_type(cx.tcx, did);
                 if has_iface_bounds(*item_ty.bounds) {
                     let impls = cx.impl_map.get(ex.id);
                     cx.vtable_map.insert(ex.id, lookup_vtables(
-                        fcx, impls, ex.span, item_ty.bounds, ts, false));
+                        fcx, impls, ex.span,
+                        item_ty.bounds, ts, false));
                 }
               }
               _ {}
@@ -4494,7 +4527,8 @@ mod vtable {
                       ast::expr_field(_, _, _) { ex.id }
                       _ { ast_util::op_expr_callee_id(ex) }
                     };
-                    let ts = fcx.node_ty_substs(callee_id);
+                    // NDM iface/impl regions
+                    let ts = fcx.node_ty_substs(callee_id).tps;
                     let iscs = cx.impl_map.get(ex.id);
                     cx.vtable_map.insert(callee_id, lookup_vtables(
                         fcx, iscs, ex.span, bounds, ts, false));
diff --git a/src/rustc/util/ppaux.rs b/src/rustc/util/ppaux.rs
index 95b5969169b..30e20883e52 100644
--- a/src/rustc/util/ppaux.rs
+++ b/src/rustc/util/ppaux.rs
@@ -10,11 +10,12 @@ import syntax::{ast, ast_util};
 import middle::ast_map;
 import driver::session::session;
 
-fn bound_region_to_str(_cx: ctxt, br: bound_region) -> str {
+fn bound_region_to_str(cx: ctxt, br: bound_region) -> str {
     alt br {
-      br_anon          { "&" }
-      br_named(str)    { #fmt["&%s", str] }
-      br_self          { "&self" }
+      br_anon                             { "&" }
+      br_named(str)                       { #fmt["&%s", str] }
+      br_self if cx.sess.opts.debug_rustc { "&<self>" }
+      br_self                             { "&self" }
     }
 }
 
@@ -127,12 +128,23 @@ fn ty_to_str(cx: ctxt, typ: t) -> str {
     fn field_to_str(cx: ctxt, f: field) -> str {
         ret f.ident + ": " + mt_to_str(cx, f.mt);
     }
-    fn parameterized(cx: ctxt, base: str, tps: [ty::t]) -> str {
+    fn parameterized(cx: ctxt,
+                     base: str,
+                     self_r: option<ty::region>,
+                     tps: [ty::t]) -> str {
+
+        let r_str = alt self_r {
+          none { "" }
+          some(r) {
+            #fmt["/%s", region_to_str(cx, r)]
+          }
+        };
+
         if vec::len(tps) > 0u {
             let strs = vec::map(tps, {|t| ty_to_str(cx, t)});
-            #fmt["%s<%s>", base, str::connect(strs, ",")]
+            #fmt["%s%s<%s>", base, r_str, str::connect(strs, ",")]
         } else {
-            base
+            #fmt["%s%s", base, r_str]
         }
     }
 
@@ -141,9 +153,11 @@ fn ty_to_str(cx: ctxt, typ: t) -> str {
       some(def_id) {
         let cs = ast_map::path_to_str(ty::item_path(cx, def_id));
         ret alt ty::get(typ).struct {
-          ty_enum(_, tps) | ty_res(_, _, tps) | ty_iface(_, tps) |
-          ty_class(_, tps) {
-            parameterized(cx, cs, tps)
+          ty_enum(_, substs) | ty_res(_, _, substs) | ty_class(_, substs) {
+            parameterized(cx, cs, substs.self_r, substs.tps)
+          }
+          ty_iface(_, tps) {
+            parameterized(cx, cs, none, tps)
           }
           _ { cs }
         };
@@ -164,7 +178,7 @@ fn ty_to_str(cx: ctxt, typ: t) -> str {
       ty_float(ast::ty_f) { "float" }
       ty_float(t) { ast_util::float_ty_to_str(t) }
       ty_str { "str" }
-      ty_self(ts) { parameterized(cx, "self", ts) }
+      ty_self(ts) { parameterized(cx, "self", none, ts) }
       ty_box(tm) { "@" + mt_to_str(cx, tm) }
       ty_uniq(tm) { "~" + mt_to_str(cx, tm) }
       ty_ptr(tm) { "*" + mt_to_str(cx, tm) }
@@ -196,11 +210,15 @@ fn ty_to_str(cx: ctxt, typ: t) -> str {
       ty_param(id, _) {
         "'" + str::from_bytes([('a' as u8) + (id as u8)])
       }
-      ty_enum(did, tps) | ty_res(did, _, tps) | ty_iface(did, tps) |
-      ty_class(did, tps) {
+      ty_enum(did, substs) | ty_res(did, _, substs) | ty_class(did, substs) {
+        let path = ty::item_path(cx, did);
+        let base = ast_map::path_to_str(path);
+        parameterized(cx, base, substs.self_r, substs.tps)
+      }
+      ty_iface(did, tps) {
         let path = ty::item_path(cx, did);
         let base = ast_map::path_to_str(path);
-        parameterized(cx, base, tps)
+        parameterized(cx, base, none, tps)
       }
       ty_evec(mt, vs) {
         #fmt["[%s]/%s", mt_to_str(cx, mt),
diff --git a/src/rustdoc/attr_pass.rs b/src/rustdoc/attr_pass.rs
index f36f3688a3a..674d7a7fc3b 100644
--- a/src/rustdoc/attr_pass.rs
+++ b/src/rustdoc/attr_pass.rs
@@ -147,7 +147,7 @@ fn fold_enum(
             let desc = astsrv::exec(srv) {|ctxt|
                 alt check ctxt.ast_map.get(doc_id) {
                   ast_map::node_item(@{
-                    node: ast::item_enum(ast_variants, _), _
+                    node: ast::item_enum(ast_variants, _, _), _
                   }, _) {
                     let ast_variant = option::get(
                         vec::find(ast_variants) {|v|
diff --git a/src/rustdoc/extract.rs b/src/rustdoc/extract.rs
index 6bcd93ba9f5..e9cfdc4db90 100644
--- a/src/rustdoc/extract.rs
+++ b/src/rustdoc/extract.rs
@@ -78,12 +78,12 @@ fn moddoc_from_mod(
                     constdoc_from_const(itemdoc)
                 ))
               }
-              ast::item_enum(variants, _) {
+              ast::item_enum(variants, _, _) {
                 some(doc::enumtag(
                     enumdoc_from_enum(itemdoc, variants)
                 ))
               }
-              ast::item_res(_, _, _, _, _) {
+              ast::item_res(_, _, _, _, _, _) {
                 some(doc::restag(
                     resdoc_from_resource(itemdoc)
                 ))
@@ -98,7 +98,7 @@ fn moddoc_from_mod(
                     impldoc_from_impl(itemdoc, methods)
                 ))
               }
-              ast::item_ty(_, _) {
+              ast::item_ty(_, _, _) {
                 some(doc::tytag(
                     tydoc_from_ty(itemdoc)
                 ))
diff --git a/src/rustdoc/tystr_pass.rs b/src/rustdoc/tystr_pass.rs
index 1819e7f0888..3e5ac07f093 100644
--- a/src/rustdoc/tystr_pass.rs
+++ b/src/rustdoc/tystr_pass.rs
@@ -112,7 +112,7 @@ fn fold_enum(
             let sig = astsrv::exec(srv) {|ctxt|
                 alt check ctxt.ast_map.get(doc_id) {
                   ast_map::node_item(@{
-                    node: ast::item_enum(ast_variants, _), _
+                    node: ast::item_enum(ast_variants, _, _), _
                   }, _) {
                     let ast_variant = option::get(
                         vec::find(ast_variants) {|v|
@@ -149,9 +149,9 @@ fn fold_res(
         sig: some(astsrv::exec(srv) {|ctxt|
             alt check ctxt.ast_map.get(doc.id()) {
               ast_map::node_item(@{
-                node: ast::item_res(decl, tys, _, _, _), _
+                node: ast::item_res(decl, tys, _, _, _, rp), _
               }, _) {
-                pprust::res_to_str(decl, doc.name(), tys)
+                pprust::res_to_str(decl, doc.name(), tys, rp)
               }
             }
         })
@@ -303,7 +303,7 @@ fn fold_type(
             alt ctxt.ast_map.get(doc.id()) {
               ast_map::node_item(@{
                 ident: ident,
-                node: ast::item_ty(ty, params), _
+                node: ast::item_ty(ty, params, ast::rp_none), _
               }, _) {
                 some(#fmt(
                     "type %s%s = %s",
diff --git a/src/test/bench/shootout-binarytrees.rs b/src/test/bench/shootout-binarytrees.rs
index 4d2c6144cdc..bbe6667ced6 100644
--- a/src/test/bench/shootout-binarytrees.rs
+++ b/src/test/bench/shootout-binarytrees.rs
@@ -2,7 +2,7 @@ use std;
 import std::arena;
 import std::arena::arena;
 
-enum tree { nil, node(&tree, &tree, int), }
+enum tree& { nil, node(&tree, &tree, int), }
 
 fn item_check(t: &tree) -> int {
     alt *t {
diff --git a/src/test/compile-fail/regions-creating-enums.rs b/src/test/compile-fail/regions-creating-enums.rs
new file mode 100644
index 00000000000..ae90feadd57
--- /dev/null
+++ b/src/test/compile-fail/regions-creating-enums.rs
@@ -0,0 +1,33 @@
+enum ast& {
+    num(uint),
+    add(&ast, &ast)
+}
+
+fn build() {
+    let x = num(3u);
+    let y = num(4u);
+    let z = add(&x, &y);
+    compute(&z);
+}
+
+fn compute(x: &ast) -> uint {
+    alt *x {
+      num(x) { x }
+      add(x, y) { compute(x) + compute(y) }
+    }
+}
+
+fn map_nums(x: &ast, f: fn(uint) -> uint) -> &ast {
+    alt *x {
+      num(x) {
+        ret &num(f(x)); //! ERROR mismatched types: expected `&ast/&` but found
+      }
+      add(x, y) {
+        let m_x = map_nums(x, f);
+        let m_y = map_nums(y, f);
+        ret &add(m_x, m_y);  //! ERROR mismatched types: expected `&ast/&` but found
+      }
+    }
+}
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/compile-fail/regions-in-enums.rs b/src/test/compile-fail/regions-in-enums.rs
new file mode 100644
index 00000000000..4585c781739
--- /dev/null
+++ b/src/test/compile-fail/regions-in-enums.rs
@@ -0,0 +1,25 @@
+enum no0 {
+    x0(&uint) //! ERROR to use region types here, the containing type must be declared with a region bound
+}
+
+enum no1 {
+    x1(&self.uint) //! ERROR to use region types here, the containing type must be declared with a region bound
+}
+
+enum no2 {
+    x2(&foo.uint) //! ERROR named regions other than `self` are not allowed as part of a type declaration
+}
+
+enum yes0& {
+    x3(&uint)
+}
+
+enum yes1& {
+    x4(&self.uint)
+}
+
+enum yes2& {
+    x5(&foo.uint) //! ERROR named regions other than `self` are not allowed as part of a type declaration
+}
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/compile-fail/regions-in-rsrcs.rs b/src/test/compile-fail/regions-in-rsrcs.rs
new file mode 100644
index 00000000000..3b0e61d6163
--- /dev/null
+++ b/src/test/compile-fail/regions-in-rsrcs.rs
@@ -0,0 +1,19 @@
+resource no0(x: &uint) { //! ERROR to use region types here, the containing type must be declared with a region bound
+}
+
+resource no1(x: &self.uint) { //! ERROR to use region types here, the containing type must be declared with a region bound
+}
+
+resource no2(x: &foo.uint) { //! ERROR named regions other than `self` are not allowed as part of a type declaration
+}
+
+resource yes0&(x: &uint) {
+}
+
+resource yes1&(x: &self.uint) {
+}
+
+resource yes2&(x: &foo.uint) { //! ERROR named regions other than `self` are not allowed as part of a type declaration
+}
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/compile-fail/regions-in-type-items.rs b/src/test/compile-fail/regions-in-type-items.rs
new file mode 100644
index 00000000000..80d734d9992
--- /dev/null
+++ b/src/test/compile-fail/regions-in-type-items.rs
@@ -0,0 +1,25 @@
+type item_ty_no0 = {
+    x: &uint //! ERROR to use region types here, the containing type must be declared with a region bound
+};
+
+type item_ty_no1 = {
+    x: &self.uint //! ERROR to use region types here, the containing type must be declared with a region bound
+};
+
+type item_ty_no2 = {
+    x: &foo.uint //! ERROR named regions other than `self` are not allowed as part of a type declaration
+};
+
+type item_ty_yes0& = {
+    x: &uint
+};
+
+type item_ty_yes1& = {
+    x: &self.uint
+};
+
+type item_ty_yes2& = {
+    x: &foo.uint //! ERROR named regions other than `self` are not allowed as part of a type declaration
+};
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/compile-fail/seq-args.rs b/src/test/compile-fail/seq-args.rs
index d21c2871be3..4273675e4da 100644
--- a/src/test/compile-fail/seq-args.rs
+++ b/src/test/compile-fail/seq-args.rs
@@ -2,8 +2,7 @@ use std;
 fn main() {
 iface seq { }
 
-impl <T> of seq<T> for [T] {
-    //!^ ERROR wrong number of type arguments for a polymorphic type
+impl <T> of seq<T> for [T] { //! ERROR wrong number of type arguments
     /* ... */
 }
 impl of seq<bool> for u32 {
diff --git a/src/test/run-pass/regions-mock-trans-impls.rs b/src/test/run-pass/regions-mock-trans-impls.rs
index 2c1c16e4315..4801524c55f 100644
--- a/src/test/run-pass/regions-mock-trans-impls.rs
+++ b/src/test/run-pass/regions-mock-trans-impls.rs
@@ -2,11 +2,11 @@ import libc, sys, unsafe;
 
 enum arena = ();
 
-type bcx = {
+type bcx& = {
     fcx: &fcx
 };
 
-type fcx = {
+type fcx& = {
     arena: &arena,
     ccx: &ccx
 };
diff --git a/src/test/run-pass/regions-mock-trans.rs b/src/test/run-pass/regions-mock-trans.rs
index 62f095d8162..959319381c6 100644
--- a/src/test/run-pass/regions-mock-trans.rs
+++ b/src/test/run-pass/regions-mock-trans.rs
@@ -2,11 +2,11 @@ import libc, sys, unsafe;
 
 enum arena = ();
 
-type bcx = {
+type bcx& = {
     fcx: &fcx
 };
 
-type fcx = {
+type fcx& = {
     arena: &arena,
     ccx: &ccx
 };