diff options
Diffstat (limited to 'bindgen/ir/analysis/sizedness.rs')
| -rw-r--r-- | bindgen/ir/analysis/sizedness.rs | 361 |
1 files changed, 361 insertions, 0 deletions
diff --git a/bindgen/ir/analysis/sizedness.rs b/bindgen/ir/analysis/sizedness.rs new file mode 100644 index 00000000..251c3747 --- /dev/null +++ b/bindgen/ir/analysis/sizedness.rs @@ -0,0 +1,361 @@ +//! Determining the sizedness of types (as base classes and otherwise). + +use super::{ + generate_dependencies, ConstrainResult, HasVtable, MonotoneFramework, +}; +use crate::ir::context::{BindgenContext, TypeId}; +use crate::ir::item::IsOpaque; +use crate::ir::traversal::EdgeKind; +use crate::ir::ty::TypeKind; +use crate::{Entry, HashMap}; +use std::{cmp, ops}; + +/// The result of the `Sizedness` analysis for an individual item. +/// +/// This is a chain lattice of the form: +/// +/// ```ignore +/// NonZeroSized +/// | +/// DependsOnTypeParam +/// | +/// ZeroSized +/// ``` +/// +/// We initially assume that all types are `ZeroSized` and then update our +/// understanding as we learn more about each type. +#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)] +pub enum SizednessResult { + /// The type is zero-sized. + /// + /// This means that if it is a C++ type, and is not being used as a base + /// member, then we must add an `_address` byte to enforce the + /// unique-address-per-distinct-object-instance rule. + ZeroSized, + + /// Whether this type is zero-sized or not depends on whether a type + /// parameter is zero-sized or not. + /// + /// For example, given these definitions: + /// + /// ```c++ + /// template<class T> + /// class Flongo : public T {}; + /// + /// class Empty {}; + /// + /// class NonEmpty { int x; }; + /// ``` + /// + /// Then `Flongo<Empty>` is zero-sized, and needs an `_address` byte + /// inserted, while `Flongo<NonEmpty>` is *not* zero-sized, and should *not* + /// have an `_address` byte inserted. + /// + /// We don't properly handle this situation correctly right now: + /// https://github.com/rust-lang/rust-bindgen/issues/586 + DependsOnTypeParam, + + /// Has some size that is known to be greater than zero. That doesn't mean + /// it has a static size, but it is not zero sized for sure. In other words, + /// it might contain an incomplete array or some other dynamically sized + /// type. + NonZeroSized, +} + +impl Default for SizednessResult { + fn default() -> Self { + SizednessResult::ZeroSized + } +} + +impl SizednessResult { + /// Take the least upper bound of `self` and `rhs`. + pub fn join(self, rhs: Self) -> Self { + cmp::max(self, rhs) + } +} + +impl ops::BitOr for SizednessResult { + type Output = Self; + + fn bitor(self, rhs: SizednessResult) -> Self::Output { + self.join(rhs) + } +} + +impl ops::BitOrAssign for SizednessResult { + fn bitor_assign(&mut self, rhs: SizednessResult) { + *self = self.join(rhs) + } +} + +/// An analysis that computes the sizedness of all types. +/// +/// * For types with known sizes -- for example pointers, scalars, etc... -- +/// they are assigned `NonZeroSized`. +/// +/// * For compound structure types with one or more fields, they are assigned +/// `NonZeroSized`. +/// +/// * For compound structure types without any fields, the results of the bases +/// are `join`ed. +/// +/// * For type parameters, `DependsOnTypeParam` is assigned. +#[derive(Debug)] +pub struct SizednessAnalysis<'ctx> { + ctx: &'ctx BindgenContext, + dependencies: HashMap<TypeId, Vec<TypeId>>, + // Incremental results of the analysis. Missing entries are implicitly + // considered `ZeroSized`. + sized: HashMap<TypeId, SizednessResult>, +} + +impl<'ctx> SizednessAnalysis<'ctx> { + fn consider_edge(kind: EdgeKind) -> bool { + // These are the only edges that can affect whether a type is + // zero-sized or not. + matches!( + kind, + EdgeKind::TemplateArgument | + EdgeKind::TemplateParameterDefinition | + EdgeKind::TemplateDeclaration | + EdgeKind::TypeReference | + EdgeKind::BaseMember | + EdgeKind::Field + ) + } + + /// Insert an incremental result, and return whether this updated our + /// knowledge of types and we should continue the analysis. + fn insert( + &mut self, + id: TypeId, + result: SizednessResult, + ) -> ConstrainResult { + trace!("inserting {:?} for {:?}", result, id); + + if let SizednessResult::ZeroSized = result { + return ConstrainResult::Same; + } + + match self.sized.entry(id) { + Entry::Occupied(mut entry) => { + if *entry.get() < result { + entry.insert(result); + ConstrainResult::Changed + } else { + ConstrainResult::Same + } + } + Entry::Vacant(entry) => { + entry.insert(result); + ConstrainResult::Changed + } + } + } + + fn forward(&mut self, from: TypeId, to: TypeId) -> ConstrainResult { + match self.sized.get(&from).cloned() { + None => ConstrainResult::Same, + Some(r) => self.insert(to, r), + } + } +} + +impl<'ctx> MonotoneFramework for SizednessAnalysis<'ctx> { + type Node = TypeId; + type Extra = &'ctx BindgenContext; + type Output = HashMap<TypeId, SizednessResult>; + + fn new(ctx: &'ctx BindgenContext) -> SizednessAnalysis<'ctx> { + let dependencies = generate_dependencies(ctx, Self::consider_edge) + .into_iter() + .filter_map(|(id, sub_ids)| { + id.as_type_id(ctx).map(|id| { + ( + id, + sub_ids + .into_iter() + .filter_map(|s| s.as_type_id(ctx)) + .collect::<Vec<_>>(), + ) + }) + }) + .collect(); + + let sized = HashMap::default(); + + SizednessAnalysis { + ctx, + dependencies, + sized, + } + } + + fn initial_worklist(&self) -> Vec<TypeId> { + self.ctx + .allowlisted_items() + .iter() + .cloned() + .filter_map(|id| id.as_type_id(self.ctx)) + .collect() + } + + fn constrain(&mut self, id: TypeId) -> ConstrainResult { + trace!("constrain {:?}", id); + + if let Some(SizednessResult::NonZeroSized) = + self.sized.get(&id).cloned() + { + trace!(" already know it is not zero-sized"); + return ConstrainResult::Same; + } + + if id.has_vtable_ptr(self.ctx) { + trace!(" has an explicit vtable pointer, therefore is not zero-sized"); + return self.insert(id, SizednessResult::NonZeroSized); + } + + let ty = self.ctx.resolve_type(id); + + if id.is_opaque(self.ctx, &()) { + trace!(" type is opaque; checking layout..."); + let result = + ty.layout(self.ctx).map_or(SizednessResult::ZeroSized, |l| { + if l.size == 0 { + trace!(" ...layout has size == 0"); + SizednessResult::ZeroSized + } else { + trace!(" ...layout has size > 0"); + SizednessResult::NonZeroSized + } + }); + return self.insert(id, result); + } + + match *ty.kind() { + TypeKind::Void => { + trace!(" void is zero-sized"); + self.insert(id, SizednessResult::ZeroSized) + } + + TypeKind::TypeParam => { + trace!( + " type params sizedness depends on what they're \ + instantiated as" + ); + self.insert(id, SizednessResult::DependsOnTypeParam) + } + + TypeKind::Int(..) | + TypeKind::Float(..) | + TypeKind::Complex(..) | + TypeKind::Function(..) | + TypeKind::Enum(..) | + TypeKind::Reference(..) | + TypeKind::NullPtr | + TypeKind::ObjCId | + TypeKind::ObjCSel | + TypeKind::Pointer(..) => { + trace!(" {:?} is known not to be zero-sized", ty.kind()); + self.insert(id, SizednessResult::NonZeroSized) + } + + TypeKind::ObjCInterface(..) => { + trace!(" obj-c interfaces always have at least the `isa` pointer"); + self.insert(id, SizednessResult::NonZeroSized) + } + + TypeKind::TemplateAlias(t, _) | + TypeKind::Alias(t) | + TypeKind::BlockPointer(t) | + TypeKind::ResolvedTypeRef(t) => { + trace!(" aliases and type refs forward to their inner type"); + self.forward(t, id) + } + + TypeKind::TemplateInstantiation(ref inst) => { + trace!( + " template instantiations are zero-sized if their \ + definition is zero-sized" + ); + self.forward(inst.template_definition(), id) + } + + TypeKind::Array(_, 0) => { + trace!(" arrays of zero elements are zero-sized"); + self.insert(id, SizednessResult::ZeroSized) + } + TypeKind::Array(..) => { + trace!(" arrays of > 0 elements are not zero-sized"); + self.insert(id, SizednessResult::NonZeroSized) + } + TypeKind::Vector(..) => { + trace!(" vectors are not zero-sized"); + self.insert(id, SizednessResult::NonZeroSized) + } + + TypeKind::Comp(ref info) => { + trace!(" comp considers its own fields and bases"); + + if !info.fields().is_empty() { + return self.insert(id, SizednessResult::NonZeroSized); + } + + let result = info + .base_members() + .iter() + .filter_map(|base| self.sized.get(&base.ty)) + .fold(SizednessResult::ZeroSized, |a, b| a.join(*b)); + + self.insert(id, result) + } + + TypeKind::Opaque => { + unreachable!("covered by the .is_opaque() check above") + } + + TypeKind::UnresolvedTypeRef(..) => { + unreachable!("Should have been resolved after parsing!"); + } + } + } + + fn each_depending_on<F>(&self, id: TypeId, mut f: F) + where + F: FnMut(TypeId), + { + if let Some(edges) = self.dependencies.get(&id) { + for ty in edges { + trace!("enqueue {:?} into worklist", ty); + f(*ty); + } + } + } +} + +impl<'ctx> From<SizednessAnalysis<'ctx>> for HashMap<TypeId, SizednessResult> { + fn from(analysis: SizednessAnalysis<'ctx>) -> Self { + // We let the lack of an entry mean "ZeroSized" to save space. + extra_assert!(analysis + .sized + .values() + .all(|v| { *v != SizednessResult::ZeroSized })); + + analysis.sized + } +} + +/// A convenience trait for querying whether some type or id is sized. +/// +/// This is not for _computing_ whether the thing is sized, it is for looking up +/// the results of the `Sizedness` analysis's computations for a specific thing. +pub trait Sizedness { + /// Get the sizedness of this type. + fn sizedness(&self, ctx: &BindgenContext) -> SizednessResult; + + /// Is the sizedness for this type `SizednessResult::ZeroSized`? + fn is_zero_sized(&self, ctx: &BindgenContext) -> bool { + self.sizedness(ctx) == SizednessResult::ZeroSized + } +} |