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