summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/build.cc49
-rw-r--r--src/build.h4
-rw-r--r--src/build_test.cc53
-rw-r--r--src/graph_test.cc49
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) {
generated by cgit v0.12 at 2024-11-15 20:03:05 (GMT)