Bug 1383880: add Graph.visit_preorder; r=ahal
☠☠ backed out by 1d02aa80f2f8 ☠ ☠
authorDustin J. Mitchell <dustin@mozilla.com>
Sun, 20 Aug 2017 16:29:12 +0000
changeset 378299 91f116ce6c2a84761f8c40e48f0abd7bee73f66f
parent 378298 045498bc36c4bab49853ca54d2ca3f26fc50f91e
child 378300 e62c90e3c1e8957186a02cc8e65c2f2321fcea6c
push id32428
push userarchaeopteryx@coole-files.de
push dateSat, 02 Sep 2017 08:52:28 +0000
treeherdermozilla-central@b01a7e57425b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersahal
bugs1383880
milestone57.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1383880: add Graph.visit_preorder; r=ahal MozReview-Commit-ID: BWGqLUuWlN9
taskcluster/taskgraph/graph.py
taskcluster/taskgraph/test/test_graph.py
--- a/taskcluster/taskgraph/graph.py
+++ b/taskcluster/taskgraph/graph.py
@@ -73,39 +73,49 @@ class Graph(object):
             add_edges = set((left, right, name)
                             for (left, right, name) in self.edges
                             if (right if reverse else left) in nodes)
             add_nodes = set((left if reverse else right) for (left, right, _) in add_edges)
             new_nodes = nodes | add_nodes
             new_edges = edges | add_edges
         return Graph(new_nodes, new_edges)
 
-    def visit_postorder(self):
-        """
-        Generate a sequence of nodes in postorder, such that every node is
-        visited *after* any nodes it links to.
-
-        Behavior is undefined (read: it will hang) if the graph contains a
-        cycle.
-        """
+    def _visit(self, reverse):
         queue = collections.deque(sorted(self.nodes))
-        links_by_node = self.links_dict()
+        links_by_node = self.reverse_links_dict() if reverse else self.links_dict()
         seen = set()
         while queue:
             node = queue.popleft()
             if node in seen:
                 continue
             links = links_by_node[node]
             if all((n in seen) for n in links):
                 seen.add(node)
                 yield node
             else:
                 queue.extend(n for n in links if n not in seen)
                 queue.append(node)
 
+    def visit_postorder(self):
+        """
+        Generate a sequence of nodes in postorder, such that every node is
+        visited *after* any nodes it links to.
+
+        Behavior is undefined (read: it will hang) if the graph contains a
+        cycle.
+        """
+        return self._visit(False)
+
+    def visit_preorder(self):
+        """
+        Like visit_postorder, but in reverse: evrey node is visited *before*
+        any nodes it links to.
+        """
+        return self._visit(True)
+
     def links_dict(self):
         """
         Return a dictionary mapping each node to a set of the nodes it links to
         (omitting edge names)
         """
         links = collections.defaultdict(set)
         for left, right, _ in self.edges:
             links[left].add(right)
--- a/taskcluster/taskgraph/test/test_graph.py
+++ b/taskcluster/taskgraph/test/test_graph.py
@@ -124,16 +124,41 @@ class TestGraph(unittest.TestCase):
     def test_visit_postorder_multi_edges(self):
         "postorder visit of a graph with duplicate edges satisfies invariant"
         self.assert_postorder(self.multi_edges.visit_postorder(), self.multi_edges.nodes)
 
     def test_visit_postorder_disjoint(self):
         "postorder visit of a disjoint graph satisfies invariant"
         self.assert_postorder(self.disjoint.visit_postorder(), self.disjoint.nodes)
 
+    def assert_preorder(self, seq, all_nodes):
+        seen = set()
+        for e in seq:
+            for l, r, n in self.tree.edges:
+                if r == e:
+                    self.failUnless(l in seen)
+            seen.add(e)
+        self.assertEqual(seen, all_nodes)
+
+    def test_visit_preorder_tree(self):
+        "preorder visit of a tree satisfies invariant"
+        self.assert_preorder(self.tree.visit_preorder(), self.tree.nodes)
+
+    def test_visit_preorder_diamonds(self):
+        "preorder visit of a graph full of diamonds satisfies invariant"
+        self.assert_preorder(self.diamonds.visit_preorder(), self.diamonds.nodes)
+
+    def test_visit_preorder_multi_edges(self):
+        "preorder visit of a graph with duplicate edges satisfies invariant"
+        self.assert_preorder(self.multi_edges.visit_preorder(), self.multi_edges.nodes)
+
+    def test_visit_preorder_disjoint(self):
+        "preorder visit of a disjoint graph satisfies invariant"
+        self.assert_preorder(self.disjoint.visit_preorder(), self.disjoint.nodes)
+
     def test_links_dict(self):
         "link dict for a graph with multiple edges is correct"
         self.assertEqual(self.multi_edges.links_dict(), {
             '2': set(['1']),
             '3': set(['1', '2']),
             '4': set(['3']),
         })