Refactor so that references to traits are not represented using a type with a

bare function store (which is not in fact a kind of value) but rather
ty::TraitRef.  Removes many uses of fail!() and other telltale signs of
type-semantic mismatch.

cc #4183 (not a fix, but related)

46 files changed, 1071 insertions, 862 deletions

diff --git a/src/libcore/option.rs b/src/libcore/option.rs
index cd34d7ab0c0..de1482e2c39 100644
--- a/src/libcore/option.rs
+++ b/src/libcore/option.rs
@@ -46,7 +46,8 @@ use ops::Add;
 use kinds::Copy;
 use util;
 use num::Zero;
-use iter::{BaseIter, MutableIter};
+use iter::{BaseIter, MutableIter, ExtendedIter};
+use iter;
 
 #[cfg(test)] use ptr;
 #[cfg(test)] use str;
@@ -118,6 +119,31 @@ impl<T> MutableIter<T> for Option<T> {
     }
 }
 
+impl<A> ExtendedIter<A> for Option<A> {
+    pub fn eachi(&self, blk: &fn(uint, v: &A) -> bool) {
+        iter::eachi(self, blk)
+    }
+    pub fn all(&self, blk: &fn(&A) -> bool) -> bool {
+        iter::all(self, blk)
+    }
+    pub fn any(&self, blk: &fn(&A) -> bool) -> bool {
+        iter::any(self, blk)
+    }
+    pub fn foldl<B>(&self, b0: B, blk: &fn(&B, &A) -> B) -> B {
+        iter::foldl(self, b0, blk)
+    }
+    pub fn position(&self, f: &fn(&A) -> bool) -> Option<uint> {
+        iter::position(self, f)
+    }
+    fn map_to_vec<B>(&self, op: &fn(&A) -> B) -> ~[B] {
+        iter::map_to_vec(self, op)
+    }
+    fn flat_map_to_vec<B,IB:BaseIter<B>>(&self, op: &fn(&A) -> IB)
+        -> ~[B] {
+        iter::flat_map_to_vec(self, op)
+    }
+}
+
 pub impl<T> Option<T> {
     /// Returns true if the option equals `none`
     fn is_none(&const self) -> bool {
diff --git a/src/libcore/reflect.rs b/src/libcore/reflect.rs
index 3e11febc5bf..a449c4e73cf 100644
--- a/src/libcore/reflect.rs
+++ b/src/libcore/reflect.rs
@@ -443,9 +443,9 @@ impl<V:TyVisitor + MovePtr> TyVisitor for MovePtrAdaptor<V> {
     }
 
     fn visit_trait(&self) -> bool {
-        self.align_to::<TyVisitor>();
+        self.align_to::<@TyVisitor>();
         if ! self.inner.visit_trait() { return false; }
-        self.bump_past::<TyVisitor>();
+        self.bump_past::<@TyVisitor>();
         true
     }
 
diff --git a/src/libcore/run.rs b/src/libcore/run.rs
index 8116ea952e4..98564beeba9 100644
--- a/src/libcore/run.rs
+++ b/src/libcore/run.rs
@@ -298,7 +298,7 @@ pub fn start_program(prog: &str, args: &[~str]) -> @Program {
     @ProgRes(repr) as @Program
 }
 
-fn read_all(rd: io::Reader) -> ~str {
+fn read_all(rd: @io::Reader) -> ~str {
     let buf = io::with_bytes_writer(|wr| {
         let mut bytes = [0, ..4096];
         while !rd.eof() {
diff --git a/src/librustc/metadata/common.rs b/src/librustc/metadata/common.rs
index 5df7b037334..71a1f1b3f9b 100644
--- a/src/librustc/metadata/common.rs
+++ b/src/librustc/metadata/common.rs
@@ -74,7 +74,9 @@ pub static tag_crate_dep_vers: uint = 0x2cu;
 pub static tag_mod_impl: uint = 0x30u;
 
 pub static tag_item_trait_method: uint = 0x31u;
-pub static tag_impl_trait: uint = 0x32u;
+
+pub static tag_item_trait_ref: uint = 0x32u;
+pub static tag_item_super_trait_ref: uint = 0x33u;
 
 // discriminator value for variants
 pub static tag_disr_val: uint = 0x34u;
diff --git a/src/librustc/metadata/csearch.rs b/src/librustc/metadata/csearch.rs
index 8e7ecdec638..74e891a0194 100644
--- a/src/librustc/metadata/csearch.rs
+++ b/src/librustc/metadata/csearch.rs
@@ -139,7 +139,7 @@ pub fn get_provided_trait_methods(tcx: ty::ctxt,
     decoder::get_provided_trait_methods(cstore.intr, cdata, def.node, tcx)
 }
 
-pub fn get_supertraits(tcx: ty::ctxt, def: ast::def_id) -> ~[ty::t] {
+pub fn get_supertraits(tcx: ty::ctxt, def: ast::def_id) -> ~[@ty::TraitRef] {
     let cstore = tcx.cstore;
     let cdata = cstore::get_crate_data(cstore, def.crate);
     decoder::get_supertraits(cdata, def.node, tcx)
@@ -180,6 +180,12 @@ pub fn get_type(tcx: ty::ctxt,
     decoder::get_type(cdata, def.node, tcx)
 }
 
+pub fn get_trait_def(tcx: ty::ctxt, def: ast::def_id) -> ty::TraitDef {
+    let cstore = tcx.cstore;
+    let cdata = cstore::get_crate_data(cstore, def.crate);
+    decoder::get_trait_def(cdata, def.node, tcx)
+}
+
 pub fn get_region_param(cstore: @mut metadata::cstore::CStore,
                         def: ast::def_id) -> Option<ty::region_variance> {
     let cdata = cstore::get_crate_data(cstore, def.crate);
@@ -204,8 +210,8 @@ pub fn get_field_type(tcx: ty::ctxt, class_id: ast::def_id,
     debug!("got field data %?", the_field);
     let ty = decoder::item_type(def, the_field, tcx, cdata);
     ty::ty_param_bounds_and_ty {
-        bounds: @~[],
-        region_param: None,
+        generics: ty::Generics {bounds: @~[],
+                                region_param: None},
         ty: ty
     }
 }
@@ -213,7 +219,8 @@ pub fn get_field_type(tcx: ty::ctxt, class_id: ast::def_id,
 // Given a def_id for an impl or class, return the traits it implements,
 // or the empty vector if it's not for an impl or for a class that implements
 // traits
-pub fn get_impl_traits(tcx: ty::ctxt, def: ast::def_id) -> ~[ty::t] {
+pub fn get_impl_traits(tcx: ty::ctxt,
+                       def: ast::def_id) -> ~[@ty::TraitRef] {
     let cstore = tcx.cstore;
     let cdata = cstore::get_crate_data(cstore, def.crate);
     decoder::get_impl_traits(cdata, def.node, tcx)
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 32a912d0101..d9ef30ff297 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -20,7 +20,7 @@ use metadata::csearch;
 use metadata::cstore;
 use metadata::decoder;
 use metadata::tydecode::{parse_ty_data, parse_def_id, parse_bounds_data,
-                         parse_bare_fn_ty_data};
+                         parse_bare_fn_ty_data, parse_trait_ref_data};
 use middle::{ty, resolve};
 
 use core::hash::HashUtil;
@@ -256,12 +256,14 @@ pub fn item_type(item_id: ast::def_id, item: ebml::Doc,
     }
 }
 
-fn item_impl_traits(item: ebml::Doc, tcx: ty::ctxt, cdata: cmd) -> ~[ty::t] {
-    let mut results = ~[];
-    for reader::tagged_docs(item, tag_impl_trait) |ity| {
-        results.push(doc_type(ity, tcx, cdata));
-    };
-    results
+fn doc_trait_ref(doc: ebml::Doc, tcx: ty::ctxt, cdata: cmd) -> ty::TraitRef {
+    parse_trait_ref_data(doc.data, cdata.cnum, doc.start, tcx,
+                         |_, did| translate_def_id(cdata, did))
+}
+
+fn item_trait_ref(doc: ebml::Doc, tcx: ty::ctxt, cdata: cmd) -> ty::TraitRef {
+    let tp = reader::get_doc(doc, tag_item_trait_ref);
+    doc_trait_ref(tp, tcx, cdata)
 }
 
 fn item_ty_param_bounds(item: ebml::Doc, tcx: ty::ctxt, cdata: cmd,
@@ -371,6 +373,21 @@ pub fn lookup_def(cnum: ast::crate_num, data: @~[u8], did_: ast::def_id) ->
     return def_like_to_def(item_to_def_like(item, did, cnum));
 }
 
+pub fn get_trait_def(cdata: cmd,
+                     item_id: ast::node_id,
+                     tcx: ty::ctxt) -> ty::TraitDef
+{
+    let item_doc = lookup_item(item_id, cdata.data);
+    let tp_bounds = item_ty_param_bounds(item_doc, tcx, cdata,
+                                         tag_items_data_item_ty_param_bounds);
+    let rp = item_ty_region_param(item_doc);
+    ty::TraitDef {
+        generics: ty::Generics {bounds: tp_bounds,
+                                region_param: rp},
+        trait_ref: @item_trait_ref(item_doc, tcx, cdata)
+    }
+}
+
 pub fn get_type(cdata: cmd, id: ast::node_id, tcx: ty::ctxt)
     -> ty::ty_param_bounds_and_ty {
 
@@ -382,8 +399,8 @@ pub fn get_type(cdata: cmd, id: ast::node_id, tcx: ty::ctxt)
     } else { @~[] };
     let rp = item_ty_region_param(item);
     ty::ty_param_bounds_and_ty {
-        bounds: tp_bounds,
-        region_param: rp,
+        generics: ty::Generics {bounds: tp_bounds,
+                                region_param: rp},
         ty: t
     }
 }
@@ -399,9 +416,19 @@ pub fn get_type_param_count(data: @~[u8], id: ast::node_id) -> uint {
     item_ty_param_count(lookup_item(id, data))
 }
 
-pub fn get_impl_traits(cdata: cmd, id: ast::node_id, tcx: ty::ctxt)
-                    -> ~[ty::t] {
-    item_impl_traits(lookup_item(id, cdata.data), tcx, cdata)
+pub fn get_impl_traits(cdata: cmd,
+                       id: ast::node_id,
+                       tcx: ty::ctxt) -> ~[@ty::TraitRef]
+{
+    let item_doc = lookup_item(id, cdata.data);
+    let mut results = ~[];
+    for reader::tagged_docs(item_doc, tag_item_trait_ref) |tp| {
+        let trait_ref =
+            @parse_trait_ref_data(tp.data, cdata.cnum, tp.start, tcx,
+                                  |_, did| translate_def_id(cdata, did));
+        results.push(trait_ref);
+    };
+    results
 }
 
 pub fn get_impl_method(intr: @ident_interner, cdata: cmd, id: ast::node_id,
@@ -735,7 +762,10 @@ pub fn get_method(intr: @ident_interner, cdata: cmd, id: ast::node_id,
     let self_ty = get_self_ty(method_doc);
     ty::method {
         ident: name,
-        tps: bounds,
+        generics: ty::Generics {
+            bounds: bounds,
+            region_param: None
+        },
         transformed_self_ty: transformed_self_ty,
         fty: fty,
         self_ty: self_ty,
@@ -784,7 +814,10 @@ pub fn get_provided_trait_methods(intr: @ident_interner, cdata: cmd,
         let self_ty = get_self_ty(mth);
         let ty_method = ty::method {
             ident: name,
-            tps: bounds,
+            generics: ty::Generics {
+                bounds: bounds,
+                region_param: None
+            },
             transformed_self_ty: transformed_self_ty,
             fty: fty,
             self_ty: self_ty,
@@ -804,11 +837,11 @@ pub fn get_provided_trait_methods(intr: @ident_interner, cdata: cmd,
 
 /// Returns the supertraits of the given trait.
 pub fn get_supertraits(cdata: cmd, id: ast::node_id, tcx: ty::ctxt)
-                    -> ~[ty::t] {
+                    -> ~[@ty::TraitRef] {
     let mut results = ~[];
     let item_doc = lookup_item(id, cdata.data);
-    for reader::tagged_docs(item_doc, tag_impl_trait) |trait_doc| {
-        results.push(doc_type(trait_doc, tcx, cdata));
+    for reader::tagged_docs(item_doc, tag_item_super_trait_ref) |trait_doc| {
+        results.push(@doc_trait_ref(trait_doc, tcx, cdata));
     }
     return results;
 }
@@ -837,8 +870,8 @@ pub fn get_static_methods_if_impl(intr: @ident_interner,
         return None;
     }
 
-    // If this impl has a trait ref, don't consider it.
-    for reader::tagged_docs(item, tag_impl_trait) |_doc| {
+    // If this impl implements a trait, don't consider it.
+    for reader::tagged_docs(item, tag_item_trait_ref) |_doc| {
         return None;
     }
 
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index e8fc4c44fea..e251af7c8a8 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -153,14 +153,23 @@ fn add_to_index(ecx: @EncodeContext, ebml_w: writer::Encoder, path: &[ident],
         });
 }
 
-fn encode_trait_ref(ebml_w: writer::Encoder, ecx: @EncodeContext,
-                    t: @trait_ref) {
-    ebml_w.start_tag(tag_impl_trait);
-    encode_type(ecx, ebml_w, node_id_to_type(ecx.tcx, t.ref_id));
+fn encode_trait_ref(ebml_w: writer::Encoder,
+                    ecx: @EncodeContext,
+                    trait_ref: &ty::TraitRef,
+                    tag: uint)
+{
+    let ty_str_ctxt = @tyencode::ctxt {
+        diag: ecx.diag,
+        ds: def_to_str,
+        tcx: ecx.tcx,
+        reachable: |a| reachable(ecx, a),
+        abbrevs: tyencode::ac_use_abbrevs(ecx.type_abbrevs)};
+
+    ebml_w.start_tag(tag);
+    tyencode::enc_trait_ref(ebml_w.writer, ty_str_ctxt, trait_ref);
     ebml_w.end_tag();
 }
 
-
 // Item info table encoding
 fn encode_family(ebml_w: writer::Encoder, c: char) {
     ebml_w.start_tag(tag_items_data_item_family);
@@ -579,7 +588,7 @@ fn encode_method_ty_fields(ecx: @EncodeContext,
 {
     encode_def_id(ebml_w, method_ty.def_id);
     encode_name(ecx, ebml_w, method_ty.ident);
-    encode_ty_type_param_bounds(ebml_w, ecx, method_ty.tps,
+    encode_ty_type_param_bounds(ebml_w, ecx, method_ty.generics.bounds,
                                 tag_item_method_tps);
     encode_transformed_self_ty(ecx, ebml_w, method_ty.transformed_self_ty);
     encode_method_fty(ecx, ebml_w, &method_ty.fty);
@@ -872,8 +881,9 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
             ebml_w.writer.write(str::to_bytes(def_to_str(method_def_id)));
             ebml_w.end_tag();
         }
-        for opt_trait.each |associated_trait| {
-           encode_trait_ref(ebml_w, ecx, *associated_trait);
+        for opt_trait.each |ast_trait_ref| {
+            let trait_ref = ty::node_id_to_trait_ref(ecx.tcx, ast_trait_ref.ref_id);
+            encode_trait_ref(ebml_w, ecx, trait_ref, tag_item_trait_ref);
         }
         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
         ebml_w.end_tag();
@@ -894,14 +904,15 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
                                    &m.generics);
         }
       }
-      item_trait(ref generics, ref traits, ref ms) => {
+      item_trait(ref generics, ref super_traits, ref ms) => {
         add_to_index();
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, local_def(item.id));
         encode_family(ebml_w, 'I');
         encode_region_param(ecx, ebml_w, item);
         encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
-        encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
+        let trait_def = ty::lookup_trait_def(tcx, local_def(item.id));
+        encode_trait_ref(ebml_w, ecx, trait_def.trait_ref, tag_item_trait_ref);
         encode_name(ecx, ebml_w, item.ident);
         encode_attributes(ebml_w, item.attrs);
         for ty::trait_method_def_ids(tcx, local_def(item.id)).each |&method_def_id| {
@@ -910,8 +921,9 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
             ebml_w.end_tag();
         }
         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
-        for traits.each |associated_trait| {
-            encode_trait_ref(ebml_w, ecx, *associated_trait);
+        for super_traits.each |ast_trait_ref| {
+            let trait_ref = ty::node_id_to_trait_ref(ecx.tcx, ast_trait_ref.ref_id);
+            encode_trait_ref(ebml_w, ecx, trait_ref, tag_item_super_trait_ref);
         }
         ebml_w.end_tag();
 
@@ -940,7 +952,7 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
                                       method_ty.fty.purity));
 
                     let tpt = ty::lookup_item_type(tcx, method_def_id);
-                    encode_ty_type_param_bounds(ebml_w, ecx, tpt.bounds,
+                    encode_ty_type_param_bounds(ebml_w, ecx, tpt.generics.bounds,
                                                 tag_items_data_item_ty_param_bounds);
                     encode_type(ecx, ebml_w, tpt.ty);
                 }
diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index 2982ed26877..2ec13abb483 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -125,6 +125,12 @@ pub fn parse_bare_fn_ty_data(data: @~[u8], crate_num: int, pos: uint, tcx: ty::c
     parse_bare_fn_ty(st, conv)
 }
 
+pub fn parse_trait_ref_data(data: @~[u8], crate_num: int, pos: uint, tcx: ty::ctxt,
+                            conv: conv_did) -> ty::TraitRef {
+    let st = parse_state_from_data(data, crate_num, pos, tcx);
+    parse_trait_ref(st, conv)
+}
+
 pub fn parse_arg_data(data: @~[u8], crate_num: int, pos: uint, tcx: ty::ctxt,
                       conv: conv_did) -> ty::arg {
     let st = parse_state_from_data(data, crate_num, pos, tcx);
@@ -183,7 +189,6 @@ fn parse_trait_store(st: @mut PState) -> ty::TraitStore {
         '~' => ty::UniqTraitStore,
         '@' => ty::BoxTraitStore,
         '&' => ty::RegionTraitStore(parse_region(st)),
-        '.' => ty::BareTraitStore,
         c => st.tcx.sess.bug(fmt!("parse_trait_store(): bad input '%c'", c))
     }
 }
@@ -265,6 +270,12 @@ fn parse_str(st: @mut PState, term: char) -> ~str {
     return result;
 }
 
+fn parse_trait_ref(st: @mut PState, conv: conv_did) -> ty::TraitRef {
+    let def = parse_def(st, NominalType, conv);
+    let substs = parse_substs(st, conv);
+    ty::TraitRef {def_id: def, substs: substs}
+}
+
 fn parse_ty(st: @mut PState, conv: conv_did) -> ty::t {
     match next(st) {
       'n' => return ty::mk_nil(st.tcx),
@@ -551,7 +562,7 @@ fn parse_bounds(st: @mut PState, conv: conv_did) -> @~[ty::param_bound] {
           'C' => ty::bound_copy,
           'K' => ty::bound_const,
           'O' => ty::bound_durable,
-          'I' => ty::bound_trait(parse_ty(st, conv)),
+          'I' => ty::bound_trait(@parse_trait_ref(st, conv)),
           '.' => break,
           _ => fail!(~"parse_bounds: bad bounds")
         });
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index 419219d411d..ca2d66de9c4 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -214,11 +214,16 @@ pub fn enc_vstore(w: @io::Writer, cx: @ctxt, v: ty::vstore) {
     }
 }
 
+pub fn enc_trait_ref(w: @io::Writer, cx: @ctxt, s: &ty::TraitRef) {
+    w.write_str((cx.ds)(s.def_id));
+    w.write_char('|');
+    enc_substs(w, cx, s.substs);
+}
+
 pub fn enc_trait_store(w: @io::Writer, cx: @ctxt, s: ty::TraitStore) {
     match s {
         ty::UniqTraitStore => w.write_char('~'),
         ty::BoxTraitStore => w.write_char('@'),
-        ty::BareTraitStore => w.write_char('.'),
         ty::RegionTraitStore(re) => {
             w.write_char('&');
             enc_region(w, cx, re);
@@ -415,8 +420,8 @@ pub fn enc_bounds(w: @io::Writer, cx: @ctxt, bs: @~[ty::param_bound]) {
           ty::bound_const => w.write_char('K'),
           ty::bound_durable => w.write_char('O'),
           ty::bound_trait(tp) => {
-            w.write_char('I');
-            enc_ty(w, cx, tp);
+              w.write_char('I');
+              enc_trait_ref(w, cx, tp);
           }
         }
     }
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index 6fc74c9a713..20b72a19df7 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -779,16 +779,20 @@ impl ebml_writer_helpers for writer::Encoder {
 
     fn emit_tpbt(&self, ecx: @e::EncodeContext,
                  tpbt: ty::ty_param_bounds_and_ty) {
-        do self.emit_struct("ty_param_bounds_and_ty", 3) {
-            do self.emit_field(~"bounds", 0) {
-                do self.emit_from_vec(*tpbt.bounds) |bs| {
-                    self.emit_bounds(ecx, *bs);
+        do self.emit_struct("ty_param_bounds_and_ty", 2) {
+            do self.emit_field(~"generics", 0) {
+                do self.emit_struct("Generics", 2) {
+                    do self.emit_field(~"bounds", 0) {
+                        do self.emit_from_vec(*tpbt.generics.bounds) |bs| {
+                            self.emit_bounds(ecx, *bs);
+                        }
+                    }
+                    do self.emit_field(~"region_param", 1) {
+                        tpbt.generics.region_param.encode(self);
+                    }
                 }
             }
-            do self.emit_field(~"region_param", 1u) {
-                tpbt.region_param.encode(self);
-            }
-            do self.emit_field(~"ty", 2u) {
+            do self.emit_field(~"ty", 1) {
                 self.emit_ty(ecx, tpbt.ty);
             }
         }
@@ -1046,15 +1050,19 @@ impl ebml_decoder_decoder_helpers for reader::Decoder {
     fn read_ty_param_bounds_and_ty(&self, xcx: @ExtendedDecodeContext)
         -> ty::ty_param_bounds_and_ty
     {
-        do self.read_struct("ty_param_bounds_and_ty", 3) {
+        do self.read_struct("ty_param_bounds_and_ty", 2) {
             ty::ty_param_bounds_and_ty {
-                bounds: self.read_field(~"bounds", 0u, || {
-                    @self.read_to_vec(|| self.read_bounds(xcx) )
-                }),
-                region_param: self.read_field(~"region_param", 1u, || {
-                    Decodable::decode(self)
-                }),
-                ty: self.read_field(~"ty", 2u, || {
+                generics: do self.read_struct("Generics", 2) {
+                    ty::Generics {
+                        bounds: self.read_field(~"bounds", 0, || {
+                            @self.read_to_vec(|| self.read_bounds(xcx) )
+                        }),
+                        region_param: self.read_field(~"region_param", 1, || {
+                            Decodable::decode(self)
+                        })
+                    }
+                },
+                ty: self.read_field(~"ty", 1, || {
                     self.read_ty(xcx)
                 })
             }
diff --git a/src/librustc/middle/kind.rs b/src/librustc/middle/kind.rs
index a25e2f49e09..96e8ef40770 100644
--- a/src/librustc/middle/kind.rs
+++ b/src/librustc/middle/kind.rs
@@ -91,7 +91,7 @@ fn check_struct_safe_for_destructor(cx: Context,
                                     span: span,
                                     struct_did: def_id) {
     let struct_tpt = ty::lookup_item_type(cx.tcx, struct_did);
-    if struct_tpt.bounds.len() == 0 {
+    if struct_tpt.generics.bounds.len() == 0 {
         let struct_ty = ty::mk_struct(cx.tcx, struct_did, ty::substs {
             self_r: None,
             self_ty: None,
@@ -279,7 +279,7 @@ pub fn check_expr(e: @expr, cx: Context, v: visit::vt<Context>) {
         let bounds = match e.node {
           expr_path(_) => {
             let did = ast_util::def_id_of_def(*cx.tcx.def_map.get(&e.id));
-            ty::lookup_item_type(cx.tcx, did).bounds
+            ty::lookup_item_type(cx.tcx, did).generics.bounds
           }
           _ => {
             // Type substitutions should only occur on paths and
@@ -340,7 +340,7 @@ fn check_ty(aty: @Ty, cx: Context, v: visit::vt<Context>) {
             // FIXME(#5562): removing this copy causes a segfault before stage2
             let ts = /*bad*/ copy **ts;
             let did = ast_util::def_id_of_def(*cx.tcx.def_map.get(&id));
-            let bounds = ty::lookup_item_type(cx.tcx, did).bounds;
+            let bounds = ty::lookup_item_type(cx.tcx, did).generics.bounds;
             for vec::each2(ts, *bounds) |ty, bound| {
                 check_bounds(cx, aty.id, aty.span, *ty, *bound)
             }
diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs
index a21cc26bd91..b4aff91ed5b 100644
--- a/src/librustc/middle/lint.rs
+++ b/src/librustc/middle/lint.rs
@@ -825,8 +825,7 @@ fn check_item_heap(cx: ty::ctxt, it: @ast::item) {
       ast::item_fn(*) |
       ast::item_ty(*) |
       ast::item_enum(*) |
-      ast::item_struct(*) |
-      ast::item_trait(*) => check_type(cx, it.id, it.id, it.span,
+      ast::item_struct(*) => check_type(cx, it.id, it.id, it.span,
                                        ty::node_id_to_type(cx, it.id)),
       _ => ()
     }
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index 7232e99bf22..fcf0b7022a7 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -79,6 +79,7 @@ use syntax::opt_vec::OptVec;
 use core::option::Some;
 use core::str::each_split_str;
 use core::hashmap::{HashMap, HashSet};
+use core::util;
 
 // Definition mapping
 pub type DefMap = @mut HashMap<node_id,def>;
@@ -3414,7 +3415,6 @@ pub impl Resolver {
                       self_type,
                       ref methods) => {
                 self.resolve_implementation(item.id,
-                                            item.span,
                                             generics,
                                             implemented_traits,
                                             self_type,
@@ -3723,13 +3723,30 @@ pub impl Resolver {
         for type_parameters.each |type_parameter| {
             for type_parameter.bounds.each |&bound| {
                 match bound {
-                    TraitTyParamBound(ty) => self.resolve_type(ty, visitor),
+                    TraitTyParamBound(tref) => {
+                        self.resolve_trait_reference(tref, visitor)
+                    }
                     RegionTyParamBound => {}
                 }
             }
         }
     }
 
+    fn resolve_trait_reference(@mut self,
+                               trait_reference: &trait_ref,
+                               visitor: ResolveVisitor) {
+        match self.resolve_path(trait_reference.path, TypeNS, true, visitor) {
+            None => {
+                self.session.span_err(trait_reference.path.span,
+                                      ~"attempt to implement an \
+                                        unknown trait");
+            }
+            Some(def) => {
+                self.record_def(trait_reference.ref_id, def);
+            }
+        }
+    }
+
     fn resolve_struct(@mut self,
                       id: node_id,
                       generics: &Generics,
@@ -3797,7 +3814,6 @@ pub impl Resolver {
 
     fn resolve_implementation(@mut self,
                               id: node_id,
-                              span: span,
                               generics: &Generics,
                               opt_trait_reference: Option<@trait_ref>,
                               self_type: @Ty,
@@ -3816,25 +3832,16 @@ pub impl Resolver {
             let original_trait_refs;
             match opt_trait_reference {
                 Some(trait_reference) => {
-                    let mut new_trait_refs = ~[];
-                    match self.resolve_path(
-                        trait_reference.path, TypeNS, true, visitor) {
-                        None => {
-                            self.session.span_err(span,
-                                                  ~"attempt to implement an \
-                                                    unknown trait");
-                        }
-                        Some(def) => {
-                            self.record_def(trait_reference.ref_id, def);
+                    self.resolve_trait_reference(trait_reference, visitor);
 
-                            // Record the current trait reference.
-                            new_trait_refs.push(def_id_of_def(def));
-                        }
-                    }
                     // Record the current set of trait references.
-                    let mut old = Some(new_trait_refs);
-                    self.current_trait_refs <-> old;
-                    original_trait_refs = Some(old);
+                    let mut new_trait_refs = ~[];
+                    for self.def_map.find(&trait_reference.ref_id).each |&def| {
+                        new_trait_refs.push(def_id_of_def(*def));
+                    }
+                    original_trait_refs = Some(util::replace(
+                        &mut self.current_trait_refs,
+                        Some(new_trait_refs)));
                 }
                 None => {
                     original_trait_refs = None;
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index f0c17a6f80d..593d37c2ff8 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -1062,9 +1062,6 @@ pub fn T_opaque_trait(cx: @CrateContext, store: ty::TraitStore) -> TypeRef {
         ty::RegionTraitStore(_) => {
             T_struct(~[T_ptr(cx.tydesc_type), T_ptr(T_i8())])
         }
-        ty::BareTraitStore => {
-            cx.sess.bug(~"can't make T_opaque_trait with bare trait store")
-        }
     }
 }
 
diff --git a/src/librustc/middle/trans/glue.rs b/src/librustc/middle/trans/glue.rs
index 1b27d21e6f4..d8c8301a835 100644
--- a/src/librustc/middle/trans/glue.rs
+++ b/src/librustc/middle/trans/glue.rs
@@ -40,7 +40,6 @@ use core::libc::c_uint;
 use core::str;
 use std::time;
 use syntax::ast;
-use syntax::parse::token::special_idents;
 
 pub fn trans_free(cx: block, v: ValueRef) -> block {
     let _icx = cx.insn_ctxt("trans_free");
@@ -400,11 +399,9 @@ pub fn call_tydesc_glue(++cx: block, v: ValueRef, t: ty::t, field: uint)
 pub fn make_visit_glue(bcx: block, v: ValueRef, t: ty::t) {
     let _icx = bcx.insn_ctxt("make_visit_glue");
     let mut bcx = bcx;
-    let ty_visitor_name = special_idents::ty_visitor;
-    assert!(bcx.ccx().tcx.intrinsic_defs.contains_key(&ty_visitor_name));
-    let (trait_id, ty) = *bcx.ccx().tcx.intrinsic_defs.get(&ty_visitor_name);
-    let v = PointerCast(bcx, v, T_ptr(type_of::type_of(bcx.ccx(), ty)));
-    bcx = reflect::emit_calls_to_trait_visit_ty(bcx, t, v, trait_id);
+    let (visitor_trait, object_ty) = ty::visitor_object_ty(bcx.tcx());
+    let v = PointerCast(bcx, v, T_ptr(type_of::type_of(bcx.ccx(), object_ty)));
+    bcx = reflect::emit_calls_to_trait_visit_ty(bcx, t, v, visitor_trait.def_id);
     build_return(bcx);
 }
 
@@ -554,8 +551,7 @@ pub fn make_drop_glue(bcx: block, v0: ValueRef, t: ty::t) {
       ty::ty_closure(_) => {
         closure::make_closure_glue(bcx, v0, t, drop_ty)
       }
-      ty::ty_trait(_, _, ty::BoxTraitStore) |
-      ty::ty_trait(_, _, ty::BareTraitStore) => {
+      ty::ty_trait(_, _, ty::BoxTraitStore) => {
         let llbox = Load(bcx, GEPi(bcx, v0, [0u, 1u]));
         decr_refcnt_maybe_free(bcx, llbox, ty::mk_opaque_box(ccx.tcx))
       }
@@ -621,8 +617,7 @@ pub fn make_take_glue(bcx: block, v: ValueRef, t: ty::t) {
       ty::ty_closure(_) => {
         closure::make_closure_glue(bcx, v, t, take_ty)
       }
-      ty::ty_trait(_, _, ty::BoxTraitStore) |
-      ty::ty_trait(_, _, ty::BareTraitStore) => {
+      ty::ty_trait(_, _, ty::BoxTraitStore) => {
         let llbox = Load(bcx, GEPi(bcx, v, [0u, 1u]));
         incr_refcnt_of_boxed(bcx, llbox);
         bcx
diff --git a/src/librustc/middle/trans/inline.rs b/src/librustc/middle/trans/inline.rs
index cb20e5bbd32..2ca19b90754 100644
--- a/src/librustc/middle/trans/inline.rs
+++ b/src/librustc/middle/trans/inline.rs
@@ -87,8 +87,7 @@ pub fn maybe_instantiate_inline(ccx: @CrateContext, fn_id: ast::def_id,
             ccx.stats.n_inlines += 1;
             ccx.external.insert(fn_id, Some(mth.id));
             let ty::ty_param_bounds_and_ty {
-                bounds: impl_bnds,
-                region_param: _,
+                generics: ty::Generics { bounds: impl_bnds, _ },
                 ty: _
             } = ty::lookup_item_type(ccx.tcx, impl_did);
             if translate &&
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index feab9945fc4..bbf53480a56 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -11,7 +11,6 @@
 use core::prelude::*;
 
 use back::abi;
-use driver;
 use lib::llvm::llvm;
 use lib::llvm::ValueRef;
 use lib;
@@ -302,8 +301,8 @@ pub fn trans_static_method_callee(bcx: block,
     // found on the type parametesr T1...Tn to find the index of the
     // one we are interested in.
     let bound_index = {
-        let trait_polyty = ty::lookup_item_type(bcx.tcx(), trait_id);
-        ty::count_traits_and_supertraits(bcx.tcx(), *trait_polyty.bounds)
+        let trait_def = ty::lookup_trait_def(bcx.tcx(), trait_id);
+        ty::count_traits_and_supertraits(bcx.tcx(), *trait_def.generics.bounds)
     };
 
     let mname = if method_id.crate == ast::local_crate {
@@ -552,8 +551,10 @@ pub fn combine_impl_and_methods_origins(bcx: block,
     // rcvr + method bounds.
     let ccx = bcx.ccx(), tcx = bcx.tcx();
     let n_m_tps = method_ty_param_count(ccx, mth_did, impl_did);
-    let ty::ty_param_bounds_and_ty {bounds: r_m_bounds, _}
-        = ty::lookup_item_type(tcx, mth_did);
+    let ty::ty_param_bounds_and_ty {
+        generics: ty::Generics {bounds: r_m_bounds, _},
+        _
+    } = ty::lookup_item_type(tcx, mth_did);
     let n_r_m_tps = r_m_bounds.len(); // rcvr + method tps
     let m_boundss = vec::slice(*r_m_bounds, n_r_m_tps - n_m_tps, n_r_m_tps);
 
@@ -656,7 +657,6 @@ pub fn trans_trait_callee_from_llval(bcx: block,
             // payload.
             match store {
                 ty::BoxTraitStore |
-                ty::BareTraitStore |
                 ty::UniqTraitStore => {
                     llself = GEPi(bcx, llbox, [0u, abi::box_field_body]);
                 }
@@ -679,7 +679,7 @@ pub fn trans_trait_callee_from_llval(bcx: block,
 
             // Pass a pointer to the box.
             match store {
-                ty::BoxTraitStore | ty::BareTraitStore => llself = llbox,
+                ty::BoxTraitStore => llself = llbox,
                 _ => bcx.tcx().sess.bug(~"@self receiver with non-@Trait")
             }
 
@@ -785,19 +785,14 @@ pub fn make_impl_vtable(ccx: @CrateContext,
     let tcx = ccx.tcx;
 
     // XXX: This should support multiple traits.
-    let trt_id = driver::session::expect(
-        tcx.sess,
-        ty::ty_to_def_id(ty::impl_traits(tcx,
-                                         impl_id,
-                                         ty::BoxTraitStore)[0]),
-        || ~"make_impl_vtable: non-trait-type implemented");
-
-    let has_tps = (*ty::lookup_item_type(ccx.tcx, impl_id).bounds).len() > 0u;
+    let trt_id = ty::impl_trait_refs(tcx, impl_id)[0].def_id;
+
+    let has_tps = ty::lookup_item_type(ccx.tcx, impl_id).generics.bounds.len() > 0u;
     make_vtable(ccx, ty::trait_method_def_ids(tcx, trt_id).map(|method_def_id| {
         let im = ty::method(tcx, *method_def_id);
         let fty = ty::subst_tps(tcx, substs, None,
                                 ty::mk_bare_fn(tcx, copy im.fty));
-        if im.tps.len() > 0u || ty::type_has_self(fty) {
+        if im.generics.bounds.len() > 0u || ty::type_has_self(fty) {
             debug!("(making impl vtable) method has self or type params: %s",
                    *tcx.sess.str_of(im.ident));
             C_null(T_ptr(T_nil()))
@@ -844,7 +839,7 @@ pub fn trans_trait_cast(bcx: block,
     let v_ty = expr_ty(bcx, val);
 
     match store {
-        ty::RegionTraitStore(_) | ty::BoxTraitStore | ty::BareTraitStore => {
+        ty::RegionTraitStore(_) | ty::BoxTraitStore => {
             let mut llboxdest = GEPi(bcx, lldest, [0u, 1u]);
             // Just store the pointer into the pair.
             llboxdest = PointerCast(bcx,
diff --git a/src/librustc/middle/trans/monomorphize.rs b/src/librustc/middle/trans/monomorphize.rs
index 89617ac5eb8..319f57fb75c 100644
--- a/src/librustc/middle/trans/monomorphize.rs
+++ b/src/librustc/middle/trans/monomorphize.rs
@@ -169,7 +169,7 @@ pub fn monomorphic_fn(ccx: @CrateContext,
     let psubsts = Some(@param_substs {
         tys: substs,
         vtables: vtables,
-        bounds: tpt.bounds,
+        bounds: tpt.generics.bounds,
         self_ty: impl_ty_opt
     });
 
@@ -291,7 +291,7 @@ pub fn normalize_for_monomorphization(tcx: ty::ctxt,
         ty::ty_trait(_, _, ref store) => {
             let sigil = match *store {
                 ty::UniqTraitStore => ast::OwnedSigil,
-                ty::BoxTraitStore | ty::BareTraitStore => ast::ManagedSigil,
+                ty::BoxTraitStore => ast::ManagedSigil,
                 ty::RegionTraitStore(_) => ast::BorrowedSigil,
             };
 
@@ -328,7 +328,7 @@ pub fn make_mono_id(ccx: @CrateContext, item: ast::def_id, substs: &[ty::t],
                     +param_uses: Option<~[type_use::type_uses]>) -> mono_id {
     let precise_param_ids = match vtables {
       Some(vts) => {
-        let bounds = ty::lookup_item_type(ccx.tcx, item).bounds;
+        let bounds = ty::lookup_item_type(ccx.tcx, item).generics.bounds;
         let mut i = 0;
         vec::map2(*bounds, substs, |bounds, subst| {
             let mut v = ~[];
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index eb9eec25c04..b1d977b7445 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -25,8 +25,10 @@ use middle;
 use util::ppaux::{note_and_explain_region, bound_region_to_str};
 use util::ppaux::{region_to_str, vstore_to_str};
 use util::ppaux::{trait_store_to_str, ty_to_str, tys_to_str};
+use util::ppaux::{trait_ref_to_str};
 use util::common::{indenter};
 
+use core;
 use core::cast;
 use core::cmp;
 use core::ops;
@@ -44,6 +46,7 @@ use syntax::ast_util;
 use syntax::codemap::span;
 use syntax::codemap;
 use syntax::print::pprust;
+use syntax::parse::token::special_idents;
 use syntax::{ast, ast_map};
 use syntax::opt_vec::OptVec;
 use syntax::opt_vec;
@@ -70,7 +73,7 @@ pub type param_bounds = @~[param_bound];
 
 pub struct method {
     ident: ast::ident,
-    tps: @~[param_bounds],
+    generics: ty::Generics,
     transformed_self_ty: Option<ty::t>,
     fty: BareFnTy,
     self_ty: ast::self_ty_,
@@ -96,9 +99,8 @@ pub enum vstore {
 
 #[auto_encode]
 #[auto_decode]
-#[deriving(Eq)]
+#[deriving(Eq, IterBytes)]
 pub enum TraitStore {
-    BareTraitStore,             // a plain trait without a sigil
     BoxTraitStore,              // @Trait
     UniqTraitStore,             // ~Trait
     RegionTraitStore(Region),   // &Trait
@@ -225,11 +227,6 @@ pub struct ProvidedMethodSource {
     impl_id: ast::def_id
 }
 
-pub struct InstantiatedTraitRef {
-    def_id: ast::def_id,
-    tpt: ty_param_substs_and_ty
-}
-
 pub type ctxt = @ctxt_;
 
 struct ctxt_ {
@@ -265,8 +262,12 @@ struct ctxt_ {
     // A cache for the trait_methods() routine
     trait_methods_cache: @mut HashMap<def_id, @~[@method]>,
 
+    trait_refs: @mut HashMap<node_id, @TraitRef>,
+    trait_defs: @mut HashMap<def_id, @TraitDef>,
+
     items: ast_map::map,
     intrinsic_defs: @mut HashMap<ast::ident, (ast::def_id, t)>,
+    intrinsic_traits: @mut HashMap<ast::ident, @TraitRef>,
     freevars: freevars::freevar_map,
     tcache: type_cache,
     rcache: creader_cache,
@@ -286,7 +287,7 @@ struct ctxt_ {
     // that implementation implements.
     provided_methods: ProvidedMethodsMap,
     provided_method_sources: @mut HashMap<ast::def_id, ProvidedMethodSource>,
-    supertraits: @mut HashMap<ast::def_id, @~[InstantiatedTraitRef]>,
+    supertraits: @mut HashMap<ast::def_id, @~[@TraitRef]>,
 
     // A mapping from the def ID of an enum or struct type to the def ID
     // of the method that implements its destructor. If the type is not
@@ -536,6 +537,12 @@ pub enum sty {
     ty_unboxed_vec(mt),
 }
 
+#[deriving(Eq, IterBytes)]
+pub struct TraitRef {
+    def_id: def_id,
+    substs: substs
+}
+
 #[deriving(Eq)]
 pub enum IntVarValue {
     IntType(ast::int_ty),
@@ -582,16 +589,17 @@ pub enum type_err {
     terr_self_substs,
     terr_integer_as_char,
     terr_int_mismatch(expected_found<IntVarValue>),
-    terr_float_mismatch(expected_found<ast::float_ty>)
+    terr_float_mismatch(expected_found<ast::float_ty>),
+    terr_traits(expected_found<ast::def_id>),
 }
 
-#[deriving(Eq)]
+#[deriving(Eq, IterBytes)]
 pub enum param_bound {
     bound_copy,
     bound_durable,
     bound_owned,
     bound_const,
-    bound_trait(t),
+    bound_trait(@TraitRef),
 }
 
 #[deriving(Eq)]
@@ -660,19 +668,6 @@ impl cmp::Eq for InferRegion {
     }
 }
 
-impl to_bytes::IterBytes for param_bound {
-    fn iter_bytes(&self, +lsb0: bool, f: to_bytes::Cb) {
-        match *self {
-          bound_copy => 0u8.iter_bytes(lsb0, f),
-          bound_durable => 1u8.iter_bytes(lsb0, f),
-          bound_owned => 2u8.iter_bytes(lsb0, f),
-          bound_const => 3u8.iter_bytes(lsb0, f),
-          bound_trait(ref t) =>
-          to_bytes::iter_bytes_2(&4u8, t, lsb0, f)
-        }
-    }
-}
-
 pub trait Vid {
     fn to_uint(&self) -> uint;
 }
@@ -759,6 +754,13 @@ impl to_bytes::IterBytes for RegionVid {
     }
 }
 
+/// Information about the type/lifetime parametesr associated with an item.
+/// Analogous to ast::Generics.
+pub struct Generics {
+    bounds: @~[param_bounds],
+    region_param: Option<region_variance>,
+}
+
 /// A polytype.
 ///
 /// - `bounds`: The list of bounds for each type parameter.  The length of the
@@ -770,11 +772,16 @@ impl to_bytes::IterBytes for RegionVid {
 /// - `ty`: the base type.  May have reference to the (unsubstituted) bound
 ///   region `&self` or to (unsubstituted) ty_param types
 pub struct ty_param_bounds_and_ty {
-    bounds: @~[param_bounds],
-    region_param: Option<region_variance>,
+    generics: Generics,
     ty: t
 }
 
+/// As `ty_param_bounds_and_ty` but for a trait ref.
+pub struct TraitDef {
+    generics: Generics,
+    trait_ref: @ty::TraitRef,
+}
+
 pub struct ty_param_substs_and_ty {
     substs: ty::substs,
     ty: ty::t
@@ -829,6 +836,9 @@ pub fn mk_ctxt(s: session::Session,
         region_paramd_items: region_paramd_items,
         node_types: @mut SmallIntMap::new(),
         node_type_substs: @mut HashMap::new(),
+        trait_refs: @mut HashMap::new(),
+        trait_defs: @mut HashMap::new(),
+        intrinsic_traits: @mut HashMap::new(),
         items: amap,
         intrinsic_defs: @mut HashMap::new(),
         freevars: freevars,
@@ -1412,7 +1422,7 @@ pub fn param_bound_to_str(cx: ctxt, pb: &param_bound) -> ~str {
         bound_durable => ~"'static",
         bound_owned => ~"owned",
         bound_const => ~"const",
-        bound_trait(t) => ::util::ppaux::ty_to_str(cx, t)
+        bound_trait(t) => ::util::ppaux::trait_ref_to_str(cx, t)
     }
 }
 
@@ -1466,13 +1476,26 @@ pub fn subst(cx: ctxt,
     }
 }
 
+pub fn subst_in_trait_ref(cx: ctxt,
+                          substs: &substs,
+                          trait_ref: &ty::TraitRef) -> ty::TraitRef
+{
+    ty::TraitRef {
+        def_id: trait_ref.def_id,
+        substs: subst_in_substs(cx, substs, &trait_ref.substs)
+    }
+}
+
 // Performs substitutions on a set of substitutions (result = sup(sub)) to
 // yield a new set of substitutions. This is used in trait inheritance.
-pub fn subst_substs(cx: ctxt, sup: &substs, sub: &substs) -> substs {
+pub fn subst_in_substs(cx: ctxt,
+                       substs: &substs,
+                       in_substs: &substs) -> substs
+{
     substs {
-        self_r: sup.self_r,
-        self_ty: sup.self_ty.map(|typ| subst(cx, sub, *typ)),
-        tps: sup.tps.map(|typ| subst(cx, sub, *typ))
+        self_r: in_substs.self_r,
+        self_ty: in_substs.self_ty.map(|&typ| subst(cx, substs, typ)),
+        tps: in_substs.tps.map(|&typ| subst(cx, substs, typ))
     }
 }
 
@@ -1488,6 +1511,11 @@ pub fn type_is_error(ty: t) -> bool {
     (get(ty).flags & (has_ty_err as uint)) != 0
 }
 
+pub fn trait_ref_contains_error(tref: &ty::TraitRef) -> bool {
+    tref.substs.self_ty.any(|&t| type_is_error(t)) ||
+        tref.substs.tps.any(|&t| type_is_error(t))
+}
+
 pub fn type_is_ty_var(ty: t) -> bool {
     match get(ty).sty {
       ty_infer(TyVar(_)) => true,
@@ -1932,8 +1960,7 @@ pub fn type_contents(cx: ctxt, ty: t) -> TypeContents {
                 TC_OWNED_CLOSURE
             }
 
-            ty_trait(_, _, BoxTraitStore) |
-            ty_trait(_, _, BareTraitStore) => {
+            ty_trait(_, _, BoxTraitStore) => {
                 TC_MANAGED
             }
 
@@ -2592,17 +2619,6 @@ impl to_bytes::IterBytes for vstore {
     }
 }
 
-impl to_bytes::IterBytes for TraitStore {
-    fn iter_bytes(&self, +lsb0: bool, f: to_bytes::Cb) {
-        match *self {
-          BareTraitStore => 0u8.iter_bytes(lsb0, f),
-          UniqTraitStore => 1u8.iter_bytes(lsb0, f),
-          BoxTraitStore => 2u8.iter_bytes(lsb0, f),
-          RegionTraitStore(ref r) => to_bytes::iter_bytes_2(&3u8, r, lsb0, f),
-        }
-    }
-}
-
 impl to_bytes::IterBytes for substs {
     fn iter_bytes(&self, +lsb0: bool, f: to_bytes::Cb) {
           to_bytes::iter_bytes_3(&self.self_r,
@@ -2715,6 +2731,16 @@ impl to_bytes::IterBytes for sty {
     }
 }
 
+pub fn node_id_to_trait_ref(cx: ctxt, id: ast::node_id) -> @ty::TraitRef {
+    match cx.trait_refs.find(&id) {
+       Some(&t) => t,
+       None => cx.sess.bug(
+           fmt!("node_id_to_trait_ref: no trait ref for node `%s`",
+                ast_map::node_id_to_str(cx.items, id,
+                                        cx.sess.parse_sess.interner)))
+    }
+}
+
 pub fn node_id_to_type(cx: ctxt, id: ast::node_id) -> t {
     //io::println(fmt!("%?/%?", id, cx.node_types.len()));
     match cx.node_types.find(&(id as uint)) {
@@ -3025,7 +3051,7 @@ pub fn method_call_bounds(tcx: ctxt, method_map: typeck::method_map,
             // n.b.: When we encode impl methods, the bounds
             // that we encode include both the impl bounds
             // and then the method bounds themselves...
-            ty::lookup_item_type(tcx, did).bounds
+            ty::lookup_item_type(tcx, did).generics.bounds
           }
           typeck::method_param(typeck::method_param {
               trait_id: trt_id,
@@ -3036,10 +3062,9 @@ pub fn method_call_bounds(tcx: ctxt, method_map: typeck::method_map,
             // ...trait methods bounds, in contrast, include only the
             // method bounds, so we must preprend the tps from the
             // trait itself.  This ought to be harmonized.
-            let trt_bounds =
-                ty::lookup_item_type(tcx, trt_id).bounds;
+            let trt_bounds = ty::lookup_trait_def(tcx, trt_id).generics.bounds;
             @(vec::append(/*bad*/copy *trt_bounds,
-                          *ty::trait_method(tcx, trt_id, n_mth).tps))
+                          *ty::trait_method(tcx, trt_id, n_mth).generics.bounds))
           }
         }
     }
@@ -3488,6 +3513,11 @@ pub fn type_err_to_str(cx: ctxt, err: &type_err) -> ~str {
                  ty_sort_str(cx, values.expected),
                  ty_sort_str(cx, values.found))
         }
+        terr_traits(values) => {
+            fmt!("expected trait %s but found trait %s",
+                 item_path_str(cx, values.expected),
+                 item_path_str(cx, values.found))
+        }
         terr_self_substs => {
             ~"inconsistent self substitution" // XXX this is more of a bug
         }
@@ -3565,11 +3595,11 @@ pub fn provided_trait_methods(cx: ctxt, id: ast::def_id) -> ~[ast::ident] {
 }
 
 pub fn trait_supertraits(cx: ctxt,
-                         id: ast::def_id)
-                      -> @~[InstantiatedTraitRef] {
+                         id: ast::def_id) -> @~[@TraitRef]
+{
     // Check the cache.
     match cx.supertraits.find(&id) {
-        Some(&instantiated_trait_info) => { return instantiated_trait_info; }
+        Some(&trait_refs) => { return trait_refs; }
         None => {}  // Continue.
     }
 
@@ -3578,25 +3608,10 @@ pub fn trait_supertraits(cx: ctxt,
     assert!(!is_local(id));
 
     // Get the supertraits out of the metadata and create the
-    // InstantiatedTraitRef for each.
-    let mut result = ~[];
-    for csearch::get_supertraits(cx, id).each |trait_type| {
-        match get(*trait_type).sty {
-            ty_trait(def_id, ref substs, _) => {
-                result.push(InstantiatedTraitRef {
-                    def_id: def_id,
-                    tpt: ty_param_substs_and_ty {
-                        substs: (/*bad*/copy *substs),
-                        ty: *trait_type
-                    }
-                });
-            }
-            _ => cx.sess.bug(~"trait_supertraits: trait ref wasn't a trait")
-        }
-    }
-
-    // Unwrap and return the result.
-    return @result;
+    // TraitRef for each.
+    let result = @csearch::get_supertraits(cx, id);
+    cx.supertraits.insert(id, result);
+    return result;
 }
 
 fn lookup_locally_or_in_crate_store<V:Copy>(
@@ -3659,23 +3674,7 @@ pub fn trait_method_def_ids(cx: ctxt, id: ast::def_id) -> @~[def_id] {
         || @csearch::get_trait_method_def_ids(cx.cstore, id))
 }
 
-/*
-  Could this return a list of (def_id, substs) pairs?
- */
-pub fn impl_traits(cx: ctxt, id: ast::def_id, store: TraitStore) -> ~[t] {
-    fn storeify(cx: ctxt, ty: t, store: TraitStore) -> t {
-        match ty::get(ty).sty {
-            ty::ty_trait(did, ref substs, trait_store) => {
-                if store == trait_store {
-                    ty
-                } else {
-                    mk_trait(cx, did, (/*bad*/copy *substs), store)
-                }
-            }
-            _ => cx.sess.bug(~"impl_traits: not a trait")
-        }
-    }
-
+pub fn impl_trait_refs(cx: ctxt, id: ast::def_id) -> ~[@TraitRef] {
     if id.crate == ast::local_crate {
         debug!("(impl_traits) searching for trait impl %?", id);
         match cx.items.find(&id.node) {
@@ -3683,17 +3682,15 @@ pub fn impl_traits(cx: ctxt, id: ast::def_id, store: TraitStore) -> ~[t] {
                         node: ast::item_impl(_, opt_trait, _, _),
                         _},
                     _)) => {
-
-               do opt_trait.map_default(~[]) |trait_ref| {
-                   ~[storeify(cx, node_id_to_type(cx, trait_ref.ref_id),
-                              store)]
+               match opt_trait {
+                   Some(t) => ~[ty::node_id_to_trait_ref(cx, t.ref_id)],
+                   None => ~[]
                }
            }
            _ => ~[]
         }
     } else {
-        vec::map(csearch::get_impl_traits(cx, id),
-                 |x| storeify(cx, *x, store))
+        csearch::get_impl_traits(cx, id)
     }
 }
 
@@ -3967,6 +3964,23 @@ pub fn lookup_item_type(cx: ctxt,
         || csearch::get_type(cx, did))
 }
 
+/// Given the did of a trait, returns its canonical trait ref.
+pub fn lookup_trait_def(cx: ctxt, did: ast::def_id) -> @ty::TraitDef {
+    match cx.trait_defs.find(&did) {
+        Some(&trait_def) => {
+            // The item is in this crate. The caller should have added it to the
+            // type cache already
+            return trait_def;
+        }
+        None => {
+            assert!(did.crate != ast::local_crate);
+            let trait_def = @csearch::get_trait_def(cx, did);
+            cx.trait_defs.insert(did, trait_def);
+            return trait_def;
+        }
+    }
+}
+
 // Look up a field ID, whether or not it's local
 // Takes a list of type substs in case the struct is generic
 pub fn lookup_field_type(tcx: ctxt,
@@ -4250,9 +4264,6 @@ pub fn normalize_ty(cx: ctxt, t: t) -> t {
                 t
             },
 
-        ty_trait(did, ref substs, BareTraitStore) =>
-            mk_trait(cx, did, copy *substs, BoxTraitStore),
-
         _ =>
             t
     };
@@ -4318,12 +4329,11 @@ pub fn determine_inherited_purity(parent_purity: ast::purity,
 // list.
 pub fn iter_bound_traits_and_supertraits(tcx: ctxt,
                                          bounds: param_bounds,
-                                         f: &fn(t) -> bool) {
+                                         f: &fn(&TraitRef) -> bool) {
     let mut fin = false;
 
     for bounds.each |bound| {
-
-        let bound_trait_ty = match *bound {
+        let bound_trait_ref = match *bound {
             ty::bound_trait(bound_t) => bound_t,
 
             ty::bound_copy | ty::bound_owned |
@@ -4332,39 +4342,38 @@ pub fn iter_bound_traits_and_supertraits(tcx: ctxt,
             }
         };
 
-        let mut supertrait_map = HashMap::new();
+        let mut supertrait_set = HashMap::new();
         let mut seen_def_ids = ~[];
         let mut i = 0;
-        let trait_ty_id = ty_to_def_id(bound_trait_ty).expect(
-            ~"iter_trait_ty_supertraits got a non-trait type");
-        let mut trait_ty = bound_trait_ty;
+        let trait_ty_id = bound_trait_ref.def_id;
+        let mut trait_ref = bound_trait_ref;
 
-        debug!("iter_bound_traits_and_supertraits: trait_ty = %s",
-               ty_to_str(tcx, trait_ty));
+        debug!("iter_bound_traits_and_supertraits: trait_ref = %s",
+               trait_ref_to_str(tcx, trait_ref));
 
         // Add the given trait ty to the hash map
-        supertrait_map.insert(trait_ty_id, trait_ty);
+        supertrait_set.insert(trait_ty_id, ());
         seen_def_ids.push(trait_ty_id);
 
-        if f(trait_ty) {
+        if f(trait_ref) {
             // Add all the supertraits to the hash map,
             // executing <f> on each of them
-            while i < supertrait_map.len() && !fin {
+            while i < supertrait_set.len() && !fin {
                 let init_trait_id = seen_def_ids[i];
                 i += 1;
-                 // Add supertraits to supertrait_map
-                let supertraits = trait_supertraits(tcx, init_trait_id);
-                for supertraits.each |supertrait| {
-                    let super_t = supertrait.tpt.ty;
-                    let d_id = ty_to_def_id(super_t).expect("supertrait \
-                        should be a trait ty");
-                    if !supertrait_map.contains_key(&d_id) {
-                        supertrait_map.insert(d_id, super_t);
-                        trait_ty = super_t;
+
+                 // Add supertraits to supertrait_set
+                let supertrait_refs = trait_supertraits(tcx, init_trait_id);
+                for supertrait_refs.each |&supertrait_ref| {
+                    let d_id = supertrait_ref.def_id;
+                    if !supertrait_set.contains_key(&d_id) {
+                        // NOTE Could have same trait multiple times
+                        supertrait_set.insert(d_id, ());
+                        trait_ref = supertrait_ref;
                         seen_def_ids.push(d_id);
                     }
-                    debug!("A super_t = %s", ty_to_str(tcx, trait_ty));
-                    if !f(trait_ty) {
+                    debug!("A super_t = %s", trait_ref_to_str(tcx, trait_ref));
+                    if !f(trait_ref) {
                         fin = true;
                     }
                 }
@@ -4401,6 +4410,14 @@ pub fn get_impl_id(tcx: ctxt, trait_id: def_id, self_ty: t) -> def_id {
     }
 }
 
+pub fn visitor_object_ty(tcx: ctxt) -> (@TraitRef, t) {
+    let ty_visitor_name = special_idents::ty_visitor;
+    assert!(tcx.intrinsic_traits.contains_key(&ty_visitor_name));
+    let trait_ref = *tcx.intrinsic_traits.get(&ty_visitor_name);
+    (trait_ref,
+     mk_trait(tcx, trait_ref.def_id, copy trait_ref.substs, BoxTraitStore))
+}
+
 // Local Variables:
 // mode: rust
 // fill-column: 78;
diff --git a/src/librustc/middle/typeck/astconv.rs b/src/librustc/middle/typeck/astconv.rs
index 05a5e926f27..209091ecd66 100644
--- a/src/librustc/middle/typeck/astconv.rs
+++ b/src/librustc/middle/typeck/astconv.rs
@@ -14,14 +14,14 @@
  * is parameterized by an instance of `AstConv` and a `region_scope`.
  *
  * The parameterization of `ast_ty_to_ty()` is because it behaves
- * somewhat differently during the collect and check phases, particularly
- * with respect to looking up the types of top-level items.  In the
- * collect phase, the crate context is used as the `AstConv` instance;
- * in this phase, the `get_item_ty()` function triggers a recursive call
- * to `ty_of_item()` (note that `ast_ty_to_ty()` will detect recursive
- * types and report an error).  In the check phase, when the @FnCtxt is
- * used as the `AstConv`, `get_item_ty()` just looks up the item type in
- * `tcx.tcache`.
+ * somewhat differently during the collect and check phases,
+ * particularly with respect to looking up the types of top-level
+ * items.  In the collect phase, the crate context is used as the
+ * `AstConv` instance; in this phase, the `get_item_ty()` function
+ * triggers a recursive call to `ty_of_item()`  (note that
+ * `ast_ty_to_ty()` will detect recursive types and report an error).
+ * In the check phase, when the @FnCtxt is used as the `AstConv`,
+ * `get_item_ty()` just looks up the item type in `tcx.tcache`.
  *
  * The `region_scope` trait controls how region references are
  * handled.  It has two methods which are used to resolve anonymous
@@ -76,6 +76,7 @@ use util::common::indenter;
 pub trait AstConv {
     fn tcx(&self) -> ty::ctxt;
     fn get_item_ty(&self, id: ast::def_id) -> ty::ty_param_bounds_and_ty;
+    fn get_trait_def(&self, id: ast::def_id) -> @ty::TraitDef;
 
     // what type should we use when a type is omitted?
     fn ty_infer(&self, span: span) -> ty::t;
@@ -129,62 +130,96 @@ pub fn ast_region_to_region<AC:AstConv,RS:region_scope + Copy + Durable>(
     get_region_reporting_err(self.tcx(), span, opt_lifetime, res)
 }
 
-pub fn ast_path_to_substs_and_ty<AC:AstConv,RS:region_scope + Copy + Durable>(
-        self: &AC,
-        rscope: &RS,
-        did: ast::def_id,
-        path: @ast::path)
-     -> ty_param_substs_and_ty {
-    let tcx = self.tcx();
-    let ty::ty_param_bounds_and_ty {
-        bounds: decl_bounds,
-        region_param: decl_rp,
-        ty: decl_ty
-    } = self.get_item_ty(did);
+fn ast_path_substs<AC:AstConv,RS:region_scope + Copy + Durable>(
+    self: &AC,
+    rscope: &RS,
+    def_id: ast::def_id,
+    decl_generics: &ty::Generics,
+    path: @ast::path) -> ty::substs
+{
+    /*!
+     *
+     * Given a path `path` that refers to an item `I` with the
+     * declared generics `decl_generics`, returns an appropriate
+     * set of substitutions for this particular reference to `I`.
+     */
 
-    debug!("ast_path_to_substs_and_ty: did=%? decl_rp=%?",
-           did, decl_rp);
+    let tcx = self.tcx();
 
     // If the type is parameterized by the self region, then replace self
     // region with the current anon region binding (in other words,
     // whatever & would get replaced with).
-    let self_r = match (decl_rp, path.rp) {
-      (None, None) => {
+    let self_r = match (&decl_generics.region_param, &path.rp) {
+      (&None, &None) => {
         None
       }
-      (None, Some(_)) => {
+      (&None, &Some(_)) => {
         tcx.sess.span_err(
             path.span,
             fmt!("no region bound is allowed on `%s`, \
                   which is not declared as containing region pointers",
-                 ty::item_path_str(tcx, did)));
+                 ty::item_path_str(tcx, def_id)));
         None
       }
-      (Some(_), None) => {
+      (&Some(_), &None) => {
         let res = rscope.anon_region(path.span);
         let r = get_region_reporting_err(self.tcx(), path.span, None, res);
         Some(r)
       }
-      (Some(_), Some(_)) => {
+      (&Some(_), &Some(_)) => {
         Some(ast_region_to_region(self, rscope, path.span, path.rp))
       }
     };
 
     // Convert the type parameters supplied by the user.
-    if !vec::same_length(*decl_bounds, path.types) {
+    if !vec::same_length(*decl_generics.bounds, path.types) {
         self.tcx().sess.span_fatal(
             path.span,
             fmt!("wrong number of type arguments: expected %u but found %u",
-                 (*decl_bounds).len(), path.types.len()));
+                 decl_generics.bounds.len(), path.types.len()));
     }
     let tps = path.types.map(|a_t| ast_ty_to_ty(self, rscope, *a_t));
 
-    let substs = substs {self_r:self_r, self_ty:None, tps:tps};
-    let ty = ty::subst(tcx, &substs, decl_ty);
+    substs {self_r:self_r, self_ty:None, tps:tps}
+}
 
+pub fn ast_path_to_substs_and_ty<AC:AstConv,RS:region_scope + Copy + Durable>(
+    self: &AC,
+    rscope: &RS,
+    did: ast::def_id,
+    path: @ast::path) -> ty_param_substs_and_ty
+{
+    let tcx = self.tcx();
+    let ty::ty_param_bounds_and_ty {
+        generics: generics,
+        ty: decl_ty
+    } = self.get_item_ty(did);
+
+    let substs = ast_path_substs(self, rscope, did, &generics, path);
+    let ty = ty::subst(tcx, &substs, decl_ty);
     ty_param_substs_and_ty { substs: substs, ty: ty }
 }
 
+pub fn ast_path_to_trait_ref<AC:AstConv,RS:region_scope + Copy + Durable>(
+    self: &AC,
+    rscope: &RS,
+    trait_def_id: ast::def_id,
+    path: @ast::path) -> @ty::TraitRef
+{
+    let trait_def =
+        self.get_trait_def(trait_def_id);
+    let substs =
+        ast_path_substs(
+            self, rscope,
+            trait_def.trait_ref.def_id, &trait_def.generics,
+            path);
+    let trait_ref =
+        @ty::TraitRef {def_id: trait_def_id,
+                       substs: substs};
+    return trait_ref;
+}
+
+
 pub fn ast_path_to_ty<AC:AstConv,RS:region_scope + Copy + Durable>(
         self: &AC,
         rscope: &RS,
@@ -243,40 +278,29 @@ pub fn ast_ty_to_ty<AC:AstConv, RS:region_scope + Copy + Durable>(
                         check_path_args(tcx, path, NO_TPS | NO_REGIONS);
                         return ty::mk_estr(tcx, vst);
                     }
-                    Some(&ast::def_trait(type_def_id)) => {
-                        let result = ast_path_to_substs_and_ty(
-                            self, rscope,
-                            type_def_id, path);
-                        match ty::get(result.ty).sty {
-                            ty::ty_trait(trait_def_id, ref substs, _) => {
-                                let trait_store = match vst {
-                                    ty::vstore_box => ty::BoxTraitStore,
-                                    ty::vstore_uniq => ty::UniqTraitStore,
-                                    ty::vstore_slice(r) => {
-                                        ty::RegionTraitStore(r)
-                                    }
-                                    ty::vstore_fixed(*) => {
-                                        tcx.sess.span_err(
-                                            path.span,
-                                            ~"@trait, ~trait or &trait \
-                                              are the only supported \
-                                              forms of casting-to-\
-                                              trait");
-                                        ty::BoxTraitStore
-                                    }
-                                };
-                                return ty::mk_trait(tcx,
-                                                    trait_def_id,
-                                                    /*bad*/copy *substs,
-                                                    trait_store);
-
+                    Some(&ast::def_trait(trait_def_id)) => {
+                        let result = ast_path_to_trait_ref(
+                            self, rscope, trait_def_id, path);
+                        let trait_store = match vst {
+                            ty::vstore_box => ty::BoxTraitStore,
+                            ty::vstore_uniq => ty::UniqTraitStore,
+                            ty::vstore_slice(r) => {
+                                ty::RegionTraitStore(r)
                             }
-                            _ => {
-                                tcx.sess.span_bug(
-                                    a_seq_ty.ty.span,
-                                    fmt!("def_trait but not ty_trait"));
+                            ty::vstore_fixed(*) => {
+                                tcx.sess.span_err(
+                                    path.span,
+                                    ~"@trait, ~trait or &trait \
+                                      are the only supported \
+                                      forms of casting-to-\
+                                      trait");
+                                ty::BoxTraitStore
                             }
-                        }
+                        };
+                        return ty::mk_trait(tcx,
+                                            result.def_id,
+                                            copy result.substs,
+                                            trait_store);
                     }
                     _ => {}
                 }
@@ -376,7 +400,16 @@ pub fn ast_ty_to_ty<AC:AstConv, RS:region_scope + Copy + Durable>(
           Some(&d) => d
         };
         match a_def {
-          ast::def_trait(did) | ast::def_ty(did) | ast::def_struct(did) => {
+          ast::def_trait(_) => {
+              let path_str = path_to_str(path, tcx.sess.intr());
+              tcx.sess.span_err(
+                  ast_ty.span,
+                  fmt!("reference to trait `%s` where a type is expected; \
+                        try `@%s`, `~%s`, or `&%s`",
+                       path_str, path_str, path_str, path_str));
+              ty::mk_err(tcx)
+          }
+          ast::def_ty(did) | ast::def_struct(did) => {
             ast_path_to_ty(self, rscope, did, path).ty
           }
           ast::def_prim_ty(nty) => {
diff --git a/src/librustc/middle/typeck/check/_match.rs b/src/librustc/middle/typeck/check/_match.rs
index f2d0ef22970..605caba74a3 100644
--- a/src/librustc/middle/typeck/check/_match.rs
+++ b/src/librustc/middle/typeck/check/_match.rs
@@ -135,7 +135,7 @@ pub fn check_pat_variant(pcx: pat_ctxt, pat: @ast::pat, path: @ast::path,
                     ty::enum_variant_with_id(tcx, enm, var);
                 let var_tpt = ty::lookup_item_type(tcx, var);
                 vinfo.args.map(|t| {
-                    if var_tpt.bounds.len() == expected_substs.tps.len() {
+                    if var_tpt.generics.bounds.len() == expected_substs.tps.len() {
                         ty::subst(tcx, expected_substs, *t)
                     }
                     else {
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index e2d9a8a20c7..fa3cb43d9ab 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -382,7 +382,7 @@ pub impl<'self> LookupContext<'self> {
         let bounds = tcx.ty_param_bounds.get(&param_ty.def_id.node);
 
         for bounds.each |bound| {
-            let bound_trait_ty = match *bound {
+            let bound_trait_ref = match *bound {
                 ty::bound_trait(bound_t) => bound_t,
 
                 ty::bound_copy | ty::bound_owned |
@@ -391,22 +391,10 @@ pub impl<'self> LookupContext<'self> {
                 }
             };
 
-
-            let bound_substs = match ty::get(bound_trait_ty).sty {
-                ty::ty_trait(_, ref substs, _) => (/*bad*/copy *substs),
-                _ => {
-                    self.bug(fmt!("add_candidates_from_param: \
-                                   non-trait bound %s",
-                                  self.ty_to_str(bound_trait_ty)));
-                }
-            };
-
-
             // Loop over the trait and all of its supertraits.
             let mut worklist = ~[];
 
-            let init_trait_ty = bound_trait_ty;
-            let init_substs = bound_substs;
+            let init_trait_ref = bound_trait_ref;
 
             // Replace any appearance of `self` with the type of the
             // generic parameter itself.  Note that this is the only
@@ -417,29 +405,26 @@ pub impl<'self> LookupContext<'self> {
             // to self are not permitted).
             let init_substs = substs {
                 self_ty: Some(rcvr_ty),
-                ..init_substs
+                ..copy bound_trait_ref.substs
             };
 
-            worklist.push((init_trait_ty, init_substs));
+            worklist.push((init_trait_ref.def_id, init_substs));
 
             let mut i = 0;
             while i < worklist.len() {
-                let (init_trait_ty, init_substs) = /*bad*/copy worklist[i];
+                let (init_trait_id, init_substs) = /*bad*/copy worklist[i];
                 i += 1;
 
-                let init_trait_id = ty::ty_to_def_id(init_trait_ty).get();
-
                 // Add all the supertraits of this trait to the worklist.
-                let supertraits = ty::trait_supertraits(tcx,
-                                                        init_trait_id);
-                for supertraits.each |supertrait| {
+                let supertraits = ty::trait_supertraits(tcx, init_trait_id);
+                for supertraits.each |supertrait_ref| {
                     debug!("adding supertrait: %?",
-                           supertrait.def_id);
+                           supertrait_ref.def_id);
 
-                    let new_substs = ty::subst_substs(
+                    let new_substs = ty::subst_in_substs(
                         tcx,
-                        &supertrait.tpt.substs,
-                        &init_substs);
+                        &init_substs,
+                        &supertrait_ref.substs);
 
                     // Again replacing the self type
                     let new_substs = substs {
@@ -447,7 +432,7 @@ pub impl<'self> LookupContext<'self> {
                         ..new_substs
                     };
 
-                    worklist.push((supertrait.tpt.ty, new_substs));
+                    worklist.push((supertrait_ref.def_id, new_substs));
                 }
 
 
@@ -1116,7 +1101,7 @@ pub impl<'self> LookupContext<'self> {
         // If they were not explicitly supplied, just construct fresh
         // type variables.
         let num_supplied_tps = self.supplied_tps.len();
-        let num_method_tps = candidate.method_ty.tps.len();
+        let num_method_tps = candidate.method_ty.generics.bounds.len();
         let m_substs = {
             if num_supplied_tps == 0u {
                 self.fcx.infcx().next_ty_vars(num_method_tps)
@@ -1210,7 +1195,7 @@ pub impl<'self> LookupContext<'self> {
                   self-type through a boxed trait");
         }
 
-        if candidate.method_ty.tps.len() > 0 {
+        if candidate.method_ty.generics.bounds.len() > 0 {
             self.tcx().sess.span_err(
                 self.expr.span,
                 ~"cannot call a generic method through a boxed trait");
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 560fcb8c920..957259e7d17 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -610,7 +610,7 @@ pub fn check_item(ccx: @mut CrateCtxt, it: @ast::item) {
         } else {
             for m.items.each |item| {
                 let tpt = ty::lookup_item_type(ccx.tcx, local_def(item.id));
-                if !tpt.bounds.is_empty() {
+                if !tpt.generics.bounds.is_empty() {
                     ccx.tcx.sess.span_err(
                         item.span,
                         fmt!("foreign items may not have type parameters"));
@@ -629,6 +629,10 @@ impl AstConv for FnCtxt {
         ty::lookup_item_type(self.tcx(), id)
     }
 
+    fn get_trait_def(&self, id: ast::def_id) -> @ty::TraitDef {
+        ty::lookup_trait_def(self.tcx(), id)
+    }
+
     fn ty_infer(&self, _span: span) -> ty::t {
         self.infcx().next_ty_var()
     }
@@ -1064,7 +1068,7 @@ pub fn impl_self_ty(vcx: &VtableContext,
 
     let (n_tps, region_param, raw_ty) = {
         let ity = ty::lookup_item_type(tcx, did);
-        (vec::len(*ity.bounds), ity.region_param, ity.ty)
+        (ity.generics.bounds.len(), ity.generics.region_param, ity.ty)
     };
 
     let self_r = if region_param.is_some() {
@@ -1888,8 +1892,8 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
             }
         } else {
             let item_type = ty::lookup_item_type(tcx, class_id);
-            type_parameter_count = (*item_type.bounds).len();
-            region_parameterized = item_type.region_param;
+            type_parameter_count = item_type.generics.bounds.len();
+            region_parameterized = item_type.generics.region_param;
             raw_type = item_type.ty;
         }
 
@@ -1976,8 +1980,8 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
             }
         } else {
             let item_type = ty::lookup_item_type(tcx, enum_id);
-            type_parameter_count = (*item_type.bounds).len();
-            region_parameterized = item_type.region_param;
+            type_parameter_count = item_type.generics.bounds.len();
+            region_parameterized = item_type.generics.region_param;
             raw_type = item_type.ty;
         }
 
@@ -3147,8 +3151,10 @@ pub fn ty_param_bounds_and_ty_for_def(fcx: @mut FnCtxt,
       ast::def_fn(_, ast::extern_fn) => {
         // extern functions are just u8 pointers
         return ty_param_bounds_and_ty {
-            bounds: @~[],
-            region_param: None,
+            generics: ty::Generics {
+                bounds: @~[],
+                region_param: None
+            },
             ty: ty::mk_ptr(
                 fcx.ccx.tcx,
                 ty::mt {
@@ -3211,7 +3217,7 @@ pub fn instantiate_path(fcx: @mut FnCtxt,
                         region_lb: ty::Region) {
     debug!(">>> instantiate_path");
 
-    let ty_param_count = vec::len(*tpt.bounds);
+    let ty_param_count = tpt.generics.bounds.len();
     let ty_substs_len = vec::len(pth.types);
 
     debug!("ty_param_count=%? ty_substs_len=%?",
@@ -3222,7 +3228,7 @@ pub fn instantiate_path(fcx: @mut FnCtxt,
     // (if any) and otherwise using a fresh region variable
     let self_r = match pth.rp {
       Some(_) => { // user supplied a lifetime parameter...
-        match tpt.region_param {
+        match tpt.generics.region_param {
           None => { // ...but the type is not lifetime parameterized!
             fcx.ccx.tcx.sess.span_err
                 (span, ~"this item is not region-parameterized");
@@ -3235,7 +3241,7 @@ pub fn instantiate_path(fcx: @mut FnCtxt,
       }
       None => { // no lifetime parameter supplied, insert default
         fcx.region_var_if_parameterized(
-            tpt.region_param, span, region_lb)
+            tpt.generics.region_param, span, region_lb)
       }
     };
 
@@ -3433,28 +3439,13 @@ pub fn check_intrinsic_type(ccx: @mut CrateCtxt, it: @ast::foreign_item) {
       }
       ~"visit_tydesc" => {
           let tydesc_name = special_idents::tydesc;
-          let ty_visitor_name = tcx.sess.ident_of(~"TyVisitor");
           assert!(tcx.intrinsic_defs.contains_key(&tydesc_name));
-          assert!(ccx.tcx.intrinsic_defs.contains_key(&ty_visitor_name));
           let (_, tydesc_ty) = *tcx.intrinsic_defs.get(&tydesc_name);
-          let (_, visitor_trait) = *tcx.intrinsic_defs.get(&ty_visitor_name);
-
-          let visitor_trait = match ty::get(visitor_trait).sty {
-            ty::ty_trait(trait_def_id, ref trait_substs, _) => {
-                ty::mk_trait(tcx,
-                             trait_def_id,
-                             copy *trait_substs,
-                             ty::BoxTraitStore)
-            }
-            _ => {
-                tcx.sess.span_bug(it.span, ~"TyVisitor wasn't a trait?!")
-            }
-          };
-
+          let (_, visitor_object_ty) = ty::visitor_object_ty(tcx);
           let td_ptr = ty::mk_ptr(ccx.tcx, ty::mt {ty: tydesc_ty,
                                                    mutbl: ast::m_imm});
           (0u, ~[arg(ast::by_copy, td_ptr),
-                 arg(ast::by_ref, visitor_trait)], ty::mk_nil(tcx))
+                 arg(ast::by_ref, visitor_object_ty)], ty::mk_nil(tcx))
       }
       ~"frame_address" => {
         let fty = ty::mk_closure(ccx.tcx, ty::ClosureTy {
@@ -3700,7 +3691,7 @@ pub fn check_intrinsic_type(ccx: @mut CrateCtxt, it: @ast::foreign_item) {
                     output: output}
     });
     let i_ty = ty::lookup_item_type(ccx.tcx, local_def(it.id));
-    let i_n_tps = (*i_ty.bounds).len();
+    let i_n_tps = i_ty.generics.bounds.len();
     if i_n_tps != n_tps {
         tcx.sess.span_err(it.span, fmt!("intrinsic has wrong number \
                                          of type parameters: found %u, \
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index 51f54d21ec4..c30765baf37 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -70,7 +70,7 @@ pub impl VtableContext {
     fn tcx(&const self) -> ty::ctxt { self.ccx.tcx }
 }
 
-pub fn has_trait_bounds(tps: ~[ty::param_bounds]) -> bool {
+fn has_trait_bounds(tps: ~[ty::param_bounds]) -> bool {
     vec::any(tps, |bs| {
         bs.any(|b| {
             match b { &ty::bound_trait(_) => true, _ => false }
@@ -78,11 +78,11 @@ pub fn has_trait_bounds(tps: ~[ty::param_bounds]) -> bool {
     })
 }
 
-pub fn lookup_vtables(vcx: &VtableContext,
-                      location_info: &LocationInfo,
-                      bounds: @~[ty::param_bounds],
-                      substs: &ty::substs,
-                      is_early: bool) -> vtable_res {
+fn lookup_vtables(vcx: &VtableContext,
+                  location_info: &LocationInfo,
+                  bounds: @~[ty::param_bounds],
+                  substs: &ty::substs,
+                  is_early: bool) -> vtable_res {
     debug!("lookup_vtables(location_info=%?,
             # bounds=%?, \
             substs=%s",
@@ -95,30 +95,30 @@ pub fn lookup_vtables(vcx: &VtableContext,
     let mut result = ~[], i = 0u;
     for substs.tps.each |ty| {
         for ty::iter_bound_traits_and_supertraits(
-            tcx, bounds[i]) |trait_ty|
+            tcx, bounds[i]) |trait_ref|
         {
             debug!("about to subst: %?, %?",
-                   ppaux::ty_to_str(tcx, trait_ty),
+                   ppaux::trait_ref_to_str(tcx, trait_ref),
                    ty::substs_to_str(tcx, substs));
 
             let new_substs = substs {
                 self_ty: Some(*ty),
                 ../*bad*/copy *substs
             };
-            let trait_ty = ty::subst(tcx, &new_substs, trait_ty);
+            let trait_ref = ty::subst_in_trait_ref(tcx, &new_substs, trait_ref);
 
             debug!("after subst: %?",
-                   ppaux::ty_to_str(tcx, trait_ty));
+                   vcx.infcx.trait_ref_to_str(&trait_ref));
 
-            match lookup_vtable(vcx, location_info, *ty, trait_ty, is_early) {
+            match lookup_vtable(vcx, location_info, *ty, &trait_ref, is_early) {
                 Some(vtable) => result.push(vtable),
                 None => {
                     vcx.tcx().sess.span_fatal(
                         location_info.span,
                         fmt!("failed to find an implementation of \
                               trait %s for %s",
-                             ppaux::ty_to_str(vcx.tcx(), trait_ty),
-                             ppaux::ty_to_str(vcx.tcx(), *ty)));
+                             vcx.infcx.trait_ref_to_str(&trait_ref),
+                             vcx.infcx.ty_to_str(*ty)));
                 }
             }
         }
@@ -136,9 +136,9 @@ pub fn lookup_vtables(vcx: &VtableContext,
     @result
 }
 
-pub fn fixup_substs(vcx: &VtableContext, location_info: &LocationInfo,
-                    id: ast::def_id, +substs: ty::substs,
-                    is_early: bool) -> Option<ty::substs> {
+fn fixup_substs(vcx: &VtableContext, location_info: &LocationInfo,
+                id: ast::def_id, +substs: ty::substs,
+                is_early: bool) -> Option<ty::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,
@@ -152,31 +152,58 @@ pub fn fixup_substs(vcx: &VtableContext, location_info: &LocationInfo,
     }
 }
 
-pub fn relate_trait_tys(vcx: &VtableContext, location_info: &LocationInfo,
-                        exp_trait_ty: ty::t, act_trait_ty: ty::t) {
-    demand_suptype(vcx, location_info.span, exp_trait_ty, act_trait_ty)
+fn relate_trait_refs(vcx: &VtableContext,
+                     location_info: &LocationInfo,
+                     act_trait_ref: &ty::TraitRef,
+                     exp_trait_ref: &ty::TraitRef)
+{
+    /*!
+     *
+     * Checks that an implementation of `act_trait_ref` is suitable
+     * for use where `exp_trait_ref` is required and reports an
+     * error otherwise.
+     */
+
+    match infer::mk_sub_trait_refs(vcx.infcx, false, location_info.span,
+                                   act_trait_ref, exp_trait_ref)
+    {
+        result::Ok(()) => {} // Ok.
+        result::Err(ref err) => {
+            let r_act_trait_ref =
+                vcx.infcx.resolve_type_vars_in_trait_ref_if_possible(act_trait_ref);
+            let r_exp_trait_ref =
+                vcx.infcx.resolve_type_vars_in_trait_ref_if_possible(exp_trait_ref);
+            if !ty::trait_ref_contains_error(&r_act_trait_ref) &&
+                !ty::trait_ref_contains_error(&r_exp_trait_ref)
+            {
+                let tcx = vcx.tcx();
+                tcx.sess.span_err(
+                    location_info.span,
+                    fmt!("expected %s, but found %s (%s)",
+                         ppaux::trait_ref_to_str(tcx, &r_exp_trait_ref),
+                         ppaux::trait_ref_to_str(tcx, &r_act_trait_ref),
+                         ty::type_err_to_str(tcx, err)));
+            }
+        }
+    }
 }
 
 // Look up the vtable to use when treating an item of type `t` as if it has
 // type `trait_ty`
-pub fn lookup_vtable(vcx: &VtableContext,
-                     location_info: &LocationInfo,
-                     ty: ty::t,
-                     trait_ty: ty::t,
-                     is_early: bool)
-                  -> Option<vtable_origin> {
-    debug!("lookup_vtable(ty=%s, trait_ty=%s)",
-           vcx.infcx.ty_to_str(ty), vcx.infcx.ty_to_str(trait_ty));
+fn lookup_vtable(vcx: &VtableContext,
+                 location_info: &LocationInfo,
+                 ty: ty::t,
+                 trait_ref: &ty::TraitRef,
+                 is_early: bool)
+    -> Option<vtable_origin>
+{
+    debug!("lookup_vtable(ty=%s, trait_ref=%s)",
+           vcx.infcx.ty_to_str(ty),
+           vcx.infcx.trait_ref_to_str(trait_ref));
     let _i = indenter();
 
     let tcx = vcx.tcx();
-    let (trait_id, trait_substs, trait_store) = match ty::get(trait_ty).sty {
-        ty::ty_trait(did, ref substs, store) =>
-            (did, (/*bad*/copy *substs), store),
-        _ => tcx.sess.impossible_case(location_info.span,
-                                      "lookup_vtable: \
-                                       don't know how to handle a non-trait")
-    };
+
     let ty = match fixup_ty(vcx, location_info, ty, is_early) {
         Some(ty) => ty,
         None => {
@@ -194,37 +221,20 @@ pub fn lookup_vtable(vcx: &VtableContext,
             let mut n_bound = 0;
             let bounds = *tcx.ty_param_bounds.get(&did.node);
             for ty::iter_bound_traits_and_supertraits(
-                tcx, bounds) |ity| {
+                tcx, bounds) |bound_trait_ref|
+            {
                 debug!("checking bounds trait %?",
-                       vcx.infcx.ty_to_str(ity));
-
-                match ty::get(ity).sty {
-                    ty::ty_trait(idid, ref isubsts, _) => {
-                        if trait_id == idid {
-                            debug!("(checking vtable) @0 \
-                                    relating ty to trait \
-                                    ty with did %?",
-                                   idid);
-
-                            // Convert `ity` so that it has the right vstore.
-                            let ity = ty::mk_trait(vcx.tcx(),
-                                                   idid,
-                                                   copy *isubsts,
-                                                   trait_store);
-
-                            relate_trait_tys(vcx, location_info,
-                                             trait_ty, ity);
-                            let vtable = vtable_param(n, n_bound);
-                            debug!("found param vtable: %?",
-                                   vtable);
-                            return Some(vtable);
-                        }
-                    }
-                    _ => tcx.sess.impossible_case(
-                        location_info.span,
-                        "lookup_vtable: in loop, \
-                         don't know how to handle a \
-                         non-trait ity")
+                       vcx.infcx.trait_ref_to_str(bound_trait_ref));
+
+                if bound_trait_ref.def_id == trait_ref.def_id {
+                    relate_trait_refs(vcx,
+                                      location_info,
+                                      bound_trait_ref,
+                                      trait_ref);
+                    let vtable = vtable_param(n, n_bound);
+                    debug!("found param vtable: %?",
+                           vtable);
+                    return Some(vtable);
                 }
 
                 n_bound += 1;
@@ -236,18 +246,19 @@ pub fn lookup_vtable(vcx: &VtableContext,
 
             let mut impls_seen = HashSet::new();
 
-            match vcx.ccx.coherence_info.extension_methods.find(&trait_id) {
+            match vcx.ccx.coherence_info.extension_methods.find(&trait_ref.def_id) {
                 None => {
                     // Nothing found. Continue.
                 }
                 Some(implementations) => {
                     let implementations: &mut ~[@Impl] = *implementations;
+
                     // implementations is the list of all impls in scope for
-                    // trait_ty. (Usually, there's just one.)
+                    // trait_ref. (Usually, there's just one.)
                     for uint::range(0, implementations.len()) |i| {
                         let im = implementations[i];
 
-                        // im is one specific impl of trait_ty.
+                        // im is one specific impl of trait_ref.
 
                         // First, ensure we haven't processed this impl yet.
                         if impls_seen.contains(&im.did) {
@@ -269,22 +280,15 @@ pub fn lookup_vtable(vcx: &VtableContext,
                         //   ~[baz<int>, bar, quux]
                         //
                         // For each of the traits foo implements, if
-                        // it's the same trait as trait_ty, we need to
-                        // unify it with trait_ty in order to get all
+                        // it's the same trait as trait_ref, we need to
+                        // unify it with trait_ref in order to get all
                         // the ty vars sorted out.
-                        for vec::each(ty::impl_traits(tcx,
-                                                      im.did,
-                                                      trait_store)) |of_ty| {
-                            match ty::get(*of_ty).sty {
-                                ty::ty_trait(id, _, _) => {
-                                    // Not the trait we're looking for
-                                    if id != trait_id { loop; }
-                                }
-                                _ => { /* ok */ }
-                            }
+                        for ty::impl_trait_refs(tcx, im.did).each |&of_trait_ref|
+                        {
+                            if of_trait_ref.def_id != trait_ref.def_id { loop; }
 
-                            // At this point, we know that of_ty is
-                            // the same trait as trait_ty, but
+                            // At this point, we know that of_trait_ref is
+                            // the same trait as trait_ref, but
                             // possibly applied to different substs.
                             //
                             // Next, we check whether the "for" ty in
@@ -318,39 +322,36 @@ pub fn lookup_vtable(vcx: &VtableContext,
                                    vcx.infcx.ty_to_str(for_ty),
                                    tys_to_str(vcx.tcx(), substs.tps));
 
-                            // Next, we unify trait_ty -- the type
-                            // that we want to cast to -- with of_ty
+                            // Next, we unify trait_ref -- the type
+                            // that we want to cast to -- with of_trait_ref
                             // -- the trait that im implements. At
                             // this point, we require that they be
                             // unifiable with each other -- that's
-                            // what relate_trait_tys does.
+                            // what relate_trait_refs does.
                             //
                             // For example, in the above example,
-                            // of_ty would be some_trait<T>, so we
-                            // would be unifying trait_ty<U> (for some
+                            // of_trait_ref would be some_trait<T>, so we
+                            // would be unifying trait_ref<U> (for some
                             // value of U) with some_trait<T>. This
                             // would fail if T and U weren't
                             // compatible.
 
                             debug!("(checking vtable) @2 relating trait \
-                                    ty %s to of_ty %s",
-                                   vcx.infcx.ty_to_str(trait_ty),
-                                   vcx.infcx.ty_to_str(*of_ty));
-                            let of_ty = ty::subst(tcx, &substs, *of_ty);
-                            relate_trait_tys(vcx, location_info, trait_ty,
-                                             of_ty);
-
-                            // Recall that trait_ty -- the trait type
-                            // we're casting to -- is the trait with
-                            // id trait_id applied to the substs
-                            // trait_substs. Now we extract out the
-                            // types themselves from trait_substs.
+                                    ty %s to of_trait_ref %s",
+                                   vcx.infcx.trait_ref_to_str(trait_ref),
+                                   vcx.infcx.trait_ref_to_str(of_trait_ref));
 
-                            let trait_tps = /*bad*/copy trait_substs.tps;
+                            let of_trait_ref =
+                                ty::subst_in_trait_ref(tcx, &substs, of_trait_ref);
+                            relate_trait_refs(
+                                vcx, location_info,
+                                &of_trait_ref, trait_ref);
 
-                            debug!("Casting to a trait ty whose substs \
-                                    (trait_tps) are %s",
-                                   tys_to_str(vcx.tcx(), trait_tps));
+                            // Recall that trait_ref -- the trait type
+                            // we're casting to -- is the trait with
+                            // id trait_ref.def_id applied to the substs
+                            // trait_ref.substs. Now we extract out the
+                            // types themselves from trait_ref.substs.
 
                             // Recall that substs is the impl self
                             // type's list of substitutions. That is,
@@ -362,7 +363,7 @@ pub fn lookup_vtable(vcx: &VtableContext,
 
                             let substs_f = match fixup_substs(vcx,
                                                               location_info,
-                                                              trait_id,
+                                                              trait_ref.def_id,
                                                               substs,
                                                               is_early) {
                                 Some(ref substs) => (/*bad*/copy *substs),
@@ -377,7 +378,7 @@ pub fn lookup_vtable(vcx: &VtableContext,
                                     they will be unified with the bounds for \
                                     the target ty, %s",
                                    tys_to_str(vcx.tcx(), substs_f.tps),
-                                   tys_to_str(vcx.tcx(), trait_tps));
+                                   vcx.infcx.trait_ref_to_str(trait_ref));
 
                             // Next, we unify the fixed-up
                             // substitutions for the impl self ty with
@@ -386,14 +387,13 @@ pub fn lookup_vtable(vcx: &VtableContext,
                             // to. connect_trait_tps requires these
                             // lists of types to unify pairwise.
 
-                            let im_bs = ty::lookup_item_type(tcx,
-                                                             im.did).bounds;
+                            let im_bs =
+                                ty::lookup_item_type(tcx, im.did).generics.bounds;
                             connect_trait_tps(vcx,
                                               location_info,
-                                              /*bad*/copy substs_f.tps,
-                                              trait_tps,
-                                              im.did,
-                                              trait_store);
+                                              &substs_f,
+                                              trait_ref,
+                                              im.did);
                             let subres = lookup_vtables(
                                 vcx, location_info, im_bs, &substs_f,
                                 is_early);
@@ -430,10 +430,10 @@ pub fn lookup_vtable(vcx: &VtableContext,
     return None;
 }
 
-pub fn fixup_ty(vcx: &VtableContext,
-                location_info: &LocationInfo,
-                ty: ty::t,
-                is_early: bool) -> Option<ty::t> {
+fn fixup_ty(vcx: &VtableContext,
+            location_info: &LocationInfo,
+            ty: ty::t,
+            is_early: bool) -> Option<ty::t> {
     let tcx = vcx.tcx();
     match resolve_type(vcx.infcx, ty, resolve_and_force_all_but_regions) {
         Ok(new_type) => Some(new_type),
@@ -450,45 +450,23 @@ pub fn fixup_ty(vcx: &VtableContext,
     }
 }
 
-// Version of demand::suptype() that takes a vtable context instead of a
-// function context.
-pub fn demand_suptype(vcx: &VtableContext, sp: span, e: ty::t, a: ty::t) {
-    // NB: Order of actual, expected is reversed.
-    match infer::mk_subty(vcx.infcx, false, sp, a, e) {
-        result::Ok(()) => {} // Ok.
-        result::Err(ref err) => {
-            vcx.infcx.report_mismatched_types(sp, e, a, err);
-        }
-    }
-}
-
-pub fn connect_trait_tps(vcx: &VtableContext,
-                         location_info: &LocationInfo,
-                         impl_tys: ~[ty::t],
-                         trait_tys: ~[ty::t],
-                         impl_did: ast::def_id,
-                         store: ty::TraitStore) {
+fn connect_trait_tps(vcx: &VtableContext,
+                     location_info: &LocationInfo,
+                     impl_substs: &ty::substs,
+                     trait_ref: &ty::TraitRef,
+                     impl_did: ast::def_id)
+{
     let tcx = vcx.tcx();
 
     // XXX: This should work for multiple traits.
-    let ity = ty::impl_traits(tcx, impl_did, store)[0];
-    let trait_ty = ty::subst_tps(tcx, impl_tys, None, ity);
-    debug!("(connect trait tps) trait type is %?, impl did is %?",
-           ty::get(trait_ty).sty, impl_did);
-    match ty::get(trait_ty).sty {
-     ty::ty_trait(_, ref substs, _) => {
-         for vec::each2((*substs).tps, trait_tys) |a, b| {
-            demand_suptype(vcx, location_info.span, *a, *b);
-         }
-      }
-     _ => tcx.sess.impossible_case(location_info.span, "connect_trait_tps: \
-            don't know how to handle a non-trait ty")
-    }
+    let impl_trait_ref = ty::impl_trait_refs(tcx, impl_did)[0];
+    let impl_trait_ref = ty::subst_in_trait_ref(tcx, impl_substs, impl_trait_ref);
+    relate_trait_refs(vcx, location_info, trait_ref, &impl_trait_ref);
 }
 
-pub fn insert_vtables(fcx: @mut FnCtxt,
-                      callee_id: ast::node_id,
-                      vtables: vtable_res) {
+fn insert_vtables(fcx: @mut FnCtxt,
+                  callee_id: ast::node_id,
+                  vtables: vtable_res) {
     debug!("insert_vtables(callee_id=%d, vtables=%?)",
            callee_id, vtables.map(|v| v.to_str(fcx.tcx())));
     fcx.inh.vtable_map.insert(callee_id, vtables);
@@ -517,15 +495,15 @@ pub fn early_resolve_expr(ex: @ast::expr,
             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(/*bad*/copy *item_ty.bounds) {
-                for item_ty.bounds.each |bounds| {
+            if has_trait_bounds(/*bad*/copy *item_ty.generics.bounds) {
+                for item_ty.generics.bounds.each |bounds| {
                     debug!("early_resolve_expr: looking up vtables for bound \
                             %s",
                            ty::param_bounds_to_str(fcx.tcx(), *bounds));
                 }
                 let vcx = VtableContext { ccx: fcx.ccx, infcx: fcx.infcx() };
                 let vtbls = lookup_vtables(&vcx, &location_info_for_expr(ex),
-                                           item_ty.bounds, substs, is_early);
+                                           item_ty.generics.bounds, substs, is_early);
                 if !is_early {
                     insert_vtables(fcx, ex.id, vtbls);
                 }
@@ -564,7 +542,7 @@ pub fn early_resolve_expr(ex: @ast::expr,
       ast::expr_cast(src, _) => {
           let target_ty = fcx.expr_ty(ex);
           match ty::get(target_ty).sty {
-              ty::ty_trait(_, _, store) => {
+              ty::ty_trait(target_def_id, ref target_substs, store) => {
                   // Look up vtables for the type we're casting to,
                   // passing in the source and target type.  The source
                   // must be a pointer type suitable to the object sigil,
@@ -573,7 +551,6 @@ pub fn early_resolve_expr(ex: @ast::expr,
                                                       fcx.expr_ty(src));
                   match (&ty::get(ty).sty, store) {
                       (&ty::ty_box(mt), ty::BoxTraitStore) |
-                      // XXX: Bare trait store is deprecated.
                       (&ty::ty_uniq(mt), ty::UniqTraitStore) |
                       (&ty::ty_rptr(_, mt), ty::RegionTraitStore(*)) => {
                           let location_info =
@@ -582,11 +559,15 @@ pub fn early_resolve_expr(ex: @ast::expr,
                               ccx: fcx.ccx,
                               infcx: fcx.infcx()
                           };
+                          let target_trait_ref = ty::TraitRef {
+                              def_id: target_def_id,
+                              substs: copy *target_substs
+                          };
                           let vtable_opt =
                               lookup_vtable(&vcx,
                                             location_info,
                                             mt.ty,
-                                            target_ty,
+                                            &target_trait_ref,
                                             is_early);
                           match vtable_opt {
                               Some(vtable) => {
@@ -622,11 +603,12 @@ pub fn early_resolve_expr(ex: @ast::expr,
                           }
                       }
 
-                      (_, ty::BareTraitStore) => {
+                      (_, ty::UniqTraitStore) => {
                           fcx.ccx.tcx.sess.span_err(
                               ex.span,
-                              ~"a sigil (`@`, `~`, or `&`) must be specified \
-                                when casting to a trait");
+                              fmt!("can only cast an ~-pointer \
+                                    to a ~-object, not a %s",
+                                   ty::ty_sort_str(fcx.tcx(), ty)));
                       }
 
                       (_, ty::BoxTraitStore) => {
@@ -637,14 +619,6 @@ pub fn early_resolve_expr(ex: @ast::expr,
                                    ty::ty_sort_str(fcx.tcx(), ty)));
                       }
 
-                      (_, ty::UniqTraitStore) => {
-                          fcx.ccx.tcx.sess.span_err(
-                              ex.span,
-                              fmt!("can only cast an ~-pointer \
-                                    to a ~-object, not a %s",
-                                   ty::ty_sort_str(fcx.tcx(), ty)));
-                      }
-
                       (_, ty::RegionTraitStore(_)) => {
                           fcx.ccx.tcx.sess.span_err(
                               ex.span,
@@ -661,9 +635,9 @@ pub fn early_resolve_expr(ex: @ast::expr,
     }
 }
 
-pub fn resolve_expr(ex: @ast::expr,
-                    &&fcx: @mut FnCtxt,
-                    v: visit::vt<@mut FnCtxt>) {
+fn resolve_expr(ex: @ast::expr,
+                &&fcx: @mut FnCtxt,
+                v: visit::vt<@mut FnCtxt>) {
     early_resolve_expr(ex, fcx, false);
     visit::visit_expr(ex, fcx, v);
 }
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index 22b6926e9f0..f6042cf2e0c 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -358,7 +358,7 @@ pub impl CoherenceChecker {
                 @ProvidedMethodInfo {
                     method_info: @MethodInfo {
                         did: new_did,
-                        n_tps: trait_method.tps.len(),
+                        n_tps: trait_method.generics.bounds.len(),
                         ident: trait_method.ident,
                         self_type: trait_method.self_ty
                     },
@@ -542,10 +542,10 @@ pub impl CoherenceChecker {
                                   -> UniversalQuantificationResult {
         // NDM--this span is bogus.
         let self_region =
-            polytype.region_param.map(
+            polytype.generics.region_param.map(
                 |_r| self.inference_context.next_region_var_nb(dummy_sp()));
 
-        let bounds_count = polytype.bounds.len();
+        let bounds_count = polytype.generics.bounds.len();
         let type_parameters =
             self.inference_context.next_ty_vars(bounds_count);
 
@@ -565,7 +565,7 @@ pub impl CoherenceChecker {
         UniversalQuantificationResult {
             monotype: monotype,
             type_variables: type_parameters,
-            bounds: polytype.bounds
+            bounds: polytype.generics.bounds
         }
     }
 
@@ -864,17 +864,8 @@ pub impl CoherenceChecker {
             }
 
             // Record all the trait methods.
-            for associated_traits.each |trait_type| {
-                match get(*trait_type).sty {
-                    ty_trait(trait_id, _, _) => {
-                        self.add_trait_method(trait_id, *implementation);
-                    }
-                    _ => {
-                        self.crate_context.tcx.sess.bug(~"trait type \
-                                                          returned is not a \
-                                                          trait");
-                    }
-                }
+            for associated_traits.each |trait_ref| {
+                self.add_trait_method(trait_ref.def_id, *implementation);
             }
 
             // Add the implementation to the mapping from
@@ -923,7 +914,7 @@ pub impl CoherenceChecker {
                 @ProvidedMethodInfo {
                     method_info: @MethodInfo {
                         did: new_did,
-                        n_tps: trait_method_info.ty.tps.len(),
+                        n_tps: trait_method_info.ty.generics.bounds.len(),
                         ident: trait_method_info.ty.ident,
                         self_type: trait_method_info.ty.self_ty
                     },
@@ -954,15 +945,7 @@ pub impl CoherenceChecker {
                                                   def_id);
                     }
                     dl_def(def_trait(def_id)) => {
-                        let tcx = self.crate_context.tcx;
-                        let polytype = csearch::get_type(tcx, def_id);
-                        match ty::get(polytype.ty).sty {
-                            ty::ty_trait(*) => {
-                                self.add_default_methods_for_external_trait(
-                                    def_id);
-                            }
-                            _ => {}
-                        }
+                        self.add_default_methods_for_external_trait(def_id);
                     }
                     dl_def(_) | dl_impl(_) | dl_field => {
                         // Skip this.
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index 81acae1d3a9..a2245dc82cf 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -33,7 +33,6 @@ are represented as `ty_param()` instances.
 use core::prelude::*;
 
 use metadata::csearch;
-use middle::ty::InstantiatedTraitRef;
 use middle::ty::{substs, ty_param_bounds_and_ty, ty_param_substs_and_ty};
 use middle::ty;
 use middle::typeck::astconv::{AstConv, ty_of_arg};
@@ -83,12 +82,10 @@ pub fn collect_item_types(ccx: @mut CrateCtxt, crate: @ast::crate) {
 
                     match intrinsic_item.node {
                       ast::item_trait(*) => {
-                        let ty = ty::mk_trait(ccx.tcx,
-                                              def_id,
-                                              substs,
-                                              ty::BareTraitStore);
-                        ccx.tcx.intrinsic_defs.insert
-                            (intrinsic_item.ident, (def_id, ty));
+                          let tref = @ty::TraitRef {def_id: def_id,
+                                                    substs: substs};
+                          ccx.tcx.intrinsic_traits.insert
+                              (intrinsic_item.ident, tref);
                       }
 
                       ast::item_enum(*) => {
@@ -152,6 +149,10 @@ impl AstConv for CrateCtxt {
         }
     }
 
+    fn get_trait_def(&self, id: ast::def_id) -> @ty::TraitDef {
+        get_trait_def(self, id)
+    }
+
     fn ty_infer(&self, span: span) -> ty::t {
         self.tcx.sess.span_bug(span,
                                ~"found `ty_infer` in unexpected place");
@@ -186,8 +187,7 @@ pub fn get_enum_variant_types(ccx: &CrateCtxt,
 
             ast::struct_variant_kind(struct_def) => {
                 let tpt = ty_param_bounds_and_ty {
-                    bounds: ty_param_bounds(ccx, generics),
-                    region_param: rp,
+                    generics: ty_generics(ccx, rp, generics),
                     ty: enum_ty
                 };
 
@@ -208,8 +208,7 @@ pub fn get_enum_variant_types(ccx: &CrateCtxt,
             None => {}
             Some(result_ty) => {
                 let tpt = ty_param_bounds_and_ty {
-                    bounds: ty_param_bounds(ccx, generics),
-                    region_param: rp,
+                    generics: ty_generics(ccx, rp, generics),
                     ty: result_ty
                 };
                 tcx.tcache.insert(local_def(variant.node.id), tpt);
@@ -220,8 +219,7 @@ pub fn get_enum_variant_types(ccx: &CrateCtxt,
 }
 
 pub fn ensure_trait_methods(ccx: &CrateCtxt,
-                            trait_id: ast::node_id,
-                            trait_ty: ty::t)
+                            trait_id: ast::node_id)
 {
     let tcx = ccx.tcx;
     let region_paramd = tcx.region_paramd_items.find(&trait_id).map(|&x| *x);
@@ -230,7 +228,7 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
             node: ast::item_trait(ref generics, _, ref ms),
             _
         }, _) => {
-            let trait_bounds = ty_param_bounds(ccx, generics);
+            let trait_ty_generics = ty_generics(ccx, region_paramd, generics);
 
             // For each method, construct a suitable ty::method and
             // store it into the `tcx.methods` table:
@@ -252,9 +250,8 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
                 };
 
                 if ty_method.self_ty == ast::sty_static {
-                    make_static_method_ty(ccx, region_paramd,
-                                          ty_method, trait_ty,
-                                          trait_bounds);
+                    make_static_method_ty(ccx, trait_id, ty_method,
+                                          &trait_ty_generics);
                 }
 
                 tcx.methods.insert(ty_method.def_id, ty_method);
@@ -275,12 +272,9 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
     }
 
     fn make_static_method_ty(ccx: &CrateCtxt,
-                             rp: Option<ty::region_variance>,
+                             trait_id: ast::node_id,
                              m: &ty::method,
-                             // Take this as an argument b/c we may check
-                             // the impl before the trait.
-                             trait_ty: ty::t,
-                             trait_bounds: @~[ty::param_bounds]) {
+                             trait_ty_generics: &ty::Generics) {
         // We need to create a typaram that replaces self. This param goes
         // *in between* the typarams from the trait and those from the
         // method (since its bound can depend on the trait? or
@@ -291,12 +285,13 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
 
         let dummy_defid = ast::def_id {crate: 0, node: 0};
 
-        let non_shifted_trait_tps = do vec::from_fn(trait_bounds.len()) |i| {
+        let num_trait_bounds = trait_ty_generics.bounds.len();
+        let non_shifted_trait_tps = do vec::from_fn(num_trait_bounds) |i| {
             ty::mk_param(ccx.tcx, i, dummy_defid)
         };
-        let self_param = ty::mk_param(ccx.tcx, trait_bounds.len(),
+        let self_param = ty::mk_param(ccx.tcx, num_trait_bounds,
                                       dummy_defid);
-        let shifted_method_tps = do vec::from_fn(m.tps.len()) |i| {
+        let shifted_method_tps = do vec::from_fn(m.generics.bounds.len()) |i| {
             ty::mk_param(ccx.tcx, i + 1, dummy_defid)
         };
 
@@ -308,13 +303,20 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
         let ty = ty::subst(ccx.tcx,
                            &substs,
                            ty::mk_bare_fn(ccx.tcx, copy m.fty));
-        let bounds = @(*trait_bounds + ~[@~[ty::bound_trait(trait_ty)]]
-                       + *m.tps);
+        let trait_def = get_trait_def(ccx, local_def(trait_id));
+        let trait_ref = trait_def.trait_ref;
+        let mut new_bounds = ~[];
+        new_bounds.push_all(*trait_ty_generics.bounds);
+        new_bounds.push(@~[ty::bound_trait(trait_ref)]);
+        new_bounds.push_all(*m.generics.bounds);
         ccx.tcx.tcache.insert(m.def_id,
                               ty_param_bounds_and_ty {
-                                bounds: bounds,
-                                region_param: rp,
-                                ty: ty});
+                                  generics: ty::Generics {
+                                      bounds: @new_bounds,
+                                      region_param: trait_ty_generics.region_param
+                                  },
+                                  ty: ty
+                              });
     }
 
     fn ty_method_of_trait_method(self: &CrateCtxt,
@@ -335,7 +337,7 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
                                   trait_self_ty, *m_self_ty, m_decl);
         ty::method {
             ident: *m_ident,
-            tps: ty_param_bounds(self, m_generics),
+            generics: ty_generics(self, None, m_generics),
             transformed_self_ty: transformed_self_ty,
             fty: fty,
             self_ty: m_self_ty.node,
@@ -350,25 +352,28 @@ pub fn ensure_supertraits(ccx: &CrateCtxt,
                           id: ast::node_id,
                           sp: codemap::span,
                           rp: Option<ty::region_variance>,
-                          trait_refs: &[@ast::trait_ref],
-                          generics: &ast::Generics) {
+                          ast_trait_refs: &[@ast::trait_ref],
+                          generics: &ast::Generics)
+{
     let tcx = ccx.tcx;
     if tcx.supertraits.contains_key(&local_def(id)) { return; }
 
-    let mut instantiated = ~[];
-    for trait_refs.each |trait_ref| {
-        let (did, tpt) = instantiate_trait_ref(ccx, *trait_ref, rp, generics);
-        if instantiated.any(|other_trait: &InstantiatedTraitRef|
-                            { other_trait.def_id == did }) {
+    let mut ty_trait_refs: ~[@ty::TraitRef] = ~[];
+    for ast_trait_refs.each |&ast_trait_ref| {
+        let trait_ref = instantiate_trait_ref(ccx, ast_trait_ref, rp, generics);
+
+        // NOTE Could have same trait multiple times
+        if ty_trait_refs.any(|other_trait| other_trait.def_id == trait_ref.def_id) {
             // This means a trait inherited from the same supertrait more
             // than once.
             tcx.sess.span_err(sp, ~"Duplicate supertrait in trait \
                                      declaration");
-            return;
+            break;
+        } else {
+            ty_trait_refs.push(trait_ref);
         }
-        instantiated.push(InstantiatedTraitRef { def_id: did, tpt: tpt });
     }
-    tcx.supertraits.insert(local_def(id), @instantiated);
+    tcx.supertraits.insert(local_def(id), @ty_trait_refs);
 }
 
 /**
@@ -422,15 +427,15 @@ pub fn compare_impl_method(tcx: ty::ctxt,
         }
     }
 
-    if impl_m.tps.len() != trait_m.tps.len() {
+    if impl_m.generics.bounds.len() != trait_m.generics.bounds.len() {
         tcx.sess.span_err(
             cm.span,
             fmt!("method `%s` has %u type %s, but its trait \
                   declaration has %u type %s",
-                 *tcx.sess.str_of(trait_m.ident), impl_m.tps.len(),
-                 pluralize(impl_m.tps.len(), ~"parameter"),
-                 trait_m.tps.len(),
-                 pluralize(trait_m.tps.len(), ~"parameter")));
+                 *tcx.sess.str_of(trait_m.ident), impl_m.generics.bounds.len(),
+                 pluralize(impl_m.generics.bounds.len(), ~"parameter"),
+                 trait_m.generics.bounds.len(),
+                 pluralize(trait_m.generics.bounds.len(), ~"parameter")));
         return;
     }
 
@@ -448,9 +453,9 @@ pub fn compare_impl_method(tcx: ty::ctxt,
     // FIXME(#2687)---we should be checking that the bounds of the
     // trait imply the bounds of the subtype, but it appears
     // we are...not checking this.
-    for trait_m.tps.eachi() |i, trait_param_bounds| {
+    for trait_m.generics.bounds.eachi() |i, trait_param_bounds| {
         // For each of the corresponding impl ty param's bounds...
-        let impl_param_bounds = impl_m.tps[i];
+        let impl_param_bounds = impl_m.generics.bounds[i];
         // Make sure the bounds lists have the same length
         // Would be nice to use the ty param names in the error message,
         // but we don't have easy access to them here
@@ -490,7 +495,7 @@ pub fn compare_impl_method(tcx: ty::ctxt,
     };
     debug!("impl_fty: %s", ppaux::ty_to_str(tcx, impl_fty));
     let trait_fty = {
-        let dummy_tps = do vec::from_fn((*trait_m.tps).len()) |i| {
+        let dummy_tps = do vec::from_fn(trait_m.generics.bounds.len()) |i| {
             // hack: we don't know the def id of the impl tp, but it
             // is not important for unification
             ty::mk_param(tcx, i + impl_tps, ast::def_id {crate: 0, node: 0})
@@ -538,37 +543,23 @@ pub fn check_methods_against_trait(ccx: &CrateCtxt,
                                    impl_ms: &[ConvertedMethod])
 {
     let tcx = ccx.tcx;
-    let (did, tpt) = instantiate_trait_ref(ccx, a_trait_ty, rp, generics);
-
-    if did.crate == ast::local_crate {
-        // NB: This is subtle. We need to do this on the type of the trait
-        // item *itself*, not on the type that includes the parameter
-        // substitutions provided by the programmer at this particular
-        // trait ref. Otherwise, we will potentially overwrite the types of
-        // the methods within the trait with bogus results. (See issue #3903.)
-
-        match tcx.items.find(&did.node) {
-            Some(&ast_map::node_item(item, _)) => {
-                let tpt = ty_of_item(ccx, item);
-                ensure_trait_methods(ccx, did.node, tpt.ty);
-            }
-            _ => {
-                tcx.sess.bug(~"trait ref didn't resolve to trait");
-            }
-        }
+    let trait_ref = instantiate_trait_ref(ccx, a_trait_ty, rp, generics);
+
+    if trait_ref.def_id.crate == ast::local_crate {
+        ensure_trait_methods(ccx, trait_ref.def_id.node);
     }
 
     // Check that each method we impl is a method on the trait
     // Trait methods we don't implement must be default methods, but if not
     // we'll catch it in coherence
-    let trait_ms = ty::trait_methods(tcx, did);
+    let trait_ms = ty::trait_methods(tcx, trait_ref.def_id);
     for impl_ms.each |impl_m| {
         match trait_ms.find(|trait_m| trait_m.ident == impl_m.mty.ident) {
             Some(trait_m) => {
                 let num_impl_tps = generics.ty_params.len();
                 compare_impl_method(
                     ccx.tcx, num_impl_tps, impl_m, trait_m,
-                    &tpt.substs, selfty);
+                    &trait_ref.substs, selfty);
             }
             None => {
                 // This method is not part of the trait
@@ -594,8 +585,10 @@ pub fn convert_field(ccx: &CrateCtxt,
     /* add the field to the tcache */
     ccx.tcx.tcache.insert(local_def(v.node.id),
                           ty::ty_param_bounds_and_ty {
-                              bounds: bounds,
-                              region_param: rp,
+                              generics: ty::Generics {
+                                  bounds: bounds,
+                                  region_param: rp
+                              },
                               ty: tt
                           });
 }
@@ -609,28 +602,34 @@ pub struct ConvertedMethod {
 
 pub fn convert_methods(ccx: &CrateCtxt,
                        ms: &[@ast::method],
-                       rp: Option<ty::region_variance>,
                        untransformed_rcvr_ty: ty::t,
-                       rcvr_bounds: @~[ty::param_bounds],
-                       rcvr_generics: &ast::Generics,
+                       rcvr_ty_generics: &ty::Generics,
+                       rcvr_ast_generics: &ast::Generics,
                        rcvr_visibility: ast::visibility)
                     -> ~[ConvertedMethod]
 {
     let tcx = ccx.tcx;
     return vec::map(ms, |m| {
-        let bounds = ty_param_bounds(ccx, &m.generics);
-        let mty = @ty_of_method(
-            ccx, *m, rp, untransformed_rcvr_ty,
-            rcvr_generics, rcvr_visibility, &m.generics);
-        let fty = ty::mk_bare_fn(tcx, copy mty.fty);
+        let m_ty_generics =
+            ty_generics(ccx, rcvr_ty_generics.region_param, &m.generics);
+        let mty =
+            @ty_of_method(ccx, *m, rcvr_ty_generics.region_param,
+                          untransformed_rcvr_ty,
+                          rcvr_ast_generics, rcvr_visibility,
+                          &m.generics);
+        let fty =
+            ty::mk_bare_fn(tcx, copy mty.fty);
         tcx.tcache.insert(
             local_def(m.id),
 
             // n.b.: the type of a method is parameterized by both
             // the tps on the receiver and those on the method itself
             ty_param_bounds_and_ty {
-                bounds: @(vec::append(/*bad*/copy *rcvr_bounds, *bounds)),
-                region_param: rp,
+                generics: ty::Generics {
+                    bounds: @(vec::append(copy *rcvr_ty_generics.bounds,
+                                          *m_ty_generics.bounds)),
+                    region_param: rcvr_ty_generics.region_param
+                },
                 ty: fty
             });
         write_ty_to_tcx(tcx, m.id, fty);
@@ -657,7 +656,7 @@ pub fn convert_methods(ccx: &CrateCtxt,
                                   m.self_ty, &m.decl);
         ty::method {
             ident: m.ident,
-            tps: ty_param_bounds(ccx, &m.generics),
+            generics: ty_generics(ccx, None, &m.generics),
             transformed_self_ty: transformed_self_ty,
             fty: fty,
             self_ty: m.self_ty.node,
@@ -700,16 +699,15 @@ pub fn convert(ccx: &CrateCtxt, it: @ast::item) {
                                rp);
       }
       ast::item_impl(ref generics, opt_trait_ref, selfty, ref ms) => {
-        let i_bounds = ty_param_bounds(ccx, generics);
+        let i_ty_generics = ty_generics(ccx, rp, generics);
         let region_parameterization =
             RegionParameterization::from_variance_and_generics(rp, generics);
         let selfty = ccx.to_ty(&type_rscope(region_parameterization), selfty);
         write_ty_to_tcx(tcx, it.id, selfty);
         tcx.tcache.insert(local_def(it.id),
                           ty_param_bounds_and_ty {
-                            bounds: i_bounds,
-                            region_param: rp,
-                            ty: selfty});
+                              generics: i_ty_generics,
+                              ty: selfty});
 
         // If there is a trait reference, treat the methods as always public.
         // This is to work around some incorrect behavior in privacy checking:
@@ -722,27 +720,27 @@ pub fn convert(ccx: &CrateCtxt, it: @ast::item) {
             it.vis
         };
 
-        let cms = convert_methods(ccx, *ms, rp, selfty, i_bounds, generics,
+        let cms = convert_methods(ccx, *ms, selfty,
+                                  &i_ty_generics, generics,
                                   parent_visibility);
         for opt_trait_ref.each |t| {
             check_methods_against_trait(ccx, generics, rp, selfty, *t, cms);
         }
       }
       ast::item_trait(ref generics, ref supertraits, ref trait_methods) => {
-        let tpt = ty_of_item(ccx, it);
-        debug!("item_trait(it.id=%d, tpt.ty=%s)",
-               it.id, ppaux::ty_to_str(tcx, tpt.ty));
-        write_ty_to_tcx(tcx, it.id, tpt.ty);
-        ensure_trait_methods(ccx, it.id, tpt.ty);
-        ensure_supertraits(ccx, it.id, it.span, rp, *supertraits, generics);
-
-        let (_, provided_methods) =
-            split_trait_methods(*trait_methods);
-        let (bounds, _) = mk_substs(ccx, generics, rp);
-        let untransformed_rcvr_ty = ty::mk_self(tcx, local_def(it.id));
-        let _ = convert_methods(ccx, provided_methods, rp,
-                                untransformed_rcvr_ty, bounds, generics,
-                                it.vis);
+          let trait_def = trait_def_of_item(ccx, it);
+          tcx.trait_defs.insert(local_def(it.id), trait_def);
+          ensure_trait_methods(ccx, it.id);
+          ensure_supertraits(ccx, it.id, it.span, rp, *supertraits, generics);
+
+          let (_, provided_methods) =
+              split_trait_methods(*trait_methods);
+          let (ty_generics, _) = mk_substs(ccx, generics, rp);
+          let untransformed_rcvr_ty = ty::mk_self(tcx, local_def(it.id));
+          let _ = convert_methods(ccx, provided_methods,
+                                  untransformed_rcvr_ty,
+                                  &ty_generics, generics,
+                                  it.vis);
       }
       ast::item_struct(struct_def, ref generics) => {
         ensure_no_ty_param_bounds(ccx, it.span, generics, "structure");
@@ -794,14 +792,16 @@ pub fn convert_struct(ccx: &CrateCtxt,
         write_ty_to_tcx(tcx, dtor.node.id, t_dtor);
         tcx.tcache.insert(local_def(dtor.node.id),
                           ty_param_bounds_and_ty {
-                            bounds: tpt.bounds,
-                            region_param: rp,
-                            ty: t_dtor});
+                              generics: ty::Generics {
+                                  bounds: tpt.generics.bounds,
+                                  region_param: rp
+                              },
+                              ty: t_dtor});
     };
 
     // Write the type of each of the members
     for struct_def.fields.each |f| {
-       convert_field(ccx, rp, tpt.bounds, *f, generics);
+       convert_field(ccx, rp, tpt.generics.bounds, *f, generics);
     }
     let (_, substs) = mk_substs(ccx, generics, rp);
     let selfty = ty::mk_struct(tcx, local_def(id), substs);
@@ -824,8 +824,7 @@ pub fn convert_struct(ccx: &CrateCtxt,
                 let ctor_fn_ty = ty::mk_ctor_fn(tcx, inputs, selfty);
                 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
                 tcx.tcache.insert(local_def(ctor_id), ty_param_bounds_and_ty {
-                    bounds: tpt.bounds,
-                    region_param: tpt.region_param,
+                    generics: tpt.generics,
                     ty: ctor_fn_ty
                 });
             }
@@ -842,38 +841,75 @@ pub fn convert_foreign(ccx: &CrateCtxt, i: @ast::foreign_item) {
     ccx.tcx.tcache.insert(local_def(i.id), tpt);
 }
 
-/*
-  Instantiates the path for the given trait reference, assuming that
-  it's bound to a valid trait type. Returns the def_id for the defining
-  trait. Fails if the type is a type other than an trait type.
- */
 pub fn instantiate_trait_ref(ccx: &CrateCtxt,
-                             t: @ast::trait_ref,
+                             ast_trait_ref: @ast::trait_ref,
                              rp: Option<ty::region_variance>,
-                             generics: &ast::Generics)
-    -> (ast::def_id, ty_param_substs_and_ty) {
-
-    let sp = t.path.span, err = ~"can only implement trait types",
-        sess = ccx.tcx.sess;
+                             generics: &ast::Generics) -> @ty::TraitRef
+{
+    /*!
+     * Instantiates the path for the given trait reference, assuming that
+     * it's bound to a valid trait type. Returns the def_id for the defining
+     * trait. Fails if the type is a type other than an trait type.
+     */
 
     let rp = RegionParameterization::from_variance_and_generics(rp, generics);
 
     let rscope = type_rscope(rp);
 
-    match lookup_def_tcx(ccx.tcx, t.path.span, t.ref_id) {
-      ast::def_trait(t_id) => {
-        let tpt = astconv::ast_path_to_ty(ccx, &rscope, t_id, t.path);
+    match lookup_def_tcx(ccx.tcx, ast_trait_ref.path.span, ast_trait_ref.ref_id) {
+        ast::def_trait(trait_did) => {
+            let trait_ref =
+                astconv::ast_path_to_trait_ref(
+                    ccx, &rscope, trait_did, ast_trait_ref.path);
+            ccx.tcx.trait_refs.insert(
+                ast_trait_ref.ref_id, trait_ref);
+            return trait_ref;
+        }
+        _ => {
+            ccx.tcx.sess.span_fatal(
+                ast_trait_ref.path.span,
+                fmt!("%s is not a trait",
+                    path_to_str(ast_trait_ref.path,
+                                ccx.tcx.sess.intr())));
+        }
+    }
+}
 
-        write_tpt_to_tcx(ccx.tcx, t.ref_id, &tpt);
+fn get_trait_def(ccx: &CrateCtxt, trait_id: ast::def_id) -> @ty::TraitDef {
+    if trait_id.crate != ast::local_crate {
+        ty::lookup_trait_def(ccx.tcx, trait_id)
+    } else {
+        match ccx.tcx.items.get(&trait_id.node) {
+            &ast_map::node_item(item, _) => trait_def_of_item(ccx, item),
+            _ => ccx.tcx.sess.bug(fmt!("get_trait_def(%d): not an item",
+                                       trait_id.node))
+        }
+    }
+}
 
-        match ty::get(tpt.ty).sty {
-           ty::ty_trait(*) => {
-              (t_id, tpt)
-           }
-           _ => sess.span_fatal(sp, err),
+pub fn trait_def_of_item(ccx: &CrateCtxt, it: @ast::item) -> @ty::TraitDef {
+    let def_id = local_def(it.id);
+    let tcx = ccx.tcx;
+    match tcx.trait_defs.find(&def_id) {
+      Some(&def) => return def,
+      _ => {}
+    }
+    let rp = tcx.region_paramd_items.find(&it.id).map_consume(|x| *x);
+    match it.node {
+        ast::item_trait(ref generics, _, _) => {
+            let (ty_generics, substs) = mk_substs(ccx, generics, rp);
+            let trait_ref = @ty::TraitRef {def_id: def_id,
+                                           substs: substs};
+            let trait_def = @ty::TraitDef {generics: ty_generics,
+                                           trait_ref: trait_ref};
+            tcx.trait_defs.insert(def_id, trait_def);
+            return trait_def;
+        }
+        ref s => {
+            tcx.sess.span_bug(
+                it.span,
+                fmt!("trait_def_of_item invoked on %?", s));
         }
-      }
-      _ => sess.span_fatal(sp, err)
     }
 }
 
@@ -894,7 +930,8 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: @ast::item)
         return tpt;
       }
       ast::item_fn(ref decl, purity, _, ref generics, _) => {
-        let bounds = ty_param_bounds(ccx, generics);
+        assert!(rp.is_none());
+        let ty_generics = ty_generics(ccx, None, generics);
         let tofd = astconv::ty_of_bare_fn(ccx,
                                           &empty_rscope,
                                           purity,
@@ -902,8 +939,10 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: @ast::item)
                                           &generics.lifetimes,
                                           decl);
         let tpt = ty_param_bounds_and_ty {
-            bounds: bounds,
-            region_param: None,
+            generics: ty::Generics {
+                bounds: ty_generics.bounds,
+                region_param: None
+            },
             ty: ty::mk_bare_fn(ccx.tcx, tofd)
         };
         debug!("type of %s (id %d) is %s",
@@ -934,8 +973,7 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: @ast::item)
                 }
             };
             ty_param_bounds_and_ty {
-                bounds: ty_param_bounds(ccx, generics),
-                region_param: rp,
+                generics: ty_generics(ccx, rp, generics),
                 ty: ty
             }
         };
@@ -945,37 +983,26 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: @ast::item)
       }
       ast::item_enum(_, ref generics) => {
         // Create a new generic polytype.
-        let (bounds, substs) = mk_substs(ccx, generics, rp);
+        let (ty_generics, substs) = mk_substs(ccx, generics, rp);
         let t = ty::mk_enum(tcx, local_def(it.id), substs);
         let tpt = ty_param_bounds_and_ty {
-            bounds: bounds,
-            region_param: rp,
+            generics: ty_generics,
             ty: t
         };
         tcx.tcache.insert(local_def(it.id), tpt);
         return tpt;
       }
-      ast::item_trait(ref generics, _, _) => {
-        let (bounds, substs) = mk_substs(ccx, generics, rp);
-        let t = ty::mk_trait(tcx,
-                             local_def(it.id),
-                             substs,
-                             ty::BareTraitStore);
-        let tpt = ty_param_bounds_and_ty {
-            bounds: bounds,
-            region_param: rp,
-            ty: t
-        };
-        tcx.tcache.insert(local_def(it.id), tpt);
-        return tpt;
+      ast::item_trait(*) => {
+          tcx.sess.span_bug(
+              it.span,
+              fmt!("Invoked ty_of_item on trait"));
       }
       ast::item_struct(_, ref generics) => {
-          let (bounds, substs) = mk_substs(ccx, generics, rp);
+          let (ty_generics, substs) = mk_substs(ccx, generics, rp);
           let t = ty::mk_struct(tcx, local_def(it.id), substs);
           let tpt = ty_param_bounds_and_ty {
-            bounds: bounds,
-            region_param: rp,
-            ty: t
+              generics: ty_generics,
+              ty: t
           };
           tcx.tcache.insert(local_def(it.id), tpt);
           return tpt;
@@ -997,76 +1024,82 @@ pub fn ty_of_foreign_item(ccx: &CrateCtxt, it: @ast::foreign_item)
         }
         ast::foreign_item_const(t) => {
             ty::ty_param_bounds_and_ty {
-                bounds: @~[],
-                region_param: None,
+                generics: ty::Generics {
+                    bounds: @~[],
+                    region_param: None,
+                },
                 ty: ast_ty_to_ty(ccx, &empty_rscope, t)
             }
         }
     }
 }
 
-// Translate the AST's notion of ty param bounds (which are an enum consisting
-// of a newtyped Ty or a region) to ty's notion of ty param bounds, which can
-// either be user-defined traits, or one of the four built-in traits (formerly
-// known as kinds): Const, Copy, Durable, and Send.
-pub fn compute_bounds(ccx: &CrateCtxt,
-                      ast_bounds: @OptVec<ast::TyParamBound>)
-                   -> ty::param_bounds {
-    @ast_bounds.flat_map_to_vec(|b| {
-        match b {
-            &TraitTyParamBound(b) => {
-                let li = &ccx.tcx.lang_items;
-                let ity = ast_ty_to_ty(ccx, &empty_rscope, b);
-                match ty::get(ity).sty {
-                    ty::ty_trait(did, _, _) => {
-                        if did == li.owned_trait() {
-                            ~[ty::bound_owned]
-                        } else if did == li.copy_trait() {
-                            ~[ty::bound_copy]
-                        } else if did == li.const_trait() {
-                            ~[ty::bound_const]
-                        } else if did == li.durable_trait() {
-                            ~[ty::bound_durable]
-                        } else {
-                            // Must be a user-defined trait
-                            ~[ty::bound_trait(ity)]
-                        }
-                    }
-                    _ => {
-                        ccx.tcx.sess.span_err(
-                            (*b).span, ~"type parameter bounds must be \
-                                         trait types");
-                        ~[]
-                    }
+pub fn ty_generics(ccx: &CrateCtxt,
+                   rp: Option<ty::region_variance>,
+                   generics: &ast::Generics) -> ty::Generics {
+    return ty::Generics {
+        region_param: rp,
+        bounds: @generics.ty_params.map_to_vec(|param| {
+            match ccx.tcx.ty_param_bounds.find(&param.id) {
+                Some(&bs) => bs,
+                None => {
+                    let bounds = compute_bounds(ccx, rp, generics, param.bounds);
+                    ccx.tcx.ty_param_bounds.insert(param.id, bounds);
+                    bounds
                 }
             }
-            &RegionTyParamBound => ~[ty::bound_durable]
-        }
-    })
-}
+        })
+    };
 
-pub fn ty_param_bounds(ccx: &CrateCtxt,
-                       generics: &ast::Generics)
-                    -> @~[ty::param_bounds] {
-    @do generics.ty_params.map_to_vec |param| {
-        match ccx.tcx.ty_param_bounds.find(&param.id) {
-          Some(&bs) => bs,
-          None => {
-            let bounds = compute_bounds(ccx, param.bounds);
-            ccx.tcx.ty_param_bounds.insert(param.id, bounds);
-            bounds
-          }
-        }
+    fn compute_bounds(
+        ccx: &CrateCtxt,
+        rp: Option<ty::region_variance>,
+        generics: &ast::Generics,
+        ast_bounds: @OptVec<ast::TyParamBound>) -> ty::param_bounds
+    {
+        /*!
+         *
+         * Translate the AST's notion of ty param bounds (which are an
+         * enum consisting of a newtyped Ty or a region) to ty's
+         * notion of ty param bounds, which can either be user-defined
+         * traits, or one of the four built-in traits (formerly known
+         * as kinds): Const, Copy, Durable, and Send.
+         */
+
+        @ast_bounds.flat_map_to_vec(|b| {
+            match b {
+                &TraitTyParamBound(b) => {
+                    let li = &ccx.tcx.lang_items;
+                    let trait_ref = instantiate_trait_ref(ccx, b, rp, generics);
+                    if trait_ref.def_id == li.owned_trait() {
+                        ~[ty::bound_owned]
+                    } else if trait_ref.def_id == li.copy_trait() {
+                        ~[ty::bound_copy]
+                    } else if trait_ref.def_id == li.const_trait() {
+                        ~[ty::bound_const]
+                    } else if trait_ref.def_id == li.durable_trait() {
+                        ~[ty::bound_durable]
+                    } else {
+                        // Must be a user-defined trait
+                        ~[ty::bound_trait(trait_ref)]
+                    }
+                }
+
+                &RegionTyParamBound => {
+                    ~[ty::bound_durable]
+                }
+            }
+        })
     }
 }
 
 pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
                              decl: &ast::fn_decl,
                              def_id: ast::def_id,
-                             generics: &ast::Generics)
+                             ast_generics: &ast::Generics)
                           -> ty::ty_param_bounds_and_ty {
-    let bounds = ty_param_bounds(ccx, generics);
-    let region_param_names = RegionParamNames::from_generics(generics);
+    let ty_generics = ty_generics(ccx, None, ast_generics);
+    let region_param_names = RegionParamNames::from_generics(ast_generics);
     let rb = in_binding_rscope(&empty_rscope, region_param_names);
     let input_tys = decl.inputs.map(|a| ty_of_arg(ccx, &rb, *a, None) );
     let output_ty = ast_ty_to_ty(ccx, &rb, decl.output);
@@ -1081,33 +1114,24 @@ pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
                             output: output_ty}
         });
     let tpt = ty_param_bounds_and_ty {
-        bounds: bounds,
-        region_param: None,
+        generics: ty_generics,
         ty: t_fn
     };
     ccx.tcx.tcache.insert(def_id, tpt);
     return tpt;
 }
 
-pub fn mk_generics(ccx: &CrateCtxt, generics: &ast::Generics)
-    -> (@~[ty::param_bounds], ~[ty::t])
-{
-    let mut i = 0u;
-    let bounds = ty_param_bounds(ccx, generics);
-    (bounds,
-     generics.ty_params.map_to_vec(|atp| {
-         let t = ty::mk_param(ccx.tcx, i, local_def(atp.id));
-         i += 1u;
-         t
-     }))
-}
-
 pub fn mk_substs(ccx: &CrateCtxt,
-                 generics: &ast::Generics,
-                 rp: Option<ty::region_variance>)
-              -> (@~[ty::param_bounds], ty::substs)
+                 ast_generics: &ast::Generics,
+                 rp: Option<ty::region_variance>) -> (ty::Generics, ty::substs)
 {
-    let (bounds, params) = mk_generics(ccx, generics);
+    let mut i = 0;
+    let ty_generics = ty_generics(ccx, rp, ast_generics);
+    let params = ast_generics.ty_params.map_to_vec(|atp| {
+        let t = ty::mk_param(ccx.tcx, i, local_def(atp.id));
+        i += 1u;
+        t
+    });
     let self_r = rscope::bound_self_region(rp);
-    (bounds, substs { self_r: self_r, self_ty: None, tps: params })
+    (ty_generics, substs {self_r: self_r, self_ty: None, tps: params})
 }
diff --git a/src/librustc/middle/typeck/infer/combine.rs b/src/librustc/middle/typeck/infer/combine.rs
index add70b21e39..69c7b1d616b 100644
--- a/src/librustc/middle/typeck/infer/combine.rs
+++ b/src/librustc/middle/typeck/infer/combine.rs
@@ -90,7 +90,7 @@ pub trait Combine {
     fn tps(&self, as_: &[ty::t], bs: &[ty::t]) -> cres<~[ty::t]>;
     fn self_tys(&self, a: Option<ty::t>, b: Option<ty::t>)
                -> cres<Option<ty::t>>;
-    fn substs(&self, did: ast::def_id, as_: &ty::substs,
+    fn substs(&self, generics: &ty::Generics, as_: &ty::substs,
               bs: &ty::substs) -> cres<ty::substs>;
     fn bare_fn_tys(&self, a: &ty::BareFnTy,
                    b: &ty::BareFnTy) -> cres<ty::BareFnTy>;
@@ -114,6 +114,7 @@ pub trait Combine {
                     a: ty::TraitStore,
                     b: ty::TraitStore)
                  -> cres<ty::TraitStore>;
+    fn trait_refs(&self, a: &ty::TraitRef, b: &ty::TraitRef) -> cres<ty::TraitRef>;
 }
 
 pub struct CombineFields {
@@ -192,32 +193,31 @@ pub fn eq_opt_regions<C:Combine>(
 }
 
 pub fn super_substs<C:Combine>(
-    self: &C, did: ast::def_id,
+    self: &C, generics: &ty::Generics,
     a: &ty::substs, b: &ty::substs) -> cres<ty::substs> {
 
     fn relate_region_param<C:Combine>(
         self: &C,
-        did: ast::def_id,
+        generics: &ty::Generics,
         a: Option<ty::Region>,
         b: Option<ty::Region>)
         -> cres<Option<ty::Region>>
     {
-        let polyty = ty::lookup_item_type(self.infcx().tcx, did);
-        match (polyty.region_param, a, b) {
-          (None, None, None) => {
+        match (&generics.region_param, &a, &b) {
+          (&None, &None, &None) => {
             Ok(None)
           }
-          (Some(ty::rv_invariant), Some(a), Some(b)) => {
+          (&Some(ty::rv_invariant), &Some(a), &Some(b)) => {
             do eq_regions(self, a, b).then {
                 Ok(Some(a))
             }
           }
-          (Some(ty::rv_covariant), Some(a), Some(b)) => {
+          (&Some(ty::rv_covariant), &Some(a), &Some(b)) => {
             do self.regions(a, b).chain |r| {
                 Ok(Some(r))
             }
           }
-          (Some(ty::rv_contravariant), Some(a), Some(b)) => {
+          (&Some(ty::rv_contravariant), &Some(a), &Some(b)) => {
             do self.contraregions(a, b).chain |r| {
                 Ok(Some(r))
             }
@@ -233,14 +233,14 @@ pub fn super_substs<C:Combine>(
                       b had opt_region %s with variance %?",
                       a.inf_str(self.infcx()),
                       b.inf_str(self.infcx()),
-                      polyty.region_param));
+                     generics.region_param));
           }
         }
     }
 
     do self.tps(a.tps, b.tps).chain |tps| {
         do self.self_tys(a.self_ty, b.self_ty).chain |self_ty| {
-            do relate_region_param(self, did,
+            do relate_region_param(self, generics,
                                    a.self_r, b.self_r).chain |self_r|
             {
                 Ok(substs {
@@ -520,26 +520,29 @@ pub fn super_tys<C:Combine>(
       (ty::ty_enum(a_id, ref a_substs),
        ty::ty_enum(b_id, ref b_substs))
       if a_id == b_id => {
-        do self.substs(a_id, a_substs, b_substs).chain |substs| {
-            Ok(ty::mk_enum(tcx, a_id, substs))
-        }
+          let type_def = ty::lookup_item_type(tcx, a_id);
+          do self.substs(&type_def.generics, a_substs, b_substs).chain |substs| {
+              Ok(ty::mk_enum(tcx, a_id, substs))
+          }
       }
 
       (ty::ty_trait(a_id, ref a_substs, a_store),
        ty::ty_trait(b_id, ref b_substs, b_store))
       if a_id == b_id => {
-        do self.substs(a_id, a_substs, b_substs).chain |substs| {
-            do self.trait_stores(ty::terr_trait, a_store, b_store).chain |s| {
-                Ok(ty::mk_trait(tcx, a_id, /*bad*/copy substs, s))
-            }
-        }
+          let trait_def = ty::lookup_trait_def(tcx, a_id);
+          do self.substs(&trait_def.generics, a_substs, b_substs).chain |substs| {
+              do self.trait_stores(ty::terr_trait, a_store, b_store).chain |s| {
+                  Ok(ty::mk_trait(tcx, a_id, /*bad*/copy substs, s))
+              }
+          }
       }
 
       (ty::ty_struct(a_id, ref a_substs), ty::ty_struct(b_id, ref b_substs))
       if a_id == b_id => {
-        do self.substs(a_id, a_substs, b_substs).chain |substs| {
-            Ok(ty::mk_struct(tcx, a_id, substs))
-        }
+          let type_def = ty::lookup_item_type(tcx, a_id);
+          do self.substs(&type_def.generics, a_substs, b_substs).chain |substs| {
+              Ok(ty::mk_struct(tcx, a_id, substs))
+          }
       }
 
       (ty::ty_box(ref a_mt), ty::ty_box(ref b_mt)) => {
@@ -634,3 +637,25 @@ pub fn super_tys<C:Combine>(
         Ok(ty::mk_mach_float(tcx, val))
     }
 }
+
+pub fn super_trait_refs<C:Combine>(
+    self: &C, a: &ty::TraitRef, b: &ty::TraitRef) -> cres<ty::TraitRef>
+{
+    // Different traits cannot be related
+
+    // - NOTE in the future, expand out subtraits!
+
+    if a.def_id != b.def_id {
+        Err(ty::terr_traits(
+            expected_found(self, a.def_id, b.def_id)))
+    } else {
+        let tcx = self.infcx().tcx;
+        let trait_def = ty::lookup_trait_def(tcx, a.def_id);
+        let substs = if_ok!(self.substs(&trait_def.generics, &a.substs, &b.substs));
+        Ok(ty::TraitRef {
+            def_id: a.def_id,
+            substs: substs
+        })
+    }
+}
+
diff --git a/src/librustc/middle/typeck/infer/glb.rs b/src/librustc/middle/typeck/infer/glb.rs
index 9c8c8997ae0..43f2b0eaf72 100644
--- a/src/librustc/middle/typeck/infer/glb.rs
+++ b/src/librustc/middle/typeck/infer/glb.rs
@@ -299,10 +299,11 @@ impl Combine for Glb {
         super_closure_tys(self, a, b)
     }
 
-    fn substs(&self, did: ast::def_id,
+    fn substs(&self,
+              generics: &ty::Generics,
               as_: &ty::substs,
               bs: &ty::substs) -> cres<ty::substs> {
-        super_substs(self, did, as_, bs)
+        super_substs(self, generics, as_, bs)
     }
 
     fn tps(&self, as_: &[ty::t], bs: &[ty::t]) -> cres<~[ty::t]> {
@@ -313,5 +314,9 @@ impl Combine for Glb {
                -> cres<Option<ty::t>> {
         super_self_tys(self, a, b)
     }
+
+    fn trait_refs(&self, a: &ty::TraitRef, b: &ty::TraitRef) -> cres<ty::TraitRef> {
+        super_trait_refs(self, a, b)
+    }
 }
 
diff --git a/src/librustc/middle/typeck/infer/lub.rs b/src/librustc/middle/typeck/infer/lub.rs
index 5a705c31c12..7cf4d25c670 100644
--- a/src/librustc/middle/typeck/infer/lub.rs
+++ b/src/librustc/middle/typeck/infer/lub.rs
@@ -244,10 +244,11 @@ impl Combine for Lub {
         super_args(self, a, b)
     }
 
-    fn substs(&self, did: ast::def_id,
+    fn substs(&self,
+              generics: &ty::Generics,
               as_: &ty::substs,
               bs: &ty::substs) -> cres<ty::substs> {
-        super_substs(self, did, as_, bs)
+        super_substs(self, generics, as_, bs)
     }
 
     fn tps(&self, as_: &[ty::t], bs: &[ty::t]) -> cres<~[ty::t]> {
@@ -258,4 +259,8 @@ impl Combine for Lub {
                -> cres<Option<ty::t>> {
         super_self_tys(self, a, b)
     }
+
+    fn trait_refs(&self, a: &ty::TraitRef, b: &ty::TraitRef) -> cres<ty::TraitRef> {
+        super_trait_refs(self, a, b)
+    }
 }
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index d8093d571a1..58de0122c8c 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -265,7 +265,7 @@ use middle::typeck::infer::to_str::InferStr;
 use middle::typeck::infer::unify::{ValsAndBindings, Root};
 use middle::typeck::isr_alist;
 use util::common::indent;
-use util::ppaux::{bound_region_to_str, ty_to_str};
+use util::ppaux::{bound_region_to_str, ty_to_str, trait_ref_to_str};
 
 use core::cmp::Eq;
 use core::result::{Result, Ok, Err};
@@ -419,6 +419,23 @@ pub fn mk_eqty(cx: @mut InferCtxt,
     }.to_ures()
 }
 
+pub fn mk_sub_trait_refs(cx: @mut InferCtxt,
+                         a_is_expected: bool,
+                         span: span,
+                         a: &ty::TraitRef,
+                         b: &ty::TraitRef)
+    -> ures
+{
+    debug!("mk_sub_trait_refs(%s <: %s)",
+           a.inf_str(cx), b.inf_str(cx));
+    do indent {
+        do cx.commit {
+            let suber = cx.sub(a_is_expected, span);
+            suber.trait_refs(a, b)
+        }
+    }.to_ures()
+}
+
 pub fn mk_coercety(cx: @mut InferCtxt,
                    a_is_expected: bool,
                    span: span,
@@ -700,6 +717,11 @@ pub impl InferCtxt {
                   self.resolve_type_vars_if_possible(t))
     }
 
+    fn trait_ref_to_str(@mut self, t: &ty::TraitRef) -> ~str {
+        let t = self.resolve_type_vars_in_trait_ref_if_possible(t);
+        trait_ref_to_str(self.tcx, &t)
+    }
+
     fn resolve_type_vars_if_possible(@mut self, typ: ty::t) -> ty::t {
         match resolve_type(self, typ, resolve_nested_tvar | resolve_ivar) {
           result::Ok(new_type) => new_type,
@@ -707,6 +729,31 @@ pub impl InferCtxt {
         }
     }
 
+    fn resolve_type_vars_in_trait_ref_if_possible(@mut self,
+                                                  trait_ref: &ty::TraitRef)
+        -> ty::TraitRef
+    {
+        // make up a dummy type just to reuse/abuse the resolve machinery
+        let dummy0 = ty::mk_trait(self.tcx,
+                                  trait_ref.def_id,
+                                  copy trait_ref.substs,
+                                  ty::UniqTraitStore);
+        let dummy1 = self.resolve_type_vars_if_possible(dummy0);
+        match ty::get(dummy1).sty {
+            ty::ty_trait(ref def_id, ref substs, _) => {
+                ty::TraitRef {def_id: *def_id,
+                              substs: copy *substs}
+            }
+            _ => {
+                self.tcx.sess.bug(
+                    fmt!("resolve_type_vars_if_possible() yielded %s \
+                          when supplied with %s",
+                         self.ty_to_str(dummy0),
+                         self.ty_to_str(dummy1)));
+            }
+        }
+    }
+
     fn type_error_message(@mut self, sp: span, mk_msg: &fn(~str) -> ~str,
                           actual_ty: ty::t, err: Option<&ty::type_err>) {
         let actual_ty = self.resolve_type_vars_if_possible(actual_ty);
diff --git a/src/librustc/middle/typeck/infer/sub.rs b/src/librustc/middle/typeck/infer/sub.rs
index 161905c12e5..2e1be2c380f 100644
--- a/src/librustc/middle/typeck/infer/sub.rs
+++ b/src/librustc/middle/typeck/infer/sub.rs
@@ -256,10 +256,11 @@ impl Combine for Sub {
         super_args(self, a, b)
     }
 
-    fn substs(&self, did: ast::def_id,
+    fn substs(&self,
+              generics: &ty::Generics,
               as_: &ty::substs,
               bs: &ty::substs) -> cres<ty::substs> {
-        super_substs(self, did, as_, bs)
+        super_substs(self, generics, as_, bs)
     }
 
     fn tps(&self, as_: &[ty::t], bs: &[ty::t]) -> cres<~[ty::t]> {
@@ -270,5 +271,9 @@ impl Combine for Sub {
                -> cres<Option<ty::t>> {
         super_self_tys(self, a, b)
     }
+
+    fn trait_refs(&self, a: &ty::TraitRef, b: &ty::TraitRef) -> cres<ty::TraitRef> {
+        super_trait_refs(self, a, b)
+    }
 }
 
diff --git a/src/librustc/middle/typeck/infer/to_str.rs b/src/librustc/middle/typeck/infer/to_str.rs
index 559d29e66ef..d4959961f12 100644
--- a/src/librustc/middle/typeck/infer/to_str.rs
+++ b/src/librustc/middle/typeck/infer/to_str.rs
@@ -16,7 +16,7 @@ use middle::ty;
 use middle::typeck::infer::{Bound, Bounds};
 use middle::typeck::infer::InferCtxt;
 use middle::typeck::infer::unify::{Redirect, Root, VarValue};
-use util::ppaux::{mt_to_str, ty_to_str};
+use util::ppaux::{mt_to_str, ty_to_str, trait_ref_to_str};
 
 use syntax::ast;
 
@@ -91,3 +91,9 @@ impl InferStr for ast::float_ty {
         self.to_str()
     }
 }
+
+impl InferStr for ty::TraitRef {
+    fn inf_str(&self, cx: &InferCtxt) -> ~str {
+        trait_ref_to_str(cx.tcx, self)
+    }
+}
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index d829b0d2a0d..d3502adb33a 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -222,8 +222,8 @@ pub fn lookup_def_ccx(ccx: @mut CrateCtxt, sp: span, id: ast::node_id)
 
 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
     ty::ty_param_bounds_and_ty {
-        bounds: @~[],
-        region_param: None,
+        generics: ty::Generics {bounds: @~[],
+                                region_param: None},
         ty: t
     }
 }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 238ecf7acea..cdeb12b80f4 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -239,7 +239,6 @@ pub fn vstore_to_str(cx: ctxt, vs: ty::vstore) -> ~str {
 
 pub fn trait_store_to_str(cx: ctxt, s: ty::TraitStore) -> ~str {
     match s {
-      ty::BareTraitStore => ~"",
       ty::UniqTraitStore => ~"~",
       ty::BoxTraitStore => ~"@",
       ty::RegionTraitStore(r) => region_to_str_space(cx, "&", r)
@@ -285,6 +284,12 @@ pub fn fn_sig_to_str(cx: ctxt, typ: &ty::FnSig) -> ~str {
          ty_to_str(cx, typ.output))
 }
 
+pub fn trait_ref_to_str(cx: ctxt, trait_ref: &ty::TraitRef) -> ~str {
+    let path = ty::item_path(cx, trait_ref.def_id);
+    let base = ast_map::path_to_str(path, cx.sess.intr());
+    parameterized(cx, base, trait_ref.substs.self_r, trait_ref.substs.tps)
+}
+
 pub fn ty_to_str(cx: ctxt, typ: t) -> ~str {
     fn fn_input_to_str(cx: ctxt, input: ty::arg) -> ~str {
         let ty::arg {mode: mode, ty: ty} = input;
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 4a0e58b09c8..ec77b54a853 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -144,7 +144,7 @@ pub static crate_node_id: node_id = 0;
 // the "special" built-in traits (see middle::lang_items) and
 // detects Copy, Send, Owned, and Const.
 pub enum TyParamBound {
-    TraitTyParamBound(@Ty),
+    TraitTyParamBound(@trait_ref),
     RegionTyParamBound
 }
 
diff --git a/src/libsyntax/ext/auto_encode.rs b/src/libsyntax/ext/auto_encode.rs
index d25792355a7..39b8d4f2cce 100644
--- a/src/libsyntax/ext/auto_encode.rs
+++ b/src/libsyntax/ext/auto_encode.rs
@@ -227,10 +227,9 @@ priv impl @ext_ctxt {
         path: @ast::path,
         bounds: @OptVec<ast::TyParamBound>
     ) -> ast::TyParam {
-        let bound = ast::TraitTyParamBound(@ast::Ty {
-            id: self.next_id(),
-            node: ast::ty_path(path, self.next_id()),
-            span: span,
+        let bound = ast::TraitTyParamBound(@ast::trait_ref {
+            ref_id: self.next_id(),
+            path: path
         });
 
         ast::TyParam {
@@ -466,10 +465,9 @@ fn mk_impl(
     // All the type parameters need to bound to the trait.
     let mut impl_tps = opt_vec::with(ty_param);
     for generics.ty_params.each |tp| {
-        let t_bound = ast::TraitTyParamBound(@ast::Ty {
-            id: cx.next_id(),
-            node: ast::ty_path(path, cx.next_id()),
-            span: span,
+        let t_bound = ast::TraitTyParamBound(@ast::trait_ref {
+            path: path,
+            ref_id: cx.next_id(),
         });
 
         impl_tps.push(ast::TyParam {
diff --git a/src/libsyntax/ext/build.rs b/src/libsyntax/ext/build.rs
index 9499f95f0e7..43f0c9edcb9 100644
--- a/src/libsyntax/ext/build.rs
+++ b/src/libsyntax/ext/build.rs
@@ -337,6 +337,17 @@ pub fn mk_ty_path_global(cx: @ext_ctxt,
     let ty = @ast::Ty { id: cx.next_id(), node: ty, span: span };
     ty
 }
+pub fn mk_trait_ref_global(cx: @ext_ctxt,
+                           span: span,
+                           +idents: ~[ ast::ident ])
+    -> @ast::trait_ref
+{
+    let path = build::mk_raw_path_global(span, idents);
+    @ast::trait_ref {
+        path: path,
+        ref_id: cx.next_id()
+    }
+}
 pub fn mk_simple_ty_path(cx: @ext_ctxt,
                          span: span,
                          ident: ast::ident)
diff --git a/src/libsyntax/ext/deriving/mod.rs b/src/libsyntax/ext/deriving/mod.rs
index 18ebceaeb43..ccd9a33757d 100644
--- a/src/libsyntax/ext/deriving/mod.rs
+++ b/src/libsyntax/ext/deriving/mod.rs
@@ -177,9 +177,9 @@ pub fn create_derived_impl(cx: @ext_ctxt,
 
     // Create the type parameters.
     let impl_ty_params = generics.ty_params.map(|ty_param| {
-        let bound = build::mk_ty_path_global(cx,
-                                             span,
-                                             trait_path.map(|x| *x));
+        let bound = build::mk_trait_ref_global(cx,
+                                               span,
+                                               trait_path.map(|x| *x));
         let bounds = @opt_vec::with(TraitTyParamBound(bound));
         build::mk_ty_param(cx, ty_param.ident, bounds)
     });
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 0a473b1cebe..5aa51c262e1 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -134,7 +134,7 @@ pub fn fold_fn_decl(decl: &ast::fn_decl, fld: @ast_fold) -> ast::fn_decl {
 
 fn fold_ty_param_bound(tpb: &TyParamBound, fld: @ast_fold) -> TyParamBound {
     match *tpb {
-        TraitTyParamBound(ty) => TraitTyParamBound(fld.fold_ty(ty)),
+        TraitTyParamBound(ty) => TraitTyParamBound(fold_trait_ref(ty, fld)),
         RegionTyParamBound => RegionTyParamBound
     }
 }
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 1d780c9b806..3a3597828cd 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -2750,8 +2750,8 @@ pub impl Parser {
                     self.bump();
                 }
                 token::MOD_SEP | token::IDENT(*) => {
-                    let maybe_bound = match *self.token {
-                        token::MOD_SEP => None,
+                    let obsolete_bound = match *self.token {
+                        token::MOD_SEP => false,
                         token::IDENT(copy sid, _) => {
                             match *self.id_to_str(sid) {
                                 ~"send" |
@@ -2761,27 +2761,18 @@ pub impl Parser {
                                     self.obsolete(
                                         *self.span,
                                         ObsoleteLowerCaseKindBounds);
-
-                                    // Bogus value, but doesn't matter, since
-                                    // is an error
-                                    Some(TraitTyParamBound(
-                                        self.mk_ty_path(sid)))
+                                    self.bump();
+                                    true
                                 }
-                                _ => None
+                                _ => false
                             }
                         }
                         _ => fail!()
                     };
 
-                    match maybe_bound {
-                        Some(bound) => {
-                            self.bump();
-                            result.push(bound);
-                        }
-                        None => {
-                            let ty = self.parse_ty(true);
-                            result.push(TraitTyParamBound(ty));
-                        }
+                    if !obsolete_bound {
+                        let tref = self.parse_trait_ref();
+                        result.push(TraitTyParamBound(tref));
                     }
                 }
                 _ => break,
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 0c79cbca039..20fc99baf21 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -562,7 +562,7 @@ pub fn print_item(s: @ps, &&item: @ast::item) {
 
         match opt_trait {
             Some(t) => {
-                print_path(s, t.path, false);
+                print_trait_ref(s, t);
                 space(s.s);
                 word_space(s, ~"for");
             }
@@ -619,6 +619,10 @@ pub fn print_item(s: @ps, &&item: @ast::item) {
     (s.ann.post)(ann_node);
 }
 
+fn print_trait_ref(s: @ps, t: &ast::trait_ref) {
+    print_path(s, t.path, false);
+}
+
 pub fn print_enum_def(s: @ps, enum_definition: ast::enum_def,
                       generics: &ast::Generics, ident: ast::ident,
                       span: codemap::span, visibility: ast::visibility) {
@@ -1744,7 +1748,7 @@ pub fn print_bounds(s: @ps, bounds: @OptVec<ast::TyParamBound>) {
             }
 
             match *bound {
-                TraitTyParamBound(ty) => print_type(s, ty),
+                TraitTyParamBound(tref) => print_trait_ref(s, tref),
                 RegionTyParamBound => word(s.s, ~"'static"),
             }
         }
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index a994f2b5b22..b20c5eeee1f 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -147,6 +147,10 @@ pub fn visit_local<E>(loc: @local, e: E, v: vt<E>) {
     }
 }
 
+fn visit_trait_ref<E>(tref: @ast::trait_ref, e: E, v: vt<E>) {
+    visit_path(tref.path, e, v);
+}
+
 pub fn visit_item<E>(i: @item, e: E, v: vt<E>) {
     match i.node {
         item_const(t, ex) => {
@@ -189,9 +193,9 @@ pub fn visit_item<E>(i: @item, e: E, v: vt<E>) {
         }
         item_impl(ref tps, ref traits, ty, ref methods) => {
             (v.visit_generics)(tps, e, v);
-            for traits.each |p| {
-                visit_path(p.path, e, v);
-        }
+            for traits.each |&p| {
+                visit_trait_ref(p, e, v);
+            }
             (v.visit_ty)(ty, e, v);
             for methods.each |m| {
                 visit_method_helper(*m, e, v)
@@ -327,8 +331,8 @@ pub fn visit_ty_param_bounds<E>(bounds: @OptVec<TyParamBound>,
                                 e: E, v: vt<E>) {
     for bounds.each |bound| {
         match *bound {
-            TraitTyParamBound(ty) => (v.visit_ty)(ty, e, v),
-            RegionTyParamBound => ()
+            TraitTyParamBound(ty) => visit_trait_ref(ty, e, v),
+            RegionTyParamBound => {}
         }
     }
 }
diff --git a/src/test/compile-fail/issue-2330.rs b/src/test/compile-fail/issue-2330.rs
index d8acbf2893a..6152e82294d 100644
--- a/src/test/compile-fail/issue-2330.rs
+++ b/src/test/compile-fail/issue-2330.rs
@@ -15,7 +15,7 @@ trait channel<T> {
 }
 
 // `chan` is not a trait, it's an enum
-impl chan for int { //~ ERROR can only implement trait types
+impl chan for int { //~ ERROR chan is not a trait
     fn send(&self, v: int) { fail!() }
 }
 
diff --git a/src/test/compile-fail/selftype-traittype.rs b/src/test/compile-fail/selftype-traittype.rs
index 467154244b7..220573660c5 100644
--- a/src/test/compile-fail/selftype-traittype.rs
+++ b/src/test/compile-fail/selftype-traittype.rs
@@ -12,7 +12,7 @@ trait add {
     fn plus(&self, x: Self) -> Self;
 }
 
-fn do_add(x: add, y: add) -> add {
+fn do_add(x: @add, y: @add) -> @add {
     x.plus(y) //~ ERROR cannot call a method whose type contains a self-type through a boxed trait
 }
 
diff --git a/src/test/run-pass/issue-3702.rs b/src/test/run-pass/issue-3702.rs
index eaa2ac4c4ba..7c2f8cf98cb 100644
--- a/src/test/run-pass/issue-3702.rs
+++ b/src/test/run-pass/issue-3702.rs
@@ -13,7 +13,7 @@ pub fn main() {
     fn to_str(&self) -> ~str;
   }
 
-  fn to_string(t: Text) {
+  fn to_string(t: @Text) {
     io::println(t.to_str());
   }
 
diff --git a/src/test/run-pass/reflect-visit-data.rs b/src/test/run-pass/reflect-visit-data.rs
index 565c06fb8c8..a27599e6ed0 100644
--- a/src/test/run-pass/reflect-visit-data.rs
+++ b/src/test/run-pass/reflect-visit-data.rs
@@ -417,9 +417,9 @@ impl<V:TyVisitor + movable_ptr> TyVisitor for ptr_visit_adaptor<V> {
     }
 
     fn visit_trait(&self) -> bool {
-        self.align_to::<TyVisitor>();
+        self.align_to::<@TyVisitor>();
         if ! self.inner.visit_trait() { return false; }
-        self.bump_past::<TyVisitor>();
+        self.bump_past::<@TyVisitor>();
         true
     }