src/comp/middle/ty.rs

   1 import std::int;
   2 import std::str;
   3 import std::uint;
   4 import std::vec;
   5 import std::box;
   6 import std::ufind;
   7 import std::map;
   8 import std::map::hashmap;
   9 import std::option;
  10 import std::option::none;
  11 import std::option::some;
  12 import std::smallintmap;
  13
  14 import driver::session;
  15 import front::ast;
  16 import front::ast::mutability;
  17 import front::ast::controlflow;
  18 import front::creader;
  19 import middle::metadata;
  20 import util::common;
  21
  22 import util::common::ty_u8;
  23 import util::common::ty_u16;
  24 import util::common::ty_u32;
  25 import util::common::ty_u64;
  26
  27 import util::common::ty_i8;
  28 import util::common::ty_i16;
  29 import util::common::ty_i32;
  30 import util::common::ty_i64;
  31
  32 import util::common::ty_f32;
  33 import util::common::ty_f64;
  34
  35 import util::common::new_def_hash;
  36 import util::common::span;
  37
  38 import util::data::interner;
  39
  40 // Data types
  41
  42 tag mode {
  43     mo_val;
  44     mo_alias(bool);
  45 }
  46
  47 type arg = rec(mode mode, t ty);
  48 type field = rec(ast::ident ident, mt mt);
  49 type method = rec(ast::proto proto,
  50                   ast::ident ident,
  51                   vec[arg] inputs,
  52                   t output,
  53                   controlflow cf,
  54                   vec[@ast::constr] constrs);
  55
  56 tag any_item {
  57     any_item_rust(@ast::item);
  58     any_item_native(@ast::native_item, ast::native_abi);
  59 }
  60
  61 type item_table = hashmap[ast::def_id,any_item];
  62
  63 type mt = rec(t ty, ast::mutability mut);
  64
  65 // Contains information needed to resolve types and (in the future) look up
  66 // the types of AST nodes.
  67 type creader_cache = hashmap[tup(int,uint,uint),ty::t];
  68 type ctxt = rec(@type_store ts,
  69                 session::session sess,
  70                 resolve::def_map def_map,
  71                 node_type_table node_types,
  72                 item_table items,
  73                 type_cache tcache,
  74                 creader_cache rcache,
  75                 hashmap[t,str] short_names_cache,
  76                 hashmap[@ast::ty,option::t[t]] ast_ty_to_ty_cache);
  77 type ty_ctxt = ctxt;    // Needed for disambiguation from unify::ctxt.
  78
  79 // Convert from method type to function type.  Pretty easy; we just drop
  80 // 'ident'.
  81 fn method_ty_to_fn_ty(&ctxt cx, method m) -> t {
  82     ret mk_fn(cx, m.proto, m.inputs, m.output, m.cf, m.constrs);
  83 }
  84
  85 // Never construct these manually. These are interned.
  86 //
  87 // TODO: It'd be really nice to be able to hide this definition from the
  88 // outside world, to enforce the above invariants.
  89 type raw_t = rec(sty struct,
  90                  option::t[str] cname,
  91                  uint hash,
  92                  bool has_params,
  93                  bool has_vars);
  94
  95 type t = uint;
  96
  97 // NB: If you change this, you'll probably want to change the corresponding
  98 // AST structure in front/ast::rs as well.
  99 tag sty {
 100     ty_nil;
 101     ty_bot;
 102     ty_bool;
 103     ty_int;
 104     ty_float;
 105     ty_uint;
 106     ty_machine(util::common::ty_mach);
 107     ty_char;
 108     ty_str;
 109     ty_istr;
 110     ty_tag(ast::def_id, vec[t]);
 111     ty_box(mt);
 112     ty_vec(mt);
 113     ty_ivec(mt);
 114     ty_ptr(mt);
 115     ty_port(t);
 116     ty_chan(t);
 117     ty_task;
 118     ty_tup(vec[mt]);
 119     ty_rec(vec[field]);
 120     ty_fn(ast::proto, vec[arg], t, controlflow, vec[@ast::constr]);
 121     ty_native_fn(ast::native_abi, vec[arg], t);
 122     ty_obj(vec[method]);
 123     ty_var(int);                                    // type variable
 124     ty_param(uint);                                 // fn/tag type param
 125     ty_type;
 126     ty_native;
 127     // TODO: ty_fn_arg(t), for a possibly-aliased function argument
 128 }
 129
 130 // Data structures used in type unification
 131
 132 tag type_err {
 133     terr_mismatch;
 134     terr_controlflow_mismatch;
 135     terr_box_mutability;
 136     terr_vec_mutability;
 137     terr_tuple_size(uint, uint);
 138     terr_tuple_mutability;
 139     terr_record_size(uint, uint);
 140     terr_record_mutability;
 141     terr_record_fields(ast::ident,ast::ident);
 142     terr_meth_count;
 143     terr_obj_meths(ast::ident,ast::ident);
 144     terr_arg_count;
 145 }
 146
 147
 148 type ty_param_count_and_ty = tup(uint, t);
 149 type type_cache = hashmap[ast::def_id,ty_param_count_and_ty];
 150
 151 const uint idx_nil      = 0u;
 152 const uint idx_bool     = 1u;
 153 const uint idx_int      = 2u;
 154 const uint idx_float    = 3u;
 155 const uint idx_uint     = 4u;
 156 const uint idx_i8       = 5u;
 157 const uint idx_i16      = 6u;
 158 const uint idx_i32      = 7u;
 159 const uint idx_i64      = 8u;
 160 const uint idx_u8       = 9u;
 161 const uint idx_u16      = 10u;
 162 const uint idx_u32      = 11u;
 163 const uint idx_u64      = 12u;
 164 const uint idx_f32      = 13u;
 165 const uint idx_f64      = 14u;
 166 const uint idx_char     = 15u;
 167 const uint idx_str      = 16u;
 168 const uint idx_istr     = 17u;
 169 const uint idx_task     = 18u;
 170 const uint idx_native   = 19u;
 171 const uint idx_type     = 20u;
 172 const uint idx_bot      = 21u;
 173 const uint idx_first_others = 22u;
 174
 175 type type_store = interner::interner[raw_t];
 176
 177 type ty_param_substs_opt_and_ty = tup(option::t[vec[ty::t]], ty::t);
 178 type node_type_table =
 179     @mutable vec[mutable option::t[ty::ty_param_substs_opt_and_ty]];
 180
 181 fn populate_type_store(&ctxt cx) {
 182
 183     intern(cx, ty_nil, none[str]);
 184     intern(cx, ty_bool, none[str]);
 185     intern(cx, ty_int, none[str]);
 186     intern(cx, ty_float, none[str]);
 187     intern(cx, ty_uint, none[str]);
 188     intern(cx, ty_machine(ty_i8), none[str]);
 189     intern(cx, ty_machine(ty_i16), none[str]);
 190     intern(cx, ty_machine(ty_i32), none[str]);
 191     intern(cx, ty_machine(ty_i64), none[str]);
 192     intern(cx, ty_machine(ty_u8), none[str]);
 193     intern(cx, ty_machine(ty_u16), none[str]);
 194     intern(cx, ty_machine(ty_u32), none[str]);
 195     intern(cx, ty_machine(ty_u64), none[str]);
 196     intern(cx, ty_machine(ty_f32), none[str]);
 197     intern(cx, ty_machine(ty_f64), none[str]);
 198     intern(cx, ty_char, none[str]);
 199     intern(cx, ty_str, none[str]);
 200     intern(cx, ty_istr, none[str]);
 201     intern(cx, ty_task, none[str]);
 202     intern(cx, ty_native, none[str]);
 203     intern(cx, ty_type, none[str]);
 204     intern(cx, ty_bot, none[str]);
 205
 206     assert vec::len(cx.ts.vect) == idx_first_others;
 207 }
 208
 209 fn mk_rcache() -> creader_cache {
 210     fn hash_cache_entry(&tup(int,uint,uint) k) -> uint {
 211         ret (k._0 as uint) + k._1 + k._2;
 212     }
 213     fn eq_cache_entries(&tup(int,uint,uint) a,
 214                         &tup(int,uint,uint) b) -> bool {
 215         ret a._0 == b._0 &&
 216             a._1 == b._1 &&
 217             a._2 == b._2;
 218     }
 219     auto h = hash_cache_entry;
 220     auto e = eq_cache_entries;
 221     ret map::mk_hashmap[tup(int,uint,uint),t](h, e);
 222 }
 223
 224 fn mk_ctxt(session::session s, resolve::def_map dm) -> ctxt {
 225
 226     let vec[mutable option::t[ty::ty_param_substs_opt_and_ty]] ntt_sub =
 227         [mutable];
 228     let node_type_table ntt = @mutable ntt_sub;
 229
 230     auto tcache =
 231         common::new_def_hash[ty::ty_param_count_and_ty]();
 232
 233     auto items = common::new_def_hash[any_item]();
 234     auto ts = @interner::mk[raw_t](hash_raw_ty, eq_raw_ty);
 235
 236     auto cx =
 237         rec(ts = ts,
 238             sess = s,
 239             def_map = dm,
 240             node_types = ntt,
 241             items = items,
 242             tcache = tcache,
 243             rcache = mk_rcache(),
 244             short_names_cache =
 245             map::mk_hashmap[ty::t,str](ty::hash_ty, ty::eq_ty),
 246             ast_ty_to_ty_cache =
 247             map::mk_hashmap[@ast::ty,option::t[t]](ast::hash_ty, ast::eq_ty));
 248
 249     populate_type_store(cx);
 250     ret cx;
 251 }
 252
 253
 254 // Type constructors
 255
 256 fn mk_raw_ty(&ctxt cx, &sty st, &option::t[str] cname) -> raw_t {
 257     auto h = hash_type_info(st, cname);
 258
 259     let bool has_params = false;
 260     let bool has_vars = false;
 261
 262     fn derive_flags_t(&ctxt cx,
 263                       &mutable bool has_params,
 264                       &mutable bool has_vars,
 265                       &t tt) {
 266         auto rt = interner::get[raw_t](*cx.ts, tt);
 267         has_params = has_params || rt.has_params;
 268         has_vars = has_vars || rt.has_vars;
 269     }
 270
 271     fn derive_flags_mt(&ctxt cx,
 272                        &mutable bool has_params,
 273                        &mutable bool has_vars,
 274                        &mt m) {
 275         derive_flags_t(cx, has_params, has_vars, m.ty);
 276     }
 277
 278
 279     fn derive_flags_arg(&ctxt cx,
 280                         &mutable bool has_params,
 281                         &mutable bool has_vars,
 282                         &arg a) {
 283         derive_flags_t(cx, has_params, has_vars, a.ty);
 284     }
 285
 286     fn derive_flags_sig(&ctxt cx,
 287                         &mutable bool has_params,
 288                         &mutable bool has_vars,
 289                         &vec[arg] args,
 290                         &t tt) {
 291         for (arg a in args) {
 292             derive_flags_arg(cx, has_params, has_vars, a);
 293         }
 294         derive_flags_t(cx, has_params, has_vars, tt);
 295     }
 296
 297     alt (st) {
 298         case (ty_param(_)) {
 299             has_params = true;
 300         }
 301         case (ty_var(_)) { has_vars = true; }
 302         case (ty_tag(_, ?tys)) {
 303             for (t tt in tys) {
 304                 derive_flags_t(cx, has_params, has_vars, tt);
 305             }
 306         }
 307         case (ty_box(?m)) {
 308             derive_flags_mt(cx, has_params, has_vars, m);
 309         }
 310
 311         case (ty_vec(?m)) {
 312             derive_flags_mt(cx, has_params, has_vars, m);
 313         }
 314
 315         case (ty_port(?tt)) {
 316             derive_flags_t(cx, has_params, has_vars, tt);
 317         }
 318
 319         case (ty_chan(?tt)) {
 320             derive_flags_t(cx, has_params, has_vars, tt);
 321         }
 322
 323         case (ty_tup(?mts)) {
 324             for (mt m in mts) {
 325                 derive_flags_mt(cx, has_params, has_vars, m);
 326             }
 327         }
 328
 329         case (ty_rec(?flds)) {
 330             for (field f in flds) {
 331                 derive_flags_mt(cx, has_params, has_vars, f.mt);
 332             }
 333         }
 334
 335         case (ty_fn(_, ?args, ?tt, _, _)) {
 336             derive_flags_sig(cx, has_params, has_vars, args, tt);
 337         }
 338
 339         case (ty_native_fn(_, ?args, ?tt)) {
 340             derive_flags_sig(cx, has_params, has_vars, args, tt);
 341         }
 342
 343         case (ty_obj(?meths)) {
 344             for (method m in meths) {
 345                 derive_flags_sig(cx, has_params, has_vars, m.inputs,
 346                                  m.output);
 347             }
 348         }
 349         case (_) { }
 350     }
 351
 352     ret rec(struct=st, cname=cname, hash=h,
 353             has_params=has_params,
 354             has_vars=has_vars);
 355 }
 356
 357 fn intern(&ctxt cx, &sty st, &option::t[str] cname) {
 358     interner::intern[raw_t](*cx.ts, mk_raw_ty(cx, st, cname));
 359 }
 360
 361 fn gen_ty_full(&ctxt cx, &sty st, &option::t[str] cname) -> t {
 362     auto raw_type = mk_raw_ty(cx, st, cname);
 363     ret interner::intern[raw_t](*cx.ts, raw_type);
 364 }
 365
 366 // These are private constructors to this module. External users should always
 367 // use the mk_foo() functions below.
 368 fn gen_ty(&ctxt cx, &sty st) -> t {
 369     ret gen_ty_full(cx, st, none[str]);
 370 }
 371
 372 fn mk_nil(&ctxt cx) -> t          { ret idx_nil; }
 373 fn mk_bot(&ctxt cx) -> t          { ret idx_bot; }
 374 fn mk_bool(&ctxt cx) -> t         { ret idx_bool; }
 375 fn mk_int(&ctxt cx) -> t          { ret idx_int; }
 376 fn mk_float(&ctxt cx) -> t        { ret idx_float; }
 377 fn mk_uint(&ctxt cx) -> t         { ret idx_uint; }
 378
 379 fn mk_mach(&ctxt cx, &util::common::ty_mach tm) -> t {
 380     alt (tm) {
 381         case (ty_u8)  { ret idx_u8; }
 382         case (ty_u16) { ret idx_u16; }
 383         case (ty_u32) { ret idx_u32; }
 384         case (ty_u64) { ret idx_u64; }
 385
 386         case (ty_i8)  { ret idx_i8; }
 387         case (ty_i16) { ret idx_i16; }
 388         case (ty_i32) { ret idx_i32; }
 389         case (ty_i64) { ret idx_i64; }
 390
 391         case (ty_f32) { ret idx_f32; }
 392         case (ty_f64) { ret idx_f64; }
 393     }
 394 }
 395
 396 fn mk_char(&ctxt cx) -> t    { ret idx_char; }
 397 fn mk_str(&ctxt cx) -> t     { ret idx_str; }
 398 fn mk_istr(&ctxt cx) -> t    { ret idx_istr; }
 399
 400 fn mk_tag(&ctxt cx, &ast::def_id did, &vec[t] tys) -> t {
 401     ret gen_ty(cx, ty_tag(did, tys));
 402 }
 403
 404 fn mk_box(&ctxt cx, &mt tm) -> t {
 405     ret gen_ty(cx, ty_box(tm));
 406 }
 407
 408 fn mk_ptr(&ctxt cx, &mt tm) -> t {
 409     ret gen_ty(cx, ty_ptr(tm));
 410 }
 411
 412 fn mk_imm_box(&ctxt cx, &t ty) -> t {
 413     ret mk_box(cx, rec(ty=ty, mut=ast::imm));
 414 }
 415
 416 fn mk_vec(&ctxt cx, &mt tm) -> t  { ret gen_ty(cx, ty_vec(tm)); }
 417
 418 fn mk_ivec(&ctxt cx, &mt tm) -> t { ret gen_ty(cx, ty_ivec(tm)); }
 419
 420 fn mk_imm_vec(&ctxt cx, &t typ) -> t {
 421     ret gen_ty(cx, ty_vec(rec(ty=typ, mut=ast::imm)));
 422 }
 423
 424 fn mk_port(&ctxt cx, &t ty) -> t  { ret gen_ty(cx, ty_port(ty)); }
 425 fn mk_chan(&ctxt cx, &t ty) -> t  { ret gen_ty(cx, ty_chan(ty)); }
 426 fn mk_task(&ctxt cx) -> t        { ret gen_ty(cx, ty_task); }
 427
 428 fn mk_tup(&ctxt cx, &vec[mt] tms) -> t { ret gen_ty(cx, ty_tup(tms)); }
 429
 430 fn mk_imm_tup(&ctxt cx, &vec[t] tys) -> t {
 431     // TODO: map
 432     let vec[ty::mt] mts = [];
 433     for (t typ in tys) {
 434         mts += [rec(ty=typ, mut=ast::imm)];
 435     }
 436     ret mk_tup(cx, mts);
 437 }
 438
 439 fn mk_rec(&ctxt cx, &vec[field] fs) -> t { ret gen_ty(cx, ty_rec(fs)); }
 440
 441 fn mk_fn(&ctxt cx, &ast::proto proto, &vec[arg] args, &t ty,
 442          &controlflow cf, &vec[@ast::constr] constrs) -> t {
 443     ret gen_ty(cx, ty_fn(proto, args, ty, cf, constrs));
 444 }
 445
 446 fn mk_native_fn(&ctxt cx, &ast::native_abi abi, &vec[arg] args, &t ty) -> t {
 447     ret gen_ty(cx, ty_native_fn(abi, args, ty));
 448 }
 449
 450 fn mk_obj(&ctxt cx, &vec[method] meths) -> t {
 451     ret gen_ty(cx, ty_obj(meths));
 452 }
 453
 454 fn mk_var(&ctxt cx, int v) -> t {
 455     ret gen_ty(cx, ty_var(v));
 456 }
 457
 458 fn mk_param(&ctxt cx, uint n) -> t {
 459     ret gen_ty(cx, ty_param(n));
 460 }
 461
 462 fn mk_type(&ctxt cx) -> t    { ret idx_type; }
 463 fn mk_native(&ctxt cx) -> t  { ret idx_native; }
 464
 465
 466 // Returns the one-level-deep type structure of the given type.
 467 fn struct(&ctxt cx, &t typ) -> sty {
 468     ret interner::get[raw_t](*cx.ts, typ).struct;
 469 }
 470
 471 // Returns the canonical name of the given type.
 472 fn cname(&ctxt cx, &t typ) -> option::t[str] {
 473     ret interner::get[raw_t](*cx.ts, typ).cname;
 474 }
 475
 476
 477 // Stringification
 478
 479 fn path_to_str(&ast::path pth) -> str {
 480     auto result = str::connect(pth.node.idents,  "::");
 481     if (vec::len[@ast::ty](pth.node.types) > 0u) {
 482         fn f(&@ast::ty t) -> str {
 483             ret pretty::pprust::ty_to_str(*t);
 484         }
 485         result += "[";
 486         result += str::connect(vec::map(f, pth.node.types), ",");
 487         result += "]";
 488     }
 489     ret result;
 490 }
 491
 492 // Type folds
 493
 494 type ty_walk = fn(t);
 495
 496 fn walk_ty(&ctxt cx, ty_walk walker, t ty) {
 497     alt (struct(cx, ty)) {
 498         case (ty_nil)           { /* no-op */ }
 499         case (ty_bot)           { /* no-op */ }
 500         case (ty_bool)          { /* no-op */ }
 501         case (ty_int)           { /* no-op */ }
 502         case (ty_uint)          { /* no-op */ }
 503         case (ty_float)         { /* no-op */ }
 504         case (ty_machine(_))    { /* no-op */ }
 505         case (ty_char)          { /* no-op */ }
 506         case (ty_str)           { /* no-op */ }
 507         case (ty_istr)          { /* no-op */ }
 508         case (ty_type)          { /* no-op */ }
 509         case (ty_native)        { /* no-op */ }
 510         case (ty_box(?tm))      { walk_ty(cx, walker, tm.ty); }
 511         case (ty_vec(?tm))      { walk_ty(cx, walker, tm.ty); }
 512         case (ty_ivec(?tm))     { walk_ty(cx, walker, tm.ty); }
 513         case (ty_port(?subty))  { walk_ty(cx, walker, subty); }
 514         case (ty_chan(?subty))  { walk_ty(cx, walker, subty); }
 515         case (ty_tag(?tid, ?subtys)) {
 516             for (t subty in subtys) {
 517                 walk_ty(cx, walker, subty);
 518             }
 519         }
 520         case (ty_tup(?mts)) {
 521             for (mt tm in mts) {
 522                 walk_ty(cx, walker, tm.ty);
 523             }
 524         }
 525         case (ty_rec(?fields)) {
 526             for (field fl in fields) {
 527                 walk_ty(cx, walker, fl.mt.ty);
 528             }
 529         }
 530         case (ty_fn(?proto, ?args, ?ret_ty, _, _)) {
 531             for (arg a in args) {
 532                 walk_ty(cx, walker, a.ty);
 533             }
 534             walk_ty(cx, walker, ret_ty);
 535         }
 536         case (ty_native_fn(?abi, ?args, ?ret_ty)) {
 537             for (arg a in args) {
 538                 walk_ty(cx, walker, a.ty);
 539             }
 540             walk_ty(cx, walker, ret_ty);
 541         }
 542         case (ty_obj(?methods)) {
 543             let vec[method] new_methods = [];
 544             for (method m in methods) {
 545                 for (arg a in m.inputs) {
 546                     walk_ty(cx, walker, a.ty);
 547                 }
 548                 walk_ty(cx, walker, m.output);
 549             }
 550         }
 551         case (ty_var(_))         { /* no-op */ }
 552         case (ty_param(_))       { /* no-op */ }
 553     }
 554
 555     walker(ty);
 556 }
 557
 558 tag fold_mode {
 559     fm_var(fn(int)->t);
 560     fm_param(fn(uint)->t);
 561     fm_general(fn(t)->t);
 562 }
 563
 564 fn fold_ty(&ctxt cx, fold_mode fld, t ty_0) -> t {
 565     auto ty = ty_0;
 566
 567     // Fast paths.
 568     alt (fld) {
 569         case (fm_var(_)) { if (!type_contains_vars(cx, ty)) { ret ty; } }
 570         case (fm_param(_)) { if (!type_contains_params(cx, ty)) { ret ty; } }
 571         case (fm_general(_)) { /* no fast path */ }
 572     }
 573
 574     alt (struct(cx, ty)) {
 575         case (ty_nil)           { /* no-op */ }
 576         case (ty_bot)           { /* no-op */ }
 577         case (ty_bool)          { /* no-op */ }
 578         case (ty_int)           { /* no-op */ }
 579         case (ty_uint)          { /* no-op */ }
 580         case (ty_float)         { /* no-op */ }
 581         case (ty_machine(_))    { /* no-op */ }
 582         case (ty_char)          { /* no-op */ }
 583         case (ty_str)           { /* no-op */ }
 584         case (ty_type)          { /* no-op */ }
 585         case (ty_native)        { /* no-op */ }
 586         case (ty_task)          { /* no-op */ }
 587         case (ty_box(?tm)) {
 588             ty = copy_cname(cx, mk_box(cx, rec(ty=fold_ty(cx, fld, tm.ty),
 589                                                mut=tm.mut)), ty);
 590         }
 591         case (ty_ptr(?tm)) {
 592             ty = copy_cname(cx, mk_ptr(cx, rec(ty=fold_ty(cx, fld, tm.ty),
 593                                                mut=tm.mut)), ty);
 594         }
 595         case (ty_vec(?tm)) {
 596             ty = copy_cname(cx, mk_vec(cx, rec(ty=fold_ty(cx, fld, tm.ty),
 597                                                           mut=tm.mut)), ty);
 598         }
 599         case (ty_port(?subty)) {
 600             ty = copy_cname(cx, mk_port(cx, fold_ty(cx, fld, subty)), ty);
 601         }
 602         case (ty_chan(?subty)) {
 603             ty = copy_cname(cx, mk_chan(cx, fold_ty(cx, fld, subty)), ty);
 604         }
 605         case (ty_tag(?tid, ?subtys)) {
 606             let vec[t] new_subtys = [];
 607             for (t subty in subtys) {
 608                 new_subtys += [fold_ty(cx, fld, subty)];
 609             }
 610             ty = copy_cname(cx, mk_tag(cx, tid, new_subtys), ty);
 611         }
 612         case (ty_tup(?mts)) {
 613             let vec[mt] new_mts = [];
 614             for (mt tm in mts) {
 615                 auto new_subty = fold_ty(cx, fld, tm.ty);
 616                 new_mts += [rec(ty=new_subty, mut=tm.mut)];
 617             }
 618             ty = copy_cname(cx, mk_tup(cx, new_mts), ty);
 619         }
 620         case (ty_rec(?fields)) {
 621             let vec[field] new_fields = [];
 622             for (field fl in fields) {
 623                 auto new_ty = fold_ty(cx, fld, fl.mt.ty);
 624                 auto new_mt = rec(ty=new_ty, mut=fl.mt.mut);
 625                 new_fields += [rec(ident=fl.ident, mt=new_mt)];
 626             }
 627             ty = copy_cname(cx, mk_rec(cx, new_fields), ty);
 628         }
 629         case (ty_fn(?proto, ?args, ?ret_ty, ?cf, ?constrs)) {
 630             let vec[arg] new_args = [];
 631             for (arg a in args) {
 632                 auto new_ty = fold_ty(cx, fld, a.ty);
 633                 new_args += [rec(mode=a.mode, ty=new_ty)];
 634             }
 635             ty = copy_cname(cx, mk_fn(cx, proto, new_args,
 636                                   fold_ty(cx, fld, ret_ty), cf, constrs), ty);
 637         }
 638         case (ty_native_fn(?abi, ?args, ?ret_ty)) {
 639             let vec[arg] new_args = [];
 640             for (arg a in args) {
 641                 auto new_ty = fold_ty(cx, fld, a.ty);
 642                 new_args += [rec(mode=a.mode, ty=new_ty)];
 643             }
 644             ty = copy_cname(cx, mk_native_fn(cx, abi, new_args,
 645                                              fold_ty(cx, fld, ret_ty)), ty);
 646         }
 647         case (ty_obj(?methods)) {
 648             let vec[method] new_methods = [];
 649             for (method m in methods) {
 650                 let vec[arg] new_args = [];
 651                 for (arg a in m.inputs) {
 652                     new_args += [rec(mode=a.mode,
 653                                         ty=fold_ty(cx, fld, a.ty))];
 654                 }
 655                 new_methods += [rec(proto=m.proto, ident=m.ident,
 656                                inputs=new_args,
 657                                output=fold_ty(cx, fld, m.output),
 658                                cf=m.cf, constrs=m.constrs)];
 659             }
 660             ty = copy_cname(cx, mk_obj(cx, new_methods), ty);
 661         }
 662         case (ty_var(?id)) {
 663             alt (fld) {
 664                 case (fm_var(?folder)) { ty = folder(id); }
 665                 case (_) { /* no-op */ }
 666             }
 667         }
 668         case (ty_param(?id)) {
 669             alt (fld) {
 670                 case (fm_param(?folder)) { ty = folder(id); }
 671                 case (_) { /* no-op */ }
 672             }
 673         }
 674     }
 675
 676     // If this is a general type fold, then we need to run it now.
 677     alt (fld) {
 678         case (fm_general(?folder)) { ret folder(ty); }
 679         case (_) { ret ty; }
 680     }
 681 }
 682
 683 // Type utilities
 684
 685 fn rename(&ctxt cx, t typ, str new_cname) -> t {
 686     ret gen_ty_full(cx, struct(cx, typ), some[str](new_cname));
 687 }
 688
 689 // Returns a type with the structural part taken from `struct_ty` and the
 690 // canonical name from `cname_ty`.
 691 fn copy_cname(&ctxt cx, t struct_ty, t cname_ty) -> t {
 692     ret gen_ty_full(cx, struct(cx, struct_ty), cname(cx, cname_ty));
 693 }
 694
 695 fn type_is_nil(&ctxt cx, &t ty) -> bool {
 696     alt (struct(cx, ty)) {
 697         case (ty_nil) { ret true; }
 698         case (_) { ret false; }
 699     }
 700 }
 701
 702 fn type_is_bot(&ctxt cx, &t ty) -> bool {
 703     alt (struct(cx, ty)) {
 704         case (ty_bot) { ret true; }
 705         case (_) { ret false; }
 706     }
 707 }
 708
 709 fn type_is_bool(&ctxt cx, &t ty) -> bool {
 710     alt (struct(cx, ty)) {
 711         case (ty_bool) { ret true; }
 712         case (_) { ret false; }
 713     }
 714 }
 715
 716
 717 fn type_is_structural(&ctxt cx, &t ty) -> bool {
 718     alt (struct(cx, ty)) {
 719         case (ty_tup(_))    { ret true; }
 720         case (ty_rec(_))    { ret true; }
 721         case (ty_tag(_,_))  { ret true; }
 722         case (ty_fn(_,_,_,_,_)) { ret true; }
 723         case (ty_obj(_))    { ret true; }
 724         case (_)            { ret false; }
 725     }
 726 }
 727
 728 fn type_is_sequence(&ctxt cx, &t ty) -> bool {
 729     alt (struct(cx, ty)) {
 730         case (ty_str)    { ret true; }
 731         case (ty_vec(_))    { ret true; }
 732         case (_)            { ret false; }
 733     }
 734 }
 735
 736 fn sequence_element_type(&ctxt cx, &t ty) -> t {
 737     alt (struct(cx, ty)) {
 738         case (ty_str)      { ret mk_mach(cx, common::ty_u8); }
 739         case (ty_vec(?mt)) { ret mt.ty; }
 740         // NB: This is not exhaustive.
 741     }
 742
 743     cx.sess.bug("sequence_element_type called on non-sequence value");
 744 }
 745
 746 fn type_is_tup_like(&ctxt cx, &t ty) -> bool {
 747     alt (struct(cx, ty)) {
 748         case (ty_box(_))    { ret true; }
 749         case (ty_tup(_))    { ret true; }
 750         case (ty_rec(_))    { ret true; }
 751         case (ty_tag(_,_))  { ret true; }
 752         case (_)            { ret false; }
 753     }
 754 }
 755
 756 fn get_element_type(&ctxt cx, &t ty, uint i) -> t {
 757     assert (type_is_tup_like(cx, ty));
 758     alt (struct(cx, ty)) {
 759         case (ty_tup(?mts)) {
 760             ret mts.(i).ty;
 761         }
 762         case (ty_rec(?flds)) {
 763             ret flds.(i).mt.ty;
 764         }
 765         // NB: This is not exhaustive -- struct(cx, ty) could be a box or a
 766         // tag.
 767     }
 768
 769     cx.sess.bug("get_element_type called on a value other than a "
 770                 + "tuple or record");
 771 }
 772
 773 fn type_is_box(&ctxt cx, &t ty) -> bool {
 774     alt (struct(cx, ty)) {
 775         case (ty_box(_)) { ret true; }
 776         case (_) { ret false; }
 777     }
 778 }
 779
 780 fn type_is_boxed(&ctxt cx, &t ty) -> bool {
 781     alt (struct(cx, ty)) {
 782         case (ty_str) { ret true; }
 783         case (ty_vec(_)) { ret true; }
 784         case (ty_box(_)) { ret true; }
 785         case (ty_port(_)) { ret true; }
 786         case (ty_chan(_)) { ret true; }
 787         case (ty_task) { ret true; }
 788         case (_) { ret false; }
 789     }
 790 }
 791
 792 fn type_is_scalar(&ctxt cx, &t ty) -> bool {
 793     alt (struct(cx, ty)) {
 794         case (ty_nil) { ret true; }
 795         case (ty_bool) { ret true; }
 796         case (ty_int) { ret true; }
 797         case (ty_float) { ret true; }
 798         case (ty_uint) { ret true; }
 799         case (ty_machine(_)) { ret true; }
 800         case (ty_char) { ret true; }
 801         case (ty_type) { ret true; }
 802         case (ty_native) { ret true; }
 803         case (ty_ptr(_)) { ret true; }
 804         case (_) { ret false; }
 805     }
 806 }
 807
 808 fn type_has_pointers(&ctxt cx, &t ty) -> bool {
 809     alt (struct(cx, ty)) {
 810         // scalar types
 811         case (ty_nil) { ret false; }
 812         case (ty_bot) { ret false; }
 813         case (ty_bool) { ret false; }
 814         case (ty_int) { ret false; }
 815         case (ty_float) { ret false; }
 816         case (ty_uint) { ret false; }
 817         case (ty_machine(_)) { ret false; }
 818         case (ty_char) { ret false; }
 819         case (ty_type) { ret false; }
 820         case (ty_native) { ret false; }
 821
 822         case (ty_tup(?elts))    {
 823             for (mt m in elts) {
 824                 if (type_has_pointers(cx, m.ty)) { ret true; }
 825             }
 826             ret false;
 827         }
 828         case (ty_rec(?flds)) {
 829             for (field f in flds) {
 830                 if (type_has_pointers(cx, f.mt.ty)) { ret true; }
 831             }
 832             ret false;
 833         }
 834
 835         case (ty_tag(?did,?tps))  {
 836             auto variants = tag_variants(cx, did);
 837             for (variant_info variant in variants) {
 838                 auto tup_ty = mk_imm_tup(cx, variant.args);
 839                 // Perform any type parameter substitutions.
 840                 tup_ty = substitute_type_params(cx, tps, tup_ty);
 841                 if (type_has_pointers(cx, tup_ty)) { ret true; }
 842             }
 843             ret false;
 844         }
 845         case (_) { ret true; }
 846     }
 847 }
 848
 849
 850 // FIXME: should we just return true for native types in
 851 // type_is_scalar?
 852 fn type_is_native(&ctxt cx, &t ty) -> bool {
 853     alt (struct(cx, ty)) {
 854         case (ty_native) { ret true; }
 855         case (_) { ret false; }
 856     }
 857 }
 858
 859 fn type_has_dynamic_size(&ctxt cx, &t ty) -> bool {
 860     alt (struct(cx, ty)) {
 861         case (ty_tup(?mts)) {
 862             auto i = 0u;
 863             while (i < vec::len[mt](mts)) {
 864                 if (type_has_dynamic_size(cx, mts.(i).ty)) { ret true; }
 865                 i += 1u;
 866             }
 867         }
 868         case (ty_rec(?fields)) {
 869             auto i = 0u;
 870             while (i < vec::len[field](fields)) {
 871                 if (type_has_dynamic_size(cx, fields.(i).mt.ty)) {
 872                     ret true;
 873                 }
 874                 i += 1u;
 875             }
 876         }
 877         case (ty_tag(_, ?subtys)) {
 878             auto i = 0u;
 879             while (i < vec::len[t](subtys)) {
 880                 if (type_has_dynamic_size(cx, subtys.(i))) { ret true; }
 881                 i += 1u;
 882             }
 883         }
 884         case (ty_param(_)) { ret true; }
 885         case (_) { /* fall through */ }
 886     }
 887     ret false;
 888 }
 889
 890 fn type_is_integral(&ctxt cx, &t ty) -> bool {
 891     alt (struct(cx, ty)) {
 892         case (ty_int) { ret true; }
 893         case (ty_uint) { ret true; }
 894         case (ty_machine(?m)) {
 895             alt (m) {
 896                 case (common::ty_i8) { ret true; }
 897                 case (common::ty_i16) { ret true; }
 898                 case (common::ty_i32) { ret true; }
 899                 case (common::ty_i64) { ret true; }
 900
 901                 case (common::ty_u8) { ret true; }
 902                 case (common::ty_u16) { ret true; }
 903                 case (common::ty_u32) { ret true; }
 904                 case (common::ty_u64) { ret true; }
 905                 case (_) { ret false; }
 906             }
 907         }
 908         case (ty_char) { ret true; }
 909         case (_) { ret false; }
 910     }
 911 }
 912
 913 fn type_is_fp(&ctxt cx, &t ty) -> bool {
 914     alt (struct(cx, ty)) {
 915         case (ty_machine(?tm)) {
 916             alt (tm) {
 917                 case (common::ty_f32) { ret true; }
 918                 case (common::ty_f64) { ret true; }
 919                 case (_) { ret false; }
 920             }
 921         }
 922         case (ty_float) {
 923             ret true;
 924         }
 925         case (_) { ret false; }
 926     }
 927 }
 928
 929 fn type_is_signed(&ctxt cx, &t ty) -> bool {
 930     alt (struct(cx, ty)) {
 931         case (ty_int) { ret true; }
 932         case (ty_machine(?tm)) {
 933             alt (tm) {
 934                 case (common::ty_i8) { ret true; }
 935                 case (common::ty_i16) { ret true; }
 936                 case (common::ty_i32) { ret true; }
 937                 case (common::ty_i64) { ret true; }
 938                 case (_) { ret false; }
 939             }
 940         }
 941         case (_) { ret false; }
 942     }
 943 }
 944
 945 fn type_param(&ctxt cx, &t ty) -> option::t[uint] {
 946     alt (struct(cx, ty)) {
 947         case (ty_param(?id)) { ret some[uint](id); }
 948         case (_)             { /* fall through */  }
 949     }
 950     ret none[uint];
 951 }
 952
 953 fn def_to_str(&ast::def_id did) -> str {
 954     ret #fmt("%d:%d", did._0, did._1);
 955 }
 956
 957
 958 // Type hashing. This function is private to this module (and slow); external
 959 // users should use `hash_ty()` instead.
 960 fn hash_type_structure(&sty st) -> uint {
 961     fn hash_uint(uint id, uint n) -> uint {
 962         auto h = id;
 963         h += h << 5u + n;
 964         ret h;
 965     }
 966
 967     fn hash_def(uint id, ast::def_id did) -> uint {
 968         auto h = id;
 969         h += h << 5u + (did._0 as uint);
 970         h += h << 5u + (did._1 as uint);
 971         ret h;
 972     }
 973
 974     fn hash_subty(uint id, &t subty) -> uint {
 975         auto h = id;
 976         h += h << 5u + hash_ty(subty);
 977         ret h;
 978     }
 979
 980     fn hash_fn(uint id, &vec[arg] args, &t rty) -> uint {
 981         auto h = id;
 982         for (arg a in args) {
 983             h += h << 5u + hash_ty(a.ty);
 984         }
 985         h += h << 5u + hash_ty(rty);
 986         ret h;
 987     }
 988
 989     alt (st) {
 990         case (ty_nil) { ret 0u; }
 991         case (ty_bool) { ret 1u; }
 992         case (ty_int) { ret 2u; }
 993         case (ty_float) { ret 3u; }
 994         case (ty_uint) { ret 4u; }
 995         case (ty_machine(?tm)) {
 996             alt (tm) {
 997                 case (common::ty_i8) { ret 5u; }
 998                 case (common::ty_i16) { ret 6u; }
 999                 case (common::ty_i32) { ret 7u; }
1000                 case (common::ty_i64) { ret 8u; }
1001
1002                 case (common::ty_u8) { ret 9u; }
1003                 case (common::ty_u16) { ret 10u; }
1004                 case (common::ty_u32) { ret 11u; }
1005                 case (common::ty_u64) { ret 12u; }
1006
1007                 case (common::ty_f32) { ret 13u; }
1008                 case (common::ty_f64) { ret 14u; }
1009             }
1010         }
1011         case (ty_char) { ret 15u; }
1012         case (ty_str) { ret 16u; }
1013         case (ty_istr) { ret 17u; }
1014         case (ty_tag(?did, ?tys)) {
1015             auto h = hash_def(18u, did);
1016             for (t typ in tys) {
1017                 h += h << 5u + hash_ty(typ);
1018             }
1019             ret h;
1020         }
1021         case (ty_box(?mt)) { ret hash_subty(19u, mt.ty); }
1022         case (ty_vec(?mt)) { ret hash_subty(20u, mt.ty); }
1023         case (ty_ivec(?mt)) { ret hash_subty(21u, mt.ty); }
1024         case (ty_port(?typ)) { ret hash_subty(22u, typ); }
1025         case (ty_chan(?typ)) { ret hash_subty(23u, typ); }
1026         case (ty_task) { ret 24u; }
1027         case (ty_tup(?mts)) {
1028             auto h = 25u;
1029             for (mt tm in mts) {
1030                 h += h << 5u + hash_ty(tm.ty);
1031             }
1032             ret h;
1033         }
1034         case (ty_rec(?fields)) {
1035             auto h = 26u;
1036             for (field f in fields) {
1037                 h += h << 5u + hash_ty(f.mt.ty);
1038             }
1039             ret h;
1040         }
1041         // ???
1042         case (ty_fn(_, ?args, ?rty, _, _)) { ret hash_fn(27u, args, rty); }
1043         case (ty_native_fn(_, ?args, ?rty)) { ret hash_fn(28u, args, rty); }
1044         case (ty_obj(?methods)) {
1045             auto h = 29u;
1046             for (method m in methods) {
1047                 h += h << 5u + str::hash(m.ident);
1048             }
1049             ret h;
1050         }
1051         case (ty_var(?v)) { ret hash_uint(30u, v as uint); }
1052         case (ty_param(?pid)) { ret hash_uint(31u, pid); }
1053         case (ty_type) { ret 32u; }
1054         case (ty_native) { ret 33u; }
1055         case (ty_bot) { ret 34u; }
1056         case (ty_ptr(?mt)) { ret hash_subty(35u, mt.ty); }
1057     }
1058 }
1059
1060 fn hash_type_info(&sty st, &option::t[str] cname_opt) -> uint {
1061     auto h = hash_type_structure(st);
1062     alt (cname_opt) {
1063         case (none) { /* no-op */ }
1064         case (some(?s)) { h += h << 5u + str::hash(s); }
1065     }
1066     ret h;
1067 }
1068
1069 fn hash_raw_ty(&raw_t rt) -> uint { ret rt.hash; }
1070
1071 fn hash_ty(&t typ) -> uint { ret typ; }
1072
1073
1074 // Type equality. This function is private to this module (and slow); external
1075 // users should use `eq_ty()` instead.
1076
1077 fn arg_eq(@ast::constr_arg a, @ast::constr_arg b) -> bool {
1078     alt (a.node) {
1079         case (ast::carg_base) {
1080             alt (b.node) {
1081                 case (ast::carg_base) {
1082                     ret true;
1083                 }
1084                 case (_) {
1085                     ret false;
1086                 }
1087             }
1088         }
1089         case (ast::carg_ident(?s)) {
1090             alt (b.node) {
1091                 case (ast::carg_ident(?t)) {
1092                     ret (s == t);
1093                 }
1094                 case (_) {
1095                     ret false;
1096                 }
1097             }
1098         }
1099         case (ast::carg_lit(?l)) {
1100             alt (b.node) {
1101                 case (ast::carg_lit(?m)) {
1102                     ret util::common::lit_eq(l, m);
1103                 }
1104                 case (_) {
1105                     ret false;
1106                 }
1107             }
1108         }
1109     }
1110 }
1111 fn args_eq(vec[@ast::constr_arg] a, vec[@ast::constr_arg] b) -> bool {
1112     let uint i = 0u;
1113     for (@ast::constr_arg arg in a) {
1114         if (!arg_eq(arg, b.(i))) {
1115             ret false;
1116         }
1117         i += 1u;
1118     }
1119     ret true;
1120 }
1121
1122
1123 fn constr_eq(&@ast::constr c, &@ast::constr d) -> bool {
1124     ret path_to_str(c.node.path) == path_to_str(d.node.path) // FIXME: hack
1125         && args_eq(c.node.args, d.node.args);
1126 }
1127
1128 fn constrs_eq(&vec[@ast::constr] cs, &vec[@ast::constr] ds) -> bool {
1129     if (vec::len(cs) != vec::len(ds)) {
1130         ret false;
1131     }
1132     auto i = 0;
1133     for (@ast::constr c in cs) {
1134         if (!constr_eq(c, ds.(i))) {
1135             ret false;
1136         }
1137         i += 1;
1138     }
1139     ret true;
1140 }
1141
1142 fn equal_type_structures(&sty a, &sty b) -> bool {
1143     fn equal_mt(&mt a, &mt b) -> bool {
1144         ret a.mut == b.mut && eq_ty(a.ty, b.ty);
1145     }
1146
1147     fn equal_fn(&vec[arg] args_a, &t rty_a,
1148                 &vec[arg] args_b, &t rty_b) -> bool {
1149         if (!eq_ty(rty_a, rty_b)) { ret false; }
1150
1151         auto len = vec::len[arg](args_a);
1152         if (len != vec::len[arg](args_b)) { ret false; }
1153
1154         auto i = 0u;
1155         while (i < len) {
1156             auto arg_a = args_a.(i); auto arg_b = args_b.(i);
1157             if (arg_a.mode != arg_b.mode) { ret false; }
1158             if (!eq_ty(arg_a.ty, arg_b.ty)) { ret false; }
1159             i += 1u;
1160         }
1161         ret true;
1162     }
1163
1164     fn equal_def(&ast::def_id did_a, &ast::def_id did_b) -> bool {
1165         ret did_a._0 == did_b._0 && did_a._1 == did_b._1;
1166     }
1167
1168     alt (a) {
1169         case (ty_nil) {
1170             alt (b) {
1171                 case (ty_nil) { ret true; }
1172                 case (_) { ret false; }
1173             }
1174         }
1175         case (ty_bot) {
1176             alt(b) {
1177                 case (ty_bot) { ret true; }
1178                 case (_)      { ret false; }
1179             }
1180         }
1181         case (ty_bool) {
1182             alt (b) {
1183                 case (ty_bool) { ret true; }
1184                 case (_) { ret false; }
1185             }
1186         }
1187         case (ty_int) {
1188             alt (b) {
1189                 case (ty_int) { ret true; }
1190                 case (_) { ret false; }
1191             }
1192         }
1193         case (ty_float) {
1194             alt (b) {
1195                 case (ty_float) { ret true; }
1196                 case (_) { ret false; }
1197             }
1198         }
1199         case (ty_uint) {
1200             alt (b) {
1201                 case (ty_uint) { ret true; }
1202                 case (_) { ret false; }
1203             }
1204         }
1205         case (ty_machine(?tm_a)) {
1206             alt (b) {
1207                 case (ty_machine(?tm_b)) {
1208                     ret hash_type_structure(a) == hash_type_structure(b);
1209                 }
1210                 case (_) { ret false; }
1211             }
1212         }
1213         case (ty_char) {
1214             alt (b) {
1215                 case (ty_char) { ret true; }
1216                 case (_) { ret false; }
1217             }
1218         }
1219         case (ty_str) {
1220             alt (b) {
1221                 case (ty_str) { ret true; }
1222                 case (_) { ret false; }
1223             }
1224         }
1225         case (ty_tag(?id_a, ?tys_a)) {
1226             alt (b) {
1227                 case (ty_tag(?id_b, ?tys_b)) {
1228                     if (!equal_def(id_a, id_b)) { ret false; }
1229
1230                     auto len = vec::len[t](tys_a);
1231                     if (len != vec::len[t](tys_b)) { ret false; }
1232                     auto i = 0u;
1233                     while (i < len) {
1234                         if (!eq_ty(tys_a.(i), tys_b.(i))) { ret false; }
1235                         i += 1u;
1236                     }
1237                     ret true;
1238                 }
1239                 case (_) { ret false; }
1240             }
1241         }
1242         case (ty_box(?mt_a)) {
1243             alt (b) {
1244                 case (ty_box(?mt_b)) { ret equal_mt(mt_a, mt_b); }
1245                 case (_) { ret false; }
1246             }
1247         }
1248         case (ty_vec(?mt_a)) {
1249             alt (b) {
1250                 case (ty_vec(?mt_b)) { ret equal_mt(mt_a, mt_b); }
1251                 case (_) { ret false; }
1252             }
1253         }
1254         case (ty_ptr(?mt_a)) {
1255             alt (b) {
1256                 case (ty_ptr(?mt_b)) { ret equal_mt(mt_a, mt_b); }
1257                 case (_) { ret false; }
1258             }
1259         }
1260         case (ty_port(?t_a)) {
1261             alt (b) {
1262                 case (ty_port(?t_b)) { ret eq_ty(t_a, t_b); }
1263                 case (_) { ret false; }
1264             }
1265         }
1266         case (ty_chan(?t_a)) {
1267             alt (b) {
1268                 case (ty_chan(?t_b)) { ret eq_ty(t_a, t_b); }
1269                 case (_) { ret false; }
1270             }
1271         }
1272         case (ty_task) {
1273             alt (b) {
1274                 case (ty_task) { ret true; }
1275                 case (_) { ret false; }
1276             }
1277         }
1278         case (ty_tup(?mts_a)) {
1279             alt (b) {
1280                 case (ty_tup(?mts_b)) {
1281                     auto len = vec::len[mt](mts_a);
1282                     if (len != vec::len[mt](mts_b)) { ret false; }
1283                     auto i = 0u;
1284                     while (i < len) {
1285                         if (!equal_mt(mts_a.(i), mts_b.(i))) { ret false; }
1286                         i += 1u;
1287                     }
1288                     ret true;
1289                 }
1290                 case (_) { ret false; }
1291             }
1292         }
1293         case (ty_rec(?flds_a)) {
1294             alt (b) {
1295                 case (ty_rec(?flds_b)) {
1296                     auto len = vec::len[field](flds_a);
1297                     if (len != vec::len[field](flds_b)) { ret false; }
1298                     auto i = 0u;
1299                     while (i < len) {
1300                         auto fld_a = flds_a.(i); auto fld_b = flds_b.(i);
1301                         if (!str::eq(fld_a.ident, fld_b.ident) ||
1302                                 !equal_mt(fld_a.mt, fld_b.mt)) {
1303                             ret false;
1304                         }
1305                         i += 1u;
1306                     }
1307                     ret true;
1308                 }
1309                 case (_) { ret false; }
1310             }
1311         }
1312         case (ty_fn(?p_a, ?args_a, ?rty_a, ?cf_a, ?constrs_a)) {
1313             alt (b) {
1314                 case (ty_fn(?p_b, ?args_b, ?rty_b, ?cf_b, ?constrs_b)) {
1315                     ret p_a == p_b &&
1316                         cf_a == cf_b &&
1317                         constrs_eq(constrs_a, constrs_b) &&
1318                         equal_fn(args_a, rty_a, args_b, rty_b);
1319                 }
1320                 case (_) { ret false; }
1321             }
1322         }
1323         case (ty_native_fn(?abi_a, ?args_a, ?rty_a)) {
1324             alt (b) {
1325                 case (ty_native_fn(?abi_b, ?args_b, ?rty_b)) {
1326                     ret abi_a == abi_b &&
1327                         equal_fn(args_a, rty_a, args_b, rty_b);
1328                 }
1329                 case (_) { ret false; }
1330             }
1331         }
1332         case (ty_obj(?methods_a)) {
1333             alt (b) {
1334                 case (ty_obj(?methods_b)) {
1335                     auto len = vec::len[method](methods_a);
1336                     if (len != vec::len[method](methods_b)) { ret false; }
1337                     auto i = 0u;
1338                     while (i < len) {
1339                         auto m_a = methods_a.(i); auto m_b = methods_b.(i);
1340                         if (m_a.proto != m_b.proto ||
1341                                 !str::eq(m_a.ident, m_b.ident) ||
1342                                 !equal_fn(m_a.inputs, m_a.output,
1343                                           m_b.inputs, m_b.output)) {
1344                             ret false;
1345                         }
1346                         i += 1u;
1347                     }
1348                     ret true;
1349                 }
1350                 case (_) { ret false; }
1351             }
1352         }
1353         case (ty_var(?v_a)) {
1354             alt (b) {
1355                 case (ty_var(?v_b)) { ret v_a == v_b; }
1356                 case (_) { ret false; }
1357             }
1358         }
1359         case (ty_param(?pid_a)) {
1360             alt (b) {
1361                 case (ty_param(?pid_b)) { ret pid_a == pid_b; }
1362                 case (_) { ret false; }
1363             }
1364         }
1365         case (ty_type) {
1366             alt (b) {
1367                 case (ty_type) { ret true; }
1368                 case (_) { ret false; }
1369             }
1370         }
1371         case (ty_native) {
1372             alt (b) {
1373                 case (ty_native) { ret true; }
1374                 case (_) { ret false; }
1375             }
1376         }
1377     }
1378 }
1379
1380 // An expensive type equality function. This function is private to this
1381 // module.
1382 //
1383 // FIXME: Use structural comparison, but this loops forever and segfaults.
1384 fn eq_raw_ty(&raw_t a, &raw_t b) -> bool {
1385     // Check hashes (fast path).
1386     if (a.hash != b.hash) {
1387         ret false;
1388     }
1389
1390     // Check canonical names.
1391     alt (a.cname) {
1392         case (none) {
1393             alt (b.cname) {
1394                 case (none[str]) { /* ok */ }
1395                 case (_) { ret false; }
1396             }
1397         }
1398         case (some(?s_a)) {
1399             alt (b.cname) {
1400                 case (some(?s_b)) {
1401                     if (!str::eq(s_a, s_b)) { ret false; }
1402                 }
1403                 case (_) { ret false; }
1404             }
1405         }
1406     }
1407
1408     // Check structures.
1409     ret equal_type_structures(a.struct, b.struct);
1410 }
1411
1412 // This is the equality function the public should use. It works as long as
1413 // the types are interned.
1414 fn eq_ty(&t a, &t b) -> bool { ret a == b; }
1415
1416
1417 // Type lookups
1418
1419 fn ann_to_ty_param_substs_opt_and_ty(&ctxt cx, &ast::ann ann)
1420     -> ty_param_substs_opt_and_ty {
1421
1422     // Pull out the node type table.
1423     alt ({cx.node_types.(ann.id)}) {
1424         case (none) {
1425             cx.sess.bug("ann_to_ty_param_substs_opt_and_ty() called on an " +
1426                         "untyped node");
1427         }
1428         case (some(?tpot)) { ret tpot; }
1429     }
1430 }
1431
1432 fn ann_to_type(&ctxt cx, &ast::ann ann) -> t {
1433     ret ann_to_ty_param_substs_opt_and_ty(cx, ann)._1;
1434 }
1435
1436 fn ann_to_type_params(&ctxt cx, &ast::ann ann) -> vec[t] {
1437     alt (ann_to_ty_param_substs_opt_and_ty(cx, ann)._0) {
1438         case (none) {
1439             let vec[t] result = [];
1440             ret result;
1441         }
1442         case (some(?tps)) { ret tps; }
1443     }
1444 }
1445
1446 fn ann_has_type_params(&ctxt cx, &ast::ann ann) -> bool {
1447     auto tpt = ann_to_ty_param_substs_opt_and_ty(cx, ann);
1448     ret !option::is_none[vec[t]](tpt._0);
1449 }
1450
1451
1452 // Returns a type with type parameter substitutions performed if applicable.
1453 fn ty_param_substs_opt_and_ty_to_monotype(&ctxt cx,
1454                                           &ty_param_substs_opt_and_ty tpot)
1455         -> t {
1456     alt (tpot._0) {
1457         case (none) { ret tpot._1; }
1458         case (some(?tps)) { ret substitute_type_params(cx, tps, tpot._1); }
1459     }
1460 }
1461
1462 // Returns the type of an annotation, with type parameter substitutions
1463 // performed if applicable.
1464 fn ann_to_monotype(&ctxt cx, ast::ann a) -> t {
1465     auto tpot = ann_to_ty_param_substs_opt_and_ty(cx, a);
1466     ret ty_param_substs_opt_and_ty_to_monotype(cx, tpot);
1467 }
1468
1469
1470 // Returns the number of distinct type parameters in the given type.
1471 fn count_ty_params(&ctxt cx, t ty) -> uint {
1472     fn counter(&ctxt cx, @mutable vec[uint] param_indices, t ty) {
1473         alt (struct(cx, ty)) {
1474             case (ty_param(?param_idx)) {
1475                 auto seen = false;
1476                 for (uint other_param_idx in *param_indices) {
1477                     if (param_idx == other_param_idx) {
1478                         seen = true;
1479                     }
1480                 }
1481                 if (!seen) {
1482                     *param_indices += [param_idx];
1483                 }
1484             }
1485             case (_) { /* fall through */ }
1486         }
1487     }
1488
1489     let vec[uint] v = [];    // FIXME: typechecker botch
1490     let @mutable vec[uint] param_indices = @mutable v;
1491     auto f = bind counter(cx, param_indices, _);
1492     walk_ty(cx, f, ty);
1493     ret vec::len[uint](*param_indices);
1494 }
1495
1496 fn type_contains_vars(&ctxt cx, &t typ) -> bool {
1497     ret interner::get[raw_t](*cx.ts, typ).has_vars;
1498 }
1499
1500 fn type_contains_params(&ctxt cx, &t typ) -> bool {
1501     ret interner::get[raw_t](*cx.ts, typ).has_params;
1502 }
1503
1504 // Type accessors for substructures of types
1505
1506 fn ty_fn_args(&ctxt cx, &t fty) -> vec[arg] {
1507     alt (struct(cx, fty)) {
1508         case (ty::ty_fn(_, ?a, _, _, _)) { ret a; }
1509         case (ty::ty_native_fn(_, ?a, _)) { ret a; }
1510     }
1511     cx.sess.bug("ty_fn_args() called on non-fn type");
1512 }
1513
1514 fn ty_fn_proto(&ctxt cx, &t fty) -> ast::proto {
1515     alt (struct(cx, fty)) {
1516         case (ty::ty_fn(?p, _, _, _, _)) { ret p; }
1517     }
1518     cx.sess.bug("ty_fn_proto() called on non-fn type");
1519 }
1520
1521 fn ty_fn_abi(&ctxt cx, &t fty) -> ast::native_abi {
1522     alt (struct(cx, fty)) {
1523         case (ty::ty_native_fn(?a, _, _)) { ret a; }
1524     }
1525     cx.sess.bug("ty_fn_abi() called on non-native-fn type");
1526 }
1527
1528 fn ty_fn_ret(&ctxt cx, &t fty) -> t {
1529     alt (struct(cx, fty)) {
1530         case (ty::ty_fn(_, _, ?r, _, _)) { ret r; }
1531         case (ty::ty_native_fn(_, _, ?r)) { ret r; }
1532     }
1533     cx.sess.bug("ty_fn_ret() called on non-fn type");
1534 }
1535
1536 fn is_fn_ty(&ctxt cx, &t fty) -> bool {
1537     alt (struct(cx, fty)) {
1538         case (ty::ty_fn(_, _, _, _, _)) { ret true; }
1539         case (ty::ty_native_fn(_, _, _)) { ret true; }
1540         case (_) { ret false; }
1541     }
1542 }
1543
1544 fn ty_var_id(&ctxt cx, t typ) -> int {
1545     alt (struct(cx, typ)) {
1546         case (ty::ty_var(?vid)) { ret vid; }
1547         case (_) { log_err "ty_var_id called on non-var ty"; fail; }
1548     }
1549 }
1550
1551
1552 // Type accessors for AST nodes
1553
1554 fn block_ty(&ctxt cx, &ast::block b) -> t {
1555     ret ann_to_type(cx, b.node.a);
1556 }
1557
1558 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
1559 // doesn't provide type parameter substitutions.
1560 fn pat_ty(&ctxt cx, &@ast::pat pat) -> t {
1561     ret ann_to_monotype(cx, pat_ann(pat));
1562 }
1563
1564 fn item_ann(&@ast::item it) -> ast::ann {
1565     alt (it.node) {
1566         case (ast::item_const(_,_,_,_,?a)) { ret a; }
1567         case (ast::item_fn(_,_,_,_,?a)) { ret a; }
1568         case (ast::item_mod(_,_,_)) {
1569             log_err "a module was passed to item_ann(), " +
1570                 "but modules haven't annotations";
1571             fail;
1572         }
1573         case (ast::item_native_mod(_,_,_)) {
1574             log_err "a native module was passed to item_ann(), " +
1575                 "but native modules haven't annotations";
1576             fail;
1577         }
1578         case (ast::item_ty(_,_,_,_,?a)) { ret a; }
1579         case (ast::item_tag(_,_,_,_,?a)) { ret a; }
1580         case (ast::item_obj(_,_,_,_,?a)) { ret a; }
1581     }
1582 }
1583
1584 fn expr_ann(&@ast::expr e) -> ast::ann {
1585     alt (e.node) {
1586         case (ast::expr_vec(_,_,_,?a)) { ret a; }
1587         case (ast::expr_tup(_,?a)) { ret a; }
1588         case (ast::expr_rec(_,_,?a)) { ret a; }
1589         case (ast::expr_call(_,_,?a)) { ret a; }
1590         case (ast::expr_bind(_,_,?a)) { ret a; }
1591         case (ast::expr_binary(_,_,_,?a)) { ret a; }
1592         case (ast::expr_unary(_,_,?a)) { ret a; }
1593         case (ast::expr_lit(_,?a)) { ret a; }
1594         case (ast::expr_cast(_,_,?a)) { ret a; }
1595         case (ast::expr_if(_,_,_,?a)) { ret a; }
1596         case (ast::expr_while(_,_,?a)) { ret a; }
1597         case (ast::expr_for(_,_,_,?a)) { ret a; }
1598         case (ast::expr_for_each(_,_,_,?a)) { ret a; }
1599         case (ast::expr_do_while(_,_,?a)) { ret a; }
1600         case (ast::expr_alt(_,_,?a)) { ret a; }
1601         case (ast::expr_block(_,?a)) { ret a; }
1602         case (ast::expr_move(_,_,?a)) { ret a; }
1603         case (ast::expr_assign(_,_,?a)) { ret a; }
1604         case (ast::expr_assign_op(_,_,_,?a)) { ret a; }
1605         case (ast::expr_send(_,_,?a)) { ret a; }
1606         case (ast::expr_recv(_,_,?a)) { ret a; }
1607         case (ast::expr_field(_,_,?a)) { ret a; }
1608         case (ast::expr_index(_,_,?a)) { ret a; }
1609         case (ast::expr_path(_,?a)) { ret a; }
1610         case (ast::expr_ext(_,_,_,_,?a)) { ret a; }
1611         case (ast::expr_fail(?a,_)) { ret a; }
1612         case (ast::expr_ret(_,?a)) { ret a; }
1613         case (ast::expr_put(_,?a)) { ret a; }
1614         case (ast::expr_be(_,?a)) { ret a; }
1615         case (ast::expr_log(_,_,?a)) { ret a; }
1616         case (ast::expr_assert(_,?a)) { ret a; }
1617         case (ast::expr_check(_,?a)) { ret a; }
1618         case (ast::expr_port(?a)) { ret a; }
1619         case (ast::expr_chan(_,?a)) { ret a; }
1620         case (ast::expr_anon_obj(_,_,_,?a)) { ret a; }
1621         case (ast::expr_break(?a)) { ret a; }
1622         case (ast::expr_cont(?a)) { ret a; }
1623         case (ast::expr_self_method(_, ?a)) { ret a; }
1624         case (ast::expr_spawn(_, _, _, _, ?a)) { ret a; }
1625     }
1626 }
1627
1628 // Returns the type of an expression as a monotype.
1629 //
1630 // NB: This type doesn't provide type parameter substitutions; e.g. if you
1631 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
1632 // instead of "fn(&T) -> T with T = int". If this isn't what you want, see
1633 // expr_ty_params_and_ty() below.
1634 fn expr_ty(&ctxt cx, &@ast::expr expr) -> t {
1635     ret ann_to_monotype(cx, expr_ann(expr));
1636 }
1637
1638 fn expr_ty_params_and_ty(&ctxt cx, &@ast::expr expr)
1639         -> tup(vec[t], t) {
1640     auto a = expr_ann(expr);
1641
1642     ret tup(ann_to_type_params(cx, a),
1643             ann_to_type(cx, a));
1644 }
1645
1646 fn expr_has_ty_params(&ctxt cx, &@ast::expr expr) -> bool {
1647     ret ann_has_type_params(cx, expr_ann(expr));
1648 }
1649
1650 fn decl_local_ty(&ctxt cx, &@ast::decl d) -> t {
1651     alt (d.node) {
1652         case (ast::decl_local(?l)) {
1653             ret ann_to_type(cx, l.ann);
1654         }
1655         case (_) {
1656             cx.sess.bug("decl_local_ty called on an item decl");
1657         }
1658     }
1659 }
1660
1661 fn stmt_ann(&@ast::stmt s) -> ast::ann {
1662     alt (s.node) {
1663         case (ast::stmt_decl(_, ?a)) { ret a; }
1664         case (ast::stmt_expr(_, ?a)) { ret a; }
1665         case (ast::stmt_crate_directive(_)) {
1666             log_err "ty::stmt_ann(): crate directive found";
1667             fail;
1668         }
1669     }
1670 }
1671
1672 fn pat_ann(&@ast::pat p) -> ast::ann {
1673     alt (p.node) {
1674         case (ast::pat_wild(?a))        { ret a; }
1675         case (ast::pat_bind(_, _, ?a))  { ret a; }
1676         case (ast::pat_lit(_, ?a))      { ret a; }
1677         case (ast::pat_tag(_, _, ?a))   { ret a; }
1678     }
1679 }
1680
1681
1682 // Expression utilities
1683
1684 fn field_num(&session::session sess, &span sp,
1685              &ast::ident id) -> uint {
1686     let uint accum = 0u;
1687     let uint i = 0u;
1688     for (u8 c in id) {
1689         if (i == 0u) {
1690             if (c != ('_' as u8)) {
1691                 sess.span_err(sp,
1692                               "bad numeric field on tuple: "
1693                               + "missing leading underscore");
1694             }
1695         } else {
1696             if (('0' as u8) <= c && c <= ('9' as u8)) {
1697                 accum *= 10u;
1698                 accum += (c as uint) - ('0' as uint);
1699             } else {
1700                 auto s = "";
1701                 s += str::unsafe_from_byte(c);
1702                 sess.span_err(sp,
1703                               "bad numeric field on tuple: "
1704                               + " non-digit character: "
1705                               + s);
1706             }
1707         }
1708         i += 1u;
1709     }
1710     ret accum;
1711 }
1712
1713 fn field_idx(&session::session sess, &span sp,
1714              &ast::ident id, &vec[field] fields) -> uint {
1715     let uint i = 0u;
1716     for (field f in fields) {
1717         if (str::eq(f.ident, id)) {
1718             ret i;
1719         }
1720         i += 1u;
1721     }
1722     sess.span_err(sp, "unknown field '" + id + "' of record");
1723 }
1724
1725 fn method_idx(&session::session sess, &span sp,
1726               &ast::ident id, &vec[method] meths) -> uint {
1727     let uint i = 0u;
1728     for (method m in meths) {
1729         if (str::eq(m.ident, id)) {
1730             ret i;
1731         }
1732         i += 1u;
1733     }
1734     sess.span_err(sp, "unknown method '" + id + "' of obj");
1735 }
1736
1737 fn sort_methods(&vec[method] meths) -> vec[method] {
1738     fn method_lteq(&method a, &method b) -> bool {
1739         ret str::lteq(a.ident, b.ident);
1740     }
1741
1742     ret std::sort::merge_sort[method](bind method_lteq(_,_), meths);
1743 }
1744
1745 fn is_lval(&@ast::expr expr) -> bool {
1746     alt (expr.node) {
1747         case (ast::expr_field(_,_,_))    { ret true;  }
1748         case (ast::expr_index(_,_,_))    { ret true;  }
1749         case (ast::expr_path(_,_))       { ret true;  }
1750         case (ast::expr_unary(ast::deref,_,_))  { ret true; }
1751         case (_)                        { ret false; }
1752     }
1753 }
1754
1755 // Type unification via Robinson's algorithm (Robinson 1965). Implemented as
1756 // described in Hoder and Voronkov:
1757 //
1758 //     http://www.cs.man.ac.uk/~hoderk/ubench/unification_full.pdf
1759
1760 mod unify {
1761     tag result {
1762         ures_ok(t);
1763         ures_err(type_err);
1764     }
1765
1766     tag union_result {
1767         unres_ok;
1768         unres_err(type_err);
1769     }
1770
1771     tag fixup_result {
1772         fix_ok(t);      // fixup succeeded
1773         fix_err(int);   // fixup failed because a type variable was unresolved
1774     }
1775
1776     type var_bindings = rec(ufind::ufind sets,
1777                             smallintmap::smallintmap[t] types);
1778
1779     type ctxt = rec(@var_bindings vb, ty_ctxt tcx);
1780
1781     fn mk_var_bindings() -> @var_bindings {
1782         ret @rec(sets=ufind::make(), types=smallintmap::mk[t]());
1783     }
1784
1785     // Unifies two sets.
1786     fn union(&@ctxt cx, uint set_a, uint set_b) -> union_result {
1787         ufind::grow(cx.vb.sets, uint::max(set_a, set_b) + 1u);
1788
1789         auto root_a = ufind::find(cx.vb.sets, set_a);
1790         auto root_b = ufind::find(cx.vb.sets, set_b);
1791         ufind::union(cx.vb.sets, set_a, set_b);
1792         auto root_c = ufind::find(cx.vb.sets, set_a);
1793
1794         alt (smallintmap::find[t](cx.vb.types, root_a)) {
1795             case (none[t]) {
1796                 alt (smallintmap::find[t](cx.vb.types, root_b)) {
1797                     case (none[t]) { ret unres_ok; }
1798                     case (some[t](?t_b)) {
1799                         smallintmap::insert[t](cx.vb.types, root_c, t_b);
1800                         ret unres_ok;
1801                     }
1802                 }
1803             }
1804             case (some[t](?t_a)) {
1805                 alt (smallintmap::find[t](cx.vb.types, root_b)) {
1806                     case (none[t]) {
1807                         smallintmap::insert[t](cx.vb.types, root_c, t_a);
1808                         ret unres_ok;
1809                     }
1810                     case (some[t](?t_b)) {
1811                         alt (unify_step(cx, t_a, t_b)) {
1812                             case (ures_ok(?t_c)) {
1813                                 smallintmap::insert[t](cx.vb.types, root_c,
1814                                                        t_c);
1815                                 ret unres_ok;
1816                             }
1817                             case (ures_err(?terr)) { ret unres_err(terr); }
1818                         }
1819                     }
1820                 }
1821             }
1822         }
1823     }
1824
1825     fn record_var_binding(&@ctxt cx, int key, t typ) -> result {
1826         ufind::grow(cx.vb.sets, (key as uint) + 1u);
1827         auto root = ufind::find(cx.vb.sets, key as uint);
1828
1829         auto result_type = typ;
1830         alt (smallintmap::find[t](cx.vb.types, root)) {
1831             case (some(?old_type)) {
1832                 alt (unify_step(cx, old_type, typ)) {
1833                     case (ures_ok(?unified_type)) {
1834                         result_type = unified_type;
1835                     }
1836                     case (?res) { ret res; }
1837                 }
1838             }
1839             case (none) { /* fall through */ }
1840         }
1841
1842         smallintmap::insert[t](cx.vb.types, root, result_type);
1843         ret ures_ok(typ);
1844     }
1845
1846     // Wraps the given type in an appropriate cname.
1847     //
1848     // TODO: This doesn't do anything yet. We should carry the cname up from
1849     // the expected and/or actual types when unification results in a type
1850     // identical to one or both of the two. The precise algorithm for this is
1851     // something we'll probably need to develop over time.
1852
1853     // Simple structural type comparison.
1854     fn struct_cmp(@ctxt cx, t expected, t actual) -> result {
1855         if (struct(cx.tcx, expected) == struct(cx.tcx, actual)) {
1856             ret ures_ok(expected);
1857         }
1858
1859         ret ures_err(terr_mismatch);
1860     }
1861
1862     // Unifies two mutability flags.
1863     fn unify_mut(ast::mutability expected, ast::mutability actual)
1864             -> option::t[ast::mutability] {
1865         if (expected == actual) {
1866             ret some[ast::mutability](expected);
1867         }
1868         if (expected == ast::maybe_mut) {
1869             ret some[ast::mutability](actual);
1870         }
1871         if (actual == ast::maybe_mut) {
1872             ret some[ast::mutability](expected);
1873         }
1874         ret none[ast::mutability];
1875     }
1876
1877     tag fn_common_res {
1878         fn_common_res_err(result);
1879         fn_common_res_ok(vec[arg], t);
1880     }
1881
1882     fn unify_fn_common(&@ctxt cx,
1883                        &t expected,
1884                        &t actual,
1885                        &vec[arg] expected_inputs, &t expected_output,
1886                        &vec[arg] actual_inputs, &t actual_output)
1887         -> fn_common_res {
1888         auto expected_len = vec::len[arg](expected_inputs);
1889         auto actual_len = vec::len[arg](actual_inputs);
1890         if (expected_len != actual_len) {
1891             ret fn_common_res_err(ures_err(terr_arg_count));
1892         }
1893
1894         // TODO: as above, we should have an iter2 iterator.
1895         let vec[arg] result_ins = [];
1896         auto i = 0u;
1897         while (i < expected_len) {
1898             auto expected_input = expected_inputs.(i);
1899             auto actual_input = actual_inputs.(i);
1900
1901             // Unify the result modes.
1902             auto result_mode;
1903             if (expected_input.mode != actual_input.mode) {
1904                 // FIXME this is the wrong error
1905                 ret fn_common_res_err(ures_err(terr_arg_count));
1906             } else {
1907                 result_mode = expected_input.mode;
1908             }
1909
1910             auto result = unify_step(cx, expected_input.ty, actual_input.ty);
1911
1912             alt (result) {
1913                 case (ures_ok(?rty)) {
1914                     result_ins += [rec(mode=result_mode, ty=rty)];
1915                 }
1916
1917                 case (_) {
1918                     ret fn_common_res_err(result);
1919                 }
1920             }
1921
1922             i += 1u;
1923         }
1924
1925         // Check the output.
1926         auto result = unify_step(cx, expected_output, actual_output);
1927         alt (result) {
1928             case (ures_ok(?rty)) {
1929                 ret fn_common_res_ok(result_ins, rty);
1930             }
1931
1932             case (_) {
1933                 ret fn_common_res_err(result);
1934             }
1935         }
1936     }
1937
1938     fn unify_fn(&@ctxt cx,
1939                 &ast::proto e_proto,
1940                 &ast::proto a_proto,
1941                 &t expected,
1942                 &t actual,
1943                 &vec[arg] expected_inputs, &t expected_output,
1944                 &vec[arg] actual_inputs, &t actual_output,
1945                 &controlflow expected_cf, &controlflow actual_cf,
1946                 &vec[@ast::constr] expected_constrs,
1947                 &vec[@ast::constr] actual_constrs)
1948         -> result {
1949
1950         if (e_proto != a_proto) {
1951             ret ures_err(terr_mismatch);
1952         }
1953         alt (expected_cf) {
1954             case (ast::return) { } // ok
1955             case (ast::noreturn) {
1956                 alt (actual_cf) {
1957                     case (ast::noreturn) {
1958                         // ok
1959                     }
1960                     case (_) {
1961                         /* even though typestate checking is mostly
1962                            responsible for checking control flow annotations,
1963                            this check is necessary to ensure that the
1964                            annotation in an object method matches the
1965                            declared object type */
1966                         ret ures_err(terr_controlflow_mismatch);
1967                     }
1968                 }
1969             }
1970         }
1971         auto t = unify_fn_common(cx, expected, actual,
1972                                  expected_inputs, expected_output,
1973                                  actual_inputs, actual_output);
1974         alt (t) {
1975             case (fn_common_res_err(?r)) {
1976                 ret r;
1977             }
1978             case (fn_common_res_ok(?result_ins, ?result_out)) {
1979                 auto t2 = mk_fn(cx.tcx, e_proto, result_ins, result_out,
1980                                 actual_cf, actual_constrs);
1981                 ret ures_ok(t2);
1982             }
1983         }
1984     }
1985
1986     fn unify_native_fn(&@ctxt cx,
1987                        &ast::native_abi e_abi,
1988                        &ast::native_abi a_abi,
1989                        &t expected,
1990                        &t actual,
1991                        &vec[arg] expected_inputs, &t expected_output,
1992                        &vec[arg] actual_inputs, &t actual_output)
1993         -> result {
1994         if (e_abi != a_abi) { ret ures_err(terr_mismatch); }
1995
1996         auto t = unify_fn_common(cx, expected, actual,
1997                                  expected_inputs, expected_output,
1998                                  actual_inputs, actual_output);
1999         alt (t) {
2000             case (fn_common_res_err(?r)) {
2001                 ret r;
2002             }
2003             case (fn_common_res_ok(?result_ins, ?result_out)) {
2004                 auto t2 = mk_native_fn(cx.tcx, e_abi, result_ins,
2005                                        result_out);
2006                 ret ures_ok(t2);
2007             }
2008         }
2009     }
2010
2011     fn unify_obj(&@ctxt cx,
2012                  &t expected,
2013                  &t actual,
2014                  &vec[method] expected_meths,
2015                  &vec[method] actual_meths) -> result {
2016       let vec[method] result_meths = [];
2017       let uint i = 0u;
2018       let uint expected_len = vec::len[method](expected_meths);
2019       let uint actual_len = vec::len[method](actual_meths);
2020
2021       if (expected_len != actual_len) { ret ures_err(terr_meth_count); }
2022
2023       while (i < expected_len) {
2024         auto e_meth = expected_meths.(i);
2025         auto a_meth = actual_meths.(i);
2026         if (! str::eq(e_meth.ident, a_meth.ident)) {
2027           ret ures_err(terr_obj_meths(e_meth.ident, a_meth.ident));
2028         }
2029         auto r = unify_fn(cx,
2030                           e_meth.proto, a_meth.proto,
2031                           expected, actual,
2032                           e_meth.inputs, e_meth.output,
2033                           a_meth.inputs, a_meth.output,
2034                           e_meth.cf, a_meth.cf,
2035                           e_meth.constrs, a_meth.constrs);
2036         alt (r) {
2037             case (ures_ok(?tfn)) {
2038                 alt (struct(cx.tcx, tfn)) {
2039                     case (ty_fn(?proto, ?ins, ?out, ?cf, ?constrs)) {
2040                         result_meths += [rec(inputs = ins,
2041                                              output = out,
2042                                              cf     = cf,
2043                                              constrs = constrs
2044                                              with e_meth)];
2045                     }
2046                 }
2047             }
2048             case (_) {
2049                 ret r;
2050             }
2051         }
2052         i += 1u;
2053       }
2054       auto t = mk_obj(cx.tcx, result_meths);
2055       ret ures_ok(t);
2056     }
2057
2058     // If the given type is a variable, returns the structure of that type.
2059     fn resolve_type_structure(&ty_ctxt tcx, &@var_bindings vb, t typ)
2060             -> fixup_result {
2061         alt (struct(tcx, typ)) {
2062             case (ty_var(?vid)) {
2063                 if ((vid as uint) >= ufind::set_count(vb.sets)) {
2064                     ret fix_err(vid);
2065                 }
2066
2067                 auto root_id = ufind::find(vb.sets, vid as uint);
2068                 alt (smallintmap::find[t](vb.types, root_id)) {
2069                     case (none[t]) { ret fix_err(vid); }
2070                     case (some[t](?rt)) { ret fix_ok(rt); }
2071                 }
2072             }
2073             case (_) { ret fix_ok(typ); }
2074         }
2075     }
2076
2077     fn unify_step(&@ctxt cx, &t expected, &t actual) -> result {
2078         // TODO: rewrite this using tuple pattern matching when available, to
2079         // avoid all this rightward drift and spikiness.
2080
2081         // TODO: occurs check, to make sure we don't loop forever when
2082         // unifying e.g. 'a and option['a]
2083
2084         // Fast path.
2085         if (eq_ty(expected, actual)) { ret ures_ok(expected); }
2086
2087         // Stage 1: Handle the cases in which one side or another is a type
2088         // variable.
2089
2090         alt (struct(cx.tcx, actual)) {
2091             // If the RHS is a variable type, then just do the appropriate
2092             // binding.
2093             case (ty::ty_var(?actual_id)) {
2094                 auto actual_n = actual_id as uint;
2095                 alt (struct(cx.tcx, expected)) {
2096                     case (ty::ty_var(?expected_id)) {
2097                         auto expected_n = expected_id as uint;
2098                         union(cx, expected_n, actual_n);
2099                     }
2100                     case (_) {
2101                         // Just bind the type variable to the expected type.
2102                         alt (record_var_binding(cx, actual_id, expected)) {
2103                             case (ures_ok(_)) { /* fall through */ }
2104                             case (?res) { ret res; }
2105                         }
2106                     }
2107                 }
2108                 ret ures_ok(mk_var(cx.tcx, actual_id));
2109             }
2110
2111             case (_) { /* empty */ }
2112         }
2113
2114         alt (struct(cx.tcx, expected)) {
2115             case (ty::ty_var(?expected_id)) {
2116                 // Add a binding. (`actual` can't actually be a var here.)
2117                 alt (record_var_binding(cx, expected_id, actual)) {
2118                     case (ures_ok(_)) { /* fall through */ }
2119                     case (?res) { ret res; }
2120                 }
2121                 ret ures_ok(mk_var(cx.tcx, expected_id));
2122             }
2123
2124             case (_) { /* fall through */ }
2125         }
2126
2127         // Stage 2: Handle all other cases.
2128
2129         alt (struct(cx.tcx, actual)) {
2130             case (ty::ty_bot)        { ret ures_ok(expected);                }
2131             case (_)                 { /* fall through */                    }
2132         }
2133
2134         alt (struct(cx.tcx, expected)) {
2135             case (ty::ty_nil)        { ret struct_cmp(cx, expected, actual); }
2136             // _|_ unifies with anything
2137             case (ty::ty_bot)        { ret ures_ok(actual);                  }
2138             case (ty::ty_bool)       { ret struct_cmp(cx, expected, actual); }
2139             case (ty::ty_int)        { ret struct_cmp(cx, expected, actual); }
2140             case (ty::ty_uint)       { ret struct_cmp(cx, expected, actual); }
2141             case (ty::ty_machine(_)) { ret struct_cmp(cx, expected, actual); }
2142             case (ty::ty_float)      { ret struct_cmp(cx, expected, actual); }
2143             case (ty::ty_char)       { ret struct_cmp(cx, expected, actual); }
2144             case (ty::ty_str)        { ret struct_cmp(cx, expected, actual); }
2145             case (ty::ty_istr)       { ret struct_cmp(cx, expected, actual); }
2146             case (ty::ty_type)       { ret struct_cmp(cx, expected, actual); }
2147             case (ty::ty_native)     { ret struct_cmp(cx, expected, actual); }
2148             case (ty::ty_param(_))   { ret struct_cmp(cx, expected, actual); }
2149
2150             case (ty::ty_tag(?expected_id, ?expected_tps)) {
2151                 alt (struct(cx.tcx, actual)) {
2152                     case (ty::ty_tag(?actual_id, ?actual_tps)) {
2153                         if (expected_id._0 != actual_id._0 ||
2154                                 expected_id._1 != actual_id._1) {
2155                             ret ures_err(terr_mismatch);
2156                         }
2157
2158                         // TODO: factor this cruft out, see the TODO in the
2159                         // ty::ty_tup case
2160                         let vec[t] result_tps = [];
2161                         auto i = 0u;
2162                         auto expected_len = vec::len[t](expected_tps);
2163                         while (i < expected_len) {
2164                             auto expected_tp = expected_tps.(i);
2165                             auto actual_tp = actual_tps.(i);
2166
2167                             auto result = unify_step(cx,
2168                                                      expected_tp,
2169                                                      actual_tp);
2170
2171                             alt (result) {
2172                                 case (ures_ok(?rty)) {
2173                                     vec::push[t](result_tps, rty);
2174                                 }
2175                                 case (_) {
2176                                     ret result;
2177                                 }
2178                             }
2179
2180                             i += 1u;
2181                         }
2182
2183                         ret ures_ok(mk_tag(cx.tcx, expected_id, result_tps));
2184                     }
2185                     case (_) { /* fall through */ }
2186                 }
2187
2188                 ret ures_err(terr_mismatch);
2189             }
2190
2191             case (ty::ty_box(?expected_mt)) {
2192                 alt (struct(cx.tcx, actual)) {
2193                     case (ty::ty_box(?actual_mt)) {
2194                         auto mut;
2195                         alt (unify_mut(expected_mt.mut, actual_mt.mut)) {
2196                             case (none) { ret ures_err(terr_box_mutability); }
2197                             case (some(?m)) { mut = m; }
2198                         }
2199
2200                         auto result = unify_step(cx,
2201                                                  expected_mt.ty,
2202                                                  actual_mt.ty);
2203                         alt (result) {
2204                             case (ures_ok(?result_sub)) {
2205                                 auto mt = rec(ty=result_sub, mut=mut);
2206                                 ret ures_ok(mk_box(cx.tcx, mt));
2207                             }
2208                             case (_) {
2209                                 ret result;
2210                             }
2211                         }
2212                     }
2213
2214                     case (_) { ret ures_err(terr_mismatch); }
2215                 }
2216             }
2217
2218             case (ty::ty_vec(?expected_mt)) {
2219                 alt (struct(cx.tcx, actual)) {
2220                     case (ty::ty_vec(?actual_mt)) {
2221                         auto mut;
2222                         alt (unify_mut(expected_mt.mut, actual_mt.mut)) {
2223                             case (none) { ret ures_err(terr_vec_mutability); }
2224                             case (some(?m)) { mut = m; }
2225                         }
2226
2227                         auto result = unify_step(cx,
2228                                                  expected_mt.ty,
2229                                                  actual_mt.ty);
2230                         alt (result) {
2231                             case (ures_ok(?result_sub)) {
2232                                 auto mt = rec(ty=result_sub, mut=mut);
2233                                 ret ures_ok(mk_vec(cx.tcx, mt));
2234                             }
2235                             case (_) {
2236                                 ret result;
2237                             }
2238                         }
2239                     }
2240
2241                     case (_) { ret ures_err(terr_mismatch); }
2242                 }
2243             }
2244
2245             case (ty::ty_ivec(?expected_mt)) {
2246                 alt (struct(cx.tcx, actual)) {
2247                     case (ty::ty_ivec(?actual_mt)) {
2248                         auto mut;
2249                         alt (unify_mut(expected_mt.mut, actual_mt.mut)) {
2250                             case (none) { ret ures_err(terr_vec_mutability); }
2251                             case (some(?m)) { mut = m; }
2252                         }
2253
2254                         auto result = unify_step(cx,
2255                                                  expected_mt.ty,
2256                                                  actual_mt.ty);
2257                         alt (result) {
2258                             case (ures_ok(?result_sub)) {
2259                                 auto mt = rec(ty=result_sub, mut=mut);
2260                                 ret ures_ok(mk_ivec(cx.tcx, mt));
2261                             }
2262                             case (_) {
2263                                 ret result;
2264                             }
2265                         }
2266                     }
2267
2268                     case (_) { ret ures_err(terr_mismatch); }
2269                 }
2270             }
2271
2272             case (ty::ty_port(?expected_sub)) {
2273                 alt (struct(cx.tcx, actual)) {
2274                     case (ty::ty_port(?actual_sub)) {
2275                         auto result = unify_step(cx,
2276                                                  expected_sub,
2277                                                  actual_sub);
2278                         alt (result) {
2279                             case (ures_ok(?result_sub)) {
2280                                 ret ures_ok(mk_port(cx.tcx, result_sub));
2281                             }
2282                             case (_) {
2283                                 ret result;
2284                             }
2285                         }
2286                     }
2287
2288                     case (_) { ret ures_err(terr_mismatch); }
2289                 }
2290             }
2291
2292             case (ty::ty_chan(?expected_sub)) {
2293                 alt (struct(cx.tcx, actual)) {
2294                     case (ty::ty_chan(?actual_sub)) {
2295                         auto result = unify_step(cx,
2296                                                  expected_sub,
2297                                                  actual_sub);
2298                         alt (result) {
2299                             case (ures_ok(?result_sub)) {
2300                                 ret ures_ok(mk_chan(cx.tcx, result_sub));
2301                             }
2302                             case (_) {
2303                                 ret result;
2304                             }
2305                         }
2306                     }
2307
2308                     case (_) { ret ures_err(terr_mismatch); }
2309                 }
2310             }
2311
2312             case (ty::ty_tup(?expected_elems)) {
2313                 alt (struct(cx.tcx, actual)) {
2314                     case (ty::ty_tup(?actual_elems)) {
2315                         auto expected_len = vec::len[ty::mt](expected_elems);
2316                         auto actual_len = vec::len[ty::mt](actual_elems);
2317                         if (expected_len != actual_len) {
2318                             auto err = terr_tuple_size(expected_len,
2319                                                        actual_len);
2320                             ret ures_err(err);
2321                         }
2322
2323                         // TODO: implement an iterator that can iterate over
2324                         // two arrays simultaneously.
2325                         let vec[ty::mt] result_elems = [];
2326                         auto i = 0u;
2327                         while (i < expected_len) {
2328                             auto expected_elem = expected_elems.(i);
2329                             auto actual_elem = actual_elems.(i);
2330
2331                             auto mut;
2332                             alt (unify_mut(expected_elem.mut,
2333                                            actual_elem.mut)) {
2334                                 case (none) {
2335                                     auto err = terr_tuple_mutability;
2336                                     ret ures_err(err);
2337                                 }
2338                                 case (some(?m)) { mut = m; }
2339                             }
2340
2341                             auto result = unify_step(cx,
2342                                                      expected_elem.ty,
2343                                                      actual_elem.ty);
2344                             alt (result) {
2345                                 case (ures_ok(?rty)) {
2346                                     auto mt = rec(ty=rty, mut=mut);
2347                                     result_elems += [mt];
2348                                 }
2349                                 case (_) {
2350                                     ret result;
2351                                 }
2352                             }
2353
2354                             i += 1u;
2355                         }
2356
2357                         ret ures_ok(mk_tup(cx.tcx, result_elems));
2358                     }
2359
2360                     case (_) { ret ures_err(terr_mismatch); }
2361                 }
2362             }
2363
2364             case (ty::ty_rec(?expected_fields)) {
2365                 alt (struct(cx.tcx, actual)) {
2366                     case (ty::ty_rec(?actual_fields)) {
2367                         auto expected_len = vec::len[field](expected_fields);
2368                         auto actual_len = vec::len[field](actual_fields);
2369                         if (expected_len != actual_len) {
2370                             auto err = terr_record_size(expected_len,
2371                                                         actual_len);
2372                             ret ures_err(err);
2373                         }
2374
2375                         // TODO: implement an iterator that can iterate over
2376                         // two arrays simultaneously.
2377                         let vec[field] result_fields = [];
2378                         auto i = 0u;
2379                         while (i < expected_len) {
2380                             auto expected_field = expected_fields.(i);
2381                             auto actual_field = actual_fields.(i);
2382
2383                             auto mut;
2384                             alt (unify_mut(expected_field.mt.mut,
2385                                            actual_field.mt.mut)) {
2386                                 case (none) {
2387                                     ret ures_err(terr_record_mutability);
2388                                 }
2389                                 case (some(?m)) { mut = m; }
2390                             }
2391
2392                             if (!str::eq(expected_field.ident,
2393                                          actual_field.ident)) {
2394                                 auto err =
2395                                     terr_record_fields(expected_field.ident,
2396                                                        actual_field.ident);
2397                                 ret ures_err(err);
2398                             }
2399
2400                             auto result = unify_step(cx,
2401                                                      expected_field.mt.ty,
2402                                                      actual_field.mt.ty);
2403                             alt (result) {
2404                                 case (ures_ok(?rty)) {
2405                                     auto mt = rec(ty=rty, mut=mut);
2406                                     vec::push[field]
2407                                         (result_fields,
2408                                          rec(mt=mt with expected_field));
2409                                 }
2410                                 case (_) {
2411                                     ret result;
2412                                 }
2413                             }
2414
2415                             i += 1u;
2416                         }
2417
2418                         ret ures_ok(mk_rec(cx.tcx, result_fields));
2419                     }
2420
2421                     case (_) { ret ures_err(terr_mismatch); }
2422                 }
2423             }
2424
2425             case (ty::ty_fn(?ep, ?expected_inputs,
2426                             ?expected_output, ?expected_cf,
2427                             ?expected_constrs)) {
2428                 alt (struct(cx.tcx, actual)) {
2429                     case (ty::ty_fn(?ap, ?actual_inputs,
2430                                     ?actual_output, ?actual_cf,
2431                                     ?actual_constrs)) {
2432                         ret unify_fn(cx, ep, ap,
2433                                      expected, actual,
2434                                      expected_inputs, expected_output,
2435                                      actual_inputs, actual_output,
2436                                      expected_cf, actual_cf,
2437                                      expected_constrs, actual_constrs);
2438                     }
2439
2440                     case (_) { ret ures_err(terr_mismatch); }
2441                 }
2442             }
2443
2444             case (ty::ty_native_fn(?e_abi, ?expected_inputs,
2445                                   ?expected_output)) {
2446                 alt (struct(cx.tcx, actual)) {
2447                     case (ty::ty_native_fn(?a_abi, ?actual_inputs,
2448                                           ?actual_output)) {
2449                         ret unify_native_fn(cx, e_abi, a_abi,
2450                                             expected, actual,
2451                                             expected_inputs, expected_output,
2452                                             actual_inputs, actual_output);
2453                     }
2454                     case (_) { ret ures_err(terr_mismatch); }
2455                 }
2456             }
2457
2458             case (ty::ty_obj(?expected_meths)) {
2459                 alt (struct(cx.tcx, actual)) {
2460                     case (ty::ty_obj(?actual_meths)) {
2461                         ret unify_obj(cx, expected, actual,
2462                                       expected_meths, actual_meths);
2463                     }
2464                     case (_) { ret ures_err(terr_mismatch); }
2465                 }
2466             }
2467         }
2468     }
2469
2470     fn unify(&t expected,
2471              &t actual,
2472              &@var_bindings vb,
2473              &ty_ctxt tcx) -> result {
2474         auto cx = @rec(vb=vb, tcx=tcx);
2475         ret unify_step(cx, expected, actual);
2476     }
2477
2478     fn dump_var_bindings(ty_ctxt tcx, @var_bindings vb) {
2479         auto i = 0u;
2480         while (i < vec::len[ufind::node](vb.sets.nodes)) {
2481             auto sets = "";
2482             auto j = 0u;
2483             while (j < vec::len[option::t[uint]](vb.sets.nodes)) {
2484                 if (ufind::find(vb.sets, j) == i) { sets += #fmt(" %u", j); }
2485                 j += 1u;
2486             }
2487
2488             auto typespec;
2489             alt (smallintmap::find[t](vb.types, i)) {
2490                 case (none[t]) { typespec = ""; }
2491                 case (some[t](?typ)) {
2492                     typespec = " =" + pretty::ppaux::ty_to_str(tcx, typ);
2493                 }
2494             }
2495
2496             log_err #fmt("set %u:%s%s", i, typespec, sets);
2497             i += 1u;
2498         }
2499     }
2500
2501     // Fixups and substitutions
2502
2503     fn fixup_vars(ty_ctxt tcx, @var_bindings vb, t typ) -> fixup_result {
2504         fn subst_vars(ty_ctxt tcx, @var_bindings vb,
2505                       @mutable option::t[int] unresolved, int vid) -> t {
2506             if ((vid as uint) >= ufind::set_count(vb.sets)) {
2507                 *unresolved = some[int](vid);
2508                 ret ty::mk_var(tcx, vid);
2509             }
2510
2511             auto root_id = ufind::find(vb.sets, vid as uint);
2512             alt (smallintmap::find[t](vb.types, root_id)) {
2513                 case (none[t]) {
2514                     *unresolved = some[int](vid);
2515                     ret ty::mk_var(tcx, vid);
2516                 }
2517                 case (some[t](?rt)) {
2518                     ret fold_ty(tcx,
2519                         fm_var(bind subst_vars(tcx, vb, unresolved, _)), rt);
2520                 }
2521             }
2522         }
2523
2524         auto unresolved = @mutable none[int];
2525         auto rty = fold_ty(tcx,
2526                            fm_var(bind subst_vars(tcx, vb, unresolved, _)),
2527                            typ);
2528
2529         auto ur = *unresolved;
2530         alt (ur) {
2531             case (none[int]) { ret fix_ok(rty); }
2532             case (some[int](?var_id)) { ret fix_err(var_id); }
2533         }
2534     }
2535
2536     fn resolve_type_var(&ty_ctxt tcx, &@var_bindings vb, int vid)
2537             -> fixup_result {
2538         if ((vid as uint) >= ufind::set_count(vb.sets)) { ret fix_err(vid); }
2539
2540         auto root_id = ufind::find(vb.sets, vid as uint);
2541         alt (smallintmap::find[t](vb.types, root_id)) {
2542             case (none[t]) { ret fix_err(vid); }
2543             case (some[t](?rt)) { ret fixup_vars(tcx, vb, rt); }
2544         }
2545     }
2546 }
2547
2548 fn type_err_to_str(&ty::type_err err) -> str {
2549     alt (err) {
2550         case (terr_mismatch) {
2551             ret "types differ";
2552         }
2553         case (terr_controlflow_mismatch) {
2554             ret "returning function used where non-returning function"
2555                 + " was expected";
2556         }
2557         case (terr_box_mutability) {
2558             ret "boxed values differ in mutability";
2559         }
2560         case (terr_vec_mutability) {
2561             ret "vectors differ in mutability";
2562         }
2563         case (terr_tuple_size(?e_sz, ?a_sz)) {
2564             ret "expected a tuple with " + uint::to_str(e_sz, 10u) +
2565                 " elements but found one with " + uint::to_str(a_sz, 10u) +
2566                 " elements";
2567         }
2568         case (terr_tuple_mutability) {
2569             ret "tuple elements differ in mutability";
2570         }
2571         case (terr_record_size(?e_sz, ?a_sz)) {
2572             ret "expected a record with " + uint::to_str(e_sz, 10u) +
2573                 " fields but found one with " + uint::to_str(a_sz, 10u) +
2574                 " fields";
2575         }
2576         case (terr_record_mutability) {
2577             ret "record elements differ in mutability";
2578         }
2579         case (terr_record_fields(?e_fld, ?a_fld)) {
2580             ret "expected a record with field '" + e_fld +
2581                 "' but found one with field '" + a_fld +
2582                 "'";
2583         }
2584         case (terr_arg_count) {
2585             ret "incorrect number of function parameters";
2586         }
2587         case (terr_meth_count) {
2588             ret "incorrect number of object methods";
2589         }
2590         case (terr_obj_meths(?e_meth, ?a_meth)) {
2591             ret "expected an obj with method '" + e_meth +
2592                 "' but found one with method '" + a_meth +
2593                 "'";
2594         }
2595     }
2596 }
2597
2598 // Converts type parameters in a type to type variables and returns the
2599 // resulting type along with a list of type variable IDs.
2600 fn bind_params_in_type(&ctxt cx, fn()->int next_ty_var, t typ,
2601                        uint ty_param_count) -> tup(vec[int], t) {
2602     let vec[int] param_var_ids = [];
2603     auto i = 0u;
2604     while (i < ty_param_count) {
2605         param_var_ids += [next_ty_var()];
2606         i += 1u;
2607     }
2608
2609     fn binder(ctxt cx, vec[int] param_var_ids, fn()->int next_ty_var,
2610               uint index) -> t {
2611         ret mk_var(cx, param_var_ids.(index));
2612     }
2613
2614     auto new_typ = fold_ty(cx,
2615         fm_param(bind binder(cx, param_var_ids, next_ty_var, _)), typ);
2616     ret tup(param_var_ids, new_typ);
2617 }
2618
2619 // Replaces type parameters in the given type using the given list of
2620 // substitions.
2621 fn substitute_type_params(&ctxt cx, vec[ty::t] substs, t typ) -> t {
2622     if (!type_contains_params(cx, typ)) { ret typ; }
2623
2624     fn substituter(ctxt cx, vec[ty::t] substs, uint idx) -> t {
2625         ret substs.(idx);
2626     }
2627
2628     ret fold_ty(cx, fm_param(bind substituter(cx, substs, _)), typ);
2629 }
2630
2631 fn def_has_ty_params(&ast::def def) -> bool {
2632     alt (def) {
2633         case (ast::def_fn(_))            { ret true;  }
2634         case (ast::def_obj(_))           { ret true;  }
2635         case (ast::def_obj_field(_))     { ret false; }
2636         case (ast::def_mod(_))           { ret false; }
2637         case (ast::def_const(_))         { ret false; }
2638         case (ast::def_arg(_))           { ret false; }
2639         case (ast::def_local(_))         { ret false; }
2640         case (ast::def_variant(_, _))    { ret true;  }
2641         case (ast::def_ty(_))            { ret false; }
2642         case (ast::def_ty_arg(_))        { ret false; }
2643         case (ast::def_binding(_))       { ret false; }
2644         case (ast::def_use(_))           { ret false; }
2645         case (ast::def_native_ty(_))     { ret false; }
2646         case (ast::def_native_fn(_))     { ret true;  }
2647     }
2648 }
2649
2650
2651 // Tag information
2652
2653 type variant_info = rec(vec[ty::t] args, ty::t ctor_ty, ast::def_id id);
2654
2655 fn tag_variants(&ctxt cx, &ast::def_id id) -> vec[variant_info] {
2656     if (cx.sess.get_targ_crate_num() != id._0) {
2657         ret creader::get_tag_variants(cx, id);
2658     }
2659
2660     assert (cx.items.contains_key(id));
2661     alt (cx.items.get(id)) {
2662         case (any_item_rust(?item)) {
2663             alt (item.node) {
2664                 case (ast::item_tag(_, ?variants, _, _, _)) {
2665                     let vec[variant_info] result = [];
2666                     for (ast::variant variant in variants) {
2667                         auto ctor_ty = ann_to_monotype(cx, variant.node.ann);
2668                         let vec[t] arg_tys = [];
2669                         if (vec::len[ast::variant_arg](variant.node.args)
2670                             > 0u) {
2671                             for (arg a in ty_fn_args(cx, ctor_ty)) {
2672                                 arg_tys += [a.ty];
2673                             }
2674                         }
2675                         auto did = variant.node.id;
2676                         result += [rec(args=arg_tys,
2677                                        ctor_ty=ctor_ty,
2678                                        id=did)];
2679                     }
2680                     ret result;
2681                 }
2682             }
2683         }
2684     }
2685 }
2686
2687 // Returns information about the tag variant with the given ID:
2688 fn tag_variant_with_id(&ctxt cx,
2689                        &ast::def_id tag_id,
2690                        &ast::def_id variant_id) -> variant_info {
2691     auto variants = tag_variants(cx, tag_id);
2692
2693     auto i = 0u;
2694     while (i < vec::len[variant_info](variants)) {
2695         auto variant = variants.(i);
2696         if (common::def_eq(variant.id, variant_id)) {
2697             ret variant;
2698         }
2699         i += 1u;
2700     }
2701
2702     cx.sess.bug("tag_variant_with_id(): no variant exists with that ID");
2703
2704 }
2705
2706 // If the given item is in an external crate, looks up its type and adds it to
2707 // the type cache. Returns the type parameters and type.
2708 fn lookup_item_type(ctxt cx, ast::def_id did) -> ty_param_count_and_ty {
2709     if (did._0 == cx.sess.get_targ_crate_num()) {
2710         // The item is in this crate. The caller should have added it to the
2711         // type cache already; we simply return it.
2712         ret cx.tcache.get(did);
2713     }
2714
2715     alt (cx.tcache.find(did)) {
2716         case (some(?tpt)) { ret tpt; }
2717         case (none) {
2718             auto tyt = creader::get_type(cx, did);
2719             cx.tcache.insert(did, tyt);
2720             ret tyt;
2721         }
2722     }
2723 }
2724
2725 fn ret_ty_of_fn_ty(ctxt cx, t a_ty) -> t {
2726     alt (ty::struct(cx, a_ty)) {
2727         case (ty::ty_fn(_, _, ?ret_ty, _, _)) {
2728             ret ret_ty;
2729         }
2730         case (_) {
2731             cx.sess.bug("ret_ty_of_fn_ty() called on non-function type");
2732         }
2733     }
2734 }
2735
2736 fn ret_ty_of_fn(ctxt cx, ast::ann ann) -> t {
2737     ret ret_ty_of_fn_ty(cx, ann_to_type(cx, ann));
2738 }
2739
2740 fn lookup_fn_decl(ty_ctxt tcx, ast::ann ann)
2741     -> option::t[tup(ast::fn_decl, ast::def_id)] {
2742     auto nada = none[tup(ast::fn_decl, ast::def_id)];
2743     alt (tcx.def_map.find(ann.id)) {
2744         case (some(ast::def_fn(?d))) {
2745             alt (tcx.items.find(d)) {
2746                 case (some(any_item_rust(?it))) {
2747                     alt (it.node) {
2748                         case (ast::item_fn(_,?f,_,_,_)) {
2749                             ret some(tup(f.decl, d));
2750                         }
2751                         case (_) { ret nada; }
2752                     }
2753                 }
2754                 case (_) { ret nada; }
2755             }
2756         }
2757         case (_) { ret nada; }
2758     }
2759 }
2760
2761 // Local Variables:
2762 // mode: rust
2763 // fill-column: 78;
2764 // indent-tabs-mode: nil
2765 // c-basic-offset: 4
2766 // buffer-file-coding-system: utf-8-unix
2767 // compile-command: "make -k -C $RBUILD 2>&1 | sed -e 's/\\/x\\//x:\\//g'";
2768 // End: