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