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