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
  51 import SCons.Sig
  52 import SCons.Util
  53
  54 # Node states
  55 #
  56 # These are in "priority" order, so that the maximum value for any
  57 # child/dependency of a node represents the state of that node if
  58 # it has no builder of its own.  The canonical example is a file
  59 # system directory, which is only up to date if all of its children
  60 # were up to date.
  61 pending = 1
  62 executing = 2
  63 up_to_date = 3
  64 executed = 4
  65 failed = 5
  66 stack = 6 # nodes that are in the current Taskmaster execution stack
  67
  68 # controls whether implicit depedencies are cached:
  69 implicit_cache = 0
  70
  71 # controls whether implicit dep changes are ignored:
  72 implicit_deps_unchanged = 0
  73
  74 # controls whether the cached implicit deps are ignored:
  75 implicit_deps_changed = 0
  76
  77 # A variable that can be set to an interface-specific function be called
  78 # to annotate a Node with information about its creation.
  79 def do_nothing(node): pass
  80
  81 Annotate = do_nothing
  82
  83 class Node:
  84     """The base Node class, for entities that we know how to
  85     build, or use to build other Nodes.
  86     """
  87
  88     class Attrs:
  89         pass
  90
  91     def __init__(self):
  92         # Note that we no longer explicitly initialize a self.builder
  93         # attribute to None here.  That's because the self.builder
  94         # attribute may be created on-the-fly later by a subclass (the
  95         # canonical example being a builder to fetch a file from a
  96         # source code system like CVS or Subversion).
  97
  98         # Each list of children that we maintain is accompanied by a
  99         # dictionary used to look up quickly whether a node is already
 100         # present in the list.  Empirical tests showed that it was
 101         # fastest to maintain them as side-by-side Node attributes in
 102         # this way, instead of wrapping up each list+dictionary pair in
 103         # a class.  (Of course, we could always still do that in the
 104         # future if we had a good reason to...).
 105         self.sources = []       # source files used to build node
 106         self.sources_dict = {}
 107         self.depends = []       # explicit dependencies (from Depends)
 108         self.depends_dict = {}
 109         self.ignore = []        # dependencies to ignore
 110         self.ignore_dict = {}
 111         self.implicit = None    # implicit (scanned) dependencies (None means not scanned yet)
 112         self.parents = {}
 113         self.wkids = None       # Kids yet to walk, when it's an array
 114         self.source_scanner = None      # implicit scanner from scanner map
 115         self.target_scanner = None      # explicit scanner from this node's Builder
 116
 117         self.env = None
 118         self.state = None
 119         self.precious = None
 120         self.always_build = None
 121         self.found_includes = {}
 122         self.includes = None
 123         self.overrides = {}     # construction variable overrides for building this node
 124         self.attributes = self.Attrs() # Generic place to stick information about the Node.
 125         self.side_effect = 0 # true iff this node is a side effect
 126         self.side_effects = [] # the side effects of building this target
 127         self.pre_actions = []
 128         self.post_actions = []
 129         self.linked = 0 # is this node linked to the build directory?
 130
 131         # Let the interface in which the build engine is embedded
 132         # annotate this Node with its own info (like a description of
 133         # what line in what file created the node, for example).
 134         Annotate(self)
 135
 136     def generate_build_env(self, env):
 137         """Generate the appropriate Environment to build this node."""
 138         return env
 139
 140     def get_build_env(self):
 141         """Fetch the appropriate Environment to build this node."""
 142         executor = self.get_executor()
 143         return executor.get_build_env()
 144
 145     def set_executor(self, executor):
 146         """Set the action executor for this node."""
 147         self.executor = executor
 148
 149     def get_executor(self, create=1):
 150         """Fetch the action executor for this node.  Create one if
 151         there isn't already one, and requested to do so."""
 152         try:
 153             executor = self.executor
 154         except AttributeError:
 155             if not create:
 156                 raise
 157             import SCons.Builder
 158             env = self.generate_build_env(self.builder.env)
 159             executor = SCons.Executor.Executor(self.builder,
 160                                                env,
 161                                                self.builder.overrides,
 162                                                [self],
 163                                                self.sources)
 164             self.executor = executor
 165         return executor
 166
 167     def _for_each_action(self, func):
 168         """Call a function for each action required to build a node.
 169
 170         The purpose here is to have one place for the logic that
 171         collects and executes all of the actions for a node's builder,
 172         even though multiple sections of code elsewhere need this logic
 173         to do different things."""
 174         if not self.has_builder():
 175             return
 176         executor = self.get_executor()
 177         executor(self, func)
 178
 179     def build(self):
 180         """Actually build the node.
 181
 182         This method is called from multiple threads in a parallel build,
 183         so only do thread safe stuff here. Do thread unsafe stuff in
 184         built().
 185         """
 186         def do_action(action, targets, sources, env, self=self):
 187             stat = action(targets, sources, env)
 188             if stat:
 189                 raise SCons.Errors.BuildError(node = self,
 190                                               errstr = "Error %d" % stat)
 191         self._for_each_action(do_action)
 192
 193     def built(self):
 194         """Called just after this node is sucessfully built."""
 195         self.store_bsig()
 196
 197         # Clear out the implicit dependency caches:
 198         # XXX this really should somehow be made more general and put
 199         #     under the control of the scanners.
 200         if self.source_scanner:
 201             self.found_includes = {}
 202             self.includes = None
 203
 204             def get_parents(node, parent): return node.get_parents()
 205             def clear_cache(node, parent):
 206                 node.implicit = None
 207                 node.del_bsig()
 208             w = Walker(self, get_parents, ignore_cycle, clear_cache)
 209             while w.next(): pass
 210
 211         # clear out the content signature, since the contents of this
 212         # node were presumably just changed:
 213         self.del_csig()
 214
 215     def clear(self):
 216         """Completely clear a Node of all its cached state (so that it
 217         can be re-evaluated by interfaces that do continuous integration
 218         builds).
 219         """
 220         self.set_state(None)
 221         self.del_bsig()
 222         self.del_csig()
 223         try:
 224             delattr(self, '_calculated_sig')
 225         except AttributeError:
 226             pass
 227         try:
 228             delattr(self, '_tempbsig')
 229         except AttributeError:
 230             pass
 231         self.includes = None
 232         self.found_includes = {}
 233         self.implicit = None
 234
 235     def visited(self):
 236         """Called just after this node has been visited
 237         without requiring a build.."""
 238         pass
 239
 240     def depends_on(self, nodes):
 241         """Does this node depend on any of 'nodes'?"""
 242         for node in nodes:
 243             if node in self.children():
 244                 return 1
 245
 246         return 0
 247
 248     def builder_set(self, builder):
 249         self.builder = builder
 250
 251     def has_builder(self):
 252         """Return whether this Node has a builder or not.
 253
 254         In Boolean tests, this turns out to be a *lot* more efficient
 255         than simply examining the builder attribute directly ("if
 256         node.builder: ..."). When the builder attribute is examined
 257         directly, it ends up calling __getattr__ for both the __len__
 258         and __nonzero__ attributes on instances of our Builder Proxy
 259         class(es), generating a bazillion extra calls and slowing
 260         things down immensely.
 261         """
 262         try:
 263             b = self.builder
 264         except AttributeError:
 265             # There was no explicit builder for this Node, so initialize
 266             # the self.builder attribute to None now.
 267             self.builder = None
 268             b = self.builder
 269         return not b is None
 270
 271     def is_derived(self):
 272         """
 273         Returns true iff this node is derived (i.e. built).
 274
 275         This should return true only for nodes whose path should be in
 276         the build directory when duplicate=0 and should contribute their build
 277         signatures when they are used as source files to other derived files. For
 278         example: source with source builders are not derived in this sense,
 279         and hence should not return true.
 280         """
 281         return self.has_builder() or self.side_effect
 282
 283     def is_pseudo_derived(self):
 284         """
 285         Returns true iff this node is built, but should use a source path
 286         when duplicate=0 and should contribute a content signature (i.e.
 287         source signature) when used as a source for other derived files.
 288         """
 289         return 0
 290
 291     def alter_targets(self):
 292         """Return a list of alternate targets for this Node.
 293         """
 294         return [], None
 295
 296     def get_found_includes(self, env, scanner, target):
 297         """Return the scanned include lines (implicit dependencies)
 298         found in this node.
 299
 300         The default is no implicit dependencies.  We expect this method
 301         to be overridden by any subclass that can be scanned for
 302         implicit dependencies.
 303         """
 304         return []
 305
 306     def get_implicit_deps(self, env, scanner, target):
 307         """Return a list of implicit dependencies for this node.
 308
 309         This method exists to handle recursive invocation of the scanner
 310         on the implicit dependencies returned by the scanner, if the
 311         scanner's recursive flag says that we should.
 312         """
 313         if not scanner:
 314             return []
 315
 316         try:
 317             recurse = scanner.recursive
 318         except AttributeError:
 319             recurse = None
 320
 321         nodes = [self]
 322         seen = {}
 323         seen[self] = 1
 324         deps = []
 325         while nodes:
 326            n = nodes.pop(0)
 327            d = filter(lambda x, seen=seen: not seen.has_key(x),
 328                       n.get_found_includes(env, scanner, target))
 329            if d:
 330                deps.extend(d)
 331                for n in d:
 332                    seen[n] = 1
 333                if recurse:
 334                    nodes.extend(d)
 335
 336         return deps
 337
 338     # cache used to make implicit_factory fast.
 339     implicit_factory_cache = {}
 340
 341     def implicit_factory(self, path):
 342         """
 343         Turn a cache implicit dependency path into a node.
 344         This is called so many times that doing caching
 345         here is a significant perforamnce boost.
 346         """
 347         try:
 348             return self.implicit_factory_cache[path]
 349         except KeyError:
 350             n = self.builder.source_factory(path)
 351             self.implicit_factory_cache[path] = n
 352             return n
 353
 354     def scan(self):
 355         """Scan this node's dependents for implicit dependencies."""
 356         # Don't bother scanning non-derived files, because we don't
 357         # care what their dependencies are.
 358         # Don't scan again, if we already have scanned.
 359         if not self.implicit is None:
 360             return
 361         self.implicit = []
 362         self.implicit_dict = {}
 363         self._children_reset()
 364         if not self.has_builder():
 365             return
 366
 367         if implicit_cache and not implicit_deps_changed:
 368             implicit = self.get_stored_implicit()
 369             if implicit is not None:
 370                 implicit = map(self.implicit_factory, implicit)
 371                 self._add_child(self.implicit, self.implicit_dict, implicit)
 372                 calc = SCons.Sig.default_calc
 373                 if implicit_deps_unchanged or calc.current(self, calc.bsig(self)):
 374                     return
 375                 else:
 376                     # one of this node's sources has changed, so
 377                     # we need to recalculate the implicit deps,
 378                     # and the bsig:
 379                     self.implicit = []
 380                     self.implicit_dict = {}
 381                     self._children_reset()
 382                     self.del_bsig()
 383
 384         build_env = self.get_build_env()
 385
 386         for child in self.children(scan=0):
 387             self._add_child(self.implicit,
 388                             self.implicit_dict,
 389                             child.get_implicit_deps(build_env,
 390                                                     child.source_scanner,
 391                                                     self))
 392
 393         # scan this node itself for implicit dependencies
 394         self._add_child(self.implicit,
 395                         self.implicit_dict,
 396                         self.get_implicit_deps(build_env,
 397                                                self.target_scanner,
 398                                                self))
 399
 400         if implicit_cache:
 401             self.store_implicit()
 402
 403     def scanner_key(self):
 404         return None
 405
 406     def env_set(self, env, safe=0):
 407         if safe and self.env:
 408             return
 409         self.env = env
 410
 411     def calc_signature(self, calc):
 412         """
 413         Select and calculate the appropriate build signature for a node.
 414
 415         self - the node
 416         calc - the signature calculation module
 417         returns - the signature
 418         """
 419         try:
 420             return self._calculated_sig
 421         except AttributeError:
 422             if self.is_derived():
 423                 if SCons.Sig.build_signature:
 424                     sig = self.rfile().calc_bsig(calc, self)
 425                 else:
 426                     sig = self.rfile().calc_csig(calc, self)
 427             elif not self.rexists():
 428                 sig = None
 429             else:
 430                 sig = self.rfile().calc_csig(calc, self)
 431             self._calculated_sig = sig
 432             return sig
 433
 434     def calc_bsig(self, calc, cache=None):
 435         """Return the node's build signature, calculating it first
 436         if necessary.
 437
 438         Note that we don't save it in the "real" build signature
 439         attribute if we have to calculate it here; the "real" build
 440         signature only gets updated after a file is actually built.
 441         """
 442         if cache is None: cache = self
 443         try:
 444             return cache.bsig
 445         except AttributeError:
 446             try:
 447                 return cache._tempbsig
 448             except AttributeError:
 449                 cache._tempbsig = calc.bsig(self, cache)
 450                 return cache._tempbsig
 451
 452     def get_bsig(self):
 453         """Get the node's build signature (based on the signatures
 454         of its dependency files and build information)."""
 455         try:
 456             return self.bsig
 457         except AttributeError:
 458             return None
 459
 460     def set_bsig(self, bsig):
 461         """Set the node's build signature (based on the signatures
 462         of its dependency files and build information)."""
 463         self.bsig = bsig
 464         try:
 465             delattr(self, '_tempbsig')
 466         except AttributeError:
 467             pass
 468
 469     def store_bsig(self):
 470         """Make the build signature permanent (that is, store it in the
 471         .sconsign file or equivalent)."""
 472         pass
 473
 474     def del_bsig(self):
 475         """Delete the bsig from this node."""
 476         try:
 477             delattr(self, 'bsig')
 478         except AttributeError:
 479             pass
 480
 481     def get_csig(self):
 482         """Get the signature of the node's content."""
 483         try:
 484             return self.csig
 485         except AttributeError:
 486             return None
 487
 488     def calc_csig(self, calc, cache=None):
 489         """Return the node's content signature, calculating it first
 490         if necessary.
 491         """
 492         if cache is None: cache = self
 493         try:
 494             return cache.csig
 495         except AttributeError:
 496             cache.csig = calc.csig(self, cache)
 497             return cache.csig
 498
 499     def set_csig(self, csig):
 500         """Set the signature of the node's content."""
 501         self.csig = csig
 502
 503     def store_csig(self):
 504         """Make the content signature permanent (that is, store it in the
 505         .sconsign file or equivalent)."""
 506         pass
 507
 508     def del_csig(self):
 509         """Delete the csig from this node."""
 510         try:
 511             delattr(self, 'csig')
 512         except AttributeError:
 513             pass
 514
 515     def get_prevsiginfo(self):
 516         """Fetch the previous signature information from the
 517         .sconsign entry."""
 518         return SCons.Sig._SConsign.null_siginfo
 519
 520     def get_timestamp(self):
 521         return 0
 522
 523     def store_timestamp(self):
 524         """Make the timestamp permanent (that is, store it in the
 525         .sconsign file or equivalent)."""
 526         pass
 527
 528     def store_implicit(self):
 529         """Make the implicit deps permanent (that is, store them in the
 530         .sconsign file or equivalent)."""
 531         pass
 532
 533     def get_stored_implicit(self):
 534         """Fetch the stored implicit dependencies"""
 535         return None
 536
 537     def set_precious(self, precious = 1):
 538         """Set the Node's precious value."""
 539         self.precious = precious
 540
 541     def set_always_build(self, always_build = 1):
 542         """Set the Node's always_build value."""
 543         self.always_build = always_build
 544
 545     def exists(self):
 546         """Does this node exists?"""
 547         # All node exist by default:
 548         return 1
 549
 550     def rexists(self):
 551         """Does this node exist locally or in a repositiory?"""
 552         # There are no repositories by default:
 553         return self.exists()
 554
 555     def prepare(self):
 556         """Prepare for this Node to be created.
 557         The default implemenation checks that all children either exist
 558         or are derived.
 559         """
 560         def missing(node):
 561             return not node.is_derived() and \
 562                    not node.is_pseudo_derived() and \
 563                    not node.linked and \
 564                    not node.rexists()
 565         missing_sources = filter(missing, self.children())
 566         if missing_sources:
 567             desc = "No Builder for target `%s', needed by `%s'." % (missing_sources[0], self)
 568             raise SCons.Errors.StopError, desc
 569
 570     def remove(self):
 571         """Remove this Node:  no-op by default."""
 572         return None
 573
 574     def add_dependency(self, depend):
 575         """Adds dependencies. The depend argument must be a list."""
 576         self._add_child(self.depends, self.depends_dict, depend)
 577
 578     def add_ignore(self, depend):
 579         """Adds dependencies to ignore. The depend argument must be a list."""
 580         self._add_child(self.ignore, self.ignore_dict, depend)
 581
 582     def add_source(self, source):
 583         """Adds sources. The source argument must be a list."""
 584         self._add_child(self.sources, self.sources_dict, source)
 585
 586     def _add_child(self, collection, dict, child):
 587         """Adds 'child' to 'collection', first checking 'dict' to see if
 588         it's already present. The 'child' argument must be a list"""
 589         if type(child) is not type([]):
 590             raise TypeError("child must be a list")
 591         added = None
 592         for c in child:
 593             if not dict.has_key(c):
 594                 collection.append(c)
 595                 dict[c] = 1
 596                 added = 1
 597             c.parents[self] = 1
 598         if added:
 599             self._children_reset()
 600
 601     def add_wkid(self, wkid):
 602         """Add a node to the list of kids waiting to be evaluated"""
 603         if self.wkids != None:
 604             self.wkids.append(wkid)
 605
 606     def _children_reset(self):
 607         try:
 608             delattr(self, '_children')
 609         except AttributeError:
 610             pass
 611
 612     def children(self, scan=1):
 613         """Return a list of the node's direct children, minus those
 614         that are ignored by this node."""
 615         if scan:
 616             self.scan()
 617         try:
 618             return self._children
 619         except AttributeError:
 620             c = filter(lambda x, i=self.ignore: x not in i,
 621                               self.all_children(scan=0))
 622             self._children = c
 623             return c
 624
 625     def all_children(self, scan=1):
 626         """Return a list of all the node's direct children."""
 627         # The return list may contain duplicate Nodes, especially in
 628         # source trees where there are a lot of repeated #includes
 629         # of a tangle of .h files.  Profiling shows, however, that
 630         # eliminating the duplicates with a brute-force approach that
 631         # preserves the order (that is, something like:
 632         #
 633         #       u = []
 634         #       for n in list:
 635         #           if n not in u:
 636         #               u.append(n)"
 637         #
 638         # takes more cycles than just letting the underlying methods
 639         # hand back cached values if a Node's information is requested
 640         # multiple times.  (Other methods of removing duplicates, like
 641         # using dictionary keys, lose the order, and the only ordered
 642         # dictionary patterns I found all ended up using "not in"
 643         # internally anyway...)
 644         if scan:
 645             self.scan()
 646         if self.implicit is None:
 647             return self.sources + self.depends
 648         else:
 649             return self.sources + self.depends + self.implicit
 650
 651     def get_parents(self):
 652         return self.parents.keys()
 653
 654     def set_state(self, state):
 655         self.state = state
 656
 657     def get_state(self):
 658         return self.state
 659
 660     def current(self, calc=None):
 661         return None
 662
 663     def rfile(self):
 664         return self
 665
 666     def rstr(self):
 667         return str(self)
 668
 669     def is_literal(self):
 670         """Always pass the string representation of a Node to
 671         the command interpreter literally."""
 672         return 1
 673
 674     def add_pre_action(self, act):
 675         """Adds an Action performed on this Node only before
 676         building it."""
 677         self.pre_actions.append(act)
 678
 679     def add_post_action(self, act):
 680         """Adds and Action performed on this Node only after
 681         building it."""
 682         self.post_actions.append(act)
 683
 684     def render_include_tree(self):
 685         """
 686         Return a text representation, suitable for displaying to the
 687         user, of the include tree for the sources of this node.
 688         """
 689         if self.is_derived() and self.env:
 690             env = self.get_build_env()
 691             for s in self.sources:
 692                 def f(node, env=env, scanner=s.source_scanner, target=self):
 693                     return node.get_found_includes(env, scanner, target)
 694                 return SCons.Util.render_tree(s, f, 1)
 695         else:
 696             return None
 697
 698     def get_abspath(self):
 699         """
 700         Return an absolute path to the Node.  This will return simply
 701         str(Node) by default, but for Node types that have a concept of
 702         relative path, this might return something different.
 703         """
 704         return str(self)
 705
 706     def for_signature(self):
 707         """
 708         Return a string representation of the Node that will always
 709         be the same for this particular Node, no matter what.  This
 710         is by contrast to the __str__() method, which might, for
 711         instance, return a relative path for a file Node.  The purpose
 712         of this method is to generate a value to be used in signature
 713         calculation for the command line used to build a target, and
 714         we use this method instead of str() to avoid unnecessary
 715         rebuilds.  This method does not need to return something that
 716         would actually work in a command line; it can return any kind of
 717         nonsense, so long as it does not change.
 718         """
 719         return str(self)
 720
 721     def get_string(self, for_signature):
 722         """This is a convenience function designed primarily to be
 723         used in command generators (i.e., CommandGeneratorActions or
 724         Environment variables that are callable), which are called
 725         with a for_signature argument that is nonzero if the command
 726         generator is being called to generate a signature for the
 727         command line, which determines if we should rebuild or not.
 728
 729         Such command generators shoud use this method in preference
 730         to str(Node) when converting a Node to a string, passing
 731         in the for_signature parameter, such that we will call
 732         Node.for_signature() or str(Node) properly, depending on whether
 733         we are calculating a signature or actually constructing a
 734         command line."""
 735         if for_signature:
 736             return self.for_signature()
 737         return str(self)
 738
 739     def get_subst_proxy(self):
 740         """
 741         This method is expected to return an object that will function
 742         exactly like this Node, except that it implements any additional
 743         special features that we would like to be in effect for
 744         Environment variable substitution.  The principle use is that
 745         some Nodes would like to implement a __getattr__() method,
 746         but putting that in the Node type itself has a tendency to kill
 747         performance.  We instead put it in a proxy and return it from
 748         this method.  It is legal for this method to return self
 749         if no new functionality is needed for Environment substitution.
 750         """
 751         return self
 752
 753
 754 def get_children(node, parent): return node.children()
 755 def ignore_cycle(node, stack): pass
 756 def do_nothing(node, parent): pass
 757
 758 class Walker:
 759     """An iterator for walking a Node tree.
 760
 761     This is depth-first, children are visited before the parent.
 762     The Walker object can be initialized with any node, and
 763     returns the next node on the descent with each next() call.
 764     'kids_func' is an optional function that will be called to
 765     get the children of a node instead of calling 'children'.
 766     'cycle_func' is an optional function that will be called
 767     when a cycle is detected.
 768
 769     This class does not get caught in node cycles caused, for example,
 770     by C header file include loops.
 771     """
 772     def __init__(self, node, kids_func=get_children,
 773                              cycle_func=ignore_cycle,
 774                              eval_func=do_nothing):
 775         self.kids_func = kids_func
 776         self.cycle_func = cycle_func
 777         self.eval_func = eval_func
 778         node.wkids = copy.copy(kids_func(node, None))
 779         self.stack = [node]
 780         self.history = {} # used to efficiently detect and avoid cycles
 781         self.history[node] = None
 782
 783     def next(self):
 784         """Return the next node for this walk of the tree.
 785
 786         This function is intentionally iterative, not recursive,
 787         to sidestep any issues of stack size limitations.
 788         """
 789
 790         while self.stack:
 791             if self.stack[-1].wkids:
 792                 node = self.stack[-1].wkids.pop(0)
 793                 if not self.stack[-1].wkids:
 794                     self.stack[-1].wkids = None
 795                 if self.history.has_key(node):
 796                     self.cycle_func(node, self.stack)
 797                 else:
 798                     node.wkids = copy.copy(self.kids_func(node, self.stack[-1]))
 799                     self.stack.append(node)
 800                     self.history[node] = None
 801             else:
 802                 node = self.stack.pop()
 803                 del self.history[node]
 804                 if node:
 805                     if self.stack:
 806                         parent = self.stack[-1]
 807                     else:
 808                         parent = None
 809                     self.eval_func(node, parent)
 810                 return node
 811
 812     def is_done(self):
 813         return not self.stack
 814
 815
 816 arg2nodes_lookups = []
 817
 818 def arg2nodes(args, node_factory=None, lookup_list=arg2nodes_lookups):
 819     """This function converts a string or list into a list of Node
 820     instances.  It accepts the following inputs:
 821         - A single string,
 822         - A single Node instance,
 823         - A list containing either strings or Node instances.
 824     In all cases, strings are converted to Node instances, and the
 825     function returns a list of Node instances."""
 826
 827     if not args:
 828         return []
 829     if not SCons.Util.is_List(args):
 830         args = [args]
 831
 832     nodes = []
 833     for v in args:
 834         if SCons.Util.is_String(v):
 835             n = None
 836             for l in lookup_list:
 837                 n = l(v)
 838                 if not n is None:
 839                     break
 840             if not n is None:
 841                 if SCons.Util.is_String(n) and node_factory:
 842                     n = node_factory(n)
 843                 nodes.append(n)
 844             elif node_factory:
 845                 nodes.append(node_factory(v))
 846         # Do we enforce the following restriction?  Maybe, but it
 847         # would also restrict what we can do to allow people to
 848         # use the engine with alternate Node implementations...
 849         #elif not issubclass(v.__class__, Node):
 850         #    raise TypeError
 851         else:
 852             nodes.append(v)
 853
 854     return nodes