src/librustc/middle/typeck/infer/mod.rs

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