1 //! Check whether a type is representable.
2 use rustc_data_structures::stable_map::FxHashMap;
4 use rustc_middle::ty::{self, Ty, TyCtxt};
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.
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 {
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>)>),
26 /// Check whether a type is representable. This means it cannot contain unboxed
27 /// structural recursion. This check is needed for structs and enums.
28 pub fn ty_is_representable<'tcx>(
32 field_id: Option<hir::HirId>,
33 ) -> Representability {
34 debug!("is_type_representable: {:?}", ty);
35 // To avoid a stack overflow when checking an enum variant or struct that
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).
43 let mut seen: Vec<Ty<'_>> = Vec::new();
44 let mut shadow_seen: Vec<ty::AdtDef<'tcx>> = Vec::new();
45 let mut representable_cache = FxHashMap::default();
46 let mut force_result = false;
47 let r = is_type_structurally_recursive(
51 &mut representable_cache,
57 debug!("is_type_representable: {:?} is {:?}", ty, r);
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())
67 (r1, r2) => cmp::max(r1, r2),
71 fn are_inner_types_recursive<'tcx>(
73 seen: &mut Vec<Ty<'tcx>>,
74 shadow_seen: &mut Vec<ty::AdtDef<'tcx>>,
75 representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
78 field_id: Option<hir::HirId>,
79 force_result: &mut bool,
80 ) -> Representability {
81 debug!("are_inner_types_recursive({:?}, {:?}, {:?})", ty, seen, shadow_seen);
83 ty::Tuple(fields) => {
84 // Find non representable
85 fold_repr(fields.iter().map(|ty| {
86 is_type_structurally_recursive(
98 // Fixed-length vectors.
99 // FIXME(#11924) Behavior undecided for zero-length vectors.
100 ty::Array(ty, _) => is_type_structurally_recursive(
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);
114 let (sp, field_id) = match field
117 .map(|id| tcx.hir().local_def_id_to_hir_id(id))
118 .and_then(|id| tcx.hir().find(id))
120 Some(hir::Node::Field(field)) => (field.ty.span, Some(field.hir_id)),
124 let mut result = None;
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:
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;
150 result = Some(Representability::SelfRecursive(vec![(sp, field_id)]));
154 result = Some(Representability::Representable);
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.
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
167 .take(shadow_seen.len() - 1)
168 .any(|seen_def| seen_def == def)
170 let adt_def_id = def.did();
171 let raw_adt_ty = tcx.type_of(adt_def_id);
172 debug!("are_inner_types_recursive: checking nested type: {:?}", raw_adt_ty);
174 // Check independently whether the ADT is SelfRecursive. If so,
175 // we must be ContainsRecursive (except for the special case
177 let mut nested_seen: Vec<Ty<'_>> = vec![];
179 match is_type_structurally_recursive(
189 Representability::SelfRecursive(_) => {
191 Representability::SelfRecursive(vec![(sp, field_id)])
193 Representability::ContainsRecursive
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):
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):
227 match is_type_structurally_recursive(
237 Representability::SelfRecursive(_) => {
238 Representability::SelfRecursive(vec![(sp, field_id)])
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)
254 _ => Representability::Representable,
258 fn same_adt<'tcx>(ty: Ty<'tcx>, def: ty::AdtDef<'tcx>) -> bool {
260 ty::Adt(ty_def, _) => ty_def == def,
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>(
269 seen: &mut Vec<Ty<'tcx>>,
270 shadow_seen: &mut Vec<ty::AdtDef<'tcx>>,
271 representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
274 field_id: Option<hir::HirId>,
275 force_result: &mut bool,
276 ) -> Representability {
277 debug!("is_type_structurally_recursive: {:?} {:?} {:?}", ty, sp, field_id);
278 if let Some(representability) = representable_cache.get(&ty) {
280 "is_type_structurally_recursive: {:?} {:?} {:?} - (cached) {:?}",
281 ty, sp, field_id, representability
283 return representability.clone();
286 let representability = is_type_structurally_recursive_inner(
297 representable_cache.insert(ty, representability.clone());
301 fn is_type_structurally_recursive_inner<'tcx>(
303 seen: &mut Vec<Ty<'tcx>>,
304 shadow_seen: &mut Vec<ty::AdtDef<'tcx>>,
305 representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
308 field_id: Option<hir::HirId>,
309 force_result: &mut bool,
310 ) -> Representability {
314 debug!("is_type_structurally_recursive_inner: adt: {:?}, seen: {:?}", ty, seen);
316 // Iterate through stack of previously seen types.
317 let mut iter = seen.iter();
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:
325 // struct Bar<T> { x: Bar<Foo> }
327 if let Some(&seen_adt) = iter.next() {
328 if same_adt(seen_adt, *def) {
329 debug!("SelfRecursive: {:?} contains {:?}", seen_adt, ty);
330 return Representability::SelfRecursive(vec![(sp, field_id)]);
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.
338 // It is important that we DO take generic parameters into account
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
344 // struct Foo { Option<Option<Foo>> }
346 for &seen_adt in iter {
348 debug!("ContainsRecursive: {:?} contains {:?}", seen_adt, ty);
349 return Representability::ContainsRecursive;
354 // For structs and enums, track all previously seen types by pushing them
355 // onto the 'seen' stack.
357 shadow_seen.push(*def);
358 let out = are_inner_types_recursive(
373 // No need to push in other cases.
374 are_inner_types_recursive(