+ candidates = self.candidates
+ self.candidates = []
+ 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
+
+ def trace_node(self, node):
+ return '<%-10s %-3s %s>' % (StateString[node.get_state()],
+ node.ref_count,
+ repr(str(node)))
+
+ def _find_next_ready_node(self):
+ """
+ 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.
+ """
+
+ self.ready_exc = None
+
+ T = self.trace
+ if T: T.write(u'\n' + self.trace_message('Looking for a node to evaluate'))
+
+ while True:
+ node = self.next_candidate()
+ if node is None:
+ if T: T.write(self.trace_message('No candidate anymore.') + u'\n')
+ return None
+
+ node = node.disambiguate()
projects / scons.git / blobdiff