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