Improve comments and retrieve edges into ready_queue directly

6 files changed, 28 insertions, 31 deletions

diff --git a/src/build.cc b/src/build.cc
index d6be1c0..de62a62 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -173,9 +173,7 @@ void Plan::ScheduleWork(map<Edge*, Want>::iterator want_e) {
   Pool* pool = edge->pool();
   if (pool->ShouldDelayEdge()) {
     pool->DelayEdge(edge);
-    EdgeSet new_edges;
-    pool->RetrieveReadyEdges(&new_edges);
-    ready_.push_multiple(new_edges.begin(), new_edges.end());
+    pool->RetrieveReadyEdges(&ready_);
   } else {
     pool->EdgeScheduled(*edge);
     ready_.push(edge);
@@ -190,9 +188,7 @@ bool Plan::EdgeFinished(Edge* edge, EdgeResult result, string* err) {
   // See if this job frees up any delayed jobs.
   if (directly_wanted)
     edge->pool()->EdgeFinished(*edge);
-  EdgeSet new_edges;
-  edge->pool()->RetrieveReadyEdges(&new_edges);
-  ready_.push_multiple(new_edges.begin(), new_edges.end());
+  edge->pool()->RetrieveReadyEdges(&ready_);
 
   // The rest of this function only applies to successful commands.
   if (result != kEdgeSucceeded)
@@ -541,10 +537,10 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) {
   // Use backflow algorithm to compute critical times for all nodes, starting
   // from the destination nodes.
   // XXX: ignores pools
-  std::queue<Edge*> breadthFirstEdges;  // Queue, for breadth-first traversal
-  std::set<const Edge*> active_edges;   // Set of in breadthFirstEdges
+  std::queue<Edge*> work_queue;        // Queue, for breadth-first traversal
+  std::set<const Edge*> active_edges;  // Set of edges in work_queue
   SeenBefore<Edge> seen_edge(
-      &active_edges);  // Test for uniqueness in breadthFirstEdges
+      &active_edges);  // Test for uniqueness in work_queue
 
   for (std::vector<const Node*>::reverse_iterator it = targets_.rbegin(),
                                                   end = targets_.rend();
@@ -557,14 +553,14 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) {
           priority_weight +
           std::max<int64_t>(in->run_time_ms_, in->critical_time()));
       if (!seen_edge(in)) {
-        breadthFirstEdges.push(in);
+        work_queue.push(in);
       }
     }
   }
 
-  while (!breadthFirstEdges.empty()) {
-    Edge* e = breadthFirstEdges.front();
-    breadthFirstEdges.pop();
+  while (!work_queue.empty()) {
+    Edge* e = work_queue.front();
+    work_queue.pop();
     active_edges.erase(e);
 
     for (std::vector<Node*>::iterator it = e->inputs_.begin(),
@@ -579,7 +575,7 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) {
       if (proposed_time > in->critical_time()) {
         in->set_critical_time(proposed_time);
         if (!seen_edge(in)) {
-          breadthFirstEdges.push(in);
+          work_queue.push(in);
         }
       }
     }
diff --git a/src/build.h b/src/build.h
index e91edbe..0d7c01a 100644
--- a/src/build.h
+++ b/src/build.h
@@ -22,7 +22,7 @@
 #include <vector>
 
 #include "depfile_parser.h"
-#include "graph.h"  // XXX needed for DependencyScan; should rearrange.
+#include "graph.h"
 #include "exit_status.h"
 #include "util.h"  // int64_t
 
@@ -120,7 +120,7 @@ private:
   /// we want for the edge.
   std::map<Edge*, Want> want_;
 
-  EdgeQueue ready_;
+  EdgePriorityQueue ready_;
 
   Builder* builder_;
   /// user provided targets in build order, earlier one have higher priority
diff --git a/src/graph.h b/src/graph.h
index 0604ea7..4b45dad 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -197,7 +197,7 @@ struct Edge {
 
   void Dump(const char* prefix="") const;
 
-  // Critical time is the estimated exection time in ms of the edges
+  // Critical time is the estimated execution time in ms of the edges
   // forming the longest time-weighted path to the target output.
   // This quantity is used as a priority during build scheduling.
   // NOTE: Defaults to -1 as a marker smaller than any valid time
@@ -376,7 +376,13 @@ struct DependencyScan {
   DyndepLoader dyndep_loader_;
 };
 
-// Prioritize edges by largest critical time first
+// Implements a less comarison for edges by priority, where highest
+// priority is defined lexicographically first by largest critical
+// time, then lowest ID.
+//
+// Including ID means that wherever the critical times are the same,
+// the edges are executed in ascending ID order which was historically
+// how all tasks were scheduled.
 struct EdgePriorityCompare {
   bool operator()(const Edge* e1, const Edge* e2) const {
     const int64_t ct1 = e1->critical_time();
@@ -388,20 +394,15 @@ struct EdgePriorityCompare {
   }
 };
 
-// Set of ready edges, sorted by priority
-class EdgeQueue:
+// A priority queue holding non-owning Edge pointers. top() will
+// return the edge with the largest critical time, and lowest ID if
+// more than one edge has the same critical time.
+class EdgePriorityQueue:
   public std::priority_queue<Edge*, std::vector<Edge*>, EdgePriorityCompare>{
 public:
   void clear() {
     c.clear();
   }
-
-  template <typename It>
-  void push_multiple(It first, It last) {
-    for (; first != last; ++first) {
-      push(*first);
-    }
-  }
 };
 
 #endif  // NINJA_GRAPH_H_
diff --git a/src/graph_test.cc b/src/graph_test.cc
index 97726ce..d657387 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -968,7 +968,7 @@ TEST_F(GraphTest, EdgeQueuePriority) {
     edges[i]->set_critical_time(i * 10);
   }
 
-  EdgeQueue queue;
+  EdgePriorityQueue queue;
   for (int i = 0; i < n_edges; ++i) {
     queue.push(edges[i]);
   }
diff --git a/src/state.cc b/src/state.cc
index 556b0d8..e194519 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -38,13 +38,13 @@ void Pool::DelayEdge(Edge* edge) {
   delayed_.insert(edge);
 }
 
-void Pool::RetrieveReadyEdges(EdgeSet* ready_queue) {
+void Pool::RetrieveReadyEdges(EdgePriorityQueue* ready_queue) {
   DelayedEdges::iterator it = delayed_.begin();
   while (it != delayed_.end()) {
     Edge* edge = *it;
     if (current_use_ + edge->weight() > depth_)
       break;
-    ready_queue->insert(edge);
+    ready_queue->push(edge);
     EdgeScheduled(*edge);
     ++it;
   }
diff --git a/src/state.h b/src/state.h
index 878ac6d..2b0fa90 100644
--- a/src/state.h
+++ b/src/state.h
@@ -62,7 +62,7 @@ struct Pool {
   void DelayEdge(Edge* edge);
 
   /// Pool will add zero or more edges to the ready_queue
-  void RetrieveReadyEdges(EdgeSet* ready_queue);
+  void RetrieveReadyEdges(EdgePriorityQueue* ready_queue);
 
   /// Dump the Pool and its edges (useful for debugging).
   void Dump() const;