diff options
| -rw-r--r-- | pylib/gyp/input.py | 69 | ||||
| -rwxr-xr-x | pylib/gyp/input_test.py | 14 | ||||
| -rw-r--r-- | test/errors/dependency_cycle.gyp | 23 | ||||
| -rw-r--r-- | test/errors/file_cycle0.gyp | 17 | ||||
| -rw-r--r-- | test/errors/file_cycle1.gyp | 13 | ||||
| -rwxr-xr-x | test/errors/gyptest-errors.py | 8 |
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) |