From 56e9d08c028d2c16f787041dc1f41271464a8bdc Mon Sep 17 00:00:00 2001 From: Nico Weber Date: Sun, 15 Mar 2015 19:34:03 -0400 Subject: [PATCH] Build self-consistent graphs for dupe edges with multiple outputs. Fixes #867, both the crashes and "[stuck]" issues. The problem was that a duplicate edge would modify the in_edge of the outputs of the new build rule, but the edge corresponding to the old build rule would still think that the in_edge points to itself. `old_edge->outputs_[0]->in_edge()` would not return `old_edge`, which confused the scan logic. As fix, let `State::AddOut()` reject changing in_edge if it's already set. This changes behavior in a minor way: Previously, if there were multiple edges for a single output, the last edge would be kept. Now, the first edge is kept. This only had mostly-well-defined semantics if all duplicate edges are the same (which is the only case I've seen in practice), and for that case the behavior doesn't change. For testing, add a VerifyGraph() function and call that every time any test graph is parsed. That's a bit more code than just copying the test cases from the bug into build_test.cc, but it also yields better test coverage overall. --- src/manifest_parser.cc | 8 ++++++++ src/manifest_parser_test.cc | 13 +++++++++++++ src/state.cc | 3 ++- src/test.cc | 22 ++++++++++++++++++++++ src/test.h | 1 + 5 files changed, 46 insertions(+), 1 deletion(-) diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc index 044b259..f0457dd 100644 --- a/src/manifest_parser.cc +++ b/src/manifest_parser.cc @@ -340,6 +340,14 @@ bool ManifestParser::ParseEdge(string* err) { edge->implicit_deps_ = implicit; edge->order_only_deps_ = order_only; + if (edge->outputs_.empty()) { + // All outputs of the edge are already created by other edges. Don't add + // this edge. + state_->edges_.pop_back(); + delete edge; + return true; + } + // Multiple outputs aren't (yet?) supported with depslog. string deps_type = edge->GetBinding("deps"); if (!deps_type.empty() && edge->outputs_.size() > 1) { diff --git a/src/manifest_parser_test.cc b/src/manifest_parser_test.cc index e13d728..7e38fc6 100644 --- a/src/manifest_parser_test.cc +++ b/src/manifest_parser_test.cc @@ -28,6 +28,7 @@ struct ParserTest : public testing::Test, string err; EXPECT_TRUE(parser.ParseTest(input, &err)); ASSERT_EQ("", err); + VerifyGraph(state); } virtual bool ReadFile(const string& path, string* content, string* err) { @@ -340,6 +341,18 @@ TEST_F(ParserTest, CanonicalizePathsBackslashes) { } #endif +TEST_F(ParserTest, DuplicateEdgeWithMultipleOutputs) { + ASSERT_NO_FATAL_FAILURE(AssertParse( +"rule cat\n" +" command = cat $in > $out\n" +"build out1 out2: cat in1\n" +"build out1: cat in2\n" +"build final: cat out1\n" +)); + // AssertParse() checks that the generated build graph is self-consistent. + // That's all the checking that this test needs. +} + TEST_F(ParserTest, ReservedWords) { ASSERT_NO_FATAL_FAILURE(AssertParse( "rule build\n" diff --git a/src/state.cc b/src/state.cc index 89f90c0..18c0c8c 100644 --- a/src/state.cc +++ b/src/state.cc @@ -141,13 +141,14 @@ void State::AddIn(Edge* edge, StringPiece path, unsigned int slash_bits) { void State::AddOut(Edge* edge, StringPiece path, unsigned int slash_bits) { Node* node = GetNode(path, slash_bits); - edge->outputs_.push_back(node); if (node->in_edge()) { Warning("multiple rules generate %s. " "builds involving this target will not be correct; " "continuing anyway", path.AsString().c_str()); + return; } + edge->outputs_.push_back(node); node->set_in_edge(edge); } diff --git a/src/test.cc b/src/test.cc index f667fef..76b8416 100644 --- a/src/test.cc +++ b/src/test.cc @@ -28,6 +28,7 @@ #endif #include "build_log.h" +#include "graph.h" #include "manifest_parser.h" #include "util.h" @@ -98,12 +99,33 @@ void AssertParse(State* state, const char* input) { string err; EXPECT_TRUE(parser.ParseTest(input, &err)); ASSERT_EQ("", err); + VerifyGraph(*state); } void AssertHash(const char* expected, uint64_t actual) { ASSERT_EQ(BuildLog::LogEntry::HashCommand(expected), actual); } +void VerifyGraph(const State& state) { + for (vector::const_iterator e = state.edges_.begin(); + e != state.edges_.end(); ++e) { + // All edges need at least one output. + EXPECT_FALSE((*e)->outputs_.empty()); + // Check that the edge's inputs have the edge as out edge. + for (vector::const_iterator in_node = (*e)->inputs_.begin(); + in_node != (*e)->inputs_.end(); ++in_node) { + const vector& out_edges = (*in_node)->out_edges(); + EXPECT_NE(std::find(out_edges.begin(), out_edges.end(), *e), + out_edges.end()); + } + // Check that the edge's outputs have the edge as in edge. + for (vector::const_iterator out_node = (*e)->outputs_.begin(); + out_node != (*e)->outputs_.end(); ++out_node) { + EXPECT_EQ((*out_node)->in_edge(), *e); + } + } +} + void VirtualFileSystem::Create(const string& path, const string& contents) { files_[path].mtime = now_; diff --git a/src/test.h b/src/test.h index 4c15203..3ce510d 100644 --- a/src/test.h +++ b/src/test.h @@ -124,6 +124,7 @@ struct StateTestWithBuiltinRules : public testing::Test { void AssertParse(State* state, const char* input); void AssertHash(const char* expected, uint64_t actual); +void VerifyGraph(const State& state); /// An implementation of DiskInterface that uses an in-memory representation /// of disk state. It also logs file accesses and directory creations -- 2.7.4