Auto merge of #32346 - nikomatsakis:no-erased-regions, r=eddyb

Remove `ErasedRegions` from substs

This commit removes the `ErasedRegions` enum from `Substs`. Instead, in trans, we just generate a vector of `ReStatic` of suitable length. The goal is both general cleanup and to help pave the way for a glorious future where erasure is used in type check.

r? @eddyb

One concern: might be nice to do some profiling. Not sure the best way to do that. Perhaps I'll investigate running nrc's test suite locally.

33 files changed, 192 insertions, 349 deletions

diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index 510a3dd454b..b9bf550704e 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -11,7 +11,6 @@
 // Type substitutions.
 
 pub use self::ParamSpace::*;
-pub use self::RegionSubsts::*;
 
 use middle::cstore;
 use middle::def_id::DefId;
@@ -34,16 +33,7 @@ use syntax::codemap::{Span, DUMMY_SP};
 #[derive(Clone, PartialEq, Eq, Hash)]
 pub struct Substs<'tcx> {
     pub types: VecPerParamSpace<Ty<'tcx>>,
-    pub regions: RegionSubsts,
-}
-
-/// 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::ReStatic`.
-#[derive(Clone, PartialEq, Eq, Hash)]
-pub enum RegionSubsts {
-    ErasedRegions,
-    NonerasedRegions(VecPerParamSpace<ty::Region>)
+    pub regions: VecPerParamSpace<ty::Region>,
 }
 
 impl<'tcx> Substs<'tcx> {
@@ -51,7 +41,7 @@ impl<'tcx> Substs<'tcx> {
                r: VecPerParamSpace<ty::Region>)
                -> Substs<'tcx>
     {
-        Substs { types: t, regions: NonerasedRegions(r) }
+        Substs { types: t, regions: r }
     }
 
     pub fn new_type(t: Vec<Ty<'tcx>>,
@@ -71,32 +61,15 @@ impl<'tcx> Substs<'tcx> {
                     VecPerParamSpace::new(r, Vec::new(), Vec::new()))
     }
 
-    pub fn erased(t: VecPerParamSpace<Ty<'tcx>>) -> Substs<'tcx>
-    {
-        Substs { types: t, regions: ErasedRegions }
-    }
-
     pub fn empty() -> Substs<'tcx> {
         Substs {
             types: VecPerParamSpace::empty(),
-            regions: NonerasedRegions(VecPerParamSpace::empty()),
-        }
-    }
-
-    pub fn trans_empty() -> Substs<'tcx> {
-        Substs {
-            types: VecPerParamSpace::empty(),
-            regions: ErasedRegions
+            regions: VecPerParamSpace::empty(),
         }
     }
 
     pub fn is_noop(&self) -> bool {
-        let regions_is_noop = match self.regions {
-            ErasedRegions => false, // may be used to canonicalize
-            NonerasedRegions(ref regions) => regions.is_empty(),
-        };
-
-        regions_is_noop && self.types.is_empty()
+        self.regions.is_empty() && self.types.is_empty()
     }
 
     pub fn type_for_def(&self, ty_param_def: &ty::TypeParameterDef) -> Ty<'tcx> {
@@ -115,26 +88,9 @@ impl<'tcx> Substs<'tcx> {
     }
 
     pub fn erase_regions(self) -> Substs<'tcx> {
-        let Substs { types, regions: _ } = self;
-        Substs { types: types, regions: ErasedRegions }
-    }
-
-    /// Since ErasedRegions are only to be used in trans, most of the compiler can use this method
-    /// to easily access the set of region substitutions.
-    pub fn regions<'a>(&'a self) -> &'a VecPerParamSpace<ty::Region> {
-        match self.regions {
-            ErasedRegions => panic!("Erased regions only expected in trans"),
-            NonerasedRegions(ref r) => r
-        }
-    }
-
-    /// Since ErasedRegions are only to be used in trans, most of the compiler can use this method
-    /// to easily access the set of region substitutions.
-    pub fn mut_regions<'a>(&'a mut self) -> &'a mut VecPerParamSpace<ty::Region> {
-        match self.regions {
-            ErasedRegions => panic!("Erased regions only expected in trans"),
-            NonerasedRegions(ref mut r) => r
-        }
+        let Substs { types, regions } = self;
+        let regions = regions.map(|_| ty::ReStatic);
+        Substs { types: types, regions: regions }
     }
 
     pub fn with_method(self,
@@ -144,7 +100,7 @@ impl<'tcx> Substs<'tcx> {
     {
         let Substs { types, regions } = self;
         let types = types.with_slice(FnSpace, &m_types);
-        let regions = regions.map(|r| r.with_slice(FnSpace, &m_regions));
+        let regions = regions.with_slice(FnSpace, &m_regions);
         Substs { types: types, regions: regions }
     }
 
@@ -154,27 +110,23 @@ impl<'tcx> Substs<'tcx> {
     {
         let Substs { types, regions } = self.clone();
         let types = types.with_slice(FnSpace, meth_substs.types.get_slice(FnSpace));
-        let regions = regions.map(|r| {
-            r.with_slice(FnSpace, meth_substs.regions().get_slice(FnSpace))
-        });
+        let regions = regions.with_slice(FnSpace, meth_substs.regions.get_slice(FnSpace));
         Substs { types: types, regions: regions }
     }
 
     pub fn with_method_from_subst(self, other: &Substs<'tcx>) -> Substs<'tcx> {
         let Substs { types, regions } = self;
         let types = types.with_slice(FnSpace, other.types.get_slice(FnSpace));
-        let regions = regions.map(|r| {
-            r.with_slice(FnSpace, other.regions().get_slice(FnSpace))
-        });
+        let regions = regions.with_slice(FnSpace, other.regions.get_slice(FnSpace));
         Substs { types: types, regions: regions }
     }
 
     /// Creates a trait-ref out of this substs, ignoring the FnSpace substs
     pub fn to_trait_ref(&self, tcx: &TyCtxt<'tcx>, trait_id: DefId)
                         -> ty::TraitRef<'tcx> {
-        let Substs { mut types, regions } = self.clone();
+        let Substs { mut types, mut regions } = self.clone();
         types.truncate(FnSpace, 0);
-        let regions = regions.map(|mut r| { r.truncate(FnSpace, 0); r });
+        regions.truncate(FnSpace, 0);
 
         ty::TraitRef {
             def_id: trait_id,
@@ -212,24 +164,6 @@ impl<'tcx> Decodable for &'tcx Substs<'tcx> {
     }
 }
 
-impl RegionSubsts {
-    pub fn map<F>(self, op: F) -> RegionSubsts where
-        F: FnOnce(VecPerParamSpace<ty::Region>) -> VecPerParamSpace<ty::Region>,
-    {
-        match self {
-            ErasedRegions => ErasedRegions,
-            NonerasedRegions(r) => NonerasedRegions(op(r))
-        }
-    }
-
-    pub fn is_erased(&self) -> bool {
-        match *self {
-            ErasedRegions => true,
-            NonerasedRegions(_) => false,
-        }
-    }
-}
-
 ///////////////////////////////////////////////////////////////////////////
 // ParamSpace
 
@@ -664,26 +598,22 @@ impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
         // the specialized routine `ty::replace_late_regions()`.
         match r {
             ty::ReEarlyBound(data) => {
-                match self.substs.regions {
-                    ErasedRegions => ty::ReStatic,
-                    NonerasedRegions(ref regions) =>
-                        match regions.opt_get(data.space, data.index as usize) {
-                            Some(&r) => {
-                                self.shift_region_through_binders(r)
-                            }
-                            None => {
-                                let span = self.span.unwrap_or(DUMMY_SP);
-                                self.tcx().sess.span_bug(
-                                    span,
-                                    &format!("Type parameter out of range \
-                                              when substituting in region {} (root type={:?}) \
-                                              (space={:?}, index={})",
-                                             data.name,
-                                             self.root_ty,
-                                             data.space,
-                                             data.index));
-                            }
-                        }
+                match self.substs.regions.opt_get(data.space, data.index as usize) {
+                    Some(&r) => {
+                        self.shift_region_through_binders(r)
+                    }
+                    None => {
+                        let span = self.span.unwrap_or(DUMMY_SP);
+                        self.tcx().sess.span_bug(
+                            span,
+                            &format!("Region parameter out of range \
+                                      when substituting in region {} (root type={:?}) \
+                                      (space={:?}, index={})",
+                                     data.name,
+                                     self.root_ty,
+                                     data.space,
+                                     data.index));
+                    }
                 }
             }
             _ => r
diff --git a/src/librustc/middle/traits/specialize/mod.rs b/src/librustc/middle/traits/specialize/mod.rs
index a692fe55a77..92478f2874e 100644
--- a/src/librustc/middle/traits/specialize/mod.rs
+++ b/src/librustc/middle/traits/specialize/mod.rs
@@ -102,14 +102,6 @@ pub fn translate_substs<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
         specialization_graph::Node::Trait(..) => source_trait_ref.substs.clone(),
     };
 
-    // retain erasure mode
-    // NB: this must happen before inheriting method generics below
-    let target_substs = if source_substs.regions.is_erased() {
-        target_substs.erase_regions()
-    } else {
-        target_substs
-    };
-
     // directly inherent the method generics, since those do not vary across impls
     infcx.tcx.mk_substs(target_substs.with_method_from_subst(source_substs))
 }
diff --git a/src/librustc/middle/ty/flags.rs b/src/librustc/middle/ty/flags.rs
index c491bd6ca5e..c874e9b7ca5 100644
--- a/src/librustc/middle/ty/flags.rs
+++ b/src/librustc/middle/ty/flags.rs
@@ -194,13 +194,8 @@ impl FlagComputation {
 
     fn add_substs(&mut self, substs: &subst::Substs) {
         self.add_tys(substs.types.as_slice());
-        match substs.regions {
-            subst::ErasedRegions => {}
-            subst::NonerasedRegions(ref regions) => {
-                for &r in regions {
-                    self.add_region(r);
-                }
-            }
+        for &r in &substs.regions {
+            self.add_region(r);
         }
     }
 
diff --git a/src/librustc/middle/ty/fold.rs b/src/librustc/middle/ty/fold.rs
index 090d4eeb874..f754e5c5a0a 100644
--- a/src/librustc/middle/ty/fold.rs
+++ b/src/librustc/middle/ty/fold.rs
@@ -532,7 +532,7 @@ impl<'tcx> TyCtxt<'tcx> {
             fn fold_substs(&mut self,
                            substs: &subst::Substs<'tcx>)
                            -> subst::Substs<'tcx> {
-                subst::Substs { regions: subst::ErasedRegions,
+                subst::Substs { regions: substs.regions.fold_with(self),
                                 types: substs.types.fold_with(self) }
             }
         }
diff --git a/src/librustc/middle/ty/mod.rs b/src/librustc/middle/ty/mod.rs
index 6a081cb8dd1..050024d0e94 100644
--- a/src/librustc/middle/ty/mod.rs
+++ b/src/librustc/middle/ty/mod.rs
@@ -2605,7 +2605,7 @@ impl<'tcx> TyCtxt<'tcx> {
 
         Substs {
             types: types,
-            regions: subst::NonerasedRegions(regions)
+            regions: regions,
         }
     }
 
diff --git a/src/librustc/middle/ty/relate.rs b/src/librustc/middle/ty/relate.rs
index 1df7a440f4f..563ff346a64 100644
--- a/src/librustc/middle/ty/relate.rs
+++ b/src/librustc/middle/ty/relate.rs
@@ -14,7 +14,7 @@
 //! type equality, etc.
 
 use middle::def_id::DefId;
-use middle::subst::{ErasedRegions, NonerasedRegions, ParamSpace, Substs};
+use middle::subst::{ParamSpace, Substs};
 use middle::ty::{self, Ty, TyCtxt, TypeFoldable};
 use middle::ty::error::{ExpectedFound, TypeError};
 use std::rc::Rc;
@@ -156,23 +156,15 @@ pub fn relate_substs<'a,'tcx:'a,R>(relation: &mut R,
         substs.types.replace(space, tps);
     }
 
-    match (&a_subst.regions, &b_subst.regions) {
-        (&ErasedRegions, _) | (_, &ErasedRegions) => {
-            substs.regions = ErasedRegions;
-        }
-
-        (&NonerasedRegions(ref a), &NonerasedRegions(ref b)) => {
-            for &space in &ParamSpace::all() {
-                let a_regions = a.get_slice(space);
-                let b_regions = b.get_slice(space);
-                let r_variances = variances.map(|v| v.regions.get_slice(space));
-                let regions = relate_region_params(relation,
-                                                   r_variances,
-                                                   a_regions,
-                                                   b_regions)?;
-                substs.mut_regions().replace(space, regions);
-            }
-        }
+    for &space in &ParamSpace::all() {
+        let a_regions = a_subst.regions.get_slice(space);
+        let b_regions = b_subst.regions.get_slice(space);
+        let r_variances = variances.map(|v| v.regions.get_slice(space));
+        let regions = relate_region_params(relation,
+                                           r_variances,
+                                           a_regions,
+                                           b_regions)?;
+        substs.regions.replace(space, regions);
     }
 
     Ok(substs)
diff --git a/src/librustc/middle/ty/structural_impls.rs b/src/librustc/middle/ty/structural_impls.rs
index 57cfdd0d8b8..0358fa2f124 100644
--- a/src/librustc/middle/ty/structural_impls.rs
+++ b/src/librustc/middle/ty/structural_impls.rs
@@ -487,14 +487,7 @@ impl<'tcx> TypeFoldable<'tcx> for ty::Region {
 
 impl<'tcx> TypeFoldable<'tcx> for subst::Substs<'tcx> {
     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
-        let regions = match self.regions {
-            subst::ErasedRegions => subst::ErasedRegions,
-            subst::NonerasedRegions(ref regions) => {
-                subst::NonerasedRegions(regions.fold_with(folder))
-            }
-        };
-
-        subst::Substs { regions: regions,
+        subst::Substs { regions: self.regions.fold_with(folder),
                         types: self.types.fold_with(folder) }
     }
 
@@ -503,10 +496,7 @@ impl<'tcx> TypeFoldable<'tcx> for subst::Substs<'tcx> {
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
-        self.types.visit_with(visitor) || match self.regions {
-            subst::ErasedRegions => false,
-            subst::NonerasedRegions(ref regions) => regions.visit_with(visitor),
-        }
+        self.types.visit_with(visitor) || self.regions.visit_with(visitor)
     }
 }
 
diff --git a/src/librustc/middle/ty/sty.rs b/src/librustc/middle/ty/sty.rs
index 6b1ccf3b162..7a17b24df5e 100644
--- a/src/librustc/middle/ty/sty.rs
+++ b/src/librustc/middle/ty/sty.rs
@@ -1204,18 +1204,18 @@ impl<'tcx> TyS<'tcx> {
             TyTrait(ref obj) => {
                 let mut v = vec![obj.bounds.region_bound];
                 v.extend_from_slice(obj.principal.skip_binder()
-                                       .substs.regions().as_slice());
+                                       .substs.regions.as_slice());
                 v
             }
             TyEnum(_, substs) |
             TyStruct(_, substs) => {
-                substs.regions().as_slice().to_vec()
+                substs.regions.as_slice().to_vec()
             }
             TyClosure(_, ref substs) => {
-                substs.func_substs.regions().as_slice().to_vec()
+                substs.func_substs.regions.as_slice().to_vec()
             }
             TyProjection(ref data) => {
-                data.trait_ref.substs.regions().as_slice().to_vec()
+                data.trait_ref.substs.regions.as_slice().to_vec()
             }
             TyFnDef(..) |
             TyFnPtr(_) |
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 64619e40f49..6e7f49516e8 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -104,17 +104,9 @@ pub fn parameterized<GG>(f: &mut fmt::Formatter,
     };
 
     if verbose {
-        match substs.regions {
-            subst::ErasedRegions => {
-                start_or_continue(f, "<", ", ")?;
-                write!(f, "..")?;
-            }
-            subst::NonerasedRegions(ref regions) => {
-                for region in regions {
-                    start_or_continue(f, "<", ", ")?;
-                    write!(f, "{:?}", region)?;
-                }
-            }
+        for region in &substs.regions {
+            start_or_continue(f, "<", ", ")?;
+            write!(f, "{:?}", region)?;
         }
         for &ty in &substs.types {
             start_or_continue(f, "<", ", ")?;
@@ -136,23 +128,18 @@ pub fn parameterized<GG>(f: &mut fmt::Formatter,
         }
     }
 
-    match substs.regions {
-        subst::ErasedRegions => { }
-        subst::NonerasedRegions(ref regions) => {
-            for &r in regions {
-                start_or_continue(f, "<", ", ")?;
-                let s = r.to_string();
-                if s.is_empty() {
-                    // This happens when the value of the region
-                    // parameter is not easily serialized. This may be
-                    // because the user omitted it in the first place,
-                    // or because it refers to some block in the code,
-                    // etc. I'm not sure how best to serialize this.
-                    write!(f, "'_")?;
-                } else {
-                    write!(f, "{}", s)?;
-                }
-            }
+    for &r in &substs.regions {
+        start_or_continue(f, "<", ", ")?;
+        let s = r.to_string();
+        if s.is_empty() {
+            // This happens when the value of the region
+            // parameter is not easily serialized. This may be
+            // because the user omitted it in the first place,
+            // or because it refers to some block in the code,
+            // etc. I'm not sure how best to serialize this.
+            write!(f, "'_")?;
+        } else {
+            write!(f, "{}", s)?;
         }
     }
 
@@ -393,15 +380,6 @@ impl<'tcx> fmt::Debug for ty::ItemSubsts<'tcx> {
     }
 }
 
-impl fmt::Debug for subst::RegionSubsts {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        match *self {
-            subst::ErasedRegions => write!(f, "erased"),
-            subst::NonerasedRegions(ref regions) => write!(f, "{:?}", regions)
-        }
-    }
-}
-
 impl<'tcx> fmt::Debug for ty::TraitRef<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         // when printing out the debug representation, we don't need
diff --git a/src/librustc_lint/types.rs b/src/librustc_lint/types.rs
index 4d844bbf032..1a84afab86b 100644
--- a/src/librustc_lint/types.rs
+++ b/src/librustc_lint/types.rs
@@ -29,7 +29,6 @@ use syntax::attr::{self, AttrMetaMethods};
 use syntax::codemap::{self, Span};
 
 use rustc_front::hir;
-use rustc_front::intravisit::{self, Visitor};
 use rustc_front::util::is_shift_binop;
 
 register_long_diagnostics! {
@@ -403,16 +402,6 @@ fn is_repr_nullable_ptr<'tcx>(tcx: &TyCtxt<'tcx>,
     false
 }
 
-fn ast_ty_to_normalized<'tcx>(tcx: &TyCtxt<'tcx>,
-                              id: ast::NodeId)
-                              -> Ty<'tcx> {
-    let tty = match tcx.ast_ty_to_ty_cache.borrow().get(&id) {
-        Some(&t) => t,
-        None => panic!("ast_ty_to_ty_cache was incomplete after typeck!")
-    };
-    infer::normalize_associated_type(tcx, &tty)
-}
-
 impl<'a, 'tcx> ImproperCTypesVisitor<'a, 'tcx> {
     /// Check if the given type is "ffi-safe" (has a stable, well-defined
     /// representation which can be exported to C code).
@@ -604,10 +593,12 @@ impl<'a, 'tcx> ImproperCTypesVisitor<'a, 'tcx> {
         }
     }
 
-    fn check_def(&mut self, sp: Span, id: ast::NodeId) {
-        let tty = ast_ty_to_normalized(self.cx.tcx, id);
+    fn check_type_for_ffi_and_report_errors(&mut self, sp: Span, ty: Ty<'tcx>) {
+        // it is only OK to use this function because extern fns cannot have
+        // any generic types right now:
+        let ty = infer::normalize_associated_type(self.cx.tcx, &ty);
 
-        match ImproperCTypesVisitor::check_type_for_ffi(self, &mut FnvHashSet(), tty) {
+        match self.check_type_for_ffi(&mut FnvHashSet(), ty) {
             FfiResult::FfiSafe => {}
             FfiResult::FfiUnsafe(s) => {
                 self.cx.span_lint(IMPROPER_CTYPES, sp, s);
@@ -628,27 +619,30 @@ impl<'a, 'tcx> ImproperCTypesVisitor<'a, 'tcx> {
             }
         }
     }
-}
 
-impl<'a, 'tcx, 'v> Visitor<'v> for ImproperCTypesVisitor<'a, 'tcx> {
-    fn visit_ty(&mut self, ty: &hir::Ty) {
-        match ty.node {
-            hir::TyPath(..) |
-            hir::TyBareFn(..) => self.check_def(ty.span, ty.id),
-            hir::TyVec(..) => {
-                self.cx.span_lint(IMPROPER_CTYPES, ty.span,
-                    "found Rust slice type in foreign module, consider \
-                     using a raw pointer instead");
-            }
-            hir::TyFixedLengthVec(ref ty, _) => self.visit_ty(ty),
-            hir::TyTup(..) => {
-                self.cx.span_lint(IMPROPER_CTYPES, ty.span,
-                    "found Rust tuple type in foreign module; \
-                     consider using a struct instead`")
+    fn check_foreign_fn(&mut self, id: ast::NodeId, decl: &hir::FnDecl) {
+        let def_id = self.cx.tcx.map.local_def_id(id);
+        let scheme = self.cx.tcx.lookup_item_type(def_id);
+        let sig = scheme.ty.fn_sig();
+        let sig = self.cx.tcx.erase_late_bound_regions(&sig);
+
+        for (&input_ty, input_hir) in sig.inputs.iter().zip(&decl.inputs) {
+            self.check_type_for_ffi_and_report_errors(input_hir.ty.span, &input_ty);
+        }
+
+        if let hir::Return(ref ret_hir) = decl.output {
+            let ret_ty = sig.output.unwrap();
+            if !ret_ty.is_nil() {
+                self.check_type_for_ffi_and_report_errors(ret_hir.span, ret_ty);
             }
-            _ => intravisit::walk_ty(self, ty)
         }
     }
+
+    fn check_foreign_static(&mut self, id: ast::NodeId, span: Span) {
+        let def_id = self.cx.tcx.map.local_def_id(id);
+        let scheme = self.cx.tcx.lookup_item_type(def_id);
+        self.check_type_for_ffi_and_report_errors(span, scheme.ty);
+    }
 }
 
 #[derive(Copy, Clone)]
@@ -662,29 +656,17 @@ impl LintPass for ImproperCTypes {
 
 impl LateLintPass for ImproperCTypes {
     fn check_item(&mut self, cx: &LateContext, it: &hir::Item) {
-        fn check_ty(cx: &LateContext, ty: &hir::Ty) {
-            let mut vis = ImproperCTypesVisitor { cx: cx };
-            vis.visit_ty(ty);
-        }
-
-        fn check_foreign_fn(cx: &LateContext, decl: &hir::FnDecl) {
-            for input in &decl.inputs {
-                check_ty(cx, &input.ty);
-            }
-            if let hir::Return(ref ret_ty) = decl.output {
-                let tty = ast_ty_to_normalized(cx.tcx, ret_ty.id);
-                if !tty.is_nil() {
-                    check_ty(cx, &ret_ty);
-                }
-            }
-        }
-
+        let mut vis = ImproperCTypesVisitor { cx: cx };
         if let hir::ItemForeignMod(ref nmod) = it.node {
             if nmod.abi != Abi::RustIntrinsic && nmod.abi != Abi::PlatformIntrinsic {
                 for ni in &nmod.items {
                     match ni.node {
-                        hir::ForeignItemFn(ref decl, _) => check_foreign_fn(cx, &decl),
-                        hir::ForeignItemStatic(ref t, _) => check_ty(cx, &t)
+                        hir::ForeignItemFn(ref decl, _) => {
+                            vis.check_foreign_fn(ni.id, decl);
+                        }
+                        hir::ForeignItemStatic(ref ty, _) => {
+                            vis.check_foreign_static(ni.id, ty.span);
+                        }
                     }
                 }
             }
diff --git a/src/librustc_metadata/tydecode.rs b/src/librustc_metadata/tydecode.rs
index e9b23eb0458..cd9c2e828bd 100644
--- a/src/librustc_metadata/tydecode.rs
+++ b/src/librustc_metadata/tydecode.rs
@@ -144,22 +144,11 @@ impl<'a,'tcx> TyDecoder<'a,'tcx> {
     }
 
     pub fn parse_substs(&mut self) -> subst::Substs<'tcx> {
-        let regions = self.parse_region_substs();
+        let regions = self.parse_vec_per_param_space(|this| this.parse_region());
         let types = self.parse_vec_per_param_space(|this| this.parse_ty());
         subst::Substs { types: types, regions: regions }
     }
 
-    fn parse_region_substs(&mut self) -> subst::RegionSubsts {
-        match self.next() {
-            'e' => subst::ErasedRegions,
-            'n' => {
-                subst::NonerasedRegions(
-                    self.parse_vec_per_param_space(|this| this.parse_region()))
-            }
-            _ => panic!("parse_bound_region: bad input")
-        }
-    }
-
     fn parse_bound_region(&mut self) -> ty::BoundRegion {
         match self.next() {
             'a' => {
diff --git a/src/librustc_metadata/tyencode.rs b/src/librustc_metadata/tyencode.rs
index a6601e591ab..4718732c8a0 100644
--- a/src/librustc_metadata/tyencode.rs
+++ b/src/librustc_metadata/tyencode.rs
@@ -246,24 +246,12 @@ fn enc_vec_per_param_space<'a, 'tcx, T, F>(w: &mut Cursor<Vec<u8>>,
 
 pub fn enc_substs<'a, 'tcx>(w: &mut Cursor<Vec<u8>>, cx: &ctxt<'a, 'tcx>,
                             substs: &subst::Substs<'tcx>) {
-    enc_region_substs(w, cx, &substs.regions);
+    enc_vec_per_param_space(w, cx, &substs.regions,
+                            |w, cx, &r| enc_region(w, cx, r));
     enc_vec_per_param_space(w, cx, &substs.types,
                             |w, cx, &ty| enc_ty(w, cx, ty));
 }
 
-fn enc_region_substs(w: &mut Cursor<Vec<u8>>, cx: &ctxt, substs: &subst::RegionSubsts) {
-    match *substs {
-        subst::ErasedRegions => {
-            write!(w, "e");
-        }
-        subst::NonerasedRegions(ref regions) => {
-            write!(w, "n");
-            enc_vec_per_param_space(w, cx, regions,
-                                    |w, cx, &r| enc_region(w, cx, r));
-        }
-    }
-}
-
 pub fn enc_region(w: &mut Cursor<Vec<u8>>, cx: &ctxt, r: ty::Region) {
     match r {
         ty::ReLateBound(id, br) => {
diff --git a/src/librustc_trans/trans/base.rs b/src/librustc_trans/trans/base.rs
index 1844c41760c..1d8daf9d86b 100644
--- a/src/librustc_trans/trans/base.rs
+++ b/src/librustc_trans/trans/base.rs
@@ -673,9 +673,11 @@ pub fn custom_coerce_unsize_info<'ccx, 'tcx>(ccx: &CrateContext<'ccx, 'tcx>,
                                              source_ty: Ty<'tcx>,
                                              target_ty: Ty<'tcx>)
                                              -> CustomCoerceUnsized {
-    let trait_substs = Substs::erased(subst::VecPerParamSpace::new(vec![target_ty],
-                                                                   vec![source_ty],
-                                                                   Vec::new()));
+    let trait_substs = Substs::new(subst::VecPerParamSpace::new(vec![target_ty],
+                                                                vec![source_ty],
+                                                                Vec::new()),
+                                   subst::VecPerParamSpace::empty());
+
     let trait_ref = ty::Binder(ty::TraitRef {
         def_id: ccx.tcx().lang_items.coerce_unsized_trait().unwrap(),
         substs: ccx.tcx().mk_substs(trait_substs)
@@ -1824,10 +1826,8 @@ pub fn trans_closure<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
     ccx.stats().n_closures.set(ccx.stats().n_closures.get() + 1);
 
     if collector::collecting_debug_information(ccx) {
-        ccx.record_translation_item_as_generated(TransItem::Fn(Instance {
-            def: def_id,
-            params: &param_substs.types
-        }))
+        ccx.record_translation_item_as_generated(
+            TransItem::Fn(Instance::new(def_id, param_substs)));
     }
 
     let _icx = push_ctxt("trans_closure");
@@ -2259,8 +2259,8 @@ pub fn trans_item(ccx: &CrateContext, item: &hir::Item) {
                 // compilation unit that references the item, so it will still get
                 // translated everywhere it's needed.
                 for (ref ccx, is_origin) in ccx.maybe_iter(!from_external && trans_everywhere) {
-                    let empty_substs = tcx.mk_substs(Substs::trans_empty());
                     let def_id = tcx.map.local_def_id(item.id);
+                    let empty_substs = ccx.empty_substs_for_def_id(def_id);
                     let llfn = Callee::def(ccx, def_id, empty_substs).reify(ccx).val;
                     trans_fn(ccx, &decl, &body, llfn, empty_substs, item.id);
                     set_global_section(ccx, llfn, item);
@@ -2298,8 +2298,8 @@ pub fn trans_item(ccx: &CrateContext, item: &hir::Item) {
                     if sig.generics.ty_params.is_empty() {
                         let trans_everywhere = attr::requests_inline(&impl_item.attrs);
                         for (ref ccx, is_origin) in ccx.maybe_iter(trans_everywhere) {
-                            let empty_substs = tcx.mk_substs(Substs::trans_empty());
                             let def_id = tcx.map.local_def_id(impl_item.id);
+                            let empty_substs = ccx.empty_substs_for_def_id(def_id);
                             let llfn = Callee::def(ccx, def_id, empty_substs).reify(ccx).val;
                             trans_fn(ccx, &sig.decl, body, llfn, empty_substs, impl_item.id);
                             update_linkage(ccx, llfn, Some(impl_item.id),
@@ -2389,7 +2389,7 @@ pub fn create_entry_wrapper(ccx: &CrateContext, sp: Span, main_llfn: ValueRef) {
                     Ok(id) => id,
                     Err(s) => ccx.sess().fatal(&s)
                 };
-                let empty_substs = ccx.tcx().mk_substs(Substs::trans_empty());
+                let empty_substs = ccx.tcx().mk_substs(Substs::empty());
                 let start_fn = Callee::def(ccx, start_def_id, empty_substs).reify(ccx).val;
                 let args = {
                     let opaque_rust_main =
diff --git a/src/librustc_trans/trans/callee.rs b/src/librustc_trans/trans/callee.rs
index 17d08cd6c2f..1013c5d64b6 100644
--- a/src/librustc_trans/trans/callee.rs
+++ b/src/librustc_trans/trans/callee.rs
@@ -383,7 +383,7 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
     let llfn = declare::define_internal_fn(ccx, &function_name, tuple_fn_ty);
 
     //
-    let empty_substs = tcx.mk_substs(Substs::trans_empty());
+    let empty_substs = tcx.mk_substs(Substs::empty());
     let (block_arena, fcx): (TypedArena<_>, FunctionContext);
     block_arena = TypedArena::new();
     fcx = FunctionContext::new(ccx, llfn, fn_ty, None, empty_substs, &block_arena);
diff --git a/src/librustc_trans/trans/closure.rs b/src/librustc_trans/trans/closure.rs
index 2036feb31a2..dbabc3f54c5 100644
--- a/src/librustc_trans/trans/closure.rs
+++ b/src/librustc_trans/trans/closure.rs
@@ -144,10 +144,7 @@ fn get_or_create_closure_declaration<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
     // duplicate declarations
     let tcx = ccx.tcx();
     let substs = tcx.erase_regions(substs);
-    let instance = Instance {
-        def: closure_id,
-        params: &substs.func_substs.types
-    };
+    let instance = Instance::new(closure_id, &substs.func_substs);
 
     if let Some(&llfn) = ccx.instances().borrow().get(&instance) {
         debug!("get_or_create_closure_declaration(): found closure {:?}: {:?}",
diff --git a/src/librustc_trans/trans/collector.rs b/src/librustc_trans/trans/collector.rs
index 2c996c032ca..ab8f7d6bec3 100644
--- a/src/librustc_trans/trans/collector.rs
+++ b/src/librustc_trans/trans/collector.rs
@@ -241,7 +241,7 @@ impl<'tcx> Hash for TransItem<'tcx> {
             TransItem::Fn(instance) => {
                 1u8.hash(s);
                 instance.def.hash(s);
-                (instance.params as *const _ as usize).hash(s);
+                (instance.substs as *const _ as usize).hash(s);
             }
             TransItem::Static(node_id) => {
                 2u8.hash(s);
@@ -285,7 +285,6 @@ fn collect_roots<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
             mode: mode,
             output: &mut roots,
             enclosing_item: None,
-            trans_empty_substs: ccx.tcx().mk_substs(Substs::trans_empty()),
         };
 
         ccx.tcx().map.krate().visit_all_items(&mut visitor);
@@ -331,10 +330,7 @@ fn collect_items_rec<'a, 'tcx: 'a>(ccx: &CrateContext<'a, 'tcx>,
                 ccx: ccx,
                 mir: &mir,
                 output: &mut neighbors,
-                param_substs: ccx.tcx().mk_substs(Substs {
-                    types: instance.params.clone(),
-                    regions: subst::ErasedRegions
-                })
+                param_substs: instance.substs
             };
 
             visitor.visit_mir(&mir);
@@ -437,7 +433,7 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
                 let exchange_malloc_fn_trans_item =
                     create_fn_trans_item(self.ccx,
                                          exchange_malloc_fn_def_id,
-                                         &Substs::trans_empty(),
+                                         &Substs::empty(),
                                          self.param_substs);
 
                 self.output.push(exchange_malloc_fn_trans_item);
@@ -569,8 +565,8 @@ fn find_drop_glue_neighbors<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
         let exchange_free_fn_trans_item =
             create_fn_trans_item(ccx,
                                  exchange_free_fn_def_id,
-                                 &Substs::trans_empty(),
-                                 &Substs::trans_empty());
+                                 &Substs::empty(),
+                                 &Substs::empty());
 
         output.push(exchange_free_fn_trans_item);
     }
@@ -592,7 +588,7 @@ fn find_drop_glue_neighbors<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                                    .unwrap();
 
         let self_type_substs = ccx.tcx().mk_substs(
-            Substs::trans_empty().with_self_ty(ty));
+            Substs::empty().with_self_ty(ty));
 
         let trait_ref = ty::TraitRef {
             def_id: drop_trait_def_id,
@@ -608,7 +604,7 @@ fn find_drop_glue_neighbors<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
             let trans_item = create_fn_trans_item(ccx,
                                                   destructor_did,
                                                   substs,
-                                                  &Substs::trans_empty());
+                                                  &Substs::empty());
             output.push(trans_item);
         }
     }
@@ -875,10 +871,9 @@ fn create_fn_trans_item<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                                                            fn_substs);
     let concrete_substs = ccx.tcx().erase_regions(&concrete_substs);
 
-    let trans_item = TransItem::Fn(Instance {
-        def: def_id,
-        params: &ccx.tcx().mk_substs(concrete_substs).types,
-    });
+    let trans_item =
+        TransItem::Fn(Instance::new(def_id,
+                                    &ccx.tcx().mk_substs(concrete_substs)));
 
     return trans_item;
 }
@@ -914,7 +909,7 @@ fn create_trans_items_for_vtable_methods<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                                 Some(create_fn_trans_item(ccx,
                                                           impl_method.method.def_id,
                                                           &impl_method.substs,
-                                                          &Substs::trans_empty()))
+                                                          &Substs::empty()))
                             } else {
                                 None
                             }
@@ -938,7 +933,6 @@ struct RootCollector<'b, 'a: 'b, 'tcx: 'a + 'b> {
     mode: TransItemCollectionMode,
     output: &'b mut Vec<TransItem<'tcx>>,
     enclosing_item: Option<&'tcx hir::Item>,
-    trans_empty_substs: &'tcx Substs<'tcx>
 }
 
 impl<'b, 'a, 'v> hir_visit::Visitor<'v> for RootCollector<'b, 'a, 'v> {
@@ -962,7 +956,6 @@ impl<'b, 'a, 'v> hir_visit::Visitor<'v> for RootCollector<'b, 'a, 'v> {
                 if self.mode == TransItemCollectionMode::Eager {
                     create_trans_items_for_default_impls(self.ccx,
                                                          item,
-                                                         self.trans_empty_substs,
                                                          self.output);
                 }
             }
@@ -1049,7 +1042,6 @@ impl<'b, 'a, 'v> hir_visit::Visitor<'v> for RootCollector<'b, 'a, 'v> {
 
 fn create_trans_items_for_default_impls<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                                                   item: &'tcx hir::Item,
-                                                  trans_empty_substs: &'tcx Substs<'tcx>,
                                                   output: &mut Vec<TransItem<'tcx>>) {
     match item.node {
         hir::ItemImpl(_,
@@ -1098,10 +1090,11 @@ fn create_trans_items_for_default_impls<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                     }
 
                     if can_have_local_instance(ccx, default_impl.def_id) {
+                        let empty_substs = ccx.tcx().mk_substs(ccx.tcx().erase_regions(mth.substs));
                         let item = create_fn_trans_item(ccx,
                                                         default_impl.def_id,
                                                         callee_substs,
-                                                        trans_empty_substs);
+                                                        empty_substs);
                         output.push(item);
                     }
                 }
@@ -1328,7 +1321,7 @@ fn push_instance_as_string<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                                      instance: Instance<'tcx>,
                                      output: &mut String) {
     push_item_name(ccx, instance.def, output);
-    push_type_params(ccx, instance.params, &[], output);
+    push_type_params(ccx, &instance.substs.types, &[], output);
 }
 
 fn def_id_to_string(ccx: &CrateContext, def_id: DefId) -> String {
@@ -1386,7 +1379,7 @@ impl<'tcx> TransItem<'tcx> {
             TransItem::Fn(instance) => {
                 format!("Fn({:?}, {})",
                          instance.def,
-                         instance.params as *const _ as usize)
+                         instance.substs as *const _ as usize)
             }
             TransItem::Static(id) => {
                 format!("Static({:?})", id)
diff --git a/src/librustc_trans/trans/consts.rs b/src/librustc_trans/trans/consts.rs
index a1ba05840a1..7e6b2496910 100644
--- a/src/librustc_trans/trans/consts.rs
+++ b/src/librustc_trans/trans/consts.rs
@@ -272,7 +272,7 @@ fn get_const_val<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                            param_substs: &'tcx Substs<'tcx>)
                            -> Result<ValueRef, ConstEvalFailure> {
     let expr = get_const_expr(ccx, def_id, ref_expr, param_substs);
-    let empty_substs = ccx.tcx().mk_substs(Substs::trans_empty());
+    let empty_substs = ccx.tcx().mk_substs(Substs::empty());
     match get_const_expr_as_global(ccx, expr, ConstQualif::empty(), empty_substs, TrueConst::Yes) {
         Err(Runtime(err)) => {
             ccx.tcx().sess.span_err(expr.span, &err.description());
@@ -1148,7 +1148,7 @@ pub fn trans_static(ccx: &CrateContext,
         let def_id = ccx.tcx().map.local_def_id(id);
         let datum = get_static(ccx, def_id);
 
-        let empty_substs = ccx.tcx().mk_substs(Substs::trans_empty());
+        let empty_substs = ccx.tcx().mk_substs(Substs::empty());
         let (v, _) = const_expr(
             ccx,
             expr,
diff --git a/src/librustc_trans/trans/context.rs b/src/librustc_trans/trans/context.rs
index 8f5572f5c4e..046e05dd071 100644
--- a/src/librustc_trans/trans/context.rs
+++ b/src/librustc_trans/trans/context.rs
@@ -28,7 +28,7 @@ use trans::mir::CachedMir;
 use trans::monomorphize::Instance;
 use trans::collector::{TransItem, TransItemState};
 use trans::type_::{Type, TypeNames};
-use middle::subst::Substs;
+use middle::subst::{Substs, VecPerParamSpace};
 use middle::ty::{self, Ty, TyCtxt};
 use session::config::NoDebugInfo;
 use session::Session;
@@ -551,7 +551,6 @@ impl<'b, 'tcx> CrateContext<'b, 'tcx> {
         self.local
     }
 
-
     /// Get a (possibly) different `CrateContext` from the same
     /// `SharedCrateContext`.
     pub fn rotate(&self) -> CrateContext<'b, 'tcx> {
@@ -856,6 +855,21 @@ impl<'b, 'tcx> CrateContext<'b, 'tcx> {
             codegen_items.insert(cgi, TransItemState::NotPredictedButGenerated);
         }
     }
+
+    /// Given the def-id of some item that has no type parameters, make
+    /// a suitable "empty substs" for it.
+    pub fn empty_substs_for_def_id(&self, item_def_id: DefId) -> &'tcx Substs<'tcx> {
+        let scheme = self.tcx().lookup_item_type(item_def_id);
+        self.empty_substs_for_scheme(&scheme)
+    }
+
+    pub fn empty_substs_for_scheme(&self, scheme: &ty::TypeScheme<'tcx>)
+                                   -> &'tcx Substs<'tcx> {
+        assert!(scheme.generics.types.is_empty());
+        self.tcx().mk_substs(
+            Substs::new(VecPerParamSpace::empty(),
+                        scheme.generics.regions.map(|_| ty::ReStatic)))
+    }
 }
 
 pub struct TypeOfDepthLock<'a, 'tcx: 'a>(&'a LocalCrateContext<'tcx>);
diff --git a/src/librustc_trans/trans/expr.rs b/src/librustc_trans/trans/expr.rs
index abcd703f33b..fe98fa29021 100644
--- a/src/librustc_trans/trans/expr.rs
+++ b/src/librustc_trans/trans/expr.rs
@@ -176,7 +176,7 @@ pub fn trans_into<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                 hir::ExprPath(..) => {
                     match bcx.def(expr.id) {
                         Def::Const(did) | Def::AssociatedConst(did) => {
-                            let empty_substs = bcx.tcx().mk_substs(Substs::trans_empty());
+                            let empty_substs = bcx.tcx().mk_substs(Substs::empty());
                             let const_expr = consts::get_const_expr(bcx.ccx(), did, expr,
                                                                     empty_substs);
                             // Temporarily get cleanup scopes out of the way,
diff --git a/src/librustc_trans/trans/glue.rs b/src/librustc_trans/trans/glue.rs
index 4ca5fb07c98..de4b1ba858a 100644
--- a/src/librustc_trans/trans/glue.rs
+++ b/src/librustc_trans/trans/glue.rs
@@ -267,7 +267,7 @@ fn get_drop_glue_core<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 
     let _s = StatRecorder::new(ccx, format!("drop {:?}", t));
 
-    let empty_substs = tcx.mk_substs(Substs::trans_empty());
+    let empty_substs = ccx.tcx().mk_substs(Substs::empty());
     let (arena, fcx): (TypedArena<_>, FunctionContext);
     arena = TypedArena::new();
     fcx = FunctionContext::new(ccx, llfn, fn_ty, None, empty_substs, &arena);
@@ -358,7 +358,7 @@ fn trans_struct_drop<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 
     let trait_ref = ty::Binder(ty::TraitRef {
         def_id: tcx.lang_items.drop_trait().unwrap(),
-        substs: tcx.mk_substs(Substs::trans_empty().with_self_ty(t))
+        substs: tcx.mk_substs(Substs::empty().with_self_ty(t))
     });
     let vtbl = match fulfill_obligation(bcx.ccx(), DUMMY_SP, trait_ref) {
         traits::VtableImpl(data) => data,
diff --git a/src/librustc_trans/trans/inline.rs b/src/librustc_trans/trans/inline.rs
index ad32870444a..530b99cba92 100644
--- a/src/librustc_trans/trans/inline.rs
+++ b/src/librustc_trans/trans/inline.rs
@@ -70,7 +70,7 @@ fn instantiate_inline(ccx: &CrateContext, fn_id: DefId) -> Option<DefId> {
                         // performance.
                         AvailableExternallyLinkage
                     };
-                    let empty_substs = tcx.mk_substs(Substs::trans_empty());
+                    let empty_substs = tcx.mk_substs(Substs::empty());
                     let def_id = tcx.map.local_def_id(item.id);
                     let llfn = Callee::def(ccx, def_id, empty_substs).reify(ccx).val;
                     SetLinkage(llfn, linkage);
@@ -144,8 +144,8 @@ fn instantiate_inline(ccx: &CrateContext, fn_id: DefId) -> Option<DefId> {
                 let impl_tpt = tcx.lookup_item_type(impl_did);
                 if impl_tpt.generics.types.is_empty() &&
                         sig.generics.ty_params.is_empty() {
-                    let empty_substs = tcx.mk_substs(Substs::trans_empty());
                     let def_id = tcx.map.local_def_id(impl_item.id);
+                    let empty_substs = ccx.empty_substs_for_def_id(def_id);
                     let llfn = Callee::def(ccx, def_id, empty_substs).reify(ccx).val;
                     trans_fn(ccx,
                              &sig.decl,
diff --git a/src/librustc_trans/trans/intrinsic.rs b/src/librustc_trans/trans/intrinsic.rs
index 05b8086de13..9bc07c6cd86 100644
--- a/src/librustc_trans/trans/intrinsic.rs
+++ b/src/librustc_trans/trans/intrinsic.rs
@@ -1298,7 +1298,7 @@ fn gen_fn<'a, 'tcx>(fcx: &FunctionContext<'a, 'tcx>,
         sig: ty::Binder(sig)
     });
     let llfn = declare::define_internal_fn(ccx, name, rust_fn_ty);
-    let empty_substs = ccx.tcx().mk_substs(Substs::trans_empty());
+    let empty_substs = ccx.tcx().mk_substs(Substs::empty());
     let (fcx, block_arena);
     block_arena = TypedArena::new();
     fcx = FunctionContext::new(ccx, llfn, fn_ty, None, empty_substs, &block_arena);
diff --git a/src/librustc_trans/trans/meth.rs b/src/librustc_trans/trans/meth.rs
index 30560ec05c4..ae619ceb30b 100644
--- a/src/librustc_trans/trans/meth.rs
+++ b/src/librustc_trans/trans/meth.rs
@@ -15,7 +15,7 @@ use back::link;
 use llvm::{ValueRef, get_params};
 use middle::def_id::DefId;
 use middle::infer;
-use middle::subst::{Subst, Substs};
+use middle::subst::{FnSpace, Subst, Substs};
 use middle::subst;
 use middle::traits::{self, ProjectionMode};
 use trans::abi::FnType;
@@ -92,7 +92,7 @@ pub fn trans_object_shim<'a, 'tcx>(ccx: &'a CrateContext<'a, 'tcx>,
     let function_name = link::mangle_internal_name_by_type_and_seq(ccx, method_ty, "object_shim");
     let llfn = declare::define_internal_fn(ccx, &function_name, method_ty);
 
-    let empty_substs = tcx.mk_substs(Substs::trans_empty());
+    let empty_substs = tcx.mk_substs(Substs::empty());
     let (block_arena, fcx): (TypedArena<_>, FunctionContext);
     block_arena = TypedArena::new();
     fcx = FunctionContext::new(ccx, llfn, fn_ty, None, empty_substs, &block_arena);
@@ -268,9 +268,17 @@ pub fn get_vtable_methods<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
             debug!("get_vtable_methods: trait_method_type={:?}",
                    trait_method_type);
 
+            // the method may have some early-bound lifetimes, add
+            // regions for those
+            let num_dummy_regions = trait_method_type.generics.regions.len(FnSpace);
+            let dummy_regions = vec![ty::ReStatic; num_dummy_regions];
+            let method_substs = substs.clone()
+                                      .with_method(vec![], dummy_regions);
+            let method_substs = tcx.mk_substs(method_substs);
+
             // The substitutions we have are on the impl, so we grab
             // the method type from the impl to substitute into.
-            let mth = get_impl_method(tcx, impl_id, substs, name);
+            let mth = get_impl_method(tcx, impl_id, method_substs, name);
 
             debug!("get_vtable_methods: mth={:?}", mth);
 
diff --git a/src/librustc_trans/trans/monomorphize.rs b/src/librustc_trans/trans/monomorphize.rs
index 2e75439ffc3..63fb8c5fb5e 100644
--- a/src/librustc_trans/trans/monomorphize.rs
+++ b/src/librustc_trans/trans/monomorphize.rs
@@ -45,10 +45,7 @@ pub fn monomorphic_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 
     let _icx = push_ctxt("monomorphic_fn");
 
-    let instance = Instance {
-        def: fn_id,
-        params: &psubsts.types
-    };
+    let instance = Instance::new(fn_id, psubsts);
 
     let item_ty = ccx.tcx().lookup_item_type(fn_id).ty;
 
@@ -179,26 +176,24 @@ pub fn monomorphic_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
 pub struct Instance<'tcx> {
     pub def: DefId,
-    pub params: &'tcx subst::VecPerParamSpace<Ty<'tcx>>
+    pub substs: &'tcx Substs<'tcx>,
 }
 
 impl<'tcx> fmt::Display for Instance<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        let substs = Substs {
-            types: self.params.clone(),
-            regions: subst::ErasedRegions
-        };
-        ppaux::parameterized(f, &substs, self.def, ppaux::Ns::Value, &[],
+        ppaux::parameterized(f, &self.substs, self.def, ppaux::Ns::Value, &[],
                              |tcx| tcx.lookup_item_type(self.def).generics)
     }
 }
 
 impl<'tcx> Instance<'tcx> {
+    pub fn new(def_id: DefId, substs: &'tcx Substs<'tcx>)
+               -> Instance<'tcx> {
+        assert!(substs.regions.iter().all(|&r| r == ty::ReStatic));
+        Instance { def: def_id, substs: substs }
+    }
     pub fn mono(tcx: &TyCtxt<'tcx>, def_id: DefId) -> Instance<'tcx> {
-        Instance {
-            def: def_id,
-            params: &tcx.mk_substs(Substs::trans_empty()).types
-        }
+        Instance::new(def_id, &tcx.mk_substs(Substs::empty()))
     }
 }
 
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 67bd79bb57e..159ff90b509 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -411,7 +411,7 @@ fn create_substs_for_ast_path<'tcx>(
            decl_generics, self_ty, types_provided,
            region_substs);
 
-    assert_eq!(region_substs.regions().len(TypeSpace), decl_generics.regions.len(TypeSpace));
+    assert_eq!(region_substs.regions.len(TypeSpace), decl_generics.regions.len(TypeSpace));
     assert!(region_substs.types.is_empty());
 
     // Convert the type parameters supplied by the user.
diff --git a/src/librustc_typeck/check/compare_method.rs b/src/librustc_typeck/check/compare_method.rs
index ee5dbd032f3..3e59f0ba73a 100644
--- a/src/librustc_typeck/check/compare_method.rs
+++ b/src/librustc_typeck/check/compare_method.rs
@@ -180,7 +180,7 @@ pub fn compare_impl_method<'tcx>(tcx: &TyCtxt<'tcx>,
         trait_to_impl_substs
         .subst(tcx, impl_to_skol_substs)
         .with_method(impl_to_skol_substs.types.get_slice(subst::FnSpace).to_vec(),
-                     impl_to_skol_substs.regions().get_slice(subst::FnSpace).to_vec());
+                     impl_to_skol_substs.regions.get_slice(subst::FnSpace).to_vec());
     debug!("compare_impl_method: trait_to_skol_substs={:?}",
            trait_to_skol_substs);
 
@@ -439,7 +439,7 @@ pub fn compare_const_impl<'tcx>(tcx: &TyCtxt<'tcx>,
         trait_to_impl_substs
         .subst(tcx, impl_to_skol_substs)
         .with_method(impl_to_skol_substs.types.get_slice(subst::FnSpace).to_vec(),
-                     impl_to_skol_substs.regions().get_slice(subst::FnSpace).to_vec());
+                     impl_to_skol_substs.regions.get_slice(subst::FnSpace).to_vec());
     debug!("compare_const_impl: trait_to_skol_substs={:?}",
            trait_to_skol_substs);
 
diff --git a/src/librustc_typeck/check/method/confirm.rs b/src/librustc_typeck/check/method/confirm.rs
index f4268deee37..aa4e1d0b529 100644
--- a/src/librustc_typeck/check/method/confirm.rs
+++ b/src/librustc_typeck/check/method/confirm.rs
@@ -334,7 +334,7 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
                     .generics.regions.get_slice(subst::FnSpace));
 
         let subst::Substs { types, regions } = substs;
-        let regions = regions.map(|r| r.with_slice(subst::FnSpace, &method_regions));
+        let regions = regions.with_slice(subst::FnSpace, &method_regions);
         let mut final_substs = subst::Substs { types: types, regions: regions };
 
         if num_supplied_types == 0 {
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index b522de8d135..5f7f9703b10 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -505,11 +505,11 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                 assert_eq!(m.generics.types.get_slice(subst::TypeSpace).len(),
                            trait_ref.substs.types.get_slice(subst::TypeSpace).len());
                 assert_eq!(m.generics.regions.get_slice(subst::TypeSpace).len(),
-                           trait_ref.substs.regions().get_slice(subst::TypeSpace).len());
+                           trait_ref.substs.regions.get_slice(subst::TypeSpace).len());
                 assert_eq!(m.generics.types.get_slice(subst::SelfSpace).len(),
                            trait_ref.substs.types.get_slice(subst::SelfSpace).len());
                 assert_eq!(m.generics.regions.get_slice(subst::SelfSpace).len(),
-                           trait_ref.substs.regions().get_slice(subst::SelfSpace).len());
+                           trait_ref.substs.regions.get_slice(subst::SelfSpace).len());
             }
 
             // Because this trait derives from a where-clause, it
@@ -1194,7 +1194,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
         // method yet. So create fresh variables here for those too,
         // if there are any.
         assert_eq!(substs.types.len(subst::FnSpace), 0);
-        assert_eq!(substs.regions().len(subst::FnSpace), 0);
+        assert_eq!(substs.regions.len(subst::FnSpace), 0);
 
         if self.mode == Mode::Path {
             return impl_ty;
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 903fc458d81..6eb663e6047 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -4431,7 +4431,7 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
         assert_eq!(substs.types.len(space), type_defs.len(space));
 
         adjust_region_parameters(fcx, span, space, region_defs, &mut substs);
-        assert_eq!(substs.regions().len(space), region_defs.len(space));
+        assert_eq!(substs.regions.len(space), region_defs.len(space));
     }
 
     // The things we are substituting into the type should not contain
@@ -4459,7 +4459,7 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
         let impl_scheme = fcx.tcx().lookup_item_type(impl_def_id);
         assert_eq!(substs.types.len(subst::TypeSpace),
                    impl_scheme.generics.types.len(subst::TypeSpace));
-        assert_eq!(substs.regions().len(subst::TypeSpace),
+        assert_eq!(substs.regions.len(subst::TypeSpace),
                    impl_scheme.generics.regions.len(subst::TypeSpace));
 
         let impl_ty = fcx.instantiate_type_scheme(span, &substs, &impl_scheme.ty);
@@ -4550,11 +4550,11 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 
         {
             let region_count = region_defs.len(space);
-            assert_eq!(substs.regions().len(space), 0);
+            assert_eq!(substs.regions.len(space), 0);
             for (i, lifetime) in data.lifetimes.iter().enumerate() {
                 let r = ast_region_to_region(fcx.tcx(), lifetime);
                 if i < region_count {
-                    substs.mut_regions().push(space, r);
+                    substs.regions.push(space, r);
                 } else if i == region_count {
                     span_err!(fcx.tcx().sess, lifetime.span, E0088,
                         "too many lifetime parameters provided: \
@@ -4563,7 +4563,7 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
                         if region_count == 1 {""} else {"s"},
                         data.lifetimes.len(),
                         if data.lifetimes.len() == 1 {""} else {"s"});
-                    substs.mut_regions().truncate(space, 0);
+                    substs.regions.truncate(space, 0);
                     break;
                 }
             }
@@ -4686,7 +4686,7 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
         defs: &VecPerParamSpace<ty::RegionParameterDef>,
         substs: &mut Substs)
     {
-        let provided_len = substs.mut_regions().len(space);
+        let provided_len = substs.regions.len(space);
         let desired = defs.get_slice(space);
 
         // Enforced by `push_explicit_parameters_from_segment_to_substs()`.
@@ -4694,7 +4694,7 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 
         // If nothing was provided, just use inference variables.
         if provided_len == 0 {
-            substs.mut_regions().replace(
+            substs.regions.replace(
                 space,
                 fcx.infcx().region_vars_for_defs(span, desired));
             return;
@@ -4715,7 +4715,7 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
             provided_len,
             if provided_len == 1 {""} else {"s"});
 
-        substs.mut_regions().replace(
+        substs.regions.replace(
             space,
             fcx.infcx().region_vars_for_defs(span, desired));
     }
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index e428fc927f0..fb4870bce87 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -1496,7 +1496,7 @@ pub fn substs_wf_in_scope<'a,'tcx>(rcx: &mut Rcx<'a,'tcx>,
 
     let origin = infer::ParameterInScope(origin, expr_span);
 
-    for &region in substs.regions() {
+    for &region in &substs.regions {
         rcx.fcx.mk_subr(origin.clone(), expr_region, region);
     }
 
@@ -1624,7 +1624,7 @@ fn projection_must_outlive<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
     // edges, which winds up enforcing the same condition.
     let needs_infer = {
         projection_ty.trait_ref.substs.types.iter().any(|t| t.needs_infer()) ||
-            projection_ty.trait_ref.substs.regions().iter().any(|r| r.needs_infer())
+            projection_ty.trait_ref.substs.regions.iter().any(|r| r.needs_infer())
     };
     if env_bounds.is_empty() && needs_infer {
         debug!("projection_must_outlive: no declared bounds");
@@ -1633,7 +1633,7 @@ fn projection_must_outlive<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
             type_must_outlive(rcx, origin.clone(), component_ty, region);
         }
 
-        for &r in projection_ty.trait_ref.substs.regions() {
+        for &r in &projection_ty.trait_ref.substs.regions {
             rcx.fcx.mk_subr(origin.clone(), region, r);
         }
 
@@ -1650,7 +1650,7 @@ fn projection_must_outlive<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
     if !env_bounds.is_empty() && env_bounds[1..].iter().all(|b| *b == env_bounds[0]) {
         let unique_bound = env_bounds[0];
         debug!("projection_must_outlive: unique declared bound = {:?}", unique_bound);
-        if projection_ty.trait_ref.substs.regions()
+        if projection_ty.trait_ref.substs.regions
                                          .iter()
                                          .any(|r| env_bounds.contains(r))
         {
diff --git a/src/librustc_typeck/constrained_type_params.rs b/src/librustc_typeck/constrained_type_params.rs
index 907ee15c41b..4446063e0c7 100644
--- a/src/librustc_typeck/constrained_type_params.rs
+++ b/src/librustc_typeck/constrained_type_params.rs
@@ -81,7 +81,7 @@ fn parameters_for_type_shallow<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
 }
 
 fn parameters_for_regions_in_substs(substs: &subst::Substs) -> Vec<Parameter> {
-    substs.regions()
+    substs.regions
           .iter()
           .filter_map(|r| parameters_for_region(r))
           .collect()
diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs
index aecc588c3e2..5c74e9096f3 100644
--- a/src/librustc_typeck/variance/constraints.rs
+++ b/src/librustc_typeck/variance/constraints.rs
@@ -477,7 +477,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
                 self.declared_variance(p.def_id, def_id,
                                        RegionParam, p.space, p.index as usize);
             let variance_i = self.xform(variance, variance_decl);
-            let substs_r = *substs.regions().get(p.space, p.index as usize);
+            let substs_r = *substs.regions.get(p.space, p.index as usize);
             self.add_constraints_from_region(generics, substs_r, variance_i);
         }
     }
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index cca027ca17a..15aeca9204a 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -606,7 +606,7 @@ impl<'tcx> Clean<(Vec<TyParamBound>, Vec<TypeBinding>)> for ty::ExistentialBound
 
 fn external_path_params(cx: &DocContext, trait_did: Option<DefId>,
                         bindings: Vec<TypeBinding>, substs: &subst::Substs) -> PathParameters {
-    let lifetimes = substs.regions().get_slice(subst::TypeSpace)
+    let lifetimes = substs.regions.get_slice(subst::TypeSpace)
                     .iter()
                     .filter_map(|v| v.clean(cx))
                     .collect();
@@ -739,7 +739,7 @@ impl<'tcx> Clean<TyParamBound> for ty::TraitRef<'tcx> {
 impl<'tcx> Clean<Option<Vec<TyParamBound>>> for subst::Substs<'tcx> {
     fn clean(&self, cx: &DocContext) -> Option<Vec<TyParamBound>> {
         let mut v = Vec::new();
-        v.extend(self.regions().iter().filter_map(|r| r.clean(cx)).map(RegionBound));
+        v.extend(self.regions.iter().filter_map(|r| r.clean(cx)).map(RegionBound));
         v.extend(self.types.iter().map(|t| TraitBound(PolyTrait {
             trait_: t.clean(cx),
             lifetimes: vec![]