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 3603 2008/10/10 05:46:45 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
62 StateString = SCons.Node.StateString
63 NODE_NO_STATE = SCons.Node.no_state
64 NODE_PENDING = SCons.Node.pending
65 NODE_EXECUTING = SCons.Node.executing
66 NODE_UP_TO_DATE = SCons.Node.up_to_date
67 NODE_EXECUTED = SCons.Node.executed
68 NODE_FAILED = SCons.Node.failed
69
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
112
113
114
116 """
117 Default SCons build engine task.
118
119 This controls the interaction of the actual building of node
120 and the rest of the engine.
121
122 This is expected to handle all of the normally-customizable
123 aspects of controlling a build, so any given application
124 *should* be able to do what it wants by sub-classing this
125 class and overriding methods as appropriate. If an application
126 needs to customze something by sub-classing Taskmaster (or
127 some other build engine class), we should first try to migrate
128 that functionality into this class.
129
130 Note that it's generally a good idea for sub-classes to call
131 these methods explicitly to update state, etc., rather than
132 roll their own interaction with Taskmaster from scratch.
133 """
134 - def __init__(self, tm, targets, top, node):
135 self.tm = tm
136 self.targets = targets
137 self.top = top
138 self.node = node
139 self.exc_clear()
140
142 """
143 Hook to allow the calling interface to display a message.
144
145 This hook gets called as part of preparing a task for execution
146 (that is, a Node to be built). As part of figuring out what Node
147 should be built next, the actually target list may be altered,
148 along with a message describing the alteration. The calling
149 interface can subclass Task and provide a concrete implementation
150 of this method to see those messages.
151 """
152 pass
153
155 """
156 Called just before the task is executed.
157
158 This is mainly intended to give the target Nodes a chance to
159 unlink underlying files and make all necessary directories before
160 the Action is actually called to build the targets.
161 """
162
163
164
165
166 self.exception_raise()
167
168 if self.tm.message:
169 self.display(self.tm.message)
170 self.tm.message = None
171
172
173
174
175
176
177
178
179
180
181
182 self.targets[0].get_executor().prepare()
183 for t in self.targets:
184 t.prepare()
185 for s in t.side_effects:
186 s.prepare()
187
189 """Fetch the target being built or updated by this task.
190 """
191 return self.node
192
194 """
195 Called to determine whether the task's execute() method should
196 be run.
197
198 This method allows one to skip the somethat costly execution
199 of the execute() method in a seperate thread. For example,
200 that would be unnecessary for up-to-date targets.
201 """
202 return True
203
205 """
206 Called to execute the task.
207
208 This method is called from multiple threads in a parallel build,
209 so only do thread safe stuff here. Do thread unsafe stuff in
210 prepare(), executed() or failed().
211 """
212
213 try:
214 everything_was_cached = 1
215 for t in self.targets:
216 if not t.retrieve_from_cache():
217 everything_was_cached = 0
218 break
219 if not everything_was_cached:
220 self.targets[0].build()
221 except SystemExit:
222 exc_value = sys.exc_info()[1]
223 raise SCons.Errors.ExplicitExit(self.targets[0], exc_value.code)
224 except SCons.Errors.UserError:
225 raise
226 except SCons.Errors.BuildError:
227 raise
228 except:
229 raise SCons.Errors.TaskmasterException(self.targets[0],
230 sys.exc_info())
231
233 """
234 Called when the task has been successfully executed
235 and the Taskmaster instance doesn't want to call
236 the Node's callback methods.
237 """
238 for t in self.targets:
239 if t.get_state() == NODE_EXECUTING:
240 for side_effect in t.side_effects:
241 side_effect.set_state(NODE_NO_STATE)
242 t.set_state(NODE_EXECUTED)
243
245 """
246 Called when the task has been successfully executed and
247 the Taskmaster instance wants to call the Node's callback
248 methods.
249
250 This may have been a do-nothing operation (to preserve build
251 order), so we must check the node's state before deciding whether
252 it was "built", in which case we call the appropriate Node method.
253 In any event, we always call "visited()", which will handle any
254 post-visit actions that must take place regardless of whether
255 or not the target was an actual built target or a source Node.
256 """
257 for t in self.targets:
258 if t.get_state() == NODE_EXECUTING:
259 for side_effect in t.side_effects:
260 side_effect.set_state(NODE_NO_STATE)
261 t.set_state(NODE_EXECUTED)
262 t.built()
263 t.visited()
264
265 executed = executed_with_callbacks
266
268 """
269 Default action when a task fails: stop the build.
270 """
271 self.fail_stop()
272
274 """
275 Explicit stop-the-build failure.
276 """
277
278
279
280 self.tm.will_not_build(self.targets)
281
282
283 self.tm.stop()
284
285
286
287
288 self.targets = [self.tm.current_top]
289 self.top = 1
290
292 """
293 Explicit continue-the-build failure.
294
295 This sets failure status on the target nodes and all of
296 their dependent parent nodes.
297 """
298 self.tm.will_not_build(self.targets)
299
301 """
302 Marks all targets in a task ready for execution.
303
304 This is used when the interface needs every target Node to be
305 visited--the canonical example being the "scons -c" option.
306 """
307 self.out_of_date = self.targets[:]
308 for t in self.targets:
309 t.disambiguate().set_state(NODE_EXECUTING)
310 for s in t.side_effects:
311 s.set_state(NODE_EXECUTING)
312
347
348 make_ready = make_ready_current
349
350 - def postprocess(self):
351 """
352 Post-processes a task after it's been executed.
353
354 This examines all the targets just built (or not, we don't care
355 if the build was successful, or even if there was no build
356 because everything was up-to-date) to see if they have any
357 waiting parent Nodes, or Nodes waiting on a common side effect,
358 that can be put back on the candidates list.
359 """
360
361
362
363
364
365
366
367
368 targets = set(self.targets)
369
370 parents = {}
371 for t in targets:
372 for p in t.waiting_parents:
373 parents[p] = parents.get(p, 0) + 1
374
375 for t in targets:
376 for s in t.side_effects:
377 if s.get_state() == NODE_EXECUTING:
378 s.set_state(NODE_NO_STATE)
379 for p in s.waiting_parents:
380 parents[p] = parents.get(p, 0) + 1
381 for p in s.waiting_s_e:
382 if p.ref_count == 0:
383 self.tm.candidates.append(p)
384 self.tm.pending_children.discard(p)
385
386 for p, subtract in parents.items():
387 p.ref_count = p.ref_count - subtract
388 if p.ref_count == 0:
389 self.tm.candidates.append(p)
390 self.tm.pending_children.discard(p)
391
392 for t in targets:
393 t.postprocess()
394
395
396
397
398
399
400
401
402
403
405 """
406 Returns info about a recorded exception.
407 """
408 return self.exception
409
411 """
412 Clears any recorded exception.
413
414 This also changes the "exception_raise" attribute to point
415 to the appropriate do-nothing method.
416 """
417 self.exception = (None, None, None)
418 self.exception_raise = self._no_exception_to_raise
419
421 """
422 Records an exception to be raised at the appropriate time.
423
424 This also changes the "exception_raise" attribute to point
425 to the method that will, in fact
426 """
427 if not exception:
428 exception = sys.exc_info()
429 self.exception = exception
430 self.exception_raise = self._exception_raise
431
434
436 """
437 Raises a pending exception that was recorded while getting a
438 Task ready for execution.
439 """
440 exc = self.exc_info()[:]
441 try:
442 exc_type, exc_value, exc_traceback = exc
443 except ValueError:
444 exc_type, exc_value = exc
445 exc_traceback = None
446 raise exc_type, exc_value, exc_traceback
447
448
450 if stack[-1] in visited:
451 return None
452 visited.add(stack[-1])
453 for n in stack[-1].waiting_parents:
454 stack.append(n)
455 if stack[0] == stack[-1]:
456 return stack
457 if find_cycle(stack, visited):
458 return stack
459 stack.pop()
460 return None
461
462
464 """
465 The Taskmaster for walking the dependency DAG.
466 """
467
468 - def __init__(self, targets=[], tasker=Task, order=None, trace=None):
469 self.original_top = targets
470 self.top_targets_left = targets[:]
471 self.top_targets_left.reverse()
472 self.candidates = []
473 self.tasker = tasker
474 if not order:
475 order = lambda l: l
476 self.order = order
477 self.message = None
478 self.trace = trace
479 self.next_candidate = self.find_next_candidate
480 self.pending_children = set()
481
482
484 """
485 Returns the next candidate Node for (potential) evaluation.
486
487 The candidate list (really a stack) initially consists of all of
488 the top-level (command line) targets provided when the Taskmaster
489 was initialized. While we walk the DAG, visiting Nodes, all the
490 children that haven't finished processing get pushed on to the
491 candidate list. Each child can then be popped and examined in
492 turn for whether *their* children are all up-to-date, in which
493 case a Task will be created for their actual evaluation and
494 potential building.
495
496 Here is where we also allow candidate Nodes to alter the list of
497 Nodes that should be examined. This is used, for example, when
498 invoking SCons in a source directory. A source directory Node can
499 return its corresponding build directory Node, essentially saying,
500 "Hey, you really need to build this thing over here instead."
501 """
502 try:
503 return self.candidates.pop()
504 except IndexError:
505 pass
506 try:
507 node = self.top_targets_left.pop()
508 except IndexError:
509 return None
510 self.current_top = node
511 alt, message = node.alter_targets()
512 if alt:
513 self.message = message
514 self.candidates.append(node)
515 self.candidates.extend(self.order(alt))
516 node = self.candidates.pop()
517 return node
518
520 """
521 Stops Taskmaster processing by not returning a next candidate.
522
523 Note that we have to clean-up the Taskmaster candidate list
524 because the cycle detection depends on the fact all nodes have
525 been processed somehow.
526 """
527 while self.candidates:
528 candidates = self.candidates
529 self.candidates = []
530 self.will_not_build(candidates, lambda n: n.state < NODE_UP_TO_DATE)
531 return None
532
534 """
535 Finds the next node that is ready to be built.
536
537 This is *the* main guts of the DAG walk. We loop through the
538 list of candidates, looking for something that has no un-built
539 children (i.e., that is a leaf Node or has dependencies that are
540 all leaf Nodes or up-to-date). Candidate Nodes are re-scanned
541 (both the target Node itself and its sources, which are always
542 scanned in the context of a given target) to discover implicit
543 dependencies. A Node that must wait for some children to be
544 built will be put back on the candidates list after the children
545 have finished building. A Node that has been put back on the
546 candidates list in this way may have itself (or its sources)
547 re-scanned, in order to handle generated header files (e.g.) and
548 the implicit dependencies therein.
549
550 Note that this method does not do any signature calculation or
551 up-to-date check itself. All of that is handled by the Task
552 class. This is purely concerned with the dependency graph walk.
553 """
554
555 self.ready_exc = None
556
557 T = self.trace
558 if T: T.write('\nTaskmaster: Looking for a node to evaluate\n')
559
560 while 1:
561 node = self.next_candidate()
562 if node is None:
563 if T: T.write('Taskmaster: No candidate anymore.\n\n')
564 return None
565
566 node = node.disambiguate()
567 state = node.get_state()
568
569 if CollectStats:
570 if not hasattr(node, 'stats'):
571 node.stats = Stats()
572 StatsNodes.append(node)
573 S = node.stats
574 S.considered = S.considered + 1
575 else:
576 S = None
577
578 if T: T.write('Taskmaster: Considering node <%-10s %-3s %s> and its children:\n' %
579 (StateString[node.get_state()], node.ref_count, repr(str(node))))
580
581 if state == NODE_NO_STATE:
582
583 node.set_state(NODE_PENDING)
584 elif state > NODE_PENDING:
585
586 if S: S.already_handled = S.already_handled + 1
587 if T: T.write('Taskmaster: already handled (executed)\n')
588 continue
589
590 try:
591 children = node.children()
592 except SystemExit:
593 exc_value = sys.exc_info()[1]
594 e = SCons.Errors.ExplicitExit(node, exc_value.code)
595 self.ready_exc = (SCons.Errors.ExplicitExit, e)
596 if T: T.write('Taskmaster: SystemExit\n')
597 return node
598 except Exception, e:
599
600
601
602
603 self.ready_exc = sys.exc_info()
604 if S: S.problem = S.problem + 1
605 if T: T.write('Taskmaster: exception %s while scanning children.\n'%s)
606 return node
607
608 children_not_visited = []
609 children_pending = set()
610 children_not_ready = []
611 children_failed = False
612
613 for child in chain(children,node.prerequisites):
614 childstate = child.get_state()
615
616 if T: T.write('Taskmaster: <%-10s %-3s %s>\n' %
617 (StateString[childstate], child.ref_count, repr(str(child))))
618
619 if childstate == NODE_NO_STATE:
620 children_not_visited.append(child)
621 elif childstate == NODE_PENDING:
622 children_pending.add(child)
623 elif childstate == NODE_FAILED:
624 children_failed = True
625
626 if childstate <= NODE_EXECUTING:
627 children_not_ready.append(child)
628
629
630
631
632
633 children_not_visited.reverse()
634 self.candidates.extend(self.order(children_not_visited))
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657 if children_failed:
658 node.set_state(NODE_FAILED)
659
660 if S: S.child_failed = S.child_failed + 1
661 if T: T.write('Taskmaster:****** <%-10s %-3s %s>\n' %
662 (StateString[node.get_state()], node.ref_count, repr(str(node))))
663 continue
664
665 if children_not_ready:
666 for child in children_not_ready:
667
668
669 if S: S.not_built = S.not_built + 1
670
671
672
673
674
675 node.ref_count = node.ref_count + child.add_to_waiting_parents(node)
676 if T: T.write('Taskmaster: adjusting ref count: <%-10s %-3s %s>\n' %
677 (StateString[node.get_state()], node.ref_count, repr(str(node))))
678
679 self.pending_children = self.pending_children | children_pending
680
681 continue
682
683
684
685 wait_side_effects = False
686 for se in node.side_effects:
687 if se.get_state() == NODE_EXECUTING:
688 se.add_to_waiting_s_e(node)
689 wait_side_effects = True
690
691 if wait_side_effects:
692 if S: S.side_effects = S.side_effects + 1
693 continue
694
695
696
697 if S: S.build = S.build + 1
698 if T: T.write('Taskmaster: Evaluating <%-10s %-3s %s>\n' %
699 (StateString[node.get_state()], node.ref_count, repr(str(node))))
700 return node
701
702 return None
703
705 """
706 Returns the next task to be executed.
707
708 This simply asks for the next Node to be evaluated, and then wraps
709 it in the specific Task subclass with which we were initialized.
710 """
711 node = self._find_next_ready_node()
712
713 if node is None:
714 return None
715
716 tlist = node.get_executor().targets
717
718 task = self.tasker(self, tlist, node in self.original_top, node)
719 try:
720 task.make_ready()
721 except:
722
723
724
725
726 self.ready_exc = sys.exc_info()
727
728 if self.ready_exc:
729 task.exception_set(self.ready_exc)
730
731 self.ready_exc = None
732
733 return task
734
736 """
737 Perform clean-up about nodes that will never be built.
738 """
739
740 pending_children = self.pending_children
741
742 to_visit = set()
743 for node in nodes:
744
745
746 if mark_fail(node):
747 node.set_state(NODE_FAILED)
748 parents = node.waiting_parents
749 to_visit = to_visit | parents
750 pending_children = pending_children - parents
751
752 try:
753 while 1:
754 try:
755 node = to_visit.pop()
756 except AttributeError:
757
758 if len(to_visit):
759 node = to_visit[0]
760 to_visit.remove(node)
761 else:
762 break
763 if mark_fail(node):
764 node.set_state(NODE_FAILED)
765 parents = node.waiting_parents
766 to_visit = to_visit | parents
767 pending_children = pending_children - parents
768 except KeyError:
769
770 pass
771
772
773
774
775 self.pending_children = pending_children
776
778 """
779 Stops the current build completely.
780 """
781 self.next_candidate = self.no_next_candidate
782
784 """
785 Check for dependency cycles.
786 """
787 if self.pending_children:
788 desc = 'Found dependency cycle(s):\n'
789 for node in self.pending_children:
790 cycle = find_cycle([node], set())
791 if cycle:
792 desc = desc + " " + string.join(map(str, cycle), " -> ") + "\n"
793 else:
794 desc = desc + \
795 " Internal Error: no cycle found for node %s (%s) in state %s\n" % \
796 (node, repr(node), StateString[node.get_state()])
797
798 raise SCons.Errors.UserError, desc
799