path: root/src/ir/analysis/sizedness.rs

//! 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 {
        match kind {
            // These are the only edges that can affect whether a type is
            // zero-sized or not.
            EdgeKind::TemplateArgument |
            EdgeKind::TemplateParameterDefinition |
            EdgeKind::TemplateDeclaration |
            EdgeKind::TypeReference |
            EdgeKind::BaseMember |
            EdgeKind::Field => true,
            _ => false,
        }
    }

    /// 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
    }
}