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 = {:?}\nvia path = {:?}",
291 item, path
292 );
293 }
294
295 newly_discovered
296 }
297}
298
299/// The queue of seen-but-not-yet-traversed items.
300///
301/// Using a FIFO queue with a traversal will yield a breadth-first traversal,
302/// while using a LIFO queue will result in a depth-first traversal of the IR
303/// graph.
304pub(crate) trait TraversalQueue: Default {
305 /// Add a newly discovered item to the queue.
306 fn push(&mut self, item: ItemId);
307
308 /// Pop the next item to traverse, if any.
309 fn next(&mut self) -> Option<ItemId>;
310}
311
312impl TraversalQueue for Vec<ItemId> {
313 fn push(&mut self, item: ItemId) {
314 self.push(item);
315 }
316
317 fn next(&mut self) -> Option<ItemId> {
318 self.pop()
319 }
320}
321
322impl TraversalQueue for VecDeque<ItemId> {
323 fn push(&mut self, item: ItemId) {
324 self.push_back(item);
325 }
326
327 fn next(&mut self) -> Option<ItemId> {
328 self.pop_front()
329 }
330}
331
332/// Something that can receive edges from a `Trace` implementation.
333pub(crate) trait Tracer {
334 /// Note an edge between items. Called from within a `Trace` implementation.
335 fn visit_kind(&mut self, item: ItemId, kind: EdgeKind);
336
337 /// A synonym for `tracer.visit_kind(item, EdgeKind::Generic)`.
338 fn visit(&mut self, item: ItemId) {
339 self.visit_kind(item, kind:EdgeKind::Generic);
340 }
341}
342
343impl<F> Tracer for F
344where
345 F: FnMut(ItemId, EdgeKind),
346{
347 fn visit_kind(&mut self, item: ItemId, kind: EdgeKind) {
348 (*self)(item, kind)
349 }
350}
351
352/// Trace all of the outgoing edges to other items. Implementations should call
353/// one of `tracer.visit(edge)` or `tracer.visit_kind(edge, EdgeKind::Whatever)`
354/// for each of their outgoing edges.
355pub(crate) trait Trace {
356 /// If a particular type needs extra information beyond what it has in
357 /// `self` and `context` to find its referenced items, its implementation
358 /// can define this associated type, forcing callers to pass the needed
359 /// information through.
360 type Extra;
361
362 /// Trace all of this item's outgoing edges to other items.
363 fn trace<T>(
364 &self,
365 context: &BindgenContext,
366 tracer: &mut T,
367 extra: &Self::Extra,
368 ) where
369 T: Tracer;
370}
371
372/// An graph traversal of the transitive closure of references between items.
373///
374/// See `BindgenContext::allowlisted_items` for more information.
375pub(crate) struct ItemTraversal<'ctx, Storage, Queue>
376where
377 Storage: TraversalStorage<'ctx>,
378 Queue: TraversalQueue,
379{
380 ctx: &'ctx BindgenContext,
381
382 /// The set of items we have seen thus far in this traversal.
383 seen: Storage,
384
385 /// The set of items that we have seen, but have yet to traverse.
386 queue: Queue,
387
388 /// The predicate that determines which edges this traversal will follow.
389 predicate: TraversalPredicate,
390
391 /// The item we are currently traversing.
392 currently_traversing: Option<ItemId>,
393}
394
395impl<'ctx, Storage, Queue> ItemTraversal<'ctx, Storage, Queue>
396where
397 Storage: TraversalStorage<'ctx>,
398 Queue: TraversalQueue,
399{
400 /// Begin a new traversal, starting from the given roots.
401 pub(crate) fn new<R>(
402 ctx: &'ctx BindgenContext,
403 roots: R,
404 predicate: TraversalPredicate,
405 ) -> ItemTraversal<'ctx, Storage, Queue>
406 where
407 R: IntoIterator<Item = ItemId>,
408 {
409 let mut seen = Storage::new(ctx);
410 let mut queue = Queue::default();
411
412 for id in roots {
413 seen.add(None, id);
414 queue.push(id);
415 }
416
417 ItemTraversal {
418 ctx,
419 seen,
420 queue,
421 predicate,
422 currently_traversing: None,
423 }
424 }
425}
426
427impl<'ctx, Storage, Queue> Tracer for ItemTraversal<'ctx, Storage, Queue>
428where
429 Storage: TraversalStorage<'ctx>,
430 Queue: TraversalQueue,
431{
432 fn visit_kind(&mut self, item: ItemId, kind: EdgeKind) {
433 let edge: Edge = Edge::new(to:item, kind);
434 if !(self.predicate)(self.ctx, edge) {
435 return;
436 }
437
438 let is_newly_discovered: bool =
439 self.seen.add(self.currently_traversing, item);
440 if is_newly_discovered {
441 self.queue.push(item)
442 }
443 }
444}
445
446impl<'ctx, Storage, Queue> Iterator for ItemTraversal<'ctx, Storage, Queue>
447where
448 Storage: TraversalStorage<'ctx>,
449 Queue: TraversalQueue,
450{
451 type Item = ItemId;
452
453 fn next(&mut self) -> Option<Self::Item> {
454 let id: ItemId = self.queue.next()?;
455
456 let newly_discovered: bool = self.seen.add(from:None, item:id);
457 debug_assert!(
458 !newly_discovered,
459 "should have already seen anything we get out of our queue"
460 );
461 debug_assert!(
462 self.ctx.resolve_item_fallible(id).is_some(),
463 "should only get IDs of actual items in our context during traversal"
464 );
465
466 self.currently_traversing = Some(id);
467 id.trace(self.ctx, self, &());
468 self.currently_traversing = None;
469
470 Some(id)
471 }
472}
473
474/// An iterator to find any dangling items.
475///
476/// See `BindgenContext::assert_no_dangling_item_traversal` for more
477/// information.
478pub(crate) type AssertNoDanglingItemsTraversal<'ctx> =
479 ItemTraversal<'ctx, Paths<'ctx>, VecDeque<ItemId>>;
480