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