From 015c818cbe85093316115c5a510274eccdb4180b Mon Sep 17 00:00:00 2001 From: Nico Weber Date: Sun, 7 Dec 2014 16:02:35 -0800 Subject: Let DependencyScan::RecomputeDirty() work correclty with cyclic graphs. RecomputDirty(edge) currently works roughly like this: RecomputeDirty(edge): LoadDeps(edge) for in in edge.inputs: if in.StatIfNecessary(): RecomputeDirty(in.in_edge) # recurse into inputs for out in edge.outputs: out.StatIfNecessary() # mark outputs as visited It uses the stat state of each node to mark nodes as visited and doesn't traverse across nodes that have been visited already. For cyclic graphs with an edge with multiple outputs on the cycle, nothing prevents an edge to be visited more than once if the cycle is entered through an output that isn't on the cycle. In other words, RecomputeDirty() for the same edge can be on the call stack more than once. This is bad for at least two reasons: 1. Deps are added multiple times, making the graph confusing to reason about. 2. LoadDeps() will insert into the inputs_ of an edge that's iterated over in a callframe higher up. This can invalidate the iterator, which causes a crash when the callframe with the loop over the now-invalidated iterator resumes. To fix this, let RecomputeDirty() mark all outputs of an edge as visited as the first thing it does. This way, even if the edge is on a cycle with several outputs, each output is already marked and no edge will have its deps loaded more than once. Fixes the crashes in #875. (In practice, it turns the crashes into "stuck [this is a bug]" messages for now, due to the example without duplicate rules in #867) --- src/build.cc | 1 - src/graph.cc | 17 ++++++++++--- src/graph_test.cc | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 89 insertions(+), 4 deletions(-) diff --git a/src/build.cc b/src/build.cc index ba2f93d..5d66f4b 100644 --- a/src/build.cc +++ b/src/build.cc @@ -576,7 +576,6 @@ Node* Builder::AddTarget(const string& name, string* err) { } bool Builder::AddTarget(Node* node, string* err) { - node->StatIfNecessary(disk_interface_); if (Edge* in_edge = node->in_edge()) { if (!scan_.RecomputeDirty(in_edge, err)) return false; diff --git a/src/graph.cc b/src/graph.cc index 57f790c..44eca3c 100644 --- a/src/graph.cc +++ b/src/graph.cc @@ -62,6 +62,19 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { edge->outputs_ready_ = true; edge->deps_missing_ = false; + // 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) { + (*o)->StatIfNecessary(disk_interface_); + } + if (!dep_loader_.LoadDeps(edge, err)) { if (!err->empty()) return false; @@ -110,11 +123,9 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { if (!dirty) dirty = RecomputeOutputsDirty(edge, most_recent_input); - // Finally, visit each output to mark off that we've visited it, and update - // their dirty state if necessary. + // Finally, visit each output and update their dirty state if necessary. for (vector::iterator o = edge->outputs_.begin(); o != edge->outputs_.end(); ++o) { - (*o)->StatIfNecessary(disk_interface_); if (dirty) (*o)->MarkDirty(); } diff --git a/src/graph_test.cc b/src/graph_test.cc index 382d352..e41f5cc 100644 --- a/src/graph_test.cc +++ b/src/graph_test.cc @@ -252,6 +252,81 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) { ASSERT_FALSE(plan_.more_to_do()); } +// 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) { + AssertParse(&state_, +"rule deprule\n" +" depfile = dep.d\n" +" command = unused\n" +"build a b: deprule\n" + ); + fs_.Create("dep.d", "a: b\n"); + + string err; + Edge* edge = GetNode("a")->in_edge(); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &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: + EXPECT_EQ(1, edge->inputs_.size()); + EXPECT_EQ("b", edge->inputs_[0]->path()); +} + +// Like CycleWithLengthZeroFromDepfile but with a higher cycle length. +TEST_F(GraphTest, CycleWithLengthOneFromDepfile) { + AssertParse(&state_, +"rule deprule\n" +" depfile = dep.d\n" +" command = unused\n" +"rule r\n" +" command = unused\n" +"build a b: deprule\n" +"build c: r b\n" + ); + fs_.Create("dep.d", "a: c\n"); + + string err; + Edge* edge = GetNode("a")->in_edge(); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &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: + EXPECT_EQ(1, edge->inputs_.size()); + EXPECT_EQ("c", edge->inputs_[0]->path()); +} + +// Like CycleWithLengthOneFromDepfile but building a node one hop away from +// the cycle. +TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) { + AssertParse(&state_, +"rule deprule\n" +" depfile = dep.d\n" +" command = unused\n" +"rule r\n" +" command = unused\n" +"build a b: deprule\n" +"build c: r b\n" +"build d: r a\n" + ); + fs_.Create("dep.d", "a: c\n"); + + string err; + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d")->in_edge(), &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()); +} + #ifdef _WIN32 TEST_F(GraphTest, Decanonicalize) { ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, -- cgit v0.12