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 "depfile_parser.h"
22 #include "deps_log.h"
23 #include "disk_interface.h"
24 #include "explain.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 
64  TimeStamp deps_mtime = 0;
65  if (!dep_loader_.LoadDeps(edge, &deps_mtime, err)) {
66  if (!err->empty())
67  return false;
68  // Failed to load dependency info: rebuild to regenerate it.
69  dirty = 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  string command = edge->EvaluateCommand(true);
112 
113  for (vector<Node*>::iterator i = edge->outputs_.begin();
114  i != edge->outputs_.end(); ++i) {
115  (*i)->StatIfNecessary(disk_interface_);
116  if (RecomputeOutputDirty(edge, most_recent_input, deps_mtime,
117  command, *i)) {
118  dirty = true;
119  break;
120  }
121  }
122  }
123 
124  // Finally, visit each output to mark off that we've visited it, and update
125  // their dirty state if necessary.
126  for (vector<Node*>::iterator i = edge->outputs_.begin();
127  i != edge->outputs_.end(); ++i) {
128  (*i)->StatIfNecessary(disk_interface_);
129  if (dirty)
130  (*i)->MarkDirty();
131  }
132 
133  // If an edge is dirty, its outputs are normally not ready. (It's
134  // possible to be clean but still not be ready in the presence of
135  // order-only inputs.)
136  // But phony edges with no inputs have nothing to do, so are always
137  // ready.
138  if (dirty && !(edge->is_phony() && edge->inputs_.empty()))
139  edge->outputs_ready_ = false;
140 
141  return true;
142 }
143 
145  Node* most_recent_input,
146  TimeStamp deps_mtime,
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  // Dirty if the output is newer than the deps.
189  if (deps_mtime && output->mtime() > deps_mtime) {
190  EXPLAIN("stored deps info out of date for for %s (%d vs %d)",
191  output->path().c_str(), deps_mtime, output->mtime());
192  return true;
193  }
194 
195  // May also be dirty due to the command changing since the last build.
196  // But if this is a generator rule, the command changing does not make us
197  // dirty.
198  if (!edge->GetBindingBool("generator") && build_log()) {
199  if (entry || (entry = build_log()->LookupByOutput(output->path()))) {
200  if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
201  EXPLAIN("command line changed for %s", output->path().c_str());
202  return true;
203  }
204  }
205  if (!entry) {
206  EXPLAIN("command line not found in log for %s", output->path().c_str());
207  return true;
208  }
209  }
210 
211  return false;
212 }
213 
214 bool Edge::AllInputsReady() const {
215  for (vector<Node*>::const_iterator i = inputs_.begin();
216  i != inputs_.end(); ++i) {
217  if ((*i)->in_edge() && !(*i)->in_edge()->outputs_ready())
218  return false;
219  }
220  return true;
221 }
222 
223 /// An Env for an Edge, providing $in and $out.
224 struct EdgeEnv : public Env {
225  explicit EdgeEnv(Edge* edge) : edge_(edge) {}
226  virtual string LookupVariable(const string& var);
227 
228  /// Given a span of Nodes, construct a list of paths suitable for a command
229  /// line.
230  string MakePathList(vector<Node*>::iterator begin,
231  vector<Node*>::iterator end,
232  char sep);
233 
235 };
236 
237 string EdgeEnv::LookupVariable(const string& var) {
238  if (var == "in" || var == "in_newline") {
239  int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ -
241  return MakePathList(edge_->inputs_.begin(),
242  edge_->inputs_.begin() + explicit_deps_count,
243  var == "in" ? ' ' : '\n');
244  } else if (var == "out") {
245  return MakePathList(edge_->outputs_.begin(),
246  edge_->outputs_.end(),
247  ' ');
248  }
249 
250  // See notes on BindingEnv::LookupWithFallback.
251  const EvalString* eval = edge_->rule_->GetBinding(var);
252  return edge_->env_->LookupWithFallback(var, eval, this);
253 }
254 
255 string EdgeEnv::MakePathList(vector<Node*>::iterator begin,
256  vector<Node*>::iterator end,
257  char sep) {
258  string result;
259  for (vector<Node*>::iterator i = begin; i != end; ++i) {
260  if (!result.empty())
261  result.push_back(sep);
262  const string& path = (*i)->path();
263  if (path.find(" ") != string::npos) {
264  result.append("\"");
265  result.append(path);
266  result.append("\"");
267  } else {
268  result.append(path);
269  }
270  }
271  return result;
272 }
273 
274 string Edge::EvaluateCommand(bool incl_rsp_file) {
275  string command = GetBinding("command");
276  if (incl_rsp_file) {
277  string rspfile_content = GetBinding("rspfile_content");
278  if (!rspfile_content.empty())
279  command += ";rspfile=" + rspfile_content;
280  }
281  return command;
282 }
283 
284 string Edge::GetBinding(const string& key) {
285  EdgeEnv env(this);
286  return env.LookupVariable(key);
287 }
288 
289 bool Edge::GetBindingBool(const string& key) {
290  return !GetBinding(key).empty();
291 }
292 
293 void Edge::Dump(const char* prefix) const {
294  printf("%s[ ", prefix);
295  for (vector<Node*>::const_iterator i = inputs_.begin();
296  i != inputs_.end() && *i != NULL; ++i) {
297  printf("%s ", (*i)->path().c_str());
298  }
299  printf("--%s-> ", rule_->name().c_str());
300  for (vector<Node*>::const_iterator i = outputs_.begin();
301  i != outputs_.end() && *i != NULL; ++i) {
302  printf("%s ", (*i)->path().c_str());
303  }
304  if (pool_) {
305  if (!pool_->name().empty()) {
306  printf("(in pool '%s')", pool_->name().c_str());
307  }
308  } else {
309  printf("(null pool?)");
310  }
311  printf("] 0x%p\n", this);
312 }
313 
314 bool Edge::is_phony() const {
315  return rule_ == &State::kPhonyRule;
316 }
317 
318 void Node::Dump(const char* prefix) const {
319  printf("%s <%s 0x%p> mtime: %d%s, (:%s), ",
320  prefix, path().c_str(), this,
321  mtime(), mtime() ? "" : " (:missing)",
322  dirty() ? " dirty" : " clean");
323  if (in_edge()) {
324  in_edge()->Dump("in-edge: ");
325  } else {
326  printf("no in-edge\n");
327  }
328  printf(" out edges:\n");
329  for (vector<Edge*>::const_iterator e = out_edges().begin();
330  e != out_edges().end() && *e != NULL; ++e) {
331  (*e)->Dump(" +- ");
332  }
333 }
334 
335 bool ImplicitDepLoader::LoadDeps(Edge* edge, TimeStamp* mtime, string* err) {
336  string deps_type = edge->GetBinding("deps");
337  if (!deps_type.empty()) {
338  if (!LoadDepsFromLog(edge, mtime, err)) {
339  if (!err->empty())
340  return false;
341  EXPLAIN("deps for %s are missing", edge->outputs_[0]->path().c_str());
342  return false;
343  }
344  return true;
345  }
346 
347  string depfile = edge->GetBinding("depfile");
348  if (!depfile.empty()) {
349  if (!LoadDepFile(edge, depfile, err)) {
350  if (!err->empty())
351  return false;
352  EXPLAIN("depfile '%s' is missing", depfile.c_str());
353  return false;
354  }
355  return true;
356  }
357 
358  // No deps to load.
359  return true;
360 }
361 
362 bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
363  string* err) {
364  METRIC_RECORD("depfile load");
365  string content = disk_interface_->ReadFile(path, err);
366  if (!err->empty()) {
367  *err = "loading '" + path + "': " + *err;
368  return false;
369  }
370  // On a missing depfile: return false and empty *err.
371  if (content.empty())
372  return false;
373 
374  DepfileParser depfile;
375  string depfile_err;
376  if (!depfile.Parse(&content, &depfile_err)) {
377  *err = path + ": " + depfile_err;
378  return false;
379  }
380 
381  // Check that this depfile matches the edge's output.
382  Node* first_output = edge->outputs_[0];
383  StringPiece opath = StringPiece(first_output->path());
384  if (opath != depfile.out_) {
385  *err = "expected depfile '" + path + "' to mention '" +
386  first_output->path() + "', got '" + depfile.out_.AsString() + "'";
387  return false;
388  }
389 
390  // Preallocate space in edge->inputs_ to be filled in below.
391  vector<Node*>::iterator implicit_dep =
392  PreallocateSpace(edge, depfile.ins_.size());
393 
394  // Add all its in-edges.
395  for (vector<StringPiece>::iterator i = depfile.ins_.begin();
396  i != depfile.ins_.end(); ++i, ++implicit_dep) {
397  if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, err))
398  return false;
399 
400  Node* node = state_->GetNode(*i);
401  *implicit_dep = node;
402  node->AddOutEdge(edge);
403  CreatePhonyInEdge(node);
404  }
405 
406  return true;
407 }
408 
410  string* err) {
411  DepsLog::Deps* deps = deps_log_->GetDeps(edge->outputs_[0]);
412  if (!deps)
413  return false;
414 
415  *deps_mtime = deps->mtime;
416 
417  vector<Node*>::iterator implicit_dep =
418  PreallocateSpace(edge, deps->node_count);
419  for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) {
420  *implicit_dep = deps->nodes[i];
421  deps->nodes[i]->AddOutEdge(edge);
422  CreatePhonyInEdge(*implicit_dep);
423  }
424  return true;
425 }
426 
427 vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge,
428  int count) {
429  edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
430  (size_t)count, 0);
431  edge->implicit_deps_ += count;
432  return edge->inputs_.end() - edge->order_only_deps_ - count;
433 }
434 
436  if (node->in_edge())
437  return;
438 
439  Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
440  node->set_in_edge(phony_edge);
441  phony_edge->outputs_.push_back(node);
442 
443  // RecomputeDirty might not be called for phony_edge if a previous call
444  // to RecomputeDirty had caused the file to be stat'ed. Because previous
445  // invocations of RecomputeDirty would have seen this node without an
446  // input edge (and therefore ready), we have to set outputs_ready_ to true
447  // to avoid a potential stuck build. If we do call RecomputeDirty for
448  // this node, it will simply set outputs_ready_ to the correct value.
449  phony_edge->outputs_ready_ = true;
450 }
bool is_phony() const
Definition: graph.cc:314
An Env for an Edge, providing $in and $out.
Definition: graph.cc:224
void Dump(const char *prefix="") const
Definition: graph.cc:318
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
int order_only_deps_
Definition: graph.h:175
TimeStamp restat_mtime
Definition: build_log.h:52
TimeStamp mtime() const
Definition: graph.h:74
int implicit_deps_
Definition: graph.h:174
Edge * edge_
Definition: graph.cc:234
Parser for the dependency information emitted by gcc's -M flags.
Node * GetNode(StringPiece path)
Definition: state.cc:112
bool RecomputeOutputDirty(Edge *edge, Node *most_recent_input, TimeStamp deps_mtime, const string &command, Node *output)
Recompute whether a given single output should be marked dirty.
Definition: graph.cc:144
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
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.
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:427
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:255
virtual string LookupVariable(const string &var)
Definition: graph.cc:237
ImplicitDepLoader dep_loader_
Definition: graph.h:263
Interface for accessing the disk.
Edge * in_edge() const
Definition: graph.h:80
Node ** nodes
Definition: deps_log.h:80
bool GetBindingBool(const string &key)
Definition: graph.cc:289
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:293
void AddOutEdge(Edge *edge)
Definition: graph.h:87
int TimeStamp
Definition: timestamp.h:22
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:274
bool is_order_only(size_t index)
Definition: graph.h:180
bool CanonicalizePath(string *path, string *err)
Canonicalize a path like "foo/../bar.h" into just "bar.h".
Definition: util.cc:87
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
uint64_t command_hash
Definition: build_log.h:49
Edge * AddEdge(const Rule *rule)
Definition: state.cc:103
vector< Node * > inputs_
Definition: graph.h:156
bool outputs_ready_
Definition: graph.h:159
BuildLog * build_log() const
Definition: graph.h:249
bool LoadDepFile(Edge *edge, const string &path, string *err)
Load implicit dependencies for edge from a depfile attribute.
Definition: graph.cc:362
DiskInterface * disk_interface_
Definition: graph.h:262
DepsLog * deps_log_
Definition: graph.h:224
BindingEnv * env_
Definition: graph.h:158
Deps * GetDeps(Node *node)
Definition: deps_log.cc:248
bool dirty() const
Definition: graph.h:76
bool exists() const
Definition: graph.h:65
int node_count
Definition: deps_log.h:79
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:435
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:97
#define METRIC_RECORD(name)
The primary interface to metrics.
Definition: metrics.h:85
EdgeEnv(Edge *edge)
Definition: graph.cc:225
const string & name() const
Definition: state.h:46
const string & path() const
Definition: graph.h:73
Pool * pool_
Definition: graph.h:155
void AddBinding(const string &key, const EvalString &val)
Definition: graph.cc:36
bool LoadDepsFromLog(Edge *edge, TimeStamp *mtime, string *err)
Load implicit dependencies for edge from the DepsLog.
Definition: graph.cc:409
string GetBinding(const string &key)
Definition: graph.cc:284
static uint64_t HashCommand(StringPiece command)
Definition: build_log.cc:90
const Rule * rule_
Definition: graph.h:154
#define EXPLAIN(fmt,...)
Definition: explain.h:20
LogEntry * LookupByOutput(const string &path)
Lookup a previously-run command by its output path.
Definition: build_log.cc:337
State * state_
Definition: graph.h:222
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:214
bool LoadDeps(Edge *edge, TimeStamp *mtime, string *err)
Load implicit dependencies for edge.
Definition: graph.cc:335
DiskInterface * disk_interface_
Definition: graph.h:223
string path_
Definition: graph.h:92
StringPiece out_
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
virtual TimeStamp Stat(const string &path)=0
stat() a file, returning the mtime, or 0 if missing and -1 on other errors.
static const Rule kPhonyRule
Definition: state.h:85
vector< Node * > outputs_
Definition: graph.h:157