Overhaul the kind-checking pass

Not really useful yet because missing last-use-of-local optimization.

Also: instantiation of type parameters needs to be checked.

Issue #1177

4 files changed, 189 insertions, 126 deletions

diff --git a/src/comp/middle/kind.rs b/src/comp/middle/kind.rs
index c82792fddf0..abc7ee8413b 100644
--- a/src/comp/middle/kind.rs
+++ b/src/comp/middle/kind.rs
@@ -1,3 +1,122 @@
+import std::option::some;
+import syntax::{visit, ast_util};
+import syntax::ast::*;
+import syntax::codemap::span;
+
+fn kind_to_str(k: kind) -> str {
+    alt k {
+      kind_sendable. { "sendable" }
+      kind_copyable. { "copyable" }
+      kind_noncopyable. { "noncopyable" }
+    }
+}
+
+type rval_map = std::map::hashmap<node_id, ()>;
+
+type ctx = {tcx: ty::ctxt,
+            rval_map: rval_map,
+            mutable ret_by_ref: bool};
+
+fn check_crate(tcx: ty::ctxt, crate: @crate) -> rval_map {
+    let ctx = {tcx: tcx,
+               rval_map: std::map::new_int_hash(),
+               mutable ret_by_ref: false};
+    let visit = visit::mk_vt(@{
+        visit_expr: check_expr,
+        visit_stmt: check_stmt,
+        visit_fn: visit_fn
+        with *visit::default_visitor()
+    });
+    visit::visit_crate(*crate, ctx, visit);
+    // FIXME go through alias's copy_map, check implicit copies (either here,
+    // or in alias.rs)
+    tcx.sess.abort_if_errors();
+    ret ctx.rval_map;
+}
+
+fn check_expr(e: @expr, cx: ctx, v: visit::vt<ctx>) {
+    alt e.node {
+      expr_assign(_, ex) | expr_assign_op(_, _, ex) |
+      expr_block({node: {expr: some(ex), _}, _}) |
+      expr_unary(box(_), ex) | expr_unary(uniq(_), ex) { maybe_copy(cx, ex); }
+      expr_ret(some(ex)) { if !cx.ret_by_ref { maybe_copy(cx, ex); } }
+      expr_copy(expr) { check_copy_ex(cx, expr, false); }
+      // Vector add copies.
+      expr_binary(add., ls, rs) { maybe_copy(cx, ls); maybe_copy(cx, rs); }
+      expr_rec(fields, _) {
+        for field in fields { maybe_copy(cx, field.node.expr); }
+      }
+      expr_tup(exprs) | expr_vec(exprs, _) {
+        for expr in exprs { maybe_copy(cx, expr); }
+      }
+      expr_bind(_, args) {
+        for a in args { alt a { some(ex) { maybe_copy(cx, ex); } _ {} } }
+      }
+      // FIXME check for by-copy args
+      expr_call(_f, _args, _) {
+
+      }
+      // FIXME: generic instantiation
+      expr_path(_) {}
+      expr_fn({proto: proto_shared(_), _}) {
+        for free in *freevars::get_freevars(cx.tcx, e.id) {
+            let id = ast_util::def_id_of_def(free).node;
+            let ty = ty::node_id_to_type(cx.tcx, id);
+            check_copy(cx, ty, e.span);
+        }
+      }
+      expr_ternary(_, a, b) { maybe_copy(cx, a); maybe_copy(cx, b); }
+      _ { }
+    }
+    visit::visit_expr(e, cx, v);
+}
+
+fn check_stmt(stmt: @stmt, cx: ctx, v: visit::vt<ctx>) {
+    alt stmt.node {
+      stmt_decl(@{node: decl_local(locals), _}, _) {
+        for (_, local) in locals {
+            alt local.node.init {
+              some({op: init_assign., expr}) { maybe_copy(cx, expr); }
+              _ {}
+            }
+        }
+      }
+      _ {}
+    }
+    visit::visit_stmt(stmt, cx, v);
+}
+
+fn visit_fn(f: _fn, tps: [ty_param], sp: span, ident: fn_ident,
+            id: node_id, cx: ctx, v: visit::vt<ctx>) {
+    let old_ret = cx.ret_by_ref;
+    cx.ret_by_ref = ast_util::ret_by_ref(f.decl.cf);
+    visit::visit_fn(f, tps, sp, ident, id, cx, v);
+    cx.ret_by_ref = old_ret;
+}
+
+fn maybe_copy(cx: ctx, ex: @expr) {
+    check_copy_ex(cx, ex, true);
+}
+
+fn check_copy_ex(cx: ctx, ex: @expr, _warn: bool) {
+    if ty::expr_is_lval(cx.tcx, ex) {
+        let ty = ty::expr_ty(cx.tcx, ex);
+        check_copy(cx, ty, ex.span);
+        // FIXME turn this on again once vector types are no longer unique.
+        // Right now, it is too annoying to be useful.
+        /* if warn && ty::type_is_unique(cx.tcx, ty) {
+            cx.tcx.sess.span_warn(ex.span, "copying a unique value");
+        }*/
+    }
+}
+
+fn check_copy(cx: ctx, ty: ty::t, sp: span) {
+    if ty::type_kind(cx.tcx, ty) == kind_noncopyable {
+        cx.tcx.sess.span_err(sp, "copying a noncopyable value");
+    }
+}
+
+
 /*
 * Kinds are types of type.
 *
@@ -84,28 +203,6 @@
 *
 */
 
-import syntax::ast;
-import ast::{kind, kind_sendable, kind_copyable, kind_noncopyable};
-
-fn kind_lteq(a: kind, b: kind) -> bool {
-    alt a {
-      kind_noncopyable. { true }
-      kind_copyable. { b != kind_noncopyable }
-      kind_sendable. { b == kind_sendable }
-    }
-}
-
-fn lower_kind(a: kind, b: kind) -> kind {
-    if kind_lteq(a, b) { a } else { b }
-}
-
-fn kind_to_str(k: kind) -> str {
-    alt k {
-      ast::kind_sendable. { "sendable" }
-      ast::kind_copyable. { "copyable" }
-      ast::kind_noncopyable. { "noncopyable" }
-    }
-}
 /*
 fn type_and_kind(tcx: ty::ctxt, e: @ast::expr) ->
    {ty: ty::t, kind: ast::kind} {
@@ -296,15 +393,6 @@ fn check_stmt(tcx: ty::ctxt, stmt: @ast::stmt) {
     }
 }
 */
-fn check_crate(_tcx: ty::ctxt, _crate: @ast::crate) {
-    // FIXME stubbed out
-/*    let visit =
-        visit::mk_simple_visitor(@{visit_expr: bind check_expr(tcx, _),
-                                   visit_stmt: bind check_stmt(tcx, _)
-                                      with *visit::default_simple_visitor()});
-    visit::visit_crate(*crate, (), visit);
-    tcx.sess.abort_if_errors();*/
-}
 
 //
 // Local Variables:
diff --git a/src/comp/middle/trans.rs b/src/comp/middle/trans.rs
index 22f088b26f6..becdaa092ab 100644
--- a/src/comp/middle/trans.rs
+++ b/src/comp/middle/trans.rs
@@ -3128,7 +3128,7 @@ fn trans_callee(bcx: @block_ctxt, e: @ast::expr) -> lval_maybe_callee {
       ast::expr_path(p) { ret trans_path(bcx, p, e.id); }
       ast::expr_field(base, ident) {
         // Lval means this is a record field, so not a method
-        if !expr_is_lval(bcx_tcx(bcx), e) {
+        if !ty::expr_is_lval(bcx_tcx(bcx), e) {
             let of = trans_object_field(bcx, base, ident);
             ret {bcx: of.bcx, val: of.mthptr, kind: owned,
                  env: obj_env(of.objptr), generic: none};
@@ -3149,25 +3149,6 @@ fn trans_callee(bcx: @block_ctxt, e: @ast::expr) -> lval_maybe_callee {
     ret lval_no_env(lv.bcx, lv.val, lv.kind);
 }
 
-fn expr_is_lval(tcx: ty::ctxt, e: @ast::expr) -> bool {
-    alt e.node {
-      ast::expr_path(_) | ast::expr_index(_, _) |
-      ast::expr_unary(ast::deref., _) { true }
-      ast::expr_field(base, ident) {
-        let basety = ty::type_autoderef(tcx, ty::expr_ty(tcx, base));
-        alt ty::struct(tcx, basety) {
-          ty::ty_obj(_) { false }
-          ty::ty_rec(_) { true }
-        }
-      }
-      ast::expr_call(f, _, _) {
-          let fty = ty::expr_ty(tcx, f);
-          ast_util::ret_by_ref(ty::ty_fn_ret_style(tcx, fty))
-      }
-      _ { false }
-    }
-}
-
 // Use this when you know you are compiling an lval.
 // The additional bool returned indicates whether it's mem (that is
 // represented as an alloca or heap, hence needs a 'load' to be used as an
@@ -4103,7 +4084,7 @@ fn trans_expr_save_in(bcx: @block_ctxt, e: @ast::expr, dest: ValueRef)
 // use trans_temp_expr.
 fn trans_temp_lval(bcx: @block_ctxt, e: @ast::expr) -> lval_result {
     let bcx = bcx;
-    if expr_is_lval(bcx_tcx(bcx), e) {
+    if ty::expr_is_lval(bcx_tcx(bcx), e) {
         ret trans_lval(bcx, e);
     } else {
         let tcx = bcx_tcx(bcx);
@@ -4141,7 +4122,7 @@ fn trans_temp_expr(bcx: @block_ctxt, e: @ast::expr) -> result {
 // - exprs with non-immediate type never get dest=by_val
 fn trans_expr(bcx: @block_ctxt, e: @ast::expr, dest: dest) -> @block_ctxt {
     let tcx = bcx_tcx(bcx);
-    if expr_is_lval(tcx, e) { ret lval_to_dps(bcx, e, dest); }
+    if ty::expr_is_lval(tcx, e) { ret lval_to_dps(bcx, e, dest); }
 
     alt e.node {
       ast::expr_if(cond, thn, els) | ast::expr_if_check(cond, thn, els) {
@@ -4176,7 +4157,7 @@ fn trans_expr(bcx: @block_ctxt, e: @ast::expr, dest: dest) -> @block_ctxt {
       ast::expr_fn(f) { ret trans_expr_fn(bcx, f, e.span, e.id, dest); }
       ast::expr_bind(f, args) { ret trans_bind(bcx, f, args, e.id, dest); }
       ast::expr_copy(a) {
-        if !expr_is_lval(tcx, a) { ret trans_expr(bcx, a, dest); }
+        if !ty::expr_is_lval(tcx, a) { ret trans_expr(bcx, a, dest); }
         else { ret lval_to_dps(bcx, a, dest); }
       }
       ast::expr_cast(val, _) { ret trans_cast(bcx, val, e.id, dest); }
@@ -4574,7 +4555,7 @@ fn init_local(bcx: @block_ctxt, local: @ast::local) -> @block_ctxt {
     alt local.node.init {
       some(init) {
         if init.op == ast::init_assign ||
-           !expr_is_lval(bcx_tcx(bcx), init.expr) {
+           !ty::expr_is_lval(bcx_tcx(bcx), init.expr) {
             bcx = trans_expr_save_in(bcx, init.expr, llptr);
         } else { // This is a move from an lval, must perform an actual move
             let sub = trans_lval(bcx, init.expr);
diff --git a/src/comp/middle/ty.rs b/src/comp/middle/ty.rs
index 1537789629e..5cd58c130f0 100644
--- a/src/comp/middle/ty.rs
+++ b/src/comp/middle/ty.rs
@@ -41,6 +41,7 @@ export eq_ty;
 export expr_has_ty_params;
 export expr_ty;
 export expr_ty_params_and_ty;
+export expr_is_lval;
 export fold_ty;
 export field;
 export field_idx;
@@ -139,6 +140,7 @@ export ty_fn_args;
 export type_constr;
 export type_contains_params;
 export type_contains_vars;
+export kind_lteq;
 export type_kind;
 export type_err;
 export type_err_to_str;
@@ -981,109 +983,84 @@ fn type_needs_drop(cx: ctxt, ty: t) -> bool {
         };
 }
 
+fn kind_lteq(a: kind, b: kind) -> bool {
+    alt a {
+      kind_noncopyable. { true }
+      kind_copyable. { b != kind_noncopyable }
+      kind_sendable. { b == kind_sendable }
+    }
+}
+
+fn lower_kind(a: kind, b: kind) -> kind {
+    if ty::kind_lteq(a, b) { a } else { b }
+}
+
 fn type_kind(cx: ctxt, ty: t) -> ast::kind {
     alt cx.kind_cache.find(ty) {
       some(result) { ret result; }
       none. {/* fall through */ }
     }
 
-    let result = ast::kind_noncopyable;
-
     // Insert a default in case we loop back on self recursively.
-    cx.kind_cache.insert(ty, result);
+    cx.kind_cache.insert(ty, ast::kind_sendable);
 
-    alt struct(cx, ty) {
-      // Scalar types are unique-kind, no substructure.
+    let result = alt struct(cx, ty) {
+      // Scalar and unique types are sendable
       ty_nil. | ty_bot. | ty_bool. | ty_int. | ty_uint. | ty_float. |
-      ty_machine(_) | ty_char. | ty_native(_) {
-        // no-op
-      }
-      // A handful of other built-in are unique too.
-      ty_type. | ty_str. | ty_native_fn(_, _, _) {
-        // no-op
-      }
+      ty_machine(_) | ty_char. | ty_native(_) |
+      ty_type. | ty_str. | ty_native_fn(_, _, _) { ast::kind_sendable }
       // FIXME: obj is broken for now, since we aren't asserting
       // anything about its fields.
-      ty_obj(_) {
-        result = kind_copyable;
-      }
+      ty_obj(_) { kind_copyable }
       // FIXME: the environment capture mode is not fully encoded
       // here yet, leading to weirdness around closure.
       ty_fn(proto, _, _, _, _) {
-        result = alt proto {
+        alt proto {
           ast::proto_block. { ast::kind_noncopyable }
           ast::proto_shared(_) { ast::kind_copyable }
           ast::proto_bare. { ast::kind_sendable }
-        };
+        }
       }
       // Those with refcounts-to-inner raise pinned to shared,
       // lower unique to shared. Therefore just set result to shared.
-      ty_box(mt) {
-        result = ast::kind_copyable;
-      }
+      ty_box(mt) { ast::kind_copyable }
       // Pointers and unique containers raise pinned to shared.
-      ty_ptr(tm) | ty_vec(tm) | ty_uniq(tm) {
-        let k = type_kind(cx, tm.ty);
-
-        // FIXME (984) Doing this implies a lot of subtle rules about what can
-        // and can't be copied, so I'm going to start by not raising unique of
-        // pinned to shared, make sure that's relatively safe, then we can try
-        // to make this work.
-
-        // if k == ast::kind_pinned { k = ast::kind_shared; }
-
-        result = kind::lower_kind(result, k);
-      }
+      ty_ptr(tm) | ty_vec(tm) | ty_uniq(tm) { type_kind(cx, tm.ty) }
       // Records lower to the lowest of their members.
       ty_rec(flds) {
-        for f: field in flds {
-            result = kind::lower_kind(result, type_kind(cx, f.mt.ty));
-            if result == ast::kind_noncopyable { break; }
-        }
+        let lowest = ast::kind_sendable;
+        for f in flds { lowest = lower_kind(lowest, type_kind(cx, f.mt.ty)); }
+        lowest
       }
       // Tuples lower to the lowest of their members.
       ty_tup(tys) {
-        for ty: t in tys {
-            result = kind::lower_kind(result, type_kind(cx, ty));
-            if result == ast::kind_noncopyable { break; }
-        }
+        let lowest = ast::kind_sendable;
+        for ty in tys { lowest = lower_kind(lowest, type_kind(cx, ty)); }
+        lowest
       }
       // Tags lower to the lowest of their variants.
       ty_tag(did, tps) {
-        let variants = tag_variants(cx, did);
-        for variant: variant_info in variants {
-            for aty: t in variant.args {
+        let lowest = ast::kind_sendable;
+        for variant in tag_variants(cx, did) {
+            for aty in variant.args {
                 // Perform any type parameter substitutions.
                 let arg_ty = substitute_type_params(cx, tps, aty);
-                result = kind::lower_kind(result, type_kind(cx, arg_ty));
-                if result == ast::kind_noncopyable { break; }
+                lowest = lower_kind(lowest, type_kind(cx, arg_ty));
+                if lowest == ast::kind_noncopyable { break; }
             }
-            if result == ast::kind_noncopyable { break; }
         }
+        lowest
       }
-      // Resources are always pinned.
-      ty_res(did, inner, tps) {
-        result = ast::kind_noncopyable;
-      }
-      ty_var(_) {
-        fail;
-      }
-      ty_param(_, k) {
-        result = kind::lower_kind(result, k);
-      }
-      ty_constr(t, _) {
-        result = type_kind(cx, t);
-      }
-      _ {
-        cx.sess.bug("missed case: " + ty_to_str(cx, ty));
-      }
-    }
+      // Resources are always noncopyable.
+      ty_res(did, inner, tps) { ast::kind_noncopyable }
+      ty_param(_, k) { k }
+      ty_constr(t, _) { type_kind(cx, t) }
+    };
 
     cx.kind_cache.insert(ty, result);
     ret result;
 }
 
-
 // FIXME: should we just return true for native types in
 // type_is_scalar?
 fn type_is_native(cx: ctxt, ty: t) -> bool {
@@ -1708,6 +1685,25 @@ fn expr_has_ty_params(cx: ctxt, expr: @ast::expr) -> bool {
     ret node_id_has_type_params(cx, expr.id);
 }
 
+fn expr_is_lval(tcx: ty::ctxt, e: @ast::expr) -> bool {
+    alt e.node {
+      ast::expr_path(_) | ast::expr_index(_, _) |
+      ast::expr_unary(ast::deref., _) { true }
+      ast::expr_field(base, ident) {
+        let basety = type_autoderef(tcx, expr_ty(tcx, base));
+        alt struct(tcx, basety) {
+          ty_obj(_) { false }
+          ty_rec(_) { true }
+        }
+      }
+      ast::expr_call(f, _, _) {
+          let fty = expr_ty(tcx, f);
+          ast_util::ret_by_ref(ty_fn_ret_style(tcx, fty))
+      }
+      _ { false }
+    }
+}
+
 fn stmt_node_id(s: @ast::stmt) -> ast::node_id {
     alt s.node {
       ast::stmt_decl(_, id) { ret id; }
diff --git a/src/comp/middle/typeck.rs b/src/comp/middle/typeck.rs
index 567d65d038b..35509c75496 100644
--- a/src/comp/middle/typeck.rs
+++ b/src/comp/middle/typeck.rs
@@ -267,18 +267,16 @@ fn ast_ty_to_ty(tcx: ty::ctxt, getter: ty_getter, &&ast_ty: @ast::ty)
         if vec::len(ty_param_kinds_and_ty.kinds) == 0u {
             ret ty_param_kinds_and_ty.ty;
         }
-        // The typedef is type-parametric. Do the type substitution.
-        //
 
+        // The typedef is type-parametric. Do the type substitution.
         let param_bindings: [ty::t] = [];
+        if vec::len(args) != vec::len(ty_param_kinds_and_ty.kinds) {
+            tcx.sess.span_fatal(sp, "Wrong number of type arguments for a \
+                                     polymorphic type");
+        }
         for ast_ty: @ast::ty in args {
             param_bindings += [ast_ty_to_ty(tcx, getter, ast_ty)];
         }
-        if vec::len(param_bindings) != vec::len(ty_param_kinds_and_ty.kinds) {
-            tcx.sess.span_fatal(sp,
-                                "Wrong number of type arguments for a \
-                                 polymorphic type");
-        }
         let typ =
             ty::substitute_type_params(tcx, param_bindings,
                                        ty_param_kinds_and_ty.ty);