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 2928 2008/04/29 22:44:09 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)
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 if children_failed:
657 node.set_state(NODE_FAILED)
658
659 if S: S.child_failed = S.child_failed + 1
660 if T: T.write('Taskmaster:****** <%-10s %-3s %s>\n' %
661 (StateString[node.get_state()], node.ref_count, repr(str(node))))
662 continue
663
664 if children_not_ready:
665 for child in children_not_ready:
666
667
668 if S: S.not_built = S.not_built + 1
669
670
671
672
673
674 node.ref_count = node.ref_count + child.add_to_waiting_parents(node)
675 if T: T.write('Taskmaster: adjusting ref count: <%-10s %-3s %s>\n' %
676 (StateString[node.get_state()], node.ref_count, repr(str(node))))
677
678 self.pending_children = self.pending_children | children_pending
679
680 continue
681
682
683
684 wait_side_effects = False
685 for se in node.side_effects:
686 if se.get_state() == NODE_EXECUTING:
687 se.add_to_waiting_s_e(node)
688 wait_side_effects = True
689
690 if wait_side_effects:
691 if S: S.side_effects = S.side_effects + 1
692 continue
693
694
695
696 if S: S.build = S.build + 1
697 if T: T.write('Taskmaster: Evaluating <%-10s %-3s %s>\n' %
698 (StateString[node.get_state()], node.ref_count, repr(str(node))))
699 return node
700
701 return None
702
704 """
705 Returns the next task to be executed.
706
707 This simply asks for the next Node to be evaluated, and then wraps
708 it in the specific Task subclass with which we were initialized.
709 """
710 node = self._find_next_ready_node()
711
712 if node is None:
713 return None
714
715 tlist = node.get_executor().targets
716
717 task = self.tasker(self, tlist, node in self.original_top, node)
718 try:
719 task.make_ready()
720 except:
721
722
723
724
725 self.ready_exc = sys.exc_info()
726
727 if self.ready_exc:
728 task.exception_set(self.ready_exc)
729
730 self.ready_exc = None
731
732 return task
733
735 """
736 Perform clean-up about nodes that will never be built.
737 """
738
739 pending_children = self.pending_children
740
741 to_visit = set()
742 for node in nodes:
743
744
745 if node.state != NODE_FAILED:
746 node.state = NODE_FAILED
747 parents = node.waiting_parents
748 to_visit = to_visit | parents
749 pending_children = pending_children - parents
750
751 try:
752 while 1:
753 try:
754 node = to_visit.pop()
755 except AttributeError:
756
757 if len(to_visit):
758 node = to_visit[0]
759 to_visit.remove(node)
760 else:
761 break
762 if node.state != NODE_FAILED:
763 node.state = NODE_FAILED
764 parents = node.waiting_parents
765 to_visit = to_visit | parents
766 pending_children = pending_children - parents
767 except KeyError:
768
769 pass
770
771
772
773
774 self.pending_children = pending_children
775
777 """
778 Stops the current build completely.
779 """
780 self.next_candidate = self.no_next_candidate
781
783 """
784 Check for dependency cycles.
785 """
786 if self.pending_children:
787 desc = 'Found dependency cycle(s):\n'
788 for node in self.pending_children:
789 cycle = find_cycle([node], set())
790 if cycle:
791 desc = desc + " " + string.join(map(str, cycle), " -> ") + "\n"
792 else:
793 desc = desc + \
794 " Internal Error: no cycle found for node %s (%s) in state %s\n" % \
795 (node, repr(node), StateString[node.get_state()])
796
797 raise SCons.Errors.UserError, desc
798