Drop unnecessary cycle detection in Plan::AddTarget

We now detect and reject cycles in DependencyScan::RecomputeDirty before
Plan::AddTarget is called so we can assume DAG input to the Plan.

4 files changed, 55 insertions, 100 deletions

diff --git a/src/build.cc b/src/build.cc
index c2a615a..61ef0e8 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -298,26 +298,22 @@ void Plan::Reset() {
 }
 
 bool Plan::AddTarget(Node* node, string* err) {
-  vector<Node*> stack;
-  return AddSubTarget(node, &stack, err);
+  return AddSubTarget(node, NULL, err);
 }
 
-bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) {
+bool Plan::AddSubTarget(Node* node, Node* dependent, string* err) {
   Edge* edge = node->in_edge();
   if (!edge) {  // Leaf node.
     if (node->dirty()) {
       string referenced;
-      if (!stack->empty())
-        referenced = ", needed by '" + stack->back()->path() + "',";
+      if (dependent)
+        referenced = ", needed by '" + dependent->path() + "',";
       *err = "'" + node->path() + "'" + referenced + " missing "
              "and no known rule to make it";
     }
     return false;
   }
 
-  if (CheckDependencyCycle(node, *stack, err))
-    return false;
-
   if (edge->outputs_ready())
     return false;  // Don't need to do anything.
 
@@ -341,47 +337,12 @@ bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) {
   if (!want_ins.second)
     return true;  // We've already processed the inputs.
 
-  stack->push_back(node);
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
-    if (!AddSubTarget(*i, stack, err) && !err->empty())
+    if (!AddSubTarget(*i, node, err) && !err->empty())
       return false;
   }
-  assert(stack->back() == node);
-  stack->pop_back();
-
-  return true;
-}
-
-bool Plan::CheckDependencyCycle(Node* node, const vector<Node*>& stack,
-                                string* err) {
-  vector<Node*>::const_iterator start = stack.begin();
-  while (start != stack.end() && (*start)->in_edge() != node->in_edge())
-    ++start;
-  if (start == stack.end())
-    return false;
-
-  // Build error string for the cycle.
-  vector<Node*> cycle(start, stack.end());
-  cycle.push_back(node);
-
-  if (cycle.front() != cycle.back()) {
-    // Consider
-    //   build a b: cat c
-    //   build c: cat a
-    // stack will contain [b, c], node will be a.  To not print b -> c -> a,
-    // shift by one to get c -> a -> c which makes the cycle clear.
-    cycle.erase(cycle.begin());
-    cycle.push_back(cycle.front());
-    assert(cycle.front() == cycle.back());
-  }
 
-  *err = "dependency cycle: ";
-  for (vector<Node*>::const_iterator i = cycle.begin(); i != cycle.end(); ++i) {
-    if (i != cycle.begin())
-      err->append(" -> ");
-    err->append((*i)->path());
-  }
   return true;
 }
 
diff --git a/src/build.h b/src/build.h
index f97d67e..43786f1 100644
--- a/src/build.h
+++ b/src/build.h
@@ -75,9 +75,7 @@ struct Plan {
   void Reset();
 
 private:
-  bool AddSubTarget(Node* node, vector<Node*>* stack, string* err);
-  bool CheckDependencyCycle(Node* node, const vector<Node*>& stack,
-                            string* err);
+  bool AddSubTarget(Node* node, Node* dependent, string* err);
   void NodeFinished(Node* node);
 
   /// Submits a ready edge as a candidate for execution.
diff --git a/src/build_test.cc b/src/build_test.cc
index 8c9fb11..a0f898f 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -185,59 +185,6 @@ TEST_F(PlanTest, DoubleDependent) {
   ASSERT_FALSE(edge);  // done
 }
 
-TEST_F(PlanTest, DependencyCycle) {
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build out: cat mid\n"
-"build mid: cat in\n"
-"build in: cat pre\n"
-"build pre: cat out\n"));
-  GetNode("out")->MarkDirty();
-  GetNode("mid")->MarkDirty();
-  GetNode("in")->MarkDirty();
-  GetNode("pre")->MarkDirty();
-
-  string err;
-  EXPECT_FALSE(plan_.AddTarget(GetNode("out"), &err));
-  ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes1) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build a b: cat a\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err));
-  ASSERT_EQ("dependency cycle: a -> a", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes2) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build b a: cat a\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err));
-  ASSERT_EQ("dependency cycle: a -> a", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes3) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build a b: cat c\n"
-"build c: cat a\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err));
-  ASSERT_EQ("dependency cycle: c -> a -> c", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes4) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build d: cat c\n"
-"build c: cat b\n"
-"build b: cat a\n"
-"build a e: cat d\n"
-"build f: cat e\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("f"), &err));
-  ASSERT_EQ("dependency cycle: d -> c -> b -> a -> d", err);
-}
-
 void PlanTest::TestPoolWithDepthOne(const char* test_case) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, test_case));
   GetNode("out1")->MarkDirty();
diff --git a/src/graph_test.cc b/src/graph_test.cc
index b76526f..d4d2824 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -323,6 +323,55 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) {
   ASSERT_FALSE(plan_.more_to_do());
 }
 
+TEST_F(GraphTest, DependencyCycle) {
+  AssertParse(&state_,
+"build out: cat mid\n"
+"build mid: cat in\n"
+"build in: cat pre\n"
+"build pre: cat out\n");
+
+  string err;
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes1) {
+  string err;
+  AssertParse(&state_,
+"build a b: cat a\n");
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  ASSERT_EQ("dependency cycle: a -> a", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes2) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build b a: cat a\n"));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  ASSERT_EQ("dependency cycle: a -> a", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes3) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build a b: cat c\n"
+"build c: cat a\n"));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  ASSERT_EQ("dependency cycle: a -> c -> a", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes4) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build d: cat c\n"
+"build c: cat b\n"
+"build b: cat a\n"
+"build a e: cat d\n"
+"build f: cat e\n"));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), &err));
+  ASSERT_EQ("dependency cycle: a -> d -> c -> b -> a", err);
+}
+
 // 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) {