]>
Commit | Line | Data |
---|---|---|
a1dfa0c6 XL |
1 | # Trait resolution (old-style) |
2 | ||
6a06907d XL |
3 | <!-- toc --> |
4 | ||
a1dfa0c6 XL |
5 | This chapter describes the general process of _trait resolution_ and points out |
6 | some non-obvious things. | |
7 | ||
8 | **Note:** This chapter (and its subchapters) describe how the trait | |
9 | solver **currently** works. However, we are in the process of | |
10 | designing a new trait solver. If you'd prefer to read about *that*, | |
6a06907d | 11 | see [*this* subchapter](./chalk.html). |
a1dfa0c6 XL |
12 | |
13 | ## Major concepts | |
14 | ||
15 | Trait resolution is the process of pairing up an impl with each | |
16 | reference to a trait. So, for example, if there is a generic function like: | |
17 | ||
18 | ```rust,ignore | |
19 | fn clone_slice<T:Clone>(x: &[T]) -> Vec<T> { ... } | |
20 | ``` | |
21 | ||
22 | and then a call to that function: | |
23 | ||
24 | ```rust,ignore | |
25 | let v: Vec<isize> = clone_slice(&[1, 2, 3]) | |
26 | ``` | |
27 | ||
28 | it is the job of trait resolution to figure out whether there exists an impl of | |
29 | (in this case) `isize : Clone`. | |
30 | ||
31 | Note that in some cases, like generic functions, we may not be able to | |
32 | find a specific impl, but we can figure out that the caller must | |
33 | provide an impl. For example, consider the body of `clone_slice`: | |
34 | ||
35 | ```rust,ignore | |
36 | fn clone_slice<T:Clone>(x: &[T]) -> Vec<T> { | |
37 | let mut v = Vec::new(); | |
38 | for e in &x { | |
39 | v.push((*e).clone()); // (*) | |
40 | } | |
41 | } | |
42 | ``` | |
43 | ||
44 | The line marked `(*)` is only legal if `T` (the type of `*e`) | |
45 | implements the `Clone` trait. Naturally, since we don't know what `T` | |
46 | is, we can't find the specific impl; but based on the bound `T:Clone`, | |
47 | we can say that there exists an impl which the caller must provide. | |
48 | ||
49 | We use the term *obligation* to refer to a trait reference in need of | |
50 | an impl. Basically, the trait resolution system resolves an obligation | |
51 | by proving that an appropriate impl does exist. | |
52 | ||
53 | During type checking, we do not store the results of trait selection. | |
54 | We simply wish to verify that trait selection will succeed. Then | |
55 | later, at trans time, when we have all concrete types available, we | |
56 | can repeat the trait selection to choose an actual implementation, which | |
57 | will then be generated in the output binary. | |
58 | ||
59 | ## Overview | |
60 | ||
61 | Trait resolution consists of three major parts: | |
62 | ||
63 | - **Selection**: Deciding how to resolve a specific obligation. For | |
64 | example, selection might decide that a specific obligation can be | |
65 | resolved by employing an impl which matches the `Self` type, or by using a | |
66 | parameter bound (e.g. `T: Trait`). In the case of an impl, selecting one | |
67 | obligation can create *nested obligations* because of where clauses | |
68 | on the impl itself. It may also require evaluating those nested | |
69 | obligations to resolve ambiguities. | |
70 | ||
71 | - **Fulfillment**: The fulfillment code is what tracks that obligations | |
72 | are completely fulfilled. Basically it is a worklist of obligations | |
73 | to be selected: once selection is successful, the obligation is | |
74 | removed from the worklist and any nested obligations are enqueued. | |
75 | ||
76 | - **Coherence**: The coherence checks are intended to ensure that there | |
77 | are never overlapping impls, where two impls could be used with | |
78 | equal precedence. | |
79 | ||
80 | ## Selection | |
81 | ||
82 | Selection is the process of deciding whether an obligation can be | |
83 | resolved and, if so, how it is to be resolved (via impl, where clause, etc). | |
84 | The main interface is the `select()` function, which takes an obligation | |
85 | and returns a `SelectionResult`. There are three possible outcomes: | |
86 | ||
87 | - `Ok(Some(selection))` – yes, the obligation can be resolved, and | |
88 | `selection` indicates how. If the impl was resolved via an impl, | |
89 | then `selection` may also indicate nested obligations that are required | |
90 | by the impl. | |
91 | ||
92 | - `Ok(None)` – we are not yet sure whether the obligation can be | |
93 | resolved or not. This happens most commonly when the obligation | |
94 | contains unbound type variables. | |
95 | ||
96 | - `Err(err)` – the obligation definitely cannot be resolved due to a | |
97 | type error or because there are no impls that could possibly apply. | |
98 | ||
99 | The basic algorithm for selection is broken into two big phases: | |
100 | candidate assembly and confirmation. | |
101 | ||
102 | Note that because of how lifetime inference works, it is not possible to | |
103 | give back immediate feedback as to whether a unification or subtype | |
104 | relationship between lifetimes holds or not. Therefore, lifetime | |
105 | matching is *not* considered during selection. This is reflected in | |
106 | the fact that subregion assignment is infallible. This may yield | |
107 | lifetime constraints that will later be found to be in error (in | |
108 | contrast, the non-lifetime-constraints have already been checked | |
109 | during selection and can never cause an error, though naturally they | |
110 | may lead to other errors downstream). | |
111 | ||
112 | ### Candidate assembly | |
113 | ||
114 | Searches for impls/where-clauses/etc that might | |
115 | possibly be used to satisfy the obligation. Each of those is called | |
116 | a candidate. To avoid ambiguity, we want to find exactly one | |
117 | candidate that is definitively applicable. In some cases, we may not | |
118 | know whether an impl/where-clause applies or not – this occurs when | |
119 | the obligation contains unbound inference variables. | |
120 | ||
6a06907d XL |
121 | The subroutines that decide whether a particular impl/where-clause/etc applies |
122 | to a particular obligation are collectively referred to as the process of | |
123 | _matching_. As of <!-- date: 2021-01 --> January 2021, this amounts to unifying | |
124 | the `Self` types, but in the future we may also recursively consider some of the | |
125 | nested obligations, in the case of an impl. | |
a1dfa0c6 XL |
126 | |
127 | **TODO**: what does "unifying the `Self` types" mean? The `Self` of the | |
128 | obligation with that of an impl? | |
129 | ||
130 | The basic idea for candidate assembly is to do a first pass in which | |
131 | we identify all possible candidates. During this pass, all that we do | |
132 | is try and unify the type parameters. (In particular, we ignore any | |
133 | nested where clauses.) Presuming that this unification succeeds, the | |
134 | impl is added as a candidate. | |
135 | ||
136 | Once this first pass is done, we can examine the set of candidates. If | |
137 | it is a singleton set, then we are done: this is the only impl in | |
138 | scope that could possibly apply. Otherwise, we can winnow down the set | |
139 | of candidates by using where clauses and other conditions. If this | |
140 | reduced set yields a single, unambiguous entry, we're good to go, | |
141 | otherwise the result is considered ambiguous. | |
142 | ||
143 | #### The basic process: Inferring based on the impls we see | |
144 | ||
145 | This process is easier if we work through some examples. Consider | |
146 | the following trait: | |
147 | ||
148 | ```rust,ignore | |
149 | trait Convert<Target> { | |
150 | fn convert(&self) -> Target; | |
151 | } | |
152 | ``` | |
153 | ||
154 | This trait just has one method. It's about as simple as it gets. It | |
155 | converts from the (implicit) `Self` type to the `Target` type. If we | |
156 | wanted to permit conversion between `isize` and `usize`, we might | |
157 | implement `Convert` like so: | |
158 | ||
159 | ```rust,ignore | |
160 | impl Convert<usize> for isize { ... } // isize -> usize | |
161 | impl Convert<isize> for usize { ... } // usize -> isize | |
162 | ``` | |
163 | ||
164 | Now imagine there is some code like the following: | |
165 | ||
166 | ```rust,ignore | |
167 | let x: isize = ...; | |
168 | let y = x.convert(); | |
169 | ``` | |
170 | ||
171 | The call to convert will generate a trait reference `Convert<$Y> for | |
172 | isize`, where `$Y` is the type variable representing the type of | |
173 | `y`. Of the two impls we can see, the only one that matches is | |
174 | `Convert<usize> for isize`. Therefore, we can | |
175 | select this impl, which will cause the type of `$Y` to be unified to | |
176 | `usize`. (Note that while assembling candidates, we do the initial | |
177 | unifications in a transaction, so that they don't affect one another.) | |
178 | ||
179 | **TODO**: The example says we can "select" the impl, but this section is | |
180 | talking specifically about candidate assembly. Does this mean we can sometimes | |
181 | skip confirmation? Or is this poor wording? | |
182 | **TODO**: Is the unification of `$Y` part of trait resolution or type | |
183 | inference? Or is this not the same type of "inference variable" as in type | |
184 | inference? | |
185 | ||
186 | #### Winnowing: Resolving ambiguities | |
187 | ||
188 | But what happens if there are multiple impls where all the types | |
189 | unify? Consider this example: | |
190 | ||
191 | ```rust,ignore | |
192 | trait Get { | |
193 | fn get(&self) -> Self; | |
194 | } | |
195 | ||
6a06907d XL |
196 | impl<T: Copy> Get for T { |
197 | fn get(&self) -> T { | |
198 | *self | |
199 | } | |
a1dfa0c6 XL |
200 | } |
201 | ||
6a06907d XL |
202 | impl<T: Get> Get for Box<T> { |
203 | fn get(&self) -> Box<T> { | |
204 | Box::new(<T>::get(self)) | |
205 | } | |
a1dfa0c6 XL |
206 | } |
207 | ``` | |
208 | ||
209 | What happens when we invoke `get_it(&Box::new(1_u16))`, for example? In this | |
210 | case, the `Self` type is `Box<u16>` – that unifies with both impls, | |
211 | because the first applies to all types `T`, and the second to all | |
212 | `Box<T>`. In order for this to be unambiguous, the compiler does a *winnowing* | |
213 | pass that considers `where` clauses | |
214 | and attempts to remove candidates. In this case, the first impl only | |
215 | applies if `Box<u16> : Copy`, which doesn't hold. After winnowing, | |
216 | then, we are left with just one candidate, so we can proceed. | |
217 | ||
218 | #### `where` clauses | |
219 | ||
220 | Besides an impl, the other major way to resolve an obligation is via a | |
221 | where clause. The selection process is always given a [parameter | |
222 | environment] which contains a list of where clauses, which are | |
223 | basically obligations that we can assume are satisfiable. We will iterate | |
224 | over that list and check whether our current obligation can be found | |
225 | in that list. If so, it is considered satisfied. More precisely, we | |
226 | want to check whether there is a where-clause obligation that is for | |
227 | the same trait (or some subtrait) and which can match against the obligation. | |
228 | ||
229 | [parameter environment]: ../param_env.html | |
230 | ||
231 | Consider this simple example: | |
232 | ||
233 | ```rust,ignore | |
234 | trait A1 { | |
235 | fn do_a1(&self); | |
236 | } | |
237 | trait A2 : A1 { ... } | |
238 | ||
239 | trait B { | |
240 | fn do_b(&self); | |
241 | } | |
242 | ||
243 | fn foo<X:A2+B>(x: X) { | |
244 | x.do_a1(); // (*) | |
245 | x.do_b(); // (#) | |
246 | } | |
247 | ``` | |
248 | ||
249 | In the body of `foo`, clearly we can use methods of `A1`, `A2`, or `B` | |
250 | on variable `x`. The line marked `(*)` will incur an obligation `X: A1`, | |
251 | while the line marked `(#)` will incur an obligation `X: B`. Meanwhile, | |
252 | the parameter environment will contain two where-clauses: `X : A2` and `X : B`. | |
253 | For each obligation, then, we search this list of where-clauses. The | |
254 | obligation `X: B` trivially matches against the where-clause `X: B`. | |
255 | To resolve an obligation `X:A1`, we would note that `X:A2` implies that `X:A1`. | |
256 | ||
257 | ### Confirmation | |
258 | ||
259 | _Confirmation_ unifies the output type parameters of the trait with the | |
260 | values found in the obligation, possibly yielding a type error. | |
261 | ||
262 | Suppose we have the following variation of the `Convert` example in the | |
263 | previous section: | |
264 | ||
265 | ```rust,ignore | |
266 | trait Convert<Target> { | |
267 | fn convert(&self) -> Target; | |
268 | } | |
269 | ||
270 | impl Convert<usize> for isize { ... } // isize -> usize | |
271 | impl Convert<isize> for usize { ... } // usize -> isize | |
272 | ||
273 | let x: isize = ...; | |
274 | let y: char = x.convert(); // NOTE: `y: char` now! | |
275 | ``` | |
276 | ||
277 | Confirmation is where an error would be reported because the impl specified | |
278 | that `Target` would be `usize`, but the obligation reported `char`. Hence the | |
279 | result of selection would be an error. | |
280 | ||
281 | Note that the candidate impl is chosen based on the `Self` type, but | |
282 | confirmation is done based on (in this case) the `Target` type parameter. | |
283 | ||
284 | ### Selection during translation | |
285 | ||
286 | As mentioned above, during type checking, we do not store the results of trait | |
287 | selection. At trans time, we repeat the trait selection to choose a particular | |
288 | impl for each method call. In this second selection, we do not consider any | |
289 | where-clauses to be in scope because we know that each resolution will resolve | |
290 | to a particular impl. | |
291 | ||
292 | One interesting twist has to do with nested obligations. In general, in trans, | |
293 | we only need to do a "shallow" selection for an obligation. That is, we wish to | |
294 | identify which impl applies, but we do not (yet) need to decide how to select | |
295 | any nested obligations. Nonetheless, we *do* currently do a complete resolution, | |
296 | and that is because it can sometimes inform the results of type inference. | |
297 | That is, we do not have the full substitutions in terms of the type variables | |
298 | of the impl available to us, so we must run trait selection to figure | |
299 | everything out. | |
300 | ||
301 | **TODO**: is this still talking about trans? | |
302 | ||
303 | Here is an example: | |
304 | ||
305 | ```rust,ignore | |
306 | trait Foo { ... } | |
307 | impl<U, T:Bar<U>> Foo for Vec<T> { ... } | |
308 | ||
309 | impl Bar<usize> for isize { ... } | |
310 | ``` | |
311 | ||
312 | After one shallow round of selection for an obligation like `Vec<isize> | |
313 | : Foo`, we would know which impl we want, and we would know that | |
314 | `T=isize`, but we do not know the type of `U`. We must select the | |
315 | nested obligation `isize : Bar<U>` to find out that `U=usize`. | |
316 | ||
317 | It would be good to only do *just as much* nested resolution as | |
318 | necessary. Currently, though, we just do a full resolution. |