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