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 ty::Const<'gcx>,
 446     &'gcx Substs<'gcx>,
 447     ty::FnSig<'gcx>,
 448     ty::PolyFnSig<'gcx>,
 449     ty::ClosureSubsts<'gcx>,
 450     ty::PolyTraitRef<'gcx>,
 451     ty::ExistentialTraitRef<'gcx>
 452 );
 453
 454 impl<'gcx> TransNormalize<'gcx> for LvalueTy<'gcx> {
 455     fn trans_normalize<'a, 'tcx>(&self,
 456                                  infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 457                                  param_env: ty::ParamEnv<'tcx>)
 458                                  -> Self {
 459         match *self {
 460             LvalueTy::Ty { ty } => LvalueTy::Ty { ty: ty.trans_normalize(infcx, param_env) },
 461             LvalueTy::Downcast { adt_def, substs, variant_index } => {
 462                 LvalueTy::Downcast {
 463                     adt_def,
 464                     substs: substs.trans_normalize(infcx, param_env),
 465                     variant_index,
 466                 }
 467             }
 468         }
 469     }
 470 }
 471
 472 // NOTE: Callable from trans only!
 473 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
 474     /// Currently, higher-ranked type bounds inhibit normalization. Therefore,
 475     /// each time we erase them in translation, we need to normalize
 476     /// the contents.
 477     pub fn erase_late_bound_regions_and_normalize<T>(self, value: &ty::Binder<T>)
 478         -> T
 479         where T: TransNormalize<'tcx>
 480     {
 481         assert!(!value.needs_subst());
 482         let value = self.erase_late_bound_regions(value);
 483         self.normalize_associated_type(&value)
 484     }
 485
 486     /// Fully normalizes any associated types in `value`, using an
 487     /// empty environment and `Reveal::All` mode (therefore, suitable
 488     /// only for monomorphized code during trans, basically).
 489     pub fn normalize_associated_type<T>(self, value: &T) -> T
 490         where T: TransNormalize<'tcx>
 491     {
 492         debug!("normalize_associated_type(t={:?})", value);
 493
 494         let param_env = ty::ParamEnv::empty(Reveal::All);
 495         let value = self.erase_regions(value);
 496
 497         if !value.has_projections() {
 498             return value;
 499         }
 500
 501         self.infer_ctxt().enter(|infcx| {
 502             value.trans_normalize(&infcx, param_env)
 503         })
 504     }
 505
 506     /// Does a best-effort to normalize any associated types in
 507     /// `value`; this includes revealing specializable types, so this
 508     /// should be not be used during type-checking, but only during
 509     /// optimization and code generation.
 510     pub fn normalize_associated_type_in_env<T>(
 511         self, value: &T, env: ty::ParamEnv<'tcx>
 512     ) -> T
 513         where T: TransNormalize<'tcx>
 514     {
 515         debug!("normalize_associated_type_in_env(t={:?})", value);
 516
 517         let value = self.erase_regions(value);
 518
 519         if !value.has_projections() {
 520             return value;
 521         }
 522
 523         self.infer_ctxt().enter(|infcx| {
 524             value.trans_normalize(&infcx, env.reveal_all())
 525        })
 526     }
 527 }
 528
 529 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 530     fn normalize_projections_in<T>(&self, param_env: ty::ParamEnv<'tcx>, value: &T) -> T::Lifted
 531         where T: TypeFoldable<'tcx> + ty::Lift<'gcx>
 532     {
 533         let mut selcx = traits::SelectionContext::new(self);
 534         let cause = traits::ObligationCause::dummy();
 535         let traits::Normalized { value: result, obligations } =
 536             traits::normalize(&mut selcx, param_env, cause, value);
 537
 538         debug!("normalize_projections_in: result={:?} obligations={:?}",
 539                 result, obligations);
 540
 541         let mut fulfill_cx = traits::FulfillmentContext::new();
 542
 543         for obligation in obligations {
 544             fulfill_cx.register_predicate_obligation(self, obligation);
 545         }
 546
 547         self.drain_fulfillment_cx_or_panic(DUMMY_SP, &mut fulfill_cx, &result)
 548     }
 549
 550     /// Finishes processes any obligations that remain in the
 551     /// fulfillment context, and then returns the result with all type
 552     /// variables removed and regions erased. Because this is intended
 553     /// for use after type-check has completed, if any errors occur,
 554     /// it will panic. It is used during normalization and other cases
 555     /// where processing the obligations in `fulfill_cx` may cause
 556     /// type inference variables that appear in `result` to be
 557     /// unified, and hence we need to process those obligations to get
 558     /// the complete picture of the type.
 559     pub fn drain_fulfillment_cx_or_panic<T>(&self,
 560                                             span: Span,
 561                                             fulfill_cx: &mut traits::FulfillmentContext<'tcx>,
 562                                             result: &T)
 563                                             -> T::Lifted
 564         where T: TypeFoldable<'tcx> + ty::Lift<'gcx>
 565     {
 566         debug!("drain_fulfillment_cx_or_panic()");
 567
 568         // In principle, we only need to do this so long as `result`
 569         // contains unbound type parameters. It could be a slight
 570         // optimization to stop iterating early.
 571         match fulfill_cx.select_all_or_error(self) {
 572             Ok(()) => { }
 573             Err(errors) => {
 574                 span_bug!(span, "Encountered errors `{:?}` resolving bounds after type-checking",
 575                           errors);
 576             }
 577         }
 578
 579         let result = self.resolve_type_vars_if_possible(result);
 580         let result = self.tcx.erase_regions(&result);
 581
 582         match self.tcx.lift_to_global(&result) {
 583             Some(result) => result,
 584             None => {
 585                 span_bug!(span, "Uninferred types/regions in `{:?}`", result);
 586             }
 587         }
 588     }
 589
 590     pub fn is_in_snapshot(&self) -> bool {
 591         self.in_snapshot.get()
 592     }
 593
 594     pub fn freshen<T:TypeFoldable<'tcx>>(&self, t: T) -> T {
 595         t.fold_with(&mut self.freshener())
 596     }
 597
 598     pub fn type_var_diverges(&'a self, ty: Ty) -> bool {
 599         match ty.sty {
 600             ty::TyInfer(ty::TyVar(vid)) => self.type_variables.borrow().var_diverges(vid),
 601             _ => false
 602         }
 603     }
 604
 605     pub fn freshener<'b>(&'b self) -> TypeFreshener<'b, 'gcx, 'tcx> {
 606         freshen::TypeFreshener::new(self)
 607     }
 608
 609     pub fn type_is_unconstrained_numeric(&'a self, ty: Ty) -> UnconstrainedNumeric {
 610         use ty::error::UnconstrainedNumeric::Neither;
 611         use ty::error::UnconstrainedNumeric::{UnconstrainedInt, UnconstrainedFloat};
 612         match ty.sty {
 613             ty::TyInfer(ty::IntVar(vid)) => {
 614                 if self.int_unification_table.borrow_mut().has_value(vid) {
 615                     Neither
 616                 } else {
 617                     UnconstrainedInt
 618                 }
 619             },
 620             ty::TyInfer(ty::FloatVar(vid)) => {
 621                 if self.float_unification_table.borrow_mut().has_value(vid) {
 622                     Neither
 623                 } else {
 624                     UnconstrainedFloat
 625                 }
 626             },
 627             _ => Neither,
 628         }
 629     }
 630
 631     /// Returns a type variable's default fallback if any exists. A default
 632     /// must be attached to the variable when created, if it is created
 633     /// without a default, this will return None.
 634     ///
 635     /// This code does not apply to integral or floating point variables,
 636     /// only to use declared defaults.
 637     ///
 638     /// See `new_ty_var_with_default` to create a type variable with a default.
 639     /// See `type_variable::Default` for details about what a default entails.
 640     pub fn default(&self, ty: Ty<'tcx>) -> Option<type_variable::Default<'tcx>> {
 641         match ty.sty {
 642             ty::TyInfer(ty::TyVar(vid)) => self.type_variables.borrow().default(vid),
 643             _ => None
 644         }
 645     }
 646
 647     pub fn unsolved_variables(&self) -> Vec<ty::Ty<'tcx>> {
 648         let mut variables = Vec::new();
 649
 650         let unbound_ty_vars = self.type_variables
 651                                   .borrow_mut()
 652                                   .unsolved_variables()
 653                                   .into_iter()
 654                                   .map(|t| self.tcx.mk_var(t));
 655
 656         let unbound_int_vars = self.int_unification_table
 657                                    .borrow_mut()
 658                                    .unsolved_variables()
 659                                    .into_iter()
 660                                    .map(|v| self.tcx.mk_int_var(v));
 661
 662         let unbound_float_vars = self.float_unification_table
 663                                      .borrow_mut()
 664                                      .unsolved_variables()
 665                                      .into_iter()
 666                                      .map(|v| self.tcx.mk_float_var(v));
 667
 668         variables.extend(unbound_ty_vars);
 669         variables.extend(unbound_int_vars);
 670         variables.extend(unbound_float_vars);
 671
 672         return variables;
 673     }
 674
 675     fn combine_fields(&'a self, trace: TypeTrace<'tcx>, param_env: ty::ParamEnv<'tcx>)
 676                       -> CombineFields<'a, 'gcx, 'tcx> {
 677         CombineFields {
 678             infcx: self,
 679             trace,
 680             cause: None,
 681             param_env,
 682             obligations: PredicateObligations::new(),
 683         }
 684     }
 685
 686     // Clear the "currently in a snapshot" flag, invoke the closure,
 687     // then restore the flag to its original value. This flag is a
 688     // debugging measure designed to detect cases where we start a
 689     // snapshot, create type variables, and register obligations
 690     // which may involve those type variables in the fulfillment cx,
 691     // potentially leaving "dangling type variables" behind.
 692     // In such cases, an assertion will fail when attempting to
 693     // register obligations, within a snapshot. Very useful, much
 694     // better than grovelling through megabytes of RUST_LOG output.
 695     //
 696     // HOWEVER, in some cases the flag is unhelpful. In particular, we
 697     // sometimes create a "mini-fulfilment-cx" in which we enroll
 698     // obligations. As long as this fulfillment cx is fully drained
 699     // before we return, this is not a problem, as there won't be any
 700     // escaping obligations in the main cx. In those cases, you can
 701     // use this function.
 702     pub fn save_and_restore_in_snapshot_flag<F, R>(&self, func: F) -> R
 703         where F: FnOnce(&Self) -> R
 704     {
 705         let flag = self.in_snapshot.get();
 706         self.in_snapshot.set(false);
 707         let result = func(self);
 708         self.in_snapshot.set(flag);
 709         result
 710     }
 711
 712     fn start_snapshot<'b>(&'b self) -> CombinedSnapshot<'b, 'tcx> {
 713         debug!("start_snapshot()");
 714
 715         let in_snapshot = self.in_snapshot.get();
 716         self.in_snapshot.set(true);
 717
 718         CombinedSnapshot {
 719             projection_cache_snapshot: self.projection_cache.borrow_mut().snapshot(),
 720             type_snapshot: self.type_variables.borrow_mut().snapshot(),
 721             int_snapshot: self.int_unification_table.borrow_mut().snapshot(),
 722             float_snapshot: self.float_unification_table.borrow_mut().snapshot(),
 723             region_vars_snapshot: self.region_vars.start_snapshot(),
 724             was_in_snapshot: in_snapshot,
 725             // Borrow tables "in progress" (i.e. during typeck)
 726             // to ban writes from within a snapshot to them.
 727             _in_progress_tables: self.in_progress_tables.map(|tables| {
 728                 tables.borrow()
 729             })
 730         }
 731     }
 732
 733     fn rollback_to(&self, cause: &str, snapshot: CombinedSnapshot) {
 734         debug!("rollback_to(cause={})", cause);
 735         let CombinedSnapshot { projection_cache_snapshot,
 736                                type_snapshot,
 737                                int_snapshot,
 738                                float_snapshot,
 739                                region_vars_snapshot,
 740                                was_in_snapshot,
 741                                _in_progress_tables } = snapshot;
 742
 743         self.in_snapshot.set(was_in_snapshot);
 744
 745         self.projection_cache
 746             .borrow_mut()
 747             .rollback_to(projection_cache_snapshot);
 748         self.type_variables
 749             .borrow_mut()
 750             .rollback_to(type_snapshot);
 751         self.int_unification_table
 752             .borrow_mut()
 753             .rollback_to(int_snapshot);
 754         self.float_unification_table
 755             .borrow_mut()
 756             .rollback_to(float_snapshot);
 757         self.region_vars
 758             .rollback_to(region_vars_snapshot);
 759     }
 760
 761     fn commit_from(&self, snapshot: CombinedSnapshot) {
 762         debug!("commit_from()");
 763         let CombinedSnapshot { projection_cache_snapshot,
 764                                type_snapshot,
 765                                int_snapshot,
 766                                float_snapshot,
 767                                region_vars_snapshot,
 768                                was_in_snapshot,
 769                                _in_progress_tables } = snapshot;
 770
 771         self.in_snapshot.set(was_in_snapshot);
 772
 773         self.projection_cache
 774             .borrow_mut()
 775             .commit(projection_cache_snapshot);
 776         self.type_variables
 777             .borrow_mut()
 778             .commit(type_snapshot);
 779         self.int_unification_table
 780             .borrow_mut()
 781             .commit(int_snapshot);
 782         self.float_unification_table
 783             .borrow_mut()
 784             .commit(float_snapshot);
 785         self.region_vars
 786             .commit(region_vars_snapshot);
 787     }
 788
 789     /// Execute `f` and commit the bindings
 790     pub fn commit_unconditionally<R, F>(&self, f: F) -> R where
 791         F: FnOnce() -> R,
 792     {
 793         debug!("commit()");
 794         let snapshot = self.start_snapshot();
 795         let r = f();
 796         self.commit_from(snapshot);
 797         r
 798     }
 799
 800     /// Execute `f` and commit the bindings if closure `f` returns `Ok(_)`
 801     pub fn commit_if_ok<T, E, F>(&self, f: F) -> Result<T, E> where
 802         F: FnOnce(&CombinedSnapshot) -> Result<T, E>
 803     {
 804         debug!("commit_if_ok()");
 805         let snapshot = self.start_snapshot();
 806         let r = f(&snapshot);
 807         debug!("commit_if_ok() -- r.is_ok() = {}", r.is_ok());
 808         match r {
 809             Ok(_) => { self.commit_from(snapshot); }
 810             Err(_) => { self.rollback_to("commit_if_ok -- error", snapshot); }
 811         }
 812         r
 813     }
 814
 815     // Execute `f` in a snapshot, and commit the bindings it creates
 816     pub fn in_snapshot<T, F>(&self, f: F) -> T where
 817         F: FnOnce(&CombinedSnapshot) -> T
 818     {
 819         debug!("in_snapshot()");
 820         let snapshot = self.start_snapshot();
 821         let r = f(&snapshot);
 822         self.commit_from(snapshot);
 823         r
 824     }
 825
 826     /// Execute `f` then unroll any bindings it creates
 827     pub fn probe<R, F>(&self, f: F) -> R where
 828         F: FnOnce(&CombinedSnapshot) -> R,
 829     {
 830         debug!("probe()");
 831         let snapshot = self.start_snapshot();
 832         let r = f(&snapshot);
 833         self.rollback_to("probe", snapshot);
 834         r
 835     }
 836
 837     pub fn add_given(&self,
 838                      sub: ty::Region<'tcx>,
 839                      sup: ty::RegionVid)
 840     {
 841         self.region_vars.add_given(sub, sup);
 842     }
 843
 844     pub fn can_sub<T>(&self,
 845                       param_env: ty::ParamEnv<'tcx>,
 846                       a: T,
 847                       b: T)
 848                       -> UnitResult<'tcx>
 849         where T: at::ToTrace<'tcx>
 850     {
 851         let origin = &ObligationCause::dummy();
 852         self.probe(|_| {
 853             self.at(origin, param_env).sub(a, b).map(|InferOk { obligations: _, .. }| {
 854                 // Ignore obligations, since we are unrolling
 855                 // everything anyway.
 856             })
 857         })
 858     }
 859
 860     pub fn can_eq<T>(&self,
 861                       param_env: ty::ParamEnv<'tcx>,
 862                       a: T,
 863                       b: T)
 864                       -> UnitResult<'tcx>
 865         where T: at::ToTrace<'tcx>
 866     {
 867         let origin = &ObligationCause::dummy();
 868         self.probe(|_| {
 869             self.at(origin, param_env).eq(a, b).map(|InferOk { obligations: _, .. }| {
 870                 // Ignore obligations, since we are unrolling
 871                 // everything anyway.
 872             })
 873         })
 874     }
 875
 876     pub fn sub_regions(&self,
 877                        origin: SubregionOrigin<'tcx>,
 878                        a: ty::Region<'tcx>,
 879                        b: ty::Region<'tcx>) {
 880         debug!("sub_regions({:?} <: {:?})", a, b);
 881         self.region_vars.make_subregion(origin, a, b);
 882     }
 883
 884     pub fn equality_predicate(&self,
 885                               cause: &ObligationCause<'tcx>,
 886                               param_env: ty::ParamEnv<'tcx>,
 887                               predicate: &ty::PolyEquatePredicate<'tcx>)
 888         -> InferResult<'tcx, ()>
 889     {
 890         self.commit_if_ok(|snapshot| {
 891             let (ty::EquatePredicate(a, b), skol_map) =
 892                 self.skolemize_late_bound_regions(predicate, snapshot);
 893             let cause_span = cause.span;
 894             let eqty_ok = self.at(cause, param_env).eq(b, a)?;
 895             self.leak_check(false, cause_span, &skol_map, snapshot)?;
 896             self.pop_skolemized(skol_map, snapshot);
 897             Ok(eqty_ok.unit())
 898         })
 899     }
 900
 901     pub fn subtype_predicate(&self,
 902                              cause: &ObligationCause<'tcx>,
 903                              param_env: ty::ParamEnv<'tcx>,
 904                              predicate: &ty::PolySubtypePredicate<'tcx>)
 905         -> Option<InferResult<'tcx, ()>>
 906     {
 907         // Subtle: it's ok to skip the binder here and resolve because
 908         // `shallow_resolve` just ignores anything that is not a type
 909         // variable, and because type variable's can't (at present, at
 910         // least) capture any of the things bound by this binder.
 911         //
 912         // Really, there is no *particular* reason to do this
 913         // `shallow_resolve` here except as a
 914         // micro-optimization. Naturally I could not
 915         // resist. -nmatsakis
 916         let two_unbound_type_vars = {
 917             let a = self.shallow_resolve(predicate.skip_binder().a);
 918             let b = self.shallow_resolve(predicate.skip_binder().b);
 919             a.is_ty_var() && b.is_ty_var()
 920         };
 921
 922         if two_unbound_type_vars {
 923             // Two unbound type variables? Can't make progress.
 924             return None;
 925         }
 926
 927         Some(self.commit_if_ok(|snapshot| {
 928             let (ty::SubtypePredicate { a_is_expected, a, b}, skol_map) =
 929                 self.skolemize_late_bound_regions(predicate, snapshot);
 930
 931             let cause_span = cause.span;
 932             let ok = self.at(cause, param_env).sub_exp(a_is_expected, a, b)?;
 933             self.leak_check(false, cause_span, &skol_map, snapshot)?;
 934             self.pop_skolemized(skol_map, snapshot);
 935             Ok(ok.unit())
 936         }))
 937     }
 938
 939     pub fn region_outlives_predicate(&self,
 940                                      cause: &traits::ObligationCause<'tcx>,
 941                                      predicate: &ty::PolyRegionOutlivesPredicate<'tcx>)
 942         -> UnitResult<'tcx>
 943     {
 944         self.commit_if_ok(|snapshot| {
 945             let (ty::OutlivesPredicate(r_a, r_b), skol_map) =
 946                 self.skolemize_late_bound_regions(predicate, snapshot);
 947             let origin =
 948                 SubregionOrigin::from_obligation_cause(cause,
 949                                                        || RelateRegionParamBound(cause.span));
 950             self.sub_regions(origin, r_b, r_a); // `b : a` ==> `a <= b`
 951             self.leak_check(false, cause.span, &skol_map, snapshot)?;
 952             Ok(self.pop_skolemized(skol_map, snapshot))
 953         })
 954     }
 955
 956     pub fn next_ty_var_id(&self, diverging: bool, origin: TypeVariableOrigin) -> TyVid {
 957         self.type_variables
 958             .borrow_mut()
 959             .new_var(diverging, origin, None)
 960     }
 961
 962     pub fn next_ty_var(&self, origin: TypeVariableOrigin) -> Ty<'tcx> {
 963         self.tcx.mk_var(self.next_ty_var_id(false, origin))
 964     }
 965
 966     pub fn next_diverging_ty_var(&self, origin: TypeVariableOrigin) -> Ty<'tcx> {
 967         self.tcx.mk_var(self.next_ty_var_id(true, origin))
 968     }
 969
 970     pub fn next_int_var_id(&self) -> IntVid {
 971         self.int_unification_table
 972             .borrow_mut()
 973             .new_key(None)
 974     }
 975
 976     pub fn next_float_var_id(&self) -> FloatVid {
 977         self.float_unification_table
 978             .borrow_mut()
 979             .new_key(None)
 980     }
 981
 982     pub fn next_region_var(&self, origin: RegionVariableOrigin)
 983                            -> ty::Region<'tcx> {
 984         self.tcx.mk_region(ty::ReVar(self.region_vars.new_region_var(origin)))
 985     }
 986
 987     /// Create a region inference variable for the given
 988     /// region parameter definition.
 989     pub fn region_var_for_def(&self,
 990                               span: Span,
 991                               def: &ty::RegionParameterDef)
 992                               -> ty::Region<'tcx> {
 993         self.next_region_var(EarlyBoundRegion(span, def.name))
 994     }
 995
 996     /// Create a type inference variable for the given
 997     /// type parameter definition. The substitutions are
 998     /// for actual parameters that may be referred to by
 999     /// the default of this type parameter, if it exists.
1000     /// E.g. `struct Foo<A, B, C = (A, B)>(...);` when
1001     /// used in a path such as `Foo::<T, U>::new()` will
1002     /// use an inference variable for `C` with `[T, U]`
1003     /// as the substitutions for the default, `(T, U)`.
1004     pub fn type_var_for_def(&self,
1005                             span: Span,
1006                             def: &ty::TypeParameterDef,
1007                             substs: &[Kind<'tcx>])
1008                             -> Ty<'tcx> {
1009         let default = if def.has_default {
1010             let default = self.tcx.type_of(def.def_id);
1011             Some(type_variable::Default {
1012                 ty: default.subst_spanned(self.tcx, substs, Some(span)),
1013                 origin_span: span,
1014                 def_id: def.def_id
1015             })
1016         } else {
1017             None
1018         };
1019
1020
1021         let ty_var_id = self.type_variables
1022                             .borrow_mut()
1023                             .new_var(false,
1024                                      TypeVariableOrigin::TypeParameterDefinition(span, def.name),
1025                                      default);
1026
1027         self.tcx.mk_var(ty_var_id)
1028     }
1029
1030     /// Given a set of generics defined on a type or impl, returns a substitution mapping each
1031     /// type/region parameter to a fresh inference variable.
1032     pub fn fresh_substs_for_item(&self,
1033                                  span: Span,
1034                                  def_id: DefId)
1035                                  -> &'tcx Substs<'tcx> {
1036         Substs::for_item(self.tcx, def_id, |def, _| {
1037             self.region_var_for_def(span, def)
1038         }, |def, substs| {
1039             self.type_var_for_def(span, def, substs)
1040         })
1041     }
1042
1043     pub fn fresh_bound_region(&self, debruijn: ty::DebruijnIndex) -> ty::Region<'tcx> {
1044         self.region_vars.new_bound(debruijn)
1045     }
1046
1047     /// True if errors have been reported since this infcx was
1048     /// created.  This is sometimes used as a heuristic to skip
1049     /// reporting errors that often occur as a result of earlier
1050     /// errors, but where it's hard to be 100% sure (e.g., unresolved
1051     /// inference variables, regionck errors).
1052     pub fn is_tainted_by_errors(&self) -> bool {
1053         debug!("is_tainted_by_errors(err_count={}, err_count_on_creation={}, \
1054                 tainted_by_errors_flag={})",
1055                self.tcx.sess.err_count(),
1056                self.err_count_on_creation,
1057                self.tainted_by_errors_flag.get());
1058
1059         if self.tcx.sess.err_count() > self.err_count_on_creation {
1060             return true; // errors reported since this infcx was made
1061         }
1062         self.tainted_by_errors_flag.get()
1063     }
1064
1065     /// Set the "tainted by errors" flag to true. We call this when we
1066     /// observe an error from a prior pass.
1067     pub fn set_tainted_by_errors(&self) {
1068         debug!("set_tainted_by_errors()");
1069         self.tainted_by_errors_flag.set(true)
1070     }
1071
1072     pub fn resolve_regions_and_report_errors(&self,
1073                                              region_context: DefId,
1074                                              region_map: &region::ScopeTree,
1075                                              free_regions: &FreeRegionMap<'tcx>) {
1076         let region_rels = RegionRelations::new(self.tcx,
1077                                                region_context,
1078                                                region_map,
1079                                                free_regions);
1080         let errors = self.region_vars.resolve_regions(&region_rels);
1081
1082         if !self.is_tainted_by_errors() {
1083             // As a heuristic, just skip reporting region errors
1084             // altogether if other errors have been reported while
1085             // this infcx was in use.  This is totally hokey but
1086             // otherwise we have a hard time separating legit region
1087             // errors from silly ones.
1088             self.report_region_errors(region_map, &errors); // see error_reporting module
1089         }
1090     }
1091
1092     pub fn ty_to_string(&self, t: Ty<'tcx>) -> String {
1093         self.resolve_type_vars_if_possible(&t).to_string()
1094     }
1095
1096     pub fn tys_to_string(&self, ts: &[Ty<'tcx>]) -> String {
1097         let tstrs: Vec<String> = ts.iter().map(|t| self.ty_to_string(*t)).collect();
1098         format!("({})", tstrs.join(", "))
1099     }
1100
1101     pub fn trait_ref_to_string(&self, t: &ty::TraitRef<'tcx>) -> String {
1102         self.resolve_type_vars_if_possible(t).to_string()
1103     }
1104
1105     pub fn shallow_resolve(&self, typ: Ty<'tcx>) -> Ty<'tcx> {
1106         match typ.sty {
1107             ty::TyInfer(ty::TyVar(v)) => {
1108                 // Not entirely obvious: if `typ` is a type variable,
1109                 // it can be resolved to an int/float variable, which
1110                 // can then be recursively resolved, hence the
1111                 // recursion. Note though that we prevent type
1112                 // variables from unifying to other type variables
1113                 // directly (though they may be embedded
1114                 // structurally), and we prevent cycles in any case,
1115                 // so this recursion should always be of very limited
1116                 // depth.
1117                 self.type_variables.borrow_mut()
1118                     .probe(v)
1119                     .map(|t| self.shallow_resolve(t))
1120                     .unwrap_or(typ)
1121             }
1122
1123             ty::TyInfer(ty::IntVar(v)) => {
1124                 self.int_unification_table
1125                     .borrow_mut()
1126                     .probe(v)
1127                     .map(|v| v.to_type(self.tcx))
1128                     .unwrap_or(typ)
1129             }
1130
1131             ty::TyInfer(ty::FloatVar(v)) => {
1132                 self.float_unification_table
1133                     .borrow_mut()
1134                     .probe(v)
1135                     .map(|v| v.to_type(self.tcx))
1136                     .unwrap_or(typ)
1137             }
1138
1139             _ => {
1140                 typ
1141             }
1142         }
1143     }
1144
1145     pub fn resolve_type_vars_if_possible<T>(&self, value: &T) -> T
1146         where T: TypeFoldable<'tcx>
1147     {
1148         /*!
1149          * Where possible, replaces type/int/float variables in
1150          * `value` with their final value. Note that region variables
1151          * are unaffected. If a type variable has not been unified, it
1152          * is left as is.  This is an idempotent operation that does
1153          * not affect inference state in any way and so you can do it
1154          * at will.
1155          */
1156
1157         if !value.needs_infer() {
1158             return value.clone(); // avoid duplicated subst-folding
1159         }
1160         let mut r = resolve::OpportunisticTypeResolver::new(self);
1161         value.fold_with(&mut r)
1162     }
1163
1164     /// Returns true if `T` contains unresolved type variables. In the
1165     /// process of visiting `T`, this will resolve (where possible)
1166     /// type variables in `T`, but it never constructs the final,
1167     /// resolved type, so it's more efficient than
1168     /// `resolve_type_vars_if_possible()`.
1169     pub fn any_unresolved_type_vars<T>(&self, value: &T) -> bool
1170         where T: TypeFoldable<'tcx>
1171     {
1172         let mut r = resolve::UnresolvedTypeFinder::new(self);
1173         value.visit_with(&mut r)
1174     }
1175
1176     pub fn resolve_type_and_region_vars_if_possible<T>(&self, value: &T) -> T
1177         where T: TypeFoldable<'tcx>
1178     {
1179         let mut r = resolve::OpportunisticTypeAndRegionResolver::new(self);
1180         value.fold_with(&mut r)
1181     }
1182
1183     pub fn fully_resolve<T:TypeFoldable<'tcx>>(&self, value: &T) -> FixupResult<T> {
1184         /*!
1185          * Attempts to resolve all type/region variables in
1186          * `value`. Region inference must have been run already (e.g.,
1187          * by calling `resolve_regions_and_report_errors`).  If some
1188          * variable was never unified, an `Err` results.
1189          *
1190          * This method is idempotent, but it not typically not invoked
1191          * except during the writeback phase.
1192          */
1193
1194         resolve::fully_resolve(self, value)
1195     }
1196
1197     // [Note-Type-error-reporting]
1198     // An invariant is that anytime the expected or actual type is TyError (the special
1199     // error type, meaning that an error occurred when typechecking this expression),
1200     // this is a derived error. The error cascaded from another error (that was already
1201     // reported), so it's not useful to display it to the user.
1202     // The following methods implement this logic.
1203     // They check if either the actual or expected type is TyError, and don't print the error
1204     // in this case. The typechecker should only ever report type errors involving mismatched
1205     // types using one of these methods, and should not call span_err directly for such
1206     // errors.
1207
1208     pub fn type_error_struct_with_diag<M>(&self,
1209                                           sp: Span,
1210                                           mk_diag: M,
1211                                           actual_ty: Ty<'tcx>)
1212                                           -> DiagnosticBuilder<'tcx>
1213         where M: FnOnce(String) -> DiagnosticBuilder<'tcx>,
1214     {
1215         let actual_ty = self.resolve_type_vars_if_possible(&actual_ty);
1216         debug!("type_error_struct_with_diag({:?}, {:?})", sp, actual_ty);
1217
1218         // Don't report an error if actual type is TyError.
1219         if actual_ty.references_error() {
1220             return self.tcx.sess.diagnostic().struct_dummy();
1221         }
1222
1223         mk_diag(self.ty_to_string(actual_ty))
1224     }
1225
1226     pub fn report_mismatched_types(&self,
1227                                    cause: &ObligationCause<'tcx>,
1228                                    expected: Ty<'tcx>,
1229                                    actual: Ty<'tcx>,
1230                                    err: TypeError<'tcx>)
1231                                    -> DiagnosticBuilder<'tcx> {
1232         let trace = TypeTrace::types(cause, true, expected, actual);
1233         self.report_and_explain_type_error(trace, &err)
1234     }
1235
1236     pub fn report_conflicting_default_types(&self,
1237                                             span: Span,
1238                                             body_id: ast::NodeId,
1239                                             expected: type_variable::Default<'tcx>,
1240                                             actual: type_variable::Default<'tcx>) {
1241         let trace = TypeTrace {
1242             cause: ObligationCause::misc(span, body_id),
1243             values: Types(ExpectedFound {
1244                 expected: expected.ty,
1245                 found: actual.ty
1246             })
1247         };
1248
1249         self.report_and_explain_type_error(
1250             trace,
1251             &TypeError::TyParamDefaultMismatch(ExpectedFound {
1252                 expected,
1253                 found: actual
1254             }))
1255             .emit();
1256     }
1257
1258     pub fn replace_late_bound_regions_with_fresh_var<T>(
1259         &self,
1260         span: Span,
1261         lbrct: LateBoundRegionConversionTime,
1262         value: &ty::Binder<T>)
1263         -> (T, FxHashMap<ty::BoundRegion, ty::Region<'tcx>>)
1264         where T : TypeFoldable<'tcx>
1265     {
1266         self.tcx.replace_late_bound_regions(
1267             value,
1268             |br| self.next_region_var(LateBoundRegion(span, br, lbrct)))
1269     }
1270
1271     /// Given a higher-ranked projection predicate like:
1272     ///
1273     ///     for<'a> <T as Fn<&'a u32>>::Output = &'a u32
1274     ///
1275     /// and a target trait-ref like:
1276     ///
1277     ///     <T as Fn<&'x u32>>
1278     ///
1279     /// find a substitution `S` for the higher-ranked regions (here,
1280     /// `['a => 'x]`) such that the predicate matches the trait-ref,
1281     /// and then return the value (here, `&'a u32`) but with the
1282     /// substitution applied (hence, `&'x u32`).
1283     ///
1284     /// See `higher_ranked_match` in `higher_ranked/mod.rs` for more
1285     /// details.
1286     pub fn match_poly_projection_predicate(&self,
1287                                            cause: ObligationCause<'tcx>,
1288                                            param_env: ty::ParamEnv<'tcx>,
1289                                            match_a: ty::PolyProjectionPredicate<'tcx>,
1290                                            match_b: ty::TraitRef<'tcx>)
1291                                            -> InferResult<'tcx, HrMatchResult<Ty<'tcx>>>
1292     {
1293         let match_pair = match_a.map_bound(|p| (p.projection_ty.trait_ref(self.tcx), p.ty));
1294         let trace = TypeTrace {
1295             cause,
1296             values: TraitRefs(ExpectedFound::new(true, match_pair.skip_binder().0, match_b))
1297         };
1298
1299         let mut combine = self.combine_fields(trace, param_env);
1300         let result = combine.higher_ranked_match(&match_pair, &match_b, true)?;
1301         Ok(InferOk { value: result, obligations: combine.obligations })
1302     }
1303
1304     /// See `verify_generic_bound` method in `region_inference`
1305     pub fn verify_generic_bound(&self,
1306                                 origin: SubregionOrigin<'tcx>,
1307                                 kind: GenericKind<'tcx>,
1308                                 a: ty::Region<'tcx>,
1309                                 bound: VerifyBound<'tcx>) {
1310         debug!("verify_generic_bound({:?}, {:?} <: {:?})",
1311                kind,
1312                a,
1313                bound);
1314
1315         self.region_vars.verify_generic_bound(origin, kind, a, bound);
1316     }
1317
1318     pub fn type_moves_by_default(&self,
1319                                  param_env: ty::ParamEnv<'tcx>,
1320                                  ty: Ty<'tcx>,
1321                                  span: Span)
1322                                  -> bool {
1323         let ty = self.resolve_type_vars_if_possible(&ty);
1324         // Even if the type may have no inference variables, during
1325         // type-checking closure types are in local tables only.
1326         if !self.in_progress_tables.is_some() || !ty.has_closure_types() {
1327             if let Some((param_env, ty)) = self.tcx.lift_to_global(&(param_env, ty)) {
1328                 return ty.moves_by_default(self.tcx.global_tcx(), param_env, span);
1329             }
1330         }
1331
1332         let copy_def_id = self.tcx.require_lang_item(lang_items::CopyTraitLangItem);
1333
1334         // this can get called from typeck (by euv), and moves_by_default
1335         // rightly refuses to work with inference variables, but
1336         // moves_by_default has a cache, which we want to use in other
1337         // cases.
1338         !traits::type_known_to_meet_bound(self, param_env, ty, copy_def_id, span)
1339     }
1340
1341     pub fn closure_kind(&self,
1342                         def_id: DefId)
1343                         -> Option<ty::ClosureKind>
1344     {
1345         if let Some(tables) = self.in_progress_tables {
1346             if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
1347                 let hir_id = self.tcx.hir.node_to_hir_id(id);
1348                 return tables.borrow()
1349                              .closure_kinds()
1350                              .get(hir_id)
1351                              .cloned()
1352                              .map(|(kind, _)| kind);
1353             }
1354         }
1355
1356         // During typeck, ALL closures are local. But afterwards,
1357         // during trans, we see closure ids from other traits.
1358         // That may require loading the closure data out of the
1359         // cstore.
1360         Some(self.tcx.closure_kind(def_id))
1361     }
1362
1363     /// Obtain the signature of a function or closure.
1364     /// For closures, unlike `tcx.fn_sig(def_id)`, this method will
1365     /// work during the type-checking of the enclosing function and
1366     /// return the closure signature in its partially inferred state.
1367     pub fn fn_sig(&self, def_id: DefId) -> ty::PolyFnSig<'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().closure_tys().get(hir_id) {
1372                     return ty;
1373                 }
1374             }
1375         }
1376
1377         self.tcx.fn_sig(def_id)
1378     }
1379
1380     pub fn generator_sig(&self, def_id: DefId) -> Option<ty::PolyGenSig<'tcx>> {
1381         if let Some(tables) = self.in_progress_tables {
1382             if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
1383                 let hir_id = self.tcx.hir.node_to_hir_id(id);
1384                 if let Some(&ty) = tables.borrow().generator_sigs().get(hir_id) {
1385                     return ty.map(|t| ty::Binder(t));
1386                 }
1387             }
1388         }
1389
1390         self.tcx.generator_sig(def_id)
1391     }
1392 }
1393
1394 impl<'a, 'gcx, 'tcx> TypeTrace<'tcx> {
1395     pub fn span(&self) -> Span {
1396         self.cause.span
1397     }
1398
1399     pub fn types(cause: &ObligationCause<'tcx>,
1400                  a_is_expected: bool,
1401                  a: Ty<'tcx>,
1402                  b: Ty<'tcx>)
1403                  -> TypeTrace<'tcx> {
1404         TypeTrace {
1405             cause: cause.clone(),
1406             values: Types(ExpectedFound::new(a_is_expected, a, b))
1407         }
1408     }
1409
1410     pub fn dummy(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> TypeTrace<'tcx> {
1411         TypeTrace {
1412             cause: ObligationCause::dummy(),
1413             values: Types(ExpectedFound {
1414                 expected: tcx.types.err,
1415                 found: tcx.types.err,
1416             })
1417         }
1418     }
1419 }
1420
1421 impl<'tcx> fmt::Debug for TypeTrace<'tcx> {
1422     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1423         write!(f, "TypeTrace({:?})", self.cause)
1424     }
1425 }
1426
1427 impl<'tcx> SubregionOrigin<'tcx> {
1428     pub fn span(&self) -> Span {
1429         match *self {
1430             Subtype(ref a) => a.span(),
1431             InfStackClosure(a) => a,
1432             InvokeClosure(a) => a,
1433             DerefPointer(a) => a,
1434             FreeVariable(a, _) => a,
1435             IndexSlice(a) => a,
1436             RelateObjectBound(a) => a,
1437             RelateParamBound(a, _) => a,
1438             RelateRegionParamBound(a) => a,
1439             RelateDefaultParamBound(a, _) => a,
1440             Reborrow(a) => a,
1441             ReborrowUpvar(a, _) => a,
1442             DataBorrowed(_, a) => a,
1443             ReferenceOutlivesReferent(_, a) => a,
1444             ParameterInScope(_, a) => a,
1445             ExprTypeIsNotInScope(_, a) => a,
1446             BindingTypeIsNotValidAtDecl(a) => a,
1447             CallRcvr(a) => a,
1448             CallArg(a) => a,
1449             CallReturn(a) => a,
1450             Operand(a) => a,
1451             AddrOf(a) => a,
1452             AutoBorrow(a) => a,
1453             SafeDestructor(a) => a,
1454             CompareImplMethodObligation { span, .. } => span,
1455         }
1456     }
1457
1458     pub fn from_obligation_cause<F>(cause: &traits::ObligationCause<'tcx>,
1459                                     default: F)
1460                                     -> Self
1461         where F: FnOnce() -> Self
1462     {
1463         match cause.code {
1464             traits::ObligationCauseCode::ReferenceOutlivesReferent(ref_type) =>
1465                 SubregionOrigin::ReferenceOutlivesReferent(ref_type, cause.span),
1466
1467             traits::ObligationCauseCode::CompareImplMethodObligation { item_name,
1468                                                                        impl_item_def_id,
1469                                                                        trait_item_def_id,
1470                                                                        lint_id } =>
1471                 SubregionOrigin::CompareImplMethodObligation {
1472                     span: cause.span,
1473                     item_name,
1474                     impl_item_def_id,
1475                     trait_item_def_id,
1476                     lint_id,
1477                 },
1478
1479             _ => default(),
1480         }
1481     }
1482 }
1483
1484 impl RegionVariableOrigin {
1485     pub fn span(&self) -> Span {
1486         match *self {
1487             MiscVariable(a) => a,
1488             PatternRegion(a) => a,
1489             AddrOfRegion(a) => a,
1490             Autoref(a) => a,
1491             Coercion(a) => a,
1492             EarlyBoundRegion(a, ..) => a,
1493             LateBoundRegion(a, ..) => a,
1494             BoundRegionInCoherence(_) => syntax_pos::DUMMY_SP,
1495             UpvarRegion(_, a) => a
1496         }
1497     }
1498 }
1499
1500 impl<'tcx> TypeFoldable<'tcx> for ValuePairs<'tcx> {
1501     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1502         match *self {
1503             ValuePairs::Types(ref ef) => {
1504                 ValuePairs::Types(ef.fold_with(folder))
1505             }
1506             ValuePairs::TraitRefs(ref ef) => {
1507                 ValuePairs::TraitRefs(ef.fold_with(folder))
1508             }
1509             ValuePairs::PolyTraitRefs(ref ef) => {
1510                 ValuePairs::PolyTraitRefs(ef.fold_with(folder))
1511             }
1512         }
1513     }
1514
1515     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1516         match *self {
1517             ValuePairs::Types(ref ef) => ef.visit_with(visitor),
1518             ValuePairs::TraitRefs(ref ef) => ef.visit_with(visitor),
1519             ValuePairs::PolyTraitRefs(ref ef) => ef.visit_with(visitor),
1520         }
1521     }
1522 }
1523
1524 impl<'tcx> TypeFoldable<'tcx> for TypeTrace<'tcx> {
1525     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1526         TypeTrace {
1527             cause: self.cause.fold_with(folder),
1528             values: self.values.fold_with(folder)
1529         }
1530     }
1531
1532     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1533         self.cause.visit_with(visitor) || self.values.visit_with(visitor)
1534     }
1535 }