Make supertrait methods callable on object types.

This requires changes to method search and to codegen. We now emit a
vtable for objects that includes methods from all supertraits.
Closes #4100.

Also, actually populate the cache for vtables, and also key it by type
so that it actually works.

10 files changed, 225 insertions, 170 deletions

diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index bca1a811a13..a22daac90b5 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -586,8 +586,13 @@ impl tr for method_origin {
                 }
             )
           }
-          typeck::method_trait(did, m) => {
-              typeck::method_trait(did.tr(xcx), m)
+          typeck::method_object(ref mo) => {
+            typeck::method_object(
+                typeck::method_object {
+                    trait_id: mo.trait_id.tr(xcx),
+                    .. *mo
+                }
+            )
           }
         }
     }
diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs
index 6a566f10f1e..222bef641d2 100644
--- a/src/librustc/middle/privacy.rs
+++ b/src/librustc/middle/privacy.rs
@@ -16,7 +16,7 @@ use metadata::csearch;
 use middle::ty::{ty_struct, ty_enum};
 use middle::ty;
 use middle::typeck::{method_map, method_origin, method_param};
-use middle::typeck::{method_static, method_trait};
+use middle::typeck::{method_static, method_object};
 
 use std::util::ignore;
 use syntax::ast::{decl_item, def, def_fn, def_id, def_static_method};
@@ -280,10 +280,14 @@ impl PrivacyVisitor {
             }
             method_param(method_param {
                 trait_id: trait_id,
-                 method_num: method_num,
+                method_num: method_num,
                  _
             }) |
-            method_trait(trait_id, method_num) => {
+            method_object(method_object {
+                trait_id: trait_id,
+                method_num: method_num,
+                 _
+            }) => {
                 if trait_id.crate == LOCAL_CRATE {
                     match self.tcx.items.find(&trait_id.node) {
                         Some(&node_item(item, _)) => {
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index 027696d37f1..d8c7b916a02 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -1015,6 +1015,8 @@ pub fn node_vtables(bcx: @mut Block, id: ast::NodeId)
     raw_vtables.map_move(|vts| resolve_vtables_in_fn_ctxt(bcx.fcx, *vts))
 }
 
+// Apply the typaram substitutions in the FunctionContext to some
+// vtables. This should eliminate any vtable_params.
 pub fn resolve_vtables_in_fn_ctxt(fcx: &FunctionContext, vts: typeck::vtable_res)
     -> typeck::vtable_res {
     resolve_vtables_under_param_substs(fcx.ccx.tcx,
@@ -1047,15 +1049,6 @@ pub fn resolve_param_vtables_under_param_substs(
 
 
 
-// Apply the typaram substitutions in the FunctionContext to a vtable. This should
-// eliminate any vtable_params.
-pub fn resolve_vtable_in_fn_ctxt(fcx: &FunctionContext, vt: &typeck::vtable_origin)
-    -> typeck::vtable_origin {
-    resolve_vtable_under_param_substs(fcx.ccx.tcx,
-                                      fcx.param_substs,
-                                      vt)
-}
-
 pub fn resolve_vtable_under_param_substs(tcx: ty::ctxt,
                                          param_substs: Option<@param_substs>,
                                          vt: &typeck::vtable_origin)
@@ -1081,8 +1074,8 @@ pub fn resolve_vtable_under_param_substs(tcx: ty::ctxt,
                 }
                 _ => {
                     tcx.sess.bug(fmt!(
-                        "resolve_vtable_in_fn_ctxt: asked to lookup but \
-                         no vtables in the fn_ctxt!"))
+                        "resolve_vtable_under_param_substs: asked to lookup \
+                         but no vtables in the fn_ctxt!"))
                 }
             }
         }
diff --git a/src/librustc/middle/trans/context.rs b/src/librustc/middle/trans/context.rs
index 5d0849ef12c..1318ef2c895 100644
--- a/src/librustc/middle/trans/context.rs
+++ b/src/librustc/middle/trans/context.rs
@@ -67,7 +67,7 @@ pub struct CrateContext {
      // Cache computed type parameter uses (see type_use.rs)
      type_use_cache: HashMap<ast::def_id, @~[type_use::type_uses]>,
      // Cache generated vtables
-     vtables: HashMap<mono_id, ValueRef>,
+     vtables: HashMap<(ty::t, mono_id), ValueRef>,
      // Cache of constant strings,
      const_cstr_cache: HashMap<@str, ValueRef>,
 
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index 9ffbafb706c..f4451d9c53f 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -186,10 +186,10 @@ pub fn trans_method_callee(bcx: @mut Block,
             }
         }
 
-        typeck::method_trait(_, off) => {
+        typeck::method_object(ref mt) => {
             trans_trait_callee(bcx,
                                callee_id,
-                               off,
+                               mt.real_index,
                                this)
         }
     }
@@ -398,7 +398,6 @@ pub fn combine_impl_and_methods_tps(bcx: @mut Block,
     return (ty_substs, vtables);
 }
 
-
 pub fn trans_trait_callee(bcx: @mut Block,
                           callee_id: ast::NodeId,
                           n_method: uint,
@@ -506,20 +505,35 @@ pub fn vtable_id(ccx: @mut CrateContext,
 /// This is used only for objects.
 pub fn get_vtable(bcx: @mut Block,
                   self_ty: ty::t,
-                  origin: typeck::vtable_origin)
+                  origins: typeck::vtable_param_res)
                   -> ValueRef {
-    let hash_id = vtable_id(bcx.ccx(), &origin);
-    match bcx.ccx().vtables.find(&hash_id) {
-        Some(&val) => val,
-        None => {
-            match origin {
-                typeck::vtable_static(id, substs, sub_vtables) => {
-                    make_impl_vtable(bcx, id, self_ty, substs, sub_vtables)
-                }
-                _ => fail!("get_vtable: expected a static origin"),
+    let ccx = bcx.ccx();
+    let _icx = push_ctxt("impl::get_vtable");
+
+    // Check the cache.
+    let hash_id = (self_ty, vtable_id(ccx, &origins[0]));
+    match ccx.vtables.find(&hash_id) {
+        Some(&val) => { return val }
+        None => { }
+    }
+
+    // Not in the cache. Actually build it.
+    let methods = do origins.flat_map |origin| {
+        match *origin {
+            typeck::vtable_static(id, ref substs, sub_vtables) => {
+                emit_vtable_methods(bcx, id, *substs, sub_vtables)
             }
+            _ => ccx.sess.bug("get_vtable: expected a static origin"),
         }
-    }
+    };
+
+    // Generate a type descriptor for the vtable.
+    let tydesc = get_tydesc(ccx, self_ty);
+    glue::lazily_emit_all_tydesc_glue(ccx, tydesc);
+
+    let vtable = make_vtable(ccx, tydesc, methods);
+    ccx.vtables.insert(hash_id, vtable);
+    return vtable;
 }
 
 /// Helper function to declare and initialize the vtable.
@@ -547,15 +561,12 @@ pub fn make_vtable(ccx: &mut CrateContext,
     }
 }
 
-/// Generates a dynamic vtable for objects.
-pub fn make_impl_vtable(bcx: @mut Block,
-                        impl_id: ast::def_id,
-                        self_ty: ty::t,
-                        substs: &[ty::t],
-                        vtables: typeck::vtable_res)
-                        -> ValueRef {
+fn emit_vtable_methods(bcx: @mut Block,
+                       impl_id: ast::def_id,
+                       substs: &[ty::t],
+                       vtables: typeck::vtable_res)
+                       -> ~[ValueRef] {
     let ccx = bcx.ccx();
-    let _icx = push_ctxt("impl::make_impl_vtable");
     let tcx = ccx.tcx;
 
     let trt_id = match ty::impl_trait_ref(tcx, impl_id) {
@@ -565,7 +576,7 @@ pub fn make_impl_vtable(bcx: @mut Block,
     };
 
     let trait_method_def_ids = ty::trait_method_def_ids(tcx, trt_id);
-    let methods = do trait_method_def_ids.map |method_def_id| {
+    do trait_method_def_ids.map |method_def_id| {
         let im = ty::method(tcx, *method_def_id);
         let fty = ty::subst_tps(tcx,
                                 substs,
@@ -583,13 +594,7 @@ pub fn make_impl_vtable(bcx: @mut Block,
             trans_fn_ref_with_vtables(bcx, m_id, 0,
                                       substs, Some(vtables)).llfn
         }
-    };
-
-    // Generate a type descriptor for the vtable.
-    let tydesc = get_tydesc(ccx, self_ty);
-    glue::lazily_emit_all_tydesc_glue(ccx, tydesc);
-
-    make_vtable(ccx, tydesc, methods)
+    }
 }
 
 pub fn trans_trait_cast(bcx: @mut Block,
@@ -621,9 +626,13 @@ pub fn trans_trait_cast(bcx: @mut Block,
     bcx = expr::trans_into(bcx, val, SaveIn(llboxdest));
 
     // Store the vtable into the pair or triple.
-    let orig = ccx.maps.vtable_map.get(&id)[0][0].clone();
-    let orig = resolve_vtable_in_fn_ctxt(bcx.fcx, &orig);
-    let vtable = get_vtable(bcx, v_ty, orig);
+    // This is structured a bit funny because of dynamic borrow failures.
+    let origins = {
+        let res = ccx.maps.vtable_map.get(&id);
+        let res = resolve_vtables_in_fn_ctxt(bcx.fcx, *res);
+        res[0]
+    };
+    let vtable = get_vtable(bcx, v_ty, origins);
     Store(bcx, vtable, PointerCast(bcx,
                                    GEPi(bcx, lldest, [0u, abi::trt_field_vtable]),
                                    val_ty(vtable).ptr_to()));
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 685699f7819..67bd8782497 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -59,6 +59,7 @@ pub struct field {
     mt: mt
 }
 
+#[deriving(Clone)]
 pub struct Method {
     ident: ast::ident,
     generics: ty::Generics,
@@ -3136,12 +3137,14 @@ pub fn method_call_type_param_defs(tcx: ctxt,
           typeck::method_param(typeck::method_param {
               trait_id: trt_id,
               method_num: n_mth, _}) |
-          typeck::method_trait(trt_id, n_mth) => {
+          typeck::method_object(typeck::method_object {
+              trait_id: trt_id,
+              method_num: n_mth, _}) => {
             // ...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 trait_type_param_defs =
-                ty::lookup_trait_def(tcx, trt_id).generics.type_param_defs;
+                lookup_trait_def(tcx, trt_id).generics.type_param_defs;
             @vec::append(
                 (*trait_type_param_defs).clone(),
                 *ty::trait_method(tcx,
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index 352836d81e4..c8d3bdaab28 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -90,7 +90,7 @@ use middle::typeck::check::vtable;
 use middle::typeck::check;
 use middle::typeck::infer;
 use middle::typeck::{method_map_entry, method_origin, method_param};
-use middle::typeck::{method_static, method_trait};
+use middle::typeck::{method_static, method_object};
 use middle::typeck::{param_numbered, param_self, param_index};
 use middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig;
 use util::common::indenter;
@@ -298,7 +298,7 @@ impl<'self> LookupContext<'self> {
         loop {
             match get(self_ty).sty {
                 ty_trait(did, ref substs, _, _, _) => {
-                    self.push_inherent_candidates_from_trait(did, substs);
+                    self.push_inherent_candidates_from_object(did, substs);
                     self.push_inherent_impl_candidates_for_type(did);
                 }
                 ty_enum(did, _) | ty_struct(did, _) => {
@@ -363,28 +363,40 @@ impl<'self> LookupContext<'self> {
         }
     }
 
-    fn push_inherent_candidates_from_trait(&self,
-                                               did: def_id,
-                                               substs: &ty::substs) {
-        debug!("push_inherent_candidates_from_trait(did=%s, substs=%s)",
-               self.did_to_str(did),
-               substs_to_str(self.tcx(), substs));
-        let _indenter = indenter();
-
+    // Determine the index of a method in the list of all methods belonging
+    // to a trait and its supertraits.
+    fn get_method_index(&self,
+                        trait_ref: @TraitRef,
+                        subtrait_id: ast::def_id,
+                        n_method: uint) -> uint {
         let tcx = self.tcx();
-        let ms = ty::trait_methods(tcx, did);
-        let index = match ms.iter().position(|m| m.ident == self.m_name) {
-            Some(i) => i,
-            None => { return; } // no method with the right name
-        };
-        let method = ms[index];
 
-        match method.explicit_self {
-            ast::sty_static => {
-                return; // not a method we can call with dot notation
+        // We need to figure the "real index" of the method in a
+        // listing of all the methods of an object. We do this by
+        // iterating down the supertraits of the object's trait until
+        // we find the trait the method came from, counting up the
+        // methods from them.
+        let mut method_count = 0;
+        do ty::each_bound_trait_and_supertraits(tcx, &[trait_ref])
+            |bound_ref| {
+            if bound_ref.def_id == subtrait_id { false }
+                else {
+                method_count += ty::trait_methods(tcx, bound_ref.def_id).len();
+                true
             }
-            _ => {}
-        }
+        };
+
+        return method_count + n_method;
+    }
+
+
+    fn push_inherent_candidates_from_object(&self,
+                                            did: def_id,
+                                            substs: &ty::substs) {
+        debug!("push_inherent_candidates_from_object(did=%s, substs=%s)",
+               self.did_to_str(did),
+               substs_to_str(self.tcx(), substs));
+        let _indenter = indenter();
 
         // It is illegal to invoke a method on a trait instance that
         // refers to the `self` type. An error will be reported by
@@ -392,24 +404,44 @@ impl<'self> LookupContext<'self> {
         // to the `Self` type. Substituting ty_err here allows
         // compiler to soldier on.
         //
-        // NOTE: `confirm_candidate()` also relies upon this substitution
+        // `confirm_candidate()` also relies upon this substitution
         // for Self. (fix)
         let rcvr_substs = substs {
             self_ty: Some(ty::mk_err()),
             ..(*substs).clone()
         };
-
-        self.inherent_candidates.push(Candidate {
-            rcvr_match_condition: RcvrMatchesIfObject(did),
-            rcvr_substs: rcvr_substs,
-            method_ty: method,
-            origin: method_trait(did, index)
-        });
+        let trait_ref = @TraitRef { def_id: did, substs: rcvr_substs.clone() };
+
+        do self.push_inherent_candidates_from_bounds_inner(&[trait_ref])
+            |trait_ref, m, method_num, _bound_num| {
+            let vtable_index =
+                self.get_method_index(trait_ref, trait_ref.def_id, method_num);
+            // We need to fix up the transformed self type.
+            let transformed_self_ty =
+                self.construct_transformed_self_ty_for_object(
+                    did, &rcvr_substs, m);
+            let m = @Method {
+                transformed_self_ty: Some(transformed_self_ty),
+                .. (*m).clone()
+            };
+
+            Candidate {
+                rcvr_match_condition: RcvrMatchesIfObject(did),
+                rcvr_substs: trait_ref.substs.clone(),
+                method_ty: m,
+                origin: method_object(method_object {
+                        trait_id: trait_ref.def_id,
+                        object_trait_id: did,
+                        method_num: method_num,
+                        real_index: vtable_index
+                    })
+            }
+        };
     }
 
     fn push_inherent_candidates_from_param(&self,
-                                               rcvr_ty: ty::t,
-                                               param_ty: param_ty) {
+                                           rcvr_ty: ty::t,
+                                           param_ty: param_ty) {
         debug!("push_inherent_candidates_from_param(param_ty=%?)",
                param_ty);
         let _indenter = indenter();
@@ -441,9 +473,34 @@ impl<'self> LookupContext<'self> {
     }
 
     fn push_inherent_candidates_from_bounds(&self,
-                                                self_ty: ty::t,
-                                                bounds: &[@TraitRef],
-                                                param: param_index) {
+                                            self_ty: ty::t,
+                                            bounds: &[@TraitRef],
+                                            param: param_index) {
+        do self.push_inherent_candidates_from_bounds_inner(bounds)
+            |trait_ref, m, method_num, bound_num| {
+            Candidate {
+                rcvr_match_condition: RcvrMatchesIfSubtype(self_ty),
+                rcvr_substs: trait_ref.substs.clone(),
+                method_ty: m,
+                origin: method_param(
+                                     method_param {
+                        trait_id: trait_ref.def_id,
+                        method_num: method_num,
+                        param_num: param,
+                        bound_num: bound_num,
+                    })
+            }
+        }
+    }
+
+    // Do a search through a list of bounds, using a callback to actually
+    // create the candidates.
+    fn push_inherent_candidates_from_bounds_inner(
+        &self,
+        bounds: &[@TraitRef],
+        mk_cand: &fn(trait_ref: @TraitRef, m: @ty::Method, method_num: uint,
+                     bound_num: uint) -> Candidate) {
+
         let tcx = self.tcx();
         let mut next_bound_idx = 0; // count only trait bounds
 
@@ -459,18 +516,8 @@ impl<'self> LookupContext<'self> {
                 Some(pos) => {
                     let method = trait_methods[pos];
 
-                    let cand = Candidate {
-                        rcvr_match_condition: RcvrMatchesIfSubtype(self_ty),
-                        rcvr_substs: bound_trait_ref.substs.clone(),
-                        method_ty: method,
-                        origin: method_param(
-                                             method_param {
-                                trait_id: bound_trait_ref.def_id,
-                                method_num: pos,
-                                param_num: param,
-                                bound_num: this_bound_idx,
-                            })
-                    };
+                    let cand = mk_cand(bound_trait_ref, method,
+                                       pos, this_bound_idx);
 
                     debug!("pushing inherent candidate for param: %?", cand);
                     self.inherent_candidates.push(cand);
@@ -879,7 +926,7 @@ impl<'self> LookupContext<'self> {
     fn confirm_candidate(&self, rcvr_ty: ty::t, candidate: &Candidate)
                              -> method_map_entry {
         let tcx = self.tcx();
-        let fty = self.fn_ty_from_origin(&candidate.origin);
+        let fty = ty::mk_bare_fn(tcx, candidate.method_ty.fty.clone());
 
         debug!("confirm_candidate(expr=%s, candidate=%s, fty=%s)",
                self.expr.repr(tcx),
@@ -891,17 +938,9 @@ impl<'self> LookupContext<'self> {
 
         // static methods should never have gotten this far:
         assert!(candidate.method_ty.explicit_self != sty_static);
-
-        let transformed_self_ty = match candidate.origin {
-            method_trait(trait_def_id, _) => {
-                self.construct_transformed_self_ty_for_object(
-                    trait_def_id, candidate)
-            }
-            _ => {
-                let t = candidate.method_ty.transformed_self_ty.unwrap();
-                ty::subst(tcx, &candidate.rcvr_substs, t)
-            }
-        };
+        let transformed_self_ty =
+            ty::subst(tcx, &candidate.rcvr_substs,
+                      candidate.method_ty.transformed_self_ty.unwrap());
 
         // Determine the values for the type parameters of the method.
         // If they were not explicitly supplied, just construct fresh
@@ -992,9 +1031,11 @@ impl<'self> LookupContext<'self> {
         }
     }
 
-    fn construct_transformed_self_ty_for_object(&self,
-                                                trait_def_id: ast::def_id,
-                                                candidate: &Candidate) -> ty::t
+    fn construct_transformed_self_ty_for_object(
+        &self,
+        trait_def_id: ast::def_id,
+        rcvr_substs: &ty::substs,
+        method_ty: &ty::Method) -> ty::t
     {
         /*!
          * This is a bit tricky. We have a match against a trait method
@@ -1010,17 +1051,17 @@ impl<'self> LookupContext<'self> {
          * result to be `&'a Foo`. Assuming that `m_method` is being
          * called, we want the result to be `@mut Foo`. Of course,
          * this transformation has already been done as part of
-         * `candidate.method_ty.transformed_self_ty`, but there the
+         * `method_ty.transformed_self_ty`, but there the
          * type is expressed in terms of `Self` (i.e., `&'a Self`, `@mut Self`).
          * Because objects are not standalone types, we can't just substitute
          * `s/Self/Foo/`, so we must instead perform this kind of hokey
          * match below.
          */
 
-        let substs = ty::substs {regions: candidate.rcvr_substs.regions.clone(),
+        let substs = ty::substs {regions: rcvr_substs.regions.clone(),
                                  self_ty: None,
-                                 tps: candidate.rcvr_substs.tps.clone()};
-        match candidate.method_ty.explicit_self {
+                                 tps: rcvr_substs.tps.clone()};
+        match method_ty.explicit_self {
             ast::sty_static => {
                 self.bug(~"static method for object type receiver");
             }
@@ -1029,7 +1070,7 @@ impl<'self> LookupContext<'self> {
             }
             ast::sty_region(*) | ast::sty_box(*) | ast::sty_uniq(*) => {
                 let transformed_self_ty =
-                    candidate.method_ty.transformed_self_ty.clone().unwrap();
+                    method_ty.transformed_self_ty.clone().unwrap();
                 match ty::get(transformed_self_ty).sty {
                     ty::ty_rptr(r, mt) => { // must be sty_region
                         ty::mk_trait(self.tcx(), trait_def_id,
@@ -1072,7 +1113,7 @@ impl<'self> LookupContext<'self> {
             method_static(*) | method_param(*) => {
                 return; // not a call to a trait instance
             }
-            method_trait(*) => {}
+            method_object(*) => {}
         }
 
         match candidate.method_ty.explicit_self {
@@ -1117,7 +1158,7 @@ impl<'self> LookupContext<'self> {
             // XXX: does this properly enforce this on everything now
             // that self has been merged in? -sully
             method_param(method_param { trait_id: trait_id, _ }) |
-            method_trait(trait_id, _) => {
+            method_object(method_object { trait_id: trait_id, _ }) => {
                 bad = self.tcx().destructor_for_type.contains_key(&trait_id);
             }
         }
@@ -1235,27 +1276,6 @@ impl<'self> LookupContext<'self> {
         }
     }
 
-    fn fn_ty_from_origin(&self, origin: &method_origin) -> ty::t {
-        return match *origin {
-            method_static(did) => {
-                ty::lookup_item_type(self.tcx(), did).ty
-            }
-            method_param(ref mp) => {
-                type_of_trait_method(self.tcx(), mp.trait_id, mp.method_num)
-            }
-            method_trait(did, idx) => {
-                type_of_trait_method(self.tcx(), did, idx)
-            }
-        };
-
-        fn type_of_trait_method(tcx: ty::ctxt,
-                                trait_did: def_id,
-                                method_num: uint) -> ty::t {
-            let trait_methods = ty::trait_methods(tcx, trait_did);
-            ty::mk_bare_fn(tcx, trait_methods[method_num].fty.clone())
-        }
-    }
-
     fn report_candidate(&self, idx: uint, origin: &method_origin) {
         match *origin {
             method_static(impl_did) => {
@@ -1264,8 +1284,8 @@ impl<'self> LookupContext<'self> {
             method_param(ref mp) => {
                 self.report_param_candidate(idx, (*mp).trait_id)
             }
-            method_trait(trait_did, _) => {
-                self.report_trait_candidate(idx, trait_did)
+            method_object(ref mo) => {
+                self.report_trait_candidate(idx, mo.trait_id)
             }
         }
     }
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index 37f4a6ba497..cd69a642b72 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -647,30 +647,21 @@ pub fn early_resolve_expr(ex: @ast::expr,
                                   self_ty: Some(mt.ty)
                               }
                           };
-                          let vtable_opt =
-                              lookup_vtable(&vcx,
-                                            location_info,
-                                            mt.ty,
-                                            target_trait_ref,
-                                            is_early);
-                          match vtable_opt {
-                              Some(vtable) => {
-                                  // Map this expression to that
-                                  // vtable (that is: "ex has vtable
-                                  // <vtable>")
-                                  if !is_early {
-                                      insert_vtables(fcx, ex.id,
-                                                     @~[@~[vtable]]);
-                                  }
-                              }
-                              None => {
-                                  fcx.tcx().sess.span_err(
-                                      ex.span,
-                                      fmt!("failed to find an implementation \
-                                            of trait %s for %s",
-                                           fcx.infcx().ty_to_str(target_ty),
-                                           fcx.infcx().ty_to_str(mt.ty)));
-                              }
+
+                          let param_bounds = ty::ParamBounds {
+                              builtin_bounds: ty::EmptyBuiltinBounds(),
+                              trait_bounds: ~[target_trait_ref]
+                          };
+                          let vtables =
+                                lookup_vtables_for_param(&vcx,
+                                                         location_info,
+                                                         None,
+                                                         &param_bounds,
+                                                         mt.ty,
+                                                         is_early);
+
+                          if !is_early {
+                              insert_vtables(fcx, ex.id, @~[vtables]);
                           }
 
                           // Now, if this is &trait, we need to link the
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index 61027519b5b..a8a3701e4a5 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -88,7 +88,7 @@ pub enum method_origin {
     method_param(method_param),
 
     // method invoked on a trait instance
-    method_trait(ast::def_id, uint),
+    method_object(method_object),
 
 }
 
@@ -110,6 +110,26 @@ pub struct method_param {
     bound_num: uint,
 }
 
+// details for a method invoked with a receiver whose type is an object
+#[deriving(Clone, Encodable, Decodable)]
+pub struct method_object {
+    // the (super)trait containing the method to be invoked
+    trait_id: ast::def_id,
+
+    // the actual base trait id of the object
+    object_trait_id: ast::def_id,
+
+    // index of the method to be invoked amongst the trait's methods
+    method_num: uint,
+
+    // index into the actual runtime vtable.
+    // the vtable is formed by concatenating together the method lists of
+    // the base object trait and all supertraits;  this is the index into
+    // that vtable
+    real_index: uint,
+}
+
+
 #[deriving(Clone)]
 pub struct method_map_entry {
     // the type of the self parameter, which is not reflected in the fn type
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 5ba52326579..0fdcac26ac8 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -747,8 +747,8 @@ impl Repr for typeck::method_origin {
             &typeck::method_param(ref p) => {
                 p.repr(tcx)
             }
-            &typeck::method_trait(def_id, n) => {
-                fmt!("method_trait(%s, %?)", def_id.repr(tcx), n)
+            &typeck::method_object(ref p) => {
+                p.repr(tcx)
             }
         }
     }
@@ -764,6 +764,16 @@ impl Repr for typeck::method_param {
     }
 }
 
+impl Repr for typeck::method_object {
+    fn repr(&self, tcx: ctxt) -> ~str {
+        fmt!("method_object(%s,%?,%?)",
+             self.trait_id.repr(tcx),
+             self.method_num,
+             self.real_index)
+    }
+}
+
+
 impl Repr for ty::RegionVid {
     fn repr(&self, _tcx: ctxt) -> ~str {
         fmt!("%?", *self)