diff options
author | Nico Weber <nicolasweber@gmx.de> | 2017-06-22 19:59:00 (GMT) |
---|---|---|
committer | GitHub <noreply@github.com> | 2017-06-22 19:59:00 (GMT) |
commit | 7bbc708ff08f5660f4cff4b3e8c675bec428a1f2 (patch) | |
tree | 684fc7d5bc97e97a15bd8aab5c27c1680aa2ab4e /src | |
parent | 61e347ed4e1c7681b6fd2888880ec0546907e9af (diff) | |
parent | 721d2a26b629d8556b73ce051f982967428d0738 (diff) | |
download | Ninja-7bbc708ff08f5660f4cff4b3e8c675bec428a1f2.zip Ninja-7bbc708ff08f5660f4cff4b3e8c675bec428a1f2.tar.gz Ninja-7bbc708ff08f5660f4cff4b3e8c675bec428a1f2.tar.bz2 |
Merge pull request #1111 from bradking/detect-cycles-early
Detect build graph cycles as early as possible
Diffstat (limited to 'src')
-rw-r--r-- | src/build.cc | 54 | ||||
-rw-r--r-- | src/build.h | 4 | ||||
-rw-r--r-- | src/build_test.cc | 57 | ||||
-rw-r--r-- | src/disk_interface_test.cc | 8 | ||||
-rw-r--r-- | src/graph.cc | 96 | ||||
-rw-r--r-- | src/graph.h | 15 | ||||
-rw-r--r-- | src/graph_test.cc | 103 | ||||
-rw-r--r-- | src/state.cc | 4 |
8 files changed, 175 insertions, 166 deletions
diff --git a/src/build.cc b/src/build.cc index 8f4169b..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,50 +337,15 @@ 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; -} - Edge* Plan::FindWork() { if (ready_.empty()) return NULL; @@ -640,9 +601,10 @@ Node* Builder::AddTarget(const string& name, string* err) { } bool Builder::AddTarget(Node* node, string* err) { + if (!scan_.RecomputeDirty(node, err)) + return false; + if (Edge* in_edge = node->in_edge()) { - if (!scan_.RecomputeDirty(in_edge, err)) - return false; if (in_edge->outputs_ready()) return true; // Nothing to do. } 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 623ed14..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(); @@ -1747,8 +1694,8 @@ TEST_F(BuildTest, InterruptCleanup) { TEST_F(BuildTest, StatFailureAbortsBuild) { const string kTooLongToStat(400, 'i'); ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, -("build " + kTooLongToStat + ": cat " + kTooLongToStat + "\n").c_str())); - // Also cyclic, for good measure. +("build " + kTooLongToStat + ": cat in\n").c_str())); + fs_.Create("in", ""); // This simulates a stat failure: fs_.files_[kTooLongToStat].mtime = -1; diff --git a/src/disk_interface_test.cc b/src/disk_interface_test.cc index 7187bdf..d7fb8f8 100644 --- a/src/disk_interface_test.cc +++ b/src/disk_interface_test.cc @@ -245,7 +245,7 @@ TEST_F(StatTest, Simple) { EXPECT_TRUE(out->Stat(this, &err)); EXPECT_EQ("", err); ASSERT_EQ(1u, stats_.size()); - scan_.RecomputeDirty(out->in_edge(), NULL); + scan_.RecomputeDirty(out, NULL); ASSERT_EQ(2u, stats_.size()); ASSERT_EQ("out", stats_[0]); ASSERT_EQ("in", stats_[1]); @@ -261,7 +261,7 @@ TEST_F(StatTest, TwoStep) { EXPECT_TRUE(out->Stat(this, &err)); EXPECT_EQ("", err); ASSERT_EQ(1u, stats_.size()); - scan_.RecomputeDirty(out->in_edge(), NULL); + scan_.RecomputeDirty(out, NULL); ASSERT_EQ(3u, stats_.size()); ASSERT_EQ("out", stats_[0]); ASSERT_TRUE(GetNode("out")->dirty()); @@ -281,7 +281,7 @@ TEST_F(StatTest, Tree) { EXPECT_TRUE(out->Stat(this, &err)); EXPECT_EQ("", err); ASSERT_EQ(1u, stats_.size()); - scan_.RecomputeDirty(out->in_edge(), NULL); + scan_.RecomputeDirty(out, NULL); ASSERT_EQ(1u + 6u, stats_.size()); ASSERT_EQ("mid1", stats_[1]); ASSERT_TRUE(GetNode("mid1")->dirty()); @@ -302,7 +302,7 @@ TEST_F(StatTest, Middle) { EXPECT_TRUE(out->Stat(this, &err)); EXPECT_EQ("", err); ASSERT_EQ(1u, stats_.size()); - scan_.RecomputeDirty(out->in_edge(), NULL); + scan_.RecomputeDirty(out, NULL); ASSERT_FALSE(GetNode("in")->dirty()); ASSERT_TRUE(GetNode("mid")->dirty()); ASSERT_TRUE(GetNode("out")->dirty()); diff --git a/src/graph.cc b/src/graph.cc index c90aaad..7dd9491 100644 --- a/src/graph.cc +++ b/src/graph.cc @@ -31,20 +31,44 @@ bool Node::Stat(DiskInterface* disk_interface, string* err) { return (mtime_ = disk_interface->Stat(path_, err)) != -1; } -bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { +bool DependencyScan::RecomputeDirty(Node* node, string* err) { + vector<Node*> stack; + return RecomputeDirty(node, &stack, err); +} + +bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack, + string* err) { + Edge* edge = node->in_edge(); + if (!edge) { + // If we already visited this leaf node then we are done. + if (node->status_known()) + return true; + // This node has no in-edge; it is dirty if it is missing. + if (!node->StatIfNecessary(disk_interface_, err)) + return false; + if (!node->exists()) + EXPLAIN("%s has no in-edge and is missing", node->path().c_str()); + node->set_dirty(!node->exists()); + return true; + } + + // If we already finished this edge then we are done. + if (edge->mark_ == Edge::VisitDone) + return true; + + // If we encountered this edge earlier in the call stack we have a cycle. + if (!VerifyDAG(node, stack, err)) + return false; + + // Mark the edge temporarily while in the call stack. + edge->mark_ = Edge::VisitInStack; + stack->push_back(node); + bool dirty = false; edge->outputs_ready_ = true; edge->deps_missing_ = false; // Load output mtimes so we can compare them to the most recent input below. - // RecomputeDirty() recursively walks the graph following the input nodes - // of |edge| and the in_edges of these nodes. It uses the stat state of each - // node to mark nodes as visited and doesn't traverse across nodes that have - // been visited already. To make sure that every edge is visited only once - // (important because an edge's deps are loaded every time it's visited), mark - // all outputs of |edge| visited as a first step. This ensures that edges - // with multiple inputs and outputs are visited only once, even in cyclic - // graphs. for (vector<Node*>::iterator o = edge->outputs_.begin(); o != edge->outputs_.end(); ++o) { if (!(*o)->StatIfNecessary(disk_interface_, err)) @@ -63,19 +87,9 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { Node* most_recent_input = NULL; for (vector<Node*>::iterator i = edge->inputs_.begin(); i != edge->inputs_.end(); ++i) { - if (!(*i)->status_known()) { - if (!(*i)->StatIfNecessary(disk_interface_, err)) - return false; - if (Edge* in_edge = (*i)->in_edge()) { - if (!RecomputeDirty(in_edge, err)) - return false; - } else { - // This input has no in-edge; it is dirty if it is missing. - if (!(*i)->exists()) - EXPLAIN("%s has no in-edge and is missing", (*i)->path().c_str()); - (*i)->set_dirty(!(*i)->exists()); - } - } + // Visit this input. + if (!RecomputeDirty(*i, stack, err)) + return false; // If an input is not ready, neither are our outputs. if (Edge* in_edge = (*i)->in_edge()) { @@ -118,9 +132,47 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { if (dirty && !(edge->is_phony() && edge->inputs_.empty())) edge->outputs_ready_ = false; + // Mark the edge as finished during this walk now that it will no longer + // be in the call stack. + edge->mark_ = Edge::VisitDone; + assert(stack->back() == node); + stack->pop_back(); + return true; } +bool DependencyScan::VerifyDAG(Node* node, vector<Node*>* stack, string* err) { + Edge* edge = node->in_edge(); + assert(edge != NULL); + + // If we have no temporary mark on the edge then we do not yet have a cycle. + if (edge->mark_ != Edge::VisitInStack) + return true; + + // We have this edge earlier in the call stack. Find it. + vector<Node*>::iterator start = stack->begin(); + while (start != stack->end() && (*start)->in_edge() != edge) + ++start; + assert(start != stack->end()); + + // Make the cycle clear by reporting its start as the node at its end + // instead of some other output of the starting edge. For example, + // running 'ninja b' on + // build a b: cat c + // build c: cat a + // should report a -> c -> a instead of b -> c -> a. + *start = node; + + // Construct the error message rejecting the cycle. + *err = "dependency cycle: "; + for (vector<Node*>::const_iterator i = start; i != stack->end(); ++i) { + err->append((*i)->path()); + err->append(" -> "); + } + err->append((*start)->path()); + return false; +} + bool DependencyScan::RecomputeOutputsDirty(Edge* edge, Node* most_recent_input, bool* outputs_dirty, string* err) { string command = edge->EvaluateCommand(/*incl_rsp_file=*/true); diff --git a/src/graph.h b/src/graph.h index ec24293..586c588 100644 --- a/src/graph.h +++ b/src/graph.h @@ -128,7 +128,13 @@ private: /// An edge in the dependency graph; links between Nodes using Rules. struct Edge { - Edge() : rule_(NULL), pool_(NULL), env_(NULL), + enum VisitMark { + VisitNone, + VisitInStack, + VisitDone + }; + + Edge() : rule_(NULL), pool_(NULL), env_(NULL), mark_(VisitNone), outputs_ready_(false), deps_missing_(false), implicit_deps_(0), order_only_deps_(0), implicit_outs_(0) {} @@ -156,6 +162,7 @@ struct Edge { vector<Node*> inputs_; vector<Node*> outputs_; BindingEnv* env_; + VisitMark mark_; bool outputs_ready_; bool deps_missing_; @@ -246,11 +253,12 @@ struct DependencyScan { disk_interface_(disk_interface), dep_loader_(state, deps_log, disk_interface) {} + /// Update the |dirty_| state of the given node by inspecting its input edge. /// Examine inputs, outputs, and command lines to judge whether an edge /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_| /// state accordingly. /// Returns false on failure. - bool RecomputeDirty(Edge* edge, string* err); + bool RecomputeDirty(Node* node, string* err); /// Recompute whether any output of the edge is dirty, if so sets |*dirty|. /// Returns false on failure. @@ -269,6 +277,9 @@ struct DependencyScan { } private: + bool RecomputeDirty(Node* node, vector<Node*>* stack, string* err); + bool VerifyDAG(Node* node, vector<Node*>* stack, string* err); + /// Recompute whether a given single output should be marked dirty. /// Returns true if so. bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input, diff --git a/src/graph_test.cc b/src/graph_test.cc index be08b19..d4d2824 100644 --- a/src/graph_test.cc +++ b/src/graph_test.cc @@ -30,9 +30,8 @@ TEST_F(GraphTest, MissingImplicit) { fs_.Create("in", ""); fs_.Create("out", ""); - Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err)); ASSERT_EQ("", err); // A missing implicit dep *should* make the output dirty. @@ -49,9 +48,8 @@ TEST_F(GraphTest, ModifiedImplicit) { fs_.Tick(); fs_.Create("implicit", ""); - Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err)); ASSERT_EQ("", err); // A modified implicit dep should make the output dirty. @@ -70,9 +68,8 @@ TEST_F(GraphTest, FunkyMakefilePath) { fs_.Tick(); fs_.Create("implicit.h", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); // implicit.h has changed, though our depfile refers to it with a @@ -94,9 +91,8 @@ TEST_F(GraphTest, ExplicitImplicit) { fs_.Tick(); fs_.Create("data", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); // We have both an implicit and an explicit dep on implicit.h. @@ -123,9 +119,8 @@ TEST_F(GraphTest, ImplicitOutputMissing) { fs_.Create("in", ""); fs_.Create("out", ""); - Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out")->dirty()); @@ -140,9 +135,8 @@ TEST_F(GraphTest, ImplicitOutputOutOfDate) { fs_.Create("in", ""); fs_.Create("out", ""); - Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out")->dirty()); @@ -165,9 +159,8 @@ TEST_F(GraphTest, ImplicitOutputOnlyMissing) { "build | out.imp: cat in\n")); fs_.Create("in", ""); - Edge* edge = GetNode("out.imp")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out.imp")->dirty()); @@ -180,9 +173,8 @@ TEST_F(GraphTest, ImplicitOutputOnlyOutOfDate) { fs_.Tick(); fs_.Create("in", ""); - Edge* edge = GetNode("out.imp")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out.imp")->dirty()); @@ -198,9 +190,8 @@ TEST_F(GraphTest, PathWithCurrentDirectory) { fs_.Create("out.o.d", "out.o: foo.cc\n"); fs_.Create("out.o", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); EXPECT_FALSE(GetNode("out.o")->dirty()); @@ -247,9 +238,8 @@ TEST_F(GraphTest, DepfileWithCanonicalizablePath) { fs_.Create("out.o.d", "out.o: bar/../foo.cc\n"); fs_.Create("out.o", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); EXPECT_FALSE(GetNode("out.o")->dirty()); @@ -268,15 +258,14 @@ TEST_F(GraphTest, DepfileRemoved) { fs_.Create("out.o.d", "out.o: foo.h\n"); fs_.Create("out.o", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); EXPECT_FALSE(GetNode("out.o")->dirty()); state_.Reset(); fs_.RemoveFile("out.o.d"); - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out.o")->dirty()); } @@ -323,8 +312,7 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) { "build n2: phony n1\n" ); string err; - Edge* edge = GetNode("n2")->in_edge(); - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), &err)); ASSERT_EQ("", err); Plan plan_; @@ -335,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) { @@ -347,13 +384,13 @@ TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) { fs_.Create("dep.d", "a: b\n"); string err; - Edge* edge = GetNode("a")->in_edge(); - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); - ASSERT_EQ("", err); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err)); + ASSERT_EQ("dependency cycle: b -> b", err); // Despite the depfile causing edge to be a cycle (it has outputs a and b, // but the depfile also adds b as an input), the deps should have been loaded // only once: + Edge* edge = GetNode("a")->in_edge(); EXPECT_EQ(1, edge->inputs_.size()); EXPECT_EQ("b", edge->inputs_[0]->path()); } @@ -372,13 +409,13 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfile) { fs_.Create("dep.d", "a: c\n"); string err; - Edge* edge = GetNode("a")->in_edge(); - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); - ASSERT_EQ("", err); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err)); + ASSERT_EQ("dependency cycle: b -> c -> b", err); // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b, // but c's in_edge has b as input but the depfile also adds |edge| as // output)), the deps should have been loaded only once: + Edge* edge = GetNode("a")->in_edge(); EXPECT_EQ(1, edge->inputs_.size()); EXPECT_EQ("c", edge->inputs_[0]->path()); } @@ -399,8 +436,8 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) { fs_.Create("dep.d", "a: c\n"); string err; - EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d")->in_edge(), &err)); - ASSERT_EQ("", err); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), &err)); + ASSERT_EQ("dependency cycle: b -> c -> b", err); // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b, // but c's in_edge has b as input but the depfile also adds |edge| as diff --git a/src/state.cc b/src/state.cc index 6079229..9b3c7e1 100644 --- a/src/state.cc +++ b/src/state.cc @@ -184,8 +184,10 @@ vector<Node*> State::DefaultNodes(string* err) const { void State::Reset() { for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) i->second->ResetState(); - for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) + for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) { (*e)->outputs_ready_ = false; + (*e)->mark_ = Edge::VisitNone; + } } void State::Dump() { |