X-Git-Url: http://git.tremily.us/?a=blobdiff_plain;f=src%2Fengine%2FSCons%2FTaskmaster.py;h=f60b2e254b3e77e0822a1ebcdf02bffbd01b32a9;hb=6a218d30e5fa1a14835a31129881b4288db7dc1d;hp=a82d917f457c6fabc5c9e684514d35c2f6b78e51;hpb=f0935a3f7c37f0fdcbaea486d8531ebb0c89a9b3;p=scons.git diff --git a/src/engine/SCons/Taskmaster.py b/src/engine/SCons/Taskmaster.py index a82d917f..f60b2e25 100644 --- a/src/engine/SCons/Taskmaster.py +++ b/src/engine/SCons/Taskmaster.py @@ -20,6 +20,7 @@ # OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION # WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. # +from __future__ import generators ### KEEP FOR COMPATIBILITY FIXERS __doc__ = """ Generic Taskmaster module for the SCons build engine. @@ -52,12 +53,12 @@ __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__" from itertools import chain import operator -import string import sys import traceback import SCons.Errors import SCons.Node +import SCons.Warnings StateString = SCons.Node.StateString NODE_NO_STATE = SCons.Node.no_state @@ -164,7 +165,7 @@ class Task: the Action is actually called to build the targets. """ T = self.tm.trace - if T: T.write(self.trace_message('Task.prepare()', self.node)) + if T: T.write(self.trace_message(u'Task.prepare()', self.node)) # Now that it's the appropriate time, give the TaskMaster a # chance to raise any exceptions it encountered while preparing @@ -185,8 +186,9 @@ class Task: # target t.prepare() methods check that each target's explicit # or implicit dependencies exists, and also initialize the # .sconsign info. - self.targets[0].get_executor().prepare() - for t in self.targets: + executor = self.targets[0].get_executor() + executor.prepare() + for t in executor.get_action_targets(): t.prepare() for s in t.side_effects: s.prepare() @@ -197,14 +199,14 @@ class Task: return self.node def needs_execute(self): - """ - Called to determine whether the task's execute() method should - be run. - - This method allows one to skip the somethat costly execution - of the execute() method in a seperate thread. For example, - that would be unnecessary for up-to-date targets. - """ + # TODO(deprecate): "return True" is the old default behavior; + # change it to NotImplementedError (after running through the + # Deprecation Cycle) so the desired behavior is explicitly + # determined by which concrete subclass is used. + #raise NotImplementedError + msg = ('Direct use of the Taskmaster.Task class will be deprecated\n' + + '\tin a future release.') + SCons.Warnings.warn(SCons.Warnings.TaskmasterNeedsExecuteWarning, msg) return True def execute(self): @@ -216,12 +218,19 @@ class Task: prepare(), executed() or failed(). """ T = self.tm.trace - if T: T.write(self.trace_message('Task.execute()', self.node)) + if T: T.write(self.trace_message(u'Task.execute()', self.node)) try: everything_was_cached = 1 for t in self.targets: - if not t.retrieve_from_cache(): + if t.retrieve_from_cache(): + # Call the .built() method without calling the + # .push_to_cache() method, since we just got the + # target from the cache and don't need to push + # it back there. + t.set_state(NODE_EXECUTED) + t.built() + else: everything_was_cached = 0 break if not everything_was_cached: @@ -277,6 +286,7 @@ class Task: for side_effect in t.side_effects: side_effect.set_state(NODE_NO_STATE) t.set_state(NODE_EXECUTED) + t.push_to_cache() t.built() t.visited() @@ -303,13 +313,12 @@ class Task: the executing state, it might also be invoked on up-to-date nodes when using Configure(). """ - T = self.tm.trace if T: T.write(self.trace_message('Task.failed_stop()', self.node)) # Invoke will_not_build() to clean-up the pending children # list. - self.tm.will_not_build(self.targets) + self.tm.will_not_build(self.targets, lambda n: n.set_state(NODE_FAILED)) # Tell the taskmaster to not start any new tasks self.tm.stop() @@ -334,8 +343,8 @@ class Task: T = self.tm.trace if T: T.write(self.trace_message('Task.failed_continue()', self.node)) - self.tm.will_not_build(self.targets) - + self.tm.will_not_build(self.targets, lambda n: n.set_state(NODE_FAILED)) + def make_ready_all(self): """ Marks all targets in a task ready for execution. @@ -350,7 +359,8 @@ class Task: for t in self.targets: t.disambiguate().set_state(NODE_EXECUTING) for s in t.side_effects: - s.set_state(NODE_EXECUTING) + # add disambiguate here to mirror the call on targets above + s.disambiguate().set_state(NODE_EXECUTING) def make_ready_current(self): """ @@ -360,7 +370,7 @@ class Task: This is the default behavior for building only what's necessary. """ T = self.tm.trace - if T: T.write(self.trace_message('Task.make_ready_current()', + if T: T.write(self.trace_message(u'Task.make_ready_current()', self.node)) self.out_of_date = [] @@ -381,8 +391,9 @@ class Task: for t in self.targets: t.set_state(NODE_EXECUTING) for s in t.side_effects: - s.set_state(NODE_EXECUTING) - else: + # add disambiguate here to mirror the call on targets in first loop above + s.disambiguate().set_state(NODE_EXECUTING) + else: for t in self.targets: # We must invoke visited() to ensure that the node # information has been computed before allowing the @@ -404,7 +415,7 @@ class Task: that can be put back on the candidates list. """ T = self.tm.trace - if T: T.write(self.trace_message('Task.postprocess()', self.node)) + if T: T.write(self.trace_message(u'Task.postprocess()', self.node)) # We may have built multiple targets, some of which may have # common parents waiting for this build. Count up how many @@ -415,14 +426,16 @@ class Task: targets = set(self.targets) + pending_children = self.tm.pending_children parents = {} for t in targets: # A node can only be in the pending_children set if it has # some waiting_parents. if t.waiting_parents: - if T: T.write(self.trace_message('Task.postprocess()', + if T: T.write(self.trace_message(u'Task.postprocess()', t, 'removing')) + pending_children.discard(t) for p in t.waiting_parents: parents[p] = parents.get(p, 0) + 1 @@ -435,16 +448,14 @@ class Task: for p in s.waiting_s_e: if p.ref_count == 0: self.tm.candidates.append(p) - self.tm.pending_children.discard(p) for p, subtract in parents.items(): p.ref_count = p.ref_count - subtract - if T: T.write(self.trace_message('Task.postprocess()', + if T: T.write(self.trace_message(u'Task.postprocess()', p, - 'adjusting parent ref count')) + 'adjusted parent ref count')) if p.ref_count == 0: self.tm.candidates.append(p) - self.tm.pending_children.discard(p) for t in targets: t.postprocess() @@ -502,6 +513,30 @@ class Task: exc_traceback = None raise exc_type, exc_value, exc_traceback +class AlwaysTask(Task): + def needs_execute(self): + """ + Always returns True (indicating this Task should always + be executed). + + Subclasses that need this behavior (as opposed to the default + of only executing Nodes that are out of date w.r.t. their + dependencies) can use this as follows: + + class MyTaskSubclass(SCons.Taskmaster.Task): + needs_execute = SCons.Taskmaster.Task.execute_always + """ + return True + +class OutOfDateTask(Task): + def needs_execute(self): + """ + Returns True (indicating this Task should be executed) if this + Task's target state indicates it needs executing, which has + already been determined by an earlier up-to-date check. + """ + return self.targets[0].get_state() == SCons.Node.executing + def find_cycle(stack, visited): if stack[-1] in visited: @@ -522,11 +557,13 @@ class Taskmaster: The Taskmaster for walking the dependency DAG. """ - def __init__(self, targets=[], tasker=Task, order=None, trace=None): + def __init__(self, targets=[], tasker=None, order=None, trace=None): self.original_top = targets self.top_targets_left = targets[:] self.top_targets_left.reverse() self.candidates = [] + if tasker is None: + tasker = OutOfDateTask self.tasker = tasker if not order: order = lambda l: l @@ -575,7 +612,7 @@ class Taskmaster: def no_next_candidate(self): """ Stops Taskmaster processing by not returning a next candidate. - + Note that we have to clean-up the Taskmaster candidate list because the cycle detection depends on the fact all nodes have been processed somehow. @@ -583,9 +620,88 @@ class Taskmaster: while self.candidates: candidates = self.candidates self.candidates = [] - self.will_not_build(candidates, lambda n: n.state < NODE_UP_TO_DATE) + self.will_not_build(candidates) return None + def _validate_pending_children(self): + """ + Validate the content of the pending_children set. Assert if an + internal error is found. + + This function is used strictly for debugging the taskmaster by + checking that no invariants are violated. It is not used in + normal operation. + + The pending_children set is used to detect cycles in the + dependency graph. We call a "pending child" a child that is + found in the "pending" state when checking the dependencies of + its parent node. + + A pending child can occur when the Taskmaster completes a loop + through a cycle. For example, lets imagine a graph made of + three node (A, B and C) making a cycle. The evaluation starts + at node A. The taskmaster first consider whether node A's + child B is up-to-date. Then, recursively, node B needs to + check whether node C is up-to-date. This leaves us with a + dependency graph looking like: + + Next candidate \ + \ + Node A (Pending) --> Node B(Pending) --> Node C (NoState) + ^ | + | | + +-------------------------------------+ + + Now, when the Taskmaster examines the Node C's child Node A, + it finds that Node A is in the "pending" state. Therefore, + Node A is a pending child of node C. + + Pending children indicate that the Taskmaster has potentially + loop back through a cycle. We say potentially because it could + also occur when a DAG is evaluated in parallel. For example, + consider the following graph: + + + Node A (Pending) --> Node B(Pending) --> Node C (Pending) --> ... + | ^ + | | + +----------> Node D (NoState) --------+ + / + Next candidate / + + The Taskmaster first evaluates the nodes A, B, and C and + starts building some children of node C. Assuming, that the + maximum parallel level has not been reached, the Taskmaster + will examine Node D. It will find that Node C is a pending + child of Node D. + + In summary, evaluating a graph with a cycle will always + involve a pending child at one point. A pending child might + indicate either a cycle or a diamond-shaped DAG. Only a + fraction of the nodes ends-up being a "pending child" of + another node. This keeps the pending_children set small in + practice. + + We can differentiate between the two cases if we wait until + the end of the build. At this point, all the pending children + nodes due to a diamond-shaped DAG will have been properly + built (or will have failed to build). But, the pending + children involved in a cycle will still be in the pending + state. + + The taskmaster removes nodes from the pending_children set as + soon as a pending_children node moves out of the pending + state. This also helps to keep the pending_children set small. + """ + + for n in self.pending_children: + assert n.state in (NODE_PENDING, NODE_EXECUTING), \ + (str(n), StateString[n.state]) + assert len(n.waiting_parents) != 0, (str(n), len(n.waiting_parents)) + for p in n.waiting_parents: + assert p.ref_count > 0, (str(n), str(p), p.ref_count) + + def trace_message(self, message): return 'Taskmaster: %s\n' % message @@ -619,17 +735,25 @@ class Taskmaster: self.ready_exc = None T = self.trace - if T: T.write('\n' + self.trace_message('Looking for a node to evaluate')) + if T: T.write(u'\n' + self.trace_message('Looking for a node to evaluate')) - while 1: + while True: node = self.next_candidate() if node is None: - if T: T.write(self.trace_message('No candidate anymore.') + '\n') + if T: T.write(self.trace_message('No candidate anymore.') + u'\n') return None node = node.disambiguate() state = node.get_state() + # For debugging only: + # + # try: + # self._validate_pending_children() + # except: + # self.ready_exc = sys.exc_info() + # return node + if CollectStats: if not hasattr(node, 'stats'): node.stats = Stats() @@ -639,7 +763,7 @@ class Taskmaster: else: S = None - if T: T.write(self.trace_message(' Considering node %s and its children:' % self.trace_node(node))) + if T: T.write(self.trace_message(u' Considering node %s and its children:' % self.trace_node(node))) if state == NODE_NO_STATE: # Mark this node as being on the execution stack: @@ -647,16 +771,18 @@ class Taskmaster: elif state > NODE_PENDING: # Skip this node if it has already been evaluated: if S: S.already_handled = S.already_handled + 1 - if T: T.write(self.trace_message(' already handled (executed)')) + if T: T.write(self.trace_message(u' already handled (executed)')) continue + executor = node.get_executor() + try: - children = node.children() + children = executor.get_all_children() except SystemExit: exc_value = sys.exc_info()[1] e = SCons.Errors.ExplicitExit(node, exc_value.code) self.ready_exc = (SCons.Errors.ExplicitExit, e) - if T: T.write('Taskmaster: SystemExit\n') + if T: T.write(self.trace_message(' SystemExit')) return node except Exception, e: # We had a problem just trying to figure out the @@ -673,10 +799,10 @@ class Taskmaster: children_not_ready = [] children_failed = False - for child in chain(children,node.prerequisites): + for child in chain(executor.get_all_prerequisites(), children): childstate = child.get_state() - if T: T.write(self.trace_message(' ' + self.trace_node(child))) + if T: T.write(self.trace_message(u' ' + self.trace_node(child))) if childstate == NODE_NO_STATE: children_not_visited.append(child) @@ -717,11 +843,11 @@ class Taskmaster: # added the other children to the list of candidate nodes # to keep on building (--keep-going). if children_failed: - node.set_state(NODE_FAILED) + for n in executor.get_action_targets(): + n.set_state(NODE_FAILED) if S: S.child_failed = S.child_failed + 1 - if T: T.write('Taskmaster:****** <%-10s %-3s %s>\n' % - (StateString[node.get_state()], node.ref_count, repr(str(node)))) + if T: T.write(self.trace_message('****** %s\n' % self.trace_node(node))) continue if children_not_ready: @@ -735,17 +861,21 @@ class Taskmaster: # count so we can be put back on the list for # re-evaluation when they've all finished. node.ref_count = node.ref_count + child.add_to_waiting_parents(node) - if T: T.write(self.trace_message(' adjusting ref count: %s, child %s' % + if T: T.write(self.trace_message(u' adjusted ref count: %s, child %s' % (self.trace_node(node), repr(str(child))))) + if T: + for pc in children_pending: + T.write(self.trace_message(' adding %s to the pending children set\n' % + self.trace_node(pc))) self.pending_children = self.pending_children | children_pending - + continue # Skip this node if it has side-effects that are # currently being built: wait_side_effects = False - for se in node.side_effects: + for se in executor.get_action_side_effects(): if se.get_state() == NODE_EXECUTING: se.add_to_waiting_s_e(node) wait_side_effects = True @@ -757,8 +887,17 @@ class Taskmaster: # The default when we've gotten through all of the checks above: # this node is ready to be built. if S: S.build = S.build + 1 - if T: T.write(self.trace_message('Evaluating %s\n' % + if T: T.write(self.trace_message(u'Evaluating %s\n' % self.trace_node(node))) + + # For debugging only: + # + # try: + # self._validate_pending_children() + # except: + # self.ready_exc = sys.exc_info() + # return node + return node return None @@ -775,7 +914,7 @@ class Taskmaster: if node is None: return None - tlist = node.get_executor().targets + tlist = node.get_executor().get_all_targets() task = self.tasker(self, tlist, node in self.original_top, node) try: @@ -794,25 +933,26 @@ class Taskmaster: return task - def will_not_build(self, nodes, mark_fail=lambda n: n.state != NODE_FAILED): + def will_not_build(self, nodes, node_func=lambda n: None): """ - Perform clean-up about nodes that will never be built. + Perform clean-up about nodes that will never be built. Invokes + a user defined function on all of these nodes (including all + of their parents). """ + T = self.trace + pending_children = self.pending_children - to_visit = set() - for node in nodes: - # Set failure state on all of the parents that were dependent - # on this failed build. - if mark_fail(node): - node.set_state(NODE_FAILED) - parents = node.waiting_parents - to_visit = to_visit | parents - pending_children = pending_children - parents + to_visit = set(nodes) + pending_children = pending_children - to_visit + if T: + for n in nodes: + T.write(self.trace_message(' removing node %s from the pending children set\n' % + self.trace_node(n))) try: - while 1: + while True: try: node = to_visit.pop() except AttributeError: @@ -822,11 +962,21 @@ class Taskmaster: to_visit.remove(node) else: break - if mark_fail(node): - node.set_state(NODE_FAILED) - parents = node.waiting_parents - to_visit = to_visit | parents - pending_children = pending_children - parents + + node_func(node) + + # Prune recursion by flushing the waiting children + # list immediately. + parents = node.waiting_parents + node.waiting_parents = set() + + to_visit = to_visit | parents + pending_children = pending_children - parents + + for p in parents: + p.ref_count = p.ref_count - 1 + if T: T.write(self.trace_message(' removing parent %s from the pending children set\n' % + self.trace_node(p))) except KeyError: # The container to_visit has been emptied. pass @@ -846,15 +996,37 @@ class Taskmaster: """ Check for dependency cycles. """ - if self.pending_children: - desc = 'Found dependency cycle(s):\n' - for node in self.pending_children: - cycle = find_cycle([node], set()) - if cycle: - desc = desc + " " + string.join(map(str, cycle), " -> ") + "\n" - else: - desc = desc + \ - " Internal Error: no cycle found for node %s (%s) in state %s\n" % \ - (node, repr(node), StateString[node.get_state()]) + if not self.pending_children: + return + + # TODO(1.5) + #nclist = [ (n, find_cycle([n], set())) for n in self.pending_children ] + nclist = [(n, find_cycle([n], set())) for n in self.pending_children] + + # TODO(1.5) + #genuine_cycles = [ + # node for node, cycle in nclist + # if cycle or node.get_state() != NODE_EXECUTED + #] + genuine_cycles = [t for t in nclist if t[1] or t[0].get_state() != NODE_EXECUTED] + if not genuine_cycles: + # All of the "cycles" found were single nodes in EXECUTED state, + # which is to say, they really weren't cycles. Just return. + return + + desc = 'Found dependency cycle(s):\n' + for node, cycle in nclist: + if cycle: + desc = desc + " " + " -> ".join(map(str, cycle)) + "\n" + else: + desc = desc + \ + " Internal Error: no cycle found for node %s (%s) in state %s\n" % \ + (node, repr(node), StateString[node.get_state()]) + + raise SCons.Errors.UserError(desc) - raise SCons.Errors.UserError, desc +# Local Variables: +# tab-width:4 +# indent-tabs-mode:nil +# End: +# vim: set expandtab tabstop=4 shiftwidth=4: