From a8b5cdc4e9034f8823ee0cfa94ea49d7795698ab Mon Sep 17 00:00:00 2001
From: Brad King <brad.king@kitware.com>
Date: Thu, 12 Nov 2015 11:24:50 -0500
Subject: 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.
---
 src/graph.h  | 9 ++++++++-
 src/state.cc | 4 +++-
 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() {
-- 
cgit v0.12