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