1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 /*! See `doc.rs` for high-level documentation */
12 #![allow(dead_code)] // FIXME -- just temporarily
14 pub use self::MethodMatchResult::*;
15 pub use self::MethodMatchedData::*;
16 use self::Candidate::*;
17 use self::BuiltinBoundConditions::*;
18 use self::EvaluationResult::*;
20 use super::{Obligation, ObligationCause};
21 use super::{SelectionError, Unimplemented, Overflow,
22 OutputTypeParameterMismatch};
23 use super::{Selection};
24 use super::{SelectionResult};
25 use super::{VtableBuiltin, VtableImpl, VtableParam, VtableUnboxedClosure};
26 use super::{VtableImplData, VtableParamData, VtableBuiltinData};
29 use middle::fast_reject;
30 use middle::mem_categorization::Typer;
31 use middle::subst::{Subst, Substs, VecPerParamSpace};
32 use middle::ty::{mod, Ty};
33 use middle::typeck::infer;
34 use middle::typeck::infer::{InferCtxt, TypeSkolemizer};
35 use middle::ty_fold::TypeFoldable;
36 use std::cell::RefCell;
37 use std::collections::hash_map::HashMap;
40 use util::common::ErrorReported;
41 use util::ppaux::Repr;
43 pub struct SelectionContext<'cx, 'tcx:'cx> {
44 infcx: &'cx InferCtxt<'cx, 'tcx>,
45 param_env: &'cx ty::ParameterEnvironment<'tcx>,
46 typer: &'cx Typer<'tcx>+'cx,
48 /// Skolemizer used specifically for skolemizing entries on the
49 /// obligation stack. This ensures that all entries on the stack
50 /// at one time will have the same set of skolemized entries,
51 /// which is important for checking for trait bounds that
52 /// recursively require themselves.
53 skolemizer: TypeSkolemizer<'cx, 'tcx>,
55 /// If true, indicates that the evaluation should be conservative
56 /// and consider the possibility of types outside this crate.
57 /// This comes up primarily when resolving ambiguity. Imagine
58 /// there is some trait reference `$0 : Bar` where `$0` is an
59 /// inference variable. If `intercrate` is true, then we can never
60 /// say for sure that this reference is not implemented, even if
61 /// there are *no impls at all for `Bar`*, because `$0` could be
62 /// bound to some type that in a downstream crate that implements
63 /// `Bar`. This is the suitable mode for coherence. Elsewhere,
64 /// though, we set this to false, because we are only interested
65 /// in types that the user could actually have written --- in
66 /// other words, we consider `$0 : Bar` to be unimplemented if
67 /// there is no type that the user could *actually name* that
68 /// would satisfy it. This avoids crippling inference, basically.
72 // A stack that walks back up the stack frame.
73 struct ObligationStack<'prev, 'tcx: 'prev> {
74 obligation: &'prev Obligation<'tcx>,
76 /// Trait ref from `obligation` but skolemized with the
77 /// selection-context's skolemizer. Used to check for recursion.
78 skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
80 previous: Option<&'prev ObligationStack<'prev, 'tcx>>
83 pub struct SelectionCache<'tcx> {
84 hashmap: RefCell<HashMap<Rc<ty::TraitRef<'tcx>>,
85 SelectionResult<'tcx, Candidate<'tcx>>>>,
88 pub enum MethodMatchResult {
89 MethodMatched(MethodMatchedData),
90 MethodAmbiguous(/* list of impls that could apply */ Vec<ast::DefId>),
95 pub enum MethodMatchedData {
96 // In the case of a precise match, we don't really need to store
97 // how the match was found. So don't.
100 // In the case of a coercion, we need to know the precise impl so
101 // that we can determine the type to which things were coerced.
102 CoerciveMethodMatch(/* impl we matched */ ast::DefId)
106 * The selection process begins by considering all impls, where
107 * clauses, and so forth that might resolve an obligation. Sometimes
108 * we'll be able to say definitively that (e.g.) an impl does not
109 * apply to the obligation: perhaps it is defined for `uint` but the
110 * obligation is for `int`. In that case, we drop the impl out of the
111 * list. But the other cases are considered *candidates*.
113 * Candidates can either be definitive or ambiguous. An ambiguous
114 * candidate is one that might match or might not, depending on how
115 * type variables wind up being resolved. This only occurs during inference.
117 * For selection to suceed, there must be exactly one non-ambiguous
118 * candidate. Usually, it is not possible to have more than one
119 * definitive candidate, due to the coherence rules. However, there is
120 * one case where it could occur: if there is a blanket impl for a
121 * trait (that is, an impl applied to all T), and a type parameter
122 * with a where clause. In that case, we can have a candidate from the
123 * where clause and a second candidate from the impl. This is not a
124 * problem because coherence guarantees us that the impl which would
125 * be used to satisfy the where clause is the same one that we see
126 * now. To resolve this issue, therefore, we ignore impls if we find a
127 * matching where clause. Part of the reason for this is that where
128 * clauses can give additional information (like, the types of output
129 * parameters) that would have to be inferred from the impl.
131 #[deriving(PartialEq,Eq,Show,Clone)]
132 enum Candidate<'tcx> {
133 BuiltinCandidate(ty::BuiltinBound),
134 ParamCandidate(VtableParamData<'tcx>),
135 ImplCandidate(ast::DefId),
136 UnboxedClosureCandidate(/* closure */ ast::DefId, Substs<'tcx>),
140 struct CandidateSet<'tcx> {
141 vec: Vec<Candidate<'tcx>>,
145 enum BuiltinBoundConditions<'tcx> {
152 enum EvaluationResult {
158 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
159 pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>,
160 param_env: &'cx ty::ParameterEnvironment<'tcx>,
161 typer: &'cx Typer<'tcx>)
162 -> SelectionContext<'cx, 'tcx> {
165 param_env: param_env,
167 skolemizer: infcx.skolemizer(),
172 pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'tcx>,
173 param_env: &'cx ty::ParameterEnvironment<'tcx>,
174 typer: &'cx Typer<'tcx>)
175 -> SelectionContext<'cx, 'tcx> {
178 param_env: param_env,
180 skolemizer: infcx.skolemizer(),
185 pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
189 ///////////////////////////////////////////////////////////////////////////
192 // The selection phase tries to identify *how* an obligation will
193 // be resolved. For example, it will identify which impl or
194 // parameter bound is to be used. The process can be inconclusive
195 // if the self type in the obligation is not fully inferred. Selection
196 // can result in an error in one of two ways:
198 // 1. If no applicable impl or parameter bound can be found.
199 // 2. If the output type parameters in the obligation do not match
200 // those specified by the impl/bound. For example, if the obligation
201 // is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
202 // `impl<T> Iterable<T> for Vec<T>`, than an error would result.
204 pub fn select(&mut self, obligation: &Obligation<'tcx>)
205 -> SelectionResult<'tcx, Selection<'tcx>> {
207 * Evaluates whether the obligation can be satisfied. Returns
208 * an indication of whether the obligation can be satisfied
209 * and, if so, by what means. Never affects surrounding typing
213 debug!("select({})", obligation.repr(self.tcx()));
214 assert!(!obligation.trait_ref.has_escaping_regions());
216 let stack = self.push_stack(None, obligation);
217 match try!(self.candidate_from_obligation(&stack)) {
219 Some(candidate) => Ok(Some(try!(self.confirm_candidate(obligation, candidate)))),
223 pub fn select_inherent_impl(&mut self,
224 impl_def_id: ast::DefId,
225 obligation_cause: ObligationCause<'tcx>,
226 obligation_self_ty: Ty<'tcx>)
227 -> SelectionResult<'tcx, VtableImplData<'tcx, Obligation<'tcx>>>
229 debug!("select_inherent_impl(impl_def_id={}, obligation_self_ty={})",
230 impl_def_id.repr(self.tcx()),
231 obligation_self_ty.repr(self.tcx()));
233 match self.match_inherent_impl(impl_def_id,
235 obligation_self_ty) {
237 let vtable_impl = self.vtable_impl(impl_def_id, substs, obligation_cause, 0);
238 Ok(Some(vtable_impl))
246 ///////////////////////////////////////////////////////////////////////////
249 // Tests whether an obligation can be selected or whether an impl
250 // can be applied to particular types. It skips the "confirmation"
251 // step and hence completely ignores output type parameters.
253 // The result is "true" if the obligation *may* hold and "false" if
254 // we can be sure it does not.
256 pub fn evaluate_obligation(&mut self,
257 obligation: &Obligation<'tcx>)
261 * Evaluates whether the obligation `obligation` can be
262 * satisfied (by any means).
265 debug!("evaluate_obligation({})",
266 obligation.repr(self.tcx()));
267 assert!(!obligation.trait_ref.has_escaping_regions());
269 let stack = self.push_stack(None, obligation);
270 self.evaluate_stack(&stack).may_apply()
273 fn evaluate_builtin_bound_recursively<'o>(&mut self,
274 bound: ty::BuiltinBound,
275 previous_stack: &ObligationStack<'o, 'tcx>,
280 util::obligation_for_builtin_bound(
282 previous_stack.obligation.cause,
284 previous_stack.obligation.recursion_depth + 1,
289 self.evaluate_obligation_recursively(Some(previous_stack), &obligation)
291 Err(ErrorReported) => {
297 fn evaluate_obligation_recursively<'o>(&mut self,
298 previous_stack: Option<&ObligationStack<'o, 'tcx>>,
299 obligation: &Obligation<'tcx>)
302 debug!("evaluate_obligation_recursively({})",
303 obligation.repr(self.tcx()));
305 let stack = self.push_stack(previous_stack.map(|x| x), obligation);
307 let result = self.evaluate_stack(&stack);
309 debug!("result: {}", result);
313 fn evaluate_stack<'o>(&mut self,
314 stack: &ObligationStack<'o, 'tcx>)
317 // In intercrate mode, whenever any of the types are unbound,
318 // there can always be an impl. Even if there are no impls in
319 // this crate, perhaps the type would be unified with
320 // something from another crate that does provide an impl.
322 // In intracrate mode, we must still be conservative. The reason is
323 // that we want to avoid cycles. Imagine an impl like:
325 // impl<T:Eq> Eq for Vec<T>
327 // and a trait reference like `$0 : Eq` where `$0` is an
328 // unbound variable. When we evaluate this trait-reference, we
329 // will unify `$0` with `Vec<$1>` (for some fresh variable
330 // `$1`), on the condition that `$1 : Eq`. We will then wind
331 // up with many candidates (since that are other `Eq` impls
332 // that apply) and try to winnow things down. This results in
333 // a recurssive evaluation that `$1 : Eq` -- as you can
334 // imagine, this is just where we started. To avoid that, we
335 // check for unbound variables and return an ambiguous (hence possible)
336 // match if we've seen this trait before.
338 // This suffices to allow chains like `FnMut` implemented in
339 // terms of `Fn` etc, but we could probably make this more
341 let input_types = stack.skol_trait_ref.input_types();
342 let unbound_input_types = input_types.iter().any(|&t| ty::type_is_skolemized(t));
344 unbound_input_types &&
346 stack.iter().skip(1).any(
347 |prev| stack.skol_trait_ref.def_id == prev.skol_trait_ref.def_id))
349 debug!("evaluate_stack_intracrate({}) --> unbound argument, recursion --> ambiguous",
350 stack.skol_trait_ref.repr(self.tcx()));
351 return EvaluatedToAmbig;
354 // If there is any previous entry on the stack that precisely
355 // matches this obligation, then we can assume that the
356 // obligation is satisfied for now (still all other conditions
357 // must be met of course). One obvious case this comes up is
358 // marker traits like `Send`. Think of a linked list:
360 // struct List<T> { data: T, next: Option<Box<List<T>>> {
362 // `Box<List<T>>` will be `Send` if `T` is `Send` and
363 // `Option<Box<List<T>>>` is `Send`, and in turn
364 // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
367 // Note that we do this comparison using the `skol_trait_ref`
368 // fields. Because these have all been skolemized using
369 // `self.skolemizer`, we can be sure that (a) this will not
370 // affect the inferencer state and (b) that if we see two
371 // skolemized types with the same index, they refer to the
372 // same unbound type variable.
375 .skip(1) // skip top-most frame
376 .any(|prev| stack.skol_trait_ref == prev.skol_trait_ref)
378 debug!("evaluate_stack_intracrate({}) --> recursive",
379 stack.skol_trait_ref.repr(self.tcx()));
380 return EvaluatedToOk;
383 match self.candidate_from_obligation(stack) {
384 Ok(Some(c)) => self.winnow_candidate(stack, &c),
385 Ok(None) => EvaluatedToAmbig,
386 Err(_) => EvaluatedToErr,
390 pub fn evaluate_impl(&mut self,
391 impl_def_id: ast::DefId,
392 obligation: &Obligation<'tcx>)
396 * Evaluates whether the impl with id `impl_def_id` could be
397 * applied to the self type `obligation_self_ty`. This can be
398 * used either for trait or inherent impls.
401 debug!("evaluate_impl(impl_def_id={}, obligation={})",
402 impl_def_id.repr(self.tcx()),
403 obligation.repr(self.tcx()));
405 self.infcx.probe(|| {
406 match self.match_impl(impl_def_id, obligation) {
408 let vtable_impl = self.vtable_impl(impl_def_id,
411 obligation.recursion_depth + 1);
412 self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
421 ///////////////////////////////////////////////////////////////////////////
424 // Method matching is a variation on the normal select/evaluation
425 // situation. In this scenario, rather than having a full trait
426 // reference to select from, we start with an expression like
427 // `receiver.method(...)`. This means that we have `rcvr_ty`, the
428 // type of the receiver, and we have a possible trait that
429 // supplies `method`. We must determine whether the receiver is
430 // applicable, taking into account the transformed self type
431 // declared on `method`. We also must consider the possibility
432 // that `receiver` can be *coerced* into a suitable type (for
433 // example, a receiver type like `&(Any+Send)` might be coerced
434 // into a receiver like `&Any` to allow for method dispatch). See
435 // the body of `evaluate_method_obligation()` for more details on
438 pub fn evaluate_method_obligation(&mut self,
440 xform_self_ty: Ty<'tcx>,
441 obligation: &Obligation<'tcx>)
445 * Determine whether a trait-method is applicable to a receiver of
446 * type `rcvr_ty`. *Does not affect the inference state.*
448 * - `rcvr_ty` -- type of the receiver
449 * - `xform_self_ty` -- transformed self type declared on the method, with `Self`
450 * to a fresh type variable
451 * - `obligation` -- a reference to the trait where the method is declared, with
452 * the input types on the trait replaced with fresh type variables
455 // Here is the situation. We have a trait method declared (say) like so:
458 // fn the_method(self: Rc<Self>, ...) { ... }
461 // And then we have a call looking (say) like this:
463 // let x: Rc<Foo> = ...;
466 // Now we want to decide if `TheTrait` is applicable. As a
467 // human, we can see that `TheTrait` is applicable if there is
468 // an impl for the type `Foo`. But how does the compiler know
469 // what impl to look for, given that our receiver has type
470 // `Rc<Foo>`? We need to take the method's self type into
473 // On entry to this function, we have the following inputs:
475 // - `rcvr_ty = Rc<Foo>`
476 // - `xform_self_ty = Rc<$0>`
477 // - `obligation = $0 as TheTrait`
479 // We do the match in two phases. The first is a *precise
480 // match*, which means that no coercion is required. This is
481 // the preferred way to match. It works by first making
482 // `rcvr_ty` a subtype of `xform_self_ty`. This unifies `$0`
483 // and `Foo`. We can then evaluate (roughly as normal) the
484 // trait reference `Foo as TheTrait`.
486 // If this fails, we fallback to a coercive match, described below.
488 match self.infcx.probe(|| self.match_method_precise(rcvr_ty, xform_self_ty, obligation)) {
489 Ok(()) => { return MethodMatched(PreciseMethodMatch); }
493 // Coercive matches work slightly differently and cannot
494 // completely reuse the normal trait matching machinery
495 // (though they employ many of the same bits and pieces). To
496 // see how it works, let's continue with our previous example,
497 // but with the following declarations:
500 // trait Foo : Bar { .. }
501 // trait Bar : Baz { ... }
503 // impl TheTrait for Bar {
504 // fn the_method(self: Rc<Bar>, ...) { ... }
508 // Now we see that the receiver type `Rc<Foo>` is actually an
509 // object type. And in fact the impl we want is an impl on the
510 // supertrait `Rc<Bar>`. The precise matching procedure won't
511 // find it, however, because `Rc<Foo>` is not a subtype of
512 // `Rc<Bar>` -- it is *coercible* to `Rc<Bar>` (actually, such
513 // coercions are not yet implemented, but let's leave that
516 // To handle this case, we employ a different procedure. Recall
517 // that our initial state is as follows:
519 // - `rcvr_ty = Rc<Foo>`
520 // - `xform_self_ty = Rc<$0>`
521 // - `obligation = $0 as TheTrait`
523 // We now go through each impl and instantiate all of its type
524 // variables, yielding the trait reference that the impl
525 // provides. In our example, the impl would provide `Bar as
526 // TheTrait`. Next we (try to) unify the trait reference that
527 // the impl provides with the input obligation. This would
528 // unify `$0` and `Bar`. Now we can see whether the receiver
529 // type (`Rc<Foo>`) is *coercible to* the transformed self
530 // type (`Rc<$0> == Rc<Bar>`). In this case, the answer is
531 // yes, so the impl is considered a candidate.
533 // Note that there is the possibility of ambiguity here, even
534 // when all types are known. In our example, this might occur
535 // if there was *also* an impl of `TheTrait` for `Baz`. In
536 // this case, `Rc<Foo>` would be coercible to both `Rc<Bar>`
537 // and `Rc<Baz>`. (Note that it is not a *coherence violation*
538 // to have impls for both `Bar` and `Baz`, despite this
539 // ambiguity). In this case, we report an error, listing all
540 // the applicable impls. The user can explicitly "up-coerce"
541 // to the type they want.
543 // Note that this coercion step only considers actual impls
544 // found in the source. This is because all the
545 // compiler-provided impls (such as those for unboxed
546 // closures) do not have relevant coercions. This simplifies
550 self.assemble_method_candidates_from_impls(rcvr_ty, xform_self_ty, obligation);
553 impls.retain(|&c| self.winnow_method_impl(c, rcvr_ty, xform_self_ty, obligation));
557 return MethodAmbiguous(impls);
561 Some(def_id) => MethodMatched(CoerciveMethodMatch(def_id)),
562 None => MethodDidNotMatch
566 pub fn confirm_method_match(&mut self,
568 xform_self_ty: Ty<'tcx>,
569 obligation: &Obligation<'tcx>,
570 data: MethodMatchedData)
573 * Given the successful result of a method match, this
574 * function "confirms" the result, which basically repeats the
575 * various matching operations, but outside of any snapshot so
576 * that their effects are committed into the inference state.
579 let is_ok = match data {
580 PreciseMethodMatch => {
581 self.match_method_precise(rcvr_ty, xform_self_ty, obligation).is_ok()
584 CoerciveMethodMatch(impl_def_id) => {
585 self.match_method_coerce(impl_def_id, rcvr_ty, xform_self_ty, obligation).is_ok()
590 self.tcx().sess.span_bug(
591 obligation.cause.span,
592 format!("match not repeatable: {}, {}, {}, {}",
593 rcvr_ty.repr(self.tcx()),
594 xform_self_ty.repr(self.tcx()),
595 obligation.repr(self.tcx()),
600 fn match_method_precise(&mut self,
602 xform_self_ty: Ty<'tcx>,
603 obligation: &Obligation<'tcx>)
607 * Implements the *precise method match* procedure described in
608 * `evaluate_method_obligation()`.
611 self.infcx.commit_if_ok(|| {
612 match self.infcx.sub_types(false, infer::RelateSelfType(obligation.cause.span),
613 rcvr_ty, xform_self_ty) {
615 Err(_) => { return Err(()); }
618 if self.evaluate_obligation(obligation) {
626 fn assemble_method_candidates_from_impls(&mut self,
628 xform_self_ty: Ty<'tcx>,
629 obligation: &Obligation<'tcx>)
633 * Assembles a list of potentially applicable impls using the
634 * *coercive match* procedure described in
635 * `evaluate_method_obligation()`.
638 let mut candidates = Vec::new();
640 let all_impls = self.all_impls(obligation.trait_ref.def_id);
641 for &impl_def_id in all_impls.iter() {
642 self.infcx.probe(|| {
643 match self.match_method_coerce(impl_def_id, rcvr_ty, xform_self_ty, obligation) {
644 Ok(_) => { candidates.push(impl_def_id); }
653 fn match_method_coerce(&mut self,
654 impl_def_id: ast::DefId,
656 xform_self_ty: Ty<'tcx>,
657 obligation: &Obligation<'tcx>)
658 -> Result<Substs<'tcx>, ()>
661 * Applies the *coercive match* procedure described in
662 * `evaluate_method_obligation()` to a particular impl.
665 // This is almost always expected to succeed. It
666 // causes the impl's self-type etc to be unified with
667 // the type variable that is shared between
668 // obligation/xform_self_ty. In our example, after
669 // this is done, the type of `xform_self_ty` would
670 // change from `Rc<$0>` to `Rc<Foo>` (because $0 is
671 // unified with `Foo`).
672 let substs = try!(self.match_impl(impl_def_id, obligation));
674 // Next, check whether we can coerce. For now we require
675 // that the coercion be a no-op.
676 let origin = infer::Misc(obligation.cause.span);
677 match infer::mk_coercety(self.infcx, true, origin,
678 rcvr_ty, xform_self_ty) {
679 Ok(None) => { /* Fallthrough */ }
680 Ok(Some(_)) | Err(_) => { return Err(()); }
686 fn winnow_method_impl(&mut self,
687 impl_def_id: ast::DefId,
689 xform_self_ty: Ty<'tcx>,
690 obligation: &Obligation<'tcx>)
694 * A version of `winnow_impl` applicable to coerice method
695 * matching. This is basically the same as `winnow_impl` but
696 * it uses the method matching procedure and is specific to
700 debug!("winnow_method_impl: impl_def_id={} rcvr_ty={} xform_self_ty={} obligation={}",
701 impl_def_id.repr(self.tcx()),
702 rcvr_ty.repr(self.tcx()),
703 xform_self_ty.repr(self.tcx()),
704 obligation.repr(self.tcx()));
706 self.infcx.probe(|| {
707 match self.match_method_coerce(impl_def_id, rcvr_ty, xform_self_ty, obligation) {
709 let vtable_impl = self.vtable_impl(impl_def_id,
712 obligation.recursion_depth + 1);
713 self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
722 ///////////////////////////////////////////////////////////////////////////
723 // CANDIDATE ASSEMBLY
725 // The selection process begins by examining all in-scope impls,
726 // caller obligations, and so forth and assembling a list of
727 // candidates. See `doc.rs` and the `Candidate` type for more details.
729 fn candidate_from_obligation<'o>(&mut self,
730 stack: &ObligationStack<'o, 'tcx>)
731 -> SelectionResult<'tcx, Candidate<'tcx>>
733 // Watch out for overflow. This intentionally bypasses (and does
734 // not update) the cache.
735 let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
736 if stack.obligation.recursion_depth >= recursion_limit {
737 debug!("{} --> overflow (limit={})",
738 stack.obligation.repr(self.tcx()),
743 // Check the cache. Note that we skolemize the trait-ref
744 // separately rather than using `stack.skol_trait_ref` -- this
745 // is because we want the unbound variables to be replaced
746 // with fresh skolemized types starting from index 0.
747 let cache_skol_trait_ref =
748 self.infcx.skolemize(stack.obligation.trait_ref.clone());
749 debug!("candidate_from_obligation(cache_skol_trait_ref={}, obligation={})",
750 cache_skol_trait_ref.repr(self.tcx()),
751 stack.repr(self.tcx()));
752 assert!(!stack.obligation.trait_ref.has_escaping_regions());
754 match self.check_candidate_cache(cache_skol_trait_ref.clone()) {
756 debug!("CACHE HIT: cache_skol_trait_ref={}, candidate={}",
757 cache_skol_trait_ref.repr(self.tcx()),
764 // If no match, compute result and insert into cache.
765 let candidate = self.candidate_from_obligation_no_cache(stack);
766 debug!("CACHE MISS: cache_skol_trait_ref={}, candidate={}",
767 cache_skol_trait_ref.repr(self.tcx()), candidate.repr(self.tcx()));
768 self.insert_candidate_cache(cache_skol_trait_ref, candidate.clone());
772 fn candidate_from_obligation_no_cache<'o>(&mut self,
773 stack: &ObligationStack<'o, 'tcx>)
774 -> SelectionResult<'tcx, Candidate<'tcx>>
776 if ty::type_is_error(stack.obligation.self_ty()) {
777 return Ok(Some(ErrorCandidate));
780 let candidate_set = try!(self.assemble_candidates(stack));
782 if candidate_set.ambiguous {
783 debug!("candidate set contains ambig");
787 let mut candidates = candidate_set.vec;
789 debug!("assembled {} candidates for {}",
790 candidates.len(), stack.repr(self.tcx()));
792 // At this point, we know that each of the entries in the
793 // candidate set is *individually* applicable. Now we have to
794 // figure out if they contain mutual incompatibilities. This
795 // frequently arises if we have an unconstrained input type --
796 // for example, we are looking for $0:Eq where $0 is some
797 // unconstrained type variable. In that case, we'll get a
798 // candidate which assumes $0 == int, one that assumes $0 ==
799 // uint, etc. This spells an ambiguity.
801 // If there is more than one candidate, first winnow them down
802 // by considering extra conditions (nested obligations and so
803 // forth). We don't winnow if there is exactly one
804 // candidate. This is a relatively minor distinction but it
805 // can lead to better inference and error-reporting. An
806 // example would be if there was an impl:
808 // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
810 // and we were to see some code `foo.push_clone()` where `boo`
811 // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
812 // we were to winnow, we'd wind up with zero candidates.
813 // Instead, we select the right impl now but report `Bar does
814 // not implement Clone`.
815 if candidates.len() > 1 {
816 candidates.retain(|c| self.winnow_candidate(stack, c).may_apply())
819 // If there are STILL multiple candidate, we can further reduce
820 // the list by dropping duplicates.
821 if candidates.len() > 1 {
823 while i < candidates.len() {
825 range(0, candidates.len())
827 .any(|j| self.candidate_should_be_dropped_in_favor_of(stack,
831 debug!("Dropping candidate #{}/{}: {}",
832 i, candidates.len(), candidates[i].repr(self.tcx()));
833 candidates.swap_remove(i);
835 debug!("Retaining candidate #{}/{}: {}",
836 i, candidates.len(), candidates[i].repr(self.tcx()));
842 // If there are *STILL* multiple candidates, give up and
843 // report ambiguiuty.
844 if candidates.len() > 1 {
845 debug!("multiple matches, ambig");
849 // If there are *NO* candidates, that there are no impls --
850 // that we know of, anyway. Note that in the case where there
851 // are unbound type variables within the obligation, it might
852 // be the case that you could still satisfy the obligation
853 // from another crate by instantiating the type variables with
854 // a type from another crate that does have an impl. This case
855 // is checked for in `evaluate_stack` (and hence users
856 // who might care about this case, like coherence, should use
858 if candidates.len() == 0 {
859 return Err(Unimplemented);
862 // Just one candidate left.
863 let candidate = candidates.pop().unwrap();
867 fn pick_candidate_cache(&self,
868 cache_skol_trait_ref: &Rc<ty::TraitRef<'tcx>>)
869 -> &SelectionCache<'tcx>
871 // High-level idea: we have to decide whether to consult the
872 // cache that is specific to this scope, or to consult the
873 // global cache. We want the cache that is specific to this
874 // scope whenever where clauses might affect the result.
876 // Avoid using the master cache during coherence and just rely
877 // on the local cache. This effectively disables caching
878 // during coherence. It is really just a simplification to
879 // avoid us having to fear that coherence results "pollute"
880 // the master cache. Since coherence executes pretty quickly,
881 // it's not worth going to more trouble to increase the
882 // hit-rate I don't think.
884 return &self.param_env.selection_cache;
887 // If the trait refers to any parameters in scope, then use
888 // the cache of the param-environment.
890 cache_skol_trait_ref.input_types().iter().any(
891 |&t| ty::type_has_self(t) || ty::type_has_params(t))
893 return &self.param_env.selection_cache;
896 // If the trait refers to unbound type variables, and there
897 // are where clauses in scope, then use the local environment.
898 // If there are no where clauses in scope, which is a very
899 // common case, then we can use the global environment.
900 // See the discussion in doc.rs for more details.
902 !self.param_env.caller_obligations.is_empty()
904 cache_skol_trait_ref.input_types().iter().any(
905 |&t| ty::type_has_ty_infer(t))
907 return &self.param_env.selection_cache;
910 // Otherwise, we can use the global cache.
911 &self.tcx().selection_cache
914 fn check_candidate_cache(&mut self,
915 cache_skol_trait_ref: Rc<ty::TraitRef<'tcx>>)
916 -> Option<SelectionResult<'tcx, Candidate<'tcx>>>
918 let cache = self.pick_candidate_cache(&cache_skol_trait_ref);
919 let hashmap = cache.hashmap.borrow();
920 hashmap.get(&cache_skol_trait_ref).map(|c| (*c).clone())
923 fn insert_candidate_cache(&mut self,
924 cache_skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
925 candidate: SelectionResult<'tcx, Candidate<'tcx>>)
927 let cache = self.pick_candidate_cache(&cache_skol_trait_ref);
928 let mut hashmap = cache.hashmap.borrow_mut();
929 hashmap.insert(cache_skol_trait_ref, candidate);
932 fn assemble_candidates<'o>(&mut self,
933 stack: &ObligationStack<'o, 'tcx>)
934 -> Result<CandidateSet<'tcx>, SelectionError<'tcx>>
936 // Check for overflow.
938 let ObligationStack { obligation, .. } = *stack;
940 let mut candidates = CandidateSet {
945 // Other bounds. Consider both in-scope bounds from fn decl
946 // and applicable impls. There is a certain set of precedence rules here.
948 match self.tcx().lang_items.to_builtin_kind(obligation.trait_ref.def_id) {
950 try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
954 // For the time being, we ignore user-defined impls for builtin-bounds.
955 // (And unboxed candidates only apply to the Fn/FnMut/etc traits.)
956 try!(self.assemble_unboxed_candidates(obligation, &mut candidates));
957 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
961 try!(self.assemble_candidates_from_caller_bounds(obligation, &mut candidates));
965 fn assemble_candidates_from_caller_bounds(&mut self,
966 obligation: &Obligation<'tcx>,
967 candidates: &mut CandidateSet<'tcx>)
968 -> Result<(),SelectionError<'tcx>>
971 * Given an obligation like `<SomeTrait for T>`, search the obligations
972 * that the caller supplied to find out whether it is listed among
975 * Never affects inference environment.
978 debug!("assemble_candidates_from_caller_bounds({})",
979 obligation.repr(self.tcx()));
981 let caller_trait_refs: Vec<Rc<ty::TraitRef>> =
982 self.param_env.caller_obligations.iter()
983 .map(|o| o.trait_ref.clone())
987 util::transitive_bounds(
988 self.tcx(), caller_trait_refs.as_slice());
990 let matching_bounds =
992 |bound| self.infcx.probe(
993 || self.match_trait_refs(obligation,
994 (*bound).clone())).is_ok());
996 let param_candidates =
998 |bound| ParamCandidate(VtableParamData { bound: bound }));
1000 candidates.vec.extend(param_candidates);
1005 fn assemble_unboxed_candidates(&mut self,
1006 obligation: &Obligation<'tcx>,
1007 candidates: &mut CandidateSet<'tcx>)
1008 -> Result<(),SelectionError<'tcx>>
1011 * Check for the artificial impl that the compiler will create
1012 * for an obligation like `X : FnMut<..>` where `X` is an
1013 * unboxed closure type.
1015 * Note: the type parameters on an unboxed closure candidate
1016 * are modeled as *output* type parameters and hence do not
1017 * affect whether this trait is a match or not. They will be
1018 * unified during the confirmation step.
1021 let tcx = self.tcx();
1022 let kind = if Some(obligation.trait_ref.def_id) == tcx.lang_items.fn_trait() {
1023 ty::FnUnboxedClosureKind
1024 } else if Some(obligation.trait_ref.def_id) == tcx.lang_items.fn_mut_trait() {
1025 ty::FnMutUnboxedClosureKind
1026 } else if Some(obligation.trait_ref.def_id) == tcx.lang_items.fn_once_trait() {
1027 ty::FnOnceUnboxedClosureKind
1029 return Ok(()); // not a fn trait, ignore
1032 let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1033 let (closure_def_id, substs) = match self_ty.sty {
1034 ty::ty_unboxed_closure(id, _, ref substs) => (id, substs.clone()),
1035 ty::ty_infer(ty::TyVar(_)) => {
1036 candidates.ambiguous = true;
1039 _ => { return Ok(()); }
1042 debug!("assemble_unboxed_candidates: self_ty={} obligation={}",
1043 self_ty.repr(self.tcx()),
1044 obligation.repr(self.tcx()));
1046 let closure_kind = match self.typer.unboxed_closures().borrow().get(&closure_def_id) {
1047 Some(closure) => closure.kind,
1049 self.tcx().sess.span_bug(
1050 obligation.cause.span,
1051 format!("No entry for unboxed closure: {}",
1052 closure_def_id.repr(self.tcx())).as_slice());
1056 if closure_kind == kind {
1057 candidates.vec.push(UnboxedClosureCandidate(closure_def_id, substs.clone()));
1063 fn assemble_candidates_from_impls(&mut self,
1064 obligation: &Obligation<'tcx>,
1065 candidates: &mut CandidateSet<'tcx>)
1066 -> Result<(), SelectionError<'tcx>>
1069 * Search for impls that might apply to `obligation`.
1072 let all_impls = self.all_impls(obligation.trait_ref.def_id);
1073 for &impl_def_id in all_impls.iter() {
1074 self.infcx.probe(|| {
1075 match self.match_impl(impl_def_id, obligation) {
1077 candidates.vec.push(ImplCandidate(impl_def_id));
1086 ///////////////////////////////////////////////////////////////////////////
1089 // Winnowing is the process of attempting to resolve ambiguity by
1090 // probing further. During the winnowing process, we unify all
1091 // type variables (ignoring skolemization) and then we also
1092 // attempt to evaluate recursive bounds to see if they are
1095 fn winnow_candidate<'o>(&mut self,
1096 stack: &ObligationStack<'o, 'tcx>,
1097 candidate: &Candidate<'tcx>)
1101 * Further evaluate `candidate` to decide whether all type parameters match
1102 * and whether nested obligations are met. Returns true if `candidate` remains
1103 * viable after this further scrutiny.
1106 debug!("winnow_candidate: candidate={}", candidate.repr(self.tcx()));
1107 self.infcx.probe(|| {
1108 let candidate = (*candidate).clone();
1109 match self.confirm_candidate(stack.obligation, candidate) {
1110 Ok(selection) => self.winnow_selection(Some(stack), selection),
1111 Err(_) => EvaluatedToErr,
1116 fn winnow_selection<'o>(&mut self,
1117 stack: Option<&ObligationStack<'o, 'tcx>>,
1118 selection: Selection<'tcx>)
1121 let mut result = EvaluatedToOk;
1122 for obligation in selection.iter_nested() {
1123 match self.evaluate_obligation_recursively(stack, obligation) {
1124 EvaluatedToErr => { return EvaluatedToErr; }
1125 EvaluatedToAmbig => { result = EvaluatedToAmbig; }
1126 EvaluatedToOk => { }
1132 fn candidate_should_be_dropped_in_favor_of<'o>(&mut self,
1133 stack: &ObligationStack<'o, 'tcx>,
1134 candidate_i: &Candidate<'tcx>,
1135 candidate_j: &Candidate<'tcx>)
1139 * Returns true if `candidate_i` should be dropped in favor of `candidate_j`.
1140 * This is generally true if either:
1141 * - candidate i and candidate j are equivalent; or,
1142 * - candidate i is a conrete impl and candidate j is a where clause bound,
1143 * and the concrete impl is applicable to the types in the where clause bound.
1145 * The last case refers to cases where there are blanket impls (often conditional
1146 * blanket impls) as well as a where clause. This can come down to one of two cases:
1148 * - The impl is truly unconditional (it has no where clauses
1149 * of its own), in which case the where clause is
1150 * unnecessary, because coherence requires that we would
1151 * pick that particular impl anyhow (at least so long as we
1152 * don't have specialization).
1154 * - The impl is conditional, in which case we may not have winnowed it out
1155 * because we don't know if the conditions apply, but the where clause is basically
1156 * telling us taht there is some impl, though not necessarily the one we see.
1158 * In both cases we prefer to take the where clause, which is
1159 * essentially harmless. See issue #18453 for more details of
1160 * a case where doing the opposite caused us harm.
1163 match (candidate_i, candidate_j) {
1164 (&ImplCandidate(impl_def_id), &ParamCandidate(ref vt)) => {
1165 debug!("Considering whether to drop param {} in favor of impl {}",
1166 candidate_i.repr(self.tcx()),
1167 candidate_j.repr(self.tcx()));
1169 self.infcx.probe(|| {
1171 self.rematch_impl(impl_def_id, stack.obligation);
1172 let impl_trait_ref =
1173 ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
1174 let impl_trait_ref =
1175 impl_trait_ref.subst(self.tcx(), &impl_substs);
1177 infer::RelateOutputImplTypes(stack.obligation.cause.span);
1179 .sub_trait_refs(false, origin,
1180 impl_trait_ref, vt.bound.clone())
1185 *candidate_i == *candidate_j
1190 ///////////////////////////////////////////////////////////////////////////
1193 // These cover the traits that are built-in to the language
1194 // itself. This includes `Copy` and `Sized` for sure. For the
1195 // moment, it also includes `Send` / `Sync` and a few others, but
1196 // those will hopefully change to library-defined traits in the
1199 fn assemble_builtin_bound_candidates<'o>(&mut self,
1200 bound: ty::BuiltinBound,
1201 stack: &ObligationStack<'o, 'tcx>,
1202 candidates: &mut CandidateSet<'tcx>)
1203 -> Result<(),SelectionError<'tcx>>
1205 // FIXME -- To be more like a normal impl, we should just
1206 // ignore the nested cases here, and instead generate nested
1207 // obligations in `confirm_candidate`. However, this doesn't
1208 // work because we require handling the recursive cases to
1209 // avoid infinite cycles (that is, with recursive types,
1210 // sometimes `Foo : Copy` only holds if `Foo : Copy`).
1212 match self.builtin_bound(bound, stack.obligation.self_ty()) {
1214 debug!("builtin_bound: bound={} nested={}",
1215 bound.repr(self.tcx()),
1216 nested.repr(self.tcx()));
1217 let data = self.vtable_builtin_data(stack.obligation, bound, nested);
1218 match self.winnow_selection(Some(stack), VtableBuiltin(data)) {
1219 EvaluatedToOk => { Ok(candidates.vec.push(BuiltinCandidate(bound))) }
1220 EvaluatedToAmbig => { Ok(candidates.ambiguous = true) }
1221 EvaluatedToErr => { Err(Unimplemented) }
1224 Ok(ParameterBuiltin) => { Ok(()) }
1225 Ok(AmbiguousBuiltin) => { Ok(candidates.ambiguous = true) }
1226 Err(e) => { Err(e) }
1230 fn builtin_bound(&mut self,
1231 bound: ty::BuiltinBound,
1233 -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1235 let self_ty = self.infcx.shallow_resolve(self_ty);
1236 return match self_ty.sty {
1237 ty::ty_infer(ty::IntVar(_)) |
1238 ty::ty_infer(ty::FloatVar(_)) |
1245 // safe for everything
1249 ty::ty_uniq(referent_ty) => { // Box<T>
1261 Ok(If(vec![referent_ty]))
1266 ty::ty_ptr(ty::mt { ty: referent_ty, .. }) => { // *const T, *mut T
1275 Ok(If(vec![referent_ty]))
1280 ty::ty_closure(ref c) => {
1282 ty::UniqTraitStore => {
1283 // proc: Equivalent to `Box<FnOnce>`
1295 if c.bounds.builtin_bounds.contains(&bound) {
1303 ty::RegionTraitStore(_, mutbl) => {
1304 // ||: Equivalent to `&FnMut` or `&mut FnMut` or something like that.
1308 ast::MutMutable => Err(Unimplemented), // &mut T is affine
1309 ast::MutImmutable => Ok(If(Vec::new())), // &T is copyable
1319 if c.bounds.builtin_bounds.contains(&bound) {
1330 ty::ty_trait(box ty::TyTrait { ref principal, bounds }) => {
1335 ty::BoundCopy | ty::BoundSync | ty::BoundSend => {
1336 if bounds.builtin_bounds.contains(&bound) {
1339 // Recursively check all supertraits to find out if any further
1340 // bounds are required and thus we must fulfill.
1341 // We have to create a temp trait ref here since TyTraits don't
1342 // have actual self type info (which is required for the
1343 // supertraits iterator).
1344 let tmp_tr = Rc::new(ty::TraitRef {
1345 def_id: principal.def_id,
1346 substs: principal.substs.with_self_ty(ty::mk_err())
1348 for tr in util::supertraits(self.tcx(), tmp_tr) {
1349 let td = ty::lookup_trait_def(self.tcx(), tr.def_id);
1351 if td.bounds.builtin_bounds.contains(&bound) {
1352 return Ok(If(Vec::new()))
1362 ty::ty_rptr(_, ty::mt { ty: referent_ty, mutbl }) => {
1367 // &mut T is affine and hence never `Copy`
1368 ast::MutMutable => Err(Unimplemented),
1370 // &T is always copyable
1371 ast::MutImmutable => Ok(If(Vec::new())),
1381 // Note: technically, a region pointer is only
1382 // sendable if it has lifetime
1383 // `'static`. However, we don't take regions
1384 // into account when doing trait matching:
1385 // instead, when we decide that `T : Send`, we
1386 // will register a separate constraint with
1387 // the region inferencer that `T : 'static`
1388 // holds as well (because the trait `Send`
1389 // requires it). This will ensure that there
1390 // is no borrowed data in `T` (or else report
1391 // an inference error). The reason we do it
1392 // this way is that we do not yet *know* what
1393 // lifetime the borrowed reference has, since
1394 // we haven't finished running inference -- in
1395 // other words, there's a kind of
1396 // chicken-and-egg problem.
1397 Ok(If(vec![referent_ty]))
1402 ty::ty_vec(element_ty, ref len) => {
1407 Some(_) => Ok(If(vec![element_ty])), // [T, ..n] is copy iff T is copy
1408 None => Err(Unimplemented), // [T] is unsized and hence affine
1422 Ok(If(vec![element_ty]))
1428 // Equivalent to [u8]
1442 ty::ty_tup(ref tys) => {
1443 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1447 ty::ty_unboxed_closure(def_id, _, ref substs) => {
1448 // FIXME -- This case is tricky. In the case of by-ref
1449 // closures particularly, we need the results of
1450 // inference to decide how to reflect the type of each
1451 // upvar (the upvar may have type `T`, but the runtime
1452 // type could be `&mut`, `&`, or just `T`). For now,
1453 // though, we'll do this unsoundly and assume that all
1454 // captures are by value. Really what we ought to do
1455 // is reserve judgement and then intertwine this
1456 // analysis with closure inference.
1457 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
1458 match self.tcx().freevars.borrow().get(&def_id.node) {
1469 let freevar_def_id = freevar.def.def_id();
1470 self.typer.node_ty(freevar_def_id.node)
1471 .unwrap_or(ty::mk_err()).subst(self.tcx(), substs)
1479 ty::ty_struct(def_id, ref substs) => {
1480 let types: Vec<Ty> =
1481 ty::struct_fields(self.tcx(), def_id, substs)
1485 nominal(self, bound, def_id, types)
1488 ty::ty_enum(def_id, ref substs) => {
1489 let types: Vec<Ty> =
1490 ty::substd_enum_variants(self.tcx(), def_id, substs)
1492 .flat_map(|variant| variant.args.iter())
1495 nominal(self, bound, def_id, types)
1498 ty::ty_param(_) => {
1499 // Note: A type parameter is only considered to meet a
1500 // particular bound if there is a where clause telling
1501 // us that it does, and that case is handled by
1502 // `assemble_candidates_from_caller_bounds()`.
1503 Ok(ParameterBuiltin)
1506 ty::ty_infer(ty::TyVar(_)) => {
1507 // Unbound type variable. Might or might not have
1508 // applicable impls and so forth, depending on what
1509 // those type variables wind up being bound to.
1510 Ok(AmbiguousBuiltin)
1518 ty::ty_infer(ty::SkolemizedTy(_)) |
1519 ty::ty_infer(ty::SkolemizedIntTy(_)) => {
1520 self.tcx().sess.bug(
1522 "asked to assemble builtin bounds of unexpected type: {}",
1523 self_ty.repr(self.tcx())).as_slice());
1527 fn nominal<'cx, 'tcx>(this: &mut SelectionContext<'cx, 'tcx>,
1528 bound: ty::BuiltinBound,
1530 types: Vec<Ty<'tcx>>)
1531 -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1533 // First check for markers and other nonsense.
1534 let tcx = this.tcx();
1538 Some(def_id) == tcx.lang_items.no_send_bound() ||
1539 Some(def_id) == tcx.lang_items.managed_bound()
1541 return Err(Unimplemented);
1547 Some(def_id) == tcx.lang_items.no_copy_bound() ||
1548 Some(def_id) == tcx.lang_items.managed_bound() ||
1549 ty::has_dtor(tcx, def_id)
1551 return Err(Unimplemented);
1557 Some(def_id) == tcx.lang_items.no_sync_bound() ||
1558 Some(def_id) == tcx.lang_items.managed_bound()
1560 return Err(Unimplemented);
1562 Some(def_id) == tcx.lang_items.unsafe_type()
1564 // FIXME(#13231) -- we currently consider `UnsafeCell<T>`
1565 // to always be sync. This is allow for types like `Queue`
1566 // and `Mutex`, where `Queue<T> : Sync` is `T : Send`.
1567 return Ok(If(Vec::new()));
1571 ty::BoundSized => { }
1578 ///////////////////////////////////////////////////////////////////////////
1581 // Confirmation unifies the output type parameters of the trait
1582 // with the values found in the obligation, possibly yielding a
1583 // type error. See `doc.rs` for more details.
1585 fn confirm_candidate(&mut self,
1586 obligation: &Obligation<'tcx>,
1587 candidate: Candidate<'tcx>)
1588 -> Result<Selection<'tcx>,SelectionError<'tcx>>
1590 debug!("confirm_candidate({}, {})",
1591 obligation.repr(self.tcx()),
1592 candidate.repr(self.tcx()));
1595 // FIXME -- see assemble_builtin_bound_candidates()
1596 BuiltinCandidate(_) |
1598 Ok(VtableBuiltin(VtableBuiltinData { nested: VecPerParamSpace::empty() }))
1601 ParamCandidate(param) => {
1603 try!(self.confirm_param_candidate(obligation, param))))
1606 ImplCandidate(impl_def_id) => {
1608 try!(self.confirm_impl_candidate(obligation, impl_def_id));
1609 Ok(VtableImpl(vtable_impl))
1612 UnboxedClosureCandidate(closure_def_id, substs) => {
1613 try!(self.confirm_unboxed_closure_candidate(obligation, closure_def_id, &substs));
1614 Ok(VtableUnboxedClosure(closure_def_id, substs))
1619 fn confirm_param_candidate(&mut self,
1620 obligation: &Obligation<'tcx>,
1621 param: VtableParamData<'tcx>)
1622 -> Result<VtableParamData<'tcx>,
1623 SelectionError<'tcx>>
1625 debug!("confirm_param_candidate({},{})",
1626 obligation.repr(self.tcx()),
1627 param.repr(self.tcx()));
1629 let () = try!(self.confirm(obligation.cause,
1630 obligation.trait_ref.clone(),
1631 param.bound.clone()));
1635 fn confirm_builtin_candidate(&mut self,
1636 obligation: &Obligation<'tcx>,
1637 bound: ty::BuiltinBound)
1638 -> Result<VtableBuiltinData<Obligation<'tcx>>,
1639 SelectionError<'tcx>>
1641 debug!("confirm_builtin_candidate({})",
1642 obligation.repr(self.tcx()));
1644 match try!(self.builtin_bound(bound, obligation.self_ty())) {
1645 If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)),
1647 ParameterBuiltin => {
1648 self.tcx().sess.span_bug(
1649 obligation.cause.span,
1650 format!("builtin bound for {} was ambig",
1651 obligation.repr(self.tcx())).as_slice());
1656 fn vtable_builtin_data(&mut self,
1657 obligation: &Obligation<'tcx>,
1658 bound: ty::BuiltinBound,
1659 nested: Vec<Ty<'tcx>>)
1660 -> VtableBuiltinData<Obligation<'tcx>>
1662 let obligations = nested.iter().map(|&t| {
1663 util::obligation_for_builtin_bound(
1667 obligation.recursion_depth + 1,
1669 }).collect::<Result<_, _>>();
1670 let obligations = match obligations {
1672 Err(ErrorReported) => Vec::new()
1674 let obligations = VecPerParamSpace::new(obligations, Vec::new(),
1675 Vec::new(), Vec::new());
1676 VtableBuiltinData { nested: obligations }
1679 fn confirm_impl_candidate(&mut self,
1680 obligation: &Obligation<'tcx>,
1681 impl_def_id: ast::DefId)
1682 -> Result<VtableImplData<'tcx, Obligation<'tcx>>,
1683 SelectionError<'tcx>>
1685 debug!("confirm_impl_candidate({},{})",
1686 obligation.repr(self.tcx()),
1687 impl_def_id.repr(self.tcx()));
1689 // First, create the substitutions by matching the impl again,
1690 // this time not in a probe.
1691 let substs = self.rematch_impl(impl_def_id, obligation);
1692 Ok(self.vtable_impl(impl_def_id, substs, obligation.cause, obligation.recursion_depth + 1))
1695 fn vtable_impl(&mut self,
1696 impl_def_id: ast::DefId,
1697 substs: Substs<'tcx>,
1698 cause: ObligationCause<'tcx>,
1699 recursion_depth: uint)
1700 -> VtableImplData<'tcx, Obligation<'tcx>>
1702 let impl_obligations =
1703 self.impl_obligations(cause,
1707 VtableImplData { impl_def_id: impl_def_id,
1709 nested: impl_obligations }
1712 fn confirm_unboxed_closure_candidate(&mut self,
1713 obligation: &Obligation<'tcx>,
1714 closure_def_id: ast::DefId,
1715 substs: &Substs<'tcx>)
1716 -> Result<(),SelectionError<'tcx>>
1718 debug!("confirm_unboxed_closure_candidate({},{},{})",
1719 obligation.repr(self.tcx()),
1720 closure_def_id.repr(self.tcx()),
1721 substs.repr(self.tcx()));
1723 let closure_type = match self.typer.unboxed_closures().borrow().get(&closure_def_id) {
1724 Some(closure) => closure.closure_type.clone(),
1726 self.tcx().sess.span_bug(
1727 obligation.cause.span,
1728 format!("No entry for unboxed closure: {}",
1729 closure_def_id.repr(self.tcx())).as_slice());
1733 let closure_sig = &closure_type.sig;
1734 let arguments_tuple = closure_sig.inputs[0];
1737 vec![arguments_tuple.subst(self.tcx(), substs),
1738 closure_sig.output.unwrap().subst(self.tcx(), substs)],
1741 obligation.self_ty());
1742 let trait_ref = Rc::new(ty::TraitRef {
1743 def_id: obligation.trait_ref.def_id,
1747 self.confirm(obligation.cause,
1748 obligation.trait_ref.clone(),
1752 ///////////////////////////////////////////////////////////////////////////
1755 // Matching is a common path used for both evaluation and
1756 // confirmation. It basically unifies types that appear in impls
1757 // and traits. This does affect the surrounding environment;
1758 // therefore, when used during evaluation, match routines must be
1759 // run inside of a `probe()` so that their side-effects are
1762 fn rematch_impl(&mut self,
1763 impl_def_id: ast::DefId,
1764 obligation: &Obligation<'tcx>)
1767 match self.match_impl(impl_def_id, obligation) {
1772 self.tcx().sess.bug(
1773 format!("Impl {} was matchable against {} but now is not",
1774 impl_def_id.repr(self.tcx()),
1775 obligation.repr(self.tcx()))
1781 fn match_impl(&mut self,
1782 impl_def_id: ast::DefId,
1783 obligation: &Obligation<'tcx>)
1784 -> Result<Substs<'tcx>, ()>
1786 let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
1787 impl_def_id).unwrap();
1789 // Before we create the substitutions and everything, first
1790 // consider a "quick reject". This avoids creating more types
1791 // and so forth that we need to.
1792 if self.fast_reject_trait_refs(obligation, &*impl_trait_ref) {
1796 let impl_substs = util::fresh_substs_for_impl(self.infcx,
1797 obligation.cause.span,
1800 let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
1803 match self.match_trait_refs(obligation, impl_trait_ref) {
1804 Ok(()) => Ok(impl_substs),
1809 fn fast_reject_trait_refs(&mut self,
1810 obligation: &Obligation,
1811 impl_trait_ref: &ty::TraitRef)
1814 // We can avoid creating type variables and doing the full
1815 // substitution if we find that any of the input types, when
1816 // simplified, do not match.
1818 obligation.trait_ref.input_types().iter()
1819 .zip(impl_trait_ref.input_types().iter())
1820 .any(|(&obligation_ty, &impl_ty)| {
1821 let simplified_obligation_ty =
1822 fast_reject::simplify_type(self.tcx(), obligation_ty, true);
1823 let simplified_impl_ty =
1824 fast_reject::simplify_type(self.tcx(), impl_ty, false);
1826 simplified_obligation_ty.is_some() &&
1827 simplified_impl_ty.is_some() &&
1828 simplified_obligation_ty != simplified_impl_ty
1832 fn match_trait_refs(&mut self,
1833 obligation: &Obligation<'tcx>,
1834 trait_ref: Rc<ty::TraitRef<'tcx>>)
1837 debug!("match_trait_refs: obligation={} trait_ref={}",
1838 obligation.repr(self.tcx()),
1839 trait_ref.repr(self.tcx()));
1841 let origin = infer::RelateOutputImplTypes(obligation.cause.span);
1842 match self.infcx.sub_trait_refs(false,
1845 obligation.trait_ref.clone()) {
1851 fn match_inherent_impl(&mut self,
1852 impl_def_id: ast::DefId,
1853 obligation_cause: ObligationCause,
1854 obligation_self_ty: Ty<'tcx>)
1855 -> Result<Substs<'tcx>,()>
1858 * Determines whether the self type declared against
1859 * `impl_def_id` matches `obligation_self_ty`. If successful,
1860 * returns the substitutions used to make them match. See
1861 * `match_impl()`. For example, if `impl_def_id` is declared
1864 * impl<T:Copy> Foo for ~T { ... }
1866 * and `obligation_self_ty` is `int`, we'd back an `Err(_)`
1867 * result. But if `obligation_self_ty` were `~int`, we'd get
1871 // Create fresh type variables for each type parameter declared
1873 let impl_substs = util::fresh_substs_for_impl(self.infcx,
1874 obligation_cause.span,
1877 // Find the self type for the impl.
1878 let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty;
1879 let impl_self_ty = impl_self_ty.subst(self.tcx(), &impl_substs);
1881 debug!("match_impl_self_types(obligation_self_ty={}, impl_self_ty={})",
1882 obligation_self_ty.repr(self.tcx()),
1883 impl_self_ty.repr(self.tcx()));
1885 match self.match_self_types(obligation_cause,
1887 obligation_self_ty) {
1889 debug!("Matched impl_substs={}", impl_substs.repr(self.tcx()));
1899 fn match_self_types(&mut self,
1900 cause: ObligationCause,
1902 // The self type provided by the impl/caller-obligation:
1903 provided_self_ty: Ty<'tcx>,
1905 // The self type the obligation is for:
1906 required_self_ty: Ty<'tcx>)
1909 // FIXME(#5781) -- equating the types is stronger than
1910 // necessary. Should consider variance of trait w/r/t Self.
1912 let origin = infer::RelateSelfType(cause.span);
1913 match self.infcx.eq_types(false,
1922 ///////////////////////////////////////////////////////////////////////////
1925 // The final step of selection: once we know how an obligation is
1926 // is resolved, we confirm that selection in order to have
1927 // side-effects on the typing environment. This step also unifies
1928 // the output type parameters from the obligation with those found
1929 // on the impl/bound, which may yield type errors.
1931 fn confirm_impl_vtable(&mut self,
1932 impl_def_id: ast::DefId,
1933 obligation_cause: ObligationCause<'tcx>,
1934 obligation_trait_ref: Rc<ty::TraitRef<'tcx>>,
1935 substs: &Substs<'tcx>)
1936 -> Result<(), SelectionError<'tcx>>
1939 * Relates the output type parameters from an impl to the
1940 * trait. This may lead to type errors. The confirmation step
1941 * is separated from the main match procedure because these
1942 * type errors do not cause us to select another impl.
1944 * As an example, consider matching the obligation
1945 * `Iterator<char> for Elems<int>` using the following impl:
1947 * impl<T> Iterator<T> for Elems<T> { ... }
1949 * The match phase will succeed with substitution `T=int`.
1950 * The confirm step will then try to unify `int` and `char`
1951 * and yield an error.
1954 let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
1955 impl_def_id).unwrap();
1956 let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
1958 self.confirm(obligation_cause, obligation_trait_ref, impl_trait_ref)
1961 fn confirm(&mut self,
1962 obligation_cause: ObligationCause,
1963 obligation_trait_ref: Rc<ty::TraitRef<'tcx>>,
1964 expected_trait_ref: Rc<ty::TraitRef<'tcx>>)
1965 -> Result<(), SelectionError<'tcx>>
1968 * After we have determined which impl applies, and with what
1969 * substitutions, there is one last step. We have to go back
1970 * and relate the "output" type parameters from the obligation
1971 * to the types that are specified in the impl.
1973 * For example, imagine we have:
1975 * impl<T> Iterator<T> for Vec<T> { ... }
1977 * and our obligation is `Iterator<Foo> for Vec<int>` (note
1978 * the mismatch in the obligation types). Up until this step,
1979 * no error would be reported: the self type is `Vec<int>`,
1980 * and that matches `Vec<T>` with the substitution `T=int`.
1981 * At this stage, we could then go and check that the type
1982 * parameters to the `Iterator` trait match.
1983 * (In terms of the parameters, the `expected_trait_ref`
1984 * here would be `Iterator<int> for Vec<int>`, and the
1985 * `obligation_trait_ref` would be `Iterator<Foo> for Vec<int>`.
1987 * Note that this checking occurs *after* the impl has
1988 * selected, because these output type parameters should not
1989 * affect the selection of the impl. Therefore, if there is a
1990 * mismatch, we report an error to the user.
1993 let origin = infer::RelateOutputImplTypes(obligation_cause.span);
1995 let obligation_trait_ref = obligation_trait_ref.clone();
1996 match self.infcx.sub_trait_refs(false,
1998 expected_trait_ref.clone(),
1999 obligation_trait_ref) {
2001 Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, e))
2005 ///////////////////////////////////////////////////////////////////////////
2008 fn push_stack<'o,'s:'o>(&mut self,
2009 previous_stack: Option<&'s ObligationStack<'s, 'tcx>>,
2010 obligation: &'o Obligation<'tcx>)
2011 -> ObligationStack<'o, 'tcx>
2013 let skol_trait_ref = obligation.trait_ref.fold_with(&mut self.skolemizer);
2016 obligation: obligation,
2017 skol_trait_ref: skol_trait_ref,
2018 previous: previous_stack.map(|p| p), // FIXME variance
2022 fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
2024 * Returns set of all impls for a given trait.
2027 ty::populate_implementations_for_trait_if_necessary(self.tcx(),
2029 match self.tcx().trait_impls.borrow().get(&trait_def_id) {
2031 Some(impls) => impls.borrow().clone()
2035 fn impl_obligations(&self,
2036 cause: ObligationCause<'tcx>,
2037 recursion_depth: uint,
2038 impl_def_id: ast::DefId,
2039 impl_substs: &Substs<'tcx>)
2040 -> VecPerParamSpace<Obligation<'tcx>>
2042 let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
2043 let bounds = impl_generics.to_bounds(self.tcx(), impl_substs);
2044 util::obligations_for_generics(self.tcx(), cause, recursion_depth,
2045 &bounds, &impl_substs.types)
2049 impl<'tcx> Repr<'tcx> for Candidate<'tcx> {
2050 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2052 ErrorCandidate => format!("ErrorCandidate"),
2053 BuiltinCandidate(b) => format!("BuiltinCandidate({})", b),
2054 UnboxedClosureCandidate(c, ref s) => {
2055 format!("MatchedUnboxedClosureCandidate({},{})", c, s.repr(tcx))
2057 ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
2058 ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
2063 impl<'tcx> SelectionCache<'tcx> {
2064 pub fn new() -> SelectionCache<'tcx> {
2066 hashmap: RefCell::new(HashMap::new())
2071 impl<'o, 'tcx> ObligationStack<'o, 'tcx> {
2072 fn iter(&self) -> Option<&ObligationStack<'o, 'tcx>> {
2077 impl<'o, 'tcx> Iterator<&'o ObligationStack<'o, 'tcx>> for Option<&'o ObligationStack<'o, 'tcx>> {
2078 fn next(&mut self) -> Option<&'o ObligationStack<'o, 'tcx>> {
2091 impl<'o, 'tcx> Repr<'tcx> for ObligationStack<'o, 'tcx> {
2092 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2093 format!("ObligationStack({})",
2094 self.obligation.repr(tcx))
2098 impl EvaluationResult {
2099 fn may_apply(&self) -> bool {
2101 EvaluatedToOk | EvaluatedToAmbig => true,
2102 EvaluatedToErr => false,
2107 impl MethodMatchResult {
2108 pub fn may_apply(&self) -> bool {
2110 MethodMatched(_) => true,
2111 MethodAmbiguous(_) => true,
2112 MethodDidNotMatch => false,