summaryrefslogtreecommitdiffstats
path: root/src/graph_test.cc
diff options
context:
space:
mode:
authorNico Weber <nicolasweber@gmx.de>2014-12-08 00:02:35 (GMT)
committerNico Weber <nicolasweber@gmx.de>2014-12-08 00:20:24 (GMT)
commit015c818cbe85093316115c5a510274eccdb4180b (patch)
treec614fbaf19e47e84aa625b5ccc4533677d8b65a0 /src/graph_test.cc
parenta9dac57ecad0b8ff4822c39446e9bf35afc0a615 (diff)
downloadNinja-015c818cbe85093316115c5a510274eccdb4180b.zip
Ninja-015c818cbe85093316115c5a510274eccdb4180b.tar.gz
Ninja-015c818cbe85093316115c5a510274eccdb4180b.tar.bz2
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)
Diffstat (limited to 'src/graph_test.cc')
-rw-r--r--src/graph_test.cc75
1 files changed, 75 insertions, 0 deletions
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_,