Teach RecomputeDirty to detect cycles in the build graph

RecomputeDirty is the earliest traversal of the build graph complete
with depfile-loaded dependencies.  Teach it to detect cycles and fail
immediately.  This avoids the need to tolerate cycles in RecomputeDirty
only to diagnose them later.  It also enables future simplification of
Plan and Builder logic because they will be able to assume DAG input.

When RecomputeDirty detects a cycle, reject it with an error message
like that previously produced by Plan::CheckDependencyCycle.

Previously we used the stat state of each node to determine whether
we reached it earlier in the walk.  Retain this approach for leaf
nodes, but add an explicit walk state mark for each Edge so that
we can have a temporary mark to aid cycle detection.

1 files changed, 3 insertions, 0 deletions

diff --git a/src/graph.h b/src/graph.h
index 1b30dee..586c588 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -277,6 +277,9 @@ struct DependencyScan {
   }
 
  private:
+  bool RecomputeDirty(Node* node, vector<Node*>* stack, string* err);
+  bool VerifyDAG(Node* node, vector<Node*>* stack, string* err);
+
   /// Recompute whether a given single output should be marked dirty.
   /// Returns true if so.
   bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input,