diff options
Diffstat (limited to 'src/engine/SCons/Taskmaster.py')
-rw-r--r-- | src/engine/SCons/Taskmaster.py | 242 |
1 files changed, 136 insertions, 106 deletions
diff --git a/src/engine/SCons/Taskmaster.py b/src/engine/SCons/Taskmaster.py index ecd6b07..7cdecf3 100644 --- a/src/engine/SCons/Taskmaster.py +++ b/src/engine/SCons/Taskmaster.py @@ -1,9 +1,3 @@ -"""SCons.Taskmaster - -Generic Taskmaster. - -""" - # # __COPYRIGHT__ # @@ -27,6 +21,32 @@ Generic Taskmaster. # WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. # +__doc__ = """ +Generic Taskmaster module for the SCons build engine. + +This module contains the primary interface(s) between a wrapping user +interface and the SCons build engine. There are two key classes here: + + Taskmaster + This is the main engine for walking the dependency graph and + calling things to decide what does or doesn't need to be built. + + Task + This is the base class for allowing a wrapping interface to + decide what does or doesn't actually need to be done. The + intention is for a wrapping interface to subclass this as + appropriate for different types of behavior it may need. + + The canonical example is the SCons native Python interface, + which has Task subclasses that handle its specific behavior, + like printing "`foo' is up to date" when a top-level target + doesn't need to be built, and handling the -c option by removing + targets as its "build" action. + + The Taskmaster instantiates a Task object for each (set of) + target(s) that it decides need to be evaluated and/or built. +""" + __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__" import string @@ -36,6 +56,8 @@ import traceback import SCons.Node import SCons.Errors +StateString = SCons.Node.StateString + # A subsystem for recording stats about how different Nodes are handled by # the main Taskmaster loop. There's no external control here (no need for # a --debug= option); enable it by changing the value of CollectStats. @@ -43,12 +65,22 @@ import SCons.Errors CollectStats = None class Stats: + """ + A simple class for holding statistics about the disposition of a + Node by the Taskmaster. If we're collecting statistics, each Node + processed by the Taskmaster gets one of these attached, in which + the Taskmaster records its decision each time it processes the Node. + (Ideally, that's just once per Node.) + """ def __init__(self): + """ + Instantiates a Taskmaster.Stats object, initializing all + appropriate counters to zero. + """ self.considered = 0 self.already_handled = 0 self.problem = 0 self.child_failed = 0 - self.not_started = 0 self.not_built = 0 self.side_effects = 0 self.build = 0 @@ -59,7 +91,6 @@ fmt = "%(considered)3d "\ "%(already_handled)3d " \ "%(problem)3d " \ "%(child_failed)3d " \ - "%(not_started)3d " \ "%(not_built)3d " \ "%(side_effects)3d " \ "%(build)3d " @@ -118,6 +149,11 @@ class Task: for s in t.side_effects: s.prepare() + def get_target(self): + """Fetch the target being built or updated by this task. + """ + return self.node + def execute(self): """Called to execute the task. @@ -146,11 +182,6 @@ class Task: raise SCons.Errors.TaskmasterException(self.targets[0], sys.exc_info()) - def get_target(self): - """Fetch the target being built or updated by this task. - """ - return self.node - def executed(self): """Called when the task has been successfully executed. @@ -161,8 +192,6 @@ class Task: back on the pending list.""" for t in self.targets: if t.get_state() == SCons.Node.executing: - for side_effect in t.side_effects: - side_effect.set_state(SCons.Node.no_state) t.set_state(SCons.Node.executed) t.built() else: @@ -179,15 +208,13 @@ class Task: for t in self.targets: t.set_state(SCons.Node.failed) self.tm.failed(self.node) - next_top = self.tm.next_top_level_candidate() self.tm.stop() - if next_top: - # We're stopping because of a build failure, but give the - # calling Task class a chance to postprocess() the top-level - # target under which the build failure occurred. - self.targets = [next_top] - self.top = 1 + # We're stopping because of a build failure, but give the + # calling Task class a chance to postprocess() the top-level + # target under which the build failure occurred. + self.targets = [self.tm.current_top] + self.top = 1 def fail_continue(self): """Explicit continue-the-build failure. @@ -211,9 +238,9 @@ class Task: """ self.out_of_date = self.targets[:] for t in self.targets: + t.disambiguate().set_state(SCons.Node.executing) for s in t.side_effects: - s.set_state(SCons.Node.executing) - t.set_state(SCons.Node.executing) + s.set_state(SCons.Node.pending) def make_ready_current(self): """Mark all targets in a task ready for execution if any target @@ -227,14 +254,32 @@ class Task: t.set_state(SCons.Node.up_to_date) else: self.out_of_date.append(t) - for s in t.side_effects: - s.set_state(SCons.Node.executing) t.set_state(SCons.Node.executing) + for s in t.side_effects: + s.set_state(SCons.Node.pending) make_ready = make_ready_current def postprocess(self): """Post process a task after it's been executed.""" + parents = {} + for t in self.targets: + for p in t.waiting_parents.keys(): + parents[p] = parents.get(p, 0) + 1 + for t in self.targets: + for s in t.side_effects: + if s.get_state() == SCons.Node.pending: + s.set_state(SCons.Node.no_state) + for p in s.waiting_parents.keys(): + if not parents.has_key(p): + parents[p] = 1 + for p in s.waiting_s_e.keys(): + if p.ref_count == 0: + self.tm.candidates.append(p) + for p, subtract in parents.items(): + p.ref_count = p.ref_count - subtract + if p.ref_count == 0: + self.tm.candidates.append(p) for t in self.targets: t.postprocess() @@ -265,6 +310,17 @@ def order(dependencies): return dependencies +def find_cycle(stack): + if stack[0] == stack[-1]: + return stack + for n in stack[-1].waiting_parents.keys(): + stack.append(n) + if find_cycle(stack): + return stack + stack.pop() + return None + + class Taskmaster: """A generic Taskmaster for handling a bunch of targets. @@ -273,25 +329,36 @@ class Taskmaster: """ def __init__(self, targets=[], tasker=Task, order=order, trace=None): - self.targets = targets # top level targets - self.candidates = targets[:] # nodes that might be ready to be executed - self.candidates.reverse() - self.executing = [] # nodes that are currently executing - self.pending = [] # nodes that depend on a currently executing node + self.top_targets = targets[:] + self.top_targets.reverse() + self.candidates = [] self.tasker = tasker self.ready = None # the next task that is ready to be executed self.order = order self.message = None self.trace = trace + self.next_candidate = self.find_next_candidate - # See if we can alter the target list to find any - # corresponding targets in linked build directories - for node in self.targets: - alt, message = node.alter_targets() - if alt: - self.message = message - self.candidates.extend(self.order(alt)) - continue + def find_next_candidate(self): + try: + return self.candidates.pop() + except IndexError: + pass + try: + node = self.top_targets.pop() + except IndexError: + return None + self.current_top = node + alt, message = node.alter_targets() + if alt: + self.message = message + self.candidates.append(node) + self.candidates.extend(self.order(alt)) + node = self.candidates.pop() + return node + + def no_next_candidate(self): + return None def _find_next_ready_node(self): """Find the next node that is ready to be built""" @@ -303,8 +370,13 @@ class Taskmaster: T = self.trace - while self.candidates: - node = self.candidates.pop().disambiguate() + while 1: + node = self.next_candidate() + if node is None: + self.ready = None + break + + node = node.disambiguate() state = node.get_state() if CollectStats: @@ -318,14 +390,14 @@ class Taskmaster: if T: T.write('Taskmaster: %s:' % repr(str(node))) - # Skip this node if it has already been handled: - if not state in [ SCons.Node.no_state, SCons.Node.stack ]: + # Skip this node if it has already been evaluated: + if state > SCons.Node.pending: if S: S.already_handled = S.already_handled + 1 - if T: T.write(' already handled\n') + if T: T.write(' already handled (%s)\n' % StateString[state]) continue # Mark this node as being on the execution stack: - node.set_state(SCons.Node.stack) + node.set_state(SCons.Node.pending) try: children = node.children() @@ -349,10 +421,11 @@ class Taskmaster: if S: S.problem = S.problem + 1 if T: T.write(' exception\n') break - else: + + if T and children: c = map(str, children) c.sort() - if T: T.write(' children:\n %s\n ' % c) + T.write(' children:\n %s\n ' % c) childinfo = map(lambda N: (N.get_state(), N.is_derived() or N.is_pseudo_derived(), @@ -374,19 +447,14 @@ class Taskmaster: continue # Detect dependency cycles: - cycle = filter(lambda I: I[0] == SCons.Node.stack, childinfo) - if cycle: - # The node we popped from the candidate stack is part of - # the cycle we detected, so put it back before generating - # the message to report. - self.candidates.append(node) - nodes = filter(lambda N: N.get_state() == SCons.Node.stack, - self.candidates) + \ - map(lambda I: I[2], cycle) - nodes.reverse() - desc = "Dependency cycle: " + string.join(map(str, nodes), " -> ") - if T: T.write(' dependency cycle\n') - raise SCons.Errors.UserError, desc + pending_nodes = filter(lambda I: I[0] == SCons.Node.pending, childinfo) + if pending_nodes: + for p in pending_nodes: + cycle = find_cycle([p[2], node]) + if cycle: + desc = "Dependency cycle: " + string.join(map(str, cycle), " -> ") + if T: T.write(' dependency cycle\n') + raise SCons.Errors.UserError, desc # Select all of the dependencies that are derived targets # (that is, children who have builders or are side effects). @@ -403,6 +471,7 @@ class Taskmaster: # list will get cleared and we'll re-scan the newly-built # file(s) for updated implicit dependencies. map(lambda n, P=node: n.add_to_waiting_parents(P), not_started) + node.ref_count = len(not_started) # Now we add these derived targets to the candidates # list so they can be examined and built. We have to @@ -418,6 +487,7 @@ class Taskmaster: self.candidates.append(node) not_started.reverse() self.candidates.extend(self.order(not_started)) + if S: S.not_started = S.not_started + 1 if T: c = map(str, not_started) @@ -436,11 +506,8 @@ class Taskmaster: # dependency list will get cleared and we'll re-scan the # newly-built file(s) for updated implicit dependencies. map(lambda n, P=node: n.add_to_waiting_parents(P), not_built) + node.ref_count = len(not_built) - # And add this node to the "pending" list, so it can get - # put back on the candidates list when appropriate. - self.pending.append(node) - node.set_state(SCons.Node.pending) if S: S.not_built = S.not_built + 1 if T: c = map(str, not_built) @@ -455,8 +522,7 @@ class Taskmaster: node.side_effects, 0) if side_effects: - self.pending.append(node) - node.set_state(SCons.Node.pending) + map(lambda n, P=node: n.add_to_waiting_s_e(P), side_effects) if S: S.side_effects = S.side_effects + 1 if T: c = map(str, side_effects) @@ -468,7 +534,7 @@ class Taskmaster: # this node is ready to be built. self.ready = node if S: S.build = S.build + 1 - if T: T.write(' evaluating\n') + if T: T.write(' evaluating %s\n' % node) break def next_task(self): @@ -485,10 +551,8 @@ class Taskmaster: tlist = node.builder.targets(node) except AttributeError: tlist = [node] - self.executing.extend(tlist) - self.executing.extend(node.side_effects) - task = self.tasker(self, tlist, node in self.targets, node) + task = self.tasker(self, tlist, node is self.current_top, node) try: task.make_ready() except KeyboardInterrupt: @@ -508,53 +572,19 @@ class Taskmaster: return task - def is_blocked(self): - self._find_next_ready_node() - - return not self.ready and (self.pending or self.executing) - - def next_top_level_candidate(self): - candidates = self.candidates[:] - candidates.reverse() - for c in candidates: - if c in self.targets: - return c - return None - def stop(self): """Stop the current build completely.""" - self.candidates = [] + self.next_candidate = self.no_next_candidate self.ready = None - self.pending = [] def failed(self, node): - try: - tlist = node.builder.targets(node) - except AttributeError: - tlist = [node] - for t in tlist: - self.executing.remove(t) - for side_effect in node.side_effects: - self.executing.remove(side_effect) + pass def executed(self, node): try: tlist = node.builder.targets(node) except AttributeError: tlist = [node] - for t in tlist: - self.executing.remove(t) - for side_effect in node.side_effects: - self.executing.remove(side_effect) - - # move the current pending nodes to the candidates list: - # (they may not all be ready to build, but _find_next_ready_node() - # will figure out which ones are really ready) - for node in self.pending: - node.set_state(SCons.Node.no_state) - self.pending.reverse() - self.candidates.extend(self.pending) - self.pending = [] def exception_raise(self, exception): exc = exception[:] |