1 // Copyright 2011 Google Inc. All Rights Reserved.
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
7 // http://www.apache.org/licenses/LICENSE-2.0
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
20 #include "build_log.h"
21 #include "debug_flags.h"
22 #include "depfile_parser.h"
24 #include "disk_interface.h"
25 #include "manifest_parser.h"
30 bool Node::Stat(DiskInterface* disk_interface) {
31 METRIC_RECORD("node stat");
32 mtime_ = disk_interface->Stat(path_);
36 bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
38 edge->outputs_ready_ = true;
39 edge->deps_missing_ = false;
41 // RecomputeDirty() recursively walks the graph following the input nodes
42 // of |edge| and the in_edges of these nodes. It uses the stat state of each
43 // node to mark nodes as visited and doesn't traverse across nodes that have
44 // been visited already. To make sure that every edge is visited only once
45 // (important because an edge's deps are loaded every time it's visited), mark
46 // all outputs of |edge| visited as a first step. This ensures that edges
47 // with multiple inputs and outputs are visited only once, even in cyclic
49 for (vector<Node*>::iterator o = edge->outputs_.begin();
50 o != edge->outputs_.end(); ++o) {
51 (*o)->StatIfNecessary(disk_interface_);
54 if (!dep_loader_.LoadDeps(edge, err)) {
57 // Failed to load dependency info: rebuild to regenerate it.
58 dirty = edge->deps_missing_ = true;
61 // Visit all inputs; we're dirty if any of the inputs are dirty.
62 Node* most_recent_input = NULL;
63 for (vector<Node*>::iterator i = edge->inputs_.begin();
64 i != edge->inputs_.end(); ++i) {
65 if ((*i)->StatIfNecessary(disk_interface_)) {
66 if (Edge* in_edge = (*i)->in_edge()) {
67 if (!RecomputeDirty(in_edge, err))
70 // This input has no in-edge; it is dirty if it is missing.
72 EXPLAIN("%s has no in-edge and is missing", (*i)->path().c_str());
73 (*i)->set_dirty(!(*i)->exists());
77 // If an input is not ready, neither are our outputs.
78 if (Edge* in_edge = (*i)->in_edge()) {
79 if (!in_edge->outputs_ready_)
80 edge->outputs_ready_ = false;
83 if (!edge->is_order_only(i - edge->inputs_.begin())) {
84 // If a regular input is dirty (or missing), we're dirty.
85 // Otherwise consider mtime.
87 EXPLAIN("%s is dirty", (*i)->path().c_str());
90 if (!most_recent_input || (*i)->mtime() > most_recent_input->mtime()) {
91 most_recent_input = *i;
97 // We may also be dirty due to output state: missing outputs, out of
98 // date outputs, etc. Visit all outputs and determine whether they're dirty.
100 dirty = RecomputeOutputsDirty(edge, most_recent_input);
102 // Finally, visit each output and update their dirty state if necessary.
103 for (vector<Node*>::iterator o = edge->outputs_.begin();
104 o != edge->outputs_.end(); ++o) {
109 // If an edge is dirty, its outputs are normally not ready. (It's
110 // possible to be clean but still not be ready in the presence of
111 // order-only inputs.)
112 // But phony edges with no inputs have nothing to do, so are always
114 if (dirty && !(edge->is_phony() && edge->inputs_.empty()))
115 edge->outputs_ready_ = false;
120 bool DependencyScan::RecomputeOutputsDirty(Edge* edge,
121 Node* most_recent_input) {
122 string command = edge->EvaluateCommand(/*incl_rsp_file=*/true);
123 for (vector<Node*>::iterator o = edge->outputs_.begin();
124 o != edge->outputs_.end(); ++o) {
125 (*o)->StatIfNecessary(disk_interface_);
126 if (RecomputeOutputDirty(edge, most_recent_input, command, *o))
132 bool DependencyScan::RecomputeOutputDirty(Edge* edge,
133 Node* most_recent_input,
134 const string& command,
136 if (edge->is_phony()) {
137 // Phony edges don't write any output. Outputs are only dirty if
138 // there are no inputs and we're missing the output.
139 return edge->inputs_.empty() && !output->exists();
142 BuildLog::LogEntry* entry = 0;
144 // Dirty if we're missing the output.
145 if (!output->exists()) {
146 EXPLAIN("output %s doesn't exist", output->path().c_str());
150 // Dirty if the output is older than the input.
151 if (most_recent_input && output->mtime() < most_recent_input->mtime()) {
152 TimeStamp output_mtime = output->mtime();
154 // If this is a restat rule, we may have cleaned the output with a restat
155 // rule in a previous run and stored the most recent input mtime in the
156 // build log. Use that mtime instead, so that the file will only be
157 // considered dirty if an input was modified since the previous run.
158 bool used_restat = false;
159 if (edge->GetBindingBool("restat") && build_log() &&
160 (entry = build_log()->LookupByOutput(output->path()))) {
161 output_mtime = entry->restat_mtime;
165 if (output_mtime < most_recent_input->mtime()) {
166 EXPLAIN("%soutput %s older than most recent input %s "
168 used_restat ? "restat of " : "", output->path().c_str(),
169 most_recent_input->path().c_str(),
170 output_mtime, most_recent_input->mtime());
175 // May also be dirty due to the command changing since the last build.
176 // But if this is a generator rule, the command changing does not make us
178 if (!edge->GetBindingBool("generator") && build_log()) {
179 if (entry || (entry = build_log()->LookupByOutput(output->path()))) {
180 if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
181 EXPLAIN("command line changed for %s", output->path().c_str());
186 EXPLAIN("command line not found in log for %s", output->path().c_str());
194 bool Edge::AllInputsReady() const {
195 for (vector<Node*>::const_iterator i = inputs_.begin();
196 i != inputs_.end(); ++i) {
197 if ((*i)->in_edge() && !(*i)->in_edge()->outputs_ready())
203 /// An Env for an Edge, providing $in and $out.
204 struct EdgeEnv : public Env {
205 enum EscapeKind { kShellEscape, kDoNotEscape };
207 EdgeEnv(Edge* edge, EscapeKind escape)
208 : edge_(edge), escape_in_out_(escape) {}
209 virtual string LookupVariable(const string& var);
210 virtual const Rule* LookupRule(const string& rule_name);
212 /// Given a span of Nodes, construct a list of paths suitable for a command
214 string MakePathList(vector<Node*>::iterator begin,
215 vector<Node*>::iterator end,
219 EscapeKind escape_in_out_;
222 const Rule* EdgeEnv::LookupRule(const string& rule_name) {
226 string EdgeEnv::LookupVariable(const string& var) {
227 if (var == "in" || var == "in_newline") {
228 int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ -
229 edge_->order_only_deps_;
230 return MakePathList(edge_->inputs_.begin(),
231 edge_->inputs_.begin() + explicit_deps_count,
232 var == "in" ? ' ' : '\n');
233 } else if (var == "out") {
234 return MakePathList(edge_->outputs_.begin(),
235 edge_->outputs_.end(),
239 // See notes on BindingEnv::LookupWithFallback.
240 const EvalString* eval = edge_->rule_->GetBinding(var);
241 return edge_->env_->LookupWithFallback(var, eval, this);
244 string EdgeEnv::MakePathList(vector<Node*>::iterator begin,
245 vector<Node*>::iterator end,
248 for (vector<Node*>::iterator i = begin; i != end; ++i) {
250 result.push_back(sep);
251 const string& path = (*i)->PathDecanonicalized();
252 if (escape_in_out_ == kShellEscape) {
254 GetWin32EscapedString(path, &result);
256 GetShellEscapedString(path, &result);
265 string Edge::EvaluateCommand(bool incl_rsp_file) {
266 string command = GetBinding("command");
268 string rspfile_content = GetBinding("rspfile_content");
269 if (!rspfile_content.empty())
270 command += ";rspfile=" + rspfile_content;
275 string Edge::GetBinding(const string& key) {
276 EdgeEnv env(this, EdgeEnv::kShellEscape);
277 return env.LookupVariable(key);
280 bool Edge::GetBindingBool(const string& key) {
281 return !GetBinding(key).empty();
284 string Edge::GetUnescapedDepfile() {
285 EdgeEnv env(this, EdgeEnv::kDoNotEscape);
286 return env.LookupVariable("depfile");
289 string Edge::GetUnescapedRspfile() {
290 EdgeEnv env(this, EdgeEnv::kDoNotEscape);
291 return env.LookupVariable("rspfile");
294 void Edge::Dump(const char* prefix) const {
295 printf("%s[ ", prefix);
296 for (vector<Node*>::const_iterator i = inputs_.begin();
297 i != inputs_.end() && *i != NULL; ++i) {
298 printf("%s ", (*i)->path().c_str());
300 printf("--%s-> ", rule_->name().c_str());
301 for (vector<Node*>::const_iterator i = outputs_.begin();
302 i != outputs_.end() && *i != NULL; ++i) {
303 printf("%s ", (*i)->path().c_str());
306 if (!pool_->name().empty()) {
307 printf("(in pool '%s')", pool_->name().c_str());
310 printf("(null pool?)");
312 printf("] 0x%p\n", this);
315 bool Edge::is_phony() const {
316 return rule_ == &State::kPhonyRule;
319 bool Edge::use_console() const {
320 return pool() == &State::kConsolePool;
323 string Node::PathDecanonicalized() const {
324 string result = path_;
326 unsigned int mask = 1;
327 for (char* c = &result[0]; (c = strchr(c, '/')) != NULL;) {
328 if (slash_bits_ & mask)
337 void Node::Dump(const char* prefix) const {
338 printf("%s <%s 0x%p> mtime: %d%s, (:%s), ",
339 prefix, path().c_str(), this,
340 mtime(), mtime() ? "" : " (:missing)",
341 dirty() ? " dirty" : " clean");
343 in_edge()->Dump("in-edge: ");
345 printf("no in-edge\n");
347 printf(" out edges:\n");
348 for (vector<Edge*>::const_iterator e = out_edges().begin();
349 e != out_edges().end() && *e != NULL; ++e) {
354 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
355 string deps_type = edge->GetBinding("deps");
356 if (!deps_type.empty())
357 return LoadDepsFromLog(edge, err);
359 string depfile = edge->GetUnescapedDepfile();
360 if (!depfile.empty())
361 return LoadDepFile(edge, depfile, err);
367 bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
369 METRIC_RECORD("depfile load");
370 string content = disk_interface_->ReadFile(path, err);
372 *err = "loading '" + path + "': " + *err;
375 // On a missing depfile: return false and empty *err.
376 if (content.empty()) {
377 EXPLAIN("depfile '%s' is missing", path.c_str());
381 DepfileParser depfile;
383 if (!depfile.Parse(&content, &depfile_err)) {
384 *err = path + ": " + depfile_err;
389 if (!CanonicalizePath(const_cast<char*>(depfile.out_.str_),
390 &depfile.out_.len_, &unused, err))
393 // Check that this depfile matches the edge's output, if not return false to
394 // mark the edge as dirty.
395 Node* first_output = edge->outputs_[0];
396 StringPiece opath = StringPiece(first_output->path());
397 if (opath != depfile.out_) {
398 EXPLAIN("expected depfile '%s' to mention '%s', got '%s'", path.c_str(),
399 first_output->path().c_str(), depfile.out_.AsString().c_str());
403 // Preallocate space in edge->inputs_ to be filled in below.
404 vector<Node*>::iterator implicit_dep =
405 PreallocateSpace(edge, depfile.ins_.size());
407 // Add all its in-edges.
408 for (vector<StringPiece>::iterator i = depfile.ins_.begin();
409 i != depfile.ins_.end(); ++i, ++implicit_dep) {
410 unsigned int slash_bits;
411 if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits,
415 Node* node = state_->GetNode(*i, slash_bits);
416 *implicit_dep = node;
417 node->AddOutEdge(edge);
418 CreatePhonyInEdge(node);
424 bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, string* err) {
425 // NOTE: deps are only supported for single-target edges.
426 Node* output = edge->outputs_[0];
427 DepsLog::Deps* deps = deps_log_->GetDeps(output);
429 EXPLAIN("deps for '%s' are missing", output->path().c_str());
433 // Deps are invalid if the output is newer than the deps.
434 if (output->mtime() > deps->mtime) {
435 EXPLAIN("stored deps info out of date for '%s' (%d vs %d)",
436 output->path().c_str(), deps->mtime, output->mtime());
440 vector<Node*>::iterator implicit_dep =
441 PreallocateSpace(edge, deps->node_count);
442 for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) {
443 Node* node = deps->nodes[i];
444 *implicit_dep = node;
445 node->AddOutEdge(edge);
446 CreatePhonyInEdge(node);
451 vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge,
453 edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
455 edge->implicit_deps_ += count;
456 return edge->inputs_.end() - edge->order_only_deps_ - count;
459 void ImplicitDepLoader::CreatePhonyInEdge(Node* node) {
463 Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
464 node->set_in_edge(phony_edge);
465 phony_edge->outputs_.push_back(node);
467 // RecomputeDirty might not be called for phony_edge if a previous call
468 // to RecomputeDirty had caused the file to be stat'ed. Because previous
469 // invocations of RecomputeDirty would have seen this node without an
470 // input edge (and therefore ready), we have to set outputs_ready_ to true
471 // to avoid a potential stuck build. If we do call RecomputeDirty for
472 // this node, it will simply set outputs_ready_ to the correct value.
473 phony_edge->outputs_ready_ = true;