Merge pull request #521 from riannucci/ignore_duplicate_edges_in_shcedule_work

Fix duplicate edge Pool crash in the minimally invasive way

4 files changed, 99 insertions, 7 deletions

diff --git a/src/build.cc b/src/build.cc
index 1e3ad9e..ae47a50 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -425,6 +425,12 @@ Edge* Plan::FindWork() {
 void Plan::ScheduleWork(Edge* edge) {
   Pool* pool = edge->pool();
   if (pool->ShouldDelayEdge()) {
+    // The graph is not completely clean. Some Nodes have duplicate Out edges.
+    // We need to explicitly ignore these here, otherwise their work will get
+    // scheduled twice (see https://github.com/martine/ninja/pull/519)
+    if (ready_.count(edge)) {
+      return;
+    }
     pool->DelayEdge(edge);
     pool->RetrieveReadyEdges(&ready_);
   } else {
diff --git a/src/build_test.cc b/src/build_test.cc
index 59c4c53..40a82ed 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -302,6 +302,80 @@ TEST_F(PlanTest, PoolsWithDepthTwo) {
   ASSERT_FALSE(plan_.FindWork());
 }
 
+TEST_F(PlanTest, PoolWithRedundantEdges) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "pool compile\n"
+    "  depth = 1\n"
+    "rule gen_foo\n"
+    "  command = touch foo.cpp\n"
+    "rule gen_bar\n"
+    "  command = touch bar.cpp\n"
+    "rule echo\n"
+    "  command = echo $out > $out\n"
+    "build foo.cpp.obj: echo foo.cpp || foo.cpp\n"
+    "  pool = compile\n"
+    "build bar.cpp.obj: echo bar.cpp || bar.cpp\n"
+    "  pool = compile\n"
+    "build libfoo.a: echo foo.cpp.obj bar.cpp.obj\n"
+    "build foo.cpp: gen_foo\n"
+    "build bar.cpp: gen_bar\n"
+    "build all: phony libfoo.a\n"));
+  GetNode("foo.cpp")->MarkDirty();
+  GetNode("foo.cpp.obj")->MarkDirty();
+  GetNode("bar.cpp")->MarkDirty();
+  GetNode("bar.cpp.obj")->MarkDirty();
+  GetNode("libfoo.a")->MarkDirty();
+  GetNode("all")->MarkDirty();
+  string err;
+  EXPECT_TRUE(plan_.AddTarget(GetNode("all"), &err));
+  ASSERT_EQ("", err);
+  ASSERT_TRUE(plan_.more_to_do());
+
+  Edge* edge = NULL;
+
+  edge = plan_.FindWork();
+  ASSERT_TRUE(edge);
+  ASSERT_EQ("foo.cpp", edge->outputs_[0]->path());
+  plan_.EdgeFinished(edge);
+
+  edge = plan_.FindWork();
+  ASSERT_TRUE(edge);
+  ASSERT_EQ("foo.cpp", edge->inputs_[0]->path());
+  ASSERT_EQ("foo.cpp", edge->inputs_[1]->path());
+  ASSERT_EQ("foo.cpp.obj", edge->outputs_[0]->path());
+  plan_.EdgeFinished(edge);
+
+  edge = plan_.FindWork();
+  ASSERT_TRUE(edge);
+  ASSERT_EQ("bar.cpp", edge->outputs_[0]->path());
+  plan_.EdgeFinished(edge);
+
+  edge = plan_.FindWork();
+  ASSERT_TRUE(edge);
+  ASSERT_EQ("bar.cpp", edge->inputs_[0]->path());
+  ASSERT_EQ("bar.cpp", edge->inputs_[1]->path());
+  ASSERT_EQ("bar.cpp.obj", edge->outputs_[0]->path());
+  plan_.EdgeFinished(edge);
+
+  edge = plan_.FindWork();
+  ASSERT_TRUE(edge);
+  ASSERT_EQ("foo.cpp.obj", edge->inputs_[0]->path());
+  ASSERT_EQ("bar.cpp.obj", edge->inputs_[1]->path());
+  ASSERT_EQ("libfoo.a", edge->outputs_[0]->path());
+  plan_.EdgeFinished(edge);
+
+  edge = plan_.FindWork();
+  ASSERT_TRUE(edge);
+  ASSERT_EQ("libfoo.a", edge->inputs_[0]->path());
+  ASSERT_EQ("all", edge->outputs_[0]->path());
+  plan_.EdgeFinished(edge);
+
+  edge = plan_.FindWork();
+  ASSERT_FALSE(edge);
+  ASSERT_FALSE(plan_.more_to_do());
+}
+
+
 struct BuildTest : public StateTestWithBuiltinRules,
                    public CommandRunner {
   BuildTest() : config_(MakeConfig()),
diff --git a/src/state.cc b/src/state.cc
index b5d2622..9f46fee 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -35,23 +35,25 @@ void Pool::EdgeFinished(const Edge& edge) {
 
 void Pool::DelayEdge(Edge* edge) {
   assert(depth_ != 0);
-  delayed_.push_back(edge);
+  delayed_.insert(edge);
 }
 
 void Pool::RetrieveReadyEdges(set<Edge*>* ready_queue) {
-  while (!delayed_.empty()) {
-    Edge* edge = delayed_.front();
+  DelayedEdges::iterator it = delayed_.begin();
+  while (it != delayed_.end()) {
+    Edge* edge = *it;
     if (current_use_ + edge->weight() > depth_)
       break;
-    delayed_.pop_front();
     ready_queue->insert(edge);
     EdgeScheduled(*edge);
+    ++it;
   }
+  delayed_.erase(delayed_.begin(), it);
 }
 
 void Pool::Dump() const {
   printf("%s (%d/%d) ->\n", name_.c_str(), current_use_, depth_);
-  for (deque<Edge*>::const_iterator it = delayed_.begin();
+  for (DelayedEdges::const_iterator it = delayed_.begin();
        it != delayed_.end(); ++it)
   {
     printf("\t");
@@ -59,6 +61,13 @@ void Pool::Dump() const {
   }
 }
 
+bool Pool::WeightedEdgeCmp(const Edge* a, const Edge* b) {
+  if (!a) return b;
+  if (!b) return false;
+  int weight_diff = a->weight() - b->weight();
+  return ((weight_diff < 0) || (weight_diff == 0 && a < b));
+}
+
 Pool State::kDefaultPool("", 0);
 const Rule State::kPhonyRule("phony");
 
diff --git a/src/state.h b/src/state.h
index 0a2e890..7e3aead 100644
--- a/src/state.h
+++ b/src/state.h
@@ -39,7 +39,7 @@ struct Rule;
 /// completes).
 struct Pool {
   explicit Pool(const string& name, int depth)
-    : name_(name), current_use_(0), depth_(depth) { }
+    : name_(name), current_use_(0), depth_(depth), delayed_(&WeightedEdgeCmp) { }
 
   // A depth of 0 is infinite
   bool is_valid() const { return depth_ >= 0; }
@@ -74,7 +74,10 @@ struct Pool {
   int current_use_;
   int depth_;
 
-  deque<Edge*> delayed_;
+  static bool WeightedEdgeCmp(const Edge* a, const Edge* b);
+
+  typedef set<Edge*,bool(*)(const Edge*, const Edge*)> DelayedEdges;
+  DelayedEdges delayed_;
 };
 
 /// Global state (file status, loaded rules) for a single run.