Add the --random option.

4 files changed, 60 insertions, 15 deletions

diff --git a/src/engine/SCons/Node/FS.py b/src/engine/SCons/Node/FS.py
index 08a47a7..2057797 100644
--- a/src/engine/SCons/Node/FS.py
+++ b/src/engine/SCons/Node/FS.py
@@ -727,7 +727,6 @@ class Dir(Entry):
             return self.entries['..'].root()
 
     def all_children(self, scan):
-        #XXX --random:  randomize "dependencies?"
         keys = filter(lambda k: k != '.' and k != '..', self.entries.keys())
         kids = map(lambda x, s=self: s.entries[x], keys)
         def c(one, two):
diff --git a/src/engine/SCons/Script/__init__.py b/src/engine/SCons/Script/__init__.py
index eed045d..41b95dc 100644
--- a/src/engine/SCons/Script/__init__.py
+++ b/src/engine/SCons/Script/__init__.py
@@ -41,6 +41,7 @@ start_time = time.time()
 
 import os
 import os.path
+import random
 import string
 import sys
 import traceback
@@ -544,6 +545,9 @@ class OptParser(OptionParser):
                         default=0,
                         help="Don't print SCons progress messages.")
 
+        self.add_option('--random', dest="random", action="store_true",
+                        default=0, help="Build dependencies in random order.")
+
         self.add_option('-s', '--silent', '--quiet', action="store_true",
                         default=0, help="Don't print commands.")
 
@@ -607,10 +611,6 @@ class OptParser(OptionParser):
                         callback=opt_not_yet,
                         # help="Clear default environments and variables."
                         help=SUPPRESS_HELP)
-        self.add_option('--random', action="callback",
-                        callback=opt_not_yet,
-                        # help="Build dependencies in random order."
-                        help=SUPPRESS_HELP)
         self.add_option('-w', '--print-directory', action="callback",
                         callback=opt_not_yet,
                         # help="Print the current directory."
@@ -868,8 +868,23 @@ def _main():
 
         calc = SCons.Sig.default_calc
 
+    if options.random:
+        def order(dependencies):
+            """Randomize the dependencies."""
+            # This is cribbed from the implementation of
+            # random.shuffle() in Python 2.X.
+            d = dependencies
+            for i in xrange(len(d)-1, 0, -1):
+                j = int(random.random() * (i+1))
+                d[i], d[j] = d[j], d[i]
+            return d
+    else:
+        def order(dependencies):
+            """Leave the order of dependencies alone."""
+            return dependencies
+
     display("scons: Building targets ...")
-    taskmaster = SCons.Taskmaster.Taskmaster(nodes, task_class, calc)
+    taskmaster = SCons.Taskmaster.Taskmaster(nodes, task_class, calc, order)
 
     jobs = SCons.Job.Jobs(get_num_jobs(options), taskmaster)
 
diff --git a/src/engine/SCons/Taskmaster.py b/src/engine/SCons/Taskmaster.py
index e0d933e..521dc19 100644
--- a/src/engine/SCons/Taskmaster.py
+++ b/src/engine/SCons/Taskmaster.py
@@ -159,6 +159,10 @@ class Task:
                     side_effect.set_state(state)
             t.set_state(state)
 
+def order(dependencies):
+    """Re-order a list of dependencies (if we need to)."""
+    return dependencies
+
 class Calc:
     def bsig(self, node):
         """
@@ -180,7 +184,7 @@ class Taskmaster:
     the base class method, so this class can do its thing.
     """
 
-    def __init__(self, targets=[], tasker=Task, calc=Calc()):
+    def __init__(self, targets=[], tasker=Task, calc=Calc(), order=order):
         self.targets = targets # top level targets
         self.candidates = targets[:] # nodes that might be ready to be executed
         self.candidates.reverse()
@@ -189,6 +193,7 @@ class Taskmaster:
         self.tasker = tasker
         self.ready = None # the next task that is ready to be executed
         self.calc = calc
+        self.order = order
 
     def _find_next_ready_node(self):
         """Find the next node that is ready to be built"""
@@ -200,12 +205,12 @@ class Taskmaster:
             node = self.candidates[-1]
             state = node.get_state()
 
-            # Skip nodes that have already been executed:
+            # Skip this node if it has already been executed:
             if state != None and state != SCons.Node.stack:
                 self.candidates.pop()
                 continue
 
-            # keep track of which nodes are in the execution stack:
+            # Mark this node as being on the execution stack:
             node.set_state(SCons.Node.stack)
 
             try:
@@ -221,7 +226,7 @@ class Taskmaster:
                 self.ready = node
                 break
 
-            # detect dependency cycles:
+            # Detect dependency cycles:
             def in_stack(node): return node.get_state() == SCons.Node.stack
             cycle = filter(in_stack, children)
             if cycle:
@@ -230,17 +235,18 @@ class Taskmaster:
                 desc = "Dependency cycle: " + string.join(map(str, nodes), " -> ")
                 raise SCons.Errors.UserError, desc
 
-            # Add non-derived files that have not been built
+            # Add derived files that have not been built
             # to the candidates list:
             def derived(node):
                 return (node.has_builder() or node.side_effect) and node.get_state() == None
             derived = filter(derived, children)
             if derived:
                 derived.reverse()
-                self.candidates.extend(derived)
+                self.candidates.extend(self.order(derived))
                 continue
 
-            # Skip nodes whose side-effects are currently being built:
+            # Skip this node if it has side-effects that are
+            # currently being built:
             cont = 0
             for side_effect in node.side_effects:
                 if side_effect.get_state() == SCons.Node.executing:
@@ -251,14 +257,16 @@ class Taskmaster:
                     break
             if cont: continue
 
-            # Skip nodes that are pending on a currently executing node:
+            # Skip this node if it is pending on a currently
+            # executing node:
             if node.depends_on(self.executing) or node.depends_on(self.pending):
                 self.pending.append(node)
                 node.set_state(SCons.Node.pending)
                 self.candidates.pop()
                 continue
 
-            # The default when we've gotten through all of the checks above.
+            # The default when we've gotten through all of the checks above:
+            # this node is ready to be built.
             self.candidates.pop()
             self.ready = node
             break
diff --git a/src/engine/SCons/TaskmasterTests.py b/src/engine/SCons/TaskmasterTests.py
index 2b8a362..5a19c56 100644
--- a/src/engine/SCons/TaskmasterTests.py
+++ b/src/engine/SCons/TaskmasterTests.py
@@ -352,6 +352,29 @@ class TaskmasterTestCase(unittest.TestCase):
         assert not tm.next_task()
         t.executed()
 
+        n1 = Node("n1")
+        n2 = Node("n2")
+        n3 = Node("n3")
+        n4 = Node("n4", [n1,n2,n3])
+        def reverse(dependencies):
+            dependencies.reverse()
+            return dependencies
+        tm = SCons.Taskmaster.Taskmaster([n4], order=reverse)
+        t = tm.next_task()
+        assert t.get_target() == n3, t.get_target()
+        t.executed()
+        t = tm.next_task()
+        assert t.get_target() == n2, t.get_target()
+        t.executed()
+        t = tm.next_task()
+        assert t.get_target() == n1, t.get_target()
+        t.executed()
+        t = tm.next_task()
+        assert t.get_target() == n4, t.get_target()
+        t.executed()
+
+
+
     def test_make_ready_exception(self):
         """Test handling exceptions from Task.make_ready()
         """