Avoid double-scheduling build edges in another case

The change in commit v1.2.0~3^2~3^2~3 (Fix duplicate edge Pool crash in
the minimally invasive way, 2013-03-18) avoids double-scheduling in a
case involving duplicate out edges.  However, double-scheduling may also
occur on a consistent graph when an edge and one of its dependencies
share an order-only input:

    $ cat build.ninja
    ...
    build c: touch
    build b: touch || c
    build a: touch | b || c
    $ ninja a
    $ rm a c
    $ ninja a

In this case 'c' will build first.  When NodeFinished('c') loops over
the out edges it will find AllInputsReady is true for 'b' and call
EdgeFinished('b') since it is not wanted (up to date).  This will
call NodeFinished('b') which will loop over its out edges, find
AllInputsReady is true for 'a', and call ScheduleEdge('a').  When
we eventually return to the loop in NodeFinished('c') it will move
on to its second output and find that AllInputsReady is true for
'a' and call ScheduleEdge('a') again.

Teach ScheduleEdge to tolerate duplicate calls for an edge that has
already been scheduled.  Avoid calling EdgeScheduled more than once
for the same edge.

2 files changed, 33 insertions, 7 deletions

diff --git a/src/build.cc b/src/build.cc
index e33a007..0f3c8ef 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -366,19 +366,22 @@ Edge* Plan::FindWork() {
 }
 
 void Plan::ScheduleWork(Edge* edge) {
+  set<Edge*>::iterator e = ready_.lower_bound(edge);
+  if (e != ready_.end() && !ready_.key_comp()(edge, *e)) {
+    // This edge has already been scheduled.  We can get here again if an edge
+    // and one of its dependencies share an order-only input, or if a node
+    // duplicates an out edge (see https://github.com/ninja-build/ninja/pull/519).
+    // Avoid scheduling the work again.
+    return;
+  }
+
   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/ninja-build/ninja/pull/519)
-    if (ready_.count(edge)) {
-      return;
-    }
     pool->DelayEdge(edge);
     pool->RetrieveReadyEdges(&ready_);
   } else {
     pool->EdgeScheduled(*edge);
-    ready_.insert(edge);
+    ready_.insert(e, edge);
   }
 }
 
diff --git a/src/build_test.cc b/src/build_test.cc
index 7c6060d..26bf7ef 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -875,6 +875,29 @@ TEST_F(BuildTest, DepFileParseError) {
   EXPECT_EQ("foo.o.d: expected ':' in depfile", err);
 }
 
+TEST_F(BuildTest, EncounterReadyTwice) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"build c: touch\n"
+"build b: touch || c\n"
+"build a: touch | b || c\n"));
+
+  vector<Edge*> c_out = GetNode("c")->out_edges();
+  ASSERT_EQ(2u, c_out.size());
+  EXPECT_EQ("b", c_out[0]->outputs_[0]->path());
+  EXPECT_EQ("a", c_out[1]->outputs_[0]->path());
+
+  fs_.Create("b", "");
+  EXPECT_TRUE(builder_.AddTarget("a", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  ASSERT_EQ("", err);
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size());
+}
+
 TEST_F(BuildTest, OrderOnlyDeps) {
   string err;
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,