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         self.sources = []       # source files used to build node
  99         self.depends = []       # explicit dependencies (from Depends)
 100         self.implicit = None    # implicit (scanned) dependencies (None means not scanned yet)
 101         self.ignore = []        # dependencies to ignore
 102         self.parents = {}
 103         self.wkids = None       # Kids yet to walk, when it's an array
 104         self.source_scanner = None      # implicit scanner from scanner map
 105         self.target_scanner = None      # explicit scanner from this node's Builder
 106
 107         self.env = None
 108         self.state = None
 109         self.precious = None
 110         self.found_includes = {}
 111         self.includes = None
 112         self.overrides = {}     # construction variable overrides for building this node
 113         self.attributes = self.Attrs() # Generic place to stick information about the Node.
 114         self.side_effect = 0 # true iff this node is a side effect
 115         self.side_effects = [] # the side effects of building this target
 116         self.pre_actions = []
 117         self.post_actions = []
 118         self.linked = 0 # is this node linked to the build directory?
 119
 120         # Let the interface in which the build engine is embedded
 121         # annotate this Node with its own info (like a description of
 122         # what line in what file created the node, for example).
 123         Annotate(self)
 124
 125     def generate_build_env(self):
 126         """Generate the appropriate Environment to build this node."""
 127         if self.env is None:
 128             # The node itself doesn't have an associated Environment
 129             # (which kind of implies it's a source code file, but who
 130             # knows...).  Regardless of why, use the environment (if
 131             # any) associated with the Builder itself.
 132             env = self.builder.env
 133             overrides = self.builder.overrides
 134         else:
 135             # The normal case: use the Environment used to specify how
 136             # this Node is to be built.
 137             env = self.env
 138             overrides = self.overrides
 139         return env.Override(overrides)
 140
 141     def _for_each_action(self, func):
 142         """Call a function for each action required to build a node.
 143
 144         The purpose here is to have one place for the logic that
 145         collects and executes all of the actions for a node's builder,
 146         even though multiple sections of code elsewhere need this logic
 147         to do different things."""
 148         if not self.has_builder():
 149             return
 150         action_list = self.pre_actions + \
 151                       self.builder.get_actions() + \
 152                       self.post_actions
 153         if not action_list:
 154             return
 155         targets = self.builder.targets(self)
 156         env = self.generate_build_env()
 157         for action in action_list:
 158             func(action, targets, self.sources, env)
 159
 160     def build(self):
 161         """Actually build the node.
 162
 163         This method is called from multiple threads in a parallel build,
 164         so only do thread safe stuff here. Do thread unsafe stuff in
 165         built().
 166         """
 167         def do_action(action, targets, sources, env, self=self):
 168             stat = action(targets, sources, env)
 169             if stat:
 170                 raise SCons.Errors.BuildError(node = self,
 171                                               errstr = "Error %d" % stat)
 172         self._for_each_action(do_action)
 173
 174     def built(self):
 175         """Called just after this node is sucessfully built."""
 176         self.store_bsig()
 177
 178         # Clear out the implicit dependency caches:
 179         # XXX this really should somehow be made more general and put
 180         #     under the control of the scanners.
 181         if self.source_scanner:
 182             self.found_includes = {}
 183             self.includes = None
 184
 185             def get_parents(node, parent): return node.get_parents()
 186             def clear_cache(node, parent):
 187                 node.implicit = None
 188                 node.del_bsig()
 189             w = Walker(self, get_parents, ignore_cycle, clear_cache)
 190             while w.next(): pass
 191
 192         # clear out the content signature, since the contents of this
 193         # node were presumably just changed:
 194         self.del_csig()
 195
 196     def visited(self):
 197         """Called just after this node has been visited
 198         without requiring a build.."""
 199         pass
 200
 201     def depends_on(self, nodes):
 202         """Does this node depend on any of 'nodes'?"""
 203         for node in nodes:
 204             if node in self.children():
 205                 return 1
 206
 207         return 0
 208
 209     def builder_set(self, builder):
 210         self.builder = builder
 211
 212     def has_builder(self):
 213         """Return whether this Node has a builder or not.
 214
 215         In Boolean tests, this turns out to be a *lot* more efficient
 216         than simply examining the builder attribute directly ("if
 217         node.builder: ..."). When the builder attribute is examined
 218         directly, it ends up calling __getattr__ for both the __len__
 219         and __nonzero__ attributes on instances of our Builder Proxy
 220         class(es), generating a bazillion extra calls and slowing
 221         things down immensely.
 222         """
 223         try:
 224             b = self.builder
 225         except AttributeError:
 226             # There was no explicit builder for this Node, so initialize
 227             # the self.builder attribute to None now.
 228             self.builder = None
 229             b = self.builder
 230         return not b is None
 231
 232     def is_derived(self):
 233         return self.has_builder() or self.side_effect
 234
 235     def alter_targets(self):
 236         """Return a list of alternate targets for this Node.
 237         """
 238         return [], None
 239
 240     def builder_sig_adapter(self):
 241         """Create an adapter for calculating a builder's signature.
 242
 243         The underlying signature class will call get_contents()
 244         to fetch the signature of a builder, but the actual
 245         content of that signature depends on the node and the
 246         environment (for construction variable substitution),
 247         so this adapter provides the right glue between the two.
 248         """
 249         class Adapter:
 250             def __init__(self, node):
 251                 self.node = node
 252             def get_contents(self):
 253                 return self.node.builder.get_contents(self.node, self.node.sources, self.node.generate_build_env())
 254             def get_timestamp(self):
 255                 return None
 256         return Adapter(self)
 257
 258     def get_found_includes(self, env, scanner, target):
 259         """Return the scanned include lines (implicit dependencies)
 260         found in this node.
 261
 262         The default is no implicit dependencies.  We expect this method
 263         to be overridden by any subclass that can be scanned for
 264         implicit dependencies.
 265         """
 266         return []
 267
 268     def get_implicit_deps(self, env, scanner, target):
 269         """Return a list of implicit dependencies for this node.
 270
 271         This method exists to handle recursive invocation of the scanner
 272         on the implicit dependencies returned by the scanner, if the
 273         scanner's recursive flag says that we should.
 274         """
 275         if not scanner:
 276             return []
 277
 278         try:
 279             recurse = scanner.recursive
 280         except AttributeError:
 281             recurse = None
 282
 283         nodes = [self]
 284         seen = {}
 285         seen[self] = 1
 286         deps = []
 287         while nodes:
 288            n = nodes.pop(0)
 289            d = filter(lambda x, seen=seen: not seen.has_key(x),
 290                       n.get_found_includes(env, scanner, target))
 291            if d:
 292                deps.extend(d)
 293                for n in d:
 294                    seen[n] = 1
 295                if recurse:
 296                    nodes.extend(d)
 297
 298         return deps
 299
 300     # cache used to make implicit_factory fast.
 301     implicit_factory_cache = {}
 302
 303     def implicit_factory(self, path):
 304         """
 305         Turn a cache implicit dependency path into a node.
 306         This is called so many times that doing caching
 307         here is a significant perforamnce boost.
 308         """
 309         try:
 310             return self.implicit_factory_cache[path]
 311         except KeyError:
 312             n = self.builder.source_factory(path)
 313             self.implicit_factory_cache[path] = n
 314             return n
 315
 316     def scan(self):
 317         """Scan this node's dependents for implicit dependencies."""
 318         # Don't bother scanning non-derived files, because we don't
 319         # care what their dependencies are.
 320         # Don't scan again, if we already have scanned.
 321         if not self.implicit is None:
 322             return
 323         self.implicit = []
 324         if not self.has_builder():
 325             return
 326
 327         if implicit_cache and not implicit_deps_changed:
 328             implicit = self.get_stored_implicit()
 329             if implicit is not None:
 330                 implicit = map(self.implicit_factory, implicit)
 331                 self._add_child(self.implicit, implicit)
 332                 calc = SCons.Sig.default_calc
 333                 if implicit_deps_unchanged or calc.current(self, calc.bsig(self)):
 334                     return
 335                 else:
 336                     # one of this node's sources has changed, so
 337                     # we need to recalculate the implicit deps,
 338                     # and the bsig:
 339                     self.implicit = []
 340                     self.del_bsig()
 341
 342         build_env = self.generate_build_env()
 343
 344         for child in self.children(scan=0):
 345             self._add_child(self.implicit,
 346                             child.get_implicit_deps(build_env,
 347                                                     child.source_scanner,
 348                                                     self))
 349
 350         # scan this node itself for implicit dependencies
 351         self._add_child(self.implicit,
 352                         self.get_implicit_deps(build_env,
 353                                                self.target_scanner,
 354                                                self))
 355
 356         if implicit_cache:
 357             self.store_implicit()
 358
 359     def scanner_key(self):
 360         return None
 361
 362     def env_set(self, env, safe=0):
 363         if safe and self.env:
 364             return
 365         self.env = env
 366
 367     def calc_signature(self, calc, cache=None):
 368         """
 369         Select and calculate the appropriate build signature for a node.
 370
 371         self - the node
 372         calc - the signature calculation module
 373         cache - alternate node to use for the signature cache
 374         returns - the signature
 375         """
 376
 377         if self.has_builder():
 378             if SCons.Sig.build_signature:
 379                 return calc.bsig(self, cache)
 380             else:
 381                 return calc.csig(self, cache)
 382         elif not self.exists():
 383             return None
 384         else:
 385             return calc.csig(self, cache)
 386
 387     def get_bsig(self):
 388         """Get the node's build signature (based on the signatures
 389         of its dependency files and build information)."""
 390         if not hasattr(self, 'bsig'):
 391             return None
 392         return self.bsig
 393
 394     def set_bsig(self, bsig):
 395         """Set the node's build signature (based on the signatures
 396         of its dependency files and build information)."""
 397         self.bsig = bsig
 398
 399     def store_bsig(self):
 400         """Make the build signature permanent (that is, store it in the
 401         .sconsign file or equivalent)."""
 402         pass
 403
 404     def del_bsig(self):
 405         """Delete the bsig from this node."""
 406         if hasattr(self, 'bsig'):
 407             delattr(self, 'bsig')
 408
 409     def get_csig(self):
 410         """Get the signature of the node's content."""
 411         if not hasattr(self, 'csig'):
 412             return None
 413         return self.csig
 414
 415     def set_csig(self, csig):
 416         """Set the signature of the node's content."""
 417         self.csig = csig
 418
 419     def store_csig(self):
 420         """Make the content signature permanent (that is, store it in the
 421         .sconsign file or equivalent)."""
 422         pass
 423
 424     def del_csig(self):
 425         """Delete the csig from this node."""
 426         if hasattr(self, 'csig'):
 427             delattr(self, 'csig')
 428
 429     def get_prevsiginfo(self):
 430         """Fetch the previous signature information from the
 431         .sconsign entry."""
 432         return None
 433
 434     def get_timestamp(self):
 435         return 0
 436
 437     def store_timestamp(self):
 438         """Make the timestamp permanent (that is, store it in the
 439         .sconsign file or equivalent)."""
 440         pass
 441
 442     def store_implicit(self):
 443         """Make the implicit deps permanent (that is, store them in the
 444         .sconsign file or equivalent)."""
 445         pass
 446
 447     def get_stored_implicit(self):
 448         """Fetch the stored implicit dependencies"""
 449         return None
 450
 451     def set_precious(self, precious = 1):
 452         """Set the Node's precious value."""
 453         self.precious = precious
 454
 455     def exists(self):
 456         """Does this node exists?"""
 457         # All node exist by default:
 458         return 1
 459
 460     def rexists(self):
 461         """Does this node exist locally or in a repositiory?"""
 462         # There are no repositories by default:
 463         return self.exists()
 464
 465     def prepare(self):
 466         """Prepare for this Node to be created.
 467         The default implemenation checks that all children either exist
 468         or are derived.
 469         """
 470         def missing(node):
 471             return not node.is_derived() and not node.linked and not node.rexists()
 472         missing_sources = filter(missing, self.children())
 473         if missing_sources:
 474             desc = "No Builder for target `%s', needed by `%s'." % (missing_sources[0], self)
 475             raise SCons.Errors.StopError, desc
 476
 477     def remove(self):
 478         """Remove this Node:  no-op by default."""
 479         return None
 480
 481     def add_dependency(self, depend):
 482         """Adds dependencies. The depend argument must be a list."""
 483         self._add_child(self.depends, depend)
 484
 485     def add_ignore(self, depend):
 486         """Adds dependencies to ignore. The depend argument must be a list."""
 487         self._add_child(self.ignore, depend)
 488
 489     def add_source(self, source):
 490         """Adds sources. The source argument must be a list."""
 491         self._add_child(self.sources, source)
 492
 493     def _add_child(self, collection, child):
 494         """Adds 'child' to 'collection'. The 'child' argument must be a list"""
 495         if type(child) is not type([]):
 496             raise TypeError("child must be a list")
 497         child = filter(lambda x, s=collection: x not in s, child)
 498         if child:
 499             collection.extend(child)
 500
 501         for c in child:
 502             c.parents[self] = 1
 503
 504     def add_wkid(self, wkid):
 505         """Add a node to the list of kids waiting to be evaluated"""
 506         if self.wkids != None:
 507             self.wkids.append(wkid)
 508
 509     def children(self, scan=1):
 510         """Return a list of the node's direct children, minus those
 511         that are ignored by this node."""
 512         return filter(lambda x, i=self.ignore: x not in i,
 513                       self.all_children(scan))
 514
 515     def all_children(self, scan=1):
 516         """Return a list of all the node's direct children."""
 517         # The return list may contain duplicate Nodes, especially in
 518         # source trees where there are a lot of repeated #includes
 519         # of a tangle of .h files.  Profiling shows, however, that
 520         # eliminating the duplicates with a brute-force approach that
 521         # preserves the order (that is, something like:
 522         #
 523         #       u = []
 524         #       for n in list:
 525         #           if n not in u:
 526         #               u.append(n)"
 527         #
 528         # takes more cycles than just letting the underlying methods
 529         # hand back cached values if a Node's information is requested
 530         # multiple times.  (Other methods of removing duplicates, like
 531         # using dictionary keys, lose the order, and the only ordered
 532         # dictionary patterns I found all ended up using "not in"
 533         # internally anyway...)
 534         if scan:
 535             self.scan()
 536         if self.implicit is None:
 537             return self.sources + self.depends
 538         else:
 539             return self.sources + self.depends + self.implicit
 540
 541     def get_parents(self):
 542         return self.parents.keys()
 543
 544     def set_state(self, state):
 545         self.state = state
 546
 547     def get_state(self):
 548         return self.state
 549
 550     def current(self, calc=None):
 551         return None
 552
 553     def rfile(self):
 554         return self
 555
 556     def rstr(self):
 557         return str(self)
 558
 559     def is_literal(self):
 560         """Always pass the string representation of a Node to
 561         the command interpreter literally."""
 562         return 1
 563
 564     def add_pre_action(self, act):
 565         """Adds an Action performed on this Node only before
 566         building it."""
 567         self.pre_actions.append(act)
 568
 569     def add_post_action(self, act):
 570         """Adds and Action performed on this Node only after
 571         building it."""
 572         self.post_actions.append(act)
 573
 574     def render_include_tree(self):
 575         """
 576         Return a text representation, suitable for displaying to the
 577         user, of the include tree for the sources of this node.
 578         """
 579         if self.has_builder() and self.env:
 580             env = self.generate_build_env()
 581             for s in self.sources:
 582                 def f(node, env=env, scanner=s.source_scanner, target=self):
 583                     return node.get_found_includes(env, scanner, target)
 584                 return SCons.Util.render_tree(s, f, 1)
 585         else:
 586             return None
 587
 588 def get_children(node, parent): return node.children()
 589 def ignore_cycle(node, stack): pass
 590 def do_nothing(node, parent): pass
 591
 592 class Walker:
 593     """An iterator for walking a Node tree.
 594
 595     This is depth-first, children are visited before the parent.
 596     The Walker object can be initialized with any node, and
 597     returns the next node on the descent with each next() call.
 598     'kids_func' is an optional function that will be called to
 599     get the children of a node instead of calling 'children'.
 600     'cycle_func' is an optional function that will be called
 601     when a cycle is detected.
 602
 603     This class does not get caught in node cycles caused, for example,
 604     by C header file include loops.
 605     """
 606     def __init__(self, node, kids_func=get_children,
 607                              cycle_func=ignore_cycle,
 608                              eval_func=do_nothing):
 609         self.kids_func = kids_func
 610         self.cycle_func = cycle_func
 611         self.eval_func = eval_func
 612         node.wkids = copy.copy(kids_func(node, None))
 613         self.stack = [node]
 614         self.history = {} # used to efficiently detect and avoid cycles
 615         self.history[node] = None
 616
 617     def next(self):
 618         """Return the next node for this walk of the tree.
 619
 620         This function is intentionally iterative, not recursive,
 621         to sidestep any issues of stack size limitations.
 622         """
 623
 624         while self.stack:
 625             if self.stack[-1].wkids:
 626                 node = self.stack[-1].wkids.pop(0)
 627                 if not self.stack[-1].wkids:
 628                     self.stack[-1].wkids = None
 629                 if self.history.has_key(node):
 630                     self.cycle_func(node, self.stack)
 631                 else:
 632                     node.wkids = copy.copy(self.kids_func(node, self.stack[-1]))
 633                     self.stack.append(node)
 634                     self.history[node] = None
 635             else:
 636                 node = self.stack.pop()
 637                 del self.history[node]
 638                 if node:
 639                     if self.stack:
 640                         parent = self.stack[-1]
 641                     else:
 642                         parent = None
 643                     self.eval_func(node, parent)
 644                 return node
 645
 646     def is_done(self):
 647         return not self.stack
 648
 649
 650 arg2nodes_lookups = []
 651
 652 def arg2nodes(args, node_factory=None, lookup_list=arg2nodes_lookups):
 653     """This function converts a string or list into a list of Node
 654     instances.  It accepts the following inputs:
 655         - A single string,
 656         - A single Node instance,
 657         - A list containing either strings or Node instances.
 658     In all cases, strings are converted to Node instances, and the
 659     function returns a list of Node instances."""
 660
 661     if not args:
 662         return []
 663     if not SCons.Util.is_List(args):
 664         args = [args]
 665
 666     nodes = []
 667     for v in args:
 668         if SCons.Util.is_String(v):
 669             n = None
 670             for l in lookup_list:
 671                 n = l(v)
 672                 if not n is None:
 673                     break
 674             if not n is None:
 675                 if SCons.Util.is_String(n) and node_factory:
 676                     n = node_factory(n)
 677                 nodes.append(n)
 678             elif node_factory:
 679                 nodes.append(node_factory(v))
 680         # Do we enforce the following restriction?  Maybe, but it
 681         # would also restrict what we can do to allow people to
 682         # use the engine with alternate Node implementations...
 683         #elif not issubclass(v.__class__, Node):
 684         #    raise TypeError
 685         else:
 686             nodes.append(v)
 687
 688     return nodes