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::SelectionCandidate::*;
  17 use self::BuiltinBoundConditions::*;
  18 use self::EvaluationResult::*;
  19
  20 use super::{DerivedObligationCause};
  21 use super::{project};
  22 use super::project::Normalized;
  23 use super::{PredicateObligation, TraitObligation, ObligationCause};
  24 use super::{ObligationCauseCode, BuiltinDerivedObligation};
  25 use super::{SelectionError, Unimplemented, Overflow, OutputTypeParameterMismatch};
  26 use super::{Selection};
  27 use super::{SelectionResult};
  28 use super::{VtableBuiltin, VtableImpl, VtableParam, VtableClosure,
  29             VtableFnPointer, VtableObject};
  30 use super::{VtableImplData, VtableObjectData, VtableBuiltinData};
  31 use super::object_safety;
  32 use super::{util};
  33
  34 use middle::fast_reject;
  35 use middle::subst::{Subst, Substs, TypeSpace, VecPerParamSpace};
  36 use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty};
  37 use middle::infer;
  38 use middle::infer::{InferCtxt, TypeFreshener};
  39 use middle::ty_fold::TypeFoldable;
  40 use std::cell::RefCell;
  41 use std::collections::hash_map::HashMap;
  42 use std::rc::Rc;
  43 use syntax::{abi, ast};
  44 use util::common::ErrorReported;
  45 use util::ppaux::Repr;
  46
  47 pub struct SelectionContext<'cx, 'tcx:'cx> {
  48     infcx: &'cx InferCtxt<'cx, 'tcx>,
  49     closure_typer: &'cx (ty::ClosureTyper<'tcx>+'cx),
  50
  51     /// Freshener used specifically for skolemizing entries on the
  52     /// obligation stack. This ensures that all entries on the stack
  53     /// at one time will have the same set of skolemized entries,
  54     /// which is important for checking for trait bounds that
  55     /// recursively require themselves.
  56     freshener: TypeFreshener<'cx, 'tcx>,
  57
  58     /// If true, indicates that the evaluation should be conservative
  59     /// and consider the possibility of types outside this crate.
  60     /// This comes up primarily when resolving ambiguity. Imagine
  61     /// there is some trait reference `$0 : Bar` where `$0` is an
  62     /// inference variable. If `intercrate` is true, then we can never
  63     /// say for sure that this reference is not implemented, even if
  64     /// there are *no impls at all for `Bar`*, because `$0` could be
  65     /// bound to some type that in a downstream crate that implements
  66     /// `Bar`. This is the suitable mode for coherence. Elsewhere,
  67     /// though, we set this to false, because we are only interested
  68     /// in types that the user could actually have written --- in
  69     /// other words, we consider `$0 : Bar` to be unimplemented if
  70     /// there is no type that the user could *actually name* that
  71     /// would satisfy it. This avoids crippling inference, basically.
  72     intercrate: bool,
  73 }
  74
  75 // A stack that walks back up the stack frame.
  76 struct TraitObligationStack<'prev, 'tcx: 'prev> {
  77     obligation: &'prev TraitObligation<'tcx>,
  78
  79     /// Trait ref from `obligation` but skolemized with the
  80     /// selection-context's freshener. Used to check for recursion.
  81     fresh_trait_ref: ty::PolyTraitRef<'tcx>,
  82
  83     previous: Option<&'prev TraitObligationStack<'prev, 'tcx>>
  84 }
  85
  86 #[derive(Clone)]
  87 pub struct SelectionCache<'tcx> {
  88     hashmap: RefCell<HashMap<Rc<ty::TraitRef<'tcx>>,
  89                              SelectionResult<'tcx, SelectionCandidate<'tcx>>>>,
  90 }
  91
  92 pub enum MethodMatchResult {
  93     MethodMatched(MethodMatchedData),
  94     MethodAmbiguous(/* list of impls that could apply */ Vec<ast::DefId>),
  95     MethodDidNotMatch,
  96 }
  97
  98 #[derive(Copy, Debug)]
  99 pub enum MethodMatchedData {
 100     // In the case of a precise match, we don't really need to store
 101     // how the match was found. So don't.
 102     PreciseMethodMatch,
 103
 104     // In the case of a coercion, we need to know the precise impl so
 105     // that we can determine the type to which things were coerced.
 106     CoerciveMethodMatch(/* impl we matched */ ast::DefId)
 107 }
 108
 109 /// The selection process begins by considering all impls, where
 110 /// clauses, and so forth that might resolve an obligation.  Sometimes
 111 /// we'll be able to say definitively that (e.g.) an impl does not
 112 /// apply to the obligation: perhaps it is defined for `uint` but the
 113 /// obligation is for `int`. In that case, we drop the impl out of the
 114 /// list.  But the other cases are considered *candidates*.
 115 ///
 116 /// Candidates can either be definitive or ambiguous. An ambiguous
 117 /// candidate is one that might match or might not, depending on how
 118 /// type variables wind up being resolved. This only occurs during inference.
 119 ///
 120 /// For selection to succeed, there must be exactly one non-ambiguous
 121 /// candidate.  Usually, it is not possible to have more than one
 122 /// definitive candidate, due to the coherence rules. However, there is
 123 /// one case where it could occur: if there is a blanket impl for a
 124 /// trait (that is, an impl applied to all T), and a type parameter
 125 /// with a where clause. In that case, we can have a candidate from the
 126 /// where clause and a second candidate from the impl. This is not a
 127 /// problem because coherence guarantees us that the impl which would
 128 /// be used to satisfy the where clause is the same one that we see
 129 /// now. To resolve this issue, therefore, we ignore impls if we find a
 130 /// matching where clause. Part of the reason for this is that where
 131 /// clauses can give additional information (like, the types of output
 132 /// parameters) that would have to be inferred from the impl.
 133 #[derive(PartialEq,Eq,Debug,Clone)]
 134 enum SelectionCandidate<'tcx> {
 135     BuiltinCandidate(ty::BuiltinBound),
 136     ParamCandidate(ty::PolyTraitRef<'tcx>),
 137     ImplCandidate(ast::DefId),
 138
 139     /// This is a trait matching with a projected type as `Self`, and
 140     /// we found an applicable bound in the trait definition.
 141     ProjectionCandidate,
 142
 143     /// Implementation of a `Fn`-family trait by one of the
 144     /// anonymous types generated for a `||` expression.
 145     ClosureCandidate(/* closure */ ast::DefId, Substs<'tcx>),
 146
 147     /// Implementation of a `Fn`-family trait by one of the anonymous
 148     /// types generated for a fn pointer type (e.g., `fn(int)->int`)
 149     FnPointerCandidate,
 150
 151     ObjectCandidate,
 152
 153     ErrorCandidate,
 154 }
 155
 156 struct SelectionCandidateSet<'tcx> {
 157     // a list of candidates that definitely apply to the current
 158     // obligation (meaning: types unify).
 159     vec: Vec<SelectionCandidate<'tcx>>,
 160
 161     // if this is true, then there were candidates that might or might
 162     // not have applied, but we couldn't tell. This occurs when some
 163     // of the input types are type variables, in which case there are
 164     // various "builtin" rules that might or might not trigger.
 165     ambiguous: bool,
 166 }
 167
 168 enum BuiltinBoundConditions<'tcx> {
 169     If(Vec<Ty<'tcx>>),
 170     ParameterBuiltin,
 171     AmbiguousBuiltin
 172 }
 173
 174 #[derive(Debug)]
 175 enum EvaluationResult<'tcx> {
 176     EvaluatedToOk,
 177     EvaluatedToAmbig,
 178     EvaluatedToErr(SelectionError<'tcx>),
 179 }
 180
 181 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 182     pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>,
 183                closure_typer: &'cx ty::ClosureTyper<'tcx>)
 184                -> SelectionContext<'cx, 'tcx> {
 185         SelectionContext {
 186             infcx: infcx,
 187             closure_typer: closure_typer,
 188             freshener: infcx.freshener(),
 189             intercrate: false,
 190         }
 191     }
 192
 193     pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'tcx>,
 194                       closure_typer: &'cx ty::ClosureTyper<'tcx>)
 195                       -> SelectionContext<'cx, 'tcx> {
 196         SelectionContext {
 197             infcx: infcx,
 198             closure_typer: closure_typer,
 199             freshener: infcx.freshener(),
 200             intercrate: true,
 201         }
 202     }
 203
 204     pub fn infcx(&self) -> &'cx InferCtxt<'cx, 'tcx> {
 205         self.infcx
 206     }
 207
 208     pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
 209         self.infcx.tcx
 210     }
 211
 212     pub fn param_env(&self) -> &'cx ty::ParameterEnvironment<'cx, 'tcx> {
 213         self.closure_typer.param_env()
 214     }
 215
 216     pub fn closure_typer(&self) -> &'cx (ty::ClosureTyper<'tcx>+'cx) {
 217         self.closure_typer
 218     }
 219
 220     ///////////////////////////////////////////////////////////////////////////
 221     // Selection
 222     //
 223     // The selection phase tries to identify *how* an obligation will
 224     // be resolved. For example, it will identify which impl or
 225     // parameter bound is to be used. The process can be inconclusive
 226     // if the self type in the obligation is not fully inferred. Selection
 227     // can result in an error in one of two ways:
 228     //
 229     // 1. If no applicable impl or parameter bound can be found.
 230     // 2. If the output type parameters in the obligation do not match
 231     //    those specified by the impl/bound. For example, if the obligation
 232     //    is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
 233     //    `impl<T> Iterable<T> for Vec<T>`, than an error would result.
 234
 235     /// Attempts to satisfy the obligation. If successful, this will affect the surrounding
 236     /// type environment by performing unification.
 237     pub fn select(&mut self, obligation: &TraitObligation<'tcx>)
 238                   -> SelectionResult<'tcx, Selection<'tcx>> {
 239         debug!("select({})", obligation.repr(self.tcx()));
 240         assert!(!obligation.predicate.has_escaping_regions());
 241
 242         let stack = self.push_stack(None, obligation);
 243         match try!(self.candidate_from_obligation(&stack)) {
 244             None => {
 245                 self.consider_unification_despite_ambiguity(obligation);
 246                 Ok(None)
 247             }
 248             Some(candidate) => Ok(Some(try!(self.confirm_candidate(obligation, candidate)))),
 249         }
 250     }
 251
 252     /// In the particular case of unboxed closure obligations, we can
 253     /// sometimes do some amount of unification for the
 254     /// argument/return types even though we can't yet fully match obligation.
 255     /// The particular case we are interesting in is an obligation of the form:
 256     ///
 257     ///    C : FnFoo<A>
 258     ///
 259     /// where `C` is an unboxed closure type and `FnFoo` is one of the
 260     /// `Fn` traits. Because we know that users cannot write impls for closure types
 261     /// themselves, the only way that `C : FnFoo` can fail to match is under two
 262     /// conditions:
 263     ///
 264     /// 1. The closure kind for `C` is not yet known, because inference isn't complete.
 265     /// 2. The closure kind for `C` *is* known, but doesn't match what is needed.
 266     ///    For example, `C` may be a `FnOnce` closure, but a `Fn` closure is needed.
 267     ///
 268     /// In either case, we always know what argument types are
 269     /// expected by `C`, no matter what kind of `Fn` trait it
 270     /// eventually matches. So we can go ahead and unify the argument
 271     /// types, even though the end result is ambiguous.
 272     ///
 273     /// Note that this is safe *even if* the trait would never be
 274     /// matched (case 2 above). After all, in that case, an error will
 275     /// result, so it kind of doesn't matter what we do --- unifying
 276     /// the argument types can only be helpful to the user, because
 277     /// once they patch up the kind of closure that is expected, the
 278     /// argment types won't really change.
 279     fn consider_unification_despite_ambiguity(&mut self, obligation: &TraitObligation<'tcx>) {
 280         // Is this a `C : FnFoo(...)` trait reference for some trait binding `FnFoo`?
 281         match self.tcx().lang_items.fn_trait_kind(obligation.predicate.0.def_id()) {
 282             Some(_) => { }
 283             None => { return; }
 284         }
 285
 286         // Is the self-type a closure type? We ignore bindings here
 287         // because if it is a closure type, it must be a closure type from
 288         // within this current fn, and hence none of the higher-ranked
 289         // lifetimes can appear inside the self-type.
 290         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
 291         let (closure_def_id, substs) = match self_ty.sty {
 292             ty::ty_closure(id, _, ref substs) => (id, substs.clone()),
 293             _ => { return; }
 294         };
 295         assert!(!substs.has_escaping_regions());
 296
 297         let closure_trait_ref = self.closure_trait_ref(obligation, closure_def_id, substs);
 298         match self.confirm_poly_trait_refs(obligation.cause.clone(),
 299                                            obligation.predicate.to_poly_trait_ref(),
 300                                            closure_trait_ref) {
 301             Ok(()) => { }
 302             Err(_) => { /* Silently ignore errors. */ }
 303         }
 304     }
 305
 306     ///////////////////////////////////////////////////////////////////////////
 307     // EVALUATION
 308     //
 309     // Tests whether an obligation can be selected or whether an impl
 310     // can be applied to particular types. It skips the "confirmation"
 311     // step and hence completely ignores output type parameters.
 312     //
 313     // The result is "true" if the obligation *may* hold and "false" if
 314     // we can be sure it does not.
 315
 316     /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
 317     pub fn evaluate_obligation(&mut self,
 318                                obligation: &PredicateObligation<'tcx>)
 319                                -> bool
 320     {
 321         debug!("evaluate_obligation({})",
 322                obligation.repr(self.tcx()));
 323
 324         self.evaluate_predicate_recursively(None, obligation).may_apply()
 325     }
 326
 327     fn evaluate_builtin_bound_recursively<'o>(&mut self,
 328                                               bound: ty::BuiltinBound,
 329                                               previous_stack: &TraitObligationStack<'o, 'tcx>,
 330                                               ty: Ty<'tcx>)
 331                                               -> EvaluationResult<'tcx>
 332     {
 333         let obligation =
 334             util::predicate_for_builtin_bound(
 335                 self.tcx(),
 336                 previous_stack.obligation.cause.clone(),
 337                 bound,
 338                 previous_stack.obligation.recursion_depth + 1,
 339                 ty);
 340
 341         match obligation {
 342             Ok(obligation) => {
 343                 self.evaluate_predicate_recursively(Some(previous_stack), &obligation)
 344             }
 345             Err(ErrorReported) => {
 346                 EvaluatedToOk
 347             }
 348         }
 349     }
 350
 351     fn evaluate_predicates_recursively<'a,'o,I>(&mut self,
 352                                                 stack: Option<&TraitObligationStack<'o, 'tcx>>,
 353                                                 predicates: I)
 354                                                 -> EvaluationResult<'tcx>
 355         where I : Iterator<Item=&'a PredicateObligation<'tcx>>, 'tcx:'a
 356     {
 357         let mut result = EvaluatedToOk;
 358         for obligation in predicates {
 359             match self.evaluate_predicate_recursively(stack, obligation) {
 360                 EvaluatedToErr(e) => { return EvaluatedToErr(e); }
 361                 EvaluatedToAmbig => { result = EvaluatedToAmbig; }
 362                 EvaluatedToOk => { }
 363             }
 364         }
 365         result
 366     }
 367
 368     fn evaluate_predicate_recursively<'o>(&mut self,
 369                                           previous_stack: Option<&TraitObligationStack<'o, 'tcx>>,
 370                                           obligation: &PredicateObligation<'tcx>)
 371                                            -> EvaluationResult<'tcx>
 372     {
 373         debug!("evaluate_predicate_recursively({})",
 374                obligation.repr(self.tcx()));
 375
 376         match obligation.predicate {
 377             ty::Predicate::Trait(ref t) => {
 378                 assert!(!t.has_escaping_regions());
 379                 let obligation = obligation.with(t.clone());
 380                 self.evaluate_obligation_recursively(previous_stack, &obligation)
 381             }
 382
 383             ty::Predicate::Equate(ref p) => {
 384                 let result = self.infcx.probe(|_| {
 385                     self.infcx.equality_predicate(obligation.cause.span, p)
 386                 });
 387                 match result {
 388                     Ok(()) => EvaluatedToOk,
 389                     Err(_) => EvaluatedToErr(Unimplemented),
 390                 }
 391             }
 392
 393             ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => {
 394                 // we do not consider region relationships when
 395                 // evaluating trait matches
 396                 EvaluatedToOk
 397             }
 398
 399             ty::Predicate::Projection(ref data) => {
 400                 self.infcx.probe(|_| {
 401                     let project_obligation = obligation.with(data.clone());
 402                     match project::poly_project_and_unify_type(self, &project_obligation) {
 403                         Ok(Some(subobligations)) => {
 404                             self.evaluate_predicates_recursively(previous_stack,
 405                                                                  subobligations.iter())
 406                         }
 407                         Ok(None) => {
 408                             EvaluatedToAmbig
 409                         }
 410                         Err(_) => {
 411                             EvaluatedToErr(Unimplemented)
 412                         }
 413                     }
 414                 })
 415             }
 416         }
 417     }
 418
 419     fn evaluate_obligation_recursively<'o>(&mut self,
 420                                            previous_stack: Option<&TraitObligationStack<'o, 'tcx>>,
 421                                            obligation: &TraitObligation<'tcx>)
 422                                            -> EvaluationResult<'tcx>
 423     {
 424         debug!("evaluate_obligation_recursively({})",
 425                obligation.repr(self.tcx()));
 426
 427         let stack = self.push_stack(previous_stack.map(|x| x), obligation);
 428
 429         let result = self.evaluate_stack(&stack);
 430
 431         debug!("result: {:?}", result);
 432         result
 433     }
 434
 435     fn evaluate_stack<'o>(&mut self,
 436                           stack: &TraitObligationStack<'o, 'tcx>)
 437                           -> EvaluationResult<'tcx>
 438     {
 439         // In intercrate mode, whenever any of the types are unbound,
 440         // there can always be an impl. Even if there are no impls in
 441         // this crate, perhaps the type would be unified with
 442         // something from another crate that does provide an impl.
 443         //
 444         // In intracrate mode, we must still be conservative. The reason is
 445         // that we want to avoid cycles. Imagine an impl like:
 446         //
 447         //     impl<T:Eq> Eq for Vec<T>
 448         //
 449         // and a trait reference like `$0 : Eq` where `$0` is an
 450         // unbound variable. When we evaluate this trait-reference, we
 451         // will unify `$0` with `Vec<$1>` (for some fresh variable
 452         // `$1`), on the condition that `$1 : Eq`. We will then wind
 453         // up with many candidates (since that are other `Eq` impls
 454         // that apply) and try to winnow things down. This results in
 455         // a recursive evaluation that `$1 : Eq` -- as you can
 456         // imagine, this is just where we started. To avoid that, we
 457         // check for unbound variables and return an ambiguous (hence possible)
 458         // match if we've seen this trait before.
 459         //
 460         // This suffices to allow chains like `FnMut` implemented in
 461         // terms of `Fn` etc, but we could probably make this more
 462         // precise still.
 463         let input_types = stack.fresh_trait_ref.0.input_types();
 464         let unbound_input_types = input_types.iter().any(|&t| ty::type_is_fresh(t));
 465         if
 466             unbound_input_types &&
 467              (self.intercrate ||
 468               stack.iter().skip(1).any(
 469                   |prev| stack.fresh_trait_ref.def_id() == prev.fresh_trait_ref.def_id()))
 470         {
 471             debug!("evaluate_stack({}) --> unbound argument, recursion -->  ambiguous",
 472                    stack.fresh_trait_ref.repr(self.tcx()));
 473             return EvaluatedToAmbig;
 474         }
 475
 476         // If there is any previous entry on the stack that precisely
 477         // matches this obligation, then we can assume that the
 478         // obligation is satisfied for now (still all other conditions
 479         // must be met of course). One obvious case this comes up is
 480         // marker traits like `Send`. Think of a linked list:
 481         //
 482         //    struct List<T> { data: T, next: Option<Box<List<T>>> {
 483         //
 484         // `Box<List<T>>` will be `Send` if `T` is `Send` and
 485         // `Option<Box<List<T>>>` is `Send`, and in turn
 486         // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
 487         // `Send`.
 488         //
 489         // Note that we do this comparison using the `fresh_trait_ref`
 490         // fields. Because these have all been skolemized using
 491         // `self.freshener`, we can be sure that (a) this will not
 492         // affect the inferencer state and (b) that if we see two
 493         // skolemized types with the same index, they refer to the
 494         // same unbound type variable.
 495         if
 496             stack.iter()
 497             .skip(1) // skip top-most frame
 498             .any(|prev| stack.fresh_trait_ref == prev.fresh_trait_ref)
 499         {
 500             debug!("evaluate_stack({}) --> recursive",
 501                    stack.fresh_trait_ref.repr(self.tcx()));
 502             return EvaluatedToOk;
 503         }
 504
 505         match self.candidate_from_obligation(stack) {
 506             Ok(Some(c)) => self.winnow_candidate(stack, &c),
 507             Ok(None) => EvaluatedToAmbig,
 508             Err(e) => EvaluatedToErr(e),
 509         }
 510     }
 511
 512     /// Evaluates whether the impl with id `impl_def_id` could be applied to the self type
 513     /// `obligation_self_ty`. This can be used either for trait or inherent impls.
 514     pub fn evaluate_impl(&mut self,
 515                          impl_def_id: ast::DefId,
 516                          obligation: &TraitObligation<'tcx>)
 517                          -> bool
 518     {
 519         debug!("evaluate_impl(impl_def_id={}, obligation={})",
 520                impl_def_id.repr(self.tcx()),
 521                obligation.repr(self.tcx()));
 522
 523         self.infcx.probe(|snapshot| {
 524             let (skol_obligation_trait_ref, skol_map) =
 525                 self.infcx().skolemize_late_bound_regions(&obligation.predicate, snapshot);
 526             match self.match_impl(impl_def_id, obligation, snapshot,
 527                                   &skol_map, skol_obligation_trait_ref.trait_ref.clone()) {
 528                 Ok(substs) => {
 529                     let vtable_impl = self.vtable_impl(impl_def_id,
 530                                                        substs,
 531                                                        obligation.cause.clone(),
 532                                                        obligation.recursion_depth + 1,
 533                                                        skol_map,
 534                                                        snapshot);
 535                     self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
 536                 }
 537                 Err(()) => {
 538                     false
 539                 }
 540             }
 541         })
 542     }
 543
 544     ///////////////////////////////////////////////////////////////////////////
 545     // CANDIDATE ASSEMBLY
 546     //
 547     // The selection process begins by examining all in-scope impls,
 548     // caller obligations, and so forth and assembling a list of
 549     // candidates. See `doc.rs` and the `Candidate` type for more details.
 550
 551     fn candidate_from_obligation<'o>(&mut self,
 552                                      stack: &TraitObligationStack<'o, 'tcx>)
 553                                      -> SelectionResult<'tcx, SelectionCandidate<'tcx>>
 554     {
 555         // Watch out for overflow. This intentionally bypasses (and does
 556         // not update) the cache.
 557         let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
 558         if stack.obligation.recursion_depth >= recursion_limit {
 559             debug!("{} --> overflow (limit={})",
 560                    stack.obligation.repr(self.tcx()),
 561                    recursion_limit);
 562             return Err(Overflow)
 563         }
 564
 565         // Check the cache. Note that we skolemize the trait-ref
 566         // separately rather than using `stack.fresh_trait_ref` -- this
 567         // is because we want the unbound variables to be replaced
 568         // with fresh skolemized types starting from index 0.
 569         let cache_fresh_trait_pred =
 570             self.infcx.freshen(stack.obligation.predicate.clone());
 571         debug!("candidate_from_obligation(cache_fresh_trait_pred={}, obligation={})",
 572                cache_fresh_trait_pred.repr(self.tcx()),
 573                stack.repr(self.tcx()));
 574         assert!(!stack.obligation.predicate.has_escaping_regions());
 575
 576         match self.check_candidate_cache(&cache_fresh_trait_pred) {
 577             Some(c) => {
 578                 debug!("CACHE HIT: cache_fresh_trait_pred={}, candidate={}",
 579                        cache_fresh_trait_pred.repr(self.tcx()),
 580                        c.repr(self.tcx()));
 581                 return c;
 582             }
 583             None => { }
 584         }
 585
 586         // If no match, compute result and insert into cache.
 587         let candidate = self.candidate_from_obligation_no_cache(stack);
 588
 589         if self.should_update_candidate_cache(&cache_fresh_trait_pred, &candidate) {
 590             debug!("CACHE MISS: cache_fresh_trait_pred={}, candidate={}",
 591                    cache_fresh_trait_pred.repr(self.tcx()), candidate.repr(self.tcx()));
 592             self.insert_candidate_cache(cache_fresh_trait_pred, candidate.clone());
 593         }
 594
 595         candidate
 596     }
 597
 598     fn candidate_from_obligation_no_cache<'o>(&mut self,
 599                                               stack: &TraitObligationStack<'o, 'tcx>)
 600                                               -> SelectionResult<'tcx, SelectionCandidate<'tcx>>
 601     {
 602         if ty::type_is_error(stack.obligation.predicate.0.self_ty()) {
 603             return Ok(Some(ErrorCandidate));
 604         }
 605
 606         let candidate_set = try!(self.assemble_candidates(stack));
 607
 608         if candidate_set.ambiguous {
 609             debug!("candidate set contains ambig");
 610             return Ok(None);
 611         }
 612
 613         let mut candidates = candidate_set.vec;
 614
 615         debug!("assembled {} candidates for {}: {}",
 616                candidates.len(),
 617                stack.repr(self.tcx()),
 618                candidates.repr(self.tcx()));
 619
 620         // At this point, we know that each of the entries in the
 621         // candidate set is *individually* applicable. Now we have to
 622         // figure out if they contain mutual incompatibilities. This
 623         // frequently arises if we have an unconstrained input type --
 624         // for example, we are looking for $0:Eq where $0 is some
 625         // unconstrained type variable. In that case, we'll get a
 626         // candidate which assumes $0 == int, one that assumes $0 ==
 627         // uint, etc. This spells an ambiguity.
 628
 629         // If there is more than one candidate, first winnow them down
 630         // by considering extra conditions (nested obligations and so
 631         // forth). We don't winnow if there is exactly one
 632         // candidate. This is a relatively minor distinction but it
 633         // can lead to better inference and error-reporting. An
 634         // example would be if there was an impl:
 635         //
 636         //     impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
 637         //
 638         // and we were to see some code `foo.push_clone()` where `boo`
 639         // is a `Vec<Bar>` and `Bar` does not implement `Clone`.  If
 640         // we were to winnow, we'd wind up with zero candidates.
 641         // Instead, we select the right impl now but report `Bar does
 642         // not implement Clone`.
 643         if candidates.len() > 1 {
 644             candidates.retain(|c| self.winnow_candidate(stack, c).may_apply())
 645         }
 646
 647         // If there are STILL multiple candidate, we can further reduce
 648         // the list by dropping duplicates.
 649         if candidates.len() > 1 {
 650             let mut i = 0;
 651             while i < candidates.len() {
 652                 let is_dup =
 653                     (0..candidates.len())
 654                     .filter(|&j| i != j)
 655                     .any(|j| self.candidate_should_be_dropped_in_favor_of(&candidates[i],
 656                                                                           &candidates[j]));
 657                 if is_dup {
 658                     debug!("Dropping candidate #{}/{}: {}",
 659                            i, candidates.len(), candidates[i].repr(self.tcx()));
 660                     candidates.swap_remove(i);
 661                 } else {
 662                     debug!("Retaining candidate #{}/{}: {}",
 663                            i, candidates.len(), candidates[i].repr(self.tcx()));
 664                     i += 1;
 665                 }
 666             }
 667         }
 668
 669         // If there are *STILL* multiple candidates, give up and
 670         // report ambiguity.
 671         if candidates.len() > 1 {
 672             debug!("multiple matches, ambig");
 673             return Ok(None);
 674         }
 675
 676
 677         // If there are *NO* candidates, that there are no impls --
 678         // that we know of, anyway. Note that in the case where there
 679         // are unbound type variables within the obligation, it might
 680         // be the case that you could still satisfy the obligation
 681         // from another crate by instantiating the type variables with
 682         // a type from another crate that does have an impl. This case
 683         // is checked for in `evaluate_stack` (and hence users
 684         // who might care about this case, like coherence, should use
 685         // that function).
 686         if candidates.len() == 0 {
 687             return Err(Unimplemented);
 688         }
 689
 690         // Just one candidate left.
 691         let candidate = candidates.pop().unwrap();
 692
 693         match candidate {
 694             ImplCandidate(def_id) => {
 695                 match ty::trait_impl_polarity(self.tcx(), def_id) {
 696                     Some(ast::ImplPolarity::Negative) => return Err(Unimplemented),
 697                     _ => {}
 698                 }
 699             }
 700             _ => {}
 701         }
 702
 703         Ok(Some(candidate))
 704     }
 705
 706     fn pick_candidate_cache(&self) -> &SelectionCache<'tcx> {
 707         // If there are any where-clauses in scope, then we always use
 708         // a cache local to this particular scope. Otherwise, we
 709         // switch to a global cache. We used to try and draw
 710         // finer-grained distinctions, but that led to a serious of
 711         // annoying and weird bugs like #22019 and #18290. This simple
 712         // rule seems to be pretty clearly safe and also still retains
 713         // a very high hit rate (~95% when compiling rustc).
 714         if !self.param_env().caller_bounds.is_empty() {
 715             return &self.param_env().selection_cache;
 716         }
 717
 718         // Avoid using the master cache during coherence and just rely
 719         // on the local cache. This effectively disables caching
 720         // during coherence. It is really just a simplification to
 721         // avoid us having to fear that coherence results "pollute"
 722         // the master cache. Since coherence executes pretty quickly,
 723         // it's not worth going to more trouble to increase the
 724         // hit-rate I don't think.
 725         if self.intercrate {
 726             return &self.param_env().selection_cache;
 727         }
 728
 729         // Otherwise, we can use the global cache.
 730         &self.tcx().selection_cache
 731     }
 732
 733     fn check_candidate_cache(&mut self,
 734                              cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>)
 735                              -> Option<SelectionResult<'tcx, SelectionCandidate<'tcx>>>
 736     {
 737         let cache = self.pick_candidate_cache();
 738         let hashmap = cache.hashmap.borrow();
 739         hashmap.get(&cache_fresh_trait_pred.0.trait_ref).map(|c| (*c).clone())
 740     }
 741
 742     fn insert_candidate_cache(&mut self,
 743                               cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
 744                               candidate: SelectionResult<'tcx, SelectionCandidate<'tcx>>)
 745     {
 746         let cache = self.pick_candidate_cache();
 747         let mut hashmap = cache.hashmap.borrow_mut();
 748         hashmap.insert(cache_fresh_trait_pred.0.trait_ref.clone(), candidate);
 749     }
 750
 751     fn should_update_candidate_cache(&mut self,
 752                                      cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>,
 753                                      candidate: &SelectionResult<'tcx, SelectionCandidate<'tcx>>)
 754                                      -> bool
 755     {
 756         // In general, it's a good idea to cache results, even
 757         // ambiguous ones, to save us some trouble later. But we have
 758         // to be careful not to cache results that could be
 759         // invalidated later by advances in inference. Normally, this
 760         // is not an issue, because any inference variables whose
 761         // types are not yet bound are "freshened" in the cache key,
 762         // which means that if we later get the same request once that
 763         // type variable IS bound, we'll have a different cache key.
 764         // For example, if we have `Vec<_#0t> : Foo`, and `_#0t` is
 765         // not yet known, we may cache the result as `None`. But if
 766         // later `_#0t` is bound to `Bar`, then when we freshen we'll
 767         // have `Vec<Bar> : Foo` as the cache key.
 768         //
 769         // HOWEVER, it CAN happen that we get an ambiguity result in
 770         // one particular case around closures where the cache key
 771         // would not change. That is when the precise types of the
 772         // upvars that a closure references have not yet been figured
 773         // out (i.e., because it is not yet known if they are captured
 774         // by ref, and if by ref, what kind of ref). In these cases,
 775         // when matching a builtin bound, we will yield back an
 776         // ambiguous result. But the *cache key* is just the closure type,
 777         // it doesn't capture the state of the upvar computation.
 778         //
 779         // To avoid this trap, just don't cache ambiguous results if
 780         // the self-type contains no inference byproducts (that really
 781         // shouldn't happen in other circumstances anyway, given
 782         // coherence).
 783
 784         match *candidate {
 785             Ok(Some(_)) | Err(_) => true,
 786             Ok(None) => {
 787                 cache_fresh_trait_pred.0.input_types().iter().any(|&t| ty::type_has_ty_infer(t))
 788             }
 789         }
 790     }
 791
 792     fn assemble_candidates<'o>(&mut self,
 793                                stack: &TraitObligationStack<'o, 'tcx>)
 794                                -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>>
 795     {
 796         // Check for overflow.
 797
 798         let TraitObligationStack { obligation, .. } = *stack;
 799
 800         let mut candidates = SelectionCandidateSet {
 801             vec: Vec::new(),
 802             ambiguous: false
 803         };
 804
 805         // Other bounds. Consider both in-scope bounds from fn decl
 806         // and applicable impls. There is a certain set of precedence rules here.
 807
 808         match self.tcx().lang_items.to_builtin_kind(obligation.predicate.def_id()) {
 809             Some(ty::BoundCopy) => {
 810                 debug!("obligation self ty is {}",
 811                        obligation.predicate.0.self_ty().repr(self.tcx()));
 812
 813                 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
 814
 815                 try!(self.assemble_builtin_bound_candidates(ty::BoundCopy,
 816                                                             stack,
 817                                                             &mut candidates));
 818             }
 819             Some(bound @ ty::BoundSend) |
 820             Some(bound @ ty::BoundSync) => {
 821                 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
 822
 823                 // No explicit impls were declared for this type, consider the fallback rules.
 824                 if candidates.vec.is_empty() && !candidates.ambiguous {
 825                     try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
 826                 }
 827             }
 828
 829             Some(bound @ ty::BoundSized) => {
 830                 // Sized and Copy are always automatically computed.
 831                 try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
 832             }
 833
 834             None => {
 835                 // For the time being, we ignore user-defined impls for builtin-bounds, other than
 836                 // `Copy`.
 837                 // (And unboxed candidates only apply to the Fn/FnMut/etc traits.)
 838                 try!(self.assemble_closure_candidates(obligation, &mut candidates));
 839                 try!(self.assemble_fn_pointer_candidates(obligation, &mut candidates));
 840                 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
 841                 self.assemble_candidates_from_object_ty(obligation, &mut candidates);
 842             }
 843         }
 844
 845         self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
 846         try!(self.assemble_candidates_from_caller_bounds(stack, &mut candidates));
 847         debug!("candidate list size: {}", candidates.vec.len());
 848         Ok(candidates)
 849     }
 850
 851     fn assemble_candidates_from_projected_tys(&mut self,
 852                                               obligation: &TraitObligation<'tcx>,
 853                                               candidates: &mut SelectionCandidateSet<'tcx>)
 854     {
 855         let poly_trait_predicate =
 856             self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
 857
 858         debug!("assemble_candidates_for_projected_tys({},{})",
 859                obligation.repr(self.tcx()),
 860                poly_trait_predicate.repr(self.tcx()));
 861
 862         // FIXME(#20297) -- just examining the self-type is very simplistic
 863
 864         // before we go into the whole skolemization thing, just
 865         // quickly check if the self-type is a projection at all.
 866         let trait_def_id = match poly_trait_predicate.0.trait_ref.self_ty().sty {
 867             ty::ty_projection(ref data) => data.trait_ref.def_id,
 868             ty::ty_infer(ty::TyVar(_)) => {
 869                 // If the self-type is an inference variable, then it MAY wind up
 870                 // being a projected type, so induce an ambiguity.
 871                 //
 872                 // FIXME(#20297) -- being strict about this can cause
 873                 // inference failures with BorrowFrom, which is
 874                 // unfortunate. Can we do better here?
 875                 debug!("assemble_candidates_for_projected_tys: ambiguous self-type");
 876                 candidates.ambiguous = true;
 877                 return;
 878             }
 879             _ => { return; }
 880         };
 881
 882         debug!("assemble_candidates_for_projected_tys: trait_def_id={}",
 883                trait_def_id.repr(self.tcx()));
 884
 885         let result = self.infcx.probe(|snapshot| {
 886             self.match_projection_obligation_against_bounds_from_trait(obligation,
 887                                                                        snapshot)
 888         });
 889
 890         if result {
 891             candidates.vec.push(ProjectionCandidate);
 892         }
 893     }
 894
 895     fn match_projection_obligation_against_bounds_from_trait(
 896         &mut self,
 897         obligation: &TraitObligation<'tcx>,
 898         snapshot: &infer::CombinedSnapshot)
 899         -> bool
 900     {
 901         let poly_trait_predicate =
 902             self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
 903         let (skol_trait_predicate, skol_map) =
 904             self.infcx().skolemize_late_bound_regions(&poly_trait_predicate, snapshot);
 905         debug!("match_projection_obligation_against_bounds_from_trait: \
 906                 skol_trait_predicate={} skol_map={}",
 907                skol_trait_predicate.repr(self.tcx()),
 908                skol_map.repr(self.tcx()));
 909
 910         let projection_trait_ref = match skol_trait_predicate.trait_ref.self_ty().sty {
 911             ty::ty_projection(ref data) => &data.trait_ref,
 912             _ => {
 913                 self.tcx().sess.span_bug(
 914                     obligation.cause.span,
 915                     &format!("match_projection_obligation_against_bounds_from_trait() called \
 916                               but self-ty not a projection: {}",
 917                              skol_trait_predicate.trait_ref.self_ty().repr(self.tcx())));
 918             }
 919         };
 920         debug!("match_projection_obligation_against_bounds_from_trait: \
 921                 projection_trait_ref={}",
 922                projection_trait_ref.repr(self.tcx()));
 923
 924         let trait_predicates = ty::lookup_predicates(self.tcx(), projection_trait_ref.def_id);
 925         let bounds = trait_predicates.instantiate(self.tcx(), projection_trait_ref.substs);
 926         debug!("match_projection_obligation_against_bounds_from_trait: \
 927                 bounds={}",
 928                bounds.repr(self.tcx()));
 929
 930         let matching_bound =
 931             util::elaborate_predicates(self.tcx(), bounds.predicates.into_vec())
 932             .filter_to_traits()
 933             .find(
 934                 |bound| self.infcx.probe(
 935                     |_| self.match_projection(obligation,
 936                                               bound.clone(),
 937                                               skol_trait_predicate.trait_ref.clone(),
 938                                               &skol_map,
 939                                               snapshot)));
 940
 941         debug!("match_projection_obligation_against_bounds_from_trait: \
 942                 matching_bound={}",
 943                matching_bound.repr(self.tcx()));
 944         match matching_bound {
 945             None => false,
 946             Some(bound) => {
 947                 // Repeat the successful match, if any, this time outside of a probe.
 948                 let result = self.match_projection(obligation,
 949                                                    bound,
 950                                                    skol_trait_predicate.trait_ref.clone(),
 951                                                    &skol_map,
 952                                                    snapshot);
 953                 assert!(result);
 954                 true
 955             }
 956         }
 957     }
 958
 959     fn match_projection(&mut self,
 960                         obligation: &TraitObligation<'tcx>,
 961                         trait_bound: ty::PolyTraitRef<'tcx>,
 962                         skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
 963                         skol_map: &infer::SkolemizationMap,
 964                         snapshot: &infer::CombinedSnapshot)
 965                         -> bool
 966     {
 967         assert!(!skol_trait_ref.has_escaping_regions());
 968         let origin = infer::RelateOutputImplTypes(obligation.cause.span);
 969         match self.infcx.sub_poly_trait_refs(false,
 970                                              origin,
 971                                              trait_bound.clone(),
 972                                              ty::Binder(skol_trait_ref.clone())) {
 973             Ok(()) => { }
 974             Err(_) => { return false; }
 975         }
 976
 977         self.infcx.leak_check(skol_map, snapshot).is_ok()
 978     }
 979
 980     /// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller
 981     /// supplied to find out whether it is listed among them.
 982     ///
 983     /// Never affects inference environment.
 984     fn assemble_candidates_from_caller_bounds<'o>(&mut self,
 985                                                   stack: &TraitObligationStack<'o, 'tcx>,
 986                                                   candidates: &mut SelectionCandidateSet<'tcx>)
 987                                                   -> Result<(),SelectionError<'tcx>>
 988     {
 989         debug!("assemble_candidates_from_caller_bounds({})",
 990                stack.obligation.repr(self.tcx()));
 991
 992         let caller_trait_refs: Vec<_> =
 993             self.param_env().caller_bounds.iter()
 994             .filter_map(|o| o.to_opt_poly_trait_ref())
 995             .collect();
 996
 997         let all_bounds =
 998             util::transitive_bounds(
 999                 self.tcx(), &caller_trait_refs[]);
1000
1001         let matching_bounds =
1002             all_bounds.filter(
1003                 |bound| self.evaluate_where_clause(stack, bound.clone()).may_apply());
1004
1005         let param_candidates =
1006             matching_bounds.map(|bound| ParamCandidate(bound));
1007
1008         candidates.vec.extend(param_candidates);
1009
1010         Ok(())
1011     }
1012
1013     fn evaluate_where_clause<'o>(&mut self,
1014                                  stack: &TraitObligationStack<'o, 'tcx>,
1015                                  where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
1016                                  -> EvaluationResult<'tcx>
1017     {
1018         self.infcx().probe(move |_| {
1019             match self.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) {
1020                 Ok(obligations) => {
1021                     self.evaluate_predicates_recursively(Some(stack), obligations.iter())
1022                 }
1023                 Err(()) => {
1024                     EvaluatedToErr(Unimplemented)
1025                 }
1026             }
1027         })
1028     }
1029
1030     /// Check for the artificial impl that the compiler will create for an obligation like `X :
1031     /// FnMut<..>` where `X` is a closure type.
1032     ///
1033     /// Note: the type parameters on a closure candidate are modeled as *output* type
1034     /// parameters and hence do not affect whether this trait is a match or not. They will be
1035     /// unified during the confirmation step.
1036     fn assemble_closure_candidates(&mut self,
1037                                    obligation: &TraitObligation<'tcx>,
1038                                    candidates: &mut SelectionCandidateSet<'tcx>)
1039                                    -> Result<(),SelectionError<'tcx>>
1040     {
1041         let kind = match self.tcx().lang_items.fn_trait_kind(obligation.predicate.0.def_id()) {
1042             Some(k) => k,
1043             None => { return Ok(()); }
1044         };
1045
1046         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1047         let (closure_def_id, substs) = match self_ty.sty {
1048             ty::ty_closure(id, _, ref substs) => (id, substs.clone()),
1049             ty::ty_infer(ty::TyVar(_)) => {
1050                 debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
1051                 candidates.ambiguous = true;
1052                 return Ok(());
1053             }
1054             _ => { return Ok(()); }
1055         };
1056
1057         debug!("assemble_unboxed_candidates: self_ty={} kind={:?} obligation={}",
1058                self_ty.repr(self.tcx()),
1059                kind,
1060                obligation.repr(self.tcx()));
1061
1062         match self.closure_typer.closure_kind(closure_def_id) {
1063             Some(closure_kind) => {
1064                 debug!("assemble_unboxed_candidates: closure_kind = {:?}", closure_kind);
1065                 if closure_kind == kind {
1066                     candidates.vec.push(ClosureCandidate(closure_def_id, substs.clone()));
1067                 }
1068             }
1069             None => {
1070                 debug!("assemble_unboxed_candidates: closure_kind not yet known");
1071                 candidates.ambiguous = true;
1072             }
1073         }
1074
1075         Ok(())
1076     }
1077
1078     /// Implement one of the `Fn()` family for a fn pointer.
1079     fn assemble_fn_pointer_candidates(&mut self,
1080                                       obligation: &TraitObligation<'tcx>,
1081                                       candidates: &mut SelectionCandidateSet<'tcx>)
1082                                       -> Result<(),SelectionError<'tcx>>
1083     {
1084         // We provide a `Fn` impl for fn pointers. There is no need to provide
1085         // the other traits (e.g. `FnMut`) since those are provided by blanket
1086         // impls.
1087         if Some(obligation.predicate.def_id()) != self.tcx().lang_items.fn_trait() {
1088             return Ok(());
1089         }
1090
1091         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1092         match self_ty.sty {
1093             ty::ty_infer(ty::TyVar(_)) => {
1094                 debug!("assemble_fn_pointer_candidates: ambiguous self-type");
1095                 candidates.ambiguous = true; // could wind up being a fn() type
1096             }
1097
1098             // provide an impl, but only for suitable `fn` pointers
1099             ty::ty_bare_fn(_, &ty::BareFnTy {
1100                 unsafety: ast::Unsafety::Normal,
1101                 abi: abi::Rust,
1102                 sig: ty::Binder(ty::FnSig {
1103                     inputs: _,
1104                     output: ty::FnConverging(_),
1105                     variadic: false
1106                 })
1107             }) => {
1108                 candidates.vec.push(FnPointerCandidate);
1109             }
1110
1111             _ => { }
1112         }
1113
1114         Ok(())
1115     }
1116
1117     /// Search for impls that might apply to `obligation`.
1118     fn assemble_candidates_from_impls(&mut self,
1119                                       obligation: &TraitObligation<'tcx>,
1120                                       candidates: &mut SelectionCandidateSet<'tcx>)
1121                                       -> Result<(), SelectionError<'tcx>>
1122     {
1123         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1124         debug!("assemble_candidates_from_impls(self_ty={})", self_ty.repr(self.tcx()));
1125
1126         let all_impls = self.all_impls(obligation.predicate.def_id());
1127         for &impl_def_id in &all_impls {
1128             self.infcx.probe(|snapshot| {
1129                 let (skol_obligation_trait_pred, skol_map) =
1130                     self.infcx().skolemize_late_bound_regions(&obligation.predicate, snapshot);
1131                 match self.match_impl(impl_def_id, obligation, snapshot,
1132                                       &skol_map, skol_obligation_trait_pred.trait_ref.clone()) {
1133                     Ok(_) => {
1134                         candidates.vec.push(ImplCandidate(impl_def_id));
1135                     }
1136                     Err(()) => { }
1137                 }
1138             });
1139         }
1140         Ok(())
1141     }
1142
1143     /// Search for impls that might apply to `obligation`.
1144     fn assemble_candidates_from_object_ty(&mut self,
1145                                           obligation: &TraitObligation<'tcx>,
1146                                           candidates: &mut SelectionCandidateSet<'tcx>)
1147     {
1148         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1149
1150         debug!("assemble_candidates_from_object_ty(self_ty={})",
1151                self_ty.repr(self.tcx()));
1152
1153         // Object-safety candidates are only applicable to object-safe
1154         // traits. Including this check is useful because it helps
1155         // inference in cases of traits like `BorrowFrom`, which are
1156         // not object-safe, and which rely on being able to infer the
1157         // self-type from one of the other inputs. Without this check,
1158         // these cases wind up being considered ambiguous due to a
1159         // (spurious) ambiguity introduced here.
1160         if !object_safety::is_object_safe(self.tcx(), obligation.predicate.to_poly_trait_ref()) {
1161             return;
1162         }
1163
1164         let poly_trait_ref = match self_ty.sty {
1165             ty::ty_trait(ref data) => {
1166                 data.principal_trait_ref_with_self_ty(self.tcx(), self_ty)
1167             }
1168             ty::ty_infer(ty::TyVar(_)) => {
1169                 debug!("assemble_candidates_from_object_ty: ambiguous");
1170                 candidates.ambiguous = true; // could wind up being an object type
1171                 return;
1172             }
1173             _ => {
1174                 return;
1175             }
1176         };
1177
1178         debug!("assemble_candidates_from_object_ty: poly_trait_ref={}",
1179                poly_trait_ref.repr(self.tcx()));
1180
1181         // see whether the object trait can be upcast to the trait we are looking for
1182         let obligation_def_id = obligation.predicate.def_id();
1183         let upcast_trait_ref = match util::upcast(self.tcx(), poly_trait_ref, obligation_def_id) {
1184             Some(r) => r,
1185             None => { return; }
1186         };
1187
1188         debug!("assemble_candidates_from_object_ty: upcast_trait_ref={}",
1189                upcast_trait_ref.repr(self.tcx()));
1190
1191         // check whether the upcast version of the trait-ref matches what we are looking for
1192         if let Ok(()) = self.infcx.probe(|_| self.match_poly_trait_ref(obligation,
1193                                                                        upcast_trait_ref.clone())) {
1194             debug!("assemble_candidates_from_object_ty: matched, pushing candidate");
1195             candidates.vec.push(ObjectCandidate);
1196         }
1197     }
1198
1199     ///////////////////////////////////////////////////////////////////////////
1200     // WINNOW
1201     //
1202     // Winnowing is the process of attempting to resolve ambiguity by
1203     // probing further. During the winnowing process, we unify all
1204     // type variables (ignoring skolemization) and then we also
1205     // attempt to evaluate recursive bounds to see if they are
1206     // satisfied.
1207
1208     /// Further evaluate `candidate` to decide whether all type parameters match and whether nested
1209     /// obligations are met. Returns true if `candidate` remains viable after this further
1210     /// scrutiny.
1211     fn winnow_candidate<'o>(&mut self,
1212                             stack: &TraitObligationStack<'o, 'tcx>,
1213                             candidate: &SelectionCandidate<'tcx>)
1214                             -> EvaluationResult<'tcx>
1215     {
1216         debug!("winnow_candidate: candidate={}", candidate.repr(self.tcx()));
1217         let result = self.infcx.probe(|_| {
1218             let candidate = (*candidate).clone();
1219             match self.confirm_candidate(stack.obligation, candidate) {
1220                 Ok(selection) => self.winnow_selection(Some(stack), selection),
1221                 Err(error) => EvaluatedToErr(error),
1222             }
1223         });
1224         debug!("winnow_candidate depth={} result={:?}",
1225                stack.obligation.recursion_depth, result);
1226         result
1227     }
1228
1229     fn winnow_selection<'o>(&mut self,
1230                             stack: Option<&TraitObligationStack<'o, 'tcx>>,
1231                             selection: Selection<'tcx>)
1232                             -> EvaluationResult<'tcx>
1233     {
1234         self.evaluate_predicates_recursively(stack, selection.iter_nested())
1235     }
1236
1237     /// Returns true if `candidate_i` should be dropped in favor of
1238     /// `candidate_j`.  Generally speaking we will drop duplicate
1239     /// candidates and prefer where-clause candidates.
1240     fn candidate_should_be_dropped_in_favor_of<'o>(&mut self,
1241                                                    candidate_i: &SelectionCandidate<'tcx>,
1242                                                    candidate_j: &SelectionCandidate<'tcx>)
1243                                                    -> bool
1244     {
1245         if candidate_i == candidate_j {
1246             return true;
1247         }
1248
1249         match (candidate_i, candidate_j) {
1250             (&ImplCandidate(..), &ParamCandidate(..)) |
1251             (&ClosureCandidate(..), &ParamCandidate(..)) |
1252             (&FnPointerCandidate(..), &ParamCandidate(..)) |
1253             (&BuiltinCandidate(..), &ParamCandidate(..)) => {
1254                 // We basically prefer always prefer to use a
1255                 // where-clause over another option. Where clauses
1256                 // impose the burden of finding the exact match onto
1257                 // the caller. Using an impl in preference of a where
1258                 // clause can also lead us to "overspecialize", as in
1259                 // #18453.
1260                 true
1261             }
1262             (&ProjectionCandidate, &ParamCandidate(_)) => {
1263                 // FIXME(#20297) -- this gives where clauses precedent
1264                 // over projections. Really these are just two means
1265                 // of deducing information (one based on the where
1266                 // clauses on the trait definition; one based on those
1267                 // on the enclosing scope), and it'd be better to
1268                 // integrate them more intelligently. But for now this
1269                 // seems ok. If we DON'T give where clauses
1270                 // precedence, we run into trouble in default methods,
1271                 // where both the projection bounds for `Self::A` and
1272                 // the where clauses are in scope.
1273                 true
1274             }
1275             _ => {
1276                 false
1277             }
1278         }
1279     }
1280
1281     ///////////////////////////////////////////////////////////////////////////
1282     // BUILTIN BOUNDS
1283     //
1284     // These cover the traits that are built-in to the language
1285     // itself.  This includes `Copy` and `Sized` for sure. For the
1286     // moment, it also includes `Send` / `Sync` and a few others, but
1287     // those will hopefully change to library-defined traits in the
1288     // future.
1289
1290     fn assemble_builtin_bound_candidates<'o>(&mut self,
1291                                              bound: ty::BuiltinBound,
1292                                              stack: &TraitObligationStack<'o, 'tcx>,
1293                                              candidates: &mut SelectionCandidateSet<'tcx>)
1294                                              -> Result<(),SelectionError<'tcx>>
1295     {
1296         match self.builtin_bound(bound, stack.obligation) {
1297             Ok(If(..)) => {
1298                 debug!("builtin_bound: bound={}",
1299                        bound.repr(self.tcx()));
1300                 candidates.vec.push(BuiltinCandidate(bound));
1301                 Ok(())
1302             }
1303             Ok(ParameterBuiltin) => { Ok(()) }
1304             Ok(AmbiguousBuiltin) => {
1305                 debug!("assemble_builtin_bound_candidates: ambiguous builtin");
1306                 Ok(candidates.ambiguous = true)
1307             }
1308             Err(e) => { Err(e) }
1309         }
1310     }
1311
1312     fn builtin_bound(&mut self,
1313                      bound: ty::BuiltinBound,
1314                      obligation: &TraitObligation<'tcx>)
1315                      -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1316     {
1317         // Note: these tests operate on types that may contain bound
1318         // regions. To be proper, we ought to skolemize here, but we
1319         // forego the skolemization and defer it until the
1320         // confirmation step.
1321
1322         let self_ty = self.infcx.shallow_resolve(obligation.predicate.0.self_ty());
1323         return match self_ty.sty {
1324             ty::ty_infer(ty::IntVar(_)) |
1325             ty::ty_infer(ty::FloatVar(_)) |
1326             ty::ty_uint(_) |
1327             ty::ty_int(_) |
1328             ty::ty_bool |
1329             ty::ty_float(_) |
1330             ty::ty_bare_fn(..) |
1331             ty::ty_char => {
1332                 // safe for everything
1333                 Ok(If(Vec::new()))
1334             }
1335
1336             ty::ty_uniq(referent_ty) => {  // Box<T>
1337                 match bound {
1338                     ty::BoundCopy => {
1339                         Err(Unimplemented)
1340                     }
1341
1342                     ty::BoundSized => {
1343                         Ok(If(Vec::new()))
1344                     }
1345
1346                     ty::BoundSync |
1347                     ty::BoundSend => {
1348                         Ok(If(vec![referent_ty]))
1349                     }
1350                 }
1351             }
1352
1353             ty::ty_ptr(..) => {     // *const T, *mut T
1354                 match bound {
1355                     ty::BoundCopy |
1356                     ty::BoundSized => {
1357                         Ok(If(Vec::new()))
1358                     }
1359
1360                     ty::BoundSync |
1361                     ty::BoundSend => {
1362                         // sync and send are not implemented for *const, *mut
1363                         Err(Unimplemented)
1364                     }
1365                 }
1366             }
1367
1368             ty::ty_trait(ref data) => {
1369                 match bound {
1370                     ty::BoundSized => {
1371                         Err(Unimplemented)
1372                     }
1373                     ty::BoundCopy | ty::BoundSync | ty::BoundSend => {
1374                         if data.bounds.builtin_bounds.contains(&bound) {
1375                             Ok(If(Vec::new()))
1376                         } else {
1377                             // Recursively check all supertraits to find out if any further
1378                             // bounds are required and thus we must fulfill.
1379                             let principal =
1380                                 data.principal_trait_ref_with_self_ty(self.tcx(),
1381                                                                       self.tcx().types.err);
1382                             for tr in util::supertraits(self.tcx(), principal) {
1383                                 let td = ty::lookup_trait_def(self.tcx(), tr.def_id());
1384                                 if td.bounds.builtin_bounds.contains(&bound) {
1385                                     return Ok(If(Vec::new()))
1386                                 }
1387                             }
1388
1389                             Err(Unimplemented)
1390                         }
1391                     }
1392                 }
1393             }
1394
1395             ty::ty_rptr(_, ty::mt { ty: referent_ty, mutbl }) => {
1396                 // &mut T or &T
1397                 match bound {
1398                     ty::BoundCopy => {
1399                         match mutbl {
1400                             // &mut T is affine and hence never `Copy`
1401                             ast::MutMutable => {
1402                                 Err(Unimplemented)
1403                             }
1404
1405                             // &T is always copyable
1406                             ast::MutImmutable => {
1407                                 Ok(If(Vec::new()))
1408                             }
1409                         }
1410                     }
1411
1412                     ty::BoundSized => {
1413                         Ok(If(Vec::new()))
1414                     }
1415
1416                     ty::BoundSync |
1417                     ty::BoundSend => {
1418                         Ok(If(vec![referent_ty]))
1419                     }
1420                 }
1421             }
1422
1423             ty::ty_vec(element_ty, ref len) => {
1424                 // [T, ..n] and [T]
1425                 match bound {
1426                     ty::BoundCopy => {
1427                         match *len {
1428                             Some(_) => {
1429                                 // [T, ..n] is copy iff T is copy
1430                                 Ok(If(vec![element_ty]))
1431                             }
1432                             None => {
1433                                 // [T] is unsized and hence affine
1434                                 Err(Unimplemented)
1435                             }
1436                         }
1437                     }
1438
1439                     ty::BoundSized => {
1440                         if len.is_some() {
1441                             Ok(If(Vec::new()))
1442                         } else {
1443                             Err(Unimplemented)
1444                         }
1445                     }
1446
1447                     ty::BoundSync |
1448                     ty::BoundSend => {
1449                         Ok(If(vec![element_ty]))
1450                     }
1451                 }
1452             }
1453
1454             ty::ty_str => {
1455                 // Equivalent to [u8]
1456                 match bound {
1457                     ty::BoundSync |
1458                     ty::BoundSend => {
1459                         Ok(If(Vec::new()))
1460                     }
1461
1462                     ty::BoundCopy |
1463                     ty::BoundSized => {
1464                         Err(Unimplemented)
1465                     }
1466                 }
1467             }
1468
1469             ty::ty_tup(ref tys) => {
1470                 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1471                 Ok(If(tys.clone()))
1472             }
1473
1474             ty::ty_closure(def_id, _, substs) => {
1475                 // FIXME -- This case is tricky. In the case of by-ref
1476                 // closures particularly, we need the results of
1477                 // inference to decide how to reflect the type of each
1478                 // upvar (the upvar may have type `T`, but the runtime
1479                 // type could be `&mut`, `&`, or just `T`). For now,
1480                 // though, we'll do this unsoundly and assume that all
1481                 // captures are by value. Really what we ought to do
1482                 // is reserve judgement and then intertwine this
1483                 // analysis with closure inference.
1484                 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
1485
1486                 // Unboxed closures shouldn't be
1487                 // implicitly copyable
1488                 if bound == ty::BoundCopy {
1489                     return Ok(ParameterBuiltin);
1490                 }
1491
1492                 // Upvars are always local variables or references to
1493                 // local variables, and local variables cannot be
1494                 // unsized, so the closure struct as a whole must be
1495                 // Sized.
1496                 if bound == ty::BoundSized {
1497                     return Ok(If(Vec::new()));
1498                 }
1499
1500                 match self.closure_typer.closure_upvars(def_id, substs) {
1501                     Some(upvars) => {
1502                         Ok(If(upvars.iter().map(|c| c.ty).collect()))
1503                     }
1504                     None => {
1505                         debug!("assemble_builtin_bound_candidates: no upvar types available yet");
1506                         Ok(AmbiguousBuiltin)
1507                     }
1508                 }
1509             }
1510
1511             ty::ty_struct(def_id, substs) => {
1512                 let types: Vec<Ty> =
1513                     ty::struct_fields(self.tcx(), def_id, substs).iter()
1514                                                                  .map(|f| f.mt.ty)
1515                                                                  .collect();
1516                 nominal(self, bound, def_id, types)
1517             }
1518
1519             ty::ty_enum(def_id, substs) => {
1520                 let types: Vec<Ty> =
1521                     ty::substd_enum_variants(self.tcx(), def_id, substs)
1522                     .iter()
1523                     .flat_map(|variant| variant.args.iter())
1524                     .map(|&ty| ty)
1525                     .collect();
1526                 nominal(self, bound, def_id, types)
1527             }
1528
1529             ty::ty_projection(_) |
1530             ty::ty_param(_) => {
1531                 // Note: A type parameter is only considered to meet a
1532                 // particular bound if there is a where clause telling
1533                 // us that it does, and that case is handled by
1534                 // `assemble_candidates_from_caller_bounds()`.
1535                 Ok(ParameterBuiltin)
1536             }
1537
1538             ty::ty_infer(ty::TyVar(_)) => {
1539                 // Unbound type variable. Might or might not have
1540                 // applicable impls and so forth, depending on what
1541                 // those type variables wind up being bound to.
1542                 debug!("assemble_builtin_bound_candidates: ambiguous builtin");
1543                 Ok(AmbiguousBuiltin)
1544             }
1545
1546             ty::ty_open(ty) => {
1547                 // these only crop up in trans, and represent an
1548                 // "opened" unsized/existential type (one that has
1549                 // been dereferenced)
1550                 match bound {
1551                     ty::BoundCopy |
1552                     ty::BoundSync |
1553                     ty::BoundSend => {
1554                         Ok(If(vec!(ty)))
1555                     }
1556
1557                     ty::BoundSized => {
1558                         Err(Unimplemented)
1559                     }
1560                 }
1561             }
1562             ty::ty_err => {
1563                 Ok(If(Vec::new()))
1564             }
1565
1566             ty::ty_infer(ty::FreshTy(_)) |
1567             ty::ty_infer(ty::FreshIntTy(_)) => {
1568                 self.tcx().sess.bug(
1569                     &format!(
1570                         "asked to assemble builtin bounds of unexpected type: {}",
1571                         self_ty.repr(self.tcx()))[]);
1572             }
1573         };
1574
1575         fn nominal<'cx, 'tcx>(this: &mut SelectionContext<'cx, 'tcx>,
1576                               bound: ty::BuiltinBound,
1577                               def_id: ast::DefId,
1578                               types: Vec<Ty<'tcx>>)
1579                               -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1580         {
1581             // First check for markers and other nonsense.
1582             let tcx = this.tcx();
1583             match bound {
1584                 ty::BoundSend => {
1585                     if Some(def_id) == tcx.lang_items.managed_bound() {
1586                         return Err(Unimplemented)
1587                     }
1588                 }
1589
1590                 ty::BoundCopy => {
1591                     return Ok(ParameterBuiltin)
1592                 }
1593
1594                 ty::BoundSync => {
1595                     if
1596                         Some(def_id) == tcx.lang_items.managed_bound() ||
1597                         Some(def_id) == tcx.lang_items.unsafe_cell_type()
1598                     {
1599                         return Err(Unimplemented)
1600                     }
1601                 }
1602
1603                 ty::BoundSized => { }
1604             }
1605
1606             Ok(If(types))
1607         }
1608     }
1609
1610     ///////////////////////////////////////////////////////////////////////////
1611     // CONFIRMATION
1612     //
1613     // Confirmation unifies the output type parameters of the trait
1614     // with the values found in the obligation, possibly yielding a
1615     // type error.  See `doc.rs` for more details.
1616
1617     fn confirm_candidate(&mut self,
1618                          obligation: &TraitObligation<'tcx>,
1619                          candidate: SelectionCandidate<'tcx>)
1620                          -> Result<Selection<'tcx>,SelectionError<'tcx>>
1621     {
1622         debug!("confirm_candidate({}, {})",
1623                obligation.repr(self.tcx()),
1624                candidate.repr(self.tcx()));
1625
1626         match candidate {
1627             BuiltinCandidate(builtin_bound) => {
1628                 Ok(VtableBuiltin(
1629                     try!(self.confirm_builtin_candidate(obligation, builtin_bound))))
1630             }
1631
1632             ErrorCandidate => {
1633                 Ok(VtableBuiltin(VtableBuiltinData { nested: VecPerParamSpace::empty() }))
1634             }
1635
1636             ParamCandidate(param) => {
1637                 let obligations = self.confirm_param_candidate(obligation, param);
1638                 Ok(VtableParam(obligations))
1639             }
1640
1641             ImplCandidate(impl_def_id) => {
1642                 let vtable_impl =
1643                     try!(self.confirm_impl_candidate(obligation, impl_def_id));
1644                 Ok(VtableImpl(vtable_impl))
1645             }
1646
1647             ClosureCandidate(closure_def_id, substs) => {
1648                 try!(self.confirm_closure_candidate(obligation, closure_def_id, &substs));
1649                 Ok(VtableClosure(closure_def_id, substs))
1650             }
1651
1652             ObjectCandidate => {
1653                 let data = self.confirm_object_candidate(obligation);
1654                 Ok(VtableObject(data))
1655             }
1656
1657             FnPointerCandidate => {
1658                 let fn_type =
1659                     try!(self.confirm_fn_pointer_candidate(obligation));
1660                 Ok(VtableFnPointer(fn_type))
1661             }
1662
1663             ProjectionCandidate => {
1664                 self.confirm_projection_candidate(obligation);
1665                 Ok(VtableParam(Vec::new()))
1666             }
1667         }
1668     }
1669
1670     fn confirm_projection_candidate(&mut self,
1671                                     obligation: &TraitObligation<'tcx>)
1672     {
1673         let _: Result<(),()> =
1674             self.infcx.try(|snapshot| {
1675                 let result =
1676                     self.match_projection_obligation_against_bounds_from_trait(obligation,
1677                                                                                snapshot);
1678                 assert!(result);
1679                 Ok(())
1680             });
1681     }
1682
1683     fn confirm_param_candidate(&mut self,
1684                                obligation: &TraitObligation<'tcx>,
1685                                param: ty::PolyTraitRef<'tcx>)
1686                                -> Vec<PredicateObligation<'tcx>>
1687     {
1688         debug!("confirm_param_candidate({},{})",
1689                obligation.repr(self.tcx()),
1690                param.repr(self.tcx()));
1691
1692         // During evaluation, we already checked that this
1693         // where-clause trait-ref could be unified with the obligation
1694         // trait-ref. Repeat that unification now without any
1695         // transactional boundary; it should not fail.
1696         match self.match_where_clause_trait_ref(obligation, param.clone()) {
1697             Ok(obligations) => obligations,
1698             Err(()) => {
1699                 self.tcx().sess.bug(
1700                     &format!("Where clause `{}` was applicable to `{}` but now is not",
1701                              param.repr(self.tcx()),
1702                              obligation.repr(self.tcx())));
1703             }
1704         }
1705     }
1706
1707     fn confirm_builtin_candidate(&mut self,
1708                                  obligation: &TraitObligation<'tcx>,
1709                                  bound: ty::BuiltinBound)
1710                                  -> Result<VtableBuiltinData<PredicateObligation<'tcx>>,
1711                                            SelectionError<'tcx>>
1712     {
1713         debug!("confirm_builtin_candidate({})",
1714                obligation.repr(self.tcx()));
1715
1716         match try!(self.builtin_bound(bound, obligation)) {
1717             If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)),
1718             AmbiguousBuiltin | ParameterBuiltin => {
1719                 self.tcx().sess.span_bug(
1720                     obligation.cause.span,
1721                     &format!("builtin bound for {} was ambig",
1722                             obligation.repr(self.tcx()))[]);
1723             }
1724         }
1725     }
1726
1727     fn vtable_builtin_data(&mut self,
1728                            obligation: &TraitObligation<'tcx>,
1729                            bound: ty::BuiltinBound,
1730                            nested: Vec<Ty<'tcx>>)
1731                            -> VtableBuiltinData<PredicateObligation<'tcx>>
1732     {
1733         let derived_cause = self.derived_cause(obligation, BuiltinDerivedObligation);
1734         let obligations = nested.iter().map(|&bound_ty| {
1735             // the obligation might be higher-ranked, e.g. for<'a> &'a
1736             // int : Copy. In that case, we will wind up with
1737             // late-bound regions in the `nested` vector. So for each
1738             // one we instantiate to a skolemized region, do our work
1739             // to produce something like `&'0 int : Copy`, and then
1740             // re-bind it. This is a bit of busy-work but preserves
1741             // the invariant that we only manipulate free regions, not
1742             // bound ones.
1743             self.infcx.try(|snapshot| {
1744                 let (skol_ty, skol_map) =
1745                     self.infcx().skolemize_late_bound_regions(&ty::Binder(bound_ty), snapshot);
1746                 let skol_predicate =
1747                     util::predicate_for_builtin_bound(
1748                         self.tcx(),
1749                         derived_cause.clone(),
1750                         bound,
1751                         obligation.recursion_depth + 1,
1752                         skol_ty);
1753                 match skol_predicate {
1754                     Ok(skol_predicate) => Ok(self.infcx().plug_leaks(skol_map, snapshot,
1755                                                                      &skol_predicate)),
1756                     Err(ErrorReported) => Err(ErrorReported)
1757                 }
1758             })
1759         }).collect::<Result<_, _>>();
1760         let obligations = match obligations {
1761             Ok(o) => o,
1762             Err(ErrorReported) => Vec::new()
1763         };
1764
1765         let obligations = VecPerParamSpace::new(obligations, Vec::new(), Vec::new());
1766
1767         debug!("vtable_builtin_data: obligations={}",
1768                obligations.repr(self.tcx()));
1769
1770         VtableBuiltinData { nested: obligations }
1771     }
1772
1773     fn confirm_impl_candidate(&mut self,
1774                               obligation: &TraitObligation<'tcx>,
1775                               impl_def_id: ast::DefId)
1776                               -> Result<VtableImplData<'tcx, PredicateObligation<'tcx>>,
1777                                         SelectionError<'tcx>>
1778     {
1779         debug!("confirm_impl_candidate({},{})",
1780                obligation.repr(self.tcx()),
1781                impl_def_id.repr(self.tcx()));
1782
1783         // First, create the substitutions by matching the impl again,
1784         // this time not in a probe.
1785         self.infcx.try(|snapshot| {
1786             let (skol_obligation_trait_ref, skol_map) =
1787                 self.infcx().skolemize_late_bound_regions(&obligation.predicate, snapshot);
1788             let substs =
1789                 self.rematch_impl(impl_def_id, obligation,
1790                                   snapshot, &skol_map, skol_obligation_trait_ref.trait_ref);
1791             debug!("confirm_impl_candidate substs={}", substs.repr(self.tcx()));
1792             Ok(self.vtable_impl(impl_def_id, substs, obligation.cause.clone(),
1793                                 obligation.recursion_depth + 1, skol_map, snapshot))
1794         })
1795     }
1796
1797     fn vtable_impl(&mut self,
1798                    impl_def_id: ast::DefId,
1799                    substs: Normalized<'tcx, Substs<'tcx>>,
1800                    cause: ObligationCause<'tcx>,
1801                    recursion_depth: uint,
1802                    skol_map: infer::SkolemizationMap,
1803                    snapshot: &infer::CombinedSnapshot)
1804                    -> VtableImplData<'tcx, PredicateObligation<'tcx>>
1805     {
1806         debug!("vtable_impl(impl_def_id={}, substs={}, recursion_depth={}, skol_map={})",
1807                impl_def_id.repr(self.tcx()),
1808                substs.repr(self.tcx()),
1809                recursion_depth,
1810                skol_map.repr(self.tcx()));
1811
1812         let mut impl_obligations =
1813             self.impl_obligations(cause,
1814                                  recursion_depth,
1815                                  impl_def_id,
1816                                  &substs.value,
1817                                  skol_map,
1818                                  snapshot);
1819
1820         debug!("vtable_impl: impl_def_id={} impl_obligations={}",
1821                impl_def_id.repr(self.tcx()),
1822                impl_obligations.repr(self.tcx()));
1823
1824         impl_obligations.extend(TypeSpace, substs.obligations.into_iter());
1825
1826         VtableImplData { impl_def_id: impl_def_id,
1827                          substs: substs.value,
1828                          nested: impl_obligations }
1829     }
1830
1831     fn confirm_object_candidate(&mut self,
1832                                 obligation: &TraitObligation<'tcx>)
1833                                 -> VtableObjectData<'tcx>
1834     {
1835         debug!("confirm_object_candidate({})",
1836                obligation.repr(self.tcx()));
1837
1838         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1839         let poly_trait_ref = match self_ty.sty {
1840             ty::ty_trait(ref data) => {
1841                 data.principal_trait_ref_with_self_ty(self.tcx(), self_ty)
1842             }
1843             _ => {
1844                 self.tcx().sess.span_bug(obligation.cause.span,
1845                                          "object candidate with non-object");
1846             }
1847         };
1848
1849         let obligation_def_id = obligation.predicate.def_id();
1850         let upcast_trait_ref = match util::upcast(self.tcx(),
1851                                                   poly_trait_ref.clone(),
1852                                                   obligation_def_id) {
1853             Some(r) => r,
1854             None => {
1855                 self.tcx().sess.span_bug(obligation.cause.span,
1856                                          &format!("unable to upcast from {} to {}",
1857                                                   poly_trait_ref.repr(self.tcx()),
1858                                                   obligation_def_id.repr(self.tcx())));
1859             }
1860         };
1861
1862         match self.match_poly_trait_ref(obligation, upcast_trait_ref) {
1863             Ok(()) => { }
1864             Err(()) => {
1865                 self.tcx().sess.span_bug(obligation.cause.span,
1866                                          "failed to match trait refs");
1867             }
1868         }
1869
1870         VtableObjectData { object_ty: self_ty }
1871     }
1872
1873     fn confirm_fn_pointer_candidate(&mut self,
1874                                     obligation: &TraitObligation<'tcx>)
1875                                     -> Result<ty::Ty<'tcx>,SelectionError<'tcx>>
1876     {
1877         debug!("confirm_fn_pointer_candidate({})",
1878                obligation.repr(self.tcx()));
1879
1880         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1881         let sig = ty::ty_fn_sig(self_ty);
1882         let ty::Binder((trait_ref, _)) =
1883             util::closure_trait_ref_and_return_type(self.tcx(),
1884                                                     obligation.predicate.def_id(),
1885                                                     self_ty,
1886                                                     sig,
1887                                                     util::TupleArgumentsFlag::Yes);
1888         let trait_ref = ty::Binder(trait_ref);
1889
1890         try!(self.confirm_poly_trait_refs(obligation.cause.clone(),
1891                                           obligation.predicate.to_poly_trait_ref(),
1892                                           trait_ref));
1893         Ok(self_ty)
1894     }
1895
1896     fn confirm_closure_candidate(&mut self,
1897                                  obligation: &TraitObligation<'tcx>,
1898                                  closure_def_id: ast::DefId,
1899                                  substs: &Substs<'tcx>)
1900                                  -> Result<(),SelectionError<'tcx>>
1901     {
1902         debug!("confirm_closure_candidate({},{},{})",
1903                obligation.repr(self.tcx()),
1904                closure_def_id.repr(self.tcx()),
1905                substs.repr(self.tcx()));
1906
1907         let trait_ref = self.closure_trait_ref(obligation,
1908                                                closure_def_id,
1909                                                substs);
1910
1911         debug!("confirm_closure_candidate(closure_def_id={}, trait_ref={})",
1912                closure_def_id.repr(self.tcx()),
1913                trait_ref.repr(self.tcx()));
1914
1915         self.confirm_poly_trait_refs(obligation.cause.clone(),
1916                                      obligation.predicate.to_poly_trait_ref(),
1917                                      trait_ref)
1918     }
1919
1920     /// In the case of closure types and fn pointers,
1921     /// we currently treat the input type parameters on the trait as
1922     /// outputs. This means that when we have a match we have only
1923     /// considered the self type, so we have to go back and make sure
1924     /// to relate the argument types too.  This is kind of wrong, but
1925     /// since we control the full set of impls, also not that wrong,
1926     /// and it DOES yield better error messages (since we don't report
1927     /// errors as if there is no applicable impl, but rather report
1928     /// errors are about mismatched argument types.
1929     ///
1930     /// Here is an example. Imagine we have an closure expression
1931     /// and we desugared it so that the type of the expression is
1932     /// `Closure`, and `Closure` expects an int as argument. Then it
1933     /// is "as if" the compiler generated this impl:
1934     ///
1935     ///     impl Fn(int) for Closure { ... }
1936     ///
1937     /// Now imagine our obligation is `Fn(uint) for Closure`. So far
1938     /// we have matched the self-type `Closure`. At this point we'll
1939     /// compare the `int` to `uint` and generate an error.
1940     ///
1941     /// Note that this checking occurs *after* the impl has selected,
1942     /// because these output type parameters should not affect the
1943     /// selection of the impl. Therefore, if there is a mismatch, we
1944     /// report an error to the user.
1945     fn confirm_poly_trait_refs(&mut self,
1946                                obligation_cause: ObligationCause,
1947                                obligation_trait_ref: ty::PolyTraitRef<'tcx>,
1948                                expected_trait_ref: ty::PolyTraitRef<'tcx>)
1949                                -> Result<(), SelectionError<'tcx>>
1950     {
1951         let origin = infer::RelateOutputImplTypes(obligation_cause.span);
1952
1953         let obligation_trait_ref = obligation_trait_ref.clone();
1954         match self.infcx.sub_poly_trait_refs(false,
1955                                              origin,
1956                                              expected_trait_ref.clone(),
1957                                              obligation_trait_ref.clone()) {
1958             Ok(()) => Ok(()),
1959             Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
1960         }
1961     }
1962
1963     ///////////////////////////////////////////////////////////////////////////
1964     // Matching
1965     //
1966     // Matching is a common path used for both evaluation and
1967     // confirmation.  It basically unifies types that appear in impls
1968     // and traits. This does affect the surrounding environment;
1969     // therefore, when used during evaluation, match routines must be
1970     // run inside of a `probe()` so that their side-effects are
1971     // contained.
1972
1973     fn rematch_impl(&mut self,
1974                     impl_def_id: ast::DefId,
1975                     obligation: &TraitObligation<'tcx>,
1976                     snapshot: &infer::CombinedSnapshot,
1977                     skol_map: &infer::SkolemizationMap,
1978                     skol_obligation_trait_ref: Rc<ty::TraitRef<'tcx>>)
1979                     -> Normalized<'tcx, Substs<'tcx>>
1980     {
1981         match self.match_impl(impl_def_id, obligation, snapshot,
1982                               skol_map, skol_obligation_trait_ref) {
1983             Ok(substs) => {
1984                 substs
1985             }
1986             Err(()) => {
1987                 self.tcx().sess.bug(
1988                     &format!("Impl {} was matchable against {} but now is not",
1989                             impl_def_id.repr(self.tcx()),
1990                             obligation.repr(self.tcx()))[]);
1991             }
1992         }
1993     }
1994
1995     fn match_impl(&mut self,
1996                   impl_def_id: ast::DefId,
1997                   obligation: &TraitObligation<'tcx>,
1998                   snapshot: &infer::CombinedSnapshot,
1999                   skol_map: &infer::SkolemizationMap,
2000                   skol_obligation_trait_ref: Rc<ty::TraitRef<'tcx>>)
2001                   -> Result<Normalized<'tcx, Substs<'tcx>>, ()>
2002     {
2003         let impl_trait_ref = ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
2004
2005         // Before we create the substitutions and everything, first
2006         // consider a "quick reject". This avoids creating more types
2007         // and so forth that we need to.
2008         if self.fast_reject_trait_refs(obligation, &*impl_trait_ref) {
2009             return Err(());
2010         }
2011
2012         let impl_substs = util::fresh_substs_for_impl(self.infcx,
2013                                                       obligation.cause.span,
2014                                                       impl_def_id);
2015
2016         let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
2017                                                   &impl_substs);
2018
2019         let impl_trait_ref =
2020             project::normalize_with_depth(self,
2021                                           obligation.cause.clone(),
2022                                           obligation.recursion_depth + 1,
2023                                           &impl_trait_ref);
2024
2025         debug!("match_impl(impl_def_id={}, obligation={}, \
2026                impl_trait_ref={}, skol_obligation_trait_ref={})",
2027                impl_def_id.repr(self.tcx()),
2028                obligation.repr(self.tcx()),
2029                impl_trait_ref.repr(self.tcx()),
2030                skol_obligation_trait_ref.repr(self.tcx()));
2031
2032         let origin = infer::RelateOutputImplTypes(obligation.cause.span);
2033         match self.infcx.sub_trait_refs(false,
2034                                         origin,
2035                                         impl_trait_ref.value.clone(),
2036                                         skol_obligation_trait_ref) {
2037             Ok(()) => { }
2038             Err(e) => {
2039                 debug!("match_impl: failed sub_trait_refs due to `{}`",
2040                        ty::type_err_to_str(self.tcx(), &e));
2041                 return Err(());
2042             }
2043         }
2044
2045         match self.infcx.leak_check(skol_map, snapshot) {
2046             Ok(()) => { }
2047             Err(e) => {
2048                 debug!("match_impl: failed leak check due to `{}`",
2049                        ty::type_err_to_str(self.tcx(), &e));
2050                 return Err(());
2051             }
2052         }
2053
2054         debug!("match_impl: success impl_substs={}", impl_substs.repr(self.tcx()));
2055         Ok(Normalized { value: impl_substs,
2056                         obligations: impl_trait_ref.obligations })
2057     }
2058
2059     fn fast_reject_trait_refs(&mut self,
2060                               obligation: &TraitObligation,
2061                               impl_trait_ref: &ty::TraitRef)
2062                               -> bool
2063     {
2064         // We can avoid creating type variables and doing the full
2065         // substitution if we find that any of the input types, when
2066         // simplified, do not match.
2067
2068         obligation.predicate.0.input_types().iter()
2069             .zip(impl_trait_ref.input_types().iter())
2070             .any(|(&obligation_ty, &impl_ty)| {
2071                 let simplified_obligation_ty =
2072                     fast_reject::simplify_type(self.tcx(), obligation_ty, true);
2073                 let simplified_impl_ty =
2074                     fast_reject::simplify_type(self.tcx(), impl_ty, false);
2075
2076                 simplified_obligation_ty.is_some() &&
2077                     simplified_impl_ty.is_some() &&
2078                     simplified_obligation_ty != simplified_impl_ty
2079             })
2080     }
2081
2082     /// Normalize `where_clause_trait_ref` and try to match it against
2083     /// `obligation`.  If successful, return any predicates that
2084     /// result from the normalization. Normalization is necessary
2085     /// because where-clauses are stored in the parameter environment
2086     /// unnormalized.
2087     fn match_where_clause_trait_ref(&mut self,
2088                                     obligation: &TraitObligation<'tcx>,
2089                                     where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
2090                                     -> Result<Vec<PredicateObligation<'tcx>>,()>
2091     {
2092         let () =
2093             try!(self.match_poly_trait_ref(obligation, where_clause_trait_ref));
2094
2095         Ok(Vec::new())
2096     }
2097
2098     /// Returns `Ok` if `poly_trait_ref` being true implies that the
2099     /// obligation is satisfied.
2100     fn match_poly_trait_ref(&mut self,
2101                             obligation: &TraitObligation<'tcx>,
2102                             poly_trait_ref: ty::PolyTraitRef<'tcx>)
2103                             -> Result<(),()>
2104     {
2105         debug!("match_poly_trait_ref: obligation={} poly_trait_ref={}",
2106                obligation.repr(self.tcx()),
2107                poly_trait_ref.repr(self.tcx()));
2108
2109         let origin = infer::RelateOutputImplTypes(obligation.cause.span);
2110         match self.infcx.sub_poly_trait_refs(false,
2111                                              origin,
2112                                              poly_trait_ref,
2113                                              obligation.predicate.to_poly_trait_ref()) {
2114             Ok(()) => Ok(()),
2115             Err(_) => Err(()),
2116         }
2117     }
2118
2119     /// Determines whether the self type declared against
2120     /// `impl_def_id` matches `obligation_self_ty`. If successful,
2121     /// returns the substitutions used to make them match. See
2122     /// `match_impl()`. For example, if `impl_def_id` is declared
2123     /// as:
2124     ///
2125     ///    impl<T:Copy> Foo for ~T { ... }
2126     ///
2127     /// and `obligation_self_ty` is `int`, we'd back an `Err(_)`
2128     /// result. But if `obligation_self_ty` were `~int`, we'd get
2129     /// back `Ok(T=int)`.
2130     fn match_inherent_impl(&mut self,
2131                            impl_def_id: ast::DefId,
2132                            obligation_cause: &ObligationCause,
2133                            obligation_self_ty: Ty<'tcx>)
2134                            -> Result<Substs<'tcx>,()>
2135     {
2136         // Create fresh type variables for each type parameter declared
2137         // on the impl etc.
2138         let impl_substs = util::fresh_substs_for_impl(self.infcx,
2139                                                       obligation_cause.span,
2140                                                       impl_def_id);
2141
2142         // Find the self type for the impl.
2143         let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty;
2144         let impl_self_ty = impl_self_ty.subst(self.tcx(), &impl_substs);
2145
2146         debug!("match_impl_self_types(obligation_self_ty={}, impl_self_ty={})",
2147                obligation_self_ty.repr(self.tcx()),
2148                impl_self_ty.repr(self.tcx()));
2149
2150         match self.match_self_types(obligation_cause,
2151                                     impl_self_ty,
2152                                     obligation_self_ty) {
2153             Ok(()) => {
2154                 debug!("Matched impl_substs={}", impl_substs.repr(self.tcx()));
2155                 Ok(impl_substs)
2156             }
2157             Err(()) => {
2158                 debug!("NoMatch");
2159                 Err(())
2160             }
2161         }
2162     }
2163
2164     fn match_self_types(&mut self,
2165                         cause: &ObligationCause,
2166
2167                         // The self type provided by the impl/caller-obligation:
2168                         provided_self_ty: Ty<'tcx>,
2169
2170                         // The self type the obligation is for:
2171                         required_self_ty: Ty<'tcx>)
2172                         -> Result<(),()>
2173     {
2174         // FIXME(#5781) -- equating the types is stronger than
2175         // necessary. Should consider variance of trait w/r/t Self.
2176
2177         let origin = infer::RelateSelfType(cause.span);
2178         match self.infcx.eq_types(false,
2179                                   origin,
2180                                   provided_self_ty,
2181                                   required_self_ty) {
2182             Ok(()) => Ok(()),
2183             Err(_) => Err(()),
2184         }
2185     }
2186
2187     ///////////////////////////////////////////////////////////////////////////
2188     // Miscellany
2189
2190     fn push_stack<'o,'s:'o>(&mut self,
2191                             previous_stack: Option<&'s TraitObligationStack<'s, 'tcx>>,
2192                             obligation: &'o TraitObligation<'tcx>)
2193                             -> TraitObligationStack<'o, 'tcx>
2194     {
2195         let fresh_trait_ref =
2196             obligation.predicate.to_poly_trait_ref().fold_with(&mut self.freshener);
2197
2198         TraitObligationStack {
2199             obligation: obligation,
2200             fresh_trait_ref: fresh_trait_ref,
2201             previous: previous_stack.map(|p| p), // FIXME variance
2202         }
2203     }
2204
2205     /// Returns set of all impls for a given trait.
2206     fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
2207         ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_def_id);
2208
2209         match self.tcx().trait_impls.borrow().get(&trait_def_id) {
2210             None => Vec::new(),
2211             Some(impls) => impls.borrow().clone()
2212         }
2213     }
2214
2215     fn closure_trait_ref(&self,
2216                          obligation: &TraitObligation<'tcx>,
2217                          closure_def_id: ast::DefId,
2218                          substs: &Substs<'tcx>)
2219                          -> ty::PolyTraitRef<'tcx>
2220     {
2221         let closure_type = self.closure_typer.closure_type(closure_def_id, substs);
2222         let ty::Binder((trait_ref, _)) =
2223             util::closure_trait_ref_and_return_type(self.tcx(),
2224                                                     obligation.predicate.def_id(),
2225                                                     obligation.predicate.0.self_ty(), // (1)
2226                                                     &closure_type.sig,
2227                                                     util::TupleArgumentsFlag::No);
2228
2229         // (1) Feels icky to skip the binder here, but OTOH we know
2230         // that the self-type is an unboxed closure type and hence is
2231         // in fact unparameterized (or at least does not reference any
2232         // regions bound in the obligation). Still probably some
2233         // refactoring could make this nicer.
2234
2235         ty::Binder(trait_ref)
2236     }
2237
2238     fn impl_obligations(&mut self,
2239                         cause: ObligationCause<'tcx>,
2240                         recursion_depth: uint,
2241                         impl_def_id: ast::DefId,
2242                         impl_substs: &Substs<'tcx>,
2243                         skol_map: infer::SkolemizationMap,
2244                         snapshot: &infer::CombinedSnapshot)
2245                         -> VecPerParamSpace<PredicateObligation<'tcx>>
2246     {
2247         let impl_bounds = ty::lookup_predicates(self.tcx(), impl_def_id);
2248         let bounds = impl_bounds.instantiate(self.tcx(), impl_substs);
2249         let normalized_bounds =
2250             project::normalize_with_depth(self, cause.clone(), recursion_depth, &bounds);
2251         let normalized_bounds =
2252             self.infcx().plug_leaks(skol_map, snapshot, &normalized_bounds);
2253         let mut impl_obligations =
2254             util::predicates_for_generics(self.tcx(),
2255                                           cause,
2256                                           recursion_depth,
2257                                           &normalized_bounds.value);
2258         impl_obligations.extend(TypeSpace, normalized_bounds.obligations.into_iter());
2259         impl_obligations
2260     }
2261
2262     #[allow(unused_comparisons)]
2263     fn derived_cause(&self,
2264                      obligation: &TraitObligation<'tcx>,
2265                      variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>)
2266                      -> ObligationCause<'tcx>
2267     {
2268         /*!
2269          * Creates a cause for obligations that are derived from
2270          * `obligation` by a recursive search (e.g., for a builtin
2271          * bound, or eventually a `impl Foo for ..`). If `obligation`
2272          * is itself a derived obligation, this is just a clone, but
2273          * otherwise we create a "derived obligation" cause so as to
2274          * keep track of the original root obligation for error
2275          * reporting.
2276          */
2277
2278         // NOTE(flaper87): As of now, it keeps track of the whole error
2279         // chain. Ideally, we should have a way to configure this either
2280         // by using -Z verbose or just a CLI argument.
2281         if obligation.recursion_depth >= 0 {
2282             let derived_cause = DerivedObligationCause {
2283                 parent_trait_ref: obligation.predicate.to_poly_trait_ref(),
2284                 parent_code: Rc::new(obligation.cause.code.clone()),
2285             };
2286             ObligationCause::new(obligation.cause.span,
2287                                  obligation.cause.body_id,
2288                                  variant(derived_cause))
2289         } else {
2290             obligation.cause.clone()
2291         }
2292     }
2293 }
2294
2295 impl<'tcx> Repr<'tcx> for SelectionCandidate<'tcx> {
2296     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2297         match *self {
2298             ErrorCandidate => format!("ErrorCandidate"),
2299             BuiltinCandidate(b) => format!("BuiltinCandidate({:?})", b),
2300             ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
2301             ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
2302             ProjectionCandidate => format!("ProjectionCandidate"),
2303             FnPointerCandidate => format!("FnPointerCandidate"),
2304             ObjectCandidate => {
2305                 format!("ObjectCandidate")
2306             }
2307             ClosureCandidate(c, ref s) => {
2308                 format!("ClosureCandidate({:?},{})", c, s.repr(tcx))
2309             }
2310         }
2311     }
2312 }
2313
2314 impl<'tcx> SelectionCache<'tcx> {
2315     pub fn new() -> SelectionCache<'tcx> {
2316         SelectionCache {
2317             hashmap: RefCell::new(HashMap::new())
2318         }
2319     }
2320 }
2321
2322 impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> {
2323     fn iter(&self) -> Option<&TraitObligationStack<'o, 'tcx>> {
2324         Some(self)
2325     }
2326 }
2327
2328 impl<'o, 'tcx> Iterator for Option<&'o TraitObligationStack<'o, 'tcx>> {
2329     type Item = &'o TraitObligationStack<'o,'tcx>;
2330
2331     fn next(&mut self) -> Option<&'o TraitObligationStack<'o, 'tcx>> {
2332         match *self {
2333             Some(o) => {
2334                 *self = o.previous;
2335                 Some(o)
2336             }
2337             None => {
2338                 None
2339             }
2340         }
2341     }
2342 }
2343
2344 impl<'o, 'tcx> Repr<'tcx> for TraitObligationStack<'o, 'tcx> {
2345     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2346         format!("TraitObligationStack({})",
2347                 self.obligation.repr(tcx))
2348     }
2349 }
2350
2351 impl<'tcx> EvaluationResult<'tcx> {
2352     fn may_apply(&self) -> bool {
2353         match *self {
2354             EvaluatedToOk |
2355             EvaluatedToAmbig |
2356             EvaluatedToErr(Overflow) |
2357             EvaluatedToErr(OutputTypeParameterMismatch(..)) => {
2358                 true
2359             }
2360             EvaluatedToErr(Unimplemented) => {
2361                 false
2362             }
2363         }
2364     }
2365 }
2366
2367 impl MethodMatchResult {
2368     pub fn may_apply(&self) -> bool {
2369         match *self {
2370             MethodMatched(_) => true,
2371             MethodAmbiguous(_) => true,
2372             MethodDidNotMatch => false,
2373         }
2374     }
2375 }