More resolving and typechecking of bounded type parameters.

Extern interfaces still don't get recognized.

Issue #1227

6 files changed, 211 insertions, 55 deletions

diff --git a/src/comp/metadata/csearch.rs b/src/comp/metadata/csearch.rs
index 2603903cf65..3da705f41ef 100644
--- a/src/comp/metadata/csearch.rs
+++ b/src/comp/metadata/csearch.rs
@@ -72,6 +72,7 @@ fn get_impls_for_mod(cstore: cstore::cstore, def: ast::def_id,
         let nm = decoder::lookup_item_name(cdata, did.node);
         if alt name { some(n) { n == nm } none. { true } } {
             result += [@{did: did,
+                         iface_did: none::<ast::def_id>, // FIXME[impl]
                          ident: nm,
                          methods: decoder::lookup_impl_methods(
                              cdata, did.node, did.crate)}];
diff --git a/src/comp/middle/kind.rs b/src/comp/middle/kind.rs
index f71112002c4..b920a9758b1 100644
--- a/src/comp/middle/kind.rs
+++ b/src/comp/middle/kind.rs
@@ -163,14 +163,14 @@ fn check_expr(e: @expr, cx: ctx, v: visit::vt<ctx>) {
         alt substs.substs {
           some(ts) {
             let did = ast_util::def_id_of_def(cx.tcx.def_map.get(e.id));
-            let kinds = vec::map(ty::lookup_item_type(cx.tcx, did).bounds,
-                                 {|bs| ty::param_bounds_to_kind(bs)});
+            let bounds = ty::lookup_item_type(cx.tcx, did).bounds;
             let i = 0u;
             for ty in ts {
                 let kind = ty::type_kind(cx.tcx, ty);
-                if !ty::kind_lteq(kinds[i], kind) {
+                let p_kind = ty::param_bounds_to_kind(bounds[i]);
+                if !ty::kind_lteq(p_kind, kind) {
                     cx.tcx.sess.span_err(e.span, "instantiating a " +
-                                         kind_to_str(kinds[i]) +
+                                         kind_to_str(p_kind) +
                                          " type parameter with a "
                                          + kind_to_str(kind) + " type");
                 }
diff --git a/src/comp/middle/resolve.rs b/src/comp/middle/resolve.rs
index ca9887534cb..2013d9180e3 100644
--- a/src/comp/middle/resolve.rs
+++ b/src/comp/middle/resolve.rs
@@ -1701,7 +1701,8 @@ fn check_exports(e: @env) {
 // Impl resolution
 
 type method_info = {did: def_id, n_tps: uint, ident: ast::ident};
-type _impl = {did: def_id, ident: ast::ident, methods: [@method_info]};
+type _impl = {did: def_id, iface_did: option::t<def_id>,
+              ident: ast::ident, methods: [@method_info]};
 type iscopes = list<@[@_impl]>;
 
 fn resolve_impls(e: @env, c: @ast::crate) {
@@ -1757,14 +1758,20 @@ fn find_impls_in_view_item(e: env, vi: @ast::view_item,
     }
 }
 
-fn find_impls_in_item(i: @ast::item, &impls: [@_impl],
+fn find_impls_in_item(e: env, i: @ast::item, &impls: [@_impl],
                       name: option::t<ident>,
                       ck_exports: option::t<ast::_mod>) {
     alt i.node {
-      ast::item_impl(_, _, _, mthds) {
+      ast::item_impl(_, ifce, _, mthds) {
         if alt name { some(n) { n == i.ident } _ { true } } &&
            alt ck_exports { some(m) { is_exported(i.ident, m) } _ { true } } {
             impls += [@{did: local_def(i.id),
+                        iface_did: alt ifce {
+                            some(@{node: ast::ty_path(_, id), _}) {
+                                some(def_id_of_def(e.def_map.get(id)))
+                            }
+                            _ { none }
+                        },
                         ident: i.ident,
                         methods: vec::map(mthds, {|m|
                             @{did: local_def(m.id),
@@ -1788,7 +1795,7 @@ fn find_impls_in_mod(e: env, m: def, &impls: [@_impl],
             cached = if defid.crate == ast::local_crate {
                 let tmp = [];
                 for i in option::get(e.mod_map.get(defid.node).m).items {
-                    find_impls_in_item(i, tmp, name, none);
+                    find_impls_in_item(e, i, tmp, name, none);
                 }
                 @tmp
             } else {
@@ -1816,7 +1823,7 @@ fn visit_block_with_impl_scope(e: @env, b: ast::blk, sc: iscopes,
     for st in b.node.stmts {
         alt st.node {
           ast::stmt_decl(@{node: ast::decl_item(i), _}, _) {
-            find_impls_in_item(i, impls, none, none);
+            find_impls_in_item(*e, i, impls, none, none);
           }
           _ {}
         }
@@ -1829,13 +1836,15 @@ fn visit_mod_with_impl_scope(e: @env, m: ast::_mod, s: span, sc: iscopes,
                              v: vt<iscopes>) {
     let impls = [];
     for vi in m.view_items { find_impls_in_view_item(*e, vi, impls, sc); }
-    for i in m.items { find_impls_in_item(i, impls, none, none); }
+    for i in m.items { find_impls_in_item(*e, i, impls, none, none); }
     visit::visit_mod(m, s, vec::len(impls) > 0u ? cons(@impls, @sc) : sc, v);
 }
 
 fn resolve_impl_in_expr(e: @env, x: @ast::expr, sc: iscopes, v: vt<iscopes>) {
     alt x.node {
-      ast::expr_field(_, _, _) { e.impl_map.insert(x.id, sc); }
+      ast::expr_field(_, _, _) | ast::expr_path(_) {
+        e.impl_map.insert(x.id, sc);
+      }
       _ {}
     }
     visit::visit_expr(x, sc, v);
diff --git a/src/comp/middle/trans.rs b/src/comp/middle/trans.rs
index 99a112321c8..c843f6e524d 100644
--- a/src/comp/middle/trans.rs
+++ b/src/comp/middle/trans.rs
@@ -2858,9 +2858,12 @@ fn trans_callee(bcx: @block_ctxt, e: @ast::expr) -> lval_maybe_callee {
         // Lval means this is a record field, so not a method
         if !expr_is_lval(bcx, e) {
             alt bcx_ccx(bcx).method_map.find(e.id) {
-              some(did) { // An impl method
+              some(typeck::method_static(did)) { // An impl method
                 ret trans_method_callee(bcx, e, base, did);
               }
+              some(typeck::method_param(_)) {
+                fail "not implemented"; // FIXME[impl]
+              }
               none. { // An object method
                 let of = trans_object_field(bcx, base, ident);
                 ret {bcx: of.bcx, val: of.mthptr, kind: owned,
diff --git a/src/comp/middle/ty.rs b/src/comp/middle/ty.rs
index f893801d2f0..dad0a1609f4 100644
--- a/src/comp/middle/ty.rs
+++ b/src/comp/middle/ty.rs
@@ -814,7 +814,7 @@ fn fold_ty(cx: ctxt, fld: fold_mode, ty_0: t) -> t {
         alt fld { fm_var(folder) { ty = folder(id); } _ {/* no-op */ } }
       }
       ty_param(id, did) {
-        alt fld { fm_param(folder) { ty = folder(id, did); } _ {/* no-op */ } }
+        alt fld { fm_param(folder) { ty = folder(id, did); } _ {} }
       }
     }
 
@@ -1731,6 +1731,7 @@ mod unify {
     export ures_ok;
     export ures_err;
     export var_bindings;
+    export precise, in_bindings, bind_params;
 
     tag result { ures_ok(t); ures_err(type_err); }
     tag union_result { unres_ok; unres_err(type_err); }
@@ -1741,7 +1742,12 @@ mod unify {
     type var_bindings =
         {sets: ufind::ufind, types: smallintmap::smallintmap<t>};
 
-    type ctxt = {vb: option::t<@var_bindings>, tcx: ty_ctxt};
+    tag unify_style {
+        precise;
+        in_bindings(@var_bindings);
+        bind_params(@mutable [mutable option::t<t>]);
+    }
+    type ctxt = {st: unify_style, tcx: ty_ctxt};
 
     fn mk_var_bindings() -> @var_bindings {
         ret @{sets: ufind::make(), types: smallintmap::mk::<t>()};
@@ -1750,7 +1756,9 @@ mod unify {
     // Unifies two sets.
     fn union(cx: @ctxt, set_a: uint, set_b: uint,
              variance: variance) -> union_result {
-        let vb = option::get(cx.vb);
+        let vb = alt cx.st {
+            in_bindings(vb) { vb }
+        };
         ufind::grow(vb.sets, float::max(set_a, set_b) + 1u);
         let root_a = ufind::find(vb.sets, set_a);
         let root_b = ufind::find(vb.sets, set_b);
@@ -1800,7 +1808,7 @@ mod unify {
     fn record_var_binding(
         cx: @ctxt, key: int, typ: t, variance: variance) -> result {
 
-        let vb = option::get(cx.vb);
+        let vb = alt cx.st { in_bindings(vb) { vb } };
         ufind::grow(vb.sets, (key as uint) + 1u);
         let root = ufind::find(vb.sets, key as uint);
         let result_type = typ;
@@ -2136,7 +2144,6 @@ mod unify {
           // If the RHS is a variable type, then just do the
           // appropriate binding.
           ty::ty_var(actual_id) {
-            assert option::is_some(cx.vb);
             let actual_n = actual_id as uint;
             alt struct(cx.tcx, expected) {
               ty::ty_var(expected_id) {
@@ -2157,11 +2164,20 @@ mod unify {
             }
             ret ures_ok(mk_var(cx.tcx, actual_id));
           }
+          ty::ty_param(n, _) {
+            alt cx.st {
+              bind_params(cell) {
+                while vec::len(*cell) < n + 1u { *cell += [mutable none]; }
+                cell[n] = some(expected);
+                ret ures_ok(expected);
+              }
+              _ {}
+            }
+          }
           _ {/* empty */ }
         }
         alt struct(cx.tcx, expected) {
           ty::ty_var(expected_id) {
-            assert option::is_some(cx.vb);
             // Add a binding. (`actual` can't actually be a var here.)
             alt record_var_binding_for_expected(
                 cx, expected_id, actual,
@@ -2478,9 +2494,9 @@ mod unify {
           }
         }
     }
-    fn unify(expected: t, actual: t, vb: option::t<@var_bindings>,
+    fn unify(expected: t, actual: t, st: unify_style,
              tcx: ty_ctxt) -> result {
-        let cx = @{vb: vb, tcx: tcx};
+        let cx = @{st: st, tcx: tcx};
         ret unify_step(cx, expected, actual, covariant);
     }
     fn dump_var_bindings(tcx: ty_ctxt, vb: @var_bindings) {
@@ -2553,7 +2569,7 @@ mod unify {
 }
 
 fn same_type(cx: ctxt, a: t, b: t) -> bool {
-    alt unify::unify(a, b, none, cx) {
+    alt unify::unify(a, b, unify::precise, cx) {
       unify::ures_ok(_) { true }
       _ { false }
     }
diff --git a/src/comp/middle/typeck.rs b/src/comp/middle/typeck.rs
index 313023ba108..a86a29d9f1a 100644
--- a/src/comp/middle/typeck.rs
+++ b/src/comp/middle/typeck.rs
@@ -18,9 +18,13 @@ import std::map::{hashmap, new_int_hash};
 import option::{none, some};
 import syntax::print::pprust::*;
 
-export check_crate, method_map;
+export check_crate, method_map, method_origin, method_static, method_param;
 
-type method_map = hashmap<ast::node_id, ast::def_id>;
+tag method_origin {
+    method_static(ast::def_id);
+    method_param(uint);
+}
+type method_map = hashmap<ast::node_id, method_origin>;
 
 type ty_table = hashmap<ast::def_id, ty::t>;
 
@@ -798,7 +802,8 @@ mod collect {
 mod unify {
     fn unify(fcx: @fn_ctxt, expected: ty::t, actual: ty::t) ->
        ty::unify::result {
-        ret ty::unify::unify(expected, actual, some(fcx.var_bindings),
+        ret ty::unify::unify(expected, actual,
+                             ty::unify::in_bindings(fcx.var_bindings),
                              fcx.ccx.tcx);
     }
 }
@@ -1115,7 +1120,8 @@ fn gather_locals(ccx: @crate_ctxt,
             alt ty_opt {
               none. {/* nothing to do */ }
               some(typ) {
-                ty::unify::unify(ty::mk_var(tcx, var_id), typ, some(vb), tcx);
+                ty::unify::unify(ty::mk_var(tcx, var_id), typ,
+                                 ty::unify::in_bindings(vb), tcx);
               }
             }
         };
@@ -1465,28 +1471,75 @@ fn check_expr_with(fcx: @fn_ctxt, expr: @ast::expr, expected: ty::t) -> bool {
     ret check_expr_with_unifier(fcx, expr, demand::simple, expected);
 }
 
+fn impl_self_ty(tcx: ty::ctxt, did: ast::def_id) -> {n_tps: uint, ty: ty::t} {
+    if did.crate == ast::local_crate {
+        alt tcx.items.get(did.node) {
+          ast_map::node_item(@{node: ast::item_impl(ts, _, st, _),
+                               _}) {
+            {n_tps: vec::len(ts), ty: ast_ty_to_ty(tcx, m_check, st)}
+          }
+        }
+    } else {
+        let tpt = csearch::get_type(tcx, did);
+        {n_tps: vec::len(tpt.bounds), ty: tpt.ty}
+    }
+}
+
 fn lookup_method(fcx: @fn_ctxt, isc: resolve::iscopes,
                  name: ast::ident, ty: ty::t, sp: span)
-    -> option::t<{method: @resolve::method_info, ids: [int]}> {
+    -> option::t<{method_ty: ty::t, n_tps: uint, ids: [int],
+                  origin: method_origin}> {
+    let tcx = fcx.ccx.tcx;
+
+    // First, see whether this is an interface-bounded parameter
+    alt ty::struct(tcx, ty) {
+      ty::ty_param(n, did) {
+        for bound in *tcx.ty_param_bounds.get(did) {
+            alt bound {
+              ty::bound_iface(t) {
+                let (iid, _tps) = alt ty::struct(tcx, t) {
+                    ty::ty_iface(i, tps) { (i, tps) }
+                    _ { ret none; }
+                };
+                alt vec::find(*ty::iface_methods(tcx, iid),
+                              {|m| m.ident == name}) {
+                  some(m) {
+                    ret some({method_ty: ty::mk_fn(tcx, m.fty),
+                              n_tps: vec::len(m.tps),
+                              ids: [], // FIXME[impl]
+                              origin: method_param(n)});
+                  }
+                  _ {}
+                }
+              }
+              _ {}
+            }
+        }
+        ret none;
+      }
+      _ {}
+    }
+
+    fn ty_from_did(tcx: ty::ctxt, did: ast::def_id) -> ty::t {
+        if did.crate == ast::local_crate {
+            alt tcx.items.get(did.node) {
+              ast_map::node_method(m) {
+                let mt = ty_of_method(tcx, m_check, m);
+                ty::mk_fn(tcx, mt.fty)
+              }
+            }
+        } else { csearch::get_type(tcx, did).ty }
+    }
+
     let result = none;
     std::list::iter(isc) {|impls|
         if option::is_some(result) { ret; }
         for @{did, methods, _} in *impls {
             alt vec::find(methods, {|m| m.ident == name}) {
               some(m) {
-                let (n_tps, self_ty) = if did.crate == ast::local_crate {
-                    alt fcx.ccx.tcx.items.get(did.node) {
-                      ast_map::node_item(@{node: ast::item_impl(ts, _, st, _),
-                                           _}) {
-                        (vec::len(ts), ast_ty_to_ty_crate(fcx.ccx, st))
-                      }
-                    }
-                } else {
-                    let tpt = csearch::get_type(fcx.ccx.tcx, did);
-                    (vec::len(tpt.bounds), tpt.ty)
-                };
+                let {n_tps, ty: self_ty} = impl_self_ty(tcx, did);
                 let {ids, ty: self_ty} = if n_tps > 0u {
-                    bind_params_in_type(ast_util::dummy_sp(), fcx.ccx.tcx,
+                    bind_params_in_type(ast_util::dummy_sp(), tcx,
                                         bind next_ty_var_id(fcx), self_ty,
                                         n_tps)
                 } else { {ids: [], ty: self_ty} };
@@ -1494,10 +1547,13 @@ fn lookup_method(fcx: @fn_ctxt, isc: resolve::iscopes,
                   ures_ok(_) {
                     if option::is_some(result) {
                         // FIXME[impl] score specificity to resolve ambiguity?
-                        fcx.ccx.tcx.sess.span_err(
+                        tcx.sess.span_err(
                             sp, "multiple applicable methods in scope");
                     } else {
-                        result = some({method: m, ids: ids});
+                        result = some({method_ty: ty_from_did(tcx, m.did),
+                                       n_tps: m.n_tps,
+                                       ids: ids,
+                                       origin: method_static(m.did)});
                     }
                   }
                   _ {}
@@ -2153,7 +2209,8 @@ fn check_expr_with_unifier(fcx: @fn_ctxt, expr: @ast::expr, unify: unifier,
       }
       ast::expr_field(base, field, tys) {
         bot |= check_expr(fcx, base);
-        let expr_t = expr_ty(tcx, base);
+        let expr_t = structurally_resolved_type(fcx, expr.span,
+                                                expr_ty(tcx, base));
         let base_t = do_autoderef(fcx, expr.span, expr_t);
         let handled = false, n_tys = vec::len(tys);
         alt structure_of(fcx, expr.span, base_t) {
@@ -2191,21 +2248,13 @@ fn check_expr_with_unifier(fcx: @fn_ctxt, expr: @ast::expr, unify: unifier,
         if !handled {
             let iscope = fcx.ccx.impl_map.get(expr.id);
             alt lookup_method(fcx, iscope, field, expr_t, expr.span) {
-              some({method, ids}) {
-                let fty = if method.did.crate == ast::local_crate {
-                    alt tcx.items.get(method.did.node) {
-                      ast_map::node_method(m) {
-                        let mt = ty_of_method(tcx, m_check, m);
-                        ty::mk_fn(tcx, mt.fty)
-                      }
-                    }
-                } else { csearch::get_type(tcx, method.did).ty };
+              some({method_ty: fty, n_tps: method_n_tps, ids, origin}) {
                 let tvars = vec::map(ids, {|id| ty::mk_var(tcx, id)});
                 let n_tps = vec::len(ids);
-                if method.n_tps + n_tps  > 0u {
+                if method_n_tps + n_tps  > 0u {
                     let b = bind_params_in_type(expr.span, tcx,
                                                 bind next_ty_var_id(fcx), fty,
-                                                n_tps + method.n_tps);
+                                                n_tps + method_n_tps);
                     let _tvars = vec::map(b.ids, {|id| ty::mk_var(tcx, id)});
                     let i = 0;
                     for v in tvars {
@@ -2213,9 +2262,8 @@ fn check_expr_with_unifier(fcx: @fn_ctxt, expr: @ast::expr, unify: unifier,
                         i += 1;
                     }
                     tvars = _tvars;
-                    fty = b.ty;
                     if n_tys > 0u {
-                        if n_tys != method.n_tps {
+                        if n_tys != method_n_tps {
                             tcx.sess.span_fatal
                                 (expr.span, "incorrect number of type \
                                            parameters given for this method");
@@ -2235,7 +2283,7 @@ fn check_expr_with_unifier(fcx: @fn_ctxt, expr: @ast::expr, unify: unifier,
                                          parameters");
                 }
                 write::ty_fixup(fcx, id, {substs: some(tvars), ty: fty});
-                fcx.ccx.method_map.insert(id, method.did);
+                fcx.ccx.method_map.insert(id, origin);
               }
               none. {
                 let t_err = resolve_type_vars_if_possible(fcx, expr_t);
@@ -2807,6 +2855,84 @@ fn check_for_main_fn(tcx: ty::ctxt, crate: @ast::crate) {
     }
 }
 
+// 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_expr(ex: @ast::expr, cx: ccx, v: visit::vt<ccx>) {
+        alt ex.node {
+          ast::expr_path(_) {
+            let substs = ty::node_id_to_ty_param_substs_opt_and_ty(
+                cx.tcx, ex.id);
+            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;
+                }
+              }
+              _ {}
+            }
+          }
+          _ {}
+        }
+        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) {
+            ty::ty_iface(did, _) { did }
+            _ { ret; }
+        };
+        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;
+                        }
+                      }
+                      _ {}
+                    }
+                }
+            }
+        }
+        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));
+        }
+    }
+    visit::visit_crate(*crate, cx, visit::mk_vt(@{
+        visit_expr: resolve_expr
+        with *visit::default_visitor()
+    }));
+}
+
 fn check_crate(tcx: ty::ctxt, impl_map: resolve::impl_map,
                crate: @ast::crate) -> method_map {
     collect::collect_item_types(tcx, crate);
@@ -2821,6 +2947,7 @@ 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);
     check_for_main_fn(tcx, crate);
     tcx.sess.abort_if_errors();
     ccx.method_map