Simplify and optimize FindCycles

pylib/gyp/input.py

Index: pylib/gyp/input.py
diff --git a/pylib/gyp/input.py b/pylib/gyp/input.py
index bb853a5408ecf7c93bd38524e4d962438e63a51c..8866298fa2f7381e7ae2cf568a31f16109b8e0c6 100644
--- a/pylib/gyp/input.py
+++ b/pylib/gyp/input.py
@@ -1556,24 +1556,23 @@ class DependencyGraphNode(object):
 
     return list(flat_list)
 
-  def FindCycles(self, path=None):
+  def FindCycles(self):
     """
     Returns a list of cycles in the graph, where each cycle is its own list.
     """
-    if path is None:
-      path = [self]
-
     results = []
-    for node in self.dependents:
-      if node in path:
-        cycle = [node]
-        for part in path:
-          cycle.append(part)
-          if part == node:
-            break
-        results.append(tuple(cycle))
-      else:
-        results.extend(node.FindCycles([node] + path))
+    visited = set()
+
+    def Visit(node, path):
+      for child in node.dependents:
+        if child in path:
+          results.append(tuple([child] + path[:path.index(child) + 1]))

[scottmg, 2014/10/21 02:53:07]

Does this have to make a tuple() out of the list? (The docstring appears to
imply not)

[cjhopman, 2014/10/21 18:22:23]

Done.

This needed the tuple to convert results to a set below. This approach shouldn't
actually discover a particular cycle multiple times, so the uniqification isn't
needed anymore.

+        elif not child in visited:
+          visited.add(child)
+          Visit(child, [child] + path)

[scottmg, 2014/10/21 03:22:42]

I'm probably reading this wrong, but... given A->B->C->D->B

won't path be [D,C,B,A] so we'll print B->D-C->B as the cycle?

[cjhopman, 2014/10/21 18:22:23]

Ehh, I had the same problem. So the key is that this is actually traversing to
dependents, not dependencies. Maybe the name "child" doesn't help the mental
model.

+
+    visited.add(self)
+    Visit(self, [self])
 
     return list(set(results))
 
@@ -1792,12 +1791,16 @@ def BuildDependencyList(targets):
   flat_list = root_node.FlattenToList()
 
   # If there's anything left unvisited, there must be a circular dependency
-  # (cycle).  If you need to figure out what's wrong, look for elements of
-  # targets that are not in flat_list.
+  # (cycle).
   if len(flat_list) != len(targets):
-    raise DependencyGraphNode.CircularException(
-        'Some targets not reachable, cycle in dependency graph detected: ' +
-        ' '.join(set(flat_list) ^ set(targets)))
+    cycles = []
+    for cycle in root_node.FindCycles():
+      paths = []
+      for node in cycle:
+        paths.append(node.ref)
+      cycles.append('Cycle: %s' % ' -> '.join(paths))
+    raise DependencyGraphNode.CircularException, \

[scottmg, 2014/10/21 02:50:23]

Why not CircularException(...)?

[cjhopman, 2014/10/21 18:22:23]

Done.

I just did what was used for raising this below. I've updated there to use (..)
also.

+        'Cycles in dependency graph detected:\n' + '\n'.join(cycles)

[scottmg, 2014/10/21 02:50:23]

Could you add a test for this improved output format to input_test.py?

[cjhopman, 2014/10/21 18:22:23]

Done.

 
   return [dependency_nodes, flat_list]