src/graph.cc

   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, string* err) {
  31   return (mtime_ = disk_interface->Stat(path_, err)) != -1;
  32 }
  33
  34 bool DependencyScan::RecomputeDirty(Node* node, string* err) {
  35   vector<Node*> stack;
  36   return RecomputeDirty(node, &stack, err);
  37 }
  38
  39 bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
  40                                     string* err) {
  41   Edge* edge = node->in_edge();
  42   if (!edge) {
  43     // If we already visited this leaf node then we are done.
  44     if (node->status_known())
  45       return true;
  46     // This node has no in-edge; it is dirty if it is missing.
  47     if (!node->StatIfNecessary(disk_interface_, err))
  48       return false;
  49     if (!node->exists())
  50       EXPLAIN("%s has no in-edge and is missing", node->path().c_str());
  51     node->set_dirty(!node->exists());
  52     return true;
  53   }
  54
  55   // If we already finished this edge then we are done.
  56   if (edge->mark_ == Edge::VisitDone)
  57     return true;
  58
  59   // If we encountered this edge earlier in the call stack we have a cycle.
  60   if (!VerifyDAG(node, stack, err))
  61     return false;
  62
  63   // Mark the edge temporarily while in the call stack.
  64   edge->mark_ = Edge::VisitInStack;
  65   stack->push_back(node);
  66
  67   bool dirty = false;
  68   edge->outputs_ready_ = true;
  69   edge->deps_missing_ = false;
  70
  71   // Load output mtimes so we can compare them to the most recent input below.
  72   for (vector<Node*>::iterator o = edge->outputs_.begin();
  73        o != edge->outputs_.end(); ++o) {
  74     if (!(*o)->StatIfNecessary(disk_interface_, err))
  75       return false;
  76   }
  77
  78   if (!dep_loader_.LoadDeps(edge, err)) {
  79     if (!err->empty())
  80       return false;
  81     // Failed to load dependency info: rebuild to regenerate it.
  82     // LoadDeps() did EXPLAIN() already, no need to do it here.
  83     dirty = edge->deps_missing_ = true;
  84   }
  85
  86   // Visit all inputs; we're dirty if any of the inputs are dirty.
  87   Node* most_recent_input = NULL;
  88   for (vector<Node*>::iterator i = edge->inputs_.begin();
  89        i != edge->inputs_.end(); ++i) {
  90     // Visit this input.
  91     if (!RecomputeDirty(*i, stack, err))
  92       return false;
  93
  94     // If an input is not ready, neither are our outputs.
  95     if (Edge* in_edge = (*i)->in_edge()) {
  96       if (!in_edge->outputs_ready_)
  97         edge->outputs_ready_ = false;
  98     }
  99
 100     if (!edge->is_order_only(i - edge->inputs_.begin())) {
 101       // If a regular input is dirty (or missing), we're dirty.
 102       // Otherwise consider mtime.
 103       if ((*i)->dirty()) {
 104         EXPLAIN("%s is dirty", (*i)->path().c_str());
 105         dirty = true;
 106       } else {
 107         if (!most_recent_input || (*i)->mtime() > most_recent_input->mtime()) {
 108           most_recent_input = *i;
 109         }
 110       }
 111     }
 112   }
 113
 114   // We may also be dirty due to output state: missing outputs, out of
 115   // date outputs, etc.  Visit all outputs and determine whether they're dirty.
 116   if (!dirty)
 117     if (!RecomputeOutputsDirty(edge, most_recent_input, &dirty, err))
 118       return false;
 119
 120   // Finally, visit each output and update their dirty state if necessary.
 121   for (vector<Node*>::iterator o = edge->outputs_.begin();
 122        o != edge->outputs_.end(); ++o) {
 123     if (dirty)
 124       (*o)->MarkDirty();
 125   }
 126
 127   // If an edge is dirty, its outputs are normally not ready.  (It's
 128   // possible to be clean but still not be ready in the presence of
 129   // order-only inputs.)
 130   // But phony edges with no inputs have nothing to do, so are always
 131   // ready.
 132   if (dirty && !(edge->is_phony() && edge->inputs_.empty()))
 133     edge->outputs_ready_ = false;
 134
 135   // Mark the edge as finished during this walk now that it will no longer
 136   // be in the call stack.
 137   edge->mark_ = Edge::VisitDone;
 138   assert(stack->back() == node);
 139   stack->pop_back();
 140
 141   return true;
 142 }
 143
 144 bool DependencyScan::VerifyDAG(Node* node, vector<Node*>* stack, string* err) {
 145   Edge* edge = node->in_edge();
 146   assert(edge != NULL);
 147
 148   // If we have no temporary mark on the edge then we do not yet have a cycle.
 149   if (edge->mark_ != Edge::VisitInStack)
 150     return true;
 151
 152   // We have this edge earlier in the call stack.  Find it.
 153   vector<Node*>::iterator start = stack->begin();
 154   while (start != stack->end() && (*start)->in_edge() != edge)
 155     ++start;
 156   assert(start != stack->end());
 157
 158   // Make the cycle clear by reporting its start as the node at its end
 159   // instead of some other output of the starting edge.  For example,
 160   // running 'ninja b' on
 161   //   build a b: cat c
 162   //   build c: cat a
 163   // should report a -> c -> a instead of b -> c -> a.
 164   *start = node;
 165
 166   // Construct the error message rejecting the cycle.
 167   *err = "dependency cycle: ";
 168   for (vector<Node*>::const_iterator i = start; i != stack->end(); ++i) {
 169     err->append((*i)->path());
 170     err->append(" -> ");
 171   }
 172   err->append((*start)->path());
 173
 174   if ((start + 1) == stack->end() && edge->maybe_phonycycle_diagnostic()) {
 175     // The manifest parser would have filtered out the self-referencing
 176     // input if it were not configured to allow the error.
 177     err->append(" [-w phonycycle=err]");
 178   }
 179
 180   return false;
 181 }
 182
 183 bool DependencyScan::RecomputeOutputsDirty(Edge* edge, Node* most_recent_input,
 184                                            bool* outputs_dirty, string* err) {
 185   string command = edge->EvaluateCommand(/*incl_rsp_file=*/true);
 186   for (vector<Node*>::iterator o = edge->outputs_.begin();
 187        o != edge->outputs_.end(); ++o) {
 188     if (RecomputeOutputDirty(edge, most_recent_input, command, *o)) {
 189       *outputs_dirty = true;
 190       return true;
 191     }
 192   }
 193   return true;
 194 }
 195
 196 bool DependencyScan::RecomputeOutputDirty(Edge* edge,
 197                                           Node* most_recent_input,
 198                                           const string& command,
 199                                           Node* output) {
 200   if (edge->is_phony()) {
 201     // Phony edges don't write any output.  Outputs are only dirty if
 202     // there are no inputs and we're missing the output.
 203     if (edge->inputs_.empty() && !output->exists()) {
 204       EXPLAIN("output %s of phony edge with no inputs doesn't exist",
 205               output->path().c_str());
 206       return true;
 207     }
 208     return false;
 209   }
 210
 211   BuildLog::LogEntry* entry = 0;
 212
 213   // Dirty if we're missing the output.
 214   if (!output->exists()) {
 215     EXPLAIN("output %s doesn't exist", output->path().c_str());
 216     return true;
 217   }
 218
 219   // Dirty if the output is older than the input.
 220   if (most_recent_input && output->mtime() < most_recent_input->mtime()) {
 221     TimeStamp output_mtime = output->mtime();
 222
 223     // If this is a restat rule, we may have cleaned the output with a restat
 224     // rule in a previous run and stored the most recent input mtime in the
 225     // build log.  Use that mtime instead, so that the file will only be
 226     // considered dirty if an input was modified since the previous run.
 227     bool used_restat = false;
 228     if (edge->GetBindingBool("restat") && build_log() &&
 229         (entry = build_log()->LookupByOutput(output->path()))) {
 230       output_mtime = entry->mtime;
 231       used_restat = true;
 232     }
 233
 234     if (output_mtime < most_recent_input->mtime()) {
 235       EXPLAIN("%soutput %s older than most recent input %s "
 236               "(%d vs %d)",
 237               used_restat ? "restat of " : "", output->path().c_str(),
 238               most_recent_input->path().c_str(),
 239               output_mtime, most_recent_input->mtime());
 240       return true;
 241     }
 242   }
 243
 244   if (build_log()) {
 245     bool generator = edge->GetBindingBool("generator");
 246     if (entry || (entry = build_log()->LookupByOutput(output->path()))) {
 247       if (!generator &&
 248           BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
 249         // May also be dirty due to the command changing since the last build.
 250         // But if this is a generator rule, the command changing does not make us
 251         // dirty.
 252         EXPLAIN("command line changed for %s", output->path().c_str());
 253         return true;
 254       }
 255       if (most_recent_input && entry->mtime < most_recent_input->mtime()) {
 256         // May also be dirty due to the mtime in the log being older than the
 257         // mtime of the most recent input.  This can occur even when the mtime
 258         // on disk is newer if a previous run wrote to the output file but
 259         // exited with an error or was interrupted.
 260         EXPLAIN("recorded mtime of %s older than most recent input %s (%d vs %d)",
 261                 output->path().c_str(), most_recent_input->path().c_str(),
 262                 entry->mtime, most_recent_input->mtime());
 263         return true;
 264       }
 265     }
 266     if (!entry && !generator) {
 267       EXPLAIN("command line not found in log for %s", output->path().c_str());
 268       return true;
 269     }
 270   }
 271
 272   return false;
 273 }
 274
 275 bool Edge::AllInputsReady() const {
 276   for (vector<Node*>::const_iterator i = inputs_.begin();
 277        i != inputs_.end(); ++i) {
 278     if ((*i)->in_edge() && !(*i)->in_edge()->outputs_ready())
 279       return false;
 280   }
 281   return true;
 282 }
 283
 284 /// An Env for an Edge, providing $in and $out.
 285 struct EdgeEnv : public Env {
 286   enum EscapeKind { kShellEscape, kDoNotEscape };
 287
 288   EdgeEnv(Edge* edge, EscapeKind escape)
 289       : edge_(edge), escape_in_out_(escape), recursive_(false) {}
 290   virtual string LookupVariable(const string& var);
 291
 292   /// Given a span of Nodes, construct a list of paths suitable for a command
 293   /// line.
 294   string MakePathList(vector<Node*>::iterator begin,
 295                       vector<Node*>::iterator end,
 296                       char sep);
 297
 298  private:
 299   vector<string> lookups_;
 300   Edge* edge_;
 301   EscapeKind escape_in_out_;
 302   bool recursive_;
 303 };
 304
 305 string EdgeEnv::LookupVariable(const string& var) {
 306   if (var == "in" || var == "in_newline") {
 307     int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ -
 308       edge_->order_only_deps_;
 309     return MakePathList(edge_->inputs_.begin(),
 310                         edge_->inputs_.begin() + explicit_deps_count,
 311                         var == "in" ? ' ' : '\n');
 312   } else if (var == "out") {
 313     int explicit_outs_count = edge_->outputs_.size() - edge_->implicit_outs_;
 314     return MakePathList(edge_->outputs_.begin(),
 315                         edge_->outputs_.begin() + explicit_outs_count,
 316                         ' ');
 317   }
 318
 319   if (recursive_) {
 320     vector<string>::const_iterator it;
 321     if ((it = find(lookups_.begin(), lookups_.end(), var)) != lookups_.end()) {
 322       string cycle;
 323       for (; it != lookups_.end(); ++it)
 324         cycle.append(*it + " -> ");
 325       cycle.append(var);
 326       Fatal(("cycle in rule variables: " + cycle).c_str());
 327     }
 328   }
 329
 330   // See notes on BindingEnv::LookupWithFallback.
 331   const EvalString* eval = edge_->rule_->GetBinding(var);
 332   if (recursive_ && eval)
 333     lookups_.push_back(var);
 334
 335   // In practice, variables defined on rules never use another rule variable.
 336   // For performance, only start checking for cycles after the first lookup.
 337   recursive_ = true;
 338   return edge_->env_->LookupWithFallback(var, eval, this);
 339 }
 340
 341 string EdgeEnv::MakePathList(vector<Node*>::iterator begin,
 342                              vector<Node*>::iterator end,
 343                              char sep) {
 344   string result;
 345   for (vector<Node*>::iterator i = begin; i != end; ++i) {
 346     if (!result.empty())
 347       result.push_back(sep);
 348     const string& path = (*i)->PathDecanonicalized();
 349     if (escape_in_out_ == kShellEscape) {
 350 #if _WIN32
 351       GetWin32EscapedString(path, &result);
 352 #else
 353       GetShellEscapedString(path, &result);
 354 #endif
 355     } else {
 356       result.append(path);
 357     }
 358   }
 359   return result;
 360 }
 361
 362 string Edge::EvaluateCommand(bool incl_rsp_file) {
 363   string command = GetBinding("command");
 364   if (incl_rsp_file) {
 365     string rspfile_content = GetBinding("rspfile_content");
 366     if (!rspfile_content.empty())
 367       command += ";rspfile=" + rspfile_content;
 368   }
 369   return command;
 370 }
 371
 372 string Edge::GetBinding(const string& key) {
 373   EdgeEnv env(this, EdgeEnv::kShellEscape);
 374   return env.LookupVariable(key);
 375 }
 376
 377 bool Edge::GetBindingBool(const string& key) {
 378   return !GetBinding(key).empty();
 379 }
 380
 381 string Edge::GetUnescapedDepfile() {
 382   EdgeEnv env(this, EdgeEnv::kDoNotEscape);
 383   return env.LookupVariable("depfile");
 384 }
 385
 386 string Edge::GetUnescapedRspfile() {
 387   EdgeEnv env(this, EdgeEnv::kDoNotEscape);
 388   return env.LookupVariable("rspfile");
 389 }
 390
 391 void Edge::Dump(const char* prefix) const {
 392   printf("%s[ ", prefix);
 393   for (vector<Node*>::const_iterator i = inputs_.begin();
 394        i != inputs_.end() && *i != NULL; ++i) {
 395     printf("%s ", (*i)->path().c_str());
 396   }
 397   printf("--%s-> ", rule_->name().c_str());
 398   for (vector<Node*>::const_iterator i = outputs_.begin();
 399        i != outputs_.end() && *i != NULL; ++i) {
 400     printf("%s ", (*i)->path().c_str());
 401   }
 402   if (pool_) {
 403     if (!pool_->name().empty()) {
 404       printf("(in pool '%s')", pool_->name().c_str());
 405     }
 406   } else {
 407     printf("(null pool?)");
 408   }
 409   printf("] 0x%p\n", this);
 410 }
 411
 412 bool Edge::is_phony() const {
 413   return rule_ == &State::kPhonyRule;
 414 }
 415
 416 bool Edge::use_console() const {
 417   return pool() == &State::kConsolePool;
 418 }
 419
 420 bool Edge::maybe_phonycycle_diagnostic() const {
 421   // CMake 2.8.12.x and 3.0.x produced self-referencing phony rules
 422   // of the form "build a: phony ... a ...".   Restrict our
 423   // "phonycycle" diagnostic option to the form it used.
 424   return is_phony() && outputs_.size() == 1 && implicit_outs_ == 0 &&
 425       implicit_deps_ == 0;
 426 }
 427
 428 // static
 429 string Node::PathDecanonicalized(const string& path, uint64_t slash_bits) {
 430   string result = path;
 431 #ifdef _WIN32
 432   uint64_t mask = 1;
 433   for (char* c = &result[0]; (c = strchr(c, '/')) != NULL;) {
 434     if (slash_bits & mask)
 435       *c = '\\';
 436     c++;
 437     mask <<= 1;
 438   }
 439 #endif
 440   return result;
 441 }
 442
 443 void Node::Dump(const char* prefix) const {
 444   printf("%s <%s 0x%p> mtime: %d%s, (:%s), ",
 445          prefix, path().c_str(), this,
 446          mtime(), mtime() ? "" : " (:missing)",
 447          dirty() ? " dirty" : " clean");
 448   if (in_edge()) {
 449     in_edge()->Dump("in-edge: ");
 450   } else {
 451     printf("no in-edge\n");
 452   }
 453   printf(" out edges:\n");
 454   for (vector<Edge*>::const_iterator e = out_edges().begin();
 455        e != out_edges().end() && *e != NULL; ++e) {
 456     (*e)->Dump(" +- ");
 457   }
 458 }
 459
 460 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
 461   string deps_type = edge->GetBinding("deps");
 462   if (!deps_type.empty())
 463     return LoadDepsFromLog(edge, err);
 464
 465   string depfile = edge->GetUnescapedDepfile();
 466   if (!depfile.empty())
 467     return LoadDepFile(edge, depfile, err);
 468
 469   // No deps to load.
 470   return true;
 471 }
 472
 473 bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
 474                                     string* err) {
 475   METRIC_RECORD("depfile load");
 476   // Read depfile content.  Treat a missing depfile as empty.
 477   string content;
 478   switch (disk_interface_->ReadFile(path, &content, err)) {
 479   case DiskInterface::Okay:
 480     break;
 481   case DiskInterface::NotFound:
 482     err->clear();
 483     break;
 484   case DiskInterface::OtherError:
 485     *err = "loading '" + path + "': " + *err;
 486     return false;
 487   }
 488   // On a missing depfile: return false and empty *err.
 489   if (content.empty()) {
 490     EXPLAIN("depfile '%s' is missing", path.c_str());
 491     return false;
 492   }
 493
 494   DepfileParser depfile;
 495   string depfile_err;
 496   if (!depfile.Parse(&content, &depfile_err)) {
 497     *err = path + ": " + depfile_err;
 498     return false;
 499   }
 500
 501   uint64_t unused;
 502   if (!CanonicalizePath(const_cast<char*>(depfile.out_.str_),
 503                         &depfile.out_.len_, &unused, err)) {
 504     *err = path + ": " + *err;
 505     return false;
 506   }
 507
 508   // Check that this depfile matches the edge's output, if not return false to
 509   // mark the edge as dirty.
 510   Node* first_output = edge->outputs_[0];
 511   StringPiece opath = StringPiece(first_output->path());
 512   if (opath != depfile.out_) {
 513     EXPLAIN("expected depfile '%s' to mention '%s', got '%s'", path.c_str(),
 514             first_output->path().c_str(), depfile.out_.AsString().c_str());
 515     return false;
 516   }
 517
 518   // Preallocate space in edge->inputs_ to be filled in below.
 519   vector<Node*>::iterator implicit_dep =
 520       PreallocateSpace(edge, depfile.ins_.size());
 521
 522   // Add all its in-edges.
 523   for (vector<StringPiece>::iterator i = depfile.ins_.begin();
 524        i != depfile.ins_.end(); ++i, ++implicit_dep) {
 525     uint64_t slash_bits;
 526     if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits,
 527                           err))
 528       return false;
 529
 530     Node* node = state_->GetNode(*i, slash_bits);
 531     *implicit_dep = node;
 532     node->AddOutEdge(edge);
 533     CreatePhonyInEdge(node);
 534   }
 535
 536   return true;
 537 }
 538
 539 bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, string* err) {
 540   // NOTE: deps are only supported for single-target edges.
 541   Node* output = edge->outputs_[0];
 542   DepsLog::Deps* deps = deps_log_->GetDeps(output);
 543   if (!deps) {
 544     EXPLAIN("deps for '%s' are missing", output->path().c_str());
 545     return false;
 546   }
 547
 548   // Deps are invalid if the output is newer than the deps.
 549   if (output->mtime() > deps->mtime) {
 550     EXPLAIN("stored deps info out of date for '%s' (%d vs %d)",
 551             output->path().c_str(), deps->mtime, output->mtime());
 552     return false;
 553   }
 554
 555   vector<Node*>::iterator implicit_dep =
 556       PreallocateSpace(edge, deps->node_count);
 557   for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) {
 558     Node* node = deps->nodes[i];
 559     *implicit_dep = node;
 560     node->AddOutEdge(edge);
 561     CreatePhonyInEdge(node);
 562   }
 563   return true;
 564 }
 565
 566 vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge,
 567                                                             int count) {
 568   edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
 569                        (size_t)count, 0);
 570   edge->implicit_deps_ += count;
 571   return edge->inputs_.end() - edge->order_only_deps_ - count;
 572 }
 573
 574 void ImplicitDepLoader::CreatePhonyInEdge(Node* node) {
 575   if (node->in_edge())
 576     return;
 577
 578   Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
 579   node->set_in_edge(phony_edge);
 580   phony_edge->outputs_.push_back(node);
 581
 582   // RecomputeDirty might not be called for phony_edge if a previous call
 583   // to RecomputeDirty had caused the file to be stat'ed.  Because previous
 584   // invocations of RecomputeDirty would have seen this node without an
 585   // input edge (and therefore ready), we have to set outputs_ready_ to true
 586   // to avoid a potential stuck build.  If we do call RecomputeDirty for
 587   // this node, it will simply set outputs_ready_ to the correct value.
 588   phony_edge->outputs_ready_ = true;
 589 }