From 03cbfc65220e8f98548684e785d95bf5734c3f59 Mon Sep 17 00:00:00 2001 From: Colin Cross Date: Mon, 14 Nov 2016 17:13:16 -0800 Subject: Add unique IDs to edges Edges are nominally ordered by order in the build manifest, but in fact are ordered by memory address. In most cases the memory address will be monontonically increasing. Since serialized build output will need unique IDs, add a monotonically increasing ID to edges, and use that for sorting instead of memory address. --- src/build.cc | 2 +- src/build.h | 3 +-- src/graph.h | 18 ++++++++++++++---- src/graphviz.h | 3 ++- src/ninja.cc | 4 ++-- src/state.cc | 11 ++--------- src/state.h | 16 ++++++++++++---- 7 files changed, 34 insertions(+), 23 deletions(-) diff --git a/src/build.cc b/src/build.cc index e3131e2..3c2d0b7 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::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 2798693..2fe71fc 100644 --- a/src/build.h +++ b/src/build.h @@ -19,7 +19,6 @@ #include #include #include -#include #include #include @@ -122,7 +121,7 @@ private: /// we want for the edge. std::map want_; - std::set 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 #include #include @@ -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 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 #include "dyndep.h" +#include "graph.h" struct DiskInterface; struct Node; @@ -34,7 +35,7 @@ struct GraphViz { DyndepLoader dyndep_loader_; std::set visited_nodes_; - std::set 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* 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 seen; + EdgeSet seen; for (vector::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* 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 #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* 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 DelayedEdges; + typedef std::set DelayedEdges; DelayedEdges delayed_; }; -- cgit v0.12