Merge pull request #881 from nico/depscancycles

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

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