Eliminate unnecessary scanning before a Node is rebuilt.

4 files changed, 157 insertions, 48 deletions

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