From 6b1cb3d8c409854bbeaa06e61fc70435950f8d39 Mon Sep 17 00:00:00 2001 From: Steven Knight Date: Wed, 28 Nov 2001 04:47:15 +0000 Subject: Detect dependency cycles --- src/engine/SCons/Node/NodeTests.py | 23 +++++++++++++++ src/engine/SCons/Node/__init__.py | 15 ++++++++-- src/engine/SCons/Taskmaster.py | 17 +++++++++-- src/engine/SCons/TaskmasterTests.py | 21 ++++++++++++-- test/dependency-cycle.py | 58 +++++++++++++++++++++++++++++++++++++ 5 files changed, 125 insertions(+), 9 deletions(-) create mode 100644 test/dependency-cycle.py 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() + + -- cgit v1.2.1