Index: pylib/gyp/input.py |
diff --git a/pylib/gyp/input.py b/pylib/gyp/input.py |
index 20178672b23bd83333466c2e26afdf69b63eea85..42d38108e6b6a979a71314d527850186dd440576 100644 |
--- a/pylib/gyp/input.py |
+++ b/pylib/gyp/input.py |
@@ -58,6 +58,10 @@ path_sections = set() |
per_process_data = {} |
per_process_aux_data = {} |
+def OrderDeterministically(l, **kwargs): |
+ """ Sorts l so that it is ordered deterministically. """ |
+ return sorted(l, **kwargs) |
mithro-old
2015/12/10 03:15:28
DRY
Zachary Forman
2015/12/30 02:18:43
Done.
|
+ |
def IsPathSection(section): |
# If section ends in one of the '=+?!' characters, it's applied to a section |
# without the trailing characters. '/' is notably absent from this list, |
@@ -1539,11 +1543,16 @@ class DependencyGraphNode(object): |
# dependents. |
flat_list = OrderedSet() |
+ def ExtractNodeRef(node): |
+ """Extracts the object that the node represents from the given node.""" |
+ return node.ref |
+ |
# in_degree_zeros is the list of DependencyGraphNodes that have no |
# dependencies not in flat_list. Initially, it is a copy of the children |
# of this node, because when the graph was built, nodes with no |
# dependencies were made implicit dependents of the root node. |
- in_degree_zeros = set(self.dependents[:]) |
+ in_degree_zeros = OrderDeterministically(self.dependents[:], |
+ key=ExtractNodeRef) |
while in_degree_zeros: |
# Nodes in in_degree_zeros have no dependencies not in flat_list, so they |
@@ -1555,12 +1564,15 @@ class DependencyGraphNode(object): |
# Look at dependents of the node just added to flat_list. Some of them |
# may now belong in in_degree_zeros. |
- for node_dependent in node.dependents: |
+ for node_dependent in OrderDeterministically(node.dependents, |
+ key=ExtractNodeRef): |
is_in_degree_zero = True |
# TODO: We want to check through the |
# node_dependent.dependencies list but if it's long and we |
# always start at the beginning, then we get O(n^2) behaviour. |
- for node_dependent_dependency in node_dependent.dependencies: |
+ for node_dependent_dependency in ( |
+ OrderDeterministically(node_dependent.dependencies, |
+ key=ExtractNodeRef)): |
if not node_dependent_dependency.ref in flat_list: |
# The dependent one or more dependencies not in flat_list. There |
# will be more chances to add it to flat_list when examining |
@@ -1573,7 +1585,7 @@ class DependencyGraphNode(object): |
# All of the dependent's dependencies are already in flat_list. Add |
# it to in_degree_zeros where it will be processed in a future |
# iteration of the outer loop. |
- in_degree_zeros.add(node_dependent) |
+ in_degree_zeros += [node_dependent] |
return list(flat_list) |