Let DependencyScan::RecomputeDirty() work correclty with cyclic graphs.

RecomputDirty(edge) currently works roughly like this:

      RecomputeDirty(edge):
        LoadDeps(edge)
        for in in edge.inputs:
          if in.StatIfNecessary():
            RecomputeDirty(in.in_edge)  # recurse into inputs
        for out in edge.outputs:
          out.StatIfNecessary()  # mark outputs as visited

It uses the stat state of each node to mark nodes as visited and doesn't
traverse across nodes that have been visited already.  For cyclic graphs
with an edge with multiple outputs on the cycle, nothing prevents an
edge to be visited more than once if the cycle is entered through an
output that isn't on the cycle.  In other words, RecomputeDirty() for
the same edge can be on the call stack more than once.  This is bad for
at least two reasons:

  1. Deps are added multiple times, making the graph confusing to reason
     about.

  2.  LoadDeps() will insert into the inputs_ of an edge that's iterated
      over in a callframe higher up. This can invalidate the iterator,
      which causes a crash when the callframe with the loop over the
      now-invalidated iterator resumes.

To fix this, let RecomputeDirty() mark all outputs of an edge as visited
as the first thing it does.  This way, even if the edge is on a cycle
with several outputs, each output is already marked and no edge will
have its deps loaded more than once.

Fixes the crashes in #875.  (In practice, it turns the crashes into
"stuck [this is a bug]" messages for now, due to the example without
duplicate rules in #867)

3 files changed, 89 insertions, 4 deletions

diff --git a/src/build.cc b/src/build.cc
index ba2f93d..5d66f4b 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -576,7 +576,6 @@ Node* Builder::AddTarget(const string& name, string* err) {
 }
 
 bool Builder::AddTarget(Node* node, string* err) {
-  node->StatIfNecessary(disk_interface_);
   if (Edge* in_edge = node->in_edge()) {
     if (!scan_.RecomputeDirty(in_edge, err))
       return false;
diff --git a/src/graph.cc b/src/graph.cc
index 57f790c..44eca3c 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -62,6 +62,19 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
   edge->outputs_ready_ = true;
   edge->deps_missing_ = false;
 
+  // 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) {
+    (*o)->StatIfNecessary(disk_interface_);
+  }
+
   if (!dep_loader_.LoadDeps(edge, err)) {
     if (!err->empty())
       return false;
@@ -110,11 +123,9 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
   if (!dirty)
     dirty = RecomputeOutputsDirty(edge, most_recent_input);
 
-  // Finally, visit each output to mark off that we've visited it, and update
-  // their dirty state if necessary.
+  // Finally, visit each output and update their dirty state if necessary.
   for (vector<Node*>::iterator o = edge->outputs_.begin();
        o != edge->outputs_.end(); ++o) {
-    (*o)->StatIfNecessary(disk_interface_);
     if (dirty)
       (*o)->MarkDirty();
   }
diff --git a/src/graph_test.cc b/src/graph_test.cc
index 382d352..e41f5cc 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -252,6 +252,81 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) {
   ASSERT_FALSE(plan_.more_to_do());
 }
 
+// Verify that cycles in graphs with multiple outputs are handled correctly
+// in RecomputeDirty() and don't cause deps to be loaded multiple times.
+TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) {
+  AssertParse(&state_,
+"rule deprule\n"
+"   depfile = dep.d\n"
+"   command = unused\n"
+"build a b: deprule\n"
+  );
+  fs_.Create("dep.d", "a: b\n");
+
+  string err;
+  Edge* edge = GetNode("a")->in_edge();
+  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  ASSERT_EQ("", 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
+  // only once:
+  EXPECT_EQ(1, edge->inputs_.size());
+  EXPECT_EQ("b", edge->inputs_[0]->path());
+}
+
+// Like CycleWithLengthZeroFromDepfile but with a higher cycle length.
+TEST_F(GraphTest, CycleWithLengthOneFromDepfile) {
+  AssertParse(&state_,
+"rule deprule\n"
+"   depfile = dep.d\n"
+"   command = unused\n"
+"rule r\n"
+"   command = unused\n"
+"build a b: deprule\n"
+"build c: r b\n"
+  );
+  fs_.Create("dep.d", "a: c\n");
+
+  string err;
+  Edge* edge = GetNode("a")->in_edge();
+  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  ASSERT_EQ("", 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
+  // output)), the deps should have been loaded only once:
+  EXPECT_EQ(1, edge->inputs_.size());
+  EXPECT_EQ("c", edge->inputs_[0]->path());
+}
+
+// Like CycleWithLengthOneFromDepfile but building a node one hop away from
+// the cycle.
+TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) {
+  AssertParse(&state_,
+"rule deprule\n"
+"   depfile = dep.d\n"
+"   command = unused\n"
+"rule r\n"
+"   command = unused\n"
+"build a b: deprule\n"
+"build c: r b\n"
+"build d: r a\n"
+  );
+  fs_.Create("dep.d", "a: c\n");
+
+  string err;
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d")->in_edge(), &err));
+  ASSERT_EQ("", 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
+  // output)), the deps should have been loaded only once:
+  Edge* edge = GetNode("a")->in_edge();
+  EXPECT_EQ(1, edge->inputs_.size());
+  EXPECT_EQ("c", edge->inputs_[0]->path());
+}
+
 #ifdef _WIN32
 TEST_F(GraphTest, Decanonicalize) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,