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