Merge pull request #1866 from jhasse/unique-edge-ids

Add unique IDs to edges

7 files changed, 34 insertions, 23 deletions

diff --git a/src/build.cc b/src/build.cc
index d08535d..2007d82 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -381,7 +381,7 @@ void Plan::EdgeWanted(const Edge* edge) {
 Edge* Plan::FindWork() {
   if (ready_.empty())
     return NULL;
-  set<Edge*>::iterator e = ready_.begin();
+  EdgeSet::iterator e = ready_.begin();
   Edge* edge = *e;
   ready_.erase(e);
   return edge;
diff --git a/src/build.h b/src/build.h
index fd6b6f6..0a68478 100644
--- a/src/build.h
+++ b/src/build.h
@@ -19,7 +19,6 @@
 #include <map>
 #include <memory>
 #include <queue>
-#include <set>
 #include <string>
 #include <vector>
 
@@ -122,7 +121,7 @@ private:
   /// we want for the edge.
   std::map<Edge*, Want> want_;
 
-  std::set<Edge*> ready_;
+  EdgeSet ready_;
 
   Builder* builder_;
 
diff --git a/src/graph.h b/src/graph.h
index 4833f49..8c51782 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -15,6 +15,7 @@
 #ifndef NINJA_GRAPH_H_
 #define NINJA_GRAPH_H_
 
+#include <set>
 #include <string>
 #include <vector>
 
@@ -143,10 +144,11 @@ struct Edge {
     VisitDone
   };
 
-  Edge() : rule_(NULL), pool_(NULL), dyndep_(NULL), env_(NULL),
-           mark_(VisitNone), outputs_ready_(false), deps_loaded_(false),
-           deps_missing_(false), implicit_deps_(0), order_only_deps_(0),
-           implicit_outs_(0) {}
+  Edge()
+      : rule_(NULL), pool_(NULL), dyndep_(NULL), env_(NULL), mark_(VisitNone),
+        id_(0), outputs_ready_(false), deps_loaded_(false),
+        deps_missing_(false), implicit_deps_(0), order_only_deps_(0),
+        implicit_outs_(0) {}
 
   /// Return true if all inputs' in-edges are ready.
   bool AllInputsReady() const;
@@ -176,6 +178,7 @@ struct Edge {
   Node* dyndep_;
   BindingEnv* env_;
   VisitMark mark_;
+  size_t id_;
   bool outputs_ready_;
   bool deps_loaded_;
   bool deps_missing_;
@@ -218,6 +221,13 @@ struct Edge {
   bool maybe_phonycycle_diagnostic() const;
 };
 
+struct EdgeCmp {
+  bool operator()(const Edge* a, const Edge* b) const {
+    return a->id_ < b->id_;
+  }
+};
+
+typedef std::set<Edge*, EdgeCmp> EdgeSet;
 
 /// ImplicitDepLoader loads implicit dependencies, as referenced via the
 /// "depfile" attribute in build files.
diff --git a/src/graphviz.h b/src/graphviz.h
index 601c9b2..3a3282e 100644
--- a/src/graphviz.h
+++ b/src/graphviz.h
@@ -18,6 +18,7 @@
 #include <set>
 
 #include "dyndep.h"
+#include "graph.h"
 
 struct DiskInterface;
 struct Node;
@@ -34,7 +35,7 @@ struct GraphViz {
 
   DyndepLoader dyndep_loader_;
   std::set<Node*> visited_nodes_;
-  std::set<Edge*> visited_edges_;
+  EdgeSet visited_edges_;
 };
 
 #endif  // NINJA_GRAPHVIZ_H_
diff --git a/src/ninja.cc b/src/ninja.cc
index 471a023..eb97320 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -613,7 +613,7 @@ int NinjaMain::ToolRules(const Options* options, int argc, char* argv[]) {
 }
 
 enum PrintCommandMode { PCM_Single, PCM_All };
-void PrintCommands(Edge* edge, set<Edge*>* seen, PrintCommandMode mode) {
+void PrintCommands(Edge* edge, EdgeSet* seen, PrintCommandMode mode) {
   if (!edge)
     return;
   if (!seen->insert(edge).second)
@@ -664,7 +664,7 @@ int NinjaMain::ToolCommands(const Options* options, int argc, char* argv[]) {
     return 1;
   }
 
-  set<Edge*> seen;
+  EdgeSet seen;
   for (vector<Node*>::iterator in = nodes.begin(); in != nodes.end(); ++in)
     PrintCommands((*in)->in_edge(), &seen, mode);
 
diff --git a/src/state.cc b/src/state.cc
index d3a9e29..a33d5a8 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -39,7 +39,7 @@ void Pool::DelayEdge(Edge* edge) {
   delayed_.insert(edge);
 }
 
-void Pool::RetrieveReadyEdges(set<Edge*>* ready_queue) {
+void Pool::RetrieveReadyEdges(EdgeSet* ready_queue) {
   DelayedEdges::iterator it = delayed_.begin();
   while (it != delayed_.end()) {
     Edge* edge = *it;
@@ -62,14 +62,6 @@ void Pool::Dump() const {
   }
 }
 
-// static
-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);
 Pool State::kConsolePool("console", 1);
 const Rule State::kPhonyRule("phony");
@@ -97,6 +89,7 @@ Edge* State::AddEdge(const Rule* rule) {
   edge->rule_ = rule;
   edge->pool_ = &State::kDefaultPool;
   edge->env_ = &bindings_;
+  edge->id_ = edges_.size();
   edges_.push_back(edge);
   return edge;
 }
diff --git a/src/state.h b/src/state.h
index f553ed4..72c5b33 100644
--- a/src/state.h
+++ b/src/state.h
@@ -21,6 +21,7 @@
 #include <vector>
 
 #include "eval_env.h"
+#include "graph.h"
 #include "hash_map.h"
 #include "util.h"
 
@@ -38,7 +39,7 @@ struct Rule;
 /// completes).
 struct Pool {
   Pool(const std::string& name, int depth)
-    : name_(name), current_use_(0), depth_(depth), delayed_(&WeightedEdgeCmp) {}
+    : name_(name), current_use_(0), depth_(depth), delayed_() {}
 
   // A depth of 0 is infinite
   bool is_valid() const { return depth_ >= 0; }
@@ -61,7 +62,7 @@ struct Pool {
   void DelayEdge(Edge* edge);
 
   /// Pool will add zero or more edges to the ready_queue
-  void RetrieveReadyEdges(std::set<Edge*>* ready_queue);
+  void RetrieveReadyEdges(EdgeSet* ready_queue);
 
   /// Dump the Pool and its edges (useful for debugging).
   void Dump() const;
@@ -74,9 +75,16 @@ struct Pool {
   int current_use_;
   int depth_;
 
-  static bool WeightedEdgeCmp(const Edge* a, const Edge* b);
+  struct WeightedEdgeCmp {
+    bool operator()(const Edge* a, const Edge* b) const {
+      if (!a) return b;
+      if (!b) return false;
+      int weight_diff = a->weight() - b->weight();
+      return ((weight_diff < 0) || (weight_diff == 0 && EdgeCmp()(a, b)));
+    }
+  };
 
-  typedef std::set<Edge*,bool(*)(const Edge*, const Edge*)> DelayedEdges;
+  typedef std::set<Edge*, WeightedEdgeCmp> DelayedEdges;
   DelayedEdges delayed_;
 };