Merge pull request #951 from nico/cyclefix2

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

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();