src/engine/SCons/Node/__init__.py

   1 """SCons.Node
   2
   3 The Node package for the SCons software construction utility.
   4
   5 This is, in many ways, the heart of SCons.
   6
   7 A Node is where we encapsulate all of the dependency information about
   8 any thing that SCons can build, or about any thing which SCons can use
   9 to build some other thing.  The canonical "thing," of course, is a file,
  10 but a Node can also represent something remote (like a web page) or
  11 something completely abstract (like an Alias).
  12
  13 Each specific type of "thing" is specifically represented by a subclass
  14 of the Node base class:  Node.FS.File for files, Node.Alias for aliases,
  15 etc.  Dependency information is kept here in the base class, and
  16 information specific to files/aliases/etc. is in the subclass.  The
  17 goal, if we've done this correctly, is that any type of "thing" should
  18 be able to depend on any other type of "thing."
  19
  20 """
  21
  22 #
  23 # __COPYRIGHT__
  24 #
  25 # Permission is hereby granted, free of charge, to any person obtaining
  26 # a copy of this software and associated documentation files (the
  27 # "Software"), to deal in the Software without restriction, including
  28 # without limitation the rights to use, copy, modify, merge, publish,
  29 # distribute, sublicense, and/or sell copies of the Software, and to
  30 # permit persons to whom the Software is furnished to do so, subject to
  31 # the following conditions:
  32 #
  33 # The above copyright notice and this permission notice shall be included
  34 # in all copies or substantial portions of the Software.
  35 #
  36 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
  37 # KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  38 # WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  39 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  40 # LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  41 # OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  42 # WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  43 #
  44
  45 __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__"
  46
  47
  48
  49 import copy
  50 import string
  51 import UserList
  52
  53 from SCons.Debug import logInstanceCreation
  54 import SCons.Executor
  55 import SCons.SConsign
  56 import SCons.Util
  57
  58 # Node states
  59 #
  60 # These are in "priority" order, so that the maximum value for any
  61 # child/dependency of a node represents the state of that node if
  62 # it has no builder of its own.  The canonical example is a file
  63 # system directory, which is only up to date if all of its children
  64 # were up to date.
  65 pending = 1
  66 executing = 2
  67 up_to_date = 3
  68 executed = 4
  69 failed = 5
  70 stack = 6 # nodes that are in the current Taskmaster execution stack
  71
  72 # controls whether implicit dependencies are cached:
  73 implicit_cache = 0
  74
  75 # controls whether implicit dep changes are ignored:
  76 implicit_deps_unchanged = 0
  77
  78 # controls whether the cached implicit deps are ignored:
  79 implicit_deps_changed = 0
  80
  81 # A variable that can be set to an interface-specific function be called
  82 # to annotate a Node with information about its creation.
  83 def do_nothing(node): pass
  84
  85 Annotate = do_nothing
  86
  87 class BuildInfo:
  88     def __cmp__(self, other):
  89         return cmp(self.__dict__, other.__dict__)
  90
  91 class Node:
  92     """The base Node class, for entities that we know how to
  93     build, or use to build other Nodes.
  94     """
  95
  96     __metaclass__ = SCons.Memoize.Memoized_Metaclass
  97
  98     class Attrs:
  99         pass
 100
 101     def __init__(self):
 102         if __debug__: logInstanceCreation(self, 'Node')
 103         # Note that we no longer explicitly initialize a self.builder
 104         # attribute to None here.  That's because the self.builder
 105         # attribute may be created on-the-fly later by a subclass (the
 106         # canonical example being a builder to fetch a file from a
 107         # source code system like CVS or Subversion).
 108
 109         # Each list of children that we maintain is accompanied by a
 110         # dictionary used to look up quickly whether a node is already
 111         # present in the list.  Empirical tests showed that it was
 112         # fastest to maintain them as side-by-side Node attributes in
 113         # this way, instead of wrapping up each list+dictionary pair in
 114         # a class.  (Of course, we could always still do that in the
 115         # future if we had a good reason to...).
 116         self.sources = []       # source files used to build node
 117         self.sources_dict = {}
 118         self.depends = []       # explicit dependencies (from Depends)
 119         self.depends_dict = {}
 120         self.ignore = []        # dependencies to ignore
 121         self.ignore_dict = {}
 122         self.implicit = None    # implicit (scanned) dependencies (None means not scanned yet)
 123         self.waiting_parents = []
 124         self.wkids = None       # Kids yet to walk, when it's an array
 125
 126         self.env = None
 127         self.state = None
 128         self.precious = None
 129         self.always_build = None
 130         self.found_includes = {}
 131         self.includes = None
 132         self.attributes = self.Attrs() # Generic place to stick information about the Node.
 133         self.side_effect = 0 # true iff this node is a side effect
 134         self.side_effects = [] # the side effects of building this target
 135         self.pre_actions = []
 136         self.post_actions = []
 137         self.linked = 0 # is this node linked to the build directory?
 138
 139         # Let the interface in which the build engine is embedded
 140         # annotate this Node with its own info (like a description of
 141         # what line in what file created the node, for example).
 142         Annotate(self)
 143
 144     def get_suffix(self):
 145         return ''
 146
 147     def get_build_env(self):
 148         """Fetch the appropriate Environment to build this node.
 149         __cacheable__"""
 150         return self.get_executor().get_build_env()
 151
 152     def get_build_scanner_path(self, scanner):
 153         """Fetch the appropriate scanner path for this node."""
 154         return self.get_executor().get_build_scanner_path(scanner)
 155
 156     def set_executor(self, executor):
 157         """Set the action executor for this node."""
 158         self.executor = executor
 159
 160     def get_executor(self, create=1):
 161         """Fetch the action executor for this node.  Create one if
 162         there isn't already one, and requested to do so."""
 163         try:
 164             executor = self.executor
 165         except AttributeError:
 166             if not create:
 167                 raise
 168             try:
 169                 act = self.builder.action
 170             except AttributeError:
 171                 executor = SCons.Executor.Null()
 172             else:
 173                 if self.pre_actions:
 174                     act = self.pre_actions + act
 175                 if self.post_actions:
 176                     act = act + self.post_actions
 177                 executor = SCons.Executor.Executor(act,
 178                                                    self.env or self.builder.env,
 179                                                    [self.builder.overrides],
 180                                                    [self],
 181                                                    self.sources)
 182             self.executor = executor
 183         return executor
 184
 185     def executor_cleanup(self):
 186         """Let the executor clean up any cached information."""
 187         try:
 188             executor = self.get_executor(create=None)
 189         except AttributeError:
 190             pass
 191         else:
 192             executor.cleanup()
 193
 194     def reset_executor(self):
 195         "Remove cached executor; forces recompute when needed."
 196         try:
 197             delattr(self, 'executor')
 198         except AttributeError:
 199             pass
 200
 201     def retrieve_from_cache(self):
 202         """Try to retrieve the node's content from a cache
 203
 204         This method is called from multiple threads in a parallel build,
 205         so only do thread safe stuff here. Do thread unsafe stuff in
 206         built().
 207
 208         Returns true iff the node was successfully retrieved.
 209         """
 210         return 0
 211
 212     def build(self, **kw):
 213         """Actually build the node.
 214
 215         This method is called from multiple threads in a parallel build,
 216         so only do thread safe stuff here. Do thread unsafe stuff in
 217         built().
 218         """
 219         def errfunc(stat, node=self):
 220             raise SCons.Errors.BuildError(node=node, errstr="Error %d" % stat)
 221         executor = self.get_executor()
 222         apply(executor, (self, errfunc), kw)
 223
 224     def built(self):
 225         """Called just after this node is successfully built."""
 226
 227         # Clear the implicit dependency caches of any Nodes
 228         # waiting for this Node to be built.
 229         for parent in self.waiting_parents:
 230             parent.implicit = None
 231             parent.del_binfo()
 232
 233         try:
 234             new_binfo = self.binfo
 235         except AttributeError:
 236             # Node arrived here without build info; apparently it
 237             # doesn't need it, so don't bother calculating or storing
 238             # it.
 239             new_binfo = None
 240
 241         # Reset this Node's cached state since it was just built and
 242         # various state has changed.
 243         self.clear()
 244
 245         # Had build info, so it should be stored in the signature
 246         # cache.  However, if the build info included a content
 247         # signature then it should be recalculated before being
 248         # stored.
 249
 250         if new_binfo:
 251             if hasattr(new_binfo, 'csig'):
 252                 new_binfo = self.gen_binfo()  # sets self.binfo
 253             else:
 254                 self.binfo = new_binfo
 255             self.store_info(new_binfo)
 256
 257     def add_to_waiting_parents(self, node):
 258         self.waiting_parents.append(node)
 259
 260     def call_for_all_waiting_parents(self, func):
 261         func(self)
 262         for parent in self.waiting_parents:
 263             parent.call_for_all_waiting_parents(func)
 264
 265     def postprocess(self):
 266         """Clean up anything we don't need to hang onto after we've
 267         been built."""
 268         self.executor_cleanup()
 269
 270     def clear(self):
 271         """Completely clear a Node of all its cached state (so that it
 272         can be re-evaluated by interfaces that do continuous integration
 273         builds).
 274         __reset_cache__
 275         """
 276         self.executor_cleanup()
 277         self.del_binfo()
 278         self.del_cinfo()
 279         try:
 280             delattr(self, '_calculated_sig')
 281         except AttributeError:
 282             pass
 283         self.includes = None
 284         self.found_includes = {}
 285         self.implicit = None
 286
 287         self.waiting_parents = []
 288
 289     def visited(self):
 290         """Called just after this node has been visited
 291         without requiring a build.."""
 292         pass
 293
 294     def depends_on(self, nodes):
 295         """Does this node depend on any of 'nodes'? __cacheable__"""
 296         return reduce(lambda D,N,C=self.children(): D or (N in C), nodes, 0)
 297
 298     def builder_set(self, builder):
 299         "__cache_reset__"
 300         self.builder = builder
 301
 302     def has_builder(self):
 303         """Return whether this Node has a builder or not.
 304
 305         In Boolean tests, this turns out to be a *lot* more efficient
 306         than simply examining the builder attribute directly ("if
 307         node.builder: ..."). When the builder attribute is examined
 308         directly, it ends up calling __getattr__ for both the __len__
 309         and __nonzero__ attributes on instances of our Builder Proxy
 310         class(es), generating a bazillion extra calls and slowing
 311         things down immensely.
 312         """
 313         try:
 314             b = self.builder
 315         except AttributeError:
 316             # There was no explicit builder for this Node, so initialize
 317             # the self.builder attribute to None now.
 318             self.builder = None
 319             b = self.builder
 320         return not b is None
 321
 322     def set_explicit(self, is_explicit):
 323         self.is_explicit = is_explicit
 324
 325     def has_explicit_builder(self):
 326         """Return whether this Node has an explicit builder
 327
 328         This allows an internal Builder created by SCons to be marked
 329         non-explicit, so that it can be overridden by an explicit
 330         builder that the user supplies (the canonical example being
 331         directories)."""
 332         try:
 333             return self.is_explicit
 334         except AttributeError:
 335             self.is_explicit = None
 336             return self.is_explicit
 337
 338     def get_builder(self, default_builder=None):
 339         """Return the set builder, or a specified default value"""
 340         try:
 341             return self.builder
 342         except AttributeError:
 343             return default_builder
 344
 345     multiple_side_effect_has_builder = has_builder
 346
 347     def is_derived(self):
 348         """
 349         Returns true iff this node is derived (i.e. built).
 350
 351         This should return true only for nodes whose path should be in
 352         the build directory when duplicate=0 and should contribute their build
 353         signatures when they are used as source files to other derived files. For
 354         example: source with source builders are not derived in this sense,
 355         and hence should not return true.
 356         __cacheable__
 357         """
 358         return self.has_builder() or self.side_effect
 359
 360     def is_pseudo_derived(self):
 361         """
 362         Returns true iff this node is built, but should use a source path
 363         when duplicate=0 and should contribute a content signature (i.e.
 364         source signature) when used as a source for other derived files.
 365         """
 366         return 0
 367
 368     def alter_targets(self):
 369         """Return a list of alternate targets for this Node.
 370         """
 371         return [], None
 372
 373     def get_found_includes(self, env, scanner, path):
 374         """Return the scanned include lines (implicit dependencies)
 375         found in this node.
 376
 377         The default is no implicit dependencies.  We expect this method
 378         to be overridden by any subclass that can be scanned for
 379         implicit dependencies.
 380         """
 381         return []
 382
 383     def get_implicit_deps(self, env, scanner, path):
 384         """Return a list of implicit dependencies for this node.
 385
 386         This method exists to handle recursive invocation of the scanner
 387         on the implicit dependencies returned by the scanner, if the
 388         scanner's recursive flag says that we should.
 389         """
 390         if not scanner:
 391             return []
 392
 393         # Give the scanner a chance to select a more specific scanner
 394         # for this Node.
 395         scanner = scanner.select(self)
 396
 397         nodes = [self]
 398         seen = {}
 399         seen[self] = 1
 400         deps = []
 401         while nodes:
 402             n = nodes.pop(0)
 403             d = filter(lambda x, seen=seen: not seen.has_key(x),
 404                        n.get_found_includes(env, scanner, path))
 405             if d:
 406                 deps.extend(d)
 407                 for n in d:
 408                     seen[n] = 1
 409                 nodes.extend(scanner.recurse_nodes(d))
 410
 411         return deps
 412
 413     def implicit_factory(self, path):
 414         """
 415         Turn a cache implicit dependency path into a node.
 416         This is called so many times that doing caching
 417         here is a significant performance boost.
 418         __cacheable__
 419         """
 420         return self.builder.source_factory(path)
 421
 422     def get_scanner(self, env, kw={}):
 423         return env.get_scanner(self.scanner_key())
 424
 425     def get_source_scanner(self, node):
 426         """Fetch the source scanner for the specified node
 427
 428         NOTE:  "self" is the target being built, "node" is
 429         the source file for which we want to fetch the scanner.
 430
 431         Implies self.has_builder() is true; again, expect to only be
 432         called from locations where this is already verified.
 433
 434         This function may be called very often; it attempts to cache
 435         the scanner found to improve performance.
 436         """
 437         scanner = None
 438         try:
 439             scanner = self.builder.source_scanner
 440         except AttributeError:
 441             pass
 442         if not scanner:
 443             # The builder didn't have an explicit scanner, so go look up
 444             # a scanner from env['SCANNERS'] based on the node's scanner
 445             # key (usually the file extension).
 446             scanner = self.get_scanner(self.get_build_env())
 447         if scanner:
 448             scanner = scanner.select(node)
 449         return scanner
 450
 451     def add_to_implicit(self, deps):
 452         if not hasattr(self, 'implicit') or self.implicit is None:
 453             self.implicit = []
 454             self.implicit_dict = {}
 455             self._children_reset()
 456         self._add_child(self.implicit, self.implicit_dict, deps)
 457
 458     def scan(self):
 459         """Scan this node's dependents for implicit dependencies."""
 460         # Don't bother scanning non-derived files, because we don't
 461         # care what their dependencies are.
 462         # Don't scan again, if we already have scanned.
 463         if not self.implicit is None:
 464             return
 465         self.implicit = []
 466         self.implicit_dict = {}
 467         self._children_reset()
 468         if not self.has_builder():
 469             return
 470
 471         build_env = self.get_build_env()
 472
 473         # Here's where we implement --implicit-cache.
 474         if implicit_cache and not implicit_deps_changed:
 475             implicit = self.get_stored_implicit()
 476             if implicit is not None:
 477                 implicit = map(self.implicit_factory, implicit)
 478                 self._add_child(self.implicit, self.implicit_dict, implicit)
 479                 calc = build_env.get_calculator()
 480                 if implicit_deps_unchanged or self.current(calc):
 481                     return
 482                 else:
 483                     # one of this node's sources has changed, so
 484                     # we need to recalculate the implicit deps,
 485                     # and the bsig:
 486                     self.implicit = []
 487                     self.implicit_dict = {}
 488                     self._children_reset()
 489                     self.del_binfo()
 490
 491         scanner = self.builder.source_scanner
 492         self.get_executor().scan(scanner)
 493
 494         # scan this node itself for implicit dependencies
 495         scanner = self.builder.target_scanner
 496         if scanner:
 497             path = self.get_build_scanner_path(scanner)
 498             deps = self.get_implicit_deps(build_env, scanner, path)
 499             self._add_child(self.implicit, self.implicit_dict, deps)
 500
 501         # XXX See note above re: --implicit-cache.
 502         #if implicit_cache:
 503         #    self.store_implicit()
 504
 505     def scanner_key(self):
 506         return None
 507
 508     def env_set(self, env, safe=0):
 509         if safe and self.env:
 510             return
 511         self.env = env
 512
 513     def calculator(self):
 514         import SCons.Defaults
 515
 516         env = self.env or SCons.Defaults.DefaultEnvironment()
 517         return env.get_calculator()
 518
 519     def calc_signature(self, calc=None):
 520         """
 521         Select and calculate the appropriate build signature for a node.
 522         __cacheable__
 523
 524         self - the node
 525         calc - the signature calculation module
 526         returns - the signature
 527         """
 528         if self.is_derived():
 529             import SCons.Defaults
 530
 531             env = self.env or SCons.Defaults.DefaultEnvironment()
 532             if env.use_build_signature():
 533                 return self.calc_bsig(calc)
 534         elif not self.rexists():
 535             return None
 536         return self.calc_csig(calc)
 537
 538     def new_binfo(self):
 539         return BuildInfo()
 540
 541     def del_binfo(self):
 542         """Delete the bsig from this node."""
 543         try:
 544             delattr(self, 'binfo')
 545         except AttributeError:
 546             pass
 547
 548     def calc_bsig(self, calc=None):
 549         try:
 550             return self.binfo.bsig
 551         except AttributeError:
 552             self.binfo = self.gen_binfo(calc)
 553             return self.binfo.bsig
 554
 555     def gen_binfo(self, calc=None, scan=1):
 556         """
 557         Generate a node's build signature, the digested signatures
 558         of its dependency files and build information.
 559
 560         node - the node whose sources will be collected
 561         cache - alternate node to use for the signature cache
 562         returns - the build signature
 563
 564         This no longer handles the recursive descent of the
 565         node's children's signatures.  We expect that they're
 566         already built and updated by someone else, if that's
 567         what's wanted.
 568         __cacheable__
 569         """
 570
 571         if calc is None:
 572             calc = self.calculator()
 573
 574         binfo = self.new_binfo()
 575
 576         if scan:
 577             self.scan()
 578
 579         executor = self.get_executor()
 580
 581         sourcelist = executor.get_source_binfo(calc)
 582         depends = self.depends
 583         implicit = self.implicit or []
 584
 585         if self.ignore:
 586             sourcelist = filter(lambda t, s=self: s.do_not_ignore(t[0]), sourcelist)
 587             depends = filter(self.do_not_ignore, depends)
 588             implicit = filter(self.do_not_ignore, implicit)
 589
 590         def calc_signature(node, calc=calc):
 591             return node.calc_signature(calc)
 592         sourcesigs = map(lambda t: t[1], sourcelist)
 593         dependsigs = map(calc_signature, depends)
 594         implicitsigs = map(calc_signature, implicit)
 595
 596         sigs = sourcesigs + dependsigs + implicitsigs
 597
 598         if self.has_builder():
 599             binfo.bact = str(executor)
 600             binfo.bactsig = calc.module.signature(executor)
 601             sigs.append(binfo.bactsig)
 602
 603         binfo.bsources = map(lambda t: t[2], sourcelist)
 604         binfo.bdepends = map(str, depends)
 605         binfo.bimplicit = map(str, implicit)
 606
 607         binfo.bsourcesigs = sourcesigs
 608         binfo.bdependsigs = dependsigs
 609         binfo.bimplicitsigs = implicitsigs
 610
 611         binfo.bsig = calc.module.collect(filter(None, sigs))
 612
 613         return binfo
 614
 615     def del_cinfo(self):
 616         try:
 617             del self.binfo.csig
 618         except AttributeError:
 619             pass
 620
 621     def calc_csig(self, calc=None):
 622         try:
 623             binfo = self.binfo
 624         except AttributeError:
 625             binfo = self.binfo = self.new_binfo()
 626         try:
 627             return binfo.csig
 628         except AttributeError:
 629             if calc is None:
 630                 calc = self.calculator()
 631             binfo.csig = calc.module.signature(self)
 632             self.store_info(binfo)
 633             return binfo.csig
 634
 635     def store_info(self, obj):
 636         """Make the build signature permanent (that is, store it in the
 637         .sconsign file or equivalent)."""
 638         pass
 639
 640     def get_stored_info(self):
 641         return None
 642
 643     def get_stored_implicit(self):
 644         """Fetch the stored implicit dependencies"""
 645         return None
 646
 647     def set_precious(self, precious = 1):
 648         """Set the Node's precious value."""
 649         self.precious = precious
 650
 651     def set_always_build(self, always_build = 1):
 652         """Set the Node's always_build value."""
 653         self.always_build = always_build
 654
 655     def exists(self):
 656         """Does this node exists?"""
 657         # All node exist by default:
 658         return 1
 659
 660     def rexists(self):
 661         """Does this node exist locally or in a repositiory?"""
 662         # There are no repositories by default:
 663         return self.exists()
 664
 665     def missing(self):
 666         """__cacheable__"""
 667         return not self.is_derived() and \
 668                not self.is_pseudo_derived() and \
 669                not self.linked and \
 670                not self.rexists()
 671
 672     def prepare(self):
 673         """Prepare for this Node to be created.
 674         The default implemenation checks that all children either exist
 675         or are derived.
 676         """
 677         l = self.depends
 678         if not self.implicit is None:
 679             l = l + self.implicit
 680         missing_sources = self.get_executor().get_missing_sources() \
 681                           + filter(lambda c: c.missing(), l)
 682         if missing_sources:
 683             desc = "Source `%s' not found, needed by target `%s'." % (missing_sources[0], self)
 684             raise SCons.Errors.StopError, desc
 685
 686     def remove(self):
 687         """Remove this Node:  no-op by default."""
 688         return None
 689
 690     def add_dependency(self, depend):
 691         """Adds dependencies."""
 692         try:
 693             self._add_child(self.depends, self.depends_dict, depend)
 694         except TypeError, e:
 695             e = e.args[0]
 696             if SCons.Util.is_List(e):
 697                 s = map(str, e)
 698             else:
 699                 s = str(e)
 700             raise SCons.Errors.UserError("attempted to add a non-Node dependency to %s:\n\t%s is a %s, not a Node" % (str(self), s, type(e)))
 701
 702     def add_ignore(self, depend):
 703         """Adds dependencies to ignore."""
 704         try:
 705             self._add_child(self.ignore, self.ignore_dict, depend)
 706         except TypeError, e:
 707             e = e.args[0]
 708             if SCons.Util.is_List(e):
 709                 s = map(str, e)
 710             else:
 711                 s = str(e)
 712             raise SCons.Errors.UserError("attempted to ignore a non-Node dependency of %s:\n\t%s is a %s, not a Node" % (str(self), s, type(e)))
 713
 714     def add_source(self, source):
 715         """Adds sources."""
 716         try:
 717             self._add_child(self.sources, self.sources_dict, source)
 718         except TypeError, e:
 719             e = e.args[0]
 720             if SCons.Util.is_List(e):
 721                 s = map(str, e)
 722             else:
 723                 s = str(e)
 724             raise SCons.Errors.UserError("attempted to add a non-Node as source of %s:\n\t%s is a %s, not a Node" % (str(self), s, type(e)))
 725
 726     def _add_child(self, collection, dict, child):
 727         """Adds 'child' to 'collection', first checking 'dict' to see
 728         if it's already present."""
 729         if type(child) is not type([]):
 730             child = [child]
 731         for c in child:
 732             if not isinstance(c, Node):
 733                 raise TypeError, c
 734         added = None
 735         for c in child:
 736             if not dict.has_key(c):
 737                 collection.append(c)
 738                 dict[c] = 1
 739                 added = 1
 740         if added:
 741             self._children_reset()
 742
 743     def add_wkid(self, wkid):
 744         """Add a node to the list of kids waiting to be evaluated"""
 745         if self.wkids != None:
 746             self.wkids.append(wkid)
 747
 748     def _children_reset(self):
 749         "__cache_reset__"
 750         # We need to let the Executor clear out any calculated
 751         # bsig info that it's cached so we can re-calculate it.
 752         self.executor_cleanup()
 753
 754     def do_not_ignore(self, node):
 755         return node not in self.ignore
 756
 757     def _all_children_get(self):
 758         # The return list may contain duplicate Nodes, especially in
 759         # source trees where there are a lot of repeated #includes
 760         # of a tangle of .h files.  Profiling shows, however, that
 761         # eliminating the duplicates with a brute-force approach that
 762         # preserves the order (that is, something like:
 763         #
 764         #       u = []
 765         #       for n in list:
 766         #           if n not in u:
 767         #               u.append(n)"
 768         #
 769         # takes more cycles than just letting the underlying methods
 770         # hand back cached values if a Node's information is requested
 771         # multiple times.  (Other methods of removing duplicates, like
 772         # using dictionary keys, lose the order, and the only ordered
 773         # dictionary patterns I found all ended up using "not in"
 774         # internally anyway...)
 775         if self.implicit is None:
 776             return self.sources + self.depends
 777         else:
 778             return self.sources + self.depends + self.implicit
 779
 780     def _children_get(self):
 781         "__cacheable__"
 782         children = self._all_children_get()
 783         if self.ignore:
 784             children = filter(self.do_not_ignore, children)
 785         return children
 786
 787     def all_children(self, scan=1):
 788         """Return a list of all the node's direct children."""
 789         if scan:
 790             self.scan()
 791         return self._all_children_get()
 792
 793     def children(self, scan=1):
 794         """Return a list of the node's direct children, minus those
 795         that are ignored by this node."""
 796         if scan:
 797             self.scan()
 798         return self._children_get()
 799
 800     def set_state(self, state):
 801         self.state = state
 802
 803     def get_state(self):
 804         return self.state
 805
 806     def current(self, calc=None):
 807         """Default check for whether the Node is current: unknown Node
 808         subtypes are always out of date, so they will always get built."""
 809         return None
 810
 811     def children_are_up_to_date(self, calc=None):
 812         """Alternate check for whether the Node is current:  If all of
 813         our children were up-to-date, then this Node was up-to-date, too.
 814
 815         The SCons.Node.Alias and SCons.Node.Python.Value subclasses
 816         rebind their current() method to this method."""
 817         # Allow the children to calculate their signatures.
 818         self.binfo = self.gen_binfo(calc)
 819         if self.always_build:
 820             return None
 821         state = 0
 822         for kid in self.children(None):
 823             s = kid.get_state()
 824             if s and (not state or s > state):
 825                 state = s
 826         return (state == 0 or state == SCons.Node.up_to_date)
 827
 828     def is_literal(self):
 829         """Always pass the string representation of a Node to
 830         the command interpreter literally."""
 831         return 1
 832
 833     def add_pre_action(self, act):
 834         """Adds an Action performed on this Node only before
 835         building it."""
 836         self.pre_actions.append(act)
 837         # executor must be recomputed to include new pre-actions
 838         self.reset_executor()
 839
 840     def add_post_action(self, act):
 841         """Adds and Action performed on this Node only after
 842         building it."""
 843         self.post_actions.append(act)
 844         # executor must be recomputed to include new pre-actions
 845         self.reset_executor()
 846
 847     def render_include_tree(self):
 848         """
 849         Return a text representation, suitable for displaying to the
 850         user, of the include tree for the sources of this node.
 851         """
 852         if self.is_derived() and self.env:
 853             env = self.get_build_env()
 854             for s in self.sources:
 855                 scanner = self.get_source_scanner(s)
 856                 path = self.get_build_scanner_path(scanner)
 857                 def f(node, env=env, scanner=scanner, path=path):
 858                     return node.get_found_includes(env, scanner, path)
 859                 return SCons.Util.render_tree(s, f, 1)
 860         else:
 861             return None
 862
 863     def get_abspath(self):
 864         """
 865         Return an absolute path to the Node.  This will return simply
 866         str(Node) by default, but for Node types that have a concept of
 867         relative path, this might return something different.
 868         """
 869         return str(self)
 870
 871     def for_signature(self):
 872         """
 873         Return a string representation of the Node that will always
 874         be the same for this particular Node, no matter what.  This
 875         is by contrast to the __str__() method, which might, for
 876         instance, return a relative path for a file Node.  The purpose
 877         of this method is to generate a value to be used in signature
 878         calculation for the command line used to build a target, and
 879         we use this method instead of str() to avoid unnecessary
 880         rebuilds.  This method does not need to return something that
 881         would actually work in a command line; it can return any kind of
 882         nonsense, so long as it does not change.
 883         """
 884         return str(self)
 885
 886     def get_string(self, for_signature):
 887         """This is a convenience function designed primarily to be
 888         used in command generators (i.e., CommandGeneratorActions or
 889         Environment variables that are callable), which are called
 890         with a for_signature argument that is nonzero if the command
 891         generator is being called to generate a signature for the
 892         command line, which determines if we should rebuild or not.
 893
 894         Such command generators should use this method in preference
 895         to str(Node) when converting a Node to a string, passing
 896         in the for_signature parameter, such that we will call
 897         Node.for_signature() or str(Node) properly, depending on whether
 898         we are calculating a signature or actually constructing a
 899         command line."""
 900         if for_signature:
 901             return self.for_signature()
 902         return str(self)
 903
 904     def get_subst_proxy(self):
 905         """
 906         This method is expected to return an object that will function
 907         exactly like this Node, except that it implements any additional
 908         special features that we would like to be in effect for
 909         Environment variable substitution.  The principle use is that
 910         some Nodes would like to implement a __getattr__() method,
 911         but putting that in the Node type itself has a tendency to kill
 912         performance.  We instead put it in a proxy and return it from
 913         this method.  It is legal for this method to return self
 914         if no new functionality is needed for Environment substitution.
 915         """
 916         return self
 917
 918     def explain(self):
 919         if not self.exists():
 920             return "building `%s' because it doesn't exist\n" % self
 921
 922         old = self.get_stored_info()
 923         if old is None:
 924             return None
 925
 926         def dictify(result, kids, sigs):
 927             for k, s in zip(kids, sigs):
 928                 result[k] = s
 929
 930         try:
 931             old_bkids = old.bsources + old.bdepends + old.bimplicit
 932         except AttributeError:
 933             return "Cannot explain why `%s' is being rebuilt: No previous build information found\n" % self
 934
 935         osig = {}
 936         dictify(osig, old.bsources, old.bsourcesigs)
 937         dictify(osig, old.bdepends, old.bdependsigs)
 938         dictify(osig, old.bimplicit, old.bimplicitsigs)
 939
 940         new_bsources = map(str, self.binfo.bsources)
 941         new_bdepends = map(str, self.binfo.bdepends)
 942         new_bimplicit = map(str, self.binfo.bimplicit)
 943
 944         nsig = {}
 945         dictify(nsig, new_bsources, self.binfo.bsourcesigs)
 946         dictify(nsig, new_bdepends, self.binfo.bdependsigs)
 947         dictify(nsig, new_bimplicit, self.binfo.bimplicitsigs)
 948
 949         new_bkids = new_bsources + new_bdepends + new_bimplicit
 950         lines = map(lambda x: "`%s' is no longer a dependency\n" % x,
 951                     filter(lambda x, nk=new_bkids: not x in nk, old_bkids))
 952
 953         for k in new_bkids:
 954             if not k in old_bkids:
 955                 lines.append("`%s' is a new dependency\n" % k)
 956             elif osig[k] != nsig[k]:
 957                 lines.append("`%s' changed\n" % k)
 958
 959         if len(lines) == 0 and old_bkids != new_bkids:
 960             lines.append("the dependency order changed:\n" +
 961                          "%sold: %s\n" % (' '*15, old_bkids) +
 962                          "%snew: %s\n" % (' '*15, new_bkids))
 963
 964         if len(lines) == 0:
 965             newact, newactsig = self.binfo.bact, self.binfo.bactsig
 966             def fmt_with_title(title, strlines):
 967                 lines = string.split(strlines, '\n')
 968                 sep = '\n' + ' '*(15 + len(title))
 969                 return ' '*15 + title + string.join(lines, sep) + '\n'
 970             if old.bactsig != newactsig:
 971                 if old.bact == newact:
 972                     lines.append("the contents of the build action changed\n" +
 973                                  fmt_with_title('action: ', newact))
 974                 else:
 975                     lines.append("the build action changed:\n" +
 976                                  fmt_with_title('old: ', old.bact) +
 977                                  fmt_with_title('new: ', newact))
 978
 979         if len(lines) == 0:
 980             return "rebuilding `%s' for unknown reasons\n" % self
 981
 982         preamble = "rebuilding `%s' because" % self
 983         if len(lines) == 1:
 984             return "%s %s"  % (preamble, lines[0])
 985         else:
 986             lines = ["%s:\n" % preamble] + lines
 987             return string.join(lines, ' '*11)
 988
 989 l = [1]
 990 ul = UserList.UserList([2])
 991 try:
 992     l.extend(ul)
 993 except TypeError:
 994     def NodeList(l):
 995         return l
 996 else:
 997     class NodeList(UserList.UserList):
 998         def __str__(self):
 999             return str(map(str, self.data))
1000 del l
1001 del ul
1002
1003 if not SCons.Memoize.has_metaclass:
1004     _Base = Node
1005     class Node(SCons.Memoize.Memoizer, _Base):
1006         def __init__(self, *args, **kw):
1007             apply(_Base.__init__, (self,)+args, kw)
1008             SCons.Memoize.Memoizer.__init__(self)
1009
1010
1011 def get_children(node, parent): return node.children()
1012 def ignore_cycle(node, stack): pass
1013 def do_nothing(node, parent): pass
1014
1015 class Walker:
1016     """An iterator for walking a Node tree.
1017
1018     This is depth-first, children are visited before the parent.
1019     The Walker object can be initialized with any node, and
1020     returns the next node on the descent with each next() call.
1021     'kids_func' is an optional function that will be called to
1022     get the children of a node instead of calling 'children'.
1023     'cycle_func' is an optional function that will be called
1024     when a cycle is detected.
1025
1026     This class does not get caught in node cycles caused, for example,
1027     by C header file include loops.
1028     """
1029     def __init__(self, node, kids_func=get_children,
1030                              cycle_func=ignore_cycle,
1031                              eval_func=do_nothing):
1032         self.kids_func = kids_func
1033         self.cycle_func = cycle_func
1034         self.eval_func = eval_func
1035         node.wkids = copy.copy(kids_func(node, None))
1036         self.stack = [node]
1037         self.history = {} # used to efficiently detect and avoid cycles
1038         self.history[node] = None
1039
1040     def next(self):
1041         """Return the next node for this walk of the tree.
1042
1043         This function is intentionally iterative, not recursive,
1044         to sidestep any issues of stack size limitations.
1045         """
1046
1047         while self.stack:
1048             if self.stack[-1].wkids:
1049                 node = self.stack[-1].wkids.pop(0)
1050                 if not self.stack[-1].wkids:
1051                     self.stack[-1].wkids = None
1052                 if self.history.has_key(node):
1053                     self.cycle_func(node, self.stack)
1054                 else:
1055                     node.wkids = copy.copy(self.kids_func(node, self.stack[-1]))
1056                     self.stack.append(node)
1057                     self.history[node] = None
1058             else:
1059                 node = self.stack.pop()
1060                 del self.history[node]
1061                 if node:
1062                     if self.stack:
1063                         parent = self.stack[-1]
1064                     else:
1065                         parent = None
1066                     self.eval_func(node, parent)
1067                 return node
1068         return None
1069
1070     def is_done(self):
1071         return not self.stack
1072
1073
1074 arg2nodes_lookups = []