Implement implicit dependency caching.

7 files changed, 262 insertions, 79 deletions

diff --git a/src/engine/SCons/Node/FS.py b/src/engine/SCons/Node/FS.py
index c49361d..1c506c9 100644
--- a/src/engine/SCons/Node/FS.py
+++ b/src/engine/SCons/Node/FS.py
@@ -467,10 +467,8 @@ class Dir(Entry):
         """Return the .sconsign file info for this directory,
         creating it first if necessary."""
         if not self._sconsign:
-            #XXX Rework this to get rid of the hard-coding
             import SCons.Sig
-            import SCons.Sig.MD5
-            self._sconsign = SCons.Sig.SConsignFile(self, SCons.Sig.MD5)
+            self._sconsign = SCons.Sig.SConsignFile(self)
         return self._sconsign
 
 
@@ -534,11 +532,15 @@ class File(Entry):
                                 self.get_bsig(),
                                 old[2])
 
+    def store_implicit(self):
+        self.dir.sconsign().set_implicit(self.name, self.implicit)
+
     def get_prevsiginfo(self):
-        """Fetch the previous signature information from the
-        .sconsign entry."""
         return self.dir.sconsign().get(self.name)
 
+    def get_stored_implicit(self):
+        return self.dir.sconsign().get_implicit(self.name)
+
     def get_implicit_deps(self, env, scanner, target):
         if scanner:
             return scanner.scan(self, env, target)
diff --git a/src/engine/SCons/Node/FSTests.py b/src/engine/SCons/Node/FSTests.py
index 0e19cec..6b35adb 100644
--- a/src/engine/SCons/Node/FSTests.py
+++ b/src/engine/SCons/Node/FSTests.py
@@ -36,10 +36,16 @@ import stat
 built_it = None
 
 class Builder:
+    def __init__(self, factory):
+        self.factory = factory
+
     def execute(self, **kw):
         global built_it
         built_it = 1
         return 0
+    
+    def source_factory(self, name):
+        return self.factory(name)
 
 scanner_count = 0
 
@@ -285,7 +291,7 @@ class FSTestCase(unittest.TestCase):
         built_it = None
         assert not built_it
         d1.add_source([SCons.Node.Node()])    # XXX FAKE SUBCLASS ATTRIBUTE
-        d1.builder_set(Builder())
+        d1.builder_set(Builder(fs.File))
         d1.env_set(Environment())
         d1.build()
         assert not built_it
@@ -293,7 +299,7 @@ class FSTestCase(unittest.TestCase):
         built_it = None
         assert not built_it
         f1.add_source([SCons.Node.Node()])    # XXX FAKE SUBCLASS ATTRIBUTE
-        f1.builder_set(Builder())
+        f1.builder_set(Builder(fs.File))
         f1.env_set(Environment())
         f1.build()
         assert built_it
@@ -381,6 +387,7 @@ class FSTestCase(unittest.TestCase):
         match(d12.path_, "subdir/d12/")
         e13 = fs.Entry("subdir/e13")
         match(e13.path, "subdir/subdir/e13")
+        fs.chdir(fs.Dir('..'))
 
         # Test scanning
         f1.target_scanner = Scanner()
@@ -391,7 +398,9 @@ class FSTestCase(unittest.TestCase):
         assert f1.implicit == []
         f1.implicit = None
         f1.scan()
-        assert f1.implicit[0].path_ == os.path.join("d1", "f1")
+        assert f1.implicit[0].path_ == os.path.join("d1", "f1"), f1.implicit[0].path_
+        f1.store_implicit()
+        assert f1.get_stored_implicit()[0] == os.path.join("d1", "f1")
 
         # Test building a file whose directory is not there yet...
         f1 = fs.File(test.workpath("foo/bar/baz/ack"))
diff --git a/src/engine/SCons/Node/__init__.py b/src/engine/SCons/Node/__init__.py
index a9ca790..cbaed7b 100644
--- a/src/engine/SCons/Node/__init__.py
+++ b/src/engine/SCons/Node/__init__.py
@@ -35,6 +35,7 @@ import string
 import types
 import copy
 import sys
+import SCons.Sig
 
 from SCons.Errors import BuildError
 import SCons.Util
@@ -53,6 +54,9 @@ executed = 4
 failed = 5
 stack = 6 # nodes that are in the current Taskmaster execution stack
 
+# controls whether implicit depedencies are cached:
+implicit_cache = 0
+
 class Node:
     """The base Node class, for entities that we know how to
     build, or use to build other Nodes.
@@ -116,9 +120,9 @@ class Node:
         if self.source_scanner:
             self.found_includes = {}
             self.includes = None
-            
+
             def get_parents(node, parent): return node.get_parents()
-            def clear_cache(node, parent): 
+            def clear_cache(node, parent):
                 node.implicit = None
                 node.bsig = None
             w = Walker(self, get_parents, ignore_cycle, clear_cache)
@@ -170,17 +174,38 @@ class Node:
         # Don't bother scanning non-derived files, because we don't
         # care what their dependencies are.
         # Don't scan again, if we already have scanned.
-        if self.implicit is None:
-            if self.builder:
-                self.implicit = []
-                for child in self.children(scan=0):
-                    self._add_child(self.implicit, child.get_implicit_deps(self.env, child.source_scanner, self))
-            
-                # scan this node itself for implicit dependencies
-                self._add_child(self.implicit, self.get_implicit_deps(self.env, self.target_scanner, self))
-            else:
-                self.implicit = []
-    
+        if not self.implicit is None:
+            return
+        self.implicit = []
+        if not self.builder:
+            return
+
+        if implicit_cache:
+            implicit = self.get_stored_implicit()
+            if implicit is not None:
+                implicit = map(self.builder.source_factory, implicit)
+                self._add_child(self.implicit, implicit)
+                calc = SCons.Sig.default_calc
+                if calc.current(self, calc.bsig(self)):
+                    return
+                else:
+                    self.implicit = []
+
+        for child in self.children(scan=0):
+            self._add_child(self.implicit,
+                            child.get_implicit_deps(self.env,
+                                                    child.source_scanner,
+                                                    self))
+
+        # scan this node itself for implicit dependencies
+        self._add_child(self.implicit,
+                        self.get_implicit_deps(self.env,
+                                               self.target_scanner,
+                                               self))
+
+        if implicit_cache:
+            self.store_implicit()
+
     def scanner_key(self):
         return None
 
@@ -225,6 +250,15 @@ class Node:
     def get_timestamp(self):
         return 0
 
+    def store_implicit(self):
+        """Make the implicit deps permanent (that is, store them in the
+        .sconsign file or equivalent)."""
+        pass
+
+    def get_stored_implicit(self):
+        """Fetch the stored implicit dependencies"""
+        return None
+
     def set_precious(self, precious = 1):
         """Set the Node's precious value."""
         self.precious = precious
@@ -276,7 +310,7 @@ class Node:
             return self.sources + self.depends
         else:
             return self.sources + self.depends + self.implicit
-    
+
     def get_parents(self):
         return self.parents.keys()
 
@@ -300,10 +334,10 @@ class Walker:
     The Walker object can be initialized with any node, and
     returns the next node on the descent with each next() call.
     'kids_func' is an optional function that will be called to
-    get the children of a node instead of calling 'children'. 
+    get the children of a node instead of calling 'children'.
     'cycle_func' is an optional function that will be called
     when a cycle is detected.
-    
+
     This class does not get caught in node cycles caused, for example,
     by C header file include loops.
     """
diff --git a/src/engine/SCons/Script/__init__.py b/src/engine/SCons/Script/__init__.py
index d9406ec..308552d 100644
--- a/src/engine/SCons/Script/__init__.py
+++ b/src/engine/SCons/Script/__init__.py
@@ -163,7 +163,7 @@ max_drift = None
 
 def get_all_children(node): return node.all_children(None)
 
-def get_derived_children(node): 
+def get_derived_children(node):
     children = node.all_children(None)
     return filter(lambda x: x.builder, children)
 
@@ -224,7 +224,7 @@ opt_func = {}		# mapping of option strings to functions
 
 def options_init():
     """Initialize command-line options processing.
-    
+
     This is in a subroutine mainly so we can easily single-step over
     it in the debugger.
     """
@@ -471,6 +471,14 @@ def options_init():
 	short = 'I', long = ['include-dir'], arg = 'DIRECTORY',
 	help = "Search DIRECTORY for imported Python modules.")
 
+    def opt_implicit_cache(opt, arg):
+        import SCons.Node
+        SCons.Node.implicit_cache = 1
+
+    Option(func = opt_implicit_cache,
+        long = ['implicit-cache'],
+        help = "Cache implicit dependencies")
+
     def opt_j(opt, arg):
 	global num_jobs
 	try:
@@ -515,7 +523,7 @@ def options_init():
         global max_drift
         try:
             max_drift = int(arg)
-        except ValueError: 
+        except ValueError:
             raise UserError, "The argument for --max-drift must be an integer."
 
     Option(func = opt_max_drift,
@@ -727,7 +735,7 @@ def _main():
             os.chdir(script_dir)
         else:
             raise UserError, "No SConstruct file found."
-        
+
     SCons.Node.FS.default_fs.set_toplevel_dir(os.getcwd())
 
     if not scripts:
@@ -810,10 +818,11 @@ def _main():
     nodes = filter(lambda x: x is not None, map(Entry, targets))
 
     if not calc:
-        if max_drift is None:
-            calc = SCons.Sig.Calculator(SCons.Sig.MD5)
-        else:
-            calc = SCons.Sig.Calculator(SCons.Sig.MD5, max_drift)
+        if max_drift is not None:
+            SCons.Sig.default_calc = SCons.Sig.Calculator(SCons.Sig.MD5,
+                                                          max_drift)
+
+        calc = SCons.Sig.default_calc
 
     taskmaster = SCons.Taskmaster.Taskmaster(nodes, task_class, calc)
 
diff --git a/src/engine/SCons/Sig/SigTests.py b/src/engine/SCons/Sig/SigTests.py
index 2a2560f..cc39656 100644
--- a/src/engine/SCons/Sig/SigTests.py
+++ b/src/engine/SCons/Sig/SigTests.py
@@ -58,11 +58,11 @@ class DummyNode:
         self.oldtime = 0
         self.oldbsig = 0
         self.oldcsig = 0
-        
+
     def get_contents(self):
         # a file that doesn't exist has no contents:
         assert self.exists()
-        
+
         return self.file.contents
 
     def get_timestamp(self):
@@ -80,11 +80,11 @@ class DummyNode:
         except AttributeError:
             self.exists_cache = self.exists()
             return self.exists_cache
-        
+
     def children(self):
         return filter(lambda x, i=self.ignore: x not in i,
                       self.sources + self.depends)
-        
+
     def all_children(self):
         return self.sources + self.depends
 
@@ -113,7 +113,16 @@ class DummyNode:
 
     def get_prevsiginfo(self):
         return (self.oldtime, self.oldbsig, self.oldcsig)
-    
+
+    def get_stored_implicit(self):
+        return None
+
+    def store_csig(self):
+        pass
+
+    def store_bsig(self):
+        pass
+
     def builder_sig_adapter(self):
         class Adapter:
             def get_contents(self):
@@ -135,7 +144,7 @@ def create_files(test):
              (test.workpath('d1/test.c'), 'blah blah', 111, 0),#8
              (test.workpath('d1/test.o'), None, 0, 1),         #9
              (test.workpath('d1/test'), None, 0, 1)]           #10
-    
+
     files = map(lambda x: apply(DummyFile, x), args)
 
     return files
@@ -173,12 +182,12 @@ def clear(nodes):
         node.bsig = None
 
 class SigTestBase:
-    
+
     def runTest(self):
 
         test = TestCmd.TestCmd(workdir = '')
         test.subdir('d1')
-        
+
         self.files = create_files(test)
         self.test_initial()
         self.test_built()
@@ -186,9 +195,9 @@ class SigTestBase:
         self.test_modify_same_time()
         self.test_delete()
         self.test_cache()
-        
+
     def test_initial(self):
-        
+
         nodes = create_nodes(self.files)
         calc = SCons.Sig.Calculator(self.module)
 
@@ -209,7 +218,7 @@ class SigTestBase:
         calc = SCons.Sig.Calculator(self.module)
 
         write(calc, nodes)
-        
+
         for node in nodes:
             self.failUnless(current(calc, node),
                             "all of the nodes should be current")
@@ -242,7 +251,6 @@ class SigTestBase:
         self.failUnless(not current(calc, nodes[9]), "direct source modified")
         self.failUnless(not current(calc, nodes[10]), "indirect source modified")
 
-
     def test_modify_same_time(self):
 
         nodes = create_nodes(self.files)
@@ -264,9 +272,9 @@ class SigTestBase:
                             "all of the nodes should be current")
 
     def test_delete(self):
-        
+
         nodes = create_nodes(self.files)
-        
+
         calc = SCons.Sig.Calculator(self.module)
 
         write(calc, nodes)
@@ -292,13 +300,13 @@ class SigTestBase:
     def test_cache(self):
         """Test that signatures are cached properly."""
         nodes = create_nodes(self.files)
-        
+
         calc = SCons.Sig.Calculator(self.module)
         nodes[0].set_csig(1)
         nodes[1].set_bsig(1)
         assert calc.csig(nodes[0]) == 1, calc.csig(nodes[0])
         assert calc.bsig(nodes[1]) == 1, calc.bsig(nodes[1])
-        
+
 
 class MD5TestCase(unittest.TestCase, SigTestBase):
     """Test MD5 signatures"""
@@ -311,7 +319,7 @@ class TimeStampTestCase(unittest.TestCase, SigTestBase):
     module = SCons.Sig.TimeStamp
 
 class CalcTestCase(unittest.TestCase):
-    
+
     def runTest(self):
         class MySigModule:
             def collect(self, signatures):
@@ -348,6 +356,8 @@ class CalcTestCase(unittest.TestCase):
                 return self.csig
             def get_prevsiginfo(self):
                 return 0, self.bsig, self.csig
+            def get_stored_implicit(self):
+                return None
             def get_timestamp(self):
                 return 1
             def builder_sig_adapter(self):
@@ -443,11 +453,52 @@ class CalcTestCase(unittest.TestCase):
         assert not self.calc.current(nn, 30)
         assert self.calc.current(nn, 33)
 
+class SConsignEntryTestCase(unittest.TestCase):
+
+    def runTest(self):
+        class DummyModule:
+            def to_string(self, sig):
+                return str(sig)
+
+            def from_string(self, sig):
+                return int(sig)
+
+        m = DummyModule()
+        e = SCons.Sig.SConsignEntry(m)
+        assert e.timestamp == None
+        assert e.csig == None
+        assert e.bsig == None
+        assert e.get_implicit() == None
+        assert e.render(m) == "- - - -"
+
+        e = SCons.Sig.SConsignEntry(m, "- - - -")
+        assert e.timestamp == None
+        assert e.csig == None
+        assert e.bsig == None
+        assert e.get_implicit() == None
+        assert e.render(m) == "- - - -"
+
+        e = SCons.Sig.SConsignEntry(m, "- - - foo\0bar")
+        assert e.timestamp == None
+        assert e.csig == None
+        assert e.bsig == None
+        assert e.get_implicit() == ['foo', 'bar']
+        assert e.render(m) == "- - - foo\0bar"
+
+        e = SCons.Sig.SConsignEntry(m, "123 456 789 foo bletch\0bar")
+        assert e.timestamp == 123
+        assert e.bsig == 456
+        assert e.csig == 789
+        assert e.get_implicit() == ['foo bletch', 'bar']
+        assert e.render(m) == "123 456 789 foo bletch\0bar"
+
+
 def suite():
     suite = unittest.TestSuite()
     suite.addTest(MD5TestCase())
     suite.addTest(TimeStampTestCase())
     suite.addTest(CalcTestCase())
+    suite.addTest(SConsignEntryTestCase())
     return suite
 
 if __name__ == "__main__":
@@ -455,4 +506,4 @@ if __name__ == "__main__":
     result = runner.run(suite())
     if not result.wasSuccessful():
         sys.exit(1)
-    
+
diff --git a/src/engine/SCons/Sig/__init__.py b/src/engine/SCons/Sig/__init__.py
index d077114..386c9e5 100644
--- a/src/engine/SCons/Sig/__init__.py
+++ b/src/engine/SCons/Sig/__init__.py
@@ -43,19 +43,74 @@ def write():
     for sig_file in sig_files:
         sig_file.write()
 
+class SConsignEntry:
+    def __init__(self, module, entry=None):
+
+        self.timestamp = self.csig = self.bsig = self.implicit = None
+
+        if not entry is None:
+            arr = map(string.strip, string.split(entry, " ", 3))
+
+            try:
+                if arr[0] == '-': self.timestamp = None
+                else:             self.timestamp = int(arr[0])
+
+                if arr[1] == '-': self.bsig = None
+                else:             self.bsig = module.from_string(arr[1])
+
+                if arr[2] == '-': self.csig = None
+                else:             self.csig = module.from_string(arr[2])
+
+                if arr[3] == '-': self.implicit = None
+                else:             self.implicit = arr[3]
+            except IndexError:
+                pass
+
+    def render(self, module):
+        if self.timestamp is None: timestamp = '-'
+        else:                      timestamp = "%d"%self.timestamp
+
+        if self.bsig is None: bsig = '-'
+        else:                 bsig = module.to_string(self.bsig)
+
+        if self.csig is None: csig = '-'
+        else:                 csig = module.to_string(self.csig)
+
+        if self.implicit is None: implicit = '-'
+        else:                     implicit = self.implicit
+
+        return '%s %s %s %s' % (timestamp, bsig, csig, implicit)
+
+    def get_implicit(self):
+        if self.implicit is None:
+            return None
+        else:
+            return string.split(self.implicit, '\0')
+
+    def set_implicit(self, implicit):
+        if implicit is None:
+            self.implicit = None
+        else:
+            self.implicit = string.join(map(str, implicit), '\0')
+
+
 class SConsignFile:
     """
     Encapsulates reading and writing a .sconsign file.
     """
 
-    def __init__(self, dir, module):
+    def __init__(self, dir, module=None):
         """
         dir - the directory for the file
         module - the signature module being used
         """
 
         self.dir = dir
-        self.module = module
+
+        if module is None:
+            self.module = default_calc.module
+        else:
+            self.module = module
         self.sconsign = os.path.join(dir.path, '.sconsign')
         self.entries = {}
         self.dirty = None
@@ -66,8 +121,8 @@ class SConsignFile:
             pass
         else:
             for line in file.readlines():
-                filename, rest = map(string.strip, string.split(line, ":"))
-                self.entries[filename] = rest
+                filename, rest = map(string.strip, string.split(line, ":", 1))
+                self.entries[filename] = SConsignEntry(self.module, rest)
 
         global sig_files
         sig_files.append(self)
@@ -77,24 +132,13 @@ class SConsignFile:
         Get the .sconsign entry for a file
 
         filename - the filename whose signature will be returned
-        returns - (timestamp, bsig, csig)
+        returns - (timestamp, bsig, csig, implicit)
         """
-
         try:
-            arr = map(string.strip, string.split(self.entries[filename], " "))
+            entry = self.entries[filename]
+            return (entry.timestamp, entry.bsig, entry.csig)
         except KeyError:
             return (None, None, None)
-        try:
-            if arr[1] == '-': bsig = None
-            else:             bsig = self.module.from_string(arr[1])
-        except IndexError:
-            bsig = None
-        try:
-            if arr[2] == '-': csig = None
-            else:             csig = self.module.from_string(arr[2])
-        except IndexError:
-            csig = None
-        return (int(arr[0]), bsig, csig)
 
     def set(self, filename, timestamp, bsig = None, csig = None):
         """
@@ -106,13 +150,37 @@ class SConsignFile:
         bsig - the file's build signature
         csig - the file's content signature
         """
-        if bsig is None: bsig = '-'
-        else:            bsig = self.module.to_string(bsig)
-        if csig is None: csig = ''
-        else:            csig = ' ' + self.module.to_string(csig)
-        self.entries[filename] = "%d %s%s" % (timestamp, bsig, csig)
+
+        try:
+            entry = self.entries[filename]
+        except KeyError:
+            entry = SConsignEntry(self.module)
+            self.entries[filename] = entry
+
+        entry.timestamp = timestamp
+        entry.bsig = bsig
+        entry.csig = csig
+
         self.dirty = 1
 
+    def get_implicit(self, filename):
+        """Fetch the cached implicit dependencies for 'filename'"""
+        try:
+            entry = self.entries[filename]
+            return entry.get_implicit()
+        except KeyError:
+            return None
+
+    def set_implicit(self, filename, implicit):
+        """Cache the implicit dependencies for 'filename'."""
+        try:
+            entry = self.entries[filename]
+        except KeyError:
+            entry = SConsignEntry(self.module)
+            self.entries[filename] = entry
+
+        entry.set_implicit(implicit)
+
     def write(self):
         """
         Write the .sconsign file to disk.
@@ -132,12 +200,15 @@ class SConsignFile:
                 file = open(temp, 'wt')
                 fname = temp
             except:
-                file = open(self.sconsign, 'wt')
-                fname = self.sconsign
+                try:
+                    file = open(self.sconsign, 'wt')
+                    fname = self.sconsign
+                except:
+                    return
             keys = self.entries.keys()
             keys.sort()
             for name in keys:
-                file.write("%s: %s\n" % (name, self.entries[name]))
+                file.write("%s: %s\n" % (name, self.entries[name].render(self.module)))
             file.close()
             if fname != self.sconsign:
                 try:
@@ -163,7 +234,7 @@ class Calculator:
     for the build engine.
     """
 
-    def __init__(self, module, max_drift=2*24*60*60):
+    def __init__(self, module=None, max_drift=2*24*60*60):
         """
         Initialize the calculator.
 
@@ -172,7 +243,11 @@ class Calculator:
           cache content signatures. A negative value means to never cache
           content signatures. (defaults to 2 days)
         """
-        self.module = module
+        if module is None:
+            import MD5
+            self.module = MD5
+        else:
+            self.module = module
         self.max_drift = max_drift
 
     def bsig(self, node):
@@ -198,6 +273,7 @@ class Calculator:
         sigs = map(self.get_signature, node.children())
         if node.builder:
             sigs.append(self.module.signature(node.builder_sig_adapter()))
+
         bsig = self.module.collect(filter(lambda x: not x is None, sigs))
 
         node.set_bsig(bsig)
@@ -294,3 +370,6 @@ class Calculator:
             return 1
 
         return self.module.current(newsig, oldbsig)
+
+
+default_calc = Calculator()
diff --git a/src/engine/SCons/Taskmaster.py b/src/engine/SCons/Taskmaster.py
index 22c22cb..7985b2e 100644
--- a/src/engine/SCons/Taskmaster.py
+++ b/src/engine/SCons/Taskmaster.py
@@ -125,7 +125,6 @@ class Task:
         state = SCons.Node.up_to_date
         for t in self.targets:
             bsig = self.tm.calc.bsig(t)
-            t.set_bsig(bsig)
             if not self.tm.calc.current(t, bsig):
                 state = SCons.Node.executing
         self.set_tstates(state)