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