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