1//! Determining the sizedness of types (as base classes and otherwise).
2
3use super::{
4 generate_dependencies, ConstrainResult, HasVtable, MonotoneFramework,
5};
6use crate::ir::context::{BindgenContext, TypeId};
7use crate::ir::item::IsOpaque;
8use crate::ir::traversal::EdgeKind;
9use crate::ir::ty::TypeKind;
10use crate::{Entry, HashMap};
11use std::{cmp, ops};
12
13/// The result of the `Sizedness` analysis for an individual item.
14///
15/// This is a chain lattice of the form:
16///
17/// ```ignore
18/// NonZeroSized
19/// |
20/// DependsOnTypeParam
21/// |
22/// ZeroSized
23/// ```
24///
25/// We initially assume that all types are `ZeroSized` and then update our
26/// understanding as we learn more about each type.
27#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
28pub(crate) enum SizednessResult {
29 /// The type is zero-sized.
30 ///
31 /// This means that if it is a C++ type, and is not being used as a base
32 /// member, then we must add an `_address` byte to enforce the
33 /// unique-address-per-distinct-object-instance rule.
34 ZeroSized,
35
36 /// Whether this type is zero-sized or not depends on whether a type
37 /// parameter is zero-sized or not.
38 ///
39 /// For example, given these definitions:
40 ///
41 /// ```c++
42 /// template<class T>
43 /// class Flongo : public T {};
44 ///
45 /// class Empty {};
46 ///
47 /// class NonEmpty { int x; };
48 /// ```
49 ///
50 /// Then `Flongo<Empty>` is zero-sized, and needs an `_address` byte
51 /// inserted, while `Flongo<NonEmpty>` is *not* zero-sized, and should *not*
52 /// have an `_address` byte inserted.
53 ///
54 /// We don't properly handle this situation correctly right now:
55 /// <https://github.com/rust-lang/rust-bindgen/issues/586>
56 DependsOnTypeParam,
57
58 /// Has some size that is known to be greater than zero. That doesn't mean
59 /// it has a static size, but it is not zero sized for sure. In other words,
60 /// it might contain an incomplete array or some other dynamically sized
61 /// type.
62 NonZeroSized,
63}
64
65impl Default for SizednessResult {
66 fn default() -> Self {
67 SizednessResult::ZeroSized
68 }
69}
70
71impl SizednessResult {
72 /// Take the least upper bound of `self` and `rhs`.
73 pub(crate) fn join(self, rhs: Self) -> Self {
74 cmp::max(self, v2:rhs)
75 }
76}
77
78impl ops::BitOr for SizednessResult {
79 type Output = Self;
80
81 fn bitor(self, rhs: SizednessResult) -> Self::Output {
82 self.join(rhs)
83 }
84}
85
86impl ops::BitOrAssign for SizednessResult {
87 fn bitor_assign(&mut self, rhs: SizednessResult) {
88 *self = self.join(rhs)
89 }
90}
91
92/// An analysis that computes the sizedness of all types.
93///
94/// * For types with known sizes -- for example pointers, scalars, etc... --
95/// they are assigned `NonZeroSized`.
96///
97/// * For compound structure types with one or more fields, they are assigned
98/// `NonZeroSized`.
99///
100/// * For compound structure types without any fields, the results of the bases
101/// are `join`ed.
102///
103/// * For type parameters, `DependsOnTypeParam` is assigned.
104#[derive(Debug)]
105pub(crate) struct SizednessAnalysis<'ctx> {
106 ctx: &'ctx BindgenContext,
107 dependencies: HashMap<TypeId, Vec<TypeId>>,
108 // Incremental results of the analysis. Missing entries are implicitly
109 // considered `ZeroSized`.
110 sized: HashMap<TypeId, SizednessResult>,
111}
112
113impl<'ctx> SizednessAnalysis<'ctx> {
114 fn consider_edge(kind: EdgeKind) -> bool {
115 // These are the only edges that can affect whether a type is
116 // zero-sized or not.
117 matches!(
118 kind,
119 EdgeKind::TemplateArgument |
120 EdgeKind::TemplateParameterDefinition |
121 EdgeKind::TemplateDeclaration |
122 EdgeKind::TypeReference |
123 EdgeKind::BaseMember |
124 EdgeKind::Field
125 )
126 }
127
128 /// Insert an incremental result, and return whether this updated our
129 /// knowledge of types and we should continue the analysis.
130 fn insert(
131 &mut self,
132 id: TypeId,
133 result: SizednessResult,
134 ) -> ConstrainResult {
135 trace!("inserting {:?} for {:?}", result, id);
136
137 if let SizednessResult::ZeroSized = result {
138 return ConstrainResult::Same;
139 }
140
141 match self.sized.entry(id) {
142 Entry::Occupied(mut entry) => {
143 if *entry.get() < result {
144 entry.insert(result);
145 ConstrainResult::Changed
146 } else {
147 ConstrainResult::Same
148 }
149 }
150 Entry::Vacant(entry) => {
151 entry.insert(result);
152 ConstrainResult::Changed
153 }
154 }
155 }
156
157 fn forward(&mut self, from: TypeId, to: TypeId) -> ConstrainResult {
158 match self.sized.get(&from).cloned() {
159 None => ConstrainResult::Same,
160 Some(r) => self.insert(to, r),
161 }
162 }
163}
164
165impl<'ctx> MonotoneFramework for SizednessAnalysis<'ctx> {
166 type Node = TypeId;
167 type Extra = &'ctx BindgenContext;
168 type Output = HashMap<TypeId, SizednessResult>;
169
170 fn new(ctx: &'ctx BindgenContext) -> SizednessAnalysis<'ctx> {
171 let dependencies = generate_dependencies(ctx, Self::consider_edge)
172 .into_iter()
173 .filter_map(|(id, sub_ids)| {
174 id.as_type_id(ctx).map(|id| {
175 (
176 id,
177 sub_ids
178 .into_iter()
179 .filter_map(|s| s.as_type_id(ctx))
180 .collect::<Vec<_>>(),
181 )
182 })
183 })
184 .collect();
185
186 let sized = HashMap::default();
187
188 SizednessAnalysis {
189 ctx,
190 dependencies,
191 sized,
192 }
193 }
194
195 fn initial_worklist(&self) -> Vec<TypeId> {
196 self.ctx
197 .allowlisted_items()
198 .iter()
199 .cloned()
200 .filter_map(|id| id.as_type_id(self.ctx))
201 .collect()
202 }
203
204 fn constrain(&mut self, id: TypeId) -> ConstrainResult {
205 trace!("constrain {:?}", id);
206
207 if let Some(SizednessResult::NonZeroSized) =
208 self.sized.get(&id).cloned()
209 {
210 trace!(" already know it is not zero-sized");
211 return ConstrainResult::Same;
212 }
213
214 if id.has_vtable_ptr(self.ctx) {
215 trace!(" has an explicit vtable pointer, therefore is not zero-sized");
216 return self.insert(id, SizednessResult::NonZeroSized);
217 }
218
219 let ty = self.ctx.resolve_type(id);
220
221 if id.is_opaque(self.ctx, &()) {
222 trace!(" type is opaque; checking layout...");
223 let result =
224 ty.layout(self.ctx).map_or(SizednessResult::ZeroSized, |l| {
225 if l.size == 0 {
226 trace!(" ...layout has size == 0");
227 SizednessResult::ZeroSized
228 } else {
229 trace!(" ...layout has size > 0");
230 SizednessResult::NonZeroSized
231 }
232 });
233 return self.insert(id, result);
234 }
235
236 match *ty.kind() {
237 TypeKind::Void => {
238 trace!(" void is zero-sized");
239 self.insert(id, SizednessResult::ZeroSized)
240 }
241
242 TypeKind::TypeParam => {
243 trace!(
244 " type params sizedness depends on what they're \
245 instantiated as"
246 );
247 self.insert(id, SizednessResult::DependsOnTypeParam)
248 }
249
250 TypeKind::Int(..) |
251 TypeKind::Float(..) |
252 TypeKind::Complex(..) |
253 TypeKind::Function(..) |
254 TypeKind::Enum(..) |
255 TypeKind::Reference(..) |
256 TypeKind::NullPtr |
257 TypeKind::ObjCId |
258 TypeKind::ObjCSel |
259 TypeKind::Pointer(..) => {
260 trace!(" {:?} is known not to be zero-sized", ty.kind());
261 self.insert(id, SizednessResult::NonZeroSized)
262 }
263
264 TypeKind::ObjCInterface(..) => {
265 trace!(" obj-c interfaces always have at least the `isa` pointer");
266 self.insert(id, SizednessResult::NonZeroSized)
267 }
268
269 TypeKind::TemplateAlias(t, _) |
270 TypeKind::Alias(t) |
271 TypeKind::BlockPointer(t) |
272 TypeKind::ResolvedTypeRef(t) => {
273 trace!(" aliases and type refs forward to their inner type");
274 self.forward(t, id)
275 }
276
277 TypeKind::TemplateInstantiation(ref inst) => {
278 trace!(
279 " template instantiations are zero-sized if their \
280 definition is zero-sized"
281 );
282 self.forward(inst.template_definition(), id)
283 }
284
285 TypeKind::Array(_, 0) => {
286 trace!(" arrays of zero elements are zero-sized");
287 self.insert(id, SizednessResult::ZeroSized)
288 }
289 TypeKind::Array(..) => {
290 trace!(" arrays of > 0 elements are not zero-sized");
291 self.insert(id, SizednessResult::NonZeroSized)
292 }
293 TypeKind::Vector(..) => {
294 trace!(" vectors are not zero-sized");
295 self.insert(id, SizednessResult::NonZeroSized)
296 }
297
298 TypeKind::Comp(ref info) => {
299 trace!(" comp considers its own fields and bases");
300
301 if !info.fields().is_empty() {
302 return self.insert(id, SizednessResult::NonZeroSized);
303 }
304
305 let result = info
306 .base_members()
307 .iter()
308 .filter_map(|base| self.sized.get(&base.ty))
309 .fold(SizednessResult::ZeroSized, |a, b| a.join(*b));
310
311 self.insert(id, result)
312 }
313
314 TypeKind::Opaque => {
315 unreachable!("covered by the .is_opaque() check above")
316 }
317
318 TypeKind::UnresolvedTypeRef(..) => {
319 unreachable!("Should have been resolved after parsing!");
320 }
321 }
322 }
323
324 fn each_depending_on<F>(&self, id: TypeId, mut f: F)
325 where
326 F: FnMut(TypeId),
327 {
328 if let Some(edges) = self.dependencies.get(&id) {
329 for ty in edges {
330 trace!("enqueue {:?} into worklist", ty);
331 f(*ty);
332 }
333 }
334 }
335}
336
337impl<'ctx> From<SizednessAnalysis<'ctx>> for HashMap<TypeId, SizednessResult> {
338 fn from(analysis: SizednessAnalysis<'ctx>) -> Self {
339 // We let the lack of an entry mean "ZeroSized" to save space.
340 extra_assert!(analysis
341 .sized
342 .values()
343 .all(|v| { *v != SizednessResult::ZeroSized }));
344
345 analysis.sized
346 }
347}
348
349/// A convenience trait for querying whether some type or ID is sized.
350///
351/// This is not for _computing_ whether the thing is sized, it is for looking up
352/// the results of the `Sizedness` analysis's computations for a specific thing.
353pub(crate) trait Sizedness {
354 /// Get the sizedness of this type.
355 fn sizedness(&self, ctx: &BindgenContext) -> SizednessResult;
356
357 /// Is the sizedness for this type `SizednessResult::ZeroSized`?
358 fn is_zero_sized(&self, ctx: &BindgenContext) -> bool {
359 self.sizedness(ctx) == SizednessResult::ZeroSized
360 }
361}
362