From f5c5789aad8001e15a7e4f1ee0dee0c2b688e993 Mon Sep 17 00:00:00 2001
From: Nico Weber <nicolasweber@gmx.de>
Date: Thu, 19 Mar 2015 16:42:06 -0700
Subject: Another crash fix for duplicate edges. Fixes #939.

Patch #933 fixed a crash with duplicate edges by not adding edges to the
graph if all the edge's outputs are already built by other edges.
However, it added the edge to the out_edges of the edge's input nodes
before deleting it, letting inputs refer to dead edges.

To fix, move the check for deleting an edge above the code that adds
inputs.  Expand VerifyGraph() to check that nodes don't refer to edges
that aren't present in the state.
---
 src/manifest_parser.cc      | 24 ++++++++++++------------
 src/manifest_parser_test.cc | 11 +++++++++++
 src/state.cc                |  1 +
 src/test.cc                 | 16 ++++++++++++++--
 4 files changed, 38 insertions(+), 14 deletions(-)

diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc
index f0457dd..4e639d1 100644
--- a/src/manifest_parser.cc
+++ b/src/manifest_parser.cc
@@ -321,14 +321,6 @@ bool ManifestParser::ParseEdge(string* err) {
     edge->pool_ = pool;
   }
 
-  for (vector<EvalString>::iterator i = ins.begin(); i != ins.end(); ++i) {
-    string path = i->Evaluate(env);
-    string path_err;
-    unsigned int slash_bits;
-    if (!CanonicalizePath(&path, &slash_bits, &path_err))
-      return lexer_.Error(path_err, err);
-    state_->AddIn(edge, path, slash_bits);
-  }
   for (vector<EvalString>::iterator i = outs.begin(); i != outs.end(); ++i) {
     string path = i->Evaluate(env);
     string path_err;
@@ -337,17 +329,25 @@ bool ManifestParser::ParseEdge(string* err) {
       return lexer_.Error(path_err, err);
     state_->AddOut(edge, path, slash_bits);
   }
-  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.
+    // this edge.  Do this check before input nodes are connected to the edge.
     state_->edges_.pop_back();
     delete edge;
     return true;
   }
 
+  for (vector<EvalString>::iterator i = ins.begin(); i != ins.end(); ++i) {
+    string path = i->Evaluate(env);
+    string path_err;
+    unsigned int slash_bits;
+    if (!CanonicalizePath(&path, &slash_bits, &path_err))
+      return lexer_.Error(path_err, err);
+    state_->AddIn(edge, path, slash_bits);
+  }
+  edge->implicit_deps_ = implicit;
+  edge->order_only_deps_ = order_only;
+
   // 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 7e38fc6..7e72b34 100644
--- a/src/manifest_parser_test.cc
+++ b/src/manifest_parser_test.cc
@@ -353,6 +353,17 @@ TEST_F(ParserTest, DuplicateEdgeWithMultipleOutputs) {
   // That's all the checking that this test needs.
 }
 
+TEST_F(ParserTest, NoDeadPointerFromDuplicateEdge) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"rule cat\n"
+"  command = cat $in > $out\n"
+"build out: cat in\n"
+"build out: cat in\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 18c0c8c..0426b85 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -61,6 +61,7 @@ void Pool::Dump() const {
   }
 }
 
+// static
 bool Pool::WeightedEdgeCmp(const Edge* a, const Edge* b) {
   if (!a) return b;
   if (!b) return false;
diff --git a/src/test.cc b/src/test.cc
index 76b8416..ddecd3d 100644
--- a/src/test.cc
+++ b/src/test.cc
@@ -111,19 +111,31 @@ void VerifyGraph(const State& state) {
        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.
+    // 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.
+    // 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);
     }
   }
+
+  // The union of all in- and out-edges of each nodes should be exactly edges_.
+  set<const Edge*> node_edge_set;
+  for (State::Paths::const_iterator p = state.paths_.begin();
+       p != state.paths_.end(); ++p) {
+    const Node* n = p->second;
+    if (n->in_edge())
+      node_edge_set.insert(n->in_edge());
+    node_edge_set.insert(n->out_edges().begin(), n->out_edges().end());
+  }
+  set<const Edge*> edge_set(state.edges_.begin(), state.edges_.end());
+  EXPECT_EQ(node_edge_set, edge_set);
 }
 
 void VirtualFileSystem::Create(const string& path,
-- 
cgit v0.12