bindgen/ir/
traversal.rs

Help
1//! Traversal of the graph of IR items and types.
2
3use super::context::{BindgenContext, ItemId};
4use super::item::ItemSet;
5use std::collections::{BTreeMap, VecDeque};
6
7/// An outgoing edge in the IR graph is a reference from some item to another
8/// item:
9///
10///   from --> to
11///
12/// The `from` is left implicit: it is the concrete `Trace` implementer which
13/// yielded this outgoing edge.
14#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
15pub(crate) struct Edge {
16    to: ItemId,
17    kind: EdgeKind,
18}
19
20impl Edge {
21    /// Construct a new edge whose referent is `to` and is of the given `kind`.
22    pub(crate) fn new(to: ItemId, kind: EdgeKind) -> Edge {
23        Edge { to, kind }
24    }
25}
26
27impl From<Edge> for ItemId {
28    fn from(val: Edge) -> Self {
29        val.to
30    }
31}
32
33/// The kind of edge reference. This is useful when we wish to only consider
34/// certain kinds of edges for a particular traversal or analysis.
35#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
36pub(crate) enum EdgeKind {
37    /// A generic, catch-all edge.
38    Generic,
39
40    /// An edge from a template declaration, to the definition of a named type
41    /// parameter. For example, the edge from `Foo<T>` to `T` in the following
42    /// snippet:
43    ///
44    /// ```C++
45    /// template<typename T>
46    /// class Foo { };
47    /// ```
48    TemplateParameterDefinition,
49
50    /// An edge from a template instantiation to the template declaration that
51    /// is being instantiated. For example, the edge from `Foo<int>` to
52    /// to `Foo<T>`:
53    ///
54    /// ```C++
55    /// template<typename T>
56    /// class Foo { };
57    ///
58    /// using Bar = Foo<ant>;
59    /// ```
60    TemplateDeclaration,
61
62    /// An edge from a template instantiation to its template argument. For
63    /// example, `Foo<Bar>` to `Bar`:
64    ///
65    /// ```C++
66    /// template<typename T>
67    /// class Foo { };
68    ///
69    /// class Bar { };
70    ///
71    /// using FooBar = Foo<Bar>;
72    /// ```
73    TemplateArgument,
74
75    /// An edge from a compound type to one of its base member types. For
76    /// example, the edge from `Bar` to `Foo`:
77    ///
78    /// ```C++
79    /// class Foo { };
80    ///
81    /// class Bar : public Foo { };
82    /// ```
83    BaseMember,
84
85    /// An edge from a compound type to the types of one of its fields. For
86    /// example, the edge from `Foo` to `int`:
87    ///
88    /// ```C++
89    /// class Foo {
90    ///     int x;
91    /// };
92    /// ```
93    Field,
94
95    /// An edge from an class or struct type to an inner type member. For
96    /// example, the edge from `Foo` to `Foo::Bar` here:
97    ///
98    /// ```C++
99    /// class Foo {
100    ///     struct Bar { };
101    /// };
102    /// ```
103    InnerType,
104
105    /// An edge from an class or struct type to an inner static variable. For
106    /// example, the edge from `Foo` to `Foo::BAR` here:
107    ///
108    /// ```C++
109    /// class Foo {
110    ///     static const char* BAR;
111    /// };
112    /// ```
113    InnerVar,
114
115    /// An edge from a class or struct type to one of its method functions. For
116    /// example, the edge from `Foo` to `Foo::bar`:
117    ///
118    /// ```C++
119    /// class Foo {
120    ///     bool bar(int x, int y);
121    /// };
122    /// ```
123    Method,
124
125    /// An edge from a class or struct type to one of its constructor
126    /// functions. For example, the edge from `Foo` to `Foo::Foo(int x, int y)`:
127    ///
128    /// ```C++
129    /// class Foo {
130    ///     int my_x;
131    ///     int my_y;
132    ///
133    ///   public:
134    ///     Foo(int x, int y);
135    /// };
136    /// ```
137    Constructor,
138
139    /// An edge from a class or struct type to its destructor function. For
140    /// example, the edge from `Doggo` to `Doggo::~Doggo()`:
141    ///
142    /// ```C++
143    /// struct Doggo {
144    ///     char* wow;
145    ///
146    ///   public:
147    ///     ~Doggo();
148    /// };
149    /// ```
150    Destructor,
151
152    /// An edge from a function declaration to its return type. For example, the
153    /// edge from `foo` to `int`:
154    ///
155    /// ```C++
156    /// int foo(char* string);
157    /// ```
158    FunctionReturn,
159
160    /// An edge from a function declaration to one of its parameter types. For
161    /// example, the edge from `foo` to `char*`:
162    ///
163    /// ```C++
164    /// int foo(char* string);
165    /// ```
166    FunctionParameter,
167
168    /// An edge from a static variable to its type. For example, the edge from
169    /// `FOO` to `const char*`:
170    ///
171    /// ```C++
172    /// static const char* FOO;
173    /// ```
174    VarType,
175
176    /// An edge from a non-templated alias or typedef to the referenced type.
177    TypeReference,
178}
179
180/// A predicate to allow visiting only sub-sets of the whole IR graph by
181/// excluding certain edges from being followed by the traversal.
182///
183/// The predicate must return true if the traversal should follow this edge
184/// and visit everything that is reachable through it.
185pub(crate) type TraversalPredicate =
186    for<'a> fn(&'a BindgenContext, Edge) -> bool;
187
188/// A `TraversalPredicate` implementation that follows all edges, and therefore
189/// traversals using this predicate will see the whole IR graph reachable from
190/// the traversal's roots.
191pub(crate) fn all_edges(_: &BindgenContext, _: Edge) -> bool {
192    true
193}
194
195/// A `TraversalPredicate` implementation that only follows
196/// `EdgeKind::InnerType` edges, and therefore traversals using this predicate
197/// will only visit the traversal's roots and their inner types. This is used
198/// in no-recursive-allowlist mode, where inner types such as anonymous
199/// structs/unions still need to be processed.
200pub(crate) fn only_inner_type_edges(_: &BindgenContext, edge: Edge) -> bool {
201    edge.kind == EdgeKind::InnerType
202}
203
204/// A `TraversalPredicate` implementation that only follows edges to items that
205/// are enabled for code generation. This lets us skip considering items for
206/// which are not reachable from code generation.
207pub(crate) fn codegen_edges(ctx: &BindgenContext, edge: Edge) -> bool {
208    let cc = &ctx.options().codegen_config;
209    match edge.kind {
210        EdgeKind::Generic => {
211            ctx.resolve_item(edge.to).is_enabled_for_codegen(ctx)
212        }
213
214        // We statically know the kind of item that non-generic edges can point
215        // to, so we don't need to actually resolve the item and check
216        // `Item::is_enabled_for_codegen`.
217        EdgeKind::TemplateParameterDefinition |
218        EdgeKind::TemplateArgument |
219        EdgeKind::TemplateDeclaration |
220        EdgeKind::BaseMember |
221        EdgeKind::Field |
222        EdgeKind::InnerType |
223        EdgeKind::FunctionReturn |
224        EdgeKind::FunctionParameter |
225        EdgeKind::VarType |
226        EdgeKind::TypeReference => cc.types(),
227        EdgeKind::InnerVar => cc.vars(),
228        EdgeKind::Method => cc.methods(),
229        EdgeKind::Constructor => cc.constructors(),
230        EdgeKind::Destructor => cc.destructors(),
231    }
232}
233
234/// The storage for the set of items that have been seen (although their
235/// outgoing edges might not have been fully traversed yet) in an active
236/// traversal.
237pub(crate) trait TraversalStorage<'ctx> {
238    /// Construct a new instance of this `TraversalStorage`, for a new traversal.
239    fn new(ctx: &'ctx BindgenContext) -> Self;
240
241    /// Add the given item to the storage. If the item has never been seen
242    /// before, return `true`. Otherwise, return `false`.
243    ///
244    /// The `from` item is the item from which we discovered this item, or is
245    /// `None` if this item is a root.
246    fn add(&mut self, from: Option<ItemId>, item: ItemId) -> bool;
247}
248
249impl<'ctx> TraversalStorage<'ctx> for ItemSet {
250    fn new(_: &'ctx BindgenContext) -> Self {
251        ItemSet::new()
252    }
253
254    fn add(&mut self, _: Option<ItemId>, item: ItemId) -> bool {
255        self.insert(item)
256    }
257}
258
259/// A `TraversalStorage` implementation that keeps track of how we first reached
260/// each item. This is useful for providing debug assertions with meaningful
261/// diagnostic messages about dangling items.
262#[derive(Debug)]
263pub(crate) struct Paths<'ctx>(BTreeMap<ItemId, ItemId>, &'ctx BindgenContext);
264
265impl<'ctx> TraversalStorage<'ctx> for Paths<'ctx> {
266    fn new(ctx: &'ctx BindgenContext) -> Self {
267        Paths(BTreeMap::new(), ctx)
268    }
269
270    fn add(&mut self, from: Option<ItemId>, item: ItemId) -> bool {
271        let newly_discovered =
272            self.0.insert(item, from.unwrap_or(item)).is_none();
273
274        if self.1.resolve_item_fallible(item).is_none() {
275            let mut path = vec![];
276            let mut current = item;
277            loop {
278                let predecessor = *self.0.get(&current).expect(
279                    "We know we found this item id, so it must have a \
280                     predecessor",
281                );
282                if predecessor == current {
283                    break;
284                }
285                path.push(predecessor);
286                current = predecessor;
287            }
288            path.reverse();
289            panic!(
290                "Found reference to dangling id = {item:?}\nvia path = {path:?}"
291            );
292        }
293
294        newly_discovered
295    }
296}
297
298/// The queue of seen-but-not-yet-traversed items.
299///
300/// Using a FIFO queue with a traversal will yield a breadth-first traversal,
301/// while using a LIFO queue will result in a depth-first traversal of the IR
302/// graph.
303pub(crate) trait TraversalQueue: Default {
304    /// Add a newly discovered item to the queue.
305    fn push(&mut self, item: ItemId);
306
307    /// Pop the next item to traverse, if any.
308    fn next(&mut self) -> Option<ItemId>;
309}
310
311impl TraversalQueue for Vec<ItemId> {
312    fn push(&mut self, item: ItemId) {
313        self.push(item);
314    }
315
316    fn next(&mut self) -> Option<ItemId> {
317        self.pop()
318    }
319}
320
321impl TraversalQueue for VecDeque<ItemId> {
322    fn push(&mut self, item: ItemId) {
323        self.push_back(item);
324    }
325
326    fn next(&mut self) -> Option<ItemId> {
327        self.pop_front()
328    }
329}
330
331/// Something that can receive edges from a `Trace` implementation.
332pub(crate) trait Tracer {
333    /// Note an edge between items. Called from within a `Trace` implementation.
334    fn visit_kind(&mut self, item: ItemId, kind: EdgeKind);
335
336    /// A synonym for `tracer.visit_kind(item, EdgeKind::Generic)`.
337    fn visit(&mut self, item: ItemId) {
338        self.visit_kind(item, EdgeKind::Generic);
339    }
340}
341
342impl<F> Tracer for F
343where
344    F: FnMut(ItemId, EdgeKind),
345{
346    fn visit_kind(&mut self, item: ItemId, kind: EdgeKind) {
347        (*self)(item, kind);
348    }
349}
350
351/// Trace all of the outgoing edges to other items. Implementations should call
352/// one of `tracer.visit(edge)` or `tracer.visit_kind(edge, EdgeKind::Whatever)`
353/// for each of their outgoing edges.
354pub(crate) trait Trace {
355    /// If a particular type needs extra information beyond what it has in
356    /// `self` and `context` to find its referenced items, its implementation
357    /// can define this associated type, forcing callers to pass the needed
358    /// information through.
359    type Extra;
360
361    /// Trace all of this item's outgoing edges to other items.
362    fn trace<T>(
363        &self,
364        context: &BindgenContext,
365        tracer: &mut T,
366        extra: &Self::Extra,
367    ) where
368        T: Tracer;
369}
370
371/// An graph traversal of the transitive closure of references between items.
372///
373/// See `BindgenContext::allowlisted_items` for more information.
374pub(crate) struct ItemTraversal<'ctx, Storage, Queue>
375where
376    Storage: TraversalStorage<'ctx>,
377    Queue: TraversalQueue,
378{
379    ctx: &'ctx BindgenContext,
380
381    /// The set of items we have seen thus far in this traversal.
382    seen: Storage,
383
384    /// The set of items that we have seen, but have yet to traverse.
385    queue: Queue,
386
387    /// The predicate that determines which edges this traversal will follow.
388    predicate: TraversalPredicate,
389
390    /// The item we are currently traversing.
391    currently_traversing: Option<ItemId>,
392}
393
394impl<'ctx, Storage, Queue> ItemTraversal<'ctx, Storage, Queue>
395where
396    Storage: TraversalStorage<'ctx>,
397    Queue: TraversalQueue,
398{
399    /// Begin a new traversal, starting from the given roots.
400    pub(crate) fn new<R>(
401        ctx: &'ctx BindgenContext,
402        roots: R,
403        predicate: TraversalPredicate,
404    ) -> ItemTraversal<'ctx, Storage, Queue>
405    where
406        R: IntoIterator<Item = ItemId>,
407    {
408        let mut seen = Storage::new(ctx);
409        let mut queue = Queue::default();
410
411        for id in roots {
412            seen.add(None, id);
413            queue.push(id);
414        }
415
416        ItemTraversal {
417            ctx,
418            seen,
419            queue,
420            predicate,
421            currently_traversing: None,
422        }
423    }
424}
425
426impl<'ctx, Storage, Queue> Tracer for ItemTraversal<'ctx, Storage, Queue>
427where
428    Storage: TraversalStorage<'ctx>,
429    Queue: TraversalQueue,
430{
431    fn visit_kind(&mut self, item: ItemId, kind: EdgeKind) {
432        let edge = Edge::new(item, kind);
433        if !(self.predicate)(self.ctx, edge) {
434            return;
435        }
436
437        let is_newly_discovered =
438            self.seen.add(self.currently_traversing, item);
439        if is_newly_discovered {
440            self.queue.push(item);
441        }
442    }
443}
444
445impl<'ctx, Storage, Queue> Iterator for ItemTraversal<'ctx, Storage, Queue>
446where
447    Storage: TraversalStorage<'ctx>,
448    Queue: TraversalQueue,
449{
450    type Item = ItemId;
451
452    fn next(&mut self) -> Option<Self::Item> {
453        let id = self.queue.next()?;
454
455        let newly_discovered = self.seen.add(None, id);
456        debug_assert!(
457            !newly_discovered,
458            "should have already seen anything we get out of our queue"
459        );
460        debug_assert!(
461            self.ctx.resolve_item_fallible(id).is_some(),
462            "should only get IDs of actual items in our context during traversal"
463        );
464
465        self.currently_traversing = Some(id);
466        id.trace(self.ctx, self, &());
467        self.currently_traversing = None;
468
469        Some(id)
470    }
471}
472
473/// An iterator to find any dangling items.
474///
475/// See `BindgenContext::assert_no_dangling_item_traversal` for more
476/// information.
477pub(crate) type AssertNoDanglingItemsTraversal<'ctx> =
478    ItemTraversal<'ctx, Paths<'ctx>, VecDeque<ItemId>>;
bindgen/ir/traversal.rs

bindgen/ir/
traversal.rs
