1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 rel_2.4.0:3365:9259ea1c13d7 2015/09/21 14:03:43 bdbaddog"
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
70
71
72
73
74
75 CollectStats = None
76
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 """
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
109 for n in sorted(StatsNodes, key=lambda a: str(a)):
110 print (fmt % n.stats.__dict__) + str(n)
111
112
113
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):
139
141 fmt = '%-20s %s %s\n'
142 return fmt % (method + ':', description, self.tm.trace_node(node))
143
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
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
170
171
172 self.exception_raise()
173
174 if self.tm.message:
175 self.display(self.tm.message)
176 self.tm.message = None
177
178
179
180
181
182
183
184
185
186
187
188 executor = self.targets[0].get_executor()
189 if executor is None:
190 return
191 executor.prepare()
192 for t in executor.get_action_targets():
193 if print_prepare:
194 print "Preparing target %s..."%t
195 for s in t.side_effects:
196 print "...with side-effect %s..."%s
197 t.prepare()
198 for s in t.side_effects:
199 if print_prepare:
200 print "...Preparing side-effect %s..."%s
201 s.prepare()
202
204 """Fetch the target being built or updated by this task.
205 """
206 return self.node
207
219
221 """
222 Called to execute the task.
223
224 This method is called from multiple threads in a parallel build,
225 so only do thread safe stuff here. Do thread unsafe stuff in
226 prepare(), executed() or failed().
227 """
228 T = self.tm.trace
229 if T: T.write(self.trace_message(u'Task.execute()', self.node))
230
231 try:
232 cached_targets = []
233 for t in self.targets:
234 if not t.retrieve_from_cache():
235 break
236 cached_targets.append(t)
237 if len(cached_targets) < len(self.targets):
238
239
240
241
242
243 for t in cached_targets:
244 try:
245 t.fs.unlink(t.get_internal_path())
246 except (IOError, OSError):
247 pass
248 self.targets[0].build()
249 else:
250 for t in cached_targets:
251 t.cached = 1
252 except SystemExit:
253 exc_value = sys.exc_info()[1]
254 raise SCons.Errors.ExplicitExit(self.targets[0], exc_value.code)
255 except SCons.Errors.UserError:
256 raise
257 except SCons.Errors.BuildError:
258 raise
259 except Exception, e:
260 buildError = SCons.Errors.convert_to_BuildError(e)
261 buildError.node = self.targets[0]
262 buildError.exc_info = sys.exc_info()
263 raise buildError
264
280
282 """
283 Called when the task has been successfully executed and
284 the Taskmaster instance wants to call the Node's callback
285 methods.
286
287 This may have been a do-nothing operation (to preserve build
288 order), so we must check the node's state before deciding whether
289 it was "built", in which case we call the appropriate Node method.
290 In any event, we always call "visited()", which will handle any
291 post-visit actions that must take place regardless of whether
292 or not the target was an actual built target or a source Node.
293 """
294 global print_prepare
295 T = self.tm.trace
296 if T: T.write(self.trace_message('Task.executed_with_callbacks()',
297 self.node))
298
299 for t in self.targets:
300 if t.get_state() == NODE_EXECUTING:
301 for side_effect in t.side_effects:
302 side_effect.set_state(NODE_NO_STATE)
303 t.set_state(NODE_EXECUTED)
304 if not t.cached:
305 t.push_to_cache()
306 t.built()
307 t.visited()
308 if (not print_prepare and
309 (not hasattr(self, 'options') or not self.options.debug_includes)):
310 t.release_target_info()
311 else:
312 t.visited()
313
314 executed = executed_with_callbacks
315
317 """
318 Default action when a task fails: stop the build.
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 self.fail_stop()
325
327 """
328 Explicit stop-the-build failure.
329
330 This sets failure status on the target nodes and all of
331 their dependent parent nodes.
332
333 Note: Although this function is normally invoked on nodes in
334 the executing state, it might also be invoked on up-to-date
335 nodes when using Configure().
336 """
337 T = self.tm.trace
338 if T: T.write(self.trace_message('Task.failed_stop()', self.node))
339
340
341
342 self.tm.will_not_build(self.targets, lambda n: n.set_state(NODE_FAILED))
343
344
345 self.tm.stop()
346
347
348
349
350 self.targets = [self.tm.current_top]
351 self.top = 1
352
354 """
355 Explicit continue-the-build failure.
356
357 This sets failure status on the target nodes and all of
358 their dependent parent nodes.
359
360 Note: Although this function is normally invoked on nodes in
361 the executing state, it might also be invoked on up-to-date
362 nodes when using Configure().
363 """
364 T = self.tm.trace
365 if T: T.write(self.trace_message('Task.failed_continue()', self.node))
366
367 self.tm.will_not_build(self.targets, lambda n: n.set_state(NODE_FAILED))
368
385
429
430 make_ready = make_ready_current
431
432 - def postprocess(self):
433 """
434 Post-processes a task after it's been executed.
435
436 This examines all the targets just built (or not, we don't care
437 if the build was successful, or even if there was no build
438 because everything was up-to-date) to see if they have any
439 waiting parent Nodes, or Nodes waiting on a common side effect,
440 that can be put back on the candidates list.
441 """
442 T = self.tm.trace
443 if T: T.write(self.trace_message(u'Task.postprocess()', self.node))
444
445
446
447
448
449
450
451
452 targets = set(self.targets)
453
454 pending_children = self.tm.pending_children
455 parents = {}
456 for t in targets:
457
458
459 if t.waiting_parents:
460 if T: T.write(self.trace_message(u'Task.postprocess()',
461 t,
462 'removing'))
463 pending_children.discard(t)
464 for p in t.waiting_parents:
465 parents[p] = parents.get(p, 0) + 1
466
467 for t in targets:
468 if t.side_effects is not None:
469 for s in t.side_effects:
470 if s.get_state() == NODE_EXECUTING:
471 s.set_state(NODE_NO_STATE)
472 for p in s.waiting_parents:
473 parents[p] = parents.get(p, 0) + 1
474 for p in s.waiting_s_e:
475 if p.ref_count == 0:
476 self.tm.candidates.append(p)
477
478 for p, subtract in parents.items():
479 p.ref_count = p.ref_count - subtract
480 if T: T.write(self.trace_message(u'Task.postprocess()',
481 p,
482 'adjusted parent ref count'))
483 if p.ref_count == 0:
484 self.tm.candidates.append(p)
485
486 for t in targets:
487 t.postprocess()
488
489
490
491
492
493
494
495
496
497
499 """
500 Returns info about a recorded exception.
501 """
502 return self.exception
503
505 """
506 Clears any recorded exception.
507
508 This also changes the "exception_raise" attribute to point
509 to the appropriate do-nothing method.
510 """
511 self.exception = (None, None, None)
512 self.exception_raise = self._no_exception_to_raise
513
515 """
516 Records an exception to be raised at the appropriate time.
517
518 This also changes the "exception_raise" attribute to point
519 to the method that will, in fact
520 """
521 if not exception:
522 exception = sys.exc_info()
523 self.exception = exception
524 self.exception_raise = self._exception_raise
525
528
530 """
531 Raises a pending exception that was recorded while getting a
532 Task ready for execution.
533 """
534 exc = self.exc_info()[:]
535 try:
536 exc_type, exc_value, exc_traceback = exc
537 except ValueError:
538 exc_type, exc_value = exc
539 exc_traceback = None
540 raise exc_type, exc_value, exc_traceback
541
544 """
545 Always returns True (indicating this Task should always
546 be executed).
547
548 Subclasses that need this behavior (as opposed to the default
549 of only executing Nodes that are out of date w.r.t. their
550 dependencies) can use this as follows:
551
552 class MyTaskSubclass(SCons.Taskmaster.Task):
553 needs_execute = SCons.Taskmaster.Task.execute_always
554 """
555 return True
556
559 """
560 Returns True (indicating this Task should be executed) if this
561 Task's target state indicates it needs executing, which has
562 already been determined by an earlier up-to-date check.
563 """
564 return self.targets[0].get_state() == SCons.Node.executing
565
566
568 if stack[-1] in visited:
569 return None
570 visited.add(stack[-1])
571 for n in stack[-1].waiting_parents:
572 stack.append(n)
573 if stack[0] == stack[-1]:
574 return stack
575 if find_cycle(stack, visited):
576 return stack
577 stack.pop()
578 return None
579
580
582 """
583 The Taskmaster for walking the dependency DAG.
584 """
585
586 - def __init__(self, targets=[], tasker=None, order=None, trace=None):
587 self.original_top = targets
588 self.top_targets_left = targets[:]
589 self.top_targets_left.reverse()
590 self.candidates = []
591 if tasker is None:
592 tasker = OutOfDateTask
593 self.tasker = tasker
594 if not order:
595 order = lambda l: l
596 self.order = order
597 self.message = None
598 self.trace = trace
599 self.next_candidate = self.find_next_candidate
600 self.pending_children = set()
601
603 """
604 Returns the next candidate Node for (potential) evaluation.
605
606 The candidate list (really a stack) initially consists of all of
607 the top-level (command line) targets provided when the Taskmaster
608 was initialized. While we walk the DAG, visiting Nodes, all the
609 children that haven't finished processing get pushed on to the
610 candidate list. Each child can then be popped and examined in
611 turn for whether *their* children are all up-to-date, in which
612 case a Task will be created for their actual evaluation and
613 potential building.
614
615 Here is where we also allow candidate Nodes to alter the list of
616 Nodes that should be examined. This is used, for example, when
617 invoking SCons in a source directory. A source directory Node can
618 return its corresponding build directory Node, essentially saying,
619 "Hey, you really need to build this thing over here instead."
620 """
621 try:
622 return self.candidates.pop()
623 except IndexError:
624 pass
625 try:
626 node = self.top_targets_left.pop()
627 except IndexError:
628 return None
629 self.current_top = node
630 alt, message = node.alter_targets()
631 if alt:
632 self.message = message
633 self.candidates.append(node)
634 self.candidates.extend(self.order(alt))
635 node = self.candidates.pop()
636 return node
637
639 """
640 Stops Taskmaster processing by not returning a next candidate.
641
642 Note that we have to clean-up the Taskmaster candidate list
643 because the cycle detection depends on the fact all nodes have
644 been processed somehow.
645 """
646 while self.candidates:
647 candidates = self.candidates
648 self.candidates = []
649 self.will_not_build(candidates)
650 return None
651
653 """
654 Validate the content of the pending_children set. Assert if an
655 internal error is found.
656
657 This function is used strictly for debugging the taskmaster by
658 checking that no invariants are violated. It is not used in
659 normal operation.
660
661 The pending_children set is used to detect cycles in the
662 dependency graph. We call a "pending child" a child that is
663 found in the "pending" state when checking the dependencies of
664 its parent node.
665
666 A pending child can occur when the Taskmaster completes a loop
667 through a cycle. For example, lets imagine a graph made of
668 three node (A, B and C) making a cycle. The evaluation starts
669 at node A. The taskmaster first consider whether node A's
670 child B is up-to-date. Then, recursively, node B needs to
671 check whether node C is up-to-date. This leaves us with a
672 dependency graph looking like:
673
674 Next candidate \
675 \
676 Node A (Pending) --> Node B(Pending) --> Node C (NoState)
677 ^ |
678 | |
679 +-------------------------------------+
680
681 Now, when the Taskmaster examines the Node C's child Node A,
682 it finds that Node A is in the "pending" state. Therefore,
683 Node A is a pending child of node C.
684
685 Pending children indicate that the Taskmaster has potentially
686 loop back through a cycle. We say potentially because it could
687 also occur when a DAG is evaluated in parallel. For example,
688 consider the following graph:
689
690
691 Node A (Pending) --> Node B(Pending) --> Node C (Pending) --> ...
692 | ^
693 | |
694 +----------> Node D (NoState) --------+
695 /
696 Next candidate /
697
698 The Taskmaster first evaluates the nodes A, B, and C and
699 starts building some children of node C. Assuming, that the
700 maximum parallel level has not been reached, the Taskmaster
701 will examine Node D. It will find that Node C is a pending
702 child of Node D.
703
704 In summary, evaluating a graph with a cycle will always
705 involve a pending child at one point. A pending child might
706 indicate either a cycle or a diamond-shaped DAG. Only a
707 fraction of the nodes ends-up being a "pending child" of
708 another node. This keeps the pending_children set small in
709 practice.
710
711 We can differentiate between the two cases if we wait until
712 the end of the build. At this point, all the pending children
713 nodes due to a diamond-shaped DAG will have been properly
714 built (or will have failed to build). But, the pending
715 children involved in a cycle will still be in the pending
716 state.
717
718 The taskmaster removes nodes from the pending_children set as
719 soon as a pending_children node moves out of the pending
720 state. This also helps to keep the pending_children set small.
721 """
722
723 for n in self.pending_children:
724 assert n.state in (NODE_PENDING, NODE_EXECUTING), \
725 (str(n), StateString[n.state])
726 assert len(n.waiting_parents) != 0, (str(n), len(n.waiting_parents))
727 for p in n.waiting_parents:
728 assert p.ref_count > 0, (str(n), str(p), p.ref_count)
729
730
732 return 'Taskmaster: %s\n' % message
733
738
740 """
741 Finds the next node that is ready to be built.
742
743 This is *the* main guts of the DAG walk. We loop through the
744 list of candidates, looking for something that has no un-built
745 children (i.e., that is a leaf Node or has dependencies that are
746 all leaf Nodes or up-to-date). Candidate Nodes are re-scanned
747 (both the target Node itself and its sources, which are always
748 scanned in the context of a given target) to discover implicit
749 dependencies. A Node that must wait for some children to be
750 built will be put back on the candidates list after the children
751 have finished building. A Node that has been put back on the
752 candidates list in this way may have itself (or its sources)
753 re-scanned, in order to handle generated header files (e.g.) and
754 the implicit dependencies therein.
755
756 Note that this method does not do any signature calculation or
757 up-to-date check itself. All of that is handled by the Task
758 class. This is purely concerned with the dependency graph walk.
759 """
760
761 self.ready_exc = None
762
763 T = self.trace
764 if T: T.write(u'\n' + self.trace_message('Looking for a node to evaluate'))
765
766 while True:
767 node = self.next_candidate()
768 if node is None:
769 if T: T.write(self.trace_message('No candidate anymore.') + u'\n')
770 return None
771
772 node = node.disambiguate()
773 state = node.get_state()
774
775
776
777
778
779
780
781
782
783 if CollectStats:
784 if not hasattr(node, 'stats'):
785 node.stats = Stats()
786 StatsNodes.append(node)
787 S = node.stats
788 S.considered = S.considered + 1
789 else:
790 S = None
791
792 if T: T.write(self.trace_message(u' Considering node %s and its children:' % self.trace_node(node)))
793
794 if state == NODE_NO_STATE:
795
796 node.set_state(NODE_PENDING)
797 elif state > NODE_PENDING:
798
799 if S: S.already_handled = S.already_handled + 1
800 if T: T.write(self.trace_message(u' already handled (executed)'))
801 continue
802
803 executor = node.get_executor()
804
805 try:
806 children = executor.get_all_children()
807 except SystemExit:
808 exc_value = sys.exc_info()[1]
809 e = SCons.Errors.ExplicitExit(node, exc_value.code)
810 self.ready_exc = (SCons.Errors.ExplicitExit, e)
811 if T: T.write(self.trace_message(' SystemExit'))
812 return node
813 except Exception, e:
814
815
816
817
818 self.ready_exc = sys.exc_info()
819 if S: S.problem = S.problem + 1
820 if T: T.write(self.trace_message(' exception %s while scanning children.\n' % e))
821 return node
822
823 children_not_visited = []
824 children_pending = set()
825 children_not_ready = []
826 children_failed = False
827
828 for child in chain(executor.get_all_prerequisites(), children):
829 childstate = child.get_state()
830
831 if T: T.write(self.trace_message(u' ' + self.trace_node(child)))
832
833 if childstate == NODE_NO_STATE:
834 children_not_visited.append(child)
835 elif childstate == NODE_PENDING:
836 children_pending.add(child)
837 elif childstate == NODE_FAILED:
838 children_failed = True
839
840 if childstate <= NODE_EXECUTING:
841 children_not_ready.append(child)
842
843
844
845
846
847 children_not_visited.reverse()
848 self.candidates.extend(self.order(children_not_visited))
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871 if children_failed:
872 for n in executor.get_action_targets():
873 n.set_state(NODE_FAILED)
874
875 if S: S.child_failed = S.child_failed + 1
876 if T: T.write(self.trace_message('****** %s\n' % self.trace_node(node)))
877 continue
878
879 if children_not_ready:
880 for child in children_not_ready:
881
882
883 if S: S.not_built = S.not_built + 1
884
885
886
887
888
889 node.ref_count = node.ref_count + child.add_to_waiting_parents(node)
890 if T: T.write(self.trace_message(u' adjusted ref count: %s, child %s' %
891 (self.trace_node(node), repr(str(child)))))
892
893 if T:
894 for pc in children_pending:
895 T.write(self.trace_message(' adding %s to the pending children set\n' %
896 self.trace_node(pc)))
897 self.pending_children = self.pending_children | children_pending
898
899 continue
900
901
902
903 wait_side_effects = False
904 for se in executor.get_action_side_effects():
905 if se.get_state() == NODE_EXECUTING:
906 se.add_to_waiting_s_e(node)
907 wait_side_effects = True
908
909 if wait_side_effects:
910 if S: S.side_effects = S.side_effects + 1
911 continue
912
913
914
915 if S: S.build = S.build + 1
916 if T: T.write(self.trace_message(u'Evaluating %s\n' %
917 self.trace_node(node)))
918
919
920
921
922
923
924
925
926
927 return node
928
929 return None
930
932 """
933 Returns the next task to be executed.
934
935 This simply asks for the next Node to be evaluated, and then wraps
936 it in the specific Task subclass with which we were initialized.
937 """
938 node = self._find_next_ready_node()
939
940 if node is None:
941 return None
942
943 executor = node.get_executor()
944 if executor is None:
945 return None
946
947 tlist = executor.get_all_targets()
948
949 task = self.tasker(self, tlist, node in self.original_top, node)
950 try:
951 task.make_ready()
952 except:
953
954
955
956
957 self.ready_exc = sys.exc_info()
958
959 if self.ready_exc:
960 task.exception_set(self.ready_exc)
961
962 self.ready_exc = None
963
964 return task
965
967 """
968 Perform clean-up about nodes that will never be built. Invokes
969 a user defined function on all of these nodes (including all
970 of their parents).
971 """
972
973 T = self.trace
974
975 pending_children = self.pending_children
976
977 to_visit = set(nodes)
978 pending_children = pending_children - to_visit
979
980 if T:
981 for n in nodes:
982 T.write(self.trace_message(' removing node %s from the pending children set\n' %
983 self.trace_node(n)))
984 try:
985 while len(to_visit):
986 node = to_visit.pop()
987 node_func(node)
988
989
990
991 parents = node.waiting_parents
992 node.waiting_parents = set()
993
994 to_visit = to_visit | parents
995 pending_children = pending_children - parents
996
997 for p in parents:
998 p.ref_count = p.ref_count - 1
999 if T: T.write(self.trace_message(' removing parent %s from the pending children set\n' %
1000 self.trace_node(p)))
1001 except KeyError:
1002
1003 pass
1004
1005
1006
1007
1008 self.pending_children = pending_children
1009
1011 """
1012 Stops the current build completely.
1013 """
1014 self.next_candidate = self.no_next_candidate
1015
1017 """
1018 Check for dependency cycles.
1019 """
1020 if not self.pending_children:
1021 return
1022
1023 nclist = [(n, find_cycle([n], set())) for n in self.pending_children]
1024
1025 genuine_cycles = [
1026 node for node,cycle in nclist
1027 if cycle or node.get_state() != NODE_EXECUTED
1028 ]
1029 if not genuine_cycles:
1030
1031
1032 return
1033
1034 desc = 'Found dependency cycle(s):\n'
1035 for node, cycle in nclist:
1036 if cycle:
1037 desc = desc + " " + " -> ".join(map(str, cycle)) + "\n"
1038 else:
1039 desc = desc + \
1040 " Internal Error: no cycle found for node %s (%s) in state %s\n" % \
1041 (node, repr(node), StateString[node.get_state()])
1042
1043 raise SCons.Errors.UserError(desc)
1044
1045
1046
1047
1048
1049
1050