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