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
 from compiler.ast import Stmt
 import compiler
 import gyp.common
 import gyp.simple_copy
 import multiprocessing
 import optparse
 import os.path
 import re
 import shlex
 import signal
 import subprocess
 import sys
 import threading
 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.
 linkable_types = [
   'executable',
   'shared_library',
   'loadable_module',
   'mac_kernel_extension',
 ]
 
@@ skipping 1494 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[:],

[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
       # 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]