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