From 90e3504154c15c70e704f3660d97e1397dc1e08e Mon Sep 17 00:00:00 2001
From: Evan Martin <martine@danga.com>
Date: Fri, 3 Dec 2010 19:01:18 -0800
Subject: [PATCH] cleanup cycle checking

---
 build.cc      | 37 +++++++++++++++++++++----------------
 build.h       |  1 +
 build_test.cc |  4 ++--
 3 files changed, 24 insertions(+), 18 deletions(-)

diff --git a/build.cc b/build.cc
index 4206221..4a155f9 100644
--- a/build.cc
+++ b/build.cc
@@ -21,23 +21,8 @@ bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) {
   }
   assert(edge);
 
-  // Check for a dependency cycle.
-  vector<Node*>::reverse_iterator i =
-      find(stack->rbegin(), stack->rend(), node);
-  if (i != stack->rend()) {
-    // Add this node onto the stack to make it clearer where the loop
-    // is.
-    stack->push_back(node);
-
-    vector<Node*>::iterator i =
-        find(stack->begin(), stack->end(), node);
-    for (; i != stack->end(); ++i) {
-      if (!err->empty())
-        err->append(" -> ");
-      err->append((*i)->file_->path_);
-    }
+  if (CheckDependencyCycle(node, stack, err))
     return false;
-  }
 
   if (!node->dirty())
     return false;  // Don't need to do anything.
@@ -63,6 +48,26 @@ bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) {
   return true;
 }
 
+bool Plan::CheckDependencyCycle(Node* node, vector<Node*>* stack, string* err) {
+  vector<Node*>::reverse_iterator ri =
+      find(stack->rbegin(), stack->rend(), node);
+  if (ri == stack->rend())
+    return false;
+
+  // Add this node onto the stack to make it clearer where the loop
+  // is.
+  stack->push_back(node);
+
+  vector<Node*>::iterator start = find(stack->begin(), stack->end(), node);
+  *err = "dependency cycle: ";
+  for (vector<Node*>::iterator i = start; i != stack->end(); ++i) {
+    if (i != start)
+      err->append(" -> ");
+    err->append((*i)->file_->path_);
+  }
+  return true;
+}
+
 Edge* Plan::FindWork() {
   if (ready_.empty())
     return NULL;
diff --git a/build.h b/build.h
index 7fef9f7..41df8ba 100644
--- a/build.h
+++ b/build.h
@@ -36,6 +36,7 @@ struct Plan {
 
 private:
   bool AddSubTarget(Node* node, vector<Node*>* stack, string* err);
+  bool CheckDependencyCycle(Node* node, vector<Node*>* stack, string* err);
   void NodeFinished(Node* node);
 
   set<Edge*> want_;
diff --git a/build_test.cc b/build_test.cc
index a6eaa54..26d1080 100644
--- a/build_test.cc
+++ b/build_test.cc
@@ -145,7 +145,7 @@ TEST_F(PlanTest, DoubleDependent) {
   ASSERT_FALSE(edge);  // done
 }
 
-TEST_F(PlanTest, DependencyLoop) {
+TEST_F(PlanTest, DependencyCycle) {
   AssertParse(&state_,
 "build out: cat mid\n"
 "build mid: cat in\n"
@@ -154,7 +154,7 @@ TEST_F(PlanTest, DependencyLoop) {
   GetNode("pre")->MarkDependentsDirty();
   string err;
   EXPECT_FALSE(plan_.AddTarget(GetNode("out"), &err));
-  ASSERT_EQ("out -> mid -> in -> pre -> out", err);
+  ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
 }
 
 struct BuildTest : public StateTestWithBuiltinRules,
-- 
2.7.4