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