summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/codegen/mod.rs6
-rw-r--r--src/ir/comp.rs47
-rw-r--r--src/ir/context.rs177
-rw-r--r--src/ir/function.rs17
-rw-r--r--src/ir/item.rs44
-rw-r--r--src/ir/mod.rs2
-rw-r--r--src/ir/traversal.rs352
-rw-r--r--src/ir/ty.rs34
-rw-r--r--src/ir/type_collector.rs22
9 files changed, 461 insertions, 240 deletions
diff --git a/src/codegen/mod.rs b/src/codegen/mod.rs
index 99400f7a..b626fe34 100644
--- a/src/codegen/mod.rs
+++ b/src/codegen/mod.rs
@@ -12,13 +12,13 @@ use ir::derive::{CanDeriveCopy, CanDeriveDebug, CanDeriveDefault};
use ir::enum_ty::{Enum, EnumVariant, EnumVariantValue};
use ir::function::{Function, FunctionSig};
use ir::int::IntKind;
-use ir::item::{Item, ItemAncestors, ItemCanonicalName, ItemCanonicalPath};
+use ir::item::{Item, ItemAncestors, ItemCanonicalName, ItemCanonicalPath,
+ ItemSet};
use ir::item_kind::ItemKind;
use ir::layout::Layout;
use ir::module::Module;
use ir::objc::ObjCInterface;
use ir::ty::{Type, TypeKind};
-use ir::type_collector::ItemSet;
use ir::var::Var;
use std::borrow::Cow;
@@ -2190,7 +2190,7 @@ impl ToRustTy for Type {
.map(|arg| arg.to_rust_ty(ctx))
.collect::<Vec<_>>();
- path.segments.last_mut().unwrap().parameters = if
+ path.segments.last_mut().unwrap().parameters = if
template_args.is_empty() {
None
} else {
diff --git a/src/ir/comp.rs b/src/ir/comp.rs
index 7c58e233..fff4655c 100644
--- a/src/ir/comp.rs
+++ b/src/ir/comp.rs
@@ -5,8 +5,8 @@ use super::context::{BindgenContext, ItemId};
use super::derive::{CanDeriveCopy, CanDeriveDebug, CanDeriveDefault};
use super::item::Item;
use super::layout::Layout;
+use super::traversal::{EdgeKind, Trace, Tracer};
use super::ty::{TemplateDeclaration, Type};
-use super::type_collector::{ItemSet, TypeCollector};
use clang;
use parse::{ClangItemParser, ParseError};
use std::cell::Cell;
@@ -1075,44 +1075,55 @@ impl<'a> CanDeriveCopy<'a> for CompInfo {
}
}
-impl TypeCollector for CompInfo {
+impl Trace for CompInfo {
type Extra = Item;
- fn collect_types(&self,
- context: &BindgenContext,
- types: &mut ItemSet,
- item: &Item) {
+ fn trace<T>(&self, context: &BindgenContext, tracer: &mut T, item: &Item)
+ where T: Tracer,
+ {
+ // TODO: We should properly distinguish template instantiations from
+ // template declarations at the type level. Why are some template
+ // instantiations represented here instead of as
+ // TypeKind::TemplateInstantiation?
if let Some(template) = self.specialized_template() {
- types.insert(template);
- }
-
- let applicable_template_args = item.applicable_template_args(context);
- for arg in applicable_template_args {
- types.insert(arg);
+ // This is an instantiation of a template declaration with concrete
+ // template type arguments.
+ tracer.visit(template);
+ let args = item.applicable_template_args(context);
+ for a in args {
+ tracer.visit(a);
+ }
+ } else {
+ let params = item.applicable_template_args(context);
+ // This is a template declaration with abstract template type
+ // parameters.
+ for p in params {
+ tracer.visit_kind(p, EdgeKind::TemplateParameterDefinition);
+ }
}
for base in self.base_members() {
- types.insert(base.ty);
+ tracer.visit(base.ty);
}
for field in self.fields() {
- types.insert(field.ty());
+ tracer.visit(field.ty());
}
for &ty in self.inner_types() {
- types.insert(ty);
+ tracer.visit(ty);
}
for &var in self.inner_vars() {
- types.insert(var);
+ tracer.visit(var);
}
for method in self.methods() {
- types.insert(method.signature);
+ tracer.visit(method.signature);
}
for &ctor in self.constructors() {
- types.insert(ctor);
+ tracer.visit(ctor);
}
}
}
diff --git a/src/ir/context.rs b/src/ir/context.rs
index 91ce579c..d2fb2bef 100644
--- a/src/ir/context.rs
+++ b/src/ir/context.rs
@@ -2,11 +2,11 @@
use super::derive::{CanDeriveCopy, CanDeriveDebug, CanDeriveDefault};
use super::int::IntKind;
-use super::item::{Item, ItemCanonicalPath};
+use super::item::{Item, ItemCanonicalPath, ItemSet};
use super::item_kind::ItemKind;
use super::module::{Module, ModuleKind};
+use super::traversal::{self, Edge, ItemTraversal};
use super::ty::{FloatKind, TemplateDeclaration, Type, TypeKind};
-use super::type_collector::{ItemSet, TypeCollector};
use BindgenOptions;
use cexpr;
use chooser::TypeChooser;
@@ -15,7 +15,7 @@ use clang_sys;
use parse::ClangItemParser;
use std::borrow::Cow;
use std::cell::Cell;
-use std::collections::{HashMap, VecDeque, hash_map};
+use std::collections::{HashMap, hash_map};
use std::collections::btree_map::{self, BTreeMap};
use std::fmt;
use std::iter::IntoIterator;
@@ -151,6 +151,13 @@ pub struct BindgenContext<'ctx> {
generated_bindegen_complex: Cell<bool>,
}
+/// A traversal of whitelisted items.
+pub type WhitelistedItems<'ctx, 'gen> = ItemTraversal<'ctx,
+ 'gen,
+ ItemSet,
+ Vec<ItemId>,
+ fn(Edge) -> bool>;
+
impl<'ctx> BindgenContext<'ctx> {
/// Construct the context for the given `options`.
pub fn new(options: BindgenOptions) -> Self {
@@ -538,23 +545,14 @@ impl<'ctx> BindgenContext<'ctx> {
fn assert_no_dangling_item_traversal<'me>
(&'me self)
- -> AssertNoDanglingItemIter<'me, 'ctx> {
+ -> traversal::AssertNoDanglingItemsTraversal<'me, 'ctx> {
assert!(self.in_codegen_phase());
assert!(self.current_module == self.root_module);
- let mut roots = self.items().map(|(&id, _)| id);
-
- let mut seen = BTreeMap::<ItemId, ItemId>::new();
- let next_child = roots.next().map(|id| id).unwrap();
- seen.insert(next_child, next_child);
-
- let to_iterate = seen.iter().map(|(&id, _)| id).rev().collect();
-
- AssertNoDanglingItemIter {
- ctx: self,
- seen: seen,
- to_iterate: to_iterate,
- }
+ let roots = self.items().map(|(&id, _)| id);
+ traversal::AssertNoDanglingItemsTraversal::new(self,
+ roots,
+ traversal::all_edges)
}
// This deserves a comment. Builtin types don't get a valid declaration, so
@@ -1202,8 +1200,7 @@ impl<'ctx> BindgenContext<'ctx> {
///
/// If no items are explicitly whitelisted, then all items are considered
/// whitelisted.
- pub fn whitelisted_items<'me>(&'me self)
- -> WhitelistedItemsIter<'me, 'ctx> {
+ pub fn whitelisted_items<'me>(&'me self) -> WhitelistedItems<'me, 'ctx> {
assert!(self.in_codegen_phase());
assert!(self.current_module == self.root_module);
@@ -1268,18 +1265,19 @@ impl<'ctx> BindgenContext<'ctx> {
})
.map(|(&id, _)| id);
- let seen: ItemSet = roots.collect();
-
- // The .rev() preserves the expected ordering traversal, resulting in
- // more stable-ish bindgen-generated names for anonymous types (like
+ // The reversal preserves the expected ordering of traversal, resulting
+ // in more stable-ish bindgen-generated names for anonymous types (like
// unions).
- let to_iterate = seen.iter().cloned().rev().collect();
+ let mut roots: Vec<_> = roots.collect();
+ roots.reverse();
- WhitelistedItemsIter {
- ctx: self,
- seen: seen,
- to_iterate: to_iterate,
- }
+ let predicate = if self.options().whitelist_recursively {
+ traversal::all_edges
+ } else {
+ traversal::no_edges
+ };
+
+ WhitelistedItems::new(self, roots, predicate)
}
/// Convenient method for getting the prefix to use for most traits in
@@ -1364,124 +1362,3 @@ impl TemplateDeclaration for PartialType {
}
}
}
-
-/// An iterator over whitelisted items.
-///
-/// See `BindgenContext::whitelisted_items` for more information.
-pub struct WhitelistedItemsIter<'ctx, 'gen>
- where 'gen: 'ctx,
-{
- ctx: &'ctx BindgenContext<'gen>,
-
- /// The set of whitelisted items we have seen. If you think of traversing
- /// whitelisted items like GC tracing, this is the mark bits, and contains
- /// both black and gray items.
- seen: ItemSet,
-
- /// The set of whitelisted items that we have seen but have yet to iterate
- /// over and collect transitive references from. To return to the GC analogy,
- /// this is the mark stack, containing the set of gray items which we have
- /// not finished tracing yet.
- to_iterate: Vec<ItemId>,
-}
-
-impl<'ctx, 'gen> Iterator for WhitelistedItemsIter<'ctx, 'gen>
- where 'gen: 'ctx,
-{
- type Item = ItemId;
-
- fn next(&mut self) -> Option<Self::Item> {
- let id = match self.to_iterate.pop() {
- None => return None,
- Some(id) => id,
- };
-
- debug_assert!(self.seen.contains(&id));
- debug_assert!(self.ctx.items.contains_key(&id));
-
- if self.ctx.options().whitelist_recursively {
- let mut sub_types = ItemSet::new();
- id.collect_types(self.ctx, &mut sub_types, &());
-
- for id in sub_types {
- if self.seen.insert(id) {
- self.to_iterate.push(id);
- }
- }
- }
-
- Some(id)
- }
-}
-
-/// An iterator to find any dangling items.
-///
-/// See `BindgenContext::assert_no_dangling_item_traversal` for more
-/// information.
-pub struct AssertNoDanglingItemIter<'ctx, 'gen>
- where 'gen: 'ctx,
-{
- ctx: &'ctx BindgenContext<'gen>,
- seen: BTreeMap<ItemId, ItemId>,
- to_iterate: VecDeque<ItemId>,
-}
-
-impl<'ctx, 'gen> Iterator for AssertNoDanglingItemIter<'ctx, 'gen>
- where 'gen: 'ctx,
-{
- type Item = ItemId;
-
- fn next(&mut self) -> Option<Self::Item> {
- let id = match self.to_iterate.pop_front() {
- None => {
- // We've traversed everything reachable from the previous
- // root(s), see if we have any more roots.
- match self.ctx
- .items()
- .filter(|&(id, _)| !self.seen.contains_key(id))
- .next()
- .map(|(id, _)| *id) {
- None => return None,
- Some(id) => {
- // This is a new root.
- self.seen.insert(id, id);
- id
- }
- }
- }
- Some(id) => id,
- };
-
- let mut sub_types = ItemSet::new();
- id.collect_types(self.ctx, &mut sub_types, &());
-
- if self.ctx.resolve_item_fallible(id).is_none() {
- let mut path = vec![];
- let mut current = id;
- loop {
- let predecessor = *self.seen
- .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 = {:?}",
- id,
- path);
- }
-
- for sub_id in sub_types {
- if self.seen.insert(sub_id, id).is_none() {
- // We've never visited this sub item before.
- self.to_iterate.push_back(sub_id);
- }
- }
-
- Some(id)
- }
-}
diff --git a/src/ir/function.rs b/src/ir/function.rs
index 6273de28..22b9c9b0 100644
--- a/src/ir/function.rs
+++ b/src/ir/function.rs
@@ -2,8 +2,8 @@
use super::context::{BindgenContext, ItemId};
use super::item::Item;
+use super::traversal::{Trace, Tracer};
use super::ty::TypeKind;
-use super::type_collector::{ItemSet, TypeCollector};
use clang;
use clang_sys::CXCallingConv;
use parse::{ClangItemParser, ClangSubItemParser, ParseError, ParseResult};
@@ -316,17 +316,16 @@ impl ClangSubItemParser for Function {
}
}
-impl TypeCollector for FunctionSig {
- type Extra = Item;
+impl Trace for FunctionSig {
+ type Extra = ();
- fn collect_types(&self,
- _context: &BindgenContext,
- types: &mut ItemSet,
- _item: &Item) {
- types.insert(self.return_type());
+ fn trace<T>(&self, _: &BindgenContext, tracer: &mut T, _: &())
+ where T: Tracer,
+ {
+ tracer.visit(self.return_type());
for &(_, ty) in self.argument_types() {
- types.insert(ty);
+ tracer.visit(ty);
}
}
}
diff --git a/src/ir/item.rs b/src/ir/item.rs
index 83e2a41f..4c65c433 100644
--- a/src/ir/item.rs
+++ b/src/ir/item.rs
@@ -6,12 +6,13 @@ use super::derive::{CanDeriveCopy, CanDeriveDebug, CanDeriveDefault};
use super::function::Function;
use super::item_kind::ItemKind;
use super::module::Module;
+use super::traversal::{Trace, Tracer};
use super::ty::{TemplateDeclaration, Type, TypeKind};
-use super::type_collector::{ItemSet, TypeCollector};
use clang;
use clang_sys;
use parse::{ClangItemParser, ClangSubItemParser, ParseError, ParseResult};
use std::cell::{Cell, RefCell};
+use std::collections::BTreeSet;
use std::fmt::Write;
use std::iter;
@@ -166,25 +167,23 @@ impl ItemAncestors for Item {
}
}
-impl TypeCollector for ItemId {
+impl Trace for ItemId {
type Extra = ();
- fn collect_types(&self,
- ctx: &BindgenContext,
- types: &mut ItemSet,
- extra: &()) {
- ctx.resolve_item(*self).collect_types(ctx, types, extra);
+ fn trace<T>(&self, ctx: &BindgenContext, tracer: &mut T, extra: &())
+ where T: Tracer,
+ {
+ ctx.resolve_item(*self).trace(ctx, tracer, extra);
}
}
-impl TypeCollector for Item {
+impl Trace for Item {
type Extra = ();
- fn collect_types(&self,
- ctx: &BindgenContext,
- types: &mut ItemSet,
- _extra: &()) {
- if self.is_hidden(ctx) || types.contains(&self.id()) {
+ fn trace<T>(&self, ctx: &BindgenContext, tracer: &mut T, _extra: &())
+ where T: Tracer,
+ {
+ if self.is_hidden(ctx) {
return;
}
@@ -195,22 +194,25 @@ impl TypeCollector for Item {
// opaque.
if ty.should_be_traced_unconditionally() ||
!self.is_opaque(ctx) {
- ty.collect_types(ctx, types, self);
+ ty.trace(ctx, tracer, self);
}
}
ItemKind::Function(ref fun) => {
// Just the same way, it has not real meaning for a function to
// be opaque, so we trace across it.
- types.insert(fun.signature());
+ tracer.visit(fun.signature());
}
ItemKind::Var(ref var) => {
- types.insert(var.ty());
+ tracer.visit(var.ty());
}
ItemKind::Module(_) => {
// Module -> children edges are "weak", and we do not want to
// trace them. If we did, then whitelisting wouldn't work as
// expected: everything in every module would end up
// whitelisted.
+ //
+ // TODO: make a new edge kind for module -> children edges and
+ // filter them during whitelisting traversals.
}
}
}
@@ -902,6 +904,9 @@ impl Item {
}
}
+/// A set of items.
+pub type ItemSet = BTreeSet<ItemId>;
+
impl TemplateDeclaration for ItemId {
fn template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
ctx.resolve_item_fallible(*self)
@@ -919,10 +924,11 @@ impl TemplateDeclaration for ItemKind {
fn template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
match *self {
ItemKind::Type(ref ty) => ty.template_params(ctx),
- // TODO FITZGEN: shouldn't functions be able to have free template
- // params?
- ItemKind::Module(_) |
+ // If we start emitting bindings to explicitly instantiated
+ // functions, then we'll need to check ItemKind::Function for
+ // template params.
ItemKind::Function(_) |
+ ItemKind::Module(_) |
ItemKind::Var(_) => None,
}
}
diff --git a/src/ir/mod.rs b/src/ir/mod.rs
index d424fcdf..9fe0beb5 100644
--- a/src/ir/mod.rs
+++ b/src/ir/mod.rs
@@ -14,7 +14,7 @@ pub mod item;
pub mod item_kind;
pub mod layout;
pub mod module;
+pub mod traversal;
pub mod ty;
-pub mod type_collector;
pub mod var;
pub mod objc;
diff --git a/src/ir/traversal.rs b/src/ir/traversal.rs
new file mode 100644
index 00000000..eb4fc686
--- /dev/null
+++ b/src/ir/traversal.rs
@@ -0,0 +1,352 @@
+//! 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` implementor 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: to,
+ kind: kind,
+ }
+ }
+
+ /// Get the item that this edge is pointing to.
+ pub fn to(&self) -> ItemId {
+ self.to
+ }
+
+ /// Get the kind of edge that this is.
+ pub fn kind(&self) -> EdgeKind {
+ self.kind
+ }
+}
+
+impl Into<ItemId> for Edge {
+ fn into(self) -> ItemId {
+ self.to
+ }
+}
+
+/// The kind of edge reference. This is useful when we wish to only consider
+/// certain kinds of edges for a particular traversal.
+#[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 Foo -> T in the following snippet:
+ ///
+ /// ```C++
+ /// template<typename T>
+ /// class Foo {
+ /// int x;
+ /// };
+ /// ```
+ TemplateParameterDefinition,
+}
+
+/// 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, edge: Edge) -> bool;
+}
+
+impl TraversalPredicate for fn(Edge) -> bool {
+ fn should_follow(&self, edge: Edge) -> bool {
+ (*self)(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(_: Edge) -> bool {
+ true
+}
+
+/// A `TraversalPredicate` implementation that never follows any edges, and
+/// therefore traversals using this predicate will only visit the traversal's
+/// roots.
+pub fn no_edges(_: Edge) -> bool {
+ false
+}
+
+/// 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, 'gen> {
+ /// Construct a new instance of this TraversalStorage, for a new traversal.
+ fn new(ctx: &'ctx BindgenContext<'gen>) -> 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, 'gen> TraversalStorage<'ctx, 'gen> for ItemSet {
+ fn new(_: &'ctx BindgenContext<'gen>) -> 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, 'gen>(BTreeMap<ItemId, ItemId>,
+ &'ctx BindgenContext<'gen>)
+ where 'gen: 'ctx;
+
+impl<'ctx, 'gen> TraversalStorage<'ctx, 'gen> for Paths<'ctx, 'gen>
+ where 'gen: 'ctx,
+{
+ fn new(ctx: &'ctx BindgenContext<'gen>) -> 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);
+ }
+}
+
+/// Trace all of the outgoing edges to other items. Implementations should call
+/// `tracer.visit(edge)` 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::whitelisted_items` for more information.
+pub struct ItemTraversal<'ctx, 'gen, Storage, Queue, Predicate>
+ where 'gen: 'ctx,
+ Storage: TraversalStorage<'ctx, 'gen>,
+ Queue: TraversalQueue,
+ Predicate: TraversalPredicate,
+{
+ ctx: &'ctx BindgenContext<'gen>,
+
+ /// 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 determins which edges this traversal will follow.
+ predicate: Predicate,
+
+ /// The item we are currently traversing.
+ currently_traversing: Option<ItemId>,
+}
+
+impl<'ctx, 'gen, Storage, Queue, Predicate> ItemTraversal<'ctx,
+ 'gen,
+ Storage,
+ Queue,
+ Predicate>
+ where 'gen: 'ctx,
+ Storage: TraversalStorage<'ctx, 'gen>,
+ Queue: TraversalQueue,
+ Predicate: TraversalPredicate,
+{
+ /// Begin a new traversal, starting from the given roots.
+ pub fn new<R>(ctx: &'ctx BindgenContext<'gen>,
+ roots: R,
+ predicate: Predicate)
+ -> ItemTraversal<'ctx, 'gen, 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: ctx,
+ seen: seen,
+ queue: queue,
+ predicate: predicate,
+ currently_traversing: None,
+ }
+ }
+}
+
+impl<'ctx, 'gen, Storage, Queue, Predicate> Tracer
+ for ItemTraversal<'ctx, 'gen, Storage, Queue, Predicate>
+ where 'gen: 'ctx,
+ Storage: TraversalStorage<'ctx, 'gen>,
+ Queue: TraversalQueue,
+ Predicate: TraversalPredicate,
+{
+ fn visit_kind(&mut self, item: ItemId, kind: EdgeKind) {
+ let edge = Edge::new(item, kind);
+ if !self.predicate.should_follow(edge) {
+ return;
+ }
+
+ let is_newly_discovered = self.seen
+ .add(self.currently_traversing, item);
+ if is_newly_discovered {
+ self.queue.push(item)
+ }
+ }
+}
+
+impl<'ctx, 'gen, Storage, Queue, Predicate> Iterator
+ for ItemTraversal<'ctx, 'gen, Storage, Queue, Predicate>
+ where 'gen: 'ctx,
+ Storage: TraversalStorage<'ctx, 'gen>,
+ Queue: TraversalQueue,
+ Predicate: TraversalPredicate,
+{
+ type Item = ItemId;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ let id = match self.queue.next() {
+ None => return None,
+ Some(id) => id,
+ };
+
+ 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, 'gen> =
+ ItemTraversal<'ctx,
+ 'gen,
+ Paths<'ctx, 'gen>,
+ VecDeque<ItemId>,
+ fn(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(_: &TraversalPredicate) {}
+ }
+}
diff --git a/src/ir/ty.rs b/src/ir/ty.rs
index a47c1470..ec168f02 100644
--- a/src/ir/ty.rs
+++ b/src/ir/ty.rs
@@ -9,7 +9,7 @@ use super::int::IntKind;
use super::item::Item;
use super::layout::Layout;
use super::objc::ObjCInterface;
-use super::type_collector::{ItemSet, TypeCollector};
+use super::traversal::{Trace, Tracer};
use clang::{self, Cursor};
use parse::{ClangItemParser, ParseError, ParseResult};
use std::mem;
@@ -1026,7 +1026,9 @@ impl Type {
CXType_MemberPointer |
CXType_Pointer => {
let inner = Item::from_ty_or_ref(ty.pointee_type().unwrap(),
- location, None, ctx);
+ location,
+ None,
+ ctx);
TypeKind::Pointer(inner)
}
CXType_BlockPointer => TypeKind::BlockPointer,
@@ -1067,8 +1069,7 @@ impl Type {
}
CXType_Typedef => {
let inner = cursor.typedef_type().expect("Not valid Type?");
- let inner =
- Item::from_ty_or_ref(inner, location, None, ctx);
+ let inner = Item::from_ty_or_ref(inner, location, None, ctx);
TypeKind::Alias(inner)
}
CXType_Enum => {
@@ -1125,40 +1126,37 @@ impl Type {
}
}
-impl TypeCollector for Type {
+impl Trace for Type {
type Extra = Item;
- fn collect_types(&self,
- context: &BindgenContext,
- types: &mut ItemSet,
- item: &Item) {
+ fn trace<T>(&self, context: &BindgenContext, tracer: &mut T, item: &Item)
+ where T: Tracer,
+ {
match *self.kind() {
TypeKind::Pointer(inner) |
TypeKind::Reference(inner) |
TypeKind::Array(inner, _) |
TypeKind::Alias(inner) |
TypeKind::ResolvedTypeRef(inner) => {
- types.insert(inner);
+ tracer.visit(inner);
}
TypeKind::TemplateAlias(inner, ref template_args) |
TypeKind::TemplateInstantiation(inner, ref template_args) => {
- types.insert(inner);
+ tracer.visit(inner);
for &item in template_args {
- types.insert(item);
+ tracer.visit(item);
}
}
- TypeKind::Comp(ref ci) => ci.collect_types(context, types, item),
- TypeKind::Function(ref sig) => {
- sig.collect_types(context, types, item)
- }
+ TypeKind::Comp(ref ci) => ci.trace(context, tracer, item),
+ TypeKind::Function(ref sig) => sig.trace(context, tracer, &()),
TypeKind::Enum(ref en) => {
if let Some(repr) = en.repr() {
- types.insert(repr);
+ tracer.visit(repr);
}
}
TypeKind::UnresolvedTypeRef(_, _, Some(id)) => {
- types.insert(id);
+ tracer.visit(id);
}
TypeKind::ObjCInterface(_) => {
diff --git a/src/ir/type_collector.rs b/src/ir/type_collector.rs
deleted file mode 100644
index 25285b23..00000000
--- a/src/ir/type_collector.rs
+++ /dev/null
@@ -1,22 +0,0 @@
-//! Collecting type items.
-
-use super::context::{BindgenContext, ItemId};
-use std::collections::BTreeSet;
-
-/// A set of items.
-pub type ItemSet = BTreeSet<ItemId>;
-
-/// Collect all the type items referenced by this item.
-pub trait TypeCollector {
- /// If a particular type needs extra information beyond what it has in
- /// `self` and `context` to find its referenced type items, its
- /// implementation can define this associated type, forcing callers to pass
- /// the needed information through.
- type Extra;
-
- /// Add each type item referenced by `self` into the `types` set.
- fn collect_types(&self,
- context: &BindgenContext,
- types: &mut ItemSet,
- extra: &Self::Extra);
-}
generated by cgit v1.2.3 (git 2.46.0) at 2025-07-04 10:38:16 +0000