Generalize the `ty::substs` struct so that it can represent

multiple lifetime parameters, and not just one. Also add an option
for erasing lifetimes, which makes trans code somewhat simpler
and cleaner.

19 files changed, 304 insertions, 179 deletions

diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index 1edd3c805d0..b76743fc468 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -186,7 +186,7 @@ fn parse_trait_store(st: &mut PState) -> ty::TraitStore {
 }
 
 fn parse_substs(st: &mut PState, conv: conv_did) -> ty::substs {
-    let self_r = parse_opt(st, |st| parse_region(st) );
+    let regions = parse_region_substs(st, |x,y| conv(x,y));
 
     let self_ty = parse_opt(st, |st| parse_ty(st, |x,y| conv(x,y)) );
 
@@ -196,12 +196,28 @@ fn parse_substs(st: &mut PState, conv: conv_did) -> ty::substs {
     st.pos = st.pos + 1u;
 
     return ty::substs {
-        self_r: self_r,
+        regions: regions,
         self_ty: self_ty,
         tps: params
     };
 }
 
+fn parse_region_substs(st: &mut PState, conv: conv_did) -> ty::RegionSubsts {
+    match next(st) {
+        'e' => ty::ErasedRegions,
+        'n' => {
+            let mut regions = opt_vec::Empty;
+            while peek(st) != '.' {
+                let r = parse_region(st);
+                regions.push(r);
+            }
+            assert_eq!(next(st), '.');
+            ty::NonerasedRegions(regions)
+        }
+        _ => fail!("parse_bound_region: bad input")
+    }
+}
+
 fn parse_bound_region(st: &mut PState) -> ty::bound_region {
     match next(st) {
       's' => ty::br_self,
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index bab13c2b470..a1cb1bf6848 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -120,13 +120,28 @@ fn enc_opt<T>(w: @io::Writer, t: Option<T>, enc_f: &fn(T)) {
 }
 
 fn enc_substs(w: @io::Writer, cx: @ctxt, substs: &ty::substs) {
-    do enc_opt(w, substs.self_r) |r| { enc_region(w, cx, r) }
+    enc_region_substs(w, cx, &substs.regions);
     do enc_opt(w, substs.self_ty) |t| { enc_ty(w, cx, t) }
     w.write_char('[');
     for substs.tps.iter().advance |t| { enc_ty(w, cx, *t); }
     w.write_char(']');
 }
 
+fn enc_region_substs(w: @io::Writer, cx: @ctxt, substs: &ty::RegionSubsts) {
+    match *substs {
+        ty::ErasedRegions => {
+            w.write_char('e');
+        }
+        ty::NonerasedRegions(ref regions) => {
+            w.write_char('n');
+            for regions.iter().advance |&r| {
+                enc_region(w, cx, r);
+            }
+            w.write_char('.');
+        }
+    }
+}
+
 fn enc_region(w: @io::Writer, cx: @ctxt, r: ty::Region) {
     match r {
       ty::re_bound(br) => {
diff --git a/src/librustc/middle/kind.rs b/src/librustc/middle/kind.rs
index eb9d18c9b24..99aae34911b 100644
--- a/src/librustc/middle/kind.rs
+++ b/src/librustc/middle/kind.rs
@@ -19,6 +19,7 @@ use util::ppaux::UserString;
 use syntax::ast::*;
 use syntax::attr;
 use syntax::codemap::span;
+use syntax::opt_vec;
 use syntax::print::pprust::expr_to_str;
 use syntax::{visit, ast_util};
 
@@ -83,7 +84,7 @@ fn check_struct_safe_for_destructor(cx: Context,
     let struct_tpt = ty::lookup_item_type(cx.tcx, struct_did);
     if !struct_tpt.generics.has_type_params() {
         let struct_ty = ty::mk_struct(cx.tcx, struct_did, ty::substs {
-            self_r: None,
+            regions: ty::NonerasedRegions(opt_vec::Empty),
             self_ty: None,
             tps: ~[]
         });
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index d43cea2c733..7b2b130bc68 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -12,6 +12,7 @@
 
 
 use middle::ty;
+use syntax::opt_vec::OptVec;
 use util::ppaux::Repr;
 
 ///////////////////////////////////////////////////////////////////////////
@@ -79,6 +80,12 @@ impl<T:Subst> Subst for ~[T] {
     }
 }
 
+impl<T:Subst> Subst for OptVec<T> {
+    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> OptVec<T> {
+        self.map(|t| t.subst(tcx, substs))
+    }
+}
+
 impl<T:Subst + 'static> Subst for @T {
     fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> @T {
         match self {
@@ -105,13 +112,26 @@ impl Subst for ty::TraitRef {
 impl Subst for ty::substs {
     fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::substs {
         ty::substs {
-            self_r: self.self_r.subst(tcx, substs),
+            regions: self.regions.subst(tcx, substs),
             self_ty: self.self_ty.map(|typ| typ.subst(tcx, substs)),
             tps: self.tps.map(|typ| typ.subst(tcx, substs))
         }
     }
 }
 
+impl Subst for ty::RegionSubsts {
+    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::RegionSubsts {
+        match *self {
+            ty::ErasedRegions => {
+                ty::ErasedRegions
+            }
+            ty::NonerasedRegions(ref regions) => {
+                ty::NonerasedRegions(regions.subst(tcx, substs))
+            }
+        }
+    }
+}
+
 impl Subst for ty::BareFnTy {
     fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::BareFnTy {
         ty::fold_bare_fn_ty(self, |t| t.subst(tcx, substs))
@@ -158,15 +178,18 @@ impl Subst for ty::Region {
         // will most likely disappear.
         match self {
             &ty::re_bound(ty::br_self) => {
-                match substs.self_r {
-                    None => {
-                        tcx.sess.bug(
-                            fmt!("ty::Region#subst(): \
-                                  Reference to self region when \
-                                  given substs with no self region: %s",
-                                 substs.repr(tcx)));
+                match substs.regions {
+                    ty::ErasedRegions => ty::re_static,
+                    ty::NonerasedRegions(ref regions) => {
+                        if regions.len() != 1 {
+                            tcx.sess.bug(
+                                fmt!("ty::Region#subst(): \
+                                      Reference to self region when \
+                                      given substs with no self region: %s",
+                                     substs.repr(tcx)));
+                        }
+                        *regions.get(0)
                     }
-                    Some(self_r) => self_r
                 }
             }
             _ => *self
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index bf5c5ac334d..d2b075150ff 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -517,7 +517,8 @@ pub fn get_res_dtor(ccx: @mut CrateContext,
             did
         };
         assert_eq!(did.crate, ast::local_crate);
-        let tsubsts = ty::substs { self_r: None, self_ty: None,
+        let tsubsts = ty::substs {regions: ty::ErasedRegions,
+                                  self_ty: None,
                                   tps: /*bad*/ substs.to_owned() };
         let (val, _) = monomorphize::monomorphic_fn(ccx,
                                                     did,
diff --git a/src/librustc/middle/trans/callee.rs b/src/librustc/middle/trans/callee.rs
index 5f76981c794..416c5e3db29 100644
--- a/src/librustc/middle/trans/callee.rs
+++ b/src/librustc/middle/trans/callee.rs
@@ -284,15 +284,10 @@ pub fn trans_fn_ref_with_vtables(
     // Polytype of the function item (may have type params)
     let fn_tpt = ty::lookup_item_type(tcx, def_id);
 
-    // For simplicity, we want to use the Subst trait when composing
-    // substitutions for default methods.  The subst trait does
-    // substitutions with regions, though, so we put a dummy self
-    // region parameter in to keep it from failing. This is a hack.
-    let substs = ty::substs { self_r: Some(ty::re_empty),
+    let substs = ty::substs { regions: ty::ErasedRegions,
                               self_ty: None,
                               tps: /*bad*/ type_params.to_owned() };
 
-
     // We need to do a bunch of special handling for default methods.
     // We need to modify the def_id and our substs in order to monomorphize
     // the function.
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index fef6607bbed..bab0f41477c 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -1114,7 +1114,7 @@ pub fn find_vtable(tcx: ty::ctxt,
 
 pub fn dummy_substs(tps: ~[ty::t]) -> ty::substs {
     substs {
-        self_r: Some(ty::re_bound(ty::br_self)),
+        regions: ty::ErasedRegions,
         self_ty: None,
         tps: tps
     }
diff --git a/src/librustc/middle/trans/type_of.rs b/src/librustc/middle/trans/type_of.rs
index 4e15b4bc229..b743f2e9401 100644
--- a/src/librustc/middle/trans/type_of.rs
+++ b/src/librustc/middle/trans/type_of.rs
@@ -17,6 +17,7 @@ use util::ppaux;
 use middle::trans::type_::Type;
 
 use syntax::ast;
+use syntax::opt_vec;
 
 pub fn arg_is_indirect(ccx: &CrateContext, arg_ty: &ty::t) -> bool {
     !ty::type_is_immediate(ccx.tcx, *arg_ty)
@@ -312,7 +313,8 @@ pub fn llvm_type_name(cx: &CrateContext,
         a_struct => { "struct" }
         an_enum => { "enum" }
     };
-    let tstr = ppaux::parameterized(cx.tcx, ty::item_path_str(cx.tcx, did), None, tps);
+    let tstr = ppaux::parameterized(cx.tcx, ty::item_path_str(cx.tcx, did),
+                                    &ty::NonerasedRegions(opt_vec::Empty), tps);
     if did.crate == 0 {
         fmt!("%s.%s", name, tstr)
     } else {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index cd9d744c240..743d063be24 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -486,7 +486,15 @@ pub enum bound_region {
     br_cap_avoid(ast::node_id, @bound_region),
 }
 
-type opt_region = Option<Region>;
+/**
+ * Represents the values to use when substituting lifetime parameters.
+ * If the value is `ErasedRegions`, then this subst is occurring during
+ * trans, and all region parameters will be replaced with `ty::re_static`. */
+#[deriving(Clone, Eq, IterBytes)]
+pub enum RegionSubsts {
+    ErasedRegions,
+    NonerasedRegions(OptVec<ty::Region>)
+}
 
 /**
  * The type substs represents the kinds of things that can be substituted to
@@ -507,9 +515,9 @@ type opt_region = Option<Region>;
  *   always substituted away to the implementing type for a trait. */
 #[deriving(Clone, Eq, IterBytes)]
 pub struct substs {
-    self_r: opt_region,
     self_ty: Option<ty::t>,
-    tps: ~[t]
+    tps: ~[t],
+    regions: RegionSubsts,
 }
 
 mod primitives {
@@ -948,7 +956,14 @@ fn mk_t(cx: ctxt, st: sty) -> t {
     fn sflags(substs: &substs) -> uint {
         let mut f = 0u;
         for substs.tps.iter().advance |tt| { f |= get(*tt).flags; }
-        for substs.self_r.iter().advance |r| { f |= rflags(*r) }
+        match substs.regions {
+            ErasedRegions => {}
+            NonerasedRegions(ref regions) => {
+                for regions.iter().advance |r| {
+                    f |= rflags(*r)
+                }
+            }
+        }
         return f;
     }
     match &st {
@@ -1286,7 +1301,7 @@ pub fn fold_bare_fn_ty(fty: &BareFnTy, fldop: &fn(t) -> t) -> BareFnTy {
 
 fn fold_sty(sty: &sty, fldop: &fn(t) -> t) -> sty {
     fn fold_substs(substs: &substs, fldop: &fn(t) -> t) -> substs {
-        substs {self_r: substs.self_r,
+        substs {regions: substs.regions.clone(),
                 self_ty: substs.self_ty.map(|t| fldop(*t)),
                 tps: substs.tps.map(|t| fldop(*t))}
     }
@@ -1378,8 +1393,15 @@ pub fn fold_regions_and_ty(
         fldr: &fn(r: Region) -> Region,
         fldt: &fn(t: t) -> t)
      -> substs {
+        let regions = match substs.regions {
+            ErasedRegions => ErasedRegions,
+            NonerasedRegions(ref regions) => {
+                NonerasedRegions(regions.map(|r| fldr(*r)))
+            }
+        };
+
         substs {
-            self_r: substs.self_r.map(|r| fldr(*r)),
+            regions: regions,
             self_ty: substs.self_ty.map(|t| fldt(*t)),
             tps: substs.tps.map(|t| fldt(*t))
         }
@@ -1478,8 +1500,13 @@ pub fn subst_tps(cx: ctxt, tps: &[t], self_ty_opt: Option<t>, typ: t) -> t {
 }
 
 pub fn substs_is_noop(substs: &substs) -> bool {
+    let regions_is_noop = match substs.regions {
+        ErasedRegions => false, // may be used to canonicalize
+        NonerasedRegions(ref regions) => regions.is_empty()
+    };
+
     substs.tps.len() == 0u &&
-        substs.self_r.is_none() &&
+        regions_is_noop &&
         substs.self_ty.is_none()
 }
 
@@ -4227,30 +4254,33 @@ pub fn normalize_ty(cx: ctxt, t: t) -> t {
             })
         }
 
-        ty_enum(did, ref r) =>
-            match (*r).self_r {
-                Some(_) =>
-                    // Use re_static since trans doesn't care about regions
-                    mk_enum(cx, did,
-                     substs {
-                        self_r: Some(ty::re_static),
-                        self_ty: None,
-                        tps: (*r).tps.clone()
-                     }),
-                None =>
+        ty_enum(did, ref r) => {
+            match (*r).regions {
+                NonerasedRegions(_) => {
+                    // trans doesn't care about regions
+                    mk_enum(cx, did, substs {regions: ty::ErasedRegions,
+                                             self_ty: None,
+                                             tps: (*r).tps.clone()})
+                }
+                ErasedRegions => {
                     t
-            },
+                }
+            }
+        }
 
-        ty_struct(did, ref r) =>
-            match (*r).self_r {
-              Some(_) =>
-                // Ditto.
-                mk_struct(cx, did, substs {self_r: Some(ty::re_static),
-                                           self_ty: None,
-                                           tps: (*r).tps.clone()}),
-              None =>
-                t
-            },
+        ty_struct(did, ref r) => {
+            match (*r).regions {
+                NonerasedRegions(_) => {
+                    // Ditto.
+                    mk_struct(cx, did, substs {regions: ty::ErasedRegions,
+                                               self_ty: None,
+                                               tps: (*r).tps.clone()})
+                }
+                ErasedRegions => {
+                    t
+                }
+            }
+        }
 
         _ =>
             t
@@ -4434,7 +4464,7 @@ pub fn visitor_object_ty(tcx: ctxt) -> Result<(@TraitRef, t), ~str> {
         Err(s) => { return Err(s); }
     };
     let substs = substs {
-        self_r: None,
+        regions: ty::NonerasedRegions(opt_vec::Empty),
         self_ty: None,
         tps: ~[]
     };
diff --git a/src/librustc/middle/typeck/astconv.rs b/src/librustc/middle/typeck/astconv.rs
index 28595e5af51..a506142a971 100644
--- a/src/librustc/middle/typeck/astconv.rs
+++ b/src/librustc/middle/typeck/astconv.rs
@@ -150,26 +150,27 @@ fn ast_path_substs<AC:AstConv,RS:region_scope + Clone + 'static>(
     // If the type is parameterized by the this region, then replace this
     // region with the current anon region binding (in other words,
     // whatever & would get replaced with).
-    let self_r = match (&decl_generics.region_param, &path.rp) {
-      (&None, &None) => {
-        None
-      }
-      (&None, &Some(_)) => {
-        tcx.sess.span_err(
-            path.span,
-            fmt!("no region bound is allowed on `%s`, \
-                  which is not declared as containing region pointers",
-                 ty::item_path_str(tcx, def_id)));
-        None
-      }
-      (&Some(_), &None) => {
-        let res = rscope.anon_region(path.span);
-        let r = get_region_reporting_err(this.tcx(), path.span, &None, res);
-        Some(r)
-      }
-      (&Some(_), &Some(_)) => {
-        Some(ast_region_to_region(this, rscope, path.span, &path.rp))
-      }
+    let regions = match (&decl_generics.region_param, &path.rp) {
+        (&None, &None) => {
+            opt_vec::Empty
+        }
+        (&None, &Some(_)) => {
+            tcx.sess.span_err(
+                path.span,
+                fmt!("no region bound is allowed on `%s`, \
+                      which is not declared as containing region pointers",
+                     ty::item_path_str(tcx, def_id)));
+            opt_vec::Empty
+        }
+        (&Some(_), &None) => {
+            let res = rscope.anon_region(path.span);
+            let r = get_region_reporting_err(this.tcx(), path.span, &None, res);
+            opt_vec::with(r)
+        }
+        (&Some(_), &Some(_)) => {
+            opt_vec::with(
+                ast_region_to_region(this, rscope, path.span, &path.rp))
+        }
     };
 
     // Convert the type parameters supplied by the user.
@@ -181,7 +182,7 @@ fn ast_path_substs<AC:AstConv,RS:region_scope + Clone + 'static>(
     }
     let tps = path.types.map(|a_t| ast_ty_to_ty(this, rscope, a_t));
 
-    substs {self_r:self_r, self_ty:self_ty, tps:tps}
+    substs {regions:ty::NonerasedRegions(regions), self_ty:self_ty, tps:tps}
 }
 
 pub fn ast_path_to_substs_and_ty<AC:AstConv,
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index 4a32e8bf952..05e400fb8b5 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -952,7 +952,7 @@ impl<'self> LookupContext<'self> {
         // which is equal to the class tps + the method tps.
         let all_substs = substs {
             tps: vec::append(candidate.rcvr_substs.tps.clone(), m_substs),
-            self_r: candidate.rcvr_substs.self_r,
+            regions: candidate.rcvr_substs.regions.clone(),
             self_ty: candidate.rcvr_substs.self_ty,
         };
 
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index c04e1c2515c..a7aef4f0680 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -925,10 +925,15 @@ impl FnCtxt {
     pub fn region_var_if_parameterized(&self,
                                        rp: Option<ty::region_variance>,
                                        span: span)
-                                       -> Option<ty::Region> {
-        rp.map(
-            |_| self.infcx().next_region_var(
-                infer::BoundRegionInTypeOrImpl(span)))
+                                       -> OptVec<ty::Region> {
+        match rp {
+            None => opt_vec::Empty,
+            Some(_) => {
+                opt_vec::with(
+                    self.infcx().next_region_var(
+                        infer::BoundRegionInTypeOrImpl(span)))
+            }
+        }
     }
 
     pub fn type_error_message(&self,
@@ -1111,15 +1116,15 @@ pub fn impl_self_ty(vcx: &VtableContext,
         (ity.generics.type_param_defs.len(), ity.generics.region_param, ity.ty)
     };
 
-    let self_r = if region_param.is_some() {
-        Some(vcx.infcx.next_region_var(
+    let regions = ty::NonerasedRegions(if region_param.is_some() {
+        opt_vec::with(vcx.infcx.next_region_var(
             infer::BoundRegionInTypeOrImpl(location_info.span)))
     } else {
-        None
-    };
+        opt_vec::Empty
+    });
     let tps = vcx.infcx.next_ty_vars(n_tps);
 
-    let substs = substs { self_r: self_r, self_ty: None, tps: tps };
+    let substs = substs {regions: regions, self_ty: None, tps: tps};
     let substd_ty = ty::subst(tcx, &substs, raw_ty);
 
     ty_param_substs_and_ty { substs: substs, ty: substd_ty }
@@ -1986,7 +1991,7 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
                         bound_self_region(region_parameterized);
 
                     raw_type = ty::mk_struct(tcx, class_id, substs {
-                        self_r: self_region,
+                        regions: ty::NonerasedRegions(self_region),
                         self_ty: None,
                         tps: ty::ty_params_to_tys(
                             tcx,
@@ -2006,11 +2011,11 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
         }
 
         // Generate the struct type.
-        let self_region =
+        let regions =
             fcx.region_var_if_parameterized(region_parameterized, span);
         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
         let substitutions = substs {
-            self_r: self_region,
+            regions: ty::NonerasedRegions(regions),
             self_ty: None,
             tps: type_parameters
         };
@@ -2070,11 +2075,10 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
 
                     type_parameter_count = generics.ty_params.len();
 
-                    let self_region =
-                        bound_self_region(region_parameterized);
+                    let regions = bound_self_region(region_parameterized);
 
                     raw_type = ty::mk_enum(tcx, enum_id, substs {
-                        self_r: self_region,
+                        regions: ty::NonerasedRegions(regions),
                         self_ty: None,
                         tps: ty::ty_params_to_tys(
                             tcx,
@@ -2094,11 +2098,11 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
         }
 
         // Generate the enum type.
-        let self_region =
+        let regions =
             fcx.region_var_if_parameterized(region_parameterized, span);
         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
         let substitutions = substs {
-            self_r: self_region,
+            regions: ty::NonerasedRegions(regions),
             self_ty: None,
             tps: type_parameters
         };
@@ -3309,22 +3313,23 @@ pub fn instantiate_path(fcx: @mut FnCtxt,
 
     // determine the region bound, using the value given by the user
     // (if any) and otherwise using a fresh region variable
-    let self_r = match pth.rp {
-      Some(_) => { // user supplied a lifetime parameter...
-        match tpt.generics.region_param {
-          None => { // ...but the type is not lifetime parameterized!
-            fcx.ccx.tcx.sess.span_err
-                (span, "this item is not region-parameterized");
-            None
-          }
-          Some(_) => { // ...and the type is lifetime parameterized, ok.
-            Some(ast_region_to_region(fcx, fcx, span, &pth.rp))
-          }
+    let regions = match pth.rp {
+        Some(_) => { // user supplied a lifetime parameter...
+            match tpt.generics.region_param {
+                None => { // ...but the type is not lifetime parameterized!
+                    fcx.ccx.tcx.sess.span_err
+                        (span, "this item is not region-parameterized");
+                    opt_vec::Empty
+                }
+                Some(_) => { // ...and the type is lifetime parameterized, ok.
+                    opt_vec::with(
+                        ast_region_to_region(fcx, fcx, span, &pth.rp))
+                }
+            }
+        }
+        None => { // no lifetime parameter supplied, insert default
+            fcx.region_var_if_parameterized(tpt.generics.region_param, span)
         }
-      }
-      None => { // no lifetime parameter supplied, insert default
-        fcx.region_var_if_parameterized(tpt.generics.region_param, span)
-      }
     };
 
     // determine values for type parameters, using the values given by
@@ -3351,7 +3356,9 @@ pub fn instantiate_path(fcx: @mut FnCtxt,
         pth.types.map(|aty| fcx.to_ty(aty))
     };
 
-    let substs = substs { self_r: self_r, self_ty: None, tps: tps };
+    let substs = substs {regions: ty::NonerasedRegions(regions),
+                         self_ty: None,
+                         tps: tps };
     fcx.write_ty_substs(node_id, tpt.ty, substs);
 
     debug!("<<<");
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index da09f79d031..7fd4257a006 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -590,7 +590,7 @@ pub fn early_resolve_expr(ex: @ast::expr,
                               def_id: target_def_id,
                               substs: ty::substs {
                                   tps: target_substs.tps.clone(),
-                                  self_r: target_substs.self_r,
+                                  regions: target_substs.regions.clone(),
                                   self_ty: Some(mt.ty)
                               }
                           };
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index 84a2627c87c..ca3710e19a4 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -45,6 +45,7 @@ use syntax::ast_map;
 use syntax::ast_util::{def_id_of_def, local_def};
 use syntax::codemap::{span, dummy_sp};
 use syntax::parse;
+use syntax::opt_vec;
 use syntax::visit::{default_simple_visitor, default_visitor};
 use syntax::visit::{mk_simple_visitor, mk_vt, visit_crate, visit_item};
 use syntax::visit::{Visitor, SimpleVisitor};
@@ -436,16 +437,20 @@ impl CoherenceChecker {
     pub fn universally_quantify_polytype(&self,
                                          polytype: ty_param_bounds_and_ty)
                                          -> UniversalQuantificationResult {
-        let self_region =
-            polytype.generics.region_param.map(
-                |_| self.inference_context.next_region_var(
-                    infer::BoundRegionInCoherence));
+        let regions = match polytype.generics.region_param {
+            None => opt_vec::Empty,
+            Some(r) => {
+                opt_vec::with(
+                    self.inference_context.next_region_var(
+                        infer::BoundRegionInCoherence))
+            }
+        };
 
         let bounds_count = polytype.generics.type_param_defs.len();
         let type_parameters = self.inference_context.next_ty_vars(bounds_count);
 
         let substitutions = substs {
-            self_r: self_region,
+            regions: ty::NonerasedRegions(regions),
             self_ty: None,
             tps: type_parameters
         };
@@ -453,13 +458,9 @@ impl CoherenceChecker {
                              &substitutions,
                              polytype.ty);
 
-        // Get our type parameters back.
-        let substs { self_r: _, self_ty: _, tps: type_parameters } =
-            substitutions;
-
         UniversalQuantificationResult {
             monotype: monotype,
-            type_variables: type_parameters,
+            type_variables: substitutions.tps,
             type_param_defs: polytype.generics.type_param_defs
         }
     }
@@ -845,7 +846,7 @@ pub fn make_substs_for_receiver_types(tcx: ty::ctxt,
     });
 
     return ty::substs {
-        self_r: trait_ref.substs.self_r,
+        regions: trait_ref.substs.regions.clone(),
         self_ty: trait_ref.substs.self_ty,
         tps: combined_tps
     };
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index 3db881dac1a..98b4de9d719 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -301,7 +301,7 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
         //     Self => D'
         //     D,E,F => E',F',G'
         let substs = substs {
-            self_r: None,
+            regions: ty::NonerasedRegions(opt_vec::Empty),
             self_ty: Some(self_param),
             tps: non_shifted_trait_tps + shifted_method_tps
         };
@@ -622,7 +622,7 @@ pub fn compare_impl_method(tcx: ty::ctxt,
         let trait_tps = trait_substs.tps.map(
             |t| replace_bound_self(tcx, *t, dummy_self_r));
         let substs = substs {
-            self_r: Some(dummy_self_r),
+            regions: ty::NonerasedRegions(opt_vec::with(dummy_self_r)),
             self_ty: Some(self_ty),
             tps: vec::append(trait_tps, dummy_tps)
         };
@@ -1268,6 +1268,8 @@ pub fn mk_item_substs(ccx: &CrateCtxt,
         i += 1u;
         t
     });
-    let self_r = rscope::bound_self_region(rp);
-    (ty_generics, substs {self_r: self_r, self_ty: self_ty, tps: params})
+    let regions = rscope::bound_self_region(rp);
+    (ty_generics, substs {regions: ty::NonerasedRegions(regions),
+                          self_ty: self_ty,
+                          tps: params})
 }
diff --git a/src/librustc/middle/typeck/infer/combine.rs b/src/librustc/middle/typeck/infer/combine.rs
index 65fbd080561..b1492cac16e 100644
--- a/src/librustc/middle/typeck/infer/combine.rs
+++ b/src/librustc/middle/typeck/infer/combine.rs
@@ -197,56 +197,67 @@ pub fn super_substs<C:Combine>(
     this: &C, generics: &ty::Generics,
     a: &ty::substs, b: &ty::substs) -> cres<ty::substs> {
 
-    fn relate_region_param<C:Combine>(
+    fn relate_region_params<C:Combine>(
         this: &C,
         generics: &ty::Generics,
-        a: Option<ty::Region>,
-        b: Option<ty::Region>)
-        -> cres<Option<ty::Region>>
+        a: &ty::RegionSubsts,
+        b: &ty::RegionSubsts)
+        -> cres<ty::RegionSubsts>
     {
-        match (&generics.region_param, &a, &b) {
-          (&None, &None, &None) => {
-            Ok(None)
-          }
-          (&Some(ty::rv_invariant), &Some(a), &Some(b)) => {
-            do eq_regions(this, a, b).then {
-                Ok(Some(a))
-            }
-          }
-          (&Some(ty::rv_covariant), &Some(a), &Some(b)) => {
-            do this.regions(a, b).chain |r| {
-                Ok(Some(r))
+        match (a, b) {
+            (&ty::ErasedRegions, _) |
+            (_, &ty::ErasedRegions) => {
+                Ok(ty::ErasedRegions)
             }
-          }
-          (&Some(ty::rv_contravariant), &Some(a), &Some(b)) => {
-            do this.contraregions(a, b).chain |r| {
-                Ok(Some(r))
+
+            (&ty::NonerasedRegions(ref a_rs),
+             &ty::NonerasedRegions(ref b_rs)) => {
+                match generics.region_param {
+                    None => {
+                        assert!(a_rs.is_empty());
+                        assert!(b_rs.is_empty());
+                        Ok(ty::NonerasedRegions(opt_vec::Empty))
+                    }
+
+                    Some(variance) => {
+                        assert_eq!(a_rs.len(), 1);
+                        assert_eq!(b_rs.len(), 1);
+                        let a_r = *a_rs.get(0);
+                        let b_r = *b_rs.get(0);
+
+                        match variance {
+                            ty::rv_invariant => {
+                                do eq_regions(this, a_r, b_r).then {
+                                    Ok(ty::NonerasedRegions(opt_vec::with(a_r)))
+                                }
+                            }
+
+                            ty::rv_covariant => {
+                                do this.regions(a_r, b_r).chain |r| {
+                                    Ok(ty::NonerasedRegions(opt_vec::with(r)))
+                                }
+                            }
+
+                            ty::rv_contravariant => {
+                                do this.contraregions(a_r, b_r).chain |r| {
+                                    Ok(ty::NonerasedRegions(opt_vec::with(r)))
+                                }
+                            }
+                        }
+                    }
+                }
             }
-          }
-          (_, _, _) => {
-            // If these two substitutions are for the same type (and
-            // they should be), then the type should either
-            // consistently have a region parameter or not have a
-            // region parameter, and that should match with the
-            // polytype.
-            this.infcx().tcx.sess.bug(
-                fmt!("substitution a had opt_region %s and \
-                      b had opt_region %s with variance %?",
-                      a.inf_str(this.infcx()),
-                      b.inf_str(this.infcx()),
-                     generics.region_param));
-          }
         }
     }
 
     do this.tps(a.tps, b.tps).chain |tps| {
         do this.self_tys(a.self_ty, b.self_ty).chain |self_ty| {
-            do relate_region_param(this,
-                                   generics,
-                                   a.self_r,
-                                   b.self_r).chain |self_r| {
+            do relate_region_params(this,
+                                    generics,
+                                    &a.regions,
+                                    &b.regions).chain |regions| {
                 Ok(substs {
-                    self_r: self_r,
+                    regions: regions,
                     self_ty: self_ty,
                     tps: tps.clone()
                 })
diff --git a/src/librustc/middle/typeck/rscope.rs b/src/librustc/middle/typeck/rscope.rs
index 2f319687f6c..94d30fd9a87 100644
--- a/src/librustc/middle/typeck/rscope.rs
+++ b/src/librustc/middle/typeck/rscope.rs
@@ -260,10 +260,10 @@ impl region_scope for type_rscope {
 }
 
 pub fn bound_self_region(rp: Option<ty::region_variance>)
-                      -> Option<ty::Region> {
+                      -> OptVec<ty::Region> {
     match rp {
-      Some(_) => Some(ty::re_bound(ty::br_self)),
-      None => None
+      Some(_) => opt_vec::with(ty::re_bound(ty::br_self)),
+      None => opt_vec::Empty
     }
 }
 
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 32ac5e72928..6d74068401b 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -30,6 +30,8 @@ use syntax::codemap::span;
 use syntax::parse::token;
 use syntax::print::pprust;
 use syntax::{ast, ast_util};
+use syntax::opt_vec;
+use syntax::opt_vec::OptVec;
 
 /// Produces a string suitable for debugging output.
 pub trait Repr {
@@ -451,12 +453,12 @@ pub fn ty_to_str(cx: ctxt, typ: t) -> ~str {
       ty_enum(did, ref substs) | ty_struct(did, ref substs) => {
         let path = ty::item_path(cx, did);
         let base = ast_map::path_to_str(path, cx.sess.intr());
-        parameterized(cx, base, substs.self_r, substs.tps)
+        parameterized(cx, base, &substs.regions, substs.tps)
       }
       ty_trait(did, ref substs, s, mutbl, ref bounds) => {
         let path = ty::item_path(cx, did);
         let base = ast_map::path_to_str(path, cx.sess.intr());
-        let ty = parameterized(cx, base, substs.self_r, substs.tps);
+        let ty = parameterized(cx, base, &substs.regions, substs.tps);
         let bound_sep = if bounds.is_empty() { "" } else { ":" };
         let bound_str = bounds.repr(cx);
         fmt!("%s%s%s%s%s", trait_store_to_str(cx, s), mutability_to_str(mutbl), ty,
@@ -475,16 +477,18 @@ pub fn ty_to_str(cx: ctxt, typ: t) -> ~str {
 
 pub fn parameterized(cx: ctxt,
                      base: &str,
-                     self_r: Option<ty::Region>,
+                     regions: &ty::RegionSubsts,
                      tps: &[ty::t]) -> ~str {
 
     let mut strs = ~[];
-    match self_r {
-        None => (),
-        Some(r) => {
-            strs.push(region_to_str(cx, "", false, r))
+    match *regions {
+        ty::ErasedRegions => { }
+        ty::NonerasedRegions(ref regions) => {
+            for regions.iter().advance |&r| {
+                strs.push(region_to_str(cx, "", false, r))
+            }
         }
-    };
+    }
 
     for tps.iter().advance |t| {
         strs.push(ty_to_str(cx, *t))
@@ -534,6 +538,15 @@ impl<'self, T:Repr> Repr for &'self [T] {
     }
 }
 
+impl<T:Repr> Repr for OptVec<T> {
+    fn repr(&self, tcx: ctxt) -> ~str {
+        match *self {
+            opt_vec::Empty => ~"[]",
+            opt_vec::Vec(ref v) => repr_vec(tcx, *v)
+        }
+    }
+}
+
 // This is necessary to handle types like Option<~[T]>, for which
 // autoderef cannot convert the &[T] handler
 impl<T:Repr> Repr for ~[T] {
@@ -557,13 +570,22 @@ impl Repr for ty::t {
 
 impl Repr for ty::substs {
     fn repr(&self, tcx: ctxt) -> ~str {
-        fmt!("substs(self_r=%s, self_ty=%s, tps=%s)",
-             self.self_r.repr(tcx),
+        fmt!("substs(regions=%s, self_ty=%s, tps=%s)",
+             self.regions.repr(tcx),
              self.self_ty.repr(tcx),
              self.tps.repr(tcx))
     }
 }
 
+impl Repr for ty::RegionSubsts {
+    fn repr(&self, tcx: ctxt) -> ~str {
+        match *self {
+            ty::ErasedRegions => ~"erased",
+            ty::NonerasedRegions(ref regions) => regions.repr(tcx)
+        }
+    }
+}
+
 impl Repr for ty::ParamBounds {
     fn repr(&self, tcx: ctxt) -> ~str {
         let mut res = ~[];
@@ -832,10 +854,9 @@ impl UserString for ty::TraitRef {
         if tcx.sess.verbose() && self.substs.self_ty.is_some() {
             let mut all_tps = self.substs.tps.clone();
             for self.substs.self_ty.iter().advance |&t| { all_tps.push(t); }
-            parameterized(tcx, base, self.substs.self_r, all_tps)
+            parameterized(tcx, base, &self.substs.regions, all_tps)
         } else {
-            parameterized(tcx, base, self.substs.self_r,
-                          self.substs.tps)
+            parameterized(tcx, base, &self.substs.regions, self.substs.tps)
         }
     }
 }
diff --git a/src/libsyntax/opt_vec.rs b/src/libsyntax/opt_vec.rs
index 6ec80140c76..10603751a06 100644
--- a/src/libsyntax/opt_vec.rs
+++ b/src/libsyntax/opt_vec.rs
@@ -9,7 +9,6 @@
 // except according to those terms.
 
 /*!
- *
  * Defines a type OptVec<T> that can be used in place of ~[T].
  * OptVec avoids the need for allocation for empty vectors.
  * OptVec implements the iterable interface as well as