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