Combine the vtable_origins from impl + method.

Not as clean as it could be, but fixes #3314.

7 files changed, 265 insertions, 84 deletions

diff --git a/src/rustc/middle/trans/callee.rs b/src/rustc/middle/trans/callee.rs
index a92f8c9adf6..874eb86a18c 100644
--- a/src/rustc/middle/trans/callee.rs
+++ b/src/rustc/middle/trans/callee.rs
@@ -120,21 +120,18 @@ fn trans_fn_ref_to_callee(bcx: block,
 fn trans_fn_ref(bcx: block,
                 def_id: ast::def_id,
                 ref_id: ast::node_id) -> FnData {
-    //!
-    //
-    // Translates a reference (with id `ref_id`) to the fn/method
-    // with id `def_id` into a function pointer.  This may require
-    // monomorphization or inlining.
+    /*!
+     *
+     * Translates a reference (with id `ref_id`) to the fn/method
+     * with id `def_id` into a function pointer.  This may require
+     * monomorphization or inlining. */
 
     let _icx = bcx.insn_ctxt("trans_fn");
 
     let type_params = node_id_type_params(bcx, ref_id);
 
-    let raw_vtables = bcx.ccx().maps.vtable_map.find(ref_id);
-    let resolved_vtables = raw_vtables.map(
-        |vts| impl::resolve_vtables_in_fn_ctxt(bcx.fcx, vts));
-    trans_fn_ref_with_vtables(bcx, def_id, ref_id, type_params,
-                              resolved_vtables)
+    let vtables = node_vtables(bcx, ref_id);
+    trans_fn_ref_with_vtables(bcx, def_id, ref_id, type_params, vtables)
 }
 
 fn trans_fn_ref_with_vtables_to_callee(bcx: block,
@@ -174,6 +171,13 @@ fn trans_fn_ref_with_vtables(
     let ccx = bcx.ccx();
     let tcx = ccx.tcx;
 
+    debug!("trans_fn_ref_with_vtables(bcx=%s, def_id=%?, ref_id=%?, \
+            type_params=%?, vtables=%?)",
+           bcx.to_str(), def_id, ref_id,
+           type_params.map(|t| bcx.ty_to_str(t)),
+           vtables);
+    let _indenter = indenter();
+
     // Polytype of the function item (may have type params)
     let fn_tpt = ty::lookup_item_type(tcx, def_id);
 
diff --git a/src/rustc/middle/trans/common.rs b/src/rustc/middle/trans/common.rs
index 75007312e11..064b3006431 100644
--- a/src/rustc/middle/trans/common.rs
+++ b/src/rustc/middle/trans/common.rs
@@ -187,6 +187,13 @@ type param_substs = {tys: ~[ty::t],
                      vtables: Option<typeck::vtable_res>,
                      bounds: @~[ty::param_bounds]};
 
+fn param_substs_to_str(tcx: ty::ctxt, substs: &param_substs) -> ~str {
+    fmt!("param_substs {tys:%?, vtables:%?, bounds:%?}",
+         substs.tys.map(|t| ty_to_str(tcx, t)),
+         substs.vtables.map(|vs| vs.map(|v| v.to_str(tcx))),
+         substs.bounds.map(|b| ty::param_bounds_to_str(tcx, b)))
+}
+
 // Function context.  Every LLVM function we create will have one of
 // these.
 type fn_ctxt = @{
@@ -1181,9 +1188,11 @@ fn node_id_type(bcx: block, id: ast::node_id) -> ty::t {
       _ => { assert !ty::type_has_params(t); t }
     }
 }
+
 fn expr_ty(bcx: block, ex: @ast::expr) -> ty::t {
     node_id_type(bcx, ex.id)
 }
+
 fn node_id_type_params(bcx: block, id: ast::node_id) -> ~[ty::t] {
     let tcx = bcx.tcx();
     let params = ty::node_id_to_type_params(tcx, id);
@@ -1195,6 +1204,71 @@ fn node_id_type_params(bcx: block, id: ast::node_id) -> ~[ty::t] {
     }
 }
 
+fn node_vtables(bcx: block, id: ast::node_id) -> Option<typeck::vtable_res> {
+    let raw_vtables = bcx.ccx().maps.vtable_map.find(id);
+    raw_vtables.map(
+        |vts| impl::resolve_vtables_in_fn_ctxt(bcx.fcx, vts))
+}
+
+fn resolve_vtables_in_fn_ctxt(fcx: fn_ctxt, vts: typeck::vtable_res)
+    -> typeck::vtable_res
+{
+    @vec::map(*vts, |d| resolve_vtable_in_fn_ctxt(fcx, d))
+}
+
+// Apply the typaram substitutions in the fn_ctxt to a vtable. This should
+// eliminate any vtable_params.
+fn resolve_vtable_in_fn_ctxt(fcx: fn_ctxt, vt: typeck::vtable_origin)
+    -> typeck::vtable_origin
+{
+    let tcx = fcx.ccx.tcx;
+    match vt {
+        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))
+                }
+                _ => tys
+            };
+            typeck::vtable_static(trait_id, tys,
+                                  resolve_vtables_in_fn_ctxt(fcx, sub))
+        }
+        typeck::vtable_param(n_param, n_bound) => {
+            match fcx.param_substs {
+                Some(ref substs) => {
+                    find_vtable(tcx, substs, n_param, n_bound)
+                }
+                _ => {
+                    tcx.sess.bug(fmt!(
+                        "resolve_vtable_in_fn_ctxt: asked to lookup %? but \
+                         no vtables in the fn_ctxt!", vt))
+                }
+            }
+        }
+        _ => vt
+    }
+}
+
+fn find_vtable(tcx: ty::ctxt, ps: &param_substs,
+               n_param: uint, n_bound: uint)
+    -> typeck::vtable_origin
+{
+    debug!("find_vtable_in_fn_ctxt(n_param=%u, n_bound=%u, ps=%?)",
+           n_param, n_bound, param_substs_to_str(tcx, ps));
+
+    let mut vtable_off = n_bound, i = 0u;
+    // Vtables are stored in a flat array, finding the right one is
+    // somewhat awkward
+    for vec::each(*ps.bounds) |bounds| {
+        if i >= n_param { break; }
+        for vec::each(*bounds) |bound| {
+            match bound { ty::bound_trait(_) => vtable_off += 1u, _ => () }
+        }
+        i += 1u;
+    }
+    option::get(ps.vtables)[vtable_off]
+}
+
 fn dummy_substs(tps: ~[ty::t]) -> ty::substs {
     {self_r: Some(ty::re_bound(ty::br_self)),
      self_ty: None,
diff --git a/src/rustc/middle/trans/impl.rs b/src/rustc/middle/trans/impl.rs
index ae128a10f7c..f821d74af06 100644
--- a/src/rustc/middle/trans/impl.rs
+++ b/src/rustc/middle/trans/impl.rs
@@ -134,8 +134,8 @@ fn trans_method_callee(bcx: block, callee_id: ast::node_id,
         typeck::method_param({trait_id:trait_id, method_num:off,
                               param_num:p, bound_num:b}) => {
             match bcx.fcx.param_substs {
-                Some(substs) => {
-                    let vtbl = find_vtable_in_fn_ctxt(substs, p, b);
+                Some(ref substs) => {
+                    let vtbl = base::find_vtable(bcx.tcx(), substs, p, b);
                     trans_monomorphized_callee(bcx, callee_id, self, mentry,
                                                trait_id, off, vtbl)
                 }
@@ -177,19 +177,17 @@ fn trans_static_method_callee(bcx: block,
         bcx.fcx, ccx.maps.vtable_map.get(callee_id));
 
     match vtbls[0] { // is index 0 always the one we want?
-        typeck::vtable_static(impl_did, impl_substs, sub_origins) => {
+        typeck::vtable_static(impl_did, rcvr_substs, rcvr_origins) => {
 
             let mth_id = method_with_name(bcx.ccx(), impl_did, mname);
-            let n_m_tps = method_ty_param_count(ccx, mth_id, impl_did);
-            let node_substs = node_id_type_params(bcx, callee_id);
-            let ty_substs
-                = vec::append(impl_substs,
-                              vec::tailn(node_substs,
-                                         node_substs.len() - n_m_tps));
+            let callee_substs = combine_impl_and_methods_tps(
+                bcx, mth_id, impl_did, callee_id, rcvr_substs);
+            let callee_origins = combine_impl_and_methods_origins(
+                bcx, mth_id, impl_did, callee_id, rcvr_origins);
 
             let FnData {llfn: lval} =
                 trans_fn_ref_with_vtables(bcx, mth_id, callee_id,
-                                          ty_substs, Some(sub_origins));
+                                          callee_substs, Some(callee_origins));
 
             let callee_ty = node_id_type(bcx, callee_id);
             let llty = T_ptr(type_of_fn_from_ty(ccx, callee_ty));
@@ -248,8 +246,8 @@ fn trans_monomorphized_callee(bcx: block,
     -> Callee
 {
     let _icx = bcx.insn_ctxt("impl::trans_monomorphized_callee");
-    match vtbl {
-      typeck::vtable_static(impl_did, impl_substs, sub_origins) => {
+    return match vtbl {
+      typeck::vtable_static(impl_did, rcvr_substs, rcvr_origins) => {
           let ccx = bcx.ccx();
           let mname = ty::trait_methods(ccx.tcx, trait_id)[n_method].ident;
           let mth_id = method_with_name(bcx.ccx(), impl_did, mname);
@@ -260,20 +258,14 @@ fn trans_monomorphized_callee(bcx: block,
 
           // create a concatenated set of substitutions which includes
           // those from the impl and those from the method:
-          let n_m_tps = method_ty_param_count(ccx, mth_id, impl_did);
-          let node_substs = node_id_type_params(bcx, callee_id);
-          let ty_substs
-              = vec::append(impl_substs,
-                            vec::tailn(node_substs,
-                                       node_substs.len() - n_m_tps));
-          debug!("n_m_tps=%?", n_m_tps);
-          debug!("impl_substs=%?", impl_substs.map(|t| bcx.ty_to_str(t)));
-          debug!("node_substs=%?", node_substs.map(|t| bcx.ty_to_str(t)));
-          debug!("ty_substs=%?", ty_substs.map(|t| bcx.ty_to_str(t)));
+          let callee_substs = combine_impl_and_methods_tps(
+              bcx, mth_id, impl_did, callee_id, rcvr_substs);
+          let callee_origins = combine_impl_and_methods_origins(
+              bcx, mth_id, impl_did, callee_id, rcvr_origins);
 
           // translate the function
           let callee = trans_fn_ref_with_vtables(
-              bcx, mth_id, callee_id, ty_substs, Some(sub_origins));
+              bcx, mth_id, callee_id, callee_substs, Some(callee_origins));
 
           // create a llvalue that represents the fn ptr
           let fn_ty = node_id_type(bcx, callee_id);
@@ -297,9 +289,99 @@ fn trans_monomorphized_callee(bcx: block,
       typeck::vtable_param(*) => {
           fail ~"vtable_param left in monomorphized function's vtable substs";
       }
-    }
+    };
+
+}
+
+fn combine_impl_and_methods_tps(bcx: block,
+                                mth_did: ast::def_id,
+                                impl_did: ast::def_id,
+                                callee_id: ast::node_id,
+                                rcvr_substs: ~[ty::t])
+    -> ~[ty::t]
+{
+    /*!
+    *
+    * Creates a concatenated set of substitutions which includes
+    * those from the impl and those from the method.  This are
+    * some subtle complications here.  Statically, we have a list
+    * of type parameters like `[T0, T1, T2, M1, M2, M3]` where
+    * `Tn` are type parameters that appear on the receiver.  For
+    * example, if the receiver is a method parameter `A` with a
+    * bound like `trait<B,C,D>` then `Tn` would be `[B,C,D]`.
+    *
+    * The weird part is that the type `A` might now be bound to
+    * any other type, such as `foo<X>`.  In that case, the vector
+    * we want is: `[X, M1, M2, M3]`.  Therefore, what we do now is
+    * to slice off the method type parameters and append them to
+    * the type parameters from the type that the receiver is
+    * mapped to. */
+
+    let ccx = bcx.ccx();
+    let n_m_tps = method_ty_param_count(ccx, mth_did, impl_did);
+    let node_substs = node_id_type_params(bcx, callee_id);
+    let ty_substs
+        = vec::append(rcvr_substs,
+                      vec::tailn(node_substs,
+                                 node_substs.len() - n_m_tps));
+    debug!("n_m_tps=%?", n_m_tps);
+    debug!("rcvr_substs=%?", rcvr_substs.map(|t| bcx.ty_to_str(t)));
+    debug!("node_substs=%?", node_substs.map(|t| bcx.ty_to_str(t)));
+    debug!("ty_substs=%?", ty_substs.map(|t| bcx.ty_to_str(t)));
+
+    return ty_substs;
+}
+
+fn combine_impl_and_methods_origins(bcx: block,
+                                    mth_did: ast::def_id,
+                                    impl_did: ast::def_id,
+                                    callee_id: ast::node_id,
+                                    rcvr_origins: typeck::vtable_res)
+    -> typeck::vtable_res
+{
+    /*!
+     *
+     * Similar to `combine_impl_and_methods_tps`, but for vtables.
+     * This is much messier because of the flattened layout we are
+     * currently using (for some reason that I fail to understand).
+     * The proper fix is described in #3446.
+     */
+
+
+    // Find the bounds for the method, which are the tail of the
+    // bounds found in the item type, as the item type combines the
+    // rcvr + method bounds.
+    let ccx = bcx.ccx(), tcx = bcx.tcx();
+    let n_m_tps = method_ty_param_count(ccx, mth_did, impl_did);
+    let {bounds: r_m_bounds, _} = ty::lookup_item_type(tcx, mth_did);
+    let n_r_m_tps = r_m_bounds.len(); // rcvr + method tps
+    let m_boundss = vec::view(*r_m_bounds, n_r_m_tps - n_m_tps, n_r_m_tps);
+
+    // Flatten out to find the number of vtables the method expects.
+    let m_vtables = m_boundss.foldl(0, |sum, m_bounds| {
+        m_bounds.foldl(sum, |sum, m_bound| {
+            sum + match m_bound {
+                ty::bound_copy | ty::bound_owned |
+                ty::bound_send | ty::bound_const => 0,
+                ty::bound_trait(_) => 1
+            }
+        })
+    });
+
+    // Find the vtables we computed at type check time and monomorphize them
+    let r_m_origins = match node_vtables(bcx, callee_id) {
+        Some(vt) => vt,
+        None => @~[]
+    };
+
+    // Extract those that belong to method:
+    let m_origins = vec::tailn(*r_m_origins, r_m_origins.len() - m_vtables);
+
+    // Combine rcvr + method to find the final result:
+    @vec::append(*rcvr_origins, m_origins)
 }
 
+
 fn trans_trait_callee(bcx: block,
                       callee_id: ast::node_id,
                       n_method: uint,
@@ -367,54 +449,6 @@ fn trans_trait_callee_from_llval(bcx: block,
     };
 }
 
-fn find_vtable_in_fn_ctxt(ps: param_substs, n_param: uint, n_bound: uint)
-    -> typeck::vtable_origin
-{
-    let mut vtable_off = n_bound, i = 0u;
-    // Vtables are stored in a flat array, finding the right one is
-    // somewhat awkward
-    for vec::each(*ps.bounds) |bounds| {
-        if i >= n_param { break; }
-        for vec::each(*bounds) |bound| {
-            match bound { ty::bound_trait(_) => vtable_off += 1u, _ => () }
-        }
-        i += 1u;
-    }
-    option::get(ps.vtables)[vtable_off]
-}
-
-fn resolve_vtables_in_fn_ctxt(fcx: fn_ctxt, vts: typeck::vtable_res)
-    -> typeck::vtable_res {
-    @vec::map(*vts, |d| resolve_vtable_in_fn_ctxt(fcx, d))
-}
-
-// Apply the typaram substitutions in the fn_ctxt to a vtable. This should
-// eliminate any vtable_params.
-fn resolve_vtable_in_fn_ctxt(fcx: fn_ctxt, vt: typeck::vtable_origin)
-    -> typeck::vtable_origin {
-    match vt {
-      typeck::vtable_static(trait_id, tys, sub) => {
-        let tys = match fcx.param_substs {
-          Some(substs) => {
-            vec::map(tys, |t| ty::subst_tps(fcx.ccx.tcx, substs.tys, t))
-          }
-          _ => tys
-        };
-        typeck::vtable_static(trait_id, tys,
-                              resolve_vtables_in_fn_ctxt(fcx, sub))
-      }
-      typeck::vtable_param(n_param, n_bound) => {
-        match fcx.param_substs {
-          Some(substs) => {
-            find_vtable_in_fn_ctxt(substs, n_param, n_bound)
-          }
-          _ => fail ~"resolve_vtable_in_fn_ctxt: no substs"
-        }
-      }
-      _ => vt
-    }
-}
-
 fn vtable_id(ccx: @crate_ctxt, origin: typeck::vtable_origin) -> mono_id {
     match origin {
         typeck::vtable_static(impl_id, substs, sub_vtables) => {
diff --git a/src/rustc/middle/ty.rs b/src/rustc/middle/ty.rs
index b8d610e7a15..4a322a74cec 100644
--- a/src/rustc/middle/ty.rs
+++ b/src/rustc/middle/ty.rs
@@ -156,6 +156,7 @@ export ck_block;
 export ck_box;
 export ck_uniq;
 export param_bound, param_bounds, bound_copy, bound_owned;
+export param_bounds_to_str, param_bound_to_str;
 export bound_send, bound_trait;
 export param_bounds_to_kind;
 export default_arg_mode_for_ty;
@@ -1338,6 +1339,20 @@ fn substs_to_str(cx: ctxt, substs: &substs) -> ~str {
          substs.tps.map(|t| ty_to_str(cx, t)))
 }
 
+fn param_bound_to_str(cx: ctxt, pb: &param_bound) -> ~str {
+    match *pb {
+        bound_copy => ~"copy",
+        bound_owned => ~"owned",
+        bound_send => ~"send",
+        bound_const => ~"const",
+        bound_trait(t) => ty_to_str(cx, t)
+    }
+}
+
+fn param_bounds_to_str(cx: ctxt, pbs: param_bounds) -> ~str {
+    fmt!("%?", pbs.map(|pb| param_bound_to_str(cx, &pb)))
+}
+
 fn subst(cx: ctxt,
          substs: &substs,
          typ: t) -> t {
diff --git a/src/rustc/middle/typeck.rs b/src/rustc/middle/typeck.rs
index 39d4a64f19f..4dfa17a9034 100644
--- a/src/rustc/middle/typeck.rs
+++ b/src/rustc/middle/typeck.rs
@@ -150,6 +150,29 @@ enum vtable_origin {
     vtable_trait(ast::def_id, ~[ty::t]),
 }
 
+impl vtable_origin {
+    fn to_str(tcx: ty::ctxt) -> ~str {
+        match self {
+            vtable_static(def_id, ref tys, ref vtable_res) => {
+                fmt!("vtable_static(%?:%s, %?, %?)",
+                     def_id, ty::item_path_str(tcx, def_id),
+                     tys,
+                     vtable_res.map(|o| o.to_str(tcx)))
+            }
+
+            vtable_param(x, y) => {
+                fmt!("vtable_param(%?, %?)", x, y)
+            }
+
+            vtable_trait(def_id, ref tys) => {
+                fmt!("vtable_trait(%?:%s, %?)",
+                     def_id, ty::item_path_str(tcx, def_id),
+                     tys.map(|t| ty_to_str(tcx, t)))
+            }
+        }
+    }
+}
+
 type vtable_map = hashmap<ast::node_id, vtable_res>;
 
 // Stores information about provided methods, aka "default methods" in traits.
@@ -182,6 +205,8 @@ fn write_substs_to_tcx(tcx: ty::ctxt,
                        node_id: ast::node_id,
                        +substs: ~[ty::t]) {
     if substs.len() > 0u {
+        debug!("write_substs_to_tcx(%d, %?)", node_id,
+               substs.map(|t| ty_to_str(tcx, t)));
         tcx.node_type_substs.insert(node_id, substs);
     }
 }
diff --git a/src/rustc/middle/typeck/check.rs b/src/rustc/middle/typeck/check.rs
index 677a7a444f0..4d4409e499c 100644
--- a/src/rustc/middle/typeck/check.rs
+++ b/src/rustc/middle/typeck/check.rs
@@ -76,6 +76,7 @@ use rscope::{in_binding_rscope, region_scope, type_rscope,
 use syntax::ast::ty_i;
 use typeck::infer::{resolve_type, force_tvar};
 use result::{Result, Ok, Err};
+use syntax::print::pprust;
 
 use std::map::{str_hash, uint_hash};
 
@@ -587,9 +588,16 @@ impl @fn_ctxt: region_scope {
 
 impl @fn_ctxt {
     fn tag() -> ~str { fmt!("%x", ptr::addr_of(*self) as uint) }
+
+    fn expr_to_str(expr: @ast::expr) -> ~str {
+        fmt!("expr(%?:%s)", expr.id,
+             pprust::expr_to_str(expr, self.tcx().sess.intr()))
+    }
+
     fn block_region() -> ty::region {
         ty::re_scope(self.region_lb)
     }
+
     #[inline(always)]
     fn write_ty(node_id: ast::node_id, ty: ty::t) {
         debug!("write_ty(%d, %s) in fcx %s",
@@ -598,6 +606,10 @@ impl @fn_ctxt {
     }
     fn write_substs(node_id: ast::node_id, +substs: ty::substs) {
         if !ty::substs_is_noop(&substs) {
+            debug!("write_substs(%d, %s) in fcx %s",
+                   node_id,
+                   ty::substs_to_str(self.tcx(), &substs),
+                   self.tag());
             self.inh.node_type_substs.insert(node_id, substs);
         }
     }
diff --git a/src/rustc/middle/typeck/check/vtable.rs b/src/rustc/middle/typeck/check/vtable.rs
index 1a9925c3618..6feffc9c067 100644
--- a/src/rustc/middle/typeck/check/vtable.rs
+++ b/src/rustc/middle/typeck/check/vtable.rs
@@ -34,7 +34,16 @@ fn lookup_vtables(fcx: @fn_ctxt,
                   bounds: @~[ty::param_bounds],
                   substs: &ty::substs,
                   allow_unsafe: bool,
-                  is_early: bool) -> vtable_res {
+                  is_early: bool) -> vtable_res
+{
+    debug!("lookup_vtables(expr=%?/%s, \
+            # bounds=%?, \
+            substs=%s",
+           expr.id, fcx.expr_to_str(expr),
+           bounds.len(),
+           ty::substs_to_str(fcx.tcx(), substs));
+    let _i = indenter();
+
     let tcx = fcx.ccx.tcx;
     let mut result = ~[], i = 0u;
     for substs.tps.each |ty| {
@@ -391,6 +400,12 @@ fn connect_trait_tps(fcx: @fn_ctxt, expr: @ast::expr, impl_tys: ~[ty::t],
     }
 }
 
+fn insert_vtables(ccx: @crate_ctxt, callee_id: ast::node_id, vtables: vtable_res) {
+    debug!("insert_vtables(callee_id=%d, vtables=%?)",
+           callee_id, vtables.map(|v| v.to_str(ccx.tcx)));
+    ccx.vtable_map.insert(callee_id, vtables);
+}
+
 fn early_resolve_expr(ex: @ast::expr, &&fcx: @fn_ctxt, is_early: bool) {
     debug!("vtable: early_resolve_expr() ex with id %? (early: %b): %s",
            ex.id, is_early, expr_to_str(ex, fcx.tcx().sess.intr()));
@@ -424,7 +439,9 @@ fn early_resolve_expr(ex: @ast::expr, &&fcx: @fn_ctxt, is_early: bool) {
                 let substs = fcx.node_ty_substs(callee_id);
                 let vtbls = lookup_vtables(fcx, ex, bounds,
                                            &substs, false, is_early);
-                if !is_early { cx.vtable_map.insert(callee_id, vtbls); }
+                if !is_early {
+                    insert_vtables(cx, callee_id, vtbls);
+                }
             }
           }
           None => ()