From fd91e0dc26d18209f7625730bb0e653f8321fff9 Mon Sep 17 00:00:00 2001 From: Evan Martin Date: Sun, 2 Sep 2012 11:03:01 -0700 Subject: [PATCH] split out dirty recomputation logic from Edge class Rather than passing States and DiskInterfaces through all the calls, put the necessary ambient information in a new DependencyScan object and move the code accordingly. Note: I didn't move the source location of the functions to preserve history, though this does result in a sort of weird order for the functions in graph.cc. --- src/build.cc | 15 ++++--- src/build.h | 4 +- src/disk_interface_test.cc | 11 +++-- src/graph.cc | 107 ++++++++++++++++++++++++--------------------- src/graph.h | 49 ++++++++++++++------- src/graph_test.cc | 19 ++++---- 6 files changed, 117 insertions(+), 88 deletions(-) diff --git a/src/build.cc b/src/build.cc index 6d1318c..18bba9e 100644 --- a/src/build.cc +++ b/src/build.cc @@ -406,7 +406,7 @@ void Plan::NodeFinished(Node* node) { } } -void Plan::CleanNode(BuildLog* build_log, Node* node) { +void Plan::CleanNode(DependencyScan* scan, Node* node) { node->set_dirty(false); for (vector::const_iterator ei = node->out_edges().begin(); @@ -435,12 +435,12 @@ void Plan::CleanNode(BuildLog* build_log, Node* node) { if (!(*ni)->dirty()) continue; - if ((*ei)->RecomputeOutputDirty(build_log, most_recent_input, NULL, command, - *ni)) { + if (scan->RecomputeOutputDirty(*ei, most_recent_input, NULL, + command, *ni)) { (*ni)->MarkDirty(); all_outputs_clean = false; } else { - CleanNode(build_log, *ni); + CleanNode(scan, *ni); } } @@ -554,7 +554,8 @@ struct DryRunCommandRunner : public CommandRunner { Builder::Builder(State* state, const BuildConfig& config, DiskInterface* disk_interface) - : state_(state), config_(config), disk_interface_(disk_interface) { + : state_(state), config_(config), disk_interface_(disk_interface), + scan_(state, disk_interface) { status_ = new BuildStatus(config); log_ = state->build_log_; } @@ -604,7 +605,7 @@ Node* Builder::AddTarget(const string& name, string* err) { bool Builder::AddTarget(Node* node, string* err) { node->StatIfNecessary(disk_interface_); if (Edge* in_edge = node->in_edge()) { - if (!in_edge->RecomputeDirty(state_, disk_interface_, err)) + if (!scan_.RecomputeDirty(in_edge, err)) return false; if (in_edge->outputs_ready()) return true; // Nothing to do. @@ -756,7 +757,7 @@ void Builder::FinishEdge(Edge* edge, bool success, const string& output) { // The rule command did not change the output. Propagate the clean // state through the build graph. // Note that this also applies to nonexistent outputs (mtime == 0). - plan_.CleanNode(log_, *i); + plan_.CleanNode(&scan_, *i); node_cleaned = true; } } diff --git a/src/build.h b/src/build.h index 986e8a9..9152eac 100644 --- a/src/build.h +++ b/src/build.h @@ -23,6 +23,7 @@ #include #include +#include "graph.h" // XXX needed for DependencyScan; should rearrange. #include "exit_status.h" #include "metrics.h" #include "util.h" // int64_t @@ -59,7 +60,7 @@ struct Plan { void EdgeFinished(Edge* edge); /// Clean the given node during the build. - void CleanNode(BuildLog* build_log, Node* node); + void CleanNode(DependencyScan* scan, Node* node); /// Number of edges with commands to run. int command_edge_count() const { return command_edges_; } @@ -151,6 +152,7 @@ struct Builder { private: DiskInterface* disk_interface_; + DependencyScan scan_; // Unimplemented copy ctor and operator= ensure we don't copy the auto_ptr. Builder(const Builder &other); // DO NOT IMPLEMENT diff --git a/src/disk_interface_test.cc b/src/disk_interface_test.cc index 985e991..68a6ca9 100644 --- a/src/disk_interface_test.cc +++ b/src/disk_interface_test.cc @@ -105,6 +105,8 @@ TEST_F(DiskInterfaceTest, RemoveFile) { struct StatTest : public StateTestWithBuiltinRules, public DiskInterface { + StatTest() : scan_(&state_, this) {} + // DiskInterface implementation. virtual TimeStamp Stat(const string& path); virtual bool WriteFile(const string& path, const string& contents) { @@ -124,6 +126,7 @@ struct StatTest : public StateTestWithBuiltinRules, return 0; } + DependencyScan scan_; map mtimes_; vector stats_; }; @@ -143,7 +146,7 @@ TEST_F(StatTest, Simple) { Node* out = GetNode("out"); out->Stat(this); ASSERT_EQ(1u, stats_.size()); - out->in_edge()->RecomputeDirty(NULL, this, NULL); + scan_.RecomputeDirty(out->in_edge(), NULL); ASSERT_EQ(2u, stats_.size()); ASSERT_EQ("out", stats_[0]); ASSERT_EQ("in", stats_[1]); @@ -157,7 +160,7 @@ TEST_F(StatTest, TwoStep) { Node* out = GetNode("out"); out->Stat(this); ASSERT_EQ(1u, stats_.size()); - out->in_edge()->RecomputeDirty(NULL, this, NULL); + scan_.RecomputeDirty(out->in_edge(), NULL); ASSERT_EQ(3u, stats_.size()); ASSERT_EQ("out", stats_[0]); ASSERT_TRUE(GetNode("out")->dirty()); @@ -175,7 +178,7 @@ TEST_F(StatTest, Tree) { Node* out = GetNode("out"); out->Stat(this); ASSERT_EQ(1u, stats_.size()); - out->in_edge()->RecomputeDirty(NULL, this, NULL); + scan_.RecomputeDirty(out->in_edge(), NULL); ASSERT_EQ(1u + 6u, stats_.size()); ASSERT_EQ("mid1", stats_[1]); ASSERT_TRUE(GetNode("mid1")->dirty()); @@ -194,7 +197,7 @@ TEST_F(StatTest, Middle) { Node* out = GetNode("out"); out->Stat(this); ASSERT_EQ(1u, stats_.size()); - out->in_edge()->RecomputeDirty(NULL, this, NULL); + scan_.RecomputeDirty(out->in_edge(), NULL); ASSERT_FALSE(GetNode("in")->dirty()); ASSERT_TRUE(GetNode("mid")->dirty()); ASSERT_TRUE(GetNode("out")->dirty()); diff --git a/src/graph.cc b/src/graph.cc index 3567bfa..d73e38e 100644 --- a/src/graph.cc +++ b/src/graph.cc @@ -32,17 +32,16 @@ bool Node::Stat(DiskInterface* disk_interface) { return mtime_ > 0; } -bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface, - string* err) { +bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { bool dirty = false; - outputs_ready_ = true; + edge->outputs_ready_ = true; - if (!rule_->depfile().empty()) { - if (!LoadDepFile(state, disk_interface, err)) { + if (!edge->rule_->depfile().empty()) { + if (!LoadDepFile(edge, err)) { if (!err->empty()) return false; EXPLAIN("Edge targets are dirty because depfile '%s' is missing", - EvaluateDepFile().c_str()); + edge->EvaluateDepFile().c_str()); dirty = true; } } @@ -50,10 +49,11 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface, // Visit all inputs; we're dirty if any of the inputs are dirty. TimeStamp most_recent_input = 1; Node* most_recent_node = NULL; - for (vector::iterator i = inputs_.begin(); i != inputs_.end(); ++i) { - if ((*i)->StatIfNecessary(disk_interface)) { - if (Edge* edge = (*i)->in_edge()) { - if (!edge->RecomputeDirty(state, disk_interface, err)) + for (vector::iterator i = edge->inputs_.begin(); + i != edge->inputs_.end(); ++i) { + if ((*i)->StatIfNecessary(disk_interface_)) { + if (Edge* in_edge = (*i)->in_edge()) { + if (!RecomputeDirty(in_edge, err)) return false; } else { // This input has no in-edge; it is dirty if it is missing. @@ -64,12 +64,12 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface, } // If an input is not ready, neither are our outputs. - if (Edge* edge = (*i)->in_edge()) { - if (!edge->outputs_ready_) - outputs_ready_ = false; + if (Edge* in_edge = (*i)->in_edge()) { + if (!in_edge->outputs_ready_) + edge->outputs_ready_ = false; } - if (!is_order_only(i - inputs_.begin())) { + if (!edge->is_order_only(i - edge->inputs_.begin())) { // If a regular input is dirty (or missing), we're dirty. // Otherwise consider mtime. if ((*i)->dirty()) { @@ -87,13 +87,13 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface, // We may also be dirty due to output state: missing outputs, out of // date outputs, etc. Visit all outputs and determine whether they're dirty. if (!dirty) { - BuildLog* build_log = state ? state->build_log_ : 0; - string command = EvaluateCommand(true); + string command = edge->EvaluateCommand(true); - for (vector::iterator i = outputs_.begin(); - i != outputs_.end(); ++i) { - (*i)->StatIfNecessary(disk_interface); - if (RecomputeOutputDirty(build_log, most_recent_input, most_recent_node, command, *i)) { + for (vector::iterator i = edge->outputs_.begin(); + i != edge->outputs_.end(); ++i) { + (*i)->StatIfNecessary(disk_interface_); + if (RecomputeOutputDirty(edge, most_recent_input, most_recent_node, + command, *i)) { dirty = true; break; } @@ -102,30 +102,33 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface, // Finally, visit each output to mark off that we've visited it, and update // their dirty state if necessary. - for (vector::iterator i = outputs_.begin(); i != outputs_.end(); ++i) { - (*i)->StatIfNecessary(disk_interface); + for (vector::iterator i = edge->outputs_.begin(); + i != edge->outputs_.end(); ++i) { + (*i)->StatIfNecessary(disk_interface_); if (dirty) (*i)->MarkDirty(); } - // If we're dirty, our outputs are normally not ready. (It's possible to be - // clean but still not be ready in the presence of order-only inputs.) - // But phony edges with no inputs have nothing to do, so are always ready. - if (dirty && !(is_phony() && inputs_.empty())) - outputs_ready_ = false; + // If an edge is dirty, its outputs are normally not ready. (It's + // possible to be clean but still not be ready in the presence of + // order-only inputs.) + // But phony edges with no inputs have nothing to do, so are always + // ready. + if (dirty && !(edge->is_phony() && edge->inputs_.empty())) + edge->outputs_ready_ = false; return true; } -bool Edge::RecomputeOutputDirty(BuildLog* build_log, - TimeStamp most_recent_input, - Node* most_recent_node, - const string& command, - Node* output) { - if (is_phony()) { +bool DependencyScan::RecomputeOutputDirty(Edge* edge, + TimeStamp most_recent_input, + Node* most_recent_node, + const string& command, + Node* output) { + if (edge->is_phony()) { // Phony edges don't write any output. Outputs are only dirty if // there are no inputs and we're missing the output. - return inputs_.empty() && !output->exists(); + return edge->inputs_.empty() && !output->exists(); } BuildLog::LogEntry* entry = 0; @@ -142,8 +145,8 @@ bool Edge::RecomputeOutputDirty(BuildLog* build_log, // rule in a previous run and stored the most recent input mtime in the // build log. Use that mtime instead, so that the file will only be // considered dirty if an input was modified since the previous run. - if (rule_->restat() && build_log && - (entry = build_log->LookupByOutput(output->path()))) { + if (edge->rule_->restat() && build_log() && + (entry = build_log()->LookupByOutput(output->path()))) { if (entry->restat_mtime < most_recent_input) { EXPLAIN("restat of output %s older than most recent input %s (%d vs %d)", output->path().c_str(), @@ -163,8 +166,8 @@ bool Edge::RecomputeOutputDirty(BuildLog* build_log, // 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. - if (!rule_->generator() && build_log) { - if (entry || (entry = build_log->LookupByOutput(output->path()))) { + if (!edge->rule_->generator() && build_log()) { + if (entry || (entry = build_log()->LookupByOutput(output->path()))) { if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) { EXPLAIN("command line changed for %s", output->path().c_str()); return true; @@ -272,11 +275,10 @@ string Edge::GetRspFileContent() { return rule_->rspfile_content().Evaluate(&env); } -bool Edge::LoadDepFile(State* state, DiskInterface* disk_interface, - string* err) { +bool DependencyScan::LoadDepFile(Edge* edge, string* err) { METRIC_RECORD("depfile load"); - string path = EvaluateDepFile(); - string content = disk_interface->ReadFile(path, err); + string path = edge->EvaluateDepFile(); + string content = disk_interface_->ReadFile(path, err); if (!err->empty()) return false; // On a missing depfile: return false and empty *err. @@ -290,18 +292,21 @@ bool Edge::LoadDepFile(State* state, DiskInterface* disk_interface, return false; } - // Check that this depfile matches our output. - StringPiece opath = StringPiece(outputs_[0]->path()); + // Check that this depfile matches the edge's output. + Node* first_output = edge->outputs_[0]; + StringPiece opath = StringPiece(first_output->path()); if (opath != depfile.out_) { *err = "expected depfile '" + path + "' to mention '" + - outputs_[0]->path() + "', got '" + depfile.out_.AsString() + "'"; + first_output->path() + "', got '" + depfile.out_.AsString() + "'"; return false; } - inputs_.insert(inputs_.end() - order_only_deps_, depfile.ins_.size(), 0); - implicit_deps_ += depfile.ins_.size(); + // Preallocate space in edge->inputs_ to be filled in below. + edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_, + depfile.ins_.size(), 0); + edge->implicit_deps_ += depfile.ins_.size(); vector::iterator implicit_dep = - inputs_.end() - order_only_deps_ - depfile.ins_.size(); + edge->inputs_.end() - edge->order_only_deps_ - depfile.ins_.size(); // Add all its in-edges. for (vector::iterator i = depfile.ins_.begin(); @@ -309,15 +314,15 @@ bool Edge::LoadDepFile(State* state, DiskInterface* disk_interface, if (!CanonicalizePath(const_cast(i->str_), &i->len_, err)) return false; - Node* node = state->GetNode(*i); + Node* node = state_->GetNode(*i); *implicit_dep = node; - node->AddOutEdge(this); + node->AddOutEdge(edge); // If we don't have a edge that generates this input already, // create one; this makes us not abort if the input is missing, // but instead will rebuild in that circumstance. if (!node->in_edge()) { - Edge* phony_edge = state->AddEdge(&State::kPhonyRule); + Edge* phony_edge = state_->AddEdge(&State::kPhonyRule); node->set_in_edge(phony_edge); phony_edge->outputs_.push_back(node); diff --git a/src/graph.h b/src/graph.h index f487a22..3e2e57a 100644 --- a/src/graph.h +++ b/src/graph.h @@ -20,6 +20,7 @@ using namespace std; #include "eval_env.h" +#include "state.h" #include "timestamp.h" struct DiskInterface; @@ -142,39 +143,25 @@ struct Edge { Edge() : rule_(NULL), env_(NULL), outputs_ready_(false), implicit_deps_(0), order_only_deps_(0) {} - /// Examine inputs, outputs, and command lines to judge whether this edge - /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_| - /// state accordingly. - /// Returns false on failure. - bool RecomputeDirty(State* state, DiskInterface* disk_interface, string* err); - - /// Recompute whether a given single output should be marked dirty. - /// Returns true if so. - bool RecomputeOutputDirty(BuildLog* build_log, TimeStamp most_recent_input, - Node* most_recent_node, const string& command, - Node* output); - /// Return true if all inputs' in-edges are ready. bool AllInputsReady() const; /// Expand all variables in a command and return it as a string. - /// If incl_rsp_file is enabled, the string will also contain the + /// If incl_rsp_file is enabled, the string will also contain the /// full contents of a response file (if applicable) string EvaluateCommand(bool incl_rsp_file = false); // XXX move to env, take env ptr string EvaluateDepFile(); string GetDescription(); - + /// Does the edge use a response file? bool HasRspFile(); - + /// Get the path to the response file string GetRspFile(); /// Get the contents of the response file string GetRspFileContent(); - bool LoadDepFile(State* state, DiskInterface* disk_interface, string* err); - void Dump(const char* prefix="") const; const Rule* rule_; @@ -210,4 +197,32 @@ struct Edge { bool is_phony() const; }; + +/// DependencyScan manages the process of scanning the files in a graph +/// and updating the dirty/outputs_ready state of all the nodes and edges. +struct DependencyScan { + DependencyScan(State* state, DiskInterface* disk_interface) + : state_(state), disk_interface_(disk_interface) {} + + /// Examine inputs, outputs, and command lines to judge whether an edge + /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_| + /// state accordingly. + /// Returns false on failure. + bool RecomputeDirty(Edge* edge, string* err); + + /// Recompute whether a given single output should be marked dirty. + /// Returns true if so. + bool RecomputeOutputDirty(Edge* edge, TimeStamp most_recent_input, + Node* most_recent_node, + const string& command, Node* output); + + bool LoadDepFile(Edge* edge, string* err); + + State* state_; + DiskInterface* disk_interface_; + BuildLog* build_log() const { + return state_->build_log_; + } +}; + #endif // NINJA_GRAPH_H_ diff --git a/src/graph_test.cc b/src/graph_test.cc index 4b41f8a..2bc0c17 100644 --- a/src/graph_test.cc +++ b/src/graph_test.cc @@ -17,7 +17,10 @@ #include "test.h" struct GraphTest : public StateTestWithBuiltinRules { + GraphTest() : scan_(&state_, &fs_) {} + VirtualFileSystem fs_; + DependencyScan scan_; }; TEST_F(GraphTest, MissingImplicit) { @@ -28,7 +31,7 @@ TEST_F(GraphTest, MissingImplicit) { Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(edge->RecomputeDirty(&state_, &fs_, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); ASSERT_EQ("", err); // A missing implicit dep *should* make the output dirty. @@ -46,7 +49,7 @@ TEST_F(GraphTest, ModifiedImplicit) { Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(edge->RecomputeDirty(&state_, &fs_, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); ASSERT_EQ("", err); // A modified implicit dep should make the output dirty. @@ -66,7 +69,7 @@ TEST_F(GraphTest, FunkyMakefilePath) { Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(edge->RecomputeDirty(&state_, &fs_, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); ASSERT_EQ("", err); // implicit.h has changed, though our depfile refers to it with a @@ -89,7 +92,7 @@ TEST_F(GraphTest, ExplicitImplicit) { Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(edge->RecomputeDirty(&state_, &fs_, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); ASSERT_EQ("", err); // We have both an implicit and an explicit dep on implicit.h. @@ -110,7 +113,7 @@ TEST_F(GraphTest, PathWithCurrentDirectory) { Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(edge->RecomputeDirty(&state_, &fs_, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); ASSERT_EQ("", err); EXPECT_FALSE(GetNode("out.o")->dirty()); @@ -154,7 +157,7 @@ TEST_F(GraphTest, DepfileWithCanonicalizablePath) { Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(edge->RecomputeDirty(&state_, &fs_, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); ASSERT_EQ("", err); EXPECT_FALSE(GetNode("out.o")->dirty()); @@ -174,13 +177,13 @@ TEST_F(GraphTest, DepfileRemoved) { Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(edge->RecomputeDirty(&state_, &fs_, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); ASSERT_EQ("", err); EXPECT_FALSE(GetNode("out.o")->dirty()); state_.Reset(); fs_.RemoveFile("out.o.d"); - EXPECT_TRUE(edge->RecomputeDirty(&state_, &fs_, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out.o")->dirty()); } -- 2.7.4