Simplify and optimize FindCycles

Finding cycles in a directed graph only requires a simple depth first
traversal, it does not require checking every path in the graph.

This is now fast enough to actually identify and print cycles between
targets.

Changes the error message slightly for file and target cycles,
and adds tests for both those cases.

Patch from cjhopman@chromium.org.

R=scottmg@chromium.org

Review URL: https://codereview.chromium.org/664253005

git-svn-id: http://gyp.googlecode.com/svn/trunk@1992 78cadc50-ecff-11dd-a971-7dbc132099af

6 files changed, 106 insertions, 38 deletions

diff --git a/pylib/gyp/input.py b/pylib/gyp/input.py
index bb853a54..4f07eaaa 100644
--- a/pylib/gyp/input.py
+++ b/pylib/gyp/input.py
@@ -1556,26 +1556,25 @@ 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()
 
-    return list(set(results))
+    def Visit(node, path):
+      for child in node.dependents:
+        if child in path:
+          results.append([child] + path[:path.index(child) + 1])
+        elif not child in visited:
+          visited.add(child)
+          Visit(child, [child] + path)
+
+    visited.add(self)
+    Visit(self, [self])
+
+    return results
 
   def DirectDependencies(self, dependencies=None):
     """Returns a list of just direct dependencies."""
@@ -1792,12 +1791,22 @@ 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):
+    if not root_node.dependents:
+      # If all targets have dependencies, add the first target as a dependent
+      # of root_node so that the cycle can be discovered from root_node.
+      target = targets.keys()[0]
+      target_node = dependency_nodes[target]
+      target_node.dependencies.append(root_node)
+      root_node.dependents.append(target_node)
+
+    cycles = []
+    for cycle in root_node.FindCycles():
+      paths = [node.ref for node in cycle]
+      cycles.append('Cycle: %s' % ' -> '.join(paths))
     raise DependencyGraphNode.CircularException(
-        'Some targets not reachable, cycle in dependency graph detected: ' +
-        ' '.join(set(flat_list) ^ set(targets)))
+        'Cycles in dependency graph detected:\n' + '\n'.join(cycles))
 
   return [dependency_nodes, flat_list]
 
@@ -1847,20 +1856,18 @@ def VerifyNoGYPFileCircularDependencies(targets):
   # If there's anything left unvisited, there must be a circular dependency
   # (cycle).
   if len(flat_list) != len(dependency_nodes):
-    bad_files = []
-    for file in dependency_nodes.iterkeys():
-      if not file in flat_list:
-        bad_files.append(file)
-    common_path_prefix = os.path.commonprefix(dependency_nodes)
+    if not root_node.dependents:
+      # If all files have dependencies, add the first file as a dependent
+      # of root_node so that the cycle can be discovered from root_node.
+      file_node = dependency_nodes.values()[0]
+      file_node.dependencies.append(root_node)
+      root_node.dependents.append(file_node)
     cycles = []
     for cycle in root_node.FindCycles():
-      simplified_paths = []
-      for node in cycle:
-        assert(node.ref.startswith(common_path_prefix))
-        simplified_paths.append(node.ref[len(common_path_prefix):])
-      cycles.append('Cycle: %s' % ' -> '.join(simplified_paths))
-    raise DependencyGraphNode.CircularException, \
-        'Cycles in .gyp file dependency graph detected:\n' + '\n'.join(cycles)
+      paths = [node.ref for node in cycle]
+      cycles.append('Cycle: %s' % ' -> '.join(paths))
+    raise DependencyGraphNode.CircularException(
+        'Cycles in .gyp file dependency graph detected:\n' + '\n'.join(cycles))
 
 
 def DoDependentSettings(key, flat_list, targets, dependency_nodes):
diff --git a/pylib/gyp/input_test.py b/pylib/gyp/input_test.py
index cdbf6b2f..4234fbb8 100755
--- a/pylib/gyp/input_test.py
+++ b/pylib/gyp/input_test.py
@@ -44,16 +44,16 @@ class TestFindCycles(unittest.TestCase):
   def test_cycle_self_reference(self):
     self._create_dependency(self.nodes['a'], self.nodes['a'])
 
-    self.assertEquals([(self.nodes['a'], self.nodes['a'])],
+    self.assertEquals([[self.nodes['a'], self.nodes['a']]],
                       self.nodes['a'].FindCycles())
 
   def test_cycle_two_nodes(self):
     self._create_dependency(self.nodes['a'], self.nodes['b'])
     self._create_dependency(self.nodes['b'], self.nodes['a'])
 
-    self.assertEquals([(self.nodes['a'], self.nodes['b'], self.nodes['a'])],
+    self.assertEquals([[self.nodes['a'], self.nodes['b'], self.nodes['a']]],
                       self.nodes['a'].FindCycles())
-    self.assertEquals([(self.nodes['b'], self.nodes['a'], self.nodes['b'])],
+    self.assertEquals([[self.nodes['b'], self.nodes['a'], self.nodes['b']]],
                       self.nodes['b'].FindCycles())
 
   def test_two_cycles(self):
@@ -65,9 +65,9 @@ class TestFindCycles(unittest.TestCase):
 
     cycles = self.nodes['a'].FindCycles()
     self.assertTrue(
-       (self.nodes['a'], self.nodes['b'], self.nodes['a']) in cycles)
+       [self.nodes['a'], self.nodes['b'], self.nodes['a']] in cycles)
     self.assertTrue(
-       (self.nodes['b'], self.nodes['c'], self.nodes['b']) in cycles)
+       [self.nodes['b'], self.nodes['c'], self.nodes['b']] in cycles)
     self.assertEquals(2, len(cycles))
 
   def test_big_cycle(self):
@@ -77,12 +77,12 @@ class TestFindCycles(unittest.TestCase):
     self._create_dependency(self.nodes['d'], self.nodes['e'])
     self._create_dependency(self.nodes['e'], self.nodes['a'])
 
-    self.assertEquals([(self.nodes['a'],
+    self.assertEquals([[self.nodes['a'],
                         self.nodes['b'],
                         self.nodes['c'],
                         self.nodes['d'],
                         self.nodes['e'],
-                        self.nodes['a'])],
+                        self.nodes['a']]],
                       self.nodes['a'].FindCycles())
 
 
diff --git a/test/errors/dependency_cycle.gyp b/test/errors/dependency_cycle.gyp
new file mode 100644
index 00000000..eef44bc9
--- /dev/null
+++ b/test/errors/dependency_cycle.gyp
@@ -0,0 +1,23 @@
+# Copyright 2014 Google Inc. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+{
+  'targets': [
+    {
+      'target_name': 'target0',
+      'type': 'none',
+      'dependencies': [ 'target1' ],
+    },
+    {
+      'target_name': 'target1',
+      'type': 'none',
+      'dependencies': [ 'target2' ],
+    },
+    {
+      'target_name': 'target2',
+      'type': 'none',
+      'dependencies': [ 'target0' ],
+    },
+  ],
+}
diff --git a/test/errors/file_cycle0.gyp b/test/errors/file_cycle0.gyp
new file mode 100644
index 00000000..3bfafb6c
--- /dev/null
+++ b/test/errors/file_cycle0.gyp
@@ -0,0 +1,17 @@
+# Copyright 2014 Google Inc. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+{
+  'targets': [
+    {
+      'target_name': 'top',
+      'type': 'none',
+      'dependencies': [ 'file_cycle1.gyp:middle' ],
+    },
+    {
+      'target_name': 'bottom',
+      'type': 'none',
+    },
+  ],
+}
diff --git a/test/errors/file_cycle1.gyp b/test/errors/file_cycle1.gyp
new file mode 100644
index 00000000..fbd7a0d1
--- /dev/null
+++ b/test/errors/file_cycle1.gyp
@@ -0,0 +1,13 @@
+# Copyright 2014 Google Inc. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+{
+  'targets': [
+    {
+      'target_name': 'middle',
+      'type': 'none',
+      'dependencies': [ 'file_cycle0.gyp:bottom' ],
+    },
+  ],
+}
diff --git a/test/errors/gyptest-errors.py b/test/errors/gyptest-errors.py
index 5f66bac0..4612c16b 100755
--- a/test/errors/gyptest-errors.py
+++ b/test/errors/gyptest-errors.py
@@ -39,6 +39,14 @@ stderr = ("gyp: Key 'targets' repeated at level 1 with key path '' while "
 test.run_gyp('duplicate_node.gyp', '--check', status=1, stderr=stderr,
              match=TestCmd.match_re_dotall)
 
+stderr = (".*target0.*target1.*target2.*target0.*")
+test.run_gyp('dependency_cycle.gyp', status=1, stderr=stderr,
+             match=TestCmd.match_re_dotall)
+
+stderr = (".*file_cycle0.*file_cycle1.*file_cycle0.*")
+test.run_gyp('file_cycle0.gyp', status=1, stderr=stderr,
+             match=TestCmd.match_re_dotall)
+
 stderr = 'gyp: Duplicate basenames in sources section, see list above\n'
 test.run_gyp('duplicate_basenames.gyp', status=1, stderr=stderr)