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