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
12 #![allow(dead_code)] // FIXME -- just temporarily
14 pub use self::MethodMatchResult
::*;
15 pub use self::MethodMatchedData
::*;
16 use self::SelectionCandidate
::*;
17 use self::BuiltinBoundConditions
::*;
18 use self::EvaluationResult
::*;
21 use super::DerivedObligationCause
;
23 use super::project
::{normalize_with_depth, Normalized}
;
24 use super::{PredicateObligation, TraitObligation, ObligationCause}
;
25 use super::report_overflow_error
;
26 use super::{ObligationCauseCode, BuiltinDerivedObligation, ImplDerivedObligation}
;
27 use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch}
;
28 use super::{ObjectCastObligation, Obligation}
;
29 use super::TraitNotObjectSafe
;
31 use super::SelectionResult
;
32 use super::{VtableBuiltin
, VtableImpl
, VtableParam
, VtableClosure
,
33 VtableFnPointer
, VtableObject
, VtableDefaultImpl
};
34 use super::{VtableImplData
, VtableObjectData
, VtableBuiltinData
,
35 VtableClosureData
, VtableDefaultImplData
};
36 use super::object_safety
;
39 use middle
::fast_reject
;
40 use middle
::subst
::{Subst, Substs, TypeSpace}
;
41 use middle
::ty
::{self, ToPredicate, RegionEscape, ToPolyTraitRef, Ty, HasTypeFlags}
;
43 use middle
::infer
::{InferCtxt, TypeFreshener}
;
44 use middle
::ty_fold
::TypeFoldable
;
46 use middle
::ty_relate
::TypeRelation
;
48 use std
::cell
::RefCell
;
51 use syntax
::{abi, ast}
;
52 use util
::common
::ErrorReported
;
53 use util
::nodemap
::FnvHashMap
;
55 pub struct SelectionContext
<'cx
, 'tcx
:'cx
> {
56 infcx
: &'cx InferCtxt
<'cx
, 'tcx
>,
58 /// Freshener used specifically for skolemizing entries on the
59 /// obligation stack. This ensures that all entries on the stack
60 /// at one time will have the same set of skolemized entries,
61 /// which is important for checking for trait bounds that
62 /// recursively require themselves.
63 freshener
: TypeFreshener
<'cx
, 'tcx
>,
65 /// If true, indicates that the evaluation should be conservative
66 /// and consider the possibility of types outside this crate.
67 /// This comes up primarily when resolving ambiguity. Imagine
68 /// there is some trait reference `$0 : Bar` where `$0` is an
69 /// inference variable. If `intercrate` is true, then we can never
70 /// say for sure that this reference is not implemented, even if
71 /// there are *no impls at all for `Bar`*, because `$0` could be
72 /// bound to some type that in a downstream crate that implements
73 /// `Bar`. This is the suitable mode for coherence. Elsewhere,
74 /// though, we set this to false, because we are only interested
75 /// in types that the user could actually have written --- in
76 /// other words, we consider `$0 : Bar` to be unimplemented if
77 /// there is no type that the user could *actually name* that
78 /// would satisfy it. This avoids crippling inference, basically.
83 // A stack that walks back up the stack frame.
84 struct TraitObligationStack
<'prev
, 'tcx
: 'prev
> {
85 obligation
: &'prev TraitObligation
<'tcx
>,
87 /// Trait ref from `obligation` but skolemized with the
88 /// selection-context's freshener. Used to check for recursion.
89 fresh_trait_ref
: ty
::PolyTraitRef
<'tcx
>,
91 previous
: TraitObligationStackList
<'prev
, 'tcx
>,
95 pub struct SelectionCache
<'tcx
> {
96 hashmap
: RefCell
<FnvHashMap
<ty
::TraitRef
<'tcx
>,
97 SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>>>,
100 pub enum MethodMatchResult
{
101 MethodMatched(MethodMatchedData
),
102 MethodAmbiguous(/* list of impls that could apply */ Vec
<ast
::DefId
>),
106 #[derive(Copy, Clone, Debug)]
107 pub enum MethodMatchedData
{
108 // In the case of a precise match, we don't really need to store
109 // how the match was found. So don't.
112 // In the case of a coercion, we need to know the precise impl so
113 // that we can determine the type to which things were coerced.
114 CoerciveMethodMatch(/* impl we matched */ ast
::DefId
)
117 /// The selection process begins by considering all impls, where
118 /// clauses, and so forth that might resolve an obligation. Sometimes
119 /// we'll be able to say definitively that (e.g.) an impl does not
120 /// apply to the obligation: perhaps it is defined for `usize` but the
121 /// obligation is for `int`. In that case, we drop the impl out of the
122 /// list. But the other cases are considered *candidates*.
124 /// For selection to succeed, there must be exactly one matching
125 /// candidate. If the obligation is fully known, this is guaranteed
126 /// by coherence. However, if the obligation contains type parameters
127 /// or variables, there may be multiple such impls.
129 /// It is not a real problem if multiple matching impls exist because
130 /// of type variables - it just means the obligation isn't sufficiently
131 /// elaborated. In that case we report an ambiguity, and the caller can
132 /// try again after more type information has been gathered or report a
133 /// "type annotations required" error.
135 /// However, with type parameters, this can be a real problem - type
136 /// parameters don't unify with regular types, but they *can* unify
137 /// with variables from blanket impls, and (unless we know its bounds
138 /// will always be satisfied) picking the blanket impl will be wrong
139 /// for at least *some* substitutions. To make this concrete, if we have
141 /// trait AsDebug { type Out : fmt::Debug; fn debug(self) -> Self::Out; }
142 /// impl<T: fmt::Debug> AsDebug for T {
144 /// fn debug(self) -> fmt::Debug { self }
146 /// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); }
148 /// we can't just use the impl to resolve the <T as AsDebug> obligation
149 /// - a type from another crate (that doesn't implement fmt::Debug) could
150 /// implement AsDebug.
152 /// Because where-clauses match the type exactly, multiple clauses can
153 /// only match if there are unresolved variables, and we can mostly just
154 /// report this ambiguity in that case. This is still a problem - we can't
155 /// *do anything* with ambiguities that involve only regions. This is issue
158 /// If a single where-clause matches and there are no inference
159 /// variables left, then it definitely matches and we can just select
162 /// In fact, we even select the where-clause when the obligation contains
163 /// inference variables. The can lead to inference making "leaps of logic",
164 /// for example in this situation:
166 /// pub trait Foo<T> { fn foo(&self) -> T; }
167 /// impl<T> Foo<()> for T { fn foo(&self) { } }
168 /// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } }
170 /// pub fn foo<T>(t: T) where T: Foo<bool> {
171 /// println!("{:?}", <T as Foo<_>>::foo(&t));
173 /// fn main() { foo(false); }
175 /// Here the obligation <T as Foo<$0>> can be matched by both the blanket
176 /// impl and the where-clause. We select the where-clause and unify $0=bool,
177 /// so the program prints "false". However, if the where-clause is omitted,
178 /// the blanket impl is selected, we unify $0=(), and the program prints
181 /// Exactly the same issues apply to projection and object candidates, except
182 /// that we can have both a projection candidate and a where-clause candidate
183 /// for the same obligation. In that case either would do (except that
184 /// different "leaps of logic" would occur if inference variables are
185 /// present), and we just pick the projection. This is, for example,
186 /// required for associated types to work in default impls, as the bounds
187 /// are visible both as projection bounds and as where-clauses from the
188 /// parameter environment.
189 #[derive(PartialEq,Eq,Debug,Clone)]
190 enum SelectionCandidate
<'tcx
> {
192 BuiltinCandidate(ty
::BuiltinBound
),
193 ParamCandidate(ty
::PolyTraitRef
<'tcx
>),
194 ImplCandidate(ast
::DefId
),
195 DefaultImplCandidate(ast
::DefId
),
196 DefaultImplObjectCandidate(ast
::DefId
),
198 /// This is a trait matching with a projected type as `Self`, and
199 /// we found an applicable bound in the trait definition.
202 /// Implementation of a `Fn`-family trait by one of the
203 /// anonymous types generated for a `||` expression.
204 ClosureCandidate(/* closure */ ast
::DefId
, &'tcx ty
::ClosureSubsts
<'tcx
>),
206 /// Implementation of a `Fn`-family trait by one of the anonymous
207 /// types generated for a fn pointer type (e.g., `fn(int)->int`)
212 BuiltinObjectCandidate
,
214 BuiltinUnsizeCandidate
,
219 struct SelectionCandidateSet
<'tcx
> {
220 // a list of candidates that definitely apply to the current
221 // obligation (meaning: types unify).
222 vec
: Vec
<SelectionCandidate
<'tcx
>>,
224 // if this is true, then there were candidates that might or might
225 // not have applied, but we couldn't tell. This occurs when some
226 // of the input types are type variables, in which case there are
227 // various "builtin" rules that might or might not trigger.
231 enum BuiltinBoundConditions
<'tcx
> {
232 If(ty
::Binder
<Vec
<Ty
<'tcx
>>>),
238 enum EvaluationResult
<'tcx
> {
241 EvaluatedToErr(SelectionError
<'tcx
>),
244 impl<'cx
, 'tcx
> SelectionContext
<'cx
, 'tcx
> {
245 pub fn new(infcx
: &'cx InferCtxt
<'cx
, 'tcx
>)
246 -> SelectionContext
<'cx
, 'tcx
> {
249 freshener
: infcx
.freshener(),
254 pub fn intercrate(infcx
: &'cx InferCtxt
<'cx
, 'tcx
>)
255 -> SelectionContext
<'cx
, 'tcx
> {
258 freshener
: infcx
.freshener(),
263 pub fn infcx(&self) -> &'cx InferCtxt
<'cx
, 'tcx
> {
267 pub fn tcx(&self) -> &'cx ty
::ctxt
<'tcx
> {
271 pub fn param_env(&self) -> &'cx ty
::ParameterEnvironment
<'cx
, 'tcx
> {
272 self.infcx
.param_env()
275 pub fn closure_typer(&self) -> &'cx InferCtxt
<'cx
, 'tcx
> {
279 ///////////////////////////////////////////////////////////////////////////
282 // The selection phase tries to identify *how* an obligation will
283 // be resolved. For example, it will identify which impl or
284 // parameter bound is to be used. The process can be inconclusive
285 // if the self type in the obligation is not fully inferred. Selection
286 // can result in an error in one of two ways:
288 // 1. If no applicable impl or parameter bound can be found.
289 // 2. If the output type parameters in the obligation do not match
290 // those specified by the impl/bound. For example, if the obligation
291 // is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
292 // `impl<T> Iterable<T> for Vec<T>`, than an error would result.
294 /// Attempts to satisfy the obligation. If successful, this will affect the surrounding
295 /// type environment by performing unification.
296 pub fn select(&mut self, obligation
: &TraitObligation
<'tcx
>)
297 -> SelectionResult
<'tcx
, Selection
<'tcx
>> {
298 debug
!("select({:?})", obligation
);
299 assert
!(!obligation
.predicate
.has_escaping_regions());
301 let stack
= self.push_stack(TraitObligationStackList
::empty(), obligation
);
302 match try
!(self.candidate_from_obligation(&stack
)) {
304 self.consider_unification_despite_ambiguity(obligation
);
307 Some(candidate
) => Ok(Some(try
!(self.confirm_candidate(obligation
, candidate
)))),
311 /// In the particular case of unboxed closure obligations, we can
312 /// sometimes do some amount of unification for the
313 /// argument/return types even though we can't yet fully match obligation.
314 /// The particular case we are interesting in is an obligation of the form:
318 /// where `C` is an unboxed closure type and `FnFoo` is one of the
319 /// `Fn` traits. Because we know that users cannot write impls for closure types
320 /// themselves, the only way that `C : FnFoo` can fail to match is under two
323 /// 1. The closure kind for `C` is not yet known, because inference isn't complete.
324 /// 2. The closure kind for `C` *is* known, but doesn't match what is needed.
325 /// For example, `C` may be a `FnOnce` closure, but a `Fn` closure is needed.
327 /// In either case, we always know what argument types are
328 /// expected by `C`, no matter what kind of `Fn` trait it
329 /// eventually matches. So we can go ahead and unify the argument
330 /// types, even though the end result is ambiguous.
332 /// Note that this is safe *even if* the trait would never be
333 /// matched (case 2 above). After all, in that case, an error will
334 /// result, so it kind of doesn't matter what we do --- unifying
335 /// the argument types can only be helpful to the user, because
336 /// once they patch up the kind of closure that is expected, the
337 /// argment types won't really change.
338 fn consider_unification_despite_ambiguity(&mut self, obligation
: &TraitObligation
<'tcx
>) {
339 // Is this a `C : FnFoo(...)` trait reference for some trait binding `FnFoo`?
340 match self.tcx().lang_items
.fn_trait_kind(obligation
.predicate
.0.def_id()) {
345 // Is the self-type a closure type? We ignore bindings here
346 // because if it is a closure type, it must be a closure type from
347 // within this current fn, and hence none of the higher-ranked
348 // lifetimes can appear inside the self-type.
349 let self_ty
= self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder());
350 let (closure_def_id
, substs
) = match self_ty
.sty
{
351 ty
::TyClosure(id
, ref substs
) => (id
, substs
),
354 assert
!(!substs
.has_escaping_regions());
356 // It is OK to call the unnormalized variant here - this is only
357 // reached for TyClosure: Fn inputs where the closure kind is
358 // still unknown, which should only occur in typeck where the
359 // closure type is already normalized.
360 let closure_trait_ref
= self.closure_trait_ref_unnormalized(obligation
,
364 match self.confirm_poly_trait_refs(obligation
.cause
.clone(),
365 obligation
.predicate
.to_poly_trait_ref(),
368 Err(_
) => { /* Silently ignore errors. */ }
372 ///////////////////////////////////////////////////////////////////////////
375 // Tests whether an obligation can be selected or whether an impl
376 // can be applied to particular types. It skips the "confirmation"
377 // step and hence completely ignores output type parameters.
379 // The result is "true" if the obligation *may* hold and "false" if
380 // we can be sure it does not.
382 /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
383 pub fn evaluate_obligation(&mut self,
384 obligation
: &PredicateObligation
<'tcx
>)
387 debug
!("evaluate_obligation({:?})",
390 self.evaluate_predicate_recursively(TraitObligationStackList
::empty(), obligation
)
394 fn evaluate_builtin_bound_recursively
<'o
>(&mut self,
395 bound
: ty
::BuiltinBound
,
396 previous_stack
: &TraitObligationStack
<'o
, 'tcx
>,
398 -> EvaluationResult
<'tcx
>
401 util
::predicate_for_builtin_bound(
403 previous_stack
.obligation
.cause
.clone(),
405 previous_stack
.obligation
.recursion_depth
+ 1,
410 self.evaluate_predicate_recursively(previous_stack
.list(), &obligation
)
412 Err(ErrorReported
) => {
418 fn evaluate_predicates_recursively
<'a
,'o
,I
>(&mut self,
419 stack
: TraitObligationStackList
<'o
, 'tcx
>,
421 -> EvaluationResult
<'tcx
>
422 where I
: Iterator
<Item
=&'a PredicateObligation
<'tcx
>>, 'tcx
:'a
424 let mut result
= EvaluatedToOk
;
425 for obligation
in predicates
{
426 match self.evaluate_predicate_recursively(stack
, obligation
) {
427 EvaluatedToErr(e
) => { return EvaluatedToErr(e); }
428 EvaluatedToAmbig
=> { result = EvaluatedToAmbig; }
435 fn evaluate_predicate_recursively
<'o
>(&mut self,
436 previous_stack
: TraitObligationStackList
<'o
, 'tcx
>,
437 obligation
: &PredicateObligation
<'tcx
>)
438 -> EvaluationResult
<'tcx
>
440 debug
!("evaluate_predicate_recursively({:?})",
443 // Check the cache from the tcx of predicates that we know
444 // have been proven elsewhere. This cache only contains
445 // predicates that are global in scope and hence unaffected by
446 // the current environment.
447 if self.tcx().fulfilled_predicates
.borrow().is_duplicate(&obligation
.predicate
) {
448 return EvaluatedToOk
;
451 match obligation
.predicate
{
452 ty
::Predicate
::Trait(ref t
) => {
453 assert
!(!t
.has_escaping_regions());
454 let obligation
= obligation
.with(t
.clone());
455 self.evaluate_obligation_recursively(previous_stack
, &obligation
)
458 ty
::Predicate
::Equate(ref p
) => {
459 let result
= self.infcx
.probe(|_
| {
460 self.infcx
.equality_predicate(obligation
.cause
.span
, p
)
463 Ok(()) => EvaluatedToOk
,
464 Err(_
) => EvaluatedToErr(Unimplemented
),
468 ty
::Predicate
::TypeOutlives(..) | ty
::Predicate
::RegionOutlives(..) => {
469 // we do not consider region relationships when
470 // evaluating trait matches
474 ty
::Predicate
::Projection(ref data
) => {
475 self.infcx
.probe(|_
| {
476 let project_obligation
= obligation
.with(data
.clone());
477 match project
::poly_project_and_unify_type(self, &project_obligation
) {
478 Ok(Some(subobligations
)) => {
479 self.evaluate_predicates_recursively(previous_stack
,
480 subobligations
.iter())
486 EvaluatedToErr(Unimplemented
)
494 fn evaluate_obligation_recursively
<'o
>(&mut self,
495 previous_stack
: TraitObligationStackList
<'o
, 'tcx
>,
496 obligation
: &TraitObligation
<'tcx
>)
497 -> EvaluationResult
<'tcx
>
499 debug
!("evaluate_obligation_recursively({:?})",
502 let stack
= self.push_stack(previous_stack
, obligation
);
504 let result
= self.evaluate_stack(&stack
);
506 debug
!("result: {:?}", result
);
510 fn evaluate_stack
<'o
>(&mut self,
511 stack
: &TraitObligationStack
<'o
, 'tcx
>)
512 -> EvaluationResult
<'tcx
>
514 // In intercrate mode, whenever any of the types are unbound,
515 // there can always be an impl. Even if there are no impls in
516 // this crate, perhaps the type would be unified with
517 // something from another crate that does provide an impl.
519 // In intracrate mode, we must still be conservative. The reason is
520 // that we want to avoid cycles. Imagine an impl like:
522 // impl<T:Eq> Eq for Vec<T>
524 // and a trait reference like `$0 : Eq` where `$0` is an
525 // unbound variable. When we evaluate this trait-reference, we
526 // will unify `$0` with `Vec<$1>` (for some fresh variable
527 // `$1`), on the condition that `$1 : Eq`. We will then wind
528 // up with many candidates (since that are other `Eq` impls
529 // that apply) and try to winnow things down. This results in
530 // a recursive evaluation that `$1 : Eq` -- as you can
531 // imagine, this is just where we started. To avoid that, we
532 // check for unbound variables and return an ambiguous (hence possible)
533 // match if we've seen this trait before.
535 // This suffices to allow chains like `FnMut` implemented in
536 // terms of `Fn` etc, but we could probably make this more
538 let input_types
= stack
.fresh_trait_ref
.0.input_types
();
539 let unbound_input_types
= input_types
.iter().any(|ty
| ty
.is_fresh());
541 unbound_input_types
&&
543 stack
.iter().skip(1).any(
544 |prev
| self.match_fresh_trait_refs(&stack
.fresh_trait_ref
,
545 &prev
.fresh_trait_ref
)))
547 debug
!("evaluate_stack({:?}) --> unbound argument, recursion --> ambiguous",
548 stack
.fresh_trait_ref
);
549 return EvaluatedToAmbig
;
552 // If there is any previous entry on the stack that precisely
553 // matches this obligation, then we can assume that the
554 // obligation is satisfied for now (still all other conditions
555 // must be met of course). One obvious case this comes up is
556 // marker traits like `Send`. Think of a linked list:
558 // struct List<T> { data: T, next: Option<Box<List<T>>> {
560 // `Box<List<T>>` will be `Send` if `T` is `Send` and
561 // `Option<Box<List<T>>>` is `Send`, and in turn
562 // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
565 // Note that we do this comparison using the `fresh_trait_ref`
566 // fields. Because these have all been skolemized using
567 // `self.freshener`, we can be sure that (a) this will not
568 // affect the inferencer state and (b) that if we see two
569 // skolemized types with the same index, they refer to the
570 // same unbound type variable.
573 .skip(1) // skip top-most frame
574 .any(|prev
| stack
.fresh_trait_ref
== prev
.fresh_trait_ref
)
576 debug
!("evaluate_stack({:?}) --> recursive",
577 stack
.fresh_trait_ref
);
578 return EvaluatedToOk
;
581 match self.candidate_from_obligation(stack
) {
582 Ok(Some(c
)) => self.winnow_candidate(stack
, &c
),
583 Ok(None
) => EvaluatedToAmbig
,
584 Err(e
) => EvaluatedToErr(e
),
588 /// Evaluates whether the impl with id `impl_def_id` could be applied to the self type
589 /// `obligation_self_ty`. This can be used either for trait or inherent impls.
590 pub fn evaluate_impl(&mut self,
591 impl_def_id
: ast
::DefId
,
592 obligation
: &TraitObligation
<'tcx
>)
595 debug
!("evaluate_impl(impl_def_id={:?}, obligation={:?})",
599 self.infcx
.probe(|snapshot
| {
600 match self.match_impl(impl_def_id
, obligation
, snapshot
) {
601 Ok((substs
, skol_map
)) => {
602 let vtable_impl
= self.vtable_impl(impl_def_id
,
604 obligation
.cause
.clone(),
605 obligation
.recursion_depth
+ 1,
608 self.winnow_selection(TraitObligationStackList
::empty(),
609 VtableImpl(vtable_impl
)).may_apply()
618 ///////////////////////////////////////////////////////////////////////////
619 // CANDIDATE ASSEMBLY
621 // The selection process begins by examining all in-scope impls,
622 // caller obligations, and so forth and assembling a list of
623 // candidates. See `README.md` and the `Candidate` type for more
626 fn candidate_from_obligation
<'o
>(&mut self,
627 stack
: &TraitObligationStack
<'o
, 'tcx
>)
628 -> SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>
630 // Watch out for overflow. This intentionally bypasses (and does
631 // not update) the cache.
632 let recursion_limit
= self.infcx
.tcx
.sess
.recursion_limit
.get();
633 if stack
.obligation
.recursion_depth
>= recursion_limit
{
634 report_overflow_error(self.infcx(), &stack
.obligation
);
637 // Check the cache. Note that we skolemize the trait-ref
638 // separately rather than using `stack.fresh_trait_ref` -- this
639 // is because we want the unbound variables to be replaced
640 // with fresh skolemized types starting from index 0.
641 let cache_fresh_trait_pred
=
642 self.infcx
.freshen(stack
.obligation
.predicate
.clone());
643 debug
!("candidate_from_obligation(cache_fresh_trait_pred={:?}, obligation={:?})",
644 cache_fresh_trait_pred
,
646 assert
!(!stack
.obligation
.predicate
.has_escaping_regions());
648 match self.check_candidate_cache(&cache_fresh_trait_pred
) {
650 debug
!("CACHE HIT: cache_fresh_trait_pred={:?}, candidate={:?}",
651 cache_fresh_trait_pred
,
658 // If no match, compute result and insert into cache.
659 let candidate
= self.candidate_from_obligation_no_cache(stack
);
661 if self.should_update_candidate_cache(&cache_fresh_trait_pred
, &candidate
) {
662 debug
!("CACHE MISS: cache_fresh_trait_pred={:?}, candidate={:?}",
663 cache_fresh_trait_pred
, candidate
);
664 self.insert_candidate_cache(cache_fresh_trait_pred
, candidate
.clone());
670 fn candidate_from_obligation_no_cache
<'o
>(&mut self,
671 stack
: &TraitObligationStack
<'o
, 'tcx
>)
672 -> SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>
674 if stack
.obligation
.predicate
.0.self_ty().references_error() {
675 return Ok(Some(ErrorCandidate
));
678 if !self.is_knowable(stack
) {
679 debug
!("intercrate not knowable");
683 let candidate_set
= try
!(self.assemble_candidates(stack
));
685 if candidate_set
.ambiguous
{
686 debug
!("candidate set contains ambig");
690 let mut candidates
= candidate_set
.vec
;
692 debug
!("assembled {} candidates for {:?}: {:?}",
697 // At this point, we know that each of the entries in the
698 // candidate set is *individually* applicable. Now we have to
699 // figure out if they contain mutual incompatibilities. This
700 // frequently arises if we have an unconstrained input type --
701 // for example, we are looking for $0:Eq where $0 is some
702 // unconstrained type variable. In that case, we'll get a
703 // candidate which assumes $0 == int, one that assumes $0 ==
704 // usize, etc. This spells an ambiguity.
706 // If there is more than one candidate, first winnow them down
707 // by considering extra conditions (nested obligations and so
708 // forth). We don't winnow if there is exactly one
709 // candidate. This is a relatively minor distinction but it
710 // can lead to better inference and error-reporting. An
711 // example would be if there was an impl:
713 // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
715 // and we were to see some code `foo.push_clone()` where `boo`
716 // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
717 // we were to winnow, we'd wind up with zero candidates.
718 // Instead, we select the right impl now but report `Bar does
719 // not implement Clone`.
720 if candidates
.len() > 1 {
721 candidates
.retain(|c
| self.winnow_candidate(stack
, c
).may_apply())
724 // If there are STILL multiple candidate, we can further reduce
725 // the list by dropping duplicates.
726 if candidates
.len() > 1 {
728 while i
< candidates
.len() {
730 (0..candidates
.len())
732 .any(|j
| self.candidate_should_be_dropped_in_favor_of(&candidates
[i
],
735 debug
!("Dropping candidate #{}/{}: {:?}",
736 i
, candidates
.len(), candidates
[i
]);
737 candidates
.swap_remove(i
);
739 debug
!("Retaining candidate #{}/{}: {:?}",
740 i
, candidates
.len(), candidates
[i
]);
746 // If there are *STILL* multiple candidates, give up and
748 if candidates
.len() > 1 {
749 debug
!("multiple matches, ambig");
754 // If there are *NO* candidates, that there are no impls --
755 // that we know of, anyway. Note that in the case where there
756 // are unbound type variables within the obligation, it might
757 // be the case that you could still satisfy the obligation
758 // from another crate by instantiating the type variables with
759 // a type from another crate that does have an impl. This case
760 // is checked for in `evaluate_stack` (and hence users
761 // who might care about this case, like coherence, should use
763 if candidates
.is_empty() {
764 return Err(Unimplemented
);
767 // Just one candidate left.
768 let candidate
= candidates
.pop().unwrap();
771 ImplCandidate(def_id
) => {
772 match self.tcx().trait_impl_polarity(def_id
) {
773 Some(ast
::ImplPolarity
::Negative
) => return Err(Unimplemented
),
783 fn is_knowable
<'o
>(&mut self,
784 stack
: &TraitObligationStack
<'o
, 'tcx
>)
787 debug
!("is_knowable(intercrate={})", self.intercrate
);
789 if !self.intercrate
{
793 let obligation
= &stack
.obligation
;
794 let predicate
= self.infcx().resolve_type_vars_if_possible(&obligation
.predicate
);
796 // ok to skip binder because of the nature of the
797 // trait-ref-is-knowable check, which does not care about
799 let trait_ref
= &predicate
.skip_binder().trait_ref
;
801 coherence
::trait_ref_is_knowable(self.tcx(), trait_ref
)
804 fn pick_candidate_cache(&self) -> &SelectionCache
<'tcx
> {
805 // If there are any where-clauses in scope, then we always use
806 // a cache local to this particular scope. Otherwise, we
807 // switch to a global cache. We used to try and draw
808 // finer-grained distinctions, but that led to a serious of
809 // annoying and weird bugs like #22019 and #18290. This simple
810 // rule seems to be pretty clearly safe and also still retains
811 // a very high hit rate (~95% when compiling rustc).
812 if !self.param_env().caller_bounds
.is_empty() {
813 return &self.param_env().selection_cache
;
816 // Avoid using the master cache during coherence and just rely
817 // on the local cache. This effectively disables caching
818 // during coherence. It is really just a simplification to
819 // avoid us having to fear that coherence results "pollute"
820 // the master cache. Since coherence executes pretty quickly,
821 // it's not worth going to more trouble to increase the
822 // hit-rate I don't think.
824 return &self.param_env().selection_cache
;
827 // Otherwise, we can use the global cache.
828 &self.tcx().selection_cache
831 fn check_candidate_cache(&mut self,
832 cache_fresh_trait_pred
: &ty
::PolyTraitPredicate
<'tcx
>)
833 -> Option
<SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>>
835 let cache
= self.pick_candidate_cache();
836 let hashmap
= cache
.hashmap
.borrow();
837 hashmap
.get(&cache_fresh_trait_pred
.0.trait_ref
).cloned()
840 fn insert_candidate_cache(&mut self,
841 cache_fresh_trait_pred
: ty
::PolyTraitPredicate
<'tcx
>,
842 candidate
: SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>)
844 let cache
= self.pick_candidate_cache();
845 let mut hashmap
= cache
.hashmap
.borrow_mut();
846 hashmap
.insert(cache_fresh_trait_pred
.0.trait_ref
.clone(), candidate
);
849 fn should_update_candidate_cache(&mut self,
850 cache_fresh_trait_pred
: &ty
::PolyTraitPredicate
<'tcx
>,
851 candidate
: &SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>>)
854 // In general, it's a good idea to cache results, even
855 // ambiguous ones, to save us some trouble later. But we have
856 // to be careful not to cache results that could be
857 // invalidated later by advances in inference. Normally, this
858 // is not an issue, because any inference variables whose
859 // types are not yet bound are "freshened" in the cache key,
860 // which means that if we later get the same request once that
861 // type variable IS bound, we'll have a different cache key.
862 // For example, if we have `Vec<_#0t> : Foo`, and `_#0t` is
863 // not yet known, we may cache the result as `None`. But if
864 // later `_#0t` is bound to `Bar`, then when we freshen we'll
865 // have `Vec<Bar> : Foo` as the cache key.
867 // HOWEVER, it CAN happen that we get an ambiguity result in
868 // one particular case around closures where the cache key
869 // would not change. That is when the precise types of the
870 // upvars that a closure references have not yet been figured
871 // out (i.e., because it is not yet known if they are captured
872 // by ref, and if by ref, what kind of ref). In these cases,
873 // when matching a builtin bound, we will yield back an
874 // ambiguous result. But the *cache key* is just the closure type,
875 // it doesn't capture the state of the upvar computation.
877 // To avoid this trap, just don't cache ambiguous results if
878 // the self-type contains no inference byproducts (that really
879 // shouldn't happen in other circumstances anyway, given
883 Ok(Some(_
)) | Err(_
) => true,
885 cache_fresh_trait_pred
.0.input_types
().has_infer_types()
890 fn assemble_candidates
<'o
>(&mut self,
891 stack
: &TraitObligationStack
<'o
, 'tcx
>)
892 -> Result
<SelectionCandidateSet
<'tcx
>, SelectionError
<'tcx
>>
894 let TraitObligationStack { obligation, .. }
= *stack
;
896 let mut candidates
= SelectionCandidateSet
{
901 // Other bounds. Consider both in-scope bounds from fn decl
902 // and applicable impls. There is a certain set of precedence rules here.
904 match self.tcx().lang_items
.to_builtin_kind(obligation
.predicate
.def_id()) {
905 Some(ty
::BoundCopy
) => {
906 debug
!("obligation self ty is {:?}",
907 obligation
.predicate
.0.self_ty());
909 // User-defined copy impls are permitted, but only for
910 // structs and enums.
911 try
!(self.assemble_candidates_from_impls(obligation
, &mut candidates
));
913 // For other types, we'll use the builtin rules.
914 try
!(self.assemble_builtin_bound_candidates(ty
::BoundCopy
,
918 Some(bound @ ty
::BoundSized
) => {
919 // Sized is never implementable by end-users, it is
920 // always automatically computed.
921 try
!(self.assemble_builtin_bound_candidates(bound
, stack
, &mut candidates
));
924 None
if self.tcx().lang_items
.unsize_trait() ==
925 Some(obligation
.predicate
.def_id()) => {
926 self.assemble_candidates_for_unsizing(obligation
, &mut candidates
);
929 Some(ty
::BoundSend
) |
930 Some(ty
::BoundSync
) |
932 try
!(self.assemble_closure_candidates(obligation
, &mut candidates
));
933 try
!(self.assemble_fn_pointer_candidates(obligation
, &mut candidates
));
934 try
!(self.assemble_candidates_from_impls(obligation
, &mut candidates
));
935 self.assemble_candidates_from_object_ty(obligation
, &mut candidates
);
939 self.assemble_candidates_from_projected_tys(obligation
, &mut candidates
);
940 try
!(self.assemble_candidates_from_caller_bounds(stack
, &mut candidates
));
941 // Default implementations have lower priority, so we only
942 // consider triggering a default if there is no other impl that can apply.
943 if candidates
.vec
.is_empty() {
944 try
!(self.assemble_candidates_from_default_impls(obligation
, &mut candidates
));
946 debug
!("candidate list size: {}", candidates
.vec
.len());
950 fn assemble_candidates_from_projected_tys(&mut self,
951 obligation
: &TraitObligation
<'tcx
>,
952 candidates
: &mut SelectionCandidateSet
<'tcx
>)
954 let poly_trait_predicate
=
955 self.infcx().resolve_type_vars_if_possible(&obligation
.predicate
);
957 debug
!("assemble_candidates_for_projected_tys({:?},{:?})",
959 poly_trait_predicate
);
961 // FIXME(#20297) -- just examining the self-type is very simplistic
963 // before we go into the whole skolemization thing, just
964 // quickly check if the self-type is a projection at all.
965 let trait_def_id
= match poly_trait_predicate
.0.trait_ref
.self_ty().sty
{
966 ty
::TyProjection(ref data
) => data
.trait_ref
.def_id
,
967 ty
::TyInfer(ty
::TyVar(_
)) => {
968 // If the self-type is an inference variable, then it MAY wind up
969 // being a projected type, so induce an ambiguity.
971 // FIXME(#20297) -- being strict about this can cause
972 // inference failures with BorrowFrom, which is
973 // unfortunate. Can we do better here?
974 debug
!("assemble_candidates_for_projected_tys: ambiguous self-type");
975 candidates
.ambiguous
= true;
981 debug
!("assemble_candidates_for_projected_tys: trait_def_id={:?}",
984 let result
= self.infcx
.probe(|snapshot
| {
985 self.match_projection_obligation_against_bounds_from_trait(obligation
,
990 candidates
.vec
.push(ProjectionCandidate
);
994 fn match_projection_obligation_against_bounds_from_trait(
996 obligation
: &TraitObligation
<'tcx
>,
997 snapshot
: &infer
::CombinedSnapshot
)
1000 let poly_trait_predicate
=
1001 self.infcx().resolve_type_vars_if_possible(&obligation
.predicate
);
1002 let (skol_trait_predicate
, skol_map
) =
1003 self.infcx().skolemize_late_bound_regions(&poly_trait_predicate
, snapshot
);
1004 debug
!("match_projection_obligation_against_bounds_from_trait: \
1005 skol_trait_predicate={:?} skol_map={:?}",
1006 skol_trait_predicate
,
1009 let projection_trait_ref
= match skol_trait_predicate
.trait_ref
.self_ty().sty
{
1010 ty
::TyProjection(ref data
) => &data
.trait_ref
,
1012 self.tcx().sess
.span_bug(
1013 obligation
.cause
.span
,
1014 &format
!("match_projection_obligation_against_bounds_from_trait() called \
1015 but self-ty not a projection: {:?}",
1016 skol_trait_predicate
.trait_ref
.self_ty()));
1019 debug
!("match_projection_obligation_against_bounds_from_trait: \
1020 projection_trait_ref={:?}",
1021 projection_trait_ref
);
1023 let trait_predicates
= self.tcx().lookup_predicates(projection_trait_ref
.def_id
);
1024 let bounds
= trait_predicates
.instantiate(self.tcx(), projection_trait_ref
.substs
);
1025 debug
!("match_projection_obligation_against_bounds_from_trait: \
1029 let matching_bound
=
1030 util
::elaborate_predicates(self.tcx(), bounds
.predicates
.into_vec())
1033 |bound
| self.infcx
.probe(
1034 |_
| self.match_projection(obligation
,
1036 skol_trait_predicate
.trait_ref
.clone(),
1040 debug
!("match_projection_obligation_against_bounds_from_trait: \
1041 matching_bound={:?}",
1043 match matching_bound
{
1046 // Repeat the successful match, if any, this time outside of a probe.
1047 let result
= self.match_projection(obligation
,
1049 skol_trait_predicate
.trait_ref
.clone(),
1058 fn match_projection(&mut self,
1059 obligation
: &TraitObligation
<'tcx
>,
1060 trait_bound
: ty
::PolyTraitRef
<'tcx
>,
1061 skol_trait_ref
: ty
::TraitRef
<'tcx
>,
1062 skol_map
: &infer
::SkolemizationMap
,
1063 snapshot
: &infer
::CombinedSnapshot
)
1066 assert
!(!skol_trait_ref
.has_escaping_regions());
1067 let origin
= infer
::RelateOutputImplTypes(obligation
.cause
.span
);
1068 match self.infcx
.sub_poly_trait_refs(false,
1070 trait_bound
.clone(),
1071 ty
::Binder(skol_trait_ref
.clone())) {
1073 Err(_
) => { return false; }
1076 self.infcx
.leak_check(skol_map
, snapshot
).is_ok()
1079 /// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller
1080 /// supplied to find out whether it is listed among them.
1082 /// Never affects inference environment.
1083 fn assemble_candidates_from_caller_bounds
<'o
>(&mut self,
1084 stack
: &TraitObligationStack
<'o
, 'tcx
>,
1085 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1086 -> Result
<(),SelectionError
<'tcx
>>
1088 debug
!("assemble_candidates_from_caller_bounds({:?})",
1092 self.param_env().caller_bounds
1094 .filter_map(|o
| o
.to_opt_poly_trait_ref());
1096 let matching_bounds
=
1098 |bound
| self.evaluate_where_clause(stack
, bound
.clone()).may_apply());
1100 let param_candidates
=
1101 matching_bounds
.map(|bound
| ParamCandidate(bound
));
1103 candidates
.vec
.extend(param_candidates
);
1108 fn evaluate_where_clause
<'o
>(&mut self,
1109 stack
: &TraitObligationStack
<'o
, 'tcx
>,
1110 where_clause_trait_ref
: ty
::PolyTraitRef
<'tcx
>)
1111 -> EvaluationResult
<'tcx
>
1113 self.infcx().probe(move |_
| {
1114 match self.match_where_clause_trait_ref(stack
.obligation
, where_clause_trait_ref
) {
1115 Ok(obligations
) => {
1116 self.evaluate_predicates_recursively(stack
.list(), obligations
.iter())
1119 EvaluatedToErr(Unimplemented
)
1125 /// Check for the artificial impl that the compiler will create for an obligation like `X :
1126 /// FnMut<..>` where `X` is a closure type.
1128 /// Note: the type parameters on a closure candidate are modeled as *output* type
1129 /// parameters and hence do not affect whether this trait is a match or not. They will be
1130 /// unified during the confirmation step.
1131 fn assemble_closure_candidates(&mut self,
1132 obligation
: &TraitObligation
<'tcx
>,
1133 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1134 -> Result
<(),SelectionError
<'tcx
>>
1136 let kind
= match self.tcx().lang_items
.fn_trait_kind(obligation
.predicate
.0.def_id()) {
1138 None
=> { return Ok(()); }
1141 // ok to skip binder because the substs on closure types never
1142 // touch bound regions, they just capture the in-scope
1143 // type/region parameters
1144 let self_ty
= self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder());
1145 let (closure_def_id
, substs
) = match self_ty
.sty
{
1146 ty
::TyClosure(id
, ref substs
) => (id
, substs
),
1147 ty
::TyInfer(ty
::TyVar(_
)) => {
1148 debug
!("assemble_unboxed_closure_candidates: ambiguous self-type");
1149 candidates
.ambiguous
= true;
1152 _
=> { return Ok(()); }
1155 debug
!("assemble_unboxed_candidates: self_ty={:?} kind={:?} obligation={:?}",
1160 match self.infcx
.closure_kind(closure_def_id
) {
1161 Some(closure_kind
) => {
1162 debug
!("assemble_unboxed_candidates: closure_kind = {:?}", closure_kind
);
1163 if closure_kind
.extends(kind
) {
1164 candidates
.vec
.push(ClosureCandidate(closure_def_id
, substs
));
1168 debug
!("assemble_unboxed_candidates: closure_kind not yet known");
1169 candidates
.ambiguous
= true;
1176 /// Implement one of the `Fn()` family for a fn pointer.
1177 fn assemble_fn_pointer_candidates(&mut self,
1178 obligation
: &TraitObligation
<'tcx
>,
1179 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1180 -> Result
<(),SelectionError
<'tcx
>>
1182 // We provide impl of all fn traits for fn pointers.
1183 if self.tcx().lang_items
.fn_trait_kind(obligation
.predicate
.def_id()).is_none() {
1187 // ok to skip binder because what we are inspecting doesn't involve bound regions
1188 let self_ty
= self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder());
1190 ty
::TyInfer(ty
::TyVar(_
)) => {
1191 debug
!("assemble_fn_pointer_candidates: ambiguous self-type");
1192 candidates
.ambiguous
= true; // could wind up being a fn() type
1195 // provide an impl, but only for suitable `fn` pointers
1196 ty
::TyBareFn(_
, &ty
::BareFnTy
{
1197 unsafety
: ast
::Unsafety
::Normal
,
1199 sig
: ty
::Binder(ty
::FnSig
{
1201 output
: ty
::FnConverging(_
),
1205 candidates
.vec
.push(FnPointerCandidate
);
1214 /// Search for impls that might apply to `obligation`.
1215 fn assemble_candidates_from_impls(&mut self,
1216 obligation
: &TraitObligation
<'tcx
>,
1217 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1218 -> Result
<(), SelectionError
<'tcx
>>
1220 debug
!("assemble_candidates_from_impls(obligation={:?})", obligation
);
1222 let def
= self.tcx().lookup_trait_def(obligation
.predicate
.def_id());
1224 def
.for_each_relevant_impl(
1226 obligation
.predicate
.0.trait_ref
.self_ty(),
1228 self.infcx
.probe(|snapshot
| {
1229 if let Ok(_
) = self.match_impl(impl_def_id
, obligation
, snapshot
) {
1230 candidates
.vec
.push(ImplCandidate(impl_def_id
));
1239 fn assemble_candidates_from_default_impls(&mut self,
1240 obligation
: &TraitObligation
<'tcx
>,
1241 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1242 -> Result
<(), SelectionError
<'tcx
>>
1244 // OK to skip binder here because the tests we do below do not involve bound regions
1245 let self_ty
= self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder());
1246 debug
!("assemble_candidates_from_default_impls(self_ty={:?})", self_ty
);
1248 let def_id
= obligation
.predicate
.def_id();
1250 if self.tcx().trait_has_default_impl(def_id
) {
1252 ty
::TyTrait(..) => {
1253 // For object types, we don't know what the closed
1254 // over types are. For most traits, this means we
1255 // conservatively say nothing; a candidate may be
1256 // added by `assemble_candidates_from_object_ty`.
1257 // However, for the kind of magic reflect trait,
1258 // we consider it to be implemented even for
1259 // object types, because it just lets you reflect
1260 // onto the object type, not into the object's
1262 if self.tcx().has_attr(def_id
, "rustc_reflect_like") {
1263 candidates
.vec
.push(DefaultImplObjectCandidate(def_id
));
1267 ty
::TyProjection(..) => {
1268 // In these cases, we don't know what the actual
1269 // type is. Therefore, we cannot break it down
1270 // into its constituent types. So we don't
1271 // consider the `..` impl but instead just add no
1272 // candidates: this means that typeck will only
1273 // succeed if there is another reason to believe
1274 // that this obligation holds. That could be a
1275 // where-clause or, in the case of an object type,
1276 // it could be that the object type lists the
1277 // trait (e.g. `Foo+Send : Send`). See
1278 // `compile-fail/typeck-default-trait-impl-send-param.rs`
1279 // for an example of a test case that exercises
1282 ty
::TyInfer(ty
::TyVar(_
)) => {
1283 // the defaulted impl might apply, we don't know
1284 candidates
.ambiguous
= true;
1287 candidates
.vec
.push(DefaultImplCandidate(def_id
.clone()))
1295 /// Search for impls that might apply to `obligation`.
1296 fn assemble_candidates_from_object_ty(&mut self,
1297 obligation
: &TraitObligation
<'tcx
>,
1298 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1300 debug
!("assemble_candidates_from_object_ty(self_ty={:?})",
1301 self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder()));
1303 // Object-safety candidates are only applicable to object-safe
1304 // traits. Including this check is useful because it helps
1305 // inference in cases of traits like `BorrowFrom`, which are
1306 // not object-safe, and which rely on being able to infer the
1307 // self-type from one of the other inputs. Without this check,
1308 // these cases wind up being considered ambiguous due to a
1309 // (spurious) ambiguity introduced here.
1310 let predicate_trait_ref
= obligation
.predicate
.to_poly_trait_ref();
1311 if !object_safety
::is_object_safe(self.tcx(), predicate_trait_ref
.def_id()) {
1315 self.infcx
.commit_if_ok(|snapshot
| {
1317 self.infcx
.resolve_type_vars_if_possible(&obligation
.self_ty());
1319 self.infcx().skolemize_late_bound_regions(&bound_self_ty
, snapshot
);
1320 let poly_trait_ref
= match self_ty
.sty
{
1321 ty
::TyTrait(ref data
) => {
1322 match self.tcx().lang_items
.to_builtin_kind(obligation
.predicate
.def_id()) {
1323 Some(bound @ ty
::BoundSend
) | Some(bound @ ty
::BoundSync
) => {
1324 if data
.bounds
.builtin_bounds
.contains(&bound
) {
1325 debug
!("assemble_candidates_from_object_ty: matched builtin bound, \
1326 pushing candidate");
1327 candidates
.vec
.push(BuiltinObjectCandidate
);
1334 data
.principal_trait_ref_with_self_ty(self.tcx(), self_ty
)
1336 ty
::TyInfer(ty
::TyVar(_
)) => {
1337 debug
!("assemble_candidates_from_object_ty: ambiguous");
1338 candidates
.ambiguous
= true; // could wind up being an object type
1346 debug
!("assemble_candidates_from_object_ty: poly_trait_ref={:?}",
1349 // Count only those upcast versions that match the trait-ref
1350 // we are looking for. Specifically, do not only check for the
1351 // correct trait, but also the correct type parameters.
1352 // For example, we may be trying to upcast `Foo` to `Bar<i32>`,
1353 // but `Foo` is declared as `trait Foo : Bar<u32>`.
1354 let upcast_trait_refs
=
1355 util
::supertraits(self.tcx(), poly_trait_ref
)
1356 .filter(|upcast_trait_ref
| {
1357 self.infcx
.probe(|_
| {
1358 let upcast_trait_ref
= upcast_trait_ref
.clone();
1359 self.match_poly_trait_ref(obligation
, upcast_trait_ref
).is_ok()
1364 if upcast_trait_refs
> 1 {
1365 // can be upcast in many ways; need more type information
1366 candidates
.ambiguous
= true;
1367 } else if upcast_trait_refs
== 1 {
1368 candidates
.vec
.push(ObjectCandidate
);
1375 /// Search for unsizing that might apply to `obligation`.
1376 fn assemble_candidates_for_unsizing(&mut self,
1377 obligation
: &TraitObligation
<'tcx
>,
1378 candidates
: &mut SelectionCandidateSet
<'tcx
>) {
1379 // We currently never consider higher-ranked obligations e.g.
1380 // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
1381 // because they are a priori invalid, and we could potentially add support
1382 // for them later, it's just that there isn't really a strong need for it.
1383 // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
1384 // impl, and those are generally applied to concrete types.
1386 // That said, one might try to write a fn with a where clause like
1387 // for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
1388 // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
1389 // Still, you'd be more likely to write that where clause as
1391 // so it seems ok if we (conservatively) fail to accept that `Unsize`
1392 // obligation above. Should be possible to extend this in the future.
1393 let self_ty
= match self.tcx().no_late_bound_regions(&obligation
.self_ty()) {
1396 // Don't add any candidates if there are bound regions.
1400 let source
= self.infcx
.shallow_resolve(self_ty
);
1401 let target
= self.infcx
.shallow_resolve(obligation
.predicate
.0.input_types
()[0]);
1403 debug
!("assemble_candidates_for_unsizing(source={:?}, target={:?})",
1406 let may_apply
= match (&source
.sty
, &target
.sty
) {
1407 // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
1408 (&ty
::TyTrait(ref data_a
), &ty
::TyTrait(ref data_b
)) => {
1409 // Upcasts permit two things:
1411 // 1. Dropping builtin bounds, e.g. `Foo+Send` to `Foo`
1412 // 2. Tightening the region bound, e.g. `Foo+'a` to `Foo+'b` if `'a : 'b`
1414 // Note that neither of these changes requires any
1415 // change at runtime. Eventually this will be
1418 // We always upcast when we can because of reason
1419 // #2 (region bounds).
1420 data_a
.principal
.def_id() == data_a
.principal
.def_id() &&
1421 data_a
.bounds
.builtin_bounds
.is_superset(&data_b
.bounds
.builtin_bounds
)
1425 (_
, &ty
::TyTrait(_
)) => true,
1427 // Ambiguous handling is below T -> Trait, because inference
1428 // variables can still implement Unsize<Trait> and nested
1429 // obligations will have the final say (likely deferred).
1430 (&ty
::TyInfer(ty
::TyVar(_
)), _
) |
1431 (_
, &ty
::TyInfer(ty
::TyVar(_
))) => {
1432 debug
!("assemble_candidates_for_unsizing: ambiguous");
1433 candidates
.ambiguous
= true;
1438 (&ty
::TyArray(_
, _
), &ty
::TySlice(_
)) => true,
1440 // Struct<T> -> Struct<U>.
1441 (&ty
::TyStruct(def_id_a
, _
), &ty
::TyStruct(def_id_b
, _
)) => {
1442 def_id_a
== def_id_b
1449 candidates
.vec
.push(BuiltinUnsizeCandidate
);
1453 ///////////////////////////////////////////////////////////////////////////
1456 // Winnowing is the process of attempting to resolve ambiguity by
1457 // probing further. During the winnowing process, we unify all
1458 // type variables (ignoring skolemization) and then we also
1459 // attempt to evaluate recursive bounds to see if they are
1462 /// Further evaluate `candidate` to decide whether all type parameters match and whether nested
1463 /// obligations are met. Returns true if `candidate` remains viable after this further
1465 fn winnow_candidate
<'o
>(&mut self,
1466 stack
: &TraitObligationStack
<'o
, 'tcx
>,
1467 candidate
: &SelectionCandidate
<'tcx
>)
1468 -> EvaluationResult
<'tcx
>
1470 debug
!("winnow_candidate: candidate={:?}", candidate
);
1471 let result
= self.infcx
.probe(|_
| {
1472 let candidate
= (*candidate
).clone();
1473 match self.confirm_candidate(stack
.obligation
, candidate
) {
1474 Ok(selection
) => self.winnow_selection(stack
.list(),
1476 Err(error
) => EvaluatedToErr(error
),
1479 debug
!("winnow_candidate depth={} result={:?}",
1480 stack
.obligation
.recursion_depth
, result
);
1484 fn winnow_selection
<'o
>(&mut self,
1485 stack
: TraitObligationStackList
<'o
,'tcx
>,
1486 selection
: Selection
<'tcx
>)
1487 -> EvaluationResult
<'tcx
>
1489 self.evaluate_predicates_recursively(stack
,
1490 selection
.nested_obligations().iter())
1493 /// Returns true if `candidate_i` should be dropped in favor of
1494 /// `candidate_j`. Generally speaking we will drop duplicate
1495 /// candidates and prefer where-clause candidates.
1496 /// Returns true if `victim` should be dropped in favor of
1497 /// `other`. Generally speaking we will drop duplicate
1498 /// candidates and prefer where-clause candidates.
1500 /// See the comment for "SelectionCandidate" for more details.
1501 fn candidate_should_be_dropped_in_favor_of
<'o
>(&mut self,
1502 victim
: &SelectionCandidate
<'tcx
>,
1503 other
: &SelectionCandidate
<'tcx
>)
1506 if victim
== other
{
1511 &ObjectCandidate(..) |
1512 &ParamCandidate(_
) | &ProjectionCandidate
=> match victim
{
1513 &DefaultImplCandidate(..) => {
1514 self.tcx().sess
.bug(
1515 "default implementations shouldn't be recorded \
1516 when there are other valid candidates");
1518 &PhantomFnCandidate
=> {
1519 self.tcx().sess
.bug("PhantomFn didn't short-circuit selection");
1521 &ImplCandidate(..) |
1522 &ClosureCandidate(..) |
1523 &FnPointerCandidate(..) |
1524 &BuiltinObjectCandidate(..) |
1525 &BuiltinUnsizeCandidate(..) |
1526 &DefaultImplObjectCandidate(..) |
1527 &BuiltinCandidate(..) => {
1528 // We have a where-clause so don't go around looking
1532 &ObjectCandidate(..) |
1533 &ProjectionCandidate
=> {
1534 // Arbitrarily give param candidates priority
1535 // over projection and object candidates.
1538 &ParamCandidate(..) => false,
1539 &ErrorCandidate
=> false // propagate errors
1545 ///////////////////////////////////////////////////////////////////////////
1548 // These cover the traits that are built-in to the language
1549 // itself. This includes `Copy` and `Sized` for sure. For the
1550 // moment, it also includes `Send` / `Sync` and a few others, but
1551 // those will hopefully change to library-defined traits in the
1554 fn assemble_builtin_bound_candidates
<'o
>(&mut self,
1555 bound
: ty
::BuiltinBound
,
1556 stack
: &TraitObligationStack
<'o
, 'tcx
>,
1557 candidates
: &mut SelectionCandidateSet
<'tcx
>)
1558 -> Result
<(),SelectionError
<'tcx
>>
1560 match self.builtin_bound(bound
, stack
.obligation
) {
1562 debug
!("builtin_bound: bound={:?}",
1564 candidates
.vec
.push(BuiltinCandidate(bound
));
1567 Ok(ParameterBuiltin
) => { Ok(()) }
1568 Ok(AmbiguousBuiltin
) => {
1569 debug
!("assemble_builtin_bound_candidates: ambiguous builtin");
1570 Ok(candidates
.ambiguous
= true)
1572 Err(e
) => { Err(e) }
1576 fn builtin_bound(&mut self,
1577 bound
: ty
::BuiltinBound
,
1578 obligation
: &TraitObligation
<'tcx
>)
1579 -> Result
<BuiltinBoundConditions
<'tcx
>,SelectionError
<'tcx
>>
1581 // Note: these tests operate on types that may contain bound
1582 // regions. To be proper, we ought to skolemize here, but we
1583 // forego the skolemization and defer it until the
1584 // confirmation step.
1586 let self_ty
= self.infcx
.shallow_resolve(obligation
.predicate
.0.self_ty());
1587 return match self_ty
.sty
{
1588 ty
::TyInfer(ty
::IntVar(_
)) |
1589 ty
::TyInfer(ty
::FloatVar(_
)) |
1596 // safe for everything
1600 ty
::TyBox(_
) => { // Box<T>
1602 ty
::BoundCopy
=> Err(Unimplemented
),
1604 ty
::BoundSized
=> ok_if(Vec
::new()),
1606 ty
::BoundSync
| ty
::BoundSend
=> {
1607 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1612 ty
::TyRawPtr(..) => { // *const T, *mut T
1614 ty
::BoundCopy
| ty
::BoundSized
=> ok_if(Vec
::new()),
1616 ty
::BoundSync
| ty
::BoundSend
=> {
1617 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1622 ty
::TyTrait(ref data
) => {
1624 ty
::BoundSized
=> Err(Unimplemented
),
1626 if data
.bounds
.builtin_bounds
.contains(&bound
) {
1629 // Recursively check all supertraits to find out if any further
1630 // bounds are required and thus we must fulfill.
1632 data
.principal_trait_ref_with_self_ty(self.tcx(),
1633 self.tcx().types
.err
);
1634 let copy_def_id
= obligation
.predicate
.def_id();
1635 for tr
in util
::supertraits(self.tcx(), principal
) {
1636 if tr
.def_id() == copy_def_id
{
1637 return ok_if(Vec
::new())
1644 ty
::BoundSync
| ty
::BoundSend
=> {
1645 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1650 ty
::TyRef(_
, ty
::TypeAndMut { ty: _, mutbl }
) => {
1655 // &mut T is affine and hence never `Copy`
1656 ast
::MutMutable
=> Err(Unimplemented
),
1658 // &T is always copyable
1659 ast
::MutImmutable
=> ok_if(Vec
::new()),
1663 ty
::BoundSized
=> ok_if(Vec
::new()),
1665 ty
::BoundSync
| ty
::BoundSend
=> {
1666 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1671 ty
::TyArray(element_ty
, _
) => {
1674 ty
::BoundCopy
=> ok_if(vec
![element_ty
]),
1675 ty
::BoundSized
=> ok_if(Vec
::new()),
1676 ty
::BoundSync
| ty
::BoundSend
=> {
1677 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1682 ty
::TyStr
| ty
::TySlice(_
) => {
1684 ty
::BoundSync
| ty
::BoundSend
=> {
1685 self.tcx().sess
.bug("Send/Sync shouldn't occur in builtin_bounds()");
1688 ty
::BoundCopy
| ty
::BoundSized
=> Err(Unimplemented
),
1692 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1693 ty
::TyTuple(ref tys
) => ok_if(tys
.clone()),
1695 ty
::TyClosure(def_id
, ref substs
) => {
1696 // FIXME -- This case is tricky. In the case of by-ref
1697 // closures particularly, we need the results of
1698 // inference to decide how to reflect the type of each
1699 // upvar (the upvar may have type `T`, but the runtime
1700 // type could be `&mut`, `&`, or just `T`). For now,
1701 // though, we'll do this unsoundly and assume that all
1702 // captures are by value. Really what we ought to do
1703 // is reserve judgement and then intertwine this
1704 // analysis with closure inference.
1705 assert_eq
!(def_id
.krate
, ast
::LOCAL_CRATE
);
1707 // Unboxed closures shouldn't be
1708 // implicitly copyable
1709 if bound
== ty
::BoundCopy
{
1710 return Ok(ParameterBuiltin
);
1713 // Upvars are always local variables or references to
1714 // local variables, and local variables cannot be
1715 // unsized, so the closure struct as a whole must be
1717 if bound
== ty
::BoundSized
{
1718 return ok_if(Vec
::new());
1721 ok_if(substs
.upvar_tys
.clone())
1724 ty
::TyStruct(def_id
, substs
) => {
1725 let types
: Vec
<Ty
> =
1726 self.tcx().struct_fields(def_id
, substs
).iter()
1729 nominal(bound
, types
)
1732 ty
::TyEnum(def_id
, substs
) => {
1733 let types
: Vec
<Ty
> =
1734 self.tcx().substd_enum_variants(def_id
, substs
)
1736 .flat_map(|variant
| &variant
.args
)
1739 nominal(bound
, types
)
1742 ty
::TyProjection(_
) | ty
::TyParam(_
) => {
1743 // Note: A type parameter is only considered to meet a
1744 // particular bound if there is a where clause telling
1745 // us that it does, and that case is handled by
1746 // `assemble_candidates_from_caller_bounds()`.
1747 Ok(ParameterBuiltin
)
1750 ty
::TyInfer(ty
::TyVar(_
)) => {
1751 // Unbound type variable. Might or might not have
1752 // applicable impls and so forth, depending on what
1753 // those type variables wind up being bound to.
1754 debug
!("assemble_builtin_bound_candidates: ambiguous builtin");
1755 Ok(AmbiguousBuiltin
)
1758 ty
::TyError
=> ok_if(Vec
::new()),
1760 ty
::TyInfer(ty
::FreshTy(_
))
1761 | ty
::TyInfer(ty
::FreshIntTy(_
))
1762 | ty
::TyInfer(ty
::FreshFloatTy(_
)) => {
1763 self.tcx().sess
.bug(
1765 "asked to assemble builtin bounds of unexpected type: {:?}",
1770 fn ok_if
<'tcx
>(v
: Vec
<Ty
<'tcx
>>)
1771 -> Result
<BuiltinBoundConditions
<'tcx
>, SelectionError
<'tcx
>> {
1772 Ok(If(ty
::Binder(v
)))
1775 fn nominal
<'cx
, 'tcx
>(bound
: ty
::BuiltinBound
,
1776 types
: Vec
<Ty
<'tcx
>>)
1777 -> Result
<BuiltinBoundConditions
<'tcx
>, SelectionError
<'tcx
>>
1779 // First check for markers and other nonsense.
1781 // Fallback to whatever user-defined impls exist in this case.
1782 ty
::BoundCopy
=> Ok(ParameterBuiltin
),
1784 // Sized if all the component types are sized.
1785 ty
::BoundSized
=> ok_if(types
),
1787 // Shouldn't be coming through here.
1788 ty
::BoundSend
| ty
::BoundSync
=> unreachable
!(),
1793 /// For default impls, we need to break apart a type into its
1794 /// "constituent types" -- meaning, the types that it contains.
1796 /// Here are some (simple) examples:
1799 /// (i32, u32) -> [i32, u32]
1800 /// Foo where struct Foo { x: i32, y: u32 } -> [i32, u32]
1801 /// Bar<i32> where struct Bar<T> { x: T, y: u32 } -> [i32, u32]
1802 /// Zed<i32> where enum Zed { A(T), B(u32) } -> [i32, u32]
1804 fn constituent_types_for_ty(&self, t
: Ty
<'tcx
>) -> Vec
<Ty
<'tcx
>> {
1813 ty
::TyInfer(ty
::IntVar(_
)) |
1814 ty
::TyInfer(ty
::FloatVar(_
)) |
1821 ty
::TyProjection(..) |
1822 ty
::TyInfer(ty
::TyVar(_
)) |
1823 ty
::TyInfer(ty
::FreshTy(_
)) |
1824 ty
::TyInfer(ty
::FreshIntTy(_
)) |
1825 ty
::TyInfer(ty
::FreshFloatTy(_
)) => {
1826 self.tcx().sess
.bug(
1828 "asked to assemble constituent types of unexpected type: {:?}",
1832 ty
::TyBox(referent_ty
) => { // Box<T>
1836 ty
::TyRawPtr(ty
::TypeAndMut { ty: element_ty, ..}
) |
1837 ty
::TyRef(_
, ty
::TypeAndMut { ty: element_ty, ..}
) => {
1841 ty
::TyArray(element_ty
, _
) | ty
::TySlice(element_ty
) => {
1845 ty
::TyTuple(ref tys
) => {
1846 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1850 ty
::TyClosure(def_id
, ref substs
) => {
1851 // FIXME(#27086). We are invariant w/r/t our
1852 // substs.func_substs, but we don't see them as
1853 // constituent types; this seems RIGHT but also like
1854 // something that a normal type couldn't simulate. Is
1855 // this just a gap with the way that PhantomData and
1856 // OIBIT interact? That is, there is no way to say
1857 // "make me invariant with respect to this TYPE, but
1858 // do not act as though I can reach it"
1859 assert_eq
!(def_id
.krate
, ast
::LOCAL_CRATE
);
1860 substs
.upvar_tys
.clone()
1863 // for `PhantomData<T>`, we pass `T`
1864 ty
::TyStruct(def_id
, substs
)
1865 if Some(def_id
) == self.tcx().lang_items
.phantom_data() =>
1867 substs
.types
.get_slice(TypeSpace
).to_vec()
1870 ty
::TyStruct(def_id
, substs
) => {
1871 self.tcx().struct_fields(def_id
, substs
)
1877 ty
::TyEnum(def_id
, substs
) => {
1878 self.tcx().substd_enum_variants(def_id
, substs
)
1880 .flat_map(|variant
| &variant
.args
)
1887 fn collect_predicates_for_types(&mut self,
1888 obligation
: &TraitObligation
<'tcx
>,
1889 trait_def_id
: ast
::DefId
,
1890 types
: ty
::Binder
<Vec
<Ty
<'tcx
>>>)
1891 -> Vec
<PredicateObligation
<'tcx
>>
1893 let derived_cause
= match self.tcx().lang_items
.to_builtin_kind(trait_def_id
) {
1895 self.derived_cause(obligation
, BuiltinDerivedObligation
)
1898 self.derived_cause(obligation
, ImplDerivedObligation
)
1902 // Because the types were potentially derived from
1903 // higher-ranked obligations they may reference late-bound
1904 // regions. For example, `for<'a> Foo<&'a int> : Copy` would
1905 // yield a type like `for<'a> &'a int`. In general, we
1906 // maintain the invariant that we never manipulate bound
1907 // regions, so we have to process these bound regions somehow.
1909 // The strategy is to:
1911 // 1. Instantiate those regions to skolemized regions (e.g.,
1912 // `for<'a> &'a int` becomes `&0 int`.
1913 // 2. Produce something like `&'0 int : Copy`
1914 // 3. Re-bind the regions back to `for<'a> &'a int : Copy`
1916 // Move the binder into the individual types
1917 let bound_types
: Vec
<ty
::Binder
<Ty
<'tcx
>>> =
1920 .map(|&nested_ty
| ty
::Binder(nested_ty
))
1923 // For each type, produce a vector of resulting obligations
1924 let obligations
: Result
<Vec
<Vec
<_
>>, _
> = bound_types
.iter().map(|nested_ty
| {
1925 self.infcx
.commit_if_ok(|snapshot
| {
1926 let (skol_ty
, skol_map
) =
1927 self.infcx().skolemize_late_bound_regions(nested_ty
, snapshot
);
1928 let Normalized { value: normalized_ty, mut obligations }
=
1929 project
::normalize_with_depth(self,
1930 obligation
.cause
.clone(),
1931 obligation
.recursion_depth
+ 1,
1933 let skol_obligation
=
1934 util
::predicate_for_trait_def(self.tcx(),
1935 derived_cause
.clone(),
1937 obligation
.recursion_depth
+ 1,
1940 obligations
.push(skol_obligation
);
1941 Ok(self.infcx().plug_leaks(skol_map
, snapshot
, &obligations
))
1945 // Flatten those vectors (couldn't do it above due `collect`)
1947 Ok(obligations
) => obligations
.into_iter().flat_map(|o
| o
).collect(),
1948 Err(ErrorReported
) => Vec
::new(),
1952 ///////////////////////////////////////////////////////////////////////////
1955 // Confirmation unifies the output type parameters of the trait
1956 // with the values found in the obligation, possibly yielding a
1957 // type error. See `README.md` for more details.
1959 fn confirm_candidate(&mut self,
1960 obligation
: &TraitObligation
<'tcx
>,
1961 candidate
: SelectionCandidate
<'tcx
>)
1962 -> Result
<Selection
<'tcx
>,SelectionError
<'tcx
>>
1964 debug
!("confirm_candidate({:?}, {:?})",
1969 BuiltinCandidate(builtin_bound
) => {
1971 try
!(self.confirm_builtin_candidate(obligation
, builtin_bound
))))
1974 PhantomFnCandidate
|
1976 Ok(VtableBuiltin(VtableBuiltinData { nested: vec![] }
))
1979 ParamCandidate(param
) => {
1980 let obligations
= self.confirm_param_candidate(obligation
, param
);
1981 Ok(VtableParam(obligations
))
1984 DefaultImplCandidate(trait_def_id
) => {
1985 let data
= self.confirm_default_impl_candidate(obligation
, trait_def_id
);
1986 Ok(VtableDefaultImpl(data
))
1989 DefaultImplObjectCandidate(trait_def_id
) => {
1990 let data
= self.confirm_default_impl_object_candidate(obligation
, trait_def_id
);
1991 Ok(VtableDefaultImpl(data
))
1994 ImplCandidate(impl_def_id
) => {
1996 try
!(self.confirm_impl_candidate(obligation
, impl_def_id
));
1997 Ok(VtableImpl(vtable_impl
))
2000 ClosureCandidate(closure_def_id
, substs
) => {
2001 let vtable_closure
=
2002 try
!(self.confirm_closure_candidate(obligation
, closure_def_id
, substs
));
2003 Ok(VtableClosure(vtable_closure
))
2006 BuiltinObjectCandidate
=> {
2007 // This indicates something like `(Trait+Send) :
2008 // Send`. In this case, we know that this holds
2009 // because that's what the object type is telling us,
2010 // and there's really no additional obligations to
2011 // prove and no types in particular to unify etc.
2012 Ok(VtableParam(Vec
::new()))
2015 ObjectCandidate
=> {
2016 let data
= self.confirm_object_candidate(obligation
);
2017 Ok(VtableObject(data
))
2020 FnPointerCandidate
=> {
2022 try
!(self.confirm_fn_pointer_candidate(obligation
));
2023 Ok(VtableFnPointer(fn_type
))
2026 ProjectionCandidate
=> {
2027 self.confirm_projection_candidate(obligation
);
2028 Ok(VtableParam(Vec
::new()))
2031 BuiltinUnsizeCandidate
=> {
2032 let data
= try
!(self.confirm_builtin_unsize_candidate(obligation
));
2033 Ok(VtableBuiltin(data
))
2038 fn confirm_projection_candidate(&mut self,
2039 obligation
: &TraitObligation
<'tcx
>)
2041 let _
: Result
<(),()> =
2042 self.infcx
.commit_if_ok(|snapshot
| {
2044 self.match_projection_obligation_against_bounds_from_trait(obligation
,
2051 fn confirm_param_candidate(&mut self,
2052 obligation
: &TraitObligation
<'tcx
>,
2053 param
: ty
::PolyTraitRef
<'tcx
>)
2054 -> Vec
<PredicateObligation
<'tcx
>>
2056 debug
!("confirm_param_candidate({:?},{:?})",
2060 // During evaluation, we already checked that this
2061 // where-clause trait-ref could be unified with the obligation
2062 // trait-ref. Repeat that unification now without any
2063 // transactional boundary; it should not fail.
2064 match self.match_where_clause_trait_ref(obligation
, param
.clone()) {
2065 Ok(obligations
) => obligations
,
2067 self.tcx().sess
.bug(
2068 &format
!("Where clause `{:?}` was applicable to `{:?}` but now is not",
2075 fn confirm_builtin_candidate(&mut self,
2076 obligation
: &TraitObligation
<'tcx
>,
2077 bound
: ty
::BuiltinBound
)
2078 -> Result
<VtableBuiltinData
<PredicateObligation
<'tcx
>>,
2079 SelectionError
<'tcx
>>
2081 debug
!("confirm_builtin_candidate({:?})",
2084 match try
!(self.builtin_bound(bound
, obligation
)) {
2085 If(nested
) => Ok(self.vtable_builtin_data(obligation
, bound
, nested
)),
2086 AmbiguousBuiltin
| ParameterBuiltin
=> {
2087 self.tcx().sess
.span_bug(
2088 obligation
.cause
.span
,
2089 &format
!("builtin bound for {:?} was ambig",
2095 fn vtable_builtin_data(&mut self,
2096 obligation
: &TraitObligation
<'tcx
>,
2097 bound
: ty
::BuiltinBound
,
2098 nested
: ty
::Binder
<Vec
<Ty
<'tcx
>>>)
2099 -> VtableBuiltinData
<PredicateObligation
<'tcx
>>
2101 let trait_def
= match self.tcx().lang_items
.from_builtin_kind(bound
) {
2102 Ok(def_id
) => def_id
,
2104 self.tcx().sess
.bug("builtin trait definition not found");
2108 let obligations
= self.collect_predicates_for_types(obligation
, trait_def
, nested
);
2110 debug
!("vtable_builtin_data: obligations={:?}",
2113 VtableBuiltinData { nested: obligations }
2116 /// This handles the case where a `impl Foo for ..` impl is being used.
2117 /// The idea is that the impl applies to `X : Foo` if the following conditions are met:
2119 /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds
2120 /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds.
2121 fn confirm_default_impl_candidate(&mut self,
2122 obligation
: &TraitObligation
<'tcx
>,
2123 trait_def_id
: ast
::DefId
)
2124 -> VtableDefaultImplData
<PredicateObligation
<'tcx
>>
2126 debug
!("confirm_default_impl_candidate({:?}, {:?})",
2130 // binder is moved below
2131 let self_ty
= self.infcx
.shallow_resolve(obligation
.predicate
.skip_binder().self_ty());
2132 let types
= self.constituent_types_for_ty(self_ty
);
2133 self.vtable_default_impl(obligation
, trait_def_id
, ty
::Binder(types
))
2136 fn confirm_default_impl_object_candidate(&mut self,
2137 obligation
: &TraitObligation
<'tcx
>,
2138 trait_def_id
: ast
::DefId
)
2139 -> VtableDefaultImplData
<PredicateObligation
<'tcx
>>
2141 debug
!("confirm_default_impl_object_candidate({:?}, {:?})",
2145 assert
!(self.tcx().has_attr(trait_def_id
, "rustc_reflect_like"));
2147 // OK to skip binder, it is reintroduced below
2148 let self_ty
= self.infcx
.shallow_resolve(obligation
.predicate
.skip_binder().self_ty());
2150 ty
::TyTrait(ref data
) => {
2151 // OK to skip the binder, it is reintroduced below
2152 let input_types
= data
.principal
.skip_binder().substs
.types
.get_slice(TypeSpace
);
2153 let assoc_types
= data
.bounds
.projection_bounds
2155 .map(|pb
| pb
.skip_binder().ty
);
2156 let all_types
: Vec
<_
> = input_types
.iter().cloned()
2160 // reintroduce the two binding levels we skipped, then flatten into one
2161 let all_types
= ty
::Binder(ty
::Binder(all_types
));
2162 let all_types
= self.tcx().flatten_late_bound_regions(&all_types
);
2164 self.vtable_default_impl(obligation
, trait_def_id
, all_types
)
2167 self.tcx().sess
.bug(
2169 "asked to confirm default object implementation for non-object type: {:?}",
2175 /// See `confirm_default_impl_candidate`
2176 fn vtable_default_impl(&mut self,
2177 obligation
: &TraitObligation
<'tcx
>,
2178 trait_def_id
: ast
::DefId
,
2179 nested
: ty
::Binder
<Vec
<Ty
<'tcx
>>>)
2180 -> VtableDefaultImplData
<PredicateObligation
<'tcx
>>
2182 debug
!("vtable_default_impl_data: nested={:?}", nested
);
2184 let mut obligations
= self.collect_predicates_for_types(obligation
,
2188 let trait_obligations
: Result
<Vec
<_
>,()> = self.infcx
.commit_if_ok(|snapshot
| {
2189 let poly_trait_ref
= obligation
.predicate
.to_poly_trait_ref();
2190 let (trait_ref
, skol_map
) =
2191 self.infcx().skolemize_late_bound_regions(&poly_trait_ref
, snapshot
);
2192 Ok(self.impl_or_trait_obligations(obligation
.cause
.clone(),
2193 obligation
.recursion_depth
+ 1,
2200 // no Errors in that code above
2201 obligations
.append(&mut trait_obligations
.unwrap());
2203 debug
!("vtable_default_impl_data: obligations={:?}", obligations
);
2205 VtableDefaultImplData
{
2206 trait_def_id
: trait_def_id
,
2211 fn confirm_impl_candidate(&mut self,
2212 obligation
: &TraitObligation
<'tcx
>,
2213 impl_def_id
: ast
::DefId
)
2214 -> Result
<VtableImplData
<'tcx
, PredicateObligation
<'tcx
>>,
2215 SelectionError
<'tcx
>>
2217 debug
!("confirm_impl_candidate({:?},{:?})",
2221 // First, create the substitutions by matching the impl again,
2222 // this time not in a probe.
2223 self.infcx
.commit_if_ok(|snapshot
| {
2224 let (substs
, skol_map
) =
2225 self.rematch_impl(impl_def_id
, obligation
,
2227 debug
!("confirm_impl_candidate substs={:?}", substs
);
2228 Ok(self.vtable_impl(impl_def_id
, substs
, obligation
.cause
.clone(),
2229 obligation
.recursion_depth
+ 1, skol_map
, snapshot
))
2233 fn vtable_impl(&mut self,
2234 impl_def_id
: ast
::DefId
,
2235 mut substs
: Normalized
<'tcx
, Substs
<'tcx
>>,
2236 cause
: ObligationCause
<'tcx
>,
2237 recursion_depth
: usize,
2238 skol_map
: infer
::SkolemizationMap
,
2239 snapshot
: &infer
::CombinedSnapshot
)
2240 -> VtableImplData
<'tcx
, PredicateObligation
<'tcx
>>
2242 debug
!("vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={}, skol_map={:?})",
2248 let mut impl_obligations
=
2249 self.impl_or_trait_obligations(cause
,
2256 debug
!("vtable_impl: impl_def_id={:?} impl_obligations={:?}",
2260 impl_obligations
.append(&mut substs
.obligations
);
2262 VtableImplData
{ impl_def_id
: impl_def_id
,
2263 substs
: substs
.value
,
2264 nested
: impl_obligations
}
2267 fn confirm_object_candidate(&mut self,
2268 obligation
: &TraitObligation
<'tcx
>)
2269 -> VtableObjectData
<'tcx
>
2271 debug
!("confirm_object_candidate({:?})",
2274 // FIXME skipping binder here seems wrong -- we should
2275 // probably flatten the binder from the obligation and the
2276 // binder from the object. Have to try to make a broken test
2277 // case that results. -nmatsakis
2278 let self_ty
= self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder());
2279 let poly_trait_ref
= match self_ty
.sty
{
2280 ty
::TyTrait(ref data
) => {
2281 data
.principal_trait_ref_with_self_ty(self.tcx(), self_ty
)
2284 self.tcx().sess
.span_bug(obligation
.cause
.span
,
2285 "object candidate with non-object");
2289 let mut upcast_trait_ref
= None
;
2293 // We want to find the first supertrait in the list of
2294 // supertraits that we can unify with, and do that
2295 // unification. We know that there is exactly one in the list
2296 // where we can unify because otherwise select would have
2297 // reported an ambiguity. (When we do find a match, also
2298 // record it for later.)
2300 util
::supertraits(self.tcx(), poly_trait_ref
)
2303 self.infcx
.commit_if_ok(
2304 |_
| self.match_poly_trait_ref(obligation
, t
))
2306 Ok(_
) => { upcast_trait_ref = Some(t); false }
2311 // Additionally, for each of the nonmatching predicates that
2312 // we pass over, we sum up the set of number of vtable
2313 // entries, so that we can compute the offset for the selected
2316 nonmatching
.map(|t
| util
::count_own_vtable_entries(self.tcx(), t
))
2322 upcast_trait_ref
: upcast_trait_ref
.unwrap(),
2323 vtable_base
: vtable_base
,
2327 fn confirm_fn_pointer_candidate(&mut self,
2328 obligation
: &TraitObligation
<'tcx
>)
2329 -> Result
<ty
::Ty
<'tcx
>,SelectionError
<'tcx
>>
2331 debug
!("confirm_fn_pointer_candidate({:?})",
2334 // ok to skip binder; it is reintroduced below
2335 let self_ty
= self.infcx
.shallow_resolve(*obligation
.self_ty().skip_binder());
2336 let sig
= self_ty
.fn_sig();
2338 util
::closure_trait_ref_and_return_type(self.tcx(),
2339 obligation
.predicate
.def_id(),
2342 util
::TupleArgumentsFlag
::Yes
)
2343 .map_bound(|(trait_ref
, _
)| trait_ref
);
2345 try
!(self.confirm_poly_trait_refs(obligation
.cause
.clone(),
2346 obligation
.predicate
.to_poly_trait_ref(),
2351 fn confirm_closure_candidate(&mut self,
2352 obligation
: &TraitObligation
<'tcx
>,
2353 closure_def_id
: ast
::DefId
,
2354 substs
: &ty
::ClosureSubsts
<'tcx
>)
2355 -> Result
<VtableClosureData
<'tcx
, PredicateObligation
<'tcx
>>,
2356 SelectionError
<'tcx
>>
2358 debug
!("confirm_closure_candidate({:?},{:?},{:?})",
2366 } = self.closure_trait_ref(obligation
, closure_def_id
, substs
);
2368 debug
!("confirm_closure_candidate(closure_def_id={:?}, trait_ref={:?}, obligations={:?})",
2373 try
!(self.confirm_poly_trait_refs(obligation
.cause
.clone(),
2374 obligation
.predicate
.to_poly_trait_ref(),
2377 Ok(VtableClosureData
{
2378 closure_def_id
: closure_def_id
,
2379 substs
: substs
.clone(),
2384 /// In the case of closure types and fn pointers,
2385 /// we currently treat the input type parameters on the trait as
2386 /// outputs. This means that when we have a match we have only
2387 /// considered the self type, so we have to go back and make sure
2388 /// to relate the argument types too. This is kind of wrong, but
2389 /// since we control the full set of impls, also not that wrong,
2390 /// and it DOES yield better error messages (since we don't report
2391 /// errors as if there is no applicable impl, but rather report
2392 /// errors are about mismatched argument types.
2394 /// Here is an example. Imagine we have an closure expression
2395 /// and we desugared it so that the type of the expression is
2396 /// `Closure`, and `Closure` expects an int as argument. Then it
2397 /// is "as if" the compiler generated this impl:
2399 /// impl Fn(int) for Closure { ... }
2401 /// Now imagine our obligation is `Fn(usize) for Closure`. So far
2402 /// we have matched the self-type `Closure`. At this point we'll
2403 /// compare the `int` to `usize` and generate an error.
2405 /// Note that this checking occurs *after* the impl has selected,
2406 /// because these output type parameters should not affect the
2407 /// selection of the impl. Therefore, if there is a mismatch, we
2408 /// report an error to the user.
2409 fn confirm_poly_trait_refs(&mut self,
2410 obligation_cause
: ObligationCause
,
2411 obligation_trait_ref
: ty
::PolyTraitRef
<'tcx
>,
2412 expected_trait_ref
: ty
::PolyTraitRef
<'tcx
>)
2413 -> Result
<(), SelectionError
<'tcx
>>
2415 let origin
= infer
::RelateOutputImplTypes(obligation_cause
.span
);
2417 let obligation_trait_ref
= obligation_trait_ref
.clone();
2418 match self.infcx
.sub_poly_trait_refs(false,
2420 expected_trait_ref
.clone(),
2421 obligation_trait_ref
.clone()) {
2423 Err(e
) => Err(OutputTypeParameterMismatch(expected_trait_ref
, obligation_trait_ref
, e
))
2427 fn confirm_builtin_unsize_candidate(&mut self,
2428 obligation
: &TraitObligation
<'tcx
>,)
2429 -> Result
<VtableBuiltinData
<PredicateObligation
<'tcx
>>,
2430 SelectionError
<'tcx
>> {
2431 let tcx
= self.tcx();
2433 // assemble_candidates_for_unsizing should ensure there are no late bound
2434 // regions here. See the comment there for more details.
2435 let source
= self.infcx
.shallow_resolve(
2436 tcx
.no_late_bound_regions(&obligation
.self_ty()).unwrap());
2437 let target
= self.infcx
.shallow_resolve(obligation
.predicate
.0.input_types
()[0]);
2439 debug
!("confirm_builtin_unsize_candidate(source={:?}, target={:?})",
2442 let mut nested
= vec
![];
2443 match (&source
.sty
, &target
.sty
) {
2444 // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
2445 (&ty
::TyTrait(ref data_a
), &ty
::TyTrait(ref data_b
)) => {
2446 // See assemble_candidates_for_unsizing for more info.
2447 let bounds
= ty
::ExistentialBounds
{
2448 region_bound
: data_b
.bounds
.region_bound
,
2449 builtin_bounds
: data_b
.bounds
.builtin_bounds
,
2450 projection_bounds
: data_a
.bounds
.projection_bounds
.clone(),
2453 let new_trait
= tcx
.mk_trait(data_a
.principal
.clone(), bounds
);
2454 let origin
= infer
::Misc(obligation
.cause
.span
);
2455 if self.infcx
.sub_types(false, origin
, new_trait
, target
).is_err() {
2456 return Err(Unimplemented
);
2459 // Register one obligation for 'a: 'b.
2460 let cause
= ObligationCause
::new(obligation
.cause
.span
,
2461 obligation
.cause
.body_id
,
2462 ObjectCastObligation(target
));
2463 let outlives
= ty
::OutlivesPredicate(data_a
.bounds
.region_bound
,
2464 data_b
.bounds
.region_bound
);
2465 nested
.push(Obligation
::with_depth(cause
,
2466 obligation
.recursion_depth
+ 1,
2467 ty
::Binder(outlives
).to_predicate()));
2471 (_
, &ty
::TyTrait(ref data
)) => {
2472 let object_did
= data
.principal_def_id();
2473 if !object_safety
::is_object_safe(tcx
, object_did
) {
2474 return Err(TraitNotObjectSafe(object_did
));
2477 let cause
= ObligationCause
::new(obligation
.cause
.span
,
2478 obligation
.cause
.body_id
,
2479 ObjectCastObligation(target
));
2480 let mut push
= |predicate
| {
2481 nested
.push(Obligation
::with_depth(cause
.clone(),
2482 obligation
.recursion_depth
+ 1,
2486 // Create the obligation for casting from T to Trait.
2487 push(data
.principal_trait_ref_with_self_ty(tcx
, source
).to_predicate());
2489 // We can only make objects from sized types.
2490 let mut builtin_bounds
= data
.bounds
.builtin_bounds
;
2491 builtin_bounds
.insert(ty
::BoundSized
);
2493 // Create additional obligations for all the various builtin
2494 // bounds attached to the object cast. (In other words, if the
2495 // object type is Foo+Send, this would create an obligation
2496 // for the Send check.)
2497 for bound
in &builtin_bounds
{
2498 if let Ok(tr
) = util
::trait_ref_for_builtin_bound(tcx
, bound
, source
) {
2499 push(tr
.to_predicate());
2501 return Err(Unimplemented
);
2505 // Create obligations for the projection predicates.
2506 for bound
in data
.projection_bounds_with_self_ty(tcx
, source
) {
2507 push(bound
.to_predicate());
2510 // If the type is `Foo+'a`, ensures that the type
2511 // being cast to `Foo+'a` outlives `'a`:
2512 let outlives
= ty
::OutlivesPredicate(source
,
2513 data
.bounds
.region_bound
);
2514 push(ty
::Binder(outlives
).to_predicate());
2518 (&ty
::TyArray(a
, _
), &ty
::TySlice(b
)) => {
2519 let origin
= infer
::Misc(obligation
.cause
.span
);
2520 if self.infcx
.sub_types(false, origin
, a
, b
).is_err() {
2521 return Err(Unimplemented
);
2525 // Struct<T> -> Struct<U>.
2526 (&ty
::TyStruct(def_id
, substs_a
), &ty
::TyStruct(_
, substs_b
)) => {
2527 let fields
= tcx
.lookup_struct_fields(def_id
).iter().map(|f
| {
2528 tcx
.lookup_field_type_unsubstituted(def_id
, f
.id
)
2529 }).collect
::<Vec
<_
>>();
2531 // The last field of the structure has to exist and contain type parameters.
2532 let field
= if let Some(&field
) = fields
.last() {
2535 return Err(Unimplemented
);
2537 let mut ty_params
= vec
![];
2538 for ty
in field
.walk() {
2539 if let ty
::TyParam(p
) = ty
.sty
{
2540 assert
!(p
.space
== TypeSpace
);
2541 let idx
= p
.idx
as usize;
2542 if !ty_params
.contains(&idx
) {
2543 ty_params
.push(idx
);
2547 if ty_params
.is_empty() {
2548 return Err(Unimplemented
);
2551 // Replace type parameters used in unsizing with
2552 // TyError and ensure they do not affect any other fields.
2553 // This could be checked after type collection for any struct
2554 // with a potentially unsized trailing field.
2555 let mut new_substs
= substs_a
.clone();
2556 for &i
in &ty_params
{
2557 new_substs
.types
.get_mut_slice(TypeSpace
)[i
] = tcx
.types
.err
;
2559 for &ty
in fields
.split_last().unwrap().1 {
2560 if ty
.subst(tcx
, &new_substs
).references_error() {
2561 return Err(Unimplemented
);
2565 // Extract Field<T> and Field<U> from Struct<T> and Struct<U>.
2566 let inner_source
= field
.subst(tcx
, substs_a
);
2567 let inner_target
= field
.subst(tcx
, substs_b
);
2569 // Check that the source structure with the target's
2570 // type parameters is a subtype of the target.
2571 for &i
in &ty_params
{
2572 let param_b
= *substs_b
.types
.get(TypeSpace
, i
);
2573 new_substs
.types
.get_mut_slice(TypeSpace
)[i
] = param_b
;
2575 let new_struct
= tcx
.mk_struct(def_id
, tcx
.mk_substs(new_substs
));
2576 let origin
= infer
::Misc(obligation
.cause
.span
);
2577 if self.infcx
.sub_types(false, origin
, new_struct
, target
).is_err() {
2578 return Err(Unimplemented
);
2581 // Construct the nested Field<T>: Unsize<Field<U>> predicate.
2582 nested
.push(util
::predicate_for_trait_def(tcx
,
2583 obligation
.cause
.clone(),
2584 obligation
.predicate
.def_id(),
2585 obligation
.recursion_depth
+ 1,
2587 vec
![inner_target
]));
2593 Ok(VtableBuiltinData { nested: nested }
)
2596 ///////////////////////////////////////////////////////////////////////////
2599 // Matching is a common path used for both evaluation and
2600 // confirmation. It basically unifies types that appear in impls
2601 // and traits. This does affect the surrounding environment;
2602 // therefore, when used during evaluation, match routines must be
2603 // run inside of a `probe()` so that their side-effects are
2606 fn rematch_impl(&mut self,
2607 impl_def_id
: ast
::DefId
,
2608 obligation
: &TraitObligation
<'tcx
>,
2609 snapshot
: &infer
::CombinedSnapshot
)
2610 -> (Normalized
<'tcx
, Substs
<'tcx
>>, infer
::SkolemizationMap
)
2612 match self.match_impl(impl_def_id
, obligation
, snapshot
) {
2613 Ok((substs
, skol_map
)) => (substs
, skol_map
),
2615 self.tcx().sess
.bug(
2616 &format
!("Impl {:?} was matchable against {:?} but now is not",
2623 fn match_impl(&mut self,
2624 impl_def_id
: ast
::DefId
,
2625 obligation
: &TraitObligation
<'tcx
>,
2626 snapshot
: &infer
::CombinedSnapshot
)
2627 -> Result
<(Normalized
<'tcx
, Substs
<'tcx
>>,
2628 infer
::SkolemizationMap
), ()>
2630 let impl_trait_ref
= self.tcx().impl_trait_ref(impl_def_id
).unwrap();
2632 // Before we create the substitutions and everything, first
2633 // consider a "quick reject". This avoids creating more types
2634 // and so forth that we need to.
2635 if self.fast_reject_trait_refs(obligation
, &impl_trait_ref
) {
2639 let (skol_obligation
, skol_map
) = self.infcx().skolemize_late_bound_regions(
2640 &obligation
.predicate
,
2642 let skol_obligation_trait_ref
= skol_obligation
.trait_ref
;
2644 let impl_substs
= util
::fresh_type_vars_for_impl(self.infcx
,
2645 obligation
.cause
.span
,
2648 let impl_trait_ref
= impl_trait_ref
.subst(self.tcx(),
2651 let impl_trait_ref
=
2652 project
::normalize_with_depth(self,
2653 obligation
.cause
.clone(),
2654 obligation
.recursion_depth
+ 1,
2657 debug
!("match_impl(impl_def_id={:?}, obligation={:?}, \
2658 impl_trait_ref={:?}, skol_obligation_trait_ref={:?})",
2662 skol_obligation_trait_ref
);
2664 let origin
= infer
::RelateOutputImplTypes(obligation
.cause
.span
);
2665 if let Err(e
) = self.infcx
.sub_trait_refs(false,
2667 impl_trait_ref
.value
.clone(),
2668 skol_obligation_trait_ref
) {
2669 debug
!("match_impl: failed sub_trait_refs due to `{}`", e
);
2673 if let Err(e
) = self.infcx
.leak_check(&skol_map
, snapshot
) {
2674 debug
!("match_impl: failed leak check due to `{}`", e
);
2678 debug
!("match_impl: success impl_substs={:?}", impl_substs
);
2681 obligations
: impl_trait_ref
.obligations
2685 fn fast_reject_trait_refs(&mut self,
2686 obligation
: &TraitObligation
,
2687 impl_trait_ref
: &ty
::TraitRef
)
2690 // We can avoid creating type variables and doing the full
2691 // substitution if we find that any of the input types, when
2692 // simplified, do not match.
2694 obligation
.predicate
.0.input_types
().iter()
2695 .zip(impl_trait_ref
.input_types())
2696 .any(|(&obligation_ty
, &impl_ty
)| {
2697 let simplified_obligation_ty
=
2698 fast_reject
::simplify_type(self.tcx(), obligation_ty
, true);
2699 let simplified_impl_ty
=
2700 fast_reject
::simplify_type(self.tcx(), impl_ty
, false);
2702 simplified_obligation_ty
.is_some() &&
2703 simplified_impl_ty
.is_some() &&
2704 simplified_obligation_ty
!= simplified_impl_ty
2708 /// Normalize `where_clause_trait_ref` and try to match it against
2709 /// `obligation`. If successful, return any predicates that
2710 /// result from the normalization. Normalization is necessary
2711 /// because where-clauses are stored in the parameter environment
2713 fn match_where_clause_trait_ref(&mut self,
2714 obligation
: &TraitObligation
<'tcx
>,
2715 where_clause_trait_ref
: ty
::PolyTraitRef
<'tcx
>)
2716 -> Result
<Vec
<PredicateObligation
<'tcx
>>,()>
2718 try
!(self.match_poly_trait_ref(obligation
, where_clause_trait_ref
));
2722 /// Returns `Ok` if `poly_trait_ref` being true implies that the
2723 /// obligation is satisfied.
2724 fn match_poly_trait_ref(&self,
2725 obligation
: &TraitObligation
<'tcx
>,
2726 poly_trait_ref
: ty
::PolyTraitRef
<'tcx
>)
2729 debug
!("match_poly_trait_ref: obligation={:?} poly_trait_ref={:?}",
2733 let origin
= infer
::RelateOutputImplTypes(obligation
.cause
.span
);
2734 match self.infcx
.sub_poly_trait_refs(false,
2737 obligation
.predicate
.to_poly_trait_ref()) {
2743 /// Determines whether the self type declared against
2744 /// `impl_def_id` matches `obligation_self_ty`. If successful,
2745 /// returns the substitutions used to make them match. See
2746 /// `match_impl()`. For example, if `impl_def_id` is declared
2749 /// impl<T:Copy> Foo for Box<T> { ... }
2751 /// and `obligation_self_ty` is `int`, we'd get back an `Err(_)`
2752 /// result. But if `obligation_self_ty` were `Box<int>`, we'd get
2753 /// back `Ok(T=int)`.
2754 fn match_inherent_impl(&mut self,
2755 impl_def_id
: ast
::DefId
,
2756 obligation_cause
: &ObligationCause
,
2757 obligation_self_ty
: Ty
<'tcx
>)
2758 -> Result
<Substs
<'tcx
>,()>
2760 // Create fresh type variables for each type parameter declared
2762 let impl_substs
= util
::fresh_type_vars_for_impl(self.infcx
,
2763 obligation_cause
.span
,
2766 // Find the self type for the impl.
2767 let impl_self_ty
= self.tcx().lookup_item_type(impl_def_id
).ty
;
2768 let impl_self_ty
= impl_self_ty
.subst(self.tcx(), &impl_substs
);
2770 debug
!("match_impl_self_types(obligation_self_ty={:?}, impl_self_ty={:?})",
2774 match self.match_self_types(obligation_cause
,
2776 obligation_self_ty
) {
2778 debug
!("Matched impl_substs={:?}", impl_substs
);
2788 fn match_self_types(&mut self,
2789 cause
: &ObligationCause
,
2791 // The self type provided by the impl/caller-obligation:
2792 provided_self_ty
: Ty
<'tcx
>,
2794 // The self type the obligation is for:
2795 required_self_ty
: Ty
<'tcx
>)
2798 // FIXME(#5781) -- equating the types is stronger than
2799 // necessary. Should consider variance of trait w/r/t Self.
2801 let origin
= infer
::RelateSelfType(cause
.span
);
2802 match self.infcx
.eq_types(false,
2811 ///////////////////////////////////////////////////////////////////////////
2814 fn match_fresh_trait_refs(&self,
2815 previous
: &ty
::PolyTraitRef
<'tcx
>,
2816 current
: &ty
::PolyTraitRef
<'tcx
>)
2819 let mut matcher
= ty_match
::Match
::new(self.tcx());
2820 matcher
.relate(previous
, current
).is_ok()
2823 fn push_stack
<'o
,'s
:'o
>(&mut self,
2824 previous_stack
: TraitObligationStackList
<'s
, 'tcx
>,
2825 obligation
: &'o TraitObligation
<'tcx
>)
2826 -> TraitObligationStack
<'o
, 'tcx
>
2828 let fresh_trait_ref
=
2829 obligation
.predicate
.to_poly_trait_ref().fold_with(&mut self.freshener
);
2831 TraitObligationStack
{
2832 obligation
: obligation
,
2833 fresh_trait_ref
: fresh_trait_ref
,
2834 previous
: previous_stack
,
2838 fn closure_trait_ref_unnormalized(&mut self,
2839 obligation
: &TraitObligation
<'tcx
>,
2840 closure_def_id
: ast
::DefId
,
2841 substs
: &ty
::ClosureSubsts
<'tcx
>)
2842 -> ty
::PolyTraitRef
<'tcx
>
2844 let closure_type
= self.infcx
.closure_type(closure_def_id
, substs
);
2845 let ty
::Binder((trait_ref
, _
)) =
2846 util
::closure_trait_ref_and_return_type(self.tcx(),
2847 obligation
.predicate
.def_id(),
2848 obligation
.predicate
.0.self_ty(), // (1)
2850 util
::TupleArgumentsFlag
::No
);
2851 // (1) Feels icky to skip the binder here, but OTOH we know
2852 // that the self-type is an unboxed closure type and hence is
2853 // in fact unparameterized (or at least does not reference any
2854 // regions bound in the obligation). Still probably some
2855 // refactoring could make this nicer.
2857 ty
::Binder(trait_ref
)
2860 fn closure_trait_ref(&mut self,
2861 obligation
: &TraitObligation
<'tcx
>,
2862 closure_def_id
: ast
::DefId
,
2863 substs
: &ty
::ClosureSubsts
<'tcx
>)
2864 -> Normalized
<'tcx
, ty
::PolyTraitRef
<'tcx
>>
2866 let trait_ref
= self.closure_trait_ref_unnormalized(
2867 obligation
, closure_def_id
, substs
);
2869 // A closure signature can contain associated types which
2870 // must be normalized.
2871 normalize_with_depth(self,
2872 obligation
.cause
.clone(),
2873 obligation
.recursion_depth
+1,
2877 /// Returns the obligations that are implied by instantiating an
2878 /// impl or trait. The obligations are substituted and fully
2879 /// normalized. This is used when confirming an impl or default
2881 fn impl_or_trait_obligations(&mut self,
2882 cause
: ObligationCause
<'tcx
>,
2883 recursion_depth
: usize,
2884 def_id
: ast
::DefId
, // of impl or trait
2885 substs
: &Substs
<'tcx
>, // for impl or trait
2886 skol_map
: infer
::SkolemizationMap
,
2887 snapshot
: &infer
::CombinedSnapshot
)
2888 -> Vec
<PredicateObligation
<'tcx
>>
2890 debug
!("impl_or_trait_obligations(def_id={:?})", def_id
);
2892 let predicates
= self.tcx().lookup_predicates(def_id
);
2893 let predicates
= predicates
.instantiate(self.tcx(), substs
);
2894 let predicates
= normalize_with_depth(self, cause
.clone(), recursion_depth
, &predicates
);
2895 let mut predicates
= self.infcx().plug_leaks(skol_map
, snapshot
, &predicates
);
2896 let mut obligations
=
2897 util
::predicates_for_generics(cause
,
2900 obligations
.append(&mut predicates
.obligations
);
2904 #[allow(unused_comparisons)]
2905 fn derived_cause(&self,
2906 obligation
: &TraitObligation
<'tcx
>,
2907 variant
: fn(DerivedObligationCause
<'tcx
>) -> ObligationCauseCode
<'tcx
>)
2908 -> ObligationCause
<'tcx
>
2911 * Creates a cause for obligations that are derived from
2912 * `obligation` by a recursive search (e.g., for a builtin
2913 * bound, or eventually a `impl Foo for ..`). If `obligation`
2914 * is itself a derived obligation, this is just a clone, but
2915 * otherwise we create a "derived obligation" cause so as to
2916 * keep track of the original root obligation for error
2920 // NOTE(flaper87): As of now, it keeps track of the whole error
2921 // chain. Ideally, we should have a way to configure this either
2922 // by using -Z verbose or just a CLI argument.
2923 if obligation
.recursion_depth
>= 0 {
2924 let derived_cause
= DerivedObligationCause
{
2925 parent_trait_ref
: obligation
.predicate
.to_poly_trait_ref(),
2926 parent_code
: Rc
::new(obligation
.cause
.code
.clone()),
2928 ObligationCause
::new(obligation
.cause
.span
,
2929 obligation
.cause
.body_id
,
2930 variant(derived_cause
))
2932 obligation
.cause
.clone()
2937 impl<'tcx
> SelectionCache
<'tcx
> {
2938 pub fn new() -> SelectionCache
<'tcx
> {
2940 hashmap
: RefCell
::new(FnvHashMap())
2945 impl<'o
,'tcx
> TraitObligationStack
<'o
,'tcx
> {
2946 fn list(&'o
self) -> TraitObligationStackList
<'o
,'tcx
> {
2947 TraitObligationStackList
::with(self)
2950 fn iter(&'o
self) -> TraitObligationStackList
<'o
,'tcx
> {
2955 #[derive(Copy, Clone)]
2956 struct TraitObligationStackList
<'o
,'tcx
:'o
> {
2957 head
: Option
<&'o TraitObligationStack
<'o
,'tcx
>>
2960 impl<'o
,'tcx
> TraitObligationStackList
<'o
,'tcx
> {
2961 fn empty() -> TraitObligationStackList
<'o
,'tcx
> {
2962 TraitObligationStackList { head: None }
2965 fn with(r
: &'o TraitObligationStack
<'o
,'tcx
>) -> TraitObligationStackList
<'o
,'tcx
> {
2966 TraitObligationStackList { head: Some(r) }
2970 impl<'o
,'tcx
> Iterator
for TraitObligationStackList
<'o
,'tcx
>{
2971 type Item
= &'o TraitObligationStack
<'o
,'tcx
>;
2973 fn next(&mut self) -> Option
<&'o TraitObligationStack
<'o
,'tcx
>> {
2984 impl<'o
,'tcx
> fmt
::Debug
for TraitObligationStack
<'o
,'tcx
> {
2985 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
2986 write
!(f
, "TraitObligationStack({:?})", self.obligation
)
2990 impl<'tcx
> EvaluationResult
<'tcx
> {
2991 fn may_apply(&self) -> bool
{
2995 EvaluatedToErr(OutputTypeParameterMismatch(..)) |
2996 EvaluatedToErr(TraitNotObjectSafe(_
)) =>
2999 EvaluatedToErr(Unimplemented
) =>
3005 impl MethodMatchResult
{
3006 pub fn may_apply(&self) -> bool
{
3008 MethodMatched(_
) => true,
3009 MethodAmbiguous(_
) => true,
3010 MethodDidNotMatch
=> false,