src/librustc/infer/mod.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! See the Book for more information.
  12
  13 pub use self::LateBoundRegionConversionTime::*;
  14 pub use self::RegionVariableOrigin::*;
  15 pub use self::SubregionOrigin::*;
  16 pub use self::ValuePairs::*;
  17 pub use ty::IntVarValue;
  18 pub use self::freshen::TypeFreshener;
  19 pub use self::region_inference::{GenericKind, VerifyBound};
  20
  21 use hir::def_id::DefId;
  22 use middle::free_region::{FreeRegionMap, RegionRelations};
  23 use middle::region;
  24 use middle::lang_items;
  25 use mir::tcx::LvalueTy;
  26 use ty::subst::{Kind, Subst, Substs};
  27 use ty::{TyVid, IntVid, FloatVid};
  28 use ty::{self, Ty, TyCtxt};
  29 use ty::error::{ExpectedFound, TypeError, UnconstrainedNumeric};
  30 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
  31 use ty::relate::RelateResult;
  32 use traits::{self, ObligationCause, PredicateObligations, Reveal};
  33 use rustc_data_structures::unify::{self, UnificationTable};
  34 use std::cell::{Cell, RefCell, Ref};
  35 use std::fmt;
  36 use syntax::ast;
  37 use errors::DiagnosticBuilder;
  38 use syntax_pos::{self, Span, DUMMY_SP};
  39 use util::nodemap::FxHashMap;
  40 use arena::DroplessArena;
  41
  42 use self::combine::CombineFields;
  43 use self::higher_ranked::HrMatchResult;
  44 use self::region_inference::{RegionVarBindings, RegionSnapshot};
  45 use self::type_variable::TypeVariableOrigin;
  46 use self::unify_key::ToType;
  47
  48 pub mod at;
  49 mod combine;
  50 mod equate;
  51 pub mod error_reporting;
  52 mod fudge;
  53 mod glb;
  54 mod higher_ranked;
  55 pub mod lattice;
  56 mod lub;
  57 pub mod region_inference;
  58 pub mod resolve;
  59 mod freshen;
  60 mod sub;
  61 pub mod type_variable;
  62 pub mod unify_key;
  63
  64 #[must_use]
  65 pub struct InferOk<'tcx, T> {
  66     pub value: T,
  67     pub obligations: PredicateObligations<'tcx>,
  68 }
  69 pub type InferResult<'tcx, T> = Result<InferOk<'tcx, T>, TypeError<'tcx>>;
  70
  71 pub type Bound<T> = Option<T>;
  72 pub type UnitResult<'tcx> = RelateResult<'tcx, ()>; // "unify result"
  73 pub type FixupResult<T> = Result<T, FixupError>; // "fixup result"
  74
  75 pub struct InferCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  76     pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
  77
  78     /// During type-checking/inference of a body, `in_progress_tables`
  79     /// contains a reference to the tables being built up, which are
  80     /// used for reading closure kinds/signatures as they are inferred,
  81     /// and for error reporting logic to read arbitrary node types.
  82     pub in_progress_tables: Option<&'a RefCell<ty::TypeckTables<'tcx>>>,
  83
  84     // Cache for projections. This cache is snapshotted along with the
  85     // infcx.
  86     //
  87     // Public so that `traits::project` can use it.
  88     pub projection_cache: RefCell<traits::ProjectionCache<'tcx>>,
  89
  90     // We instantiate UnificationTable with bounds<Ty> because the
  91     // types that might instantiate a general type variable have an
  92     // order, represented by its upper and lower bounds.
  93     pub type_variables: RefCell<type_variable::TypeVariableTable<'tcx>>,
  94
  95     // Map from integral variable to the kind of integer it represents
  96     int_unification_table: RefCell<UnificationTable<ty::IntVid>>,
  97
  98     // Map from floating variable to the kind of float it represents
  99     float_unification_table: RefCell<UnificationTable<ty::FloatVid>>,
 100
 101     // For region variables.
 102     region_vars: RegionVarBindings<'a, 'gcx, 'tcx>,
 103
 104     /// Caches the results of trait selection. This cache is used
 105     /// for things that have to do with the parameters in scope.
 106     pub selection_cache: traits::SelectionCache<'tcx>,
 107
 108     /// Caches the results of trait evaluation.
 109     pub evaluation_cache: traits::EvaluationCache<'tcx>,
 110
 111     // the set of predicates on which errors have been reported, to
 112     // avoid reporting the same error twice.
 113     pub reported_trait_errors: RefCell<FxHashMap<Span, Vec<ty::Predicate<'tcx>>>>,
 114
 115     // When an error occurs, we want to avoid reporting "derived"
 116     // errors that are due to this original failure. Normally, we
 117     // handle this with the `err_count_on_creation` count, which
 118     // basically just tracks how many errors were reported when we
 119     // started type-checking a fn and checks to see if any new errors
 120     // have been reported since then. Not great, but it works.
 121     //
 122     // However, when errors originated in other passes -- notably
 123     // resolve -- this heuristic breaks down. Therefore, we have this
 124     // auxiliary flag that one can set whenever one creates a
 125     // type-error that is due to an error in a prior pass.
 126     //
 127     // Don't read this flag directly, call `is_tainted_by_errors()`
 128     // and `set_tainted_by_errors()`.
 129     tainted_by_errors_flag: Cell<bool>,
 130
 131     // Track how many errors were reported when this infcx is created.
 132     // If the number of errors increases, that's also a sign (line
 133     // `tained_by_errors`) to avoid reporting certain kinds of errors.
 134     err_count_on_creation: usize,
 135
 136     // This flag is true while there is an active snapshot.
 137     in_snapshot: Cell<bool>,
 138 }
 139
 140 /// A map returned by `skolemize_late_bound_regions()` indicating the skolemized
 141 /// region that each late-bound region was replaced with.
 142 pub type SkolemizationMap<'tcx> = FxHashMap<ty::BoundRegion, ty::Region<'tcx>>;
 143
 144 /// See `error_reporting` module for more details
 145 #[derive(Clone, Debug)]
 146 pub enum ValuePairs<'tcx> {
 147     Types(ExpectedFound<Ty<'tcx>>),
 148     TraitRefs(ExpectedFound<ty::TraitRef<'tcx>>),
 149     PolyTraitRefs(ExpectedFound<ty::PolyTraitRef<'tcx>>),
 150 }
 151
 152 /// The trace designates the path through inference that we took to
 153 /// encounter an error or subtyping constraint.
 154 ///
 155 /// See `error_reporting` module for more details.
 156 #[derive(Clone)]
 157 pub struct TypeTrace<'tcx> {
 158     cause: ObligationCause<'tcx>,
 159     values: ValuePairs<'tcx>,
 160 }
 161
 162 /// The origin of a `r1 <= r2` constraint.
 163 ///
 164 /// See `error_reporting` module for more details
 165 #[derive(Clone, Debug)]
 166 pub enum SubregionOrigin<'tcx> {
 167     // Arose from a subtyping relation
 168     Subtype(TypeTrace<'tcx>),
 169
 170     // Stack-allocated closures cannot outlive innermost loop
 171     // or function so as to ensure we only require finite stack
 172     InfStackClosure(Span),
 173
 174     // Invocation of closure must be within its lifetime
 175     InvokeClosure(Span),
 176
 177     // Dereference of reference must be within its lifetime
 178     DerefPointer(Span),
 179
 180     // Closure bound must not outlive captured free variables
 181     FreeVariable(Span, ast::NodeId),
 182
 183     // Index into slice must be within its lifetime
 184     IndexSlice(Span),
 185
 186     // When casting `&'a T` to an `&'b Trait` object,
 187     // relating `'a` to `'b`
 188     RelateObjectBound(Span),
 189
 190     // Some type parameter was instantiated with the given type,
 191     // and that type must outlive some region.
 192     RelateParamBound(Span, Ty<'tcx>),
 193
 194     // The given region parameter was instantiated with a region
 195     // that must outlive some other region.
 196     RelateRegionParamBound(Span),
 197
 198     // A bound placed on type parameters that states that must outlive
 199     // the moment of their instantiation.
 200     RelateDefaultParamBound(Span, Ty<'tcx>),
 201
 202     // Creating a pointer `b` to contents of another reference
 203     Reborrow(Span),
 204
 205     // Creating a pointer `b` to contents of an upvar
 206     ReborrowUpvar(Span, ty::UpvarId),
 207
 208     // Data with type `Ty<'tcx>` was borrowed
 209     DataBorrowed(Ty<'tcx>, Span),
 210
 211     // (&'a &'b T) where a >= b
 212     ReferenceOutlivesReferent(Ty<'tcx>, Span),
 213
 214     // Type or region parameters must be in scope.
 215     ParameterInScope(ParameterOrigin, Span),
 216
 217     // The type T of an expression E must outlive the lifetime for E.
 218     ExprTypeIsNotInScope(Ty<'tcx>, Span),
 219
 220     // A `ref b` whose region does not enclose the decl site
 221     BindingTypeIsNotValidAtDecl(Span),
 222
 223     // Regions appearing in a method receiver must outlive method call
 224     CallRcvr(Span),
 225
 226     // Regions appearing in a function argument must outlive func call
 227     CallArg(Span),
 228
 229     // Region in return type of invoked fn must enclose call
 230     CallReturn(Span),
 231
 232     // Operands must be in scope
 233     Operand(Span),
 234
 235     // Region resulting from a `&` expr must enclose the `&` expr
 236     AddrOf(Span),
 237
 238     // An auto-borrow that does not enclose the expr where it occurs
 239     AutoBorrow(Span),
 240
 241     // Region constraint arriving from destructor safety
 242     SafeDestructor(Span),
 243
 244     // Comparing the signature and requirements of an impl method against
 245     // the containing trait.
 246     CompareImplMethodObligation {
 247         span: Span,
 248         item_name: ast::Name,
 249         impl_item_def_id: DefId,
 250         trait_item_def_id: DefId,
 251
 252         // this is `Some(_)` if this error arises from the bug fix for
 253         // #18937. This is a temporary measure.
 254         lint_id: Option<ast::NodeId>,
 255     },
 256 }
 257
 258 /// Places that type/region parameters can appear.
 259 #[derive(Clone, Copy, Debug)]
 260 pub enum ParameterOrigin {
 261     Path, // foo::bar
 262     MethodCall, // foo.bar() <-- parameters on impl providing bar()
 263     OverloadedOperator, // a + b when overloaded
 264     OverloadedDeref, // *a when overloaded
 265 }
 266
 267 /// Times when we replace late-bound regions with variables:
 268 #[derive(Clone, Copy, Debug)]
 269 pub enum LateBoundRegionConversionTime {
 270     /// when a fn is called
 271     FnCall,
 272
 273     /// when two higher-ranked types are compared
 274     HigherRankedType,
 275
 276     /// when projecting an associated type
 277     AssocTypeProjection(DefId),
 278 }
 279
 280 /// Reasons to create a region inference variable
 281 ///
 282 /// See `error_reporting` module for more details
 283 #[derive(Clone, Debug)]
 284 pub enum RegionVariableOrigin {
 285     // Region variables created for ill-categorized reasons,
 286     // mostly indicates places in need of refactoring
 287     MiscVariable(Span),
 288
 289     // Regions created by a `&P` or `[...]` pattern
 290     PatternRegion(Span),
 291
 292     // Regions created by `&` operator
 293     AddrOfRegion(Span),
 294
 295     // Regions created as part of an autoref of a method receiver
 296     Autoref(Span),
 297
 298     // Regions created as part of an automatic coercion
 299     Coercion(Span),
 300
 301     // Region variables created as the values for early-bound regions
 302     EarlyBoundRegion(Span, ast::Name),
 303
 304     // Region variables created for bound regions
 305     // in a function or method that is called
 306     LateBoundRegion(Span, ty::BoundRegion, LateBoundRegionConversionTime),
 307
 308     UpvarRegion(ty::UpvarId, Span),
 309
 310     BoundRegionInCoherence(ast::Name),
 311 }
 312
 313 #[derive(Copy, Clone, Debug)]
 314 pub enum FixupError {
 315     UnresolvedIntTy(IntVid),
 316     UnresolvedFloatTy(FloatVid),
 317     UnresolvedTy(TyVid)
 318 }
 319
 320 impl fmt::Display for FixupError {
 321     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 322         use self::FixupError::*;
 323
 324         match *self {
 325             UnresolvedIntTy(_) => {
 326                 write!(f, "cannot determine the type of this integer; \
 327                            add a suffix to specify the type explicitly")
 328             }
 329             UnresolvedFloatTy(_) => {
 330                 write!(f, "cannot determine the type of this number; \
 331                            add a suffix to specify the type explicitly")
 332             }
 333             UnresolvedTy(_) => write!(f, "unconstrained type")
 334         }
 335     }
 336 }
 337
 338 /// Helper type of a temporary returned by tcx.infer_ctxt().
 339 /// Necessary because we can't write the following bound:
 340 /// F: for<'b, 'tcx> where 'gcx: 'tcx FnOnce(InferCtxt<'b, 'gcx, 'tcx>).
 341 pub struct InferCtxtBuilder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 342     global_tcx: TyCtxt<'a, 'gcx, 'gcx>,
 343     arena: DroplessArena,
 344     fresh_tables: Option<RefCell<ty::TypeckTables<'tcx>>>,
 345 }
 346
 347 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'gcx> {
 348     pub fn infer_ctxt(self) -> InferCtxtBuilder<'a, 'gcx, 'tcx> {
 349         InferCtxtBuilder {
 350             global_tcx: self,
 351             arena: DroplessArena::new(),
 352             fresh_tables: None,
 353
 354         }
 355     }
 356 }
 357
 358 impl<'a, 'gcx, 'tcx> InferCtxtBuilder<'a, 'gcx, 'tcx> {
 359     /// Used only by `rustc_typeck` during body type-checking/inference,
 360     /// will initialize `in_progress_tables` with fresh `TypeckTables`.
 361     pub fn with_fresh_in_progress_tables(mut self, table_owner: DefId) -> Self {
 362         self.fresh_tables = Some(RefCell::new(ty::TypeckTables::empty(Some(table_owner))));
 363         self
 364     }
 365
 366     pub fn enter<F, R>(&'tcx mut self, f: F) -> R
 367         where F: for<'b> FnOnce(InferCtxt<'b, 'gcx, 'tcx>) -> R
 368     {
 369         let InferCtxtBuilder {
 370             global_tcx,
 371             ref arena,
 372             ref fresh_tables,
 373         } = *self;
 374         let in_progress_tables = fresh_tables.as_ref();
 375         global_tcx.enter_local(arena, |tcx| f(InferCtxt {
 376             tcx,
 377             in_progress_tables,
 378             projection_cache: RefCell::new(traits::ProjectionCache::new()),
 379             type_variables: RefCell::new(type_variable::TypeVariableTable::new()),
 380             int_unification_table: RefCell::new(UnificationTable::new()),
 381             float_unification_table: RefCell::new(UnificationTable::new()),
 382             region_vars: RegionVarBindings::new(tcx),
 383             selection_cache: traits::SelectionCache::new(),
 384             evaluation_cache: traits::EvaluationCache::new(),
 385             reported_trait_errors: RefCell::new(FxHashMap()),
 386             tainted_by_errors_flag: Cell::new(false),
 387             err_count_on_creation: tcx.sess.err_count(),
 388             in_snapshot: Cell::new(false),
 389         }))
 390     }
 391 }
 392
 393 impl<T> ExpectedFound<T> {
 394     pub fn new(a_is_expected: bool, a: T, b: T) -> Self {
 395         if a_is_expected {
 396             ExpectedFound {expected: a, found: b}
 397         } else {
 398             ExpectedFound {expected: b, found: a}
 399         }
 400     }
 401 }
 402
 403 impl<'tcx, T> InferOk<'tcx, T> {
 404     pub fn unit(self) -> InferOk<'tcx, ()> {
 405         InferOk { value: (), obligations: self.obligations }
 406     }
 407 }
 408
 409 #[must_use = "once you start a snapshot, you should always consume it"]
 410 pub struct CombinedSnapshot<'a, 'tcx:'a> {
 411     projection_cache_snapshot: traits::ProjectionCacheSnapshot,
 412     type_snapshot: type_variable::Snapshot,
 413     int_snapshot: unify::Snapshot<ty::IntVid>,
 414     float_snapshot: unify::Snapshot<ty::FloatVid>,
 415     region_vars_snapshot: RegionSnapshot,
 416     was_in_snapshot: bool,
 417     _in_progress_tables: Option<Ref<'a, ty::TypeckTables<'tcx>>>,
 418 }
 419
 420 /// Helper trait for shortening the lifetimes inside a
 421 /// value for post-type-checking normalization.
 422 pub trait TransNormalize<'gcx>: TypeFoldable<'gcx> {
 423     fn trans_normalize<'a, 'tcx>(&self,
 424                                  infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 425                                  param_env: ty::ParamEnv<'tcx>)
 426                                  -> Self;
 427 }
 428
 429 macro_rules! items { ($($item:item)+) => ($($item)+) }
 430 macro_rules! impl_trans_normalize {
 431     ($lt_gcx:tt, $($ty:ty),+) => {
 432         items!($(impl<$lt_gcx> TransNormalize<$lt_gcx> for $ty {
 433             fn trans_normalize<'a, 'tcx>(&self,
 434                                          infcx: &InferCtxt<'a, $lt_gcx, 'tcx>,
 435                                          param_env: ty::ParamEnv<'tcx>)
 436                                          -> Self {
 437                 infcx.normalize_projections_in(param_env, self)
 438             }
 439         })+);
 440     }
 441 }
 442
 443 impl_trans_normalize!('gcx,
 444     Ty<'gcx>,
 445     &'gcx Substs<'gcx>,
 446     ty::FnSig<'gcx>,
 447     ty::PolyFnSig<'gcx>,
 448     ty::ClosureSubsts<'gcx>,
 449     ty::PolyTraitRef<'gcx>,
 450     ty::ExistentialTraitRef<'gcx>
 451 );
 452
 453 impl<'gcx> TransNormalize<'gcx> for LvalueTy<'gcx> {
 454     fn trans_normalize<'a, 'tcx>(&self,
 455                                  infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 456                                  param_env: ty::ParamEnv<'tcx>)
 457                                  -> Self {
 458         match *self {
 459             LvalueTy::Ty { ty } => LvalueTy::Ty { ty: ty.trans_normalize(infcx, param_env) },
 460             LvalueTy::Downcast { adt_def, substs, variant_index } => {
 461                 LvalueTy::Downcast {
 462                     adt_def,
 463                     substs: substs.trans_normalize(infcx, param_env),
 464                     variant_index,
 465                 }
 466             }
 467         }
 468     }
 469 }
 470
 471 // NOTE: Callable from trans only!
 472 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
 473     /// Currently, higher-ranked type bounds inhibit normalization. Therefore,
 474     /// each time we erase them in translation, we need to normalize
 475     /// the contents.
 476     pub fn erase_late_bound_regions_and_normalize<T>(self, value: &ty::Binder<T>)
 477         -> T
 478         where T: TransNormalize<'tcx>
 479     {
 480         assert!(!value.needs_subst());
 481         let value = self.erase_late_bound_regions(value);
 482         self.normalize_associated_type(&value)
 483     }
 484
 485     /// Fully normalizes any associated types in `value`, using an
 486     /// empty environment and `Reveal::All` mode (therefore, suitable
 487     /// only for monomorphized code during trans, basically).
 488     pub fn normalize_associated_type<T>(self, value: &T) -> T
 489         where T: TransNormalize<'tcx>
 490     {
 491         debug!("normalize_associated_type(t={:?})", value);
 492
 493         let param_env = ty::ParamEnv::empty(Reveal::All);
 494         let value = self.erase_regions(value);
 495
 496         if !value.has_projection_types() {
 497             return value;
 498         }
 499
 500         self.infer_ctxt().enter(|infcx| {
 501             value.trans_normalize(&infcx, param_env)
 502         })
 503     }
 504
 505     /// Does a best-effort to normalize any associated types in
 506     /// `value`; this includes revealing specializable types, so this
 507     /// should be not be used during type-checking, but only during
 508     /// optimization and code generation.
 509     pub fn normalize_associated_type_in_env<T>(
 510         self, value: &T, env: ty::ParamEnv<'tcx>
 511     ) -> T
 512         where T: TransNormalize<'tcx>
 513     {
 514         debug!("normalize_associated_type_in_env(t={:?})", value);
 515
 516         let value = self.erase_regions(value);
 517
 518         if !value.has_projection_types() {
 519             return value;
 520         }
 521
 522         self.infer_ctxt().enter(|infcx| {
 523             value.trans_normalize(&infcx, env.reveal_all())
 524        })
 525     }
 526 }
 527
 528 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 529     fn normalize_projections_in<T>(&self, param_env: ty::ParamEnv<'tcx>, value: &T) -> T::Lifted
 530         where T: TypeFoldable<'tcx> + ty::Lift<'gcx>
 531     {
 532         let mut selcx = traits::SelectionContext::new(self);
 533         let cause = traits::ObligationCause::dummy();
 534         let traits::Normalized { value: result, obligations } =
 535             traits::normalize(&mut selcx, param_env, cause, value);
 536
 537         debug!("normalize_projections_in: result={:?} obligations={:?}",
 538                 result, obligations);
 539
 540         let mut fulfill_cx = traits::FulfillmentContext::new();
 541
 542         for obligation in obligations {
 543             fulfill_cx.register_predicate_obligation(self, obligation);
 544         }
 545
 546         self.drain_fulfillment_cx_or_panic(DUMMY_SP, &mut fulfill_cx, &result)
 547     }
 548
 549     /// Finishes processes any obligations that remain in the
 550     /// fulfillment context, and then returns the result with all type
 551     /// variables removed and regions erased. Because this is intended
 552     /// for use after type-check has completed, if any errors occur,
 553     /// it will panic. It is used during normalization and other cases
 554     /// where processing the obligations in `fulfill_cx` may cause
 555     /// type inference variables that appear in `result` to be
 556     /// unified, and hence we need to process those obligations to get
 557     /// the complete picture of the type.
 558     pub fn drain_fulfillment_cx_or_panic<T>(&self,
 559                                             span: Span,
 560                                             fulfill_cx: &mut traits::FulfillmentContext<'tcx>,
 561                                             result: &T)
 562                                             -> T::Lifted
 563         where T: TypeFoldable<'tcx> + ty::Lift<'gcx>
 564     {
 565         debug!("drain_fulfillment_cx_or_panic()");
 566
 567         // In principle, we only need to do this so long as `result`
 568         // contains unbound type parameters. It could be a slight
 569         // optimization to stop iterating early.
 570         match fulfill_cx.select_all_or_error(self) {
 571             Ok(()) => { }
 572             Err(errors) => {
 573                 span_bug!(span, "Encountered errors `{:?}` resolving bounds after type-checking",
 574                           errors);
 575             }
 576         }
 577
 578         let result = self.resolve_type_vars_if_possible(result);
 579         let result = self.tcx.erase_regions(&result);
 580
 581         match self.tcx.lift_to_global(&result) {
 582             Some(result) => result,
 583             None => {
 584                 span_bug!(span, "Uninferred types/regions in `{:?}`", result);
 585             }
 586         }
 587     }
 588
 589     pub fn is_in_snapshot(&self) -> bool {
 590         self.in_snapshot.get()
 591     }
 592
 593     pub fn freshen<T:TypeFoldable<'tcx>>(&self, t: T) -> T {
 594         t.fold_with(&mut self.freshener())
 595     }
 596
 597     pub fn type_var_diverges(&'a self, ty: Ty) -> bool {
 598         match ty.sty {
 599             ty::TyInfer(ty::TyVar(vid)) => self.type_variables.borrow().var_diverges(vid),
 600             _ => false
 601         }
 602     }
 603
 604     pub fn freshener<'b>(&'b self) -> TypeFreshener<'b, 'gcx, 'tcx> {
 605         freshen::TypeFreshener::new(self)
 606     }
 607
 608     pub fn type_is_unconstrained_numeric(&'a self, ty: Ty) -> UnconstrainedNumeric {
 609         use ty::error::UnconstrainedNumeric::Neither;
 610         use ty::error::UnconstrainedNumeric::{UnconstrainedInt, UnconstrainedFloat};
 611         match ty.sty {
 612             ty::TyInfer(ty::IntVar(vid)) => {
 613                 if self.int_unification_table.borrow_mut().has_value(vid) {
 614                     Neither
 615                 } else {
 616                     UnconstrainedInt
 617                 }
 618             },
 619             ty::TyInfer(ty::FloatVar(vid)) => {
 620                 if self.float_unification_table.borrow_mut().has_value(vid) {
 621                     Neither
 622                 } else {
 623                     UnconstrainedFloat
 624                 }
 625             },
 626             _ => Neither,
 627         }
 628     }
 629
 630     /// Returns a type variable's default fallback if any exists. A default
 631     /// must be attached to the variable when created, if it is created
 632     /// without a default, this will return None.
 633     ///
 634     /// This code does not apply to integral or floating point variables,
 635     /// only to use declared defaults.
 636     ///
 637     /// See `new_ty_var_with_default` to create a type variable with a default.
 638     /// See `type_variable::Default` for details about what a default entails.
 639     pub fn default(&self, ty: Ty<'tcx>) -> Option<type_variable::Default<'tcx>> {
 640         match ty.sty {
 641             ty::TyInfer(ty::TyVar(vid)) => self.type_variables.borrow().default(vid),
 642             _ => None
 643         }
 644     }
 645
 646     pub fn unsolved_variables(&self) -> Vec<ty::Ty<'tcx>> {
 647         let mut variables = Vec::new();
 648
 649         let unbound_ty_vars = self.type_variables
 650                                   .borrow_mut()
 651                                   .unsolved_variables()
 652                                   .into_iter()
 653                                   .map(|t| self.tcx.mk_var(t));
 654
 655         let unbound_int_vars = self.int_unification_table
 656                                    .borrow_mut()
 657                                    .unsolved_variables()
 658                                    .into_iter()
 659                                    .map(|v| self.tcx.mk_int_var(v));
 660
 661         let unbound_float_vars = self.float_unification_table
 662                                      .borrow_mut()
 663                                      .unsolved_variables()
 664                                      .into_iter()
 665                                      .map(|v| self.tcx.mk_float_var(v));
 666
 667         variables.extend(unbound_ty_vars);
 668         variables.extend(unbound_int_vars);
 669         variables.extend(unbound_float_vars);
 670
 671         return variables;
 672     }
 673
 674     fn combine_fields(&'a self, trace: TypeTrace<'tcx>, param_env: ty::ParamEnv<'tcx>)
 675                       -> CombineFields<'a, 'gcx, 'tcx> {
 676         CombineFields {
 677             infcx: self,
 678             trace,
 679             cause: None,
 680             param_env,
 681             obligations: PredicateObligations::new(),
 682         }
 683     }
 684
 685     // Clear the "currently in a snapshot" flag, invoke the closure,
 686     // then restore the flag to its original value. This flag is a
 687     // debugging measure designed to detect cases where we start a
 688     // snapshot, create type variables, and register obligations
 689     // which may involve those type variables in the fulfillment cx,
 690     // potentially leaving "dangling type variables" behind.
 691     // In such cases, an assertion will fail when attempting to
 692     // register obligations, within a snapshot. Very useful, much
 693     // better than grovelling through megabytes of RUST_LOG output.
 694     //
 695     // HOWEVER, in some cases the flag is unhelpful. In particular, we
 696     // sometimes create a "mini-fulfilment-cx" in which we enroll
 697     // obligations. As long as this fulfillment cx is fully drained
 698     // before we return, this is not a problem, as there won't be any
 699     // escaping obligations in the main cx. In those cases, you can
 700     // use this function.
 701     pub fn save_and_restore_in_snapshot_flag<F, R>(&self, func: F) -> R
 702         where F: FnOnce(&Self) -> R
 703     {
 704         let flag = self.in_snapshot.get();
 705         self.in_snapshot.set(false);
 706         let result = func(self);
 707         self.in_snapshot.set(flag);
 708         result
 709     }
 710
 711     fn start_snapshot<'b>(&'b self) -> CombinedSnapshot<'b, 'tcx> {
 712         debug!("start_snapshot()");
 713
 714         let in_snapshot = self.in_snapshot.get();
 715         self.in_snapshot.set(true);
 716
 717         CombinedSnapshot {
 718             projection_cache_snapshot: self.projection_cache.borrow_mut().snapshot(),
 719             type_snapshot: self.type_variables.borrow_mut().snapshot(),
 720             int_snapshot: self.int_unification_table.borrow_mut().snapshot(),
 721             float_snapshot: self.float_unification_table.borrow_mut().snapshot(),
 722             region_vars_snapshot: self.region_vars.start_snapshot(),
 723             was_in_snapshot: in_snapshot,
 724             // Borrow tables "in progress" (i.e. during typeck)
 725             // to ban writes from within a snapshot to them.
 726             _in_progress_tables: self.in_progress_tables.map(|tables| {
 727                 tables.borrow()
 728             })
 729         }
 730     }
 731
 732     fn rollback_to(&self, cause: &str, snapshot: CombinedSnapshot) {
 733         debug!("rollback_to(cause={})", cause);
 734         let CombinedSnapshot { projection_cache_snapshot,
 735                                type_snapshot,
 736                                int_snapshot,
 737                                float_snapshot,
 738                                region_vars_snapshot,
 739                                was_in_snapshot,
 740                                _in_progress_tables } = snapshot;
 741
 742         self.in_snapshot.set(was_in_snapshot);
 743
 744         self.projection_cache
 745             .borrow_mut()
 746             .rollback_to(projection_cache_snapshot);
 747         self.type_variables
 748             .borrow_mut()
 749             .rollback_to(type_snapshot);
 750         self.int_unification_table
 751             .borrow_mut()
 752             .rollback_to(int_snapshot);
 753         self.float_unification_table
 754             .borrow_mut()
 755             .rollback_to(float_snapshot);
 756         self.region_vars
 757             .rollback_to(region_vars_snapshot);
 758     }
 759
 760     fn commit_from(&self, snapshot: CombinedSnapshot) {
 761         debug!("commit_from()");
 762         let CombinedSnapshot { projection_cache_snapshot,
 763                                type_snapshot,
 764                                int_snapshot,
 765                                float_snapshot,
 766                                region_vars_snapshot,
 767                                was_in_snapshot,
 768                                _in_progress_tables } = snapshot;
 769
 770         self.in_snapshot.set(was_in_snapshot);
 771
 772         self.projection_cache
 773             .borrow_mut()
 774             .commit(projection_cache_snapshot);
 775         self.type_variables
 776             .borrow_mut()
 777             .commit(type_snapshot);
 778         self.int_unification_table
 779             .borrow_mut()
 780             .commit(int_snapshot);
 781         self.float_unification_table
 782             .borrow_mut()
 783             .commit(float_snapshot);
 784         self.region_vars
 785             .commit(region_vars_snapshot);
 786     }
 787
 788     /// Execute `f` and commit the bindings
 789     pub fn commit_unconditionally<R, F>(&self, f: F) -> R where
 790         F: FnOnce() -> R,
 791     {
 792         debug!("commit()");
 793         let snapshot = self.start_snapshot();
 794         let r = f();
 795         self.commit_from(snapshot);
 796         r
 797     }
 798
 799     /// Execute `f` and commit the bindings if closure `f` returns `Ok(_)`
 800     pub fn commit_if_ok<T, E, F>(&self, f: F) -> Result<T, E> where
 801         F: FnOnce(&CombinedSnapshot) -> Result<T, E>
 802     {
 803         debug!("commit_if_ok()");
 804         let snapshot = self.start_snapshot();
 805         let r = f(&snapshot);
 806         debug!("commit_if_ok() -- r.is_ok() = {}", r.is_ok());
 807         match r {
 808             Ok(_) => { self.commit_from(snapshot); }
 809             Err(_) => { self.rollback_to("commit_if_ok -- error", snapshot); }
 810         }
 811         r
 812     }
 813
 814     // Execute `f` in a snapshot, and commit the bindings it creates
 815     pub fn in_snapshot<T, F>(&self, f: F) -> T where
 816         F: FnOnce(&CombinedSnapshot) -> T
 817     {
 818         debug!("in_snapshot()");
 819         let snapshot = self.start_snapshot();
 820         let r = f(&snapshot);
 821         self.commit_from(snapshot);
 822         r
 823     }
 824
 825     /// Execute `f` then unroll any bindings it creates
 826     pub fn probe<R, F>(&self, f: F) -> R where
 827         F: FnOnce(&CombinedSnapshot) -> R,
 828     {
 829         debug!("probe()");
 830         let snapshot = self.start_snapshot();
 831         let r = f(&snapshot);
 832         self.rollback_to("probe", snapshot);
 833         r
 834     }
 835
 836     pub fn add_given(&self,
 837                      sub: ty::Region<'tcx>,
 838                      sup: ty::RegionVid)
 839     {
 840         self.region_vars.add_given(sub, sup);
 841     }
 842
 843     pub fn can_sub<T>(&self,
 844                       param_env: ty::ParamEnv<'tcx>,
 845                       a: T,
 846                       b: T)
 847                       -> UnitResult<'tcx>
 848         where T: at::ToTrace<'tcx>
 849     {
 850         let origin = &ObligationCause::dummy();
 851         self.probe(|_| {
 852             self.at(origin, param_env).sub(a, b).map(|InferOk { obligations: _, .. }| {
 853                 // Ignore obligations, since we are unrolling
 854                 // everything anyway.
 855             })
 856         })
 857     }
 858
 859     pub fn can_eq<T>(&self,
 860                       param_env: ty::ParamEnv<'tcx>,
 861                       a: T,
 862                       b: T)
 863                       -> UnitResult<'tcx>
 864         where T: at::ToTrace<'tcx>
 865     {
 866         let origin = &ObligationCause::dummy();
 867         self.probe(|_| {
 868             self.at(origin, param_env).eq(a, b).map(|InferOk { obligations: _, .. }| {
 869                 // Ignore obligations, since we are unrolling
 870                 // everything anyway.
 871             })
 872         })
 873     }
 874
 875     pub fn sub_regions(&self,
 876                        origin: SubregionOrigin<'tcx>,
 877                        a: ty::Region<'tcx>,
 878                        b: ty::Region<'tcx>) {
 879         debug!("sub_regions({:?} <: {:?})", a, b);
 880         self.region_vars.make_subregion(origin, a, b);
 881     }
 882
 883     pub fn equality_predicate(&self,
 884                               cause: &ObligationCause<'tcx>,
 885                               param_env: ty::ParamEnv<'tcx>,
 886                               predicate: &ty::PolyEquatePredicate<'tcx>)
 887         -> InferResult<'tcx, ()>
 888     {
 889         self.commit_if_ok(|snapshot| {
 890             let (ty::EquatePredicate(a, b), skol_map) =
 891                 self.skolemize_late_bound_regions(predicate, snapshot);
 892             let cause_span = cause.span;
 893             let eqty_ok = self.at(cause, param_env).eq(b, a)?;
 894             self.leak_check(false, cause_span, &skol_map, snapshot)?;
 895             self.pop_skolemized(skol_map, snapshot);
 896             Ok(eqty_ok.unit())
 897         })
 898     }
 899
 900     pub fn subtype_predicate(&self,
 901                              cause: &ObligationCause<'tcx>,
 902                              param_env: ty::ParamEnv<'tcx>,
 903                              predicate: &ty::PolySubtypePredicate<'tcx>)
 904         -> Option<InferResult<'tcx, ()>>
 905     {
 906         // Subtle: it's ok to skip the binder here and resolve because
 907         // `shallow_resolve` just ignores anything that is not a type
 908         // variable, and because type variable's can't (at present, at
 909         // least) capture any of the things bound by this binder.
 910         //
 911         // Really, there is no *particular* reason to do this
 912         // `shallow_resolve` here except as a
 913         // micro-optimization. Naturally I could not
 914         // resist. -nmatsakis
 915         let two_unbound_type_vars = {
 916             let a = self.shallow_resolve(predicate.skip_binder().a);
 917             let b = self.shallow_resolve(predicate.skip_binder().b);
 918             a.is_ty_var() && b.is_ty_var()
 919         };
 920
 921         if two_unbound_type_vars {
 922             // Two unbound type variables? Can't make progress.
 923             return None;
 924         }
 925
 926         Some(self.commit_if_ok(|snapshot| {
 927             let (ty::SubtypePredicate { a_is_expected, a, b}, skol_map) =
 928                 self.skolemize_late_bound_regions(predicate, snapshot);
 929
 930             let cause_span = cause.span;
 931             let ok = self.at(cause, param_env).sub_exp(a_is_expected, a, b)?;
 932             self.leak_check(false, cause_span, &skol_map, snapshot)?;
 933             self.pop_skolemized(skol_map, snapshot);
 934             Ok(ok.unit())
 935         }))
 936     }
 937
 938     pub fn region_outlives_predicate(&self,
 939                                      cause: &traits::ObligationCause<'tcx>,
 940                                      predicate: &ty::PolyRegionOutlivesPredicate<'tcx>)
 941         -> UnitResult<'tcx>
 942     {
 943         self.commit_if_ok(|snapshot| {
 944             let (ty::OutlivesPredicate(r_a, r_b), skol_map) =
 945                 self.skolemize_late_bound_regions(predicate, snapshot);
 946             let origin =
 947                 SubregionOrigin::from_obligation_cause(cause,
 948                                                        || RelateRegionParamBound(cause.span));
 949             self.sub_regions(origin, r_b, r_a); // `b : a` ==> `a <= b`
 950             self.leak_check(false, cause.span, &skol_map, snapshot)?;
 951             Ok(self.pop_skolemized(skol_map, snapshot))
 952         })
 953     }
 954
 955     pub fn next_ty_var_id(&self, diverging: bool, origin: TypeVariableOrigin) -> TyVid {
 956         self.type_variables
 957             .borrow_mut()
 958             .new_var(diverging, origin, None)
 959     }
 960
 961     pub fn next_ty_var(&self, origin: TypeVariableOrigin) -> Ty<'tcx> {
 962         self.tcx.mk_var(self.next_ty_var_id(false, origin))
 963     }
 964
 965     pub fn next_diverging_ty_var(&self, origin: TypeVariableOrigin) -> Ty<'tcx> {
 966         self.tcx.mk_var(self.next_ty_var_id(true, origin))
 967     }
 968
 969     pub fn next_int_var_id(&self) -> IntVid {
 970         self.int_unification_table
 971             .borrow_mut()
 972             .new_key(None)
 973     }
 974
 975     pub fn next_float_var_id(&self) -> FloatVid {
 976         self.float_unification_table
 977             .borrow_mut()
 978             .new_key(None)
 979     }
 980
 981     pub fn next_region_var(&self, origin: RegionVariableOrigin)
 982                            -> ty::Region<'tcx> {
 983         self.tcx.mk_region(ty::ReVar(self.region_vars.new_region_var(origin)))
 984     }
 985
 986     /// Create a region inference variable for the given
 987     /// region parameter definition.
 988     pub fn region_var_for_def(&self,
 989                               span: Span,
 990                               def: &ty::RegionParameterDef)
 991                               -> ty::Region<'tcx> {
 992         self.next_region_var(EarlyBoundRegion(span, def.name))
 993     }
 994
 995     /// Create a type inference variable for the given
 996     /// type parameter definition. The substitutions are
 997     /// for actual parameters that may be referred to by
 998     /// the default of this type parameter, if it exists.
 999     /// E.g. `struct Foo<A, B, C = (A, B)>(...);` when
1000     /// used in a path such as `Foo::<T, U>::new()` will
1001     /// use an inference variable for `C` with `[T, U]`
1002     /// as the substitutions for the default, `(T, U)`.
1003     pub fn type_var_for_def(&self,
1004                             span: Span,
1005                             def: &ty::TypeParameterDef,
1006                             substs: &[Kind<'tcx>])
1007                             -> Ty<'tcx> {
1008         let default = if def.has_default {
1009             let default = self.tcx.type_of(def.def_id);
1010             Some(type_variable::Default {
1011                 ty: default.subst_spanned(self.tcx, substs, Some(span)),
1012                 origin_span: span,
1013                 def_id: def.def_id
1014             })
1015         } else {
1016             None
1017         };
1018
1019
1020         let ty_var_id = self.type_variables
1021                             .borrow_mut()
1022                             .new_var(false,
1023                                      TypeVariableOrigin::TypeParameterDefinition(span, def.name),
1024                                      default);
1025
1026         self.tcx.mk_var(ty_var_id)
1027     }
1028
1029     /// Given a set of generics defined on a type or impl, returns a substitution mapping each
1030     /// type/region parameter to a fresh inference variable.
1031     pub fn fresh_substs_for_item(&self,
1032                                  span: Span,
1033                                  def_id: DefId)
1034                                  -> &'tcx Substs<'tcx> {
1035         Substs::for_item(self.tcx, def_id, |def, _| {
1036             self.region_var_for_def(span, def)
1037         }, |def, substs| {
1038             self.type_var_for_def(span, def, substs)
1039         })
1040     }
1041
1042     pub fn fresh_bound_region(&self, debruijn: ty::DebruijnIndex) -> ty::Region<'tcx> {
1043         self.region_vars.new_bound(debruijn)
1044     }
1045
1046     /// True if errors have been reported since this infcx was
1047     /// created.  This is sometimes used as a heuristic to skip
1048     /// reporting errors that often occur as a result of earlier
1049     /// errors, but where it's hard to be 100% sure (e.g., unresolved
1050     /// inference variables, regionck errors).
1051     pub fn is_tainted_by_errors(&self) -> bool {
1052         debug!("is_tainted_by_errors(err_count={}, err_count_on_creation={}, \
1053                 tainted_by_errors_flag={})",
1054                self.tcx.sess.err_count(),
1055                self.err_count_on_creation,
1056                self.tainted_by_errors_flag.get());
1057
1058         if self.tcx.sess.err_count() > self.err_count_on_creation {
1059             return true; // errors reported since this infcx was made
1060         }
1061         self.tainted_by_errors_flag.get()
1062     }
1063
1064     /// Set the "tainted by errors" flag to true. We call this when we
1065     /// observe an error from a prior pass.
1066     pub fn set_tainted_by_errors(&self) {
1067         debug!("set_tainted_by_errors()");
1068         self.tainted_by_errors_flag.set(true)
1069     }
1070
1071     pub fn resolve_regions_and_report_errors(&self,
1072                                              region_context: DefId,
1073                                              region_map: &region::ScopeTree,
1074                                              free_regions: &FreeRegionMap<'tcx>) {
1075         let region_rels = RegionRelations::new(self.tcx,
1076                                                region_context,
1077                                                region_map,
1078                                                free_regions);
1079         let errors = self.region_vars.resolve_regions(&region_rels);
1080
1081         if !self.is_tainted_by_errors() {
1082             // As a heuristic, just skip reporting region errors
1083             // altogether if other errors have been reported while
1084             // this infcx was in use.  This is totally hokey but
1085             // otherwise we have a hard time separating legit region
1086             // errors from silly ones.
1087             self.report_region_errors(region_map, &errors); // see error_reporting module
1088         }
1089     }
1090
1091     pub fn ty_to_string(&self, t: Ty<'tcx>) -> String {
1092         self.resolve_type_vars_if_possible(&t).to_string()
1093     }
1094
1095     pub fn tys_to_string(&self, ts: &[Ty<'tcx>]) -> String {
1096         let tstrs: Vec<String> = ts.iter().map(|t| self.ty_to_string(*t)).collect();
1097         format!("({})", tstrs.join(", "))
1098     }
1099
1100     pub fn trait_ref_to_string(&self, t: &ty::TraitRef<'tcx>) -> String {
1101         self.resolve_type_vars_if_possible(t).to_string()
1102     }
1103
1104     pub fn shallow_resolve(&self, typ: Ty<'tcx>) -> Ty<'tcx> {
1105         match typ.sty {
1106             ty::TyInfer(ty::TyVar(v)) => {
1107                 // Not entirely obvious: if `typ` is a type variable,
1108                 // it can be resolved to an int/float variable, which
1109                 // can then be recursively resolved, hence the
1110                 // recursion. Note though that we prevent type
1111                 // variables from unifying to other type variables
1112                 // directly (though they may be embedded
1113                 // structurally), and we prevent cycles in any case,
1114                 // so this recursion should always be of very limited
1115                 // depth.
1116                 self.type_variables.borrow_mut()
1117                     .probe(v)
1118                     .map(|t| self.shallow_resolve(t))
1119                     .unwrap_or(typ)
1120             }
1121
1122             ty::TyInfer(ty::IntVar(v)) => {
1123                 self.int_unification_table
1124                     .borrow_mut()
1125                     .probe(v)
1126                     .map(|v| v.to_type(self.tcx))
1127                     .unwrap_or(typ)
1128             }
1129
1130             ty::TyInfer(ty::FloatVar(v)) => {
1131                 self.float_unification_table
1132                     .borrow_mut()
1133                     .probe(v)
1134                     .map(|v| v.to_type(self.tcx))
1135                     .unwrap_or(typ)
1136             }
1137
1138             _ => {
1139                 typ
1140             }
1141         }
1142     }
1143
1144     pub fn resolve_type_vars_if_possible<T>(&self, value: &T) -> T
1145         where T: TypeFoldable<'tcx>
1146     {
1147         /*!
1148          * Where possible, replaces type/int/float variables in
1149          * `value` with their final value. Note that region variables
1150          * are unaffected. If a type variable has not been unified, it
1151          * is left as is.  This is an idempotent operation that does
1152          * not affect inference state in any way and so you can do it
1153          * at will.
1154          */
1155
1156         if !value.needs_infer() {
1157             return value.clone(); // avoid duplicated subst-folding
1158         }
1159         let mut r = resolve::OpportunisticTypeResolver::new(self);
1160         value.fold_with(&mut r)
1161     }
1162
1163     pub fn resolve_type_and_region_vars_if_possible<T>(&self, value: &T) -> T
1164         where T: TypeFoldable<'tcx>
1165     {
1166         let mut r = resolve::OpportunisticTypeAndRegionResolver::new(self);
1167         value.fold_with(&mut r)
1168     }
1169
1170     pub fn fully_resolve<T:TypeFoldable<'tcx>>(&self, value: &T) -> FixupResult<T> {
1171         /*!
1172          * Attempts to resolve all type/region variables in
1173          * `value`. Region inference must have been run already (e.g.,
1174          * by calling `resolve_regions_and_report_errors`).  If some
1175          * variable was never unified, an `Err` results.
1176          *
1177          * This method is idempotent, but it not typically not invoked
1178          * except during the writeback phase.
1179          */
1180
1181         resolve::fully_resolve(self, value)
1182     }
1183
1184     // [Note-Type-error-reporting]
1185     // An invariant is that anytime the expected or actual type is TyError (the special
1186     // error type, meaning that an error occurred when typechecking this expression),
1187     // this is a derived error. The error cascaded from another error (that was already
1188     // reported), so it's not useful to display it to the user.
1189     // The following methods implement this logic.
1190     // They check if either the actual or expected type is TyError, and don't print the error
1191     // in this case. The typechecker should only ever report type errors involving mismatched
1192     // types using one of these methods, and should not call span_err directly for such
1193     // errors.
1194
1195     pub fn type_error_struct_with_diag<M>(&self,
1196                                           sp: Span,
1197                                           mk_diag: M,
1198                                           actual_ty: Ty<'tcx>)
1199                                           -> DiagnosticBuilder<'tcx>
1200         where M: FnOnce(String) -> DiagnosticBuilder<'tcx>,
1201     {
1202         let actual_ty = self.resolve_type_vars_if_possible(&actual_ty);
1203         debug!("type_error_struct_with_diag({:?}, {:?})", sp, actual_ty);
1204
1205         // Don't report an error if actual type is TyError.
1206         if actual_ty.references_error() {
1207             return self.tcx.sess.diagnostic().struct_dummy();
1208         }
1209
1210         mk_diag(self.ty_to_string(actual_ty))
1211     }
1212
1213     pub fn report_mismatched_types(&self,
1214                                    cause: &ObligationCause<'tcx>,
1215                                    expected: Ty<'tcx>,
1216                                    actual: Ty<'tcx>,
1217                                    err: TypeError<'tcx>)
1218                                    -> DiagnosticBuilder<'tcx> {
1219         let trace = TypeTrace::types(cause, true, expected, actual);
1220         self.report_and_explain_type_error(trace, &err)
1221     }
1222
1223     pub fn report_conflicting_default_types(&self,
1224                                             span: Span,
1225                                             body_id: ast::NodeId,
1226                                             expected: type_variable::Default<'tcx>,
1227                                             actual: type_variable::Default<'tcx>) {
1228         let trace = TypeTrace {
1229             cause: ObligationCause::misc(span, body_id),
1230             values: Types(ExpectedFound {
1231                 expected: expected.ty,
1232                 found: actual.ty
1233             })
1234         };
1235
1236         self.report_and_explain_type_error(
1237             trace,
1238             &TypeError::TyParamDefaultMismatch(ExpectedFound {
1239                 expected,
1240                 found: actual
1241             }))
1242             .emit();
1243     }
1244
1245     pub fn replace_late_bound_regions_with_fresh_var<T>(
1246         &self,
1247         span: Span,
1248         lbrct: LateBoundRegionConversionTime,
1249         value: &ty::Binder<T>)
1250         -> (T, FxHashMap<ty::BoundRegion, ty::Region<'tcx>>)
1251         where T : TypeFoldable<'tcx>
1252     {
1253         self.tcx.replace_late_bound_regions(
1254             value,
1255             |br| self.next_region_var(LateBoundRegion(span, br, lbrct)))
1256     }
1257
1258     /// Given a higher-ranked projection predicate like:
1259     ///
1260     ///     for<'a> <T as Fn<&'a u32>>::Output = &'a u32
1261     ///
1262     /// and a target trait-ref like:
1263     ///
1264     ///     <T as Fn<&'x u32>>
1265     ///
1266     /// find a substitution `S` for the higher-ranked regions (here,
1267     /// `['a => 'x]`) such that the predicate matches the trait-ref,
1268     /// and then return the value (here, `&'a u32`) but with the
1269     /// substitution applied (hence, `&'x u32`).
1270     ///
1271     /// See `higher_ranked_match` in `higher_ranked/mod.rs` for more
1272     /// details.
1273     pub fn match_poly_projection_predicate(&self,
1274                                            cause: ObligationCause<'tcx>,
1275                                            param_env: ty::ParamEnv<'tcx>,
1276                                            match_a: ty::PolyProjectionPredicate<'tcx>,
1277                                            match_b: ty::TraitRef<'tcx>)
1278                                            -> InferResult<'tcx, HrMatchResult<Ty<'tcx>>>
1279     {
1280         let match_pair = match_a.map_bound(|p| (p.projection_ty.trait_ref(self.tcx), p.ty));
1281         let trace = TypeTrace {
1282             cause,
1283             values: TraitRefs(ExpectedFound::new(true, match_pair.skip_binder().0, match_b))
1284         };
1285
1286         let mut combine = self.combine_fields(trace, param_env);
1287         let result = combine.higher_ranked_match(&match_pair, &match_b, true)?;
1288         Ok(InferOk { value: result, obligations: combine.obligations })
1289     }
1290
1291     /// See `verify_generic_bound` method in `region_inference`
1292     pub fn verify_generic_bound(&self,
1293                                 origin: SubregionOrigin<'tcx>,
1294                                 kind: GenericKind<'tcx>,
1295                                 a: ty::Region<'tcx>,
1296                                 bound: VerifyBound<'tcx>) {
1297         debug!("verify_generic_bound({:?}, {:?} <: {:?})",
1298                kind,
1299                a,
1300                bound);
1301
1302         self.region_vars.verify_generic_bound(origin, kind, a, bound);
1303     }
1304
1305     pub fn type_moves_by_default(&self,
1306                                  param_env: ty::ParamEnv<'tcx>,
1307                                  ty: Ty<'tcx>,
1308                                  span: Span)
1309                                  -> bool {
1310         let ty = self.resolve_type_vars_if_possible(&ty);
1311         // Even if the type may have no inference variables, during
1312         // type-checking closure types are in local tables only.
1313         if !self.in_progress_tables.is_some() || !ty.has_closure_types() {
1314             if let Some((param_env, ty)) = self.tcx.lift_to_global(&(param_env, ty)) {
1315                 return ty.moves_by_default(self.tcx.global_tcx(), param_env, span);
1316             }
1317         }
1318
1319         let copy_def_id = self.tcx.require_lang_item(lang_items::CopyTraitLangItem);
1320
1321         // this can get called from typeck (by euv), and moves_by_default
1322         // rightly refuses to work with inference variables, but
1323         // moves_by_default has a cache, which we want to use in other
1324         // cases.
1325         !traits::type_known_to_meet_bound(self, param_env, ty, copy_def_id, span)
1326     }
1327
1328     pub fn closure_kind(&self,
1329                         def_id: DefId)
1330                         -> Option<ty::ClosureKind>
1331     {
1332         if let Some(tables) = self.in_progress_tables {
1333             if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
1334                 let hir_id = self.tcx.hir.node_to_hir_id(id);
1335                 return tables.borrow()
1336                              .closure_kinds()
1337                              .get(hir_id)
1338                              .cloned()
1339                              .map(|(kind, _)| kind);
1340             }
1341         }
1342
1343         // During typeck, ALL closures are local. But afterwards,
1344         // during trans, we see closure ids from other traits.
1345         // That may require loading the closure data out of the
1346         // cstore.
1347         Some(self.tcx.closure_kind(def_id))
1348     }
1349
1350     /// Obtain the signature of a function or closure.
1351     /// For closures, unlike `tcx.fn_sig(def_id)`, this method will
1352     /// work during the type-checking of the enclosing function and
1353     /// return the closure signature in its partially inferred state.
1354     pub fn fn_sig(&self, def_id: DefId) -> ty::PolyFnSig<'tcx> {
1355         if let Some(tables) = self.in_progress_tables {
1356             if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
1357                 let hir_id = self.tcx.hir.node_to_hir_id(id);
1358                 if let Some(&ty) = tables.borrow().closure_tys().get(hir_id) {
1359                     return ty;
1360                 }
1361             }
1362         }
1363
1364         self.tcx.fn_sig(def_id)
1365     }
1366
1367     pub fn generator_sig(&self, def_id: DefId) -> Option<ty::PolyGenSig<'tcx>> {
1368         if let Some(tables) = self.in_progress_tables {
1369             if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
1370                 let hir_id = self.tcx.hir.node_to_hir_id(id);
1371                 if let Some(&ty) = tables.borrow().generator_sigs().get(hir_id) {
1372                     return ty.map(|t| ty::Binder(t));
1373                 }
1374             }
1375         }
1376
1377         self.tcx.generator_sig(def_id)
1378     }
1379 }
1380
1381 impl<'a, 'gcx, 'tcx> TypeTrace<'tcx> {
1382     pub fn span(&self) -> Span {
1383         self.cause.span
1384     }
1385
1386     pub fn types(cause: &ObligationCause<'tcx>,
1387                  a_is_expected: bool,
1388                  a: Ty<'tcx>,
1389                  b: Ty<'tcx>)
1390                  -> TypeTrace<'tcx> {
1391         TypeTrace {
1392             cause: cause.clone(),
1393             values: Types(ExpectedFound::new(a_is_expected, a, b))
1394         }
1395     }
1396
1397     pub fn dummy(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> TypeTrace<'tcx> {
1398         TypeTrace {
1399             cause: ObligationCause::dummy(),
1400             values: Types(ExpectedFound {
1401                 expected: tcx.types.err,
1402                 found: tcx.types.err,
1403             })
1404         }
1405     }
1406 }
1407
1408 impl<'tcx> fmt::Debug for TypeTrace<'tcx> {
1409     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1410         write!(f, "TypeTrace({:?})", self.cause)
1411     }
1412 }
1413
1414 impl<'tcx> SubregionOrigin<'tcx> {
1415     pub fn span(&self) -> Span {
1416         match *self {
1417             Subtype(ref a) => a.span(),
1418             InfStackClosure(a) => a,
1419             InvokeClosure(a) => a,
1420             DerefPointer(a) => a,
1421             FreeVariable(a, _) => a,
1422             IndexSlice(a) => a,
1423             RelateObjectBound(a) => a,
1424             RelateParamBound(a, _) => a,
1425             RelateRegionParamBound(a) => a,
1426             RelateDefaultParamBound(a, _) => a,
1427             Reborrow(a) => a,
1428             ReborrowUpvar(a, _) => a,
1429             DataBorrowed(_, a) => a,
1430             ReferenceOutlivesReferent(_, a) => a,
1431             ParameterInScope(_, a) => a,
1432             ExprTypeIsNotInScope(_, a) => a,
1433             BindingTypeIsNotValidAtDecl(a) => a,
1434             CallRcvr(a) => a,
1435             CallArg(a) => a,
1436             CallReturn(a) => a,
1437             Operand(a) => a,
1438             AddrOf(a) => a,
1439             AutoBorrow(a) => a,
1440             SafeDestructor(a) => a,
1441             CompareImplMethodObligation { span, .. } => span,
1442         }
1443     }
1444
1445     pub fn from_obligation_cause<F>(cause: &traits::ObligationCause<'tcx>,
1446                                     default: F)
1447                                     -> Self
1448         where F: FnOnce() -> Self
1449     {
1450         match cause.code {
1451             traits::ObligationCauseCode::ReferenceOutlivesReferent(ref_type) =>
1452                 SubregionOrigin::ReferenceOutlivesReferent(ref_type, cause.span),
1453
1454             traits::ObligationCauseCode::CompareImplMethodObligation { item_name,
1455                                                                        impl_item_def_id,
1456                                                                        trait_item_def_id,
1457                                                                        lint_id } =>
1458                 SubregionOrigin::CompareImplMethodObligation {
1459                     span: cause.span,
1460                     item_name,
1461                     impl_item_def_id,
1462                     trait_item_def_id,
1463                     lint_id,
1464                 },
1465
1466             _ => default(),
1467         }
1468     }
1469 }
1470
1471 impl RegionVariableOrigin {
1472     pub fn span(&self) -> Span {
1473         match *self {
1474             MiscVariable(a) => a,
1475             PatternRegion(a) => a,
1476             AddrOfRegion(a) => a,
1477             Autoref(a) => a,
1478             Coercion(a) => a,
1479             EarlyBoundRegion(a, ..) => a,
1480             LateBoundRegion(a, ..) => a,
1481             BoundRegionInCoherence(_) => syntax_pos::DUMMY_SP,
1482             UpvarRegion(_, a) => a
1483         }
1484     }
1485 }
1486
1487 impl<'tcx> TypeFoldable<'tcx> for ValuePairs<'tcx> {
1488     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1489         match *self {
1490             ValuePairs::Types(ref ef) => {
1491                 ValuePairs::Types(ef.fold_with(folder))
1492             }
1493             ValuePairs::TraitRefs(ref ef) => {
1494                 ValuePairs::TraitRefs(ef.fold_with(folder))
1495             }
1496             ValuePairs::PolyTraitRefs(ref ef) => {
1497                 ValuePairs::PolyTraitRefs(ef.fold_with(folder))
1498             }
1499         }
1500     }
1501
1502     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1503         match *self {
1504             ValuePairs::Types(ref ef) => ef.visit_with(visitor),
1505             ValuePairs::TraitRefs(ref ef) => ef.visit_with(visitor),
1506             ValuePairs::PolyTraitRefs(ref ef) => ef.visit_with(visitor),
1507         }
1508     }
1509 }
1510
1511 impl<'tcx> TypeFoldable<'tcx> for TypeTrace<'tcx> {
1512     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1513         TypeTrace {
1514             cause: self.cause.fold_with(folder),
1515             values: self.values.fold_with(folder)
1516         }
1517     }
1518
1519     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1520         self.cause.visit_with(visitor) || self.values.visit_with(visitor)
1521     }
1522 }