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.
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.
11 //! See `doc.rs` for high-level documentation
12 #![allow(dead_code)] // FIXME -- just temporarily
14 pub use self::MethodMatchResult::*;
15 pub use self::MethodMatchedData::*;
16 use self::SelectionCandidate::*;
17 use self::BuiltinBoundConditions::*;
18 use self::EvaluationResult::*;
20 use super::{DerivedObligationCause};
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, VtableClosure,
29 VtableFnPointer, VtableObject};
30 use super::{VtableImplData, VtableObjectData, VtableBuiltinData};
31 use super::object_safety;
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};
39 use middle::infer::{InferCtxt, TypeFreshener};
40 use middle::ty_fold::TypeFoldable;
41 use std::cell::RefCell;
42 use std::collections::hash_map::HashMap;
44 use syntax::{abi, ast};
45 use util::common::ErrorReported;
46 use util::ppaux::Repr;
48 pub struct SelectionContext<'cx, 'tcx:'cx> {
49 infcx: &'cx InferCtxt<'cx, 'tcx>,
50 closure_typer: &'cx (ty::ClosureTyper<'tcx>+'cx),
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>,
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.
76 // A stack that walks back up the stack frame.
77 struct TraitObligationStack<'prev, 'tcx: 'prev> {
78 obligation: &'prev TraitObligation<'tcx>,
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>,
84 previous: Option<&'prev TraitObligationStack<'prev, 'tcx>>
88 pub struct SelectionCache<'tcx> {
89 hashmap: RefCell<HashMap<Rc<ty::TraitRef<'tcx>>,
90 SelectionResult<'tcx, SelectionCandidate<'tcx>>>>,
93 pub enum MethodMatchResult {
94 MethodMatched(MethodMatchedData),
95 MethodAmbiguous(/* list of impls that could apply */ Vec<ast::DefId>),
99 #[derive(Copy, Debug)]
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.
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)
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*.
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.
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,Debug,Clone)]
135 enum SelectionCandidate<'tcx> {
136 BuiltinCandidate(ty::BuiltinBound),
137 ParamCandidate(ty::PolyTraitRef<'tcx>),
138 ImplCandidate(ast::DefId),
140 /// This is a trait matching with a projected type as `Self`, and
141 /// we found an applicable bound in the trait definition.
144 /// Implementation of a `Fn`-family trait by one of the
145 /// anonymous types generated for a `||` expression.
146 ClosureCandidate(/* closure */ ast::DefId, Substs<'tcx>),
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`)
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>>,
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.
169 enum BuiltinBoundConditions<'tcx> {
176 enum EvaluationResult<'tcx> {
179 EvaluatedToErr(SelectionError<'tcx>),
182 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
183 pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>,
184 closure_typer: &'cx ty::ClosureTyper<'tcx>)
185 -> SelectionContext<'cx, 'tcx> {
188 closure_typer: closure_typer,
189 freshener: infcx.freshener(),
194 pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'tcx>,
195 closure_typer: &'cx ty::ClosureTyper<'tcx>)
196 -> SelectionContext<'cx, 'tcx> {
199 closure_typer: closure_typer,
200 freshener: infcx.freshener(),
205 pub fn infcx(&self) -> &'cx InferCtxt<'cx, 'tcx> {
209 pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
213 pub fn param_env(&self) -> &'cx ty::ParameterEnvironment<'cx, 'tcx> {
214 self.closure_typer.param_env()
217 pub fn closure_typer(&self) -> &'cx (ty::ClosureTyper<'tcx>+'cx) {
221 ///////////////////////////////////////////////////////////////////////////
224 // The selection phase tries to identify *how* an obligation will
225 // be resolved. For example, it will identify which impl or
226 // parameter bound is to be used. The process can be inconclusive
227 // if the self type in the obligation is not fully inferred. Selection
228 // can result in an error in one of two ways:
230 // 1. If no applicable impl or parameter bound can be found.
231 // 2. If the output type parameters in the obligation do not match
232 // those specified by the impl/bound. For example, if the obligation
233 // is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
234 // `impl<T> Iterable<T> for Vec<T>`, than an error would result.
236 /// Evaluates whether the obligation can be satisfied. Returns an indication of whether the
237 /// obligation can be satisfied and, if so, by what means. Never affects surrounding typing
239 pub fn select(&mut self, obligation: &TraitObligation<'tcx>)
240 -> SelectionResult<'tcx, Selection<'tcx>> {
241 debug!("select({})", obligation.repr(self.tcx()));
242 assert!(!obligation.predicate.has_escaping_regions());
244 let stack = self.push_stack(None, obligation);
245 match try!(self.candidate_from_obligation(&stack)) {
247 Some(candidate) => Ok(Some(try!(self.confirm_candidate(obligation, candidate)))),
251 ///////////////////////////////////////////////////////////////////////////
254 // Tests whether an obligation can be selected or whether an impl
255 // can be applied to particular types. It skips the "confirmation"
256 // step and hence completely ignores output type parameters.
258 // The result is "true" if the obligation *may* hold and "false" if
259 // we can be sure it does not.
261 /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
262 pub fn evaluate_obligation(&mut self,
263 obligation: &PredicateObligation<'tcx>)
266 debug!("evaluate_obligation({})",
267 obligation.repr(self.tcx()));
269 self.evaluate_predicate_recursively(None, obligation).may_apply()
272 fn evaluate_builtin_bound_recursively<'o>(&mut self,
273 bound: ty::BuiltinBound,
274 previous_stack: &TraitObligationStack<'o, 'tcx>,
276 -> EvaluationResult<'tcx>
279 util::predicate_for_builtin_bound(
281 previous_stack.obligation.cause.clone(),
283 previous_stack.obligation.recursion_depth + 1,
288 self.evaluate_predicate_recursively(Some(previous_stack), &obligation)
290 Err(ErrorReported) => {
296 fn evaluate_predicates_recursively<'a,'o,I>(&mut self,
297 stack: Option<&TraitObligationStack<'o, 'tcx>>,
299 -> EvaluationResult<'tcx>
300 where I : Iterator<Item=&'a PredicateObligation<'tcx>>, 'tcx:'a
302 let mut result = EvaluatedToOk;
303 for obligation in predicates {
304 match self.evaluate_predicate_recursively(stack, obligation) {
305 EvaluatedToErr(e) => { return EvaluatedToErr(e); }
306 EvaluatedToAmbig => { result = EvaluatedToAmbig; }
313 fn evaluate_predicate_recursively<'o>(&mut self,
314 previous_stack: Option<&TraitObligationStack<'o, 'tcx>>,
315 obligation: &PredicateObligation<'tcx>)
316 -> EvaluationResult<'tcx>
318 debug!("evaluate_predicate_recursively({})",
319 obligation.repr(self.tcx()));
321 match obligation.predicate {
322 ty::Predicate::Trait(ref t) => {
323 assert!(!t.has_escaping_regions());
324 let obligation = obligation.with(t.clone());
325 self.evaluate_obligation_recursively(previous_stack, &obligation)
328 ty::Predicate::Equate(ref p) => {
329 let result = self.infcx.probe(|_| {
330 self.infcx.equality_predicate(obligation.cause.span, p)
333 Ok(()) => EvaluatedToOk,
334 Err(_) => EvaluatedToErr(Unimplemented),
338 ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => {
339 // we do not consider region relationships when
340 // evaluating trait matches
344 ty::Predicate::Projection(ref data) => {
345 self.infcx.probe(|_| {
346 let project_obligation = obligation.with(data.clone());
347 match project::poly_project_and_unify_type(self, &project_obligation) {
348 Ok(Some(subobligations)) => {
349 self.evaluate_predicates_recursively(previous_stack,
350 subobligations.iter())
356 EvaluatedToErr(Unimplemented)
364 fn evaluate_obligation_recursively<'o>(&mut self,
365 previous_stack: Option<&TraitObligationStack<'o, 'tcx>>,
366 obligation: &TraitObligation<'tcx>)
367 -> EvaluationResult<'tcx>
369 debug!("evaluate_obligation_recursively({})",
370 obligation.repr(self.tcx()));
372 let stack = self.push_stack(previous_stack.map(|x| x), obligation);
374 let result = self.evaluate_stack(&stack);
376 debug!("result: {:?}", result);
380 fn evaluate_stack<'o>(&mut self,
381 stack: &TraitObligationStack<'o, 'tcx>)
382 -> EvaluationResult<'tcx>
384 // In intercrate mode, whenever any of the types are unbound,
385 // there can always be an impl. Even if there are no impls in
386 // this crate, perhaps the type would be unified with
387 // something from another crate that does provide an impl.
389 // In intracrate mode, we must still be conservative. The reason is
390 // that we want to avoid cycles. Imagine an impl like:
392 // impl<T:Eq> Eq for Vec<T>
394 // and a trait reference like `$0 : Eq` where `$0` is an
395 // unbound variable. When we evaluate this trait-reference, we
396 // will unify `$0` with `Vec<$1>` (for some fresh variable
397 // `$1`), on the condition that `$1 : Eq`. We will then wind
398 // up with many candidates (since that are other `Eq` impls
399 // that apply) and try to winnow things down. This results in
400 // a recursive evaluation that `$1 : Eq` -- as you can
401 // imagine, this is just where we started. To avoid that, we
402 // check for unbound variables and return an ambiguous (hence possible)
403 // match if we've seen this trait before.
405 // This suffices to allow chains like `FnMut` implemented in
406 // terms of `Fn` etc, but we could probably make this more
408 let input_types = stack.fresh_trait_ref.0.input_types();
409 let unbound_input_types = input_types.iter().any(|&t| ty::type_is_fresh(t));
411 unbound_input_types &&
413 stack.iter().skip(1).any(
414 |prev| stack.fresh_trait_ref.def_id() == prev.fresh_trait_ref.def_id()))
416 debug!("evaluate_stack({}) --> unbound argument, recursion --> ambiguous",
417 stack.fresh_trait_ref.repr(self.tcx()));
418 return EvaluatedToAmbig;
421 // If there is any previous entry on the stack that precisely
422 // matches this obligation, then we can assume that the
423 // obligation is satisfied for now (still all other conditions
424 // must be met of course). One obvious case this comes up is
425 // marker traits like `Send`. Think of a linked list:
427 // struct List<T> { data: T, next: Option<Box<List<T>>> {
429 // `Box<List<T>>` will be `Send` if `T` is `Send` and
430 // `Option<Box<List<T>>>` is `Send`, and in turn
431 // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
434 // Note that we do this comparison using the `fresh_trait_ref`
435 // fields. Because these have all been skolemized using
436 // `self.freshener`, we can be sure that (a) this will not
437 // affect the inferencer state and (b) that if we see two
438 // skolemized types with the same index, they refer to the
439 // same unbound type variable.
442 .skip(1) // skip top-most frame
443 .any(|prev| stack.fresh_trait_ref == prev.fresh_trait_ref)
445 debug!("evaluate_stack({}) --> recursive",
446 stack.fresh_trait_ref.repr(self.tcx()));
447 return EvaluatedToOk;
450 match self.candidate_from_obligation(stack) {
451 Ok(Some(c)) => self.winnow_candidate(stack, &c),
452 Ok(None) => EvaluatedToAmbig,
453 Err(e) => EvaluatedToErr(e),
457 /// Evaluates whether the impl with id `impl_def_id` could be applied to the self type
458 /// `obligation_self_ty`. This can be used either for trait or inherent impls.
459 pub fn evaluate_impl(&mut self,
460 impl_def_id: ast::DefId,
461 obligation: &TraitObligation<'tcx>)
464 debug!("evaluate_impl(impl_def_id={}, obligation={})",
465 impl_def_id.repr(self.tcx()),
466 obligation.repr(self.tcx()));
468 self.infcx.probe(|snapshot| {
469 let (skol_obligation_trait_ref, skol_map) =
470 self.infcx().skolemize_late_bound_regions(&obligation.predicate, snapshot);
471 match self.match_impl(impl_def_id, obligation, snapshot,
472 &skol_map, skol_obligation_trait_ref.trait_ref.clone()) {
474 let vtable_impl = self.vtable_impl(impl_def_id,
476 obligation.cause.clone(),
477 obligation.recursion_depth + 1,
480 self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
489 ///////////////////////////////////////////////////////////////////////////
490 // CANDIDATE ASSEMBLY
492 // The selection process begins by examining all in-scope impls,
493 // caller obligations, and so forth and assembling a list of
494 // candidates. See `doc.rs` and the `Candidate` type for more details.
496 fn candidate_from_obligation<'o>(&mut self,
497 stack: &TraitObligationStack<'o, 'tcx>)
498 -> SelectionResult<'tcx, SelectionCandidate<'tcx>>
500 // Watch out for overflow. This intentionally bypasses (and does
501 // not update) the cache.
502 let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
503 if stack.obligation.recursion_depth >= recursion_limit {
504 debug!("{} --> overflow (limit={})",
505 stack.obligation.repr(self.tcx()),
510 // Check the cache. Note that we skolemize the trait-ref
511 // separately rather than using `stack.fresh_trait_ref` -- this
512 // is because we want the unbound variables to be replaced
513 // with fresh skolemized types starting from index 0.
514 let cache_fresh_trait_pred =
515 self.infcx.freshen(stack.obligation.predicate.clone());
516 debug!("candidate_from_obligation(cache_fresh_trait_pred={}, obligation={})",
517 cache_fresh_trait_pred.repr(self.tcx()),
518 stack.repr(self.tcx()));
519 assert!(!stack.obligation.predicate.has_escaping_regions());
521 match self.check_candidate_cache(&cache_fresh_trait_pred) {
523 debug!("CACHE HIT: cache_fresh_trait_pred={}, candidate={}",
524 cache_fresh_trait_pred.repr(self.tcx()),
531 // If no match, compute result and insert into cache.
532 let candidate = self.candidate_from_obligation_no_cache(stack);
534 if self.should_update_candidate_cache(&cache_fresh_trait_pred, &candidate) {
535 debug!("CACHE MISS: cache_fresh_trait_pred={}, candidate={}",
536 cache_fresh_trait_pred.repr(self.tcx()), candidate.repr(self.tcx()));
537 self.insert_candidate_cache(cache_fresh_trait_pred, candidate.clone());
543 fn candidate_from_obligation_no_cache<'o>(&mut self,
544 stack: &TraitObligationStack<'o, 'tcx>)
545 -> SelectionResult<'tcx, SelectionCandidate<'tcx>>
547 if ty::type_is_error(stack.obligation.predicate.0.self_ty()) {
548 return Ok(Some(ErrorCandidate));
551 let candidate_set = try!(self.assemble_candidates(stack));
553 if candidate_set.ambiguous {
554 debug!("candidate set contains ambig");
558 let mut candidates = candidate_set.vec;
560 debug!("assembled {} candidates for {}: {}",
562 stack.repr(self.tcx()),
563 candidates.repr(self.tcx()));
565 // At this point, we know that each of the entries in the
566 // candidate set is *individually* applicable. Now we have to
567 // figure out if they contain mutual incompatibilities. This
568 // frequently arises if we have an unconstrained input type --
569 // for example, we are looking for $0:Eq where $0 is some
570 // unconstrained type variable. In that case, we'll get a
571 // candidate which assumes $0 == int, one that assumes $0 ==
572 // uint, etc. This spells an ambiguity.
574 // If there is more than one candidate, first winnow them down
575 // by considering extra conditions (nested obligations and so
576 // forth). We don't winnow if there is exactly one
577 // candidate. This is a relatively minor distinction but it
578 // can lead to better inference and error-reporting. An
579 // example would be if there was an impl:
581 // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
583 // and we were to see some code `foo.push_clone()` where `boo`
584 // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
585 // we were to winnow, we'd wind up with zero candidates.
586 // Instead, we select the right impl now but report `Bar does
587 // not implement Clone`.
588 if candidates.len() > 1 {
589 candidates.retain(|c| self.winnow_candidate(stack, c).may_apply())
592 // If there are STILL multiple candidate, we can further reduce
593 // the list by dropping duplicates.
594 if candidates.len() > 1 {
596 while i < candidates.len() {
598 (0..candidates.len())
600 .any(|j| self.candidate_should_be_dropped_in_favor_of(stack,
604 debug!("Dropping candidate #{}/{}: {}",
605 i, candidates.len(), candidates[i].repr(self.tcx()));
606 candidates.swap_remove(i);
608 debug!("Retaining candidate #{}/{}: {}",
609 i, candidates.len(), candidates[i].repr(self.tcx()));
615 // If there are *STILL* multiple candidates, give up and
617 if candidates.len() > 1 {
618 debug!("multiple matches, ambig");
623 // If there are *NO* candidates, that there are no impls --
624 // that we know of, anyway. Note that in the case where there
625 // are unbound type variables within the obligation, it might
626 // be the case that you could still satisfy the obligation
627 // from another crate by instantiating the type variables with
628 // a type from another crate that does have an impl. This case
629 // is checked for in `evaluate_stack` (and hence users
630 // who might care about this case, like coherence, should use
632 if candidates.len() == 0 {
633 return Err(Unimplemented);
636 // Just one candidate left.
637 let candidate = candidates.pop().unwrap();
640 ImplCandidate(def_id) => {
641 match ty::trait_impl_polarity(self.tcx(), def_id) {
642 Some(ast::ImplPolarity::Negative) => return Err(Unimplemented),
652 fn pick_candidate_cache(&self,
653 cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>)
654 -> &SelectionCache<'tcx>
656 // High-level idea: we have to decide whether to consult the
657 // cache that is specific to this scope, or to consult the
658 // global cache. We want the cache that is specific to this
659 // scope whenever where clauses might affect the result.
661 // Avoid using the master cache during coherence and just rely
662 // on the local cache. This effectively disables caching
663 // during coherence. It is really just a simplification to
664 // avoid us having to fear that coherence results "pollute"
665 // the master cache. Since coherence executes pretty quickly,
666 // it's not worth going to more trouble to increase the
667 // hit-rate I don't think.
669 return &self.param_env().selection_cache;
672 // If the trait refers to any parameters in scope, then use
673 // the cache of the param-environment.
675 cache_fresh_trait_pred.0.input_types().iter().any(
676 |&t| ty::type_has_self(t) || ty::type_has_params(t))
678 return &self.param_env().selection_cache;
681 // If the trait refers to unbound type variables, and there
682 // are where clauses in scope, then use the local environment.
683 // If there are no where clauses in scope, which is a very
684 // common case, then we can use the global environment.
685 // See the discussion in doc.rs for more details.
687 !self.param_env().caller_bounds.is_empty() &&
688 cache_fresh_trait_pred.0.input_types().iter().any(
689 |&t| ty::type_has_ty_infer(t))
691 return &self.param_env().selection_cache;
694 // Otherwise, we can use the global cache.
695 &self.tcx().selection_cache
698 fn check_candidate_cache(&mut self,
699 cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>)
700 -> Option<SelectionResult<'tcx, SelectionCandidate<'tcx>>>
702 let cache = self.pick_candidate_cache(cache_fresh_trait_pred);
703 let hashmap = cache.hashmap.borrow();
704 hashmap.get(&cache_fresh_trait_pred.0.trait_ref).map(|c| (*c).clone())
707 fn insert_candidate_cache(&mut self,
708 cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
709 candidate: SelectionResult<'tcx, SelectionCandidate<'tcx>>)
711 let cache = self.pick_candidate_cache(&cache_fresh_trait_pred);
712 let mut hashmap = cache.hashmap.borrow_mut();
713 hashmap.insert(cache_fresh_trait_pred.0.trait_ref.clone(), candidate);
716 fn should_update_candidate_cache(&mut self,
717 cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>,
718 candidate: &SelectionResult<'tcx, SelectionCandidate<'tcx>>)
721 // In general, it's a good idea to cache results, even
722 // ambigious ones, to save us some trouble later. But we have
723 // to be careful not to cache results that could be
724 // invalidated later by advances in inference. Normally, this
725 // is not an issue, because any inference variables whose
726 // types are not yet bound are "freshened" in the cache key,
727 // which means that if we later get the same request once that
728 // type variable IS bound, we'll have a different cache key.
729 // For example, if we have `Vec<_#0t> : Foo`, and `_#0t` is
730 // not yet known, we may cache the result as `None`. But if
731 // later `_#0t` is bound to `Bar`, then when we freshen we'll
732 // have `Vec<Bar> : Foo` as the cache key.
734 // HOWEVER, it CAN happen that we get an ambiguity result in
735 // one particular case around closures where the cache key
736 // would not change. That is when the precise types of the
737 // upvars that a closure references have not yet been figured
738 // out (i.e., because it is not yet known if they are captured
739 // by ref, and if by ref, what kind of ref). In these cases,
740 // when matching a builtin bound, we will yield back an
741 // ambiguous result. But the *cache key* is just the closure type,
742 // it doesn't capture the state of the upvar computation.
744 // To avoid this trap, just don't cache ambiguous results if
745 // the self-type contains no inference byproducts (that really
746 // shouldn't happen in other circumstances anyway, given
750 Ok(Some(_)) | Err(_) => true,
752 cache_fresh_trait_pred.0.input_types().iter().any(|&t| ty::type_has_ty_infer(t))
757 fn assemble_candidates<'o>(&mut self,
758 stack: &TraitObligationStack<'o, 'tcx>)
759 -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>>
761 // Check for overflow.
763 let TraitObligationStack { obligation, .. } = *stack;
765 let mut candidates = SelectionCandidateSet {
770 // Other bounds. Consider both in-scope bounds from fn decl
771 // and applicable impls. There is a certain set of precedence rules here.
773 match self.tcx().lang_items.to_builtin_kind(obligation.predicate.def_id()) {
774 Some(ty::BoundCopy) => {
775 debug!("obligation self ty is {}",
776 obligation.predicate.0.self_ty().repr(self.tcx()));
778 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
780 try!(self.assemble_builtin_bound_candidates(ty::BoundCopy,
784 Some(bound @ ty::BoundSend) |
785 Some(bound @ ty::BoundSync) => {
786 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
788 // No explicit impls were declared for this type, consider the fallback rules.
789 if candidates.vec.is_empty() && !candidates.ambiguous {
790 try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
794 Some(bound @ ty::BoundSized) => {
795 // Sized and Copy are always automatically computed.
796 try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
800 // For the time being, we ignore user-defined impls for builtin-bounds, other than
802 // (And unboxed candidates only apply to the Fn/FnMut/etc traits.)
803 try!(self.assemble_closure_candidates(obligation, &mut candidates));
804 try!(self.assemble_fn_pointer_candidates(obligation, &mut candidates));
805 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
806 self.assemble_candidates_from_object_ty(obligation, &mut candidates);
810 self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
811 try!(self.assemble_candidates_from_caller_bounds(stack, &mut candidates));
812 debug!("candidate list size: {}", candidates.vec.len());
816 fn assemble_candidates_from_projected_tys(&mut self,
817 obligation: &TraitObligation<'tcx>,
818 candidates: &mut SelectionCandidateSet<'tcx>)
820 let poly_trait_predicate =
821 self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
823 debug!("assemble_candidates_for_projected_tys({},{})",
824 obligation.repr(self.tcx()),
825 poly_trait_predicate.repr(self.tcx()));
827 // FIXME(#20297) -- just examining the self-type is very simplistic
829 // before we go into the whole skolemization thing, just
830 // quickly check if the self-type is a projection at all.
831 let trait_def_id = match poly_trait_predicate.0.trait_ref.self_ty().sty {
832 ty::ty_projection(ref data) => data.trait_ref.def_id,
833 ty::ty_infer(ty::TyVar(_)) => {
834 // If the self-type is an inference variable, then it MAY wind up
835 // being a projected type, so induce an ambiguity.
837 // FIXME(#20297) -- being strict about this can cause
838 // inference failures with BorrowFrom, which is
839 // unfortunate. Can we do better here?
840 debug!("assemble_candidates_for_projected_tys: ambiguous self-type");
841 candidates.ambiguous = true;
847 debug!("assemble_candidates_for_projected_tys: trait_def_id={}",
848 trait_def_id.repr(self.tcx()));
850 let result = self.infcx.probe(|snapshot| {
851 self.match_projection_obligation_against_bounds_from_trait(obligation,
856 candidates.vec.push(ProjectionCandidate);
860 fn match_projection_obligation_against_bounds_from_trait(
862 obligation: &TraitObligation<'tcx>,
863 snapshot: &infer::CombinedSnapshot)
866 let poly_trait_predicate =
867 self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
868 let (skol_trait_predicate, skol_map) =
869 self.infcx().skolemize_late_bound_regions(&poly_trait_predicate, snapshot);
870 debug!("match_projection_obligation_against_bounds_from_trait: \
871 skol_trait_predicate={} skol_map={}",
872 skol_trait_predicate.repr(self.tcx()),
873 skol_map.repr(self.tcx()));
875 let projection_trait_ref = match skol_trait_predicate.trait_ref.self_ty().sty {
876 ty::ty_projection(ref data) => &data.trait_ref,
878 self.tcx().sess.span_bug(
879 obligation.cause.span,
880 format!("match_projection_obligation_against_bounds_from_trait() called \
881 but self-ty not a projection: {}",
882 skol_trait_predicate.trait_ref.self_ty().repr(self.tcx())).as_slice());
885 debug!("match_projection_obligation_against_bounds_from_trait: \
886 projection_trait_ref={}",
887 projection_trait_ref.repr(self.tcx()));
889 let trait_def = ty::lookup_trait_def(self.tcx(), projection_trait_ref.def_id);
890 let bounds = trait_def.generics.to_bounds(self.tcx(), projection_trait_ref.substs);
891 debug!("match_projection_obligation_against_bounds_from_trait: \
893 bounds.repr(self.tcx()));
896 util::elaborate_predicates(self.tcx(), bounds.predicates.into_vec())
899 |bound| self.infcx.probe(
900 |_| self.match_projection(obligation,
902 skol_trait_predicate.trait_ref.clone(),
906 debug!("match_projection_obligation_against_bounds_from_trait: \
908 matching_bound.repr(self.tcx()));
909 match matching_bound {
912 // Repeat the successful match, if any, this time outside of a probe.
913 let result = self.match_projection(obligation,
915 skol_trait_predicate.trait_ref.clone(),
924 fn match_projection(&mut self,
925 obligation: &TraitObligation<'tcx>,
926 trait_bound: ty::PolyTraitRef<'tcx>,
927 skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
928 skol_map: &infer::SkolemizationMap,
929 snapshot: &infer::CombinedSnapshot)
932 assert!(!skol_trait_ref.has_escaping_regions());
933 let origin = infer::RelateOutputImplTypes(obligation.cause.span);
934 match self.infcx.sub_poly_trait_refs(false,
937 ty::Binder(skol_trait_ref.clone())) {
939 Err(_) => { return false; }
942 self.infcx.leak_check(skol_map, snapshot).is_ok()
945 /// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller
946 /// supplied to find out whether it is listed among them.
948 /// Never affects inference environment.
949 fn assemble_candidates_from_caller_bounds<'o>(&mut self,
950 stack: &TraitObligationStack<'o, 'tcx>,
951 candidates: &mut SelectionCandidateSet<'tcx>)
952 -> Result<(),SelectionError<'tcx>>
954 debug!("assemble_candidates_from_caller_bounds({})",
955 stack.obligation.repr(self.tcx()));
957 let caller_trait_refs: Vec<_> =
958 self.param_env().caller_bounds.iter()
959 .filter_map(|o| o.to_opt_poly_trait_ref())
963 util::transitive_bounds(
964 self.tcx(), &caller_trait_refs[]);
966 let matching_bounds =
968 |bound| self.evaluate_where_clause(stack, bound.clone()).may_apply());
970 let param_candidates =
971 matching_bounds.map(|bound| ParamCandidate(bound));
973 candidates.vec.extend(param_candidates);
978 fn evaluate_where_clause<'o>(&mut self,
979 stack: &TraitObligationStack<'o, 'tcx>,
980 where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
981 -> EvaluationResult<'tcx>
983 self.infcx().probe(move |_| {
984 match self.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) {
986 self.evaluate_predicates_recursively(Some(stack), obligations.iter())
989 EvaluatedToErr(Unimplemented)
995 /// Check for the artificial impl that the compiler will create for an obligation like `X :
996 /// FnMut<..>` where `X` is a closure type.
998 /// Note: the type parameters on a closure candidate are modeled as *output* type
999 /// parameters and hence do not affect whether this trait is a match or not. They will be
1000 /// unified during the confirmation step.
1001 fn assemble_closure_candidates(&mut self,
1002 obligation: &TraitObligation<'tcx>,
1003 candidates: &mut SelectionCandidateSet<'tcx>)
1004 -> Result<(),SelectionError<'tcx>>
1006 let kind = match self.fn_family_trait_kind(obligation.predicate.0.def_id()) {
1008 None => { return Ok(()); }
1011 let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1012 let (closure_def_id, substs) = match self_ty.sty {
1013 ty::ty_closure(id, _, ref substs) => (id, substs.clone()),
1014 ty::ty_infer(ty::TyVar(_)) => {
1015 debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
1016 candidates.ambiguous = true;
1019 _ => { return Ok(()); }
1022 debug!("assemble_unboxed_candidates: self_ty={} kind={:?} obligation={}",
1023 self_ty.repr(self.tcx()),
1025 obligation.repr(self.tcx()));
1027 match self.closure_typer.closure_kind(closure_def_id) {
1028 Some(closure_kind) => {
1029 debug!("assemble_unboxed_candidates: closure_kind = {:?}", closure_kind);
1030 if closure_kind == kind {
1031 candidates.vec.push(ClosureCandidate(closure_def_id, substs.clone()));
1035 debug!("assemble_unboxed_candidates: closure_kind not yet known");
1036 candidates.ambiguous = true;
1043 /// Implement one of the `Fn()` family for a fn pointer.
1044 fn assemble_fn_pointer_candidates(&mut self,
1045 obligation: &TraitObligation<'tcx>,
1046 candidates: &mut SelectionCandidateSet<'tcx>)
1047 -> Result<(),SelectionError<'tcx>>
1049 // We provide a `Fn` impl for fn pointers. There is no need to provide
1050 // the other traits (e.g. `FnMut`) since those are provided by blanket
1052 if Some(obligation.predicate.def_id()) != self.tcx().lang_items.fn_trait() {
1056 let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1058 ty::ty_infer(ty::TyVar(_)) => {
1059 debug!("assemble_fn_pointer_candidates: ambiguous self-type");
1060 candidates.ambiguous = true; // could wind up being a fn() type
1063 // provide an impl, but only for suitable `fn` pointers
1064 ty::ty_bare_fn(_, &ty::BareFnTy {
1065 unsafety: ast::Unsafety::Normal,
1067 sig: ty::Binder(ty::FnSig {
1069 output: ty::FnConverging(_),
1073 candidates.vec.push(FnPointerCandidate);
1082 /// Search for impls that might apply to `obligation`.
1083 fn assemble_candidates_from_impls(&mut self,
1084 obligation: &TraitObligation<'tcx>,
1085 candidates: &mut SelectionCandidateSet<'tcx>)
1086 -> Result<(), SelectionError<'tcx>>
1088 let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1089 debug!("assemble_candidates_from_impls(self_ty={})", self_ty.repr(self.tcx()));
1091 let all_impls = self.all_impls(obligation.predicate.def_id());
1092 for &impl_def_id in &all_impls {
1093 self.infcx.probe(|snapshot| {
1094 let (skol_obligation_trait_pred, skol_map) =
1095 self.infcx().skolemize_late_bound_regions(&obligation.predicate, snapshot);
1096 match self.match_impl(impl_def_id, obligation, snapshot,
1097 &skol_map, skol_obligation_trait_pred.trait_ref.clone()) {
1099 candidates.vec.push(ImplCandidate(impl_def_id));
1108 /// Search for impls that might apply to `obligation`.
1109 fn assemble_candidates_from_object_ty(&mut self,
1110 obligation: &TraitObligation<'tcx>,
1111 candidates: &mut SelectionCandidateSet<'tcx>)
1113 let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1115 debug!("assemble_candidates_from_object_ty(self_ty={})",
1116 self_ty.repr(self.tcx()));
1118 // Object-safety candidates are only applicable to object-safe
1119 // traits. Including this check is useful because it helps
1120 // inference in cases of traits like `BorrowFrom`, which are
1121 // not object-safe, and which rely on being able to infer the
1122 // self-type from one of the other inputs. Without this check,
1123 // these cases wind up being considered ambiguous due to a
1124 // (spurious) ambiguity introduced here.
1125 if !object_safety::is_object_safe(self.tcx(), obligation.predicate.to_poly_trait_ref()) {
1129 let poly_trait_ref = match self_ty.sty {
1130 ty::ty_trait(ref data) => {
1131 data.principal_trait_ref_with_self_ty(self.tcx(), self_ty)
1133 ty::ty_infer(ty::TyVar(_)) => {
1134 debug!("assemble_candidates_from_object_ty: ambiguous");
1135 candidates.ambiguous = true; // could wind up being an object type
1143 debug!("assemble_candidates_from_object_ty: poly_trait_ref={}",
1144 poly_trait_ref.repr(self.tcx()));
1146 // see whether the object trait can be upcast to the trait we are looking for
1147 let obligation_def_id = obligation.predicate.def_id();
1148 let upcast_trait_ref = match util::upcast(self.tcx(), poly_trait_ref, obligation_def_id) {
1153 debug!("assemble_candidates_from_object_ty: upcast_trait_ref={}",
1154 upcast_trait_ref.repr(self.tcx()));
1156 // check whether the upcast version of the trait-ref matches what we are looking for
1157 if let Ok(()) = self.infcx.probe(|_| self.match_poly_trait_ref(obligation,
1158 upcast_trait_ref.clone())) {
1159 debug!("assemble_candidates_from_object_ty: matched, pushing candidate");
1160 candidates.vec.push(ObjectCandidate);
1164 ///////////////////////////////////////////////////////////////////////////
1167 // Winnowing is the process of attempting to resolve ambiguity by
1168 // probing further. During the winnowing process, we unify all
1169 // type variables (ignoring skolemization) and then we also
1170 // attempt to evaluate recursive bounds to see if they are
1173 /// Further evaluate `candidate` to decide whether all type parameters match and whether nested
1174 /// obligations are met. Returns true if `candidate` remains viable after this further
1176 fn winnow_candidate<'o>(&mut self,
1177 stack: &TraitObligationStack<'o, 'tcx>,
1178 candidate: &SelectionCandidate<'tcx>)
1179 -> EvaluationResult<'tcx>
1181 debug!("winnow_candidate: candidate={}", candidate.repr(self.tcx()));
1182 let result = self.infcx.probe(|_| {
1183 let candidate = (*candidate).clone();
1184 match self.confirm_candidate(stack.obligation, candidate) {
1185 Ok(selection) => self.winnow_selection(Some(stack), selection),
1186 Err(error) => EvaluatedToErr(error),
1189 debug!("winnow_candidate depth={} result={:?}",
1190 stack.obligation.recursion_depth, result);
1194 fn winnow_selection<'o>(&mut self,
1195 stack: Option<&TraitObligationStack<'o, 'tcx>>,
1196 selection: Selection<'tcx>)
1197 -> EvaluationResult<'tcx>
1199 self.evaluate_predicates_recursively(stack, selection.iter_nested())
1202 /// Returns true if `candidate_i` should be dropped in favor of `candidate_j`.
1204 /// This is generally true if either:
1205 /// - candidate i and candidate j are equivalent; or,
1206 /// - candidate i is a concrete impl and candidate j is a where clause bound,
1207 /// and the concrete impl is applicable to the types in the where clause bound.
1209 /// The last case refers to cases where there are blanket impls (often conditional
1210 /// blanket impls) as well as a where clause. This can come down to one of two cases:
1212 /// - The impl is truly unconditional (it has no where clauses
1213 /// of its own), in which case the where clause is
1214 /// unnecessary, because coherence requires that we would
1215 /// pick that particular impl anyhow (at least so long as we
1216 /// don't have specialization).
1218 /// - The impl is conditional, in which case we may not have winnowed it out
1219 /// because we don't know if the conditions apply, but the where clause is basically
1220 /// telling us taht there is some impl, though not necessarily the one we see.
1222 /// In both cases we prefer to take the where clause, which is
1223 /// essentially harmless. See issue #18453 for more details of
1224 /// a case where doing the opposite caused us harm.
1225 fn candidate_should_be_dropped_in_favor_of<'o>(&mut self,
1226 stack: &TraitObligationStack<'o, 'tcx>,
1227 candidate_i: &SelectionCandidate<'tcx>,
1228 candidate_j: &SelectionCandidate<'tcx>)
1231 if candidate_i == candidate_j {
1235 match (candidate_i, candidate_j) {
1236 (&ImplCandidate(impl_def_id), &ParamCandidate(ref bound)) => {
1237 debug!("Considering whether to drop param {} in favor of impl {}",
1238 candidate_i.repr(self.tcx()),
1239 candidate_j.repr(self.tcx()));
1241 self.infcx.probe(|snapshot| {
1242 let (skol_obligation_trait_ref, skol_map) =
1243 self.infcx().skolemize_late_bound_regions(
1244 &stack.obligation.predicate, snapshot);
1246 self.rematch_impl(impl_def_id, stack.obligation, snapshot,
1247 &skol_map, skol_obligation_trait_ref.trait_ref.clone());
1248 let impl_trait_ref =
1249 ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
1250 let impl_trait_ref =
1251 impl_trait_ref.subst(self.tcx(), &impl_substs.value);
1252 let poly_impl_trait_ref =
1253 ty::Binder(impl_trait_ref);
1255 infer::RelateOutputImplTypes(stack.obligation.cause.span);
1257 .sub_poly_trait_refs(false, origin, poly_impl_trait_ref, bound.clone())
1261 (&BuiltinCandidate(_), &ParamCandidate(_)) => {
1262 // If we have a where-clause like `Option<K> : Send`,
1263 // then we wind up in a situation where there is a
1264 // default rule (`Option<K>:Send if K:Send) and the
1265 // where-clause that both seem applicable. Just take
1266 // the where-clause in that case.
1269 (&ProjectionCandidate, &ParamCandidate(_)) => {
1270 // FIXME(#20297) -- this gives where clauses precedent
1271 // over projections. Really these are just two means
1272 // of deducing information (one based on the where
1273 // clauses on the trait definition; one based on those
1274 // on the enclosing scope), and it'd be better to
1275 // integrate them more intelligently. But for now this
1276 // seems ok. If we DON'T give where clauses
1277 // precedence, we run into trouble in default methods,
1278 // where both the projection bounds for `Self::A` and
1279 // the where clauses are in scope.
1282 (&ParamCandidate(ref bound1), &ParamCandidate(ref bound2)) => {
1283 self.infcx.probe(|_| {
1285 project::normalize_with_depth(self,
1286 stack.obligation.cause.clone(),
1287 stack.obligation.recursion_depth+1,
1290 project::normalize_with_depth(self,
1291 stack.obligation.cause.clone(),
1292 stack.obligation.recursion_depth+1,
1295 infer::RelateOutputImplTypes(stack.obligation.cause.span);
1297 .sub_poly_trait_refs(false, origin, bound1.value, bound2.value)
1307 ///////////////////////////////////////////////////////////////////////////
1310 // These cover the traits that are built-in to the language
1311 // itself. This includes `Copy` and `Sized` for sure. For the
1312 // moment, it also includes `Send` / `Sync` and a few others, but
1313 // those will hopefully change to library-defined traits in the
1316 fn assemble_builtin_bound_candidates<'o>(&mut self,
1317 bound: ty::BuiltinBound,
1318 stack: &TraitObligationStack<'o, 'tcx>,
1319 candidates: &mut SelectionCandidateSet<'tcx>)
1320 -> Result<(),SelectionError<'tcx>>
1322 match self.builtin_bound(bound, stack.obligation) {
1324 debug!("builtin_bound: bound={}",
1325 bound.repr(self.tcx()));
1326 candidates.vec.push(BuiltinCandidate(bound));
1329 Ok(ParameterBuiltin) => { Ok(()) }
1330 Ok(AmbiguousBuiltin) => {
1331 debug!("assemble_builtin_bound_candidates: ambiguous builtin");
1332 Ok(candidates.ambiguous = true)
1334 Err(e) => { Err(e) }
1338 fn builtin_bound(&mut self,
1339 bound: ty::BuiltinBound,
1340 obligation: &TraitObligation<'tcx>)
1341 -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1343 // Note: these tests operate on types that may contain bound
1344 // regions. To be proper, we ought to skolemize here, but we
1345 // forego the skolemization and defer it until the
1346 // confirmation step.
1348 let self_ty = self.infcx.shallow_resolve(obligation.predicate.0.self_ty());
1349 return match self_ty.sty {
1350 ty::ty_infer(ty::IntVar(_)) |
1351 ty::ty_infer(ty::FloatVar(_)) |
1356 ty::ty_bare_fn(..) |
1358 // safe for everything
1362 ty::ty_uniq(referent_ty) => { // Box<T>
1374 Ok(If(vec![referent_ty]))
1379 ty::ty_ptr(..) => { // *const T, *mut T
1388 // sync and send are not implemented for *const, *mut
1394 ty::ty_trait(ref data) => {
1399 ty::BoundCopy | ty::BoundSync | ty::BoundSend => {
1400 if data.bounds.builtin_bounds.contains(&bound) {
1403 // Recursively check all supertraits to find out if any further
1404 // bounds are required and thus we must fulfill.
1406 data.principal_trait_ref_with_self_ty(self.tcx(),
1407 self.tcx().types.err);
1408 for tr in util::supertraits(self.tcx(), principal) {
1409 let td = ty::lookup_trait_def(self.tcx(), tr.def_id());
1410 if td.bounds.builtin_bounds.contains(&bound) {
1411 return Ok(If(Vec::new()))
1421 ty::ty_rptr(_, ty::mt { ty: referent_ty, mutbl }) => {
1426 // &mut T is affine and hence never `Copy`
1427 ast::MutMutable => {
1431 // &T is always copyable
1432 ast::MutImmutable => {
1444 // Note: technically, a region pointer is only
1445 // sendable if it has lifetime
1446 // `'static`. However, we don't take regions
1447 // into account when doing trait matching:
1448 // instead, when we decide that `T : Send`, we
1449 // will register a separate constraint with
1450 // the region inferencer that `T : 'static`
1451 // holds as well (because the trait `Send`
1452 // requires it). This will ensure that there
1453 // is no borrowed data in `T` (or else report
1454 // an inference error). The reason we do it
1455 // this way is that we do not yet *know* what
1456 // lifetime the borrowed reference has, since
1457 // we haven't finished running inference -- in
1458 // other words, there's a kind of
1459 // chicken-and-egg problem.
1460 Ok(If(vec![referent_ty]))
1465 ty::ty_vec(element_ty, ref len) => {
1471 // [T, ..n] is copy iff T is copy
1472 Ok(If(vec![element_ty]))
1475 // [T] is unsized and hence affine
1491 Ok(If(vec![element_ty]))
1497 // Equivalent to [u8]
1511 ty::ty_tup(ref tys) => {
1512 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1516 ty::ty_closure(def_id, _, substs) => {
1517 // FIXME -- This case is tricky. In the case of by-ref
1518 // closures particularly, we need the results of
1519 // inference to decide how to reflect the type of each
1520 // upvar (the upvar may have type `T`, but the runtime
1521 // type could be `&mut`, `&`, or just `T`). For now,
1522 // though, we'll do this unsoundly and assume that all
1523 // captures are by value. Really what we ought to do
1524 // is reserve judgement and then intertwine this
1525 // analysis with closure inference.
1526 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
1528 // Unboxed closures shouldn't be
1529 // implicitly copyable
1530 if bound == ty::BoundCopy {
1531 return Ok(ParameterBuiltin);
1534 match self.closure_typer.closure_upvars(def_id, substs) {
1536 Ok(If(upvars.iter().map(|c| c.ty).collect()))
1539 debug!("assemble_builtin_bound_candidates: no upvar types available yet");
1540 Ok(AmbiguousBuiltin)
1545 ty::ty_struct(def_id, substs) => {
1546 let types: Vec<Ty> =
1547 ty::struct_fields(self.tcx(), def_id, substs).iter()
1550 nominal(self, bound, def_id, types)
1553 ty::ty_enum(def_id, substs) => {
1554 let types: Vec<Ty> =
1555 ty::substd_enum_variants(self.tcx(), def_id, substs)
1557 .flat_map(|variant| variant.args.iter())
1560 nominal(self, bound, def_id, types)
1563 ty::ty_projection(_) |
1564 ty::ty_param(_) => {
1565 // Note: A type parameter is only considered to meet a
1566 // particular bound if there is a where clause telling
1567 // us that it does, and that case is handled by
1568 // `assemble_candidates_from_caller_bounds()`.
1569 Ok(ParameterBuiltin)
1572 ty::ty_infer(ty::TyVar(_)) => {
1573 // Unbound type variable. Might or might not have
1574 // applicable impls and so forth, depending on what
1575 // those type variables wind up being bound to.
1576 debug!("assemble_builtin_bound_candidates: ambiguous builtin");
1577 Ok(AmbiguousBuiltin)
1580 ty::ty_open(ty) => {
1581 // these only crop up in trans, and represent an
1582 // "opened" unsized/existential type (one that has
1583 // been dereferenced)
1600 ty::ty_infer(ty::FreshTy(_)) |
1601 ty::ty_infer(ty::FreshIntTy(_)) => {
1602 self.tcx().sess.bug(
1604 "asked to assemble builtin bounds of unexpected type: {}",
1605 self_ty.repr(self.tcx()))[]);
1609 fn nominal<'cx, 'tcx>(this: &mut SelectionContext<'cx, 'tcx>,
1610 bound: ty::BuiltinBound,
1612 types: Vec<Ty<'tcx>>)
1613 -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1615 // First check for markers and other nonsense.
1616 let tcx = this.tcx();
1619 if Some(def_id) == tcx.lang_items.managed_bound() {
1620 return Err(Unimplemented)
1625 return Ok(ParameterBuiltin)
1630 Some(def_id) == tcx.lang_items.managed_bound() ||
1631 Some(def_id) == tcx.lang_items.unsafe_type()
1633 return Err(Unimplemented)
1637 ty::BoundSized => { }
1644 ///////////////////////////////////////////////////////////////////////////
1647 // Confirmation unifies the output type parameters of the trait
1648 // with the values found in the obligation, possibly yielding a
1649 // type error. See `doc.rs` for more details.
1651 fn confirm_candidate(&mut self,
1652 obligation: &TraitObligation<'tcx>,
1653 candidate: SelectionCandidate<'tcx>)
1654 -> Result<Selection<'tcx>,SelectionError<'tcx>>
1656 debug!("confirm_candidate({}, {})",
1657 obligation.repr(self.tcx()),
1658 candidate.repr(self.tcx()));
1661 BuiltinCandidate(builtin_bound) => {
1663 try!(self.confirm_builtin_candidate(obligation, builtin_bound))))
1667 Ok(VtableBuiltin(VtableBuiltinData { nested: VecPerParamSpace::empty() }))
1670 ParamCandidate(param) => {
1671 let obligations = self.confirm_param_candidate(obligation, param);
1672 Ok(VtableParam(obligations))
1675 ImplCandidate(impl_def_id) => {
1677 try!(self.confirm_impl_candidate(obligation, impl_def_id));
1678 Ok(VtableImpl(vtable_impl))
1681 ClosureCandidate(closure_def_id, substs) => {
1682 try!(self.confirm_closure_candidate(obligation, closure_def_id, &substs));
1683 Ok(VtableClosure(closure_def_id, substs))
1686 ObjectCandidate => {
1687 let data = self.confirm_object_candidate(obligation);
1688 Ok(VtableObject(data))
1691 FnPointerCandidate => {
1693 try!(self.confirm_fn_pointer_candidate(obligation));
1694 Ok(VtableFnPointer(fn_type))
1697 ProjectionCandidate => {
1698 self.confirm_projection_candidate(obligation);
1699 Ok(VtableParam(Vec::new()))
1704 fn confirm_projection_candidate(&mut self,
1705 obligation: &TraitObligation<'tcx>)
1707 let _: Result<(),()> =
1708 self.infcx.try(|snapshot| {
1710 self.match_projection_obligation_against_bounds_from_trait(obligation,
1717 fn confirm_param_candidate(&mut self,
1718 obligation: &TraitObligation<'tcx>,
1719 param: ty::PolyTraitRef<'tcx>)
1720 -> Vec<PredicateObligation<'tcx>>
1722 debug!("confirm_param_candidate({},{})",
1723 obligation.repr(self.tcx()),
1724 param.repr(self.tcx()));
1726 // During evaluation, we already checked that this
1727 // where-clause trait-ref could be unified with the obligation
1728 // trait-ref. Repeat that unification now without any
1729 // transactional boundary; it should not fail.
1730 match self.match_where_clause_trait_ref(obligation, param.clone()) {
1731 Ok(obligations) => obligations,
1733 self.tcx().sess.bug(
1734 format!("Where clause `{}` was applicable to `{}` but now is not",
1735 param.repr(self.tcx()),
1736 obligation.repr(self.tcx())).as_slice());
1741 fn confirm_builtin_candidate(&mut self,
1742 obligation: &TraitObligation<'tcx>,
1743 bound: ty::BuiltinBound)
1744 -> Result<VtableBuiltinData<PredicateObligation<'tcx>>,
1745 SelectionError<'tcx>>
1747 debug!("confirm_builtin_candidate({})",
1748 obligation.repr(self.tcx()));
1750 match try!(self.builtin_bound(bound, obligation)) {
1751 If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)),
1752 AmbiguousBuiltin | ParameterBuiltin => {
1753 self.tcx().sess.span_bug(
1754 obligation.cause.span,
1755 &format!("builtin bound for {} was ambig",
1756 obligation.repr(self.tcx()))[]);
1761 fn vtable_builtin_data(&mut self,
1762 obligation: &TraitObligation<'tcx>,
1763 bound: ty::BuiltinBound,
1764 nested: Vec<Ty<'tcx>>)
1765 -> VtableBuiltinData<PredicateObligation<'tcx>>
1767 let derived_cause = self.derived_cause(obligation, BuiltinDerivedObligation);
1768 let obligations = nested.iter().map(|&bound_ty| {
1769 // the obligation might be higher-ranked, e.g. for<'a> &'a
1770 // int : Copy. In that case, we will wind up with
1771 // late-bound regions in the `nested` vector. So for each
1772 // one we instantiate to a skolemized region, do our work
1773 // to produce something like `&'0 int : Copy`, and then
1774 // re-bind it. This is a bit of busy-work but preserves
1775 // the invariant that we only manipulate free regions, not
1777 self.infcx.try(|snapshot| {
1778 let (skol_ty, skol_map) =
1779 self.infcx().skolemize_late_bound_regions(&ty::Binder(bound_ty), snapshot);
1780 let skol_predicate =
1781 util::predicate_for_builtin_bound(
1783 derived_cause.clone(),
1785 obligation.recursion_depth + 1,
1787 match skol_predicate {
1788 Ok(skol_predicate) => Ok(self.infcx().plug_leaks(skol_map, snapshot,
1790 Err(ErrorReported) => Err(ErrorReported)
1793 }).collect::<Result<_, _>>();
1794 let mut obligations = match obligations {
1796 Err(ErrorReported) => Vec::new()
1799 // as a special case, `Send` requires `'static`
1800 if bound == ty::BoundSend {
1801 obligations.push(Obligation {
1802 cause: obligation.cause.clone(),
1803 recursion_depth: obligation.recursion_depth+1,
1804 predicate: ty::Binder(ty::OutlivesPredicate(obligation.self_ty(),
1805 ty::ReStatic)).as_predicate(),
1809 let obligations = VecPerParamSpace::new(obligations, Vec::new(), Vec::new());
1811 debug!("vtable_builtin_data: obligations={}",
1812 obligations.repr(self.tcx()));
1814 VtableBuiltinData { nested: obligations }
1817 fn confirm_impl_candidate(&mut self,
1818 obligation: &TraitObligation<'tcx>,
1819 impl_def_id: ast::DefId)
1820 -> Result<VtableImplData<'tcx, PredicateObligation<'tcx>>,
1821 SelectionError<'tcx>>
1823 debug!("confirm_impl_candidate({},{})",
1824 obligation.repr(self.tcx()),
1825 impl_def_id.repr(self.tcx()));
1827 // First, create the substitutions by matching the impl again,
1828 // this time not in a probe.
1829 self.infcx.try(|snapshot| {
1830 let (skol_obligation_trait_ref, skol_map) =
1831 self.infcx().skolemize_late_bound_regions(&obligation.predicate, snapshot);
1833 self.rematch_impl(impl_def_id, obligation,
1834 snapshot, &skol_map, skol_obligation_trait_ref.trait_ref);
1835 debug!("confirm_impl_candidate substs={}", substs.repr(self.tcx()));
1836 Ok(self.vtable_impl(impl_def_id, substs, obligation.cause.clone(),
1837 obligation.recursion_depth + 1, skol_map, snapshot))
1841 fn vtable_impl(&mut self,
1842 impl_def_id: ast::DefId,
1843 substs: Normalized<'tcx, Substs<'tcx>>,
1844 cause: ObligationCause<'tcx>,
1845 recursion_depth: uint,
1846 skol_map: infer::SkolemizationMap,
1847 snapshot: &infer::CombinedSnapshot)
1848 -> VtableImplData<'tcx, PredicateObligation<'tcx>>
1850 debug!("vtable_impl(impl_def_id={}, substs={}, recursion_depth={}, skol_map={})",
1851 impl_def_id.repr(self.tcx()),
1852 substs.repr(self.tcx()),
1854 skol_map.repr(self.tcx()));
1856 let mut impl_obligations =
1857 self.impl_obligations(cause,
1864 debug!("vtable_impl: impl_def_id={} impl_obligations={}",
1865 impl_def_id.repr(self.tcx()),
1866 impl_obligations.repr(self.tcx()));
1868 impl_obligations.extend(TypeSpace, substs.obligations.into_iter());
1870 VtableImplData { impl_def_id: impl_def_id,
1871 substs: substs.value,
1872 nested: impl_obligations }
1875 fn confirm_object_candidate(&mut self,
1876 obligation: &TraitObligation<'tcx>)
1877 -> VtableObjectData<'tcx>
1879 debug!("confirm_object_candidate({})",
1880 obligation.repr(self.tcx()));
1882 let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1883 let poly_trait_ref = match self_ty.sty {
1884 ty::ty_trait(ref data) => {
1885 data.principal_trait_ref_with_self_ty(self.tcx(), self_ty)
1888 self.tcx().sess.span_bug(obligation.cause.span,
1889 "object candidate with non-object");
1893 let obligation_def_id = obligation.predicate.def_id();
1894 let upcast_trait_ref = match util::upcast(self.tcx(),
1895 poly_trait_ref.clone(),
1896 obligation_def_id) {
1899 self.tcx().sess.span_bug(obligation.cause.span,
1900 format!("unable to upcast from {} to {}",
1901 poly_trait_ref.repr(self.tcx()),
1902 obligation_def_id.repr(self.tcx())).as_slice());
1906 match self.match_poly_trait_ref(obligation, upcast_trait_ref) {
1909 self.tcx().sess.span_bug(obligation.cause.span,
1910 "failed to match trait refs");
1914 VtableObjectData { object_ty: self_ty }
1917 fn confirm_fn_pointer_candidate(&mut self,
1918 obligation: &TraitObligation<'tcx>)
1919 -> Result<ty::Ty<'tcx>,SelectionError<'tcx>>
1921 debug!("confirm_fn_pointer_candidate({})",
1922 obligation.repr(self.tcx()));
1924 let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1925 let sig = ty::ty_fn_sig(self_ty);
1926 let ty::Binder((trait_ref, _)) =
1927 util::closure_trait_ref_and_return_type(self.tcx(),
1928 obligation.predicate.def_id(),
1931 util::TupleArgumentsFlag::Yes);
1932 let trait_ref = ty::Binder(trait_ref);
1934 try!(self.confirm_poly_trait_refs(obligation.cause.clone(),
1935 obligation.predicate.to_poly_trait_ref(),
1940 fn confirm_closure_candidate(&mut self,
1941 obligation: &TraitObligation<'tcx>,
1942 closure_def_id: ast::DefId,
1943 substs: &Substs<'tcx>)
1944 -> Result<(),SelectionError<'tcx>>
1946 debug!("confirm_closure_candidate({},{},{})",
1947 obligation.repr(self.tcx()),
1948 closure_def_id.repr(self.tcx()),
1949 substs.repr(self.tcx()));
1951 let trait_ref = self.closure_trait_ref(obligation,
1955 debug!("confirm_closure_candidate(closure_def_id={}, trait_ref={})",
1956 closure_def_id.repr(self.tcx()),
1957 trait_ref.repr(self.tcx()));
1959 self.confirm_poly_trait_refs(obligation.cause.clone(),
1960 obligation.predicate.to_poly_trait_ref(),
1964 /// In the case of closure types and fn pointers,
1965 /// we currently treat the input type parameters on the trait as
1966 /// outputs. This means that when we have a match we have only
1967 /// considered the self type, so we have to go back and make sure
1968 /// to relate the argument types too. This is kind of wrong, but
1969 /// since we control the full set of impls, also not that wrong,
1970 /// and it DOES yield better error messages (since we don't report
1971 /// errors as if there is no applicable impl, but rather report
1972 /// errors are about mismatched argument types.
1974 /// Here is an example. Imagine we have an closure expression
1975 /// and we desugared it so that the type of the expression is
1976 /// `Closure`, and `Closure` expects an int as argument. Then it
1977 /// is "as if" the compiler generated this impl:
1979 /// impl Fn(int) for Closure { ... }
1981 /// Now imagine our obligation is `Fn(uint) for Closure`. So far
1982 /// we have matched the self-type `Closure`. At this point we'll
1983 /// compare the `int` to `uint` and generate an error.
1985 /// Note that this checking occurs *after* the impl has selected,
1986 /// because these output type parameters should not affect the
1987 /// selection of the impl. Therefore, if there is a mismatch, we
1988 /// report an error to the user.
1989 fn confirm_poly_trait_refs(&mut self,
1990 obligation_cause: ObligationCause,
1991 obligation_trait_ref: ty::PolyTraitRef<'tcx>,
1992 expected_trait_ref: ty::PolyTraitRef<'tcx>)
1993 -> Result<(), SelectionError<'tcx>>
1995 let origin = infer::RelateOutputImplTypes(obligation_cause.span);
1997 let obligation_trait_ref = obligation_trait_ref.clone();
1998 match self.infcx.sub_poly_trait_refs(false,
2000 expected_trait_ref.clone(),
2001 obligation_trait_ref.clone()) {
2003 Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
2007 ///////////////////////////////////////////////////////////////////////////
2010 // Matching is a common path used for both evaluation and
2011 // confirmation. It basically unifies types that appear in impls
2012 // and traits. This does affect the surrounding environment;
2013 // therefore, when used during evaluation, match routines must be
2014 // run inside of a `probe()` so that their side-effects are
2017 fn rematch_impl(&mut self,
2018 impl_def_id: ast::DefId,
2019 obligation: &TraitObligation<'tcx>,
2020 snapshot: &infer::CombinedSnapshot,
2021 skol_map: &infer::SkolemizationMap,
2022 skol_obligation_trait_ref: Rc<ty::TraitRef<'tcx>>)
2023 -> Normalized<'tcx, Substs<'tcx>>
2025 match self.match_impl(impl_def_id, obligation, snapshot,
2026 skol_map, skol_obligation_trait_ref) {
2031 self.tcx().sess.bug(
2032 &format!("Impl {} was matchable against {} but now is not",
2033 impl_def_id.repr(self.tcx()),
2034 obligation.repr(self.tcx()))[]);
2039 fn match_impl(&mut self,
2040 impl_def_id: ast::DefId,
2041 obligation: &TraitObligation<'tcx>,
2042 snapshot: &infer::CombinedSnapshot,
2043 skol_map: &infer::SkolemizationMap,
2044 skol_obligation_trait_ref: Rc<ty::TraitRef<'tcx>>)
2045 -> Result<Normalized<'tcx, Substs<'tcx>>, ()>
2047 let impl_trait_ref = ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
2049 // Before we create the substitutions and everything, first
2050 // consider a "quick reject". This avoids creating more types
2051 // and so forth that we need to.
2052 if self.fast_reject_trait_refs(obligation, &*impl_trait_ref) {
2056 let impl_substs = util::fresh_substs_for_impl(self.infcx,
2057 obligation.cause.span,
2060 let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
2063 let impl_trait_ref =
2064 project::normalize_with_depth(self,
2065 obligation.cause.clone(),
2066 obligation.recursion_depth + 1,
2069 debug!("match_impl(impl_def_id={}, obligation={}, \
2070 impl_trait_ref={}, skol_obligation_trait_ref={})",
2071 impl_def_id.repr(self.tcx()),
2072 obligation.repr(self.tcx()),
2073 impl_trait_ref.repr(self.tcx()),
2074 skol_obligation_trait_ref.repr(self.tcx()));
2076 let origin = infer::RelateOutputImplTypes(obligation.cause.span);
2077 match self.infcx.sub_trait_refs(false,
2079 impl_trait_ref.value.clone(),
2080 skol_obligation_trait_ref) {
2083 debug!("match_impl: failed sub_trait_refs due to `{}`",
2084 ty::type_err_to_str(self.tcx(), &e));
2089 match self.infcx.leak_check(skol_map, snapshot) {
2092 debug!("match_impl: failed leak check due to `{}`",
2093 ty::type_err_to_str(self.tcx(), &e));
2098 debug!("match_impl: success impl_substs={}", impl_substs.repr(self.tcx()));
2099 Ok(Normalized { value: impl_substs,
2100 obligations: impl_trait_ref.obligations })
2103 fn fast_reject_trait_refs(&mut self,
2104 obligation: &TraitObligation,
2105 impl_trait_ref: &ty::TraitRef)
2108 // We can avoid creating type variables and doing the full
2109 // substitution if we find that any of the input types, when
2110 // simplified, do not match.
2112 obligation.predicate.0.input_types().iter()
2113 .zip(impl_trait_ref.input_types().iter())
2114 .any(|(&obligation_ty, &impl_ty)| {
2115 let simplified_obligation_ty =
2116 fast_reject::simplify_type(self.tcx(), obligation_ty, true);
2117 let simplified_impl_ty =
2118 fast_reject::simplify_type(self.tcx(), impl_ty, false);
2120 simplified_obligation_ty.is_some() &&
2121 simplified_impl_ty.is_some() &&
2122 simplified_obligation_ty != simplified_impl_ty
2126 /// Normalize `where_clause_trait_ref` and try to match it against
2127 /// `obligation`. If successful, return any predicates that
2128 /// result from the normalization. Normalization is necessary
2129 /// because where-clauses are stored in the parameter environment
2131 fn match_where_clause_trait_ref(&mut self,
2132 obligation: &TraitObligation<'tcx>,
2133 where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
2134 -> Result<Vec<PredicateObligation<'tcx>>,()>
2137 try!(self.match_poly_trait_ref(obligation, where_clause_trait_ref));
2142 /// Returns `Ok` if `poly_trait_ref` being true implies that the
2143 /// obligation is satisfied.
2144 fn match_poly_trait_ref(&mut self,
2145 obligation: &TraitObligation<'tcx>,
2146 poly_trait_ref: ty::PolyTraitRef<'tcx>)
2149 debug!("match_poly_trait_ref: obligation={} poly_trait_ref={}",
2150 obligation.repr(self.tcx()),
2151 poly_trait_ref.repr(self.tcx()));
2153 let origin = infer::RelateOutputImplTypes(obligation.cause.span);
2154 match self.infcx.sub_poly_trait_refs(false,
2157 obligation.predicate.to_poly_trait_ref()) {
2163 /// Determines whether the self type declared against
2164 /// `impl_def_id` matches `obligation_self_ty`. If successful,
2165 /// returns the substitutions used to make them match. See
2166 /// `match_impl()`. For example, if `impl_def_id` is declared
2169 /// impl<T:Copy> Foo for ~T { ... }
2171 /// and `obligation_self_ty` is `int`, we'd back an `Err(_)`
2172 /// result. But if `obligation_self_ty` were `~int`, we'd get
2173 /// back `Ok(T=int)`.
2174 fn match_inherent_impl(&mut self,
2175 impl_def_id: ast::DefId,
2176 obligation_cause: &ObligationCause,
2177 obligation_self_ty: Ty<'tcx>)
2178 -> Result<Substs<'tcx>,()>
2180 // Create fresh type variables for each type parameter declared
2182 let impl_substs = util::fresh_substs_for_impl(self.infcx,
2183 obligation_cause.span,
2186 // Find the self type for the impl.
2187 let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty;
2188 let impl_self_ty = impl_self_ty.subst(self.tcx(), &impl_substs);
2190 debug!("match_impl_self_types(obligation_self_ty={}, impl_self_ty={})",
2191 obligation_self_ty.repr(self.tcx()),
2192 impl_self_ty.repr(self.tcx()));
2194 match self.match_self_types(obligation_cause,
2196 obligation_self_ty) {
2198 debug!("Matched impl_substs={}", impl_substs.repr(self.tcx()));
2208 fn match_self_types(&mut self,
2209 cause: &ObligationCause,
2211 // The self type provided by the impl/caller-obligation:
2212 provided_self_ty: Ty<'tcx>,
2214 // The self type the obligation is for:
2215 required_self_ty: Ty<'tcx>)
2218 // FIXME(#5781) -- equating the types is stronger than
2219 // necessary. Should consider variance of trait w/r/t Self.
2221 let origin = infer::RelateSelfType(cause.span);
2222 match self.infcx.eq_types(false,
2231 ///////////////////////////////////////////////////////////////////////////
2234 fn push_stack<'o,'s:'o>(&mut self,
2235 previous_stack: Option<&'s TraitObligationStack<'s, 'tcx>>,
2236 obligation: &'o TraitObligation<'tcx>)
2237 -> TraitObligationStack<'o, 'tcx>
2239 let fresh_trait_ref =
2240 obligation.predicate.to_poly_trait_ref().fold_with(&mut self.freshener);
2242 TraitObligationStack {
2243 obligation: obligation,
2244 fresh_trait_ref: fresh_trait_ref,
2245 previous: previous_stack.map(|p| p), // FIXME variance
2249 /// Returns set of all impls for a given trait.
2250 fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
2251 ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_def_id);
2253 match self.tcx().trait_impls.borrow().get(&trait_def_id) {
2255 Some(impls) => impls.borrow().clone()
2259 fn closure_trait_ref(&self,
2260 obligation: &TraitObligation<'tcx>,
2261 closure_def_id: ast::DefId,
2262 substs: &Substs<'tcx>)
2263 -> ty::PolyTraitRef<'tcx>
2265 let closure_type = self.closure_typer.closure_type(closure_def_id, substs);
2266 let ty::Binder((trait_ref, _)) =
2267 util::closure_trait_ref_and_return_type(self.tcx(),
2268 obligation.predicate.def_id(),
2269 obligation.predicate.0.self_ty(), // (1)
2271 util::TupleArgumentsFlag::No);
2273 // (1) Feels icky to skip the binder here, but OTOH we know
2274 // that the self-type is an unboxed closure type and hence is
2275 // in fact unparameterized (or at least does not reference any
2276 // regions bound in the obligation). Still probably some
2277 // refactoring could make this nicer.
2279 ty::Binder(trait_ref)
2282 fn impl_obligations(&mut self,
2283 cause: ObligationCause<'tcx>,
2284 recursion_depth: uint,
2285 impl_def_id: ast::DefId,
2286 impl_substs: &Substs<'tcx>,
2287 skol_map: infer::SkolemizationMap,
2288 snapshot: &infer::CombinedSnapshot)
2289 -> VecPerParamSpace<PredicateObligation<'tcx>>
2291 let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
2292 let bounds = impl_generics.to_bounds(self.tcx(), impl_substs);
2293 let normalized_bounds =
2294 project::normalize_with_depth(self, cause.clone(), recursion_depth, &bounds);
2295 let normalized_bounds =
2296 self.infcx().plug_leaks(skol_map, snapshot, &normalized_bounds);
2297 let mut impl_obligations =
2298 util::predicates_for_generics(self.tcx(),
2301 &normalized_bounds.value);
2302 impl_obligations.extend(TypeSpace, normalized_bounds.obligations.into_iter());
2306 fn fn_family_trait_kind(&self,
2307 trait_def_id: ast::DefId)
2308 -> Option<ty::ClosureKind>
2310 let tcx = self.tcx();
2311 if Some(trait_def_id) == tcx.lang_items.fn_trait() {
2312 Some(ty::FnClosureKind)
2313 } else if Some(trait_def_id) == tcx.lang_items.fn_mut_trait() {
2314 Some(ty::FnMutClosureKind)
2315 } else if Some(trait_def_id) == tcx.lang_items.fn_once_trait() {
2316 Some(ty::FnOnceClosureKind)
2322 #[allow(unused_comparisons)]
2323 fn derived_cause(&self,
2324 obligation: &TraitObligation<'tcx>,
2325 variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>)
2326 -> ObligationCause<'tcx>
2329 * Creates a cause for obligations that are derived from
2330 * `obligation` by a recursive search (e.g., for a builtin
2331 * bound, or eventually a `impl Foo for ..`). If `obligation`
2332 * is itself a derived obligation, this is just a clone, but
2333 * otherwise we create a "derived obligation" cause so as to
2334 * keep track of the original root obligation for error
2338 // NOTE(flaper87): As of now, it keeps track of the whole error
2339 // chain. Ideally, we should have a way to configure this either
2340 // by using -Z verbose or just a CLI argument.
2341 if obligation.recursion_depth >= 0 {
2342 let derived_cause = DerivedObligationCause {
2343 parent_trait_ref: obligation.predicate.to_poly_trait_ref(),
2344 parent_code: Rc::new(obligation.cause.code.clone()),
2346 ObligationCause::new(obligation.cause.span,
2347 obligation.cause.body_id,
2348 variant(derived_cause))
2350 obligation.cause.clone()
2355 impl<'tcx> Repr<'tcx> for SelectionCandidate<'tcx> {
2356 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2358 ErrorCandidate => format!("ErrorCandidate"),
2359 BuiltinCandidate(b) => format!("BuiltinCandidate({:?})", b),
2360 ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
2361 ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
2362 ProjectionCandidate => format!("ProjectionCandidate"),
2363 FnPointerCandidate => format!("FnPointerCandidate"),
2364 ObjectCandidate => {
2365 format!("ObjectCandidate")
2367 ClosureCandidate(c, ref s) => {
2368 format!("ClosureCandidate({:?},{})", c, s.repr(tcx))
2374 impl<'tcx> SelectionCache<'tcx> {
2375 pub fn new() -> SelectionCache<'tcx> {
2377 hashmap: RefCell::new(HashMap::new())
2382 impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> {
2383 fn iter(&self) -> Option<&TraitObligationStack<'o, 'tcx>> {
2388 impl<'o, 'tcx> Iterator for Option<&'o TraitObligationStack<'o, 'tcx>> {
2389 type Item = &'o TraitObligationStack<'o,'tcx>;
2391 fn next(&mut self) -> Option<&'o TraitObligationStack<'o, 'tcx>> {
2404 impl<'o, 'tcx> Repr<'tcx> for TraitObligationStack<'o, 'tcx> {
2405 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2406 format!("TraitObligationStack({})",
2407 self.obligation.repr(tcx))
2411 impl<'tcx> EvaluationResult<'tcx> {
2412 fn may_apply(&self) -> bool {
2416 EvaluatedToErr(Overflow) |
2417 EvaluatedToErr(OutputTypeParameterMismatch(..)) => {
2420 EvaluatedToErr(Unimplemented) => {
2427 impl MethodMatchResult {
2428 pub fn may_apply(&self) -> bool {
2430 MethodMatched(_) => true,
2431 MethodAmbiguous(_) => true,
2432 MethodDidNotMatch => false,