summaryrefslogtreecommitdiffstats
path: root/third_party/rust/bindgen/ir/traversal.rs
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--third_party/rust/bindgen/ir/traversal.rs478
1 files changed, 478 insertions, 0 deletions
diff --git a/third_party/rust/bindgen/ir/traversal.rs b/third_party/rust/bindgen/ir/traversal.rs
new file mode 100644
index 0000000000..f14483f295
--- /dev/null
+++ b/third_party/rust/bindgen/ir/traversal.rs
@@ -0,0 +1,478 @@
+//! 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.
+///
+/// The predicate must return true if the traversal should follow this edge
+/// and visit everything that is reachable through it.
+pub type TraversalPredicate = for<'a> fn(&'a BindgenContext, Edge) -> bool;
+
+/// 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>
+where
+ Storage: TraversalStorage<'ctx>,
+ Queue: TraversalQueue,
+{
+ 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: TraversalPredicate,
+
+ /// The item we are currently traversing.
+ currently_traversing: Option<ItemId>,
+}
+
+impl<'ctx, Storage, Queue> ItemTraversal<'ctx, Storage, Queue>
+where
+ Storage: TraversalStorage<'ctx>,
+ Queue: TraversalQueue,
+{
+ /// Begin a new traversal, starting from the given roots.
+ pub fn new<R>(
+ ctx: &'ctx BindgenContext,
+ roots: R,
+ predicate: TraversalPredicate,
+ ) -> ItemTraversal<'ctx, Storage, Queue>
+ 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> Tracer for ItemTraversal<'ctx, Storage, Queue>
+where
+ Storage: TraversalStorage<'ctx>,
+ Queue: TraversalQueue,
+{
+ fn visit_kind(&mut self, item: ItemId, kind: EdgeKind) {
+ let edge = Edge::new(item, kind);
+ if !(self.predicate)(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> Iterator for ItemTraversal<'ctx, Storage, Queue>
+where
+ Storage: TraversalStorage<'ctx>,
+ Queue: TraversalQueue,
+{
+ 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>>;
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 12:54:26 +0000