diff options
Diffstat (limited to 'src/graph.cc')
-rw-r--r-- | src/graph.cc | 78 |
1 files changed, 64 insertions, 14 deletions
diff --git a/src/graph.cc b/src/graph.cc index c34fab8..7dd9491 100644 --- a/src/graph.cc +++ b/src/graph.cc @@ -32,28 +32,43 @@ bool Node::Stat(DiskInterface* disk_interface, string* err) { } bool DependencyScan::RecomputeDirty(Node* node, string* err) { + vector<Node*> stack; + return RecomputeDirty(node, &stack, err); +} + +bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack, + string* err) { Edge* edge = node->in_edge(); if (!edge) { + // If we already visited this leaf node then we are done. + if (node->status_known()) + return true; // This node has no in-edge; it is dirty if it is missing. + if (!node->StatIfNecessary(disk_interface_, err)) + return false; if (!node->exists()) EXPLAIN("%s has no in-edge and is missing", node->path().c_str()); node->set_dirty(!node->exists()); return true; } + // If we already finished this edge then we are done. + if (edge->mark_ == Edge::VisitDone) + return true; + + // If we encountered this edge earlier in the call stack we have a cycle. + if (!VerifyDAG(node, stack, err)) + return false; + + // Mark the edge temporarily while in the call stack. + edge->mark_ = Edge::VisitInStack; + stack->push_back(node); + bool dirty = false; edge->outputs_ready_ = true; edge->deps_missing_ = false; // Load output mtimes so we can compare them to the most recent input below. - // RecomputeDirty() recursively walks the graph following the input nodes - // of |edge| and the in_edges of these nodes. It uses the stat state of each - // node to mark nodes as visited and doesn't traverse across nodes that have - // been visited already. To make sure that every edge is visited only once - // (important because an edge's deps are loaded every time it's visited), mark - // all outputs of |edge| visited as a first step. This ensures that edges - // with multiple inputs and outputs are visited only once, even in cyclic - // graphs. for (vector<Node*>::iterator o = edge->outputs_.begin(); o != edge->outputs_.end(); ++o) { if (!(*o)->StatIfNecessary(disk_interface_, err)) @@ -72,12 +87,9 @@ bool DependencyScan::RecomputeDirty(Node* node, string* err) { Node* most_recent_input = NULL; for (vector<Node*>::iterator i = edge->inputs_.begin(); i != edge->inputs_.end(); ++i) { - if (!(*i)->status_known()) { - if (!(*i)->StatIfNecessary(disk_interface_, err)) - return false; - if (!RecomputeDirty(*i, err)) - return false; - } + // Visit this input. + if (!RecomputeDirty(*i, stack, err)) + return false; // If an input is not ready, neither are our outputs. if (Edge* in_edge = (*i)->in_edge()) { @@ -120,9 +132,47 @@ bool DependencyScan::RecomputeDirty(Node* node, string* err) { if (dirty && !(edge->is_phony() && edge->inputs_.empty())) edge->outputs_ready_ = false; + // Mark the edge as finished during this walk now that it will no longer + // be in the call stack. + edge->mark_ = Edge::VisitDone; + assert(stack->back() == node); + stack->pop_back(); + return true; } +bool DependencyScan::VerifyDAG(Node* node, vector<Node*>* stack, string* err) { + Edge* edge = node->in_edge(); + assert(edge != NULL); + + // If we have no temporary mark on the edge then we do not yet have a cycle. + if (edge->mark_ != Edge::VisitInStack) + return true; + + // We have this edge earlier in the call stack. Find it. + vector<Node*>::iterator start = stack->begin(); + while (start != stack->end() && (*start)->in_edge() != edge) + ++start; + assert(start != stack->end()); + + // Make the cycle clear by reporting its start as the node at its end + // instead of some other output of the starting edge. For example, + // running 'ninja b' on + // build a b: cat c + // build c: cat a + // should report a -> c -> a instead of b -> c -> a. + *start = node; + + // Construct the error message rejecting the cycle. + *err = "dependency cycle: "; + for (vector<Node*>::const_iterator i = start; i != stack->end(); ++i) { + err->append((*i)->path()); + err->append(" -> "); + } + err->append((*start)->path()); + return false; +} + bool DependencyScan::RecomputeOutputsDirty(Edge* edge, Node* most_recent_input, bool* outputs_dirty, string* err) { string command = edge->EvaluateCommand(/*incl_rsp_file=*/true); |