From f87e865e5b4ef91ac642f063ba55708359b8294f Mon Sep 17 00:00:00 2001 From: Brad King Date: Tue, 20 Jun 2017 15:17:39 -0400 Subject: Track in Plan whether wanted edges have been scheduled Refactor the `want_` map to track for wanted edges whether they have been scheduled or not. This gives `ScheduleWork` a direct place to keep this information, making the logic more robust and easier to follow. It also future-proofs `ScheduleWork` to avoid repeat scheduling if it is called after an edge has been removed from `ready_` by `FindWork`. --- src/build.cc | 44 +++++++++++++++++++++++--------------------- src/build.h | 22 +++++++++++++++++----- 2 files changed, 40 insertions(+), 26 deletions(-) diff --git a/src/build.cc b/src/build.cc index 61ef0e8..b888288 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::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::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::iterator e = ready_.lower_bound(edge); - if (e != ready_.end() && !ready_.key_comp()(edge, *e)) { +void Plan::ScheduleWork(map::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::iterator e = want_.find(edge); + map::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::const_iterator oe = node->out_edges().begin(); oe != node->out_edges().end(); ++oe) { - map::iterator want_e = want_.find(*oe); + map::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::const_iterator oe = node->out_edges().begin(); oe != node->out_edges().end(); ++oe) { // Don't process edges that we don't actually want. - map::iterator want_e = want_.find(*oe); - if (want_e == want_.end() || !want_e->second) + map::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. @@ -464,7 +466,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_; @@ -476,8 +478,8 @@ bool Plan::CleanNode(DependencyScan* scan, Node* node, string* err) { void Plan::Dump() { printf("pending: %d\n", (int)want_.size()); - for (map::iterator e = want_.begin(); e != want_.end(); ++e) { - if (e->second) + for (map::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 43786f1..d7a9a79 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::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 want_; + /// dependents. If it does contain an entry, the enumeration indicates what + /// we want for the edge. + map want_; set ready_; -- cgit v0.12