summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/build.cc91
-rw-r--r--src/build.h14
-rw-r--r--src/build_test.cc30
-rw-r--r--src/graph.cc81
-rw-r--r--src/graph.h39
-rw-r--r--src/stat_cache.cc4
-rw-r--r--src/state.cc6
-rw-r--r--src/state.h1
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.