1 files changed, 148 insertions, 42 deletions

diff --git a/src/graph.cc b/src/graph.cc
index c875d3b..199294d 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -15,6 +15,7 @@
 #include "graph.h"
 
 #include <algorithm>
+#include <deque>
 #include <assert.h>
 #include <stdio.h>
 
@@ -46,13 +47,42 @@ void Node::UpdatePhonyMtime(TimeStamp mtime) {
   }
 }
 
-bool DependencyScan::RecomputeDirty(Node* node, string* err) {
-  vector<Node*> stack;
-  return RecomputeDirty(node, &stack, err);
+bool DependencyScan::RecomputeDirty(Node* initial_node,
+                                    std::vector<Node*>* validation_nodes,
+                                    string* err) {
+  std::vector<Node*> stack;
+  std::vector<Node*> new_validation_nodes;
+
+  std::deque<Node*> nodes(1, initial_node);
+
+  // RecomputeNodeDirty might return new validation nodes that need to be
+  // checked for dirty state, keep a queue of nodes to visit.
+  while (!nodes.empty()) {
+    Node* node = nodes.front();
+    nodes.pop_front();
+
+    stack.clear();
+    new_validation_nodes.clear();
+
+    if (!RecomputeNodeDirty(node, &stack, &new_validation_nodes, err))
+      return false;
+    nodes.insert(nodes.end(), new_validation_nodes.begin(),
+                              new_validation_nodes.end());
+    if (!new_validation_nodes.empty()) {
+      assert(validation_nodes &&
+          "validations require RecomputeDirty to be called with validation_nodes");
+      validation_nodes->insert(validation_nodes->end(),
+                           new_validation_nodes.begin(),
+                           new_validation_nodes.end());
+    }
+  }
+
+  return true;
 }
 
-bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
-                                    string* err) {
+bool DependencyScan::RecomputeNodeDirty(Node* node, std::vector<Node*>* stack,
+                                        std::vector<Node*>* validation_nodes,
+                                        string* err) {
   Edge* edge = node->in_edge();
   if (!edge) {
     // If we already visited this leaf node then we are done.
@@ -96,7 +126,7 @@ bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
     //   Later during the build the dyndep file will become ready and be
     //   loaded to update this edge before it can possibly be scheduled.
     if (edge->dyndep_ && edge->dyndep_->dyndep_pending()) {
-      if (!RecomputeDirty(edge->dyndep_, stack, err))
+      if (!RecomputeNodeDirty(edge->dyndep_, stack, validation_nodes, err))
         return false;
 
       if (!edge->dyndep_->in_edge() ||
@@ -127,12 +157,20 @@ bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
     }
   }
 
+  // Store any validation nodes from the edge for adding to the initial
+  // nodes.  Don't recurse into them, that would trigger the dependency
+  // cycle detector if the validation node depends on this node.
+  // RecomputeDirty will add the validation nodes to the initial nodes
+  // and recurse into them.
+  validation_nodes->insert(validation_nodes->end(),
+      edge->validations_.begin(), edge->validations_.end());
+
   // Visit all inputs; we're dirty if any of the inputs are dirty.
   Node* most_recent_input = NULL;
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
     // Visit this input.
-    if (!RecomputeDirty(*i, stack, err))
+    if (!RecomputeNodeDirty(*i, stack, validation_nodes, err))
       return false;
 
     // If an input is not ready, neither are our outputs.
@@ -260,37 +298,34 @@ bool DependencyScan::RecomputeOutputDirty(const Edge* edge,
     return false;
   }
 
-  BuildLog::LogEntry* entry = 0;
-
   // Dirty if we're missing the output.
   if (!output->exists()) {
     EXPLAIN("output %s doesn't exist", output->path().c_str());
     return true;
   }
 
-  // Dirty if the output is older than the input.
-  if (most_recent_input && output->mtime() < most_recent_input->mtime()) {
-    TimeStamp output_mtime = output->mtime();
-
-    // If this is a restat rule, we may have cleaned the output with a restat
-    // rule in a previous run and stored the most recent input mtime in the
-    // build log.  Use that mtime instead, so that the file will only be
-    // considered dirty if an input was modified since the previous run.
-    bool used_restat = false;
-    if (edge->GetBindingBool("restat") && build_log() &&
-        (entry = build_log()->LookupByOutput(output->path()))) {
-      output_mtime = entry->mtime;
-      used_restat = true;
-    }
+  BuildLog::LogEntry* entry = 0;
 
-    if (output_mtime < most_recent_input->mtime()) {
-      EXPLAIN("%soutput %s older than most recent input %s "
-              "(%" PRId64 " vs %" PRId64 ")",
-              used_restat ? "restat of " : "", output->path().c_str(),
-              most_recent_input->path().c_str(),
-              output_mtime, most_recent_input->mtime());
-      return true;
-    }
+  // If this is a restat rule, we may have cleaned the output in a
+  // previous run and stored the command start time in the build log.
+  // We don't want to consider a restat rule's outputs as dirty unless
+  // an input changed since the last run, so we'll skip checking the
+  // output file's actual mtime and simply check the recorded mtime from
+  // the log against the most recent input's mtime (see below)
+  bool used_restat = false;
+  if (edge->GetBindingBool("restat") && build_log() &&
+      (entry = build_log()->LookupByOutput(output->path()))) {
+    used_restat = true;
+  }
+
+  // Dirty if the output is older than the input.
+  if (!used_restat && most_recent_input && output->mtime() < most_recent_input->mtime()) {
+    EXPLAIN("output %s older than most recent input %s "
+            "(%" PRId64 " vs %" PRId64 ")",
+            output->path().c_str(),
+            most_recent_input->path().c_str(),
+            output->mtime(), most_recent_input->mtime());
+    return true;
   }
 
   if (build_log()) {
@@ -308,7 +343,9 @@ bool DependencyScan::RecomputeOutputDirty(const Edge* edge,
         // May also be dirty due to the mtime in the log being older than the
         // mtime of the most recent input.  This can occur even when the mtime
         // on disk is newer if a previous run wrote to the output file but
-        // exited with an error or was interrupted.
+        // exited with an error or was interrupted. If this was a restat rule,
+        // then we only check the recorded mtime against the most recent input
+        // mtime and ignore the actual output's mtime above.
         EXPLAIN("recorded mtime of %s older than most recent input %s (%" PRId64 " vs %" PRId64 ")",
                 output->path().c_str(), most_recent_input->path().c_str(),
                 entry->mtime, most_recent_input->mtime());
@@ -355,7 +392,7 @@ struct EdgeEnv : public Env {
   std::string MakePathList(const Node* const* span, size_t size, char sep) const;
 
  private:
-  vector<string> lookups_;
+  std::vector<std::string> lookups_;
   const Edge* const edge_;
   EscapeKind escape_in_out_;
   bool recursive_;
@@ -365,21 +402,50 @@ string EdgeEnv::LookupVariable(const string& var) {
   if (var == "in" || var == "in_newline") {
     int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ -
       edge_->order_only_deps_;
-#if __cplusplus >= 201103L
     return MakePathList(edge_->inputs_.data(), explicit_deps_count,
-#else
-    return MakePathList(&edge_->inputs_[0], explicit_deps_count,
-#endif
                         var == "in" ? ' ' : '\n');
   } else if (var == "out") {
     int explicit_outs_count = edge_->outputs_.size() - edge_->implicit_outs_;
     return MakePathList(&edge_->outputs_[0], explicit_outs_count, ' ');
   }
 
+  // Technical note about the lookups_ vector.
+  //
+  // This is used to detect cycles during recursive variable expansion
+  // which can be seen as a graph traversal problem. Consider the following
+  // example:
+  //
+  //    rule something
+  //      command = $foo $foo $var1
+  //      var1 = $var2
+  //      var2 = $var3
+  //      var3 = $var1
+  //      foo = FOO
+  //
+  // Each variable definition can be seen as a node in a graph that looks
+  // like the following:
+  //
+  //   command --> foo
+  //      |
+  //      v
+  //    var1 <-----.
+  //      |        |
+  //      v        |
+  //    var2 ---> var3
+  //
+  // The lookups_ vector is used as a stack of visited nodes/variables
+  // during recursive expansion. Entering a node adds an item to the
+  // stack, leaving the node removes it.
+  //
+  // The recursive_ flag is used as a small performance optimization
+  // to never record the starting node in the stack when beginning a new
+  // expansion, since in most cases, expansions are not recursive
+  // at all.
+  //
   if (recursive_) {
-    vector<string>::const_iterator it;
-    if ((it = find(lookups_.begin(), lookups_.end(), var)) != lookups_.end()) {
-      string cycle;
+    auto it = std::find(lookups_.begin(), lookups_.end(), var);
+    if (it != lookups_.end()) {
+      std::string cycle;
       for (; it != lookups_.end(); ++it)
         cycle.append(*it + " -> ");
       cycle.append(var);
@@ -389,13 +455,17 @@ string EdgeEnv::LookupVariable(const string& var) {
 
   // See notes on BindingEnv::LookupWithFallback.
   const EvalString* eval = edge_->rule_->GetBinding(var);
-  if (recursive_ && eval)
+  bool record_varname = recursive_ && eval;
+  if (record_varname)
     lookups_.push_back(var);
 
   // In practice, variables defined on rules never use another rule variable.
   // For performance, only start checking for cycles after the first lookup.
   recursive_ = true;
-  return edge_->env_->LookupWithFallback(var, eval, this);
+  std::string result = edge_->env_->LookupWithFallback(var, eval, this);
+  if (record_varname)
+    lookups_.pop_back();
+  return result;
 }
 
 std::string EdgeEnv::MakePathList(const Node* const* const span,
@@ -418,6 +488,28 @@ std::string EdgeEnv::MakePathList(const Node* const* const span,
   return result;
 }
 
+void Edge::CollectInputs(bool shell_escape,
+                         std::vector<std::string>* out) const {
+  for (std::vector<Node*>::const_iterator it = inputs_.begin();
+       it != inputs_.end(); ++it) {
+    std::string path = (*it)->PathDecanonicalized();
+    if (shell_escape) {
+      std::string unescaped;
+      unescaped.swap(path);
+#ifdef _WIN32
+      GetWin32EscapedString(unescaped, &path);
+#else
+      GetShellEscapedString(unescaped, &path);
+#endif
+    }
+#if __cplusplus >= 201103L
+    out->push_back(std::move(path));
+#else
+    out->push_back(path);
+#endif
+  }
+}
+
 std::string Edge::EvaluateCommand(const bool incl_rsp_file) const {
   string command = GetBinding("command");
   if (incl_rsp_file) {
@@ -463,6 +555,13 @@ void Edge::Dump(const char* prefix) const {
        i != outputs_.end() && *i != NULL; ++i) {
     printf("%s ", (*i)->path().c_str());
   }
+  if (!validations_.empty()) {
+    printf(" validations ");
+    for (std::vector<Node*>::const_iterator i = validations_.begin();
+         i != validations_.end() && *i != NULL; ++i) {
+      printf("%s ", (*i)->path().c_str());
+    }
+  }
   if (pool_) {
     if (!pool_->name().empty()) {
       printf("(in pool '%s')", pool_->name().c_str());
@@ -519,6 +618,13 @@ void Node::Dump(const char* prefix) const {
        e != out_edges().end() && *e != NULL; ++e) {
     (*e)->Dump(" +- ");
   }
+  if (!validation_out_edges().empty()) {
+    printf(" validation out edges:\n");
+    for (std::vector<Edge*>::const_iterator e = validation_out_edges().begin();
+         e != validation_out_edges().end() && *e != NULL; ++e) {
+      (*e)->Dump(" +- ");
+    }
+  }
 }
 
 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {