rustc: Implement monomorphic default methods. r=nmatsakis

21 files changed, 615 insertions, 300 deletions

diff --git a/src/rustc/metadata/common.rs b/src/rustc/metadata/common.rs
index 1857abf2cf2..972d48a6135 100644
--- a/src/rustc/metadata/common.rs
+++ b/src/rustc/metadata/common.rs
@@ -124,5 +124,7 @@ enum astencode_tag { // Reserves 0x50 -- 0x6f
     tag_table_legacy_boxed_trait = 0x63
 }
 
+const tag_item_trait_method_sort: uint = 0x70;
+
 type link_meta = {name: ~str, vers: ~str, extras_hash: ~str};
 
diff --git a/src/rustc/metadata/csearch.rs b/src/rustc/metadata/csearch.rs
index 5f5f938541f..ea6bd499a3b 100644
--- a/src/rustc/metadata/csearch.rs
+++ b/src/rustc/metadata/csearch.rs
@@ -23,6 +23,7 @@ export get_region_param;
 export get_enum_variants;
 export get_impls_for_mod;
 export get_trait_methods;
+export get_provided_trait_methods;
 export get_method_names_if_trait;
 export get_item_attrs;
 export each_path;
@@ -31,6 +32,12 @@ export get_impl_traits;
 export get_impl_method;
 export get_item_path;
 export maybe_get_item_ast, found_ast, found, found_parent, not_found;
+export ProvidedTraitMethodInfo;
+
+struct ProvidedTraitMethodInfo {
+    ty: ty::method,
+    def_id: ast::def_id
+}
 
 fn get_symbol(cstore: cstore::cstore, def: ast::def_id) -> ~str {
     let cdata = cstore::get_crate_data(cstore, def.crate).data;
@@ -99,6 +106,13 @@ fn get_trait_methods(tcx: ty::ctxt, def: ast::def_id) -> @~[ty::method] {
     decoder::get_trait_methods(cstore.intr, cdata, def.node, tcx)
 }
 
+fn get_provided_trait_methods(tcx: ty::ctxt, def: ast::def_id) ->
+        ~[ProvidedTraitMethodInfo] {
+    let cstore = tcx.cstore;
+    let cdata = cstore::get_crate_data(cstore, def.crate);
+    decoder::get_provided_trait_methods(cstore.intr, cdata, def.node, tcx)
+}
+
 fn get_method_names_if_trait(cstore: cstore::cstore, def: ast::def_id)
     -> Option<@DVec<(ast::ident, ast::self_ty_)>> {
 
diff --git a/src/rustc/metadata/decoder.rs b/src/rustc/metadata/decoder.rs
index e639449a857..f0911bd1aa2 100644
--- a/src/rustc/metadata/decoder.rs
+++ b/src/rustc/metadata/decoder.rs
@@ -19,6 +19,7 @@ use syntax::diagnostic::span_handler;
 use common::*;
 use syntax::parse::token::ident_interner;
 use hash::{Hash, HashUtil};
+use csearch::ProvidedTraitMethodInfo;
 
 export class_dtor;
 export get_class_fields;
@@ -40,6 +41,7 @@ export get_crate_hash;
 export get_crate_vers;
 export get_impls_for_mod;
 export get_trait_methods;
+export get_provided_trait_methods;
 export get_method_names_if_trait;
 export get_item_attrs;
 export get_crate_module_paths;
@@ -164,6 +166,13 @@ fn item_family(item: ebml::Doc) -> Family {
     }
 }
 
+fn item_method_sort(item: ebml::Doc) -> char {
+    for ebml::tagged_docs(item, tag_item_trait_method_sort) |doc| {
+        return str::from_bytes(ebml::doc_data(doc))[0] as char;
+    }
+    return 'r';
+}
+
 fn item_symbol(item: ebml::Doc) -> ~str {
     let sym = ebml::get_doc(item, tag_items_data_item_symbol);
     return str::from_bytes(ebml::doc_data(sym));
@@ -701,6 +710,7 @@ fn get_trait_methods(intr: @ident_interner, cdata: cmd, id: ast::node_id,
         let bounds = item_ty_param_bounds(mth, tcx, cdata);
         let name = item_name(intr, mth);
         let ty = doc_type(mth, tcx, cdata);
+        let def_id = item_def_id(mth, cdata);
         let fty = match ty::get(ty).sty {
           ty::ty_fn(f) => f,
           _ => {
@@ -708,14 +718,52 @@ fn get_trait_methods(intr: @ident_interner, cdata: cmd, id: ast::node_id,
                 ~"get_trait_methods: id has non-function type");
         } };
         let self_ty = get_self_ty(mth);
-        result.push({ident: name, tps: bounds, fty: fty,
-                           self_ty: self_ty,
-                           vis: ast::public});
+        result.push({ident: name, tps: bounds, fty: fty, self_ty: self_ty,
+                     vis: ast::public, def_id: def_id});
     }
     debug!("get_trait_methods: }");
     @result
 }
 
+fn get_provided_trait_methods(intr: @ident_interner, cdata: cmd,
+                              id: ast::node_id, tcx: ty::ctxt) ->
+        ~[ProvidedTraitMethodInfo] {
+    let data = cdata.data;
+    let item = lookup_item(id, data);
+    let mut result = ~[];
+
+    for ebml::tagged_docs(item, tag_item_trait_method) |mth| {
+        if item_method_sort(mth) != 'p' { loop; }
+
+        let did = item_def_id(mth, cdata);
+
+        let bounds = item_ty_param_bounds(mth, tcx, cdata);
+        let name = item_name(intr, mth);
+        let ty = doc_type(mth, tcx, cdata);
+
+        let fty;
+        match ty::get(ty).sty {
+            ty::ty_fn(f) => fty = f,
+            _ => {
+                tcx.diag.handler().bug(~"get_provided_trait_methods(): id \
+                                         has non-function type");
+            }
+        }
+
+        let self_ty = get_self_ty(mth);
+        let ty_method = {ident: name, tps: bounds, fty: fty, self_ty: self_ty,
+                         vis: ast::public, def_id: did};
+        let provided_trait_method_info = ProvidedTraitMethodInfo {
+            ty: ty_method,
+            def_id: did
+        };
+
+        vec::push(&mut result, move provided_trait_method_info);
+    }
+
+    return move result;
+}
+
 // If the item in question is a trait, returns its set of methods and
 // their self types. Otherwise, returns none. This overlaps in an
 // annoying way with get_trait_methods.
diff --git a/src/rustc/metadata/encoder.rs b/src/rustc/metadata/encoder.rs
index 2fdd39a2ca4..652af81659a 100644
--- a/src/rustc/metadata/encoder.rs
+++ b/src/rustc/metadata/encoder.rs
@@ -388,6 +388,12 @@ fn encode_self_type(ebml_w: ebml::Serializer, self_type: ast::self_ty_) {
     ebml_w.end_tag();
 }
 
+fn encode_method_sort(ebml_w: ebml::Serializer, sort: char) {
+    ebml_w.start_tag(tag_item_trait_method_sort);
+    ebml_w.writer.write(&[ sort as u8 ]);
+    ebml_w.end_tag();
+}
+
 /* Returns an index of items in this class */
 fn encode_info_for_class(ecx: @encode_ctxt, ebml_w: ebml::Serializer,
                          id: node_id, path: ast_map::path,
@@ -726,6 +732,8 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::Serializer,
         }
       }
       item_trait(tps, traits, ms) => {
+        let provided_methods = dvec::DVec();
+
         add_to_index();
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, local_def(item.id));
@@ -746,12 +754,21 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::Serializer,
                 encode_type(ecx, ebml_w, ty::mk_fn(tcx, mty.fty));
                 encode_family(ebml_w, purity_fn_family(mty.fty.meta.purity));
                 encode_self_type(ebml_w, mty.self_ty);
+                encode_method_sort(ebml_w, 'r');
                 ebml_w.end_tag();
               }
               provided(m) => {
-                encode_info_for_method(ecx, ebml_w, path,
-                                       should_inline(m.attrs), item.id,
-                                       m, m.tps);
+                provided_methods.push(m);
+
+                ebml_w.start_tag(tag_item_trait_method);
+                encode_def_id(ebml_w, local_def(m.id));
+                encode_name(ecx, ebml_w, mty.ident);
+                encode_type_param_bounds(ebml_w, ecx, m.tps);
+                encode_type(ecx, ebml_w, ty::mk_fn(tcx, mty.fty));
+                encode_family(ebml_w, purity_fn_family(mty.fty.meta.purity));
+                encode_self_type(ebml_w, mty.self_ty);
+                encode_method_sort(ebml_w, 'p');
+                ebml_w.end_tag();
               }
             }
             i += 1u;
@@ -785,7 +802,12 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::Serializer,
             ebml_w.end_tag();
         }
 
-
+        // Finally, output all the provided methods as items.
+        for provided_methods.each |m| {
+            index.push({val: m.id, pos: ebml_w.writer.tell()});
+            encode_info_for_method(ecx, ebml_w, path, true, item.id, *m,
+                                   m.tps);
+        }
       }
       item_mac(*) => fail ~"item macros unimplemented"
     }
diff --git a/src/rustc/middle/resolve.rs b/src/rustc/middle/resolve.rs
index ba8e6c26274..4f170fd050b 100644
--- a/src/rustc/middle/resolve.rs
+++ b/src/rustc/middle/resolve.rs
@@ -4680,6 +4680,9 @@ impl Resolver {
     }
 
     fn search_for_traits_containing_method(name: ident) -> @DVec<def_id> {
+        debug!("(searching for traits containing method) looking for '%s'",
+               self.session.str_of(name));
+
         let found_traits = @DVec();
         let mut search_module = self.current_module;
         loop {
@@ -4687,8 +4690,8 @@ impl Resolver {
             match copy self.current_trait_refs {
                 Some(trait_def_ids) => {
                     for trait_def_ids.each |trait_def_id| {
-                        self.add_trait_info_if_containing_method
-                            (found_traits, *trait_def_id, name);
+                        self.add_trait_info_if_containing_method(
+                            found_traits, *trait_def_id, name);
                     }
                 }
                 None => {
@@ -4702,8 +4705,8 @@ impl Resolver {
                     Some(def) => {
                         match def.def {
                             def_ty(trait_def_id) => {
-                                self.add_trait_info_if_containing_method
-                                    (found_traits, trait_def_id, name);
+                                self.add_trait_info_if_containing_method(
+                                    found_traits, trait_def_id, name);
                             }
                             _ => {
                                 // Continue.
@@ -4730,8 +4733,8 @@ impl Resolver {
                                 match def.def {
                                     def_ty(trait_def_id) => {
                                         self.
-                                        add_trait_info_if_containing_method
-                                        (found_traits, trait_def_id, name);
+                                        add_trait_info_if_containing_method(
+                                        found_traits, trait_def_id, name);
                                     }
                                     _ => {
                                         // Continue.
@@ -4766,6 +4769,12 @@ impl Resolver {
                                            trait_def_id: def_id,
                                            name: ident) {
 
+        debug!("(adding trait info if containing method) trying trait %d:%d \
+                for method '%s'",
+               trait_def_id.crate,
+               trait_def_id.node,
+               self.session.str_of(name));
+
         match self.trait_info.find(trait_def_id) {
             Some(trait_info) if trait_info.contains_key(name) => {
                 debug!("(adding trait info if containing method) found trait \
diff --git a/src/rustc/middle/trans/base.rs b/src/rustc/middle/trans/base.rs
index 06d5b2f239e..93e8435d3e9 100644
--- a/src/rustc/middle/trans/base.rs
+++ b/src/rustc/middle/trans/base.rs
@@ -206,7 +206,7 @@ fn GEP_enum(bcx: block, llblobptr: ValueRef, enum_id: ast::def_id,
     assert ix < variant.args.len();
 
     let arg_lltys = vec::map(variant.args, |aty| {
-        type_of(ccx, ty::subst_tps(ccx.tcx, ty_substs, *aty))
+        type_of(ccx, ty::subst_tps(ccx.tcx, ty_substs, None, *aty))
     });
     let typed_blobptr = PointerCast(bcx, llblobptr,
                                     T_ptr(T_struct(arg_lltys)));
@@ -385,16 +385,16 @@ fn get_res_dtor(ccx: @crate_ctxt, did: ast::def_id,
     let _icx = ccx.insn_ctxt("trans_res_dtor");
     if (substs.is_not_empty()) {
         let did = if did.crate != ast::local_crate {
-            inline::maybe_instantiate_inline(ccx, did)
+            inline::maybe_instantiate_inline(ccx, did, true)
         } else { did };
         assert did.crate == ast::local_crate;
-        monomorphize::monomorphic_fn(ccx, did, substs, None, None).val
+        monomorphize::monomorphic_fn(ccx, did, substs, None, None, None).val
     } else if did.crate == ast::local_crate {
         get_item_val(ccx, did.node)
     } else {
         let tcx = ccx.tcx;
         let name = csearch::get_symbol(ccx.sess.cstore, did);
-        let class_ty = ty::subst_tps(tcx, substs,
+        let class_ty = ty::subst_tps(tcx, substs, None,
                           ty::lookup_item_type(tcx, parent_id).ty);
         let llty = type_of_dtor(ccx, class_ty);
         get_extern_fn(ccx.externs, ccx.llmod, name, lib::llvm::CCallConv,
@@ -529,7 +529,8 @@ fn iter_structural_ty(cx: block, av: ValueRef, t: ty::t,
             let v_id = variant.id;
             for vec::each(fn_ty.sig.inputs) |a| {
                 let llfldp_a = GEP_enum(cx, a_tup, tid, v_id, tps, j);
-                let ty_subst = ty::subst_tps(ccx.tcx, tps, a.ty);
+                // XXX: Is "None" right here?
+                let ty_subst = ty::subst_tps(ccx.tcx, tps, None, a.ty);
                 cx = f(cx, llfldp_a, ty_subst);
                 j += 1u;
             }
@@ -1392,8 +1393,11 @@ fn mk_standard_basic_blocks(llfn: ValueRef) ->
 //  - create_llargs_for_fn_args.
 //  - new_fn_ctxt
 //  - trans_args
-fn new_fn_ctxt_w_id(ccx: @crate_ctxt, path: path,
-                    llfndecl: ValueRef, id: ast::node_id,
+fn new_fn_ctxt_w_id(ccx: @crate_ctxt,
+                    path: path,
+                    llfndecl: ValueRef,
+                    id: ast::node_id,
+                    impl_id: Option<ast::def_id>,
                     param_substs: Option<param_substs>,
                     sp: Option<span>) -> fn_ctxt {
     let llbbs = mk_standard_basic_blocks(llfndecl);
@@ -1410,6 +1414,7 @@ fn new_fn_ctxt_w_id(ccx: @crate_ctxt, path: path,
           lllocals: HashMap(),
           llupvars: HashMap(),
           id: id,
+          impl_id: impl_id,
           param_substs: param_substs,
           span: sp,
           path: path,
@@ -1418,7 +1423,7 @@ fn new_fn_ctxt_w_id(ccx: @crate_ctxt, path: path,
 
 fn new_fn_ctxt(ccx: @crate_ctxt, path: path, llfndecl: ValueRef,
                sp: Option<span>) -> fn_ctxt {
-    return new_fn_ctxt_w_id(ccx, path, llfndecl, -1, None, sp);
+    return new_fn_ctxt_w_id(ccx, path, llfndecl, -1, None, None, sp);
 }
 
 // NB: must keep 4 fns in sync:
@@ -1561,6 +1566,7 @@ fn trans_closure(ccx: @crate_ctxt, path: path, decl: ast::fn_decl,
                  ty_self: self_arg,
                  param_substs: Option<param_substs>,
                  id: ast::node_id,
+                 impl_id: Option<ast::def_id>,
                  maybe_load_env: fn(fn_ctxt),
                  finish: fn(block)) {
     ccx.stats.n_closures += 1;
@@ -1568,7 +1574,7 @@ fn trans_closure(ccx: @crate_ctxt, path: path, decl: ast::fn_decl,
     set_uwtable(llfndecl);
 
     // Set up arguments to the function.
-    let fcx = new_fn_ctxt_w_id(ccx, path, llfndecl, id, param_substs,
+    let fcx = new_fn_ctxt_w_id(ccx, path, llfndecl, id, impl_id, param_substs,
                                   Some(body.span));
     let raw_llargs = create_llargs_for_fn_args(fcx, ty_self, decl.inputs);
 
@@ -1620,14 +1626,15 @@ fn trans_fn(ccx: @crate_ctxt,
             llfndecl: ValueRef,
             ty_self: self_arg,
             param_substs: Option<param_substs>,
-            id: ast::node_id) {
+            id: ast::node_id,
+            impl_id: Option<ast::def_id>) {
     let do_time = ccx.sess.trans_stats();
     let start = if do_time { time::get_time() }
                 else { {sec: 0i64, nsec: 0i32} };
     let _icx = ccx.insn_ctxt("trans_fn");
     ccx.stats.n_fns += 1;
     trans_closure(ccx, path, decl, body, llfndecl, ty_self,
-                  param_substs, id,
+                  param_substs, id, impl_id,
                   |fcx| {
                       if ccx.sess.opts.extra_debuginfo {
                           debuginfo::create_function(fcx);
@@ -1654,7 +1661,7 @@ fn trans_enum_variant(ccx: @crate_ctxt,
          ty: varg.ty,
          ident: special_idents::arg,
          id: varg.id});
-    let fcx = new_fn_ctxt_w_id(ccx, ~[], llfndecl, variant.node.id,
+    let fcx = new_fn_ctxt_w_id(ccx, ~[], llfndecl, variant.node.id, None,
                                param_substs, None);
     let raw_llargs = create_llargs_for_fn_args(fcx, no_self, fn_args);
     let ty_param_substs = match param_substs {
@@ -1704,7 +1711,7 @@ fn trans_class_dtor(ccx: @crate_ctxt, path: path,
   let mut class_ty = ty::lookup_item_type(tcx, parent_id).ty;
   /* Substitute in the class type if necessary */
     do option::iter(&psubsts) |ss| {
-    class_ty = ty::subst_tps(tcx, ss.tys, class_ty);
+    class_ty = ty::subst_tps(tcx, ss.tys, ss.self_ty, class_ty);
   }
 
   /* The dtor takes a (null) output pointer, and a self argument,
@@ -1724,7 +1731,7 @@ fn trans_class_dtor(ccx: @crate_ctxt, path: path,
   }
   /* Translate the dtor body */
   trans_fn(ccx, path, ast_util::dtor_dec(),
-           body, lldecl, impl_self(class_ty), psubsts, dtor_id);
+           body, lldecl, impl_self(class_ty), psubsts, dtor_id, None);
   lldecl
 }
 
@@ -1777,7 +1784,7 @@ fn trans_item(ccx: @crate_ctxt, item: ast::item) {
             let llfndecl = get_item_val(ccx, item.id);
             trans_fn(ccx,
                      vec::append(*path, ~[path_name(item.ident)]),
-                     decl, body, llfndecl, no_self, None, item.id);
+                     decl, body, llfndecl, no_self, None, item.id, None);
         } else {
             for vec::each(body.node.stmts) |stmt| {
                 match stmt.node {
@@ -1789,48 +1796,8 @@ fn trans_item(ccx: @crate_ctxt, item: ast::item) {
             }
         }
       }
-      ast::item_impl(tps, trait_refs, self_ast_ty, ms) => {
-        meth::trans_impl(ccx, *path, item.ident, ms, tps, None);
-
-        // Translate any methods that have provided implementations.
-        for trait_refs.each |trait_ref_ptr| {
-            let trait_def = ccx.tcx.def_map.get(trait_ref_ptr.ref_id);
-
-            // XXX: Cross-crate default methods.
-            let trait_id = def_id_of_def(trait_def);
-            if trait_id.crate != ast::local_crate {
-                loop;
-            }
-
-            // Get the self type.
-            let self_ty;
-            match ccx.tcx.ast_ty_to_ty_cache.get(self_ast_ty) {
-                ty::atttce_resolved(self_type) => self_ty = self_type,
-                ty::atttce_unresolved => {
-                    ccx.tcx.sess.impossible_case(item.span,
-                                                 ~"didn't cache self ast ty");
-                }
-            }
-
-            match ccx.tcx.items.get(trait_id.node) {
-                ast_map::node_item(trait_item, _) => {
-                    match trait_item.node {
-                        ast::item_trait(tps, _, trait_methods) => {
-                            trans_trait(ccx, tps, trait_methods, path,
-                                        item.ident, self_ty);
-                        }
-                        _ => {
-                            ccx.tcx.sess.impossible_case(item.span,
-                                                         ~"trait item not a \
-                                                           trait");
-                        }
-                    }
-                }
-                _ => {
-                    ccx.tcx.sess.impossible_case(item.span, ~"no trait item");
-                }
-            }
-        }
+      ast::item_impl(tps, _, _, ms) => {
+        meth::trans_impl(ccx, *path, item.ident, ms, tps, None, item.id);
       }
       ast::item_mod(m) => {
         trans_mod(ccx, m);
@@ -1871,16 +1838,7 @@ fn trans_struct_def(ccx: @crate_ctxt, struct_def: @ast::struct_def,
     // If there are ty params, the ctor will get monomorphized
 
     // Translate methods
-    meth::trans_impl(ccx, *path, ident, struct_def.methods, tps, None);
-}
-
-fn trans_trait(ccx: @crate_ctxt, tps: ~[ast::ty_param],
-               trait_methods: ~[ast::trait_method],
-               path: @ast_map::path, ident: ast::ident,
-               self_ty: ty::t) {
-    // Translate any methods that have provided implementations
-    let (_, provided_methods) = ast_util::split_trait_methods(trait_methods);
-    meth::trans_impl(ccx, *path, ident, provided_methods, tps, Some(self_ty));
+    meth::trans_impl(ccx, *path, ident, struct_def.methods, tps, None, id);
 }
 
 // Translate a module. Doing this amounts to translating the items in the
@@ -2035,7 +1993,7 @@ fn get_dtor_symbol(ccx: @crate_ctxt, path: path, id: ast::node_id,
        // this to item_symbols
        match substs {
          Some(ss) => {
-           let mono_ty = ty::subst_tps(ccx.tcx, ss.tys, t);
+           let mono_ty = ty::subst_tps(ccx.tcx, ss.tys, ss.self_ty, t);
            mangle_exported_name(
                ccx,
                vec::append(path,
diff --git a/src/rustc/middle/trans/callee.rs b/src/rustc/middle/trans/callee.rs
index aa998fb7b92..133f4647e68 100644
--- a/src/rustc/middle/trans/callee.rs
+++ b/src/rustc/middle/trans/callee.rs
@@ -184,21 +184,31 @@ fn trans_fn_ref_with_vtables(
     // Polytype of the function item (may have type params)
     let fn_tpt = ty::lookup_item_type(tcx, def_id);
 
+    // Modify the def_id if this is a default method; we want to be
+    // monomorphizing the trait's code.
+    let (def_id, opt_impl_did) =
+            match tcx.provided_method_sources.find(def_id) {
+        None => (def_id, None),
+        Some(source) => (source.method_id, Some(source.impl_id))
+    };
+
     // Check whether this fn has an inlined copy and, if so, redirect
     // def_id to the local id of the inlined copy.
     let def_id = {
         if def_id.crate != ast::local_crate {
-            inline::maybe_instantiate_inline(ccx, def_id)
+            let may_translate = opt_impl_did.is_none();
+            inline::maybe_instantiate_inline(ccx, def_id, may_translate)
         } else {
             def_id
         }
     };
 
-    // We must monomorphise if the fn has type parameters or is a rust
-    // intrinsic.  In particular, if we see an intrinsic that is
-    // inlined from a different crate, we want to reemit the intrinsic
-    // instead of trying to call it in the other crate.
-    let must_monomorphise = type_params.len() > 0 || {
+    // We must monomorphise if the fn has type parameters, is a rust
+    // intrinsic, or is a default method.  In particular, if we see an
+    // intrinsic that is inlined from a different crate, we want to reemit the
+    // intrinsic instead of trying to call it in the other crate.
+    let must_monomorphise = type_params.len() > 0 ||
+        opt_impl_did.is_some() || {
         if def_id.crate == ast::local_crate {
             let map_node = session::expect(
                 ccx.sess,
@@ -222,7 +232,7 @@ fn trans_fn_ref_with_vtables(
 
         let mut {val, must_cast} =
             monomorphize::monomorphic_fn(ccx, def_id, type_params,
-                                         vtables, Some(ref_id));
+                                         vtables, opt_impl_did, Some(ref_id));
         if must_cast && ref_id != 0 {
             // Monotype of the REFERENCE to the function (type params
             // are subst'd)
@@ -317,7 +327,9 @@ fn trans_rtcall_or_lang_call_with_type_params(bcx: block,
             match callee.data {
                 Fn(fn_data) => {
                     let substituted = ty::subst_tps(callee.bcx.tcx(),
-                                                    type_params, fty);
+                                                    type_params,
+                                                    None,
+                                                    fty);
                     let mut llfnty = type_of::type_of(callee.bcx.ccx(),
                                                       substituted);
                     llfnty = T_ptr(struct_elt(llfnty, 0));
diff --git a/src/rustc/middle/trans/closure.rs b/src/rustc/middle/trans/closure.rs
index 655efe75bf6..3997076f987 100644
--- a/src/rustc/middle/trans/closure.rs
+++ b/src/rustc/middle/trans/closure.rs
@@ -372,7 +372,7 @@ fn trans_expr_fn(bcx: block,
         let {llbox, cdata_ty, bcx} = build_closure(bcx, cap_vars, ck,
                                                    ret_handle);
         trans_closure(ccx, sub_path, decl, body, llfn, no_self,
-                      bcx.fcx.param_substs, id, |fcx| {
+                      bcx.fcx.param_substs, id, None, |fcx| {
             load_environment(fcx, cdata_ty, cap_vars,
                              ret_handle.is_some(), ck);
                       }, |bcx| {
@@ -395,7 +395,7 @@ fn trans_expr_fn(bcx: block,
         }
         ty::proto_bare => {
             trans_closure(ccx, sub_path, decl, body, llfn, no_self, None,
-                          id, |_fcx| { }, |_bcx| { });
+                          id, None, |_fcx| { }, |_bcx| { });
             rslt(bcx, C_null(T_opaque_box_ptr(ccx)))
         }
         ty::proto_vstore(ty::vstore_fixed(_)) => {
diff --git a/src/rustc/middle/trans/common.rs b/src/rustc/middle/trans/common.rs
index 61141f18336..0fa22dd65ba 100644
--- a/src/rustc/middle/trans/common.rs
+++ b/src/rustc/middle/trans/common.rs
@@ -181,9 +181,12 @@ struct ValSelfData {
 
 enum local_val { local_mem(ValueRef), local_imm(ValueRef), }
 
+// Here `self_ty` is the real type of the self parameter to this method. It
+// will only be set in the case of default methods.
 type param_substs = {tys: ~[ty::t],
                      vtables: Option<typeck::vtable_res>,
-                     bounds: @~[ty::param_bounds]};
+                     bounds: @~[ty::param_bounds],
+                     self_ty: Option<ty::t>};
 
 fn param_substs_to_str(tcx: ty::ctxt, substs: &param_substs) -> ~str {
     fmt!("param_substs {tys:%?, vtables:%?, bounds:%?}",
@@ -220,6 +223,10 @@ type fn_ctxt = @{
     mut llreturn: BasicBlockRef,
     // The 'self' value currently in use in this function, if there
     // is one.
+    //
+    // NB: This is the type of the self *variable*, not the self *type*. The
+    // self type is set only for default methods, while the self variable is
+    // set for all methods.
     mut llself: Option<ValSelfData>,
     // The a value alloca'd for calls to upcalls.rust_personality. Used when
     // outputting the resume instruction.
@@ -240,6 +247,9 @@ type fn_ctxt = @{
     // a user-defined function.
     id: ast::node_id,
 
+    // The def_id of the impl we're inside, or None if we aren't inside one.
+    impl_id: Option<ast::def_id>,
+
     // If this function is being monomorphized, this contains the type
     // substitutions used.
     param_substs: Option<param_substs>,
@@ -1110,7 +1120,11 @@ enum mono_param_id {
               datum::DatumMode),
 }
 
-type mono_id_ = {def: ast::def_id, params: ~[mono_param_id]};
+type mono_id_ = {
+    def: ast::def_id,
+    params: ~[mono_param_id],
+    impl_did_opt: Option<ast::def_id>
+};
 
 type mono_id = @mono_id_;
 
@@ -1193,7 +1207,9 @@ fn path_str(sess: session::session, p: path) -> ~str {
 
 fn monomorphize_type(bcx: block, t: ty::t) -> ty::t {
     match bcx.fcx.param_substs {
-        Some(substs) => ty::subst_tps(bcx.tcx(), substs.tys, t),
+        Some(substs) => {
+            ty::subst_tps(bcx.tcx(), substs.tys, substs.self_ty, t)
+        }
         _ => { assert !ty::type_has_params(t); t }
     }
 }
@@ -1213,7 +1229,9 @@ fn node_id_type_params(bcx: block, id: ast::node_id) -> ~[ty::t] {
     let params = ty::node_id_to_type_params(tcx, id);
     match bcx.fcx.param_substs {
       Some(substs) => {
-        vec::map(params, |t| ty::subst_tps(tcx, substs.tys, *t))
+        do vec::map(params) |t| {
+            ty::subst_tps(tcx, substs.tys, substs.self_ty, *t)
+        }
       }
       _ => params
     }
@@ -1241,7 +1259,9 @@ fn resolve_vtable_in_fn_ctxt(fcx: fn_ctxt, vt: typeck::vtable_origin)
         typeck::vtable_static(trait_id, tys, sub) => {
             let tys = match fcx.param_substs {
                 Some(substs) => {
-                    vec::map(tys, |t| ty::subst_tps(tcx, substs.tys, *t))
+                    do vec::map(tys) |t| {
+                        ty::subst_tps(tcx, substs.tys, substs.self_ty, *t)
+                    }
                 }
                 _ => tys
             };
diff --git a/src/rustc/middle/trans/expr.rs b/src/rustc/middle/trans/expr.rs
index 333d76a91ee..08abe986be6 100644
--- a/src/rustc/middle/trans/expr.rs
+++ b/src/rustc/middle/trans/expr.rs
@@ -793,7 +793,9 @@ fn trans_local_var(bcx: block, def: ast::def) -> Datum {
 
             // This cast should not be necessary. We should cast self *once*,
             // but right now this conflicts with default methods.
-            let llselfty = T_ptr(type_of::type_of(bcx.ccx(), self_info.t));
+            let real_self_ty = monomorphize_type(bcx, self_info.t);
+            let llselfty = T_ptr(type_of::type_of(bcx.ccx(), real_self_ty));
+
             let casted_val = PointerCast(bcx, self_info.v, llselfty);
             Datum {
                 val: casted_val,
diff --git a/src/rustc/middle/trans/foreign.rs b/src/rustc/middle/trans/foreign.rs
index dbf5ef81046..5a6260ae270 100644
--- a/src/rustc/middle/trans/foreign.rs
+++ b/src/rustc/middle/trans/foreign.rs
@@ -794,7 +794,7 @@ fn trans_intrinsic(ccx: @crate_ctxt, decl: ValueRef, item: @ast::foreign_item,
 {
     debug!("trans_intrinsic(item.ident=%s)", ccx.sess.str_of(item.ident));
 
-    let fcx = new_fn_ctxt_w_id(ccx, path, decl, item.id,
+    let fcx = new_fn_ctxt_w_id(ccx, path, decl, item.id, None,
                                Some(substs), Some(item.span));
     let mut bcx = top_scope_block(fcx, None), lltop = bcx.llbb;
     match ccx.sess.str_of(item.ident) {
@@ -1025,7 +1025,7 @@ fn trans_foreign_fn(ccx: @crate_ctxt, path: ast_map::path, decl: ast::fn_decl,
             )));
         let llty = type_of_fn_from_ty(ccx, t);
         let llfndecl = decl_internal_cdecl_fn(ccx.llmod, ps, llty);
-        trans_fn(ccx, path, decl, body, llfndecl, no_self, None, id);
+        trans_fn(ccx, path, decl, body, llfndecl, no_self, None, id, None);
         return llfndecl;
     }
 
diff --git a/src/rustc/middle/trans/inline.rs b/src/rustc/middle/trans/inline.rs
index ce9088d4b55..d3cc23094ee 100644
--- a/src/rustc/middle/trans/inline.rs
+++ b/src/rustc/middle/trans/inline.rs
@@ -5,9 +5,12 @@ use syntax::ast_map::{path, path_mod, path_name};
 use base::{trans_item, get_item_val, self_arg, trans_fn,
               impl_self, get_insn_ctxt};
 
-fn maybe_instantiate_inline(ccx: @crate_ctxt, fn_id: ast::def_id)
-    -> ast::def_id
-{
+// `translate` will be true if this function is allowed to translate the
+// item and false otherwise. Currently, this parameter is set to false when
+// translating default methods.
+fn maybe_instantiate_inline(ccx: @crate_ctxt, fn_id: ast::def_id,
+                            translate: bool)
+    -> ast::def_id {
     let _icx = ccx.insn_ctxt("maybe_instantiate_inline");
     match ccx.external.find(fn_id) {
       Some(Some(node_id)) => {
@@ -31,7 +34,7 @@ fn maybe_instantiate_inline(ccx: @crate_ctxt, fn_id: ast::def_id)
           csearch::found(ast::ii_item(item)) => {
             ccx.external.insert(fn_id, Some(item.id));
             ccx.stats.n_inlines += 1;
-            trans_item(ccx, *item);
+            if translate { trans_item(ccx, *item); }
             local_def(item.id)
           }
           csearch::found(ast::ii_foreign(item)) => {
@@ -53,7 +56,7 @@ fn maybe_instantiate_inline(ccx: @crate_ctxt, fn_id: ast::def_id)
               _ => ccx.sess.bug(~"maybe_instantiate_inline: item has a \
                     non-enum parent")
             }
-            trans_item(ccx, *item);
+            if translate { trans_item(ccx, *item); }
             local_def(my_id)
           }
           csearch::found_parent(_, _) => {
@@ -65,13 +68,14 @@ fn maybe_instantiate_inline(ccx: @crate_ctxt, fn_id: ast::def_id)
             ccx.external.insert(fn_id, Some(mth.id));
             let {bounds: impl_bnds, region_param: _, ty: impl_ty} =
                 ty::lookup_item_type(ccx.tcx, impl_did);
-            if (*impl_bnds).len() + mth.tps.len() == 0u {
+            if translate && (*impl_bnds).len() + mth.tps.len() == 0u {
                 let llfn = get_item_val(ccx, mth.id);
                 let path = vec::append(
                     ty::item_path(ccx.tcx, impl_did),
                     ~[path_name(mth.ident)]);
                 trans_fn(ccx, path, mth.decl, mth.body,
-                         llfn, impl_self(impl_ty), None, mth.id);
+                         llfn, impl_self(impl_ty), None, mth.id,
+                         Some(impl_did));
             }
             local_def(mth.id)
           }
@@ -83,3 +87,4 @@ fn maybe_instantiate_inline(ccx: @crate_ctxt, fn_id: ast::def_id)
       }
     }
 }
+
diff --git a/src/rustc/middle/trans/meth.rs b/src/rustc/middle/trans/meth.rs
index 96cf7fabd1f..89b101ab875 100644
--- a/src/rustc/middle/trans/meth.rs
+++ b/src/rustc/middle/trans/meth.rs
@@ -28,7 +28,7 @@ see `trans::base::lval_static_fn()` or `trans::base::monomorphic_fn()`.
 */
 fn trans_impl(ccx: @crate_ctxt, path: path, name: ast::ident,
               methods: ~[@ast::method], tps: ~[ast::ty_param],
-              self_ty: Option<ty::t>) {
+              self_ty: Option<ty::t>, id: ast::node_id) {
     let _icx = ccx.insn_ctxt("impl::trans_impl");
     if tps.len() > 0u { return; }
     let sub_path = vec::append_one(path, path_name(name));
@@ -36,7 +36,22 @@ fn trans_impl(ccx: @crate_ctxt, path: path, name: ast::ident,
         if method.tps.len() == 0u {
             let llfn = get_item_val(ccx, method.id);
             let path = vec::append_one(sub_path, path_name(method.ident));
-            trans_method(ccx, path, *method, None, self_ty, llfn);
+
+            let param_substs_opt;
+            match self_ty {
+                None => param_substs_opt = None,
+                Some(self_ty) => {
+                    param_substs_opt = Some({
+                        tys: ~[],
+                        vtables: None,
+                        bounds: @~[],
+                        self_ty: Some(self_ty)
+                    });
+                }
+            }
+
+            trans_method(ccx, path, *method, param_substs_opt, self_ty, llfn,
+                         ast_util::local_def(id));
         }
     }
 }
@@ -54,13 +69,15 @@ Translates a (possibly monomorphized) method body.
   will be none if this is not a default method and must always be present
   if this is a default method.
 - `llfn`: the LLVM ValueRef for the method
+- `impl_id`: the node ID of the impl this method is inside
 */
 fn trans_method(ccx: @crate_ctxt,
                 path: path,
                 method: &ast::method,
                 param_substs: Option<param_substs>,
                 base_self_ty: Option<ty::t>,
-                llfn: ValueRef) {
+                llfn: ValueRef,
+                impl_id: ast::def_id) {
 
     // figure out how self is being passed
     let self_arg = match method.self_ty.node {
@@ -76,8 +93,10 @@ fn trans_method(ccx: @crate_ctxt,
             Some(provided_self_ty) => self_ty = provided_self_ty
         }
         let self_ty = match param_substs {
-          None => self_ty,
-          Some({tys: ref tys, _}) => ty::subst_tps(ccx.tcx, *tys, self_ty)
+            None => self_ty,
+            Some({tys: ref tys, _}) => {
+                ty::subst_tps(ccx.tcx, *tys, None, self_ty)
+            }
         };
         match method.self_ty.node {
           ast::sty_value => {
@@ -98,15 +117,20 @@ fn trans_method(ccx: @crate_ctxt,
              llfn,
              self_arg,
              param_substs,
-             method.id);
+             method.id,
+             Some(impl_id));
 }
 
-fn trans_self_arg(bcx: block, base: @ast::expr,
+fn trans_self_arg(bcx: block,
+                  base: @ast::expr,
                   mentry: typeck::method_map_entry) -> Result {
     let _icx = bcx.insn_ctxt("impl::trans_self_arg");
     let mut temp_cleanups = ~[];
+
+    // Compute the mode and type of self.
     let self_arg = {mode: mentry.self_arg.mode,
                     ty: monomorphize_type(bcx, mentry.self_arg.ty)};
+
     let result = trans_arg_expr(bcx, self_arg, base,
                                 &mut temp_cleanups, None, DontAutorefArg);
 
@@ -120,11 +144,31 @@ fn trans_self_arg(bcx: block, base: @ast::expr,
 }
 
 fn trans_method_callee(bcx: block, callee_id: ast::node_id,
-                       self: @ast::expr, mentry: typeck::method_map_entry)
-    -> Callee
-{
+                       self: @ast::expr, mentry: typeck::method_map_entry) ->
+                       Callee {
     let _icx = bcx.insn_ctxt("impl::trans_method_callee");
-    match mentry.origin {
+
+    // Replace method_self with method_static here.
+    let mut origin = mentry.origin;
+    match origin {
+        typeck::method_self(copy trait_id, copy method_index) => {
+            // Get the ID of the impl we're inside.
+            let impl_def_id = bcx.fcx.impl_id.get();
+
+            io::println(fmt!("impl_def_id is %?", impl_def_id));
+
+            // Get the ID of the method we're calling.
+            let method_name =
+                ty::trait_methods(bcx.tcx(), trait_id)[method_index].ident;
+            let method_id = method_with_name(bcx.ccx(), impl_def_id,
+                                             method_name);
+            origin = typeck::method_static(method_id);
+        }
+        typeck::method_static(*) | typeck::method_param(*) |
+        typeck::method_trait(*) => {}
+    }
+
+    match origin {
         typeck::method_static(did) => {
             let callee_fn = callee::trans_fn_ref(bcx, did, callee_id);
             let Result {bcx, val} = trans_self_arg(bcx, self, mentry);
@@ -155,7 +199,7 @@ fn trans_method_callee(bcx: block, callee_id: ast::node_id,
             trans_trait_callee(bcx, callee_id, off, self, vstore)
         }
         typeck::method_self(*) => {
-            bcx.tcx().sess.span_bug(self.span, ~"self method call");
+            fail ~"method_self should have been handled above"
         }
     }
 }
@@ -519,13 +563,21 @@ fn vtable_id(ccx: @crate_ctxt, origin: typeck::vtable_origin) -> mono_id {
     match origin {
         typeck::vtable_static(impl_id, substs, sub_vtables) => {
             monomorphize::make_mono_id(
-                ccx, impl_id, substs,
-                if (*sub_vtables).len() == 0u { None }
-                else { Some(sub_vtables) }, None)
+                ccx,
+                impl_id,
+                substs,
+                if (*sub_vtables).len() == 0u {
+                    None
+                } else {
+                    Some(sub_vtables)
+                },
+                None,
+                None)
         }
         typeck::vtable_trait(trait_id, substs) => {
             @{def: trait_id,
-              params: vec::map(substs, |t| mono_precise(*t, None))}
+              params: vec::map(substs, |t| mono_precise(*t, None)),
+              impl_did_opt: None}
         }
         // can't this be checked at the callee?
         _ => fail ~"vtable_id"
@@ -571,7 +623,7 @@ fn make_impl_vtable(ccx: @crate_ctxt, impl_id: ast::def_id, substs: ~[ty::t],
 
     let has_tps = (*ty::lookup_item_type(ccx.tcx, impl_id).bounds).len() > 0u;
     make_vtable(ccx, vec::map(*ty::trait_methods(tcx, trt_id), |im| {
-        let fty = ty::subst_tps(tcx, substs, ty::mk_fn(tcx, im.fty));
+        let fty = ty::subst_tps(tcx, substs, None, ty::mk_fn(tcx, im.fty));
         if (*im.tps).len() > 0u || ty::type_has_self(fty) {
             C_null(T_ptr(T_nil()))
         } else {
@@ -580,10 +632,11 @@ fn make_impl_vtable(ccx: @crate_ctxt, impl_id: ast::def_id, substs: ~[ty::t],
                 // If the method is in another crate, need to make an inlined
                 // copy first
                 if m_id.crate != ast::local_crate {
-                    m_id = inline::maybe_instantiate_inline(ccx, m_id);
+                    // XXX: Set impl ID here?
+                    m_id = inline::maybe_instantiate_inline(ccx, m_id, true);
                 }
                 monomorphize::monomorphic_fn(ccx, m_id, substs,
-                                             Some(vtables), None).val
+                                             Some(vtables), None, None).val
             } else if m_id.crate == ast::local_crate {
                 get_item_val(ccx, m_id.node)
             } else {
diff --git a/src/rustc/middle/trans/monomorphize.rs b/src/rustc/middle/trans/monomorphize.rs
index 914b733df19..f6763206e18 100644
--- a/src/rustc/middle/trans/monomorphize.rs
+++ b/src/rustc/middle/trans/monomorphize.rs
@@ -16,9 +16,9 @@ fn monomorphic_fn(ccx: @crate_ctxt,
                   fn_id: ast::def_id,
                   real_substs: ~[ty::t],
                   vtables: Option<typeck::vtable_res>,
-                  ref_id: Option<ast::node_id>)
-    -> {val: ValueRef, must_cast: bool}
-{
+                  impl_did_opt: Option<ast::def_id>,
+                  ref_id: Option<ast::node_id>) ->
+                  {val: ValueRef, must_cast: bool} {
     let _icx = ccx.insn_ctxt("monomorphic_fn");
     let mut must_cast = false;
     let substs = vec::map(real_substs, |t| {
@@ -31,7 +31,8 @@ fn monomorphic_fn(ccx: @crate_ctxt,
     for real_substs.each() |s| { assert !ty::type_has_params(*s); }
     for substs.each() |s| { assert !ty::type_has_params(*s); }
     let param_uses = type_use::type_uses_for(ccx, fn_id, substs.len());
-    let hash_id = make_mono_id(ccx, fn_id, substs, vtables, Some(param_uses));
+    let hash_id = make_mono_id(ccx, fn_id, substs, vtables, impl_did_opt,
+                               Some(param_uses));
     if vec::any(hash_id.params,
                 |p| match *p { mono_precise(_, _) => false, _ => true }) {
         must_cast = true;
@@ -73,8 +74,11 @@ fn monomorphic_fn(ccx: @crate_ctxt,
       }
       ast_map::node_dtor(_, dtor, _, pt) =>
           (pt, special_idents::dtor, dtor.span),
-      ast_map::node_trait_method(*) => {
-        ccx.tcx.sess.bug(~"Can't monomorphize a trait method")
+      ast_map::node_trait_method(@ast::provided(m), _, pt) => {
+        (pt, m.ident, m.span)
+      }
+      ast_map::node_trait_method(@ast::required(_), _, _) => {
+        ccx.tcx.sess.bug(~"Can't monomorphize a required trait method")
       }
       ast_map::node_expr(*) => {
         ccx.tcx.sess.bug(~"Can't monomorphize an expr")
@@ -93,7 +97,18 @@ fn monomorphic_fn(ccx: @crate_ctxt,
           ccx.tcx.sess.bug(~"Can't monomorphize a local")
       }
     };
-    let mono_ty = ty::subst_tps(ccx.tcx, substs, llitem_ty);
+
+    // Look up the impl type if we're translating a default method.
+    // XXX: Generics.
+    let impl_ty_opt;
+    match impl_did_opt {
+        None => impl_ty_opt = None,
+        Some(impl_did) => {
+            impl_ty_opt = Some(ty::lookup_item_type(ccx.tcx, impl_did).ty);
+        }
+    }
+
+    let mono_ty = ty::subst_tps(ccx.tcx, substs, impl_ty_opt, llitem_ty);
     let llfty = type_of_fn_from_ty(ccx, mono_ty);
 
     ccx.stats.n_monos += 1;
@@ -118,12 +133,18 @@ fn monomorphic_fn(ccx: @crate_ctxt,
         lldecl
     };
 
-    let psubsts = Some({tys: substs, vtables: vtables, bounds: tpt.bounds});
+    let psubsts = Some({
+        tys: substs,
+        vtables: vtables,
+        bounds: tpt.bounds,
+        self_ty: impl_ty_opt
+    });
+
     let lldecl = match map_node {
       ast_map::node_item(i@@{node: ast::item_fn(decl, _, _, body), _}, _) => {
         let d = mk_lldecl();
         set_inline_hint_if_appr(i.attrs, d);
-        trans_fn(ccx, pt, decl, body, d, no_self, psubsts, fn_id.node);
+        trans_fn(ccx, pt, decl, body, d, no_self, psubsts, fn_id.node, None);
         d
       }
       ast_map::node_item(*) => {
@@ -154,11 +175,19 @@ fn monomorphic_fn(ccx: @crate_ctxt,
         }
         d
       }
-      ast_map::node_method(mth, _, _) => {
+      ast_map::node_method(mth, supplied_impl_did, _) => {
         // XXX: What should the self type be here?
         let d = mk_lldecl();
         set_inline_hint_if_appr(mth.attrs, d);
-        meth::trans_method(ccx, pt, mth, psubsts, None, d);
+
+        // Override the impl def ID if necessary.
+        let impl_did;
+        match impl_did_opt {
+            None => impl_did = supplied_impl_did,
+            Some(override_impl_did) => impl_did = override_impl_did
+        }
+
+        meth::trans_method(ccx, pt, mth, psubsts, None, d, impl_did);
         d
       }
       ast_map::node_dtor(_, dtor, _, pt) => {
@@ -171,6 +200,15 @@ fn monomorphic_fn(ccx: @crate_ctxt,
         trans_class_dtor(ccx, *pt, dtor.node.body,
           dtor.node.id, psubsts, Some(hash_id), parent_id)
       }
+      ast_map::node_trait_method(@ast::provided(mth), _, pt) => {
+        let d = mk_lldecl();
+        set_inline_hint_if_appr(mth.attrs, d);
+        io::println(fmt!("monomorphic_fn impl_did_opt is %?", impl_did_opt));
+        meth::trans_method(ccx, *pt, mth, psubsts, None, d,
+                           impl_did_opt.get());
+        d
+      }
+
       // Ugh -- but this ensures any new variants won't be forgotten
       ast_map::node_expr(*) |
       ast_map::node_stmt(*) |
@@ -226,6 +264,7 @@ fn normalize_for_monomorphization(tcx: ty::ctxt, ty: ty::t) -> Option<ty::t> {
 
 fn make_mono_id(ccx: @crate_ctxt, item: ast::def_id, substs: ~[ty::t],
                 vtables: Option<typeck::vtable_res>,
+                impl_did_opt: Option<ast::def_id>,
                 param_uses: Option<~[type_use::type_uses]>) -> mono_id {
     let precise_param_ids = match vtables {
       Some(vts) => {
@@ -295,5 +334,5 @@ fn make_mono_id(ccx: @crate_ctxt, item: ast::def_id, substs: ~[ty::t],
           })
       }
     };
-    @{def: item, params: param_ids}
+    @{def: item, params: param_ids, impl_did_opt: impl_did_opt}
 }
diff --git a/src/rustc/middle/trans/type_use.rs b/src/rustc/middle/trans/type_use.rs
index 1f9ad20dd03..8ccc8a28de3 100644
--- a/src/rustc/middle/trans/type_use.rs
+++ b/src/rustc/middle/trans/type_use.rs
@@ -40,8 +40,13 @@ fn type_uses_for(ccx: @crate_ctxt, fn_id: def_id, n_tps: uint)
       Some(uses) => return uses,
       None => ()
     }
-    let fn_id_loc = if fn_id.crate == local_crate { fn_id }
-                    else { inline::maybe_instantiate_inline(ccx, fn_id) };
+
+    let fn_id_loc = if fn_id.crate == local_crate {
+        fn_id
+    } else {
+        inline::maybe_instantiate_inline(ccx, fn_id, true)
+    };
+
     // Conservatively assume full use for recursive loops
     ccx.type_use_cache.insert(fn_id, vec::from_elem(n_tps, 3u));
 
diff --git a/src/rustc/middle/ty.rs b/src/rustc/middle/ty.rs
index cc132a431a3..a0ca46ee017 100644
--- a/src/rustc/middle/ty.rs
+++ b/src/rustc/middle/ty.rs
@@ -19,6 +19,7 @@ use syntax::ast::*;
 use syntax::print::pprust::*;
 use util::ppaux::{ty_to_str, proto_ty_to_str, tys_to_str};
 
+export ProvidedMethodSource;
 export TyVid, IntVid, FnVid, RegionVid, vid;
 export br_hashmap;
 export is_instantiable;
@@ -207,7 +208,8 @@ type method = {ident: ast::ident,
                tps: @~[param_bounds],
                fty: FnTy,
                self_ty: ast::self_ty_,
-               vis: ast::visibility};
+               vis: ast::visibility,
+               def_id: ast::def_id};
 
 type mt = {ty: t, mutbl: ast::mutability};
 
@@ -314,6 +316,11 @@ enum AutoRefKind {
     AutoPtr
 }
 
+struct ProvidedMethodSource {
+    method_id: ast::def_id,
+    impl_id: ast::def_id
+}
+
 type ctxt =
     @{diag: syntax::diagnostic::span_handler,
       interner: HashMap<intern_key, t_box>,
@@ -356,7 +363,8 @@ type ctxt =
       adjustments: HashMap<ast::node_id, @AutoAdjustment>,
       normalized_cache: HashMap<t, t>,
       lang_items: middle::lang_items::LanguageItems,
-      legacy_boxed_traits: HashMap<node_id, ()>};
+      legacy_boxed_traits: HashMap<node_id, ()>,
+      provided_method_sources: HashMap<ast::def_id, ProvidedMethodSource>};
 
 enum tbox_flag {
     has_params = 1,
@@ -879,7 +887,8 @@ fn mk_ctxt(s: session::session,
       adjustments: HashMap(),
       normalized_cache: new_ty_hash(),
       lang_items: move lang_items,
-      legacy_boxed_traits: HashMap()}
+      legacy_boxed_traits: HashMap(),
+      provided_method_sources: HashMap()}
 }
 
 
@@ -1392,13 +1401,23 @@ fn fold_region(cx: ctxt, t0: t, fldop: fn(region, bool) -> region) -> t {
 }
 
 // Substitute *only* type parameters.  Used in trans where regions are erased.
-fn subst_tps(cx: ctxt, tps: &[t], typ: t) -> t {
-    if tps.len() == 0u { return typ; }
+fn subst_tps(cx: ctxt, tps: &[t], self_ty_opt: Option<t>, typ: t) -> t {
+    if tps.len() == 0u && self_ty_opt.is_none() { return typ; }
     let tb = ty::get(typ);
-    if !tbox_has_flag(tb, has_params) { return typ; }
+    if self_ty_opt.is_none() && !tbox_has_flag(tb, has_params) { return typ; }
     match tb.sty {
-      ty_param(p) => tps[p.idx],
-      ref sty => fold_sty_to_ty(cx, sty, |t| subst_tps(cx, tps, t))
+        ty_param(p) => tps[p.idx],
+        ty_self => {
+            match self_ty_opt {
+                None => cx.sess.bug(~"ty_self unexpected here"),
+                Some(self_ty) => {
+                    subst_tps(cx, tps, self_ty_opt, self_ty)
+                }
+            }
+        }
+        ref sty => {
+            fold_sty_to_ty(cx, sty, |t| subst_tps(cx, tps, self_ty_opt, t))
+        }
     }
 }
 
@@ -3328,20 +3347,18 @@ fn store_trait_methods(cx: ctxt, id: ast::node_id, ms: @~[method]) {
     cx.trait_method_cache.insert(ast_util::local_def(id), ms);
 }
 
-fn provided_trait_methods(cx: ctxt, id: ast::def_id) -> ~[@ast::method] {
+fn provided_trait_methods(cx: ctxt, id: ast::def_id) -> ~[ast::ident] {
     if is_local(id) {
         match cx.items.find(id.node) {
             Some(ast_map::node_item(@{node: item_trait(_, _, ms),_}, _)) =>
                 match ast_util::split_trait_methods(ms) {
-                   (_, p) => p
+                   (_, p) => p.map(|method| method.ident)
                 },
             _ => cx.sess.bug(fmt!("provided_trait_methods: %? is not a trait",
                                   id))
         }
-    }
-    else {
-        // FIXME #2794: default methods for traits don't work cross-crate
-        ~[]
+    } else {
+        csearch::get_provided_trait_methods(cx, id).map(|info| info.ty.ident)
     }
 }
 
@@ -3599,10 +3616,12 @@ fn enum_variant_with_id(cx: ctxt, enum_id: ast::def_id,
 // the type cache. Returns the type parameters and type.
 fn lookup_item_type(cx: ctxt, did: ast::def_id) -> ty_param_bounds_and_ty {
     match cx.tcache.find(did) {
-      Some(tpt) => return tpt,
-      None => {
+      Some(tpt) => {
         // The item is in this crate. The caller should have added it to the
         // type cache already
+        return tpt;
+      }
+      None => {
         assert did.crate != ast::local_crate;
         let tyt = csearch::get_type(cx, did);
         cx.tcache.insert(did, tyt);
diff --git a/src/rustc/middle/typeck.rs b/src/rustc/middle/typeck.rs
index 7cb04bc0ea3..077d34700b8 100644
--- a/src/rustc/middle/typeck.rs
+++ b/src/rustc/middle/typeck.rs
@@ -62,6 +62,7 @@ use util::ppaux::{ty_to_str, tys_to_str, region_to_str,
 use util::common::{indent, indenter};
 use std::list;
 use list::{List, Nil, Cons};
+use dvec::DVec;
 
 export check_crate;
 export infer;
@@ -174,12 +175,6 @@ impl vtable_origin {
 
 type vtable_map = HashMap<ast::node_id, vtable_res>;
 
-// Stores information about provided methods, aka "default methods" in traits.
-// Maps from a trait's def_id to a MethodInfo about
-// that method in that trait.
-type provided_methods_map = HashMap<ast::node_id,
-                                    ~[@resolve::MethodInfo]>;
-
 type ty_param_substs_and_ty = {substs: ty::substs, ty: ty::t};
 
 type crate_ctxt_ = {// A mapping from method call sites to traits that have
@@ -188,7 +183,6 @@ type crate_ctxt_ = {// A mapping from method call sites to traits that have
                     method_map: method_map,
                     vtable_map: vtable_map,
                     coherence_info: @coherence::CoherenceInfo,
-                    provided_methods_map: provided_methods_map,
                     tcx: ty::ctxt};
 
 enum crate_ctxt {
@@ -340,7 +334,6 @@ fn check_crate(tcx: ty::ctxt,
                             method_map: std::map::HashMap(),
                             vtable_map: std::map::HashMap(),
                             coherence_info: @coherence::CoherenceInfo(),
-                            provided_methods_map: std::map::HashMap(),
                             tcx: tcx});
     collect::collect_item_types(ccx, crate);
     coherence::check_coherence(ccx, crate);
diff --git a/src/rustc/middle/typeck/check/method.rs b/src/rustc/middle/typeck/check/method.rs
index 0d71d61bdaa..04be0047548 100644
--- a/src/rustc/middle/typeck/check/method.rs
+++ b/src/rustc/middle/typeck/check/method.rs
@@ -69,7 +69,7 @@ obtained the type `Foo`, we would never match this method.
 
 */
 
-use coherence::get_base_type_def_id;
+use coherence::{ProvidedMethodInfo, get_base_type_def_id};
 use middle::resolve::{Impl, MethodInfo};
 use middle::ty::*;
 use syntax::ast::{def_id, sty_by_ref, sty_value, sty_region, sty_box,
@@ -146,7 +146,7 @@ impl LookupContext {
 
         // Prepare the list of candidates
         self.push_inherent_candidates(self_ty);
-        self.push_extension_candidates();
+        self.push_extension_candidates(self_ty);
 
         let enum_dids = DVec();
         let mut self_ty = self_ty;
@@ -251,7 +251,7 @@ impl LookupContext {
         }
     }
 
-    fn push_extension_candidates(&self) {
+    fn push_extension_candidates(&self, self_ty: ty::t) {
         // If the method being called is associated with a trait, then
         // find all the impls of that trait.  Each of those are
         // candidates.
@@ -259,6 +259,8 @@ impl LookupContext {
         for opt_applicable_traits.each |applicable_traits| {
             for applicable_traits.each |trait_did| {
                 let coherence_info = self.fcx.ccx.coherence_info;
+
+                // Look for explicit implementations.
                 let opt_impl_infos =
                     coherence_info.extension_methods.find(*trait_did);
                 for opt_impl_infos.each |impl_infos| {
@@ -267,12 +269,21 @@ impl LookupContext {
                             &self.extension_candidates, *impl_info);
                     }
                 }
+
+                // Look for default methods.
+                match coherence_info.provided_methods.find(*trait_did) {
+                    Some(methods) => {
+                        self.push_candidates_from_provided_methods(
+                            &self.extension_candidates, self_ty, *trait_did,
+                            methods);
+                    }
+                    None => {}
+                }
             }
         }
     }
 
-    fn push_inherent_candidates_from_param(&self, param_ty: param_ty)
-    {
+    fn push_inherent_candidates_from_param(&self, param_ty: param_ty) {
         debug!("push_inherent_candidates_from_param(param_ty=%?)",
                param_ty);
         let _indenter = indenter();
@@ -348,8 +359,7 @@ impl LookupContext {
                                            self_ty: ty::t,
                                            did: def_id,
                                            substs: &ty::substs,
-                                           vstore: ty::vstore)
-    {
+                                           vstore: ty::vstore) {
         debug!("push_inherent_candidates_from_trait(did=%s, substs=%s)",
                self.did_to_str(did),
                substs_to_str(self.tcx(), substs));
@@ -423,8 +433,7 @@ impl LookupContext {
         });
     }
 
-    fn push_inherent_impl_candidates_for_type(did: def_id)
-    {
+    fn push_inherent_impl_candidates_for_type(did: def_id) {
         let opt_impl_infos =
             self.fcx.ccx.coherence_info.inherent_methods.find(did);
         for opt_impl_infos.each |impl_infos| {
@@ -436,8 +445,7 @@ impl LookupContext {
     }
 
     fn push_candidates_from_impl(&self, candidates: &DVec<Candidate>,
-                                 impl_info: &resolve::Impl)
-    {
+                                 impl_info: &resolve::Impl) {
         if !self.impl_dups.insert(impl_info.did, ()) {
             return; // already visited
         }
@@ -471,12 +479,47 @@ impl LookupContext {
         });
     }
 
+    fn push_candidates_from_provided_methods(
+            &self,
+            candidates: &DVec<Candidate>,
+            self_ty: ty::t,
+            trait_def_id: def_id,
+            methods: @DVec<@ProvidedMethodInfo>) {
+        debug!("(pushing candidates from provided methods) considering trait \
+                id %d:%d",
+               trait_def_id.crate,
+               trait_def_id.node);
+
+        for methods.each |provided_method_info| {
+            if provided_method_info.method_info.ident != self.m_name { loop; }
+
+            debug!("(pushing candidates from provided methods) adding \
+                    candidate");
+
+            // XXX: Needs to support generics.
+            let dummy_substs = { self_r: None, self_ty: None, tps: ~[] };
+            let (impl_ty, impl_substs) =
+                self.create_rcvr_ty_and_substs_for_method(
+                    provided_method_info.method_info.self_type,
+                    self_ty,
+                    dummy_substs);
+
+            candidates.push(Candidate {
+                rcvr_ty: impl_ty,
+                rcvr_substs: move impl_substs,
+                num_method_tps: provided_method_info.method_info.n_tps,
+                self_mode: get_mode_from_self_type(
+                    provided_method_info.method_info.self_type),
+                origin: method_static(provided_method_info.method_info.did)
+            });
+        }
+    }
+
     fn create_rcvr_ty_and_substs_for_method(&self,
                                             self_decl: ast::self_ty_,
                                             self_ty: ty::t,
                                             +self_substs: ty::substs)
-        -> (ty::t, ty::substs)
-    {
+        -> (ty::t, ty::substs) {
         // If the self type includes a region (like &self), we need to
         // ensure that the receiver substitutions have a self region.
         // If the receiver type does not itself contain borrowed
@@ -693,8 +736,7 @@ impl LookupContext {
     fn confirm_candidate(&self,
                          self_ty: ty::t,
                          candidate: &Candidate)
-        -> method_map_entry
-    {
+        -> method_map_entry {
         let tcx = self.tcx();
         let fty = self.fn_ty_from_origin(&candidate.origin);
 
diff --git a/src/rustc/middle/typeck/check/vtable.rs b/src/rustc/middle/typeck/check/vtable.rs
index 00fb134f2be..345b8246b42 100644
--- a/src/rustc/middle/typeck/check/vtable.rs
+++ b/src/rustc/middle/typeck/check/vtable.rs
@@ -444,7 +444,7 @@ fn connect_trait_tps(fcx: @fn_ctxt, expr: @ast::expr, impl_tys: ~[ty::t],
 
     // XXX: This should work for multiple traits.
     let ity = ty::impl_traits(tcx, impl_did, vstore)[0];
-    let trait_ty = ty::subst_tps(tcx, impl_tys, ity);
+    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 {
diff --git a/src/rustc/middle/typeck/coherence.rs b/src/rustc/middle/typeck/coherence.rs
index 89cd696eb6f..9a9a8dda6e4 100644
--- a/src/rustc/middle/typeck/coherence.rs
+++ b/src/rustc/middle/typeck/coherence.rs
@@ -4,12 +4,13 @@
 // has at most one implementation for each type. Then we build a mapping from
 // each trait in the system to its implementations.
 
-use metadata::csearch::{each_path, get_impl_traits, get_impls_for_mod};
+use metadata::csearch::{ProvidedTraitMethodInfo, each_path, get_impl_traits};
+use metadata::csearch::{get_impls_for_mod};
 use metadata::cstore::{cstore, iter_crate_data};
 use metadata::decoder::{dl_def, dl_field, dl_impl};
 use middle::resolve::{Impl, MethodInfo};
-use middle::ty::{get, lookup_item_type, subst, t, ty_box};
-use middle::ty::{ty_uniq, ty_ptr, ty_rptr, ty_enum};
+use middle::ty::{ProvidedMethodSource, get, lookup_item_type, subst, t};
+use middle::ty::{ty_box, ty_uniq, ty_ptr, ty_rptr, ty_enum};
 use middle::ty::{ty_class, ty_nil, ty_bot, ty_bool, ty_int, ty_uint};
 use middle::ty::{ty_float, ty_estr, ty_evec, ty_rec};
 use middle::ty::{ty_fn, ty_trait, ty_tup, ty_infer};
@@ -17,7 +18,7 @@ use middle::ty::{ty_param, ty_self, ty_type, ty_opaque_box};
 use middle::ty::{ty_opaque_closure_ptr, ty_unboxed_vec, type_is_ty_var};
 use middle::typeck::infer::{infer_ctxt, can_mk_subty};
 use middle::typeck::infer::{new_infer_ctxt, resolve_ivar, resolve_type};
-use syntax::ast::{crate, def_id, def_mod};
+use syntax::ast::{crate, def_id, def_mod, def_ty};
 use syntax::ast::{item, item_class, item_const, item_enum, item_fn};
 use syntax::ast::{item_foreign_mod, item_impl, item_mac, item_mod};
 use syntax::ast::{item_trait, item_ty, local_crate, method, node_id};
@@ -118,6 +119,21 @@ fn method_to_MethodInfo(ast_method: @method) -> @MethodInfo {
     }
 }
 
+// Stores the method info and definition ID of the associated trait method for
+// each instantiation of each provided method.
+struct ProvidedMethodInfo {
+    method_info: @MethodInfo,
+    trait_method_def_id: def_id
+}
+
+// Stores information about provided methods (a.k.a. default methods) in
+// implementations.
+//
+// This is a map from ID of each implementation to the method info and trait
+// method ID of each of the default methods belonging to the trait that that
+// implementation implements.
+type ProvidedMethodsMap = HashMap<def_id,@DVec<@ProvidedMethodInfo>>;
+
 struct CoherenceInfo {
     // Contains implementations of methods that are inherent to a type.
     // Methods in these implementations don't need to be exported.
@@ -128,14 +144,20 @@ struct CoherenceInfo {
     extension_methods: HashMap<def_id,@DVec<@Impl>>,
 
     // A mapping from a supertrait to its subtraits.
-    supertrait_to_subtraits: HashMap<def_id,@DVec<def_id>>
+    supertrait_to_subtraits: HashMap<def_id,@DVec<def_id>>,
+
+    // A mapping from an implementation ID to the method info and trait method
+    // ID of the provided (a.k.a. default) methods in the traits that that
+    // implementation implements.
+    provided_methods: ProvidedMethodsMap,
 }
 
 fn CoherenceInfo() -> CoherenceInfo {
     CoherenceInfo {
         inherent_methods: HashMap(),
         extension_methods: HashMap(),
-        supertrait_to_subtraits: HashMap()
+        supertrait_to_subtraits: HashMap(),
+        provided_methods: HashMap(),
     }
 }
 
@@ -165,68 +187,6 @@ struct CoherenceChecker {
 }
 
 impl CoherenceChecker {
-    // Create a mapping containing a MethodInfo for every provided
-    // method in every trait.
-    fn build_provided_methods_map(crate: @crate) {
-        let sess = self.crate_context.tcx.sess;
-
-        let pmm = self.crate_context.provided_methods_map;
-
-        visit_crate(*crate, (), mk_simple_visitor(@{
-            visit_item: |item| {
-                match item.node {
-                  item_trait(_, _, trait_methods) => {
-                    for trait_methods.each |trait_method| {
-                        debug!("(building provided methods map) checking \
-                                trait `%s` with id %d",
-                                sess.str_of(item.ident), item.id);
-
-                        match *trait_method {
-                            required(_) => { /* fall through */}
-                            provided(m) => {
-                                // For every provided method in the
-                                // trait, store a MethodInfo.
-                                let mi = method_to_MethodInfo(m);
-
-                                match pmm.find(item.id) {
-                                    Some(mis) => {
-                                      // If the trait already has an
-                                      // entry in the
-                                      // provided_methods_map, we just
-                                      // need to add this method to
-                                      // that entry.
-                                      debug!("(building provided \
-                                              methods map) adding \
-                                              method `%s` to entry for \
-                                              existing trait",
-                                              sess.str_of(mi.ident));
-                                      let mut method_infos = mis;
-                                      method_infos.push(mi);
-                                      pmm.insert(item.id, method_infos);
-                                    }
-                                    None => {
-                                      // If the trait doesn't have an
-                                      // entry yet, create one.
-                                      debug!("(building provided \
-                                              methods map) creating new \
-                                              entry for method `%s`",
-                                              sess.str_of(mi.ident));
-                                      pmm.insert(item.id, ~[mi]);
-                                    }
-                                }
-                            }
-                        }
-                    }
-                  }
-                  _ => {
-                    // Nothing to do.
-                  }
-                };
-            },
-            .. *default_simple_visitor()
-        }));
-    }
-
     fn check_coherence(crate: @crate) {
         // Check implementations and traits. This populates the tables
         // containing the inherent methods and extension methods. It also
@@ -307,6 +267,7 @@ impl CoherenceChecker {
                         self.crate_context.tcx.sess.parse_sess.interner),
                     self.crate_context.tcx.sess.str_of(item.ident));
 
+            self.instantiate_default_methods(item.id, trait_did);
             let implementation = self.create_impl_from_item(item);
             self.add_trait_method(trait_did, implementation);
         }
@@ -321,6 +282,7 @@ impl CoherenceChecker {
                 // Nothing to do.
             }
             Some(base_type_def_id) => {
+                // XXX: Gather up default methods?
                 let implementation = self.create_impl_from_item(item);
                 self.add_inherent_method(base_type_def_id, implementation);
 
@@ -330,6 +292,68 @@ impl CoherenceChecker {
         }
     }
 
+    // Creates default method IDs and performs type substitutions for an impl
+    // and trait pair. Then, for each provided method in the trait, inserts a
+    // `ProvidedMethodInfo` instance into the `provided_method_sources` map.
+    fn instantiate_default_methods(impl_id: ast::node_id,
+                                   trait_did: ast::def_id) {
+        for self.each_provided_trait_method(trait_did) |trait_method| {
+            // Synthesize an ID.
+            let tcx = self.crate_context.tcx;
+            let new_id = syntax::parse::next_node_id(tcx.sess.parse_sess);
+            let new_did = local_def(new_id);
+
+            // XXX: Perform substitutions.
+            let new_polytype = ty::lookup_item_type(tcx, trait_method.def_id);
+            tcx.tcache.insert(new_did, new_polytype);
+
+            // Pair the new synthesized ID up with the
+            // ID of the method.
+            let source = ProvidedMethodSource {
+                method_id: trait_method.def_id,
+                impl_id: local_def(impl_id)
+            };
+
+            self.crate_context.tcx.provided_method_sources.insert(new_did,
+                                                                  source);
+
+            let provided_method_info =
+                @ProvidedMethodInfo {
+                    method_info: @{
+                        did: new_did,
+                        n_tps: trait_method.tps.len(),
+                        ident: trait_method.ident,
+                        self_type: trait_method.self_ty
+                    },
+                    trait_method_def_id: trait_method.def_id
+                };
+
+            let pmm = self.crate_context.coherence_info.provided_methods;
+            match pmm.find(local_def(impl_id)) {
+                Some(mis) => {
+                    // If the trait already has an entry in the
+                    // provided_methods_map, we just need to add this
+                    // method to that entry.
+                    debug!("(checking implementation) adding method `%s` \
+                            to entry for existing trait",
+                            self.crate_context.tcx.sess.str_of(
+                                provided_method_info.method_info.ident));
+                    mis.push(provided_method_info);
+                }
+                None => {
+                    // If the trait doesn't have an entry yet, create one.
+                    debug!("(checking implementation) creating new entry \
+                            for method `%s`",
+                            self.crate_context.tcx.sess.str_of(
+                                provided_method_info.method_info.ident));
+                    let method_infos = @DVec();
+                    method_infos.push(provided_method_info);
+                    pmm.insert(local_def(impl_id), method_infos);
+                }
+            }
+        }
+    }
+
     fn register_inherited_trait(item: @item, supertraits: ~[@trait_ref]) {
         // XXX: This is wrong. We need to support substitutions; e.g.
         // trait Foo : Bar<int>.
@@ -354,8 +378,7 @@ impl CoherenceChecker {
     fn add_inherent_method(base_def_id: def_id, implementation: @Impl) {
         let implementation_list;
         match self.crate_context.coherence_info.inherent_methods
-            .find(base_def_id) {
-
+                  .find(base_def_id) {
             None => {
                 implementation_list = @DVec();
                 self.crate_context.coherence_info.inherent_methods
@@ -372,8 +395,7 @@ impl CoherenceChecker {
     fn add_trait_method(trait_id: def_id, implementation: @Impl) {
         let implementation_list;
         match self.crate_context.coherence_info.extension_methods
-                .find(trait_id) {
-
+                  .find(trait_id) {
             None => {
                 implementation_list = @DVec();
                 self.crate_context.coherence_info.extension_methods
@@ -413,6 +435,26 @@ impl CoherenceChecker {
         }
     }
 
+    fn each_provided_trait_method(
+            trait_did: ast::def_id,
+            f: &fn(x: &ty::method) -> bool) {
+        // Make a list of all the names of the provided methods.
+        // XXX: This is horrible.
+        let provided_method_idents = HashMap();
+        let tcx = self.crate_context.tcx;
+        for ty::provided_trait_methods(tcx, trait_did).each |ident| {
+            provided_method_idents.insert(*ident, ());
+        }
+
+        for ty::trait_methods(tcx, trait_did).each |method| {
+            if provided_method_idents.contains_key(method.ident) {
+                if !f(method) {
+                    break;
+                }
+            }
+        }
+    }
+
     fn polytypes_unify(polytype_a: ty_param_bounds_and_ty,
                        polytype_b: ty_param_bounds_and_ty)
                     -> bool {
@@ -449,7 +491,6 @@ impl CoherenceChecker {
 
     fn get_self_type_for_implementation(implementation: @Impl)
                                      -> ty_param_bounds_and_ty {
-
         return self.crate_context.tcx.tcache.get(implementation.did);
     }
 
@@ -552,33 +593,15 @@ impl CoherenceChecker {
 
     // Converts an implementation in the AST to an Impl structure.
     fn create_impl_from_item(item: @item) -> @Impl {
-
-        fn add_provided_methods(inherent_methods: ~[@MethodInfo],
-                                all_provided_methods: ~[@MethodInfo],
-                                sess: driver::session::session)
-            -> ~[@MethodInfo] {
-
-            let mut methods = inherent_methods;
-
-            // If there's no inherent method with the same name as a
-            // provided method, add that provided method to `methods`.
+        fn add_provided_methods(all_methods: &mut ~[@MethodInfo],
+                                all_provided_methods: ~[@ProvidedMethodInfo],
+                                sess: driver::session::session) {
             for all_provided_methods.each |provided_method| {
-                let mut method_inherent_to_impl = false;
-                for inherent_methods.each |inherent_method| {
-                    if provided_method.ident == inherent_method.ident {
-                        method_inherent_to_impl = true;
-                    }
-                }
-
-                if !method_inherent_to_impl {
-                    debug!(
-                        "(creating impl) adding provided method `%s` to impl",
-                        sess.str_of(provided_method.ident));
-                    methods.push(*provided_method);
-                }
+                debug!(
+                    "(creating impl) adding provided method `%s` to impl",
+                    sess.str_of(provided_method.method_info.ident));
+                vec::push(all_methods, provided_method.method_info);
             }
-
-            return methods;
         }
 
         match item.node {
@@ -598,24 +621,22 @@ impl CoherenceChecker {
                     let trait_did =
                         self.trait_ref_to_trait_def_id(*trait_ref);
 
-                    match self.crate_context.provided_methods_map
-                        .find(trait_did.node) {
+                    match self.crate_context
+                              .coherence_info
+                              .provided_methods
+                              .find(local_def(item.id)) {
                         None => {
                             debug!("(creating impl) trait with node_id `%d` \
                                     has no provided methods", trait_did.node);
                             /* fall through */
                         }
-                        Some(all_provided)
-                                    => {
+                        Some(all_provided) => {
                             debug!("(creating impl) trait with node_id `%d` \
                                     has provided methods", trait_did.node);
-                            // Selectively add only those provided
-                            // methods that aren't inherent to the
-                            // trait.
-
-                            // XXX: could probably be doing this with filter.
-                            methods = add_provided_methods(
-                                methods, all_provided,
+                            // Add all provided methods.
+                            add_provided_methods(
+                                &mut methods,
+                                all_provided.get(),
                                 self.crate_context.tcx.sess);
                         }
                     }
@@ -758,6 +779,41 @@ impl CoherenceChecker {
         }
     }
 
+    fn add_default_methods_for_external_trait(trait_def_id: ast::def_id) {
+        let tcx = self.crate_context.tcx;
+        let pmm = self.crate_context.coherence_info.provided_methods;
+
+        if pmm.contains_key(trait_def_id) { return; }
+
+        debug!("(adding default methods for trait) processing trait");
+
+        for csearch::get_provided_trait_methods(tcx,
+                                                trait_def_id).each |info| {
+            debug!("(adding default methods for trait) found default method");
+
+            // Create a new def ID for this provided method.
+            let parse_sess = &self.crate_context.tcx.sess.parse_sess;
+            let new_did = local_def(syntax::parse::next_node_id(*parse_sess));
+
+            let provided_method_info =
+                @ProvidedMethodInfo {
+                    method_info: @{
+                        did: new_did,
+                        n_tps: info.ty.tps.len(),
+                        ident: info.ty.ident,
+                        self_type: info.ty.self_ty
+                    },
+                    trait_method_def_id: info.def_id
+                };
+
+            let method_infos = @DVec();
+            method_infos.push(provided_method_info);
+            pmm.insert(trait_def_id, method_infos);
+        }
+    }
+
+    // Adds implementations and traits from external crates to the coherence
+    // info.
     fn add_external_crates() {
         let impls_seen = HashMap();
 
@@ -768,20 +824,28 @@ impl CoherenceChecker {
                                       { crate: crate_number, node: 0 });
 
             for each_path(crate_store, crate_number) |path_entry| {
-                let module_def_id;
                 match path_entry.def_like {
                     dl_def(def_mod(def_id)) => {
-                        module_def_id = def_id;
+                        self.add_impls_for_module(impls_seen,
+                                                  crate_store,
+                                                  def_id);
+                    }
+                    dl_def(def_ty(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);
+                            }
+                            _ => {}
+                        }
                     }
                     dl_def(_) | dl_impl(_) | dl_field => {
                         // Skip this.
                         loop;
                     }
                 }
-
-                self.add_impls_for_module(impls_seen,
-                                          crate_store,
-                                          module_def_id);
             }
         }
     }
@@ -789,7 +853,6 @@ impl CoherenceChecker {
 
 fn check_coherence(crate_context: @crate_ctxt, crate: @crate) {
     let coherence_checker = @CoherenceChecker(crate_context);
-    (*coherence_checker).build_provided_methods_map(crate);
     (*coherence_checker).check_coherence(crate);
 }
 
diff --git a/src/rustc/middle/typeck/collect.rs b/src/rustc/middle/typeck/collect.rs
index a38e69effdf..9e51225f172 100644
--- a/src/rustc/middle/typeck/collect.rs
+++ b/src/rustc/middle/typeck/collect.rs
@@ -212,9 +212,15 @@ fn ensure_trait_methods(ccx: @crate_ctxt, id: ast::node_id, trait_ty: ty::t) {
     match tcx.items.get(id) {
       ast_map::node_item(@{node: ast::item_trait(params, _, ms), _}, _) => {
         store_methods::<ast::trait_method>(ccx, id, ms, |m| {
+            let def_id;
+            match *m {
+                ast::required(ty_method) => def_id = local_def(ty_method.id),
+                ast::provided(method) => def_id = local_def(method.id)
+            }
+
             let trait_bounds = ty_param_bounds(ccx, params);
             let ty_m = trait_method_to_ty_method(*m);
-            let method_ty = ty_of_ty_method(ccx, ty_m, region_paramd);
+            let method_ty = ty_of_ty_method(ccx, ty_m, region_paramd, def_id);
             if ty_m.self_ty.node == ast::sty_static {
                 make_static_method_ty(ccx, ty_m, region_paramd,
                                       method_ty, trait_ty, trait_bounds);
@@ -373,7 +379,7 @@ fn check_methods_against_trait(ccx: @crate_ctxt,
 
               let provided_methods = ty::provided_trait_methods(tcx, did);
               match vec::find(provided_methods, |provided_method|
-                              provided_method.ident == trait_m.ident) {
+                              *provided_method == trait_m.ident) {
                 Some(_) => {
                     // If there's a provided method with the name we
                     // want, then we're fine; nothing else to do.
@@ -546,19 +552,22 @@ fn ty_of_method(ccx: @crate_ctxt,
                         m.purity, @~[],
                         m.decl, None, m.span),
      self_ty: m.self_ty.node,
-     vis: m.vis}
+     vis: m.vis,
+     def_id: local_def(m.id)}
 }
 
 fn ty_of_ty_method(self: @crate_ctxt,
                    m: ast::ty_method,
-                   rp: Option<ty::region_variance>) -> ty::method {
+                   rp: Option<ty::region_variance>,
+                   id: ast::def_id) -> ty::method {
     {ident: m.ident,
      tps: ty_param_bounds(self, m.tps),
      fty: ty_of_fn_decl(self, type_rscope(rp), ast::proto_bare, m.purity,
                         @~[], m.decl, None, m.span),
      // assume public, because this is only invoked on trait methods
      self_ty: m.self_ty.node,
-     vis: ast::public}
+     vis: ast::public,
+     def_id: id}
 }
 
 /*