Teach RecomputeDirty to detect cycles in the build graph

RecomputeDirty is the earliest traversal of the build graph complete
with depfile-loaded dependencies.  Teach it to detect cycles and fail
immediately.  This avoids the need to tolerate cycles in RecomputeDirty
only to diagnose them later.  It also enables future simplification of
Plan and Builder logic because they will be able to assume DAG input.

When RecomputeDirty detects a cycle, reject it with an error message
like that previously produced by Plan::CheckDependencyCycle.

Previously we used the stat state of each node to determine whether
we reached it earlier in the walk.  Retain this approach for leaf
nodes, but add an explicit walk state mark for each Edge so that
we can have a temporary mark to aid cycle detection.

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