GTTF: Print much better error message for dependency cycles.
Example:
gyp: Cycles in .gyp file dependency graph detected:
Cycle: build/linux/system.gyp -> third_party/zlib/zlib.gyp -> base/base.gyp -> tools/xdisplaycheck/xdisplaycheck.gyp -> build/linux/system.gyp
Cycle: build/linux/system.gyp -> third_party/zlib/zlib.gyp -> base/base.gyp -> build/linux/system.gyp
Cycle: base/base.gyp -> tools/xdisplaycheck/xdisplaycheck.gyp -> build/linux/system.gyp -> base/base.gyp
Cycle: build/linux/system.gyp -> base/base.gyp -> tools/xdisplaycheck/xdisplaycheck.gyp -> build/linux/system.gyp
Cycle: base/base.gyp -> build/linux/system.gyp -> base/base.gyp
Cycle: base/base.gyp -> tools/xdisplaycheck/xdisplaycheck.gyp -> build/linux/system.gyp -> third_party/zlib/zlib.gyp -> base/base.gyp
Cycle: base/base.gyp -> build/linux/system.gyp -> third_party/zlib/zlib.gyp -> base/base.gyp
Cycle: build/linux/system.gyp -> base/base.gyp -> build/linux/system.gyp
BUG=chromium:35878
Patch by Paweł Hajdan Jr. <phajdan.jr@chromium.org>
Take 2, originally landed in r1695 and backed out in r1696.
Review URL: https://codereview.chromium.org/23018008/
git-svn-id: http://gyp.googlecode.com/svn/trunk@1700 78cadc50-ecff-11dd-a971-7dbc132099af
diff --git a/pylib/gyp/input.py b/pylib/gyp/input.py
index 0d9beb0..0c303d2 100644
--- a/pylib/gyp/input.py
+++ b/pylib/gyp/input.py
@@ -1443,6 +1443,9 @@
self.dependencies = []
self.dependents = []
+ def __repr__(self):
+ return '<DependencyGraphNode: %r>' % self.ref
+
def FlattenToList(self):
# flat_list is the sorted list of dependencies - actually, the list items
# are the "ref" attributes of DependencyGraphNodes. Every target will
@@ -1485,6 +1488,27 @@
return flat_list
+ def FindCycles(self, path=None):
+ """
+ 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))
+
+ return list(set(results))
+
def DirectDependencies(self, dependencies=None):
"""Returns a list of just direct dependencies."""
if dependencies == None:
@@ -1717,10 +1741,16 @@
for file in dependency_nodes.iterkeys():
if not file in flat_list:
bad_files.append(file)
+ common_path_prefix = os.path.commonprefix(dependency_nodes)
+ 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, \
- 'Some files not reachable, cycle in .gyp file dependency graph ' + \
- 'detected involving some or all of: ' + \
- ' '.join(bad_files)
+ '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
new file mode 100755
index 0000000..cdbf6b2
--- /dev/null
+++ b/pylib/gyp/input_test.py
@@ -0,0 +1,90 @@
+#!/usr/bin/env python
+
+# Copyright 2013 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.
+
+"""Unit tests for the input.py file."""
+
+import gyp.input
+import unittest
+import sys
+
+
+class TestFindCycles(unittest.TestCase):
+ def setUp(self):
+ self.nodes = {}
+ for x in ('a', 'b', 'c', 'd', 'e'):
+ self.nodes[x] = gyp.input.DependencyGraphNode(x)
+
+ def _create_dependency(self, dependent, dependency):
+ dependent.dependencies.append(dependency)
+ dependency.dependents.append(dependent)
+
+ def test_no_cycle_empty_graph(self):
+ for label, node in self.nodes.iteritems():
+ self.assertEquals([], node.FindCycles())
+
+ def test_no_cycle_line(self):
+ self._create_dependency(self.nodes['a'], self.nodes['b'])
+ self._create_dependency(self.nodes['b'], self.nodes['c'])
+ self._create_dependency(self.nodes['c'], self.nodes['d'])
+
+ for label, node in self.nodes.iteritems():
+ self.assertEquals([], node.FindCycles())
+
+ def test_no_cycle_dag(self):
+ self._create_dependency(self.nodes['a'], self.nodes['b'])
+ self._create_dependency(self.nodes['a'], self.nodes['c'])
+ self._create_dependency(self.nodes['b'], self.nodes['c'])
+
+ for label, node in self.nodes.iteritems():
+ self.assertEquals([], node.FindCycles())
+
+ def test_cycle_self_reference(self):
+ self._create_dependency(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.nodes['a'].FindCycles())
+ self.assertEquals([(self.nodes['b'], self.nodes['a'], self.nodes['b'])],
+ self.nodes['b'].FindCycles())
+
+ def test_two_cycles(self):
+ self._create_dependency(self.nodes['a'], self.nodes['b'])
+ self._create_dependency(self.nodes['b'], self.nodes['a'])
+
+ self._create_dependency(self.nodes['b'], self.nodes['c'])
+ self._create_dependency(self.nodes['c'], self.nodes['b'])
+
+ cycles = self.nodes['a'].FindCycles()
+ self.assertTrue(
+ (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.assertEquals(2, len(cycles))
+
+ def test_big_cycle(self):
+ self._create_dependency(self.nodes['a'], self.nodes['b'])
+ self._create_dependency(self.nodes['b'], self.nodes['c'])
+ self._create_dependency(self.nodes['c'], self.nodes['d'])
+ self._create_dependency(self.nodes['d'], self.nodes['e'])
+ self._create_dependency(self.nodes['e'], 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'].FindCycles())
+
+
+if __name__ == '__main__':
+ unittest.main()
diff --git a/test/small/gyptest-small.py b/test/small/gyptest-small.py
index 0e33f28..a8d61fb 100755
--- a/test/small/gyptest-small.py
+++ b/test/small/gyptest-small.py
@@ -30,6 +30,7 @@
'pylib/gyp/generator/ninja_test.py',
'pylib/gyp/generator/xcode_test.py',
'pylib/gyp/common_test.py',
+ 'pylib/gyp/input_test.py',
]
# Collect all the suites from the above files.
