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