src/librustc/middle/typeck/check/mod.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 /*
  12
  13 # check.rs
  14
  15 Within the check phase of type check, we check each item one at a time
  16 (bodies of function expressions are checked as part of the containing
  17 function).  Inference is used to supply types wherever they are
  18 unknown.
  19
  20 By far the most complex case is checking the body of a function. This
  21 can be broken down into several distinct phases:
  22
  23 - gather: creates type variables to represent the type of each local
  24   variable and pattern binding.
  25
  26 - main: the main pass does the lion's share of the work: it
  27   determines the types of all expressions, resolves
  28   methods, checks for most invalid conditions, and so forth.  In
  29   some cases, where a type is unknown, it may create a type or region
  30   variable and use that as the type of an expression.
  31
  32   In the process of checking, various constraints will be placed on
  33   these type variables through the subtyping relationships requested
  34   through the `demand` module.  The `typeck::infer` module is in charge
  35   of resolving those constraints.
  36
  37 - regionck: after main is complete, the regionck pass goes over all
  38   types looking for regions and making sure that they did not escape
  39   into places they are not in scope.  This may also influence the
  40   final assignments of the various region variables if there is some
  41   flexibility.
  42
  43 - vtable: find and records the impls to use for each trait bound that
  44   appears on a type parameter.
  45
  46 - writeback: writes the final types within a function body, replacing
  47   type variables with their final inferred types.  These final types
  48   are written into the `tcx.node_types` table, which should *never* contain
  49   any reference to a type variable.
  50
  51 ## Intermediate types
  52
  53 While type checking a function, the intermediate types for the
  54 expressions, blocks, and so forth contained within the function are
  55 stored in `fcx.node_types` and `fcx.node_type_substs`.  These types
  56 may contain unresolved type variables.  After type checking is
  57 complete, the functions in the writeback module are used to take the
  58 types from this table, resolve them, and then write them into their
  59 permanent home in the type context `ccx.tcx`.
  60
  61 This means that during inferencing you should use `fcx.write_ty()`
  62 and `fcx.expr_ty()` / `fcx.node_ty()` to write/obtain the types of
  63 nodes within the function.
  64
  65 The types of top-level items, which never contain unbound type
  66 variables, are stored directly into the `tcx` tables.
  67
  68 n.b.: A type variable is not the same thing as a type parameter.  A
  69 type variable is rather an "instance" of a type parameter: that is,
  70 given a generic function `fn foo<T>(t: T)`: while checking the
  71 function `foo`, the type `ty_param(0)` refers to the type `T`, which
  72 is treated in abstract.  When `foo()` is called, however, `T` will be
  73 substituted for a fresh type variable `N`.  This variable will
  74 eventually be resolved to some concrete type (which might itself be
  75 type parameter).
  76
  77 */
  78
  79 use core::prelude::*;
  80
  81 use middle::const_eval;
  82 use middle::pat_util::pat_id_map;
  83 use middle::pat_util;
  84 use middle::ty::{TyVid, Vid, FnSig, VariantInfo_, field};
  85 use middle::ty::{ty_param_bounds_and_ty, ty_param_substs_and_ty};
  86 use middle::ty::{re_bound, br_cap_avoid, substs, arg, param_ty};
  87 use middle::ty;
  88 use middle::typeck::astconv::{AstConv, ast_path_to_ty};
  89 use middle::typeck::astconv::{ast_region_to_region, ast_ty_to_ty};
  90 use middle::typeck::astconv;
  91 use middle::typeck::check::_match::pat_ctxt;
  92 use middle::typeck::check::method::{CheckTraitsAndInherentMethods};
  93 use middle::typeck::check::method::{CheckTraitsOnly, TransformTypeNormally};
  94 use middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig;
  95 use middle::typeck::check::vtable::{LocationInfo, VtableContext};
  96 use middle::typeck::CrateCtxt;
  97 use middle::typeck::infer::{resolve_type, force_tvar, mk_eqty};
  98 use middle::typeck::infer;
  99 use middle::typeck::rscope::{binding_rscope, bound_self_region};
 100 use middle::typeck::rscope::{RegionError};
 101 use middle::typeck::rscope::{in_binding_rscope, region_scope, type_rscope};
 102 use middle::typeck::rscope;
 103 use middle::typeck::{isr_alist, lookup_def_ccx, method_map_entry};
 104 use middle::typeck::{method_origin, method_self, method_trait, no_params};
 105 use middle::typeck::{require_same_types};
 106 use util::common::{block_query, indenter, loop_query};
 107 use util::ppaux::{bound_region_to_str, expr_repr, pat_repr};
 108 use util::ppaux;
 109
 110 use core::either;
 111 use core::option;
 112 use core::ptr;
 113 use core::result::{Result, Ok, Err};
 114 use core::result;
 115 use core::str;
 116 use core::vec;
 117 use std::list::Nil;
 118 use std::oldmap::HashMap;
 119 use std::oldmap;
 120 use syntax::ast::{provided, required, ty_i};
 121 use syntax::ast;
 122 use syntax::ast_map;
 123 use syntax::ast_util::{Private, Public, is_local, local_def};
 124 use syntax::ast_util;
 125 use syntax::codemap::{span, spanned, respan};
 126 use syntax::codemap;
 127 use syntax::parse::token::special_idents;
 128 use syntax::print::pprust;
 129 use syntax::visit;
 130 use syntax::opt_vec::OptVec;
 131 use syntax;
 132
 133 pub mod _match;
 134 pub mod vtable;
 135 pub mod writeback;
 136 pub mod regionmanip;
 137 pub mod regionck;
 138 pub mod demand;
 139 pub mod method;
 140
 141 pub struct SelfInfo {
 142     self_ty: ty::t,
 143     self_id: ast::node_id,
 144     def_id: ast::def_id,
 145     explicit_self: ast::self_ty
 146 }
 147
 148 /// Fields that are part of a `FnCtxt` which are inherited by
 149 /// closures defined within the function.  For example:
 150 ///
 151 ///     fn foo() {
 152 ///         do bar() { ... }
 153 ///     }
 154 ///
 155 /// Here, the function `foo()` and the closure passed to
 156 /// `bar()` will each have their own `FnCtxt`, but they will
 157 /// share the inherited fields.
 158 pub struct inherited {
 159     infcx: @mut infer::InferCtxt,
 160     locals: HashMap<ast::node_id, ty::t>,
 161     node_types: HashMap<ast::node_id, ty::t>,
 162     node_type_substs: HashMap<ast::node_id, ty::substs>,
 163     adjustments: HashMap<ast::node_id, @ty::AutoAdjustment>
 164 }
 165
 166 pub enum FnKind {
 167     // This is a for-closure.  The ty::t is the return type of the
 168     // enclosing function.
 169     ForLoop(ty::t),
 170
 171     // A do-closure.
 172     DoBlock,
 173
 174     // A normal closure or fn item.
 175     Vanilla
 176 }
 177
 178 pub struct FnCtxt {
 179     // var_bindings, locals and next_var_id are shared
 180     // with any nested functions that capture the environment
 181     // (and with any functions whose environment is being captured).
 182
 183     // Refers to whichever `self` is in scope, even this FnCtxt is
 184     // for a nested closure that captures `self`
 185     self_info: Option<SelfInfo>,
 186     ret_ty: ty::t,
 187     // Used by loop bodies that return from the outer function
 188     indirect_ret_ty: Option<ty::t>,
 189     purity: ast::purity,
 190
 191     // Sometimes we generate region pointers where the precise region
 192     // to use is not known. For example, an expression like `&x.f`
 193     // where `x` is of type `@T`: in this case, we will be rooting
 194     // `x` onto the stack frame, and we could choose to root it until
 195     // the end of (almost) any enclosing block or expression.  We
 196     // want to pick the narrowest block that encompasses all uses.
 197     //
 198     // What we do in such cases is to generate a region variable with
 199     // `region_lb` as a lower bound.  The regionck pass then adds
 200     // other constriants based on how the variable is used and region
 201     // inference selects the ultimate value.  Finally, borrowck is
 202     // charged with guaranteeing that the value whose address was taken
 203     // can actually be made to live as long as it needs to live.
 204     region_lb: ast::node_id,
 205
 206     // Says whether we're inside a for loop, in a do block
 207     // or neither. Helps with error messages involving the
 208     // function return type.
 209     fn_kind: FnKind,
 210
 211     in_scope_regions: isr_alist,
 212
 213     inh: @inherited,
 214
 215     ccx: @mut CrateCtxt,
 216 }
 217
 218 pub fn blank_inherited(ccx: @mut CrateCtxt) -> @inherited {
 219     @inherited {
 220         infcx: infer::new_infer_ctxt(ccx.tcx),
 221         locals: HashMap(),
 222         node_types: oldmap::HashMap(),
 223         node_type_substs: oldmap::HashMap(),
 224         adjustments: oldmap::HashMap()
 225     }
 226 }
 227
 228 // Used by check_const and check_enum_variants
 229 pub fn blank_fn_ctxt(ccx: @mut CrateCtxt,
 230                      rty: ty::t,
 231                      region_bnd: ast::node_id)
 232                   -> @mut FnCtxt {
 233 // It's kind of a kludge to manufacture a fake function context
 234 // and statement context, but we might as well do write the code only once
 235     @mut FnCtxt {
 236         self_info: None,
 237         ret_ty: rty,
 238         indirect_ret_ty: None,
 239         purity: ast::pure_fn,
 240         region_lb: region_bnd,
 241         in_scope_regions: @Nil,
 242         fn_kind: Vanilla,
 243         inh: blank_inherited(ccx),
 244         ccx: ccx
 245     }
 246 }
 247
 248 pub fn check_item_types(ccx: @mut CrateCtxt, crate: @ast::crate) {
 249     let visit = visit::mk_simple_visitor(@visit::SimpleVisitor {
 250         visit_item: |a| check_item(ccx, a),
 251         .. *visit::default_simple_visitor()
 252     });
 253     visit::visit_crate(*crate, (), visit);
 254 }
 255
 256 pub fn check_bare_fn(ccx: @mut CrateCtxt,
 257                      decl: &ast::fn_decl,
 258                      body: &ast::blk,
 259                      id: ast::node_id,
 260                      self_info: Option<SelfInfo>) {
 261     let fty = ty::node_id_to_type(ccx.tcx, id);
 262     match ty::get(fty).sty {
 263         ty::ty_bare_fn(ref fn_ty) => {
 264             let fcx =
 265                 check_fn(ccx, self_info, fn_ty.purity,
 266                          &fn_ty.sig, decl, body, Vanilla,
 267                          @Nil, blank_inherited(ccx));;
 268
 269             vtable::resolve_in_block(fcx, body);
 270             regionck::regionck_fn(fcx, body);
 271             writeback::resolve_type_vars_in_fn(fcx, decl, body, self_info);
 272         }
 273         _ => ccx.tcx.sess.impossible_case(body.span,
 274                                  "check_bare_fn: function type expected")
 275     }
 276 }
 277
 278 pub fn check_fn(ccx: @mut CrateCtxt,
 279                 +self_info: Option<SelfInfo>,
 280                 purity: ast::purity,
 281                 fn_sig: &ty::FnSig,
 282                 decl: &ast::fn_decl,
 283                 body: &ast::blk,
 284                 fn_kind: FnKind,
 285                 inherited_isr: isr_alist,
 286                 inherited: @inherited) -> @mut FnCtxt
 287 {
 288     /*!
 289      *
 290      * Helper used by check_bare_fn and check_expr_fn.  Does the
 291      * grungy work of checking a function body and returns the
 292      * function context used for that purpose, since in the case of a
 293      * fn item there is still a bit more to do.
 294      *
 295      * - ...
 296      * - inherited_isr: regions in scope from the enclosing fn (if any)
 297      * - inherited: other fields inherited from the enclosing fn (if any)
 298      */
 299
 300     let tcx = ccx.tcx;
 301
 302     // ______________________________________________________________________
 303     // First, we have to replace any bound regions in the fn and self
 304     // types with free ones.  The free region references will be bound
 305     // the node_id of the body block.
 306
 307     let (isr, self_info, fn_sig) = {
 308         replace_bound_regions_in_fn_sig(tcx, inherited_isr, self_info, fn_sig,
 309                                         |br| ty::re_free(body.node.id, br))
 310     };
 311
 312     let arg_tys = fn_sig.inputs.map(|a| a.ty);
 313     let ret_ty = fn_sig.output;
 314
 315     debug!("check_fn(arg_tys=%?, ret_ty=%?, self_info.self_ty=%?)",
 316            arg_tys.map(|a| ppaux::ty_to_str(tcx, *a)),
 317            ppaux::ty_to_str(tcx, ret_ty),
 318            option::map(&self_info, |s| ppaux::ty_to_str(tcx, s.self_ty)));
 319
 320     // ______________________________________________________________________
 321     // Create the function context.  This is either derived from scratch or,
 322     // in the case of function expressions, based on the outer context.
 323     let fcx: @mut FnCtxt = {
 324         // In a for-loop, you have an 'indirect return' because return
 325         // does not return out of the directly enclosing fn
 326         let indirect_ret_ty = match fn_kind {
 327             ForLoop(t) => Some(t),
 328             DoBlock | Vanilla => None
 329         };
 330
 331         @mut FnCtxt {
 332             self_info: self_info,
 333             ret_ty: ret_ty,
 334             indirect_ret_ty: indirect_ret_ty,
 335             purity: purity,
 336             region_lb: body.node.id,
 337             in_scope_regions: isr,
 338             fn_kind: fn_kind,
 339             inh: inherited,
 340             ccx: ccx
 341         }
 342     };
 343
 344     // Update the SelfInfo to contain an accurate self type (taking
 345     // into account explicit self).
 346     let self_info = do self_info.chain_ref |self_info| {
 347         // If the self type is sty_static, we don't have a self ty.
 348         if self_info.explicit_self.node == ast::sty_static {
 349             None
 350         } else  {
 351             let in_scope_regions = fcx.in_scope_regions;
 352             let self_region = in_scope_regions.find(ty::br_self);
 353             let ty = method::transform_self_type_for_method(
 354                 fcx.tcx(),
 355                 self_region,
 356                 self_info.self_ty,
 357                 self_info.explicit_self.node,
 358                 TransformTypeNormally);
 359             Some(SelfInfo { self_ty: ty,.. *self_info })
 360         }
 361     };
 362
 363     gather_locals(fcx, decl, body, arg_tys, self_info);
 364     check_block(fcx, body);
 365
 366     // We unify the tail expr's type with the
 367     // function result type, if there is a tail expr.
 368     match body.node.expr {
 369       Some(tail_expr) => {
 370         let tail_expr_ty = fcx.expr_ty(tail_expr);
 371         // Special case: we print a special error if there appears
 372         // to be do-block/for-loop confusion
 373         demand::suptype_with_fn(fcx, tail_expr.span, false,
 374             fcx.ret_ty, tail_expr_ty,
 375             |sp, e, a, s| {
 376                 fcx.report_mismatched_return_types(sp, e, a, s) });
 377       }
 378       None => ()
 379     }
 380
 381     for self_info.each |self_info| {
 382         fcx.write_ty(self_info.self_id, self_info.self_ty);
 383     }
 384     for vec::each2(decl.inputs, arg_tys) |input, arg| {
 385         fcx.write_ty(input.id, *arg);
 386     }
 387
 388     return fcx;
 389
 390     fn gather_locals(fcx: @mut FnCtxt,
 391                      decl: &ast::fn_decl,
 392                      body: &ast::blk,
 393                      arg_tys: &[ty::t],
 394                      self_info: Option<SelfInfo>) {
 395         let tcx = fcx.ccx.tcx;
 396
 397         let assign: @fn(ast::node_id, Option<ty::t>) = |nid, ty_opt| {
 398             match ty_opt {
 399                 None => {
 400                     // infer the variable's type
 401                     let var_id = fcx.infcx().next_ty_var_id();
 402                     let var_ty = ty::mk_var(fcx.tcx(), var_id);
 403                     fcx.inh.locals.insert(nid, var_ty);
 404                 }
 405                 Some(typ) => {
 406                     // take type that the user specified
 407                     fcx.inh.locals.insert(nid, typ);
 408                 }
 409             }
 410         };
 411
 412         // Add the self parameter
 413         for self_info.each |self_info| {
 414             assign(self_info.self_id, Some(self_info.self_ty));
 415             debug!("self is assigned to %s",
 416                    fcx.infcx().ty_to_str(
 417                        fcx.inh.locals.get(&self_info.self_id)));
 418         }
 419
 420         // Add formal parameters.
 421         for vec::each2(arg_tys, decl.inputs) |arg_ty, input| {
 422             // Create type variables for each argument.
 423             do pat_util::pat_bindings(tcx.def_map, input.pat)
 424                     |_bm, pat_id, _sp, _path| {
 425                 assign(pat_id, None);
 426             }
 427
 428             // Check the pattern.
 429             let region = fcx.block_region();
 430             let pcx = pat_ctxt {
 431                 fcx: fcx,
 432                 map: pat_id_map(tcx.def_map, input.pat),
 433                 match_region: region,
 434                 block_region: region,
 435             };
 436             _match::check_pat(pcx, input.pat, *arg_ty);
 437         }
 438
 439         // Add explicitly-declared locals.
 440         let visit_local: @fn(@ast::local, &&e: (), visit::vt<()>) =
 441                 |local, e, v| {
 442             let o_ty = match local.node.ty.node {
 443               ast::ty_infer => None,
 444               _ => Some(fcx.to_ty(local.node.ty))
 445             };
 446             assign(local.node.id, o_ty);
 447             debug!("Local variable %s is assigned type %s",
 448                    fcx.pat_to_str(local.node.pat),
 449                    fcx.infcx().ty_to_str(
 450                        fcx.inh.locals.get(&local.node.id)));
 451             visit::visit_local(local, e, v);
 452         };
 453
 454         // Add pattern bindings.
 455         let visit_pat: @fn(@ast::pat, &&e: (), visit::vt<()>) = |p, e, v| {
 456             match p.node {
 457               ast::pat_ident(_, path, _)
 458                   if pat_util::pat_is_binding(fcx.ccx.tcx.def_map, p) => {
 459                 assign(p.id, None);
 460                 debug!("Pattern binding %s is assigned to %s",
 461                        *tcx.sess.str_of(path.idents[0]),
 462                        fcx.infcx().ty_to_str(
 463                            fcx.inh.locals.get(&p.id)));
 464               }
 465               _ => {}
 466             }
 467             visit::visit_pat(p, e, v);
 468         };
 469
 470         let visit_block: @fn(&ast::blk, &&e: (), visit::vt<()>) = |b, e, v| {
 471             // non-obvious: the `blk` variable maps to region lb, so
 472             // we have to keep this up-to-date.  This
 473             // is... unfortunate.  It'd be nice to not need this.
 474             do fcx.with_region_lb(b.node.id) {
 475                 visit::visit_block(b, e, v);
 476             }
 477         };
 478
 479         // Don't descend into fns and items
 480         fn visit_fn(_fk: &visit::fn_kind, _decl: &ast::fn_decl,
 481                     _body: &ast::blk, _sp: span,
 482                     _id: ast::node_id, &&_t: (), _v: visit::vt<()>) {
 483         }
 484         fn visit_item(_i: @ast::item, &&_e: (), _v: visit::vt<()>) { }
 485
 486         let visit = visit::mk_vt(
 487             @visit::Visitor {visit_local: visit_local,
 488                              visit_pat: visit_pat,
 489                              visit_fn: visit_fn,
 490                              visit_item: visit_item,
 491                              visit_block: visit_block,
 492                              ..*visit::default_visitor()});
 493
 494         (visit.visit_block)(body, (), visit);
 495     }
 496 }
 497
 498 pub fn check_method(ccx: @mut CrateCtxt,
 499                     method: @ast::method,
 500                     self_ty: ty::t,
 501                     self_impl_def_id: ast::def_id) {
 502     let self_info = SelfInfo {
 503         self_ty: self_ty,
 504         self_id: method.self_id,
 505         def_id: self_impl_def_id,
 506         explicit_self: method.self_ty
 507     };
 508     check_bare_fn(
 509         ccx,
 510         &method.decl,
 511         &method.body,
 512         method.id,
 513         Some(self_info)
 514     );
 515 }
 516
 517 pub fn check_no_duplicate_fields(tcx: ty::ctxt,
 518                                  fields: ~[(ast::ident, span)]) {
 519     let field_names = HashMap();
 520
 521     for fields.each |p| {
 522         let (id, sp) = *p;
 523         match field_names.find(&id) {
 524           Some(orig_sp) => {
 525             tcx.sess.span_err(sp, fmt!("Duplicate field \
 526                                    name %s in record type declaration",
 527                                         *tcx.sess.str_of(id)));
 528             tcx.sess.span_note(orig_sp, ~"First declaration of \
 529                                           this field occurred here");
 530             break;
 531           }
 532           None => {
 533             field_names.insert(id, sp);
 534           }
 535         }
 536     }
 537 }
 538
 539 pub fn check_struct(ccx: @mut CrateCtxt,
 540                     struct_def: @ast::struct_def,
 541                     id: ast::node_id,
 542                     span: span) {
 543     let tcx = ccx.tcx;
 544     let self_ty = ty::node_id_to_type(tcx, id);
 545
 546     for struct_def.dtor.each |dtor| {
 547         let class_t = SelfInfo {
 548             self_ty: self_ty,
 549             self_id: dtor.node.self_id,
 550             def_id: local_def(id),
 551             explicit_self: spanned {
 552                 node: ast::sty_by_ref,
 553                 span: codemap::dummy_sp()
 554             }
 555         };
 556         // typecheck the dtor
 557         let dtor_dec = ast_util::dtor_dec();
 558         check_bare_fn(
 559             ccx,
 560             &dtor_dec,
 561             &dtor.node.body,
 562             dtor.node.id,
 563             Some(class_t)
 564         );
 565     };
 566
 567     // Check that the class is instantiable
 568     check_instantiable(ccx.tcx, span, id);
 569 }
 570
 571 pub fn check_item(ccx: @mut CrateCtxt, it: @ast::item) {
 572     debug!("check_item(it.id=%d, it.ident=%s)",
 573            it.id,
 574            ty::item_path_str(ccx.tcx, local_def(it.id)));
 575     let _indenter = indenter();
 576
 577     match /*bad*/copy it.node {
 578       ast::item_const(_, e) => check_const(ccx, it.span, e, it.id),
 579       ast::item_enum(ref enum_definition, _) => {
 580         check_enum_variants(ccx,
 581                             it.span,
 582                             /*bad*/copy (*enum_definition).variants,
 583                             it.id);
 584       }
 585       ast::item_fn(ref decl, _, _, ref body) => {
 586         check_bare_fn(ccx, decl, body, it.id, None);
 587       }
 588       ast::item_impl(_, _, ty, ms) => {
 589         let rp = ccx.tcx.region_paramd_items.find(&it.id);
 590         debug!("item_impl %s with id %d rp %?",
 591                *ccx.tcx.sess.str_of(it.ident), it.id, rp);
 592         let self_ty = ccx.to_ty(&rscope::type_rscope(rp), ty);
 593         for ms.each |m| {
 594             check_method(ccx, *m, self_ty, local_def(it.id));
 595         }
 596       }
 597       ast::item_trait(_, _, ref trait_methods) => {
 598         for (*trait_methods).each |trait_method| {
 599             match *trait_method {
 600               required(*) => {
 601                 // Nothing to do, since required methods don't have
 602                 // bodies to check.
 603               }
 604               provided(m) => {
 605                 check_method(ccx, m, ty::mk_self(ccx.tcx), local_def(it.id));
 606               }
 607             }
 608         }
 609       }
 610       ast::item_struct(struct_def, _) => {
 611         check_struct(ccx, struct_def, it.id, it.span);
 612       }
 613       ast::item_ty(t, ref generics) => {
 614         let tpt_ty = ty::node_id_to_type(ccx.tcx, it.id);
 615         check_bounds_are_used(ccx, t.span, &generics.ty_params, tpt_ty);
 616       }
 617       ast::item_foreign_mod(m) => {
 618         if syntax::attr::foreign_abi(it.attrs) ==
 619             either::Right(ast::foreign_abi_rust_intrinsic) {
 620             for m.items.each |item| {
 621                 check_intrinsic_type(ccx, *item);
 622             }
 623         } else {
 624             for m.items.each |item| {
 625                 let tpt = ty::lookup_item_type(ccx.tcx, local_def(item.id));
 626                 if !tpt.bounds.is_empty() {
 627                     ccx.tcx.sess.span_err(
 628                         item.span,
 629                         fmt!("foreign items may not have type parameters"));
 630                 }
 631             }
 632         }
 633       }
 634       _ => {/* nothing to do */ }
 635     }
 636 }
 637
 638 impl AstConv for FnCtxt {
 639     fn tcx(&self) -> ty::ctxt { self.ccx.tcx }
 640
 641     fn get_item_ty(&self, id: ast::def_id) -> ty::ty_param_bounds_and_ty {
 642         ty::lookup_item_type(self.tcx(), id)
 643     }
 644
 645     fn ty_infer(&self, _span: span) -> ty::t {
 646         self.infcx().next_ty_var()
 647     }
 648 }
 649
 650 pub impl FnCtxt {
 651     fn infcx(&self) -> @mut infer::InferCtxt { self.inh.infcx }
 652     fn search_in_scope_regions(
 653         &self,
 654         span: span,
 655         br: ty::bound_region) -> Result<ty::Region, RegionError>
 656     {
 657         let in_scope_regions = self.in_scope_regions;
 658         match in_scope_regions.find(br) {
 659             Some(r) => result::Ok(r),
 660             None => {
 661                 let blk_br = ty::br_named(special_idents::blk);
 662                 if br == blk_br {
 663                     result::Ok(self.block_region())
 664                 } else {
 665                     result::Err(RegionError {
 666                         msg: fmt!("named region `%s` not in scope here",
 667                                   bound_region_to_str(self.tcx(), br)),
 668                         replacement: self.infcx().next_region_var_nb(span)
 669                     })
 670                 }
 671             }
 672         }
 673     }
 674 }
 675
 676 impl region_scope for FnCtxt {
 677     fn anon_region(&self, span: span) -> Result<ty::Region, RegionError> {
 678         result::Ok(self.infcx().next_region_var_nb(span))
 679     }
 680     fn self_region(&self, span: span) -> Result<ty::Region, RegionError> {
 681         self.search_in_scope_regions(span, ty::br_self)
 682     }
 683     fn named_region(&self,
 684                     span: span,
 685                     id: ast::ident) -> Result<ty::Region, RegionError> {
 686         self.search_in_scope_regions(span, ty::br_named(id))
 687     }
 688 }
 689
 690 pub impl FnCtxt {
 691     fn tag(&self) -> ~str { fmt!("%x", ptr::addr_of(&(*self)) as uint) }
 692
 693     fn local_ty(&self, span: span, nid: ast::node_id) -> ty::t {
 694         match self.inh.locals.find(&nid) {
 695             Some(t) => t,
 696             None => {
 697                 self.tcx().sess.span_bug(
 698                     span,
 699                     fmt!("No type for local variable %?", nid));
 700             }
 701         }
 702     }
 703
 704     fn expr_to_str(&self, expr: @ast::expr) -> ~str {
 705         fmt!("expr(%?:%s)", expr.id,
 706              pprust::expr_to_str(expr, self.tcx().sess.intr()))
 707     }
 708
 709     fn block_region(&self) -> ty::Region {
 710         ty::re_scope(self.region_lb)
 711     }
 712
 713     #[inline(always)]
 714     fn write_ty(&self, node_id: ast::node_id, ty: ty::t) {
 715         debug!("write_ty(%d, %s) in fcx %s",
 716                node_id, ppaux::ty_to_str(self.tcx(), ty), self.tag());
 717         self.inh.node_types.insert(node_id, ty);
 718     }
 719
 720     fn write_substs(&self, node_id: ast::node_id, +substs: ty::substs) {
 721         if !ty::substs_is_noop(&substs) {
 722             debug!("write_substs(%d, %s) in fcx %s",
 723                    node_id,
 724                    ty::substs_to_str(self.tcx(), &substs),
 725                    self.tag());
 726             self.inh.node_type_substs.insert(node_id, substs);
 727         }
 728     }
 729
 730     fn write_ty_substs(&self,
 731                        node_id: ast::node_id,
 732                        ty: ty::t,
 733                        +substs: ty::substs) {
 734         let ty = ty::subst(self.tcx(), &substs, ty);
 735         self.write_ty(node_id, ty);
 736         self.write_substs(node_id, substs);
 737     }
 738
 739     fn write_autoderef_adjustment(&self,
 740                                   node_id: ast::node_id,
 741                                   derefs: uint) {
 742         if derefs == 0 { return; }
 743         self.write_adjustment(
 744             node_id,
 745             @ty::AutoDerefRef(ty::AutoDerefRef {
 746                 autoderefs: derefs,
 747                 autoref: None })
 748         );
 749     }
 750
 751     fn write_adjustment(&self,
 752                         node_id: ast::node_id,
 753                         adj: @ty::AutoAdjustment) {
 754         debug!("write_adjustment(node_id=%?, adj=%?)", node_id, adj);
 755         self.inh.adjustments.insert(node_id, adj);
 756     }
 757
 758     fn write_nil(&self, node_id: ast::node_id) {
 759         self.write_ty(node_id, ty::mk_nil(self.tcx()));
 760     }
 761     fn write_bot(&self, node_id: ast::node_id) {
 762         self.write_ty(node_id, ty::mk_bot(self.tcx()));
 763     }
 764
 765     fn to_ty(&self, ast_t: @ast::Ty) -> ty::t {
 766         ast_ty_to_ty(self, self, ast_t)
 767     }
 768
 769     fn expr_to_str(&self, expr: @ast::expr) -> ~str {
 770         expr_repr(self.tcx(), expr)
 771     }
 772
 773     fn pat_to_str(&self, pat: @ast::pat) -> ~str {
 774         pat_repr(self.tcx(), pat)
 775     }
 776
 777     fn expr_ty(&self, ex: @ast::expr) -> ty::t {
 778         match self.inh.node_types.find(&ex.id) {
 779             Some(t) => t,
 780             None => {
 781                 self.tcx().sess.bug(
 782                     fmt!("no type for %s in fcx %s",
 783                          self.expr_to_str(ex), self.tag()));
 784             }
 785         }
 786     }
 787     fn node_ty(&self, id: ast::node_id) -> ty::t {
 788         match self.inh.node_types.find(&id) {
 789             Some(t) => t,
 790             None => {
 791                 self.tcx().sess.bug(
 792                     fmt!("no type for node %d: %s in fcx %s",
 793                          id, ast_map::node_id_to_str(
 794                              self.tcx().items, id,
 795                              self.tcx().sess.parse_sess.interner),
 796                          self.tag()));
 797             }
 798         }
 799     }
 800     fn node_ty_substs(&self, id: ast::node_id) -> ty::substs {
 801         match self.inh.node_type_substs.find(&id) {
 802             Some(ref ts) => (/*bad*/copy *ts),
 803             None => {
 804                 self.tcx().sess.bug(
 805                     fmt!("no type substs for node %d: %s in fcx %s",
 806                          id, ast_map::node_id_to_str(
 807                              self.tcx().items, id,
 808                              self.tcx().sess.parse_sess.interner),
 809                          self.tag()));
 810             }
 811         }
 812     }
 813     fn opt_node_ty_substs(&self, id: ast::node_id) -> Option<ty::substs> {
 814         self.inh.node_type_substs.find(&id)
 815     }
 816
 817
 818     fn mk_subty(&self,
 819                 a_is_expected: bool,
 820                 span: span,
 821                 sub: ty::t,
 822                 sup: ty::t)
 823              -> Result<(), ty::type_err> {
 824         infer::mk_subty(self.infcx(), a_is_expected, span, sub, sup)
 825     }
 826
 827     fn can_mk_subty(&self,
 828                     sub: ty::t,
 829                     sup: ty::t)
 830                  -> Result<(), ty::type_err> {
 831         infer::can_mk_subty(self.infcx(), sub, sup)
 832     }
 833
 834     fn mk_assignty(&self, expr: @ast::expr, sub: ty::t, sup: ty::t)
 835                 -> Result<(), ty::type_err> {
 836         match infer::mk_coercety(self.infcx(), false, expr.span, sub, sup) {
 837             Ok(None) => result::Ok(()),
 838             Err(ref e) => result::Err((*e)),
 839             Ok(Some(adjustment)) => {
 840                 self.write_adjustment(expr.id, adjustment);
 841                 Ok(())
 842             }
 843         }
 844     }
 845
 846     fn can_mk_assignty(&self,
 847                        sub: ty::t,
 848                        sup: ty::t)
 849                     -> Result<(), ty::type_err> {
 850         infer::can_mk_coercety(self.infcx(), sub, sup)
 851     }
 852
 853     fn mk_eqty(&self,
 854                a_is_expected: bool,
 855                span: span,
 856                sub: ty::t,
 857                sup: ty::t)
 858             -> Result<(), ty::type_err> {
 859         infer::mk_eqty(self.infcx(), a_is_expected, span, sub, sup)
 860     }
 861
 862     fn mk_subr(&self,
 863                a_is_expected: bool,
 864                span: span,
 865                sub: ty::Region,
 866                sup: ty::Region)
 867             -> Result<(), ty::type_err> {
 868         infer::mk_subr(self.infcx(), a_is_expected, span, sub, sup)
 869     }
 870
 871     fn require_unsafe(&self, sp: span, op: ~str) {
 872         match self.purity {
 873           ast::unsafe_fn => {/*ok*/}
 874           _ => {
 875             self.ccx.tcx.sess.span_err(
 876                 sp,
 877                 fmt!("%s requires unsafe function or block", op));
 878           }
 879         }
 880     }
 881
 882     fn with_region_lb<R>(@mut self, lb: ast::node_id, f: &fn() -> R) -> R {
 883         let old_region_lb = self.region_lb;
 884         self.region_lb = lb;
 885         let v = f();
 886         self.region_lb = old_region_lb;
 887         v
 888     }
 889
 890     fn region_var_if_parameterized(&self,
 891                                    rp: Option<ty::region_variance>,
 892                                    span: span,
 893                                    lower_bound: ty::Region)
 894                                 -> Option<ty::Region> {
 895         rp.map(
 896             |_rp| self.infcx().next_region_var_with_lb(span, lower_bound))
 897     }
 898
 899     fn type_error_message(&self,
 900                           sp: span,
 901                           mk_msg: &fn(~str) -> ~str,
 902                           actual_ty: ty::t,
 903                           err: Option<&ty::type_err>) {
 904         self.infcx().type_error_message(sp, mk_msg, actual_ty, err);
 905     }
 906
 907     fn report_mismatched_return_types(&self,
 908                                       sp: span,
 909                                       e: ty::t,
 910                                       a: ty::t,
 911                                       err: &ty::type_err) {
 912         match self.fn_kind {
 913             ForLoop(_) if !ty::type_is_bool(e) && !ty::type_is_nil(a) =>
 914                     self.tcx().sess.span_err(sp, fmt!("A for-loop body must \
 915                         return (), but it returns %s here. \
 916                         Perhaps you meant to write a `do`-block?",
 917                                             ppaux::ty_to_str(self.tcx(), a))),
 918             DoBlock if ty::type_is_bool(e) && ty::type_is_nil(a) =>
 919                 // If we expected bool and got ()...
 920                     self.tcx().sess.span_err(sp, fmt!("Do-block body must \
 921                         return %s, but returns () here. Perhaps you meant \
 922                         to write a `for`-loop?",
 923                         ppaux::ty_to_str(self.tcx(), e))),
 924             _ => self.infcx().report_mismatched_types(sp, e, a, err)
 925         }
 926     }
 927
 928     fn report_mismatched_types(&self,
 929                                sp: span,
 930                                e: ty::t,
 931                                a: ty::t,
 932                                err: &ty::type_err) {
 933         self.infcx().report_mismatched_types(sp, e, a, err)
 934     }
 935 }
 936
 937 pub fn do_autoderef(fcx: @mut FnCtxt, sp: span, t: ty::t) -> (ty::t, uint) {
 938     /*!
 939      *
 940      * Autoderefs the type `t` as many times as possible, returning
 941      * a new type and a counter for how many times the type was
 942      * deref'd.  If the counter is non-zero, the receiver is responsible
 943      * for inserting an AutoAdjustment record into `tcx.adjustments`
 944      * so that trans/borrowck/etc know about this autoderef. */
 945
 946     let mut t1 = t;
 947     let mut enum_dids = ~[];
 948     let mut autoderefs = 0;
 949     loop {
 950         let sty = structure_of(fcx, sp, t1);
 951
 952         // Some extra checks to detect weird cycles and so forth:
 953         match sty {
 954             ty::ty_box(inner) | ty::ty_uniq(inner) |
 955             ty::ty_rptr(_, inner) => {
 956                 match ty::get(t1).sty {
 957                     ty::ty_infer(ty::TyVar(v1)) => {
 958                         ty::occurs_check(fcx.ccx.tcx, sp, v1,
 959                                          ty::mk_box(fcx.ccx.tcx, inner));
 960                     }
 961                     _ => ()
 962                 }
 963             }
 964             ty::ty_enum(ref did, _) => {
 965                 // Watch out for a type like `enum t = @t`.  Such a
 966                 // type would otherwise infinitely auto-deref.  Only
 967                 // autoderef loops during typeck (basically, this one
 968                 // and the loops in typeck::check::method) need to be
 969                 // concerned with this, as an error will be reported
 970                 // on the enum definition as well because the enum is
 971                 // not instantiable.
 972                 if vec::contains(enum_dids, did) {
 973                     return (t1, autoderefs);
 974                 }
 975                 enum_dids.push(*did);
 976             }
 977             _ => { /*ok*/ }
 978         }
 979
 980         // Otherwise, deref if type is derefable:
 981         match ty::deref_sty(fcx.ccx.tcx, &sty, false) {
 982             None => {
 983                 return (t1, autoderefs);
 984             }
 985             Some(mt) => {
 986                 autoderefs += 1;
 987                 t1 = mt.ty
 988             }
 989         }
 990     };
 991 }
 992
 993 // AST fragment checking
 994 pub fn check_lit(fcx: @mut FnCtxt, lit: @ast::lit) -> ty::t {
 995     let tcx = fcx.ccx.tcx;
 996
 997     match lit.node {
 998       ast::lit_str(*) => ty::mk_estr(tcx, ty::vstore_slice(ty::re_static)),
 999       ast::lit_int(_, t) => ty::mk_mach_int(tcx, t),
1000       ast::lit_uint(_, t) => ty::mk_mach_uint(tcx, t),
1001       ast::lit_int_unsuffixed(_) => {
1002         // An unsuffixed integer literal could have any integral type,
1003         // so we create an integral type variable for it.
1004         ty::mk_int_var(tcx, fcx.infcx().next_int_var_id())
1005       }
1006       ast::lit_float(_, t) => ty::mk_mach_float(tcx, t),
1007       ast::lit_float_unsuffixed(_) => {
1008         // An unsuffixed floating point literal could have any floating point
1009         // type, so we create a floating point type variable for it.
1010         ty::mk_float_var(tcx, fcx.infcx().next_float_var_id())
1011       }
1012       ast::lit_nil => ty::mk_nil(tcx),
1013       ast::lit_bool(_) => ty::mk_bool(tcx)
1014     }
1015 }
1016
1017 pub fn valid_range_bounds(ccx: @mut CrateCtxt,
1018                           from: @ast::expr,
1019                           to: @ast::expr)
1020                        -> bool {
1021     const_eval::compare_lit_exprs(ccx.tcx, from, to) <= 0
1022 }
1023
1024 pub fn check_expr_has_type(
1025     fcx: @mut FnCtxt, expr: @ast::expr,
1026     expected: ty::t) -> bool {
1027     do check_expr_with_unifier(fcx, expr, Some(expected)) {
1028         demand::suptype(fcx, expr.span, expected, fcx.expr_ty(expr));
1029     }
1030 }
1031
1032 pub fn check_expr_coercable_to_type(
1033     fcx: @mut FnCtxt, expr: @ast::expr,
1034     expected: ty::t) -> bool {
1035     do check_expr_with_unifier(fcx, expr, Some(expected)) {
1036         demand::coerce(fcx, expr.span, expected, expr)
1037     }
1038 }
1039
1040 pub fn check_expr_with_hint(
1041     fcx: @mut FnCtxt, expr: @ast::expr,
1042     expected: ty::t) -> bool {
1043     check_expr_with_unifier(fcx, expr, Some(expected), || ())
1044 }
1045
1046 pub fn check_expr_with_opt_hint(
1047     fcx: @mut FnCtxt, expr: @ast::expr,
1048     expected: Option<ty::t>) -> bool {
1049     check_expr_with_unifier(fcx, expr, expected, || ())
1050 }
1051
1052 pub fn check_expr(fcx: @mut FnCtxt, expr: @ast::expr) -> bool {
1053     check_expr_with_unifier(fcx, expr, None, || ())
1054 }
1055
1056 // determine the `self` type, using fresh variables for all variables
1057 // declared on the impl declaration e.g., `impl<A,B> for ~[(A,B)]`
1058 // would return ($0, $1) where $0 and $1 are freshly instantiated type
1059 // variables.
1060 pub fn impl_self_ty(vcx: &VtableContext,
1061                     location_info: &LocationInfo, // (potential) receiver for
1062                                                   // this impl
1063                     did: ast::def_id)
1064                  -> ty_param_substs_and_ty {
1065     let tcx = vcx.tcx();
1066
1067     let (n_tps, region_param, raw_ty) = if did.crate == ast::local_crate {
1068         let region_param = tcx.region_paramd_items.find(&did.node);
1069         match tcx.items.find(&did.node) {
1070           Some(ast_map::node_item(@ast::item {
1071                   node: ast::item_impl(ref ts, _, st, _),
1072                   _
1073               }, _)) => {
1074             (ts.ty_params.len(),
1075              region_param,
1076              vcx.ccx.to_ty(&rscope::type_rscope(region_param), st))
1077           }
1078           Some(ast_map::node_item(@ast::item {
1079                   node: ast::item_struct(_, ref ts),
1080                   id: class_id,
1081                   _
1082               },_)) => {
1083               /* If the impl is a class, the self ty is just the class ty
1084                  (doing a no-op subst for the ty params; in the next step,
1085                  we substitute in fresh vars for them)
1086                */
1087               (ts.ty_params.len(),
1088                region_param,
1089                ty::mk_struct(tcx, local_def(class_id),
1090                       substs {
1091                         self_r: rscope::bound_self_region(region_param),
1092                         self_ty: None,
1093                         tps: ty::ty_params_to_tys(tcx, ts)
1094                       }))
1095           }
1096           _ => { tcx.sess.bug(~"impl_self_ty: unbound item or item that \
1097                doesn't have a self_ty"); }
1098         }
1099     } else {
1100         let ity = ty::lookup_item_type(tcx, did);
1101         (vec::len(*ity.bounds), ity.region_param, ity.ty)
1102     };
1103
1104     let self_r = if region_param.is_some() {
1105         Some(vcx.infcx.next_region_var(location_info.span,
1106                                          location_info.id))
1107     } else {
1108         None
1109     };
1110     let tps = vcx.infcx.next_ty_vars(n_tps);
1111
1112     let substs = substs { self_r: self_r, self_ty: None, tps: tps };
1113     let substd_ty = ty::subst(tcx, &substs, raw_ty);
1114
1115     ty_param_substs_and_ty { substs: substs, ty: substd_ty }
1116 }
1117
1118 // Only for fields! Returns <none> for methods>
1119 // Indifferent to privacy flags
1120 pub fn lookup_field_ty(tcx: ty::ctxt,
1121                        class_id: ast::def_id,
1122                        items: &[ty::field_ty],
1123                        fieldname: ast::ident,
1124                        substs: &ty::substs) -> Option<ty::t> {
1125
1126     let o_field = vec::find(items, |f| f.ident == fieldname);
1127     do o_field.map() |f| {
1128         ty::lookup_field_type(tcx, class_id, f.id, substs)
1129     }
1130 }
1131
1132 // Controls whether the arguments are automatically referenced. This is useful
1133 // for overloaded binary and unary operators.
1134 pub enum DerefArgs {
1135     DontDerefArgs,
1136     DoDerefArgs
1137 }
1138
1139 pub fn break_here() {
1140     debug!("break here!");
1141 }
1142
1143 pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
1144                                expr: @ast::expr,
1145                                expected: Option<ty::t>,
1146                                unifier: &fn()) -> bool {
1147     debug!(">> typechecking %s", fcx.expr_to_str(expr));
1148
1149     // A generic function to factor out common logic from call and
1150     // overloaded operations
1151     fn check_call_inner(
1152         fcx: @mut FnCtxt,
1153         sp: span,
1154         call_expr_id: ast::node_id,
1155         in_fty: ty::t,
1156         callee_expr: @ast::expr,
1157         args: ~[@ast::expr],
1158         sugar: ast::CallSugar,
1159         deref_args: DerefArgs) -> (ty::t, bool)
1160     {
1161         let tcx = fcx.ccx.tcx;
1162         let mut bot = false;
1163
1164         // Replace all region parameters in the arguments and return
1165         // type with fresh region variables.
1166
1167         debug!("check_call_inner: before universal quant., in_fty=%s",
1168                fcx.infcx().ty_to_str(in_fty));
1169
1170         let formal_tys;
1171
1172         // This is subtle: we expect `fty` to be a function type, which
1173         // normally introduce a level of binding.  In this case, we want to
1174         // process the types bound by the function but not by any nested
1175         // functions.  Therefore, we match one level of structure.
1176         let ret_ty = match structure_of(fcx, sp, in_fty) {
1177             ty::ty_bare_fn(ty::BareFnTy {sig: ref sig, _}) |
1178             ty::ty_closure(ty::ClosureTy {sig: ref sig, _}) => {
1179                 let (_, _, sig) =
1180                     replace_bound_regions_in_fn_sig(
1181                         tcx, @Nil, None, sig,
1182                         |_br| fcx.infcx().next_region_var(
1183                             sp, call_expr_id));
1184
1185                 let supplied_arg_count = args.len();
1186
1187                 bot |= ty::type_is_bot(sig.output);
1188
1189                 // Grab the argument types, supplying fresh type variables
1190                 // if the wrong number of arguments were supplied
1191                 let expected_arg_count = sig.inputs.len();
1192                 formal_tys = if expected_arg_count == supplied_arg_count {
1193                     sig.inputs.map(|a| a.ty)
1194                 } else {
1195                     let suffix = match sugar {
1196                         ast::NoSugar => "",
1197                         ast::DoSugar => " (including the closure passed by \
1198                                          the `do` keyword)",
1199                         ast::ForSugar => " (including the closure passed by \
1200                                           the `for` keyword)"
1201                     };
1202                     let msg = fmt!("this function takes %u parameter%s but \
1203                                     %u parameter%s supplied%s",
1204                                    expected_arg_count,
1205                                    if expected_arg_count == 1 {""}
1206                                    else {"s"},
1207                                    supplied_arg_count,
1208                                    if supplied_arg_count == 1 {" was"}
1209                                    else {"s were"},
1210                                    suffix);
1211
1212                     tcx.sess.span_err(sp, msg);
1213
1214                     vec::from_fn(supplied_arg_count, |_| ty::mk_err(tcx))
1215                 };
1216
1217                 sig.output
1218             }
1219
1220             _ => {
1221                 fcx.type_error_message(sp, |actual| {
1222                     fmt!("expected function or foreign function but \
1223                           found `%s`", actual) }, in_fty, None);
1224
1225                 // check each arg against "error", in order to set up
1226                 // all the node type bindings
1227                 formal_tys = args.map(|_x| ty::mk_err(tcx));
1228                 ty::mk_err(tcx)
1229             }
1230         };
1231
1232         debug!("check_call_inner: after universal quant., \
1233                 formal_tys=%? ret_ty=%s",
1234                formal_tys.map(|t| fcx.infcx().ty_to_str(*t)),
1235                fcx.infcx().ty_to_str(ret_ty));
1236
1237         // Check the arguments.
1238         // We do this in a pretty awful way: first we typecheck any arguments
1239         // that are not anonymous functions, then we typecheck the anonymous
1240         // functions. This is so that we have more information about the types
1241         // of arguments when we typecheck the functions. This isn't really the
1242         // right way to do this.
1243         for [false, true].each |check_blocks| {
1244             let check_blocks = *check_blocks;
1245             debug!("check_blocks=%b", check_blocks);
1246
1247             // More awful hacks: before we check the blocks, try to do
1248             // an "opportunistic" vtable resolution of any trait
1249             // bounds on the call.
1250             if check_blocks {
1251                 vtable::early_resolve_expr(callee_expr, fcx, true);
1252             }
1253
1254             for args.eachi |i, arg| {
1255                 let is_block = match arg.node {
1256                     ast::expr_fn_block(*) | ast::expr_loop_body(*) |
1257                     ast::expr_do_body(*) => true,
1258                     _ => false
1259                 };
1260
1261                 if is_block == check_blocks {
1262                     debug!("checking the argument");
1263                     let mut formal_ty = formal_tys[i];
1264
1265                     match deref_args {
1266                         DoDerefArgs => {
1267                             match ty::get(formal_ty).sty {
1268                                 ty::ty_rptr(_, mt) => formal_ty = mt.ty,
1269                                 _ => {
1270                                     fcx.ccx.tcx.sess.span_bug(arg.span,
1271                                                               ~"no ref");
1272                                 }
1273                             }
1274                         }
1275                         DontDerefArgs => {}
1276                     }
1277
1278                     // mismatch error happens in here
1279                     bot |= check_expr_coercable_to_type(
1280                         fcx, *arg, formal_ty);
1281
1282                 }
1283             }
1284         }
1285
1286         (ret_ty, bot)
1287     }
1288
1289     // A generic function for checking assignment expressions
1290     fn check_assignment(fcx: @mut FnCtxt,
1291                         lhs: @ast::expr,
1292                         rhs: @ast::expr,
1293                         id: ast::node_id)
1294                      -> bool {
1295         let mut bot = check_expr(fcx, lhs);
1296         let lhs_type = fcx.expr_ty(lhs);
1297         bot |= check_expr_has_type(fcx, rhs, lhs_type);
1298         fcx.write_ty(id, ty::mk_nil(fcx.ccx.tcx));
1299         return bot;
1300     }
1301
1302     // A generic function for doing all of the checking for call or
1303     // method expressions
1304     fn check_call_or_method(fcx: @mut FnCtxt,
1305                             sp: span,
1306                             call_expr_id: ast::node_id,
1307                             fn_ty: ty::t,
1308                             expr: @ast::expr,
1309                             +args: ~[@ast::expr],
1310                             bot: bool,
1311                             sugar: ast::CallSugar) -> bool
1312     {
1313         let mut bot = bot;
1314
1315         // Call the generic checker.
1316         let (ret_ty, b) = check_call_inner(fcx, sp, call_expr_id,
1317                                            fn_ty, expr, args, sugar,
1318                                            DontDerefArgs);
1319         bot |= b;
1320
1321         // Pull the return type out of the type of the function.
1322         fcx.write_ty(call_expr_id, ret_ty);
1323         return bot;
1324     }
1325
1326     // A generic function for doing all of the checking for call expressions
1327     fn check_call(fcx: @mut FnCtxt,
1328                   sp: span,
1329                   call_expr_id: ast::node_id,
1330                   f: @ast::expr,
1331                   +args: ~[@ast::expr],
1332                   sugar: ast::CallSugar)
1333                -> bool {
1334         // Index expressions need to be handled separately, to inform them
1335         // that they appear in call position.
1336         let mut bot = match /*bad*/copy f.node {
1337             ast::expr_field(base, field, tys) => {
1338                 check_field(fcx, f, true, base, field, tys)
1339             }
1340             _ => check_expr(fcx, f)
1341         };
1342
1343         check_call_or_method(fcx,
1344                              sp,
1345                              call_expr_id,
1346                              fcx.expr_ty(f),
1347                              f,
1348                              args,
1349                              bot,
1350                              sugar)
1351     }
1352
1353     // Checks a method call.
1354     fn check_method_call(fcx: @mut FnCtxt,
1355                          expr: @ast::expr,
1356                          rcvr: @ast::expr,
1357                          method_name: ast::ident,
1358                          +args: ~[@ast::expr],
1359                          tps: ~[@ast::Ty],
1360                          sugar: ast::CallSugar)
1361                       -> bool {
1362         let bot = check_expr(fcx, rcvr);
1363         let expr_t = structurally_resolved_type(fcx,
1364                                                 expr.span,
1365                                                 fcx.expr_ty(rcvr));
1366
1367         let tps = tps.map(|ast_ty| fcx.to_ty(*ast_ty));
1368         match method::lookup(fcx,
1369                              expr,
1370                              rcvr,
1371                              expr.callee_id,
1372                              method_name,
1373                              expr_t,
1374                              tps,
1375                              DontDerefArgs,
1376                              CheckTraitsAndInherentMethods) {
1377             Some(ref entry) => {
1378                 let method_map = fcx.ccx.method_map;
1379                 method_map.insert(expr.id, (*entry));
1380             }
1381             None => {
1382                 fcx.type_error_message(expr.span,
1383                   |actual| {
1384                       fmt!("type `%s` does not implement any method in scope \
1385                             named `%s`",
1386                            actual,
1387                            *fcx.ccx.tcx.sess.str_of(method_name))
1388                   },
1389                   expr_t,
1390                   None);
1391
1392                 // Add error type for the result
1393                 fcx.write_ty(expr.id, ty::mk_err(fcx.ccx.tcx));
1394                 fcx.write_ty(expr.callee_id, ty::mk_err(fcx.ccx.tcx));
1395             }
1396         }
1397
1398         check_call_or_method(fcx,
1399                              expr.span,
1400                              expr.id,
1401                              fcx.node_ty(expr.callee_id),
1402                              expr,
1403                              args,
1404                              bot,
1405                              sugar)
1406     }
1407
1408     // A generic function for checking for or for-each loops
1409     fn check_for(fcx: @mut FnCtxt,
1410                  local: @ast::local,
1411                  element_ty: ty::t,
1412                  body: &ast::blk,
1413                  node_id: ast::node_id)
1414               -> bool {
1415         let local_ty = fcx.local_ty(local.span, local.node.id);
1416         demand::suptype(fcx, local.span, local_ty, element_ty);
1417         let bot = check_decl_local(fcx, local);
1418         check_block_no_value(fcx, body);
1419         fcx.write_nil(node_id);
1420         return bot;
1421     }
1422
1423     // A generic function for checking the then and else in an if
1424     // or if-check
1425     fn check_then_else(fcx: @mut FnCtxt,
1426                        thn: &ast::blk,
1427                        elsopt: Option<@ast::expr>,
1428                        id: ast::node_id,
1429                        _sp: span)
1430                     -> bool {
1431         let (if_t, if_bot) =
1432             match elsopt {
1433                 Some(els) => {
1434                     let if_t = fcx.infcx().next_ty_var();
1435                     let thn_bot = check_block(fcx, thn);
1436                     let thn_t = fcx.node_ty(thn.node.id);
1437                     demand::suptype(fcx, thn.span, if_t, thn_t);
1438                     let els_bot = check_expr_has_type(fcx, els, if_t);
1439                     (if_t, thn_bot & els_bot)
1440                 }
1441                 None => {
1442                     check_block_no_value(fcx, thn);
1443                     (ty::mk_nil(fcx.ccx.tcx), false)
1444                 }
1445             };
1446         fcx.write_ty(id, if_t);
1447         return if_bot;
1448     }
1449
1450     fn lookup_op_method(fcx: @mut FnCtxt,
1451                         op_ex: @ast::expr,
1452                         self_ex: @ast::expr,
1453                         self_t: ty::t,
1454                         opname: ast::ident,
1455                         +args: ~[@ast::expr],
1456                         +deref_args: DerefArgs)
1457                      -> Option<(ty::t, bool)> {
1458         match method::lookup(fcx,
1459                              op_ex,
1460                              self_ex,
1461                              op_ex.callee_id,
1462                              opname,
1463                              self_t,
1464                              ~[],
1465                              deref_args,
1466                              CheckTraitsOnly) {
1467           Some(ref origin) => {
1468               let method_ty = fcx.node_ty(op_ex.callee_id);
1469               let method_map = fcx.ccx.method_map;
1470               method_map.insert(op_ex.id, *origin);
1471               Some(check_call_inner(fcx,
1472                                     op_ex.span,
1473                                     op_ex.id,
1474                                     method_ty,
1475                                     op_ex,
1476                                     args,
1477                                     ast::NoSugar,
1478                                     deref_args))
1479           }
1480           _ => None
1481         }
1482     }
1483
1484     // could be either a expr_binop or an expr_assign_binop
1485     fn check_binop(fcx: @mut FnCtxt,
1486                    expr: @ast::expr,
1487                    op: ast::binop,
1488                    lhs: @ast::expr,
1489                    rhs: @ast::expr)
1490                 -> bool {
1491         let tcx = fcx.ccx.tcx;
1492
1493         let lhs_bot = check_expr(fcx, lhs);
1494         let lhs_t = fcx.expr_ty(lhs);
1495         let lhs_t = structurally_resolved_type(fcx, lhs.span, lhs_t);
1496
1497         if ty::type_is_integral(lhs_t) && ast_util::is_shift_binop(op) {
1498             // Shift is a special case: rhs can be any integral type
1499             let rhs_bot = check_expr(fcx, rhs);
1500             let rhs_t = fcx.expr_ty(rhs);
1501             require_integral(fcx, rhs.span, rhs_t);
1502             fcx.write_ty(expr.id, lhs_t);
1503             return lhs_bot | rhs_bot;
1504         }
1505
1506         if ty::is_binopable(tcx, lhs_t, op) {
1507             let tvar = fcx.infcx().next_ty_var();
1508             demand::suptype(fcx, expr.span, tvar, lhs_t);
1509             let rhs_bot = check_expr_has_type(fcx, rhs, tvar);
1510
1511             let result_t = match op {
1512                 ast::eq | ast::ne | ast::lt | ast::le | ast::ge |
1513                 ast::gt => {
1514                     ty::mk_bool(tcx)
1515                 }
1516                 _ => {
1517                     lhs_t
1518                 }
1519             };
1520
1521             fcx.write_ty(expr.id, result_t);
1522             return {
1523                 if !ast_util::lazy_binop(op) { lhs_bot | rhs_bot }
1524                 else { lhs_bot }
1525             };
1526         }
1527
1528         // A hack, but this prevents multiple errors for the same code
1529         // (since check_user_binop calls structurally_resolve_type)
1530         let (result, rhs_bot) =
1531            match ty::deref(fcx.tcx(), lhs_t, false).map(
1532                       |tt| structurally_resolved_type(fcx,
1533                                                       expr.span, tt.ty)) {
1534                 Some(t) if ty::get(t).sty == ty::ty_err => (t, false),
1535                 _ => check_user_binop(fcx, expr, lhs, lhs_t, op, rhs)
1536            };
1537         fcx.write_ty(expr.id, result);
1538         return lhs_bot | rhs_bot;
1539     }
1540
1541     fn check_user_binop(fcx: @mut FnCtxt,
1542                         ex: @ast::expr,
1543                         lhs_expr: @ast::expr,
1544                         lhs_resolved_t: ty::t,
1545                         op: ast::binop,
1546                         rhs: @ast::expr)
1547                      -> (ty::t, bool) {
1548         let tcx = fcx.ccx.tcx;
1549         match ast_util::binop_to_method_name(op) {
1550           Some(ref name) => {
1551             match lookup_op_method(fcx, ex, lhs_expr, lhs_resolved_t,
1552                                    fcx.tcx().sess.ident_of(copy *name),
1553                                    ~[rhs], DoDerefArgs) {
1554               Some(pair) => return pair,
1555               _ => ()
1556             }
1557           }
1558           _ => ()
1559         }
1560         check_expr(fcx, rhs);
1561         fcx.type_error_message(ex.span,
1562            |actual| {
1563                fmt!("binary operation %s cannot be applied to type `%s`",
1564                     ast_util::binop_to_str(op), actual)
1565            },
1566            lhs_resolved_t, None);
1567
1568         // If the or operator is used it might be that the user forgot to
1569         // supply the do keyword.  Let's be more helpful in that situation.
1570         if op == ast::or {
1571             match ty::get(lhs_resolved_t).sty {
1572                 ty::ty_bare_fn(_) | ty::ty_closure(_) => {
1573                     tcx.sess.span_note(
1574                         ex.span, ~"did you forget the `do` keyword \
1575                                    for the call?");
1576                 }
1577                 _ => ()
1578             }
1579         }
1580
1581         (lhs_resolved_t, false)
1582     }
1583
1584     fn check_user_unop(fcx: @mut FnCtxt,
1585                        op_str: ~str,
1586                        mname: ~str,
1587                        ex: @ast::expr,
1588                        rhs_expr: @ast::expr,
1589                        rhs_t: ty::t)
1590                     -> ty::t {
1591         match lookup_op_method(
1592             fcx, ex, rhs_expr, rhs_t,
1593             fcx.tcx().sess.ident_of(/*bad*/ copy mname), ~[],
1594             DontDerefArgs)
1595         {
1596           Some((ret_ty, _)) => ret_ty,
1597           _ => {
1598               fcx.type_error_message(ex.span, |actual| {
1599                   fmt!("cannot apply unary operator `%s` to type `%s`",
1600                               op_str, actual)
1601               }, rhs_t, None);
1602               rhs_t
1603           }
1604         }
1605     }
1606
1607     // Resolves `expected` by a single level if it is a variable and passes it
1608     // through the `unpack` function.  It there is no expected type or
1609     // resolution is not possible (e.g., no constraints yet present), just
1610     // returns `none`.
1611     fn unpack_expected<O:Copy>(fcx: @mut FnCtxt,
1612                                 expected: Option<ty::t>,
1613                                 unpack: &fn(&ty::sty) -> Option<O>)
1614                              -> Option<O> {
1615         match expected {
1616             Some(t) => {
1617                 match resolve_type(fcx.infcx(), t, force_tvar) {
1618                     Ok(t) => unpack(&ty::get(t).sty),
1619                     _ => None
1620                 }
1621             }
1622             _ => None
1623         }
1624     }
1625
1626     fn check_expr_fn(fcx: @mut FnCtxt,
1627                      expr: @ast::expr,
1628                      ast_sigil_opt: Option<ast::Sigil>,
1629                      decl: &ast::fn_decl,
1630                      body: &ast::blk,
1631                      fn_kind: FnKind,
1632                      expected: Option<ty::t>) {
1633         let tcx = fcx.ccx.tcx;
1634
1635         // Find the expected input/output types (if any).  Careful to
1636         // avoid capture of bound regions in the expected type.  See
1637         // def'n of br_cap_avoid() for a more lengthy explanation of
1638         // what's going on here.
1639         // Also try to pick up inferred purity and sigil, defaulting
1640         // to impure and block. Note that we only will use those for
1641         // block syntax lambdas; that is, lambdas without explicit
1642         // sigils.
1643         let expected_sty = unpack_expected(fcx, expected, |x| Some(copy *x));
1644         let (expected_tys,
1645              expected_purity,
1646              expected_sigil,
1647              expected_onceness) = {
1648             match expected_sty {
1649                 Some(ty::ty_closure(ref cenv)) => {
1650                     let id = expr.id;
1651                     let (_, _, sig) =
1652                         replace_bound_regions_in_fn_sig(
1653                             tcx, @Nil, None, &cenv.sig,
1654                             |br| ty::re_bound(ty::br_cap_avoid(id, @br)));
1655                     (Some(sig), cenv.purity, cenv.sigil, cenv.onceness)
1656                 }
1657                 _ => {
1658                     (None, ast::impure_fn, ast::BorrowedSigil, ast::Many)
1659                 }
1660             }
1661         };
1662
1663         // If the proto is specified, use that, otherwise select a
1664         // proto based on inference.
1665         let (sigil, purity) = match ast_sigil_opt {
1666             Some(p) => (p, ast::impure_fn),
1667             None => (expected_sigil, expected_purity)
1668         };
1669
1670         // construct the function type
1671         let mut fn_ty = astconv::ty_of_closure(
1672             fcx, fcx,
1673             sigil, purity, expected_onceness,
1674             None, decl, expected_tys, expr.span);
1675
1676         let fty = ty::mk_closure(tcx, copy fn_ty);
1677
1678         debug!("check_expr_fn_with_unifier %s fty=%s",
1679                fcx.expr_to_str(expr),
1680                fcx.infcx().ty_to_str(fty));
1681
1682         fcx.write_ty(expr.id, fty);
1683
1684         let inherited_purity =
1685             ty::determine_inherited_purity(fcx.purity, purity,
1686                                            fn_ty.sigil);
1687
1688         // We inherit the same self info as the enclosing scope,
1689         // since the function we're checking might capture `self`
1690         check_fn(fcx.ccx, fcx.self_info, inherited_purity,
1691                  &fn_ty.sig, decl, body, fn_kind,
1692                  fcx.in_scope_regions, fcx.inh);
1693     }
1694
1695
1696     // Check field access expressions
1697     fn check_field(fcx: @mut FnCtxt,
1698                    expr: @ast::expr,
1699                    is_callee: bool,
1700                    base: @ast::expr,
1701                    field: ast::ident,
1702                    tys: ~[@ast::Ty])
1703                 -> bool {
1704         let tcx = fcx.ccx.tcx;
1705         let bot = check_expr(fcx, base);
1706         let expr_t = structurally_resolved_type(fcx, expr.span,
1707                                                 fcx.expr_ty(base));
1708         let (base_t, derefs) = do_autoderef(fcx, expr.span, expr_t);
1709         let n_tys = tys.len();
1710
1711         match structure_of(fcx, expr.span, base_t) {
1712             ty::ty_struct(base_id, ref substs) => {
1713                 // This is just for fields -- the same code handles
1714                 // methods in both classes and traits
1715
1716                 // (1) verify that the class id actually has a field called
1717                 // field
1718                 debug!("class named %s", ppaux::ty_to_str(tcx, base_t));
1719                 let cls_items = ty::lookup_struct_fields(tcx, base_id);
1720                 match lookup_field_ty(tcx, base_id, cls_items,
1721                                       field, &(*substs)) {
1722                     Some(field_ty) => {
1723                         // (2) look up what field's type is, and return it
1724                         fcx.write_ty(expr.id, field_ty);
1725                         fcx.write_autoderef_adjustment(base.id, derefs);
1726                         return bot;
1727                     }
1728                     None => ()
1729                 }
1730             }
1731             _ => ()
1732         }
1733
1734         let tps = vec::map(tys, |ty| fcx.to_ty(*ty));
1735
1736         match method::lookup(fcx,
1737                              expr,
1738                              base,
1739                              expr.id,
1740                              field,
1741                              expr_t,
1742                              tps,
1743                              DontDerefArgs,
1744                              CheckTraitsAndInherentMethods) {
1745             Some(ref entry) => {
1746                 let method_map = fcx.ccx.method_map;
1747                 method_map.insert(expr.id, (*entry));
1748
1749                 // If we have resolved to a method but this is not in
1750                 // a callee position, error
1751                 if !is_callee {
1752                     tcx.sess.span_err(
1753                         expr.span,
1754                         ~"attempted to take value of method \
1755                           (try writing an anonymous function)");
1756                     // Add error type for the result
1757                     fcx.write_ty(expr.id, ty::mk_err(tcx));
1758                 }
1759             }
1760             None => {
1761                 fcx.type_error_message(expr.span,
1762                   |actual| {
1763                       fmt!("attempted access of field `%s` on type `%s`, but \
1764                             no field or method with that name was found",
1765                            *tcx.sess.str_of(field), actual)
1766                   },
1767                   expr_t, None);
1768                 // Add error type for the result
1769                 fcx.write_ty(expr.id, ty::mk_err(tcx));
1770             }
1771         }
1772
1773         return bot;
1774     }
1775
1776     fn check_struct_or_variant_fields(fcx: @mut FnCtxt,
1777                                       span: span,
1778                                       class_id: ast::def_id,
1779                                       substitutions: &ty::substs,
1780                                       field_types: ~[ty::field_ty],
1781                                       ast_fields: ~[ast::field],
1782                                       check_completeness: bool)
1783                                    -> bool {
1784         let tcx = fcx.ccx.tcx;
1785         let mut bot = false;
1786
1787         debug!("%? %?", ast_fields.len(), field_types.len());
1788
1789         let class_field_map = HashMap();
1790         let mut fields_found = 0;
1791         for field_types.each |field| {
1792             // XXX: Check visibility here.
1793             class_field_map.insert(field.ident, (field.id, false));
1794         }
1795
1796         // Typecheck each field.
1797         for ast_fields.each |field| {
1798             match class_field_map.find(&field.node.ident) {
1799                 None => {
1800                     tcx.sess.span_err(
1801                         field.span,
1802                         fmt!("structure has no field named `%s`",
1803                              *tcx.sess.str_of(field.node.ident)));
1804                 }
1805                 Some((_, true)) => {
1806                     tcx.sess.span_err(
1807                         field.span,
1808                         fmt!("field `%s` specified more than once",
1809                              *tcx.sess.str_of(field.node.ident)));
1810                 }
1811                 Some((field_id, false)) => {
1812                     let expected_field_type =
1813                         ty::lookup_field_type(
1814                             tcx, class_id, field_id, substitutions);
1815                     bot |=
1816                         check_expr_coercable_to_type(
1817                             fcx,
1818                             field.node.expr,
1819                             expected_field_type);
1820                     class_field_map.insert(
1821                         field.node.ident, (field_id, true));
1822                     fields_found += 1;
1823                 }
1824             }
1825         }
1826
1827         if check_completeness {
1828             // Make sure the programmer specified all the fields.
1829             fail_unless!(fields_found <= field_types.len());
1830             if fields_found < field_types.len() {
1831                 let mut missing_fields = ~[];
1832                 for field_types.each |class_field| {
1833                     let name = class_field.ident;
1834                     let (_, seen) = class_field_map.get(&name);
1835                     if !seen {
1836                         missing_fields.push(
1837                             ~"`" + *tcx.sess.str_of(name) + ~"`");
1838                     }
1839                 }
1840
1841                 tcx.sess.span_err(span,
1842                                   fmt!("missing field%s: %s",
1843                                        if missing_fields.len() == 1 {
1844                                            ~""
1845                                        } else {
1846                                            ~"s"
1847                                        },
1848                                        str::connect(missing_fields, ~", ")));
1849             }
1850         }
1851
1852         return bot;
1853     }
1854
1855     fn check_struct_constructor(fcx: @mut FnCtxt,
1856                                 id: ast::node_id,
1857                                 span: codemap::span,
1858                                 class_id: ast::def_id,
1859                                 fields: ~[ast::field],
1860                                 base_expr: Option<@ast::expr>)
1861                              -> bool {
1862         let mut bot = false;
1863         let tcx = fcx.ccx.tcx;
1864
1865         // Look up the number of type parameters and the raw type, and
1866         // determine whether the class is region-parameterized.
1867         let type_parameter_count, region_parameterized, raw_type;
1868         if class_id.crate == ast::local_crate {
1869             region_parameterized =
1870                 tcx.region_paramd_items.find(&class_id.node);
1871             match tcx.items.find(&class_id.node) {
1872                 Some(ast_map::node_item(@ast::item {
1873                         node: ast::item_struct(_, ref generics),
1874                         _
1875                     }, _)) => {
1876
1877                     type_parameter_count = generics.ty_params.len();
1878
1879                     let self_region =
1880                         bound_self_region(region_parameterized);
1881
1882                     raw_type = ty::mk_struct(tcx, class_id, substs {
1883                         self_r: self_region,
1884                         self_ty: None,
1885                         tps: ty::ty_params_to_tys(
1886                             tcx,
1887                             generics)
1888                     });
1889                 }
1890                 _ => {
1891                     tcx.sess.span_bug(span,
1892                                       ~"resolve didn't map this to a class");
1893                 }
1894             }
1895         } else {
1896             let item_type = ty::lookup_item_type(tcx, class_id);
1897             type_parameter_count = (*item_type.bounds).len();
1898             region_parameterized = item_type.region_param;
1899             raw_type = item_type.ty;
1900         }
1901
1902         // Generate the struct type.
1903         let self_region =
1904             fcx.region_var_if_parameterized(region_parameterized,
1905                                             span,
1906                                             ty::re_scope(id));
1907         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
1908         let substitutions = substs {
1909             self_r: self_region,
1910             self_ty: None,
1911             tps: type_parameters
1912         };
1913
1914         let struct_type = ty::subst(tcx, &substitutions, raw_type);
1915
1916         // Look up and check the fields.
1917         let class_fields = ty::lookup_struct_fields(tcx, class_id);
1918         bot = check_struct_or_variant_fields(fcx,
1919                                              span,
1920                                              class_id,
1921                                              &substitutions,
1922                                              class_fields,
1923                                              fields,
1924                                              base_expr.is_none()) || bot;
1925
1926         // Check the base expression if necessary.
1927         match base_expr {
1928             None => {}
1929             Some(base_expr) => {
1930                 bot = check_expr_has_type(fcx, base_expr, struct_type) || bot
1931             }
1932         }
1933
1934         // Write in the resulting type.
1935         fcx.write_ty(id, struct_type);
1936         return bot;
1937     }
1938
1939     fn check_struct_enum_variant(fcx: @mut FnCtxt,
1940                                  id: ast::node_id,
1941                                  span: codemap::span,
1942                                  enum_id: ast::def_id,
1943                                  variant_id: ast::def_id,
1944                                  fields: ~[ast::field])
1945                               -> bool {
1946         let mut bot = false;
1947         let tcx = fcx.ccx.tcx;
1948
1949         // Look up the number of type parameters and the raw type, and
1950         // determine whether the enum is region-parameterized.
1951         let type_parameter_count, region_parameterized, raw_type;
1952         if enum_id.crate == ast::local_crate {
1953             region_parameterized =
1954                 tcx.region_paramd_items.find(&enum_id.node);
1955             match tcx.items.find(&enum_id.node) {
1956                 Some(ast_map::node_item(@ast::item {
1957                         node: ast::item_enum(_, ref generics),
1958                         _
1959                     }, _)) => {
1960
1961                     type_parameter_count = generics.ty_params.len();
1962
1963                     let self_region =
1964                         bound_self_region(region_parameterized);
1965
1966                     raw_type = ty::mk_enum(tcx, enum_id, substs {
1967                         self_r: self_region,
1968                         self_ty: None,
1969                         tps: ty::ty_params_to_tys(
1970                             tcx,
1971                             generics)
1972                     });
1973                 }
1974                 _ => {
1975                     tcx.sess.span_bug(span,
1976                                       ~"resolve didn't map this to an enum");
1977                 }
1978             }
1979         } else {
1980             let item_type = ty::lookup_item_type(tcx, enum_id);
1981             type_parameter_count = (*item_type.bounds).len();
1982             region_parameterized = item_type.region_param;
1983             raw_type = item_type.ty;
1984         }
1985
1986         // Generate the enum type.
1987         let self_region =
1988             fcx.region_var_if_parameterized(region_parameterized,
1989                                             span,
1990                                             ty::re_scope(id));
1991         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
1992         let substitutions = substs {
1993             self_r: self_region,
1994             self_ty: None,
1995             tps: type_parameters
1996         };
1997
1998         let enum_type = ty::subst(tcx, &substitutions, raw_type);
1999
2000         // Look up and check the enum variant fields.
2001         let variant_fields = ty::lookup_struct_fields(tcx, variant_id);
2002         bot = check_struct_or_variant_fields(fcx,
2003                                              span,
2004                                              variant_id,
2005                                              &substitutions,
2006                                              variant_fields,
2007                                              fields,
2008                                              true) || bot;
2009
2010         // Write in the resulting type.
2011         fcx.write_ty(id, enum_type);
2012         return bot;
2013     }
2014
2015     fn check_loop_body(fcx: @mut FnCtxt,
2016                        expr: @ast::expr,
2017                        expected: Option<ty::t>,
2018                        loop_body: @ast::expr) {
2019         // a loop body is the special argument to a `for` loop.  We know that
2020         // there will be an expected type in this context because it can only
2021         // appear in the context of a call, so we get the expected type of the
2022         // parameter. The catch here is that we need to validate two things:
2023         // 1. a closure that returns a bool is expected
2024         // 2. the closure that was given returns unit
2025         let tcx = fcx.tcx();
2026         let mut err_happened = false;
2027         let expected_sty = unpack_expected(fcx, expected, |x| Some(copy *x));
2028         let inner_ty = match expected_sty {
2029             Some(ty::ty_closure(ref fty)) => {
2030                 match fcx.mk_subty(false, expr.span,
2031                                    fty.sig.output, ty::mk_bool(tcx)) {
2032                     result::Ok(_) => {
2033                         ty::mk_closure(tcx, ty::ClosureTy {
2034                             sig: FnSig {output: ty::mk_nil(tcx),
2035                                         ..copy fty.sig},
2036                             ..copy *fty
2037                         })
2038                     }
2039                     result::Err(_) => {
2040                         fcx.type_error_message(
2041                             expr.span,
2042                             |actual| {
2043                                 let did_you_mean = {
2044                                     if ty::type_is_nil(fty.sig.output) {
2045                                         "\nDid you mean to use \
2046                                              `do` instead of `for`?"
2047                                      } else {
2048                                          ""
2049                                      }
2050                                 };
2051                                 fmt!("A `for` loop iterator should expect a \
2052                                       closure that returns `bool`. This \
2053                                       iterator expects a closure that \
2054                                       returns `%s`.%s",
2055                                      actual, did_you_mean)
2056                             },
2057                             fty.sig.output,
2058                             None);
2059                         err_happened = true;
2060
2061                         // Kind of a hack: create a function type with
2062                         // the result replaced with ty_err, to
2063                         // suppress derived errors.
2064                         let t = ty::replace_closure_return_type(
2065                             tcx, ty::mk_closure(tcx, copy *fty),
2066                             ty::mk_err(tcx));
2067                         fcx.write_ty(expr.id, ty::mk_err(tcx));
2068                         t
2069                     }
2070                 }
2071             }
2072             _ => {
2073                 match expected {
2074                     Some(expected_t) => {
2075                         fcx.type_error_message(
2076                             expr.span,
2077                             |actual| {
2078                                 fmt!("last argument in `for` call \
2079                                       has non-closure type: %s",
2080                                      actual)
2081                             },
2082                             expected_t, None);
2083                         let err_ty = ty::mk_err(tcx);
2084                         fcx.write_ty(expr.id, err_ty);
2085                         err_happened = true;
2086                         err_ty
2087                     }
2088                     None => fcx.tcx().sess.impossible_case(
2089                         expr.span,
2090                         ~"loop body must have an expected type")
2091                 }
2092             }
2093         };
2094
2095         match loop_body.node {
2096             ast::expr_fn_block(ref decl, ref body) => {
2097                 // If an error occurred, we pretend this isn't a for
2098                 // loop, so as to assign types to all nodes while also
2099                 // propagating ty_err throughout so as to suppress
2100                 // derived errors. If we passed in ForLoop in the
2101                 // error case, we'd potentially emit a spurious error
2102                 // message because of the indirect_ret_ty.
2103                 let fn_kind = if err_happened {
2104                     Vanilla
2105                 } else {
2106                     let indirect_ret_ty =
2107                         fcx.indirect_ret_ty.get_or_default(fcx.ret_ty);
2108                     ForLoop(indirect_ret_ty)
2109                 };
2110                 check_expr_fn(fcx, loop_body, None,
2111                               decl, body, fn_kind, Some(inner_ty));
2112                 demand::suptype(fcx, loop_body.span,
2113                                 inner_ty, fcx.expr_ty(loop_body));
2114             }
2115             ref n => {
2116                 fail!(fmt!(
2117                     "check_loop_body expected expr_fn_block, not %?", n))
2118             }
2119         }
2120
2121         let block_ty = structurally_resolved_type(
2122             fcx, expr.span, fcx.node_ty(loop_body.id));
2123         if err_happened {
2124             fcx.write_ty(expr.id, ty::mk_err(fcx.tcx()));
2125         } else {
2126             let loop_body_ty =
2127                 ty::replace_closure_return_type(
2128                     tcx, block_ty, ty::mk_bool(tcx));
2129             fcx.write_ty(expr.id, loop_body_ty);
2130         }
2131     }
2132
2133     let tcx = fcx.ccx.tcx;
2134     let id = expr.id;
2135     let mut bot = false;
2136     match /*bad*/copy expr.node {
2137       ast::expr_vstore(ev, vst) => {
2138         let typ = match /*bad*/copy ev.node {
2139           ast::expr_lit(@codemap::spanned { node: ast::lit_str(s), _ }) => {
2140             let tt = ast_expr_vstore_to_vstore(fcx, ev, str::len(*s), vst);
2141             ty::mk_estr(tcx, tt)
2142           }
2143           ast::expr_vec(args, mutbl) => {
2144             let tt = ast_expr_vstore_to_vstore(fcx, ev, args.len(), vst);
2145             let mutability;
2146             match vst {
2147                 ast::expr_vstore_mut_box | ast::expr_vstore_mut_slice => {
2148                     mutability = ast::m_mutbl
2149                 }
2150                 _ => mutability = mutbl
2151             }
2152             let t: ty::t = fcx.infcx().next_ty_var();
2153             for args.each |e| { bot |= check_expr_has_type(fcx, *e, t); }
2154             ty::mk_evec(tcx, ty::mt {ty: t, mutbl: mutability}, tt)
2155           }
2156           ast::expr_repeat(element, count_expr, mutbl) => {
2157             let count = ty::eval_repeat_count(tcx, count_expr);
2158             fcx.write_ty(count_expr.id, ty::mk_uint(tcx));
2159             let tt = ast_expr_vstore_to_vstore(fcx, ev, count, vst);
2160             let t: ty::t = fcx.infcx().next_ty_var();
2161             bot |= check_expr_has_type(fcx, element, t);
2162             ty::mk_evec(tcx, ty::mt {ty: t, mutbl: mutbl}, tt)
2163           }
2164           _ =>
2165             tcx.sess.span_bug(expr.span, ~"vstore modifier on non-sequence")
2166         };
2167         fcx.write_ty(ev.id, typ);
2168         fcx.write_ty(id, typ);
2169       }
2170
2171       ast::expr_lit(lit) => {
2172         let typ = check_lit(fcx, lit);
2173         fcx.write_ty(id, typ);
2174       }
2175       ast::expr_binary(op, lhs, rhs) => {
2176         bot |= check_binop(fcx, expr, op, lhs, rhs);
2177       }
2178       ast::expr_assign_op(op, lhs, rhs) => {
2179         bot |= check_binop(fcx, expr, op, lhs, rhs);
2180         let lhs_t = fcx.expr_ty(lhs);
2181         let result_t = fcx.expr_ty(expr);
2182         demand::suptype(fcx, expr.span, result_t, lhs_t);
2183
2184         // Overwrite result of check_binop...this preserves existing behavior
2185         // but seems quite dubious with regard to user-defined methods
2186         // and so forth. - Niko
2187         fcx.write_nil(expr.id);
2188       }
2189       ast::expr_unary(unop, oprnd) => {
2190         let exp_inner = do unpack_expected(fcx, expected) |sty| {
2191             match unop {
2192               ast::box(_) | ast::uniq(_) => match *sty {
2193                 ty::ty_box(ref mt) | ty::ty_uniq(ref mt) => Some(mt.ty),
2194                 _ => None
2195               },
2196               ast::not | ast::neg => expected,
2197               ast::deref => None
2198             }
2199         };
2200         bot = check_expr_with_opt_hint(fcx, oprnd, exp_inner);
2201         let mut oprnd_t = fcx.expr_ty(oprnd);
2202         match unop {
2203           ast::box(mutbl) => {
2204             oprnd_t = ty::mk_box(tcx, ty::mt {ty: oprnd_t, mutbl: mutbl});
2205           }
2206           ast::uniq(mutbl) => {
2207             oprnd_t = ty::mk_uniq(tcx, ty::mt {ty: oprnd_t, mutbl: mutbl});
2208           }
2209           ast::deref => {
2210             let sty = structure_of(fcx, expr.span, oprnd_t);
2211
2212             match sty {
2213               // deref'ing an unsafe pointer requires that we be in an unsafe
2214               // context
2215               ty::ty_ptr(*) => {
2216                 fcx.require_unsafe(
2217                     expr.span,
2218                     ~"dereference of unsafe pointer");
2219               }
2220               _ => { /*ok*/ }
2221             }
2222
2223             let operand_ty = ty::deref_sty(tcx, &sty, true);
2224
2225             match operand_ty {
2226               Some(mt) => {
2227                   oprnd_t = mt.ty
2228               }
2229               None => {
2230                 match sty {
2231                   ty::ty_enum(*) => {
2232                     tcx.sess.span_err(
2233                         expr.span,
2234                         ~"can only dereference enums \
2235                          with a single variant which has a \
2236                          single argument");
2237                   }
2238                   ty::ty_struct(*) => {
2239                     tcx.sess.span_err(
2240                         expr.span,
2241                         ~"can only dereference structs with one anonymous \
2242                           field");
2243                   }
2244                   _ => {
2245                       fcx.type_error_message(expr.span, |actual| {
2246                           fmt!("type %s cannot be dereferenced", actual)
2247                       }, oprnd_t, None);
2248                   }
2249                 }
2250               }
2251             }
2252           }
2253           ast::not => {
2254             oprnd_t = structurally_resolved_type(fcx, oprnd.span, oprnd_t);
2255             if !(ty::type_is_integral(oprnd_t) ||
2256                  ty::get(oprnd_t).sty == ty::ty_bool) {
2257                 oprnd_t = check_user_unop(fcx, ~"!", ~"not", expr,
2258                                          oprnd, oprnd_t);
2259             }
2260           }
2261           ast::neg => {
2262             oprnd_t = structurally_resolved_type(fcx, oprnd.span, oprnd_t);
2263             if !(ty::type_is_integral(oprnd_t) ||
2264                  ty::type_is_fp(oprnd_t)) {
2265                 oprnd_t = check_user_unop(fcx, ~"-", ~"neg", expr,
2266                                          oprnd, oprnd_t);
2267             }
2268           }
2269         }
2270         fcx.write_ty(id, oprnd_t);
2271       }
2272       ast::expr_addr_of(mutbl, oprnd) => {
2273           let hint = unpack_expected(
2274               fcx, expected,
2275               |sty| match *sty { ty::ty_rptr(_, ref mt) => Some(mt.ty),
2276                                  _ => None });
2277         bot = check_expr_with_opt_hint(fcx, oprnd, hint);
2278
2279         // Note: at this point, we cannot say what the best lifetime
2280         // is to use for resulting pointer.  We want to use the
2281         // shortest lifetime possible so as to avoid spurious borrowck
2282         // errors.  Moreover, the longest lifetime will depend on the
2283         // precise details of the value whose address is being taken
2284         // (and how long it is valid), which we don't know yet until type
2285         // inference is complete.
2286         //
2287         // Therefore, here we simply generate a region variable with
2288         // the current expression as a lower bound.  The region
2289         // inferencer will then select the ultimate value.  Finally,
2290         // borrowck is charged with guaranteeing that the value whose
2291         // address was taken can actually be made to live as long as
2292         // it needs to live.
2293         let region = fcx.infcx().next_region_var(expr.span, expr.id);
2294
2295         let tm = ty::mt { ty: fcx.expr_ty(oprnd), mutbl: mutbl };
2296         let oprnd_t = ty::mk_rptr(tcx, region, tm);
2297         fcx.write_ty(id, oprnd_t);
2298       }
2299       ast::expr_path(pth) => {
2300         let defn = lookup_def(fcx, pth.span, id);
2301
2302         let tpt = ty_param_bounds_and_ty_for_def(fcx, expr.span, defn);
2303         let region_lb = ty::re_scope(expr.id);
2304         instantiate_path(fcx, pth, tpt, expr.span, expr.id, region_lb);
2305       }
2306       ast::expr_inline_asm(*) => {
2307           fcx.require_unsafe(expr.span, ~"use of inline assembly");
2308           fcx.write_nil(id);
2309       }
2310       ast::expr_mac(_) => tcx.sess.bug(~"unexpanded macro"),
2311       ast::expr_break(_) => { fcx.write_bot(id); bot = true; }
2312       ast::expr_again(_) => { fcx.write_bot(id); bot = true; }
2313       ast::expr_ret(expr_opt) => {
2314         bot = true;
2315         let ret_ty = match fcx.indirect_ret_ty {
2316           Some(t) =>  t, None => fcx.ret_ty
2317         };
2318         match expr_opt {
2319           None => match fcx.mk_eqty(false, expr.span,
2320                                     ret_ty, ty::mk_nil(tcx)) {
2321             result::Ok(_) => { /* fall through */ }
2322             result::Err(_) => {
2323                 tcx.sess.span_err(
2324                     expr.span,
2325                     ~"`return;` in function returning non-nil");
2326             }
2327           },
2328           Some(e) => {
2329               check_expr_has_type(fcx, e, ret_ty);
2330           }
2331         }
2332         fcx.write_bot(id);
2333       }
2334       ast::expr_log(_, lv, e) => {
2335         bot = check_expr_has_type(fcx, lv,
2336                                   ty::mk_mach_uint(tcx, ast::ty_u32));
2337
2338         // Note: this does not always execute, so do not propagate bot:
2339         check_expr(fcx, e);
2340         fcx.write_nil(id);
2341       }
2342       ast::expr_copy(a) => {
2343         bot = check_expr_with_opt_hint(fcx, a, expected);
2344         fcx.write_ty(id, fcx.expr_ty(a));
2345       }
2346       ast::expr_paren(a) => {
2347         bot = check_expr_with_opt_hint(fcx, a, expected);
2348         fcx.write_ty(id, fcx.expr_ty(a));
2349       }
2350       ast::expr_assign(lhs, rhs) => {
2351         bot = check_assignment(fcx, lhs, rhs, id);
2352       }
2353       ast::expr_swap(lhs, rhs) => {
2354         bot = check_assignment(fcx, lhs, rhs, id);
2355       }
2356       ast::expr_if(cond, ref thn, elsopt) => {
2357         bot = check_expr_has_type(fcx, cond, ty::mk_bool(tcx));
2358         bot |= check_then_else(fcx, thn, elsopt, id, expr.span);
2359       }
2360       ast::expr_while(cond, ref body) => {
2361         bot = check_expr_has_type(fcx, cond, ty::mk_bool(tcx));
2362         check_block_no_value(fcx, body);
2363         fcx.write_ty(id, ty::mk_nil(tcx));
2364       }
2365       ast::expr_loop(ref body, _) => {
2366         check_block_no_value(fcx, body);
2367         fcx.write_ty(id, ty::mk_nil(tcx));
2368         bot = !may_break(tcx, expr.id, body);
2369       }
2370       ast::expr_match(discrim, ref arms) => {
2371         bot = _match::check_match(fcx, expr, discrim, (/*bad*/copy *arms));
2372       }
2373       ast::expr_fn_block(ref decl, ref body) => {
2374         check_expr_fn(fcx, expr, None,
2375                       decl, body, Vanilla, expected);
2376       }
2377       ast::expr_loop_body(loop_body) => {
2378           check_loop_body(fcx, expr, expected, loop_body);
2379       }
2380       ast::expr_do_body(b) => {
2381         let expected_sty = unpack_expected(fcx, expected, |x| Some(copy *x));
2382         let inner_ty = match expected_sty {
2383             Some(ty::ty_closure(_)) => expected.get(),
2384             _ => match expected {
2385                 Some(expected_t) => {
2386                     fcx.type_error_message(expr.span, |actual| {
2387                         fmt!("last argument in `do` call \
2388                               has non-closure type: %s",
2389                              actual)
2390                     }, expected_t, None);
2391                     let err_ty = ty::mk_err(tcx);
2392                     fcx.write_ty(id, err_ty);
2393                     err_ty
2394                 }
2395                 None => {
2396                     fcx.tcx().sess.impossible_case(
2397                         expr.span,
2398                         ~"do body must have expected type")
2399                 }
2400             }
2401         };
2402         match b.node {
2403           ast::expr_fn_block(ref decl, ref body) => {
2404             check_expr_fn(fcx, b, None,
2405                           decl, body, DoBlock, Some(inner_ty));
2406             demand::suptype(fcx, b.span, inner_ty, fcx.expr_ty(b));
2407           }
2408           // argh
2409           _ => fail!(~"expected fn ty")
2410         }
2411         fcx.write_ty(expr.id, fcx.node_ty(b.id));
2412       }
2413       ast::expr_block(ref b) => {
2414         // If this is an unchecked block, turn off purity-checking
2415         bot = check_block_with_expected(fcx, b, expected);
2416         let typ =
2417             match b.node.expr {
2418               Some(expr) => fcx.expr_ty(expr),
2419               None => ty::mk_nil(tcx)
2420             };
2421         fcx.write_ty(id, typ);
2422       }
2423       ast::expr_call(f, args, sugar) => {
2424         bot = check_call(fcx, expr.span, expr.id, f, args, sugar);
2425       }
2426       ast::expr_method_call(rcvr, ident, tps, args, sugar) => {
2427         bot = check_method_call(fcx, expr, rcvr, ident, args, tps, sugar);
2428       }
2429       ast::expr_cast(e, t) => {
2430         bot = check_expr(fcx, e);
2431         let t_1 = fcx.to_ty(t);
2432         let t_e = fcx.expr_ty(e);
2433
2434         debug!("t_1=%s", fcx.infcx().ty_to_str(t_1));
2435         debug!("t_e=%s", fcx.infcx().ty_to_str(t_e));
2436
2437         match ty::get(t_1).sty {
2438           // This will be looked up later on
2439           ty::ty_trait(*) => (),
2440
2441           _ => {
2442             if ty::type_is_nil(t_e) {
2443                 fcx.type_error_message(expr.span, |actual| {
2444                     fmt!("cast from nil: `%s` as `%s`", actual,
2445                          fcx.infcx().ty_to_str(t_1))
2446                 }, t_e, None);
2447             } else if ty::type_is_nil(t_1) {
2448                 fcx.type_error_message(expr.span, |actual| {
2449                     fmt!("cast to nil: `%s` as `%s`", actual,
2450                          fcx.infcx().ty_to_str(t_1))
2451                 }, t_e, None);
2452             }
2453
2454             let t_1_is_scalar = type_is_scalar(fcx, expr.span, t_1);
2455             if type_is_c_like_enum(fcx,expr.span,t_e) && t_1_is_scalar {
2456                 /* this case is allowed */
2457             } else if type_is_region_ptr(fcx, expr.span, t_e) &&
2458                       type_is_unsafe_ptr(fcx, expr.span, t_1) {
2459
2460                 fn is_vec(t: ty::t) -> bool {
2461                     match ty::get(t).sty {
2462                       ty::ty_evec(_,_) => true,
2463                       _ => false
2464                     }
2465                 }
2466                 fn types_compatible(fcx: @mut FnCtxt, sp: span, t1: ty::t,
2467                                     t2: ty::t) -> bool {
2468                     if !is_vec(t1) {
2469                         false
2470                     } else {
2471                         let el = ty::sequence_element_type(fcx.tcx(), t1);
2472                         infer::mk_eqty(fcx.infcx(), false, sp, el, t2).is_ok()
2473                     }
2474                 }
2475
2476                 // Due to the limitations of LLVM global constants,
2477                 // region pointers end up pointing at copies of
2478                 // vector elements instead of the original values.
2479                 // To allow unsafe pointers to work correctly, we
2480                 // need to special-case obtaining an unsafe pointer
2481                 // from a region pointer to a vector.
2482
2483                 /* this cast is only allowed from &[T] to *T or
2484                    &T to *T. */
2485                 let te = structurally_resolved_type(fcx, e.span, t_e);
2486                 match (&ty::get(te).sty, &ty::get(t_1).sty) {
2487                   (&ty::ty_rptr(_, mt1), &ty::ty_ptr(mt2))
2488                     if types_compatible(fcx, e.span, mt1.ty, mt2.ty) => {
2489                       /* this case is allowed */
2490                   }
2491                   _ => {
2492                     demand::coerce(fcx, e.span, t_1, e);
2493                   }
2494                 }
2495             } else if !(type_is_scalar(fcx,expr.span,t_e) && t_1_is_scalar) {
2496                 /*
2497                 If more type combinations should be supported than are
2498                 supported here, then file an enhancement issue and record the
2499                 issue number in this comment.
2500                 */
2501                 fcx.type_error_message(expr.span, |actual| {
2502                     fmt!("non-scalar cast: `%s` as `%s`", actual,
2503                          fcx.infcx().ty_to_str(t_1))
2504                 }, t_e, None);
2505             }
2506           }
2507         }
2508         fcx.write_ty(id, t_1);
2509       }
2510       ast::expr_vec(args, mutbl) => {
2511         let t: ty::t = fcx.infcx().next_ty_var();
2512         for args.each |e| { bot |= check_expr_has_type(fcx, *e, t); }
2513         let typ = ty::mk_evec(tcx, ty::mt {ty: t, mutbl: mutbl},
2514                               ty::vstore_fixed(args.len()));
2515         fcx.write_ty(id, typ);
2516       }
2517       ast::expr_repeat(element, count_expr, mutbl) => {
2518         let count = ty::eval_repeat_count(tcx, count_expr);
2519         fcx.write_ty(count_expr.id, ty::mk_uint(tcx));
2520         let t: ty::t = fcx.infcx().next_ty_var();
2521         bot |= check_expr_has_type(fcx, element, t);
2522         let t = ty::mk_evec(tcx, ty::mt {ty: t, mutbl: mutbl},
2523                             ty::vstore_fixed(count));
2524         fcx.write_ty(id, t);
2525       }
2526       ast::expr_tup(elts) => {
2527         let flds = unpack_expected(fcx, expected, |sty| {
2528             match *sty { ty::ty_tup(ref flds) => Some(copy *flds), _ => None }
2529         });
2530         let elt_ts = do elts.mapi |i, e| {
2531             check_expr_with_opt_hint(fcx, *e, flds.map(|fs| fs[i]));
2532             fcx.expr_ty(*e)
2533         };
2534         let typ = ty::mk_tup(tcx, elt_ts);
2535         fcx.write_ty(id, typ);
2536       }
2537       ast::expr_struct(path, ref fields, base_expr) => {
2538         // Resolve the path.
2539         match tcx.def_map.find(&id) {
2540             Some(ast::def_struct(type_def_id)) => {
2541                 check_struct_constructor(fcx, id, expr.span, type_def_id,
2542                                          (/*bad*/copy *fields), base_expr);
2543             }
2544             Some(ast::def_variant(enum_id, variant_id)) => {
2545                 check_struct_enum_variant(fcx, id, expr.span, enum_id,
2546                                           variant_id, (/*bad*/copy *fields));
2547             }
2548             _ => {
2549                 tcx.sess.span_bug(path.span, ~"structure constructor does \
2550                                                not name a structure type");
2551             }
2552         }
2553       }
2554       ast::expr_field(base, field, tys) => {
2555         bot = check_field(fcx, expr, false, base, field, tys);
2556       }
2557       ast::expr_index(base, idx) => {
2558           bot |= check_expr(fcx, base);
2559           let raw_base_t = fcx.expr_ty(base);
2560           let (base_t, derefs) = do_autoderef(fcx, expr.span, raw_base_t);
2561           bot |= check_expr(fcx, idx);
2562           let idx_t = fcx.expr_ty(idx);
2563           let base_sty = structure_of(fcx, expr.span, base_t);
2564           match ty::index_sty(tcx, &base_sty) {
2565               Some(mt) => {
2566                   require_integral(fcx, idx.span, idx_t);
2567                   fcx.write_ty(id, mt.ty);
2568                   fcx.write_autoderef_adjustment(base.id, derefs);
2569               }
2570               None => {
2571                   let resolved = structurally_resolved_type(fcx, expr.span,
2572                                                             raw_base_t);
2573                   match lookup_op_method(fcx, expr, base, resolved,
2574                                          tcx.sess.ident_of(~"index"),
2575                                          ~[idx], DontDerefArgs) {
2576                       Some((ret_ty, _)) => fcx.write_ty(id, ret_ty),
2577                       _ => {
2578                           fcx.type_error_message(expr.span, |actual|
2579                               fmt!("cannot index a value of type `%s`",
2580                                    actual), base_t, None);
2581                           fcx.write_ty(id, ty::mk_err(tcx));
2582                           return true;
2583                       }
2584                   }
2585               }
2586           }
2587       }
2588     }
2589     if bot { fcx.write_bot(expr.id); }
2590
2591     debug!("type of expr %s is...",
2592            syntax::print::pprust::expr_to_str(expr, tcx.sess.intr()));
2593     debug!("... %s, expected is %s",
2594            ppaux::ty_to_str(tcx, fcx.expr_ty(expr)),
2595            match expected {
2596                Some(t) => ppaux::ty_to_str(tcx, t),
2597                _ => ~"empty"
2598            });
2599
2600     unifier();
2601
2602     debug!("<< bot=%b", bot);
2603     return bot;
2604 }
2605
2606 pub fn require_integral(fcx: @mut FnCtxt, sp: span, t: ty::t) {
2607     if !type_is_integral(fcx, sp, t) {
2608         fcx.type_error_message(sp, |actual| {
2609             fmt!("mismatched types: expected integral type but found `%s`",
2610                  actual)
2611         }, t, None);
2612     }
2613 }
2614
2615 pub fn check_decl_initializer(fcx: @mut FnCtxt,
2616                               nid: ast::node_id,
2617                               init: @ast::expr)
2618                            -> bool {
2619     let local_ty = fcx.local_ty(init.span, nid);
2620     return check_expr_coercable_to_type(fcx, init, local_ty);
2621 }
2622
2623 pub fn check_decl_local(fcx: @mut FnCtxt, local: @ast::local) -> bool {
2624     let mut bot = false;
2625     let tcx = fcx.ccx.tcx;
2626
2627     let t = fcx.local_ty(local.span, local.node.id);
2628     fcx.write_ty(local.node.id, t);
2629
2630     match local.node.init {
2631         Some(init) => {
2632             bot = check_decl_initializer(fcx, local.node.id, init);
2633         }
2634         _ => {}
2635     }
2636
2637     let region =
2638         ty::re_scope(tcx.region_map.get(&local.node.id));
2639     let pcx = pat_ctxt {
2640         fcx: fcx,
2641         map: pat_id_map(tcx.def_map, local.node.pat),
2642         match_region: region,
2643         block_region: region,
2644     };
2645     _match::check_pat(pcx, local.node.pat, t);
2646     return bot;
2647 }
2648
2649 pub fn check_stmt(fcx: @mut FnCtxt, stmt: @ast::stmt) -> bool {
2650     let mut node_id;
2651     let mut bot = false;
2652     match stmt.node {
2653       ast::stmt_decl(decl, id) => {
2654         node_id = id;
2655         match /*bad*/copy decl.node {
2656           ast::decl_local(ls) => for ls.each |l| {
2657             bot |= check_decl_local(fcx, *l);
2658           },
2659           ast::decl_item(_) => {/* ignore for now */ }
2660         }
2661       }
2662       ast::stmt_expr(expr, id) => {
2663         node_id = id;
2664         bot = check_expr_has_type(fcx, expr, ty::mk_nil(fcx.ccx.tcx));
2665       }
2666       ast::stmt_semi(expr, id) => {
2667         node_id = id;
2668         bot = check_expr(fcx, expr);
2669       }
2670       ast::stmt_mac(*) => fcx.ccx.tcx.sess.bug(~"unexpanded macro")
2671     }
2672     fcx.write_nil(node_id);
2673     return bot;
2674 }
2675
2676 pub fn check_block_no_value(fcx: @mut FnCtxt, blk: &ast::blk) -> bool {
2677     let bot = check_block(fcx, blk);
2678     if !bot {
2679         let blkty = fcx.node_ty(blk.node.id);
2680         let nilty = ty::mk_nil(fcx.ccx.tcx);
2681         demand::suptype(fcx, blk.span, nilty, blkty);
2682     }
2683     return bot;
2684 }
2685
2686 pub fn check_block(fcx0: @mut FnCtxt, blk: &ast::blk) -> bool {
2687     check_block_with_expected(fcx0, blk, None)
2688 }
2689
2690 pub fn check_block_with_expected(fcx0: @mut FnCtxt,
2691                                  blk: &ast::blk,
2692                                  expected: Option<ty::t>)
2693                               -> bool {
2694     let fcx = match blk.node.rules {
2695       ast::unsafe_blk => @mut FnCtxt {purity: ast::unsafe_fn,.. copy *fcx0},
2696       ast::default_blk => fcx0
2697     };
2698     do fcx.with_region_lb(blk.node.id) {
2699         let mut bot = false;
2700         let mut warned = false;
2701         for blk.node.stmts.each |s| {
2702             if bot && !warned &&
2703                 match s.node {
2704                   ast::stmt_decl(@codemap::spanned { node: ast::decl_local(_),
2705                                                  _}, _) |
2706                   ast::stmt_expr(_, _) | ast::stmt_semi(_, _) => {
2707                     true
2708                   }
2709                   _ => false
2710                 } {
2711                 fcx.ccx.tcx.sess.span_warn(s.span, ~"unreachable statement");
2712                 warned = true;
2713             }
2714             bot |= check_stmt(fcx, *s);
2715         }
2716         match blk.node.expr {
2717           None => fcx.write_nil(blk.node.id),
2718           Some(e) => {
2719             if bot && !warned {
2720                 fcx.ccx.tcx.sess.span_warn(e.span, ~"unreachable expression");
2721             }
2722             bot |= check_expr_with_opt_hint(fcx, e, expected);
2723             let ety = fcx.expr_ty(e);
2724             fcx.write_ty(blk.node.id, ety);
2725           }
2726         }
2727         if bot {
2728             fcx.write_bot(blk.node.id);
2729         }
2730         bot
2731     }
2732 }
2733
2734 pub fn check_const(ccx: @mut CrateCtxt,
2735                    sp: span,
2736                    e: @ast::expr,
2737                    id: ast::node_id) {
2738     let rty = ty::node_id_to_type(ccx.tcx, id);
2739     let fcx = blank_fn_ctxt(ccx, rty, e.id);
2740     let declty = fcx.ccx.tcx.tcache.get(&local_def(id)).ty;
2741     check_const_with_ty(fcx, sp, e, declty);
2742 }
2743
2744 pub fn check_const_with_ty(fcx: @mut FnCtxt,
2745                            _: span,
2746                            e: @ast::expr,
2747                            declty: ty::t) {
2748     check_expr(fcx, e);
2749     let cty = fcx.expr_ty(e);
2750     demand::suptype(fcx, e.span, declty, cty);
2751     regionck::regionck_expr(fcx, e);
2752     writeback::resolve_type_vars_in_expr(fcx, e);
2753 }
2754
2755 /// Checks whether a type can be created without an instance of itself.
2756 /// This is similar but different from the question of whether a type
2757 /// can be represented.  For example, the following type:
2758 ///
2759 ///     enum foo { None, Some(foo) }
2760 ///
2761 /// is instantiable but is not representable.  Similarly, the type
2762 ///
2763 ///     enum foo { Some(@foo) }
2764 ///
2765 /// is representable, but not instantiable.
2766 pub fn check_instantiable(tcx: ty::ctxt,
2767                           sp: span,
2768                           item_id: ast::node_id) {
2769     let item_ty = ty::node_id_to_type(tcx, item_id);
2770     if !ty::is_instantiable(tcx, item_ty) {
2771         tcx.sess.span_err(sp, fmt!("this type cannot be instantiated \
2772                   without an instance of itself; \
2773                   consider using `Option<%s>`",
2774                                    ppaux::ty_to_str(tcx, item_ty)));
2775     }
2776 }
2777
2778 pub fn check_enum_variants(ccx: @mut CrateCtxt,
2779                            sp: span,
2780                            +vs: ~[ast::variant],
2781                            id: ast::node_id) {
2782     fn do_check(ccx: @mut CrateCtxt,
2783                 sp: span,
2784                 vs: ~[ast::variant],
2785                 id: ast::node_id,
2786                 disr_vals: &mut ~[int],
2787                 disr_val: &mut int,
2788                 variants: &mut ~[ty::VariantInfo]) {
2789         let rty = ty::node_id_to_type(ccx.tcx, id);
2790         for vs.each |v| {
2791             for v.node.disr_expr.each |e_ref| {
2792                 let e = *e_ref;
2793                 debug!("disr expr, checking %s",
2794                        pprust::expr_to_str(e, ccx.tcx.sess.intr()));
2795                 let declty = ty::mk_int(ccx.tcx);
2796                 let fcx = blank_fn_ctxt(ccx, rty, e.id);
2797                 check_const_with_ty(fcx, e.span, e, declty);
2798                 // check_expr (from check_const pass) doesn't guarantee
2799                 // that the expression is in an form that eval_const_expr can
2800                 // handle, so we may still get an internal compiler error
2801
2802                 match const_eval::eval_const_expr_partial(ccx.tcx, e) {
2803                   Ok(const_eval::const_int(val)) => {
2804                     *disr_val = val as int;
2805                   }
2806                   Ok(_) => {
2807                     ccx.tcx.sess.span_err(e.span, ~"expected signed integer \
2808                                                     constant");
2809                   }
2810                   Err(ref err) => {
2811                     ccx.tcx.sess.span_err(e.span,
2812                      fmt!("expected constant: %s", (*err)));
2813
2814                   }
2815                 }
2816             }
2817             if vec::contains(*disr_vals, &*disr_val) {
2818                 ccx.tcx.sess.span_err(v.span,
2819                                       ~"discriminator value already exists");
2820             }
2821             disr_vals.push(*disr_val);
2822             let ctor_ty = ty::node_id_to_type(ccx.tcx, v.node.id);
2823             let arg_tys;
2824
2825             let this_disr_val = *disr_val;
2826             *disr_val += 1;
2827
2828             match v.node.kind {
2829                 ast::tuple_variant_kind(ref args) if args.len() > 0u => {
2830                     arg_tys = Some(ty::ty_fn_args(ctor_ty).map(|a| a.ty));
2831                 }
2832                 ast::tuple_variant_kind(_) => {
2833                     arg_tys = Some(~[]);
2834                 }
2835                 ast::struct_variant_kind(_) => {
2836                     arg_tys = Some(ty::lookup_struct_fields(
2837                         ccx.tcx, local_def(v.node.id)).map(|cf|
2838                             ty::node_id_to_type(ccx.tcx, cf.id.node)));
2839                 }
2840                 ast::enum_variant_kind(_) => {
2841                     arg_tys = None;
2842                     do_check(ccx,
2843                              sp,
2844                              /*bad*/copy vs,
2845                              id,
2846                              &mut *disr_vals,
2847                              &mut *disr_val,
2848                              &mut *variants);
2849                 }
2850             }
2851
2852             match arg_tys {
2853                 None => {}
2854                 Some(arg_tys) => {
2855                     variants.push(
2856                         @VariantInfo_{args: arg_tys, ctor_ty: ctor_ty,
2857                           name: v.node.name, id: local_def(v.node.id),
2858                           disr_val: this_disr_val, vis: v.node.vis});
2859                 }
2860             }
2861         }
2862     }
2863
2864     let rty = ty::node_id_to_type(ccx.tcx, id);
2865     let mut disr_vals: ~[int] = ~[];
2866     let mut disr_val = 0;
2867     let mut variants = ~[];
2868
2869     do_check(ccx, sp, vs, id, &mut disr_vals, &mut disr_val, &mut variants);
2870
2871     // cache so that ty::enum_variants won't repeat this work
2872     ccx.tcx.enum_var_cache.insert(local_def(id), @variants);
2873
2874     // Check that it is possible to represent this enum:
2875     let mut outer = true, did = local_def(id);
2876     if ty::type_structurally_contains(ccx.tcx, rty, |sty| {
2877         match *sty {
2878           ty::ty_enum(id, _) if id == did => {
2879             if outer { outer = false; false }
2880             else { true }
2881           }
2882           _ => false
2883         }
2884     }) {
2885         ccx.tcx.sess.span_err(sp, ~"illegal recursive enum type; \
2886                                  wrap the inner value in a box to \
2887                                  make it representable");
2888     }
2889
2890     // Check that it is possible to instantiate this enum:
2891     //
2892     // This *sounds* like the same that as representable, but it's
2893     // not.  See def'n of `check_instantiable()` for details.
2894     check_instantiable(ccx.tcx, sp, id);
2895 }
2896
2897 pub fn lookup_def(fcx: @mut FnCtxt, sp: span, id: ast::node_id) -> ast::def {
2898     lookup_def_ccx(fcx.ccx, sp, id)
2899 }
2900
2901 // Returns the type parameter count and the type for the given definition.
2902 pub fn ty_param_bounds_and_ty_for_def(fcx: @mut FnCtxt,
2903                                       sp: span,
2904                                       defn: ast::def)
2905                                    -> ty_param_bounds_and_ty {
2906
2907     match defn {
2908       ast::def_arg(nid, _, _) | ast::def_local(nid, _) |
2909       ast::def_self(nid, _) | ast::def_binding(nid, _) => {
2910           let typ = fcx.local_ty(sp, nid);
2911           return no_params(typ);
2912       }
2913       ast::def_fn(_, ast::extern_fn) => {
2914         // extern functions are just u8 pointers
2915         return ty_param_bounds_and_ty {
2916             bounds: @~[],
2917             region_param: None,
2918             ty: ty::mk_ptr(
2919                 fcx.ccx.tcx,
2920                 ty::mt {
2921                     ty: ty::mk_mach_uint(fcx.ccx.tcx, ast::ty_u8),
2922                     mutbl: ast::m_imm
2923                 })
2924         };
2925       }
2926
2927       ast::def_fn(id, ast::unsafe_fn) |
2928       ast::def_static_method(id, _, ast::unsafe_fn) => {
2929         // Unsafe functions can only be touched in an unsafe context
2930         fcx.require_unsafe(sp, ~"access to unsafe function");
2931         return ty::lookup_item_type(fcx.ccx.tcx, id);
2932       }
2933
2934       ast::def_fn(id, _) | ast::def_static_method(id, _, _) |
2935       ast::def_const(id) | ast::def_variant(_, id) |
2936       ast::def_struct(id) => {
2937         return ty::lookup_item_type(fcx.ccx.tcx, id);
2938       }
2939       ast::def_upvar(_, inner, _, _) => {
2940         return ty_param_bounds_and_ty_for_def(fcx, sp, *inner);
2941       }
2942       ast::def_ty(_) | ast::def_prim_ty(_) | ast::def_ty_param(*)=> {
2943         fcx.ccx.tcx.sess.span_bug(sp, ~"expected value but found type");
2944       }
2945       ast::def_mod(*) | ast::def_foreign_mod(*) => {
2946         fcx.ccx.tcx.sess.span_bug(sp, ~"expected value but found module");
2947       }
2948       ast::def_use(*) => {
2949         fcx.ccx.tcx.sess.span_bug(sp, ~"expected value but found use");
2950       }
2951       ast::def_region(*) => {
2952         fcx.ccx.tcx.sess.span_bug(sp, ~"expected value but found region");
2953       }
2954       ast::def_typaram_binder(*) => {
2955         fcx.ccx.tcx.sess.span_bug(sp, ~"expected value but found type \
2956                                           parameter");
2957       }
2958       ast::def_label(*) => {
2959         fcx.ccx.tcx.sess.span_bug(sp, ~"expected value but found label");
2960       }
2961       ast::def_self_ty(*) => {
2962         fcx.ccx.tcx.sess.span_bug(sp, ~"expected value but found self ty");
2963       }
2964     }
2965 }
2966
2967 // Instantiates the given path, which must refer to an item with the given
2968 // number of type parameters and type.
2969 pub fn instantiate_path(fcx: @mut FnCtxt,
2970                         pth: @ast::path,
2971                         tpt: ty_param_bounds_and_ty,
2972                         span: span,
2973                         node_id: ast::node_id,
2974                         region_lb: ty::Region) {
2975     debug!(">>> instantiate_path");
2976
2977     let ty_param_count = vec::len(*tpt.bounds);
2978     let ty_substs_len = vec::len(pth.types);
2979
2980     // determine the region bound, using the value given by the user
2981     // (if any) and otherwise using a fresh region variable
2982     let self_r = match pth.rp {
2983       Some(_) => { // user supplied a lifetime parameter...
2984         match tpt.region_param {
2985           None => { // ...but the type is not lifetime parameterized!
2986             fcx.ccx.tcx.sess.span_err
2987                 (span, ~"this item is not region-parameterized");
2988             None
2989           }
2990           Some(_) => { // ...and the type is lifetime parameterized, ok.
2991             Some(ast_region_to_region(fcx, fcx, span, pth.rp))
2992           }
2993         }
2994       }
2995       None => { // no lifetime parameter supplied, insert default
2996         fcx.region_var_if_parameterized(
2997             tpt.region_param, span, region_lb)
2998       }
2999     };
3000
3001     // determine values for type parameters, using the values given by
3002     // the user (if any) and otherwise using fresh type variables
3003     let tps = if ty_substs_len == 0 {
3004         fcx.infcx().next_ty_vars(ty_param_count)
3005     } else if ty_param_count == 0 {
3006         fcx.ccx.tcx.sess.span_err
3007             (span, ~"this item does not take type parameters");
3008         fcx.infcx().next_ty_vars(ty_param_count)
3009     } else if ty_substs_len > ty_param_count {
3010         fcx.ccx.tcx.sess.span_err
3011             (span, ~"too many type parameters provided for this item");
3012         fcx.infcx().next_ty_vars(ty_param_count)
3013     } else if ty_substs_len < ty_param_count {
3014         fcx.ccx.tcx.sess.span_err
3015             (span, ~"not enough type parameters provided for this item");
3016         fcx.infcx().next_ty_vars(ty_param_count)
3017     } else {
3018         pth.types.map(|aty| fcx.to_ty(*aty))
3019     };
3020
3021     let substs = substs { self_r: self_r, self_ty: None, tps: tps };
3022     fcx.write_ty_substs(node_id, tpt.ty, substs);
3023
3024     debug!("<<<");
3025 }
3026
3027 // Resolves `typ` by a single level if `typ` is a type variable.  If no
3028 // resolution is possible, then an error is reported.
3029 pub fn structurally_resolved_type(fcx: @mut FnCtxt, sp: span, tp: ty::t)
3030                                -> ty::t {
3031     match infer::resolve_type(fcx.infcx(), tp, force_tvar) {
3032         Ok(t_s) if !ty::type_is_ty_var(t_s) => return t_s,
3033         _ => {
3034             fcx.type_error_message(sp, |_actual| {
3035                 ~"the type of this value must be known in this context"
3036             }, tp, None);
3037             return ty::mk_err(fcx.tcx());
3038         }
3039     }
3040 }
3041
3042 // Returns the one-level-deep structure of the given type.
3043 pub fn structure_of(fcx: @mut FnCtxt, sp: span, typ: ty::t) -> ty::sty {
3044     /*bad*/copy ty::get(structurally_resolved_type(fcx, sp, typ)).sty
3045 }
3046
3047 pub fn type_is_integral(fcx: @mut FnCtxt, sp: span, typ: ty::t) -> bool {
3048     let typ_s = structurally_resolved_type(fcx, sp, typ);
3049     return ty::type_is_integral(typ_s);
3050 }
3051
3052 pub fn type_is_scalar(fcx: @mut FnCtxt, sp: span, typ: ty::t) -> bool {
3053     let typ_s = structurally_resolved_type(fcx, sp, typ);
3054     return ty::type_is_scalar(typ_s);
3055 }
3056
3057 pub fn type_is_unsafe_ptr(fcx: @mut FnCtxt, sp: span, typ: ty::t) -> bool {
3058     let typ_s = structurally_resolved_type(fcx, sp, typ);
3059     return ty::type_is_unsafe_ptr(typ_s);
3060 }
3061
3062 pub fn type_is_region_ptr(fcx: @mut FnCtxt, sp: span, typ: ty::t) -> bool {
3063     let typ_s = structurally_resolved_type(fcx, sp, typ);
3064     return ty::type_is_region_ptr(typ_s);
3065 }
3066
3067 pub fn type_is_c_like_enum(fcx: @mut FnCtxt, sp: span, typ: ty::t) -> bool {
3068     let typ_s = structurally_resolved_type(fcx, sp, typ);
3069     return ty::type_is_c_like_enum(fcx.ccx.tcx, typ_s);
3070 }
3071
3072 pub fn ast_expr_vstore_to_vstore(fcx: @mut FnCtxt,
3073                                  e: @ast::expr,
3074                                  n: uint,
3075                                  v: ast::expr_vstore)
3076                               -> ty::vstore {
3077     match v {
3078         ast::expr_vstore_fixed(None) => ty::vstore_fixed(n),
3079         ast::expr_vstore_fixed(Some(u)) => {
3080             if n != u {
3081                 let s = fmt!("fixed-size sequence mismatch: %u vs. %u",u, n);
3082                 fcx.ccx.tcx.sess.span_err(e.span,s);
3083             }
3084             ty::vstore_fixed(u)
3085         }
3086         ast::expr_vstore_uniq => ty::vstore_uniq,
3087         ast::expr_vstore_box | ast::expr_vstore_mut_box => ty::vstore_box,
3088         ast::expr_vstore_slice | ast::expr_vstore_mut_slice => {
3089             let r = fcx.infcx().next_region_var(e.span, e.id);
3090             ty::vstore_slice(r)
3091         }
3092     }
3093 }
3094
3095 // Returns true if b contains a break that can exit from b
3096 pub fn may_break(cx: ty::ctxt, id: ast::node_id, b: &ast::blk) -> bool {
3097     // First: is there an unlabeled break immediately
3098     // inside the loop?
3099     (loop_query(b, |e| {
3100         match e {
3101             ast::expr_break(_) => true,
3102             _ => false
3103         }
3104     })) ||
3105    // Second: is there a labeled break with label
3106    // <id> nested anywhere inside the loop?
3107     (block_query(b, |e| {
3108         match e.node {
3109             ast::expr_break(Some(_)) =>
3110                 match cx.def_map.find(&e.id) {
3111                     Some(ast::def_label(loop_id)) if id == loop_id => true,
3112                     _ => false,
3113                 },
3114             _ => false
3115         }}))
3116 }
3117
3118 pub fn check_bounds_are_used(ccx: @mut CrateCtxt,
3119                              span: span,
3120                              tps: &OptVec<ast::TyParam>,
3121                              ty: ty::t) {
3122     debug!("check_bounds_are_used(n_tps=%u, ty=%s)",
3123            tps.len(), ppaux::ty_to_str(ccx.tcx, ty));
3124
3125     // make a vector of booleans initially false, set to true when used
3126     if tps.len() == 0u { return; }
3127     let mut tps_used = vec::from_elem(tps.len(), false);
3128
3129     ty::walk_regions_and_ty(
3130         ccx.tcx, ty,
3131         |_r| {},
3132         |t| {
3133             match ty::get(t).sty {
3134               ty::ty_param(param_ty {idx, _}) => {
3135                   debug!("Found use of ty param #%u", idx);
3136                   tps_used[idx] = true;
3137               }
3138               _ => ()
3139             }
3140             true
3141         });
3142
3143     for tps_used.eachi |i, b| {
3144         if !*b {
3145             ccx.tcx.sess.span_err(
3146                 span, fmt!("type parameter `%s` is unused",
3147                            *ccx.tcx.sess.str_of(tps.get(i).ident)));
3148         }
3149     }
3150 }
3151
3152 pub fn check_intrinsic_type(ccx: @mut CrateCtxt, it: @ast::foreign_item) {
3153     fn param(ccx: @mut CrateCtxt, n: uint) -> ty::t {
3154         ty::mk_param(ccx.tcx, n, local_def(0))
3155     }
3156     fn arg(m: ast::rmode, ty: ty::t) -> ty::arg {
3157         arg {mode: ast::expl(m), ty: ty}
3158     }
3159     let tcx = ccx.tcx;
3160     let (n_tps, inputs, output) = match *ccx.tcx.sess.str_of(it.ident) {
3161       ~"size_of" |
3162       ~"pref_align_of" | ~"min_align_of" => (1u, ~[], ty::mk_uint(ccx.tcx)),
3163       ~"init" => (1u, ~[], param(ccx, 0u)),
3164       ~"forget" => (1u, ~[arg(ast::by_copy, param(ccx, 0u))],
3165                     ty::mk_nil(tcx)),
3166       ~"reinterpret_cast" => (2u, ~[arg(ast::by_ref, param(ccx, 0u))],
3167                               param(ccx, 1u)),
3168       ~"addr_of" => (1u, ~[arg(ast::by_ref, param(ccx, 0u))],
3169                       ty::mk_imm_ptr(tcx, param(ccx, 0u))),
3170       ~"move_val" | ~"move_val_init" => {
3171           (1u, ~[arg(ast::by_copy,
3172                      ty::mk_mut_rptr(tcx, ty::re_bound(ty::br_anon(0)),
3173                                      param(ccx, 0u))),
3174                arg(ast::by_copy, param(ccx, 0u))],
3175          ty::mk_nil(tcx))
3176       }
3177       ~"needs_drop" => (1u, ~[], ty::mk_bool(tcx)),
3178
3179       ~"atomic_cxchg"    | ~"atomic_cxchg_acq"| ~"atomic_cxchg_rel" => {
3180         (0u, ~[arg(ast::by_copy,
3181                    ty::mk_mut_rptr(tcx, ty::re_bound(ty::br_anon(0)),
3182                                    ty::mk_int(tcx))),
3183                arg(ast::by_copy, ty::mk_int(tcx)),
3184                arg(ast::by_copy, ty::mk_int(tcx))],
3185          ty::mk_int(tcx))
3186       }
3187       ~"atomic_xchg"     | ~"atomic_xadd"     | ~"atomic_xsub"     |
3188       ~"atomic_xchg_acq" | ~"atomic_xadd_acq" | ~"atomic_xsub_acq" |
3189       ~"atomic_xchg_rel" | ~"atomic_xadd_rel" | ~"atomic_xsub_rel" => {
3190         (0u, ~[arg(ast::by_copy,
3191                    ty::mk_mut_rptr(tcx, ty::re_bound(ty::br_anon(0)),
3192                                    ty::mk_int(tcx))),
3193                arg(ast::by_copy, ty::mk_int(tcx))],
3194          ty::mk_int(tcx))
3195       }
3196
3197       ~"get_tydesc" => {
3198         // FIXME (#3730): return *intrinsic::tydesc, not *()
3199         (1u, ~[], ty::mk_nil_ptr(tcx))
3200       }
3201       ~"visit_tydesc" => {
3202           let tydesc_name = special_idents::tydesc;
3203           let ty_visitor_name = tcx.sess.ident_of(~"TyVisitor");
3204           fail_unless!(tcx.intrinsic_defs.contains_key(&tydesc_name));
3205           fail_unless!(ccx.tcx.intrinsic_defs.contains_key(&ty_visitor_name));
3206           let (_, tydesc_ty) = tcx.intrinsic_defs.get(&tydesc_name);
3207           let (_, visitor_trait) = tcx.intrinsic_defs.get(&ty_visitor_name);
3208           let td_ptr = ty::mk_ptr(ccx.tcx, ty::mt {ty: tydesc_ty,
3209                                                    mutbl: ast::m_imm});
3210           (0u, ~[arg(ast::by_val, td_ptr),
3211                  arg(ast::by_ref, visitor_trait)], ty::mk_nil(tcx))
3212       }
3213       ~"frame_address" => {
3214         let fty = ty::mk_closure(ccx.tcx, ty::ClosureTy {
3215             purity: ast::impure_fn,
3216             sigil: ast::BorrowedSigil,
3217             onceness: ast::Once,
3218             region: ty::re_bound(ty::br_anon(0)),
3219             sig: ty::FnSig {
3220                 inputs: ~[arg {mode: ast::expl(ast::by_val),
3221                                ty: ty::mk_imm_ptr(
3222                                    ccx.tcx,
3223                                    ty::mk_mach_uint(ccx.tcx, ast::ty_u8))}],
3224                 output: ty::mk_nil(ccx.tcx)
3225             }
3226         });
3227         (0u, ~[arg(ast::by_ref, fty)], ty::mk_nil(tcx))
3228       }
3229       ~"morestack_addr" => {
3230         (0u, ~[], ty::mk_nil_ptr(tcx))
3231       }
3232       ~"memmove32" => {
3233         (0, ~[arg(ast::by_copy,
3234                   ty::mk_ptr(tcx,
3235                     ty::mt { ty: ty::mk_u8(tcx), mutbl: ast::m_mutbl })),
3236               arg(ast::by_copy,
3237                   ty::mk_ptr(tcx,
3238                     ty::mt { ty: ty::mk_u8(tcx), mutbl: ast::m_imm })),
3239               arg(ast::by_copy,
3240                   ty::mk_u32(tcx))],
3241          ty::mk_nil(tcx))
3242       }
3243       ~"memmove64" => {
3244         (0, ~[arg(ast::by_copy,
3245                   ty::mk_ptr(tcx,
3246                     ty::mt { ty: ty::mk_u8(tcx), mutbl: ast::m_mutbl })),
3247               arg(ast::by_copy,
3248                   ty::mk_ptr(tcx,
3249                     ty::mt { ty: ty::mk_u8(tcx), mutbl: ast::m_imm })),
3250               arg(ast::by_copy,
3251                   ty::mk_u64(tcx))],
3252          ty::mk_nil(tcx))
3253       }
3254      ~"sqrtf32" => {
3255         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3256          ty::mk_f32(tcx))
3257      }
3258      ~"sqrtf64" => {
3259         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3260          ty::mk_f64(tcx))
3261      }
3262      ~"powif32" => {
3263         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx)),
3264                arg(ast::by_copy, ty::mk_i32(tcx))],
3265          ty::mk_f32(tcx))
3266      }
3267      ~"powif64" => {
3268         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx)),
3269                arg(ast::by_copy, ty::mk_i32(tcx))],
3270          ty::mk_f64(tcx))
3271      }
3272      ~"sinf32" => {
3273         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3274          ty::mk_f32(tcx))
3275      }
3276      ~"sinf64" => {
3277         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3278          ty::mk_f64(tcx))
3279      }
3280      ~"cosf32" => {
3281         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3282          ty::mk_f32(tcx))
3283      }
3284      ~"cosf64" => {
3285         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3286          ty::mk_f64(tcx))
3287      }
3288      ~"powf32" => {
3289         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx)),
3290                arg(ast::by_copy, ty::mk_f32(tcx))],
3291          ty::mk_f32(tcx))
3292      }
3293      ~"powf64" => {
3294         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx)),
3295                arg(ast::by_copy, ty::mk_f64(tcx))],
3296          ty::mk_f64(tcx))
3297      }
3298      ~"expf32" => {
3299         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3300          ty::mk_f32(tcx))
3301      }
3302      ~"expf64" => {
3303         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3304          ty::mk_f64(tcx))
3305      }
3306      ~"exp2f32" => {
3307         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3308          ty::mk_f32(tcx))
3309      }
3310      ~"exp2f64" => {
3311         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3312          ty::mk_f64(tcx))
3313      }
3314      ~"logf32" => {
3315         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3316          ty::mk_f32(tcx))
3317      }
3318      ~"logf64" => {
3319         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3320          ty::mk_f64(tcx))
3321      }
3322      ~"log10f32" => {
3323         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3324          ty::mk_f32(tcx))
3325      }
3326      ~"log10f64" => {
3327         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3328          ty::mk_f64(tcx))
3329      }
3330      ~"log2f32" => {
3331         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3332          ty::mk_f32(tcx))
3333      }
3334      ~"log2f64" => {
3335         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3336          ty::mk_f64(tcx))
3337      }
3338      ~"fmaf32" => {
3339         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx)),
3340                arg(ast::by_copy, ty::mk_f32(tcx)),
3341                arg(ast::by_copy, ty::mk_f32(tcx))],
3342          ty::mk_f32(tcx))
3343      }
3344      ~"fmaf64" => {
3345         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx)),
3346                arg(ast::by_copy, ty::mk_f64(tcx)),
3347                arg(ast::by_copy, ty::mk_f64(tcx))],
3348          ty::mk_f64(tcx))
3349      }
3350      ~"fabsf32" => {
3351         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3352          ty::mk_f32(tcx))
3353      }
3354      ~"fabsf64" => {
3355         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3356          ty::mk_f64(tcx))
3357      }
3358      ~"floorf32" => {
3359         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3360          ty::mk_f32(tcx))
3361      }
3362      ~"floorf64" => {
3363         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3364          ty::mk_f64(tcx))
3365      }
3366      ~"ceilf32" => {
3367         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3368          ty::mk_f32(tcx))
3369      }
3370      ~"ceilf64" => {
3371         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3372          ty::mk_f64(tcx))
3373      }
3374      ~"truncf32" => {
3375         (0u, ~[arg(ast::by_copy, ty::mk_f32(tcx))],
3376          ty::mk_f32(tcx))
3377      }
3378      ~"truncf64" => {
3379         (0u, ~[arg(ast::by_copy, ty::mk_f64(tcx))],
3380          ty::mk_f64(tcx))
3381      }
3382      ~"ctpop8" => {
3383         (0u, ~[arg(ast::by_copy, ty::mk_i8(tcx))],
3384          ty::mk_i8(tcx))
3385      }
3386      ~"ctpop16" => {
3387         (0u, ~[arg(ast::by_copy, ty::mk_i16(tcx))],
3388          ty::mk_i16(tcx))
3389      }
3390      ~"ctpop32" => {
3391         (0u, ~[arg(ast::by_copy, ty::mk_i32(tcx))],
3392          ty::mk_i32(tcx))
3393      }
3394      ~"ctpop64" => {
3395         (0u, ~[arg(ast::by_copy, ty::mk_i64(tcx))],
3396          ty::mk_i64(tcx))
3397      }
3398      ~"ctlz8" => {
3399          (0u, ~[arg(ast::by_copy, ty::mk_i8(tcx))],
3400          ty::mk_i8(tcx))
3401      }
3402      ~"ctlz16" => {
3403          (0u, ~[arg(ast::by_copy, ty::mk_i16(tcx))],
3404          ty::mk_i16(tcx))
3405      }
3406      ~"ctlz32" => {
3407          (0u, ~[arg(ast::by_copy, ty::mk_i32(tcx))],
3408          ty::mk_i32(tcx))
3409      }
3410      ~"ctlz64" => {
3411          (0u, ~[arg(ast::by_copy, ty::mk_i64(tcx))],
3412          ty::mk_i64(tcx))
3413      }
3414      ~"cttz8" => {
3415          (0u, ~[arg(ast::by_copy, ty::mk_i8(tcx))],
3416          ty::mk_i8(tcx))
3417      }
3418      ~"cttz16" => {
3419          (0u, ~[arg(ast::by_copy, ty::mk_i16(tcx))],
3420          ty::mk_i16(tcx))
3421      }
3422      ~"cttz32" => {
3423          (0u, ~[arg(ast::by_copy, ty::mk_i32(tcx))],
3424          ty::mk_i32(tcx))
3425      }
3426      ~"cttz64" => {
3427          (0u, ~[arg(ast::by_copy, ty::mk_i64(tcx))],
3428          ty::mk_i64(tcx))
3429      }
3430      ~"bswap16" => {
3431          (0u, ~[arg(ast::by_copy, ty::mk_i16(tcx))],
3432          ty::mk_i16(tcx))
3433      }
3434      ~"bswap32" => {
3435          (0u, ~[arg(ast::by_copy, ty::mk_i32(tcx))],
3436          ty::mk_i32(tcx))
3437      }
3438      ~"bswap64" => {
3439          (0u, ~[arg(ast::by_copy, ty::mk_i64(tcx))],
3440          ty::mk_i64(tcx))
3441      }
3442      ref other => {
3443         tcx.sess.span_err(it.span, ~"unrecognized intrinsic function: `" +
3444                           (*other) + ~"`");
3445         return;
3446       }
3447     };
3448     let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
3449         purity: ast::unsafe_fn,
3450         abi: ast::RustAbi,
3451         sig: FnSig {inputs: inputs,
3452                     output: output}
3453     });
3454     let i_ty = ty::lookup_item_type(ccx.tcx, local_def(it.id));
3455     let i_n_tps = (*i_ty.bounds).len();
3456     if i_n_tps != n_tps {
3457         tcx.sess.span_err(it.span, fmt!("intrinsic has wrong number \
3458                                          of type parameters: found %u, \
3459                                          expected %u", i_n_tps, n_tps));
3460     } else {
3461         require_same_types(
3462             tcx, None, false, it.span, i_ty.ty, fty,
3463             || fmt!("intrinsic has wrong type: \
3464                       expected `%s`",
3465                      ppaux::ty_to_str(ccx.tcx, fty)));
3466     }
3467 }