rustc: First stab at a typechecker

5 files changed, 912 insertions, 49 deletions

diff --git a/src/comp/driver/rustc.rs b/src/comp/driver/rustc.rs
index 154b87cb..baf00780 100644
--- a/src/comp/driver/rustc.rs
+++ b/src/comp/driver/rustc.rs
@@ -4,6 +4,7 @@ import front.parser;
 import front.token;
 import middle.trans;
 import middle.resolve;
+import middle.typeck;
 
 import std.option;
 import std.option.some;
@@ -15,6 +16,7 @@ impure fn compile_input(session.session sess, str input, str output) {
           auto p = parser.new_parser(sess, 0, input);
           auto crate = parser.parse_crate(p);
           crate = resolve.resolve_crate(sess, crate);
+          crate = typeck.check_crate(sess, crate);
           trans.trans_crate(sess, crate, output);
 }
 
diff --git a/src/comp/front/ast.rs b/src/comp/front/ast.rs
index c3b38cb6..3a67d2f2 100644
--- a/src/comp/front/ast.rs
+++ b/src/comp/front/ast.rs
@@ -1,6 +1,7 @@
 
 import std.map.hashmap;
 import std.option;
+import middle.typeck;
 import util.common.span;
 import util.common.spanned;
 
@@ -17,7 +18,7 @@ type def_id = tup(crate_num, def_num);
 // Annotations added during successive passes.
 tag ann {
     ann_none;
-    ann_type(@ty);
+    ann_type(@typeck.ty);
 }
 
 tag def {
@@ -119,6 +120,8 @@ tag lit_ {
     lit_bool(bool);
 }
 
+// NB: If you change this, you'll probably want to change the corresponding
+// type structure in middle/typeck.rs as well.
 type ty = spanned[ty_];
 tag ty_ {
     ty_nil;
diff --git a/src/comp/middle/trans.rs b/src/comp/middle/trans.rs
index 0c85d50b..d2199fae 100644
--- a/src/comp/middle/trans.rs
+++ b/src/comp/middle/trans.rs
@@ -9,6 +9,7 @@ import std.option.none;
 
 import front.ast;
 import driver.session;
+import middle.typeck;
 import back.x86;
 import back.abi;
 
@@ -237,13 +238,13 @@ fn T_taskptr() -> TypeRef {
     ret T_ptr(T_task());
 }
 
-fn type_of(@trans_ctxt cx, @ast.ty t) -> TypeRef {
-    alt (t.node) {
-        case (ast.ty_nil) { ret T_nil(); }
-        case (ast.ty_bool) { ret T_bool(); }
-        case (ast.ty_int) { ret T_int(); }
-        case (ast.ty_uint) { ret T_int(); }
-        case (ast.ty_machine(?tm)) {
+fn type_of(@trans_ctxt cx, @typeck.ty t) -> TypeRef {
+    alt (t.struct) {
+        case (typeck.ty_nil) { ret T_nil(); }
+        case (typeck.ty_bool) { ret T_bool(); }
+        case (typeck.ty_int) { ret T_int(); }
+        case (typeck.ty_uint) { ret T_int(); }
+        case (typeck.ty_machine(?tm)) {
             alt (tm) {
                 case (common.ty_i8) { ret T_i8(); }
                 case (common.ty_u8) { ret T_i8(); }
@@ -257,24 +258,25 @@ fn type_of(@trans_ctxt cx, @ast.ty t) -> TypeRef {
                 case (common.ty_f64) { ret T_f64(); }
             }
         }
-        case (ast.ty_char) { ret T_char(); }
-        case (ast.ty_str) { ret T_str(0u); }
-        case (ast.ty_box(?t)) {
+        case (typeck.ty_char) { ret T_char(); }
+        case (typeck.ty_str) { ret T_str(0u); }
+        case (typeck.ty_box(?t)) {
             ret T_ptr(T_box(type_of(cx, t)));
         }
-        case (ast.ty_vec(?t)) {
+        case (typeck.ty_vec(?t)) {
             ret T_ptr(T_vec(type_of(cx, t), 0u));
         }
-        case (ast.ty_tup(?elts)) {
+        case (typeck.ty_tup(?elts)) {
             let vec[TypeRef] tys = vec();
-            for (tup(bool, @ast.ty) elt in elts) {
+            for (tup(bool, @typeck.ty) elt in elts) {
                 tys += type_of(cx, elt._1);
             }
             ret T_struct(tys);
         }
-        case (ast.ty_path(?pth,  ?def)) {
+        case (typeck.ty_var(_)) {
             // FIXME: implement.
-            cx.sess.unimpl("ty_path in trans.type_of");
+            log "ty_var in trans.type_of";
+            ret T_i8();
         }
     }
     fail;
@@ -340,27 +342,23 @@ fn C_tydesc(TypeRef t) -> ValueRef {
                      C_null(T_opaque())));      // is_stateful
 }
 
-fn decl_fn(ModuleRef llmod, str name,
-           uint cc, vec[TypeRef] inputs, TypeRef output) -> ValueRef {
-    let TypeRef llty = T_fn(inputs, output);
+fn decl_fn(ModuleRef llmod, str name, uint cc, TypeRef llty) -> ValueRef {
     let ValueRef llfn =
         llvm.LLVMAddFunction(llmod, _str.buf(name), llty);
     llvm.LLVMSetFunctionCallConv(llfn, cc);
     ret llfn;
 }
 
-fn decl_cdecl_fn(ModuleRef llmod, str name,
-                 vec[TypeRef] inputs, TypeRef output) -> ValueRef {
-    ret decl_fn(llmod, name, lib.llvm.LLVMCCallConv, inputs, output);
+fn decl_cdecl_fn(ModuleRef llmod, str name, TypeRef llty) -> ValueRef {
+    ret decl_fn(llmod, name, lib.llvm.LLVMCCallConv, llty);
 }
 
-fn decl_fastcall_fn(ModuleRef llmod, str name,
-                    vec[TypeRef] inputs, TypeRef output) -> ValueRef {
-    ret decl_fn(llmod, name, lib.llvm.LLVMFastCallConv, inputs, output);
+fn decl_fastcall_fn(ModuleRef llmod, str name, TypeRef llty) -> ValueRef {
+    ret decl_fn(llmod, name, lib.llvm.LLVMFastCallConv, llty);
 }
 
 fn decl_glue(ModuleRef llmod, str s) -> ValueRef {
-    ret decl_cdecl_fn(llmod, s, vec(T_taskptr()), T_void());
+    ret decl_cdecl_fn(llmod, s, T_fn(vec(T_taskptr()), T_void()));
 }
 
 fn decl_upcall(ModuleRef llmod, uint _n) -> ValueRef {
@@ -375,7 +373,7 @@ fn decl_upcall(ModuleRef llmod, uint _n) -> ValueRef {
             T_int())     // callee
         + _vec.init_elt[TypeRef](T_int(), n as uint);
 
-    ret decl_fastcall_fn(llmod, s, args, T_int());
+    ret decl_fastcall_fn(llmod, s, T_fn(args, T_int()));
 }
 
 fn get_upcall(@trans_ctxt cx, str name, int n_args) -> ValueRef {
@@ -385,7 +383,7 @@ fn get_upcall(@trans_ctxt cx, str name, int n_args) -> ValueRef {
     auto inputs = vec(T_taskptr());
     inputs += _vec.init_elt[TypeRef](T_int(), n_args as uint);
     auto output = T_int();
-    auto f = decl_cdecl_fn(cx.llmod, name, inputs, output);
+    auto f = decl_cdecl_fn(cx.llmod, name, T_fn(inputs, output));
     cx.upcalls.insert(name, f);
     ret f;
 }
@@ -937,6 +935,7 @@ impure fn trans_expr(@block_ctxt cx, &ast.expr e) -> result {
         case (ast.expr_call(?f, ?args, _)) {
             auto f_res = trans_lval(cx, *f);
             check (! f_res._1);
+
             auto args_res = trans_exprs(f_res._0.bcx, args);
             auto llargs = vec(cx.fcx.lltaskptr);
             llargs += args_res._1;
@@ -1141,15 +1140,7 @@ impure fn trans_block(@block_ctxt cx, &ast.block b) -> result {
     auto bcx = cx;
 
     for each (@ast.local local in block_locals(b)) {
-        auto ty = T_nil();
-        alt (local.ty) {
-            case (some[@ast.ty](?t)) {
-                ty = type_of(cx.fcx.tcx, t);
-            }
-            case (none[@ast.ty]) {
-                cx.fcx.tcx.sess.err("missing type for local " + local.ident);
-            }
-        }
+        auto ty = node_type(cx.fcx.tcx, local.ann);
         auto val = bcx.build.Alloca(ty);
         cx.fcx.lllocals.insert(local.id, val);
     }
@@ -1236,15 +1227,24 @@ impure fn trans_mod(@trans_ctxt cx, &ast._mod m) {
 
 fn collect_item(&@trans_ctxt cx, @ast.item i) -> @trans_ctxt {
     alt (i.node) {
-        case (ast.item_fn(?name, ?f, ?fid, _)) {
-            cx.items.insert(fid, i);
-            let TypeRef out = type_of(cx, f.output);
-            auto args = vec(T_taskptr());
-            for (ast.arg arg in f.inputs) {
-                args += type_of(cx, arg.ty);
+        case (ast.item_fn(?name, ?f, ?fid, ?ann)) {
+            auto fn_inputs;
+            auto fn_output;
+            alt (typeck.ann_to_type(ann).struct) {
+                case (typeck.ty_fn(?ins, ?out)) {
+                    fn_inputs = ins;
+                    fn_output = out;
+                }
+                case (_) {
+                    log "trans: fn item doesn't have function type!";
+                    fail;
+                }
             }
+
+            cx.items.insert(fid, i);
+            auto llty = node_type(cx, ann);
             let str s = cx.names.next("_rust_fn") + "." + name;
-            let ValueRef llfn = decl_fastcall_fn(cx.llmod, s, args, out);
+            let ValueRef llfn = decl_fastcall_fn(cx.llmod, s, llty);
             cx.fn_ids.insert(fid, llfn);
         }
 
@@ -1338,10 +1338,10 @@ fn trans_main_fn(@trans_ctxt cx, ValueRef llcrate) {
     }
 
     auto llmain =
-        decl_cdecl_fn(cx.llmod, main_name, T_main_args, T_int());
+        decl_cdecl_fn(cx.llmod, main_name, T_fn(T_main_args, T_int()));
 
-    auto llrust_start =
-        decl_cdecl_fn(cx.llmod, "rust_start", T_rust_start_args, T_int());
+    auto llrust_start = decl_cdecl_fn(cx.llmod, "rust_start",
+                                      T_fn(T_rust_start_args, T_int()));
 
     auto llargc = llvm.LLVMGetParam(llmain, 0u);
     auto llargv = llvm.LLVMGetParam(llmain, 1u);
@@ -1367,7 +1367,7 @@ fn trans_main_fn(@trans_ctxt cx, ValueRef llcrate) {
 
 fn declare_intrinsics(ModuleRef llmod) {
     let vec[TypeRef] T_trap_args = vec();
-    decl_cdecl_fn(llmod, "llvm.trap", T_trap_args, T_void());
+    decl_cdecl_fn(llmod, "llvm.trap", T_fn(T_trap_args, T_void()));
 }
 
 fn trans_crate(session.session sess, @ast.crate crate, str output) {
@@ -1396,7 +1396,7 @@ fn trans_crate(session.session sess, @ast.crate crate, str output) {
                        */
                       exit_task_glue =
                       decl_cdecl_fn(llmod, abi.exit_task_glue_name(),
-                                    vec(T_taskptr()), T_void()),
+                                    T_fn(vec(T_taskptr()), T_void())),
 
                       upcall_glues =
                       _vec.init_fn[ValueRef](bind decl_upcall(llmod, _),
diff --git a/src/comp/middle/typeck.rs b/src/comp/middle/typeck.rs
new file mode 100644
index 00000000..8ef75ffa
--- /dev/null
+++ b/src/comp/middle/typeck.rs
@@ -0,0 +1,857 @@
+//
+// comp/middle/typeck.rs
+//
+
+import front.ast;
+import front.ast.ann;
+import middle.fold;
+import driver.session;
+import util.common;
+import util.common.span;
+
+import std._str;
+import std._uint;
+import std._vec;
+import std.map;
+import std.map.hashmap;
+import std.option;
+import std.option.none;
+import std.option.some;
+
+type ty_table = hashmap[ast.def_id, @ty];
+type env = rec(session.session sess,
+               @ty_table item_types,
+               mutable int next_var_id);
+
+type arg = rec(ast.mode mode, @ty ty);
+
+// NB: If you change this, you'll probably want to change the corresponding
+// AST structure in front/ast.rs as well.
+type ty = rec(sty struct, option.t[str] cname);
+tag sty {
+    ty_nil;
+    ty_bool;
+    ty_int;
+    ty_uint;
+    ty_machine(util.common.ty_mach);
+    ty_char;
+    ty_str;
+    ty_box(@ty);
+    ty_vec(@ty);
+    ty_tup(vec[tup(bool /* mutability */, @ty)]);
+    ty_fn(vec[arg], @ty);                           // TODO: effect
+    ty_var(int);
+}
+
+tag type_err {
+    terr_mismatch;
+    terr_tuple_size(uint, uint);
+    terr_tuple_mutability;
+    terr_arg_count;
+}
+
+tag unify_result {
+    ures_ok(@ty);
+    ures_err(type_err, @ty, @ty);
+}
+
+// Used for ast_ty_to_ty() below.
+type ty_getter = fn(ast.def_id) -> @ty;
+
+// Error-reporting utility functions
+
+fn ast_ty_to_str(&@ast.ty ty) -> str {
+    fn ast_tup_elem_to_str(&tup(bool, @ast.ty) elem) -> str {
+        auto s;
+        if (elem._0) {
+            s = "mutable ";
+        } else {
+            s = "";
+        }
+
+        ret s + ast_ty_to_str(elem._1);
+    }
+
+    fn ast_fn_input_to_str(&rec(ast.mode mode, @ast.ty ty) input) -> str {
+        auto s;
+        if (mode_is_alias(input.mode)) {
+            s = "&";
+        } else {
+            s = "";
+        }
+
+        ret s + ast_ty_to_str(input.ty);
+    }
+
+    auto s;
+    alt (ty.node) {
+        case (ast.ty_nil)          { s = "()";                            }
+        case (ast.ty_bool)         { s = "bool";                          }
+        case (ast.ty_int)          { s = "int";                           }
+        case (ast.ty_uint)         { s = "uint";                          }
+        case (ast.ty_machine(?tm)) { s = common.ty_mach_to_str(tm);       }
+        case (ast.ty_char)         { s = "char";                          }
+        case (ast.ty_str)          { s = "str";                           }
+        case (ast.ty_box(?t))      { s = "@" + ast_ty_to_str(t);          }
+        case (ast.ty_vec(?t))      { s = "vec[" + ast_ty_to_str(t) + "]"; }
+
+        case (ast.ty_tup(?elems)) {
+            auto f = ast_tup_elem_to_str;
+            s = "tup(";
+            s += _str.connect(_vec.map[tup(bool,@ast.ty),str](f, elems), ",");
+            s += ")";
+        }
+
+        case (ast.ty_fn(?inputs, ?output)) {
+            auto f = ast_fn_input_to_str;
+            s = "fn(";
+            auto is = _vec.map[rec(ast.mode mode, @ast.ty ty),str](f, inputs);
+            s += _str.connect(is, ", ");
+            s += ")";
+
+            if (output.node != ast.ty_nil) {
+                s += " -> " + ast_ty_to_str(output);
+            }
+        }
+
+        case (ast.ty_path(?path, _)) {
+            s = path_to_str(path);
+        }
+
+        case (_) {
+            fail;   // FIXME: typestate bug
+        }
+    }
+
+    ret s;
+}
+
+fn name_to_str(&ast.name nm) -> str {
+    auto result = nm.node.ident;
+    if (_vec.len[@ast.ty](nm.node.types) > 0u) {
+        auto f = ast_ty_to_str;
+        result += "[";
+        result += _str.connect(_vec.map[@ast.ty,str](f, nm.node.types), ",");
+        result += "]";
+    }
+    ret result;
+}
+
+fn path_to_str(&ast.path path) -> str {
+    auto f = name_to_str;
+    ret _str.connect(_vec.map[ast.name,str](f, path), ".");
+}
+
+fn ty_to_str(@ty typ) -> str {
+    fn tup_elem_to_str(&tup(bool, @ty) elem) -> str {
+        auto s;
+        if (elem._0) {
+            s = "mutable ";
+        } else {
+            s = "";
+        }
+
+        ret s + ty_to_str(elem._1);
+    }
+
+    fn fn_input_to_str(&rec(ast.mode mode, @ty ty) input) -> str {
+        auto s;
+        if (mode_is_alias(input.mode)) {
+            s = "&";
+        } else {
+            s = "";
+        }
+
+        ret s + ty_to_str(input.ty);
+    }
+
+    auto s;
+    alt (typ.struct) {
+        case (ty_nil)          { s = "()";                        }
+        case (ty_bool)         { s = "bool";                      }
+        case (ty_int)          { s = "int";                       }
+        case (ty_uint)         { s = "uint";                      }
+        case (ty_machine(?tm)) { s = common.ty_mach_to_str(tm);   }
+        case (ty_char)         { s = "char";                      }
+        case (ty_str)          { s = "str";                       }
+        case (ty_box(?t))      { s = "@" + ty_to_str(t);          }
+        case (ty_vec(?t))      { s = "vec[" + ty_to_str(t) + "]"; }
+
+        case (ty_tup(?elems)) {
+            auto f = tup_elem_to_str;
+            auto strs = _vec.map[tup(bool,@ty),str](f, elems);
+            s = "tup(" + _str.connect(strs, ",") + ")";
+        }
+
+        case (ty_fn(?inputs, ?output)) {
+            auto f = fn_input_to_str;
+            s = "fn(" + _str.connect(_vec.map[arg,str](f, inputs), ", ") + ")";
+            if (output.struct != ty_nil) {
+                s += " -> " + ty_to_str(output);
+            }
+        }
+
+        case (ty_var(?v)) {
+            // FIXME: wrap around in the case of many variables
+            auto ch = ('T' as u8) + (v as u8);
+            s = _str.from_bytes(vec(ch));
+        }
+    }
+
+    ret s;
+}
+
+// Parses the programmer's textual representation of a type into our internal
+// notion of a type. `getter` is a function that returns the type
+// corresponding to a definition ID.
+fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty {
+    fn ast_arg_to_arg(ty_getter getter, &rec(ast.mode mode, @ast.ty ty) arg)
+            -> rec(ast.mode mode, @ty ty) {
+        ret rec(mode=arg.mode, ty=ast_ty_to_ty(getter, arg.ty));
+    }
+
+    auto sty;
+    auto cname = none[str];
+    alt (ast_ty.node) {
+        case (ast.ty_nil)          { sty = ty_nil; }
+        case (ast.ty_bool)         { sty = ty_bool; }
+        case (ast.ty_int)          { sty = ty_int; }
+        case (ast.ty_uint)         { sty = ty_uint; }
+        case (ast.ty_machine(?tm)) { sty = ty_machine(tm); }
+        case (ast.ty_char)         { sty = ty_char; }
+        case (ast.ty_str)          { sty = ty_str; }
+        case (ast.ty_box(?t))      { sty = ty_box(ast_ty_to_ty(getter, t)); }
+        case (ast.ty_vec(?t))      { sty = ty_vec(ast_ty_to_ty(getter, t)); }
+
+        case (ast.ty_fn(?inputs, ?output)) {
+            auto f = bind ast_arg_to_arg(getter, _);
+            auto i = _vec.map[rec(ast.mode mode, @ast.ty ty),arg](f, inputs);
+            sty = ty_fn(i, ast_ty_to_ty(getter, output));
+        }
+
+        case (ast.ty_path(?path, ?def)) {
+            auto def_id;
+            alt (option.get[ast.def](def)) {
+                case (ast.def_ty(?id)) { def_id = id; }
+                case (_) { fail; }
+            }
+
+            // TODO: maybe record cname chains so we can do "foo = int" like
+            // OCaml?
+            sty = getter(def_id).struct;
+            cname = some(path_to_str(path));
+        }
+    }
+
+    ret @rec(struct=sty, cname=cname);
+}
+
+// A convenience function to use an environment to resolve names for
+// ast_ty_to_ty.
+fn ast_ty_to_ty_env(@env e, &@ast.ty ast_ty) -> @ty {
+    fn getter(@env e, ast.def_id id) -> @ty {
+        ret e.item_types.get(id);
+    }
+    auto f = bind getter(e, _);
+    ret ast_ty_to_ty(f, ast_ty);
+}
+
+fn type_err_to_str(&type_err err) -> str {
+    alt (err) {
+        case (terr_mismatch) {
+            ret "types differ";
+        }
+        case (terr_tuple_size(?e_sz, ?a_sz)) {
+            ret "expected a tuple with " + _uint.to_str(e_sz, 10u) +
+                " elements but found one with " + _uint.to_str(a_sz, 10u) +
+                " elements";
+        }
+        case (terr_tuple_mutability) {
+            ret "tuple elements differ in mutability";
+        }
+        case (terr_arg_count) {
+            ret "incorrect number of function parameters";
+        }
+    }
+}
+
+// Item collection - a pair of bootstrap passes:
+//
+// 1. Collect the IDs of all type items (typedefs) and store them in a table.
+//
+// 2. Translate the AST fragments that describe types to determine a type for
+//    each item. When we encounter a named type, we consult the table built in
+//    pass 1 to find its item, and recursively translate it.
+//
+// We then annotate the AST with the resulting types and return the annotated
+// AST, along with a table mapping item IDs to their types.
+
+fn collect_item_types(@ast.crate crate) -> tup(@ast.crate, @ty_table) {
+    fn trans_ty_item_id_to_ty(@hashmap[ast.def_id,@ast.item] id_to_ty_item,
+                              @ty_table item_to_ty,
+                              ast.def_id id) -> @ty {
+        auto item = id_to_ty_item.get(id);
+        ret trans_ty_item_to_ty(id_to_ty_item, item_to_ty, item);
+    }
+
+    fn trans_fn_arg_to_ty(@hashmap[ast.def_id,@ast.item] id_to_ty_item,
+                          @ty_table item_to_ty,
+                          &ast.arg a) -> arg {
+        auto f = bind trans_ty_item_id_to_ty(id_to_ty_item, item_to_ty, _);
+        ret rec(mode=a.mode, ty=ast_ty_to_ty(f, a.ty));
+    }
+
+    fn trans_ty_item_to_ty(@hashmap[ast.def_id,@ast.item] id_to_ty_item,
+                           @ty_table item_to_ty,
+                           @ast.item it) -> @ty {
+        alt (it.node) {
+            case (ast.item_fn(?ident, ?fn_info, ?def_id, _)) {
+                auto f = bind trans_fn_arg_to_ty(id_to_ty_item, item_to_ty,
+                                                 _);
+                auto input_tys = _vec.map[ast.arg,arg](f, fn_info.inputs);
+
+                auto g = bind trans_ty_item_id_to_ty(id_to_ty_item,
+                                                     item_to_ty, _);
+                auto output_ty = ast_ty_to_ty(g, fn_info.output);
+
+                auto t_fn = plain_ty(ty_fn(input_tys, output_ty));
+                item_to_ty.insert(def_id, t_fn);
+                ret t_fn;
+            }
+
+            case (ast.item_ty(?ident, ?referent_ty, ?def_id, _)) {
+                if (item_to_ty.contains_key(def_id)) {
+                    // Avoid repeating work.
+                    ret item_to_ty.get(def_id);
+                }
+
+                // Tell ast_ty_to_ty() that we want to perform a recursive
+                // call to resolve any named types.
+                auto f = bind trans_ty_item_id_to_ty(id_to_ty_item,
+                                                     item_to_ty, _);
+                auto ty = ast_ty_to_ty(f, referent_ty);
+                item_to_ty.insert(def_id, ty);
+                ret ty;
+            }
+
+            case (ast.item_mod(_, _, _)) { fail; }
+        }
+    }
+
+    // First pass: collect all type item IDs.
+    auto module = crate.node.module;
+    auto id_to_ty_item = @common.new_def_hash[@ast.item]();
+    for (@ast.item item in module.items) {
+        alt (item.node) {
+            case (ast.item_ty(_, _, ?def_id, _)) {
+                id_to_ty_item.insert(def_id, item);
+            }
+            case (_) { /* empty */ }
+        }
+    }
+
+    // Second pass: translate the types of all items.
+    auto item_to_ty = @common.new_def_hash[@ty]();
+    let vec[@ast.item] items_t = vec();
+    for (@ast.item it in module.items) {
+        let ast.item_ result;
+        alt (it.node) {
+            case (ast.item_fn(?ident, ?fn_info, ?def_id, _)) {
+                auto t = trans_ty_item_to_ty(id_to_ty_item, item_to_ty, it);
+                result = ast.item_fn(ident, fn_info, def_id, ast.ann_type(t));
+            }
+            case (ast.item_ty(?ident, ?referent_ty, ?def_id, _)) {
+                auto t = trans_ty_item_to_ty(id_to_ty_item, item_to_ty, it);
+                auto ann = ast.ann_type(t);
+                result = ast.item_ty(ident, referent_ty, def_id, ann);
+            }
+            case (ast.item_mod(_, _, _)) {
+                result = it.node;
+            }
+        }
+        items_t += vec(@fold.respan[ast.item_](it.span, result));
+    }
+
+    auto module_t = rec(items=items_t, index=module.index);
+    ret tup(@fold.respan[ast.crate_](crate.span, rec(module=module_t)),
+            item_to_ty);
+}
+
+// Type utilities
+
+// FIXME: remove me when == works on these tags.
+fn mode_is_alias(ast.mode m) -> bool {
+    alt (m) {
+        case (ast.val) { ret false; }
+        case (ast.alias) { ret true; }
+    }
+}
+
+fn plain_ty(&sty st) -> @ty {
+    ret @rec(struct=st, cname=none[str]);
+}
+
+fn ann_to_type(&ast.ann ann) -> @ty {
+    alt (ann) {
+        case (ast.ann_none) {
+            // shouldn't happen, but can until the typechecker is complete
+            ret plain_ty(ty_var(0));    // FIXME: broken, broken, broken
+        }
+        case (ast.ann_type(?ty)) {
+            ret ty;
+        }
+    }
+}
+
+fn type_of(@ast.expr expr) -> @ty {
+    alt (expr.node) {
+        case (ast.expr_vec(_, ?ann))          { ret ann_to_type(ann); }
+        case (ast.expr_tup(_, ?ann))          { ret ann_to_type(ann); }
+        case (ast.expr_rec(_, ?ann))          { ret ann_to_type(ann); }
+        case (ast.expr_call(_, _, ?ann))      { ret ann_to_type(ann); }
+        case (ast.expr_binary(_, _, _, ?ann)) { ret ann_to_type(ann); }
+        case (ast.expr_unary(_, _, ?ann))     { ret ann_to_type(ann); }
+        case (ast.expr_lit(_, ?ann))          { ret ann_to_type(ann); }
+        case (ast.expr_cast(_, _, ?ann))      { ret ann_to_type(ann); }
+        case (ast.expr_if(_, _, _, ?ann))     { ret ann_to_type(ann); }
+        case (ast.expr_while(_, _, ?ann))     { ret ann_to_type(ann); }
+        case (ast.expr_do_while(_, _, ?ann))  { ret ann_to_type(ann); }
+        case (ast.expr_block(_, ?ann))        { ret ann_to_type(ann); }
+        case (ast.expr_assign(_, _, ?ann))    { ret ann_to_type(ann); }
+        case (ast.expr_field(_, _, ?ann))     { ret ann_to_type(ann); }
+        case (ast.expr_index(_, _, ?ann))     { ret ann_to_type(ann); }
+        case (ast.expr_name(_, _, ?ann))      { ret ann_to_type(ann); }
+    }
+
+    fail;
+}
+
+// Type unification
+
+fn unify(@ty expected, @ty actual) -> unify_result {
+    // Wraps the given type in an appropriate cname.
+    //
+    // TODO: This doesn't do anything yet. We should carry the cname up from
+    // the expected and/or actual types when unification results in a type
+    // identical to one or both of the two. The precise algorithm for this is
+    // something we'll probably need to develop over time.
+
+    // Simple structural type comparison.
+    fn struct_cmp(@ty expected, @ty actual) -> unify_result {
+        if (expected == actual) {
+            ret ures_ok(expected);
+        }
+
+        ret ures_err(terr_mismatch, expected, actual);
+    }
+
+    fn unify_step(@ty expected, @ty actual, &hashmap[int,@ty] bindings)
+            -> unify_result {
+        // TODO: rewrite this using tuple pattern matching when available, to
+        // avoid all this rightward drift and spikiness.
+        alt (expected.struct) {
+            case (ty_nil)        { ret struct_cmp(expected, actual); }
+            case (ty_bool)       { ret struct_cmp(expected, actual); }
+            case (ty_int)        { ret struct_cmp(expected, actual); }
+            case (ty_uint)       { ret struct_cmp(expected, actual); }
+            case (ty_machine(_)) { ret struct_cmp(expected, actual); }
+            case (ty_char)       { ret struct_cmp(expected, actual); }
+            case (ty_str)        { ret struct_cmp(expected, actual); }
+
+            case (ty_box(?expected_sub)) {
+                alt (actual.struct) {
+                    case (ty_box(?actual_sub)) {
+                        auto result = unify_step(expected_sub, actual_sub,
+                                                 bindings);
+                        alt (result) {
+                            case (ures_ok(?result_sub)) {
+                                ret ures_ok(plain_ty(ty_box(result_sub)));
+                            } 
+                            case (_) {
+                                ret result;
+                            }
+                        }
+                    }
+
+                    // TODO: ty_var
+
+                    case (_) {
+                        ret ures_err(terr_mismatch, expected, actual);
+                    }
+                }
+            }
+
+            case (ty_vec(?expected_sub)) {
+                alt (actual.struct) {
+                    case (ty_vec(?actual_sub)) {
+                        auto result = unify_step(expected_sub, actual_sub,
+                                                 bindings);
+                        alt (result) {
+                            case (ures_ok(?result_sub)) {
+                                ret ures_ok(plain_ty(ty_vec(result_sub)));
+                            }
+                            case (_) {
+                                ret result;
+                            }
+                        }
+                    }
+
+                    // TODO: ty_var
+
+                    case (_) {
+                        ret ures_err(terr_mismatch, expected, actual);
+                   }
+                }
+            }
+
+            case (ty_tup(?expected_elems)) {
+                alt (actual.struct) {
+                    case (ty_tup(?actual_elems)) {
+                        auto expected_len =
+                            _vec.len[tup(bool,@ty)](expected_elems);
+                        auto actual_len =
+                            _vec.len[tup(bool,@ty)](actual_elems);
+                        if (expected_len != actual_len) {
+                            auto err = terr_tuple_size(expected_len,
+                                                       actual_len);
+                            ret ures_err(err, expected, actual);
+                        }
+
+                        // TODO: implement an iterator that can iterate over
+                        // two arrays simultaneously.
+                        let vec[tup(bool, @ty)] result_elems = vec();
+                        auto i = 0u;
+                        while (i < expected_len) {
+                            auto expected_elem = expected_elems.(i);
+                            auto actual_elem = actual_elems.(i);
+                            if (expected_elem._0 != actual_elem._0) {
+                                auto err = terr_tuple_mutability;
+                                ret ures_err(err, expected, actual);
+                            }
+
+                            auto result = unify_step(expected_elem._1,
+                                                     actual_elem._1,
+                                                     bindings);
+                            alt (result) {
+                                case (ures_ok(?rty)) {
+                                    result_elems += vec(tup(expected_elem._0,
+                                                            rty));
+                                }
+                                case (_) {
+                                    ret result;
+                                }
+                            }
+
+                            i += 1u;
+                        }
+
+                        ret ures_ok(plain_ty(ty_tup(result_elems)));
+                    }
+
+                    // TODO: ty_var
+
+                    case (_) {
+                        ret ures_err(terr_mismatch, expected, actual);
+                    }
+                }
+            }
+
+            case (ty_fn(?expected_inputs, ?expected_output)) {
+                alt (actual.struct) {
+                    case (ty_fn(?actual_inputs, ?actual_output)) {
+                        auto expected_len = _vec.len[arg](expected_inputs);
+                        auto actual_len = _vec.len[arg](actual_inputs);
+                        if (expected_len != actual_len) {
+                            ret ures_err(terr_arg_count, expected, actual);
+                        }
+
+                        // TODO: as above, we should have an iter2 iterator.
+                        let vec[arg] result_ins = vec();
+                        auto i = 0u;
+                        while (i < expected_len) {
+                            auto expected_input = expected_inputs.(i);
+                            auto actual_input = actual_inputs.(i);
+
+                            // This should be safe, I think?
+                            auto result_mode;
+                            if (mode_is_alias(expected_input.mode) ||
+                                    mode_is_alias(actual_input.mode)) {
+                                result_mode = ast.alias;
+                            } else {
+                                result_mode = ast.val;
+                            }
+
+                            auto result = unify_step(expected_input.ty,
+                                                     actual_input.ty,
+                                                     bindings);
+
+                            alt (result) {
+                                case (ures_ok(?rty)) {
+                                    result_ins += vec(rec(mode=result_mode,
+                                                          ty=rty));
+                                }
+
+                                case (_) {
+                                    ret result;
+                                }
+                            }
+
+                            i += 1u;
+                        }
+
+                        // Check the output.
+                        auto result_out;
+                        auto result = unify_step(expected_output,
+                                                 actual_output, bindings);
+                        alt (result) {
+                            case (ures_ok(?rty)) {  
+                                result_out = rty;
+                            }
+
+                            case (_) {
+                                ret result;
+                            }
+                        }
+
+                        ret ures_ok(plain_ty(ty_fn(result_ins, result_out)));
+                    }
+
+                    case (_) {
+                        ret ures_err(terr_mismatch, expected, actual);
+                    }
+                }
+            }
+
+            case (ty_var(?expected_id)) {
+                if (bindings.contains_key(expected_id)) {
+                     auto binding = bindings.get(expected_id);
+                     ret unify_step(binding, actual, bindings);
+                }
+
+                bindings.insert(expected_id, actual);
+                ret ures_ok(actual);
+            }
+        }
+
+        // TODO: remove me once match-exhaustiveness checking works
+        fail;
+    }
+
+    fn hash_int(&int x) -> uint { ret x as uint; }
+    fn eq_int(&int a, &int b) -> bool { ret a == b; }
+    auto hasher = hash_int;
+    auto eqer = eq_int;
+    auto bindings = map.mk_hashmap[int,@ty](hasher, eqer);
+
+    ret unify_step(expected, actual, bindings);
+}
+
+// Requires that the two types unify, and prints an error message if they
+// don't. Returns the unified type.
+fn demand(&@env e, &span sp, @ty expected, @ty actual) -> @ty {
+    alt (unify(expected, actual)) {
+        case (ures_ok(?ty)) {
+            ret ty;
+        }
+
+        case (ures_err(?err, ?expected, ?actual)) {
+            e.sess.err("mismatched types: expected " + ty_to_str(expected) +
+                       " but found " + ty_to_str(actual) + " (" +
+                       type_err_to_str(err) + ")");
+
+            // TODO: In the future, try returning "expected", reporting the
+            // error, and continue.
+            fail;
+        }
+    }
+}
+
+// Unifies the supplied type with the type of the local `id`, and stores the
+// unified type in the local table. Emits an error if the type is incompatible
+// with the previously-stored type for this local.
+fn demand_local(&@env e, &span sp, &@ty_table locals, ast.def_id local_id,
+                @ty t) {
+    auto prev_ty = locals.get(local_id);
+    auto unified_ty = demand(e, sp, prev_ty, t);
+    locals.insert(local_id, unified_ty);
+}
+
+// Returns true if the two types unify and false if they don't.
+fn are_compatible(@ty expected, @ty actual) -> bool {
+    alt (unify(expected, actual)) {
+        case (ures_ok(_))        { ret true;  }
+        case (ures_err(_, _, _)) { ret false; }
+    }
+}
+
+// Writeback: the phase that writes inferred types back into the AST.
+
+fn writeback_local(&@ty_table locals, &span sp, @ast.local local)
+        -> @ast.decl {
+    auto local_wb = @rec(ann=ast.ann_type(locals.get(local.id)) with *local);
+    ret @fold.respan[ast.decl_](sp, ast.decl_local(local_wb));
+}
+
+fn writeback(&@env e, &@ty_table locals, &ast.block block) -> ast.block {
+    auto fld = fold.new_identity_fold[@ty_table]();
+    auto f = writeback_local;   // FIXME: trans_const_lval bug
+    fld = @rec(fold_decl_local = f with *fld);
+    ret fold.fold_block[@ty_table](locals, fld, block);
+}
+
+// AST fragment checking
+
+fn check_lit(&@env e, @ast.lit lit) -> @ty {
+    auto sty;
+    alt (lit.node) {
+        case (ast.lit_str(_))   { sty = ty_str;  }
+        case (ast.lit_char(_))  { sty = ty_char; }
+        case (ast.lit_int(_))   { sty = ty_int;  }
+        case (ast.lit_uint(_))  { sty = ty_uint; }
+        case (ast.lit_nil)      { sty = ty_nil;  }
+        case (ast.lit_bool(_))  { sty = ty_bool; }
+    }
+
+    ret plain_ty(sty);
+}
+
+fn check_expr(&@env e, &@ty_table locals, @ast.expr expr) -> @ast.expr {
+    alt (expr.node) {
+        case (ast.expr_lit(?lit, _)) {
+            auto ty = check_lit(e, lit);
+            ret @fold.respan[ast.expr_](expr.span,
+                                        ast.expr_lit(lit, ast.ann_type(ty)));
+        }
+        
+        case (_) {
+            // TODO
+            ret expr;
+        }
+    }
+}
+
+fn check_stmt(@env e, @ty_table locals, @ty ret_ty, &@ast.stmt stmt)
+        -> @ast.stmt {
+    alt (stmt.node) {
+        case (ast.stmt_decl(?decl)) {
+            alt (decl.node) {
+                case (ast.decl_local(?local)) {
+                    alt (local.init) {
+                        case (none[@ast.expr]) {
+                            // empty
+                        }
+
+                        case (some[@ast.expr](?expr)) {
+                            auto expr_t = check_expr(e, locals, expr);
+                            locals.insert(local.id, type_of(expr_t));
+
+                            alt (local.ty) {
+                                case (none[@ast.ty]) {
+                                    // Nothing to do. We'll figure out the
+                                    // type later.
+                                }
+
+                                case (some[@ast.ty](?ast_ty)) {
+                                    auto ty = ast_ty_to_ty_env(e, ast_ty);
+                                    demand_local(e, decl.span, locals,
+                                                 local.id, ty);
+                                }
+                            }
+                        }
+                    }
+                }
+
+                case (ast.decl_item(_)) {
+                    // Ignore for now. We'll return later.
+                }
+            }
+
+            ret stmt;
+        }
+
+        case (ast.stmt_ret(?expr_opt)) {
+            alt (expr_opt) {
+                case (none[@ast.expr]) {
+                    if (!are_compatible(ret_ty, plain_ty(ty_nil))) {
+                        e.sess.err("ret; in function returning non-void");
+                    }
+
+                    ret stmt;
+                }
+
+                case (some[@ast.expr](?expr)) {
+                    auto expr_t = check_expr(e, locals, expr);
+                    demand(e, expr.span, ret_ty, type_of(expr_t));
+                    ret @fold.respan[ast.stmt_](stmt.span,
+                                                ast.stmt_ret(some(expr_t)));
+                }
+            }
+        }
+
+        case (ast.stmt_log(?expr)) {
+            auto expr_t = check_expr(e, locals, expr);
+            ret @fold.respan[ast.stmt_](stmt.span, ast.stmt_log(expr_t));
+        }
+
+        case (ast.stmt_check_expr(?expr)) {
+            auto expr_t = check_expr(e, locals, expr);
+            demand(e, expr.span, plain_ty(ty_bool), type_of(expr_t));
+            ret @fold.respan[ast.stmt_](stmt.span,
+                                        ast.stmt_check_expr(expr_t));
+        }
+
+        case (ast.stmt_expr(?expr)) {
+            auto expr_t = check_expr(e, locals, expr);
+            if (!are_compatible(type_of(expr_t), plain_ty(ty_nil))) {
+                // TODO: real warning function
+                log "warning: expression used as statement should have " +
+                    "void type";
+            }
+
+            ret @fold.respan[ast.stmt_](stmt.span, ast.stmt_expr(expr_t));
+        }
+    }
+
+    fail;
+}
+
+fn check_block(&@env e, &@ty_table locals, @ty ret_ty, &ast.block block)
+        -> ast.block {
+    auto f = bind check_stmt(e, locals, ret_ty, _);
+    auto stmts_t = _vec.map[@ast.stmt,@ast.stmt](f, block.node.stmts);
+    ret fold.respan[ast.block_](block.span,
+                                rec(stmts=stmts_t, index=block.node.index));
+}
+
+fn check_fn(&@env e, &span sp, ast.ident ident, &ast._fn f, ast.def_id id,
+            ast.ann ann) -> @ast.item {
+    auto local_ty_table = @common.new_def_hash[@ty]();
+
+    // Store the type of each argument in the table.
+    let vec[arg] inputs = vec();
+    for (ast.arg arg in f.inputs) {
+        auto input_ty = ast_ty_to_ty_env(e, arg.ty);
+        inputs += vec(rec(mode=arg.mode, ty=input_ty));
+        local_ty_table.insert(arg.id, input_ty);
+    }
+
+    auto output_ty = ast_ty_to_ty_env(e, f.output);
+    auto fn_sty = ty_fn(inputs, output_ty);
+    auto fn_ann = ast.ann_type(plain_ty(fn_sty));
+
+    auto block_t = check_block(e, local_ty_table, output_ty, f.body);
+    auto block_wb = writeback(e, local_ty_table, block_t);
+    auto fn_t = rec(inputs=f.inputs, output=f.output, body=block_wb);
+    ret @fold.respan[ast.item_](sp, ast.item_fn(ident, fn_t, id, fn_ann));
+}
+
+fn check_crate(session.session sess, @ast.crate crate) -> @ast.crate {
+    auto result = collect_item_types(crate);
+    auto e = @rec(sess=sess, item_types=result._1, mutable next_var_id=0);
+
+    auto fld = fold.new_identity_fold[@env]();
+    auto f = check_fn;  // FIXME: trans_const_lval bug
+    fld = @rec(fold_item_fn = f with *fld);
+    ret fold.fold_crate[@env](e, fld, result._0);
+}
+
diff --git a/src/comp/rustc.rc b/src/comp/rustc.rc
index 7b314ad7..ef9be053 100644
--- a/src/comp/rustc.rc
+++ b/src/comp/rustc.rc
@@ -14,6 +14,7 @@ mod middle {
     mod fold;
     mod resolve;
     mod trans;
+    mod typeck;
 }
 
 mod back {