bindgen/ir/analysis/
sizedness.rs

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, 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 SizednessAnalysis<'_> {
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 {result:?} for {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) {
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            .filter_map(|id| id.as_type_id(self.ctx))
195            .collect()
196    }
197
198    fn constrain(&mut self, id: TypeId) -> ConstrainResult {
199        trace!("constrain {id:?}");
200
201        if let Some(SizednessResult::NonZeroSized) = self.sized.get(&id) {
202            trace!("    already know it is not zero-sized");
203            return ConstrainResult::Same;
204        }
205
206        if id.has_vtable_ptr(self.ctx) {
207            trace!("    has an explicit vtable pointer, therefore is not zero-sized");
208            return self.insert(id, SizednessResult::NonZeroSized);
209        }
210
211        let ty = self.ctx.resolve_type(id);
212
213        if id.is_opaque(self.ctx, &()) {
214            trace!("    type is opaque; checking layout...");
215            let result =
216                ty.layout(self.ctx).map_or(SizednessResult::ZeroSized, |l| {
217                    if l.size == 0 {
218                        trace!("    ...layout has size == 0");
219                        SizednessResult::ZeroSized
220                    } else {
221                        trace!("    ...layout has size > 0");
222                        SizednessResult::NonZeroSized
223                    }
224                });
225            return self.insert(id, result);
226        }
227
228        match *ty.kind() {
229            TypeKind::Void => {
230                trace!("    void is zero-sized");
231                self.insert(id, SizednessResult::ZeroSized)
232            }
233
234            TypeKind::TypeParam => {
235                trace!(
236                    "    type params sizedness depends on what they're \
237                     instantiated as"
238                );
239                self.insert(id, SizednessResult::DependsOnTypeParam)
240            }
241
242            TypeKind::Int(..) |
243            TypeKind::Float(..) |
244            TypeKind::Complex(..) |
245            TypeKind::Function(..) |
246            TypeKind::Enum(..) |
247            TypeKind::Reference(..) |
248            TypeKind::NullPtr |
249            TypeKind::ObjCId |
250            TypeKind::ObjCSel |
251            TypeKind::Pointer(..) => {
252                trace!("    {:?} is known not to be zero-sized", ty.kind());
253                self.insert(id, SizednessResult::NonZeroSized)
254            }
255
256            TypeKind::ObjCInterface(..) => {
257                trace!("    obj-c interfaces always have at least the `isa` pointer");
258                self.insert(id, SizednessResult::NonZeroSized)
259            }
260
261            TypeKind::TemplateAlias(t, _) |
262            TypeKind::Alias(t) |
263            TypeKind::BlockPointer(t) |
264            TypeKind::ResolvedTypeRef(t) => {
265                trace!("    aliases and type refs forward to their inner type");
266                self.forward(t, id)
267            }
268
269            TypeKind::TemplateInstantiation(ref inst) => {
270                trace!(
271                    "    template instantiations are zero-sized if their \
272                     definition is zero-sized"
273                );
274                self.forward(inst.template_definition(), id)
275            }
276
277            TypeKind::Array(_, 0) => {
278                trace!("    arrays of zero elements are zero-sized");
279                self.insert(id, SizednessResult::ZeroSized)
280            }
281            TypeKind::Array(..) => {
282                trace!("    arrays of > 0 elements are not zero-sized");
283                self.insert(id, SizednessResult::NonZeroSized)
284            }
285            TypeKind::Vector(..) => {
286                trace!("    vectors are not zero-sized");
287                self.insert(id, SizednessResult::NonZeroSized)
288            }
289
290            TypeKind::Comp(ref info) => {
291                trace!("    comp considers its own fields and bases");
292
293                if !info.fields().is_empty() {
294                    return self.insert(id, SizednessResult::NonZeroSized);
295                }
296
297                let result = info
298                    .base_members()
299                    .iter()
300                    .filter_map(|base| self.sized.get(&base.ty))
301                    .fold(SizednessResult::ZeroSized, |a, b| a.join(*b));
302
303                self.insert(id, result)
304            }
305
306            TypeKind::Opaque => {
307                unreachable!("covered by the .is_opaque() check above")
308            }
309
310            TypeKind::UnresolvedTypeRef(..) => {
311                unreachable!("Should have been resolved after parsing!");
312            }
313        }
314    }
315
316    fn each_depending_on<F>(&self, id: TypeId, mut f: F)
317    where
318        F: FnMut(TypeId),
319    {
320        if let Some(edges) = self.dependencies.get(&id) {
321            for ty in edges {
322                trace!("enqueue {ty:?} into worklist");
323                f(*ty);
324            }
325        }
326    }
327}
328
329impl<'ctx> From<SizednessAnalysis<'ctx>> for HashMap<TypeId, SizednessResult> {
330    fn from(analysis: SizednessAnalysis<'ctx>) -> Self {
331        // We let the lack of an entry mean "ZeroSized" to save space.
332        extra_assert!(analysis
333            .sized
334            .values()
335            .all(|v| { *v != SizednessResult::ZeroSized }));
336
337        analysis.sized
338    }
339}
340
341/// A convenience trait for querying whether some type or ID is sized.
342///
343/// This is not for _computing_ whether the thing is sized, it is for looking up
344/// the results of the `Sizedness` analysis's computations for a specific thing.
345pub(crate) trait Sizedness {
346    /// Get the sizedness of this type.
347    fn sizedness(&self, ctx: &BindgenContext) -> SizednessResult;
348
349    /// Is the sizedness for this type `SizednessResult::ZeroSized`?
350    fn is_zero_sized(&self, ctx: &BindgenContext) -> bool {
351        self.sizedness(ctx) == SizednessResult::ZeroSized
352    }
353}
bindgen/ir/analysis/sizedness.rs

bindgen/ir/analysis/
sizedness.rs
