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 collections::HashMap;
  25 use collections::SmallIntMap;
  26 use middle::ty::{TyVid, IntVid, FloatVid, RegionVid, Vid};
  27 use middle::ty;
  28 use middle::ty_fold;
  29 use middle::ty_fold::TypeFolder;
  30 use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
  31 use middle::typeck::infer::coercion::Coerce;
  32 use middle::typeck::infer::combine::{Combine, CombineFields, eq_tys};
  33 use middle::typeck::infer::region_inference::{RegionVarBindings};
  34 use middle::typeck::infer::resolve::{resolver};
  35 use middle::typeck::infer::sub::Sub;
  36 use middle::typeck::infer::lub::Lub;
  37 use middle::typeck::infer::to_str::InferStr;
  38 use middle::typeck::infer::unify::{ValsAndBindings, Root};
  39 use middle::typeck::infer::error_reporting::ErrorReporting;
  40 use std::cell::{Cell, RefCell};
  41 use std::rc::Rc;
  42 use syntax::ast;
  43 use syntax::codemap;
  44 use syntax::codemap::Span;
  45 use syntax::owned_slice::OwnedSlice;
  46 use util::common::indent;
  47 use util::ppaux::{bound_region_to_str, ty_to_str, trait_ref_to_str, Repr};
  48
  49 pub mod doc;
  50 pub mod macros;
  51 pub mod combine;
  52 pub mod glb;
  53 pub mod lattice;
  54 pub mod lub;
  55 pub mod region_inference;
  56 pub mod resolve;
  57 pub mod sub;
  58 pub mod to_str;
  59 pub mod unify;
  60 pub mod coercion;
  61 pub mod error_reporting;
  62
  63 pub type Bound<T> = Option<T>;
  64
  65 #[deriving(Clone)]
  66 pub struct Bounds<T> {
  67     lb: Bound<T>,
  68     ub: Bound<T>
  69 }
  70
  71 pub type cres<T> = Result<T,ty::type_err>; // "combine result"
  72 pub type ures = cres<()>; // "unify result"
  73 pub type fres<T> = Result<T, fixup_err>; // "fixup result"
  74 pub type CoerceResult = cres<Option<ty::AutoAdjustment>>;
  75
  76 pub struct InferCtxt<'a> {
  77     pub tcx: &'a ty::ctxt,
  78
  79     // We instantiate ValsAndBindings with bounds<ty::t> because the
  80     // types that might instantiate a general type variable have an
  81     // order, represented by its upper and lower bounds.
  82     pub ty_var_bindings: RefCell<ValsAndBindings<ty::TyVid, Bounds<ty::t>>>,
  83     pub ty_var_counter: Cell<uint>,
  84
  85     // Map from integral variable to the kind of integer it represents
  86     pub int_var_bindings: RefCell<ValsAndBindings<ty::IntVid,
  87                                               Option<IntVarValue>>>,
  88     pub int_var_counter: Cell<uint>,
  89
  90     // Map from floating variable to the kind of float it represents
  91     pub float_var_bindings: RefCell<ValsAndBindings<ty::FloatVid,
  92                                                 Option<ast::FloatTy>>>,
  93     pub float_var_counter: Cell<uint>,
  94
  95     // For region variables.
  96     pub region_vars: RegionVarBindings<'a>,
  97 }
  98
  99 /// Why did we require that the two types be related?
 100 ///
 101 /// See `error_reporting.rs` for more details
 102 #[deriving(Clone)]
 103 pub enum TypeOrigin {
 104     // Not yet categorized in a better way
 105     Misc(Span),
 106
 107     // Checking that method of impl is compatible with trait
 108     MethodCompatCheck(Span),
 109
 110     // Checking that this expression can be assigned where it needs to be
 111     // FIXME(eddyb) #11161 is the original Expr required?
 112     ExprAssignable(Span),
 113
 114     // Relating trait refs when resolving vtables
 115     RelateTraitRefs(Span),
 116
 117     // Relating trait refs when resolving vtables
 118     RelateSelfType(Span),
 119
 120     // Computing common supertype in a match expression
 121     MatchExpression(Span),
 122
 123     // Computing common supertype in an if expression
 124     IfExpression(Span),
 125 }
 126
 127 /// See `error_reporting.rs` for more details
 128 #[deriving(Clone)]
 129 pub enum ValuePairs {
 130     Types(ty::expected_found<ty::t>),
 131     TraitRefs(ty::expected_found<Rc<ty::TraitRef>>),
 132 }
 133
 134 /// The trace designates the path through inference that we took to
 135 /// encounter an error or subtyping constraint.
 136 ///
 137 /// See `error_reporting.rs` for more details.
 138 #[deriving(Clone)]
 139 pub struct TypeTrace {
 140     origin: TypeOrigin,
 141     values: ValuePairs,
 142 }
 143
 144 /// The origin of a `r1 <= r2` constraint.
 145 ///
 146 /// See `error_reporting.rs` for more details
 147 #[deriving(Clone)]
 148 pub enum SubregionOrigin {
 149     // Arose from a subtyping relation
 150     Subtype(TypeTrace),
 151
 152     // Stack-allocated closures cannot outlive innermost loop
 153     // or function so as to ensure we only require finite stack
 154     InfStackClosure(Span),
 155
 156     // Invocation of closure must be within its lifetime
 157     InvokeClosure(Span),
 158
 159     // Dereference of reference must be within its lifetime
 160     DerefPointer(Span),
 161
 162     // Closure bound must not outlive captured free variables
 163     FreeVariable(Span, ast::NodeId),
 164
 165     // Index into slice must be within its lifetime
 166     IndexSlice(Span),
 167
 168     // When casting `&'a T` to an `&'b Trait` object,
 169     // relating `'a` to `'b`
 170     RelateObjectBound(Span),
 171
 172     // Creating a pointer `b` to contents of another reference
 173     Reborrow(Span),
 174
 175     // Creating a pointer `b` to contents of an upvar
 176     ReborrowUpvar(Span, ty::UpvarId),
 177
 178     // (&'a &'b T) where a >= b
 179     ReferenceOutlivesReferent(ty::t, Span),
 180
 181     // A `ref b` whose region does not enclose the decl site
 182     BindingTypeIsNotValidAtDecl(Span),
 183
 184     // Regions appearing in a method receiver must outlive method call
 185     CallRcvr(Span),
 186
 187     // Regions appearing in a function argument must outlive func call
 188     CallArg(Span),
 189
 190     // Region in return type of invoked fn must enclose call
 191     CallReturn(Span),
 192
 193     // Region resulting from a `&` expr must enclose the `&` expr
 194     AddrOf(Span),
 195
 196     // An auto-borrow that does not enclose the expr where it occurs
 197     AutoBorrow(Span),
 198 }
 199
 200 /// Reasons to create a region inference variable
 201 ///
 202 /// See `error_reporting.rs` for more details
 203 #[deriving(Clone)]
 204 pub enum RegionVariableOrigin {
 205     // Region variables created for ill-categorized reasons,
 206     // mostly indicates places in need of refactoring
 207     MiscVariable(Span),
 208
 209     // Regions created by a `&P` or `[...]` pattern
 210     PatternRegion(Span),
 211
 212     // Regions created by `&` operator
 213     AddrOfRegion(Span),
 214
 215     // Regions created by `&[...]` literal
 216     AddrOfSlice(Span),
 217
 218     // Regions created as part of an autoref of a method receiver
 219     Autoref(Span),
 220
 221     // Regions created as part of an automatic coercion
 222     Coercion(TypeTrace),
 223
 224     // Region variables created as the values for early-bound regions
 225     EarlyBoundRegion(Span, ast::Name),
 226
 227     // Region variables created for bound regions
 228     // in a function or method that is called
 229     LateBoundRegion(Span, ty::BoundRegion),
 230
 231     // Region variables created for bound regions
 232     // when doing subtyping/lub/glb computations
 233     BoundRegionInFnType(Span, ty::BoundRegion),
 234
 235     UpvarRegion(ty::UpvarId, Span),
 236
 237     BoundRegionInCoherence(ast::Name),
 238 }
 239
 240 pub enum fixup_err {
 241     unresolved_int_ty(IntVid),
 242     unresolved_ty(TyVid),
 243     cyclic_ty(TyVid),
 244     unresolved_region(RegionVid),
 245     region_var_bound_by_region_var(RegionVid, RegionVid)
 246 }
 247
 248 pub fn fixup_err_to_str(f: fixup_err) -> String {
 249     match f {
 250       unresolved_int_ty(_) => "unconstrained integral type".to_string(),
 251       unresolved_ty(_) => "unconstrained type".to_string(),
 252       cyclic_ty(_) => "cyclic type of infinite size".to_string(),
 253       unresolved_region(_) => "unconstrained region".to_string(),
 254       region_var_bound_by_region_var(r1, r2) => {
 255         format_strbuf!("region var {:?} bound by another region var {:?}; \
 256                         this is a bug in rustc",
 257                        r1,
 258                        r2)
 259       }
 260     }
 261 }
 262
 263 fn new_ValsAndBindings<V:Clone,T:Clone>() -> ValsAndBindings<V, T> {
 264     ValsAndBindings {
 265         vals: SmallIntMap::new(),
 266         bindings: Vec::new()
 267     }
 268 }
 269
 270 pub fn new_infer_ctxt<'a>(tcx: &'a ty::ctxt) -> InferCtxt<'a> {
 271     InferCtxt {
 272         tcx: tcx,
 273
 274         ty_var_bindings: RefCell::new(new_ValsAndBindings()),
 275         ty_var_counter: Cell::new(0),
 276
 277         int_var_bindings: RefCell::new(new_ValsAndBindings()),
 278         int_var_counter: Cell::new(0),
 279
 280         float_var_bindings: RefCell::new(new_ValsAndBindings()),
 281         float_var_counter: Cell::new(0),
 282
 283         region_vars: RegionVarBindings(tcx),
 284     }
 285 }
 286
 287 pub fn common_supertype(cx: &InferCtxt,
 288                         origin: TypeOrigin,
 289                         a_is_expected: bool,
 290                         a: ty::t,
 291                         b: ty::t)
 292                         -> ty::t {
 293     /*!
 294      * Computes the least upper-bound of `a` and `b`. If this is
 295      * not possible, reports an error and returns ty::err.
 296      */
 297
 298     debug!("common_supertype({}, {})", a.inf_str(cx), b.inf_str(cx));
 299
 300     let trace = TypeTrace {
 301         origin: origin,
 302         values: Types(expected_found(a_is_expected, a, b))
 303     };
 304
 305     let result = cx.commit(|| cx.lub(a_is_expected, trace.clone()).tys(a, b));
 306     match result {
 307         Ok(t) => t,
 308         Err(ref err) => {
 309             cx.report_and_explain_type_error(trace, err);
 310             ty::mk_err()
 311         }
 312     }
 313 }
 314
 315 pub fn mk_subty(cx: &InferCtxt,
 316                 a_is_expected: bool,
 317                 origin: TypeOrigin,
 318                 a: ty::t,
 319                 b: ty::t)
 320              -> ures {
 321     debug!("mk_subty({} <: {})", a.inf_str(cx), b.inf_str(cx));
 322     indent(|| {
 323         cx.commit(|| {
 324             let trace = TypeTrace {
 325                 origin: origin,
 326                 values: Types(expected_found(a_is_expected, a, b))
 327             };
 328             cx.sub(a_is_expected, trace).tys(a, b)
 329         })
 330     }).to_ures()
 331 }
 332
 333 pub fn can_mk_subty(cx: &InferCtxt, a: ty::t, b: ty::t) -> ures {
 334     debug!("can_mk_subty({} <: {})", a.inf_str(cx), b.inf_str(cx));
 335     indent(|| {
 336         cx.probe(|| {
 337             let trace = TypeTrace {
 338                 origin: Misc(codemap::DUMMY_SP),
 339                 values: Types(expected_found(true, a, b))
 340             };
 341             cx.sub(true, trace).tys(a, b)
 342         })
 343     }).to_ures()
 344 }
 345
 346 pub fn mk_subr(cx: &InferCtxt,
 347                _a_is_expected: bool,
 348                origin: SubregionOrigin,
 349                a: ty::Region,
 350                b: ty::Region) {
 351     debug!("mk_subr({} <: {})", a.inf_str(cx), b.inf_str(cx));
 352     cx.region_vars.start_snapshot();
 353     cx.region_vars.make_subregion(origin, a, b);
 354     cx.region_vars.commit();
 355 }
 356
 357 pub fn mk_eqty(cx: &InferCtxt,
 358                a_is_expected: bool,
 359                origin: TypeOrigin,
 360                a: ty::t,
 361                b: ty::t)
 362             -> ures {
 363     debug!("mk_eqty({} <: {})", a.inf_str(cx), b.inf_str(cx));
 364     indent(|| {
 365         cx.commit(|| {
 366             let trace = TypeTrace {
 367                 origin: origin,
 368                 values: Types(expected_found(a_is_expected, a, b))
 369             };
 370             let suber = cx.sub(a_is_expected, trace);
 371             eq_tys(&suber, a, b)
 372         })
 373     }).to_ures()
 374 }
 375
 376 pub fn mk_sub_trait_refs(cx: &InferCtxt,
 377                          a_is_expected: bool,
 378                          origin: TypeOrigin,
 379                          a: Rc<ty::TraitRef>,
 380                          b: Rc<ty::TraitRef>)
 381     -> ures
 382 {
 383     debug!("mk_sub_trait_refs({} <: {})",
 384            a.inf_str(cx), b.inf_str(cx));
 385     indent(|| {
 386         cx.commit(|| {
 387             let trace = TypeTrace {
 388                 origin: origin,
 389                 values: TraitRefs(expected_found(a_is_expected, a.clone(), b.clone()))
 390             };
 391             let suber = cx.sub(a_is_expected, trace);
 392             suber.trait_refs(&*a, &*b)
 393         })
 394     }).to_ures()
 395 }
 396
 397 fn expected_found<T>(a_is_expected: bool,
 398                      a: T,
 399                      b: T) -> ty::expected_found<T> {
 400     if a_is_expected {
 401         ty::expected_found {expected: a, found: b}
 402     } else {
 403         ty::expected_found {expected: b, found: a}
 404     }
 405 }
 406
 407 pub fn mk_coercety(cx: &InferCtxt,
 408                    a_is_expected: bool,
 409                    origin: TypeOrigin,
 410                    a: ty::t,
 411                    b: ty::t)
 412                 -> CoerceResult {
 413     debug!("mk_coercety({} -> {})", a.inf_str(cx), b.inf_str(cx));
 414     indent(|| {
 415         cx.commit(|| {
 416             let trace = TypeTrace {
 417                 origin: origin,
 418                 values: Types(expected_found(a_is_expected, a, b))
 419             };
 420             Coerce(cx.combine_fields(a_is_expected, trace)).tys(a, b)
 421         })
 422     })
 423 }
 424
 425 // See comment on the type `resolve_state` below
 426 pub fn resolve_type(cx: &InferCtxt,
 427                     a: ty::t,
 428                     modes: uint)
 429                  -> fres<ty::t> {
 430     let mut resolver = resolver(cx, modes);
 431     resolver.resolve_type_chk(a)
 432 }
 433
 434 pub fn resolve_region(cx: &InferCtxt, r: ty::Region, modes: uint)
 435                    -> fres<ty::Region> {
 436     let mut resolver = resolver(cx, modes);
 437     resolver.resolve_region_chk(r)
 438 }
 439
 440 trait then {
 441     fn then<T:Clone>(&self, f: || -> Result<T,ty::type_err>)
 442         -> Result<T,ty::type_err>;
 443 }
 444
 445 impl then for ures {
 446     fn then<T:Clone>(&self, f: || -> Result<T,ty::type_err>)
 447         -> Result<T,ty::type_err> {
 448         self.and_then(|_i| f())
 449     }
 450 }
 451
 452 trait ToUres {
 453     fn to_ures(&self) -> ures;
 454 }
 455
 456 impl<T> ToUres for cres<T> {
 457     fn to_ures(&self) -> ures {
 458         match *self {
 459           Ok(ref _v) => Ok(()),
 460           Err(ref e) => Err((*e))
 461         }
 462     }
 463 }
 464
 465 trait CresCompare<T> {
 466     fn compare(&self, t: T, f: || -> ty::type_err) -> cres<T>;
 467 }
 468
 469 impl<T:Clone + Eq> CresCompare<T> for cres<T> {
 470     fn compare(&self, t: T, f: || -> ty::type_err) -> cres<T> {
 471         (*self).clone().and_then(|s| {
 472             if s == t {
 473                 (*self).clone()
 474             } else {
 475                 Err(f())
 476             }
 477         })
 478     }
 479 }
 480
 481 pub fn uok() -> ures {
 482     Ok(())
 483 }
 484
 485 fn rollback_to<V:Clone + Vid,T:Clone>(vb: &mut ValsAndBindings<V, T>,
 486                                       len: uint) {
 487     while vb.bindings.len() != len {
 488         let (vid, old_v) = vb.bindings.pop().unwrap();
 489         vb.vals.insert(vid.to_uint(), old_v);
 490     }
 491 }
 492
 493 pub struct Snapshot {
 494     ty_var_bindings_len: uint,
 495     int_var_bindings_len: uint,
 496     float_var_bindings_len: uint,
 497     region_vars_snapshot: uint,
 498 }
 499
 500 impl<'a> InferCtxt<'a> {
 501     pub fn combine_fields<'a>(&'a self, a_is_expected: bool, trace: TypeTrace)
 502                               -> CombineFields<'a> {
 503         CombineFields {infcx: self,
 504                        a_is_expected: a_is_expected,
 505                        trace: trace}
 506     }
 507
 508     pub fn sub<'a>(&'a self, a_is_expected: bool, trace: TypeTrace) -> Sub<'a> {
 509         Sub(self.combine_fields(a_is_expected, trace))
 510     }
 511
 512     pub fn lub<'a>(&'a self, a_is_expected: bool, trace: TypeTrace) -> Lub<'a> {
 513         Lub(self.combine_fields(a_is_expected, trace))
 514     }
 515
 516     pub fn in_snapshot(&self) -> bool {
 517         self.region_vars.in_snapshot()
 518     }
 519
 520     pub fn start_snapshot(&self) -> Snapshot {
 521         Snapshot {
 522             ty_var_bindings_len: self.ty_var_bindings.borrow().bindings.len(),
 523             int_var_bindings_len: self.int_var_bindings.borrow().bindings.len(),
 524             float_var_bindings_len: self.float_var_bindings.borrow().bindings.len(),
 525             region_vars_snapshot: self.region_vars.start_snapshot(),
 526         }
 527     }
 528
 529     pub fn rollback_to(&self, snapshot: &Snapshot) {
 530         debug!("rollback!");
 531         rollback_to(&mut *self.ty_var_bindings.borrow_mut(),
 532                     snapshot.ty_var_bindings_len);
 533         rollback_to(&mut *self.int_var_bindings.borrow_mut(),
 534                     snapshot.int_var_bindings_len);
 535         rollback_to(&mut *self.float_var_bindings.borrow_mut(),
 536                     snapshot.float_var_bindings_len);
 537
 538         self.region_vars.rollback_to(snapshot.region_vars_snapshot);
 539     }
 540
 541     /// Execute `f` and commit the bindings if successful
 542     pub fn commit<T,E>(&self, f: || -> Result<T,E>) -> Result<T,E> {
 543         assert!(!self.in_snapshot());
 544
 545         debug!("commit()");
 546         indent(|| {
 547             let r = self.try(|| f());
 548
 549             self.ty_var_bindings.borrow_mut().bindings.truncate(0);
 550             self.int_var_bindings.borrow_mut().bindings.truncate(0);
 551             self.region_vars.commit();
 552             r
 553         })
 554     }
 555
 556     /// Execute `f`, unroll bindings on failure
 557     pub fn try<T,E>(&self, f: || -> Result<T,E>) -> Result<T,E> {
 558         debug!("try()");
 559         let snapshot = self.start_snapshot();
 560         let r = f();
 561         match r {
 562             Ok(_) => { debug!("success"); }
 563             Err(ref e) => {
 564                 debug!("error: {:?}", *e);
 565                 self.rollback_to(&snapshot)
 566             }
 567         }
 568         r
 569     }
 570
 571     /// Execute `f` then unroll any bindings it creates
 572     pub fn probe<T,E>(&self, f: || -> Result<T,E>) -> Result<T,E> {
 573         debug!("probe()");
 574         indent(|| {
 575             let snapshot = self.start_snapshot();
 576             let r = f();
 577             self.rollback_to(&snapshot);
 578             r
 579         })
 580     }
 581 }
 582
 583 fn next_simple_var<V:Clone,T:Clone>(counter: &mut uint,
 584                                     bindings: &mut ValsAndBindings<V,
 585                                                                    Option<T>>)
 586                                     -> uint {
 587     let id = *counter;
 588     *counter += 1;
 589     bindings.vals.insert(id, Root(None, 0));
 590     return id;
 591 }
 592
 593 impl<'a> InferCtxt<'a> {
 594     pub fn next_ty_var_id(&self) -> TyVid {
 595         let id = self.ty_var_counter.get();
 596         self.ty_var_counter.set(id + 1);
 597         {
 598             let mut ty_var_bindings = self.ty_var_bindings.borrow_mut();
 599             let vals = &mut ty_var_bindings.vals;
 600             vals.insert(id, Root(Bounds { lb: None, ub: None }, 0u));
 601         }
 602         return TyVid(id);
 603     }
 604
 605     pub fn next_ty_var(&self) -> ty::t {
 606         ty::mk_var(self.tcx, self.next_ty_var_id())
 607     }
 608
 609     pub fn next_ty_vars(&self, n: uint) -> Vec<ty::t> {
 610         Vec::from_fn(n, |_i| self.next_ty_var())
 611     }
 612
 613     pub fn next_int_var_id(&self) -> IntVid {
 614         let mut int_var_counter = self.int_var_counter.get();
 615         let mut int_var_bindings = self.int_var_bindings.borrow_mut();
 616         let result = IntVid(next_simple_var(&mut int_var_counter,
 617                                             &mut *int_var_bindings));
 618         self.int_var_counter.set(int_var_counter);
 619         result
 620     }
 621
 622     pub fn next_float_var_id(&self) -> FloatVid {
 623         let mut float_var_counter = self.float_var_counter.get();
 624         let mut float_var_bindings = self.float_var_bindings.borrow_mut();
 625         let result = FloatVid(next_simple_var(&mut float_var_counter,
 626                                               &mut *float_var_bindings));
 627         self.float_var_counter.set(float_var_counter);
 628         result
 629     }
 630
 631     pub fn next_region_var(&self, origin: RegionVariableOrigin) -> ty::Region {
 632         ty::ReInfer(ty::ReVar(self.region_vars.new_region_var(origin)))
 633     }
 634
 635     pub fn region_vars_for_defs(&self,
 636                                 span: Span,
 637                                 defs: &[ty::RegionParameterDef])
 638                                 -> OwnedSlice<ty::Region> {
 639         defs.iter()
 640             .map(|d| self.next_region_var(EarlyBoundRegion(span, d.name)))
 641             .collect()
 642     }
 643
 644     pub fn fresh_bound_region(&self, binder_id: ast::NodeId) -> ty::Region {
 645         self.region_vars.new_bound(binder_id)
 646     }
 647
 648     pub fn resolve_regions_and_report_errors(&self) {
 649         let errors = self.region_vars.resolve_regions();
 650         self.report_region_errors(&errors); // see error_reporting.rs
 651     }
 652
 653     pub fn ty_to_str(&self, t: ty::t) -> String {
 654         ty_to_str(self.tcx,
 655                   self.resolve_type_vars_if_possible(t))
 656     }
 657
 658     pub fn tys_to_str(&self, ts: &[ty::t]) -> String {
 659         let tstrs: Vec<String> = ts.iter().map(|t| self.ty_to_str(*t)).collect();
 660         format_strbuf!("({})", tstrs.connect(", "))
 661     }
 662
 663     pub fn trait_ref_to_str(&self, t: &ty::TraitRef) -> String {
 664         let t = self.resolve_type_vars_in_trait_ref_if_possible(t);
 665         trait_ref_to_str(self.tcx, &t)
 666     }
 667
 668     pub fn resolve_type_vars_if_possible(&self, typ: ty::t) -> ty::t {
 669         match resolve_type(self, typ, resolve_nested_tvar | resolve_ivar) {
 670             Ok(new_type) => new_type,
 671             Err(_) => typ
 672         }
 673     }
 674
 675     pub fn resolve_type_vars_in_trait_ref_if_possible(&self,
 676                                                       trait_ref:
 677                                                       &ty::TraitRef)
 678                                                       -> ty::TraitRef {
 679         // make up a dummy type just to reuse/abuse the resolve machinery
 680         let dummy0 = ty::mk_trait(self.tcx,
 681                                   trait_ref.def_id,
 682                                   trait_ref.substs.clone(),
 683                                   ty::UniqTraitStore,
 684                                   ty::EmptyBuiltinBounds());
 685         let dummy1 = self.resolve_type_vars_if_possible(dummy0);
 686         match ty::get(dummy1).sty {
 687             ty::ty_trait(box ty::TyTrait { ref def_id, ref substs, .. }) => {
 688                 ty::TraitRef {
 689                     def_id: *def_id,
 690                     substs: (*substs).clone(),
 691                 }
 692             }
 693             _ => {
 694                 self.tcx.sess.bug(
 695                     format!("resolve_type_vars_if_possible() yielded {} \
 696                              when supplied with {}",
 697                             self.ty_to_str(dummy0),
 698                             self.ty_to_str(dummy1)).as_slice());
 699             }
 700         }
 701     }
 702
 703     // [Note-Type-error-reporting]
 704     // An invariant is that anytime the expected or actual type is ty_err (the special
 705     // error type, meaning that an error occurred when typechecking this expression),
 706     // this is a derived error. The error cascaded from another error (that was already
 707     // reported), so it's not useful to display it to the user.
 708     // The following four methods -- type_error_message_str, type_error_message_str_with_expected,
 709     // type_error_message, and report_mismatched_types -- implement this logic.
 710     // They check if either the actual or expected type is ty_err, and don't print the error
 711     // in this case. The typechecker should only ever report type errors involving mismatched
 712     // types using one of these four methods, and should not call span_err directly for such
 713     // errors.
 714     pub fn type_error_message_str(&self,
 715                                   sp: Span,
 716                                   mk_msg: |Option<String>, String| -> String,
 717                                   actual_ty: String,
 718                                   err: Option<&ty::type_err>) {
 719         self.type_error_message_str_with_expected(sp, mk_msg, None, actual_ty, err)
 720     }
 721
 722     pub fn type_error_message_str_with_expected(&self,
 723                                                 sp: Span,
 724                                                 mk_msg: |Option<String>,
 725                                                          String|
 726                                                          -> String,
 727                                                 expected_ty: Option<ty::t>,
 728                                                 actual_ty: String,
 729                                                 err: Option<&ty::type_err>) {
 730         debug!("hi! expected_ty = {:?}, actual_ty = {}", expected_ty, actual_ty);
 731
 732         let error_str = err.map_or("".to_string(), |t_err| {
 733             format!(" ({})", ty::type_err_to_str(self.tcx, t_err))
 734         });
 735         let resolved_expected = expected_ty.map(|e_ty| {
 736             self.resolve_type_vars_if_possible(e_ty)
 737         });
 738         if !resolved_expected.map_or(false, |e| { ty::type_is_error(e) }) {
 739             match resolved_expected {
 740                 None => {
 741                     self.tcx
 742                         .sess
 743                         .span_err(sp,
 744                                   format!("{}{}",
 745                                           mk_msg(None, actual_ty),
 746                                           error_str).as_slice())
 747                 }
 748                 Some(e) => {
 749                     self.tcx.sess.span_err(sp,
 750                         format!("{}{}",
 751                                 mk_msg(Some(self.ty_to_str(e)), actual_ty),
 752                                 error_str).as_slice());
 753                 }
 754             }
 755             for err in err.iter() {
 756                 ty::note_and_explain_type_err(self.tcx, *err)
 757             }
 758         }
 759     }
 760
 761     pub fn type_error_message(&self,
 762                               sp: Span,
 763                               mk_msg: |String| -> String,
 764                               actual_ty: ty::t,
 765                               err: Option<&ty::type_err>) {
 766         let actual_ty = self.resolve_type_vars_if_possible(actual_ty);
 767
 768         // Don't report an error if actual type is ty_err.
 769         if ty::type_is_error(actual_ty) {
 770             return;
 771         }
 772
 773         self.type_error_message_str(sp, |_e, a| { mk_msg(a) }, self.ty_to_str(actual_ty), err);
 774     }
 775
 776     pub fn report_mismatched_types(&self,
 777                                    sp: Span,
 778                                    e: ty::t,
 779                                    a: ty::t,
 780                                    err: &ty::type_err) {
 781         let resolved_expected =
 782             self.resolve_type_vars_if_possible(e);
 783         let mk_msg = match ty::get(resolved_expected).sty {
 784             // Don't report an error if expected is ty_err
 785             ty::ty_err => return,
 786             _ => {
 787                 // if I leave out : String, it infers &str and complains
 788                 |actual: String| {
 789                     format_strbuf!("mismatched types: expected `{}` but \
 790                                     found `{}`",
 791                                    self.ty_to_str(resolved_expected),
 792                                    actual)
 793                 }
 794             }
 795         };
 796         self.type_error_message(sp, mk_msg, a, Some(err));
 797     }
 798
 799     pub fn replace_late_bound_regions_with_fresh_regions(&self,
 800                                                          trace: TypeTrace,
 801                                                          fsig: &ty::FnSig)
 802                                                     -> (ty::FnSig,
 803                                                         HashMap<ty::BoundRegion,
 804                                                                 ty::Region>) {
 805         let (map, fn_sig) =
 806             replace_late_bound_regions_in_fn_sig(self.tcx, fsig, |br| {
 807                 let rvar = self.next_region_var(
 808                     BoundRegionInFnType(trace.origin.span(), br));
 809                 debug!("Bound region {} maps to {:?}",
 810                        bound_region_to_str(self.tcx, "", false, br),
 811                        rvar);
 812                 rvar
 813             });
 814         (fn_sig, map)
 815     }
 816 }
 817
 818 pub fn fold_regions_in_sig(tcx: &ty::ctxt,
 819                            fn_sig: &ty::FnSig,
 820                            fldr: |r: ty::Region| -> ty::Region)
 821                            -> ty::FnSig {
 822     ty_fold::RegionFolder::regions(tcx, fldr).fold_sig(fn_sig)
 823 }
 824
 825 impl TypeTrace {
 826     pub fn span(&self) -> Span {
 827         self.origin.span()
 828     }
 829 }
 830
 831 impl Repr for TypeTrace {
 832     fn repr(&self, tcx: &ty::ctxt) -> String {
 833         format_strbuf!("TypeTrace({})", self.origin.repr(tcx))
 834     }
 835 }
 836
 837 impl TypeOrigin {
 838     pub fn span(&self) -> Span {
 839         match *self {
 840             MethodCompatCheck(span) => span,
 841             ExprAssignable(span) => span,
 842             Misc(span) => span,
 843             RelateTraitRefs(span) => span,
 844             RelateSelfType(span) => span,
 845             MatchExpression(span) => span,
 846             IfExpression(span) => span,
 847         }
 848     }
 849 }
 850
 851 impl Repr for TypeOrigin {
 852     fn repr(&self, tcx: &ty::ctxt) -> String {
 853         match *self {
 854             MethodCompatCheck(a) => {
 855                 format_strbuf!("MethodCompatCheck({})", a.repr(tcx))
 856             }
 857             ExprAssignable(a) => {
 858                 format_strbuf!("ExprAssignable({})", a.repr(tcx))
 859             }
 860             Misc(a) => format_strbuf!("Misc({})", a.repr(tcx)),
 861             RelateTraitRefs(a) => {
 862                 format_strbuf!("RelateTraitRefs({})", a.repr(tcx))
 863             }
 864             RelateSelfType(a) => {
 865                 format_strbuf!("RelateSelfType({})", a.repr(tcx))
 866             }
 867             MatchExpression(a) => {
 868                 format_strbuf!("MatchExpression({})", a.repr(tcx))
 869             }
 870             IfExpression(a) => {
 871                 format_strbuf!("IfExpression({})", a.repr(tcx))
 872             }
 873         }
 874     }
 875 }
 876
 877 impl SubregionOrigin {
 878     pub fn span(&self) -> Span {
 879         match *self {
 880             Subtype(ref a) => a.span(),
 881             InfStackClosure(a) => a,
 882             InvokeClosure(a) => a,
 883             DerefPointer(a) => a,
 884             FreeVariable(a, _) => a,
 885             IndexSlice(a) => a,
 886             RelateObjectBound(a) => a,
 887             Reborrow(a) => a,
 888             ReborrowUpvar(a, _) => a,
 889             ReferenceOutlivesReferent(_, a) => a,
 890             BindingTypeIsNotValidAtDecl(a) => a,
 891             CallRcvr(a) => a,
 892             CallArg(a) => a,
 893             CallReturn(a) => a,
 894             AddrOf(a) => a,
 895             AutoBorrow(a) => a,
 896         }
 897     }
 898 }
 899
 900 impl Repr for SubregionOrigin {
 901     fn repr(&self, tcx: &ty::ctxt) -> String {
 902         match *self {
 903             Subtype(ref a) => {
 904                 format_strbuf!("Subtype({})", a.repr(tcx))
 905             }
 906             InfStackClosure(a) => {
 907                 format_strbuf!("InfStackClosure({})", a.repr(tcx))
 908             }
 909             InvokeClosure(a) => {
 910                 format_strbuf!("InvokeClosure({})", a.repr(tcx))
 911             }
 912             DerefPointer(a) => {
 913                 format_strbuf!("DerefPointer({})", a.repr(tcx))
 914             }
 915             FreeVariable(a, b) => {
 916                 format_strbuf!("FreeVariable({}, {})", a.repr(tcx), b)
 917             }
 918             IndexSlice(a) => {
 919                 format_strbuf!("IndexSlice({})", a.repr(tcx))
 920             }
 921             RelateObjectBound(a) => {
 922                 format_strbuf!("RelateObjectBound({})", a.repr(tcx))
 923             }
 924             Reborrow(a) => format_strbuf!("Reborrow({})", a.repr(tcx)),
 925             ReborrowUpvar(a, b) => {
 926                 format_strbuf!("ReborrowUpvar({},{:?})", a.repr(tcx), b)
 927             }
 928             ReferenceOutlivesReferent(_, a) => {
 929                 format_strbuf!("ReferenceOutlivesReferent({})", a.repr(tcx))
 930             }
 931             BindingTypeIsNotValidAtDecl(a) => {
 932                 format_strbuf!("BindingTypeIsNotValidAtDecl({})", a.repr(tcx))
 933             }
 934             CallRcvr(a) => format_strbuf!("CallRcvr({})", a.repr(tcx)),
 935             CallArg(a) => format_strbuf!("CallArg({})", a.repr(tcx)),
 936             CallReturn(a) => format_strbuf!("CallReturn({})", a.repr(tcx)),
 937             AddrOf(a) => format_strbuf!("AddrOf({})", a.repr(tcx)),
 938             AutoBorrow(a) => format_strbuf!("AutoBorrow({})", a.repr(tcx)),
 939         }
 940     }
 941 }
 942
 943 impl RegionVariableOrigin {
 944     pub fn span(&self) -> Span {
 945         match *self {
 946             MiscVariable(a) => a,
 947             PatternRegion(a) => a,
 948             AddrOfRegion(a) => a,
 949             AddrOfSlice(a) => a,
 950             Autoref(a) => a,
 951             Coercion(ref a) => a.span(),
 952             EarlyBoundRegion(a, _) => a,
 953             LateBoundRegion(a, _) => a,
 954             BoundRegionInFnType(a, _) => a,
 955             BoundRegionInCoherence(_) => codemap::DUMMY_SP,
 956             UpvarRegion(_, a) => a
 957         }
 958     }
 959 }
 960
 961 impl Repr for RegionVariableOrigin {
 962     fn repr(&self, tcx: &ty::ctxt) -> String {
 963         match *self {
 964             MiscVariable(a) => {
 965                 format_strbuf!("MiscVariable({})", a.repr(tcx))
 966             }
 967             PatternRegion(a) => {
 968                 format_strbuf!("PatternRegion({})", a.repr(tcx))
 969             }
 970             AddrOfRegion(a) => {
 971                 format_strbuf!("AddrOfRegion({})", a.repr(tcx))
 972             }
 973             AddrOfSlice(a) => format_strbuf!("AddrOfSlice({})", a.repr(tcx)),
 974             Autoref(a) => format_strbuf!("Autoref({})", a.repr(tcx)),
 975             Coercion(ref a) => format_strbuf!("Coercion({})", a.repr(tcx)),
 976             EarlyBoundRegion(a, b) => {
 977                 format_strbuf!("EarlyBoundRegion({},{})",
 978                                a.repr(tcx),
 979                                b.repr(tcx))
 980             }
 981             LateBoundRegion(a, b) => {
 982                 format_strbuf!("LateBoundRegion({},{})",
 983                                a.repr(tcx),
 984                                b.repr(tcx))
 985             }
 986             BoundRegionInFnType(a, b) => {
 987                 format_strbuf!("bound_regionInFnType({},{})",
 988                                a.repr(tcx),
 989                                b.repr(tcx))
 990             }
 991             BoundRegionInCoherence(a) => {
 992                 format_strbuf!("bound_regionInCoherence({})", a.repr(tcx))
 993             }
 994             UpvarRegion(a, b) => {
 995                 format_strbuf!("UpvarRegion({}, {})",
 996                                a.repr(tcx),
 997                                b.repr(tcx))
 998             }
 999         }
1000     }
1001 }