rollup merge of #19898: Aatch/issue-19684

[rust.git] / src / librustc / middle / graph.rs

diff --git a/src/librustc/middle/graph.rs b/src/librustc/middle/graph.rs
index e73fcd93e0504cb1892d724b02ec6562acc27d4b..06e6ef30f74dacadc64ff42e6d1f5e6a3443498d 100644 (file)
--- a/src/librustc/middle/graph.rs
+++ b/src/librustc/middle/graph.rs
@@ -34,6 +34,7 @@
 
 use std::fmt::{Formatter, Error, Show};
 use std::uint;
+use std::collections::BitvSet;
 
 pub struct Graph<N,E> {
     nodes: Vec<Node<N>> ,
@@ -288,6 +289,40 @@ pub fn iterate_until_fixed_point<'a, F>(&'a self, mut op: F) where
             }
         }
     }
+
+    pub fn depth_traverse<'a>(&'a self, start: NodeIndex) -> DepthFirstTraversal<'a, N, E>  {
+        DepthFirstTraversal {
+            graph: self,
+            stack: vec![start],
+            visited: BitvSet::new()
+        }
+    }
+}
+
+pub struct DepthFirstTraversal<'g, N:'g, E:'g> {
+    graph: &'g Graph<N, E>,
+    stack: Vec<NodeIndex>,
+    visited: BitvSet
+}
+
+impl<'g, N, E> Iterator<&'g N> for DepthFirstTraversal<'g, N, E> {
+    fn next(&mut self) -> Option<&'g N> {
+        while let Some(idx) = self.stack.pop() {
+            if !self.visited.insert(idx.node_id()) {
+                continue;
+            }
+            self.graph.each_outgoing_edge(idx, |_, e| -> bool {
+                if !self.visited.contains(&e.target().node_id()) {
+                    self.stack.push(e.target());
+                }
+                true
+            });
+
+            return Some(self.graph.node_data(idx));
+        }
+
+        return None;
+    }
 }
 
 pub fn each_edge_index<F>(max_edge_index: EdgeIndex, mut f: F) where