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