4 files changed, 67 insertions, 9 deletions

diff --git a/src/engine/SCons/Node/NodeTests.py b/src/engine/SCons/Node/NodeTests.py
index 8c51e0b..2eba47e 100644
--- a/src/engine/SCons/Node/NodeTests.py
+++ b/src/engine/SCons/Node/NodeTests.py
@@ -35,6 +35,7 @@ import SCons.Node
 built_it = None
 built_target =  None
 built_source =  None
+cycle_detected = None
 
 class Builder:
     def execute(self, **kw):
@@ -306,6 +307,28 @@ class NodeTestCase(unittest.TestCase):
 	assert nw.next().name ==  "n1"
 	assert nw.next() == None
 
+        n8 = MyNode("n8")
+        n8.add_dependency([n3])
+        n7.add_dependency([n8])
+
+        def cycle(node, stack):
+            global cycle_detected
+            cycle_detected = 1
+
+        global cycle_detected
+
+        nw = SCons.Node.Walker(n3, cycle_func = cycle)
+        n = nw.next()
+        assert n.name == "n6", n.name
+        n = nw.next()
+        assert n.name == "n8", n.name
+        assert cycle_detected
+        cycle_detected = None
+        n = nw.next()
+        assert n.name == "n7", n.name
+        n = nw.next()
+        assert nw.next() == None
+
     def test_children_are_executed(self):
         n1 = SCons.Node.Node()
         n2 = SCons.Node.Node()
diff --git a/src/engine/SCons/Node/__init__.py b/src/engine/SCons/Node/__init__.py
index a6606a9..83663dc 100644
--- a/src/engine/SCons/Node/__init__.py
+++ b/src/engine/SCons/Node/__init__.py
@@ -176,6 +176,7 @@ class Node:
                       1)
 
 def get_children(node): return node.children()
+def ignore_cycle(node, stack): pass
 
 class Wrapper:
     def __init__(self, node, kids_func):
@@ -184,6 +185,9 @@ class Wrapper:
 
         # XXX randomize kids here, if requested
 
+    def __str__(self):
+        return str(self.node)
+
 class Walker:
     """An iterator for walking a Node tree.
 
@@ -191,13 +195,16 @@ class Walker:
     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'.
+    get the children of a node instead of calling 'children'. 
+    'cycle_func' is an optional function that will be called
+    when a cycle is detected.
     
     This class does not get caught in node cycles caused, for example,
     by C header file include loops.
     """
-    def __init__(self, node, kids_func=get_children):
+    def __init__(self, node, kids_func=get_children, cycle_func=ignore_cycle):
         self.kids_func = kids_func
+        self.cycle_func = cycle_func
         self.stack = [Wrapper(node, self.kids_func)]
         self.history = {} # used to efficiently detect and avoid cycles
         self.history[node] = None
@@ -212,7 +219,9 @@ class Walker:
 	while self.stack:
 	    if self.stack[-1].kids:
                 node = self.stack[-1].kids.pop(0)
-                if not self.history.has_key(node):
+                if self.history.has_key(node):
+                    self.cycle_func(node, self.stack)
+                else:
                     self.stack.append(Wrapper(node, self.kids_func))
                     self.history[node] = None
             else:
diff --git a/src/engine/SCons/Taskmaster.py b/src/engine/SCons/Taskmaster.py
index e7dcfc0..1fb200c 100644
--- a/src/engine/SCons/Taskmaster.py
+++ b/src/engine/SCons/Taskmaster.py
@@ -33,8 +33,9 @@ __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__"
 
 
 import SCons.Node
-
-
+import string
+import SCons.Errors
+import copy
 
 class Task:
     """Default SCons build engine task.
@@ -140,10 +141,20 @@ class Taskmaster:
     """
 
     def __init__(self, targets=[], tasker=Task, calc=Calc()):
+        
         def out_of_date(node):
             return filter(lambda x: x.get_state() != SCons.Node.up_to_date,
                           node.children())
-        self.walkers = map(lambda x, f=out_of_date: SCons.Node.Walker(x, f),
+
+        def cycle_error(node, stack):
+            if node.builder:
+                nodes = stack + [node]
+                nodes.reverse()
+                desc = "Dependency cycle: " + string.join(map(str, nodes), " -> ")
+                raise SCons.Errors.UserError, desc
+
+        #XXX In Python 2.2 we can get rid of f1 and f2:
+        self.walkers = map(lambda x, f1=out_of_date, f2=cycle_error: SCons.Node.Walker(x, f1, f2),
                            targets)
         self.tasker = tasker
         self.calc = calc
diff --git a/src/engine/SCons/TaskmasterTests.py b/src/engine/SCons/TaskmasterTests.py
index 23f2082..ca3037d 100644
--- a/src/engine/SCons/TaskmasterTests.py
+++ b/src/engine/SCons/TaskmasterTests.py
@@ -27,7 +27,7 @@ import sys
 import unittest
 
 import SCons.Taskmaster
-
+import SCons.Errors
 
 
 built = None
@@ -74,7 +74,8 @@ class Node:
                                    and x),
                       self.children(),
                       1)
-
+    def __str__(self):
+        return self.name
 
 
 class TaskmasterTestCase(unittest.TestCase):
@@ -210,7 +211,21 @@ class TaskmasterTestCase(unittest.TestCase):
         assert not tm.is_blocked()
         t = tm.next_task()
         assert tm. next_task() == None
-        
+    
+    def test_cycle_detection(self):
+        n1 = Node("n1")
+        n2 = Node("n2", [n1])
+        n3 = Node("n3", [n2])
+        n1.kids = [n3]
+        n3.parents.append(n1)
+
+        try:
+            tm = SCons.Taskmaster.Taskmaster([n3])
+            t = tm.next_task()
+        except SCons.Errors.UserError, e:
+            assert str(e) == "Dependency cycle: n3 -> n1 -> n2 -> n3"
+        else:
+            assert 0
         
     def test_is_blocked(self):
         """Test whether a task is blocked