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)->path();
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 
331 void Node::Dump(const char* prefix) const {
332  printf("%s <%s 0x%p> mtime: %d%s, (:%s), ",
333  prefix, path().c_str(), this,
334  mtime(), mtime() ? "" : " (:missing)",
335  dirty() ? " dirty" : " clean");
336  if (in_edge()) {
337  in_edge()->Dump("in-edge: ");
338  } else {
339  printf("no in-edge\n");
340  }
341  printf(" out edges:\n");
342  for (vector<Edge*>::const_iterator e = out_edges().begin();
343  e != out_edges().end() && *e != NULL; ++e) {
344  (*e)->Dump(" +- ");
345  }
346 }
347 
348 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
349  string deps_type = edge->GetBinding("deps");
350  if (!deps_type.empty())
351  return LoadDepsFromLog(edge, err);
352 
353  string depfile = edge->GetUnescapedDepfile();
354  if (!depfile.empty())
355  return LoadDepFile(edge, depfile, err);
356 
357  // No deps to load.
358  return true;
359 }
360 
361 bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
362  string* err) {
363  METRIC_RECORD("depfile load");
364  string content = disk_interface_->ReadFile(path, err);
365  if (!err->empty()) {
366  *err = "loading '" + path + "': " + *err;
367  return false;
368  }
369  // On a missing depfile: return false and empty *err.
370  if (content.empty()) {
371  EXPLAIN("depfile '%s' is missing", path.c_str());
372  return false;
373  }
374 
375  DepfileParser depfile;
376  string depfile_err;
377  if (!depfile.Parse(&content, &depfile_err)) {
378  *err = path + ": " + depfile_err;
379  return false;
380  }
381 
382  // Check that this depfile matches the edge's output.
383  Node* first_output = edge->outputs_[0];
384  StringPiece opath = StringPiece(first_output->path());
385  if (opath != depfile.out_) {
386  *err = "expected depfile '" + path + "' to mention '" +
387  first_output->path() + "', got '" + depfile.out_.AsString() + "'";
388  return false;
389  }
390 
391  // Preallocate space in edge->inputs_ to be filled in below.
392  vector<Node*>::iterator implicit_dep =
393  PreallocateSpace(edge, depfile.ins_.size());
394 
395  // Add all its in-edges.
396  for (vector<StringPiece>::iterator i = depfile.ins_.begin();
397  i != depfile.ins_.end(); ++i, ++implicit_dep) {
398  if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, err))
399  return false;
400 
401  Node* node = state_->GetNode(*i);
402  *implicit_dep = node;
403  node->AddOutEdge(edge);
404  CreatePhonyInEdge(node);
405  }
406 
407  return true;
408 }
409 
410 bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, string* err) {
411  // NOTE: deps are only supported for single-target edges.
412  Node* output = edge->outputs_[0];
413  DepsLog::Deps* deps = deps_log_->GetDeps(output);
414  if (!deps) {
415  EXPLAIN("deps for '%s' are missing", output->path().c_str());
416  return false;
417  }
418 
419  // Deps are invalid if the output is newer than the deps.
420  if (output->mtime() > deps->mtime) {
421  EXPLAIN("stored deps info out of date for for '%s' (%d vs %d)",
422  output->path().c_str(), deps->mtime, output->mtime());
423  return false;
424  }
425 
426  vector<Node*>::iterator implicit_dep =
427  PreallocateSpace(edge, deps->node_count);
428  for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) {
429  Node* node = deps->nodes[i];
430  *implicit_dep = node;
431  node->AddOutEdge(edge);
432  CreatePhonyInEdge(node);
433  }
434  return true;
435 }
436 
437 vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge,
438  int count) {
439  edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
440  (size_t)count, 0);
441  edge->implicit_deps_ += count;
442  return edge->inputs_.end() - edge->order_only_deps_ - count;
443 }
444 
446  if (node->in_edge())
447  return;
448 
449  Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
450  node->set_in_edge(phony_edge);
451  phony_edge->outputs_.push_back(node);
452 
453  // RecomputeDirty might not be called for phony_edge if a previous call
454  // to RecomputeDirty had caused the file to be stat'ed. Because previous
455  // invocations of RecomputeDirty would have seen this node without an
456  // input edge (and therefore ready), we have to set outputs_ready_ to true
457  // to avoid a potential stuck build. If we do call RecomputeDirty for
458  // this node, it will simply set outputs_ready_ to the correct value.
459  phony_edge->outputs_ready_ = true;
460 }
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:331
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
bool LoadDeps(Edge *edge, string *err)
Load implicit dependencies for edge.
Definition: graph.cc:348
int order_only_deps_
Definition: graph.h:182
TimeStamp restat_mtime
Definition: build_log.h:59
TimeStamp mtime() const
Definition: graph.h:74
int implicit_deps_
Definition: graph.h:181
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.
Node * GetNode(StringPiece path)
Definition: state.cc:114
void GetWin32EscapedString(const string &input, string *result)
Definition: util.cc:247
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:220
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:437
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:274
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:80
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
void Dump(const char *prefix="") const
Definition: graph.cc:302
void AddOutEdge(Edge *edge)
Definition: graph.h:87
int TimeStamp
Definition: timestamp.h:22
Pool * pool() const
Definition: graph.h:169
An edge in the dependency graph; links between Nodes using Rules.
Definition: graph.h:137
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:187
EscapeKind escape_in_out_
Definition: graph.cc:231
bool CanonicalizePath(string *path, string *err)
Canonicalize a path like "foo/../bar.h" into just "bar.h".
Definition: util.cc:88
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:162
bool outputs_ready_
Definition: graph.h:165
BuildLog * build_log() const
Definition: graph.h:255
bool LoadDepFile(Edge *edge, const string &path, string *err)
Load implicit dependencies for edge from a depfile attribute.
Definition: graph.cc:361
DiskInterface * disk_interface_
Definition: graph.h:273
DepsLog * deps_log_
Definition: graph.h:232
BindingEnv * env_
Definition: graph.h:164
Deps * GetDeps(Node *node)
Definition: deps_log.cc:295
bool dirty() const
Definition: graph.h:76
bool exists() const
Definition: graph.h:65
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:445
vector< StringPiece > ins_
TimeStamp mtime_
Possible values of mtime_: -1: file hasn't been examined 0: we looked, and file doesn't exist >0: act...
Definition: graph.h:97
#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:73
Pool * pool_
Definition: graph.h:161
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:160
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:410
State * state_
Definition: graph.h:230
map< string, EvalString > bindings_
Definition: graph.h:133
void set_in_edge(Edge *edge)
Definition: graph.h:81
const string & name() const
Definition: graph.h:119
bool AllInputsReady() const
Return true if all inputs' in-edges are ready.
Definition: graph.cc:207
DiskInterface * disk_interface_
Definition: graph.h:231
string GetUnescapedDepfile()
Like GetBinding("depfile"), but without shell escaping.
Definition: graph.cc:292
string path_
Definition: graph.h:92
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:86
bool deps_missing_
Definition: graph.h:166
#define EXPLAIN(fmt,...)
Definition: debug_flags.h:20
static const Rule kPhonyRule
Definition: state.h:86
vector< Node * > outputs_
Definition: graph.h:163