]>
Commit | Line | Data |
---|---|---|
dc9dc135 XL |
1 | # Member constraints |
2 | ||
3 | A member constraint `'m member of ['c_1..'c_N]` expresses that the | |
4 | region `'m` must be *equal* to some **choice regions** `'c_i` (for | |
5 | some `i`). These constraints cannot be expressed by users, but they | |
6 | arise from `impl Trait` due to its lifetime capture rules. Consider a | |
7 | function such as the following: | |
8 | ||
416331ca | 9 | ```rust,ignore |
dc9dc135 XL |
10 | fn make(a: &'a u32, b: &'b u32) -> impl Trait<'a, 'b> { .. } |
11 | ``` | |
12 | ||
13 | Here, the true return type (often called the "hidden type") is only | |
14 | permitted to capture the lifetimes `'a` or `'b`. You can kind of see | |
15 | this more clearly by desugaring that `impl Trait` return type into its | |
16 | more explicit form: | |
17 | ||
416331ca | 18 | ```rust,ignore |
dc9dc135 XL |
19 | type MakeReturn<'x, 'y> = impl Trait<'x, 'y>; |
20 | fn make(a: &'a u32, b: &'b u32) -> MakeReturn<'a, 'b> { .. } | |
21 | ``` | |
22 | ||
23 | Here, the idea is that the hidden type must be some type that could | |
24 | have been written in place of the `impl Trait<'x, 'y>` -- but clearly | |
25 | such a type can only reference the regions `'x` or `'y` (or | |
26 | `'static`!), as those are the only names in scope. This limitation is | |
27 | then translated into a restriction to only access `'a` or `'b` because | |
28 | we are returning `MakeReturn<'a, 'b>`, where `'x` and `'y` have been | |
29 | replaced with `'a` and `'b` respectively. | |
30 | ||
31 | ## Detailed example | |
32 | ||
33 | To help us explain member constraints in more detail, let's spell out | |
34 | the `make` example in a bit more detail. First off, let's assume that | |
35 | you have some dummy trait: | |
36 | ||
416331ca | 37 | ```rust,ignore |
dc9dc135 XL |
38 | trait Trait<'a, 'b> { } |
39 | impl<T> Trait<'_, '_> for T { } | |
40 | ``` | |
41 | ||
42 | and this is the `make` function (in desugared form): | |
43 | ||
416331ca | 44 | ```rust,ignore |
dc9dc135 XL |
45 | type MakeReturn<'x, 'y> = impl Trait<'x, 'y>; |
46 | fn make(a: &'a u32, b: &'b u32) -> MakeReturn<'a, 'b> { | |
47 | (a, b) | |
48 | } | |
49 | ``` | |
50 | ||
51 | What happens in this case is that the return type will be `(&'0 u32, &'1 u32)`, | |
52 | where `'0` and `'1` are fresh region variables. We will have the following | |
53 | region constraints: | |
54 | ||
416331ca | 55 | ```txt |
dc9dc135 XL |
56 | '0 live at {L} |
57 | '1 live at {L} | |
58 | 'a: '0 | |
59 | 'b: '1 | |
60 | '0 member of ['a, 'b, 'static] | |
61 | '1 member of ['a, 'b, 'static] | |
62 | ``` | |
63 | ||
64 | Here the "liveness set" `{L}` corresponds to that subset of the body | |
65 | where `'0` and `'1` are live -- basically the point from where the | |
66 | return tuple is constructed to where it is returned (in fact, `'0` and | |
67 | `'1` might have slightly different liveness sets, but that's not very | |
68 | interesting to the point we are illustrating here). | |
69 | ||
70 | The `'a: '0` and `'b: '1` constraints arise from subtyping. When we | |
71 | construct the `(a, b)` value, it will be assigned type `(&'0 u32, &'1 | |
72 | u32)` -- the region variables reflect that the lifetimes of these | |
73 | references could be made smaller. For this value to be created from | |
74 | `a` and `b`, however, we do require that: | |
75 | ||
416331ca | 76 | ```txt |
dc9dc135 XL |
77 | (&'a u32, &'b u32) <: (&'0 u32, &'1 u32) |
78 | ``` | |
79 | ||
80 | which means in turn that `&'a u32 <: &'0 u32` and hence that `'a: '0` | |
81 | (and similarly that `&'b u32 <: &'1 u32`, `'b: '1`). | |
82 | ||
83 | Note that if we ignore member constraints, the value of `'0` would be | |
84 | inferred to some subset of the function body (from the liveness | |
85 | constraints, which we did not write explicitly). It would never become | |
86 | `'a`, because there is no need for it too -- we have a constraint that | |
87 | `'a: '0`, but that just puts a "cap" on how *large* `'0` can grow to | |
88 | become. Since we compute the *minimal* value that we can, we are happy | |
89 | to leave `'0` as being just equal to the liveness set. This is where | |
90 | member constraints come in. | |
91 | ||
92 | ## Choices are always lifetime parameters | |
93 | ||
94 | At present, the "choice" regions from a member constraint are always | |
95 | lifetime parameters from the current function. This falls out from the | |
96 | placement of impl Trait, though in the future it may not be the case. | |
97 | We take some advantage of this fact, as it simplifies the current | |
98 | code. In particular, we don't have to consider a case like `'0 member | |
99 | of ['1, 'static]`, in which the value of both `'0` and `'1` are being | |
60c5eb7d | 100 | inferred and hence changing. See [rust-lang/rust#61773][#61773] for more |
dc9dc135 XL |
101 | information. |
102 | ||
103 | [#61773]: https://github.com/rust-lang/rust/issues/61773 | |
104 | ||
105 | ## Applying member constraints | |
106 | ||
107 | Member constraints are a bit more complex than other forms of | |
108 | constraints. This is because they have a "or" quality to them -- that | |
109 | is, they describe multiple choices that we must select from. E.g., in | |
110 | our example constraint `'0 member of ['a, 'b, 'static]`, it might be | |
111 | that `'0` is equal to `'a`, `'b`, *or* `'static`. How can we pick the | |
112 | correct one? What we currently do is to look for a *minimal choice* | |
113 | -- if we find one, then we will grow `'0` to be equal to that minimal | |
114 | choice. To find that minimal choice, we take two factors into | |
115 | consideration: lower and upper bounds. | |
116 | ||
117 | ### Lower bounds | |
118 | ||
119 | The *lower bounds* are those lifetimes that `'0` *must outlive* -- | |
120 | i.e., that `'0` must be larger than. In fact, when it comes time to | |
121 | apply member constraints, we've already *computed* the lower bounds of | |
122 | `'0` because we computed its minimal value (or at least, the lower | |
123 | bounds considering everything but member constraints). | |
124 | ||
125 | Let `LB` be the current value of `'0`. We know then that `'0: LB` must | |
126 | hold, whatever the final value of `'0` is. Therefore, we can rule out | |
127 | any choice `'choice` where `'choice: LB` does not hold. | |
128 | ||
129 | Unfortunately, in our example, this is not very helpful. The lower | |
130 | bound for `'0` will just be the liveness set `{L}`, and we know that | |
131 | all the lifetime parameters outlive that set. So we are left with the | |
132 | same set of choices here. (But in other examples, particularly those | |
133 | with different variance, lower bound constraints may be relevant.) | |
134 | ||
135 | ### Upper bounds | |
136 | ||
137 | The *upper bounds* are those lifetimes that *must outlive* `'0` -- | |
138 | i.e., that `'0` must be *smaller* than. In our example, this would be | |
139 | `'a`, because we have the constraint that `'a: '0`. In more complex | |
140 | examples, the chain may be more indirect. | |
141 | ||
142 | We can use upper bounds to rule out members in a very similar way to | |
143 | lower lower bounds. If UB is some upper bound, then we know that `UB: | |
144 | '0` must hold, so we can rule out any choice `'choice` where `UB: | |
145 | 'choice` does not hold. | |
146 | ||
147 | In our example, we would be able to reduce our choice set from `['a, | |
148 | 'b, 'static]` to just `['a]`. This is because `'0` has an upper bound | |
149 | of `'a`, and neither `'a: 'b` nor `'a: 'static` is known to hold. | |
150 | ||
151 | (For notes on how we collect upper bounds in the implementation, see | |
152 | [the section below](#collecting).) | |
153 | ||
154 | ### Minimal choice | |
155 | ||
156 | After applying lower and upper bounds, we can still sometimes have | |
157 | multiple possibilities. For example, imagine a variant of our example | |
158 | using types with the opposite variance. In that case, we would have | |
159 | the constraint `'0: 'a` instead of `'a: '0`. Hence the current value | |
160 | of `'0` would be `{L, 'a}`. Using this as a lower bound, we would be | |
161 | able to narrow down the member choices to `['a, 'static]` because `'b: | |
162 | 'a` is not known to hold (but `'a: 'a` and `'static: 'a` do hold). We | |
163 | would not have any upper bounds, so that would be our final set of choices. | |
164 | ||
165 | In that case, we apply the **minimal choice** rule -- basically, if | |
166 | one of our choices if smaller than the others, we can use that. In | |
167 | this case, we would opt for `'a` (and not `'static`). | |
168 | ||
169 | This choice is consistent with the general 'flow' of region | |
170 | propagation, which always aims to compute a minimal value for the | |
171 | region being inferred. However, it is somewhat arbitrary. | |
172 | ||
173 | <a name="collecting"></a> | |
174 | ||
175 | ### Collecting upper bounds in the implementation | |
176 | ||
177 | In practice, computing upper bounds is a bit inconvenient, because our | |
178 | data structures are setup for the opposite. What we do is to compute | |
416331ca | 179 | the **reverse SCC graph** (we do this lazily and cache the result) -- |
dc9dc135 XL |
180 | that is, a graph where `'a: 'b` induces an edge `SCC('b) -> |
181 | SCC('a)`. Like the normal SCC graph, this is a DAG. We can then do a | |
182 | depth-first search starting from `SCC('0)` in this graph. This will | |
416331ca | 183 | take us to all the SCCs that must outlive `'0`. |
dc9dc135 XL |
184 | |
185 | One wrinkle is that, as we walk the "upper bound" SCCs, their values | |
186 | will not yet have been fully computed. However, we **have** already | |
187 | applied their liveness constraints, so we have some information about | |
188 | their value. In particular, for any regions representing lifetime | |
189 | parameters, their value will contain themselves (i.e., the initial | |
190 | value for `'a` includes `'a` and the value for `'b` contains `'b`). So | |
191 | we can collect all of the lifetime parameters that are reachable, | |
192 | which is precisely what we are interested in. |