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