Split Node::dirty_ into two flags: Node::dirty_ and Edge::outputs_ready_

dirty_ is intended to remain static during the build (unless a restat
occurs), while outputs_ready_ reflects the dynamic state of the build.

8 files changed, 160 insertions, 106 deletions

diff --git a/src/build.cc b/src/build.cc
index e72d9d7..c9ffe7e 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,30 @@ 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;
-        }
-      }
-      if (ready)
+    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::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 +401,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,13 +516,8 @@ bool Builder::StartEdge(Edge* edge, string* err) {
 }
 
 void Builder::FinishEdge(Edge* edge, bool success, const string& output) {
-  if (success) {
-    for (vector<Node*>::iterator i = edge->outputs_.begin();
-         i != edge->outputs_.end(); ++i) {
-      (*i)->dirty_ = false;
-    }
+  if (success)
     plan_.EdgeFinished(edge);
-  }
 
   if (edge->is_phony())
     return;
diff --git a/src/build.h b/src/build.h
index 0f7303e..fa0abd2 100644
--- a/src/build.h
+++ b/src/build.h
@@ -15,6 +15,7 @@
 #ifndef NINJA_BUILD_H_
 #define NINJA_BUILD_H_
 
+#include <map>
 #include <set>
 #include <string>
 #include <queue>
@@ -41,7 +42,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();
@@ -58,11 +59,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_test.cc b/src/build_test.cc
index 84359a3..a4bf256 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -42,7 +42,6 @@ TEST_F(PlanTest, Basic) {
 
   ASSERT_FALSE(plan_.FindWork());
 
-  GetNode("mid")->dirty_ = false;
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
@@ -50,7 +49,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 +73,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 +103,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 +141,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();
@@ -324,10 +310,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 +360,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 +370,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 +506,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 +517,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,7 +525,7 @@ 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);
diff --git a/src/graph.cc b/src/graph.cc
index e1441ea..65fed2e 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)) {
@@ -51,11 +53,18 @@ 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())
+      if (!(*i)->file_->exists()) {
         dirty = true;
+        outputs_ready_ = false;
+      }
       continue;
     }
 
+    // If an input is not ready, neither are our outputs.
+    if (Edge* edge = (*i)->in_edge_)
+      if (!edge->outputs_ready_)
+        outputs_ready_ = false;
+
     // If a regular input is dirty (or missing), we're dirty.
     // Otherwise consider mtime.
     if ((*i)->dirty_) {
@@ -66,6 +75,7 @@ bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface,
     }
   }
 
+  BuildLog* build_log = state ? state->build_log_ : 0;
   string command = EvaluateCommand();
 
   assert(!outputs_.empty());
@@ -75,35 +85,44 @@ 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;
+  }
 
-    // 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;
-    } 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;
-      }
+  return 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;
+  }
+
+  // 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->file_->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_ && build_log &&
+        (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 +213,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..079db43 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -57,21 +57,6 @@ 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) { }
@@ -86,13 +71,18 @@ struct Rule {
   bool generator_;
 };
 
+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/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.