Refactor IR graph traversal infrastructure

This makes the IR traversal infrastructure generic. It makes it so we can use
the same traversal code for whitelisting traversals and asserting no dangling
item references. Therefore the queue of items to visit is generic (whitelisting
uses DFS, while asserting against dangling uses BFS), the storage for the seen
set (whitelisting uses a simple set, asserting against dangling uses a map from
item to the item from which it was discovered).

It also introduces the concept of different kinds of edges in the IR graph, and
the ability to choose which edges to follow. This means we can simplify
non-transitive whitelisting to a simple function that always returns "no do not
follow this edge". It plays an important part for future analysis of which
template declaration type parameters are used or not.

6 files changed, 390 insertions, 190 deletions

diff --git a/src/ir/comp.rs b/src/ir/comp.rs
index bcc386ad..ecc0442b 100644
--- a/src/ir/comp.rs
+++ b/src/ir/comp.rs
@@ -3,8 +3,9 @@
 use super::annotations::Annotations;
 use super::context::{BindgenContext, ItemId};
 use super::derive::{CanDeriveCopy, CanDeriveDebug, CanDeriveDefault};
-use super::item::{Item, ItemSet};
+use super::item::Item;
 use super::layout::Layout;
+use super::traversal::{EdgeKind, Trace, Tracer};
 use super::ty::{TemplateDeclaration, Type};
 use super::traversal::Trace;
 use clang;
@@ -1078,41 +1079,55 @@ impl<'a> CanDeriveCopy<'a> for CompInfo {
 impl Trace for CompInfo {
     type Extra = Item;
 
-    fn trace(&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 7ce7f775..63d451a8 100644
--- a/src/ir/context.rs
+++ b/src/ir/context.rs
@@ -5,7 +5,7 @@ use super::int::IntKind;
 use super::item::{Item, ItemSet, ItemCanonicalPath};
 use super::item_kind::ItemKind;
 use super::module::{Module, ModuleKind};
-use super::traversal::{ItemTraversal, Trace};
+use super::traversal::{self, Edge, ItemTraversal};
 use super::ty::{FloatKind, TemplateDeclaration, Type, TypeKind};
 use BindgenOptions;
 use cexpr;
@@ -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,10 @@ 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 +542,12 @@ 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 +1195,7 @@ impl<'ctx> BindgenContext<'ctx> {
     ///
     /// If no items are explicitly whitelisted, then all items are considered
     /// whitelisted.
-    pub fn whitelisted_items<'me>(&'me self)
-                                  -> ItemTraversal<'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,7 +1260,19 @@ impl<'ctx> BindgenContext<'ctx> {
             })
             .map(|(&id, _)| id);
 
-        ItemTraversal::new(self, roots)
+        // The reversal preserves the expected ordering of traversal, resulting
+        // in more stable-ish bindgen-generated names for anonymous types (like
+        // unions).
+        let mut roots: Vec<_> = roots.collect();
+        roots.reverse();
+
+        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
@@ -1353,75 +1357,3 @@ impl TemplateDeclaration for PartialType {
         }
     }
 }
-
-/// 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.trace(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 7beb35a4..cd504b9c 100644
--- a/src/ir/function.rs
+++ b/src/ir/function.rs
@@ -1,7 +1,8 @@
 //! Intermediate representation for C/C++ functions and methods.
 
 use super::context::{BindgenContext, ItemId};
-use super::item::{Item, ItemSet};
+use super::item::Item;
+use super::traversal::{Trace, Tracer};
 use super::ty::TypeKind;
 use super::traversal::Trace;
 use clang;
@@ -317,16 +318,18 @@ impl ClangSubItemParser for Function {
 }
 
 impl Trace for FunctionSig {
-    type Extra = Item;
+    type Extra = ();
 
-    fn trace(&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 04831f75..f168579e 100644
--- a/src/ir/item.rs
+++ b/src/ir/item.rs
@@ -6,6 +6,7 @@ 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::traversal::Trace;
 use clang;
@@ -170,22 +171,20 @@ impl ItemAncestors for Item {
 impl Trace for ItemId {
     type Extra = ();
 
-    fn trace(&self,
-                     ctx: &BindgenContext,
-                     types: &mut ItemSet,
-                     extra: &()) {
-        ctx.resolve_item(*self).trace(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 Trace for Item {
     type Extra = ();
 
-    fn trace(&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;
         }
 
@@ -196,22 +195,25 @@ impl Trace for Item {
                 // opaque.
                 if ty.should_be_traced_unconditionally() ||
                    !self.is_opaque(ctx) {
-                    ty.trace(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.
             }
         }
     }
@@ -923,10 +925,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/traversal.rs b/src/ir/traversal.rs
index 4965b6cb..4e78ce2a 100644
--- a/src/ir/traversal.rs
+++ b/src/ir/traversal.rs
@@ -1,92 +1,339 @@
 //! Traversal of the graph of IR items and types.
 
+use std::collections::{BTreeMap, VecDeque};
 use super::context::{BindgenContext, ItemId};
 use super::item::ItemSet;
 
-/// Collect all the type items referenced by this item.
+/// 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 type items, its
-    /// implementation can define this associated type, forcing callers to pass
-    /// the needed information through.
+    /// `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;
 
-    /// Add each type item referenced by `self` into the `types` set.
-    fn trace(&self,
-                     context: &BindgenContext,
-                     types: &mut ItemSet,
-                     extra: &Self::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>
+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 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 items we have seen thus far in this traversal.
+    seen: Storage,
 
-    /// 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>,
+    /// 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> ItemTraversal<'ctx, 'gen>
+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)
-                  -> ItemTraversal<'ctx, 'gen>
+                  roots: R,
+                  predicate: Predicate)
+                  -> ItemTraversal<'ctx, 'gen, Storage, Queue, Predicate>
         where R: IntoIterator<Item = ItemId>,
     {
-        // Construct the ItemSet first. Because its underlying storage is a
-        // BTreeSet, its iteration over its entries is ordered, and the roots
-        // end up ordered as well. This contributes enables stable,
-        // deterministic generated names in the bindings.
-        let seen: ItemSet = roots.into_iter().collect();
-        let roots: Vec<_> = seen.iter().cloned().collect();
+        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,
-            to_iterate: roots,
+            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> Iterator for ItemTraversal<'ctx, 'gen>
+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.to_iterate.pop() {
+        let id = match self.queue.next() {
             None => return None,
             Some(id) => id,
         };
 
-        debug_assert!(self.seen.contains(&id));
-        debug_assert!(self.ctx.resolve_item_fallible(id).is_some());
+        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");
 
-        if self.ctx.options().whitelist_recursively {
-            let mut sub_types = ItemSet::new();
-            id.trace(self.ctx, &mut sub_types, &());
-
-            for id in sub_types {
-                if self.seen.insert(id) {
-                    self.to_iterate.push(id);
-                }
-            }
-        }
+        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 030b012e..236eae8b 100644
--- a/src/ir/ty.rs
+++ b/src/ir/ty.rs
@@ -6,10 +6,10 @@ use super::derive::{CanDeriveCopy, CanDeriveDebug, CanDeriveDefault};
 use super::enum_ty::Enum;
 use super::function::FunctionSig;
 use super::int::IntKind;
-use super::item::{Item, ItemSet};
+use super::item::Item;
 use super::layout::Layout;
 use super::objc::ObjCInterface;
-use super::traversal::Trace;
+use super::traversal::{Trace, Tracer};
 use clang::{self, Cursor};
 use parse::{ClangItemParser, ParseError, ParseResult};
 use std::mem;
@@ -1128,37 +1128,37 @@ impl Type {
 impl Trace for Type {
     type Extra = Item;
 
-    fn trace(&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.trace(context, types, item),
-            TypeKind::Function(ref sig) => {
-                sig.trace(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(_) => {