Ninja
graph.cc
Go to the documentation of this file.
1 // Copyright 2011 Google Inc. All Rights Reserved.
2 //
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
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
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.
14 
15 #include "graph.h"
16 
17 #include <assert.h>
18 #include <stdio.h>
19 
20 #include "build_log.h"
21 #include "debug_flags.h"
22 #include "depfile_parser.h"
23 #include "deps_log.h"
24 #include "disk_interface.h"
25 #include "manifest_parser.h"
26 #include "metrics.h"
27 #include "state.h"
28 #include "util.h"
29 
30 bool Node::Stat(DiskInterface* disk_interface) {
31  METRIC_RECORD("node stat");
32  mtime_ = disk_interface->Stat(path_);
33  return mtime_ > 0;
34 }
35 
36 void Rule::AddBinding(const string& key, const EvalString& val) {
37  bindings_[key] = val;
38 }
39 
40 const EvalString* Rule::GetBinding(const string& key) const {
41  map<string, EvalString>::const_iterator i = bindings_.find(key);
42  if (i == bindings_.end())
43  return NULL;
44  return &i->second;
45 }
46 
47 // static
48 bool Rule::IsReservedBinding(const string& var) {
49  return var == "command" ||
50  var == "depfile" ||
51  var == "description" ||
52  var == "deps" ||
53  var == "generator" ||
54  var == "pool" ||
55  var == "restat" ||
56  var == "rspfile" ||
57  var == "rspfile_content";
58 }
59 
60 bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
61  bool dirty = false;
62  edge->outputs_ready_ = true;
63  edge->deps_missing_ = false;
64 
65  if (!dep_loader_.LoadDeps(edge, err)) {
66  if (!err->empty())
67  return false;
68  // Failed to load dependency info: rebuild to regenerate it.
69  dirty = edge->deps_missing_ = true;
70  }
71 
72  // Visit all inputs; we're dirty if any of the inputs are dirty.
73  Node* most_recent_input = NULL;
74  for (vector<Node*>::iterator i = edge->inputs_.begin();
75  i != edge->inputs_.end(); ++i) {
76  if ((*i)->StatIfNecessary(disk_interface_)) {
77  if (Edge* in_edge = (*i)->in_edge()) {
78  if (!RecomputeDirty(in_edge, err))
79  return false;
80  } else {
81  // This input has no in-edge; it is dirty if it is missing.
82  if (!(*i)->exists())
83  EXPLAIN("%s has no in-edge and is missing", (*i)->path().c_str());
84  (*i)->set_dirty(!(*i)->exists());
85  }
86  }
87 
88  // If an input is not ready, neither are our outputs.
89  if (Edge* in_edge = (*i)->in_edge()) {
90  if (!in_edge->outputs_ready_)
91  edge->outputs_ready_ = false;
92  }
93 
94  if (!edge->is_order_only(i - edge->inputs_.begin())) {
95  // If a regular input is dirty (or missing), we're dirty.
96  // Otherwise consider mtime.
97  if ((*i)->dirty()) {
98  EXPLAIN("%s is dirty", (*i)->path().c_str());
99  dirty = true;
100  } else {
101  if (!most_recent_input || (*i)->mtime() > most_recent_input->mtime()) {
102  most_recent_input = *i;
103  }
104  }
105  }
106  }
107 
108  // We may also be dirty due to output state: missing outputs, out of
109  // date outputs, etc. Visit all outputs and determine whether they're dirty.
110  if (!dirty)
111  dirty = RecomputeOutputsDirty(edge, most_recent_input);
112 
113  // Finally, visit each output to mark off that we've visited it, and update
114  // their dirty state if necessary.
115  for (vector<Node*>::iterator i = edge->outputs_.begin();
116  i != edge->outputs_.end(); ++i) {
117  (*i)->StatIfNecessary(disk_interface_);
118  if (dirty)
119  (*i)->MarkDirty();
120  }
121 
122  // If an edge is dirty, its outputs are normally not ready. (It's
123  // possible to be clean but still not be ready in the presence of
124  // order-only inputs.)
125  // But phony edges with no inputs have nothing to do, so are always
126  // ready.
127  if (dirty && !(edge->is_phony() && edge->inputs_.empty()))
128  edge->outputs_ready_ = false;
129 
130  return true;
131 }
132 
134  Node* most_recent_input) {
135  string command = edge->EvaluateCommand(true);
136  for (vector<Node*>::iterator i = edge->outputs_.begin();
137  i != edge->outputs_.end(); ++i) {
138  (*i)->StatIfNecessary(disk_interface_);
139  if (RecomputeOutputDirty(edge, most_recent_input, command, *i))
140  return true;
141  }
142  return false;
143 }
144 
146  Node* most_recent_input,
147  const string& command,
148  Node* output) {
149  if (edge->is_phony()) {
150  // Phony edges don't write any output. Outputs are only dirty if
151  // there are no inputs and we're missing the output.
152  return edge->inputs_.empty() && !output->exists();
153  }
154 
155  BuildLog::LogEntry* entry = 0;
156 
157  // Dirty if we're missing the output.
158  if (!output->exists()) {
159  EXPLAIN("output %s doesn't exist", output->path().c_str());
160  return true;
161  }
162 
163  // Dirty if the output is older than the input.
164  if (most_recent_input && output->mtime() < most_recent_input->mtime()) {
165  TimeStamp output_mtime = output->mtime();
166 
167  // If this is a restat rule, we may have cleaned the output with a restat
168  // rule in a previous run and stored the most recent input mtime in the
169  // build log. Use that mtime instead, so that the file will only be
170  // considered dirty if an input was modified since the previous run.
171  bool used_restat = false;
172  if (edge->GetBindingBool("restat") && build_log() &&
173  (entry = build_log()->LookupByOutput(output->path()))) {
174  output_mtime = entry->restat_mtime;
175  used_restat = true;
176  }
177 
178  if (output_mtime < most_recent_input->mtime()) {
179  EXPLAIN("%soutput %s older than most recent input %s "
180  "(%d vs %d)",
181  used_restat ? "restat of " : "", output->path().c_str(),
182  most_recent_input->path().c_str(),
183  output_mtime, most_recent_input->mtime());
184  return true;
185  }
186  }
187 
188  // May also be dirty due to the command changing since the last build.
189  // But if this is a generator rule, the command changing does not make us
190  // dirty.
191  if (!edge->GetBindingBool("generator") && build_log()) {
192  if (entry || (entry = build_log()->LookupByOutput(output->path()))) {
193  if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
194  EXPLAIN("command line changed for %s", output->path().c_str());
195  return true;
196  }
197  }
198  if (!entry) {
199  EXPLAIN("command line not found in log for %s", output->path().c_str());
200  return true;
201  }
202  }
203 
204  return false;
205 }
206 
207 bool Edge::AllInputsReady() const {
208  for (vector<Node*>::const_iterator i = inputs_.begin();
209  i != inputs_.end(); ++i) {
210  if ((*i)->in_edge() && !(*i)->in_edge()->outputs_ready())
211  return false;
212  }
213  return true;
214 }
215 
216 /// An Env for an Edge, providing $in and $out.
217 struct EdgeEnv : public Env {
219 
220  explicit EdgeEnv(Edge* edge, EscapeKind escape)
221  : edge_(edge), escape_in_out_(escape) {}
222  virtual string LookupVariable(const string& var);
223 
224  /// Given a span of Nodes, construct a list of paths suitable for a command
225  /// line.
226  string MakePathList(vector<Node*>::iterator begin,
227  vector<Node*>::iterator end,
228  char sep);
229 
232 };
233 
234 string EdgeEnv::LookupVariable(const string& var) {
235  if (var == "in" || var == "in_newline") {
236  int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ -
238  return MakePathList(edge_->inputs_.begin(),
239  edge_->inputs_.begin() + explicit_deps_count,
240  var == "in" ? ' ' : '\n');
241  } else if (var == "out") {
242  return MakePathList(edge_->outputs_.begin(),
243  edge_->outputs_.end(),
244  ' ');
245  }
246 
247  // See notes on BindingEnv::LookupWithFallback.
248  const EvalString* eval = edge_->rule_->GetBinding(var);
249  return edge_->env_->LookupWithFallback(var, eval, this);
250 }
251 
252 string EdgeEnv::MakePathList(vector<Node*>::iterator begin,
253  vector<Node*>::iterator end,
254  char sep) {
255  string result;
256  for (vector<Node*>::iterator i = begin; i != end; ++i) {
257  if (!result.empty())
258  result.push_back(sep);
259  const string& path = (*i)->PathDecanonicalized();
260  if (escape_in_out_ == kShellEscape) {
261 #if _WIN32
262  GetWin32EscapedString(path, &result);
263 #else
264  GetShellEscapedString(path, &result);
265 #endif
266  } else {
267  result.append(path);
268  }
269  }
270  return result;
271 }
272 
273 string Edge::EvaluateCommand(bool incl_rsp_file) {
274  string command = GetBinding("command");
275  if (incl_rsp_file) {
276  string rspfile_content = GetBinding("rspfile_content");
277  if (!rspfile_content.empty())
278  command += ";rspfile=" + rspfile_content;
279  }
280  return command;
281 }
282 
283 string Edge::GetBinding(const string& key) {
284  EdgeEnv env(this, EdgeEnv::kShellEscape);
285  return env.LookupVariable(key);
286 }
287 
288 bool Edge::GetBindingBool(const string& key) {
289  return !GetBinding(key).empty();
290 }
291 
293  EdgeEnv env(this, EdgeEnv::kDoNotEscape);
294  return env.LookupVariable("depfile");
295 }
296 
298  EdgeEnv env(this, EdgeEnv::kDoNotEscape);
299  return env.LookupVariable("rspfile");
300 }
301 
302 void Edge::Dump(const char* prefix) const {
303  printf("%s[ ", prefix);
304  for (vector<Node*>::const_iterator i = inputs_.begin();
305  i != inputs_.end() && *i != NULL; ++i) {
306  printf("%s ", (*i)->path().c_str());
307  }
308  printf("--%s-> ", rule_->name().c_str());
309  for (vector<Node*>::const_iterator i = outputs_.begin();
310  i != outputs_.end() && *i != NULL; ++i) {
311  printf("%s ", (*i)->path().c_str());
312  }
313  if (pool_) {
314  if (!pool_->name().empty()) {
315  printf("(in pool '%s')", pool_->name().c_str());
316  }
317  } else {
318  printf("(null pool?)");
319  }
320  printf("] 0x%p\n", this);
321 }
322 
323 bool Edge::is_phony() const {
324  return rule_ == &State::kPhonyRule;
325 }
326 
327 bool Edge::use_console() const {
328  return pool() == &State::kConsolePool;
329 }
330 
332  string result = path_;
333 #ifdef _WIN32
334  unsigned int mask = 1;
335  for (char* c = &result[0]; (c = strchr(c, '/')) != NULL;) {
336  if (slash_bits_ & mask)
337  *c = '\\';
338  c++;
339  mask <<= 1;
340  }
341 #endif
342  return result;
343 }
344 
345 void Node::Dump(const char* prefix) const {
346  printf("%s <%s 0x%p> mtime: %d%s, (:%s), ",
347  prefix, path().c_str(), this,
348  mtime(), mtime() ? "" : " (:missing)",
349  dirty() ? " dirty" : " clean");
350  if (in_edge()) {
351  in_edge()->Dump("in-edge: ");
352  } else {
353  printf("no in-edge\n");
354  }
355  printf(" out edges:\n");
356  for (vector<Edge*>::const_iterator e = out_edges().begin();
357  e != out_edges().end() && *e != NULL; ++e) {
358  (*e)->Dump(" +- ");
359  }
360 }
361 
362 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
363  string deps_type = edge->GetBinding("deps");
364  if (!deps_type.empty())
365  return LoadDepsFromLog(edge, err);
366 
367  string depfile = edge->GetUnescapedDepfile();
368  if (!depfile.empty())
369  return LoadDepFile(edge, depfile, err);
370 
371  // No deps to load.
372  return true;
373 }
374 
375 bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
376  string* err) {
377  METRIC_RECORD("depfile load");
378  string content = disk_interface_->ReadFile(path, err);
379  if (!err->empty()) {
380  *err = "loading '" + path + "': " + *err;
381  return false;
382  }
383  // On a missing depfile: return false and empty *err.
384  if (content.empty()) {
385  EXPLAIN("depfile '%s' is missing", path.c_str());
386  return false;
387  }
388 
389  DepfileParser depfile;
390  string depfile_err;
391  if (!depfile.Parse(&content, &depfile_err)) {
392  *err = path + ": " + depfile_err;
393  return false;
394  }
395 
396  unsigned int unused;
397  if (!CanonicalizePath(const_cast<char*>(depfile.out_.str_),
398  &depfile.out_.len_, &unused, err))
399  return false;
400 
401  // Check that this depfile matches the edge's output.
402  Node* first_output = edge->outputs_[0];
403  StringPiece opath = StringPiece(first_output->path());
404  if (opath != depfile.out_) {
405  *err = "expected depfile '" + path + "' to mention '" +
406  first_output->path() + "', got '" + depfile.out_.AsString() + "'";
407  return false;
408  }
409 
410  // Preallocate space in edge->inputs_ to be filled in below.
411  vector<Node*>::iterator implicit_dep =
412  PreallocateSpace(edge, depfile.ins_.size());
413 
414  // Add all its in-edges.
415  for (vector<StringPiece>::iterator i = depfile.ins_.begin();
416  i != depfile.ins_.end(); ++i, ++implicit_dep) {
417  unsigned int slash_bits;
418  if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits,
419  err))
420  return false;
421 
422  Node* node = state_->GetNode(*i, slash_bits);
423  *implicit_dep = node;
424  node->AddOutEdge(edge);
425  CreatePhonyInEdge(node);
426  }
427 
428  return true;
429 }
430 
431 bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, string* err) {
432  // NOTE: deps are only supported for single-target edges.
433  Node* output = edge->outputs_[0];
434  DepsLog::Deps* deps = deps_log_->GetDeps(output);
435  if (!deps) {
436  EXPLAIN("deps for '%s' are missing", output->path().c_str());
437  return false;
438  }
439 
440  // Deps are invalid if the output is newer than the deps.
441  if (output->mtime() > deps->mtime) {
442  EXPLAIN("stored deps info out of date for for '%s' (%d vs %d)",
443  output->path().c_str(), deps->mtime, output->mtime());
444  return false;
445  }
446 
447  vector<Node*>::iterator implicit_dep =
448  PreallocateSpace(edge, deps->node_count);
449  for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) {
450  Node* node = deps->nodes[i];
451  *implicit_dep = node;
452  node->AddOutEdge(edge);
453  CreatePhonyInEdge(node);
454  }
455  return true;
456 }
457 
458 vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge,
459  int count) {
460  edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
461  (size_t)count, 0);
462  edge->implicit_deps_ += count;
463  return edge->inputs_.end() - edge->order_only_deps_ - count;
464 }
465 
467  if (node->in_edge())
468  return;
469 
470  Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
471  node->set_in_edge(phony_edge);
472  phony_edge->outputs_.push_back(node);
473 
474  // RecomputeDirty might not be called for phony_edge if a previous call
475  // to RecomputeDirty had caused the file to be stat'ed. Because previous
476  // invocations of RecomputeDirty would have seen this node without an
477  // input edge (and therefore ready), we have to set outputs_ready_ to true
478  // to avoid a potential stuck build. If we do call RecomputeDirty for
479  // this node, it will simply set outputs_ready_ to the correct value.
480  phony_edge->outputs_ready_ = true;
481 }
bool is_phony() const
Definition: graph.cc:323
An Env for an Edge, providing $in and $out.
Definition: graph.cc:217
void Dump(const char *prefix="") const
Definition: graph.cc:345
virtual string ReadFile(const string &path, string *err)=0
Read a file to a string. Fill in |err| on error.
static bool IsReservedBinding(const string &var)
Definition: graph.cc:48
string PathDecanonicalized() const
Get |path()| but use slash_bits to convert back to original slash styles.
Definition: graph.cc:331
const char * str_
Definition: string_piece.h:49
bool LoadDeps(Edge *edge, string *err)
Load implicit dependencies for edge.
Definition: graph.cc:362
int order_only_deps_
Definition: graph.h:191
TimeStamp restat_mtime
Definition: build_log.h:59
TimeStamp mtime() const
Definition: graph.h:78
int implicit_deps_
Definition: graph.h:190
Edge * edge_
Definition: graph.cc:230
bool RecomputeOutputDirty(Edge *edge, Node *most_recent_input, const string &command, Node *output)
Recompute whether a given single output should be marked dirty.
Definition: graph.cc:145
Parser for the dependency information emitted by gcc's -M flags.
void GetWin32EscapedString(const string &input, string *result)
Definition: util.cc:305
bool RecomputeDirty(Edge *edge, string *err)
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.
Definition: graph.cc:60
StringPiece represents a slice of a string whose memory is managed externally.
Definition: string_piece.h:27
string GetUnescapedRspfile()
Like GetBinding("rspfile"), but without shell escaping.
Definition: graph.cc:297
Information about a node in the dependency graph: the file, whether it's dirty, mtime, etc.
Definition: graph.h:35
bool Parse(string *content, string *err)
Parse an input file.
void GetShellEscapedString(const string &input, string *result)
Appends |input| to |*result|, escaping according to the whims of either Bash, or Win32's CommandLineT...
Definition: util.cc:278
vector< Node * >::iterator PreallocateSpace(Edge *edge, int count)
Preallocate count spaces in the input array on edge, returning an iterator pointing at the first new ...
Definition: graph.cc:458
string MakePathList(vector< Node * >::iterator begin, vector< Node * >::iterator end, char sep)
Given a span of Nodes, construct a list of paths suitable for a command line.
Definition: graph.cc:252
virtual string LookupVariable(const string &var)
Definition: graph.cc:234
ImplicitDepLoader dep_loader_
Definition: graph.h:283
Interface for accessing the disk.
bool RecomputeOutputsDirty(Edge *edge, Node *most_recent_input)
Recompute whether any output of the edge is dirty.
Definition: graph.cc:133
Edge * in_edge() const
Definition: graph.h:84
Node ** nodes
Definition: deps_log.h:83
bool GetBindingBool(const string &key)
Definition: graph.cc:288
string AsString() const
Convert the slice into a full-fledged std::string, copying the data into a new string.
Definition: string_piece.h:45
bool CanonicalizePath(string *path, unsigned int *slash_bits, string *err)
Canonicalize a path like "foo/../bar.h" into just "bar.h".
Definition: util.cc:88
void Dump(const char *prefix="") const
Definition: graph.cc:302
void AddOutEdge(Edge *edge)
Definition: graph.h:91
int TimeStamp
Definition: timestamp.h:22
Node * GetNode(StringPiece path, unsigned int slash_bits)
Definition: state.cc:114
Pool * pool() const
Definition: graph.h:178
An edge in the dependency graph; links between Nodes using Rules.
Definition: graph.h:146
string EvaluateCommand(bool incl_rsp_file=false)
Expand all variables in a command and return it as a string.
Definition: graph.cc:273
bool is_order_only(size_t index)
Definition: graph.h:196
EscapeKind escape_in_out_
Definition: graph.cc:231
const EvalString * GetBinding(const string &key) const
Definition: graph.cc:40
bool Stat(DiskInterface *disk_interface)
Return true if the file exists (mtime_ got a value).
Definition: graph.cc:30
EscapeKind
Definition: graph.cc:218
uint64_t command_hash
Definition: build_log.h:56
Edge * AddEdge(const Rule *rule)
Definition: state.cc:105
vector< Node * > inputs_
Definition: graph.h:171
bool outputs_ready_
Definition: graph.h:174
BuildLog * build_log() const
Definition: graph.h:264
bool LoadDepFile(Edge *edge, const string &path, string *err)
Load implicit dependencies for edge from a depfile attribute.
Definition: graph.cc:375
DiskInterface * disk_interface_
Definition: graph.h:282
DepsLog * deps_log_
Definition: graph.h:241
BindingEnv * env_
Definition: graph.h:173
Deps * GetDeps(Node *node)
Definition: deps_log.cc:300
bool dirty() const
Definition: graph.h:80
bool exists() const
Definition: graph.h:66
int node_count
Definition: deps_log.h:82
bool use_console() const
Definition: graph.cc:327
static Pool kConsolePool
Definition: state.h:85
string LookupWithFallback(const string &var, const EvalString *eval, Env *env)
This is tricky.
Definition: eval_env.cc:30
void CreatePhonyInEdge(Node *node)
If we don't have a edge that generates this input already, create one; this makes us not abort if the...
Definition: graph.cc:466
vector< StringPiece > ins_
TimeStamp mtime_
Possible values of mtime_: -1: file hasn't been examined 0: we looked, and file doesn't exist >0: actu...
Definition: graph.h:106
#define METRIC_RECORD(name)
The primary interface to metrics.
Definition: metrics.h:85
const string & name() const
Definition: state.h:46
const string & path() const
Definition: graph.h:74
Pool * pool_
Definition: graph.h:170
void AddBinding(const string &key, const EvalString &val)
Definition: graph.cc:36
string GetBinding(const string &key)
Returns the shell-escaped value of |key|.
Definition: graph.cc:283
static uint64_t HashCommand(StringPiece command)
Definition: build_log.cc:91
const Rule * rule_
Definition: graph.h:169
LogEntry * LookupByOutput(const string &path)
Lookup a previously-run command by its output path.
Definition: build_log.cc:341
bool LoadDepsFromLog(Edge *edge, string *err)
Load implicit dependencies for edge from the DepsLog.
Definition: graph.cc:431
unsigned int slash_bits_
Set bits starting from lowest for backslashes that were normalized to forward slashes by Canonicalize...
Definition: graph.h:100
size_t len_
Definition: string_piece.h:50
State * state_
Definition: graph.h:239
map< string, EvalString > bindings_
Definition: graph.h:142
void set_in_edge(Edge *edge)
Definition: graph.h:85
const string & name() const
Definition: graph.h:128
bool AllInputsReady() const
Return true if all inputs' in-edges are ready.
Definition: graph.cc:207
DiskInterface * disk_interface_
Definition: graph.h:240
string GetUnescapedDepfile()
Like GetBinding("depfile"), but without shell escaping.
Definition: graph.cc:292
string path_
Definition: graph.h:96
virtual TimeStamp Stat(const string &path) const =0
stat() a file, returning the mtime, or 0 if missing and -1 on other errors.
StringPiece out_
EdgeEnv(Edge *edge, EscapeKind escape)
Definition: graph.cc:220
A tokenized string that contains variable references.
Definition: eval_env.h:59
An interface for a scope for variable (e.g. "$foo") lookups.
Definition: eval_env.h:28
const vector< Edge * > & out_edges() const
Definition: graph.h:90
bool deps_missing_
Definition: graph.h:175
#define EXPLAIN(fmt,...)
Definition: debug_flags.h:20
static const Rule kPhonyRule
Definition: state.h:86
vector< Node * > outputs_
Definition: graph.h:172