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

   1 // Copyright 2012-2014 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::lang_items::{ExchangeHeapLangItem, GcLangItem};
  82 use middle::lang_items::{ManagedHeapLangItem};
  83 use middle::lint::UnreachableCode;
  84 use middle::pat_util::pat_id_map;
  85 use middle::pat_util;
  86 use middle::subst::Subst;
  87 use middle::ty::{FnSig, VariantInfo};
  88 use middle::ty::{ty_param_bounds_and_ty, ty_param_substs_and_ty};
  89 use middle::ty::{substs, param_ty, Disr, ExprTyProvider};
  90 use middle::ty;
  91 use middle::ty_fold::TypeFolder;
  92 use middle::typeck::astconv::AstConv;
  93 use middle::typeck::astconv::{ast_region_to_region, ast_ty_to_ty};
  94 use middle::typeck::astconv;
  95 use middle::typeck::check::_match::pat_ctxt;
  96 use middle::typeck::check::method::{AutoderefReceiver};
  97 use middle::typeck::check::method::{AutoderefReceiverFlag};
  98 use middle::typeck::check::method::{CheckTraitsAndInherentMethods};
  99 use middle::typeck::check::method::{DontAutoderefReceiver};
 100 use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
 101 use middle::typeck::check::regionmanip::relate_free_regions;
 102 use middle::typeck::check::vtable::VtableContext;
 103 use middle::typeck::CrateCtxt;
 104 use middle::typeck::infer::{resolve_type, force_tvar};
 105 use middle::typeck::infer;
 106 use middle::typeck::rscope::RegionScope;
 107 use middle::typeck::{lookup_def_ccx};
 108 use middle::typeck::no_params;
 109 use middle::typeck::{require_same_types, vtable_map};
 110 use middle::typeck::{MethodCall, MethodMap};
 111 use middle::lang_items::TypeIdLangItem;
 112 use util::common::{block_query, indenter, loop_query};
 113 use util::ppaux;
 114 use util::ppaux::{UserString, Repr};
 115 use util::nodemap::{FnvHashMap, NodeMap};
 116
 117 use std::cell::{Cell, RefCell};
 118 use collections::HashMap;
 119 use std::mem::replace;
 120 use std::result;
 121 use std::slice;
 122 use std::vec::Vec;
 123 use syntax::abi;
 124 use syntax::ast::{Provided, Required};
 125 use syntax::ast;
 126 use syntax::ast_util::local_def;
 127 use syntax::ast_util;
 128 use syntax::attr;
 129 use syntax::codemap::Span;
 130 use syntax::codemap;
 131 use syntax::owned_slice::OwnedSlice;
 132 use syntax::parse::token;
 133 use syntax::print::pprust;
 134 use syntax::visit;
 135 use syntax::visit::Visitor;
 136 use syntax;
 137
 138 pub mod _match;
 139 pub mod vtable;
 140 pub mod writeback;
 141 pub mod regionmanip;
 142 pub mod regionck;
 143 pub mod demand;
 144 pub mod method;
 145
 146 /// Fields that are part of a `FnCtxt` which are inherited by
 147 /// closures defined within the function.  For example:
 148 ///
 149 ///     fn foo() {
 150 ///         bar(proc() { ... })
 151 ///     }
 152 ///
 153 /// Here, the function `foo()` and the closure passed to
 154 /// `bar()` will each have their own `FnCtxt`, but they will
 155 /// share the inherited fields.
 156 pub struct Inherited<'a> {
 157     infcx: infer::InferCtxt<'a>,
 158     locals: @RefCell<NodeMap<ty::t>>,
 159     param_env: ty::ParameterEnvironment,
 160
 161     // Temporary tables:
 162     node_types: RefCell<NodeMap<ty::t>>,
 163     node_type_substs: RefCell<NodeMap<ty::substs>>,
 164     adjustments: RefCell<NodeMap<@ty::AutoAdjustment>>,
 165     method_map: MethodMap,
 166     vtable_map: vtable_map,
 167     upvar_borrow_map: RefCell<ty::UpvarBorrowMap>,
 168 }
 169
 170 #[deriving(Clone)]
 171 pub enum FnKind {
 172     // A do-closure.
 173     DoBlock,
 174
 175     // A normal closure or fn item.
 176     Vanilla
 177 }
 178
 179 #[deriving(Clone)]
 180 pub struct PurityState {
 181     pub def: ast::NodeId,
 182     pub purity: ast::Purity,
 183     from_fn: bool
 184 }
 185
 186 impl PurityState {
 187     pub fn function(purity: ast::Purity, def: ast::NodeId) -> PurityState {
 188         PurityState { def: def, purity: purity, from_fn: true }
 189     }
 190
 191     pub fn recurse(&mut self, blk: &ast::Block) -> PurityState {
 192         match self.purity {
 193             // If this unsafe, then if the outer function was already marked as
 194             // unsafe we shouldn't attribute the unsafe'ness to the block. This
 195             // way the block can be warned about instead of ignoring this
 196             // extraneous block (functions are never warned about).
 197             ast::UnsafeFn if self.from_fn => *self,
 198
 199             purity => {
 200                 let (purity, def) = match blk.rules {
 201                     ast::UnsafeBlock(..) => (ast::UnsafeFn, blk.id),
 202                     ast::DefaultBlock => (purity, self.def),
 203                 };
 204                 PurityState{ def: def,
 205                              purity: purity,
 206                              from_fn: false }
 207             }
 208         }
 209     }
 210 }
 211
 212 /// Whether `check_binop` is part of an assignment or not.
 213 /// Used to know wether we allow user overloads and to print
 214 /// better messages on error.
 215 #[deriving(Eq)]
 216 enum IsBinopAssignment{
 217     SimpleBinop,
 218     BinopAssignment,
 219 }
 220
 221 #[deriving(Clone)]
 222 pub struct FnCtxt<'a> {
 223     // Number of errors that had been reported when we started
 224     // checking this function. On exit, if we find that *more* errors
 225     // have been reported, we will skip regionck and other work that
 226     // expects the types within the function to be consistent.
 227     err_count_on_creation: uint,
 228
 229     ret_ty: ty::t,
 230     ps: RefCell<PurityState>,
 231
 232     // Sometimes we generate region pointers where the precise region
 233     // to use is not known. For example, an expression like `&x.f`
 234     // where `x` is of type `@T`: in this case, we will be rooting
 235     // `x` onto the stack frame, and we could choose to root it until
 236     // the end of (almost) any enclosing block or expression.  We
 237     // want to pick the narrowest block that encompasses all uses.
 238     //
 239     // What we do in such cases is to generate a region variable with
 240     // `region_lb` as a lower bound.  The regionck pass then adds
 241     // other constriants based on how the variable is used and region
 242     // inference selects the ultimate value.  Finally, borrowck is
 243     // charged with guaranteeing that the value whose address was taken
 244     // can actually be made to live as long as it needs to live.
 245     region_lb: Cell<ast::NodeId>,
 246
 247     // Says whether we're inside a for loop, in a do block
 248     // or neither. Helps with error messages involving the
 249     // function return type.
 250     fn_kind: FnKind,
 251
 252     inh: &'a Inherited<'a>,
 253
 254     ccx: &'a CrateCtxt<'a>,
 255 }
 256
 257 impl<'a> Inherited<'a> {
 258     fn new(tcx: &'a ty::ctxt,
 259            param_env: ty::ParameterEnvironment)
 260            -> Inherited<'a> {
 261         Inherited {
 262             infcx: infer::new_infer_ctxt(tcx),
 263             locals: @RefCell::new(NodeMap::new()),
 264             param_env: param_env,
 265             node_types: RefCell::new(NodeMap::new()),
 266             node_type_substs: RefCell::new(NodeMap::new()),
 267             adjustments: RefCell::new(NodeMap::new()),
 268             method_map: @RefCell::new(FnvHashMap::new()),
 269             vtable_map: @RefCell::new(FnvHashMap::new()),
 270             upvar_borrow_map: RefCell::new(HashMap::new()),
 271         }
 272     }
 273 }
 274
 275 // Used by check_const and check_enum_variants
 276 fn blank_fn_ctxt<'a>(ccx: &'a CrateCtxt<'a>,
 277                      inh: &'a Inherited<'a>,
 278                      rty: ty::t,
 279                      region_bnd: ast::NodeId)
 280                      -> FnCtxt<'a> {
 281     FnCtxt {
 282         err_count_on_creation: ccx.tcx.sess.err_count(),
 283         ret_ty: rty,
 284         ps: RefCell::new(PurityState::function(ast::ImpureFn, 0)),
 285         region_lb: Cell::new(region_bnd),
 286         fn_kind: Vanilla,
 287         inh: inh,
 288         ccx: ccx
 289     }
 290 }
 291
 292 fn blank_inherited_fields<'a>(ccx: &'a CrateCtxt<'a>) -> Inherited<'a> {
 293     // It's kind of a kludge to manufacture a fake function context
 294     // and statement context, but we might as well do write the code only once
 295     let param_env = ty::ParameterEnvironment { free_substs: substs::empty(),
 296                                                self_param_bound: None,
 297                                                type_param_bounds: Vec::new() };
 298     Inherited::new(ccx.tcx, param_env)
 299 }
 300
 301 impl<'a> ExprTyProvider for FnCtxt<'a> {
 302     fn expr_ty(&self, ex: &ast::Expr) -> ty::t {
 303         self.expr_ty(ex)
 304     }
 305
 306     fn ty_ctxt<'a>(&'a self) -> &'a ty::ctxt {
 307         self.ccx.tcx
 308     }
 309 }
 310
 311 struct CheckItemTypesVisitor<'a> { ccx: &'a CrateCtxt<'a> }
 312
 313 impl<'a> Visitor<()> for CheckItemTypesVisitor<'a> {
 314     fn visit_item(&mut self, i: &ast::Item, _: ()) {
 315         check_item(self.ccx, i);
 316         visit::walk_item(self, i, ());
 317     }
 318 }
 319
 320 pub fn check_item_types(ccx: &CrateCtxt, krate: &ast::Crate) {
 321     let mut visit = CheckItemTypesVisitor { ccx: ccx };
 322     visit::walk_crate(&mut visit, krate, ());
 323 }
 324
 325 fn check_bare_fn(ccx: &CrateCtxt,
 326                  decl: &ast::FnDecl,
 327                  body: &ast::Block,
 328                  id: ast::NodeId,
 329                  fty: ty::t,
 330                  param_env: ty::ParameterEnvironment) {
 331     // Compute the fty from point of view of inside fn
 332     // (replace any type-scheme with a type)
 333     let fty = fty.subst(ccx.tcx, &param_env.free_substs);
 334
 335     match ty::get(fty).sty {
 336         ty::ty_bare_fn(ref fn_ty) => {
 337             let inh = Inherited::new(ccx.tcx, param_env);
 338             let fcx = check_fn(ccx, fn_ty.purity, &fn_ty.sig,
 339                                decl, id, body, Vanilla, &inh);
 340
 341             vtable::resolve_in_block(&fcx, body);
 342             regionck::regionck_fn(&fcx, body);
 343             writeback::resolve_type_vars_in_fn(&fcx, decl, body);
 344         }
 345         _ => ccx.tcx.sess.impossible_case(body.span,
 346                                  "check_bare_fn: function type expected")
 347     }
 348 }
 349
 350 struct GatherLocalsVisitor<'a> {
 351     fcx: &'a FnCtxt<'a>
 352 }
 353
 354 impl<'a> GatherLocalsVisitor<'a> {
 355     fn assign(&mut self, nid: ast::NodeId, ty_opt: Option<ty::t>) {
 356             match ty_opt {
 357                 None => {
 358                     // infer the variable's type
 359                     let var_id = self.fcx.infcx().next_ty_var_id();
 360                     let var_ty = ty::mk_var(self.fcx.tcx(), var_id);
 361                     self.fcx.inh.locals.borrow_mut().insert(nid, var_ty);
 362                 }
 363                 Some(typ) => {
 364                     // take type that the user specified
 365                     self.fcx.inh.locals.borrow_mut().insert(nid, typ);
 366                 }
 367             }
 368     }
 369 }
 370
 371 impl<'a> Visitor<()> for GatherLocalsVisitor<'a> {
 372         // Add explicitly-declared locals.
 373     fn visit_local(&mut self, local: &ast::Local, _: ()) {
 374             let o_ty = match local.ty.node {
 375               ast::TyInfer => None,
 376               _ => Some(self.fcx.to_ty(local.ty))
 377             };
 378             self.assign(local.id, o_ty);
 379             debug!("Local variable {} is assigned type {}",
 380                    self.fcx.pat_to_str(local.pat),
 381                    self.fcx.infcx().ty_to_str(
 382                        self.fcx.inh.locals.borrow().get_copy(&local.id)));
 383             visit::walk_local(self, local, ());
 384
 385     }
 386         // Add pattern bindings.
 387     fn visit_pat(&mut self, p: &ast::Pat, _: ()) {
 388             match p.node {
 389               ast::PatIdent(_, ref path, _)
 390                   if pat_util::pat_is_binding(self.fcx.ccx.tcx.def_map, p) => {
 391                 self.assign(p.id, None);
 392                 debug!("Pattern binding {} is assigned to {}",
 393                        token::get_ident(path.segments.get(0).identifier),
 394                        self.fcx.infcx().ty_to_str(
 395                            self.fcx.inh.locals.borrow().get_copy(&p.id)));
 396               }
 397               _ => {}
 398             }
 399             visit::walk_pat(self, p, ());
 400
 401     }
 402
 403     fn visit_block(&mut self, b: &ast::Block, _: ()) {
 404         // non-obvious: the `blk` variable maps to region lb, so
 405         // we have to keep this up-to-date.  This
 406         // is... unfortunate.  It'd be nice to not need this.
 407         self.fcx.with_region_lb(b.id, || visit::walk_block(self, b, ()));
 408     }
 409
 410     // Don't descend into fns and items
 411     fn visit_fn(&mut self, _: &visit::FnKind, _: &ast::FnDecl,
 412                 _: &ast::Block, _: Span, _: ast::NodeId, _: ()) { }
 413     fn visit_item(&mut self, _: &ast::Item, _: ()) { }
 414
 415 }
 416
 417 fn check_fn<'a>(ccx: &'a CrateCtxt<'a>,
 418                 purity: ast::Purity,
 419                 fn_sig: &ty::FnSig,
 420                 decl: &ast::FnDecl,
 421                 id: ast::NodeId,
 422                 body: &ast::Block,
 423                 fn_kind: FnKind,
 424                 inherited: &'a Inherited<'a>) -> FnCtxt<'a>
 425 {
 426     /*!
 427      * Helper used by check_bare_fn and check_expr_fn.  Does the
 428      * grungy work of checking a function body and returns the
 429      * function context used for that purpose, since in the case of a
 430      * fn item there is still a bit more to do.
 431      *
 432      * - ...
 433      * - inherited: other fields inherited from the enclosing fn (if any)
 434      */
 435
 436     let tcx = ccx.tcx;
 437     let err_count_on_creation = tcx.sess.err_count();
 438
 439     // First, we have to replace any bound regions in the fn type with free ones.
 440     // The free region references will be bound the node_id of the body block.
 441     let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(tcx, fn_sig, |br| {
 442         ty::ReFree(ty::FreeRegion {scope_id: body.id, bound_region: br})
 443     });
 444
 445     relate_free_regions(tcx, &fn_sig);
 446
 447     let arg_tys = fn_sig.inputs.as_slice();
 448     let ret_ty = fn_sig.output;
 449
 450     debug!("check_fn(arg_tys={:?}, ret_ty={:?})",
 451            arg_tys.iter().map(|&a| ppaux::ty_to_str(tcx, a)).collect::<Vec<~str>>(),
 452            ppaux::ty_to_str(tcx, ret_ty));
 453
 454     // Create the function context.  This is either derived from scratch or,
 455     // in the case of function expressions, based on the outer context.
 456     let fcx = FnCtxt {
 457         err_count_on_creation: err_count_on_creation,
 458         ret_ty: ret_ty,
 459         ps: RefCell::new(PurityState::function(purity, id)),
 460         region_lb: Cell::new(body.id),
 461         fn_kind: fn_kind,
 462         inh: inherited,
 463         ccx: ccx
 464     };
 465
 466     {
 467
 468         let mut visit = GatherLocalsVisitor { fcx: &fcx, };
 469         // Add formal parameters.
 470         for (arg_ty, input) in arg_tys.iter().zip(decl.inputs.iter()) {
 471             // Create type variables for each argument.
 472             pat_util::pat_bindings(tcx.def_map,
 473                                    input.pat,
 474                                    |_bm, pat_id, _sp, _path| {
 475                                        visit.assign(pat_id, None);
 476                                    });
 477
 478             // Check the pattern.
 479             let pcx = pat_ctxt {
 480                 fcx: &fcx,
 481                 map: pat_id_map(tcx.def_map, input.pat),
 482             };
 483             _match::check_pat(&pcx, input.pat, *arg_ty);
 484         }
 485
 486         visit.visit_block(body, ());
 487     }
 488
 489     check_block_with_expected(&fcx, body, Some(ret_ty));
 490
 491     // We unify the tail expr's type with the
 492     // function result type, if there is a tail expr.
 493     match body.expr {
 494         Some(tail_expr) => {
 495             // Special case: we print a special error if there appears
 496             // to be do-block/for-loop confusion
 497             demand::suptype_with_fn(&fcx, tail_expr.span, false,
 498                 fcx.ret_ty, fcx.expr_ty(tail_expr),
 499                 |sp, e, a, s| {
 500                     fcx.report_mismatched_return_types(sp, e, a, s);
 501                 });
 502         }
 503         None => {}
 504     }
 505
 506     for (input, arg) in decl.inputs.iter().zip(arg_tys.iter()) {
 507         fcx.write_ty(input.id, *arg);
 508     }
 509
 510     fcx
 511 }
 512
 513 pub fn check_struct(ccx: &CrateCtxt, id: ast::NodeId, span: Span) {
 514     let tcx = ccx.tcx;
 515
 516     // Check that the struct is representable
 517     check_representable(tcx, span, id, "struct");
 518
 519     // Check that the struct is instantiable
 520     check_instantiable(tcx, span, id);
 521
 522     if ty::lookup_simd(tcx, local_def(id)) {
 523         check_simd(tcx, span, id);
 524     }
 525 }
 526
 527 pub fn check_item(ccx: &CrateCtxt, it: &ast::Item) {
 528     debug!("check_item(it.id={}, it.ident={})",
 529            it.id,
 530            ty::item_path_str(ccx.tcx, local_def(it.id)));
 531     let _indenter = indenter();
 532
 533     match it.node {
 534       ast::ItemStatic(_, _, e) => check_const(ccx, it.span, e, it.id),
 535       ast::ItemEnum(ref enum_definition, _) => {
 536         check_enum_variants(ccx,
 537                             it.span,
 538                             enum_definition.variants.as_slice(),
 539                             it.id);
 540       }
 541       ast::ItemFn(decl, _, _, _, body) => {
 542         let fn_tpt = ty::lookup_item_type(ccx.tcx, ast_util::local_def(it.id));
 543
 544         let param_env = ty::construct_parameter_environment(
 545                 ccx.tcx,
 546                 None,
 547                 fn_tpt.generics.type_param_defs(),
 548                 [],
 549                 [],
 550                 fn_tpt.generics.region_param_defs.as_slice(),
 551                 body.id);
 552
 553         check_bare_fn(ccx, decl, body, it.id, fn_tpt.ty, param_env);
 554       }
 555       ast::ItemImpl(_, ref opt_trait_ref, _, ref ms) => {
 556         debug!("ItemImpl {} with id {}", token::get_ident(it.ident), it.id);
 557
 558         let impl_tpt = ty::lookup_item_type(ccx.tcx, ast_util::local_def(it.id));
 559         for m in ms.iter() {
 560             check_method_body(ccx, &impl_tpt.generics, None, *m);
 561         }
 562
 563         match *opt_trait_ref {
 564             Some(ref ast_trait_ref) => {
 565                 let impl_trait_ref =
 566                     ty::node_id_to_trait_ref(ccx.tcx, ast_trait_ref.ref_id);
 567                 check_impl_methods_against_trait(ccx,
 568                                              it.span,
 569                                              &impl_tpt.generics,
 570                                              ast_trait_ref,
 571                                              impl_trait_ref,
 572                                              ms.as_slice());
 573                 vtable::resolve_impl(ccx.tcx, it, &impl_tpt.generics, impl_trait_ref);
 574             }
 575             None => { }
 576         }
 577
 578       }
 579       ast::ItemTrait(_, _, ref trait_methods) => {
 580         let trait_def = ty::lookup_trait_def(ccx.tcx, local_def(it.id));
 581         for trait_method in (*trait_methods).iter() {
 582             match *trait_method {
 583                 Required(..) => {
 584                     // Nothing to do, since required methods don't have
 585                     // bodies to check.
 586                 }
 587                 Provided(m) => {
 588                     check_method_body(ccx, &trait_def.generics,
 589                                       Some(trait_def.trait_ref), m);
 590                 }
 591             }
 592         }
 593       }
 594       ast::ItemStruct(..) => {
 595         check_struct(ccx, it.id, it.span);
 596       }
 597       ast::ItemTy(ref t, ref generics) => {
 598         let tpt_ty = ty::node_id_to_type(ccx.tcx, it.id);
 599         check_bounds_are_used(ccx, t.span, &generics.ty_params, tpt_ty);
 600       }
 601       ast::ItemForeignMod(ref m) => {
 602         if m.abi == abi::RustIntrinsic {
 603             for item in m.items.iter() {
 604                 check_intrinsic_type(ccx, *item);
 605             }
 606         } else {
 607             for item in m.items.iter() {
 608                 let tpt = ty::lookup_item_type(ccx.tcx, local_def(item.id));
 609                 if tpt.generics.has_type_params() {
 610                     ccx.tcx.sess.span_err(item.span, "foreign items may not have type parameters");
 611                 }
 612
 613                 match item.node {
 614                     ast::ForeignItemFn(ref fn_decl, _) => {
 615                         if fn_decl.variadic && m.abi != abi::C {
 616                             ccx.tcx.sess.span_err(
 617                                 item.span, "variadic function must have C calling convention");
 618                         }
 619                     }
 620                     _ => {}
 621                 }
 622             }
 623         }
 624       }
 625       _ => {/* nothing to do */ }
 626     }
 627 }
 628
 629 fn check_method_body(ccx: &CrateCtxt,
 630                      item_generics: &ty::Generics,
 631                      self_bound: Option<@ty::TraitRef>,
 632                      method: &ast::Method) {
 633     /*!
 634      * Type checks a method body.
 635      *
 636      * # Parameters
 637      * - `item_generics`: generics defined on the impl/trait that contains
 638      *   the method
 639      * - `self_bound`: bound for the `Self` type parameter, if any
 640      * - `method`: the method definition
 641      */
 642
 643     debug!("check_method_body(item_generics={}, \
 644             self_bound={}, \
 645             method.id={})",
 646             item_generics.repr(ccx.tcx),
 647             self_bound.repr(ccx.tcx),
 648             method.id);
 649     let method_def_id = local_def(method.id);
 650     let method_ty = ty::method(ccx.tcx, method_def_id);
 651     let method_generics = &method_ty.generics;
 652
 653     let param_env =
 654         ty::construct_parameter_environment(
 655             ccx.tcx,
 656             self_bound,
 657             item_generics.type_param_defs(),
 658             method_generics.type_param_defs(),
 659             item_generics.region_param_defs(),
 660             method_generics.region_param_defs(),
 661             method.body.id);
 662
 663     let fty = ty::node_id_to_type(ccx.tcx, method.id);
 664
 665     check_bare_fn(ccx, method.decl, method.body, method.id, fty, param_env);
 666 }
 667
 668 fn check_impl_methods_against_trait(ccx: &CrateCtxt,
 669                                     impl_span: Span,
 670                                     impl_generics: &ty::Generics,
 671                                     ast_trait_ref: &ast::TraitRef,
 672                                     impl_trait_ref: &ty::TraitRef,
 673                                     impl_methods: &[@ast::Method]) {
 674     // Locate trait methods
 675     let tcx = ccx.tcx;
 676     let trait_methods = ty::trait_methods(tcx, impl_trait_ref.def_id);
 677
 678     // Check existing impl methods to see if they are both present in trait
 679     // and compatible with trait signature
 680     for impl_method in impl_methods.iter() {
 681         let impl_method_def_id = local_def(impl_method.id);
 682         let impl_method_ty = ty::method(ccx.tcx, impl_method_def_id);
 683
 684         // If this is an impl of a trait method, find the corresponding
 685         // method definition in the trait.
 686         let opt_trait_method_ty =
 687             trait_methods.iter().
 688             find(|tm| tm.ident.name == impl_method_ty.ident.name);
 689         match opt_trait_method_ty {
 690             Some(trait_method_ty) => {
 691                 compare_impl_method(ccx.tcx,
 692                                     impl_generics,
 693                                     impl_method_ty,
 694                                     impl_method.span,
 695                                     impl_method.body.id,
 696                                     *trait_method_ty,
 697                                     &impl_trait_ref.substs);
 698             }
 699             None => {
 700                 tcx.sess.span_err(
 701                     impl_method.span,
 702                     format!("method `{}` is not a member of trait `{}`",
 703                             token::get_ident(impl_method_ty.ident),
 704                             pprust::path_to_str(&ast_trait_ref.path)));
 705             }
 706         }
 707     }
 708
 709     // Check for missing methods from trait
 710     let provided_methods = ty::provided_trait_methods(tcx,
 711                                                       impl_trait_ref.def_id);
 712     let mut missing_methods = Vec::new();
 713     for trait_method in trait_methods.iter() {
 714         let is_implemented =
 715             impl_methods.iter().any(
 716                 |m| m.ident.name == trait_method.ident.name);
 717         let is_provided =
 718             provided_methods.iter().any(
 719                 |m| m.ident.name == trait_method.ident.name);
 720         if !is_implemented && !is_provided {
 721             missing_methods.push(
 722                 format!("`{}`", token::get_ident(trait_method.ident)));
 723         }
 724     }
 725
 726     if !missing_methods.is_empty() {
 727         tcx.sess.span_err(
 728             impl_span,
 729             format!("not all trait methods implemented, missing: {}",
 730                     missing_methods.connect(", ")));
 731     }
 732 }
 733
 734 /**
 735  * Checks that a method from an impl/class conforms to the signature of
 736  * the same method as declared in the trait.
 737  *
 738  * # Parameters
 739  *
 740  * - impl_generics: the generics declared on the impl itself (not the method!)
 741  * - impl_m: type of the method we are checking
 742  * - impl_m_span: span to use for reporting errors
 743  * - impl_m_body_id: id of the method body
 744  * - trait_m: the method in the trait
 745  * - trait_substs: the substitutions used on the type of the trait
 746  */
 747 fn compare_impl_method(tcx: &ty::ctxt,
 748                        impl_generics: &ty::Generics,
 749                        impl_m: @ty::Method,
 750                        impl_m_span: Span,
 751                        impl_m_body_id: ast::NodeId,
 752                        trait_m: &ty::Method,
 753                        trait_substs: &ty::substs) {
 754     debug!("compare_impl_method()");
 755     let infcx = infer::new_infer_ctxt(tcx);
 756
 757     let impl_tps = impl_generics.type_param_defs().len();
 758
 759     // Try to give more informative error messages about self typing
 760     // mismatches.  Note that any mismatch will also be detected
 761     // below, where we construct a canonical function type that
 762     // includes the self parameter as a normal parameter.  It's just
 763     // that the error messages you get out of this code are a bit more
 764     // inscrutable, particularly for cases where one method has no
 765     // self.
 766     match (&trait_m.explicit_self, &impl_m.explicit_self) {
 767         (&ast::SelfStatic, &ast::SelfStatic) => {}
 768         (&ast::SelfStatic, _) => {
 769             tcx.sess.span_err(
 770                 impl_m_span,
 771                 format!("method `{}` has a `{}` declaration in the impl, \
 772                         but not in the trait",
 773                         token::get_ident(trait_m.ident),
 774                         pprust::explicit_self_to_str(impl_m.explicit_self)));
 775             return;
 776         }
 777         (_, &ast::SelfStatic) => {
 778             tcx.sess.span_err(
 779                 impl_m_span,
 780                 format!("method `{}` has a `{}` declaration in the trait, \
 781                         but not in the impl",
 782                         token::get_ident(trait_m.ident),
 783                         pprust::explicit_self_to_str(trait_m.explicit_self)));
 784             return;
 785         }
 786         _ => {
 787             // Let the type checker catch other errors below
 788         }
 789     }
 790
 791     let num_impl_m_type_params = impl_m.generics.type_param_defs().len();
 792     let num_trait_m_type_params = trait_m.generics.type_param_defs().len();
 793     if num_impl_m_type_params != num_trait_m_type_params {
 794         tcx.sess.span_err(
 795             impl_m_span,
 796             format!("method `{method}` has {nimpl, plural, =1{# type parameter} \
 797                                                         other{# type parameters}}, \
 798                      but its trait declaration has {ntrait, plural, =1{# type parameter} \
 799                                                                  other{# type parameters}}",
 800                     method = token::get_ident(trait_m.ident),
 801                     nimpl = num_impl_m_type_params,
 802                     ntrait = num_trait_m_type_params));
 803         return;
 804     }
 805
 806     if impl_m.fty.sig.inputs.len() != trait_m.fty.sig.inputs.len() {
 807         tcx.sess.span_err(
 808             impl_m_span,
 809             format!("method `{method}` has {nimpl, plural, =1{# parameter} \
 810                                                         other{# parameters}} \
 811                      but the declaration in trait `{trait}` has {ntrait}",
 812                  method = token::get_ident(trait_m.ident),
 813                  nimpl = impl_m.fty.sig.inputs.len(),
 814                  trait = ty::item_path_str(tcx, trait_m.def_id),
 815                  ntrait = trait_m.fty.sig.inputs.len()));
 816         return;
 817     }
 818
 819     let it = trait_m.generics.type_param_defs().iter()
 820         .zip(impl_m.generics.type_param_defs().iter());
 821
 822     for (i, (trait_param_def, impl_param_def)) in it.enumerate() {
 823         // Check that the impl does not require any builtin-bounds
 824         // that the trait does not guarantee:
 825         let extra_bounds =
 826             impl_param_def.bounds.builtin_bounds -
 827             trait_param_def.bounds.builtin_bounds;
 828         if !extra_bounds.is_empty() {
 829            tcx.sess.span_err(
 830                impl_m_span,
 831                format!("in method `{}`, \
 832                        type parameter {} requires `{}`, \
 833                        which is not required by \
 834                        the corresponding type parameter \
 835                        in the trait declaration",
 836                        token::get_ident(trait_m.ident),
 837                        i,
 838                        extra_bounds.user_string(tcx)));
 839            return;
 840         }
 841
 842         // FIXME(#2687)---we should be checking that the bounds of the
 843         // trait imply the bounds of the subtype, but it appears we
 844         // are...not checking this.
 845         if impl_param_def.bounds.trait_bounds.len() !=
 846             trait_param_def.bounds.trait_bounds.len()
 847         {
 848             tcx.sess.span_err(
 849                 impl_m_span,
 850                 format!("in method `{method}`, \
 851                         type parameter {typaram} has \
 852                         {nimpl, plural, =1{# trait bound} other{# trait bounds}}, \
 853                         but the corresponding type parameter in \
 854                         the trait declaration has \
 855                         {ntrait, plural, =1{# trait bound} other{# trait bounds}}",
 856                         method = token::get_ident(trait_m.ident),
 857                         typaram = i,
 858                         nimpl = impl_param_def.bounds.trait_bounds.len(),
 859                         ntrait = trait_param_def.bounds.trait_bounds.len()));
 860             return;
 861         }
 862     }
 863
 864     // Create a substitution that maps the type parameters on the impl
 865     // to themselves and which replace any references to bound regions
 866     // in the self type with free regions.  So, for example, if the
 867     // impl type is "&'a str", then this would replace the self
 868     // type with a free region `self`.
 869     let dummy_impl_tps: Vec<ty::t> =
 870         impl_generics.type_param_defs().iter().enumerate().
 871         map(|(i,t)| ty::mk_param(tcx, i, t.def_id)).
 872         collect();
 873     let dummy_method_tps: Vec<ty::t> =
 874         impl_m.generics.type_param_defs().iter().enumerate().
 875         map(|(i,t)| ty::mk_param(tcx, i + impl_tps, t.def_id)).
 876         collect();
 877     let dummy_impl_regions: OwnedSlice<ty::Region> =
 878         impl_generics.region_param_defs().iter().
 879         map(|l| ty::ReFree(ty::FreeRegion {
 880                 scope_id: impl_m_body_id,
 881                 bound_region: ty::BrNamed(l.def_id, l.name)})).
 882         collect();
 883     let dummy_substs = ty::substs {
 884         tps: dummy_impl_tps.append(dummy_method_tps.as_slice()),
 885         regions: ty::NonerasedRegions(dummy_impl_regions),
 886         self_ty: None };
 887
 888     // Create a bare fn type for trait/impl
 889     // It'd be nice to refactor so as to provide the bare fn types instead.
 890     let trait_fty = ty::mk_bare_fn(tcx, trait_m.fty.clone());
 891     let impl_fty = ty::mk_bare_fn(tcx, impl_m.fty.clone());
 892
 893     // Perform substitutions so that the trait/impl methods are expressed
 894     // in terms of the same set of type/region parameters:
 895     // - replace trait type parameters with those from `trait_substs`,
 896     //   except with any reference to bound self replaced with `dummy_self_r`
 897     // - replace method parameters on the trait with fresh, dummy parameters
 898     //   that correspond to the parameters we will find on the impl
 899     // - replace self region with a fresh, dummy region
 900     let impl_fty = {
 901         debug!("impl_fty (pre-subst): {}", ppaux::ty_to_str(tcx, impl_fty));
 902         impl_fty.subst(tcx, &dummy_substs)
 903     };
 904     debug!("impl_fty (post-subst): {}", ppaux::ty_to_str(tcx, impl_fty));
 905     let trait_fty = {
 906         let substs { regions: trait_regions,
 907                      tps: trait_tps,
 908                      self_ty: self_ty } = trait_substs.subst(tcx, &dummy_substs);
 909         let substs = substs {
 910             regions: trait_regions,
 911             tps: trait_tps.append(dummy_method_tps.as_slice()),
 912             self_ty: self_ty,
 913         };
 914         debug!("trait_fty (pre-subst): {} substs={}",
 915                trait_fty.repr(tcx), substs.repr(tcx));
 916         trait_fty.subst(tcx, &substs)
 917     };
 918     debug!("trait_fty (post-subst): {}", trait_fty.repr(tcx));
 919
 920     match infer::mk_subty(&infcx, false, infer::MethodCompatCheck(impl_m_span),
 921                           impl_fty, trait_fty) {
 922         result::Ok(()) => {}
 923         result::Err(ref terr) => {
 924             tcx.sess.span_err(
 925                 impl_m_span,
 926                 format!("method `{}` has an incompatible type: {}",
 927                         token::get_ident(trait_m.ident),
 928                         ty::type_err_to_str(tcx, terr)));
 929             ty::note_and_explain_type_err(tcx, terr);
 930         }
 931     }
 932 }
 933
 934 impl<'a> AstConv for FnCtxt<'a> {
 935     fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.ccx.tcx }
 936
 937     fn get_item_ty(&self, id: ast::DefId) -> ty::ty_param_bounds_and_ty {
 938         ty::lookup_item_type(self.tcx(), id)
 939     }
 940
 941     fn get_trait_def(&self, id: ast::DefId) -> @ty::TraitDef {
 942         ty::lookup_trait_def(self.tcx(), id)
 943     }
 944
 945     fn ty_infer(&self, _span: Span) -> ty::t {
 946         self.infcx().next_ty_var()
 947     }
 948 }
 949
 950 impl<'a> FnCtxt<'a> {
 951     pub fn infcx<'b>(&'b self) -> &'b infer::InferCtxt<'a> {
 952         &self.inh.infcx
 953     }
 954
 955     pub fn err_count_since_creation(&self) -> uint {
 956         self.ccx.tcx.sess.err_count() - self.err_count_on_creation
 957     }
 958
 959     pub fn vtable_context<'a>(&'a self) -> VtableContext<'a> {
 960         VtableContext {
 961             infcx: self.infcx(),
 962             param_env: &self.inh.param_env
 963         }
 964     }
 965 }
 966
 967 impl<'a> RegionScope for infer::InferCtxt<'a> {
 968     fn anon_regions(&self, span: Span, count: uint)
 969                     -> Result<Vec<ty::Region> , ()> {
 970         Ok(Vec::from_fn(count, |_| {
 971             self.next_region_var(infer::MiscVariable(span))
 972         }))
 973     }
 974 }
 975
 976 impl<'a> FnCtxt<'a> {
 977     pub fn tag(&self) -> ~str {
 978         format!("{}", self as *FnCtxt)
 979     }
 980
 981     pub fn local_ty(&self, span: Span, nid: ast::NodeId) -> ty::t {
 982         match self.inh.locals.borrow().find(&nid) {
 983             Some(&t) => t,
 984             None => {
 985                 self.tcx().sess.span_bug(
 986                     span,
 987                     format!("no type for local variable {:?}", nid));
 988             }
 989         }
 990     }
 991
 992     #[inline]
 993     pub fn write_ty(&self, node_id: ast::NodeId, ty: ty::t) {
 994         debug!("write_ty({}, {}) in fcx {}",
 995                node_id, ppaux::ty_to_str(self.tcx(), ty), self.tag());
 996         self.inh.node_types.borrow_mut().insert(node_id, ty);
 997     }
 998
 999     pub fn write_substs(&self, node_id: ast::NodeId, substs: ty::substs) {
1000         if !ty::substs_is_noop(&substs) {
1001             debug!("write_substs({}, {}) in fcx {}",
1002                    node_id,
1003                    ty::substs_to_str(self.tcx(), &substs),
1004                    self.tag());
1005
1006             self.inh.node_type_substs.borrow_mut().insert(node_id, substs);
1007         }
1008     }
1009
1010     pub fn write_ty_substs(&self,
1011                            node_id: ast::NodeId,
1012                            ty: ty::t,
1013                            substs: ty::substs) {
1014         let ty = ty::subst(self.tcx(), &substs, ty);
1015         self.write_ty(node_id, ty);
1016         self.write_substs(node_id, substs);
1017     }
1018
1019     pub fn write_autoderef_adjustment(&self,
1020                                       node_id: ast::NodeId,
1021                                       derefs: uint) {
1022         if derefs == 0 { return; }
1023         self.write_adjustment(
1024             node_id,
1025             @ty::AutoDerefRef(ty::AutoDerefRef {
1026                 autoderefs: derefs,
1027                 autoref: None })
1028         );
1029     }
1030
1031     pub fn write_adjustment(&self,
1032                             node_id: ast::NodeId,
1033                             adj: @ty::AutoAdjustment) {
1034         debug!("write_adjustment(node_id={:?}, adj={:?})", node_id, adj);
1035         self.inh.adjustments.borrow_mut().insert(node_id, adj);
1036     }
1037
1038     pub fn write_nil(&self, node_id: ast::NodeId) {
1039         self.write_ty(node_id, ty::mk_nil());
1040     }
1041     pub fn write_bot(&self, node_id: ast::NodeId) {
1042         self.write_ty(node_id, ty::mk_bot());
1043     }
1044     pub fn write_error(&self, node_id: ast::NodeId) {
1045         self.write_ty(node_id, ty::mk_err());
1046     }
1047
1048     pub fn to_ty(&self, ast_t: &ast::Ty) -> ty::t {
1049         ast_ty_to_ty(self, self.infcx(), ast_t)
1050     }
1051
1052     pub fn pat_to_str(&self, pat: &ast::Pat) -> ~str {
1053         pat.repr(self.tcx())
1054     }
1055
1056     pub fn expr_ty(&self, ex: &ast::Expr) -> ty::t {
1057         match self.inh.node_types.borrow().find(&ex.id) {
1058             Some(&t) => t,
1059             None => {
1060                 self.tcx().sess.bug(format!("no type for expr in fcx {}",
1061                                             self.tag()));
1062             }
1063         }
1064     }
1065
1066     pub fn node_ty(&self, id: ast::NodeId) -> ty::t {
1067         match self.inh.node_types.borrow().find(&id) {
1068             Some(&t) => t,
1069             None => {
1070                 self.tcx().sess.bug(
1071                     format!("no type for node {}: {} in fcx {}",
1072                             id, self.tcx().map.node_to_str(id),
1073                             self.tag()));
1074             }
1075         }
1076     }
1077
1078     pub fn method_ty_substs(&self, id: ast::NodeId) -> ty::substs {
1079         match self.inh.method_map.borrow().find(&MethodCall::expr(id)) {
1080             Some(method) => method.substs.clone(),
1081             None => {
1082                 self.tcx().sess.bug(
1083                     format!("no method entry for node {}: {} in fcx {}",
1084                             id, self.tcx().map.node_to_str(id),
1085                             self.tag()));
1086             }
1087         }
1088     }
1089
1090     pub fn opt_node_ty_substs(&self,
1091                               id: ast::NodeId,
1092                               f: |&ty::substs| -> bool)
1093                               -> bool {
1094         match self.inh.node_type_substs.borrow().find(&id) {
1095             Some(s) => f(s),
1096             None => true
1097         }
1098     }
1099
1100     pub fn mk_subty(&self,
1101                     a_is_expected: bool,
1102                     origin: infer::TypeOrigin,
1103                     sub: ty::t,
1104                     sup: ty::t)
1105                     -> Result<(), ty::type_err> {
1106         infer::mk_subty(self.infcx(), a_is_expected, origin, sub, sup)
1107     }
1108
1109     pub fn can_mk_subty(&self, sub: ty::t, sup: ty::t)
1110                         -> Result<(), ty::type_err> {
1111         infer::can_mk_subty(self.infcx(), sub, sup)
1112     }
1113
1114     pub fn mk_assignty(&self,
1115                        expr: &ast::Expr,
1116                        sub: ty::t,
1117                        sup: ty::t)
1118                        -> Result<(), ty::type_err> {
1119         match infer::mk_coercety(self.infcx(),
1120                                  false,
1121                                  infer::ExprAssignable(expr.span),
1122                                  sub,
1123                                  sup) {
1124             Ok(None) => result::Ok(()),
1125             Err(ref e) => result::Err((*e)),
1126             Ok(Some(adjustment)) => {
1127                 self.write_adjustment(expr.id, adjustment);
1128                 Ok(())
1129             }
1130         }
1131     }
1132
1133     pub fn mk_eqty(&self,
1134                    a_is_expected: bool,
1135                    origin: infer::TypeOrigin,
1136                    sub: ty::t,
1137                    sup: ty::t)
1138                    -> Result<(), ty::type_err> {
1139         infer::mk_eqty(self.infcx(), a_is_expected, origin, sub, sup)
1140     }
1141
1142     pub fn mk_subr(&self,
1143                    a_is_expected: bool,
1144                    origin: infer::SubregionOrigin,
1145                    sub: ty::Region,
1146                    sup: ty::Region) {
1147         infer::mk_subr(self.infcx(), a_is_expected, origin, sub, sup)
1148     }
1149
1150     pub fn with_region_lb<R>(&self, lb: ast::NodeId, f: || -> R) -> R {
1151         let old_region_lb = self.region_lb.get();
1152         self.region_lb.set(lb);
1153         let v = f();
1154         self.region_lb.set(old_region_lb);
1155         v
1156     }
1157
1158     pub fn type_error_message(&self,
1159                               sp: Span,
1160                               mk_msg: |~str| -> ~str,
1161                               actual_ty: ty::t,
1162                               err: Option<&ty::type_err>) {
1163         self.infcx().type_error_message(sp, mk_msg, actual_ty, err);
1164     }
1165
1166     pub fn report_mismatched_return_types(&self,
1167                                           sp: Span,
1168                                           e: ty::t,
1169                                           a: ty::t,
1170                                           err: &ty::type_err) {
1171         // Derived error
1172         if ty::type_is_error(e) || ty::type_is_error(a) {
1173             return;
1174         }
1175         self.infcx().report_mismatched_types(sp, e, a, err)
1176     }
1177
1178     pub fn report_mismatched_types(&self,
1179                                    sp: Span,
1180                                    e: ty::t,
1181                                    a: ty::t,
1182                                    err: &ty::type_err) {
1183         self.infcx().report_mismatched_types(sp, e, a, err)
1184     }
1185 }
1186
1187 pub enum LvaluePreference {
1188     PreferMutLvalue,
1189     NoPreference
1190 }
1191
1192 pub fn autoderef<T>(fcx: &FnCtxt, sp: Span, base_ty: ty::t,
1193                     expr_id: Option<ast::NodeId>,
1194                     mut lvalue_pref: LvaluePreference,
1195                     should_stop: |ty::t, uint| -> Option<T>)
1196                     -> (ty::t, uint, Option<T>) {
1197     /*!
1198      * Executes an autoderef loop for the type `t`. At each step, invokes
1199      * `should_stop` to decide whether to terminate the loop. Returns
1200      * the final type and number of derefs that it performed.
1201      *
1202      * Note: this method does not modify the adjustments table. The caller is
1203      * responsible for inserting an AutoAdjustment record into the `fcx`
1204      * using one of the suitable methods.
1205      */
1206
1207     let mut t = base_ty;
1208     for autoderefs in range(0, fcx.tcx().sess.recursion_limit.get()) {
1209         let resolved_t = structurally_resolved_type(fcx, sp, t);
1210
1211         match should_stop(resolved_t, autoderefs) {
1212             Some(x) => return (resolved_t, autoderefs, Some(x)),
1213             None => {}
1214         }
1215
1216         // Otherwise, deref if type is derefable:
1217         let mt = match ty::deref(resolved_t, false) {
1218             Some(mt) => Some(mt),
1219             None => {
1220                 let method_call =
1221                     expr_id.map(|id| MethodCall::autoderef(id, autoderefs as u32));
1222                 try_overloaded_deref(fcx, sp, method_call, None, resolved_t, lvalue_pref)
1223             }
1224         };
1225         match mt {
1226             Some(mt) => {
1227                 t = mt.ty;
1228                 if mt.mutbl == ast::MutImmutable {
1229                     lvalue_pref = NoPreference;
1230                 }
1231             }
1232             None => return (resolved_t, autoderefs, None)
1233         }
1234     }
1235
1236     // We've reached the recursion limit, error gracefully.
1237     fcx.tcx().sess.span_err(sp,
1238         format!("reached the recursion limit while auto-dereferencing {}",
1239                 base_ty.repr(fcx.tcx())));
1240     (ty::mk_err(), 0, None)
1241 }
1242
1243 fn try_overloaded_deref(fcx: &FnCtxt,
1244                         span: Span,
1245                         method_call: Option<MethodCall>,
1246                         base_expr: Option<&ast::Expr>,
1247                         base_ty: ty::t,
1248                         lvalue_pref: LvaluePreference)
1249                         -> Option<ty::mt> {
1250     // Try DerefMut first, if preferred.
1251     let method = match (lvalue_pref, fcx.tcx().lang_items.deref_mut_trait()) {
1252         (PreferMutLvalue, Some(trait_did)) => {
1253             method::lookup_in_trait(fcx, span, base_expr.map(|x| &*x),
1254                                     token::intern("deref_mut"), trait_did,
1255                                     base_ty, [], DontAutoderefReceiver)
1256         }
1257         _ => None
1258     };
1259
1260     // Otherwise, fall back to Deref.
1261     let method = match (method, fcx.tcx().lang_items.deref_trait()) {
1262         (None, Some(trait_did)) => {
1263             method::lookup_in_trait(fcx, span, base_expr.map(|x| &*x),
1264                                     token::intern("deref"), trait_did,
1265                                     base_ty, [], DontAutoderefReceiver)
1266         }
1267         (method, _) => method
1268     };
1269
1270     match method {
1271         Some(method) => {
1272             let ref_ty = ty::ty_fn_ret(method.ty);
1273             match method_call {
1274                 Some(method_call) => {
1275                     fcx.inh.method_map.borrow_mut().insert(method_call, method);
1276                 }
1277                 None => {}
1278             }
1279             ty::deref(ref_ty, true)
1280         }
1281         None => None
1282     }
1283 }
1284
1285 // AST fragment checking
1286 pub fn check_lit(fcx: &FnCtxt, lit: &ast::Lit) -> ty::t {
1287     let tcx = fcx.ccx.tcx;
1288
1289     match lit.node {
1290         ast::LitStr(..) => ty::mk_str(tcx, ty::vstore_slice(ty::ReStatic)),
1291         ast::LitBinary(..) => {
1292             ty::mk_vec(tcx, ty::mt{ ty: ty::mk_u8(), mutbl: ast::MutImmutable },
1293                        ty::vstore_slice(ty::ReStatic))
1294         }
1295         ast::LitChar(_) => ty::mk_char(),
1296         ast::LitInt(_, t) => ty::mk_mach_int(t),
1297         ast::LitUint(_, t) => ty::mk_mach_uint(t),
1298         ast::LitIntUnsuffixed(_) => {
1299             // An unsuffixed integer literal could have any integral type,
1300             // so we create an integral type variable for it.
1301             ty::mk_int_var(tcx, fcx.infcx().next_int_var_id())
1302         }
1303         ast::LitFloat(_, t) => ty::mk_mach_float(t),
1304         ast::LitFloatUnsuffixed(_) => {
1305             // An unsuffixed floating point literal could have any floating point
1306             // type, so we create a floating point type variable for it.
1307             ty::mk_float_var(tcx, fcx.infcx().next_float_var_id())
1308         }
1309         ast::LitNil => ty::mk_nil(),
1310         ast::LitBool(_) => ty::mk_bool()
1311     }
1312 }
1313
1314 pub fn valid_range_bounds(ccx: &CrateCtxt,
1315                           from: &ast::Expr,
1316                           to: &ast::Expr)
1317                        -> Option<bool> {
1318     match const_eval::compare_lit_exprs(ccx.tcx, from, to) {
1319         Some(val) => Some(val <= 0),
1320         None => None
1321     }
1322 }
1323
1324 pub fn check_expr_has_type(
1325     fcx: &FnCtxt, expr: &ast::Expr,
1326     expected: ty::t) {
1327     check_expr_with_unifier(fcx, expr, Some(expected), NoPreference, || {
1328         demand::suptype(fcx, expr.span, expected, fcx.expr_ty(expr));
1329     });
1330 }
1331
1332 fn check_expr_coercable_to_type(fcx: &FnCtxt, expr: &ast::Expr, expected: ty::t) {
1333     check_expr_with_unifier(fcx, expr, Some(expected), NoPreference, || {
1334         demand::coerce(fcx, expr.span, expected, expr)
1335     });
1336 }
1337
1338 fn check_expr_with_hint(fcx: &FnCtxt, expr: &ast::Expr, expected: ty::t) {
1339     check_expr_with_unifier(fcx, expr, Some(expected), NoPreference, || ())
1340 }
1341
1342 fn check_expr_with_opt_hint(fcx: &FnCtxt, expr: &ast::Expr,
1343                             expected: Option<ty::t>)  {
1344     check_expr_with_unifier(fcx, expr, expected, NoPreference, || ())
1345 }
1346
1347 fn check_expr_with_opt_hint_and_lvalue_pref(fcx: &FnCtxt,
1348                                             expr: &ast::Expr,
1349                                             expected: Option<ty::t>,
1350                                             lvalue_pref: LvaluePreference) {
1351     check_expr_with_unifier(fcx, expr, expected, lvalue_pref, || ())
1352 }
1353
1354 fn check_expr(fcx: &FnCtxt, expr: &ast::Expr)  {
1355     check_expr_with_unifier(fcx, expr, None, NoPreference, || ())
1356 }
1357
1358 fn check_expr_with_lvalue_pref(fcx: &FnCtxt, expr: &ast::Expr,
1359                                lvalue_pref: LvaluePreference)  {
1360     check_expr_with_unifier(fcx, expr, None, lvalue_pref, || ())
1361 }
1362
1363
1364 // determine the `self` type, using fresh variables for all variables
1365 // declared on the impl declaration e.g., `impl<A,B> for ~[(A,B)]`
1366 // would return ($0, $1) where $0 and $1 are freshly instantiated type
1367 // variables.
1368 pub fn impl_self_ty(vcx: &VtableContext,
1369                     span: Span, // (potential) receiver for this impl
1370                     did: ast::DefId)
1371                  -> ty_param_substs_and_ty {
1372     let tcx = vcx.tcx();
1373
1374     let ity = ty::lookup_item_type(tcx, did);
1375     let (n_tps, rps, raw_ty) =
1376         (ity.generics.type_param_defs().len(),
1377          ity.generics.region_param_defs(),
1378          ity.ty);
1379
1380     let rps = vcx.infcx.region_vars_for_defs(span, rps);
1381     let tps = vcx.infcx.next_ty_vars(n_tps);
1382
1383     let substs = substs {
1384         regions: ty::NonerasedRegions(rps),
1385         self_ty: None,
1386         tps: tps,
1387     };
1388     let substd_ty = ty::subst(tcx, &substs, raw_ty);
1389
1390     ty_param_substs_and_ty { substs: substs, ty: substd_ty }
1391 }
1392
1393 // Only for fields! Returns <none> for methods>
1394 // Indifferent to privacy flags
1395 pub fn lookup_field_ty(tcx: &ty::ctxt,
1396                        class_id: ast::DefId,
1397                        items: &[ty::field_ty],
1398                        fieldname: ast::Name,
1399                        substs: &ty::substs) -> Option<ty::t> {
1400
1401     let o_field = items.iter().find(|f| f.name == fieldname);
1402     o_field.map(|f| ty::lookup_field_type(tcx, class_id, f.id, substs))
1403 }
1404
1405 // Controls whether the arguments are automatically referenced. This is useful
1406 // for overloaded binary and unary operators.
1407 pub enum DerefArgs {
1408     DontDerefArgs,
1409     DoDerefArgs
1410 }
1411
1412 // Given the provenance of a static method, returns the generics of the static
1413 // method's container.
1414 fn generics_of_static_method_container(type_context: &ty::ctxt,
1415                                        provenance: ast::MethodProvenance)
1416                                        -> ty::Generics {
1417     match provenance {
1418         ast::FromTrait(trait_def_id) => {
1419             ty::lookup_trait_def(type_context, trait_def_id).generics.clone()
1420         }
1421         ast::FromImpl(impl_def_id) => {
1422             ty::lookup_item_type(type_context, impl_def_id).generics.clone()
1423         }
1424     }
1425 }
1426
1427 // Verifies that type parameters supplied in paths are in the right
1428 // locations.
1429 fn check_type_parameter_positions_in_path(function_context: &FnCtxt,
1430                                           path: &ast::Path,
1431                                           def: ast::Def) {
1432     // We only care about checking the case in which the path has two or
1433     // more segments.
1434     if path.segments.len() < 2 {
1435         return
1436     }
1437
1438     // Verify that no lifetimes or type parameters are present anywhere
1439     // except the final two elements of the path.
1440     for i in range(0, path.segments.len() - 2) {
1441         for lifetime in path.segments.get(i).lifetimes.iter() {
1442             function_context.tcx()
1443                 .sess
1444                 .span_err(lifetime.span,
1445                           "lifetime parameters may not \
1446                           appear here");
1447             break;
1448         }
1449
1450         for typ in path.segments.get(i).types.iter() {
1451             function_context.tcx()
1452                             .sess
1453                             .span_err(typ.span,
1454                                       "type parameters may not appear here");
1455             break;
1456         }
1457     }
1458
1459     // If there are no parameters at all, there is nothing more to do; the
1460     // rest of typechecking will (attempt to) infer everything.
1461     if path.segments
1462            .iter()
1463            .all(|s| s.lifetimes.is_empty() && s.types.is_empty()) {
1464         return
1465     }
1466
1467     match def {
1468         // If this is a static method of a trait or implementation, then
1469         // ensure that the segment of the path which names the trait or
1470         // implementation (the penultimate segment) is annotated with the
1471         // right number of type parameters.
1472         ast::DefStaticMethod(_, provenance, _) => {
1473             let generics =
1474                 generics_of_static_method_container(function_context.ccx.tcx,
1475                                                     provenance);
1476             let name = match provenance {
1477                 ast::FromTrait(_) => "trait",
1478                 ast::FromImpl(_) => "impl",
1479             };
1480
1481             let trait_segment = &path.segments.get(path.segments.len() - 2);
1482
1483             // Make sure lifetime parameterization agrees with the trait or
1484             // implementation type.
1485             let trait_region_parameter_count = generics.region_param_defs().len();
1486             let supplied_region_parameter_count = trait_segment.lifetimes.len();
1487             if trait_region_parameter_count != supplied_region_parameter_count
1488                 && supplied_region_parameter_count != 0 {
1489                 function_context.tcx()
1490                     .sess
1491                     .span_err(path.span,
1492                               format!("expected {nexpected, plural, =1{# lifetime parameter} \
1493                                                                  other{# lifetime parameters}}, \
1494                                        found {nsupplied, plural, =1{# lifetime parameter} \
1495                                                               other{# lifetime parameters}}",
1496                                       nexpected = trait_region_parameter_count,
1497                                       nsupplied = supplied_region_parameter_count));
1498             }
1499
1500             // Make sure the number of type parameters supplied on the trait
1501             // or implementation segment equals the number of type parameters
1502             // on the trait or implementation definition.
1503             let formal_ty_param_count = generics.type_param_defs().len();
1504             let required_ty_param_count = generics.type_param_defs().iter()
1505                                                   .take_while(|x| x.default.is_none())
1506                                                   .len();
1507             let supplied_ty_param_count = trait_segment.types.len();
1508             if supplied_ty_param_count < required_ty_param_count {
1509                 let msg = if required_ty_param_count < generics.type_param_defs().len() {
1510                     format!("the {trait_or_impl} referenced by this path needs at least \
1511                              {nexpected, plural, =1{# type parameter} \
1512                                               other{# type parameters}}, \
1513                              but {nsupplied, plural, =1{# type parameter} \
1514                                                   other{# type parameters}} were supplied",
1515                             trait_or_impl = name,
1516                             nexpected = required_ty_param_count,
1517                             nsupplied = supplied_ty_param_count)
1518                 } else {
1519                     format!("the {trait_or_impl} referenced by this path needs \
1520                              {nexpected, plural, =1{# type parameter} \
1521                                               other{# type parameters}}, \
1522                              but {nsupplied, plural, =1{# type parameter} \
1523                                                   other{# type parameters}} were supplied",
1524                             trait_or_impl = name,
1525                             nexpected = required_ty_param_count,
1526                             nsupplied = supplied_ty_param_count)
1527                 };
1528                 function_context.tcx().sess.span_err(path.span, msg)
1529             } else if supplied_ty_param_count > formal_ty_param_count {
1530                 let msg = if required_ty_param_count < generics.type_param_defs().len() {
1531                     format!("the {trait_or_impl} referenced by this path needs at most \
1532                              {nexpected, plural, =1{# type parameter} \
1533                                               other{# type parameters}}, \
1534                              but {nsupplied, plural, =1{# type parameter} \
1535                                                   other{# type parameters}} were supplied",
1536                             trait_or_impl = name,
1537                             nexpected = formal_ty_param_count,
1538                             nsupplied = supplied_ty_param_count)
1539                 } else {
1540                     format!("the {trait_or_impl} referenced by this path needs \
1541                              {nexpected, plural, =1{# type parameter} \
1542                                               other{# type parameters}}, \
1543                              but {nsupplied, plural, =1{# type parameter} \
1544                                                   other{# type parameters}} were supplied",
1545                             trait_or_impl = name,
1546                             nexpected = formal_ty_param_count,
1547                             nsupplied = supplied_ty_param_count)
1548                 };
1549                 function_context.tcx().sess.span_err(path.span, msg)
1550             }
1551         }
1552         _ => {
1553             // Verify that no lifetimes or type parameters are present on
1554             // the penultimate segment of the path.
1555             let segment = &path.segments.get(path.segments.len() - 2);
1556             for lifetime in segment.lifetimes.iter() {
1557                 function_context.tcx()
1558                     .sess
1559                     .span_err(lifetime.span,
1560                               "lifetime parameters may not
1561                               appear here");
1562                 break;
1563             }
1564             for typ in segment.types.iter() {
1565                 function_context.tcx()
1566                                 .sess
1567                                 .span_err(typ.span,
1568                                           "type parameters may not appear \
1569                                            here");
1570                 break;
1571             }
1572         }
1573     }
1574 }
1575
1576 /// Invariant:
1577 /// If an expression has any sub-expressions that result in a type error,
1578 /// inspecting that expression's type with `ty::type_is_error` will return
1579 /// true. Likewise, if an expression is known to diverge, inspecting its
1580 /// type with `ty::type_is_bot` will return true (n.b.: since Rust is
1581 /// strict, _|_ can appear in the type of an expression that does not,
1582 /// itself, diverge: for example, fn() -> _|_.)
1583 /// Note that inspecting a type's structure *directly* may expose the fact
1584 /// that there are actually multiple representations for both `ty_err` and
1585 /// `ty_bot`, so avoid that when err and bot need to be handled differently.
1586 fn check_expr_with_unifier(fcx: &FnCtxt,
1587                            expr: &ast::Expr,
1588                            expected: Option<ty::t>,
1589                            lvalue_pref: LvaluePreference,
1590                            unifier: ||) {
1591     debug!(">> typechecking");
1592
1593     fn check_method_argument_types(
1594         fcx: &FnCtxt,
1595         sp: Span,
1596         method_fn_ty: ty::t,
1597         callee_expr: &ast::Expr,
1598         args: &[@ast::Expr],
1599         deref_args: DerefArgs) -> ty::t {
1600         // HACK(eddyb) ignore provided self (it has special typeck rules).
1601         let args = args.slice_from(1);
1602         if ty::type_is_error(method_fn_ty) {
1603             let err_inputs = err_args(args.len());
1604             check_argument_types(fcx, sp, err_inputs.as_slice(), callee_expr,
1605                                  args, deref_args, false);
1606             method_fn_ty
1607         } else {
1608             match ty::get(method_fn_ty).sty {
1609                 ty::ty_bare_fn(ref fty) => {
1610                     // HACK(eddyb) ignore self in the definition (see above).
1611                     check_argument_types(fcx, sp, fty.sig.inputs.slice_from(1),
1612                                          callee_expr, args, deref_args,
1613                                          fty.sig.variadic);
1614                     fty.sig.output
1615                 }
1616                 _ => {
1617                     fcx.tcx().sess.span_bug(
1618                         sp,
1619                         format!("method without bare fn type"));
1620                 }
1621             }
1622         }
1623     }
1624
1625     fn check_argument_types(fcx: &FnCtxt,
1626                             sp: Span,
1627                             fn_inputs: &[ty::t],
1628                             callee_expr: &ast::Expr,
1629                             args: &[@ast::Expr],
1630                             deref_args: DerefArgs,
1631                             variadic: bool) {
1632         /*!
1633          *
1634          * Generic function that factors out common logic from
1635          * function calls, method calls and overloaded operators.
1636          */
1637
1638         let tcx = fcx.ccx.tcx;
1639
1640         // Grab the argument types, supplying fresh type variables
1641         // if the wrong number of arguments were supplied
1642         let supplied_arg_count = args.len();
1643         let expected_arg_count = fn_inputs.len();
1644         let formal_tys = if expected_arg_count == supplied_arg_count {
1645             fn_inputs.iter().map(|a| *a).collect()
1646         } else if variadic {
1647             if supplied_arg_count >= expected_arg_count {
1648                 fn_inputs.iter().map(|a| *a).collect()
1649             } else {
1650                 let msg = format!(
1651                     "this function takes at least {nexpected, plural, =1{# parameter} \
1652                                                                    other{# parameters}} \
1653                      but {nsupplied, plural, =1{# parameter was} \
1654                                           other{# parameters were}} supplied",
1655                      nexpected = expected_arg_count,
1656                      nsupplied = supplied_arg_count);
1657
1658                 tcx.sess.span_err(sp, msg);
1659
1660                 err_args(supplied_arg_count)
1661             }
1662         } else {
1663             let msg = format!(
1664                 "this function takes {nexpected, plural, =1{# parameter} \
1665                                                       other{# parameters}} \
1666                  but {nsupplied, plural, =1{# parameter was} \
1667                                       other{# parameters were}} supplied",
1668                  nexpected = expected_arg_count,
1669                  nsupplied = supplied_arg_count);
1670
1671             tcx.sess.span_err(sp, msg);
1672
1673             err_args(supplied_arg_count)
1674         };
1675
1676         debug!("check_argument_types: formal_tys={:?}",
1677                formal_tys.iter().map(|t| fcx.infcx().ty_to_str(*t)).collect::<Vec<~str>>());
1678
1679         // Check the arguments.
1680         // We do this in a pretty awful way: first we typecheck any arguments
1681         // that are not anonymous functions, then we typecheck the anonymous
1682         // functions. This is so that we have more information about the types
1683         // of arguments when we typecheck the functions. This isn't really the
1684         // right way to do this.
1685         let xs = [false, true];
1686         for check_blocks in xs.iter() {
1687             let check_blocks = *check_blocks;
1688             debug!("check_blocks={}", check_blocks);
1689
1690             // More awful hacks: before we check the blocks, try to do
1691             // an "opportunistic" vtable resolution of any trait
1692             // bounds on the call.
1693             if check_blocks {
1694                 vtable::early_resolve_expr(callee_expr, fcx, true);
1695             }
1696
1697             // For variadic functions, we don't have a declared type for all of
1698             // the arguments hence we only do our usual type checking with
1699             // the arguments who's types we do know.
1700             let t = if variadic {
1701                 expected_arg_count
1702             } else {
1703                 supplied_arg_count
1704             };
1705             for (i, arg) in args.iter().take(t).enumerate() {
1706                 let is_block = match arg.node {
1707                     ast::ExprFnBlock(..) |
1708                     ast::ExprProc(..) => true,
1709                     _ => false
1710                 };
1711
1712                 if is_block == check_blocks {
1713                     debug!("checking the argument");
1714                     let mut formal_ty = *formal_tys.get(i);
1715
1716                     match deref_args {
1717                         DoDerefArgs => {
1718                             match ty::get(formal_ty).sty {
1719                                 ty::ty_rptr(_, mt) => formal_ty = mt.ty,
1720                                 ty::ty_err => (),
1721                                 _ => {
1722                                     // So we hit this case when one implements the
1723                                     // operator traits but leaves an argument as
1724                                     // just T instead of &T. We'll catch it in the
1725                                     // mismatch impl/trait method phase no need to
1726                                     // ICE here.
1727                                     // See: #11450
1728                                     formal_ty = ty::mk_err();
1729                                 }
1730                             }
1731                         }
1732                         DontDerefArgs => {}
1733                     }
1734
1735                     check_expr_coercable_to_type(fcx, *arg, formal_ty);
1736
1737                 }
1738             }
1739         }
1740
1741         // We also need to make sure we at least write the ty of the other
1742         // arguments which we skipped above.
1743         if variadic {
1744             for arg in args.iter().skip(expected_arg_count) {
1745                 check_expr(fcx, *arg);
1746
1747                 // There are a few types which get autopromoted when passed via varargs
1748                 // in C but we just error out instead and require explicit casts.
1749                 let arg_ty = structurally_resolved_type(fcx, arg.span, fcx.expr_ty(*arg));
1750                 match ty::get(arg_ty).sty {
1751                     ty::ty_float(ast::TyF32) => {
1752                         fcx.type_error_message(arg.span,
1753                                 |t| format!("can't pass an {} to variadic function, \
1754                                              cast to c_double", t), arg_ty, None);
1755                     }
1756                     ty::ty_int(ast::TyI8) | ty::ty_int(ast::TyI16) | ty::ty_bool => {
1757                         fcx.type_error_message(arg.span,
1758                                 |t| format!("can't pass {} to variadic function, cast to c_int",
1759                                             t), arg_ty, None);
1760                     }
1761                     ty::ty_uint(ast::TyU8) | ty::ty_uint(ast::TyU16) => {
1762                         fcx.type_error_message(arg.span,
1763                                 |t| format!("can't pass {} to variadic function, cast to c_uint",
1764                                             t), arg_ty, None);
1765                     }
1766                     _ => {}
1767                 }
1768             }
1769         }
1770     }
1771
1772     fn err_args(len: uint) -> Vec<ty::t> {
1773         Vec::from_fn(len, |_| ty::mk_err())
1774     }
1775
1776     fn write_call(fcx: &FnCtxt, call_expr: &ast::Expr, output: ty::t) {
1777         fcx.write_ty(call_expr.id, output);
1778     }
1779
1780     // A generic function for doing all of the checking for call expressions
1781     fn check_call(fcx: &FnCtxt,
1782                   call_expr: &ast::Expr,
1783                   f: &ast::Expr,
1784                   args: &[@ast::Expr]) {
1785         // Index expressions need to be handled separately, to inform them
1786         // that they appear in call position.
1787         check_expr(fcx, f);
1788
1789         // Store the type of `f` as the type of the callee
1790         let fn_ty = fcx.expr_ty(f);
1791
1792         // Extract the function signature from `in_fty`.
1793         let fn_sty = structure_of(fcx, f.span, fn_ty);
1794
1795         // This is the "default" function signature, used in case of error.
1796         // In that case, we check each argument against "error" in order to
1797         // set up all the node type bindings.
1798         let error_fn_sig = FnSig {
1799             binder_id: ast::CRATE_NODE_ID,
1800             inputs: err_args(args.len()),
1801             output: ty::mk_err(),
1802             variadic: false
1803         };
1804
1805         let fn_sig = match *fn_sty {
1806             ty::ty_bare_fn(ty::BareFnTy {sig: ref sig, ..}) |
1807             ty::ty_closure(~ty::ClosureTy {sig: ref sig, ..}) => sig,
1808             _ => {
1809                 fcx.type_error_message(call_expr.span, |actual| {
1810                     format!("expected function but \
1811                           found `{}`", actual) }, fn_ty, None);
1812                 &error_fn_sig
1813             }
1814         };
1815
1816         // Replace any bound regions that appear in the function
1817         // signature with region variables
1818         let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(fcx.tcx(), fn_sig, |br| {
1819             fcx.infcx().next_region_var(infer::LateBoundRegion(call_expr.span, br))
1820         });
1821
1822         // Call the generic checker.
1823         check_argument_types(fcx, call_expr.span, fn_sig.inputs.as_slice(), f,
1824                              args, DontDerefArgs, fn_sig.variadic);
1825
1826         write_call(fcx, call_expr, fn_sig.output);
1827     }
1828
1829     // Checks a method call.
1830     fn check_method_call(fcx: &FnCtxt,
1831                          expr: &ast::Expr,
1832                          method_name: ast::Ident,
1833                          args: &[@ast::Expr],
1834                          tps: &[ast::P<ast::Ty>]) {
1835         let rcvr = args[0];
1836         // We can't know if we need &mut self before we look up the method,
1837         // so treat the receiver as mutable just in case - only explicit
1838         // overloaded dereferences care about the distinction.
1839         check_expr_with_lvalue_pref(fcx, rcvr, PreferMutLvalue);
1840
1841         // no need to check for bot/err -- callee does that
1842         let expr_t = structurally_resolved_type(fcx,
1843                                                 expr.span,
1844                                                 fcx.expr_ty(rcvr));
1845
1846         let tps = tps.iter().map(|&ast_ty| fcx.to_ty(ast_ty)).collect::<Vec<_>>();
1847         let fn_ty = match method::lookup(fcx, expr, rcvr,
1848                                          method_name.name,
1849                                          expr_t, tps.as_slice(),
1850                                          DontDerefArgs,
1851                                          CheckTraitsAndInherentMethods,
1852                                          AutoderefReceiver) {
1853             Some(method) => {
1854                 let method_ty = method.ty;
1855                 let method_call = MethodCall::expr(expr.id);
1856                 fcx.inh.method_map.borrow_mut().insert(method_call, method);
1857                 method_ty
1858             }
1859             None => {
1860                 debug!("(checking method call) failing expr is {}", expr.id);
1861
1862                 fcx.type_error_message(expr.span,
1863                   |actual| {
1864                       format!("type `{}` does not implement any method in scope \
1865                             named `{}`",
1866                            actual, token::get_ident(method_name))
1867                   },
1868                   expr_t,
1869                   None);
1870
1871                 // Add error type for the result
1872                 fcx.write_error(expr.id);
1873                 ty::mk_err()
1874             }
1875         };
1876
1877         // Call the generic checker.
1878         let ret_ty = check_method_argument_types(fcx, expr.span,
1879                                                  fn_ty, expr, args,
1880                                                  DontDerefArgs);
1881
1882         write_call(fcx, expr, ret_ty);
1883     }
1884
1885     // A generic function for checking the then and else in an if
1886     // or if-check
1887     fn check_then_else(fcx: &FnCtxt,
1888                        cond_expr: &ast::Expr,
1889                        then_blk: &ast::Block,
1890                        opt_else_expr: Option<@ast::Expr>,
1891                        id: ast::NodeId,
1892                        sp: Span,
1893                        expected: Option<ty::t>) {
1894         check_expr_has_type(fcx, cond_expr, ty::mk_bool());
1895
1896         let branches_ty = match opt_else_expr {
1897             Some(else_expr) => {
1898                 check_block_with_expected(fcx, then_blk, expected);
1899                 let then_ty = fcx.node_ty(then_blk.id);
1900                 check_expr_with_opt_hint(fcx, else_expr, expected);
1901                 let else_ty = fcx.expr_ty(else_expr);
1902                 infer::common_supertype(fcx.infcx(),
1903                                         infer::IfExpression(sp),
1904                                         true,
1905                                         then_ty,
1906                                         else_ty)
1907             }
1908             None => {
1909                 check_block_no_value(fcx, then_blk);
1910                 ty::mk_nil()
1911             }
1912         };
1913
1914         let cond_ty = fcx.expr_ty(cond_expr);
1915         let if_ty = if ty::type_is_error(cond_ty) {
1916             ty::mk_err()
1917         } else if ty::type_is_bot(cond_ty) {
1918             ty::mk_bot()
1919         } else {
1920             branches_ty
1921         };
1922
1923         fcx.write_ty(id, if_ty);
1924     }
1925
1926     fn lookup_op_method(fcx: &FnCtxt,
1927                         op_ex: &ast::Expr,
1928                         self_t: ty::t,
1929                         opname: ast::Name,
1930                         trait_did: Option<ast::DefId>,
1931                         args: &[@ast::Expr],
1932                         autoderef_receiver: AutoderefReceiverFlag,
1933                         unbound_method: ||) -> ty::t {
1934         let method = match trait_did {
1935             Some(trait_did) => {
1936                 method::lookup_in_trait(fcx, op_ex.span, Some(&*args[0]), opname,
1937                                         trait_did, self_t, [], autoderef_receiver)
1938             }
1939             None => None
1940         };
1941         match method {
1942             Some(method) => {
1943                 let method_ty = method.ty;
1944                 // HACK(eddyb) Fully qualified path to work around a resolve bug.
1945                 let method_call = ::middle::typeck::MethodCall::expr(op_ex.id);
1946                 fcx.inh.method_map.borrow_mut().insert(method_call, method);
1947                 check_method_argument_types(fcx, op_ex.span,
1948                                             method_ty, op_ex,
1949                                             args, DoDerefArgs)
1950             }
1951             None => {
1952                 unbound_method();
1953                 // Check the args anyway
1954                 // so we get all the error messages
1955                 let expected_ty = ty::mk_err();
1956                 check_method_argument_types(fcx, op_ex.span,
1957                                             expected_ty, op_ex,
1958                                             args, DoDerefArgs);
1959                 ty::mk_err()
1960             }
1961         }
1962     }
1963
1964     // could be either an expr_binop or an expr_assign_binop
1965     fn check_binop(fcx: &FnCtxt,
1966                    expr: &ast::Expr,
1967                    op: ast::BinOp,
1968                    lhs: @ast::Expr,
1969                    rhs: @ast::Expr,
1970                    is_binop_assignment: IsBinopAssignment) {
1971         let tcx = fcx.ccx.tcx;
1972
1973         let lvalue_pref = match is_binop_assignment {
1974             BinopAssignment => PreferMutLvalue,
1975             SimpleBinop => NoPreference
1976         };
1977         check_expr_with_lvalue_pref(fcx, lhs, lvalue_pref);
1978
1979         // Callee does bot / err checking
1980         let lhs_t = structurally_resolved_type(fcx, lhs.span,
1981                                                fcx.expr_ty(lhs));
1982
1983         if ty::type_is_integral(lhs_t) && ast_util::is_shift_binop(op) {
1984             // Shift is a special case: rhs can be any integral type
1985             check_expr(fcx, rhs);
1986             let rhs_t = fcx.expr_ty(rhs);
1987             require_integral(fcx, rhs.span, rhs_t);
1988             fcx.write_ty(expr.id, lhs_t);
1989             return;
1990         }
1991
1992         if ty::is_binopable(tcx, lhs_t, op) {
1993             let tvar = fcx.infcx().next_ty_var();
1994             demand::suptype(fcx, expr.span, tvar, lhs_t);
1995             check_expr_has_type(fcx, rhs, tvar);
1996
1997             let result_t = match op {
1998                 ast::BiEq | ast::BiNe | ast::BiLt | ast::BiLe | ast::BiGe |
1999                 ast::BiGt => ty::mk_bool(),
2000                 _ => lhs_t
2001             };
2002
2003             fcx.write_ty(expr.id, result_t);
2004             return;
2005         }
2006
2007         if op == ast::BiOr || op == ast::BiAnd {
2008             // This is an error; one of the operands must have the wrong
2009             // type
2010             fcx.write_error(expr.id);
2011             fcx.write_error(rhs.id);
2012             fcx.type_error_message(expr.span, |actual| {
2013                 format!("binary operation `{}` cannot be applied \
2014                       to type `{}`",
2015                      ast_util::binop_to_str(op), actual)},
2016                                    lhs_t, None)
2017
2018         }
2019
2020         // Check for overloaded operators if not an assignment.
2021         let result_t = if is_binop_assignment == SimpleBinop {
2022             check_user_binop(fcx, expr, lhs, lhs_t, op, rhs)
2023         } else {
2024             fcx.type_error_message(expr.span,
2025                                    |actual| {
2026                                         format!("binary assignment operation \
2027                                                 `{}=` cannot be applied to type `{}`",
2028                                                 ast_util::binop_to_str(op),
2029                                                 actual)
2030                                    },
2031                                    lhs_t,
2032                                    None);
2033             check_expr(fcx, rhs);
2034             ty::mk_err()
2035         };
2036
2037         fcx.write_ty(expr.id, result_t);
2038         if ty::type_is_error(result_t) {
2039             fcx.write_ty(rhs.id, result_t);
2040         }
2041     }
2042
2043     fn check_user_binop(fcx: &FnCtxt,
2044                         ex: &ast::Expr,
2045                         lhs_expr: @ast::Expr,
2046                         lhs_resolved_t: ty::t,
2047                         op: ast::BinOp,
2048                         rhs: @ast::Expr) -> ty::t {
2049         let tcx = fcx.ccx.tcx;
2050         let lang = tcx.lang_items;
2051         let (name, trait_did) = match op {
2052             ast::BiAdd => ("add", lang.add_trait()),
2053             ast::BiSub => ("sub", lang.sub_trait()),
2054             ast::BiMul => ("mul", lang.mul_trait()),
2055             ast::BiDiv => ("div", lang.div_trait()),
2056             ast::BiRem => ("rem", lang.rem_trait()),
2057             ast::BiBitXor => ("bitxor", lang.bitxor_trait()),
2058             ast::BiBitAnd => ("bitand", lang.bitand_trait()),
2059             ast::BiBitOr => ("bitor", lang.bitor_trait()),
2060             ast::BiShl => ("shl", lang.shl_trait()),
2061             ast::BiShr => ("shr", lang.shr_trait()),
2062             ast::BiLt => ("lt", lang.ord_trait()),
2063             ast::BiLe => ("le", lang.ord_trait()),
2064             ast::BiGe => ("ge", lang.ord_trait()),
2065             ast::BiGt => ("gt", lang.ord_trait()),
2066             ast::BiEq => ("eq", lang.eq_trait()),
2067             ast::BiNe => ("ne", lang.eq_trait()),
2068             ast::BiAnd | ast::BiOr => {
2069                 check_expr(fcx, rhs);
2070                 return ty::mk_err();
2071             }
2072         };
2073         lookup_op_method(fcx, ex, lhs_resolved_t, token::intern(name),
2074                          trait_did, [lhs_expr, rhs], DontAutoderefReceiver, || {
2075             fcx.type_error_message(ex.span, |actual| {
2076                 format!("binary operation `{}` cannot be applied to type `{}`",
2077                     ast_util::binop_to_str(op), actual)
2078             }, lhs_resolved_t, None)
2079         })
2080     }
2081
2082     fn check_user_unop(fcx: &FnCtxt,
2083                        op_str: &str,
2084                        mname: &str,
2085                        trait_did: Option<ast::DefId>,
2086                        ex: &ast::Expr,
2087                        rhs_expr: @ast::Expr,
2088                        rhs_t: ty::t) -> ty::t {
2089        lookup_op_method(fcx, ex, rhs_t, token::intern(mname),
2090                         trait_did, [rhs_expr], DontAutoderefReceiver, || {
2091             fcx.type_error_message(ex.span, |actual| {
2092                 format!("cannot apply unary operator `{}` to type `{}`", op_str, actual)
2093             }, rhs_t, None);
2094         })
2095     }
2096
2097     // Resolves `expected` by a single level if it is a variable and passes it
2098     // through the `unpack` function.  It there is no expected type or
2099     // resolution is not possible (e.g., no constraints yet present), just
2100     // returns `none`.
2101     fn unpack_expected<O>(
2102                        fcx: &FnCtxt,
2103                        expected: Option<ty::t>,
2104                        unpack: |&ty::sty| -> Option<O>)
2105                        -> Option<O> {
2106         match expected {
2107             Some(t) => {
2108                 match resolve_type(fcx.infcx(), t, force_tvar) {
2109                     Ok(t) => unpack(&ty::get(t).sty),
2110                     _ => None
2111                 }
2112             }
2113             _ => None
2114         }
2115     }
2116
2117     fn check_expr_fn(fcx: &FnCtxt,
2118                      expr: &ast::Expr,
2119                      ast_sigil_opt: Option<ast::Sigil>,
2120                      decl: &ast::FnDecl,
2121                      body: ast::P<ast::Block>,
2122                      fn_kind: FnKind,
2123                      expected: Option<ty::t>) {
2124         let tcx = fcx.ccx.tcx;
2125
2126         // Find the expected input/output types (if any). Substitute
2127         // fresh bound regions for any bound regions we find in the
2128         // expected types so as to avoid capture.
2129         //
2130         // Also try to pick up inferred purity and sigil, defaulting
2131         // to impure and block. Note that we only will use those for
2132         // block syntax lambdas; that is, lambdas without explicit
2133         // sigils.
2134         let expected_sty = unpack_expected(fcx,
2135                                            expected,
2136                                            |x| Some((*x).clone()));
2137         let error_happened = false;
2138         let (expected_sig,
2139              expected_purity,
2140              expected_sigil,
2141              expected_onceness,
2142              expected_bounds) = {
2143             match expected_sty {
2144                 Some(ty::ty_closure(ref cenv)) => {
2145                     let (_, sig) =
2146                         replace_late_bound_regions_in_fn_sig(
2147                             tcx, &cenv.sig,
2148                             |_| fcx.inh.infcx.fresh_bound_region(expr.id));
2149                     (Some(sig), cenv.purity, cenv.sigil,
2150                      cenv.onceness, cenv.bounds)
2151                 }
2152                 _ => {
2153                     // Not an error! Means we're inferring the closure type
2154                     let mut sigil = ast::BorrowedSigil;
2155                     let mut onceness = ast::Many;
2156                     let mut bounds = ty::EmptyBuiltinBounds();
2157                     match expr.node {
2158                         ast::ExprProc(..) => {
2159                             sigil = ast::OwnedSigil;
2160                             onceness = ast::Once;
2161                             bounds.add(ty::BoundSend);
2162                         }
2163                         _ => ()
2164                     }
2165                     (None, ast::ImpureFn, sigil,
2166                      onceness, bounds)
2167                 }
2168             }
2169         };
2170
2171         // If the proto is specified, use that, otherwise select a
2172         // proto based on inference.
2173         let (sigil, purity) = match ast_sigil_opt {
2174             Some(p) => (p, ast::ImpureFn),
2175             None => (expected_sigil, expected_purity)
2176         };
2177
2178         // construct the function type
2179         let fn_ty = astconv::ty_of_closure(fcx,
2180                                            fcx.infcx(),
2181                                            expr.id,
2182                                            sigil,
2183                                            purity,
2184                                            expected_onceness,
2185                                            expected_bounds,
2186                                            &None,
2187                                            decl,
2188                                            expected_sig,
2189                                            expr.span);
2190
2191         let fty_sig;
2192         let fty = if error_happened {
2193             fty_sig = FnSig {
2194                 binder_id: ast::CRATE_NODE_ID,
2195                 inputs: fn_ty.sig.inputs.iter().map(|_| ty::mk_err()).collect(),
2196                 output: ty::mk_err(),
2197                 variadic: false
2198             };
2199             ty::mk_err()
2200         } else {
2201             let fn_ty_copy = fn_ty.clone();
2202             fty_sig = fn_ty.sig.clone();
2203             ty::mk_closure(tcx, fn_ty_copy)
2204         };
2205
2206         debug!("check_expr_fn_with_unifier fty={}",
2207                fcx.infcx().ty_to_str(fty));
2208
2209         fcx.write_ty(expr.id, fty);
2210
2211         let (inherited_purity, id) =
2212             ty::determine_inherited_purity((fcx.ps.borrow().purity,
2213                                             fcx.ps.borrow().def),
2214                                            (purity, expr.id),
2215                                            sigil);
2216
2217         check_fn(fcx.ccx, inherited_purity, &fty_sig,
2218                  decl, id, body, fn_kind, fcx.inh);
2219     }
2220
2221
2222     // Check field access expressions
2223     fn check_field(fcx: &FnCtxt,
2224                    expr: &ast::Expr,
2225                    lvalue_pref: LvaluePreference,
2226                    base: &ast::Expr,
2227                    field: ast::Name,
2228                    tys: &[ast::P<ast::Ty>]) {
2229         let tcx = fcx.ccx.tcx;
2230         check_expr_with_lvalue_pref(fcx, base, lvalue_pref);
2231         let expr_t = structurally_resolved_type(fcx, expr.span,
2232                                                 fcx.expr_ty(base));
2233         // FIXME(eddyb) #12808 Integrate privacy into this auto-deref loop.
2234         let (_, autoderefs, field_ty) =
2235             autoderef(fcx, expr.span, expr_t, Some(base.id), lvalue_pref, |base_t, _| {
2236                 match ty::get(base_t).sty {
2237                     ty::ty_struct(base_id, ref substs) => {
2238                         debug!("struct named {}", ppaux::ty_to_str(tcx, base_t));
2239                         let fields = ty::lookup_struct_fields(tcx, base_id);
2240                         lookup_field_ty(tcx, base_id, fields.as_slice(), field, &(*substs))
2241                     }
2242                     _ => None
2243                 }
2244             });
2245         match field_ty {
2246             Some(field_ty) => {
2247                 fcx.write_ty(expr.id, field_ty);
2248                 fcx.write_autoderef_adjustment(base.id, autoderefs);
2249                 return;
2250             }
2251             None => {}
2252         }
2253
2254         let tps: Vec<ty::t> = tys.iter().map(|&ty| fcx.to_ty(ty)).collect();
2255         match method::lookup(fcx,
2256                              expr,
2257                              base,
2258                              field,
2259                              expr_t,
2260                              tps.as_slice(),
2261                              DontDerefArgs,
2262                              CheckTraitsAndInherentMethods,
2263                              AutoderefReceiver) {
2264             Some(_) => {
2265                 fcx.type_error_message(
2266                     expr.span,
2267                     |actual| {
2268                         format!("attempted to take value of method `{}` on type `{}`",
2269                                 token::get_name(field), actual)
2270                     },
2271                     expr_t, None);
2272
2273                 tcx.sess.span_note(expr.span,
2274                     "maybe a missing `()` to call it? If not, try an anonymous function.");
2275             }
2276
2277             None => {
2278                 fcx.type_error_message(
2279                     expr.span,
2280                     |actual| {
2281                         format!("attempted access of field `{}` on type `{}`, \
2282                                  but no field with that name was found",
2283                                 token::get_name(field), actual)
2284                     },
2285                     expr_t, None);
2286             }
2287         }
2288
2289         fcx.write_error(expr.id);
2290     }
2291
2292     fn check_struct_or_variant_fields(fcx: &FnCtxt,
2293                                       struct_ty: ty::t,
2294                                       span: Span,
2295                                       class_id: ast::DefId,
2296                                       node_id: ast::NodeId,
2297                                       substitutions: ty::substs,
2298                                       field_types: &[ty::field_ty],
2299                                       ast_fields: &[ast::Field],
2300                                       check_completeness: bool)  {
2301         let tcx = fcx.ccx.tcx;
2302
2303         let mut class_field_map = HashMap::new();
2304         let mut fields_found = 0;
2305         for field in field_types.iter() {
2306             class_field_map.insert(field.name, (field.id, false));
2307         }
2308
2309         let mut error_happened = false;
2310
2311         // Typecheck each field.
2312         for field in ast_fields.iter() {
2313             let mut expected_field_type = ty::mk_err();
2314
2315             let pair = class_field_map.find(&field.ident.node.name).map(|x| *x);
2316             match pair {
2317                 None => {
2318                     fcx.type_error_message(
2319                       field.ident.span,
2320                       |actual| {
2321                           format!("structure `{}` has no field named `{}`",
2322                                   actual, token::get_ident(field.ident.node))
2323                     }, struct_ty, None);
2324                     error_happened = true;
2325                 }
2326                 Some((_, true)) => {
2327                     tcx.sess.span_err(
2328                         field.ident.span,
2329                         format!("field `{}` specified more than once",
2330                             token::get_ident(field.ident.node)));
2331                     error_happened = true;
2332                 }
2333                 Some((field_id, false)) => {
2334                     expected_field_type =
2335                         ty::lookup_field_type(
2336                             tcx, class_id, field_id, &substitutions);
2337                     class_field_map.insert(
2338                         field.ident.node.name, (field_id, true));
2339                     fields_found += 1;
2340                 }
2341             }
2342             // Make sure to give a type to the field even if there's
2343             // an error, so we can continue typechecking
2344             check_expr_coercable_to_type(
2345                     fcx,
2346                     field.expr,
2347                     expected_field_type);
2348         }
2349
2350         if error_happened {
2351             fcx.write_error(node_id);
2352         }
2353
2354         if check_completeness && !error_happened {
2355             // Make sure the programmer specified all the fields.
2356             assert!(fields_found <= field_types.len());
2357             if fields_found < field_types.len() {
2358                 let mut missing_fields = Vec::new();
2359                 for class_field in field_types.iter() {
2360                     let name = class_field.name;
2361                     let (_, seen) = *class_field_map.get(&name);
2362                     if !seen {
2363                         missing_fields.push(~"`" + token::get_name(name).get() + "`");
2364                     }
2365                 }
2366
2367                 tcx.sess.span_err(span,
2368                     format!("missing {nfields, plural, =1{field} other{fields}}: {fields}",
2369                             nfields = missing_fields.len(),
2370                             fields = missing_fields.connect(", ")));
2371              }
2372         }
2373
2374         if !error_happened {
2375             fcx.write_ty(node_id, ty::mk_struct(fcx.ccx.tcx,
2376                                 class_id, substitutions));
2377         }
2378     }
2379
2380     fn check_struct_constructor(fcx: &FnCtxt,
2381                                 id: ast::NodeId,
2382                                 span: codemap::Span,
2383                                 class_id: ast::DefId,
2384                                 fields: &[ast::Field],
2385                                 base_expr: Option<@ast::Expr>) {
2386         let tcx = fcx.ccx.tcx;
2387
2388         // Look up the number of type parameters and the raw type, and
2389         // determine whether the class is region-parameterized.
2390         let item_type = ty::lookup_item_type(tcx, class_id);
2391         let type_parameter_count = item_type.generics.type_param_defs().len();
2392         let region_param_defs = item_type.generics.region_param_defs();
2393         let raw_type = item_type.ty;
2394
2395         // Generate the struct type.
2396         let regions = fcx.infcx().region_vars_for_defs(span, region_param_defs);
2397         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
2398         let substitutions = substs {
2399             regions: ty::NonerasedRegions(regions),
2400             self_ty: None,
2401             tps: type_parameters
2402         };
2403
2404         let mut struct_type = ty::subst(tcx, &substitutions, raw_type);
2405
2406         // Look up and check the fields.
2407         let class_fields = ty::lookup_struct_fields(tcx, class_id);
2408         check_struct_or_variant_fields(fcx,
2409                                            struct_type,
2410                                            span,
2411                                            class_id,
2412                                            id,
2413                                            substitutions,
2414                                            class_fields.as_slice(),
2415                                            fields,
2416                                            base_expr.is_none());
2417         if ty::type_is_error(fcx.node_ty(id)) {
2418             struct_type = ty::mk_err();
2419         }
2420
2421         // Check the base expression if necessary.
2422         match base_expr {
2423             None => {}
2424             Some(base_expr) => {
2425                 check_expr_has_type(fcx, base_expr, struct_type);
2426                 if ty::type_is_bot(fcx.node_ty(base_expr.id)) {
2427                     struct_type = ty::mk_bot();
2428                 }
2429             }
2430         }
2431
2432         // Write in the resulting type.
2433         fcx.write_ty(id, struct_type);
2434     }
2435
2436     fn check_struct_enum_variant(fcx: &FnCtxt,
2437                                  id: ast::NodeId,
2438                                  span: codemap::Span,
2439                                  enum_id: ast::DefId,
2440                                  variant_id: ast::DefId,
2441                                  fields: &[ast::Field]) {
2442         let tcx = fcx.ccx.tcx;
2443
2444         // Look up the number of type parameters and the raw type, and
2445         // determine whether the enum is region-parameterized.
2446         let item_type = ty::lookup_item_type(tcx, enum_id);
2447         let type_parameter_count = item_type.generics.type_param_defs().len();
2448         let region_param_defs = item_type.generics.region_param_defs();
2449         let raw_type = item_type.ty;
2450
2451         // Generate the enum type.
2452         let regions = fcx.infcx().region_vars_for_defs(span, region_param_defs);
2453         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
2454         let substitutions = substs {
2455             regions: ty::NonerasedRegions(regions),
2456             self_ty: None,
2457             tps: type_parameters
2458         };
2459
2460         let enum_type = ty::subst(tcx, &substitutions, raw_type);
2461
2462         // Look up and check the enum variant fields.
2463         let variant_fields = ty::lookup_struct_fields(tcx, variant_id);
2464         check_struct_or_variant_fields(fcx,
2465                                        enum_type,
2466                                        span,
2467                                        variant_id,
2468                                        id,
2469                                        substitutions,
2470                                        variant_fields.as_slice(),
2471                                        fields,
2472                                        true);
2473         fcx.write_ty(id, enum_type);
2474     }
2475
2476     let tcx = fcx.ccx.tcx;
2477     let id = expr.id;
2478     match expr.node {
2479       ast::ExprVstore(ev, vst) => {
2480         let typ = match ev.node {
2481           ast::ExprLit(lit) if ast_util::lit_is_str(lit) => {
2482             let tt = ast_expr_vstore_to_vstore(fcx, ev, vst);
2483             ty::mk_str(tcx, tt)
2484           }
2485           ast::ExprVec(ref args, mutbl) => {
2486             let tt = ast_expr_vstore_to_vstore(fcx, ev, vst);
2487             let mut any_error = false;
2488             let mut any_bot = false;
2489             let mutability = match vst {
2490                 ast::ExprVstoreMutSlice => ast::MutMutable,
2491                 _ => mutbl,
2492             };
2493             let t: ty::t = fcx.infcx().next_ty_var();
2494             for e in args.iter() {
2495                 check_expr_has_type(fcx, *e, t);
2496                 let arg_t = fcx.expr_ty(*e);
2497                 if ty::type_is_error(arg_t) {
2498                     any_error = true;
2499                 }
2500                 else if ty::type_is_bot(arg_t) {
2501                     any_bot = true;
2502                 }
2503             }
2504             if any_error {
2505                 ty::mk_err()
2506             } else if any_bot {
2507                 ty::mk_bot()
2508             } else {
2509                 ty::mk_vec(tcx, ty::mt {ty: t, mutbl: mutability}, tt)
2510             }
2511           }
2512           ast::ExprRepeat(element, count_expr, mutbl) => {
2513             check_expr_with_hint(fcx, count_expr, ty::mk_uint());
2514             let _ = ty::eval_repeat_count(fcx, count_expr);
2515             let tt = ast_expr_vstore_to_vstore(fcx, ev, vst);
2516             let mutability = match vst {
2517                 ast::ExprVstoreMutSlice => ast::MutMutable,
2518                 _ => mutbl,
2519             };
2520             let t: ty::t = fcx.infcx().next_ty_var();
2521             check_expr_has_type(fcx, element, t);
2522             let arg_t = fcx.expr_ty(element);
2523             if ty::type_is_error(arg_t) {
2524                 ty::mk_err()
2525             } else if ty::type_is_bot(arg_t) {
2526                 ty::mk_bot()
2527             } else {
2528                 ty::mk_vec(tcx, ty::mt {ty: t, mutbl: mutability}, tt)
2529             }
2530           }
2531           _ =>
2532             tcx.sess.span_bug(expr.span, "vstore modifier on non-sequence")
2533         };
2534         fcx.write_ty(ev.id, typ);
2535         fcx.write_ty(id, typ);
2536       }
2537
2538       ast::ExprBox(place, subexpr) => {
2539           check_expr(fcx, place);
2540           check_expr(fcx, subexpr);
2541
2542           let mut checked = false;
2543           match place.node {
2544               ast::ExprPath(ref path) => {
2545                   // FIXME(pcwalton): For now we hardcode the two permissible
2546                   // places: the exchange heap and the managed heap.
2547                   let definition = lookup_def(fcx, path.span, place.id);
2548                   let def_id = ast_util::def_id_of_def(definition);
2549                   match tcx.lang_items
2550                            .items
2551                            .get(ExchangeHeapLangItem as uint) {
2552                       &Some(item_def_id) if def_id == item_def_id => {
2553                           fcx.write_ty(id, ty::mk_uniq(tcx,
2554                                                        fcx.expr_ty(subexpr)));
2555                           checked = true
2556                       }
2557                       &Some(_) | &None => {}
2558                   }
2559                   if !checked {
2560                       match tcx.lang_items
2561                                .items
2562                                .get(ManagedHeapLangItem as uint) {
2563                           &Some(item_def_id) if def_id == item_def_id => {
2564                               // Assign the magic `Gc<T>` struct.
2565                               let gc_struct_id =
2566                                   match tcx.lang_items
2567                                            .require(GcLangItem) {
2568                                       Ok(id) => id,
2569                                       Err(msg) => {
2570                                           tcx.sess.span_err(expr.span, msg);
2571                                           ast::DefId {
2572                                               krate: ast::CRATE_NODE_ID,
2573                                               node: ast::DUMMY_NODE_ID,
2574                                           }
2575                                       }
2576                                   };
2577                               let regions =
2578                                   ty::NonerasedRegions(OwnedSlice::empty());
2579                               let sty = ty::mk_struct(tcx,
2580                                                       gc_struct_id,
2581                                                       substs {
2582                                                         self_ty: None,
2583                                                         tps: vec!(
2584                                                             fcx.expr_ty(
2585                                                                 subexpr)
2586                                                         ),
2587                                                         regions: regions,
2588                                                       });
2589                               fcx.write_ty(id, sty);
2590                               checked = true
2591                           }
2592                           &Some(_) | &None => {}
2593                       }
2594                   }
2595               }
2596               _ => {}
2597           }
2598
2599           if !checked {
2600               tcx.sess.span_err(expr.span,
2601                                 "only the managed heap and exchange heap are \
2602                                  currently supported")
2603           }
2604       }
2605
2606       ast::ExprLit(lit) => {
2607         let typ = check_lit(fcx, lit);
2608         fcx.write_ty(id, typ);
2609       }
2610       ast::ExprBinary(op, lhs, rhs) => {
2611         check_binop(fcx, expr, op, lhs, rhs, SimpleBinop);
2612
2613         let lhs_ty = fcx.expr_ty(lhs);
2614         let rhs_ty = fcx.expr_ty(rhs);
2615         if ty::type_is_error(lhs_ty) ||
2616             ty::type_is_error(rhs_ty) {
2617             fcx.write_error(id);
2618         }
2619         else if ty::type_is_bot(lhs_ty) ||
2620           (ty::type_is_bot(rhs_ty) && !ast_util::lazy_binop(op)) {
2621             fcx.write_bot(id);
2622         }
2623       }
2624       ast::ExprAssignOp(op, lhs, rhs) => {
2625         check_binop(fcx, expr, op, lhs, rhs, BinopAssignment);
2626
2627         let lhs_t = fcx.expr_ty(lhs);
2628         let result_t = fcx.expr_ty(expr);
2629         demand::suptype(fcx, expr.span, result_t, lhs_t);
2630
2631         let tcx = fcx.tcx();
2632         if !ty::expr_is_lval(tcx, fcx.ccx.method_map, lhs) {
2633             tcx.sess.span_err(lhs.span, "illegal left-hand side expression");
2634         }
2635
2636         // Overwrite result of check_binop...this preserves existing behavior
2637         // but seems quite dubious with regard to user-defined methods
2638         // and so forth. - Niko
2639         if !ty::type_is_error(result_t)
2640             && !ty::type_is_bot(result_t) {
2641             fcx.write_nil(expr.id);
2642         }
2643       }
2644       ast::ExprUnary(unop, oprnd) => {
2645         let exp_inner = unpack_expected(fcx, expected, |sty| {
2646             match unop {
2647                 ast::UnBox | ast::UnUniq => match *sty {
2648                     ty::ty_box(ty) | ty::ty_uniq(ty) => Some(ty),
2649                     _ => None
2650                 },
2651                 ast::UnNot | ast::UnNeg => expected,
2652                 ast::UnDeref => None
2653             }
2654         });
2655         let lvalue_pref = match unop {
2656             ast::UnDeref => lvalue_pref,
2657             _ => NoPreference
2658         };
2659         check_expr_with_opt_hint_and_lvalue_pref(fcx, oprnd, exp_inner, lvalue_pref);
2660         let mut oprnd_t = fcx.expr_ty(oprnd);
2661         if !ty::type_is_error(oprnd_t) && !ty::type_is_bot(oprnd_t) {
2662             match unop {
2663                 ast::UnBox => {
2664                     oprnd_t = ty::mk_box(tcx, oprnd_t)
2665                 }
2666                 ast::UnUniq => {
2667                     oprnd_t = ty::mk_uniq(tcx, oprnd_t);
2668                 }
2669                 ast::UnDeref => {
2670                     oprnd_t = structurally_resolved_type(fcx, expr.span, oprnd_t);
2671                     oprnd_t = match ty::deref(oprnd_t, true) {
2672                         Some(mt) => mt.ty,
2673                         None => match try_overloaded_deref(fcx, expr.span,
2674                                                            Some(MethodCall::expr(expr.id)),
2675                                                            Some(&*oprnd), oprnd_t, lvalue_pref) {
2676                             Some(mt) => mt.ty,
2677                             None => {
2678                                 let is_newtype = match ty::get(oprnd_t).sty {
2679                                     ty::ty_struct(did, ref substs) => {
2680                                         let fields = ty::struct_fields(fcx.tcx(), did, substs);
2681                                         fields.len() == 1
2682                                         && fields.get(0).ident ==
2683                                         token::special_idents::unnamed_field
2684                                     }
2685                                     _ => false
2686                                 };
2687                                 if is_newtype {
2688                                     // This is an obsolete struct deref
2689                                     tcx.sess.span_err(expr.span,
2690                                         "single-field tuple-structs can \
2691                                          no longer be dereferenced");
2692                                 } else {
2693                                     fcx.type_error_message(expr.span, |actual| {
2694                                         format!("type `{}` cannot be dereferenced", actual)
2695                                     }, oprnd_t, None);
2696                                 }
2697                                 ty::mk_err()
2698                             }
2699                         }
2700                     };
2701                 }
2702                 ast::UnNot => {
2703                     oprnd_t = structurally_resolved_type(fcx, oprnd.span,
2704                                                          oprnd_t);
2705                     if !(ty::type_is_integral(oprnd_t) ||
2706                          ty::get(oprnd_t).sty == ty::ty_bool) {
2707                         oprnd_t = check_user_unop(fcx, "!", "not",
2708                                                   tcx.lang_items.not_trait(),
2709                                                   expr, oprnd, oprnd_t);
2710                     }
2711                 }
2712                 ast::UnNeg => {
2713                     oprnd_t = structurally_resolved_type(fcx, oprnd.span,
2714                                                          oprnd_t);
2715                     if !(ty::type_is_integral(oprnd_t) ||
2716                          ty::type_is_fp(oprnd_t)) {
2717                         oprnd_t = check_user_unop(fcx, "-", "neg",
2718                                                   tcx.lang_items.neg_trait(),
2719                                                   expr, oprnd, oprnd_t);
2720                     }
2721                 }
2722             }
2723         }
2724         fcx.write_ty(id, oprnd_t);
2725       }
2726       ast::ExprAddrOf(mutbl, oprnd) => {
2727           let hint = unpack_expected(
2728               fcx, expected,
2729               |sty| match *sty { ty::ty_rptr(_, ref mt) => Some(mt.ty),
2730                                  _ => None });
2731         let lvalue_pref = match mutbl {
2732             ast::MutMutable => PreferMutLvalue,
2733             ast::MutImmutable => NoPreference
2734         };
2735         check_expr_with_opt_hint_and_lvalue_pref(fcx, oprnd, hint, lvalue_pref);
2736
2737         // Note: at this point, we cannot say what the best lifetime
2738         // is to use for resulting pointer.  We want to use the
2739         // shortest lifetime possible so as to avoid spurious borrowck
2740         // errors.  Moreover, the longest lifetime will depend on the
2741         // precise details of the value whose address is being taken
2742         // (and how long it is valid), which we don't know yet until type
2743         // inference is complete.
2744         //
2745         // Therefore, here we simply generate a region variable.  The
2746         // region inferencer will then select the ultimate value.
2747         // Finally, borrowck is charged with guaranteeing that the
2748         // value whose address was taken can actually be made to live
2749         // as long as it needs to live.
2750         let region = fcx.infcx().next_region_var(
2751             infer::AddrOfRegion(expr.span));
2752
2753         let tm = ty::mt { ty: fcx.expr_ty(oprnd), mutbl: mutbl };
2754         let oprnd_t = if ty::type_is_error(tm.ty) {
2755             ty::mk_err()
2756         } else if ty::type_is_bot(tm.ty) {
2757             ty::mk_bot()
2758         }
2759         else {
2760             ty::mk_rptr(tcx, region, tm)
2761         };
2762         fcx.write_ty(id, oprnd_t);
2763       }
2764       ast::ExprPath(ref pth) => {
2765         let defn = lookup_def(fcx, pth.span, id);
2766
2767         check_type_parameter_positions_in_path(fcx, pth, defn);
2768         let tpt = ty_param_bounds_and_ty_for_def(fcx, expr.span, defn);
2769         instantiate_path(fcx, pth, tpt, defn, expr.span, expr.id);
2770       }
2771       ast::ExprInlineAsm(ref ia) => {
2772           for &(_, input) in ia.inputs.iter() {
2773               check_expr(fcx, input);
2774           }
2775           for &(_, out) in ia.outputs.iter() {
2776               check_expr(fcx, out);
2777           }
2778           fcx.write_nil(id);
2779       }
2780       ast::ExprMac(_) => tcx.sess.bug("unexpanded macro"),
2781       ast::ExprBreak(_) => { fcx.write_bot(id); }
2782       ast::ExprAgain(_) => { fcx.write_bot(id); }
2783       ast::ExprRet(expr_opt) => {
2784         let ret_ty = fcx.ret_ty;
2785         match expr_opt {
2786           None => match fcx.mk_eqty(false, infer::Misc(expr.span),
2787                                     ret_ty, ty::mk_nil()) {
2788             result::Ok(_) => { /* fall through */ }
2789             result::Err(_) => {
2790                 tcx.sess.span_err(
2791                     expr.span,
2792                     "`return;` in function returning non-nil");
2793             }
2794           },
2795           Some(e) => {
2796               check_expr_has_type(fcx, e, ret_ty);
2797           }
2798         }
2799         fcx.write_bot(id);
2800       }
2801       ast::ExprParen(a) => {
2802         check_expr_with_opt_hint_and_lvalue_pref(fcx, a, expected, lvalue_pref);
2803         fcx.write_ty(id, fcx.expr_ty(a));
2804       }
2805       ast::ExprAssign(lhs, rhs) => {
2806         check_expr_with_lvalue_pref(fcx, lhs, PreferMutLvalue);
2807
2808         let tcx = fcx.tcx();
2809         if !ty::expr_is_lval(tcx, fcx.ccx.method_map, lhs) {
2810             tcx.sess.span_err(lhs.span, "illegal left-hand side expression");
2811         }
2812
2813         let lhs_ty = fcx.expr_ty(lhs);
2814         check_expr_has_type(fcx, rhs, lhs_ty);
2815         let rhs_ty = fcx.expr_ty(rhs);
2816
2817         if ty::type_is_error(lhs_ty) || ty::type_is_error(rhs_ty) {
2818             fcx.write_error(id);
2819         } else if ty::type_is_bot(lhs_ty) || ty::type_is_bot(rhs_ty) {
2820             fcx.write_bot(id);
2821         } else {
2822             fcx.write_nil(id);
2823         }
2824       }
2825       ast::ExprIf(cond, then_blk, opt_else_expr) => {
2826         check_then_else(fcx, cond, then_blk, opt_else_expr,
2827                         id, expr.span, expected);
2828       }
2829       ast::ExprWhile(cond, body) => {
2830         check_expr_has_type(fcx, cond, ty::mk_bool());
2831         check_block_no_value(fcx, body);
2832         let cond_ty = fcx.expr_ty(cond);
2833         let body_ty = fcx.node_ty(body.id);
2834         if ty::type_is_error(cond_ty) || ty::type_is_error(body_ty) {
2835             fcx.write_error(id);
2836         }
2837         else if ty::type_is_bot(cond_ty) {
2838             fcx.write_bot(id);
2839         }
2840         else {
2841             fcx.write_nil(id);
2842         }
2843       }
2844       ast::ExprForLoop(..) =>
2845           fail!("non-desugared expr_for_loop"),
2846       ast::ExprLoop(body, _) => {
2847         check_block_no_value(fcx, (body));
2848         if !may_break(tcx, expr.id, body) {
2849             fcx.write_bot(id);
2850         }
2851         else {
2852             fcx.write_nil(id);
2853         }
2854       }
2855       ast::ExprMatch(discrim, ref arms) => {
2856         _match::check_match(fcx, expr, discrim, arms.as_slice());
2857       }
2858       ast::ExprFnBlock(decl, body) => {
2859         check_expr_fn(fcx,
2860                       expr,
2861                       Some(ast::BorrowedSigil),
2862                       decl,
2863                       body,
2864                       Vanilla,
2865                       expected);
2866       }
2867       ast::ExprProc(decl, body) => {
2868         check_expr_fn(fcx,
2869                       expr,
2870                       Some(ast::OwnedSigil),
2871                       decl,
2872                       body,
2873                       Vanilla,
2874                       expected);
2875       }
2876       ast::ExprBlock(b) => {
2877         check_block_with_expected(fcx, b, expected);
2878         fcx.write_ty(id, fcx.node_ty(b.id));
2879       }
2880       ast::ExprCall(f, ref args) => {
2881           check_call(fcx, expr, f, args.as_slice());
2882           let f_ty = fcx.expr_ty(f);
2883           let (args_bot, args_err) = args.iter().fold((false, false),
2884              |(rest_bot, rest_err), a| {
2885                  // is this not working?
2886                  let a_ty = fcx.expr_ty(*a);
2887                  (rest_bot || ty::type_is_bot(a_ty),
2888                   rest_err || ty::type_is_error(a_ty))});
2889           if ty::type_is_error(f_ty) || args_err {
2890               fcx.write_error(id);
2891           }
2892           else if ty::type_is_bot(f_ty) || args_bot {
2893               fcx.write_bot(id);
2894           }
2895       }
2896       ast::ExprMethodCall(ident, ref tps, ref args) => {
2897         check_method_call(fcx, expr, ident, args.as_slice(), tps.as_slice());
2898         let mut arg_tys = args.iter().map(|a| fcx.expr_ty(*a));
2899         let (args_bot, args_err) = arg_tys.fold((false, false),
2900              |(rest_bot, rest_err), a| {
2901               (rest_bot || ty::type_is_bot(a),
2902                rest_err || ty::type_is_error(a))});
2903         if args_err {
2904             fcx.write_error(id);
2905         } else if args_bot {
2906             fcx.write_bot(id);
2907         }
2908       }
2909       ast::ExprCast(e, t) => {
2910         check_expr(fcx, e);
2911         let t_1 = fcx.to_ty(t);
2912         let t_e = fcx.expr_ty(e);
2913
2914         debug!("t_1={}", fcx.infcx().ty_to_str(t_1));
2915         debug!("t_e={}", fcx.infcx().ty_to_str(t_e));
2916
2917         if ty::type_is_error(t_e) {
2918             fcx.write_error(id);
2919         }
2920         else if ty::type_is_bot(t_e) {
2921             fcx.write_bot(id);
2922         }
2923         else {
2924             match ty::get(t_1).sty {
2925                 // This will be looked up later on
2926                 ty::ty_trait(..) => (),
2927
2928                 _ => {
2929                     if ty::type_is_nil(t_e) {
2930                         fcx.type_error_message(expr.span, |actual| {
2931                             format!("cast from nil: `{}` as `{}`", actual,
2932                                  fcx.infcx().ty_to_str(t_1))
2933                         }, t_e, None);
2934                     } else if ty::type_is_nil(t_1) {
2935                         fcx.type_error_message(expr.span, |actual| {
2936                             format!("cast to nil: `{}` as `{}`", actual,
2937                                  fcx.infcx().ty_to_str(t_1))
2938                         }, t_e, None);
2939                     }
2940
2941                     let t1 = structurally_resolved_type(fcx, e.span, t_1);
2942                     let te = structurally_resolved_type(fcx, e.span, t_e);
2943                     let t_1_is_scalar = type_is_scalar(fcx, expr.span, t_1);
2944                     let t_1_is_char = type_is_char(fcx, expr.span, t_1);
2945                     let t_1_is_bare_fn = type_is_bare_fn(fcx, expr.span, t_1);
2946
2947                     // casts to scalars other than `char` and `bare fn` are trivial
2948                     let t_1_is_trivial = t_1_is_scalar &&
2949                         !t_1_is_char && !t_1_is_bare_fn;
2950
2951                     if type_is_c_like_enum(fcx, expr.span, t_e) && t_1_is_trivial {
2952                         // casts from C-like enums are allowed
2953                     } else if t_1_is_char {
2954                         let te = fcx.infcx().resolve_type_vars_if_possible(te);
2955                         if ty::get(te).sty != ty::ty_uint(ast::TyU8) {
2956                             fcx.type_error_message(expr.span, |actual| {
2957                                 format!("only `u8` can be cast as `char`, not `{}`", actual)
2958                             }, t_e, None);
2959                         }
2960                     } else if ty::get(t1).sty == ty::ty_bool {
2961                         fcx.tcx().sess.span_err(expr.span,
2962                                                 "cannot cast as `bool`, compare with zero instead");
2963                     } else if type_is_region_ptr(fcx, expr.span, t_e) &&
2964                         type_is_unsafe_ptr(fcx, expr.span, t_1) {
2965
2966                         fn is_vec(t: ty::t) -> bool {
2967                             match ty::get(t).sty {
2968                                 ty::ty_vec(..) => true,
2969                                 _ => false
2970                             }
2971                         }
2972                         fn types_compatible(fcx: &FnCtxt, sp: Span,
2973                                             t1: ty::t, t2: ty::t) -> bool {
2974                             if !is_vec(t1) {
2975                                 false
2976                             } else {
2977                                 let el = ty::sequence_element_type(fcx.tcx(),
2978                                                                    t1);
2979                                 infer::mk_eqty(fcx.infcx(), false,
2980                                                infer::Misc(sp), el, t2).is_ok()
2981                             }
2982                         }
2983
2984                         // Due to the limitations of LLVM global constants,
2985                         // region pointers end up pointing at copies of
2986                         // vector elements instead of the original values.
2987                         // To allow unsafe pointers to work correctly, we
2988                         // need to special-case obtaining an unsafe pointer
2989                         // from a region pointer to a vector.
2990
2991                         /* this cast is only allowed from &[T] to *T or
2992                         &T to *T. */
2993                         match (&ty::get(te).sty, &ty::get(t_1).sty) {
2994                             (&ty::ty_rptr(_, mt1), &ty::ty_ptr(mt2))
2995                             if types_compatible(fcx, e.span,
2996                                                 mt1.ty, mt2.ty) => {
2997                                 /* this case is allowed */
2998                             }
2999                             _ => {
3000                                 demand::coerce(fcx, e.span, t_1, e);
3001                             }
3002                         }
3003                     } else if !(type_is_scalar(fcx,expr.span,t_e)
3004                                 && t_1_is_trivial) {
3005                         /*
3006                         If more type combinations should be supported than are
3007                         supported here, then file an enhancement issue and
3008                         record the issue number in this comment.
3009                         */
3010                         fcx.type_error_message(expr.span, |actual| {
3011                             format!("non-scalar cast: `{}` as `{}`", actual,
3012                                  fcx.infcx().ty_to_str(t_1))
3013                         }, t_e, None);
3014                     }
3015                 }
3016             }
3017             fcx.write_ty(id, t_1);
3018         }
3019       }
3020       ast::ExprVec(ref args, mutbl) => {
3021         let t: ty::t = fcx.infcx().next_ty_var();
3022         for e in args.iter() {
3023             check_expr_has_type(fcx, *e, t);
3024         }
3025         let typ = ty::mk_vec(tcx, ty::mt {ty: t, mutbl: mutbl},
3026                              ty::vstore_fixed(args.len()));
3027         fcx.write_ty(id, typ);
3028       }
3029       ast::ExprRepeat(element, count_expr, mutbl) => {
3030         check_expr_with_hint(fcx, count_expr, ty::mk_uint());
3031         let count = ty::eval_repeat_count(fcx, count_expr);
3032         let t: ty::t = fcx.infcx().next_ty_var();
3033         check_expr_has_type(fcx, element, t);
3034         let element_ty = fcx.expr_ty(element);
3035         if ty::type_is_error(element_ty) {
3036             fcx.write_error(id);
3037         }
3038         else if ty::type_is_bot(element_ty) {
3039             fcx.write_bot(id);
3040         }
3041         else {
3042             let t = ty::mk_vec(tcx, ty::mt {ty: t, mutbl: mutbl},
3043                                ty::vstore_fixed(count));
3044             fcx.write_ty(id, t);
3045         }
3046       }
3047       ast::ExprTup(ref elts) => {
3048         let flds = unpack_expected(fcx, expected, |sty| {
3049             match *sty {
3050                 ty::ty_tup(ref flds) => Some((*flds).clone()),
3051                 _ => None
3052             }
3053         });
3054         let mut bot_field = false;
3055         let mut err_field = false;
3056
3057         let elt_ts = elts.iter().enumerate().map(|(i, e)| {
3058             let opt_hint = match flds {
3059                 Some(ref fs) if i < fs.len() => Some(*fs.get(i)),
3060                 _ => None
3061             };
3062             check_expr_with_opt_hint(fcx, *e, opt_hint);
3063             let t = fcx.expr_ty(*e);
3064             err_field = err_field || ty::type_is_error(t);
3065             bot_field = bot_field || ty::type_is_bot(t);
3066             t
3067         }).collect();
3068         if bot_field {
3069             fcx.write_bot(id);
3070         } else if err_field {
3071             fcx.write_error(id);
3072         } else {
3073             let typ = ty::mk_tup(tcx, elt_ts);
3074             fcx.write_ty(id, typ);
3075         }
3076       }
3077       ast::ExprStruct(ref path, ref fields, base_expr) => {
3078         // Resolve the path.
3079         match tcx.def_map.borrow().find(&id) {
3080             Some(&ast::DefStruct(type_def_id)) => {
3081                 check_struct_constructor(fcx, id, expr.span, type_def_id,
3082                                          fields.as_slice(), base_expr);
3083             }
3084             Some(&ast::DefVariant(enum_id, variant_id, _)) => {
3085                 check_struct_enum_variant(fcx, id, expr.span, enum_id,
3086                                           variant_id, fields.as_slice());
3087             }
3088             _ => {
3089                 tcx.sess.span_bug(path.span,
3090                                   "structure constructor does not name a structure type");
3091             }
3092         }
3093       }
3094       ast::ExprField(base, field, ref tys) => {
3095         check_field(fcx, expr, lvalue_pref, base, field.name, tys.as_slice());
3096       }
3097       ast::ExprIndex(base, idx) => {
3098           check_expr_with_lvalue_pref(fcx, base, lvalue_pref);
3099           check_expr(fcx, idx);
3100           let raw_base_t = fcx.expr_ty(base);
3101           let idx_t = fcx.expr_ty(idx);
3102           if ty::type_is_error(raw_base_t) || ty::type_is_bot(raw_base_t) {
3103               fcx.write_ty(id, raw_base_t);
3104           } else if ty::type_is_error(idx_t) || ty::type_is_bot(idx_t) {
3105               fcx.write_ty(id, idx_t);
3106           } else {
3107               let (base_t, autoderefs, field_ty) =
3108                 autoderef(fcx, expr.span, raw_base_t, Some(base.id),
3109                           lvalue_pref, |base_t, _| ty::index(base_t));
3110               match field_ty {
3111                   Some(mt) => {
3112                       check_expr_has_type(fcx, idx, ty::mk_uint());
3113                       fcx.write_ty(id, mt.ty);
3114                       fcx.write_autoderef_adjustment(base.id, autoderefs);
3115                   }
3116                   None => {
3117                       let resolved = structurally_resolved_type(fcx,
3118                                                                 expr.span,
3119                                                                 raw_base_t);
3120                       let ret_ty = lookup_op_method(fcx,
3121                                                     expr,
3122                                                     resolved,
3123                                                     token::intern("index"),
3124                                                     tcx.lang_items.index_trait(),
3125                                                     [base, idx],
3126                                                     AutoderefReceiver,
3127                                                     || {
3128                         fcx.type_error_message(expr.span,
3129                                                |actual| {
3130                                                 format!("cannot index a value \
3131                                                       of type `{}`",
3132                                                      actual)
3133                                                },
3134                                                base_t,
3135                                                None);
3136                       });
3137                       fcx.write_ty(id, ret_ty);
3138                   }
3139               }
3140           }
3141        }
3142     }
3143
3144     debug!("type of expr({}) {} is...", expr.id,
3145            syntax::print::pprust::expr_to_str(expr));
3146     debug!("... {}, expected is {}",
3147            ppaux::ty_to_str(tcx, fcx.expr_ty(expr)),
3148            match expected {
3149                Some(t) => ppaux::ty_to_str(tcx, t),
3150                _ => ~"empty"
3151            });
3152
3153     unifier();
3154 }
3155
3156 pub fn require_uint(fcx: &FnCtxt, sp: Span, t: ty::t) {
3157     if !type_is_uint(fcx, sp, t) {
3158         fcx.type_error_message(sp, |actual| {
3159             format!("mismatched types: expected `uint` type but found `{}`",
3160                  actual)
3161         }, t, None);
3162     }
3163 }
3164
3165 pub fn require_integral(fcx: &FnCtxt, sp: Span, t: ty::t) {
3166     if !type_is_integral(fcx, sp, t) {
3167         fcx.type_error_message(sp, |actual| {
3168             format!("mismatched types: expected integral type but found `{}`",
3169                  actual)
3170         }, t, None);
3171     }
3172 }
3173
3174 pub fn check_decl_initializer(fcx: &FnCtxt,
3175                               nid: ast::NodeId,
3176                               init: &ast::Expr)
3177                             {
3178     let local_ty = fcx.local_ty(init.span, nid);
3179     check_expr_coercable_to_type(fcx, init, local_ty)
3180 }
3181
3182 pub fn check_decl_local(fcx: &FnCtxt, local: &ast::Local)  {
3183     let tcx = fcx.ccx.tcx;
3184
3185     let t = fcx.local_ty(local.span, local.id);
3186     fcx.write_ty(local.id, t);
3187
3188     match local.init {
3189         Some(init) => {
3190             check_decl_initializer(fcx, local.id, init);
3191             let init_ty = fcx.expr_ty(init);
3192             if ty::type_is_error(init_ty) || ty::type_is_bot(init_ty) {
3193                 fcx.write_ty(local.id, init_ty);
3194             }
3195         }
3196         _ => {}
3197     }
3198
3199     let pcx = pat_ctxt {
3200         fcx: fcx,
3201         map: pat_id_map(tcx.def_map, local.pat),
3202     };
3203     _match::check_pat(&pcx, local.pat, t);
3204     let pat_ty = fcx.node_ty(local.pat.id);
3205     if ty::type_is_error(pat_ty) || ty::type_is_bot(pat_ty) {
3206         fcx.write_ty(local.id, pat_ty);
3207     }
3208 }
3209
3210 pub fn check_stmt(fcx: &FnCtxt, stmt: &ast::Stmt)  {
3211     let node_id;
3212     let mut saw_bot = false;
3213     let mut saw_err = false;
3214     match stmt.node {
3215       ast::StmtDecl(decl, id) => {
3216         node_id = id;
3217         match decl.node {
3218           ast::DeclLocal(ref l) => {
3219               check_decl_local(fcx, *l);
3220               let l_t = fcx.node_ty(l.id);
3221               saw_bot = saw_bot || ty::type_is_bot(l_t);
3222               saw_err = saw_err || ty::type_is_error(l_t);
3223           }
3224           ast::DeclItem(_) => {/* ignore for now */ }
3225         }
3226       }
3227       ast::StmtExpr(expr, id) => {
3228         node_id = id;
3229         // Check with expected type of ()
3230         check_expr_has_type(fcx, expr, ty::mk_nil());
3231         let expr_ty = fcx.expr_ty(expr);
3232         saw_bot = saw_bot || ty::type_is_bot(expr_ty);
3233         saw_err = saw_err || ty::type_is_error(expr_ty);
3234       }
3235       ast::StmtSemi(expr, id) => {
3236         node_id = id;
3237         check_expr(fcx, expr);
3238         let expr_ty = fcx.expr_ty(expr);
3239         saw_bot |= ty::type_is_bot(expr_ty);
3240         saw_err |= ty::type_is_error(expr_ty);
3241       }
3242       ast::StmtMac(..) => fcx.ccx.tcx.sess.bug("unexpanded macro")
3243     }
3244     if saw_bot {
3245         fcx.write_bot(node_id);
3246     }
3247     else if saw_err {
3248         fcx.write_error(node_id);
3249     }
3250     else {
3251         fcx.write_nil(node_id)
3252     }
3253 }
3254
3255 pub fn check_block_no_value(fcx: &FnCtxt, blk: &ast::Block)  {
3256     check_block_with_expected(fcx, blk, Some(ty::mk_nil()));
3257     let blkty = fcx.node_ty(blk.id);
3258     if ty::type_is_error(blkty) {
3259         fcx.write_error(blk.id);
3260     }
3261     else if ty::type_is_bot(blkty) {
3262         fcx.write_bot(blk.id);
3263     }
3264     else {
3265         let nilty = ty::mk_nil();
3266         demand::suptype(fcx, blk.span, nilty, blkty);
3267     }
3268 }
3269
3270 pub fn check_block_with_expected(fcx: &FnCtxt,
3271                                  blk: &ast::Block,
3272                                  expected: Option<ty::t>) {
3273     let prev = {
3274         let mut fcx_ps = fcx.ps.borrow_mut();
3275         let purity_state = fcx_ps.recurse(blk);
3276         replace(&mut *fcx_ps, purity_state)
3277     };
3278
3279     fcx.with_region_lb(blk.id, || {
3280         let mut warned = false;
3281         let mut last_was_bot = false;
3282         let mut any_bot = false;
3283         let mut any_err = false;
3284         for s in blk.stmts.iter() {
3285             check_stmt(fcx, *s);
3286             let s_id = ast_util::stmt_id(*s);
3287             let s_ty = fcx.node_ty(s_id);
3288             if last_was_bot && !warned && match s.node {
3289                   ast::StmtDecl(decl, _) => {
3290                       match decl.node {
3291                           ast::DeclLocal(_) => true,
3292                           _ => false,
3293                       }
3294                   }
3295                   ast::StmtExpr(_, _) | ast::StmtSemi(_, _) => true,
3296                   _ => false
3297                 } {
3298                 fcx.ccx.tcx.sess.add_lint(UnreachableCode, s_id, s.span,
3299                                           ~"unreachable statement");
3300                 warned = true;
3301             }
3302             if ty::type_is_bot(s_ty) {
3303                 last_was_bot = true;
3304             }
3305             any_bot = any_bot || ty::type_is_bot(s_ty);
3306             any_err = any_err || ty::type_is_error(s_ty);
3307         }
3308         match blk.expr {
3309             None => if any_err {
3310                 fcx.write_error(blk.id);
3311             }
3312             else if any_bot {
3313                 fcx.write_bot(blk.id);
3314             }
3315             else  {
3316                 fcx.write_nil(blk.id);
3317             },
3318           Some(e) => {
3319             if any_bot && !warned {
3320                 fcx.ccx.tcx.sess.add_lint(UnreachableCode, e.id, e.span,
3321                                           ~"unreachable expression");
3322             }
3323             check_expr_with_opt_hint(fcx, e, expected);
3324               let ety = fcx.expr_ty(e);
3325               fcx.write_ty(blk.id, ety);
3326               if any_err {
3327                   fcx.write_error(blk.id);
3328               }
3329               else if any_bot {
3330                   fcx.write_bot(blk.id);
3331               }
3332           }
3333         };
3334     });
3335
3336     *fcx.ps.borrow_mut() = prev;
3337 }
3338
3339 pub fn check_const(ccx: &CrateCtxt,
3340                    sp: Span,
3341                    e: &ast::Expr,
3342                    id: ast::NodeId) {
3343     let inh = blank_inherited_fields(ccx);
3344     let rty = ty::node_id_to_type(ccx.tcx, id);
3345     let fcx = blank_fn_ctxt(ccx, &inh, rty, e.id);
3346     let declty = fcx.ccx.tcx.tcache.borrow().get(&local_def(id)).ty;
3347     check_const_with_ty(&fcx, sp, e, declty);
3348 }
3349
3350 pub fn check_const_with_ty(fcx: &FnCtxt,
3351                            _: Span,
3352                            e: &ast::Expr,
3353                            declty: ty::t) {
3354     check_expr(fcx, e);
3355     let cty = fcx.expr_ty(e);
3356     demand::suptype(fcx, e.span, declty, cty);
3357     regionck::regionck_expr(fcx, e);
3358     writeback::resolve_type_vars_in_expr(fcx, e);
3359 }
3360
3361 /// Checks whether a type can be represented in memory. In particular, it
3362 /// identifies types that contain themselves without indirection through a
3363 /// pointer, which would mean their size is unbounded. This is different from
3364 /// the question of whether a type can be instantiated. See the definition of
3365 /// `check_instantiable`.
3366 pub fn check_representable(tcx: &ty::ctxt,
3367                            sp: Span,
3368                            item_id: ast::NodeId,
3369                            designation: &str) {
3370     let rty = ty::node_id_to_type(tcx, item_id);
3371
3372     // Check that it is possible to represent this type. This call identifies
3373     // (1) types that contain themselves and (2) types that contain a different
3374     // recursive type. It is only necessary to throw an error on those that
3375     // contain themselves. For case 2, there must be an inner type that will be
3376     // caught by case 1.
3377     match ty::is_type_representable(tcx, rty) {
3378       ty::SelfRecursive => {
3379         tcx.sess.span_err(
3380           sp, format!("illegal recursive {} type; \
3381                        wrap the inner value in a box to make it representable",
3382                       designation));
3383       }
3384       ty::Representable | ty::ContainsRecursive => (),
3385     }
3386 }
3387
3388 /// Checks whether a type can be created without an instance of itself.
3389 /// This is similar but different from the question of whether a type
3390 /// can be represented.  For example, the following type:
3391 ///
3392 ///     enum foo { None, Some(foo) }
3393 ///
3394 /// is instantiable but is not representable.  Similarly, the type
3395 ///
3396 ///     enum foo { Some(@foo) }
3397 ///
3398 /// is representable, but not instantiable.
3399 pub fn check_instantiable(tcx: &ty::ctxt,
3400                           sp: Span,
3401                           item_id: ast::NodeId) {
3402     let item_ty = ty::node_id_to_type(tcx, item_id);
3403     if !ty::is_instantiable(tcx, item_ty) {
3404         tcx.sess.span_err(sp, format!("this type cannot be instantiated \
3405                   without an instance of itself; \
3406                   consider using `Option<{}>`",
3407                                    ppaux::ty_to_str(tcx, item_ty)));
3408     }
3409 }
3410
3411 pub fn check_simd(tcx: &ty::ctxt, sp: Span, id: ast::NodeId) {
3412     let t = ty::node_id_to_type(tcx, id);
3413     if ty::type_needs_subst(t) {
3414         tcx.sess.span_err(sp, "SIMD vector cannot be generic");
3415         return;
3416     }
3417     match ty::get(t).sty {
3418         ty::ty_struct(did, ref substs) => {
3419             let fields = ty::lookup_struct_fields(tcx, did);
3420             if fields.is_empty() {
3421                 tcx.sess.span_err(sp, "SIMD vector cannot be empty");
3422                 return;
3423             }
3424             let e = ty::lookup_field_type(tcx, did, fields.get(0).id, substs);
3425             if !fields.iter().all(
3426                          |f| ty::lookup_field_type(tcx, did, f.id, substs) == e) {
3427                 tcx.sess.span_err(sp, "SIMD vector should be homogeneous");
3428                 return;
3429             }
3430             if !ty::type_is_machine(e) {
3431                 tcx.sess.span_err(sp, "SIMD vector element type should be \
3432                                        machine type");
3433                 return;
3434             }
3435         }
3436         _ => ()
3437     }
3438 }
3439
3440 pub fn check_enum_variants(ccx: &CrateCtxt,
3441                            sp: Span,
3442                            vs: &[ast::P<ast::Variant>],
3443                            id: ast::NodeId) {
3444
3445     fn disr_in_range(ccx: &CrateCtxt,
3446                      ty: attr::IntType,
3447                      disr: ty::Disr) -> bool {
3448         fn uint_in_range(ccx: &CrateCtxt, ty: ast::UintTy, disr: ty::Disr) -> bool {
3449             match ty {
3450                 ast::TyU8 => disr as u8 as Disr == disr,
3451                 ast::TyU16 => disr as u16 as Disr == disr,
3452                 ast::TyU32 => disr as u32 as Disr == disr,
3453                 ast::TyU64 => disr as u64 as Disr == disr,
3454                 ast::TyU => uint_in_range(ccx, ccx.tcx.sess.targ_cfg.uint_type, disr)
3455             }
3456         }
3457         fn int_in_range(ccx: &CrateCtxt, ty: ast::IntTy, disr: ty::Disr) -> bool {
3458             match ty {
3459                 ast::TyI8 => disr as i8 as Disr == disr,
3460                 ast::TyI16 => disr as i16 as Disr == disr,
3461                 ast::TyI32 => disr as i32 as Disr == disr,
3462                 ast::TyI64 => disr as i64 as Disr == disr,
3463                 ast::TyI => int_in_range(ccx, ccx.tcx.sess.targ_cfg.int_type, disr)
3464             }
3465         }
3466         match ty {
3467             attr::UnsignedInt(ty) => uint_in_range(ccx, ty, disr),
3468             attr::SignedInt(ty) => int_in_range(ccx, ty, disr)
3469         }
3470     }
3471
3472     fn do_check(ccx: &CrateCtxt,
3473                 vs: &[ast::P<ast::Variant>],
3474                 id: ast::NodeId,
3475                 hint: attr::ReprAttr)
3476                 -> Vec<@ty::VariantInfo> {
3477
3478         let rty = ty::node_id_to_type(ccx.tcx, id);
3479         let mut variants: Vec<@ty::VariantInfo> = Vec::new();
3480         let mut disr_vals: Vec<ty::Disr> = Vec::new();
3481         let mut prev_disr_val: Option<ty::Disr> = None;
3482
3483         for &v in vs.iter() {
3484
3485             // If the discriminant value is specified explicitly in the enum check whether the
3486             // initialization expression is valid, otherwise use the last value plus one.
3487             let mut current_disr_val = match prev_disr_val {
3488                 Some(prev_disr_val) => prev_disr_val + 1,
3489                 None => ty::INITIAL_DISCRIMINANT_VALUE
3490             };
3491
3492             match v.node.disr_expr {
3493                 Some(e) => {
3494                     debug!("disr expr, checking {}", pprust::expr_to_str(e));
3495
3496                     let inh = blank_inherited_fields(ccx);
3497                     let fcx = blank_fn_ctxt(ccx, &inh, rty, e.id);
3498                     let declty = ty::mk_int_var(ccx.tcx, fcx.infcx().next_int_var_id());
3499                     check_const_with_ty(&fcx, e.span, e, declty);
3500                     // check_expr (from check_const pass) doesn't guarantee
3501                     // that the expression is in an form that eval_const_expr can
3502                     // handle, so we may still get an internal compiler error
3503
3504                     match const_eval::eval_const_expr_partial(ccx.tcx, e) {
3505                         Ok(const_eval::const_int(val)) => current_disr_val = val as Disr,
3506                         Ok(const_eval::const_uint(val)) => current_disr_val = val as Disr,
3507                         Ok(_) => {
3508                             ccx.tcx.sess.span_err(e.span, "expected signed integer constant");
3509                         }
3510                         Err(ref err) => {
3511                             ccx.tcx.sess.span_err(e.span, format!("expected constant: {}", *err));
3512                         }
3513                     }
3514                 },
3515                 None => ()
3516             };
3517
3518             // Check for duplicate discriminant values
3519             if disr_vals.contains(&current_disr_val) {
3520                 ccx.tcx.sess.span_err(v.span, "discriminant value already exists");
3521             }
3522             // Check for unrepresentable discriminant values
3523             match hint {
3524                 attr::ReprAny | attr::ReprExtern => (),
3525                 attr::ReprInt(sp, ity) => {
3526                     if !disr_in_range(ccx, ity, current_disr_val) {
3527                         ccx.tcx.sess.span_err(v.span,
3528                                               "discriminant value outside specified type");
3529                         ccx.tcx.sess.span_note(sp, "discriminant type specified here");
3530                     }
3531                 }
3532             }
3533             disr_vals.push(current_disr_val);
3534
3535             let variant_info = @VariantInfo::from_ast_variant(ccx.tcx, v, current_disr_val);
3536             prev_disr_val = Some(current_disr_val);
3537
3538             variants.push(variant_info);
3539         }
3540
3541         return variants;
3542     }
3543
3544     let hint = ty::lookup_repr_hint(ccx.tcx, ast::DefId { krate: ast::LOCAL_CRATE, node: id });
3545     if hint != attr::ReprAny && vs.len() <= 1 {
3546         let msg = if vs.len() == 1 {
3547             "unsupported representation for univariant enum"
3548         } else {
3549             "unsupported representation for zero-variant enum"
3550         };
3551         ccx.tcx.sess.span_err(sp, msg)
3552     }
3553
3554     let variants = do_check(ccx, vs, id, hint);
3555
3556     // cache so that ty::enum_variants won't repeat this work
3557     ccx.tcx.enum_var_cache.borrow_mut().insert(local_def(id), @variants);
3558
3559     // Check that it is possible to represent this enum.
3560     check_representable(ccx.tcx, sp, id, "enum");
3561
3562     // Check that it is possible to instantiate this enum:
3563     //
3564     // This *sounds* like the same that as representable, but it's
3565     // not.  See def'n of `check_instantiable()` for details.
3566     check_instantiable(ccx.tcx, sp, id);
3567 }
3568
3569 pub fn lookup_def(fcx: &FnCtxt, sp: Span, id: ast::NodeId) -> ast::Def {
3570     lookup_def_ccx(fcx.ccx, sp, id)
3571 }
3572
3573 // Returns the type parameter count and the type for the given definition.
3574 pub fn ty_param_bounds_and_ty_for_def(fcx: &FnCtxt,
3575                                       sp: Span,
3576                                       defn: ast::Def)
3577                                    -> ty_param_bounds_and_ty {
3578     match defn {
3579       ast::DefArg(nid, _) | ast::DefLocal(nid, _) |
3580       ast::DefBinding(nid, _) => {
3581           let typ = fcx.local_ty(sp, nid);
3582           return no_params(typ);
3583       }
3584       ast::DefFn(id, _) | ast::DefStaticMethod(id, _, _) |
3585       ast::DefStatic(id, _) | ast::DefVariant(_, id, _) |
3586       ast::DefStruct(id) => {
3587         return ty::lookup_item_type(fcx.ccx.tcx, id);
3588       }
3589       ast::DefUpvar(_, inner, _, _) => {
3590         return ty_param_bounds_and_ty_for_def(fcx, sp, *inner);
3591       }
3592       ast::DefTrait(_) |
3593       ast::DefTy(_) |
3594       ast::DefPrimTy(_) |
3595       ast::DefTyParam(..)=> {
3596         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found type");
3597       }
3598       ast::DefMod(..) | ast::DefForeignMod(..) => {
3599         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found module");
3600       }
3601       ast::DefUse(..) => {
3602         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found use");
3603       }
3604       ast::DefRegion(..) => {
3605         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found region");
3606       }
3607       ast::DefTyParamBinder(..) => {
3608         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found type parameter");
3609       }
3610       ast::DefLabel(..) => {
3611         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found label");
3612       }
3613       ast::DefSelfTy(..) => {
3614         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found self ty");
3615       }
3616       ast::DefMethod(..) => {
3617         fcx.ccx.tcx.sess.span_bug(sp, "expected value but found method");
3618       }
3619     }
3620 }
3621
3622 // Instantiates the given path, which must refer to an item with the given
3623 // number of type parameters and type.
3624 pub fn instantiate_path(fcx: &FnCtxt,
3625                         pth: &ast::Path,
3626                         tpt: ty_param_bounds_and_ty,
3627                         def: ast::Def,
3628                         span: Span,
3629                         node_id: ast::NodeId) {
3630     debug!(">>> instantiate_path");
3631
3632     let ty_param_count = tpt.generics.type_param_defs().len();
3633     let ty_param_req = tpt.generics.type_param_defs().iter()
3634                                                    .take_while(|x| x.default.is_none())
3635                                                    .len();
3636     let mut ty_substs_len = 0;
3637     for segment in pth.segments.iter() {
3638         ty_substs_len += segment.types.len()
3639     }
3640
3641     debug!("tpt={} ty_param_count={:?} ty_substs_len={:?}",
3642            tpt.repr(fcx.tcx()),
3643            ty_param_count,
3644            ty_substs_len);
3645
3646     // determine the region parameters, using the value given by the user
3647     // (if any) and otherwise using a fresh region variable
3648     let num_expected_regions = tpt.generics.region_param_defs().len();
3649     let num_supplied_regions = pth.segments.last().unwrap().lifetimes.len();
3650     let regions = if num_expected_regions == num_supplied_regions {
3651         OwnedSlice::from_vec(pth.segments.last().unwrap().lifetimes.iter().map(
3652             |l| ast_region_to_region(fcx.tcx(), l)).collect())
3653     } else {
3654         if num_supplied_regions != 0 {
3655             fcx.ccx.tcx.sess.span_err(
3656                 span,
3657                 format!("expected {nexpected, plural, =1{# lifetime parameter} \
3658                                                    other{# lifetime parameters}}, \
3659                          found {nsupplied, plural, =1{# lifetime parameter} \
3660                                                 other{# lifetime parameters}}",
3661                         nexpected = num_expected_regions,
3662                         nsupplied = num_supplied_regions));
3663         }
3664
3665         fcx.infcx().region_vars_for_defs(span, tpt.generics.region_param_defs.as_slice())
3666     };
3667     let regions = ty::NonerasedRegions(regions);
3668
3669     // Special case: If there is a self parameter, omit it from the list of
3670     // type parameters.
3671     //
3672     // Here we calculate the "user type parameter count", which is the number
3673     // of type parameters actually manifest in the AST. This will differ from
3674     // the internal type parameter count when there are self types involved.
3675     let (user_ty_param_count, user_ty_param_req, self_parameter_index) = match def {
3676         ast::DefStaticMethod(_, provenance @ ast::FromTrait(_), _) => {
3677             let generics = generics_of_static_method_container(fcx.ccx.tcx,
3678                                                                provenance);
3679             (ty_param_count - 1, ty_param_req - 1, Some(generics.type_param_defs().len()))
3680         }
3681         _ => (ty_param_count, ty_param_req, None),
3682     };
3683
3684     // determine values for type parameters, using the values given by
3685     // the user (if any) and otherwise using fresh type variables
3686     let (tps, regions) = if ty_substs_len == 0 {
3687         (fcx.infcx().next_ty_vars(ty_param_count), regions)
3688     } else if ty_param_count == 0 {
3689         fcx.ccx.tcx.sess.span_err
3690             (span, "this item does not take type parameters");
3691         (fcx.infcx().next_ty_vars(ty_param_count), regions)
3692     } else if ty_substs_len > user_ty_param_count {
3693         let expected = if user_ty_param_req < user_ty_param_count {
3694             "expected at most"
3695         } else {
3696             "expected"
3697         };
3698         fcx.ccx.tcx.sess.span_err
3699             (span,
3700              format!("too many type parameters provided: {} {}, found {}",
3701                   expected, user_ty_param_count, ty_substs_len));
3702         (fcx.infcx().next_ty_vars(ty_param_count), regions)
3703     } else if ty_substs_len < user_ty_param_req {
3704         let expected = if user_ty_param_req < user_ty_param_count {
3705             "expected at least"
3706         } else {
3707             "expected"
3708         };
3709         fcx.ccx.tcx.sess.span_err
3710             (span,
3711              format!("not enough type parameters provided: {} {}, found {}",
3712                   expected, user_ty_param_req, ty_substs_len));
3713         (fcx.infcx().next_ty_vars(ty_param_count), regions)
3714     } else {
3715         if ty_substs_len > user_ty_param_req
3716             && !fcx.tcx().sess.features.default_type_params.get() {
3717             fcx.tcx().sess.span_err(pth.span, "default type parameters are \
3718                                                experimental and possibly buggy");
3719             fcx.tcx().sess.span_note(pth.span, "add #[feature(default_type_params)] \
3720                                                 to the crate attributes to enable");
3721         }
3722
3723         // Build up the list of type parameters, inserting the self parameter
3724         // at the appropriate position.
3725         let mut tps = Vec::new();
3726         let mut pushed = false;
3727         for (i, ty) in pth.segments.iter()
3728                                    .flat_map(|segment| segment.types.iter())
3729                                    .map(|&ast_type| fcx.to_ty(ast_type))
3730                                    .enumerate() {
3731             match self_parameter_index {
3732                 Some(index) if index == i => {
3733                     tps.push(*fcx.infcx().next_ty_vars(1).get(0));
3734                     pushed = true;
3735                 }
3736                 _ => {}
3737             }
3738             tps.push(ty)
3739         }
3740
3741         let mut substs = substs {
3742             regions: regions,
3743             self_ty: None,
3744             tps: tps
3745         };
3746
3747         let defaults = tpt.generics.type_param_defs().iter()
3748                           .enumerate().filter_map(|(i, x)| {
3749             match self_parameter_index {
3750                 Some(index) if index == i => None,
3751                 _ => Some(x.default)
3752             }
3753         });
3754         for (i, default) in defaults.skip(ty_substs_len).enumerate() {
3755             match self_parameter_index {
3756                 Some(index) if index == i + ty_substs_len => {
3757                     substs.tps.push(*fcx.infcx().next_ty_vars(1).get(0));
3758                     pushed = true;
3759                 }
3760                 _ => {}
3761             }
3762             match default {
3763                 Some(default) => {
3764                     let ty = default.subst_spanned(fcx.tcx(), &substs, Some(span));
3765                     substs.tps.push(ty);
3766                 }
3767                 None => {
3768                     fcx.tcx().sess.span_bug(span,
3769                         "missing default for a not explicitely provided type param")
3770                 }
3771             }
3772         }
3773
3774         // If the self parameter goes at the end, insert it there.
3775         if !pushed && self_parameter_index.is_some() {
3776             substs.tps.push(*fcx.infcx().next_ty_vars(1).get(0))
3777         }
3778
3779         assert_eq!(substs.tps.len(), ty_param_count)
3780
3781         let substs {tps, regions, ..} = substs;
3782         (tps, regions)
3783     };
3784
3785     fcx.write_ty_substs(node_id, tpt.ty, substs {
3786         regions: regions,
3787         self_ty: None,
3788         tps: tps
3789     });
3790
3791     debug!("<<<");
3792 }
3793
3794 // Resolves `typ` by a single level if `typ` is a type variable.  If no
3795 // resolution is possible, then an error is reported.
3796 pub fn structurally_resolved_type(fcx: &FnCtxt, sp: Span, tp: ty::t) -> ty::t {
3797     match infer::resolve_type(fcx.infcx(), tp, force_tvar) {
3798         Ok(t_s) if !ty::type_is_ty_var(t_s) => t_s,
3799         _ => {
3800             fcx.type_error_message(sp, |_actual| {
3801                 ~"the type of this value must be known in this context"
3802             }, tp, None);
3803             demand::suptype(fcx, sp, ty::mk_err(), tp);
3804             tp
3805         }
3806     }
3807 }
3808
3809 // Returns the one-level-deep structure of the given type.
3810 pub fn structure_of<'a>(fcx: &FnCtxt, sp: Span, typ: ty::t)
3811                         -> &'a ty::sty {
3812     &ty::get(structurally_resolved_type(fcx, sp, typ)).sty
3813 }
3814
3815 pub fn type_is_integral(fcx: &FnCtxt, sp: Span, typ: ty::t) -> bool {
3816     let typ_s = structurally_resolved_type(fcx, sp, typ);
3817     return ty::type_is_integral(typ_s);
3818 }
3819
3820 pub fn type_is_uint(fcx: &FnCtxt, sp: Span, typ: ty::t) -> bool {
3821     let typ_s = structurally_resolved_type(fcx, sp, typ);
3822     return ty::type_is_uint(typ_s);
3823 }
3824
3825 pub fn type_is_scalar(fcx: &FnCtxt, sp: Span, typ: ty::t) -> bool {
3826     let typ_s = structurally_resolved_type(fcx, sp, typ);
3827     return ty::type_is_scalar(typ_s);
3828 }
3829
3830 pub fn type_is_char(fcx: &FnCtxt, sp: Span, typ: ty::t) -> bool {
3831     let typ_s = structurally_resolved_type(fcx, sp, typ);
3832     return ty::type_is_char(typ_s);
3833 }
3834
3835 pub fn type_is_bare_fn(fcx: &FnCtxt, sp: Span, typ: ty::t) -> bool {
3836     let typ_s = structurally_resolved_type(fcx, sp, typ);
3837     return ty::type_is_bare_fn(typ_s);
3838 }
3839
3840 pub fn type_is_unsafe_ptr(fcx: &FnCtxt, sp: Span, typ: ty::t) -> bool {
3841     let typ_s = structurally_resolved_type(fcx, sp, typ);
3842     return ty::type_is_unsafe_ptr(typ_s);
3843 }
3844
3845 pub fn type_is_region_ptr(fcx: &FnCtxt, sp: Span, typ: ty::t) -> bool {
3846     let typ_s = structurally_resolved_type(fcx, sp, typ);
3847     return ty::type_is_region_ptr(typ_s);
3848 }
3849
3850 pub fn type_is_c_like_enum(fcx: &FnCtxt, sp: Span, typ: ty::t) -> bool {
3851     let typ_s = structurally_resolved_type(fcx, sp, typ);
3852     return ty::type_is_c_like_enum(fcx.ccx.tcx, typ_s);
3853 }
3854
3855 pub fn ast_expr_vstore_to_vstore(fcx: &FnCtxt,
3856                                  e: &ast::Expr,
3857                                  v: ast::ExprVstore)
3858                               -> ty::vstore {
3859     match v {
3860         ast::ExprVstoreUniq => ty::vstore_uniq,
3861         ast::ExprVstoreSlice | ast::ExprVstoreMutSlice => {
3862             match e.node {
3863                 ast::ExprLit(..) => {
3864                     // string literals and *empty slices* live in static memory
3865                     ty::vstore_slice(ty::ReStatic)
3866                 }
3867                 ast::ExprVec(ref elements, _) if elements.len() == 0 => {
3868                     // string literals and *empty slices* live in static memory
3869                     ty::vstore_slice(ty::ReStatic)
3870                 }
3871                 ast::ExprRepeat(..) |
3872                 ast::ExprVec(..) => {
3873                     // vector literals are temporaries on the stack
3874                     match fcx.tcx().region_maps.temporary_scope(e.id) {
3875                         Some(scope) => {
3876                             let r = ty::ReScope(scope);
3877                             ty::vstore_slice(r)
3878                         }
3879                         None => {
3880                             // this slice occurs in a static somewhere
3881                             ty::vstore_slice(ty::ReStatic)
3882                         }
3883                     }
3884                 }
3885                 _ => {
3886                     fcx.ccx.tcx.sess.span_bug(
3887                         e.span, format!("vstore with unexpected contents"))
3888                 }
3889             }
3890         }
3891     }
3892 }
3893
3894 // Returns true if b contains a break that can exit from b
3895 pub fn may_break(cx: &ty::ctxt, id: ast::NodeId, b: ast::P<ast::Block>) -> bool {
3896     // First: is there an unlabeled break immediately
3897     // inside the loop?
3898     (loop_query(b, |e| {
3899         match *e {
3900             ast::ExprBreak(_) => true,
3901             _ => false
3902         }
3903     })) ||
3904    // Second: is there a labeled break with label
3905    // <id> nested anywhere inside the loop?
3906     (block_query(b, |e| {
3907         match e.node {
3908             ast::ExprBreak(Some(_)) => {
3909                 match cx.def_map.borrow().find(&e.id) {
3910                     Some(&ast::DefLabel(loop_id)) if id == loop_id => true,
3911                     _ => false,
3912                 }
3913             }
3914             _ => false
3915         }}))
3916 }
3917
3918 pub fn check_bounds_are_used(ccx: &CrateCtxt,
3919                              span: Span,
3920                              tps: &OwnedSlice<ast::TyParam>,
3921                              ty: ty::t) {
3922     debug!("check_bounds_are_used(n_tps={}, ty={})",
3923            tps.len(), ppaux::ty_to_str(ccx.tcx, ty));
3924
3925     // make a vector of booleans initially false, set to true when used
3926     if tps.len() == 0u { return; }
3927     let mut tps_used = slice::from_elem(tps.len(), false);
3928
3929     ty::walk_ty(ty, |t| {
3930             match ty::get(t).sty {
3931                 ty::ty_param(param_ty {idx, ..}) => {
3932                     debug!("Found use of ty param \\#{}", idx);
3933                     tps_used[idx] = true;
3934                 }
3935                 _ => ()
3936             }
3937         });
3938
3939     for (i, b) in tps_used.iter().enumerate() {
3940         if !*b {
3941             ccx.tcx.sess.span_err(
3942                 span, format!("type parameter `{}` is unused",
3943                               token::get_ident(tps.get(i).ident)));
3944         }
3945     }
3946 }
3947
3948 pub fn check_intrinsic_type(ccx: &CrateCtxt, it: &ast::ForeignItem) {
3949     fn param(ccx: &CrateCtxt, n: uint) -> ty::t {
3950         ty::mk_param(ccx.tcx, n, local_def(0))
3951     }
3952
3953     let tcx = ccx.tcx;
3954     let name = token::get_ident(it.ident);
3955     let (n_tps, inputs, output) = if name.get().starts_with("atomic_") {
3956         let split : Vec<&str> = name.get().split('_').collect();
3957         assert!(split.len() >= 2, "Atomic intrinsic not correct format");
3958
3959         //We only care about the operation here
3960         match *split.get(1) {
3961             "cxchg" => (1, vec!(ty::mk_mut_ptr(tcx, param(ccx, 0)),
3962                                 param(ccx, 0),
3963                                 param(ccx, 0)),
3964                         param(ccx, 0)),
3965             "load" => (1, vec!(ty::mk_imm_ptr(tcx, param(ccx, 0))),
3966                        param(ccx, 0)),
3967             "store" => (1, vec!(ty::mk_mut_ptr(tcx, param(ccx, 0)), param(ccx, 0)),
3968                         ty::mk_nil()),
3969
3970             "xchg" | "xadd" | "xsub" | "and"  | "nand" | "or" | "xor" | "max" |
3971             "min"  | "umax" | "umin" => {
3972                 (1, vec!(ty::mk_mut_ptr(tcx, param(ccx, 0)), param(ccx, 0)),
3973                  param(ccx, 0))
3974             }
3975             "fence" => {
3976                 (0, Vec::new(), ty::mk_nil())
3977             }
3978             op => {
3979                 tcx.sess.span_err(it.span,
3980                                   format!("unrecognized atomic operation function: `{}`",
3981                                        op));
3982                 return;
3983             }
3984         }
3985
3986     } else {
3987         match name.get() {
3988             "abort" => (0, Vec::new(), ty::mk_bot()),
3989             "breakpoint" => (0, Vec::new(), ty::mk_nil()),
3990             "size_of" |
3991             "pref_align_of" | "min_align_of" => (1u, Vec::new(), ty::mk_uint()),
3992             "init" => (1u, Vec::new(), param(ccx, 0u)),
3993             "uninit" => (1u, Vec::new(), param(ccx, 0u)),
3994             "forget" => (1u, vec!( param(ccx, 0) ), ty::mk_nil()),
3995             "transmute" => (2, vec!( param(ccx, 0) ), param(ccx, 1)),
3996             "move_val_init" => {
3997                 (1u,
3998                  vec!(
3999                     ty::mk_mut_rptr(tcx, ty::ReLateBound(it.id, ty::BrAnon(0)), param(ccx, 0)),
4000                     param(ccx, 0u)
4001                   ),
4002                ty::mk_nil())
4003             }
4004             "needs_drop" => (1u, Vec::new(), ty::mk_bool()),
4005             "owns_managed" => (1u, Vec::new(), ty::mk_bool()),
4006
4007             "get_tydesc" => {
4008               let tydesc_ty = match ty::get_tydesc_ty(ccx.tcx) {
4009                   Ok(t) => t,
4010                   Err(s) => { tcx.sess.span_fatal(it.span, s); }
4011               };
4012               let td_ptr = ty::mk_ptr(ccx.tcx, ty::mt {
4013                   ty: tydesc_ty,
4014                   mutbl: ast::MutImmutable
4015               });
4016               (1u, Vec::new(), td_ptr)
4017             }
4018             "type_id" => {
4019                 let langid = ccx.tcx.lang_items.require(TypeIdLangItem);
4020                 match langid {
4021                     Ok(did) => (1u, Vec::new(), ty::mk_struct(ccx.tcx, did, substs {
4022                                                  self_ty: None,
4023                                                  tps: Vec::new(),
4024                                                  regions: ty::NonerasedRegions(OwnedSlice::empty())
4025                                                  }) ),
4026                     Err(msg) => { tcx.sess.span_fatal(it.span, msg); }
4027                 }
4028             },
4029             "visit_tydesc" => {
4030               let tydesc_ty = match ty::get_tydesc_ty(ccx.tcx) {
4031                   Ok(t) => t,
4032                   Err(s) => { tcx.sess.span_fatal(it.span, s); }
4033               };
4034               let region = ty::ReLateBound(it.id, ty::BrAnon(0));
4035               let visitor_object_ty = match ty::visitor_object_ty(tcx, region) {
4036                   Ok((_, vot)) => vot,
4037                   Err(s) => { tcx.sess.span_fatal(it.span, s); }
4038               };
4039
4040               let td_ptr = ty::mk_ptr(ccx.tcx, ty::mt {
4041                   ty: tydesc_ty,
4042                   mutbl: ast::MutImmutable
4043               });
4044               (0, vec!( td_ptr, visitor_object_ty ), ty::mk_nil())
4045             }
4046             "offset" => {
4047               (1,
4048                vec!(
4049                   ty::mk_ptr(tcx, ty::mt {
4050                       ty: param(ccx, 0),
4051                       mutbl: ast::MutImmutable
4052                   }),
4053                   ty::mk_int()
4054                ),
4055                ty::mk_ptr(tcx, ty::mt {
4056                    ty: param(ccx, 0),
4057                    mutbl: ast::MutImmutable
4058                }))
4059             }
4060             "copy_nonoverlapping_memory" => {
4061               (1,
4062                vec!(
4063                   ty::mk_ptr(tcx, ty::mt {
4064                       ty: param(ccx, 0),
4065                       mutbl: ast::MutMutable
4066                   }),
4067                   ty::mk_ptr(tcx, ty::mt {
4068                       ty: param(ccx, 0),
4069                       mutbl: ast::MutImmutable
4070                   }),
4071                   ty::mk_uint()
4072                ),
4073                ty::mk_nil())
4074             }
4075             "copy_memory" => {
4076               (1,
4077                vec!(
4078                   ty::mk_ptr(tcx, ty::mt {
4079                       ty: param(ccx, 0),
4080                       mutbl: ast::MutMutable
4081                   }),
4082                   ty::mk_ptr(tcx, ty::mt {
4083                       ty: param(ccx, 0),
4084                       mutbl: ast::MutImmutable
4085                   }),
4086                   ty::mk_uint()
4087                ),
4088                ty::mk_nil())
4089             }
4090             "set_memory" => {
4091               (1,
4092                vec!(
4093                   ty::mk_ptr(tcx, ty::mt {
4094                       ty: param(ccx, 0),
4095                       mutbl: ast::MutMutable
4096                   }),
4097                   ty::mk_u8(),
4098                   ty::mk_uint()
4099                ),
4100                ty::mk_nil())
4101             }
4102             "sqrtf32" => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4103             "sqrtf64" => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4104             "powif32" => {
4105                (0,
4106                 vec!( ty::mk_f32(), ty::mk_i32() ),
4107                 ty::mk_f32())
4108             }
4109             "powif64" => {
4110                (0,
4111                 vec!( ty::mk_f64(), ty::mk_i32() ),
4112                 ty::mk_f64())
4113             }
4114             "sinf32" => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4115             "sinf64" => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4116             "cosf32" => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4117             "cosf64" => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4118             "powf32" => {
4119                (0,
4120                 vec!( ty::mk_f32(), ty::mk_f32() ),
4121                 ty::mk_f32())
4122             }
4123             "powf64" => {
4124                (0,
4125                 vec!( ty::mk_f64(), ty::mk_f64() ),
4126                 ty::mk_f64())
4127             }
4128             "expf32"   => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4129             "expf64"   => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4130             "exp2f32"  => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4131             "exp2f64"  => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4132             "logf32"   => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4133             "logf64"   => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4134             "log10f32" => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4135             "log10f64" => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4136             "log2f32"  => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4137             "log2f64"  => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4138             "fmaf32" => {
4139                 (0,
4140                  vec!( ty::mk_f32(), ty::mk_f32(), ty::mk_f32() ),
4141                  ty::mk_f32())
4142             }
4143             "fmaf64" => {
4144                 (0,
4145                  vec!( ty::mk_f64(), ty::mk_f64(), ty::mk_f64() ),
4146                  ty::mk_f64())
4147             }
4148             "fabsf32"      => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4149             "fabsf64"      => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4150             "copysignf32"  => (0, vec!( ty::mk_f32(), ty::mk_f32() ), ty::mk_f32()),
4151             "copysignf64"  => (0, vec!( ty::mk_f64(), ty::mk_f64() ), ty::mk_f64()),
4152             "floorf32"     => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4153             "floorf64"     => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4154             "ceilf32"      => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4155             "ceilf64"      => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4156             "truncf32"     => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4157             "truncf64"     => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4158             "rintf32"      => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4159             "rintf64"      => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4160             "nearbyintf32" => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4161             "nearbyintf64" => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4162             "roundf32"     => (0, vec!( ty::mk_f32() ), ty::mk_f32()),
4163             "roundf64"     => (0, vec!( ty::mk_f64() ), ty::mk_f64()),
4164             "ctpop8"       => (0, vec!( ty::mk_i8()  ), ty::mk_i8()),
4165             "ctpop16"      => (0, vec!( ty::mk_i16() ), ty::mk_i16()),
4166             "ctpop32"      => (0, vec!( ty::mk_i32() ), ty::mk_i32()),
4167             "ctpop64"      => (0, vec!( ty::mk_i64() ), ty::mk_i64()),
4168             "ctlz8"        => (0, vec!( ty::mk_i8()  ), ty::mk_i8()),
4169             "ctlz16"       => (0, vec!( ty::mk_i16() ), ty::mk_i16()),
4170             "ctlz32"       => (0, vec!( ty::mk_i32() ), ty::mk_i32()),
4171             "ctlz64"       => (0, vec!( ty::mk_i64() ), ty::mk_i64()),
4172             "cttz8"        => (0, vec!( ty::mk_i8()  ), ty::mk_i8()),
4173             "cttz16"       => (0, vec!( ty::mk_i16() ), ty::mk_i16()),
4174             "cttz32"       => (0, vec!( ty::mk_i32() ), ty::mk_i32()),
4175             "cttz64"       => (0, vec!( ty::mk_i64() ), ty::mk_i64()),
4176             "bswap16"      => (0, vec!( ty::mk_i16() ), ty::mk_i16()),
4177             "bswap32"      => (0, vec!( ty::mk_i32() ), ty::mk_i32()),
4178             "bswap64"      => (0, vec!( ty::mk_i64() ), ty::mk_i64()),
4179
4180             "volatile_load" =>
4181                 (1, vec!( ty::mk_imm_ptr(tcx, param(ccx, 0)) ), param(ccx, 0)),
4182             "volatile_store" =>
4183                 (1, vec!( ty::mk_mut_ptr(tcx, param(ccx, 0)), param(ccx, 0) ), ty::mk_nil()),
4184
4185             "i8_add_with_overflow" | "i8_sub_with_overflow" | "i8_mul_with_overflow" =>
4186                 (0, vec!(ty::mk_i8(), ty::mk_i8()),
4187                 ty::mk_tup(tcx, vec!(ty::mk_i8(), ty::mk_bool()))),
4188
4189             "i16_add_with_overflow" | "i16_sub_with_overflow" | "i16_mul_with_overflow" =>
4190                 (0, vec!(ty::mk_i16(), ty::mk_i16()),
4191                 ty::mk_tup(tcx, vec!(ty::mk_i16(), ty::mk_bool()))),
4192
4193             "i32_add_with_overflow" | "i32_sub_with_overflow" | "i32_mul_with_overflow" =>
4194                 (0, vec!(ty::mk_i32(), ty::mk_i32()),
4195                 ty::mk_tup(tcx, vec!(ty::mk_i32(), ty::mk_bool()))),
4196
4197             "i64_add_with_overflow" | "i64_sub_with_overflow" | "i64_mul_with_overflow" =>
4198                 (0, vec!(ty::mk_i64(), ty::mk_i64()),
4199                 ty::mk_tup(tcx, vec!(ty::mk_i64(), ty::mk_bool()))),
4200
4201             "u8_add_with_overflow" | "u8_sub_with_overflow" | "u8_mul_with_overflow" =>
4202                 (0, vec!(ty::mk_u8(), ty::mk_u8()),
4203                 ty::mk_tup(tcx, vec!(ty::mk_u8(), ty::mk_bool()))),
4204
4205             "u16_add_with_overflow" | "u16_sub_with_overflow" | "u16_mul_with_overflow" =>
4206                 (0, vec!(ty::mk_u16(), ty::mk_u16()),
4207                 ty::mk_tup(tcx, vec!(ty::mk_u16(), ty::mk_bool()))),
4208
4209             "u32_add_with_overflow" | "u32_sub_with_overflow" | "u32_mul_with_overflow"=>
4210                 (0, vec!(ty::mk_u32(), ty::mk_u32()),
4211                 ty::mk_tup(tcx, vec!(ty::mk_u32(), ty::mk_bool()))),
4212
4213             "u64_add_with_overflow" | "u64_sub_with_overflow"  | "u64_mul_with_overflow" =>
4214                 (0, vec!(ty::mk_u64(), ty::mk_u64()),
4215                 ty::mk_tup(tcx, vec!(ty::mk_u64(), ty::mk_bool()))),
4216
4217             ref other => {
4218                 tcx.sess.span_err(it.span,
4219                                   format!("unrecognized intrinsic function: `{}`",
4220                                        *other));
4221                 return;
4222             }
4223         }
4224     };
4225     let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
4226         purity: ast::UnsafeFn,
4227         abi: abi::RustIntrinsic,
4228         sig: FnSig {binder_id: it.id,
4229                     inputs: inputs,
4230                     output: output,
4231                     variadic: false}
4232     });
4233     let i_ty = ty::lookup_item_type(ccx.tcx, local_def(it.id));
4234     let i_n_tps = i_ty.generics.type_param_defs().len();
4235     if i_n_tps != n_tps {
4236         tcx.sess.span_err(it.span, format!("intrinsic has wrong number \
4237                                          of type parameters: found {}, \
4238                                          expected {}", i_n_tps, n_tps));
4239     } else {
4240         require_same_types(
4241             tcx, None, false, it.span, i_ty.ty, fty,
4242             || format!("intrinsic has wrong type: \
4243                       expected `{}`",
4244                      ppaux::ty_to_str(ccx.tcx, fty)));
4245     }
4246 }