Detect dependency cycles

5 files changed, 125 insertions, 9 deletions

diff --git a/src/engine/SCons/Node/NodeTests.py b/src/engine/SCons/Node/NodeTests.py
index 8c51e0ba..2eba47eb 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 a6606a95..83663dc3 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 e7dcfc03..1fb200c9 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 23f20820..ca3037dd 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
diff --git a/test/dependency-cycle.py b/test/dependency-cycle.py
new file mode 100644
index 00000000..a907ff68
--- /dev/null
+++ b/test/dependency-cycle.py
@@ -0,0 +1,58 @@
+#!/usr/bin/env python
+#
+# Copyright (c) 2001 Steven Knight
+#
+# Permission is hereby granted, free of charge, to any person obtaining
+# a copy of this software and associated documentation files (the
+# "Software"), to deal in the Software without restriction, including
+# without limitation the rights to use, copy, modify, merge, publish,
+# distribute, sublicense, and/or sell copies of the Software, and to
+# permit persons to whom the Software is furnished to do so, subject to
+# the following conditions:
+#
+# The above copyright notice and this permission notice shall be included
+# in all copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
+# KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
+# WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+# LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+# OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+# WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+#
+
+__revision__ = "test/dependency-cycle.py __REVISION__ __DATE__ __DEVELOPER__"
+
+import TestSCons
+import TestCmd
+
+test = TestSCons.TestSCons(match = TestCmd.match_re)
+
+test.write('SConstruct', """
+env = Environment()
+foo1 = env.Library(target = 'foo1', source = 'f1.c')
+foo2 = env.Library(target = 'foo2', source = 'f1.c')
+foo3 = env.Library(target = 'foo3', source = 'f1.c')
+env.Depends(foo1, foo2)
+env.Depends(foo2, foo3)
+env.Depends(foo3, foo1)
+""")
+
+test.write('f1.c', r"""
+void
+f1(void)
+{
+	printf("f1.c\n");
+}
+""")
+
+test.run(arguments = ".", stdout = "", stderr=r"""
+SCons error: Dependency cycle: .*foo1.* -> .*foo3.* -> .*foo2.* -> .*foo1.* -> \.
+.*
+""")
+
+
+test.pass_test()
+
+