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 `README.md` for high-level documentation
13 pub use self::MethodMatchResult
::*;
14 pub use self::MethodMatchedData
::*;
15 use self::SelectionCandidate
::*;
16 use self::BuiltinBoundConditions
::*;
17 use self::EvaluationResult
::*;
20 use super::DerivedObligationCause
;
22 use super::project
::{normalize_with_depth, Normalized}
;
23 use super::{PredicateObligation, TraitObligation, ObligationCause}
;
24 use super::report_overflow_error
;
25 use super::{ObligationCauseCode, BuiltinDerivedObligation, ImplDerivedObligation}
;
26 use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch}
;
27 use super::{ObjectCastObligation, Obligation}
;
28 use super::TraitNotObjectSafe
;
30 use super::SelectionResult
;
31 use super::{VtableBuiltin
, VtableImpl
, VtableParam
, VtableClosure
,
32 VtableFnPointer
, VtableObject
, VtableDefaultImpl
};
33 use super::{VtableImplData
, VtableObjectData
, VtableBuiltinData
,
34 VtableClosureData
, VtableDefaultImplData
};
35 use super::object_safety
;
38 use middle
::def_id
::DefId
;
40 use middle
::infer
::{InferCtxt, TypeFreshener, TypeOrigin}
;
41 use middle
::subst
::{Subst, Substs, TypeSpace}
;
42 use middle
::ty
::{self, ToPredicate, ToPolyTraitRef, Ty, TypeFoldable}
;
43 use middle
::ty
::fast_reject
;
44 use middle
::ty
::relate
::TypeRelation
;
46 use std
::cell
::RefCell
;
51 use util
::common
::ErrorReported
;
52 use util
::nodemap
::FnvHashMap
;
54 pub struct SelectionContext
<'cx
, 'tcx
:'cx
> {
55 infcx
: &'cx InferCtxt
<'cx
, 'tcx
>,
57 /// Freshener used specifically for skolemizing entries on the
58 /// obligation stack. This ensures that all entries on the stack
59 /// at one time will have the same set of skolemized entries,
60 /// which is important for checking for trait bounds that
61 /// recursively require themselves.
62 freshener
: TypeFreshener
<'cx
, 'tcx
>,
64 /// If true, indicates that the evaluation should be conservative
65 /// and consider the possibility of types outside this crate.
66 /// This comes up primarily when resolving ambiguity. Imagine
67 /// there is some trait reference `$0 : Bar` where `$0` is an
68 /// inference variable. If `intercrate` is true, then we can never
69 /// say for sure that this reference is not implemented, even if
70 /// there are *no impls at all for `Bar`*, because `$0` could be
71 /// bound to some type that in a downstream crate that implements
72 /// `Bar`. This is the suitable mode for coherence. Elsewhere,
73 /// though, we set this to false, because we are only interested
74 /// in types that the user could actually have written --- in
75 /// other words, we consider `$0 : Bar` to be unimplemented if
76 /// there is no type that the user could *actually name* that
77 /// would satisfy it. This avoids crippling inference, basically.
82 // A stack that walks back up the stack frame.
83 struct TraitObligationStack
<'prev
, 'tcx
: 'prev
> {
84 obligation
: &'prev TraitObligation
<'tcx
>,
86 /// Trait ref from `obligation` but skolemized with the
87 /// selection-context's freshener. Used to check for recursion.
88 fresh_trait_ref
: ty
::PolyTraitRef
<'tcx
>,
90 previous
: TraitObligationStackList
<'prev
, 'tcx
>,
94 pub struct SelectionCache
<'tcx
> {
95 hashmap
: RefCell
<FnvHashMap
<ty
::TraitRef
<'tcx
>,
96 SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>>>,
99 pub enum MethodMatchResult
{
100 MethodMatched(MethodMatchedData
),
101 MethodAmbiguous(/* list of impls that could apply */ Vec
<DefId
>),
105 #[derive(Copy, Clone, Debug)]
106 pub enum MethodMatchedData
{
107 // In the case of a precise match, we don't really need to store
108 // how the match was found. So don't.
111 // In the case of a coercion, we need to know the precise impl so
112 // that we can determine the type to which things were coerced.
113 CoerciveMethodMatch(/* impl we matched */ DefId
)
116 /// The selection process begins by considering all impls, where
117 /// clauses, and so forth that might resolve an obligation. Sometimes
118 /// we'll be able to say definitively that (e.g.) an impl does not
119 /// apply to the obligation: perhaps it is defined for `usize` but the
120 /// obligation is for `int`. In that case, we drop the impl out of the
121 /// list. But the other cases are considered *candidates*.
123 /// For selection to succeed, there must be exactly one matching
124 /// candidate. If the obligation is fully known, this is guaranteed
125 /// by coherence. However, if the obligation contains type parameters
126 /// or variables, there may be multiple such impls.
128 /// It is not a real problem if multiple matching impls exist because
129 /// of type variables - it just means the obligation isn't sufficiently
130 /// elaborated. In that case we report an ambiguity, and the caller can
131 /// try again after more type information has been gathered or report a
132 /// "type annotations required" error.
134 /// However, with type parameters, this can be a real problem - type
135 /// parameters don't unify with regular types, but they *can* unify
136 /// with variables from blanket impls, and (unless we know its bounds
137 /// will always be satisfied) picking the blanket impl will be wrong
138 /// for at least *some* substitutions. To make this concrete, if we have
140 /// trait AsDebug { type Out : fmt::Debug; fn debug(self) -> Self::Out; }
141 /// impl<T: fmt::Debug> AsDebug for T {
143 /// fn debug(self) -> fmt::Debug { self }
145 /// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); }
147 /// we can't just use the impl to resolve the <T as AsDebug> obligation
148 /// - a type from another crate (that doesn't implement fmt::Debug) could
149 /// implement AsDebug.
151 /// Because where-clauses match the type exactly, multiple clauses can
152 /// only match if there are unresolved variables, and we can mostly just
153 /// report this ambiguity in that case. This is still a problem - we can't
154 /// *do anything* with ambiguities that involve only regions. This is issue
157 /// If a single where-clause matches and there are no inference
158 /// variables left, then it definitely matches and we can just select
161 /// In fact, we even select the where-clause when the obligation contains
162 /// inference variables. The can lead to inference making "leaps of logic",
163 /// for example in this situation:
165 /// pub trait Foo<T> { fn foo(&self) -> T; }
166 /// impl<T> Foo<()> for T { fn foo(&self) { } }
167 /// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } }
169 /// pub fn foo<T>(t: T) where T: Foo<bool> {
170 /// println!("{:?}", <T as Foo<_>>::foo(&t));
172 /// fn main() { foo(false); }
174 /// Here the obligation <T as Foo<$0>> can be matched by both the blanket
175 /// impl and the where-clause. We select the where-clause and unify $0=bool,
176 /// so the program prints "false". However, if the where-clause is omitted,
177 /// the blanket impl is selected, we unify $0=(), and the program prints
180 /// Exactly the same issues apply to projection and object candidates, except
181 /// that we can have both a projection candidate and a where-clause candidate
182 /// for the same obligation. In that case either would do (except that
183 /// different "leaps of logic" would occur if inference variables are
184 /// present), and we just pick the where-clause. This is, for example,
185 /// required for associated types to work in default impls, as the bounds
186 /// are visible both as projection bounds and as where-clauses from the
187 /// parameter environment.
188 #[derive(PartialEq,Eq,Debug,Clone)]
189 enum SelectionCandidate
<'tcx
> {
190 BuiltinCandidate(ty
::BuiltinBound
),
191 ParamCandidate(ty
::PolyTraitRef
<'tcx
>),
192 ImplCandidate(DefId
),
193 DefaultImplCandidate(DefId
),
194 DefaultImplObjectCandidate(DefId
),
196 /// This is a trait matching with a projected type as `Self`, and
197 /// we found an applicable bound in the trait definition.
200 /// Implementation of a `Fn`-family trait by one of the
201 /// anonymous types generated for a `||` expression.
202 ClosureCandidate(/* closure */ DefId
, &'tcx ty
::ClosureSubsts
<'tcx
>),
204 /// Implementation of a `Fn`-family trait by one of the anonymous
205 /// types generated for a fn pointer type (e.g., `fn(int)->int`)
210 BuiltinObjectCandidate
,
212 BuiltinUnsizeCandidate
,
215 struct SelectionCandidateSet
<'tcx
> {
216 // a list of candidates that definitely apply to the current
217 // obligation (meaning: types unify).
218 vec
: Vec
<SelectionCandidate
<'tcx
>>,
220 // if this is true, then there were candidates that might or might
221 // not have applied, but we couldn't tell. This occurs when some
222 // of the input types are type variables, in which case there are
223 // various "builtin" rules that might or might not trigger.
227 enum BuiltinBoundConditions
<'tcx
> {
228 If(ty
::Binder
<Vec
<Ty
<'tcx
>>>),
233 #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
234 /// The result of trait evaluation. The order is important
235 /// here as the evaluation of a list is the maximum of the
237 enum EvaluationResult
{
238 /// Evaluation successful
240 /// Evaluation failed because of recursion - treated as ambiguous
242 /// Evaluation is known to be ambiguous
244 /// Evaluation failed
249 pub struct EvaluationCache
<'tcx
> {
250 hashmap
: RefCell
<FnvHashMap
<ty
::PolyTraitRef
<'tcx
>, EvaluationResult
>>
253 impl<'cx
, 'tcx
> SelectionContext
<'cx
, 'tcx
> {
254 pub fn new(infcx
: &'cx InferCtxt
<'cx
, 'tcx
>)
255 -> SelectionContext
<'cx
, 'tcx
> {
258 freshener
: infcx
.freshener(),
263 pub fn intercrate(infcx
: &'cx InferCtxt
<'cx
, 'tcx
>)
264 -> SelectionContext
<'cx
, 'tcx
> {
267 freshener
: infcx
.freshener(),
272 pub fn infcx(&self) -> &'cx InferCtxt
<'cx
, 'tcx
> {
276 pub fn tcx(&self) -> &'cx ty
::ctxt
<'tcx
> {
280 pub fn param_env(&self) -> &'cx ty
::ParameterEnvironment
<'cx
, 'tcx
> {
281 self.infcx
.param_env()
284 pub fn closure_typer(&self) -> &'cx InferCtxt
<'cx
, 'tcx
> {
288 ///////////////////////////////////////////////////////////////////////////
291 // The selection phase tries to identify *how* an obligation will
292 // be resolved. For example, it will identify which impl or
293 // parameter bound is to be used. The process can be inconclusive
294 // if the self type in the obligation is not fully inferred. Selection
295 // can result in an error in one of two ways:
297 // 1. If no applicable impl or parameter bound can be found.
298 // 2. If the output type parameters in the obligation do not match
299 // those specified by the impl/bound. For example, if the obligation
300 // is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
301 // `impl<T> Iterable<T> for Vec<T>`, than an error would result.
303 /// Attempts to satisfy the obligation. If successful, this will affect the surrounding
304 /// type environment by performing unification.
305 pub fn select(&mut self, obligation
: &TraitObligation
<'tcx
>)
306 -> SelectionResult
<'tcx
, Selection
<'tcx
>> {
307 debug
!("select({:?})", obligation
);
308 assert
!(!obligation
.predicate
.has_escaping_regions());
310 let dep_node
= obligation
.predicate
.dep_node();
311 let _task
= self.tcx().dep_graph
.in_task(dep_node
);
313 let stack
= self.push_stack(TraitObligationStackList
::empty(), obligation
);
314 match try
!(self.candidate_from_obligation(&stack
)) {
316 self.consider_unification_despite_ambiguity(obligation
);
319 Some(candidate
) => Ok(Some(try
!(self.confirm_candidate(obligation
, candidate
)))),
323 /// In the particular case of unboxed closure obligations, we can
324 /// sometimes do some amount of unification for the
325 /// argument/return types even though we can't yet fully match obligation.
326 /// The particular case we are interesting in is an obligation of the form:
330 /// where `C` is an unboxed closure type and `FnFoo` is one of the
331 /// `Fn` traits. Because we know that users cannot write impls for closure types
332 /// themselves, the only way that `C : FnFoo` can fail to match is under two
335 /// 1. The closure kind for `C` is not yet known, because inference isn't complete.
336 /// 2. The closure kind for `C` *is* known, but doesn't match what is needed.
337 /// For example, `C` may be a `FnOnce` closure, but a `Fn` closure is needed.
339 /// In either case, we always know what argument types are
340 /// expected by `C`, no matter what kind of `Fn` trait it
341 /// eventually matches. So we can go ahead and unify the argument
342 /// types, even though the end result is ambiguous.
344 /// Note that this is safe *even if* the trait would never be
345 /// matched (case 2 above). After all, in that case, an error will
346 /// result, so it kind of doesn't matter what we do --- unifying
347 /// the argument types can only be helpful to the user, because
348 /// once they patch up the kind of closure that is expected, the
349 /// argment types won't really change.
350 fn consider_unification_despite_ambiguity(&mut self, obligation
: &TraitObligation
<'tcx
>) {
351 // Is this a `C : FnFoo(...)` trait reference for some trait binding `FnFoo`?
352 match self.tcx().lang_items
.fn_trait_kind(obligation
.predicate
.0.def_id()) {
357 // Is the self-type a closure type? We ignore bindings here
358 // because if it is a closure type, it must be a closure type from
359 // within this current fn, and hence none of the higher-ranked
360 // lifetimes can appear inside the self-type.
361 let self_ty
= self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder());
362 let (closure_def_id
, substs
) = match self_ty
.sty
{
363 ty
::TyClosure(id
, ref substs
) => (id
, substs
),
366 assert
!(!substs
.has_escaping_regions());
368 // It is OK to call the unnormalized variant here - this is only
369 // reached for TyClosure: Fn inputs where the closure kind is
370 // still unknown, which should only occur in typeck where the
371 // closure type is already normalized.
372 let closure_trait_ref
= self.closure_trait_ref_unnormalized(obligation
,
376 match self.confirm_poly_trait_refs(obligation
.cause
.clone(),
377 obligation
.predicate
.to_poly_trait_ref(),
380 Err(_
) => { /* Silently ignore errors. */ }
384 ///////////////////////////////////////////////////////////////////////////
387 // Tests whether an obligation can be selected or whether an impl
388 // can be applied to particular types. It skips the "confirmation"
389 // step and hence completely ignores output type parameters.
391 // The result is "true" if the obligation *may* hold and "false" if
392 // we can be sure it does not.
395 /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
396 pub fn evaluate_obligation(&mut self,
397 obligation
: &PredicateObligation
<'tcx
>)
400 debug
!("evaluate_obligation({:?})",
403 self.infcx
.probe(|_
| {
404 self.evaluate_predicate_recursively(TraitObligationStackList
::empty(), obligation
)
409 /// Evaluates whether the obligation `obligation` can be satisfied,
410 /// and returns `false` if not certain. However, this is not entirely
411 /// accurate if inference variables are involved.
412 pub fn evaluate_obligation_conservatively(&mut self,
413 obligation
: &PredicateObligation
<'tcx
>)
416 debug
!("evaluate_obligation_conservatively({:?})",
419 self.infcx
.probe(|_
| {
420 self.evaluate_predicate_recursively(TraitObligationStackList
::empty(), obligation
)
425 /// Evaluates the predicates in `predicates` recursively. Note that
426 /// this applies projections in the predicates, and therefore
427 /// is run within an inference probe.
428 fn evaluate_predicates_recursively
<'a
,'o
,I
>(&mut self,
429 stack
: TraitObligationStackList
<'o
, 'tcx
>,
432 where I
: Iterator
<Item
=&'a PredicateObligation
<'tcx
>>, 'tcx
:'a
434 let mut result
= EvaluatedToOk
;
435 for obligation
in predicates
{
436 let eval
= self.evaluate_predicate_recursively(stack
, obligation
);
437 debug
!("evaluate_predicate_recursively({:?}) = {:?}",
440 EvaluatedToErr
=> { return EvaluatedToErr; }
441 EvaluatedToAmbig
=> { result = EvaluatedToAmbig; }
442 EvaluatedToUnknown
=> {
443 if result
< EvaluatedToUnknown
{
444 result
= EvaluatedToUnknown
;
453 fn evaluate_predicate_recursively
<'o
>(&mut self,
454 previous_stack
: TraitObligationStackList
<'o
, 'tcx
>,
455 obligation
: &PredicateObligation
<'tcx
>)
458 debug
!("evaluate_predicate_recursively({:?})",
461 // Check the cache from the tcx of predicates that we know
462 // have been proven elsewhere. This cache only contains
463 // predicates that are global in scope and hence unaffected by
464 // the current environment.
465 if self.tcx().fulfilled_predicates
.borrow().check_duplicate(&obligation
.predicate
) {
466 return EvaluatedToOk
;
469 match obligation
.predicate
{
470 ty
::Predicate
::Trait(ref t
) => {
471 assert
!(!t
.has_escaping_regions());
472 let obligation
= obligation
.with(t
.clone());
473 self.evaluate_obligation_recursively(previous_stack
, &obligation
)
476 ty
::Predicate
::Equate(ref p
) => {
477 // does this code ever run?
478 match self.infcx
.equality_predicate(obligation
.cause
.span
, p
) {
479 Ok(()) => EvaluatedToOk
,
480 Err(_
) => EvaluatedToErr
484 ty
::Predicate
::WellFormed(ty
) => {
485 match ty
::wf
::obligations(self.infcx
, obligation
.cause
.body_id
,
486 ty
, obligation
.cause
.span
) {
488 self.evaluate_predicates_recursively(previous_stack
, obligations
.iter()),
494 ty
::Predicate
::TypeOutlives(..) | ty
::Predicate
::RegionOutlives(..) => {
495 // we do not consider region relationships when
496 // evaluating trait matches
500 ty
::Predicate
::ObjectSafe(trait_def_id
) => {
501 if object_safety
::is_object_safe(self.tcx(), trait_def_id
) {
508 ty
::Predicate
::Projection(ref data
) => {
509 let project_obligation
= obligation
.with(data
.clone());
510 match project
::poly_project_and_unify_type(self, &project_obligation
) {
511 Ok(Some(subobligations
)) => {
512 self.evaluate_predicates_recursively(previous_stack
,
513 subobligations
.iter())
526 fn evaluate_obligation_recursively
<'o
>(&mut self,
527 previous_stack
: TraitObligationStackList
<'o
, 'tcx
>,
528 obligation
: &TraitObligation
<'tcx
>)
531 debug
!("evaluate_obligation_recursively({:?})",
534 let stack
= self.push_stack(previous_stack
, obligation
);
535 let fresh_trait_ref
= stack
.fresh_trait_ref
;
536 if let Some(result
) = self.check_evaluation_cache(fresh_trait_ref
) {
537 debug
!("CACHE HIT: EVAL({:?})={:?}",
543 let result
= self.evaluate_stack(&stack
);
545 debug
!("CACHE MISS: EVAL({:?})={:?}",
548 self.insert_evaluation_cache(fresh_trait_ref
, result
);
553 fn evaluate_stack
<'o
>(&mut self,
554 stack
: &TraitObligationStack
<'o
, 'tcx
>)
557 // In intercrate mode, whenever any of the types are unbound,
558 // there can always be an impl. Even if there are no impls in
559 // this crate, perhaps the type would be unified with
560 // something from another crate that does provide an impl.
562 // In intracrate mode, we must still be conservative. The reason is
563 // that we want to avoid cycles. Imagine an impl like:
565 // impl<T:Eq> Eq for Vec<T>
567 // and a trait reference like `$0 : Eq` where `$0` is an
568 // unbound variable. When we evaluate this trait-reference, we
569 // will unify `$0` with `Vec<$1>` (for some fresh variable
570 // `$1`), on the condition that `$1 : Eq`. We will then wind
571 // up with many candidates (since that are other `Eq` impls
572 // that apply) and try to winnow things down. This results in
573 // a recursive evaluation that `$1 : Eq` -- as you can
574 // imagine, this is just where we started. To avoid that, we
575 // check for unbound variables and return an ambiguous (hence possible)
576 // match if we've seen this trait before.
578 // This suffices to allow chains like `FnMut` implemented in
579 // terms of `Fn` etc, but we could probably make this more
581 let input_types
= stack
.fresh_trait_ref
.0.input_types
();
582 let unbound_input_types
= input_types
.iter().any(|ty
| ty
.is_fresh());
583 if unbound_input_types
&& self.intercrate
{
584 debug
!("evaluate_stack({:?}) --> unbound argument, intercrate --> ambiguous",
585 stack
.fresh_trait_ref
);
586 return EvaluatedToAmbig
;
588 if unbound_input_types
&&
589 stack
.iter().skip(1).any(
590 |prev
| self.match_fresh_trait_refs(&stack
.fresh_trait_ref
,
591 &prev
.fresh_trait_ref
))
593 debug
!("evaluate_stack({:?}) --> unbound argument, recursive --> giving up",
594 stack
.fresh_trait_ref
);
595 return EvaluatedToUnknown
;
598 // If there is any previous entry on the stack that precisely
599 // matches this obligation, then we can assume that the
600 // obligation is satisfied for now (still all other conditions
601 // must be met of course). One obvious case this comes up is
602 // marker traits like `Send`. Think of a linked list:
604 // struct List<T> { data: T, next: Option<Box<List<T>>> {
606 // `Box<List<T>>` will be `Send` if `T` is `Send` and
607 // `Option<Box<List<T>>>` is `Send`, and in turn
608 // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
611 // Note that we do this comparison using the `fresh_trait_ref`
612 // fields. Because these have all been skolemized using
613 // `self.freshener`, we can be sure that (a) this will not
614 // affect the inferencer state and (b) that if we see two
615 // skolemized types with the same index, they refer to the
616 // same unbound type variable.
619 .skip(1) // skip top-most frame
620 .any(|prev
| stack
.fresh_trait_ref
== prev
.fresh_trait_ref
)
622 debug
!("evaluate_stack({:?}) --> recursive",
623 stack
.fresh_trait_ref
);
624 return EvaluatedToOk
;
627 match self.candidate_from_obligation(stack
) {
628 Ok(Some(c
)) => self.evaluate_candidate(stack
, &c
),
629 Ok(None
) => EvaluatedToAmbig
,
630 Err(..) => EvaluatedToErr
634 /// Further evaluate `candidate` to decide whether all type parameters match and whether nested
635 /// obligations are met. Returns true if `candidate` remains viable after this further
637 fn evaluate_candidate
<'o
>(&mut self,
638 stack
: &TraitObligationStack
<'o
, 'tcx
>,
639 candidate
: &SelectionCandidate
<'tcx
>)
642 debug
!("evaluate_candidate: depth={} candidate={:?}",
643 stack
.obligation
.recursion_depth
, candidate
);
644 let result
= self.infcx
.probe(|_
| {
645 let candidate
= (*candidate
).clone();
646 match self.confirm_candidate(stack
.obligation
, candidate
) {
648 self.evaluate_predicates_recursively(
650 selection
.nested_obligations().iter())
652 Err(..) => EvaluatedToErr
655 debug
!("evaluate_candidate: depth={} result={:?}",
656 stack
.obligation
.recursion_depth
, result
);
660 fn pick_evaluation_cache(&self) -> &EvaluationCache
<'tcx
> {
661 // see comment in `pick_candidate_cache`
662 if self.intercrate
||
663 !self.param_env().caller_bounds
.is_empty()
665 &self.param_env().evaluation_cache
668 &self.tcx().evaluation_cache
672 fn check_evaluation_cache(&self, trait_ref
: ty
::PolyTraitRef
<'tcx
>)
673 -> Option
<EvaluationResult
>
675 let cache
= self.pick_evaluation_cache();
676 cache
.hashmap
.borrow().get(&trait_ref
).cloned()
679 fn insert_evaluation_cache(&mut self,
680 trait_ref
: ty
::PolyTraitRef
<'tcx
>,
681 result
: EvaluationResult
)
683 // Avoid caching results that depend on more than just the trait-ref:
684 // The stack can create EvaluatedToUnknown, and closure signatures
685 // being yet uninferred can create "spurious" EvaluatedToAmbig
686 // and EvaluatedToOk.
687 if result
== EvaluatedToUnknown
||
688 ((result
== EvaluatedToAmbig
|| result
== EvaluatedToOk
)
689 && trait_ref
.has_closure_types())
694 let cache
= self.pick_evaluation_cache();
695 cache
.hashmap
.borrow_mut().insert(trait_ref
, result
);
698 ///////////////////////////////////////////////////////////////////////////
699 // CANDIDATE ASSEMBLY
701 // The selection process begins by examining all in-scope impls,
702 // caller obligations, and so forth and assembling a list of
703 // candidates. See `README.md` and the `Candidate` type for more
706 fn candidate_from_obligation
<'o
>(&mut self,
707 stack
: &TraitObligationStack
<'o
, 'tcx
>)
708 -> SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>
710 // Watch out for overflow. This intentionally bypasses (and does
711 // not update) the cache.
712 let recursion_limit
= self.infcx
.tcx
.sess
.recursion_limit
.get();
713 if stack
.obligation
.recursion_depth
>= recursion_limit
{
714 report_overflow_error(self.infcx(), &stack
.obligation
, true);
717 // Check the cache. Note that we skolemize the trait-ref
718 // separately rather than using `stack.fresh_trait_ref` -- this
719 // is because we want the unbound variables to be replaced
720 // with fresh skolemized types starting from index 0.
721 let cache_fresh_trait_pred
=
722 self.infcx
.freshen(stack
.obligation
.predicate
.clone());
723 debug
!("candidate_from_obligation(cache_fresh_trait_pred={:?}, obligation={:?})",
724 cache_fresh_trait_pred
,
726 assert
!(!stack
.obligation
.predicate
.has_escaping_regions());
728 match self.check_candidate_cache(&cache_fresh_trait_pred
) {
730 debug
!("CACHE HIT: SELECT({:?})={:?}",
731 cache_fresh_trait_pred
,
738 // If no match, compute result and insert into cache.
739 let candidate
= self.candidate_from_obligation_no_cache(stack
);
741 if self.should_update_candidate_cache(&cache_fresh_trait_pred
, &candidate
) {
742 debug
!("CACHE MISS: SELECT({:?})={:?}",
743 cache_fresh_trait_pred
, candidate
);
744 self.insert_candidate_cache(cache_fresh_trait_pred
, candidate
.clone());
750 fn candidate_from_obligation_no_cache
<'o
>(&mut self,
751 stack
: &TraitObligationStack
<'o
, 'tcx
>)
752 -> SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>
754 if stack
.obligation
.predicate
.references_error() {
755 // If we encounter a `TyError`, we generally prefer the
756 // most "optimistic" result in response -- that is, the
757 // one least likely to report downstream errors. But
758 // because this routine is shared by coherence and by
759 // trait selection, there isn't an obvious "right" choice
760 // here in that respect, so we opt to just return
761 // ambiguity and let the upstream clients sort it out.
765 if !self.is_knowable(stack
) {
766 debug
!("intercrate not knowable");
770 let candidate_set
= try
!(self.assemble_candidates(stack
));
772 if candidate_set
.ambiguous
{
773 debug
!("candidate set contains ambig");
777 let mut candidates
= candidate_set
.vec
;
779 debug
!("assembled {} candidates for {:?}: {:?}",
784 // At this point, we know that each of the entries in the
785 // candidate set is *individually* applicable. Now we have to
786 // figure out if they contain mutual incompatibilities. This
787 // frequently arises if we have an unconstrained input type --
788 // for example, we are looking for $0:Eq where $0 is some
789 // unconstrained type variable. In that case, we'll get a
790 // candidate which assumes $0 == int, one that assumes $0 ==
791 // usize, etc. This spells an ambiguity.
793 // If there is more than one candidate, first winnow them down
794 // by considering extra conditions (nested obligations and so
795 // forth). We don't winnow if there is exactly one
796 // candidate. This is a relatively minor distinction but it
797 // can lead to better inference and error-reporting. An
798 // example would be if there was an impl:
800 // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
802 // and we were to see some code `foo.push_clone()` where `boo`
803 // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
804 // we were to winnow, we'd wind up with zero candidates.
805 // Instead, we select the right impl now but report `Bar does
806 // not implement Clone`.
807 if candidates
.len() > 1 {
808 candidates
.retain(|c
| self.evaluate_candidate(stack
, c
).may_apply())
811 // If there are STILL multiple candidate, we can further reduce
812 // the list by dropping duplicates.
813 if candidates
.len() > 1 {
815 while i
< candidates
.len() {
817 (0..candidates
.len())
819 .any(|j
| self.candidate_should_be_dropped_in_favor_of(&candidates
[i
],
822 debug
!("Dropping candidate #{}/{}: {:?}",
823 i
, candidates
.len(), candidates
[i
]);
824 candidates
.swap_remove(i
);
826 debug
!("Retaining candidate #{}/{}: {:?}",
827 i
, candidates
.len(), candidates
[i
]);
833 // If there are *STILL* multiple candidates, give up and
835 if candidates
.len() > 1 {
836 debug
!("multiple matches, ambig");
841 // If there are *NO* candidates, that there are no impls --
842 // that we know of, anyway. Note that in the case where there
843 // are unbound type variables within the obligation, it might
844 // be the case that you could still satisfy the obligation
845 // from another crate by instantiating the type variables with
846 // a type from another crate that does have an impl. This case
847 // is checked for in `evaluate_stack` (and hence users
848 // who might care about this case, like coherence, should use
850 if candidates
.is_empty() {
851 return Err(Unimplemented
);
854 // Just one candidate left.
855 let candidate
= candidates
.pop().unwrap();
858 ImplCandidate(def_id
) => {
859 match self.tcx().trait_impl_polarity(def_id
) {
860 Some(hir
::ImplPolarity
::Negative
) => return Err(Unimplemented
),
870 fn is_knowable
<'o
>(&mut self,
871 stack
: &TraitObligationStack
<'o
, 'tcx
>)
874 debug
!("is_knowable(intercrate={})", self.intercrate
);
876 if !self.intercrate
{
880 let obligation
= &stack
.obligation
;
881 let predicate
= self.infcx().resolve_type_vars_if_possible(&obligation
.predicate
);
883 // ok to skip binder because of the nature of the
884 // trait-ref-is-knowable check, which does not care about
886 let trait_ref
= &predicate
.skip_binder().trait_ref
;
888 coherence
::trait_ref_is_knowable(self.tcx(), trait_ref
)
891 fn pick_candidate_cache(&self) -> &SelectionCache
<'tcx
> {
892 // If there are any where-clauses in scope, then we always use
893 // a cache local to this particular scope. Otherwise, we
894 // switch to a global cache. We used to try and draw
895 // finer-grained distinctions, but that led to a serious of
896 // annoying and weird bugs like #22019 and #18290. This simple
897 // rule seems to be pretty clearly safe and also still retains
898 // a very high hit rate (~95% when compiling rustc).
899 if !self.param_env().caller_bounds
.is_empty() {
900 return &self.param_env().selection_cache
;
903 // Avoid using the master cache during coherence and just rely
904 // on the local cache. This effectively disables caching
905 // during coherence. It is really just a simplification to
906 // avoid us having to fear that coherence results "pollute"
907 // the master cache. Since coherence executes pretty quickly,
908 // it's not worth going to more trouble to increase the
909 // hit-rate I don't think.
911 return &self.param_env().selection_cache
;
914 // Otherwise, we can use the global cache.
915 &self.tcx().selection_cache
918 fn check_candidate_cache(&mut self,
919 cache_fresh_trait_pred
: &ty
::PolyTraitPredicate
<'tcx
>)
920 -> Option
<SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>>
922 let cache
= self.pick_candidate_cache();
923 let hashmap
= cache
.hashmap
.borrow();
924 hashmap
.get(&cache_fresh_trait_pred
.0.trait_ref
).cloned()
927 fn insert_candidate_cache(&mut self,
928 cache_fresh_trait_pred
: ty
::PolyTraitPredicate
<'tcx
>,
929 candidate
: SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>)
931 let cache
= self.pick_candidate_cache();
932 let mut hashmap
= cache
.hashmap
.borrow_mut();
933 hashmap
.insert(cache_fresh_trait_pred
.0.trait_ref
.clone(), candidate
);
936 fn should_update_candidate_cache(&mut self,
937 cache_fresh_trait_pred
: &ty
::PolyTraitPredicate
<'tcx
>,
938 candidate
: &SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>)
941 // In general, it's a good idea to cache results, even
942 // ambiguous ones, to save us some trouble later. But we have
943 // to be careful not to cache results that could be
944 // invalidated later by advances in inference. Normally, this
945 // is not an issue, because any inference variables whose
946 // types are not yet bound are "freshened" in the cache key,
947 // which means that if we later get the same request once that
948 // type variable IS bound, we'll have a different cache key.
949 // For example, if we have `Vec<_#0t> : Foo`, and `_#0t` is
950 // not yet known, we may cache the result as `None`. But if
951 // later `_#0t` is bound to `Bar`, then when we freshen we'll
952 // have `Vec<Bar> : Foo` as the cache key.
954 // HOWEVER, it CAN happen that we get an ambiguity result in
955 // one particular case around closures where the cache key
956 // would not change. That is when the precise types of the
957 // upvars that a closure references have not yet been figured
958 // out (i.e., because it is not yet known if they are captured
959 // by ref, and if by ref, what kind of ref). In these cases,
960 // when matching a builtin bound, we will yield back an
961 // ambiguous result. But the *cache key* is just the closure type,
962 // it doesn't capture the state of the upvar computation.
964 // To avoid this trap, just don't cache ambiguous results if
965 // the self-type contains no inference byproducts (that really
966 // shouldn't happen in other circumstances anyway, given
970 Ok(Some(_
)) | Err(_
) => true,
972 cache_fresh_trait_pred
.0.trait_ref
.substs
.types
.has_infer_types()
977 fn assemble_candidates
<'o
>(&mut self,
978 stack
: &TraitObligationStack
<'o
, 'tcx
>)
979 -> Result
<SelectionCandidateSet
<'tcx
>, SelectionError
<'tcx
>>
981 let TraitObligationStack { obligation, .. }
= *stack
;
982 let ref obligation
= Obligation
{
983 cause
: obligation
.cause
.clone(),
984 recursion_depth
: obligation
.recursion_depth
,
985 predicate
: self.infcx().resolve_type_vars_if_possible(&obligation
.predicate
)
988 if obligation
.predicate
.skip_binder().self_ty().is_ty_var() {
989 // FIXME(#20297): Self is a type variable (e.g. `_: AsRef<str>`).
991 // This is somewhat problematic, as the current scheme can't really
992 // handle it turning to be a projection. This does end up as truly
993 // ambiguous in most cases anyway.
995 // Until this is fixed, take the fast path out - this also improves
996 // performance by preventing assemble_candidates_from_impls from
997 // matching every impl for this trait.
998 return Ok(SelectionCandidateSet { vec: vec![], ambiguous: true }
);
1001 let mut candidates
= SelectionCandidateSet
{
1006 // Other bounds. Consider both in-scope bounds from fn decl
1007 // and applicable impls. There is a certain set of precedence rules here.
1009 match self.tcx().lang_items
.to_builtin_kind(obligation
.predicate
.def_id()) {
1010 Some(ty
::BoundCopy
) => {
1011 debug
!("obligation self ty is {:?}",
1012 obligation
.predicate
.0.self_ty());
1014 // User-defined copy impls are permitted, but only for
1015 // structs and enums.
1016 try
!(self.assemble_candidates_from_impls(obligation
, &mut candidates
));
1018 // For other types, we'll use the builtin rules.
1019 try
!(self.assemble_builtin_bound_candidates(ty
::BoundCopy
,
1023 Some(bound @ ty
::BoundSized
) => {
1024 // Sized is never implementable by end-users, it is
1025 // always automatically computed.
1026 try
!(self.assemble_builtin_bound_candidates(bound
,
1031 None
if self.tcx().lang_items
.unsize_trait() ==
1032 Some(obligation
.predicate
.def_id()) => {
1033 self.assemble_candidates_for_unsizing(obligation
, &mut candidates
);
1036 Some(ty
::BoundSend
) |
1037 Some(ty
::BoundSync
) |
1039 try
!(self.assemble_closure_candidates(obligation
, &mut candidates
));
1040 try
!(self.assemble_fn_pointer_candidates(obligation
, &mut candidates
));
1041 try
!(self.assemble_candidates_from_impls(obligation
, &mut candidates
));
1042 self.assemble_candidates_from_object_ty(obligation
, &mut candidates
);
1046 self.assemble_candidates_from_projected_tys(obligation
, &mut candidates
);
1047 try
!(self.assemble_candidates_from_caller_bounds(stack
, &mut candidates
));
1048 // Default implementations have lower priority, so we only
1049 // consider triggering a default if there is no other impl that can apply.
1050 if candidates
.vec
.is_empty() {
1051 try
!(self.assemble_candidates_from_default_impls(obligation
, &mut candidates
));
1053 debug
!("candidate list size: {}", candidates
.vec
.len());
1057 fn assemble_candidates_from_projected_tys(&mut self,
1058 obligation
: &TraitObligation
<'tcx
>,
1059 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1061 debug
!("assemble_candidates_for_projected_tys({:?})", obligation
);
1063 // FIXME(#20297) -- just examining the self-type is very simplistic
1065 // before we go into the whole skolemization thing, just
1066 // quickly check if the self-type is a projection at all.
1067 let trait_def_id
= match obligation
.predicate
.0.trait_ref
.self_ty().sty
{
1068 ty
::TyProjection(ref data
) => data
.trait_ref
.def_id
,
1069 ty
::TyInfer(ty
::TyVar(_
)) => {
1070 self.tcx().sess
.span_bug(obligation
.cause
.span
,
1071 "Self=_ should have been handled by assemble_candidates");
1076 debug
!("assemble_candidates_for_projected_tys: trait_def_id={:?}",
1079 let result
= self.infcx
.probe(|snapshot
| {
1080 self.match_projection_obligation_against_bounds_from_trait(obligation
,
1085 candidates
.vec
.push(ProjectionCandidate
);
1089 fn match_projection_obligation_against_bounds_from_trait(
1091 obligation
: &TraitObligation
<'tcx
>,
1092 snapshot
: &infer
::CombinedSnapshot
)
1095 let poly_trait_predicate
=
1096 self.infcx().resolve_type_vars_if_possible(&obligation
.predicate
);
1097 let (skol_trait_predicate
, skol_map
) =
1098 self.infcx().skolemize_late_bound_regions(&poly_trait_predicate
, snapshot
);
1099 debug
!("match_projection_obligation_against_bounds_from_trait: \
1100 skol_trait_predicate={:?} skol_map={:?}",
1101 skol_trait_predicate
,
1104 let projection_trait_ref
= match skol_trait_predicate
.trait_ref
.self_ty().sty
{
1105 ty
::TyProjection(ref data
) => &data
.trait_ref
,
1107 self.tcx().sess
.span_bug(
1108 obligation
.cause
.span
,
1109 &format
!("match_projection_obligation_against_bounds_from_trait() called \
1110 but self-ty not a projection: {:?}",
1111 skol_trait_predicate
.trait_ref
.self_ty()));
1114 debug
!("match_projection_obligation_against_bounds_from_trait: \
1115 projection_trait_ref={:?}",
1116 projection_trait_ref
);
1118 let trait_predicates
= self.tcx().lookup_predicates(projection_trait_ref
.def_id
);
1119 let bounds
= trait_predicates
.instantiate(self.tcx(), projection_trait_ref
.substs
);
1120 debug
!("match_projection_obligation_against_bounds_from_trait: \
1124 let matching_bound
=
1125 util
::elaborate_predicates(self.tcx(), bounds
.predicates
.into_vec())
1128 |bound
| self.infcx
.probe(
1129 |_
| self.match_projection(obligation
,
1131 skol_trait_predicate
.trait_ref
.clone(),
1135 debug
!("match_projection_obligation_against_bounds_from_trait: \
1136 matching_bound={:?}",
1138 match matching_bound
{
1141 // Repeat the successful match, if any, this time outside of a probe.
1142 let result
= self.match_projection(obligation
,
1144 skol_trait_predicate
.trait_ref
.clone(),
1153 fn match_projection(&mut self,
1154 obligation
: &TraitObligation
<'tcx
>,
1155 trait_bound
: ty
::PolyTraitRef
<'tcx
>,
1156 skol_trait_ref
: ty
::TraitRef
<'tcx
>,
1157 skol_map
: &infer
::SkolemizationMap
,
1158 snapshot
: &infer
::CombinedSnapshot
)
1161 assert
!(!skol_trait_ref
.has_escaping_regions());
1162 let origin
= TypeOrigin
::RelateOutputImplTypes(obligation
.cause
.span
);
1163 match self.infcx
.sub_poly_trait_refs(false,
1165 trait_bound
.clone(),
1166 ty
::Binder(skol_trait_ref
.clone())) {
1168 Err(_
) => { return false; }
1171 self.infcx
.leak_check(skol_map
, snapshot
).is_ok()
1174 /// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller
1175 /// supplied to find out whether it is listed among them.
1177 /// Never affects inference environment.
1178 fn assemble_candidates_from_caller_bounds
<'o
>(&mut self,
1179 stack
: &TraitObligationStack
<'o
, 'tcx
>,
1180 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1181 -> Result
<(),SelectionError
<'tcx
>>
1183 debug
!("assemble_candidates_from_caller_bounds({:?})",
1187 self.param_env().caller_bounds
1189 .filter_map(|o
| o
.to_opt_poly_trait_ref());
1191 let matching_bounds
=
1193 |bound
| self.evaluate_where_clause(stack
, bound
.clone()).may_apply());
1195 let param_candidates
=
1196 matching_bounds
.map(|bound
| ParamCandidate(bound
));
1198 candidates
.vec
.extend(param_candidates
);
1203 fn evaluate_where_clause
<'o
>(&mut self,
1204 stack
: &TraitObligationStack
<'o
, 'tcx
>,
1205 where_clause_trait_ref
: ty
::PolyTraitRef
<'tcx
>)
1208 self.infcx().probe(move |_
| {
1209 match self.match_where_clause_trait_ref(stack
.obligation
, where_clause_trait_ref
) {
1210 Ok(obligations
) => {
1211 self.evaluate_predicates_recursively(stack
.list(), obligations
.iter())
1213 Err(()) => EvaluatedToErr
1218 /// Check for the artificial impl that the compiler will create for an obligation like `X :
1219 /// FnMut<..>` where `X` is a closure type.
1221 /// Note: the type parameters on a closure candidate are modeled as *output* type
1222 /// parameters and hence do not affect whether this trait is a match or not. They will be
1223 /// unified during the confirmation step.
1224 fn assemble_closure_candidates(&mut self,
1225 obligation
: &TraitObligation
<'tcx
>,
1226 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1227 -> Result
<(),SelectionError
<'tcx
>>
1229 let kind
= match self.tcx().lang_items
.fn_trait_kind(obligation
.predicate
.0.def_id()) {
1231 None
=> { return Ok(()); }
1234 // ok to skip binder because the substs on closure types never
1235 // touch bound regions, they just capture the in-scope
1236 // type/region parameters
1237 let self_ty
= *obligation
.self_ty().skip_binder();
1238 let (closure_def_id
, substs
) = match self_ty
.sty
{
1239 ty
::TyClosure(id
, ref substs
) => (id
, substs
),
1240 ty
::TyInfer(ty
::TyVar(_
)) => {
1241 debug
!("assemble_unboxed_closure_candidates: ambiguous self-type");
1242 candidates
.ambiguous
= true;
1245 _
=> { return Ok(()); }
1248 debug
!("assemble_unboxed_candidates: self_ty={:?} kind={:?} obligation={:?}",
1253 match self.infcx
.closure_kind(closure_def_id
) {
1254 Some(closure_kind
) => {
1255 debug
!("assemble_unboxed_candidates: closure_kind = {:?}", closure_kind
);
1256 if closure_kind
.extends(kind
) {
1257 candidates
.vec
.push(ClosureCandidate(closure_def_id
, substs
));
1261 debug
!("assemble_unboxed_candidates: closure_kind not yet known");
1262 candidates
.ambiguous
= true;
1269 /// Implement one of the `Fn()` family for a fn pointer.
1270 fn assemble_fn_pointer_candidates(&mut self,
1271 obligation
: &TraitObligation
<'tcx
>,
1272 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1273 -> Result
<(),SelectionError
<'tcx
>>
1275 // We provide impl of all fn traits for fn pointers.
1276 if self.tcx().lang_items
.fn_trait_kind(obligation
.predicate
.def_id()).is_none() {
1280 // ok to skip binder because what we are inspecting doesn't involve bound regions
1281 let self_ty
= *obligation
.self_ty().skip_binder();
1283 ty
::TyInfer(ty
::TyVar(_
)) => {
1284 debug
!("assemble_fn_pointer_candidates: ambiguous self-type");
1285 candidates
.ambiguous
= true; // could wind up being a fn() type
1288 // provide an impl, but only for suitable `fn` pointers
1289 ty
::TyBareFn(_
, &ty
::BareFnTy
{
1290 unsafety
: hir
::Unsafety
::Normal
,
1292 sig
: ty
::Binder(ty
::FnSig
{
1294 output
: ty
::FnConverging(_
),
1298 candidates
.vec
.push(FnPointerCandidate
);
1307 /// Search for impls that might apply to `obligation`.
1308 fn assemble_candidates_from_impls(&mut self,
1309 obligation
: &TraitObligation
<'tcx
>,
1310 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1311 -> Result
<(), SelectionError
<'tcx
>>
1313 debug
!("assemble_candidates_from_impls(obligation={:?})", obligation
);
1315 let def
= self.tcx().lookup_trait_def(obligation
.predicate
.def_id());
1317 def
.for_each_relevant_impl(
1319 obligation
.predicate
.0.trait_ref
.self_ty(),
1321 self.infcx
.probe(|snapshot
| {
1322 if let Ok(_
) = self.match_impl(impl_def_id
, obligation
, snapshot
) {
1323 candidates
.vec
.push(ImplCandidate(impl_def_id
));
1332 fn assemble_candidates_from_default_impls(&mut self,
1333 obligation
: &TraitObligation
<'tcx
>,
1334 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1335 -> Result
<(), SelectionError
<'tcx
>>
1337 // OK to skip binder here because the tests we do below do not involve bound regions
1338 let self_ty
= *obligation
.self_ty().skip_binder();
1339 debug
!("assemble_candidates_from_default_impls(self_ty={:?})", self_ty
);
1341 let def_id
= obligation
.predicate
.def_id();
1343 if self.tcx().trait_has_default_impl(def_id
) {
1345 ty
::TyTrait(..) => {
1346 // For object types, we don't know what the closed
1347 // over types are. For most traits, this means we
1348 // conservatively say nothing; a candidate may be
1349 // added by `assemble_candidates_from_object_ty`.
1350 // However, for the kind of magic reflect trait,
1351 // we consider it to be implemented even for
1352 // object types, because it just lets you reflect
1353 // onto the object type, not into the object's
1355 if self.tcx().has_attr(def_id
, "rustc_reflect_like") {
1356 candidates
.vec
.push(DefaultImplObjectCandidate(def_id
));
1360 ty
::TyProjection(..) => {
1361 // In these cases, we don't know what the actual
1362 // type is. Therefore, we cannot break it down
1363 // into its constituent types. So we don't
1364 // consider the `..` impl but instead just add no
1365 // candidates: this means that typeck will only
1366 // succeed if there is another reason to believe
1367 // that this obligation holds. That could be a
1368 // where-clause or, in the case of an object type,
1369 // it could be that the object type lists the
1370 // trait (e.g. `Foo+Send : Send`). See
1371 // `compile-fail/typeck-default-trait-impl-send-param.rs`
1372 // for an example of a test case that exercises
1375 ty
::TyInfer(ty
::TyVar(_
)) => {
1376 // the defaulted impl might apply, we don't know
1377 candidates
.ambiguous
= true;
1380 candidates
.vec
.push(DefaultImplCandidate(def_id
.clone()))
1388 /// Search for impls that might apply to `obligation`.
1389 fn assemble_candidates_from_object_ty(&mut self,
1390 obligation
: &TraitObligation
<'tcx
>,
1391 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1393 debug
!("assemble_candidates_from_object_ty(self_ty={:?})",
1394 obligation
.self_ty().skip_binder());
1396 // Object-safety candidates are only applicable to object-safe
1397 // traits. Including this check is useful because it helps
1398 // inference in cases of traits like `BorrowFrom`, which are
1399 // not object-safe, and which rely on being able to infer the
1400 // self-type from one of the other inputs. Without this check,
1401 // these cases wind up being considered ambiguous due to a
1402 // (spurious) ambiguity introduced here.
1403 let predicate_trait_ref
= obligation
.predicate
.to_poly_trait_ref();
1404 if !object_safety
::is_object_safe(self.tcx(), predicate_trait_ref
.def_id()) {
1408 self.infcx
.commit_if_ok(|snapshot
| {
1410 self.infcx().skolemize_late_bound_regions(&obligation
.self_ty(), snapshot
);
1411 let poly_trait_ref
= match self_ty
.sty
{
1412 ty
::TyTrait(ref data
) => {
1413 match self.tcx().lang_items
.to_builtin_kind(obligation
.predicate
.def_id()) {
1414 Some(bound @ ty
::BoundSend
) | Some(bound @ ty
::BoundSync
) => {
1415 if data
.bounds
.builtin_bounds
.contains(&bound
) {
1416 debug
!("assemble_candidates_from_object_ty: matched builtin bound, \
1417 pushing candidate");
1418 candidates
.vec
.push(BuiltinObjectCandidate
);
1425 data
.principal_trait_ref_with_self_ty(self.tcx(), self_ty
)
1427 ty
::TyInfer(ty
::TyVar(_
)) => {
1428 debug
!("assemble_candidates_from_object_ty: ambiguous");
1429 candidates
.ambiguous
= true; // could wind up being an object type
1437 debug
!("assemble_candidates_from_object_ty: poly_trait_ref={:?}",
1440 // Count only those upcast versions that match the trait-ref
1441 // we are looking for. Specifically, do not only check for the
1442 // correct trait, but also the correct type parameters.
1443 // For example, we may be trying to upcast `Foo` to `Bar<i32>`,
1444 // but `Foo` is declared as `trait Foo : Bar<u32>`.
1445 let upcast_trait_refs
=
1446 util
::supertraits(self.tcx(), poly_trait_ref
)
1447 .filter(|upcast_trait_ref
| {
1448 self.infcx
.probe(|_
| {
1449 let upcast_trait_ref
= upcast_trait_ref
.clone();
1450 self.match_poly_trait_ref(obligation
, upcast_trait_ref
).is_ok()
1455 if upcast_trait_refs
> 1 {
1456 // can be upcast in many ways; need more type information
1457 candidates
.ambiguous
= true;
1458 } else if upcast_trait_refs
== 1 {
1459 candidates
.vec
.push(ObjectCandidate
);
1466 /// Search for unsizing that might apply to `obligation`.
1467 fn assemble_candidates_for_unsizing(&mut self,
1468 obligation
: &TraitObligation
<'tcx
>,
1469 candidates
: &mut SelectionCandidateSet
<'tcx
>) {
1470 // We currently never consider higher-ranked obligations e.g.
1471 // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
1472 // because they are a priori invalid, and we could potentially add support
1473 // for them later, it's just that there isn't really a strong need for it.
1474 // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
1475 // impl, and those are generally applied to concrete types.
1477 // That said, one might try to write a fn with a where clause like
1478 // for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
1479 // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
1480 // Still, you'd be more likely to write that where clause as
1482 // so it seems ok if we (conservatively) fail to accept that `Unsize`
1483 // obligation above. Should be possible to extend this in the future.
1484 let source
= match self.tcx().no_late_bound_regions(&obligation
.self_ty()) {
1487 // Don't add any candidates if there are bound regions.
1491 let target
= obligation
.predicate
.0.input_types
()[0];
1493 debug
!("assemble_candidates_for_unsizing(source={:?}, target={:?})",
1496 let may_apply
= match (&source
.sty
, &target
.sty
) {
1497 // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
1498 (&ty
::TyTrait(ref data_a
), &ty
::TyTrait(ref data_b
)) => {
1499 // Upcasts permit two things:
1501 // 1. Dropping builtin bounds, e.g. `Foo+Send` to `Foo`
1502 // 2. Tightening the region bound, e.g. `Foo+'a` to `Foo+'b` if `'a : 'b`
1504 // Note that neither of these changes requires any
1505 // change at runtime. Eventually this will be
1508 // We always upcast when we can because of reason
1509 // #2 (region bounds).
1510 data_a
.principal
.def_id() == data_a
.principal
.def_id() &&
1511 data_a
.bounds
.builtin_bounds
.is_superset(&data_b
.bounds
.builtin_bounds
)
1515 (_
, &ty
::TyTrait(_
)) => true,
1517 // Ambiguous handling is below T -> Trait, because inference
1518 // variables can still implement Unsize<Trait> and nested
1519 // obligations will have the final say (likely deferred).
1520 (&ty
::TyInfer(ty
::TyVar(_
)), _
) |
1521 (_
, &ty
::TyInfer(ty
::TyVar(_
))) => {
1522 debug
!("assemble_candidates_for_unsizing: ambiguous");
1523 candidates
.ambiguous
= true;
1528 (&ty
::TyArray(_
, _
), &ty
::TySlice(_
)) => true,
1530 // Struct<T> -> Struct<U>.
1531 (&ty
::TyStruct(def_id_a
, _
), &ty
::TyStruct(def_id_b
, _
)) => {
1532 def_id_a
== def_id_b
1539 candidates
.vec
.push(BuiltinUnsizeCandidate
);
1543 ///////////////////////////////////////////////////////////////////////////
1546 // Winnowing is the process of attempting to resolve ambiguity by
1547 // probing further. During the winnowing process, we unify all
1548 // type variables (ignoring skolemization) and then we also
1549 // attempt to evaluate recursive bounds to see if they are
1552 /// Returns true if `candidate_i` should be dropped in favor of
1553 /// `candidate_j`. Generally speaking we will drop duplicate
1554 /// candidates and prefer where-clause candidates.
1555 /// Returns true if `victim` should be dropped in favor of
1556 /// `other`. Generally speaking we will drop duplicate
1557 /// candidates and prefer where-clause candidates.
1559 /// See the comment for "SelectionCandidate" for more details.
1560 fn candidate_should_be_dropped_in_favor_of
<'o
>(&mut self,
1561 victim
: &SelectionCandidate
<'tcx
>,
1562 other
: &SelectionCandidate
<'tcx
>)
1565 if victim
== other
{
1571 &ParamCandidate(_
) | &ProjectionCandidate
=> match victim
{
1572 &DefaultImplCandidate(..) => {
1573 self.tcx().sess
.bug(
1574 "default implementations shouldn't be recorded \
1575 when there are other valid candidates");
1577 &ImplCandidate(..) |
1578 &ClosureCandidate(..) |
1579 &FnPointerCandidate
|
1580 &BuiltinObjectCandidate
|
1581 &BuiltinUnsizeCandidate
|
1582 &DefaultImplObjectCandidate(..) |
1583 &BuiltinCandidate(..) => {
1584 // We have a where-clause so don't go around looking
1589 &ProjectionCandidate
=> {
1590 // Arbitrarily give param candidates priority
1591 // over projection and object candidates.
1594 &ParamCandidate(..) => false,
1600 ///////////////////////////////////////////////////////////////////////////
1603 // These cover the traits that are built-in to the language
1604 // itself. This includes `Copy` and `Sized` for sure. For the
1605 // moment, it also includes `Send` / `Sync` and a few others, but
1606 // those will hopefully change to library-defined traits in the
1609 fn assemble_builtin_bound_candidates
<'o
>(&mut self,
1610 bound
: ty
::BuiltinBound
,
1611 obligation
: &TraitObligation
<'tcx
>,
1612 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1613 -> Result
<(),SelectionError
<'tcx
>>
1615 match self.builtin_bound(bound
, obligation
) {
1617 debug
!("builtin_bound: bound={:?}",
1619 candidates
.vec
.push(BuiltinCandidate(bound
));
1622 Ok(ParameterBuiltin
) => { Ok(()) }
1623 Ok(AmbiguousBuiltin
) => {
1624 debug
!("assemble_builtin_bound_candidates: ambiguous builtin");
1625 Ok(candidates
.ambiguous
= true)
1627 Err(e
) => { Err(e) }
1631 fn builtin_bound(&mut self,
1632 bound
: ty
::BuiltinBound
,
1633 obligation
: &TraitObligation
<'tcx
>)
1634 -> Result
<BuiltinBoundConditions
<'tcx
>,SelectionError
<'tcx
>>
1636 // Note: these tests operate on types that may contain bound
1637 // regions. To be proper, we ought to skolemize here, but we
1638 // forego the skolemization and defer it until the
1639 // confirmation step.
1641 let self_ty
= self.infcx
.shallow_resolve(obligation
.predicate
.0.self_ty());
1642 return match self_ty
.sty
{
1643 ty
::TyInfer(ty
::IntVar(_
)) |
1644 ty
::TyInfer(ty
::FloatVar(_
)) |
1651 // safe for everything
1655 ty
::TyBox(_
) => { // Box<T>
1657 ty
::BoundCopy
=> Err(Unimplemented
),
1659 ty
::BoundSized
=> ok_if(Vec
::new()),
1661 ty
::BoundSync
| ty
::BoundSend
=> {
1662 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1667 ty
::TyRawPtr(..) => { // *const T, *mut T
1669 ty
::BoundCopy
| ty
::BoundSized
=> ok_if(Vec
::new()),
1671 ty
::BoundSync
| ty
::BoundSend
=> {
1672 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1677 ty
::TyTrait(ref data
) => {
1679 ty
::BoundSized
=> Err(Unimplemented
),
1681 if data
.bounds
.builtin_bounds
.contains(&bound
) {
1684 // Recursively check all supertraits to find out if any further
1685 // bounds are required and thus we must fulfill.
1687 data
.principal_trait_ref_with_self_ty(self.tcx(),
1688 self.tcx().types
.err
);
1689 let copy_def_id
= obligation
.predicate
.def_id();
1690 for tr
in util
::supertraits(self.tcx(), principal
) {
1691 if tr
.def_id() == copy_def_id
{
1692 return ok_if(Vec
::new())
1699 ty
::BoundSync
| ty
::BoundSend
=> {
1700 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1705 ty
::TyRef(_
, ty
::TypeAndMut { ty: _, mutbl }
) => {
1710 // &mut T is affine and hence never `Copy`
1711 hir
::MutMutable
=> Err(Unimplemented
),
1713 // &T is always copyable
1714 hir
::MutImmutable
=> ok_if(Vec
::new()),
1718 ty
::BoundSized
=> ok_if(Vec
::new()),
1720 ty
::BoundSync
| ty
::BoundSend
=> {
1721 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1726 ty
::TyArray(element_ty
, _
) => {
1729 ty
::BoundCopy
=> ok_if(vec
![element_ty
]),
1730 ty
::BoundSized
=> ok_if(Vec
::new()),
1731 ty
::BoundSync
| ty
::BoundSend
=> {
1732 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1737 ty
::TyStr
| ty
::TySlice(_
) => {
1739 ty
::BoundSync
| ty
::BoundSend
=> {
1740 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1743 ty
::BoundCopy
| ty
::BoundSized
=> Err(Unimplemented
),
1747 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1748 ty
::TyTuple(ref tys
) => ok_if(tys
.clone()),
1750 ty
::TyClosure(_
, ref substs
) => {
1751 // FIXME -- This case is tricky. In the case of by-ref
1752 // closures particularly, we need the results of
1753 // inference to decide how to reflect the type of each
1754 // upvar (the upvar may have type `T`, but the runtime
1755 // type could be `&mut`, `&`, or just `T`). For now,
1756 // though, we'll do this unsoundly and assume that all
1757 // captures are by value. Really what we ought to do
1758 // is reserve judgement and then intertwine this
1759 // analysis with closure inference.
1761 // Unboxed closures shouldn't be
1762 // implicitly copyable
1763 if bound
== ty
::BoundCopy
{
1764 return Ok(ParameterBuiltin
);
1767 // Upvars are always local variables or references to
1768 // local variables, and local variables cannot be
1769 // unsized, so the closure struct as a whole must be
1771 if bound
== ty
::BoundSized
{
1772 return ok_if(Vec
::new());
1775 ok_if(substs
.upvar_tys
.clone())
1778 ty
::TyStruct(def
, substs
) | ty
::TyEnum(def
, substs
) => {
1779 let types
: Vec
<Ty
> = def
.all_fields().map(|f
| {
1780 f
.ty(self.tcx(), substs
)
1782 nominal(bound
, types
)
1785 ty
::TyProjection(_
) | ty
::TyParam(_
) => {
1786 // Note: A type parameter is only considered to meet a
1787 // particular bound if there is a where clause telling
1788 // us that it does, and that case is handled by
1789 // `assemble_candidates_from_caller_bounds()`.
1790 Ok(ParameterBuiltin
)
1793 ty
::TyInfer(ty
::TyVar(_
)) => {
1794 // Unbound type variable. Might or might not have
1795 // applicable impls and so forth, depending on what
1796 // those type variables wind up being bound to.
1797 debug
!("assemble_builtin_bound_candidates: ambiguous builtin");
1798 Ok(AmbiguousBuiltin
)
1801 ty
::TyError
=> ok_if(Vec
::new()),
1803 ty
::TyInfer(ty
::FreshTy(_
))
1804 | ty
::TyInfer(ty
::FreshIntTy(_
))
1805 | ty
::TyInfer(ty
::FreshFloatTy(_
)) => {
1806 self.tcx().sess
.bug(
1808 "asked to assemble builtin bounds of unexpected type: {:?}",
1813 fn ok_if
<'tcx
>(v
: Vec
<Ty
<'tcx
>>)
1814 -> Result
<BuiltinBoundConditions
<'tcx
>, SelectionError
<'tcx
>> {
1815 Ok(If(ty
::Binder(v
)))
1818 fn nominal
<'cx
, 'tcx
>(bound
: ty
::BuiltinBound
,
1819 types
: Vec
<Ty
<'tcx
>>)
1820 -> Result
<BuiltinBoundConditions
<'tcx
>, SelectionError
<'tcx
>>
1822 // First check for markers and other nonsense.
1824 // Fallback to whatever user-defined impls exist in this case.
1825 ty
::BoundCopy
=> Ok(ParameterBuiltin
),
1827 // Sized if all the component types are sized.
1828 ty
::BoundSized
=> ok_if(types
),
1830 // Shouldn't be coming through here.
1831 ty
::BoundSend
| ty
::BoundSync
=> unreachable
!(),
1836 /// For default impls, we need to break apart a type into its
1837 /// "constituent types" -- meaning, the types that it contains.
1839 /// Here are some (simple) examples:
1842 /// (i32, u32) -> [i32, u32]
1843 /// Foo where struct Foo { x: i32, y: u32 } -> [i32, u32]
1844 /// Bar<i32> where struct Bar<T> { x: T, y: u32 } -> [i32, u32]
1845 /// Zed<i32> where enum Zed { A(T), B(u32) } -> [i32, u32]
1847 fn constituent_types_for_ty(&self, t
: Ty
<'tcx
>) -> Vec
<Ty
<'tcx
>> {
1856 ty
::TyInfer(ty
::IntVar(_
)) |
1857 ty
::TyInfer(ty
::FloatVar(_
)) |
1864 ty
::TyProjection(..) |
1865 ty
::TyInfer(ty
::TyVar(_
)) |
1866 ty
::TyInfer(ty
::FreshTy(_
)) |
1867 ty
::TyInfer(ty
::FreshIntTy(_
)) |
1868 ty
::TyInfer(ty
::FreshFloatTy(_
)) => {
1869 self.tcx().sess
.bug(
1871 "asked to assemble constituent types of unexpected type: {:?}",
1875 ty
::TyBox(referent_ty
) => { // Box<T>
1879 ty
::TyRawPtr(ty
::TypeAndMut { ty: element_ty, ..}
) |
1880 ty
::TyRef(_
, ty
::TypeAndMut { ty: element_ty, ..}
) => {
1884 ty
::TyArray(element_ty
, _
) | ty
::TySlice(element_ty
) => {
1888 ty
::TyTuple(ref tys
) => {
1889 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1893 ty
::TyClosure(_
, ref substs
) => {
1894 // FIXME(#27086). We are invariant w/r/t our
1895 // substs.func_substs, but we don't see them as
1896 // constituent types; this seems RIGHT but also like
1897 // something that a normal type couldn't simulate. Is
1898 // this just a gap with the way that PhantomData and
1899 // OIBIT interact? That is, there is no way to say
1900 // "make me invariant with respect to this TYPE, but
1901 // do not act as though I can reach it"
1902 substs
.upvar_tys
.clone()
1905 // for `PhantomData<T>`, we pass `T`
1906 ty
::TyStruct(def
, substs
) if def
.is_phantom_data() => {
1907 substs
.types
.get_slice(TypeSpace
).to_vec()
1910 ty
::TyStruct(def
, substs
) | ty
::TyEnum(def
, substs
) => {
1912 .map(|f
| f
.ty(self.tcx(), substs
))
1918 fn collect_predicates_for_types(&mut self,
1919 obligation
: &TraitObligation
<'tcx
>,
1920 trait_def_id
: DefId
,
1921 types
: ty
::Binder
<Vec
<Ty
<'tcx
>>>)
1922 -> Vec
<PredicateObligation
<'tcx
>>
1924 let derived_cause
= match self.tcx().lang_items
.to_builtin_kind(trait_def_id
) {
1926 self.derived_cause(obligation
, BuiltinDerivedObligation
)
1929 self.derived_cause(obligation
, ImplDerivedObligation
)
1933 // Because the types were potentially derived from
1934 // higher-ranked obligations they may reference late-bound
1935 // regions. For example, `for<'a> Foo<&'a int> : Copy` would
1936 // yield a type like `for<'a> &'a int`. In general, we
1937 // maintain the invariant that we never manipulate bound
1938 // regions, so we have to process these bound regions somehow.
1940 // The strategy is to:
1942 // 1. Instantiate those regions to skolemized regions (e.g.,
1943 // `for<'a> &'a int` becomes `&0 int`.
1944 // 2. Produce something like `&'0 int : Copy`
1945 // 3. Re-bind the regions back to `for<'a> &'a int : Copy`
1947 // Move the binder into the individual types
1948 let bound_types
: Vec
<ty
::Binder
<Ty
<'tcx
>>> =
1951 .map(|&nested_ty
| ty
::Binder(nested_ty
))
1954 // For each type, produce a vector of resulting obligations
1955 let obligations
: Result
<Vec
<Vec
<_
>>, _
> = bound_types
.iter().map(|nested_ty
| {
1956 self.infcx
.commit_if_ok(|snapshot
| {
1957 let (skol_ty
, skol_map
) =
1958 self.infcx().skolemize_late_bound_regions(nested_ty
, snapshot
);
1959 let Normalized { value: normalized_ty, mut obligations }
=
1960 project
::normalize_with_depth(self,
1961 obligation
.cause
.clone(),
1962 obligation
.recursion_depth
+ 1,
1964 let skol_obligation
=
1965 util
::predicate_for_trait_def(self.tcx(),
1966 derived_cause
.clone(),
1968 obligation
.recursion_depth
+ 1,
1971 obligations
.push(skol_obligation
);
1972 Ok(self.infcx().plug_leaks(skol_map
, snapshot
, &obligations
))
1976 // Flatten those vectors (couldn't do it above due `collect`)
1978 Ok(obligations
) => obligations
.into_iter().flat_map(|o
| o
).collect(),
1979 Err(ErrorReported
) => Vec
::new(),
1983 ///////////////////////////////////////////////////////////////////////////
1986 // Confirmation unifies the output type parameters of the trait
1987 // with the values found in the obligation, possibly yielding a
1988 // type error. See `README.md` for more details.
1990 fn confirm_candidate(&mut self,
1991 obligation
: &TraitObligation
<'tcx
>,
1992 candidate
: SelectionCandidate
<'tcx
>)
1993 -> Result
<Selection
<'tcx
>,SelectionError
<'tcx
>>
1995 debug
!("confirm_candidate({:?}, {:?})",
2000 BuiltinCandidate(builtin_bound
) => {
2002 try
!(self.confirm_builtin_candidate(obligation
, builtin_bound
))))
2005 ParamCandidate(param
) => {
2006 let obligations
= self.confirm_param_candidate(obligation
, param
);
2007 Ok(VtableParam(obligations
))
2010 DefaultImplCandidate(trait_def_id
) => {
2011 let data
= self.confirm_default_impl_candidate(obligation
, trait_def_id
);
2012 Ok(VtableDefaultImpl(data
))
2015 DefaultImplObjectCandidate(trait_def_id
) => {
2016 let data
= self.confirm_default_impl_object_candidate(obligation
, trait_def_id
);
2017 Ok(VtableDefaultImpl(data
))
2020 ImplCandidate(impl_def_id
) => {
2022 try
!(self.confirm_impl_candidate(obligation
, impl_def_id
));
2023 Ok(VtableImpl(vtable_impl
))
2026 ClosureCandidate(closure_def_id
, substs
) => {
2027 let vtable_closure
=
2028 try
!(self.confirm_closure_candidate(obligation
, closure_def_id
, substs
));
2029 Ok(VtableClosure(vtable_closure
))
2032 BuiltinObjectCandidate
=> {
2033 // This indicates something like `(Trait+Send) :
2034 // Send`. In this case, we know that this holds
2035 // because that's what the object type is telling us,
2036 // and there's really no additional obligations to
2037 // prove and no types in particular to unify etc.
2038 Ok(VtableParam(Vec
::new()))
2041 ObjectCandidate
=> {
2042 let data
= self.confirm_object_candidate(obligation
);
2043 Ok(VtableObject(data
))
2046 FnPointerCandidate
=> {
2048 try
!(self.confirm_fn_pointer_candidate(obligation
));
2049 Ok(VtableFnPointer(fn_type
))
2052 ProjectionCandidate
=> {
2053 self.confirm_projection_candidate(obligation
);
2054 Ok(VtableParam(Vec
::new()))
2057 BuiltinUnsizeCandidate
=> {
2058 let data
= try
!(self.confirm_builtin_unsize_candidate(obligation
));
2059 Ok(VtableBuiltin(data
))
2064 fn confirm_projection_candidate(&mut self,
2065 obligation
: &TraitObligation
<'tcx
>)
2067 let _
: Result
<(),()> =
2068 self.infcx
.commit_if_ok(|snapshot
| {
2070 self.match_projection_obligation_against_bounds_from_trait(obligation
,
2077 fn confirm_param_candidate(&mut self,
2078 obligation
: &TraitObligation
<'tcx
>,
2079 param
: ty
::PolyTraitRef
<'tcx
>)
2080 -> Vec
<PredicateObligation
<'tcx
>>
2082 debug
!("confirm_param_candidate({:?},{:?})",
2086 // During evaluation, we already checked that this
2087 // where-clause trait-ref could be unified with the obligation
2088 // trait-ref. Repeat that unification now without any
2089 // transactional boundary; it should not fail.
2090 match self.match_where_clause_trait_ref(obligation
, param
.clone()) {
2091 Ok(obligations
) => obligations
,
2093 self.tcx().sess
.bug(
2094 &format
!("Where clause `{:?}` was applicable to `{:?}` but now is not",
2101 fn confirm_builtin_candidate(&mut self,
2102 obligation
: &TraitObligation
<'tcx
>,
2103 bound
: ty
::BuiltinBound
)
2104 -> Result
<VtableBuiltinData
<PredicateObligation
<'tcx
>>,
2105 SelectionError
<'tcx
>>
2107 debug
!("confirm_builtin_candidate({:?})",
2110 match try
!(self.builtin_bound(bound
, obligation
)) {
2111 If(nested
) => Ok(self.vtable_builtin_data(obligation
, bound
, nested
)),
2112 AmbiguousBuiltin
| ParameterBuiltin
=> {
2113 self.tcx().sess
.span_bug(
2114 obligation
.cause
.span
,
2115 &format
!("builtin bound for {:?} was ambig",
2121 fn vtable_builtin_data(&mut self,
2122 obligation
: &TraitObligation
<'tcx
>,
2123 bound
: ty
::BuiltinBound
,
2124 nested
: ty
::Binder
<Vec
<Ty
<'tcx
>>>)
2125 -> VtableBuiltinData
<PredicateObligation
<'tcx
>>
2127 debug
!("vtable_builtin_data(obligation={:?}, bound={:?}, nested={:?})",
2128 obligation
, bound
, nested
);
2130 let trait_def
= match self.tcx().lang_items
.from_builtin_kind(bound
) {
2131 Ok(def_id
) => def_id
,
2133 self.tcx().sess
.bug("builtin trait definition not found");
2137 let obligations
= self.collect_predicates_for_types(obligation
, trait_def
, nested
);
2139 debug
!("vtable_builtin_data: obligations={:?}",
2142 VtableBuiltinData { nested: obligations }
2145 /// This handles the case where a `impl Foo for ..` impl is being used.
2146 /// The idea is that the impl applies to `X : Foo` if the following conditions are met:
2148 /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds
2149 /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds.
2150 fn confirm_default_impl_candidate(&mut self,
2151 obligation
: &TraitObligation
<'tcx
>,
2152 trait_def_id
: DefId
)
2153 -> VtableDefaultImplData
<PredicateObligation
<'tcx
>>
2155 debug
!("confirm_default_impl_candidate({:?}, {:?})",
2159 // binder is moved below
2160 let self_ty
= self.infcx
.shallow_resolve(obligation
.predicate
.skip_binder().self_ty());
2161 let types
= self.constituent_types_for_ty(self_ty
);
2162 self.vtable_default_impl(obligation
, trait_def_id
, ty
::Binder(types
))
2165 fn confirm_default_impl_object_candidate(&mut self,
2166 obligation
: &TraitObligation
<'tcx
>,
2167 trait_def_id
: DefId
)
2168 -> VtableDefaultImplData
<PredicateObligation
<'tcx
>>
2170 debug
!("confirm_default_impl_object_candidate({:?}, {:?})",
2174 assert
!(self.tcx().has_attr(trait_def_id
, "rustc_reflect_like"));
2176 // OK to skip binder, it is reintroduced below
2177 let self_ty
= self.infcx
.shallow_resolve(obligation
.predicate
.skip_binder().self_ty());
2179 ty
::TyTrait(ref data
) => {
2180 // OK to skip the binder, it is reintroduced below
2181 let input_types
= data
.principal
.skip_binder().substs
.types
.get_slice(TypeSpace
);
2182 let assoc_types
= data
.bounds
.projection_bounds
2184 .map(|pb
| pb
.skip_binder().ty
);
2185 let all_types
: Vec
<_
> = input_types
.iter().cloned()
2189 // reintroduce the two binding levels we skipped, then flatten into one
2190 let all_types
= ty
::Binder(ty
::Binder(all_types
));
2191 let all_types
= self.tcx().flatten_late_bound_regions(&all_types
);
2193 self.vtable_default_impl(obligation
, trait_def_id
, all_types
)
2196 self.tcx().sess
.bug(
2198 "asked to confirm default object implementation for non-object type: {:?}",
2204 /// See `confirm_default_impl_candidate`
2205 fn vtable_default_impl(&mut self,
2206 obligation
: &TraitObligation
<'tcx
>,
2207 trait_def_id
: DefId
,
2208 nested
: ty
::Binder
<Vec
<Ty
<'tcx
>>>)
2209 -> VtableDefaultImplData
<PredicateObligation
<'tcx
>>
2211 debug
!("vtable_default_impl_data: nested={:?}", nested
);
2213 let mut obligations
= self.collect_predicates_for_types(obligation
,
2217 let trait_obligations
: Result
<Vec
<_
>,()> = self.infcx
.commit_if_ok(|snapshot
| {
2218 let poly_trait_ref
= obligation
.predicate
.to_poly_trait_ref();
2219 let (trait_ref
, skol_map
) =
2220 self.infcx().skolemize_late_bound_regions(&poly_trait_ref
, snapshot
);
2221 Ok(self.impl_or_trait_obligations(obligation
.cause
.clone(),
2222 obligation
.recursion_depth
+ 1,
2229 // no Errors in that code above
2230 obligations
.append(&mut trait_obligations
.unwrap());
2232 debug
!("vtable_default_impl_data: obligations={:?}", obligations
);
2234 VtableDefaultImplData
{
2235 trait_def_id
: trait_def_id
,
2240 fn confirm_impl_candidate(&mut self,
2241 obligation
: &TraitObligation
<'tcx
>,
2243 -> Result
<VtableImplData
<'tcx
, PredicateObligation
<'tcx
>>,
2244 SelectionError
<'tcx
>>
2246 debug
!("confirm_impl_candidate({:?},{:?})",
2250 // First, create the substitutions by matching the impl again,
2251 // this time not in a probe.
2252 self.infcx
.commit_if_ok(|snapshot
| {
2253 let (substs
, skol_map
) =
2254 self.rematch_impl(impl_def_id
, obligation
,
2256 debug
!("confirm_impl_candidate substs={:?}", substs
);
2257 Ok(self.vtable_impl(impl_def_id
, substs
, obligation
.cause
.clone(),
2258 obligation
.recursion_depth
+ 1, skol_map
, snapshot
))
2262 fn vtable_impl(&mut self,
2264 mut substs
: Normalized
<'tcx
, Substs
<'tcx
>>,
2265 cause
: ObligationCause
<'tcx
>,
2266 recursion_depth
: usize,
2267 skol_map
: infer
::SkolemizationMap
,
2268 snapshot
: &infer
::CombinedSnapshot
)
2269 -> VtableImplData
<'tcx
, PredicateObligation
<'tcx
>>
2271 debug
!("vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={}, skol_map={:?})",
2277 let mut impl_obligations
=
2278 self.impl_or_trait_obligations(cause
,
2285 debug
!("vtable_impl: impl_def_id={:?} impl_obligations={:?}",
2289 // Because of RFC447, the impl-trait-ref and obligations
2290 // are sufficient to determine the impl substs, without
2291 // relying on projections in the impl-trait-ref.
2293 // e.g. `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V`
2294 impl_obligations
.append(&mut substs
.obligations
);
2296 VtableImplData
{ impl_def_id
: impl_def_id
,
2297 substs
: substs
.value
,
2298 nested
: impl_obligations
}
2301 fn confirm_object_candidate(&mut self,
2302 obligation
: &TraitObligation
<'tcx
>)
2303 -> VtableObjectData
<'tcx
>
2305 debug
!("confirm_object_candidate({:?})",
2308 // FIXME skipping binder here seems wrong -- we should
2309 // probably flatten the binder from the obligation and the
2310 // binder from the object. Have to try to make a broken test
2311 // case that results. -nmatsakis
2312 let self_ty
= self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder());
2313 let poly_trait_ref
= match self_ty
.sty
{
2314 ty
::TyTrait(ref data
) => {
2315 data
.principal_trait_ref_with_self_ty(self.tcx(), self_ty
)
2318 self.tcx().sess
.span_bug(obligation
.cause
.span
,
2319 "object candidate with non-object");
2323 let mut upcast_trait_ref
= None
;
2327 // We want to find the first supertrait in the list of
2328 // supertraits that we can unify with, and do that
2329 // unification. We know that there is exactly one in the list
2330 // where we can unify because otherwise select would have
2331 // reported an ambiguity. (When we do find a match, also
2332 // record it for later.)
2334 util
::supertraits(self.tcx(), poly_trait_ref
)
2337 self.infcx
.commit_if_ok(
2338 |_
| self.match_poly_trait_ref(obligation
, t
))
2340 Ok(_
) => { upcast_trait_ref = Some(t); false }
2345 // Additionally, for each of the nonmatching predicates that
2346 // we pass over, we sum up the set of number of vtable
2347 // entries, so that we can compute the offset for the selected
2350 nonmatching
.map(|t
| util
::count_own_vtable_entries(self.tcx(), t
))
2356 upcast_trait_ref
: upcast_trait_ref
.unwrap(),
2357 vtable_base
: vtable_base
,
2361 fn confirm_fn_pointer_candidate(&mut self,
2362 obligation
: &TraitObligation
<'tcx
>)
2363 -> Result
<ty
::Ty
<'tcx
>,SelectionError
<'tcx
>>
2365 debug
!("confirm_fn_pointer_candidate({:?})",
2368 // ok to skip binder; it is reintroduced below
2369 let self_ty
= self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder());
2370 let sig
= self_ty
.fn_sig();
2372 util
::closure_trait_ref_and_return_type(self.tcx(),
2373 obligation
.predicate
.def_id(),
2376 util
::TupleArgumentsFlag
::Yes
)
2377 .map_bound(|(trait_ref
, _
)| trait_ref
);
2379 try
!(self.confirm_poly_trait_refs(obligation
.cause
.clone(),
2380 obligation
.predicate
.to_poly_trait_ref(),
2385 fn confirm_closure_candidate(&mut self,
2386 obligation
: &TraitObligation
<'tcx
>,
2387 closure_def_id
: DefId
,
2388 substs
: &ty
::ClosureSubsts
<'tcx
>)
2389 -> Result
<VtableClosureData
<'tcx
, PredicateObligation
<'tcx
>>,
2390 SelectionError
<'tcx
>>
2392 debug
!("confirm_closure_candidate({:?},{:?},{:?})",
2400 } = self.closure_trait_ref(obligation
, closure_def_id
, substs
);
2402 debug
!("confirm_closure_candidate(closure_def_id={:?}, trait_ref={:?}, obligations={:?})",
2407 try
!(self.confirm_poly_trait_refs(obligation
.cause
.clone(),
2408 obligation
.predicate
.to_poly_trait_ref(),
2411 Ok(VtableClosureData
{
2412 closure_def_id
: closure_def_id
,
2413 substs
: substs
.clone(),
2418 /// In the case of closure types and fn pointers,
2419 /// we currently treat the input type parameters on the trait as
2420 /// outputs. This means that when we have a match we have only
2421 /// considered the self type, so we have to go back and make sure
2422 /// to relate the argument types too. This is kind of wrong, but
2423 /// since we control the full set of impls, also not that wrong,
2424 /// and it DOES yield better error messages (since we don't report
2425 /// errors as if there is no applicable impl, but rather report
2426 /// errors are about mismatched argument types.
2428 /// Here is an example. Imagine we have a closure expression
2429 /// and we desugared it so that the type of the expression is
2430 /// `Closure`, and `Closure` expects an int as argument. Then it
2431 /// is "as if" the compiler generated this impl:
2433 /// impl Fn(int) for Closure { ... }
2435 /// Now imagine our obligation is `Fn(usize) for Closure`. So far
2436 /// we have matched the self-type `Closure`. At this point we'll
2437 /// compare the `int` to `usize` and generate an error.
2439 /// Note that this checking occurs *after* the impl has selected,
2440 /// because these output type parameters should not affect the
2441 /// selection of the impl. Therefore, if there is a mismatch, we
2442 /// report an error to the user.
2443 fn confirm_poly_trait_refs(&mut self,
2444 obligation_cause
: ObligationCause
,
2445 obligation_trait_ref
: ty
::PolyTraitRef
<'tcx
>,
2446 expected_trait_ref
: ty
::PolyTraitRef
<'tcx
>)
2447 -> Result
<(), SelectionError
<'tcx
>>
2449 let origin
= TypeOrigin
::RelateOutputImplTypes(obligation_cause
.span
);
2451 let obligation_trait_ref
= obligation_trait_ref
.clone();
2452 match self.infcx
.sub_poly_trait_refs(false,
2454 expected_trait_ref
.clone(),
2455 obligation_trait_ref
.clone()) {
2457 Err(e
) => Err(OutputTypeParameterMismatch(expected_trait_ref
, obligation_trait_ref
, e
))
2461 fn confirm_builtin_unsize_candidate(&mut self,
2462 obligation
: &TraitObligation
<'tcx
>,)
2463 -> Result
<VtableBuiltinData
<PredicateObligation
<'tcx
>>,
2464 SelectionError
<'tcx
>> {
2465 let tcx
= self.tcx();
2467 // assemble_candidates_for_unsizing should ensure there are no late bound
2468 // regions here. See the comment there for more details.
2469 let source
= self.infcx
.shallow_resolve(
2470 tcx
.no_late_bound_regions(&obligation
.self_ty()).unwrap());
2471 let target
= self.infcx
.shallow_resolve(obligation
.predicate
.0.input_types
()[0]);
2473 debug
!("confirm_builtin_unsize_candidate(source={:?}, target={:?})",
2476 let mut nested
= vec
![];
2477 match (&source
.sty
, &target
.sty
) {
2478 // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
2479 (&ty
::TyTrait(ref data_a
), &ty
::TyTrait(ref data_b
)) => {
2480 // See assemble_candidates_for_unsizing for more info.
2481 let bounds
= ty
::ExistentialBounds
{
2482 region_bound
: data_b
.bounds
.region_bound
,
2483 builtin_bounds
: data_b
.bounds
.builtin_bounds
,
2484 projection_bounds
: data_a
.bounds
.projection_bounds
.clone(),
2487 let new_trait
= tcx
.mk_trait(data_a
.principal
.clone(), bounds
);
2488 let origin
= TypeOrigin
::Misc(obligation
.cause
.span
);
2489 if self.infcx
.sub_types(false, origin
, new_trait
, target
).is_err() {
2490 return Err(Unimplemented
);
2493 // Register one obligation for 'a: 'b.
2494 let cause
= ObligationCause
::new(obligation
.cause
.span
,
2495 obligation
.cause
.body_id
,
2496 ObjectCastObligation(target
));
2497 let outlives
= ty
::OutlivesPredicate(data_a
.bounds
.region_bound
,
2498 data_b
.bounds
.region_bound
);
2499 nested
.push(Obligation
::with_depth(cause
,
2500 obligation
.recursion_depth
+ 1,
2501 ty
::Binder(outlives
).to_predicate()));
2505 (_
, &ty
::TyTrait(ref data
)) => {
2506 let object_did
= data
.principal_def_id();
2507 if !object_safety
::is_object_safe(tcx
, object_did
) {
2508 return Err(TraitNotObjectSafe(object_did
));
2511 let cause
= ObligationCause
::new(obligation
.cause
.span
,
2512 obligation
.cause
.body_id
,
2513 ObjectCastObligation(target
));
2514 let mut push
= |predicate
| {
2515 nested
.push(Obligation
::with_depth(cause
.clone(),
2516 obligation
.recursion_depth
+ 1,
2520 // Create the obligation for casting from T to Trait.
2521 push(data
.principal_trait_ref_with_self_ty(tcx
, source
).to_predicate());
2523 // We can only make objects from sized types.
2524 let mut builtin_bounds
= data
.bounds
.builtin_bounds
;
2525 builtin_bounds
.insert(ty
::BoundSized
);
2527 // Create additional obligations for all the various builtin
2528 // bounds attached to the object cast. (In other words, if the
2529 // object type is Foo+Send, this would create an obligation
2530 // for the Send check.)
2531 for bound
in &builtin_bounds
{
2532 if let Ok(tr
) = util
::trait_ref_for_builtin_bound(tcx
, bound
, source
) {
2533 push(tr
.to_predicate());
2535 return Err(Unimplemented
);
2539 // Create obligations for the projection predicates.
2540 for bound
in data
.projection_bounds_with_self_ty(tcx
, source
) {
2541 push(bound
.to_predicate());
2544 // If the type is `Foo+'a`, ensures that the type
2545 // being cast to `Foo+'a` outlives `'a`:
2546 let outlives
= ty
::OutlivesPredicate(source
,
2547 data
.bounds
.region_bound
);
2548 push(ty
::Binder(outlives
).to_predicate());
2552 (&ty
::TyArray(a
, _
), &ty
::TySlice(b
)) => {
2553 let origin
= TypeOrigin
::Misc(obligation
.cause
.span
);
2554 if self.infcx
.sub_types(false, origin
, a
, b
).is_err() {
2555 return Err(Unimplemented
);
2559 // Struct<T> -> Struct<U>.
2560 (&ty
::TyStruct(def
, substs_a
), &ty
::TyStruct(_
, substs_b
)) => {
2563 .map(|f
| f
.unsubst_ty())
2564 .collect
::<Vec
<_
>>();
2566 // The last field of the structure has to exist and contain type parameters.
2567 let field
= if let Some(&field
) = fields
.last() {
2570 return Err(Unimplemented
);
2572 let mut ty_params
= vec
![];
2573 for ty
in field
.walk() {
2574 if let ty
::TyParam(p
) = ty
.sty
{
2575 assert
!(p
.space
== TypeSpace
);
2576 let idx
= p
.idx
as usize;
2577 if !ty_params
.contains(&idx
) {
2578 ty_params
.push(idx
);
2582 if ty_params
.is_empty() {
2583 return Err(Unimplemented
);
2586 // Replace type parameters used in unsizing with
2587 // TyError and ensure they do not affect any other fields.
2588 // This could be checked after type collection for any struct
2589 // with a potentially unsized trailing field.
2590 let mut new_substs
= substs_a
.clone();
2591 for &i
in &ty_params
{
2592 new_substs
.types
.get_mut_slice(TypeSpace
)[i
] = tcx
.types
.err
;
2594 for &ty
in fields
.split_last().unwrap().1 {
2595 if ty
.subst(tcx
, &new_substs
).references_error() {
2596 return Err(Unimplemented
);
2600 // Extract Field<T> and Field<U> from Struct<T> and Struct<U>.
2601 let inner_source
= field
.subst(tcx
, substs_a
);
2602 let inner_target
= field
.subst(tcx
, substs_b
);
2604 // Check that the source structure with the target's
2605 // type parameters is a subtype of the target.
2606 for &i
in &ty_params
{
2607 let param_b
= *substs_b
.types
.get(TypeSpace
, i
);
2608 new_substs
.types
.get_mut_slice(TypeSpace
)[i
] = param_b
;
2610 let new_struct
= tcx
.mk_struct(def
, tcx
.mk_substs(new_substs
));
2611 let origin
= TypeOrigin
::Misc(obligation
.cause
.span
);
2612 if self.infcx
.sub_types(false, origin
, new_struct
, target
).is_err() {
2613 return Err(Unimplemented
);
2616 // Construct the nested Field<T>: Unsize<Field<U>> predicate.
2617 nested
.push(util
::predicate_for_trait_def(tcx
,
2618 obligation
.cause
.clone(),
2619 obligation
.predicate
.def_id(),
2620 obligation
.recursion_depth
+ 1,
2622 vec
![inner_target
]));
2628 Ok(VtableBuiltinData { nested: nested }
)
2631 ///////////////////////////////////////////////////////////////////////////
2634 // Matching is a common path used for both evaluation and
2635 // confirmation. It basically unifies types that appear in impls
2636 // and traits. This does affect the surrounding environment;
2637 // therefore, when used during evaluation, match routines must be
2638 // run inside of a `probe()` so that their side-effects are
2641 fn rematch_impl(&mut self,
2643 obligation
: &TraitObligation
<'tcx
>,
2644 snapshot
: &infer
::CombinedSnapshot
)
2645 -> (Normalized
<'tcx
, Substs
<'tcx
>>, infer
::SkolemizationMap
)
2647 match self.match_impl(impl_def_id
, obligation
, snapshot
) {
2648 Ok((substs
, skol_map
)) => (substs
, skol_map
),
2650 self.tcx().sess
.bug(
2651 &format
!("Impl {:?} was matchable against {:?} but now is not",
2658 fn match_impl(&mut self,
2660 obligation
: &TraitObligation
<'tcx
>,
2661 snapshot
: &infer
::CombinedSnapshot
)
2662 -> Result
<(Normalized
<'tcx
, Substs
<'tcx
>>,
2663 infer
::SkolemizationMap
), ()>
2665 let impl_trait_ref
= self.tcx().impl_trait_ref(impl_def_id
).unwrap();
2667 // Before we create the substitutions and everything, first
2668 // consider a "quick reject". This avoids creating more types
2669 // and so forth that we need to.
2670 if self.fast_reject_trait_refs(obligation
, &impl_trait_ref
) {
2674 let (skol_obligation
, skol_map
) = self.infcx().skolemize_late_bound_regions(
2675 &obligation
.predicate
,
2677 let skol_obligation_trait_ref
= skol_obligation
.trait_ref
;
2679 let impl_substs
= util
::fresh_type_vars_for_impl(self.infcx
,
2680 obligation
.cause
.span
,
2683 let impl_trait_ref
= impl_trait_ref
.subst(self.tcx(),
2686 let impl_trait_ref
=
2687 project
::normalize_with_depth(self,
2688 obligation
.cause
.clone(),
2689 obligation
.recursion_depth
+ 1,
2692 debug
!("match_impl(impl_def_id={:?}, obligation={:?}, \
2693 impl_trait_ref={:?}, skol_obligation_trait_ref={:?})",
2697 skol_obligation_trait_ref
);
2699 let origin
= TypeOrigin
::RelateOutputImplTypes(obligation
.cause
.span
);
2700 if let Err(e
) = self.infcx
.eq_trait_refs(false,
2702 impl_trait_ref
.value
.clone(),
2703 skol_obligation_trait_ref
) {
2704 debug
!("match_impl: failed eq_trait_refs due to `{}`", e
);
2708 if let Err(e
) = self.infcx
.leak_check(&skol_map
, snapshot
) {
2709 debug
!("match_impl: failed leak check due to `{}`", e
);
2713 debug
!("match_impl: success impl_substs={:?}", impl_substs
);
2716 obligations
: impl_trait_ref
.obligations
2720 fn fast_reject_trait_refs(&mut self,
2721 obligation
: &TraitObligation
,
2722 impl_trait_ref
: &ty
::TraitRef
)
2725 // We can avoid creating type variables and doing the full
2726 // substitution if we find that any of the input types, when
2727 // simplified, do not match.
2729 obligation
.predicate
.0.input_types
().iter()
2730 .zip(impl_trait_ref
.input_types())
2731 .any(|(&obligation_ty
, &impl_ty
)| {
2732 let simplified_obligation_ty
=
2733 fast_reject
::simplify_type(self.tcx(), obligation_ty
, true);
2734 let simplified_impl_ty
=
2735 fast_reject
::simplify_type(self.tcx(), impl_ty
, false);
2737 simplified_obligation_ty
.is_some() &&
2738 simplified_impl_ty
.is_some() &&
2739 simplified_obligation_ty
!= simplified_impl_ty
2743 /// Normalize `where_clause_trait_ref` and try to match it against
2744 /// `obligation`. If successful, return any predicates that
2745 /// result from the normalization. Normalization is necessary
2746 /// because where-clauses are stored in the parameter environment
2748 fn match_where_clause_trait_ref(&mut self,
2749 obligation
: &TraitObligation
<'tcx
>,
2750 where_clause_trait_ref
: ty
::PolyTraitRef
<'tcx
>)
2751 -> Result
<Vec
<PredicateObligation
<'tcx
>>,()>
2753 try
!(self.match_poly_trait_ref(obligation
, where_clause_trait_ref
));
2757 /// Returns `Ok` if `poly_trait_ref` being true implies that the
2758 /// obligation is satisfied.
2759 fn match_poly_trait_ref(&self,
2760 obligation
: &TraitObligation
<'tcx
>,
2761 poly_trait_ref
: ty
::PolyTraitRef
<'tcx
>)
2764 debug
!("match_poly_trait_ref: obligation={:?} poly_trait_ref={:?}",
2768 let origin
= TypeOrigin
::RelateOutputImplTypes(obligation
.cause
.span
);
2769 match self.infcx
.sub_poly_trait_refs(false,
2772 obligation
.predicate
.to_poly_trait_ref()) {
2778 ///////////////////////////////////////////////////////////////////////////
2781 fn match_fresh_trait_refs(&self,
2782 previous
: &ty
::PolyTraitRef
<'tcx
>,
2783 current
: &ty
::PolyTraitRef
<'tcx
>)
2786 let mut matcher
= ty
::_match
::Match
::new(self.tcx());
2787 matcher
.relate(previous
, current
).is_ok()
2790 fn push_stack
<'o
,'s
:'o
>(&mut self,
2791 previous_stack
: TraitObligationStackList
<'s
, 'tcx
>,
2792 obligation
: &'o TraitObligation
<'tcx
>)
2793 -> TraitObligationStack
<'o
, 'tcx
>
2795 let fresh_trait_ref
=
2796 obligation
.predicate
.to_poly_trait_ref().fold_with(&mut self.freshener
);
2798 TraitObligationStack
{
2799 obligation
: obligation
,
2800 fresh_trait_ref
: fresh_trait_ref
,
2801 previous
: previous_stack
,
2805 fn closure_trait_ref_unnormalized(&mut self,
2806 obligation
: &TraitObligation
<'tcx
>,
2807 closure_def_id
: DefId
,
2808 substs
: &ty
::ClosureSubsts
<'tcx
>)
2809 -> ty
::PolyTraitRef
<'tcx
>
2811 let closure_type
= self.infcx
.closure_type(closure_def_id
, substs
);
2812 let ty
::Binder((trait_ref
, _
)) =
2813 util
::closure_trait_ref_and_return_type(self.tcx(),
2814 obligation
.predicate
.def_id(),
2815 obligation
.predicate
.0.self_ty(), // (1)
2817 util
::TupleArgumentsFlag
::No
);
2818 // (1) Feels icky to skip the binder here, but OTOH we know
2819 // that the self-type is an unboxed closure type and hence is
2820 // in fact unparameterized (or at least does not reference any
2821 // regions bound in the obligation). Still probably some
2822 // refactoring could make this nicer.
2824 ty
::Binder(trait_ref
)
2827 fn closure_trait_ref(&mut self,
2828 obligation
: &TraitObligation
<'tcx
>,
2829 closure_def_id
: DefId
,
2830 substs
: &ty
::ClosureSubsts
<'tcx
>)
2831 -> Normalized
<'tcx
, ty
::PolyTraitRef
<'tcx
>>
2833 let trait_ref
= self.closure_trait_ref_unnormalized(
2834 obligation
, closure_def_id
, substs
);
2836 // A closure signature can contain associated types which
2837 // must be normalized.
2838 normalize_with_depth(self,
2839 obligation
.cause
.clone(),
2840 obligation
.recursion_depth
+1,
2844 /// Returns the obligations that are implied by instantiating an
2845 /// impl or trait. The obligations are substituted and fully
2846 /// normalized. This is used when confirming an impl or default
2848 fn impl_or_trait_obligations(&mut self,
2849 cause
: ObligationCause
<'tcx
>,
2850 recursion_depth
: usize,
2851 def_id
: DefId
, // of impl or trait
2852 substs
: &Substs
<'tcx
>, // for impl or trait
2853 skol_map
: infer
::SkolemizationMap
,
2854 snapshot
: &infer
::CombinedSnapshot
)
2855 -> Vec
<PredicateObligation
<'tcx
>>
2857 debug
!("impl_or_trait_obligations(def_id={:?})", def_id
);
2858 let tcx
= self.tcx();
2860 // To allow for one-pass evaluation of the nested obligation,
2861 // each predicate must be preceded by the obligations required
2863 // for example, if we have:
2864 // impl<U: Iterator, V: Iterator<Item=U>> Foo for V where U::Item: Copy
2865 // the impl will have the following predicates:
2866 // <V as Iterator>::Item = U,
2867 // U: Iterator, U: Sized,
2868 // V: Iterator, V: Sized,
2869 // <U as Iterator>::Item: Copy
2870 // When we substitute, say, `V => IntoIter<u32>, U => $0`, the last
2871 // obligation will normalize to `<$0 as Iterator>::Item = $1` and
2872 // `$1: Copy`, so we must ensure the obligations are emitted in
2874 let predicates
= tcx
2875 .lookup_predicates(def_id
)
2877 .flat_map(|predicate
| {
2879 normalize_with_depth(self, cause
.clone(), recursion_depth
,
2880 &predicate
.subst(tcx
, substs
));
2881 predicate
.obligations
.into_iter().chain(
2883 cause
: cause
.clone(),
2884 recursion_depth
: recursion_depth
,
2885 predicate
: predicate
.value
2888 self.infcx().plug_leaks(skol_map
, snapshot
, &predicates
)
2891 #[allow(unused_comparisons)]
2892 fn derived_cause(&self,
2893 obligation
: &TraitObligation
<'tcx
>,
2894 variant
: fn(DerivedObligationCause
<'tcx
>) -> ObligationCauseCode
<'tcx
>)
2895 -> ObligationCause
<'tcx
>
2898 * Creates a cause for obligations that are derived from
2899 * `obligation` by a recursive search (e.g., for a builtin
2900 * bound, or eventually a `impl Foo for ..`). If `obligation`
2901 * is itself a derived obligation, this is just a clone, but
2902 * otherwise we create a "derived obligation" cause so as to
2903 * keep track of the original root obligation for error
2907 // NOTE(flaper87): As of now, it keeps track of the whole error
2908 // chain. Ideally, we should have a way to configure this either
2909 // by using -Z verbose or just a CLI argument.
2910 if obligation
.recursion_depth
>= 0 {
2911 let derived_cause
= DerivedObligationCause
{
2912 parent_trait_ref
: obligation
.predicate
.to_poly_trait_ref(),
2913 parent_code
: Rc
::new(obligation
.cause
.code
.clone())
2915 let derived_code
= variant(derived_cause
);
2916 ObligationCause
::new(obligation
.cause
.span
, obligation
.cause
.body_id
, derived_code
)
2918 obligation
.cause
.clone()
2923 impl<'tcx
> SelectionCache
<'tcx
> {
2924 pub fn new() -> SelectionCache
<'tcx
> {
2926 hashmap
: RefCell
::new(FnvHashMap())
2931 impl<'tcx
> EvaluationCache
<'tcx
> {
2932 pub fn new() -> EvaluationCache
<'tcx
> {
2934 hashmap
: RefCell
::new(FnvHashMap())
2939 impl<'o
,'tcx
> TraitObligationStack
<'o
,'tcx
> {
2940 fn list(&'o
self) -> TraitObligationStackList
<'o
,'tcx
> {
2941 TraitObligationStackList
::with(self)
2944 fn iter(&'o
self) -> TraitObligationStackList
<'o
,'tcx
> {
2949 #[derive(Copy, Clone)]
2950 struct TraitObligationStackList
<'o
,'tcx
:'o
> {
2951 head
: Option
<&'o TraitObligationStack
<'o
,'tcx
>>
2954 impl<'o
,'tcx
> TraitObligationStackList
<'o
,'tcx
> {
2955 fn empty() -> TraitObligationStackList
<'o
,'tcx
> {
2956 TraitObligationStackList { head: None }
2959 fn with(r
: &'o TraitObligationStack
<'o
,'tcx
>) -> TraitObligationStackList
<'o
,'tcx
> {
2960 TraitObligationStackList { head: Some(r) }
2964 impl<'o
,'tcx
> Iterator
for TraitObligationStackList
<'o
,'tcx
>{
2965 type Item
= &'o TraitObligationStack
<'o
,'tcx
>;
2967 fn next(&mut self) -> Option
<&'o TraitObligationStack
<'o
,'tcx
>> {
2978 impl<'o
,'tcx
> fmt
::Debug
for TraitObligationStack
<'o
,'tcx
> {
2979 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
2980 write
!(f
, "TraitObligationStack({:?})", self.obligation
)
2984 impl EvaluationResult
{
2985 fn may_apply(&self) -> bool
{
2989 EvaluatedToUnknown
=> true,
2991 EvaluatedToErr
=> false
2996 impl MethodMatchResult
{
2997 pub fn may_apply(&self) -> bool
{
2999 MethodMatched(_
) => true,
3000 MethodAmbiguous(_
) => true,
3001 MethodDidNotMatch
=> false,