src/comp/middle/typeck.rs

   1 import syntax::{ast, ast_util};
   2 import ast::spanned;
   3 import syntax::ast_util::{local_def, respan};
   4 import syntax::visit;
   5 import metadata::csearch;
   6 import driver::session::session;
   7 import util::common::*;
   8 import syntax::codemap::span;
   9 import pat_util::*;
  10 import middle::ty;
  11 import middle::ty::{node_id_to_type, arg, block_ty,
  12                     expr_ty, field, node_type_table, mk_nil,
  13                     ty_param_substs_opt_and_ty, ty_param_bounds_and_ty};
  14 import util::ppaux::ty_to_str;
  15 import middle::ty::unify::{ures_ok, ures_err, fix_ok, fix_err};
  16 import core::{int, vec, str, option};
  17 import std::smallintmap;
  18 import std::map::{hashmap, new_int_hash};
  19 import option::{none, some};
  20 import syntax::print::pprust::*;
  21
  22 export check_crate;
  23 export method_map, method_origin, method_static, method_param, method_iface;
  24 export dict_map, dict_res, dict_origin, dict_static, dict_param, dict_iface;
  25
  26 enum method_origin {
  27     method_static(ast::def_id),
  28     // iface id, method num, param num, bound num
  29     method_param(ast::def_id, uint, uint, uint),
  30     method_iface(uint),
  31 }
  32 type method_map = hashmap<ast::node_id, method_origin>;
  33
  34 // Resolutions for bounds of all parameters, left to right, for a given path.
  35 type dict_res = @[dict_origin];
  36 enum dict_origin {
  37     dict_static(ast::def_id, [ty::t], dict_res),
  38     // Param number, bound number
  39     dict_param(uint, uint),
  40     dict_iface(ast::def_id),
  41 }
  42 type dict_map = hashmap<ast::node_id, dict_res>;
  43
  44 type ty_table = hashmap<ast::def_id, ty::t>;
  45
  46 // Used for typechecking the methods of an impl
  47 enum self_info {
  48     self_impl(ty::t),
  49 }
  50
  51 type crate_ctxt = {mutable self_infos: [self_info],
  52                    impl_map: resolve::impl_map,
  53                    method_map: method_map,
  54                    dict_map: dict_map,
  55                    tcx: ty::ctxt};
  56
  57 type fn_ctxt =
  58     // var_bindings, locals and next_var_id are shared
  59     // with any nested functions that capture the environment
  60     // (and with any functions whose environment is being captured).
  61     {ret_ty: ty::t,
  62      purity: ast::purity,
  63      proto: ast::proto,
  64      var_bindings: @ty::unify::var_bindings,
  65      locals: hashmap<ast::node_id, int>,
  66      next_var_id: @mutable int,
  67      mutable fixups: [ast::node_id],
  68      ccx: @crate_ctxt};
  69
  70
  71 fn lookup_local(fcx: @fn_ctxt, sp: span, id: ast::node_id) -> int {
  72     alt fcx.locals.find(id) {
  73       some(x) { x }
  74       _ {
  75         fcx.ccx.tcx.sess.span_fatal(sp,
  76                                     "internal error looking up a local var")
  77       }
  78     }
  79 }
  80
  81 fn lookup_def(fcx: @fn_ctxt, sp: span, id: ast::node_id) -> ast::def {
  82     alt fcx.ccx.tcx.def_map.find(id) {
  83       some(x) { x }
  84       _ {
  85         fcx.ccx.tcx.sess.span_fatal(sp,
  86                                     "internal error looking up a definition")
  87       }
  88     }
  89 }
  90
  91 // Returns the type parameter count and the type for the given definition.
  92 fn ty_param_bounds_and_ty_for_def(fcx: @fn_ctxt, sp: span, defn: ast::def) ->
  93    ty_param_bounds_and_ty {
  94     alt defn {
  95       ast::def_arg(id, _) {
  96         assert (fcx.locals.contains_key(id.node));
  97         let typ = ty::mk_var(fcx.ccx.tcx, lookup_local(fcx, sp, id.node));
  98         ret {bounds: @[], ty: typ};
  99       }
 100       ast::def_local(id, _) {
 101         assert (fcx.locals.contains_key(id.node));
 102         let typ = ty::mk_var(fcx.ccx.tcx, lookup_local(fcx, sp, id.node));
 103         ret {bounds: @[], ty: typ};
 104       }
 105       ast::def_self(id) {
 106         alt get_self_info(fcx.ccx) {
 107           some(self_impl(impl_t)) {
 108             ret {bounds: @[], ty: impl_t};
 109           }
 110         }
 111       }
 112       ast::def_fn(id, _) | ast::def_const(id) |
 113       ast::def_variant(_, id) { ret ty::lookup_item_type(fcx.ccx.tcx, id); }
 114       ast::def_binding(id) {
 115         assert (fcx.locals.contains_key(id.node));
 116         let typ = ty::mk_var(fcx.ccx.tcx, lookup_local(fcx, sp, id.node));
 117         ret {bounds: @[], ty: typ};
 118       }
 119       ast::def_mod(_) {
 120         // Hopefully part of a path.
 121         // TODO: return a type that's more poisonous, perhaps?
 122         ret {bounds: @[], ty: ty::mk_nil(fcx.ccx.tcx)};
 123       }
 124       ast::def_ty(_) {
 125         fcx.ccx.tcx.sess.span_fatal(sp, "expected value but found type");
 126       }
 127       ast::def_upvar(_, inner, _) {
 128         ret ty_param_bounds_and_ty_for_def(fcx, sp, *inner);
 129       }
 130       _ {
 131         // FIXME: handle other names.
 132         fcx.ccx.tcx.sess.unimpl("definition variant");
 133       }
 134     }
 135 }
 136
 137 // Instantiates the given path, which must refer to an item with the given
 138 // number of type parameters and type.
 139 fn instantiate_path(fcx: @fn_ctxt, pth: @ast::path,
 140                     tpt: ty_param_bounds_and_ty, sp: span)
 141     -> ty_param_substs_opt_and_ty {
 142     let ty_param_count = vec::len(*tpt.bounds);
 143     let vars = vec::init_fn(ty_param_count, {|_i| next_ty_var(fcx)});
 144     let ty_substs_len = vec::len(pth.node.types);
 145     if ty_substs_len > 0u {
 146         let param_var_len = vec::len(vars);
 147         if param_var_len == 0u {
 148             fcx.ccx.tcx.sess.span_fatal
 149                 (sp, "this item does not take type parameters");
 150         } else if ty_substs_len > param_var_len {
 151             fcx.ccx.tcx.sess.span_fatal
 152                 (sp, "too many type parameter provided for this item");
 153         } else if ty_substs_len < param_var_len {
 154             fcx.ccx.tcx.sess.span_fatal
 155                 (sp, "not enough type parameters provided for this item");
 156         }
 157         vec::iter2(pth.node.types, vars) {|sub, var|
 158             let ty_subst = ast_ty_to_ty_crate(fcx.ccx, sub);
 159             demand::simple(fcx, pth.span, var, ty_subst);
 160         }
 161         if ty_param_count == 0u {
 162             fcx.ccx.tcx.sess.span_fatal(
 163                 sp, "this item does not take type parameters");
 164         }
 165     }
 166     {substs: some(vars), ty: tpt.ty}
 167 }
 168
 169 // Type tests
 170 fn structurally_resolved_type(fcx: @fn_ctxt, sp: span, tp: ty::t) -> ty::t {
 171     alt ty::unify::resolve_type_structure(fcx.ccx.tcx, fcx.var_bindings, tp) {
 172       fix_ok(typ_s) { ret typ_s; }
 173       fix_err(_) {
 174         fcx.ccx.tcx.sess.span_fatal
 175             (sp, "the type of this value must be known in this context");
 176       }
 177     }
 178 }
 179
 180
 181 // Returns the one-level-deep structure of the given type.f
 182 fn structure_of(fcx: @fn_ctxt, sp: span, typ: ty::t) -> ty::sty {
 183     ret ty::struct(fcx.ccx.tcx, structurally_resolved_type(fcx, sp, typ));
 184 }
 185
 186 // Returns the one-level-deep structure of the given type or none if it
 187 // is not known yet.
 188 fn structure_of_maybe(fcx: @fn_ctxt, _sp: span, typ: ty::t) ->
 189    option::t<ty::sty> {
 190     let r =
 191         ty::unify::resolve_type_structure(fcx.ccx.tcx, fcx.var_bindings, typ);
 192     ret alt r {
 193           fix_ok(typ_s) { some(ty::struct(fcx.ccx.tcx, typ_s)) }
 194           fix_err(_) { none }
 195         }
 196 }
 197
 198 fn type_is_integral(fcx: @fn_ctxt, sp: span, typ: ty::t) -> bool {
 199     let typ_s = structurally_resolved_type(fcx, sp, typ);
 200     ret ty::type_is_integral(fcx.ccx.tcx, typ_s);
 201 }
 202
 203 fn type_is_scalar(fcx: @fn_ctxt, sp: span, typ: ty::t) -> bool {
 204     let typ_s = structurally_resolved_type(fcx, sp, typ);
 205     ret ty::type_is_scalar(fcx.ccx.tcx, typ_s);
 206 }
 207
 208 fn type_is_c_like_enum(fcx: @fn_ctxt, sp: span, typ: ty::t) -> bool {
 209     let typ_s = structurally_resolved_type(fcx, sp, typ);
 210     ret ty::type_is_c_like_enum(fcx.ccx.tcx, typ_s);
 211 }
 212
 213 // Parses the programmer's textual representation of a type into our internal
 214 // notion of a type. `getter` is a function that returns the type
 215 // corresponding to a definition ID:
 216 fn default_arg_mode_for_ty(tcx: ty::ctxt, m: ast::mode,
 217                            ty: ty::t) -> ast::mode {
 218     alt m {
 219       ast::mode_infer {
 220         alt ty::struct(tcx, ty) {
 221             ty::ty_var(_) { ast::mode_infer }
 222             _ {
 223                 if ty::type_is_immediate(tcx, ty) { ast::by_val }
 224                 else { ast::by_ref }
 225             }
 226         }
 227       }
 228       _ { m }
 229     }
 230 }
 231
 232 enum mode { m_collect, m_check, m_check_tyvar(@fn_ctxt), }
 233
 234 fn ast_ty_to_ty(tcx: ty::ctxt, mode: mode, &&ast_ty: @ast::ty) -> ty::t {
 235     fn getter(tcx: ty::ctxt, mode: mode, id: ast::def_id)
 236         -> ty::ty_param_bounds_and_ty {
 237         alt mode {
 238           m_check | m_check_tyvar(_) { ty::lookup_item_type(tcx, id) }
 239           m_collect {
 240             if id.crate != ast::local_crate { csearch::get_type(tcx, id) }
 241             else {
 242                 alt tcx.items.find(id.node) {
 243                   some(ast_map::node_item(item)) {
 244                     ty_of_item(tcx, mode, item)
 245                   }
 246                   some(ast_map::node_native_item(native_item)) {
 247                     ty_of_native_item(tcx, mode, native_item)
 248                   }
 249                 }
 250             }
 251           }
 252         }
 253     }
 254     fn ast_arg_to_arg(tcx: ty::ctxt, mode: mode, arg: ast::arg)
 255         -> {mode: ty::mode, ty: ty::t} {
 256         let ty = ast_ty_to_ty(tcx, mode, arg.ty);
 257         ret {mode: default_arg_mode_for_ty(tcx, arg.mode, ty), ty: ty};
 258     }
 259     alt tcx.ast_ty_to_ty_cache.find(ast_ty) {
 260       some(some(ty)) { ret ty; }
 261       some(none) {
 262         tcx.sess.span_fatal(ast_ty.span, "illegal recursive type. \
 263                                           insert a enum in the cycle, \
 264                                           if this is desired)");
 265       }
 266       none { }
 267     } /* go on */
 268
 269     tcx.ast_ty_to_ty_cache.insert(ast_ty, none::<ty::t>);
 270     fn ast_mt_to_mt(tcx: ty::ctxt, mode: mode, mt: ast::mt) -> ty::mt {
 271         ret {ty: ast_ty_to_ty(tcx, mode, mt.ty), mut: mt.mut};
 272     }
 273     fn instantiate(tcx: ty::ctxt, sp: span, mode: mode,
 274                    id: ast::def_id, args: [@ast::ty]) -> ty::t {
 275         // TODO: maybe record cname chains so we can do
 276         // "foo = int" like OCaml?
 277
 278         let ty_param_bounds_and_ty = getter(tcx, mode, id);
 279         if vec::len(*ty_param_bounds_and_ty.bounds) == 0u {
 280             ret ty_param_bounds_and_ty.ty;
 281         }
 282
 283         // The typedef is type-parametric. Do the type substitution.
 284         let param_bindings: [ty::t] = [];
 285         if vec::len(args) != vec::len(*ty_param_bounds_and_ty.bounds) {
 286             tcx.sess.span_fatal(sp, "Wrong number of type arguments for a \
 287                                      polymorphic type");
 288         }
 289         for ast_ty: @ast::ty in args {
 290             param_bindings += [ast_ty_to_ty(tcx, mode, ast_ty)];
 291         }
 292         let typ =
 293             ty::substitute_type_params(tcx, param_bindings,
 294                                        ty_param_bounds_and_ty.ty);
 295         ret typ;
 296     }
 297     let typ;
 298     alt ast_ty.node {
 299       ast::ty_nil { typ = ty::mk_nil(tcx); }
 300       ast::ty_bot { typ = ty::mk_bot(tcx); }
 301       ast::ty_bool { typ = ty::mk_bool(tcx); }
 302       ast::ty_int(it) { typ = ty::mk_mach_int(tcx, it); }
 303       ast::ty_uint(uit) { typ = ty::mk_mach_uint(tcx, uit); }
 304       ast::ty_float(ft) { typ = ty::mk_mach_float(tcx, ft); }
 305       ast::ty_str { typ = ty::mk_str(tcx); }
 306       ast::ty_box(mt) {
 307         typ = ty::mk_box(tcx, ast_mt_to_mt(tcx, mode, mt));
 308       }
 309       ast::ty_uniq(mt) {
 310         typ = ty::mk_uniq(tcx, ast_mt_to_mt(tcx, mode, mt));
 311       }
 312       ast::ty_vec(mt) {
 313         typ = ty::mk_vec(tcx, ast_mt_to_mt(tcx, mode, mt));
 314       }
 315       ast::ty_ptr(mt) {
 316         typ = ty::mk_ptr(tcx, ast_mt_to_mt(tcx, mode, mt));
 317       }
 318       ast::ty_tup(fields) {
 319         let flds = vec::map(fields, bind ast_ty_to_ty(tcx, mode, _));
 320         typ = ty::mk_tup(tcx, flds);
 321       }
 322       ast::ty_rec(fields) {
 323         let flds: [field] = [];
 324         for f: ast::ty_field in fields {
 325             let tm = ast_mt_to_mt(tcx, mode, f.node.mt);
 326             flds += [{ident: f.node.ident, mt: tm}];
 327         }
 328         typ = ty::mk_rec(tcx, flds);
 329       }
 330       ast::ty_fn(proto, decl) {
 331         typ = ty::mk_fn(tcx, ty_of_fn_decl(tcx, mode, proto, decl));
 332       }
 333       ast::ty_path(path, id) {
 334         alt tcx.def_map.find(id) {
 335           some(ast::def_ty(id)) {
 336             typ = instantiate(tcx, ast_ty.span, mode, id, path.node.types);
 337           }
 338           some(ast::def_native_ty(id)) { typ = getter(tcx, mode, id).ty; }
 339           some(ast::def_ty_param(id, n)) {
 340             typ = ty::mk_param(tcx, n, id);
 341           }
 342           some(_) {
 343             tcx.sess.span_fatal(ast_ty.span,
 344                                 "found type name used as a variable");
 345           }
 346           _ {
 347             tcx.sess.span_fatal(ast_ty.span, "internal error in instantiate");
 348           }
 349         }
 350       }
 351       ast::ty_constr(t, cs) {
 352         let out_cs = [];
 353         for constr: @ast::ty_constr in cs {
 354             out_cs += [ty::ast_constr_to_constr(tcx, constr)];
 355         }
 356         typ = ty::mk_constr(tcx, ast_ty_to_ty(tcx, mode, t), out_cs);
 357       }
 358       ast::ty_infer {
 359         alt mode {
 360           m_check_tyvar(fcx) { ret next_ty_var(fcx); }
 361           _ { tcx.sess.span_bug(ast_ty.span,
 362                                 "found `ty_infer` in unexpected place"); }
 363         }
 364       }
 365     }
 366     tcx.ast_ty_to_ty_cache.insert(ast_ty, some(typ));
 367     ret typ;
 368 }
 369
 370 fn ty_of_item(tcx: ty::ctxt, mode: mode, it: @ast::item)
 371     -> ty::ty_param_bounds_and_ty {
 372     alt it.node {
 373       ast::item_const(t, _) {
 374         let typ = ast_ty_to_ty(tcx, mode, t);
 375         let tpt = {bounds: @[], ty: typ};
 376         tcx.tcache.insert(local_def(it.id), tpt);
 377         ret tpt;
 378       }
 379       ast::item_fn(decl, tps, _) {
 380         ret ty_of_fn(tcx, mode, decl, tps, local_def(it.id));
 381       }
 382       ast::item_ty(t, tps) {
 383         alt tcx.tcache.find(local_def(it.id)) {
 384           some(tpt) { ret tpt; }
 385           none { }
 386         }
 387         // Tell ast_ty_to_ty() that we want to perform a recursive
 388         // call to resolve any named types.
 389         let tpt = {bounds: ty_param_bounds(tcx, mode, tps),
 390                    ty: ty::mk_named(tcx, ast_ty_to_ty(tcx, mode, t),
 391                                     @it.ident)};
 392         tcx.tcache.insert(local_def(it.id), tpt);
 393         ret tpt;
 394       }
 395       ast::item_res(decl, tps, _, _, _) {
 396         let {bounds, params} = mk_ty_params(tcx, tps);
 397         let t_arg = ty_of_arg(tcx, mode, decl.inputs[0]);
 398         let t = ty::mk_named(tcx, ty::mk_res(tcx, local_def(it.id), t_arg.ty,
 399                                              params),
 400                              @it.ident);
 401         let t_res = {bounds: bounds, ty: t};
 402         tcx.tcache.insert(local_def(it.id), t_res);
 403         ret t_res;
 404       }
 405       ast::item_enum(_, tps) {
 406         // Create a new generic polytype.
 407         let {bounds, params} = mk_ty_params(tcx, tps);
 408         let t = ty::mk_named(tcx, ty::mk_enum(tcx, local_def(it.id), params),
 409                              @it.ident);
 410         let tpt = {bounds: bounds, ty: t};
 411         tcx.tcache.insert(local_def(it.id), tpt);
 412         ret tpt;
 413       }
 414       ast::item_iface(tps, ms) {
 415         let s_tp = vec::len(tps) - 1u;
 416         tcx.ty_param_bounds.insert(tps[s_tp].id, @[]);
 417         let {bounds, params} = mk_ty_params(tcx, vec::slice(tps, 0u, s_tp));
 418         let t = ty::mk_named(tcx, ty::mk_iface(tcx, local_def(it.id), params),
 419                              @it.ident);
 420         let tpt = {bounds: bounds, ty: t};
 421         tcx.tcache.insert(local_def(it.id), tpt);
 422         ret tpt;
 423       }
 424     }
 425 }
 426 fn ty_of_native_item(tcx: ty::ctxt, mode: mode, it: @ast::native_item)
 427     -> ty::ty_param_bounds_and_ty {
 428     alt it.node {
 429       ast::native_item_fn(fn_decl, params) {
 430         ret ty_of_native_fn_decl(tcx, mode, fn_decl, params,
 431                                  local_def(it.id));
 432       }
 433       ast::native_item_ty {
 434         alt tcx.tcache.find(local_def(it.id)) {
 435           some(tpt) { ret tpt; }
 436           none { }
 437         }
 438         let t = ty::mk_native(tcx, local_def(it.id));
 439         let t = ty::mk_named(tcx, t, @it.ident);
 440         let tpt = {bounds: @[], ty: t};
 441         tcx.tcache.insert(local_def(it.id), tpt);
 442         ret tpt;
 443       }
 444     }
 445 }
 446 fn ty_of_arg(tcx: ty::ctxt, mode: mode, a: ast::arg) -> ty::arg {
 447     let ty = ast_ty_to_ty(tcx, mode, a.ty);
 448     {mode: default_arg_mode_for_ty(tcx, a.mode, ty), ty: ty}
 449 }
 450 fn ty_of_fn_decl(tcx: ty::ctxt, mode: mode,
 451                  proto: ast::proto, decl: ast::fn_decl) -> ty::fn_ty {
 452     let input_tys = [];
 453     for a: ast::arg in decl.inputs { input_tys += [ty_of_arg(tcx, mode, a)]; }
 454     let output_ty = ast_ty_to_ty(tcx, mode, decl.output);
 455
 456     let out_constrs = [];
 457     for constr: @ast::constr in decl.constraints {
 458         out_constrs += [ty::ast_constr_to_constr(tcx, constr)];
 459     }
 460     {proto: proto, inputs: input_tys,
 461      output: output_ty, ret_style: decl.cf, constraints: out_constrs}
 462 }
 463 fn ty_of_fn(tcx: ty::ctxt, mode: mode, decl: ast::fn_decl,
 464             ty_params: [ast::ty_param], def_id: ast::def_id)
 465     -> ty::ty_param_bounds_and_ty {
 466     let bounds = ty_param_bounds(tcx, mode, ty_params);
 467     let tofd = ty_of_fn_decl(tcx, mode, ast::proto_bare, decl);
 468     let tpt = {bounds: bounds, ty: ty::mk_fn(tcx, tofd)};
 469     tcx.tcache.insert(def_id, tpt);
 470     ret tpt;
 471 }
 472 fn ty_of_native_fn_decl(tcx: ty::ctxt, mode: mode, decl: ast::fn_decl,
 473                         ty_params: [ast::ty_param], def_id: ast::def_id)
 474     -> ty::ty_param_bounds_and_ty {
 475     let input_tys = [], bounds = ty_param_bounds(tcx, mode, ty_params);
 476     for a: ast::arg in decl.inputs { input_tys += [ty_of_arg(tcx, mode, a)]; }
 477     let output_ty = ast_ty_to_ty(tcx, mode, decl.output);
 478
 479     let t_fn = ty::mk_fn(tcx, {proto: ast::proto_bare,
 480                                inputs: input_tys,
 481                                output: output_ty,
 482                                ret_style: ast::return_val,
 483                                constraints: []});
 484     let tpt = {bounds: bounds, ty: t_fn};
 485     tcx.tcache.insert(def_id, tpt);
 486     ret tpt;
 487 }
 488 fn ty_param_bounds(tcx: ty::ctxt, mode: mode, params: [ast::ty_param])
 489     -> @[ty::param_bounds] {
 490     let result = [];
 491     for param in params {
 492         result += [alt tcx.ty_param_bounds.find(param.id) {
 493           some(bs) { bs }
 494           none {
 495             let bounds = [];
 496             for b in *param.bounds {
 497                 bounds += [alt b {
 498                   ast::bound_send { ty::bound_send }
 499                   ast::bound_copy { ty::bound_copy }
 500                   ast::bound_iface(t) {
 501                     let ity = ast_ty_to_ty(tcx, mode, t);
 502                     alt ty::struct(tcx, ity) {
 503                       ty::ty_iface(_, _) {}
 504                       _ {
 505                         tcx.sess.span_fatal(
 506                             t.span, "type parameter bounds must be \
 507                                      interface types");
 508                       }
 509                     }
 510                     ty::bound_iface(ity)
 511                   }
 512                 }];
 513             }
 514             let boxed = @bounds;
 515             tcx.ty_param_bounds.insert(param.id, boxed);
 516             boxed
 517           }
 518         }];
 519     }
 520     @result
 521 }
 522 fn ty_of_method(tcx: ty::ctxt, mode: mode, m: @ast::method) -> ty::method {
 523     {ident: m.ident, tps: ty_param_bounds(tcx, mode, m.tps),
 524      fty: ty_of_fn_decl(tcx, mode, ast::proto_bare, m.decl)}
 525 }
 526 fn ty_of_ty_method(tcx: ty::ctxt, mode: mode, m: ast::ty_method)
 527     -> ty::method {
 528     {ident: m.ident, tps: ty_param_bounds(tcx, mode, m.tps),
 529      fty: ty_of_fn_decl(tcx, mode, ast::proto_bare, m.decl)}
 530 }
 531
 532 // A convenience function to use a crate_ctxt to resolve names for
 533 // ast_ty_to_ty.
 534 fn ast_ty_to_ty_crate(ccx: @crate_ctxt, &&ast_ty: @ast::ty) -> ty::t {
 535     ret ast_ty_to_ty(ccx.tcx, m_check, ast_ty);
 536 }
 537
 538 // A wrapper around ast_ty_to_ty_crate that handles ty_infer.
 539 fn ast_ty_to_ty_crate_infer(ccx: @crate_ctxt, &&ast_ty: @ast::ty) ->
 540    option::t<ty::t> {
 541     alt ast_ty.node {
 542       ast::ty_infer { none }
 543       _ { some(ast_ty_to_ty_crate(ccx, ast_ty)) }
 544     }
 545 }
 546
 547
 548 // Functions that write types into the node type table
 549 mod write {
 550     fn inner(ntt: node_type_table, node_id: ast::node_id,
 551              tpot: ty_param_substs_opt_and_ty) {
 552         smallintmap::insert(*ntt, node_id as uint, tpot);
 553     }
 554
 555     // Writes a type parameter count and type pair into the node type table.
 556     fn ty(tcx: ty::ctxt, node_id: ast::node_id,
 557           tpot: ty_param_substs_opt_and_ty) {
 558         assert (!ty::type_contains_vars(tcx, tpot.ty));
 559         inner(tcx.node_types, node_id, tpot);
 560     }
 561
 562     // Writes a type parameter count and type pair into the node type table.
 563     // This function allows for the possibility of type variables, which will
 564     // be rewritten later during the fixup mode.
 565     fn ty_fixup(fcx: @fn_ctxt, node_id: ast::node_id,
 566                 tpot: ty_param_substs_opt_and_ty) {
 567         inner(fcx.ccx.tcx.node_types, node_id, tpot);
 568         if ty::type_contains_vars(fcx.ccx.tcx, tpot.ty) {
 569             fcx.fixups += [node_id];
 570         }
 571     }
 572
 573     // Writes a type with no type parameters into the node type table.
 574     fn ty_only(tcx: ty::ctxt, node_id: ast::node_id, typ: ty::t) {
 575         ty(tcx, node_id, {substs: none::<[ty::t]>, ty: typ});
 576     }
 577
 578     // Writes a type with no type parameters into the node type table. This
 579     // function allows for the possibility of type variables.
 580     fn ty_only_fixup(fcx: @fn_ctxt, node_id: ast::node_id, typ: ty::t) {
 581         ret ty_fixup(fcx, node_id, {substs: none::<[ty::t]>, ty: typ});
 582     }
 583
 584     // Writes a nil type into the node type table.
 585     fn nil_ty(tcx: ty::ctxt, node_id: ast::node_id) {
 586         ret ty(tcx, node_id, {substs: none::<[ty::t]>, ty: ty::mk_nil(tcx)});
 587     }
 588
 589     // Writes the bottom type into the node type table.
 590     fn bot_ty(tcx: ty::ctxt, node_id: ast::node_id) {
 591         ret ty(tcx, node_id, {substs: none::<[ty::t]>, ty: ty::mk_bot(tcx)});
 592     }
 593 }
 594
 595 fn mk_ty_params(tcx: ty::ctxt, atps: [ast::ty_param])
 596     -> {bounds: @[ty::param_bounds], params: [ty::t]} {
 597     let i = 0u, bounds = ty_param_bounds(tcx, m_collect, atps);
 598     {bounds: bounds,
 599      params: vec::map(atps, {|atp|
 600          let t = ty::mk_param(tcx, i, local_def(atp.id));
 601          i += 1u;
 602          t
 603      })}
 604 }
 605
 606 fn compare_impl_method(tcx: ty::ctxt, sp: span, impl_m: ty::method,
 607                        impl_tps: uint, if_m: ty::method, substs: [ty::t])
 608     -> ty::t {
 609     if impl_m.tps != if_m.tps {
 610         tcx.sess.span_err(sp, "method `" + if_m.ident +
 611                           "` has an incompatible set of type parameters");
 612         ty::mk_fn(tcx, impl_m.fty)
 613     } else {
 614         let auto_modes = vec::map2(impl_m.fty.inputs, if_m.fty.inputs, {|i, f|
 615             alt ty::struct(tcx, f.ty) {
 616               ty::ty_param(0u, _) if i.mode == ast::mode_infer {
 617                 {mode: ast::by_ref with i}
 618               }
 619               _ { i }
 620             }
 621         });
 622         let impl_fty = ty::mk_fn(tcx, {inputs: auto_modes with impl_m.fty});
 623         // Add dummy substs for the parameters of the impl method
 624         let substs = substs + vec::init_fn(vec::len(*if_m.tps), {|i|
 625             ty::mk_param(tcx, i + impl_tps, {crate: 0, node: 0})
 626         });
 627         let if_fty = ty::substitute_type_params(tcx, substs,
 628                                                 ty::mk_fn(tcx, if_m.fty));
 629         alt ty::unify::unify(impl_fty, if_fty, ty::unify::precise, tcx) {
 630           ty::unify::ures_err(err) {
 631             tcx.sess.span_err(sp, "method `" + if_m.ident +
 632                               "` has an incompatible type: " +
 633                               ty::type_err_to_str(err));
 634             impl_fty
 635           }
 636           ty::unify::ures_ok(tp) { tp }
 637         }
 638     }
 639 }
 640
 641 // Item collection - a pair of bootstrap passes:
 642 //
 643 // (1) Collect the IDs of all type items (typedefs) and store them in a table.
 644 //
 645 // (2) Translate the AST fragments that describe types to determine a type for
 646 //     each item. When we encounter a named type, we consult the table built
 647 //     in pass 1 to find its item, and recursively translate it.
 648 //
 649 // We then annotate the AST with the resulting types and return the annotated
 650 // AST, along with a table mapping item IDs to their types.
 651 //
 652 // TODO: This logic is quite convoluted; it's a relic of the time when we
 653 // actually wrote types directly into the AST and didn't have a type cache.
 654 // Could use some cleanup. Consider topologically sorting in phase (1) above.
 655 mod collect {
 656     type ctxt = {tcx: ty::ctxt};
 657
 658     fn get_enum_variant_types(cx: @ctxt, enum_ty: ty::t,
 659                              variants: [ast::variant],
 660                              ty_params: [ast::ty_param]) {
 661         // Create a set of parameter types shared among all the variants.
 662
 663         for variant: ast::variant in variants {
 664             // Nullary enum constructors get turned into constants; n-ary enum
 665             // constructors get turned into functions.
 666
 667             let result_ty = if vec::len(variant.node.args) == 0u {
 668                 enum_ty
 669             } else {
 670                 // As above, tell ast_ty_to_ty() that trans_ty_item_to_ty()
 671                 // should be called to resolve named types.
 672                 let args: [arg] = [];
 673                 for va: ast::variant_arg in variant.node.args {
 674                     let arg_ty = ast_ty_to_ty(cx.tcx, m_collect, va.ty);
 675                     args += [{mode: ast::by_copy, ty: arg_ty}];
 676                 }
 677                 // FIXME: this will be different for constrained types
 678                 ty::mk_fn(cx.tcx,
 679                           {proto: ast::proto_box,
 680                            inputs: args, output: enum_ty,
 681                            ret_style: ast::return_val, constraints: []})
 682             };
 683             let tpt = {bounds: ty_param_bounds(cx.tcx, m_collect, ty_params),
 684                        ty: result_ty};
 685             cx.tcx.tcache.insert(local_def(variant.node.id), tpt);
 686             write::ty_only(cx.tcx, variant.node.id, result_ty);
 687         }
 688     }
 689     fn convert(cx: @ctxt, it: @ast::item) {
 690         alt it.node {
 691           // These don't define types.
 692           ast::item_mod(_) | ast::item_native_mod(_) {}
 693           ast::item_enum(variants, ty_params) {
 694             let tpt = ty_of_item(cx.tcx, m_collect, it);
 695             write::ty_only(cx.tcx, it.id, tpt.ty);
 696             get_enum_variant_types(cx, tpt.ty, variants, ty_params);
 697           }
 698           ast::item_impl(tps, ifce, selfty, ms) {
 699             let i_bounds = ty_param_bounds(cx.tcx, m_collect, tps);
 700             let my_methods = [];
 701             for m in ms {
 702                 let bounds = ty_param_bounds(cx.tcx, m_collect, m.tps);
 703                 let mty = ty_of_method(cx.tcx, m_collect, m);
 704                 my_methods += [{mty: mty, id: m.id}];
 705                 let fty = ty::mk_fn(cx.tcx, mty.fty);
 706                 cx.tcx.tcache.insert(local_def(m.id),
 707                                      {bounds: @(*i_bounds + *bounds),
 708                                       ty: fty});
 709                 write::ty_only(cx.tcx, m.id, fty);
 710             }
 711             let selfty = ast_ty_to_ty(cx.tcx, m_collect, selfty);
 712             write::ty_only(cx.tcx, it.id, selfty);
 713             alt ifce {
 714               some(t) {
 715                 let iface_ty = ast_ty_to_ty(cx.tcx, m_collect, t);
 716                 cx.tcx.tcache.insert(local_def(it.id),
 717                                      {bounds: i_bounds, ty: iface_ty});
 718                 alt ty::struct(cx.tcx, iface_ty) {
 719                   ty::ty_iface(did, tys) {
 720                     for if_m in *ty::iface_methods(cx.tcx, did) {
 721                         alt vec::find(my_methods,
 722                                       {|m| if_m.ident == m.mty.ident}) {
 723                           some({mty: m, id}) {
 724                             let mt = compare_impl_method(
 725                                 cx.tcx, t.span, m, vec::len(tps), if_m,
 726                                 tys + [selfty]);
 727                             let old = cx.tcx.tcache.get(local_def(id));
 728                             if old.ty != mt {
 729                                 cx.tcx.tcache.insert(local_def(id),
 730                                                      {bounds: old.bounds,
 731                                                       ty: mt});
 732                                 write::ty_only(cx.tcx, id, mt);
 733                             }
 734                           }
 735                           none {
 736                             cx.tcx.sess.span_err(t.span, "missing method `" +
 737                                                  if_m.ident + "`");
 738                           }
 739                         }
 740                     }
 741                   }
 742                   _ {
 743                     cx.tcx.sess.span_fatal(t.span, "can only implement \
 744                                                     interface types");
 745                   }
 746                 }
 747               }
 748               _ {}
 749             }
 750           }
 751           ast::item_res(decl, tps, _, dtor_id, ctor_id) {
 752             let {bounds, params} = mk_ty_params(cx.tcx, tps);
 753             let t_arg = ty_of_arg(cx.tcx, m_collect, decl.inputs[0]);
 754             let t_res = ty::mk_res(cx.tcx, local_def(it.id), t_arg.ty,
 755                                    params);
 756             let t_ctor = ty::mk_fn(cx.tcx, {
 757                 proto: ast::proto_box,
 758                 inputs: [{mode: ast::by_copy with t_arg}],
 759                 output: t_res,
 760                 ret_style: ast::return_val, constraints: []
 761             });
 762             let t_dtor = ty::mk_fn(cx.tcx, {
 763                 proto: ast::proto_box,
 764                 inputs: [t_arg], output: ty::mk_nil(cx.tcx),
 765                 ret_style: ast::return_val, constraints: []
 766             });
 767             write::ty_only(cx.tcx, it.id, t_res);
 768             write::ty_only(cx.tcx, ctor_id, t_ctor);
 769             cx.tcx.tcache.insert(local_def(ctor_id),
 770                                  {bounds: bounds, ty: t_ctor});
 771             write::ty_only(cx.tcx, dtor_id, t_dtor);
 772           }
 773           ast::item_iface(_, ms) {
 774             let tpt = ty_of_item(cx.tcx, m_collect, it);
 775             write::ty_only(cx.tcx, it.id, tpt.ty);
 776             ty::store_iface_methods(cx.tcx, it.id, @vec::map(ms, {|m|
 777                 ty_of_ty_method(cx.tcx, m_collect, m)
 778             }));
 779           }
 780           _ {
 781             // This call populates the type cache with the converted type
 782             // of the item in passing. All we have to do here is to write
 783             // it into the node type table.
 784             let tpt = ty_of_item(cx.tcx, m_collect, it);
 785             write::ty_only(cx.tcx, it.id, tpt.ty);
 786           }
 787         }
 788     }
 789     fn convert_native(cx: @ctxt, i: @ast::native_item) {
 790         // As above, this call populates the type table with the converted
 791         // type of the native item. We simply write it into the node type
 792         // table.
 793         let tpt = ty_of_native_item(cx.tcx, m_collect, i);
 794         alt i.node {
 795           ast::native_item_ty {
 796             // FIXME: Native types have no annotation. Should they? --pcw
 797           }
 798           ast::native_item_fn(_, _) {
 799             write::ty_only(cx.tcx, i.id, tpt.ty);
 800           }
 801         }
 802     }
 803     fn collect_item_types(tcx: ty::ctxt, crate: @ast::crate) {
 804         let cx = @{tcx: tcx};
 805         let visit =
 806             visit::mk_simple_visitor(@{visit_item: bind convert(cx, _),
 807                                        visit_native_item:
 808                                            bind convert_native(cx, _)
 809                                        with
 810                                           *visit::default_simple_visitor()});
 811         visit::visit_crate(*crate, (), visit);
 812     }
 813 }
 814
 815
 816 // Type unification
 817 mod unify {
 818     fn unify(fcx: @fn_ctxt, expected: ty::t, actual: ty::t) ->
 819        ty::unify::result {
 820         ret ty::unify::unify(expected, actual,
 821                              ty::unify::in_bindings(fcx.var_bindings),
 822                              fcx.ccx.tcx);
 823     }
 824 }
 825
 826
 827 // FIXME This is almost a duplicate of ty::type_autoderef, with structure_of
 828 // instead of ty::struct.
 829 fn do_autoderef(fcx: @fn_ctxt, sp: span, t: ty::t) -> ty::t {
 830     let t1 = t;
 831     while true {
 832         alt structure_of(fcx, sp, t1) {
 833           ty::ty_box(inner) | ty::ty_uniq(inner) {
 834             alt ty::struct(fcx.ccx.tcx, t1) {
 835               ty::ty_var(v1) {
 836                 if ty::occurs_check_fails(fcx.ccx.tcx, some(sp), v1,
 837                                           ty::mk_box(fcx.ccx.tcx, inner)) {
 838                     break;
 839                 }
 840               }
 841               _ { }
 842             }
 843             t1 = inner.ty;
 844           }
 845           ty::ty_res(_, inner, tps) {
 846             t1 = ty::substitute_type_params(fcx.ccx.tcx, tps, inner);
 847           }
 848           ty::ty_enum(did, tps) {
 849             let variants = ty::enum_variants(fcx.ccx.tcx, did);
 850             if vec::len(*variants) != 1u || vec::len(variants[0].args) != 1u {
 851                 ret t1;
 852             }
 853             t1 =
 854                 ty::substitute_type_params(fcx.ccx.tcx, tps,
 855                                            variants[0].args[0]);
 856           }
 857           _ { ret t1; }
 858         }
 859     }
 860     fail;
 861 }
 862
 863 fn resolve_type_vars_if_possible(fcx: @fn_ctxt, typ: ty::t) -> ty::t {
 864     alt ty::unify::fixup_vars(fcx.ccx.tcx, none, fcx.var_bindings, typ) {
 865       fix_ok(new_type) { ret new_type; }
 866       fix_err(_) { ret typ; }
 867     }
 868 }
 869
 870
 871 // Demands - procedures that require that two types unify and emit an error
 872 // message if they don't.
 873 type ty_param_substs_and_ty = {substs: [ty::t], ty: ty::t};
 874
 875 mod demand {
 876     fn simple(fcx: @fn_ctxt, sp: span, expected: ty::t, actual: ty::t) ->
 877        ty::t {
 878         full(fcx, sp, expected, actual, []).ty
 879     }
 880
 881     fn with_substs(fcx: @fn_ctxt, sp: span, expected: ty::t, actual: ty::t,
 882                    ty_param_substs_0: [ty::t]) -> ty_param_substs_and_ty {
 883         full(fcx, sp, expected, actual, ty_param_substs_0)
 884     }
 885
 886     // Requires that the two types unify, and prints an error message if they
 887     // don't. Returns the unified type and the type parameter substitutions.
 888     fn full(fcx: @fn_ctxt, sp: span, expected: ty::t, actual: ty::t,
 889             ty_param_substs_0: [ty::t]) ->
 890        ty_param_substs_and_ty {
 891
 892         let ty_param_substs: [mutable ty::t] = [mutable];
 893         let ty_param_subst_var_ids: [int] = [];
 894         for ty_param_subst: ty::t in ty_param_substs_0 {
 895             // Generate a type variable and unify it with the type parameter
 896             // substitution. We will then pull out these type variables.
 897             let t_0 = next_ty_var(fcx);
 898             ty_param_substs += [mutable t_0];
 899             ty_param_subst_var_ids += [ty::ty_var_id(fcx.ccx.tcx, t_0)];
 900             simple(fcx, sp, ty_param_subst, t_0);
 901         }
 902
 903         fn mk_result(fcx: @fn_ctxt, result_ty: ty::t,
 904                      ty_param_subst_var_ids: [int]) ->
 905            ty_param_substs_and_ty {
 906             let result_ty_param_substs: [ty::t] = [];
 907             for var_id: int in ty_param_subst_var_ids {
 908                 let tp_subst = ty::mk_var(fcx.ccx.tcx, var_id);
 909                 result_ty_param_substs += [tp_subst];
 910             }
 911             ret {substs: result_ty_param_substs, ty: result_ty};
 912         }
 913
 914
 915         alt unify::unify(fcx, expected, actual) {
 916           ures_ok(t) { ret mk_result(fcx, t, ty_param_subst_var_ids); }
 917           ures_err(err) {
 918             let e_err = resolve_type_vars_if_possible(fcx, expected);
 919             let a_err = resolve_type_vars_if_possible(fcx, actual);
 920             fcx.ccx.tcx.sess.span_err(sp,
 921                                       "mismatched types: expected `" +
 922                                           ty_to_str(fcx.ccx.tcx, e_err) +
 923                                           "` but found `" +
 924                                           ty_to_str(fcx.ccx.tcx, a_err) +
 925                                           "` (" + ty::type_err_to_str(err) +
 926                                           ")");
 927             ret mk_result(fcx, expected, ty_param_subst_var_ids);
 928           }
 929         }
 930     }
 931 }
 932
 933
 934 // Returns true if the two types unify and false if they don't.
 935 fn are_compatible(fcx: @fn_ctxt, expected: ty::t, actual: ty::t) -> bool {
 936     alt unify::unify(fcx, expected, actual) {
 937       ures_ok(_) { ret true; }
 938       ures_err(_) { ret false; }
 939     }
 940 }
 941
 942
 943 // Returns the types of the arguments to a enum variant.
 944 fn variant_arg_types(ccx: @crate_ctxt, _sp: span, vid: ast::def_id,
 945                      enum_ty_params: [ty::t]) -> [ty::t] {
 946     let result: [ty::t] = [];
 947     let tpt = ty::lookup_item_type(ccx.tcx, vid);
 948     alt ty::struct(ccx.tcx, tpt.ty) {
 949       ty::ty_fn(f) {
 950         // N-ary variant.
 951         for arg: ty::arg in f.inputs {
 952             let arg_ty =
 953                 ty::substitute_type_params(ccx.tcx, enum_ty_params, arg.ty);
 954             result += [arg_ty];
 955         }
 956       }
 957       _ {
 958         // Nullary variant. Do nothing, as there are no arguments.
 959       }
 960     }
 961     /* result is a vector of the *expected* types of all the fields */
 962
 963     ret result;
 964 }
 965
 966
 967 // Type resolution: the phase that finds all the types in the AST with
 968 // unresolved type variables and replaces "ty_var" types with their
 969 // substitutions.
 970 //
 971 // TODO: inefficient since not all types have vars in them. It would be better
 972 // to maintain a list of fixups.
 973 mod writeback {
 974
 975     export resolve_type_vars_in_block;
 976     export resolve_type_vars_in_expr;
 977
 978     fn resolve_type_vars_in_type(fcx: @fn_ctxt, sp: span, typ: ty::t) ->
 979        option::t<ty::t> {
 980         if !ty::type_contains_vars(fcx.ccx.tcx, typ) { ret some(typ); }
 981         alt ty::unify::fixup_vars(fcx.ccx.tcx, some(sp), fcx.var_bindings,
 982                                   typ) {
 983           fix_ok(new_type) { ret some(new_type); }
 984           fix_err(vid) {
 985             fcx.ccx.tcx.sess.span_err(sp, "cannot determine a type \
 986                                            for this expression");
 987             ret none;
 988           }
 989         }
 990     }
 991     fn resolve_type_vars_for_node(wbcx: wb_ctxt, sp: span, id: ast::node_id) {
 992         let fcx = wbcx.fcx;
 993         let tpot = ty::node_id_to_ty_param_substs_opt_and_ty(fcx.ccx.tcx, id);
 994         let new_ty =
 995             alt resolve_type_vars_in_type(fcx, sp, tpot.ty) {
 996               some(t) { t }
 997               none { wbcx.success = false; ret }
 998             };
 999         let new_substs_opt;
1000         alt tpot.substs {
1001           none { new_substs_opt = none; }
1002           some(substs) {
1003             let new_substs: [ty::t] = [];
1004             for subst: ty::t in substs {
1005                 alt resolve_type_vars_in_type(fcx, sp, subst) {
1006                   some(t) { new_substs += [t]; }
1007                   none { wbcx.success = false; ret; }
1008                 }
1009             }
1010             new_substs_opt = some(new_substs);
1011           }
1012         }
1013         write::ty(fcx.ccx.tcx, id, {substs: new_substs_opt, ty: new_ty});
1014     }
1015
1016     type wb_ctxt =
1017         // As soon as we hit an error we have to stop resolving
1018         // the entire function
1019         {fcx: @fn_ctxt, mutable success: bool};
1020     type wb_vt = visit::vt<wb_ctxt>;
1021
1022     fn visit_stmt(s: @ast::stmt, wbcx: wb_ctxt, v: wb_vt) {
1023         if !wbcx.success { ret; }
1024         resolve_type_vars_for_node(wbcx, s.span, ty::stmt_node_id(s));
1025         visit::visit_stmt(s, wbcx, v);
1026     }
1027     fn visit_expr(e: @ast::expr, wbcx: wb_ctxt, v: wb_vt) {
1028         if !wbcx.success { ret; }
1029         resolve_type_vars_for_node(wbcx, e.span, e.id);
1030         alt e.node {
1031           ast::expr_fn(_, decl, _, _) |
1032           ast::expr_fn_block(decl, _) {
1033             for input in decl.inputs {
1034                 resolve_type_vars_for_node(wbcx, e.span, input.id);
1035             }
1036           }
1037           _ { }
1038         }
1039         visit::visit_expr(e, wbcx, v);
1040     }
1041     fn visit_block(b: ast::blk, wbcx: wb_ctxt, v: wb_vt) {
1042         if !wbcx.success { ret; }
1043         resolve_type_vars_for_node(wbcx, b.span, b.node.id);
1044         visit::visit_block(b, wbcx, v);
1045     }
1046     fn visit_pat(p: @ast::pat, wbcx: wb_ctxt, v: wb_vt) {
1047         if !wbcx.success { ret; }
1048         resolve_type_vars_for_node(wbcx, p.span, p.id);
1049         visit::visit_pat(p, wbcx, v);
1050     }
1051     fn visit_local(l: @ast::local, wbcx: wb_ctxt, v: wb_vt) {
1052         if !wbcx.success { ret; }
1053         let var_id = lookup_local(wbcx.fcx, l.span, l.node.id);
1054         let fix_rslt =
1055             ty::unify::resolve_type_var(wbcx.fcx.ccx.tcx, some(l.span),
1056                                         wbcx.fcx.var_bindings, var_id);
1057         alt fix_rslt {
1058           fix_ok(lty) { write::ty_only(wbcx.fcx.ccx.tcx, l.node.id, lty); }
1059           fix_err(_) {
1060             wbcx.fcx.ccx.tcx.sess.span_err(l.span,
1061                                            "cannot determine a type \
1062                                                 for this local variable");
1063             wbcx.success = false;
1064           }
1065         }
1066         visit::visit_local(l, wbcx, v);
1067     }
1068     fn visit_item(_item: @ast::item, _wbcx: wb_ctxt, _v: wb_vt) {
1069         // Ignore items
1070     }
1071
1072     fn resolve_type_vars_in_expr(fcx: @fn_ctxt, e: @ast::expr) -> bool {
1073         let wbcx = {fcx: fcx, mutable success: true};
1074         let visit =
1075             visit::mk_vt(@{visit_item: visit_item,
1076                            visit_stmt: visit_stmt,
1077                            visit_expr: visit_expr,
1078                            visit_block: visit_block,
1079                            visit_pat: visit_pat,
1080                            visit_local: visit_local
1081                               with *visit::default_visitor()});
1082         visit::visit_expr(e, wbcx, visit);
1083         ret wbcx.success;
1084     }
1085
1086     fn resolve_type_vars_in_block(fcx: @fn_ctxt, blk: ast::blk) -> bool {
1087         let wbcx = {fcx: fcx, mutable success: true};
1088         let visit =
1089             visit::mk_vt(@{visit_item: visit_item,
1090                            visit_stmt: visit_stmt,
1091                            visit_expr: visit_expr,
1092                            visit_block: visit_block,
1093                            visit_pat: visit_pat,
1094                            visit_local: visit_local
1095                               with *visit::default_visitor()});
1096         visit.visit_block(blk, wbcx, visit);
1097         ret wbcx.success;
1098     }
1099 }
1100
1101
1102 // Local variable gathering. We gather up all locals and create variable IDs
1103 // for them before typechecking the function.
1104 type gather_result =
1105     {var_bindings: @ty::unify::var_bindings,
1106      locals: hashmap<ast::node_id, int>,
1107      next_var_id: @mutable int};
1108
1109 // Used only as a helper for check_fn.
1110 fn gather_locals(ccx: @crate_ctxt,
1111                  decl: ast::fn_decl,
1112                  body: ast::blk,
1113                  id: ast::node_id,
1114                  old_fcx: option::t<@fn_ctxt>) -> gather_result {
1115     let {vb: vb, locals: locals, nvi: nvi} =
1116         alt old_fcx {
1117           none {
1118             {vb: ty::unify::mk_var_bindings(),
1119              locals: new_int_hash::<int>(),
1120              nvi: @mutable 0}
1121           }
1122           some(fcx) {
1123             {vb: fcx.var_bindings,
1124              locals: fcx.locals,
1125              nvi: fcx.next_var_id}
1126           }
1127         };
1128     let tcx = ccx.tcx;
1129
1130     let next_var_id = fn@() -> int { let rv = *nvi; *nvi += 1; ret rv; };
1131     let assign = fn@(nid: ast::node_id, ty_opt: option::t<ty::t>) {
1132             let var_id = next_var_id();
1133             locals.insert(nid, var_id);
1134             alt ty_opt {
1135               none {/* nothing to do */ }
1136               some(typ) {
1137                 ty::unify::unify(ty::mk_var(tcx, var_id), typ,
1138                                  ty::unify::in_bindings(vb), tcx);
1139               }
1140             }
1141         };
1142
1143     // Add formal parameters.
1144     let args = ty::ty_fn_args(ccx.tcx, ty::node_id_to_type(ccx.tcx, id));
1145     let i = 0u;
1146     for arg: ty::arg in args {
1147         assign(decl.inputs[i].id, some(arg.ty));
1148         i += 1u;
1149     }
1150
1151     // Add explicitly-declared locals.
1152     let visit_local = fn@(local: @ast::local, &&e: (), v: visit::vt<()>) {
1153             let local_ty = ast_ty_to_ty_crate_infer(ccx, local.node.ty);
1154             assign(local.node.id, local_ty);
1155             visit::visit_local(local, e, v);
1156         };
1157
1158     // Add pattern bindings.
1159     let visit_pat = fn@(p: @ast::pat, &&e: (), v: visit::vt<()>) {
1160         alt normalize_pat(ccx.tcx, p).node {
1161               ast::pat_ident(_, _) { assign(p.id, none); }
1162               _ {/* no-op */ }
1163             }
1164             visit::visit_pat(p, e, v);
1165         };
1166
1167     // Don't descend into fns and items
1168     fn visit_fn<T>(_fk: visit::fn_kind, _decl: ast::fn_decl, _body: ast::blk,
1169                    _sp: span, _id: ast::node_id, _t: T, _v: visit::vt<T>) {
1170     }
1171     fn visit_item<E>(_i: @ast::item, _e: E, _v: visit::vt<E>) { }
1172
1173     let visit =
1174         @{visit_local: visit_local,
1175           visit_pat: visit_pat,
1176           visit_fn: bind visit_fn(_, _, _, _, _, _, _),
1177           visit_item: bind visit_item(_, _, _)
1178               with *visit::default_visitor()};
1179
1180     visit::visit_block(body, (), visit::mk_vt(visit));
1181     ret {var_bindings: vb,
1182          locals: locals,
1183          next_var_id: nvi};
1184 }
1185
1186 // AST fragment checking
1187 fn check_lit(ccx: @crate_ctxt, lit: @ast::lit) -> ty::t {
1188     alt lit.node {
1189       ast::lit_str(_) { ty::mk_str(ccx.tcx) }
1190       ast::lit_int(_, t) { ty::mk_mach_int(ccx.tcx, t) }
1191       ast::lit_uint(_, t) { ty::mk_mach_uint(ccx.tcx, t) }
1192       ast::lit_float(_, t) { ty::mk_mach_float(ccx.tcx, t) }
1193       ast::lit_nil { ty::mk_nil(ccx.tcx) }
1194       ast::lit_bool(_) { ty::mk_bool(ccx.tcx) }
1195     }
1196 }
1197
1198 fn valid_range_bounds(from: @ast::expr, to: @ast::expr) -> bool {
1199     ast_util::compare_lit_exprs(from, to) <= 0
1200 }
1201
1202 // Pattern checking is top-down rather than bottom-up so that bindings get
1203 // their types immediately.
1204 fn check_pat(fcx: @fn_ctxt, map: pat_util::pat_id_map, pat: @ast::pat,
1205              expected: ty::t) {
1206     alt normalize_pat(fcx.ccx.tcx, pat).node {
1207       ast::pat_wild {
1208           alt structure_of(fcx, pat.span, expected) {
1209                   ty::ty_enum(_, expected_tps) {
1210                       let path_tpt = {substs: some(expected_tps),
1211                                       ty: expected};
1212                       write::ty_fixup(fcx, pat.id, path_tpt);
1213                   }
1214                   _ {
1215                       write::ty_only_fixup(fcx, pat.id, expected);
1216                   }
1217               }
1218       }
1219       ast::pat_lit(lt) {
1220         check_expr_with(fcx, lt, expected);
1221         write::ty_only_fixup(fcx, pat.id, expr_ty(fcx.ccx.tcx, lt));
1222       }
1223       ast::pat_range(begin, end) {
1224         check_expr_with(fcx, begin, expected);
1225         check_expr_with(fcx, end, expected);
1226         let b_ty = resolve_type_vars_if_possible(fcx, expr_ty(fcx.ccx.tcx,
1227                                                               begin));
1228         if !ty::same_type(fcx.ccx.tcx, b_ty, resolve_type_vars_if_possible(
1229             fcx, expr_ty(fcx.ccx.tcx, end))) {
1230             fcx.ccx.tcx.sess.span_err(pat.span, "mismatched types in range");
1231         } else if !ty::type_is_numeric(fcx.ccx.tcx, b_ty) {
1232             fcx.ccx.tcx.sess.span_err(pat.span,
1233                                       "non-numeric type used in range");
1234         } else if !valid_range_bounds(begin, end) {
1235             fcx.ccx.tcx.sess.span_err(begin.span,
1236                                       "lower range bound must be less \
1237                                        than upper");
1238         }
1239         write::ty_only_fixup(fcx, pat.id, b_ty);
1240       }
1241       ast::pat_ident(name, sub) {
1242         let vid = lookup_local(fcx, pat.span, pat.id);
1243         let typ = ty::mk_var(fcx.ccx.tcx, vid);
1244         typ = demand::simple(fcx, pat.span, expected, typ);
1245         let canon_id = map.get(path_to_ident(name));
1246         if canon_id != pat.id {
1247             let ct =
1248                 ty::mk_var(fcx.ccx.tcx,
1249                            lookup_local(fcx, pat.span, canon_id));
1250             typ = demand::simple(fcx, pat.span, ct, typ);
1251         }
1252         write::ty_only_fixup(fcx, pat.id, typ);
1253         alt sub {
1254           some(p) { check_pat(fcx, map, p, expected); }
1255           _ {}
1256         }
1257       }
1258       ast::pat_enum(path, subpats) {
1259         // Typecheck the path.
1260         let v_def = lookup_def(fcx, path.span, pat.id);
1261         let v_def_ids = ast_util::variant_def_ids(v_def);
1262         let enum_tpt = ty::lookup_item_type(fcx.ccx.tcx, v_def_ids.tg);
1263         let path_tpot = instantiate_path(fcx, path, enum_tpt, pat.span);
1264
1265         // Take the enum type params out of `expected`.
1266         alt structure_of(fcx, pat.span, expected) {
1267           ty::ty_enum(_, expected_tps) {
1268             // Unify with the expected enum type.
1269             let ctor_ty =
1270                 ty::ty_param_substs_opt_and_ty_to_monotype(fcx.ccx.tcx,
1271                                                            path_tpot);
1272
1273             let path_tpt =
1274                 demand::with_substs(fcx, pat.span, expected, ctor_ty,
1275                                     expected_tps);
1276             path_tpot =
1277                 {substs: some::<[ty::t]>(path_tpt.substs), ty: path_tpt.ty};
1278
1279             // Get the number of arguments in this enum variant.
1280             let arg_types =
1281                 variant_arg_types(fcx.ccx, pat.span, v_def_ids.var,
1282                                   expected_tps);
1283             let subpats_len = vec::len::<@ast::pat>(subpats);
1284             if vec::len::<ty::t>(arg_types) > 0u {
1285                 // N-ary variant.
1286
1287                 let arg_len = vec::len::<ty::t>(arg_types);
1288                 if arg_len != subpats_len {
1289                     // TODO: note definition of enum variant
1290                     // TODO (issue #448): Wrap a #fmt string over multiple
1291                     // lines...
1292                     let s =
1293                         #fmt["this pattern has %u field%s, but the \
1294                                        corresponding variant has %u field%s",
1295                              subpats_len,
1296                              if subpats_len == 1u { "" } else { "s" },
1297                              arg_len, if arg_len == 1u { "" } else { "s" }];
1298                     fcx.ccx.tcx.sess.span_fatal(pat.span, s);
1299                 }
1300
1301                 // TODO: vec::iter2
1302
1303                 let i = 0u;
1304                 for subpat: @ast::pat in subpats {
1305                     check_pat(fcx, map, subpat, arg_types[i]);
1306                     i += 1u;
1307                 }
1308             } else if subpats_len > 0u {
1309                 // TODO: note definition of enum variant
1310                 fcx.ccx.tcx.sess.span_fatal
1311                     (pat.span,
1312                      #fmt["this pattern has %u field%s, \
1313                           but the corresponding \
1314                           variant has no fields",
1315                                                  subpats_len,
1316                                                  if subpats_len == 1u {
1317                                                      ""
1318                                                  } else { "s" }]);
1319             }
1320             write::ty_fixup(fcx, pat.id, path_tpot);
1321           }
1322           _ {
1323             // FIXME: Switch expected and actual in this message? I
1324             // can never tell.
1325             fcx.ccx.tcx.sess.span_fatal
1326                 (pat.span,
1327                  #fmt["mismatched types: expected `%s` but found enum",
1328                       ty_to_str(fcx.ccx.tcx, expected)]);
1329           }
1330         }
1331         write::ty_fixup(fcx, pat.id, path_tpot);
1332       }
1333       ast::pat_rec(fields, etc) {
1334         let ex_fields;
1335         alt structure_of(fcx, pat.span, expected) {
1336           ty::ty_rec(fields) { ex_fields = fields; }
1337           _ {
1338             fcx.ccx.tcx.sess.span_fatal
1339                 (pat.span,
1340                 #fmt["mismatched types: expected `%s` but found record",
1341                                 ty_to_str(fcx.ccx.tcx, expected)]);
1342           }
1343         }
1344         let f_count = vec::len(fields);
1345         let ex_f_count = vec::len(ex_fields);
1346         if ex_f_count < f_count || !etc && ex_f_count > f_count {
1347             fcx.ccx.tcx.sess.span_fatal
1348                 (pat.span, #fmt["mismatched types: expected a record \
1349                       with %u fields, found one with %u \
1350                       fields",
1351                                 ex_f_count, f_count]);
1352         }
1353         fn matches(name: str, f: ty::field) -> bool {
1354             ret str::eq(name, f.ident);
1355         }
1356         for f: ast::field_pat in fields {
1357             alt vec::find(ex_fields, bind matches(f.ident, _)) {
1358               some(field) { check_pat(fcx, map, f.pat, field.mt.ty); }
1359               none {
1360                 fcx.ccx.tcx.sess.span_fatal(pat.span,
1361                                             #fmt["mismatched types: did not \
1362                                            expect a record with a field `%s`",
1363                                                  f.ident]);
1364               }
1365             }
1366         }
1367         write::ty_only_fixup(fcx, pat.id, expected);
1368       }
1369       ast::pat_tup(elts) {
1370         let ex_elts;
1371         alt structure_of(fcx, pat.span, expected) {
1372           ty::ty_tup(elts) { ex_elts = elts; }
1373           _ {
1374             fcx.ccx.tcx.sess.span_fatal
1375                 (pat.span,
1376                  #fmt["mismatched types: expected `%s`, found tuple",
1377                         ty_to_str(fcx.ccx.tcx, expected)]);
1378           }
1379         }
1380         let e_count = vec::len(elts);
1381         if e_count != vec::len(ex_elts) {
1382             fcx.ccx.tcx.sess.span_fatal
1383                 (pat.span, #fmt["mismatched types: expected a tuple \
1384                       with %u fields, found one with %u \
1385                       fields", vec::len(ex_elts), e_count]);
1386         }
1387         let i = 0u;
1388         for elt in elts { check_pat(fcx, map, elt, ex_elts[i]); i += 1u; }
1389         write::ty_only_fixup(fcx, pat.id, expected);
1390       }
1391       ast::pat_box(inner) {
1392         alt structure_of(fcx, pat.span, expected) {
1393           ty::ty_box(e_inner) {
1394             check_pat(fcx, map, inner, e_inner.ty);
1395             write::ty_only_fixup(fcx, pat.id, expected);
1396           }
1397           _ {
1398             fcx.ccx.tcx.sess.span_fatal(pat.span,
1399                                         "mismatched types: expected `" +
1400                                             ty_to_str(fcx.ccx.tcx, expected) +
1401                                             "` found box");
1402           }
1403         }
1404       }
1405       ast::pat_uniq(inner) {
1406         alt structure_of(fcx, pat.span, expected) {
1407           ty::ty_uniq(e_inner) {
1408             check_pat(fcx, map, inner, e_inner.ty);
1409             write::ty_only_fixup(fcx, pat.id, expected);
1410           }
1411           _ {
1412             fcx.ccx.tcx.sess.span_fatal(pat.span,
1413                                         "mismatched types: expected `" +
1414                                             ty_to_str(fcx.ccx.tcx, expected) +
1415                                             "` found uniq");
1416           }
1417         }
1418       }
1419     }
1420 }
1421
1422 fn require_unsafe(sess: session, f_purity: ast::purity, sp: span) {
1423     alt f_purity {
1424       ast::unsafe_fn { ret; }
1425       _ {
1426         sess.span_err(
1427             sp,
1428             "unsafe operation requires unsafe function or block");
1429       }
1430     }
1431 }
1432
1433 fn require_impure(sess: session, f_purity: ast::purity, sp: span) {
1434     alt f_purity {
1435       ast::unsafe_fn { ret; }
1436       ast::impure_fn { ret; }
1437       ast::pure_fn {
1438         sess.span_err(sp, "Found impure expression in pure function decl");
1439       }
1440     }
1441 }
1442
1443 fn require_pure_call(ccx: @crate_ctxt, caller_purity: ast::purity,
1444                      callee: @ast::expr, sp: span) {
1445     alt caller_purity {
1446       ast::unsafe_fn { ret; }
1447       ast::impure_fn {
1448         alt ccx.tcx.def_map.find(callee.id) {
1449           some(ast::def_fn(_, ast::unsafe_fn)) {
1450             ccx.tcx.sess.span_err(
1451                 sp,
1452                 "safe function calls function marked unsafe");
1453           }
1454           _ {
1455           }
1456         }
1457         ret;
1458       }
1459       ast::pure_fn {
1460         alt ccx.tcx.def_map.find(callee.id) {
1461           some(ast::def_fn(_, ast::pure_fn)) |
1462           some(ast::def_variant(_, _)) { ret; }
1463           _ {
1464             ccx.tcx.sess.span_err
1465                 (sp, "pure function calls function not known to be pure");
1466           }
1467         }
1468       }
1469     }
1470 }
1471
1472 type unifier = fn@(@fn_ctxt, span, ty::t, ty::t) -> ty::t;
1473
1474 fn check_expr(fcx: @fn_ctxt, expr: @ast::expr) -> bool {
1475     fn dummy_unify(_fcx: @fn_ctxt, _sp: span, _expected: ty::t, actual: ty::t)
1476        -> ty::t {
1477         actual
1478     }
1479     ret check_expr_with_unifier(fcx, expr, dummy_unify, 0u);
1480 }
1481 fn check_expr_with(fcx: @fn_ctxt, expr: @ast::expr, expected: ty::t) -> bool {
1482     ret check_expr_with_unifier(fcx, expr, demand::simple, expected);
1483 }
1484
1485 fn impl_self_ty(tcx: ty::ctxt, did: ast::def_id) -> {n_tps: uint, ty: ty::t} {
1486     if did.crate == ast::local_crate {
1487         alt tcx.items.get(did.node) {
1488           ast_map::node_item(@{node: ast::item_impl(ts, _, st, _),
1489                                _}) {
1490             {n_tps: vec::len(ts), ty: ast_ty_to_ty(tcx, m_check, st)}
1491           }
1492         }
1493     } else {
1494         let tpt = csearch::get_type(tcx, did);
1495         {n_tps: vec::len(*tpt.bounds), ty: tpt.ty}
1496     }
1497 }
1498
1499 fn lookup_method(fcx: @fn_ctxt, isc: resolve::iscopes,
1500                  name: ast::ident, ty: ty::t, sp: span)
1501     -> option::t<{method_ty: ty::t, n_tps: uint, substs: [ty::t],
1502                   origin: method_origin}> {
1503     let tcx = fcx.ccx.tcx;
1504
1505     // First, see whether this is an interface-bounded parameter
1506     alt ty::struct(tcx, ty) {
1507       ty::ty_param(n, did) {
1508         let bound_n = 0u;
1509         for bound in *tcx.ty_param_bounds.get(did.node) {
1510             alt bound {
1511               ty::bound_iface(t) {
1512                 let (iid, tps) = alt ty::struct(tcx, t) {
1513                     ty::ty_iface(i, tps) { (i, tps) }
1514                 };
1515                 let ifce_methods = ty::iface_methods(tcx, iid);
1516                 alt vec::position(*ifce_methods, {|m| m.ident == name}) {
1517                   some(pos) {
1518                     let m = ifce_methods[pos];
1519                     ret some({method_ty: ty::mk_fn(tcx, m.fty),
1520                               n_tps: vec::len(*m.tps),
1521                               substs: tps + [ty],
1522                               origin: method_param(iid, pos, n, bound_n)});
1523                   }
1524                   _ {}
1525                 }
1526                 bound_n += 1u;
1527               }
1528               _ {}
1529             }
1530         }
1531         ret none;
1532       }
1533       ty::ty_iface(did, tps) {
1534         let i = 0u;
1535         for m in *ty::iface_methods(tcx, did) {
1536             if m.ident == name {
1537                 ret some({method_ty: ty::mk_fn(tcx, m.fty),
1538                           n_tps: vec::len(*m.tps),
1539                           substs: tps + [ty::mk_int(tcx)],
1540                           origin: method_iface(i)});
1541             }
1542             i += 1u;
1543         }
1544       }
1545       _ {}
1546     }
1547
1548     let result = none;
1549     std::list::iter(isc) {|impls|
1550         if option::is_some(result) { ret; }
1551         for @{did, methods, _} in *impls {
1552             alt vec::find(methods, {|m| m.ident == name}) {
1553               some(m) {
1554                 let {n_tps, ty: self_ty} = impl_self_ty(tcx, did);
1555                 let {vars, ty: self_ty} = if n_tps > 0u {
1556                     bind_params(fcx, self_ty, n_tps)
1557                 } else { {vars: [], ty: self_ty} };
1558                 alt unify::unify(fcx, ty, self_ty) {
1559                   ures_ok(_) {
1560                     if option::is_some(result) {
1561                         // FIXME[impl] score specificity to resolve ambiguity?
1562                         tcx.sess.span_err(
1563                             sp, "multiple applicable methods in scope");
1564                     } else {
1565                         result = some({
1566                             method_ty: ty::lookup_item_type(tcx, m.did).ty,
1567                             n_tps: m.n_tps,
1568                             substs: vars,
1569                             origin: method_static(m.did)
1570                         });
1571                     }
1572                   }
1573                   _ {}
1574                 }
1575               }
1576               _ {}
1577             }
1578         }
1579     }
1580     result
1581 }
1582
1583 fn check_expr_fn_with_unifier(fcx: @fn_ctxt,
1584                               expr: @ast::expr,
1585                               proto: ast::proto,
1586                               decl: ast::fn_decl,
1587                               body: ast::blk,
1588                               unify: unifier,
1589                               expected: ty::t) {
1590     let tcx = fcx.ccx.tcx;
1591
1592     let fty = ty::mk_fn(tcx, ty_of_fn_decl(tcx, m_check_tyvar(fcx),
1593                                            proto, decl));
1594
1595     #debug("check_expr_fn_with_unifier %s fty=%s",
1596            expr_to_str(expr),
1597            ty_to_str(tcx, fty));
1598
1599     write::ty_only_fixup(fcx, expr.id, fty);
1600
1601     // Unify the type of the function with the expected type before we
1602     // typecheck the body so that we have more information about the
1603     // argument types in the body. This is needed to make binops and
1604     // record projection work on type inferred arguments.
1605     unify(fcx, expr.span, expected, fty);
1606
1607     check_fn(fcx.ccx, proto, decl, body, expr.id, some(fcx));
1608 }
1609
1610 fn check_expr_with_unifier(fcx: @fn_ctxt, expr: @ast::expr, unify: unifier,
1611                            expected: ty::t) -> bool {
1612     #debug("typechecking expr %s",
1613            syntax::print::pprust::expr_to_str(expr));
1614
1615     // A generic function to factor out common logic from call and bind
1616     // expressions.
1617     fn check_call_or_bind(fcx: @fn_ctxt, sp: span, fty: ty::t,
1618                           args: [option::t<@ast::expr>]) -> bool {
1619         let sty = structure_of(fcx, sp, fty);
1620         // Grab the argument types
1621         let arg_tys = alt sty {
1622           ty::ty_fn({inputs: arg_tys, _}) { arg_tys }
1623           _ {
1624             fcx.ccx.tcx.sess.span_fatal(sp, "mismatched types: \
1625                                              expected function or native \
1626                                              function but found "
1627                                         + ty_to_str(fcx.ccx.tcx, fty))
1628           }
1629         };
1630
1631         // Check that the correct number of arguments were supplied.
1632         let expected_arg_count = vec::len(arg_tys);
1633         let supplied_arg_count = vec::len(args);
1634         if expected_arg_count != supplied_arg_count {
1635             fcx.ccx.tcx.sess.span_err(
1636                 sp, #fmt["this function takes %u parameter%s but %u \
1637                           parameter%s supplied", expected_arg_count,
1638                          expected_arg_count == 1u ? "" : "s",
1639                          supplied_arg_count,
1640                          supplied_arg_count == 1u ? " was" : "s were"]);
1641             // HACK: build an arguments list with dummy arguments to
1642             // check against
1643             let dummy = {mode: ast::by_ref, ty: ty::mk_bot(fcx.ccx.tcx)};
1644             arg_tys = vec::init_elt(supplied_arg_count, dummy);
1645         }
1646
1647         // Check the arguments.
1648         // We do this in a pretty awful way: first we typecheck any arguments
1649         // that are not anonymous functions, then we typecheck the anonymous
1650         // functions. This is so that we have more information about the types
1651         // of arguments when we typecheck the functions. This isn't really the
1652         // right way to do this.
1653         let check_args = fn@(check_blocks: bool) -> bool {
1654             let i = 0u;
1655             let bot = false;
1656             for a_opt in args {
1657                 alt a_opt {
1658                   some(a) {
1659                     let is_block = alt a.node {
1660                       ast::expr_fn_block(_, _) { true }
1661                       _ { false }
1662                     };
1663                     if is_block == check_blocks {
1664                         bot |= check_expr_with_unifier(
1665                             fcx, a, demand::simple, arg_tys[i].ty);
1666                     }
1667                   }
1668                   none { }
1669                 }
1670                 i += 1u;
1671             }
1672             ret bot;
1673         };
1674         check_args(false) | check_args(true)
1675     }
1676
1677     // A generic function for checking assignment expressions
1678     fn check_assignment(fcx: @fn_ctxt, _sp: span, lhs: @ast::expr,
1679                         rhs: @ast::expr, id: ast::node_id) -> bool {
1680         let t = next_ty_var(fcx);
1681         let bot = check_expr_with(fcx, lhs, t) | check_expr_with(fcx, rhs, t);
1682         write::ty_only_fixup(fcx, id, ty::mk_nil(fcx.ccx.tcx));
1683         ret bot;
1684     }
1685
1686     // A generic function for checking call expressions
1687     fn check_call(fcx: @fn_ctxt, sp: span, f: @ast::expr, args: [@ast::expr])
1688         -> bool {
1689         let args_opt_0: [option::t<@ast::expr>] = [];
1690         for arg: @ast::expr in args {
1691             args_opt_0 += [some::<@ast::expr>(arg)];
1692         }
1693
1694         let bot = check_expr(fcx, f);
1695         // Call the generic checker.
1696         bot | check_call_or_bind(fcx, sp, expr_ty(fcx.ccx.tcx, f), args_opt_0)
1697     }
1698
1699     // A generic function for doing all of the checking for call expressions
1700     fn check_call_full(fcx: @fn_ctxt, sp: span, f: @ast::expr,
1701                        args: [@ast::expr], id: ast::node_id) -> bool {
1702         /* here we're kind of hosed, as f can be any expr
1703         need to restrict it to being an explicit expr_path if we're
1704         inside a pure function, and need an environment mapping from
1705         function name onto purity-designation */
1706         require_pure_call(fcx.ccx, fcx.purity, f, sp);
1707         let bot = check_call(fcx, sp, f, args);
1708
1709         // Pull the return type out of the type of the function.
1710         let fty = ty::expr_ty(fcx.ccx.tcx, f);
1711         let rt_1 = alt structure_of(fcx, sp, fty) {
1712           ty::ty_fn(f) {
1713             bot |= f.ret_style == ast::noreturn;
1714             f.output
1715           }
1716           _ { fcx.ccx.tcx.sess.span_fatal(sp, "calling non-function"); }
1717         };
1718         write::ty_only_fixup(fcx, id, rt_1);
1719         ret bot;
1720     }
1721
1722     // A generic function for checking for or for-each loops
1723     fn check_for(fcx: @fn_ctxt, local: @ast::local,
1724                  element_ty: ty::t, body: ast::blk,
1725                  node_id: ast::node_id) -> bool {
1726         let locid = lookup_local(fcx, local.span, local.node.id);
1727         let element_ty = demand::simple(fcx, local.span, element_ty,
1728                                         ty::mk_var(fcx.ccx.tcx, locid));
1729         let bot = check_decl_local(fcx, local);
1730         check_block_no_value(fcx, body);
1731         // Unify type of decl with element type of the seq
1732         demand::simple(fcx, local.span,
1733                        ty::node_id_to_type(fcx.ccx.tcx, local.node.id),
1734                        element_ty);
1735         write::nil_ty(fcx.ccx.tcx, node_id);
1736         ret bot;
1737     }
1738
1739
1740     // A generic function for checking the then and else in an if
1741     // or if-check
1742     fn check_then_else(fcx: @fn_ctxt, thn: ast::blk,
1743                        elsopt: option::t<@ast::expr>, id: ast::node_id,
1744                        _sp: span) -> bool {
1745         let (if_t, if_bot) =
1746             alt elsopt {
1747               some(els) {
1748                 let thn_bot = check_block(fcx, thn);
1749                 let thn_t = block_ty(fcx.ccx.tcx, thn);
1750                 let els_bot = check_expr_with(fcx, els, thn_t);
1751                 let els_t = expr_ty(fcx.ccx.tcx, els);
1752                 let if_t = if !ty::type_is_bot(fcx.ccx.tcx, els_t) {
1753                     els_t
1754                 } else {
1755                     thn_t
1756                 };
1757                 (if_t, thn_bot & els_bot)
1758               }
1759               none {
1760                 check_block_no_value(fcx, thn);
1761                 (ty::mk_nil(fcx.ccx.tcx), false)
1762               }
1763             };
1764         write::ty_only_fixup(fcx, id, if_t);
1765         ret if_bot;
1766     }
1767
1768     fn binop_method(op: ast::binop) -> option::t<str> {
1769         alt op {
1770           ast::add | ast::subtract | ast::mul | ast::div | ast::rem |
1771           ast::bitxor | ast::bitand | ast::bitor | ast::lsl | ast::lsr |
1772           ast::asr { some(ast_util::binop_to_str(op)) }
1773           _ { none }
1774         }
1775     }
1776     fn lookup_op_method(fcx: @fn_ctxt, op_ex: @ast::expr, self_t: ty::t,
1777                         opname: str,
1778                         args: [option::t<@ast::expr>]) -> option::t<ty::t> {
1779         let isc = fcx.ccx.impl_map.get(op_ex.id);
1780         alt lookup_method(fcx, isc, opname, self_t, op_ex.span) {
1781           some({method_ty, n_tps: 0u, substs, origin}) {
1782             let callee_id = ast_util::op_expr_callee_id(op_ex);
1783             write::ty_fixup(fcx, callee_id, {substs: some(substs),
1784                                              ty: method_ty});
1785             check_call_or_bind(fcx, op_ex.span, method_ty, args);
1786             fcx.ccx.method_map.insert(op_ex.id, origin);
1787             some(ty::ty_fn_ret(fcx.ccx.tcx, method_ty))
1788           }
1789           _ { none }
1790         }
1791     }
1792     fn check_binop(fcx: @fn_ctxt, ex: @ast::expr, ty: ty::t,
1793                    op: ast::binop, rhs: @ast::expr) -> ty::t {
1794         let resolved_t = structurally_resolved_type(fcx, ex.span, ty);
1795         let tcx = fcx.ccx.tcx;
1796         if ty::is_binopable(tcx, resolved_t, op) {
1797             ret alt op {
1798               ast::eq | ast::lt | ast::le | ast::ne | ast::ge |
1799               ast::gt { ty::mk_bool(tcx) }
1800               _ { resolved_t }
1801             };
1802         }
1803
1804         alt binop_method(op) {
1805           some(name) {
1806             alt lookup_op_method(fcx, ex, resolved_t, name, [some(rhs)]) {
1807               some(ret_ty) { ret ret_ty; }
1808               _ {}
1809             }
1810           }
1811           _ {}
1812         }
1813         tcx.sess.span_err(
1814             ex.span, "binary operation " + ast_util::binop_to_str(op) +
1815             " cannot be applied to type `" + ty_to_str(tcx, resolved_t) +
1816             "`");
1817         resolved_t
1818     }
1819     fn check_user_unop(fcx: @fn_ctxt, op_str: str, mname: str,
1820                        ex: @ast::expr, rhs_t: ty::t) -> ty::t {
1821         alt lookup_op_method(fcx, ex, rhs_t, mname, []) {
1822           some(ret_ty) { ret_ty }
1823           _ {
1824             fcx.ccx.tcx.sess.span_err(
1825                 ex.span, #fmt["cannot apply unary operator `%s` to type `%s`",
1826                               op_str, ty_to_str(fcx.ccx.tcx, rhs_t)]);
1827             rhs_t
1828           }
1829         }
1830     }
1831
1832     let tcx = fcx.ccx.tcx;
1833     let id = expr.id;
1834     let bot = false;
1835     alt expr.node {
1836       ast::expr_lit(lit) {
1837         let typ = check_lit(fcx.ccx, lit);
1838         write::ty_only_fixup(fcx, id, typ);
1839       }
1840       ast::expr_binary(binop, lhs, rhs) {
1841         let lhs_t = next_ty_var(fcx);
1842         bot = check_expr_with(fcx, lhs, lhs_t);
1843
1844         let rhs_bot = check_expr_with(fcx, rhs, lhs_t);
1845         if !ast_util::lazy_binop(binop) { bot |= rhs_bot; }
1846
1847         let result = check_binop(fcx, expr, lhs_t, binop, rhs);
1848         write::ty_only_fixup(fcx, id, result);
1849       }
1850       ast::expr_assign_op(op, lhs, rhs) {
1851         require_impure(tcx.sess, fcx.purity, expr.span);
1852         bot = check_assignment(fcx, expr.span, lhs, rhs, id);
1853         let lhs_t = ty::expr_ty(tcx, lhs);
1854         let result = check_binop(fcx, expr, lhs_t, op, rhs);
1855         demand::simple(fcx, expr.span, result, lhs_t);
1856       }
1857       ast::expr_unary(unop, oper) {
1858         bot = check_expr(fcx, oper);
1859         let oper_t = expr_ty(tcx, oper);
1860         alt unop {
1861           ast::box(mut) { oper_t = ty::mk_box(tcx, {ty: oper_t, mut: mut}); }
1862           ast::uniq(mut) {
1863             oper_t = ty::mk_uniq(tcx, {ty: oper_t, mut: mut});
1864           }
1865           ast::deref {
1866             alt structure_of(fcx, expr.span, oper_t) {
1867               ty::ty_box(inner) { oper_t = inner.ty; }
1868               ty::ty_uniq(inner) { oper_t = inner.ty; }
1869               ty::ty_res(_, inner, _) { oper_t = inner; }
1870               ty::ty_enum(id, tps) {
1871                 let variants = ty::enum_variants(tcx, id);
1872                 if vec::len(*variants) != 1u ||
1873                        vec::len(variants[0].args) != 1u {
1874                     tcx.sess.span_fatal(expr.span,
1875                                         "can only dereference enums " +
1876                                         "with a single variant which has a "
1877                                             + "single argument");
1878                 }
1879                 oper_t =
1880                     ty::substitute_type_params(tcx, tps, variants[0].args[0]);
1881               }
1882               ty::ty_ptr(inner) {
1883                 oper_t = inner.ty;
1884                 require_unsafe(tcx.sess, fcx.purity, expr.span);
1885               }
1886               _ {
1887                 tcx.sess.span_fatal(expr.span,
1888                                     "dereferencing non-" +
1889                                         "dereferenceable type: " +
1890                                         ty_to_str(tcx, oper_t));
1891               }
1892             }
1893           }
1894           ast::not {
1895             oper_t = structurally_resolved_type(fcx, oper.span, oper_t);
1896             if !(ty::type_is_integral(tcx, oper_t) ||
1897                  ty::struct(tcx, oper_t) == ty::ty_bool) {
1898                 oper_t = check_user_unop(fcx, "!", "!", expr, oper_t);
1899             }
1900           }
1901           ast::neg {
1902             oper_t = structurally_resolved_type(fcx, oper.span, oper_t);
1903             if !(ty::type_is_integral(tcx, oper_t) ||
1904                  ty::type_is_fp(tcx, oper_t)) {
1905                 oper_t = check_user_unop(fcx, "-", "unary-", expr, oper_t);
1906             }
1907           }
1908         }
1909         write::ty_only_fixup(fcx, id, oper_t);
1910       }
1911       ast::expr_path(pth) {
1912         let defn = lookup_def(fcx, pth.span, id);
1913
1914         let tpt = ty_param_bounds_and_ty_for_def(fcx, expr.span, defn);
1915         if ty::def_has_ty_params(defn) {
1916             let path_tpot = instantiate_path(fcx, pth, tpt, expr.span);
1917             write::ty_fixup(fcx, id, path_tpot);
1918         } else {
1919             // The definition doesn't take type parameters. If the programmer
1920             // supplied some, that's an error
1921             if vec::len::<@ast::ty>(pth.node.types) > 0u {
1922                 tcx.sess.span_fatal(expr.span,
1923                                     "this kind of value does not \
1924                                      take type parameters");
1925             }
1926             write::ty_only_fixup(fcx, id, tpt.ty);
1927         }
1928       }
1929       ast::expr_mac(_) { tcx.sess.bug("unexpanded macro"); }
1930       ast::expr_fail(expr_opt) {
1931         bot = true;
1932         alt expr_opt {
1933           none {/* do nothing */ }
1934           some(e) { check_expr_with(fcx, e, ty::mk_str(tcx)); }
1935         }
1936         write::bot_ty(tcx, id);
1937       }
1938       ast::expr_break { write::bot_ty(tcx, id); bot = true; }
1939       ast::expr_cont { write::bot_ty(tcx, id); bot = true; }
1940       ast::expr_ret(expr_opt) {
1941         bot = true;
1942         alt expr_opt {
1943           none {
1944             let nil = ty::mk_nil(tcx);
1945             if !are_compatible(fcx, fcx.ret_ty, nil) {
1946                 tcx.sess.span_err(expr.span,
1947                                   "ret; in function returning non-nil");
1948             }
1949           }
1950           some(e) { check_expr_with(fcx, e, fcx.ret_ty); }
1951         }
1952         write::bot_ty(tcx, id);
1953       }
1954       ast::expr_be(e) {
1955         // FIXME: prove instead of assert
1956         assert (ast_util::is_call_expr(e));
1957         check_expr_with(fcx, e, fcx.ret_ty);
1958         bot = true;
1959         write::nil_ty(tcx, id);
1960       }
1961       ast::expr_log(_, lv, e) {
1962         bot = check_expr_with(fcx, lv, ty::mk_mach_uint(tcx, ast::ty_u32));
1963         bot |= check_expr(fcx, e);
1964         write::nil_ty(tcx, id);
1965       }
1966       ast::expr_check(_, e) {
1967         bot = check_pred_expr(fcx, e);
1968         write::nil_ty(tcx, id);
1969       }
1970       ast::expr_if_check(cond, thn, elsopt) {
1971         bot =
1972             check_pred_expr(fcx, cond) |
1973                 check_then_else(fcx, thn, elsopt, id, expr.span);
1974       }
1975       ast::expr_ternary(_, _, _) {
1976         bot = check_expr(fcx, ast_util::ternary_to_if(expr));
1977       }
1978       ast::expr_assert(e) {
1979         bot = check_expr_with(fcx, e, ty::mk_bool(tcx));
1980         write::nil_ty(tcx, id);
1981       }
1982       ast::expr_copy(a) {
1983         bot = check_expr_with_unifier(fcx, a, unify, expected);
1984         let tpot =
1985             ty::node_id_to_ty_param_substs_opt_and_ty(tcx, a.id);
1986         write::ty_fixup(fcx, id, tpot);
1987
1988       }
1989       ast::expr_move(lhs, rhs) {
1990         require_impure(tcx.sess, fcx.purity, expr.span);
1991         bot = check_assignment(fcx, expr.span, lhs, rhs, id);
1992       }
1993       ast::expr_assign(lhs, rhs) {
1994         require_impure(tcx.sess, fcx.purity, expr.span);
1995         bot = check_assignment(fcx, expr.span, lhs, rhs, id);
1996       }
1997       ast::expr_swap(lhs, rhs) {
1998         require_impure(tcx.sess, fcx.purity, expr.span);
1999         bot = check_assignment(fcx, expr.span, lhs, rhs, id);
2000       }
2001       ast::expr_if(cond, thn, elsopt) {
2002         bot =
2003             check_expr_with(fcx, cond, ty::mk_bool(tcx)) |
2004                 check_then_else(fcx, thn, elsopt, id, expr.span);
2005       }
2006       ast::expr_for(decl, seq, body) {
2007         bot = check_expr(fcx, seq);
2008         let elt_ty;
2009         let ety = expr_ty(tcx, seq);
2010         alt structure_of(fcx, expr.span, ety) {
2011           ty::ty_vec(vec_elt_ty) { elt_ty = vec_elt_ty.ty; }
2012           ty::ty_str { elt_ty = ty::mk_mach_uint(tcx, ast::ty_u8); }
2013           _ {
2014             tcx.sess.span_fatal(expr.span,
2015                                 "mismatched types: expected vector or string "
2016                                 + "but found `" + ty_to_str(tcx, ety) + "`");
2017           }
2018         }
2019         bot |= check_for(fcx, decl, elt_ty, body, id);
2020       }
2021       ast::expr_while(cond, body) {
2022         bot = check_expr_with(fcx, cond, ty::mk_bool(tcx));
2023         check_block_no_value(fcx, body);
2024         write::ty_only_fixup(fcx, id, ty::mk_nil(tcx));
2025       }
2026       ast::expr_do_while(body, cond) {
2027         bot = check_expr_with(fcx, cond, ty::mk_bool(tcx)) |
2028               check_block_no_value(fcx, body);
2029         write::ty_only_fixup(fcx, id, block_ty(tcx, body));
2030       }
2031       ast::expr_alt(expr, arms) {
2032         bot = check_expr(fcx, expr);
2033
2034         // Typecheck the patterns first, so that we get types for all the
2035         // bindings.
2036         let pattern_ty = ty::expr_ty(tcx, expr);
2037         for arm: ast::arm in arms {
2038             let id_map = pat_util::pat_id_map(tcx, arm.pats[0]);
2039             for p: @ast::pat in arm.pats {
2040                 check_pat(fcx, id_map, p, pattern_ty);
2041             }
2042         }
2043         // Now typecheck the blocks.
2044         let result_ty = next_ty_var(fcx);
2045         let arm_non_bot = false;
2046         for arm: ast::arm in arms {
2047             alt arm.guard {
2048               some(e) { check_expr_with(fcx, e, ty::mk_bool(tcx)); }
2049               none { }
2050             }
2051             if !check_block(fcx, arm.body) { arm_non_bot = true; }
2052             let bty = block_ty(tcx, arm.body);
2053             result_ty = demand::simple(fcx, arm.body.span, result_ty, bty);
2054         }
2055         bot |= !arm_non_bot;
2056         if !arm_non_bot { result_ty = ty::mk_bot(tcx); }
2057         write::ty_only_fixup(fcx, id, result_ty);
2058       }
2059       ast::expr_fn(proto, decl, body, captures) {
2060         check_expr_fn_with_unifier(fcx, expr, proto, decl, body,
2061                                    unify, expected);
2062         capture::check_capture_clause(tcx, expr.id, proto, *captures);
2063       }
2064       ast::expr_fn_block(decl, body) {
2065         // Take the prototype from the expected type, but default to block:
2066         let proto = alt ty::struct(tcx, expected) {
2067           ty::ty_fn({proto, _}) { proto }
2068           _ {
2069             tcx.sess.span_warn(expr.span, "unable to infer kind of closure, \
2070                                            defaulting to block");
2071             ast::proto_block
2072           }
2073         };
2074         #debug("checking expr_fn_block %s expected=%s",
2075                expr_to_str(expr),
2076                ty_to_str(tcx, expected));
2077         check_expr_fn_with_unifier(fcx, expr, proto, decl, body,
2078                                    unify, expected);
2079         write::ty_only_fixup(fcx, id, expected);
2080       }
2081       ast::expr_block(b) {
2082         // If this is an unchecked block, turn off purity-checking
2083         bot = check_block(fcx, b);
2084         let typ =
2085             alt b.node.expr {
2086               some(expr) { expr_ty(tcx, expr) }
2087               none { ty::mk_nil(tcx) }
2088             };
2089         write::ty_only_fixup(fcx, id, typ);
2090       }
2091       ast::expr_bind(f, args) {
2092         // Call the generic checker.
2093         bot = check_expr(fcx, f);
2094         bot |= check_call_or_bind(fcx, expr.span, expr_ty(tcx, f), args);
2095
2096         // Pull the argument and return types out.
2097         let proto, arg_tys, rt, cf, constrs;
2098         alt structure_of(fcx, expr.span, expr_ty(tcx, f)) {
2099           // FIXME:
2100           // probably need to munge the constrs to drop constraints
2101           // for any bound args
2102           ty::ty_fn(f) {
2103             proto = f.proto;
2104             arg_tys = f.inputs;
2105             rt = f.output;
2106             cf = f.ret_style;
2107             constrs = f.constraints;
2108           }
2109           _ { fail "LHS of bind expr didn't have a function type?!"; }
2110         }
2111
2112         // For each blank argument, add the type of that argument
2113         // to the resulting function type.
2114         let out_args = [];
2115         let i = 0u;
2116         while i < vec::len(args) {
2117             alt args[i] {
2118               some(_) {/* no-op */ }
2119               none { out_args += [arg_tys[i]]; }
2120             }
2121             i += 1u;
2122         }
2123
2124         // Determine what fn prototype results from binding
2125         fn lower_bound_proto(proto: ast::proto) -> ast::proto {
2126             // FIXME: This is right for bare fns, possibly not others
2127             alt proto {
2128               ast::proto_bare { ast::proto_box }
2129               _ { proto }
2130             }
2131         }
2132
2133         let ft = ty::mk_fn(tcx, {proto: lower_bound_proto(proto),
2134                                  inputs: out_args, output: rt,
2135                                  ret_style: cf, constraints: constrs});
2136         write::ty_only_fixup(fcx, id, ft);
2137       }
2138       ast::expr_call(f, args, _) {
2139         bot = check_call_full(fcx, expr.span, f, args, expr.id);
2140       }
2141       ast::expr_cast(e, t) {
2142         bot = check_expr(fcx, e);
2143         let t_1 = ast_ty_to_ty_crate(fcx.ccx, t);
2144         let t_e = ty::expr_ty(tcx, e);
2145
2146         alt ty::struct(tcx, t_1) {
2147           // This will be looked up later on
2148           ty::ty_iface(_, _) {}
2149           _ {
2150             if ty::type_is_nil(tcx, t_e) {
2151                 tcx.sess.span_err(expr.span, "cast from nil: " +
2152                                   ty_to_str(tcx, t_e) + " as " +
2153                                   ty_to_str(tcx, t_1));
2154             } else if ty::type_is_nil(tcx, t_1) {
2155                 tcx.sess.span_err(expr.span, "cast to nil: " +
2156                                   ty_to_str(tcx, t_e) + " as " +
2157                                   ty_to_str(tcx, t_1));
2158             }
2159
2160             let t_1_is_scalar = type_is_scalar(fcx, expr.span, t_1);
2161             if type_is_c_like_enum(fcx,expr.span,t_e) && t_1_is_scalar {
2162                 /* this case is allowed */
2163             } else if !(type_is_scalar(fcx,expr.span,t_e) && t_1_is_scalar) {
2164                 // FIXME there are more forms of cast to support, eventually.
2165                 tcx.sess.span_err(expr.span,
2166                                   "non-scalar cast: " +
2167                                   ty_to_str(tcx, t_e) + " as " +
2168                                   ty_to_str(tcx, t_1));
2169             }
2170           }
2171         }
2172         write::ty_only_fixup(fcx, id, t_1);
2173       }
2174       ast::expr_vec(args, mut) {
2175         let t: ty::t = next_ty_var(fcx);
2176         for e: @ast::expr in args { bot |= check_expr_with(fcx, e, t); }
2177         let typ = ty::mk_vec(tcx, {ty: t, mut: mut});
2178         write::ty_only_fixup(fcx, id, typ);
2179       }
2180       ast::expr_tup(elts) {
2181         let elt_ts = [];
2182         vec::reserve(elt_ts, vec::len(elts));
2183         for e in elts {
2184             check_expr(fcx, e);
2185             let ety = expr_ty(tcx, e);
2186             elt_ts += [ety];
2187         }
2188         let typ = ty::mk_tup(tcx, elt_ts);
2189         write::ty_only_fixup(fcx, id, typ);
2190       }
2191       ast::expr_rec(fields, base) {
2192         alt base { none {/* no-op */ } some(b_0) { check_expr(fcx, b_0); } }
2193         let fields_t: [spanned<field>] = [];
2194         for f: ast::field in fields {
2195             bot |= check_expr(fcx, f.node.expr);
2196             let expr_t = expr_ty(tcx, f.node.expr);
2197             let expr_mt = {ty: expr_t, mut: f.node.mut};
2198             // for the most precise error message,
2199             // should be f.node.expr.span, not f.span
2200             fields_t +=
2201                 [respan(f.node.expr.span,
2202                         {ident: f.node.ident, mt: expr_mt})];
2203         }
2204         alt base {
2205           none {
2206             fn get_node(f: spanned<field>) -> field { f.node }
2207             let typ = ty::mk_rec(tcx, vec::map(fields_t, get_node));
2208             write::ty_only_fixup(fcx, id, typ);
2209           }
2210           some(bexpr) {
2211             bot |= check_expr(fcx, bexpr);
2212             let bexpr_t = expr_ty(tcx, bexpr);
2213             let base_fields: [field] = [];
2214             alt structure_of(fcx, expr.span, bexpr_t) {
2215               ty::ty_rec(flds) { base_fields = flds; }
2216               _ {
2217                 tcx.sess.span_fatal(expr.span,
2218                                     "record update has non-record base");
2219               }
2220             }
2221             write::ty_only_fixup(fcx, id, bexpr_t);
2222             for f: spanned<ty::field> in fields_t {
2223                 let found = false;
2224                 for bf: ty::field in base_fields {
2225                     if str::eq(f.node.ident, bf.ident) {
2226                         demand::simple(fcx, f.span, bf.mt.ty, f.node.mt.ty);
2227                         found = true;
2228                     }
2229                 }
2230                 if !found {
2231                     tcx.sess.span_fatal(f.span,
2232                                         "unknown field in record update: " +
2233                                             f.node.ident);
2234                 }
2235             }
2236           }
2237         }
2238       }
2239       ast::expr_field(base, field, tys) {
2240         bot |= check_expr(fcx, base);
2241         let expr_t = structurally_resolved_type(fcx, expr.span,
2242                                                 expr_ty(tcx, base));
2243         let base_t = do_autoderef(fcx, expr.span, expr_t);
2244         let handled = false, n_tys = vec::len(tys);
2245         alt structure_of(fcx, expr.span, base_t) {
2246           ty::ty_rec(fields) {
2247             alt ty::field_idx(field, fields) {
2248               some(ix) {
2249                 if n_tys > 0u {
2250                     tcx.sess.span_err(expr.span,
2251                                       "can't provide type parameters \
2252                                        to a field access");
2253                 }
2254                 write::ty_only_fixup(fcx, id, fields[ix].mt.ty);
2255                 handled = true;
2256               }
2257               _ {}
2258             }
2259           }
2260           _ {}
2261         }
2262         if !handled {
2263             let iscope = fcx.ccx.impl_map.get(expr.id);
2264             alt lookup_method(fcx, iscope, field, expr_t, expr.span) {
2265               some({method_ty: fty, n_tps: method_n_tps, substs, origin}) {
2266                 let substs = substs, n_tps = vec::len(substs);
2267                 if method_n_tps + n_tps > 0u {
2268                     if n_tys > 0u {
2269                         if n_tys != method_n_tps {
2270                             tcx.sess.span_fatal
2271                                 (expr.span, "incorrect number of type \
2272                                            parameters given for this method");
2273
2274                         }
2275                         for ty in tys {
2276                             substs += [ast_ty_to_ty_crate(fcx.ccx, ty)];
2277                         }
2278                     } else {
2279                         let i = 0u;
2280                         while i < method_n_tps {
2281                             substs += [ty::mk_var(tcx, next_ty_var_id(fcx))];
2282                             i += 1u;
2283                         }
2284                     }
2285                     write::ty_fixup(fcx, id, {substs: some(substs), ty: fty});
2286                 } else if n_tys > 0u {
2287                     tcx.sess.span_fatal(expr.span,
2288                                         "this method does not take type \
2289                                          parameters");
2290                 } else {
2291                     write::ty_only_fixup(fcx, id, fty);
2292                 }
2293                 fcx.ccx.method_map.insert(id, origin);
2294               }
2295               none {
2296                 let t_err = resolve_type_vars_if_possible(fcx, expr_t);
2297                 let msg = #fmt["attempted access of field %s on type %s, but \
2298                                 no method implementation was found",
2299                                field, ty_to_str(tcx, t_err)];
2300                 tcx.sess.span_err(expr.span, msg);
2301                 // NB: Adding a bogus type to allow typechecking to continue
2302                 write::ty_only_fixup(fcx, id, ty::mk_nil(tcx));
2303               }
2304             }
2305         }
2306       }
2307       ast::expr_index(base, idx) {
2308         bot |= check_expr(fcx, base);
2309         let raw_base_t = expr_ty(tcx, base);
2310         let base_t = do_autoderef(fcx, expr.span, raw_base_t);
2311         bot |= check_expr(fcx, idx);
2312         let idx_t = expr_ty(tcx, idx);
2313         fn require_integral(fcx: @fn_ctxt, sp: span, t: ty::t) {
2314             if !type_is_integral(fcx, sp, t) {
2315                 fcx.ccx.tcx.sess.span_err(sp, "mismatched types: expected \
2316                                                `integer` but found `"
2317                                   + ty_to_str(fcx.ccx.tcx, t) + "`");
2318             }
2319         }
2320         alt structure_of(fcx, expr.span, base_t) {
2321           ty::ty_vec(mt) {
2322             require_integral(fcx, idx.span, idx_t);
2323             write::ty_only_fixup(fcx, id, mt.ty);
2324           }
2325           ty::ty_str {
2326             require_integral(fcx, idx.span, idx_t);
2327             let typ = ty::mk_mach_uint(tcx, ast::ty_u8);
2328             write::ty_only_fixup(fcx, id, typ);
2329           }
2330           _ {
2331             let resolved = structurally_resolved_type(fcx, expr.span,
2332                                                       raw_base_t);
2333             alt lookup_op_method(fcx, expr, resolved, "[]",
2334                                  [some(idx)]) {
2335               some(ret_ty) { write::ty_only_fixup(fcx, id, ret_ty); }
2336               _ {
2337                 tcx.sess.span_fatal(
2338                     expr.span, "cannot index a value of type `" +
2339                     ty_to_str(tcx, base_t) + "`");
2340               }
2341             }
2342           }
2343         }
2344       }
2345       _ { tcx.sess.unimpl("expr type in typeck::check_expr"); }
2346     }
2347     if bot { write::ty_only_fixup(fcx, expr.id, ty::mk_bot(tcx)); }
2348
2349     unify(fcx, expr.span, expected, expr_ty(tcx, expr));
2350     ret bot;
2351 }
2352
2353 fn next_ty_var_id(fcx: @fn_ctxt) -> int {
2354     let id = *fcx.next_var_id;
2355     *fcx.next_var_id += 1;
2356     ret id;
2357 }
2358
2359 fn next_ty_var(fcx: @fn_ctxt) -> ty::t {
2360     ret ty::mk_var(fcx.ccx.tcx, next_ty_var_id(fcx));
2361 }
2362
2363 fn bind_params(fcx: @fn_ctxt, tp: ty::t, count: uint)
2364     -> {vars: [ty::t], ty: ty::t} {
2365     let vars = vec::init_fn(count, {|_i| next_ty_var(fcx)});
2366     {vars: vars, ty: ty::substitute_type_params(fcx.ccx.tcx, vars, tp)}
2367 }
2368
2369 fn get_self_info(ccx: @crate_ctxt) -> option::t<self_info> {
2370     ret vec::last(ccx.self_infos);
2371 }
2372
2373 fn check_decl_initializer(fcx: @fn_ctxt, nid: ast::node_id,
2374                           init: ast::initializer) -> bool {
2375     let lty = ty::mk_var(fcx.ccx.tcx, lookup_local(fcx, init.expr.span, nid));
2376     ret check_expr_with(fcx, init.expr, lty);
2377 }
2378
2379 fn check_decl_local(fcx: @fn_ctxt, local: @ast::local) -> bool {
2380     let bot = false;
2381
2382     alt fcx.locals.find(local.node.id) {
2383       some(i) {
2384         let t = ty::mk_var(fcx.ccx.tcx, i);
2385         write::ty_only_fixup(fcx, local.node.id, t);
2386         alt local.node.init {
2387           some(init) {
2388             bot = check_decl_initializer(fcx, local.node.id, init);
2389           }
2390           _ {/* fall through */ }
2391         }
2392         let id_map = pat_util::pat_id_map(fcx.ccx.tcx, local.node.pat);
2393         check_pat(fcx, id_map, local.node.pat, t);
2394       }
2395     }
2396     ret bot;
2397 }
2398
2399 fn check_stmt(fcx: @fn_ctxt, stmt: @ast::stmt) -> bool {
2400     let node_id;
2401     let bot = false;
2402     alt stmt.node {
2403       ast::stmt_decl(decl, id) {
2404         node_id = id;
2405         alt decl.node {
2406           ast::decl_local(ls) {
2407             for (_, l) in ls { bot |= check_decl_local(fcx, l); }
2408           }
2409           ast::decl_item(_) {/* ignore for now */ }
2410         }
2411       }
2412       ast::stmt_expr(expr, id) {
2413         node_id = id;
2414         bot = check_expr_with(fcx, expr, ty::mk_nil(fcx.ccx.tcx));
2415       }
2416       ast::stmt_semi(expr, id) {
2417         node_id = id;
2418         bot = check_expr(fcx, expr);
2419       }
2420     }
2421     write::nil_ty(fcx.ccx.tcx, node_id);
2422     ret bot;
2423 }
2424
2425 fn check_block_no_value(fcx: @fn_ctxt, blk: ast::blk) -> bool {
2426     let bot = check_block(fcx, blk);
2427     if !bot {
2428         let blkty = ty::node_id_to_monotype(fcx.ccx.tcx, blk.node.id);
2429         let nilty = ty::mk_nil(fcx.ccx.tcx);
2430         demand::simple(fcx, blk.span, nilty, blkty);
2431     }
2432     ret bot;
2433 }
2434
2435 fn check_block(fcx0: @fn_ctxt, blk: ast::blk) -> bool {
2436     let fcx = alt blk.node.rules {
2437       ast::unchecked_blk { @{purity: ast::impure_fn with *fcx0} }
2438       ast::unsafe_blk { @{purity: ast::unsafe_fn with *fcx0} }
2439       ast::default_blk { fcx0 }
2440     };
2441     let bot = false;
2442     let warned = false;
2443     for s: @ast::stmt in blk.node.stmts {
2444         if bot && !warned &&
2445                alt s.node {
2446                  ast::stmt_decl(@{node: ast::decl_local(_), _}, _) |
2447                  ast::stmt_expr(_, _) | ast::stmt_semi(_, _) {
2448                    true
2449                  }
2450                  _ { false }
2451                } {
2452             fcx.ccx.tcx.sess.span_warn(s.span, "unreachable statement");
2453             warned = true;
2454         }
2455         bot |= check_stmt(fcx, s);
2456     }
2457     alt blk.node.expr {
2458       none { write::nil_ty(fcx.ccx.tcx, blk.node.id); }
2459       some(e) {
2460         if bot && !warned {
2461             fcx.ccx.tcx.sess.span_warn(e.span, "unreachable expression");
2462         }
2463         bot |= check_expr(fcx, e);
2464         let ety = expr_ty(fcx.ccx.tcx, e);
2465         write::ty_only_fixup(fcx, blk.node.id, ety);
2466       }
2467     }
2468     if bot {
2469         write::ty_only_fixup(fcx, blk.node.id, ty::mk_bot(fcx.ccx.tcx));
2470     }
2471     ret bot;
2472 }
2473
2474 fn check_const(ccx: @crate_ctxt, _sp: span, e: @ast::expr, id: ast::node_id) {
2475     // FIXME: this is kinda a kludge; we manufacture a fake function context
2476     // and statement context for checking the initializer expression.
2477     let rty = node_id_to_type(ccx.tcx, id);
2478     let fixups: [ast::node_id] = [];
2479     let fcx: @fn_ctxt =
2480         @{ret_ty: rty,
2481           purity: ast::pure_fn,
2482           proto: ast::proto_box,
2483           var_bindings: ty::unify::mk_var_bindings(),
2484           locals: new_int_hash::<int>(),
2485           next_var_id: @mutable 0,
2486           mutable fixups: fixups,
2487           ccx: ccx};
2488     check_expr(fcx, e);
2489     let cty = expr_ty(fcx.ccx.tcx, e);
2490     let declty = fcx.ccx.tcx.tcache.get(local_def(id)).ty;
2491     demand::simple(fcx, e.span, declty, cty);
2492 }
2493
2494 fn check_enum_variants(ccx: @crate_ctxt, sp: span, vs: [ast::variant],
2495                       id: ast::node_id) {
2496     // FIXME: this is kinda a kludge; we manufacture a fake function context
2497     // and statement context for checking the initializer expression.
2498     let rty = node_id_to_type(ccx.tcx, id);
2499     let fixups: [ast::node_id] = [];
2500     let fcx: @fn_ctxt =
2501         @{ret_ty: rty,
2502           purity: ast::pure_fn,
2503           proto: ast::proto_box,
2504           var_bindings: ty::unify::mk_var_bindings(),
2505           locals: new_int_hash::<int>(),
2506           next_var_id: @mutable 0,
2507           mutable fixups: fixups,
2508           ccx: ccx};
2509     let disr_vals: [int] = [];
2510     let disr_val = 0;
2511     for v in vs {
2512         alt v.node.disr_expr {
2513           some(e) {
2514             check_expr(fcx, e);
2515             let cty = expr_ty(fcx.ccx.tcx, e);
2516             let declty = ty::mk_int(fcx.ccx.tcx);
2517             demand::simple(fcx, e.span, declty, cty);
2518             // FIXME: issue #1417
2519             // Also, check_expr (from check_const pass) doesn't guarantee that
2520             // the expression in an form that eval_const_expr can handle, so
2521             // we may still get an internal compiler error
2522             alt syntax::ast_util::eval_const_expr(e) {
2523               syntax::ast_util::const_int(val) {
2524                 disr_val = val as int;
2525               }
2526               _ {
2527                 ccx.tcx.sess.span_err(e.span,
2528                                       "expected signed integer constant");
2529               }
2530             }
2531           }
2532           _ {}
2533         }
2534         if vec::member(disr_val, disr_vals) {
2535             ccx.tcx.sess.span_err(v.span,
2536                                   "discriminator value already exists.");
2537         }
2538         disr_vals += [disr_val];
2539         disr_val += 1;
2540     }
2541     let outer = true, did = local_def(id);
2542     if ty::type_structurally_contains(ccx.tcx, rty, {|sty|
2543         alt sty {
2544           ty::ty_enum(id, _) if id == did {
2545             if outer { outer = false; false }
2546             else { true }
2547           }
2548           _ { false }
2549         }
2550     }) {
2551         ccx.tcx.sess.span_fatal(sp, "illegal recursive enum type. \
2552                                      wrap the inner value in a box to \
2553                                      make it represenable");
2554     }
2555 }
2556
2557 // A generic function for checking the pred in a check
2558 // or if-check
2559 fn check_pred_expr(fcx: @fn_ctxt, e: @ast::expr) -> bool {
2560     let bot = check_expr_with(fcx, e, ty::mk_bool(fcx.ccx.tcx));
2561
2562     /* e must be a call expr where all arguments are either
2563     literals or slots */
2564     alt e.node {
2565       ast::expr_call(operator, operands, _) {
2566         if !ty::is_pred_ty(fcx.ccx.tcx, expr_ty(fcx.ccx.tcx, operator)) {
2567             fcx.ccx.tcx.sess.span_err
2568                 (operator.span,
2569                  "operator in constraint has non-boolean return type");
2570         }
2571
2572         alt operator.node {
2573           ast::expr_path(oper_name) {
2574             alt fcx.ccx.tcx.def_map.find(operator.id) {
2575               some(ast::def_fn(_, ast::pure_fn)) {
2576                 // do nothing
2577               }
2578               _ {
2579                 fcx.ccx.tcx.sess.span_err(operator.span,
2580                                             "Impure function as operator \
2581                                              in constraint");
2582               }
2583             }
2584             for operand: @ast::expr in operands {
2585                 if !ast_util::is_constraint_arg(operand) {
2586                     let s =
2587                         "Constraint args must be slot variables or literals";
2588                     fcx.ccx.tcx.sess.span_err(e.span, s);
2589                 }
2590             }
2591           }
2592           _ {
2593             let s = "In a constraint, expected the \
2594                      constraint name to be an explicit name";
2595             fcx.ccx.tcx.sess.span_err(e.span, s);
2596           }
2597         }
2598       }
2599       _ { fcx.ccx.tcx.sess.span_err(e.span, "check on non-predicate"); }
2600     }
2601     ret bot;
2602 }
2603
2604 fn check_constraints(fcx: @fn_ctxt, cs: [@ast::constr], args: [ast::arg]) {
2605     let c_args;
2606     let num_args = vec::len(args);
2607     for c: @ast::constr in cs {
2608         c_args = [];
2609         for a: @spanned<ast::fn_constr_arg> in c.node.args {
2610             c_args += [
2611                  // "base" should not occur in a fn type thing, as of
2612                  // yet, b/c we don't allow constraints on the return type
2613
2614                  // Works b/c no higher-order polymorphism
2615                  /*
2616                  This is kludgy, and we probably shouldn't be assigning
2617                  node IDs here, but we're creating exprs that are
2618                  ephemeral, just for the purposes of typechecking. So
2619                  that's my justification.
2620                  */
2621                  @alt a.node {
2622                     ast::carg_base {
2623                       fcx.ccx.tcx.sess.span_bug(a.span,
2624                                                 "check_constraints:\
2625                     unexpected carg_base");
2626                     }
2627                     ast::carg_lit(l) {
2628                       let tmp_node_id = fcx.ccx.tcx.sess.next_node_id();
2629                       {id: tmp_node_id, node: ast::expr_lit(l), span: a.span}
2630                     }
2631                     ast::carg_ident(i) {
2632                       if i < num_args {
2633                           let p: ast::path_ =
2634                               {global: false,
2635                                idents: [args[i].ident],
2636                                types: []};
2637                           let arg_occ_node_id =
2638                               fcx.ccx.tcx.sess.next_node_id();
2639                           fcx.ccx.tcx.def_map.insert
2640                               (arg_occ_node_id,
2641                                ast::def_arg(local_def(args[i].id),
2642                                             args[i].mode));
2643                           {id: arg_occ_node_id,
2644                            node: ast::expr_path(@respan(a.span, p)),
2645                            span: a.span}
2646                       } else {
2647                           fcx.ccx.tcx.sess.span_bug(a.span,
2648                                                     "check_constraints:\
2649                      carg_ident index out of bounds");
2650                       }
2651                     }
2652                   }];
2653         }
2654         let p_op: ast::expr_ = ast::expr_path(c.node.path);
2655         let oper: @ast::expr = @{id: c.node.id, node: p_op, span: c.span};
2656         // Another ephemeral expr
2657         let call_expr_id = fcx.ccx.tcx.sess.next_node_id();
2658         let call_expr =
2659             @{id: call_expr_id,
2660               node: ast::expr_call(oper, c_args, false),
2661               span: c.span};
2662         check_pred_expr(fcx, call_expr);
2663     }
2664 }
2665
2666 fn check_fn(ccx: @crate_ctxt,
2667             proto: ast::proto,
2668             decl: ast::fn_decl,
2669             body: ast::blk,
2670             id: ast::node_id,
2671             old_fcx: option::t<@fn_ctxt>) {
2672     // If old_fcx is some(...), this is a block fn { |x| ... }.
2673     // In that case, the purity is inherited from the context.
2674     let purity = alt old_fcx {
2675       none { decl.purity }
2676       some(f) { assert decl.purity == ast::impure_fn; f.purity }
2677     };
2678
2679     let gather_result = gather_locals(ccx, decl, body, id, old_fcx);
2680     let fixups: [ast::node_id] = [];
2681     let fcx: @fn_ctxt =
2682         @{ret_ty: ty::ty_fn_ret(ccx.tcx, ty::node_id_to_type(ccx.tcx, id)),
2683           purity: purity,
2684           proto: proto,
2685           var_bindings: gather_result.var_bindings,
2686           locals: gather_result.locals,
2687           next_var_id: gather_result.next_var_id,
2688           mutable fixups: fixups,
2689           ccx: ccx};
2690
2691     check_constraints(fcx, decl.constraints, decl.inputs);
2692     check_block(fcx, body);
2693
2694     // We unify the tail expr's type with the
2695     // function result type, if there is a tail expr.
2696     alt body.node.expr {
2697       some(tail_expr) {
2698         let tail_expr_ty = expr_ty(ccx.tcx, tail_expr);
2699         demand::simple(fcx, tail_expr.span, fcx.ret_ty, tail_expr_ty);
2700       }
2701       none { }
2702     }
2703
2704     let args = ty::ty_fn_args(ccx.tcx, ty::node_id_to_type(ccx.tcx, id));
2705     let i = 0u;
2706     for arg: ty::arg in args {
2707         write::ty_only_fixup(fcx, decl.inputs[i].id, arg.ty);
2708         i += 1u;
2709     }
2710
2711     // If we don't have any enclosing function scope, it is time to
2712     // force any remaining type vars to be resolved.
2713     // If we have an enclosing function scope, our type variables will be
2714     // resolved when the enclosing scope finishes up.
2715     if option::is_none(old_fcx) {
2716         dict::resolve_in_block(fcx, body);
2717         writeback::resolve_type_vars_in_block(fcx, body);
2718     }
2719 }
2720
2721 fn check_method(ccx: @crate_ctxt, method: @ast::method) {
2722     check_fn(ccx, ast::proto_bare, method.decl, method.body, method.id, none);
2723 }
2724
2725 fn check_item(ccx: @crate_ctxt, it: @ast::item) {
2726     alt it.node {
2727       ast::item_const(_, e) { check_const(ccx, it.span, e, it.id); }
2728       ast::item_enum(vs, _) { check_enum_variants(ccx, it.span, vs, it.id); }
2729       ast::item_fn(decl, tps, body) {
2730         check_fn(ccx, ast::proto_bare, decl, body, it.id, none);
2731       }
2732       ast::item_res(decl, tps, body, dtor_id, _) {
2733         check_fn(ccx, ast::proto_bare, decl, body, dtor_id, none);
2734       }
2735       ast::item_impl(tps, _, ty, ms) {
2736         ccx.self_infos += [self_impl(ast_ty_to_ty(ccx.tcx, m_check, ty))];
2737         for m in ms { check_method(ccx, m); }
2738         vec::pop(ccx.self_infos);
2739       }
2740       _ {/* nothing to do */ }
2741     }
2742 }
2743
2744 fn arg_is_argv_ty(tcx: ty::ctxt, a: ty::arg) -> bool {
2745     alt ty::struct(tcx, a.ty) {
2746       ty::ty_vec(mt) {
2747         if mt.mut != ast::imm { ret false; }
2748         alt ty::struct(tcx, mt.ty) {
2749           ty::ty_str { ret true; }
2750           _ { ret false; }
2751         }
2752       }
2753       _ { ret false; }
2754     }
2755 }
2756
2757 fn check_main_fn_ty(tcx: ty::ctxt, main_id: ast::node_id) {
2758     let main_t = ty::node_id_to_monotype(tcx, main_id);
2759     alt ty::struct(tcx, main_t) {
2760       ty::ty_fn({proto: ast::proto_bare, inputs, output,
2761                  ret_style: ast::return_val, constraints}) {
2762         let ok = vec::len(constraints) == 0u;
2763         ok &= ty::type_is_nil(tcx, output);
2764         let num_args = vec::len(inputs);
2765         ok &= num_args == 0u || num_args == 1u &&
2766               arg_is_argv_ty(tcx, inputs[0]);
2767         if !ok {
2768             let span = ast_map::node_span(tcx.items.get(main_id));
2769             tcx.sess.span_err(span,
2770                               "wrong type in main function: found `" +
2771                                   ty_to_str(tcx, main_t) + "`");
2772         }
2773       }
2774       _ {
2775         let span = ast_map::node_span(tcx.items.get(main_id));
2776         tcx.sess.span_bug(span,
2777                           "main has a non-function type: found `" +
2778                               ty_to_str(tcx, main_t) + "`");
2779       }
2780     }
2781 }
2782
2783 fn check_for_main_fn(tcx: ty::ctxt, crate: @ast::crate) {
2784     if !tcx.sess.building_library {
2785         alt tcx.sess.main_fn {
2786           some(id) { check_main_fn_ty(tcx, id); }
2787           none { tcx.sess.span_err(crate.span, "main function not found"); }
2788         }
2789     }
2790 }
2791
2792 mod dict {
2793     fn has_iface_bounds(tps: [ty::param_bounds]) -> bool {
2794         vec::any(tps, {|bs|
2795             vec::any(*bs, {|b|
2796                 alt b { ty::bound_iface(_) { true } _ { false } }
2797             })
2798         })
2799     }
2800
2801     fn lookup_dicts(fcx: @fn_ctxt, isc: resolve::iscopes, sp: span,
2802                     bounds: @[ty::param_bounds], tys: [ty::t])
2803         -> dict_res {
2804         let tcx = fcx.ccx.tcx, result = [], i = 0u;
2805         for ty in tys {
2806             for bound in *bounds[i] {
2807                 alt bound {
2808                   ty::bound_iface(i_ty) {
2809                     let i_ty = ty::substitute_type_params(tcx, tys, i_ty);
2810                     result += [lookup_dict(fcx, isc, sp, ty, i_ty)];
2811                   }
2812                   _ {}
2813                 }
2814             }
2815             i += 1u;
2816         }
2817         @result
2818     }
2819
2820     fn lookup_dict(fcx: @fn_ctxt, isc: resolve::iscopes, sp: span,
2821                    ty: ty::t, iface_ty: ty::t) -> dict_origin {
2822         let tcx = fcx.ccx.tcx;
2823         let (iface_id, iface_tps) = alt ty::struct(tcx, iface_ty) {
2824             ty::ty_iface(did, tps) { (did, tps) }
2825         };
2826         let ty = fixup_ty(fcx, sp, ty);
2827         alt ty::struct(tcx, ty) {
2828           ty::ty_param(n, did) {
2829             let n_bound = 0u;
2830             for bound in *tcx.ty_param_bounds.get(did.node) {
2831                 alt bound {
2832                   ty::bound_iface(ity) {
2833                     alt ty::struct(tcx, ity) {
2834                       ty::ty_iface(idid, _) {
2835                         if iface_id == idid { ret dict_param(n, n_bound); }
2836                       }
2837                     }
2838                     n_bound += 1u;
2839                   }
2840                   _ {}
2841                 }
2842             }
2843           }
2844           ty::ty_iface(did, _) {
2845             ret dict_iface(did);
2846           }
2847           _ {
2848             let found = none;
2849             std::list::iter(isc) {|impls|
2850                 if option::is_some(found) { ret; }
2851                 for im in *impls {
2852                     let match = alt ty::impl_iface(tcx, im.did) {
2853                       some(ity) {
2854                         alt ty::struct(tcx, ity) {
2855                           ty::ty_iface(id, _) { id == iface_id }
2856                         }
2857                       }
2858                       _ { false }
2859                     };
2860                     if match {
2861                         let {n_tps, ty: self_ty} = impl_self_ty(tcx, im.did);
2862                         let {vars, ty: self_ty} = if n_tps > 0u {
2863                             bind_params(fcx, self_ty, n_tps)
2864                         } else { {vars: [], ty: self_ty} };
2865                         let im_bs = ty::lookup_item_type(tcx, im.did).bounds;
2866                         alt unify::unify(fcx, ty, self_ty) {
2867                           ures_ok(_) {
2868                             if option::is_some(found) {
2869                                 tcx.sess.span_err(
2870                                     sp, "multiple applicable implementations \
2871                                          in scope");
2872                             } else {
2873                                 connect_iface_tps(fcx, sp, vars, iface_tps,
2874                                                   im.did);
2875                                 let params = vec::map(vars, {|t|
2876                                     fixup_ty(fcx, sp, t)});
2877                                 let subres = lookup_dicts(fcx, isc, sp, im_bs,
2878                                                           params);
2879                                 found = some(dict_static(im.did, params,
2880                                                          subres));
2881                             }
2882                           }
2883                           _ {}
2884                         }
2885                     }
2886                 }
2887             }
2888             alt found {
2889               some(rslt) { ret rslt; }
2890               _ {}
2891             }
2892           }
2893         }
2894
2895         tcx.sess.span_fatal(
2896             sp, "failed to find an implementation of interface " +
2897             ty_to_str(tcx, iface_ty) + " for " +
2898             ty_to_str(tcx, ty));
2899     }
2900
2901     fn fixup_ty(fcx: @fn_ctxt, sp: span, ty: ty::t) -> ty::t {
2902         let tcx = fcx.ccx.tcx;
2903         alt ty::unify::fixup_vars(tcx, some(sp), fcx.var_bindings, ty) {
2904           fix_ok(new_type) { new_type }
2905           fix_err(vid) {
2906             tcx.sess.span_fatal(sp, "could not determine a type for a \
2907                                      bounded type parameter");
2908           }
2909         }
2910     }
2911
2912     fn connect_iface_tps(fcx: @fn_ctxt, sp: span, impl_tys: [ty::t],
2913                          iface_tys: [ty::t], impl_did: ast::def_id) {
2914         let tcx = fcx.ccx.tcx;
2915         let ity = option::get(ty::impl_iface(tcx, impl_did));
2916         let iface_ty = ty::substitute_type_params(tcx, impl_tys, ity);
2917         alt ty::struct(tcx, iface_ty) {
2918           ty::ty_iface(_, tps) {
2919             vec::iter2(tps, iface_tys,
2920                        {|a, b| demand::simple(fcx, sp, a, b);});
2921           }
2922         }
2923     }
2924
2925     fn resolve_expr(ex: @ast::expr, &&fcx: @fn_ctxt, v: visit::vt<@fn_ctxt>) {
2926         let cx = fcx.ccx;
2927         alt ex.node {
2928           ast::expr_path(_) {
2929             let substs = ty::node_id_to_ty_param_substs_opt_and_ty(
2930                 cx.tcx, ex.id);
2931             alt substs.substs {
2932               some(ts) {
2933                 let did = ast_util::def_id_of_def(cx.tcx.def_map.get(ex.id));
2934                 let item_ty = ty::lookup_item_type(cx.tcx, did);
2935                 if has_iface_bounds(*item_ty.bounds) {
2936                     let impls = cx.impl_map.get(ex.id);
2937                     cx.dict_map.insert(ex.id, lookup_dicts(
2938                         fcx, impls, ex.span, item_ty.bounds, ts));
2939                 }
2940               }
2941               _ {}
2942             }
2943           }
2944           // Must resolve bounds on methods with bounded params
2945           ast::expr_field(_, _, _) | ast::expr_binary(_, _, _) |
2946           ast::expr_unary(_, _) | ast::expr_assign_op(_, _, _) |
2947           ast::expr_index(_, _) {
2948             alt cx.method_map.find(ex.id) {
2949               some(method_static(did)) {
2950                 let bounds = ty::lookup_item_type(cx.tcx, did).bounds;
2951                 if has_iface_bounds(*bounds) {
2952                     let callee_id = alt ex.node {
2953                       ast::expr_field(_, _, _) { ex.id }
2954                       _ { ast_util::op_expr_callee_id(ex) }
2955                     };
2956                     let ts = ty::node_id_to_type_params(cx.tcx, callee_id);
2957                     let iscs = cx.impl_map.get(ex.id);
2958                     cx.dict_map.insert(callee_id, lookup_dicts(
2959                         fcx, iscs, ex.span, bounds, ts));
2960                 }
2961               }
2962               _ {}
2963             }
2964           }
2965           ast::expr_cast(src, _) {
2966             // Ifaces that refer to a self type can not be cast to -- callers
2967             // wouldn't know what self refers to.
2968             fn type_refers_to_self(tcx: ty::ctxt, t: ty::t, s_param: uint)
2969                 -> bool {
2970                 let found = false;
2971                 if ty::type_contains_params(tcx, t) {
2972                     ty::walk_ty(tcx, t) {|t|
2973                         alt ty::struct(tcx, t) {
2974                           ty::ty_param(n, _) if n == s_param { found = true; }
2975                           _ {}
2976                         }
2977                     }
2978                 }
2979                 found
2980             }
2981             fn method_refers_to_self(tcx: ty::ctxt, m: ty::method,
2982                                      s_param: uint) -> bool {
2983                 vec::any(m.fty.inputs, {|in|
2984                     type_refers_to_self(tcx, in.ty, s_param)
2985                 }) || type_refers_to_self(tcx, m.fty.output, s_param)
2986             }
2987             let target_ty = expr_ty(cx.tcx, ex);
2988             alt ty::struct(cx.tcx, target_ty) {
2989               ty::ty_iface(id, tps) {
2990                 for m in *ty::iface_methods(cx.tcx, id) {
2991                     if method_refers_to_self(cx.tcx, m, vec::len(tps)) {
2992                         cx.tcx.sess.span_err(
2993                             ex.span, "can not cast to an iface type that \
2994                                       refers to `self` " + m.ident);
2995                         break;
2996                     }
2997                 }
2998                 let impls = cx.impl_map.get(ex.id);
2999                 let dict = lookup_dict(fcx, impls, ex.span,
3000                                        expr_ty(cx.tcx, src), target_ty);
3001                 cx.dict_map.insert(ex.id, @[dict]);
3002               }
3003               _ {}
3004             }
3005           }
3006           ast::expr_fn(p, _, _, _) if ast::is_blockish(p) {}
3007           ast::expr_fn(_, _, _, _) { ret; }
3008           _ {}
3009         }
3010         visit::visit_expr(ex, fcx, v);
3011     }
3012
3013     // Detect points where an interface-bounded type parameter is
3014     // instantiated, resolve the impls for the parameters.
3015     fn resolve_in_block(fcx: @fn_ctxt, bl: ast::blk) {
3016         visit::visit_block(bl, fcx, visit::mk_vt(@{
3017             visit_expr: resolve_expr,
3018             visit_item: fn@(_i: @ast::item, &&_e: @fn_ctxt,
3019                             _v: visit::vt<@fn_ctxt>) {}
3020             with *visit::default_visitor()
3021         }));
3022     }
3023 }
3024
3025 fn check_crate(tcx: ty::ctxt, impl_map: resolve::impl_map,
3026                crate: @ast::crate) -> (method_map, dict_map) {
3027     collect::collect_item_types(tcx, crate);
3028
3029     let ccx = @{mutable self_infos: [],
3030                 impl_map: impl_map,
3031                 method_map: std::map::new_int_hash(),
3032                 dict_map: std::map::new_int_hash(),
3033                 tcx: tcx};
3034     let visit = visit::mk_simple_visitor(@{
3035         visit_item: bind check_item(ccx, _)
3036         with *visit::default_simple_visitor()
3037     });
3038     visit::visit_crate(*crate, (), visit);
3039     check_for_main_fn(tcx, crate);
3040     tcx.sess.abort_if_errors();
3041     (ccx.method_map, ccx.dict_map)
3042 }
3043 //
3044 // Local Variables:
3045 // mode: rust
3046 // fill-column: 78;
3047 // indent-tabs-mode: nil
3048 // c-basic-offset: 4
3049 // buffer-file-coding-system: utf-8-unix
3050 // End:
3051 //