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 <algorithm>
18#include <deque>
19#include <assert.h>
20#include <stdio.h>
21
22#include "build_log.h"
23#include "debug_flags.h"
24#include "depfile_parser.h"
25#include "deps_log.h"
26#include "disk_interface.h"
27#include "manifest_parser.h"
28#include "metrics.h"
29#include "state.h"
30#include "util.h"
31
32using namespace std;
33
34bool Node::Stat(DiskInterface* disk_interface, string* err) {
35 METRIC_RECORD("node stat");
36 mtime_ = disk_interface->Stat(path_, err);
37 if (mtime_ == -1) {
38 return false;
39 }
40 exists_ = (mtime_ != 0) ? ExistenceStatusExists : ExistenceStatusMissing;
41 return true;
42}
43
44void Node::UpdatePhonyMtime(TimeStamp mtime) {
45 if (!exists()) {
46 mtime_ = std::max(mtime_, mtime);
47 }
48}
49
50bool DependencyScan::RecomputeDirty(Node* initial_node,
51 std::vector<Node*>* validation_nodes,
52 string* err) {
53 std::vector<Node*> stack;
54 std::vector<Node*> new_validation_nodes;
55
56 std::deque<Node*> nodes(1, initial_node);
57
58 // RecomputeNodeDirty might return new validation nodes that need to be
59 // checked for dirty state, keep a queue of nodes to visit.
60 while (!nodes.empty()) {
61 Node* node = nodes.front();
62 nodes.pop_front();
63
64 stack.clear();
65 new_validation_nodes.clear();
66
67 if (!RecomputeNodeDirty(node, &stack, &new_validation_nodes, err))
68 return false;
69 nodes.insert(nodes.end(), new_validation_nodes.begin(),
70 new_validation_nodes.end());
71 if (!new_validation_nodes.empty()) {
72 assert(validation_nodes &&
73 "validations require RecomputeDirty to be called with validation_nodes");
74 validation_nodes->insert(validation_nodes->end(),
75 new_validation_nodes.begin(),
76 new_validation_nodes.end());
77 }
78 }
79
80 return true;
81}
82
83bool DependencyScan::RecomputeNodeDirty(Node* node, std::vector<Node*>* stack,
84 std::vector<Node*>* validation_nodes,
85 string* err) {
86 Edge* edge = node->in_edge();
87 if (!edge) {
88 // If we already visited this leaf node then we are done.
89 if (node->status_known())
90 return true;
91 // This node has no in-edge; it is dirty if it is missing.
92 if (!node->StatIfNecessary(disk_interface_, err))
93 return false;
94 if (!node->exists())
95 EXPLAIN("%s has no in-edge and is missing", node->path().c_str());
96 node->set_dirty(!node->exists());
97 return true;
98 }
99
100 // If we already finished this edge then we are done.
101 if (edge->mark_ == Edge::VisitDone)
102 return true;
103
104 // If we encountered this edge earlier in the call stack we have a cycle.
105 if (!VerifyDAG(node, stack, err))
106 return false;
107
108 // Mark the edge temporarily while in the call stack.
109 edge->mark_ = Edge::VisitInStack;
110 stack->push_back(node);
111
112 bool dirty = false;
113 edge->outputs_ready_ = true;
114 edge->deps_missing_ = false;
115
116 if (!edge->deps_loaded_) {
117 // This is our first encounter with this edge.
118 // If there is a pending dyndep file, visit it now:
119 // * If the dyndep file is ready then load it now to get any
120 // additional inputs and outputs for this and other edges.
121 // Once the dyndep file is loaded it will no longer be pending
122 // if any other edges encounter it, but they will already have
123 // been updated.
124 // * If the dyndep file is not ready then since is known to be an
125 // input to this edge, the edge will not be considered ready below.
126 // Later during the build the dyndep file will become ready and be
127 // loaded to update this edge before it can possibly be scheduled.
128 if (edge->dyndep_ && edge->dyndep_->dyndep_pending()) {
129 if (!RecomputeNodeDirty(edge->dyndep_, stack, validation_nodes, err))
130 return false;
131
132 if (!edge->dyndep_->in_edge() ||
133 edge->dyndep_->in_edge()->outputs_ready()) {
134 // The dyndep file is ready, so load it now.
135 if (!LoadDyndeps(edge->dyndep_, err))
136 return false;
137 }
138 }
139 }
140
141 // Load output mtimes so we can compare them to the most recent input below.
142 for (vector<Node*>::iterator o = edge->outputs_.begin();
143 o != edge->outputs_.end(); ++o) {
144 if (!(*o)->StatIfNecessary(disk_interface_, err))
145 return false;
146 }
147
148 if (!edge->deps_loaded_) {
149 // This is our first encounter with this edge. Load discovered deps.
150 edge->deps_loaded_ = true;
151 if (!dep_loader_.LoadDeps(edge, err)) {
152 if (!err->empty())
153 return false;
154 // Failed to load dependency info: rebuild to regenerate it.
155 // LoadDeps() did EXPLAIN() already, no need to do it here.
156 dirty = edge->deps_missing_ = true;
157 }
158 }
159
160 // Store any validation nodes from the edge for adding to the initial
161 // nodes. Don't recurse into them, that would trigger the dependency
162 // cycle detector if the validation node depends on this node.
163 // RecomputeDirty will add the validation nodes to the initial nodes
164 // and recurse into them.
165 validation_nodes->insert(validation_nodes->end(),
166 edge->validations_.begin(), edge->validations_.end());
167
168 // Visit all inputs; we're dirty if any of the inputs are dirty.
169 Node* most_recent_input = NULL;
170 for (vector<Node*>::iterator i = edge->inputs_.begin();
171 i != edge->inputs_.end(); ++i) {
172 // Visit this input.
173 if (!RecomputeNodeDirty(*i, stack, validation_nodes, err))
174 return false;
175
176 // If an input is not ready, neither are our outputs.
177 if (Edge* in_edge = (*i)->in_edge()) {
178 if (!in_edge->outputs_ready_)
179 edge->outputs_ready_ = false;
180 }
181
182 if (!edge->is_order_only(i - edge->inputs_.begin())) {
183 // If a regular input is dirty (or missing), we're dirty.
184 // Otherwise consider mtime.
185 if ((*i)->dirty()) {
186 EXPLAIN("%s is dirty", (*i)->path().c_str());
187 dirty = true;
188 } else {
189 if (!most_recent_input || (*i)->mtime() > most_recent_input->mtime()) {
190 most_recent_input = *i;
191 }
192 }
193 }
194 }
195
196 // We may also be dirty due to output state: missing outputs, out of
197 // date outputs, etc. Visit all outputs and determine whether they're dirty.
198 if (!dirty)
199 if (!RecomputeOutputsDirty(edge, most_recent_input, &dirty, err))
200 return false;
201
202 // Finally, visit each output and update their dirty state if necessary.
203 for (vector<Node*>::iterator o = edge->outputs_.begin();
204 o != edge->outputs_.end(); ++o) {
205 if (dirty)
206 (*o)->MarkDirty();
207 }
208
209 // If an edge is dirty, its outputs are normally not ready. (It's
210 // possible to be clean but still not be ready in the presence of
211 // order-only inputs.)
212 // But phony edges with no inputs have nothing to do, so are always
213 // ready.
214 if (dirty && !(edge->is_phony() && edge->inputs_.empty()))
215 edge->outputs_ready_ = false;
216
217 // Mark the edge as finished during this walk now that it will no longer
218 // be in the call stack.
219 edge->mark_ = Edge::VisitDone;
220 assert(stack->back() == node);
221 stack->pop_back();
222
223 return true;
224}
225
226bool DependencyScan::VerifyDAG(Node* node, vector<Node*>* stack, string* err) {
227 Edge* edge = node->in_edge();
228 assert(edge != NULL);
229
230 // If we have no temporary mark on the edge then we do not yet have a cycle.
231 if (edge->mark_ != Edge::VisitInStack)
232 return true;
233
234 // We have this edge earlier in the call stack. Find it.
235 vector<Node*>::iterator start = stack->begin();
236 while (start != stack->end() && (*start)->in_edge() != edge)
237 ++start;
238 assert(start != stack->end());
239
240 // Make the cycle clear by reporting its start as the node at its end
241 // instead of some other output of the starting edge. For example,
242 // running 'ninja b' on
243 // build a b: cat c
244 // build c: cat a
245 // should report a -> c -> a instead of b -> c -> a.
246 *start = node;
247
248 // Construct the error message rejecting the cycle.
249 *err = "dependency cycle: ";
250 for (vector<Node*>::const_iterator i = start; i != stack->end(); ++i) {
251 err->append((*i)->path());
252 err->append(" -> ");
253 }
254 err->append((*start)->path());
255
256 if ((start + 1) == stack->end() && edge->maybe_phonycycle_diagnostic()) {
257 // The manifest parser would have filtered out the self-referencing
258 // input if it were not configured to allow the error.
259 err->append(" [-w phonycycle=err]");
260 }
261
262 return false;
263}
264
265bool DependencyScan::RecomputeOutputsDirty(Edge* edge, Node* most_recent_input,
266 bool* outputs_dirty, string* err) {
267 string command = edge->EvaluateCommand(/*incl_rsp_file=*/true);
268 for (vector<Node*>::iterator o = edge->outputs_.begin();
269 o != edge->outputs_.end(); ++o) {
270 if (RecomputeOutputDirty(edge, most_recent_input, command, *o)) {
271 *outputs_dirty = true;
272 return true;
273 }
274 }
275 return true;
276}
277
278bool DependencyScan::RecomputeOutputDirty(const Edge* edge,
279 const Node* most_recent_input,
280 const string& command,
281 Node* output) {
282 if (edge->is_phony()) {
283 // Phony edges don't write any output. Outputs are only dirty if
284 // there are no inputs and we're missing the output.
285 if (edge->inputs_.empty() && !output->exists()) {
286 EXPLAIN("output %s of phony edge with no inputs doesn't exist",
287 output->path().c_str());
288 return true;
289 }
290
291 // Update the mtime with the newest input. Dependents can thus call mtime()
292 // on the fake node and get the latest mtime of the dependencies
293 if (most_recent_input) {
294 output->UpdatePhonyMtime(most_recent_input->mtime());
295 }
296
297 // Phony edges are clean, nothing to do
298 return false;
299 }
300
301 // Dirty if we're missing the output.
302 if (!output->exists()) {
303 EXPLAIN("output %s doesn't exist", output->path().c_str());
304 return true;
305 }
306
307 BuildLog::LogEntry* entry = 0;
308
309 // If this is a restat rule, we may have cleaned the output in a
310 // previous run and stored the command start time in the build log.
311 // We don't want to consider a restat rule's outputs as dirty unless
312 // an input changed since the last run, so we'll skip checking the
313 // output file's actual mtime and simply check the recorded mtime from
314 // the log against the most recent input's mtime (see below)
315 bool used_restat = false;
316 if (edge->GetBindingBool("restat") && build_log() &&
317 (entry = build_log()->LookupByOutput(output->path()))) {
318 used_restat = true;
319 }
320
321 // Dirty if the output is older than the input.
322 if (!used_restat && most_recent_input && output->mtime() < most_recent_input->mtime()) {
323 EXPLAIN("output %s older than most recent input %s "
324 "(%" PRId64 " vs %" PRId64 ")",
325 output->path().c_str(),
326 most_recent_input->path().c_str(),
327 output->mtime(), most_recent_input->mtime());
328 return true;
329 }
330
331 if (build_log()) {
332 bool generator = edge->GetBindingBool("generator");
333 if (entry || (entry = build_log()->LookupByOutput(output->path()))) {
334 if (!generator &&
335 BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
336 // May also be dirty due to the command changing since the last build.
337 // But if this is a generator rule, the command changing does not make us
338 // dirty.
339 EXPLAIN("command line changed for %s", output->path().c_str());
340 return true;
341 }
342 if (most_recent_input && entry->mtime < most_recent_input->mtime()) {
343 // May also be dirty due to the mtime in the log being older than the
344 // mtime of the most recent input. This can occur even when the mtime
345 // on disk is newer if a previous run wrote to the output file but
346 // exited with an error or was interrupted. If this was a restat rule,
347 // then we only check the recorded mtime against the most recent input
348 // mtime and ignore the actual output's mtime above.
349 EXPLAIN("recorded mtime of %s older than most recent input %s (%" PRId64 " vs %" PRId64 ")",
350 output->path().c_str(), most_recent_input->path().c_str(),
351 entry->mtime, most_recent_input->mtime());
352 return true;
353 }
354 }
355 if (!entry && !generator) {
356 EXPLAIN("command line not found in log for %s", output->path().c_str());
357 return true;
358 }
359 }
360
361 return false;
362}
363
364bool DependencyScan::LoadDyndeps(Node* node, string* err) const {
365 return dyndep_loader_.LoadDyndeps(node, err);
366}
367
368bool DependencyScan::LoadDyndeps(Node* node, DyndepFile* ddf,
369 string* err) const {
370 return dyndep_loader_.LoadDyndeps(node, ddf, err);
371}
372
373bool Edge::AllInputsReady() const {
374 for (vector<Node*>::const_iterator i = inputs_.begin();
375 i != inputs_.end(); ++i) {
376 if ((*i)->in_edge() && !(*i)->in_edge()->outputs_ready())
377 return false;
378 }
379 return true;
380}
381
382/// An Env for an Edge, providing $in and $out.
383struct EdgeEnv : public Env {
384 enum EscapeKind { kShellEscape, kDoNotEscape };
385
386 EdgeEnv(const Edge* const edge, const EscapeKind escape)
387 : edge_(edge), escape_in_out_(escape), recursive_(false) {}
388 virtual string LookupVariable(const string& var);
389
390 /// Given a span of Nodes, construct a list of paths suitable for a command
391 /// line.
392 std::string MakePathList(const Node* const* span, size_t size, char sep) const;
393
394 private:
395 vector<string> lookups_;
396 const Edge* const edge_;
397 EscapeKind escape_in_out_;
398 bool recursive_;
399};
400
401string EdgeEnv::LookupVariable(const string& var) {
402 if (var == "in" || var == "in_newline") {
403 int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ -
404 edge_->order_only_deps_;
405 return MakePathList(edge_->inputs_.data(), explicit_deps_count,
406 var == "in" ? ' ' : '\n');
407 } else if (var == "out") {
408 int explicit_outs_count = edge_->outputs_.size() - edge_->implicit_outs_;
409 return MakePathList(&edge_->outputs_[0], explicit_outs_count, ' ');
410 }
411
412 if (recursive_) {
413 vector<string>::const_iterator it;
414 if ((it = find(lookups_.begin(), lookups_.end(), var)) != lookups_.end()) {
415 string cycle;
416 for (; it != lookups_.end(); ++it)
417 cycle.append(*it + " -> ");
418 cycle.append(var);
419 Fatal(("cycle in rule variables: " + cycle).c_str());
420 }
421 }
422
423 // See notes on BindingEnv::LookupWithFallback.
424 const EvalString* eval = edge_->rule_->GetBinding(var);
425 if (recursive_ && eval)
426 lookups_.push_back(var);
427
428 // In practice, variables defined on rules never use another rule variable.
429 // For performance, only start checking for cycles after the first lookup.
430 recursive_ = true;
431 return edge_->env_->LookupWithFallback(var, eval, this);
432}
433
434std::string EdgeEnv::MakePathList(const Node* const* const span,
435 const size_t size, const char sep) const {
436 string result;
437 for (const Node* const* i = span; i != span + size; ++i) {
438 if (!result.empty())
439 result.push_back(sep);
440 const string& path = (*i)->PathDecanonicalized();
441 if (escape_in_out_ == kShellEscape) {
442#ifdef _WIN32
443 GetWin32EscapedString(path, &result);
444#else
445 GetShellEscapedString(path, &result);
446#endif
447 } else {
448 result.append(path);
449 }
450 }
451 return result;
452}
453
454void Edge::CollectInputs(bool shell_escape,
455 std::vector<std::string>* out) const {
456 for (std::vector<Node*>::const_iterator it = inputs_.begin();
457 it != inputs_.end(); ++it) {
458 std::string path = (*it)->PathDecanonicalized();
459 if (shell_escape) {
460 std::string unescaped;
461 unescaped.swap(path);
462#ifdef _WIN32
463 GetWin32EscapedString(unescaped, &path);
464#else
465 GetShellEscapedString(unescaped, &path);
466#endif
467 }
468#if __cplusplus >= 201103L
469 out->push_back(std::move(path));
470#else
471 out->push_back(path);
472#endif
473 }
474}
475
476std::string Edge::EvaluateCommand(const bool incl_rsp_file) const {
477 string command = GetBinding("command");
478 if (incl_rsp_file) {
479 string rspfile_content = GetBinding("rspfile_content");
480 if (!rspfile_content.empty())
481 command += ";rspfile=" + rspfile_content;
482 }
483 return command;
484}
485
486std::string Edge::GetBinding(const std::string& key) const {
487 EdgeEnv env(this, EdgeEnv::kShellEscape);
488 return env.LookupVariable(key);
489}
490
491bool Edge::GetBindingBool(const string& key) const {
492 return !GetBinding(key).empty();
493}
494
495string Edge::GetUnescapedDepfile() const {
496 EdgeEnv env(this, EdgeEnv::kDoNotEscape);
497 return env.LookupVariable("depfile");
498}
499
500string Edge::GetUnescapedDyndep() const {
501 EdgeEnv env(this, EdgeEnv::kDoNotEscape);
502 return env.LookupVariable("dyndep");
503}
504
505std::string Edge::GetUnescapedRspfile() const {
506 EdgeEnv env(this, EdgeEnv::kDoNotEscape);
507 return env.LookupVariable("rspfile");
508}
509
510void Edge::Dump(const char* prefix) const {
511 printf("%s[ ", prefix);
512 for (vector<Node*>::const_iterator i = inputs_.begin();
513 i != inputs_.end() && *i != NULL; ++i) {
514 printf("%s ", (*i)->path().c_str());
515 }
516 printf("--%s-> ", rule_->name().c_str());
517 for (vector<Node*>::const_iterator i = outputs_.begin();
518 i != outputs_.end() && *i != NULL; ++i) {
519 printf("%s ", (*i)->path().c_str());
520 }
521 if (!validations_.empty()) {
522 printf(" validations ");
523 for (std::vector<Node*>::const_iterator i = validations_.begin();
524 i != validations_.end() && *i != NULL; ++i) {
525 printf("%s ", (*i)->path().c_str());
526 }
527 }
528 if (pool_) {
529 if (!pool_->name().empty()) {
530 printf("(in pool '%s')", pool_->name().c_str());
531 }
532 } else {
533 printf("(null pool?)");
534 }
535 printf("] 0x%p\n", this);
536}
537
538bool Edge::is_phony() const {
539 return rule_ == &State::kPhonyRule;
540}
541
542bool Edge::use_console() const {
543 return pool() == &State::kConsolePool;
544}
545
546bool Edge::maybe_phonycycle_diagnostic() const {
547 // CMake 2.8.12.x and 3.0.x produced self-referencing phony rules
548 // of the form "build a: phony ... a ...". Restrict our
549 // "phonycycle" diagnostic option to the form it used.
550 return is_phony() && outputs_.size() == 1 && implicit_outs_ == 0 &&
551 implicit_deps_ == 0;
552}
553
554// static
555string Node::PathDecanonicalized(const string& path, uint64_t slash_bits) {
556 string result = path;
557#ifdef _WIN32
558 uint64_t mask = 1;
559 for (char* c = &result[0]; (c = strchr(c, '/')) != NULL;) {
560 if (slash_bits & mask)
561 *c = '\\';
562 c++;
563 mask <<= 1;
564 }
565#endif
566 return result;
567}
568
569void Node::Dump(const char* prefix) const {
570 printf("%s <%s 0x%p> mtime: %" PRId64 "%s, (:%s), ",
571 prefix, path().c_str(), this,
572 mtime(), exists() ? "" : " (:missing)",
573 dirty() ? " dirty" : " clean");
574 if (in_edge()) {
575 in_edge()->Dump("in-edge: ");
576 } else {
577 printf("no in-edge\n");
578 }
579 printf(" out edges:\n");
580 for (vector<Edge*>::const_iterator e = out_edges().begin();
581 e != out_edges().end() && *e != NULL; ++e) {
582 (*e)->Dump(" +- ");
583 }
584 if (!validation_out_edges().empty()) {
585 printf(" validation out edges:\n");
586 for (std::vector<Edge*>::const_iterator e = validation_out_edges().begin();
587 e != validation_out_edges().end() && *e != NULL; ++e) {
588 (*e)->Dump(" +- ");
589 }
590 }
591}
592
593bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
594 string deps_type = edge->GetBinding("deps");
595 if (!deps_type.empty())
596 return LoadDepsFromLog(edge, err);
597
598 string depfile = edge->GetUnescapedDepfile();
599 if (!depfile.empty())
600 return LoadDepFile(edge, depfile, err);
601
602 // No deps to load.
603 return true;
604}
605
606struct matches {
607 explicit matches(std::vector<StringPiece>::iterator i) : i_(i) {}
608
609 bool operator()(const Node* node) const {
610 StringPiece opath = StringPiece(node->path());
611 return *i_ == opath;
612 }
613
614 std::vector<StringPiece>::iterator i_;
615};
616
617bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
618 string* err) {
619 METRIC_RECORD("depfile load");
620 // Read depfile content. Treat a missing depfile as empty.
621 string content;
622 switch (disk_interface_->ReadFile(path, &content, err)) {
623 case DiskInterface::Okay:
624 break;
625 case DiskInterface::NotFound:
626 err->clear();
627 break;
628 case DiskInterface::OtherError:
629 *err = "loading '" + path + "': " + *err;
630 return false;
631 }
632 // On a missing depfile: return false and empty *err.
633 if (content.empty()) {
634 EXPLAIN("depfile '%s' is missing", path.c_str());
635 return false;
636 }
637
638 DepfileParser depfile(depfile_parser_options_
639 ? *depfile_parser_options_
640 : DepfileParserOptions());
641 string depfile_err;
642 if (!depfile.Parse(&content, &depfile_err)) {
643 *err = path + ": " + depfile_err;
644 return false;
645 }
646
647 if (depfile.outs_.empty()) {
648 *err = path + ": no outputs declared";
649 return false;
650 }
651
652 uint64_t unused;
653 std::vector<StringPiece>::iterator primary_out = depfile.outs_.begin();
654 CanonicalizePath(const_cast<char*>(primary_out->str_), &primary_out->len_,
655 &unused);
656
657 // Check that this depfile matches the edge's output, if not return false to
658 // mark the edge as dirty.
659 Node* first_output = edge->outputs_[0];
660 StringPiece opath = StringPiece(first_output->path());
661 if (opath != *primary_out) {
662 EXPLAIN("expected depfile '%s' to mention '%s', got '%s'", path.c_str(),
663 first_output->path().c_str(), primary_out->AsString().c_str());
664 return false;
665 }
666
667 // Ensure that all mentioned outputs are outputs of the edge.
668 for (std::vector<StringPiece>::iterator o = depfile.outs_.begin();
669 o != depfile.outs_.end(); ++o) {
670 matches m(o);
671 if (std::find_if(edge->outputs_.begin(), edge->outputs_.end(), m) == edge->outputs_.end()) {
672 *err = path + ": depfile mentions '" + o->AsString() + "' as an output, but no such output was declared";
673 return false;
674 }
675 }
676
677 return ProcessDepfileDeps(edge, &depfile.ins_, err);
678}
679
680bool ImplicitDepLoader::ProcessDepfileDeps(
681 Edge* edge, std::vector<StringPiece>* depfile_ins, std::string* err) {
682 // Preallocate space in edge->inputs_ to be filled in below.
683 vector<Node*>::iterator implicit_dep =
684 PreallocateSpace(edge, depfile_ins->size());
685
686 // Add all its in-edges.
687 for (std::vector<StringPiece>::iterator i = depfile_ins->begin();
688 i != depfile_ins->end(); ++i, ++implicit_dep) {
689 uint64_t slash_bits;
690 CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits);
691 Node* node = state_->GetNode(*i, slash_bits);
692 *implicit_dep = node;
693 node->AddOutEdge(edge);
694 CreatePhonyInEdge(node);
695 }
696
697 return true;
698}
699
700bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, string* err) {
701 // NOTE: deps are only supported for single-target edges.
702 Node* output = edge->outputs_[0];
703 DepsLog::Deps* deps = deps_log_ ? deps_log_->GetDeps(output) : NULL;
704 if (!deps) {
705 EXPLAIN("deps for '%s' are missing", output->path().c_str());
706 return false;
707 }
708
709 // Deps are invalid if the output is newer than the deps.
710 if (output->mtime() > deps->mtime) {
711 EXPLAIN("stored deps info out of date for '%s' (%" PRId64 " vs %" PRId64 ")",
712 output->path().c_str(), deps->mtime, output->mtime());
713 return false;
714 }
715
716 vector<Node*>::iterator implicit_dep =
717 PreallocateSpace(edge, deps->node_count);
718 for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) {
719 Node* node = deps->nodes[i];
720 *implicit_dep = node;
721 node->AddOutEdge(edge);
722 CreatePhonyInEdge(node);
723 }
724 return true;
725}
726
727vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge,
728 int count) {
729 edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
730 (size_t)count, 0);
731 edge->implicit_deps_ += count;
732 return edge->inputs_.end() - edge->order_only_deps_ - count;
733}
734
735void ImplicitDepLoader::CreatePhonyInEdge(Node* node) {
736 if (node->in_edge())
737 return;
738
739 Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
740 phony_edge->generated_by_dep_loader_ = true;
741 node->set_in_edge(phony_edge);
742 phony_edge->outputs_.push_back(node);
743
744 // RecomputeDirty might not be called for phony_edge if a previous call
745 // to RecomputeDirty had caused the file to be stat'ed. Because previous
746 // invocations of RecomputeDirty would have seen this node without an
747 // input edge (and therefore ready), we have to set outputs_ready_ to true
748 // to avoid a potential stuck build. If we do call RecomputeDirty for
749 // this node, it will simply set outputs_ready_ to the correct value.
750 phony_edge->outputs_ready_ = true;
751}
752