diff options
| -rw-r--r-- | src/graph.cc | 78 | ||||
| -rw-r--r-- | src/graph.h | 3 | ||||
| -rw-r--r-- | src/graph_test.cc | 12 |
3 files changed, 73 insertions, 20 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); diff --git a/src/graph.h b/src/graph.h index 1b30dee..586c588 100644 --- a/src/graph.h +++ b/src/graph.h @@ -277,6 +277,9 @@ struct DependencyScan { } private: + bool RecomputeDirty(Node* node, vector<Node*>* stack, string* err); + bool VerifyDAG(Node* node, vector<Node*>* stack, string* err); + /// Recompute whether a given single output should be marked dirty. /// Returns true if so. bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input, diff --git a/src/graph_test.cc b/src/graph_test.cc index 87f3430..b76526f 100644 --- a/src/graph_test.cc +++ b/src/graph_test.cc @@ -335,8 +335,8 @@ TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) { fs_.Create("dep.d", "a: b\n"); string err; - EXPECT_TRUE(scan_.RecomputeDirty(GetNode("a"), &err)); - ASSERT_EQ("", err); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err)); + ASSERT_EQ("dependency cycle: b -> b", err); // Despite the depfile causing edge to be a cycle (it has outputs a and b, // but the depfile also adds b as an input), the deps should have been loaded @@ -360,8 +360,8 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfile) { fs_.Create("dep.d", "a: c\n"); string err; - EXPECT_TRUE(scan_.RecomputeDirty(GetNode("a"), &err)); - ASSERT_EQ("", err); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err)); + ASSERT_EQ("dependency cycle: b -> c -> b", err); // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b, // but c's in_edge has b as input but the depfile also adds |edge| as @@ -387,8 +387,8 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) { fs_.Create("dep.d", "a: c\n"); string err; - EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d"), &err)); - ASSERT_EQ("", err); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), &err)); + ASSERT_EQ("dependency cycle: b -> c -> b", err); // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b, // but c's in_edge has b as input but the depfile also adds |edge| as |