]> git.lizzy.rs Git - rust.git/blob - compiler/rustc_ty_utils/src/representability.rs
Rollup merge of #84328 - Folyd:stablize_map_into_keys_values, r=m-ou-se
[rust.git] / compiler / rustc_ty_utils / src / representability.rs
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
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);
34     r
35 }
36
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())
42         }
43         (r1, r2) => cmp::max(r1, r2),
44     })
45 }
46
47 fn are_inner_types_recursive<'tcx>(
48     tcx: TyCtxt<'tcx>,
49     sp: Span,
50     seen: &mut Vec<Ty<'tcx>>,
51     representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
52     ty: Ty<'tcx>,
53 ) -> Representability {
54     match ty.kind() {
55         ty::Tuple(..) => {
56             // Find non representable
57             fold_repr(
58                 ty.tuple_fields().map(|ty| {
59                     is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
60                 }),
61             )
62         }
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
71                     .did
72                     .as_local()
73                     .map(|id| tcx.hir().local_def_id_to_hir_id(id))
74                     .and_then(|id| tcx.hir().find(id))
75                 {
76                     Some(hir::Node::Field(field)) => field.ty.span,
77                     _ => sp,
78                 };
79                 match is_type_structurally_recursive(tcx, span, seen, representable_cache, ty) {
80                     Representability::SelfRecursive(_) => {
81                         Representability::SelfRecursive(vec![span])
82                     }
83                     x => x,
84                 }
85             }))
86         }
87         ty::Closure(..) => {
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)
91         }
92         _ => Representability::Representable,
93     }
94 }
95
96 fn same_adt<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool {
97     match *ty.kind() {
98         ty::Adt(ty_def, _) => ty_def == def,
99         _ => false,
100     }
101 }
102
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>(
106     tcx: TyCtxt<'tcx>,
107     sp: Span,
108     seen: &mut Vec<Ty<'tcx>>,
109     representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
110     ty: Ty<'tcx>,
111 ) -> Representability {
112     debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp);
113     if let Some(representability) = representable_cache.get(ty) {
114         debug!(
115             "is_type_structurally_recursive: {:?} {:?} - (cached) {:?}",
116             ty, sp, representability
117         );
118         return representability.clone();
119     }
120
121     let representability =
122         is_type_structurally_recursive_inner(tcx, sp, seen, representable_cache, ty);
123
124     representable_cache.insert(ty, representability.clone());
125     representability
126 }
127
128 fn is_type_structurally_recursive_inner<'tcx>(
129     tcx: TyCtxt<'tcx>,
130     sp: Span,
131     seen: &mut Vec<Ty<'tcx>>,
132     representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
133     ty: Ty<'tcx>,
134 ) -> Representability {
135     match ty.kind() {
136         ty::Adt(def, _) => {
137             {
138                 // Iterate through stack of previously seen types.
139                 let mut iter = seen.iter();
140
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:
145                 //
146                 // struct Foo;
147                 // struct Bar<T> { x: Bar<Foo> }
148
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]);
153                     }
154                 }
155
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.
159                 //
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:
163                 //
164                 // struct Foo { Option<Option<Foo>> }
165
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;
170                     }
171                 }
172             }
173
174             // For structs and enums, track all previously seen types by pushing them
175             // onto the 'seen' stack.
176             seen.push(ty);
177             let out = are_inner_types_recursive(tcx, sp, seen, representable_cache, ty);
178             seen.pop();
179             out
180         }
181         _ => {
182             // No need to push in other cases.
183             are_inner_types_recursive(tcx, sp, seen, representable_cache, ty)
184         }
185     }
186 }