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