Package SCons :: Module Taskmaster :: Class Taskmaster
[hide private]
[frames] | no frames]

Class Taskmaster

source code

object --+
         |
        Taskmaster


The Taskmaster for walking the dependency DAG.



Instance Methods [hide private]
 
__init__(self, targets=[], tasker=False, order=False, trace=False)
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
source code
 
find_next_candidate(self)
Returns the next candidate Node for (potential) evaluation.
source code
 
no_next_candidate(self)
Stops Taskmaster processing by not returning a next candidate.
source code
 
_validate_pending_children(self)
Validate the content of the pending_children set.
source code
 
trace_message(self, message) source code
 
trace_node(self, node) source code
 
_find_next_ready_node(self)
Finds the next node that is ready to be built.
source code
 
next_task(self)
Returns the next task to be executed.
source code
 
will_not_build(self, nodes, node_func=<function <lambda> at 0x88dc1b4>)
Perform clean-up about nodes that will never be built.
source code
 
stop(self)
Stops the current build completely.
source code
 
cleanup(self)
Check for dependency cycles.
source code

Inherited from object: __delattr__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __str__

Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self, targets=[], tasker=False, order=False, trace=False)
(Constructor)

source code 
x.__init__(...) initializes x; see x.__class__.__doc__ for signature

Overrides: object.__init__
(inherited documentation)

find_next_candidate(self)

source code 

Returns the next candidate Node for (potential) evaluation.

The candidate list (really a stack) initially consists of all of
the top-level (command line) targets provided when the Taskmaster
was initialized.  While we walk the DAG, visiting Nodes, all the
children that haven't finished processing get pushed on to the
candidate list.  Each child can then be popped and examined in
turn for whether *their* children are all up-to-date, in which
case a Task will be created for their actual evaluation and
potential building.

Here is where we also allow candidate Nodes to alter the list of
Nodes that should be examined.  This is used, for example, when
invoking SCons in a source directory.  A source directory Node can
return its corresponding build directory Node, essentially saying,
"Hey, you really need to build this thing over here instead."

no_next_candidate(self)

source code 

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.

_validate_pending_children(self)

source code 

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.

_find_next_ready_node(self)

source code 

Finds the next node that is ready to be built.

This is *the* main guts of the DAG walk.  We loop through the
list of candidates, looking for something that has no un-built
children (i.e., that is a leaf Node or has dependencies that are
all leaf Nodes or up-to-date).  Candidate Nodes are re-scanned
(both the target Node itself and its sources, which are always
scanned in the context of a given target) to discover implicit
dependencies.  A Node that must wait for some children to be
built will be put back on the candidates list after the children
have finished building.  A Node that has been put back on the
candidates list in this way may have itself (or its sources)
re-scanned, in order to handle generated header files (e.g.) and
the implicit dependencies therein.

Note that this method does not do any signature calculation or
up-to-date check itself.  All of that is handled by the Task
class.  This is purely concerned with the dependency graph walk.

next_task(self)

source code 

Returns the next task to be executed.

This simply asks for the next Node to be evaluated, and then wraps
it in the specific Task subclass with which we were initialized.

will_not_build(self, nodes, node_func=<function <lambda> at 0x88dc1b4>)

source code 

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).