Reduce the number of scanner calls in large cross-products of targets and sources.

5 files changed, 63 insertions, 18 deletions

diff --git a/src/engine/SCons/Executor.py b/src/engine/SCons/Executor.py
index 1d7a1073..c58f82ef 100644
--- a/src/engine/SCons/Executor.py
+++ b/src/engine/SCons/Executor.py
@@ -150,6 +150,32 @@ class Executor:
         """
         return 0
 
+    def scan(self, scanner):
+        """Scan this Executor's source files for implicit dependencies
+        and update all of the targets with them.  This essentially
+        short-circuits an N^2 scan of the sources for each individual
+        targets, which is a hell of a lot more efficient.
+        """
+        env = self.get_build_env()
+        select_specific_scanner = lambda t: (t[0], t[1].select(t[0]))
+        remove_null_scanners = lambda t: not t[1] is None
+        add_scanner_path = lambda t, s=self: (t[0], t[1], s.get_build_scanner_path(t[1]))
+        if scanner:
+            initial_scanners = lambda src, s=scanner: (src, s)
+        else:
+            initial_scanners = lambda src, e=env: (src, e.get_scanner(src.scanner_key()))
+        scanner_list = map(initial_scanners, self.sources)
+        scanner_list = filter(remove_null_scanners, scanner_list)
+        scanner_list = map(select_specific_scanner, scanner_list)
+        scanner_list = filter(remove_null_scanners, scanner_list)
+        scanner_path_list = map(add_scanner_path, scanner_list)
+        deps = []
+        for src, scanner, path in scanner_path_list:
+            deps.extend(src.get_implicit_deps(env, scanner, path))
+
+        for tgt in self.targets:
+            tgt.add_to_implicit(deps)
+
 if not SCons.Memoize.has_metaclass:
     _Base = Executor
     class Executor(SCons.Memoize.Memoizer, _Base):
diff --git a/src/engine/SCons/ExecutorTests.py b/src/engine/SCons/ExecutorTests.py
index b503a74b..555d485e 100644
--- a/src/engine/SCons/ExecutorTests.py
+++ b/src/engine/SCons/ExecutorTests.py
@@ -63,6 +63,7 @@ class MyBuilder:
 class MyNode:
     def __init__(self, name=None, pre=[], post=[]):
         self.name = name
+        self.implicit = []
         self.pre_actions = pre
         self.post_actions = post
     def __str__(self):
@@ -76,13 +77,16 @@ class MyNode:
                                            [self],
                                            ['s1', 's2'])
         apply(executor, (self, errfunc), {})
+    def get_implicit_deps(self, env, scanner, path):
+        return ['dep-' + str(self)]
+    def add_to_implicit(self, deps):
+        self.implicit.extend(deps)
 
 class MyScanner:
-    def path(self, env, dir, target, source):
-        target = map(str, target)
-        source = map(str, source)
-        return "scanner: %s, %s, %s, %s" % (env['SCANNERVAL'], dir, target, source)
-        
+    def path(self, env, cwd, target, source):
+        return ()
+    def select(self, node):
+        return self
 
 class ExecutorTestCase(unittest.TestCase):
 
@@ -143,7 +147,12 @@ class ExecutorTestCase(unittest.TestCase):
                                     [t],
                                     ['s1', 's2'])
 
-        s = MyScanner()
+        class LocalScanner:
+            def path(self, env, dir, target, source):
+                target = map(str, target)
+                source = map(str, source)
+                return "scanner: %s, %s, %s, %s" % (env['SCANNERVAL'], dir, target, source)
+        s = LocalScanner()
 
         p = x.get_build_scanner_path(s)
         assert p == "scanner: sss, here, ['t'], ['s1', 's2']", p
@@ -276,6 +285,16 @@ class ExecutorTestCase(unittest.TestCase):
         ts = x.get_timestamp()
         assert ts == 0, ts
 
+    def test_scan(self):
+        """Test scanning the sources for implicit dependencies"""
+        env = MyEnvironment(S='string', SCANNERVAL='scn')
+        targets = [MyNode('t')]
+        sources = [MyNode('s1'), MyNode('s2')]
+        x = SCons.Executor.Executor('b', env, [{}], targets, sources)
+        scanner = MyScanner()
+        deps = x.scan(scanner)
+        assert targets[0].implicit == ['dep-s1', 'dep-s2'], targets[0].implicit
+
 
 if __name__ == "__main__":
     suite = unittest.TestSuite()
diff --git a/src/engine/SCons/Node/FSTests.py b/src/engine/SCons/Node/FSTests.py
index 1a3236ee..5018f991 100644
--- a/src/engine/SCons/Node/FSTests.py
+++ b/src/engine/SCons/Node/FSTests.py
@@ -94,6 +94,7 @@ class Builder:
         self.overrides = {}
         self.action = action
         self.target_scanner = None
+        self.source_scanner = None
 
     def targets(self, t):
         return [t]
diff --git a/src/engine/SCons/Node/NodeTests.py b/src/engine/SCons/Node/NodeTests.py
index 7d737bec..4424e610 100644
--- a/src/engine/SCons/Node/NodeTests.py
+++ b/src/engine/SCons/Node/NodeTests.py
@@ -128,6 +128,8 @@ class Builder:
         self.action = MyAction()
         self.source_factory = MyNode
         self.is_explicit = is_explicit
+        self.target_scanner = None
+        self.source_scanner = None
     def targets(self, t):
         return [t]
     def get_actions(self):
diff --git a/src/engine/SCons/Node/__init__.py b/src/engine/SCons/Node/__init__.py
index 06cb5bfe..93a65377 100644
--- a/src/engine/SCons/Node/__init__.py
+++ b/src/engine/SCons/Node/__init__.py
@@ -467,6 +467,13 @@ class Node:
             scanner = scanner.select(node)
         return scanner
 
+    def add_to_implicit(self, deps):
+        if not hasattr(self, 'implicit') or self.implicit is None:
+            self.implicit = []
+            self.implicit_dict = {}
+            self._children_reset()
+        self._add_child(self.implicit, self.implicit_dict, deps)
+
     def scan(self):
         """Scan this node's dependents for implicit dependencies."""
         # Don't bother scanning non-derived files, because we don't
@@ -500,18 +507,8 @@ class Node:
                     self._children_reset()
                     self.del_binfo()
 
-        # Potential optimization for the N^2 problem if we can tie
-        # scanning to the Executor in some way so that we can scan
-        # source files onces and then spread the implicit dependencies
-        # to all of the targets at once.
-        #kids = self.children(scan=0)
-        #for child in filter(lambda n: n.implicit is None, kids):
-        for child in self.children(scan=0):
-            scanner = self.get_source_scanner(child)
-            if scanner:
-                path = self.get_build_scanner_path(scanner)
-                deps = child.get_implicit_deps(build_env, scanner, path)
-                self._add_child(self.implicit, self.implicit_dict, deps)
+        scanner = self.builder.source_scanner
+        self.get_executor().scan(scanner)
 
         # scan this node itself for implicit dependencies
         scanner = self.builder.target_scanner