Merged revisions 1907-1940,1942-1967 via svnmerge from
[scons.git] / src / engine / SCons / Node / __init__.py
index 338df0783b76640b678ac1b114e7941f4939e146..f550b5b7cebbc29c8c8c957722aabc5e40bb02e8 100644 (file)
@@ -44,12 +44,15 @@ be able to depend on any other type of "thing."
 
 __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__"
 
-
+import SCons.compat
 
 import copy
 import string
+import UserList
 
 from SCons.Debug import logInstanceCreation
+import SCons.Executor
+import SCons.Memoize
 import SCons.SConsign
 import SCons.Util
 
@@ -60,14 +63,23 @@ import SCons.Util
 # it has no builder of its own.  The canonical example is a file
 # system directory, which is only up to date if all of its children
 # were up to date.
+no_state = 0
 pending = 1
 executing = 2
 up_to_date = 3
 executed = 4
 failed = 5
-stack = 6 # nodes that are in the current Taskmaster execution stack
 
-# controls whether implicit depedencies are cached:
+StateString = {
+    0 : "0",
+    1 : "pending",
+    2 : "executing",
+    3 : "up_to_date",
+    4 : "executed",
+    5 : "failed",
+}
+
+# controls whether implicit dependencies are cached:
 implicit_cache = 0
 
 # controls whether implicit dep changes are ignored:
@@ -82,20 +94,86 @@ def do_nothing(node): pass
 
 Annotate = do_nothing
 
-class BuildInfo:
+# Classes for signature info for Nodes.
+
+class NodeInfoBase:
+    """
+    The generic base class for signature information for a Node.
+
+    Node subclasses should subclass NodeInfoBase to provide their own
+    logic for dealing with their own Node-specific signature information.
+    """
+    def __init__(self, node):
+        """A null initializer so that subclasses have a superclass
+        initialization method to call for future use.
+        """
+        pass
     def __cmp__(self, other):
         return cmp(self.__dict__, other.__dict__)
+    def update(self, node):
+        pass
+    def merge(self, other):
+        for key, val in other.__dict__.items():
+            self.__dict__[key] = val
+    def prepare_dependencies(self):
+        pass
+    def format(self):
+        try:
+            field_list = self.field_list
+        except AttributeError:
+            field_list = self.__dict__.keys()
+            field_list.sort()
+        fields = []
+        for field in field_list:
+            try:
+                f = getattr(self, field)
+            except AttributeError:
+                f = None
+            fields.append(str(f))
+        return string.join(fields, " ")
+
+class BuildInfoBase:
+    """
+    The generic base clasee for build information for a Node.
+
+    This is what gets stored in a .sconsign file for each target file.
+    It contains a NodeInfo instance for this node (signature information
+    that's specific to the type of Node) and direct attributes for the
+    generic build stuff we have to track:  sources, explicit dependencies,
+    implicit dependencies, and action information.
+    """
+    def __init__(self, node):
+        self.ninfo = node.NodeInfo(node)
+        self.bsourcesigs = []
+        self.bdependsigs = []
+        self.bimplicitsigs = []
+        self.bactsig = None
+    def __cmp__(self, other):
+        return cmp(self.ninfo, other.ninfo)
+    def merge(self, other):
+        for key, val in other.__dict__.items():
+            try:
+                merge = self.__dict__[key].merge
+            except (AttributeError, KeyError):
+                self.__dict__[key] = val
+            else:
+                merge(val)
 
 class Node:
     """The base Node class, for entities that we know how to
     build, or use to build other Nodes.
     """
 
+    if SCons.Memoize.use_memoizer:
+        __metaclass__ = SCons.Memoize.Memoized_Metaclass
+
+    memoizer_counters = []
+
     class Attrs:
         pass
 
     def __init__(self):
-        if __debug__: logInstanceCreation(self, 'Node')
+        if __debug__: logInstanceCreation(self, 'Node.Node')
         # Note that we no longer explicitly initialize a self.builder
         # attribute to None here.  That's because the self.builder
         # attribute may be created on-the-fly later by a subclass (the
@@ -116,43 +194,45 @@ class Node:
         self.ignore = []        # dependencies to ignore
         self.ignore_dict = {}
         self.implicit = None    # implicit (scanned) dependencies (None means not scanned yet)
-        self.waiting_parents = []
+        self.waiting_parents = {}
+        self.waiting_s_e = {}
+        self.ref_count = 0
         self.wkids = None       # Kids yet to walk, when it's an array
-        self.target_scanner = None      # explicit scanner from this node's Builder
-        self.source_scanner = None
-        self.backup_source_scanner = None
 
         self.env = None
-        self.state = None
+        self.state = no_state
         self.precious = None
+        self.noclean = 0
+        self.nocache = 0
         self.always_build = None
         self.found_includes = {}
         self.includes = None
-        self.overrides = {}     # construction variable overrides for building this node
         self.attributes = self.Attrs() # Generic place to stick information about the Node.
         self.side_effect = 0 # true iff this node is a side effect
         self.side_effects = [] # the side effects of building this target
-        self.pre_actions = []
-        self.post_actions = []
-        self.linked = 0 # is this node linked to the build directory? 
+        self.linked = 0 # is this node linked to the build directory?
+
+        self.clear_memoized_values()
 
         # Let the interface in which the build engine is embedded
         # annotate this Node with its own info (like a description of
         # what line in what file created the node, for example).
         Annotate(self)
 
+    def disambiguate(self, must_exist=None):
+        return self
+
     def get_suffix(self):
         return ''
 
-    def generate_build_dict(self):
-        """Return an appropriate dictionary of values for building
-        this Node."""
-        return {}
-
     def get_build_env(self):
-        """Fetch the appropriate Environment to build this node."""
-        executor = self.get_executor()
-        return executor.get_build_env()
+        """Fetch the appropriate Environment to build this node.
+        """
+        return self.get_executor().get_build_env()
+
+    def get_build_scanner_path(self, scanner):
+        """Fetch the appropriate scanner path for this node."""
+        return self.get_executor().get_build_scanner_path(scanner)
 
     def set_executor(self, executor):
         """Set the action executor for this node."""
@@ -166,15 +246,35 @@ class Node:
         except AttributeError:
             if not create:
                 raise
-            import SCons.Executor
-            executor = SCons.Executor.Executor(self.builder.action,
-                                               self.builder.env,
-                                               [self.builder.overrides],
-                                               [self],
-                                               self.sources)
+            try:
+                act = self.builder.action
+            except AttributeError:
+                executor = SCons.Executor.Null(targets=[self])
+            else:
+                executor = SCons.Executor.Executor(act,
+                                                   self.env or self.builder.env,
+                                                   [self.builder.overrides],
+                                                   [self],
+                                                   self.sources)
             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:
+            delattr(self, 'executor')
+        except AttributeError:
+            pass
+
     def retrieve_from_cache(self):
         """Try to retrieve the node's content from a cache
 
@@ -185,7 +285,7 @@ class Node:
         Returns true iff the node was successfully retrieved.
         """
         return 0
-        
+
     def build(self, **kw):
         """Actually build the node.
 
@@ -193,74 +293,83 @@ class Node:
         so only do thread safe stuff here. Do thread unsafe stuff in
         built().
         """
-        if not self.has_builder():
-            return
-        def errfunc(stat, node=self):
-            raise SCons.Errors.BuildError(node=node, errstr="Error %d" % stat)
+        def exitstatfunc(stat, node=self):
+            if stat:
+                msg = "Error %d" % stat
+                raise SCons.Errors.BuildError(node=node, errstr=msg)
         executor = self.get_executor()
-        apply(executor, (self, errfunc), kw)
+        apply(executor, (self, exitstatfunc), kw)
 
     def built(self):
-        """Called just after this node is sucessfully built."""
+        """Called just after this node is successfully built."""
 
         # Clear the implicit dependency caches of any Nodes
         # waiting for this Node to be built.
-        for parent in self.waiting_parents:
+        for parent in self.waiting_parents.keys():
             parent.implicit = None
             parent.del_binfo()
-        
+
         try:
-            new_binfo = self.binfo
+            new = self.binfo
         except AttributeError:
             # Node arrived here without build info; apparently it
             # doesn't need it, so don't bother calculating or storing
             # it.
-            new_binfo = None
+            new = None
 
         # Reset this Node's cached state since it was just built and
         # various state has changed.
-        save_state = self.get_state()
         self.clear()
-        self.set_state(save_state)
 
-        # Had build info, so it should be stored in the signature
-        # cache.  However, if the build info included a content
-        # signature then it should be recalculated before being
-        # stored.
-        
-        if new_binfo:
-            if hasattr(new_binfo, 'csig'):
-                new_binfo = self.gen_binfo()  # sets self.binfo
+        if new:
+            # It had build info, so it should be stored in the signature
+            # cache.  However, if the build info included a content
+            # signature then it must be recalculated before being stored.
+            if hasattr(new.ninfo, 'csig'):
+                self.get_csig()
             else:
-                self.binfo = new_binfo
-            self.store_info(new_binfo)
+                new.ninfo.update(self)
+                self.binfo = new
+            self.store_info(self.binfo)
+
+    def add_to_waiting_s_e(self, node):
+        self.waiting_s_e[node] = 1
 
     def add_to_waiting_parents(self, node):
-        self.waiting_parents.append(node)
+        """
+        Returns the number of nodes added to our waiting parents list:
+        1 if we add a unique waiting parent, 0 if not.  (Note that the
+        returned values are intended to be used to increment a reference
+        count, so don't think you can "clean up" this function by using
+        True and False instead...)
+        """
+        wp = self.waiting_parents
+        if wp.has_key(node):
+            result = 0
+        else:
+            result = 1
+        wp[node] = 1
+        return result
 
     def call_for_all_waiting_parents(self, func):
         func(self)
-        for parent in self.waiting_parents:
+        for parent in self.waiting_parents.keys():
             parent.call_for_all_waiting_parents(func)
 
     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()
+        self.waiting_parents = {}
 
     def clear(self):
         """Completely clear a Node of all its cached state (so that it
         can be re-evaluated by interfaces that do continuous integration
         builds).
         """
-        self.set_state(None)
+        self.clear_memoized_values()
+        self.executor_cleanup()
         self.del_binfo()
-        self.del_cinfo()
         try:
             delattr(self, '_calculated_sig')
         except AttributeError:
@@ -269,21 +378,14 @@ class Node:
         self.found_includes = {}
         self.implicit = None
 
-        self.waiting_parents = []
+    def clear_memoized_values(self):
+        self._memo = {}
 
     def visited(self):
         """Called just after this node has been visited
         without requiring a build.."""
         pass
 
-    def depends_on(self, nodes):
-        """Does this node depend on any of 'nodes'?"""
-        for node in nodes:
-            if node in self.children():
-                return 1
-
-        return 0
-
     def builder_set(self, builder):
         self.builder = builder
 
@@ -307,6 +409,29 @@ class Node:
             b = self.builder
         return not b is None
 
+    def set_explicit(self, is_explicit):
+        self.is_explicit = is_explicit
+
+    def has_explicit_builder(self):
+        """Return whether this Node has an explicit builder
+
+        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)."""
+        try:
+            return self.is_explicit
+        except AttributeError:
+            self.is_explicit = None
+            return self.is_explicit
+
+    def get_builder(self, default_builder=None):
+        """Return the set builder, or a specified default value"""
+        try:
+            return self.builder
+        except AttributeError:
+            return default_builder
+
     multiple_side_effect_has_builder = has_builder
 
     def is_derived(self):
@@ -334,7 +459,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.
 
@@ -344,7 +469,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
@@ -356,61 +481,62 @@ class Node:
 
         # Give the scanner a chance to select a more specific scanner
         # for this Node.
-        scanner = scanner.select(self)
-
-        try:
-            recurse = scanner.recursive
-        except AttributeError:
-            recurse = None
+        #scanner = scanner.select(self)
 
         nodes = [self]
         seen = {}
         seen[self] = 1
         deps = []
         while nodes:
-           n = nodes.pop(0)
-           d = filter(lambda x, seen=seen: not seen.has_key(x),
-                      n.get_found_includes(env, scanner, target))
-           if d:
-               deps.extend(d)
-               for n in d:
-                   seen[n] = 1
-               if recurse:
-                   nodes.extend(d)
+            n = nodes.pop(0)
+            d = filter(lambda x, seen=seen: not seen.has_key(x),
+                       n.get_found_includes(env, scanner, path))
+            if d:
+                deps.extend(d)
+                for n in d:
+                    seen[n] = 1
+                nodes.extend(scanner.recurse_nodes(d))
 
         return deps
 
-    # cache used to make implicit_factory fast.
-    implicit_factory_cache = {}
-    
-    def implicit_factory(self, path):
-        """
-        Turn a cache implicit dependency path into a node.
-        This is called so many times that doing caching
-        here is a significant performance boost.
-        """
-        try:
-            return self.implicit_factory_cache[path]
-        except KeyError:
-            n = self.builder.source_factory(path)
-            self.implicit_factory_cache[path] = n
-            return n
+    def get_env_scanner(self, env, kw={}):
+        return env.get_scanner(self.scanner_key())
+
+    def get_target_scanner(self):
+        return self.builder.target_scanner
 
     def get_source_scanner(self, node):
         """Fetch the source scanner for the specified node
 
         NOTE:  "self" is the target being built, "node" is
         the source file for which we want to fetch the scanner.
+
+        Implies self.has_builder() is true; again, expect to only be
+        called from locations where this is already verified.
+
+        This function may be called very often; it attempts to cache
+        the scanner found to improve performance.
         """
-        if self.source_scanner:
-            return self.source_scanner
+        scanner = None
         try:
             scanner = self.builder.source_scanner
-            if scanner:
-                return scanner
         except AttributeError:
             pass
-        return node.backup_source_scanner or None
+        if not scanner:
+            # The builder didn't have an explicit scanner, so go look up
+            # a scanner from env['SCANNERS'] based on the node's scanner
+            # key (usually the file extension).
+            scanner = self.get_env_scanner(self.get_build_env())
+        if scanner:
+            scanner = scanner.select(node)
+        return scanner
+
+    def add_to_implicit(self, deps):
+        if not hasattr(self, 'implicit') or self.implicit is None:
+            self.implicit = []
+            self.implicit_dict = {}
+            self._children_reset()
+        self._add_child(self.implicit, self.implicit_dict, deps)
 
     def scan(self):
         """Scan this node's dependents for implicit dependencies."""
@@ -431,48 +557,77 @@ class Node:
         if implicit_cache and not implicit_deps_changed:
             implicit = self.get_stored_implicit()
             if implicit is not None:
-                implicit = map(self.implicit_factory, implicit)
-                self._add_child(self.implicit, self.implicit_dict, implicit)
+                factory = build_env.get_factory(self.builder.source_factory)
+                nodes = []
+                for i in implicit:
+                    try:
+                        n = factory(i)
+                    except TypeError:
+                        # The implicit dependency was cached as one type
+                        # of Node last time, but the configuration has
+                        # changed (probably) and it's a different type
+                        # this time.  Just ignore the mismatch and go
+                        # with what our current configuration says the
+                        # Node is.
+                        pass
+                    else:
+                        nodes.append(n)
+                self._add_child(self.implicit, self.implicit_dict, nodes)
                 calc = build_env.get_calculator()
-                if implicit_deps_unchanged or self.current(calc, scan=0):
+                if implicit_deps_unchanged or self.current(calc):
                     return
-                else:
-                    # one of this node's sources has changed, so
-                    # we need to recalculate the implicit deps,
-                    # and the bsig:
-                    self.implicit = []
-                    self.implicit_dict = {}
-                    self._children_reset()
-                    self.del_binfo()
-
-        for child in self.children(scan=0):
-            scanner = self.get_source_scanner(child)
-            if scanner:
-                deps = child.get_implicit_deps(build_env, scanner, self)
-                self._add_child(self.implicit, self.implicit_dict, deps)
-
-        # scan this node itself for implicit dependencies
-        deps = self.get_implicit_deps(build_env, self.target_scanner, self)
-        self._add_child(self.implicit, self.implicit_dict, deps)
+                # one of this node's sources has changed, so
+                # we need to recalculate the implicit deps,
+                # and the bsig:
+                self.implicit = []
+                self.implicit_dict = {}
+                self._children_reset()
+                self.del_binfo()
 
-        # XXX See note above re: --implicit-cache.
-        #if implicit_cache:
-        #    self.store_implicit()
+        executor = self.get_executor()
+
+        # Have the executor scan the sources.
+        executor.scan_sources(self.builder.source_scanner)
+
+        # If there's a target scanner, have the executor scan the target
+        # node itself and associated targets that might be built.
+        scanner = self.get_target_scanner()
+        if scanner:
+            executor.scan_targets(scanner)
 
     def scanner_key(self):
         return None
 
+    def select_scanner(self, scanner):
+        """Selects a scanner for this Node.
+
+        This is a separate method so it can be overridden by Node
+        subclasses (specifically, Node.FS.Dir) that *must* use their
+        own Scanner and don't select one the Scanner.Selector that's
+        configured for the target.
+        """
+        return scanner.select(self)
+
     def env_set(self, env, safe=0):
         if safe and self.env:
             return
         self.env = env
 
+    #
+    # SIGNATURE SUBSYSTEM
+    #
+
+    NodeInfo = NodeInfoBase
+    BuildInfo = BuildInfoBase
+
     def calculator(self):
         import SCons.Defaults
         
         env = self.env or SCons.Defaults.DefaultEnvironment()
         return env.get_calculator()
 
+    memoizer_counters.append(SCons.Memoize.CountValue('calc_signature'))
+
     def calc_signature(self, calc=None):
         """
         Select and calculate the appropriate build signature for a node.
@@ -482,39 +637,43 @@ class Node:
         returns - the signature
         """
         try:
-            return self._calculated_sig
-        except AttributeError:
-            if self.is_derived():
-                import SCons.Defaults
-                
-                env = self.env or SCons.Defaults.DefaultEnvironment()
-                if env.use_build_signature():
-                    sig = self.calc_bsig(calc)
-                else:
-                    sig = self.calc_csig(calc)
-            elif not self.rexists():
-                sig = None
+            return self._memo['calc_signature']
+        except KeyError:
+            pass
+        if self.is_derived():
+            import SCons.Defaults
+
+            env = self.env or SCons.Defaults.DefaultEnvironment()
+            if env.use_build_signature():
+                result = self.get_bsig(calc)
             else:
-                sig = self.calc_csig(calc)
-            self._calculated_sig = sig
-            return sig
+                result = self.get_csig(calc)
+        elif not self.rexists():
+            result = None
+        else:
+            result = self.get_csig(calc)
+        self._memo['calc_signature'] = result
+        return result
+
+    def new_ninfo(self):
+        return self.NodeInfo(self)
 
     def new_binfo(self):
-        return BuildInfo()
+        return self.BuildInfo(self)
 
-    def del_binfo(self):
-        """Delete the bsig from this node."""
+    def get_binfo(self):
         try:
-            delattr(self, 'binfo')
+            return self.binfo
         except AttributeError:
-            pass
+            self.binfo = self.new_binfo()
+            return self.binfo
 
-    def calc_bsig(self, calc=None):
+    def del_binfo(self):
+        """Delete the build info from this node."""
         try:
-            return self.binfo.bsig
+            delattr(self, 'binfo')
         except AttributeError:
-            self.binfo = self.gen_binfo(calc)
-            return self.binfo.bsig
+            pass
 
     def gen_binfo(self, calc=None, scan=1):
         """
@@ -534,63 +693,64 @@ class Node:
         if calc is None:
             calc = self.calculator()
 
-        binfo = self.new_binfo()
+        binfo = self.get_binfo()
 
         if scan:
             self.scan()
 
-        sources = self.filter_ignore(self.sources)
-        depends = self.filter_ignore(self.depends)
-        if self.implicit is None:
-            implicit = []
-        else:
-            implicit = self.filter_ignore(self.implicit)
-
+        executor = self.get_executor()
         def calc_signature(node, calc=calc):
             return node.calc_signature(calc)
-        sourcesigs = map(calc_signature, sources)
+
+        sources = executor.get_unignored_sources(self.ignore)
+        sourcesigs = executor.process_sources(calc_signature, self.ignore)
+
+        depends = self.depends
+        implicit = self.implicit or []
+
+        if self.ignore:
+            depends = filter(self.do_not_ignore, depends)
+            implicit = filter(self.do_not_ignore, implicit)
+
         dependsigs = map(calc_signature, depends)
         implicitsigs = map(calc_signature, implicit)
 
         sigs = sourcesigs + dependsigs + implicitsigs
 
         if self.has_builder():
-            executor = self.get_executor()
-            binfo.bact = executor.strfunction()
+            binfo.bact = str(executor)
             binfo.bactsig = calc.module.signature(executor)
             sigs.append(binfo.bactsig)
 
-        binfo.bsources = map(str, sources)
-        binfo.bdepends = map(str, depends)
-        binfo.bimplicit = map(str, implicit)
+        binfo.bsources = sources
+        binfo.bdepends = depends
+        binfo.bimplicit = implicit
 
         binfo.bsourcesigs = sourcesigs
         binfo.bdependsigs = dependsigs
         binfo.bimplicitsigs = implicitsigs
 
-        binfo.bsig = calc.module.collect(filter(None, sigs))
+        binfo.ninfo.bsig = calc.module.collect(filter(None, sigs))
 
         return binfo
 
-    def del_cinfo(self):
+    def get_bsig(self, calc=None):
+        binfo = self.get_binfo()
         try:
-            del self.binfo.csig
+            return binfo.ninfo.bsig
         except AttributeError:
-            pass
+            self.binfo = self.gen_binfo(calc)
+            return self.binfo.ninfo.bsig
 
-    def calc_csig(self, calc=None):
+    def get_csig(self, calc=None):
+        binfo = self.get_binfo()
         try:
-            binfo = self.binfo
-        except AttributeError:
-            binfo = self.binfo = self.new_binfo()
-        try:
-            return binfo.csig
+            return binfo.ninfo.csig
         except AttributeError:
             if calc is None:
                 calc = self.calculator()
-            binfo.csig = calc.module.signature(self)
-            self.store_info(binfo)
-            return binfo.csig
+            csig = binfo.ninfo.csig = calc.module.signature(self)
+            return csig
 
     def store_info(self, obj):
         """Make the build signature permanent (that is, store it in the
@@ -604,10 +764,26 @@ class Node:
         """Fetch the stored implicit dependencies"""
         return None
 
+    #
+    #
+    #
+
     def set_precious(self, precious = 1):
         """Set the Node's precious value."""
         self.precious = precious
 
+    def set_noclean(self, noclean = 1):
+        """Set the Node's noclean value."""
+        # Make sure noclean is an integer so the --debug=stree
+        # output in Util.py can use it as an index.
+        self.noclean = noclean and 1 or 0
+
+    def set_nocache(self, nocache = 1):
+        """Set the Node's nocache value."""
+        # Make sure nocache is an integer so the --debug=stree
+        # output in Util.py can use it as an index.
+        self.nocache = nocache and 1 or 0
+
     def set_always_build(self, always_build = 1):
         """Set the Node's always_build value."""
         self.always_build = always_build
@@ -616,23 +792,28 @@ class Node:
         """Does this node exists?"""
         # All node exist by default:
         return 1
-    
+
     def rexists(self):
         """Does this node exist locally or in a repositiory?"""
         # There are no repositories by default:
         return self.exists()
+
+    def missing(self):
+        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
@@ -700,33 +881,15 @@ class Node:
             self.wkids.append(wkid)
 
     def _children_reset(self):
-        try:
-            delattr(self, '_children')
-        except AttributeError:
-            pass
+        self.clear_memoized_values()
+        # 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(self, scan=1):
-        """Return a list of the node's direct children, minus those
-        that are ignored by this node."""
-        if scan:
-            self.scan()
-        try:
-            return self._children
-        except AttributeError:
-            c = self.all_children(scan=0)
-            self._children = self.filter_ignore(c)
-            return self._children
-
-    def all_children(self, scan=1):
-        """Return a list of all the node's direct children."""
+    def _all_children_get(self):
         # The return list may contain duplicate Nodes, especially in
         # source trees where there are a lot of repeated #includes
         # of a tangle of .h files.  Profiling shows, however, that
@@ -744,13 +907,37 @@ class Node:
         # using dictionary keys, lose the order, and the only ordered
         # dictionary patterns I found all ended up using "not in"
         # internally anyway...)
-        if scan:
-            self.scan()
         if self.implicit is None:
             return self.sources + self.depends
         else:
             return self.sources + self.depends + self.implicit
 
+    memoizer_counters.append(SCons.Memoize.CountValue('_children_get'))
+
+    def _children_get(self):
+        try:
+            return self._memo['children_get']
+        except KeyError:
+            pass
+        children = self._all_children_get()
+        if self.ignore:
+            children = filter(self.do_not_ignore, children)
+        self._memo['children_get'] = children
+        return children
+
+    def all_children(self, scan=1):
+        """Return a list of all the node's direct children."""
+        if scan:
+            self.scan()
+        return self._all_children_get()
+
+    def children(self, scan=1):
+        """Return a list of the node's direct children, minus those
+        that are ignored by this node."""
+        if scan:
+            self.scan()
+        return self._children_get()
+
     def set_state(self, state):
         self.state = state
 
@@ -770,6 +957,8 @@ class Node:
         rebind their current() method to this method."""
         # Allow the children to calculate their signatures.
         self.binfo = self.gen_binfo(calc)
+        if self.always_build:
+            return None
         state = 0
         for kid in self.children(None):
             s = kid.get_state()
@@ -782,16 +971,6 @@ class Node:
         the command interpreter literally."""
         return 1
 
-    def add_pre_action(self, act):
-        """Adds an Action performed on this Node only before
-        building it."""
-        self.pre_actions.append(act)
-
-    def add_post_action(self, act):
-        """Adds and Action performed on this Node only after
-        building it."""
-        self.post_actions.append(act)
-
     def render_include_tree(self):
         """
         Return a text representation, suitable for displaying to the
@@ -801,8 +980,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
@@ -866,62 +1046,68 @@ class Node:
         if not self.exists():
             return "building `%s' because it doesn't exist\n" % self
 
+        if self.always_build:
+            return "rebuilding `%s' because AlwaysBuild() is specified\n" % self
+
         old = self.get_stored_info()
         if old is None:
             return None
-
-        def dictify(result, kids, sigs):
-            for k, s in zip(kids, sigs):
-                result[k] = s
+        old.prepare_dependencies()
 
         try:
-            old_bkids = old.bsources + old.bdepends + old.bimplicit
+            old_bkids    = old.bsources    + old.bdepends    + old.bimplicit
+            old_bkidsigs = old.bsourcesigs + old.bdependsigs + old.bimplicitsigs
         except AttributeError:
             return "Cannot explain why `%s' is being rebuilt: No previous build information found\n" % self
 
-        osig = {}
-        dictify(osig, old.bsources, old.bsourcesigs)
-        dictify(osig, old.bdepends, old.bdependsigs)
-        dictify(osig, old.bimplicit, old.bimplicitsigs)
+        new = self.get_binfo()
+
+        new_bkids    = new.bsources    + new.bdepends    + new.bimplicit
+        new_bkidsigs = new.bsourcesigs + new.bdependsigs + new.bimplicitsigs
 
-        new_bsources = map(str, self.binfo.bsources)
-        new_bdepends = map(str, self.binfo.bdepends)
-        new_bimplicit = map(str, self.binfo.bimplicit)
+        osig = dict(zip(old_bkids, old_bkidsigs))
+        nsig = dict(zip(new_bkids, new_bkidsigs))
 
-        nsig = {}
-        dictify(nsig, new_bsources, self.binfo.bsourcesigs)
-        dictify(nsig, new_bdepends, self.binfo.bdependsigs)
-        dictify(nsig, new_bimplicit, self.binfo.bimplicitsigs)
+        # The sources and dependencies we'll want to report are all stored
+        # as relative paths to this target's directory, but we want to
+        # report them relative to the top-level SConstruct directory,
+        # so we only print them after running them through this lambda
+        # to turn them into the right relative Node and then return
+        # its string.
+        stringify = lambda s, E=self.dir.Entry: str(E(s))
 
-        new_bkids = new_bsources + new_bdepends + new_bimplicit
-        lines = map(lambda x: "`%s' is no longer a dependency\n" % x,
-                    filter(lambda x, nk=new_bkids: not x in nk, old_bkids))
+        lines = []
+
+        removed = filter(lambda x, nk=new_bkids: not x in nk, old_bkids)
+        if removed:
+            removed = map(stringify, removed)
+            fmt = "`%s' is no longer a dependency\n"
+            lines.extend(map(lambda s, fmt=fmt: fmt % s, removed))
 
         for k in new_bkids:
             if not k in old_bkids:
-                lines.append("`%s' is a new dependency\n" % k)
+                lines.append("`%s' is a new dependency\n" % stringify(k))
             elif osig[k] != nsig[k]:
-                lines.append("`%s' changed\n" % k)
+                lines.append("`%s' changed\n" % stringify(k))
 
         if len(lines) == 0 and old_bkids != new_bkids:
             lines.append("the dependency order changed:\n" +
-                         "%sold: %s\n" % (' '*15, old_bkids) +
-                         "%snew: %s\n" % (' '*15, new_bkids))
+                         "%sold: %s\n" % (' '*15, map(stringify, old_bkids)) +
+                         "%snew: %s\n" % (' '*15, map(stringify, new_bkids)))
 
         if len(lines) == 0:
-            newact, newactsig = self.binfo.bact, self.binfo.bactsig
             def fmt_with_title(title, strlines):
                 lines = string.split(strlines, '\n')
                 sep = '\n' + ' '*(15 + len(title))
                 return ' '*15 + title + string.join(lines, sep) + '\n'
-            if old.bactsig != newactsig:
-                if old.bact == newact:
+            if old.bactsig != new.bactsig:
+                if old.bact == new.bact:
                     lines.append("the contents of the build action changed\n" +
-                                 fmt_with_title('action: ', newact))
+                                 fmt_with_title('action: ', new.bact))
                 else:
                     lines.append("the build action changed:\n" +
                                  fmt_with_title('old: ', old.bact) +
-                                 fmt_with_title('new: ', newact))
+                                 fmt_with_title('new: ', new.bact))
 
         if len(lines) == 0:
             return "rebuilding `%s' for unknown reasons\n" % self
@@ -933,6 +1119,20 @@ class Node:
             lines = ["%s:\n" % preamble] + lines
             return string.join(lines, ' '*11)
 
+l = [1]
+ul = UserList.UserList([2])
+try:
+    l.extend(ul)
+except TypeError:
+    def NodeList(l):
+        return l
+else:
+    class NodeList(UserList.UserList):
+        def __str__(self):
+            return str(map(str, self.data))
+del l
+del ul
+
 def get_children(node, parent): return node.children()
 def ignore_cycle(node, stack): pass
 def do_nothing(node, parent): pass