| // Copyright 2011 Google Inc. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "graph.h" |
| |
| #include <assert.h> |
| #include <stdio.h> |
| |
| #include "build_log.h" |
| #include "depfile_parser.h" |
| #include "deps_log.h" |
| #include "disk_interface.h" |
| #include "explain.h" |
| #include "manifest_parser.h" |
| #include "metrics.h" |
| #include "state.h" |
| #include "util.h" |
| |
| bool Node::Stat(DiskInterface* disk_interface) { |
| METRIC_RECORD("node stat"); |
| mtime_ = disk_interface->Stat(path_); |
| return mtime_ > 0; |
| } |
| |
| void Rule::AddBinding(const string& key, const EvalString& val) { |
| bindings_[key] = val; |
| } |
| |
| const EvalString* Rule::GetBinding(const string& key) const { |
| map<string, EvalString>::const_iterator i = bindings_.find(key); |
| if (i == bindings_.end()) |
| return NULL; |
| return &i->second; |
| } |
| |
| // static |
| bool Rule::IsReservedBinding(const string& var) { |
| return var == "command" || |
| var == "depfile" || |
| var == "description" || |
| var == "deps" || |
| var == "generator" || |
| var == "pool" || |
| var == "restat" || |
| var == "rspfile" || |
| var == "rspfile_content"; |
| } |
| |
| bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { |
| bool dirty = false; |
| edge->outputs_ready_ = true; |
| |
| TimeStamp deps_mtime = 0; |
| if (!dep_loader_.LoadDeps(edge, &deps_mtime, err)) { |
| if (!err->empty()) |
| return false; |
| // Failed to load dependency info: rebuild to regenerate it. |
| dirty = true; |
| } |
| |
| // Visit all inputs; we're dirty if any of the inputs are dirty. |
| Node* most_recent_input = NULL; |
| for (vector<Node*>::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. |
| if (!(*i)->exists()) |
| EXPLAIN("%s has no in-edge and is missing", (*i)->path().c_str()); |
| (*i)->set_dirty(!(*i)->exists()); |
| } |
| } |
| |
| // If an input is not ready, neither are our outputs. |
| if (Edge* in_edge = (*i)->in_edge()) { |
| if (!in_edge->outputs_ready_) |
| edge->outputs_ready_ = false; |
| } |
| |
| 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()) { |
| EXPLAIN("%s is dirty", (*i)->path().c_str()); |
| dirty = true; |
| } else { |
| if (!most_recent_input || (*i)->mtime() > most_recent_input->mtime()) { |
| most_recent_input = *i; |
| } |
| } |
| } |
| } |
| |
| // 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) { |
| string command = edge->EvaluateCommand(true); |
| |
| for (vector<Node*>::iterator i = edge->outputs_.begin(); |
| i != edge->outputs_.end(); ++i) { |
| (*i)->StatIfNecessary(disk_interface_); |
| if (RecomputeOutputDirty(edge, most_recent_input, deps_mtime, |
| command, *i)) { |
| dirty = true; |
| break; |
| } |
| } |
| } |
| |
| // Finally, visit each output to mark off that we've visited it, and update |
| // their dirty state if necessary. |
| for (vector<Node*>::iterator i = edge->outputs_.begin(); |
| i != edge->outputs_.end(); ++i) { |
| (*i)->StatIfNecessary(disk_interface_); |
| if (dirty) |
| (*i)->MarkDirty(); |
| } |
| |
| // 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 DependencyScan::RecomputeOutputDirty(Edge* edge, |
| Node* most_recent_input, |
| TimeStamp deps_mtime, |
| 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 edge->inputs_.empty() && !output->exists(); |
| } |
| |
| BuildLog::LogEntry* entry = 0; |
| |
| // Dirty if we're missing the output. |
| if (!output->exists()) { |
| EXPLAIN("output %s doesn't exist", output->path().c_str()); |
| return true; |
| } |
| |
| // Dirty if the output is older than the input. |
| if (most_recent_input && output->mtime() < most_recent_input->mtime()) { |
| TimeStamp output_mtime = output->mtime(); |
| |
| // If this is a restat rule, we may have cleaned the output with a restat |
| // 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. |
| bool used_restat = false; |
| if (edge->GetBindingBool("restat") && build_log() && |
| (entry = build_log()->LookupByOutput(output->path()))) { |
| output_mtime = entry->restat_mtime; |
| used_restat = true; |
| } |
| |
| if (output_mtime < most_recent_input->mtime()) { |
| EXPLAIN("%soutput %s older than most recent input %s " |
| "(%d vs %d)", |
| used_restat ? "restat of " : "", output->path().c_str(), |
| most_recent_input->path().c_str(), |
| output_mtime, most_recent_input->mtime()); |
| return true; |
| } |
| } |
| |
| // Dirty if the output is newer than the deps. |
| if (deps_mtime && output->mtime() > deps_mtime) { |
| EXPLAIN("stored deps info out of date for for %s (%d vs %d)", |
| output->path().c_str(), deps_mtime, output->mtime()); |
| return true; |
| } |
| |
| // 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 (!edge->GetBindingBool("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; |
| } |
| } |
| if (!entry) { |
| EXPLAIN("command line not found in log for %s", output->path().c_str()); |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| bool Edge::AllInputsReady() const { |
| for (vector<Node*>::const_iterator i = inputs_.begin(); |
| i != inputs_.end(); ++i) { |
| if ((*i)->in_edge() && !(*i)->in_edge()->outputs_ready()) |
| return false; |
| } |
| return true; |
| } |
| |
| /// An Env for an Edge, providing $in and $out. |
| struct EdgeEnv : public Env { |
| explicit EdgeEnv(Edge* edge) : edge_(edge) {} |
| virtual string LookupVariable(const string& var); |
| |
| /// Given a span of Nodes, construct a list of paths suitable for a command |
| /// line. |
| string MakePathList(vector<Node*>::iterator begin, |
| vector<Node*>::iterator end, |
| char sep); |
| |
| Edge* edge_; |
| }; |
| |
| string EdgeEnv::LookupVariable(const string& var) { |
| if (var == "in" || var == "in_newline") { |
| int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ - |
| edge_->order_only_deps_; |
| return MakePathList(edge_->inputs_.begin(), |
| edge_->inputs_.begin() + explicit_deps_count, |
| var == "in" ? ' ' : '\n'); |
| } else if (var == "out") { |
| return MakePathList(edge_->outputs_.begin(), |
| edge_->outputs_.end(), |
| ' '); |
| } |
| |
| // See notes on BindingEnv::LookupWithFallback. |
| const EvalString* eval = edge_->rule_->GetBinding(var); |
| return edge_->env_->LookupWithFallback(var, eval, this); |
| } |
| |
| string EdgeEnv::MakePathList(vector<Node*>::iterator begin, |
| vector<Node*>::iterator end, |
| char sep) { |
| string result; |
| for (vector<Node*>::iterator i = begin; i != end; ++i) { |
| if (!result.empty()) |
| result.push_back(sep); |
| const string& path = (*i)->path(); |
| if (path.find(" ") != string::npos) { |
| result.append("\""); |
| result.append(path); |
| result.append("\""); |
| } else { |
| result.append(path); |
| } |
| } |
| return result; |
| } |
| |
| string Edge::EvaluateCommand(bool incl_rsp_file) { |
| string command = GetBinding("command"); |
| if (incl_rsp_file) { |
| string rspfile_content = GetBinding("rspfile_content"); |
| if (!rspfile_content.empty()) |
| command += ";rspfile=" + rspfile_content; |
| } |
| return command; |
| } |
| |
| string Edge::GetBinding(const string& key) { |
| EdgeEnv env(this); |
| return env.LookupVariable(key); |
| } |
| |
| bool Edge::GetBindingBool(const string& key) { |
| return !GetBinding(key).empty(); |
| } |
| |
| void Edge::Dump(const char* prefix) const { |
| printf("%s[ ", prefix); |
| for (vector<Node*>::const_iterator i = inputs_.begin(); |
| i != inputs_.end() && *i != NULL; ++i) { |
| printf("%s ", (*i)->path().c_str()); |
| } |
| printf("--%s-> ", rule_->name().c_str()); |
| for (vector<Node*>::const_iterator i = outputs_.begin(); |
| i != outputs_.end() && *i != NULL; ++i) { |
| printf("%s ", (*i)->path().c_str()); |
| } |
| if (pool_) { |
| if (!pool_->name().empty()) { |
| printf("(in pool '%s')", pool_->name().c_str()); |
| } |
| } else { |
| printf("(null pool?)"); |
| } |
| printf("] 0x%p\n", this); |
| } |
| |
| bool Edge::is_phony() const { |
| return rule_ == &State::kPhonyRule; |
| } |
| |
| void Node::Dump(const char* prefix) const { |
| printf("%s <%s 0x%p> mtime: %d%s, (:%s), ", |
| prefix, path().c_str(), this, |
| mtime(), mtime() ? "" : " (:missing)", |
| dirty() ? " dirty" : " clean"); |
| if (in_edge()) { |
| in_edge()->Dump("in-edge: "); |
| } else { |
| printf("no in-edge\n"); |
| } |
| printf(" out edges:\n"); |
| for (vector<Edge*>::const_iterator e = out_edges().begin(); |
| e != out_edges().end() && *e != NULL; ++e) { |
| (*e)->Dump(" +- "); |
| } |
| } |
| |
| bool ImplicitDepLoader::LoadDeps(Edge* edge, TimeStamp* mtime, string* err) { |
| string deps_type = edge->GetBinding("deps"); |
| if (!deps_type.empty()) { |
| if (!LoadDepsFromLog(edge, mtime, err)) { |
| if (!err->empty()) |
| return false; |
| EXPLAIN("deps for %s are missing", edge->outputs_[0]->path().c_str()); |
| return false; |
| } |
| return true; |
| } |
| |
| string depfile = edge->GetBinding("depfile"); |
| if (!depfile.empty()) { |
| if (!LoadDepFile(edge, depfile, err)) { |
| if (!err->empty()) |
| return false; |
| EXPLAIN("depfile '%s' is missing", depfile.c_str()); |
| return false; |
| } |
| return true; |
| } |
| |
| // No deps to load. |
| return true; |
| } |
| |
| bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path, |
| string* err) { |
| METRIC_RECORD("depfile load"); |
| string content = disk_interface_->ReadFile(path, err); |
| if (!err->empty()) { |
| *err = "loading '" + path + "': " + *err; |
| return false; |
| } |
| // On a missing depfile: return false and empty *err. |
| if (content.empty()) |
| return false; |
| |
| DepfileParser depfile; |
| string depfile_err; |
| if (!depfile.Parse(&content, &depfile_err)) { |
| *err = path + ": " + depfile_err; |
| return false; |
| } |
| |
| // 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 '" + |
| first_output->path() + "', got '" + depfile.out_.AsString() + "'"; |
| return false; |
| } |
| |
| // Preallocate space in edge->inputs_ to be filled in below. |
| vector<Node*>::iterator implicit_dep = |
| PreallocateSpace(edge, depfile.ins_.size()); |
| |
| // Add all its in-edges. |
| for (vector<StringPiece>::iterator i = depfile.ins_.begin(); |
| i != depfile.ins_.end(); ++i, ++implicit_dep) { |
| if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, err)) |
| return false; |
| |
| Node* node = state_->GetNode(*i); |
| *implicit_dep = node; |
| node->AddOutEdge(edge); |
| CreatePhonyInEdge(node); |
| } |
| |
| return true; |
| } |
| |
| bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, TimeStamp* deps_mtime, |
| string* err) { |
| DepsLog::Deps* deps = deps_log_->GetDeps(edge->outputs_[0]); |
| if (!deps) |
| return false; |
| |
| *deps_mtime = deps->mtime; |
| |
| vector<Node*>::iterator implicit_dep = |
| PreallocateSpace(edge, deps->node_count); |
| for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) { |
| *implicit_dep = deps->nodes[i]; |
| CreatePhonyInEdge(*implicit_dep); |
| } |
| return true; |
| } |
| |
| vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge, |
| int count) { |
| edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_, |
| (size_t)count, 0); |
| edge->implicit_deps_ += count; |
| return edge->inputs_.end() - edge->order_only_deps_ - count; |
| } |
| |
| void ImplicitDepLoader::CreatePhonyInEdge(Node* node) { |
| if (node->in_edge()) |
| return; |
| |
| Edge* phony_edge = state_->AddEdge(&State::kPhonyRule); |
| node->set_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; |
| } |