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 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 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 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 type TraversalPredicate = for<'a> fn(&'a BindgenContext, Edge) -> bool;
186
187/// A `TraversalPredicate` implementation that follows all edges, and therefore
188/// traversals using this predicate will see the whole IR graph reachable from
189/// the traversal's roots.
190pub fn all_edges(_: &BindgenContext, _: Edge) -> bool {
191 true
192}
193
194/// A `TraversalPredicate` implementation that only follows
195/// `EdgeKind::InnerType` edges, and therefore traversals using this predicate
196/// will only visit the traversal's roots and their inner types. This is used
197/// in no-recursive-allowlist mode, where inner types such as anonymous
198/// structs/unions still need to be processed.
199pub fn only_inner_type_edges(_: &BindgenContext, edge: Edge) -> bool {
200 edge.kind == EdgeKind::InnerType
201}
202
203/// A `TraversalPredicate` implementation that only follows edges to items that
204/// are enabled for code generation. This lets us skip considering items for
205/// which are not reachable from code generation.
206pub fn codegen_edges(ctx: &BindgenContext, edge: Edge) -> bool {
207 let cc = &ctx.options().codegen_config;
208 match edge.kind {
209 EdgeKind::Generic => {
210 ctx.resolve_item(edge.to).is_enabled_for_codegen(ctx)
211 }
212
213 // We statically know the kind of item that non-generic edges can point
214 // to, so we don't need to actually resolve the item and check
215 // `Item::is_enabled_for_codegen`.
216 EdgeKind::TemplateParameterDefinition |
217 EdgeKind::TemplateArgument |
218 EdgeKind::TemplateDeclaration |
219 EdgeKind::BaseMember |
220 EdgeKind::Field |
221 EdgeKind::InnerType |
222 EdgeKind::FunctionReturn |
223 EdgeKind::FunctionParameter |
224 EdgeKind::VarType |
225 EdgeKind::TypeReference => cc.types(),
226 EdgeKind::InnerVar => cc.vars(),
227 EdgeKind::Method => cc.methods(),
228 EdgeKind::Constructor => cc.constructors(),
229 EdgeKind::Destructor => cc.destructors(),
230 }
231}
232
233/// The storage for the set of items that have been seen (although their
234/// outgoing edges might not have been fully traversed yet) in an active
235/// traversal.
236pub trait TraversalStorage<'ctx> {
237 /// Construct a new instance of this TraversalStorage, for a new traversal.
238 fn new(ctx: &'ctx BindgenContext) -> Self;
239
240 /// Add the given item to the storage. If the item has never been seen
241 /// before, return `true`. Otherwise, return `false`.
242 ///
243 /// The `from` item is the item from which we discovered this item, or is
244 /// `None` if this item is a root.
245 fn add(&mut self, from: Option<ItemId>, item: ItemId) -> bool;
246}
247
248impl<'ctx> TraversalStorage<'ctx> for ItemSet {
249 fn new(_: &'ctx BindgenContext) -> Self {
250 ItemSet::new()
251 }
252
253 fn add(&mut self, _: Option<ItemId>, item: ItemId) -> bool {
254 self.insert(item)
255 }
256}
257
258/// A `TraversalStorage` implementation that keeps track of how we first reached
259/// each item. This is useful for providing debug assertions with meaningful
260/// diagnostic messages about dangling items.
261#[derive(Debug)]
262pub struct Paths<'ctx>(BTreeMap<ItemId, ItemId>, &'ctx BindgenContext);
263
264impl<'ctx> TraversalStorage<'ctx> for Paths<'ctx> {
265 fn new(ctx: &'ctx BindgenContext) -> Self {
266 Paths(BTreeMap::new(), ctx)
267 }
268
269 fn add(&mut self, from: Option<ItemId>, item: ItemId) -> bool {
270 let newly_discovered =
271 self.0.insert(item, from.unwrap_or(item)).is_none();
272
273 if self.1.resolve_item_fallible(item).is_none() {
274 let mut path = vec![];
275 let mut current = item;
276 loop {
277 let predecessor = *self.0.get(&current).expect(
278 "We know we found this item id, so it must have a \
279 predecessor",
280 );
281 if predecessor == current {
282 break;
283 }
284 path.push(predecessor);
285 current = predecessor;
286 }
287 path.reverse();
288 panic!(
289 "Found reference to dangling id = {:?}\nvia path = {:?}",
290 item, 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 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 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, kind: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 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 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 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 = Edge::new(to:item, kind);
433 if !(self.predicate)(self.ctx, edge) {
434 return;
435 }
436
437 let is_newly_discovered: bool =
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: ItemId = self.queue.next()?;
454
455 let newly_discovered: bool = self.seen.add(from:None, item: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 type AssertNoDanglingItemsTraversal<'ctx> =
478 ItemTraversal<'ctx, Paths<'ctx>, VecDeque<ItemId>>;
479