src/librustc/middle/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 #![allow(non_camel_case_types)]
  14
  15 pub use self::LateBoundRegionConversionTime::*;
  16 pub use self::RegionVariableOrigin::*;
  17 pub use self::SubregionOrigin::*;
  18 pub use self::TypeOrigin::*;
  19 pub use self::ValuePairs::*;
  20 pub use self::fixup_err::*;
  21 pub use middle::ty::IntVarValue;
  22 pub use self::freshen::TypeFreshener;
  23 pub use self::region_inference::GenericKind;
  24
  25 use middle::free_region::FreeRegionMap;
  26 use middle::subst;
  27 use middle::subst::Substs;
  28 use middle::ty::{TyVid, IntVid, FloatVid, RegionVid, UnconstrainedNumeric};
  29 use middle::ty::{self, Ty};
  30 use middle::ty_fold::{self, TypeFolder, TypeFoldable};
  31 use middle::ty_relate::{Relate, RelateResult, TypeRelation};
  32 use rustc_data_structures::unify::{self, UnificationTable};
  33 use std::cell::{RefCell};
  34 use std::fmt;
  35 use syntax::ast;
  36 use syntax::codemap;
  37 use syntax::codemap::Span;
  38 use util::nodemap::FnvHashMap;
  39
  40 use self::combine::CombineFields;
  41 use self::region_inference::{RegionVarBindings, RegionSnapshot};
  42 use self::error_reporting::ErrorReporting;
  43 use self::unify_key::ToType;
  44
  45 pub mod bivariate;
  46 pub mod combine;
  47 pub mod equate;
  48 pub mod error_reporting;
  49 pub mod glb;
  50 mod higher_ranked;
  51 pub mod lattice;
  52 pub mod lub;
  53 pub mod region_inference;
  54 pub mod resolve;
  55 mod freshen;
  56 pub mod sub;
  57 pub mod type_variable;
  58 pub mod unify_key;
  59
  60 pub type Bound<T> = Option<T>;
  61 pub type UnitResult<'tcx> = RelateResult<'tcx, ()>; // "unify result"
  62 pub type fres<T> = Result<T, fixup_err>; // "fixup result"
  63
  64 pub struct InferCtxt<'a, 'tcx: 'a> {
  65     pub tcx: &'a ty::ctxt<'tcx>,
  66
  67     // We instantiate UnificationTable with bounds<Ty> because the
  68     // types that might instantiate a general type variable have an
  69     // order, represented by its upper and lower bounds.
  70     type_variables: RefCell<type_variable::TypeVariableTable<'tcx>>,
  71
  72     // Map from integral variable to the kind of integer it represents
  73     int_unification_table: RefCell<UnificationTable<ty::IntVid>>,
  74
  75     // Map from floating variable to the kind of float it represents
  76     float_unification_table: RefCell<UnificationTable<ty::FloatVid>>,
  77
  78     // For region variables.
  79     region_vars: RegionVarBindings<'a, 'tcx>,
  80 }
  81
  82 /// A map returned by `skolemize_late_bound_regions()` indicating the skolemized
  83 /// region that each late-bound region was replaced with.
  84 pub type SkolemizationMap = FnvHashMap<ty::BoundRegion,ty::Region>;
  85
  86 /// Why did we require that the two types be related?
  87 ///
  88 /// See `error_reporting.rs` for more details
  89 #[derive(Clone, Copy, Debug)]
  90 pub enum TypeOrigin {
  91     // Not yet categorized in a better way
  92     Misc(Span),
  93
  94     // Checking that method of impl is compatible with trait
  95     MethodCompatCheck(Span),
  96
  97     // Checking that this expression can be assigned where it needs to be
  98     // FIXME(eddyb) #11161 is the original Expr required?
  99     ExprAssignable(Span),
 100
 101     // Relating trait refs when resolving vtables
 102     RelateTraitRefs(Span),
 103
 104     // Relating self types when resolving vtables
 105     RelateSelfType(Span),
 106
 107     // Relating trait type parameters to those found in impl etc
 108     RelateOutputImplTypes(Span),
 109
 110     // Computing common supertype in the arms of a match expression
 111     MatchExpressionArm(Span, Span),
 112
 113     // Computing common supertype in an if expression
 114     IfExpression(Span),
 115
 116     // Computing common supertype of an if expression with no else counter-part
 117     IfExpressionWithNoElse(Span),
 118
 119     // Computing common supertype in a range expression
 120     RangeExpression(Span),
 121
 122     // `where a == b`
 123     EquatePredicate(Span),
 124 }
 125
 126 impl TypeOrigin {
 127     fn as_str(&self) -> &'static str {
 128         match self {
 129             &TypeOrigin::Misc(_) |
 130             &TypeOrigin::RelateSelfType(_) |
 131             &TypeOrigin::RelateOutputImplTypes(_) |
 132             &TypeOrigin::ExprAssignable(_) => "mismatched types",
 133             &TypeOrigin::RelateTraitRefs(_) => "mismatched traits",
 134             &TypeOrigin::MethodCompatCheck(_) => "method not compatible with trait",
 135             &TypeOrigin::MatchExpressionArm(_, _) => "match arms have incompatible types",
 136             &TypeOrigin::IfExpression(_) => "if and else have incompatible types",
 137             &TypeOrigin::IfExpressionWithNoElse(_) => "if may be missing an else clause",
 138             &TypeOrigin::RangeExpression(_) => "start and end of range have incompatible types",
 139             &TypeOrigin::EquatePredicate(_) => "equality predicate not satisfied",
 140         }
 141     }
 142 }
 143
 144 impl fmt::Display for TypeOrigin {
 145     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(),fmt::Error> {
 146         fmt::Display::fmt(self.as_str(), f)
 147     }
 148 }
 149
 150 /// See `error_reporting.rs` for more details
 151 #[derive(Clone, Debug)]
 152 pub enum ValuePairs<'tcx> {
 153     Types(ty::expected_found<Ty<'tcx>>),
 154     TraitRefs(ty::expected_found<ty::TraitRef<'tcx>>),
 155     PolyTraitRefs(ty::expected_found<ty::PolyTraitRef<'tcx>>),
 156 }
 157
 158 /// The trace designates the path through inference that we took to
 159 /// encounter an error or subtyping constraint.
 160 ///
 161 /// See `error_reporting.rs` for more details.
 162 #[derive(Clone)]
 163 pub struct TypeTrace<'tcx> {
 164     origin: TypeOrigin,
 165     values: ValuePairs<'tcx>,
 166 }
 167
 168 /// The origin of a `r1 <= r2` constraint.
 169 ///
 170 /// See `error_reporting.rs` for more details
 171 #[derive(Clone, Debug)]
 172 pub enum SubregionOrigin<'tcx> {
 173     // Arose from a subtyping relation
 174     Subtype(TypeTrace<'tcx>),
 175
 176     // Arose from a subtyping relation
 177     DefaultExistentialBound(TypeTrace<'tcx>),
 178
 179     // Stack-allocated closures cannot outlive innermost loop
 180     // or function so as to ensure we only require finite stack
 181     InfStackClosure(Span),
 182
 183     // Invocation of closure must be within its lifetime
 184     InvokeClosure(Span),
 185
 186     // Dereference of reference must be within its lifetime
 187     DerefPointer(Span),
 188
 189     // Closure bound must not outlive captured free variables
 190     FreeVariable(Span, ast::NodeId),
 191
 192     // Index into slice must be within its lifetime
 193     IndexSlice(Span),
 194
 195     // When casting `&'a T` to an `&'b Trait` object,
 196     // relating `'a` to `'b`
 197     RelateObjectBound(Span),
 198
 199     // Some type parameter was instantiated with the given type,
 200     // and that type must outlive some region.
 201     RelateParamBound(Span, Ty<'tcx>),
 202
 203     // The given region parameter was instantiated with a region
 204     // that must outlive some other region.
 205     RelateRegionParamBound(Span),
 206
 207     // A bound placed on type parameters that states that must outlive
 208     // the moment of their instantiation.
 209     RelateDefaultParamBound(Span, Ty<'tcx>),
 210
 211     // Creating a pointer `b` to contents of another reference
 212     Reborrow(Span),
 213
 214     // Creating a pointer `b` to contents of an upvar
 215     ReborrowUpvar(Span, ty::UpvarId),
 216
 217     // (&'a &'b T) where a >= b
 218     ReferenceOutlivesReferent(Ty<'tcx>, Span),
 219
 220     // The type T of an expression E must outlive the lifetime for E.
 221     ExprTypeIsNotInScope(Ty<'tcx>, Span),
 222
 223     // A `ref b` whose region does not enclose the decl site
 224     BindingTypeIsNotValidAtDecl(Span),
 225
 226     // Regions appearing in a method receiver must outlive method call
 227     CallRcvr(Span),
 228
 229     // Regions appearing in a function argument must outlive func call
 230     CallArg(Span),
 231
 232     // Region in return type of invoked fn must enclose call
 233     CallReturn(Span),
 234
 235     // Operands must be in scope
 236     Operand(Span),
 237
 238     // Region resulting from a `&` expr must enclose the `&` expr
 239     AddrOf(Span),
 240
 241     // An auto-borrow that does not enclose the expr where it occurs
 242     AutoBorrow(Span),
 243
 244     // Region constraint arriving from destructor safety
 245     SafeDestructor(Span),
 246 }
 247
 248 /// Times when we replace late-bound regions with variables:
 249 #[derive(Clone, Copy, Debug)]
 250 pub enum LateBoundRegionConversionTime {
 251     /// when a fn is called
 252     FnCall,
 253
 254     /// when two higher-ranked types are compared
 255     HigherRankedType,
 256
 257     /// when projecting an associated type
 258     AssocTypeProjection(ast::Name),
 259 }
 260
 261 /// Reasons to create a region inference variable
 262 ///
 263 /// See `error_reporting.rs` for more details
 264 #[derive(Clone, Debug)]
 265 pub enum RegionVariableOrigin {
 266     // Region variables created for ill-categorized reasons,
 267     // mostly indicates places in need of refactoring
 268     MiscVariable(Span),
 269
 270     // Regions created by a `&P` or `[...]` pattern
 271     PatternRegion(Span),
 272
 273     // Regions created by `&` operator
 274     AddrOfRegion(Span),
 275
 276     // Regions created as part of an autoref of a method receiver
 277     Autoref(Span),
 278
 279     // Regions created as part of an automatic coercion
 280     Coercion(Span),
 281
 282     // Region variables created as the values for early-bound regions
 283     EarlyBoundRegion(Span, ast::Name),
 284
 285     // Region variables created for bound regions
 286     // in a function or method that is called
 287     LateBoundRegion(Span, ty::BoundRegion, LateBoundRegionConversionTime),
 288
 289     UpvarRegion(ty::UpvarId, Span),
 290
 291     BoundRegionInCoherence(ast::Name),
 292 }
 293
 294 #[derive(Copy, Clone, Debug)]
 295 pub enum fixup_err {
 296     unresolved_int_ty(IntVid),
 297     unresolved_float_ty(FloatVid),
 298     unresolved_ty(TyVid)
 299 }
 300
 301 pub fn fixup_err_to_string(f: fixup_err) -> String {
 302     match f {
 303       unresolved_int_ty(_) => {
 304           "cannot determine the type of this integer; add a suffix to \
 305            specify the type explicitly".to_string()
 306       }
 307       unresolved_float_ty(_) => {
 308           "cannot determine the type of this number; add a suffix to specify \
 309            the type explicitly".to_string()
 310       }
 311       unresolved_ty(_) => "unconstrained type".to_string(),
 312     }
 313 }
 314
 315 pub fn new_infer_ctxt<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>)
 316                                 -> InferCtxt<'a, 'tcx> {
 317     InferCtxt {
 318         tcx: tcx,
 319         type_variables: RefCell::new(type_variable::TypeVariableTable::new()),
 320         int_unification_table: RefCell::new(UnificationTable::new()),
 321         float_unification_table: RefCell::new(UnificationTable::new()),
 322         region_vars: RegionVarBindings::new(tcx),
 323     }
 324 }
 325
 326 /// Computes the least upper-bound of `a` and `b`. If this is not possible, reports an error and
 327 /// returns ty::err.
 328 pub fn common_supertype<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>,
 329                                   origin: TypeOrigin,
 330                                   a_is_expected: bool,
 331                                   a: Ty<'tcx>,
 332                                   b: Ty<'tcx>)
 333                                   -> Ty<'tcx>
 334 {
 335     debug!("common_supertype({:?}, {:?})",
 336            a, b);
 337
 338     let trace = TypeTrace {
 339         origin: origin,
 340         values: Types(expected_found(a_is_expected, a, b))
 341     };
 342
 343     let result = cx.commit_if_ok(|_| cx.lub(a_is_expected, trace.clone()).relate(&a, &b));
 344     match result {
 345         Ok(t) => t,
 346         Err(ref err) => {
 347             cx.report_and_explain_type_error(trace, err);
 348             cx.tcx.types.err
 349         }
 350     }
 351 }
 352
 353 pub fn mk_subty<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>,
 354                           a_is_expected: bool,
 355                           origin: TypeOrigin,
 356                           a: Ty<'tcx>,
 357                           b: Ty<'tcx>)
 358                           -> UnitResult<'tcx>
 359 {
 360     debug!("mk_subty({:?} <: {:?})", a, b);
 361     cx.sub_types(a_is_expected, origin, a, b)
 362 }
 363
 364 pub fn can_mk_subty<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>,
 365                               a: Ty<'tcx>,
 366                               b: Ty<'tcx>)
 367                               -> UnitResult<'tcx> {
 368     debug!("can_mk_subty({:?} <: {:?})", a, b);
 369     cx.probe(|_| {
 370         let trace = TypeTrace {
 371             origin: Misc(codemap::DUMMY_SP),
 372             values: Types(expected_found(true, a, b))
 373         };
 374         cx.sub(true, trace).relate(&a, &b).map(|_| ())
 375     })
 376 }
 377
 378 pub fn can_mk_eqty<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>, a: Ty<'tcx>, b: Ty<'tcx>)
 379                              -> UnitResult<'tcx>
 380 {
 381     cx.can_equate(&a, &b)
 382 }
 383
 384 pub fn mk_subr<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>,
 385                          origin: SubregionOrigin<'tcx>,
 386                          a: ty::Region,
 387                          b: ty::Region) {
 388     debug!("mk_subr({:?} <: {:?})", a, b);
 389     let snapshot = cx.region_vars.start_snapshot();
 390     cx.region_vars.make_subregion(origin, a, b);
 391     cx.region_vars.commit(snapshot);
 392 }
 393
 394 pub fn mk_eqty<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>,
 395                          a_is_expected: bool,
 396                          origin: TypeOrigin,
 397                          a: Ty<'tcx>,
 398                          b: Ty<'tcx>)
 399                          -> UnitResult<'tcx>
 400 {
 401     debug!("mk_eqty({:?} <: {:?})", a, b);
 402     cx.commit_if_ok(|_| cx.eq_types(a_is_expected, origin, a, b))
 403 }
 404
 405 pub fn mk_sub_poly_trait_refs<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>,
 406                                    a_is_expected: bool,
 407                                    origin: TypeOrigin,
 408                                    a: ty::PolyTraitRef<'tcx>,
 409                                    b: ty::PolyTraitRef<'tcx>)
 410                                    -> UnitResult<'tcx>
 411 {
 412     debug!("mk_sub_trait_refs({:?} <: {:?})",
 413            a, b);
 414     cx.commit_if_ok(|_| cx.sub_poly_trait_refs(a_is_expected, origin, a.clone(), b.clone()))
 415 }
 416
 417 fn expected_found<T>(a_is_expected: bool,
 418                      a: T,
 419                      b: T)
 420                      -> ty::expected_found<T>
 421 {
 422     if a_is_expected {
 423         ty::expected_found {expected: a, found: b}
 424     } else {
 425         ty::expected_found {expected: b, found: a}
 426     }
 427 }
 428
 429 #[must_use = "once you start a snapshot, you should always consume it"]
 430 pub struct CombinedSnapshot {
 431     type_snapshot: type_variable::Snapshot,
 432     int_snapshot: unify::Snapshot<ty::IntVid>,
 433     float_snapshot: unify::Snapshot<ty::FloatVid>,
 434     region_vars_snapshot: RegionSnapshot,
 435 }
 436
 437 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
 438     pub fn freshen<T:TypeFoldable<'tcx>>(&self, t: T) -> T {
 439         t.fold_with(&mut self.freshener())
 440     }
 441
 442     pub fn type_var_diverges(&'a self, ty: Ty) -> bool {
 443         match ty.sty {
 444             ty::TyInfer(ty::TyVar(vid)) => self.type_variables.borrow().var_diverges(vid),
 445             _ => false
 446         }
 447     }
 448
 449     pub fn freshener<'b>(&'b self) -> TypeFreshener<'b, 'tcx> {
 450         freshen::TypeFreshener::new(self)
 451     }
 452
 453     pub fn type_is_unconstrained_numeric(&'a self, ty: Ty) -> UnconstrainedNumeric {
 454         use middle::ty::UnconstrainedNumeric::{Neither, UnconstrainedInt, UnconstrainedFloat};
 455         match ty.sty {
 456             ty::TyInfer(ty::IntVar(vid)) => {
 457                 if self.int_unification_table.borrow_mut().has_value(vid) {
 458                     Neither
 459                 } else {
 460                     UnconstrainedInt
 461                 }
 462             },
 463             ty::TyInfer(ty::FloatVar(vid)) => {
 464                 if self.float_unification_table.borrow_mut().has_value(vid) {
 465                     Neither
 466                 } else {
 467                     UnconstrainedFloat
 468                 }
 469             },
 470             _ => Neither,
 471         }
 472     }
 473
 474     fn combine_fields(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
 475                       -> CombineFields<'a, 'tcx> {
 476         CombineFields {infcx: self,
 477                        a_is_expected: a_is_expected,
 478                        trace: trace,
 479                        cause: None}
 480     }
 481
 482     // public so that it can be used from the rustc_driver unit tests
 483     pub fn equate(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
 484               -> equate::Equate<'a, 'tcx>
 485     {
 486         self.combine_fields(a_is_expected, trace).equate()
 487     }
 488
 489     // public so that it can be used from the rustc_driver unit tests
 490     pub fn sub(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
 491                -> sub::Sub<'a, 'tcx>
 492     {
 493         self.combine_fields(a_is_expected, trace).sub()
 494     }
 495
 496     // public so that it can be used from the rustc_driver unit tests
 497     pub fn lub(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
 498                -> lub::Lub<'a, 'tcx>
 499     {
 500         self.combine_fields(a_is_expected, trace).lub()
 501     }
 502
 503     // public so that it can be used from the rustc_driver unit tests
 504     pub fn glb(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
 505                -> glb::Glb<'a, 'tcx>
 506     {
 507         self.combine_fields(a_is_expected, trace).glb()
 508     }
 509
 510     fn start_snapshot(&self) -> CombinedSnapshot {
 511         CombinedSnapshot {
 512             type_snapshot: self.type_variables.borrow_mut().snapshot(),
 513             int_snapshot: self.int_unification_table.borrow_mut().snapshot(),
 514             float_snapshot: self.float_unification_table.borrow_mut().snapshot(),
 515             region_vars_snapshot: self.region_vars.start_snapshot(),
 516         }
 517     }
 518
 519     fn rollback_to(&self, snapshot: CombinedSnapshot) {
 520         debug!("rollback!");
 521         let CombinedSnapshot { type_snapshot,
 522                                int_snapshot,
 523                                float_snapshot,
 524                                region_vars_snapshot } = snapshot;
 525
 526         self.type_variables
 527             .borrow_mut()
 528             .rollback_to(type_snapshot);
 529         self.int_unification_table
 530             .borrow_mut()
 531             .rollback_to(int_snapshot);
 532         self.float_unification_table
 533             .borrow_mut()
 534             .rollback_to(float_snapshot);
 535         self.region_vars
 536             .rollback_to(region_vars_snapshot);
 537     }
 538
 539     fn commit_from(&self, snapshot: CombinedSnapshot) {
 540         debug!("commit_from!");
 541         let CombinedSnapshot { type_snapshot,
 542                                int_snapshot,
 543                                float_snapshot,
 544                                region_vars_snapshot } = snapshot;
 545
 546         self.type_variables
 547             .borrow_mut()
 548             .commit(type_snapshot);
 549         self.int_unification_table
 550             .borrow_mut()
 551             .commit(int_snapshot);
 552         self.float_unification_table
 553             .borrow_mut()
 554             .commit(float_snapshot);
 555         self.region_vars
 556             .commit(region_vars_snapshot);
 557     }
 558
 559     /// Execute `f` and commit the bindings
 560     pub fn commit_unconditionally<R, F>(&self, f: F) -> R where
 561         F: FnOnce() -> R,
 562     {
 563         debug!("commit()");
 564         let snapshot = self.start_snapshot();
 565         let r = f();
 566         self.commit_from(snapshot);
 567         r
 568     }
 569
 570     /// Execute `f` and commit the bindings if closure `f` returns `Ok(_)`
 571     pub fn commit_if_ok<T, E, F>(&self, f: F) -> Result<T, E> where
 572         F: FnOnce(&CombinedSnapshot) -> Result<T, E>
 573     {
 574         debug!("commit_if_ok()");
 575         let snapshot = self.start_snapshot();
 576         let r = f(&snapshot);
 577         debug!("commit_if_ok() -- r.is_ok() = {}", r.is_ok());
 578         match r {
 579             Ok(_) => { self.commit_from(snapshot); }
 580             Err(_) => { self.rollback_to(snapshot); }
 581         }
 582         r
 583     }
 584
 585     /// Execute `f` and commit only the region bindings if successful.
 586     /// The function f must be very careful not to leak any non-region
 587     /// variables that get created.
 588     pub fn commit_regions_if_ok<T, E, F>(&self, f: F) -> Result<T, E> where
 589         F: FnOnce() -> Result<T, E>
 590     {
 591         debug!("commit_regions_if_ok()");
 592         let CombinedSnapshot { type_snapshot,
 593                                int_snapshot,
 594                                float_snapshot,
 595                                region_vars_snapshot } = self.start_snapshot();
 596
 597         let r = self.commit_if_ok(|_| f());
 598
 599         // Roll back any non-region bindings - they should be resolved
 600         // inside `f`, with, e.g. `resolve_type_vars_if_possible`.
 601         self.type_variables
 602             .borrow_mut()
 603             .rollback_to(type_snapshot);
 604         self.int_unification_table
 605             .borrow_mut()
 606             .rollback_to(int_snapshot);
 607         self.float_unification_table
 608             .borrow_mut()
 609             .rollback_to(float_snapshot);
 610
 611         // Commit region vars that may escape through resolved types.
 612         self.region_vars
 613             .commit(region_vars_snapshot);
 614
 615         r
 616     }
 617
 618     /// Execute `f` then unroll any bindings it creates
 619     pub fn probe<R, F>(&self, f: F) -> R where
 620         F: FnOnce(&CombinedSnapshot) -> R,
 621     {
 622         debug!("probe()");
 623         let snapshot = self.start_snapshot();
 624         let r = f(&snapshot);
 625         self.rollback_to(snapshot);
 626         r
 627     }
 628
 629     pub fn add_given(&self,
 630                      sub: ty::FreeRegion,
 631                      sup: ty::RegionVid)
 632     {
 633         self.region_vars.add_given(sub, sup);
 634     }
 635
 636     pub fn sub_types(&self,
 637                      a_is_expected: bool,
 638                      origin: TypeOrigin,
 639                      a: Ty<'tcx>,
 640                      b: Ty<'tcx>)
 641                      -> UnitResult<'tcx>
 642     {
 643         debug!("sub_types({:?} <: {:?})", a, b);
 644         self.commit_if_ok(|_| {
 645             let trace = TypeTrace::types(origin, a_is_expected, a, b);
 646             self.sub(a_is_expected, trace).relate(&a, &b).map(|_| ())
 647         })
 648     }
 649
 650     pub fn eq_types(&self,
 651                     a_is_expected: bool,
 652                     origin: TypeOrigin,
 653                     a: Ty<'tcx>,
 654                     b: Ty<'tcx>)
 655                     -> UnitResult<'tcx>
 656     {
 657         self.commit_if_ok(|_| {
 658             let trace = TypeTrace::types(origin, a_is_expected, a, b);
 659             self.equate(a_is_expected, trace).relate(&a, &b).map(|_| ())
 660         })
 661     }
 662
 663     pub fn sub_trait_refs(&self,
 664                           a_is_expected: bool,
 665                           origin: TypeOrigin,
 666                           a: ty::TraitRef<'tcx>,
 667                           b: ty::TraitRef<'tcx>)
 668                           -> UnitResult<'tcx>
 669     {
 670         debug!("sub_trait_refs({:?} <: {:?})",
 671                a,
 672                b);
 673         self.commit_if_ok(|_| {
 674             let trace = TypeTrace {
 675                 origin: origin,
 676                 values: TraitRefs(expected_found(a_is_expected, a.clone(), b.clone()))
 677             };
 678             self.sub(a_is_expected, trace).relate(&a, &b).map(|_| ())
 679         })
 680     }
 681
 682     pub fn sub_poly_trait_refs(&self,
 683                                a_is_expected: bool,
 684                                origin: TypeOrigin,
 685                                a: ty::PolyTraitRef<'tcx>,
 686                                b: ty::PolyTraitRef<'tcx>)
 687                                -> UnitResult<'tcx>
 688     {
 689         debug!("sub_poly_trait_refs({:?} <: {:?})",
 690                a,
 691                b);
 692         self.commit_if_ok(|_| {
 693             let trace = TypeTrace {
 694                 origin: origin,
 695                 values: PolyTraitRefs(expected_found(a_is_expected, a.clone(), b.clone()))
 696             };
 697             self.sub(a_is_expected, trace).relate(&a, &b).map(|_| ())
 698         })
 699     }
 700
 701     pub fn construct_skolemized_subst(&self,
 702                                       generics: &ty::Generics<'tcx>,
 703                                       snapshot: &CombinedSnapshot)
 704                                       -> (subst::Substs<'tcx>, SkolemizationMap) {
 705         /*! See `higher_ranked::construct_skolemized_subst` */
 706
 707         higher_ranked::construct_skolemized_substs(self, generics, snapshot)
 708     }
 709
 710     pub fn skolemize_late_bound_regions<T>(&self,
 711                                            value: &ty::Binder<T>,
 712                                            snapshot: &CombinedSnapshot)
 713                                            -> (T, SkolemizationMap)
 714         where T : TypeFoldable<'tcx>
 715     {
 716         /*! See `higher_ranked::skolemize_late_bound_regions` */
 717
 718         higher_ranked::skolemize_late_bound_regions(self, value, snapshot)
 719     }
 720
 721     pub fn leak_check(&self,
 722                       skol_map: &SkolemizationMap,
 723                       snapshot: &CombinedSnapshot)
 724                       -> UnitResult<'tcx>
 725     {
 726         /*! See `higher_ranked::leak_check` */
 727
 728         match higher_ranked::leak_check(self, skol_map, snapshot) {
 729             Ok(()) => Ok(()),
 730             Err((br, r)) => Err(ty::terr_regions_insufficiently_polymorphic(br, r))
 731         }
 732     }
 733
 734     pub fn plug_leaks<T>(&self,
 735                          skol_map: SkolemizationMap,
 736                          snapshot: &CombinedSnapshot,
 737                          value: &T)
 738                          -> T
 739         where T : TypeFoldable<'tcx>
 740     {
 741         /*! See `higher_ranked::plug_leaks` */
 742
 743         higher_ranked::plug_leaks(self, skol_map, snapshot, value)
 744     }
 745
 746     pub fn equality_predicate(&self,
 747                               span: Span,
 748                               predicate: &ty::PolyEquatePredicate<'tcx>)
 749                               -> UnitResult<'tcx> {
 750         self.commit_if_ok(|snapshot| {
 751             let (ty::EquatePredicate(a, b), skol_map) =
 752                 self.skolemize_late_bound_regions(predicate, snapshot);
 753             let origin = EquatePredicate(span);
 754             let () = try!(mk_eqty(self, false, origin, a, b));
 755             self.leak_check(&skol_map, snapshot)
 756         })
 757     }
 758
 759     pub fn region_outlives_predicate(&self,
 760                                      span: Span,
 761                                      predicate: &ty::PolyRegionOutlivesPredicate)
 762                                      -> UnitResult<'tcx> {
 763         self.commit_if_ok(|snapshot| {
 764             let (ty::OutlivesPredicate(r_a, r_b), skol_map) =
 765                 self.skolemize_late_bound_regions(predicate, snapshot);
 766             let origin = RelateRegionParamBound(span);
 767             let () = mk_subr(self, origin, r_b, r_a); // `b : a` ==> `a <= b`
 768             self.leak_check(&skol_map, snapshot)
 769         })
 770     }
 771
 772     pub fn next_ty_var_id(&self, diverging: bool) -> TyVid {
 773         self.type_variables
 774             .borrow_mut()
 775             .new_var(diverging)
 776     }
 777
 778     pub fn next_ty_var(&self) -> Ty<'tcx> {
 779         ty::mk_var(self.tcx, self.next_ty_var_id(false))
 780     }
 781
 782     pub fn next_diverging_ty_var(&self) -> Ty<'tcx> {
 783         ty::mk_var(self.tcx, self.next_ty_var_id(true))
 784     }
 785
 786     pub fn next_ty_vars(&self, n: usize) -> Vec<Ty<'tcx>> {
 787         (0..n).map(|_i| self.next_ty_var()).collect()
 788     }
 789
 790     pub fn next_int_var_id(&self) -> IntVid {
 791         self.int_unification_table
 792             .borrow_mut()
 793             .new_key(None)
 794     }
 795
 796     pub fn next_float_var_id(&self) -> FloatVid {
 797         self.float_unification_table
 798             .borrow_mut()
 799             .new_key(None)
 800     }
 801
 802     pub fn next_region_var(&self, origin: RegionVariableOrigin) -> ty::Region {
 803         ty::ReInfer(ty::ReVar(self.region_vars.new_region_var(origin)))
 804     }
 805
 806     pub fn region_vars_for_defs(&self,
 807                                 span: Span,
 808                                 defs: &[ty::RegionParameterDef])
 809                                 -> Vec<ty::Region> {
 810         defs.iter()
 811             .map(|d| self.next_region_var(EarlyBoundRegion(span, d.name)))
 812             .collect()
 813     }
 814
 815     /// Given a set of generics defined on a type or impl, returns a substitution mapping each
 816     /// type/region parameter to a fresh inference variable.
 817     pub fn fresh_substs_for_generics(&self,
 818                                      span: Span,
 819                                      generics: &ty::Generics<'tcx>)
 820                                      -> subst::Substs<'tcx>
 821     {
 822         let type_params =
 823             generics.types.map(
 824                 |_| self.next_ty_var());
 825         let region_params =
 826             generics.regions.map(
 827                 |d| self.next_region_var(EarlyBoundRegion(span, d.name)));
 828         subst::Substs::new(type_params, region_params)
 829     }
 830
 831     /// Given a set of generics defined on a trait, returns a substitution mapping each output
 832     /// type/region parameter to a fresh inference variable, and mapping the self type to
 833     /// `self_ty`.
 834     pub fn fresh_substs_for_trait(&self,
 835                                   span: Span,
 836                                   generics: &ty::Generics<'tcx>,
 837                                   self_ty: Ty<'tcx>)
 838                                   -> subst::Substs<'tcx>
 839     {
 840
 841         assert!(generics.types.len(subst::SelfSpace) == 1);
 842         assert!(generics.types.len(subst::FnSpace) == 0);
 843         assert!(generics.regions.len(subst::SelfSpace) == 0);
 844         assert!(generics.regions.len(subst::FnSpace) == 0);
 845
 846         let type_parameter_count = generics.types.len(subst::TypeSpace);
 847         let type_parameters = self.next_ty_vars(type_parameter_count);
 848
 849         let region_param_defs = generics.regions.get_slice(subst::TypeSpace);
 850         let regions = self.region_vars_for_defs(span, region_param_defs);
 851
 852         subst::Substs::new_trait(type_parameters, regions, self_ty)
 853     }
 854
 855     pub fn fresh_bound_region(&self, debruijn: ty::DebruijnIndex) -> ty::Region {
 856         self.region_vars.new_bound(debruijn)
 857     }
 858
 859     pub fn resolve_regions_and_report_errors(&self,
 860                                              free_regions: &FreeRegionMap,
 861                                              subject_node_id: ast::NodeId) {
 862         let errors = self.region_vars.resolve_regions(free_regions, subject_node_id);
 863         self.report_region_errors(&errors); // see error_reporting.rs
 864     }
 865
 866     pub fn ty_to_string(&self, t: Ty<'tcx>) -> String {
 867         self.resolve_type_vars_if_possible(&t).to_string()
 868     }
 869
 870     pub fn tys_to_string(&self, ts: &[Ty<'tcx>]) -> String {
 871         let tstrs: Vec<String> = ts.iter().map(|t| self.ty_to_string(*t)).collect();
 872         format!("({})", tstrs.connect(", "))
 873     }
 874
 875     pub fn trait_ref_to_string(&self, t: &ty::TraitRef<'tcx>) -> String {
 876         self.resolve_type_vars_if_possible(t).to_string()
 877     }
 878
 879     pub fn shallow_resolve(&self, typ: Ty<'tcx>) -> Ty<'tcx> {
 880         match typ.sty {
 881             ty::TyInfer(ty::TyVar(v)) => {
 882                 // Not entirely obvious: if `typ` is a type variable,
 883                 // it can be resolved to an int/float variable, which
 884                 // can then be recursively resolved, hence the
 885                 // recursion. Note though that we prevent type
 886                 // variables from unifying to other type variables
 887                 // directly (though they may be embedded
 888                 // structurally), and we prevent cycles in any case,
 889                 // so this recursion should always be of very limited
 890                 // depth.
 891                 self.type_variables.borrow()
 892                     .probe(v)
 893                     .map(|t| self.shallow_resolve(t))
 894                     .unwrap_or(typ)
 895             }
 896
 897             ty::TyInfer(ty::IntVar(v)) => {
 898                 self.int_unification_table
 899                     .borrow_mut()
 900                     .probe(v)
 901                     .map(|v| v.to_type(self.tcx))
 902                     .unwrap_or(typ)
 903             }
 904
 905             ty::TyInfer(ty::FloatVar(v)) => {
 906                 self.float_unification_table
 907                     .borrow_mut()
 908                     .probe(v)
 909                     .map(|v| v.to_type(self.tcx))
 910                     .unwrap_or(typ)
 911             }
 912
 913             _ => {
 914                 typ
 915             }
 916         }
 917     }
 918
 919     pub fn resolve_type_vars_if_possible<T:TypeFoldable<'tcx>>(&self, value: &T) -> T {
 920         /*!
 921          * Where possible, replaces type/int/float variables in
 922          * `value` with their final value. Note that region variables
 923          * are unaffected. If a type variable has not been unified, it
 924          * is left as is.  This is an idempotent operation that does
 925          * not affect inference state in any way and so you can do it
 926          * at will.
 927          */
 928
 929         let mut r = resolve::OpportunisticTypeResolver::new(self);
 930         value.fold_with(&mut r)
 931     }
 932
 933     pub fn fully_resolve<T:TypeFoldable<'tcx>>(&self, value: &T) -> fres<T> {
 934         /*!
 935          * Attempts to resolve all type/region variables in
 936          * `value`. Region inference must have been run already (e.g.,
 937          * by calling `resolve_regions_and_report_errors`).  If some
 938          * variable was never unified, an `Err` results.
 939          *
 940          * This method is idempotent, but it not typically not invoked
 941          * except during the writeback phase.
 942          */
 943
 944         resolve::fully_resolve(self, value)
 945     }
 946
 947     // [Note-Type-error-reporting]
 948     // An invariant is that anytime the expected or actual type is TyError (the special
 949     // error type, meaning that an error occurred when typechecking this expression),
 950     // this is a derived error. The error cascaded from another error (that was already
 951     // reported), so it's not useful to display it to the user.
 952     // The following four methods -- type_error_message_str, type_error_message_str_with_expected,
 953     // type_error_message, and report_mismatched_types -- implement this logic.
 954     // They check if either the actual or expected type is TyError, and don't print the error
 955     // in this case. The typechecker should only ever report type errors involving mismatched
 956     // types using one of these four methods, and should not call span_err directly for such
 957     // errors.
 958     pub fn type_error_message_str<M>(&self,
 959                                      sp: Span,
 960                                      mk_msg: M,
 961                                      actual_ty: String,
 962                                      err: Option<&ty::type_err<'tcx>>) where
 963         M: FnOnce(Option<String>, String) -> String,
 964     {
 965         self.type_error_message_str_with_expected(sp, mk_msg, None, actual_ty, err)
 966     }
 967
 968     pub fn type_error_message_str_with_expected<M>(&self,
 969                                                    sp: Span,
 970                                                    mk_msg: M,
 971                                                    expected_ty: Option<Ty<'tcx>>,
 972                                                    actual_ty: String,
 973                                                    err: Option<&ty::type_err<'tcx>>) where
 974         M: FnOnce(Option<String>, String) -> String,
 975     {
 976         debug!("hi! expected_ty = {:?}, actual_ty = {}", expected_ty, actual_ty);
 977
 978         let resolved_expected = expected_ty.map(|e_ty| self.resolve_type_vars_if_possible(&e_ty));
 979
 980         match resolved_expected {
 981             Some(t) if ty::type_is_error(t) => (),
 982             _ => {
 983                 let error_str = err.map_or("".to_string(), |t_err| {
 984                     format!(" ({})", t_err)
 985                 });
 986
 987                 self.tcx.sess.span_err(sp, &format!("{}{}",
 988                     mk_msg(resolved_expected.map(|t| self.ty_to_string(t)), actual_ty),
 989                     error_str));
 990
 991                 if let Some(err) = err {
 992                     ty::note_and_explain_type_err(self.tcx, err, sp)
 993                 }
 994             }
 995         }
 996     }
 997
 998     pub fn type_error_message<M>(&self,
 999                                  sp: Span,
1000                                  mk_msg: M,
1001                                  actual_ty: Ty<'tcx>,
1002                                  err: Option<&ty::type_err<'tcx>>) where
1003         M: FnOnce(String) -> String,
1004     {
1005         let actual_ty = self.resolve_type_vars_if_possible(&actual_ty);
1006
1007         // Don't report an error if actual type is TyError.
1008         if ty::type_is_error(actual_ty) {
1009             return;
1010         }
1011
1012         self.type_error_message_str(sp,
1013             move |_e, a| { mk_msg(a) },
1014             self.ty_to_string(actual_ty), err);
1015     }
1016
1017     pub fn report_mismatched_types(&self,
1018                                    span: Span,
1019                                    expected: Ty<'tcx>,
1020                                    actual: Ty<'tcx>,
1021                                    err: &ty::type_err<'tcx>) {
1022         let trace = TypeTrace {
1023             origin: Misc(span),
1024             values: Types(ty::expected_found {
1025                 expected: expected,
1026                 found: actual
1027             })
1028         };
1029         self.report_and_explain_type_error(trace, err);
1030     }
1031
1032     pub fn replace_late_bound_regions_with_fresh_var<T>(
1033         &self,
1034         span: Span,
1035         lbrct: LateBoundRegionConversionTime,
1036         value: &ty::Binder<T>)
1037         -> (T, FnvHashMap<ty::BoundRegion,ty::Region>)
1038         where T : TypeFoldable<'tcx>
1039     {
1040         ty_fold::replace_late_bound_regions(
1041             self.tcx,
1042             value,
1043             |br| self.next_region_var(LateBoundRegion(span, br, lbrct)))
1044     }
1045
1046     /// See `verify_generic_bound` method in `region_inference`
1047     pub fn verify_generic_bound(&self,
1048                                 origin: SubregionOrigin<'tcx>,
1049                                 kind: GenericKind<'tcx>,
1050                                 a: ty::Region,
1051                                 bs: Vec<ty::Region>) {
1052         debug!("verify_generic_bound({:?}, {:?} <: {:?})",
1053                kind,
1054                a,
1055                bs);
1056
1057         self.region_vars.verify_generic_bound(origin, kind, a, bs);
1058     }
1059
1060     pub fn can_equate<'b,T>(&'b self, a: &T, b: &T) -> UnitResult<'tcx>
1061         where T: Relate<'b,'tcx> + fmt::Debug
1062     {
1063         debug!("can_equate({:?}, {:?})", a, b);
1064         self.probe(|_| {
1065             // Gin up a dummy trace, since this won't be committed
1066             // anyhow. We should make this typetrace stuff more
1067             // generic so we don't have to do anything quite this
1068             // terrible.
1069             let e = self.tcx.types.err;
1070             let trace = TypeTrace { origin: Misc(codemap::DUMMY_SP),
1071                                     values: Types(expected_found(true, e, e)) };
1072             self.equate(true, trace).relate(a, b)
1073         }).map(|_| ())
1074     }
1075 }
1076
1077 impl<'tcx> TypeTrace<'tcx> {
1078     pub fn span(&self) -> Span {
1079         self.origin.span()
1080     }
1081
1082     pub fn types(origin: TypeOrigin,
1083                  a_is_expected: bool,
1084                  a: Ty<'tcx>,
1085                  b: Ty<'tcx>)
1086                  -> TypeTrace<'tcx> {
1087         TypeTrace {
1088             origin: origin,
1089             values: Types(expected_found(a_is_expected, a, b))
1090         }
1091     }
1092
1093     pub fn dummy(tcx: &ty::ctxt<'tcx>) -> TypeTrace<'tcx> {
1094         TypeTrace {
1095             origin: Misc(codemap::DUMMY_SP),
1096             values: Types(ty::expected_found {
1097                 expected: tcx.types.err,
1098                 found: tcx.types.err,
1099             })
1100         }
1101     }
1102 }
1103
1104 impl<'tcx> fmt::Debug for TypeTrace<'tcx> {
1105     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1106         write!(f, "TypeTrace({:?})", self.origin)
1107     }
1108 }
1109
1110 impl TypeOrigin {
1111     pub fn span(&self) -> Span {
1112         match *self {
1113             MethodCompatCheck(span) => span,
1114             ExprAssignable(span) => span,
1115             Misc(span) => span,
1116             RelateTraitRefs(span) => span,
1117             RelateSelfType(span) => span,
1118             RelateOutputImplTypes(span) => span,
1119             MatchExpressionArm(match_span, _) => match_span,
1120             IfExpression(span) => span,
1121             IfExpressionWithNoElse(span) => span,
1122             RangeExpression(span) => span,
1123             EquatePredicate(span) => span,
1124         }
1125     }
1126 }
1127
1128 impl<'tcx> SubregionOrigin<'tcx> {
1129     pub fn span(&self) -> Span {
1130         match *self {
1131             Subtype(ref a) => a.span(),
1132             DefaultExistentialBound(ref a) => a.span(),
1133             InfStackClosure(a) => a,
1134             InvokeClosure(a) => a,
1135             DerefPointer(a) => a,
1136             FreeVariable(a, _) => a,
1137             IndexSlice(a) => a,
1138             RelateObjectBound(a) => a,
1139             RelateParamBound(a, _) => a,
1140             RelateRegionParamBound(a) => a,
1141             RelateDefaultParamBound(a, _) => a,
1142             Reborrow(a) => a,
1143             ReborrowUpvar(a, _) => a,
1144             ReferenceOutlivesReferent(_, a) => a,
1145             ExprTypeIsNotInScope(_, a) => a,
1146             BindingTypeIsNotValidAtDecl(a) => a,
1147             CallRcvr(a) => a,
1148             CallArg(a) => a,
1149             CallReturn(a) => a,
1150             Operand(a) => a,
1151             AddrOf(a) => a,
1152             AutoBorrow(a) => a,
1153             SafeDestructor(a) => a,
1154         }
1155     }
1156 }
1157
1158 impl RegionVariableOrigin {
1159     pub fn span(&self) -> Span {
1160         match *self {
1161             MiscVariable(a) => a,
1162             PatternRegion(a) => a,
1163             AddrOfRegion(a) => a,
1164             Autoref(a) => a,
1165             Coercion(a) => a,
1166             EarlyBoundRegion(a, _) => a,
1167             LateBoundRegion(a, _, _) => a,
1168             BoundRegionInCoherence(_) => codemap::DUMMY_SP,
1169             UpvarRegion(_, a) => a
1170         }
1171     }
1172 }