Add infrastructure for efficient walks through the `Edge` graph

Store a mark in each `Edge` to be updated as it is encountered by a walk.

2 files changed, 11 insertions, 2 deletions

diff --git a/src/graph.h b/src/graph.h
index 9e82ca2..1b30dee 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -128,7 +128,13 @@ private:
 
 /// An edge in the dependency graph; links between Nodes using Rules.
 struct Edge {
-  Edge() : rule_(NULL), pool_(NULL), env_(NULL),
+  enum VisitMark {
+    VisitNone,
+    VisitInStack,
+    VisitDone
+  };
+
+  Edge() : rule_(NULL), pool_(NULL), env_(NULL), mark_(VisitNone),
            outputs_ready_(false), deps_missing_(false),
            implicit_deps_(0), order_only_deps_(0), implicit_outs_(0) {}
 
@@ -156,6 +162,7 @@ struct Edge {
   vector<Node*> inputs_;
   vector<Node*> outputs_;
   BindingEnv* env_;
+  VisitMark mark_;
   bool outputs_ready_;
   bool deps_missing_;
 
diff --git a/src/state.cc b/src/state.cc
index 6079229..9b3c7e1 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -184,8 +184,10 @@ vector<Node*> State::DefaultNodes(string* err) const {
 void State::Reset() {
   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i)
     i->second->ResetState();
-  for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e)
+  for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) {
     (*e)->outputs_ready_ = false;
+    (*e)->mark_ = Edge::VisitNone;
+  }
 }
 
 void State::Dump() {