]>
Commit | Line | Data |
---|---|---|
cdc7bbd5 XL |
1 | //! Check whether a type is representable. |
2 | use rustc_data_structures::stable_map::FxHashMap; | |
3 | use rustc_hir as hir; | |
4 | use rustc_middle::ty::{self, Ty, TyCtxt}; | |
5 | use rustc_span::Span; | |
6 | use std::cmp; | |
7 | ||
8 | /// Describes whether a type is representable. For types that are not | |
9 | /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to | |
10 | /// distinguish between types that are recursive with themselves and types that | |
11 | /// contain a different recursive type. These cases can therefore be treated | |
12 | /// differently when reporting errors. | |
13 | /// | |
14 | /// The ordering of the cases is significant. They are sorted so that cmp::max | |
15 | /// will keep the "more erroneous" of two values. | |
16 | #[derive(Clone, PartialOrd, Ord, Eq, PartialEq, Debug)] | |
17 | pub enum Representability { | |
18 | Representable, | |
19 | ContainsRecursive, | |
5e7ed085 FG |
20 | /// Return a list of types that are included in themselves: |
21 | /// the spans where they are self-included, and (if found) | |
22 | /// the HirId of the FieldDef that defines the self-inclusion. | |
23 | SelfRecursive(Vec<(Span, Option<hir::HirId>)>), | |
cdc7bbd5 XL |
24 | } |
25 | ||
26 | /// Check whether a type is representable. This means it cannot contain unboxed | |
27 | /// structural recursion. This check is needed for structs and enums. | |
5e7ed085 FG |
28 | pub fn ty_is_representable<'tcx>( |
29 | tcx: TyCtxt<'tcx>, | |
30 | ty: Ty<'tcx>, | |
31 | sp: Span, | |
32 | field_id: Option<hir::HirId>, | |
33 | ) -> Representability { | |
cdc7bbd5 XL |
34 | debug!("is_type_representable: {:?}", ty); |
35 | // To avoid a stack overflow when checking an enum variant or struct that | |
17df50a5 XL |
36 | // contains a different, structurally recursive type, maintain a stack of |
37 | // seen types and check recursion for each of them (issues #3008, #3779, | |
38 | // #74224, #84611). `shadow_seen` contains the full stack and `seen` only | |
39 | // the one for the current type (e.g. if we have structs A and B, B contains | |
40 | // a field of type A, and we're currently looking at B, then `seen` will be | |
41 | // cleared when recursing to check A, but `shadow_seen` won't, so that we | |
42 | // can catch cases of mutual recursion where A also contains B). | |
cdc7bbd5 | 43 | let mut seen: Vec<Ty<'_>> = Vec::new(); |
5e7ed085 | 44 | let mut shadow_seen: Vec<ty::AdtDef<'tcx>> = Vec::new(); |
cdc7bbd5 | 45 | let mut representable_cache = FxHashMap::default(); |
17df50a5 XL |
46 | let mut force_result = false; |
47 | let r = is_type_structurally_recursive( | |
48 | tcx, | |
17df50a5 XL |
49 | &mut seen, |
50 | &mut shadow_seen, | |
51 | &mut representable_cache, | |
52 | ty, | |
5e7ed085 FG |
53 | sp, |
54 | field_id, | |
17df50a5 XL |
55 | &mut force_result, |
56 | ); | |
cdc7bbd5 XL |
57 | debug!("is_type_representable: {:?} is {:?}", ty, r); |
58 | r | |
59 | } | |
60 | ||
61 | // Iterate until something non-representable is found | |
62 | fn fold_repr<It: Iterator<Item = Representability>>(iter: It) -> Representability { | |
63 | iter.fold(Representability::Representable, |r1, r2| match (r1, r2) { | |
64 | (Representability::SelfRecursive(v1), Representability::SelfRecursive(v2)) => { | |
65 | Representability::SelfRecursive(v1.into_iter().chain(v2).collect()) | |
66 | } | |
67 | (r1, r2) => cmp::max(r1, r2), | |
68 | }) | |
69 | } | |
70 | ||
71 | fn are_inner_types_recursive<'tcx>( | |
72 | tcx: TyCtxt<'tcx>, | |
cdc7bbd5 | 73 | seen: &mut Vec<Ty<'tcx>>, |
5e7ed085 | 74 | shadow_seen: &mut Vec<ty::AdtDef<'tcx>>, |
cdc7bbd5 XL |
75 | representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, |
76 | ty: Ty<'tcx>, | |
5e7ed085 FG |
77 | sp: Span, |
78 | field_id: Option<hir::HirId>, | |
17df50a5 | 79 | force_result: &mut bool, |
cdc7bbd5 | 80 | ) -> Representability { |
17df50a5 | 81 | debug!("are_inner_types_recursive({:?}, {:?}, {:?})", ty, seen, shadow_seen); |
cdc7bbd5 | 82 | match ty.kind() { |
5e7ed085 | 83 | ty::Tuple(fields) => { |
cdc7bbd5 | 84 | // Find non representable |
5e7ed085 | 85 | fold_repr(fields.iter().map(|ty| { |
17df50a5 XL |
86 | is_type_structurally_recursive( |
87 | tcx, | |
17df50a5 XL |
88 | seen, |
89 | shadow_seen, | |
90 | representable_cache, | |
91 | ty, | |
5e7ed085 FG |
92 | sp, |
93 | field_id, | |
17df50a5 XL |
94 | force_result, |
95 | ) | |
96 | })) | |
cdc7bbd5 XL |
97 | } |
98 | // Fixed-length vectors. | |
99 | // FIXME(#11924) Behavior undecided for zero-length vectors. | |
17df50a5 XL |
100 | ty::Array(ty, _) => is_type_structurally_recursive( |
101 | tcx, | |
17df50a5 XL |
102 | seen, |
103 | shadow_seen, | |
104 | representable_cache, | |
5099ac24 | 105 | *ty, |
5e7ed085 FG |
106 | sp, |
107 | field_id, | |
17df50a5 XL |
108 | force_result, |
109 | ), | |
cdc7bbd5 XL |
110 | ty::Adt(def, substs) => { |
111 | // Find non representable fields with their spans | |
112 | fold_repr(def.all_fields().map(|field| { | |
113 | let ty = field.ty(tcx, substs); | |
5e7ed085 FG |
114 | let (sp, field_id) = match field |
115 | .did | |
116 | .as_local() | |
117 | .map(|id| tcx.hir().local_def_id_to_hir_id(id)) | |
118 | .and_then(|id| tcx.hir().find(id)) | |
119 | { | |
120 | Some(hir::Node::Field(field)) => (field.ty.span, Some(field.hir_id)), | |
121 | _ => (sp, field_id), | |
cdc7bbd5 | 122 | }; |
17df50a5 XL |
123 | |
124 | let mut result = None; | |
125 | ||
126 | // First, we check whether the field type per se is representable. | |
127 | // This catches cases as in #74224 and #84611. There is a special | |
128 | // case related to mutual recursion, though; consider this example: | |
129 | // | |
130 | // struct A<T> { | |
131 | // z: T, | |
132 | // x: B<T>, | |
133 | // } | |
134 | // | |
135 | // struct B<T> { | |
136 | // y: A<T> | |
137 | // } | |
138 | // | |
139 | // Here, without the following special case, both A and B are | |
140 | // ContainsRecursive, which is a problem because we only report | |
141 | // errors for SelfRecursive. We fix this by detecting this special | |
142 | // case (shadow_seen.first() is the type we are originally | |
143 | // interested in, and if we ever encounter the same AdtDef again, | |
144 | // we know that it must be SelfRecursive) and "forcibly" returning | |
145 | // SelfRecursive (by setting force_result, which tells the calling | |
146 | // invocations of are_inner_types_representable to forward the | |
147 | // result without adjusting). | |
148 | if shadow_seen.len() > seen.len() && shadow_seen.first() == Some(def) { | |
149 | *force_result = true; | |
5e7ed085 | 150 | result = Some(Representability::SelfRecursive(vec![(sp, field_id)])); |
17df50a5 XL |
151 | } |
152 | ||
153 | if result == None { | |
154 | result = Some(Representability::Representable); | |
155 | ||
156 | // Now, we check whether the field types per se are representable, e.g. | |
157 | // for struct Foo { x: Option<Foo> }, we first check whether Option<_> | |
158 | // by itself is representable (which it is), and the nesting of Foo | |
159 | // will be detected later. This is necessary for #74224 and #84611. | |
160 | ||
161 | // If we have encountered an ADT definition that we have not seen | |
162 | // before (no need to check them twice), recurse to see whether that | |
163 | // definition is SelfRecursive. If so, we must be ContainsRecursive. | |
164 | if shadow_seen.len() > 1 | |
165 | && !shadow_seen | |
166 | .iter() | |
167 | .take(shadow_seen.len() - 1) | |
168 | .any(|seen_def| seen_def == def) | |
169 | { | |
5e7ed085 | 170 | let adt_def_id = def.did(); |
17df50a5 XL |
171 | let raw_adt_ty = tcx.type_of(adt_def_id); |
172 | debug!("are_inner_types_recursive: checking nested type: {:?}", raw_adt_ty); | |
173 | ||
174 | // Check independently whether the ADT is SelfRecursive. If so, | |
175 | // we must be ContainsRecursive (except for the special case | |
176 | // mentioned above). | |
177 | let mut nested_seen: Vec<Ty<'_>> = vec![]; | |
178 | result = Some( | |
179 | match is_type_structurally_recursive( | |
180 | tcx, | |
17df50a5 XL |
181 | &mut nested_seen, |
182 | shadow_seen, | |
183 | representable_cache, | |
184 | raw_adt_ty, | |
5e7ed085 FG |
185 | sp, |
186 | field_id, | |
17df50a5 XL |
187 | force_result, |
188 | ) { | |
189 | Representability::SelfRecursive(_) => { | |
190 | if *force_result { | |
5e7ed085 | 191 | Representability::SelfRecursive(vec![(sp, field_id)]) |
17df50a5 XL |
192 | } else { |
193 | Representability::ContainsRecursive | |
194 | } | |
195 | } | |
196 | x => x, | |
197 | }, | |
198 | ); | |
199 | } | |
200 | ||
201 | // We only enter the following block if the type looks representable | |
202 | // so far. This is necessary for cases such as this one (#74224): | |
203 | // | |
204 | // struct A<T> { | |
205 | // x: T, | |
206 | // y: A<A<T>>, | |
207 | // } | |
208 | // | |
209 | // struct B { | |
210 | // z: A<usize> | |
211 | // } | |
212 | // | |
213 | // When checking B, we recurse into A and check field y of type | |
214 | // A<A<usize>>. We haven't seen this exact type before, so we recurse | |
215 | // into A<A<usize>>, which contains, A<A<A<usize>>>, and so forth, | |
216 | // ad infinitum. We can prevent this from happening by first checking | |
217 | // A separately (the code above) and only checking for nested Bs if | |
218 | // A actually looks representable (which it wouldn't in this example). | |
219 | if result == Some(Representability::Representable) { | |
220 | // Now, even if the type is representable (e.g. Option<_>), | |
221 | // it might still contribute to a recursive type, e.g.: | |
222 | // struct Foo { x: Option<Option<Foo>> } | |
223 | // These cases are handled by passing the full `seen` | |
224 | // stack to is_type_structurally_recursive (instead of the | |
225 | // empty `nested_seen` above): | |
226 | result = Some( | |
227 | match is_type_structurally_recursive( | |
228 | tcx, | |
17df50a5 XL |
229 | seen, |
230 | shadow_seen, | |
231 | representable_cache, | |
232 | ty, | |
5e7ed085 FG |
233 | sp, |
234 | field_id, | |
17df50a5 XL |
235 | force_result, |
236 | ) { | |
237 | Representability::SelfRecursive(_) => { | |
5e7ed085 | 238 | Representability::SelfRecursive(vec![(sp, field_id)]) |
17df50a5 XL |
239 | } |
240 | x => x, | |
241 | }, | |
242 | ); | |
cdc7bbd5 | 243 | } |
cdc7bbd5 | 244 | } |
17df50a5 XL |
245 | |
246 | result.unwrap() | |
cdc7bbd5 XL |
247 | })) |
248 | } | |
249 | ty::Closure(..) => { | |
250 | // this check is run on type definitions, so we don't expect | |
251 | // to see closure types | |
252 | bug!("requires check invoked on inapplicable type: {:?}", ty) | |
253 | } | |
254 | _ => Representability::Representable, | |
255 | } | |
256 | } | |
257 | ||
5e7ed085 | 258 | fn same_adt<'tcx>(ty: Ty<'tcx>, def: ty::AdtDef<'tcx>) -> bool { |
cdc7bbd5 XL |
259 | match *ty.kind() { |
260 | ty::Adt(ty_def, _) => ty_def == def, | |
261 | _ => false, | |
262 | } | |
263 | } | |
264 | ||
265 | // Does the type `ty` directly (without indirection through a pointer) | |
266 | // contain any types on stack `seen`? | |
267 | fn is_type_structurally_recursive<'tcx>( | |
268 | tcx: TyCtxt<'tcx>, | |
cdc7bbd5 | 269 | seen: &mut Vec<Ty<'tcx>>, |
5e7ed085 | 270 | shadow_seen: &mut Vec<ty::AdtDef<'tcx>>, |
cdc7bbd5 XL |
271 | representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, |
272 | ty: Ty<'tcx>, | |
5e7ed085 FG |
273 | sp: Span, |
274 | field_id: Option<hir::HirId>, | |
17df50a5 | 275 | force_result: &mut bool, |
cdc7bbd5 | 276 | ) -> Representability { |
5e7ed085 | 277 | debug!("is_type_structurally_recursive: {:?} {:?} {:?}", ty, sp, field_id); |
5099ac24 | 278 | if let Some(representability) = representable_cache.get(&ty) { |
cdc7bbd5 | 279 | debug!( |
5e7ed085 FG |
280 | "is_type_structurally_recursive: {:?} {:?} {:?} - (cached) {:?}", |
281 | ty, sp, field_id, representability | |
cdc7bbd5 XL |
282 | ); |
283 | return representability.clone(); | |
284 | } | |
285 | ||
17df50a5 XL |
286 | let representability = is_type_structurally_recursive_inner( |
287 | tcx, | |
17df50a5 XL |
288 | seen, |
289 | shadow_seen, | |
290 | representable_cache, | |
291 | ty, | |
5e7ed085 FG |
292 | sp, |
293 | field_id, | |
17df50a5 XL |
294 | force_result, |
295 | ); | |
cdc7bbd5 XL |
296 | |
297 | representable_cache.insert(ty, representability.clone()); | |
298 | representability | |
299 | } | |
300 | ||
301 | fn is_type_structurally_recursive_inner<'tcx>( | |
302 | tcx: TyCtxt<'tcx>, | |
cdc7bbd5 | 303 | seen: &mut Vec<Ty<'tcx>>, |
5e7ed085 | 304 | shadow_seen: &mut Vec<ty::AdtDef<'tcx>>, |
cdc7bbd5 XL |
305 | representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, |
306 | ty: Ty<'tcx>, | |
5e7ed085 FG |
307 | sp: Span, |
308 | field_id: Option<hir::HirId>, | |
17df50a5 | 309 | force_result: &mut bool, |
cdc7bbd5 XL |
310 | ) -> Representability { |
311 | match ty.kind() { | |
312 | ty::Adt(def, _) => { | |
313 | { | |
17df50a5 XL |
314 | debug!("is_type_structurally_recursive_inner: adt: {:?}, seen: {:?}", ty, seen); |
315 | ||
cdc7bbd5 XL |
316 | // Iterate through stack of previously seen types. |
317 | let mut iter = seen.iter(); | |
318 | ||
319 | // The first item in `seen` is the type we are actually curious about. | |
320 | // We want to return SelfRecursive if this type contains itself. | |
321 | // It is important that we DON'T take generic parameters into account | |
322 | // for this check, so that Bar<T> in this example counts as SelfRecursive: | |
323 | // | |
324 | // struct Foo; | |
325 | // struct Bar<T> { x: Bar<Foo> } | |
326 | ||
327 | if let Some(&seen_adt) = iter.next() { | |
328 | if same_adt(seen_adt, *def) { | |
329 | debug!("SelfRecursive: {:?} contains {:?}", seen_adt, ty); | |
5e7ed085 | 330 | return Representability::SelfRecursive(vec![(sp, field_id)]); |
cdc7bbd5 XL |
331 | } |
332 | } | |
333 | ||
334 | // We also need to know whether the first item contains other types | |
335 | // that are structurally recursive. If we don't catch this case, we | |
336 | // will recurse infinitely for some inputs. | |
337 | // | |
338 | // It is important that we DO take generic parameters into account | |
17df50a5 XL |
339 | // here, because nesting e.g. Options is allowed (as long as the |
340 | // definition of Option doesn't itself include an Option field, which | |
341 | // would be a case of SelfRecursive above). The following, too, counts | |
342 | // as SelfRecursive: | |
cdc7bbd5 XL |
343 | // |
344 | // struct Foo { Option<Option<Foo>> } | |
345 | ||
346 | for &seen_adt in iter { | |
5099ac24 | 347 | if ty == seen_adt { |
cdc7bbd5 XL |
348 | debug!("ContainsRecursive: {:?} contains {:?}", seen_adt, ty); |
349 | return Representability::ContainsRecursive; | |
350 | } | |
351 | } | |
352 | } | |
353 | ||
354 | // For structs and enums, track all previously seen types by pushing them | |
355 | // onto the 'seen' stack. | |
356 | seen.push(ty); | |
5e7ed085 | 357 | shadow_seen.push(*def); |
17df50a5 XL |
358 | let out = are_inner_types_recursive( |
359 | tcx, | |
17df50a5 XL |
360 | seen, |
361 | shadow_seen, | |
362 | representable_cache, | |
363 | ty, | |
5e7ed085 FG |
364 | sp, |
365 | field_id, | |
17df50a5 XL |
366 | force_result, |
367 | ); | |
368 | shadow_seen.pop(); | |
cdc7bbd5 XL |
369 | seen.pop(); |
370 | out | |
371 | } | |
372 | _ => { | |
373 | // No need to push in other cases. | |
17df50a5 XL |
374 | are_inner_types_recursive( |
375 | tcx, | |
17df50a5 XL |
376 | seen, |
377 | shadow_seen, | |
378 | representable_cache, | |
379 | ty, | |
5e7ed085 FG |
380 | sp, |
381 | field_id, | |
17df50a5 XL |
382 | force_result, |
383 | ) | |
cdc7bbd5 XL |
384 | } |
385 | } | |
386 | } |