From 29a6e2fc6c671b9490193d4b235b53fb61886c80 Mon Sep 17 00:00:00 2001 From: Brad King Date: Tue, 10 Nov 2015 15:09:47 -0500 Subject: Simplify BuildTest.StatFailureAbortsBuild test case Remove a dependency cycle from the test case, as cycles are covered by other tests. Ensure this case covers stat failure on a valid graph. --- src/build_test.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/build_test.cc b/src/build_test.cc index 623ed14..8c9fb11 100644 --- a/src/build_test.cc +++ b/src/build_test.cc @@ -1747,8 +1747,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; -- cgit v0.12 From afe3beb980a4780caecc12d3fc919feb3f9cce42 Mon Sep 17 00:00:00 2001 From: Brad King Date: Fri, 13 Nov 2015 13:05:51 -0500 Subject: Refactor RecomputeDirty to take a node instead of an edge All call sites have a node on which they call `in_edge()` to call RecomputeDirty. Simplify call sites by taking the node directly and calling `in_edge()` internally. --- src/build.cc | 5 +++-- src/disk_interface_test.cc | 8 ++++---- src/graph.cc | 22 +++++++++++---------- src/graph.h | 3 ++- src/graph_test.cc | 48 +++++++++++++++++----------------------------- 5 files changed, 39 insertions(+), 47 deletions(-) diff --git a/src/build.cc b/src/build.cc index 8f4169b..c2a615a 100644 --- a/src/build.cc +++ b/src/build.cc @@ -640,9 +640,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/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..c34fab8 100644 --- a/src/graph.cc +++ b/src/graph.cc @@ -31,7 +31,16 @@ 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) { + Edge* edge = node->in_edge(); + if (!edge) { + // This node has no in-edge; it is dirty if it is missing. + if (!node->exists()) + EXPLAIN("%s has no in-edge and is missing", node->path().c_str()); + node->set_dirty(!node->exists()); + return true; + } + bool dirty = false; edge->outputs_ready_ = true; edge->deps_missing_ = false; @@ -66,15 +75,8 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { 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()); - } + if (!RecomputeDirty(*i, err)) + return false; } // If an input is not ready, neither are our outputs. diff --git a/src/graph.h b/src/graph.h index ec24293..9e82ca2 100644 --- a/src/graph.h +++ b/src/graph.h @@ -246,11 +246,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. diff --git a/src/graph_test.cc b/src/graph_test.cc index be08b19..87f3430 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_; @@ -347,13 +335,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)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("a"), &err)); ASSERT_EQ("", 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 +360,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)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("a"), &err)); ASSERT_EQ("", 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,7 +387,7 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) { fs_.Create("dep.d", "a: c\n"); string err; - EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d")->in_edge(), &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d"), &err)); ASSERT_EQ("", err); // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b, -- cgit v0.12 From a8b5cdc4e9034f8823ee0cfa94ea49d7795698ab Mon Sep 17 00:00:00 2001 From: Brad King Date: Thu, 12 Nov 2015 11:24:50 -0500 Subject: Add infrastructure for efficient walks through the `Edge` graph Store a mark in each `Edge` to be updated as it is encountered by a walk. --- src/graph.h | 9 ++++++++- src/state.cc | 4 +++- 2 files changed, 11 insertions(+), 2 deletions(-) diff --git a/src/graph.h b/src/graph.h index 9e82ca2..1b30dee 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 inputs_; vector outputs_; BindingEnv* env_; + VisitMark mark_; bool outputs_ready_; bool deps_missing_; 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 State::DefaultNodes(string* err) const { void State::Reset() { for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) i->second->ResetState(); - for (vector::iterator e = edges_.begin(); e != edges_.end(); ++e) + for (vector::iterator e = edges_.begin(); e != edges_.end(); ++e) { (*e)->outputs_ready_ = false; + (*e)->mark_ = Edge::VisitNone; + } } void State::Dump() { -- cgit v0.12 From b6f020d3640988824b1fe4355996ef0726a2c44c Mon Sep 17 00:00:00 2001 From: Brad King Date: Fri, 13 Nov 2015 13:09:11 -0500 Subject: Teach RecomputeDirty to detect cycles in the build graph RecomputeDirty is the earliest traversal of the build graph complete with depfile-loaded dependencies. Teach it to detect cycles and fail immediately. This avoids the need to tolerate cycles in RecomputeDirty only to diagnose them later. It also enables future simplification of Plan and Builder logic because they will be able to assume DAG input. When RecomputeDirty detects a cycle, reject it with an error message like that previously produced by Plan::CheckDependencyCycle. Previously we used the stat state of each node to determine whether we reached it earlier in the walk. Retain this approach for leaf nodes, but add an explicit walk state mark for each Edge so that we can have a temporary mark to aid cycle detection. --- src/graph.cc | 78 +++++++++++++++++++++++++++++++++++++++++++++---------- src/graph.h | 3 +++ src/graph_test.cc | 12 ++++----- 3 files changed, 73 insertions(+), 20 deletions(-) diff --git a/src/graph.cc b/src/graph.cc index c34fab8..7dd9491 100644 --- a/src/graph.cc +++ b/src/graph.cc @@ -32,28 +32,43 @@ bool Node::Stat(DiskInterface* disk_interface, string* err) { } bool DependencyScan::RecomputeDirty(Node* node, string* err) { + vector stack; + return RecomputeDirty(node, &stack, err); +} + +bool DependencyScan::RecomputeDirty(Node* node, vector* 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::iterator o = edge->outputs_.begin(); o != edge->outputs_.end(); ++o) { if (!(*o)->StatIfNecessary(disk_interface_, err)) @@ -72,12 +87,9 @@ bool DependencyScan::RecomputeDirty(Node* node, string* err) { Node* most_recent_input = NULL; for (vector::iterator i = edge->inputs_.begin(); i != edge->inputs_.end(); ++i) { - if (!(*i)->status_known()) { - if (!(*i)->StatIfNecessary(disk_interface_, err)) - return false; - if (!RecomputeDirty(*i, err)) - return false; - } + // 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()) { @@ -120,9 +132,47 @@ bool DependencyScan::RecomputeDirty(Node* node, 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* 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::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::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 1b30dee..586c588 100644 --- a/src/graph.h +++ b/src/graph.h @@ -277,6 +277,9 @@ struct DependencyScan { } private: + bool RecomputeDirty(Node* node, vector* stack, string* err); + bool VerifyDAG(Node* node, vector* 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 87f3430..b76526f 100644 --- a/src/graph_test.cc +++ b/src/graph_test.cc @@ -335,8 +335,8 @@ TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) { fs_.Create("dep.d", "a: b\n"); string err; - EXPECT_TRUE(scan_.RecomputeDirty(GetNode("a"), &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 @@ -360,8 +360,8 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfile) { fs_.Create("dep.d", "a: c\n"); string err; - EXPECT_TRUE(scan_.RecomputeDirty(GetNode("a"), &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 @@ -387,8 +387,8 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) { fs_.Create("dep.d", "a: c\n"); string err; - EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d"), &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 -- cgit v0.12 From 721d2a26b629d8556b73ce051f982967428d0738 Mon Sep 17 00:00:00 2001 From: Brad King Date: Fri, 13 Nov 2015 16:03:16 -0500 Subject: Drop unnecessary cycle detection in Plan::AddTarget We now detect and reject cycles in DependencyScan::RecomputeDirty before Plan::AddTarget is called so we can assume DAG input to the Plan. --- src/build.cc | 49 +++++-------------------------------------------- src/build.h | 4 +--- src/build_test.cc | 53 ----------------------------------------------------- src/graph_test.cc | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ 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 stack; - return AddSubTarget(node, &stack, err); + return AddSubTarget(node, NULL, err); } -bool Plan::AddSubTarget(Node* node, vector* 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* stack, string* err) { if (!want_ins.second) return true; // We've already processed the inputs. - stack->push_back(node); for (vector::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& stack, - string* err) { - vector::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 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::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* stack, string* err); - bool CheckDependencyCycle(Node* node, const vector& 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) { -- cgit v0.12