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

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