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
diff --git a/pylib/gyp/input.py b/pylib/gyp/input.py
index bb853a5..4f07eaa 100644
--- a/pylib/gyp/input.py
+++ b/pylib/gyp/input.py
@@ -1556,26 +1556,25 @@
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 @@
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 @@
# 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 cdbf6b2..4234fbb 100755
--- a/pylib/gyp/input_test.py
+++ b/pylib/gyp/input_test.py
@@ -44,16 +44,16 @@
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 @@
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 @@
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 0000000..eef44bc
--- /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 0000000..3bfafb6
--- /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 0000000..fbd7a0d
--- /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 5f66bac..4612c16 100755
--- a/test/errors/gyptest-errors.py
+++ b/test/errors/gyptest-errors.py
@@ -39,6 +39,14 @@
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)
