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

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