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