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