auto merge of #14702 : nikomatsakis/rust/issue-5527-namespace-substs-b, r=pnkfelix

Separate out initial refactorings for PR #14604

71 files changed, 1019 insertions, 934 deletions

diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 17e659e5391..1b17cfb1bae 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -46,6 +46,7 @@ extern crate time;
 extern crate log;
 
 pub mod middle {
+    pub mod def;
     pub mod trans;
     pub mod ty;
     pub mod ty_fold;
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 30b40369c10..6469462734e 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -22,6 +22,7 @@ use metadata::tydecode::{parse_ty_data, parse_def_id,
                          parse_type_param_def_data,
                          parse_bare_fn_ty_data, parse_trait_ref_data};
 use middle::lang_items;
+use middle::def;
 use middle::ty::{ImplContainer, TraitContainer};
 use middle::ty;
 use middle::typeck;
@@ -333,11 +334,11 @@ fn item_to_def_like(item: ebml::Doc, did: ast::DefId, cnum: ast::CrateNum)
     -> DefLike {
     let fam = item_family(item);
     match fam {
-        ImmStatic => DlDef(ast::DefStatic(did, false)),
-        MutStatic => DlDef(ast::DefStatic(did, true)),
-        Struct    => DlDef(ast::DefStruct(did)),
-        UnsafeFn  => DlDef(ast::DefFn(did, ast::UnsafeFn)),
-        Fn        => DlDef(ast::DefFn(did, ast::NormalFn)),
+        ImmStatic => DlDef(def::DefStatic(did, false)),
+        MutStatic => DlDef(def::DefStatic(did, true)),
+        Struct    => DlDef(def::DefStruct(did)),
+        UnsafeFn  => DlDef(def::DefFn(did, ast::UnsafeFn)),
+        Fn        => DlDef(def::DefFn(did, ast::NormalFn)),
         StaticMethod | UnsafeStaticMethod => {
             let fn_style = if fam == UnsafeStaticMethod { ast::UnsafeFn } else
                 { ast::NormalFn };
@@ -348,27 +349,27 @@ fn item_to_def_like(item: ebml::Doc, did: ast::DefId, cnum: ast::CrateNum)
             // a trait_method_sort.
             let provenance = if reader::maybe_get_doc(
                   item, tag_item_trait_method_sort).is_some() {
-                ast::FromTrait(item_reqd_and_translated_parent_item(cnum,
+                def::FromTrait(item_reqd_and_translated_parent_item(cnum,
                                                                     item))
             } else {
-                ast::FromImpl(item_reqd_and_translated_parent_item(cnum,
+                def::FromImpl(item_reqd_and_translated_parent_item(cnum,
                                                                    item))
             };
-            DlDef(ast::DefStaticMethod(did, provenance, fn_style))
+            DlDef(def::DefStaticMethod(did, provenance, fn_style))
         }
-        Type | ForeignType => DlDef(ast::DefTy(did)),
-        Mod => DlDef(ast::DefMod(did)),
-        ForeignMod => DlDef(ast::DefForeignMod(did)),
+        Type | ForeignType => DlDef(def::DefTy(did)),
+        Mod => DlDef(def::DefMod(did)),
+        ForeignMod => DlDef(def::DefForeignMod(did)),
         StructVariant => {
             let enum_did = item_reqd_and_translated_parent_item(cnum, item);
-            DlDef(ast::DefVariant(enum_did, did, true))
+            DlDef(def::DefVariant(enum_did, did, true))
         }
         TupleVariant => {
             let enum_did = item_reqd_and_translated_parent_item(cnum, item);
-            DlDef(ast::DefVariant(enum_did, did, false))
+            DlDef(def::DefVariant(enum_did, did, false))
         }
-        Trait => DlDef(ast::DefTrait(did)),
-        Enum => DlDef(ast::DefTy(did)),
+        Trait => DlDef(def::DefTrait(did)),
+        Enum => DlDef(def::DefTy(did)),
         Impl => DlImpl(did),
         PublicField | InheritedField => DlField,
     }
@@ -459,7 +460,7 @@ pub fn get_symbol(data: &[u8], id: ast::NodeId) -> String {
 // Something that a name can resolve to.
 #[deriving(Clone)]
 pub enum DefLike {
-    DlDef(ast::Def),
+    DlDef(def::Def),
     DlImpl(ast::DefId),
     DlField
 }
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index 61dfde38c28..2cc06f7a32d 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -1631,7 +1631,7 @@ impl<'a,'b,'c> Visitor<()> for ImplVisitor<'a,'b,'c> {
             ItemImpl(_, Some(ref trait_ref), _, _) => {
                 let def_map = &self.ecx.tcx.def_map;
                 let trait_def = def_map.borrow().get_copy(&trait_ref.ref_id);
-                let def_id = ast_util::def_id_of_def(trait_def);
+                let def_id = trait_def.def_id();
 
                 // Load eagerly if this is an implementation of the Drop trait
                 // or if the trait is not defined in this crate.
diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index f8d041bc923..a39be31c4b5 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -16,6 +16,7 @@
 
 #![allow(non_camel_case_types)]
 
+use middle::subst;
 use middle::ty;
 
 use std::rc::Rc;
@@ -25,7 +26,6 @@ use std::uint;
 use syntax::abi;
 use syntax::ast;
 use syntax::ast::*;
-use syntax::owned_slice::OwnedSlice;
 use syntax::parse::token;
 
 // Compact string representation for ty::t values. API ty_str &
@@ -133,7 +133,7 @@ pub fn parse_trait_ref_data(data: &[u8], crate_num: ast::CrateNum, pos: uint, tc
 }
 
 pub fn parse_substs_data(data: &[u8], crate_num: ast::CrateNum, pos: uint, tcx: &ty::ctxt,
-                         conv: conv_did) -> ty::substs {
+                         conv: conv_did) -> subst::Substs {
     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
     parse_substs(&mut st, conv)
 }
@@ -162,7 +162,7 @@ fn parse_trait_store(st: &mut PState, conv: conv_did) -> ty::TraitStore {
     }
 }
 
-fn parse_substs(st: &mut PState, conv: conv_did) -> ty::substs {
+fn parse_substs(st: &mut PState, conv: conv_did) -> subst::Substs {
     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)) );
@@ -172,16 +172,16 @@ fn parse_substs(st: &mut PState, conv: conv_did) -> ty::substs {
     while peek(st) != ']' { params.push(parse_ty(st, |x,y| conv(x,y))); }
     st.pos = st.pos + 1u;
 
-    return ty::substs {
+    return subst::Substs {
         regions: regions,
         self_ty: self_ty,
         tps: params
     };
 }
 
-fn parse_region_substs(st: &mut PState, conv: conv_did) -> ty::RegionSubsts {
+fn parse_region_substs(st: &mut PState, conv: conv_did) -> subst::RegionSubsts {
     match next(st) {
-        'e' => ty::ErasedRegions,
+        'e' => subst::ErasedRegions,
         'n' => {
             let mut regions = vec!();
             while peek(st) != '.' {
@@ -189,7 +189,7 @@ fn parse_region_substs(st: &mut PState, conv: conv_did) -> ty::RegionSubsts {
                 regions.push(r);
             }
             assert_eq!(next(st), '.');
-            ty::NonerasedRegions(OwnedSlice::from_vec(regions))
+            subst::NonerasedRegions(regions)
         }
         _ => fail!("parse_bound_region: bad input")
     }
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index 5d2d6ed5815..f48dbecc530 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -17,6 +17,7 @@ use std::cell::RefCell;
 use std::collections::HashMap;
 use std::io::MemWriter;
 
+use middle::subst;
 use middle::ty::param_ty;
 use middle::ty;
 
@@ -96,7 +97,7 @@ fn enc_opt<T>(w: &mut MemWriter, t: Option<T>, enc_f: |&mut MemWriter, T|) {
     }
 }
 
-pub fn enc_substs(w: &mut MemWriter, cx: &ctxt, substs: &ty::substs) {
+pub fn enc_substs(w: &mut MemWriter, cx: &ctxt, substs: &subst::Substs) {
     enc_region_substs(w, cx, &substs.regions);
     enc_opt(w, substs.self_ty, |w, t| enc_ty(w, cx, t));
     mywrite!(w, "[");
@@ -104,12 +105,12 @@ pub fn enc_substs(w: &mut MemWriter, cx: &ctxt, substs: &ty::substs) {
     mywrite!(w, "]");
 }
 
-fn enc_region_substs(w: &mut MemWriter, cx: &ctxt, substs: &ty::RegionSubsts) {
+fn enc_region_substs(w: &mut MemWriter, cx: &ctxt, substs: &subst::RegionSubsts) {
     match *substs {
-        ty::ErasedRegions => {
+        subst::ErasedRegions => {
             mywrite!(w, "e");
         }
-        ty::NonerasedRegions(ref regions) => {
+        subst::NonerasedRegions(ref regions) => {
             mywrite!(w, "n");
             for &r in regions.iter() {
                 enc_region(w, cx, r);
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index aec25071249..f0caf0e7fe8 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -16,6 +16,7 @@ use c = metadata::common;
 use cstore = metadata::cstore;
 use driver::session::Session;
 use metadata::decoder;
+use middle::def;
 use e = metadata::encoder;
 use middle::freevars::freevar_entry;
 use middle::region;
@@ -23,6 +24,7 @@ use metadata::tydecode;
 use metadata::tydecode::{DefIdSource, NominalType, TypeWithId, TypeParameter,
                          RegionParameter};
 use metadata::tyencode;
+use middle::subst;
 use middle::typeck::{MethodCall, MethodCallee, MethodOrigin};
 use middle::{ty, typeck};
 use util::ppaux::ty_to_str;
@@ -394,58 +396,58 @@ fn renumber_and_map_ast(xcx: &ExtendedDecodeContext,
 // ______________________________________________________________________
 // Encoding and decoding of ast::def
 
-fn decode_def(xcx: &ExtendedDecodeContext, doc: ebml::Doc) -> ast::Def {
+fn decode_def(xcx: &ExtendedDecodeContext, doc: ebml::Doc) -> def::Def {
     let mut dsr = reader::Decoder::new(doc);
-    let def: ast::Def = Decodable::decode(&mut dsr).unwrap();
+    let def: def::Def = Decodable::decode(&mut dsr).unwrap();
     def.tr(xcx)
 }
 
-impl tr for ast::Def {
-    fn tr(&self, xcx: &ExtendedDecodeContext) -> ast::Def {
+impl tr for def::Def {
+    fn tr(&self, xcx: &ExtendedDecodeContext) -> def::Def {
         match *self {
-          ast::DefFn(did, p) => ast::DefFn(did.tr(xcx), p),
-          ast::DefStaticMethod(did, wrapped_did2, p) => {
-            ast::DefStaticMethod(did.tr(xcx),
+          def::DefFn(did, p) => def::DefFn(did.tr(xcx), p),
+          def::DefStaticMethod(did, wrapped_did2, p) => {
+            def::DefStaticMethod(did.tr(xcx),
                                    match wrapped_did2 {
-                                    ast::FromTrait(did2) => {
-                                        ast::FromTrait(did2.tr(xcx))
+                                    def::FromTrait(did2) => {
+                                        def::FromTrait(did2.tr(xcx))
                                     }
-                                    ast::FromImpl(did2) => {
-                                        ast::FromImpl(did2.tr(xcx))
+                                    def::FromImpl(did2) => {
+                                        def::FromImpl(did2.tr(xcx))
                                     }
                                    },
                                    p)
           }
-          ast::DefMethod(did0, did1) => {
-            ast::DefMethod(did0.tr(xcx), did1.map(|did1| did1.tr(xcx)))
+          def::DefMethod(did0, did1) => {
+            def::DefMethod(did0.tr(xcx), did1.map(|did1| did1.tr(xcx)))
           }
-          ast::DefSelfTy(nid) => { ast::DefSelfTy(xcx.tr_id(nid)) }
-          ast::DefMod(did) => { ast::DefMod(did.tr(xcx)) }
-          ast::DefForeignMod(did) => { ast::DefForeignMod(did.tr(xcx)) }
-          ast::DefStatic(did, m) => { ast::DefStatic(did.tr(xcx), m) }
-          ast::DefArg(nid, b) => { ast::DefArg(xcx.tr_id(nid), b) }
-          ast::DefLocal(nid, b) => { ast::DefLocal(xcx.tr_id(nid), b) }
-          ast::DefVariant(e_did, v_did, is_s) => {
-            ast::DefVariant(e_did.tr(xcx), v_did.tr(xcx), is_s)
+          def::DefSelfTy(nid) => { def::DefSelfTy(xcx.tr_id(nid)) }
+          def::DefMod(did) => { def::DefMod(did.tr(xcx)) }
+          def::DefForeignMod(did) => { def::DefForeignMod(did.tr(xcx)) }
+          def::DefStatic(did, m) => { def::DefStatic(did.tr(xcx), m) }
+          def::DefArg(nid, b) => { def::DefArg(xcx.tr_id(nid), b) }
+          def::DefLocal(nid, b) => { def::DefLocal(xcx.tr_id(nid), b) }
+          def::DefVariant(e_did, v_did, is_s) => {
+            def::DefVariant(e_did.tr(xcx), v_did.tr(xcx), is_s)
           },
-          ast::DefTrait(did) => ast::DefTrait(did.tr(xcx)),
-          ast::DefTy(did) => ast::DefTy(did.tr(xcx)),
-          ast::DefPrimTy(p) => ast::DefPrimTy(p),
-          ast::DefTyParam(did, v) => ast::DefTyParam(did.tr(xcx), v),
-          ast::DefBinding(nid, bm) => ast::DefBinding(xcx.tr_id(nid), bm),
-          ast::DefUse(did) => ast::DefUse(did.tr(xcx)),
-          ast::DefUpvar(nid1, def, nid2, nid3) => {
-            ast::DefUpvar(xcx.tr_id(nid1),
+          def::DefTrait(did) => def::DefTrait(did.tr(xcx)),
+          def::DefTy(did) => def::DefTy(did.tr(xcx)),
+          def::DefPrimTy(p) => def::DefPrimTy(p),
+          def::DefTyParam(did, v) => def::DefTyParam(did.tr(xcx), v),
+          def::DefBinding(nid, bm) => def::DefBinding(xcx.tr_id(nid), bm),
+          def::DefUse(did) => def::DefUse(did.tr(xcx)),
+          def::DefUpvar(nid1, def, nid2, nid3) => {
+            def::DefUpvar(xcx.tr_id(nid1),
                            @(*def).tr(xcx),
                            xcx.tr_id(nid2),
                            xcx.tr_id(nid3))
           }
-          ast::DefStruct(did) => ast::DefStruct(did.tr(xcx)),
-          ast::DefRegion(nid) => ast::DefRegion(xcx.tr_id(nid)),
-          ast::DefTyParamBinder(nid) => {
-            ast::DefTyParamBinder(xcx.tr_id(nid))
+          def::DefStruct(did) => def::DefStruct(did.tr(xcx)),
+          def::DefRegion(nid) => def::DefRegion(xcx.tr_id(nid)),
+          def::DefTyParamBinder(nid) => {
+            def::DefTyParamBinder(xcx.tr_id(nid))
           }
-          ast::DefLabel(nid) => ast::DefLabel(xcx.tr_id(nid))
+          def::DefLabel(nid) => def::DefLabel(xcx.tr_id(nid))
         }
     }
 }
@@ -796,7 +798,7 @@ trait ebml_writer_helpers {
     fn emit_tpbt(&mut self,
                  ecx: &e::EncodeContext,
                  tpbt: ty::ty_param_bounds_and_ty);
-    fn emit_substs(&mut self, ecx: &e::EncodeContext, substs: &ty::substs);
+    fn emit_substs(&mut self, ecx: &e::EncodeContext, substs: &subst::Substs);
     fn emit_auto_adjustment(&mut self, ecx: &e::EncodeContext, adj: &ty::AutoAdjustment);
 }
 
@@ -842,7 +844,7 @@ impl<'a> ebml_writer_helpers for Encoder<'a> {
         });
     }
 
-    fn emit_substs(&mut self, ecx: &e::EncodeContext, substs: &ty::substs) {
+    fn emit_substs(&mut self, ecx: &e::EncodeContext, substs: &subst::Substs) {
         self.emit_opaque(|this| Ok(tyencode::enc_substs(this.writer,
                                                            &ecx.ty_str_ctxt(),
                                                            substs)));
@@ -1076,7 +1078,7 @@ trait ebml_decoder_decoder_helpers {
                            -> ty::TypeParameterDef;
     fn read_ty_param_bounds_and_ty(&mut self, xcx: &ExtendedDecodeContext)
                                 -> ty::ty_param_bounds_and_ty;
-    fn read_substs(&mut self, xcx: &ExtendedDecodeContext) -> ty::substs;
+    fn read_substs(&mut self, xcx: &ExtendedDecodeContext) -> subst::Substs;
     fn read_auto_adjustment(&mut self, xcx: &ExtendedDecodeContext) -> ty::AutoAdjustment;
     fn convert_def_id(&mut self,
                       xcx: &ExtendedDecodeContext,
@@ -1093,7 +1095,7 @@ trait ebml_decoder_decoder_helpers {
                       cdata: &cstore::crate_metadata) -> Vec<ty::t>;
     fn read_substs_noxcx(&mut self, tcx: &ty::ctxt,
                          cdata: &cstore::crate_metadata)
-                         -> ty::substs;
+                         -> subst::Substs;
 }
 
 impl<'a> ebml_decoder_decoder_helpers for reader::Decoder<'a> {
@@ -1121,7 +1123,7 @@ impl<'a> ebml_decoder_decoder_helpers for reader::Decoder<'a> {
     fn read_substs_noxcx(&mut self,
                          tcx: &ty::ctxt,
                          cdata: &cstore::crate_metadata)
-                         -> ty::substs
+                         -> subst::Substs
     {
         self.read_opaque(|_, doc| {
             Ok(tydecode::parse_substs_data(
@@ -1210,7 +1212,7 @@ impl<'a> ebml_decoder_decoder_helpers for reader::Decoder<'a> {
         }).unwrap()
     }
 
-    fn read_substs(&mut self, xcx: &ExtendedDecodeContext) -> ty::substs {
+    fn read_substs(&mut self, xcx: &ExtendedDecodeContext) -> subst::Substs {
         self.read_opaque(|this, doc| {
             Ok(tydecode::parse_substs_data(doc.data,
                                         xcx.dcx.cdata.cnum,
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index 0fbcf157dac..5706d249c46 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -14,6 +14,7 @@
 
 use middle::dataflow::DataFlowContext;
 use middle::dataflow::DataFlowOperator;
+use middle::def;
 use euv = middle::expr_use_visitor;
 use mc = middle::mem_categorization;
 use middle::ty;
@@ -399,7 +400,7 @@ impl<'a> BorrowckCtxt<'a> {
                    id: ast::NodeId,
                    span: Span,
                    ty: ty::t,
-                   def: ast::Def)
+                   def: def::Def)
                    -> mc::cmt {
         match self.mc().cat_def(id, span, ty, def) {
             Ok(c) => c,
@@ -412,11 +413,11 @@ impl<'a> BorrowckCtxt<'a> {
     pub fn cat_captured_var(&self,
                             closure_id: ast::NodeId,
                             closure_span: Span,
-                            upvar_def: ast::Def)
+                            upvar_def: def::Def)
                             -> mc::cmt {
         // Create the cmt for the variable being borrowed, from the
         // caller's perspective
-        let var_id = ast_util::def_id_of_def(upvar_def).node;
+        let var_id = upvar_def.def_id().node;
         let var_ty = ty::node_id_to_type(self.tcx, var_id);
         self.cat_def(closure_id, closure_span, var_ty, upvar_def)
     }
diff --git a/src/librustc/middle/cfg/construct.rs b/src/librustc/middle/cfg/construct.rs
index e2b4dde577a..4a36e84fbe5 100644
--- a/src/librustc/middle/cfg/construct.rs
+++ b/src/librustc/middle/cfg/construct.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 use middle::cfg::*;
+use middle::def;
 use middle::graph;
 use middle::typeck;
 use middle::ty;
@@ -531,7 +532,7 @@ impl<'a> CFGBuilder<'a> {
 
             Some(_) => {
                 match self.tcx.def_map.borrow().find(&expr.id) {
-                    Some(&ast::DefLabel(loop_id)) => {
+                    Some(&def::DefLabel(loop_id)) => {
                         for l in self.loop_scopes.iter() {
                             if l.loop_id == loop_id {
                                 return *l;
diff --git a/src/librustc/middle/check_const.rs b/src/librustc/middle/check_const.rs
index 64b7977c235..2bb7d0bc5c8 100644
--- a/src/librustc/middle/check_const.rs
+++ b/src/librustc/middle/check_const.rs
@@ -10,6 +10,7 @@
 
 
 use driver::session::Session;
+use middle::def::*;
 use middle::resolve;
 use middle::ty;
 use middle::typeck;
diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs
index 26bc845a15a..39a35e3adfa 100644
--- a/src/librustc/middle/check_match.rs
+++ b/src/librustc/middle/check_match.rs
@@ -12,6 +12,7 @@
 
 use middle::const_eval::{compare_const_vals, lookup_const_by_id};
 use middle::const_eval::{eval_const_expr, const_val, const_bool, const_float};
+use middle::def::*;
 use middle::pat_util::*;
 use middle::ty::*;
 use middle::ty;
diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs
index e7ad08d4eb2..ca94cf24850 100644
--- a/src/librustc/middle/const_eval.rs
+++ b/src/librustc/middle/const_eval.rs
@@ -14,6 +14,7 @@
 use metadata::csearch;
 use middle::astencode;
 
+use middle::def;
 use middle::ty;
 use middle::typeck::astconv;
 use util::nodemap::{DefIdMap};
@@ -83,10 +84,10 @@ pub fn join_all<It: Iterator<constness>>(mut cs: It) -> constness {
 pub fn lookup_const(tcx: &ty::ctxt, e: &Expr) -> Option<@Expr> {
     let opt_def = tcx.def_map.borrow().find_copy(&e.id);
     match opt_def {
-        Some(ast::DefStatic(def_id, false)) => {
+        Some(def::DefStatic(def_id, false)) => {
             lookup_const_by_id(tcx, def_id)
         }
-        Some(ast::DefVariant(enum_def, variant_def, _)) => {
+        Some(def::DefVariant(enum_def, variant_def, _)) => {
             lookup_variant_by_id(tcx, enum_def, variant_def)
         }
         _ => None
diff --git a/src/librustc/middle/dataflow.rs b/src/librustc/middle/dataflow.rs
index 30792da84e0..3eec3c7e881 100644
--- a/src/librustc/middle/dataflow.rs
+++ b/src/librustc/middle/dataflow.rs
@@ -17,6 +17,9 @@
  */
 
 
+use middle::def;
+use middle::ty;
+use middle::typeck;
 use std::io;
 use std::string::String;
 use std::uint;
@@ -24,8 +27,6 @@ use syntax::ast;
 use syntax::ast_util;
 use syntax::ast_util::IdRange;
 use syntax::print::{pp, pprust};
-use middle::ty;
-use middle::typeck;
 use util::ppaux::Repr;
 use util::nodemap::NodeMap;
 
@@ -757,7 +758,7 @@ impl<'a, 'b, O:DataFlowOperator> PropagationContext<'a, 'b, O> {
 
             Some(_) => {
                 match self.tcx().def_map.borrow().find(&expr.id) {
-                    Some(&ast::DefLabel(loop_id)) => {
+                    Some(&def::DefLabel(loop_id)) => {
                         match loop_scopes.iter().position(|l| l.loop_id == loop_id) {
                             Some(i) => i,
                             None => {
diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs
index d3d5eb3f8fd..fb19fbd70c6 100644
--- a/src/librustc/middle/dead.rs
+++ b/src/librustc/middle/dead.rs
@@ -12,6 +12,7 @@
 // closely. The idea is that all reachable symbols are live, codes called
 // from live codes are live, and everything else is dead.
 
+use middle::def;
 use middle::lint::{Allow, contains_lint, DeadCode};
 use middle::privacy;
 use middle::ty;
@@ -21,7 +22,7 @@ use util::nodemap::NodeSet;
 use std::collections::HashSet;
 use syntax::ast;
 use syntax::ast_map;
-use syntax::ast_util::{local_def, def_id_of_def, is_local};
+use syntax::ast_util::{local_def, is_local};
 use syntax::attr;
 use syntax::codemap;
 use syntax::parse::token;
@@ -77,9 +78,9 @@ impl<'a> MarkSymbolVisitor<'a> {
             None => return
         };
         let def_id = match def {
-            ast::DefVariant(enum_id, _, _) => Some(enum_id),
-            ast::DefPrimTy(_) => None,
-            _ => Some(def_id_of_def(def)),
+            def::DefVariant(enum_id, _, _) => Some(enum_id),
+            def::DefPrimTy(_) => None,
+            _ => Some(def.def_id())
         };
         match def_id {
             Some(def_id) => self.check_def_id(def_id),
diff --git a/src/librustc/middle/def.rs b/src/librustc/middle/def.rs
new file mode 100644
index 00000000000..ca89439eaba
--- /dev/null
+++ b/src/librustc/middle/def.rs
@@ -0,0 +1,89 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use syntax::ast;
+use syntax::ast_util::local_def;
+
+#[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
+pub enum Def {
+    DefFn(ast::DefId, ast::FnStyle),
+    DefStaticMethod(/* method */ ast::DefId, MethodProvenance, ast::FnStyle),
+    DefSelfTy(/* trait id */ ast::NodeId),
+    DefMod(ast::DefId),
+    DefForeignMod(ast::DefId),
+    DefStatic(ast::DefId, bool /* is_mutbl */),
+    DefArg(ast::NodeId, ast::BindingMode),
+    DefLocal(ast::NodeId, ast::BindingMode),
+    DefVariant(ast::DefId /* enum */, ast::DefId /* variant */, bool /* is_structure */),
+    DefTy(ast::DefId),
+    DefTrait(ast::DefId),
+    DefPrimTy(ast::PrimTy),
+    DefTyParam(ast::DefId, uint),
+    DefBinding(ast::NodeId, ast::BindingMode),
+    DefUse(ast::DefId),
+    DefUpvar(ast::NodeId,  // id of closed over var
+             @Def,     // closed over def
+             ast::NodeId,  // expr node that creates the closure
+             ast::NodeId), // id for the block/body of the closure expr
+
+    /// Note that if it's a tuple struct's definition, the node id of the ast::DefId
+    /// may either refer to the item definition's id or the StructDef.ctor_id.
+    ///
+    /// The cases that I have encountered so far are (this is not exhaustive):
+    /// - If it's a ty_path referring to some tuple struct, then DefMap maps
+    ///   it to a def whose id is the item definition's id.
+    /// - If it's an ExprPath referring to some tuple struct, then DefMap maps
+    ///   it to a def whose id is the StructDef.ctor_id.
+    DefStruct(ast::DefId),
+    DefTyParamBinder(ast::NodeId), /* struct, impl or trait with ty params */
+    DefRegion(ast::NodeId),
+    DefLabel(ast::NodeId),
+    DefMethod(ast::DefId /* method */, Option<ast::DefId> /* trait */),
+}
+
+#[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
+pub enum MethodProvenance {
+    FromTrait(ast::DefId),
+    FromImpl(ast::DefId),
+}
+
+impl Def {
+    pub fn def_id(&self) -> ast::DefId {
+        match *self {
+            DefFn(id, _) | DefStaticMethod(id, _, _) | DefMod(id) |
+            DefForeignMod(id) | DefStatic(id, _) |
+            DefVariant(_, id, _) | DefTy(id) | DefTyParam(id, _) |
+            DefUse(id) | DefStruct(id) | DefTrait(id) | DefMethod(id, _) => {
+                id
+            }
+            DefArg(id, _) |
+            DefLocal(id, _) |
+            DefSelfTy(id) |
+            DefUpvar(id, _, _, _) |
+            DefBinding(id, _) |
+            DefRegion(id) |
+            DefTyParamBinder(id) |
+            DefLabel(id) => {
+                local_def(id)
+            }
+
+            DefPrimTy(_) => fail!()
+        }
+    }
+
+    pub fn variant_def_ids(&self) -> Option<(ast::DefId, ast::DefId)> {
+        match *self {
+            DefVariant(enum_id, var_id, _) => {
+                Some((enum_id, var_id))
+            }
+            _ => None
+        }
+    }
+}
diff --git a/src/librustc/middle/effect.rs b/src/librustc/middle/effect.rs
index bc9a1c9b5fc..c75d793cba6 100644
--- a/src/librustc/middle/effect.rs
+++ b/src/librustc/middle/effect.rs
@@ -11,6 +11,7 @@
 //! Enforces the Rust effect system. Currently there is just one effect,
 /// `unsafe`.
 
+use middle::def;
 use middle::ty;
 use middle::typeck::MethodCall;
 use util::ppaux;
@@ -183,7 +184,7 @@ impl<'a> Visitor<()> for EffectCheckVisitor<'a> {
             }
             ast::ExprPath(..) => {
                 match ty::resolve_expr(self.tcx, expr) {
-                    ast::DefStatic(_, true) => {
+                    def::DefStatic(_, true) => {
                         self.require_unsafe(expr.span, "use of mutable static")
                     }
                     _ => {}
diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index cd71d95bee9..c44ea0ae78b 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -15,12 +15,12 @@
  */
 
 use mc = middle::mem_categorization;
+use middle::def;
 use middle::freevars;
 use middle::pat_util;
 use middle::ty;
 use middle::typeck;
 use syntax::ast;
-use syntax::ast_util;
 use syntax::codemap::{Span};
 use util::ppaux::Repr;
 
@@ -814,7 +814,7 @@ impl<'d,'t,TYPER:mc::Typer> ExprUseVisitor<'d,'t,TYPER> {
                             closure_expr: &ast::Expr,
                             freevars: &[freevars::freevar_entry]) {
         for freevar in freevars.iter() {
-            let id_var = ast_util::def_id_of_def(freevar.def).node;
+            let id_var = freevar.def.def_id().node;
             let cmt_var = return_if_err!(self.cat_captured_var(closure_expr.id,
                                                                closure_expr.span,
                                                                freevar.def));
@@ -850,11 +850,11 @@ impl<'d,'t,TYPER:mc::Typer> ExprUseVisitor<'d,'t,TYPER> {
     fn cat_captured_var(&mut self,
                         closure_id: ast::NodeId,
                         closure_span: Span,
-                        upvar_def: ast::Def)
+                        upvar_def: def::Def)
                         -> mc::McResult<mc::cmt> {
         // Create the cmt for the variable being borrowed, from the
         // caller's perspective
-        let var_id = ast_util::def_id_of_def(upvar_def).node;
+        let var_id = upvar_def.def_id().node;
         let var_ty = ty::node_id_to_type(self.tcx(), var_id);
         self.mc.cat_def(closure_id, closure_span, var_ty, upvar_def)
     }
diff --git a/src/librustc/middle/freevars.rs b/src/librustc/middle/freevars.rs
index 47523f4f750..614972f3d57 100644
--- a/src/librustc/middle/freevars.rs
+++ b/src/librustc/middle/freevars.rs
@@ -13,12 +13,13 @@
 
 #![allow(non_camel_case_types)]
 
+use middle::def;
 use middle::resolve;
 use middle::ty;
 use util::nodemap::{NodeMap, NodeSet};
 
 use syntax::codemap::Span;
-use syntax::{ast, ast_util};
+use syntax::{ast};
 use syntax::visit;
 use syntax::visit::Visitor;
 
@@ -35,7 +36,7 @@ pub enum CaptureMode {
 // (The def_upvar will already have been stripped).
 #[deriving(Encodable, Decodable)]
 pub struct freevar_entry {
-    pub def: ast::Def, //< The variable being accessed free.
+    pub def: def::Def, //< The variable being accessed free.
     pub span: Span     //< First span where it is accessed (there can be multiple)
 }
 pub type freevar_map = NodeMap<Vec<freevar_entry>>;
@@ -64,13 +65,13 @@ impl<'a> Visitor<int> for CollectFreevarsVisitor<'a> {
                         let mut def = df;
                         while i < depth {
                             match def {
-                                ast::DefUpvar(_, inner, _, _) => { def = *inner; }
+                                def::DefUpvar(_, inner, _, _) => { def = *inner; }
                                 _ => break
                             }
                             i += 1;
                         }
                         if i == depth { // Made it to end of loop
-                            let dnum = ast_util::def_id_of_def(def).node;
+                            let dnum = def.def_id().node;
                             if !self.seen.contains(&dnum) {
                                 self.refs.push(freevar_entry {
                                     def: def,
diff --git a/src/librustc/middle/kind.rs b/src/librustc/middle/kind.rs
index b6614d15106..39f2e842583 100644
--- a/src/librustc/middle/kind.rs
+++ b/src/librustc/middle/kind.rs
@@ -11,6 +11,7 @@
 
 use middle::freevars::freevar_entry;
 use middle::freevars;
+use middle::subst;
 use middle::ty;
 use middle::typeck;
 use util::ppaux::{Repr, ty_to_str};
@@ -19,9 +20,8 @@ use util::ppaux::UserString;
 use syntax::ast::*;
 use syntax::attr;
 use syntax::codemap::Span;
-use syntax::owned_slice::OwnedSlice;
 use syntax::print::pprust::{expr_to_str,path_to_str};
-use syntax::{visit,ast_util};
+use syntax::{visit};
 use syntax::visit::Visitor;
 
 // Kind analysis pass.
@@ -87,8 +87,8 @@ fn check_struct_safe_for_destructor(cx: &mut Context,
                                     struct_did: DefId) {
     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 {
-            regions: ty::NonerasedRegions(OwnedSlice::empty()),
+        let struct_ty = ty::mk_struct(cx.tcx, struct_did, subst::Substs {
+            regions: subst::NonerasedRegions(Vec::new()),
             self_ty: None,
             tps: Vec::new()
         });
@@ -116,7 +116,7 @@ fn check_impl_of_trait(cx: &mut Context, it: &Item, trait_ref: &TraitRef, self_t
     let ast_trait_def = *cx.tcx.def_map.borrow()
                               .find(&trait_ref.ref_id)
                               .expect("trait ref not in def map!");
-    let trait_def_id = ast_util::def_id_of_def(ast_trait_def);
+    let trait_def_id = ast_trait_def.def_id();
     let trait_def = cx.tcx.trait_defs.borrow()
                           .find_copy(&trait_def_id)
                           .expect("trait def not in trait-defs map!");
@@ -141,7 +141,7 @@ fn check_impl_of_trait(cx: &mut Context, it: &Item, trait_ref: &TraitRef, self_t
             TyPath(_, ref bounds, path_node_id) => {
                 assert!(bounds.is_none());
                 let struct_def = cx.tcx.def_map.borrow().get_copy(&path_node_id);
-                let struct_did = ast_util::def_id_of_def(struct_def);
+                let struct_did = struct_def.def_id();
                 check_struct_safe_for_destructor(cx, self_type.span, struct_did);
             }
             _ => {
@@ -174,7 +174,7 @@ fn with_appropriate_checker(cx: &Context,
     fn check_for_uniq(cx: &Context, fv: &freevar_entry, bounds: ty::BuiltinBounds) {
         // all captured data must be owned, regardless of whether it is
         // moved in or copied in.
-        let id = ast_util::def_id_of_def(fv.def).node;
+        let id = fv.def.def_id().node;
         let var_t = ty::node_id_to_type(cx.tcx, id);
 
         check_freevar_bounds(cx, fv.span, var_t, bounds, None);
@@ -182,7 +182,7 @@ fn with_appropriate_checker(cx: &Context,
 
     fn check_for_block(cx: &Context, fv: &freevar_entry,
                        bounds: ty::BuiltinBounds, region: ty::Region) {
-        let id = ast_util::def_id_of_def(fv.def).node;
+        let id = fv.def.def_id().node;
         let var_t = ty::node_id_to_type(cx.tcx, id);
         // FIXME(#3569): Figure out whether the implicit borrow is actually
         // mutable. Currently we assume all upvars are referenced mutably.
@@ -257,7 +257,7 @@ pub fn check_expr(cx: &mut Context, e: &Expr) {
             let def_map = cx.tcx.def_map.borrow();
             let type_param_defs = match e.node {
               ExprPath(_) => {
-                let did = ast_util::def_id_of_def(def_map.get_copy(&e.id));
+                let did = def_map.get_copy(&e.id).def_id();
                 ty::lookup_item_type(cx.tcx, did).generics.type_param_defs.clone()
               }
               _ => {
@@ -348,7 +348,7 @@ fn check_ty(cx: &mut Context, aty: &Ty) {
                 None => { }
                 Some(ref item_substs) => {
                     let def_map = cx.tcx.def_map.borrow();
-                    let did = ast_util::def_id_of_def(def_map.get_copy(&id));
+                    let did = def_map.get_copy(&id).def_id();
                     let generics = ty::lookup_item_type(cx.tcx, did).generics;
                     let type_param_defs = generics.type_param_defs();
                     for (&ty, type_param_def) in
diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs
index 871a336479d..cae8436d6df 100644
--- a/src/librustc/middle/lint.rs
+++ b/src/librustc/middle/lint.rs
@@ -38,6 +38,8 @@
 use driver::session;
 use metadata::csearch;
 use middle::dead::DEAD_CODE_LINT_STR;
+use middle::def;
+use middle::def::*;
 use middle::pat_util;
 use middle::privacy;
 use middle::trans::adt; // for `adt::is_ffi_safe`
@@ -935,17 +937,17 @@ fn check_item_ctypes(cx: &Context, it: &ast::Item) {
         match ty.node {
             ast::TyPath(_, _, id) => {
                 match cx.tcx.def_map.borrow().get_copy(&id) {
-                    ast::DefPrimTy(ast::TyInt(ast::TyI)) => {
+                    def::DefPrimTy(ast::TyInt(ast::TyI)) => {
                         cx.span_lint(CTypes, ty.span,
                                 "found rust type `int` in foreign module, while \
                                 libc::c_int or libc::c_long should be used");
                     }
-                    ast::DefPrimTy(ast::TyUint(ast::TyU)) => {
+                    def::DefPrimTy(ast::TyUint(ast::TyU)) => {
                         cx.span_lint(CTypes, ty.span,
                                 "found rust type `uint` in foreign module, while \
                                 libc::c_uint or libc::c_ulong should be used");
                     }
-                    ast::DefTy(def_id) => {
+                    def::DefTy(def_id) => {
                         if !adt::is_ffi_safe(cx.tcx, def_id) {
                             cx.span_lint(CTypes, ty.span,
                                          "found enum type without foreign-function-safe \
@@ -1394,7 +1396,7 @@ fn check_item_non_uppercase_statics(cx: &Context, it: &ast::Item) {
 fn check_pat_non_uppercase_statics(cx: &Context, p: &ast::Pat) {
     // Lint for constants that look like binding identifiers (#7526)
     match (&p.node, cx.tcx.def_map.borrow().find(&p.id)) {
-        (&ast::PatIdent(_, ref path, _), Some(&ast::DefStatic(_, false))) => {
+        (&ast::PatIdent(_, ref path, _), Some(&def::DefStatic(_, false))) => {
             // last identifier alone is right choice for this lint.
             let ident = path.segments.last().unwrap().identifier;
             let s = token::get_ident(ident);
@@ -1411,8 +1413,8 @@ fn check_pat_uppercase_variable(cx: &Context, p: &ast::Pat) {
     match &p.node {
         &ast::PatIdent(_, ref path, _) => {
             match cx.tcx.def_map.borrow().find(&p.id) {
-                Some(&ast::DefLocal(_, _)) | Some(&ast::DefBinding(_, _)) |
-                        Some(&ast::DefArg(_, _)) => {
+                Some(&def::DefLocal(_, _)) | Some(&def::DefBinding(_, _)) |
+                        Some(&def::DefArg(_, _)) => {
                     // last identifier alone is right choice for this lint.
                     let ident = path.segments.last().unwrap().identifier;
                     let s = token::get_ident(ident);
@@ -1726,7 +1728,7 @@ fn check_stability(cx: &Context, e: &ast::Expr) {
     let id = match e.node {
         ast::ExprPath(..) | ast::ExprStruct(..) => {
             match cx.tcx.def_map.borrow().find(&e.id) {
-                Some(&def) => ast_util::def_id_of_def(def),
+                Some(&def) => def.def_id(),
                 None => return
             }
         }
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index b5cb0f8e5aa..8b1de130053 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -102,7 +102,7 @@
  *   to return explicitly.
  */
 
-
+use middle::def::*;
 use middle::freevars;
 use middle::lint::{UnusedVariable, DeadAssignment};
 use middle::pat_util;
@@ -486,7 +486,7 @@ fn visit_expr(ir: &mut IrMaps, expr: &Expr) {
                 match moved_variable_node_id_from_def(fv.def) {
                     Some(rv) => {
                         let fv_ln = ir.add_live_node(FreeVarNode(fv.span));
-                        let fv_id = ast_util::def_id_of_def(fv.def).node;
+                        let fv_id = fv.def.def_id().node;
                         let fv_ty = ty::node_id_to_type(ir.tcx, fv_id);
                         let is_move = match fv_mode {
                             // var must be dead afterwards
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 240212699e4..06e0a125772 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -62,6 +62,7 @@
 
 #![allow(non_camel_case_types)]
 
+use middle::def;
 use middle::ty;
 use middle::typeck;
 use util::nodemap::NodeMap;
@@ -489,20 +490,20 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
                    id: ast::NodeId,
                    span: Span,
                    expr_ty: ty::t,
-                   def: ast::Def)
+                   def: def::Def)
                    -> McResult<cmt> {
         debug!("cat_def: id={} expr={} def={:?}",
                id, expr_ty.repr(self.tcx()), def);
 
         match def {
-          ast::DefStruct(..) | ast::DefVariant(..) => {
+          def::DefStruct(..) | def::DefVariant(..) => {
                 Ok(self.cat_rvalue_node(id, span, expr_ty))
           }
-          ast::DefFn(..) | ast::DefStaticMethod(..) | ast::DefMod(_) |
-          ast::DefForeignMod(_) | ast::DefStatic(_, false) |
-          ast::DefUse(_) | ast::DefTrait(_) | ast::DefTy(_) | ast::DefPrimTy(_) |
-          ast::DefTyParam(..) | ast::DefTyParamBinder(..) | ast::DefRegion(_) |
-          ast::DefLabel(_) | ast::DefSelfTy(..) | ast::DefMethod(..) => {
+          def::DefFn(..) | def::DefStaticMethod(..) | def::DefMod(_) |
+          def::DefForeignMod(_) | def::DefStatic(_, false) |
+          def::DefUse(_) | def::DefTrait(_) | def::DefTy(_) | def::DefPrimTy(_) |
+          def::DefTyParam(..) | def::DefTyParamBinder(..) | def::DefRegion(_) |
+          def::DefLabel(_) | def::DefSelfTy(..) | def::DefMethod(..) => {
               Ok(Rc::new(cmt_ {
                   id:id,
                   span:span,
@@ -512,7 +513,7 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
               }))
           }
 
-          ast::DefStatic(_, true) => {
+          def::DefStatic(_, true) => {
               Ok(Rc::new(cmt_ {
                   id:id,
                   span:span,
@@ -522,7 +523,7 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
               }))
           }
 
-          ast::DefArg(vid, binding_mode) => {
+          def::DefArg(vid, binding_mode) => {
             // Idea: make this could be rewritten to model by-ref
             // stuff as `&const` and `&mut`?
 
@@ -540,7 +541,7 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
             }))
           }
 
-          ast::DefUpvar(var_id, _, fn_node_id, _) => {
+          def::DefUpvar(var_id, _, fn_node_id, _) => {
               let ty = if_ok!(self.node_ty(fn_node_id));
               match ty::get(ty).sty {
                   ty::ty_closure(ref closure_ty) => {
@@ -582,8 +583,8 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
               }
           }
 
-          ast::DefLocal(vid, binding_mode) |
-          ast::DefBinding(vid, binding_mode) => {
+          def::DefLocal(vid, binding_mode) |
+          def::DefBinding(vid, binding_mode) => {
             // by-value/by-ref bindings are local variables
             let m = match binding_mode {
                 ast::BindByValue(ast::MutMutable) => McDeclared,
@@ -987,7 +988,7 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
           }
           ast::PatEnum(_, Some(ref subpats)) => {
             match self.tcx().def_map.borrow().find(&pat.id) {
-                Some(&ast::DefVariant(enum_did, _, _)) => {
+                Some(&def::DefVariant(enum_did, _, _)) => {
                     // variant(x, y, z)
 
                     let downcast_cmt = {
@@ -1009,8 +1010,8 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
                         if_ok!(self.cat_pattern(subcmt, subpat, |x,y,z| op(x,y,z)));
                     }
                 }
-                Some(&ast::DefFn(..)) |
-                Some(&ast::DefStruct(..)) => {
+                Some(&def::DefFn(..)) |
+                Some(&def::DefStruct(..)) => {
                     for (i, &subpat) in subpats.iter().enumerate() {
                         let subpat_ty = if_ok!(self.pat_ty(subpat)); // see (*2)
                         let cmt_field =
@@ -1020,7 +1021,7 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
                         if_ok!(self.cat_pattern(cmt_field, subpat, |x,y,z| op(x,y,z)));
                     }
                 }
-                Some(&ast::DefStatic(..)) => {
+                Some(&def::DefStatic(..)) => {
                     for &subpat in subpats.iter() {
                         if_ok!(self.cat_pattern(cmt.clone(), subpat, |x,y,z| op(x,y,z)));
                     }
diff --git a/src/librustc/middle/pat_util.rs b/src/librustc/middle/pat_util.rs
index 49437a90e3f..44ed0192d1d 100644
--- a/src/librustc/middle/pat_util.rs
+++ b/src/librustc/middle/pat_util.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-
+use middle::def::*;
 use middle::resolve;
 
 use std::collections::HashMap;
diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs
index 5b47336efe5..fcd6d424659 100644
--- a/src/librustc/middle/privacy.rs
+++ b/src/librustc/middle/privacy.rs
@@ -15,6 +15,7 @@
 use std::mem::replace;
 
 use metadata::csearch;
+use middle::def;
 use middle::lint;
 use middle::resolve;
 use middle::ty;
@@ -24,7 +25,7 @@ use util::nodemap::{NodeMap, NodeSet};
 
 use syntax::ast;
 use syntax::ast_map;
-use syntax::ast_util::{is_local, def_id_of_def, local_def};
+use syntax::ast_util::{is_local, local_def};
 use syntax::attr;
 use syntax::codemap::Span;
 use syntax::parse::token;
@@ -243,9 +244,9 @@ impl<'a> Visitor<()> for EmbargoVisitor<'a> {
                 let public_ty = match ty.node {
                     ast::TyPath(_, _, id) => {
                         match self.tcx.def_map.borrow().get_copy(&id) {
-                            ast::DefPrimTy(..) => true,
+                            def::DefPrimTy(..) => true,
                             def => {
-                                let did = def_id_of_def(def);
+                                let did = def.def_id();
                                 !is_local(did) ||
                                  self.exported_items.contains(&did.node)
                             }
@@ -301,9 +302,9 @@ impl<'a> Visitor<()> for EmbargoVisitor<'a> {
                 match ty.node {
                     ast::TyPath(_, _, id) => {
                         match self.tcx.def_map.borrow().get_copy(&id) {
-                            ast::DefPrimTy(..) => {},
+                            def::DefPrimTy(..) => {},
                             def => {
-                                let did = def_id_of_def(def);
+                                let did = def.def_id();
                                 if is_local(did) {
                                     self.exported_items.insert(did.node);
                                 }
@@ -576,7 +577,7 @@ impl<'a> PrivacyVisitor<'a> {
                             _ => return Some((err_span, err_msg, None)),
                         };
                         let def = self.tcx.def_map.borrow().get_copy(&id);
-                        let did = def_id_of_def(def);
+                        let did = def.def_id();
                         assert!(is_local(did));
                         match self.tcx.map.get(did.node) {
                             ast_map::NodeItem(item) => item,
@@ -673,7 +674,7 @@ impl<'a> PrivacyVisitor<'a> {
                                                 .last()
                                                 .unwrap()
                                                 .identifier);
-                let origdid = def_id_of_def(orig_def);
+                let origdid = orig_def.def_id();
                 self.ensure_public(span,
                                    def,
                                    Some(origdid),
@@ -750,16 +751,16 @@ impl<'a> PrivacyVisitor<'a> {
         // be accurate and we can get slightly wonky error messages (but type
         // checking is always correct).
         match self.tcx.def_map.borrow().get_copy(&path_id) {
-            ast::DefStaticMethod(..) => ck("static method"),
-            ast::DefFn(..) => ck("function"),
-            ast::DefStatic(..) => ck("static"),
-            ast::DefVariant(..) => ck("variant"),
-            ast::DefTy(..) => ck("type"),
-            ast::DefTrait(..) => ck("trait"),
-            ast::DefStruct(..) => ck("struct"),
-            ast::DefMethod(_, Some(..)) => ck("trait method"),
-            ast::DefMethod(..) => ck("method"),
-            ast::DefMod(..) => ck("module"),
+            def::DefStaticMethod(..) => ck("static method"),
+            def::DefFn(..) => ck("function"),
+            def::DefStatic(..) => ck("static"),
+            def::DefVariant(..) => ck("variant"),
+            def::DefTy(..) => ck("type"),
+            def::DefTrait(..) => ck("trait"),
+            def::DefStruct(..) => ck("struct"),
+            def::DefMethod(_, Some(..)) => ck("trait method"),
+            def::DefMethod(..) => ck("method"),
+            def::DefMod(..) => ck("module"),
             _ => {}
         }
     }
@@ -829,7 +830,7 @@ impl<'a> Visitor<()> for PrivacyVisitor<'a> {
                     }
                     ty::ty_enum(_, _) => {
                         match self.tcx.def_map.borrow().get_copy(&expr.id) {
-                            ast::DefVariant(_, variant_id, _) => {
+                            def::DefVariant(_, variant_id, _) => {
                                 for field in fields.iter() {
                                     self.check_field(expr.span, variant_id,
                                                      NamedField(field.ident.node));
@@ -862,7 +863,7 @@ impl<'a> Visitor<()> for PrivacyVisitor<'a> {
                     }
                 };
                 match self.tcx.def_map.borrow().find(&expr.id) {
-                    Some(&ast::DefStruct(did)) => {
+                    Some(&def::DefStruct(did)) => {
                         guard(if is_local(did) {
                             local_def(self.tcx.map.get_parent(did.node))
                         } else {
@@ -877,7 +878,7 @@ impl<'a> Visitor<()> for PrivacyVisitor<'a> {
                     }
                     // Tuple struct constructors across crates are identified as
                     // DefFn types, so we explicitly handle that case here.
-                    Some(&ast::DefFn(did, _)) if !is_local(did) => {
+                    Some(&def::DefFn(did, _)) if !is_local(did) => {
                         match csearch::get_tuple_struct_definition_if_ctor(
                                     &self.tcx.sess.cstore, did) {
                             Some(did) => guard(did),
@@ -940,7 +941,7 @@ impl<'a> Visitor<()> for PrivacyVisitor<'a> {
                     }
                     ty::ty_enum(_, _) => {
                         match self.tcx.def_map.borrow().find(&pattern.id) {
-                            Some(&ast::DefVariant(_, variant_id, _)) => {
+                            Some(&def::DefVariant(_, variant_id, _)) => {
                                 for field in fields.iter() {
                                     self.check_field(pattern.span, variant_id,
                                                      NamedField(field.ident));
@@ -1205,8 +1206,8 @@ impl<'a> VisiblePrivateTypesVisitor<'a> {
     fn path_is_private_type(&self, path_id: ast::NodeId) -> bool {
         let did = match self.tcx.def_map.borrow().find_copy(&path_id) {
             // `int` etc. (None doesn't seem to occur.)
-            None | Some(ast::DefPrimTy(..)) => return false,
-            Some(def) => def_id_of_def(def)
+            None | Some(def::DefPrimTy(..)) => return false,
+            Some(def) => def.def_id()
         };
         // A path can only be private if:
         // it's in this crate...
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index a725ac960f8..ef2f78de8f9 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -16,6 +16,7 @@
 // reachable as well.
 
 use driver::config;
+use middle::def;
 use middle::ty;
 use middle::typeck;
 use middle::privacy;
@@ -25,7 +26,7 @@ use std::collections::HashSet;
 use syntax::abi;
 use syntax::ast;
 use syntax::ast_map;
-use syntax::ast_util::{def_id_of_def, is_local};
+use syntax::ast_util::{is_local};
 use syntax::attr;
 use syntax::visit::Visitor;
 use syntax::visit;
@@ -109,7 +110,7 @@ impl<'a> Visitor<()> for ReachableContext<'a> {
                     }
                 };
 
-                let def_id = def_id_of_def(def);
+                let def_id = def.def_id();
                 if is_local(def_id) {
                     if self.def_id_represents_local_inlined_item(def_id) {
                         self.worklist.push(def_id.node)
@@ -119,7 +120,7 @@ impl<'a> Visitor<()> for ReachableContext<'a> {
                             // to do some work to figure out whether the static
                             // is indeed reachable (address_insignificant
                             // statics are *never* reachable).
-                            ast::DefStatic(..) => {
+                            def::DefStatic(..) => {
                                 self.worklist.push(def_id.node);
                             }
 
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index 2228c21b239..9bfa0e10aed 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -13,6 +13,7 @@
 use driver::session::Session;
 use metadata::csearch;
 use metadata::decoder::{DefLike, DlDef, DlField, DlImpl};
+use middle::def::*;
 use middle::lang_items::LanguageItems;
 use middle::lint::{UnnecessaryQualification, UnusedImports};
 use middle::pat_util::pat_bindings;
@@ -20,7 +21,7 @@ use util::nodemap::{NodeMap, DefIdSet, FnvHashMap};
 
 use syntax::ast::*;
 use syntax::ast;
-use syntax::ast_util::{def_id_of_def, local_def};
+use syntax::ast_util::{local_def};
 use syntax::ast_util::{path_to_ident, walk_pat, trait_method_to_ty_method};
 use syntax::ext::mtwt;
 use syntax::parse::token::special_idents;
@@ -265,8 +266,8 @@ enum RibKind {
               // parent;   method itself
     MethodRibKind(NodeId, MethodSort),
 
-    // We passed through a function *item* scope. Disallow upvars.
-    OpaqueFunctionRibKind,
+    // We passed through an item scope. Disallow upvars.
+    ItemRibKind,
 
     // We're in a constant item. Can't refer to dynamic stuff.
     ConstantItemRibKind
@@ -1599,7 +1600,7 @@ impl<'a> Resolver<'a> {
             }
         };
         if is_exported {
-            self.external_exports.insert(def_id_of_def(def));
+            self.external_exports.insert(def.def_id());
         }
         match def {
           DefMod(def_id) | DefForeignMod(def_id) | DefStruct(def_id) |
@@ -2438,7 +2439,7 @@ impl<'a> Resolver<'a> {
             Some(ref target) => {
                 let def = target.bindings.def_for_namespace(ValueNS).unwrap();
                 self.def_map.borrow_mut().insert(directive.id, def);
-                let did = def_id_of_def(def);
+                let did = def.def_id();
                 if value_used_public {Some(lp)} else {Some(DependsOn(did))}
             },
             // AllPublic here and below is a dummy value, it should never be used because
@@ -2449,7 +2450,7 @@ impl<'a> Resolver<'a> {
             Some(ref target) => {
                 let def = target.bindings.def_for_namespace(TypeNS).unwrap();
                 self.def_map.borrow_mut().insert(directive.id, def);
-                let did = def_id_of_def(def);
+                let did = def.def_id();
                 if type_used_public {Some(lp)} else {Some(DependsOn(did))}
             },
             None => None,
@@ -3307,10 +3308,10 @@ impl<'a> Resolver<'a> {
             Some(d) => {
                 let name = token::get_name(name);
                 debug!("(computing exports) YES: export '{}' => {:?}",
-                       name, def_id_of_def(d));
+                       name, d.def_id());
                 exports2.push(Export2 {
                     name: name.get().to_string(),
-                    def_id: def_id_of_def(d)
+                    def_id: d.def_id()
                 });
             }
             d_opt => {
@@ -3417,7 +3418,8 @@ impl<'a> Resolver<'a> {
                 def = d;
                 is_ty_param = false;
             }
-            DlDef(d @ DefTyParam(..)) => {
+            DlDef(d @ DefTyParam(..)) |
+            DlDef(d @ DefSelfTy(..)) => {
                 def = d;
                 is_ty_param = true;
             }
@@ -3434,10 +3436,10 @@ impl<'a> Resolver<'a> {
                 }
                 FunctionRibKind(function_id, body_id) => {
                     if !is_ty_param {
-                        def = DefUpvar(def_id_of_def(def).node,
-                                        @def,
-                                        function_id,
-                                        body_id);
+                        def = DefUpvar(def.def_id().node,
+                                       @def,
+                                       function_id,
+                                       body_id);
                     }
                 }
                 MethodRibKind(item_id, _) => {
@@ -3450,6 +3452,13 @@ impl<'a> Resolver<'a> {
                     } => {
                       // ok
                     }
+
+                    DefSelfTy(did) if {
+                        did == item_id
+                    } => {
+                      // ok
+                    }
+
                     _ => {
                     if !is_ty_param {
                         // This was an attempt to access an upvar inside a
@@ -3474,7 +3483,7 @@ impl<'a> Resolver<'a> {
                     }
                   }
                 }
-                OpaqueFunctionRibKind => {
+                ItemRibKind => {
                     if !is_ty_param {
                         // This was an attempt to access an upvar inside a
                         // named function item. This is not allowed, so we
@@ -3574,7 +3583,7 @@ impl<'a> Resolver<'a> {
                 self.with_type_parameter_rib(HasTypeParameters(generics,
                                                                item.id,
                                                                0,
-                                                               NormalRibKind),
+                                                               ItemRibKind),
                                              |this| {
                     visit::walk_item(this, item, ());
                 });
@@ -3584,7 +3593,7 @@ impl<'a> Resolver<'a> {
                 self.with_type_parameter_rib(HasTypeParameters(generics,
                                                                item.id,
                                                                0,
-                                                               NormalRibKind),
+                                                               ItemRibKind),
                                              |this| {
                     visit::walk_item(this, item, ());
                 });
@@ -3603,7 +3612,8 @@ impl<'a> Resolver<'a> {
 
             ItemTrait(ref generics, _, ref traits, ref methods) => {
                 // Create a new rib for the self type.
-                let self_type_rib = Rib::new(NormalRibKind);
+                let self_type_rib = Rib::new(ItemRibKind);
+
                 // plain insert (no renaming)
                 let name = self.type_self_ident.name;
                 self_type_rib.bindings.borrow_mut()
@@ -3685,7 +3695,7 @@ impl<'a> Resolver<'a> {
                                 this.with_type_parameter_rib(
                                     HasTypeParameters(
                                         generics, foreign_item.id, 0,
-                                        NormalRibKind),
+                                        ItemRibKind),
                                     |this| visit::walk_foreign_item(this,
                                                                 *foreign_item,
                                                                 ()));
@@ -3701,13 +3711,13 @@ impl<'a> Resolver<'a> {
             }
 
             ItemFn(fn_decl, _, _, ref generics, block) => {
-                self.resolve_function(OpaqueFunctionRibKind,
+                self.resolve_function(ItemRibKind,
                                       Some(fn_decl),
                                       HasTypeParameters
                                         (generics,
                                          item.id,
                                          0,
-                                         OpaqueFunctionRibKind),
+                                         ItemRibKind),
                                       block);
             }
 
@@ -3889,7 +3899,7 @@ impl<'a> Resolver<'a> {
         self.with_type_parameter_rib(HasTypeParameters(generics,
                                                        id,
                                                        0,
-                                                       OpaqueFunctionRibKind),
+                                                       ItemRibKind),
                                      |this| {
             // Resolve the type parameters.
             this.resolve_type_parameters(&generics.ty_params);
@@ -3967,7 +3977,7 @@ impl<'a> Resolver<'a> {
 
                 match self.def_map.borrow().find(&trait_ref.ref_id) {
                     Some(def) => {
-                        let did = def_id_of_def(*def);
+                        let did = def.def_id();
                         Some((did, trait_ref.clone()))
                     }
                     None => None
@@ -4638,7 +4648,7 @@ impl<'a> Resolver<'a> {
                         let p = child_name_bindings.defined_in_public_namespace(
                                         namespace);
                         let lp = if p {LastMod(AllPublic)} else {
-                            LastMod(DependsOn(def_id_of_def(def)))
+                            LastMod(DependsOn(def.def_id()))
                         };
                         return ChildNameDefinition(def, lp);
                     }
@@ -5118,7 +5128,7 @@ impl<'a> Resolver<'a> {
                                 self.value_ribs.borrow().iter().rev().advance(|rib| {
                                     let res = match *rib {
                                         Rib { bindings: _, kind: MethodRibKind(_, _) } => true,
-                                        Rib { bindings: _, kind: OpaqueFunctionRibKind } => false,
+                                        Rib { bindings: _, kind: ItemRibKind } => false,
                                         _ => return true, // Keep advancing
                                     };
 
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index e4bd8243e43..c4121d830db 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -15,9 +15,79 @@ use middle::ty_fold;
 use middle::ty_fold::{TypeFoldable, TypeFolder};
 use util::ppaux::Repr;
 
+use std::vec::Vec;
 use syntax::codemap::Span;
 
 ///////////////////////////////////////////////////////////////////////////
+
+/**
+ * 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`. */
+#[deriving(Clone, PartialEq, Eq, Hash)]
+pub enum RegionSubsts {
+    ErasedRegions,
+    NonerasedRegions(Vec<ty::Region>)
+}
+
+/**
+ * The type `Substs` represents the kinds of things that can be substituted to
+ * convert a polytype into a monotype.  Note however that substituting bound
+ * regions other than `self` is done through a different mechanism:
+ *
+ * - `tps` represents the type parameters in scope.  They are indexed
+ *   according to the order in which they were declared.
+ *
+ * - `self_r` indicates the region parameter `self` that is present on nominal
+ *   types (enums, structs) declared as having a region parameter.  `self_r`
+ *   should always be none for types that are not region-parameterized and
+ *   Some(_) for types that are.  The only bound region parameter that should
+ *   appear within a region-parameterized type is `self`.
+ *
+ * - `self_ty` is the type to which `self` should be remapped, if any.  The
+ *   `self` type is rather funny in that it can only appear on traits and is
+ *   always substituted away to the implementing type for a trait. */
+#[deriving(Clone, PartialEq, Eq, Hash)]
+pub struct Substs {
+    pub self_ty: Option<ty::t>,
+    pub tps: Vec<ty::t>,
+    pub regions: RegionSubsts,
+}
+
+impl Substs {
+    pub fn empty() -> Substs {
+        Substs {
+            self_ty: None,
+            tps: Vec::new(),
+            regions: NonerasedRegions(Vec::new())
+        }
+    }
+
+    pub fn trans_empty() -> Substs {
+        Substs {
+            self_ty: None,
+            tps: Vec::new(),
+            regions: ErasedRegions
+        }
+    }
+
+    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()
+        };
+
+        self.tps.len() == 0u &&
+            regions_is_noop &&
+            self.self_ty.is_none()
+    }
+
+    pub fn self_ty(&self) -> ty::t {
+        self.self_ty.unwrap()
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
 // Public trait `Subst`
 //
 // Just call `foo.subst(tcx, substs)` to perform a substitution across
@@ -25,12 +95,12 @@ use syntax::codemap::Span;
 // there is more information available (for better errors).
 
 pub trait Subst {
-    fn subst(&self, tcx: &ty::ctxt, substs: &ty::substs) -> Self {
+    fn subst(&self, tcx: &ty::ctxt, substs: &Substs) -> Self {
         self.subst_spanned(tcx, substs, None)
     }
 
     fn subst_spanned(&self, tcx: &ty::ctxt,
-                     substs: &ty::substs,
+                     substs: &Substs,
                      span: Option<Span>)
                      -> Self;
 }
@@ -38,7 +108,7 @@ pub trait Subst {
 impl<T:TypeFoldable> Subst for T {
     fn subst_spanned(&self,
                      tcx: &ty::ctxt,
-                     substs: &ty::substs,
+                     substs: &Substs,
                      span: Option<Span>)
                      -> T
     {
@@ -56,7 +126,7 @@ impl<T:TypeFoldable> Subst for T {
 
 struct SubstFolder<'a> {
     tcx: &'a ty::ctxt,
-    substs: &'a ty::substs,
+    substs: &'a Substs,
 
     // The location for which the substitution is performed, if available.
     span: Option<Span>,
@@ -81,8 +151,8 @@ impl<'a> TypeFolder for SubstFolder<'a> {
         match r {
             ty::ReEarlyBound(_, i, _) => {
                 match self.substs.regions {
-                    ty::ErasedRegions => ty::ReStatic,
-                    ty::NonerasedRegions(ref regions) => *regions.get(i),
+                    ErasedRegions => ty::ReStatic,
+                    NonerasedRegions(ref regions) => *regions.get(i),
                 }
             }
             _ => r
diff --git a/src/librustc/middle/trans/_match.rs b/src/librustc/middle/trans/_match.rs
index 1cf8a301d80..2a3ec63e995 100644
--- a/src/librustc/middle/trans/_match.rs
+++ b/src/librustc/middle/trans/_match.rs
@@ -198,6 +198,7 @@ use back::abi;
 use driver::config::FullDebugInfo;
 use lib::llvm::{llvm, ValueRef, BasicBlockRef};
 use middle::const_eval;
+use middle::def;
 use middle::lang_items::{UniqStrEqFnLangItem, StrEqFnLangItem};
 use middle::pat_util::*;
 use middle::resolve::DefMap;
@@ -336,7 +337,7 @@ fn variant_opt(bcx: &Block, pat_id: ast::NodeId) -> Opt {
     let ccx = bcx.ccx();
     let def = ccx.tcx.def_map.borrow().get_copy(&pat_id);
     match def {
-        ast::DefVariant(enum_id, var_id, _) => {
+        def::DefVariant(enum_id, var_id, _) => {
             let variants = ty::enum_variants(ccx.tcx(), enum_id);
             for v in (*variants).iter() {
                 if var_id == v.id {
@@ -346,8 +347,8 @@ fn variant_opt(bcx: &Block, pat_id: ast::NodeId) -> Opt {
             }
             unreachable!();
         }
-        ast::DefFn(..) |
-        ast::DefStruct(_) => {
+        def::DefFn(..) |
+        def::DefStruct(_) => {
             return lit(UnitLikeStructLit(pat_id));
         }
         _ => {
@@ -603,7 +604,7 @@ fn enter_opt<'a, 'b>(
             ast::PatEnum(..) |
             ast::PatIdent(_, _, None) if pat_is_const(&tcx.def_map, p) => {
                 let const_def = tcx.def_map.borrow().get_copy(&p.id);
-                let const_def_id = ast_util::def_id_of_def(const_def);
+                let const_def_id = const_def.def_id();
                 if opt_eq(tcx, &lit(ConstLit(const_def_id)), opt) {
                     Some(Vec::new())
                 } else {
@@ -644,7 +645,7 @@ fn enter_opt<'a, 'b>(
                     // Look up the struct variant ID.
                     let struct_id;
                     match tcx.def_map.borrow().get_copy(&p.id) {
-                        ast::DefVariant(_, found_struct_id, _) => {
+                        def::DefVariant(_, found_struct_id, _) => {
                             struct_id = found_struct_id;
                         }
                         _ => {
@@ -918,15 +919,15 @@ fn get_options(bcx: &Block, m: &[Match], col: uint) -> Vec<Opt> {
                 // variable binding.
                 let opt_def = ccx.tcx.def_map.borrow().find_copy(&cur.id);
                 match opt_def {
-                    Some(ast::DefVariant(..)) => {
+                    Some(def::DefVariant(..)) => {
                         add_to_set(ccx.tcx(), &mut found,
                                    variant_opt(bcx, cur.id));
                     }
-                    Some(ast::DefStruct(..)) => {
+                    Some(def::DefStruct(..)) => {
                         add_to_set(ccx.tcx(), &mut found,
                                    lit(UnitLikeStructLit(cur.id)));
                     }
-                    Some(ast::DefStatic(const_did, false)) => {
+                    Some(def::DefStatic(const_did, false)) => {
                         add_to_set(ccx.tcx(), &mut found,
                                    lit(ConstLit(const_did)));
                     }
@@ -938,12 +939,12 @@ fn get_options(bcx: &Block, m: &[Match], col: uint) -> Vec<Opt> {
                 // struct-like enum variant, or a struct.
                 let opt_def = ccx.tcx.def_map.borrow().find_copy(&cur.id);
                 match opt_def {
-                    Some(ast::DefFn(..)) |
-                    Some(ast::DefVariant(..)) => {
+                    Some(def::DefFn(..)) |
+                    Some(def::DefVariant(..)) => {
                         add_to_set(ccx.tcx(), &mut found,
                                    variant_opt(bcx, cur.id));
                     }
-                    Some(ast::DefStatic(const_did, false)) => {
+                    Some(def::DefStatic(const_did, false)) => {
                         add_to_set(ccx.tcx(), &mut found,
                                    lit(ConstLit(const_did)));
                     }
@@ -1122,8 +1123,8 @@ fn any_tuple_struct_pat(bcx: &Block, m: &[Match], col: uint) -> bool {
         match pat.node {
             ast::PatEnum(_, _) => {
                 match bcx.tcx().def_map.borrow().find(&pat.id) {
-                    Some(&ast::DefFn(..)) |
-                    Some(&ast::DefStruct(..)) => true,
+                    Some(&def::DefFn(..)) |
+                    Some(&def::DefStruct(..)) => true,
                     _ => false
                 }
             }
@@ -2205,7 +2206,7 @@ fn bind_irrefutable_pat<'a>(
         ast::PatEnum(_, ref sub_pats) => {
             let opt_def = bcx.tcx().def_map.borrow().find_copy(&pat.id);
             match opt_def {
-                Some(ast::DefVariant(enum_id, var_id, _)) => {
+                Some(def::DefVariant(enum_id, var_id, _)) => {
                     let repr = adt::represent_node(bcx, pat.id);
                     let vinfo = ty::enum_variant_with_id(ccx.tcx(),
                                                          enum_id,
@@ -2222,8 +2223,8 @@ fn bind_irrefutable_pat<'a>(
                         }
                     }
                 }
-                Some(ast::DefFn(..)) |
-                Some(ast::DefStruct(..)) => {
+                Some(def::DefFn(..)) |
+                Some(def::DefStruct(..)) => {
                     match *sub_pats {
                         None => {
                             // This is a unit-like struct. Nothing to do here.
@@ -2241,7 +2242,7 @@ fn bind_irrefutable_pat<'a>(
                         }
                     }
                 }
-                Some(ast::DefStatic(_, false)) => {
+                Some(def::DefStatic(_, false)) => {
                 }
                 _ => {
                     // Nothing to do here.
diff --git a/src/librustc/middle/trans/adt.rs b/src/librustc/middle/trans/adt.rs
index 45baf07c07c..5f51f80299f 100644
--- a/src/librustc/middle/trans/adt.rs
+++ b/src/librustc/middle/trans/adt.rs
@@ -51,6 +51,8 @@ use std::num::{Bitwise};
 use std::rc::Rc;
 
 use lib::llvm::{ValueRef, True, IntEQ, IntNE};
+use middle::subst;
+use middle::subst::Subst;
 use middle::trans::_match;
 use middle::trans::build::*;
 use middle::trans::common::*;
@@ -304,10 +306,10 @@ impl Case {
     }
 }
 
-fn get_cases(tcx: &ty::ctxt, def_id: ast::DefId, substs: &ty::substs) -> Vec<Case> {
+fn get_cases(tcx: &ty::ctxt, def_id: ast::DefId, substs: &subst::Substs) -> Vec<Case> {
     ty::enum_variants(tcx, def_id).iter().map(|vi| {
         let arg_tys = vi.args.iter().map(|&raw_ty| {
-            ty::subst(tcx, substs, raw_ty)
+            raw_ty.subst(tcx, substs)
         }).collect();
         Case { discr: vi.disr_val, tys: arg_tys }
     }).collect()
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index 6096060f975..96d059c2f84 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -40,6 +40,8 @@ use middle::lint;
 use middle::astencode;
 use middle::lang_items::{LangItem, ExchangeMallocFnLangItem, StartFnLangItem};
 use middle::weak_lang_items;
+use middle::subst;
+use middle::subst::Subst;
 use middle::trans::_match;
 use middle::trans::adt;
 use middle::trans::build::*;
@@ -442,7 +444,7 @@ pub fn get_res_dtor(ccx: &CrateContext,
                     did: ast::DefId,
                     t: ty::t,
                     parent_id: ast::DefId,
-                    substs: &ty::substs)
+                    substs: &subst::Substs)
                  -> ValueRef {
     let _icx = push_ctxt("trans_res_dtor");
     let did = if did.krate != ast::LOCAL_CRATE {
@@ -463,8 +465,7 @@ pub fn get_res_dtor(ccx: &CrateContext,
     } else {
         let tcx = ccx.tcx();
         let name = csearch::get_symbol(&ccx.sess().cstore, did);
-        let class_ty = ty::subst(tcx, substs,
-                                 ty::lookup_item_type(tcx, parent_id).ty);
+        let class_ty = ty::lookup_item_type(tcx, parent_id).ty.subst(tcx, substs);
         let llty = type_of_dtor(ccx, class_ty);
         let dtor_ty = ty::mk_ctor_fn(ccx.tcx(), ast::DUMMY_NODE_ID,
                                      [glue::get_drop_glue_type(ccx, t)], ty::mk_nil());
@@ -633,7 +634,7 @@ pub fn iter_structural_ty<'r,
                     repr: &adt::Repr,
                     av: ValueRef,
                     variant: &ty::VariantInfo,
-                    substs: &ty::substs,
+                    substs: &subst::Substs,
                     f: val_and_ty_fn<'r,'b>)
                     -> &'b Block<'b> {
         let _icx = push_ctxt("iter_variant");
@@ -643,7 +644,7 @@ pub fn iter_structural_ty<'r,
         for (i, &arg) in variant.args.iter().enumerate() {
             cx = f(cx,
                    adt::trans_field_ptr(cx, repr, av, variant.disr_val, i),
-                   ty::subst(tcx, substs, arg));
+                   arg.subst(tcx, substs));
         }
         return cx;
     }
@@ -1097,11 +1098,11 @@ pub fn new_fn_ctxt<'a>(ccx: &'a CrateContext,
                        id: ast::NodeId,
                        has_env: bool,
                        output_type: ty::t,
-                       param_substs: Option<&'a param_substs>,
+                       param_substs: &'a param_substs,
                        sp: Option<Span>,
                        block_arena: &'a TypedArena<Block<'a>>)
                        -> FunctionContext<'a> {
-    for p in param_substs.iter() { p.validate(); }
+    param_substs.validate();
 
     debug!("new_fn_ctxt(path={}, id={}, param_substs={})",
            if id == -1 {
@@ -1109,7 +1110,7 @@ pub fn new_fn_ctxt<'a>(ccx: &'a CrateContext,
            } else {
                ccx.tcx.map.path_to_str(id).to_string()
            },
-           id, param_substs.map(|s| s.repr(ccx.tcx())));
+           id, param_substs.repr(ccx.tcx()));
 
     let substd_output_type = output_type.substp(ccx.tcx(), param_substs);
     let uses_outptr = type_of::return_uses_outptr(ccx, substd_output_type);
@@ -1302,7 +1303,7 @@ pub fn trans_closure(ccx: &CrateContext,
                      decl: &ast::FnDecl,
                      body: &ast::Block,
                      llfndecl: ValueRef,
-                     param_substs: Option<&param_substs>,
+                     param_substs: &param_substs,
                      id: ast::NodeId,
                      _attributes: &[ast::Attribute],
                      output_type: ty::t,
@@ -1313,7 +1314,7 @@ pub fn trans_closure(ccx: &CrateContext,
     set_uwtable(llfndecl);
 
     debug!("trans_closure(..., param_substs={})",
-           param_substs.map(|s| s.repr(ccx.tcx())));
+           param_substs.repr(ccx.tcx()));
 
     let has_env = match ty::get(ty::node_id_to_type(ccx.tcx(), id)).sty {
         ty::ty_closure(_) => true,
@@ -1326,7 +1327,7 @@ pub fn trans_closure(ccx: &CrateContext,
                           id,
                           has_env,
                           output_type,
-                          param_substs.map(|s| &*s),
+                          param_substs,
                           Some(body.span),
                           &arena);
     init_function(&fcx, false, output_type);
@@ -1402,11 +1403,11 @@ pub fn trans_fn(ccx: &CrateContext,
                 decl: &ast::FnDecl,
                 body: &ast::Block,
                 llfndecl: ValueRef,
-                param_substs: Option<&param_substs>,
+                param_substs: &param_substs,
                 id: ast::NodeId,
                 attrs: &[ast::Attribute]) {
     let _s = StatRecorder::new(ccx, ccx.tcx.map.path_to_str(id).to_string());
-    debug!("trans_fn(param_substs={})", param_substs.map(|s| s.repr(ccx.tcx())));
+    debug!("trans_fn(param_substs={})", param_substs.repr(ccx.tcx()));
     let _icx = push_ctxt("trans_fn");
     let output_type = ty::ty_fn_ret(ty::node_id_to_type(ccx.tcx(), id));
     trans_closure(ccx, decl, body, llfndecl,
@@ -1418,7 +1419,7 @@ pub fn trans_enum_variant(ccx: &CrateContext,
                           variant: &ast::Variant,
                           _args: &[ast::VariantArg],
                           disr: ty::Disr,
-                          param_substs: Option<&param_substs>,
+                          param_substs: &param_substs,
                           llfndecl: ValueRef) {
     let _icx = push_ctxt("trans_enum_variant");
 
@@ -1433,7 +1434,7 @@ pub fn trans_enum_variant(ccx: &CrateContext,
 pub fn trans_tuple_struct(ccx: &CrateContext,
                           _fields: &[ast::StructField],
                           ctor_id: ast::NodeId,
-                          param_substs: Option<&param_substs>,
+                          param_substs: &param_substs,
                           llfndecl: ValueRef) {
     let _icx = push_ctxt("trans_tuple_struct");
 
@@ -1448,7 +1449,7 @@ pub fn trans_tuple_struct(ccx: &CrateContext,
 fn trans_enum_variant_or_tuple_like_struct(ccx: &CrateContext,
                                            ctor_id: ast::NodeId,
                                            disr: ty::Disr,
-                                           param_substs: Option<&param_substs>,
+                                           param_substs: &param_substs,
                                            llfndecl: ValueRef) {
     let ctor_ty = ty::node_id_to_type(ccx.tcx(), ctor_id);
     let ctor_ty = ctor_ty.substp(ccx.tcx(), param_substs);
@@ -1463,7 +1464,7 @@ fn trans_enum_variant_or_tuple_like_struct(ccx: &CrateContext,
 
     let arena = TypedArena::new();
     let fcx = new_fn_ctxt(ccx, llfndecl, ctor_id, false, result_ty,
-                          param_substs.map(|s| &*s), None, &arena);
+                          param_substs, None, &arena);
     init_function(&fcx, false, result_ty);
 
     let arg_tys = ty::ty_fn_args(ctor_ty);
@@ -1499,7 +1500,7 @@ fn trans_enum_def(ccx: &CrateContext, enum_definition: &ast::EnumDef,
             ast::TupleVariantKind(ref args) if args.len() > 0 => {
                 let llfn = get_item_val(ccx, variant.node.id);
                 trans_enum_variant(ccx, id, variant, args.as_slice(),
-                                   disr_val, None, llfn);
+                                   disr_val, &param_substs::empty(), llfn);
             }
             ast::TupleVariantKind(_) => {
                 // Nothing to do.
@@ -1586,7 +1587,7 @@ pub fn trans_item(ccx: &CrateContext, item: &ast::Item) {
                      decl,
                      body,
                      llfn,
-                     None,
+                     &param_substs::empty(),
                      item.id,
                      item.attrs.as_slice());
         } else {
@@ -1659,7 +1660,7 @@ pub fn trans_struct_def(ccx: &CrateContext, struct_def: @ast::StructDef) {
         Some(ctor_id) if struct_def.fields.len() > 0 => {
             let llfndecl = get_item_val(ccx, ctor_id);
             trans_tuple_struct(ccx, struct_def.fields.as_slice(),
-                               ctor_id, None, llfndecl);
+                               ctor_id, &param_substs::empty(), llfndecl);
         }
         Some(_) | None => {}
     }
diff --git a/src/librustc/middle/trans/callee.rs b/src/librustc/middle/trans/callee.rs
index b5cf3fb8e73..8ee777278fe 100644
--- a/src/librustc/middle/trans/callee.rs
+++ b/src/librustc/middle/trans/callee.rs
@@ -21,6 +21,9 @@ use driver::session;
 use lib::llvm::ValueRef;
 use lib::llvm::llvm;
 use metadata::csearch;
+use middle::def;
+use middle::subst;
+use middle::subst::Subst;
 use middle::trans::base;
 use middle::trans::base::*;
 use middle::trans::build::*;
@@ -39,7 +42,6 @@ use middle::trans::monomorphize;
 use middle::trans::type_of;
 use middle::trans::foreign;
 use middle::ty;
-use middle::subst::Subst;
 use middle::typeck;
 use middle::typeck::coherence::make_substs_for_receiver_types;
 use middle::typeck::MethodCall;
@@ -113,42 +115,42 @@ fn trans<'a>(bcx: &'a Block<'a>, expr: &ast::Expr) -> Callee<'a> {
         return Callee {bcx: bcx, data: Fn(llfn)};
     }
 
-    fn trans_def<'a>(bcx: &'a Block<'a>, def: ast::Def, ref_expr: &ast::Expr)
+    fn trans_def<'a>(bcx: &'a Block<'a>, def: def::Def, ref_expr: &ast::Expr)
                  -> Callee<'a> {
         match def {
-            ast::DefFn(did, _) |
-            ast::DefStaticMethod(did, ast::FromImpl(_), _) => {
+            def::DefFn(did, _) |
+            def::DefStaticMethod(did, def::FromImpl(_), _) => {
                 fn_callee(bcx, trans_fn_ref(bcx, did, ExprId(ref_expr.id)))
             }
-            ast::DefStaticMethod(impl_did,
-                                   ast::FromTrait(trait_did),
-                                   _) => {
+            def::DefStaticMethod(impl_did,
+                                 def::FromTrait(trait_did),
+                                 _) => {
                 fn_callee(bcx, meth::trans_static_method_callee(bcx, impl_did,
                                                                 trait_did,
                                                                 ref_expr.id))
             }
-            ast::DefVariant(tid, vid, _) => {
+            def::DefVariant(tid, vid, _) => {
                 // nullary variants are not callable
                 assert!(ty::enum_variant_with_id(bcx.tcx(),
                                                       tid,
                                                       vid).args.len() > 0u);
                 fn_callee(bcx, trans_fn_ref(bcx, vid, ExprId(ref_expr.id)))
             }
-            ast::DefStruct(def_id) => {
+            def::DefStruct(def_id) => {
                 fn_callee(bcx, trans_fn_ref(bcx, def_id, ExprId(ref_expr.id)))
             }
-            ast::DefStatic(..) |
-            ast::DefArg(..) |
-            ast::DefLocal(..) |
-            ast::DefBinding(..) |
-            ast::DefUpvar(..) => {
+            def::DefStatic(..) |
+            def::DefArg(..) |
+            def::DefLocal(..) |
+            def::DefBinding(..) |
+            def::DefUpvar(..) => {
                 datum_callee(bcx, ref_expr)
             }
-            ast::DefMod(..) | ast::DefForeignMod(..) | ast::DefTrait(..) |
-            ast::DefTy(..) | ast::DefPrimTy(..) |
-            ast::DefUse(..) | ast::DefTyParamBinder(..) |
-            ast::DefRegion(..) | ast::DefLabel(..) | ast::DefTyParam(..) |
-            ast::DefSelfTy(..) | ast::DefMethod(..) => {
+            def::DefMod(..) | def::DefForeignMod(..) | def::DefTrait(..) |
+            def::DefTy(..) | def::DefPrimTy(..) |
+            def::DefUse(..) | def::DefTyParamBinder(..) |
+            def::DefRegion(..) | def::DefLabel(..) | def::DefTyParam(..) |
+            def::DefSelfTy(..) | def::DefMethod(..) => {
                 bcx.tcx().sess.span_bug(
                     ref_expr.span,
                     format!("cannot translate def {:?} \
@@ -184,8 +186,8 @@ pub fn trans_fn_ref(bcx: &Block, def_id: ast::DefId, node: ExprOrMethodCall) ->
 fn trans_fn_ref_with_vtables_to_callee<'a>(bcx: &'a Block<'a>,
                                            def_id: ast::DefId,
                                            ref_id: ast::NodeId,
-                                           substs: ty::substs,
-                                           vtables: Option<typeck::vtable_res>)
+                                           substs: subst::Substs,
+                                           vtables: typeck::vtable_res)
                                            -> Callee<'a> {
     Callee {bcx: bcx,
             data: Fn(trans_fn_ref_with_vtables(bcx, def_id, ExprId(ref_id),
@@ -195,9 +197,10 @@ fn trans_fn_ref_with_vtables_to_callee<'a>(bcx: &'a Block<'a>,
 fn resolve_default_method_vtables(bcx: &Block,
                                   impl_id: ast::DefId,
                                   method: &ty::Method,
-                                  substs: &ty::substs,
-                                  impl_vtables: Option<typeck::vtable_res>)
-                          -> (typeck::vtable_res, typeck::vtable_param_res) {
+                                  substs: &subst::Substs,
+                                  impl_vtables: typeck::vtable_res)
+                          -> (typeck::vtable_res, typeck::vtable_param_res)
+{
 
     // Get the vtables that the impl implements the trait at
     let impl_res = ty::lookup_impl_vtables(bcx.tcx(), impl_id);
@@ -211,27 +214,15 @@ fn resolve_default_method_vtables(bcx: &Block,
     };
 
     let mut param_vtables = resolve_vtables_under_param_substs(
-        bcx.tcx(), Some(&param_substs), impl_res.trait_vtables.as_slice());
+        bcx.tcx(), &param_substs, impl_res.trait_vtables.as_slice());
 
     // Now we pull any vtables for parameters on the actual method.
     let num_method_vtables = method.generics.type_param_defs().len();
-    match impl_vtables {
-        Some(ref vtables) => {
-            let num_impl_type_parameters =
-                vtables.len() - num_method_vtables;
-            param_vtables.push_all(vtables.tailn(num_impl_type_parameters))
-        },
-        None => {
-            param_vtables.extend(range(0, num_method_vtables).map(
-                |_| -> typeck::vtable_param_res {
-                    Vec::new()
-                }
-            ))
-        }
-    }
+    let num_impl_type_parameters = impl_vtables.len() - num_method_vtables;
+    param_vtables.push_all(impl_vtables.tailn(num_impl_type_parameters));
 
     let self_vtables = resolve_param_vtables_under_param_substs(
-        bcx.tcx(), Some(&param_substs), impl_res.self_vtables.as_slice());
+        bcx.tcx(), &param_substs, impl_res.self_vtables.as_slice());
 
     (param_vtables, self_vtables)
 }
@@ -241,8 +232,8 @@ pub fn trans_fn_ref_with_vtables(
         bcx: &Block,       //
         def_id: ast::DefId,   // def id of fn
         node: ExprOrMethodCall,  // node id of use of fn; may be zero if N/A
-        substs: ty::substs, // values for fn's ty params
-        vtables: Option<typeck::vtable_res>) // vtables for the call
+        substs: subst::Substs, // values for fn's ty params
+        vtables: typeck::vtable_res) // vtables for the call
      -> ValueRef {
     /*!
      * Translates a reference to a fn/method item, monomorphizing and
@@ -334,7 +325,7 @@ pub fn trans_fn_ref_with_vtables(
                    self_vtables.repr(tcx), param_vtables.repr(tcx));
 
             (true, source_id,
-             new_substs, Some(self_vtables), Some(param_vtables))
+             new_substs, Some(self_vtables), param_vtables)
         }
     };
 
@@ -504,8 +495,8 @@ pub fn trans_lang_call<'a>(
                                 trans_fn_ref_with_vtables_to_callee(bcx,
                                                                     did,
                                                                     0,
-                                                                    ty::substs::empty(),
-                                                                    None)
+                                                                    subst::Substs::empty(),
+                                                                    Vec::new())
                              },
                              ArgVals(args),
                              dest)
diff --git a/src/librustc/middle/trans/closure.rs b/src/librustc/middle/trans/closure.rs
index 9ca66f4c3b0..f956b58031c 100644
--- a/src/librustc/middle/trans/closure.rs
+++ b/src/librustc/middle/trans/closure.rs
@@ -13,6 +13,7 @@ use back::abi;
 use back::link::mangle_internal_name_by_path_and_seq;
 use driver::config::FullDebugInfo;
 use lib::llvm::ValueRef;
+use middle::def;
 use middle::freevars;
 use middle::lang_items::ClosureExchangeMallocFnLangItem;
 use middle::trans::base::*;
@@ -30,7 +31,6 @@ use util::ppaux::ty_to_str;
 
 use arena::TypedArena;
 use syntax::ast;
-use syntax::ast_util;
 
 // ___Good to know (tm)__________________________________________________
 //
@@ -282,7 +282,7 @@ fn load_environment<'a>(bcx: &'a Block<'a>,
             ty::RegionTraitStore(..) => { upvarptr = Load(bcx, upvarptr); }
             ty::UniqTraitStore => {}
         }
-        let def_id = ast_util::def_id_of_def(freevar.def);
+        let def_id = freevar.def.def_id();
 
         bcx.fcx.llupvars.borrow_mut().insert(def_id.node, upvarptr);
 
@@ -368,13 +368,13 @@ pub fn trans_expr_fn<'a>(
 
 pub fn get_wrapper_for_bare_fn(ccx: &CrateContext,
                                closure_ty: ty::t,
-                               def: ast::Def,
+                               def: def::Def,
                                fn_ptr: ValueRef,
                                is_local: bool) -> ValueRef {
 
     let def_id = match def {
-        ast::DefFn(did, _) | ast::DefStaticMethod(did, _, _) |
-        ast::DefVariant(_, did, _) | ast::DefStruct(did) => did,
+        def::DefFn(did, _) | def::DefStaticMethod(did, _, _) |
+        def::DefVariant(_, did, _) | def::DefStruct(did) => did,
         _ => {
             ccx.sess().bug(format!("get_wrapper_for_bare_fn: \
                                     expected a statically resolved fn, got \
@@ -421,7 +421,9 @@ pub fn get_wrapper_for_bare_fn(ccx: &CrateContext,
     let _icx = push_ctxt("closure::get_wrapper_for_bare_fn");
 
     let arena = TypedArena::new();
-    let fcx = new_fn_ctxt(ccx, llfn, -1, true, f.sig.output, None, None, &arena);
+    let empty_param_substs = param_substs::empty();
+    let fcx = new_fn_ctxt(ccx, llfn, -1, true, f.sig.output,
+                          &empty_param_substs, None, &arena);
     init_function(&fcx, true, f.sig.output);
     let bcx = fcx.entry_bcx.borrow().clone().unwrap();
 
@@ -453,7 +455,7 @@ pub fn get_wrapper_for_bare_fn(ccx: &CrateContext,
 
 pub fn make_closure_from_bare_fn<'a>(bcx: &'a Block<'a>,
                                      closure_ty: ty::t,
-                                     def: ast::Def,
+                                     def: def::Def,
                                      fn_ptr: ValueRef)
                                      -> DatumBlock<'a, Expr>  {
     let scratch = rvalue_scratch_datum(bcx, closure_ty, "__adjust");
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index 5b6815dbb6b..1bcf47531dd 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -17,14 +17,16 @@ use lib::llvm::{ValueRef, BasicBlockRef, BuilderRef};
 use lib::llvm::{True, False, Bool};
 use lib::llvm::llvm;
 use lib;
+use middle::def;
 use middle::lang_items::LangItem;
+use middle::subst;
+use middle::subst::Subst;
 use middle::trans::build;
 use middle::trans::cleanup;
 use middle::trans::datum;
 use middle::trans::debuginfo;
 use middle::trans::type_::Type;
 use middle::ty;
-use middle::subst::Subst;
 use middle::typeck;
 use util::ppaux::Repr;
 use util::nodemap::NodeMap;
@@ -177,12 +179,20 @@ pub type ExternMap = HashMap<String, ValueRef>;
 // Here `self_ty` is the real type of the self parameter to this method. It
 // will only be set in the case of default methods.
 pub struct param_substs {
-    pub substs: ty::substs,
-    pub vtables: Option<typeck::vtable_res>,
+    pub substs: subst::Substs,
+    pub vtables: typeck::vtable_res,
     pub self_vtables: Option<typeck::vtable_param_res>
 }
 
 impl param_substs {
+    pub fn empty() -> param_substs {
+        param_substs {
+            substs: subst::Substs::trans_empty(),
+            vtables: Vec::new(),
+            self_vtables: None
+        }
+    }
+
     pub fn validate(&self) {
         for t in self.substs.tps.iter() {
             assert!(!ty::type_needs_infer(*t));
@@ -204,21 +214,13 @@ impl Repr for param_substs {
 }
 
 pub trait SubstP {
-    fn substp(&self, tcx: &ty::ctxt, param_substs: Option<&param_substs>)
+    fn substp(&self, tcx: &ty::ctxt, param_substs: &param_substs)
               -> Self;
 }
 
 impl<T:Subst+Clone> SubstP for T {
-    fn substp(&self, tcx: &ty::ctxt, param_substs: Option<&param_substs>)
-              -> T {
-        match param_substs {
-            Some(substs) => {
-                self.subst(tcx, &substs.substs)
-            }
-            None => {
-                (*self).clone()
-            }
-        }
+    fn substp(&self, tcx: &ty::ctxt, substs: &param_substs) -> T {
+        self.subst(tcx, &substs.substs)
     }
 }
 
@@ -279,7 +281,7 @@ pub struct FunctionContext<'a> {
 
     // If this function is being monomorphized, this contains the type
     // substitutions used.
-    pub param_substs: Option<&'a param_substs>,
+    pub param_substs: &'a param_substs,
 
     // The source span and nesting context where this function comes from, for
     // error reporting and symbol generation.
@@ -453,7 +455,7 @@ impl<'a> Block<'a> {
         e.repr(self.tcx())
     }
 
-    pub fn def(&self, nid: ast::NodeId) -> ast::Def {
+    pub fn def(&self, nid: ast::NodeId) -> def::Def {
         match self.tcx().def_map.borrow().find(&nid) {
             Some(&v) => v,
             None => {
@@ -695,16 +697,7 @@ pub fn is_null(val: ValueRef) -> bool {
 }
 
 pub fn monomorphize_type(bcx: &Block, t: ty::t) -> ty::t {
-    match bcx.fcx.param_substs {
-        Some(ref substs) => {
-            ty::subst(bcx.tcx(), &substs.substs, t)
-        }
-        _ => {
-            assert!(!ty::type_has_params(t));
-            assert!(!ty::type_has_self(t));
-            t
-        }
-    }
+    t.subst(bcx.tcx(), &bcx.fcx.param_substs.substs)
 }
 
 pub fn node_id_type(bcx: &Block, id: ast::NodeId) -> ty::t {
@@ -733,7 +726,7 @@ pub enum ExprOrMethodCall {
 
 pub fn node_id_substs(bcx: &Block,
                       node: ExprOrMethodCall)
-                      -> ty::substs {
+                      -> subst::Substs {
     let tcx = bcx.tcx();
 
     let substs = match node {
@@ -757,10 +750,10 @@ pub fn node_id_substs(bcx: &Block,
 }
 
 pub fn node_vtables(bcx: &Block, id: typeck::MethodCall)
-                 -> Option<typeck::vtable_res> {
+                 -> typeck::vtable_res {
     bcx.tcx().vtable_map.borrow().find(&id).map(|vts| {
         resolve_vtables_in_fn_ctxt(bcx.fcx, vts.as_slice())
-    })
+    }).unwrap_or_else(|| Vec::new())
 }
 
 // Apply the typaram substitutions in the FunctionContext to some
@@ -774,7 +767,7 @@ pub fn resolve_vtables_in_fn_ctxt(fcx: &FunctionContext,
 }
 
 pub fn resolve_vtables_under_param_substs(tcx: &ty::ctxt,
-                                          param_substs: Option<&param_substs>,
+                                          param_substs: &param_substs,
                                           vts: &[typeck::vtable_param_res])
                                           -> typeck::vtable_res {
     vts.iter().map(|ds| {
@@ -786,7 +779,7 @@ pub fn resolve_vtables_under_param_substs(tcx: &ty::ctxt,
 
 pub fn resolve_param_vtables_under_param_substs(
     tcx: &ty::ctxt,
-    param_substs: Option<&param_substs>,
+    param_substs: &param_substs,
     ds: &[typeck::vtable_origin])
     -> typeck::vtable_param_res {
     ds.iter().map(|d| {
@@ -799,7 +792,7 @@ pub fn resolve_param_vtables_under_param_substs(
 
 
 pub fn resolve_vtable_under_param_substs(tcx: &ty::ctxt,
-                                         param_substs: Option<&param_substs>,
+                                         param_substs: &param_substs,
                                          vt: &typeck::vtable_origin)
                                          -> typeck::vtable_origin {
     match *vt {
@@ -810,16 +803,7 @@ pub fn resolve_vtable_under_param_substs(tcx: &ty::ctxt,
                 resolve_vtables_under_param_substs(tcx, param_substs, sub.as_slice()))
         }
         typeck::vtable_param(n_param, n_bound) => {
-            match param_substs {
-                Some(substs) => {
-                    find_vtable(tcx, substs, n_param, n_bound)
-                }
-                _ => {
-                    tcx.sess.bug(format!(
-                        "resolve_vtable_under_param_substs: asked to lookup \
-                         but no vtables in the fn_ctxt!").as_slice())
-                }
-            }
+            find_vtable(tcx, param_substs, n_param, n_bound)
         }
     }
 }
@@ -835,9 +819,7 @@ pub fn find_vtable(tcx: &ty::ctxt,
     let param_bounds = match n_param {
         typeck::param_self => ps.self_vtables.as_ref().expect("self vtables missing"),
         typeck::param_numbered(n) => {
-            let tables = ps.vtables.as_ref()
-                .expect("vtables missing where they are needed");
-            tables.get(n)
+            ps.vtables.get(n)
         }
     };
     param_bounds.get(n_bound).clone()
diff --git a/src/librustc/middle/trans/consts.rs b/src/librustc/middle/trans/consts.rs
index 8b43e99b6ac..ac6e9ca6c64 100644
--- a/src/librustc/middle/trans/consts.rs
+++ b/src/librustc/middle/trans/consts.rs
@@ -17,6 +17,7 @@ use lib::llvm::{IntEQ, IntNE, IntUGT, IntUGE, IntULT, IntULE, IntSGT, IntSGE, In
 
 use metadata::csearch;
 use middle::const_eval;
+use middle::def;
 use middle::trans::adt;
 use middle::trans::base;
 use middle::trans::base::push_ctxt;
@@ -617,7 +618,7 @@ fn const_expr_unadjusted(cx: &CrateContext, e: &ast::Expr,
 
             let opt_def = cx.tcx().def_map.borrow().find_copy(&e.id);
             match opt_def {
-                Some(ast::DefFn(def_id, _fn_style)) => {
+                Some(def::DefFn(def_id, _fn_style)) => {
                     if !ast_util::is_local(def_id) {
                         let ty = csearch::get_type(cx.tcx(), def_id).ty;
                         (base::trans_external_path(cx, def_id, ty), true)
@@ -626,10 +627,10 @@ fn const_expr_unadjusted(cx: &CrateContext, e: &ast::Expr,
                         (base::get_item_val(cx, def_id.node), true)
                     }
                 }
-                Some(ast::DefStatic(def_id, false)) => {
+                Some(def::DefStatic(def_id, false)) => {
                     get_const_val(cx, def_id)
                 }
-                Some(ast::DefVariant(enum_did, variant_did, _)) => {
+                Some(def::DefVariant(enum_did, variant_did, _)) => {
                     let ety = ty::expr_ty(cx.tcx(), e);
                     let repr = adt::represent_type(cx, ety);
                     let vinfo = ty::enum_variant_with_id(cx.tcx(),
@@ -637,7 +638,7 @@ fn const_expr_unadjusted(cx: &CrateContext, e: &ast::Expr,
                                                          variant_did);
                     (adt::trans_const(cx, &*repr, vinfo.disr_val, []), true)
                 }
-                Some(ast::DefStruct(_)) => {
+                Some(def::DefStruct(_)) => {
                     let ety = ty::expr_ty(cx.tcx(), e);
                     let llty = type_of::type_of(cx, ety);
                     (C_null(llty), true)
@@ -650,14 +651,14 @@ fn const_expr_unadjusted(cx: &CrateContext, e: &ast::Expr,
           ast::ExprCall(callee, ref args) => {
               let opt_def = cx.tcx().def_map.borrow().find_copy(&callee.id);
               match opt_def {
-                  Some(ast::DefStruct(_)) => {
+                  Some(def::DefStruct(_)) => {
                       let ety = ty::expr_ty(cx.tcx(), e);
                       let repr = adt::represent_type(cx, ety);
                       let (arg_vals, inlineable) = map_list(args.as_slice());
                       (adt::trans_const(cx, &*repr, 0, arg_vals.as_slice()),
                        inlineable)
                   }
-                  Some(ast::DefVariant(enum_did, variant_did, _)) => {
+                  Some(def::DefVariant(enum_did, variant_did, _)) => {
                       let ety = ty::expr_ty(cx.tcx(), e);
                       let repr = adt::represent_type(cx, ety);
                       let vinfo = ty::enum_variant_with_id(cx.tcx(),
diff --git a/src/librustc/middle/trans/controlflow.rs b/src/librustc/middle/trans/controlflow.rs
index eac7af56ed4..ea152c34808 100644
--- a/src/librustc/middle/trans/controlflow.rs
+++ b/src/librustc/middle/trans/controlflow.rs
@@ -10,6 +10,7 @@
 
 use lib::llvm::*;
 use driver::config::FullDebugInfo;
+use middle::def;
 use middle::lang_items::{FailFnLangItem, FailBoundsCheckFnLangItem};
 use middle::trans::base::*;
 use middle::trans::build::*;
@@ -288,7 +289,7 @@ pub fn trans_break_cont<'a>(bcx: &'a Block<'a>,
         None => fcx.top_loop_scope(),
         Some(_) => {
             match bcx.tcx().def_map.borrow().find(&expr_id) {
-                Some(&ast::DefLabel(loop_id)) => loop_id,
+                Some(&def::DefLabel(loop_id)) => loop_id,
                 ref r => {
                     bcx.tcx().sess.bug(format!("{:?} in def-map for label",
                                                r).as_slice())
diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs
index 6e0d6d491a5..b709fa52cf7 100644
--- a/src/librustc/middle/trans/debuginfo.rs
+++ b/src/librustc/middle/trans/debuginfo.rs
@@ -131,6 +131,7 @@ use lib::llvm::llvm;
 use lib::llvm::{ModuleRef, ContextRef, ValueRef};
 use lib::llvm::debuginfo::*;
 use metadata::csearch;
+use middle::subst;
 use middle::trans::adt;
 use middle::trans::common::*;
 use middle::trans::datum::{Datum, Lvalue};
@@ -620,7 +621,7 @@ pub fn start_emitting_source_locations(fcx: &FunctionContext) {
 /// indicates why no debuginfo should be created for the function.
 pub fn create_function_debug_context(cx: &CrateContext,
                                      fn_ast_id: ast::NodeId,
-                                     param_substs: Option<&param_substs>,
+                                     param_substs: &param_substs,
                                      llfn: ValueRef) -> FunctionDebugContext {
     if cx.sess().opts.debuginfo == NoDebugInfo {
         return FunctionDebugContext { repr: DebugInfoDisabled };
@@ -787,7 +788,7 @@ pub fn create_function_debug_context(cx: &CrateContext,
     fn get_function_signature(cx: &CrateContext,
                               fn_ast_id: ast::NodeId,
                               fn_decl: &ast::FnDecl,
-                              param_substs: Option<&param_substs>,
+                              param_substs: &param_substs,
                               error_span: Span) -> DIArray {
         if cx.sess().opts.debuginfo == LimitedDebugInfo {
             return create_DIArray(DIB(cx), []);
@@ -822,14 +823,11 @@ pub fn create_function_debug_context(cx: &CrateContext,
 
     fn get_template_parameters(cx: &CrateContext,
                                generics: &ast::Generics,
-                               param_substs: Option<&param_substs>,
+                               param_substs: &param_substs,
                                file_metadata: DIFile,
                                name_to_append_suffix_to: &mut String)
                                -> DIArray {
-        let self_type = match param_substs {
-            Some(param_substs) => param_substs.substs.self_ty,
-            _ => None
-        };
+        let self_type = param_substs.substs.self_ty;
 
         // Only true for static default methods:
         let has_self_type = self_type.is_some();
@@ -883,13 +881,7 @@ pub fn create_function_debug_context(cx: &CrateContext,
         }
 
         // Handle other generic parameters
-        let actual_types = match param_substs {
-            Some(param_substs) => &param_substs.substs.tps,
-            None => {
-                return create_DIArray(DIB(cx), template_params.as_slice());
-            }
-        };
-
+        let actual_types = &param_substs.substs.tps;
         for (index, &ast::TyParam{ ident: ident, .. }) in generics.ty_params.iter().enumerate() {
             let actual_type = *actual_types.get(index);
             // Add actual type name to <...> clause of function name
@@ -1356,7 +1348,7 @@ impl StructMemberDescriptionFactory {
 fn prepare_struct_metadata(cx: &CrateContext,
                            struct_type: ty::t,
                            def_id: ast::DefId,
-                           substs: &ty::substs,
+                           substs: &subst::Substs,
                            span: Span)
                         -> RecursiveTypeDescription {
     let struct_name = ppaux::ty_to_str(cx.tcx(), struct_type);
@@ -2251,7 +2243,7 @@ fn subroutine_type_metadata(cx: &CrateContext,
 fn trait_metadata(cx: &CrateContext,
                   def_id: ast::DefId,
                   trait_type: ty::t,
-                  substs: &ty::substs,
+                  substs: &subst::Substs,
                   trait_store: ty::TraitStore,
                   _: &ty::BuiltinBounds)
                -> DIType {
diff --git a/src/librustc/middle/trans/expr.rs b/src/librustc/middle/trans/expr.rs
index 6241c1222f9..d9ae9b08381 100644
--- a/src/librustc/middle/trans/expr.rs
+++ b/src/librustc/middle/trans/expr.rs
@@ -37,6 +37,7 @@ use back::abi;
 use lib::llvm::{ValueRef, llvm};
 use lib;
 use metadata::csearch;
+use middle::def;
 use middle::lang_items::MallocFnLangItem;
 use middle::trans::_match;
 use middle::trans::adt;
@@ -499,18 +500,18 @@ fn trans_index<'a>(bcx: &'a Block<'a>,
 
 fn trans_def<'a>(bcx: &'a Block<'a>,
                  ref_expr: &ast::Expr,
-                 def: ast::Def)
+                 def: def::Def)
                  -> DatumBlock<'a, Expr>
 {
     //! Translates a reference to a path.
 
     let _icx = push_ctxt("trans_def_lvalue");
     match def {
-        ast::DefFn(..) | ast::DefStaticMethod(..) |
-        ast::DefStruct(_) | ast::DefVariant(..) => {
+        def::DefFn(..) | def::DefStaticMethod(..) |
+        def::DefStruct(_) | def::DefVariant(..) => {
             trans_def_fn_unadjusted(bcx, ref_expr, def)
         }
-        ast::DefStatic(did, _) => {
+        def::DefStatic(did, _) => {
             let const_ty = expr_ty(bcx, ref_expr);
 
             fn get_did(ccx: &CrateContext, did: ast::DefId)
@@ -775,7 +776,7 @@ fn trans_rvalue_dps_unadjusted<'a>(bcx: &'a Block<'a>,
 fn trans_def_dps_unadjusted<'a>(
                             bcx: &'a Block<'a>,
                             ref_expr: &ast::Expr,
-                            def: ast::Def,
+                            def: def::Def,
                             dest: Dest)
                             -> &'a Block<'a> {
     let _icx = push_ctxt("trans_def_dps_unadjusted");
@@ -786,7 +787,7 @@ fn trans_def_dps_unadjusted<'a>(
     };
 
     match def {
-        ast::DefVariant(tid, vid, _) => {
+        def::DefVariant(tid, vid, _) => {
             let variant_info = ty::enum_variant_with_id(bcx.tcx(), tid, vid);
             if variant_info.args.len() > 0u {
                 // N-ary variant.
@@ -802,7 +803,7 @@ fn trans_def_dps_unadjusted<'a>(
                 return bcx;
             }
         }
-        ast::DefStruct(_) => {
+        def::DefStruct(_) => {
             let ty = expr_ty(bcx, ref_expr);
             match ty::get(ty).sty {
                 ty::ty_struct(did, _) if ty::has_dtor(bcx.tcx(), did) => {
@@ -823,16 +824,16 @@ fn trans_def_dps_unadjusted<'a>(
 
 fn trans_def_fn_unadjusted<'a>(bcx: &'a Block<'a>,
                                ref_expr: &ast::Expr,
-                               def: ast::Def) -> DatumBlock<'a, Expr> {
+                               def: def::Def) -> DatumBlock<'a, Expr> {
     let _icx = push_ctxt("trans_def_datum_unadjusted");
 
     let llfn = match def {
-        ast::DefFn(did, _) |
-        ast::DefStruct(did) | ast::DefVariant(_, did, _) |
-        ast::DefStaticMethod(did, ast::FromImpl(_), _) => {
+        def::DefFn(did, _) |
+        def::DefStruct(did) | def::DefVariant(_, did, _) |
+        def::DefStaticMethod(did, def::FromImpl(_), _) => {
             callee::trans_fn_ref(bcx, did, ExprId(ref_expr.id))
         }
-        ast::DefStaticMethod(impl_did, ast::FromTrait(trait_did), _) => {
+        def::DefStaticMethod(impl_did, def::FromTrait(trait_did), _) => {
             meth::trans_static_method_callee(bcx, impl_did,
                                              trait_did, ref_expr.id)
         }
@@ -849,7 +850,7 @@ fn trans_def_fn_unadjusted<'a>(bcx: &'a Block<'a>,
 }
 
 pub fn trans_local_var<'a>(bcx: &'a Block<'a>,
-                           def: ast::Def)
+                           def: def::Def)
                            -> Datum<Lvalue> {
     /*!
      * Translates a reference to a local variable or argument.
@@ -859,7 +860,7 @@ pub fn trans_local_var<'a>(bcx: &'a Block<'a>,
     let _icx = push_ctxt("trans_local_var");
 
     return match def {
-        ast::DefUpvar(nid, _, _, _) => {
+        def::DefUpvar(nid, _, _, _) => {
             // Can't move upvars, so this is never a ZeroMemLastUse.
             let local_ty = node_id_type(bcx, nid);
             match bcx.fcx.llupvars.borrow().find(&nid) {
@@ -871,10 +872,10 @@ pub fn trans_local_var<'a>(bcx: &'a Block<'a>,
                 }
             }
         }
-        ast::DefArg(nid, _) => {
+        def::DefArg(nid, _) => {
             take_local(bcx, &*bcx.fcx.llargs.borrow(), nid)
         }
-        ast::DefLocal(nid, _) | ast::DefBinding(nid, _) => {
+        def::DefLocal(nid, _) | def::DefBinding(nid, _) => {
             take_local(bcx, &*bcx.fcx.lllocals.borrow(), nid)
         }
         _ => {
@@ -931,7 +932,7 @@ pub fn with_field_tys<R>(tcx: &ty::ctxt,
                 Some(node_id) => {
                     let def = tcx.def_map.borrow().get_copy(&node_id);
                     match def {
-                        ast::DefVariant(enum_id, variant_id, _) => {
+                        def::DefVariant(enum_id, variant_id, _) => {
                             let variant_info = ty::enum_variant_with_id(
                                 tcx, enum_id, variant_id);
                             op(variant_info.disr_val,
diff --git a/src/librustc/middle/trans/foreign.rs b/src/librustc/middle/trans/foreign.rs
index 96fb8ac0e98..6f217d83a62 100644
--- a/src/librustc/middle/trans/foreign.rs
+++ b/src/librustc/middle/trans/foreign.rs
@@ -570,7 +570,7 @@ pub fn trans_rust_fn_with_foreign_abi(ccx: &CrateContext,
 
         let llfn = base::decl_internal_rust_fn(ccx, t, ps.as_slice());
         base::set_llvm_fn_attrs(attrs, llfn);
-        base::trans_fn(ccx, decl, body, llfn, None, id, []);
+        base::trans_fn(ccx, decl, body, llfn, &param_substs::empty(), id, []);
         llfn
     }
 
diff --git a/src/librustc/middle/trans/glue.rs b/src/librustc/middle/trans/glue.rs
index 80ccf810e5a..96aa7267d23 100644
--- a/src/librustc/middle/trans/glue.rs
+++ b/src/librustc/middle/trans/glue.rs
@@ -18,6 +18,7 @@ use back::link::*;
 use lib::llvm::{llvm, ValueRef, True};
 use lib;
 use middle::lang_items::{FreeFnLangItem, ExchangeFreeFnLangItem};
+use middle::subst;
 use middle::trans::adt;
 use middle::trans::base::*;
 use middle::trans::build::*;
@@ -229,7 +230,7 @@ fn trans_struct_drop_flag<'a>(bcx: &'a Block<'a>,
                               v0: ValueRef,
                               dtor_did: ast::DefId,
                               class_did: ast::DefId,
-                              substs: &ty::substs)
+                              substs: &subst::Substs)
                               -> &'a Block<'a> {
     let repr = adt::represent_type(bcx.ccx(), t);
     let drop_flag = adt::trans_drop_flag_ptr(bcx, &*repr, v0);
@@ -243,7 +244,7 @@ fn trans_struct_drop<'a>(bcx: &'a Block<'a>,
                          v0: ValueRef,
                          dtor_did: ast::DefId,
                          class_did: ast::DefId,
-                         substs: &ty::substs)
+                         substs: &subst::Substs)
                          -> &'a Block<'a> {
     let repr = adt::represent_type(bcx.ccx(), t);
 
@@ -478,7 +479,9 @@ fn make_generic_glue(ccx: &CrateContext,
     let _s = StatRecorder::new(ccx, glue_name);
 
     let arena = TypedArena::new();
-    let fcx = new_fn_ctxt(ccx, llfn, -1, false, ty::mk_nil(), None, None, &arena);
+    let empty_param_substs = param_substs::empty();
+    let fcx = new_fn_ctxt(ccx, llfn, -1, false, ty::mk_nil(),
+                          &empty_param_substs, None, &arena);
 
     init_function(&fcx, false, ty::mk_nil());
 
diff --git a/src/librustc/middle/trans/inline.rs b/src/librustc/middle/trans/inline.rs
index fa4a62319db..c14ff7a49ea 100644
--- a/src/librustc/middle/trans/inline.rs
+++ b/src/librustc/middle/trans/inline.rs
@@ -131,7 +131,8 @@ pub fn maybe_instantiate_inline(ccx: &CrateContext, fn_id: ast::DefId)
 
           if num_type_params == 0 {
               let llfn = get_item_val(ccx, mth.id);
-              trans_fn(ccx, mth.decl, mth.body, llfn, None, mth.id, []);
+              trans_fn(ccx, mth.decl, mth.body, llfn,
+                       &param_substs::empty(), mth.id, []);
           }
           local_def(mth.id)
         }
diff --git a/src/librustc/middle/trans/intrinsic.rs b/src/librustc/middle/trans/intrinsic.rs
index eea8ce44a9d..0719288bb02 100644
--- a/src/librustc/middle/trans/intrinsic.rs
+++ b/src/librustc/middle/trans/intrinsic.rs
@@ -192,7 +192,7 @@ pub fn trans_intrinsic(ccx: &CrateContext,
 
     let arena = TypedArena::new();
     let fcx = new_fn_ctxt(ccx, decl, item.id, false, output_type,
-                          Some(&*substs), Some(item.span), &arena);
+                          substs, Some(item.span), &arena);
     init_function(&fcx, true, output_type);
 
     set_always_inline(fcx.llfn);
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index e735fd21034..2beb3be3d27 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -14,6 +14,7 @@ use lib::llvm::llvm;
 use lib::llvm::ValueRef;
 use lib;
 use metadata::csearch;
+use middle::subst;
 use middle::trans::base::*;
 use middle::trans::build::*;
 use middle::trans::callee::*;
@@ -67,7 +68,7 @@ pub fn trans_impl(ccx: &CrateContext,
         if method.generics.ty_params.len() == 0u {
             let llfn = get_item_val(ccx, method.id);
             trans_fn(ccx, method.decl, method.body,
-                     llfn, None, method.id, []);
+                     llfn, &param_substs::empty(), method.id, []);
         } else {
             let mut v = TransItemVisitor{ ccx: ccx };
             visit::walk_method_helper(&mut v, *method, ());
@@ -109,19 +110,13 @@ pub fn trans_method_callee<'a>(
             param_num: p,
             bound_num: b
         }) => {
-            match bcx.fcx.param_substs {
-                Some(substs) => {
-                    ty::populate_implementations_for_trait_if_necessary(
-                        bcx.tcx(),
-                        trait_id);
-
-                    let vtbl = find_vtable(bcx.tcx(), substs, p, b);
-                    trans_monomorphized_callee(bcx, method_call,
-                                               trait_id, off, vtbl)
-                }
-                // how to get rid of this?
-                None => fail!("trans_method_callee: missing param_substs")
-            }
+            ty::populate_implementations_for_trait_if_necessary(
+                bcx.tcx(),
+                trait_id);
+
+            let vtbl = find_vtable(bcx.tcx(), bcx.fcx.param_substs, p, b);
+            trans_monomorphized_callee(bcx, method_call,
+                                       trait_id, off, vtbl)
         }
 
         typeck::MethodObject(ref mt) => {
@@ -208,7 +203,7 @@ pub fn trans_static_method_callee(bcx: &Block,
 
             let llfn = trans_fn_ref_with_vtables(bcx, mth_id, ExprId(expr_id),
                                                  callee_substs,
-                                                 Some(callee_origins));
+                                                 callee_origins);
 
             let callee_ty = node_id_type(bcx, expr_id);
             let llty = type_of_fn_from_ty(ccx, callee_ty).ptr_to();
@@ -264,7 +259,7 @@ fn trans_monomorphized_callee<'a>(bcx: &'a Block<'a>,
                                                mth_id,
                                                MethodCall(method_call),
                                                callee_substs,
-                                               Some(callee_origins));
+                                               callee_origins);
 
           Callee { bcx: bcx, data: Fn(llfn) }
       }
@@ -277,9 +272,9 @@ fn trans_monomorphized_callee<'a>(bcx: &'a Block<'a>,
 fn combine_impl_and_methods_tps(bcx: &Block,
                                 mth_did: ast::DefId,
                                 node: ExprOrMethodCall,
-                                rcvr_substs: ty::substs,
+                                rcvr_substs: subst::Substs,
                                 rcvr_origins: typeck::vtable_res)
-                                -> (ty::substs, typeck::vtable_res)
+                                -> (subst::Substs, typeck::vtable_res)
 {
     /*!
      * Creates a concatenated set of substitutions which includes
@@ -321,23 +316,13 @@ fn combine_impl_and_methods_tps(bcx: &Block,
         MethodCall(method_call) => method_call
     };
     let mut vtables = rcvr_origins;
-    match node_vtables(bcx, vtable_key) {
-        Some(vt) => {
-            let start = vt.len() - n_m_tps;
-            vtables.extend(vt.move_iter().skip(start));
-        }
-        None => {
-            vtables.extend(range(0, n_m_tps).map(
-                |_| -> typeck::vtable_param_res {
-                    Vec::new()
-                }
-            ));
-        }
-    }
+    let vt = node_vtables(bcx, vtable_key);
+    let start = vt.len() - n_m_tps;
+    vtables.extend(vt.move_iter().skip(start));
 
-    let ty_substs = ty::substs {
+    let ty_substs = subst::Substs {
         tps: tps,
-        regions: ty::ErasedRegions,
+        regions: subst::ErasedRegions,
         self_ty: rcvr_self_ty
     };
 
@@ -493,7 +478,7 @@ pub fn make_vtable<I: Iterator<ValueRef>>(ccx: &CrateContext,
 
 fn emit_vtable_methods(bcx: &Block,
                        impl_id: ast::DefId,
-                       substs: ty::substs,
+                       substs: subst::Substs,
                        vtables: typeck::vtable_res)
                        -> Vec<ValueRef> {
     let ccx = bcx.ccx();
@@ -524,7 +509,7 @@ fn emit_vtable_methods(bcx: &Block,
             C_null(Type::nil(ccx).ptr_to())
         } else {
             trans_fn_ref_with_vtables(bcx, m_id, ExprId(0),
-                                      substs.clone(), Some(vtables.clone()))
+                                      substs.clone(), vtables.clone())
         }
     }).collect()
 }
diff --git a/src/librustc/middle/trans/monomorphize.rs b/src/librustc/middle/trans/monomorphize.rs
index 913f333b0f3..9559c0909a6 100644
--- a/src/librustc/middle/trans/monomorphize.rs
+++ b/src/librustc/middle/trans/monomorphize.rs
@@ -11,6 +11,8 @@
 use back::link::exported_name;
 use driver::session;
 use lib::llvm::ValueRef;
+use middle::subst;
+use middle::subst::Subst;
 use middle::trans::base::{set_llvm_fn_attrs, set_inline_hint};
 use middle::trans::base::{trans_enum_variant, push_ctxt, get_item_val};
 use middle::trans::base::{trans_fn, decl_internal_rust_fn};
@@ -29,8 +31,8 @@ use std::hash::{sip, Hash};
 
 pub fn monomorphic_fn(ccx: &CrateContext,
                       fn_id: ast::DefId,
-                      real_substs: &ty::substs,
-                      vtables: Option<typeck::vtable_res>,
+                      real_substs: &subst::Substs,
+                      vtables: typeck::vtable_res,
                       self_vtables: Option<typeck::vtable_param_res>,
                       ref_id: Option<ast::NodeId>)
     -> (ValueRef, bool) {
@@ -53,23 +55,7 @@ pub fn monomorphic_fn(ccx: &CrateContext,
     let _icx = push_ctxt("monomorphic_fn");
 
     let substs_iter = real_substs.self_ty.iter().chain(real_substs.tps.iter());
-    let param_ids: Vec<MonoParamId> = match vtables {
-        Some(ref vts) => {
-            debug!("make_mono_id vtables={} psubsts={}",
-                   vts.repr(ccx.tcx()), real_substs.tps.repr(ccx.tcx()));
-            let vts_iter = self_vtables.iter().chain(vts.iter());
-            vts_iter.zip(substs_iter).map(|(vtable, subst)| MonoParamId {
-                subst: *subst,
-                // Do we really need the vtables to be hashed? Isn't the type enough?
-                vtables: vtable.iter().map(|vt| make_vtable_id(ccx, vt)).collect()
-            }).collect()
-        }
-        None => substs_iter.map(|subst| MonoParamId {
-            subst: *subst,
-            vtables: Vec::new()
-        }).collect()
-    };
-
+    let param_ids: Vec<ty::t> = substs_iter.map(|t| *t).collect();
     let hash_id = MonoId {
         def: fn_id,
         params: param_ids
@@ -139,7 +125,7 @@ pub fn monomorphic_fn(ccx: &CrateContext,
 
     debug!("monomorphic_fn about to subst into {}", llitem_ty.repr(ccx.tcx()));
     let mono_ty = match is_static_provided {
-        None => ty::subst(ccx.tcx(), real_substs, llitem_ty),
+        None => llitem_ty.subst(ccx.tcx(), real_substs),
         Some(num_method_ty_params) => {
             // Static default methods are a little unfortunate, in
             // that the "internal" and "external" type of them differ.
@@ -161,14 +147,14 @@ pub fn monomorphic_fn(ccx: &CrateContext,
             tps.push(real_substs.self_ty.unwrap());
             tps.push_all(real_substs.tps.tailn(idx));
 
-            let substs = ty::substs { regions: ty::ErasedRegions,
-                                      self_ty: None,
-                                      tps: tps };
+            let substs = subst::Substs { regions: subst::ErasedRegions,
+                                         self_ty: None,
+                                         tps: tps };
 
             debug!("static default: changed substitution to {}",
                    substs.repr(ccx.tcx()));
 
-            ty::subst(ccx.tcx(), &substs, llitem_ty)
+            llitem_ty.subst(ccx.tcx(), &substs)
         }
     };
 
@@ -220,7 +206,7 @@ pub fn monomorphic_fn(ccx: &CrateContext,
               } => {
                   let d = mk_lldecl();
                   set_llvm_fn_attrs(i.attrs.as_slice(), d);
-                  trans_fn(ccx, decl, body, d, Some(&psubsts), fn_id.node, []);
+                  trans_fn(ccx, decl, body, d, &psubsts, fn_id.node, []);
                   d
               }
               _ => {
@@ -252,7 +238,7 @@ pub fn monomorphic_fn(ccx: &CrateContext,
                                        v,
                                        args.as_slice(),
                                        this_tv.disr_val,
-                                       Some(&psubsts),
+                                       &psubsts,
                                        d);
                 }
                 ast::StructVariantKind(_) =>
@@ -263,7 +249,7 @@ pub fn monomorphic_fn(ccx: &CrateContext,
         ast_map::NodeMethod(mth) => {
             let d = mk_lldecl();
             set_llvm_fn_attrs(mth.attrs.as_slice(), d);
-            trans_fn(ccx, mth.decl, mth.body, d, Some(&psubsts), mth.id, []);
+            trans_fn(ccx, mth.decl, mth.body, d, &psubsts, mth.id, []);
             d
         }
         ast_map::NodeTraitMethod(method) => {
@@ -271,7 +257,7 @@ pub fn monomorphic_fn(ccx: &CrateContext,
                 ast::Provided(mth) => {
                     let d = mk_lldecl();
                     set_llvm_fn_attrs(mth.attrs.as_slice(), d);
-                    trans_fn(ccx, mth.decl, mth.body, d, Some(&psubsts), mth.id, []);
+                    trans_fn(ccx, mth.decl, mth.body, d, &psubsts, mth.id, []);
                     d
                 }
                 _ => {
@@ -287,7 +273,7 @@ pub fn monomorphic_fn(ccx: &CrateContext,
                                      struct_def.fields.as_slice(),
                                      struct_def.ctor_id.expect("ast-mapped tuple struct \
                                                                 didn't have a ctor id"),
-                                     Some(&psubsts),
+                                     &psubsts,
                                      d);
             d
         }
@@ -315,33 +301,22 @@ pub fn monomorphic_fn(ccx: &CrateContext,
 #[deriving(PartialEq, Eq, Hash)]
 pub struct MonoParamId {
     pub subst: ty::t,
-    // Do we really need the vtables to be hashed? Isn't the type enough?
-    pub vtables: Vec<MonoId>
 }
 
 #[deriving(PartialEq, Eq, Hash)]
 pub struct MonoId {
     pub def: ast::DefId,
-    pub params: Vec<MonoParamId>
+    pub params: Vec<ty::t>
 }
 
-pub fn make_vtable_id(ccx: &CrateContext,
+pub fn make_vtable_id(_ccx: &CrateContext,
                       origin: &typeck::vtable_origin)
                       -> MonoId {
     match origin {
-        &typeck::vtable_static(impl_id, ref substs, ref sub_vtables) => {
+        &typeck::vtable_static(impl_id, ref substs, _) => {
             MonoId {
                 def: impl_id,
-                // FIXME(NDM) -- this is pretty bogus. It ignores self-type,
-                // and vtables are not necessary, AND they are not guaranteed
-                // to be same length as the number of TPS ANYHOW!
-                params: sub_vtables.iter().zip(substs.tps.iter()).map(|(vtable, subst)| {
-                    MonoParamId {
-                        subst: *subst,
-                        // Do we really need the vtables to be hashed? Isn't the type enough?
-                        vtables: vtable.iter().map(|vt| make_vtable_id(ccx, vt)).collect()
-                    }
-                }).collect()
+                params: substs.tps.iter().map(|subst| *subst).collect()
             }
         }
 
diff --git a/src/librustc/middle/trans/reflect.rs b/src/librustc/middle/trans/reflect.rs
index a4f583cdb82..3b469a1d110 100644
--- a/src/librustc/middle/trans/reflect.rs
+++ b/src/librustc/middle/trans/reflect.rs
@@ -297,8 +297,10 @@ impl<'a, 'b> Reflector<'a, 'b> {
                                                     fn_ty,
                                                     sym.as_slice());
                 let arena = TypedArena::new();
+                let empty_param_substs = param_substs::empty();
                 let fcx = new_fn_ctxt(ccx, llfdecl, -1, false,
-                                      ty::mk_u64(), None, None, &arena);
+                                      ty::mk_u64(), &empty_param_substs,
+                                      None, &arena);
                 init_function(&fcx, false, ty::mk_u64());
 
                 let arg = unsafe {
diff --git a/src/librustc/middle/trans/type_of.rs b/src/librustc/middle/trans/type_of.rs
index 0f28ce4d972..bf5bedd98e8 100644
--- a/src/librustc/middle/trans/type_of.rs
+++ b/src/librustc/middle/trans/type_of.rs
@@ -10,6 +10,7 @@
 
 #![allow(non_camel_case_types)]
 
+use middle::subst;
 use middle::trans::adt;
 use middle::trans::common::*;
 use middle::trans::foreign;
@@ -21,7 +22,6 @@ use middle::trans::type_::Type;
 
 use syntax::abi;
 use syntax::ast;
-use syntax::owned_slice::OwnedSlice;
 
 pub fn arg_is_indirect(ccx: &CrateContext, arg_ty: ty::t) -> bool {
     !type_is_immediate(ccx, arg_ty)
@@ -310,8 +310,7 @@ pub fn llvm_type_name(cx: &CrateContext,
     let tstr = ppaux::parameterized(cx.tcx(),
                                     ty::item_path_str(cx.tcx(),
                                                       did).as_slice(),
-                                    &ty::NonerasedRegions(
-                                        OwnedSlice::empty()),
+                                    &subst::ErasedRegions,
                                     tps,
                                     did,
                                     false);
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 9ecd6d48e12..6275abdc8ab 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -16,14 +16,16 @@ use metadata::csearch;
 use mc = middle::mem_categorization;
 use middle::lint;
 use middle::const_eval;
+use middle::def;
 use middle::dependency_format;
 use middle::lang_items::{ExchangeHeapLangItem, OpaqueStructLangItem};
 use middle::lang_items::{TyDescStructLangItem, TyVisitorTraitLangItem};
 use middle::freevars;
 use middle::resolve;
 use middle::resolve_lifetime;
+use middle::subst;
+use middle::subst::{Subst, Substs};
 use middle::ty;
-use middle::subst::Subst;
 use middle::typeck;
 use middle::typeck::MethodCall;
 use middle::ty_fold;
@@ -207,7 +209,7 @@ pub enum AutoAdjustment {
     AutoObject(ty::TraitStore,
                ty::BuiltinBounds,
                ast::DefId, /* Trait ID */
-               ty::substs /* Trait substitutions */)
+               subst::Substs /* Trait substitutions */)
 }
 
 #[deriving(Clone, Decodable, Encodable)]
@@ -639,40 +641,6 @@ pub enum BoundRegion {
     BrFresh(uint),
 }
 
-/**
- * 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`. */
-#[deriving(Clone, PartialEq, Eq, Hash)]
-pub enum RegionSubsts {
-    ErasedRegions,
-    NonerasedRegions(OwnedSlice<ty::Region>)
-}
-
-/**
- * The type substs represents the kinds of things that can be substituted to
- * convert a polytype into a monotype.  Note however that substituting bound
- * regions other than `self` is done through a different mechanism:
- *
- * - `tps` represents the type parameters in scope.  They are indexed
- *   according to the order in which they were declared.
- *
- * - `self_r` indicates the region parameter `self` that is present on nominal
- *   types (enums, structs) declared as having a region parameter.  `self_r`
- *   should always be none for types that are not region-parameterized and
- *   Some(_) for types that are.  The only bound region parameter that should
- *   appear within a region-parameterized type is `self`.
- *
- * - `self_ty` is the type to which `self` should be remapped, if any.  The
- *   `self` type is rather funny in that it can only appear on traits and is
- *   always substituted away to the implementing type for a trait. */
-#[deriving(Clone, PartialEq, Eq, Hash)]
-pub struct substs {
-    pub self_ty: Option<ty::t>,
-    pub tps: Vec<t>,
-    pub regions: RegionSubsts,
-}
-
 mod primitives {
     use super::t_box_;
 
@@ -731,7 +699,7 @@ pub enum sty {
     ty_int(ast::IntTy),
     ty_uint(ast::UintTy),
     ty_float(ast::FloatTy),
-    ty_enum(DefId, substs),
+    ty_enum(DefId, Substs),
     ty_box(t),
     ty_uniq(t),
     ty_str,
@@ -741,7 +709,7 @@ pub enum sty {
     ty_bare_fn(BareFnTy),
     ty_closure(Box<ClosureTy>),
     ty_trait(Box<TyTrait>),
-    ty_struct(DefId, substs),
+    ty_struct(DefId, Substs),
     ty_tup(Vec<t>),
 
     ty_param(param_ty), // type parameter
@@ -757,7 +725,7 @@ pub enum sty {
 #[deriving(Clone, PartialEq, Eq, Hash)]
 pub struct TyTrait {
     pub def_id: DefId,
-    pub substs: substs,
+    pub substs: Substs,
     pub store: TraitStore,
     pub bounds: BuiltinBounds
 }
@@ -765,7 +733,7 @@ pub struct TyTrait {
 #[deriving(PartialEq, Eq, Hash)]
 pub struct TraitRef {
     pub def_id: DefId,
-    pub substs: substs
+    pub substs: Substs
 }
 
 #[deriving(Clone, PartialEq)]
@@ -1032,7 +1000,7 @@ pub struct ParameterEnvironment {
     /// In general, this means converting from bound parameters to
     /// free parameters. Since we currently represent bound/free type
     /// parameters in the same way, this only has an affect on regions.
-    pub free_substs: ty::substs,
+    pub free_substs: Substs,
 
     /// Bound on the Self parameter
     pub self_param_bound: Option<Rc<TraitRef>>,
@@ -1068,11 +1036,11 @@ pub struct TraitDef {
 /// item into the monotype of an item reference.
 #[deriving(Clone)]
 pub struct ItemSubsts {
-    pub substs: ty::substs,
+    pub substs: Substs,
 }
 
 pub struct ty_param_substs_and_ty {
-    pub substs: ty::substs,
+    pub substs: Substs,
     pub ty: ty::t
 }
 
@@ -1176,12 +1144,12 @@ pub fn mk_t(cx: &ctxt, st: sty) -> t {
             }
         }
     }
-    fn sflags(substs: &substs) -> uint {
+    fn sflags(substs: &Substs) -> uint {
         let mut f = 0u;
         for tt in substs.tps.iter() { f |= get(*tt).flags; }
         match substs.regions {
-            ErasedRegions => {}
-            NonerasedRegions(ref regions) => {
+            subst::ErasedRegions => {}
+            subst::NonerasedRegions(ref regions) => {
                 for r in regions.iter() {
                     f |= rflags(*r)
                 }
@@ -1369,7 +1337,7 @@ pub fn mk_str_slice(cx: &ctxt, r: Region, m: ast::Mutability) -> t {
             })
 }
 
-pub fn mk_enum(cx: &ctxt, did: ast::DefId, substs: substs) -> t {
+pub fn mk_enum(cx: &ctxt, did: ast::DefId, substs: Substs) -> t {
     // take a copy of substs so that we own the vectors inside
     mk_t(cx, ty_enum(did, substs))
 }
@@ -1444,7 +1412,7 @@ pub fn mk_ctor_fn(cx: &ctxt,
 
 pub fn mk_trait(cx: &ctxt,
                 did: ast::DefId,
-                substs: substs,
+                substs: Substs,
                 store: TraitStore,
                 bounds: BuiltinBounds)
              -> t {
@@ -1458,7 +1426,7 @@ pub fn mk_trait(cx: &ctxt,
     mk_t(cx, ty_trait(inner))
 }
 
-pub fn mk_struct(cx: &ctxt, struct_id: ast::DefId, substs: substs) -> t {
+pub fn mk_struct(cx: &ctxt, struct_id: ast::DefId, substs: Substs) -> t {
     // take a copy of substs so that we own the vectors inside
     mk_t(cx, ty_struct(struct_id, substs))
 }
@@ -1524,38 +1492,14 @@ pub fn walk_regions_and_ty(cx: &ctxt, ty: t, fldr: |r: Region|, fldt: |t: t|)
 
 impl ItemSubsts {
     pub fn empty() -> ItemSubsts {
-        ItemSubsts {
-            substs: substs::empty(),
-        }
+        ItemSubsts { substs: Substs::empty() }
     }
 
     pub fn is_noop(&self) -> bool {
-        ty::substs_is_noop(&self.substs)
+        self.substs.is_noop()
     }
 }
 
-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 &&
-        regions_is_noop &&
-        substs.self_ty.is_none()
-}
-
-pub fn substs_to_str(cx: &ctxt, substs: &substs) -> String {
-    substs.repr(cx)
-}
-
-pub fn subst(cx: &ctxt,
-             substs: &substs,
-             typ: t)
-          -> t {
-    typ.subst(cx, substs)
-}
-
 // Type utilities
 
 pub fn type_is_nil(ty: t) -> bool { get(ty).sty == ty_nil }
@@ -1744,7 +1688,7 @@ fn type_needs_unwind_cleanup_(cx: &ctxt, ty: t,
           ty_enum(did, ref substs) => {
             for v in (*enum_variants(cx, did)).iter() {
                 for aty in v.args.iter() {
-                    let t = subst(cx, substs, *aty);
+                    let t = aty.subst(cx, substs);
                     needs_unwind_cleanup |=
                         type_needs_unwind_cleanup_(cx, t, tycache,
                                                    encountered_box);
@@ -2376,7 +2320,7 @@ pub fn is_instantiable(cx: &ctxt, r_ty: t) -> bool {
                 let vs = enum_variants(cx, did);
                 let r = !vs.is_empty() && vs.iter().all(|variant| {
                     variant.args.iter().any(|aty| {
-                        let sty = subst(cx, substs, *aty);
+                        let sty = aty.subst(cx, substs);
                         type_requires(cx, seen, r_ty, sty)
                     })
                 });
@@ -3002,7 +2946,7 @@ pub fn method_call_type_param_defs(tcx: &ctxt, origin: typeck::MethodOrigin)
     }
 }
 
-pub fn resolve_expr(tcx: &ctxt, expr: &ast::Expr) -> ast::Def {
+pub fn resolve_expr(tcx: &ctxt, expr: &ast::Expr) -> def::Def {
     match tcx.def_map.borrow().find(&expr.id) {
         Some(&def) => def,
         None => {
@@ -3050,7 +2994,7 @@ pub fn expr_kind(tcx: &ctxt, expr: &ast::Expr) -> ExprKind {
     match expr.node {
         ast::ExprPath(..) => {
             match resolve_expr(tcx, expr) {
-                ast::DefVariant(tid, vid, _) => {
+                def::DefVariant(tid, vid, _) => {
                     let variant_info = enum_variant_with_id(tcx, tid, vid);
                     if variant_info.args.len() > 0u {
                         // N-ary variant.
@@ -3061,7 +3005,7 @@ pub fn expr_kind(tcx: &ctxt, expr: &ast::Expr) -> ExprKind {
                     }
                 }
 
-                ast::DefStruct(_) => {
+                def::DefStruct(_) => {
                     match get(expr_ty(tcx, expr)).sty {
                         ty_bare_fn(..) => RvalueDatumExpr,
                         _ => RvalueDpsExpr
@@ -3069,16 +3013,16 @@ pub fn expr_kind(tcx: &ctxt, expr: &ast::Expr) -> ExprKind {
                 }
 
                 // Fn pointers are just scalar values.
-                ast::DefFn(..) | ast::DefStaticMethod(..) => RvalueDatumExpr,
+                def::DefFn(..) | def::DefStaticMethod(..) => RvalueDatumExpr,
 
                 // Note: there is actually a good case to be made that
                 // DefArg's, particularly those of immediate type, ought to
                 // considered rvalues.
-                ast::DefStatic(..) |
-                ast::DefBinding(..) |
-                ast::DefUpvar(..) |
-                ast::DefArg(..) |
-                ast::DefLocal(..) => LvalueExpr,
+                def::DefStatic(..) |
+                def::DefBinding(..) |
+                def::DefUpvar(..) |
+                def::DefArg(..) |
+                def::DefLocal(..) => LvalueExpr,
 
                 def => {
                     tcx.sess.span_bug(
@@ -3169,7 +3113,7 @@ pub fn expr_kind(tcx: &ctxt, expr: &ast::Expr) -> ExprKind {
                 Some(&def) => def,
                 None => fail!("no def for place"),
             };
-            let def_id = ast_util::def_id_of_def(definition);
+            let def_id = definition.def_id();
             match tcx.lang_items.items.get(ExchangeHeapLangItem as uint) {
                 &Some(item_def_id) if def_id == item_def_id => {
                     RvalueDatumExpr
@@ -3591,7 +3535,7 @@ pub fn trait_ref_to_def_id(tcx: &ctxt, tr: &ast::TraitRef) -> ast::DefId {
     let def = *tcx.def_map.borrow()
                      .find(&tr.ref_id)
                      .expect("no def-map entry for trait");
-    ast_util::def_id_of_def(def)
+    def.def_id()
 }
 
 pub fn try_add_builtin_trait(tcx: &ctxt,
@@ -3688,13 +3632,13 @@ impl VariantInfo {
 
 pub fn substd_enum_variants(cx: &ctxt,
                             id: ast::DefId,
-                            substs: &substs)
+                            substs: &Substs)
                          -> Vec<Rc<VariantInfo>> {
     enum_variants(cx, id).iter().map(|variant_info| {
         let substd_args = variant_info.args.iter()
-            .map(|aty| subst(cx, substs, *aty)).collect();
+            .map(|aty| aty.subst(cx, substs)).collect();
 
-        let substd_ctor_ty = subst(cx, substs, variant_info.ctor_ty);
+        let substd_ctor_ty = variant_info.ctor_ty.subst(cx, substs);
 
         Rc::new(VariantInfo {
             args: substd_args,
@@ -3944,7 +3888,7 @@ pub fn lookup_repr_hint(tcx: &ctxt, did: DefId) -> attr::ReprAttr {
 pub fn lookup_field_type(tcx: &ctxt,
                          struct_id: DefId,
                          id: DefId,
-                         substs: &substs)
+                         substs: &Substs)
                       -> ty::t {
     let t = if id.krate == ast::LOCAL_CRATE {
         node_id_to_type(tcx, id.node)
@@ -3959,7 +3903,7 @@ pub fn lookup_field_type(tcx: &ctxt,
            }
         }
     };
-    subst(tcx, substs, t)
+    t.subst(tcx, substs)
 }
 
 // Lookup all ancestor structs of a struct indicated by did. That is the reflexive,
@@ -4027,7 +3971,7 @@ pub fn lookup_struct_field(cx: &ctxt,
 
 // Returns a list of fields corresponding to the struct's items. trans uses
 // this. Takes a list of substs with which to instantiate field types.
-pub fn struct_fields(cx: &ctxt, did: ast::DefId, substs: &substs)
+pub fn struct_fields(cx: &ctxt, did: ast::DefId, substs: &Substs)
                      -> Vec<field> {
     lookup_struct_fields(cx, did).iter().map(|f| {
        field {
@@ -4140,11 +4084,11 @@ pub fn normalize_ty(cx: &ctxt, t: t) -> t {
         }
 
         fn fold_substs(&mut self,
-                       substs: &substs)
-                       -> substs {
-            substs { regions: ErasedRegions,
-                     self_ty: substs.self_ty.fold_with(self),
-                     tps: substs.tps.fold_with(self) }
+                       substs: &subst::Substs)
+                       -> subst::Substs {
+            subst::Substs { regions: subst::ErasedRegions,
+                            self_ty: substs.self_ty.fold_with(self),
+                            tps: substs.tps.fold_with(self) }
         }
 
         fn fold_sig(&mut self,
@@ -4292,8 +4236,8 @@ pub fn visitor_object_ty(tcx: &ctxt,
         Ok(id) => id,
         Err(s) => { return Err(s); }
     };
-    let substs = substs {
-        regions: ty::NonerasedRegions(OwnedSlice::empty()),
+    let substs = Substs {
+        regions: subst::NonerasedRegions(Vec::new()),
         self_ty: None,
         tps: Vec::new()
     };
@@ -4676,10 +4620,10 @@ pub fn construct_parameter_environment(
         push_region_params(t, free_id, method_region_params)
     };
 
-    let free_substs = substs {
+    let free_substs = Substs {
         self_ty: self_ty,
         tps: type_params,
-        regions: ty::NonerasedRegions(OwnedSlice::from_vec(region_params))
+        regions: subst::NonerasedRegions(region_params)
     };
 
     //
@@ -4712,16 +4656,6 @@ pub fn construct_parameter_environment(
     }
 }
 
-impl substs {
-    pub fn empty() -> substs {
-        substs {
-            self_ty: None,
-            tps: Vec::new(),
-            regions: NonerasedRegions(OwnedSlice::empty())
-        }
-    }
-}
-
 impl BorrowKind {
     pub fn from_mutbl(m: ast::Mutability) -> BorrowKind {
         match m {
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 27a02ea47cb..e8f043b5f86 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -10,6 +10,7 @@
 
 // Generalized type folding mechanism.
 
+use middle::subst;
 use middle::ty;
 use middle::typeck;
 use std::rc::Rc;
@@ -50,8 +51,8 @@ pub trait TypeFolder {
     }
 
     fn fold_substs(&mut self,
-                   substs: &ty::substs)
-                   -> ty::substs {
+                   substs: &subst::Substs)
+                   -> subst::Substs {
         super_fold_substs(self, substs)
     }
 
@@ -180,8 +181,8 @@ impl TypeFoldable for ty::Region {
     }
 }
 
-impl TypeFoldable for ty::substs {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::substs {
+impl TypeFoldable for subst::Substs {
+    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> subst::Substs {
         folder.fold_substs(self)
     }
 }
@@ -278,20 +279,20 @@ pub fn super_fold_ty<T:TypeFolder>(this: &mut T,
 }
 
 pub fn super_fold_substs<T:TypeFolder>(this: &mut T,
-                                       substs: &ty::substs)
-                                       -> ty::substs {
+                                       substs: &subst::Substs)
+                                       -> subst::Substs {
     let regions = match substs.regions {
-        ty::ErasedRegions => {
-            ty::ErasedRegions
+        subst::ErasedRegions => {
+            subst::ErasedRegions
         }
-        ty::NonerasedRegions(ref regions) => {
-            ty::NonerasedRegions(regions.fold_with(this))
+        subst::NonerasedRegions(ref regions) => {
+            subst::NonerasedRegions(regions.fold_with(this))
         }
     };
 
-    ty::substs { regions: regions,
-                 self_ty: substs.self_ty.fold_with(this),
-                 tps: substs.tps.fold_with(this) }
+    subst::Substs { regions: regions,
+                    self_ty: substs.self_ty.fold_with(this),
+                    tps: substs.tps.fold_with(this) }
 }
 
 pub fn super_fold_sig<T:TypeFolder>(this: &mut T,
diff --git a/src/librustc/middle/typeck/astconv.rs b/src/librustc/middle/typeck/astconv.rs
index 5323d4468c9..f8821a86e71 100644
--- a/src/librustc/middle/typeck/astconv.rs
+++ b/src/librustc/middle/typeck/astconv.rs
@@ -49,10 +49,10 @@
  * an rptr (`&r.T`) use the region `r` that appears in the rptr.
  */
 
-
 use middle::const_eval;
-use middle::subst::Subst;
-use middle::ty::{substs};
+use middle::def;
+use middle::subst;
+use middle::subst::{Subst, Substs};
 use middle::ty::{ty_param_substs_and_ty};
 use middle::ty;
 use middle::typeck::rscope;
@@ -152,7 +152,7 @@ fn ast_path_substs<AC:AstConv,RS:RegionScope>(
     rscope: &RS,
     decl_generics: &ty::Generics,
     self_ty: Option<ty::t>,
-    path: &ast::Path) -> ty::substs
+    path: &ast::Path) -> subst::Substs
 {
     /*!
      * Given a path `path` that refers to an item `I` with the
@@ -232,8 +232,8 @@ fn ast_path_substs<AC:AstConv,RS:RegionScope>(
                             .map(|&a_t| ast_ty_to_ty(this, rscope, a_t))
                             .collect();
 
-    let mut substs = substs {
-        regions: ty::NonerasedRegions(OwnedSlice::from_vec(regions)),
+    let mut substs = subst::Substs {
+        regions: subst::NonerasedRegions(regions),
         self_ty: self_ty,
         tps: tps
     };
@@ -261,7 +261,7 @@ pub fn ast_path_to_substs_and_ty<AC:AstConv,
     } = this.get_item_ty(did);
 
     let substs = ast_path_substs(this, rscope, &generics, None, path);
-    let ty = ty::subst(tcx, &substs, decl_ty);
+    let ty = decl_ty.subst(tcx, &substs);
     ty_param_substs_and_ty { substs: substs, ty: ty }
 }
 
@@ -329,7 +329,7 @@ pub fn ast_ty_to_prim_ty(tcx: &ty::ctxt, ast_ty: &ast::Ty) -> Option<ty::t> {
                 Some(&d) => d
             };
             match a_def {
-                ast::DefPrimTy(nty) => {
+                def::DefPrimTy(nty) => {
                     match nty {
                         ast::TyBool => {
                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
@@ -402,7 +402,7 @@ pub fn ast_ty_to_builtin_ty<AC:AstConv,
             // FIXME(#12938): This is a hack until we have full support for
             // DST.
             match a_def {
-                ast::DefTy(did) | ast::DefStruct(did)
+                def::DefTy(did) | def::DefStruct(did)
                         if Some(did) == this.tcx().lang_items.owned_box() => {
                     if path.segments
                            .iter()
@@ -496,7 +496,7 @@ fn mk_pointer<AC:AstConv,
             // restriction is enforced in the below case for ty_path, which
             // will run after this as long as the path isn't a trait.
             match tcx.def_map.borrow().find(&id) {
-                Some(&ast::DefPrimTy(ast::TyStr)) => {
+                Some(&def::DefPrimTy(ast::TyStr)) => {
                     check_path_args(tcx, path, NO_TPS | NO_REGIONS);
                     match ptr_ty {
                         Uniq => {
@@ -512,7 +512,7 @@ fn mk_pointer<AC:AstConv,
                         }
                     }
                 }
-                Some(&ast::DefTrait(trait_def_id)) => {
+                Some(&def::DefTrait(trait_def_id)) => {
                     let result = ast_path_to_trait_ref(
                         this, rscope, trait_def_id, None, path);
                     let trait_store = match ptr_ty {
@@ -661,14 +661,14 @@ pub fn ast_ty_to_ty<AC:AstConv, RS:RegionScope>(
                 // Kind bounds on path types are only supported for traits.
                 match a_def {
                     // But don't emit the error if the user meant to do a trait anyway.
-                    ast::DefTrait(..) => { },
+                    def::DefTrait(..) => { },
                     _ if bounds.is_some() =>
                         tcx.sess.span_err(ast_ty.span,
                                           "kind bounds can only be used on trait types"),
                     _ => { },
                 }
                 match a_def {
-                    ast::DefTrait(_) => {
+                    def::DefTrait(_) => {
                         let path_str = path_to_str(path);
                         tcx.sess.span_err(
                             ast_ty.span,
@@ -678,14 +678,14 @@ pub fn ast_ty_to_ty<AC:AstConv, RS:RegionScope>(
                                     name=path_str).as_slice());
                         ty::mk_err()
                     }
-                    ast::DefTy(did) | ast::DefStruct(did) => {
+                    def::DefTy(did) | def::DefStruct(did) => {
                         ast_path_to_ty(this, rscope, did, path).ty
                     }
-                    ast::DefTyParam(id, n) => {
+                    def::DefTyParam(id, n) => {
                         check_path_args(tcx, path, NO_TPS | NO_REGIONS);
                         ty::mk_param(tcx, n, id)
                     }
-                    ast::DefSelfTy(id) => {
+                    def::DefSelfTy(id) => {
                         // n.b.: resolve guarantees that the this type only appears in a
                         // trait, which we rely upon in various places when creating
                         // substs
@@ -693,12 +693,12 @@ pub fn ast_ty_to_ty<AC:AstConv, RS:RegionScope>(
                         let did = ast_util::local_def(id);
                         ty::mk_self(tcx, did)
                     }
-                    ast::DefMod(id) => {
+                    def::DefMod(id) => {
                         tcx.sess.span_fatal(ast_ty.span,
                             format!("found module name used as a type: {}",
                                     tcx.map.node_to_str(id.node)).as_slice());
                     }
-                    ast::DefPrimTy(_) => {
+                    def::DefPrimTy(_) => {
                         fail!("DefPrimTy arm missed in previous ast_ty_to_prim_ty call");
                     }
                     _ => {
@@ -912,7 +912,7 @@ fn conv_builtin_bounds(tcx: &ty::ctxt, ast_bounds: &Option<OwnedSlice<ast::TyPar
                 match *ast_bound {
                     ast::TraitTyParamBound(ref b) => {
                         match lookup_def_tcx(tcx, b.path.span, b.ref_id) {
-                            ast::DefTrait(trait_did) => {
+                            def::DefTrait(trait_did) => {
                                 if ty::try_add_builtin_trait(tcx, trait_did,
                                                              &mut builtin_bounds) {
                                     continue; // success
diff --git a/src/librustc/middle/typeck/check/_match.rs b/src/librustc/middle/typeck/check/_match.rs
index 62c4e92997c..df774b21504 100644
--- a/src/librustc/middle/typeck/check/_match.rs
+++ b/src/librustc/middle/typeck/check/_match.rs
@@ -10,7 +10,10 @@
 
 #![allow(non_camel_case_types)]
 
+use middle::def;
 use middle::pat_util::{PatIdMap, pat_id_map, pat_is_binding, pat_is_const};
+use middle::subst;
+use middle::subst::Subst;
 use middle::ty;
 use middle::typeck::check::demand;
 use middle::typeck::check::{check_expr, check_expr_has_type, FnCtxt};
@@ -126,7 +129,7 @@ pub fn check_pat_variant(pcx: &pat_ctxt, pat: &ast::Pat, path: &ast::Path,
         ty::ty_enum(_, ref expected_substs) => {
             // Lookup the enum and variant def ids:
             let v_def = lookup_def(pcx.fcx, pat.span, pat.id);
-            match ast_util::variant_def_ids(v_def) {
+            match v_def.variant_def_ids() {
                 Some((enm, var)) => {
                     // Assign the pattern the type of the *enum*, not the variant.
                     let enum_tpt = ty::lookup_item_type(tcx, enm);
@@ -151,7 +154,7 @@ pub fn check_pat_variant(pcx: &pat_ctxt, pat: &ast::Pat, path: &ast::Path,
                             if var_tpt.generics.type_param_defs().len() ==
                                 expected_substs.tps.len()
                             {
-                                ty::subst(tcx, expected_substs, *t)
+                                t.subst(tcx, expected_substs)
                             }
                             else {
                                 *t // In this case, an error was already signaled
@@ -186,7 +189,7 @@ pub fn check_pat_variant(pcx: &pat_ctxt, pat: &ast::Pat, path: &ast::Path,
         ty::ty_struct(struct_def_id, ref expected_substs) => {
             // Lookup the struct ctor def id
             let s_def = lookup_def(pcx.fcx, pat.span, pat.id);
-            let s_def_id = ast_util::def_id_of_def(s_def);
+            let s_def_id = s_def.def_id();
 
             // Assign the pattern the type of the struct.
             let ctor_tpt = ty::lookup_item_type(tcx, s_def_id);
@@ -301,7 +304,7 @@ pub fn check_struct_pat_fields(pcx: &pat_ctxt,
                                fields: &[ast::FieldPat],
                                class_fields: Vec<ty::field_ty>,
                                class_id: ast::DefId,
-                               substitutions: &ty::substs,
+                               substitutions: &subst::Substs,
                                etc: bool) {
     let tcx = pcx.fcx.ccx.tcx;
 
@@ -362,7 +365,7 @@ pub fn check_struct_pat(pcx: &pat_ctxt, pat_id: ast::NodeId, span: Span,
                         expected: ty::t, path: &ast::Path,
                         fields: &[ast::FieldPat], etc: bool,
                         struct_id: ast::DefId,
-                        substitutions: &ty::substs) {
+                        substitutions: &subst::Substs) {
     let fcx = pcx.fcx;
     let tcx = pcx.fcx.ccx.tcx;
 
@@ -370,11 +373,11 @@ pub fn check_struct_pat(pcx: &pat_ctxt, pat_id: ast::NodeId, span: Span,
 
     // Check to ensure that the struct is the one specified.
     match tcx.def_map.borrow().find(&pat_id) {
-        Some(&ast::DefStruct(supplied_def_id))
+        Some(&def::DefStruct(supplied_def_id))
                 if supplied_def_id == struct_id => {
             // OK.
         }
-        Some(&ast::DefStruct(..)) | Some(&ast::DefVariant(..)) => {
+        Some(&def::DefStruct(..)) | Some(&def::DefVariant(..)) => {
             let name = pprust::path_to_str(path);
             tcx.sess
                .span_err(span,
@@ -400,13 +403,13 @@ pub fn check_struct_like_enum_variant_pat(pcx: &pat_ctxt,
                                           fields: &[ast::FieldPat],
                                           etc: bool,
                                           enum_id: ast::DefId,
-                                          substitutions: &ty::substs) {
+                                          substitutions: &subst::Substs) {
     let fcx = pcx.fcx;
     let tcx = pcx.fcx.ccx.tcx;
 
     // Find the variant that was specified.
     match tcx.def_map.borrow().find(&pat_id) {
-        Some(&ast::DefVariant(found_enum_id, variant_id, _))
+        Some(&def::DefVariant(found_enum_id, variant_id, _))
                 if found_enum_id == enum_id => {
             // Get the struct fields from this struct-like enum variant.
             let class_fields = ty::lookup_struct_fields(tcx, variant_id);
@@ -414,7 +417,7 @@ pub fn check_struct_like_enum_variant_pat(pcx: &pat_ctxt,
             check_struct_pat_fields(pcx, span, fields, class_fields,
                                     variant_id, substitutions, etc);
         }
-        Some(&ast::DefStruct(..)) | Some(&ast::DefVariant(..)) => {
+        Some(&def::DefStruct(..)) | Some(&def::DefVariant(..)) => {
             let name = pprust::path_to_str(path);
             tcx.sess.span_err(span,
                               format!("mismatched types: expected `{}` but \
@@ -475,8 +478,7 @@ pub fn check_pat(pcx: &pat_ctxt, pat: &ast::Pat, expected: ty::t) {
       }
       ast::PatEnum(..) |
       ast::PatIdent(..) if pat_is_const(&tcx.def_map, pat) => {
-        let const_did = ast_util::def_id_of_def(tcx.def_map.borrow()
-                                                   .get_copy(&pat.id));
+        let const_did = tcx.def_map.borrow().get_copy(&pat.id).def_id();
         let const_tpt = ty::lookup_item_type(tcx, const_did);
         demand::suptype(fcx, pat.span, expected, const_tpt.ty);
         fcx.write_ty(pat.id, const_tpt.ty);
@@ -556,7 +558,7 @@ pub fn check_pat(pcx: &pat_ctxt, pat: &ast::Pat, expected: ty::t) {
                             "a structure pattern".to_string(),
                             None);
                 match tcx.def_map.borrow().find(&pat.id) {
-                    Some(&ast::DefStruct(supplied_def_id)) => {
+                    Some(&def::DefStruct(supplied_def_id)) => {
                          check_struct_pat(pcx,
                                           pat.id,
                                           pat.span,
@@ -565,10 +567,10 @@ pub fn check_pat(pcx: &pat_ctxt, pat: &ast::Pat, expected: ty::t) {
                                           fields.as_slice(),
                                           etc,
                                           supplied_def_id,
-                                          &ty::substs {
+                                          &subst::Substs {
                                               self_ty: None,
                                               tps: Vec::new(),
-                                              regions: ty::ErasedRegions,
+                                              regions: subst::ErasedRegions,
                                           });
                     }
                     _ => () // Error, but we're already in an error case
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index b32875b06ee..0d4fea56e77 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -80,6 +80,7 @@ obtained the type `Foo`, we would never match this method.
 */
 
 
+use middle::subst;
 use middle::subst::Subst;
 use middle::ty::*;
 use middle::ty;
@@ -104,7 +105,6 @@ use syntax::ast::{MutMutable, MutImmutable};
 use syntax::ast;
 use syntax::codemap::Span;
 use syntax::parse::token;
-use syntax::owned_slice::OwnedSlice;
 
 #[deriving(PartialEq)]
 pub enum CheckTraitsFlag {
@@ -233,7 +233,7 @@ fn construct_transformed_self_ty_for_object(
     tcx: &ty::ctxt,
     span: Span,
     trait_def_id: ast::DefId,
-    rcvr_substs: &ty::substs,
+    rcvr_substs: &subst::Substs,
     method_ty: &ty::Method)
     -> ty::t {
     /*!
@@ -257,7 +257,7 @@ fn construct_transformed_self_ty_for_object(
         * match below.
         */
 
-    let substs = ty::substs {regions: rcvr_substs.regions.clone(),
+    let substs = subst::Substs {regions: rcvr_substs.regions.clone(),
                                 self_ty: None,
                                 tps: rcvr_substs.tps.clone()};
     match method_ty.explicit_self {
@@ -319,7 +319,7 @@ struct LookupContext<'a> {
 #[deriving(Clone)]
 struct Candidate {
     rcvr_match_condition: RcvrMatchCondition,
-    rcvr_substs: ty::substs,
+    rcvr_substs: subst::Substs,
     method_ty: Rc<ty::Method>,
     origin: MethodOrigin,
 }
@@ -500,7 +500,7 @@ impl<'a> LookupContext<'a> {
 
     fn push_inherent_candidates_from_object(&mut self,
                                             did: DefId,
-                                            substs: &ty::substs) {
+                                            substs: &subst::Substs) {
         debug!("push_inherent_candidates_from_object(did={}, substs={})",
                self.did_to_str(did),
                substs.repr(self.tcx()));
@@ -516,7 +516,7 @@ impl<'a> LookupContext<'a> {
         //
         // `confirm_candidate()` also relies upon this substitution
         // for Self. (fix)
-        let rcvr_substs = substs {
+        let rcvr_substs = subst::Substs {
             self_ty: Some(ty::mk_err()),
             ..(*substs).clone()
         };
@@ -1047,7 +1047,7 @@ impl<'a> LookupContext<'a> {
             return Some(MethodCallee {
                 origin: relevant_candidates.get(0).origin,
                 ty: ty::mk_err(),
-                substs: substs::empty()
+                substs: subst::Substs::empty()
             });
         }
 
@@ -1140,8 +1140,10 @@ impl<'a> LookupContext<'a> {
         // Determine values for the early-bound lifetime parameters.
         // FIXME -- permit users to manually specify lifetimes
         let mut all_regions: Vec<Region> = match candidate.rcvr_substs.regions {
-            NonerasedRegions(ref v) => v.iter().map(|r| r.clone()).collect(),
-            ErasedRegions => tcx.sess.span_bug(self.span, "ErasedRegions")
+            subst::NonerasedRegions(ref v) => {
+                v.iter().map(|r| r.clone()).collect()
+            }
+            subst::ErasedRegions => tcx.sess.span_bug(self.span, "ErasedRegions")
         };
         let m_regions =
             self.fcx.infcx().region_vars_for_defs(
@@ -1153,9 +1155,9 @@ impl<'a> LookupContext<'a> {
 
         // Construct the full set of type parameters for the method,
         // which is equal to the class tps + the method tps.
-        let all_substs = substs {
+        let all_substs = subst::Substs {
             tps: candidate.rcvr_substs.tps.clone().append(m_substs.as_slice()),
-            regions: NonerasedRegions(OwnedSlice::from_vec(all_regions)),
+            regions: subst::NonerasedRegions(all_regions),
             self_ty: candidate.rcvr_substs.self_ty,
         };
 
@@ -1164,7 +1166,7 @@ impl<'a> LookupContext<'a> {
         // Compute the method type with type parameters substituted
         debug!("fty={} all_substs={}",
                bare_fn_ty.repr(tcx),
-               ty::substs_to_str(tcx, &all_substs));
+               all_substs.repr(tcx));
 
         let fn_sig = &bare_fn_ty.sig;
         let inputs = match candidate.origin {
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 4ec6de9e4d2..a09c92d4db0 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -78,15 +78,17 @@ type parameter).
 
 
 use middle::const_eval;
+use middle::def;
 use middle::lang_items::{ExchangeHeapLangItem, GcLangItem};
 use middle::lang_items::{ManagedHeapLangItem};
 use middle::lint::UnreachableCode;
 use middle::pat_util::pat_id_map;
 use middle::pat_util;
-use middle::subst::Subst;
+use middle::subst;
+use middle::subst::{Subst, Substs};
 use middle::ty::{FnSig, VariantInfo};
 use middle::ty::{ty_param_bounds_and_ty, ty_param_substs_and_ty};
-use middle::ty::{substs, param_ty, Disr, ExprTyProvider};
+use middle::ty::{param_ty, Disr, ExprTyProvider};
 use middle::ty;
 use middle::ty_fold::TypeFolder;
 use middle::typeck::astconv::AstConv;
@@ -283,9 +285,11 @@ fn blank_fn_ctxt<'a>(ccx: &'a CrateCtxt<'a>,
 fn blank_inherited_fields<'a>(ccx: &'a CrateCtxt<'a>) -> Inherited<'a> {
     // It's kind of a kludge to manufacture a fake function context
     // and statement context, but we might as well do write the code only once
-    let param_env = ty::ParameterEnvironment { free_substs: substs::empty(),
-                                               self_param_bound: None,
-                                               type_param_bounds: Vec::new() };
+    let param_env = ty::ParameterEnvironment {
+        free_substs: subst::Substs::empty(),
+        self_param_bound: None,
+        type_param_bounds: Vec::new()
+    };
     Inherited::new(ccx.tcx, param_env)
 }
 
@@ -855,7 +859,7 @@ fn compare_impl_method(tcx: &ty::ctxt,
                        impl_m_span: Span,
                        impl_m_body_id: ast::NodeId,
                        trait_m: &ty::Method,
-                       trait_substs: &ty::substs) {
+                       trait_substs: &subst::Substs) {
     debug!("compare_impl_method()");
     let infcx = infer::new_infer_ctxt(tcx);
 
@@ -983,15 +987,15 @@ fn compare_impl_method(tcx: &ty::ctxt,
         impl_m.generics.type_param_defs().iter().enumerate().
         map(|(i,t)| ty::mk_param(tcx, i + impl_tps, t.def_id)).
         collect();
-    let dummy_impl_regions: OwnedSlice<ty::Region> =
+    let dummy_impl_regions: Vec<ty::Region> =
         impl_generics.region_param_defs().iter().
         map(|l| ty::ReFree(ty::FreeRegion {
                 scope_id: impl_m_body_id,
                 bound_region: ty::BrNamed(l.def_id, l.name)})).
         collect();
-    let dummy_substs = ty::substs {
+    let dummy_substs = subst::Substs {
         tps: dummy_impl_tps.append(dummy_method_tps.as_slice()),
-        regions: ty::NonerasedRegions(dummy_impl_regions),
+        regions: subst::NonerasedRegions(dummy_impl_regions),
         self_ty: None };
 
     // Create a bare fn type for trait/impl
@@ -1012,10 +1016,10 @@ fn compare_impl_method(tcx: &ty::ctxt,
     };
     debug!("impl_fty (post-subst): {}", ppaux::ty_to_str(tcx, impl_fty));
     let trait_fty = {
-        let substs { regions: trait_regions,
-                     tps: trait_tps,
-                     self_ty: self_ty } = trait_substs.subst(tcx, &dummy_substs);
-        let substs = substs {
+        let subst::Substs { regions: trait_regions,
+                            tps: trait_tps,
+                            self_ty: self_ty } = trait_substs.subst(tcx, &dummy_substs);
+        let substs = subst::Substs {
             regions: trait_regions,
             tps: trait_tps.append(dummy_method_tps.as_slice()),
             self_ty: self_ty,
@@ -1107,7 +1111,7 @@ impl<'a> FnCtxt<'a> {
     }
 
     pub fn write_substs(&self, node_id: ast::NodeId, substs: ty::ItemSubsts) {
-        if !ty::substs_is_noop(&substs.substs) {
+        if !substs.substs.is_noop() {
             debug!("write_substs({}, {}) in fcx {}",
                    node_id,
                    substs.repr(self.tcx()),
@@ -1121,7 +1125,7 @@ impl<'a> FnCtxt<'a> {
                            node_id: ast::NodeId,
                            ty: ty::t,
                            substs: ty::ItemSubsts) {
-        let ty = ty::subst(self.tcx(), &substs.substs, ty);
+        let ty = ty.subst(self.tcx(), &substs.substs);
         self.write_ty(node_id, ty);
         self.write_substs(node_id, substs);
     }
@@ -1185,7 +1189,7 @@ impl<'a> FnCtxt<'a> {
         }
     }
 
-    pub fn method_ty_substs(&self, id: ast::NodeId) -> ty::substs {
+    pub fn method_ty_substs(&self, id: ast::NodeId) -> subst::Substs {
         match self.inh.method_map.borrow().find(&MethodCall::expr(id)) {
             Some(method) => method.substs.clone(),
             None => {
@@ -1488,12 +1492,12 @@ pub fn impl_self_ty(vcx: &VtableContext,
     let rps = vcx.infcx.region_vars_for_defs(span, rps);
     let tps = vcx.infcx.next_ty_vars(n_tps);
 
-    let substs = substs {
-        regions: ty::NonerasedRegions(rps),
+    let substs = subst::Substs {
+        regions: subst::NonerasedRegions(rps),
         self_ty: None,
         tps: tps,
     };
-    let substd_ty = ty::subst(tcx, &substs, raw_ty);
+    let substd_ty = raw_ty.subst(tcx, &substs);
 
     ty_param_substs_and_ty { substs: substs, ty: substd_ty }
 }
@@ -1504,7 +1508,7 @@ pub fn lookup_field_ty(tcx: &ty::ctxt,
                        class_id: ast::DefId,
                        items: &[ty::field_ty],
                        fieldname: ast::Name,
-                       substs: &ty::substs) -> Option<ty::t> {
+                       substs: &subst::Substs) -> Option<ty::t> {
 
     let o_field = items.iter().find(|f| f.name == fieldname);
     o_field.map(|f| ty::lookup_field_type(tcx, class_id, f.id, substs))
@@ -1520,13 +1524,13 @@ pub enum DerefArgs {
 // Given the provenance of a static method, returns the generics of the static
 // method's container.
 fn generics_of_static_method_container(type_context: &ty::ctxt,
-                                       provenance: ast::MethodProvenance)
+                                       provenance: def::MethodProvenance)
                                        -> ty::Generics {
     match provenance {
-        ast::FromTrait(trait_def_id) => {
+        def::FromTrait(trait_def_id) => {
             ty::lookup_trait_def(type_context, trait_def_id).generics.clone()
         }
-        ast::FromImpl(impl_def_id) => {
+        def::FromImpl(impl_def_id) => {
             ty::lookup_item_type(type_context, impl_def_id).generics.clone()
         }
     }
@@ -1536,7 +1540,7 @@ fn generics_of_static_method_container(type_context: &ty::ctxt,
 // locations.
 fn check_type_parameter_positions_in_path(function_context: &FnCtxt,
                                           path: &ast::Path,
-                                          def: ast::Def) {
+                                          def: def::Def) {
     // We only care about checking the case in which the path has two or
     // more segments.
     if path.segments.len() < 2 {
@@ -1577,13 +1581,13 @@ fn check_type_parameter_positions_in_path(function_context: &FnCtxt,
         // ensure that the segment of the path which names the trait or
         // implementation (the penultimate segment) is annotated with the
         // right number of type parameters.
-        ast::DefStaticMethod(_, provenance, _) => {
+        def::DefStaticMethod(_, provenance, _) => {
             let generics =
                 generics_of_static_method_container(function_context.ccx.tcx,
                                                     provenance);
             let name = match provenance {
-                ast::FromTrait(_) => "trait",
-                ast::FromImpl(_) => "impl",
+                def::FromTrait(_) => "trait",
+                def::FromImpl(_) => "impl",
             };
 
             let trait_segment = &path.segments.get(path.segments.len() - 2);
@@ -2437,7 +2441,7 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
                                       span: Span,
                                       class_id: ast::DefId,
                                       node_id: ast::NodeId,
-                                      substitutions: ty::substs,
+                                      substitutions: subst::Substs,
                                       field_types: &[ty::field_ty],
                                       ast_fields: &[ast::Field],
                                       check_completeness: bool)  {
@@ -2543,13 +2547,13 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
         // Generate the struct type.
         let regions = fcx.infcx().region_vars_for_defs(span, region_param_defs);
         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
-        let substitutions = substs {
-            regions: ty::NonerasedRegions(regions),
+        let substitutions = subst::Substs {
+            regions: subst::NonerasedRegions(regions),
             self_ty: None,
             tps: type_parameters
         };
 
-        let mut struct_type = ty::subst(tcx, &substitutions, raw_type);
+        let mut struct_type = raw_type.subst(tcx, &substitutions);
 
         // Look up and check the fields.
         let class_fields = ty::lookup_struct_fields(tcx, class_id);
@@ -2599,13 +2603,13 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
         // Generate the enum type.
         let regions = fcx.infcx().region_vars_for_defs(span, region_param_defs);
         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
-        let substitutions = substs {
-            regions: ty::NonerasedRegions(regions),
+        let substitutions = subst::Substs {
+            regions: subst::NonerasedRegions(regions),
             self_ty: None,
             tps: type_parameters
         };
 
-        let enum_type = ty::subst(tcx, &substitutions, raw_type);
+        let enum_type = raw_type.subst(tcx, &substitutions);
 
         // Look up and check the enum variant fields.
         let variant_fields = ty::lookup_struct_fields(tcx, variant_id);
@@ -2703,7 +2707,7 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
                   // FIXME(pcwalton): For now we hardcode the two permissible
                   // places: the exchange heap and the managed heap.
                   let definition = lookup_def(fcx, path.span, place.id);
-                  let def_id = ast_util::def_id_of_def(definition);
+                  let def_id = definition.def_id();
                   match tcx.lang_items
                            .items
                            .get(ExchangeHeapLangItem as uint) {
@@ -2734,10 +2738,10 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
                                       }
                                   };
                               let regions =
-                                  ty::NonerasedRegions(OwnedSlice::empty());
+                                  subst::NonerasedRegions(Vec::new());
                               let sty = ty::mk_struct(tcx,
                                                       gc_struct_id,
-                                                      substs {
+                                                      subst::Substs {
                                                         self_ty: None,
                                                         tps: vec!(
                                                             fcx.expr_ty(
@@ -3253,11 +3257,11 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
         // Resolve the path.
         let def = tcx.def_map.borrow().find(&id).map(|i| *i);
         match def {
-            Some(ast::DefStruct(type_def_id)) => {
+            Some(def::DefStruct(type_def_id)) => {
                 check_struct_constructor(fcx, id, expr.span, type_def_id,
                                          fields.as_slice(), base_expr);
             }
-            Some(ast::DefVariant(enum_id, variant_id, _)) => {
+            Some(def::DefVariant(enum_id, variant_id, _)) => {
                 check_struct_enum_variant(fcx, id, expr.span, enum_id,
                                           variant_id, fields.as_slice());
             }
@@ -3806,54 +3810,54 @@ pub fn check_enum_variants(ccx: &CrateCtxt,
     check_instantiable(ccx.tcx, sp, id);
 }
 
-pub fn lookup_def(fcx: &FnCtxt, sp: Span, id: ast::NodeId) -> ast::Def {
+pub fn lookup_def(fcx: &FnCtxt, sp: Span, id: ast::NodeId) -> def::Def {
     lookup_def_ccx(fcx.ccx, sp, id)
 }
 
 // Returns the type parameter count and the type for the given definition.
 pub fn ty_param_bounds_and_ty_for_def(fcx: &FnCtxt,
                                       sp: Span,
-                                      defn: ast::Def)
+                                      defn: def::Def)
                                    -> ty_param_bounds_and_ty {
     match defn {
-      ast::DefArg(nid, _) | ast::DefLocal(nid, _) |
-      ast::DefBinding(nid, _) => {
+      def::DefArg(nid, _) | def::DefLocal(nid, _) |
+      def::DefBinding(nid, _) => {
           let typ = fcx.local_ty(sp, nid);
           return no_params(typ);
       }
-      ast::DefFn(id, _) | ast::DefStaticMethod(id, _, _) |
-      ast::DefStatic(id, _) | ast::DefVariant(_, id, _) |
-      ast::DefStruct(id) => {
+      def::DefFn(id, _) | def::DefStaticMethod(id, _, _) |
+      def::DefStatic(id, _) | def::DefVariant(_, id, _) |
+      def::DefStruct(id) => {
         return ty::lookup_item_type(fcx.ccx.tcx, id);
       }
-      ast::DefUpvar(_, inner, _, _) => {
+      def::DefUpvar(_, inner, _, _) => {
         return ty_param_bounds_and_ty_for_def(fcx, sp, *inner);
       }
-      ast::DefTrait(_) |
-      ast::DefTy(_) |
-      ast::DefPrimTy(_) |
-      ast::DefTyParam(..)=> {
+      def::DefTrait(_) |
+      def::DefTy(_) |
+      def::DefPrimTy(_) |
+      def::DefTyParam(..)=> {
         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found type");
       }
-      ast::DefMod(..) | ast::DefForeignMod(..) => {
+      def::DefMod(..) | def::DefForeignMod(..) => {
         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found module");
       }
-      ast::DefUse(..) => {
+      def::DefUse(..) => {
         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found use");
       }
-      ast::DefRegion(..) => {
+      def::DefRegion(..) => {
         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found region");
       }
-      ast::DefTyParamBinder(..) => {
+      def::DefTyParamBinder(..) => {
         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found type parameter");
       }
-      ast::DefLabel(..) => {
+      def::DefLabel(..) => {
         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found label");
       }
-      ast::DefSelfTy(..) => {
+      def::DefSelfTy(..) => {
         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found self ty");
       }
-      ast::DefMethod(..) => {
+      def::DefMethod(..) => {
         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found method");
       }
     }
@@ -3864,7 +3868,7 @@ pub fn ty_param_bounds_and_ty_for_def(fcx: &FnCtxt,
 pub fn instantiate_path(fcx: &FnCtxt,
                         pth: &ast::Path,
                         tpt: ty_param_bounds_and_ty,
-                        def: ast::Def,
+                        def: def::Def,
                         span: Span,
                         node_id: ast::NodeId) {
     debug!(">>> instantiate_path");
@@ -3888,8 +3892,10 @@ pub fn instantiate_path(fcx: &FnCtxt,
     let num_expected_regions = tpt.generics.region_param_defs().len();
     let num_supplied_regions = pth.segments.last().unwrap().lifetimes.len();
     let regions = if num_expected_regions == num_supplied_regions {
-        OwnedSlice::from_vec(pth.segments.last().unwrap().lifetimes.iter().map(
-            |l| ast_region_to_region(fcx.tcx(), l)).collect())
+        pth.segments.last().unwrap().lifetimes
+            .iter()
+            .map(|l| ast_region_to_region(fcx.tcx(), l))
+            .collect()
     } else {
         if num_supplied_regions != 0 {
             fcx.ccx.tcx.sess.span_err(
@@ -3904,7 +3910,7 @@ pub fn instantiate_path(fcx: &FnCtxt,
 
         fcx.infcx().region_vars_for_defs(span, tpt.generics.region_param_defs.as_slice())
     };
-    let regions = ty::NonerasedRegions(regions);
+    let regions = subst::NonerasedRegions(regions);
 
     // Special case: If there is a self parameter, omit it from the list of
     // type parameters.
@@ -3913,7 +3919,7 @@ pub fn instantiate_path(fcx: &FnCtxt,
     // of type parameters actually manifest in the AST. This will differ from
     // the internal type parameter count when there are self types involved.
     let (user_ty_param_count, user_ty_param_req, self_parameter_index) = match def {
-        ast::DefStaticMethod(_, provenance @ ast::FromTrait(_), _) => {
+        def::DefStaticMethod(_, provenance @ def::FromTrait(_), _) => {
             let generics = generics_of_static_method_container(fcx.ccx.tcx,
                                                                provenance);
             (ty_param_count - 1, ty_param_req - 1, Some(generics.type_param_defs().len()))
@@ -3980,7 +3986,7 @@ pub fn instantiate_path(fcx: &FnCtxt,
             tps.push(ty)
         }
 
-        let mut substs = substs {
+        let mut substs = subst::Substs {
             regions: regions,
             self_ty: None,
             tps: tps
@@ -4020,13 +4026,13 @@ pub fn instantiate_path(fcx: &FnCtxt,
 
         assert_eq!(substs.tps.len(), ty_param_count)
 
-        let substs {tps, regions, ..} = substs;
+        let subst::Substs {tps, regions, ..} = substs;
         (tps, regions)
     };
 
-    let substs = substs { regions: regions,
-                          self_ty: None,
-                          tps: tps };
+    let substs = subst::Substs { regions: regions,
+                                 self_ty: None,
+                                 tps: tps };
 
     fcx.write_ty_substs(node_id, tpt.ty, ty::ItemSubsts {
         substs: substs,
@@ -4148,7 +4154,7 @@ pub fn may_break(cx: &ty::ctxt, id: ast::NodeId, b: ast::P<ast::Block>) -> bool
         match e.node {
             ast::ExprBreak(Some(_)) => {
                 match cx.def_map.borrow().find(&e.id) {
-                    Some(&ast::DefLabel(loop_id)) if id == loop_id => true,
+                    Some(&def::DefLabel(loop_id)) if id == loop_id => true,
                     _ => false,
                 }
             }
@@ -4261,10 +4267,10 @@ pub fn check_intrinsic_type(ccx: &CrateCtxt, it: &ast::ForeignItem) {
             "type_id" => {
                 let langid = ccx.tcx.lang_items.require(TypeIdLangItem);
                 match langid {
-                    Ok(did) => (1u, Vec::new(), ty::mk_struct(ccx.tcx, did, substs {
+                    Ok(did) => (1u, Vec::new(), ty::mk_struct(ccx.tcx, did, subst::Substs {
                                                  self_ty: None,
                                                  tps: Vec::new(),
-                                                 regions: ty::NonerasedRegions(OwnedSlice::empty())
+                                                 regions: subst::NonerasedRegions(Vec::new())
                                                  }) ),
                     Err(msg) => {
                         tcx.sess.span_fatal(it.span, msg.as_slice());
diff --git a/src/librustc/middle/typeck/check/regionck.rs b/src/librustc/middle/typeck/check/regionck.rs
index 34e8b5e169f..e1db465424a 100644
--- a/src/librustc/middle/typeck/check/regionck.rs
+++ b/src/librustc/middle/typeck/check/regionck.rs
@@ -118,7 +118,8 @@ and report an error, and it just seems like more mess in the end.)
 
 */
 
-
+use middle::def;
+use middle::def::{DefArg, DefBinding, DefLocal, DefUpvar};
 use middle::freevars;
 use mc = middle::mem_categorization;
 use middle::ty::{ReScope};
@@ -134,9 +135,7 @@ use middle::pat_util;
 use util::nodemap::NodeMap;
 use util::ppaux::{ty_to_str, region_to_str, Repr};
 
-use syntax::ast::{DefArg, DefBinding, DefLocal, DefUpvar};
 use syntax::ast;
-use syntax::ast_util;
 use syntax::codemap::Span;
 use syntax::visit;
 use syntax::visit::Visitor;
@@ -163,7 +162,7 @@ pub struct Rcx<'a> {
     repeating_scope: ast::NodeId,
 }
 
-fn region_of_def(fcx: &FnCtxt, def: ast::Def) -> ty::Region {
+fn region_of_def(fcx: &FnCtxt, def: def::Def) -> ty::Region {
     /*!
      * Returns the validity region of `def` -- that is, how long
      * is `def` valid?
@@ -665,7 +664,7 @@ fn check_expr_fn_block(rcx: &mut Rcx,
 
             // Identify the variable being closed over and its node-id.
             let def = freevar.def;
-            let def_id = ast_util::def_id_of_def(def);
+            let def_id = def.def_id();
             assert!(def_id.krate == ast::LOCAL_CRATE);
             let upvar_id = ty::UpvarId { var_id: def_id.node,
                                          closure_expr_id: expr.id };
@@ -725,7 +724,7 @@ fn check_expr_fn_block(rcx: &mut Rcx,
             // determining the final borrow_kind) and propagate that as
             // a constraint on the outer closure.
             match freevar.def {
-                ast::DefUpvar(var_id, _, outer_closure_id, _) => {
+                def::DefUpvar(var_id, _, outer_closure_id, _) => {
                     // thing being captured is itself an upvar:
                     let outer_upvar_id = ty::UpvarId {
                         var_id: var_id,
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index 7ad18ddfe5c..0665ae651f0 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -23,6 +23,7 @@ use middle::typeck::{vtable_origin, vtable_res, vtable_param_res};
 use middle::typeck::{vtable_static, vtable_param, impl_res};
 use middle::typeck::{param_numbered, param_self, param_index};
 use middle::typeck::MethodCall;
+use middle::subst;
 use middle::subst::Subst;
 use util::common::indenter;
 use util::ppaux;
@@ -73,15 +74,10 @@ impl<'a> VtableContext<'a> {
     pub fn tcx(&self) -> &'a ty::ctxt { self.infcx.tcx }
 }
 
-fn has_trait_bounds(type_param_defs: &[ty::TypeParameterDef]) -> bool {
-    type_param_defs.iter().any(
-        |type_param_def| !type_param_def.bounds.trait_bounds.is_empty())
-}
-
 fn lookup_vtables(vcx: &VtableContext,
                   span: Span,
                   type_param_defs: &[ty::TypeParameterDef],
-                  substs: &ty::substs,
+                  substs: &subst::Substs,
                   is_early: bool) -> vtable_res {
     debug!("lookup_vtables(span={:?}, \
             type_param_defs={}, \
@@ -118,7 +114,7 @@ fn lookup_vtables(vcx: &VtableContext,
 fn lookup_vtables_for_param(vcx: &VtableContext,
                             span: Span,
                             // None for substs means the identity
-                            substs: Option<&ty::substs>,
+                            substs: Option<&subst::Substs>,
                             type_param_bounds: &ty::ParamBounds,
                             ty: ty::t,
                             is_early: bool) -> vtable_param_res {
@@ -464,9 +460,9 @@ fn search_for_vtable(vcx: &VtableContext,
 fn fixup_substs(vcx: &VtableContext,
                 span: Span,
                 id: ast::DefId,
-                substs: ty::substs,
+                substs: subst::Substs,
                 is_early: bool)
-                -> Option<ty::substs> {
+                -> Option<subst::Substs> {
     let tcx = vcx.tcx();
     // use a dummy type just to package up the substs that need fixing up
     let t = ty::mk_trait(tcx,
@@ -503,7 +499,7 @@ fn fixup_ty(vcx: &VtableContext,
 
 fn connect_trait_tps(vcx: &VtableContext,
                      span: Span,
-                     impl_substs: &ty::substs,
+                     impl_substs: &subst::Substs,
                      trait_ref: Rc<ty::TraitRef>,
                      impl_did: ast::DefId) {
     let tcx = vcx.tcx();
@@ -566,7 +562,7 @@ pub fn early_resolve_expr(ex: &ast::Expr, fcx: &FnCtxt, is_early: bool) {
                       let vcx = fcx.vtable_context();
                       let target_trait_ref = Rc::new(ty::TraitRef {
                           def_id: target_def_id,
-                          substs: ty::substs {
+                          substs: subst::Substs {
                               tps: target_substs.tps.clone(),
                               regions: target_substs.regions.clone(),
                               self_ty: Some(typ)
@@ -631,20 +627,18 @@ pub fn early_resolve_expr(ex: &ast::Expr, fcx: &FnCtxt, is_early: bool) {
             debug!("vtable resolution on parameter bounds for expr {}",
                    ex.repr(fcx.tcx()));
             let def = cx.tcx.def_map.borrow().get_copy(&ex.id);
-            let did = ast_util::def_id_of_def(def);
+            let did = def.def_id();
             let item_ty = ty::lookup_item_type(cx.tcx, did);
             debug!("early resolve expr: def {:?} {:?}, {:?}, {}", ex.id, did, def,
                    fcx.infcx().ty_to_str(item_ty.ty));
-            if has_trait_bounds(item_ty.generics.type_param_defs()) {
-                debug!("early_resolve_expr: looking up vtables for type params {}",
-                       item_ty.generics.type_param_defs().repr(fcx.tcx()));
-                let vcx = fcx.vtable_context();
-                let vtbls = lookup_vtables(&vcx, ex.span,
-                                           item_ty.generics.type_param_defs(),
-                                           &item_substs.substs, is_early);
-                if !is_early {
-                    insert_vtables(fcx, MethodCall::expr(ex.id), vtbls);
-                }
+            debug!("early_resolve_expr: looking up vtables for type params {}",
+                   item_ty.generics.type_param_defs().repr(fcx.tcx()));
+            let vcx = fcx.vtable_context();
+            let vtbls = lookup_vtables(&vcx, ex.span,
+                                       item_ty.generics.type_param_defs(),
+                                       &item_substs.substs, is_early);
+            if !is_early {
+                insert_vtables(fcx, MethodCall::expr(ex.id), vtbls);
             }
         });
       }
@@ -657,19 +651,17 @@ pub fn early_resolve_expr(ex: &ast::Expr, fcx: &FnCtxt, is_early: bool) {
       ast::ExprMethodCall(_, _, _) => {
         match fcx.inh.method_map.borrow().find(&MethodCall::expr(ex.id)) {
           Some(method) => {
-            debug!("vtable resolution on parameter bounds for method call {}",
-                   ex.repr(fcx.tcx()));
-            let type_param_defs = ty::method_call_type_param_defs(cx.tcx, method.origin);
-            if has_trait_bounds(type_param_defs.as_slice()) {
-                let substs = fcx.method_ty_substs(ex.id);
-                let vcx = fcx.vtable_context();
-                let vtbls = lookup_vtables(&vcx, ex.span,
-                                           type_param_defs.as_slice(),
-                                           &substs, is_early);
-                if !is_early {
-                    insert_vtables(fcx, MethodCall::expr(ex.id), vtbls);
-                }
-            }
+              debug!("vtable resolution on parameter bounds for method call {}",
+                     ex.repr(fcx.tcx()));
+              let type_param_defs = ty::method_call_type_param_defs(cx.tcx, method.origin);
+              let substs = fcx.method_ty_substs(ex.id);
+              let vcx = fcx.vtable_context();
+              let vtbls = lookup_vtables(&vcx, ex.span,
+                                         type_param_defs.as_slice(),
+                                         &substs, is_early);
+              if !is_early {
+                  insert_vtables(fcx, MethodCall::expr(ex.id), vtbls);
+              }
           }
           None => {}
         }
@@ -695,15 +687,13 @@ pub fn early_resolve_expr(ex: &ast::Expr, fcx: &FnCtxt, is_early: bool) {
                                        ex.repr(fcx.tcx()));
                                 let type_param_defs =
                                     ty::method_call_type_param_defs(cx.tcx, method.origin);
-                                if has_trait_bounds(type_param_defs.deref().as_slice()) {
-                                    let vcx = fcx.vtable_context();
-                                    let vtbls = lookup_vtables(&vcx, ex.span,
-                                                               type_param_defs.deref()
-                                                               .as_slice(),
-                                                               &method.substs, is_early);
-                                    if !is_early {
-                                        insert_vtables(fcx, method_call, vtbls);
-                                    }
+                                let vcx = fcx.vtable_context();
+                                let vtbls = lookup_vtables(&vcx, ex.span,
+                                                           type_param_defs.deref()
+                                                           .as_slice(),
+                                                           &method.substs, is_early);
+                                if !is_early {
+                                    insert_vtables(fcx, method_call, vtbls);
                                 }
                             }
                             None => {}
@@ -799,23 +789,19 @@ pub fn resolve_impl(tcx: &ty::ctxt,
 /// Resolve vtables for a method call after typeck has finished.
 /// Used by trans to monomorphize artificial method callees (e.g. drop).
 pub fn trans_resolve_method(tcx: &ty::ctxt, id: ast::NodeId,
-                            substs: &ty::substs) -> Option<vtable_res> {
+                            substs: &subst::Substs) -> vtable_res {
     let generics = ty::lookup_item_type(tcx, ast_util::local_def(id)).generics;
     let type_param_defs = &*generics.type_param_defs;
-    if has_trait_bounds(type_param_defs.as_slice()) {
-        let vcx = VtableContext {
-            infcx: &infer::new_infer_ctxt(tcx),
-            param_env: &ty::construct_parameter_environment(tcx, None, [], [], [], [], id)
-        };
+    let vcx = VtableContext {
+        infcx: &infer::new_infer_ctxt(tcx),
+        param_env: &ty::construct_parameter_environment(tcx, None, [], [], [], [], id)
+    };
 
-        Some(lookup_vtables(&vcx,
-                            tcx.map.span(id),
-                            type_param_defs.as_slice(),
-                            substs,
-                            false))
-    } else {
-        None
-    }
+    lookup_vtables(&vcx,
+                   tcx.map.span(id),
+                   type_param_defs.as_slice(),
+                   substs,
+                   false)
 }
 
 impl<'a, 'b> visit::Visitor<()> for &'a FnCtxt<'b> {
diff --git a/src/librustc/middle/typeck/check/writeback.rs b/src/librustc/middle/typeck/check/writeback.rs
index 133fc9b1530..63dc122f7cb 100644
--- a/src/librustc/middle/typeck/check/writeback.rs
+++ b/src/librustc/middle/typeck/check/writeback.rs
@@ -12,8 +12,9 @@
 // unresolved type variables and replaces "ty_var" types with their
 // substitutions.
 
-
+use middle::def;
 use middle::pat_util;
+use middle::subst;
 use middle::ty;
 use middle::ty_fold::{TypeFolder,TypeFoldable};
 use middle::typeck::astconv::AstConv;
@@ -231,10 +232,10 @@ impl<'cx> WritebackCx<'cx> {
                         // bare functions to coerce to a closure to avoid
                         // constructing (slower) indirect call wrappers.
                         match self.tcx().def_map.borrow().find(&id) {
-                            Some(&ast::DefFn(..)) |
-                            Some(&ast::DefStaticMethod(..)) |
-                            Some(&ast::DefVariant(..)) |
-                            Some(&ast::DefStruct(_)) => {
+                            Some(&def::DefFn(..)) |
+                            Some(&def::DefStaticMethod(..)) |
+                            Some(&def::DefVariant(..)) |
+                            Some(&def::DefStruct(_)) => {
                             }
                             _ => {
                                 self.tcx().sess.span_err(
@@ -291,7 +292,7 @@ impl<'cx> WritebackCx<'cx> {
                 // probably for invocations on objects, and this
                 // causes encoding failures). -nmatsakis
                 new_method.substs.self_ty = None;
-                new_method.substs.regions = ty::ErasedRegions;
+                new_method.substs.regions = subst::ErasedRegions;
 
                 self.tcx().method_map.borrow_mut().insert(
                     method_call,
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index e4b2d2da2e8..99a6aad715c 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -17,9 +17,11 @@
 
 use metadata::csearch::{each_impl, get_impl_trait, each_implementation_for_trait};
 use metadata::csearch;
+use middle::subst;
+use middle::subst::{Substs};
 use middle::ty::get;
-use middle::ty::{ImplContainer, lookup_item_type, subst};
-use middle::ty::{substs, t, ty_bool, ty_char, ty_bot, ty_box, ty_enum, ty_err};
+use middle::ty::{ImplContainer, lookup_item_type};
+use middle::ty::{t, ty_bool, ty_char, ty_bot, ty_box, ty_enum, ty_err};
 use middle::ty::{ty_str, ty_vec, ty_float, ty_infer, ty_int, ty_nil};
 use middle::ty::{ty_param, ty_param_bounds_and_ty, ty_ptr};
 use middle::ty::{ty_rptr, ty_self, ty_struct, ty_trait, ty_tup};
@@ -33,15 +35,15 @@ use middle::typeck::infer::InferCtxt;
 use middle::typeck::infer::{new_infer_ctxt, resolve_ivar, resolve_type};
 use middle::typeck::infer;
 use util::ppaux::Repr;
-use syntax::ast::{Crate, DefId, DefStruct, DefTy};
+use middle::def::{DefStruct, DefTy};
+use syntax::ast::{Crate, DefId};
 use syntax::ast::{Item, ItemEnum, ItemImpl, ItemMod, ItemStruct};
 use syntax::ast::{LOCAL_CRATE, TraitRef, TyPath};
 use syntax::ast;
 use syntax::ast_map::NodeItem;
 use syntax::ast_map;
-use syntax::ast_util::{def_id_of_def, local_def};
+use syntax::ast_util::{local_def};
 use syntax::codemap::Span;
-use syntax::owned_slice::OwnedSlice;
 use syntax::parse::token;
 use syntax::visit;
 
@@ -505,14 +507,12 @@ impl<'a> CoherenceChecker<'a> {
         let bounds_count = polytype.generics.type_param_defs().len();
         let type_parameters = self.inference_context.next_ty_vars(bounds_count);
 
-        let substitutions = substs {
-            regions: ty::NonerasedRegions(region_parameters),
+        let substitutions = subst::Substs {
+            regions: subst::NonerasedRegions(region_parameters),
             self_ty: None,
             tps: type_parameters
         };
-        let monotype = subst(self.crate_context.tcx,
-                             &substitutions,
-                             polytype.ty);
+        let monotype = polytype.ty.subst(self.crate_context.tcx, &substitutions);
 
         UniversalQuantificationResult {
             monotype: monotype,
@@ -544,7 +544,7 @@ impl<'a> CoherenceChecker<'a> {
     fn trait_ref_to_trait_def_id(&self, trait_ref: &TraitRef) -> DefId {
         let def_map = &self.crate_context.tcx.def_map;
         let trait_def = def_map.borrow().get_copy(&trait_ref.ref_id);
-        let trait_id = def_id_of_def(trait_def);
+        let trait_id = trait_def.def_id();
         return trait_id;
     }
 
@@ -730,7 +730,7 @@ pub fn make_substs_for_receiver_types(tcx: &ty::ctxt,
                                       impl_id: ast::DefId,
                                       trait_ref: &ty::TraitRef,
                                       method: &ty::Method)
-                                      -> ty::substs {
+                                      -> subst::Substs {
     /*!
      * Substitutes the values for the receiver's type parameters
      * that are found in method, leaving the method's type parameters
@@ -753,17 +753,17 @@ pub fn make_substs_for_receiver_types(tcx: &ty::ctxt,
     let mut combined_tps = trait_ref.substs.tps.clone();
     combined_tps.push_all_move(meth_tps);
     let combined_regions = match &trait_ref.substs.regions {
-        &ty::ErasedRegions =>
+        &subst::ErasedRegions =>
             fail!("make_substs_for_receiver_types: unexpected ErasedRegions"),
 
-        &ty::NonerasedRegions(ref rs) => {
-            let mut rs = rs.clone().into_vec();
+        &subst::NonerasedRegions(ref rs) => {
+            let mut rs = rs.clone();
             rs.push_all_move(meth_regions);
-            ty::NonerasedRegions(OwnedSlice::from_vec(rs))
+            subst::NonerasedRegions(rs)
         }
     };
 
-    ty::substs {
+    subst::Substs {
         regions: combined_regions,
         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 c32aa2dd31c..c6bc6ce7297 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -32,12 +32,14 @@ are represented as `ty_param()` instances.
 
 
 use metadata::csearch;
+use middle::def;
 use middle::lang_items::SizedTraitLangItem;
 use middle::resolve_lifetime;
-use middle::ty::{ImplContainer, MethodContainer, TraitContainer, substs};
+use middle::subst;
+use middle::subst::{Subst, Substs};
+use middle::ty::{ImplContainer, MethodContainer, TraitContainer};
 use middle::ty::{ty_param_bounds_and_ty};
 use middle::ty;
-use middle::subst::Subst;
 use middle::typeck::astconv::{AstConv, ty_of_arg};
 use middle::typeck::astconv::{ast_ty_to_ty};
 use middle::typeck::astconv;
@@ -320,16 +322,14 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt, trait_id: ast::NodeId) {
         //     A,B,C => A',B',C'
         //     Self => D'
         //     D,E,F => E',F',G'
-        let substs = substs {
-            regions: ty::NonerasedRegions(rps_from_trait),
+        let substs = subst::Substs {
+            regions: subst::NonerasedRegions(rps_from_trait),
             self_ty: Some(self_param),
             tps: non_shifted_trait_tps.append(shifted_method_tps.as_slice())
         };
 
         // create the type of `foo`, applying the substitution above
-        let ty = ty::subst(tcx,
-                           &substs,
-                           ty::mk_bare_fn(tcx, m.fty.clone()));
+        let ty = ty::mk_bare_fn(tcx, m.fty.clone()).subst(tcx, &substs);
 
         // create the type parameter definitions for `foo`, applying
         // the substitution to any traits that appear in their bounds.
@@ -741,7 +741,7 @@ pub fn convert_struct(ccx: &CrateCtxt,
             ast::TyPath(_, _, path_id) => {
                 let def_map = tcx.def_map.borrow();
                 match def_map.find(&path_id) {
-                    Some(&ast::DefStruct(def_id)) => {
+                    Some(&def::DefStruct(def_id)) => {
                         // FIXME(#12511) Check for cycles in the inheritance hierarchy.
                         // Check super-struct is virtual.
                         match tcx.map.find(def_id.node) {
@@ -832,7 +832,7 @@ pub fn instantiate_trait_ref(ccx: &CrateCtxt,
     let rscope = ExplicitRscope;
 
     match lookup_def_tcx(ccx.tcx, ast_trait_ref.path.span, ast_trait_ref.ref_id) {
-        ast::DefTrait(trait_did) => {
+        def::DefTrait(trait_did) => {
             let trait_ref =
                 astconv::ast_path_to_trait_ref(
                     ccx, &rscope, trait_did, Some(self_ty), &ast_trait_ref.path);
@@ -1211,17 +1211,18 @@ pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
 
 pub fn mk_item_substs(ccx: &CrateCtxt,
                       ty_generics: &ty::Generics,
-                      self_ty: Option<ty::t>) -> ty::substs
+                      self_ty: Option<ty::t>)
+                      -> subst::Substs
 {
     let params: Vec<ty::t> =
         ty_generics.type_param_defs().iter().enumerate().map(
             |(i, t)| ty::mk_param(ccx.tcx, i, t.def_id)).collect();
 
-    let regions: OwnedSlice<ty::Region> =
+    let regions: Vec<ty::Region> =
         ty_generics.region_param_defs().iter().enumerate().map(
             |(i, l)| ty::ReEarlyBound(l.def_id.node, i, l.name)).collect();
 
-    substs {regions: ty::NonerasedRegions(regions),
-            self_ty: self_ty,
-            tps: params}
+    subst::Substs {regions: subst::NonerasedRegions(regions),
+                   self_ty: self_ty,
+                   tps: params}
 }
diff --git a/src/librustc/middle/typeck/infer/coercion.rs b/src/librustc/middle/typeck/infer/coercion.rs
index 819a69cfad1..4a2cd7cbec2 100644
--- a/src/librustc/middle/typeck/infer/coercion.rs
+++ b/src/librustc/middle/typeck/infer/coercion.rs
@@ -64,7 +64,7 @@ we may want to adjust precisely when coercions occur.
 
 */
 
-
+use middle::subst;
 use middle::ty::{AutoPtr, AutoBorrowVec, AutoBorrowObj, AutoDerefRef};
 use middle::ty::{mt};
 use middle::ty;
@@ -443,7 +443,7 @@ impl<'f> Coerce<'f> {
                          sty_a: &ty::sty,
                          b: ty::t,
                          trait_def_id: ast::DefId,
-                         trait_substs: &ty::substs,
+                         trait_substs: &subst::Substs,
                          trait_store: ty::TraitStore,
                          bounds: ty::BuiltinBounds) -> CoerceResult {
 
diff --git a/src/librustc/middle/typeck/infer/combine.rs b/src/librustc/middle/typeck/infer/combine.rs
index 8ac6b19f657..2e8698e59aa 100644
--- a/src/librustc/middle/typeck/infer/combine.rs
+++ b/src/librustc/middle/typeck/infer/combine.rs
@@ -47,8 +47,10 @@
 // now.
 
 
+use middle::subst;
+use middle::subst::Substs;
 use middle::ty::{FloatVar, FnSig, IntVar, TyVar};
-use middle::ty::{IntType, UintType, substs};
+use middle::ty::{IntType, UintType};
 use middle::ty::{BuiltinBounds};
 use middle::ty;
 use middle::typeck::infer::{then, ToUres};
@@ -66,7 +68,6 @@ use std::result;
 
 use syntax::ast::{Onceness, FnStyle};
 use syntax::ast;
-use syntax::owned_slice::OwnedSlice;
 use syntax::abi;
 
 pub trait Combine {
@@ -127,22 +128,23 @@ pub trait Combine {
 
     fn substs(&self,
               item_def_id: ast::DefId,
-              as_: &ty::substs,
-              bs: &ty::substs) -> cres<ty::substs> {
-
+              as_: &subst::Substs,
+              bs: &subst::Substs)
+              -> cres<subst::Substs>
+    {
         fn relate_region_params<C:Combine>(this: &C,
                                            item_def_id: ast::DefId,
-                                           a: &ty::RegionSubsts,
-                                           b: &ty::RegionSubsts)
-                                           -> cres<ty::RegionSubsts> {
+                                           a: &subst::RegionSubsts,
+                                           b: &subst::RegionSubsts)
+                                           -> cres<subst::RegionSubsts> {
             let tcx = this.infcx().tcx;
             match (a, b) {
-                (&ty::ErasedRegions, _) | (_, &ty::ErasedRegions) => {
-                    Ok(ty::ErasedRegions)
+                (&subst::ErasedRegions, _) | (_, &subst::ErasedRegions) => {
+                    Ok(subst::ErasedRegions)
                 }
 
-                (&ty::NonerasedRegions(ref a_rs),
-                 &ty::NonerasedRegions(ref b_rs)) => {
+                (&subst::NonerasedRegions(ref a_rs),
+                 &subst::NonerasedRegions(ref b_rs)) => {
                     let variances = ty::item_variances(tcx, item_def_id);
                     let region_params = &variances.region_params;
                     let num_region_params = region_params.len();
@@ -175,7 +177,7 @@ pub trait Combine {
                         };
                         rs.push(if_ok!(r));
                     }
-                    Ok(ty::NonerasedRegions(OwnedSlice::from_vec(rs)))
+                    Ok(subst::NonerasedRegions(rs))
                 }
             }
         }
@@ -186,9 +188,9 @@ pub trait Combine {
                                                   item_def_id,
                                                   &as_.regions,
                                                   &bs.regions));
-        Ok(substs { regions: regions,
-                    self_ty: self_ty,
-                    tps: tps.clone() })
+        Ok(subst::Substs { regions: regions,
+                           self_ty: self_ty,
+                           tps: tps.clone() })
     }
 
     fn bare_fn_tys(&self, a: &ty::BareFnTy,
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index 5853de00574..6464b191b76 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -60,6 +60,7 @@ time of error detection.
 */
 
 use std::collections::HashSet;
+use middle::def;
 use middle::ty;
 use middle::ty::{Region, ReFree};
 use middle::typeck::infer;
@@ -1045,7 +1046,7 @@ impl<'a> Rebuilder<'a> {
                         Some(&d) => d
                     };
                     match a_def {
-                        ast::DefTy(did) | ast::DefStruct(did) => {
+                        def::DefTy(did) | def::DefStruct(did) => {
                             let ty::ty_param_bounds_and_ty {
                                 generics: generics,
                                 ty: _
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index 9462094e1a6..646dad879ee 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -41,7 +41,6 @@ use std::rc::Rc;
 use syntax::ast;
 use syntax::codemap;
 use syntax::codemap::Span;
-use syntax::owned_slice::OwnedSlice;
 use util::common::indent;
 use util::ppaux::{bound_region_to_str, ty_to_str, trait_ref_to_str, Repr};
 
@@ -625,7 +624,7 @@ impl<'a> InferCtxt<'a> {
     pub fn region_vars_for_defs(&self,
                                 span: Span,
                                 defs: &[ty::RegionParameterDef])
-                                -> OwnedSlice<ty::Region> {
+                                -> Vec<ty::Region> {
         defs.iter()
             .map(|d| self.next_region_var(EarlyBoundRegion(span, d.name)))
             .collect()
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index b3cabbfb7e2..9bf6728c95b 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -63,7 +63,9 @@ independently:
 
 use driver::config;
 
+use middle::def;
 use middle::resolve;
+use middle::subst;
 use middle::ty;
 use util::common::time;
 use util::ppaux::Repr;
@@ -144,7 +146,7 @@ pub struct MethodObject {
 pub struct MethodCallee {
     pub origin: MethodOrigin,
     pub ty: ty::t,
-    pub substs: ty::substs
+    pub substs: subst::Substs
 }
 
 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
@@ -184,7 +186,7 @@ pub enum vtable_origin {
       from whence comes the vtable, and tys are the type substs.
       vtable_res is the vtable itself
      */
-    vtable_static(ast::DefId, ty::substs, vtable_res),
+    vtable_static(ast::DefId, subst::Substs, vtable_res),
 
     /*
       Dynamic vtable, comes from a parameter that has a bound on it:
@@ -265,7 +267,7 @@ pub fn write_substs_to_tcx(tcx: &ty::ctxt,
         tcx.item_substs.borrow_mut().insert(node_id, item_substs);
     }
 }
-pub fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
+pub fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> def::Def {
     match tcx.def_map.borrow().find(&id) {
         Some(&x) => x,
         _ => {
@@ -275,7 +277,7 @@ pub fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
 }
 
 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
-                   -> ast::Def {
+                   -> def::Def {
     lookup_def_tcx(ccx.tcx, sp, id)
 }
 
diff --git a/src/librustc/middle/typeck/variance.rs b/src/librustc/middle/typeck/variance.rs
index 8ee6aef3386..04244ff31a8 100644
--- a/src/librustc/middle/typeck/variance.rs
+++ b/src/librustc/middle/typeck/variance.rs
@@ -195,6 +195,7 @@ represents the "variance transform" as defined in the paper:
 use std::collections::HashMap;
 use arena;
 use arena::Arena;
+use middle::subst;
 use middle::ty;
 use std::fmt;
 use std::rc::Rc;
@@ -798,7 +799,7 @@ impl<'a> ConstraintContext<'a> {
     fn add_constraints_from_substs(&mut self,
                                    def_id: ast::DefId,
                                    generics: &ty::Generics,
-                                   substs: &ty::substs,
+                                   substs: &subst::Substs,
                                    variance: VarianceTermPtr<'a>) {
         debug!("add_constraints_from_substs(def_id={:?})", def_id);
 
@@ -810,8 +811,8 @@ impl<'a> ConstraintContext<'a> {
         }
 
         match substs.regions {
-            ty::ErasedRegions => {}
-            ty::NonerasedRegions(ref rps) => {
+            subst::ErasedRegions => {}
+            subst::NonerasedRegions(ref rps) => {
                 for (i, p) in generics.region_param_defs().iter().enumerate() {
                     let variance_decl =
                         self.declared_variance(p.def_id, def_id, RegionParam, i);
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index e14fd89fc74..a9ac1e76f11 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -9,6 +9,8 @@
 // except according to those terms.
 
 
+use middle::subst;
+use middle::subst::Subst;
 use middle::ty::{ReSkolemized, ReVar};
 use middle::ty::{BoundRegion, BrAnon, BrNamed};
 use middle::ty::{BrFresh, ctxt};
@@ -419,15 +421,15 @@ pub fn ty_to_str(cx: &ctxt, typ: t) -> String {
 
 pub fn parameterized(cx: &ctxt,
                      base: &str,
-                     regions: &ty::RegionSubsts,
+                     regions: &subst::RegionSubsts,
                      tps: &[ty::t],
                      did: ast::DefId,
                      is_trait: bool)
                      -> String {
     let mut strs = Vec::new();
     match *regions {
-        ty::ErasedRegions => { }
-        ty::NonerasedRegions(ref regions) => {
+        subst::ErasedRegions => { }
+        subst::NonerasedRegions(ref regions) => {
             for &r in regions.iter() {
                 strs.push(region_to_str(cx, "", false, r))
             }
@@ -443,7 +445,7 @@ pub fn parameterized(cx: &ctxt,
     let has_defaults = ty_params.last().map_or(false, |def| def.default.is_some());
     let num_defaults = if has_defaults {
         // We should have a borrowed version of substs instead of cloning.
-        let mut substs = ty::substs {
+        let mut substs = subst::Substs {
             tps: Vec::from_slice(tps),
             regions: regions.clone(),
             self_ty: None
@@ -451,7 +453,7 @@ pub fn parameterized(cx: &ctxt,
         ty_params.iter().zip(tps.iter()).rev().take_while(|&(def, &actual)| {
             substs.tps.pop();
             match def.default {
-                Some(default) => ty::subst(cx, &substs, default) == actual,
+                Some(default) => default.subst(cx, &substs) == actual,
                 None => false
             }
         }).len()
@@ -565,7 +567,7 @@ impl Repr for ty::t {
     }
 }
 
-impl Repr for ty::substs {
+impl Repr for subst::Substs {
     fn repr(&self, tcx: &ctxt) -> String {
         format!("substs(regions={}, self_ty={}, tps={})",
                 self.regions.repr(tcx),
@@ -580,11 +582,11 @@ impl Repr for ty::ItemSubsts {
     }
 }
 
-impl Repr for ty::RegionSubsts {
+impl Repr for subst::RegionSubsts {
     fn repr(&self, tcx: &ctxt) -> String {
         match *self {
-            ty::ErasedRegions => "erased".to_string(),
-            ty::NonerasedRegions(ref regions) => regions.repr(tcx)
+            subst::ErasedRegions => "erased".to_string(),
+            subst::NonerasedRegions(ref regions) => regions.repr(tcx)
         }
     }
 }
diff --git a/src/librustdoc/clean/inline.rs b/src/librustdoc/clean/inline.rs
index 9d8bfa8302c..9db9a0e7612 100644
--- a/src/librustdoc/clean/inline.rs
+++ b/src/librustdoc/clean/inline.rs
@@ -16,6 +16,7 @@ use syntax::attr::AttrMetaMethods;
 
 use rustc::metadata::csearch;
 use rustc::metadata::decoder;
+use rustc::middle::def;
 use rustc::middle::ty;
 
 use core;
@@ -46,22 +47,22 @@ pub fn try_inline(id: ast::NodeId) -> Option<Vec<clean::Item>> {
         Some(def) => *def,
         None => return None,
     };
-    let did = ast_util::def_id_of_def(def);
+    let did = def.def_id();
     if ast_util::is_local(did) { return None }
     try_inline_def(&**cx, tcx, def)
 }
 
 fn try_inline_def(cx: &core::DocContext,
                   tcx: &ty::ctxt,
-                  def: ast::Def) -> Option<Vec<clean::Item>> {
+                  def: def::Def) -> Option<Vec<clean::Item>> {
     let mut ret = Vec::new();
-    let did = ast_util::def_id_of_def(def);
+    let did = def.def_id();
     let inner = match def {
-        ast::DefTrait(did) => {
+        def::DefTrait(did) => {
             record_extern_fqn(cx, did, clean::TypeTrait);
             clean::TraitItem(build_external_trait(tcx, did))
         }
-        ast::DefFn(did, style) => {
+        def::DefFn(did, style) => {
             // If this function is a tuple struct constructor, we just skip it
             if csearch::get_tuple_struct_definition_if_ctor(&tcx.sess.cstore,
                                                             did).is_some() {
@@ -70,20 +71,20 @@ fn try_inline_def(cx: &core::DocContext,
             record_extern_fqn(cx, did, clean::TypeFunction);
             clean::FunctionItem(build_external_function(tcx, did, style))
         }
-        ast::DefStruct(did) => {
+        def::DefStruct(did) => {
             record_extern_fqn(cx, did, clean::TypeStruct);
             ret.extend(build_impls(cx, tcx, did).move_iter());
             clean::StructItem(build_struct(tcx, did))
         }
-        ast::DefTy(did) => {
+        def::DefTy(did) => {
             record_extern_fqn(cx, did, clean::TypeEnum);
             ret.extend(build_impls(cx, tcx, did).move_iter());
             build_type(tcx, did)
         }
         // Assume that the enum type is reexported next to the variant, and
         // variants don't show up in documentation specially.
-        ast::DefVariant(..) => return Some(Vec::new()),
-        ast::DefMod(did) => {
+        def::DefVariant(..) => return Some(Vec::new()),
+        def::DefMod(did) => {
             record_extern_fqn(cx, did, clean::TypeModule);
             clean::ModuleItem(build_module(cx, tcx, did))
         }
@@ -248,7 +249,7 @@ fn build_impls(cx: &core::DocContext,
                           impls: &mut Vec<Option<clean::Item>>) {
             match def {
                 decoder::DlImpl(did) => impls.push(build_impl(cx, tcx, did)),
-                decoder::DlDef(ast::DefMod(did)) => {
+                decoder::DlDef(def::DefMod(did)) => {
                     csearch::each_child_of_item(&tcx.sess.cstore,
                                                 did,
                                                 |def, _, _| {
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 4614d7cee3a..3cb5c663c4e 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -25,6 +25,8 @@ use rustc::driver::driver;
 use rustc::metadata::cstore;
 use rustc::metadata::csearch;
 use rustc::metadata::decoder;
+use rustc::middle::def;
+use rustc::middle::subst;
 use rustc::middle::ty;
 
 use std::rc::Rc;
@@ -190,7 +192,7 @@ impl Clean<ExternalCrate> for cstore::crate_metadata {
                                                       self.cnum,
                                                       |def, _, _| {
                     let did = match def {
-                        decoder::DlDef(ast::DefMod(did)) => did,
+                        decoder::DlDef(def::DefMod(did)) => did,
                         _ => return
                     };
                     let attrs = inline::load_attrs(tcx, did);
@@ -486,14 +488,14 @@ impl Clean<TyParamBound> for ast::TyParamBound {
     }
 }
 
-fn external_path(name: &str, substs: &ty::substs) -> Path {
+fn external_path(name: &str, substs: &subst::Substs) -> Path {
     Path {
         global: false,
         segments: vec![PathSegment {
             name: name.to_string(),
             lifetimes: match substs.regions {
-                ty::ErasedRegions => Vec::new(),
-                ty::NonerasedRegions(ref v) => {
+                subst::ErasedRegions => Vec::new(),
+                subst::NonerasedRegions(ref v) => {
                     v.iter().filter_map(|v| v.clean()).collect()
                 }
             },
@@ -509,7 +511,7 @@ impl Clean<TyParamBound> for ty::BuiltinBound {
             core::Typed(ref tcx) => tcx,
             core::NotTyped(_) => return RegionBound,
         };
-        let empty = ty::substs::empty();
+        let empty = subst::Substs::empty();
         let (did, path) = match *self {
             ty::BoundStatic => return RegionBound,
             ty::BoundSend =>
@@ -574,12 +576,12 @@ impl Clean<Vec<TyParamBound>> for ty::ParamBounds {
     }
 }
 
-impl Clean<Option<Vec<TyParamBound>>> for ty::substs {
+impl Clean<Option<Vec<TyParamBound>>> for subst::Substs {
     fn clean(&self) -> Option<Vec<TyParamBound>> {
         let mut v = Vec::new();
         match self.regions {
-            ty::NonerasedRegions(..) => v.push(RegionBound),
-            ty::ErasedRegions => {}
+            subst::NonerasedRegions(..) => v.push(RegionBound),
+            subst::ErasedRegions => {}
         }
         v.extend(self.tps.iter().map(|t| TraitBound(t.clean())));
 
@@ -1948,8 +1950,8 @@ fn resolve_type(path: Path, tpbs: Option<Vec<TyParamBound>>,
     };
 
     match def {
-        ast::DefSelfTy(i) => return Self(ast_util::local_def(i)),
-        ast::DefPrimTy(p) => match p {
+        def::DefSelfTy(i) => return Self(ast_util::local_def(i)),
+        def::DefPrimTy(p) => match p {
             ast::TyStr => return Primitive(Str),
             ast::TyBool => return Primitive(Bool),
             ast::TyChar => return Primitive(Char),
@@ -1967,24 +1969,24 @@ fn resolve_type(path: Path, tpbs: Option<Vec<TyParamBound>>,
             ast::TyFloat(ast::TyF64) => return Primitive(F64),
             ast::TyFloat(ast::TyF128) => return Primitive(F128),
         },
-        ast::DefTyParam(i, _) => return Generic(i),
-        ast::DefTyParamBinder(i) => return TyParamBinder(i),
+        def::DefTyParam(i, _) => return Generic(i),
+        def::DefTyParamBinder(i) => return TyParamBinder(i),
         _ => {}
     };
     let did = register_def(&**cx, def);
     ResolvedPath { path: path, typarams: tpbs, did: did }
 }
 
-fn register_def(cx: &core::DocContext, def: ast::Def) -> ast::DefId {
+fn register_def(cx: &core::DocContext, def: def::Def) -> ast::DefId {
     let (did, kind) = match def {
-        ast::DefFn(i, _) => (i, TypeFunction),
-        ast::DefTy(i) => (i, TypeEnum),
-        ast::DefTrait(i) => (i, TypeTrait),
-        ast::DefStruct(i) => (i, TypeStruct),
-        ast::DefMod(i) => (i, TypeModule),
-        ast::DefStatic(i, _) => (i, TypeStatic),
-        ast::DefVariant(i, _, _) => (i, TypeEnum),
-        _ => return ast_util::def_id_of_def(def),
+        def::DefFn(i, _) => (i, TypeFunction),
+        def::DefTy(i) => (i, TypeEnum),
+        def::DefTrait(i) => (i, TypeTrait),
+        def::DefStruct(i) => (i, TypeStruct),
+        def::DefMod(i) => (i, TypeModule),
+        def::DefStatic(i, _) => (i, TypeStatic),
+        def::DefVariant(i, _, _) => (i, TypeEnum),
+        _ => return def.def_id()
     };
     if ast_util::is_local(did) { return did }
     let tcx = match cx.maybe_typed {
diff --git a/src/librustdoc/visit_ast.rs b/src/librustdoc/visit_ast.rs
index 9f1ad02decd..da9169d70fd 100644
--- a/src/librustdoc/visit_ast.rs
+++ b/src/librustdoc/visit_ast.rs
@@ -195,7 +195,7 @@ impl<'a> RustdocVisitor<'a> {
             core::Typed(ref tcx) => tcx,
             core::NotTyped(_) => return false
         };
-        let def = ast_util::def_id_of_def(*tcx.def_map.borrow().get(&id));
+        let def = tcx.def_map.borrow().get(&id).def_id();
         if !ast_util::is_local(def) { return false }
         let analysis = match self.analysis {
             Some(analysis) => analysis, None => return false
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 9cbe7e0b5fc..2bc24fd1eb3 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -206,49 +206,6 @@ impl Generics {
     }
 }
 
-#[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
-pub enum MethodProvenance {
-    FromTrait(DefId),
-    FromImpl(DefId),
-}
-
-#[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
-pub enum Def {
-    DefFn(DefId, FnStyle),
-    DefStaticMethod(/* method */ DefId, MethodProvenance, FnStyle),
-    DefSelfTy(/* trait id */ NodeId),
-    DefMod(DefId),
-    DefForeignMod(DefId),
-    DefStatic(DefId, bool /* is_mutbl */),
-    DefArg(NodeId, BindingMode),
-    DefLocal(NodeId, BindingMode),
-    DefVariant(DefId /* enum */, DefId /* variant */, bool /* is_structure */),
-    DefTy(DefId),
-    DefTrait(DefId),
-    DefPrimTy(PrimTy),
-    DefTyParam(DefId, uint),
-    DefBinding(NodeId, BindingMode),
-    DefUse(DefId),
-    DefUpvar(NodeId,  // id of closed over var
-              @Def,     // closed over def
-              NodeId,  // expr node that creates the closure
-              NodeId), // id for the block/body of the closure expr
-
-    /// Note that if it's a tuple struct's definition, the node id of the DefId
-    /// may either refer to the item definition's id or the StructDef.ctor_id.
-    ///
-    /// The cases that I have encountered so far are (this is not exhaustive):
-    /// - If it's a ty_path referring to some tuple struct, then DefMap maps
-    ///   it to a def whose id is the item definition's id.
-    /// - If it's an ExprPath referring to some tuple struct, then DefMap maps
-    ///   it to a def whose id is the StructDef.ctor_id.
-    DefStruct(DefId),
-    DefTyParamBinder(NodeId), /* struct, impl or trait with ty params */
-    DefRegion(NodeId),
-    DefLabel(NodeId),
-    DefMethod(DefId /* method */, Option<DefId> /* trait */),
-}
-
 #[deriving(Clone, PartialEq, Eq, Hash, Encodable, Decodable, Show)]
 pub enum DefRegion {
     DefStaticRegion,
diff --git a/src/libsyntax/ast_util.rs b/src/libsyntax/ast_util.rs
index e4f2f7f26cf..a1ad3cc14c5 100644
--- a/src/libsyntax/ast_util.rs
+++ b/src/libsyntax/ast_util.rs
@@ -52,33 +52,6 @@ pub fn stmt_id(s: &Stmt) -> NodeId {
     }
 }
 
-pub fn variant_def_ids(d: Def) -> Option<(DefId, DefId)> {
-    match d {
-      DefVariant(enum_id, var_id, _) => {
-          Some((enum_id, var_id))
-      }
-      _ => None
-    }
-}
-
-pub fn def_id_of_def(d: Def) -> DefId {
-    match d {
-        DefFn(id, _) | DefStaticMethod(id, _, _) | DefMod(id) |
-        DefForeignMod(id) | DefStatic(id, _) |
-        DefVariant(_, id, _) | DefTy(id) | DefTyParam(id, _) |
-        DefUse(id) | DefStruct(id) | DefTrait(id) | DefMethod(id, _) => {
-            id
-        }
-        DefArg(id, _) | DefLocal(id, _) | DefSelfTy(id)
-        | DefUpvar(id, _, _, _) | DefBinding(id, _) | DefRegion(id)
-        | DefTyParamBinder(id) | DefLabel(id) => {
-            local_def(id)
-        }
-
-        DefPrimTy(_) => fail!()
-    }
-}
-
 pub fn binop_to_str(op: BinOp) -> &'static str {
     match op {
         BiAdd => "+",
diff --git a/src/test/compile-fail/issue-12796.rs b/src/test/compile-fail/issue-12796.rs
index 8b5fb90e2d4..ce3c8c52b0e 100644
--- a/src/test/compile-fail/issue-12796.rs
+++ b/src/test/compile-fail/issue-12796.rs
@@ -8,11 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: missing `Self` type param in the substitution of `fn(Self)`
-
 trait Trait {
     fn outer(self) {
         fn inner(_: Self) {
+            //~^ ERROR can't use type parameters from outer function
+            //~^^ ERROR use of undeclared type name `Self`
         }
     }
 }
diff --git a/src/test/compile-fail/issue-5997-enum.rs b/src/test/compile-fail/issue-5997-enum.rs
index 7be01b4abb4..39e1e117cd0 100644
--- a/src/test/compile-fail/issue-5997-enum.rs
+++ b/src/test/compile-fail/issue-5997-enum.rs
@@ -10,8 +10,8 @@
 
 fn f<Z>() -> bool {
     enum E { V(Z) }
-    //~^ ERROR can't use type parameters from outer function in the
-
+    //~^ ERROR can't use type parameters from outer function
+    //~^^ ERROR use of undeclared type name `Z`
     true
 }
 
diff --git a/src/test/compile-fail/resolve-type-param-in-item-in-trait.rs b/src/test/compile-fail/resolve-type-param-in-item-in-trait.rs
new file mode 100644
index 00000000000..341fe173a03
--- /dev/null
+++ b/src/test/compile-fail/resolve-type-param-in-item-in-trait.rs
@@ -0,0 +1,49 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Issue #14603: Check for references to type parameters from the
+// outer scope (in this case, the trait) used on items in an inner
+// scope (in this case, the enum).
+
+trait TraitA<A> {
+    fn outer(self) {
+        enum Foo<B> {
+            Variance(A)
+                //~^ ERROR can't use type parameters from outer function
+                //~^^ ERROR use of undeclared type name `A`
+        }
+    }
+}
+
+trait TraitB<A> {
+    fn outer(self) {
+        struct Foo<B>(A);
+                //~^ ERROR can't use type parameters from outer function
+                //~^^ ERROR use of undeclared type name `A`
+    }
+}
+
+trait TraitC<A> {
+    fn outer(self) {
+        struct Foo<B> { a: A }
+                //~^ ERROR can't use type parameters from outer function
+                //~^^ ERROR use of undeclared type name `A`
+    }
+}
+
+trait TraitD<A> {
+    fn outer(self) {
+        fn foo<B>(a: A) { }
+                //~^ ERROR can't use type parameters from outer function
+                //~^^ ERROR use of undeclared type name `A`
+    }
+}
+
+fn main() { }
diff --git a/src/test/run-pass/trait-contravariant-self.rs b/src/test/run-pass/trait-contravariant-self.rs
new file mode 100644
index 00000000000..1576c646286
--- /dev/null
+++ b/src/test/run-pass/trait-contravariant-self.rs
@@ -0,0 +1,37 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// This is an interesting test case. We have a trait (Bar) that is
+// implemented for a `Box<Foo>` object (note: no bounds). And then we
+// have a `Box<Foo:Send>` object. The impl for `Box<Foo>` is applicable
+// to `Box<Foo:Send>` because:
+//
+// 1. The trait Bar is contravariant w/r/t Self because `Self` appears
+//    only in argument position.
+// 2. The impl provides `Bar for Box<Foo>`
+// 3. The fn `wants_bar()` requires `Bar for Box<Foo:Send>`.
+// 4. `Bar for Box<Foo> <: Bar for Box<Foo:Send>` because
+//    `Box<Foo:Send> <: Box<Foo>`.
+
+trait Foo { }
+struct SFoo;
+impl Foo for SFoo { }
+
+trait Bar { fn dummy(&self); }
+impl Bar for Box<Foo> { fn dummy(&self) { } }
+
+fn wants_bar<B:Bar>(b: &B) { }
+
+fn main() {
+    let x: Box<Foo:Send> = (box SFoo);
+    wants_bar(&x);
+}
+
+