src/librustc_typeck/check/mod.rs

   1 // Copyright 2012-2015 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 `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.item_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 pub use self::LvaluePreference::*;
  80 pub use self::Expectation::*;
  81 pub use self::compare_method::{compare_impl_method, compare_const_impl};
  82 use self::TupleArgumentsFlag::*;
  83
  84 use astconv::{self, ast_region_to_region, ast_ty_to_ty, AstConv, PathParamMode};
  85 use check::_match::pat_ctxt;
  86 use fmt_macros::{Parser, Piece, Position};
  87 use middle::astconv_util::{check_path_args, NO_TPS, NO_REGIONS};
  88 use middle::def;
  89 use middle::infer;
  90 use middle::infer::type_variable;
  91 use middle::pat_util::{self, pat_id_map};
  92 use middle::privacy::{AllPublic, LastMod};
  93 use middle::region::{self, CodeExtent};
  94 use middle::subst::{self, Subst, Substs, VecPerParamSpace, ParamSpace, TypeSpace};
  95 use middle::traits::{self, report_fulfillment_errors};
  96 use middle::ty::{FnSig, GenericPredicates, TypeScheme};
  97 use middle::ty::{Disr, ParamTy, ParameterEnvironment};
  98 use middle::ty::{self, HasTypeFlags, RegionEscape, ToPolyTraitRef, Ty};
  99 use middle::ty::{MethodCall, MethodCallee};
 100 use middle::ty_fold::{TypeFolder, TypeFoldable};
 101 use require_c_abi_if_variadic;
 102 use rscope::{ElisionFailureInfo, RegionScope};
 103 use session::Session;
 104 use {CrateCtxt, lookup_full_def, require_same_types};
 105 use TypeAndSubsts;
 106 use lint;
 107 use util::common::{block_query, ErrorReported, indenter, loop_query};
 108 use util::nodemap::{DefIdMap, FnvHashMap, NodeMap};
 109 use util::lev_distance::lev_distance;
 110
 111 use std::cell::{Cell, Ref, RefCell};
 112 use std::collections::HashSet;
 113 use std::mem::replace;
 114 use std::slice;
 115 use syntax::{self, abi, attr};
 116 use syntax::attr::AttrMetaMethods;
 117 use syntax::ast::{self, DefId, Visibility};
 118 use syntax::ast_util::{self, local_def};
 119 use syntax::codemap::{self, Span};
 120 use syntax::feature_gate::emit_feature_err;
 121 use syntax::owned_slice::OwnedSlice;
 122 use syntax::parse::token;
 123 use syntax::print::pprust;
 124 use syntax::ptr::P;
 125 use syntax::visit::{self, Visitor};
 126
 127 mod assoc;
 128 pub mod dropck;
 129 pub mod _match;
 130 pub mod writeback;
 131 pub mod regionck;
 132 pub mod coercion;
 133 pub mod demand;
 134 pub mod method;
 135 mod upvar;
 136 pub mod wf;
 137 mod cast;
 138 mod closure;
 139 mod callee;
 140 mod compare_method;
 141 mod op;
 142
 143 /// closures defined within the function.  For example:
 144 ///
 145 ///     fn foo() {
 146 ///         bar(move|| { ... })
 147 ///     }
 148 ///
 149 /// Here, the function `foo()` and the closure passed to
 150 /// `bar()` will each have their own `FnCtxt`, but they will
 151 /// share the inherited fields.
 152 pub struct Inherited<'a, 'tcx: 'a> {
 153     infcx: infer::InferCtxt<'a, 'tcx>,
 154     locals: RefCell<NodeMap<Ty<'tcx>>>,
 155
 156     tables: &'a RefCell<ty::Tables<'tcx>>,
 157
 158     // A mapping from each fn's id to its signature, with all bound
 159     // regions replaced with free ones. Unlike the other tables, this
 160     // one is never copied into the tcx: it is only used by regionck.
 161     fn_sig_map: RefCell<NodeMap<Vec<Ty<'tcx>>>>,
 162
 163     // When we process a call like `c()` where `c` is a closure type,
 164     // we may not have decided yet whether `c` is a `Fn`, `FnMut`, or
 165     // `FnOnce` closure. In that case, we defer full resolution of the
 166     // call until upvar inference can kick in and make the
 167     // decision. We keep these deferred resolutions grouped by the
 168     // def-id of the closure, so that once we decide, we can easily go
 169     // back and process them.
 170     deferred_call_resolutions: RefCell<DefIdMap<Vec<DeferredCallResolutionHandler<'tcx>>>>,
 171
 172     deferred_cast_checks: RefCell<Vec<cast::CastCheck<'tcx>>>,
 173 }
 174
 175 trait DeferredCallResolution<'tcx> {
 176     fn resolve<'a>(&mut self, fcx: &FnCtxt<'a,'tcx>);
 177 }
 178
 179 type DeferredCallResolutionHandler<'tcx> = Box<DeferredCallResolution<'tcx>+'tcx>;
 180
 181 /// When type-checking an expression, we propagate downward
 182 /// whatever type hint we are able in the form of an `Expectation`.
 183 #[derive(Copy, Clone, Debug)]
 184 pub enum Expectation<'tcx> {
 185     /// We know nothing about what type this expression should have.
 186     NoExpectation,
 187
 188     /// This expression should have the type given (or some subtype)
 189     ExpectHasType(Ty<'tcx>),
 190
 191     /// This expression will be cast to the `Ty`
 192     ExpectCastableToType(Ty<'tcx>),
 193
 194     /// This rvalue expression will be wrapped in `&` or `Box` and coerced
 195     /// to `&Ty` or `Box<Ty>`, respectively. `Ty` is `[A]` or `Trait`.
 196     ExpectRvalueLikeUnsized(Ty<'tcx>),
 197 }
 198
 199 impl<'tcx> Expectation<'tcx> {
 200     // Disregard "castable to" expectations because they
 201     // can lead us astray. Consider for example `if cond
 202     // {22} else {c} as u8` -- if we propagate the
 203     // "castable to u8" constraint to 22, it will pick the
 204     // type 22u8, which is overly constrained (c might not
 205     // be a u8). In effect, the problem is that the
 206     // "castable to" expectation is not the tightest thing
 207     // we can say, so we want to drop it in this case.
 208     // The tightest thing we can say is "must unify with
 209     // else branch". Note that in the case of a "has type"
 210     // constraint, this limitation does not hold.
 211
 212     // If the expected type is just a type variable, then don't use
 213     // an expected type. Otherwise, we might write parts of the type
 214     // when checking the 'then' block which are incompatible with the
 215     // 'else' branch.
 216     fn adjust_for_branches<'a>(&self, fcx: &FnCtxt<'a, 'tcx>) -> Expectation<'tcx> {
 217         match *self {
 218             ExpectHasType(ety) => {
 219                 let ety = fcx.infcx().shallow_resolve(ety);
 220                 if !ety.is_ty_var() {
 221                     ExpectHasType(ety)
 222                 } else {
 223                     NoExpectation
 224                 }
 225             }
 226             ExpectRvalueLikeUnsized(ety) => {
 227                 ExpectRvalueLikeUnsized(ety)
 228             }
 229             _ => NoExpectation
 230         }
 231     }
 232 }
 233
 234 #[derive(Copy, Clone)]
 235 pub struct UnsafetyState {
 236     pub def: ast::NodeId,
 237     pub unsafety: ast::Unsafety,
 238     pub unsafe_push_count: u32,
 239     from_fn: bool
 240 }
 241
 242 impl UnsafetyState {
 243     pub fn function(unsafety: ast::Unsafety, def: ast::NodeId) -> UnsafetyState {
 244         UnsafetyState { def: def, unsafety: unsafety, unsafe_push_count: 0, from_fn: true }
 245     }
 246
 247     pub fn recurse(&mut self, blk: &ast::Block) -> UnsafetyState {
 248         match self.unsafety {
 249             // If this unsafe, then if the outer function was already marked as
 250             // unsafe we shouldn't attribute the unsafe'ness to the block. This
 251             // way the block can be warned about instead of ignoring this
 252             // extraneous block (functions are never warned about).
 253             ast::Unsafety::Unsafe if self.from_fn => *self,
 254
 255             unsafety => {
 256                 let (unsafety, def, count) = match blk.rules {
 257                     ast::PushUnsafeBlock(..) =>
 258                         (unsafety, blk.id, self.unsafe_push_count.checked_add(1).unwrap()),
 259                     ast::PopUnsafeBlock(..) =>
 260                         (unsafety, blk.id, self.unsafe_push_count.checked_sub(1).unwrap()),
 261                     ast::UnsafeBlock(..) =>
 262                         (ast::Unsafety::Unsafe, blk.id, self.unsafe_push_count),
 263                     ast::DefaultBlock =>
 264                         (unsafety, self.def, self.unsafe_push_count),
 265                 };
 266                 UnsafetyState{ def: def,
 267                                unsafety: unsafety,
 268                                unsafe_push_count: count,
 269                                from_fn: false }
 270             }
 271         }
 272     }
 273 }
 274
 275 #[derive(Clone)]
 276 pub struct FnCtxt<'a, 'tcx: 'a> {
 277     body_id: ast::NodeId,
 278
 279     // This flag is set to true if, during the writeback phase, we encounter
 280     // a type error in this function.
 281     writeback_errors: Cell<bool>,
 282
 283     // Number of errors that had been reported when we started
 284     // checking this function. On exit, if we find that *more* errors
 285     // have been reported, we will skip regionck and other work that
 286     // expects the types within the function to be consistent.
 287     err_count_on_creation: usize,
 288
 289     ret_ty: ty::FnOutput<'tcx>,
 290
 291     ps: RefCell<UnsafetyState>,
 292
 293     inh: &'a Inherited<'a, 'tcx>,
 294
 295     ccx: &'a CrateCtxt<'a, 'tcx>,
 296 }
 297
 298 impl<'a, 'tcx> Inherited<'a, 'tcx> {
 299     fn new(tcx: &'a ty::ctxt<'tcx>,
 300            tables: &'a RefCell<ty::Tables<'tcx>>,
 301            param_env: ty::ParameterEnvironment<'a, 'tcx>)
 302            -> Inherited<'a, 'tcx> {
 303
 304         Inherited {
 305             infcx: infer::new_infer_ctxt(tcx, tables, Some(param_env), true),
 306             locals: RefCell::new(NodeMap()),
 307             tables: tables,
 308             fn_sig_map: RefCell::new(NodeMap()),
 309             deferred_call_resolutions: RefCell::new(DefIdMap()),
 310             deferred_cast_checks: RefCell::new(Vec::new()),
 311         }
 312     }
 313
 314     fn normalize_associated_types_in<T>(&self,
 315                                         span: Span,
 316                                         body_id: ast::NodeId,
 317                                         value: &T)
 318                                         -> T
 319         where T : TypeFoldable<'tcx> + HasTypeFlags
 320     {
 321         let mut fulfillment_cx = self.infcx.fulfillment_cx.borrow_mut();
 322         assoc::normalize_associated_types_in(&self.infcx,
 323                                              &mut fulfillment_cx,
 324                                              span,
 325                                              body_id,
 326                                              value)
 327     }
 328
 329 }
 330
 331 // Used by check_const and check_enum_variants
 332 pub fn blank_fn_ctxt<'a, 'tcx>(ccx: &'a CrateCtxt<'a, 'tcx>,
 333                                inh: &'a Inherited<'a, 'tcx>,
 334                                rty: ty::FnOutput<'tcx>,
 335                                body_id: ast::NodeId)
 336                                -> FnCtxt<'a, 'tcx> {
 337     FnCtxt {
 338         body_id: body_id,
 339         writeback_errors: Cell::new(false),
 340         err_count_on_creation: ccx.tcx.sess.err_count(),
 341         ret_ty: rty,
 342         ps: RefCell::new(UnsafetyState::function(ast::Unsafety::Normal, 0)),
 343         inh: inh,
 344         ccx: ccx
 345     }
 346 }
 347
 348 fn static_inherited_fields<'a, 'tcx>(ccx: &'a CrateCtxt<'a, 'tcx>,
 349                                      tables: &'a RefCell<ty::Tables<'tcx>>)
 350                                     -> Inherited<'a, 'tcx> {
 351     // It's kind of a kludge to manufacture a fake function context
 352     // and statement context, but we might as well do write the code only once
 353     let param_env = ccx.tcx.empty_parameter_environment();
 354     Inherited::new(ccx.tcx, &tables, param_env)
 355 }
 356
 357 struct CheckItemTypesVisitor<'a, 'tcx: 'a> { ccx: &'a CrateCtxt<'a, 'tcx> }
 358 struct CheckItemBodiesVisitor<'a, 'tcx: 'a> { ccx: &'a CrateCtxt<'a, 'tcx> }
 359
 360 impl<'a, 'tcx> Visitor<'tcx> for CheckItemTypesVisitor<'a, 'tcx> {
 361     fn visit_item(&mut self, i: &'tcx ast::Item) {
 362         check_item_type(self.ccx, i);
 363         visit::walk_item(self, i);
 364     }
 365
 366     fn visit_ty(&mut self, t: &'tcx ast::Ty) {
 367         match t.node {
 368             ast::TyFixedLengthVec(_, ref expr) => {
 369                 check_const_in_type(self.ccx, &**expr, self.ccx.tcx.types.usize);
 370             }
 371             _ => {}
 372         }
 373
 374         visit::walk_ty(self, t);
 375     }
 376 }
 377
 378 impl<'a, 'tcx> Visitor<'tcx> for CheckItemBodiesVisitor<'a, 'tcx> {
 379     fn visit_item(&mut self, i: &'tcx ast::Item) {
 380         check_item_body(self.ccx, i);
 381         visit::walk_item(self, i);
 382     }
 383 }
 384
 385 pub fn check_item_types(ccx: &CrateCtxt) {
 386     let krate = ccx.tcx.map.krate();
 387     let mut visit = wf::CheckTypeWellFormedVisitor::new(ccx);
 388     visit::walk_crate(&mut visit, krate);
 389
 390     // If types are not well-formed, it leads to all manner of errors
 391     // downstream, so stop reporting errors at this point.
 392     ccx.tcx.sess.abort_if_errors();
 393
 394     let mut visit = CheckItemTypesVisitor { ccx: ccx };
 395     visit::walk_crate(&mut visit, krate);
 396
 397     ccx.tcx.sess.abort_if_errors();
 398
 399     let mut visit = CheckItemBodiesVisitor { ccx: ccx };
 400     visit::walk_crate(&mut visit, krate);
 401
 402     ccx.tcx.sess.abort_if_errors();
 403
 404     for drop_method_did in ccx.tcx.destructors.borrow().iter() {
 405         if drop_method_did.krate == ast::LOCAL_CRATE {
 406             let drop_impl_did = ccx.tcx.map.get_parent_did(drop_method_did.node);
 407             match dropck::check_drop_impl(ccx.tcx, drop_impl_did) {
 408                 Ok(()) => {}
 409                 Err(()) => {
 410                     assert!(ccx.tcx.sess.has_errors());
 411                 }
 412             }
 413         }
 414     }
 415
 416     ccx.tcx.sess.abort_if_errors();
 417 }
 418
 419 fn check_bare_fn<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 420                            decl: &'tcx ast::FnDecl,
 421                            body: &'tcx ast::Block,
 422                            fn_id: ast::NodeId,
 423                            fn_span: Span,
 424                            raw_fty: Ty<'tcx>,
 425                            param_env: ty::ParameterEnvironment<'a, 'tcx>)
 426 {
 427     match raw_fty.sty {
 428         ty::TyBareFn(_, ref fn_ty) => {
 429             let tables = RefCell::new(ty::Tables::empty());
 430             let inh = Inherited::new(ccx.tcx, &tables, param_env);
 431
 432             // Compute the fty from point of view of inside fn.
 433             let fn_sig =
 434                 fn_ty.sig.subst(ccx.tcx, &inh.infcx.parameter_environment.free_substs);
 435             let fn_sig =
 436                 ccx.tcx.liberate_late_bound_regions(region::DestructionScopeData::new(body.id),
 437                                                     &fn_sig);
 438             let fn_sig =
 439                 inh.normalize_associated_types_in(body.span,
 440                                                   body.id,
 441                                                   &fn_sig);
 442
 443             let fcx = check_fn(ccx, fn_ty.unsafety, fn_id, &fn_sig,
 444                                decl, fn_id, body, &inh);
 445
 446             fcx.select_all_obligations_and_apply_defaults();
 447             upvar::closure_analyze_fn(&fcx, fn_id, decl, body);
 448             fcx.select_all_obligations_or_error();
 449             fcx.check_casts();
 450
 451             fcx.select_all_obligations_or_error(); // Casts can introduce new obligations.
 452
 453             regionck::regionck_fn(&fcx, fn_id, fn_span, decl, body);
 454             writeback::resolve_type_vars_in_fn(&fcx, decl, body);
 455         }
 456         _ => ccx.tcx.sess.impossible_case(body.span,
 457                                  "check_bare_fn: function type expected")
 458     }
 459 }
 460
 461 struct GatherLocalsVisitor<'a, 'tcx: 'a> {
 462     fcx: &'a FnCtxt<'a, 'tcx>
 463 }
 464
 465 impl<'a, 'tcx> GatherLocalsVisitor<'a, 'tcx> {
 466     fn assign(&mut self, _span: Span, nid: ast::NodeId, ty_opt: Option<Ty<'tcx>>) -> Ty<'tcx> {
 467         match ty_opt {
 468             None => {
 469                 // infer the variable's type
 470                 let var_ty = self.fcx.infcx().next_ty_var();
 471                 self.fcx.inh.locals.borrow_mut().insert(nid, var_ty);
 472                 var_ty
 473             }
 474             Some(typ) => {
 475                 // take type that the user specified
 476                 self.fcx.inh.locals.borrow_mut().insert(nid, typ);
 477                 typ
 478             }
 479         }
 480     }
 481 }
 482
 483 impl<'a, 'tcx> Visitor<'tcx> for GatherLocalsVisitor<'a, 'tcx> {
 484     // Add explicitly-declared locals.
 485     fn visit_local(&mut self, local: &'tcx ast::Local) {
 486         let o_ty = match local.ty {
 487             Some(ref ty) => Some(self.fcx.to_ty(&**ty)),
 488             None => None
 489         };
 490         self.assign(local.span, local.id, o_ty);
 491         debug!("Local variable {:?} is assigned type {}",
 492                local.pat,
 493                self.fcx.infcx().ty_to_string(
 494                    self.fcx.inh.locals.borrow().get(&local.id).unwrap().clone()));
 495         visit::walk_local(self, local);
 496     }
 497
 498     // Add pattern bindings.
 499     fn visit_pat(&mut self, p: &'tcx ast::Pat) {
 500         if let ast::PatIdent(_, ref path1, _) = p.node {
 501             if pat_util::pat_is_binding(&self.fcx.ccx.tcx.def_map, p) {
 502                 let var_ty = self.assign(p.span, p.id, None);
 503
 504                 self.fcx.require_type_is_sized(var_ty, p.span,
 505                                                traits::VariableType(p.id));
 506
 507                 debug!("Pattern binding {} is assigned to {} with type {:?}",
 508                        token::get_ident(path1.node),
 509                        self.fcx.infcx().ty_to_string(
 510                            self.fcx.inh.locals.borrow().get(&p.id).unwrap().clone()),
 511                        var_ty);
 512             }
 513         }
 514         visit::walk_pat(self, p);
 515     }
 516
 517     fn visit_block(&mut self, b: &'tcx ast::Block) {
 518         // non-obvious: the `blk` variable maps to region lb, so
 519         // we have to keep this up-to-date.  This
 520         // is... unfortunate.  It'd be nice to not need this.
 521         visit::walk_block(self, b);
 522     }
 523
 524     // Since an expr occurs as part of the type fixed size arrays we
 525     // need to record the type for that node
 526     fn visit_ty(&mut self, t: &'tcx ast::Ty) {
 527         match t.node {
 528             ast::TyFixedLengthVec(ref ty, ref count_expr) => {
 529                 self.visit_ty(&**ty);
 530                 check_expr_with_hint(self.fcx, &**count_expr, self.fcx.tcx().types.usize);
 531             }
 532             _ => visit::walk_ty(self, t)
 533         }
 534     }
 535
 536     // Don't descend into fns and items
 537     fn visit_fn(&mut self, _: visit::FnKind<'tcx>, _: &'tcx ast::FnDecl,
 538                 _: &'tcx ast::Block, _: Span, _: ast::NodeId) { }
 539     fn visit_item(&mut self, _: &ast::Item) { }
 540
 541 }
 542
 543 /// Helper used by check_bare_fn and check_expr_fn. Does the grungy work of checking a function
 544 /// body and returns the function context used for that purpose, since in the case of a fn item
 545 /// there is still a bit more to do.
 546 ///
 547 /// * ...
 548 /// * inherited: other fields inherited from the enclosing fn (if any)
 549 fn check_fn<'a, 'tcx>(ccx: &'a CrateCtxt<'a, 'tcx>,
 550                       unsafety: ast::Unsafety,
 551                       unsafety_id: ast::NodeId,
 552                       fn_sig: &ty::FnSig<'tcx>,
 553                       decl: &'tcx ast::FnDecl,
 554                       fn_id: ast::NodeId,
 555                       body: &'tcx ast::Block,
 556                       inherited: &'a Inherited<'a, 'tcx>)
 557                       -> FnCtxt<'a, 'tcx>
 558 {
 559     let tcx = ccx.tcx;
 560     let err_count_on_creation = tcx.sess.err_count();
 561
 562     let arg_tys = &fn_sig.inputs;
 563     let ret_ty = fn_sig.output;
 564
 565     debug!("check_fn(arg_tys={:?}, ret_ty={:?}, fn_id={})",
 566            arg_tys,
 567            ret_ty,
 568            fn_id);
 569
 570     // Create the function context.  This is either derived from scratch or,
 571     // in the case of function expressions, based on the outer context.
 572     let fcx = FnCtxt {
 573         body_id: body.id,
 574         writeback_errors: Cell::new(false),
 575         err_count_on_creation: err_count_on_creation,
 576         ret_ty: ret_ty,
 577         ps: RefCell::new(UnsafetyState::function(unsafety, unsafety_id)),
 578         inh: inherited,
 579         ccx: ccx
 580     };
 581
 582     // Remember return type so that regionck can access it later.
 583     let mut fn_sig_tys: Vec<Ty> =
 584         arg_tys.iter()
 585         .cloned()
 586         .collect();
 587
 588     if let ty::FnConverging(ret_ty) = ret_ty {
 589         fcx.require_type_is_sized(ret_ty, decl.output.span(), traits::ReturnType);
 590         fn_sig_tys.push(ret_ty);
 591     }
 592
 593     debug!("fn-sig-map: fn_id={} fn_sig_tys={:?}",
 594            fn_id,
 595            fn_sig_tys);
 596
 597     inherited.fn_sig_map.borrow_mut().insert(fn_id, fn_sig_tys);
 598
 599     {
 600         let mut visit = GatherLocalsVisitor { fcx: &fcx, };
 601
 602         // Add formal parameters.
 603         for (arg_ty, input) in arg_tys.iter().zip(&decl.inputs) {
 604             // Create type variables for each argument.
 605             pat_util::pat_bindings(
 606                 &tcx.def_map,
 607                 &*input.pat,
 608                 |_bm, pat_id, sp, _path| {
 609                     let var_ty = visit.assign(sp, pat_id, None);
 610                     fcx.require_type_is_sized(var_ty, sp,
 611                                               traits::VariableType(pat_id));
 612                 });
 613
 614             // Check the pattern.
 615             let pcx = pat_ctxt {
 616                 fcx: &fcx,
 617                 map: pat_id_map(&tcx.def_map, &*input.pat),
 618             };
 619             _match::check_pat(&pcx, &*input.pat, *arg_ty);
 620         }
 621
 622         visit.visit_block(body);
 623     }
 624
 625     check_block_with_expected(&fcx, body, match ret_ty {
 626         ty::FnConverging(result_type) => ExpectHasType(result_type),
 627         ty::FnDiverging => NoExpectation
 628     });
 629
 630     for (input, arg) in decl.inputs.iter().zip(arg_tys) {
 631         fcx.write_ty(input.id, arg);
 632     }
 633
 634     fcx
 635 }
 636
 637 pub fn check_struct(ccx: &CrateCtxt, id: ast::NodeId, span: Span) {
 638     let tcx = ccx.tcx;
 639
 640     check_representable(tcx, span, id, "struct");
 641     check_instantiable(tcx, span, id);
 642
 643     if tcx.lookup_simd(local_def(id)) {
 644         check_simd(tcx, span, id);
 645     }
 646 }
 647
 648 pub fn check_item_type<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx ast::Item) {
 649     debug!("check_item_type(it.id={}, it.ident={})",
 650            it.id,
 651            ccx.tcx.item_path_str(local_def(it.id)));
 652     let _indenter = indenter();
 653     match it.node {
 654       // Consts can play a role in type-checking, so they are included here.
 655       ast::ItemStatic(_, _, ref e) |
 656       ast::ItemConst(_, ref e) => check_const(ccx, it.span, &**e, it.id),
 657       ast::ItemEnum(ref enum_definition, _) => {
 658         check_enum_variants(ccx,
 659                             it.span,
 660                             &enum_definition.variants,
 661                             it.id);
 662       }
 663       ast::ItemFn(..) => {} // entirely within check_item_body
 664       ast::ItemImpl(_, _, _, _, _, ref impl_items) => {
 665           debug!("ItemImpl {} with id {}", token::get_ident(it.ident), it.id);
 666           match ccx.tcx.impl_trait_ref(local_def(it.id)) {
 667               Some(impl_trait_ref) => {
 668                 check_impl_items_against_trait(ccx,
 669                                                it.span,
 670                                                &impl_trait_ref,
 671                                                impl_items);
 672               }
 673               None => { }
 674           }
 675       }
 676       ast::ItemTrait(_, ref generics, _, _) => {
 677         check_trait_on_unimplemented(ccx, generics, it);
 678       }
 679       ast::ItemStruct(..) => {
 680         check_struct(ccx, it.id, it.span);
 681       }
 682       ast::ItemTy(ref t, ref generics) => {
 683         let pty_ty = ccx.tcx.node_id_to_type(it.id);
 684         check_bounds_are_used(ccx, t.span, &generics.ty_params, pty_ty);
 685       }
 686       ast::ItemForeignMod(ref m) => {
 687         if m.abi == abi::RustIntrinsic {
 688             for item in &m.items {
 689                 check_intrinsic_type(ccx, &**item);
 690             }
 691         } else {
 692             for item in &m.items {
 693                 let pty = ccx.tcx.lookup_item_type(local_def(item.id));
 694                 if !pty.generics.types.is_empty() {
 695                     span_err!(ccx.tcx.sess, item.span, E0044,
 696                         "foreign items may not have type parameters");
 697                 }
 698
 699                 if let ast::ForeignItemFn(ref fn_decl, _) = item.node {
 700                     require_c_abi_if_variadic(ccx.tcx, fn_decl, m.abi, item.span);
 701                 }
 702             }
 703         }
 704       }
 705       _ => {/* nothing to do */ }
 706     }
 707 }
 708
 709 pub fn check_item_body<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx ast::Item) {
 710     debug!("check_item_body(it.id={}, it.ident={})",
 711            it.id,
 712            ccx.tcx.item_path_str(local_def(it.id)));
 713     let _indenter = indenter();
 714     match it.node {
 715       ast::ItemFn(ref decl, _, _, _, _, ref body) => {
 716         let fn_pty = ccx.tcx.lookup_item_type(ast_util::local_def(it.id));
 717         let param_env = ParameterEnvironment::for_item(ccx.tcx, it.id);
 718         check_bare_fn(ccx, &**decl, &**body, it.id, it.span, fn_pty.ty, param_env);
 719       }
 720       ast::ItemImpl(_, _, _, _, _, ref impl_items) => {
 721         debug!("ItemImpl {} with id {}", token::get_ident(it.ident), it.id);
 722
 723         let impl_pty = ccx.tcx.lookup_item_type(ast_util::local_def(it.id));
 724
 725         for impl_item in impl_items {
 726             match impl_item.node {
 727                 ast::ConstImplItem(_, ref expr) => {
 728                     check_const(ccx, impl_item.span, &*expr, impl_item.id)
 729                 }
 730                 ast::MethodImplItem(ref sig, ref body) => {
 731                     check_method_body(ccx, &impl_pty.generics, sig, body,
 732                                       impl_item.id, impl_item.span);
 733                 }
 734                 ast::TypeImplItem(_) |
 735                 ast::MacImplItem(_) => {
 736                     // Nothing to do here.
 737                 }
 738             }
 739         }
 740       }
 741       ast::ItemTrait(_, _, _, ref trait_items) => {
 742         let trait_def = ccx.tcx.lookup_trait_def(local_def(it.id));
 743         for trait_item in trait_items {
 744             match trait_item.node {
 745                 ast::ConstTraitItem(_, Some(ref expr)) => {
 746                     check_const(ccx, trait_item.span, &*expr, trait_item.id)
 747                 }
 748                 ast::MethodTraitItem(ref sig, Some(ref body)) => {
 749                     check_trait_fn_not_const(ccx, trait_item.span, sig.constness);
 750
 751                     check_method_body(ccx, &trait_def.generics, sig, body,
 752                                       trait_item.id, trait_item.span);
 753                 }
 754                 ast::MethodTraitItem(ref sig, None) => {
 755                     check_trait_fn_not_const(ccx, trait_item.span, sig.constness);
 756                 }
 757                 ast::ConstTraitItem(_, None) |
 758                 ast::TypeTraitItem(..) => {
 759                     // Nothing to do.
 760                 }
 761             }
 762         }
 763       }
 764       _ => {/* nothing to do */ }
 765     }
 766 }
 767
 768 fn check_trait_fn_not_const<'a,'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 769                                      span: Span,
 770                                      constness: ast::Constness)
 771 {
 772     match constness {
 773         ast::Constness::NotConst => {
 774             // good
 775         }
 776         ast::Constness::Const => {
 777             span_err!(ccx.tcx.sess, span, E0379, "trait fns cannot be declared const");
 778         }
 779     }
 780 }
 781
 782 fn check_trait_on_unimplemented<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 783                                generics: &ast::Generics,
 784                                item: &ast::Item) {
 785     if let Some(ref attr) = item.attrs.iter().find(|a| {
 786         a.check_name("rustc_on_unimplemented")
 787     }) {
 788         if let Some(ref istring) = attr.value_str() {
 789             let parser = Parser::new(&istring);
 790             let types = &*generics.ty_params;
 791             for token in parser {
 792                 match token {
 793                     Piece::String(_) => (), // Normal string, no need to check it
 794                     Piece::NextArgument(a) => match a.position {
 795                         // `{Self}` is allowed
 796                         Position::ArgumentNamed(s) if s == "Self" => (),
 797                         // So is `{A}` if A is a type parameter
 798                         Position::ArgumentNamed(s) => match types.iter().find(|t| {
 799                             t.ident.as_str() == s
 800                         }) {
 801                             Some(_) => (),
 802                             None => {
 803                                 span_err!(ccx.tcx.sess, attr.span, E0230,
 804                                                  "there is no type parameter \
 805                                                           {} on trait {}",
 806                                                            s, item.ident.as_str());
 807                             }
 808                         },
 809                         // `{:1}` and `{}` are not to be used
 810                         Position::ArgumentIs(_) | Position::ArgumentNext => {
 811                             span_err!(ccx.tcx.sess, attr.span, E0231,
 812                                                   "only named substitution \
 813                                                    parameters are allowed");
 814                         }
 815                     }
 816                 }
 817             }
 818         } else {
 819             span_err!(ccx.tcx.sess, attr.span, E0232,
 820                                   "this attribute must have a value, \
 821                                    eg `#[rustc_on_unimplemented = \"foo\"]`")
 822         }
 823     }
 824 }
 825
 826 /// Type checks a method body.
 827 ///
 828 /// # Parameters
 829 ///
 830 /// * `item_generics`: generics defined on the impl/trait that contains
 831 ///   the method
 832 /// * `self_bound`: bound for the `Self` type parameter, if any
 833 /// * `method`: the method definition
 834 fn check_method_body<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 835                                item_generics: &ty::Generics<'tcx>,
 836                                sig: &'tcx ast::MethodSig,
 837                                body: &'tcx ast::Block,
 838                                id: ast::NodeId, span: Span) {
 839     debug!("check_method_body(item_generics={:?}, id={})",
 840             item_generics, id);
 841     let param_env = ParameterEnvironment::for_item(ccx.tcx, id);
 842
 843     let fty = ccx.tcx.node_id_to_type(id);
 844     debug!("check_method_body: fty={:?}", fty);
 845
 846     check_bare_fn(ccx, &sig.decl, body, id, span, fty, param_env);
 847 }
 848
 849 fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 850                                             impl_span: Span,
 851                                             impl_trait_ref: &ty::TraitRef<'tcx>,
 852                                             impl_items: &[P<ast::ImplItem>]) {
 853     // Locate trait methods
 854     let tcx = ccx.tcx;
 855     let trait_items = tcx.trait_items(impl_trait_ref.def_id);
 856     let mut overridden_associated_type = None;
 857
 858     // Check existing impl methods to see if they are both present in trait
 859     // and compatible with trait signature
 860     for impl_item in impl_items {
 861         let ty_impl_item = ccx.tcx.impl_or_trait_item(local_def(impl_item.id));
 862         let ty_trait_item = trait_items.iter()
 863             .find(|ac| ac.name() == ty_impl_item.name())
 864             .unwrap_or_else(|| {
 865                 // This is checked by resolve
 866                 tcx.sess.span_bug(impl_item.span,
 867                                   &format!("impl-item `{}` is not a member of `{:?}`",
 868                                            token::get_name(ty_impl_item.name()),
 869                                            impl_trait_ref));
 870             });
 871         match impl_item.node {
 872             ast::ConstImplItem(..) => {
 873                 let impl_const = match ty_impl_item {
 874                     ty::ConstTraitItem(ref cti) => cti,
 875                     _ => tcx.sess.span_bug(impl_item.span, "non-const impl-item for const")
 876                 };
 877
 878                 // Find associated const definition.
 879                 if let &ty::ConstTraitItem(ref trait_const) = ty_trait_item {
 880                     compare_const_impl(ccx.tcx,
 881                                        &impl_const,
 882                                        impl_item.span,
 883                                        trait_const,
 884                                        &*impl_trait_ref);
 885                 } else {
 886                     span_err!(tcx.sess, impl_item.span, E0323,
 887                               "item `{}` is an associated const, \
 888                               which doesn't match its trait `{:?}`",
 889                               token::get_name(impl_const.name),
 890                               impl_trait_ref)
 891                 }
 892             }
 893             ast::MethodImplItem(ref sig, ref body) => {
 894                 check_trait_fn_not_const(ccx, impl_item.span, sig.constness);
 895
 896                 let impl_method = match ty_impl_item {
 897                     ty::MethodTraitItem(ref mti) => mti,
 898                     _ => tcx.sess.span_bug(impl_item.span, "non-method impl-item for method")
 899                 };
 900
 901                 if let &ty::MethodTraitItem(ref trait_method) = ty_trait_item {
 902                     compare_impl_method(ccx.tcx,
 903                                         &impl_method,
 904                                         impl_item.span,
 905                                         body.id,
 906                                         &trait_method,
 907                                         &impl_trait_ref);
 908                 } else {
 909                     span_err!(tcx.sess, impl_item.span, E0324,
 910                               "item `{}` is an associated method, \
 911                               which doesn't match its trait `{:?}`",
 912                               token::get_name(impl_method.name),
 913                               impl_trait_ref)
 914                 }
 915             }
 916             ast::TypeImplItem(_) => {
 917                 let impl_type = match ty_impl_item {
 918                     ty::TypeTraitItem(ref tti) => tti,
 919                     _ => tcx.sess.span_bug(impl_item.span, "non-type impl-item for type")
 920                 };
 921
 922                 if let &ty::TypeTraitItem(ref at) = ty_trait_item {
 923                     if let Some(_) = at.ty {
 924                         overridden_associated_type = Some(impl_item);
 925                     }
 926                 } else {
 927                     span_err!(tcx.sess, impl_item.span, E0325,
 928                               "item `{}` is an associated type, \
 929                               which doesn't match its trait `{:?}`",
 930                               token::get_name(impl_type.name),
 931                               impl_trait_ref)
 932                 }
 933             }
 934             ast::MacImplItem(_) => tcx.sess.span_bug(impl_item.span,
 935                                                      "unexpanded macro")
 936         }
 937     }
 938
 939     // Check for missing items from trait
 940     let provided_methods = tcx.provided_trait_methods(impl_trait_ref.def_id);
 941     let associated_consts = tcx.associated_consts(impl_trait_ref.def_id);
 942     let mut missing_items = Vec::new();
 943     let mut invalidated_items = Vec::new();
 944     let associated_type_overridden = overridden_associated_type.is_some();
 945     for trait_item in trait_items.iter() {
 946         match *trait_item {
 947             ty::ConstTraitItem(ref associated_const) => {
 948                 let is_implemented = impl_items.iter().any(|ii| {
 949                     match ii.node {
 950                         ast::ConstImplItem(..) => {
 951                             ii.ident.name == associated_const.name
 952                         }
 953                         _ => false,
 954                     }
 955                 });
 956                 let is_provided =
 957                     associated_consts.iter().any(|ac| ac.default.is_some() &&
 958                                                  ac.name == associated_const.name);
 959                 if !is_implemented {
 960                     if !is_provided {
 961                         missing_items.push(associated_const.name);
 962                     } else if associated_type_overridden {
 963                         invalidated_items.push(associated_const.name);
 964                     }
 965                 }
 966             }
 967             ty::MethodTraitItem(ref trait_method) => {
 968                 let is_implemented =
 969                     impl_items.iter().any(|ii| {
 970                         match ii.node {
 971                             ast::MethodImplItem(..) => {
 972                                 ii.ident.name == trait_method.name
 973                             }
 974                             _ => false,
 975                         }
 976                     });
 977                 let is_provided =
 978                     provided_methods.iter().any(|m| m.name == trait_method.name);
 979                 if !is_implemented {
 980                     if !is_provided {
 981                         missing_items.push(trait_method.name);
 982                     } else if associated_type_overridden {
 983                         invalidated_items.push(trait_method.name);
 984                     }
 985                 }
 986             }
 987             ty::TypeTraitItem(ref associated_type) => {
 988                 let is_implemented = impl_items.iter().any(|ii| {
 989                     match ii.node {
 990                         ast::TypeImplItem(_) => {
 991                             ii.ident.name == associated_type.name
 992                         }
 993                         _ => false,
 994                     }
 995                 });
 996                 let is_provided = associated_type.ty.is_some();
 997                 if !is_implemented {
 998                     if !is_provided {
 999                         missing_items.push(associated_type.name);
1000                     } else if associated_type_overridden {
1001                         invalidated_items.push(associated_type.name);
1002                     }
1003                 }
1004             }
1005         }
1006     }
1007
1008     if !missing_items.is_empty() {
1009         span_err!(tcx.sess, impl_span, E0046,
1010             "not all trait items implemented, missing: `{}`",
1011             missing_items.iter()
1012                   .map(<ast::Name>::as_str)
1013                   .collect::<Vec<_>>().join("`, `"))
1014     }
1015
1016     if !invalidated_items.is_empty() {
1017         let invalidator = overridden_associated_type.unwrap();
1018         span_err!(tcx.sess, invalidator.span, E0399,
1019                   "the following trait items need to be reimplemented \
1020                    as `{}` was overridden: `{}`",
1021                   invalidator.ident.as_str(),
1022                   invalidated_items.iter()
1023                                    .map(<ast::Name>::as_str)
1024                                    .collect::<Vec<_>>().join("`, `"))
1025     }
1026 }
1027
1028 fn report_cast_to_unsized_type<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
1029                                          span: Span,
1030                                          t_span: Span,
1031                                          e_span: Span,
1032                                          t_cast: Ty<'tcx>,
1033                                          t_expr: Ty<'tcx>,
1034                                          id: ast::NodeId) {
1035     let tstr = fcx.infcx().ty_to_string(t_cast);
1036     fcx.type_error_message(span, |actual| {
1037         format!("cast to unsized type: `{}` as `{}`", actual, tstr)
1038     }, t_expr, None);
1039     match t_expr.sty {
1040         ty::TyRef(_, ty::TypeAndMut { mutbl: mt, .. }) => {
1041             let mtstr = match mt {
1042                 ast::MutMutable => "mut ",
1043                 ast::MutImmutable => ""
1044             };
1045             if t_cast.is_trait() {
1046                 match fcx.tcx().sess.codemap().span_to_snippet(t_span) {
1047                     Ok(s) => {
1048                         fcx.tcx().sess.span_suggestion(t_span,
1049                                                        "try casting to a reference instead:",
1050                                                        format!("&{}{}", mtstr, s));
1051                     },
1052                     Err(_) =>
1053                         span_help!(fcx.tcx().sess, t_span,
1054                                    "did you mean `&{}{}`?", mtstr, tstr),
1055                 }
1056             } else {
1057                 span_help!(fcx.tcx().sess, span,
1058                            "consider using an implicit coercion to `&{}{}` instead",
1059                            mtstr, tstr);
1060             }
1061         }
1062         ty::TyBox(..) => {
1063             match fcx.tcx().sess.codemap().span_to_snippet(t_span) {
1064                 Ok(s) => {
1065                     fcx.tcx().sess.span_suggestion(t_span,
1066                                                    "try casting to a `Box` instead:",
1067                                                    format!("Box<{}>", s));
1068                 },
1069                 Err(_) =>
1070                     span_help!(fcx.tcx().sess, t_span, "did you mean `Box<{}>`?", tstr),
1071             }
1072         }
1073         _ => {
1074             span_help!(fcx.tcx().sess, e_span,
1075                        "consider using a box or reference as appropriate");
1076         }
1077     }
1078     fcx.write_error(id);
1079 }
1080
1081
1082 impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> {
1083     fn tcx(&self) -> &ty::ctxt<'tcx> { self.ccx.tcx }
1084
1085     fn get_item_type_scheme(&self, _: Span, id: ast::DefId)
1086                             -> Result<ty::TypeScheme<'tcx>, ErrorReported>
1087     {
1088         Ok(self.tcx().lookup_item_type(id))
1089     }
1090
1091     fn get_trait_def(&self, _: Span, id: ast::DefId)
1092                      -> Result<&'tcx ty::TraitDef<'tcx>, ErrorReported>
1093     {
1094         Ok(self.tcx().lookup_trait_def(id))
1095     }
1096
1097     fn ensure_super_predicates(&self, _: Span, _: ast::DefId) -> Result<(), ErrorReported> {
1098         // all super predicates are ensured during collect pass
1099         Ok(())
1100     }
1101
1102     fn get_free_substs(&self) -> Option<&Substs<'tcx>> {
1103         Some(&self.inh.infcx.parameter_environment.free_substs)
1104     }
1105
1106     fn get_type_parameter_bounds(&self,
1107                                  _: Span,
1108                                  node_id: ast::NodeId)
1109                                  -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>
1110     {
1111         let def = self.tcx().type_parameter_def(node_id);
1112         let r = self.inh.infcx.parameter_environment
1113                                   .caller_bounds
1114                                   .iter()
1115                                   .filter_map(|predicate| {
1116                                       match *predicate {
1117                                           ty::Predicate::Trait(ref data) => {
1118                                               if data.0.self_ty().is_param(def.space, def.index) {
1119                                                   Some(data.to_poly_trait_ref())
1120                                               } else {
1121                                                   None
1122                                               }
1123                                           }
1124                                           _ => {
1125                                               None
1126                                           }
1127                                       }
1128                                   })
1129                                   .collect();
1130         Ok(r)
1131     }
1132
1133     fn trait_defines_associated_type_named(&self,
1134                                            trait_def_id: ast::DefId,
1135                                            assoc_name: ast::Name)
1136                                            -> bool
1137     {
1138         let trait_def = self.ccx.tcx.lookup_trait_def(trait_def_id);
1139         trait_def.associated_type_names.contains(&assoc_name)
1140     }
1141
1142     fn ty_infer(&self, ty_param_def: Option<ty::TypeParameterDef<'tcx>>, span: Span) -> Ty<'tcx> {
1143         let default = ty_param_def.and_then(|t|
1144             t.default.map(|ty| type_variable::Default { ty: ty, origin_span: span, definition_span: span }));
1145         self.infcx().next_ty_var_with_default(default)
1146     }
1147
1148     fn projected_ty_from_poly_trait_ref(&self,
1149                                         span: Span,
1150                                         poly_trait_ref: ty::PolyTraitRef<'tcx>,
1151                                         item_name: ast::Name)
1152                                         -> Ty<'tcx>
1153     {
1154         let (trait_ref, _) =
1155             self.infcx().replace_late_bound_regions_with_fresh_var(
1156                 span,
1157                 infer::LateBoundRegionConversionTime::AssocTypeProjection(item_name),
1158                 &poly_trait_ref);
1159
1160         self.normalize_associated_type(span, trait_ref, item_name)
1161     }
1162
1163     fn projected_ty(&self,
1164                     span: Span,
1165                     trait_ref: ty::TraitRef<'tcx>,
1166                     item_name: ast::Name)
1167                     -> Ty<'tcx>
1168     {
1169         self.normalize_associated_type(span, trait_ref, item_name)
1170     }
1171 }
1172
1173 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
1174     fn tcx(&self) -> &ty::ctxt<'tcx> { self.ccx.tcx }
1175
1176     pub fn infcx(&self) -> &infer::InferCtxt<'a,'tcx> {
1177         &self.inh.infcx
1178     }
1179
1180     pub fn param_env(&self) -> &ty::ParameterEnvironment<'a,'tcx> {
1181         &self.inh.infcx.parameter_environment
1182     }
1183
1184     pub fn sess(&self) -> &Session {
1185         &self.tcx().sess
1186     }
1187
1188     pub fn err_count_since_creation(&self) -> usize {
1189         self.ccx.tcx.sess.err_count() - self.err_count_on_creation
1190     }
1191
1192     /// Resolves type variables in `ty` if possible. Unlike the infcx
1193     /// version, this version will also select obligations if it seems
1194     /// useful, in an effort to get more type information.
1195     fn resolve_type_vars_if_possible(&self, mut ty: Ty<'tcx>) -> Ty<'tcx> {
1196         debug!("resolve_type_vars_if_possible(ty={:?})", ty);
1197
1198         // No TyInfer()? Nothing needs doing.
1199         if !ty.has_infer_types() {
1200             debug!("resolve_type_vars_if_possible: ty={:?}", ty);
1201             return ty;
1202         }
1203
1204         // If `ty` is a type variable, see whether we already know what it is.
1205         ty = self.infcx().resolve_type_vars_if_possible(&ty);
1206         if !ty.has_infer_types() {
1207             debug!("resolve_type_vars_if_possible: ty={:?}", ty);
1208             return ty;
1209         }
1210
1211         // If not, try resolving any new fcx obligations that have cropped up.
1212         self.select_new_obligations();
1213         ty = self.infcx().resolve_type_vars_if_possible(&ty);
1214         if !ty.has_infer_types() {
1215             debug!("resolve_type_vars_if_possible: ty={:?}", ty);
1216             return ty;
1217         }
1218
1219         // If not, try resolving *all* pending obligations as much as
1220         // possible. This can help substantially when there are
1221         // indirect dependencies that don't seem worth tracking
1222         // precisely.
1223         self.select_obligations_where_possible();
1224         ty = self.infcx().resolve_type_vars_if_possible(&ty);
1225
1226         debug!("resolve_type_vars_if_possible: ty={:?}", ty);
1227         ty
1228     }
1229
1230     fn record_deferred_call_resolution(&self,
1231                                        closure_def_id: ast::DefId,
1232                                        r: DeferredCallResolutionHandler<'tcx>) {
1233         let mut deferred_call_resolutions = self.inh.deferred_call_resolutions.borrow_mut();
1234         deferred_call_resolutions.entry(closure_def_id).or_insert(vec![]).push(r);
1235     }
1236
1237     fn remove_deferred_call_resolutions(&self,
1238                                         closure_def_id: ast::DefId)
1239                                         -> Vec<DeferredCallResolutionHandler<'tcx>>
1240     {
1241         let mut deferred_call_resolutions = self.inh.deferred_call_resolutions.borrow_mut();
1242         deferred_call_resolutions.remove(&closure_def_id).unwrap_or(Vec::new())
1243     }
1244
1245     pub fn tag(&self) -> String {
1246         let self_ptr: *const FnCtxt = self;
1247         format!("{:?}", self_ptr)
1248     }
1249
1250     pub fn local_ty(&self, span: Span, nid: ast::NodeId) -> Ty<'tcx> {
1251         match self.inh.locals.borrow().get(&nid) {
1252             Some(&t) => t,
1253             None => {
1254                 self.tcx().sess.span_err(
1255                     span,
1256                     &format!("no type for local variable {}", nid));
1257                 self.tcx().types.err
1258             }
1259         }
1260     }
1261
1262     #[inline]
1263     pub fn write_ty(&self, node_id: ast::NodeId, ty: Ty<'tcx>) {
1264         debug!("write_ty({}, {:?}) in fcx {}",
1265                node_id, ty, self.tag());
1266         self.inh.tables.borrow_mut().node_types.insert(node_id, ty);
1267     }
1268
1269     pub fn write_substs(&self, node_id: ast::NodeId, substs: ty::ItemSubsts<'tcx>) {
1270         if !substs.substs.is_noop() {
1271             debug!("write_substs({}, {:?}) in fcx {}",
1272                    node_id,
1273                    substs,
1274                    self.tag());
1275
1276             self.inh.tables.borrow_mut().item_substs.insert(node_id, substs);
1277         }
1278     }
1279
1280     pub fn write_autoderef_adjustment(&self,
1281                                       node_id: ast::NodeId,
1282                                       derefs: usize) {
1283         self.write_adjustment(
1284             node_id,
1285             ty::AdjustDerefRef(ty::AutoDerefRef {
1286                 autoderefs: derefs,
1287                 autoref: None,
1288                 unsize: None
1289             })
1290         );
1291     }
1292
1293     pub fn write_adjustment(&self,
1294                             node_id: ast::NodeId,
1295                             adj: ty::AutoAdjustment<'tcx>) {
1296         debug!("write_adjustment(node_id={}, adj={:?})", node_id, adj);
1297
1298         if adj.is_identity() {
1299             return;
1300         }
1301
1302         self.inh.tables.borrow_mut().adjustments.insert(node_id, adj);
1303     }
1304
1305     /// Basically whenever we are converting from a type scheme into
1306     /// the fn body space, we always want to normalize associated
1307     /// types as well. This function combines the two.
1308     fn instantiate_type_scheme<T>(&self,
1309                                   span: Span,
1310                                   substs: &Substs<'tcx>,
1311                                   value: &T)
1312                                   -> T
1313         where T : TypeFoldable<'tcx> + HasTypeFlags
1314     {
1315         let value = value.subst(self.tcx(), substs);
1316         let result = self.normalize_associated_types_in(span, &value);
1317         debug!("instantiate_type_scheme(value={:?}, substs={:?}) = {:?}",
1318                value,
1319                substs,
1320                result);
1321         result
1322     }
1323
1324     /// As `instantiate_type_scheme`, but for the bounds found in a
1325     /// generic type scheme.
1326     fn instantiate_bounds(&self,
1327                           span: Span,
1328                           substs: &Substs<'tcx>,
1329                           bounds: &ty::GenericPredicates<'tcx>)
1330                           -> ty::InstantiatedPredicates<'tcx>
1331     {
1332         ty::InstantiatedPredicates {
1333             predicates: self.instantiate_type_scheme(span, substs, &bounds.predicates)
1334         }
1335     }
1336
1337
1338     fn normalize_associated_types_in<T>(&self, span: Span, value: &T) -> T
1339         where T : TypeFoldable<'tcx> + HasTypeFlags
1340     {
1341         self.inh.normalize_associated_types_in(span, self.body_id, value)
1342     }
1343
1344     fn normalize_associated_type(&self,
1345                                  span: Span,
1346                                  trait_ref: ty::TraitRef<'tcx>,
1347                                  item_name: ast::Name)
1348                                  -> Ty<'tcx>
1349     {
1350         let cause = traits::ObligationCause::new(span,
1351                                                  self.body_id,
1352                                                  traits::ObligationCauseCode::MiscObligation);
1353         self.inh
1354             .infcx
1355             .fulfillment_cx
1356             .borrow_mut()
1357             .normalize_projection_type(self.infcx(),
1358                                        ty::ProjectionTy {
1359                                            trait_ref: trait_ref,
1360                                            item_name: item_name,
1361                                        },
1362                                        cause)
1363     }
1364
1365     /// Returns the type of `def_id` with all generics replaced by by fresh type/region variables.
1366     /// Also returns the substitution from the type parameters on `def_id` to the fresh variables.
1367     /// Registers any trait obligations specified on `def_id` at the same time.
1368     ///
1369     /// Note that function is only intended to be used with types (notably, not fns). This is
1370     /// because it doesn't do any instantiation of late-bound regions.
1371     pub fn instantiate_type(&self,
1372                             span: Span,
1373                             def_id: ast::DefId)
1374                             -> TypeAndSubsts<'tcx>
1375     {
1376         let type_scheme =
1377             self.tcx().lookup_item_type(def_id);
1378         let type_predicates =
1379             self.tcx().lookup_predicates(def_id);
1380         let substs =
1381             self.infcx().fresh_substs_for_generics(
1382                 span,
1383                 &type_scheme.generics);
1384         let bounds =
1385             self.instantiate_bounds(span, &substs, &type_predicates);
1386         self.add_obligations_for_parameters(
1387             traits::ObligationCause::new(
1388                 span,
1389                 self.body_id,
1390                 traits::ItemObligation(def_id)),
1391             &bounds);
1392         let monotype =
1393             self.instantiate_type_scheme(span, &substs, &type_scheme.ty);
1394
1395         TypeAndSubsts {
1396             ty: monotype,
1397             substs: substs
1398         }
1399     }
1400
1401     /// Returns the type that this AST path refers to. If the path has no type
1402     /// parameters and the corresponding type has type parameters, fresh type
1403     /// and/or region variables are substituted.
1404     ///
1405     /// This is used when checking the constructor in struct literals.
1406     fn instantiate_struct_literal_ty(&self,
1407                                      did: ast::DefId,
1408                                      path: &ast::Path)
1409                                      -> TypeAndSubsts<'tcx>
1410     {
1411         let tcx = self.tcx();
1412
1413         let ty::TypeScheme { generics, ty: decl_ty } =
1414             tcx.lookup_item_type(did);
1415
1416         let substs = astconv::ast_path_substs_for_ty(self, self,
1417                                                      path.span,
1418                                                      PathParamMode::Optional,
1419                                                      &generics,
1420                                                      path.segments.last().unwrap());
1421
1422         let ty = self.instantiate_type_scheme(path.span, &substs, &decl_ty);
1423
1424         TypeAndSubsts { substs: substs, ty: ty }
1425     }
1426
1427     pub fn write_nil(&self, node_id: ast::NodeId) {
1428         self.write_ty(node_id, self.tcx().mk_nil());
1429     }
1430     pub fn write_error(&self, node_id: ast::NodeId) {
1431         self.write_ty(node_id, self.tcx().types.err);
1432     }
1433
1434     pub fn require_type_meets(&self,
1435                               ty: Ty<'tcx>,
1436                               span: Span,
1437                               code: traits::ObligationCauseCode<'tcx>,
1438                               bound: ty::BuiltinBound)
1439     {
1440         self.register_builtin_bound(
1441             ty,
1442             bound,
1443             traits::ObligationCause::new(span, self.body_id, code));
1444     }
1445
1446     pub fn require_type_is_sized(&self,
1447                                  ty: Ty<'tcx>,
1448                                  span: Span,
1449                                  code: traits::ObligationCauseCode<'tcx>)
1450     {
1451         self.require_type_meets(ty, span, code, ty::BoundSized);
1452     }
1453
1454     pub fn require_expr_have_sized_type(&self,
1455                                         expr: &ast::Expr,
1456                                         code: traits::ObligationCauseCode<'tcx>)
1457     {
1458         self.require_type_is_sized(self.expr_ty(expr), expr.span, code);
1459     }
1460
1461     pub fn type_is_known_to_be_sized(&self,
1462                                      ty: Ty<'tcx>,
1463                                      span: Span)
1464                                      -> bool
1465     {
1466         traits::type_known_to_meet_builtin_bound(self.infcx(),
1467                                                  ty,
1468                                                  ty::BoundSized,
1469                                                  span)
1470     }
1471
1472     pub fn register_builtin_bound(&self,
1473                                   ty: Ty<'tcx>,
1474                                   builtin_bound: ty::BuiltinBound,
1475                                   cause: traits::ObligationCause<'tcx>)
1476     {
1477         self.inh.infcx.fulfillment_cx.borrow_mut()
1478             .register_builtin_bound(self.infcx(), ty, builtin_bound, cause);
1479     }
1480
1481     pub fn register_predicate(&self,
1482                               obligation: traits::PredicateObligation<'tcx>)
1483     {
1484         debug!("register_predicate({:?})",
1485                obligation);
1486         self.inh.infcx.fulfillment_cx
1487             .borrow_mut()
1488             .register_predicate_obligation(self.infcx(), obligation);
1489     }
1490
1491     pub fn to_ty(&self, ast_t: &ast::Ty) -> Ty<'tcx> {
1492         let t = ast_ty_to_ty(self, self, ast_t);
1493
1494         let mut bounds_checker = wf::BoundsChecker::new(self,
1495                                                         self.body_id,
1496                                                         None);
1497         bounds_checker.check_ty(t, ast_t.span);
1498
1499         t
1500     }
1501
1502     pub fn expr_ty(&self, ex: &ast::Expr) -> Ty<'tcx> {
1503         match self.inh.tables.borrow().node_types.get(&ex.id) {
1504             Some(&t) => t,
1505             None => {
1506                 self.tcx().sess.bug(&format!("no type for expr in fcx {}",
1507                                             self.tag()));
1508             }
1509         }
1510     }
1511
1512     /// Apply `adjustment` to the type of `expr`
1513     pub fn adjust_expr_ty(&self,
1514                           expr: &ast::Expr,
1515                           adjustment: Option<&ty::AutoAdjustment<'tcx>>)
1516                           -> Ty<'tcx>
1517     {
1518         let raw_ty = self.expr_ty(expr);
1519         let raw_ty = self.infcx().shallow_resolve(raw_ty);
1520         let resolve_ty = |ty: Ty<'tcx>| self.infcx().resolve_type_vars_if_possible(&ty);
1521         raw_ty.adjust(self.tcx(), expr.span, expr.id, adjustment, |method_call| {
1522             self.inh.tables.borrow().method_map.get(&method_call)
1523                                         .map(|method| resolve_ty(method.ty))
1524         })
1525     }
1526
1527     pub fn node_ty(&self, id: ast::NodeId) -> Ty<'tcx> {
1528         match self.inh.tables.borrow().node_types.get(&id) {
1529             Some(&t) => t,
1530             None if self.err_count_since_creation() != 0 => self.tcx().types.err,
1531             None => {
1532                 self.tcx().sess.bug(
1533                     &format!("no type for node {}: {} in fcx {}",
1534                             id, self.tcx().map.node_to_string(id),
1535                             self.tag()));
1536             }
1537         }
1538     }
1539
1540     pub fn item_substs(&self) -> Ref<NodeMap<ty::ItemSubsts<'tcx>>> {
1541         // NOTE: @jroesch this is hack that appears to be fixed on nightly, will monitor if
1542         // it changes when we upgrade the snapshot compiler
1543         fn project_item_susbts<'a, 'tcx>(tables: &'a ty::Tables<'tcx>)
1544                                         -> &'a NodeMap<ty::ItemSubsts<'tcx>> {
1545             &tables.item_substs
1546         }
1547
1548         Ref::map(self.inh.tables.borrow(), project_item_susbts)
1549     }
1550
1551     pub fn opt_node_ty_substs<F>(&self,
1552                                  id: ast::NodeId,
1553                                  f: F) where
1554         F: FnOnce(&ty::ItemSubsts<'tcx>),
1555     {
1556         match self.inh.tables.borrow().item_substs.get(&id) {
1557             Some(s) => { f(s) }
1558             None => { }
1559         }
1560     }
1561
1562     pub fn mk_subty(&self,
1563                     a_is_expected: bool,
1564                     origin: infer::TypeOrigin,
1565                     sub: Ty<'tcx>,
1566                     sup: Ty<'tcx>)
1567                     -> Result<(), ty::TypeError<'tcx>> {
1568         infer::mk_subty(self.infcx(), a_is_expected, origin, sub, sup)
1569     }
1570
1571     pub fn mk_eqty(&self,
1572                    a_is_expected: bool,
1573                    origin: infer::TypeOrigin,
1574                    sub: Ty<'tcx>,
1575                    sup: Ty<'tcx>)
1576                    -> Result<(), ty::TypeError<'tcx>> {
1577         infer::mk_eqty(self.infcx(), a_is_expected, origin, sub, sup)
1578     }
1579
1580     pub fn mk_subr(&self,
1581                    origin: infer::SubregionOrigin<'tcx>,
1582                    sub: ty::Region,
1583                    sup: ty::Region) {
1584         infer::mk_subr(self.infcx(), origin, sub, sup)
1585     }
1586
1587     pub fn type_error_message<M>(&self,
1588                                  sp: Span,
1589                                  mk_msg: M,
1590                                  actual_ty: Ty<'tcx>,
1591                                  err: Option<&ty::TypeError<'tcx>>) where
1592         M: FnOnce(String) -> String,
1593     {
1594         self.infcx().type_error_message(sp, mk_msg, actual_ty, err);
1595     }
1596
1597     pub fn report_mismatched_types(&self,
1598                                    sp: Span,
1599                                    e: Ty<'tcx>,
1600                                    a: Ty<'tcx>,
1601                                    err: &ty::TypeError<'tcx>) {
1602         self.infcx().report_mismatched_types(sp, e, a, err)
1603     }
1604
1605     /// Registers an obligation for checking later, during regionck, that the type `ty` must
1606     /// outlive the region `r`.
1607     pub fn register_region_obligation(&self,
1608                                       ty: Ty<'tcx>,
1609                                       region: ty::Region,
1610                                       cause: traits::ObligationCause<'tcx>)
1611     {
1612         let mut fulfillment_cx = self.inh.infcx.fulfillment_cx.borrow_mut();
1613         fulfillment_cx.register_region_obligation(ty, region, cause);
1614     }
1615
1616     pub fn add_default_region_param_bounds(&self,
1617                                            substs: &Substs<'tcx>,
1618                                            expr: &ast::Expr)
1619     {
1620         for &ty in &substs.types {
1621             let default_bound = ty::ReScope(CodeExtent::from_node_id(expr.id));
1622             let cause = traits::ObligationCause::new(expr.span, self.body_id,
1623                                                      traits::MiscObligation);
1624             self.register_region_obligation(ty, default_bound, cause);
1625         }
1626     }
1627
1628     /// Given a fully substituted set of bounds (`generic_bounds`), and the values with which each
1629     /// type/region parameter was instantiated (`substs`), creates and registers suitable
1630     /// trait/region obligations.
1631     ///
1632     /// For example, if there is a function:
1633     ///
1634     /// ```
1635     /// fn foo<'a,T:'a>(...)
1636     /// ```
1637     ///
1638     /// and a reference:
1639     ///
1640     /// ```
1641     /// let f = foo;
1642     /// ```
1643     ///
1644     /// Then we will create a fresh region variable `'$0` and a fresh type variable `$1` for `'a`
1645     /// and `T`. This routine will add a region obligation `$1:'$0` and register it locally.
1646     pub fn add_obligations_for_parameters(&self,
1647                                           cause: traits::ObligationCause<'tcx>,
1648                                           predicates: &ty::InstantiatedPredicates<'tcx>)
1649     {
1650         assert!(!predicates.has_escaping_regions());
1651
1652         debug!("add_obligations_for_parameters(predicates={:?})",
1653                predicates);
1654
1655         for obligation in traits::predicates_for_generics(cause, predicates) {
1656             self.register_predicate(obligation);
1657         }
1658     }
1659
1660     // Only for fields! Returns <none> for methods>
1661     // Indifferent to privacy flags
1662     pub fn lookup_field_ty(&self,
1663                            span: Span,
1664                            class_id: ast::DefId,
1665                            items: &[ty::FieldTy],
1666                            fieldname: ast::Name,
1667                            substs: &subst::Substs<'tcx>)
1668                            -> Option<Ty<'tcx>>
1669     {
1670         let o_field = items.iter().find(|f| f.name == fieldname);
1671         o_field.map(|f| self.tcx().lookup_field_type(class_id, f.id, substs))
1672                .map(|t| self.normalize_associated_types_in(span, &t))
1673     }
1674
1675     pub fn lookup_tup_field_ty(&self,
1676                                span: Span,
1677                                class_id: ast::DefId,
1678                                items: &[ty::FieldTy],
1679                                idx: usize,
1680                                substs: &subst::Substs<'tcx>)
1681                                -> Option<Ty<'tcx>>
1682     {
1683         let o_field = if idx < items.len() { Some(&items[idx]) } else { None };
1684         o_field.map(|f| self.tcx().lookup_field_type(class_id, f.id, substs))
1685                .map(|t| self.normalize_associated_types_in(span, &t))
1686     }
1687
1688     fn check_casts(&self) {
1689         let mut deferred_cast_checks = self.inh.deferred_cast_checks.borrow_mut();
1690         for cast in deferred_cast_checks.drain(..) {
1691             cast.check(self);
1692         }
1693     }
1694
1695     fn select_all_obligations_and_apply_defaults(&self) {
1696         use middle::ty::UnconstrainedNumeric::{UnconstrainedInt, UnconstrainedFloat, Neither};
1697
1698         // For the time being this errs on the side of being memory wasteful but provides better
1699         // error reporting.
1700         // let type_variables = self.infcx().type_variables.clone();
1701
1702         // There is a possibility that this algorithm will have to run an arbitrary number of times
1703         // to terminate so we bound it by the compiler's recursion limit.
1704         for _ in (0..self.tcx().sess.recursion_limit.get()) {
1705             // First we try to solve all obligations, it is possible that the last iteration
1706             // has made it possible to make more progress.
1707             self.select_obligations_where_possible();
1708
1709             let mut conflicts = Vec::new();
1710
1711             // Collect all unsolved type, integral and floating point variables.
1712             let unsolved_variables = self.inh.infcx.unsolved_variables();
1713
1714             // We must collect the defaults *before* we do any unification. Because we have
1715             // directly attached defaults to the type variables any unification that occurs
1716             // will erase defaults causing conflicting defaults to be completely ignored.
1717             let default_map: FnvHashMap<_, _> =
1718                 unsolved_variables
1719                     .iter()
1720                     .filter_map(|t| self.infcx().default(t).map(|d| (t, d)))
1721                     .collect();
1722
1723             let mut unbound_tyvars = HashSet::new();
1724
1725             debug!("select_all_obligations_and_apply_defaults: defaults={:?}", default_map);
1726
1727             // We loop over the unsolved variables, resolving them and if they are
1728             // and unconstrainted numberic type we add them to the set of unbound
1729             // variables. We do this so we only apply literal fallback to type
1730             // variables without defaults.
1731             for ty in &unsolved_variables {
1732                 let resolved = self.infcx().resolve_type_vars_if_possible(ty);
1733                 if self.infcx().type_var_diverges(resolved) {
1734                     demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().mk_nil());
1735                 } else {
1736                     match self.infcx().type_is_unconstrained_numeric(resolved) {
1737                         UnconstrainedInt | UnconstrainedFloat => {
1738                             unbound_tyvars.insert(resolved);
1739                         },
1740                         Neither => {}
1741                     }
1742                 }
1743             }
1744
1745             // We now remove any numeric types that also have defaults, and instead insert
1746             // the type variable with a defined fallback.
1747             for ty in &unsolved_variables {
1748                 if let Some(_default) = default_map.get(ty) {
1749                     let resolved = self.infcx().resolve_type_vars_if_possible(ty);
1750
1751                     debug!("select_all_obligations_and_apply_defaults: ty: {:?} with default: {:?}",
1752                              ty, _default);
1753
1754                     match resolved.sty {
1755                         ty::TyInfer(ty::TyVar(_)) => {
1756                             unbound_tyvars.insert(ty);
1757                         }
1758
1759                         ty::TyInfer(ty::IntVar(_)) | ty::TyInfer(ty::FloatVar(_)) => {
1760                             unbound_tyvars.insert(ty);
1761                             if unbound_tyvars.contains(resolved) {
1762                                 unbound_tyvars.remove(resolved);
1763                             }
1764                         }
1765
1766                         _ => {}
1767                     }
1768                 }
1769             }
1770
1771             // If there are no more fallbacks to apply at this point we have applied all possible
1772             // defaults and type inference will procede as normal.
1773             if unbound_tyvars.is_empty() {
1774                 break;
1775             }
1776
1777             // Finally we go through each of the unbound type variables and unify them with
1778             // the proper fallback, reporting a conflicting default error if any of the
1779             // unifications fail. We know it must be a conflicting default because the
1780             // variable would only be in `unbound_tyvars` and have a concrete value if
1781             // it had been solved by previously applying a default.
1782
1783             // We take a snapshot for use in error reporting.
1784             let snapshot = self.infcx().type_variables.borrow_mut().snapshot();
1785
1786             for ty in &unbound_tyvars {
1787                 if self.infcx().type_var_diverges(ty) {
1788                     demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().mk_nil());
1789                 } else {
1790                     match self.infcx().type_is_unconstrained_numeric(ty) {
1791                         UnconstrainedInt => {
1792                             demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().types.i32)
1793                         },
1794                         UnconstrainedFloat => {
1795                             demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().types.f64)
1796                         }
1797                         Neither => {
1798                             if let Some(default) = default_map.get(ty) {
1799                                 let default = default.clone();
1800                                 match infer::mk_eqty(self.infcx(), false,
1801                                                      infer::Misc(default.origin_span),
1802                                                      ty, default.ty) {
1803                                     Ok(()) => {}
1804                                     Err(_) => {
1805                                         conflicts.push((*ty, default));
1806                                     }
1807                                 }
1808                             }
1809                         }
1810                     }
1811                 }
1812             }
1813
1814             // There were some errors to report
1815             if conflicts.len() > 0 {
1816                 self.infcx().type_variables.borrow_mut().rollback_to(snapshot);
1817
1818                 for (conflict, default) in conflicts {
1819                     let conflicting_default =
1820                         self.find_conflicting_default(
1821                             &unbound_tyvars,
1822                             &default_map,
1823                             conflict).unwrap_or(type_variable::Default {
1824                                 ty: self.infcx().next_ty_var(),
1825                                 origin_span: codemap::DUMMY_SP,
1826                                 definition_span: codemap::DUMMY_SP
1827                             });
1828
1829                             self.infcx().report_conflicting_default_types(
1830                                 conflicting_default.origin_span,
1831                                 conflicting_default,
1832                                 default)
1833                 }
1834             } else {
1835                 self.infcx().type_variables.borrow_mut().commit(snapshot)
1836             }
1837         }
1838
1839         self.select_obligations_where_possible();
1840     }
1841
1842     // For use in error handling related to default type parameter fallback. We explicitly
1843     // apply the default that caused conflict first to a local version of the type variable
1844     // table then apply defaults until we find a conflict. That default must be the one
1845     // that caused conflict earlier.
1846     fn find_conflicting_default(&self,
1847                                 unbound_vars: &HashSet<Ty<'tcx>>,
1848                                 default_map: &FnvHashMap<&Ty<'tcx>, type_variable::Default<'tcx>>,
1849                                 conflict: Ty<'tcx>)
1850                                 -> Option<type_variable::Default<'tcx>> {
1851         use middle::ty::UnconstrainedNumeric::{UnconstrainedInt, UnconstrainedFloat, Neither};
1852
1853         // Ensure that the conflicting default is applied first
1854         let mut unbound_tyvars = Vec::with_capacity(unbound_vars.len() + 1);
1855         unbound_tyvars.push(conflict);
1856         unbound_tyvars.extend(unbound_vars.iter());
1857
1858         let mut result = None;
1859         // We run the same code as above applying defaults in order, this time when
1860         // we find the conflict we just return it for error reporting above.
1861         for ty in &unbound_tyvars {
1862             if self.infcx().type_var_diverges(ty) {
1863                 demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().mk_nil());
1864             } else {
1865                 match self.infcx().type_is_unconstrained_numeric(ty) {
1866                     UnconstrainedInt => {
1867                         demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().types.i32)
1868                     },
1869                     UnconstrainedFloat => {
1870                         demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().types.f64)
1871                     },
1872                     Neither => {
1873                         if let Some(default) = default_map.get(ty) {
1874                             let default = default.clone();
1875                             match infer::mk_eqty(self.infcx(), false,
1876                                                  infer::Misc(default.origin_span),
1877                                                  ty, default.ty) {
1878                                 Ok(()) => {}
1879                                 Err(_) => {
1880                                     result = Some(default);
1881                                 }
1882                             }
1883                         }
1884                     }
1885                 }
1886             }
1887         }
1888
1889         return result;
1890     }
1891
1892     fn select_all_obligations_or_error(&self) {
1893         debug!("select_all_obligations_or_error");
1894
1895         // upvar inference should have ensured that all deferred call
1896         // resolutions are handled by now.
1897         assert!(self.inh.deferred_call_resolutions.borrow().is_empty());
1898
1899         self.select_all_obligations_and_apply_defaults();
1900         let mut fulfillment_cx = self.inh.infcx.fulfillment_cx.borrow_mut();
1901         match fulfillment_cx.select_all_or_error(self.infcx()) {
1902             Ok(()) => { }
1903             Err(errors) => { report_fulfillment_errors(self.infcx(), &errors); }
1904         }
1905     }
1906
1907     /// Select as many obligations as we can at present.
1908     fn select_obligations_where_possible(&self) {
1909         match
1910             self.inh.infcx.fulfillment_cx
1911             .borrow_mut()
1912             .select_where_possible(self.infcx())
1913         {
1914             Ok(()) => { }
1915             Err(errors) => { report_fulfillment_errors(self.infcx(), &errors); }
1916         }
1917     }
1918
1919     /// Try to select any fcx obligation that we haven't tried yet, in an effort
1920     /// to improve inference. You could just call
1921     /// `select_obligations_where_possible` except that it leads to repeated
1922     /// work.
1923     fn select_new_obligations(&self) {
1924         match
1925             self.inh.infcx.fulfillment_cx
1926             .borrow_mut()
1927             .select_new_obligations(self.infcx())
1928         {
1929             Ok(()) => { }
1930             Err(errors) => { report_fulfillment_errors(self.infcx(), &errors); }
1931         }
1932     }
1933
1934 }
1935
1936 impl<'a, 'tcx> RegionScope for FnCtxt<'a, 'tcx> {
1937     fn object_lifetime_default(&self, span: Span) -> Option<ty::Region> {
1938         Some(self.base_object_lifetime_default(span))
1939     }
1940
1941     fn base_object_lifetime_default(&self, span: Span) -> ty::Region {
1942         // RFC #599 specifies that object lifetime defaults take
1943         // precedence over other defaults. But within a fn body we
1944         // don't have a *default* region, rather we use inference to
1945         // find the *correct* region, which is strictly more general
1946         // (and anyway, within a fn body the right region may not even
1947         // be something the user can write explicitly, since it might
1948         // be some expression).
1949         self.infcx().next_region_var(infer::MiscVariable(span))
1950     }
1951
1952     fn anon_regions(&self, span: Span, count: usize)
1953                     -> Result<Vec<ty::Region>, Option<Vec<ElisionFailureInfo>>> {
1954         Ok((0..count).map(|_| {
1955             self.infcx().next_region_var(infer::MiscVariable(span))
1956         }).collect())
1957     }
1958 }
1959
1960 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
1961 pub enum LvaluePreference {
1962     PreferMutLvalue,
1963     NoPreference
1964 }
1965
1966 impl LvaluePreference {
1967     pub fn from_mutbl(m: ast::Mutability) -> Self {
1968         match m {
1969             ast::MutMutable => PreferMutLvalue,
1970             ast::MutImmutable => NoPreference,
1971         }
1972     }
1973 }
1974
1975 /// Whether `autoderef` requires types to resolve.
1976 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
1977 pub enum UnresolvedTypeAction {
1978     /// Produce an error and return `TyError` whenever a type cannot
1979     /// be resolved (i.e. it is `TyInfer`).
1980     Error,
1981     /// Go on without emitting any errors, and return the unresolved
1982     /// type. Useful for probing, e.g. in coercions.
1983     Ignore
1984 }
1985
1986 /// Executes an autoderef loop for the type `t`. At each step, invokes `should_stop` to decide
1987 /// whether to terminate the loop. Returns the final type and number of derefs that it performed.
1988 ///
1989 /// Note: this method does not modify the adjustments table. The caller is responsible for
1990 /// inserting an AutoAdjustment record into the `fcx` using one of the suitable methods.
1991 pub fn autoderef<'a, 'tcx, T, F>(fcx: &FnCtxt<'a, 'tcx>,
1992                                  sp: Span,
1993                                  base_ty: Ty<'tcx>,
1994                                  opt_expr: Option<&ast::Expr>,
1995                                  unresolved_type_action: UnresolvedTypeAction,
1996                                  mut lvalue_pref: LvaluePreference,
1997                                  mut should_stop: F)
1998                                  -> (Ty<'tcx>, usize, Option<T>)
1999     where F: FnMut(Ty<'tcx>, usize) -> Option<T>,
2000 {
2001     debug!("autoderef(base_ty={:?}, opt_expr={:?}, lvalue_pref={:?})",
2002            base_ty,
2003            opt_expr,
2004            lvalue_pref);
2005
2006     let mut t = base_ty;
2007     for autoderefs in 0..fcx.tcx().sess.recursion_limit.get() {
2008         let resolved_t = match unresolved_type_action {
2009             UnresolvedTypeAction::Error => {
2010                 structurally_resolved_type(fcx, sp, t)
2011             }
2012             UnresolvedTypeAction::Ignore => {
2013                 // We can continue even when the type cannot be resolved
2014                 // (i.e. it is an inference variable) because `Ty::builtin_deref`
2015                 // and `try_overloaded_deref` both simply return `None`
2016                 // in such a case without producing spurious errors.
2017                 fcx.resolve_type_vars_if_possible(t)
2018             }
2019         };
2020         if resolved_t.references_error() {
2021             return (resolved_t, autoderefs, None);
2022         }
2023
2024         match should_stop(resolved_t, autoderefs) {
2025             Some(x) => return (resolved_t, autoderefs, Some(x)),
2026             None => {}
2027         }
2028
2029         // Otherwise, deref if type is derefable:
2030         let mt = match resolved_t.builtin_deref(false) {
2031             Some(mt) => Some(mt),
2032             None => {
2033                 let method_call =
2034                     opt_expr.map(|expr| MethodCall::autoderef(expr.id, autoderefs as u32));
2035
2036                 // Super subtle: it might seem as though we should
2037                 // pass `opt_expr` to `try_overloaded_deref`, so that
2038                 // the (implicit) autoref of using an overloaded deref
2039                 // would get added to the adjustment table. However we
2040                 // do not do that, because it's kind of a
2041                 // "meta-adjustment" -- instead, we just leave it
2042                 // unrecorded and know that there "will be" an
2043                 // autoref. regionck and other bits of the code base,
2044                 // when they encounter an overloaded autoderef, have
2045                 // to do some reconstructive surgery. This is a pretty
2046                 // complex mess that is begging for a proper MIR.
2047                 try_overloaded_deref(fcx, sp, method_call, None, resolved_t, lvalue_pref)
2048             }
2049         };
2050         match mt {
2051             Some(mt) => {
2052                 t = mt.ty;
2053                 if mt.mutbl == ast::MutImmutable {
2054                     lvalue_pref = NoPreference;
2055                 }
2056             }
2057             None => return (resolved_t, autoderefs, None)
2058         }
2059     }
2060
2061     // We've reached the recursion limit, error gracefully.
2062     span_err!(fcx.tcx().sess, sp, E0055,
2063         "reached the recursion limit while auto-dereferencing {:?}",
2064         base_ty);
2065     (fcx.tcx().types.err, 0, None)
2066 }
2067
2068 fn try_overloaded_deref<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2069                                   span: Span,
2070                                   method_call: Option<MethodCall>,
2071                                   base_expr: Option<&ast::Expr>,
2072                                   base_ty: Ty<'tcx>,
2073                                   lvalue_pref: LvaluePreference)
2074                                   -> Option<ty::TypeAndMut<'tcx>>
2075 {
2076     // Try DerefMut first, if preferred.
2077     let method = match (lvalue_pref, fcx.tcx().lang_items.deref_mut_trait()) {
2078         (PreferMutLvalue, Some(trait_did)) => {
2079             method::lookup_in_trait(fcx, span, base_expr,
2080                                     token::intern("deref_mut"), trait_did,
2081                                     base_ty, None)
2082         }
2083         _ => None
2084     };
2085
2086     // Otherwise, fall back to Deref.
2087     let method = match (method, fcx.tcx().lang_items.deref_trait()) {
2088         (None, Some(trait_did)) => {
2089             method::lookup_in_trait(fcx, span, base_expr,
2090                                     token::intern("deref"), trait_did,
2091                                     base_ty, None)
2092         }
2093         (method, _) => method
2094     };
2095
2096     make_overloaded_lvalue_return_type(fcx, method_call, method)
2097 }
2098
2099 /// For the overloaded lvalue expressions (`*x`, `x[3]`), the trait returns a type of `&T`, but the
2100 /// actual type we assign to the *expression* is `T`. So this function just peels off the return
2101 /// type by one layer to yield `T`. It also inserts the `method-callee` into the method map.
2102 fn make_overloaded_lvalue_return_type<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2103                                                 method_call: Option<MethodCall>,
2104                                                 method: Option<MethodCallee<'tcx>>)
2105                                                 -> Option<ty::TypeAndMut<'tcx>>
2106 {
2107     match method {
2108         Some(method) => {
2109             // extract method method return type, which will be &T;
2110             // all LB regions should have been instantiated during method lookup
2111             let ret_ty = method.ty.fn_ret();
2112             let ret_ty = fcx.tcx().no_late_bound_regions(&ret_ty).unwrap().unwrap();
2113
2114             if let Some(method_call) = method_call {
2115                 fcx.inh.tables.borrow_mut().method_map.insert(method_call, method);
2116             }
2117
2118             // method returns &T, but the type as visible to user is T, so deref
2119             ret_ty.builtin_deref(true)
2120         }
2121         None => None,
2122     }
2123 }
2124
2125 fn lookup_indexing<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2126                              expr: &ast::Expr,
2127                              base_expr: &'tcx ast::Expr,
2128                              base_ty: Ty<'tcx>,
2129                              idx_ty: Ty<'tcx>,
2130                              lvalue_pref: LvaluePreference)
2131                              -> Option<(/*index type*/ Ty<'tcx>, /*element type*/ Ty<'tcx>)>
2132 {
2133     // FIXME(#18741) -- this is almost but not quite the same as the
2134     // autoderef that normal method probing does. They could likely be
2135     // consolidated.
2136
2137     let (ty, autoderefs, final_mt) = autoderef(fcx,
2138                                                base_expr.span,
2139                                                base_ty,
2140                                                Some(base_expr),
2141                                                UnresolvedTypeAction::Error,
2142                                                lvalue_pref,
2143                                                |adj_ty, idx| {
2144         try_index_step(fcx, MethodCall::expr(expr.id), expr, base_expr,
2145                        adj_ty, idx, false, lvalue_pref, idx_ty)
2146     });
2147
2148     if final_mt.is_some() {
2149         return final_mt;
2150     }
2151
2152     // After we have fully autoderef'd, if the resulting type is [T; n], then
2153     // do a final unsized coercion to yield [T].
2154     if let ty::TyArray(element_ty, _) = ty.sty {
2155         let adjusted_ty = fcx.tcx().mk_slice(element_ty);
2156         try_index_step(fcx, MethodCall::expr(expr.id), expr, base_expr,
2157                        adjusted_ty, autoderefs, true, lvalue_pref, idx_ty)
2158     } else {
2159         None
2160     }
2161 }
2162
2163 /// To type-check `base_expr[index_expr]`, we progressively autoderef (and otherwise adjust)
2164 /// `base_expr`, looking for a type which either supports builtin indexing or overloaded indexing.
2165 /// This loop implements one step in that search; the autoderef loop is implemented by
2166 /// `lookup_indexing`.
2167 fn try_index_step<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2168                             method_call: MethodCall,
2169                             expr: &ast::Expr,
2170                             base_expr: &'tcx ast::Expr,
2171                             adjusted_ty: Ty<'tcx>,
2172                             autoderefs: usize,
2173                             unsize: bool,
2174                             lvalue_pref: LvaluePreference,
2175                             index_ty: Ty<'tcx>)
2176                             -> Option<(/*index type*/ Ty<'tcx>, /*element type*/ Ty<'tcx>)>
2177 {
2178     let tcx = fcx.tcx();
2179     debug!("try_index_step(expr={:?}, base_expr.id={:?}, adjusted_ty={:?}, \
2180                            autoderefs={}, unsize={}, index_ty={:?})",
2181            expr,
2182            base_expr,
2183            adjusted_ty,
2184            autoderefs,
2185            unsize,
2186            index_ty);
2187
2188     let input_ty = fcx.infcx().next_ty_var();
2189
2190     // First, try built-in indexing.
2191     match (adjusted_ty.builtin_index(), &index_ty.sty) {
2192         (Some(ty), &ty::TyUint(ast::TyUs)) | (Some(ty), &ty::TyInfer(ty::IntVar(_))) => {
2193             debug!("try_index_step: success, using built-in indexing");
2194             // If we had `[T; N]`, we should've caught it before unsizing to `[T]`.
2195             assert!(!unsize);
2196             fcx.write_autoderef_adjustment(base_expr.id, autoderefs);
2197             return Some((tcx.types.usize, ty));
2198         }
2199         _ => {}
2200     }
2201
2202     // Try `IndexMut` first, if preferred.
2203     let method = match (lvalue_pref, tcx.lang_items.index_mut_trait()) {
2204         (PreferMutLvalue, Some(trait_did)) => {
2205             method::lookup_in_trait_adjusted(fcx,
2206                                              expr.span,
2207                                              Some(&*base_expr),
2208                                              token::intern("index_mut"),
2209                                              trait_did,
2210                                              autoderefs,
2211                                              unsize,
2212                                              adjusted_ty,
2213                                              Some(vec![input_ty]))
2214         }
2215         _ => None,
2216     };
2217
2218     // Otherwise, fall back to `Index`.
2219     let method = match (method, tcx.lang_items.index_trait()) {
2220         (None, Some(trait_did)) => {
2221             method::lookup_in_trait_adjusted(fcx,
2222                                              expr.span,
2223                                              Some(&*base_expr),
2224                                              token::intern("index"),
2225                                              trait_did,
2226                                              autoderefs,
2227                                              unsize,
2228                                              adjusted_ty,
2229                                              Some(vec![input_ty]))
2230         }
2231         (method, _) => method,
2232     };
2233
2234     // If some lookup succeeds, write callee into table and extract index/element
2235     // type from the method signature.
2236     // If some lookup succeeded, install method in table
2237     method.and_then(|method| {
2238         debug!("try_index_step: success, using overloaded indexing");
2239         make_overloaded_lvalue_return_type(fcx, Some(method_call), Some(method)).
2240             map(|ret| (input_ty, ret.ty))
2241     })
2242 }
2243
2244 fn check_method_argument_types<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2245                                          sp: Span,
2246                                          method_fn_ty: Ty<'tcx>,
2247                                          callee_expr: &'tcx ast::Expr,
2248                                          args_no_rcvr: &'tcx [P<ast::Expr>],
2249                                          tuple_arguments: TupleArgumentsFlag,
2250                                          expected: Expectation<'tcx>)
2251                                          -> ty::FnOutput<'tcx> {
2252     if method_fn_ty.references_error() {
2253         let err_inputs = err_args(fcx.tcx(), args_no_rcvr.len());
2254
2255         let err_inputs = match tuple_arguments {
2256             DontTupleArguments => err_inputs,
2257             TupleArguments => vec![fcx.tcx().mk_tup(err_inputs)],
2258         };
2259
2260         check_argument_types(fcx,
2261                              sp,
2262                              &err_inputs[..],
2263                              &[],
2264                              args_no_rcvr,
2265                              false,
2266                              tuple_arguments);
2267         ty::FnConverging(fcx.tcx().types.err)
2268     } else {
2269         match method_fn_ty.sty {
2270             ty::TyBareFn(_, ref fty) => {
2271                 // HACK(eddyb) ignore self in the definition (see above).
2272                 let expected_arg_tys = expected_types_for_fn_args(fcx,
2273                                                                   sp,
2274                                                                   expected,
2275                                                                   fty.sig.0.output,
2276                                                                   &fty.sig.0.inputs[1..]);
2277                 check_argument_types(fcx,
2278                                      sp,
2279                                      &fty.sig.0.inputs[1..],
2280                                      &expected_arg_tys[..],
2281                                      args_no_rcvr,
2282                                      fty.sig.0.variadic,
2283                                      tuple_arguments);
2284                 fty.sig.0.output
2285             }
2286             _ => {
2287                 fcx.tcx().sess.span_bug(callee_expr.span,
2288                                         "method without bare fn type");
2289             }
2290         }
2291     }
2292 }
2293
2294 /// Generic function that factors out common logic from function calls, method calls and overloaded
2295 /// operators.
2296 fn check_argument_types<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2297                                   sp: Span,
2298                                   fn_inputs: &[Ty<'tcx>],
2299                                   expected_arg_tys: &[Ty<'tcx>],
2300                                   args: &'tcx [P<ast::Expr>],
2301                                   variadic: bool,
2302                                   tuple_arguments: TupleArgumentsFlag) {
2303     let tcx = fcx.ccx.tcx;
2304
2305     // Grab the argument types, supplying fresh type variables
2306     // if the wrong number of arguments were supplied
2307     let supplied_arg_count = if tuple_arguments == DontTupleArguments {
2308         args.len()
2309     } else {
2310         1
2311     };
2312
2313     let mut expected_arg_tys = expected_arg_tys;
2314     let expected_arg_count = fn_inputs.len();
2315     let formal_tys = if tuple_arguments == TupleArguments {
2316         let tuple_type = structurally_resolved_type(fcx, sp, fn_inputs[0]);
2317         match tuple_type.sty {
2318             ty::TyTuple(ref arg_types) => {
2319                 if arg_types.len() != args.len() {
2320                     span_err!(tcx.sess, sp, E0057,
2321                         "this function takes {} parameter{} but {} parameter{} supplied",
2322                         arg_types.len(),
2323                         if arg_types.len() == 1 {""} else {"s"},
2324                         args.len(),
2325                         if args.len() == 1 {" was"} else {"s were"});
2326                     expected_arg_tys = &[];
2327                     err_args(fcx.tcx(), args.len())
2328                 } else {
2329                     expected_arg_tys = match expected_arg_tys.get(0) {
2330                         Some(&ty) => match ty.sty {
2331                             ty::TyTuple(ref tys) => &**tys,
2332                             _ => &[]
2333                         },
2334                         None => &[]
2335                     };
2336                     (*arg_types).clone()
2337                 }
2338             }
2339             _ => {
2340                 span_err!(tcx.sess, sp, E0059,
2341                     "cannot use call notation; the first type parameter \
2342                      for the function trait is neither a tuple nor unit");
2343                 expected_arg_tys = &[];
2344                 err_args(fcx.tcx(), args.len())
2345             }
2346         }
2347     } else if expected_arg_count == supplied_arg_count {
2348         fn_inputs.to_vec()
2349     } else if variadic {
2350         if supplied_arg_count >= expected_arg_count {
2351             fn_inputs.to_vec()
2352         } else {
2353             span_err!(tcx.sess, sp, E0060,
2354                 "this function takes at least {} parameter{} \
2355                  but {} parameter{} supplied",
2356                 expected_arg_count,
2357                 if expected_arg_count == 1 {""} else {"s"},
2358                 supplied_arg_count,
2359                 if supplied_arg_count == 1 {" was"} else {"s were"});
2360             expected_arg_tys = &[];
2361             err_args(fcx.tcx(), supplied_arg_count)
2362         }
2363     } else {
2364         span_err!(tcx.sess, sp, E0061,
2365             "this function takes {} parameter{} but {} parameter{} supplied",
2366             expected_arg_count,
2367             if expected_arg_count == 1 {""} else {"s"},
2368             supplied_arg_count,
2369             if supplied_arg_count == 1 {" was"} else {"s were"});
2370         expected_arg_tys = &[];
2371         err_args(fcx.tcx(), supplied_arg_count)
2372     };
2373
2374     debug!("check_argument_types: formal_tys={:?}",
2375            formal_tys.iter().map(|t| fcx.infcx().ty_to_string(*t)).collect::<Vec<String>>());
2376
2377     // Check the arguments.
2378     // We do this in a pretty awful way: first we typecheck any arguments
2379     // that are not anonymous functions, then we typecheck the anonymous
2380     // functions. This is so that we have more information about the types
2381     // of arguments when we typecheck the functions. This isn't really the
2382     // right way to do this.
2383     let xs = [false, true];
2384     for check_blocks in &xs {
2385         let check_blocks = *check_blocks;
2386         debug!("check_blocks={}", check_blocks);
2387
2388         // More awful hacks: before we check argument types, try to do
2389         // an "opportunistic" vtable resolution of any trait bounds on
2390         // the call. This helps coercions.
2391         if check_blocks {
2392             fcx.select_new_obligations();
2393         }
2394
2395         // For variadic functions, we don't have a declared type for all of
2396         // the arguments hence we only do our usual type checking with
2397         // the arguments who's types we do know.
2398         let t = if variadic {
2399             expected_arg_count
2400         } else if tuple_arguments == TupleArguments {
2401             args.len()
2402         } else {
2403             supplied_arg_count
2404         };
2405         for (i, arg) in args.iter().take(t).enumerate() {
2406             let is_block = match arg.node {
2407                 ast::ExprClosure(..) => true,
2408                 _ => false
2409             };
2410
2411             if is_block == check_blocks {
2412                 debug!("checking the argument");
2413                 let formal_ty = formal_tys[i];
2414
2415                 // The special-cased logic below has three functions:
2416                 // 1. Provide as good of an expected type as possible.
2417                 let expected = expected_arg_tys.get(i).map(|&ty| {
2418                     Expectation::rvalue_hint(ty)
2419                 });
2420
2421                 check_expr_with_unifier(fcx, &**arg,
2422                                         expected.unwrap_or(ExpectHasType(formal_ty)),
2423                                         NoPreference, || {
2424                     // 2. Coerce to the most detailed type that could be coerced
2425                     //    to, which is `expected_ty` if `rvalue_hint` returns an
2426                     //    `ExprHasType(expected_ty)`, or the `formal_ty` otherwise.
2427                     let coerce_ty = expected.and_then(|e| e.only_has_type(fcx));
2428                     demand::coerce(fcx, arg.span, coerce_ty.unwrap_or(formal_ty), &**arg);
2429
2430                     // 3. Relate the expected type and the formal one,
2431                     //    if the expected type was used for the coercion.
2432                     coerce_ty.map(|ty| demand::suptype(fcx, arg.span, formal_ty, ty));
2433                 });
2434             }
2435         }
2436     }
2437
2438     // We also need to make sure we at least write the ty of the other
2439     // arguments which we skipped above.
2440     if variadic {
2441         for arg in args.iter().skip(expected_arg_count) {
2442             check_expr(fcx, &**arg);
2443
2444             // There are a few types which get autopromoted when passed via varargs
2445             // in C but we just error out instead and require explicit casts.
2446             let arg_ty = structurally_resolved_type(fcx, arg.span,
2447                                                     fcx.expr_ty(&**arg));
2448             match arg_ty.sty {
2449                 ty::TyFloat(ast::TyF32) => {
2450                     fcx.type_error_message(arg.span,
2451                                            |t| {
2452                         format!("can't pass an {} to variadic \
2453                                  function, cast to c_double", t)
2454                     }, arg_ty, None);
2455                 }
2456                 ty::TyInt(ast::TyI8) | ty::TyInt(ast::TyI16) | ty::TyBool => {
2457                     fcx.type_error_message(arg.span, |t| {
2458                         format!("can't pass {} to variadic \
2459                                  function, cast to c_int",
2460                                        t)
2461                     }, arg_ty, None);
2462                 }
2463                 ty::TyUint(ast::TyU8) | ty::TyUint(ast::TyU16) => {
2464                     fcx.type_error_message(arg.span, |t| {
2465                         format!("can't pass {} to variadic \
2466                                  function, cast to c_uint",
2467                                        t)
2468                     }, arg_ty, None);
2469                 }
2470                 _ => {}
2471             }
2472         }
2473     }
2474 }
2475
2476 // FIXME(#17596) Ty<'tcx> is incorrectly invariant w.r.t 'tcx.
2477 fn err_args<'tcx>(tcx: &ty::ctxt<'tcx>, len: usize) -> Vec<Ty<'tcx>> {
2478     (0..len).map(|_| tcx.types.err).collect()
2479 }
2480
2481 fn write_call<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2482                         call_expr: &ast::Expr,
2483                         output: ty::FnOutput<'tcx>) {
2484     fcx.write_ty(call_expr.id, match output {
2485         ty::FnConverging(output_ty) => output_ty,
2486         ty::FnDiverging => fcx.infcx().next_diverging_ty_var()
2487     });
2488 }
2489
2490 // AST fragment checking
2491 fn check_lit<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2492                        lit: &ast::Lit,
2493                        expected: Expectation<'tcx>)
2494                        -> Ty<'tcx>
2495 {
2496     let tcx = fcx.ccx.tcx;
2497
2498     match lit.node {
2499         ast::LitStr(..) => tcx.mk_static_str(),
2500         ast::LitBinary(ref v) => {
2501             tcx.mk_imm_ref(tcx.mk_region(ty::ReStatic),
2502                             tcx.mk_array(tcx.types.u8, v.len()))
2503         }
2504         ast::LitByte(_) => tcx.types.u8,
2505         ast::LitChar(_) => tcx.types.char,
2506         ast::LitInt(_, ast::SignedIntLit(t, _)) => tcx.mk_mach_int(t),
2507         ast::LitInt(_, ast::UnsignedIntLit(t)) => tcx.mk_mach_uint(t),
2508         ast::LitInt(_, ast::UnsuffixedIntLit(_)) => {
2509             let opt_ty = expected.to_option(fcx).and_then(|ty| {
2510                 match ty.sty {
2511                     ty::TyInt(_) | ty::TyUint(_) => Some(ty),
2512                     ty::TyChar => Some(tcx.types.u8),
2513                     ty::TyRawPtr(..) => Some(tcx.types.usize),
2514                     ty::TyBareFn(..) => Some(tcx.types.usize),
2515                     _ => None
2516                 }
2517             });
2518             opt_ty.unwrap_or_else(
2519                 || tcx.mk_int_var(fcx.infcx().next_int_var_id()))
2520         }
2521         ast::LitFloat(_, t) => tcx.mk_mach_float(t),
2522         ast::LitFloatUnsuffixed(_) => {
2523             let opt_ty = expected.to_option(fcx).and_then(|ty| {
2524                 match ty.sty {
2525                     ty::TyFloat(_) => Some(ty),
2526                     _ => None
2527                 }
2528             });
2529             opt_ty.unwrap_or_else(
2530                 || tcx.mk_float_var(fcx.infcx().next_float_var_id()))
2531         }
2532         ast::LitBool(_) => tcx.types.bool
2533     }
2534 }
2535
2536 pub fn check_expr_has_type<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2537                                      expr: &'tcx ast::Expr,
2538                                      expected: Ty<'tcx>) {
2539     check_expr_with_unifier(
2540         fcx, expr, ExpectHasType(expected), NoPreference,
2541         || demand::suptype(fcx, expr.span, expected, fcx.expr_ty(expr)));
2542 }
2543
2544 fn check_expr_coercable_to_type<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2545                                           expr: &'tcx ast::Expr,
2546                                           expected: Ty<'tcx>) {
2547     check_expr_with_unifier(
2548         fcx, expr, ExpectHasType(expected), NoPreference,
2549         || demand::coerce(fcx, expr.span, expected, expr));
2550 }
2551
2552 fn check_expr_with_hint<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>, expr: &'tcx ast::Expr,
2553                                   expected: Ty<'tcx>) {
2554     check_expr_with_unifier(
2555         fcx, expr, ExpectHasType(expected), NoPreference,
2556         || ())
2557 }
2558
2559 fn check_expr_with_expectation<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2560                                          expr: &'tcx ast::Expr,
2561                                          expected: Expectation<'tcx>) {
2562     check_expr_with_unifier(
2563         fcx, expr, expected, NoPreference,
2564         || ())
2565 }
2566
2567 fn check_expr_with_expectation_and_lvalue_pref<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2568                                                          expr: &'tcx ast::Expr,
2569                                                          expected: Expectation<'tcx>,
2570                                                          lvalue_pref: LvaluePreference)
2571 {
2572     check_expr_with_unifier(fcx, expr, expected, lvalue_pref, || ())
2573 }
2574
2575 fn check_expr<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>, expr: &'tcx ast::Expr)  {
2576     check_expr_with_unifier(fcx, expr, NoExpectation, NoPreference, || ())
2577 }
2578
2579 fn check_expr_with_lvalue_pref<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>, expr: &'tcx ast::Expr,
2580                                         lvalue_pref: LvaluePreference)  {
2581     check_expr_with_unifier(fcx, expr, NoExpectation, lvalue_pref, || ())
2582 }
2583
2584 // determine the `self` type, using fresh variables for all variables
2585 // declared on the impl declaration e.g., `impl<A,B> for Vec<(A,B)>`
2586 // would return ($0, $1) where $0 and $1 are freshly instantiated type
2587 // variables.
2588 pub fn impl_self_ty<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2589                               span: Span, // (potential) receiver for this impl
2590                               did: ast::DefId)
2591                               -> TypeAndSubsts<'tcx> {
2592     let tcx = fcx.tcx();
2593
2594     let ity = tcx.lookup_item_type(did);
2595     let (tps, rps, raw_ty) =
2596         (ity.generics.types.get_slice(subst::TypeSpace),
2597          ity.generics.regions.get_slice(subst::TypeSpace),
2598          ity.ty);
2599
2600     debug!("impl_self_ty: tps={:?} rps={:?} raw_ty={:?}", tps, rps, raw_ty);
2601
2602     let rps = fcx.inh.infcx.region_vars_for_defs(span, rps);
2603     let tps = fcx.inh.infcx.type_vars_for_defs(span, tps);
2604     let substs = subst::Substs::new_type(tps, rps);
2605     let substd_ty = fcx.instantiate_type_scheme(span, &substs, &raw_ty);
2606
2607     TypeAndSubsts { substs: substs, ty: substd_ty }
2608 }
2609
2610 /// Controls whether the arguments are tupled. This is used for the call
2611 /// operator.
2612 ///
2613 /// Tupling means that all call-side arguments are packed into a tuple and
2614 /// passed as a single parameter. For example, if tupling is enabled, this
2615 /// function:
2616 ///
2617 ///     fn f(x: (isize, isize))
2618 ///
2619 /// Can be called as:
2620 ///
2621 ///     f(1, 2);
2622 ///
2623 /// Instead of:
2624 ///
2625 ///     f((1, 2));
2626 #[derive(Clone, Eq, PartialEq)]
2627 enum TupleArgumentsFlag {
2628     DontTupleArguments,
2629     TupleArguments,
2630 }
2631
2632 /// Unifies the return type with the expected type early, for more coercions
2633 /// and forward type information on the argument expressions.
2634 fn expected_types_for_fn_args<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2635                                         call_span: Span,
2636                                         expected_ret: Expectation<'tcx>,
2637                                         formal_ret: ty::FnOutput<'tcx>,
2638                                         formal_args: &[Ty<'tcx>])
2639                                         -> Vec<Ty<'tcx>> {
2640     let expected_args = expected_ret.only_has_type(fcx).and_then(|ret_ty| {
2641         if let ty::FnConverging(formal_ret_ty) = formal_ret {
2642             fcx.infcx().commit_regions_if_ok(|| {
2643                 // Attempt to apply a subtyping relationship between the formal
2644                 // return type (likely containing type variables if the function
2645                 // is polymorphic) and the expected return type.
2646                 // No argument expectations are produced if unification fails.
2647                 let origin = infer::Misc(call_span);
2648                 let ures = fcx.infcx().sub_types(false, origin, formal_ret_ty, ret_ty);
2649                 // FIXME(#15760) can't use try! here, FromError doesn't default
2650                 // to identity so the resulting type is not constrained.
2651                 if let Err(e) = ures {
2652                     return Err(e);
2653                 }
2654
2655                 // Record all the argument types, with the substitutions
2656                 // produced from the above subtyping unification.
2657                 Ok(formal_args.iter().map(|ty| {
2658                     fcx.infcx().resolve_type_vars_if_possible(ty)
2659                 }).collect())
2660             }).ok()
2661         } else {
2662             None
2663         }
2664     }).unwrap_or(vec![]);
2665     debug!("expected_types_for_fn_args(formal={:?} -> {:?}, expected={:?} -> {:?})",
2666            formal_args, formal_ret,
2667            expected_args, expected_ret);
2668     expected_args
2669 }
2670
2671 /// Invariant:
2672 /// If an expression has any sub-expressions that result in a type error,
2673 /// inspecting that expression's type with `ty.references_error()` will return
2674 /// true. Likewise, if an expression is known to diverge, inspecting its
2675 /// type with `ty::type_is_bot` will return true (n.b.: since Rust is
2676 /// strict, _|_ can appear in the type of an expression that does not,
2677 /// itself, diverge: for example, fn() -> _|_.)
2678 /// Note that inspecting a type's structure *directly* may expose the fact
2679 /// that there are actually multiple representations for `TyError`, so avoid
2680 /// that when err needs to be handled differently.
2681 fn check_expr_with_unifier<'a, 'tcx, F>(fcx: &FnCtxt<'a, 'tcx>,
2682                                         expr: &'tcx ast::Expr,
2683                                         expected: Expectation<'tcx>,
2684                                         lvalue_pref: LvaluePreference,
2685                                         unifier: F) where
2686     F: FnOnce(),
2687 {
2688     debug!(">> typechecking: expr={:?} expected={:?}",
2689            expr, expected);
2690
2691     // Checks a method call.
2692     fn check_method_call<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2693                                    expr: &'tcx ast::Expr,
2694                                    method_name: ast::SpannedIdent,
2695                                    args: &'tcx [P<ast::Expr>],
2696                                    tps: &[P<ast::Ty>],
2697                                    expected: Expectation<'tcx>,
2698                                    lvalue_pref: LvaluePreference) {
2699         let rcvr = &*args[0];
2700         check_expr_with_lvalue_pref(fcx, &*rcvr, lvalue_pref);
2701
2702         // no need to check for bot/err -- callee does that
2703         let expr_t = structurally_resolved_type(fcx,
2704                                                 expr.span,
2705                                                 fcx.expr_ty(&*rcvr));
2706
2707         let tps = tps.iter().map(|ast_ty| fcx.to_ty(&**ast_ty)).collect::<Vec<_>>();
2708         let fn_ty = match method::lookup(fcx,
2709                                          method_name.span,
2710                                          method_name.node.name,
2711                                          expr_t,
2712                                          tps,
2713                                          expr,
2714                                          rcvr) {
2715             Ok(method) => {
2716                 let method_ty = method.ty;
2717                 let method_call = MethodCall::expr(expr.id);
2718                 fcx.inh.tables.borrow_mut().method_map.insert(method_call, method);
2719                 method_ty
2720             }
2721             Err(error) => {
2722                 method::report_error(fcx, method_name.span, expr_t,
2723                                      method_name.node.name, Some(rcvr), error);
2724                 fcx.write_error(expr.id);
2725                 fcx.tcx().types.err
2726             }
2727         };
2728
2729         // Call the generic checker.
2730         let ret_ty = check_method_argument_types(fcx,
2731                                                  method_name.span,
2732                                                  fn_ty,
2733                                                  expr,
2734                                                  &args[1..],
2735                                                  DontTupleArguments,
2736                                                  expected);
2737
2738         write_call(fcx, expr, ret_ty);
2739     }
2740
2741     // A generic function for checking the then and else in an if
2742     // or if-else.
2743     fn check_then_else<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2744                                  cond_expr: &'tcx ast::Expr,
2745                                  then_blk: &'tcx ast::Block,
2746                                  opt_else_expr: Option<&'tcx ast::Expr>,
2747                                  id: ast::NodeId,
2748                                  sp: Span,
2749                                  expected: Expectation<'tcx>) {
2750         check_expr_has_type(fcx, cond_expr, fcx.tcx().types.bool);
2751
2752         let expected = expected.adjust_for_branches(fcx);
2753         check_block_with_expected(fcx, then_blk, expected);
2754         let then_ty = fcx.node_ty(then_blk.id);
2755
2756         let branches_ty = match opt_else_expr {
2757             Some(ref else_expr) => {
2758                 check_expr_with_expectation(fcx, &**else_expr, expected);
2759                 let else_ty = fcx.expr_ty(&**else_expr);
2760                 infer::common_supertype(fcx.infcx(),
2761                                         infer::IfExpression(sp),
2762                                         true,
2763                                         then_ty,
2764                                         else_ty)
2765             }
2766             None => {
2767                 infer::common_supertype(fcx.infcx(),
2768                                         infer::IfExpressionWithNoElse(sp),
2769                                         false,
2770                                         then_ty,
2771                                         fcx.tcx().mk_nil())
2772             }
2773         };
2774
2775         let cond_ty = fcx.expr_ty(cond_expr);
2776         let if_ty = if cond_ty.references_error() {
2777             fcx.tcx().types.err
2778         } else {
2779             branches_ty
2780         };
2781
2782         fcx.write_ty(id, if_ty);
2783     }
2784
2785     // Check field access expressions
2786     fn check_field<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
2787                             expr: &'tcx ast::Expr,
2788                             lvalue_pref: LvaluePreference,
2789                             base: &'tcx ast::Expr,
2790                             field: &ast::SpannedIdent) {
2791         let tcx = fcx.ccx.tcx;
2792         check_expr_with_lvalue_pref(fcx, base, lvalue_pref);
2793         let expr_t = structurally_resolved_type(fcx, expr.span,
2794                                                 fcx.expr_ty(base));
2795         // FIXME(eddyb) #12808 Integrate privacy into this auto-deref loop.
2796         let (_, autoderefs, field_ty) = autoderef(fcx,
2797                                                   expr.span,
2798                                                   expr_t,
2799                                                   Some(base),
2800                                                   UnresolvedTypeAction::Error,
2801                                                   lvalue_pref,
2802                                                   |base_t, _| {
2803                 match base_t.sty {
2804                     ty::TyStruct(base_id, substs) => {
2805                         debug!("struct named {:?}",  base_t);
2806                         let fields = tcx.lookup_struct_fields(base_id);
2807                         fcx.lookup_field_ty(expr.span, base_id, &fields[..],
2808                                             field.node.name, &(*substs))
2809                     }
2810                     _ => None
2811                 }
2812             });
2813         match field_ty {
2814             Some(field_ty) => {
2815                 fcx.write_ty(expr.id, field_ty);
2816                 fcx.write_autoderef_adjustment(base.id, autoderefs);
2817                 return;
2818             }
2819             None => {}
2820         }
2821
2822         if method::exists(fcx, field.span, field.node.name, expr_t, expr.id) {
2823             fcx.type_error_message(
2824                 field.span,
2825                 |actual| {
2826                     format!("attempted to take value of method `{}` on type \
2827                             `{}`", token::get_ident(field.node), actual)
2828                 },
2829                 expr_t, None);
2830
2831             tcx.sess.fileline_help(field.span,
2832                                "maybe a `()` to call it is missing? \
2833                                If not, try an anonymous function");
2834         } else {
2835             fcx.type_error_message(
2836                 expr.span,
2837                 |actual| {
2838                     format!("attempted access of field `{}` on \
2839                             type `{}`, but no field with that \
2840                             name was found",
2841                             token::get_ident(field.node),
2842                             actual)
2843                 },
2844                 expr_t, None);
2845             if let ty::TyStruct(did, _) = expr_t.sty {
2846                 suggest_field_names(did, field, tcx, vec![]);
2847             }
2848         }
2849
2850         fcx.write_error(expr.id);
2851     }
2852
2853     // displays hints about the closest matches in field names
2854     fn suggest_field_names<'tcx>(id : DefId,
2855                                  field : &ast::SpannedIdent,
2856                                  tcx : &ty::ctxt<'tcx>,
2857                                  skip : Vec<&str>) {
2858         let ident = token::get_ident(field.node);
2859         let name = &ident;
2860         // only find fits with at least one matching letter
2861         let mut best_dist = name.len();
2862         let fields = tcx.lookup_struct_fields(id);
2863         let mut best = None;
2864         for elem in &fields {
2865             let n = elem.name.as_str();
2866             // ignore already set fields
2867             if skip.iter().any(|&x| x == n) {
2868                 continue;
2869             }
2870             // ignore private fields from non-local crates
2871             if id.krate != ast::LOCAL_CRATE && elem.vis != Visibility::Public {
2872                 continue;
2873             }
2874             let dist = lev_distance(n, name);
2875             if dist < best_dist {
2876                 best = Some(n);
2877                 best_dist = dist;
2878             }
2879         }
2880         if let Some(n) = best {
2881             tcx.sess.span_help(field.span,
2882                 &format!("did you mean `{}`?", n));
2883         }
2884     }
2885
2886     // Check tuple index expressions
2887     fn check_tup_field<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
2888                                 expr: &'tcx ast::Expr,
2889                                 lvalue_pref: LvaluePreference,
2890                                 base: &'tcx ast::Expr,
2891                                 idx: codemap::Spanned<usize>) {
2892         let tcx = fcx.ccx.tcx;
2893         check_expr_with_lvalue_pref(fcx, base, lvalue_pref);
2894         let expr_t = structurally_resolved_type(fcx, expr.span,
2895                                                 fcx.expr_ty(base));
2896         let mut tuple_like = false;
2897         // FIXME(eddyb) #12808 Integrate privacy into this auto-deref loop.
2898         let (_, autoderefs, field_ty) = autoderef(fcx,
2899                                                   expr.span,
2900                                                   expr_t,
2901                                                   Some(base),
2902                                                   UnresolvedTypeAction::Error,
2903                                                   lvalue_pref,
2904                                                   |base_t, _| {
2905                 match base_t.sty {
2906                     ty::TyStruct(base_id, substs) => {
2907                         tuple_like = tcx.is_tuple_struct(base_id);
2908                         if tuple_like {
2909                             debug!("tuple struct named {:?}",  base_t);
2910                             let fields = tcx.lookup_struct_fields(base_id);
2911                             fcx.lookup_tup_field_ty(expr.span, base_id, &fields[..],
2912                                                     idx.node, &(*substs))
2913                         } else {
2914                             None
2915                         }
2916                     }
2917                     ty::TyTuple(ref v) => {
2918                         tuple_like = true;
2919                         if idx.node < v.len() { Some(v[idx.node]) } else { None }
2920                     }
2921                     _ => None
2922                 }
2923             });
2924         match field_ty {
2925             Some(field_ty) => {
2926                 fcx.write_ty(expr.id, field_ty);
2927                 fcx.write_autoderef_adjustment(base.id, autoderefs);
2928                 return;
2929             }
2930             None => {}
2931         }
2932         fcx.type_error_message(
2933             expr.span,
2934             |actual| {
2935                 if tuple_like {
2936                     format!("attempted out-of-bounds tuple index `{}` on \
2937                                     type `{}`",
2938                                    idx.node,
2939                                    actual)
2940                 } else {
2941                     format!("attempted tuple index `{}` on type `{}`, but the \
2942                                      type was not a tuple or tuple struct",
2943                                     idx.node,
2944                                     actual)
2945                 }
2946             },
2947             expr_t, None);
2948
2949         fcx.write_error(expr.id);
2950     }
2951
2952     fn check_struct_or_variant_fields<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
2953                                                 struct_ty: Ty<'tcx>,
2954                                                 span: Span,
2955                                                 class_id: ast::DefId,
2956                                                 node_id: ast::NodeId,
2957                                                 substitutions: &'tcx subst::Substs<'tcx>,
2958                                                 field_types: &[ty::FieldTy],
2959                                                 ast_fields: &'tcx [ast::Field],
2960                                                 check_completeness: bool,
2961                                                 enum_id_opt: Option<ast::DefId>)  {
2962         let tcx = fcx.ccx.tcx;
2963
2964         let mut class_field_map = FnvHashMap();
2965         let mut fields_found = 0;
2966         for field in field_types {
2967             class_field_map.insert(field.name, (field.id, false));
2968         }
2969
2970         let mut error_happened = false;
2971
2972         // Typecheck each field.
2973         for field in ast_fields {
2974             let mut expected_field_type = tcx.types.err;
2975
2976             let pair = class_field_map.get(&field.ident.node.name).cloned();
2977             match pair {
2978                 None => {
2979                     fcx.type_error_message(
2980                         field.ident.span,
2981                         |actual| match enum_id_opt {
2982                             Some(enum_id) => {
2983                                 let variant_type = tcx.enum_variant_with_id(enum_id,
2984                                                                             class_id);
2985                                 format!("struct variant `{}::{}` has no field named `{}`",
2986                                         actual, variant_type.name.as_str(),
2987                                         token::get_ident(field.ident.node))
2988                             }
2989                             None => {
2990                                 format!("structure `{}` has no field named `{}`",
2991                                         actual,
2992                                         token::get_ident(field.ident.node))
2993                             }
2994                         },
2995                         struct_ty,
2996                         None);
2997                     // prevent all specified fields from being suggested
2998                     let skip_fields = ast_fields.iter().map(|ref x| x.ident.node.name.as_str());
2999                     let actual_id = match enum_id_opt {
3000                         Some(_) => class_id,
3001                         None => struct_ty.ty_to_def_id().unwrap()
3002                     };
3003                     suggest_field_names(actual_id, &field.ident, tcx, skip_fields.collect());
3004                     error_happened = true;
3005                 }
3006                 Some((_, true)) => {
3007                     span_err!(fcx.tcx().sess, field.ident.span, E0062,
3008                         "field `{}` specified more than once",
3009                         token::get_ident(field.ident.node));
3010                     error_happened = true;
3011                 }
3012                 Some((field_id, false)) => {
3013                     expected_field_type =
3014                         tcx.lookup_field_type(class_id, field_id, substitutions);
3015                     expected_field_type =
3016                         fcx.normalize_associated_types_in(
3017                             field.span, &expected_field_type);
3018                     class_field_map.insert(
3019                         field.ident.node.name, (field_id, true));
3020                     fields_found += 1;
3021                 }
3022             }
3023
3024             // Make sure to give a type to the field even if there's
3025             // an error, so we can continue typechecking
3026             check_expr_coercable_to_type(fcx, &*field.expr, expected_field_type);
3027         }
3028
3029         if error_happened {
3030             fcx.write_error(node_id);
3031         }
3032
3033         if check_completeness && !error_happened {
3034             // Make sure the programmer specified all the fields.
3035             assert!(fields_found <= field_types.len());
3036             if fields_found < field_types.len() {
3037                 let mut missing_fields = Vec::new();
3038                 for class_field in field_types {
3039                     let name = class_field.name;
3040                     let (_, seen) = *class_field_map.get(&name).unwrap();
3041                     if !seen {
3042                         missing_fields.push(
3043                             format!("`{}`", &token::get_name(name)))
3044                     }
3045                 }
3046
3047                 span_err!(tcx.sess, span, E0063,
3048                     "missing field{}: {}",
3049                     if missing_fields.len() == 1 {""} else {"s"},
3050                     missing_fields.join(", "));
3051              }
3052         }
3053
3054         if !error_happened {
3055             fcx.write_ty(node_id, fcx.ccx.tcx.mk_struct(class_id, substitutions));
3056         }
3057     }
3058
3059     fn check_struct_constructor<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
3060                                          id: ast::NodeId,
3061                                          span: codemap::Span,
3062                                          class_id: ast::DefId,
3063                                          fields: &'tcx [ast::Field],
3064                                          base_expr: Option<&'tcx ast::Expr>) {
3065         let tcx = fcx.ccx.tcx;
3066
3067         // Generate the struct type.
3068         let TypeAndSubsts {
3069             ty: mut struct_type,
3070             substs: struct_substs
3071         } = fcx.instantiate_type(span, class_id);
3072
3073         // Look up and check the fields.
3074         let class_fields = tcx.lookup_struct_fields(class_id);
3075         check_struct_or_variant_fields(fcx,
3076                                        struct_type,
3077                                        span,
3078                                        class_id,
3079                                        id,
3080                                        fcx.ccx.tcx.mk_substs(struct_substs),
3081                                        &class_fields[..],
3082                                        fields,
3083                                        base_expr.is_none(),
3084                                        None);
3085         if fcx.node_ty(id).references_error() {
3086             struct_type = tcx.types.err;
3087         }
3088
3089         // Check the base expression if necessary.
3090         match base_expr {
3091             None => {}
3092             Some(base_expr) => {
3093                 check_expr_has_type(fcx, &*base_expr, struct_type);
3094             }
3095         }
3096
3097         // Write in the resulting type.
3098         fcx.write_ty(id, struct_type);
3099     }
3100
3101     fn check_struct_enum_variant<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
3102                                           id: ast::NodeId,
3103                                           span: codemap::Span,
3104                                           enum_id: ast::DefId,
3105                                           variant_id: ast::DefId,
3106                                           fields: &'tcx [ast::Field]) {
3107         let tcx = fcx.ccx.tcx;
3108
3109         // Look up the number of type parameters and the raw type, and
3110         // determine whether the enum is region-parameterized.
3111         let TypeAndSubsts {
3112             ty: enum_type,
3113             substs: substitutions
3114         } = fcx.instantiate_type(span, enum_id);
3115
3116         // Look up and check the enum variant fields.
3117         let variant_fields = tcx.lookup_struct_fields(variant_id);
3118         check_struct_or_variant_fields(fcx,
3119                                        enum_type,
3120                                        span,
3121                                        variant_id,
3122                                        id,
3123                                        fcx.ccx.tcx.mk_substs(substitutions),
3124                                        &variant_fields[..],
3125                                        fields,
3126                                        true,
3127                                        Some(enum_id));
3128         fcx.write_ty(id, enum_type);
3129     }
3130
3131     fn check_struct_fields_on_error<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
3132                                              id: ast::NodeId,
3133                                              fields: &'tcx [ast::Field],
3134                                              base_expr: &'tcx Option<P<ast::Expr>>) {
3135         // Make sure to still write the types
3136         // otherwise we might ICE
3137         fcx.write_error(id);
3138         for field in fields {
3139             check_expr(fcx, &*field.expr);
3140         }
3141         match *base_expr {
3142             Some(ref base) => check_expr(fcx, &**base),
3143             None => {}
3144         }
3145     }
3146
3147     type ExprCheckerWithTy = fn(&FnCtxt, &ast::Expr, Ty);
3148
3149     let tcx = fcx.ccx.tcx;
3150     let id = expr.id;
3151     match expr.node {
3152       ast::ExprBox(ref opt_place, ref subexpr) => {
3153           opt_place.as_ref().map(|place|check_expr(fcx, &**place));
3154           check_expr(fcx, &**subexpr);
3155
3156           let mut checked = false;
3157           opt_place.as_ref().map(|place| match place.node {
3158               ast::ExprPath(None, ref path) => {
3159                   // FIXME(pcwalton): For now we hardcode the only permissible
3160                   // place: the exchange heap.
3161                   let definition = lookup_full_def(tcx, path.span, place.id);
3162                   let def_id = definition.def_id();
3163                   let referent_ty = fcx.expr_ty(&**subexpr);
3164                   if tcx.lang_items.exchange_heap() == Some(def_id) {
3165                       fcx.write_ty(id, tcx.mk_box(referent_ty));
3166                       checked = true
3167                   }
3168               }
3169               _ => {}
3170           });
3171
3172           if !checked {
3173               span_err!(tcx.sess, expr.span, E0066,
3174                   "only the exchange heap is currently supported");
3175               fcx.write_ty(id, tcx.types.err);
3176           }
3177       }
3178
3179       ast::ExprLit(ref lit) => {
3180         let typ = check_lit(fcx, &**lit, expected);
3181         fcx.write_ty(id, typ);
3182       }
3183       ast::ExprBinary(op, ref lhs, ref rhs) => {
3184         op::check_binop(fcx, expr, op, lhs, rhs);
3185       }
3186       ast::ExprAssignOp(op, ref lhs, ref rhs) => {
3187         op::check_binop_assign(fcx, expr, op, lhs, rhs);
3188       }
3189       ast::ExprUnary(unop, ref oprnd) => {
3190         let expected_inner = expected.to_option(fcx).map_or(NoExpectation, |ty| {
3191             match unop {
3192                 ast::UnUniq => match ty.sty {
3193                     ty::TyBox(ty) => {
3194                         Expectation::rvalue_hint(ty)
3195                     }
3196                     _ => {
3197                         NoExpectation
3198                     }
3199                 },
3200                 ast::UnNot | ast::UnNeg => {
3201                     expected
3202                 }
3203                 ast::UnDeref => {
3204                     NoExpectation
3205                 }
3206             }
3207         });
3208         let lvalue_pref = match unop {
3209             ast::UnDeref => lvalue_pref,
3210             _ => NoPreference
3211         };
3212         check_expr_with_expectation_and_lvalue_pref(
3213             fcx, &**oprnd, expected_inner, lvalue_pref);
3214         let mut oprnd_t = fcx.expr_ty(&**oprnd);
3215
3216         if !oprnd_t.references_error() {
3217             match unop {
3218                 ast::UnUniq => {
3219                     oprnd_t = tcx.mk_box(oprnd_t);
3220                 }
3221                 ast::UnDeref => {
3222                     oprnd_t = structurally_resolved_type(fcx, expr.span, oprnd_t);
3223                     oprnd_t = match oprnd_t.builtin_deref(true) {
3224                         Some(mt) => mt.ty,
3225                         None => match try_overloaded_deref(fcx, expr.span,
3226                                                            Some(MethodCall::expr(expr.id)),
3227                                                            Some(&**oprnd), oprnd_t, lvalue_pref) {
3228                             Some(mt) => mt.ty,
3229                             None => {
3230                                 fcx.type_error_message(expr.span, |actual| {
3231                                     format!("type `{}` cannot be \
3232                                             dereferenced", actual)
3233                                 }, oprnd_t, None);
3234                                 tcx.types.err
3235                             }
3236                         }
3237                     };
3238                 }
3239                 ast::UnNot => {
3240                     oprnd_t = structurally_resolved_type(fcx, oprnd.span,
3241                                                          oprnd_t);
3242                     if !(oprnd_t.is_integral() || oprnd_t.sty == ty::TyBool) {
3243                         oprnd_t = op::check_user_unop(fcx, "!", "not",
3244                                                       tcx.lang_items.not_trait(),
3245                                                       expr, &**oprnd, oprnd_t, unop);
3246                     }
3247                 }
3248                 ast::UnNeg => {
3249                     oprnd_t = structurally_resolved_type(fcx, oprnd.span,
3250                                                          oprnd_t);
3251                     if !(oprnd_t.is_integral() || oprnd_t.is_fp()) {
3252                         oprnd_t = op::check_user_unop(fcx, "-", "neg",
3253                                                       tcx.lang_items.neg_trait(),
3254                                                       expr, &**oprnd, oprnd_t, unop);
3255                     }
3256                 }
3257             }
3258         }
3259         fcx.write_ty(id, oprnd_t);
3260       }
3261       ast::ExprAddrOf(mutbl, ref oprnd) => {
3262         let hint = expected.only_has_type(fcx).map_or(NoExpectation, |ty| {
3263             match ty.sty {
3264                 ty::TyRef(_, ref mt) | ty::TyRawPtr(ref mt) => {
3265                     if fcx.tcx().expr_is_lval(&**oprnd) {
3266                         // Lvalues may legitimately have unsized types.
3267                         // For example, dereferences of a fat pointer and
3268                         // the last field of a struct can be unsized.
3269                         ExpectHasType(mt.ty)
3270                     } else {
3271                         Expectation::rvalue_hint(mt.ty)
3272                     }
3273                 }
3274                 _ => NoExpectation
3275             }
3276         });
3277         let lvalue_pref = LvaluePreference::from_mutbl(mutbl);
3278         check_expr_with_expectation_and_lvalue_pref(fcx,
3279                                                     &**oprnd,
3280                                                     hint,
3281                                                     lvalue_pref);
3282
3283         let tm = ty::TypeAndMut { ty: fcx.expr_ty(&**oprnd), mutbl: mutbl };
3284         let oprnd_t = if tm.ty.references_error() {
3285             tcx.types.err
3286         } else {
3287             // Note: at this point, we cannot say what the best lifetime
3288             // is to use for resulting pointer.  We want to use the
3289             // shortest lifetime possible so as to avoid spurious borrowck
3290             // errors.  Moreover, the longest lifetime will depend on the
3291             // precise details of the value whose address is being taken
3292             // (and how long it is valid), which we don't know yet until type
3293             // inference is complete.
3294             //
3295             // Therefore, here we simply generate a region variable.  The
3296             // region inferencer will then select the ultimate value.
3297             // Finally, borrowck is charged with guaranteeing that the
3298             // value whose address was taken can actually be made to live
3299             // as long as it needs to live.
3300             let region = fcx.infcx().next_region_var(infer::AddrOfRegion(expr.span));
3301             tcx.mk_ref(tcx.mk_region(region), tm)
3302         };
3303         fcx.write_ty(id, oprnd_t);
3304       }
3305       ast::ExprPath(ref maybe_qself, ref path) => {
3306           let opt_self_ty = maybe_qself.as_ref().map(|qself| {
3307               fcx.to_ty(&qself.ty)
3308           });
3309
3310           let path_res = if let Some(&d) = tcx.def_map.borrow().get(&id) {
3311               d
3312           } else if let Some(ast::QSelf { position: 0, .. }) = *maybe_qself {
3313                 // Create some fake resolution that can't possibly be a type.
3314                 def::PathResolution {
3315                     base_def: def::DefMod(local_def(ast::CRATE_NODE_ID)),
3316                     last_private: LastMod(AllPublic),
3317                     depth: path.segments.len()
3318                 }
3319             } else {
3320               tcx.sess.span_bug(expr.span,
3321                                 &format!("unbound path {:?}", expr))
3322           };
3323
3324           if let Some((opt_ty, segments, def)) =
3325                   resolve_ty_and_def_ufcs(fcx, path_res, opt_self_ty, path,
3326                                           expr.span, expr.id) {
3327               let (scheme, predicates) = type_scheme_and_predicates_for_def(fcx,
3328                                                                             expr.span,
3329                                                                             def);
3330               instantiate_path(fcx,
3331                                segments,
3332                                scheme,
3333                                &predicates,
3334                                opt_ty,
3335                                def,
3336                                expr.span,
3337                                id);
3338           }
3339
3340           // We always require that the type provided as the value for
3341           // a type parameter outlives the moment of instantiation.
3342           constrain_path_type_parameters(fcx, expr);
3343       }
3344       ast::ExprInlineAsm(ref ia) => {
3345           for &(_, ref input) in &ia.inputs {
3346               check_expr(fcx, &**input);
3347           }
3348           for &(_, ref out, _) in &ia.outputs {
3349               check_expr(fcx, &**out);
3350           }
3351           fcx.write_nil(id);
3352       }
3353       ast::ExprMac(_) => tcx.sess.bug("unexpanded macro"),
3354       ast::ExprBreak(_) => { fcx.write_ty(id, fcx.infcx().next_diverging_ty_var()); }
3355       ast::ExprAgain(_) => { fcx.write_ty(id, fcx.infcx().next_diverging_ty_var()); }
3356       ast::ExprRet(ref expr_opt) => {
3357         match fcx.ret_ty {
3358             ty::FnConverging(result_type) => {
3359                 match *expr_opt {
3360                     None =>
3361                         if let Err(_) = fcx.mk_eqty(false, infer::Misc(expr.span),
3362                                                     result_type, fcx.tcx().mk_nil()) {
3363                             span_err!(tcx.sess, expr.span, E0069,
3364                                 "`return;` in a function whose return type is \
3365                                  not `()`");
3366                         },
3367                     Some(ref e) => {
3368                         check_expr_coercable_to_type(fcx, &**e, result_type);
3369                     }
3370                 }
3371             }
3372             ty::FnDiverging => {
3373                 if let Some(ref e) = *expr_opt {
3374                     check_expr(fcx, &**e);
3375                 }
3376                 span_err!(tcx.sess, expr.span, E0166,
3377                     "`return` in a function declared as diverging");
3378             }
3379         }
3380         fcx.write_ty(id, fcx.infcx().next_diverging_ty_var());
3381       }
3382       ast::ExprParen(ref a) => {
3383         check_expr_with_expectation_and_lvalue_pref(fcx,
3384                                                     &**a,
3385                                                     expected,
3386                                                     lvalue_pref);
3387         fcx.write_ty(id, fcx.expr_ty(&**a));
3388       }
3389       ast::ExprAssign(ref lhs, ref rhs) => {
3390         check_expr_with_lvalue_pref(fcx, &**lhs, PreferMutLvalue);
3391
3392         let tcx = fcx.tcx();
3393         if !tcx.expr_is_lval(&**lhs) {
3394             span_err!(tcx.sess, expr.span, E0070,
3395                 "illegal left-hand side expression");
3396         }
3397
3398         let lhs_ty = fcx.expr_ty(&**lhs);
3399         check_expr_coercable_to_type(fcx, &**rhs, lhs_ty);
3400         let rhs_ty = fcx.expr_ty(&**rhs);
3401
3402         fcx.require_expr_have_sized_type(&**lhs, traits::AssignmentLhsSized);
3403
3404         if lhs_ty.references_error() || rhs_ty.references_error() {
3405             fcx.write_error(id);
3406         } else {
3407             fcx.write_nil(id);
3408         }
3409       }
3410       ast::ExprIf(ref cond, ref then_blk, ref opt_else_expr) => {
3411         check_then_else(fcx, &**cond, &**then_blk, opt_else_expr.as_ref().map(|e| &**e),
3412                         id, expr.span, expected);
3413       }
3414       ast::ExprIfLet(..) => {
3415         tcx.sess.span_bug(expr.span, "non-desugared ExprIfLet");
3416       }
3417       ast::ExprWhile(ref cond, ref body, _) => {
3418         check_expr_has_type(fcx, &**cond, tcx.types.bool);
3419         check_block_no_value(fcx, &**body);
3420         let cond_ty = fcx.expr_ty(&**cond);
3421         let body_ty = fcx.node_ty(body.id);
3422         if cond_ty.references_error() || body_ty.references_error() {
3423             fcx.write_error(id);
3424         }
3425         else {
3426             fcx.write_nil(id);
3427         }
3428       }
3429       ast::ExprWhileLet(..) => {
3430         tcx.sess.span_bug(expr.span, "non-desugared ExprWhileLet");
3431       }
3432       ast::ExprForLoop(..) => {
3433         tcx.sess.span_bug(expr.span, "non-desugared ExprForLoop");
3434       }
3435       ast::ExprLoop(ref body, _) => {
3436         check_block_no_value(fcx, &**body);
3437         if !may_break(tcx, expr.id, &**body) {
3438             fcx.write_ty(id, fcx.infcx().next_diverging_ty_var());
3439         } else {
3440             fcx.write_nil(id);
3441         }
3442       }
3443       ast::ExprMatch(ref discrim, ref arms, match_src) => {
3444         _match::check_match(fcx, expr, &**discrim, arms, expected, match_src);
3445       }
3446       ast::ExprClosure(capture, ref decl, ref body) => {
3447           closure::check_expr_closure(fcx, expr, capture, &**decl, &**body, expected);
3448       }
3449       ast::ExprBlock(ref b) => {
3450         check_block_with_expected(fcx, &**b, expected);
3451         fcx.write_ty(id, fcx.node_ty(b.id));
3452       }
3453       ast::ExprCall(ref callee, ref args) => {
3454           callee::check_call(fcx, expr, &**callee, &args[..], expected);
3455       }
3456       ast::ExprMethodCall(ident, ref tps, ref args) => {
3457         check_method_call(fcx, expr, ident, &args[..], &tps[..], expected, lvalue_pref);
3458         let arg_tys = args.iter().map(|a| fcx.expr_ty(&**a));
3459         let  args_err = arg_tys.fold(false,
3460              |rest_err, a| {
3461               rest_err || a.references_error()});
3462         if args_err {
3463             fcx.write_error(id);
3464         }
3465       }
3466       ast::ExprCast(ref e, ref t) => {
3467         if let ast::TyFixedLengthVec(_, ref count_expr) = t.node {
3468             check_expr_with_hint(fcx, &**count_expr, tcx.types.usize);
3469         }
3470
3471         // Find the type of `e`. Supply hints based on the type we are casting to,
3472         // if appropriate.
3473         let t_cast = fcx.to_ty(t);
3474         let t_cast = structurally_resolved_type(fcx, expr.span, t_cast);
3475         check_expr_with_expectation(fcx, e, ExpectCastableToType(t_cast));
3476         let t_expr = fcx.expr_ty(e);
3477
3478         // Eagerly check for some obvious errors.
3479         if t_expr.references_error() {
3480             fcx.write_error(id);
3481         } else if !fcx.type_is_known_to_be_sized(t_cast, expr.span) {
3482             report_cast_to_unsized_type(fcx, expr.span, t.span, e.span, t_cast, t_expr, id);
3483         } else {
3484             // Write a type for the whole expression, assuming everything is going
3485             // to work out Ok.
3486             fcx.write_ty(id, t_cast);
3487
3488             // Defer other checks until we're done type checking.
3489             let mut deferred_cast_checks = fcx.inh.deferred_cast_checks.borrow_mut();
3490             let cast_check = cast::CastCheck::new((**e).clone(), t_expr, t_cast, expr.span);
3491             deferred_cast_checks.push(cast_check);
3492         }
3493       }
3494       ast::ExprVec(ref args) => {
3495         let uty = expected.to_option(fcx).and_then(|uty| {
3496             match uty.sty {
3497                 ty::TyArray(ty, _) | ty::TySlice(ty) => Some(ty),
3498                 _ => None
3499             }
3500         });
3501
3502         let typ = match uty {
3503             Some(uty) => {
3504                 for e in args {
3505                     check_expr_coercable_to_type(fcx, &**e, uty);
3506                 }
3507                 uty
3508             }
3509             None => {
3510                 let t: Ty = fcx.infcx().next_ty_var();
3511                 for e in args {
3512                     check_expr_has_type(fcx, &**e, t);
3513                 }
3514                 t
3515             }
3516         };
3517         let typ = tcx.mk_array(typ, args.len());
3518         fcx.write_ty(id, typ);
3519       }
3520       ast::ExprRepeat(ref element, ref count_expr) => {
3521         check_expr_has_type(fcx, &**count_expr, tcx.types.usize);
3522         let count = fcx.tcx().eval_repeat_count(&**count_expr);
3523
3524         let uty = match expected {
3525             ExpectHasType(uty) => {
3526                 match uty.sty {
3527                     ty::TyArray(ty, _) | ty::TySlice(ty) => Some(ty),
3528                     _ => None
3529                 }
3530             }
3531             _ => None
3532         };
3533
3534         let (element_ty, t) = match uty {
3535             Some(uty) => {
3536                 check_expr_coercable_to_type(fcx, &**element, uty);
3537                 (uty, uty)
3538             }
3539             None => {
3540                 let t: Ty = fcx.infcx().next_ty_var();
3541                 check_expr_has_type(fcx, &**element, t);
3542                 (fcx.expr_ty(&**element), t)
3543             }
3544         };
3545
3546         if count > 1 {
3547             // For [foo, ..n] where n > 1, `foo` must have
3548             // Copy type:
3549             fcx.require_type_meets(
3550                 t,
3551                 expr.span,
3552                 traits::RepeatVec,
3553                 ty::BoundCopy);
3554         }
3555
3556         if element_ty.references_error() {
3557             fcx.write_error(id);
3558         } else {
3559             let t = tcx.mk_array(t, count);
3560             fcx.write_ty(id, t);
3561         }
3562       }
3563       ast::ExprTup(ref elts) => {
3564         let flds = expected.only_has_type(fcx).and_then(|ty| {
3565             match ty.sty {
3566                 ty::TyTuple(ref flds) => Some(&flds[..]),
3567                 _ => None
3568             }
3569         });
3570         let mut err_field = false;
3571
3572         let elt_ts = elts.iter().enumerate().map(|(i, e)| {
3573             let t = match flds {
3574                 Some(ref fs) if i < fs.len() => {
3575                     let ety = fs[i];
3576                     check_expr_coercable_to_type(fcx, &**e, ety);
3577                     ety
3578                 }
3579                 _ => {
3580                     check_expr_with_expectation(fcx, &**e, NoExpectation);
3581                     fcx.expr_ty(&**e)
3582                 }
3583             };
3584             err_field = err_field || t.references_error();
3585             t
3586         }).collect();
3587         if err_field {
3588             fcx.write_error(id);
3589         } else {
3590             let typ = tcx.mk_tup(elt_ts);
3591             fcx.write_ty(id, typ);
3592         }
3593       }
3594       ast::ExprStruct(ref path, ref fields, ref base_expr) => {
3595         // Resolve the path.
3596         let def = lookup_full_def(tcx, path.span, id);
3597         let struct_id = match def {
3598             def::DefVariant(enum_id, variant_id, true) => {
3599                 if let &Some(ref base_expr) = base_expr {
3600                     span_err!(tcx.sess, base_expr.span, E0436,
3601                               "functional record update syntax requires a struct");
3602                     fcx.write_error(base_expr.id);
3603                 }
3604                 check_struct_enum_variant(fcx, id, expr.span, enum_id,
3605                                           variant_id, &fields[..]);
3606                 enum_id
3607             }
3608             def::DefTrait(def_id) => {
3609                 span_err!(tcx.sess, path.span, E0159,
3610                     "use of trait `{}` as a struct constructor",
3611                     pprust::path_to_string(path));
3612                 check_struct_fields_on_error(fcx,
3613                                              id,
3614                                              &fields[..],
3615                                              base_expr);
3616                 def_id
3617             },
3618             def => {
3619                 // Verify that this was actually a struct.
3620                 let typ = fcx.ccx.tcx.lookup_item_type(def.def_id());
3621                 match typ.ty.sty {
3622                     ty::TyStruct(struct_did, _) => {
3623                         check_struct_constructor(fcx,
3624                                                  id,
3625                                                  expr.span,
3626                                                  struct_did,
3627                                                  &fields[..],
3628                                                  base_expr.as_ref().map(|e| &**e));
3629                     }
3630                     _ => {
3631                         span_err!(tcx.sess, path.span, E0071,
3632                             "`{}` does not name a structure",
3633                             pprust::path_to_string(path));
3634                         check_struct_fields_on_error(fcx,
3635                                                      id,
3636                                                      &fields[..],
3637                                                      base_expr);
3638                     }
3639                 }
3640
3641                 def.def_id()
3642             }
3643         };
3644
3645         // Turn the path into a type and verify that that type unifies with
3646         // the resulting structure type. This is needed to handle type
3647         // parameters correctly.
3648         let actual_structure_type = fcx.expr_ty(&*expr);
3649         if !actual_structure_type.references_error() {
3650             let type_and_substs = fcx.instantiate_struct_literal_ty(struct_id, path);
3651             match fcx.mk_subty(false,
3652                                infer::Misc(path.span),
3653                                actual_structure_type,
3654                                type_and_substs.ty) {
3655                 Ok(()) => {}
3656                 Err(type_error) => {
3657                     span_err!(fcx.tcx().sess, path.span, E0235,
3658                                  "structure constructor specifies a \
3659                                          structure of type `{}`, but this \
3660                                          structure has type `{}`: {}",
3661                                          fcx.infcx()
3662                                             .ty_to_string(type_and_substs.ty),
3663                                          fcx.infcx()
3664                                             .ty_to_string(
3665                                                 actual_structure_type),
3666                                          type_error);
3667                     tcx.note_and_explain_type_err(&type_error, path.span);
3668                 }
3669             }
3670         }
3671
3672         fcx.require_expr_have_sized_type(expr, traits::StructInitializerSized);
3673       }
3674       ast::ExprField(ref base, ref field) => {
3675         check_field(fcx, expr, lvalue_pref, &**base, field);
3676       }
3677       ast::ExprTupField(ref base, idx) => {
3678         check_tup_field(fcx, expr, lvalue_pref, &**base, idx);
3679       }
3680       ast::ExprIndex(ref base, ref idx) => {
3681           check_expr_with_lvalue_pref(fcx, &**base, lvalue_pref);
3682           check_expr(fcx, &**idx);
3683
3684           let base_t = fcx.expr_ty(&**base);
3685           let idx_t = fcx.expr_ty(&**idx);
3686
3687           if base_t.references_error() {
3688               fcx.write_ty(id, base_t);
3689           } else if idx_t.references_error() {
3690               fcx.write_ty(id, idx_t);
3691           } else {
3692               let base_t = structurally_resolved_type(fcx, expr.span, base_t);
3693               match lookup_indexing(fcx, expr, base, base_t, idx_t, lvalue_pref) {
3694                   Some((index_ty, element_ty)) => {
3695                       let idx_expr_ty = fcx.expr_ty(idx);
3696                       demand::eqtype(fcx, expr.span, index_ty, idx_expr_ty);
3697                       fcx.write_ty(id, element_ty);
3698                   }
3699                   None => {
3700                       check_expr_has_type(fcx, &**idx, fcx.tcx().types.err);
3701                       fcx.type_error_message(
3702                           expr.span,
3703                           |actual| {
3704                               format!("cannot index a value of type `{}`",
3705                                       actual)
3706                           },
3707                           base_t,
3708                           None);
3709                       fcx.write_ty(id, fcx.tcx().types.err);
3710                   }
3711               }
3712           }
3713        }
3714        ast::ExprRange(ref start, ref end) => {
3715           let t_start = start.as_ref().map(|e| {
3716             check_expr(fcx, &**e);
3717             fcx.expr_ty(&**e)
3718           });
3719           let t_end = end.as_ref().map(|e| {
3720             check_expr(fcx, &**e);
3721             fcx.expr_ty(&**e)
3722           });
3723
3724           let idx_type = match (t_start, t_end) {
3725               (Some(ty), None) | (None, Some(ty)) => {
3726                   Some(ty)
3727               }
3728               (Some(t_start), Some(t_end)) if (t_start.references_error() ||
3729                                                t_end.references_error()) => {
3730                   Some(fcx.tcx().types.err)
3731               }
3732               (Some(t_start), Some(t_end)) => {
3733                   Some(infer::common_supertype(fcx.infcx(),
3734                                                infer::RangeExpression(expr.span),
3735                                                true,
3736                                                t_start,
3737                                                t_end))
3738               }
3739               _ => None
3740           };
3741
3742           // Note that we don't check the type of start/end satisfy any
3743           // bounds because right now the range structs do not have any. If we add
3744           // some bounds, then we'll need to check `t_start` against them here.
3745
3746           let range_type = match idx_type {
3747             Some(idx_type) if idx_type.references_error() => {
3748                 fcx.tcx().types.err
3749             }
3750             Some(idx_type) => {
3751                 // Find the did from the appropriate lang item.
3752                 let did = match (start, end) {
3753                     (&Some(_), &Some(_)) => tcx.lang_items.range_struct(),
3754                     (&Some(_), &None) => tcx.lang_items.range_from_struct(),
3755                     (&None, &Some(_)) => tcx.lang_items.range_to_struct(),
3756                     (&None, &None) => {
3757                         tcx.sess.span_bug(expr.span, "full range should be dealt with above")
3758                     }
3759                 };
3760
3761                 if let Some(did) = did {
3762                     let predicates = tcx.lookup_predicates(did);
3763                     let substs = Substs::new_type(vec![idx_type], vec![]);
3764                     let bounds = fcx.instantiate_bounds(expr.span, &substs, &predicates);
3765                     fcx.add_obligations_for_parameters(
3766                         traits::ObligationCause::new(expr.span,
3767                                                      fcx.body_id,
3768                                                      traits::ItemObligation(did)),
3769                         &bounds);
3770
3771                     tcx.mk_struct(did, tcx.mk_substs(substs))
3772                 } else {
3773                     span_err!(tcx.sess, expr.span, E0236, "no lang item for range syntax");
3774                     fcx.tcx().types.err
3775                 }
3776             }
3777             None => {
3778                 // Neither start nor end => RangeFull
3779                 if let Some(did) = tcx.lang_items.range_full_struct() {
3780                     let substs = Substs::new_type(vec![], vec![]);
3781                     tcx.mk_struct(did, tcx.mk_substs(substs))
3782                 } else {
3783                     span_err!(tcx.sess, expr.span, E0237, "no lang item for range syntax");
3784                     fcx.tcx().types.err
3785                 }
3786             }
3787           };
3788
3789           fcx.write_ty(id, range_type);
3790        }
3791
3792     }
3793
3794     debug!("type of expr({}) {} is...", expr.id,
3795            syntax::print::pprust::expr_to_string(expr));
3796     debug!("... {:?}, expected is {:?}",
3797            fcx.expr_ty(expr),
3798            expected);
3799
3800     unifier();
3801 }
3802
3803 pub fn resolve_ty_and_def_ufcs<'a, 'b, 'tcx>(fcx: &FnCtxt<'b, 'tcx>,
3804                                              path_res: def::PathResolution,
3805                                              opt_self_ty: Option<Ty<'tcx>>,
3806                                              path: &'a ast::Path,
3807                                              span: Span,
3808                                              node_id: ast::NodeId)
3809                                              -> Option<(Option<Ty<'tcx>>,
3810                                                         &'a [ast::PathSegment],
3811                                                         def::Def)>
3812 {
3813
3814     // Associated constants can't depend on generic types.
3815     fn have_disallowed_generic_consts<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
3816                                                 def: def::Def,
3817                                                 ty: Ty<'tcx>,
3818                                                 span: Span,
3819                                                 node_id: ast::NodeId) -> bool {
3820         match def {
3821             def::DefAssociatedConst(..) => {
3822                 if ty.has_param_types() || ty.has_self_ty() {
3823                     span_err!(fcx.sess(), span, E0329,
3824                               "Associated consts cannot depend \
3825                                on type parameters or Self.");
3826                     fcx.write_error(node_id);
3827                     return true;
3828                 }
3829             }
3830             _ => {}
3831         }
3832         false
3833     }
3834
3835     // If fully resolved already, we don't have to do anything.
3836     if path_res.depth == 0 {
3837         if let Some(ty) = opt_self_ty {
3838             if have_disallowed_generic_consts(fcx, path_res.full_def(), ty,
3839                                               span, node_id) {
3840                 return None;
3841             }
3842         }
3843         Some((opt_self_ty, &path.segments, path_res.base_def))
3844     } else {
3845         let mut def = path_res.base_def;
3846         let ty_segments = path.segments.split_last().unwrap().1;
3847         let base_ty_end = path.segments.len() - path_res.depth;
3848         let ty = astconv::finish_resolving_def_to_ty(fcx, fcx, span,
3849                                                      PathParamMode::Optional,
3850                                                      &mut def,
3851                                                      opt_self_ty,
3852                                                      &ty_segments[..base_ty_end],
3853                                                      &ty_segments[base_ty_end..]);
3854         let item_segment = path.segments.last().unwrap();
3855         let item_name = item_segment.identifier.name;
3856         match method::resolve_ufcs(fcx, span, item_name, ty, node_id) {
3857             Ok((def, lp)) => {
3858                 if have_disallowed_generic_consts(fcx, def, ty, span, node_id) {
3859                     return None;
3860                 }
3861                 // Write back the new resolution.
3862                 fcx.ccx.tcx.def_map.borrow_mut()
3863                        .insert(node_id, def::PathResolution {
3864                    base_def: def,
3865                    last_private: path_res.last_private.or(lp),
3866                    depth: 0
3867                 });
3868                 Some((Some(ty), slice::ref_slice(item_segment), def))
3869             }
3870             Err(error) => {
3871                 method::report_error(fcx, span, ty,
3872                                      item_name, None, error);
3873                 fcx.write_error(node_id);
3874                 None
3875             }
3876         }
3877     }
3878 }
3879
3880 fn constrain_path_type_parameters(fcx: &FnCtxt,
3881                                   expr: &ast::Expr)
3882 {
3883     fcx.opt_node_ty_substs(expr.id, |item_substs| {
3884         fcx.add_default_region_param_bounds(&item_substs.substs, expr);
3885     });
3886 }
3887
3888 impl<'tcx> Expectation<'tcx> {
3889     /// Provide an expectation for an rvalue expression given an *optional*
3890     /// hint, which is not required for type safety (the resulting type might
3891     /// be checked higher up, as is the case with `&expr` and `box expr`), but
3892     /// is useful in determining the concrete type.
3893     ///
3894     /// The primary use case is where the expected type is a fat pointer,
3895     /// like `&[isize]`. For example, consider the following statement:
3896     ///
3897     ///    let x: &[isize] = &[1, 2, 3];
3898     ///
3899     /// In this case, the expected type for the `&[1, 2, 3]` expression is
3900     /// `&[isize]`. If however we were to say that `[1, 2, 3]` has the
3901     /// expectation `ExpectHasType([isize])`, that would be too strong --
3902     /// `[1, 2, 3]` does not have the type `[isize]` but rather `[isize; 3]`.
3903     /// It is only the `&[1, 2, 3]` expression as a whole that can be coerced
3904     /// to the type `&[isize]`. Therefore, we propagate this more limited hint,
3905     /// which still is useful, because it informs integer literals and the like.
3906     /// See the test case `test/run-pass/coerce-expect-unsized.rs` and #20169
3907     /// for examples of where this comes up,.
3908     fn rvalue_hint(ty: Ty<'tcx>) -> Expectation<'tcx> {
3909         match ty.sty {
3910             ty::TySlice(_) | ty::TyTrait(..) => {
3911                 ExpectRvalueLikeUnsized(ty)
3912             }
3913             _ => ExpectHasType(ty)
3914         }
3915     }
3916
3917     // Resolves `expected` by a single level if it is a variable. If
3918     // there is no expected type or resolution is not possible (e.g.,
3919     // no constraints yet present), just returns `None`.
3920     fn resolve<'a>(self, fcx: &FnCtxt<'a, 'tcx>) -> Expectation<'tcx> {
3921         match self {
3922             NoExpectation => {
3923                 NoExpectation
3924             }
3925             ExpectCastableToType(t) => {
3926                 ExpectCastableToType(
3927                     fcx.infcx().resolve_type_vars_if_possible(&t))
3928             }
3929             ExpectHasType(t) => {
3930                 ExpectHasType(
3931                     fcx.infcx().resolve_type_vars_if_possible(&t))
3932             }
3933             ExpectRvalueLikeUnsized(t) => {
3934                 ExpectRvalueLikeUnsized(
3935                     fcx.infcx().resolve_type_vars_if_possible(&t))
3936             }
3937         }
3938     }
3939
3940     fn to_option<'a>(self, fcx: &FnCtxt<'a, 'tcx>) -> Option<Ty<'tcx>> {
3941         match self.resolve(fcx) {
3942             NoExpectation => None,
3943             ExpectCastableToType(ty) |
3944             ExpectHasType(ty) |
3945             ExpectRvalueLikeUnsized(ty) => Some(ty),
3946         }
3947     }
3948
3949     fn only_has_type<'a>(self, fcx: &FnCtxt<'a, 'tcx>) -> Option<Ty<'tcx>> {
3950         match self.resolve(fcx) {
3951             ExpectHasType(ty) => Some(ty),
3952             _ => None
3953         }
3954     }
3955 }
3956
3957 pub fn check_decl_initializer<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
3958                                        local: &'tcx ast::Local,
3959                                        init: &'tcx ast::Expr)
3960 {
3961     let ref_bindings = fcx.tcx().pat_contains_ref_binding(&local.pat);
3962
3963     let local_ty = fcx.local_ty(init.span, local.id);
3964     if let Some(m) = ref_bindings {
3965         // Somewhat subtle: if we have a `ref` binding in the pattern,
3966         // we want to avoid introducing coercions for the RHS. This is
3967         // both because it helps preserve sanity and, in the case of
3968         // ref mut, for soundness (issue #23116). In particular, in
3969         // the latter case, we need to be clear that the type of the
3970         // referent for the reference that results is *equal to* the
3971         // type of the lvalue it is referencing, and not some
3972         // supertype thereof.
3973         check_expr_with_lvalue_pref(fcx, init, LvaluePreference::from_mutbl(m));
3974         let init_ty = fcx.expr_ty(init);
3975         demand::eqtype(fcx, init.span, init_ty, local_ty);
3976     } else {
3977         check_expr_coercable_to_type(fcx, init, local_ty)
3978     };
3979 }
3980
3981 pub fn check_decl_local<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>, local: &'tcx ast::Local)  {
3982     let tcx = fcx.ccx.tcx;
3983
3984     let t = fcx.local_ty(local.span, local.id);
3985     fcx.write_ty(local.id, t);
3986
3987     if let Some(ref init) = local.init {
3988         check_decl_initializer(fcx, local, &**init);
3989         let init_ty = fcx.expr_ty(&**init);
3990         if init_ty.references_error() {
3991             fcx.write_ty(local.id, init_ty);
3992         }
3993     }
3994
3995     let pcx = pat_ctxt {
3996         fcx: fcx,
3997         map: pat_id_map(&tcx.def_map, &*local.pat),
3998     };
3999     _match::check_pat(&pcx, &*local.pat, t);
4000     let pat_ty = fcx.node_ty(local.pat.id);
4001     if pat_ty.references_error() {
4002         fcx.write_ty(local.id, pat_ty);
4003     }
4004 }
4005
4006 pub fn check_stmt<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>, stmt: &'tcx ast::Stmt)  {
4007     let node_id;
4008     let mut saw_bot = false;
4009     let mut saw_err = false;
4010     match stmt.node {
4011       ast::StmtDecl(ref decl, id) => {
4012         node_id = id;
4013         match decl.node {
4014           ast::DeclLocal(ref l) => {
4015               check_decl_local(fcx, &**l);
4016               let l_t = fcx.node_ty(l.id);
4017               saw_bot = saw_bot || fcx.infcx().type_var_diverges(l_t);
4018               saw_err = saw_err || l_t.references_error();
4019           }
4020           ast::DeclItem(_) => {/* ignore for now */ }
4021         }
4022       }
4023       ast::StmtExpr(ref expr, id) => {
4024         node_id = id;
4025         // Check with expected type of ()
4026         check_expr_has_type(fcx, &**expr, fcx.tcx().mk_nil());
4027         let expr_ty = fcx.expr_ty(&**expr);
4028         saw_bot = saw_bot || fcx.infcx().type_var_diverges(expr_ty);
4029         saw_err = saw_err || expr_ty.references_error();
4030       }
4031       ast::StmtSemi(ref expr, id) => {
4032         node_id = id;
4033         check_expr(fcx, &**expr);
4034         let expr_ty = fcx.expr_ty(&**expr);
4035         saw_bot |= fcx.infcx().type_var_diverges(expr_ty);
4036         saw_err |= expr_ty.references_error();
4037       }
4038       ast::StmtMac(..) => fcx.ccx.tcx.sess.bug("unexpanded macro")
4039     }
4040     if saw_bot {
4041         fcx.write_ty(node_id, fcx.infcx().next_diverging_ty_var());
4042     }
4043     else if saw_err {
4044         fcx.write_error(node_id);
4045     }
4046     else {
4047         fcx.write_nil(node_id)
4048     }
4049 }
4050
4051 pub fn check_block_no_value<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>, blk: &'tcx ast::Block)  {
4052     check_block_with_expected(fcx, blk, ExpectHasType(fcx.tcx().mk_nil()));
4053     let blkty = fcx.node_ty(blk.id);
4054     if blkty.references_error() {
4055         fcx.write_error(blk.id);
4056     } else {
4057         let nilty = fcx.tcx().mk_nil();
4058         demand::suptype(fcx, blk.span, nilty, blkty);
4059     }
4060 }
4061
4062 fn check_block_with_expected<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
4063                                        blk: &'tcx ast::Block,
4064                                        expected: Expectation<'tcx>) {
4065     let prev = {
4066         let mut fcx_ps = fcx.ps.borrow_mut();
4067         let unsafety_state = fcx_ps.recurse(blk);
4068         replace(&mut *fcx_ps, unsafety_state)
4069     };
4070
4071     let mut warned = false;
4072     let mut any_diverges = false;
4073     let mut any_err = false;
4074     for s in &blk.stmts {
4075         check_stmt(fcx, &**s);
4076         let s_id = ast_util::stmt_id(&**s);
4077         let s_ty = fcx.node_ty(s_id);
4078         if any_diverges && !warned && match s.node {
4079             ast::StmtDecl(ref decl, _) => {
4080                 match decl.node {
4081                     ast::DeclLocal(_) => true,
4082                     _ => false,
4083                 }
4084             }
4085             ast::StmtExpr(_, _) | ast::StmtSemi(_, _) => true,
4086             _ => false
4087         } {
4088             fcx.ccx
4089                 .tcx
4090                 .sess
4091                 .add_lint(lint::builtin::UNREACHABLE_CODE,
4092                           s_id,
4093                           s.span,
4094                           "unreachable statement".to_string());
4095             warned = true;
4096         }
4097         any_diverges = any_diverges || fcx.infcx().type_var_diverges(s_ty);
4098         any_err = any_err || s_ty.references_error();
4099     }
4100     match blk.expr {
4101         None => if any_err {
4102             fcx.write_error(blk.id);
4103         } else if any_diverges {
4104             fcx.write_ty(blk.id, fcx.infcx().next_diverging_ty_var());
4105         } else {
4106             fcx.write_nil(blk.id);
4107         },
4108         Some(ref e) => {
4109             if any_diverges && !warned {
4110                 fcx.ccx
4111                     .tcx
4112                     .sess
4113                     .add_lint(lint::builtin::UNREACHABLE_CODE,
4114                               e.id,
4115                               e.span,
4116                               "unreachable expression".to_string());
4117             }
4118             let ety = match expected {
4119                 ExpectHasType(ety) => {
4120                     check_expr_coercable_to_type(fcx, &**e, ety);
4121                     ety
4122                 }
4123                 _ => {
4124                     check_expr_with_expectation(fcx, &**e, expected);
4125                     fcx.expr_ty(&**e)
4126                 }
4127             };
4128
4129             if any_err {
4130                 fcx.write_error(blk.id);
4131             } else if any_diverges {
4132                 fcx.write_ty(blk.id, fcx.infcx().next_diverging_ty_var());
4133             } else {
4134                 fcx.write_ty(blk.id, ety);
4135             }
4136         }
4137     };
4138
4139     *fcx.ps.borrow_mut() = prev;
4140 }
4141
4142 /// Checks a constant appearing in a type. At the moment this is just the
4143 /// length expression in a fixed-length vector, but someday it might be
4144 /// extended to type-level numeric literals.
4145 fn check_const_in_type<'a,'tcx>(ccx: &'a CrateCtxt<'a,'tcx>,
4146                                 expr: &'tcx ast::Expr,
4147                                 expected_type: Ty<'tcx>) {
4148     let tables = RefCell::new(ty::Tables::empty());
4149     let inh = static_inherited_fields(ccx, &tables);
4150     let fcx = blank_fn_ctxt(ccx, &inh, ty::FnConverging(expected_type), expr.id);
4151     check_const_with_ty(&fcx, expr.span, expr, expected_type);
4152 }
4153
4154 fn check_const<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
4155                         sp: Span,
4156                         e: &'tcx ast::Expr,
4157                         id: ast::NodeId) {
4158     let tables = RefCell::new(ty::Tables::empty());
4159     let inh = static_inherited_fields(ccx, &tables);
4160     let rty = ccx.tcx.node_id_to_type(id);
4161     let fcx = blank_fn_ctxt(ccx, &inh, ty::FnConverging(rty), e.id);
4162     let declty = fcx.ccx.tcx.lookup_item_type(local_def(id)).ty;
4163     check_const_with_ty(&fcx, sp, e, declty);
4164 }
4165
4166 fn check_const_with_ty<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
4167                                  _: Span,
4168                                  e: &'tcx ast::Expr,
4169                                  declty: Ty<'tcx>) {
4170     // Gather locals in statics (because of block expressions).
4171     // This is technically unnecessary because locals in static items are forbidden,
4172     // but prevents type checking from blowing up before const checking can properly
4173     // emit a error.
4174     GatherLocalsVisitor { fcx: fcx }.visit_expr(e);
4175
4176     check_expr_with_hint(fcx, e, declty);
4177     demand::coerce(fcx, e.span, declty, e);
4178     fcx.select_all_obligations_or_error();
4179     fcx.check_casts();
4180     regionck::regionck_expr(fcx, e);
4181     writeback::resolve_type_vars_in_expr(fcx, e);
4182 }
4183
4184 /// Checks whether a type can be represented in memory. In particular, it
4185 /// identifies types that contain themselves without indirection through a
4186 /// pointer, which would mean their size is unbounded.
4187 pub fn check_representable(tcx: &ty::ctxt,
4188                            sp: Span,
4189                            item_id: ast::NodeId,
4190                            designation: &str) -> bool {
4191     let rty = tcx.node_id_to_type(item_id);
4192
4193     // Check that it is possible to represent this type. This call identifies
4194     // (1) types that contain themselves and (2) types that contain a different
4195     // recursive type. It is only necessary to throw an error on those that
4196     // contain themselves. For case 2, there must be an inner type that will be
4197     // caught by case 1.
4198     match rty.is_representable(tcx, sp) {
4199       ty::SelfRecursive => {
4200         span_err!(tcx.sess, sp, E0072,
4201             "illegal recursive {} type; \
4202              wrap the inner value in a box to make it representable",
4203             designation);
4204         return false
4205       }
4206       ty::Representable | ty::ContainsRecursive => (),
4207     }
4208     return true
4209 }
4210
4211 /// Checks whether a type can be constructed at runtime without
4212 /// an existing instance of that type.
4213 pub fn check_instantiable(tcx: &ty::ctxt,
4214                           sp: Span,
4215                           item_id: ast::NodeId) {
4216     let item_ty = tcx.node_id_to_type(item_id);
4217     if !item_ty.is_instantiable(tcx) &&
4218             !tcx.sess.features.borrow().static_recursion {
4219         emit_feature_err(&tcx.sess.parse_sess.span_diagnostic,
4220                          "static_recursion",
4221                          sp,
4222                          "this type cannot be instantiated at runtime \
4223                           without an instance of itself");
4224     }
4225 }
4226
4227 pub fn check_simd(tcx: &ty::ctxt, sp: Span, id: ast::NodeId) {
4228     let t = tcx.node_id_to_type(id);
4229     if t.needs_subst() {
4230         span_err!(tcx.sess, sp, E0074, "SIMD vector cannot be generic");
4231         return;
4232     }
4233     match t.sty {
4234         ty::TyStruct(did, substs) => {
4235             let fields = tcx.lookup_struct_fields(did);
4236             if fields.is_empty() {
4237                 span_err!(tcx.sess, sp, E0075, "SIMD vector cannot be empty");
4238                 return;
4239             }
4240             let e = tcx.lookup_field_type(did, fields[0].id, substs);
4241             if !fields.iter().all(
4242                          |f| tcx.lookup_field_type(did, f.id, substs) == e) {
4243                 span_err!(tcx.sess, sp, E0076, "SIMD vector should be homogeneous");
4244                 return;
4245             }
4246             if !e.is_machine() {
4247                 span_err!(tcx.sess, sp, E0077,
4248                     "SIMD vector element type should be machine type");
4249                 return;
4250             }
4251         }
4252         _ => ()
4253     }
4254 }
4255
4256 pub fn check_enum_variants<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
4257                                     sp: Span,
4258                                     vs: &'tcx [P<ast::Variant>],
4259                                     id: ast::NodeId) {
4260
4261     fn disr_in_range(ccx: &CrateCtxt,
4262                      ty: attr::IntType,
4263                      disr: ty::Disr) -> bool {
4264         fn uint_in_range(ccx: &CrateCtxt, ty: ast::UintTy, disr: ty::Disr) -> bool {
4265             match ty {
4266                 ast::TyU8 => disr as u8 as Disr == disr,
4267                 ast::TyU16 => disr as u16 as Disr == disr,
4268                 ast::TyU32 => disr as u32 as Disr == disr,
4269                 ast::TyU64 => disr as u64 as Disr == disr,
4270                 ast::TyUs => uint_in_range(ccx, ccx.tcx.sess.target.uint_type, disr)
4271             }
4272         }
4273         fn int_in_range(ccx: &CrateCtxt, ty: ast::IntTy, disr: ty::Disr) -> bool {
4274             match ty {
4275                 ast::TyI8 => disr as i8 as Disr == disr,
4276                 ast::TyI16 => disr as i16 as Disr == disr,
4277                 ast::TyI32 => disr as i32 as Disr == disr,
4278                 ast::TyI64 => disr as i64 as Disr == disr,
4279                 ast::TyIs => int_in_range(ccx, ccx.tcx.sess.target.int_type, disr)
4280             }
4281         }
4282         match ty {
4283             attr::UnsignedInt(ty) => uint_in_range(ccx, ty, disr),
4284             attr::SignedInt(ty) => int_in_range(ccx, ty, disr)
4285         }
4286     }
4287
4288     fn do_check<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
4289                           vs: &'tcx [P<ast::Variant>],
4290                           id: ast::NodeId,
4291                           hint: attr::ReprAttr) {
4292         #![allow(trivial_numeric_casts)]
4293
4294         let rty = ccx.tcx.node_id_to_type(id);
4295         let mut disr_vals: Vec<ty::Disr> = Vec::new();
4296
4297         let tables = RefCell::new(ty::Tables::empty());
4298         let inh = static_inherited_fields(ccx, &tables);
4299         let fcx = blank_fn_ctxt(ccx, &inh, ty::FnConverging(rty), id);
4300
4301         let (_, repr_type_ty) = ccx.tcx.enum_repr_type(Some(&hint));
4302         for v in vs {
4303             if let Some(ref e) = v.node.disr_expr {
4304                 check_const_with_ty(&fcx, e.span, e, repr_type_ty);
4305             }
4306         }
4307
4308         let def_id = local_def(id);
4309
4310         // ty::enum_variants guards against discriminant overflows, so
4311         // we need not check for that.
4312         let variants = ccx.tcx.enum_variants(def_id);
4313
4314         for (v, variant) in vs.iter().zip(variants.iter()) {
4315             let current_disr_val = variant.disr_val;
4316
4317             // Check for duplicate discriminant values
4318             match disr_vals.iter().position(|&x| x == current_disr_val) {
4319                 Some(i) => {
4320                     span_err!(ccx.tcx.sess, v.span, E0081,
4321                         "discriminant value `{}` already exists", disr_vals[i]);
4322                     span_note!(ccx.tcx.sess, ccx.tcx.map.span(variants[i].id.node),
4323                         "conflicting discriminant here")
4324                 }
4325                 None => {}
4326             }
4327             // Check for unrepresentable discriminant values
4328             match hint {
4329                 attr::ReprAny | attr::ReprExtern => (),
4330                 attr::ReprInt(sp, ity) => {
4331                     if !disr_in_range(ccx, ity, current_disr_val) {
4332                         span_err!(ccx.tcx.sess, v.span, E0082,
4333                             "discriminant value outside specified type");
4334                         span_note!(ccx.tcx.sess, sp,
4335                             "discriminant type specified here");
4336                     }
4337                 }
4338                 attr::ReprPacked => {
4339                     ccx.tcx.sess.bug("range_to_inttype: found ReprPacked on an enum");
4340                 }
4341             }
4342             disr_vals.push(current_disr_val);
4343         }
4344     }
4345
4346     let hint = *ccx.tcx.lookup_repr_hints(ast::DefId { krate: ast::LOCAL_CRATE, node: id })
4347         .get(0).unwrap_or(&attr::ReprAny);
4348
4349     if hint != attr::ReprAny && vs.len() <= 1 {
4350         if vs.len() == 1 {
4351             span_err!(ccx.tcx.sess, sp, E0083,
4352                 "unsupported representation for univariant enum");
4353         } else {
4354             span_err!(ccx.tcx.sess, sp, E0084,
4355                 "unsupported representation for zero-variant enum");
4356         };
4357     }
4358
4359     do_check(ccx, vs, id, hint);
4360
4361     check_representable(ccx.tcx, sp, id, "enum");
4362     check_instantiable(ccx.tcx, sp, id);
4363 }
4364
4365 // Returns the type parameter count and the type for the given definition.
4366 fn type_scheme_and_predicates_for_def<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
4367                                                 sp: Span,
4368                                                 defn: def::Def)
4369                                                 -> (TypeScheme<'tcx>, GenericPredicates<'tcx>) {
4370     match defn {
4371         def::DefLocal(nid) | def::DefUpvar(nid, _) => {
4372             let typ = fcx.local_ty(sp, nid);
4373             (ty::TypeScheme { generics: ty::Generics::empty(), ty: typ },
4374              ty::GenericPredicates::empty())
4375         }
4376         def::DefFn(id, _) | def::DefMethod(id, _) |
4377         def::DefStatic(id, _) | def::DefVariant(_, id, _) |
4378         def::DefStruct(id) | def::DefConst(id) | def::DefAssociatedConst(id, _) => {
4379             (fcx.tcx().lookup_item_type(id), fcx.tcx().lookup_predicates(id))
4380         }
4381         def::DefTrait(_) |
4382         def::DefTy(..) |
4383         def::DefAssociatedTy(..) |
4384         def::DefPrimTy(_) |
4385         def::DefTyParam(..) |
4386         def::DefMod(..) |
4387         def::DefForeignMod(..) |
4388         def::DefUse(..) |
4389         def::DefRegion(..) |
4390         def::DefLabel(..) |
4391         def::DefSelfTy(..) => {
4392             fcx.ccx.tcx.sess.span_bug(sp, &format!("expected value, found {:?}", defn));
4393         }
4394     }
4395 }
4396
4397 // Instantiates the given path, which must refer to an item with the given
4398 // number of type parameters and type.
4399 pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
4400                                   segments: &[ast::PathSegment],
4401                                   type_scheme: TypeScheme<'tcx>,
4402                                   type_predicates: &ty::GenericPredicates<'tcx>,
4403                                   opt_self_ty: Option<Ty<'tcx>>,
4404                                   def: def::Def,
4405                                   span: Span,
4406                                   node_id: ast::NodeId) {
4407     debug!("instantiate_path(path={:?}, def={:?}, node_id={}, type_scheme={:?})",
4408            segments,
4409            def,
4410            node_id,
4411            type_scheme);
4412
4413     // We need to extract the type parameters supplied by the user in
4414     // the path `path`. Due to the current setup, this is a bit of a
4415     // tricky-process; the problem is that resolve only tells us the
4416     // end-point of the path resolution, and not the intermediate steps.
4417     // Luckily, we can (at least for now) deduce the intermediate steps
4418     // just from the end-point.
4419     //
4420     // There are basically four cases to consider:
4421     //
4422     // 1. Reference to a *type*, such as a struct or enum:
4423     //
4424     //        mod a { struct Foo<T> { ... } }
4425     //
4426     //    Because we don't allow types to be declared within one
4427     //    another, a path that leads to a type will always look like
4428     //    `a::b::Foo<T>` where `a` and `b` are modules. This implies
4429     //    that only the final segment can have type parameters, and
4430     //    they are located in the TypeSpace.
4431     //
4432     //    *Note:* Generally speaking, references to types don't
4433     //    actually pass through this function, but rather the
4434     //    `ast_ty_to_ty` function in `astconv`. However, in the case
4435     //    of struct patterns (and maybe literals) we do invoke
4436     //    `instantiate_path` to get the general type of an instance of
4437     //    a struct. (In these cases, there are actually no type
4438     //    parameters permitted at present, but perhaps we will allow
4439     //    them in the future.)
4440     //
4441     // 1b. Reference to a enum variant or tuple-like struct:
4442     //
4443     //        struct foo<T>(...)
4444     //        enum E<T> { foo(...) }
4445     //
4446     //    In these cases, the parameters are declared in the type
4447     //    space.
4448     //
4449     // 2. Reference to a *fn item*:
4450     //
4451     //        fn foo<T>() { }
4452     //
4453     //    In this case, the path will again always have the form
4454     //    `a::b::foo::<T>` where only the final segment should have
4455     //    type parameters. However, in this case, those parameters are
4456     //    declared on a value, and hence are in the `FnSpace`.
4457     //
4458     // 3. Reference to a *method*:
4459     //
4460     //        impl<A> SomeStruct<A> {
4461     //            fn foo<B>(...)
4462     //        }
4463     //
4464     //    Here we can have a path like
4465     //    `a::b::SomeStruct::<A>::foo::<B>`, in which case parameters
4466     //    may appear in two places. The penultimate segment,
4467     //    `SomeStruct::<A>`, contains parameters in TypeSpace, and the
4468     //    final segment, `foo::<B>` contains parameters in fn space.
4469     //
4470     // 4. Reference to an *associated const*:
4471     //
4472     // impl<A> AnotherStruct<A> {
4473     // const FOO: B = BAR;
4474     // }
4475     //
4476     // The path in this case will look like
4477     // `a::b::AnotherStruct::<A>::FOO`, so the penultimate segment
4478     // only will have parameters in TypeSpace.
4479     //
4480     // The first step then is to categorize the segments appropriately.
4481
4482     assert!(!segments.is_empty());
4483
4484     let mut ufcs_method = None;
4485     let mut segment_spaces: Vec<_>;
4486     match def {
4487         // Case 1 and 1b. Reference to a *type* or *enum variant*.
4488         def::DefSelfTy(..) |
4489         def::DefStruct(..) |
4490         def::DefVariant(..) |
4491         def::DefTy(..) |
4492         def::DefAssociatedTy(..) |
4493         def::DefTrait(..) |
4494         def::DefPrimTy(..) |
4495         def::DefTyParam(..) => {
4496             // Everything but the final segment should have no
4497             // parameters at all.
4498             segment_spaces = vec![None; segments.len() - 1];
4499             segment_spaces.push(Some(subst::TypeSpace));
4500         }
4501
4502         // Case 2. Reference to a top-level value.
4503         def::DefFn(..) |
4504         def::DefConst(..) |
4505         def::DefStatic(..) => {
4506             segment_spaces = vec![None; segments.len() - 1];
4507             segment_spaces.push(Some(subst::FnSpace));
4508         }
4509
4510         // Case 3. Reference to a method.
4511         def::DefMethod(_, provenance) => {
4512             match provenance {
4513                 def::FromTrait(trait_did) => {
4514                     callee::check_legal_trait_for_method_call(fcx.ccx, span, trait_did)
4515                 }
4516                 def::FromImpl(_) => {}
4517             }
4518
4519             if segments.len() >= 2 {
4520                 segment_spaces = vec![None; segments.len() - 2];
4521                 segment_spaces.push(Some(subst::TypeSpace));
4522                 segment_spaces.push(Some(subst::FnSpace));
4523             } else {
4524                 // `<T>::method` will end up here, and so can `T::method`.
4525                 let self_ty = opt_self_ty.expect("UFCS sugared method missing Self");
4526                 segment_spaces = vec![Some(subst::FnSpace)];
4527                 ufcs_method = Some((provenance, self_ty));
4528             }
4529         }
4530
4531         def::DefAssociatedConst(_, provenance) => {
4532             match provenance {
4533                 def::FromTrait(trait_did) => {
4534                     callee::check_legal_trait_for_method_call(fcx.ccx, span, trait_did)
4535                 }
4536                 def::FromImpl(_) => {}
4537             }
4538
4539             if segments.len() >= 2 {
4540                 segment_spaces = vec![None; segments.len() - 2];
4541                 segment_spaces.push(Some(subst::TypeSpace));
4542                 segment_spaces.push(None);
4543             } else {
4544                 segment_spaces = vec![None];
4545             }
4546         }
4547
4548         // Other cases. Various nonsense that really shouldn't show up
4549         // here. If they do, an error will have been reported
4550         // elsewhere. (I hope)
4551         def::DefMod(..) |
4552         def::DefForeignMod(..) |
4553         def::DefLocal(..) |
4554         def::DefUse(..) |
4555         def::DefRegion(..) |
4556         def::DefLabel(..) |
4557         def::DefUpvar(..) => {
4558             segment_spaces = vec![None; segments.len()];
4559         }
4560     }
4561     assert_eq!(segment_spaces.len(), segments.len());
4562
4563     // In `<T as Trait<A, B>>::method`, `A` and `B` are mandatory, but
4564     // `opt_self_ty` can also be Some for `Foo::method`, where Foo's
4565     // type parameters are not mandatory.
4566     let require_type_space = opt_self_ty.is_some() && ufcs_method.is_none();
4567
4568     debug!("segment_spaces={:?}", segment_spaces);
4569
4570     // Next, examine the definition, and determine how many type
4571     // parameters we expect from each space.
4572     let type_defs = &type_scheme.generics.types;
4573     let region_defs = &type_scheme.generics.regions;
4574
4575     // Now that we have categorized what space the parameters for each
4576     // segment belong to, let's sort out the parameters that the user
4577     // provided (if any) into their appropriate spaces. We'll also report
4578     // errors if type parameters are provided in an inappropriate place.
4579     let mut substs = Substs::empty();
4580     for (opt_space, segment) in segment_spaces.iter().zip(segments) {
4581         match *opt_space {
4582             None => {
4583                 check_path_args(fcx.tcx(), slice::ref_slice(segment),
4584                                 NO_TPS | NO_REGIONS);
4585             }
4586
4587             Some(space) => {
4588                 push_explicit_parameters_from_segment_to_substs(fcx,
4589                                                                 space,
4590                                                                 span,
4591                                                                 type_defs,
4592                                                                 region_defs,
4593                                                                 segment,
4594                                                                 &mut substs);
4595             }
4596         }
4597     }
4598     if let Some(self_ty) = opt_self_ty {
4599         if type_defs.len(subst::SelfSpace) == 1 {
4600             substs.types.push(subst::SelfSpace, self_ty);
4601         }
4602     }
4603
4604     // Now we have to compare the types that the user *actually*
4605     // provided against the types that were *expected*. If the user
4606     // did not provide any types, then we want to substitute inference
4607     // variables. If the user provided some types, we may still need
4608     // to add defaults. If the user provided *too many* types, that's
4609     // a problem.
4610     for &space in &ParamSpace::all() {
4611         adjust_type_parameters(fcx, span, space, type_defs,
4612                                require_type_space, &mut substs);
4613         assert_eq!(substs.types.len(space), type_defs.len(space));
4614
4615         adjust_region_parameters(fcx, span, space, region_defs, &mut substs);
4616         assert_eq!(substs.regions().len(space), region_defs.len(space));
4617     }
4618
4619     // The things we are substituting into the type should not contain
4620     // escaping late-bound regions, and nor should the base type scheme.
4621     assert!(!substs.has_regions_escaping_depth(0));
4622     assert!(!type_scheme.has_escaping_regions());
4623
4624     // Add all the obligations that are required, substituting and
4625     // normalized appropriately.
4626     let bounds = fcx.instantiate_bounds(span, &substs, &type_predicates);
4627     fcx.add_obligations_for_parameters(
4628         traits::ObligationCause::new(span, fcx.body_id, traits::ItemObligation(def.def_id())),
4629         &bounds);
4630
4631     // Substitute the values for the type parameters into the type of
4632     // the referenced item.
4633     let ty_substituted = fcx.instantiate_type_scheme(span, &substs, &type_scheme.ty);
4634
4635
4636     if let Some((def::FromImpl(impl_def_id), self_ty)) = ufcs_method {
4637         // In the case of `Foo<T>::method` and `<Foo<T>>::method`, if `method`
4638         // is inherent, there is no `Self` parameter, instead, the impl needs
4639         // type parameters, which we can infer by unifying the provided `Self`
4640         // with the substituted impl type.
4641         let impl_scheme = fcx.tcx().lookup_item_type(impl_def_id);
4642         assert_eq!(substs.types.len(subst::TypeSpace),
4643                    impl_scheme.generics.types.len(subst::TypeSpace));
4644         assert_eq!(substs.regions().len(subst::TypeSpace),
4645                    impl_scheme.generics.regions.len(subst::TypeSpace));
4646
4647         let impl_ty = fcx.instantiate_type_scheme(span, &substs, &impl_scheme.ty);
4648         if fcx.mk_subty(false, infer::Misc(span), self_ty, impl_ty).is_err() {
4649             fcx.tcx().sess.span_bug(span,
4650             &format!(
4651                 "instantiate_path: (UFCS) {:?} was a subtype of {:?} but now is not?",
4652                 self_ty,
4653                 impl_ty));
4654         }
4655     }
4656
4657     fcx.write_ty(node_id, ty_substituted);
4658     fcx.write_substs(node_id, ty::ItemSubsts { substs: substs });
4659     return;
4660
4661     /// Finds the parameters that the user provided and adds them to `substs`. If too many
4662     /// parameters are provided, then reports an error and clears the output vector.
4663     ///
4664     /// We clear the output vector because that will cause the `adjust_XXX_parameters()` later to
4665     /// use inference variables. This seems less likely to lead to derived errors.
4666     ///
4667     /// Note that we *do not* check for *too few* parameters here. Due to the presence of defaults
4668     /// etc that is more complicated. I wanted however to do the reporting of *too many* parameters
4669     /// here because we can easily use the precise span of the N+1'th parameter.
4670     fn push_explicit_parameters_from_segment_to_substs<'a, 'tcx>(
4671         fcx: &FnCtxt<'a, 'tcx>,
4672         space: subst::ParamSpace,
4673         span: Span,
4674         type_defs: &VecPerParamSpace<ty::TypeParameterDef<'tcx>>,
4675         region_defs: &VecPerParamSpace<ty::RegionParameterDef>,
4676         segment: &ast::PathSegment,
4677         substs: &mut Substs<'tcx>)
4678     {
4679         match segment.parameters {
4680             ast::AngleBracketedParameters(ref data) => {
4681                 push_explicit_angle_bracketed_parameters_from_segment_to_substs(
4682                     fcx, space, type_defs, region_defs, data, substs);
4683             }
4684
4685             ast::ParenthesizedParameters(ref data) => {
4686                 span_err!(fcx.tcx().sess, span, E0238,
4687                     "parenthesized parameters may only be used with a trait");
4688                 push_explicit_parenthesized_parameters_from_segment_to_substs(
4689                     fcx, space, span, type_defs, data, substs);
4690             }
4691         }
4692     }
4693
4694     fn push_explicit_angle_bracketed_parameters_from_segment_to_substs<'a, 'tcx>(
4695         fcx: &FnCtxt<'a, 'tcx>,
4696         space: subst::ParamSpace,
4697         type_defs: &VecPerParamSpace<ty::TypeParameterDef<'tcx>>,
4698         region_defs: &VecPerParamSpace<ty::RegionParameterDef>,
4699         data: &ast::AngleBracketedParameterData,
4700         substs: &mut Substs<'tcx>)
4701     {
4702         {
4703             let type_count = type_defs.len(space);
4704             assert_eq!(substs.types.len(space), 0);
4705             for (i, typ) in data.types.iter().enumerate() {
4706                 let t = fcx.to_ty(&**typ);
4707                 if i < type_count {
4708                     substs.types.push(space, t);
4709                 } else if i == type_count {
4710                     span_err!(fcx.tcx().sess, typ.span, E0087,
4711                         "too many type parameters provided: \
4712                          expected at most {} parameter{}, \
4713                          found {} parameter{}",
4714                          type_count,
4715                          if type_count == 1 {""} else {"s"},
4716                          data.types.len(),
4717                          if data.types.len() == 1 {""} else {"s"});
4718                     substs.types.truncate(space, 0);
4719                     break;
4720                 }
4721             }
4722         }
4723
4724         if !data.bindings.is_empty() {
4725             span_err!(fcx.tcx().sess, data.bindings[0].span, E0182,
4726                       "unexpected binding of associated item in expression path \
4727                        (only allowed in type paths)");
4728         }
4729
4730         {
4731             let region_count = region_defs.len(space);
4732             assert_eq!(substs.regions().len(space), 0);
4733             for (i, lifetime) in data.lifetimes.iter().enumerate() {
4734                 let r = ast_region_to_region(fcx.tcx(), lifetime);
4735                 if i < region_count {
4736                     substs.mut_regions().push(space, r);
4737                 } else if i == region_count {
4738                     span_err!(fcx.tcx().sess, lifetime.span, E0088,
4739                         "too many lifetime parameters provided: \
4740                          expected {} parameter{}, found {} parameter{}",
4741                         region_count,
4742                         if region_count == 1 {""} else {"s"},
4743                         data.lifetimes.len(),
4744                         if data.lifetimes.len() == 1 {""} else {"s"});
4745                     substs.mut_regions().truncate(space, 0);
4746                     break;
4747                 }
4748             }
4749         }
4750     }
4751
4752     /// As with
4753     /// `push_explicit_angle_bracketed_parameters_from_segment_to_substs`,
4754     /// but intended for `Foo(A,B) -> C` form. This expands to
4755     /// roughly the same thing as `Foo<(A,B),C>`. One important
4756     /// difference has to do with the treatment of anonymous
4757     /// regions, which are translated into bound regions (NYI).
4758     fn push_explicit_parenthesized_parameters_from_segment_to_substs<'a, 'tcx>(
4759         fcx: &FnCtxt<'a, 'tcx>,
4760         space: subst::ParamSpace,
4761         span: Span,
4762         type_defs: &VecPerParamSpace<ty::TypeParameterDef<'tcx>>,
4763         data: &ast::ParenthesizedParameterData,
4764         substs: &mut Substs<'tcx>)
4765     {
4766         let type_count = type_defs.len(space);
4767         if type_count < 2 {
4768             span_err!(fcx.tcx().sess, span, E0167,
4769                       "parenthesized form always supplies 2 type parameters, \
4770                       but only {} parameter(s) were expected",
4771                       type_count);
4772         }
4773
4774         let input_tys: Vec<Ty> =
4775             data.inputs.iter().map(|ty| fcx.to_ty(&**ty)).collect();
4776
4777         let tuple_ty = fcx.tcx().mk_tup(input_tys);
4778
4779         if type_count >= 1 {
4780             substs.types.push(space, tuple_ty);
4781         }
4782
4783         let output_ty: Option<Ty> =
4784             data.output.as_ref().map(|ty| fcx.to_ty(&**ty));
4785
4786         let output_ty =
4787             output_ty.unwrap_or(fcx.tcx().mk_nil());
4788
4789         if type_count >= 2 {
4790             substs.types.push(space, output_ty);
4791         }
4792     }
4793
4794     fn adjust_type_parameters<'a, 'tcx>(
4795         fcx: &FnCtxt<'a, 'tcx>,
4796         span: Span,
4797         space: ParamSpace,
4798         defs: &VecPerParamSpace<ty::TypeParameterDef<'tcx>>,
4799         require_type_space: bool,
4800         substs: &mut Substs<'tcx>)
4801     {
4802         let provided_len = substs.types.len(space);
4803         let desired = defs.get_slice(space);
4804         let required_len = desired.iter()
4805                               .take_while(|d| d.default.is_none())
4806                               .count();
4807
4808         debug!("adjust_type_parameters(space={:?}, \
4809                provided_len={}, \
4810                desired_len={}, \
4811                required_len={})",
4812                space,
4813                provided_len,
4814                desired.len(),
4815                required_len);
4816
4817         // Enforced by `push_explicit_parameters_from_segment_to_substs()`.
4818         assert!(provided_len <= desired.len());
4819
4820         // Nothing specified at all: supply inference variables for
4821         // everything.
4822         if provided_len == 0 && !(require_type_space && space == subst::TypeSpace) {
4823             substs.types.replace(space, fcx.infcx().type_vars_for_defs(span, &desired[..]));
4824             return;
4825         }
4826
4827         // Too few parameters specified: report an error and use Err
4828         // for everything.
4829         if provided_len < required_len {
4830             let qualifier =
4831                 if desired.len() != required_len { "at least " } else { "" };
4832             span_err!(fcx.tcx().sess, span, E0089,
4833                 "too few type parameters provided: expected {}{} parameter{}, \
4834                  found {} parameter{}",
4835                 qualifier, required_len,
4836                 if required_len == 1 {""} else {"s"},
4837                 provided_len,
4838                 if provided_len == 1 {""} else {"s"});
4839             substs.types.replace(space, vec![fcx.tcx().types.err; desired.len()]);
4840             return;
4841         }
4842
4843         // Otherwise, add in any optional parameters that the user
4844         // omitted. The case of *too many* parameters is handled
4845         // already by
4846         // push_explicit_parameters_from_segment_to_substs(). Note
4847         // that the *default* type are expressed in terms of all prior
4848         // parameters, so we have to substitute as we go with the
4849         // partial substitution that we have built up.
4850         for i in provided_len..desired.len() {
4851             let default = desired[i].default.unwrap();
4852             let default = default.subst_spanned(fcx.tcx(), substs, Some(span));
4853             substs.types.push(space, default);
4854         }
4855         assert_eq!(substs.types.len(space), desired.len());
4856
4857         debug!("Final substs: {:?}", substs);
4858     }
4859
4860     fn adjust_region_parameters(
4861         fcx: &FnCtxt,
4862         span: Span,
4863         space: ParamSpace,
4864         defs: &VecPerParamSpace<ty::RegionParameterDef>,
4865         substs: &mut Substs)
4866     {
4867         let provided_len = substs.mut_regions().len(space);
4868         let desired = defs.get_slice(space);
4869
4870         // Enforced by `push_explicit_parameters_from_segment_to_substs()`.
4871         assert!(provided_len <= desired.len());
4872
4873         // If nothing was provided, just use inference variables.
4874         if provided_len == 0 {
4875             substs.mut_regions().replace(
4876                 space,
4877                 fcx.infcx().region_vars_for_defs(span, desired));
4878             return;
4879         }
4880
4881         // If just the right number were provided, everybody is happy.
4882         if provided_len == desired.len() {
4883             return;
4884         }
4885
4886         // Otherwise, too few were provided. Report an error and then
4887         // use inference variables.
4888         span_err!(fcx.tcx().sess, span, E0090,
4889             "too few lifetime parameters provided: expected {} parameter{}, \
4890              found {} parameter{}",
4891             desired.len(),
4892             if desired.len() == 1 {""} else {"s"},
4893             provided_len,
4894             if provided_len == 1 {""} else {"s"});
4895
4896         substs.mut_regions().replace(
4897             space,
4898             fcx.infcx().region_vars_for_defs(span, desired));
4899     }
4900 }
4901
4902 fn structurally_resolve_type_or_else<'a, 'tcx, F>(fcx: &FnCtxt<'a, 'tcx>,
4903                                                   sp: Span,
4904                                                   ty: Ty<'tcx>,
4905                                                   f: F) -> Ty<'tcx>
4906     where F: Fn() -> Ty<'tcx>
4907 {
4908     let mut ty = fcx.resolve_type_vars_if_possible(ty);
4909
4910     if ty.is_ty_var() {
4911         let alternative = f();
4912
4913         // If not, error.
4914         if alternative.is_ty_var() || alternative.references_error() {
4915             fcx.type_error_message(sp, |_actual| {
4916                 "the type of this value must be known in this context".to_string()
4917             }, ty, None);
4918             demand::suptype(fcx, sp, fcx.tcx().types.err, ty);
4919             ty = fcx.tcx().types.err;
4920         } else {
4921             demand::suptype(fcx, sp, alternative, ty);
4922             ty = alternative;
4923         }
4924     }
4925
4926     ty
4927 }
4928
4929 // Resolves `typ` by a single level if `typ` is a type variable.  If no
4930 // resolution is possible, then an error is reported.
4931 pub fn structurally_resolved_type<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
4932                                             sp: Span,
4933                                             ty: Ty<'tcx>)
4934                                             -> Ty<'tcx>
4935 {
4936     structurally_resolve_type_or_else(fcx, sp, ty, || {
4937         fcx.tcx().types.err
4938     })
4939 }
4940
4941 // Returns true if b contains a break that can exit from b
4942 pub fn may_break(cx: &ty::ctxt, id: ast::NodeId, b: &ast::Block) -> bool {
4943     // First: is there an unlabeled break immediately
4944     // inside the loop?
4945     (loop_query(&*b, |e| {
4946         match *e {
4947             ast::ExprBreak(None) => true,
4948             _ => false
4949         }
4950     })) ||
4951     // Second: is there a labeled break with label
4952     // <id> nested anywhere inside the loop?
4953     (block_query(b, |e| {
4954         if let ast::ExprBreak(Some(_)) = e.node {
4955             lookup_full_def(cx, e.span, e.id) == def::DefLabel(id)
4956         } else {
4957             false
4958         }
4959     }))
4960 }
4961
4962 pub fn check_bounds_are_used<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
4963                                        span: Span,
4964                                        tps: &OwnedSlice<ast::TyParam>,
4965                                        ty: Ty<'tcx>) {
4966     debug!("check_bounds_are_used(n_tps={}, ty={:?})",
4967            tps.len(),  ty);
4968
4969     // make a vector of booleans initially false, set to true when used
4970     if tps.is_empty() { return; }
4971     let mut tps_used = vec![false; tps.len()];
4972
4973     for leaf_ty in ty.walk() {
4974         if let ty::TyParam(ParamTy {idx, ..}) = leaf_ty.sty {
4975             debug!("Found use of ty param num {}", idx);
4976             tps_used[idx as usize] = true;
4977         }
4978     }
4979
4980     for (i, b) in tps_used.iter().enumerate() {
4981         if !*b {
4982             span_err!(ccx.tcx.sess, span, E0091,
4983                 "type parameter `{}` is unused",
4984                 token::get_ident(tps[i].ident));
4985         }
4986     }
4987 }
4988
4989 /// Remember to add all intrinsics here, in librustc_trans/trans/intrinsic.rs,
4990 /// and in libcore/intrinsics.rs
4991 pub fn check_intrinsic_type(ccx: &CrateCtxt, it: &ast::ForeignItem) {
4992     fn param<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, n: u32) -> Ty<'tcx> {
4993         let name = token::intern(&format!("P{}", n));
4994         ccx.tcx.mk_param(subst::FnSpace, n, name)
4995     }
4996
4997     let tcx = ccx.tcx;
4998     let name = token::get_ident(it.ident);
4999     let (n_tps, inputs, output) = if name.starts_with("atomic_") {
5000         let split : Vec<&str> = name.split('_').collect();
5001         assert!(split.len() >= 2, "Atomic intrinsic not correct format");
5002
5003         //We only care about the operation here
5004         let (n_tps, inputs, output) = match split[1] {
5005             "cxchg" => (1, vec!(tcx.mk_mut_ptr(param(ccx, 0)),
5006                                 param(ccx, 0),
5007                                 param(ccx, 0)),
5008                         param(ccx, 0)),
5009             "load" => (1, vec!(tcx.mk_imm_ptr(param(ccx, 0))),
5010                        param(ccx, 0)),
5011             "store" => (1, vec!(tcx.mk_mut_ptr(param(ccx, 0)), param(ccx, 0)),
5012                         tcx.mk_nil()),
5013
5014             "xchg" | "xadd" | "xsub" | "and"  | "nand" | "or" | "xor" | "max" |
5015             "min"  | "umax" | "umin" => {
5016                 (1, vec!(tcx.mk_mut_ptr(param(ccx, 0)), param(ccx, 0)),
5017                  param(ccx, 0))
5018             }
5019             "fence" | "singlethreadfence" => {
5020                 (0, Vec::new(), tcx.mk_nil())
5021             }
5022             op => {
5023                 span_err!(tcx.sess, it.span, E0092,
5024                     "unrecognized atomic operation function: `{}`", op);
5025                 return;
5026             }
5027         };
5028         (n_tps, inputs, ty::FnConverging(output))
5029     } else if &name[..] == "abort" || &name[..] == "unreachable" {
5030         (0, Vec::new(), ty::FnDiverging)
5031     } else {
5032         let (n_tps, inputs, output) = match &name[..] {
5033             "breakpoint" => (0, Vec::new(), tcx.mk_nil()),
5034             "size_of" |
5035             "pref_align_of" | "min_align_of" => (1, Vec::new(), ccx.tcx.types.usize),
5036             "size_of_val" |  "min_align_of_val" => {
5037                 (1, vec![
5038                     tcx.mk_imm_ref(tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1),
5039                                                                   ty::BrAnon(0))),
5040                                     param(ccx, 0))
5041                  ], ccx.tcx.types.usize)
5042             }
5043             "init" | "init_dropped" => (1, Vec::new(), param(ccx, 0)),
5044             "uninit" => (1, Vec::new(), param(ccx, 0)),
5045             "forget" => (1, vec!( param(ccx, 0) ), tcx.mk_nil()),
5046             "transmute" => (2, vec!( param(ccx, 0) ), param(ccx, 1)),
5047             "move_val_init" => {
5048                 (1,
5049                  vec!(
5050                     tcx.mk_mut_ptr(param(ccx, 0)),
5051                     param(ccx, 0)
5052                   ),
5053                tcx.mk_nil())
5054             }
5055             "drop_in_place" => {
5056                 (1, vec![tcx.mk_mut_ptr(param(ccx, 0))], tcx.mk_nil())
5057             }
5058             "needs_drop" => (1, Vec::new(), ccx.tcx.types.bool),
5059
5060             "type_name" => (1, Vec::new(), tcx.mk_static_str()),
5061             "type_id" => (1, Vec::new(), ccx.tcx.types.u64),
5062             "offset" | "arith_offset" => {
5063               (1,
5064                vec!(
5065                   tcx.mk_ptr(ty::TypeAndMut {
5066                       ty: param(ccx, 0),
5067                       mutbl: ast::MutImmutable
5068                   }),
5069                   ccx.tcx.types.isize
5070                ),
5071                tcx.mk_ptr(ty::TypeAndMut {
5072                    ty: param(ccx, 0),
5073                    mutbl: ast::MutImmutable
5074                }))
5075             }
5076             "copy" | "copy_nonoverlapping" => {
5077               (1,
5078                vec!(
5079                   tcx.mk_ptr(ty::TypeAndMut {
5080                       ty: param(ccx, 0),
5081                       mutbl: ast::MutImmutable
5082                   }),
5083                   tcx.mk_ptr(ty::TypeAndMut {
5084                       ty: param(ccx, 0),
5085                       mutbl: ast::MutMutable
5086                   }),
5087                   tcx.types.usize,
5088                ),
5089                tcx.mk_nil())
5090             }
5091             "volatile_copy_memory" | "volatile_copy_nonoverlapping_memory" => {
5092               (1,
5093                vec!(
5094                   tcx.mk_ptr(ty::TypeAndMut {
5095                       ty: param(ccx, 0),
5096                       mutbl: ast::MutMutable
5097                   }),
5098                   tcx.mk_ptr(ty::TypeAndMut {
5099                       ty: param(ccx, 0),
5100                       mutbl: ast::MutImmutable
5101                   }),
5102                   tcx.types.usize,
5103                ),
5104                tcx.mk_nil())
5105             }
5106             "write_bytes" | "volatile_set_memory" => {
5107               (1,
5108                vec!(
5109                   tcx.mk_ptr(ty::TypeAndMut {
5110                       ty: param(ccx, 0),
5111                       mutbl: ast::MutMutable
5112                   }),
5113                   tcx.types.u8,
5114                   tcx.types.usize,
5115                ),
5116                tcx.mk_nil())
5117             }
5118             "sqrtf32" => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5119             "sqrtf64" => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5120             "powif32" => {
5121                (0,
5122                 vec!( tcx.types.f32, tcx.types.i32 ),
5123                 tcx.types.f32)
5124             }
5125             "powif64" => {
5126                (0,
5127                 vec!( tcx.types.f64, tcx.types.i32 ),
5128                 tcx.types.f64)
5129             }
5130             "sinf32" => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5131             "sinf64" => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5132             "cosf32" => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5133             "cosf64" => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5134             "powf32" => {
5135                (0,
5136                 vec!( tcx.types.f32, tcx.types.f32 ),
5137                 tcx.types.f32)
5138             }
5139             "powf64" => {
5140                (0,
5141                 vec!( tcx.types.f64, tcx.types.f64 ),
5142                 tcx.types.f64)
5143             }
5144             "expf32"   => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5145             "expf64"   => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5146             "exp2f32"  => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5147             "exp2f64"  => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5148             "logf32"   => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5149             "logf64"   => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5150             "log10f32" => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5151             "log10f64" => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5152             "log2f32"  => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5153             "log2f64"  => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5154             "fmaf32" => {
5155                 (0,
5156                  vec!( tcx.types.f32, tcx.types.f32, tcx.types.f32 ),
5157                  tcx.types.f32)
5158             }
5159             "fmaf64" => {
5160                 (0,
5161                  vec!( tcx.types.f64, tcx.types.f64, tcx.types.f64 ),
5162                  tcx.types.f64)
5163             }
5164             "fabsf32"      => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5165             "fabsf64"      => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5166             "copysignf32"  => (0, vec!( tcx.types.f32, tcx.types.f32 ), tcx.types.f32),
5167             "copysignf64"  => (0, vec!( tcx.types.f64, tcx.types.f64 ), tcx.types.f64),
5168             "floorf32"     => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5169             "floorf64"     => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5170             "ceilf32"      => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5171             "ceilf64"      => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5172             "truncf32"     => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5173             "truncf64"     => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5174             "rintf32"      => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5175             "rintf64"      => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5176             "nearbyintf32" => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5177             "nearbyintf64" => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5178             "roundf32"     => (0, vec!( tcx.types.f32 ), tcx.types.f32),
5179             "roundf64"     => (0, vec!( tcx.types.f64 ), tcx.types.f64),
5180             "ctpop8"       => (0, vec!( tcx.types.u8  ), tcx.types.u8),
5181             "ctpop16"      => (0, vec!( tcx.types.u16 ), tcx.types.u16),
5182             "ctpop32"      => (0, vec!( tcx.types.u32 ), tcx.types.u32),
5183             "ctpop64"      => (0, vec!( tcx.types.u64 ), tcx.types.u64),
5184             "ctlz8"        => (0, vec!( tcx.types.u8  ), tcx.types.u8),
5185             "ctlz16"       => (0, vec!( tcx.types.u16 ), tcx.types.u16),
5186             "ctlz32"       => (0, vec!( tcx.types.u32 ), tcx.types.u32),
5187             "ctlz64"       => (0, vec!( tcx.types.u64 ), tcx.types.u64),
5188             "cttz8"        => (0, vec!( tcx.types.u8  ), tcx.types.u8),
5189             "cttz16"       => (0, vec!( tcx.types.u16 ), tcx.types.u16),
5190             "cttz32"       => (0, vec!( tcx.types.u32 ), tcx.types.u32),
5191             "cttz64"       => (0, vec!( tcx.types.u64 ), tcx.types.u64),
5192             "bswap16"      => (0, vec!( tcx.types.u16 ), tcx.types.u16),
5193             "bswap32"      => (0, vec!( tcx.types.u32 ), tcx.types.u32),
5194             "bswap64"      => (0, vec!( tcx.types.u64 ), tcx.types.u64),
5195
5196             "volatile_load" =>
5197                 (1, vec!( tcx.mk_imm_ptr(param(ccx, 0)) ), param(ccx, 0)),
5198             "volatile_store" =>
5199                 (1, vec!( tcx.mk_mut_ptr(param(ccx, 0)), param(ccx, 0) ), tcx.mk_nil()),
5200
5201             "i8_add_with_overflow" | "i8_sub_with_overflow" | "i8_mul_with_overflow" =>
5202                 (0, vec!(tcx.types.i8, tcx.types.i8),
5203                 tcx.mk_tup(vec!(tcx.types.i8, tcx.types.bool))),
5204
5205             "i16_add_with_overflow" | "i16_sub_with_overflow" | "i16_mul_with_overflow" =>
5206                 (0, vec!(tcx.types.i16, tcx.types.i16),
5207                 tcx.mk_tup(vec!(tcx.types.i16, tcx.types.bool))),
5208
5209             "i32_add_with_overflow" | "i32_sub_with_overflow" | "i32_mul_with_overflow" =>
5210                 (0, vec!(tcx.types.i32, tcx.types.i32),
5211                 tcx.mk_tup(vec!(tcx.types.i32, tcx.types.bool))),
5212
5213             "i64_add_with_overflow" | "i64_sub_with_overflow" | "i64_mul_with_overflow" =>
5214                 (0, vec!(tcx.types.i64, tcx.types.i64),
5215                 tcx.mk_tup(vec!(tcx.types.i64, tcx.types.bool))),
5216
5217             "u8_add_with_overflow" | "u8_sub_with_overflow" | "u8_mul_with_overflow" =>
5218                 (0, vec!(tcx.types.u8, tcx.types.u8),
5219                 tcx.mk_tup(vec!(tcx.types.u8, tcx.types.bool))),
5220
5221             "u16_add_with_overflow" | "u16_sub_with_overflow" | "u16_mul_with_overflow" =>
5222                 (0, vec!(tcx.types.u16, tcx.types.u16),
5223                 tcx.mk_tup(vec!(tcx.types.u16, tcx.types.bool))),
5224
5225             "u32_add_with_overflow" | "u32_sub_with_overflow" | "u32_mul_with_overflow"=>
5226                 (0, vec!(tcx.types.u32, tcx.types.u32),
5227                 tcx.mk_tup(vec!(tcx.types.u32, tcx.types.bool))),
5228
5229             "u64_add_with_overflow" | "u64_sub_with_overflow"  | "u64_mul_with_overflow" =>
5230                 (0, vec!(tcx.types.u64, tcx.types.u64),
5231                 tcx.mk_tup(vec!(tcx.types.u64, tcx.types.bool))),
5232
5233             "unchecked_udiv" | "unchecked_sdiv" | "unchecked_urem" | "unchecked_srem" =>
5234                 (1, vec![param(ccx, 0), param(ccx, 0)], param(ccx, 0)),
5235
5236             "overflowing_add" | "overflowing_sub" | "overflowing_mul" =>
5237                 (1, vec![param(ccx, 0), param(ccx, 0)], param(ccx, 0)),
5238
5239             "return_address" => (0, vec![], tcx.mk_imm_ptr(tcx.types.u8)),
5240
5241             "assume" => (0, vec![tcx.types.bool], tcx.mk_nil()),
5242
5243             "discriminant_value" => (1, vec![
5244                     tcx.mk_imm_ref(tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1),
5245                                                                   ty::BrAnon(0))),
5246                                     param(ccx, 0))], tcx.types.u64),
5247
5248             "try" => {
5249                 let mut_u8 = tcx.mk_mut_ptr(tcx.types.u8);
5250                 let fn_ty = ty::BareFnTy {
5251                     unsafety: ast::Unsafety::Normal,
5252                     abi: abi::Rust,
5253                     sig: ty::Binder(FnSig {
5254                         inputs: vec![mut_u8],
5255                         output: ty::FnOutput::FnConverging(tcx.mk_nil()),
5256                         variadic: false,
5257                     }),
5258                 };
5259                 let fn_ty = tcx.mk_bare_fn(fn_ty);
5260                 (0, vec![tcx.mk_fn(None, fn_ty), mut_u8], mut_u8)
5261             }
5262
5263             ref other => {
5264                 span_err!(tcx.sess, it.span, E0093,
5265                     "unrecognized intrinsic function: `{}`", *other);
5266                 return;
5267             }
5268         };
5269         (n_tps, inputs, ty::FnConverging(output))
5270     };
5271     let fty = tcx.mk_fn(None, tcx.mk_bare_fn(ty::BareFnTy {
5272         unsafety: ast::Unsafety::Unsafe,
5273         abi: abi::RustIntrinsic,
5274         sig: ty::Binder(FnSig {
5275             inputs: inputs,
5276             output: output,
5277             variadic: false,
5278         }),
5279     }));
5280     let i_ty = ccx.tcx.lookup_item_type(local_def(it.id));
5281     let i_n_tps = i_ty.generics.types.len(subst::FnSpace);
5282     if i_n_tps != n_tps {
5283         span_err!(tcx.sess, it.span, E0094,
5284             "intrinsic has wrong number of type \
5285              parameters: found {}, expected {}",
5286              i_n_tps, n_tps);
5287     } else {
5288         require_same_types(tcx,
5289                            None,
5290                            false,
5291                            it.span,
5292                            i_ty.ty,
5293                            fty,
5294                            || {
5295                 format!("intrinsic has wrong type: expected `{}`",
5296                          fty)
5297             });
5298     }
5299 }