Merge pull request #1866 from jhasse/unique-edge-ids
Add unique IDs to edges
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 @@
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 @@
/// 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 @@
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 @@
Node* dyndep_;
BindingEnv* env_;
VisitMark mark_;
+ size_t id_;
bool outputs_ready_;
bool deps_loaded_;
bool deps_missing_;
@@ -218,6 +221,13 @@
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 @@
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 @@
}
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 @@
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 @@
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 @@
}
}
-// 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->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 @@
/// 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 @@
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 @@
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_;
};
