From 0d1b417af45c1d8744d64d8e12e4ec701ce3d01b Mon Sep 17 00:00:00 2001 From: stevenknight Date: Tue, 15 Jan 2002 22:49:18 +0000 Subject: [PATCH] Significant performance optimizations (Charles Crain). git-svn-id: http://scons.tigris.org/svn/scons/trunk@210 fdb21ef1-2011-0410-befe-b5e4ea1792b1 --- src/CHANGES.txt | 5 + src/engine/SCons/Node/FS.py | 239 +++++++++++---------------- src/engine/SCons/Node/FSTests.py | 11 +- src/engine/SCons/Scanner/CTests.py | 18 +- src/engine/SCons/Scanner/__init__.py | 7 +- src/engine/SCons/Util.py | 4 +- src/engine/SCons/UtilTests.py | 2 +- 7 files changed, 124 insertions(+), 162 deletions(-) diff --git a/src/CHANGES.txt b/src/CHANGES.txt index f87056fd..393db1eb 100644 --- a/src/CHANGES.txt +++ b/src/CHANGES.txt @@ -10,6 +10,11 @@ RELEASE 0.04 - + From Charles Crain: + + - Significant performance improvements in the Node.FS and + Scanner subsystems. + From Steven Knight: - Fix using a directory as a Default(), and allow Default() to diff --git a/src/engine/SCons/Node/FS.py b/src/engine/SCons/Node/FS.py index 9da3a884..66b7314a 100644 --- a/src/engine/SCons/Node/FS.py +++ b/src/engine/SCons/Node/FS.py @@ -33,6 +33,7 @@ canonical default. __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__" +import string import os import os.path import types @@ -65,81 +66,22 @@ class ParentOfRoot: self.duplicate = 1 self.path = "" self.srcpath = "" + self.abspath_='' + 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 - is used by PathDict to manage case-insensitive path names. It preserves - the case of the string with which it was created, but on OS's with - case insensitive paths, it will hash equal to any case of the same - path when placed in a dictionary.""" - - try: - convert_path = unicode - except NameError: - convert_path = str - - def __init__(self, path_name=''): - if isinstance(path_name, PathName): - self.__dict__ = path_name.__dict__ - else: - self.data = PathName.convert_path(path_name) - self.norm_path = os.path.normcase(self.data) - - def __hash__(self): - return hash(self.norm_path) - def __cmp__(self, other): - if isinstance(other, PathName): - return cmp(self.norm_path, other.norm_path) - return cmp(self.norm_path, - os.path.normcase(PathName.convert_path(other))) - def __rcmp__(self, other): - if isinstance(other, PathName): - return cmp(other.norm_path, self.norm_path) - return cmp(os.path.normcase(PathName.convert_path(other)), - self.norm_path) - def __str__(self): - return str(self.data) - def __repr__(self): - return repr(self.data) - -class PathDict(UserDict): - """This is a dictionary-like class meant to hold items keyed - by path name. The difference between this class and a normal - dictionary is that string or unicode keys will act differently - on OS's that have case-insensitive path names. Specifically - string or unicode keys of different case will be treated as - equal on the OS's. - - All keys are implicitly converted to PathName objects before - insertion into the dictionary.""" - - def __init__(self, initdict = {}): - UserDict.__init__(self, initdict) - old_dict = self.data - self.data = {} - for key, val in old_dict.items(): - self.data[PathName(key)] = val - - def __setitem__(self, key, val): - self.data[PathName(key)] = val - - def __getitem__(self, key): - return self.data[PathName(key)] - - def __delitem__(self, key): - del(self.data[PathName(key)]) - - def setdefault(self, key, value): - key = PathName(key) - try: - return self.data[key] - except KeyError: - self.data[key] = value - return value + def up(self): + return None + +if os.path.normcase("TeSt") == os.path.normpath("TeSt"): + def _my_normcase(x): + return x +else: + def _my_normcase(x): + return string.upper(x) class FS: def __init__(self, path = None): @@ -155,7 +97,7 @@ class FS: self.pathTop = os.getcwd() else: self.pathTop = path - self.Root = PathDict() + self.Root = {} self.Top = None def set_toplevel_dir(self, path): @@ -164,16 +106,28 @@ class FS: def __setTopLevelDir(self): if not self.Top: - self.Top = self.__doLookup(Dir, self.pathTop) + self.Top = self.__doLookup(Dir, os.path.normpath(self.pathTop)) self.Top.path = '.' self.Top.srcpath = '.' - self.Top.path_ = os.path.join('.', '') + self.Top.path_ = '.' + os.sep self._cwd = self.Top def getcwd(self): self.__setTopLevelDir() return self._cwd + def __checkClass(self, node, klass): + if klass == Entry: + return node + if node.__class__ == Entry: + node.__class__ = klass + node._morph() + return node + if not isinstance(node, klass): + raise TypeError, "Tried to lookup %s '%s' as a %s." % \ + (node.__class__.__name__, str(node), klass.__name__) + return node + def __doLookup(self, fsclass, name, directory=None): """This method differs from the File and Dir factory methods in one important way: the meaning of the directory parameter. @@ -182,55 +136,39 @@ class FS: relative path with directory=None, then an AssertionError will be raised.""" - head, tail = os.path.split(os.path.normpath(name)) - if not tail: - # We have reached something that looks like a root - # of an absolute path. What we do here is a little - # weird. If we are on a UNIX system, everything is - # well and good, just return the root node. - # - # On DOS/Win32 things are strange, since a path - # starting with a slash is not technically an - # absolute path, but a path relative to the - # current drive. Therefore if we get a path like - # that, we will return the root Node of the - # directory parameter. If the directory parameter is - # None, raise an exception. - - drive, tail = os.path.splitdrive(head) - #if sys.platform is 'win32' and not drive: - # if not directory: - # raise OSError, 'No drive letter supplied for absolute path.' - # return directory.root() - dir = Dir(tail, ParentOfRoot()) - dir.path = drive + dir.path - dir.path_ = drive + dir.path_ - dir.abspath = drive + dir.abspath - dir.abspath_ = drive + dir.abspath_ - dir.srcpath = dir.path - return self.Root.setdefault(drive, dir) - if head: - # Recursively look up our parent directories. - directory = self.__doLookup(Dir, head, directory) + path_comp = string.split(name, os.sep) + drive, path_first = os.path.splitdrive(path_comp[0]) + if not path_first: + # Absolute path + drive_path = _my_normcase(drive) + try: + directory = self.Root[drive_path] + except KeyError: + dir = Dir(drive, ParentOfRoot()) + dir.path = dir.path + os.sep + dir.abspath = dir.abspath + os.sep + dir.srcpath = dir.srcpath + os.sep + self.Root[drive_path] = dir + directory = dir + path_comp = path_comp[1:] else: - # This path looks like a relative path. No leading slash or drive - # letter. Therefore, we will look up this path relative to the - # supplied top-level directory. - assert directory, "Tried to lookup a node by relative path with no top-level directory supplied." - ret = directory.entries.setdefault(tail, fsclass(tail, directory)) - if fsclass.__name__ == 'Entry': - # If they were looking up a generic entry, then - # whatever came back is all right. - return ret - if ret.__class__.__name__ == 'Entry': - # They were looking up a File or Dir but found a - # generic entry. Transform the node. - ret.__class__ = fsclass - ret._morph() - return ret - if not isinstance(ret, fsclass): - raise TypeError, "Tried to lookup %s '%s' as a %s." % \ - (ret.__class__.__name__, str(ret), fsclass.__name__) + path_comp = [ path_first, ] + path_comp[1:] + # Lookup the directory + for path_name in path_comp[:-1]: + path_norm = _my_normcase(path_name) + try: + directory = self.__checkClass(directory.entries[path_norm], + Dir) + except KeyError: + dir_temp = Dir(path_name, directory) + directory.entries[path_norm] = dir_temp + directory = dir_temp + file_name = _my_normcase(path_comp[-1]) + try: + ret = self.__checkClass(directory.entries[file_name], fsclass) + except KeyError: + ret = fsclass(path_comp[-1], directory) + directory.entries[file_name] = ret return ret def __transformPath(self, name, directory): @@ -246,10 +184,10 @@ class FS: self.__setTopLevelDir() if name[0] == '#': directory = self.Top - name = os.path.join(os.path.normpath('./'), name[1:]) + name = os.path.join('./', name[1:]) elif not directory: directory = self._cwd - return (name, directory) + return (os.path.normpath(name), directory) def chdir(self, dir): """Change the current working directory for lookups. @@ -335,18 +273,18 @@ class Entry(SCons.Node.Node): assert directory, "A directory must be provided" self.duplicate = directory.duplicate - self.abspath = os.path.join(directory.abspath, name) - + self.abspath = directory.abspath_ + name if str(directory.path) == '.': self.path = name else: - self.path = os.path.join(directory.path, name) + self.path = directory.path_ + name self.path_ = self.path self.abspath_ = self.abspath self.dir = directory self.use_signature = 1 self.__doSrcpath(self.duplicate) + self.srcpath_ = self.srcpath def get_dir(self): return self.dir @@ -359,7 +297,7 @@ class Entry(SCons.Node.Node): if str(self.dir.srcpath) == '.': self.srcpath = self.name else: - self.srcpath = os.path.join(self.dir.srcpath, self.name) + self.srcpath = self.dir.srcpath_ + self.name def __str__(self): """A FS node's string representation is its path name.""" @@ -371,6 +309,13 @@ class Entry(SCons.Node.Node): def exists(self): return os.path.exists(str(self)) + def cached_exists(self): + try: + return self.exists_flag + except AttributeError: + self.exists_flag = self.exists() + return self.exists_flag + def current(self): """If the underlying path doesn't exist, we know the node is not current without even checking the signature, so return 0. @@ -415,15 +360,13 @@ class Dir(Entry): into the file system tree. Specify that directories (this node) don't use signatures for currency calculation.""" - self.path_ = os.path.join(self.path, '') - self.abspath_ = os.path.join(self.abspath, '') + self.path_ = self.path + os.sep + self.abspath_ = self.abspath + os.sep + self.srcpath_ = self.srcpath + os.sep - self.entries = PathDict() + self.entries = {} self.entries['.'] = self - if hasattr(self, 'dir'): - self.entries['..'] = self.dir - else: - self.entries['..'] = None + self.entries['..'] = self.dir self.use_signature = None self.builder = 1 self._sconsign = None @@ -435,12 +378,14 @@ class Dir(Entry): def adjust_srcpath(self, duplicate): Entry.adjust_srcpath(self, duplicate) + self.srcpath_ = self.srcpath + os.sep self.__doReparent(duplicate) def link(self, srcdir, duplicate): """Set this directory as the build directory for the supplied source directory.""" self.srcpath = srcdir.path + self.srcpath_ = srcdir.path_ self.__doReparent(duplicate) def up(self): @@ -502,6 +447,7 @@ class Dir(Entry): return self._sconsign + # XXX TODO? # rfile # precious @@ -592,24 +538,25 @@ class File(Entry): # ensure that the directories for this node are # created. - listPaths = [] - strPath = self.abspath - while 1: - strPath, strFile = os.path.split(strPath) - if os.path.exists(strPath): + listDirs = [] + parent=self.dir + while parent: + if parent.cached_exists(): break - listPaths.append(strPath) - if not strFile: - break - listPaths.reverse() - for strPath in listPaths: + listDirs.append(parent) + parent = parent.up() + listDirs.reverse() + for dirnode in listDirs: try: - os.mkdir(strPath) + os.mkdir(dirnode.abspath) + dirnode.exists_flag = 1 except OSError: pass def build(self): self.__createDir() Entry.build(self) + self.exists_flag = self.exists() default_fs = FS() + diff --git a/src/engine/SCons/Node/FSTests.py b/src/engine/SCons/Node/FSTests.py index c9d17a71..1ac5be89 100644 --- a/src/engine/SCons/Node/FSTests.py +++ b/src/engine/SCons/Node/FSTests.py @@ -403,7 +403,16 @@ class FSTestCase(unittest.TestCase): fs.chdir(fs.Dir('../..')) assert str(fs.getcwd()) == test.workdir, str(fs.getcwd()) - #XXX test exists() + f1 = fs.File(test.workpath("do_i_exist")) + assert not f1.exists() + test.write("do_i_exist","\n") + assert f1.exists() + assert f1.cached_exists() + test.unlink("do_i_exist") + assert not f1.exists() + assert f1.cached_exists() + f1.build() + assert not f1.cached_exists() #XXX test current() for directories diff --git a/src/engine/SCons/Scanner/CTests.py b/src/engine/SCons/Scanner/CTests.py index 70fc2b47..d8386430 100644 --- a/src/engine/SCons/Scanner/CTests.py +++ b/src/engine/SCons/Scanner/CTests.py @@ -138,8 +138,8 @@ 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)) +def make_node(filename, fs=SCons.Node.FS.default_fs): + return fs.File(test.workpath(filename)) # define some tests: @@ -221,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(make_node('fa.cpp'), None) + deps1 = s.instance(env).scan(fs.File('fa.cpp'), None) fs.chdir(fs.Dir('subdir')) - deps2 = s.instance(env).scan(make_node('fa.cpp'), None) + deps2 = s.instance(env).scan(fs.File('#fa.cpp'), None) headers1 = ['include/fa.h', 'include/fb.h'] headers2 = ['subdir/include/fa.h', 'subdir/include/fb.h'] deps_match(self, deps1, headers1) @@ -231,12 +231,12 @@ class CScannerTestCase8(unittest.TestCase): class CScannerTestCase9(unittest.TestCase): def runTest(self): + test.write('fa.h','\n') fs = SCons.Node.FS.FS(test.workpath('')) s = SCons.Scanner.C.CScan(fs=fs) env = DummyEnvironment([]) - test.write('fa.h','\n') - deps = s.instance(env).scan(make_node('fa.cpp'), None) - deps_match(self, deps, [ test.workpath('fa.h') ]) + deps = s.instance(env).scan(fs.File('fa.cpp'), None) + deps_match(self, deps, [ 'fa.h' ]) test.unlink('fa.h') class CScannerTestCase10(unittest.TestCase): @@ -246,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(make_node('include/fa.cpp'), None) - deps_match(self, deps, [ test.workpath('include/fa.h'), test.workpath('include/fb.h') ]) + deps = s.instance(env).scan(fs.File('#include/fa.cpp'), None) + deps_match(self, deps, [ 'include/fa.h', 'include/fb.h' ]) test.unlink('include/fa.cpp') def suite(): diff --git a/src/engine/SCons/Scanner/__init__.py b/src/engine/SCons/Scanner/__init__.py index 52eae8e0..671eba3c 100644 --- a/src/engine/SCons/Scanner/__init__.py +++ b/src/engine/SCons/Scanner/__init__.py @@ -137,7 +137,7 @@ class Recursive(Base): """ nodes = [node] - seen = [node] + seen = {node : 0} deps = [] while nodes: n = nodes.pop(0) @@ -145,9 +145,10 @@ class Recursive(Base): d = self.function(n, env, self.argument) else: d = self.function(n, env) - d = filter(lambda x, seen=seen: x not in seen, d) + d = filter(lambda x, seen=seen: not seen.has_key(x), d) if d: deps.extend(d) - seen.extend(d) nodes.extend(d) + for n in d: + seen[n] = 0 return deps diff --git a/src/engine/SCons/Util.py b/src/engine/SCons/Util.py index f4d5c2a9..a207ffc5 100644 --- a/src/engine/SCons/Util.py +++ b/src/engine/SCons/Util.py @@ -271,7 +271,7 @@ def find_file(filename, paths, 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()): + (isinstance(node, SCons.Node.FS.Entry) and node.cached_exists()): retval = node break except TypeError: @@ -317,7 +317,7 @@ class VarInterpolator: suffix ='' dict[self.dest] = map(lambda x, suff=suffix, pref=prefix: \ - pref + os.path.normpath(str(x)) + suff, + pref + str(x) + suff, src) def instance(self, dir, fs): diff --git a/src/engine/SCons/UtilTests.py b/src/engine/SCons/UtilTests.py index 73949d9e..e9e763ca 100644 --- a/src/engine/SCons/UtilTests.py +++ b/src/engine/SCons/UtilTests.py @@ -166,7 +166,7 @@ class UtilTestCase(unittest.TestCase): test.write('./foo', 'Some file\n') fs = SCons.Node.FS.FS(test.workpath("")) os.chdir(test.workpath("")) # FS doesn't like the cwd to be something other than it's root - node_derived = fs.File(test.workpath('./bar/baz')) + node_derived = fs.File(test.workpath('bar/baz')) node_derived.builder_set(1) # Any non-zero value. paths = map(fs.Dir, ['.', './bar']) nodes = [find_file('foo', paths, fs.File), -- 2.26.2