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