Merge pull request #1294 from bradking/plan-track-scheduling

Track in Plan whether wanted edges have been scheduled

2 files changed, 40 insertions, 26 deletions

diff --git a/src/build.cc b/src/build.cc
index 5239637..0eda16b 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -318,18 +318,18 @@ bool Plan::AddSubTarget(Node* node, Node* dependent, string* err) {
     return false;  // Don't need to do anything.
 
   // If an entry in want_ does not already exist for edge, create an entry which
-  // maps to false, indicating that we do not want to build this entry itself.
-  pair<map<Edge*, bool>::iterator, bool> want_ins =
-    want_.insert(make_pair(edge, false));
-  bool& want = want_ins.first->second;
+  // maps to kWantNothing, indicating that we do not want to build this entry itself.
+  pair<map<Edge*, Want>::iterator, bool> want_ins =
+    want_.insert(make_pair(edge, kWantNothing));
+  Want& want = want_ins.first->second;
 
   // If we do need to build edge and we haven't already marked it as wanted,
   // mark it now.
-  if (node->dirty() && !want) {
-    want = true;
+  if (node->dirty() && want == kWantNothing) {
+    want = kWantToStart;
     ++wanted_edges_;
     if (edge->AllInputsReady())
-      ScheduleWork(edge);
+      ScheduleWork(want_ins.first);
     if (!edge->is_phony())
       ++command_edges_;
   }
@@ -355,30 +355,32 @@ Edge* Plan::FindWork() {
   return edge;
 }
 
-void Plan::ScheduleWork(Edge* edge) {
-  set<Edge*>::iterator e = ready_.lower_bound(edge);
-  if (e != ready_.end() && !ready_.key_comp()(edge, *e)) {
+void Plan::ScheduleWork(map<Edge*, Want>::iterator want_e) {
+  if (want_e->second == kWantToFinish) {
     // 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;
   }
+  assert(want_e->second == kWantToStart);
+  want_e->second = kWantToFinish;
 
+  Edge* edge = want_e->first;
   Pool* pool = edge->pool();
   if (pool->ShouldDelayEdge()) {
     pool->DelayEdge(edge);
     pool->RetrieveReadyEdges(&ready_);
   } else {
     pool->EdgeScheduled(*edge);
-    ready_.insert(e, edge);
+    ready_.insert(edge);
   }
 }
 
 void Plan::EdgeFinished(Edge* edge, EdgeResult result) {
-  map<Edge*, bool>::iterator e = want_.find(edge);
+  map<Edge*, Want>::iterator e = want_.find(edge);
   assert(e != want_.end());
-  bool directly_wanted = e->second;
+  bool directly_wanted = e->second != kWantNothing;
 
   // See if this job frees up any delayed jobs.
   if (directly_wanted)
@@ -405,14 +407,14 @@ void Plan::NodeFinished(Node* node) {
   // See if we we want any edges from this node.
   for (vector<Edge*>::const_iterator oe = node->out_edges().begin();
        oe != node->out_edges().end(); ++oe) {
-    map<Edge*, bool>::iterator want_e = want_.find(*oe);
+    map<Edge*, Want>::iterator want_e = want_.find(*oe);
     if (want_e == want_.end())
       continue;
 
     // See if the edge is now ready.
     if ((*oe)->AllInputsReady()) {
-      if (want_e->second) {
-        ScheduleWork(*oe);
+      if (want_e->second != kWantNothing) {
+        ScheduleWork(want_e);
       } else {
         // We do not need to build this edge, but we might need to build one of
         // its dependents.
@@ -428,8 +430,8 @@ bool Plan::CleanNode(DependencyScan* scan, Node* node, string* err) {
   for (vector<Edge*>::const_iterator oe = node->out_edges().begin();
        oe != node->out_edges().end(); ++oe) {
     // Don't process edges that we don't actually want.
-    map<Edge*, bool>::iterator want_e = want_.find(*oe);
-    if (want_e == want_.end() || !want_e->second)
+    map<Edge*, Want>::iterator want_e = want_.find(*oe);
+    if (want_e == want_.end() || want_e->second == kWantNothing)
       continue;
 
     // Don't attempt to clean an edge if it failed to load deps.
@@ -469,7 +471,7 @@ bool Plan::CleanNode(DependencyScan* scan, Node* node, string* err) {
             return false;
         }
 
-        want_e->second = false;
+        want_e->second = kWantNothing;
         --wanted_edges_;
         if (!(*oe)->is_phony())
           --command_edges_;
@@ -481,8 +483,8 @@ bool Plan::CleanNode(DependencyScan* scan, Node* node, string* err) {
 
 void Plan::Dump() {
   printf("pending: %d\n", (int)want_.size());
-  for (map<Edge*, bool>::iterator e = want_.begin(); e != want_.end(); ++e) {
-    if (e->second)
+  for (map<Edge*, Want>::iterator e = want_.begin(); e != want_.end(); ++e) {
+    if (e->second != kWantNothing)
       printf("want ");
     e->first->Dump();
   }
diff --git a/src/build.h b/src/build.h
index e38719c..9b90e8a 100644
--- a/src/build.h
+++ b/src/build.h
@@ -78,17 +78,29 @@ private:
   bool AddSubTarget(Node* node, Node* dependent, string* err);
   void NodeFinished(Node* node);
 
+  /// Enumerate possible steps we want for an edge.
+  enum Want
+  {
+    /// We do not want to build the edge, but we might want to build one of
+    /// its dependents.
+    kWantNothing,
+    /// We want to build the edge, but have not yet scheduled it.
+    kWantToStart,
+    /// We want to build the edge, have scheduled it, and are waiting
+    /// for it to complete.
+    kWantToFinish
+  };
+
   /// Submits a ready edge as a candidate for execution.
   /// The edge may be delayed from running, for example if it's a member of a
   /// currently-full pool.
-  void ScheduleWork(Edge* edge);
+  void ScheduleWork(map<Edge*, Want>::iterator want_e);
 
   /// Keep track of which edges we want to build in this plan.  If this map does
   /// not contain an entry for an edge, we do not want to build the entry or its
-  /// dependents.  If an entry maps to false, we do not want to build it, but we
-  /// might want to build one of its dependents.  If the entry maps to true, we
-  /// want to build it.
-  map<Edge*, bool> want_;
+  /// dependents.  If it does contain an entry, the enumeration indicates what
+  /// we want for the edge.
+  map<Edge*, Want> want_;
 
   set<Edge*> ready_;