Don't get stuck on cyclic graphs where one edge has multiple outputs.

Fixes #934. Plan::AddSubTarget() tracks in want_ if each edge has been
visited and visits every edge only once.  But Plan::CheckDependencyCycle()
worked on nodes however, so if a cycle was entered through an edge with
multiple outputs, ninja would fail to detect that cycle.

Move cycle detection to look for duplicate edges instead of nodes to fix
this.  The extra jump makes CheckDependencyCycle() a bit slower: for a
synthetic build file with 10000 serial build steps, `ninja -n` now takes
0.32s instead of 0.26s before on my laptop.  In practice, projects have
a dependency change length on the order of 50, so there shouldn't be a
noticeable slowdown in practice.  (If this does end up being a problem:
CheckDependencyCycle() currently does O(n) work and is called O(m) times
from AddSubTarget(), so I think cycle checking is O(n^2) in the build
depth.  So instead of worrying about constant overhead, we could use
a set<> instead of a stack<>.  But it doesn't seem to be a problem in
practice.)

2 files changed, 58 insertions, 4 deletions

diff --git a/src/build.cc b/src/build.cc
index 9f40d2d..ccdb37f 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -318,16 +318,33 @@ bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) {
 
 bool Plan::CheckDependencyCycle(Node* node, const vector<Node*>& stack,
                                 string* err) {
-  vector<Node*>::const_iterator start = find(stack.begin(), stack.end(), node);
+  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 = start; i != stack.end(); ++i) {
+  for (vector<Node*>::const_iterator i = cycle.begin(); i != cycle.end(); ++i) {
+    if (i != cycle.begin())
+      err->append(" -> ");
     err->append((*i)->path());
-    err->append(" -> ");
   }
-  err->append(node->path());
   return true;
 }
 
diff --git a/src/build_test.cc b/src/build_test.cc
index 13d1e7e..a313693 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -201,6 +201,43 @@ TEST_F(PlanTest, DependencyCycle) {
   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();