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