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.

5 files changed, 46 insertions, 1 deletions

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<Edge*>::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<Node*>::const_iterator in_node = (*e)->inputs_.begin();
+         in_node != (*e)->inputs_.end(); ++in_node) {
+      const vector<Edge*>& 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<Node*>::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