Package SCons :: Module Taskmaster
[hide private]
[frames] | no frames]

Source Code for Module SCons.Taskmaster

   1  # 
   2  # Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 The SCons Foundation 
   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  __doc__ = """ 
  24  Generic Taskmaster module for the SCons build engine. 
  25   
  26  This module contains the primary interface(s) between a wrapping user 
  27  interface and the SCons build engine.  There are two key classes here: 
  28   
  29      Taskmaster 
  30          This is the main engine for walking the dependency graph and 
  31          calling things to decide what does or doesn't need to be built. 
  32   
  33      Task 
  34          This is the base class for allowing a wrapping interface to 
  35          decide what does or doesn't actually need to be done.  The 
  36          intention is for a wrapping interface to subclass this as 
  37          appropriate for different types of behavior it may need. 
  38   
  39          The canonical example is the SCons native Python interface, 
  40          which has Task subclasses that handle its specific behavior, 
  41          like printing "`foo' is up to date" when a top-level target 
  42          doesn't need to be built, and handling the -c option by removing 
  43          targets as its "build" action.  There is also a separate subclass 
  44          for suppressing this output when the -q option is used. 
  45   
  46          The Taskmaster instantiates a Task object for each (set of) 
  47          target(s) that it decides need to be evaluated and/or built. 
  48  """ 
  49   
  50  __revision__ = "src/engine/SCons/Taskmaster.py  2013/03/03 09:48:35 garyo" 
  51   
  52  from itertools import chain 
  53  import operator 
  54  import sys 
  55  import traceback 
  56   
  57  import SCons.Errors 
  58  import SCons.Node 
  59  import SCons.Warnings 
  60   
  61  StateString = SCons.Node.StateString 
  62  NODE_NO_STATE = SCons.Node.no_state 
  63  NODE_PENDING = SCons.Node.pending 
  64  NODE_EXECUTING = SCons.Node.executing 
  65  NODE_UP_TO_DATE = SCons.Node.up_to_date 
  66  NODE_EXECUTED = SCons.Node.executed 
  67  NODE_FAILED = SCons.Node.failed 
  68   
  69  print_prepare = 0               # set by option --debug=prepare 
  70   
  71  # A subsystem for recording stats about how different Nodes are handled by 
  72  # the main Taskmaster loop.  There's no external control here (no need for 
  73  # a --debug= option); enable it by changing the value of CollectStats. 
  74   
  75  CollectStats = None 
  76   
77 -class Stats(object):
78 """ 79 A simple class for holding statistics about the disposition of a 80 Node by the Taskmaster. If we're collecting statistics, each Node 81 processed by the Taskmaster gets one of these attached, in which case 82 the Taskmaster records its decision each time it processes the Node. 83 (Ideally, that's just once per Node.) 84 """
85 - def __init__(self):
86 """ 87 Instantiates a Taskmaster.Stats object, initializing all 88 appropriate counters to zero. 89 """ 90 self.considered = 0 91 self.already_handled = 0 92 self.problem = 0 93 self.child_failed = 0 94 self.not_built = 0 95 self.side_effects = 0 96 self.build = 0
97 98 StatsNodes = [] 99 100 fmt = "%(considered)3d "\ 101 "%(already_handled)3d " \ 102 "%(problem)3d " \ 103 "%(child_failed)3d " \ 104 "%(not_built)3d " \ 105 "%(side_effects)3d " \ 106 "%(build)3d " 107
108 -def dump_stats():
109 for n in sorted(StatsNodes, key=lambda a: str(a)): 110 print (fmt % n.stats.__dict__) + str(n)
111 112 113
114 -class Task(object):
115 """ 116 Default SCons build engine task. 117 118 This controls the interaction of the actual building of node 119 and the rest of the engine. 120 121 This is expected to handle all of the normally-customizable 122 aspects of controlling a build, so any given application 123 *should* be able to do what it wants by sub-classing this 124 class and overriding methods as appropriate. If an application 125 needs to customze something by sub-classing Taskmaster (or 126 some other build engine class), we should first try to migrate 127 that functionality into this class. 128 129 Note that it's generally a good idea for sub-classes to call 130 these methods explicitly to update state, etc., rather than 131 roll their own interaction with Taskmaster from scratch. 132 """
133 - def __init__(self, tm, targets, top, node):
134 self.tm = tm 135 self.targets = targets 136 self.top = top 137 self.node = node 138 self.exc_clear()
139
140 - def trace_message(self, method, node, description='node'):
141 fmt = '%-20s %s %s\n' 142 return fmt % (method + ':', description, self.tm.trace_node(node))
143
144 - def display(self, message):
145 """ 146 Hook to allow the calling interface to display a message. 147 148 This hook gets called as part of preparing a task for execution 149 (that is, a Node to be built). As part of figuring out what Node 150 should be built next, the actually target list may be altered, 151 along with a message describing the alteration. The calling 152 interface can subclass Task and provide a concrete implementation 153 of this method to see those messages. 154 """ 155 pass
156
157 - def prepare(self):
158 """ 159 Called just before the task is executed. 160 161 This is mainly intended to give the target Nodes a chance to 162 unlink underlying files and make all necessary directories before 163 the Action is actually called to build the targets. 164 """ 165 global print_prepare 166 T = self.tm.trace 167 if T: T.write(self.trace_message(u'Task.prepare()', self.node)) 168 169 # Now that it's the appropriate time, give the TaskMaster a 170 # chance to raise any exceptions it encountered while preparing 171 # this task. 172 self.exception_raise() 173 174 if self.tm.message: 175 self.display(self.tm.message) 176 self.tm.message = None 177 178 # Let the targets take care of any necessary preparations. 179 # This includes verifying that all of the necessary sources 180 # and dependencies exist, removing the target file(s), etc. 181 # 182 # As of April 2008, the get_executor().prepare() method makes 183 # sure that all of the aggregate sources necessary to build this 184 # Task's target(s) exist in one up-front check. The individual 185 # target t.prepare() methods check that each target's explicit 186 # or implicit dependencies exists, and also initialize the 187 # .sconsign info. 188 executor = self.targets[0].get_executor() 189 executor.prepare() 190 for t in executor.get_action_targets(): 191 if print_prepare: 192 print "Preparing target %s..."%t 193 for s in t.side_effects: 194 print "...with side-effect %s..."%s 195 t.prepare() 196 for s in t.side_effects: 197 if print_prepare: 198 print "...Preparing side-effect %s..."%s 199 s.prepare()
200
201 - def get_target(self):
202 """Fetch the target being built or updated by this task. 203 """ 204 return self.node
205
206 - def needs_execute(self):
207 # TODO(deprecate): "return True" is the old default behavior; 208 # change it to NotImplementedError (after running through the 209 # Deprecation Cycle) so the desired behavior is explicitly 210 # determined by which concrete subclass is used. 211 #raise NotImplementedError 212 msg = ('Taskmaster.Task is an abstract base class; instead of\n' 213 '\tusing it directly, ' 214 'derive from it and override the abstract methods.') 215 SCons.Warnings.warn(SCons.Warnings.TaskmasterNeedsExecuteWarning, msg) 216 return True
217
218 - def execute(self):
219 """ 220 Called to execute the task. 221 222 This method is called from multiple threads in a parallel build, 223 so only do thread safe stuff here. Do thread unsafe stuff in 224 prepare(), executed() or failed(). 225 """ 226 T = self.tm.trace 227 if T: T.write(self.trace_message(u'Task.execute()', self.node)) 228 229 try: 230 cached_targets = [] 231 for t in self.targets: 232 if not t.retrieve_from_cache(): 233 break 234 cached_targets.append(t) 235 if len(cached_targets) < len(self.targets): 236 # Remove targets before building. It's possible that we 237 # partially retrieved targets from the cache, leaving 238 # them in read-only mode. That might cause the command 239 # to fail. 240 # 241 for t in cached_targets: 242 try: 243 t.fs.unlink(t.path) 244 except (IOError, OSError): 245 pass 246 self.targets[0].build() 247 else: 248 for t in cached_targets: 249 t.cached = 1 250 except SystemExit: 251 exc_value = sys.exc_info()[1] 252 raise SCons.Errors.ExplicitExit(self.targets[0], exc_value.code) 253 except SCons.Errors.UserError: 254 raise 255 except SCons.Errors.BuildError: 256 raise 257 except Exception, e: 258 buildError = SCons.Errors.convert_to_BuildError(e) 259 buildError.node = self.targets[0] 260 buildError.exc_info = sys.exc_info() 261 raise buildError
262
263 - def executed_without_callbacks(self):
264 """ 265 Called when the task has been successfully executed 266 and the Taskmaster instance doesn't want to call 267 the Node's callback methods. 268 """ 269 T = self.tm.trace 270 if T: T.write(self.trace_message('Task.executed_without_callbacks()', 271 self.node)) 272 273 for t in self.targets: 274 if t.get_state() == NODE_EXECUTING: 275 for side_effect in t.side_effects: 276 side_effect.set_state(NODE_NO_STATE) 277 t.set_state(NODE_EXECUTED)
278
279 - def executed_with_callbacks(self):
280 """ 281 Called when the task has been successfully executed and 282 the Taskmaster instance wants to call the Node's callback 283 methods. 284 285 This may have been a do-nothing operation (to preserve build 286 order), so we must check the node's state before deciding whether 287 it was "built", in which case we call the appropriate Node method. 288 In any event, we always call "visited()", which will handle any 289 post-visit actions that must take place regardless of whether 290 or not the target was an actual built target or a source Node. 291 """ 292 T = self.tm.trace 293 if T: T.write(self.trace_message('Task.executed_with_callbacks()', 294 self.node)) 295 296 for t in self.targets: 297 if t.get_state() == NODE_EXECUTING: 298 for side_effect in t.side_effects: 299 side_effect.set_state(NODE_NO_STATE) 300 t.set_state(NODE_EXECUTED) 301 if not t.cached: 302 t.push_to_cache() 303 t.built() 304 t.visited()
305 306 executed = executed_with_callbacks 307
308 - def failed(self):
309 """ 310 Default action when a task fails: stop the build. 311 312 Note: Although this function is normally invoked on nodes in 313 the executing state, it might also be invoked on up-to-date 314 nodes when using Configure(). 315 """ 316 self.fail_stop()
317
318 - def fail_stop(self):
319 """ 320 Explicit stop-the-build failure. 321 322 This sets failure status on the target nodes and all of 323 their dependent parent nodes. 324 325 Note: Although this function is normally invoked on nodes in 326 the executing state, it might also be invoked on up-to-date 327 nodes when using Configure(). 328 """ 329 T = self.tm.trace 330 if T: T.write(self.trace_message('Task.failed_stop()', self.node)) 331 332 # Invoke will_not_build() to clean-up the pending children 333 # list. 334 self.tm.will_not_build(self.targets, lambda n: n.set_state(NODE_FAILED)) 335 336 # Tell the taskmaster to not start any new tasks 337 self.tm.stop() 338 339 # We're stopping because of a build failure, but give the 340 # calling Task class a chance to postprocess() the top-level 341 # target under which the build failure occurred. 342 self.targets = [self.tm.current_top] 343 self.top = 1
344
345 - def fail_continue(self):
346 """ 347 Explicit continue-the-build failure. 348 349 This sets failure status on the target nodes and all of 350 their dependent parent nodes. 351 352 Note: Although this function is normally invoked on nodes in 353 the executing state, it might also be invoked on up-to-date 354 nodes when using Configure(). 355 """ 356 T = self.tm.trace 357 if T: T.write(self.trace_message('Task.failed_continue()', self.node)) 358 359 self.tm.will_not_build(self.targets, lambda n: n.set_state(NODE_FAILED))
360
361 - def make_ready_all(self):
362 """ 363 Marks all targets in a task ready for execution. 364 365 This is used when the interface needs every target Node to be 366 visited--the canonical example being the "scons -c" option. 367 """ 368 T = self.tm.trace 369 if T: T.write(self.trace_message('Task.make_ready_all()', self.node)) 370 371 self.out_of_date = self.targets[:] 372 for t in self.targets: 373 t.disambiguate().set_state(NODE_EXECUTING) 374 for s in t.side_effects: 375 # add disambiguate here to mirror the call on targets above 376 s.disambiguate().set_state(NODE_EXECUTING)
377
378 - def make_ready_current(self):
379 """ 380 Marks all targets in a task ready for execution if any target 381 is not current. 382 383 This is the default behavior for building only what's necessary. 384 """ 385 T = self.tm.trace 386 if T: T.write(self.trace_message(u'Task.make_ready_current()', 387 self.node)) 388 389 self.out_of_date = [] 390 needs_executing = False 391 for t in self.targets: 392 try: 393 t.disambiguate().make_ready() 394 is_up_to_date = not t.has_builder() or \ 395 (not t.always_build and t.is_up_to_date()) 396 except EnvironmentError, e: 397 raise SCons.Errors.BuildError(node=t, errstr=e.strerror, filename=e.filename) 398 399 if not is_up_to_date: 400 self.out_of_date.append(t) 401 needs_executing = True 402 403 if needs_executing: 404 for t in self.targets: 405 t.set_state(NODE_EXECUTING) 406 for s in t.side_effects: 407 # add disambiguate here to mirror the call on targets in first loop above 408 s.disambiguate().set_state(NODE_EXECUTING) 409 else: 410 for t in self.targets: 411 # We must invoke visited() to ensure that the node 412 # information has been computed before allowing the 413 # parent nodes to execute. (That could occur in a 414 # parallel build...) 415 t.visited() 416 t.set_state(NODE_UP_TO_DATE)
417 418 make_ready = make_ready_current 419
420 - def postprocess(self):
421 """ 422 Post-processes a task after it's been executed. 423 424 This examines all the targets just built (or not, we don't care 425 if the build was successful, or even if there was no build 426 because everything was up-to-date) to see if they have any 427 waiting parent Nodes, or Nodes waiting on a common side effect, 428 that can be put back on the candidates list. 429 """ 430 T = self.tm.trace 431 if T: T.write(self.trace_message(u'Task.postprocess()', self.node)) 432 433 # We may have built multiple targets, some of which may have 434 # common parents waiting for this build. Count up how many 435 # targets each parent was waiting for so we can subtract the 436 # values later, and so we *don't* put waiting side-effect Nodes 437 # back on the candidates list if the Node is also a waiting 438 # parent. 439 440 targets = set(self.targets) 441 442 pending_children = self.tm.pending_children 443 parents = {} 444 for t in targets: 445 # A node can only be in the pending_children set if it has 446 # some waiting_parents. 447 if t.waiting_parents: 448 if T: T.write(self.trace_message(u'Task.postprocess()', 449 t, 450 'removing')) 451 pending_children.discard(t) 452 for p in t.waiting_parents: 453 parents[p] = parents.get(p, 0) + 1 454 455 for t in targets: 456 for s in t.side_effects: 457 if s.get_state() == NODE_EXECUTING: 458 s.set_state(NODE_NO_STATE) 459 for p in s.waiting_parents: 460 parents[p] = parents.get(p, 0) + 1 461 for p in s.waiting_s_e: 462 if p.ref_count == 0: 463 self.tm.candidates.append(p) 464 465 for p, subtract in parents.items(): 466 p.ref_count = p.ref_count - subtract 467 if T: T.write(self.trace_message(u'Task.postprocess()', 468 p, 469 'adjusted parent ref count')) 470 if p.ref_count == 0: 471 self.tm.candidates.append(p) 472 473 for t in targets: 474 t.postprocess()
475 476 # Exception handling subsystem. 477 # 478 # Exceptions that occur while walking the DAG or examining Nodes 479 # must be raised, but must be raised at an appropriate time and in 480 # a controlled manner so we can, if necessary, recover gracefully, 481 # possibly write out signature information for Nodes we've updated, 482 # etc. This is done by having the Taskmaster tell us about the 483 # exception, and letting 484
485 - def exc_info(self):
486 """ 487 Returns info about a recorded exception. 488 """ 489 return self.exception
490
491 - def exc_clear(self):
492 """ 493 Clears any recorded exception. 494 495 This also changes the "exception_raise" attribute to point 496 to the appropriate do-nothing method. 497 """ 498 self.exception = (None, None, None) 499 self.exception_raise = self._no_exception_to_raise
500
501 - def exception_set(self, exception=None):
502 """ 503 Records an exception to be raised at the appropriate time. 504 505 This also changes the "exception_raise" attribute to point 506 to the method that will, in fact 507 """ 508 if not exception: 509 exception = sys.exc_info() 510 self.exception = exception 511 self.exception_raise = self._exception_raise
512
513 - def _no_exception_to_raise(self):
514 pass
515
516 - def _exception_raise(self):
517 """ 518 Raises a pending exception that was recorded while getting a 519 Task ready for execution. 520 """ 521 exc = self.exc_info()[:] 522 try: 523 exc_type, exc_value, exc_traceback = exc 524 except ValueError: 525 exc_type, exc_value = exc 526 exc_traceback = None 527 raise exc_type, exc_value, exc_traceback
528
529 -class AlwaysTask(Task):
530 - def needs_execute(self):
531 """ 532 Always returns True (indicating this Task should always 533 be executed). 534 535 Subclasses that need this behavior (as opposed to the default 536 of only executing Nodes that are out of date w.r.t. their 537 dependencies) can use this as follows: 538 539 class MyTaskSubclass(SCons.Taskmaster.Task): 540 needs_execute = SCons.Taskmaster.Task.execute_always 541 """ 542 return True
543
544 -class OutOfDateTask(Task):
545 - def needs_execute(self):
546 """ 547 Returns True (indicating this Task should be executed) if this 548 Task's target state indicates it needs executing, which has 549 already been determined by an earlier up-to-date check. 550 """ 551 return self.targets[0].get_state() == SCons.Node.executing
552 553
554 -def find_cycle(stack, visited):
555 if stack[-1] in visited: 556 return None 557 visited.add(stack[-1]) 558 for n in stack[-1].waiting_parents: 559 stack.append(n) 560 if stack[0] == stack[-1]: 561 return stack 562 if find_cycle(stack, visited): 563 return stack 564 stack.pop() 565 return None
566 567
568 -class Taskmaster(object):
569 """ 570 The Taskmaster for walking the dependency DAG. 571 """ 572
573 - def __init__(self, targets=[], tasker=None, order=None, trace=None):
574 self.original_top = targets 575 self.top_targets_left = targets[:] 576 self.top_targets_left.reverse() 577 self.candidates = [] 578 if tasker is None: 579 tasker = OutOfDateTask 580 self.tasker = tasker 581 if not order: 582 order = lambda l: l 583 self.order = order 584 self.message = None 585 self.trace = trace 586 self.next_candidate = self.find_next_candidate 587 self.pending_children = set()
588
589 - def find_next_candidate(self):
590 """ 591 Returns the next candidate Node for (potential) evaluation. 592 593 The candidate list (really a stack) initially consists of all of 594 the top-level (command line) targets provided when the Taskmaster 595 was initialized. While we walk the DAG, visiting Nodes, all the 596 children that haven't finished processing get pushed on to the 597 candidate list. Each child can then be popped and examined in 598 turn for whether *their* children are all up-to-date, in which 599 case a Task will be created for their actual evaluation and 600 potential building. 601 602 Here is where we also allow candidate Nodes to alter the list of 603 Nodes that should be examined. This is used, for example, when 604 invoking SCons in a source directory. A source directory Node can 605 return its corresponding build directory Node, essentially saying, 606 "Hey, you really need to build this thing over here instead." 607 """ 608 try: 609 return self.candidates.pop() 610 except IndexError: 611 pass 612 try: 613 node = self.top_targets_left.pop() 614 except IndexError: 615 return None 616 self.current_top = node 617 alt, message = node.alter_targets() 618 if alt: 619 self.message = message 620 self.candidates.append(node) 621 self.candidates.extend(self.order(alt)) 622 node = self.candidates.pop() 623 return node
624
625 - def no_next_candidate(self):
626 """ 627 Stops Taskmaster processing by not returning a next candidate. 628 629 Note that we have to clean-up the Taskmaster candidate list 630 because the cycle detection depends on the fact all nodes have 631 been processed somehow. 632 """ 633 while self.candidates: 634 candidates = self.candidates 635 self.candidates = [] 636 self.will_not_build(candidates) 637 return None
638
639 - def _validate_pending_children(self):
640 """ 641 Validate the content of the pending_children set. Assert if an 642 internal error is found. 643 644 This function is used strictly for debugging the taskmaster by 645 checking that no invariants are violated. It is not used in 646 normal operation. 647 648 The pending_children set is used to detect cycles in the 649 dependency graph. We call a "pending child" a child that is 650 found in the "pending" state when checking the dependencies of 651 its parent node. 652 653 A pending child can occur when the Taskmaster completes a loop 654 through a cycle. For example, lets imagine a graph made of 655 three node (A, B and C) making a cycle. The evaluation starts 656 at node A. The taskmaster first consider whether node A's 657 child B is up-to-date. Then, recursively, node B needs to 658 check whether node C is up-to-date. This leaves us with a 659 dependency graph looking like: 660 661 Next candidate \ 662 \ 663 Node A (Pending) --> Node B(Pending) --> Node C (NoState) 664 ^ | 665 | | 666 +-------------------------------------+ 667 668 Now, when the Taskmaster examines the Node C's child Node A, 669 it finds that Node A is in the "pending" state. Therefore, 670 Node A is a pending child of node C. 671 672 Pending children indicate that the Taskmaster has potentially 673 loop back through a cycle. We say potentially because it could 674 also occur when a DAG is evaluated in parallel. For example, 675 consider the following graph: 676 677 678 Node A (Pending) --> Node B(Pending) --> Node C (Pending) --> ... 679 | ^ 680 | | 681 +----------> Node D (NoState) --------+ 682 / 683 Next candidate / 684 685 The Taskmaster first evaluates the nodes A, B, and C and 686 starts building some children of node C. Assuming, that the 687 maximum parallel level has not been reached, the Taskmaster 688 will examine Node D. It will find that Node C is a pending 689 child of Node D. 690 691 In summary, evaluating a graph with a cycle will always 692 involve a pending child at one point. A pending child might 693 indicate either a cycle or a diamond-shaped DAG. Only a 694 fraction of the nodes ends-up being a "pending child" of 695 another node. This keeps the pending_children set small in 696 practice. 697 698 We can differentiate between the two cases if we wait until 699 the end of the build. At this point, all the pending children 700 nodes due to a diamond-shaped DAG will have been properly 701 built (or will have failed to build). But, the pending 702 children involved in a cycle will still be in the pending 703 state. 704 705 The taskmaster removes nodes from the pending_children set as 706 soon as a pending_children node moves out of the pending 707 state. This also helps to keep the pending_children set small. 708 """ 709 710 for n in self.pending_children: 711 assert n.state in (NODE_PENDING, NODE_EXECUTING), \ 712 (str(n), StateString[n.state]) 713 assert len(n.waiting_parents) != 0, (str(n), len(n.waiting_parents)) 714 for p in n.waiting_parents: 715 assert p.ref_count > 0, (str(n), str(p), p.ref_count)
716 717
718 - def trace_message(self, message):
719 return 'Taskmaster: %s\n' % message
720
721 - def trace_node(self, node):
722 return '<%-10s %-3s %s>' % (StateString[node.get_state()], 723 node.ref_count, 724 repr(str(node)))
725
726 - def _find_next_ready_node(self):
727 """ 728 Finds the next node that is ready to be built. 729 730 This is *the* main guts of the DAG walk. We loop through the 731 list of candidates, looking for something that has no un-built 732 children (i.e., that is a leaf Node or has dependencies that are 733 all leaf Nodes or up-to-date). Candidate Nodes are re-scanned 734 (both the target Node itself and its sources, which are always 735 scanned in the context of a given target) to discover implicit 736 dependencies. A Node that must wait for some children to be 737 built will be put back on the candidates list after the children 738 have finished building. A Node that has been put back on the 739 candidates list in this way may have itself (or its sources) 740 re-scanned, in order to handle generated header files (e.g.) and 741 the implicit dependencies therein. 742 743 Note that this method does not do any signature calculation or 744 up-to-date check itself. All of that is handled by the Task 745 class. This is purely concerned with the dependency graph walk. 746 """ 747 748 self.ready_exc = None 749 750 T = self.trace 751 if T: T.write(u'\n' + self.trace_message('Looking for a node to evaluate')) 752 753 while True: 754 node = self.next_candidate() 755 if node is None: 756 if T: T.write(self.trace_message('No candidate anymore.') + u'\n') 757 return None 758 759 node = node.disambiguate() 760 state = node.get_state() 761 762 # For debugging only: 763 # 764 # try: 765 # self._validate_pending_children() 766 # except: 767 # self.ready_exc = sys.exc_info() 768 # return node 769 770 if CollectStats: 771 if not hasattr(node, 'stats'): 772 node.stats = Stats() 773 StatsNodes.append(node) 774 S = node.stats 775 S.considered = S.considered + 1 776 else: 777 S = None 778 779 if T: T.write(self.trace_message(u' Considering node %s and its children:' % self.trace_node(node))) 780 781 if state == NODE_NO_STATE: 782 # Mark this node as being on the execution stack: 783 node.set_state(NODE_PENDING) 784 elif state > NODE_PENDING: 785 # Skip this node if it has already been evaluated: 786 if S: S.already_handled = S.already_handled + 1 787 if T: T.write(self.trace_message(u' already handled (executed)')) 788 continue 789 790 executor = node.get_executor() 791 792 try: 793 children = executor.get_all_children() 794 except SystemExit: 795 exc_value = sys.exc_info()[1] 796 e = SCons.Errors.ExplicitExit(node, exc_value.code) 797 self.ready_exc = (SCons.Errors.ExplicitExit, e) 798 if T: T.write(self.trace_message(' SystemExit')) 799 return node 800 except Exception, e: 801 # We had a problem just trying to figure out the 802 # children (like a child couldn't be linked in to a 803 # VariantDir, or a Scanner threw something). Arrange to 804 # raise the exception when the Task is "executed." 805 self.ready_exc = sys.exc_info() 806 if S: S.problem = S.problem + 1 807 if T: T.write(self.trace_message(' exception %s while scanning children.\n' % e)) 808 return node 809 810 children_not_visited = [] 811 children_pending = set() 812 children_not_ready = [] 813 children_failed = False 814 815 for child in chain(executor.get_all_prerequisites(), children): 816 childstate = child.get_state() 817 818 if T: T.write(self.trace_message(u' ' + self.trace_node(child))) 819 820 if childstate == NODE_NO_STATE: 821 children_not_visited.append(child) 822 elif childstate == NODE_PENDING: 823 children_pending.add(child) 824 elif childstate == NODE_FAILED: 825 children_failed = True 826 827 if childstate <= NODE_EXECUTING: 828 children_not_ready.append(child) 829 830 831 # These nodes have not even been visited yet. Add 832 # them to the list so that on some next pass we can 833 # take a stab at evaluating them (or their children). 834 children_not_visited.reverse() 835 self.candidates.extend(self.order(children_not_visited)) 836 #if T and children_not_visited: 837 # T.write(self.trace_message(' adding to candidates: %s' % map(str, children_not_visited))) 838 # T.write(self.trace_message(' candidates now: %s\n' % map(str, self.candidates))) 839 840 # Skip this node if any of its children have failed. 841 # 842 # This catches the case where we're descending a top-level 843 # target and one of our children failed while trying to be 844 # built by a *previous* descent of an earlier top-level 845 # target. 846 # 847 # It can also occur if a node is reused in multiple 848 # targets. One first descends though the one of the 849 # target, the next time occurs through the other target. 850 # 851 # Note that we can only have failed_children if the 852 # --keep-going flag was used, because without it the build 853 # will stop before diving in the other branch. 854 # 855 # Note that even if one of the children fails, we still 856 # added the other children to the list of candidate nodes 857 # to keep on building (--keep-going). 858 if children_failed: 859 for n in executor.get_action_targets(): 860 n.set_state(NODE_FAILED) 861 862 if S: S.child_failed = S.child_failed + 1 863 if T: T.write(self.trace_message('****** %s\n' % self.trace_node(node))) 864 continue 865 866 if children_not_ready: 867 for child in children_not_ready: 868 # We're waiting on one or more derived targets 869 # that have not yet finished building. 870 if S: S.not_built = S.not_built + 1 871 872 # Add this node to the waiting parents lists of 873 # anything we're waiting on, with a reference 874 # count so we can be put back on the list for 875 # re-evaluation when they've all finished. 876 node.ref_count = node.ref_count + child.add_to_waiting_parents(node) 877 if T: T.write(self.trace_message(u' adjusted ref count: %s, child %s' % 878 (self.trace_node(node), repr(str(child))))) 879 880 if T: 881 for pc in children_pending: 882 T.write(self.trace_message(' adding %s to the pending children set\n' % 883 self.trace_node(pc))) 884 self.pending_children = self.pending_children | children_pending 885 886 continue 887 888 # Skip this node if it has side-effects that are 889 # currently being built: 890 wait_side_effects = False 891 for se in executor.get_action_side_effects(): 892 if se.get_state() == NODE_EXECUTING: 893 se.add_to_waiting_s_e(node) 894 wait_side_effects = True 895 896 if wait_side_effects: 897 if S: S.side_effects = S.side_effects + 1 898 continue 899 900 # The default when we've gotten through all of the checks above: 901 # this node is ready to be built. 902 if S: S.build = S.build + 1 903 if T: T.write(self.trace_message(u'Evaluating %s\n' % 904 self.trace_node(node))) 905 906 # For debugging only: 907 # 908 # try: 909 # self._validate_pending_children() 910 # except: 911 # self.ready_exc = sys.exc_info() 912 # return node 913 914 return node 915 916 return None
917
918 - def next_task(self):
919 """ 920 Returns the next task to be executed. 921 922 This simply asks for the next Node to be evaluated, and then wraps 923 it in the specific Task subclass with which we were initialized. 924 """ 925 node = self._find_next_ready_node() 926 927 if node is None: 928 return None 929 930 tlist = node.get_executor().get_all_targets() 931 932 task = self.tasker(self, tlist, node in self.original_top, node) 933 try: 934 task.make_ready() 935 except: 936 # We had a problem just trying to get this task ready (like 937 # a child couldn't be linked in to a VariantDir when deciding 938 # whether this node is current). Arrange to raise the 939 # exception when the Task is "executed." 940 self.ready_exc = sys.exc_info() 941 942 if self.ready_exc: 943 task.exception_set(self.ready_exc) 944 945 self.ready_exc = None 946 947 return task
948
949 - def will_not_build(self, nodes, node_func=lambda n: None):
950 """ 951 Perform clean-up about nodes that will never be built. Invokes 952 a user defined function on all of these nodes (including all 953 of their parents). 954 """ 955 956 T = self.trace 957 958 pending_children = self.pending_children 959 960 to_visit = set(nodes) 961 pending_children = pending_children - to_visit 962 963 if T: 964 for n in nodes: 965 T.write(self.trace_message(' removing node %s from the pending children set\n' % 966 self.trace_node(n))) 967 try: 968 while len(to_visit): 969 node = to_visit.pop() 970 node_func(node) 971 972 # Prune recursion by flushing the waiting children 973 # list immediately. 974 parents = node.waiting_parents 975 node.waiting_parents = set() 976 977 to_visit = to_visit | parents 978 pending_children = pending_children - parents 979 980 for p in parents: 981 p.ref_count = p.ref_count - 1 982 if T: T.write(self.trace_message(' removing parent %s from the pending children set\n' % 983 self.trace_node(p))) 984 except KeyError: 985 # The container to_visit has been emptied. 986 pass 987 988 # We have the stick back the pending_children list into the 989 # taskmaster because the python 1.5.2 compatibility does not 990 # allow us to use in-place updates 991 self.pending_children = pending_children
992
993 - def stop(self):
994 """ 995 Stops the current build completely. 996 """ 997 self.next_candidate = self.no_next_candidate
998
999 - def cleanup(self):
1000 """ 1001 Check for dependency cycles. 1002 """ 1003 if not self.pending_children: 1004 return 1005 1006 nclist = [(n, find_cycle([n], set())) for n in self.pending_children] 1007 1008 genuine_cycles = [ 1009 node for node,cycle in nclist 1010 if cycle or node.get_state() != NODE_EXECUTED 1011 ] 1012 if not genuine_cycles: 1013 # All of the "cycles" found were single nodes in EXECUTED state, 1014 # which is to say, they really weren't cycles. Just return. 1015 return 1016 1017 desc = 'Found dependency cycle(s):\n' 1018 for node, cycle in nclist: 1019 if cycle: 1020 desc = desc + " " + " -> ".join(map(str, cycle)) + "\n" 1021 else: 1022 desc = desc + \ 1023 " Internal Error: no cycle found for node %s (%s) in state %s\n" % \ 1024 (node, repr(node), StateString[node.get_state()]) 1025 1026 raise SCons.Errors.UserError(desc)
1027 1028 # Local Variables: 1029 # tab-width:4 1030 # indent-tabs-mode:nil 1031 # End: 1032 # vim: set expandtab tabstop=4 shiftwidth=4: 1033