Merge pull request #125 from pcc/outputs-ready

CMake requirements: Make-style order-only dependencies, restat rules

12 files changed, 437 insertions, 134 deletions

diff --git a/src/build.cc b/src/build.cc
index e72d9d7..9465532 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -175,7 +175,7 @@ void BuildStatus::PrintStatus(Edge* edge) {
   }
 }
 
-Plan::Plan() : command_edges_(0) {}
+Plan::Plan() : command_edges_(0), wanted_edges_(0) {}
 
 bool Plan::AddTarget(Node* node, string* err) {
   vector<Node*> stack;
@@ -199,30 +199,39 @@ bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) {
   if (CheckDependencyCycle(node, stack, err))
     return false;
 
-  if (!node->dirty())
+  if (edge->outputs_ready())
     return false;  // Don't need to do anything.
-  if (want_.find(edge) != want_.end())
-    return true;  // We've already enqueued it.
-  want_.insert(edge);
-  if (!edge->is_phony())
-    ++command_edges_;
+
+  // If an entry in want_ does not already exist for edge, create an entry which
+  // maps to false, indicating that we do not want to build this entry itself.
+  pair<map<Edge*, bool>::iterator, bool> want_ins =
+    want_.insert(make_pair(edge, false));
+  bool& want = want_ins.first->second;
+
+  // If we do need to build edge and we haven't already marked it as wanted,
+  // mark it now.
+  if (node->dirty() && !want) {
+    want = true;
+    ++wanted_edges_;
+    if (find_if(edge->inputs_.begin(), edge->inputs_.end(),
+                not1(mem_fun(&Node::ready))) == edge->inputs_.end())
+      ready_.insert(edge);
+    if (!edge->is_phony())
+      ++command_edges_;
+  }
+
+  if (!want_ins.second)
+    return true;  // We've already processed the inputs.
 
   stack->push_back(node);
-  bool awaiting_inputs = false;
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
-    if (AddSubTarget(*i, stack, err)) {
-      awaiting_inputs = true;
-    } else if (!err->empty()) {
+    if (!AddSubTarget(*i, stack, err) && !err->empty())
       return false;
-    }
   }
   assert(stack->back() == node);
   stack->pop_back();
 
-  if (!awaiting_inputs)
-    ready_.insert(edge);
-
   return true;
 }
 
@@ -256,7 +265,12 @@ Edge* Plan::FindWork() {
 }
 
 void Plan::EdgeFinished(Edge* edge) {
-  want_.erase(edge);
+  map<Edge*, bool>::iterator i = want_.find(edge);
+  assert(i != want_.end());
+  if (i->second)
+    --wanted_edges_;
+  want_.erase(i);
+  edge->outputs_ready_ = true;
 
   // Check off any nodes we were waiting for with this edge.
   for (vector<Node*>::iterator i = edge->outputs_.begin();
@@ -269,26 +283,84 @@ void Plan::NodeFinished(Node* node) {
   // See if we we want any edges from this node.
   for (vector<Edge*>::iterator i = node->out_edges_.begin();
        i != node->out_edges_.end(); ++i) {
-    if (want_.find(*i) != want_.end()) {
-      // See if the edge is now ready.
-      bool ready = true;
-      for (vector<Node*>::iterator j = (*i)->inputs_.begin();
-           j != (*i)->inputs_.end(); ++j) {
-        if ((*j)->dirty()) {
-          ready = false;
-          break;
+    map<Edge*, bool>::iterator want_i = want_.find(*i);
+    if (want_i == want_.end())
+      continue;
+
+    // See if the edge is now ready.
+    if (find_if((*i)->inputs_.begin(), (*i)->inputs_.end(),
+                not1(mem_fun(&Node::ready))) == (*i)->inputs_.end()) {
+      if (want_i->second) {
+        ready_.insert(*i);
+      } else {
+        // We do not need to build this edge, but we might need to build one of
+        // its dependents.
+        EdgeFinished(*i);
+      }
+    }
+  }
+}
+
+void Plan::CleanNode(BuildLog* build_log, Node* node) {
+  node->dirty_ = false;
+
+  for (vector<Edge*>::iterator ei = node->out_edges_.begin();
+       ei != node->out_edges_.end(); ++ei) {
+    // Don't process edges that we don't actually want.
+    map<Edge*, bool>::iterator want_i = want_.find(*ei);
+    if (want_i == want_.end() || !want_i->second)
+      continue;
+
+    // If all non-order-only inputs for this edge are now clean,
+    // we might have changed the dirty state of the outputs.
+    vector<Node*>::iterator begin = (*ei)->inputs_.begin(),
+                            end = (*ei)->inputs_.end() - (*ei)->order_only_deps_;
+    if (find_if(begin, end, mem_fun(&Node::dirty)) == end) {
+      // Recompute most_recent_input and command.
+      time_t most_recent_input = 1;
+      for (vector<Node*>::iterator ni = begin; ni != end; ++ni)
+        if ((*ni)->file_->mtime_ > most_recent_input)
+          most_recent_input = (*ni)->file_->mtime_;
+      string command = (*ei)->EvaluateCommand();
+
+      // Now, recompute the dirty state of each output.
+      bool all_outputs_clean = true;
+      for (vector<Node*>::iterator ni = (*ei)->outputs_.begin();
+           ni != (*ei)->outputs_.end(); ++ni) {
+        if (!(*ni)->dirty_)
+          continue;
+
+        // RecomputeOutputDirty will not modify dirty_ if the output is clean.
+        (*ni)->dirty_ = false;
+
+        // Since we know that all non-order-only inputs are clean, we can pass
+        // "false" as the "dirty" argument here.
+        (*ei)->RecomputeOutputDirty(build_log, most_recent_input, false,
+                                    command, *ni);
+        if ((*ni)->dirty_) {
+          all_outputs_clean = false;
+        } else {
+          CleanNode(build_log, *ni);
         }
       }
-      if (ready)
-        ready_.insert(*i);
+
+      // If we cleaned all outputs, mark the node as not wanted.
+      if (all_outputs_clean) {
+        want_i->second = false;
+        --wanted_edges_;
+        if (!(*ei)->is_phony())
+          --command_edges_;
+      }
     }
   }
 }
 
 void Plan::Dump() {
   printf("pending: %d\n", (int)want_.size());
-  for (set<Edge*>::iterator i = want_.begin(); i != want_.end(); ++i) {
-    (*i)->Dump();
+  for (map<Edge*, bool>::iterator i = want_.begin(); i != want_.end(); ++i) {
+    if (i->second)
+      printf("want ");
+    i->first->Dump();
   }
   printf("ready: %d\n", (int)ready_.size());
 }
@@ -383,12 +455,12 @@ Node* Builder::AddTarget(const string& name, string* err) {
 
 bool Builder::AddTarget(Node* node, string* err) {
   node->file_->StatIfNecessary(disk_interface_);
-  if (node->in_edge_) {
-    if (!node->in_edge_->RecomputeDirty(state_, disk_interface_, err))
+  if (Edge* in_edge = node->in_edge_) {
+    if (!in_edge->RecomputeDirty(state_, disk_interface_, err))
       return false;
+    if (in_edge->outputs_ready())
+      return true;  // Nothing to do.
   }
-  if (!node->dirty_)
-    return true;  // Nothing to do.
 
   if (!plan_.AddTarget(node, err))
     return false;
@@ -498,11 +570,45 @@ bool Builder::StartEdge(Edge* edge, string* err) {
 }
 
 void Builder::FinishEdge(Edge* edge, bool success, const string& output) {
+  time_t restat_mtime = 0;
+
   if (success) {
-    for (vector<Node*>::iterator i = edge->outputs_.begin();
-         i != edge->outputs_.end(); ++i) {
-      (*i)->dirty_ = false;
+    if (edge->rule_->restat_) {
+      bool node_cleaned = false;
+
+      for (vector<Node*>::iterator i = edge->outputs_.begin();
+           i != edge->outputs_.end(); ++i) {
+        if ((*i)->file_->exists()) {
+          time_t new_mtime = disk_interface_->Stat((*i)->file_->path_);
+          if ((*i)->file_->mtime_ == new_mtime) {
+            // The rule command did not change the output.  Propagate the clean
+            // state through the build graph.
+            plan_.CleanNode(log_, *i);
+            node_cleaned = true;
+          }
+        }
+      }
+
+      if (node_cleaned) {
+        // If any output was cleaned, find the most recent mtime of any
+        // (existing) non-order-only input.
+        for (vector<Node*>::iterator i = edge->inputs_.begin();
+             i != edge->inputs_.end() - edge->order_only_deps_; ++i) {
+          time_t input_mtime = disk_interface_->Stat((*i)->file_->path_);
+          if (input_mtime == 0) {
+            restat_mtime = 0;
+            break;
+          }
+          if (input_mtime > restat_mtime)
+            restat_mtime = input_mtime;
+        }
+
+        // The total number of edges in the plan may have changed as a result
+        // of a restat.
+        status_->PlanHasTotalEdges(plan_.command_edge_count());
+      }
     }
+
     plan_.EdgeFinished(edge);
   }
 
@@ -512,5 +618,5 @@ void Builder::FinishEdge(Edge* edge, bool success, const string& output) {
   int start_time, end_time;
   status_->BuildEdgeFinished(edge, success, output, &start_time, &end_time);
   if (success && log_)
-    log_->RecordCommand(edge, start_time, end_time);
+    log_->RecordCommand(edge, start_time, end_time, restat_mtime);
 }
diff --git a/src/build.h b/src/build.h
index 0f7303e..586d1ff 100644
--- a/src/build.h
+++ b/src/build.h
@@ -15,12 +15,14 @@
 #ifndef NINJA_BUILD_H_
 #define NINJA_BUILD_H_
 
+#include <map>
 #include <set>
 #include <string>
 #include <queue>
 #include <vector>
 using namespace std;
 
+struct BuildLog;
 struct Edge;
 struct DiskInterface;
 struct Node;
@@ -41,7 +43,7 @@ struct Plan {
   Edge* FindWork();
 
   /// Returns true if there's more work to be done.
-  bool more_to_do() const { return !want_.empty(); }
+  bool more_to_do() const { return wanted_edges_; }
 
   /// Dumps the current state of the plan.
   void Dump();
@@ -50,6 +52,9 @@ struct Plan {
   /// tests.
   void EdgeFinished(Edge* edge);
 
+  /// Clean the given node during the build.
+  void CleanNode(BuildLog* build_log, Node* node);
+
   /// Number of edges with commands to run.
   int command_edge_count() const { return command_edges_; }
 
@@ -58,11 +63,20 @@ private:
   bool CheckDependencyCycle(Node* node, vector<Node*>* stack, string* err);
   void NodeFinished(Node* node);
 
-  set<Edge*> want_;
+  /// Keep track of which edges we want to build in this plan.  If this map does
+  /// not contain an entry for an edge, we do not want to build the entry or its
+  /// dependents.  If an entry maps to false, we do not want to build it, but we
+  /// might want to build one of its dependents.  If the entry maps to true, we
+  /// want to build it.
+  map<Edge*, bool> want_;
+
   set<Edge*> ready_;
 
   /// Total number of edges that have commands (not phony).
   int command_edges_;
+
+  /// Total remaining number of wanted edges.
+  int wanted_edges_;
 };
 
 /// CommandRunner is an interface that wraps running the build
diff --git a/src/build_log.cc b/src/build_log.cc
index 43d5f01..7fd9ca1 100644
--- a/src/build_log.cc
+++ b/src/build_log.cc
@@ -32,8 +32,8 @@
 
 namespace {
 
-const char kFileSignature[] = "# ninja log v2\n";
-const int kCurrentVersion = 2;
+const char kFileSignature[] = "# ninja log v%d\n";
+const int kCurrentVersion = 3;
 
 }
 
@@ -59,7 +59,7 @@ bool BuildLog::OpenForWrite(const string& path, string* err) {
   SetCloseOnExec(fileno(log_file_));
 
   if (ftell(log_file_) == 0) {
-    if (fwrite(kFileSignature, sizeof(kFileSignature) - 1, 1, log_file_) < 1) {
+    if (fprintf(log_file_, kFileSignature, kCurrentVersion) < 0) {
       *err = strerror(errno);
       return false;
     }
@@ -68,10 +68,8 @@ bool BuildLog::OpenForWrite(const string& path, string* err) {
   return true;
 }
 
-void BuildLog::RecordCommand(Edge* edge, int start_time, int end_time) {
-  if (!log_file_)
-    return;
-
+void BuildLog::RecordCommand(Edge* edge, int start_time, int end_time,
+                             time_t restat_mtime) {
   const string command = edge->EvaluateCommand();
   for (vector<Node*>::iterator out = edge->outputs_.begin();
        out != edge->outputs_.end(); ++out) {
@@ -88,8 +86,10 @@ void BuildLog::RecordCommand(Edge* edge, int start_time, int end_time) {
     log_entry->command = command;
     log_entry->start_time = start_time;
     log_entry->end_time = end_time;
+    log_entry->restat_mtime = restat_mtime;
 
-    WriteEntry(log_file_, *log_entry);
+    if (log_file_)
+      WriteEntry(log_file_, *log_entry);
   }
 }
 
@@ -116,10 +116,8 @@ bool BuildLog::Load(const string& path, string* err) {
   while (fgets(buf, sizeof(buf), file)) {
     if (!log_version) {
       log_version = 1;  // Assume by default.
-      if (strcmp(buf, kFileSignature) == 0) {
-        log_version = 2;
+      if (sscanf(buf, kFileSignature, &log_version) > 0)
         continue;
-      }
     }
     char* start = buf;
     char* end = strchr(start, ' ');
@@ -128,6 +126,8 @@ bool BuildLog::Load(const string& path, string* err) {
     *end = 0;
 
     int start_time = 0, end_time = 0;
+    time_t restat_mtime = 0;
+
     if (log_version == 1) {
       // In v1 we logged how long the command took; we don't use this info.
       // int time_ms = atoi(start);
@@ -144,6 +144,16 @@ bool BuildLog::Load(const string& path, string* err) {
       end_time = atoi(start);
       start = end + 1;
     }
+    
+    if (log_version >= 3) {
+      // In v3 we log the restat mtime.
+      char* end = strchr(start, ' ');
+      if (!end)
+        continue;
+      *end = 0;
+      restat_mtime = atol(start);
+      start = end + 1;
+    }
 
     end = strchr(start, ' ');
     if (!end)
@@ -169,6 +179,7 @@ bool BuildLog::Load(const string& path, string* err) {
 
     entry->start_time = start_time;
     entry->end_time = end_time;
+    entry->restat_mtime = restat_mtime;
     entry->command = string(start, end - start);
   }
 
@@ -197,8 +208,8 @@ BuildLog::LogEntry* BuildLog::LookupByOutput(const string& path) {
 }
 
 void BuildLog::WriteEntry(FILE* f, const LogEntry& entry) {
-  fprintf(f, "%d %d %s %s\n",
-          entry.start_time, entry.end_time,
+  fprintf(f, "%d %d %ld %s %s\n",
+          entry.start_time, entry.end_time, (long) entry.restat_mtime,
           entry.output.c_str(), entry.command.c_str());
 }
 
@@ -212,7 +223,7 @@ bool BuildLog::Recompact(const string& path, string* err) {
     return false;
   }
 
-  if (fwrite(kFileSignature, sizeof(kFileSignature) - 1, 1, f) < 1) {
+  if (fprintf(f, kFileSignature, kCurrentVersion) < 0) {
     *err = strerror(errno);
     return false;
   }
diff --git a/src/build_log.h b/src/build_log.h
index 4a11c1a..99ae5a0 100644
--- a/src/build_log.h
+++ b/src/build_log.h
@@ -38,7 +38,8 @@ struct BuildLog {
 
   void SetConfig(BuildConfig* config) { config_ = config; }
   bool OpenForWrite(const string& path, string* err);
-  void RecordCommand(Edge* edge, int start_time, int end_time);
+  void RecordCommand(Edge* edge, int start_time, int end_time,
+                     time_t restat_mtime = 0);
   void Close();
 
   /// Load the on-disk log.
@@ -49,11 +50,13 @@ struct BuildLog {
     string command;
     int start_time;
     int end_time;
+    time_t restat_mtime;
 
     // Used by tests.
     bool operator==(const LogEntry& o) {
       return output == o.output && command == o.command &&
-          start_time == o.start_time && end_time == o.end_time;
+          start_time == o.start_time && end_time == o.end_time &&
+          restat_mtime == o.restat_mtime;
     }
   };
 
diff --git a/src/build_log_test.cc b/src/build_log_test.cc
index fdd2378..cf31c1d 100644
--- a/src/build_log_test.cc
+++ b/src/build_log_test.cc
@@ -115,3 +115,22 @@ TEST_F(BuildLogTest, Truncate) {
     ASSERT_EQ("", err);
   }
 }
+
+TEST_F(BuildLogTest, UpgradeV2) {
+  FILE* f = fopen(kTestFilename, "wb");
+  fprintf(f, "# ninja log v2\n");
+  fprintf(f, "123 456 out command\n");
+  fclose(f);
+
+  string err;
+  BuildLog log;
+  EXPECT_TRUE(log.Load(kTestFilename, &err));
+  ASSERT_EQ("", err);
+
+  BuildLog::LogEntry* e = log.LookupByOutput("out");
+  ASSERT_TRUE(e);
+  ASSERT_EQ(123, e->start_time);
+  ASSERT_EQ(456, e->end_time);
+  ASSERT_EQ(0, e->restat_mtime);
+  ASSERT_EQ("command", e->command);
+}
diff --git a/src/build_test.cc b/src/build_test.cc
index 84359a3..9cfa6e1 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -14,6 +14,7 @@
 
 #include "build.h"
 
+#include "build_log.h"
 #include "graph.h"
 #include "test.h"
 
@@ -42,7 +43,6 @@ TEST_F(PlanTest, Basic) {
 
   ASSERT_FALSE(plan_.FindWork());
 
-  GetNode("mid")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
@@ -50,7 +50,6 @@ TEST_F(PlanTest, Basic) {
   ASSERT_EQ("mid", edge->inputs_[0]->file_->path_);
   ASSERT_EQ("out", edge->outputs_[0]->file_->path_);
 
-  GetNode("out")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   ASSERT_FALSE(plan_.more_to_do());
@@ -75,13 +74,10 @@ TEST_F(PlanTest, DoubleOutputDirect) {
   Edge* edge;
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat in
-  GetNode("mid1")->dirty_ = false;
-  GetNode("mid2")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat mid1 mid2
-  GetNode("in")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
@@ -108,23 +104,18 @@ TEST_F(PlanTest, DoubleOutputIndirect) {
   Edge* edge;
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat in
-  GetNode("a1")->dirty_ = false;
-  GetNode("a2")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat a1
-  GetNode("b1")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat a2
-  GetNode("b2")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat b1 b2
-  GetNode("out")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
@@ -151,22 +142,18 @@ TEST_F(PlanTest, DoubleDependent) {
   Edge* edge;
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat in
-  GetNode("mid")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat mid
-  GetNode("a1")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat mid
-  GetNode("a2")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat a1 a2
-  GetNode("out")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
@@ -252,7 +239,8 @@ bool BuildTest::StartCommand(Edge* edge) {
          out != edge->outputs_.end(); ++out) {
       fs_.Create((*out)->file_->path_, now_, "");
     }
-  } else if (edge->rule_->name_ == "fail") {
+  } else if (edge->rule_->name_ == "true" ||
+             edge->rule_->name_ == "fail") {
     // Don't do anything.
   } else {
     printf("unknown command\n");
@@ -324,10 +312,12 @@ TEST_F(BuildTest, TwoStep) {
 
   EXPECT_EQ("cat cat1 cat2 > cat12", commands_ran_[2]);
 
+  now_++;
+
   // Modifying in2 requires rebuilding one intermediate file
   // and the final file.
-  GetNode("cat2")->dirty_ = true;
-  GetNode("cat12")->dirty_ = true;
+  fs_.Create("in2", now_, "");
+  state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("cat12", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
@@ -372,7 +362,7 @@ TEST_F(BuildTest, Chain) {
 
   err.clear();
   commands_ran_.clear();
-  state_.stat_cache_.Invalidate();
+  state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("c5", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.AlreadyUpToDate());
@@ -382,7 +372,7 @@ TEST_F(BuildTest, Chain) {
   fs_.Create("c3", now_, "");
   err.clear();
   commands_ran_.clear();
-  state_.stat_cache_.Invalidate();
+  state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("c5", &err));
   ASSERT_EQ("", err);
   EXPECT_FALSE(builder_.AlreadyUpToDate());
@@ -518,7 +508,7 @@ TEST_F(BuildTest, OrderOnlyDeps) {
   fs_.Create("blah.h", now_, "");
   fs_.Create("bar.h", now_, "");
   commands_ran_.clear();
-  state_.stat_cache_.Invalidate();
+  state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
@@ -529,7 +519,7 @@ TEST_F(BuildTest, OrderOnlyDeps) {
   // order only dep dirty, no rebuild.
   fs_.Create("otherfile", now_, "");
   commands_ran_.clear();
-  state_.stat_cache_.Invalidate();
+  state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_EQ("", err);
   EXPECT_TRUE(builder_.AlreadyUpToDate());
@@ -537,11 +527,58 @@ TEST_F(BuildTest, OrderOnlyDeps) {
   // implicit dep missing, expect rebuild.
   fs_.RemoveFile("bar.h");
   commands_ran_.clear();
-  state_.stat_cache_.Invalidate();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
+  EXPECT_TRUE(builder_.Build(&err));
+  ASSERT_EQ("", err);
+  ASSERT_EQ(1u, commands_ran_.size());
+}
+
+TEST_F(BuildTest, RebuildOrderOnlyDeps) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule cc\n  command = cc $in\n"
+"rule true\n  command = true\n"
+"build oo.h: cc oo.h.in\n"
+"build foo.o: cc foo.c || oo.h\n"));
+
+  fs_.Create("foo.c", now_, "");
+  fs_.Create("oo.h.in", now_, "");
+
+  // foo.o and order-only dep dirty, build both.
+  EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
+  EXPECT_TRUE(builder_.Build(&err));
+  ASSERT_EQ("", err);
+  ASSERT_EQ(2u, commands_ran_.size());
+
+  // all clean, no rebuild.
+  commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
+  EXPECT_EQ("", err);
+  EXPECT_TRUE(builder_.AlreadyUpToDate());
+
+  // order-only dep missing, build it only.
+  fs_.RemoveFile("oo.h");
+  commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
+  EXPECT_TRUE(builder_.Build(&err));
+  ASSERT_EQ("", err);
+  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ("cc oo.h.in", commands_ran_[0]);
+
+  now_++;
+
+  // order-only dep dirty, build it only.
+  fs_.Create("oo.h.in", now_, "");
+  commands_ran_.clear();
+  state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
   ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ("cc oo.h.in", commands_ran_[0]);
 }
 
 TEST_F(BuildTest, Phony) {
@@ -630,3 +667,61 @@ TEST_F(BuildTest, SwallowFailuresLimit) {
   ASSERT_EQ(3u, commands_ran_.size());
   ASSERT_EQ("cannot make progress due to previous errors", err);
 }
+
+struct BuildWithLogTest : public BuildTest {
+  BuildWithLogTest() {
+    state_.build_log_ = builder_.log_ = &build_log_;
+  }
+
+  BuildLog build_log_;
+};
+
+TEST_F(BuildWithLogTest, RestatTest) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule true\n"
+"  command = true\n"
+"  restat = 1\n"
+"rule cc\n"
+"  command = cc\n"
+"  restat = 1\n"
+"build out1: cc in\n"
+"build out2: true out1\n"
+"build out3: cat out2\n"));
+
+  fs_.Create("out1", now_, "");
+  fs_.Create("out2", now_, "");
+  fs_.Create("out3", now_, "");
+
+  now_++;
+
+  fs_.Create("in", now_, "");
+
+  // "cc" touches out1, so we should build out2.  But because "true" does not
+  // touch out2, we should cancel the build of out3.
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out3", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  ASSERT_EQ(2u, commands_ran_.size());
+
+  // If we run again, it should be a no-op, because the build log has recorded
+  // that we've already built out2 with an input timestamp of 2 (from out1).
+  commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out3", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.AlreadyUpToDate());
+
+  now_++;
+
+  fs_.Create("in", now_, "");
+
+  // The build log entry should not, however, prevent us from rebuilding out2
+  // if out1 changes.
+  commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out3", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  ASSERT_EQ(2u, commands_ran_.size());
+}
diff --git a/src/graph.cc b/src/graph.cc
index e1441ea..d13b10c 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -37,6 +37,8 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface,
       return false;
   }
 
+  outputs_ready_ = true;
+
   time_t most_recent_input = 1;
   for (vector<Node*>::iterator i = inputs_.begin(); i != inputs_.end(); ++i) {
     if ((*i)->file_->StatIfNecessary(disk_interface)) {
@@ -49,23 +51,24 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface,
       }
     }
 
-    if (is_order_only(i - inputs_.begin())) {
-      // Order-only deps only make us dirty if they're missing.
-      if (!(*i)->file_->exists())
-        dirty = true;
-      continue;
-    }
-
-    // If a regular input is dirty (or missing), we're dirty.
-    // Otherwise consider mtime.
-    if ((*i)->dirty_) {
-      dirty = true;
-    } else {
-      if ((*i)->file_->mtime_ > most_recent_input)
-        most_recent_input = (*i)->file_->mtime_;
+    // If an input is not ready, neither are our outputs.
+    if (Edge* edge = (*i)->in_edge_)
+      if (!edge->outputs_ready_)
+        outputs_ready_ = false;
+
+    if (!is_order_only(i - inputs_.begin())) {
+       // If a regular input is dirty (or missing), we're dirty.
+       // Otherwise consider mtime.
+       if ((*i)->dirty_) {
+         dirty = true;
+       } else {
+         if ((*i)->file_->mtime_ > most_recent_input)
+           most_recent_input = (*i)->file_->mtime_;
+       }
     }
   }
 
+  BuildLog* build_log = state ? state->build_log_ : 0;
   string command = EvaluateCommand();
 
   assert(!outputs_.empty());
@@ -75,35 +78,57 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface,
     // visited their dependents.
     (*i)->file_->StatIfNecessary(disk_interface);
 
-    if (is_phony()) {
-      // Phony edges don't write any output.
-      // They're only dirty if an input is dirty, or if there are no inputs
-      // and we're missing the output.
-      if (dirty)
-        (*i)->dirty_ = true;
-      else if (inputs_.empty() && !(*i)->file_->exists())
-        (*i)->dirty_ = true;
-      continue;
-    }
+    RecomputeOutputDirty(build_log, most_recent_input, dirty, command, *i);
+    if ((*i)->dirty_)
+      outputs_ready_ = false;
+  }
+
+  return true;
+}
 
-    // Output is dirty if we're dirty, we're missing the output,
-    // or if it's older than the most recent input mtime.
-    if (dirty || !(*i)->file_->exists() ||
-        (*i)->file_->mtime_ < most_recent_input) {
-      (*i)->dirty_ = true;
+void Edge::RecomputeOutputDirty(BuildLog* build_log, time_t most_recent_input,
+                                bool dirty, const string& command,
+                                Node* output) {
+  if (is_phony()) {
+    // Phony edges don't write any output.
+    // They're only dirty if an input is dirty, or if there are no inputs
+    // and we're missing the output.
+    if (dirty)
+      output->dirty_ = true;
+    else if (inputs_.empty() && !output->file_->exists())
+      output->dirty_ = true;
+    return;
+  }
+
+  BuildLog::LogEntry* entry = 0;
+  // Output is dirty if we're dirty, we're missing the output,
+  // or if it's older than the most recent input mtime.
+  if (dirty || !output->file_->exists()) {
+    output->dirty_ = true;
+  } else if (output->file_->mtime_ < most_recent_input) {
+    // 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.
+    if (rule_->restat_ && build_log &&
+        (entry = build_log->LookupByOutput(output->file_->path_))) {
+      if (entry->restat_mtime < most_recent_input)
+        output->dirty_ = true;
     } else {
-      // 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.
-      BuildLog::LogEntry* entry;
-      if (!rule_->generator_ && state->build_log_ &&
-          (entry = state->build_log_->LookupByOutput((*i)->file_->path_))) {
-        if (command != entry->command)
-          (*i)->dirty_ = true;
-      }
+      output->dirty_ = true;
+    }
+  }
+
+  if (!output->dirty_) {
+    // 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 (!rule_->generator_ && build_log &&
+        (entry || (entry = build_log->LookupByOutput(output->file_->path_)))) {
+      if (command != entry->command)
+        output->dirty_ = true;
     }
   }
-  return true;
 }
 
 /// An Env for an Edge, providing $in and $out.
@@ -194,6 +219,14 @@ bool Edge::LoadDepFile(State* state, DiskInterface* disk_interface,
       Edge* phony_edge = state->AddEdge(&State::kPhonyRule);
       node->in_edge_ = phony_edge;
       phony_edge->outputs_.push_back(node);
+
+      // RecomputeDirty might not be called for phony_edge if a previous call
+      // to RecomputeDirty had caused the file to be stat'ed.  Because previous
+      // invocations of RecomputeDirty would have seen this node without an
+      // input edge (and therefore ready), we have to set outputs_ready_ to true
+      // to avoid a potential stuck build.  If we do call RecomputeDirty for
+      // this node, it will simply set outputs_ready_ to the correct value.
+      phony_edge->outputs_ready_ = true;
     }
   }
 
diff --git a/src/graph.h b/src/graph.h
index 5b6bdf2..64496d5 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -57,24 +57,9 @@ struct FileStat {
   Node* node_;
 };
 
-struct Edge;
-
-/// Information about a node in the dependency graph: the file, whether
-/// it's dirty, etc.
-struct Node {
-  Node(FileStat* file) : file_(file), dirty_(false), in_edge_(NULL) {}
-
-  bool dirty() const { return dirty_; }
-
-  FileStat* file_;
-  bool dirty_;
-  Edge* in_edge_;
-  vector<Edge*> out_edges_;
-};
-
 /// An invokable build command and associated metadata (description, etc.).
 struct Rule {
-  Rule(const string& name) : name_(name), generator_(false) { }
+  Rule(const string& name) : name_(name), generator_(false), restat_(false) { }
 
   bool ParseCommand(const string& command, string* err) {
     return command_.Parse(command, err);
@@ -83,16 +68,21 @@ struct Rule {
   EvalString command_;
   EvalString description_;
   EvalString depfile_;
-  bool generator_;
+  bool generator_, restat_;
 };
 
+struct BuildLog;
+struct Node;
 struct State;
 
 /// An edge in the dependency graph; links between Nodes using Rules.
 struct Edge {
-  Edge() : rule_(NULL), env_(NULL), implicit_deps_(0), order_only_deps_(0) {}
+  Edge() : rule_(NULL), env_(NULL), outputs_ready_(false), implicit_deps_(0),
+           order_only_deps_(0) {}
 
   bool RecomputeDirty(State* state, DiskInterface* disk_interface, string* err);
+  void RecomputeOutputDirty(BuildLog* build_log, time_t most_recent_input,
+                            bool dirty, const string& command, Node* output);
   string EvaluateCommand();  // XXX move to env, take env ptr
   string GetDescription();
   bool LoadDepFile(State* state, DiskInterface* disk_interface, string* err);
@@ -103,6 +93,9 @@ struct Edge {
   vector<Node*> inputs_;
   vector<Node*> outputs_;
   Env* env_;
+  bool outputs_ready_;
+
+  bool outputs_ready() const { return outputs_ready_; }
 
   // XXX There are three types of inputs.
   // 1) explicit deps, which show up as $in on the command line;
@@ -128,4 +121,18 @@ struct Edge {
   bool is_phony() const;
 };
 
+/// Information about a node in the dependency graph: the file, whether
+/// it's dirty, etc.
+struct Node {
+  Node(FileStat* file) : file_(file), dirty_(false), in_edge_(NULL) {}
+
+  bool dirty() const { return dirty_; }
+  bool ready() const { return !in_edge_ || in_edge_->outputs_ready(); }
+
+  FileStat* file_;
+  bool dirty_;
+  Edge* in_edge_;
+  vector<Edge*> out_edges_;
+};
+
 #endif  // NINJA_GRAPH_H_
diff --git a/src/parsers.cc b/src/parsers.cc
index c086109..4920496 100644
--- a/src/parsers.cc
+++ b/src/parsers.cc
@@ -389,6 +389,12 @@ bool ManifestParser::ParseRule(string* err) {
         if (!tokenizer_.ReadToNewline(&dummy, err))
           return false;
         continue;
+      } else if (key == "restat") {
+        rule->restat_ = true;
+        string dummy;
+        if (!tokenizer_.ReadToNewline(&dummy, err))
+          return false;
+        continue;
       } else {
         // Die on other keyvals for now; revisit if we want to add a
         // scope here.
diff --git a/src/stat_cache.cc b/src/stat_cache.cc
index 0b717b4..3309837 100644
--- a/src/stat_cache.cc
+++ b/src/stat_cache.cc
@@ -38,6 +38,8 @@ void StatCache::Dump() {
 }
 
 void StatCache::Invalidate() {
-  for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i)
+  for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
     i->second->mtime_ = -1;
+    i->second->node_->dirty_ = false;
+  }
 }
diff --git a/src/state.cc b/src/state.cc
index e1fe675..87d824b 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -106,3 +106,9 @@ vector<Node*> State::RootNodes(string* err) {
 vector<Node*> State::DefaultNodes(string* err) {
   return defaults_.empty() ? RootNodes(err) : defaults_;
 }
+
+void State::Reset() {
+  stat_cache_.Invalidate();
+  for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e)
+    (*e)->outputs_ready_ = false;
+}
diff --git a/src/state.h b/src/state.h
index ceb7c05..7f30563 100644
--- a/src/state.h
+++ b/src/state.h
@@ -44,6 +44,7 @@ struct State {
   void AddIn(Edge* edge, const string& path);
   void AddOut(Edge* edge, const string& path);
   bool AddDefault(const string& path, string* error);
+  void Reset();
 
   /// @return the root node(s) of the graph. (Root nodes have no output edges).
   /// @param error where to write the error message if somethings went wrong.