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::{ErrorReported};
21 use super::{Obligation, ObligationCause};
22 use super::{SelectionError, Unimplemented, Overflow,
23 OutputTypeParameterMismatch};
24 use super::{Selection};
25 use super::{SelectionResult};
26 use super::{VtableBuiltin, VtableImpl, VtableParam, VtableUnboxedClosure};
27 use super::{VtableImplData, VtableParamData, VtableBuiltinData};
30 use middle::mem_categorization::Typer;
31 use middle::subst::{Subst, Substs, VecPerParamSpace};
33 use middle::typeck::check::regionmanip;
34 use middle::typeck::infer;
35 use middle::typeck::infer::{InferCtxt, TypeSkolemizer};
36 use middle::ty_fold::TypeFoldable;
37 use std::cell::RefCell;
38 use std::collections::hash_map::HashMap;
41 use util::ppaux::Repr;
43 pub struct SelectionContext<'cx, 'tcx:'cx> {
44 infcx: &'cx InferCtxt<'cx, 'tcx>,
45 param_env: &'cx ty::ParameterEnvironment,
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> {
74 obligation: &'prev Obligation,
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>,
80 previous: Option<&'prev ObligationStack<'prev>>
83 pub struct SelectionCache {
84 hashmap: RefCell<HashMap<Rc<ty::TraitRef>, SelectionResult<Candidate>>>,
87 pub enum MethodMatchResult {
88 MethodMatched(MethodMatchedData),
89 MethodAmbiguous(/* list of impls that could apply */ Vec<ast::DefId>),
94 pub enum MethodMatchedData {
95 // In the case of a precise match, we don't really need to store
96 // how the match was found. So don't.
99 // In the case of a coercion, we need to know the precise impl so
100 // that we can determine the type to which things were coerced.
101 CoerciveMethodMatch(/* impl we matched */ ast::DefId)
105 * The selection process begins by considering all impls, where
106 * clauses, and so forth that might resolve an obligation. Sometimes
107 * we'll be able to say definitively that (e.g.) an impl does not
108 * apply to the obligation: perhaps it is defined for `uint` but the
109 * obligation is for `int`. In that case, we drop the impl out of the
110 * list. But the other cases are considered *candidates*.
112 * Candidates can either be definitive or ambiguous. An ambiguous
113 * candidate is one that might match or might not, depending on how
114 * type variables wind up being resolved. This only occurs during inference.
116 * For selection to suceed, there must be exactly one non-ambiguous
117 * candidate. Usually, it is not possible to have more than one
118 * definitive candidate, due to the coherence rules. However, there is
119 * one case where it could occur: if there is a blanket impl for a
120 * trait (that is, an impl applied to all T), and a type parameter
121 * with a where clause. In that case, we can have a candidate from the
122 * where clause and a second candidate from the impl. This is not a
123 * problem because coherence guarantees us that the impl which would
124 * be used to satisfy the where clause is the same one that we see
125 * now. To resolve this issue, therefore, we ignore impls if we find a
126 * matching where clause. Part of the reason for this is that where
127 * clauses can give additional information (like, the types of output
128 * parameters) that would have to be inferred from the impl.
130 #[deriving(PartialEq,Eq,Show,Clone)]
132 BuiltinCandidate(ty::BuiltinBound),
133 ParamCandidate(VtableParamData),
134 ImplCandidate(ast::DefId),
135 UnboxedClosureCandidate(/* closure */ ast::DefId, Substs),
139 struct CandidateSet {
144 enum BuiltinBoundConditions {
151 enum EvaluationResult {
157 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
158 pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>,
159 param_env: &'cx ty::ParameterEnvironment,
160 typer: &'cx Typer<'tcx>)
161 -> SelectionContext<'cx, 'tcx> {
164 param_env: param_env,
166 skolemizer: infcx.skolemizer(),
171 pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'tcx>,
172 param_env: &'cx ty::ParameterEnvironment,
173 typer: &'cx Typer<'tcx>)
174 -> SelectionContext<'cx, 'tcx> {
177 param_env: param_env,
179 skolemizer: infcx.skolemizer(),
184 pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
188 ///////////////////////////////////////////////////////////////////////////
191 // The selection phase tries to identify *how* an obligation will
192 // be resolved. For example, it will identify which impl or
193 // parameter bound is to be used. The process can be inconclusive
194 // if the self type in the obligation is not fully inferred. Selection
195 // can result in an error in one of two ways:
197 // 1. If no applicable impl or parameter bound can be found.
198 // 2. If the output type parameters in the obligation do not match
199 // those specified by the impl/bound. For example, if the obligation
200 // is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
201 // `impl<T> Iterable<T> for Vec<T>`, than an error would result.
203 pub fn select(&mut self, obligation: &Obligation) -> SelectionResult<Selection> {
205 * Evaluates whether the obligation can be satisfied. Returns
206 * an indication of whether the obligation can be satisfied
207 * and, if so, by what means. Never affects surrounding typing
211 debug!("select({})", obligation.repr(self.tcx()));
213 let stack = self.push_stack(None, obligation);
214 match try!(self.candidate_from_obligation(&stack)) {
216 Some(candidate) => Ok(Some(try!(self.confirm_candidate(obligation, candidate)))),
220 pub fn select_inherent_impl(&mut self,
221 impl_def_id: ast::DefId,
222 obligation_cause: ObligationCause,
223 obligation_self_ty: ty::t)
224 -> SelectionResult<VtableImplData<Obligation>>
226 debug!("select_inherent_impl(impl_def_id={}, obligation_self_ty={})",
227 impl_def_id.repr(self.tcx()),
228 obligation_self_ty.repr(self.tcx()));
230 match self.match_inherent_impl(impl_def_id,
232 obligation_self_ty) {
234 let vtable_impl = self.vtable_impl(impl_def_id, substs, obligation_cause, 0);
235 Ok(Some(vtable_impl))
243 ///////////////////////////////////////////////////////////////////////////
246 // Tests whether an obligation can be selected or whether an impl
247 // can be applied to particular types. It skips the "confirmation"
248 // step and hence completely ignores output type parameters.
250 // The result is "true" if the obligation *may* hold and "false" if
251 // we can be sure it does not.
253 pub fn evaluate_obligation(&mut self,
254 obligation: &Obligation)
258 * Evaluates whether the obligation `obligation` can be
259 * satisfied (by any means).
262 debug!("evaluate_obligation({})",
263 obligation.repr(self.tcx()));
265 let stack = self.push_stack(None, obligation);
266 self.evaluate_stack(&stack).may_apply()
269 fn evaluate_builtin_bound_recursively(&mut self,
270 bound: ty::BuiltinBound,
271 previous_stack: &ObligationStack,
276 util::obligation_for_builtin_bound(
278 previous_stack.obligation.cause,
280 previous_stack.obligation.recursion_depth + 1,
285 self.evaluate_obligation_recursively(Some(previous_stack), &obligation)
287 Err(ErrorReported) => {
293 fn evaluate_obligation_recursively(&mut self,
294 previous_stack: Option<&ObligationStack>,
295 obligation: &Obligation)
298 debug!("evaluate_obligation_recursively({})",
299 obligation.repr(self.tcx()));
301 let stack = self.push_stack(previous_stack.map(|x| x), obligation);
303 let result = self.evaluate_stack(&stack);
305 debug!("result: {}", result);
309 fn evaluate_stack(&mut self,
310 stack: &ObligationStack)
313 // In intercrate mode, whenever any of the types are unbound,
314 // there can always be an impl. Even if there are no impls in
315 // this crate, perhaps the type would be unified with
316 // something from another crate that does provide an impl.
318 // In intracrate mode, we must still be conservative. The reason is
319 // that we want to avoid cycles. Imagine an impl like:
321 // impl<T:Eq> Eq for Vec<T>
323 // and a trait reference like `$0 : Eq` where `$0` is an
324 // unbound variable. When we evaluate this trait-reference, we
325 // will unify `$0` with `Vec<$1>` (for some fresh variable
326 // `$1`), on the condition that `$1 : Eq`. We will then wind
327 // up with many candidates (since that are other `Eq` impls
328 // that apply) and try to winnow things down. This results in
329 // a recurssive evaluation that `$1 : Eq` -- as you can
330 // imagine, this is just where we started. To avoid that, we
331 // check for unbound variables and return an ambiguous (hence possible)
332 // match if we've seen this trait before.
334 // This suffices to allow chains like `FnMut` implemented in
335 // terms of `Fn` etc, but we could probably make this more
337 let input_types = stack.skol_trait_ref.input_types();
338 let unbound_input_types = input_types.iter().any(|&t| ty::type_is_skolemized(t));
340 unbound_input_types &&
342 stack.iter().skip(1).any(
343 |prev| stack.skol_trait_ref.def_id == prev.skol_trait_ref.def_id))
345 debug!("evaluate_stack_intracrate({}) --> unbound argument, recursion --> ambiguous",
346 stack.skol_trait_ref.repr(self.tcx()));
347 return EvaluatedToAmbig;
350 // If there is any previous entry on the stack that precisely
351 // matches this obligation, then we can assume that the
352 // obligation is satisfied for now (still all other conditions
353 // must be met of course). One obvious case this comes up is
354 // marker traits like `Send`. Think of a linked list:
356 // struct List<T> { data: T, next: Option<Box<List<T>>> {
358 // `Box<List<T>>` will be `Send` if `T` is `Send` and
359 // `Option<Box<List<T>>>` is `Send`, and in turn
360 // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
363 // Note that we do this comparison using the `skol_trait_ref`
364 // fields. Because these have all been skolemized using
365 // `self.skolemizer`, we can be sure that (a) this will not
366 // affect the inferencer state and (b) that if we see two
367 // skolemized types with the same index, they refer to the
368 // same unbound type variable.
371 .skip(1) // skip top-most frame
372 .any(|prev| stack.skol_trait_ref == prev.skol_trait_ref)
374 debug!("evaluate_stack_intracrate({}) --> recursive",
375 stack.skol_trait_ref.repr(self.tcx()));
376 return EvaluatedToOk;
379 match self.candidate_from_obligation(stack) {
380 Ok(Some(c)) => self.winnow_candidate(stack, &c),
381 Ok(None) => EvaluatedToAmbig,
382 Err(_) => EvaluatedToErr,
386 pub fn evaluate_impl(&mut self,
387 impl_def_id: ast::DefId,
388 obligation: &Obligation)
392 * Evaluates whether the impl with id `impl_def_id` could be
393 * applied to the self type `obligation_self_ty`. This can be
394 * used either for trait or inherent impls.
397 debug!("evaluate_impl(impl_def_id={}, obligation={})",
398 impl_def_id.repr(self.tcx()),
399 obligation.repr(self.tcx()));
401 self.infcx.probe(|| {
402 match self.match_impl(impl_def_id, obligation) {
404 let vtable_impl = self.vtable_impl(impl_def_id,
407 obligation.recursion_depth + 1);
408 self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
417 ///////////////////////////////////////////////////////////////////////////
420 // Method matching is a variation on the normal select/evaluation
421 // situation. In this scenario, rather than having a full trait
422 // reference to select from, we start with an expression like
423 // `receiver.method(...)`. This means that we have `rcvr_ty`, the
424 // type of the receiver, and we have a possible trait that
425 // supplies `method`. We must determine whether the receiver is
426 // applicable, taking into account the transformed self type
427 // declared on `method`. We also must consider the possibility
428 // that `receiver` can be *coerced* into a suitable type (for
429 // example, a receiver type like `&(Any+Send)` might be coerced
430 // into a receiver like `&Any` to allow for method dispatch). See
431 // the body of `evaluate_method_obligation()` for more details on
434 pub fn evaluate_method_obligation(&mut self,
436 xform_self_ty: ty::t,
437 obligation: &Obligation)
441 * Determine whether a trait-method is applicable to a receiver of
442 * type `rcvr_ty`. *Does not affect the inference state.*
444 * - `rcvr_ty` -- type of the receiver
445 * - `xform_self_ty` -- transformed self type declared on the method, with `Self`
446 * to a fresh type variable
447 * - `obligation` -- a reference to the trait where the method is declared, with
448 * the input types on the trait replaced with fresh type variables
451 // Here is the situation. We have a trait method declared (say) like so:
454 // fn the_method(self: Rc<Self>, ...) { ... }
457 // And then we have a call looking (say) like this:
459 // let x: Rc<Foo> = ...;
462 // Now we want to decide if `TheTrait` is applicable. As a
463 // human, we can see that `TheTrait` is applicable if there is
464 // an impl for the type `Foo`. But how does the compiler know
465 // what impl to look for, given that our receiver has type
466 // `Rc<Foo>`? We need to take the method's self type into
469 // On entry to this function, we have the following inputs:
471 // - `rcvr_ty = Rc<Foo>`
472 // - `xform_self_ty = Rc<$0>`
473 // - `obligation = $0 as TheTrait`
475 // We do the match in two phases. The first is a *precise
476 // match*, which means that no coercion is required. This is
477 // the preferred way to match. It works by first making
478 // `rcvr_ty` a subtype of `xform_self_ty`. This unifies `$0`
479 // and `Foo`. We can then evaluate (roughly as normal) the
480 // trait reference `Foo as TheTrait`.
482 // If this fails, we fallback to a coercive match, described below.
484 match self.infcx.probe(|| self.match_method_precise(rcvr_ty, xform_self_ty, obligation)) {
485 Ok(()) => { return MethodMatched(PreciseMethodMatch); }
489 // Coercive matches work slightly differently and cannot
490 // completely reuse the normal trait matching machinery
491 // (though they employ many of the same bits and pieces). To
492 // see how it works, let's continue with our previous example,
493 // but with the following declarations:
496 // trait Foo : Bar { .. }
497 // trait Bar : Baz { ... }
499 // impl TheTrait for Bar {
500 // fn the_method(self: Rc<Bar>, ...) { ... }
504 // Now we see that the receiver type `Rc<Foo>` is actually an
505 // object type. And in fact the impl we want is an impl on the
506 // supertrait `Rc<Bar>`. The precise matching procedure won't
507 // find it, however, because `Rc<Foo>` is not a subtype of
508 // `Rc<Bar>` -- it is *coercible* to `Rc<Bar>` (actually, such
509 // coercions are not yet implemented, but let's leave that
512 // To handle this case, we employ a different procedure. Recall
513 // that our initial state is as follows:
515 // - `rcvr_ty = Rc<Foo>`
516 // - `xform_self_ty = Rc<$0>`
517 // - `obligation = $0 as TheTrait`
519 // We now go through each impl and instantiate all of its type
520 // variables, yielding the trait reference that the impl
521 // provides. In our example, the impl would provide `Bar as
522 // TheTrait`. Next we (try to) unify the trait reference that
523 // the impl provides with the input obligation. This would
524 // unify `$0` and `Bar`. Now we can see whether the receiver
525 // type (`Rc<Foo>`) is *coercible to* the transformed self
526 // type (`Rc<$0> == Rc<Bar>`). In this case, the answer is
527 // yes, so the impl is considered a candidate.
529 // Note that there is the possibility of ambiguity here, even
530 // when all types are known. In our example, this might occur
531 // if there was *also* an impl of `TheTrait` for `Baz`. In
532 // this case, `Rc<Foo>` would be coercible to both `Rc<Bar>`
533 // and `Rc<Baz>`. (Note that it is not a *coherence violation*
534 // to have impls for both `Bar` and `Baz`, despite this
535 // ambiguity). In this case, we report an error, listing all
536 // the applicable impls. The user can explicitly "up-coerce"
537 // to the type they want.
539 // Note that this coercion step only considers actual impls
540 // found in the source. This is because all the
541 // compiler-provided impls (such as those for unboxed
542 // closures) do not have relevant coercions. This simplifies
546 self.assemble_method_candidates_from_impls(rcvr_ty, xform_self_ty, obligation);
549 impls.retain(|&c| self.winnow_method_impl(c, rcvr_ty, xform_self_ty, obligation));
553 return MethodAmbiguous(impls);
557 Some(def_id) => MethodMatched(CoerciveMethodMatch(def_id)),
558 None => MethodDidNotMatch
562 pub fn confirm_method_match(&mut self,
564 xform_self_ty: ty::t,
565 obligation: &Obligation,
566 data: MethodMatchedData)
569 * Given the successful result of a method match, this
570 * function "confirms" the result, which basically repeats the
571 * various matching operations, but outside of any snapshot so
572 * that their effects are committed into the inference state.
575 let is_ok = match data {
576 PreciseMethodMatch => {
577 self.match_method_precise(rcvr_ty, xform_self_ty, obligation).is_ok()
580 CoerciveMethodMatch(impl_def_id) => {
581 self.match_method_coerce(impl_def_id, rcvr_ty, xform_self_ty, obligation).is_ok()
586 self.tcx().sess.span_bug(
587 obligation.cause.span,
588 format!("match not repeatable: {}, {}, {}, {}",
589 rcvr_ty.repr(self.tcx()),
590 xform_self_ty.repr(self.tcx()),
591 obligation.repr(self.tcx()),
596 fn match_method_precise(&mut self,
598 xform_self_ty: ty::t,
599 obligation: &Obligation)
603 * Implements the *precise method match* procedure described in
604 * `evaluate_method_obligation()`.
607 self.infcx.commit_if_ok(|| {
608 match self.infcx.sub_types(false, infer::RelateSelfType(obligation.cause.span),
609 rcvr_ty, xform_self_ty) {
611 Err(_) => { return Err(()); }
614 if self.evaluate_obligation(obligation) {
622 fn assemble_method_candidates_from_impls(&mut self,
624 xform_self_ty: ty::t,
625 obligation: &Obligation)
629 * Assembles a list of potentially applicable impls using the
630 * *coercive match* procedure described in
631 * `evaluate_method_obligation()`.
634 let mut candidates = Vec::new();
636 let all_impls = self.all_impls(obligation.trait_ref.def_id);
637 for &impl_def_id in all_impls.iter() {
638 self.infcx.probe(|| {
639 match self.match_method_coerce(impl_def_id, rcvr_ty, xform_self_ty, obligation) {
640 Ok(_) => { candidates.push(impl_def_id); }
649 fn match_method_coerce(&mut self,
650 impl_def_id: ast::DefId,
652 xform_self_ty: ty::t,
653 obligation: &Obligation)
654 -> Result<Substs, ()>
657 * Applies the *coercive match* procedure described in
658 * `evaluate_method_obligation()` to a particular impl.
661 // This is almost always expected to succeed. It
662 // causes the impl's self-type etc to be unified with
663 // the type variable that is shared between
664 // obligation/xform_self_ty. In our example, after
665 // this is done, the type of `xform_self_ty` would
666 // change from `Rc<$0>` to `Rc<Foo>` (because $0 is
667 // unified with `Foo`).
668 let substs = try!(self.match_impl(impl_def_id, obligation));
670 // Next, check whether we can coerce. For now we require
671 // that the coercion be a no-op.
672 let origin = infer::Misc(obligation.cause.span);
673 match infer::mk_coercety(self.infcx, true, origin,
674 rcvr_ty, xform_self_ty) {
675 Ok(None) => { /* Fallthrough */ }
676 Ok(Some(_)) | Err(_) => { return Err(()); }
682 fn winnow_method_impl(&mut self,
683 impl_def_id: ast::DefId,
685 xform_self_ty: ty::t,
686 obligation: &Obligation)
690 * A version of `winnow_impl` applicable to coerice method
691 * matching. This is basically the same as `winnow_impl` but
692 * it uses the method matching procedure and is specific to
696 debug!("winnow_method_impl: impl_def_id={} rcvr_ty={} xform_self_ty={} obligation={}",
697 impl_def_id.repr(self.tcx()),
698 rcvr_ty.repr(self.tcx()),
699 xform_self_ty.repr(self.tcx()),
700 obligation.repr(self.tcx()));
702 self.infcx.probe(|| {
703 match self.match_method_coerce(impl_def_id, rcvr_ty, xform_self_ty, obligation) {
705 let vtable_impl = self.vtable_impl(impl_def_id,
708 obligation.recursion_depth + 1);
709 self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
718 ///////////////////////////////////////////////////////////////////////////
719 // CANDIDATE ASSEMBLY
721 // The selection process begins by examining all in-scope impls,
722 // caller obligations, and so forth and assembling a list of
723 // candidates. See `doc.rs` and the `Candidate` type for more details.
725 fn candidate_from_obligation(&mut self,
726 stack: &ObligationStack)
727 -> SelectionResult<Candidate>
729 // Watch out for overflow. This intentionally bypasses (and does
730 // not update) the cache.
731 let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
732 if stack.obligation.recursion_depth >= recursion_limit {
733 debug!("{} --> overflow (limit={})",
734 stack.obligation.repr(self.tcx()),
739 // Check the cache. Note that we skolemize the trait-ref
740 // separately rather than using `stack.skol_trait_ref` -- this
741 // is because we want the unbound variables to be replaced
742 // with fresh skolemized types starting from index 0.
743 let cache_skol_trait_ref =
744 self.infcx.skolemize(stack.obligation.trait_ref.clone());
745 debug!("candidate_from_obligation(cache_skol_trait_ref={}, obligation={})",
746 cache_skol_trait_ref.repr(self.tcx()),
747 stack.repr(self.tcx()));
749 match self.check_candidate_cache(cache_skol_trait_ref.clone()) {
751 debug!("CACHE HIT: cache_skol_trait_ref={}, candidate={}",
752 cache_skol_trait_ref.repr(self.tcx()),
759 // If no match, compute result and insert into cache.
760 let candidate = self.candidate_from_obligation_no_cache(stack);
761 debug!("CACHE MISS: cache_skol_trait_ref={}, candidate={}",
762 cache_skol_trait_ref.repr(self.tcx()), candidate.repr(self.tcx()));
763 self.insert_candidate_cache(cache_skol_trait_ref, candidate.clone());
767 fn candidate_from_obligation_no_cache(&mut self,
768 stack: &ObligationStack)
769 -> SelectionResult<Candidate>
771 if ty::type_is_error(stack.obligation.self_ty()) {
772 return Ok(Some(ErrorCandidate));
775 let candidate_set = try!(self.assemble_candidates(stack));
777 if candidate_set.ambiguous {
778 debug!("candidate set contains ambig");
782 let mut candidates = candidate_set.vec;
784 debug!("assembled {} candidates for {}",
785 candidates.len(), stack.repr(self.tcx()));
787 // At this point, we know that each of the entries in the
788 // candidate set is *individually* applicable. Now we have to
789 // figure out if they contain mutual incompatibilities. This
790 // frequently arises if we have an unconstrained input type --
791 // for example, we are looking for $0:Eq where $0 is some
792 // unconstrained type variable. In that case, we'll get a
793 // candidate which assumes $0 == int, one that assumes $0 ==
794 // uint, etc. This spells an ambiguity.
796 // If there is more than one candidate, first winnow them down
797 // by considering extra conditions (nested obligations and so
798 // forth). We don't winnow if there is exactly one
799 // candidate. This is a relatively minor distinction but it
800 // can lead to better inference and error-reporting. An
801 // example would be if there was an impl:
803 // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
805 // and we were to see some code `foo.push_clone()` where `boo`
806 // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
807 // we were to winnow, we'd wind up with zero candidates.
808 // Instead, we select the right impl now but report `Bar does
809 // not implement Clone`.
810 if candidates.len() > 1 {
811 candidates.retain(|c| self.winnow_candidate(stack, c).may_apply())
814 // If there are STILL multiple candidate, we can further reduce
815 // the list by dropping duplicates.
816 if candidates.len() > 1 {
818 while i < candidates.len() {
820 range(0, candidates.len())
822 .any(|j| self.candidate_should_be_dropped_in_favor_of(stack,
826 debug!("Dropping candidate #{}/{}: {}",
827 i, candidates.len(), candidates[i].repr(self.tcx()));
828 candidates.swap_remove(i);
830 debug!("Retaining candidate #{}/{}: {}",
831 i, candidates.len(), candidates[i].repr(self.tcx()));
837 // If there are *STILL* multiple candidates, give up and
838 // report ambiguiuty.
839 if candidates.len() > 1 {
840 debug!("multiple matches, ambig");
844 // If there are *NO* candidates, that there are no impls --
845 // that we know of, anyway. Note that in the case where there
846 // are unbound type variables within the obligation, it might
847 // be the case that you could still satisfy the obligation
848 // from another crate by instantiating the type variables with
849 // a type from another crate that does have an impl. This case
850 // is checked for in `evaluate_stack` (and hence users
851 // who might care about this case, like coherence, should use
853 if candidates.len() == 0 {
854 return Err(Unimplemented);
857 // Just one candidate left.
858 let candidate = candidates.pop().unwrap();
862 fn pick_candidate_cache(&self,
863 cache_skol_trait_ref: &Rc<ty::TraitRef>)
866 // High-level idea: we have to decide whether to consult the
867 // cache that is specific to this scope, or to consult the
868 // global cache. We want the cache that is specific to this
869 // scope whenever where clauses might affect the result.
871 // Avoid using the master cache during coherence and just rely
872 // on the local cache. This effectively disables caching
873 // during coherence. It is really just a simplification to
874 // avoid us having to fear that coherence results "pollute"
875 // the master cache. Since coherence executes pretty quickly,
876 // it's not worth going to more trouble to increase the
877 // hit-rate I don't think.
879 return &self.param_env.selection_cache;
882 // If the trait refers to any parameters in scope, then use
883 // the cache of the param-environment.
885 cache_skol_trait_ref.input_types().iter().any(
886 |&t| ty::type_has_self(t) || ty::type_has_params(t))
888 return &self.param_env.selection_cache;
891 // If the trait refers to unbound type variables, and there
892 // are where clauses in scope, then use the local environment.
893 // If there are no where clauses in scope, which is a very
894 // common case, then we can use the global environment.
895 // See the discussion in doc.rs for more details.
897 !self.param_env.caller_obligations.is_empty()
899 cache_skol_trait_ref.input_types().iter().any(
900 |&t| ty::type_has_ty_infer(t))
902 return &self.param_env.selection_cache;
905 // Otherwise, we can use the global cache.
906 &self.tcx().selection_cache
909 fn check_candidate_cache(&mut self,
910 cache_skol_trait_ref: Rc<ty::TraitRef>)
911 -> Option<SelectionResult<Candidate>>
913 let cache = self.pick_candidate_cache(&cache_skol_trait_ref);
914 let hashmap = cache.hashmap.borrow();
915 hashmap.get(&cache_skol_trait_ref).map(|c| (*c).clone())
918 fn insert_candidate_cache(&mut self,
919 cache_skol_trait_ref: Rc<ty::TraitRef>,
920 candidate: SelectionResult<Candidate>)
922 let cache = self.pick_candidate_cache(&cache_skol_trait_ref);
923 let mut hashmap = cache.hashmap.borrow_mut();
924 hashmap.insert(cache_skol_trait_ref, candidate);
927 fn assemble_candidates(&mut self,
928 stack: &ObligationStack)
929 -> Result<CandidateSet, SelectionError>
931 // Check for overflow.
933 let ObligationStack { obligation, .. } = *stack;
935 let mut candidates = CandidateSet {
940 // Other bounds. Consider both in-scope bounds from fn decl
941 // and applicable impls. There is a certain set of precedence rules here.
943 match self.tcx().lang_items.to_builtin_kind(obligation.trait_ref.def_id) {
945 try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
949 // For the time being, we ignore user-defined impls for builtin-bounds.
950 // (And unboxed candidates only apply to the Fn/FnMut/etc traits.)
951 try!(self.assemble_unboxed_candidates(obligation, &mut candidates));
952 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
956 try!(self.assemble_candidates_from_caller_bounds(obligation, &mut candidates));
960 fn assemble_candidates_from_caller_bounds(&mut self,
961 obligation: &Obligation,
962 candidates: &mut CandidateSet)
963 -> Result<(),SelectionError>
966 * Given an obligation like `<SomeTrait for T>`, search the obligations
967 * that the caller supplied to find out whether it is listed among
970 * Never affects inference environment.
973 debug!("assemble_candidates_from_caller_bounds({})",
974 obligation.repr(self.tcx()));
976 let caller_trait_refs: Vec<Rc<ty::TraitRef>> =
977 self.param_env.caller_obligations.iter()
978 .map(|o| o.trait_ref.clone())
982 util::transitive_bounds(
983 self.tcx(), caller_trait_refs.as_slice());
985 let matching_bounds =
987 |bound| self.infcx.probe(
988 || self.match_trait_refs(obligation,
989 (*bound).clone())).is_ok());
991 let param_candidates =
993 |bound| ParamCandidate(VtableParamData { bound: bound }));
995 candidates.vec.extend(param_candidates);
1000 fn assemble_unboxed_candidates(&mut self,
1001 obligation: &Obligation,
1002 candidates: &mut CandidateSet)
1003 -> Result<(),SelectionError>
1006 * Check for the artificial impl that the compiler will create
1007 * for an obligation like `X : FnMut<..>` where `X` is an
1008 * unboxed closure type.
1010 * Note: the type parameters on an unboxed closure candidate
1011 * are modeled as *output* type parameters and hence do not
1012 * affect whether this trait is a match or not. They will be
1013 * unified during the confirmation step.
1016 let tcx = self.tcx();
1017 let kind = if Some(obligation.trait_ref.def_id) == tcx.lang_items.fn_trait() {
1018 ty::FnUnboxedClosureKind
1019 } else if Some(obligation.trait_ref.def_id) == tcx.lang_items.fn_mut_trait() {
1020 ty::FnMutUnboxedClosureKind
1021 } else if Some(obligation.trait_ref.def_id) == tcx.lang_items.fn_once_trait() {
1022 ty::FnOnceUnboxedClosureKind
1024 return Ok(()); // not a fn trait, ignore
1027 let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1028 let (closure_def_id, substs) = match ty::get(self_ty).sty {
1029 ty::ty_unboxed_closure(id, _, ref substs) => (id, substs.clone()),
1030 ty::ty_infer(ty::TyVar(_)) => {
1031 candidates.ambiguous = true;
1034 _ => { return Ok(()); }
1037 debug!("assemble_unboxed_candidates: self_ty={} obligation={}",
1038 self_ty.repr(self.tcx()),
1039 obligation.repr(self.tcx()));
1041 let closure_kind = match self.typer.unboxed_closures().borrow().get(&closure_def_id) {
1042 Some(closure) => closure.kind,
1044 self.tcx().sess.span_bug(
1045 obligation.cause.span,
1046 format!("No entry for unboxed closure: {}",
1047 closure_def_id.repr(self.tcx())).as_slice());
1051 if closure_kind == kind {
1052 candidates.vec.push(UnboxedClosureCandidate(closure_def_id, substs.clone()));
1058 fn assemble_candidates_from_impls(&mut self,
1059 obligation: &Obligation,
1060 candidates: &mut CandidateSet)
1061 -> Result<(), SelectionError>
1064 * Search for impls that might apply to `obligation`.
1067 let all_impls = self.all_impls(obligation.trait_ref.def_id);
1068 for &impl_def_id in all_impls.iter() {
1069 self.infcx.probe(|| {
1070 match self.match_impl(impl_def_id, obligation) {
1072 candidates.vec.push(ImplCandidate(impl_def_id));
1081 ///////////////////////////////////////////////////////////////////////////
1084 // Winnowing is the process of attempting to resolve ambiguity by
1085 // probing further. During the winnowing process, we unify all
1086 // type variables (ignoring skolemization) and then we also
1087 // attempt to evaluate recursive bounds to see if they are
1090 fn winnow_candidate(&mut self,
1091 stack: &ObligationStack,
1092 candidate: &Candidate)
1096 * Further evaluate `candidate` to decide whether all type parameters match
1097 * and whether nested obligations are met. Returns true if `candidate` remains
1098 * viable after this further scrutiny.
1101 debug!("winnow_candidate: candidate={}", candidate.repr(self.tcx()));
1102 self.infcx.probe(|| {
1103 let candidate = (*candidate).clone();
1104 match self.confirm_candidate(stack.obligation, candidate) {
1105 Ok(selection) => self.winnow_selection(Some(stack), selection),
1106 Err(_) => EvaluatedToErr,
1111 fn winnow_selection(&mut self,
1112 stack: Option<&ObligationStack>,
1113 selection: Selection)
1116 let mut result = EvaluatedToOk;
1117 for obligation in selection.iter_nested() {
1118 match self.evaluate_obligation_recursively(stack, obligation) {
1119 EvaluatedToErr => { return EvaluatedToErr; }
1120 EvaluatedToAmbig => { result = EvaluatedToAmbig; }
1121 EvaluatedToOk => { }
1127 fn candidate_should_be_dropped_in_favor_of(&mut self,
1128 stack: &ObligationStack,
1129 candidate_i: &Candidate,
1130 candidate_j: &Candidate)
1134 * Returns true if `candidate_i` should be dropped in favor of `candidate_j`.
1135 * This is generally true if either:
1136 * - candidate i and candidate j are equivalent; or,
1137 * - candidate i is a conrete impl and candidate j is a where clause bound,
1138 * and the concrete impl is applicable to the types in the where clause bound.
1140 * The last case refers to cases where there are blanket impls (often conditional
1141 * blanket impls) as well as a where clause. This can come down to one of two cases:
1143 * - The impl is truly unconditional (it has no where clauses
1144 * of its own), in which case the where clause is
1145 * unnecessary, because coherence requires that we would
1146 * pick that particular impl anyhow (at least so long as we
1147 * don't have specialization).
1149 * - The impl is conditional, in which case we may not have winnowed it out
1150 * because we don't know if the conditions apply, but the where clause is basically
1151 * telling us taht there is some impl, though not necessarily the one we see.
1153 * In both cases we prefer to take the where clause, which is
1154 * essentially harmless. See issue #18453 for more details of
1155 * a case where doing the opposite caused us harm.
1158 match (candidate_i, candidate_j) {
1159 (&ImplCandidate(impl_def_id), &ParamCandidate(ref vt)) => {
1160 debug!("Considering whether to drop param {} in favor of impl {}",
1161 candidate_i.repr(self.tcx()),
1162 candidate_j.repr(self.tcx()));
1164 self.infcx.probe(|| {
1166 self.rematch_impl(impl_def_id, stack.obligation);
1167 let impl_trait_ref =
1168 ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
1169 let impl_trait_ref =
1170 impl_trait_ref.subst(self.tcx(), &impl_substs);
1172 infer::RelateOutputImplTypes(stack.obligation.cause.span);
1174 .sub_trait_refs(false, origin,
1175 impl_trait_ref, vt.bound.clone())
1180 *candidate_i == *candidate_j
1185 ///////////////////////////////////////////////////////////////////////////
1188 // These cover the traits that are built-in to the language
1189 // itself. This includes `Copy` and `Sized` for sure. For the
1190 // moment, it also includes `Send` / `Sync` and a few others, but
1191 // those will hopefully change to library-defined traits in the
1194 fn assemble_builtin_bound_candidates(&mut self,
1195 bound: ty::BuiltinBound,
1196 stack: &ObligationStack,
1197 candidates: &mut CandidateSet)
1198 -> Result<(),SelectionError>
1200 // FIXME -- To be more like a normal impl, we should just
1201 // ignore the nested cases here, and instead generate nested
1202 // obligations in `confirm_candidate`. However, this doesn't
1203 // work because we require handling the recursive cases to
1204 // avoid infinite cycles (that is, with recursive types,
1205 // sometimes `Foo : Copy` only holds if `Foo : Copy`).
1207 match self.builtin_bound(bound, stack.obligation.self_ty()) {
1209 debug!("builtin_bound: bound={} nested={}",
1210 bound.repr(self.tcx()),
1211 nested.repr(self.tcx()));
1212 let data = self.vtable_builtin_data(stack.obligation, bound, nested);
1213 match self.winnow_selection(Some(stack), VtableBuiltin(data)) {
1214 EvaluatedToOk => { Ok(candidates.vec.push(BuiltinCandidate(bound))) }
1215 EvaluatedToAmbig => { Ok(candidates.ambiguous = true) }
1216 EvaluatedToErr => { Err(Unimplemented) }
1219 Ok(ParameterBuiltin) => { Ok(()) }
1220 Ok(AmbiguousBuiltin) => { Ok(candidates.ambiguous = true) }
1221 Err(e) => { Err(e) }
1225 fn builtin_bound(&mut self,
1226 bound: ty::BuiltinBound,
1228 -> Result<BuiltinBoundConditions,SelectionError>
1230 let self_ty = self.infcx.shallow_resolve(self_ty);
1231 return match ty::get(self_ty).sty {
1232 ty::ty_infer(ty::IntVar(_)) |
1233 ty::ty_infer(ty::FloatVar(_)) |
1240 // safe for everything
1244 ty::ty_uniq(referent_ty) => { // Box<T>
1256 Ok(If(vec![referent_ty]))
1261 ty::ty_ptr(ty::mt { ty: referent_ty, .. }) => { // *const T, *mut T
1270 Ok(If(vec![referent_ty]))
1275 ty::ty_closure(ref c) => {
1277 ty::UniqTraitStore => {
1278 // proc: Equivalent to `Box<FnOnce>`
1290 if c.bounds.builtin_bounds.contains(&bound) {
1298 ty::RegionTraitStore(_, mutbl) => {
1299 // ||: Equivalent to `&FnMut` or `&mut FnMut` or something like that.
1303 ast::MutMutable => Err(Unimplemented), // &mut T is affine
1304 ast::MutImmutable => Ok(If(Vec::new())), // &T is copyable
1314 if c.bounds.builtin_bounds.contains(&bound) {
1325 ty::ty_trait(box ty::TyTrait { bounds, .. }) => {
1330 ty::BoundCopy | ty::BoundSync | ty::BoundSend => {
1331 if bounds.builtin_bounds.contains(&bound) {
1340 ty::ty_rptr(_, ty::mt { ty: referent_ty, mutbl }) => {
1345 // &mut T is affine and hence never `Copy`
1346 ast::MutMutable => Err(Unimplemented),
1348 // &T is always copyable
1349 ast::MutImmutable => Ok(If(Vec::new())),
1359 // Note: technically, a region pointer is only
1360 // sendable if it has lifetime
1361 // `'static`. However, we don't take regions
1362 // into account when doing trait matching:
1363 // instead, when we decide that `T : Send`, we
1364 // will register a separate constraint with
1365 // the region inferencer that `T : 'static`
1366 // holds as well (because the trait `Send`
1367 // requires it). This will ensure that there
1368 // is no borrowed data in `T` (or else report
1369 // an inference error). The reason we do it
1370 // this way is that we do not yet *know* what
1371 // lifetime the borrowed reference has, since
1372 // we haven't finished running inference -- in
1373 // other words, there's a kind of
1374 // chicken-and-egg problem.
1375 Ok(If(vec![referent_ty]))
1380 ty::ty_vec(element_ty, ref len) => {
1385 Some(_) => Ok(If(vec![element_ty])), // [T, ..n] is copy iff T is copy
1386 None => Err(Unimplemented), // [T] is unsized and hence affine
1400 Ok(If(vec![element_ty]))
1406 // Equivalent to [u8]
1420 ty::ty_tup(ref tys) => {
1421 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1425 ty::ty_unboxed_closure(def_id, _, ref substs) => {
1426 // FIXME -- This case is tricky. In the case of by-ref
1427 // closures particularly, we need the results of
1428 // inference to decide how to reflect the type of each
1429 // upvar (the upvar may have type `T`, but the runtime
1430 // type could be `&mut`, `&`, or just `T`). For now,
1431 // though, we'll do this unsoundly and assume that all
1432 // captures are by value. Really what we ought to do
1433 // is reserve judgement and then intertwine this
1434 // analysis with closure inference.
1435 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
1436 match self.tcx().freevars.borrow().get(&def_id.node) {
1443 let tys: Vec<ty::t> =
1447 let freevar_def_id = freevar.def.def_id();
1448 self.typer.node_ty(freevar_def_id.node)
1449 .unwrap_or(ty::mk_err()).subst(self.tcx(), substs)
1457 ty::ty_struct(def_id, ref substs) => {
1458 let types: Vec<ty::t> =
1459 ty::struct_fields(self.tcx(), def_id, substs)
1463 nominal(self, bound, def_id, types)
1466 ty::ty_enum(def_id, ref substs) => {
1467 let types: Vec<ty::t> =
1468 ty::substd_enum_variants(self.tcx(), def_id, substs)
1470 .flat_map(|variant| variant.args.iter())
1473 nominal(self, bound, def_id, types)
1476 ty::ty_param(_) => {
1477 // Note: A type parameter is only considered to meet a
1478 // particular bound if there is a where clause telling
1479 // us that it does, and that case is handled by
1480 // `assemble_candidates_from_caller_bounds()`.
1481 Ok(ParameterBuiltin)
1484 ty::ty_infer(ty::TyVar(_)) => {
1485 // Unbound type variable. Might or might not have
1486 // applicable impls and so forth, depending on what
1487 // those type variables wind up being bound to.
1488 Ok(AmbiguousBuiltin)
1496 ty::ty_infer(ty::SkolemizedTy(_)) |
1497 ty::ty_infer(ty::SkolemizedIntTy(_)) => {
1498 self.tcx().sess.bug(
1500 "asked to assemble builtin bounds of unexpected type: {}",
1501 self_ty.repr(self.tcx())).as_slice());
1505 fn nominal(this: &mut SelectionContext,
1506 bound: ty::BuiltinBound,
1509 -> Result<BuiltinBoundConditions,SelectionError>
1511 // First check for markers and other nonsense.
1512 let tcx = this.tcx();
1516 Some(def_id) == tcx.lang_items.no_send_bound() ||
1517 Some(def_id) == tcx.lang_items.managed_bound()
1519 return Err(Unimplemented);
1525 Some(def_id) == tcx.lang_items.no_copy_bound() ||
1526 Some(def_id) == tcx.lang_items.managed_bound() ||
1527 ty::has_dtor(tcx, def_id)
1529 return Err(Unimplemented);
1535 Some(def_id) == tcx.lang_items.no_sync_bound() ||
1536 Some(def_id) == tcx.lang_items.managed_bound()
1538 return Err(Unimplemented);
1540 Some(def_id) == tcx.lang_items.unsafe_type()
1542 // FIXME(#13231) -- we currently consider `UnsafeCell<T>`
1543 // to always be sync. This is allow for types like `Queue`
1544 // and `Mutex`, where `Queue<T> : Sync` is `T : Send`.
1545 return Ok(If(Vec::new()));
1549 ty::BoundSized => { }
1556 ///////////////////////////////////////////////////////////////////////////
1559 // Confirmation unifies the output type parameters of the trait
1560 // with the values found in the obligation, possibly yielding a
1561 // type error. See `doc.rs` for more details.
1563 fn confirm_candidate(&mut self,
1564 obligation: &Obligation,
1565 candidate: Candidate)
1566 -> Result<Selection,SelectionError>
1568 debug!("confirm_candidate({}, {})",
1569 obligation.repr(self.tcx()),
1570 candidate.repr(self.tcx()));
1573 // FIXME -- see assemble_builtin_bound_candidates()
1574 BuiltinCandidate(_) |
1576 Ok(VtableBuiltin(VtableBuiltinData { nested: VecPerParamSpace::empty() }))
1579 ParamCandidate(param) => {
1581 try!(self.confirm_param_candidate(obligation, param))))
1584 ImplCandidate(impl_def_id) => {
1586 try!(self.confirm_impl_candidate(obligation, impl_def_id));
1587 Ok(VtableImpl(vtable_impl))
1590 UnboxedClosureCandidate(closure_def_id, substs) => {
1591 try!(self.confirm_unboxed_closure_candidate(obligation, closure_def_id, &substs));
1592 Ok(VtableUnboxedClosure(closure_def_id, substs))
1597 fn confirm_param_candidate(&mut self,
1598 obligation: &Obligation,
1599 param: VtableParamData)
1600 -> Result<VtableParamData,SelectionError>
1602 debug!("confirm_param_candidate({},{})",
1603 obligation.repr(self.tcx()),
1604 param.repr(self.tcx()));
1606 let () = try!(self.confirm(obligation.cause,
1607 obligation.trait_ref.clone(),
1608 param.bound.clone()));
1612 fn confirm_builtin_candidate(&mut self,
1613 obligation: &Obligation,
1614 bound: ty::BuiltinBound)
1615 -> Result<VtableBuiltinData<Obligation>,SelectionError>
1617 debug!("confirm_builtin_candidate({})",
1618 obligation.repr(self.tcx()));
1620 match try!(self.builtin_bound(bound, obligation.self_ty())) {
1621 If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)),
1623 ParameterBuiltin => {
1624 self.tcx().sess.span_bug(
1625 obligation.cause.span,
1626 format!("builtin bound for {} was ambig",
1627 obligation.repr(self.tcx())).as_slice());
1632 fn vtable_builtin_data(&mut self,
1633 obligation: &Obligation,
1634 bound: ty::BuiltinBound,
1636 -> VtableBuiltinData<Obligation>
1638 let obligations = nested.iter().map(|&t| {
1639 util::obligation_for_builtin_bound(
1643 obligation.recursion_depth + 1,
1645 }).collect::<Result<_, _>>();
1646 let obligations = match obligations {
1648 Err(ErrorReported) => Vec::new()
1650 let obligations = VecPerParamSpace::new(obligations, Vec::new(),
1651 Vec::new(), Vec::new());
1652 VtableBuiltinData { nested: obligations }
1655 fn confirm_impl_candidate(&mut self,
1656 obligation: &Obligation,
1657 impl_def_id: ast::DefId)
1658 -> Result<VtableImplData<Obligation>,SelectionError>
1660 debug!("confirm_impl_candidate({},{})",
1661 obligation.repr(self.tcx()),
1662 impl_def_id.repr(self.tcx()));
1664 // First, create the substitutions by matching the impl again,
1665 // this time not in a probe.
1666 let substs = self.rematch_impl(impl_def_id, obligation);
1667 Ok(self.vtable_impl(impl_def_id, substs, obligation.cause, obligation.recursion_depth + 1))
1670 fn vtable_impl(&mut self,
1671 impl_def_id: ast::DefId,
1673 cause: ObligationCause,
1674 recursion_depth: uint)
1675 -> VtableImplData<Obligation>
1677 let impl_obligations =
1678 self.impl_obligations(cause,
1682 VtableImplData { impl_def_id: impl_def_id,
1684 nested: impl_obligations }
1687 fn confirm_unboxed_closure_candidate(&mut self,
1688 obligation: &Obligation,
1689 closure_def_id: ast::DefId,
1691 -> Result<(),SelectionError>
1693 debug!("confirm_unboxed_closure_candidate({},{},{})",
1694 obligation.repr(self.tcx()),
1695 closure_def_id.repr(self.tcx()),
1696 substs.repr(self.tcx()));
1698 let closure_type = match self.typer.unboxed_closures().borrow().get(&closure_def_id) {
1699 Some(closure) => closure.closure_type.clone(),
1701 self.tcx().sess.span_bug(
1702 obligation.cause.span,
1703 format!("No entry for unboxed closure: {}",
1704 closure_def_id.repr(self.tcx())).as_slice());
1708 // FIXME(pcwalton): This is a bogus thing to do, but
1709 // it'll do for now until we get the new trait-bound
1710 // region skolemization working.
1711 let (_, new_signature) =
1712 regionmanip::replace_late_bound_regions(
1714 closure_type.sig.binder_id,
1716 |br| self.infcx.next_region_var(
1717 infer::LateBoundRegion(obligation.cause.span, br)));
1719 let arguments_tuple = new_signature.inputs[0];
1720 let trait_ref = Rc::new(ty::TraitRef {
1721 def_id: obligation.trait_ref.def_id,
1722 substs: Substs::new_trait(
1723 vec![arguments_tuple.subst(self.tcx(), substs),
1724 new_signature.output.unwrap().subst(self.tcx(), substs)],
1727 obligation.self_ty())
1730 self.confirm(obligation.cause,
1731 obligation.trait_ref.clone(),
1735 ///////////////////////////////////////////////////////////////////////////
1738 // Matching is a common path used for both evaluation and
1739 // confirmation. It basically unifies types that appear in impls
1740 // and traits. This does affect the surrounding environment;
1741 // therefore, when used during evaluation, match routines must be
1742 // run inside of a `probe()` so that their side-effects are
1745 fn rematch_impl(&mut self,
1746 impl_def_id: ast::DefId,
1747 obligation: &Obligation)
1750 match self.match_impl(impl_def_id, obligation) {
1755 self.tcx().sess.bug(
1756 format!("Impl {} was matchable against {} but now is not",
1757 impl_def_id.repr(self.tcx()),
1758 obligation.repr(self.tcx()))
1764 fn match_impl(&mut self,
1765 impl_def_id: ast::DefId,
1766 obligation: &Obligation)
1767 -> Result<Substs, ()>
1769 let impl_substs = util::fresh_substs_for_impl(self.infcx,
1770 obligation.cause.span,
1773 let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
1774 impl_def_id).unwrap();
1775 let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
1778 match self.match_trait_refs(obligation, impl_trait_ref) {
1779 Ok(()) => Ok(impl_substs),
1784 fn match_trait_refs(&mut self,
1785 obligation: &Obligation,
1786 trait_ref: Rc<ty::TraitRef>)
1789 debug!("match_trait_refs: obligation={} trait_ref={}",
1790 obligation.repr(self.tcx()),
1791 trait_ref.repr(self.tcx()));
1793 let origin = infer::RelateOutputImplTypes(obligation.cause.span);
1794 match self.infcx.sub_trait_refs(false,
1797 obligation.trait_ref.clone()) {
1803 fn match_inherent_impl(&mut self,
1804 impl_def_id: ast::DefId,
1805 obligation_cause: ObligationCause,
1806 obligation_self_ty: ty::t)
1807 -> Result<Substs,()>
1810 * Determines whether the self type declared against
1811 * `impl_def_id` matches `obligation_self_ty`. If successful,
1812 * returns the substitutions used to make them match. See
1813 * `match_impl()`. For example, if `impl_def_id` is declared
1816 * impl<T:Copy> Foo for ~T { ... }
1818 * and `obligation_self_ty` is `int`, we'd back an `Err(_)`
1819 * result. But if `obligation_self_ty` were `~int`, we'd get
1823 // Create fresh type variables for each type parameter declared
1825 let impl_substs = util::fresh_substs_for_impl(self.infcx,
1826 obligation_cause.span,
1829 // Find the self type for the impl.
1830 let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty;
1831 let impl_self_ty = impl_self_ty.subst(self.tcx(), &impl_substs);
1833 debug!("match_impl_self_types(obligation_self_ty={}, impl_self_ty={})",
1834 obligation_self_ty.repr(self.tcx()),
1835 impl_self_ty.repr(self.tcx()));
1837 match self.match_self_types(obligation_cause,
1839 obligation_self_ty) {
1841 debug!("Matched impl_substs={}", impl_substs.repr(self.tcx()));
1851 fn match_self_types(&mut self,
1852 cause: ObligationCause,
1854 // The self type provided by the impl/caller-obligation:
1855 provided_self_ty: ty::t,
1857 // The self type the obligation is for:
1858 required_self_ty: ty::t)
1861 // FIXME(#5781) -- equating the types is stronger than
1862 // necessary. Should consider variance of trait w/r/t Self.
1864 let origin = infer::RelateSelfType(cause.span);
1865 match self.infcx.eq_types(false,
1874 ///////////////////////////////////////////////////////////////////////////
1877 // The final step of selection: once we know how an obligation is
1878 // is resolved, we confirm that selection in order to have
1879 // side-effects on the typing environment. This step also unifies
1880 // the output type parameters from the obligation with those found
1881 // on the impl/bound, which may yield type errors.
1883 fn confirm_impl_vtable(&mut self,
1884 impl_def_id: ast::DefId,
1885 obligation_cause: ObligationCause,
1886 obligation_trait_ref: Rc<ty::TraitRef>,
1888 -> Result<(), SelectionError>
1891 * Relates the output type parameters from an impl to the
1892 * trait. This may lead to type errors. The confirmation step
1893 * is separated from the main match procedure because these
1894 * type errors do not cause us to select another impl.
1896 * As an example, consider matching the obligation
1897 * `Iterator<char> for Elems<int>` using the following impl:
1899 * impl<T> Iterator<T> for Elems<T> { ... }
1901 * The match phase will succeed with substitution `T=int`.
1902 * The confirm step will then try to unify `int` and `char`
1903 * and yield an error.
1906 let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
1907 impl_def_id).unwrap();
1908 let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
1910 self.confirm(obligation_cause, obligation_trait_ref, impl_trait_ref)
1913 fn confirm(&mut self,
1914 obligation_cause: ObligationCause,
1915 obligation_trait_ref: Rc<ty::TraitRef>,
1916 expected_trait_ref: Rc<ty::TraitRef>)
1917 -> Result<(), SelectionError>
1920 * After we have determined which impl applies, and with what
1921 * substitutions, there is one last step. We have to go back
1922 * and relate the "output" type parameters from the obligation
1923 * to the types that are specified in the impl.
1925 * For example, imagine we have:
1927 * impl<T> Iterator<T> for Vec<T> { ... }
1929 * and our obligation is `Iterator<Foo> for Vec<int>` (note
1930 * the mismatch in the obligation types). Up until this step,
1931 * no error would be reported: the self type is `Vec<int>`,
1932 * and that matches `Vec<T>` with the substitution `T=int`.
1933 * At this stage, we could then go and check that the type
1934 * parameters to the `Iterator` trait match.
1935 * (In terms of the parameters, the `expected_trait_ref`
1936 * here would be `Iterator<int> for Vec<int>`, and the
1937 * `obligation_trait_ref` would be `Iterator<Foo> for Vec<int>`.
1939 * Note that this checking occurs *after* the impl has
1940 * selected, because these output type parameters should not
1941 * affect the selection of the impl. Therefore, if there is a
1942 * mismatch, we report an error to the user.
1945 let origin = infer::RelateOutputImplTypes(obligation_cause.span);
1947 let obligation_trait_ref = obligation_trait_ref.clone();
1948 match self.infcx.sub_trait_refs(false,
1950 expected_trait_ref.clone(),
1951 obligation_trait_ref) {
1953 Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, e))
1957 ///////////////////////////////////////////////////////////////////////////
1960 fn push_stack<'o,'s:'o>(&mut self,
1961 previous_stack: Option<&'s ObligationStack<'s>>,
1962 obligation: &'o Obligation)
1963 -> ObligationStack<'o>
1965 let skol_trait_ref = obligation.trait_ref.fold_with(&mut self.skolemizer);
1968 obligation: obligation,
1969 skol_trait_ref: skol_trait_ref,
1970 previous: previous_stack.map(|p| p), // FIXME variance
1974 fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
1976 * Returns set of all impls for a given trait.
1979 ty::populate_implementations_for_trait_if_necessary(self.tcx(),
1981 match self.tcx().trait_impls.borrow().get(&trait_def_id) {
1983 Some(impls) => impls.borrow().clone()
1987 fn impl_obligations(&self,
1988 cause: ObligationCause,
1989 recursion_depth: uint,
1990 impl_def_id: ast::DefId,
1991 impl_substs: &Substs)
1992 -> VecPerParamSpace<Obligation>
1994 let impl_generics = ty::lookup_item_type(self.tcx(),
1995 impl_def_id).generics;
1996 util::obligations_for_generics(self.tcx(), cause, recursion_depth,
1997 &impl_generics, impl_substs)
2001 impl Repr for Candidate {
2002 fn repr(&self, tcx: &ty::ctxt) -> String {
2004 ErrorCandidate => format!("ErrorCandidate"),
2005 BuiltinCandidate(b) => format!("BuiltinCandidate({})", b),
2006 UnboxedClosureCandidate(c, ref s) => {
2007 format!("MatchedUnboxedClosureCandidate({},{})", c, s.repr(tcx))
2009 ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
2010 ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
2015 impl SelectionCache {
2016 pub fn new() -> SelectionCache {
2018 hashmap: RefCell::new(HashMap::new())
2023 impl<'o> ObligationStack<'o> {
2024 fn iter(&self) -> Option<&ObligationStack> {
2029 impl<'o> Iterator<&'o ObligationStack<'o>> for Option<&'o ObligationStack<'o>> {
2030 fn next(&mut self) -> Option<&'o ObligationStack<'o>> {
2043 impl<'o> Repr for ObligationStack<'o> {
2044 fn repr(&self, tcx: &ty::ctxt) -> String {
2045 format!("ObligationStack({})",
2046 self.obligation.repr(tcx))
2050 impl EvaluationResult {
2051 fn may_apply(&self) -> bool {
2053 EvaluatedToOk | EvaluatedToAmbig => true,
2054 EvaluatedToErr => false,
2059 impl MethodMatchResult {
2060 pub fn may_apply(&self) -> bool {
2062 MethodMatched(_) => true,
2063 MethodAmbiguous(_) => true,
2064 MethodDidNotMatch => false,