GYP: Make GYP build deterministic

pylib/gyp/input.py

Index: pylib/gyp/input.py
diff --git a/pylib/gyp/input.py b/pylib/gyp/input.py
index 20178672b23bd83333466c2e26afdf69b63eea85..6a06bba0ffdf1fb4794fdc83884a572d2bda0146 100644
--- a/pylib/gyp/input.py
+++ b/pylib/gyp/input.py
@@ -25,6 +25,8 @@ import time
 import traceback
 from gyp.common import GypError
 from gyp.common import OrderedSet
+from gyp.common import OrderDeterministically
+
 
 
 # A list of types that are treated as linkable.
@@ -1539,11 +1541,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[:],

[Nico, 2015/12/10 20:30:24]

should this just be an gyp.common.OrderedSet?

[Zachary Forman, 2015/12/30 02:18:43]

Nope, that fails the test; I believe because the order of OrderedSet would be
the non-deterministic ordering of the dependents.

+                                             key=ExtractNodeRef)
 
     while in_degree_zeros:
       # Nodes in in_degree_zeros have no dependencies not in flat_list, so they
@@ -1555,12 +1562,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 +1583,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)