Add -k support and more

6 files changed, 365 insertions, 86 deletions

diff --git a/src/engine/SCons/Job.py b/src/engine/SCons/Job.py
index 4e791667..17315fc3 100644
--- a/src/engine/SCons/Job.py
+++ b/src/engine/SCons/Job.py
@@ -249,9 +249,12 @@ class Parallel:
                     self.taskmaster.failed(task)
                 else:
                     self.taskmaster.executed(task)
-                    
-                    if not self.taskmaster.is_blocked():
-                        cv.notifyAll()
+
+                # signal the cv whether the task failed or not,
+                # or otherwise the other Jobs might
+                # remain blocked:
+                if not self.taskmaster.is_blocked():
+                    cv.notifyAll()
                     
         finally:
             cv.release()
diff --git a/src/engine/SCons/Node/FSTests.py b/src/engine/SCons/Node/FSTests.py
index 6f2a5a75..044f83fe 100644
--- a/src/engine/SCons/Node/FSTests.py
+++ b/src/engine/SCons/Node/FSTests.py
@@ -160,15 +160,17 @@ class FSTestCase(unittest.TestCase):
 
         built_it = None
         assert not built_it
-        d1.add_source(["d"])    # XXX FAKE SUBCLASS ATTRIBUTE
+        d1.add_source([SCons.Node.Node()])    # XXX FAKE SUBCLASS ATTRIBUTE
         d1.builder_set(Builder())
         d1.env_set(Environment())
         d1.build()
         assert built_it
 
+        assert d1.get_parents() == [] 
+
         built_it = None
         assert not built_it
-        f1.add_source(["f"])    # XXX FAKE SUBCLASS ATTRIBUTE
+        f1.add_source([SCons.Node.Node()])    # XXX FAKE SUBCLASS ATTRIBUTE
         f1.builder_set(Builder())
         f1.env_set(Environment())
         f1.build()
diff --git a/src/engine/SCons/Node/NodeTests.py b/src/engine/SCons/Node/NodeTests.py
index 02b34b52..b8015c28 100644
--- a/src/engine/SCons/Node/NodeTests.py
+++ b/src/engine/SCons/Node/NodeTests.py
@@ -128,42 +128,96 @@ class NodeTestCase(unittest.TestCase):
 	"""
 	node = SCons.Node.Node()
 	assert node.depends == []
-	try:
-	    node.add_dependency('zero')
+
+        zero = SCons.Node.Node()
+        try:
+	    node.add_dependency(zero)
 	except TypeError:
 	    pass
-	node.add_dependency(['one'])
-	assert node.depends == ['one']
-	node.add_dependency(['two', 'three'])
-	assert node.depends == ['one', 'two', 'three']
-	node.add_dependency(['three', 'four', 'one'])
-	assert node.depends == ['one', 'two', 'three', 'four']
+        else:
+            assert 0
+
+        one = SCons.Node.Node()
+        two = SCons.Node.Node()
+        three = SCons.Node.Node()
+        four = SCons.Node.Node()
+
+        node.add_dependency([one])
+        assert node.depends == [one]
+        node.add_dependency([two, three])
+        assert node.depends == [one, two, three]
+        node.add_dependency([three, four, one])
+        assert node.depends == [one, two, three, four]
+
+        assert zero.get_parents() == []
+        assert one.get_parents() == [node]
+        assert two.get_parents() == [node]
+        assert three.get_parents() == [node]
+        assert four.get_parents() == [node]
+
 
     def test_add_source(self):
 	"""Test adding sources to a Node's list.
 	"""
 	node = SCons.Node.Node()
 	assert node.sources == []
+
+        zero = SCons.Node.Node()
 	try:
-	    node.add_source('zero')
+	    node.add_source(zero)
 	except TypeError:
 	    pass
-	node.add_source(['one'])
-	assert node.sources == ['one']
-	node.add_source(['two', 'three'])
-	assert node.sources == ['one', 'two', 'three']
-	node.add_source(['three', 'four', 'one'])
-	assert node.sources == ['one', 'two', 'three', 'four']
+        else:
+            assert 0
+
+        one = SCons.Node.Node()
+        two = SCons.Node.Node()
+        three = SCons.Node.Node()
+        four = SCons.Node.Node()
+
+        node.add_source([one])
+        assert node.sources == [one]
+        node.add_source([two, three])
+        assert node.sources == [one, two, three]
+        node.add_source([three, four, one])
+        assert node.sources == [one, two, three, four]
+
+        assert zero.get_parents() == []
+        assert one.get_parents() == [node]
+        assert two.get_parents() == [node]
+        assert three.get_parents() == [node]
+        assert four.get_parents() == [node]
 
     def test_children(self):
 	"""Test fetching the "children" of a Node.
 	"""
 	node = SCons.Node.Node()
-	node.add_source(['one', 'two', 'three'])
-	node.add_dependency(['four', 'five', 'six'])
-	kids = node.children()
-	kids.sort()
-	assert kids == ['five', 'four', 'one', 'six', 'three', 'two']
+        one = SCons.Node.Node()
+        two = SCons.Node.Node()
+        three = SCons.Node.Node()
+        four = SCons.Node.Node()
+        five = SCons.Node.Node()
+        six = SCons.Node.Node()
+
+        node.add_source([one, two, three])
+        node.add_dependency([four, five, six])
+        kids = node.children()
+        assert len(kids) == 6
+        assert one in kids
+        assert two in kids
+        assert three in kids
+        assert four in kids
+        assert five in kids
+        assert six in kids
+
+    def test_add_parent(self):
+        """Test adding parents to a Node."""
+        node = SCons.Node.Node()
+        parent = SCons.Node.Node()
+        node._add_parent(parent)
+        assert node.get_parents() == [parent]
+        node._add_parent(parent)
+        assert node.get_parents() == [parent]
 
     def test_state(self):
 	"""Test setting and getting the state of a node
@@ -217,6 +271,39 @@ class NodeTestCase(unittest.TestCase):
 	assert nw.next().name ==  "n1"
 	assert nw.next() == None
 
+    def test_children_are_executed(self):
+        n1 = SCons.Node.Node()
+        n2 = SCons.Node.Node()
+        n3 = SCons.Node.Node()
+        n4 = SCons.Node.Node()
+
+        n4.add_source([n3])
+        n3.add_source([n1, n2])
+
+        assert not n4.children_are_executed()
+        assert not n3.children_are_executed()
+        assert n2.children_are_executed()
+        assert n1.children_are_executed()
+
+        n1.set_state(SCons.Node.executed)
+        assert not n4.children_are_executed()
+        assert not n3.children_are_executed()
+        assert n2.children_are_executed()
+        assert n1.children_are_executed()
+
+        n2.set_state(SCons.Node.executed)
+        assert not n4.children_are_executed()
+        assert n3.children_are_executed()
+        assert n2.children_are_executed()
+        assert n1.children_are_executed()
+
+        n3.set_state(SCons.Node.executed)
+        assert n4.children_are_executed()
+        assert n3.children_are_executed()
+        assert n2.children_are_executed()
+        assert n1.children_are_executed()
+
+
 
 
 if __name__ == "__main__":
diff --git a/src/engine/SCons/Node/__init__.py b/src/engine/SCons/Node/__init__.py
index 265071ed..b7bdecf8 100644
--- a/src/engine/SCons/Node/__init__.py
+++ b/src/engine/SCons/Node/__init__.py
@@ -41,7 +41,7 @@ executing = 1
 executed = 2
 up_to_date = 3
 failed = 4
-
+pending = 5
 
 class Node:
     """The base Node class, for entities that we know how to
@@ -51,6 +51,7 @@ class Node:
     def __init__(self):
 	self.sources = []
 	self.depends = []
+        self.parents = []
 	self.builder = None
 	self.env = None
         self.state = None
@@ -82,24 +83,35 @@ class Node:
         return self.signature
 
     def add_dependency(self, depend):
-	"""Adds dependencies. The depends argument must be a list."""
-        if type(depend) is not type([]):
-            raise TypeError("depend must be a list")
-	depend = filter(lambda x, d=self.depends: x not in d, depend)
-	if len(depend):
-	    self.depends.extend(depend)
+	"""Adds dependencies. The depend argument must be a list."""
+        self._add_child(self.depends, depend)
 
     def add_source(self, source):
 	"""Adds sources. The source argument must be a list."""
-        if type(source) is not type([]):
-            raise TypeError("source must be a list")
-	source = filter(lambda x, s=self.sources: x not in s, source)
-	if len(source):
-	    self.sources.extend(source)
+        self._add_child(self.sources, source)
+
+    def _add_child(self, collection, child):
+        """Adds 'child' to 'collection'. The 'child' argument must be a list"""
+        if type(child) is not type([]):
+            raise TypeError("child must be a list")
+	child = filter(lambda x, s=collection: x not in s, child)
+	if child:
+	    collection.extend(child)
+
+        for c in child:
+            c._add_parent(self)
+
+    def _add_parent(self, parent):
+        """Adds 'parent' to the list of parents of this node"""
+
+        if parent not in self.parents: self.parents.append(parent)
 
     def children(self):
 	return self.sources + self.depends
 
+    def get_parents(self):
+        return self.parents
+
     def set_state(self, state):
         self.state = state
 
@@ -109,10 +121,20 @@ class Node:
     def current(self):
         return None
 
+    def children_are_executed(self):
+        return reduce(lambda x,y: ((y.get_state() == executed
+                                   or y.get_state() == up_to_date)
+                                   and x),
+                      self.children(),
+                      1)
+
+def get_children(node): return node.children()
+
 class Wrapper:
-    def __init__(self, node):
+    def __init__(self, node, kids_func):
         self.node = node
-        self.kids = copy.copy(node.children())
+        self.kids = copy.copy(kids_func(node))
+
         # XXX randomize kids here, if requested
 
 class Walker:
@@ -121,9 +143,12 @@ class Walker:
     This is depth-first, children are visited before the parent.
     The Walker object can be initialized with any node, and
     returns the next node on the descent with each next() call.
+    'kids_func' is an optional function that will be called to
+    get the children of a node instead of calling 'children'.
     """
-    def __init__(self, node):
-        self.stack = [Wrapper(node)]
+    def __init__(self, node, kids_func=get_children):
+        self.kids_func = kids_func
+        self.stack = [Wrapper(node, self.kids_func)]
 
     def next(self):
 	"""Return the next node for this walk of the tree.
@@ -134,7 +159,8 @@ class Walker:
 
 	while self.stack:
 	    if self.stack[-1].kids:
-	    	self.stack.append(Wrapper(self.stack[-1].kids.pop(0)))
+	    	self.stack.append(Wrapper(self.stack[-1].kids.pop(0),
+                                          self.kids_func))
             else:
                 return self.stack.pop().node
 
diff --git a/src/engine/SCons/Taskmaster.py b/src/engine/SCons/Taskmaster.py
index 3fd787eb..3b4ee85d 100644
--- a/src/engine/SCons/Taskmaster.py
+++ b/src/engine/SCons/Taskmaster.py
@@ -46,6 +46,9 @@ class Task:
 
     def set_state(self, state):
         return self.target.set_state(state)
+
+    def get_target(self):
+        return self.target
         
 def current(node):
     """Default SCons build engine is-it-current function.
@@ -64,38 +67,55 @@ class Taskmaster:
     the base class method, so this class can do it's thing.    
     """
 
-    def __init__(self, targets=[], tasker=Task, current=current):
+    def __init__(self,
+                 targets=[],
+                 tasker=Task,
+                 current=current,
+                 ignore_errors=0,
+                 keep_going_on_error=0):
         self.walkers = map(SCons.Node.Walker, targets)
         self.tasker = tasker
         self.current = current
         self.targets = targets
+        self.ready = []
+        self.pending = 0
+        self.ignore_errors = ignore_errors
+        self.keep_going_on_error = keep_going_on_error
 
+        self._find_next_ready_node()
+        
     def next_task(self):
+        if self.ready:
+            n = self.ready.pop()
+            n.set_state(SCons.Node.executing)
+            if not self.ready:
+                self._find_next_ready_node()
+
+            return self.tasker(n)
+        else:
+            return None
+        
+    def _find_next_ready_node(self):
+        """Find the next node that is ready to be built"""
         while self.walkers:
             n = self.walkers[0].next()
             if n == None:
                 self.walkers.pop(0)
             elif n.get_state() == SCons.Node.up_to_date:
                 self.up_to_date(n, self.walkers[0].is_done())
-            elif n.get_state() == SCons.Node.failed:
-                # XXX do the right thing here
-                pass
-            elif n.get_state() == SCons.Node.executing:
-                # XXX do the right thing here
-                pass
-            elif n.get_state() == SCons.Node.executed:
-                # skip this node because it has already been executed
-                pass
-            elif self.current(n):
-                n.set_state(SCons.Node.up_to_date)
-                self.up_to_date(n, self.walkers[0].is_done())
-            else:
-                n.set_state(SCons.Node.executing)
-                return self.tasker(n)
-	return None
- 
+            elif n.get_state() == None:
+                if not n.children_are_executed():
+                    n.set_state(SCons.Node.pending)
+                    self.pending = self.pending + 1
+                elif self.current(n):
+                    n.set_state(SCons.Node.up_to_date)
+                    self.up_to_date(n, self.walkers[0].is_done())
+                else:
+                    self.ready.append(n)
+                    return
+        
     def is_blocked(self):
-        return 0
+        return not self.ready and self.pending
 
     def up_to_date(self, node):
         pass
@@ -103,6 +123,33 @@ class Taskmaster:
     def executed(self, task):
         task.set_state(SCons.Node.executed)
 
+        # add all the pending parents that are now executable to the 'ready'
+        # queue:
+        n = task.get_target()
+        ready = filter(lambda x: (x.get_state() == SCons.Node.pending
+                                  and x.children_are_executed()),
+                       n.get_parents())
+        self.ready.extend(ready)
+        self.pending = self.pending - len(ready)
+        
     def failed(self, task):
-        self.walkers = []
-        task.set_state(SCons.Node.failed)
+        if self.ignore_errors:
+            self.executed(task)
+        else:
+            if self.keep_going_on_error:
+                # mark all the depants of this node as failed:
+                def get_parents(node): return node.get_parents()
+                walker = SCons.Node.Walker(task.get_target(), get_parents)
+                while 1:
+                    node = walker.next()
+                    if node == None: break
+                    if node.get_state() == SCons.Node.pending:
+                        self.pending = self.pending - 1
+                    node.set_state(SCons.Node.failed)
+            else:
+                # terminate the build:
+                self.walkers = []
+                self.pending = 0
+                self.ready = []
+
+            task.set_state(SCons.Node.failed)
diff --git a/src/engine/SCons/TaskmasterTests.py b/src/engine/SCons/TaskmasterTests.py
index 59f62bd7..809df6a3 100644
--- a/src/engine/SCons/TaskmasterTests.py
+++ b/src/engine/SCons/TaskmasterTests.py
@@ -36,7 +36,12 @@ class Node:
     def __init__(self, name, kids = []):
         self.name = name
 	self.kids = kids
-
+        self.state = None
+        self.parents = []
+        
+        for kid in kids:
+            kid.parents.append(self)
+            
     def build(self):
         global built
         built = self.name + " built"
@@ -44,18 +49,22 @@ class Node:
     def children(self):
 	return self.kids
 
+    def get_parents(self):
+        return self.parents
+    
     def get_state(self):
-        pass
+        return self.state
 
     def set_state(self, state):
-        pass
+        self.state = state
 
-class Task:
-    def __init__(self, target):
-        self.target = target
-
-    def set_state(self, state):
-        pass
+    def children_are_executed(self):
+        return reduce(lambda x,y: ((y.get_state() == SCons.Node.executed
+                                   or y.get_state() == SCons.Node.up_to_date)
+                                   and x),
+                      self.children(),
+                      1)
+    
 
 
 class TaskmasterTestCase(unittest.TestCase):
@@ -65,19 +74,36 @@ class TaskmasterTestCase(unittest.TestCase):
 	"""
 	global built
 
+        n1 = Node("n1")
+        tm = SCons.Taskmaster.Taskmaster([n1,n1])
+        t = tm.next_task()
+        tm.executed(t)
+        t = tm.next_task()
+        assert t == None
+
+        
 	n1 = Node("n1")
 	n2 = Node("n2")
         n3 = Node("n3", [n1, n2])
         
 	tm = SCons.Taskmaster.Taskmaster([n3])
-	tm.next_task().execute()
-	assert built == "n1 built"
 
-	tm.next_task().execute()
-	assert built == "n2 built"
+        t = tm.next_task()
+        t.execute()
+        assert built == "n1 built"
+        tm.executed(t)
+
+        t = tm.next_task()
+        t.execute()
+        assert built == "n2 built"
+        tm.executed(t)
 
-	tm.next_task().execute()
-	assert built == "n3 built"
+        t = tm.next_task()
+        t.execute()
+        assert built == "n3 built"
+        tm.executed(t)
+
+        assert tm.next_task() == None
 
 	def current(node):
 	    return 1
@@ -93,23 +119,68 @@ class TaskmasterTestCase(unittest.TestCase):
                 global built
                 built = built + " " + node.name
 
+
+        n1.set_state(None)
+        n2.set_state(None)
+        n3.set_state(None)
 	tm = MyTM(targets = [n3], current = current)
 	assert tm.next_task() == None
         print built
 	assert built == "up to date:  n1 n2 n3"
 
+
+        n1 = Node("n1")
+	n2 = Node("n2")
+        n3 = Node("n3", [n1, n2])
         n4 = Node("n4")
-        n4.get_state = lambda: SCons.Node.executed
-        tm = SCons.Taskmaster.Taskmaster([n4])
+        n5 = Node("n5", [n3, n4])
+        tm = SCons.Taskmaster.Taskmaster([n5])
+
+        assert not tm.is_blocked()
+        
+        t1 = tm.next_task()
+        assert t1.get_target() == n1
+        assert not tm.is_blocked()
+        
+        t2 = tm.next_task()
+        assert t2.get_target() == n2
+        assert not tm.is_blocked()
+
+        t4 = tm.next_task()
+        assert t4.get_target() == n4
+        assert tm.is_blocked()
+        tm.executed(t4)
+        assert tm.is_blocked()
+        
+        tm.executed(t1)
+        assert tm.is_blocked()
+        tm.executed(t2)
+        assert not tm.is_blocked()
+        t3 = tm.next_task()
+        assert t3.get_target() == n3
+        assert tm.is_blocked()
+
+        tm.executed(t3)
+        assert not tm.is_blocked()
+        t5 = tm.next_task()
+        assert t5.get_target() == n5
+        assert not tm.is_blocked()
+
         assert tm.next_task() == None
+
         
+        n4 = Node("n4")
+        n4.set_state(SCons.Node.executed)
+        tm = SCons.Taskmaster.Taskmaster([n4])
+        assert tm.next_task() == None
+
     def test_is_blocked(self):
         """Test whether a task is blocked
 
 	Both default and overridden in a subclass.
 	"""
 	tm = SCons.Taskmaster.Taskmaster()
-	assert tm.is_blocked() == 0
+	assert not tm.is_blocked()
 
 	class MyTM(SCons.Taskmaster.Taskmaster):
 	    def is_blocked(self):
@@ -123,7 +194,8 @@ class TaskmasterTestCase(unittest.TestCase):
 	Both default and overridden in a subclass.
 	"""
 	tm = SCons.Taskmaster.Taskmaster()
-	tm.executed(Task('foo'))
+        foo = Node('foo')
+	tm.executed(SCons.Taskmaster.Task(foo))
 
 	class MyTM(SCons.Taskmaster.Taskmaster):
 	    def executed(self, task):
@@ -131,15 +203,57 @@ class TaskmasterTestCase(unittest.TestCase):
 	tm = MyTM()
 	assert tm.executed('foo') == 'xfoo'
 
+    def test_ignore_errors(self):
+        n1 = Node("n1")
+        n2 = Node("n2")
+        n3 = Node("n3", [n1])
+        
+        tm = SCons.Taskmaster.Taskmaster([n3, n2],
+                                         SCons.Taskmaster.Task,
+                                         SCons.Taskmaster.current,
+                                         1)
+
+        t = tm.next_task()
+        assert t.get_target() == n1
+        tm.failed(t)
+        t = tm.next_task()
+        assert t.get_target() == n3
+        tm.failed(t)
+        t = tm.next_task()
+        assert t.get_target() == n2
+        
+
+    def test_keep_going(self):
+        n1 = Node("n1")
+        n2 = Node("n2")
+        n3 = Node("n3", [n1])
+        
+        tm = SCons.Taskmaster.Taskmaster([n3, n2],
+                                         SCons.Taskmaster.Task,
+                                         SCons.Taskmaster.current,
+                                         0,
+                                         1)
+
+        tm.failed(tm.next_task())
+        t = tm.next_task()
+        assert t.get_target() == n2
+        tm.executed(t)
+        assert not tm.is_blocked()
+        t = tm.next_task()
+        assert t == None
+
+
     def test_failed(self):
         """Test the failed() method
 
 	Both default and overridden in a subclass.
 	"""
-	tm = SCons.Taskmaster.Taskmaster()
-	#XXX
-	tm.failed(Task('foo'))
-
+        foo = Node('foo')
+        bar = Node('bar')
+        tm = SCons.Taskmaster.Taskmaster([foo,bar])
+        tm.failed(tm.next_task())
+        assert tm.next_task() == None
+        
 	class MyTM(SCons.Taskmaster.Taskmaster):
 	    def failed(self, task):
 	        return 'y' + task