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