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?
cjhopman
2014/10/21 18:22:23
Done.
This needed the tuple to convert results to
|
+ 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
cjhopman
2014/10/21 18:22:23
Ehh, I had the same problem. So the key is that th
|
+ |
+ 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 b
|
+ '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 form
cjhopman
2014/10/21 18:22:23
Done.
|
return [dependency_nodes, flat_list] |