Eliminate unnecessary scanning before a Node is rebuilt.

11 files changed, 267 insertions, 102 deletions

diff --git a/src/CHANGES.txt b/src/CHANGES.txt
index 48c7e08..bc885f7 100644
--- a/src/CHANGES.txt
+++ b/src/CHANGES.txt
@@ -31,6 +31,10 @@ RELEASE 0.10 - XXX
   - Refactor the Scanner interface to eliminate unnecessary Scanner
     calls and make it easier to write efficient scanners.
 
+  - Added a "recursive" flag to Scanner creation that specifies the
+    Scanner should be invoked recursively on dependency files returned
+    by the scanner.
+
   - Significant performance improvement from using a more efficient
     check, throughout the code, for whether a Node has a Builder.
 
diff --git a/src/engine/SCons/Node/FS.py b/src/engine/SCons/Node/FS.py
index aa7f973..1b627fd 100644
--- a/src/engine/SCons/Node/FS.py
+++ b/src/engine/SCons/Node/FS.py
@@ -857,7 +857,10 @@ class File(Entry):
     def get_stored_implicit(self):
         return self.dir.sconsign().get_implicit(self.name)
 
-    def get_implicit_deps(self, env, scanner, target):
+    def get_found_includes(self, env, scanner, target):
+        """Return the included implicit dependencies in this file.
+        Cache results so we only scan the file once regardless of
+        how many times this information is requested."""
         if not scanner:
             return []
 
diff --git a/src/engine/SCons/Node/FSTests.py b/src/engine/SCons/Node/FSTests.py
index 6c8893d..63cdf2c 100644
--- a/src/engine/SCons/Node/FSTests.py
+++ b/src/engine/SCons/Node/FSTests.py
@@ -65,14 +65,15 @@ class Builder:
 scanner_count = 0
 
 class Scanner:
-    def __init__(self):
+    def __init__(self, node=None):
         global scanner_count
         scanner_count = scanner_count + 1
         self.hash = scanner_count
+        self.node = node
     def path(self, env, target):
         return ()
     def __call__(self, node, env, path):
-        return [node]
+        return [self.node]
     def __hash__(self):
         return self.hash
 
@@ -674,45 +675,47 @@ class FSTestCase(unittest.TestCase):
         # Test scanning
         f1.builder_set(Builder(fs.File))
         f1.env_set(Environment())
-        f1.target_scanner = Scanner()
+        xyz = fs.File("xyz")
+        f1.target_scanner = Scanner(xyz)
+
         f1.scan()
-        assert f1.implicit[0].path_ == os.path.join("d1", "f1")
+        assert f1.implicit[0].path_ == "xyz"
         f1.implicit = []
         f1.scan()
         assert f1.implicit == []
         f1.implicit = None
         f1.scan()
-        assert f1.implicit[0].path_ == os.path.join("d1", "f1"), f1.implicit[0].path_
+        assert f1.implicit[0].path_ == "xyz"
         f1.store_implicit()
-        assert f1.get_stored_implicit()[0] == os.path.join("d1", "f1")
+        assert f1.get_stored_implicit()[0] == "xyz"
 
-        # Test underlying scanning functionality in get_implicit_deps()
+        # Test underlying scanning functionality in get_found_includes()
         env = Environment()
         f12 = fs.File("f12")
         t1 = fs.File("t1")
 
-        deps = f12.get_implicit_deps(env, None, t1)
+        deps = f12.get_found_includes(env, None, t1)
         assert deps == [], deps
 
         class MyScanner(Scanner):
             call_count = 0
             def __call__(self, node, env, path):
                 self.call_count = self.call_count + 1
-                return [node]
-        s = MyScanner()
+                return Scanner.__call__(self, node, env, path)
+        s = MyScanner(xyz)
 
-        deps = f12.get_implicit_deps(env, s, t1)
-        assert deps == [f12], deps
+        deps = f12.get_found_includes(env, s, t1)
+        assert deps == [xyz], deps
         assert s.call_count == 1, s.call_count
 
-        deps = f12.get_implicit_deps(env, s, t1)
-        assert deps == [f12], deps
+        deps = f12.get_found_includes(env, s, t1)
+        assert deps == [xyz], deps
         assert s.call_count == 1, s.call_count
 
         f12.built()
 
-        deps = f12.get_implicit_deps(env, s, t1)
-        assert deps == [f12], deps
+        deps = f12.get_found_includes(env, s, t1)
+        assert deps == [xyz], deps
         assert s.call_count == 2, s.call_count
 
         # Test building a file whose directory is not there yet...
diff --git a/src/engine/SCons/Node/NodeTests.py b/src/engine/SCons/Node/NodeTests.py
index a2b95a5..7f55980 100644
--- a/src/engine/SCons/Node/NodeTests.py
+++ b/src/engine/SCons/Node/NodeTests.py
@@ -89,6 +89,26 @@ class Environment:
     def Override(selv, overrides):
         return overrides
 
+class Scanner:
+    called = None
+    def __call__(self, node):
+        self.called = 1
+        return node.found_includes
+
+class MyNode(SCons.Node.Node):
+    """The base Node class contains a number of do-nothing methods that
+    we expect to be overridden by real, functional Node subclasses.  So
+    simulate a real, functional Node subclass.
+    """
+    def __init__(self, name):
+        SCons.Node.Node.__init__(self)
+        self.name = name
+        self.found_includes = []
+    def __str__(self):
+        return self.name
+    def get_found_includes(self, env, scanner, target):
+        return scanner(self)
+
 
 
 class NodeTestCase(unittest.TestCase):
@@ -98,27 +118,23 @@ class NodeTestCase(unittest.TestCase):
         """
         global built_it
 
-        class MyNode(SCons.Node.Node):
-            def __str__(self):
-                return self.path
         # Make sure it doesn't blow up if no builder is set.
-        node = MyNode()
+        node = MyNode("www")
         node.build()
         assert built_it == None
 
-        node = MyNode()
+        node = MyNode("xxx")
         node.builder_set(Builder())
         node.env_set(Environment())
         node.path = "xxx"
         node.sources = ["yyy", "zzz"]
         node.build()
         assert built_it
-        assert type(built_target[0]) == type(MyNode()), type(built_target[0])
-        assert str(built_target[0]) == "xxx", str(built_target[0])
+        assert built_target[0] == node, built_target[0]
         assert built_source == ["yyy", "zzz"], built_source
 
         built_it = None
-        node = MyNode()
+        node = MyNode("qqq")
         node.builder_set(NoneBuilder())
         node.env_set(Environment())
         node.path = "qqq"
@@ -126,14 +142,13 @@ class NodeTestCase(unittest.TestCase):
         node.overrides = { "foo" : 1, "bar" : 2 }
         node.build()
         assert built_it
-        assert type(built_target[0]) == type(MyNode()), type(built_target[0])
-        assert str(built_target[0]) == "qqq", str(built_target[0])
+        assert built_target[0] == node, build_target[0]
         assert built_source == ["rrr", "sss"], built_source
         assert built_args["foo"] == 1, built_args
         assert built_args["bar"] == 2, built_args
 
-        fff = MyNode()
-        ggg = MyNode()
+        fff = MyNode("fff")
+        ggg = MyNode("ggg")
         lb = ListBuilder(fff, ggg)
         e = Environment()
         fff.builder_set(lb)
@@ -146,6 +161,8 @@ class NodeTestCase(unittest.TestCase):
         ggg.sources = ["hhh", "iii"]
 
     def test_depends_on(self):
+        """Test the depends_on() method
+        """
         parent = SCons.Node.Node()
         child = SCons.Node.Node()
         parent.add_dependency([child])
@@ -348,17 +365,75 @@ class NodeTestCase(unittest.TestCase):
         assert three.get_parents() == [node]
         assert four.get_parents() == [node]
 
-    def test_scan(self):
-        """Test Scanner functionality"""
-        class DummyScanner:
-            pass
-        ds=DummyScanner()
+    def test_get_found_includes(self):
+        """Test the default get_found_includes() method
+        """
         node = SCons.Node.Node()
+        target = SCons.Node.Node()
+        e = Environment()
+        deps = node.get_found_includes(e, None, target)
+        assert deps == [], deps
+
+    def test_get_implicit_deps(self):
+        """Test get_implicit_deps()
+        """
+        node = MyNode("nnn")
+        target = MyNode("ttt")
+        env = Environment()
+
+        # No scanner at all returns []
+        deps = node.get_implicit_deps(env, None, target)
+        assert deps == [], deps
+
+        s = Scanner()
+        d = MyNode("ddd")
+        node.found_includes = [d]
+
+        # Simple return of the found includes
+        deps = node.get_implicit_deps(env, s, target)
+        assert deps == [d], deps
+
+        # No "recursive" attribute on scanner doesn't recurse
+        e = MyNode("eee")
+        d.found_includes = [e]
+        deps = node.get_implicit_deps(env, s, target)
+        assert deps == [d], map(str, deps)
+
+        # Explicit "recursive" attribute on scanner doesn't recurse
+        s.recursive = None
+        deps = node.get_implicit_deps(env, s, target)
+        assert deps == [d], map(str, deps)
+
+        # Explicit "recursive" attribute on scanner which does recurse
+        s.recursive = 1
+        deps = node.get_implicit_deps(env, s, target)
+        assert deps == [d, e], map(str, deps)
+
+        # Recursive scanning eliminates duplicates
+        f = MyNode("fff")
+        d.found_includes = [e, f]
+        e.found_includes = [f]
+        deps = node.get_implicit_deps(env, s, target)
+        assert deps == [d, e, f], map(str, deps)
+
+    def test_scan(self):
+        """Test Scanner functionality
+        """
+        node = MyNode("nnn")
+        node.builder = 1
+        node.env_set(Environment())
+        s = Scanner()
+
+        d = MyNode("ddd")
+        node.found_includes = [d]
+
         assert node.target_scanner == None, node.target_scanner
-        node.target_scanner = ds
+        node.target_scanner = s
         assert node.implicit is None
+
         node.scan()
-        assert node.implicit == []
+        assert s.called
+        assert node.implicit == [d], node.implicit
 
     def test_scanner_key(self):
         """Test that a scanner_key() method exists"""
@@ -438,11 +513,6 @@ class NodeTestCase(unittest.TestCase):
         """Test walking a Node tree.
         """
 
-        class MyNode(SCons.Node.Node):
-            def __init__(self, name):
-                SCons.Node.Node.__init__(self)
-                self.name = name
-
         n1 = MyNode("n1")
 
         nw = SCons.Node.Walker(n1)
@@ -505,11 +575,6 @@ class NodeTestCase(unittest.TestCase):
 
     def test_rstr(self):
         """Test the rstr() method."""
-        class MyNode(SCons.Node.Node):
-            def __init__(self, name):
-                self.name = name
-            def __str__(self):
-                return self.name
         n1 = MyNode("n1")
         assert n1.rstr() == 'n1', n1.rstr()
 
diff --git a/src/engine/SCons/Node/__init__.py b/src/engine/SCons/Node/__init__.py
index 16e28e2..bac547c 100644
--- a/src/engine/SCons/Node/__init__.py
+++ b/src/engine/SCons/Node/__init__.py
@@ -191,10 +191,48 @@ class Node:
                 return None
         return Adapter(self)
 
-    def get_implicit_deps(self, env, scanner, target):
-        """Return a list of implicit dependencies for this node"""
+    def get_found_includes(self, env, scanner, target):
+        """Return the scanned include lines (implicit dependencies)
+        found in this node.
+
+        The default is no implicit dependencies.  We expect this method
+        to be overridden by any subclass that can be scanned for
+        implicit dependencies.
+        """
         return []
 
+    def get_implicit_deps(self, env, scanner, target):
+        """Return a list of implicit dependencies for this node.
+
+        This method exists to handle recursive invocation of the scanner
+        on the implicit dependencies returned by the scanner, if the
+        scanner's recursive flag says that we should.
+        """
+        if not scanner:
+            return []
+
+        try:
+            recurse = scanner.recursive
+        except AttributeError:
+            recurse = None
+
+        nodes = [self]
+        seen = {}
+        seen[self] = 1
+        deps = []
+        while nodes:
+           n = nodes.pop(0)
+           d = filter(lambda x, seen=seen: not seen.has_key(x),
+                      n.get_found_includes(env, scanner, target))
+           if d:
+               deps.extend(d)
+               for n in d:
+                   seen[n] = 1
+               if recurse:
+                   nodes.extend(d)
+
+        return deps
+
     def scan(self):
         """Scan this node's dependents for implicit dependencies."""
         # Don't bother scanning non-derived files, because we don't
diff --git a/src/engine/SCons/Scanner/C.py b/src/engine/SCons/Scanner/C.py
index cbcf1c6..b9f2d8f 100644
--- a/src/engine/SCons/Scanner/C.py
+++ b/src/engine/SCons/Scanner/C.py
@@ -45,11 +45,12 @@ include_re = re.compile('^[ \t]*#[ \t]*include[ \t]+(<|")([^>"]+)(>|")', re.M)
 def CScan(fs = SCons.Node.FS.default_fs):
     """Return a prototype Scanner instance for scanning source files
     that use the C pre-processor"""
-    cs = SCons.Scanner.Recursive(scan, "CScan", fs,
-                                 [".c", ".C", ".cxx", ".cpp", ".c++", ".cc",
-                                  ".h", ".H", ".hxx", ".hpp", ".hh",
-                                  ".F", ".fpp", ".FPP"],
-                                 path_function = path)
+    cs = SCons.Scanner.Current(scan, "CScan", fs,
+                               [".c", ".C", ".cxx", ".cpp", ".c++", ".cc",
+                                ".h", ".H", ".hxx", ".hpp", ".hh",
+                                ".F", ".fpp", ".FPP"],
+                               path_function = path,
+                               recursive = 1)
     return cs
 
 def path(env, dir, fs = SCons.Node.FS.default_fs):
diff --git a/src/engine/SCons/Scanner/CTests.py b/src/engine/SCons/Scanner/CTests.py
index f02474c..8f5a7dd 100644
--- a/src/engine/SCons/Scanner/CTests.py
+++ b/src/engine/SCons/Scanner/CTests.py
@@ -208,7 +208,7 @@ class CScannerTestCase1(unittest.TestCase):
         s = SCons.Scanner.C.CScan()
         path = s.path(env)
         deps = s(make_node('f1.cpp'), env, path)
-        headers = ['f1.h', 'f2.h', 'fi.h']
+        headers = ['f1.h', 'f2.h']
         deps_match(self, deps, map(test.workpath, headers))
 
 class CScannerTestCase2(unittest.TestCase):
@@ -258,7 +258,7 @@ class CScannerTestCase5(unittest.TestCase):
         assert n.rexists_called
         
         headers =  ['d1/f1.h', 'd1/f2.h', 'd1/f3-test.h',
-                    'f1.h', 'f2.h', 'f3-test.h', 'fi.h', 'fj.h']
+                    'f1.h', 'f2.h', 'f3-test.h']
         deps_match(self, deps, map(test.workpath, headers))
 
 class CScannerTestCase6(unittest.TestCase):
diff --git a/src/engine/SCons/Scanner/Fortran.py b/src/engine/SCons/Scanner/Fortran.py
index e23c7a5..034d5ac 100644
--- a/src/engine/SCons/Scanner/Fortran.py
+++ b/src/engine/SCons/Scanner/Fortran.py
@@ -45,9 +45,10 @@ include_re = re.compile("INCLUDE[ \t]+'([\\w./\\\\]+)'", re.M)
 def FortranScan(fs = SCons.Node.FS.default_fs):
     """Return a prototype Scanner instance for scanning source files
     for Fortran INCLUDE statements"""
-    scanner = SCons.Scanner.Recursive(scan, "FortranScan", fs,
-                                      [".f", ".F", ".for", ".FOR"],
-                                      path_function = path)
+    scanner = SCons.Scanner.Current(scan, "FortranScan", fs,
+                                    [".f", ".F", ".for", ".FOR"],
+                                    path_function = path,
+                                    recursive = 1)
     return scanner
 
 def path(env, dir, fs = SCons.Node.FS.default_fs):
diff --git a/src/engine/SCons/Scanner/FortranTests.py b/src/engine/SCons/Scanner/FortranTests.py
index f721d89..03165df 100644
--- a/src/engine/SCons/Scanner/FortranTests.py
+++ b/src/engine/SCons/Scanner/FortranTests.py
@@ -92,6 +92,15 @@ test.write('fff4.f',"""
 test.write('include/f4.f', "\n")
 test.write('subdir/include/f4.f', "\n")
 
+test.write('fff5.f',"""
+      PROGRAM FOO
+      INCLUDE 'f5.f'
+      INCLUDE 'not_there.f'
+      STOP
+      END
+""")
+
+test.write('f5.f', "\n")
 
 test.subdir('repository', ['repository', 'include'],
             [ 'repository', 'src' ])
@@ -173,7 +182,7 @@ class FortranScannerTestCase1(unittest.TestCase):
         path = s.path(env)
         fs = SCons.Node.FS.FS(original)
         deps = s(make_node('fff1.f', fs), env, path)
-        headers = ['f1.f', 'f2.f', 'fi.f']
+        headers = ['f1.f', 'f2.f']
         deps_match(self, deps, map(test.workpath, headers))
         test.unlink('f1.f')
         test.unlink('f2.f')
@@ -187,7 +196,7 @@ class FortranScannerTestCase2(unittest.TestCase):
         path = s.path(env)
         fs = SCons.Node.FS.FS(original)
         deps = s(make_node('fff1.f', fs), env, path)
-        headers = ['f1.f', 'f2.f', 'fi.f']
+        headers = ['f1.f', 'f2.f']
         deps_match(self, deps, map(test.workpath, headers))
         test.unlink('f1.f')
         test.unlink('f2.f')
@@ -309,18 +318,16 @@ class FortranScannerTestCase11(unittest.TestCase):
         to = TestOut()
         to.out = None
         SCons.Warnings._warningOut = to
-        test.write('f4.f',"      INCLUDE 'not_there.f'\n")
         fs = SCons.Node.FS.FS(test.workpath(''))
         env = DummyEnvironment([])
         s = SCons.Scanner.Fortran.FortranScan(fs=fs)
         path = s.path(env)
-        deps = s(fs.File('fff4.f'), env, path)
+        deps = s(fs.File('fff5.f'), env, path)
 
         # Did we catch the warning from not finding not_there.f?
         assert to.out
         
-        deps_match(self, deps, [ 'f4.f' ])
-        test.unlink('f4.f')
+        deps_match(self, deps, [ 'f5.f' ])
 
 class FortranScannerTestCase12(unittest.TestCase):
     def runTest(self):
diff --git a/src/engine/SCons/Scanner/ScannerTests.py b/src/engine/SCons/Scanner/ScannerTests.py
index 7280c2f..431e7ae 100644
--- a/src/engine/SCons/Scanner/ScannerTests.py
+++ b/src/engine/SCons/Scanner/ScannerTests.py
@@ -122,7 +122,7 @@ class ScannerHashTestCase(ScannerTestBase, unittest.TestCase):
                         "did not hash Scanner base class as expected")
 
 class ScannerCheckTestCase(unittest.TestCase):
-    "Test the Scanner.Base class __hash__() method"
+    "Test the Scanner.Base class scan_check method"
     def setUp(self):
         self.checked = {}
     def runTest(self):
@@ -138,6 +138,67 @@ class ScannerCheckTestCase(unittest.TestCase):
         self.failUnless(self.checked['x'] == 1,
                         "did not call check function")
 
+class ScannerRecursiveTestCase(ScannerTestBase, unittest.TestCase):
+    "Test the Scanner.Base class recursive flag"
+    def runTest(self):
+        s = SCons.Scanner.Base(function = self.func)
+        self.failUnless(s.recursive == None,
+                        "incorrect default recursive value")
+        s = SCons.Scanner.Base(function = self.func, recursive = None)
+        self.failUnless(s.recursive == None,
+                        "did not set recursive flag to None")
+        s = SCons.Scanner.Base(function = self.func, recursive = 1)
+        self.failUnless(s.recursive == 1,
+                        "did not set recursive flag to 1")
+
+class CurrentTestCase(ScannerTestBase, unittest.TestCase):
+    "Test the Scanner.Current class"
+    def runTest(self):
+        class MyNode:
+            def __init__(self):
+                self.called_has_builder = None
+                self.called_current = None
+                self.func_called = None
+        class HasNoBuilder(MyNode):
+            def has_builder(self):
+                self.called_has_builder = 1
+                return None
+        class IsNotCurrent(MyNode):
+            def has_builder(self):
+                self.called_has_builder = 1
+                return 1
+            def current(self, sig):
+                self.called_current = 1
+                return None
+        class IsCurrent(MyNode):
+            def has_builder(self):
+                self.called_has_builder = 1
+                return 1
+            def current(self, sig):
+                self.called_current = 1
+                return 1
+        def func(node, env, path):
+            node.func_called = 1
+            return []
+        env = DummyEnvironment()
+        s = SCons.Scanner.Current(func)
+        path = s.path(env)
+        hnb = HasNoBuilder()
+        s(hnb, env, path)
+        self.failUnless(hnb.called_has_builder, "did not call has_builder()")
+        self.failUnless(not hnb.called_current, "did call current()")
+        self.failUnless(hnb.func_called, "did not call func()")
+        inc = IsNotCurrent()
+        s(inc, env, path)
+        self.failUnless(inc.called_has_builder, "did not call has_builder()")
+        self.failUnless(inc.called_current, "did not call current()")
+        self.failUnless(not inc.func_called, "did call func()")
+        ic = IsCurrent()
+        s(ic, env, path)
+        self.failUnless(ic.called_has_builder, "did not call has_builder()")
+        self.failUnless(ic.called_current, "did not call current()")
+        self.failUnless(ic.func_called, "did not call func()")
+
 def suite():
     suite = unittest.TestSuite()
     suite.addTest(ScannerPositionalTestCase())
@@ -146,6 +207,8 @@ def suite():
     suite.addTest(ScannerKeywordArgumentTestCase())
     suite.addTest(ScannerHashTestCase())
     suite.addTest(ScannerCheckTestCase())
+    suite.addTest(ScannerRecursiveTestCase())
+    suite.addTest(CurrentTestCase())
     return suite
 
 if __name__ == "__main__":
diff --git a/src/engine/SCons/Scanner/__init__.py b/src/engine/SCons/Scanner/__init__.py
index c27c762..cd157af 100644
--- a/src/engine/SCons/Scanner/__init__.py
+++ b/src/engine/SCons/Scanner/__init__.py
@@ -31,6 +31,7 @@ __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__"
 
 
 import SCons.Node.FS
+import SCons.Sig
 import SCons.Util
 
 
@@ -55,7 +56,8 @@ class Base:
                  path_function = None,
                  node_class = SCons.Node.FS.Entry,
                  node_factory = SCons.Node.FS.default_fs.File,
-                 scan_check = None):
+                 scan_check = None,
+                 recursive = None):
         """
         Construct a new scanner object given a scanner function.
 
@@ -88,6 +90,10 @@ class Base:
         'scan_check' - a function to be called to first check whether
         this node really needs to be scanned.
 
+        'recursive' - specifies that this scanner should be invoked
+        recursively on the implicit dependencies it returns (the
+        canonical example being #include lines in C source files).
+
         The scanner function's first argument will be the name of a file
         that should be scanned for dependencies, the second argument will
         be an Environment object, the third argument will be the value
@@ -117,6 +123,7 @@ class Base:
         self.node_class = node_class
         self.node_factory = node_factory
         self.scan_check = scan_check
+        self.recursive = recursive
 
     def path(self, env, dir = None):
         if not self.path_function:
@@ -160,43 +167,16 @@ class Base:
         """Add a skey to the list of skeys"""
         self.skeys.append(skey)
 
-class RExists(Base):
+class Current(Base):
     """
-    Scan a node only if it exists (locally or in a Repository).
+    A class for scanning files that are source files (have no builder)
+    or are derived files and are current (which implies that they exist,
+    either locally or in a repository).
     """
+
     def __init__(self, *args, **kw):
-        def rexists_check(node):
-            return node.rexists()
-        kw['scan_check'] = rexists_check
+        def current_check(node):
+            c = not node.has_builder() or node.current(SCons.Sig.default_calc)
+            return c
+        kw['scan_check'] = current_check
         apply(Base.__init__, (self,) + args, kw)
-
-class Recursive(RExists):
-    """
-    The class for recursive dependency scanning.  This will
-    re-scan any new files returned by each call to the
-    underlying scanning function, and return the aggregate
-    list of all dependencies.
-    """
-
-    def __call__(self, node, env, path = ()):
-        """
-        This method does the actual scanning. 'node' is the node
-        that will be passed to the scanner function, and 'env' is the
-        environment that will be passed to the scanner function. An
-        aggregate list of dependency nodes for the specified filename
-        and any of its scanned dependencies will be returned.
-        """
-
-        nodes = [node]
-        seen = {node : 0}
-        deps = []
-        while nodes:
-            n = nodes.pop(0)
-            d = filter(lambda x, seen=seen: not seen.has_key(x),
-                       Base.__call__(self, n, env, path))
-            if d:
-                deps.extend(d)
-                nodes.extend(d)
-                for n in d:
-                    seen[n] = 0
-        return deps