Use WeakValueDicts in the Memoizer to cut down on memory use.

5 files changed, 130 insertions, 51 deletions

diff --git a/src/CHANGES.txt b/src/CHANGES.txt
index b46af63..eafac2d 100644
--- a/src/CHANGES.txt
+++ b/src/CHANGES.txt
@@ -184,6 +184,9 @@ RELEASE 0.97 - XXX
   - Change --debug=memory output to line up the numbers and to better
     match (more or less) the headers on the --debug=count columns.
 
+  - Speed things up when there are lists of targets and/or sources by
+    getting rid of some N^2 walks of the lists involved.
+
   From Wayne Lee:
 
   - Avoid "maximum recursion limit" errors when removing $(-$) pairs
diff --git a/src/engine/SCons/Executor.py b/src/engine/SCons/Executor.py
index c58f82e..7965afe 100644
--- a/src/engine/SCons/Executor.py
+++ b/src/engine/SCons/Executor.py
@@ -176,6 +176,47 @@ class Executor:
         for tgt in self.targets:
             tgt.add_to_implicit(deps)
 
+    def get_missing_sources(self):
+        """
+        __cacheable__
+        """
+        return filter(lambda s: s.missing(), self.sources)
+
+    def get_source_binfo(self, calc):
+        """
+        __cacheable__
+        """
+        calc_signature = lambda node, calc=calc: node.calc_signature(calc)
+        return map(lambda s, c=calc_signature: (s, c(s), str(s)), self.sources)
+
+
+
+class Null:
+    """A null Executor, with a null build Environment, that does
+    nothing when the rest of the methods call it.
+
+    This might be able to disapper when we refactor things to
+    disassociate Builders from Nodes entirely, so we're not
+    going to worry about unit tests for this--at least for now.
+    """
+    def get_build_env(self):
+        class NullEnvironment:
+            def get_scanner(self, key):
+                return None
+        return NullEnvironment()
+    def get_build_scanner_path(self):
+        return None
+    def __call__(self, *args, **kw):
+        pass
+    def cleanup(self):
+        pass
+    def get_missing_sources(self):
+        return []
+    def get_source_binfo(self, calc):
+        return []
+
+
+
 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 555d485..189cbad 100644
--- a/src/engine/SCons/ExecutorTests.py
+++ b/src/engine/SCons/ExecutorTests.py
@@ -66,6 +66,7 @@ class MyNode:
         self.implicit = []
         self.pre_actions = pre
         self.post_actions = post
+        self.missing_val = None
     def __str__(self):
         return self.name
     def build(self, errfunc=None):
@@ -81,6 +82,10 @@ class MyNode:
         return ['dep-' + str(self)]
     def add_to_implicit(self, deps):
         self.implicit.extend(deps)
+    def missing(self):
+        return self.missing_val
+    def calc_signature(self, calc):
+        return 'cs-'+calc+'-'+self.name
 
 class MyScanner:
     def path(self, env, cwd, target, source):
@@ -287,7 +292,7 @@ class ExecutorTestCase(unittest.TestCase):
 
     def test_scan(self):
         """Test scanning the sources for implicit dependencies"""
-        env = MyEnvironment(S='string', SCANNERVAL='scn')
+        env = MyEnvironment(S='string')
         targets = [MyNode('t')]
         sources = [MyNode('s1'), MyNode('s2')]
         x = SCons.Executor.Executor('b', env, [{}], targets, sources)
@@ -295,6 +300,27 @@ class ExecutorTestCase(unittest.TestCase):
         deps = x.scan(scanner)
         assert targets[0].implicit == ['dep-s1', 'dep-s2'], targets[0].implicit
 
+    def test_get_missing_sources(self):
+        """Test the ability to check if any sources are missing"""
+        env = MyEnvironment()
+        targets = [MyNode('t')]
+        sources = [MyNode('s1'), MyNode('s2')]
+        x = SCons.Executor.Executor('b', env, [{}], targets, sources)
+        sources[0].missing_val = 1
+        missing = x.get_missing_sources()
+        assert missing == [sources[0]], missing
+
+    def test_get_source_binfo(self):
+        """Test fetching the build signature info for the sources"""
+        env = MyEnvironment()
+        targets = [MyNode('t')]
+        sources = [MyNode('s1'), MyNode('s2')]
+        x = SCons.Executor.Executor('b', env, [{}], targets, sources)
+        b = x.get_source_binfo('C')
+        assert b == [(sources[0], 'cs-C-s1', 's1'),
+                     (sources[1], 'cs-C-s2', 's2')], b
+
+
 
 if __name__ == "__main__":
     suite = unittest.TestSuite()
diff --git a/src/engine/SCons/Node/NodeTests.py b/src/engine/SCons/Node/NodeTests.py
index 4424e61..0637ceb 100644
--- a/src/engine/SCons/Node/NodeTests.py
+++ b/src/engine/SCons/Node/NodeTests.py
@@ -76,6 +76,12 @@ class MyAction(MyActionBase):
         self.order = built_order
         return 0
 
+class MyExecutor:
+    def get_build_scanner_path(self, scanner):
+        return 'executor would call %s' % scanner
+    def cleanup(self):
+        self.cleaned_up = 1
+
 class MyListAction(MyActionBase):
     def __init__(self, list):
         self.list = list
@@ -316,9 +322,6 @@ class NodeTestCase(unittest.TestCase):
     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')
@@ -357,6 +360,14 @@ class NodeTestCase(unittest.TestCase):
         n.set_executor(1)
         assert n.executor == 1, n.executor
 
+    def test_executor_cleanup(self):
+        """Test letting the executor cleanup its cache"""
+        n = SCons.Node.Node()
+        x = MyExecutor()
+        n.set_executor(x)
+        n.executor_cleanup()
+        assert x.cleaned_up
+
     def test_reset_executor(self):
         """Test the reset_executor() method"""
         n = SCons.Node.Node()
@@ -631,6 +642,8 @@ class NodeTestCase(unittest.TestCase):
 
     def test_prepare(self):
         """Test preparing a node to be built
+
+        By extension, this also tests the missing() method.
         """
         node = SCons.Node.Node()
 
@@ -1117,6 +1130,9 @@ class NodeTestCase(unittest.TestCase):
         n.implicit = 'testimplicit'
         n.waiting_parents = ['foo', 'bar']
 
+        x = MyExecutor()
+        n.set_executor(x)
+
         n.clear()
 
         assert not hasattr(n, 'binfo'), n.bsig
@@ -1124,6 +1140,7 @@ class NodeTestCase(unittest.TestCase):
         assert n.found_includes == {}, n.found_includes
         assert n.implicit is None, n.implicit
         assert n.waiting_parents == [], n.waiting_parents
+        assert x.cleaned_up
 
     def test_get_subst_proxy(self):
         """Test the get_subst_proxy method."""
diff --git a/src/engine/SCons/Node/__init__.py b/src/engine/SCons/Node/__init__.py
index 93a6537..6b4c996 100644
--- a/src/engine/SCons/Node/__init__.py
+++ b/src/engine/SCons/Node/__init__.py
@@ -169,26 +169,7 @@ class Node:
             try:
                 act = self.builder.action
             except AttributeError:
-                # If there's no builder or action, then return a created
-                # null Executor with a null build Environment that
-                # does nothing when the rest of the methods call it.
-                # We're keeping this here for now because this module is
-                # the only one using it, and because this whole thing
-                # may go away in the next step of refactoring this to
-                # disassociate Builders from Nodes entirely.
-                class NullExecutor:
-                    def get_build_env(self):
-                        class NullEnvironment:
-                            def get_scanner(self, key):
-                                return None
-                        return NullEnvironment()
-                    def get_build_scanner_path(self):
-                        return None
-                    def __call__(self, *args, **kw):
-                        pass
-                    def cleanup(self):
-                        pass
-                executor = NullExecutor()
+                executor = SCons.Executor.Null()
             else:
                 if self.pre_actions:
                     act = self.pre_actions + act
@@ -202,6 +183,15 @@ class Node:
             self.executor = executor
         return executor
 
+    def executor_cleanup(self):
+        """Let the executor clean up any cached information."""
+        try:
+            executor = self.get_executor(create=None)
+        except AttributeError:
+            pass
+        else:
+            executor.cleanup()
+
     def reset_executor(self):
         "Remove cached executor; forces recompute when needed."
         try:
@@ -276,12 +266,7 @@ class Node:
     def postprocess(self):
         """Clean up anything we don't need to hang onto after we've
         been built."""
-        try:
-            executor = self.get_executor(create=None)
-        except AttributeError:
-            pass
-        else:
-            executor.cleanup()
+        self.executor_cleanup()
 
     def clear(self):
         """Completely clear a Node of all its cached state (so that it
@@ -289,6 +274,7 @@ class Node:
         builds).
         __reset_cache__
         """
+        self.executor_cleanup()
         self.del_binfo()
         self.del_cinfo()
         try:
@@ -595,28 +581,31 @@ class Node:
         if scan:
             self.scan()
 
-        sources = self.filter_ignore(self.sources)
-        depends = self.filter_ignore(self.depends)
+        executor = self.get_executor()
+
+        sourcelist = executor.get_source_binfo(calc)
+
+        sourcelist = filter(lambda t, s=self: s.do_not_ignore(t[0]), sourcelist)
+        depends = filter(self.do_not_ignore, self.depends)
         if self.implicit is None:
             implicit = []
         else:
-            implicit = self.filter_ignore(self.implicit)
+            implicit = filter(self.do_not_ignore, self.implicit)
 
         def calc_signature(node, calc=calc):
             return node.calc_signature(calc)
-        sourcesigs = map(calc_signature, sources)
+        sourcesigs = map(lambda t: t[1], sourcelist)
         dependsigs = map(calc_signature, depends)
         implicitsigs = map(calc_signature, implicit)
 
         sigs = sourcesigs + dependsigs + implicitsigs
 
         if self.has_builder():
-            executor = self.get_executor()
             binfo.bact = str(executor)
             binfo.bactsig = calc.module.signature(executor)
             sigs.append(binfo.bactsig)
 
-        binfo.bsources = map(str, sources)
+        binfo.bsources = map(lambda t: t[2], sourcelist)
         binfo.bdepends = map(str, depends)
         binfo.bimplicit = map(str, implicit)
 
@@ -677,18 +666,24 @@ class Node:
         """Does this node exist locally or in a repositiory?"""
         # There are no repositories by default:
         return self.exists()
+
+    def missing(self):
+        """__cacheable__"""
+        return not self.is_derived() and \
+               not self.is_pseudo_derived() and \
+               not self.linked and \
+               not self.rexists()
     
     def prepare(self):
         """Prepare for this Node to be created.
         The default implemenation checks that all children either exist
         or are derived.
         """
-        def missing(node):
-            return not node.is_derived() and \
-                   not node.is_pseudo_derived() and \
-                   not node.linked and \
-                   not node.rexists()
-        missing_sources = filter(missing, self.children())
+        l = self.depends
+        if not self.implicit is None:
+            l = l + self.implicit
+        missing_sources = self.get_executor().get_missing_sources() \
+                          + filter(lambda c: c.missing(), l)
         if missing_sources:
             desc = "Source `%s' not found, needed by target `%s'." % (missing_sources[0], self)
             raise SCons.Errors.StopError, desc
@@ -757,19 +752,16 @@ class Node:
 
     def _children_reset(self):
         "__cache_reset__"
-        pass
+        # We need to let the Executor clear out any calculated
+        # bsig info that it's cached so we can re-calculate it.
+        self.executor_cleanup()
 
-    def filter_ignore(self, nodelist):
-        ignore = self.ignore
-        result = []
-        for node in nodelist:
-            if node not in ignore:
-                result.append(node)
-        return result
+    def do_not_ignore(self, node):
+        return node not in self.ignore
 
     def _children_get(self):
         "__cacheable__"
-        return self.filter_ignore(self.all_children(scan=0))
+        return filter(self.do_not_ignore, self.all_children(scan=0))
         
     def children(self, scan=1):
         """Return a list of the node's direct children, minus those