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_trait(ref data) => {
1277                 match bound {
1278                     ty::BoundSized => {
1279                         Err(Unimplemented)
1280                     }
1281                     ty::BoundCopy | ty::BoundSync | ty::BoundSend => {
1282                         if data.bounds.builtin_bounds.contains(&bound) {
1283                             Ok(If(Vec::new()))
1284                         } else {
1285                             // Recursively check all supertraits to find out if any further
1286                             // bounds are required and thus we must fulfill.
1287                             let principal =
1288                                 data.principal_trait_ref_with_self_ty(self.tcx(),
1289                                                                       self.tcx().types.err);
1290                             for tr in util::supertraits(self.tcx(), principal) {
1291                                 let td = ty::lookup_trait_def(self.tcx(), tr.def_id());
1292                                 if td.bounds.builtin_bounds.contains(&bound) {
1293                                     return Ok(If(Vec::new()))
1294                                 }
1295                             }
1296
1297                             Err(Unimplemented)
1298                         }
1299                     }
1300                 }
1301             }
1302
1303             ty::ty_rptr(_, ty::mt { ty: referent_ty, mutbl }) => {
1304                 // &mut T or &T
1305                 match bound {
1306                     ty::BoundCopy => {
1307                         match mutbl {
1308                             // &mut T is affine and hence never `Copy`
1309                             ast::MutMutable => {
1310                                 Err(Unimplemented)
1311                             }
1312
1313                             // &T is always copyable
1314                             ast::MutImmutable => {
1315                                 Ok(If(Vec::new()))
1316                             }
1317                         }
1318                     }
1319
1320                     ty::BoundSized => {
1321                         Ok(If(Vec::new()))
1322                     }
1323
1324                     ty::BoundSync |
1325                     ty::BoundSend => {
1326                         // Note: technically, a region pointer is only
1327                         // sendable if it has lifetime
1328                         // `'static`. However, we don't take regions
1329                         // into account when doing trait matching:
1330                         // instead, when we decide that `T : Send`, we
1331                         // will register a separate constraint with
1332                         // the region inferencer that `T : 'static`
1333                         // holds as well (because the trait `Send`
1334                         // requires it). This will ensure that there
1335                         // is no borrowed data in `T` (or else report
1336                         // an inference error). The reason we do it
1337                         // this way is that we do not yet *know* what
1338                         // lifetime the borrowed reference has, since
1339                         // we haven't finished running inference -- in
1340                         // other words, there's a kind of
1341                         // chicken-and-egg problem.
1342                         Ok(If(vec![referent_ty]))
1343                     }
1344                 }
1345             }
1346
1347             ty::ty_vec(element_ty, ref len) => {
1348                 // [T, ..n] and [T]
1349                 match bound {
1350                     ty::BoundCopy => {
1351                         match *len {
1352                             Some(_) => {
1353                                 // [T, ..n] is copy iff T is copy
1354                                 Ok(If(vec![element_ty]))
1355                             }
1356                             None => {
1357                                 // [T] is unsized and hence affine
1358                                 Err(Unimplemented)
1359                             }
1360                         }
1361                     }
1362
1363                     ty::BoundSized => {
1364                         if len.is_some() {
1365                             Ok(If(Vec::new()))
1366                         } else {
1367                             Err(Unimplemented)
1368                         }
1369                     }
1370
1371                     ty::BoundSync |
1372                     ty::BoundSend => {
1373                         Ok(If(vec![element_ty]))
1374                     }
1375                 }
1376             }
1377
1378             ty::ty_str => {
1379                 // Equivalent to [u8]
1380                 match bound {
1381                     ty::BoundSync |
1382                     ty::BoundSend => {
1383                         Ok(If(Vec::new()))
1384                     }
1385
1386                     ty::BoundCopy |
1387                     ty::BoundSized => {
1388                         Err(Unimplemented)
1389                     }
1390                 }
1391             }
1392
1393             ty::ty_tup(ref tys) => {
1394                 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1395                 Ok(If(tys.clone()))
1396             }
1397
1398             ty::ty_unboxed_closure(def_id, _, substs) => {
1399                 // FIXME -- This case is tricky. In the case of by-ref
1400                 // closures particularly, we need the results of
1401                 // inference to decide how to reflect the type of each
1402                 // upvar (the upvar may have type `T`, but the runtime
1403                 // type could be `&mut`, `&`, or just `T`). For now,
1404                 // though, we'll do this unsoundly and assume that all
1405                 // captures are by value. Really what we ought to do
1406                 // is reserve judgement and then intertwine this
1407                 // analysis with closure inference.
1408                 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
1409
1410                 // Unboxed closures shouldn't be
1411                 // implicitly copyable
1412                 if bound == ty::BoundCopy {
1413                     return Ok(ParameterBuiltin);
1414                 }
1415
1416                 match self.closure_typer.unboxed_closure_upvars(def_id, substs) {
1417                     Some(upvars) => {
1418                         Ok(If(upvars.iter().map(|c| c.ty).collect()))
1419                     }
1420                     None => {
1421                         Ok(AmbiguousBuiltin)
1422                     }
1423                 }
1424             }
1425
1426             ty::ty_struct(def_id, substs) => {
1427                 let types: Vec<Ty> =
1428                     ty::struct_fields(self.tcx(), def_id, substs).iter()
1429                                                                  .map(|f| f.mt.ty)
1430                                                                  .collect();
1431                 nominal(self, bound, def_id, types)
1432             }
1433
1434             ty::ty_enum(def_id, substs) => {
1435                 let types: Vec<Ty> =
1436                     ty::substd_enum_variants(self.tcx(), def_id, substs)
1437                     .iter()
1438                     .flat_map(|variant| variant.args.iter())
1439                     .map(|&ty| ty)
1440                     .collect();
1441                 nominal(self, bound, def_id, types)
1442             }
1443
1444             ty::ty_projection(_) |
1445             ty::ty_param(_) => {
1446                 // Note: A type parameter is only considered to meet a
1447                 // particular bound if there is a where clause telling
1448                 // us that it does, and that case is handled by
1449                 // `assemble_candidates_from_caller_bounds()`.
1450                 Ok(ParameterBuiltin)
1451             }
1452
1453             ty::ty_infer(ty::TyVar(_)) => {
1454                 // Unbound type variable. Might or might not have
1455                 // applicable impls and so forth, depending on what
1456                 // those type variables wind up being bound to.
1457                 Ok(AmbiguousBuiltin)
1458             }
1459
1460             ty::ty_err => {
1461                 Ok(If(Vec::new()))
1462             }
1463
1464             ty::ty_open(_) |
1465             ty::ty_infer(ty::FreshTy(_)) |
1466             ty::ty_infer(ty::FreshIntTy(_)) => {
1467                 self.tcx().sess.bug(
1468                     format!(
1469                         "asked to assemble builtin bounds of unexpected type: {}",
1470                         self_ty.repr(self.tcx()))[]);
1471             }
1472         };
1473
1474         fn nominal<'cx, 'tcx>(this: &mut SelectionContext<'cx, 'tcx>,
1475                               bound: ty::BuiltinBound,
1476                               def_id: ast::DefId,
1477                               types: Vec<Ty<'tcx>>)
1478                               -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1479         {
1480             // First check for markers and other nonsense.
1481             let tcx = this.tcx();
1482             match bound {
1483                 ty::BoundSend => {
1484                     if
1485                         Some(def_id) == tcx.lang_items.no_send_bound() ||
1486                         Some(def_id) == tcx.lang_items.managed_bound()
1487                     {
1488                         return Err(Unimplemented)
1489                     }
1490                 }
1491
1492                 ty::BoundCopy => {
1493                     // This is an Opt-In Built-In Trait. So, unless
1494                     // the user is asking for the old behavior, we
1495                     // don't supply any form of builtin impl.
1496                     if !this.tcx().sess.features.borrow().opt_out_copy {
1497                         return Ok(ParameterBuiltin)
1498                     } else {
1499                         // Older, backwards compatibility behavior:
1500                         if
1501                             Some(def_id) == tcx.lang_items.no_copy_bound() ||
1502                             Some(def_id) == tcx.lang_items.managed_bound() ||
1503                             ty::has_dtor(tcx, def_id)
1504                         {
1505                             return Err(Unimplemented);
1506                         }
1507                     }
1508                 }
1509
1510                 ty::BoundSync => {
1511                     if
1512                         Some(def_id) == tcx.lang_items.no_sync_bound() ||
1513                         Some(def_id) == tcx.lang_items.managed_bound() ||
1514                         Some(def_id) == tcx.lang_items.unsafe_type()
1515                     {
1516                         return Err(Unimplemented)
1517                     }
1518                 }
1519
1520                 ty::BoundSized => { }
1521             }
1522
1523             Ok(If(types))
1524         }
1525     }
1526
1527     ///////////////////////////////////////////////////////////////////////////
1528     // CONFIRMATION
1529     //
1530     // Confirmation unifies the output type parameters of the trait
1531     // with the values found in the obligation, possibly yielding a
1532     // type error.  See `doc.rs` for more details.
1533
1534     fn confirm_candidate(&mut self,
1535                          obligation: &TraitObligation<'tcx>,
1536                          candidate: SelectionCandidate<'tcx>)
1537                          -> Result<Selection<'tcx>,SelectionError<'tcx>>
1538     {
1539         debug!("confirm_candidate({}, {})",
1540                obligation.repr(self.tcx()),
1541                candidate.repr(self.tcx()));
1542
1543         match candidate {
1544             BuiltinCandidate(builtin_bound) => {
1545                 Ok(VtableBuiltin(
1546                     try!(self.confirm_builtin_candidate(obligation, builtin_bound))))
1547             }
1548
1549             ErrorCandidate => {
1550                 Ok(VtableBuiltin(VtableBuiltinData { nested: VecPerParamSpace::empty() }))
1551             }
1552
1553             ParamCandidate(param) => {
1554                 self.confirm_param_candidate(obligation, param);
1555                 Ok(VtableParam)
1556             }
1557
1558             ImplCandidate(impl_def_id) => {
1559                 let vtable_impl =
1560                     try!(self.confirm_impl_candidate(obligation, impl_def_id));
1561                 Ok(VtableImpl(vtable_impl))
1562             }
1563
1564             UnboxedClosureCandidate(closure_def_id, substs) => {
1565                 try!(self.confirm_unboxed_closure_candidate(obligation, closure_def_id, &substs));
1566                 Ok(VtableUnboxedClosure(closure_def_id, substs))
1567             }
1568
1569             ObjectCandidate => {
1570                 let data = self.confirm_object_candidate(obligation);
1571                 Ok(VtableObject(data))
1572             }
1573
1574             FnPointerCandidate => {
1575                 let fn_type =
1576                     try!(self.confirm_fn_pointer_candidate(obligation));
1577                 Ok(VtableFnPointer(fn_type))
1578             }
1579
1580             ProjectionCandidate => {
1581                 self.confirm_projection_candidate(obligation);
1582                 Ok(VtableParam)
1583             }
1584         }
1585     }
1586
1587     fn confirm_projection_candidate(&mut self,
1588                                     obligation: &TraitObligation<'tcx>)
1589     {
1590         let _: Result<(),()> =
1591             self.infcx.try(|snapshot| {
1592                 let result =
1593                     self.match_projection_obligation_against_bounds_from_trait(obligation,
1594                                                                                snapshot);
1595                 assert!(result);
1596                 Ok(())
1597             });
1598     }
1599
1600     fn confirm_param_candidate(&mut self,
1601                                obligation: &TraitObligation<'tcx>,
1602                                param: ty::PolyTraitRef<'tcx>)
1603     {
1604         debug!("confirm_param_candidate({},{})",
1605                obligation.repr(self.tcx()),
1606                param.repr(self.tcx()));
1607
1608         // During evaluation, we already checked that this
1609         // where-clause trait-ref could be unified with the obligation
1610         // trait-ref. Repeat that unification now without any
1611         // transactional boundary; it should not fail.
1612         match self.confirm_poly_trait_refs(obligation.cause.clone(),
1613                                            obligation.predicate.to_poly_trait_ref(),
1614                                            param.clone()) {
1615             Ok(()) => { }
1616             Err(_) => {
1617                 self.tcx().sess.bug(
1618                     format!("Where clause `{}` was applicable to `{}` but now is not",
1619                             param.repr(self.tcx()),
1620                             obligation.repr(self.tcx())).as_slice());
1621             }
1622         }
1623     }
1624
1625     fn confirm_builtin_candidate(&mut self,
1626                                  obligation: &TraitObligation<'tcx>,
1627                                  bound: ty::BuiltinBound)
1628                                  -> Result<VtableBuiltinData<PredicateObligation<'tcx>>,
1629                                            SelectionError<'tcx>>
1630     {
1631         debug!("confirm_builtin_candidate({})",
1632                obligation.repr(self.tcx()));
1633
1634         match try!(self.builtin_bound(bound, obligation)) {
1635             If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)),
1636             AmbiguousBuiltin | ParameterBuiltin => {
1637                 self.tcx().sess.span_bug(
1638                     obligation.cause.span,
1639                     format!("builtin bound for {} was ambig",
1640                             obligation.repr(self.tcx()))[]);
1641             }
1642         }
1643     }
1644
1645     fn vtable_builtin_data(&mut self,
1646                            obligation: &TraitObligation<'tcx>,
1647                            bound: ty::BuiltinBound,
1648                            nested: Vec<Ty<'tcx>>)
1649                            -> VtableBuiltinData<PredicateObligation<'tcx>>
1650     {
1651         let derived_cause = self.derived_cause(obligation, BuiltinDerivedObligation);
1652         let obligations = nested.iter().map(|&bound_ty| {
1653             // the obligation might be higher-ranked, e.g. for<'a> &'a
1654             // int : Copy. In that case, we will wind up with
1655             // late-bound regions in the `nested` vector. So for each
1656             // one we instantiate to a skolemized region, do our work
1657             // to produce something like `&'0 int : Copy`, and then
1658             // re-bind it. This is a bit of busy-work but preserves
1659             // the invariant that we only manipulate free regions, not
1660             // bound ones.
1661             self.infcx.try(|snapshot| {
1662                 let (skol_ty, skol_map) =
1663                     self.infcx().skolemize_late_bound_regions(&ty::Binder(bound_ty), snapshot);
1664                 let skol_predicate =
1665                     util::predicate_for_builtin_bound(
1666                         self.tcx(),
1667                         derived_cause.clone(),
1668                         bound,
1669                         obligation.recursion_depth + 1,
1670                         skol_ty);
1671                 match skol_predicate {
1672                     Ok(skol_predicate) => Ok(self.infcx().plug_leaks(skol_map, snapshot,
1673                                                                      &skol_predicate)),
1674                     Err(ErrorReported) => Err(ErrorReported)
1675                 }
1676             })
1677         }).collect::<Result<_, _>>();
1678         let mut obligations = match obligations {
1679             Ok(o) => o,
1680             Err(ErrorReported) => Vec::new()
1681         };
1682
1683         // as a special case, `Send` requires `'static`
1684         if bound == ty::BoundSend {
1685             obligations.push(Obligation {
1686                 cause: obligation.cause.clone(),
1687                 recursion_depth: obligation.recursion_depth+1,
1688                 predicate: ty::Binder(ty::OutlivesPredicate(obligation.self_ty(),
1689                                                             ty::ReStatic)).as_predicate(),
1690             });
1691         }
1692
1693         let obligations = VecPerParamSpace::new(obligations, Vec::new(), Vec::new());
1694
1695         debug!("vtable_builtin_data: obligations={}",
1696                obligations.repr(self.tcx()));
1697
1698         VtableBuiltinData { nested: obligations }
1699     }
1700
1701     fn confirm_impl_candidate(&mut self,
1702                               obligation: &TraitObligation<'tcx>,
1703                               impl_def_id: ast::DefId)
1704                               -> Result<VtableImplData<'tcx, PredicateObligation<'tcx>>,
1705                                         SelectionError<'tcx>>
1706     {
1707         debug!("confirm_impl_candidate({},{})",
1708                obligation.repr(self.tcx()),
1709                impl_def_id.repr(self.tcx()));
1710
1711         // First, create the substitutions by matching the impl again,
1712         // this time not in a probe.
1713         self.infcx.try(|snapshot| {
1714             let (skol_obligation_trait_ref, skol_map) =
1715                 self.infcx().skolemize_late_bound_regions(&obligation.predicate, snapshot);
1716             let substs =
1717                 self.rematch_impl(impl_def_id, obligation,
1718                                   snapshot, &skol_map, skol_obligation_trait_ref.trait_ref);
1719             debug!("confirm_impl_candidate substs={}", substs);
1720             Ok(self.vtable_impl(impl_def_id, substs, obligation.cause.clone(),
1721                                 obligation.recursion_depth + 1, skol_map, snapshot))
1722         })
1723     }
1724
1725     fn vtable_impl(&mut self,
1726                    impl_def_id: ast::DefId,
1727                    substs: Substs<'tcx>,
1728                    cause: ObligationCause<'tcx>,
1729                    recursion_depth: uint,
1730                    skol_map: infer::SkolemizationMap,
1731                    snapshot: &infer::CombinedSnapshot)
1732                    -> VtableImplData<'tcx, PredicateObligation<'tcx>>
1733     {
1734         debug!("vtable_impl(impl_def_id={}, substs={}, recursion_depth={}, skol_map={})",
1735                impl_def_id.repr(self.tcx()),
1736                substs.repr(self.tcx()),
1737                recursion_depth,
1738                skol_map.repr(self.tcx()));
1739
1740         let impl_predicates =
1741             self.impl_predicates(cause,
1742                                  recursion_depth,
1743                                  impl_def_id,
1744                                  &substs,
1745                                  skol_map,
1746                                  snapshot);
1747
1748         debug!("vtable_impl: impl_def_id={} impl_predicates={}",
1749                impl_def_id.repr(self.tcx()),
1750                impl_predicates.repr(self.tcx()));
1751
1752         VtableImplData { impl_def_id: impl_def_id,
1753                          substs: substs,
1754                          nested: impl_predicates }
1755     }
1756
1757     fn confirm_object_candidate(&mut self,
1758                                 obligation: &TraitObligation<'tcx>)
1759                                 -> VtableObjectData<'tcx>
1760     {
1761         debug!("confirm_object_candidate({})",
1762                obligation.repr(self.tcx()));
1763
1764         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1765         let poly_trait_ref = match self_ty.sty {
1766             ty::ty_trait(ref data) => {
1767                 data.principal_trait_ref_with_self_ty(self.tcx(), self_ty)
1768             }
1769             _ => {
1770                 self.tcx().sess.span_bug(obligation.cause.span,
1771                                          "object candidate with non-object");
1772             }
1773         };
1774
1775         let obligation_def_id = obligation.predicate.def_id();
1776         let upcast_trait_ref = match util::upcast(self.tcx(),
1777                                                   poly_trait_ref.clone(),
1778                                                   obligation_def_id) {
1779             Some(r) => r,
1780             None => {
1781                 self.tcx().sess.span_bug(obligation.cause.span,
1782                                          format!("unable to upcast from {} to {}",
1783                                                  poly_trait_ref.repr(self.tcx()),
1784                                                  obligation_def_id.repr(self.tcx())).as_slice());
1785             }
1786         };
1787
1788         match self.match_poly_trait_ref(obligation, upcast_trait_ref) {
1789             Ok(()) => { }
1790             Err(()) => {
1791                 self.tcx().sess.span_bug(obligation.cause.span,
1792                                          "failed to match trait refs");
1793             }
1794         }
1795
1796         VtableObjectData { object_ty: self_ty }
1797     }
1798
1799     fn confirm_fn_pointer_candidate(&mut self,
1800                                     obligation: &TraitObligation<'tcx>)
1801                                     -> Result<ty::Ty<'tcx>,SelectionError<'tcx>>
1802     {
1803         debug!("confirm_fn_pointer_candidate({})",
1804                obligation.repr(self.tcx()));
1805
1806         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1807         let sig = match self_ty.sty {
1808             ty::ty_bare_fn(_, &ty::BareFnTy {
1809                 unsafety: ast::Unsafety::Normal,
1810                 abi: abi::Rust,
1811                 ref sig
1812             }) => {
1813                 sig
1814             }
1815             _ => {
1816                 self.tcx().sess.span_bug(
1817                     obligation.cause.span,
1818                     format!("Fn pointer candidate for inappropriate self type: {}",
1819                             self_ty.repr(self.tcx()))[]);
1820             }
1821         };
1822
1823         let arguments_tuple = ty::mk_tup(self.tcx(), sig.0.inputs.to_vec());
1824         let output_type = sig.0.output.unwrap();
1825         let substs =
1826             Substs::new_trait(
1827                 vec![arguments_tuple, output_type],
1828                 vec![],
1829                 self_ty);
1830         let trait_ref = ty::Binder(Rc::new(ty::TraitRef {
1831             def_id: obligation.predicate.def_id(),
1832             substs: self.tcx().mk_substs(substs),
1833         }));
1834
1835         try!(self.confirm_poly_trait_refs(obligation.cause.clone(),
1836                                           obligation.predicate.to_poly_trait_ref(),
1837                                           trait_ref));
1838         Ok(self_ty)
1839     }
1840
1841     fn confirm_unboxed_closure_candidate(&mut self,
1842                                          obligation: &TraitObligation<'tcx>,
1843                                          closure_def_id: ast::DefId,
1844                                          substs: &Substs<'tcx>)
1845                                          -> Result<(),SelectionError<'tcx>>
1846     {
1847         debug!("confirm_unboxed_closure_candidate({},{},{})",
1848                obligation.repr(self.tcx()),
1849                closure_def_id.repr(self.tcx()),
1850                substs.repr(self.tcx()));
1851
1852         let closure_type = self.closure_typer.unboxed_closure_type(closure_def_id, substs);
1853
1854         debug!("confirm_unboxed_closure_candidate: closure_def_id={} closure_type={}",
1855                closure_def_id.repr(self.tcx()),
1856                closure_type.repr(self.tcx()));
1857
1858         let closure_sig = &closure_type.sig;
1859         let arguments_tuple = closure_sig.0.inputs[0];
1860         let trait_substs =
1861             Substs::new_trait(
1862                 vec![arguments_tuple, closure_sig.0.output.unwrap()],
1863                 vec![],
1864                 obligation.self_ty());
1865         let trait_ref = ty::Binder(Rc::new(ty::TraitRef {
1866             def_id: obligation.predicate.def_id(),
1867             substs: self.tcx().mk_substs(trait_substs),
1868         }));
1869
1870         debug!("confirm_unboxed_closure_candidate(closure_def_id={}, trait_ref={})",
1871                closure_def_id.repr(self.tcx()),
1872                trait_ref.repr(self.tcx()));
1873
1874         self.confirm_poly_trait_refs(obligation.cause.clone(),
1875                                      obligation.predicate.to_poly_trait_ref(),
1876                                      trait_ref)
1877     }
1878
1879     /// In the case of unboxed closure types and fn pointers,
1880     /// we currently treat the input type parameters on the trait as
1881     /// outputs. This means that when we have a match we have only
1882     /// considered the self type, so we have to go back and make sure
1883     /// to relate the argument types too.  This is kind of wrong, but
1884     /// since we control the full set of impls, also not that wrong,
1885     /// and it DOES yield better error messages (since we don't report
1886     /// errors as if there is no applicable impl, but rather report
1887     /// errors are about mismatched argument types.
1888     ///
1889     /// Here is an example. Imagine we have an unboxed closure expression
1890     /// and we desugared it so that the type of the expression is
1891     /// `Closure`, and `Closure` expects an int as argument. Then it
1892     /// is "as if" the compiler generated this impl:
1893     ///
1894     ///     impl Fn(int) for Closure { ... }
1895     ///
1896     /// Now imagine our obligation is `Fn(uint) for Closure`. So far
1897     /// we have matched the self-type `Closure`. At this point we'll
1898     /// compare the `int` to `uint` and generate an error.
1899     ///
1900     /// Note that this checking occurs *after* the impl has selected,
1901     /// because these output type parameters should not affect the
1902     /// selection of the impl. Therefore, if there is a mismatch, we
1903     /// report an error to the user.
1904     fn confirm_poly_trait_refs(&mut self,
1905                                obligation_cause: ObligationCause,
1906                                obligation_trait_ref: ty::PolyTraitRef<'tcx>,
1907                                expected_trait_ref: ty::PolyTraitRef<'tcx>)
1908                                -> Result<(), SelectionError<'tcx>>
1909     {
1910         let origin = infer::RelateOutputImplTypes(obligation_cause.span);
1911
1912         let obligation_trait_ref = obligation_trait_ref.clone();
1913         match self.infcx.sub_poly_trait_refs(false,
1914                                              origin,
1915                                              expected_trait_ref.clone(),
1916                                              obligation_trait_ref.clone()) {
1917             Ok(()) => Ok(()),
1918             Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
1919         }
1920     }
1921
1922     ///////////////////////////////////////////////////////////////////////////
1923     // Matching
1924     //
1925     // Matching is a common path used for both evaluation and
1926     // confirmation.  It basically unifies types that appear in impls
1927     // and traits. This does affect the surrounding environment;
1928     // therefore, when used during evaluation, match routines must be
1929     // run inside of a `probe()` so that their side-effects are
1930     // contained.
1931
1932     fn rematch_impl(&mut self,
1933                     impl_def_id: ast::DefId,
1934                     obligation: &TraitObligation<'tcx>,
1935                     snapshot: &infer::CombinedSnapshot,
1936                     skol_map: &infer::SkolemizationMap,
1937                     skol_obligation_trait_ref: Rc<ty::TraitRef<'tcx>>)
1938                     -> Substs<'tcx>
1939     {
1940         match self.match_impl(impl_def_id, obligation, snapshot,
1941                               skol_map, skol_obligation_trait_ref) {
1942             Ok(substs) => {
1943                 substs
1944             }
1945             Err(()) => {
1946                 self.tcx().sess.bug(
1947                     format!("Impl {} was matchable against {} but now is not",
1948                             impl_def_id.repr(self.tcx()),
1949                             obligation.repr(self.tcx()))[]);
1950             }
1951         }
1952     }
1953
1954     fn match_impl(&mut self,
1955                   impl_def_id: ast::DefId,
1956                   obligation: &TraitObligation<'tcx>,
1957                   snapshot: &infer::CombinedSnapshot,
1958                   skol_map: &infer::SkolemizationMap,
1959                   skol_obligation_trait_ref: Rc<ty::TraitRef<'tcx>>)
1960                   -> Result<Substs<'tcx>, ()>
1961     {
1962         let impl_trait_ref = ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
1963
1964         // Before we create the substitutions and everything, first
1965         // consider a "quick reject". This avoids creating more types
1966         // and so forth that we need to.
1967         if self.fast_reject_trait_refs(obligation, &*impl_trait_ref) {
1968             return Err(());
1969         }
1970
1971         let impl_substs = util::fresh_substs_for_impl(self.infcx,
1972                                                       obligation.cause.span,
1973                                                       impl_def_id);
1974
1975         let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
1976                                                   &impl_substs);
1977
1978         debug!("match_impl(impl_def_id={}, obligation={}, \
1979                impl_trait_ref={}, skol_obligation_trait_ref={})",
1980                impl_def_id.repr(self.tcx()),
1981                obligation.repr(self.tcx()),
1982                impl_trait_ref.repr(self.tcx()),
1983                skol_obligation_trait_ref.repr(self.tcx()));
1984
1985         let origin = infer::RelateOutputImplTypes(obligation.cause.span);
1986         match self.infcx.sub_trait_refs(false,
1987                                         origin,
1988                                         impl_trait_ref,
1989                                         skol_obligation_trait_ref) {
1990             Ok(()) => { }
1991             Err(e) => {
1992                 debug!("match_impl: failed sub_trait_refs due to `{}`",
1993                        ty::type_err_to_str(self.tcx(), &e));
1994                 return Err(());
1995             }
1996         }
1997
1998         match self.infcx.leak_check(skol_map, snapshot) {
1999             Ok(()) => { }
2000             Err(e) => {
2001                 debug!("match_impl: failed leak check due to `{}`",
2002                        ty::type_err_to_str(self.tcx(), &e));
2003                 return Err(());
2004             }
2005         }
2006
2007         debug!("match_impl: success impl_substs={}", impl_substs.repr(self.tcx()));
2008         Ok(impl_substs)
2009     }
2010
2011     fn fast_reject_trait_refs(&mut self,
2012                               obligation: &TraitObligation,
2013                               impl_trait_ref: &ty::TraitRef)
2014                               -> bool
2015     {
2016         // We can avoid creating type variables and doing the full
2017         // substitution if we find that any of the input types, when
2018         // simplified, do not match.
2019
2020         obligation.predicate.0.input_types().iter()
2021             .zip(impl_trait_ref.input_types().iter())
2022             .any(|(&obligation_ty, &impl_ty)| {
2023                 let simplified_obligation_ty =
2024                     fast_reject::simplify_type(self.tcx(), obligation_ty, true);
2025                 let simplified_impl_ty =
2026                     fast_reject::simplify_type(self.tcx(), impl_ty, false);
2027
2028                 simplified_obligation_ty.is_some() &&
2029                     simplified_impl_ty.is_some() &&
2030                     simplified_obligation_ty != simplified_impl_ty
2031             })
2032     }
2033
2034     fn match_poly_trait_ref(&mut self,
2035                             obligation: &TraitObligation<'tcx>,
2036                             where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
2037                             -> Result<(),()>
2038     {
2039         debug!("match_poly_trait_ref: obligation={} where_clause_trait_ref={}",
2040                obligation.repr(self.tcx()),
2041                where_clause_trait_ref.repr(self.tcx()));
2042
2043         let origin = infer::RelateOutputImplTypes(obligation.cause.span);
2044         match self.infcx.sub_poly_trait_refs(false,
2045                                              origin,
2046                                              where_clause_trait_ref,
2047                                              obligation.predicate.to_poly_trait_ref()) {
2048             Ok(()) => Ok(()),
2049             Err(_) => Err(()),
2050         }
2051     }
2052
2053     /// Determines whether the self type declared against
2054     /// `impl_def_id` matches `obligation_self_ty`. If successful,
2055     /// returns the substitutions used to make them match. See
2056     /// `match_impl()`. For example, if `impl_def_id` is declared
2057     /// as:
2058     ///
2059     ///    impl<T:Copy> Foo for ~T { ... }
2060     ///
2061     /// and `obligation_self_ty` is `int`, we'd back an `Err(_)`
2062     /// result. But if `obligation_self_ty` were `~int`, we'd get
2063     /// back `Ok(T=int)`.
2064     fn match_inherent_impl(&mut self,
2065                            impl_def_id: ast::DefId,
2066                            obligation_cause: &ObligationCause,
2067                            obligation_self_ty: Ty<'tcx>)
2068                            -> Result<Substs<'tcx>,()>
2069     {
2070         // Create fresh type variables for each type parameter declared
2071         // on the impl etc.
2072         let impl_substs = util::fresh_substs_for_impl(self.infcx,
2073                                                       obligation_cause.span,
2074                                                       impl_def_id);
2075
2076         // Find the self type for the impl.
2077         let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty;
2078         let impl_self_ty = impl_self_ty.subst(self.tcx(), &impl_substs);
2079
2080         debug!("match_impl_self_types(obligation_self_ty={}, impl_self_ty={})",
2081                obligation_self_ty.repr(self.tcx()),
2082                impl_self_ty.repr(self.tcx()));
2083
2084         match self.match_self_types(obligation_cause,
2085                                     impl_self_ty,
2086                                     obligation_self_ty) {
2087             Ok(()) => {
2088                 debug!("Matched impl_substs={}", impl_substs.repr(self.tcx()));
2089                 Ok(impl_substs)
2090             }
2091             Err(()) => {
2092                 debug!("NoMatch");
2093                 Err(())
2094             }
2095         }
2096     }
2097
2098     fn match_self_types(&mut self,
2099                         cause: &ObligationCause,
2100
2101                         // The self type provided by the impl/caller-obligation:
2102                         provided_self_ty: Ty<'tcx>,
2103
2104                         // The self type the obligation is for:
2105                         required_self_ty: Ty<'tcx>)
2106                         -> Result<(),()>
2107     {
2108         // FIXME(#5781) -- equating the types is stronger than
2109         // necessary. Should consider variance of trait w/r/t Self.
2110
2111         let origin = infer::RelateSelfType(cause.span);
2112         match self.infcx.eq_types(false,
2113                                   origin,
2114                                   provided_self_ty,
2115                                   required_self_ty) {
2116             Ok(()) => Ok(()),
2117             Err(_) => Err(()),
2118         }
2119     }
2120
2121     ///////////////////////////////////////////////////////////////////////////
2122     // Miscellany
2123
2124     fn push_stack<'o,'s:'o>(&mut self,
2125                             previous_stack: Option<&'s TraitObligationStack<'s, 'tcx>>,
2126                             obligation: &'o TraitObligation<'tcx>)
2127                             -> TraitObligationStack<'o, 'tcx>
2128     {
2129         let fresh_trait_ref =
2130             obligation.predicate.to_poly_trait_ref().fold_with(&mut self.freshener);
2131
2132         TraitObligationStack {
2133             obligation: obligation,
2134             fresh_trait_ref: fresh_trait_ref,
2135             previous: previous_stack.map(|p| p), // FIXME variance
2136         }
2137     }
2138
2139     /// Returns set of all impls for a given trait.
2140     fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
2141         ty::populate_implementations_for_trait_if_necessary(self.tcx(),
2142                                                             trait_def_id);
2143         match self.tcx().trait_impls.borrow().get(&trait_def_id) {
2144             None => Vec::new(),
2145             Some(impls) => impls.borrow().clone()
2146         }
2147     }
2148
2149     fn impl_predicates(&mut self,
2150                        cause: ObligationCause<'tcx>,
2151                        recursion_depth: uint,
2152                        impl_def_id: ast::DefId,
2153                        impl_substs: &Substs<'tcx>,
2154                        skol_map: infer::SkolemizationMap,
2155                        snapshot: &infer::CombinedSnapshot)
2156                        -> VecPerParamSpace<PredicateObligation<'tcx>>
2157     {
2158         let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
2159         let bounds = impl_generics.to_bounds(self.tcx(), impl_substs);
2160         let normalized_bounds =
2161             project::normalize_with_depth(self, cause.clone(), recursion_depth, &bounds);
2162         let normalized_bounds =
2163             self.infcx().plug_leaks(skol_map, snapshot, &normalized_bounds);
2164         let mut impl_obligations =
2165             util::predicates_for_generics(self.tcx(),
2166                                           cause,
2167                                           recursion_depth,
2168                                           &normalized_bounds.value);
2169         for obligation in normalized_bounds.obligations.into_iter() {
2170             impl_obligations.push(TypeSpace, obligation);
2171         }
2172         impl_obligations
2173     }
2174
2175     fn fn_family_trait_kind(&self,
2176                             trait_def_id: ast::DefId)
2177                             -> Option<ty::UnboxedClosureKind>
2178     {
2179         let tcx = self.tcx();
2180         if Some(trait_def_id) == tcx.lang_items.fn_trait() {
2181             Some(ty::FnUnboxedClosureKind)
2182         } else if Some(trait_def_id) == tcx.lang_items.fn_mut_trait() {
2183             Some(ty::FnMutUnboxedClosureKind)
2184         } else if Some(trait_def_id) == tcx.lang_items.fn_once_trait() {
2185             Some(ty::FnOnceUnboxedClosureKind)
2186         } else {
2187             None
2188         }
2189     }
2190
2191     #[allow(unused_comparisons)]
2192     fn derived_cause(&self,
2193                      obligation: &TraitObligation<'tcx>,
2194                      variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>)
2195                      -> ObligationCause<'tcx>
2196     {
2197         /*!
2198          * Creates a cause for obligations that are derived from
2199          * `obligation` by a recursive search (e.g., for a builtin
2200          * bound, or eventually a `impl Foo for ..`). If `obligation`
2201          * is itself a derived obligation, this is just a clone, but
2202          * otherwise we create a "derived obligation" cause so as to
2203          * keep track of the original root obligation for error
2204          * reporting.
2205          */
2206
2207         // NOTE(flaper87): As of now, it keeps track of the whole error
2208         // chain. Ideally, we should have a way to configure this either
2209         // by using -Z verbose or just a CLI argument.
2210         if obligation.recursion_depth >= 0 {
2211             let derived_cause = DerivedObligationCause {
2212                 parent_trait_ref: obligation.predicate.to_poly_trait_ref(),
2213                 parent_code: Rc::new(obligation.cause.code.clone()),
2214             };
2215             ObligationCause::new(obligation.cause.span,
2216                                  obligation.cause.body_id,
2217                                  variant(derived_cause))
2218         } else {
2219             obligation.cause.clone()
2220         }
2221     }
2222 }
2223
2224 impl<'tcx> Repr<'tcx> for SelectionCandidate<'tcx> {
2225     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2226         match *self {
2227             ErrorCandidate => format!("ErrorCandidate"),
2228             BuiltinCandidate(b) => format!("BuiltinCandidate({})", b),
2229             ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
2230             ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
2231             ProjectionCandidate => format!("ProjectionCandidate"),
2232             FnPointerCandidate => format!("FnPointerCandidate"),
2233             ObjectCandidate => {
2234                 format!("ObjectCandidate")
2235             }
2236             UnboxedClosureCandidate(c, ref s) => {
2237                 format!("UnboxedClosureCandidate({},{})", c, s.repr(tcx))
2238             }
2239         }
2240     }
2241 }
2242
2243 impl<'tcx> SelectionCache<'tcx> {
2244     pub fn new() -> SelectionCache<'tcx> {
2245         SelectionCache {
2246             hashmap: RefCell::new(HashMap::new())
2247         }
2248     }
2249 }
2250
2251 impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> {
2252     fn iter(&self) -> Option<&TraitObligationStack<'o, 'tcx>> {
2253         Some(self)
2254     }
2255 }
2256
2257 impl<'o, 'tcx> Iterator for Option<&'o TraitObligationStack<'o, 'tcx>> {
2258     type Item = &'o TraitObligationStack<'o,'tcx>;
2259
2260     fn next(&mut self) -> Option<&'o TraitObligationStack<'o, 'tcx>> {
2261         match *self {
2262             Some(o) => {
2263                 *self = o.previous;
2264                 Some(o)
2265             }
2266             None => {
2267                 None
2268             }
2269         }
2270     }
2271 }
2272
2273 impl<'o, 'tcx> Repr<'tcx> for TraitObligationStack<'o, 'tcx> {
2274     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2275         format!("TraitObligationStack({})",
2276                 self.obligation.repr(tcx))
2277     }
2278 }
2279
2280 impl<'tcx> EvaluationResult<'tcx> {
2281     fn may_apply(&self) -> bool {
2282         match *self {
2283             EvaluatedToOk |
2284             EvaluatedToAmbig |
2285             EvaluatedToErr(Overflow) |
2286             EvaluatedToErr(OutputTypeParameterMismatch(..)) => {
2287                 true
2288             }
2289             EvaluatedToErr(Unimplemented) => {
2290                 false
2291             }
2292         }
2293     }
2294 }
2295
2296 impl MethodMatchResult {
2297     pub fn may_apply(&self) -> bool {
2298         match *self {
2299             MethodMatched(_) => true,
2300             MethodAmbiguous(_) => true,
2301             MethodDidNotMatch => false,
2302         }
2303     }
2304 }