diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/build.cc | 91 | ||||
| -rw-r--r-- | src/build.h | 14 | ||||
| -rw-r--r-- | src/build_test.cc | 30 | ||||
| -rw-r--r-- | src/graph.cc | 81 | ||||
| -rw-r--r-- | src/graph.h | 39 | ||||
| -rw-r--r-- | src/stat_cache.cc | 4 | ||||
| -rw-r--r-- | src/state.cc | 6 | ||||
| -rw-r--r-- | src/state.h | 1 |
8 files changed, 160 insertions, 106 deletions
diff --git a/src/build.cc b/src/build.cc index e72d9d7..c9ffe7e 100644 --- a/src/build.cc +++ b/src/build.cc @@ -175,7 +175,7 @@ void BuildStatus::PrintStatus(Edge* edge) { } } -Plan::Plan() : command_edges_(0) {} +Plan::Plan() : command_edges_(0), wanted_edges_(0) {} bool Plan::AddTarget(Node* node, string* err) { vector<Node*> stack; @@ -199,30 +199,39 @@ bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) { if (CheckDependencyCycle(node, stack, err)) return false; - if (!node->dirty()) + if (edge->outputs_ready()) return false; // Don't need to do anything. - if (want_.find(edge) != want_.end()) - return true; // We've already enqueued it. - want_.insert(edge); - if (!edge->is_phony()) - ++command_edges_; + + // 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<map<Edge*, bool>::iterator, bool> want_ins = + want_.insert(make_pair(edge, false)); + bool& 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; + ++wanted_edges_; + if (find_if(edge->inputs_.begin(), edge->inputs_.end(), + not1(mem_fun(&Node::ready))) == edge->inputs_.end()) + ready_.insert(edge); + if (!edge->is_phony()) + ++command_edges_; + } + + if (!want_ins.second) + return true; // We've already processed the inputs. stack->push_back(node); - bool awaiting_inputs = false; for (vector<Node*>::iterator i = edge->inputs_.begin(); i != edge->inputs_.end(); ++i) { - if (AddSubTarget(*i, stack, err)) { - awaiting_inputs = true; - } else if (!err->empty()) { + if (!AddSubTarget(*i, stack, err) && !err->empty()) return false; - } } assert(stack->back() == node); stack->pop_back(); - if (!awaiting_inputs) - ready_.insert(edge); - return true; } @@ -256,7 +265,12 @@ Edge* Plan::FindWork() { } void Plan::EdgeFinished(Edge* edge) { - want_.erase(edge); + map<Edge*, bool>::iterator i = want_.find(edge); + assert(i != want_.end()); + if (i->second) + --wanted_edges_; + want_.erase(i); + edge->outputs_ready_ = true; // Check off any nodes we were waiting for with this edge. for (vector<Node*>::iterator i = edge->outputs_.begin(); @@ -269,26 +283,30 @@ void Plan::NodeFinished(Node* node) { // See if we we want any edges from this node. for (vector<Edge*>::iterator i = node->out_edges_.begin(); i != node->out_edges_.end(); ++i) { - if (want_.find(*i) != want_.end()) { - // See if the edge is now ready. - bool ready = true; - for (vector<Node*>::iterator j = (*i)->inputs_.begin(); - j != (*i)->inputs_.end(); ++j) { - if ((*j)->dirty()) { - ready = false; - break; - } - } - if (ready) + map<Edge*, bool>::iterator want_i = want_.find(*i); + if (want_i == want_.end()) + continue; + + // See if the edge is now ready. + if (find_if((*i)->inputs_.begin(), (*i)->inputs_.end(), + not1(mem_fun(&Node::ready))) == (*i)->inputs_.end()) { + if (want_i->second) { ready_.insert(*i); + } else { + // We do not need to build this edge, but we might need to build one of + // its dependents. + EdgeFinished(*i); + } } } } void Plan::Dump() { printf("pending: %d\n", (int)want_.size()); - for (set<Edge*>::iterator i = want_.begin(); i != want_.end(); ++i) { - (*i)->Dump(); + for (map<Edge*, bool>::iterator i = want_.begin(); i != want_.end(); ++i) { + if (i->second) + printf("want "); + i->first->Dump(); } printf("ready: %d\n", (int)ready_.size()); } @@ -383,12 +401,12 @@ Node* Builder::AddTarget(const string& name, string* err) { bool Builder::AddTarget(Node* node, string* err) { node->file_->StatIfNecessary(disk_interface_); - if (node->in_edge_) { - if (!node->in_edge_->RecomputeDirty(state_, disk_interface_, err)) + if (Edge* in_edge = node->in_edge_) { + if (!in_edge->RecomputeDirty(state_, disk_interface_, err)) return false; + if (in_edge->outputs_ready()) + return true; // Nothing to do. } - if (!node->dirty_) - return true; // Nothing to do. if (!plan_.AddTarget(node, err)) return false; @@ -498,13 +516,8 @@ bool Builder::StartEdge(Edge* edge, string* err) { } void Builder::FinishEdge(Edge* edge, bool success, const string& output) { - if (success) { - for (vector<Node*>::iterator i = edge->outputs_.begin(); - i != edge->outputs_.end(); ++i) { - (*i)->dirty_ = false; - } + if (success) plan_.EdgeFinished(edge); - } if (edge->is_phony()) return; diff --git a/src/build.h b/src/build.h index 0f7303e..fa0abd2 100644 --- a/src/build.h +++ b/src/build.h @@ -15,6 +15,7 @@ #ifndef NINJA_BUILD_H_ #define NINJA_BUILD_H_ +#include <map> #include <set> #include <string> #include <queue> @@ -41,7 +42,7 @@ struct Plan { Edge* FindWork(); /// Returns true if there's more work to be done. - bool more_to_do() const { return !want_.empty(); } + bool more_to_do() const { return wanted_edges_; } /// Dumps the current state of the plan. void Dump(); @@ -58,11 +59,20 @@ private: bool CheckDependencyCycle(Node* node, vector<Node*>* stack, string* err); void NodeFinished(Node* node); - set<Edge*> want_; + /// 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<Edge*, bool> want_; + set<Edge*> ready_; /// Total number of edges that have commands (not phony). int command_edges_; + + /// Total remaining number of wanted edges. + int wanted_edges_; }; /// CommandRunner is an interface that wraps running the build diff --git a/src/build_test.cc b/src/build_test.cc index 84359a3..a4bf256 100644 --- a/src/build_test.cc +++ b/src/build_test.cc @@ -42,7 +42,6 @@ TEST_F(PlanTest, Basic) { ASSERT_FALSE(plan_.FindWork()); - GetNode("mid")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); @@ -50,7 +49,6 @@ TEST_F(PlanTest, Basic) { ASSERT_EQ("mid", edge->inputs_[0]->file_->path_); ASSERT_EQ("out", edge->outputs_[0]->file_->path_); - GetNode("out")->dirty_ = false; plan_.EdgeFinished(edge); ASSERT_FALSE(plan_.more_to_do()); @@ -75,13 +73,10 @@ TEST_F(PlanTest, DoubleOutputDirect) { Edge* edge; edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat in - GetNode("mid1")->dirty_ = false; - GetNode("mid2")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat mid1 mid2 - GetNode("in")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); @@ -108,23 +103,18 @@ TEST_F(PlanTest, DoubleOutputIndirect) { Edge* edge; edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat in - GetNode("a1")->dirty_ = false; - GetNode("a2")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat a1 - GetNode("b1")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat a2 - GetNode("b2")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat b1 b2 - GetNode("out")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); @@ -151,22 +141,18 @@ TEST_F(PlanTest, DoubleDependent) { Edge* edge; edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat in - GetNode("mid")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat mid - GetNode("a1")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat mid - GetNode("a2")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); ASSERT_TRUE(edge); // cat a1 a2 - GetNode("out")->dirty_ = false; plan_.EdgeFinished(edge); edge = plan_.FindWork(); @@ -324,10 +310,12 @@ TEST_F(BuildTest, TwoStep) { EXPECT_EQ("cat cat1 cat2 > cat12", commands_ran_[2]); + now_++; + // Modifying in2 requires rebuilding one intermediate file // and the final file. - GetNode("cat2")->dirty_ = true; - GetNode("cat12")->dirty_ = true; + fs_.Create("in2", now_, ""); + state_.Reset(); EXPECT_TRUE(builder_.AddTarget("cat12", &err)); ASSERT_EQ("", err); EXPECT_TRUE(builder_.Build(&err)); @@ -372,7 +360,7 @@ TEST_F(BuildTest, Chain) { err.clear(); commands_ran_.clear(); - state_.stat_cache_.Invalidate(); + state_.Reset(); EXPECT_TRUE(builder_.AddTarget("c5", &err)); ASSERT_EQ("", err); EXPECT_TRUE(builder_.AlreadyUpToDate()); @@ -382,7 +370,7 @@ TEST_F(BuildTest, Chain) { fs_.Create("c3", now_, ""); err.clear(); commands_ran_.clear(); - state_.stat_cache_.Invalidate(); + state_.Reset(); EXPECT_TRUE(builder_.AddTarget("c5", &err)); ASSERT_EQ("", err); EXPECT_FALSE(builder_.AlreadyUpToDate()); @@ -518,7 +506,7 @@ TEST_F(BuildTest, OrderOnlyDeps) { fs_.Create("blah.h", now_, ""); fs_.Create("bar.h", now_, ""); commands_ran_.clear(); - state_.stat_cache_.Invalidate(); + state_.Reset(); EXPECT_TRUE(builder_.AddTarget("foo.o", &err)); EXPECT_TRUE(builder_.Build(&err)); ASSERT_EQ("", err); @@ -529,7 +517,7 @@ TEST_F(BuildTest, OrderOnlyDeps) { // order only dep dirty, no rebuild. fs_.Create("otherfile", now_, ""); commands_ran_.clear(); - state_.stat_cache_.Invalidate(); + state_.Reset(); EXPECT_TRUE(builder_.AddTarget("foo.o", &err)); EXPECT_EQ("", err); EXPECT_TRUE(builder_.AlreadyUpToDate()); @@ -537,7 +525,7 @@ TEST_F(BuildTest, OrderOnlyDeps) { // implicit dep missing, expect rebuild. fs_.RemoveFile("bar.h"); commands_ran_.clear(); - state_.stat_cache_.Invalidate(); + state_.Reset(); EXPECT_TRUE(builder_.AddTarget("foo.o", &err)); EXPECT_TRUE(builder_.Build(&err)); ASSERT_EQ("", err); diff --git a/src/graph.cc b/src/graph.cc index e1441ea..65fed2e 100644 --- a/src/graph.cc +++ b/src/graph.cc @@ -37,6 +37,8 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface, return false; } + outputs_ready_ = true; + time_t most_recent_input = 1; for (vector<Node*>::iterator i = inputs_.begin(); i != inputs_.end(); ++i) { if ((*i)->file_->StatIfNecessary(disk_interface)) { @@ -51,11 +53,18 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface, if (is_order_only(i - inputs_.begin())) { // Order-only deps only make us dirty if they're missing. - if (!(*i)->file_->exists()) + if (!(*i)->file_->exists()) { dirty = true; + outputs_ready_ = false; + } continue; } + // If an input is not ready, neither are our outputs. + if (Edge* edge = (*i)->in_edge_) + if (!edge->outputs_ready_) + outputs_ready_ = false; + // If a regular input is dirty (or missing), we're dirty. // Otherwise consider mtime. if ((*i)->dirty_) { @@ -66,6 +75,7 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface, } } + BuildLog* build_log = state ? state->build_log_ : 0; string command = EvaluateCommand(); assert(!outputs_.empty()); @@ -75,35 +85,44 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface, // visited their dependents. (*i)->file_->StatIfNecessary(disk_interface); - if (is_phony()) { - // Phony edges don't write any output. - // They're only dirty if an input is dirty, or if there are no inputs - // and we're missing the output. - if (dirty) - (*i)->dirty_ = true; - else if (inputs_.empty() && !(*i)->file_->exists()) - (*i)->dirty_ = true; - continue; - } + RecomputeOutputDirty(build_log, most_recent_input, dirty, command, *i); + if ((*i)->dirty_) + outputs_ready_ = false; + } - // Output is dirty if we're dirty, we're missing the output, - // or if it's older than the most recent input mtime. - if (dirty || !(*i)->file_->exists() || - (*i)->file_->mtime_ < most_recent_input) { - (*i)->dirty_ = true; - } else { - // May also be dirty due to the command changing since the last build. - // But if this is a generator rule, the command changing does not make us - // dirty. - BuildLog::LogEntry* entry; - if (!rule_->generator_ && state->build_log_ && - (entry = state->build_log_->LookupByOutput((*i)->file_->path_))) { - if (command != entry->command) - (*i)->dirty_ = true; - } + return true; +} + +void Edge::RecomputeOutputDirty(BuildLog* build_log, time_t most_recent_input, + bool dirty, const string& command, + Node* output) { + if (is_phony()) { + // Phony edges don't write any output. + // They're only dirty if an input is dirty, or if there are no inputs + // and we're missing the output. + if (dirty) + output->dirty_ = true; + else if (inputs_.empty() && !output->file_->exists()) + output->dirty_ = true; + return; + } + + // Output is dirty if we're dirty, we're missing the output, + // or if it's older than the most recent input mtime. + if (dirty || !output->file_->exists() || + output->file_->mtime_ < most_recent_input) { + output->dirty_ = true; + } else { + // May also be dirty due to the command changing since the last build. + // But if this is a generator rule, the command changing does not make us + // dirty. + BuildLog::LogEntry* entry; + if (!rule_->generator_ && build_log && + (entry = build_log->LookupByOutput(output->file_->path_))) { + if (command != entry->command) + output->dirty_ = true; } } - return true; } /// An Env for an Edge, providing $in and $out. @@ -194,6 +213,14 @@ bool Edge::LoadDepFile(State* state, DiskInterface* disk_interface, Edge* phony_edge = state->AddEdge(&State::kPhonyRule); node->in_edge_ = phony_edge; phony_edge->outputs_.push_back(node); + + // RecomputeDirty might not be called for phony_edge if a previous call + // to RecomputeDirty had caused the file to be stat'ed. Because previous + // invocations of RecomputeDirty would have seen this node without an + // input edge (and therefore ready), we have to set outputs_ready_ to true + // to avoid a potential stuck build. If we do call RecomputeDirty for + // this node, it will simply set outputs_ready_ to the correct value. + phony_edge->outputs_ready_ = true; } } diff --git a/src/graph.h b/src/graph.h index 5b6bdf2..079db43 100644 --- a/src/graph.h +++ b/src/graph.h @@ -57,21 +57,6 @@ struct FileStat { Node* node_; }; -struct Edge; - -/// Information about a node in the dependency graph: the file, whether -/// it's dirty, etc. -struct Node { - Node(FileStat* file) : file_(file), dirty_(false), in_edge_(NULL) {} - - bool dirty() const { return dirty_; } - - FileStat* file_; - bool dirty_; - Edge* in_edge_; - vector<Edge*> out_edges_; -}; - /// An invokable build command and associated metadata (description, etc.). struct Rule { Rule(const string& name) : name_(name), generator_(false) { } @@ -86,13 +71,18 @@ struct Rule { bool generator_; }; +struct BuildLog; +struct Node; struct State; /// An edge in the dependency graph; links between Nodes using Rules. struct Edge { - Edge() : rule_(NULL), env_(NULL), implicit_deps_(0), order_only_deps_(0) {} + Edge() : rule_(NULL), env_(NULL), outputs_ready_(false), implicit_deps_(0), + order_only_deps_(0) {} bool RecomputeDirty(State* state, DiskInterface* disk_interface, string* err); + void RecomputeOutputDirty(BuildLog* build_log, time_t most_recent_input, + bool dirty, const string& command, Node* output); string EvaluateCommand(); // XXX move to env, take env ptr string GetDescription(); bool LoadDepFile(State* state, DiskInterface* disk_interface, string* err); @@ -103,6 +93,9 @@ struct Edge { vector<Node*> inputs_; vector<Node*> outputs_; Env* env_; + bool outputs_ready_; + + bool outputs_ready() const { return outputs_ready_; } // XXX There are three types of inputs. // 1) explicit deps, which show up as $in on the command line; @@ -128,4 +121,18 @@ struct Edge { bool is_phony() const; }; +/// Information about a node in the dependency graph: the file, whether +/// it's dirty, etc. +struct Node { + Node(FileStat* file) : file_(file), dirty_(false), in_edge_(NULL) {} + + bool dirty() const { return dirty_; } + bool ready() const { return !in_edge_ || in_edge_->outputs_ready(); } + + FileStat* file_; + bool dirty_; + Edge* in_edge_; + vector<Edge*> out_edges_; +}; + #endif // NINJA_GRAPH_H_ diff --git a/src/stat_cache.cc b/src/stat_cache.cc index 0b717b4..3309837 100644 --- a/src/stat_cache.cc +++ b/src/stat_cache.cc @@ -38,6 +38,8 @@ void StatCache::Dump() { } void StatCache::Invalidate() { - for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) + for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) { i->second->mtime_ = -1; + i->second->node_->dirty_ = false; + } } diff --git a/src/state.cc b/src/state.cc index e1fe675..87d824b 100644 --- a/src/state.cc +++ b/src/state.cc @@ -106,3 +106,9 @@ vector<Node*> State::RootNodes(string* err) { vector<Node*> State::DefaultNodes(string* err) { return defaults_.empty() ? RootNodes(err) : defaults_; } + +void State::Reset() { + stat_cache_.Invalidate(); + for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) + (*e)->outputs_ready_ = false; +} diff --git a/src/state.h b/src/state.h index ceb7c05..7f30563 100644 --- a/src/state.h +++ b/src/state.h @@ -44,6 +44,7 @@ struct State { void AddIn(Edge* edge, const string& path); void AddOut(Edge* edge, const string& path); bool AddDefault(const string& path, string* error); + void Reset(); /// @return the root node(s) of the graph. (Root nodes have no output edges). /// @param error where to write the error message if somethings went wrong. |