General performance tweaks

8 files changed, 142 insertions, 165 deletions

diff --git a/src/engine/SCons/Node/FS.py b/src/engine/SCons/Node/FS.py
index 98b6b02..7e9a44b 100644
--- a/src/engine/SCons/Node/FS.py
+++ b/src/engine/SCons/Node/FS.py
@@ -52,6 +52,23 @@ except AttributeError:
         st=os.stat(src)
         os.chmod(dest, stat.S_IMODE(st[stat.ST_MODE]) | stat.S_IWRITE)
 
+class ParentOfRoot:
+    """
+    An instance of this class is used as the parent of the root of a
+    filesystem (POSIX) or drive (Win32). This isn't actually a node,
+    but it looks enough like one so that we don't have to have
+    special purpose code everywhere to deal with dir being None. 
+    This class is an instance of the Null object pattern.
+    """
+    def __init__(self):
+        self.abspath = ""
+        self.duplicate = 1
+        self.path = ""
+        self.srcpath = ""
+
+    def is_under(self, dir):
+        return 0
+
 class PathName:
     """This is a string like object with limited capabilities (i.e.,
     cannot always be used interchangeably with strings).  This class
@@ -145,16 +162,6 @@ class FS:
             self.Top.path_ = os.path.join('.', '')
             self._cwd = self.Top
         
-    def __hash__(self):
-        self.__setTopLevelDir()
-        return hash(self.Top)
-
-    def __cmp__(self, other):
-        self.__setTopLevelDir()
-        if isinstance(other, FS):
-            other.__setTopLevelDir()
-	return cmp(self.__dict__, other.__dict__)
-
     def getcwd(self):
         self.__setTopLevelDir()
 	return self._cwd
@@ -187,7 +194,7 @@ class FS:
             #    if not directory:
             #        raise OSError, 'No drive letter supplied for absolute path.'
             #    return directory.root()
-            dir = Dir(tail)
+            dir = Dir(tail, ParentOfRoot())
             dir.path = drive + dir.path
             dir.path_ = drive + dir.path_
             dir.abspath = drive + dir.abspath
@@ -298,7 +305,13 @@ class Entry(SCons.Node.Node):
     """A generic class for file system entries.  This class if for
     when we don't know yet whether the entry being looked up is a file
     or a directory.  Instances of this class can morph into either
-    Dir or File objects by a later, more precise lookup."""
+    Dir or File objects by a later, more precise lookup.
+
+    Note: this class does not define __cmp__ and __hash__ for efficiency
+    reasons.  SCons does a lot of comparing of Entry objects, and so that
+    operation must be as fast as possible, which means we want to use
+    Python's built-in object identity comparison.
+    """
 
     def __init__(self, name, directory):
 	"""Initialize a generic file system Entry.
@@ -310,34 +323,35 @@ class Entry(SCons.Node.Node):
         SCons.Node.Node.__init__(self)
 
         self.name = name
-        if directory:
-            self.duplicate = directory.duplicate
-            self.abspath = os.path.join(directory.abspath, name)
-            if str(directory.path) == '.':
-                self.path = name
-            else:
-                self.path = os.path.join(directory.path, name)
+
+        assert directory, "A directory must be provided"
+
+        self.duplicate = directory.duplicate
+        self.abspath = os.path.join(directory.abspath, name)
+
+        if str(directory.path) == '.':
+            self.path = name
         else:
-            self.abspath = self.path = name
-            self.duplicate = 1
+            self.path = os.path.join(directory.path, name)
+
         self.path_ = self.path
         self.abspath_ = self.abspath
         self.dir = directory
 	self.use_signature = 1
         self.__doSrcpath(self.duplicate)
 
+    def get_dir(self):
+        return self.dir
+
     def adjust_srcpath(self, duplicate):
         self.__doSrcpath(duplicate)
         
     def __doSrcpath(self, duplicate):
         self.duplicate = duplicate
-        if self.dir:
-            if str(self.dir.srcpath) == '.':
-                self.srcpath = self.name
-            else:
-                self.srcpath = os.path.join(self.dir.srcpath, self.name)
-        else:
+        if str(self.dir.srcpath) == '.':
             self.srcpath = self.name
+        else:
+            self.srcpath = os.path.join(self.dir.srcpath, self.name)
 
     def __str__(self):
 	"""A FS node's string representation is its path name."""
@@ -346,18 +360,6 @@ class Entry(SCons.Node.Node):
         else:
             return self.srcpath
 
-    def __cmp__(self, other):
-	if type(self) != types.StringType and type(other) != types.StringType:
-            try:
-                if self.__class__ != other.__class__:
-                    return 1
-            except:
-                return 1
-        return cmp(str(self), str(other))
-
-    def __hash__(self):
-	return hash(self.abspath_)
-
     def exists(self):
         return os.path.exists(str(self))
 
@@ -373,9 +375,8 @@ class Entry(SCons.Node.Node):
     def is_under(self, dir):
         if self is dir:
             return 1
-        if not self.dir:
-            return 0
-        return self.dir.is_under(dir)
+        else:
+            return self.dir.is_under(dir)
 
 
 
@@ -392,7 +393,7 @@ class Dir(Entry):
     """A class for directories in a file system.
     """
 
-    def __init__(self, name, directory = None):
+    def __init__(self, name, directory):
         Entry.__init__(self, name, directory)
 	self._morph()
 
@@ -564,7 +565,7 @@ class File(Entry):
         if self.env:
             for scn in self.scanners:
                 if not self.scanned.has_key(scn):
-                    deps = scn.scan(str(self), self.env)
+                    deps = scn.scan(self, self.env)
                     self.add_implicit(deps,scn)
                     self.scanned[scn] = 1
                     
diff --git a/src/engine/SCons/Node/FSTests.py b/src/engine/SCons/Node/FSTests.py
index 4801dae..c9d17a7 100644
--- a/src/engine/SCons/Node/FSTests.py
+++ b/src/engine/SCons/Node/FSTests.py
@@ -48,8 +48,8 @@ class Scanner:
         global scanner_count
         scanner_count = scanner_count + 1
         self.hash = scanner_count
-    def scan(self, filename, env):
-        return [SCons.Node.FS.default_fs.File(filename)]
+    def scan(self, node, env):
+        return [node]
     def __hash__(self):
         return self.hash
 
@@ -393,56 +393,7 @@ class FSTestCase(unittest.TestCase):
         f1.build()
         assert f1.dir.exists()
 
-        # Test comparison of FS objects
-        fs1 = SCons.Node.FS.FS()
-        fs2 = SCons.Node.FS.FS()
         os.chdir('..')
-        fs3 = SCons.Node.FS.FS()
-        assert fs1 == fs2
-        assert fs1 != fs3
-
-        # Test comparison of Entry objects
-        e1 = fs3.Entry('cmp/entry')
-        e2 = fs3.Entry('cmp/../cmp/entry')
-        e3 = fs3.Entry('entry')
-        assert e1 == e2
-        assert e1 != e3
-        assert e1 == os.path.normpath("cmp/entry"), e1
-        assert e1 != os.path.normpath("c/entry"), e1
-
-        # Test comparison of Dir objects
-        d1 = fs3.Dir('cmp/dir')
-        d2 = fs3.Dir('cmp/../cmp/dir')
-        d3 = fs3.Dir('dir')
-        assert d1 == d2
-        assert d1 != d3
-        assert d1 == os.path.normpath("cmp/dir"), d1
-        assert d1 != os.path.normpath("c/dir"), d1
-
-        # Test comparison of File objects
-        f1 = fs3.File('cmp/file')
-        f2 = fs3.File('cmp/../cmp/file')
-        f3 = fs3.File('file')
-        assert f1 == f2
-        assert f1 != f3
-        assert f1 == os.path.normpath("cmp/file"), f1
-        assert f1 != os.path.normpath("c/file"), f1
-
-        # Test comparison of different type objects
-        f1 = fs1.File('cmp/xxx')
-        d2 = fs2.Dir('cmp/xxx')
-        assert f1 != d2, "%s == %s" % (f1.__class__, d2.__class__)
-
-        # Test hashing FS nodes
-        f = fs1.File('hash/f')
-        d = fs1.Dir('hash/d')
-        e = fs1.Entry('hash/e')
-        val = {}
-        val[f] = 'f'
-        val[d] = 'd'
-        val[e] = 'e'
-        for k, v in val.items():
-             assert k == os.path.normpath("hash/" + v)
 
 	# Test getcwd()
         fs = SCons.Node.FS.FS()
diff --git a/src/engine/SCons/Scanner/C.py b/src/engine/SCons/Scanner/C.py
index a5aa02d..2c51223 100644
--- a/src/engine/SCons/Scanner/C.py
+++ b/src/engine/SCons/Scanner/C.py
@@ -36,8 +36,7 @@ import re
 import SCons.Scanner
 import SCons.Util
 
-angle_re = re.compile('^[ \t]*#[ \t]*include[ \t]+<([\\w./\\\\]+)>', re.M)
-quote_re = re.compile('^[ \t]*#[ \t]*include[ \t]+"([\\w./\\\\]+)"', re.M)
+include_re = re.compile('^[ \t]*#[ \t]*include[ \t]+(<|")([\\w./\\\\]+)(>|")', re.M)
 
 def CScan(fs = SCons.Node.FS.default_fs):
     "Return a prototype Scanner instance for scanning C/C++ source files"
@@ -73,9 +72,9 @@ class CScanner(SCons.Scanner.Recursive):
     def __hash__(self):
         return hash(self.hash)
 
-def scan(filename, env, args = [SCons.Node.FS.default_fs, ()]):
+def scan(node, env, args = [SCons.Node.FS.default_fs, ()]):
     """
-    scan(str, Environment) -> [str]
+    scan(node, Environment) -> [node]
 
     the C/C++ dependency scanner function
 
@@ -95,23 +94,29 @@ def scan(filename, env, args = [SCons.Node.FS.default_fs, ()]):
     """
 
     fs, cpppath = args
+    nodes = []
 
-    if fs.File(filename, fs.Top).exists():
-        file = open(filename)
-        contents = file.read()
-        file.close()
+    if node.exists():
 
-        angle_includes = angle_re.findall(contents)
-        quote_includes = quote_re.findall(contents)
-
-        dir = os.path.dirname(filename)
-        if dir:
-            source_dir = (fs.Dir(dir, fs.Top),)
+        # cache the includes list in node so we only scan it once:
+        if hasattr(node, 'includes'):
+            includes = node.includes
         else:
-            source_dir = ( fs.Top, )
+            includes = include_re.findall(node.get_contents())
+            node.includes = includes
+
+        source_dir = node.get_dir()
+
+        for include in includes:
+            if include[0] == '"':
+                node = SCons.Util.find_file(include[1], (source_dir,) + cpppath,
+                                            fs.File)
+            else:
+                node = SCons.Util.find_file(include[1], cpppath + (source_dir,),
+                                            fs.File)
+
+            if not node is None:
+                nodes.append(node)
+
+    return nodes
 
-        return (SCons.Util.find_files(angle_includes, cpppath + source_dir,
-                                      fs.File)
-                + SCons.Util.find_files(quote_includes, source_dir + cpppath,
-                                        fs.File))
-    return []
diff --git a/src/engine/SCons/Scanner/CTests.py b/src/engine/SCons/Scanner/CTests.py
index c9cc5ea..70fc2b4 100644
--- a/src/engine/SCons/Scanner/CTests.py
+++ b/src/engine/SCons/Scanner/CTests.py
@@ -138,13 +138,16 @@ def deps_match(self, deps, headers):
     expect.sort()
     self.failUnless(scanned == expect, "expect %s != scanned %s" % (expect, scanned))
 
+def make_node(filename):
+    return SCons.Node.FS.default_fs.File(test.workpath(filename))
+
 # define some tests:
 
 class CScannerTestCase1(unittest.TestCase):
     def runTest(self):
         env = DummyEnvironment([])
         s = SCons.Scanner.C.CScan()
-        deps = s.instance(env).scan(test.workpath('f1.cpp'), env)
+        deps = s.instance(env).scan(make_node('f1.cpp'), env)
 	headers = ['f1.h', 'f2.h', 'fi.h']
         deps_match(self, deps, map(test.workpath, headers))
 
@@ -152,7 +155,7 @@ class CScannerTestCase2(unittest.TestCase):
     def runTest(self):
         env = DummyEnvironment([test.workpath("d1")])
         s = SCons.Scanner.C.CScan()
-        deps = s.instance(env).scan(test.workpath('f1.cpp'), env)
+        deps = s.instance(env).scan(make_node('f1.cpp'), env)
         headers = ['f1.h', 'd1/f2.h']
         deps_match(self, deps, map(test.workpath, headers))
 
@@ -160,7 +163,7 @@ class CScannerTestCase3(unittest.TestCase):
     def runTest(self):
         env = DummyEnvironment([test.workpath("d1")])
         s = SCons.Scanner.C.CScan()
-        deps = s.instance(env).scan(test.workpath('f2.cpp'), env)
+        deps = s.instance(env).scan(make_node('f2.cpp'), env)
         headers = ['f1.h', 'd1/f1.h', 'd1/d2/f1.h']
         deps_match(self, deps, map(test.workpath, headers))
 
@@ -168,7 +171,7 @@ class CScannerTestCase4(unittest.TestCase):
     def runTest(self):
         env = DummyEnvironment([test.workpath("d1"), test.workpath("d1/d2")])
         s = SCons.Scanner.C.CScan()
-        deps = s.instance(env).scan(test.workpath('f2.cpp'), env)
+        deps = s.instance(env).scan(make_node('f2.cpp'), env)
         headers =  ['f1.h', 'd1/f1.h', 'd1/d2/f1.h', 'd1/d2/f4.h']
         deps_match(self, deps, map(test.workpath, headers))
         
@@ -176,7 +179,7 @@ class CScannerTestCase5(unittest.TestCase):
     def runTest(self):
         env = DummyEnvironment([])
         s = SCons.Scanner.C.CScan()
-        deps = s.instance(env).scan(test.workpath('f3.cpp'), env)
+        deps = s.instance(env).scan(make_node('f3.cpp'), env)
         
         # Make sure exists() gets called on the file node being
         # scanned, essential for cooperation with BuildDir functionality.
@@ -197,8 +200,8 @@ class CScannerTestCase6(unittest.TestCase):
         s3 = s.instance(env3)
         assert not s1 is s2
         assert s1 is s3
-        deps1 = s1.scan(test.workpath('f1.cpp'), None)
-        deps2 = s2.scan(test.workpath('f1.cpp'), None)
+        deps1 = s1.scan(make_node('f1.cpp'), None)
+        deps2 = s2.scan(make_node('f1.cpp'), None)
         headers1 =  ['f1.h', 'd1/f2.h']
         headers2 =  ['f1.h', 'd1/d2/f2.h']
         deps_match(self, deps1, map(test.workpath, headers1))
@@ -218,9 +221,9 @@ class CScannerTestCase8(unittest.TestCase):
         fs = SCons.Node.FS.FS(test.workpath(''))
         env = DummyEnvironment(["include"])
         s = SCons.Scanner.C.CScan(fs = fs)
-        deps1 = s.instance(env).scan(test.workpath('fa.cpp'), None)
+        deps1 = s.instance(env).scan(make_node('fa.cpp'), None)
         fs.chdir(fs.Dir('subdir'))
-        deps2 = s.instance(env).scan(test.workpath('fa.cpp'), None)
+        deps2 = s.instance(env).scan(make_node('fa.cpp'), None)
         headers1 =  ['include/fa.h', 'include/fb.h']
         headers2 =  ['subdir/include/fa.h', 'subdir/include/fb.h']
         deps_match(self, deps1, headers1)
@@ -232,8 +235,8 @@ class CScannerTestCase9(unittest.TestCase):
         s = SCons.Scanner.C.CScan(fs=fs)
         env = DummyEnvironment([])
         test.write('fa.h','\n')
-        deps = s.instance(env).scan('fa.cpp', None)
-        deps_match(self, deps, [ 'fa.h' ])
+        deps = s.instance(env).scan(make_node('fa.cpp'), None)
+        deps_match(self, deps, [ test.workpath('fa.h') ])
         test.unlink('fa.h')
 
 class CScannerTestCase10(unittest.TestCase):
@@ -243,8 +246,8 @@ class CScannerTestCase10(unittest.TestCase):
         s = SCons.Scanner.C.CScan(fs=fs)
         env = DummyEnvironment([])
         test.write('include/fa.cpp', test.read('fa.cpp'))
-        deps = s.instance(env).scan('include/fa.cpp', None)
-        deps_match(self, deps, [ 'include/fa.h', 'include/fb.h' ])
+        deps = s.instance(env).scan(make_node('include/fa.cpp'), None)
+        deps_match(self, deps, [ test.workpath('include/fa.h'), test.workpath('include/fb.h') ])
         test.unlink('include/fa.cpp')
 
 def suite():
diff --git a/src/engine/SCons/Scanner/Prog.py b/src/engine/SCons/Scanner/Prog.py
index cbbfb42..0182cda 100644
--- a/src/engine/SCons/Scanner/Prog.py
+++ b/src/engine/SCons/Scanner/Prog.py
@@ -32,7 +32,7 @@ def ProgScan():
     files for static-lib dependencies"""
     return SCons.Scanner.Base(scan, "ProgScan", SCons.Node.FS.default_fs.File)
 
-def scan(filename, env, node_factory):
+def scan(node, env, node_factory):
     """
     This scanner scans program files for static-library
     dependencies.  It will search the LIBPATH environment variable
diff --git a/src/engine/SCons/Scanner/__init__.py b/src/engine/SCons/Scanner/__init__.py
index ba37edc..52eae8e 100644
--- a/src/engine/SCons/Scanner/__init__.py
+++ b/src/engine/SCons/Scanner/__init__.py
@@ -90,18 +90,18 @@ class Base:
         self.argument = argument
         self.skeys = skeys
 
-    def scan(self, filename, env):
+    def scan(self, node, env):
         """
-        This method scans a single object. 'filename' is the filename
+        This method scans a single object. 'node' is the node
         that will be passed to the scanner function, and 'env' is the
         environment that will be passed to the scanner function. A list of
         direct dependency nodes for the specified filename will be returned.
         """
 
         if not self.argument is _null:
-            return self.function(filename, env, self.argument)
+            return self.function(node, env, self.argument)
         else:
-            return self.function(filename, env)
+            return self.function(node, env)
 
     def instance(self, env):
         """
@@ -127,28 +127,27 @@ class Recursive(Base):
     list of all dependencies.
     """
 
-    def scan(self, filename, env):
+    def scan(self, node, env):
         """
-        This method does the actual scanning. 'filename' is the filename
+        This method does the actual scanning. 'node' is the node
         that will be passed to the scanner function, and 'env' is the
         environment that will be passed to the scanner function. An
         aggregate list of dependency nodes for the specified filename
         and any of its scanned dependencies will be returned.
         """
 
-        files = [filename]
-        seen = [filename]
+        nodes = [node]
+        seen = [node]
         deps = []
-        while files:
-            f = files.pop(0)
+        while nodes:
+            n = nodes.pop(0)
             if not self.argument is _null:
-                d = self.function(f, env, self.argument)
+                d = self.function(n, env, self.argument)
             else:
-                d = self.function(f, env)
-            d = filter(lambda x, seen=seen: str(x) not in seen, d)
+                d = self.function(n, env)
+            d = filter(lambda x, seen=seen: x not in seen, d)
             if d:
                 deps.extend(d)
-                s = map(str, d)
-                seen.extend(s)
-                files.extend(s)
+                seen.extend(d)
+                nodes.extend(d)
         return deps
diff --git a/src/engine/SCons/Util.py b/src/engine/SCons/Util.py
index 7687250..a517407 100644
--- a/src/engine/SCons/Util.py
+++ b/src/engine/SCons/Util.py
@@ -224,9 +224,9 @@ def scons_subst(strSubst, locals, globals):
     return string.join(map(string.join, cmd_list), '\n')
 
 def find_files(filenames, paths,
-               node_factory = SCons.Node.FS.default_fs.File):
+	       node_factory = SCons.Node.FS.default_fs.File):
     """
-    find_files([str], [str]) -> [nodes]
+    find_files([str], [Dir()]) -> [nodes]
 
     filenames - a list of filenames to find
     paths - a list of directory path *nodes* to search in
@@ -239,22 +239,39 @@ def find_files(filenames, paths,
     Only the first file found is returned for each filename,
     and any files that aren't found are ignored.
     """
-    nodes = []
-    for filename in filenames:
-        for dir in paths:
-            try:
-                node = node_factory(filename, dir)
-                # Return true of the node exists or is a derived node.
-                if node.builder or \
-                   (isinstance(node, SCons.Node.FS.Entry) and node.exists()):
-                    nodes.append(node)
-                    break
-            except TypeError:
-                # If we find a directory instead of a file, we
-                # don't care
-                pass
+    nodes = map(lambda x, paths=paths, node_factory=node_factory: find_file(x, paths, node_factory), filenames)
+    return filter(lambda x: x != None, nodes)
 
-    return nodes
+def find_file(filename, paths,
+              node_factory = SCons.Node.FS.default_fs.File):
+    """
+    find_file(str, [Dir()]) -> [nodes]
+
+    filename - a filename to find
+    paths - a list of directory path *nodes* to search in
+
+    returns - the node created from the found file.
+
+    Find a node corresponding to either a derived file or a file
+    that exists already.
+
+    Only the first file found is returned, and none is returned
+    if no file is found.
+    """
+    retval = None
+    for dir in paths:
+        try:
+            node = node_factory(filename, dir)
+            # Return true of the node exists or is a derived node.
+            if node.builder or \
+               (isinstance(node, SCons.Node.FS.Entry) and node.exists()):
+                retval = node
+                break
+        except TypeError:
+            # If we find a directory instead of a file, we don't care
+            pass
+
+    return retval
 
 class VarInterpolator:
     def __init__(self, dest, src, prefix, suffix):
diff --git a/src/engine/SCons/UtilTests.py b/src/engine/SCons/UtilTests.py
index 168896f..784c84d 100644
--- a/src/engine/SCons/UtilTests.py
+++ b/src/engine/SCons/UtilTests.py
@@ -160,8 +160,8 @@ class UtilTestCase(unittest.TestCase):
         assert cmd_list[1][0] == 'after', cmd_list[1][0]
         assert cmd_list[0][2] == cvt('../foo/ack.cbefore'), cmd_list[0][2]
 
-    def test_find_files(self):
-        """Testing find_files function."""
+    def test_find_file(self):
+        """Testing find_file function."""
         test = TestCmd.TestCmd(workdir = '')
         test.write('./foo', 'Some file\n')
         fs = SCons.Node.FS.FS(test.workpath(""))
@@ -169,7 +169,8 @@ class UtilTestCase(unittest.TestCase):
         node_derived = fs.File(test.workpath('./bar/baz'))
         node_derived.builder_set(1) # Any non-zero value.
         paths = map(fs.Dir, ['.', './bar'])
-        nodes = find_files(['foo', 'baz'], paths, fs.File)
+        nodes = [find_file('foo', paths, fs.File), 
+                 find_file('baz', paths, fs.File)] 
         file_names = map(str, nodes)
         file_names = map(os.path.normpath, file_names)
         assert os.path.normpath('./foo') in file_names, file_names