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 SelfRecursive(Vec<Span>),
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
28 // contains a different, structurally recursive type, maintain a stack
29 // of seen types and check recursion for each of them (issues #3008, #3779).
30 let mut seen: Vec<Ty<'_>> = Vec::new();
31 let mut representable_cache = FxHashMap::default();
32 let r = is_type_structurally_recursive(tcx, sp, &mut seen, &mut representable_cache, ty);
33 debug!("is_type_representable: {:?} is {:?}", ty, r);
37 // Iterate until something non-representable is found
38 fn fold_repr<It: Iterator<Item = Representability>>(iter: It) -> Representability {
39 iter.fold(Representability::Representable, |r1, r2| match (r1, r2) {
40 (Representability::SelfRecursive(v1), Representability::SelfRecursive(v2)) => {
41 Representability::SelfRecursive(v1.into_iter().chain(v2).collect())
43 (r1, r2) => cmp::max(r1, r2),
47 fn are_inner_types_recursive<'tcx>(
50 seen: &mut Vec<Ty<'tcx>>,
51 representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
53 ) -> Representability {
56 // Find non representable
58 ty.tuple_fields().map(|ty| {
59 is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
63 // Fixed-length vectors.
64 // FIXME(#11924) Behavior undecided for zero-length vectors.
65 ty::Array(ty, _) => is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty),
66 ty::Adt(def, substs) => {
67 // Find non representable fields with their spans
68 fold_repr(def.all_fields().map(|field| {
69 let ty = field.ty(tcx, substs);
70 let span = match field
73 .map(|id| tcx.hir().local_def_id_to_hir_id(id))
74 .and_then(|id| tcx.hir().find(id))
76 Some(hir::Node::Field(field)) => field.ty.span,
79 match is_type_structurally_recursive(tcx, span, seen, representable_cache, ty) {
80 Representability::SelfRecursive(_) => {
81 Representability::SelfRecursive(vec![span])
88 // this check is run on type definitions, so we don't expect
89 // to see closure types
90 bug!("requires check invoked on inapplicable type: {:?}", ty)
92 _ => Representability::Representable,
96 fn same_adt<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool {
98 ty::Adt(ty_def, _) => ty_def == def,
103 // Does the type `ty` directly (without indirection through a pointer)
104 // contain any types on stack `seen`?
105 fn is_type_structurally_recursive<'tcx>(
108 seen: &mut Vec<Ty<'tcx>>,
109 representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
111 ) -> Representability {
112 debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp);
113 if let Some(representability) = representable_cache.get(ty) {
115 "is_type_structurally_recursive: {:?} {:?} - (cached) {:?}",
116 ty, sp, representability
118 return representability.clone();
121 let representability =
122 is_type_structurally_recursive_inner(tcx, sp, seen, representable_cache, ty);
124 representable_cache.insert(ty, representability.clone());
128 fn is_type_structurally_recursive_inner<'tcx>(
131 seen: &mut Vec<Ty<'tcx>>,
132 representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
134 ) -> Representability {
138 // Iterate through stack of previously seen types.
139 let mut iter = seen.iter();
141 // The first item in `seen` is the type we are actually curious about.
142 // We want to return SelfRecursive if this type contains itself.
143 // It is important that we DON'T take generic parameters into account
144 // for this check, so that Bar<T> in this example counts as SelfRecursive:
147 // struct Bar<T> { x: Bar<Foo> }
149 if let Some(&seen_adt) = iter.next() {
150 if same_adt(seen_adt, *def) {
151 debug!("SelfRecursive: {:?} contains {:?}", seen_adt, ty);
152 return Representability::SelfRecursive(vec![sp]);
156 // We also need to know whether the first item contains other types
157 // that are structurally recursive. If we don't catch this case, we
158 // will recurse infinitely for some inputs.
160 // It is important that we DO take generic parameters into account
161 // here, so that code like this is considered SelfRecursive, not
162 // ContainsRecursive:
164 // struct Foo { Option<Option<Foo>> }
166 for &seen_adt in iter {
167 if ty::TyS::same_type(ty, seen_adt) {
168 debug!("ContainsRecursive: {:?} contains {:?}", seen_adt, ty);
169 return Representability::ContainsRecursive;
174 // For structs and enums, track all previously seen types by pushing them
175 // onto the 'seen' stack.
177 let out = are_inner_types_recursive(tcx, sp, seen, representable_cache, ty);
182 // No need to push in other cases.
183 are_inner_types_recursive(tcx, sp, seen, representable_cache, ty)