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