]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
1 | // The outlines relation `T: 'a` or `'a: 'b`. This code frequently |
2 | // refers to rules defined in RFC 1214 (`OutlivesFooBar`), so see that | |
3 | // RFC for reference. | |
4 | ||
29967ef6 | 5 | use rustc_data_structures::sso::SsoHashSet; |
c295e0f8 | 6 | use rustc_middle::ty::subst::{GenericArg, GenericArgKind}; |
9ffffee4 | 7 | use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt}; |
c295e0f8 | 8 | use smallvec::{smallvec, SmallVec}; |
e9174d1e SL |
9 | |
10 | #[derive(Debug)] | |
11 | pub enum Component<'tcx> { | |
7cac9316 | 12 | Region(ty::Region<'tcx>), |
e9174d1e SL |
13 | Param(ty::ParamTy), |
14 | UnresolvedInferenceVariable(ty::InferTy), | |
15 | ||
16 | // Projections like `T::Foo` are tricky because a constraint like | |
17 | // `T::Foo: 'a` can be satisfied in so many ways. There may be a | |
18 | // where-clause that says `T::Foo: 'a`, or the defining trait may | |
19 | // include a bound like `type Foo: 'static`, or -- in the most | |
20 | // conservative way -- we can prove that `T: 'a` (more generally, | |
21 | // that all components in the projection outlive `'a`). This code | |
22 | // is not in a position to judge which is the best technique, so | |
23 | // we just product the projection as a component and leave it to | |
24 | // the consumer to decide (but see `EscapingProjection` below). | |
9c376795 | 25 | Alias(ty::AliasTy<'tcx>), |
e9174d1e SL |
26 | |
27 | // In the case where a projection has escaping regions -- meaning | |
28 | // regions bound within the type itself -- we always use | |
29 | // the most conservative rule, which requires that all components | |
30 | // outlive the bound. So for example if we had a type like this: | |
31 | // | |
32 | // for<'a> Trait1< <T as Trait2<'a,'b>>::Foo > | |
33 | // ~~~~~~~~~~~~~~~~~~~~~~~~~ | |
34 | // | |
35 | // then the inner projection (underlined) has an escaping region | |
36 | // `'a`. We consider that outer trait `'c` to meet a bound if `'b` | |
37 | // outlives `'b: 'c`, and we don't consider whether the trait | |
38 | // declares that `Foo: 'static` etc. Therefore, we just return the | |
39 | // free components of such a projection (in this case, `'b`). | |
40 | // | |
41 | // However, in the future, we may want to get smarter, and | |
42 | // actually return a "higher-ranked projection" here. Therefore, | |
43 | // we mark that these components are part of an escaping | |
44 | // projection, so that implied bounds code can avoid relying on | |
45 | // them. This gives us room to improve the regionck reasoning in | |
46 | // the future without breaking backwards compat. | |
9c376795 | 47 | EscapingAlias(Vec<Component<'tcx>>), |
e9174d1e SL |
48 | } |
49 | ||
c295e0f8 XL |
50 | /// Push onto `out` all the things that must outlive `'a` for the condition |
51 | /// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**. | |
a2a8927a | 52 | pub fn push_outlives_components<'tcx>( |
c295e0f8 XL |
53 | tcx: TyCtxt<'tcx>, |
54 | ty0: Ty<'tcx>, | |
55 | out: &mut SmallVec<[Component<'tcx>; 4]>, | |
56 | ) { | |
57 | let mut visited = SsoHashSet::new(); | |
58 | compute_components(tcx, ty0, out, &mut visited); | |
59 | debug!("components({:?}) = {:?}", ty0, out); | |
dfeec247 | 60 | } |
e9174d1e | 61 | |
a2a8927a | 62 | fn compute_components<'tcx>( |
6c58768f XL |
63 | tcx: TyCtxt<'tcx>, |
64 | ty: Ty<'tcx>, | |
65 | out: &mut SmallVec<[Component<'tcx>; 4]>, | |
29967ef6 | 66 | visited: &mut SsoHashSet<GenericArg<'tcx>>, |
6c58768f | 67 | ) { |
dfeec247 XL |
68 | // Descend through the types, looking for the various "base" |
69 | // components and collecting them into `out`. This is not written | |
70 | // with `collect()` because of the need to sometimes skip subtrees | |
71 | // in the `subtys` iterator (e.g., when encountering a | |
72 | // projection). | |
1b1a35ee | 73 | match *ty.kind() { |
ba9703b0 XL |
74 | ty::FnDef(_, substs) => { |
75 | // HACK(eddyb) ignore lifetimes found shallowly in `substs`. | |
76 | // This is inconsistent with `ty::Adt` (including all substs) | |
77 | // and with `ty::Closure` (ignoring all substs other than | |
78 | // upvars, of which a `ty::FnDef` doesn't have any), but | |
79 | // consistent with previous (accidental) behavior. | |
80 | // See https://github.com/rust-lang/rust/issues/70917 | |
81 | // for further background and discussion. | |
f9f354fc | 82 | for child in substs { |
ba9703b0 XL |
83 | match child.unpack() { |
84 | GenericArgKind::Type(ty) => { | |
6c58768f | 85 | compute_components(tcx, ty, out, visited); |
ba9703b0 XL |
86 | } |
87 | GenericArgKind::Lifetime(_) => {} | |
88 | GenericArgKind::Const(_) => { | |
6c58768f | 89 | compute_components_recursive(tcx, child, out, visited); |
ba9703b0 XL |
90 | } |
91 | } | |
92 | } | |
93 | } | |
94 | ||
f9f354fc XL |
95 | ty::Array(element, _) => { |
96 | // Don't look into the len const as it doesn't affect regions | |
6c58768f | 97 | compute_components(tcx, element, out, visited); |
f9f354fc XL |
98 | } |
99 | ||
ba9703b0 | 100 | ty::Closure(_, ref substs) => { |
29967ef6 XL |
101 | let tupled_ty = substs.as_closure().tupled_upvars_ty(); |
102 | compute_components(tcx, tupled_ty, out, visited); | |
e9174d1e | 103 | } |
e9174d1e | 104 | |
ba9703b0 | 105 | ty::Generator(_, ref substs, _) => { |
ea8adc8c | 106 | // Same as the closure case |
29967ef6 XL |
107 | let tupled_ty = substs.as_generator().tupled_upvars_ty(); |
108 | compute_components(tcx, tupled_ty, out, visited); | |
ea8adc8c | 109 | |
2c00a5a8 XL |
110 | // We ignore regions in the generator interior as we don't |
111 | // want these to affect region inference | |
ea8adc8c XL |
112 | } |
113 | ||
2c00a5a8 | 114 | // All regions are bound inside a witness |
9ffffee4 | 115 | ty::GeneratorWitness(..) | ty::GeneratorWitnessMIR(..) => (), |
2c00a5a8 | 116 | |
a7813a04 XL |
117 | // OutlivesTypeParameterEnv -- the actual checking that `X:'a` |
118 | // is implied by the environment is done in regionck. | |
b7449926 | 119 | ty::Param(p) => { |
a7813a04 XL |
120 | out.push(Component::Param(p)); |
121 | } | |
e9174d1e | 122 | |
a7813a04 XL |
123 | // For projections, we prefer to generate an obligation like |
124 | // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the | |
125 | // regionck more ways to prove that it holds. However, | |
126 | // regionck is not (at least currently) prepared to deal with | |
127 | // higher-ranked regions that may appear in the | |
5e7ed085 | 128 | // trait-ref. Therefore, if we see any higher-ranked regions, |
a7813a04 XL |
129 | // we simply fallback to the most restrictive rule, which |
130 | // requires that `Pi: 'a` for all `i`. | |
9c376795 FG |
131 | ty::Alias(_, alias_ty) => { |
132 | if !alias_ty.has_escaping_bound_vars() { | |
a7813a04 XL |
133 | // best case: no escaping regions, so push the |
134 | // projection and skip the subtree (thus generating no | |
135 | // constraints for Pi). This defers the choice between | |
136 | // the rules OutlivesProjectionEnv, | |
137 | // OutlivesProjectionTraitDef, and | |
138 | // OutlivesProjectionComponents to regionck. | |
9c376795 | 139 | out.push(Component::Alias(alias_ty)); |
a7813a04 XL |
140 | } else { |
141 | // fallback case: hard code | |
9c376795 | 142 | // OutlivesProjectionComponents. Continue walking |
a7813a04 | 143 | // through and constrain Pi. |
ba9703b0 | 144 | let mut subcomponents = smallvec![]; |
29967ef6 | 145 | let mut subvisited = SsoHashSet::new(); |
49aad941 | 146 | compute_alias_components_recursive(tcx, ty, &mut subcomponents, &mut subvisited); |
9c376795 | 147 | out.push(Component::EscapingAlias(subcomponents.into_iter().collect())); |
a7813a04 | 148 | } |
e9174d1e | 149 | } |
e9174d1e | 150 | |
c30ab7b3 SL |
151 | // We assume that inference variables are fully resolved. |
152 | // So, if we encounter an inference variable, just record | |
153 | // the unresolved variable as a component. | |
b7449926 | 154 | ty::Infer(infer_ty) => { |
c30ab7b3 | 155 | out.push(Component::UnresolvedInferenceVariable(infer_ty)); |
e9174d1e | 156 | } |
e9174d1e | 157 | |
a7813a04 XL |
158 | // Most types do not introduce any region binders, nor |
159 | // involve any other subtle cases, and so the WF relation | |
160 | // simply constraints any regions referenced directly by | |
161 | // the type and then visits the types that are lexically | |
162 | // contained within. (The comments refer to relevant rules | |
163 | // from RFC1214.) | |
b7449926 XL |
164 | ty::Bool | // OutlivesScalar |
165 | ty::Char | // OutlivesScalar | |
166 | ty::Int(..) | // OutlivesScalar | |
167 | ty::Uint(..) | // OutlivesScalar | |
168 | ty::Float(..) | // OutlivesScalar | |
169 | ty::Never | // ... | |
170 | ty::Adt(..) | // OutlivesNominalType | |
b7449926 XL |
171 | ty::Foreign(..) | // OutlivesNominalType |
172 | ty::Str | // OutlivesScalar (ish) | |
b7449926 XL |
173 | ty::Slice(..) | // ... |
174 | ty::RawPtr(..) | // ... | |
175 | ty::Ref(..) | // OutlivesReference | |
176 | ty::Tuple(..) | // ... | |
b7449926 | 177 | ty::FnPtr(_) | // OutlivesFunction (*) |
ba9703b0 | 178 | ty::Dynamic(..) | // OutlivesObject, OutlivesFragment (*) |
a1dfa0c6 XL |
179 | ty::Placeholder(..) | |
180 | ty::Bound(..) | | |
f035d41b | 181 | ty::Error(_) => { |
ba9703b0 XL |
182 | // (*) Function pointers and trait objects are both binders. |
183 | // In the RFC, this means we would add the bound regions to | |
9c376795 | 184 | // the "bound regions list". In our representation, no such |
a7813a04 XL |
185 | // list is maintained explicitly, because bound regions |
186 | // themselves can be readily identified. | |
6c58768f | 187 | compute_components_recursive(tcx, ty.into(), out, visited); |
e9174d1e SL |
188 | } |
189 | } | |
dfeec247 | 190 | } |
e9174d1e | 191 | |
064997fb FG |
192 | /// Collect [Component]s for *all* the substs of `parent`. |
193 | /// | |
194 | /// This should not be used to get the components of `parent` itself. | |
195 | /// Use [push_outlives_components] instead. | |
49aad941 FG |
196 | pub(super) fn compute_alias_components_recursive<'tcx>( |
197 | tcx: TyCtxt<'tcx>, | |
198 | alias_ty: Ty<'tcx>, | |
199 | out: &mut SmallVec<[Component<'tcx>; 4]>, | |
200 | visited: &mut SsoHashSet<GenericArg<'tcx>>, | |
201 | ) { | |
202 | let ty::Alias(kind, alias_ty) = alias_ty.kind() else { bug!() }; | |
203 | let opt_variances = if *kind == ty::Opaque { tcx.variances_of(alias_ty.def_id) } else { &[] }; | |
204 | for (index, child) in alias_ty.substs.iter().enumerate() { | |
205 | if opt_variances.get(index) == Some(&ty::Bivariant) { | |
206 | continue; | |
207 | } | |
208 | if !visited.insert(child) { | |
209 | continue; | |
210 | } | |
211 | match child.unpack() { | |
212 | GenericArgKind::Type(ty) => { | |
213 | compute_components(tcx, ty, out, visited); | |
214 | } | |
215 | GenericArgKind::Lifetime(lt) => { | |
216 | // Ignore late-bound regions. | |
217 | if !lt.is_late_bound() { | |
218 | out.push(Component::Region(lt)); | |
219 | } | |
220 | } | |
221 | GenericArgKind::Const(_) => { | |
222 | compute_components_recursive(tcx, child, out, visited); | |
223 | } | |
224 | } | |
225 | } | |
226 | } | |
227 | ||
228 | /// Collect [Component]s for *all* the substs of `parent`. | |
229 | /// | |
230 | /// This should not be used to get the components of `parent` itself. | |
231 | /// Use [push_outlives_components] instead. | |
232 | fn compute_components_recursive<'tcx>( | |
ba9703b0 XL |
233 | tcx: TyCtxt<'tcx>, |
234 | parent: GenericArg<'tcx>, | |
235 | out: &mut SmallVec<[Component<'tcx>; 4]>, | |
29967ef6 | 236 | visited: &mut SsoHashSet<GenericArg<'tcx>>, |
ba9703b0 | 237 | ) { |
5099ac24 | 238 | for child in parent.walk_shallow(visited) { |
ba9703b0 XL |
239 | match child.unpack() { |
240 | GenericArgKind::Type(ty) => { | |
6c58768f | 241 | compute_components(tcx, ty, out, visited); |
ba9703b0 XL |
242 | } |
243 | GenericArgKind::Lifetime(lt) => { | |
244 | // Ignore late-bound regions. | |
245 | if !lt.is_late_bound() { | |
246 | out.push(Component::Region(lt)); | |
247 | } | |
248 | } | |
249 | GenericArgKind::Const(_) => { | |
6c58768f | 250 | compute_components_recursive(tcx, child, out, visited); |
ba9703b0 XL |
251 | } |
252 | } | |
e9174d1e | 253 | } |
e9174d1e | 254 | } |