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