1 files changed, 100 insertions, 35 deletions

diff --git a/src/graph.cc b/src/graph.cc
index f1d9ca2..7dd9491 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -28,24 +28,47 @@
 #include "util.h"
 
 bool Node::Stat(DiskInterface* disk_interface, string* err) {
-  METRIC_RECORD("node stat");
   return (mtime_ = disk_interface->Stat(path_, err)) != -1;
 }
 
-bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
+bool DependencyScan::RecomputeDirty(Node* node, string* err) {
+  vector<Node*> stack;
+  return RecomputeDirty(node, &stack, err);
+}
+
+bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
+                                    string* err) {
+  Edge* edge = node->in_edge();
+  if (!edge) {
+    // If we already visited this leaf node then we are done.
+    if (node->status_known())
+      return true;
+    // This node has no in-edge; it is dirty if it is missing.
+    if (!node->StatIfNecessary(disk_interface_, err))
+      return false;
+    if (!node->exists())
+      EXPLAIN("%s has no in-edge and is missing", node->path().c_str());
+    node->set_dirty(!node->exists());
+    return true;
+  }
+
+  // If we already finished this edge then we are done.
+  if (edge->mark_ == Edge::VisitDone)
+    return true;
+
+  // If we encountered this edge earlier in the call stack we have a cycle.
+  if (!VerifyDAG(node, stack, err))
+    return false;
+
+  // Mark the edge temporarily while in the call stack.
+  edge->mark_ = Edge::VisitInStack;
+  stack->push_back(node);
+
   bool dirty = false;
   edge->outputs_ready_ = true;
   edge->deps_missing_ = false;
 
   // Load output mtimes so we can compare them to the most recent input below.
-  // RecomputeDirty() recursively walks the graph following the input nodes
-  // of |edge| and the in_edges of these nodes.  It uses the stat state of each
-  // node to mark nodes as visited and doesn't traverse across nodes that have
-  // been visited already.  To make sure that every edge is visited only once
-  // (important because an edge's deps are loaded every time it's visited), mark
-  // all outputs of |edge| visited as a first step.  This ensures that edges
-  // with multiple inputs and outputs are visited only once, even in cyclic
-  // graphs.
   for (vector<Node*>::iterator o = edge->outputs_.begin();
        o != edge->outputs_.end(); ++o) {
     if (!(*o)->StatIfNecessary(disk_interface_, err))
@@ -64,19 +87,9 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
   Node* most_recent_input = NULL;
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
-    if (!(*i)->status_known()) {
-      if (!(*i)->StatIfNecessary(disk_interface_, err))
-        return false;
-      if (Edge* in_edge = (*i)->in_edge()) {
-        if (!RecomputeDirty(in_edge, err))
-          return false;
-      } else {
-        // This input has no in-edge; it is dirty if it is missing.
-        if (!(*i)->exists())
-          EXPLAIN("%s has no in-edge and is missing", (*i)->path().c_str());
-        (*i)->set_dirty(!(*i)->exists());
-      }
-    }
+    // Visit this input.
+    if (!RecomputeDirty(*i, stack, err))
+      return false;
 
     // If an input is not ready, neither are our outputs.
     if (Edge* in_edge = (*i)->in_edge()) {
@@ -119,9 +132,47 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
   if (dirty && !(edge->is_phony() && edge->inputs_.empty()))
     edge->outputs_ready_ = false;
 
+  // Mark the edge as finished during this walk now that it will no longer
+  // be in the call stack.
+  edge->mark_ = Edge::VisitDone;
+  assert(stack->back() == node);
+  stack->pop_back();
+
   return true;
 }
 
+bool DependencyScan::VerifyDAG(Node* node, vector<Node*>* stack, string* err) {
+  Edge* edge = node->in_edge();
+  assert(edge != NULL);
+
+  // If we have no temporary mark on the edge then we do not yet have a cycle.
+  if (edge->mark_ != Edge::VisitInStack)
+    return true;
+
+  // We have this edge earlier in the call stack.  Find it.
+  vector<Node*>::iterator start = stack->begin();
+  while (start != stack->end() && (*start)->in_edge() != edge)
+    ++start;
+  assert(start != stack->end());
+
+  // Make the cycle clear by reporting its start as the node at its end
+  // instead of some other output of the starting edge.  For example,
+  // running 'ninja b' on
+  //   build a b: cat c
+  //   build c: cat a
+  // should report a -> c -> a instead of b -> c -> a.
+  *start = node;
+
+  // Construct the error message rejecting the cycle.
+  *err = "dependency cycle: ";
+  for (vector<Node*>::const_iterator i = start; i != stack->end(); ++i) {
+    err->append((*i)->path());
+    err->append(" -> ");
+  }
+  err->append((*start)->path());
+  return false;
+}
+
 bool DependencyScan::RecomputeOutputsDirty(Edge* edge, Node* most_recent_input,
                                            bool* outputs_dirty, string* err) {
   string command = edge->EvaluateCommand(/*incl_rsp_file=*/true);
@@ -169,7 +220,7 @@ bool DependencyScan::RecomputeOutputDirty(Edge* edge,
     bool used_restat = false;
     if (edge->GetBindingBool("restat") && build_log() &&
         (entry = build_log()->LookupByOutput(output->path()))) {
-      output_mtime = entry->restat_mtime;
+      output_mtime = entry->mtime;
       used_restat = true;
     }
 
@@ -183,17 +234,29 @@ bool DependencyScan::RecomputeOutputDirty(Edge* edge,
     }
   }
 
-  // May also be dirty due to the command changing since the last build.
-  // But if this is a generator rule, the command changing does not make us
-  // dirty.
-  if (!edge->GetBindingBool("generator") && build_log()) {
+  if (build_log()) {
+    bool generator = edge->GetBindingBool("generator");
     if (entry || (entry = build_log()->LookupByOutput(output->path()))) {
-      if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
+      if (!generator &&
+          BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
+        // May also be dirty due to the command changing since the last build.
+        // But if this is a generator rule, the command changing does not make us
+        // dirty.
         EXPLAIN("command line changed for %s", output->path().c_str());
         return true;
       }
+      if (most_recent_input && entry->mtime < most_recent_input->mtime()) {
+        // 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.
+        EXPLAIN("recorded mtime of %s older than most recent input %s (%d vs %d)",
+                output->path().c_str(), most_recent_input->path().c_str(),
+                entry->mtime, most_recent_input->mtime());
+        return true;
+      }
     }
-    if (!entry) {
+    if (!entry && !generator) {
       EXPLAIN("command line not found in log for %s", output->path().c_str());
       return true;
     }
@@ -348,10 +411,10 @@ bool Edge::use_console() const {
 }
 
 // static
-string Node::PathDecanonicalized(const string& path, unsigned int slash_bits) {
+string Node::PathDecanonicalized(const string& path, uint64_t slash_bits) {
   string result = path;
 #ifdef _WIN32
-  unsigned int mask = 1;
+  uint64_t mask = 1;
   for (char* c = &result[0]; (c = strchr(c, '/')) != NULL;) {
     if (slash_bits & mask)
       *c = '\\';
@@ -420,10 +483,12 @@ bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
     return false;
   }
 
-  unsigned int unused;
+  uint64_t unused;
   if (!CanonicalizePath(const_cast<char*>(depfile.out_.str_),
-                        &depfile.out_.len_, &unused, err))
+                        &depfile.out_.len_, &unused, err)) {
+    *err = path + ": " + *err;
     return false;
+  }
 
   // Check that this depfile matches the edge's output, if not return false to
   // mark the edge as dirty.
@@ -442,7 +507,7 @@ bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
   // Add all its in-edges.
   for (vector<StringPiece>::iterator i = depfile.ins_.begin();
        i != depfile.ins_.end(); ++i, ++implicit_dep) {
-    unsigned int slash_bits;
+    uint64_t slash_bits;
     if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits,
                           err))
       return false;