src/engine/SCons/Taskmaster.py

   1 """SCons.Taskmaster
   2
   3 Generic Taskmaster.
   4
   5 """
   6
   7 #
   8 # __COPYRIGHT__
   9 #
  10 # Permission is hereby granted, free of charge, to any person obtaining
  11 # a copy of this software and associated documentation files (the
  12 # "Software"), to deal in the Software without restriction, including
  13 # without limitation the rights to use, copy, modify, merge, publish,
  14 # distribute, sublicense, and/or sell copies of the Software, and to
  15 # permit persons to whom the Software is furnished to do so, subject to
  16 # the following conditions:
  17 #
  18 # The above copyright notice and this permission notice shall be included
  19 # in all copies or substantial portions of the Software.
  20 #
  21 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
  22 # KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  23 # WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  25 # LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  26 # OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  27 # WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28 #
  29
  30 __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__"
  31
  32 import string
  33 import sys
  34 import traceback
  35
  36 import SCons.Node
  37 import SCons.Errors
  38
  39 # A subsystem for recording stats about how different Nodes are handled by
  40 # the main Taskmaster loop.  There's no external control here (no need for
  41 # a --debug= option); enable it by changing the value of CollectStats.
  42
  43 CollectStats = None
  44
  45 class Stats:
  46     def __init__(self):
  47         self.considered  = 0
  48         self.already_handled  = 0
  49         self.problem  = 0
  50         self.child_failed  = 0
  51         self.not_started  = 0
  52         self.not_built  = 0
  53         self.side_effects  = 0
  54         self.build  = 0
  55
  56 StatsNodes = []
  57
  58 fmt = "%(considered)3d "\
  59       "%(already_handled)3d " \
  60       "%(problem)3d " \
  61       "%(child_failed)3d " \
  62       "%(not_started)3d " \
  63       "%(not_built)3d " \
  64       "%(side_effects)3d " \
  65       "%(build)3d "
  66
  67 def dump_stats():
  68     StatsNodes.sort(lambda a, b: cmp(str(a), str(b)))
  69     for n in StatsNodes:
  70         print (fmt % n.stats.__dict__) + str(n)
  71
  72 class Task:
  73     """Default SCons build engine task.
  74
  75     This controls the interaction of the actual building of node
  76     and the rest of the engine.
  77
  78     This is expected to handle all of the normally-customizable
  79     aspects of controlling a build, so any given application
  80     *should* be able to do what it wants by sub-classing this
  81     class and overriding methods as appropriate.  If an application
  82     needs to customze something by sub-classing Taskmaster (or
  83     some other build engine class), we should first try to migrate
  84     that functionality into this class.
  85
  86     Note that it's generally a good idea for sub-classes to call
  87     these methods explicitly to update state, etc., rather than
  88     roll their own interaction with Taskmaster from scratch."""
  89     def __init__(self, tm, targets, top, node):
  90         self.tm = tm
  91         self.targets = targets
  92         self.top = top
  93         self.node = node
  94         self.exc_clear()
  95
  96     def display(self, message):
  97         """Allow the calling interface to display a message
  98         """
  99         pass
 100
 101     def prepare(self):
 102         """Called just before the task is executed.
 103
 104         This unlinks all targets and makes all directories before
 105         building anything."""
 106
 107         # Now that it's the appropriate time, give the TaskMaster a
 108         # chance to raise any exceptions it encountered while preparing
 109         # this task.
 110         self.exception_raise()
 111
 112         if self.tm.message:
 113             self.display(self.tm.message)
 114             self.tm.message = None
 115
 116         for t in self.targets:
 117             t.prepare()
 118             for s in t.side_effects:
 119                 s.prepare()
 120
 121     def execute(self):
 122         """Called to execute the task.
 123
 124         This method is called from multiple threads in a parallel build,
 125         so only do thread safe stuff here.  Do thread unsafe stuff in
 126         prepare(), executed() or failed()."""
 127
 128         try:
 129             everything_was_cached = 1
 130             for t in self.targets:
 131                 if not t.retrieve_from_cache():
 132                     everything_was_cached = 0
 133                     break
 134             if not everything_was_cached:
 135                 self.targets[0].build()
 136         except KeyboardInterrupt:
 137             raise
 138         except SystemExit:
 139             exc_value = sys.exc_info()[1]
 140             raise SCons.Errors.ExplicitExit(self.targets[0], exc_value.code)
 141         except SCons.Errors.UserError:
 142             raise
 143         except SCons.Errors.BuildError:
 144             raise
 145         except:
 146             exc_type, exc_value, exc_traceback = sys.exc_info()
 147             raise SCons.Errors.BuildError(self.targets[0],
 148                                           "Exception",
 149                                           exc_type,
 150                                           exc_value,
 151                                           exc_traceback)
 152
 153     def get_target(self):
 154         """Fetch the target being built or updated by this task.
 155         """
 156         return self.node
 157
 158     def executed(self):
 159         """Called when the task has been successfully executed.
 160
 161         This may have been a do-nothing operation (to preserve
 162         build order), so check the node's state before updating
 163         things.  Most importantly, this calls back to the
 164         Taskmaster to put any node tasks waiting on this one
 165         back on the pending list."""
 166         for t in self.targets:
 167             if t.get_state() == SCons.Node.executing:
 168                 for side_effect in t.side_effects:
 169                     side_effect.set_state(SCons.Node.no_state)
 170                 t.set_state(SCons.Node.executed)
 171                 t.built()
 172             else:
 173                 t.visited()
 174
 175         self.tm.executed(self.node)
 176
 177     def failed(self):
 178         """Default action when a task fails:  stop the build."""
 179         self.fail_stop()
 180
 181     def fail_stop(self):
 182         """Explicit stop-the-build failure."""
 183         for t in self.targets:
 184             t.set_state(SCons.Node.failed)
 185         self.tm.failed(self.node)
 186         next_top = self.tm.next_top_level_candidate()
 187         self.tm.stop()
 188
 189         if next_top:
 190             # We're stopping because of a build failure, but give the
 191             # calling Task class a chance to postprocess() the top-level
 192             # target under which the build failure occurred.
 193             self.targets = [next_top]
 194             self.top = 1
 195
 196     def fail_continue(self):
 197         """Explicit continue-the-build failure.
 198
 199         This sets failure status on the target nodes and all of
 200         their dependent parent nodes.
 201         """
 202         for t in self.targets:
 203             # Set failure state on all of the parents that were dependent
 204             # on this failed build.
 205             def set_state(node): node.set_state(SCons.Node.failed)
 206             t.call_for_all_waiting_parents(set_state)
 207
 208         self.tm.executed(self.node)
 209
 210     def make_ready_all(self):
 211         """Mark all targets in a task ready for execution.
 212
 213         This is used when the interface needs every target Node to be
 214         visited--the canonical example being the "scons -c" option.
 215         """
 216         self.out_of_date = self.targets[:]
 217         for t in self.targets:
 218             for s in t.side_effects:
 219                 s.set_state(SCons.Node.executing)
 220             t.set_state(SCons.Node.executing)
 221
 222     def make_ready_current(self):
 223         """Mark all targets in a task ready for execution if any target
 224         is not current.
 225
 226         This is the default behavior for building only what's necessary.
 227         """
 228         self.out_of_date = []
 229         for t in self.targets:
 230             if t.current():
 231                 t.set_state(SCons.Node.up_to_date)
 232             else:
 233                 self.out_of_date.append(t)
 234                 for s in t.side_effects:
 235                     s.set_state(SCons.Node.executing)
 236                 t.set_state(SCons.Node.executing)
 237
 238     make_ready = make_ready_current
 239
 240     def postprocess(self):
 241         """Post process a task after it's been executed."""
 242         for t in self.targets:
 243             t.postprocess()
 244
 245     def exc_info(self):
 246         return self.exception
 247
 248     def exc_clear(self):
 249         self.exception = (None, None, None)
 250         self.exception_raise = self._no_exception_to_raise
 251
 252     def exception_set(self, exception=None):
 253         if not exception:
 254             exception = sys.exc_info()
 255         self.exception = exception
 256         self.exception_raise = self._exception_raise
 257
 258     def _no_exception_to_raise(self):
 259         pass
 260
 261     def _exception_raise(self):
 262         """Raise a pending exception that was recorded while
 263         getting a Task ready for execution."""
 264         self.tm.exception_raise(self.exc_info())
 265
 266
 267 def order(dependencies):
 268     """Re-order a list of dependencies (if we need to)."""
 269     return dependencies
 270
 271
 272 class Taskmaster:
 273     """A generic Taskmaster for handling a bunch of targets.
 274
 275     Classes that override methods of this class should call
 276     the base class method, so this class can do its thing.
 277     """
 278
 279     def __init__(self, targets=[], tasker=Task, order=order, trace=None):
 280         self.targets = targets # top level targets
 281         self.candidates = targets[:] # nodes that might be ready to be executed
 282         self.candidates.reverse()
 283         self.executing = [] # nodes that are currently executing
 284         self.pending = [] # nodes that depend on a currently executing node
 285         self.tasker = tasker
 286         self.ready = None # the next task that is ready to be executed
 287         self.order = order
 288         self.message = None
 289         self.trace = trace
 290
 291         # See if we can alter the target list to find any
 292         # corresponding targets in linked build directories
 293         for node in self.targets:
 294             alt, message = node.alter_targets()
 295             if alt:
 296                 self.message = message
 297                 self.candidates.extend(self.order(alt))
 298                 continue
 299
 300     def _find_next_ready_node(self):
 301         """Find the next node that is ready to be built"""
 302
 303         if self.ready:
 304             return
 305
 306         self.ready_exc = None
 307
 308         T = self.trace
 309
 310         while self.candidates:
 311             node = self.candidates.pop()
 312             state = node.get_state()
 313
 314             if CollectStats:
 315                 if not hasattr(node, 'stats'):
 316                     node.stats = Stats()
 317                     StatsNodes.append(node)
 318                 S = node.stats
 319                 S.considered = S.considered + 1
 320             else:
 321                 S = None
 322
 323             if T: T.write('Taskmaster: %s:' % repr(str(node)))
 324
 325             # Skip this node if it has already been handled:
 326             if not state in [ SCons.Node.no_state, SCons.Node.stack ]:
 327                 if S: S.already_handled = S.already_handled + 1
 328                 if T: T.write(' already handled\n')
 329                 continue
 330
 331             # Mark this node as being on the execution stack:
 332             node.set_state(SCons.Node.stack)
 333
 334             try:
 335                 children = node.children()
 336             except SystemExit:
 337                 exc_value = sys.exc_info()[1]
 338                 e = SCons.Errors.ExplicitExit(node, exc_value.code)
 339                 self.ready_exc = (SCons.Errors.ExplicitExit, e)
 340                 self.ready = node
 341                 if T: T.write(' SystemExit\n')
 342                 break
 343             except KeyboardInterrupt:
 344                 if T: T.write(' KeyboardInterrupt\n')
 345                 raise
 346             except:
 347                 # We had a problem just trying to figure out the
 348                 # children (like a child couldn't be linked in to a
 349                 # BuildDir, or a Scanner threw something).  Arrange to
 350                 # raise the exception when the Task is "executed."
 351                 self.ready_exc = sys.exc_info()
 352                 self.ready = node
 353                 if S: S.problem = S.problem + 1
 354                 if T: T.write(' exception\n')
 355                 break
 356             else:
 357                 c = map(str, children)
 358                 c.sort()
 359                 if T: T.write(' children:\n    %s\n   ' % c)
 360
 361             childinfo = map(lambda N: (N.get_state(),
 362                                        N.is_derived() or N.is_pseudo_derived(),
 363                                        N), children)
 364
 365             # Skip this node if any of its children have failed.  This
 366             # catches the case where we're descending a top-level target
 367             # and one of our children failed while trying to be built
 368             # by a *previous* descent of an earlier top-level target.
 369             failed_children = filter(lambda I: I[0] == SCons.Node.failed,
 370                                      childinfo)
 371             if failed_children:
 372                 node.set_state(SCons.Node.failed)
 373                 if S: S.child_failed = S.child_failed + 1
 374                 if T:
 375                     c = map(str, failed_children)
 376                     c.sort()
 377                     T.write(' children failed:\n    %s\n' % c)
 378                 continue
 379
 380             # Detect dependency cycles:
 381             cycle = filter(lambda I: I[0] == SCons.Node.stack, childinfo)
 382             if cycle:
 383                 # The node we popped from the candidate stack is part of
 384                 # the cycle we detected, so put it back before generating
 385                 # the message to report.
 386                 self.candidates.append(node)
 387                 nodes = filter(lambda N: N.get_state() == SCons.Node.stack,
 388                                self.candidates) + \
 389                                map(lambda I: I[2], cycle)
 390                 nodes.reverse()
 391                 desc = "Dependency cycle: " + string.join(map(str, nodes), " -> ")
 392                 if T: T.write(' dependency cycle\n')
 393                 raise SCons.Errors.UserError, desc
 394
 395             # Select all of the dependencies that are derived targets
 396             # (that is, children who have builders or are side effects).
 397             derived_children = filter(lambda I: I[1], childinfo)
 398
 399             not_started = filter(lambda I: not I[0], derived_children)
 400             if not_started:
 401                 not_started = map(lambda I: I[2], not_started)
 402
 403                 # We're waiting on one more derived targets that have
 404                 # not yet started building.  Add this node to the
 405                 # waiting_parents lists of those derived files so that
 406                 # when they've finished building, our implicit dependency
 407                 # list will get cleared and we'll re-scan the newly-built
 408                 # file(s) for updated implicit dependencies.
 409                 map(lambda n, P=node: n.add_to_waiting_parents(P), not_started)
 410
 411                 # Now we add these derived targets to the candidates
 412                 # list so they can be examined and built.  We have to
 413                 # add ourselves back to the list first, though, so we get
 414                 # a chance to re-scan and build after the dependencies.
 415                 #
 416                 # We reverse the order in which the children are added
 417                 # to the candidates stack so the order in which they're
 418                 # popped matches the order in which they show up in our
 419                 # children's list.  This is more logical / efficient for
 420                 # builders with multiple targets, since the "primary"
 421                 # target will be examined first.
 422                 self.candidates.append(node)
 423                 not_started.reverse()
 424                 self.candidates.extend(self.order(not_started))
 425                 if S: S.not_started = S.not_started + 1
 426                 if T:
 427                     c = map(str, not_started)
 428                     c.sort()
 429                     T.write(' waiting on unstarted children:\n    %s\n' % c)
 430                 continue
 431
 432             not_built = filter(lambda I: I[0] <= SCons.Node.executing, derived_children)
 433             if not_built:
 434                 not_built = map(lambda I: I[2], not_built)
 435
 436                 # We're waiting on one or more derived targets that have
 437                 # started building but not yet finished.  Add this node
 438                 # to the waiting parents lists of those derived files
 439                 # so that when they've finished building, our implicit
 440                 # dependency list will get cleared and we'll re-scan the
 441                 # newly-built file(s) for updated implicit dependencies.
 442                 map(lambda n, P=node: n.add_to_waiting_parents(P), not_built)
 443
 444                 # And add this node to the "pending" list, so it can get
 445                 # put back on the candidates list when appropriate.
 446                 self.pending.append(node)
 447                 node.set_state(SCons.Node.pending)
 448                 if S: S.not_built = S.not_built + 1
 449                 if T:
 450                     c = map(str, not_built)
 451                     c.sort()
 452                     T.write(' waiting on unfinished children:\n    %s\n' % c)
 453                 continue
 454
 455             # Skip this node if it has side-effects that are
 456             # currently being built:
 457             side_effects = reduce(lambda E,N:
 458                                   E or N.get_state() == SCons.Node.executing,
 459                                   node.side_effects,
 460                                   0)
 461             if side_effects:
 462                 self.pending.append(node)
 463                 node.set_state(SCons.Node.pending)
 464                 if S: S.side_effects = S.side_effects + 1
 465                 if T:
 466                     c = map(str, side_effects)
 467                     c.sort()
 468                     T.write(' waiting on side effects:\n    %s\n' % c)
 469                 continue
 470
 471             # The default when we've gotten through all of the checks above:
 472             # this node is ready to be built.
 473             self.ready = node
 474             if S: S.build = S.build + 1
 475             if T: T.write(' evaluating\n')
 476             break
 477
 478     def next_task(self):
 479         """Return the next task to be executed."""
 480
 481         self._find_next_ready_node()
 482
 483         node = self.ready
 484
 485         if node is None:
 486             return None
 487
 488         try:
 489             tlist = node.builder.targets(node)
 490         except AttributeError:
 491             tlist = [node]
 492         self.executing.extend(tlist)
 493         self.executing.extend(node.side_effects)
 494
 495         task = self.tasker(self, tlist, node in self.targets, node)
 496         try:
 497             task.make_ready()
 498         except KeyboardInterrupt:
 499             raise
 500         except:
 501             # We had a problem just trying to get this task ready (like
 502             # a child couldn't be linked in to a BuildDir when deciding
 503             # whether this node is current).  Arrange to raise the
 504             # exception when the Task is "executed."
 505             self.ready_exc = sys.exc_info()
 506
 507         if self.ready_exc:
 508             task.exception_set(self.ready_exc)
 509
 510         self.ready = None
 511         self.ready_exc = None
 512
 513         return task
 514
 515     def is_blocked(self):
 516         self._find_next_ready_node()
 517
 518         return not self.ready and (self.pending or self.executing)
 519
 520     def next_top_level_candidate(self):
 521         candidates = self.candidates[:]
 522         candidates.reverse()
 523         for c in candidates:
 524             if c in self.targets:
 525                 return c
 526         return None
 527
 528     def stop(self):
 529         """Stop the current build completely."""
 530         self.candidates = []
 531         self.ready = None
 532         self.pending = []
 533
 534     def failed(self, node):
 535         try:
 536             tlist = node.builder.targets(node)
 537         except AttributeError:
 538             tlist = [node]
 539         for t in tlist:
 540             self.executing.remove(t)
 541         for side_effect in node.side_effects:
 542             self.executing.remove(side_effect)
 543
 544     def executed(self, node):
 545         try:
 546             tlist = node.builder.targets(node)
 547         except AttributeError:
 548             tlist = [node]
 549         for t in tlist:
 550             self.executing.remove(t)
 551         for side_effect in node.side_effects:
 552             self.executing.remove(side_effect)
 553
 554         # move the current pending nodes to the candidates list:
 555         # (they may not all be ready to build, but _find_next_ready_node()
 556         #  will figure out which ones are really ready)
 557         for node in self.pending:
 558             node.set_state(SCons.Node.no_state)
 559         self.pending.reverse()
 560         self.candidates.extend(self.pending)
 561         self.pending = []
 562
 563     def exception_raise(self, exception):
 564         exc = exception[:]
 565         try:
 566             exc_type, exc_value, exc_traceback = exc
 567         except ValueError:
 568             exc_type, exc_value = exc
 569             exc_traceback = None
 570         raise exc_type, exc_value, exc_traceback