ty.rs 96.6 KB
Newer Older
1
import std::int;
2 3 4
import std::str;
import std::uint;
import std::vec;
5 6 7 8 9 10 11 12 13 14 15
import std::box;
import std::ufind;
import std::map;
import std::map::hashmap;
import std::option;
import std::option::none;
import std::option::some;

import driver::session;
import front::ast;
import front::ast::mutability;
16
import front::ast::controlflow;
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
import front::creader;
import middle::metadata;
import util::common;

import util::common::ty_u8;
import util::common::ty_u16;
import util::common::ty_u32;
import util::common::ty_u64;

import util::common::ty_i8;
import util::common::ty_i16;
import util::common::ty_i32;
import util::common::ty_i64;

import util::common::ty_f32;
import util::common::ty_f64;

import util::common::new_def_hash;
import util::common::span;
36
import middle::tstate::ann::ts_ann;
37

38
import util::data::interner;
39

40 41
// Data types

42 43 44 45 46 47 48
tag mode {
    mo_val;
    mo_alias;
    mo_either;
}

type arg = rec(mode mode, t ty);
49 50 51
type field = rec(ast::ident ident, mt mt);
type method = rec(ast::proto proto,
                  ast::ident ident,
52
                  vec[arg] inputs,
53 54
                  t output,
                  controlflow cf);
55

56 57 58 59 60 61 62
tag any_item {
    any_item_rust(@ast::item);
    any_item_native(@ast::native_item, ast::native_abi);
}

type item_table = hashmap[ast::def_id,any_item];

63
type mt = rec(t ty, ast::mutability mut);
64

65 66
// Contains information needed to resolve types and (in the future) look up
// the types of AST nodes.
67
type creader_cache = hashmap[tup(int,uint,uint),ty::t];
68
type ctxt = rec(@type_store ts,
69 70
                session::session sess,
                resolve::def_map def_map,
71
                node_type_table node_types,
72
                item_table items,
73
                type_cache tcache,
74 75
                creader_cache rcache,
                hashmap[t,str] short_names_cache);
76
type ty_ctxt = ctxt;    // Needed for disambiguation from unify::ctxt.
77

78 79
// Convert from method type to function type.  Pretty easy; we just drop
// 'ident'.
80
fn method_ty_to_fn_ty(&ctxt cx, method m) -> t {
81
    ret mk_fn(cx, m.proto, m.inputs, m.output, m.cf);
82 83
}

84
// Never construct these manually. These are interned.
85 86
//
// TODO: It'd be really nice to be able to hide this definition from the
87
// outside world, to enforce the above invariants.
88
type raw_t = rec(sty struct,
89
                 option::t[str] cname,
90 91 92 93
                 uint hash,
                 bool has_params,
                 bool has_bound_params,
                 bool has_vars,
94
                 bool has_locals);
95 96

type t = uint;
97

98
// NB: If you change this, you'll probably want to change the corresponding
99
// AST structure in front/ast::rs as well.
100 101
tag sty {
    ty_nil;
102
    ty_bot;
103 104
    ty_bool;
    ty_int;
105
    ty_float;
106
    ty_uint;
107
    ty_machine(util::common::ty_mach);
108 109
    ty_char;
    ty_str;
110
    ty_tag(ast::def_id, vec[t]);
111 112
    ty_box(mt);
    ty_vec(mt);
113 114
    ty_port(t);
    ty_chan(t);
115
    ty_task;
116
    ty_tup(vec[mt]);
117
    ty_rec(vec[field]);
118
    ty_fn(ast::proto, vec[arg], t, controlflow);
119
    ty_native_fn(ast::native_abi, vec[arg], t);
120 121
    ty_obj(vec[method]);
    ty_var(int);                                    // ephemeral type var
122
    ty_local(ast::def_id);                           // type of a local var
123
    ty_param(uint);                                 // fn/tag type param
124
    ty_bound_param(uint);                           // bound param, only paths
G
Graydon Hoare 已提交
125
    ty_type;
126
    ty_native;
127
    // TODO: ty_fn_arg(t), for a possibly-aliased function argument
128 129
}

130 131 132
// Data structures used in type unification

type unify_handler = obj {
133
    fn resolve_local(ast::def_id id) -> option::t[t];
134 135
    fn record_local(ast::def_id id, t ty);  // TODO: -> unify::result
    fn record_param(uint index, t binding) -> unify::result;
136 137 138 139
};

tag type_err {
    terr_mismatch;
140
    terr_controlflow_mismatch;
141 142
    terr_box_mutability;
    terr_vec_mutability;
143 144 145 146
    terr_tuple_size(uint, uint);
    terr_tuple_mutability;
    terr_record_size(uint, uint);
    terr_record_mutability;
147
    terr_record_fields(ast::ident,ast::ident);
G
Graydon Hoare 已提交
148
    terr_meth_count;
149
    terr_obj_meths(ast::ident,ast::ident);
150 151 152
    terr_arg_count;
}

153

154
type ty_param_count_and_ty = tup(uint, t);
155
type type_cache = hashmap[ast::def_id,ty_param_count_and_ty];
156

157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
const uint idx_nil      = 0u;
const uint idx_bool     = 1u;
const uint idx_int      = 2u;
const uint idx_float    = 3u;
const uint idx_uint     = 4u;
const uint idx_i8       = 5u;
const uint idx_i16      = 6u;
const uint idx_i32      = 7u;
const uint idx_i64      = 8u;
const uint idx_u8       = 9u;
const uint idx_u16      = 10u;
const uint idx_u32      = 11u;
const uint idx_u64      = 12u;
const uint idx_f32      = 13u;
const uint idx_f64      = 14u;
const uint idx_char     = 15u;
const uint idx_str      = 16u;
const uint idx_task     = 17u;
const uint idx_native   = 18u;
const uint idx_type     = 19u;
177 178
const uint idx_bot      = 20u;
const uint idx_first_others = 21u;
179

180
type type_store = interner::interner[raw_t];
181

182
type ty_param_substs_opt_and_ty = tup(option::t[vec[ty::t]], ty::t);
183 184
type node_type_table =
    @mutable vec[mutable option::t[ty::ty_param_substs_opt_and_ty]];
185

186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
fn populate_type_store(&ctxt cx) {

    intern(cx, ty_nil, none[str]);
    intern(cx, ty_bool, none[str]);
    intern(cx, ty_int, none[str]);
    intern(cx, ty_float, none[str]);
    intern(cx, ty_uint, none[str]);
    intern(cx, ty_machine(ty_i8), none[str]);
    intern(cx, ty_machine(ty_i16), none[str]);
    intern(cx, ty_machine(ty_i32), none[str]);
    intern(cx, ty_machine(ty_i64), none[str]);
    intern(cx, ty_machine(ty_u8), none[str]);
    intern(cx, ty_machine(ty_u16), none[str]);
    intern(cx, ty_machine(ty_u32), none[str]);
    intern(cx, ty_machine(ty_u64), none[str]);
    intern(cx, ty_machine(ty_f32), none[str]);
    intern(cx, ty_machine(ty_f64), none[str]);
    intern(cx, ty_char, none[str]);
    intern(cx, ty_str, none[str]);
    intern(cx, ty_task, none[str]);
    intern(cx, ty_native, none[str]);
    intern(cx, ty_type, none[str]);
    intern(cx, ty_bot, none[str]);

    assert vec::len(cx.ts.vect) == idx_first_others;
211 212
}

213 214 215 216 217 218 219 220 221 222 223 224
fn mk_rcache() -> creader_cache {
    fn hash_cache_entry(&tup(int,uint,uint) k) -> uint {
        ret (k._0 as uint) + k._1 + k._2;
    }
    fn eq_cache_entries(&tup(int,uint,uint) a,
                        &tup(int,uint,uint) b) -> bool {
        ret a._0 == b._0 &&
            a._1 == b._1 &&
            a._2 == b._2;
    }
    auto h = hash_cache_entry;
    auto e = eq_cache_entries;
225
    ret map::mk_hashmap[tup(int,uint,uint),t](h, e);
226
}
227

228
fn mk_ctxt(session::session s, resolve::def_map dm) -> ctxt {
229 230 231 232 233 234 235 236

    let vec[mutable option::t[ty::ty_param_substs_opt_and_ty]] ntt_sub =
        [mutable];
    let node_type_table ntt = @mutable ntt_sub;

    auto tcache =
        common::new_def_hash[ty::ty_param_count_and_ty]();

237
    auto items = common::new_def_hash[any_item]();
238
    auto ts = @interner::mk[raw_t](hash_raw_ty, eq_raw_ty);
239 240 241

    auto cx =
        rec(ts = ts,
242
            sess = s,
243
            def_map = dm,
244
            node_types = ntt,
245
            items = items,
246
            tcache = tcache,
247 248
            rcache = mk_rcache(),
            short_names_cache =
249 250 251 252
            map::mk_hashmap[ty::t,str](ty::hash_ty, ty::eq_ty));

    populate_type_store(cx);
    ret cx;
253
}
254 255


256 257
// Type constructors

258
fn mk_raw_ty(&ctxt cx, &sty st, &option::t[str] cname) -> raw_t {
259
    auto h = hash_type_info(st, cname);
260 261 262 263 264 265

    let bool has_params = false;
    let bool has_bound_params = false;
    let bool has_vars = false;
    let bool has_locals = false;

266
    fn derive_flags_t(&ctxt cx,
267
                      &mutable bool has_params,
268 269 270 271
                      &mutable bool has_bound_params,
                      &mutable bool has_vars,
                      &mutable bool has_locals,
                      &t tt) {
272
        auto rt = interner::get[raw_t](*cx.ts, tt);
273 274 275 276
        has_params = has_params || rt.has_params;
        has_bound_params = has_bound_params || rt.has_bound_params;
        has_vars = has_vars || rt.has_vars;
        has_locals = has_locals || rt.has_locals;
277 278
    }

279
    fn derive_flags_mt(&ctxt cx,
280
                       &mutable bool has_params,
281 282 283 284
                       &mutable bool has_bound_params,
                       &mutable bool has_vars,
                       &mutable bool has_locals,
                       &mt m) {
285
        derive_flags_t(cx, has_params, has_bound_params,
286
                       has_vars, has_locals, m.ty);
287 288 289
    }


290
    fn derive_flags_arg(&ctxt cx,
291
                        &mutable bool has_params,
292 293 294 295
                        &mutable bool has_bound_params,
                        &mutable bool has_vars,
                        &mutable bool has_locals,
                        &arg a) {
296
        derive_flags_t(cx, has_params, has_bound_params,
297
                       has_vars, has_locals, a.ty);
298 299
    }

300
    fn derive_flags_sig(&ctxt cx,
301
                        &mutable bool has_params,
302 303 304 305 306 307
                        &mutable bool has_bound_params,
                        &mutable bool has_vars,
                        &mutable bool has_locals,
                        &vec[arg] args,
                        &t tt) {
        for (arg a in args) {
308
            derive_flags_arg(cx, has_params, has_bound_params,
309
                             has_vars, has_locals, a);
310
        }
311
        derive_flags_t(cx, has_params, has_bound_params,
312
                       has_vars, has_locals, tt);
313 314 315
    }

    alt (st) {
316 317 318 319 320 321
        case (ty_param(_)) {
            has_params = true;
        }
        case (ty_bound_param(_)) {
            has_bound_params = true;
        }
322 323
        case (ty_var(_)) { has_vars = true; }
        case (ty_local(_)) { has_locals = true; }
324
        case (ty_tag(_, ?tys)) {
325
            for (t tt in tys) {
326
                derive_flags_t(cx, has_params, has_bound_params,
327
                               has_vars, has_locals, tt);
328 329 330
            }
        }
        case (ty_box(?m)) {
331
            derive_flags_mt(cx, has_params, has_bound_params,
332
                            has_vars, has_locals, m);
333 334 335
        }

        case (ty_vec(?m)) {
336
            derive_flags_mt(cx, has_params, has_bound_params,
337
                            has_vars, has_locals, m);
338 339 340
        }

        case (ty_port(?tt)) {
341
            derive_flags_t(cx, has_params, has_bound_params,
342
                           has_vars, has_locals, tt);
343 344 345
        }

        case (ty_chan(?tt)) {
346
            derive_flags_t(cx, has_params, has_bound_params,
347
                           has_vars, has_locals, tt);
348 349 350 351
        }

        case (ty_tup(?mts)) {
            for (mt m in mts) {
352
                derive_flags_mt(cx, has_params, has_bound_params,
353
                                has_vars, has_locals, m);
354 355 356 357 358
            }
        }

        case (ty_rec(?flds)) {
            for (field f in flds) {
359
                derive_flags_mt(cx, has_params, has_bound_params,
360
                                has_vars, has_locals, f.mt);
361 362 363
            }
        }

364
        case (ty_fn(_, ?args, ?tt, _)) {
365
            derive_flags_sig(cx, has_params, has_bound_params,
366
                             has_vars, has_locals, args, tt);
367 368 369
        }

        case (ty_native_fn(_, ?args, ?tt)) {
370
            derive_flags_sig(cx, has_params, has_bound_params,
371
                             has_vars, has_locals, args, tt);
372 373 374 375
        }

        case (ty_obj(?meths)) {
            for (method m in meths) {
376
                derive_flags_sig(cx, has_params, has_bound_params,
377
                                 has_vars, has_locals, m.inputs, m.output);
378 379 380 381 382
            }
        }
        case (_) { }
    }

383 384 385 386
    ret rec(struct=st, cname=cname, hash=h,
            has_params = has_params,
            has_bound_params = has_bound_params,
            has_vars = has_vars,
387
            has_locals = has_locals);
388 389
}

390 391
fn intern(&ctxt cx, &sty st, &option::t[str] cname) {
    interner::intern[raw_t](*cx.ts, mk_raw_ty(cx, st, cname));
392
}
P
Patrick Walton 已提交
393

394
fn gen_ty_full(&ctxt cx, &sty st, &option::t[str] cname) -> t {
395
    auto raw_type = mk_raw_ty(cx, st, cname);
396
    ret interner::intern[raw_t](*cx.ts, raw_type);
P
Patrick Walton 已提交
397 398
}

399 400
// These are private constructors to this module. External users should always
// use the mk_foo() functions below.
401
fn gen_ty(&ctxt cx, &sty st) -> t {
402 403 404
    ret gen_ty_full(cx, st, none[str]);
}

405
fn mk_nil(&ctxt cx) -> t          { ret idx_nil; }
406
fn mk_bot(&ctxt cx) -> t          { ret idx_bot; }
407 408 409 410
fn mk_bool(&ctxt cx) -> t         { ret idx_bool; }
fn mk_int(&ctxt cx) -> t          { ret idx_int; }
fn mk_float(&ctxt cx) -> t        { ret idx_float; }
fn mk_uint(&ctxt cx) -> t         { ret idx_uint; }
411

412
fn mk_mach(&ctxt cx, &util::common::ty_mach tm) -> t {
413
    alt (tm) {
414 415 416 417 418 419 420 421 422 423 424 425
        case (ty_u8)  { ret idx_u8; }
        case (ty_u16) { ret idx_u16; }
        case (ty_u32) { ret idx_u32; }
        case (ty_u64) { ret idx_u64; }

        case (ty_i8)  { ret idx_i8; }
        case (ty_i16) { ret idx_i16; }
        case (ty_i32) { ret idx_i32; }
        case (ty_i64) { ret idx_i64; }

        case (ty_f32) { ret idx_f32; }
        case (ty_f64) { ret idx_f64; }
426 427
    }
    fail;
428 429
}

430 431
fn mk_char(&ctxt cx) -> t    { ret idx_char; }
fn mk_str(&ctxt cx) -> t     { ret idx_str; }
432

433
fn mk_tag(&ctxt cx, &ast::def_id did, &vec[t] tys) -> t {
434
    ret gen_ty(cx, ty_tag(did, tys));
435
}
436

437
fn mk_box(&ctxt cx, &mt tm) -> t {
438
    ret gen_ty(cx, ty_box(tm));
439 440
}

441
fn mk_imm_box(&ctxt cx, &t ty) -> t {
442
    ret mk_box(cx, rec(ty=ty, mut=ast::imm));
443 444
}

445
fn mk_vec(&ctxt cx, &mt tm) -> t  { ret gen_ty(cx, ty_vec(tm)); }
446 447 448 449 450

fn mk_imm_vec(&ctxt cx, &t typ) -> t {
    ret gen_ty(cx, ty_vec(rec(ty=typ, mut=ast::imm)));
}

451 452 453
fn mk_port(&ctxt cx, &t ty) -> t  { ret gen_ty(cx, ty_port(ty)); }
fn mk_chan(&ctxt cx, &t ty) -> t  { ret gen_ty(cx, ty_chan(ty)); }
fn mk_task(&ctxt cx) -> t        { ret gen_ty(cx, ty_task); }
454

455
fn mk_tup(&ctxt cx, &vec[mt] tms) -> t { ret gen_ty(cx, ty_tup(tms)); }
456

457
fn mk_imm_tup(&ctxt cx, &vec[t] tys) -> t {
458
    // TODO: map
459
    let vec[ty::mt] mts = [];
460
    for (t typ in tys) {
461
        mts += [rec(ty=typ, mut=ast::imm)];
462
    }
463
    ret mk_tup(cx, mts);
464 465
}

466
fn mk_rec(&ctxt cx, &vec[field] fs) -> t { ret gen_ty(cx, ty_rec(fs)); }
467

468 469 470
fn mk_fn(&ctxt cx, &ast::proto proto, &vec[arg] args, &t ty,
         &controlflow cf) -> t {
    ret gen_ty(cx, ty_fn(proto, args, ty, cf));
471 472
}

473
fn mk_native_fn(&ctxt cx, &ast::native_abi abi, &vec[arg] args, &t ty) -> t {
474
    ret gen_ty(cx, ty_native_fn(abi, args, ty));
475
}
476

477
fn mk_obj(&ctxt cx, &vec[method] meths) -> t {
478
    ret gen_ty(cx, ty_obj(meths));
479 480
}

481
fn mk_var(&ctxt cx, int v) -> t {
482
    ret gen_ty(cx, ty_var(v));
483
}
484

485
fn mk_local(&ctxt cx, ast::def_id did) -> t {
486
    ret gen_ty(cx, ty_local(did));
487 488
}

489
fn mk_param(&ctxt cx, uint n) -> t {
490
    ret gen_ty(cx, ty_param(n));
491 492
}

493
fn mk_bound_param(&ctxt cx, uint n) -> t {
494
    ret gen_ty(cx, ty_bound_param(n));
495 496
}

497 498
fn mk_type(&ctxt cx) -> t    { ret idx_type; }
fn mk_native(&ctxt cx) -> t  { ret idx_native; }
499 500


501
// Returns the one-level-deep type structure of the given type.
502 503 504
fn struct(&ctxt cx, &t typ) -> sty {
    ret interner::get[raw_t](*cx.ts, typ).struct;
}
505

506
// Returns the canonical name of the given type.
507 508 509
fn cname(&ctxt cx, &t typ) -> option::t[str] {
    ret interner::get[raw_t](*cx.ts, typ).cname;
}
510

511

512 513
// Stringification

514
fn path_to_str(&ast::path pth) -> str {
515 516
    auto result = str::connect(pth.node.idents,  "::");
    if (vec::len[@ast::ty](pth.node.types) > 0u) {
517
        auto f = pretty::pprust::ty_to_str;
518
        result += "[";
519
        result += str::connect(vec::map(f, pth.node.types), ",");
520 521 522 523 524
        result += "]";
    }
    ret result;
}

525
fn ty_to_str(&ctxt cx, &t typ) -> str {
526

527
    fn fn_input_to_str(&ctxt cx, &rec(mode mode, t ty) input) -> str {
528
        auto s;
529 530 531 532
        alt (input.mode) {
            case (mo_val) { s = ""; }
            case (mo_alias) { s = "&"; }
            case (mo_either) { s = "?"; }
533 534
        }

535
        ret s + ty_to_str(cx, input.ty);
536 537
    }

538
    fn fn_to_str(&ctxt cx,
539 540
                 ast::proto proto,
                 option::t[ast::ident] ident,
541
                 vec[arg] inputs, t output) -> str {
542
            auto f = bind fn_input_to_str(cx, _);
543 544 545

            auto s;
            alt (proto) {
546
                case (ast::proto_iter) {
547 548
                    s = "iter";
                }
549
                case (ast::proto_fn) {
550 551
                    s = "fn";
                }
552
            }
553

554
            alt (ident) {
555
                case (some[ast::ident](?i)) {
556 557 558 559 560 561 562
                    s += " ";
                    s += i;
                }
                case (_) { }
            }

            s += "(";
563
            s += str::connect(vec::map[arg,str](f, inputs), ", ");
564 565
            s += ")";

566 567
            if (struct(cx, output) != ty_nil) {
                s += " -> " + ty_to_str(cx, output);
568 569 570 571
            }
            ret s;
    }

572
    fn method_to_str(&ctxt cx, &method m) -> str {
573
        ret fn_to_str(cx, m.proto, some[ast::ident](m.ident),
574
                      m.inputs, m.output) + ";";
575 576
    }

577
    fn field_to_str(&ctxt cx, &field f) -> str {
578
        ret mt_to_str(cx, f.mt) + " " + f.ident;
579 580
    }

581
    fn mt_to_str(&ctxt cx, &mt m) -> str {
582 583
        auto mstr;
        alt (m.mut) {
584 585 586
            case (ast::mut)       { mstr = "mutable "; }
            case (ast::imm)       { mstr = "";         }
            case (ast::maybe_mut) { mstr = "mutable? "; }
587 588
        }

589
        ret mstr + ty_to_str(cx, m.ty);
590 591
    }

592 593 594 595 596 597 598
    alt (cname(cx, typ)) {
        case (some[str](?cs)) {
            ret cs;
        }
        case (_) { }
    }

599
    auto s = "";
600

601
    alt (struct(cx, typ)) {
602 603
        case (ty_native)       { s += "native";                         }
        case (ty_nil)          { s += "()";                             }
604
        case (ty_bot)          { s += "_|_";                            }
605 606 607 608
        case (ty_bool)         { s += "bool";                           }
        case (ty_int)          { s += "int";                            }
        case (ty_float)        { s += "float";                          }
        case (ty_uint)         { s += "uint";                           }
609
        case (ty_machine(?tm)) { s += common::ty_mach_to_str(tm);        }
610 611
        case (ty_char)         { s += "char";                           }
        case (ty_str)          { s += "str";                            }
612 613 614 615
        case (ty_box(?tm))     { s += "@" + mt_to_str(cx, tm);          }
        case (ty_vec(?tm))     { s += "vec[" + mt_to_str(cx, tm) + "]"; }
        case (ty_port(?t))     { s += "port[" + ty_to_str(cx, t) + "]"; }
        case (ty_chan(?t))     { s += "chan[" + ty_to_str(cx, t) + "]"; }
616
        case (ty_type)         { s += "type";                           }
617
        case (ty_task)         { s += "task";                           }
618 619

        case (ty_tup(?elems)) {
620
            auto f = bind mt_to_str(cx, _);
621 622
            auto strs = vec::map[mt,str](f, elems);
            s += "tup(" + str::connect(strs, ",") + ")";
623 624 625
        }

        case (ty_rec(?elems)) {
626
            auto f = bind field_to_str(cx, _);
627 628
            auto strs = vec::map[field,str](f, elems);
            s += "rec(" + str::connect(strs, ",") + ")";
629 630
        }

631
        case (ty_tag(?id, ?tps)) {
632
            // The user should never see this if the cname is set properly!
633 634
            s += "<tag#" + util::common::istr(id._0) + ":" +
                util::common::istr(id._1) + ">";
635
            if (vec::len[t](tps) > 0u) {
636
                auto f = bind ty_to_str(cx, _);
637 638
                auto strs = vec::map[t,str](f, tps);
                s += "[" + str::connect(strs, ",") + "]";
639
            }
640 641
        }

642
        case (ty_fn(?proto, ?inputs, ?output, _)) {
643
            s += fn_to_str(cx, proto, none[ast::ident], inputs, output);
644 645
        }

646
        case (ty_native_fn(_, ?inputs, ?output)) {
647 648
            s += fn_to_str(cx, ast::proto_fn, none[ast::ident],
                           inputs, output);
649 650
        }

651
        case (ty_obj(?meths)) {
652
            auto f = bind method_to_str(cx, _);
653 654
            auto m = vec::map[method,str](f, meths);
            s += "obj {\n\t" + str::connect(m, "\n\t") + "\n}";
655 656 657
        }

        case (ty_var(?v)) {
658
            s += "<T" + util::common::istr(v) + ">";
659 660
        }

G
Graydon Hoare 已提交
661
        case (ty_local(?id)) {
662 663
            s += "<L" + util::common::istr(id._0) + ":" +
                util::common::istr(id._1) + ">";
G
Graydon Hoare 已提交
664 665
        }

666
        case (ty_param(?id)) {
667
            s += "'" + str::unsafe_from_bytes([('a' as u8) + (id as u8)]);
668
        }
669 670

        case (ty_bound_param(?id)) {
671
            s += "''" + str::unsafe_from_bytes([('a' as u8) +
672
                                                    (id as u8)]);
673
        }
674 675 676 677 678

        case (_) {
            s += ty_to_short_str(cx, typ);
        }

679 680 681 682 683
    }

    ret s;
}

684
fn ty_to_short_str(&ctxt cx, t typ) -> str {
685
    auto f = def_to_str;
686 687
    auto ecx = @rec(ds=f, tcx=cx, abbrevs=metadata::ac_no_abbrevs);
    auto s = metadata::Encode::ty_str(ecx, typ);
688
    if (str::byte_len(s) >= 32u) { s = str::substr(s, 0u, 32u); }
689
    ret s;
690 691
}

692 693
// Type folds

694
type ty_walk = fn(t);
695

696
fn walk_ty(&ctxt cx, ty_walk walker, t ty) {
697
    alt (struct(cx, ty)) {
698
        case (ty_nil)           { /* no-op */ }
699
        case (ty_bot)           { /* no-op */ }
700 701 702 703 704 705 706 707 708
        case (ty_bool)          { /* no-op */ }
        case (ty_int)           { /* no-op */ }
        case (ty_uint)          { /* no-op */ }
        case (ty_float)         { /* no-op */ }
        case (ty_machine(_))    { /* no-op */ }
        case (ty_char)          { /* no-op */ }
        case (ty_str)           { /* no-op */ }
        case (ty_type)          { /* no-op */ }
        case (ty_native)        { /* no-op */ }
709 710 711 712
        case (ty_box(?tm))      { walk_ty(cx, walker, tm.ty); }
        case (ty_vec(?tm))      { walk_ty(cx, walker, tm.ty); }
        case (ty_port(?subty))  { walk_ty(cx, walker, subty); }
        case (ty_chan(?subty))  { walk_ty(cx, walker, subty); }
713
        case (ty_tag(?tid, ?subtys)) {
714
            for (t subty in subtys) {
715
                walk_ty(cx, walker, subty);
716 717 718 719
            }
        }
        case (ty_tup(?mts)) {
            for (mt tm in mts) {
720
                walk_ty(cx, walker, tm.ty);
721 722 723 724
            }
        }
        case (ty_rec(?fields)) {
            for (field fl in fields) {
725
                walk_ty(cx, walker, fl.mt.ty);
726 727
            }
        }
728
        case (ty_fn(?proto, ?args, ?ret_ty, _)) {
729
            for (arg a in args) {
730
                walk_ty(cx, walker, a.ty);
731
            }
732
            walk_ty(cx, walker, ret_ty);
733 734 735
        }
        case (ty_native_fn(?abi, ?args, ?ret_ty)) {
            for (arg a in args) {
736
                walk_ty(cx, walker, a.ty);
737
            }
738
            walk_ty(cx, walker, ret_ty);
739 740
        }
        case (ty_obj(?methods)) {
741
            let vec[method] new_methods = [];
742 743
            for (method m in methods) {
                for (arg a in m.inputs) {
744
                    walk_ty(cx, walker, a.ty);
745
                }
746
                walk_ty(cx, walker, m.output);
747 748 749 750 751 752 753
            }
        }
        case (ty_var(_))         { /* no-op */ }
        case (ty_local(_))       { /* no-op */ }
        case (ty_param(_))       { /* no-op */ }
        case (ty_bound_param(_)) { /* no-op */ }
    }
754

755 756 757
    walker(ty);
}

758
type ty_fold = fn(t) -> t;
759

760
fn fold_ty(&ctxt cx, ty_fold fld, t ty_0) -> t {
761
    auto ty = ty_0;
762
    alt (struct(cx, ty)) {
763
        case (ty_nil)           { /* no-op */ }
764
        case (ty_bot)           { /* no-op */ }
765 766 767 768 769 770 771 772 773
        case (ty_bool)          { /* no-op */ }
        case (ty_int)           { /* no-op */ }
        case (ty_uint)          { /* no-op */ }
        case (ty_float)         { /* no-op */ }
        case (ty_machine(_))    { /* no-op */ }
        case (ty_char)          { /* no-op */ }
        case (ty_str)           { /* no-op */ }
        case (ty_type)          { /* no-op */ }
        case (ty_native)        { /* no-op */ }
774
        case (ty_box(?tm)) {
775 776
            ty = copy_cname(cx, mk_box(cx, rec(ty=fold_ty(cx, fld, tm.ty),
                                               mut=tm.mut)), ty);
777
        }
778
        case (ty_vec(?tm)) {
779 780
            ty = copy_cname(cx, mk_vec(cx, rec(ty=fold_ty(cx, fld, tm.ty),
                                                          mut=tm.mut)), ty);
781
        }
782
        case (ty_port(?subty)) {
783
            ty = copy_cname(cx, mk_port(cx, fold_ty(cx, fld, subty)), ty);
784 785
        }
        case (ty_chan(?subty)) {
786
            ty = copy_cname(cx, mk_chan(cx, fold_ty(cx, fld, subty)), ty);
787
        }
788
        case (ty_tag(?tid, ?subtys)) {
789
            let vec[t] new_subtys = [];
790
            for (t subty in subtys) {
791
                new_subtys += [fold_ty(cx, fld, subty)];
792
            }
793
            ty = copy_cname(cx, mk_tag(cx, tid, new_subtys), ty);
794
        }
795
        case (ty_tup(?mts)) {
796
            let vec[mt] new_mts = [];
797
            for (mt tm in mts) {
798
                auto new_subty = fold_ty(cx, fld, tm.ty);
799
                new_mts += [rec(ty=new_subty, mut=tm.mut)];
800
            }
801
            ty = copy_cname(cx, mk_tup(cx, new_mts), ty);
802 803
        }
        case (ty_rec(?fields)) {
804
            let vec[field] new_fields = [];
805
            for (field fl in fields) {
806
                auto new_ty = fold_ty(cx, fld, fl.mt.ty);
807
                auto new_mt = rec(ty=new_ty, mut=fl.mt.mut);
808
                new_fields += [rec(ident=fl.ident, mt=new_mt)];
809
            }
810
            ty = copy_cname(cx, mk_rec(cx, new_fields), ty);
811
        }
812
        case (ty_fn(?proto, ?args, ?ret_ty, ?cf)) {
813
            let vec[arg] new_args = [];
814
            for (arg a in args) {
815
                auto new_ty = fold_ty(cx, fld, a.ty);
816
                new_args += [rec(mode=a.mode, ty=new_ty)];
817
            }
818
            ty = copy_cname(cx, mk_fn(cx, proto, new_args,
819
                                      fold_ty(cx, fld, ret_ty), cf), ty);
820
        }
821
        case (ty_native_fn(?abi, ?args, ?ret_ty)) {
822
            let vec[arg] new_args = [];
823
            for (arg a in args) {
824
                auto new_ty = fold_ty(cx, fld, a.ty);
825
                new_args += [rec(mode=a.mode, ty=new_ty)];
826
            }
827 828
            ty = copy_cname(cx, mk_native_fn(cx, abi, new_args,
                                             fold_ty(cx, fld, ret_ty)), ty);
829
        }
830
        case (ty_obj(?methods)) {
831
            let vec[method] new_methods = [];
832
            for (method m in methods) {
833
                let vec[arg] new_args = [];
834
                for (arg a in m.inputs) {
835 836
                    new_args += [rec(mode=a.mode,
                                        ty=fold_ty(cx, fld, a.ty))];
837
                }
838
                new_methods += [rec(proto=m.proto, ident=m.ident,
839 840
                               inputs=new_args,
                               output=fold_ty(cx, fld, m.output), cf=m.cf)];
841
            }
842
            ty = copy_cname(cx, mk_obj(cx, new_methods), ty);
843
        }
844 845 846 847
        case (ty_var(_))         { /* no-op */ }
        case (ty_local(_))       { /* no-op */ }
        case (ty_param(_))       { /* no-op */ }
        case (ty_bound_param(_)) { /* no-op */ }
848 849
    }

850
    ret fld(ty);
851 852 853 854
}

// Type utilities

855
fn rename(&ctxt cx, t typ, str new_cname) -> t {
856
    ret gen_ty_full(cx, struct(cx, typ), some[str](new_cname));
857 858 859 860
}

// Returns a type with the structural part taken from `struct_ty` and the
// canonical name from `cname_ty`.
861
fn copy_cname(&ctxt cx, t struct_ty, t cname_ty) -> t {
862
    ret gen_ty_full(cx, struct(cx, struct_ty), cname(cx, cname_ty));
863 864
}

865
fn type_is_nil(&ctxt cx, &t ty) -> bool {
866
    alt (struct(cx, ty)) {
867 868 869
        case (ty_nil) { ret true; }
        case (_) { ret false; }
    }
870 871 872 873 874 875 876
}

fn type_is_bot(&ctxt cx, &t ty) -> bool {
    alt (struct(cx, ty)) {
        case (ty_bot) { ret true; }
        case (_) { ret false; }
    }
877 878
}

879
fn type_is_bool(&ctxt cx, &t ty) -> bool {
880
    alt (struct(cx, ty)) {
881 882 883 884 885
        case (ty_bool) { ret true; }
        case (_) { ret false; }
    }
}

886

887
fn type_is_structural(&ctxt cx, &t ty) -> bool {
888
    alt (struct(cx, ty)) {
889 890 891
        case (ty_tup(_))    { ret true; }
        case (ty_rec(_))    { ret true; }
        case (ty_tag(_,_))  { ret true; }
892
        case (ty_fn(_,_,_,_)) { ret true; }
893 894
        case (ty_obj(_))    { ret true; }
        case (_)            { ret false; }
895 896 897 898
    }
    fail;
}

899
fn type_is_sequence(&ctxt cx, &t ty) -> bool {
900
    alt (struct(cx, ty)) {
901 902 903 904 905 906 907
        case (ty_str)    { ret true; }
        case (ty_vec(_))    { ret true; }
        case (_)            { ret false; }
    }
    fail;
}

908
fn sequence_element_type(&ctxt cx, &t ty) -> t {
909
    alt (struct(cx, ty)) {
910
        case (ty_str)      { ret mk_mach(cx, common::ty_u8); }
911
        case (ty_vec(?mt)) { ret mt.ty; }
912 913 914 915
    }
    fail;
}

916
fn type_is_tup_like(&ctxt cx, &t ty) -> bool {
917
    alt (struct(cx, ty)) {
918 919 920 921 922
        case (ty_box(_))    { ret true; }
        case (ty_tup(_))    { ret true; }
        case (ty_rec(_))    { ret true; }
        case (ty_tag(_,_))  { ret true; }
        case (_)            { ret false; }
923 924 925 926
    }
    fail;
}

927
fn get_element_type(&ctxt cx, &t ty, uint i) -> t {
928
    assert (type_is_tup_like(cx, ty));
929
    alt (struct(cx, ty)) {
930 931
        case (ty_tup(?mts)) {
            ret mts.(i).ty;
932 933
        }
        case (ty_rec(?flds)) {
934
            ret flds.(i).mt.ty;
935 936 937 938 939
        }
    }
    fail;
}

940
fn type_is_box(&ctxt cx, &t ty) -> bool {
941
    alt (struct(cx, ty)) {
942 943 944 945 946 947
        case (ty_box(_)) { ret true; }
        case (_) { ret false; }
    }
    fail;
}

948
fn type_is_boxed(&ctxt cx, &t ty) -> bool {
949
    alt (struct(cx, ty)) {
950 951 952
        case (ty_str) { ret true; }
        case (ty_vec(_)) { ret true; }
        case (ty_box(_)) { ret true; }
B
Brian Anderson 已提交
953 954
        case (ty_port(_)) { ret true; }
        case (ty_chan(_)) { ret true; }
955 956 957 958 959
        case (_) { ret false; }
    }
    fail;
}

960
fn type_is_scalar(&ctxt cx, &t ty) -> bool {
961
    alt (struct(cx, ty)) {
962 963 964
        case (ty_nil) { ret true; }
        case (ty_bool) { ret true; }
        case (ty_int) { ret true; }
965
        case (ty_float) { ret true; }
966 967 968
        case (ty_uint) { ret true; }
        case (ty_machine(_)) { ret true; }
        case (ty_char) { ret true; }
G
Graydon Hoare 已提交
969
        case (ty_type) { ret true; }
970
        case (ty_native) { ret true; }
971 972 973 974 975
        case (_) { ret false; }
    }
    fail;
}

976

977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019
fn type_has_pointers(&ctxt cx, &t ty) -> bool {
    alt (struct(cx, ty)) {
        // scalar types
        case (ty_nil) { ret false; }
        case (ty_bool) { ret false; }
        case (ty_int) { ret false; }
        case (ty_float) { ret false; }
        case (ty_uint) { ret false; }
        case (ty_machine(_)) { ret false; }
        case (ty_char) { ret false; }
        case (ty_type) { ret false; }
        case (ty_native) { ret false; }

        case (ty_tup(?elts))    {
            for (mt m in elts) {
                if (type_has_pointers(cx, m.ty)) { ret true; }
            }
            ret false;
        }
        case (ty_rec(?flds)) {
            for (field f in flds) {
                if (type_has_pointers(cx, f.mt.ty)) { ret true; }
            }
            ret false;
        }

        case (ty_tag(?did,?tps))  {
            auto variants = tag_variants(cx, did);
            for (variant_info variant in variants) {
                auto tup_ty = mk_imm_tup(cx, variant.args);
                // Perform any type parameter substitutions.
                tup_ty = bind_params_in_type(cx, tup_ty);
                tup_ty = substitute_type_params(cx, tps, tup_ty);
                if (type_has_pointers(cx, tup_ty)) { ret true; }
            }
            ret false;
        }
        case (_) { ret true; }
    }
    fail;
}


1020 1021
// FIXME: should we just return true for native types in
// type_is_scalar?
1022
fn type_is_native(&ctxt cx, &t ty) -> bool {
1023
    alt (struct(cx, ty)) {
1024 1025 1026 1027 1028 1029
        case (ty_native) { ret true; }
        case (_) { ret false; }
    }
    fail;
}

1030
fn type_has_dynamic_size(&ctxt cx, &t ty) -> bool {
1031
    alt (struct(cx, ty)) {
1032
        case (ty_tup(?mts)) {
1033
            auto i = 0u;
1034
            while (i < vec::len[mt](mts)) {
1035
                if (type_has_dynamic_size(cx, mts.(i).ty)) { ret true; }
1036 1037 1038 1039 1040
                i += 1u;
            }
        }
        case (ty_rec(?fields)) {
            auto i = 0u;
1041
            while (i < vec::len[field](fields)) {
1042
                if (type_has_dynamic_size(cx, fields.(i).mt.ty)) {
1043 1044
                    ret true;
                }
1045 1046 1047
                i += 1u;
            }
        }
1048 1049
        case (ty_tag(_, ?subtys)) {
            auto i = 0u;
1050
            while (i < vec::len[t](subtys)) {
1051
                if (type_has_dynamic_size(cx, subtys.(i))) { ret true; }
1052 1053 1054
                i += 1u;
            }
        }
1055 1056 1057 1058 1059
        case (ty_param(_)) { ret true; }
        case (_) { /* fall through */ }
    }
    ret false;
}
1060

1061
fn type_is_integral(&ctxt cx, &t ty) -> bool {
1062
    alt (struct(cx, ty)) {
1063 1064 1065 1066
        case (ty_int) { ret true; }
        case (ty_uint) { ret true; }
        case (ty_machine(?m)) {
            alt (m) {
1067 1068 1069 1070 1071 1072 1073 1074 1075
                case (common::ty_i8) { ret true; }
                case (common::ty_i16) { ret true; }
                case (common::ty_i32) { ret true; }
                case (common::ty_i64) { ret true; }

                case (common::ty_u8) { ret true; }
                case (common::ty_u16) { ret true; }
                case (common::ty_u32) { ret true; }
                case (common::ty_u64) { ret true; }
1076 1077 1078 1079 1080 1081 1082 1083 1084
                case (_) { ret false; }
            }
        }
        case (ty_char) { ret true; }
        case (_) { ret false; }
    }
    fail;
}

1085
fn type_is_fp(&ctxt cx, &t ty) -> bool {
1086
    alt (struct(cx, ty)) {
1087 1088
        case (ty_machine(?tm)) {
            alt (tm) {
1089 1090
                case (common::ty_f32) { ret true; }
                case (common::ty_f64) { ret true; }
1091 1092 1093
                case (_) { ret false; }
            }
        }
1094 1095 1096
        case (ty_float) {
            ret true;
        }
1097 1098 1099 1100 1101
        case (_) { ret false; }
    }
    fail;
}

1102
fn type_is_signed(&ctxt cx, &t ty) -> bool {
1103
    alt (struct(cx, ty)) {
1104 1105 1106
        case (ty_int) { ret true; }
        case (ty_machine(?tm)) {
            alt (tm) {
1107 1108 1109 1110
                case (common::ty_i8) { ret true; }
                case (common::ty_i16) { ret true; }
                case (common::ty_i32) { ret true; }
                case (common::ty_i64) { ret true; }
1111 1112 1113 1114 1115 1116 1117 1118
                case (_) { ret false; }
            }
        }
        case (_) { ret false; }
    }
    fail;
}

1119
fn type_param(&ctxt cx, &t ty) -> option::t[uint] {
1120
    alt (struct(cx, ty)) {
1121 1122
        case (ty_param(?id)) { ret some[uint](id); }
        case (_)             { /* fall through */  }
1123
    }
1124
    ret none[uint];
1125 1126
}

1127
fn def_to_str(&ast::def_id did) -> str {
1128 1129 1130
    ret #fmt("%d:%d", did._0, did._1);
}

1131

P
Patrick Walton 已提交
1132 1133 1134
// Type hashing. This function is private to this module (and slow); external
// users should use `hash_ty()` instead.
fn hash_type_structure(&sty st) -> uint {
1135 1136 1137 1138 1139
    fn hash_uint(uint id, uint n) -> uint {
        auto h = id;
        h += h << 5u + n;
        ret h;
    }
P
Patrick Walton 已提交
1140

1141
    fn hash_def(uint id, ast::def_id did) -> uint {
1142 1143 1144 1145
        auto h = id;
        h += h << 5u + (did._0 as uint);
        h += h << 5u + (did._1 as uint);
        ret h;
1146
    }
P
Patrick Walton 已提交
1147

1148
    fn hash_subty(uint id, &t subty) -> uint {
1149 1150 1151 1152 1153
        auto h = id;
        h += h << 5u + hash_ty(subty);
        ret h;
    }

1154
    fn hash_fn(uint id, &vec[arg] args, &t rty) -> uint {
1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170
        auto h = id;
        for (arg a in args) {
            h += h << 5u + hash_ty(a.ty);
        }
        h += h << 5u + hash_ty(rty);
        ret h;
    }

    alt (st) {
        case (ty_nil) { ret 0u; }
        case (ty_bool) { ret 1u; }
        case (ty_int) { ret 2u; }
        case (ty_float) { ret 3u; }
        case (ty_uint) { ret 4u; }
        case (ty_machine(?tm)) {
            alt (tm) {
1171 1172 1173 1174
                case (common::ty_i8) { ret 5u; }
                case (common::ty_i16) { ret 6u; }
                case (common::ty_i32) { ret 7u; }
                case (common::ty_i64) { ret 8u; }
1175

1176 1177 1178 1179
                case (common::ty_u8) { ret 9u; }
                case (common::ty_u16) { ret 10u; }
                case (common::ty_u32) { ret 11u; }
                case (common::ty_u64) { ret 12u; }
1180

1181 1182
                case (common::ty_f32) { ret 13u; }
                case (common::ty_f64) { ret 14u; }
1183 1184 1185 1186 1187 1188
            }
        }
        case (ty_char) { ret 15u; }
        case (ty_str) { ret 16u; }
        case (ty_tag(?did, ?tys)) {
            auto h = hash_def(17u, did);
1189
            for (t typ in tys) {
1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212
                h += h << 5u + hash_ty(typ);
            }
            ret h;
        }
        case (ty_box(?mt)) { ret hash_subty(18u, mt.ty); }
        case (ty_vec(?mt)) { ret hash_subty(19u, mt.ty); }
        case (ty_port(?typ)) { ret hash_subty(20u, typ); }
        case (ty_chan(?typ)) { ret hash_subty(21u, typ); }
        case (ty_task) { ret 22u; }
        case (ty_tup(?mts)) {
            auto h = 23u;
            for (mt tm in mts) {
                h += h << 5u + hash_ty(tm.ty);
            }
            ret h;
        }
        case (ty_rec(?fields)) {
            auto h = 24u;
            for (field f in fields) {
                h += h << 5u + hash_ty(f.mt.ty);
            }
            ret h;
        }
1213
        case (ty_fn(_, ?args, ?rty, _)) { ret hash_fn(25u, args, rty); }
1214 1215 1216 1217
        case (ty_native_fn(_, ?args, ?rty)) { ret hash_fn(26u, args, rty); }
        case (ty_obj(?methods)) {
            auto h = 27u;
            for (method m in methods) {
1218
                h += h << 5u + str::hash(m.ident);
1219 1220 1221 1222 1223 1224 1225 1226 1227
            }
            ret h;
        }
        case (ty_var(?v)) { ret hash_uint(28u, v as uint); }
        case (ty_local(?did)) { ret hash_def(29u, did); }
        case (ty_param(?pid)) { ret hash_uint(30u, pid); }
        case (ty_bound_param(?pid)) { ret hash_uint(31u, pid); }
        case (ty_type) { ret 32u; }
        case (ty_native) { ret 33u; }
1228
        case (ty_bot) { ret 34u; }
1229
    }
1230 1231
}

1232
fn hash_type_info(&sty st, &option::t[str] cname_opt) -> uint {
1233 1234 1235
    auto h = hash_type_structure(st);
    alt (cname_opt) {
        case (none[str]) { /* no-op */ }
1236
        case (some[str](?s)) { h += h << 5u + str::hash(s); }
1237 1238 1239 1240
    }
    ret h;
}

1241 1242 1243
fn hash_raw_ty(&raw_t rt) -> uint { ret rt.hash; }

fn hash_ty(&t typ) -> uint { ret typ; }
P
Patrick Walton 已提交
1244

1245

1246 1247 1248 1249
// Type equality. This function is private to this module (and slow); external
// users should use `eq_ty()` instead.
fn equal_type_structures(&sty a, &sty b) -> bool {
    fn equal_mt(&mt a, &mt b) -> bool {
1250
        ret a.mut == b.mut && eq_ty(a.ty, b.ty);
1251 1252
    }

1253 1254
    fn equal_fn(&vec[arg] args_a, &t rty_a,
                &vec[arg] args_b, &t rty_b) -> bool {
1255
        if (!eq_ty(rty_a, rty_b)) { ret false; }
1256

1257 1258
        auto len = vec::len[arg](args_a);
        if (len != vec::len[arg](args_b)) { ret false; }
1259

1260 1261 1262
        auto i = 0u;
        while (i < len) {
            auto arg_a = args_a.(i); auto arg_b = args_b.(i);
1263
            if (arg_a.mode != arg_b.mode) { ret false; }
1264
            if (!eq_ty(arg_a.ty, arg_b.ty)) { ret false; }
1265 1266 1267 1268 1269
            i += 1u;
        }
        ret true;
    }

1270
    fn equal_def(&ast::def_id did_a, &ast::def_id did_b) -> bool {
1271 1272 1273 1274 1275 1276 1277 1278 1279 1280
        ret did_a._0 == did_b._0 && did_a._1 == did_b._1;
    }

    alt (a) {
        case (ty_nil) {
            alt (b) {
                case (ty_nil) { ret true; }
                case (_) { ret false; }
            }
        }
1281 1282 1283 1284 1285 1286
        case (ty_bot) {
            alt(b) {
                case (ty_bot) { ret true; }
                case (_)      { ret false; }
            }
        }
1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333
        case (ty_bool) {
            alt (b) {
                case (ty_bool) { ret true; }
                case (_) { ret false; }
            }
        }
        case (ty_int) {
            alt (b) {
                case (ty_int) { ret true; }
                case (_) { ret false; }
            }
        }
        case (ty_float) {
            alt (b) {
                case (ty_float) { ret true; }
                case (_) { ret false; }
            }
        }
        case (ty_uint) {
            alt (b) {
                case (ty_uint) { ret true; }
                case (_) { ret false; }
            }
        }
        case (ty_machine(?tm_a)) {
            alt (b) {
                case (ty_machine(?tm_b)) {
                    ret hash_type_structure(a) == hash_type_structure(b);
                }
                case (_) { ret false; }
            }
        }
        case (ty_char) {
            alt (b) {
                case (ty_char) { ret true; }
                case (_) { ret false; }
            }
        }
        case (ty_str) {
            alt (b) {
                case (ty_str) { ret true; }
                case (_) { ret false; }
            }
        }
        case (ty_tag(?id_a, ?tys_a)) {
            alt (b) {
                case (ty_tag(?id_b, ?tys_b)) {
P
Patrick Walton 已提交
1334
                    if (!equal_def(id_a, id_b)) { ret false; }
1335

1336 1337
                    auto len = vec::len[t](tys_a);
                    if (len != vec::len[t](tys_b)) { ret false; }
1338 1339
                    auto i = 0u;
                    while (i < len) {
1340
                        if (!eq_ty(tys_a.(i), tys_b.(i))) { ret false; }
1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361
                        i += 1u;
                    }
                    ret true;
                }
                case (_) { ret false; }
            }
        }
        case (ty_box(?mt_a)) {
            alt (b) {
                case (ty_box(?mt_b)) { ret equal_mt(mt_a, mt_b); }
                case (_) { ret false; }
            }
        }
        case (ty_vec(?mt_a)) {
            alt (b) {
                case (ty_vec(?mt_b)) { ret equal_mt(mt_a, mt_b); }
                case (_) { ret false; }
            }
        }
        case (ty_port(?t_a)) {
            alt (b) {
1362
                case (ty_port(?t_b)) { ret eq_ty(t_a, t_b); }
1363 1364 1365 1366 1367
                case (_) { ret false; }
            }
        }
        case (ty_chan(?t_a)) {
            alt (b) {
1368
                case (ty_chan(?t_b)) { ret eq_ty(t_a, t_b); }
1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380
                case (_) { ret false; }
            }
        }
        case (ty_task) {
            alt (b) {
                case (ty_task) { ret true; }
                case (_) { ret false; }
            }
        }
        case (ty_tup(?mts_a)) {
            alt (b) {
                case (ty_tup(?mts_b)) {
1381 1382
                    auto len = vec::len[mt](mts_a);
                    if (len != vec::len[mt](mts_b)) { ret false; }
1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395
                    auto i = 0u;
                    while (i < len) {
                        if (!equal_mt(mts_a.(i), mts_b.(i))) { ret false; }
                        i += 1u;
                    }
                    ret true;
                }
                case (_) { ret false; }
            }
        }
        case (ty_rec(?flds_a)) {
            alt (b) {
                case (ty_rec(?flds_b)) {
1396 1397
                    auto len = vec::len[field](flds_a);
                    if (len != vec::len[field](flds_b)) { ret false; }
1398 1399 1400
                    auto i = 0u;
                    while (i < len) {
                        auto fld_a = flds_a.(i); auto fld_b = flds_b.(i);
1401
                        if (!str::eq(fld_a.ident, fld_b.ident) ||
1402 1403 1404 1405 1406 1407 1408 1409 1410 1411
                                !equal_mt(fld_a.mt, fld_b.mt)) {
                            ret false;
                        }
                        i += 1u;
                    }
                    ret true;
                }
                case (_) { ret false; }
            }
        }
1412
        case (ty_fn(?p_a, ?args_a, ?rty_a, ?cf_a)) {
1413
            alt (b) {
1414
                case (ty_fn(?p_b, ?args_b, ?rty_b, ?cf_b)) {
1415
                    ret p_a == p_b &&
1416
                        cf_a == cf_b &&
1417 1418 1419 1420 1421 1422 1423 1424
                        equal_fn(args_a, rty_a, args_b, rty_b);
                }
                case (_) { ret false; }
            }
        }
        case (ty_native_fn(?abi_a, ?args_a, ?rty_a)) {
            alt (b) {
                case (ty_native_fn(?abi_b, ?args_b, ?rty_b)) {
1425
                    ret abi_a == abi_b &&
1426 1427 1428 1429 1430 1431 1432 1433
                        equal_fn(args_a, rty_a, args_b, rty_b);
                }
                case (_) { ret false; }
            }
        }
        case (ty_obj(?methods_a)) {
            alt (b) {
                case (ty_obj(?methods_b)) {
1434 1435
                    auto len = vec::len[method](methods_a);
                    if (len != vec::len[method](methods_b)) { ret false; }
1436 1437 1438
                    auto i = 0u;
                    while (i < len) {
                        auto m_a = methods_a.(i); auto m_b = methods_b.(i);
1439
                        if (m_a.proto != m_b.proto ||
1440
                                !str::eq(m_a.ident, m_b.ident) ||
P
Patrick Walton 已提交
1441 1442
                                !equal_fn(m_a.inputs, m_a.output,
                                          m_b.inputs, m_b.output)) {
1443 1444
                            ret false;
                        }
P
Patrick Walton 已提交
1445
                        i += 1u;
1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490
                    }
                    ret true;
                }
                case (_) { ret false; }
            }
        }
        case (ty_var(?v_a)) {
            alt (b) {
                case (ty_var(?v_b)) { ret v_a == v_b; }
                case (_) { ret false; }
            }
        }
        case (ty_local(?did_a)) {
            alt (b) {
                case (ty_local(?did_b)) { ret equal_def(did_a, did_b); }
                case (_) { ret false; }
            }
        }
        case (ty_param(?pid_a)) {
            alt (b) {
                case (ty_param(?pid_b)) { ret pid_a == pid_b; }
                case (_) { ret false; }
            }
        }
        case (ty_bound_param(?pid_a)) {
            alt (b) {
                case (ty_bound_param(?pid_b)) { ret pid_a == pid_b; }
                case (_) { ret false; }
            }
        }
        case (ty_type) {
            alt (b) {
                case (ty_type) { ret true; }
                case (_) { ret false; }
            }
        }
        case (ty_native) {
            alt (b) {
                case (ty_native) { ret true; }
                case (_) { ret false; }
            }
        }
    }
}

P
Patrick Walton 已提交
1491 1492
// An expensive type equality function. This function is private to this
// module.
1493 1494
//
// FIXME: Use structural comparison, but this loops forever and segfaults.
1495
fn eq_raw_ty(&raw_t a, &raw_t b) -> bool {
P
Patrick Walton 已提交
1496
    // Check hashes (fast path).
1497 1498 1499 1500
    if (a.hash != b.hash) {
        ret false;
    }

P
Patrick Walton 已提交
1501
    // Check canonical names.
1502
    alt (a.cname) {
P
Patrick Walton 已提交
1503
        case (none[str]) {
1504
            alt (b.cname) {
P
Patrick Walton 已提交
1505
                case (none[str]) { /* ok */ }
1506 1507 1508
                case (_) { ret false; }
            }
        }
P
Patrick Walton 已提交
1509
        case (some[str](?s_a)) {
1510
            alt (b.cname) {
P
Patrick Walton 已提交
1511
                case (some[str](?s_b)) {
1512
                    if (!str::eq(s_a, s_b)) { ret false; }
1513 1514 1515 1516
                }
                case (_) { ret false; }
            }
        }
P
Patrick Walton 已提交
1517
    }
1518

P
Patrick Walton 已提交
1519
    // Check structures.
1520
    ret equal_type_structures(a.struct, b.struct);
P
Patrick Walton 已提交
1521
}
1522

P
Patrick Walton 已提交
1523 1524
// This is the equality function the public should use. It works as long as
// the types are interned.
1525
fn eq_ty(&t a, &t b) -> bool { ret a == b; }
1526

1527

1528
// Type lookups
1529

1530 1531
fn ann_to_ty_param_substs_opt_and_ty(&node_type_table ntt, &ast::ann ann)
        -> ty_param_substs_opt_and_ty {
P
Patrick Walton 已提交
1532
    alt (ntt.(ann.id)) {
1533 1534 1535
        case (none[ty::ty_param_substs_opt_and_ty]) {
            log_err "ann_to_ty_param_substs_opt_and_ty() called on an " +
                "untyped node";
1536 1537
            fail;
        }
1538
        case (some[ty::ty_param_substs_opt_and_ty](?tpot)) { ret tpot; }
1539 1540 1541
    }
}

1542 1543 1544 1545 1546 1547 1548
fn ann_to_type(&node_type_table ntt, &ast::ann ann) -> t {
    ret ann_to_ty_param_substs_opt_and_ty(ntt, ann)._1;
}

fn ann_to_type_params(&node_type_table ntt, &ast::ann ann) -> vec[t] {
    alt (ann_to_ty_param_substs_opt_and_ty(ntt, ann)._0) {
        case (none[vec[t]]) {
1549
            let vec[t] result = [];
1550 1551 1552 1553 1554 1555
            ret result;
        }
        case (some[vec[t]](?tps)) { ret tps; }
    }
}

1556 1557 1558 1559 1560 1561
fn ann_has_type_params(&node_type_table ntt, &ast::ann ann) -> bool {
    auto tpt = ann_to_ty_param_substs_opt_and_ty(ntt, ann);
    ret !option::is_none[vec[t]](tpt._0);
}


1562 1563
// Returns the type of an annotation, with type parameter substitutions
// performed if applicable.
1564 1565
fn ann_to_monotype(&ctxt cx, ast::ann a) -> t {
    auto tpot = ann_to_ty_param_substs_opt_and_ty(cx.node_types, a);
1566 1567 1568 1569
    alt (tpot._0) {
        case (none[vec[t]]) { ret tpot._1; }
        case (some[vec[t]](?tps)) {
            ret substitute_type_params(cx, tps, tpot._1);
1570 1571 1572 1573
        }
    }
}

1574

P
Patrick Walton 已提交
1575 1576 1577
// Turns a type and optional type parameters into an annotation, using
// defaults for other fields.
fn mk_ann_type(uint node_id, t typ, option::t[vec[t]] tps) -> ast::ann {
1578
    ret rec(id=node_id, ty=typ, tps=tps);
P
Patrick Walton 已提交
1579 1580 1581
}

// Turns a type into an annotation, using defaults for other fields.
1582
fn triv_ann(uint node_id, t typ) -> ast::ann {
P
Patrick Walton 已提交
1583
    ret mk_ann_type(node_id, typ, none[vec[t]]);
1584 1585
}

1586 1587
// Creates a nil type annotation.
fn plain_ann(uint node_id, ctxt tcx) -> ast::ann {
P
Patrick Walton 已提交
1588
    ret triv_ann(node_id, mk_nil(tcx));
1589 1590 1591 1592
}

// Creates a _|_ type annotation.
fn bot_ann(uint node_id, ctxt tcx) -> ast::ann {
P
Patrick Walton 已提交
1593
    ret triv_ann(node_id, mk_bot(tcx));
1594 1595 1596
}


1597
// Returns the number of distinct type parameters in the given type.
1598 1599
fn count_ty_params(&ctxt cx, t ty) -> uint {
    fn counter(&ctxt cx, @mutable vec[uint] param_indices, t ty) {
1600
        alt (struct(cx, ty)) {
1601 1602 1603 1604 1605
            case (ty_param(?param_idx)) {
                auto seen = false;
                for (uint other_param_idx in *param_indices) {
                    if (param_idx == other_param_idx) {
                        seen = true;
1606
                    }
1607
                }
1608
                if (!seen) {
1609
                    *param_indices += [param_idx];
1610
                }
1611
            }
1612
            case (_) { /* fall through */ }
1613 1614 1615
        }
    }

1616
    let vec[uint] v = [];    // FIXME: typechecker botch
1617
    let @mutable vec[uint] param_indices = @mutable v;
1618 1619
    auto f = bind counter(cx, param_indices, _);
    walk_ty(cx, f, ty);
1620
    ret vec::len[uint](*param_indices);
1621 1622
}

1623
fn type_contains_vars(&ctxt cx, &t typ) -> bool {
1624
    ret interner::get[raw_t](*cx.ts, typ).has_vars;
1625 1626
}

1627
fn type_contains_locals(&ctxt cx, &t typ) -> bool {
1628
    ret interner::get[raw_t](*cx.ts, typ).has_locals;
1629 1630
}

1631
fn type_contains_params(&ctxt cx, &t typ) -> bool {
1632
    ret interner::get[raw_t](*cx.ts, typ).has_params;
1633 1634
}

1635
fn type_contains_bound_params(&ctxt cx, &t typ) -> bool {
1636
    ret interner::get[raw_t](*cx.ts, typ).has_bound_params;
1637 1638
}

G
Graydon Hoare 已提交
1639 1640
// Type accessors for substructures of types

1641
fn ty_fn_args(&ctxt cx, &t fty) -> vec[arg] {
1642
    alt (struct(cx, fty)) {
1643
        case (ty::ty_fn(_, ?a, _, _)) { ret a; }
1644
        case (ty::ty_native_fn(_, ?a, _)) { ret a; }
1645
    }
1646
    fail;
1647 1648
}

1649
fn ty_fn_proto(&ctxt cx, &t fty) -> ast::proto {
1650
    alt (struct(cx, fty)) {
1651
        case (ty::ty_fn(?p, _, _, _)) { ret p; }
1652
    }
1653
    fail;
G
Graydon Hoare 已提交
1654 1655
}

1656
fn ty_fn_abi(&ctxt cx, &t fty) -> ast::native_abi {
1657
    alt (struct(cx, fty)) {
1658
        case (ty::ty_native_fn(?a, _, _)) { ret a; }
1659 1660 1661 1662
    }
    fail;
}

1663
fn ty_fn_ret(&ctxt cx, &t fty) -> t {
1664
    alt (struct(cx, fty)) {
1665
        case (ty::ty_fn(_, _, ?r, _)) { ret r; }
1666
        case (ty::ty_native_fn(_, _, ?r)) { ret r; }
1667
    }
1668
    fail;
G
Graydon Hoare 已提交
1669 1670
}

1671
fn is_fn_ty(&ctxt cx, &t fty) -> bool {
1672
    alt (struct(cx, fty)) {
1673
        case (ty::ty_fn(_, _, _, _)) { ret true; }
1674
        case (ty::ty_native_fn(_, _, _)) { ret true; }
1675 1676 1677
        case (_) { ret false; }
    }
    ret false;
G
Graydon Hoare 已提交
1678 1679 1680
}


1681 1682
// Type accessors for AST nodes

1683 1684
// Given an item, returns the associated type as well as the number of type
// parameters it has.
1685 1686
fn native_item_ty(&node_type_table ntt, &@ast::native_item it)
        -> ty_param_count_and_ty {
1687
    auto ty_param_count;
1688 1689
    auto result_ty;
    alt (it.node) {
1690
        case (ast::native_item_fn(_, _, _, ?tps, _, ?ann)) {
1691
            ty_param_count = vec::len[ast::ty_param](tps);
1692
            result_ty = ann_to_type(ntt, ann);
1693 1694
        }
    }
1695
    ret tup(ty_param_count, result_ty);
1696 1697
}

1698
fn item_ty(&node_type_table ntt, &@ast::item it) -> ty_param_count_and_ty {
1699
    auto ty_param_count;
1700 1701
    auto result_ty;
    alt (it.node) {
1702
        case (ast::item_const(_, _, _, _, ?ann)) {
1703
            ty_param_count = 0u;
1704
            result_ty = ann_to_type(ntt, ann);
1705
        }
1706
        case (ast::item_fn(_, _, ?tps, _, ?ann)) {
1707
            ty_param_count = vec::len[ast::ty_param](tps);
1708
            result_ty = ann_to_type(ntt, ann);
1709
        }
1710
        case (ast::item_mod(_, _, _)) {
1711 1712
            fail;   // modules are typeless
        }
1713
        case (ast::item_ty(_, _, ?tps, _, ?ann)) {
1714
            ty_param_count = vec::len[ast::ty_param](tps);
1715
            result_ty = ann_to_type(ntt, ann);
1716
        }
1717
        case (ast::item_tag(_, _, ?tps, ?did, ?ann)) {
1718
            ty_param_count = vec::len[ast::ty_param](tps);
1719
            result_ty = ann_to_type(ntt, ann);
1720
        }
1721
        case (ast::item_obj(_, _, ?tps, _, ?ann)) {
1722
            ty_param_count = vec::len[ast::ty_param](tps);
1723
            result_ty = ann_to_type(ntt, ann);
1724 1725 1726
        }
    }

1727
    ret tup(ty_param_count, result_ty);
1728 1729
}

1730
fn stmt_ty(&ctxt cx, &@ast::stmt s) -> t {
1731
    alt (s.node) {
1732
        case (ast::stmt_expr(?e,_)) {
1733
            ret expr_ty(cx, e);
1734 1735
        }
        case (_) {
1736
            ret mk_nil(cx);
1737 1738 1739 1740
        }
    }
}

1741
fn block_ty(&ctxt cx, &ast::block b) -> t {
1742
    alt (b.node.expr) {
1743
        case (some[@ast::expr](?e)) { ret expr_ty(cx, e); }
1744
        case (none[@ast::expr])     { ret mk_nil(cx); }
1745 1746 1747
    }
}

1748 1749
// Returns the type of a pattern as a monotype. Like @expr_ty, this function
// doesn't provide type parameter substitutions.
1750 1751
fn pat_ty(&ctxt cx, &@ast::pat pat) -> t {
    ret ann_to_monotype(cx, pat_ann(pat));
1752 1753
}

1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773
fn item_ann(&@ast::item it) -> ast::ann {
    alt (it.node) {
        case (ast::item_const(_,_,_,_,?a)) { ret a; }
        case (ast::item_fn(_,_,_,_,?a)) { ret a; }
        case (ast::item_mod(_,_,_)) {
            log_err "a module was passed to item_ann(), " +
                "but modules haven't annotations";
            fail;
        }
        case (ast::item_native_mod(_,_,_)) {
            log_err "a native module was passed to item_ann(), " +
                "but native modules haven't annotations";
            fail;
        }
        case (ast::item_ty(_,_,_,_,?a)) { ret a; }
        case (ast::item_tag(_,_,_,_,?a)) { ret a; }
        case (ast::item_obj(_,_,_,_,?a)) { ret a; }
    }
}

1774
fn expr_ann(&@ast::expr e) -> ast::ann {
1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808
    alt (e.node) {
        case (ast::expr_vec(_,_,?a)) { ret a; }
        case (ast::expr_tup(_,?a)) { ret a; }
        case (ast::expr_rec(_,_,?a)) { ret a; }
        case (ast::expr_call(_,_,?a)) { ret a; }
        case (ast::expr_bind(_,_,?a)) { ret a; }
        case (ast::expr_binary(_,_,_,?a)) { ret a; }
        case (ast::expr_unary(_,_,?a)) { ret a; }
        case (ast::expr_lit(_,?a)) { ret a; }
        case (ast::expr_cast(_,_,?a)) { ret a; }
        case (ast::expr_if(_,_,_,?a)) { ret a; }
        case (ast::expr_while(_,_,?a)) { ret a; }
        case (ast::expr_for(_,_,_,?a)) { ret a; }
        case (ast::expr_for_each(_,_,_,?a)) { ret a; }
        case (ast::expr_do_while(_,_,?a)) { ret a; }
        case (ast::expr_alt(_,_,?a)) { ret a; }
        case (ast::expr_block(_,?a)) { ret a; }
        case (ast::expr_assign(_,_,?a)) { ret a; }
        case (ast::expr_assign_op(_,_,_,?a)) { ret a; }
        case (ast::expr_send(_,_,?a)) { ret a; }
        case (ast::expr_recv(_,_,?a)) { ret a; }
        case (ast::expr_field(_,_,?a)) { ret a; }
        case (ast::expr_index(_,_,?a)) { ret a; }
        case (ast::expr_path(_,?a)) { ret a; }
        case (ast::expr_ext(_,_,_,_,?a)) { ret a; }
        case (ast::expr_fail(?a)) { ret a; }
        case (ast::expr_ret(_,?a)) { ret a; }
        case (ast::expr_put(_,?a)) { ret a; }
        case (ast::expr_be(_,?a)) { ret a; }
        case (ast::expr_log(_,_,?a)) { ret a; }
        case (ast::expr_assert(_,?a)) { ret a; }
        case (ast::expr_check(_,?a)) { ret a; }
        case (ast::expr_port(?a)) { ret a; }
        case (ast::expr_chan(_,?a)) { ret a; }
1809
        case (ast::expr_anon_obj(_,_,_,?a)) { ret a; }
1810 1811 1812
        case (ast::expr_break(?a)) { ret a; }
        case (ast::expr_cont(?a)) { ret a; }
        case (ast::expr_self_method(_, ?a)) { ret a; }
1813
        case (ast::expr_spawn(_, _, _, _, ?a)) { ret a; }
1814 1815 1816
    }
}

1817 1818 1819 1820 1821 1822
// Returns the type of an expression as a monotype.
//
// NB: This type doesn't provide type parameter substitutions; e.g. if you
// ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
// instead of "fn(&T) -> T with T = int". If this isn't what you want, see
// expr_ty_params_and_ty() below.
1823 1824
fn expr_ty(&ctxt cx, &@ast::expr expr) -> t {
    ret ann_to_monotype(cx, expr_ann(expr));
1825 1826
}

1827
fn expr_ty_params_and_ty(&ctxt cx, &@ast::expr expr)
1828
        -> tup(vec[t], t) {
1829 1830
    auto a = expr_ann(expr);

1831 1832
    ret tup(ann_to_type_params(cx.node_types, a),
            ann_to_type(cx.node_types, a));
1833 1834
}

1835
fn expr_has_ty_params(&node_type_table ntt, &@ast::expr expr) -> bool {
1836
    ret ann_has_type_params(ntt, expr_ann(expr));
1837 1838
}

1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858
fn stmt_ann(&@ast::stmt s) -> ast::ann {
    alt (s.node) {
        case (ast::stmt_decl(_, ?a)) { ret a; }
        case (ast::stmt_expr(_, ?a)) { ret a; }
        case (ast::stmt_crate_directive(_)) {
            log_err "ty::stmt_ann(): crate directive found";
            fail;
        }
    }
}

fn pat_ann(&@ast::pat p) -> ast::ann {
    alt (p.node) {
        case (ast::pat_wild(?a))        { ret a; }
        case (ast::pat_bind(_, _, ?a))  { ret a; }
        case (ast::pat_lit(_, ?a))      { ret a; }
        case (ast::pat_tag(_, _, ?a))   { ret a; }
    }
}

1859

1860 1861
// Expression utilities

1862 1863
fn field_num(&session::session sess, &span sp,
             &ast::ident id) -> uint {
1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878
    let uint accum = 0u;
    let uint i = 0u;
    for (u8 c in id) {
        if (i == 0u) {
            if (c != ('_' as u8)) {
                sess.span_err(sp,
                              "bad numeric field on tuple: "
                              + "missing leading underscore");
            }
        } else {
            if (('0' as u8) <= c && c <= ('9' as u8)) {
                accum *= 10u;
                accum += (c as uint) - ('0' as uint);
            } else {
                auto s = "";
1879
                s += str::unsafe_from_byte(c);
1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890
                sess.span_err(sp,
                              "bad numeric field on tuple: "
                              + " non-digit character: "
                              + s);
            }
        }
        i += 1u;
    }
    ret accum;
}

1891 1892
fn field_idx(&session::session sess, &span sp,
             &ast::ident id, &vec[field] fields) -> uint {
1893 1894
    let uint i = 0u;
    for (field f in fields) {
1895
        if (str::eq(f.ident, id)) {
1896 1897 1898 1899 1900 1901 1902 1903
            ret i;
        }
        i += 1u;
    }
    sess.span_err(sp, "unknown field '" + id + "' of record");
    fail;
}

1904 1905
fn method_idx(&session::session sess, &span sp,
              &ast::ident id, &vec[method] meths) -> uint {
1906 1907
    let uint i = 0u;
    for (method m in meths) {
1908
        if (str::eq(m.ident, id)) {
1909 1910 1911 1912 1913 1914 1915 1916
            ret i;
        }
        i += 1u;
    }
    sess.span_err(sp, "unknown method '" + id + "' of obj");
    fail;
}

1917
fn sort_methods(&vec[method] meths) -> vec[method] {
1918
    fn method_lteq(&method a, &method b) -> bool {
1919
        ret str::lteq(a.ident, b.ident);
1920 1921
    }

1922
    ret std::sort::merge_sort[method](bind method_lteq(_,_), meths);
1923 1924
}

1925
fn is_lval(&@ast::expr expr) -> bool {
1926
    alt (expr.node) {
1927 1928 1929 1930
        case (ast::expr_field(_,_,_))    { ret true;  }
        case (ast::expr_index(_,_,_))    { ret true;  }
        case (ast::expr_path(_,_))       { ret true;  }
        case (ast::expr_unary(ast::deref,_,_))  { ret true; }
1931 1932 1933 1934
        case (_)                        { ret false; }
    }
}

1935 1936 1937 1938
// Type unification via Robinson's algorithm (Robinson 1965). Implemented as
// described in Hoder and Voronkov:
//
//     http://www.cs.man.ac.uk/~hoderk/ubench/unification_full.pdf
1939

1940
mod unify {
1941
    tag result {
1942 1943
        ures_ok(t);
        ures_err(type_err, t, t);
1944 1945
    }

1946 1947 1948 1949 1950
    tag set_result {
        usr_ok(vec[t]);
        usr_err(type_err, t, t);
    }

1951 1952
    type bindings[T] = rec(ufind::ufind sets,
                           hashmap[T,uint] ids,
1953
                           mutable vec[mutable option::t[t]] types);
1954

1955 1956
    fn mk_bindings[T](map::hashfn[T] hasher, map::eqfn[T] eqer)
            -> @bindings[T] {
1957
        let vec[mutable option::t[t]] types = [mutable];
1958
        ret @rec(sets=ufind::make(),
1959
                 ids=map::mk_hashmap[T,uint](hasher, eqer),
1960
                 mutable types=types);
1961 1962
    }

1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987
    fn record_binding[T](&@ctxt cx, &@bindings[T] bindings, &T key, t typ)
            -> result {
        auto n = get_or_create_set[T](bindings, key);

        auto result_type = typ;
        if (n < vec::len[option::t[t]](bindings.types)) {
            alt (bindings.types.(n)) {
                case (some[t](?old_type)) {
                    alt (unify_step(cx, old_type, typ)) {
                        case (ures_ok(?unified_type)) {
                            result_type = unified_type;
                        }
                        case (?res) { ret res; }
                    }
                }
                case (none[t]) { /* fall through */ }
            }
        }

        vec::grow_set[option::t[t]](bindings.types, n, none[t],
                                    some[t](result_type));

        ret ures_ok(typ);
    }

1988
    type ctxt = rec(@bindings[int] bindings,
1989
                    unify_handler handler,
1990
                    ty_ctxt tcx);
1991

1992 1993 1994 1995 1996 1997 1998 1999
    // Wraps the given type in an appropriate cname.
    //
    // TODO: This doesn't do anything yet. We should carry the cname up from
    // the expected and/or actual types when unification results in a type
    // identical to one or both of the two. The precise algorithm for this is
    // something we'll probably need to develop over time.

    // Simple structural type comparison.
2000
    fn struct_cmp(@ctxt cx, t expected, t actual) -> result {
2001
        if (struct(cx.tcx, expected) == struct(cx.tcx, actual)) {
2002 2003 2004 2005 2006 2007
            ret ures_ok(expected);
        }

        ret ures_err(terr_mismatch, expected, actual);
    }

2008
    // Unifies two mutability flags.
2009 2010
    fn unify_mut(ast::mutability expected, ast::mutability actual)
            -> option::t[ast::mutability] {
2011
        if (expected == actual) {
2012
            ret some[ast::mutability](expected);
2013
        }
2014 2015
        if (expected == ast::maybe_mut) {
            ret some[ast::mutability](actual);
2016
        }
2017 2018
        if (actual == ast::maybe_mut) {
            ret some[ast::mutability](expected);
2019
        }
2020
        ret none[ast::mutability];
2021 2022
    }

2023
    tag fn_common_res {
2024
        fn_common_res_err(result);
2025
        fn_common_res_ok(vec[arg], t);
2026
    }
G
Graydon Hoare 已提交
2027

2028 2029 2030 2031 2032
    fn unify_fn_common(&@ctxt cx,
                       &t expected,
                       &t actual,
                       &vec[arg] expected_inputs, &t expected_output,
                       &vec[arg] actual_inputs, &t actual_output)
2033
        -> fn_common_res {
2034 2035
        auto expected_len = vec::len[arg](expected_inputs);
        auto actual_len = vec::len[arg](actual_inputs);
2036
        if (expected_len != actual_len) {
2037 2038
            ret fn_common_res_err(ures_err(terr_arg_count,
                                           expected, actual));
2039
        }
G
Graydon Hoare 已提交
2040

2041
        // TODO: as above, we should have an iter2 iterator.
2042
        let vec[arg] result_ins = [];
2043 2044 2045 2046 2047
        auto i = 0u;
        while (i < expected_len) {
            auto expected_input = expected_inputs.(i);
            auto actual_input = actual_inputs.(i);

2048
            // Unify the result modes. "mo_either" unifies with both modes.
2049
            auto result_mode;
2050 2051 2052 2053 2054
            if (expected_input.mode == mo_either) {
                result_mode = actual_input.mode;
            } else if (actual_input.mode == mo_either) {
                result_mode = expected_input.mode;
            } else if (expected_input.mode != actual_input.mode) {
2055
                // FIXME this is the wrong error
2056 2057
                ret fn_common_res_err(ures_err(terr_arg_count,
                                               expected, actual));
2058
            } else {
2059
                result_mode = expected_input.mode;
2060
            }
G
Graydon Hoare 已提交
2061

2062
            auto result = unify_step(cx, actual_input.ty, expected_input.ty);
G
Graydon Hoare 已提交
2063

2064 2065
            alt (result) {
                case (ures_ok(?rty)) {
2066
                    result_ins += [rec(mode=result_mode, ty=rty)];
2067 2068 2069
                }

                case (_) {
2070
                    ret fn_common_res_err(result);
2071 2072
                }
            }
G
Graydon Hoare 已提交
2073

2074
            i += 1u;
G
Graydon Hoare 已提交
2075 2076
        }

2077
        // Check the output.
2078
        auto result = unify_step(cx, expected_output, actual_output);
2079 2080
        alt (result) {
            case (ures_ok(?rty)) {
2081
                ret fn_common_res_ok(result_ins, rty);
2082 2083 2084
            }

            case (_) {
2085
                ret fn_common_res_err(result);
2086
            }
G
Graydon Hoare 已提交
2087
        }
2088
    }
G
Graydon Hoare 已提交
2089

2090
    fn unify_fn(&@ctxt cx,
2091 2092
                &ast::proto e_proto,
                &ast::proto a_proto,
2093 2094 2095
                &t expected,
                &t actual,
                &vec[arg] expected_inputs, &t expected_output,
2096 2097
                &vec[arg] actual_inputs, &t actual_output,
                &controlflow expected_cf, &controlflow actual_cf)
2098
        -> result {
G
Graydon Hoare 已提交
2099

2100 2101 2102
        if (e_proto != a_proto) {
            ret ures_err(terr_mismatch, expected, actual);
        }
2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121
        alt (expected_cf) {
            case (ast::return) { } // ok
            case (ast::noreturn) {
                alt (actual_cf) {
                    case (ast::noreturn) {
                        // ok
                    }
                    case (_) {
                        /* even though typestate checking is mostly
                           responsible for checking control flow annotations,
                           this check is necessary to ensure that the
                           annotation in an object method matches the
                           declared object type */
                        ret ures_err(terr_controlflow_mismatch,
                                     expected, actual);
                    }
                }
            }
        }
2122 2123
        auto t = unify_fn_common(cx, expected, actual,
                                 expected_inputs, expected_output,
2124 2125 2126 2127 2128 2129
                                 actual_inputs, actual_output);
        alt (t) {
            case (fn_common_res_err(?r)) {
                ret r;
            }
            case (fn_common_res_ok(?result_ins, ?result_out)) {
2130 2131
                auto t2 = mk_fn(cx.tcx, e_proto, result_ins, result_out,
                                actual_cf);
2132 2133 2134 2135 2136
                ret ures_ok(t2);
            }
        }
    }

2137
    fn unify_native_fn(&@ctxt cx,
2138 2139
                       &ast::native_abi e_abi,
                       &ast::native_abi a_abi,
2140 2141 2142 2143
                       &t expected,
                       &t actual,
                       &vec[arg] expected_inputs, &t expected_output,
                       &vec[arg] actual_inputs, &t actual_output)
2144
        -> result {
2145 2146 2147 2148
        if (e_abi != a_abi) {
            ret ures_err(terr_mismatch, expected, actual);
        }

2149 2150
        auto t = unify_fn_common(cx, expected, actual,
                                 expected_inputs, expected_output,
2151 2152 2153 2154 2155 2156
                                 actual_inputs, actual_output);
        alt (t) {
            case (fn_common_res_err(?r)) {
                ret r;
            }
            case (fn_common_res_ok(?result_ins, ?result_out)) {
2157
                auto t2 = mk_native_fn(cx.tcx, e_abi, result_ins,
2158
                                       result_out);
2159 2160 2161
                ret ures_ok(t2);
            }
        }
G
Graydon Hoare 已提交
2162 2163
    }

2164 2165 2166 2167 2168
    fn unify_obj(&@ctxt cx,
                 &t expected,
                 &t actual,
                 &vec[method] expected_meths,
                 &vec[method] actual_meths) -> result {
2169
      let vec[method] result_meths = [];
G
Graydon Hoare 已提交
2170
      let uint i = 0u;
2171 2172
      let uint expected_len = vec::len[method](expected_meths);
      let uint actual_len = vec::len[method](actual_meths);
G
Graydon Hoare 已提交
2173 2174 2175 2176 2177 2178 2179 2180

      if (expected_len != actual_len) {
        ret ures_err(terr_meth_count, expected, actual);
      }

      while (i < expected_len) {
        auto e_meth = expected_meths.(i);
        auto a_meth = actual_meths.(i);
2181
        if (! str::eq(e_meth.ident, a_meth.ident)) {
G
Graydon Hoare 已提交
2182 2183 2184
          ret ures_err(terr_obj_meths(e_meth.ident, a_meth.ident),
                       expected, actual);
        }
2185
        auto r = unify_fn(cx,
2186
                          e_meth.proto, a_meth.proto,
2187
                          expected, actual,
G
Graydon Hoare 已提交
2188
                          e_meth.inputs, e_meth.output,
2189 2190
                          a_meth.inputs, a_meth.output,
                          e_meth.cf, a_meth.cf);
B
Brian Anderson 已提交
2191 2192
        alt (r) {
            case (ures_ok(?tfn)) {
2193
                alt (struct(cx.tcx, tfn)) {
2194
                    case (ty_fn(?proto, ?ins, ?out, ?cf)) {
2195
                        result_meths += [rec(inputs = ins,
2196 2197 2198
                                             output = out,
                                             cf     = cf
                                             with e_meth)];
B
Brian Anderson 已提交
2199 2200 2201 2202 2203 2204
                    }
                }
            }
            case (_) {
                ret r;
            }
G
Graydon Hoare 已提交
2205 2206 2207
        }
        i += 1u;
      }
2208
      auto t = mk_obj(cx.tcx, result_meths);
G
Graydon Hoare 已提交
2209 2210 2211
      ret ures_ok(t);
    }

2212
    fn get_or_create_set[T](&@bindings[T] bindings, &T key) -> uint {
2213
        auto set_num;
2214
        alt (bindings.ids.find(key)) {
2215
            case (none[uint]) {
2216 2217
                set_num = ufind::make_set(bindings.sets);
                bindings.ids.insert(key, set_num);
2218 2219
            }
            case (some[uint](?n)) { set_num = n; }
2220
        }
2221
        ret set_num;
2222 2223
    }

2224
    fn unify_step(&@ctxt cx, &t expected, &t actual) -> result {
2225 2226 2227
        // TODO: rewrite this using tuple pattern matching when available, to
        // avoid all this rightward drift and spikiness.

2228 2229 2230
        // TODO: occurs check, to make sure we don't loop forever when
        // unifying e.g. 'a and option['a]

2231 2232 2233
        // Fast path.
        if (eq_ty(expected, actual)) { ret ures_ok(expected); }

2234
        alt (struct(cx.tcx, actual)) {
2235 2236
            // If the RHS is a variable type, then just do the appropriate
            // binding.
2237
            case (ty::ty_var(?actual_id)) {
2238 2239
                auto actual_n = get_or_create_set[int](cx.bindings,
                                                       actual_id);
2240
                alt (struct(cx.tcx, expected)) {
2241
                    case (ty::ty_var(?expected_id)) {
2242 2243
                        auto expected_n = get_or_create_set[int](cx.bindings,
                                                                 expected_id);
2244
                        ufind::union(cx.bindings.sets, expected_n, actual_n);
2245 2246 2247 2248
                    }

                    case (_) {
                        // Just bind the type variable to the expected type.
2249 2250 2251 2252
                        alt (record_binding[int](cx, cx.bindings, actual_id,
                                                 expected)) {
                            case (ures_ok(_)) { /* fall through */ }
                            case (?res) { ret res; }
2253 2254 2255 2256
                        }
                    }
                }
                ret ures_ok(actual);
2257
            }
2258
            case (ty::ty_local(?actual_id)) {
2259
                auto result_ty;
2260
                alt (cx.handler.resolve_local(actual_id)) {
2261 2262
                    case (none[t]) { result_ty = expected; }
                    case (some[t](?actual_ty)) {
2263
                        auto result = unify_step(cx, expected, actual_ty);
2264 2265 2266 2267
                        alt (result) {
                            case (ures_ok(?rty)) { result_ty = rty; }
                            case (_) { ret result; }
                        }
2268 2269
                    }
                }
2270

2271
                cx.handler.record_local(actual_id, result_ty);
2272
                ret ures_ok(result_ty);
2273
            }
2274
            case (ty::ty_bound_param(?actual_id)) {
2275
                alt (struct(cx.tcx, expected)) {
2276
                    case (ty::ty_local(_)) {
2277
                        log_err "TODO: bound param unifying with local";
2278 2279
                        fail;
                    }
2280 2281

                    case (_) {
2282
                        ret cx.handler.record_param(actual_id, expected);
2283 2284
                    }
                }
2285
            }
2286 2287 2288
            case (_) { /* empty */ }
        }

2289
        alt (struct(cx.tcx, expected)) {
2290
            case (ty::ty_nil)        { ret struct_cmp(cx, expected, actual); }
2291 2292
            // _|_ unifies with anything
            case (ty::ty_bot)        { ret ures_ok(expected);                }
2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304
            case (ty::ty_bool)       { ret struct_cmp(cx, expected, actual); }
            case (ty::ty_int)        { ret struct_cmp(cx, expected, actual); }
            case (ty::ty_uint)       { ret struct_cmp(cx, expected, actual); }
            case (ty::ty_machine(_)) { ret struct_cmp(cx, expected, actual); }
            case (ty::ty_float)      { ret struct_cmp(cx, expected, actual); }
            case (ty::ty_char)       { ret struct_cmp(cx, expected, actual); }
            case (ty::ty_str)        { ret struct_cmp(cx, expected, actual); }
            case (ty::ty_type)       { ret struct_cmp(cx, expected, actual); }
            case (ty::ty_native)     { ret struct_cmp(cx, expected, actual); }
            case (ty::ty_param(_))   { ret struct_cmp(cx, expected, actual); }

            case (ty::ty_tag(?expected_id, ?expected_tps)) {
2305
                alt (struct(cx.tcx, actual)) {
2306
                    case (ty::ty_tag(?actual_id, ?actual_tps)) {
2307 2308 2309
                        if (expected_id._0 != actual_id._0 ||
                                expected_id._1 != actual_id._1) {
                            ret ures_err(terr_mismatch, expected, actual);
2310
                        }
2311 2312

                        // TODO: factor this cruft out, see the TODO in the
2313
                        // ty::ty_tup case
2314
                        let vec[t] result_tps = [];
2315
                        auto i = 0u;
2316
                        auto expected_len = vec::len[t](expected_tps);
2317 2318 2319 2320
                        while (i < expected_len) {
                            auto expected_tp = expected_tps.(i);
                            auto actual_tp = actual_tps.(i);

2321
                            auto result = unify_step(cx,
2322
                                                     expected_tp,
2323
                                                     actual_tp);
2324 2325 2326

                            alt (result) {
                                case (ures_ok(?rty)) {
2327
                                    vec::push[t](result_tps, rty);
2328 2329 2330 2331 2332 2333 2334 2335 2336
                                }
                                case (_) {
                                    ret result;
                                }
                            }

                            i += 1u;
                        }

2337
                        ret ures_ok(mk_tag(cx.tcx, expected_id, result_tps));
2338 2339 2340 2341 2342 2343 2344
                    }
                    case (_) { /* fall through */ }
                }

                ret ures_err(terr_mismatch, expected, actual);
            }

2345
            case (ty::ty_box(?expected_mt)) {
2346
                alt (struct(cx.tcx, actual)) {
2347
                    case (ty::ty_box(?actual_mt)) {
2348 2349
                        auto mut;
                        alt (unify_mut(expected_mt.mut, actual_mt.mut)) {
2350
                            case (none[ast::mutability]) {
2351 2352 2353
                                ret ures_err(terr_box_mutability, expected,
                                             actual);
                            }
2354
                            case (some[ast::mutability](?m)) { mut = m; }
2355 2356
                        }

2357
                        auto result = unify_step(cx,
2358
                                                 expected_mt.ty,
2359
                                                 actual_mt.ty);
2360 2361
                        alt (result) {
                            case (ures_ok(?result_sub)) {
2362
                                auto mt = rec(ty=result_sub, mut=mut);
2363
                                ret ures_ok(mk_box(cx.tcx, mt));
2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376
                            }
                            case (_) {
                                ret result;
                            }
                        }
                    }

                    case (_) {
                        ret ures_err(terr_mismatch, expected, actual);
                    }
                }
            }

2377
            case (ty::ty_vec(?expected_mt)) {
2378
                alt (struct(cx.tcx, actual)) {
2379
                    case (ty::ty_vec(?actual_mt)) {
2380 2381
                        auto mut;
                        alt (unify_mut(expected_mt.mut, actual_mt.mut)) {
2382
                            case (none[ast::mutability]) {
2383 2384 2385
                                ret ures_err(terr_vec_mutability, expected,
                                             actual);
                            }
2386
                            case (some[ast::mutability](?m)) { mut = m; }
2387 2388
                        }

2389
                        auto result = unify_step(cx,
2390
                                                 expected_mt.ty,
2391
                                                 actual_mt.ty);
2392 2393
                        alt (result) {
                            case (ures_ok(?result_sub)) {
2394
                                auto mt = rec(ty=result_sub, mut=mut);
2395
                                ret ures_ok(mk_vec(cx.tcx, mt));
2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408
                            }
                            case (_) {
                                ret result;
                            }
                        }
                    }

                    case (_) {
                        ret ures_err(terr_mismatch, expected, actual);
                   }
                }
            }

2409
            case (ty::ty_port(?expected_sub)) {
2410
                alt (struct(cx.tcx, actual)) {
2411
                    case (ty::ty_port(?actual_sub)) {
2412
                        auto result = unify_step(cx,
2413
                                                 expected_sub,
2414
                                                 actual_sub);
2415 2416
                        alt (result) {
                            case (ures_ok(?result_sub)) {
2417
                                ret ures_ok(mk_port(cx.tcx, result_sub));
2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430
                            }
                            case (_) {
                                ret result;
                            }
                        }
                    }

                    case (_) {
                        ret ures_err(terr_mismatch, expected, actual);
                    }
                }
            }

2431
            case (ty::ty_chan(?expected_sub)) {
2432
                alt (struct(cx.tcx, actual)) {
2433
                    case (ty::ty_chan(?actual_sub)) {
2434
                        auto result = unify_step(cx,
2435
                                                 expected_sub,
2436
                                                 actual_sub);
2437 2438
                        alt (result) {
                            case (ures_ok(?result_sub)) {
2439
                                ret ures_ok(mk_chan(cx.tcx, result_sub));
2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452
                            }
                            case (_) {
                                ret result;
                            }
                        }
                    }

                    case (_) {
                        ret ures_err(terr_mismatch, expected, actual);
                    }
                }
            }

2453
            case (ty::ty_tup(?expected_elems)) {
2454
                alt (struct(cx.tcx, actual)) {
2455
                    case (ty::ty_tup(?actual_elems)) {
2456 2457
                        auto expected_len = vec::len[ty::mt](expected_elems);
                        auto actual_len = vec::len[ty::mt](actual_elems);
2458 2459 2460 2461 2462 2463 2464 2465
                        if (expected_len != actual_len) {
                            auto err = terr_tuple_size(expected_len,
                                                       actual_len);
                            ret ures_err(err, expected, actual);
                        }

                        // TODO: implement an iterator that can iterate over
                        // two arrays simultaneously.
2466
                        let vec[ty::mt] result_elems = [];
2467 2468 2469 2470
                        auto i = 0u;
                        while (i < expected_len) {
                            auto expected_elem = expected_elems.(i);
                            auto actual_elem = actual_elems.(i);
2471 2472 2473 2474

                            auto mut;
                            alt (unify_mut(expected_elem.mut,
                                           actual_elem.mut)) {
2475
                                case (none[ast::mutability]) {
2476 2477 2478
                                    auto err = terr_tuple_mutability;
                                    ret ures_err(err, expected, actual);
                                }
2479
                                case (some[ast::mutability](?m)) { mut = m; }
2480 2481
                            }

2482
                            auto result = unify_step(cx,
2483
                                                     expected_elem.ty,
2484
                                                     actual_elem.ty);
2485 2486
                            alt (result) {
                                case (ures_ok(?rty)) {
2487
                                    auto mt = rec(ty=rty, mut=mut);
2488
                                    result_elems += [mt];
2489 2490 2491 2492 2493 2494 2495 2496 2497
                                }
                                case (_) {
                                    ret result;
                                }
                            }

                            i += 1u;
                        }

2498
                        ret ures_ok(mk_tup(cx.tcx, result_elems));
2499 2500 2501 2502 2503 2504 2505 2506
                    }

                    case (_) {
                        ret ures_err(terr_mismatch, expected, actual);
                    }
                }
            }

2507
            case (ty::ty_rec(?expected_fields)) {
2508
                alt (struct(cx.tcx, actual)) {
2509
                    case (ty::ty_rec(?actual_fields)) {
2510 2511
                        auto expected_len = vec::len[field](expected_fields);
                        auto actual_len = vec::len[field](actual_fields);
2512 2513 2514 2515 2516 2517 2518 2519
                        if (expected_len != actual_len) {
                            auto err = terr_record_size(expected_len,
                                                        actual_len);
                            ret ures_err(err, expected, actual);
                        }

                        // TODO: implement an iterator that can iterate over
                        // two arrays simultaneously.
2520
                        let vec[field] result_fields = [];
2521 2522 2523 2524
                        auto i = 0u;
                        while (i < expected_len) {
                            auto expected_field = expected_fields.(i);
                            auto actual_field = actual_fields.(i);
2525 2526 2527 2528

                            auto mut;
                            alt (unify_mut(expected_field.mt.mut,
                                           actual_field.mt.mut)) {
2529
                                case (none[ast::mutability]) {
2530 2531 2532
                                    ret ures_err(terr_record_mutability,
                                                 expected, actual);
                                }
2533
                                case (some[ast::mutability](?m)) { mut = m; }
2534 2535
                            }

2536
                            if (!str::eq(expected_field.ident,
2537
                                         actual_field.ident)) {
2538 2539 2540 2541 2542 2543
                                auto err =
                                    terr_record_fields(expected_field.ident,
                                                       actual_field.ident);
                                ret ures_err(err, expected, actual);
                            }

2544
                            auto result = unify_step(cx,
2545
                                                     expected_field.mt.ty,
2546
                                                     actual_field.mt.ty);
2547 2548
                            alt (result) {
                                case (ures_ok(?rty)) {
2549
                                    auto mt = rec(ty=rty, mut=mut);
2550
                                    vec::push[field]
2551
                                        (result_fields,
2552
                                         rec(mt=mt with expected_field));
2553 2554 2555 2556 2557 2558 2559 2560 2561
                                }
                                case (_) {
                                    ret result;
                                }
                            }

                            i += 1u;
                        }

2562
                        ret ures_ok(mk_rec(cx.tcx, result_fields));
2563 2564 2565 2566 2567 2568 2569 2570
                    }

                    case (_) {
                        ret ures_err(terr_mismatch, expected, actual);
                    }
                }
            }

2571 2572
            case (ty::ty_fn(?ep, ?expected_inputs,
                            ?expected_output, ?expected_cf)) {
2573
                alt (struct(cx.tcx, actual)) {
2574 2575
                    case (ty::ty_fn(?ap, ?actual_inputs,
                                    ?actual_output, ?actual_cf)) {
2576 2577
                        ret unify_fn(cx, ep, ap,
                                     expected, actual,
2578
                                     expected_inputs, expected_output,
2579 2580
                                     actual_inputs, actual_output,
                                     expected_cf, actual_cf);
2581 2582 2583 2584 2585 2586 2587 2588
                    }

                    case (_) {
                        ret ures_err(terr_mismatch, expected, actual);
                    }
                }
            }

2589
            case (ty::ty_native_fn(?e_abi, ?expected_inputs,
2590
                                  ?expected_output)) {
2591
                alt (struct(cx.tcx, actual)) {
2592
                    case (ty::ty_native_fn(?a_abi, ?actual_inputs,
2593
                                          ?actual_output)) {
2594 2595
                        ret unify_native_fn(cx, e_abi, a_abi,
                                            expected, actual,
2596 2597 2598 2599 2600 2601 2602 2603 2604
                                            expected_inputs, expected_output,
                                            actual_inputs, actual_output);
                    }
                    case (_) {
                        ret ures_err(terr_mismatch, expected, actual);
                    }
                }
            }

2605
            case (ty::ty_obj(?expected_meths)) {
2606
                alt (struct(cx.tcx, actual)) {
2607
                    case (ty::ty_obj(?actual_meths)) {
2608
                        ret unify_obj(cx, expected, actual,
2609 2610 2611 2612 2613
                                      expected_meths, actual_meths);
                    }
                    case (_) {
                        ret ures_err(terr_mismatch, expected, actual);
                    }
G
Graydon Hoare 已提交
2614 2615 2616
                }
            }

2617
            case (ty::ty_var(?expected_id)) {
2618 2619 2620 2621 2622
                // Add a binding. (`actual` can't actually be a var here.)
                alt (record_binding[int](cx, cx.bindings, expected_id,
                                         actual)) {
                    case (ures_ok(_)) { /* fall through */ }
                    case (?res) { ret res; }
2623 2624
                }
                ret ures_ok(expected);
2625 2626
            }

2627
            case (ty::ty_local(?expected_id)) {
2628
                auto result_ty;
2629
                alt (cx.handler.resolve_local(expected_id)) {
2630 2631
                    case (none[t]) { result_ty = actual; }
                    case (some[t](?expected_ty)) {
2632
                        auto result = unify_step(cx, expected_ty, actual);
2633 2634 2635 2636
                        alt (result) {
                            case (ures_ok(?rty)) { result_ty = rty; }
                            case (_) { ret result; }
                        }
2637 2638
                    }
                }
2639

2640
                cx.handler.record_local(expected_id, result_ty);
2641
                ret ures_ok(result_ty);
2642 2643
            }

2644
            case (ty::ty_bound_param(?expected_id)) {
2645
                ret cx.handler.record_param(expected_id, actual);
2646 2647 2648 2649 2650 2651 2652
            }
        }

        // TODO: remove me once match-exhaustiveness checking works
        fail;
    }

2653
    // Performs type binding substitution.
2654 2655 2656 2657
    fn substitute(&ty_ctxt tcx,
                  &@bindings[int] bindings,
                  &vec[t] set_types,
                  &t typ) -> t {
2658
        if (!type_contains_vars(tcx, typ)) {
2659 2660 2661
            ret typ;
        }

2662 2663 2664
        fn substituter(ty_ctxt tcx,
                       @bindings[int] bindings,
                       vec[t] types,
2665 2666
                       t typ) -> t {
            alt (struct(tcx, typ)) {
2667
                case (ty_var(?id)) {
2668
                    alt (bindings.ids.find(id)) {
2669
                        case (some[uint](?n)) {
2670
                            auto root = ufind::find(bindings.sets, n);
2671 2672 2673
                            ret types.(root);
                        }
                        case (none[uint]) { ret typ; }
2674 2675
                    }
                }
2676 2677 2678 2679
                case (_) { ret typ; }
            }
        }

2680
        auto f = bind substituter(tcx, bindings, set_types, _);
2681
        ret fold_ty(tcx, f, typ);
2682 2683
    }

2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697
    fn unify_sets[T](&ty_ctxt tcx, &@bindings[T] bindings) -> set_result {
        obj handler() {
            fn resolve_local(ast::def_id id) -> option::t[t] {
                log_err "resolve_local in unify_sets";
                fail;
            }
            fn record_local(ast::def_id id, t ty) {
                log_err "record_local in unify_sets";
                fail;
            }
            fn record_param(uint index, t binding) -> unify::result {
                log_err "record_param in unify_sets";
                fail;
            }
2698 2699
        }

2700 2701 2702 2703 2704
        auto node_count = vec::len[option::t[t]](bindings.types);

        let vec[option::t[t]] results =
            vec::init_elt[option::t[t]](none[t], node_count);

2705
        auto i = 0u;
2706
        while (i < node_count) {
2707
            auto root = ufind::find(bindings.sets, i);
2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729
            alt (bindings.types.(i)) {
                case (none[t]) { /* nothing to do */ }
                case (some[t](?actual)) {
                    alt (results.(root)) {
                        case (none[t]) { results.(root) = some[t](actual); }
                        case (some[t](?expected)) {
                            // FIXME: Is this right?
                            auto bindings = mk_bindings[int](int::hash,
                                                             int::eq_alias);
                            alt (unify(expected, actual, handler(), bindings,
                                    tcx)) {
                                case (ures_ok(?result_ty)) {
                                    results.(i) = some[t](result_ty);
                                }
                                case (ures_err(?e, ?t_a, ?t_b)) {
                                    ret usr_err(e, t_a, t_b);
                                }
                            }
                        }
                    }
                }
            }
2730 2731 2732
            i += 1u;
        }

2733 2734 2735 2736 2737
        // FIXME: This is equivalent to map(option::get, results) but it
        // causes an assertion in typeck at the moment.
        let vec[t] real_results = [];
        for (option::t[t] typ in results) {
            real_results += [option::get[t](typ)];
2738 2739
        }

2740
        ret usr_ok(real_results);
2741 2742
    }

2743 2744
    fn unify(&t expected,
             &t actual,
2745
             &unify_handler handler,
2746
             &@bindings[int] bindings,
2747
             &ty_ctxt tcx) -> result {
2748
        auto cx = @rec(bindings=bindings, handler=handler, tcx=tcx);
2749 2750
        ret unify_step(cx, expected, actual);
    }
2751

2752 2753 2754 2755 2756 2757 2758
    fn fixup(&ty_ctxt tcx, &@bindings[int] bindings, t typ) -> result {
        alt (unify_sets[int](tcx, bindings)) {
            case (usr_ok(?set_types)) {
                ret ures_ok(substitute(tcx, bindings, set_types, typ));
            }
            case (usr_err(?terr, ?t0, ?t1)) { ret ures_err(terr, t0, t1); }
        }
2759
    }
2760 2761
}

2762
fn type_err_to_str(&ty::type_err err) -> str {
2763 2764 2765 2766
    alt (err) {
        case (terr_mismatch) {
            ret "types differ";
        }
2767 2768 2769 2770
        case (terr_controlflow_mismatch) {
            ret "returning function used where non-returning function"
                + " was expected";
        }
2771 2772 2773 2774 2775 2776
        case (terr_box_mutability) {
            ret "boxed values differ in mutability";
        }
        case (terr_vec_mutability) {
            ret "vectors differ in mutability";
        }
2777
        case (terr_tuple_size(?e_sz, ?a_sz)) {
2778 2779
            ret "expected a tuple with " + uint::to_str(e_sz, 10u) +
                " elements but found one with " + uint::to_str(a_sz, 10u) +
2780 2781 2782 2783 2784 2785
                " elements";
        }
        case (terr_tuple_mutability) {
            ret "tuple elements differ in mutability";
        }
        case (terr_record_size(?e_sz, ?a_sz)) {
2786 2787
            ret "expected a record with " + uint::to_str(e_sz, 10u) +
                " fields but found one with " + uint::to_str(a_sz, 10u) +
2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800
                " fields";
        }
        case (terr_record_mutability) {
            ret "record elements differ in mutability";
        }
        case (terr_record_fields(?e_fld, ?a_fld)) {
            ret "expected a record with field '" + e_fld +
                "' but found one with field '" + a_fld +
                "'";
        }
        case (terr_arg_count) {
            ret "incorrect number of function parameters";
        }
G
Graydon Hoare 已提交
2801 2802 2803 2804 2805 2806 2807 2808
        case (terr_meth_count) {
            ret "incorrect number of object methods";
        }
        case (terr_obj_meths(?e_meth, ?a_meth)) {
            ret "expected an obj with method '" + e_meth +
                "' but found one with method '" + a_meth +
                "'";
        }
2809 2810 2811
    }
}

2812
// Performs bound type parameter replacement using the supplied mapping from
2813
// parameter IDs to types.
2814
fn substitute_type_params(&ctxt cx, &vec[t] bindings, &t typ) -> t {
2815
    if (!type_contains_bound_params(cx, typ)) {
2816 2817
        ret typ;
    }
2818
    fn replacer(&ctxt cx, vec[t] bindings, t typ) -> t {
2819
        alt (struct(cx, typ)) {
2820 2821
            case (ty_bound_param(?param_index)) {
                ret bindings.(param_index);
2822
            }
2823
            case (_) { ret typ; }
2824 2825
        }
    }
2826

2827 2828
    auto f = bind replacer(cx, bindings, _);
    ret fold_ty(cx, f, typ);
2829 2830
}

2831
// Converts type parameters in a type to bound type parameters.
2832
fn bind_params_in_type(&ctxt cx, &t typ) -> t {
2833 2834 2835
    if (!type_contains_params(cx, typ)) {
        ret typ;
    }
2836
    fn binder(&ctxt cx, t typ) -> t {
2837
        alt (struct(cx, typ)) {
2838
            case (ty_bound_param(?index)) {
2839
                log_err "bind_params_in_type() called on type that already " +
2840 2841
                    "has bound params in it";
                fail;
2842
            }
2843
            case (ty_param(?index)) { ret mk_bound_param(cx, index); }
2844
            case (_) { ret typ; }
2845 2846 2847
        }
    }

2848 2849
    auto f = bind binder(cx, _);
    ret fold_ty(cx, f, typ);
2850 2851
}

2852

2853
fn def_has_ty_params(&ast::def def) -> bool {
2854
    alt (def) {
2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868
        case (ast::def_fn(_))            { ret true;  }
        case (ast::def_obj(_))           { ret true;  }
        case (ast::def_obj_field(_))     { ret false; }
        case (ast::def_mod(_))           { ret false; }
        case (ast::def_const(_))         { ret false; }
        case (ast::def_arg(_))           { ret false; }
        case (ast::def_local(_))         { ret false; }
        case (ast::def_variant(_, _))    { ret true;  }
        case (ast::def_ty(_))            { ret false; }
        case (ast::def_ty_arg(_))        { ret false; }
        case (ast::def_binding(_))       { ret false; }
        case (ast::def_use(_))           { ret false; }
        case (ast::def_native_ty(_))     { ret false; }
        case (ast::def_native_fn(_))     { ret true;  }
2869 2870 2871
    }
}

2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928

// Tag information

type variant_info = rec(vec[ty::t] args, ty::t ctor_ty, ast::def_id id);

fn tag_variants(&ctxt cx, &ast::def_id id) -> vec[variant_info] {
    if (cx.sess.get_targ_crate_num() != id._0) {
        ret creader::get_tag_variants(cx, id);
    }

    assert (cx.items.contains_key(id));
    alt (cx.items.get(id)) {
        case (any_item_rust(?item)) {
            alt (item.node) {
                case (ast::item_tag(_, ?variants, _, _, _)) {
                    let vec[variant_info] result = [];
                    for (ast::variant variant in variants) {
                        auto ctor_ty = ann_to_monotype(cx, variant.node.ann);
                        let vec[t] arg_tys = [];
                        if (vec::len[ast::variant_arg](variant.node.args)
                            > 0u) {
                            for (arg a in ty_fn_args(cx, ctor_ty)) {
                                arg_tys += [a.ty];
                            }
                        }
                        auto did = variant.node.id;
                        result += [rec(args=arg_tys,
                                       ctor_ty=ctor_ty,
                                       id=did)];
                    }
                    ret result;
                }
            }
        }
    }
    fail;   // not reached
}

// Returns information about the tag variant with the given ID:
fn tag_variant_with_id(&ctxt cx,
                       &ast::def_id tag_id,
                       &ast::def_id variant_id) -> variant_info {
    auto variants = tag_variants(cx, tag_id);

    auto i = 0u;
    while (i < vec::len[variant_info](variants)) {
        auto variant = variants.(i);
        if (common::def_eq(variant.id, variant_id)) {
            ret variant;
        }
        i += 1u;
    }

    log_err "tag_variant_with_id(): no variant exists with that ID";
    fail;
}

2929 2930
// If the given item is in an external crate, looks up its type and adds it to
// the type cache. Returns the type parameters and type.
2931 2932
fn lookup_item_type(ctxt cx, ast::def_id did) -> ty_param_count_and_ty {
    if (did._0 == cx.sess.get_targ_crate_num()) {
2933 2934
        // The item is in this crate. The caller should have added it to the
        // type cache already; we simply return it.
2935
        ret cx.tcache.get(did);
2936 2937
    }

2938
    alt (cx.tcache.find(did)) {
2939 2940
        case (some[ty_param_count_and_ty](?tpt)) { ret tpt; }
        case (none[ty_param_count_and_ty]) {
2941
            auto tyt = creader::get_type(cx, did);
2942
            cx.tcache.insert(did, tyt);
2943 2944
            ret tyt;
        }
2945 2946 2947
    }
}

2948 2949
fn ret_ty_of_fn_ty(ty_ctxt tcx, t a_ty) -> t {
    alt (ty::struct(tcx, a_ty)) {
2950
        case (ty::ty_fn(_, _, ?ret_ty, _)) {
2951 2952
            ret ret_ty;
        }
2953
        case (_) {
2954 2955 2956 2957 2958
            fail;
        }
    }
}

2959 2960
fn ret_ty_of_fn(ty_ctxt tcx, ast::ann ann) -> t {
    ret ret_ty_of_fn_ty(tcx, ann_to_type(tcx.node_types, ann));
2961
}
2962

2963 2964 2965 2966 2967 2968
// Local Variables:
// mode: rust
// fill-column: 78;
// indent-tabs-mode: nil
// c-basic-offset: 4
// buffer-file-coding-system: utf-8-unix
2969
// compile-command: "make -k -C $RBUILD 2>&1 | sed -e 's/\\/x\\//x:\\//g'";
2970
// End: