src/librustc/middle/traits/select.rs

   1 // Copyright 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 high-level documentation
  12 #![allow(dead_code)] // FIXME -- just temporarily
  13
  14 pub use self::MethodMatchResult::*;
  15 pub use self::MethodMatchedData::*;
  16 use self::Candidate::*;
  17 use self::BuiltinBoundConditions::*;
  18 use self::EvaluationResult::*;
  19
  20 use super::{Obligation, ObligationCause};
  21 use super::{SelectionError, Unimplemented, Overflow,
  22             OutputTypeParameterMismatch};
  23 use super::{Selection};
  24 use super::{SelectionResult};
  25 use super::{VtableBuiltin, VtableImpl, VtableParam, VtableUnboxedClosure, VtableFnPointer};
  26 use super::{VtableImplData, VtableParamData, VtableBuiltinData};
  27 use super::{util};
  28
  29 use middle::fast_reject;
  30 use middle::mem_categorization::Typer;
  31 use middle::subst::{Subst, Substs, VecPerParamSpace};
  32 use middle::ty::{mod, Ty};
  33 use middle::infer;
  34 use middle::infer::{InferCtxt, TypeSkolemizer};
  35 use middle::ty_fold::TypeFoldable;
  36 use std::cell::RefCell;
  37 use std::collections::hash_map::HashMap;
  38 use std::rc::Rc;
  39 use syntax::{abi, ast};
  40 use util::common::ErrorReported;
  41 use util::ppaux::Repr;
  42
  43 pub struct SelectionContext<'cx, 'tcx:'cx> {
  44     infcx: &'cx InferCtxt<'cx, 'tcx>,
  45     param_env: &'cx ty::ParameterEnvironment<'tcx>,
  46     typer: &'cx (Typer<'tcx>+'cx),
  47
  48     /// Skolemizer used specifically for skolemizing entries on the
  49     /// obligation stack. This ensures that all entries on the stack
  50     /// at one time will have the same set of skolemized entries,
  51     /// which is important for checking for trait bounds that
  52     /// recursively require themselves.
  53     skolemizer: TypeSkolemizer<'cx, 'tcx>,
  54
  55     /// If true, indicates that the evaluation should be conservative
  56     /// and consider the possibility of types outside this crate.
  57     /// This comes up primarily when resolving ambiguity. Imagine
  58     /// there is some trait reference `$0 : Bar` where `$0` is an
  59     /// inference variable. If `intercrate` is true, then we can never
  60     /// say for sure that this reference is not implemented, even if
  61     /// there are *no impls at all for `Bar`*, because `$0` could be
  62     /// bound to some type that in a downstream crate that implements
  63     /// `Bar`. This is the suitable mode for coherence. Elsewhere,
  64     /// though, we set this to false, because we are only interested
  65     /// in types that the user could actually have written --- in
  66     /// other words, we consider `$0 : Bar` to be unimplemented if
  67     /// there is no type that the user could *actually name* that
  68     /// would satisfy it. This avoids crippling inference, basically.
  69     intercrate: bool,
  70 }
  71
  72 // A stack that walks back up the stack frame.
  73 struct ObligationStack<'prev, 'tcx: 'prev> {
  74     obligation: &'prev Obligation<'tcx>,
  75
  76     /// Trait ref from `obligation` but skolemized with the
  77     /// selection-context's skolemizer. Used to check for recursion.
  78     skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
  79
  80     previous: Option<&'prev ObligationStack<'prev, 'tcx>>
  81 }
  82
  83 #[deriving(Clone)]
  84 pub struct SelectionCache<'tcx> {
  85     hashmap: RefCell<HashMap<Rc<ty::TraitRef<'tcx>>,
  86                              SelectionResult<'tcx, Candidate<'tcx>>>>,
  87 }
  88
  89 pub enum MethodMatchResult {
  90     MethodMatched(MethodMatchedData),
  91     MethodAmbiguous(/* list of impls that could apply */ Vec<ast::DefId>),
  92     MethodDidNotMatch,
  93 }
  94
  95 #[deriving(Show)]
  96 pub enum MethodMatchedData {
  97     // In the case of a precise match, we don't really need to store
  98     // how the match was found. So don't.
  99     PreciseMethodMatch,
 100
 101     // In the case of a coercion, we need to know the precise impl so
 102     // that we can determine the type to which things were coerced.
 103     CoerciveMethodMatch(/* impl we matched */ ast::DefId)
 104 }
 105
 106 impl Copy for MethodMatchedData {}
 107
 108 /// The selection process begins by considering all impls, where
 109 /// clauses, and so forth that might resolve an obligation.  Sometimes
 110 /// we'll be able to say definitively that (e.g.) an impl does not
 111 /// apply to the obligation: perhaps it is defined for `uint` but the
 112 /// obligation is for `int`. In that case, we drop the impl out of the
 113 /// list.  But the other cases are considered *candidates*.
 114 ///
 115 /// Candidates can either be definitive or ambiguous. An ambiguous
 116 /// candidate is one that might match or might not, depending on how
 117 /// type variables wind up being resolved. This only occurs during inference.
 118 ///
 119 /// For selection to succeed, there must be exactly one non-ambiguous
 120 /// candidate.  Usually, it is not possible to have more than one
 121 /// definitive candidate, due to the coherence rules. However, there is
 122 /// one case where it could occur: if there is a blanket impl for a
 123 /// trait (that is, an impl applied to all T), and a type parameter
 124 /// with a where clause. In that case, we can have a candidate from the
 125 /// where clause and a second candidate from the impl. This is not a
 126 /// problem because coherence guarantees us that the impl which would
 127 /// be used to satisfy the where clause is the same one that we see
 128 /// now. To resolve this issue, therefore, we ignore impls if we find a
 129 /// matching where clause. Part of the reason for this is that where
 130 /// clauses can give additional information (like, the types of output
 131 /// parameters) that would have to be inferred from the impl.
 132 #[deriving(PartialEq,Eq,Show,Clone)]
 133 enum Candidate<'tcx> {
 134     BuiltinCandidate(ty::BuiltinBound),
 135     ParamCandidate(VtableParamData<'tcx>),
 136     ImplCandidate(ast::DefId),
 137
 138     /// Implementation of a `Fn`-family trait by one of the
 139     /// anonymous types generated for a `||` expression.
 140     UnboxedClosureCandidate(/* closure */ ast::DefId, Substs<'tcx>),
 141
 142     /// Implementation of a `Fn`-family trait by one of the anonymous
 143     /// types generated for a fn pointer type (e.g., `fn(int)->int`)
 144     FnPointerCandidate,
 145
 146     ErrorCandidate,
 147 }
 148
 149 struct CandidateSet<'tcx> {
 150     vec: Vec<Candidate<'tcx>>,
 151     ambiguous: bool
 152 }
 153
 154 enum BuiltinBoundConditions<'tcx> {
 155     If(Vec<Ty<'tcx>>),
 156     ParameterBuiltin,
 157     AmbiguousBuiltin
 158 }
 159
 160 #[deriving(Show)]
 161 enum EvaluationResult<'tcx> {
 162     EvaluatedToOk,
 163     EvaluatedToAmbig,
 164     EvaluatedToErr(SelectionError<'tcx>),
 165 }
 166
 167 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 168     pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>,
 169                param_env: &'cx ty::ParameterEnvironment<'tcx>,
 170                typer: &'cx Typer<'tcx>)
 171                -> SelectionContext<'cx, 'tcx> {
 172         SelectionContext {
 173             infcx: infcx,
 174             param_env: param_env,
 175             typer: typer,
 176             skolemizer: infcx.skolemizer(),
 177             intercrate: false,
 178         }
 179     }
 180
 181     pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'tcx>,
 182                       param_env: &'cx ty::ParameterEnvironment<'tcx>,
 183                       typer: &'cx Typer<'tcx>)
 184                       -> SelectionContext<'cx, 'tcx> {
 185         SelectionContext {
 186             infcx: infcx,
 187             param_env: param_env,
 188             typer: typer,
 189             skolemizer: infcx.skolemizer(),
 190             intercrate: true,
 191         }
 192     }
 193
 194     pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
 195         self.infcx.tcx
 196     }
 197
 198     ///////////////////////////////////////////////////////////////////////////
 199     // Selection
 200     //
 201     // The selection phase tries to identify *how* an obligation will
 202     // be resolved. For example, it will identify which impl or
 203     // parameter bound is to be used. The process can be inconclusive
 204     // if the self type in the obligation is not fully inferred. Selection
 205     // can result in an error in one of two ways:
 206     //
 207     // 1. If no applicable impl or parameter bound can be found.
 208     // 2. If the output type parameters in the obligation do not match
 209     //    those specified by the impl/bound. For example, if the obligation
 210     //    is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
 211     //    `impl<T> Iterable<T> for Vec<T>`, than an error would result.
 212
 213     /// Evaluates whether the obligation can be satisfied. Returns an indication of whether the
 214     /// obligation can be satisfied and, if so, by what means. Never affects surrounding typing
 215     /// environment.
 216     pub fn select(&mut self, obligation: &Obligation<'tcx>)
 217                   -> SelectionResult<'tcx, Selection<'tcx>> {
 218         debug!("select({})", obligation.repr(self.tcx()));
 219         assert!(!obligation.trait_ref.has_escaping_regions());
 220
 221         let stack = self.push_stack(None, obligation);
 222         match try!(self.candidate_from_obligation(&stack)) {
 223             None => Ok(None),
 224             Some(candidate) => Ok(Some(try!(self.confirm_candidate(obligation, candidate)))),
 225         }
 226     }
 227
 228     pub fn select_inherent_impl(&mut self,
 229                                 impl_def_id: ast::DefId,
 230                                 obligation_cause: ObligationCause<'tcx>,
 231                                 obligation_self_ty: Ty<'tcx>)
 232                                 -> SelectionResult<'tcx, VtableImplData<'tcx, Obligation<'tcx>>>
 233     {
 234         debug!("select_inherent_impl(impl_def_id={}, obligation_self_ty={})",
 235                impl_def_id.repr(self.tcx()),
 236                obligation_self_ty.repr(self.tcx()));
 237
 238         match self.match_inherent_impl(impl_def_id,
 239                                        obligation_cause,
 240                                        obligation_self_ty) {
 241             Ok(substs) => {
 242                 let vtable_impl = self.vtable_impl(impl_def_id, substs, obligation_cause, 0);
 243                 Ok(Some(vtable_impl))
 244             }
 245             Err(()) => {
 246                 Err(Unimplemented)
 247             }
 248         }
 249     }
 250
 251     ///////////////////////////////////////////////////////////////////////////
 252     // EVALUATION
 253     //
 254     // Tests whether an obligation can be selected or whether an impl
 255     // can be applied to particular types. It skips the "confirmation"
 256     // step and hence completely ignores output type parameters.
 257     //
 258     // The result is "true" if the obligation *may* hold and "false" if
 259     // we can be sure it does not.
 260
 261     /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
 262     pub fn evaluate_obligation(&mut self,
 263                                obligation: &Obligation<'tcx>)
 264                                -> bool
 265     {
 266         debug!("evaluate_obligation({})",
 267                obligation.repr(self.tcx()));
 268         assert!(!obligation.trait_ref.has_escaping_regions());
 269
 270         let stack = self.push_stack(None, obligation);
 271         self.evaluate_stack(&stack).may_apply()
 272     }
 273
 274     fn evaluate_builtin_bound_recursively<'o>(&mut self,
 275                                               bound: ty::BuiltinBound,
 276                                               previous_stack: &ObligationStack<'o, 'tcx>,
 277                                               ty: Ty<'tcx>)
 278                                               -> EvaluationResult<'tcx>
 279     {
 280         let obligation =
 281             util::obligation_for_builtin_bound(
 282                 self.tcx(),
 283                 previous_stack.obligation.cause,
 284                 bound,
 285                 previous_stack.obligation.recursion_depth + 1,
 286                 ty);
 287
 288         match obligation {
 289             Ok(obligation) => {
 290                 self.evaluate_obligation_recursively(Some(previous_stack), &obligation)
 291             }
 292             Err(ErrorReported) => {
 293                 EvaluatedToOk
 294             }
 295         }
 296     }
 297
 298     fn evaluate_obligation_recursively<'o>(&mut self,
 299                                            previous_stack: Option<&ObligationStack<'o, 'tcx>>,
 300                                            obligation: &Obligation<'tcx>)
 301                                            -> EvaluationResult<'tcx>
 302     {
 303         debug!("evaluate_obligation_recursively({})",
 304                obligation.repr(self.tcx()));
 305
 306         let stack = self.push_stack(previous_stack.map(|x| x), obligation);
 307
 308         let result = self.evaluate_stack(&stack);
 309
 310         debug!("result: {}", result);
 311         result
 312     }
 313
 314     fn evaluate_stack<'o>(&mut self,
 315                           stack: &ObligationStack<'o, 'tcx>)
 316                           -> EvaluationResult<'tcx>
 317     {
 318         // In intercrate mode, whenever any of the types are unbound,
 319         // there can always be an impl. Even if there are no impls in
 320         // this crate, perhaps the type would be unified with
 321         // something from another crate that does provide an impl.
 322         //
 323         // In intracrate mode, we must still be conservative. The reason is
 324         // that we want to avoid cycles. Imagine an impl like:
 325         //
 326         //     impl<T:Eq> Eq for Vec<T>
 327         //
 328         // and a trait reference like `$0 : Eq` where `$0` is an
 329         // unbound variable. When we evaluate this trait-reference, we
 330         // will unify `$0` with `Vec<$1>` (for some fresh variable
 331         // `$1`), on the condition that `$1 : Eq`. We will then wind
 332         // up with many candidates (since that are other `Eq` impls
 333         // that apply) and try to winnow things down. This results in
 334         // a recurssive evaluation that `$1 : Eq` -- as you can
 335         // imagine, this is just where we started. To avoid that, we
 336         // check for unbound variables and return an ambiguous (hence possible)
 337         // match if we've seen this trait before.
 338         //
 339         // This suffices to allow chains like `FnMut` implemented in
 340         // terms of `Fn` etc, but we could probably make this more
 341         // precise still.
 342         let input_types = stack.skol_trait_ref.input_types();
 343         let unbound_input_types = input_types.iter().any(|&t| ty::type_is_skolemized(t));
 344         if
 345             unbound_input_types &&
 346              (self.intercrate ||
 347               stack.iter().skip(1).any(
 348                   |prev| stack.skol_trait_ref.def_id == prev.skol_trait_ref.def_id))
 349         {
 350             debug!("evaluate_stack_intracrate({}) --> unbound argument, recursion -->  ambiguous",
 351                    stack.skol_trait_ref.repr(self.tcx()));
 352             return EvaluatedToAmbig;
 353         }
 354
 355         // If there is any previous entry on the stack that precisely
 356         // matches this obligation, then we can assume that the
 357         // obligation is satisfied for now (still all other conditions
 358         // must be met of course). One obvious case this comes up is
 359         // marker traits like `Send`. Think of a linked list:
 360         //
 361         //    struct List<T> { data: T, next: Option<Box<List<T>>> {
 362         //
 363         // `Box<List<T>>` will be `Send` if `T` is `Send` and
 364         // `Option<Box<List<T>>>` is `Send`, and in turn
 365         // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
 366         // `Send`.
 367         //
 368         // Note that we do this comparison using the `skol_trait_ref`
 369         // fields. Because these have all been skolemized using
 370         // `self.skolemizer`, we can be sure that (a) this will not
 371         // affect the inferencer state and (b) that if we see two
 372         // skolemized types with the same index, they refer to the
 373         // same unbound type variable.
 374         if
 375             stack.iter()
 376             .skip(1) // skip top-most frame
 377             .any(|prev| stack.skol_trait_ref == prev.skol_trait_ref)
 378         {
 379             debug!("evaluate_stack_intracrate({}) --> recursive",
 380                    stack.skol_trait_ref.repr(self.tcx()));
 381             return EvaluatedToOk;
 382         }
 383
 384         match self.candidate_from_obligation(stack) {
 385             Ok(Some(c)) => self.winnow_candidate(stack, &c),
 386             Ok(None) => EvaluatedToAmbig,
 387             Err(e) => EvaluatedToErr(e),
 388         }
 389     }
 390
 391     /// Evaluates whether the impl with id `impl_def_id` could be applied to the self type
 392     /// `obligation_self_ty`. This can be used either for trait or inherent impls.
 393     pub fn evaluate_impl(&mut self,
 394                          impl_def_id: ast::DefId,
 395                          obligation: &Obligation<'tcx>)
 396                          -> bool
 397     {
 398         debug!("evaluate_impl(impl_def_id={}, obligation={})",
 399                impl_def_id.repr(self.tcx()),
 400                obligation.repr(self.tcx()));
 401
 402         self.infcx.probe(|| {
 403             match self.match_impl(impl_def_id, obligation) {
 404                 Ok(substs) => {
 405                     let vtable_impl = self.vtable_impl(impl_def_id,
 406                                                        substs,
 407                                                        obligation.cause,
 408                                                        obligation.recursion_depth + 1);
 409                     self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
 410                 }
 411                 Err(()) => {
 412                     false
 413                 }
 414             }
 415         })
 416     }
 417
 418     ///////////////////////////////////////////////////////////////////////////
 419     // CANDIDATE ASSEMBLY
 420     //
 421     // The selection process begins by examining all in-scope impls,
 422     // caller obligations, and so forth and assembling a list of
 423     // candidates. See `doc.rs` and the `Candidate` type for more details.
 424
 425     fn candidate_from_obligation<'o>(&mut self,
 426                                      stack: &ObligationStack<'o, 'tcx>)
 427                                      -> SelectionResult<'tcx, Candidate<'tcx>>
 428     {
 429         // Watch out for overflow. This intentionally bypasses (and does
 430         // not update) the cache.
 431         let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
 432         if stack.obligation.recursion_depth >= recursion_limit {
 433             debug!("{} --> overflow (limit={})",
 434                    stack.obligation.repr(self.tcx()),
 435                    recursion_limit);
 436             return Err(Overflow)
 437         }
 438
 439         // Check the cache. Note that we skolemize the trait-ref
 440         // separately rather than using `stack.skol_trait_ref` -- this
 441         // is because we want the unbound variables to be replaced
 442         // with fresh skolemized types starting from index 0.
 443         let cache_skol_trait_ref =
 444             self.infcx.skolemize(stack.obligation.trait_ref.clone());
 445         debug!("candidate_from_obligation(cache_skol_trait_ref={}, obligation={})",
 446                cache_skol_trait_ref.repr(self.tcx()),
 447                stack.repr(self.tcx()));
 448         assert!(!stack.obligation.trait_ref.has_escaping_regions());
 449
 450         match self.check_candidate_cache(cache_skol_trait_ref.clone()) {
 451             Some(c) => {
 452                 debug!("CACHE HIT: cache_skol_trait_ref={}, candidate={}",
 453                        cache_skol_trait_ref.repr(self.tcx()),
 454                        c.repr(self.tcx()));
 455                 return c;
 456             }
 457             None => { }
 458         }
 459
 460         // If no match, compute result and insert into cache.
 461         let candidate = self.candidate_from_obligation_no_cache(stack);
 462         debug!("CACHE MISS: cache_skol_trait_ref={}, candidate={}",
 463                cache_skol_trait_ref.repr(self.tcx()), candidate.repr(self.tcx()));
 464         self.insert_candidate_cache(cache_skol_trait_ref, candidate.clone());
 465         candidate
 466     }
 467
 468     fn candidate_from_obligation_no_cache<'o>(&mut self,
 469                                               stack: &ObligationStack<'o, 'tcx>)
 470                                               -> SelectionResult<'tcx, Candidate<'tcx>>
 471     {
 472         if ty::type_is_error(stack.obligation.self_ty()) {
 473             return Ok(Some(ErrorCandidate));
 474         }
 475
 476         let candidate_set = try!(self.assemble_candidates(stack));
 477
 478         if candidate_set.ambiguous {
 479             debug!("candidate set contains ambig");
 480             return Ok(None);
 481         }
 482
 483         let mut candidates = candidate_set.vec;
 484
 485         debug!("assembled {} candidates for {}",
 486                candidates.len(), stack.repr(self.tcx()));
 487
 488         // At this point, we know that each of the entries in the
 489         // candidate set is *individually* applicable. Now we have to
 490         // figure out if they contain mutual incompatibilities. This
 491         // frequently arises if we have an unconstrained input type --
 492         // for example, we are looking for $0:Eq where $0 is some
 493         // unconstrained type variable. In that case, we'll get a
 494         // candidate which assumes $0 == int, one that assumes $0 ==
 495         // uint, etc. This spells an ambiguity.
 496
 497         // If there is more than one candidate, first winnow them down
 498         // by considering extra conditions (nested obligations and so
 499         // forth). We don't winnow if there is exactly one
 500         // candidate. This is a relatively minor distinction but it
 501         // can lead to better inference and error-reporting. An
 502         // example would be if there was an impl:
 503         //
 504         //     impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
 505         //
 506         // and we were to see some code `foo.push_clone()` where `boo`
 507         // is a `Vec<Bar>` and `Bar` does not implement `Clone`.  If
 508         // we were to winnow, we'd wind up with zero candidates.
 509         // Instead, we select the right impl now but report `Bar does
 510         // not implement Clone`.
 511         if candidates.len() > 1 {
 512             candidates.retain(|c| self.winnow_candidate(stack, c).may_apply())
 513         }
 514
 515         // If there are STILL multiple candidate, we can further reduce
 516         // the list by dropping duplicates.
 517         if candidates.len() > 1 {
 518             let mut i = 0;
 519             while i < candidates.len() {
 520                 let is_dup =
 521                     range(0, candidates.len())
 522                     .filter(|&j| i != j)
 523                     .any(|j| self.candidate_should_be_dropped_in_favor_of(stack,
 524                                                                           &candidates[i],
 525                                                                           &candidates[j]));
 526                 if is_dup {
 527                     debug!("Dropping candidate #{}/{}: {}",
 528                            i, candidates.len(), candidates[i].repr(self.tcx()));
 529                     candidates.swap_remove(i);
 530                 } else {
 531                     debug!("Retaining candidate #{}/{}: {}",
 532                            i, candidates.len(), candidates[i].repr(self.tcx()));
 533                     i += 1;
 534                 }
 535             }
 536         }
 537
 538         // If there are *STILL* multiple candidates, give up and
 539         // report ambiguiuty.
 540         if candidates.len() > 1 {
 541             debug!("multiple matches, ambig");
 542             return Ok(None);
 543         }
 544
 545         // If there are *NO* candidates, that there are no impls --
 546         // that we know of, anyway. Note that in the case where there
 547         // are unbound type variables within the obligation, it might
 548         // be the case that you could still satisfy the obligation
 549         // from another crate by instantiating the type variables with
 550         // a type from another crate that does have an impl. This case
 551         // is checked for in `evaluate_stack` (and hence users
 552         // who might care about this case, like coherence, should use
 553         // that function).
 554         if candidates.len() == 0 {
 555             return Err(Unimplemented);
 556         }
 557
 558         // Just one candidate left.
 559         let candidate = candidates.pop().unwrap();
 560         Ok(Some(candidate))
 561     }
 562
 563     fn pick_candidate_cache(&self,
 564                             cache_skol_trait_ref: &Rc<ty::TraitRef<'tcx>>)
 565                             -> &SelectionCache<'tcx>
 566     {
 567         // High-level idea: we have to decide whether to consult the
 568         // cache that is specific to this scope, or to consult the
 569         // global cache. We want the cache that is specific to this
 570         // scope whenever where clauses might affect the result.
 571
 572         // Avoid using the master cache during coherence and just rely
 573         // on the local cache. This effectively disables caching
 574         // during coherence. It is really just a simplification to
 575         // avoid us having to fear that coherence results "pollute"
 576         // the master cache. Since coherence executes pretty quickly,
 577         // it's not worth going to more trouble to increase the
 578         // hit-rate I don't think.
 579         if self.intercrate {
 580             return &self.param_env.selection_cache;
 581         }
 582
 583         // If the trait refers to any parameters in scope, then use
 584         // the cache of the param-environment.
 585         if
 586             cache_skol_trait_ref.input_types().iter().any(
 587                 |&t| ty::type_has_self(t) || ty::type_has_params(t))
 588         {
 589             return &self.param_env.selection_cache;
 590         }
 591
 592         // If the trait refers to unbound type variables, and there
 593         // are where clauses in scope, then use the local environment.
 594         // If there are no where clauses in scope, which is a very
 595         // common case, then we can use the global environment.
 596         // See the discussion in doc.rs for more details.
 597         if
 598             !self.param_env.caller_obligations.is_empty()
 599             &&
 600             cache_skol_trait_ref.input_types().iter().any(
 601                 |&t| ty::type_has_ty_infer(t))
 602         {
 603             return &self.param_env.selection_cache;
 604         }
 605
 606         // Otherwise, we can use the global cache.
 607         &self.tcx().selection_cache
 608     }
 609
 610     fn check_candidate_cache(&mut self,
 611                              cache_skol_trait_ref: Rc<ty::TraitRef<'tcx>>)
 612                              -> Option<SelectionResult<'tcx, Candidate<'tcx>>>
 613     {
 614         let cache = self.pick_candidate_cache(&cache_skol_trait_ref);
 615         let hashmap = cache.hashmap.borrow();
 616         hashmap.get(&cache_skol_trait_ref).map(|c| (*c).clone())
 617     }
 618
 619     fn insert_candidate_cache(&mut self,
 620                               cache_skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
 621                               candidate: SelectionResult<'tcx, Candidate<'tcx>>)
 622     {
 623         let cache = self.pick_candidate_cache(&cache_skol_trait_ref);
 624         let mut hashmap = cache.hashmap.borrow_mut();
 625         hashmap.insert(cache_skol_trait_ref, candidate);
 626     }
 627
 628     fn assemble_candidates<'o>(&mut self,
 629                                stack: &ObligationStack<'o, 'tcx>)
 630                                -> Result<CandidateSet<'tcx>, SelectionError<'tcx>>
 631     {
 632         // Check for overflow.
 633
 634         let ObligationStack { obligation, .. } = *stack;
 635
 636         let mut candidates = CandidateSet {
 637             vec: Vec::new(),
 638             ambiguous: false
 639         };
 640
 641         // Other bounds. Consider both in-scope bounds from fn decl
 642         // and applicable impls. There is a certain set of precedence rules here.
 643
 644         match self.tcx().lang_items.to_builtin_kind(obligation.trait_ref.def_id) {
 645             Some(ty::BoundCopy) => {
 646                 debug!("obligation self ty is {}",
 647                        obligation.self_ty().repr(self.tcx()));
 648
 649                 // If the user has asked for the older, compatibility
 650                 // behavior, ignore user-defined impls here. This will
 651                 // go away by the time 1.0 is released.
 652                 if !self.tcx().sess.features.borrow().opt_out_copy {
 653                     try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
 654                 }
 655
 656                 try!(self.assemble_builtin_bound_candidates(ty::BoundCopy,
 657                                                             stack,
 658                                                             &mut candidates));
 659             }
 660
 661             None => {
 662                 // For the time being, we ignore user-defined impls for builtin-bounds, other than
 663                 // `Copy`.
 664                 // (And unboxed candidates only apply to the Fn/FnMut/etc traits.)
 665                 try!(self.assemble_unboxed_closure_candidates(obligation, &mut candidates));
 666                 try!(self.assemble_fn_pointer_candidates(obligation, &mut candidates));
 667                 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
 668             }
 669
 670             Some(bound) => {
 671                 try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
 672             }
 673         }
 674
 675         try!(self.assemble_candidates_from_caller_bounds(obligation, &mut candidates));
 676         debug!("candidate list size: {}", candidates.vec.len());
 677         Ok(candidates)
 678     }
 679
 680     /// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller
 681     /// supplied to find out whether it is listed among them.
 682     ///
 683     /// Never affects inference environment.
 684     fn assemble_candidates_from_caller_bounds(&mut self,
 685                                               obligation: &Obligation<'tcx>,
 686                                               candidates: &mut CandidateSet<'tcx>)
 687                                               -> Result<(),SelectionError<'tcx>>
 688     {
 689         debug!("assemble_candidates_from_caller_bounds({})",
 690                obligation.repr(self.tcx()));
 691
 692         let caller_trait_refs: Vec<Rc<ty::TraitRef>> =
 693             self.param_env.caller_obligations.iter()
 694             .map(|o| o.trait_ref.clone())
 695             .collect();
 696
 697         let all_bounds =
 698             util::transitive_bounds(
 699                 self.tcx(), caller_trait_refs.as_slice());
 700
 701         let matching_bounds =
 702             all_bounds.filter(
 703                 |bound| self.infcx.probe(
 704                     || self.match_trait_refs(obligation,
 705                                              (*bound).clone())).is_ok());
 706
 707         let param_candidates =
 708             matching_bounds.map(
 709                 |bound| ParamCandidate(VtableParamData { bound: bound }));
 710
 711         candidates.vec.extend(param_candidates);
 712
 713         Ok(())
 714     }
 715
 716     /// Check for the artificial impl that the compiler will create for an obligation like `X :
 717     /// FnMut<..>` where `X` is an unboxed closure type.
 718     ///
 719     /// Note: the type parameters on an unboxed closure candidate are modeled as *output* type
 720     /// parameters and hence do not affect whether this trait is a match or not. They will be
 721     /// unified during the confirmation step.
 722     fn assemble_unboxed_closure_candidates(&mut self,
 723                                            obligation: &Obligation<'tcx>,
 724                                            candidates: &mut CandidateSet<'tcx>)
 725                                            -> Result<(),SelectionError<'tcx>>
 726     {
 727         let kind = match self.fn_family_trait_kind(obligation.trait_ref.def_id) {
 728             Some(k) => k,
 729             None => { return Ok(()); }
 730         };
 731
 732         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
 733         let (closure_def_id, substs) = match self_ty.sty {
 734             ty::ty_unboxed_closure(id, _, ref substs) => (id, substs.clone()),
 735             ty::ty_infer(ty::TyVar(_)) => {
 736                 candidates.ambiguous = true;
 737                 return Ok(());
 738             }
 739             _ => { return Ok(()); }
 740         };
 741
 742         debug!("assemble_unboxed_candidates: self_ty={} obligation={}",
 743                self_ty.repr(self.tcx()),
 744                obligation.repr(self.tcx()));
 745
 746         let closure_kind = match self.typer.unboxed_closures().borrow().get(&closure_def_id) {
 747             Some(closure) => closure.kind,
 748             None => {
 749                 self.tcx().sess.span_bug(
 750                     obligation.cause.span,
 751                     format!("No entry for unboxed closure: {}",
 752                             closure_def_id.repr(self.tcx())).as_slice());
 753             }
 754         };
 755
 756         if closure_kind == kind {
 757             candidates.vec.push(UnboxedClosureCandidate(closure_def_id, substs.clone()));
 758         }
 759
 760         Ok(())
 761     }
 762
 763     /// Implement one of the `Fn()` family for a fn pointer.
 764     fn assemble_fn_pointer_candidates(&mut self,
 765                                       obligation: &Obligation<'tcx>,
 766                                       candidates: &mut CandidateSet<'tcx>)
 767                                       -> Result<(),SelectionError<'tcx>>
 768     {
 769         // We provide a `Fn` impl for fn pointers. There is no need to provide
 770         // the other traits (e.g. `FnMut`) since those are provided by blanket
 771         // impls.
 772         if Some(obligation.trait_ref.def_id) != self.tcx().lang_items.fn_trait() {
 773             return Ok(());
 774         }
 775
 776         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
 777         match self_ty.sty {
 778             ty::ty_infer(..) => {
 779                 candidates.ambiguous = true; // could wind up being a fn() type
 780             }
 781
 782             // provide an impl, but only for suitable `fn` pointers
 783             ty::ty_bare_fn(ty::BareFnTy {
 784                 fn_style: ast::NormalFn,
 785                 abi: abi::Rust,
 786                 sig: ty::FnSig {
 787                     inputs: _,
 788                     output: ty::FnConverging(_),
 789                     variadic: false
 790                 }
 791             }) => {
 792                 candidates.vec.push(FnPointerCandidate);
 793             }
 794
 795             _ => { }
 796         }
 797
 798         Ok(())
 799     }
 800
 801     /// Search for impls that might apply to `obligation`.
 802     fn assemble_candidates_from_impls(&mut self,
 803                                       obligation: &Obligation<'tcx>,
 804                                       candidates: &mut CandidateSet<'tcx>)
 805                                       -> Result<(), SelectionError<'tcx>>
 806     {
 807         let all_impls = self.all_impls(obligation.trait_ref.def_id);
 808         for &impl_def_id in all_impls.iter() {
 809             self.infcx.probe(|| {
 810                 match self.match_impl(impl_def_id, obligation) {
 811                     Ok(_) => {
 812                         candidates.vec.push(ImplCandidate(impl_def_id));
 813                     }
 814                     Err(()) => { }
 815                 }
 816             });
 817         }
 818         Ok(())
 819     }
 820
 821     ///////////////////////////////////////////////////////////////////////////
 822     // WINNOW
 823     //
 824     // Winnowing is the process of attempting to resolve ambiguity by
 825     // probing further. During the winnowing process, we unify all
 826     // type variables (ignoring skolemization) and then we also
 827     // attempt to evaluate recursive bounds to see if they are
 828     // satisfied.
 829
 830     /// Further evaluate `candidate` to decide whether all type parameters match and whether nested
 831     /// obligations are met. Returns true if `candidate` remains viable after this further
 832     /// scrutiny.
 833     fn winnow_candidate<'o>(&mut self,
 834                             stack: &ObligationStack<'o, 'tcx>,
 835                             candidate: &Candidate<'tcx>)
 836                             -> EvaluationResult<'tcx>
 837     {
 838         debug!("winnow_candidate: candidate={}", candidate.repr(self.tcx()));
 839         self.infcx.probe(|| {
 840             let candidate = (*candidate).clone();
 841             match self.confirm_candidate(stack.obligation, candidate) {
 842                 Ok(selection) => self.winnow_selection(Some(stack), selection),
 843                 Err(error) => EvaluatedToErr(error),
 844             }
 845         })
 846     }
 847
 848     fn winnow_selection<'o>(&mut self,
 849                             stack: Option<&ObligationStack<'o, 'tcx>>,
 850                             selection: Selection<'tcx>)
 851                             -> EvaluationResult<'tcx>
 852     {
 853         let mut result = EvaluatedToOk;
 854         for obligation in selection.iter_nested() {
 855             match self.evaluate_obligation_recursively(stack, obligation) {
 856                 EvaluatedToErr(e) => { return EvaluatedToErr(e); }
 857                 EvaluatedToAmbig => { result = EvaluatedToAmbig; }
 858                 EvaluatedToOk => { }
 859             }
 860         }
 861         result
 862     }
 863
 864     /// Returns true if `candidate_i` should be dropped in favor of `candidate_j`.
 865     ///
 866     /// This is generally true if either:
 867     /// - candidate i and candidate j are equivalent; or,
 868     /// - candidate i is a conrete impl and candidate j is a where clause bound,
 869     ///   and the concrete impl is applicable to the types in the where clause bound.
 870     ///
 871     /// The last case refers to cases where there are blanket impls (often conditional
 872     /// blanket impls) as well as a where clause. This can come down to one of two cases:
 873     ///
 874     /// - The impl is truly unconditional (it has no where clauses
 875     ///   of its own), in which case the where clause is
 876     ///   unnecessary, because coherence requires that we would
 877     ///   pick that particular impl anyhow (at least so long as we
 878     ///   don't have specialization).
 879     ///
 880     /// - The impl is conditional, in which case we may not have winnowed it out
 881     ///   because we don't know if the conditions apply, but the where clause is basically
 882     ///   telling us taht there is some impl, though not necessarily the one we see.
 883     ///
 884     /// In both cases we prefer to take the where clause, which is
 885     /// essentially harmless.  See issue #18453 for more details of
 886     /// a case where doing the opposite caused us harm.
 887     fn candidate_should_be_dropped_in_favor_of<'o>(&mut self,
 888                                                    stack: &ObligationStack<'o, 'tcx>,
 889                                                    candidate_i: &Candidate<'tcx>,
 890                                                    candidate_j: &Candidate<'tcx>)
 891                                                    -> bool
 892     {
 893         match (candidate_i, candidate_j) {
 894             (&ImplCandidate(impl_def_id), &ParamCandidate(ref vt)) => {
 895                 debug!("Considering whether to drop param {} in favor of impl {}",
 896                        candidate_i.repr(self.tcx()),
 897                        candidate_j.repr(self.tcx()));
 898
 899                 self.infcx.probe(|| {
 900                     let impl_substs =
 901                         self.rematch_impl(impl_def_id, stack.obligation);
 902                     let impl_trait_ref =
 903                         ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
 904                     let impl_trait_ref =
 905                         impl_trait_ref.subst(self.tcx(), &impl_substs);
 906                     let origin =
 907                         infer::RelateOutputImplTypes(stack.obligation.cause.span);
 908                     self.infcx
 909                         .sub_trait_refs(false, origin,
 910                                         impl_trait_ref, vt.bound.clone())
 911                         .is_ok()
 912                 })
 913             }
 914             _ => {
 915                 *candidate_i == *candidate_j
 916             }
 917         }
 918     }
 919
 920     ///////////////////////////////////////////////////////////////////////////
 921     // BUILTIN BOUNDS
 922     //
 923     // These cover the traits that are built-in to the language
 924     // itself.  This includes `Copy` and `Sized` for sure. For the
 925     // moment, it also includes `Send` / `Sync` and a few others, but
 926     // those will hopefully change to library-defined traits in the
 927     // future.
 928
 929     fn assemble_builtin_bound_candidates<'o>(&mut self,
 930                                              bound: ty::BuiltinBound,
 931                                              stack: &ObligationStack<'o, 'tcx>,
 932                                              candidates: &mut CandidateSet<'tcx>)
 933                                              -> Result<(),SelectionError<'tcx>>
 934     {
 935         match self.builtin_bound(bound, stack.obligation.self_ty()) {
 936             Ok(If(_)) => {
 937                 debug!("builtin_bound: bound={}",
 938                        bound.repr(self.tcx()));
 939                 candidates.vec.push(BuiltinCandidate(bound));
 940                 Ok(())
 941             }
 942             Ok(ParameterBuiltin) => { Ok(()) }
 943             Ok(AmbiguousBuiltin) => { Ok(candidates.ambiguous = true) }
 944             Err(e) => { Err(e) }
 945         }
 946     }
 947
 948     fn builtin_bound(&mut self,
 949                      bound: ty::BuiltinBound,
 950                      self_ty: Ty<'tcx>)
 951                      -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
 952     {
 953         let self_ty = self.infcx.shallow_resolve(self_ty);
 954         return match self_ty.sty {
 955             ty::ty_infer(ty::IntVar(_)) |
 956             ty::ty_infer(ty::FloatVar(_)) |
 957             ty::ty_uint(_) |
 958             ty::ty_int(_) |
 959             ty::ty_bool |
 960             ty::ty_float(_) |
 961             ty::ty_bare_fn(_) |
 962             ty::ty_char => {
 963                 // safe for everything
 964                 Ok(If(Vec::new()))
 965             }
 966
 967             ty::ty_uniq(referent_ty) => {  // Box<T>
 968                 match bound {
 969                     ty::BoundCopy => {
 970                         Err(Unimplemented)
 971                     }
 972
 973                     ty::BoundSized => {
 974                         Ok(If(Vec::new()))
 975                     }
 976
 977                     ty::BoundSync |
 978                     ty::BoundSend => {
 979                         Ok(If(vec![referent_ty]))
 980                     }
 981                 }
 982             }
 983
 984             ty::ty_ptr(ty::mt { ty: referent_ty, .. }) => {     // *const T, *mut T
 985                 match bound {
 986                     ty::BoundCopy |
 987                     ty::BoundSized => {
 988                         Ok(If(Vec::new()))
 989                     }
 990
 991                     ty::BoundSync |
 992                     ty::BoundSend => {
 993                         Ok(If(vec![referent_ty]))
 994                     }
 995                 }
 996             }
 997
 998             ty::ty_closure(ref c) => {
 999                 match c.store {
1000                     ty::UniqTraitStore => {
1001                         // proc: Equivalent to `Box<FnOnce>`
1002                         match bound {
1003                             ty::BoundCopy => {
1004                                 Err(Unimplemented)
1005                             }
1006
1007                             ty::BoundSized => {
1008                                 Ok(If(Vec::new()))
1009                             }
1010
1011                             ty::BoundSync |
1012                             ty::BoundSend => {
1013                                 if c.bounds.builtin_bounds.contains(&bound) {
1014                                     Ok(If(Vec::new()))
1015                                 } else {
1016                                     Err(Unimplemented)
1017                                 }
1018                             }
1019                         }
1020                     }
1021                     ty::RegionTraitStore(_, mutbl) => {
1022                         // ||: Equivalent to `&FnMut` or `&mut FnMut` or something like that.
1023                         match bound {
1024                             ty::BoundCopy => {
1025                                 match mutbl {
1026                                     ast::MutMutable => Err(Unimplemented),  // &mut T is affine
1027                                     ast::MutImmutable => Ok(If(Vec::new())),  // &T is copyable
1028                                 }
1029                             }
1030
1031                             ty::BoundSized => {
1032                                 Ok(If(Vec::new()))
1033                             }
1034
1035                             ty::BoundSync |
1036                             ty::BoundSend => {
1037                                 if c.bounds.builtin_bounds.contains(&bound) {
1038                                     Ok(If(Vec::new()))
1039                                 } else {
1040                                     Err(Unimplemented)
1041                                 }
1042                             }
1043                         }
1044                     }
1045                 }
1046             }
1047
1048             ty::ty_trait(box ty::TyTrait { ref principal, bounds }) => {
1049                 match bound {
1050                     ty::BoundSized => {
1051                         Err(Unimplemented)
1052                     }
1053                     ty::BoundCopy | ty::BoundSync | ty::BoundSend => {
1054                         if bounds.builtin_bounds.contains(&bound) {
1055                             Ok(If(Vec::new()))
1056                         } else {
1057                             // Recursively check all supertraits to find out if any further
1058                             // bounds are required and thus we must fulfill.
1059                             // We have to create a temp trait ref here since TyTraits don't
1060                             // have actual self type info (which is required for the
1061                             // supertraits iterator).
1062                             let tmp_tr = Rc::new(ty::TraitRef {
1063                                 def_id: principal.def_id,
1064                                 substs: principal.substs.with_self_ty(ty::mk_err())
1065                             });
1066                             for tr in util::supertraits(self.tcx(), tmp_tr) {
1067                                 let td = ty::lookup_trait_def(self.tcx(), tr.def_id);
1068
1069                                 if td.bounds.builtin_bounds.contains(&bound) {
1070                                     return Ok(If(Vec::new()))
1071                                 }
1072                             }
1073
1074                             Err(Unimplemented)
1075                         }
1076                     }
1077                 }
1078             }
1079
1080             ty::ty_rptr(_, ty::mt { ty: referent_ty, mutbl }) => {
1081                 // &mut T or &T
1082                 match bound {
1083                     ty::BoundCopy => {
1084                         match mutbl {
1085                             // &mut T is affine and hence never `Copy`
1086                             ast::MutMutable => Err(Unimplemented),
1087
1088                             // &T is always copyable
1089                             ast::MutImmutable => Ok(If(Vec::new())),
1090                         }
1091                     }
1092
1093                     ty::BoundSized => {
1094                         Ok(If(Vec::new()))
1095                     }
1096
1097                     ty::BoundSync |
1098                     ty::BoundSend => {
1099                         // Note: technically, a region pointer is only
1100                         // sendable if it has lifetime
1101                         // `'static`. However, we don't take regions
1102                         // into account when doing trait matching:
1103                         // instead, when we decide that `T : Send`, we
1104                         // will register a separate constraint with
1105                         // the region inferencer that `T : 'static`
1106                         // holds as well (because the trait `Send`
1107                         // requires it). This will ensure that there
1108                         // is no borrowed data in `T` (or else report
1109                         // an inference error). The reason we do it
1110                         // this way is that we do not yet *know* what
1111                         // lifetime the borrowed reference has, since
1112                         // we haven't finished running inference -- in
1113                         // other words, there's a kind of
1114                         // chicken-and-egg problem.
1115                         Ok(If(vec![referent_ty]))
1116                     }
1117                 }
1118             }
1119
1120             ty::ty_vec(element_ty, ref len) => {
1121                 // [T, ..n] and [T]
1122                 match bound {
1123                     ty::BoundCopy => {
1124                         match *len {
1125                             Some(_) => Ok(If(vec![element_ty])), // [T, ..n] is copy iff T is copy
1126                             None => Err(Unimplemented), // [T] is unsized and hence affine
1127                         }
1128                     }
1129
1130                     ty::BoundSized => {
1131                         if len.is_some() {
1132                             Ok(If(Vec::new()))
1133                         } else {
1134                             Err(Unimplemented)
1135                         }
1136                     }
1137
1138                     ty::BoundSync |
1139                     ty::BoundSend => {
1140                         Ok(If(vec![element_ty]))
1141                     }
1142                 }
1143             }
1144
1145             ty::ty_str => {
1146                 // Equivalent to [u8]
1147                 match bound {
1148                     ty::BoundSync |
1149                     ty::BoundSend => {
1150                         Ok(If(Vec::new()))
1151                     }
1152
1153                     ty::BoundCopy |
1154                     ty::BoundSized => {
1155                         Err(Unimplemented)
1156                     }
1157                 }
1158             }
1159
1160             ty::ty_tup(ref tys) => {
1161                 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1162                 Ok(If(tys.clone()))
1163             }
1164
1165             ty::ty_unboxed_closure(def_id, _, ref substs) => {
1166                 // FIXME -- This case is tricky. In the case of by-ref
1167                 // closures particularly, we need the results of
1168                 // inference to decide how to reflect the type of each
1169                 // upvar (the upvar may have type `T`, but the runtime
1170                 // type could be `&mut`, `&`, or just `T`). For now,
1171                 // though, we'll do this unsoundly and assume that all
1172                 // captures are by value. Really what we ought to do
1173                 // is reserve judgement and then intertwine this
1174                 // analysis with closure inference.
1175                 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
1176                 match self.tcx().freevars.borrow().get(&def_id.node) {
1177                     None => {
1178                         // No upvars.
1179                         Ok(If(Vec::new()))
1180                     }
1181
1182                     Some(freevars) => {
1183                         let tys: Vec<Ty> =
1184                             freevars
1185                             .iter()
1186                             .map(|freevar| {
1187                                 let freevar_def_id = freevar.def.def_id();
1188                                 self.typer.node_ty(freevar_def_id.node)
1189                                     .unwrap_or(ty::mk_err()).subst(self.tcx(), substs)
1190                             })
1191                             .collect();
1192                         Ok(If(tys))
1193                     }
1194                 }
1195             }
1196
1197             ty::ty_struct(def_id, ref substs) => {
1198                 let types: Vec<Ty> =
1199                     ty::struct_fields(self.tcx(), def_id, substs)
1200                     .iter()
1201                     .map(|f| f.mt.ty)
1202                     .collect();
1203                 nominal(self, bound, def_id, types)
1204             }
1205
1206             ty::ty_enum(def_id, ref substs) => {
1207                 let types: Vec<Ty> =
1208                     ty::substd_enum_variants(self.tcx(), def_id, substs)
1209                     .iter()
1210                     .flat_map(|variant| variant.args.iter())
1211                     .map(|&ty| ty)
1212                     .collect();
1213                 nominal(self, bound, def_id, types)
1214             }
1215
1216             ty::ty_param(_) => {
1217                 // Note: A type parameter is only considered to meet a
1218                 // particular bound if there is a where clause telling
1219                 // us that it does, and that case is handled by
1220                 // `assemble_candidates_from_caller_bounds()`.
1221                 Ok(ParameterBuiltin)
1222             }
1223
1224             ty::ty_infer(ty::TyVar(_)) => {
1225                 // Unbound type variable. Might or might not have
1226                 // applicable impls and so forth, depending on what
1227                 // those type variables wind up being bound to.
1228                 Ok(AmbiguousBuiltin)
1229             }
1230
1231             ty::ty_err => {
1232                 Ok(If(Vec::new()))
1233             }
1234
1235             ty::ty_open(_) |
1236             ty::ty_infer(ty::SkolemizedTy(_)) |
1237             ty::ty_infer(ty::SkolemizedIntTy(_)) => {
1238                 self.tcx().sess.bug(
1239                     format!(
1240                         "asked to assemble builtin bounds of unexpected type: {}",
1241                         self_ty.repr(self.tcx())).as_slice());
1242             }
1243         };
1244
1245         fn nominal<'cx, 'tcx>(this: &mut SelectionContext<'cx, 'tcx>,
1246                               bound: ty::BuiltinBound,
1247                               def_id: ast::DefId,
1248                               types: Vec<Ty<'tcx>>)
1249                               -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1250         {
1251             // First check for markers and other nonsense.
1252             let tcx = this.tcx();
1253             match bound {
1254                 ty::BoundSend => {
1255                     if
1256                         Some(def_id) == tcx.lang_items.no_send_bound() ||
1257                         Some(def_id) == tcx.lang_items.managed_bound()
1258                     {
1259                         return Err(Unimplemented);
1260                     }
1261                 }
1262
1263                 ty::BoundCopy => {
1264                     // This is an Opt-In Built-In Trait. So, unless
1265                     // the user is asking for the old behavior, we
1266                     // don't supply any form of builtin impl.
1267                     if !this.tcx().sess.features.borrow().opt_out_copy {
1268                         return Ok(ParameterBuiltin)
1269                     }
1270                 }
1271
1272                 ty::BoundSync => {
1273                     if
1274                         Some(def_id) == tcx.lang_items.no_sync_bound() ||
1275                         Some(def_id) == tcx.lang_items.managed_bound()
1276                     {
1277                         return Err(Unimplemented);
1278                     } else if
1279                         Some(def_id) == tcx.lang_items.unsafe_type()
1280                     {
1281                         // FIXME(#13231) -- we currently consider `UnsafeCell<T>`
1282                         // to always be sync. This is allow for types like `Queue`
1283                         // and `Mutex`, where `Queue<T> : Sync` is `T : Send`.
1284                         return Ok(If(Vec::new()));
1285                     }
1286                 }
1287
1288                 ty::BoundSized => { }
1289             }
1290
1291             Ok(If(types))
1292         }
1293     }
1294
1295     ///////////////////////////////////////////////////////////////////////////
1296     // CONFIRMATION
1297     //
1298     // Confirmation unifies the output type parameters of the trait
1299     // with the values found in the obligation, possibly yielding a
1300     // type error.  See `doc.rs` for more details.
1301
1302     fn confirm_candidate(&mut self,
1303                          obligation: &Obligation<'tcx>,
1304                          candidate: Candidate<'tcx>)
1305                          -> Result<Selection<'tcx>,SelectionError<'tcx>>
1306     {
1307         debug!("confirm_candidate({}, {})",
1308                obligation.repr(self.tcx()),
1309                candidate.repr(self.tcx()));
1310
1311         match candidate {
1312             BuiltinCandidate(builtin_bound) => {
1313                 Ok(VtableBuiltin(
1314                     try!(self.confirm_builtin_candidate(obligation, builtin_bound))))
1315             }
1316
1317             ErrorCandidate => {
1318                 Ok(VtableBuiltin(VtableBuiltinData { nested: VecPerParamSpace::empty() }))
1319             }
1320
1321             ParamCandidate(param) => {
1322                 Ok(VtableParam(
1323                     try!(self.confirm_param_candidate(obligation, param))))
1324             }
1325
1326             ImplCandidate(impl_def_id) => {
1327                 let vtable_impl =
1328                     try!(self.confirm_impl_candidate(obligation, impl_def_id));
1329                 Ok(VtableImpl(vtable_impl))
1330             }
1331
1332             UnboxedClosureCandidate(closure_def_id, substs) => {
1333                 try!(self.confirm_unboxed_closure_candidate(obligation, closure_def_id, &substs));
1334                 Ok(VtableUnboxedClosure(closure_def_id, substs))
1335             }
1336
1337             FnPointerCandidate => {
1338                 let fn_type =
1339                     try!(self.confirm_fn_pointer_candidate(obligation));
1340                 Ok(VtableFnPointer(fn_type))
1341             }
1342         }
1343     }
1344
1345     fn confirm_param_candidate(&mut self,
1346                                obligation: &Obligation<'tcx>,
1347                                param: VtableParamData<'tcx>)
1348                                -> Result<VtableParamData<'tcx>,
1349                                          SelectionError<'tcx>>
1350     {
1351         debug!("confirm_param_candidate({},{})",
1352                obligation.repr(self.tcx()),
1353                param.repr(self.tcx()));
1354
1355         let () = try!(self.confirm(obligation.cause,
1356                                    obligation.trait_ref.clone(),
1357                                    param.bound.clone()));
1358         Ok(param)
1359     }
1360
1361     fn confirm_builtin_candidate(&mut self,
1362                                  obligation: &Obligation<'tcx>,
1363                                  bound: ty::BuiltinBound)
1364                                  -> Result<VtableBuiltinData<Obligation<'tcx>>,
1365                                            SelectionError<'tcx>>
1366     {
1367         debug!("confirm_builtin_candidate({})",
1368                obligation.repr(self.tcx()));
1369
1370         match try!(self.builtin_bound(bound, obligation.self_ty())) {
1371             If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)),
1372             AmbiguousBuiltin | ParameterBuiltin => {
1373                 self.tcx().sess.span_bug(
1374                     obligation.cause.span,
1375                     format!("builtin bound for {} was ambig",
1376                             obligation.repr(self.tcx())).as_slice());
1377             }
1378         }
1379     }
1380
1381     fn vtable_builtin_data(&mut self,
1382                            obligation: &Obligation<'tcx>,
1383                            bound: ty::BuiltinBound,
1384                            nested: Vec<Ty<'tcx>>)
1385                            -> VtableBuiltinData<Obligation<'tcx>>
1386     {
1387         let obligations = nested.iter().map(|&t| {
1388             util::obligation_for_builtin_bound(
1389                 self.tcx(),
1390                 obligation.cause,
1391                 bound,
1392                 obligation.recursion_depth + 1,
1393                 t)
1394         }).collect::<Result<_, _>>();
1395         let obligations = match obligations {
1396             Ok(o) => o,
1397             Err(ErrorReported) => Vec::new()
1398         };
1399         let obligations = VecPerParamSpace::new(obligations, Vec::new(),
1400                                                 Vec::new(), Vec::new());
1401         VtableBuiltinData { nested: obligations }
1402     }
1403
1404     fn confirm_impl_candidate(&mut self,
1405                               obligation: &Obligation<'tcx>,
1406                               impl_def_id: ast::DefId)
1407                               -> Result<VtableImplData<'tcx, Obligation<'tcx>>,
1408                                         SelectionError<'tcx>>
1409     {
1410         debug!("confirm_impl_candidate({},{})",
1411                obligation.repr(self.tcx()),
1412                impl_def_id.repr(self.tcx()));
1413
1414         // First, create the substitutions by matching the impl again,
1415         // this time not in a probe.
1416         let substs = self.rematch_impl(impl_def_id, obligation);
1417         Ok(self.vtable_impl(impl_def_id, substs, obligation.cause, obligation.recursion_depth + 1))
1418     }
1419
1420     fn vtable_impl(&mut self,
1421                    impl_def_id: ast::DefId,
1422                    substs: Substs<'tcx>,
1423                    cause: ObligationCause<'tcx>,
1424                    recursion_depth: uint)
1425                    -> VtableImplData<'tcx, Obligation<'tcx>>
1426     {
1427         let impl_obligations =
1428             self.impl_obligations(cause,
1429                                   recursion_depth,
1430                                   impl_def_id,
1431                                   &substs);
1432         VtableImplData { impl_def_id: impl_def_id,
1433                          substs: substs,
1434                          nested: impl_obligations }
1435     }
1436
1437     fn confirm_fn_pointer_candidate(&mut self,
1438                                     obligation: &Obligation<'tcx>)
1439                                     -> Result<ty::Ty<'tcx>,SelectionError<'tcx>>
1440     {
1441         debug!("confirm_fn_pointer_candidate({})",
1442                obligation.repr(self.tcx()));
1443
1444         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1445         let sig = match self_ty.sty {
1446             ty::ty_bare_fn(ty::BareFnTy {
1447                 fn_style: ast::NormalFn,
1448                 abi: abi::Rust,
1449                 ref sig
1450             }) => {
1451                 sig
1452             }
1453             _ => {
1454                 self.tcx().sess.span_bug(
1455                     obligation.cause.span,
1456                     format!("Fn pointer candidate for inappropriate self type: {}",
1457                             self_ty.repr(self.tcx())).as_slice());
1458             }
1459         };
1460
1461         let arguments_tuple = ty::mk_tup(self.tcx(), sig.inputs.to_vec());
1462         let output_type = sig.output.unwrap();
1463         let substs =
1464             Substs::new_trait(
1465                 vec![arguments_tuple, output_type],
1466                 vec![],
1467                 vec![],
1468                 self_ty);
1469         let trait_ref = Rc::new(ty::TraitRef {
1470             def_id: obligation.trait_ref.def_id,
1471             substs: substs,
1472         });
1473
1474         let () =
1475             try!(self.confirm(obligation.cause,
1476                               obligation.trait_ref.clone(),
1477                               trait_ref));
1478
1479         Ok(self_ty)
1480     }
1481
1482     fn confirm_unboxed_closure_candidate(&mut self,
1483                                          obligation: &Obligation<'tcx>,
1484                                          closure_def_id: ast::DefId,
1485                                          substs: &Substs<'tcx>)
1486                                          -> Result<(),SelectionError<'tcx>>
1487     {
1488         debug!("confirm_unboxed_closure_candidate({},{},{})",
1489                obligation.repr(self.tcx()),
1490                closure_def_id.repr(self.tcx()),
1491                substs.repr(self.tcx()));
1492
1493         let closure_type = match self.typer.unboxed_closures().borrow().get(&closure_def_id) {
1494             Some(closure) => closure.closure_type.clone(),
1495             None => {
1496                 self.tcx().sess.span_bug(
1497                     obligation.cause.span,
1498                     format!("No entry for unboxed closure: {}",
1499                             closure_def_id.repr(self.tcx())).as_slice());
1500             }
1501         };
1502
1503         let closure_sig = &closure_type.sig;
1504         let arguments_tuple = closure_sig.inputs[0];
1505         let substs =
1506             Substs::new_trait(
1507                 vec![arguments_tuple.subst(self.tcx(), substs),
1508                      closure_sig.output.unwrap().subst(self.tcx(), substs)],
1509                 vec![],
1510                 vec![],
1511                 obligation.self_ty());
1512         let trait_ref = Rc::new(ty::TraitRef {
1513             def_id: obligation.trait_ref.def_id,
1514             substs: substs,
1515         });
1516
1517         self.confirm(obligation.cause,
1518                      obligation.trait_ref.clone(),
1519                      trait_ref)
1520     }
1521
1522     ///////////////////////////////////////////////////////////////////////////
1523     // Matching
1524     //
1525     // Matching is a common path used for both evaluation and
1526     // confirmation.  It basically unifies types that appear in impls
1527     // and traits. This does affect the surrounding environment;
1528     // therefore, when used during evaluation, match routines must be
1529     // run inside of a `probe()` so that their side-effects are
1530     // contained.
1531
1532     fn rematch_impl(&mut self,
1533                     impl_def_id: ast::DefId,
1534                     obligation: &Obligation<'tcx>)
1535                     -> Substs<'tcx>
1536     {
1537         match self.match_impl(impl_def_id, obligation) {
1538             Ok(substs) => {
1539                 substs
1540             }
1541             Err(()) => {
1542                 self.tcx().sess.bug(
1543                     format!("Impl {} was matchable against {} but now is not",
1544                             impl_def_id.repr(self.tcx()),
1545                             obligation.repr(self.tcx()))
1546                         .as_slice());
1547             }
1548         }
1549     }
1550
1551     fn match_impl(&mut self,
1552                   impl_def_id: ast::DefId,
1553                   obligation: &Obligation<'tcx>)
1554                   -> Result<Substs<'tcx>, ()>
1555     {
1556         let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
1557                                                 impl_def_id).unwrap();
1558
1559         // Before we create the substitutions and everything, first
1560         // consider a "quick reject". This avoids creating more types
1561         // and so forth that we need to.
1562         if self.fast_reject_trait_refs(obligation, &*impl_trait_ref) {
1563             return Err(());
1564         }
1565
1566         let impl_substs = util::fresh_substs_for_impl(self.infcx,
1567                                                       obligation.cause.span,
1568                                                       impl_def_id);
1569
1570         let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
1571                                                   &impl_substs);
1572
1573         match self.match_trait_refs(obligation, impl_trait_ref) {
1574             Ok(()) => Ok(impl_substs),
1575             Err(()) => Err(())
1576         }
1577     }
1578
1579     fn fast_reject_trait_refs(&mut self,
1580                               obligation: &Obligation,
1581                               impl_trait_ref: &ty::TraitRef)
1582                               -> bool
1583     {
1584         // We can avoid creating type variables and doing the full
1585         // substitution if we find that any of the input types, when
1586         // simplified, do not match.
1587
1588         obligation.trait_ref.input_types().iter()
1589             .zip(impl_trait_ref.input_types().iter())
1590             .any(|(&obligation_ty, &impl_ty)| {
1591                 let simplified_obligation_ty =
1592                     fast_reject::simplify_type(self.tcx(), obligation_ty, true);
1593                 let simplified_impl_ty =
1594                     fast_reject::simplify_type(self.tcx(), impl_ty, false);
1595
1596                 simplified_obligation_ty.is_some() &&
1597                     simplified_impl_ty.is_some() &&
1598                     simplified_obligation_ty != simplified_impl_ty
1599             })
1600     }
1601
1602     fn match_trait_refs(&mut self,
1603                         obligation: &Obligation<'tcx>,
1604                         trait_ref: Rc<ty::TraitRef<'tcx>>)
1605                         -> Result<(),()>
1606     {
1607         debug!("match_trait_refs: obligation={} trait_ref={}",
1608                obligation.repr(self.tcx()),
1609                trait_ref.repr(self.tcx()));
1610
1611         let origin = infer::RelateOutputImplTypes(obligation.cause.span);
1612         match self.infcx.sub_trait_refs(false,
1613                                         origin,
1614                                         trait_ref,
1615                                         obligation.trait_ref.clone()) {
1616             Ok(()) => Ok(()),
1617             Err(_) => Err(()),
1618         }
1619     }
1620
1621     /// Determines whether the self type declared against
1622     /// `impl_def_id` matches `obligation_self_ty`. If successful,
1623     /// returns the substitutions used to make them match. See
1624     /// `match_impl()`. For example, if `impl_def_id` is declared
1625     /// as:
1626     ///
1627     ///    impl<T:Copy> Foo for ~T { ... }
1628     ///
1629     /// and `obligation_self_ty` is `int`, we'd back an `Err(_)`
1630     /// result. But if `obligation_self_ty` were `~int`, we'd get
1631     /// back `Ok(T=int)`.
1632     fn match_inherent_impl(&mut self,
1633                            impl_def_id: ast::DefId,
1634                            obligation_cause: ObligationCause,
1635                            obligation_self_ty: Ty<'tcx>)
1636                            -> Result<Substs<'tcx>,()>
1637     {
1638         // Create fresh type variables for each type parameter declared
1639         // on the impl etc.
1640         let impl_substs = util::fresh_substs_for_impl(self.infcx,
1641                                                       obligation_cause.span,
1642                                                       impl_def_id);
1643
1644         // Find the self type for the impl.
1645         let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty;
1646         let impl_self_ty = impl_self_ty.subst(self.tcx(), &impl_substs);
1647
1648         debug!("match_impl_self_types(obligation_self_ty={}, impl_self_ty={})",
1649                obligation_self_ty.repr(self.tcx()),
1650                impl_self_ty.repr(self.tcx()));
1651
1652         match self.match_self_types(obligation_cause,
1653                                     impl_self_ty,
1654                                     obligation_self_ty) {
1655             Ok(()) => {
1656                 debug!("Matched impl_substs={}", impl_substs.repr(self.tcx()));
1657                 Ok(impl_substs)
1658             }
1659             Err(()) => {
1660                 debug!("NoMatch");
1661                 Err(())
1662             }
1663         }
1664     }
1665
1666     fn match_self_types(&mut self,
1667                         cause: ObligationCause,
1668
1669                         // The self type provided by the impl/caller-obligation:
1670                         provided_self_ty: Ty<'tcx>,
1671
1672                         // The self type the obligation is for:
1673                         required_self_ty: Ty<'tcx>)
1674                         -> Result<(),()>
1675     {
1676         // FIXME(#5781) -- equating the types is stronger than
1677         // necessary. Should consider variance of trait w/r/t Self.
1678
1679         let origin = infer::RelateSelfType(cause.span);
1680         match self.infcx.eq_types(false,
1681                                   origin,
1682                                   provided_self_ty,
1683                                   required_self_ty) {
1684             Ok(()) => Ok(()),
1685             Err(_) => Err(()),
1686         }
1687     }
1688
1689     ///////////////////////////////////////////////////////////////////////////
1690     // Confirmation
1691     //
1692     // The final step of selection: once we know how an obligation is
1693     // is resolved, we confirm that selection in order to have
1694     // side-effects on the typing environment. This step also unifies
1695     // the output type parameters from the obligation with those found
1696     // on the impl/bound, which may yield type errors.
1697
1698     /// Relates the output type parameters from an impl to the
1699     /// trait.  This may lead to type errors. The confirmation step
1700     /// is separated from the main match procedure because these
1701     /// type errors do not cause us to select another impl.
1702     ///
1703     /// As an example, consider matching the obligation
1704     /// `Iterator<char> for Elems<int>` using the following impl:
1705     ///
1706     ///    impl<T> Iterator<T> for Elems<T> { ... }
1707     ///
1708     /// The match phase will succeed with substitution `T=int`.
1709     /// The confirm step will then try to unify `int` and `char`
1710     /// and yield an error.
1711     fn confirm_impl_vtable(&mut self,
1712                            impl_def_id: ast::DefId,
1713                            obligation_cause: ObligationCause<'tcx>,
1714                            obligation_trait_ref: Rc<ty::TraitRef<'tcx>>,
1715                            substs: &Substs<'tcx>)
1716                            -> Result<(), SelectionError<'tcx>>
1717     {
1718         let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
1719                                                 impl_def_id).unwrap();
1720         let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
1721                                                   substs);
1722         self.confirm(obligation_cause, obligation_trait_ref, impl_trait_ref)
1723     }
1724
1725     /// After we have determined which impl applies, and with what substitutions, there is one last
1726     /// step. We have to go back and relate the "output" type parameters from the obligation to the
1727     /// types that are specified in the impl.
1728     ///
1729     /// For example, imagine we have:
1730     ///
1731     ///     impl<T> Iterator<T> for Vec<T> { ... }
1732     ///
1733     /// and our obligation is `Iterator<Foo> for Vec<int>` (note the mismatch in the obligation
1734     /// types). Up until this step, no error would be reported: the self type is `Vec<int>`, and
1735     /// that matches `Vec<T>` with the substitution `T=int`. At this stage, we could then go and
1736     /// check that the type parameters to the `Iterator` trait match. (In terms of the parameters,
1737     /// the `expected_trait_ref` here would be `Iterator<int> for Vec<int>`, and the
1738     /// `obligation_trait_ref` would be `Iterator<Foo> for Vec<int>`.
1739     ///
1740     /// Note that this checking occurs *after* the impl has selected, because these output type
1741     /// parameters should not affect the selection of the impl. Therefore, if there is a mismatch,
1742     /// we report an error to the user.
1743     fn confirm(&mut self,
1744                obligation_cause: ObligationCause,
1745                obligation_trait_ref: Rc<ty::TraitRef<'tcx>>,
1746                expected_trait_ref: Rc<ty::TraitRef<'tcx>>)
1747                -> Result<(), SelectionError<'tcx>>
1748     {
1749         let origin = infer::RelateOutputImplTypes(obligation_cause.span);
1750
1751         let obligation_trait_ref = obligation_trait_ref.clone();
1752         match self.infcx.sub_trait_refs(false,
1753                                         origin,
1754                                         expected_trait_ref.clone(),
1755                                         obligation_trait_ref) {
1756             Ok(()) => Ok(()),
1757             Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, e))
1758         }
1759     }
1760
1761     ///////////////////////////////////////////////////////////////////////////
1762     // Miscellany
1763
1764     fn push_stack<'o,'s:'o>(&mut self,
1765                             previous_stack: Option<&'s ObligationStack<'s, 'tcx>>,
1766                             obligation: &'o Obligation<'tcx>)
1767                             -> ObligationStack<'o, 'tcx>
1768     {
1769         let skol_trait_ref = obligation.trait_ref.fold_with(&mut self.skolemizer);
1770
1771         ObligationStack {
1772             obligation: obligation,
1773             skol_trait_ref: skol_trait_ref,
1774             previous: previous_stack.map(|p| p), // FIXME variance
1775         }
1776     }
1777
1778     /// Returns set of all impls for a given trait.
1779     fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
1780         ty::populate_implementations_for_trait_if_necessary(self.tcx(),
1781                                                             trait_def_id);
1782         match self.tcx().trait_impls.borrow().get(&trait_def_id) {
1783             None => Vec::new(),
1784             Some(impls) => impls.borrow().clone()
1785         }
1786     }
1787
1788     fn impl_obligations(&self,
1789                         cause: ObligationCause<'tcx>,
1790                         recursion_depth: uint,
1791                         impl_def_id: ast::DefId,
1792                         impl_substs: &Substs<'tcx>)
1793                         -> VecPerParamSpace<Obligation<'tcx>>
1794     {
1795         let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
1796         let bounds = impl_generics.to_bounds(self.tcx(), impl_substs);
1797         util::obligations_for_generics(self.tcx(), cause, recursion_depth,
1798                                        &bounds, &impl_substs.types)
1799     }
1800
1801     fn fn_family_trait_kind(&self,
1802                             trait_def_id: ast::DefId)
1803                             -> Option<ty::UnboxedClosureKind>
1804     {
1805         let tcx = self.tcx();
1806         if Some(trait_def_id) == tcx.lang_items.fn_trait() {
1807             Some(ty::FnUnboxedClosureKind)
1808         } else if Some(trait_def_id) == tcx.lang_items.fn_mut_trait() {
1809             Some(ty::FnMutUnboxedClosureKind)
1810         } else if Some(trait_def_id) == tcx.lang_items.fn_once_trait() {
1811             Some(ty::FnOnceUnboxedClosureKind)
1812         } else {
1813             None
1814         }
1815     }
1816 }
1817
1818 impl<'tcx> Repr<'tcx> for Candidate<'tcx> {
1819     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1820         match *self {
1821             ErrorCandidate => format!("ErrorCandidate"),
1822             BuiltinCandidate(b) => format!("BuiltinCandidate({})", b),
1823             UnboxedClosureCandidate(c, ref s) => {
1824                 format!("UnboxedClosureCandidate({},{})", c, s.repr(tcx))
1825             }
1826             FnPointerCandidate => {
1827                 format!("FnPointerCandidate")
1828             }
1829             ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
1830             ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
1831         }
1832     }
1833 }
1834
1835 impl<'tcx> SelectionCache<'tcx> {
1836     pub fn new() -> SelectionCache<'tcx> {
1837         SelectionCache {
1838             hashmap: RefCell::new(HashMap::new())
1839         }
1840     }
1841 }
1842
1843 impl<'o, 'tcx> ObligationStack<'o, 'tcx> {
1844     fn iter(&self) -> Option<&ObligationStack<'o, 'tcx>> {
1845         Some(self)
1846     }
1847 }
1848
1849 impl<'o, 'tcx> Iterator<&'o ObligationStack<'o, 'tcx>> for Option<&'o ObligationStack<'o, 'tcx>> {
1850     fn next(&mut self) -> Option<&'o ObligationStack<'o, 'tcx>> {
1851         match *self {
1852             Some(o) => {
1853                 *self = o.previous;
1854                 Some(o)
1855             }
1856             None => {
1857                 None
1858             }
1859         }
1860     }
1861 }
1862
1863 impl<'o, 'tcx> Repr<'tcx> for ObligationStack<'o, 'tcx> {
1864     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1865         format!("ObligationStack({})",
1866                 self.obligation.repr(tcx))
1867     }
1868 }
1869
1870 impl<'tcx> EvaluationResult<'tcx> {
1871     fn may_apply(&self) -> bool {
1872         match *self {
1873             EvaluatedToOk |
1874             EvaluatedToAmbig |
1875             EvaluatedToErr(Overflow) |
1876             EvaluatedToErr(OutputTypeParameterMismatch(..)) => {
1877                 true
1878             }
1879             EvaluatedToErr(Unimplemented) => {
1880                 false
1881             }
1882         }
1883     }
1884 }
1885
1886 impl MethodMatchResult {
1887     pub fn may_apply(&self) -> bool {
1888         match *self {
1889             MethodMatched(_) => true,
1890             MethodAmbiguous(_) => true,
1891             MethodDidNotMatch => false,
1892         }
1893     }
1894 }