src/librustc/middle/traits/select.rs

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