GYP: Make GYP build deterministic

pylib/gyp/input.py

 # Copyright (c) 2012 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.
 
 from compiler.ast import Const
 from compiler.ast import Dict
 from compiler.ast import Discard
 from compiler.ast import List
 from compiler.ast import Module
 from compiler.ast import Node
@@ skipping 40 matching lines @@
   'outputs',
   'sources',
 ]
 path_sections = set()
 
 # These per-process dictionaries are used to cache build file data when loading
 # in parallel mode.
 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,
   # because there's no way for a regular expression to be treated as a path.
   while section and section[-1:] in '=+?!':
     section = section[:-1]
 
   if section in path_sections:
     return True
 
@@ skipping 1461 matching lines @@
   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
     # appear in flat_list after all of its dependencies, and before all of its
     # 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
       # can be appended to flat_list.  Take these nodes out of in_degree_zeros
       # as work progresses, so that the next node to process from the list can
       # always be accessed at a consistent position.
       node = in_degree_zeros.pop()
       flat_list.add(node.ref)
 
       # 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
             # it again as a dependent of those other dependencies, provided
             # that there are no cycles.
             is_in_degree_zero = False
             break
 
         if is_in_degree_zero:
           # 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)
 
   def FindCycles(self):
     """
     Returns a list of cycles in the graph, where each cycle is its own list.
     """
     results = []
     visited = set()
 
@@ skipping 1298 matching lines @@
     ValidateRunAsInTarget(target, target_dict, build_file)
     ValidateActionsInTarget(target, target_dict, build_file)
 
   # Generators might not expect ints.  Turn them into strs.
   TurnIntIntoStrInDict(data)
 
   # TODO(mark): Return |data| for now because the generator needs a list of
   # build files that came in.  In the future, maybe it should just accept
   # a list, and not the whole data dict.
   return [flat_list, targets, data]