path: root/src/ir/traversal.rs

//! Traversal of the graph of IR items and types.

use super::context::{BindgenContext, ItemId};
use super::item::ItemSet;
use std::collections::{BTreeMap, VecDeque};

/// An outgoing edge in the IR graph is a reference from some item to another
/// item:
///
///   from --> to
///
/// The `from` is left implicit: it is the concrete `Trace` implementer which
/// yielded this outgoing edge.
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Edge {
    to: ItemId,
    kind: EdgeKind,
}

impl Edge {
    /// Construct a new edge whose referent is `to` and is of the given `kind`.
    pub fn new(to: ItemId, kind: EdgeKind) -> Edge {
        Edge { to, kind }
    }
}

impl From<Edge> for ItemId {
    fn from(val: Edge) -> Self {
        val.to
    }
}

/// The kind of edge reference. This is useful when we wish to only consider
/// certain kinds of edges for a particular traversal or analysis.
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum EdgeKind {
    /// A generic, catch-all edge.
    Generic,

    /// An edge from a template declaration, to the definition of a named type
    /// parameter. For example, the edge from `Foo<T>` to `T` in the following
    /// snippet:
    ///
    /// ```C++
    /// template<typename T>
    /// class Foo { };
    /// ```
    TemplateParameterDefinition,

    /// An edge from a template instantiation to the template declaration that
    /// is being instantiated. For example, the edge from `Foo<int>` to
    /// to `Foo<T>`:
    ///
    /// ```C++
    /// template<typename T>
    /// class Foo { };
    ///
    /// using Bar = Foo<ant>;
    /// ```
    TemplateDeclaration,

    /// An edge from a template instantiation to its template argument. For
    /// example, `Foo<Bar>` to `Bar`:
    ///
    /// ```C++
    /// template<typename T>
    /// class Foo { };
    ///
    /// class Bar { };
    ///
    /// using FooBar = Foo<Bar>;
    /// ```
    TemplateArgument,

    /// An edge from a compound type to one of its base member types. For
    /// example, the edge from `Bar` to `Foo`:
    ///
    /// ```C++
    /// class Foo { };
    ///
    /// class Bar : public Foo { };
    /// ```
    BaseMember,

    /// An edge from a compound type to the types of one of its fields. For
    /// example, the edge from `Foo` to `int`:
    ///
    /// ```C++
    /// class Foo {
    ///     int x;
    /// };
    /// ```
    Field,

    /// An edge from an class or struct type to an inner type member. For
    /// example, the edge from `Foo` to `Foo::Bar` here:
    ///
    /// ```C++
    /// class Foo {
    ///     struct Bar { };
    /// };
    /// ```
    InnerType,

    /// An edge from an class or struct type to an inner static variable. For
    /// example, the edge from `Foo` to `Foo::BAR` here:
    ///
    /// ```C++
    /// class Foo {
    ///     static const char* BAR;
    /// };
    /// ```
    InnerVar,

    /// An edge from a class or struct type to one of its method functions. For
    /// example, the edge from `Foo` to `Foo::bar`:
    ///
    /// ```C++
    /// class Foo {
    ///     bool bar(int x, int y);
    /// };
    /// ```
    Method,

    /// An edge from a class or struct type to one of its constructor
    /// functions. For example, the edge from `Foo` to `Foo::Foo(int x, int y)`:
    ///
    /// ```C++
    /// class Foo {
    ///     int my_x;
    ///     int my_y;
    ///
    ///   public:
    ///     Foo(int x, int y);
    /// };
    /// ```
    Constructor,

    /// An edge from a class or struct type to its destructor function. For
    /// example, the edge from `Doggo` to `Doggo::~Doggo()`:
    ///
    /// ```C++
    /// struct Doggo {
    ///     char* wow;
    ///
    ///   public:
    ///     ~Doggo();
    /// };
    /// ```
    Destructor,

    /// An edge from a function declaration to its return type. For example, the
    /// edge from `foo` to `int`:
    ///
    /// ```C++
    /// int foo(char* string);
    /// ```
    FunctionReturn,

    /// An edge from a function declaration to one of its parameter types. For
    /// example, the edge from `foo` to `char*`:
    ///
    /// ```C++
    /// int foo(char* string);
    /// ```
    FunctionParameter,

    /// An edge from a static variable to its type. For example, the edge from
    /// `FOO` to `const char*`:
    ///
    /// ```C++
    /// static const char* FOO;
    /// ```
    VarType,

    /// An edge from a non-templated alias or typedef to the referenced type.
    TypeReference,
}

/// A predicate to allow visiting only sub-sets of the whole IR graph by
/// excluding certain edges from being followed by the traversal.
pub trait TraversalPredicate {
    /// Should the traversal follow this edge, and visit everything that is
    /// reachable through it?
    fn should_follow(&self, ctx: &BindgenContext, edge: Edge) -> bool;
}

impl TraversalPredicate for for<'a> fn(&'a BindgenContext, Edge) -> bool {
    fn should_follow(&self, ctx: &BindgenContext, edge: Edge) -> bool {
        (*self)(ctx, edge)
    }
}

/// A `TraversalPredicate` implementation that follows all edges, and therefore
/// traversals using this predicate will see the whole IR graph reachable from
/// the traversal's roots.
pub fn all_edges(_: &BindgenContext, _: Edge) -> bool {
    true
}

/// A `TraversalPredicate` implementation that only follows
/// `EdgeKind::InnerType` edges, and therefore traversals using this predicate
/// will only visit the traversal's roots and their inner types. This is used
/// in no-recursive-allowlist mode, where inner types such as anonymous
/// structs/unions still need to be processed.
pub fn only_inner_type_edges(_: &BindgenContext, edge: Edge) -> bool {
    edge.kind == EdgeKind::InnerType
}

/// A `TraversalPredicate` implementation that only follows edges to items that
/// are enabled for code generation. This lets us skip considering items for
/// which are not reachable from code generation.
pub fn codegen_edges(ctx: &BindgenContext, edge: Edge) -> bool {
    let cc = &ctx.options().codegen_config;
    match edge.kind {
        EdgeKind::Generic => {
            ctx.resolve_item(edge.to).is_enabled_for_codegen(ctx)
        }

        // We statically know the kind of item that non-generic edges can point
        // to, so we don't need to actually resolve the item and check
        // `Item::is_enabled_for_codegen`.
        EdgeKind::TemplateParameterDefinition |
        EdgeKind::TemplateArgument |
        EdgeKind::TemplateDeclaration |
        EdgeKind::BaseMember |
        EdgeKind::Field |
        EdgeKind::InnerType |
        EdgeKind::FunctionReturn |
        EdgeKind::FunctionParameter |
        EdgeKind::VarType |
        EdgeKind::TypeReference => cc.types(),
        EdgeKind::InnerVar => cc.vars(),
        EdgeKind::Method => cc.methods(),
        EdgeKind::Constructor => cc.constructors(),
        EdgeKind::Destructor => cc.destructors(),
    }
}

/// The storage for the set of items that have been seen (although their
/// outgoing edges might not have been fully traversed yet) in an active
/// traversal.
pub trait TraversalStorage<'ctx> {
    /// Construct a new instance of this TraversalStorage, for a new traversal.
    fn new(ctx: &'ctx BindgenContext) -> Self;

    /// Add the given item to the storage. If the item has never been seen
    /// before, return `true`. Otherwise, return `false`.
    ///
    /// The `from` item is the item from which we discovered this item, or is
    /// `None` if this item is a root.
    fn add(&mut self, from: Option<ItemId>, item: ItemId) -> bool;
}

impl<'ctx> TraversalStorage<'ctx> for ItemSet {
    fn new(_: &'ctx BindgenContext) -> Self {
        ItemSet::new()
    }

    fn add(&mut self, _: Option<ItemId>, item: ItemId) -> bool {
        self.insert(item)
    }
}

/// A `TraversalStorage` implementation that keeps track of how we first reached
/// each item. This is useful for providing debug assertions with meaningful
/// diagnostic messages about dangling items.
#[derive(Debug)]
pub struct Paths<'ctx>(BTreeMap<ItemId, ItemId>, &'ctx BindgenContext);

impl<'ctx> TraversalStorage<'ctx> for Paths<'ctx> {
    fn new(ctx: &'ctx BindgenContext) -> Self {
        Paths(BTreeMap::new(), ctx)
    }

    fn add(&mut self, from: Option<ItemId>, item: ItemId) -> bool {
        let newly_discovered =
            self.0.insert(item, from.unwrap_or(item)).is_none();

        if self.1.resolve_item_fallible(item).is_none() {
            let mut path = vec![];
            let mut current = item;
            loop {
                let predecessor = *self.0.get(&current).expect(
                    "We know we found this item id, so it must have a \
                     predecessor",
                );
                if predecessor == current {
                    break;
                }
                path.push(predecessor);
                current = predecessor;
            }
            path.reverse();
            panic!(
                "Found reference to dangling id = {:?}\nvia path = {:?}",
                item, path
            );
        }

        newly_discovered
    }
}

/// The queue of seen-but-not-yet-traversed items.
///
/// Using a FIFO queue with a traversal will yield a breadth-first traversal,
/// while using a LIFO queue will result in a depth-first traversal of the IR
/// graph.
pub trait TraversalQueue: Default {
    /// Add a newly discovered item to the queue.
    fn push(&mut self, item: ItemId);

    /// Pop the next item to traverse, if any.
    fn next(&mut self) -> Option<ItemId>;
}

impl TraversalQueue for Vec<ItemId> {
    fn push(&mut self, item: ItemId) {
        self.push(item);
    }

    fn next(&mut self) -> Option<ItemId> {
        self.pop()
    }
}

impl TraversalQueue for VecDeque<ItemId> {
    fn push(&mut self, item: ItemId) {
        self.push_back(item);
    }

    fn next(&mut self) -> Option<ItemId> {
        self.pop_front()
    }
}

/// Something that can receive edges from a `Trace` implementation.
pub trait Tracer {
    /// Note an edge between items. Called from within a `Trace` implementation.
    fn visit_kind(&mut self, item: ItemId, kind: EdgeKind);

    /// A synonym for `tracer.visit_kind(item, EdgeKind::Generic)`.
    fn visit(&mut self, item: ItemId) {
        self.visit_kind(item, EdgeKind::Generic);
    }
}

impl<F> Tracer for F
where
    F: FnMut(ItemId, EdgeKind),
{
    fn visit_kind(&mut self, item: ItemId, kind: EdgeKind) {
        (*self)(item, kind)
    }
}

/// Trace all of the outgoing edges to other items. Implementations should call
/// one of `tracer.visit(edge)` or `tracer.visit_kind(edge, EdgeKind::Whatever)`
/// for each of their outgoing edges.
pub trait Trace {
    /// If a particular type needs extra information beyond what it has in
    /// `self` and `context` to find its referenced items, its implementation
    /// can define this associated type, forcing callers to pass the needed
    /// information through.
    type Extra;

    /// Trace all of this item's outgoing edges to other items.
    fn trace<T>(
        &self,
        context: &BindgenContext,
        tracer: &mut T,
        extra: &Self::Extra,
    ) where
        T: Tracer;
}

/// An graph traversal of the transitive closure of references between items.
///
/// See `BindgenContext::allowlisted_items` for more information.
pub struct ItemTraversal<'ctx, Storage, Queue, Predicate>
where
    Storage: TraversalStorage<'ctx>,
    Queue: TraversalQueue,
    Predicate: TraversalPredicate,
{
    ctx: &'ctx BindgenContext,

    /// The set of items we have seen thus far in this traversal.
    seen: Storage,

    /// The set of items that we have seen, but have yet to traverse.
    queue: Queue,

    /// The predicate that determines which edges this traversal will follow.
    predicate: Predicate,

    /// The item we are currently traversing.
    currently_traversing: Option<ItemId>,
}

impl<'ctx, Storage, Queue, Predicate>
    ItemTraversal<'ctx, Storage, Queue, Predicate>
where
    Storage: TraversalStorage<'ctx>,
    Queue: TraversalQueue,
    Predicate: TraversalPredicate,
{
    /// Begin a new traversal, starting from the given roots.
    pub fn new<R>(
        ctx: &'ctx BindgenContext,
        roots: R,
        predicate: Predicate,
    ) -> ItemTraversal<'ctx, Storage, Queue, Predicate>
    where
        R: IntoIterator<Item = ItemId>,
    {
        let mut seen = Storage::new(ctx);
        let mut queue = Queue::default();

        for id in roots {
            seen.add(None, id);
            queue.push(id);
        }

        ItemTraversal {
            ctx,
            seen,
            queue,
            predicate,
            currently_traversing: None,
        }
    }
}

impl<'ctx, Storage, Queue, Predicate> Tracer
    for ItemTraversal<'ctx, Storage, Queue, Predicate>
where
    Storage: TraversalStorage<'ctx>,
    Queue: TraversalQueue,
    Predicate: TraversalPredicate,
{
    fn visit_kind(&mut self, item: ItemId, kind: EdgeKind) {
        let edge = Edge::new(item, kind);
        if !self.predicate.should_follow(self.ctx, edge) {
            return;
        }

        let is_newly_discovered =
            self.seen.add(self.currently_traversing, item);
        if is_newly_discovered {
            self.queue.push(item)
        }
    }
}

impl<'ctx, Storage, Queue, Predicate> Iterator
    for ItemTraversal<'ctx, Storage, Queue, Predicate>
where
    Storage: TraversalStorage<'ctx>,
    Queue: TraversalQueue,
    Predicate: TraversalPredicate,
{
    type Item = ItemId;

    fn next(&mut self) -> Option<Self::Item> {
        let id = self.queue.next()?;

        let newly_discovered = self.seen.add(None, id);
        debug_assert!(
            !newly_discovered,
            "should have already seen anything we get out of our queue"
        );
        debug_assert!(
            self.ctx.resolve_item_fallible(id).is_some(),
            "should only get IDs of actual items in our context during traversal"
        );

        self.currently_traversing = Some(id);
        id.trace(self.ctx, self, &());
        self.currently_traversing = None;

        Some(id)
    }
}

/// An iterator to find any dangling items.
///
/// See `BindgenContext::assert_no_dangling_item_traversal` for more
/// information.
pub type AssertNoDanglingItemsTraversal<'ctx> = ItemTraversal<
    'ctx,
    Paths<'ctx>,
    VecDeque<ItemId>,
    for<'a> fn(&'a BindgenContext, Edge) -> bool,
>;

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[allow(dead_code)]
    fn traversal_predicate_is_object_safe() {
        // This should compile only if TraversalPredicate is object safe.
        fn takes_by_trait_object(_: &dyn TraversalPredicate) {}
    }
}