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)

1 files changed, 75 insertions, 0 deletions

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_,