Regain lost performance improvements by using paths instead of targets for scanner calls and re-using Binder objects for identical paths.

15 files changed, 145 insertions, 81 deletions

diff --git a/src/engine/SCons/BuilderTests.py b/src/engine/SCons/BuilderTests.py
index 005f3de..0d9c2ec 100644
--- a/src/engine/SCons/BuilderTests.py
+++ b/src/engine/SCons/BuilderTests.py
@@ -933,6 +933,8 @@ class BuilderTestCase(unittest.TestCase):
                  return 'TestScannerkey'
             def instance(self, env):
                  return self
+            def select(self, node):
+                 return self
             name = 'TestScanner'
             def __str__(self):
                 return self.name
@@ -962,7 +964,7 @@ class BuilderTestCase(unittest.TestCase):
             name = 'EnvTestScanner'
             def __str__(self):
                 return self.name
-            def select(self, scanner):
+            def select(self, node):
                 return self
             def path(self, env, dir=None):
                 return ()
diff --git a/src/engine/SCons/Environment.py b/src/engine/SCons/Environment.py
index c2d2e92..fdd9b40 100644
--- a/src/engine/SCons/Environment.py
+++ b/src/engine/SCons/Environment.py
@@ -372,7 +372,7 @@ class SubstitutionEnvironment:
         lvars['__env__'] = self
         return SCons.Util.scons_subst_list(string, self, raw, target, source, gvars, lvars, conv)
 
-    def subst_path(self, path, target=None):
+    def subst_path(self, path, target=None, source=None):
         """Substitute a path list, turning EntryProxies into Nodes
         and leaving Nodes (and other objects) as-is."""
 
@@ -397,7 +397,7 @@ class SubstitutionEnvironment:
         r = []
         for p in path:
             if SCons.Util.is_String(p):
-                p = self.subst(p, target=target, conv=s)
+                p = self.subst(p, target=target, source=source, conv=s)
                 if SCons.Util.is_List(p):
                     if len(p) == 1:
                         p = p[0]
diff --git a/src/engine/SCons/EnvironmentTests.py b/src/engine/SCons/EnvironmentTests.py
index 44dc814..3ef5e73 100644
--- a/src/engine/SCons/EnvironmentTests.py
+++ b/src/engine/SCons/EnvironmentTests.py
@@ -503,11 +503,14 @@ class SubstitutionTestCase(unittest.TestCase):
         r = env.subst_path(['$FOO', 'xxx', '$BAR'])
         assert r == ['foo', 'xxx', 'bar'], r
 
-        r = env.subst_path(['$FOO', '$TARGET', '$BAR'])
-        assert r == ['foo', '', 'bar'], r
+        r = env.subst_path(['$FOO', '$TARGET', '$SOURCE', '$BAR'])
+        assert r == ['foo', '', '', 'bar'], r
 
-        r = env.subst_path(['$FOO', '$TARGET', '$BAR'], target=MyNode('yyy'))
-        assert map(str, r) == ['foo', 'yyy', 'bar'], r
+        r = env.subst_path(['$FOO', '$TARGET', '$BAR'], target=MyNode('ttt'))
+        assert map(str, r) == ['foo', 'ttt', 'bar'], r
+
+        r = env.subst_path(['$FOO', '$SOURCE', '$BAR'], source=MyNode('sss'))
+        assert map(str, r) == ['foo', 'sss', 'bar'], r
 
         n = MyObj()
 
diff --git a/src/engine/SCons/Executor.py b/src/engine/SCons/Executor.py
index 7bc847a..1d7a107 100644
--- a/src/engine/SCons/Executor.py
+++ b/src/engine/SCons/Executor.py
@@ -77,6 +77,17 @@ class Executor:
 
         return build_env
 
+    def get_build_scanner_path(self, scanner):
+        """
+        __cacheable__
+        """
+        env = self.get_build_env()
+        try:
+            cwd = self.targets[0].cwd
+        except (IndexError, AttributeError):
+            cwd = None
+        return scanner.path(env, cwd, self.targets, self.sources)
+
     def do_nothing(self, target, errfunc, kw):
         pass
 
diff --git a/src/engine/SCons/ExecutorTests.py b/src/engine/SCons/ExecutorTests.py
index d5b6dd2..b503a74 100644
--- a/src/engine/SCons/ExecutorTests.py
+++ b/src/engine/SCons/ExecutorTests.py
@@ -61,9 +61,12 @@ class MyBuilder:
         self.action = MyAction()
 
 class MyNode:
-    def __init__(self, pre, post):
+    def __init__(self, name=None, pre=[], post=[]):
+        self.name = name
         self.pre_actions = pre
         self.post_actions = post
+    def __str__(self):
+        return self.name
     def build(self, errfunc=None):
         executor = SCons.Executor.Executor(MyAction(self.pre_actions +
                                                     [self.builder.action] +
@@ -73,6 +76,12 @@ class MyNode:
                                            [self],
                                            ['s1', 's2'])
         apply(executor, (self, errfunc), {})
+
+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)
         
 
 class ExecutorTestCase(unittest.TestCase):
@@ -124,6 +133,21 @@ class ExecutorTestCase(unittest.TestCase):
         assert be['O'] == 'ob3', be['O']
         assert be['Y'] == 'yyy', be['Y']
 
+    def test_get_build_scanner_path(self):
+        """Test fetching the path for the specified scanner."""
+        t = MyNode('t')
+        t.cwd = 'here'
+        x = SCons.Executor.Executor(MyAction(),
+                                    MyEnvironment(SCANNERVAL='sss'),
+                                    [],
+                                    [t],
+                                    ['s1', 's2'])
+
+        s = MyScanner()
+
+        p = x.get_build_scanner_path(s)
+        assert p == "scanner: sss, here, ['t'], ['s1', 's2']", p
+
     def test__call__(self):
         """Test calling an Executor"""
         result = []
@@ -140,7 +164,7 @@ class ExecutorTestCase(unittest.TestCase):
         a = MyAction([action1, action2])
         b = MyBuilder(env, {})
         b.action = a
-        n = MyNode([pre], [post])
+        n = MyNode('n', [pre], [post])
         n.builder = b
         n.build()
         assert result == ['pre', 'action1', 'action2', 'post'], result
@@ -152,7 +176,7 @@ class ExecutorTestCase(unittest.TestCase):
                 errfunc(1)
             return 1
 
-        n = MyNode([pre_err], [post])
+        n = MyNode('n', [pre_err], [post])
         n.builder = b
         n.build()
         assert result == ['pre_err', 'action1', 'action2', 'post'], result
@@ -219,7 +243,7 @@ class ExecutorTestCase(unittest.TestCase):
         a = MyAction([action1])
         x = SCons.Executor.Executor(a, env, [], ['t1', 't2'], ['s1', 's2'])
 
-        x(MyNode([], []), None)
+        x(MyNode('', [], []), None)
         assert result == ['action1'], result
         s = str(x)
         assert s[:10] == 'GENSTRING ', s
@@ -228,7 +252,7 @@ class ExecutorTestCase(unittest.TestCase):
         x.nullify()
 
         assert result == [], result
-        x(MyNode([], []), None)
+        x(MyNode('', [], []), None)
         assert result == [], result
         s = str(x)
         assert s == '', s
diff --git a/src/engine/SCons/Node/FS.py b/src/engine/SCons/Node/FS.py
index 50e3818..789d5c3 100644
--- a/src/engine/SCons/Node/FS.py
+++ b/src/engine/SCons/Node/FS.py
@@ -612,11 +612,11 @@ class Entry(Base):
         self.clear()
         return File.rfile(self)
 
-    def get_found_includes(self, env, scanner, target):
+    def get_found_includes(self, env, scanner, path):
         """If we're looking for included files, it's because this Entry
         is really supposed to be a File itself."""
         node = self.rfile()
-        return node.get_found_includes(env, scanner, target)
+        return node.get_found_includes(env, scanner, path)
 
     def scanner_key(self):
         return self.get_suffix()
@@ -1456,29 +1456,13 @@ class File(Base):
         except AttributeError:
             return None
 
-    def get_found_includes(self, env, scanner, target):
+    def get_found_includes(self, env, scanner, path):
         """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."""
+        Cache results so we only scan the file once per path
+        regardless of how many times this information is requested.
+        __cacheable__"""
         if not scanner:
             return []
-
-        try:
-            path = target.scanner_paths[scanner]
-        except AttributeError:
-            # The target had no scanner_paths attribute, which means
-            # it's an Alias or some other node that's not actually a
-            # file.  In that case, back off and use the path for this
-            # node itself.
-            try:
-                path = self.scanner_paths[scanner]
-            except KeyError:
-                path = scanner.path(env, self.cwd, target)
-                self.scanner_paths[scanner] = path
-        except KeyError:
-            path = scanner.path(env, target.cwd, target)
-            target.scanner_paths[scanner] = path
-
         return scanner(self, env, path)
 
     def _createDir(self):
diff --git a/src/engine/SCons/Node/FSTests.py b/src/engine/SCons/Node/FSTests.py
index e65c10b..1a3236e 100644
--- a/src/engine/SCons/Node/FSTests.py
+++ b/src/engine/SCons/Node/FSTests.py
@@ -54,7 +54,7 @@ class Scanner:
         scanner_count = scanner_count + 1
         self.hash = scanner_count
         self.node = node
-    def path(self, env, dir, target=None):
+    def path(self, env, dir, target=None, source=None):
         return ()
     def __call__(self, node, env, path):
         return [self.node]
diff --git a/src/engine/SCons/Node/NodeTests.py b/src/engine/SCons/Node/NodeTests.py
index 3e5a9f0..f801963 100644
--- a/src/engine/SCons/Node/NodeTests.py
+++ b/src/engine/SCons/Node/NodeTests.py
@@ -169,6 +169,8 @@ class Scanner:
     def __call__(self, node):
         self.called = 1
         return node.found_includes
+    def path(self, env, dir, target=None, source=None):
+        return ()
     def select(self, node):
         return self
 
@@ -309,8 +311,19 @@ class NodeTestCase(unittest.TestCase):
             assert str(act.built_target[0]) == "xxx", str(act.built_target[0])
             assert act.built_source == ["yyy", "zzz"], act.built_source
 
+    def test_get_build_scanner_path(self):
+        """Test the get_build_scanner_path() method"""
+        n = SCons.Node.Node()
+        class MyExecutor:
+            def get_build_scanner_path(self, scanner):
+                return 'executor would call %s' % scanner
+        x = MyExecutor()
+        n.set_executor(x)
+        p = n.get_build_scanner_path('fake_scanner')
+        assert p == "executor would call fake_scanner", p
+
     def test_get_executor(self):
-        """Test the reset_executor() method"""
+        """Test the get_executor() method"""
         n = SCons.Node.Node()
 
         try:
@@ -337,7 +350,7 @@ class NodeTestCase(unittest.TestCase):
         assert x.env == 'env2', x.env
 
     def test_set_executor(self):
-        """Test the reset_executor() method"""
+        """Test the set_executor() method"""
         n = SCons.Node.Node()
         n.set_executor(1)
         assert n.executor == 1, n.executor
diff --git a/src/engine/SCons/Node/__init__.py b/src/engine/SCons/Node/__init__.py
index 7ffec0e..c20d657 100644
--- a/src/engine/SCons/Node/__init__.py
+++ b/src/engine/SCons/Node/__init__.py
@@ -148,6 +148,11 @@ class Node:
         __cacheable__"""
         return self.get_executor().get_build_env()
 
+    def get_build_scanner_path(self, scanner):
+        """Fetch the appropriate Environment to build this node.
+        __cacheable__"""
+        return self.get_executor().get_build_scanner_path(scanner)
+
     def set_executor(self, executor):
         """Set the action executor for this node."""
         self.executor = executor
@@ -315,8 +320,7 @@ class Node:
         This allows an internal Builder created by SCons to be marked
         non-explicit, so that it can be overridden by an explicit
         builder that the user supplies (the canonical example being
-        directories).
-        __cacheable__"""
+        directories)."""
         return self.has_builder() and self.builder.is_explicit
 
     def get_builder(self, default_builder=None):
@@ -354,7 +358,7 @@ class Node:
         """
         return [], None
 
-    def get_found_includes(self, env, scanner, target):
+    def get_found_includes(self, env, scanner, path):
         """Return the scanned include lines (implicit dependencies)
         found in this node.
 
@@ -364,7 +368,7 @@ class Node:
         """
         return []
 
-    def get_implicit_deps(self, env, scanner, target):
+    def get_implicit_deps(self, env, scanner, path):
         """Return a list of implicit dependencies for this node.
 
         This method exists to handle recursive invocation of the scanner
@@ -390,7 +394,7 @@ class Node:
         while nodes:
            n = nodes.pop(0)
            d = filter(lambda x, seen=seen: not seen.has_key(x),
-                      n.get_found_includes(env, scanner, target))
+                      n.get_found_includes(env, scanner, path))
            if d:
                deps.extend(d)
                for n in d:
@@ -421,7 +425,6 @@ class Node:
 
         This function may be called very often; it attempts to cache
         the scanner found to improve performance.
-        __cacheable__
         """
         # Called from scan() for each child (node) of this node
         # (self).  The scan() may be called multiple times, so this
@@ -434,10 +437,9 @@ class Node:
         if not self.has_builder():
             return None
         
+        scanner = None
         try:
             scanner = self.builder.source_scanner
-            if scanner:
-                return scanner
         except AttributeError:
             pass
 
@@ -445,7 +447,10 @@ class Node:
         # based on the node's scanner key (usually the file
         # extension).
         
-        scanner = self.get_build_env().get_scanner(node.scanner_key())
+        if not scanner:
+            scanner = self.get_build_env().get_scanner(node.scanner_key())
+        if scanner:
+            scanner = scanner.select(node)
         return scanner
 
     def scan(self):
@@ -481,16 +486,24 @@ 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:
-                deps = child.get_implicit_deps(build_env, scanner, self)
+                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)
 
         # scan this node itself for implicit dependencies
         scanner = self.builder.target_scanner
         if scanner:
-            deps = self.get_implicit_deps(build_env, scanner, self)
+            path = self.get_build_scanner_path(scanner)
+            deps = self.get_implicit_deps(build_env, scanner, path)
             self._add_child(self.implicit, self.implicit_dict, deps)
 
         # XXX See note above re: --implicit-cache.
@@ -836,8 +849,9 @@ class Node:
             env = self.get_build_env()
             for s in self.sources:
                 scanner = self.get_source_scanner(s)
-                def f(node, env=env, scanner=scanner, target=self):
-                    return node.get_found_includes(env, scanner, target)
+                path = self.get_build_scanner_path(scanner)
+                def f(node, env=env, scanner=scanner, path=path):
+                    return node.get_found_includes(env, scanner, path)
                 return SCons.Util.render_tree(s, f, 1)
         else:
             return None
diff --git a/src/engine/SCons/Scanner/CTests.py b/src/engine/SCons/Scanner/CTests.py
index e3caa5f..4c21fe9 100644
--- a/src/engine/SCons/Scanner/CTests.py
+++ b/src/engine/SCons/Scanner/CTests.py
@@ -188,7 +188,7 @@ class DummyEnvironment(UserDict.UserDict):
             return [self.data[strSubst[1:]]]
         return [[strSubst]]
 
-    def subst_path(self, path, target=None):
+    def subst_path(self, path, target=None, source=None):
         if type(path) != type([]):
             path = [path]
         return map(self.subst, path)
diff --git a/src/engine/SCons/Scanner/FortranTests.py b/src/engine/SCons/Scanner/FortranTests.py
index 75264ac..4c82522 100644
--- a/src/engine/SCons/Scanner/FortranTests.py
+++ b/src/engine/SCons/Scanner/FortranTests.py
@@ -236,7 +236,7 @@ class DummyEnvironment:
             return self[arg[1:]]
         return arg
 
-    def subst_path(self, path, target=None):
+    def subst_path(self, path, target=None, source=None):
         if type(path) != type([]):
             path = [path]
         return map(self.subst, path)
diff --git a/src/engine/SCons/Scanner/IDLTests.py b/src/engine/SCons/Scanner/IDLTests.py
index 31a40ea..db842c3 100644
--- a/src/engine/SCons/Scanner/IDLTests.py
+++ b/src/engine/SCons/Scanner/IDLTests.py
@@ -201,7 +201,7 @@ class DummyEnvironment:
     def subst(self, arg):
         return arg
 
-    def subst_path(self, path, target=None):
+    def subst_path(self, path, target=None, source=None):
         if type(path) != type([]):
             path = [path]
         return map(self.subst, path)
diff --git a/src/engine/SCons/Scanner/ProgTests.py b/src/engine/SCons/Scanner/ProgTests.py
index 7e33866..c31b392 100644
--- a/src/engine/SCons/Scanner/ProgTests.py
+++ b/src/engine/SCons/Scanner/ProgTests.py
@@ -78,7 +78,7 @@ class DummyEnvironment:
             return ''
         return s
 
-    def subst_path(self, path, target=None):
+    def subst_path(self, path, target=None, source=None):
         if type(path) != type([]):
             path = [path]
         return map(self.subst, path)
diff --git a/src/engine/SCons/Scanner/ScannerTests.py b/src/engine/SCons/Scanner/ScannerTests.py
index 493a330..c38dc84 100644
--- a/src/engine/SCons/Scanner/ScannerTests.py
+++ b/src/engine/SCons/Scanner/ScannerTests.py
@@ -42,7 +42,7 @@ class DummyEnvironment(UserDict.UserDict):
         if strSubst[0] == '$':
             return [self.data[strSubst[1:]]]
         return [[strSubst]]
-    def subst_path(self, path, target=None):
+    def subst_path(self, path, target=None, source=None):
         if type(path) != type([]):
             path = [path]
         return map(self.subst, path)
@@ -124,6 +124,25 @@ class BaseTestCase(unittest.TestCase):
         else:
             self.failIf(hasattr(self, "arg"), "an argument was given when it shouldn't have been")
 
+    def test_path(self):
+        """Test the Scanner.Base path() method"""
+        def pf(env, cwd, target, source, argument=None):
+            return "pf: %s %s %s %s %s" % \
+                        (env.VARIABLE, cwd, target[0], source[0], argument)
+
+        env = DummyEnvironment()
+        env.VARIABLE = 'v1'
+        target = DummyNode('target')
+        source = DummyNode('source')
+
+        s = SCons.Scanner.Base(self.func, path_function=pf)
+        p = s.path(env, 'here', [target], [source])
+        assert p == "pf: v1 here target source None", p
+
+        s = SCons.Scanner.Base(self.func, path_function=pf, argument="xyz")
+        p = s.path(env, 'here', [target], [source])
+        assert p == "pf: v1 here target source xyz", p
+
     def test_positional(self):
         """Test the Scanner.Base class using positional arguments"""
         s = SCons.Scanner.Base(self.func, "Pos")
diff --git a/src/engine/SCons/Scanner/__init__.py b/src/engine/SCons/Scanner/__init__.py
index 1322fff..c7cf382 100644
--- a/src/engine/SCons/Scanner/__init__.py
+++ b/src/engine/SCons/Scanner/__init__.py
@@ -54,8 +54,7 @@ def Scanner(function, *args, **kw):
         return apply(Base, (function,) + args, kw)
 
 
-class Binder:
-    __metaclass__ = SCons.Memoize.Memoized_Metaclass
+class _Binder:
     def __init__(self, bindval):
         self._val = bindval
     def __call__(self):
@@ -63,43 +62,39 @@ class Binder:
     def __str__(self):
         return str(self._val)
         #debug: return 'B<%s>'%str(self._val)
-    
+
+BinderDict = {}
+
+def Binder(path):
+    try:
+        return BinderDict[path]
+    except KeyError:
+        b = _Binder(path)
+        BinderDict[path] = b
+        return b
+
+
 class FindPathDirs:
     """A class to bind a specific *PATH variable name and the fs object
     to a function that will return all of the *path directories."""
-    __metaclass__ = SCons.Memoize.Memoized_Metaclass
     def __init__(self, variable, fs):
         self.variable = variable
         self.fs = fs
-    def __call__(self, env, dir, target=None, argument=None):
-        "__cacheable__"
+    def __call__(self, env, dir, target=None, source=None, argument=None):
+        # The goal is that we've made caching this unnecessary
+        # because the caching takes place at higher layers.
         try:
             path = env[self.variable]
         except KeyError:
             return ()
 
-        path = env.subst_path(path, target=target)
+        path = env.subst_path(path, target=target, source=source)
         path_tuple = tuple(self.fs.Rsearchall(path,
                                               must_exist = 0, #kwq!
                                               clazz = SCons.Node.FS.Dir,
                                               cwd = dir))
         return Binder(path_tuple)
 
-if not SCons.Memoize.has_metaclass:
-    _FPD_Base = FindPathDirs
-    class FindPathDirs(SCons.Memoize.Memoizer, _FPD_Base):
-        "Cache-backed version of FindPathDirs"
-        def __init__(self, *args, **kw):
-            apply(_FPD_Base.__init__, (self,)+args, kw)
-            SCons.Memoize.Memoizer.__init__(self)
-    _BinderBase = Binder
-    class Binder(SCons.Memoize.Memoizer, _BinderBase):
-        "Cache-backed version of Binder"
-        def __init__(self, *args, **kw):
-            apply(_BinderBase.__init__, (self,)+args, kw)
-            SCons.Memoize.Memoizer.__init__(self)
-
-
 class Base:
     """
     The base class for dependency scanners.  This implements
@@ -189,14 +184,13 @@ class Base:
         self.scan_check = scan_check
         self.recursive = recursive
 
-    def path(self, env, dir=None, target=None):
-        "__cacheable__"
+    def path(self, env, dir=None, target=None, source=None):
         if not self.path_function:
             return ()
         if not self.argument is _null:
-            return self.path_function(env, dir, target, self.argument)
+            return self.path_function(env, dir, target, source, self.argument)
         else:
-            return self.path_function(env, dir, target)
+            return self.path_function(env, dir, target, source)
 
     def __call__(self, node, env, path = ()):
         """