src/engine/SCons/Taskmaster.py

   1 #
   2 # __COPYRIGHT__
   3 #
   4 # Permission is hereby granted, free of charge, to any person obtaining
   5 # a copy of this software and associated documentation files (the
   6 # "Software"), to deal in the Software without restriction, including
   7 # without limitation the rights to use, copy, modify, merge, publish,
   8 # distribute, sublicense, and/or sell copies of the Software, and to
   9 # permit persons to whom the Software is furnished to do so, subject to
  10 # the following conditions:
  11 #
  12 # The above copyright notice and this permission notice shall be included
  13 # in all copies or substantial portions of the Software.
  14 #
  15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
  16 # KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  17 # WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  19 # LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  20 # OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  21 # WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22 #
  23
  24 __doc__ = """
  25 Generic Taskmaster module for the SCons build engine.
  26
  27 This module contains the primary interface(s) between a wrapping user
  28 interface and the SCons build engine.  There are two key classes here:
  29
  30     Taskmaster
  31         This is the main engine for walking the dependency graph and
  32         calling things to decide what does or doesn't need to be built.
  33
  34     Task
  35         This is the base class for allowing a wrapping interface to
  36         decide what does or doesn't actually need to be done.  The
  37         intention is for a wrapping interface to subclass this as
  38         appropriate for different types of behavior it may need.
  39
  40         The canonical example is the SCons native Python interface,
  41         which has Task subclasses that handle its specific behavior,
  42         like printing "`foo' is up to date" when a top-level target
  43         doesn't need to be built, and handling the -c option by removing
  44         targets as its "build" action.  There is also a separate subclass
  45         for suppressing this output when the -q option is used.
  46
  47         The Taskmaster instantiates a Task object for each (set of)
  48         target(s) that it decides need to be evaluated and/or built.
  49 """
  50
  51 __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__"
  52
  53 import SCons.compat
  54
  55 import operator
  56 import string
  57 import sys
  58 import traceback
  59
  60 import SCons.Node
  61 import SCons.Errors
  62
  63 StateString = SCons.Node.StateString
  64
  65
  66
  67 # A subsystem for recording stats about how different Nodes are handled by
  68 # the main Taskmaster loop.  There's no external control here (no need for
  69 # a --debug= option); enable it by changing the value of CollectStats.
  70
  71 CollectStats = None
  72
  73 class Stats:
  74     """
  75     A simple class for holding statistics about the disposition of a
  76     Node by the Taskmaster.  If we're collecting statistics, each Node
  77     processed by the Taskmaster gets one of these attached, in which case
  78     the Taskmaster records its decision each time it processes the Node.
  79     (Ideally, that's just once per Node.)
  80     """
  81     def __init__(self):
  82         """
  83         Instantiates a Taskmaster.Stats object, initializing all
  84         appropriate counters to zero.
  85         """
  86         self.considered  = 0
  87         self.already_handled  = 0
  88         self.problem  = 0
  89         self.child_failed  = 0
  90         self.not_built  = 0
  91         self.side_effects  = 0
  92         self.build  = 0
  93
  94 StatsNodes = []
  95
  96 fmt = "%(considered)3d "\
  97       "%(already_handled)3d " \
  98       "%(problem)3d " \
  99       "%(child_failed)3d " \
 100       "%(not_built)3d " \
 101       "%(side_effects)3d " \
 102       "%(build)3d "
 103
 104 def dump_stats():
 105     StatsNodes.sort(lambda a, b: cmp(str(a), str(b)))
 106     for n in StatsNodes:
 107         print (fmt % n.stats.__dict__) + str(n)
 108
 109
 110
 111 class Task:
 112     """
 113     Default SCons build engine task.
 114
 115     This controls the interaction of the actual building of node
 116     and the rest of the engine.
 117
 118     This is expected to handle all of the normally-customizable
 119     aspects of controlling a build, so any given application
 120     *should* be able to do what it wants by sub-classing this
 121     class and overriding methods as appropriate.  If an application
 122     needs to customze something by sub-classing Taskmaster (or
 123     some other build engine class), we should first try to migrate
 124     that functionality into this class.
 125
 126     Note that it's generally a good idea for sub-classes to call
 127     these methods explicitly to update state, etc., rather than
 128     roll their own interaction with Taskmaster from scratch.
 129     """
 130     def __init__(self, tm, targets, top, node):
 131         self.tm = tm
 132         self.targets = targets
 133         self.top = top
 134         self.node = node
 135         self.exc_clear()
 136
 137     def display(self, message):
 138         """
 139         Hook to allow the calling interface to display a message.
 140
 141         This hook gets called as part of preparing a task for execution
 142         (that is, a Node to be built).  As part of figuring out what Node
 143         should be built next, the actually target list may be altered,
 144         along with a message describing the alteration.  The calling
 145         interface can subclass Task and provide a concrete implementation
 146         of this method to see those messages.
 147         """
 148         pass
 149
 150     def prepare(self):
 151         """
 152         Called just before the task is executed.
 153
 154         This is mainly intended to give the target Nodes a chance to
 155         unlink underlying files and make all necessary directories before
 156         the Action is actually called to build the targets.
 157         """
 158
 159         # Now that it's the appropriate time, give the TaskMaster a
 160         # chance to raise any exceptions it encountered while preparing
 161         # this task.
 162         self.exception_raise()
 163
 164         if self.tm.message:
 165             self.display(self.tm.message)
 166             self.tm.message = None
 167
 168         for t in self.targets:
 169             t.prepare()
 170             for s in t.side_effects:
 171                 s.prepare()
 172
 173     def get_target(self):
 174         """Fetch the target being built or updated by this task.
 175         """
 176         return self.node
 177
 178     def execute(self):
 179         """
 180         Called to execute the task.
 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         prepare(), executed() or failed().
 185         """
 186
 187         try:
 188             everything_was_cached = 1
 189             for t in self.targets:
 190                 if not t.retrieve_from_cache():
 191                     everything_was_cached = 0
 192                     break
 193             if not everything_was_cached:
 194                 self.targets[0].build()
 195         except KeyboardInterrupt:
 196             raise
 197         except SystemExit:
 198             exc_value = sys.exc_info()[1]
 199             raise SCons.Errors.ExplicitExit(self.targets[0], exc_value.code)
 200         except SCons.Errors.UserError:
 201             raise
 202         except SCons.Errors.BuildError:
 203             raise
 204         except:
 205             raise SCons.Errors.TaskmasterException(self.targets[0],
 206                                                    sys.exc_info())
 207
 208     def executed(self):
 209         """
 210         Called when the task has been successfully executed.
 211
 212         This may have been a do-nothing operation (to preserve build
 213         order), so we have to check the node's state before deciding
 214         whether it was "built" or just "visited."
 215         """
 216         for t in self.targets:
 217             if t.get_state() == SCons.Node.executing:
 218                 t.set_state(SCons.Node.executed)
 219                 t.built()
 220             else:
 221                 t.visited()
 222
 223     def failed(self):
 224         """
 225         Default action when a task fails:  stop the build.
 226         """
 227         self.fail_stop()
 228
 229     def fail_stop(self):
 230         """
 231         Explicit stop-the-build failure.
 232         """
 233         for t in self.targets:
 234             t.set_state(SCons.Node.failed)
 235         self.tm.stop()
 236
 237         # We're stopping because of a build failure, but give the
 238         # calling Task class a chance to postprocess() the top-level
 239         # target under which the build failure occurred.
 240         self.targets = [self.tm.current_top]
 241         self.top = 1
 242
 243     def fail_continue(self):
 244         """
 245         Explicit continue-the-build failure.
 246
 247         This sets failure status on the target nodes and all of
 248         their dependent parent nodes.
 249         """
 250         for t in self.targets:
 251             # Set failure state on all of the parents that were dependent
 252             # on this failed build.
 253             def set_state(node): node.set_state(SCons.Node.failed)
 254             t.call_for_all_waiting_parents(set_state)
 255
 256     def make_ready_all(self):
 257         """
 258         Marks all targets in a task ready for execution.
 259
 260         This is used when the interface needs every target Node to be
 261         visited--the canonical example being the "scons -c" option.
 262         """
 263         self.out_of_date = self.targets[:]
 264         for t in self.targets:
 265             t.disambiguate().set_state(SCons.Node.executing)
 266             for s in t.side_effects:
 267                 s.set_state(SCons.Node.executing)
 268
 269     def make_ready_current(self):
 270         """
 271         Marks all targets in a task ready for execution if any target
 272         is not current.
 273
 274         This is the default behavior for building only what's necessary.
 275         """
 276         self.out_of_date = []
 277         for t in self.targets:
 278             try:
 279                 is_up_to_date = t.disambiguate().current()
 280             except EnvironmentError, e:
 281                 raise SCons.Errors.BuildError(node=t, errstr=e.strerror, filename=e.filename)
 282             if is_up_to_date:
 283                 t.set_state(SCons.Node.up_to_date)
 284             else:
 285                 self.out_of_date.append(t)
 286                 t.set_state(SCons.Node.executing)
 287                 for s in t.side_effects:
 288                     s.set_state(SCons.Node.executing)
 289
 290     make_ready = make_ready_current
 291
 292     def postprocess(self):
 293         """
 294         Post-processes a task after it's been executed.
 295
 296         This examines all the targets just built (or not, we don't care
 297         if the build was successful, or even if there was no build
 298         because everything was up-to-date) to see if they have any
 299         waiting parent Nodes, or Nodes waiting on a common side effect,
 300         that can be put back on the candidates list.
 301         """
 302
 303         # We may have built multiple targets, some of which may have
 304         # common parents waiting for this build.  Count up how many
 305         # targets each parent was waiting for so we can subtract the
 306         # values later, and so we *don't* put waiting side-effect Nodes
 307         # back on the candidates list if the Node is also a waiting
 308         # parent.
 309
 310         parents = {}
 311         for t in self.targets:
 312             for p in t.waiting_parents.keys():
 313                 parents[p] = parents.get(p, 0) + 1
 314
 315         for t in self.targets:
 316             for s in t.side_effects:
 317                 if s.get_state() == SCons.Node.executing:
 318                     s.set_state(SCons.Node.no_state)
 319                     for p in s.waiting_parents.keys():
 320                         if not parents.has_key(p):
 321                             parents[p] = 1
 322                 for p in s.waiting_s_e.keys():
 323                     if p.ref_count == 0:
 324                         self.tm.candidates.append(p)
 325
 326         for p, subtract in parents.items():
 327             p.ref_count = p.ref_count - subtract
 328             if p.ref_count == 0:
 329                 self.tm.candidates.append(p)
 330
 331         for t in self.targets:
 332             t.postprocess()
 333
 334     # Exception handling subsystem.
 335     #
 336     # Exceptions that occur while walking the DAG or examining Nodes
 337     # must be raised, but must be raised at an appropriate time and in
 338     # a controlled manner so we can, if necessary, recover gracefully,
 339     # possibly write out signature information for Nodes we've updated,
 340     # etc.  This is done by having the Taskmaster tell us about the
 341     # exception, and letting
 342
 343     def exc_info(self):
 344         """
 345         Returns info about a recorded exception.
 346         """
 347         return self.exception
 348
 349     def exc_clear(self):
 350         """
 351         Clears any recorded exception.
 352
 353         This also changes the "exception_raise" attribute to point
 354         to the appropriate do-nothing method.
 355         """
 356         self.exception = (None, None, None)
 357         self.exception_raise = self._no_exception_to_raise
 358
 359     def exception_set(self, exception=None):
 360         """
 361         Records an exception to be raised at the appropriate time.
 362
 363         This also changes the "exception_raise" attribute to point
 364         to the method that will, in fact
 365         """
 366         if not exception:
 367             exception = sys.exc_info()
 368         self.exception = exception
 369         self.exception_raise = self._exception_raise
 370
 371     def _no_exception_to_raise(self):
 372         pass
 373
 374     def _exception_raise(self):
 375         """
 376         Raises a pending exception that was recorded while getting a
 377         Task ready for execution.
 378         """
 379         exc = self.exc_info()[:]
 380         try:
 381             exc_type, exc_value, exc_traceback = exc
 382         except ValueError:
 383             exc_type, exc_value = exc
 384             exc_traceback = None
 385         raise exc_type, exc_value, exc_traceback
 386
 387
 388 def find_cycle(stack):
 389     if stack[0] == stack[-1]:
 390         return stack
 391     for n in stack[-1].waiting_parents.keys():
 392         stack.append(n)
 393         if find_cycle(stack):
 394             return stack
 395         stack.pop()
 396     return None
 397
 398
 399 class Taskmaster:
 400     """
 401     The Taskmaster for walking the dependency DAG.
 402     """
 403
 404     def __init__(self, targets=[], tasker=Task, order=None, trace=None):
 405         self.top_targets = targets[:]
 406         self.top_targets.reverse()
 407         self.candidates = []
 408         self.tasker = tasker
 409         if not order:
 410             order = lambda l: l
 411         self.order = order
 412         self.message = None
 413         self.trace = trace
 414         self.next_candidate = self.find_next_candidate
 415
 416     def find_next_candidate(self):
 417         """
 418         Returns the next candidate Node for (potential) evaluation.
 419
 420         The candidate list (really a stack) initially consists of all of
 421         the top-level (command line) targets provided when the Taskmaster
 422         was initialized.  While we walk the DAG, visiting Nodes, all the
 423         children that haven't finished processing get pushed on to the
 424         candidate list.  Each child can then be popped and examined in
 425         turn for whether *their* children are all up-to-date, in which
 426         case a Task will be created for their actual evaluation and
 427         potential building.
 428
 429         Here is where we also allow candidate Nodes to alter the list of
 430         Nodes that should be examined.  This is used, for example, when
 431         invoking SCons in a source directory.  A source directory Node can
 432         return its corresponding build directory Node, essentially saying,
 433         "Hey, you really need to build this thing over here instead."
 434         """
 435         try:
 436             return self.candidates.pop()
 437         except IndexError:
 438             pass
 439         try:
 440             node = self.top_targets.pop()
 441         except IndexError:
 442             return None
 443         self.current_top = node
 444         alt, message = node.alter_targets()
 445         if alt:
 446             self.message = message
 447             self.candidates.append(node)
 448             self.candidates.extend(self.order(alt))
 449             node = self.candidates.pop()
 450         return node
 451
 452     def no_next_candidate(self):
 453         """
 454         Stops Taskmaster processing by not returning a next candidate.
 455         """
 456         return None
 457
 458     def _find_next_ready_node(self):
 459         """
 460         Finds the next node that is ready to be built.
 461
 462         This is *the* main guts of the DAG walk.  We loop through the
 463         list of candidates, looking for something that has no un-built
 464         children (i.e., that is a leaf Node or has dependencies that are
 465         all leaf Nodes or up-to-date).  Candidate Nodes are re-scanned
 466         (both the target Node itself and its sources, which are always
 467         scanned in the context of a given target) to discover implicit
 468         dependencies.  A Node that must wait for some children to be
 469         built will be put back on the candidates list after the children
 470         have finished building.  A Node that has been put back on the
 471         candidates list in this way may have itself (or its sources)
 472         re-scanned, in order to handle generated header files (e.g.) and
 473         the implicit dependencies therein.
 474
 475         Note that this method does not do any signature calculation or
 476         up-to-date check itself.  All of that is handled by the Task
 477         class.  This is purely concerned with the dependency graph walk.
 478         """
 479
 480         self.ready_exc = None
 481
 482         T = self.trace
 483
 484         while 1:
 485             node = self.next_candidate()
 486             if node is None:
 487                 return None
 488
 489             node = node.disambiguate()
 490             state = node.get_state()
 491
 492             if CollectStats:
 493                 if not hasattr(node, 'stats'):
 494                     node.stats = Stats()
 495                     StatsNodes.append(node)
 496                 S = node.stats
 497                 S.considered = S.considered + 1
 498             else:
 499                 S = None
 500
 501             if T: T.write('Taskmaster: %s:' % repr(str(node)))
 502
 503             # Skip this node if it has already been evaluated:
 504             if state > SCons.Node.pending:
 505                 if S: S.already_handled = S.already_handled + 1
 506                 if T: T.write(' already handled (%s)\n' % StateString[state])
 507                 continue
 508
 509             # Mark this node as being on the execution stack:
 510             node.set_state(SCons.Node.pending)
 511
 512             try:
 513                 children = node.children()
 514             except SystemExit:
 515                 exc_value = sys.exc_info()[1]
 516                 e = SCons.Errors.ExplicitExit(node, exc_value.code)
 517                 self.ready_exc = (SCons.Errors.ExplicitExit, e)
 518                 if T: T.write(' SystemExit\n')
 519                 return node
 520             except KeyboardInterrupt:
 521                 if T: T.write(' KeyboardInterrupt\n')
 522                 raise
 523             except:
 524                 # We had a problem just trying to figure out the
 525                 # children (like a child couldn't be linked in to a
 526                 # BuildDir, or a Scanner threw something).  Arrange to
 527                 # raise the exception when the Task is "executed."
 528                 self.ready_exc = sys.exc_info()
 529                 if S: S.problem = S.problem + 1
 530                 if T: T.write(' exception\n')
 531                 return node
 532
 533             if T and children:
 534                 c = map(str, children)
 535                 c.sort()
 536                 T.write(' children:\n    %s\n   ' % c)
 537
 538             childinfo = map(lambda N: (N.get_state(),
 539                                        N.is_derived() or N.is_pseudo_derived(),
 540                                        N), children)
 541
 542             # Skip this node if any of its children have failed.  This
 543             # catches the case where we're descending a top-level target
 544             # and one of our children failed while trying to be built
 545             # by a *previous* descent of an earlier top-level target.
 546             failed_children = filter(lambda I: I[0] == SCons.Node.failed,
 547                                      childinfo)
 548             if failed_children:
 549                 node.set_state(SCons.Node.failed)
 550                 if S: S.child_failed = S.child_failed + 1
 551                 if T:
 552                     c = map(str, failed_children)
 553                     c.sort()
 554                     T.write(' children failed:\n    %s\n' % c)
 555                 continue
 556
 557             # Detect dependency cycles:
 558             pending_nodes = filter(lambda I: I[0] == SCons.Node.pending, childinfo)
 559             if pending_nodes:
 560                 for p in pending_nodes:
 561                     cycle = find_cycle([p[2], node])
 562                     if cycle:
 563                         desc = "Dependency cycle: " + string.join(map(str, cycle), " -> ")
 564                         if T: T.write(' dependency cycle\n')
 565                         raise SCons.Errors.UserError, desc
 566
 567             # Select all of the dependencies that are derived targets
 568             # (that is, children who have builders or are side effects).
 569             derived_children = filter(lambda I: I[1], childinfo)
 570
 571             not_started = filter(lambda I: not I[0], derived_children)
 572             if not_started:
 573                 not_started = map(lambda I: I[2], not_started)
 574
 575                 # We're waiting on one more derived targets that have
 576                 # not yet started building.  Add this node to the
 577                 # waiting_parents lists of those derived files so that
 578                 # when they've finished building, our implicit dependency
 579                 # list will get cleared and we'll re-scan the newly-built
 580                 # file(s) for updated implicit dependencies.
 581                 added = map(lambda n, P=node: n.add_to_waiting_parents(P), not_started)
 582                 node.ref_count = node.ref_count + reduce(operator.add, added, 0)
 583
 584                 # Now we add these derived targets to the candidates
 585                 # list so they can be examined and built.  We have to
 586                 # add ourselves back to the list first, though, so we get
 587                 # a chance to re-scan and build after the dependencies.
 588                 #
 589                 # We reverse the order in which the children are added
 590                 # to the candidates stack so the order in which they're
 591                 # popped matches the order in which they show up in our
 592                 # children's list.  This is more logical / efficient for
 593                 # builders with multiple targets, since the "primary"
 594                 # target will be examined first.
 595                 self.candidates.append(node)
 596                 not_started.reverse()
 597                 self.candidates.extend(self.order(not_started))
 598
 599                 if S: S.not_started = S.not_started + 1
 600                 if T:
 601                     c = map(str, not_started)
 602                     c.sort()
 603                     T.write(' waiting on unstarted children:\n    %s\n' % c)
 604                 continue
 605
 606             not_built = filter(lambda I: I[0] <= SCons.Node.executing, derived_children)
 607             if not_built:
 608                 not_built = map(lambda I: I[2], not_built)
 609
 610                 # We're waiting on one or more derived targets that have
 611                 # started building but not yet finished.  Add this node
 612                 # to the waiting parents lists of those derived files
 613                 # so that when they've finished building, our implicit
 614                 # dependency list will get cleared and we'll re-scan the
 615                 # newly-built file(s) for updated implicit dependencies.
 616                 added = map(lambda n, P=node: n.add_to_waiting_parents(P), not_built)
 617                 node.ref_count = node.ref_count + reduce(operator.add, added, 0)
 618
 619                 if S: S.not_built = S.not_built + 1
 620                 if T:
 621                     c = map(str, not_built)
 622                     c.sort()
 623                     T.write(' waiting on unfinished children:\n    %s\n' % c)
 624                 continue
 625
 626             # Skip this node if it has side-effects that are currently being
 627             # built themselves or waiting for something else being built.
 628             side_effects = filter(lambda N:
 629                                   N.get_state() == SCons.Node.executing,
 630                                   node.side_effects)
 631             if side_effects:
 632                 map(lambda n, P=node: n.add_to_waiting_s_e(P), side_effects)
 633                 if S: S.side_effects = S.side_effects + 1
 634                 if T:
 635                     c = map(str, side_effects)
 636                     c.sort()
 637                     T.write(' waiting on side effects:\n    %s\n' % c)
 638                 continue
 639
 640             # The default when we've gotten through all of the checks above:
 641             # this node is ready to be built.
 642             if S: S.build = S.build + 1
 643             if T: T.write(' evaluating %s\n' % node)
 644             return node
 645
 646         return None
 647
 648     def next_task(self):
 649         """
 650         Returns the next task to be executed.
 651
 652         This simply asks for the next Node to be evaluated, and then wraps
 653         it in the specific Task subclass with which we were initialized.
 654         """
 655         node = self._find_next_ready_node()
 656
 657         if node is None:
 658             return None
 659
 660         tlist = node.get_executor().targets
 661
 662         task = self.tasker(self, tlist, node is self.current_top, node)
 663         try:
 664             task.make_ready()
 665         except KeyboardInterrupt:
 666             raise
 667         except:
 668             # We had a problem just trying to get this task ready (like
 669             # a child couldn't be linked in to a BuildDir when deciding
 670             # whether this node is current).  Arrange to raise the
 671             # exception when the Task is "executed."
 672             self.ready_exc = sys.exc_info()
 673
 674         if self.ready_exc:
 675             task.exception_set(self.ready_exc)
 676
 677         self.ready_exc = None
 678
 679         return task
 680
 681     def stop(self):
 682         """
 683         Stops the current build completely.
 684         """
 685         self.next_candidate = self.no_next_candidate