3 This document describes the general process and points out some non-obvious
8 Trait resolution is the process of pairing up an impl with each
9 reference to a trait. So, for example, if there is a generic function like:
12 fn clone_slice<T:Clone>(x: &[T]) -> Vec<T> { /*...*/ }
15 and then a call to that function:
18 let v: Vec<isize> = clone_slice(&[1, 2, 3])
21 it is the job of trait resolution to figure out (in which case)
22 whether there exists an impl of `isize : Clone`
24 Note that in some cases, like generic functions, we may not be able to
25 find a specific impl, but we can figure out that the caller must
26 provide an impl. To see what I mean, consider the body of `clone_slice`:
29 fn clone_slice<T:Clone>(x: &[T]) -> Vec<T> {
30 let mut v = Vec::new();
32 v.push((*e).clone()); // (*)
37 The line marked `(*)` is only legal if `T` (the type of `*e`)
38 implements the `Clone` trait. Naturally, since we don't know what `T`
39 is, we can't find the specific impl; but based on the bound `T:Clone`,
40 we can say that there exists an impl which the caller must provide.
42 We use the term *obligation* to refer to a trait reference in need of
47 Trait resolution consists of three major parts:
49 - SELECTION: Deciding how to resolve a specific obligation. For
50 example, selection might decide that a specific obligation can be
51 resolved by employing an impl which matches the self type, or by
52 using a parameter bound. In the case of an impl, Selecting one
53 obligation can create *nested obligations* because of where clauses
54 on the impl itself. It may also require evaluating those nested
55 obligations to resolve ambiguities.
57 - FULFILLMENT: The fulfillment code is what tracks that obligations
58 are completely fulfilled. Basically it is a worklist of obligations
59 to be selected: once selection is successful, the obligation is
60 removed from the worklist and any nested obligations are enqueued.
62 - COHERENCE: The coherence checks are intended to ensure that there
63 are never overlapping impls, where two impls could be used with
68 Selection is the process of deciding whether an obligation can be
69 resolved and, if so, how it is to be resolved (via impl, where clause, etc).
70 The main interface is the `select()` function, which takes an obligation
71 and returns a `SelectionResult`. There are three possible outcomes:
73 - `Ok(Some(selection))` -- yes, the obligation can be resolved, and
74 `selection` indicates how. If the impl was resolved via an impl,
75 then `selection` may also indicate nested obligations that are required
78 - `Ok(None)` -- we are not yet sure whether the obligation can be
79 resolved or not. This happens most commonly when the obligation
80 contains unbound type variables.
82 - `Err(err)` -- the obligation definitely cannot be resolved due to a
83 type error, or because there are no impls that could possibly apply,
86 The basic algorithm for selection is broken into two big phases:
87 candidate assembly and confirmation.
89 ### Candidate assembly
91 Searches for impls/where-clauses/etc that might
92 possibly be used to satisfy the obligation. Each of those is called
93 a candidate. To avoid ambiguity, we want to find exactly one
94 candidate that is definitively applicable. In some cases, we may not
95 know whether an impl/where-clause applies or not -- this occurs when
96 the obligation contains unbound inference variables.
98 The basic idea for candidate assembly is to do a first pass in which
99 we identify all possible candidates. During this pass, all that we do
100 is try and unify the type parameters. (In particular, we ignore any
101 nested where clauses.) Presuming that this unification succeeds, the
102 impl is added as a candidate.
104 Once this first pass is done, we can examine the set of candidates. If
105 it is a singleton set, then we are done: this is the only impl in
106 scope that could possibly apply. Otherwise, we can winnow down the set
107 of candidates by using where clauses and other conditions. If this
108 reduced set yields a single, unambiguous entry, we're good to go,
109 otherwise the result is considered ambiguous.
111 #### The basic process: Inferring based on the impls we see
113 This process is easier if we work through some examples. Consider
117 trait Convert<Target> {
118 fn convert(&self) -> Target;
122 This trait just has one method. It's about as simple as it gets. It
123 converts from the (implicit) `Self` type to the `Target` type. If we
124 wanted to permit conversion between `isize` and `usize`, we might
125 implement `Convert` like so:
128 impl Convert<usize> for isize { /*...*/ } // isize -> usize
129 impl Convert<isize> for usize { /*...*/ } // usize -> isize
132 Now imagine there is some code like the following:
139 The call to convert will generate a trait reference `Convert<$Y> for
140 isize`, where `$Y` is the type variable representing the type of
141 `y`. When we match this against the two impls we can see, we will find
142 that only one remains: `Convert<usize> for isize`. Therefore, we can
143 select this impl, which will cause the type of `$Y` to be unified to
144 `usize`. (Note that while assembling candidates, we do the initial
145 unifications in a transaction, so that they don't affect one another.)
147 There are tests to this effect in src/test/run-pass:
149 traits-multidispatch-infer-convert-source-and-target.rs
150 traits-multidispatch-infer-convert-target.rs
152 #### Winnowing: Resolving ambiguities
154 But what happens if there are multiple impls where all the types
155 unify? Consider this example:
159 fn get(&self) -> Self;
162 impl<T:Copy> Get for T {
163 fn get(&self) -> T { *self }
166 impl<T:Get> Get for Box<T> {
167 fn get(&self) -> Box<T> { box get_it(&**self) }
171 What happens when we invoke `get_it(&box 1_u16)`, for example? In this
172 case, the `Self` type is `Box<u16>` -- that unifies with both impls,
173 because the first applies to all types, and the second to all
174 boxes. In the olden days we'd have called this ambiguous. But what we
175 do now is do a second *winnowing* pass that considers where clauses
176 and attempts to remove candidates -- in this case, the first impl only
177 applies if `Box<u16> : Copy`, which doesn't hold. After winnowing,
178 then, we are left with just one candidate, so we can proceed. There is
179 a test of this in `src/test/run-pass/traits-conditional-dispatch.rs`.
183 The subroutines that decide whether a particular impl/where-clause/etc
184 applies to a particular obligation. At the moment, this amounts to
185 unifying the self types, but in the future we may also recursively
186 consider some of the nested obligations, in the case of an impl.
188 #### Lifetimes and selection
190 Because of how that lifetime inference works, it is not possible to
191 give back immediate feedback as to whether a unification or subtype
192 relationship between lifetimes holds or not. Therefore, lifetime
193 matching is *not* considered during selection. This is reflected in
194 the fact that subregion assignment is infallible. This may yield
195 lifetime constraints that will later be found to be in error (in
196 contrast, the non-lifetime-constraints have already been checked
197 during selection and can never cause an error, though naturally they
198 may lead to other errors downstream).
202 Besides an impl, the other major way to resolve an obligation is via a
203 where clause. The selection process is always given a *parameter
204 environment* which contains a list of where clauses, which are
205 basically obligations that can assume are satisfiable. We will iterate
206 over that list and check whether our current obligation can be found
207 in that list, and if so it is considered satisfied. More precisely, we
208 want to check whether there is a where-clause obligation that is for
209 the same trait (or some subtrait) and for which the self types match,
210 using the definition of *matching* given above.
212 Consider this simple example:
216 trait A2 : A1 { /*...*/ }
220 fn foo<X:A2+B> { /*...*/ }
223 Clearly we can use methods offered by `A1`, `A2`, or `B` within the
224 body of `foo`. In each case, that will incur an obligation like `X :
225 A1` or `X : A2`. The parameter environment will contain two
226 where-clauses, `X : A2` and `X : B`. For each obligation, then, we
227 search this list of where-clauses. To resolve an obligation `X:A1`,
228 we would note that `X:A2` implies that `X:A1`.
232 Confirmation unifies the output type parameters of the trait with the
233 values found in the obligation, possibly yielding a type error. If we
234 return to our example of the `Convert` trait from the previous
235 section, confirmation is where an error would be reported, because the
236 impl specified that `T` would be `usize`, but the obligation reported
237 `char`. Hence the result of selection would be an error.
239 ### Selection during translation
241 During type checking, we do not store the results of trait selection.
242 We simply wish to verify that trait selection will succeed. Then
243 later, at trans time, when we have all concrete types available, we
244 can repeat the trait selection. In this case, we do not consider any
245 where-clauses to be in scope. We know that therefore each resolution
246 will resolve to a particular impl.
248 One interesting twist has to do with nested obligations. In general, in trans,
249 we only need to do a "shallow" selection for an obligation. That is, we wish to
250 identify which impl applies, but we do not (yet) need to decide how to select
251 any nested obligations. Nonetheless, we *do* currently do a complete resolution,
252 and that is because it can sometimes inform the results of type inference. That is,
253 we do not have the full substitutions in terms of the type variables of the impl available
254 to us, so we must run trait selection to figure everything out.
259 trait Foo { /*...*/ }
260 impl<U,T:Bar<U>> Foo for Vec<T> { /*...*/ }
262 impl Bar<usize> for isize { /*...*/ }
265 After one shallow round of selection for an obligation like `Vec<isize>
266 : Foo`, we would know which impl we want, and we would know that
267 `T=isize`, but we do not know the type of `U`. We must select the
268 nested obligation `isize : Bar<U>` to find out that `U=usize`.
270 It would be good to only do *just as much* nested resolution as
271 necessary. Currently, though, we just do a full resolution.
273 # Higher-ranked trait bounds
275 One of the more subtle concepts at work are *higher-ranked trait
276 bounds*. An example of such a bound is `for<'a> MyTrait<&'a isize>`.
277 Let's walk through how selection on higher-ranked trait references
280 ## Basic matching and skolemization leaks
282 Let's walk through the test `compile-fail/hrtb-just-for-static.rs` to see
283 how it works. The test starts with the trait `Foo`:
287 fn foo(&self, x: X) { }
291 Let's say we have a function `want_hrtb` that wants a type which
292 implements `Foo<&'a isize>` for any `'a`:
295 fn want_hrtb<T>() where T : for<'a> Foo<&'a isize> { ... }
298 Now we have a struct `AnyInt` that implements `Foo<&'a isize>` for any
303 impl<'a> Foo<&'a isize> for AnyInt { }
306 And the question is, does `AnyInt : for<'a> Foo<&'a isize>`? We want the
307 answer to be yes. The algorithm for figuring it out is closely related
308 to the subtyping for higher-ranked types (which is described in
309 `middle::infer::higher_ranked::doc`, but also in a [paper by SPJ] that
310 I recommend you read).
312 1. Skolemize the obligation.
313 2. Match the impl against the skolemized obligation.
314 3. Check for skolemization leaks.
316 [paper by SPJ]: http://research.microsoft.com/en-us/um/people/simonpj/papers/higher-rank/
318 So let's work through our example. The first thing we would do is to
319 skolemize the obligation, yielding `AnyInt : Foo<&'0 isize>` (here `'0`
320 represents skolemized region #0). Note that now have no quantifiers;
321 in terms of the compiler type, this changes from a `ty::PolyTraitRef`
322 to a `TraitRef`. We would then create the `TraitRef` from the impl,
323 using fresh variables for it's bound regions (and thus getting
324 `Foo<&'$a isize>`, where `'$a` is the inference variable for `'a`). Next
325 we relate the two trait refs, yielding a graph with the constraint
326 that `'0 == '$a`. Finally, we check for skolemization "leaks" -- a
327 leak is basically any attempt to relate a skolemized region to another
328 skolemized region, or to any region that pre-existed the impl match.
329 The leak check is done by searching from the skolemized region to find
330 the set of regions that it is related to in any way. This is called
331 the "taint" set. To pass the check, that set must consist *solely* of
332 itself and region variables from the impl. If the taint set includes
333 any other region, then the match is a failure. In this case, the taint
334 set for `'0` is `{'0, '$a}`, and hence the check will succeed.
336 Let's consider a failure case. Imagine we also have a struct
340 impl Foo<&'static isize> for StaticInt;
343 We want the obligation `StaticInt : for<'a> Foo<&'a isize>` to be
344 considered unsatisfied. The check begins just as before. `'a` is
345 skolemized to `'0` and the impl trait reference is instantiated to
346 `Foo<&'static isize>`. When we relate those two, we get a constraint
347 like `'static == '0`. This means that the taint set for `'0` is `{'0,
348 'static}`, which fails the leak check.
350 ## Higher-ranked trait obligations
352 Once the basic matching is done, we get to another interesting topic:
353 how to deal with impl obligations. I'll work through a simple example
354 here. Imagine we have the traits `Foo` and `Bar` and an associated impl:
358 fn foo(&self, x: X) { }
362 fn bar(&self, x: X) { }
365 impl<X,F> Foo<X> for F
371 Now let's say we have a obligation `for<'a> Foo<&'a isize>` and we match
372 this impl. What obligation is generated as a result? We want to get
373 `for<'a> Bar<&'a isize>`, but how does that happen?
375 After the matching, we are in a position where we have a skolemized
376 substitution like `X => &'0 isize`. If we apply this substitution to the
377 impl obligations, we get `F : Bar<&'0 isize>`. Obviously this is not
378 directly usable because the skolemized region `'0` cannot leak out of
381 What we do is to create an inverse mapping from the taint set of `'0`
382 back to the original bound region (`'a`, here) that `'0` resulted
383 from. (This is done in `higher_ranked::plug_leaks`). We know that the
384 leak check passed, so this taint set consists solely of the skolemized
385 region itself plus various intermediate region variables. We then walk
386 the trait-reference and convert every region in that taint set back to
387 a late-bound region, so in this case we'd wind up with `for<'a> F :
390 # Caching and subtle considerations therewith
392 In general we attempt to cache the results of trait selection. This
393 is a somewhat complex process. Part of the reason for this is that we
394 want to be able to cache results even when all the types in the trait
395 reference are not fully known. In that case, it may happen that the
396 trait selection process is also influencing type variables, so we have
397 to be able to not only cache the *result* of the selection process,
398 but *replay* its effects on the type variables.
402 The high-level idea of how the cache works is that we first replace
403 all unbound inference variables with skolemized versions. Therefore,
404 if we had a trait reference `usize : Foo<$1>`, where `$n` is an unbound
405 inference variable, we might replace it with `usize : Foo<%0>`, where
406 `%n` is a skolemized type. We would then look this up in the cache.
407 If we found a hit, the hit would tell us the immediate next step to
408 take in the selection process: i.e., apply impl #22, or apply where
409 clause `X : Foo<Y>`. Let's say in this case there is no hit.
410 Therefore, we search through impls and where clauses and so forth, and
411 we come to the conclusion that the only possible impl is this one,
415 impl Foo<isize> for usize { ... } // Impl #22
418 We would then record in the cache `usize : Foo<%0> ==>
419 ImplCandidate(22)`. Next we would confirm `ImplCandidate(22)`, which
420 would (as a side-effect) unify `$1` with `isize`.
422 Now, at some later time, we might come along and see a `usize :
423 Foo<$3>`. When skolemized, this would yield `usize : Foo<%0>`, just as
424 before, and hence the cache lookup would succeed, yielding
425 `ImplCandidate(22)`. We would confirm `ImplCandidate(22)` which would
426 (as a side-effect) unify `$3` with `isize`.
428 ## Where clauses and the local vs global cache
430 One subtle interaction is that the results of trait lookup will vary
431 depending on what where clauses are in scope. Therefore, we actually
432 have *two* caches, a local and a global cache. The local cache is
433 attached to the `ParamEnv` and the global cache attached to the
434 `tcx`. We use the local cache whenever the result might depend on the
435 where clauses that are in scope. The determination of which cache to
436 use is done by the method `pick_candidate_cache` in `select.rs`. At
437 the moment, we use a very simple, conservative rule: if there are any
438 where-clauses in scope, then we use the local cache. We used to try
439 and draw finer-grained distinctions, but that led to a serious of
440 annoying and weird bugs like #22019 and #18290. This simple rule seems
441 to be pretty clearly safe and also still retains a very high hit rate
442 (~95% when compiling rustc).
446 Defined in the `specialize` module.
448 The basic strategy is to build up a *specialization graph* during
449 coherence checking. Insertion into the graph locates the right place
450 to put an impl in the specialization hierarchy; if there is no right
451 place (due to partial overlap but no containment), you get an overlap
452 error. Specialization is consulted when selecting an impl (of course),
453 and the graph is consulted when propagating defaults down the
454 specialization hierarchy.
456 You might expect that the specialization graph would be used during
457 selection -- i.e., when actually performing specialization. This is
458 not done for two reasons:
460 - It's merely an optimization: given a set of candidates that apply,
461 we can determine the most specialized one by comparing them directly
462 for specialization, rather than consulting the graph. Given that we
463 also cache the results of selection, the benefit of this
464 optimization is questionable.
466 - To build the specialization graph in the first place, we need to use
467 selection (because we need to determine whether one impl specializes
468 another). Dealing with this reentrancy would require some additional
469 mode switch for selection. Given that there seems to be no strong
470 reason to use the graph anyway, we stick with a simpler approach in
471 selection, and use the graph only for propagating default
474 Trait impl selection can succeed even when multiple impls can apply,
475 as long as they are part of the same specialization family. In that
476 case, it returns a *single* impl on success -- this is the most
477 specialized impl *known* to apply. However, if there are any inference
478 variables in play, the returned impl may not be the actual impl we
479 will use at trans time. Thus, we take special care to avoid projecting
480 associated types unless either (1) the associated type does not use
481 `default` and thus cannot be overridden or (2) all input types are