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