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