More work on translating dictionary-passing

Reached a point where simple uses of interfaces without bounds work.

Issue #1227

8 files changed, 387 insertions, 162 deletions

diff --git a/src/comp/driver/driver.rs b/src/comp/driver/driver.rs
index ee8c36c3c8d..b8a6ba28729 100644
--- a/src/comp/driver/driver.rs
+++ b/src/comp/driver/driver.rs
@@ -173,8 +173,9 @@ fn compile_input(sess: session::session, cfg: ast::crate_cfg, input: str,
     time(time_passes, "const checking",
          bind middle::check_const::check_crate(sess, crate));
     let ty_cx = ty::mk_ctxt(sess, def_map, ast_map, freevars);
-    let method_map = time(time_passes, "typechecking",
-                          bind typeck::check_crate(ty_cx, impl_map, crate));
+    let (method_map, dict_map) =
+        time(time_passes, "typechecking",
+             bind typeck::check_crate(ty_cx, impl_map, crate));
     time(time_passes, "block-use checking",
          bind middle::block_use::check_crate(ty_cx, crate));
     time(time_passes, "function usage",
@@ -202,7 +203,7 @@ fn compile_input(sess: session::session, cfg: ast::crate_cfg, input: str,
              bind trans::trans_crate(sess, crate, ty_cx,
                                      outputs.obj_filename, exp_map, ast_map,
                                      mut_map, copy_map, last_uses,
-                                     method_map));
+                                     method_map, dict_map));
     time(time_passes, "LLVM passes",
          bind link::write::run_passes(sess, llmod, outputs.obj_filename));
 
diff --git a/src/comp/lib/llvm.rs b/src/comp/lib/llvm.rs
index 25617066515..927e9879657 100644
--- a/src/comp/lib/llvm.rs
+++ b/src/comp/lib/llvm.rs
@@ -993,7 +993,8 @@ fn type_to_str_inner(names: type_names, outer0: [TypeRef], ty: TypeRef) ->
       }
       10 {
         let el_ty = llvm::LLVMGetElementType(ty);
-        ret "[" + type_to_str_inner(names, outer, el_ty) + "]";
+        ret "[" + type_to_str_inner(names, outer, el_ty) + " x " +
+            uint::str(llvm::LLVMGetArrayLength(ty)) + "]";
       }
       11 {
         let i: uint = 0u;
diff --git a/src/comp/middle/trans.rs b/src/comp/middle/trans.rs
index 65decadfc97..d0f16a332a3 100644
--- a/src/comp/middle/trans.rs
+++ b/src/comp/middle/trans.rs
@@ -98,9 +98,14 @@ fn type_of_fn(cx: @crate_ctxt, sp: span, is_method: bool, inputs: [ty::arg],
 
     // Args >2: ty params, if not acquired via capture...
     if !is_method {
-        // FIXME[impl] Also add args for the dicts
-        for _param in params {
+        for bounds in params {
             atys += [T_ptr(cx.tydesc_type)];
+            for bound in *bounds {
+                alt bound {
+                  ty::bound_iface(_) { atys += [T_ptr(T_dict())]; }
+                  _ {}
+                }
+            }
         }
     }
     // ... then explicit args.
@@ -905,7 +910,10 @@ fn linearize_ty_params(cx: @block_ctxt, t: ty::t) ->
           ty::ty_param(pid, _) {
             let seen: bool = false;
             for d: uint in r.defs { if d == pid { seen = true; } }
-            if !seen { r.vals += [r.cx.fcx.lltydescs[pid]]; r.defs += [pid]; }
+            if !seen {
+                r.vals += [r.cx.fcx.lltyparams[pid].desc];
+                r.defs += [pid];
+            }
           }
           _ { }
         }
@@ -1041,8 +1049,9 @@ fn get_tydesc(cx: @block_ctxt, t: ty::t, escapes: bool,
     // Is the supplied type a type param? If so, return the passed-in tydesc.
     alt ty::type_param(bcx_tcx(cx), t) {
       some(id) {
-        if id < vec::len(cx.fcx.lltydescs) {
-            ret {kind: tk_param, result: rslt(cx, cx.fcx.lltydescs[id])};
+        if id < vec::len(cx.fcx.lltyparams) {
+            ret {kind: tk_param,
+                 result: rslt(cx, cx.fcx.lltyparams[id].desc)};
         } else {
             bcx_tcx(cx).sess.span_bug(cx.sp,
                                       "Unbound typaram in get_tydesc: " +
@@ -1205,10 +1214,7 @@ fn make_generic_glue_inner(cx: @local_ctxt, sp: span, t: ty::t,
         p += 1u;
     }
 
-    // FIXME: Implement some kind of freeze operation in the standard library.
-    let lltydescs_frozen = [];
-    for lltydesc: ValueRef in lltydescs { lltydescs_frozen += [lltydesc]; }
-    fcx.lltydescs = lltydescs_frozen;
+    fcx.lltyparams = vec::map_mut(lltydescs, {|d| {desc: d, dicts: none}});
 
     let bcx = new_top_block_ctxt(fcx);
     let lltop = bcx.llbb;
@@ -2558,11 +2564,13 @@ fn trans_do_while(cx: @block_ctxt, body: ast::blk, cond: @ast::expr) ->
     ret next_cx;
 }
 
-type generic_info =
-    {item_type: ty::t,
-     static_tis: [option::t<@tydesc_info>],
-     tydescs: [ValueRef],
-     param_bounds: @[ty::param_bounds]};
+type generic_info = {
+    item_type: ty::t,
+    static_tis: [option::t<@tydesc_info>],
+    tydescs: [ValueRef],
+    param_bounds: @[ty::param_bounds],
+    origins: option::t<typeck::dict_res>
+};
 
 tag lval_kind {
     temporary; //< Temporary value passed by value if of immediate type
@@ -2571,7 +2579,12 @@ tag lval_kind {
 }
 type local_var_result = {val: ValueRef, kind: lval_kind};
 type lval_result = {bcx: @block_ctxt, val: ValueRef, kind: lval_kind};
-tag callee_env { obj_env(ValueRef); null_env; is_closure; }
+tag callee_env {
+    null_env;
+    is_closure;
+    obj_env(ValueRef);
+    dict_env(ValueRef, ValueRef);
+}
 type lval_maybe_callee = {bcx: @block_ctxt,
                           val: ValueRef,
                           kind: lval_kind,
@@ -2630,11 +2643,11 @@ fn lval_static_fn(bcx: @block_ctxt, fn_id: ast::def_id, id: ast::node_id)
             bcx = td.bcx;
             tydescs += [td.val];
         }
-        let bounds = ty::lookup_item_type(ccx.tcx, fn_id).bounds;
         gen = some({item_type: tpt.ty,
                     static_tis: tis,
                     tydescs: tydescs,
-                    param_bounds: bounds});
+                    param_bounds: tpt.bounds,
+                    origins: ccx.dict_map.find(id)});
     }
     ret {bcx: bcx, val: val, kind: owned, env: null_env, generic: gen};
 }
@@ -2843,17 +2856,6 @@ fn expr_is_lval(bcx: @block_ctxt, e: @ast::expr) -> bool {
     ty::expr_is_lval(ccx.method_map, ccx.tcx, e)
 }
 
-// This is for impl methods, not obj methods.
-fn trans_method_callee(bcx: @block_ctxt, e: @ast::expr, base: @ast::expr,
-                       did: ast::def_id) -> lval_maybe_callee {
-    let tz = [], tr = [];
-    let basety = ty::expr_ty(bcx_tcx(bcx), base);
-    let {bcx, val} = trans_arg_expr(bcx, {mode: ast::by_ref, ty: basety},
-                                    type_of_or_i8(bcx, basety), tz, tr, base);
-    let val = PointerCast(bcx, val, T_opaque_boxed_closure_ptr(bcx_ccx(bcx)));
-    {env: obj_env(val) with lval_static_fn(bcx, did, e.id)}
-}
-
 fn trans_callee(bcx: @block_ctxt, e: @ast::expr) -> lval_maybe_callee {
     alt e.node {
       ast::expr_path(p) { ret trans_path(bcx, p, e.id); }
@@ -2862,10 +2864,11 @@ fn trans_callee(bcx: @block_ctxt, e: @ast::expr) -> lval_maybe_callee {
         if !expr_is_lval(bcx, e) {
             alt bcx_ccx(bcx).method_map.find(e.id) {
               some(typeck::method_static(did)) { // An impl method
-                ret trans_method_callee(bcx, e, base, did);
+                ret trans_impl::trans_static_callee(bcx, e, base, did);
               }
-              some(typeck::method_param(_)) {
-                fail "not implemented"; // FIXME[impl]
+              some(typeck::method_param(iid, off, p, b)) {
+                ret trans_impl::trans_dict_callee(
+                    bcx, e, base, iid, off, p, b);
               }
               none. { // An object method
                 let of = trans_object_field(bcx, base, ident);
@@ -2936,7 +2939,7 @@ fn maybe_add_env(bcx: @block_ctxt, c: lval_maybe_callee)
     -> (lval_kind, ValueRef) {
     alt c.env {
       is_closure. { (c.kind, c.val) }
-      obj_env(_) {
+      obj_env(_) | dict_env(_, _) {
         fail "Taking the value of a method does not work yet (issue #435)";
       }
       null_env. {
@@ -3149,7 +3152,23 @@ fn trans_args(cx: @block_ctxt, llenv: ValueRef,
     alt gen {
       some(g) {
         lazily_emit_all_generic_info_tydesc_glues(cx, g);
-        lltydescs = g.tydescs;
+        let i = 0u, n_orig = 0u;
+        for param in *g.param_bounds {
+            lltydescs += [g.tydescs[i]];
+            for bound in *param {
+                alt bound {
+                  ty::bound_iface(_) {
+                    let res = trans_impl::get_dict(
+                        bcx, option::get(g.origins)[n_orig]);
+                    lltydescs += [res.val];
+                    bcx = res.bcx;
+                    n_orig += 1u;
+                  }
+                  _ {}
+                }
+            }
+            i += 1u;
+        }
         args = ty::ty_fn_args(tcx, g.item_type);
         retty = ty::ty_fn_ret(tcx, g.item_type);
       }
@@ -3220,12 +3239,13 @@ fn trans_call(in_cx: @block_ctxt, f: @ast::expr,
     let bcx = f_res.bcx;
 
     let faddr = f_res.val;
-    let llenv;
+    let llenv, dict_param = none;
     alt f_res.env {
       null_env. {
         llenv = llvm::LLVMGetUndef(T_opaque_boxed_closure_ptr(bcx_ccx(cx)));
       }
       obj_env(e) { llenv = e; }
+      dict_env(dict, e) { llenv = e; dict_param = some(dict); }
       is_closure. {
         // It's a closure. Have to fetch the elements
         if f_res.kind == owned {
@@ -3244,6 +3264,7 @@ fn trans_call(in_cx: @block_ctxt, f: @ast::expr,
         trans_args(bcx, llenv, f_res.generic, args, fn_expr_ty, dest);
     bcx = args_res.bcx;
     let llargs = args_res.args;
+    option::may(dict_param) {|dict| llargs = [dict] + llargs}
     let llretslot = args_res.retslot;
 
     /* If the block is terminated,
@@ -3306,8 +3327,7 @@ fn invoke_(bcx: @block_ctxt, llfn: ValueRef, llargs: [ValueRef],
     // cleanups to run
     if bcx.unreachable { ret bcx; }
     let normal_bcx = new_sub_block_ctxt(bcx, "normal return");
-    invoker(bcx, llfn, llargs,
-            normal_bcx.llbb,
+    invoker(bcx, llfn, llargs, normal_bcx.llbb,
             get_landing_pad(bcx, to_zero, to_revoke));
     ret normal_bcx;
 }
@@ -4351,7 +4371,7 @@ fn new_fn_ctxt_w_id(cx: @local_ctxt, sp: span, llfndecl: ValueRef,
           llobjfields: new_int_hash::<ValueRef>(),
           lllocals: new_int_hash::<local_val>(),
           llupvars: new_int_hash::<ValueRef>(),
-          mutable lltydescs: [],
+          mutable lltyparams: [],
           derived_tydescs: ty::new_ty_hash(),
           id: id,
           ret_style: rstyle,
@@ -4393,10 +4413,22 @@ fn create_llargs_for_fn_args(cx: @fn_ctxt, ty_self: self_arg,
       obj_self(_) {}
       _ {
         for tp in ty_params {
-            let llarg = llvm::LLVMGetParam(cx.llfn, arg_n);
-            assert (llarg as int != 0);
-            cx.lltydescs += [llarg];
+            let lltydesc = llvm::LLVMGetParam(cx.llfn, arg_n), dicts = none;
             arg_n += 1u;
+            for bound in *fcx_tcx(cx).ty_param_bounds.get(tp.id) {
+                alt bound {
+                  ty::bound_iface(_) {
+                    let dict = llvm::LLVMGetParam(cx.llfn, arg_n);
+                    arg_n += 1u;
+                    dicts = some(alt dicts {
+                      none. { [dict] }
+                      some(ds) { ds + [dict] }
+                    });
+                  }
+                  _ {}
+                }
+            }
+            cx.lltyparams += [{desc: lltydesc, dicts: dicts}];
         }
       }
     }
@@ -4485,7 +4517,7 @@ fn populate_fn_ctxt_from_llself(fcx: @fn_ctxt, llself: val_self_pair) {
         let lltyparam: ValueRef =
             GEPi(bcx, obj_typarams, [0, i]);
         lltyparam = Load(bcx, lltyparam);
-        fcx.lltydescs += [lltyparam];
+        fcx.lltyparams += [{desc: lltyparam, dicts: none}];
         i += 1;
     }
     i = 0;
@@ -5582,7 +5614,8 @@ fn write_abi_version(ccx: @crate_ctxt) {
 fn trans_crate(sess: session::session, crate: @ast::crate, tcx: ty::ctxt,
                output: str, emap: resolve::exp_map, amap: ast_map::map,
                mut_map: mut::mut_map, copy_map: alias::copy_map,
-               last_uses: last_use::last_uses, method_map: typeck::method_map)
+               last_uses: last_use::last_uses, method_map: typeck::method_map,
+               dict_map: typeck::dict_map)
     -> (ModuleRef, link::link_meta) {
     let sha = std::sha1::mk_sha1();
     let link_meta = link::build_link_meta(sess, *crate, output, sha);
@@ -5659,6 +5692,7 @@ fn trans_crate(sess: session::session, crate: @ast::crate, tcx: ty::ctxt,
           copy_map: copy_map,
           last_uses: last_uses,
           method_map: method_map,
+          dict_map: dict_map,
           stats:
               {mutable n_static_tydescs: 0u,
                mutable n_derived_tydescs: 0u,
diff --git a/src/comp/middle/trans_closure.rs b/src/comp/middle/trans_closure.rs
index b10f72c3c93..66b0c775533 100644
--- a/src/comp/middle/trans_closure.rs
+++ b/src/comp/middle/trans_closure.rs
@@ -82,17 +82,21 @@ tag environment_value {
 // Given a closure ty, emits a corresponding tuple ty
 fn mk_closure_ty(tcx: ty::ctxt,
                  ck: ty::closure_kind,
-                 n_bound_tds: uint,
+                 ty_params: [fn_ty_param],
                  bound_data_ty: ty::t)
     -> ty::t {
     let tydesc_ty = alt ck {
       ty::closure_block. | ty::closure_shared. { ty::mk_type(tcx) }
       ty::closure_send. { ty::mk_send_type(tcx) }
     };
-    ret ty::mk_tup(tcx, [
-        tydesc_ty,
-        ty::mk_tup(tcx, vec::init_elt(tydesc_ty, n_bound_tds)),
-        bound_data_ty]);
+    let param_ptrs = [];
+    for tp in ty_params {
+        param_ptrs += [tydesc_ty];
+        option::may(tp.dicts) {|dicts|
+            for dict in dicts { param_ptrs += [tydesc_ty]; }
+        }
+    }
+    ty::mk_tup(tcx, [tydesc_ty, ty::mk_tup(tcx, param_ptrs), bound_data_ty])
 }
 
 fn shared_opaque_closure_box_ty(tcx: ty::ctxt) -> ty::t {
@@ -117,7 +121,7 @@ type closure_result = {
 // heap allocated closure that copies the upvars into environment.
 // Otherwise, it is stack allocated and copies pointers to the upvars.
 fn store_environment(
-    bcx: @block_ctxt, lltydescs: [ValueRef],
+    bcx: @block_ctxt, lltyparams: [fn_ty_param],
     bound_values: [environment_value],
     ck: ty::closure_kind)
     -> closure_result {
@@ -162,7 +166,7 @@ fn store_environment(
     }
     let bound_data_ty = ty::mk_tup(tcx, bound_tys);
     let closure_ty =
-        mk_closure_ty(tcx, ck, vec::len(lltydescs), bound_data_ty);
+        mk_closure_ty(tcx, ck, lltyparams, bound_data_ty);
 
     let temp_cleanups = [];
 
@@ -210,7 +214,7 @@ fn store_environment(
         // in the shape code.  Therefore, I am using
         // tps_normal, which is what we used before.
         //
-        // let tps = tps_fn(vec::len(lltydescs));
+        // let tps = tps_fn(vec::len(lltyparams));
 
         let tps = tps_normal;
         let {result:closure_td, _} =
@@ -232,10 +236,19 @@ fn store_environment(
     let {bcx:bcx, val:ty_params_slot} =
         GEP_tup_like_1(bcx, closure_ty, closure,
                        [0, abi::closure_elt_ty_params]);
-    vec::iteri(lltydescs) { |i, td|
-        let ty_param_slot = GEPi(bcx, ty_params_slot, [0, i as int]);
-        let cloned_td = maybe_clone_tydesc(bcx, ck, td);
-        Store(bcx, cloned_td, ty_param_slot);
+    let off = 0;
+
+    for tp in lltyparams {
+        let cloned_td = maybe_clone_tydesc(bcx, ck, tp.desc);
+        Store(bcx, cloned_td, GEPi(bcx, ty_params_slot, [0, off]));
+        off += 1;
+        option::may(tp.dicts, {|dicts|
+            for dict in dicts {
+                let cast = PointerCast(bcx, dict, val_ty(cloned_td));
+                Store(bcx, cast, GEPi(bcx, ty_params_slot, [0, off]));
+                off += 1;
+            }
+        });
     }
 
     // Copy expr values into boxed bindings.
@@ -316,7 +329,7 @@ fn build_closure(bcx0: @block_ctxt,
           }
         }
     }
-    ret store_environment(bcx, copy bcx.fcx.lltydescs, env_vals, ck);
+    ret store_environment(bcx, copy bcx.fcx.lltyparams, env_vals, ck);
 }
 
 // Given an enclosing block context, a new function context, a closure type,
@@ -338,13 +351,23 @@ fn load_environment(enclosing_cx: @block_ctxt,
     // Populate the type parameters from the environment. We need to
     // do this first because the tydescs are needed to index into
     // the bindings if they are dynamically sized.
-    let tydesc_count = vec::len(enclosing_cx.fcx.lltydescs);
     let lltydescs = GEPi(bcx, llclosure,
                          [0, abi::box_rc_field_body,
                           abi::closure_elt_ty_params]);
-    uint::range(0u, tydesc_count) { |i|
-        let lltydescptr = GEPi(bcx, lltydescs, [0, i as int]);
-        fcx.lltydescs += [Load(bcx, lltydescptr)];
+    let off = 0;
+    for tp in copy enclosing_cx.fcx.lltyparams {
+        let tydesc = Load(bcx, GEPi(bcx, lltydescs, [0, off]));
+        off += 1;
+        let dicts = option::map(tp.dicts, {|dicts|
+            let rslt = [];
+            for dict in dicts {
+                let dict = Load(bcx, GEPi(bcx, lltydescs, [0, off]));
+                rslt += [PointerCast(bcx, dict, T_ptr(T_dict()))];
+                off += 1;
+            }
+            rslt
+        });
+        fcx.lltyparams += [{desc: tydesc, dicts: dicts}];
     }
 
     // Populate the upvars from the environment.
@@ -439,13 +462,22 @@ fn trans_bind_1(cx: @block_ctxt, outgoing_fty: ty::t,
     let (outgoing_fty_real, lltydescs, param_bounds) = alt f_res.generic {
       none. { (outgoing_fty, [], @[]) }
       some(ginfo) {
+        for bounds in *ginfo.param_bounds {
+            for bound in *bounds {
+                alt bound {
+                  ty::bound_iface(_) {
+                    fail "FIXME[impl] binding bounded types not implemented";
+                  }
+                  _ {}
+                }
+            }
+        }
         lazily_emit_all_generic_info_tydesc_glues(cx, ginfo);
         (ginfo.item_type, ginfo.tydescs, ginfo.param_bounds)
       }
     };
 
-    let ty_param_count = vec::len(lltydescs);
-    if vec::len(bound) == 0u && ty_param_count == 0u {
+    if vec::len(bound) == 0u && vec::len(lltydescs) == 0u {
         // Trivial 'binding': just return the closure
         let lv = lval_maybe_callee_to_lval(f_res, pair_ty);
         bcx = lv.bcx;
@@ -477,7 +509,7 @@ fn trans_bind_1(cx: @block_ctxt, outgoing_fty: ty::t,
 
     // Actually construct the closure
     let {llbox, box_ty, bcx} = store_environment(
-        bcx, lltydescs,
+        bcx, vec::map(lltydescs, {|d| {desc: d, dicts: none}}),
         env_vals + vec::map(bound, {|x| env_expr(x)}),
         ty::closure_shared);
 
@@ -603,7 +635,7 @@ fn trans_bind_thunk(cx: @local_ctxt,
     // our bound tydescs, we need to load tydescs out of the environment
     // before derived tydescs are constructed. To do this, we load them
     // in the load_env block.
-    let load_env_bcx = new_raw_block_ctxt(fcx, fcx.llloadenv);
+    let l_bcx = new_raw_block_ctxt(fcx, fcx.llloadenv);
 
     // The 'llenv' that will arrive in the thunk we're creating is an
     // environment that will contain the values of its arguments and a pointer
@@ -613,7 +645,7 @@ fn trans_bind_thunk(cx: @local_ctxt,
     // 'boxed_closure_ty', which was determined by trans_bind.
     check (type_has_static_size(ccx, boxed_closure_ty));
     let llclosure_ptr_ty = type_of(ccx, sp, boxed_closure_ty);
-    let llclosure = PointerCast(load_env_bcx, fcx.llenv, llclosure_ptr_ty);
+    let llclosure = PointerCast(l_bcx, fcx.llenv, llclosure_ptr_ty);
 
     // "target", in this context, means the function that's having some of its
     // arguments bound and that will be called inside the thunk we're
@@ -664,20 +696,32 @@ fn trans_bind_thunk(cx: @local_ctxt,
     let llargs: [ValueRef] = [llretptr, lltargetenv];
 
     // Copy in the type parameters.
-    // FIXME[impl] This will also have to copy the dicts
-    let i = 0u, ty_param_count = vec::len(param_bounds);
-    while i < ty_param_count {
-        // Silly check
-        check type_is_tup_like(load_env_bcx, boxed_closure_ty);
-        let lltyparam_ptr =
-            GEP_tup_like(load_env_bcx, boxed_closure_ty, llclosure,
-                         [0, abi::box_rc_field_body,
-                          abi::closure_elt_ty_params, i as int]);
-        load_env_bcx = lltyparam_ptr.bcx;
-        let td = Load(load_env_bcx, lltyparam_ptr.val);
-        llargs += [td];
-        fcx.lltydescs += [td];
-        i += 1u;
+    check type_is_tup_like(l_bcx, boxed_closure_ty);
+    let {bcx: l_bcx, val: param_record} =
+        GEP_tup_like(l_bcx, boxed_closure_ty, llclosure,
+                     [0, abi::box_rc_field_body, abi::closure_elt_ty_params]);
+    let off = 0;
+    for param in param_bounds {
+        let dsc = Load(l_bcx, GEPi(l_bcx, param_record, [0, off])),
+            dicts = none;
+        llargs += [dsc];
+        off += 1;
+        for bound in *param {
+            alt bound {
+              ty::bound_iface(_) {
+                let dict = Load(l_bcx, GEPi(l_bcx, param_record, [0, off]));
+                dict = PointerCast(l_bcx, dict, T_ptr(T_dict()));
+                llargs += [dict];
+                off += 1;
+                dicts = some(alt dicts {
+                  none. { [dict] }
+                  some(ds) { ds + [dict] }
+                });
+              }
+              _ {}
+            }
+        }
+        fcx.lltyparams += [{desc: dsc, dicts: dicts}];
     }
 
     let a: uint = 2u; // retptr, env come first
diff --git a/src/comp/middle/trans_common.rs b/src/comp/middle/trans_common.rs
index 65dcd539510..fa0810fcf91 100644
--- a/src/comp/middle/trans_common.rs
+++ b/src/comp/middle/trans_common.rs
@@ -104,6 +104,7 @@ type crate_ctxt =
      copy_map: alias::copy_map,
      last_uses: last_use::last_uses,
      method_map: typeck::method_map,
+     dict_map: typeck::dict_map,
      stats: stats,
      upcalls: @upcall::upcalls,
      rust_object_type: TypeRef,
@@ -130,6 +131,8 @@ type val_self_pair = {v: ValueRef, t: ty::t};
 
 tag local_val { local_mem(ValueRef); local_imm(ValueRef); }
 
+type fn_ty_param = {desc: ValueRef, dicts: option::t<[ValueRef]>};
+
 // Function context.  Every LLVM function we create will have one of
 // these.
 type fn_ctxt =
@@ -235,7 +238,7 @@ type fn_ctxt =
      llobjfields: hashmap<ast::node_id, ValueRef>,
      lllocals: hashmap<ast::node_id, local_val>,
      llupvars: hashmap<ast::node_id, ValueRef>,
-     mutable lltydescs: [ValueRef],
+     mutable lltyparams: [fn_ty_param],
      derived_tydescs: hashmap<ty::t, derived_tydesc_info>,
      id: ast::node_id,
      ret_style: ast::ret_style,
@@ -532,11 +535,9 @@ fn T_size_t(targ_cfg: @session::config) -> TypeRef {
     ret T_int(targ_cfg);
 }
 
-fn T_fn(inputs: [TypeRef], output: TypeRef) -> TypeRef {
-    unsafe {
-        ret llvm::LLVMFunctionType(output, to_ptr(inputs),
-                                   vec::len::<TypeRef>(inputs), False);
-    }
+fn T_fn(inputs: [TypeRef], output: TypeRef) -> TypeRef unsafe {
+    ret llvm::LLVMFunctionType(output, to_ptr(inputs),
+                               vec::len::<TypeRef>(inputs), False);
 }
 
 fn T_fn_pair(cx: @crate_ctxt, tfn: TypeRef) -> TypeRef {
@@ -545,10 +546,8 @@ fn T_fn_pair(cx: @crate_ctxt, tfn: TypeRef) -> TypeRef {
 
 fn T_ptr(t: TypeRef) -> TypeRef { ret llvm::LLVMPointerType(t, 0u); }
 
-fn T_struct(elts: [TypeRef]) -> TypeRef {
-    unsafe {
-        ret llvm::LLVMStructType(to_ptr(elts), vec::len(elts), False);
-    }
+fn T_struct(elts: [TypeRef]) -> TypeRef unsafe {
+    ret llvm::LLVMStructType(to_ptr(elts), vec::len(elts), False);
 }
 
 fn T_named_struct(name: str) -> TypeRef {
@@ -573,6 +572,12 @@ fn T_rust_object() -> TypeRef {
     ret t;
 }
 
+// A dict is, in reality, a vtable pointer followed by zero or more pointers
+// to tydescs and other dicts that it closes over. But the types and number of
+// those are rarely known to the code that needs to manipulate them, so they
+// are described by this opaque type.
+fn T_dict() -> TypeRef { T_array(T_ptr(T_i8()), 1u) }
+
 fn T_task(targ_cfg: @session::config) -> TypeRef {
     let t = T_named_struct("task");
 
diff --git a/src/comp/middle/trans_impl.rs b/src/comp/middle/trans_impl.rs
index 095c7392287..aab8aaf10fa 100644
--- a/src/comp/middle/trans_impl.rs
+++ b/src/comp/middle/trans_impl.rs
@@ -22,6 +22,40 @@ fn trans_impl(cx: @local_ctxt, name: ast::ident, methods: [@ast::method],
     }
 }
 
+fn trans_self_arg(bcx: @block_ctxt, base: @ast::expr) -> result {
+    let tz = [], tr = [];
+    let basety = ty::expr_ty(bcx_tcx(bcx), base);
+    let {bcx, val} = trans_arg_expr(bcx, {mode: ast::by_ref, ty: basety},
+                                    T_ptr(type_of_or_i8(bcx, basety)), tz,
+                                    tr, base);
+    rslt(bcx, PointerCast(bcx, val, T_opaque_boxed_closure_ptr(bcx_ccx(bcx))))
+}
+
+fn trans_static_callee(bcx: @block_ctxt, e: @ast::expr, base: @ast::expr,
+                       did: ast::def_id) -> lval_maybe_callee {
+    let {bcx, val} = trans_self_arg(bcx, base);
+    {env: obj_env(val) with lval_static_fn(bcx, did, e.id)}
+}
+
+fn trans_dict_callee(bcx: @block_ctxt, _e: @ast::expr, base: @ast::expr,
+                     iface_id: ast::def_id, n_method: uint,
+                     n_param: uint, n_bound: uint) -> lval_maybe_callee {
+    let {bcx, val} = trans_self_arg(bcx, base);
+    let dict = option::get(bcx.fcx.lltyparams[n_param].dicts)[n_bound];
+    let method = ty::iface_methods(bcx_tcx(bcx), iface_id)[n_method];
+    let bare_fn_ty = type_of_fn(bcx_ccx(bcx), ast_util::dummy_sp(),
+                                false, method.fty.inputs, method.fty.output,
+                                *method.tps);
+    let {inputs: bare_inputs, output} = llfn_arg_tys(bare_fn_ty);
+    let fn_ty = T_fn([val_ty(dict)] + bare_inputs, output);
+    let vtable = PointerCast(bcx, Load(bcx, GEPi(bcx, dict, [0, 0])),
+                             T_ptr(T_array(T_ptr(fn_ty), n_method + 1u)));
+    let mptr = Load(bcx, GEPi(bcx, vtable, [0, n_method as int]));
+    {bcx: bcx, val: mptr, kind: owned,
+     env: dict_env(dict, val),
+     generic: none} // FIXME[impl] fetch generic info for method
+}
+
 fn llfn_arg_tys(ft: TypeRef) -> {inputs: [TypeRef], output: TypeRef} {
     let out_ty = llvm::llvm::LLVMGetReturnType(ft);
     let n_args = llvm::llvm::LLVMCountParamTypes(ft);
@@ -35,12 +69,21 @@ fn trans_wrapper(ccx: @crate_ctxt, pt: [ast::ident],
     let real_fn = ccx.item_ids.get(m.id);
     let {inputs: real_args, output: real_ret} =
         llfn_arg_tys(llvm::llvm::LLVMGetElementType(val_ty(real_fn)));
-    let env_ty = T_ptr(T_struct([T_ptr(T_i8())] +
-                                vec::map(extra_tps,
-                                         {|_p| T_ptr(ccx.tydesc_type)})));
-    // FIXME[impl] filter and pass along dicts for bounds
-    let wrap_args = [env_ty] + vec::slice(real_args, 0u, 2u) +
-        vec::slice(real_args, 2u + vec::len(extra_tps), vec::len(real_args));
+    let extra_ptrs = [];
+    for tp in extra_tps {
+        extra_ptrs += [T_ptr(ccx.tydesc_type)];
+        for bound in *tp {
+            alt bound {
+              ty::bound_iface(_) { extra_ptrs += [T_ptr(T_dict())]; }
+              _ {}
+            }
+        }
+    }
+    let env_ty = T_ptr(T_struct([T_ptr(T_i8())] + extra_ptrs));
+    let n_extra_ptrs = vec::len(extra_ptrs);
+
+    let wrap_args = [T_ptr(T_dict())] + vec::slice(real_args, 0u, 2u) +
+        vec::slice(real_args, 2u + vec::len(extra_ptrs), vec::len(real_args));
     let llfn_ty = T_fn(wrap_args, real_ret);
 
     let lcx = @{path: pt + ["wrapper", m.ident], module_path: [],
@@ -50,13 +93,13 @@ fn trans_wrapper(ccx: @crate_ctxt, pt: [ast::ident],
     let fcx = new_fn_ctxt(lcx, ast_util::dummy_sp(), llfn);
     let bcx = new_top_block_ctxt(fcx), lltop = bcx.llbb;
 
-    let dict = LLVMGetParam(llfn, 0u);
+    let dict = PointerCast(bcx, LLVMGetParam(llfn, 0u), env_ty);
     // retptr, self
-    let args = [LLVMGetParam(llfn, 1u), LLVMGetParam(llfn, 2u)], i = 1;
+    let args = [LLVMGetParam(llfn, 1u), LLVMGetParam(llfn, 2u)], i = 0u;
     // saved tydescs/dicts
-    for extra_tp in extra_tps {
-        args += [load_inbounds(bcx, dict, [0, i])];
-        i += 1;
+    while i < n_extra_ptrs {
+        i += 1u;
+        args += [load_inbounds(bcx, dict, [0, i as int])];
     }
     // the rest of the parameters
     let i = 3u, params_total = llvm::llvm::LLVMCountParamTypes(llfn_ty);
@@ -65,7 +108,45 @@ fn trans_wrapper(ccx: @crate_ctxt, pt: [ast::ident],
         i += 1u;
     }
     Call(bcx, ccx.item_ids.get(m.id), args);
+    build_return(bcx);
     finish_fn(fcx, lltop);
     ret llfn;
 }
 
+// FIXME[impl] cache these on the function level somehow
+fn get_dict(bcx: @block_ctxt, origin: typeck::dict_origin) -> result {
+    let bcx = bcx, ccx = bcx_ccx(bcx);
+    alt origin {
+      typeck::dict_static(impl_did, tys, sub_origins) {
+        assert impl_did.crate == ast::local_crate; // FIXME[impl]
+        let vtable = ccx.item_ids.get(impl_did.node);
+        let impl_params = ty::lookup_item_type(ccx.tcx, impl_did).bounds;
+        let ptrs = [vtable], i = 0u, origin = 0u, ti = none;
+        for param in *impl_params {
+            let rslt = get_tydesc(bcx, tys[i], false, tps_normal, ti).result;
+            ptrs += [rslt.val];
+            bcx = rslt.bcx;
+            for bound in *param {
+                alt bound {
+                  ty::bound_iface(_) {
+                    let res = get_dict(bcx, sub_origins[origin]);
+                    ptrs += [res.val];
+                    bcx = res.bcx;
+                    origin += 1u;
+                  }
+                  _ {}
+                }
+            }
+            i += 1u;
+        }
+        let pty = T_ptr(T_i8()), dict_ty = T_array(pty, vec::len(ptrs));
+        let dict = alloca(bcx, dict_ty), i = 0;
+        for ptr in ptrs {
+            Store(bcx, PointerCast(bcx, ptr, pty), GEPi(bcx, dict, [0, i]));
+            i += 1;
+        }
+        rslt(bcx, PointerCast(bcx, dict, T_ptr(T_dict())))
+      }
+      typeck::dict_param(_param) { fail "FIXME[impl]"; }
+    }
+}
\ No newline at end of file
diff --git a/src/comp/middle/trans_objects.rs b/src/comp/middle/trans_objects.rs
index 8b8a4b018d4..913cca74192 100644
--- a/src/comp/middle/trans_objects.rs
+++ b/src/comp/middle/trans_objects.rs
@@ -158,7 +158,7 @@ fn trans_obj(cx: @local_ctxt, sp: span, ob: ast::_obj, ctor_id: ast::node_id,
         let typarams_ty: ty::t = ty::mk_tup(ccx.tcx, tps);
         let i: int = 0;
         for tp: ast::ty_param in ty_params {
-            let typaram = bcx.fcx.lltydescs[i];
+            let typaram = bcx.fcx.lltyparams[i].desc;
             // Silly check
             check type_is_tup_like(bcx, typarams_ty);
             let capture =
diff --git a/src/comp/middle/typeck.rs b/src/comp/middle/typeck.rs
index db177b54bbb..27d94559139 100644
--- a/src/comp/middle/typeck.rs
+++ b/src/comp/middle/typeck.rs
@@ -19,10 +19,12 @@ import option::{none, some};
 import syntax::print::pprust::*;
 
 export check_crate, method_map, method_origin, method_static, method_param;
+export dict_map, dict_res, dict_origin, dict_static, dict_param;
 
 tag method_origin {
     method_static(ast::def_id);
-    method_param(uint);
+    // iface id, method num, param num, bound num
+    method_param(ast::def_id, uint, uint, uint);
 }
 type method_map = hashmap<ast::node_id, method_origin>;
 
@@ -694,14 +696,15 @@ mod collect {
             get_tag_variant_types(cx, tpt.ty, variants, ty_params);
           }
           ast::item_impl(tps, _, selfty, ms) {
-            ty_param_bounds(cx.tcx, m_collect, tps);
+            let i_bounds = ty_param_bounds(cx.tcx, m_collect, tps);
             for m in ms {
                 let bounds = ty_param_bounds(cx.tcx, m_collect, m.tps);
                 let ty = ty::mk_fn(cx.tcx,
                                    ty_of_fn_decl(cx.tcx, m_collect,
                                                  ast::proto_bare, m.decl));
-                cx.tcx.tcache.insert(local_def(m.id), {bounds: bounds,
-                                                       ty: ty});
+                cx.tcx.tcache.insert(local_def(m.id),
+                                     {bounds: @(*i_bounds + *bounds),
+                                      ty: ty});
                 write::ty_only(cx.tcx, m.id, ty);
             }
             write::ty_only(cx.tcx, it.id, ast_ty_to_ty(cx.tcx, m_collect,
@@ -1493,6 +1496,7 @@ fn lookup_method(fcx: @fn_ctxt, isc: resolve::iscopes,
     // First, see whether this is an interface-bounded parameter
     alt ty::struct(tcx, ty) {
       ty::ty_param(n, did) {
+        let bound_n = 0u;
         for bound in *tcx.ty_param_bounds.get(did.node) {
             alt bound {
               ty::bound_iface(t) {
@@ -1500,19 +1504,21 @@ fn lookup_method(fcx: @fn_ctxt, isc: resolve::iscopes,
                     ty::ty_iface(i, tps) { (i, tps) }
                     _ { ret none; }
                 };
-                alt vec::find(*ty::iface_methods(tcx, iid),
-                              {|m| m.ident == name}) {
-                  some(m) {
+                let ifce_methods = ty::iface_methods(tcx, iid);
+                alt vec::position_pred(*ifce_methods, {|m| m.ident == name}) {
+                  some(pos) {
+                    let m = ifce_methods[pos];
                     ret some({method_ty: ty::mk_fn(tcx, m.fty),
                               n_tps: vec::len(*m.tps),
                               ids: [], // FIXME[impl]
-                              origin: method_param(n)});
+                              origin: method_param(iid, pos, n, bound_n)});
                   }
                   _ {}
                 }
               }
               _ {}
             }
+            bound_n += 1u;
         }
         ret none;
       }
@@ -2742,7 +2748,8 @@ fn check_item(ccx: @crate_ctxt, it: @ast::item) {
         vec::pop(ccx.self_infos);
         alt ifce {
           some(ty) {
-            alt ty::struct(ccx.tcx, ast_ty_to_ty(ccx.tcx, m_check, ty)) {
+            let iface_ty = ast_ty_to_ty(ccx.tcx, m_check, ty);
+            alt ty::struct(ccx.tcx, iface_ty) {
               ty::ty_iface(did, tys) {
                 for if_m in *ty::iface_methods(ccx.tcx, did) {
                     alt vec::find(my_methods, {|m| if_m.ident == m.ident}) {
@@ -2759,6 +2766,9 @@ fn check_item(ccx: @crate_ctxt, it: @ast::item) {
                       }
                     }
                 }
+                let tpt = {bounds: ty_param_bounds(ccx.tcx, m_check, tps),
+                           ty: iface_ty};
+                ccx.tcx.tcache.insert(local_def(it.id), tpt);
               }
               _ {
                 ccx.tcx.sess.span_err(ty.span, "can only implement interface \
@@ -2854,12 +2864,22 @@ fn check_for_main_fn(tcx: ty::ctxt, crate: @ast::crate) {
     }
 }
 
+// Resolutions for bounds of all parameters, left to right, for a given path.
+type dict_res = @[dict_origin];
+tag dict_origin {
+    dict_static(ast::def_id, [ty::t], dict_res);
+    dict_param(uint);
+}
+type dict_map = hashmap<ast::node_id, dict_res>;
+
 // Detect points where an interface-bounded type parameter is instantiated,
 // resolve the impls for the parameters.
-fn resolve_vtables(tcx: ty::ctxt, impl_map: resolve::impl_map,
-                   crate: @ast::crate) {
-    type ccx = {tcx: ty::ctxt, impl_map: resolve::impl_map};
-    let cx = {tcx: tcx, impl_map: impl_map};
+fn resolve_dicts(tcx: ty::ctxt, impl_map: resolve::impl_map,
+                   crate: @ast::crate) -> dict_map {
+    type ccx = {tcx: ty::ctxt,
+                impl_map: resolve::impl_map,
+                dict_map: dict_map};
+    let cx = {tcx: tcx, impl_map: impl_map, dict_map: new_int_hash()};
     fn resolve_expr(ex: @ast::expr, cx: ccx, v: visit::vt<ccx>) {
         alt ex.node {
           ast::expr_path(_) {
@@ -2868,18 +2888,15 @@ fn resolve_vtables(tcx: ty::ctxt, impl_map: resolve::impl_map,
             alt substs.substs {
               some(ts) {
                 let did = ast_util::def_id_of_def(cx.tcx.def_map.get(ex.id));
-                let item_ty = ty::lookup_item_type(cx.tcx, did), i = 0u;
-                for s_ty in ts {
-                    for bound in *item_ty.bounds[i] {
-                        alt bound {
-                          ty::bound_iface(i_ty) {
-                            let impls = cx.impl_map.get(ex.id);
-                            lookup_impl(cx, impls, ex.span, s_ty, i_ty);
-                          }
-                          _ {}
-                        }
-                    }
-                    i += 1u;
+                let item_ty = ty::lookup_item_type(cx.tcx, did);
+                if vec::any(*item_ty.bounds, {|bs|
+                    vec::any(*bs, {|b|
+                        alt b { ty::bound_iface(_) { true } _ { false } }
+                    })
+                }) {
+                    let impls = cx.impl_map.get(ex.id);
+                    cx.dict_map.insert(ex.id, lookup_dicts(
+                        cx.tcx, impls, ex.span, *item_ty.bounds, ts));
                 }
               }
               _ {}
@@ -2889,52 +2906,94 @@ fn resolve_vtables(tcx: ty::ctxt, impl_map: resolve::impl_map,
         }
         visit::visit_expr(ex, cx, v);
     }
-    fn lookup_impl(cx: ccx, isc: resolve::iscopes, sp: span,
-                   sub_ty: ty::t, iface_ty: ty::t) {
-        let iface_id = alt ty::struct(cx.tcx, iface_ty) {
+    fn lookup_dicts(tcx: ty::ctxt, isc: resolve::iscopes, sp: span,
+                      bounds: [ty::param_bounds], tys: [ty::t])
+        -> dict_res {
+        let result = [], i = 0u;
+        for ty in tys {
+            for bound in *bounds[i] {
+                alt bound {
+                  ty::bound_iface(i_ty) {
+                    result += [lookup_dict(tcx, isc, sp, ty, i_ty)];
+                  }
+                  _ {}
+                }
+            }
+            i += 1u;
+        }
+        @result
+    }
+    fn lookup_dict(tcx: ty::ctxt, isc: resolve::iscopes, sp: span,
+                     ty: ty::t, iface_ty: ty::t) -> dict_origin {
+        let iface_id = alt ty::struct(tcx, iface_ty) {
             ty::ty_iface(did, _) { did }
-            _ { ret; }
+            _ { tcx.sess.abort_if_errors(); fail; }
         };
-        // FIXME check against bounded param types
-        let found = false;
-        std::list::iter(isc) {|impls|
-            if found { ret; }
-            for im in *impls {
-                if im.iface_did == some(iface_id) {
-                    let self_ty = impl_self_ty(cx.tcx, im.did).ty;
-                    let params = @mutable [mutable];
-                    alt ty::unify::unify(sub_ty, self_ty,
-                                         ty::unify::bind_params(params),
-                                         cx.tcx) {
-                      ures_ok(_) {
-                        if found {
-                            cx.tcx.sess.span_err(
-                                sp, "multiple applicable implementations in \
-                                     scope");
-                        } else {
-                            found = true;
-                        }
+        alt ty::struct(tcx, ty) {
+          ty::ty_param(n, did) {
+            for bound in *tcx.ty_param_bounds.get(did.node) {
+                alt bound {
+                  ty::bound_iface(ity) {
+                    alt ty::struct(tcx, ity) {
+                      ty::ty_iface(idid, _) {
+                        if did == idid { ret dict_param(n); }
                       }
-                      _ {}
                     }
+                  }
+                  _ {}
                 }
             }
+          }
+          _ {
+            let found = none;
+            std::list::iter(isc) {|impls|
+                if option::is_some(found) { ret; }
+                for im in *impls {
+                    if im.iface_did == some(iface_id) {
+                        let self_ty = impl_self_ty(tcx, im.did).ty;
+                        let params = @mutable [mutable];
+                        alt ty::unify::unify(ty, self_ty,
+                                             ty::unify::bind_params(params),
+                                             tcx) {
+                          ures_ok(_) {
+                            if option::is_some(found) {
+                                tcx.sess.span_err(
+                                    sp, "multiple applicable implementations \
+                                         in scope");
+                            } else {
+                                let params = vec::map_mut(
+                                    *params, {|p| option::get(p)});
+                                // FIXME[impl] check for sub-bounds
+                                found = some(dict_static(
+                                    im.did, params, @[]));
+                            }
+                          }
+                          _ {}
+                        }
+                    }
+                }
+            }
+            alt found {
+              some(rslt) { ret rslt; }
+              _ {}
+            }
+          }
         }
-        if !found {
-            cx.tcx.sess.span_err(
-                sp, "failed to find an implementation of interface " +
-                ty_to_str(cx.tcx, iface_ty) + " for " +
-                ty_to_str(cx.tcx, sub_ty));
-        }
+
+        tcx.sess.span_fatal(
+            sp, "failed to find an implementation of interface " +
+            ty_to_str(tcx, iface_ty) + " for " +
+            ty_to_str(tcx, ty));
     }
     visit::visit_crate(*crate, cx, visit::mk_vt(@{
         visit_expr: resolve_expr
         with *visit::default_visitor()
     }));
+    cx.dict_map
 }
 
 fn check_crate(tcx: ty::ctxt, impl_map: resolve::impl_map,
-               crate: @ast::crate) -> method_map {
+               crate: @ast::crate) -> (method_map, dict_map) {
     collect::collect_item_types(tcx, crate);
 
     let ccx = @{mutable self_infos: [],
@@ -2947,10 +3006,10 @@ fn check_crate(tcx: ty::ctxt, impl_map: resolve::impl_map,
                                        bind check_native_item(ccx, _)
                                    with *visit::default_simple_visitor()});
     visit::visit_crate(*crate, (), visit);
-    resolve_vtables(tcx, impl_map, crate);
+    let dict_map = resolve_dicts(tcx, impl_map, crate);
     check_for_main_fn(tcx, crate);
     tcx.sess.abort_if_errors();
-    ccx.method_map
+    (ccx.method_map, dict_map)
 }
 //
 // Local Variables: