Merge branch 'master' into recursive-elseif

Conflicts:

	src/Makefile
	src/comp/front/ast.rs
	src/comp/front/parser.rs
	src/comp/middle/fold.rs
	src/comp/middle/trans.rs

1 files changed, 489 insertions, 190 deletions

diff --git a/src/comp/middle/ty.rs b/src/comp/middle/ty.rs
index f27595a1..5a595db6 100644
--- a/src/comp/middle/ty.rs
+++ b/src/comp/middle/ty.rs
@@ -19,7 +19,10 @@ import util.common.span;
 
 type arg = rec(ast.mode mode, @t ty);
 type field = rec(ast.ident ident, @t ty);
-type method = rec(ast.ident ident, vec[arg] inputs, @t output);
+type method = rec(ast.proto proto,
+                  ast.ident ident,
+                  vec[arg] inputs,
+                  @t output);
 
 // NB: If you change this, you'll probably want to change the corresponding
 // AST structure in front/ast.rs as well.
@@ -32,16 +35,19 @@ tag sty {
     ty_machine(util.common.ty_mach);
     ty_char;
     ty_str;
-    ty_tag(ast.def_id);
+    ty_tag(ast.def_id, vec[@t]);
     ty_box(@t);
     ty_vec(@t);
     ty_tup(vec[@t]);
     ty_rec(vec[field]);
-    ty_fn(vec[arg], @t);                            // TODO: effect
+    ty_fn(ast.proto, vec[arg], @t);                 // TODO: effect
+    ty_native_fn(ast.native_abi, vec[arg], @t);     // TODO: effect
     ty_obj(vec[method]);
     ty_var(int);                                    // ephemeral type var
     ty_local(ast.def_id);                           // type of a local var
-    ty_param(ast.def_id);                           // fn type param
+    ty_param(ast.def_id);                           // fn/tag type param
+    ty_type;
+    ty_native;
     // TODO: ty_fn_arg(@t), for a possibly-aliased function argument
 }
 
@@ -103,6 +109,7 @@ fn ast_ty_to_str(&@ast.ty ty) -> str {
         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_type)         { s = "type";                          }
 
         case (ast.ty_tup(?elts)) {
             auto f = ast_ty_to_str;
@@ -118,9 +125,13 @@ fn ast_ty_to_str(&@ast.ty ty) -> str {
             s += ")";
         }
 
-        case (ast.ty_fn(?inputs, ?output)) {
+        case (ast.ty_fn(?proto, ?inputs, ?output)) {
             auto f = ast_fn_input_to_str;
-            s = "fn(";
+            if (proto == ast.proto_fn) {
+                s = "fn(";
+            } else {
+                s = "iter(";
+            }
             auto is = _vec.map[rec(ast.mode mode, @ast.ty ty),str](f, inputs);
             s += _str.connect(is, ", ");
             s += ")";
@@ -138,6 +149,7 @@ fn ast_ty_to_str(&@ast.ty ty) -> str {
             s = "mutable " + ast_ty_to_str(t);
         }
 
+
         case (_) {
             fail;   // FIXME: typestate bug
         }
@@ -157,6 +169,8 @@ fn path_to_str(&ast.path pth) -> str {
     ret result;
 }
 
+// FIXME use the pretty-printer for this once it has a concept of an
+// abstract stream
 fn ty_to_str(&@t typ) -> str {
 
     fn fn_input_to_str(&rec(ast.mode mode, @t ty) input) -> str {
@@ -170,10 +184,14 @@ fn ty_to_str(&@t typ) -> str {
         ret s + ty_to_str(input.ty);
     }
 
-    fn fn_to_str(option.t[ast.ident] ident,
+    fn fn_to_str(ast.proto proto,
+                 option.t[ast.ident] ident,
                  vec[arg] inputs, @t output) -> str {
             auto f = fn_input_to_str;
             auto s = "fn";
+            if (proto == ast.proto_iter) {
+                s = "iter";
+            }
             alt (ident) {
                 case (some[ast.ident](?i)) {
                     s += " ";
@@ -193,7 +211,8 @@ fn ty_to_str(&@t typ) -> str {
     }
 
     fn method_to_str(&method m) -> str {
-        ret fn_to_str(some[ast.ident](m.ident), m.inputs, m.output) + ";";
+        ret fn_to_str(m.proto, some[ast.ident](m.ident),
+                      m.inputs, m.output) + ";";
     }
 
     fn field_to_str(&field f) -> str {
@@ -206,6 +225,7 @@ fn ty_to_str(&@t typ) -> str {
     }
 
     alt (typ.struct) {
+        case (ty_native)       { s = "native";                    }
         case (ty_nil)          { s = "()";                        }
         case (ty_bool)         { s = "bool";                      }
         case (ty_int)          { s = "int";                       }
@@ -215,6 +235,7 @@ fn ty_to_str(&@t typ) -> str {
         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_type)         { s = "type";                      }
 
         case (ty_tup(?elems)) {
             auto f = ty_to_str;
@@ -228,13 +249,23 @@ fn ty_to_str(&@t typ) -> str {
             s = "rec(" + _str.connect(strs, ",") + ")";
         }
 
-        case (ty_tag(_)) {
+        case (ty_tag(?id, ?tps)) {
             // The user should never see this if the cname is set properly!
-            s = "<tag>";
+            s = "<tag#" + util.common.istr(id._0) + ":" +
+                util.common.istr(id._1) + ">";
+            if (_vec.len[@t](tps) > 0u) {
+                auto f = ty_to_str;
+                auto strs = _vec.map[@t,str](f, tps);
+                s += "[" + _str.connect(strs, ",") + "]";
+            }
+        }
+
+        case (ty_fn(?proto, ?inputs, ?output)) {
+            s = fn_to_str(proto, none[ast.ident], inputs, output);
         }
 
-        case (ty_fn(?inputs, ?output)) {
-            s = fn_to_str(none[ast.ident], inputs, output);
+        case (ty_native_fn(_, ?inputs, ?output)) {
+            s = fn_to_str(ast.proto_fn, none[ast.ident], inputs, output);
         }
 
         case (ty_obj(?meths)) {
@@ -280,13 +311,21 @@ fn fold_ty(ty_fold fld, @t ty) -> @t {
         case (ty_machine(_))    { ret fld.fold_simple_ty(ty); }
         case (ty_char)          { ret fld.fold_simple_ty(ty); }
         case (ty_str)           { ret fld.fold_simple_ty(ty); }
-        case (ty_tag(_))        { ret fld.fold_simple_ty(ty); }
+        case (ty_type)          { ret fld.fold_simple_ty(ty); }
+        case (ty_native)        { ret fld.fold_simple_ty(ty); }
         case (ty_box(?subty)) {
             ret rewrap(ty, ty_box(fold_ty(fld, subty)));
         }
         case (ty_vec(?subty)) {
             ret rewrap(ty, ty_vec(fold_ty(fld, subty)));
         }
+        case (ty_tag(?tid, ?subtys)) {
+            let vec[@t] new_subtys = vec();
+            for (@t subty in subtys) {
+                new_subtys += vec(fold_ty(fld, subty));
+            }
+            ret rewrap(ty, ty_tag(tid, new_subtys));
+        }
         case (ty_tup(?subtys)) {
             let vec[@t] new_subtys = vec();
             for (@t subty in subtys) {
@@ -302,13 +341,21 @@ fn fold_ty(ty_fold fld, @t ty) -> @t {
             }
             ret rewrap(ty, ty_rec(new_fields));
         }
-        case (ty_fn(?args, ?ret_ty)) {
+        case (ty_fn(?proto, ?args, ?ret_ty)) {
             let vec[arg] new_args = vec();
             for (arg a in args) {
                 auto new_ty = fold_ty(fld, a.ty);
                 new_args += vec(rec(mode=a.mode, ty=new_ty));
             }
-            ret rewrap(ty, ty_fn(new_args, fold_ty(fld, ret_ty)));
+            ret rewrap(ty, ty_fn(proto, new_args, fold_ty(fld, ret_ty)));
+        }
+        case (ty_native_fn(?abi, ?args, ?ret_ty)) {
+            let vec[arg] new_args = vec();
+            for (arg a in args) {
+                auto new_ty = fold_ty(fld, a.ty);
+                new_args += vec(rec(mode=a.mode, ty=new_ty));
+            }
+            ret rewrap(ty, ty_native_fn(abi, new_args, fold_ty(fld, ret_ty)));
         }
         case (ty_obj(?methods)) {
             let vec[method] new_methods = vec();
@@ -317,7 +364,8 @@ fn fold_ty(ty_fold fld, @t ty) -> @t {
                 for (arg a in m.inputs) {
                     new_args += vec(rec(mode=a.mode, ty=fold_ty(fld, a.ty)));
                 }
-                new_methods += vec(rec(ident=m.ident, inputs=new_args,
+                new_methods += vec(rec(proto=m.proto, ident=m.ident,
+                                       inputs=new_args,
                                        output=fold_ty(fld, m.output)));
             }
             ret rewrap(ty, ty_obj(new_methods));
@@ -327,7 +375,7 @@ fn fold_ty(ty_fold fld, @t ty) -> @t {
         case (ty_param(_))      { ret fld.fold_simple_ty(ty); }
     }
 
-    ret ty;
+    fail;
 }
 
 // Type utilities
@@ -349,24 +397,44 @@ fn type_is_nil(@t ty) -> bool {
     fail;
 }
 
+
 fn type_is_structural(@t ty) -> bool {
     alt (ty.struct) {
-        case (ty_tup(_)) { ret true; }
-        case (ty_rec(_)) { ret true; }
-        case (ty_tag(_)) { ret true; }
-        case (ty_fn(_,_)) { ret true; }
-        case (ty_obj(_)) { ret true; }
-        case (_) { ret false; }
+        case (ty_tup(_))    { ret true; }
+        case (ty_rec(_))    { ret true; }
+        case (ty_tag(_,_))  { ret true; }
+        case (ty_fn(_,_,_)) { ret true; }
+        case (ty_obj(_))    { ret true; }
+        case (_)            { ret false; }
+    }
+    fail;
+}
+
+fn type_is_sequence(@t ty) -> bool {
+    alt (ty.struct) {
+        case (ty_str)    { ret true; }
+        case (ty_vec(_))    { ret true; }
+        case (_)            { ret false; }
+    }
+    fail;
+}
+
+fn sequence_element_type(@t ty) -> @t {
+    alt (ty.struct) {
+        case (ty_str)     { ret plain_ty(ty_machine(common.ty_u8)); }
+        case (ty_vec(?e)) { ret e; }
     }
     fail;
 }
 
+
 fn type_is_tup_like(@t ty) -> bool {
     alt (ty.struct) {
-        case (ty_tup(_)) { ret true; }
-        case (ty_rec(_)) { ret true; }
-        case (ty_tag(_)) { ret true; }
-        case (_) { ret false; }
+        case (ty_box(_))    { ret true; }
+        case (ty_tup(_))    { ret true; }
+        case (ty_rec(_))    { ret true; }
+        case (ty_tag(_,_))  { ret true; }
+        case (_)            { ret false; }
     }
     fail;
 }
@@ -402,6 +470,17 @@ fn type_is_scalar(@t ty) -> bool {
         case (ty_uint) { ret true; }
         case (ty_machine(_)) { ret true; }
         case (ty_char) { ret true; }
+        case (ty_type) { ret true; }
+        case (_) { ret false; }
+    }
+    fail;
+}
+
+// FIXME: should we just return true for native types in
+// type_is_scalar?
+fn type_is_native(@t ty) -> bool {
+    alt (ty.struct) {
+        case (ty_native) { ret true; }
         case (_) { ret false; }
     }
     fail;
@@ -423,6 +502,13 @@ fn type_has_dynamic_size(@t ty) -> bool {
                 i += 1u;
             }
         }
+        case (ty_tag(_, ?subtys)) {
+            auto i = 0u;
+            while (i < _vec.len[@t](subtys)) {
+                if (type_has_dynamic_size(subtys.(i))) { ret true; }
+                i += 1u;
+            }
+        }
         case (ty_param(_)) { ret true; }
         case (_) { /* fall through */ }
     }
@@ -547,23 +633,42 @@ fn count_ty_params(@t ty) -> uint {
 // Type accessors for substructures of types
 
 fn ty_fn_args(@t fty) -> vec[arg] {
-  alt (fty.struct) {
-    case (ty.ty_fn(?a, _)) { ret a; }
-  }
+    alt (fty.struct) {
+        case (ty.ty_fn(_, ?a, _)) { ret a; }
+        case (ty.ty_native_fn(_, ?a, _)) { ret a; }
+    }
+    fail;
+}
+
+fn ty_fn_proto(@t fty) -> ast.proto {
+    alt (fty.struct) {
+        case (ty.ty_fn(?p, _, _)) { ret p; }
+    }
+    fail;
+}
+
+fn ty_fn_abi(@t fty) -> ast.native_abi {
+    alt (fty.struct) {
+        case (ty.ty_native_fn(?a, _, _)) { ret a; }
+    }
+    fail;
 }
 
 fn ty_fn_ret(@t fty) -> @t {
-  alt (fty.struct) {
-    case (ty.ty_fn(_, ?r)) { ret r; }
-  }
+    alt (fty.struct) {
+        case (ty.ty_fn(_, _, ?r)) { ret r; }
+        case (ty.ty_native_fn(_, _, ?r)) { ret r; }
+    }
+    fail;
 }
 
 fn is_fn_ty(@t fty) -> bool {
-  alt (fty.struct) {
-    case (ty.ty_fn(_, _)) { ret true; }
-    case (_) { ret false; }
-  }
-  ret false;
+    alt (fty.struct) {
+        case (ty.ty_fn(_, _, _)) { ret true; }
+        case (ty.ty_native_fn(_, _, _)) { ret true; }
+        case (_) { ret false; }
+    }
+    ret false;
 }
 
 
@@ -571,7 +676,24 @@ fn is_fn_ty(@t fty) -> bool {
 
 // Given an item, returns the associated type as well as a list of the IDs of
 // its type parameters.
-fn item_ty(@ast.item it) -> tup(vec[ast.def_id], @t) {
+type ty_params_and_ty = tup(vec[ast.def_id], @t);
+fn native_item_ty(@ast.native_item it) -> ty_params_and_ty {
+    auto ty_params;
+    auto result_ty;
+    alt (it.node) {
+        case (ast.native_item_fn(_, _, ?tps, _, ?ann)) {
+            ty_params = tps;
+            result_ty = ann_to_type(ann);
+        }
+    }
+    let vec[ast.def_id] ty_param_ids = vec();
+    for (ast.ty_param tp in ty_params) {
+        ty_param_ids += vec(tp.id);
+    }
+    ret tup(ty_param_ids, result_ty);
+}
+
+fn item_ty(@ast.item it) -> ty_params_and_ty {
     let vec[ast.ty_param] ty_params;
     auto result_ty;
     alt (it.node) {
@@ -591,8 +713,13 @@ fn item_ty(@ast.item it) -> tup(vec[ast.def_id], @t) {
             result_ty = ann_to_type(ann);
         }
         case (ast.item_tag(_, _, ?tps, ?did)) {
+            // Create a new generic polytype.
             ty_params = tps;
-            result_ty = plain_ty(ty_tag(did));
+            let vec[@t] subtys = vec();
+            for (ast.ty_param tp in tps) {
+                subtys += vec(plain_ty(ty_param(tp.id)));
+            }
+            result_ty = plain_ty(ty_tag(did, subtys));
         }
         case (ast.item_obj(_, _, ?tps, _, ?ann)) {
             ty_params = tps;
@@ -628,6 +755,7 @@ fn block_ty(&ast.block b) -> @t {
 fn pat_ty(@ast.pat pat) -> @t {
     alt (pat.node) {
         case (ast.pat_wild(?ann))           { ret ann_to_type(ann); }
+        case (ast.pat_lit(_, ?ann))         { ret ann_to_type(ann); }
         case (ast.pat_bind(_, _, ?ann))     { ret ann_to_type(ann); }
         case (ast.pat_tag(_, _, _, ?ann))   { ret ann_to_type(ann); }
     }
@@ -638,7 +766,7 @@ fn expr_ty(@ast.expr expr) -> @t {
     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_rec(_, _, ?ann))       { ret ann_to_type(ann); }
         case (ast.expr_bind(_, _, ?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); }
@@ -647,6 +775,8 @@ fn expr_ty(@ast.expr expr) -> @t {
         case (ast.expr_cast(_, _, ?ann))      { ret ann_to_type(ann); }
         case (ast.expr_if(_, _, _, ?ann))     { ret ann_to_type(ann); }
         case (ast.expr_for(_, _, _, ?ann))    { ret ann_to_type(ann); }
+        case (ast.expr_for_each(_, _, _, ?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_alt(_, _, ?ann))       { ret ann_to_type(ann); }
@@ -657,6 +787,14 @@ fn expr_ty(@ast.expr expr) -> @t {
         case (ast.expr_field(_, _, ?ann))     { ret ann_to_type(ann); }
         case (ast.expr_index(_, _, ?ann))     { ret ann_to_type(ann); }
         case (ast.expr_path(_, _, ?ann))      { ret ann_to_type(ann); }
+        case (ast.expr_ext(_, _, _, _, ?ann)) { ret ann_to_type(ann); }
+
+        case (ast.expr_fail)                  { ret plain_ty(ty_nil); }
+        case (ast.expr_log(_))                { ret plain_ty(ty_nil); }
+        case (ast.expr_check_expr(_))         { ret plain_ty(ty_nil); }
+        case (ast.expr_ret(_))                { ret plain_ty(ty_nil); }
+        case (ast.expr_put(_))                { ret plain_ty(ty_nil); }
+        case (ast.expr_be(_))                 { ret plain_ty(ty_nil); }
     }
     fail;
 }
@@ -726,7 +864,10 @@ fn is_lval(@ast.expr expr) -> bool {
     }
 }
 
-// Type unification
+// Type unification via Robinson's algorithm (Robinson 1965). Implemented as
+// described in Hoder and Voronkov:
+//
+//     http://www.cs.man.ac.uk/~hoderk/ubench/unification_full.pdf
 
 fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
         -> unify_result {
@@ -746,81 +887,137 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
         ret ures_err(terr_mismatch, expected, actual);
     }
 
-    fn unify_fn(&hashmap[int,@ty.t] bindings,
-                @ty.t expected,
-                @ty.t actual,
-                &unify_handler handler,
-                vec[arg] expected_inputs, @t expected_output,
-                vec[arg] actual_inputs, @t actual_output)
-      -> unify_result {
-      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);
-      }
+    tag fn_common_res {
+        fn_common_res_err(unify_result);
+        fn_common_res_ok(vec[arg], @t);
+    }
 
-      // 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;
+    fn unify_fn_common(@hashmap[int,@ty.t] bindings,
+                       @ty.t expected,
+                       @ty.t actual,
+                       &unify_handler handler,
+                       vec[arg] expected_inputs, @t expected_output,
+                       vec[arg] actual_inputs, @t actual_output)
+        -> fn_common_res {
+        auto expected_len = _vec.len[arg](expected_inputs);
+        auto actual_len = _vec.len[arg](actual_inputs);
+        if (expected_len != actual_len) {
+            ret fn_common_res_err(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(bindings,
+                                     actual_input.ty,
+                                     expected_input.ty,
+                                     handler);
+
+            alt (result) {
+                case (ures_ok(?rty)) {
+                    result_ins += vec(rec(mode=result_mode,
+                                          ty=rty));
+                }
+
+                case (_) {
+                    ret fn_common_res_err(result);
+                }
+            }
+
+            i += 1u;
         }
 
+        // Check the output.
         auto result = unify_step(bindings,
-                                 actual_input.ty,
-                                 expected_input.ty,
+                                 expected_output,
+                                 actual_output,
                                  handler);
-
         alt (result) {
-          case (ures_ok(?rty)) {
-            result_ins += vec(rec(mode=result_mode,
-                                  ty=rty));
-          }
+            case (ures_ok(?rty)) {
+                ret fn_common_res_ok(result_ins, rty);
+            }
 
-          case (_) {
-            ret result;
-          }
+            case (_) {
+                ret fn_common_res_err(result);
+            }
         }
+    }
 
-        i += 1u;
-      }
+    fn unify_fn(@hashmap[int,@ty.t] bindings,
+                ast.proto e_proto,
+                ast.proto a_proto,
+                @ty.t expected,
+                @ty.t actual,
+                &unify_handler handler,
+                vec[arg] expected_inputs, @t expected_output,
+                vec[arg] actual_inputs, @t actual_output)
+        -> unify_result {
 
-      // Check the output.
-      auto result_out;
-      auto result = unify_step(bindings,
-                               expected_output,
-                               actual_output,
-                               handler);
-      alt (result) {
-        case (ures_ok(?rty)) {
-          result_out = rty;
+        if (e_proto != a_proto) {
+            ret ures_err(terr_mismatch, expected, actual);
         }
-
-        case (_) {
-          ret result;
+        auto t = unify_fn_common(bindings, expected, actual,
+                                 handler, expected_inputs, expected_output,
+                                 actual_inputs, actual_output);
+        alt (t) {
+            case (fn_common_res_err(?r)) {
+                ret r;
+            }
+            case (fn_common_res_ok(?result_ins, ?result_out)) {
+                auto t2 = plain_ty(ty.ty_fn(e_proto, result_ins, result_out));
+                ret ures_ok(t2);
+            }
         }
-      }
+    }
 
-      auto t = plain_ty(ty.ty_fn(result_ins, result_out));
-      ret ures_ok(t);
+    fn unify_native_fn(@hashmap[int,@ty.t] bindings,
+                       ast.native_abi e_abi,
+                       ast.native_abi a_abi,
+                       @ty.t expected,
+                       @ty.t actual,
+                       &unify_handler handler,
+                       vec[arg] expected_inputs, @t expected_output,
+                       vec[arg] actual_inputs, @t actual_output)
+        -> unify_result {
+        if (e_abi != a_abi) {
+            ret ures_err(terr_mismatch, expected, actual);
+        }
 
+        auto t = unify_fn_common(bindings, expected, actual,
+                                 handler, expected_inputs, expected_output,
+                                 actual_inputs, actual_output);
+        alt (t) {
+            case (fn_common_res_err(?r)) {
+                ret r;
+            }
+            case (fn_common_res_ok(?result_ins, ?result_out)) {
+                auto t2 = plain_ty(ty.ty_native_fn(e_abi, result_ins,
+                                                   result_out));
+                ret ures_ok(t2);
+            }
+        }
     }
 
-    fn unify_obj(&hashmap[int,@ty.t] bindings,
-                @ty.t expected,
-                @ty.t actual,
-                &unify_handler handler,
-                vec[method] expected_meths,
-                vec[method] actual_meths) -> unify_result {
+    fn unify_obj(@hashmap[int,@ty.t] bindings,
+                 @ty.t expected,
+                 @ty.t actual,
+                 &unify_handler handler,
+                 vec[method] expected_meths,
+                 vec[method] actual_meths) -> unify_result {
       let vec[method] result_meths = vec();
       let uint i = 0u;
       let uint expected_len = _vec.len[method](expected_meths);
@@ -830,32 +1027,6 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
         ret ures_err(terr_meth_count, expected, actual);
       }
 
-      // FIXME: work around buggy typestate logic for 'alt', sigh.
-      fn is_ok(&unify_result r) -> bool {
-        alt (r) {
-          case (ures_ok(?tfn)) {
-            ret true;
-          }
-          case (_) {}
-        }
-        ret false;
-      }
-
-      fn append_if_ok(&method e_meth,
-                      &unify_result r, &mutable vec[method] result_meths) {
-        alt (r) {
-          case (ures_ok(?tfn)) {
-            alt (tfn.struct) {
-              case (ty_fn(?ins, ?out)) {
-                result_meths += vec(rec(inputs = ins,
-                                        output = out
-                                        with e_meth));
-              }
-            }
-          }
-        }
-      }
-
       while (i < expected_len) {
         auto e_meth = expected_meths.(i);
         auto a_meth = actual_meths.(i);
@@ -863,40 +1034,69 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
           ret ures_err(terr_obj_meths(e_meth.ident, a_meth.ident),
                        expected, actual);
         }
-        auto r = unify_fn(bindings, expected, actual, handler,
+        auto r = unify_fn(bindings,
+                          e_meth.proto, a_meth.proto,
+                          expected, actual, handler,
                           e_meth.inputs, e_meth.output,
                           a_meth.inputs, a_meth.output);
-        if (!is_ok(r)) {
-          ret r;
+        alt (r) {
+            case (ures_ok(?tfn)) {
+                alt (tfn.struct) {
+                    case (ty_fn(?proto, ?ins, ?out)) {
+                        result_meths += vec(rec(inputs = ins,
+                                                output = out
+                                                with e_meth));
+                    }
+                }
+            }
+            case (_) {
+                ret r;
+            }
         }
-        append_if_ok(e_meth, r, result_meths);
         i += 1u;
       }
       auto t = plain_ty(ty_obj(result_meths));
       ret ures_ok(t);
     }
 
-    fn unify_step(&hashmap[int,@ty.t] bindings, @ty.t expected, @ty.t actual,
-                  &unify_handler handler) -> unify_result {
+    fn resolve(@hashmap[int,@t] bindings, @t typ) -> @t {
+        alt (typ.struct) {
+            case (ty_var(?id)) {
+                alt (bindings.find(id)) {
+                    case (some[@t](?typ2)) {
+                        ret resolve(bindings, typ2);
+                    }
+                    case (none[@t]) {
+                        // fall through
+                    }
+                }
+            }
+            case (_) {
+                // fall through
+            }
+        }
+        ret typ;
+    }
+
+    fn unify_step(@hashmap[int,@ty.t] bindings, @ty.t in_expected,
+                  @ty.t in_actual, &unify_handler handler) -> unify_result {
+
+        // Resolve any bindings.
+        auto expected = resolve(bindings, in_expected);
+        auto actual = resolve(bindings, in_actual);
+
         // TODO: rewrite this using tuple pattern matching when available, to
         // avoid all this rightward drift and spikiness.
 
+        // TODO: occurs check, to make sure we don't loop forever when
+        // unifying e.g. 'a and option['a]
+
         alt (actual.struct) {
             // If the RHS is a variable type, then just do the appropriate
             // binding.
             case (ty.ty_var(?actual_id)) {
-                alt (bindings.find(actual_id)) {
-                    case (some[@ty.t](?actual_ty)) {
-                        // FIXME: change the binding here?
-                        // FIXME: "be"
-                        ret unify_step(bindings, expected, actual_ty,
-                                       handler);
-                    }
-                    case (none[@ty.t]) {
-                        bindings.insert(actual_id, expected);
-                        ret ures_ok(expected);
-                    }
-                }
+                bindings.insert(actual_id, expected);
+                ret ures_ok(expected);
             }
             case (ty.ty_local(?actual_id)) {
                 auto actual_ty = handler.resolve_local(actual_id);
@@ -938,14 +1138,45 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
             case (ty.ty_machine(_)) { ret struct_cmp(expected, actual); }
             case (ty.ty_char)       { ret struct_cmp(expected, actual); }
             case (ty.ty_str)        { ret struct_cmp(expected, actual); }
+            case (ty.ty_type)       { ret struct_cmp(expected, actual); }
+            case (ty.ty_native)     { ret struct_cmp(expected, actual); }
 
-            case (ty.ty_tag(?expected_id)) {
+            case (ty.ty_tag(?expected_id, ?expected_tps)) {
                 alt (actual.struct) {
-                    case (ty.ty_tag(?actual_id)) {
-                        if (expected_id._0 == actual_id._0 &&
-                                expected_id._1 == actual_id._1) {
-                            ret ures_ok(expected);
+                    case (ty.ty_tag(?actual_id, ?actual_tps)) {
+                        if (expected_id._0 != actual_id._0 ||
+                                expected_id._1 != actual_id._1) {
+                            ret ures_err(terr_mismatch, expected, actual);
                         }
+
+                        // TODO: factor this cruft out, see the TODO in the
+                        // ty.ty_tup case
+                        let vec[@ty.t] result_tps = vec();
+                        auto i = 0u;
+                        auto expected_len = _vec.len[@ty.t](expected_tps);
+                        while (i < expected_len) {
+                            auto expected_tp = expected_tps.(i);
+                            auto actual_tp = actual_tps.(i);
+
+                            auto result = unify_step(bindings,
+                                                     expected_tp,
+                                                     actual_tp,
+                                                     handler);
+
+                            alt (result) {
+                                case (ures_ok(?rty)) {
+                                    append[@ty.t](result_tps, rty);
+                                }
+                                case (_) {
+                                    ret result;
+                                }
+                            }
+
+                            i += 1u;
+                        }
+
+                        ret ures_ok(plain_ty(ty.ty_tag(expected_id,
+                                                       result_tps)));
                     }
                     case (_) { /* fall through */ }
                 }
@@ -970,8 +1201,6 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                         }
                     }
 
-                    // TODO: ty_var
-
                     case (_) {
                         ret ures_err(terr_mismatch, expected, actual);
                     }
@@ -995,8 +1224,6 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                         }
                     }
 
-                    // TODO: ty_var
-
                     case (_) {
                         ret ures_err(terr_mismatch, expected, actual);
                    }
@@ -1045,8 +1272,6 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                         ret ures_ok(plain_ty(ty.ty_tup(result_elems)));
                     }
 
-                    // TODO: ty_var
-
                     case (_) {
                         ret ures_err(terr_mismatch, expected, actual);
                     }
@@ -1106,20 +1331,19 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                         ret ures_ok(plain_ty(ty.ty_rec(result_fields)));
                     }
 
-                    // TODO: ty_var
-
                     case (_) {
                         ret ures_err(terr_mismatch, expected, actual);
                     }
                 }
             }
 
-            case (ty.ty_fn(?expected_inputs, ?expected_output)) {
+            case (ty.ty_fn(?ep, ?expected_inputs, ?expected_output)) {
                 alt (actual.struct) {
-                    case (ty.ty_fn(?actual_inputs, ?actual_output)) {
-                      ret unify_fn(bindings, expected, actual, handler,
-                                   expected_inputs, expected_output,
-                                   actual_inputs, actual_output);
+                    case (ty.ty_fn(?ap, ?actual_inputs, ?actual_output)) {
+                        ret unify_fn(bindings, ep, ap,
+                                     expected, actual, handler,
+                                     expected_inputs, expected_output,
+                                     actual_inputs, actual_output);
                     }
 
                     case (_) {
@@ -1128,35 +1352,40 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                 }
             }
 
-            case (ty.ty_obj(?expected_meths)) {
-              alt (actual.struct) {
-                case (ty.ty_obj(?actual_meths)) {
-                  ret unify_obj(bindings, expected, actual, handler,
-                                expected_meths, actual_meths);
-                }
-                case (_) {
-                  ret ures_err(terr_mismatch, expected, actual);
+            case (ty.ty_native_fn(?e_abi, ?expected_inputs,
+                                  ?expected_output)) {
+                alt (actual.struct) {
+                    case (ty.ty_native_fn(?a_abi, ?actual_inputs,
+                                          ?actual_output)) {
+                        ret unify_native_fn(bindings, e_abi, a_abi,
+                                            expected, actual, handler,
+                                            expected_inputs, expected_output,
+                                            actual_inputs, actual_output);
+                    }
+                    case (_) {
+                        ret ures_err(terr_mismatch, expected, actual);
+                    }
                 }
-              }
             }
 
-            case (ty.ty_var(?expected_id)) {
-                alt (bindings.find(expected_id)) {
-                    case (some[@ty.t](?expected_ty)) {
-                        // FIXME: change the binding here?
-                        // FIXME: "be"
-                        ret unify_step(bindings,
-                                       expected_ty,
-                                       actual,
-                                       handler);
+            case (ty.ty_obj(?expected_meths)) {
+                alt (actual.struct) {
+                    case (ty.ty_obj(?actual_meths)) {
+                        ret unify_obj(bindings, expected, actual, handler,
+                                      expected_meths, actual_meths);
                     }
-                    case (none[@ty.t]) {
-                        bindings.insert(expected_id, actual);
-                        ret ures_ok(actual);
+                    case (_) {
+                        ret ures_err(terr_mismatch, expected, actual);
                     }
                 }
             }
 
+            case (ty.ty_var(?expected_id)) {
+                // Add a binding.
+                bindings.insert(expected_id, actual);
+                ret ures_ok(actual);
+            }
+
             case (ty.ty_local(?expected_id)) {
                 auto expected_ty = handler.resolve_local(expected_id);
                 auto result = unify_step(bindings,
@@ -1182,13 +1411,43 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
         fail;
     }
 
+    // Performs type binding substitution.
+    fn substitute(@hashmap[int,@t] bindings, @t typ) -> @t {
+        state obj folder(@hashmap[int,@t] bindings) {
+            fn fold_simple_ty(@t typ) -> @t {
+                alt (typ.struct) {
+                    case (ty_var(?id)) {
+                        alt (bindings.find(id)) {
+                            case (some[@t](?typ2)) {
+                                ret substitute(bindings, typ2);
+                            }
+                            case (none[@t]) {
+                                ret typ;
+                            }
+                        }
+                    }
+                    case (_) {
+                        ret typ;
+                    }
+                }
+            }
+        }
+
+        ret ty.fold_ty(folder(bindings), typ);
+    }
+
     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.t](hasher, eqer);
+    auto bindings = @map.mk_hashmap[int,@ty.t](hasher, eqer);
 
-    ret unify_step(bindings, expected, actual, handler);
+    auto ures = unify_step(bindings, expected, actual, handler);
+    alt (ures) {
+        case (ures_ok(?t))  { ret ures_ok(substitute(bindings, t)); }
+        case (_)            { ret ures;                             }
+    }
+    fail;   // not reached
 }
 
 fn type_err_to_str(&ty.type_err err) -> str {
@@ -1231,9 +1490,10 @@ fn type_err_to_str(&ty.type_err err) -> str {
     }
 }
 
-// Type parameter resolution, used in translation
+// Type parameter resolution, used in translation and typechecking
 
-fn resolve_ty_params(@ast.item item, @t monoty) -> vec[@t] {
+fn resolve_ty_params(ty_params_and_ty ty_params_and_polyty,
+                     @t monoty) -> vec[@t] {
     obj resolve_ty_params_handler(@hashmap[ast.def_id,@t] bindings) {
         fn resolve_local(ast.def_id id) -> @t { log "resolve local"; fail; }
         fn record_local(ast.def_id id, @t ty) { log "record local"; fail; }
@@ -1249,8 +1509,6 @@ fn resolve_ty_params(@ast.item item, @t monoty) -> vec[@t] {
         }
     }
 
-    auto ty_params_and_polyty = item_ty(item);
-
     auto bindings = @new_def_hash[@t]();
     auto handler = resolve_ty_params_handler(bindings);
 
@@ -1274,6 +1532,47 @@ fn resolve_ty_params(@ast.item item, @t monoty) -> vec[@t] {
     ret result_tys;
 }
 
+// Performs type parameter replacement using the supplied mapping from
+// parameter IDs to types.
+fn replace_type_params(@t typ, hashmap[ast.def_id,@t] param_map) -> @t {
+    state obj param_replacer(hashmap[ast.def_id,@t] param_map) {
+        fn fold_simple_ty(@t typ) -> @t {
+            alt (typ.struct) {
+                case (ty_param(?param_def)) {
+                    if (param_map.contains_key(param_def)) {
+                        ret param_map.get(param_def);
+                    } else {
+                        ret typ;
+                    }
+                }
+                case (_) {
+                    ret typ;
+                }
+            }
+        }
+    }
+    auto replacer = param_replacer(param_map);
+    ret fold_ty(replacer, typ);
+}
+
+// Substitutes the type parameters specified by @ty_params with the
+// corresponding types in @bound in the given type. The two vectors must have
+// the same length.
+fn substitute_ty_params(vec[ast.ty_param] ty_params, vec[@t] bound, @t ty)
+        -> @t {
+    auto ty_param_len = _vec.len[ast.ty_param](ty_params);
+    check (ty_param_len == _vec.len[@t](bound));
+
+    auto bindings = common.new_def_hash[@t]();
+    auto i = 0u;
+    while (i < ty_param_len) {
+        bindings.insert(ty_params.(i).id, bound.(i));
+        i += 1u;
+    }
+
+    ret replace_type_params(ty, bindings);
+}
+
 // Local Variables:
 // mode: rust
 // fill-column: 78;