Merge pull request #1111 from bradking/detect-cycles-early

Detect build graph cycles as early as possible

8 files changed, 175 insertions, 166 deletions

diff --git a/src/build.cc b/src/build.cc
index 8f4169b..61ef0e8 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -298,26 +298,22 @@ void Plan::Reset() {
 }
 
 bool Plan::AddTarget(Node* node, string* err) {
-  vector<Node*> stack;
-  return AddSubTarget(node, &stack, err);
+  return AddSubTarget(node, NULL, err);
 }
 
-bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) {
+bool Plan::AddSubTarget(Node* node, Node* dependent, string* err) {
   Edge* edge = node->in_edge();
   if (!edge) {  // Leaf node.
     if (node->dirty()) {
       string referenced;
-      if (!stack->empty())
-        referenced = ", needed by '" + stack->back()->path() + "',";
+      if (dependent)
+        referenced = ", needed by '" + dependent->path() + "',";
       *err = "'" + node->path() + "'" + referenced + " missing "
              "and no known rule to make it";
     }
     return false;
   }
 
-  if (CheckDependencyCycle(node, *stack, err))
-    return false;
-
   if (edge->outputs_ready())
     return false;  // Don't need to do anything.
 
@@ -341,50 +337,15 @@ bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) {
   if (!want_ins.second)
     return true;  // We've already processed the inputs.
 
-  stack->push_back(node);
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
-    if (!AddSubTarget(*i, stack, err) && !err->empty())
+    if (!AddSubTarget(*i, node, err) && !err->empty())
       return false;
   }
-  assert(stack->back() == node);
-  stack->pop_back();
 
   return true;
 }
 
-bool Plan::CheckDependencyCycle(Node* node, const vector<Node*>& stack,
-                                string* err) {
-  vector<Node*>::const_iterator start = stack.begin();
-  while (start != stack.end() && (*start)->in_edge() != node->in_edge())
-    ++start;
-  if (start == stack.end())
-    return false;
-
-  // Build error string for the cycle.
-  vector<Node*> cycle(start, stack.end());
-  cycle.push_back(node);
-
-  if (cycle.front() != cycle.back()) {
-    // Consider
-    //   build a b: cat c
-    //   build c: cat a
-    // stack will contain [b, c], node will be a.  To not print b -> c -> a,
-    // shift by one to get c -> a -> c which makes the cycle clear.
-    cycle.erase(cycle.begin());
-    cycle.push_back(cycle.front());
-    assert(cycle.front() == cycle.back());
-  }
-
-  *err = "dependency cycle: ";
-  for (vector<Node*>::const_iterator i = cycle.begin(); i != cycle.end(); ++i) {
-    if (i != cycle.begin())
-      err->append(" -> ");
-    err->append((*i)->path());
-  }
-  return true;
-}
-
 Edge* Plan::FindWork() {
   if (ready_.empty())
     return NULL;
@@ -640,9 +601,10 @@ Node* Builder::AddTarget(const string& name, string* err) {
 }
 
 bool Builder::AddTarget(Node* node, string* err) {
+  if (!scan_.RecomputeDirty(node, err))
+    return false;
+
   if (Edge* in_edge = node->in_edge()) {
-    if (!scan_.RecomputeDirty(in_edge, err))
-      return false;
     if (in_edge->outputs_ready())
       return true;  // Nothing to do.
   }
diff --git a/src/build.h b/src/build.h
index f97d67e..43786f1 100644
--- a/src/build.h
+++ b/src/build.h
@@ -75,9 +75,7 @@ struct Plan {
   void Reset();
 
 private:
-  bool AddSubTarget(Node* node, vector<Node*>* stack, string* err);
-  bool CheckDependencyCycle(Node* node, const vector<Node*>& stack,
-                            string* err);
+  bool AddSubTarget(Node* node, Node* dependent, string* err);
   void NodeFinished(Node* node);
 
   /// Submits a ready edge as a candidate for execution.
diff --git a/src/build_test.cc b/src/build_test.cc
index 623ed14..a0f898f 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -185,59 +185,6 @@ TEST_F(PlanTest, DoubleDependent) {
   ASSERT_FALSE(edge);  // done
 }
 
-TEST_F(PlanTest, DependencyCycle) {
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build out: cat mid\n"
-"build mid: cat in\n"
-"build in: cat pre\n"
-"build pre: cat out\n"));
-  GetNode("out")->MarkDirty();
-  GetNode("mid")->MarkDirty();
-  GetNode("in")->MarkDirty();
-  GetNode("pre")->MarkDirty();
-
-  string err;
-  EXPECT_FALSE(plan_.AddTarget(GetNode("out"), &err));
-  ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes1) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build a b: cat a\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err));
-  ASSERT_EQ("dependency cycle: a -> a", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes2) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build b a: cat a\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err));
-  ASSERT_EQ("dependency cycle: a -> a", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes3) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build a b: cat c\n"
-"build c: cat a\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err));
-  ASSERT_EQ("dependency cycle: c -> a -> c", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes4) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build d: cat c\n"
-"build c: cat b\n"
-"build b: cat a\n"
-"build a e: cat d\n"
-"build f: cat e\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("f"), &err));
-  ASSERT_EQ("dependency cycle: d -> c -> b -> a -> d", err);
-}
-
 void PlanTest::TestPoolWithDepthOne(const char* test_case) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, test_case));
   GetNode("out1")->MarkDirty();
@@ -1747,8 +1694,8 @@ TEST_F(BuildTest, InterruptCleanup) {
 TEST_F(BuildTest, StatFailureAbortsBuild) {
   const string kTooLongToStat(400, 'i');
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-("build " + kTooLongToStat + ": cat " + kTooLongToStat + "\n").c_str()));
-  // Also cyclic, for good measure.
+("build " + kTooLongToStat + ": cat in\n").c_str()));
+  fs_.Create("in", "");
 
   // This simulates a stat failure:
   fs_.files_[kTooLongToStat].mtime = -1;
diff --git a/src/disk_interface_test.cc b/src/disk_interface_test.cc
index 7187bdf..d7fb8f8 100644
--- a/src/disk_interface_test.cc
+++ b/src/disk_interface_test.cc
@@ -245,7 +245,7 @@ TEST_F(StatTest, Simple) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out->in_edge(), NULL);
+  scan_.RecomputeDirty(out, NULL);
   ASSERT_EQ(2u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_EQ("in",  stats_[1]);
@@ -261,7 +261,7 @@ TEST_F(StatTest, TwoStep) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out->in_edge(), NULL);
+  scan_.RecomputeDirty(out, NULL);
   ASSERT_EQ(3u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_TRUE(GetNode("out")->dirty());
@@ -281,7 +281,7 @@ TEST_F(StatTest, Tree) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out->in_edge(), NULL);
+  scan_.RecomputeDirty(out, NULL);
   ASSERT_EQ(1u + 6u, stats_.size());
   ASSERT_EQ("mid1", stats_[1]);
   ASSERT_TRUE(GetNode("mid1")->dirty());
@@ -302,7 +302,7 @@ TEST_F(StatTest, Middle) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out->in_edge(), NULL);
+  scan_.RecomputeDirty(out, NULL);
   ASSERT_FALSE(GetNode("in")->dirty());
   ASSERT_TRUE(GetNode("mid")->dirty());
   ASSERT_TRUE(GetNode("out")->dirty());
diff --git a/src/graph.cc b/src/graph.cc
index c90aaad..7dd9491 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -31,20 +31,44 @@ bool Node::Stat(DiskInterface* disk_interface, string* err) {
   return (mtime_ = disk_interface->Stat(path_, err)) != -1;
 }
 
-bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
+bool DependencyScan::RecomputeDirty(Node* node, string* err) {
+  vector<Node*> stack;
+  return RecomputeDirty(node, &stack, err);
+}
+
+bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
+                                    string* err) {
+  Edge* edge = node->in_edge();
+  if (!edge) {
+    // If we already visited this leaf node then we are done.
+    if (node->status_known())
+      return true;
+    // This node has no in-edge; it is dirty if it is missing.
+    if (!node->StatIfNecessary(disk_interface_, err))
+      return false;
+    if (!node->exists())
+      EXPLAIN("%s has no in-edge and is missing", node->path().c_str());
+    node->set_dirty(!node->exists());
+    return true;
+  }
+
+  // If we already finished this edge then we are done.
+  if (edge->mark_ == Edge::VisitDone)
+    return true;
+
+  // If we encountered this edge earlier in the call stack we have a cycle.
+  if (!VerifyDAG(node, stack, err))
+    return false;
+
+  // Mark the edge temporarily while in the call stack.
+  edge->mark_ = Edge::VisitInStack;
+  stack->push_back(node);
+
   bool dirty = false;
   edge->outputs_ready_ = true;
   edge->deps_missing_ = false;
 
   // Load output mtimes so we can compare them to the most recent input below.
-  // RecomputeDirty() recursively walks the graph following the input nodes
-  // of |edge| and the in_edges of these nodes.  It uses the stat state of each
-  // node to mark nodes as visited and doesn't traverse across nodes that have
-  // been visited already.  To make sure that every edge is visited only once
-  // (important because an edge's deps are loaded every time it's visited), mark
-  // all outputs of |edge| visited as a first step.  This ensures that edges
-  // with multiple inputs and outputs are visited only once, even in cyclic
-  // graphs.
   for (vector<Node*>::iterator o = edge->outputs_.begin();
        o != edge->outputs_.end(); ++o) {
     if (!(*o)->StatIfNecessary(disk_interface_, err))
@@ -63,19 +87,9 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
   Node* most_recent_input = NULL;
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
-    if (!(*i)->status_known()) {
-      if (!(*i)->StatIfNecessary(disk_interface_, err))
-        return false;
-      if (Edge* in_edge = (*i)->in_edge()) {
-        if (!RecomputeDirty(in_edge, err))
-          return false;
-      } else {
-        // This input has no in-edge; it is dirty if it is missing.
-        if (!(*i)->exists())
-          EXPLAIN("%s has no in-edge and is missing", (*i)->path().c_str());
-        (*i)->set_dirty(!(*i)->exists());
-      }
-    }
+    // Visit this input.
+    if (!RecomputeDirty(*i, stack, err))
+      return false;
 
     // If an input is not ready, neither are our outputs.
     if (Edge* in_edge = (*i)->in_edge()) {
@@ -118,9 +132,47 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
   if (dirty && !(edge->is_phony() && edge->inputs_.empty()))
     edge->outputs_ready_ = false;
 
+  // Mark the edge as finished during this walk now that it will no longer
+  // be in the call stack.
+  edge->mark_ = Edge::VisitDone;
+  assert(stack->back() == node);
+  stack->pop_back();
+
   return true;
 }
 
+bool DependencyScan::VerifyDAG(Node* node, vector<Node*>* stack, string* err) {
+  Edge* edge = node->in_edge();
+  assert(edge != NULL);
+
+  // If we have no temporary mark on the edge then we do not yet have a cycle.
+  if (edge->mark_ != Edge::VisitInStack)
+    return true;
+
+  // We have this edge earlier in the call stack.  Find it.
+  vector<Node*>::iterator start = stack->begin();
+  while (start != stack->end() && (*start)->in_edge() != edge)
+    ++start;
+  assert(start != stack->end());
+
+  // Make the cycle clear by reporting its start as the node at its end
+  // instead of some other output of the starting edge.  For example,
+  // running 'ninja b' on
+  //   build a b: cat c
+  //   build c: cat a
+  // should report a -> c -> a instead of b -> c -> a.
+  *start = node;
+
+  // Construct the error message rejecting the cycle.
+  *err = "dependency cycle: ";
+  for (vector<Node*>::const_iterator i = start; i != stack->end(); ++i) {
+    err->append((*i)->path());
+    err->append(" -> ");
+  }
+  err->append((*start)->path());
+  return false;
+}
+
 bool DependencyScan::RecomputeOutputsDirty(Edge* edge, Node* most_recent_input,
                                            bool* outputs_dirty, string* err) {
   string command = edge->EvaluateCommand(/*incl_rsp_file=*/true);
diff --git a/src/graph.h b/src/graph.h
index ec24293..586c588 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_;
 
@@ -246,11 +253,12 @@ struct DependencyScan {
         disk_interface_(disk_interface),
         dep_loader_(state, deps_log, disk_interface) {}
 
+  /// Update the |dirty_| state of the given node by inspecting its input edge.
   /// Examine inputs, outputs, and command lines to judge whether an edge
   /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
   /// state accordingly.
   /// Returns false on failure.
-  bool RecomputeDirty(Edge* edge, string* err);
+  bool RecomputeDirty(Node* node, string* err);
 
   /// Recompute whether any output of the edge is dirty, if so sets |*dirty|.
   /// Returns false on failure.
@@ -269,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,
diff --git a/src/graph_test.cc b/src/graph_test.cc
index be08b19..d4d2824 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -30,9 +30,8 @@ TEST_F(GraphTest, MissingImplicit) {
   fs_.Create("in", "");
   fs_.Create("out", "");
 
-  Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
   ASSERT_EQ("", err);
 
   // A missing implicit dep *should* make the output dirty.
@@ -49,9 +48,8 @@ TEST_F(GraphTest, ModifiedImplicit) {
   fs_.Tick();
   fs_.Create("implicit", "");
 
-  Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
   ASSERT_EQ("", err);
 
   // A modified implicit dep should make the output dirty.
@@ -70,9 +68,8 @@ TEST_F(GraphTest, FunkyMakefilePath) {
   fs_.Tick();
   fs_.Create("implicit.h", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
 
   // implicit.h has changed, though our depfile refers to it with a
@@ -94,9 +91,8 @@ TEST_F(GraphTest, ExplicitImplicit) {
   fs_.Tick();
   fs_.Create("data", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
 
   // We have both an implicit and an explicit dep on implicit.h.
@@ -123,9 +119,8 @@ TEST_F(GraphTest, ImplicitOutputMissing) {
   fs_.Create("in", "");
   fs_.Create("out", "");
 
-  Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -140,9 +135,8 @@ TEST_F(GraphTest, ImplicitOutputOutOfDate) {
   fs_.Create("in", "");
   fs_.Create("out", "");
 
-  Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -165,9 +159,8 @@ TEST_F(GraphTest, ImplicitOutputOnlyMissing) {
 "build | out.imp: cat in\n"));
   fs_.Create("in", "");
 
-  Edge* edge = GetNode("out.imp")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -180,9 +173,8 @@ TEST_F(GraphTest, ImplicitOutputOnlyOutOfDate) {
   fs_.Tick();
   fs_.Create("in", "");
 
-  Edge* edge = GetNode("out.imp")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -198,9 +190,8 @@ TEST_F(GraphTest, PathWithCurrentDirectory) {
   fs_.Create("out.o.d", "out.o: foo.cc\n");
   fs_.Create("out.o", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -247,9 +238,8 @@ TEST_F(GraphTest, DepfileWithCanonicalizablePath) {
   fs_.Create("out.o.d", "out.o: bar/../foo.cc\n");
   fs_.Create("out.o", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -268,15 +258,14 @@ TEST_F(GraphTest, DepfileRemoved) {
   fs_.Create("out.o.d", "out.o: foo.h\n");
   fs_.Create("out.o", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
   EXPECT_FALSE(GetNode("out.o")->dirty());
 
   state_.Reset();
   fs_.RemoveFile("out.o.d");
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(GetNode("out.o")->dirty());
 }
@@ -323,8 +312,7 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) {
 "build n2: phony n1\n"
   );
   string err;
-  Edge* edge = GetNode("n2")->in_edge();
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), &err));
   ASSERT_EQ("", err);
 
   Plan plan_;
@@ -335,6 +323,55 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) {
   ASSERT_FALSE(plan_.more_to_do());
 }
 
+TEST_F(GraphTest, DependencyCycle) {
+  AssertParse(&state_,
+"build out: cat mid\n"
+"build mid: cat in\n"
+"build in: cat pre\n"
+"build pre: cat out\n");
+
+  string err;
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes1) {
+  string err;
+  AssertParse(&state_,
+"build a b: cat a\n");
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  ASSERT_EQ("dependency cycle: a -> a", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes2) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build b a: cat a\n"));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  ASSERT_EQ("dependency cycle: a -> a", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes3) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build a b: cat c\n"
+"build c: cat a\n"));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  ASSERT_EQ("dependency cycle: a -> c -> a", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes4) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build d: cat c\n"
+"build c: cat b\n"
+"build b: cat a\n"
+"build a e: cat d\n"
+"build f: cat e\n"));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), &err));
+  ASSERT_EQ("dependency cycle: a -> d -> c -> b -> a", err);
+}
+
 // Verify that cycles in graphs with multiple outputs are handled correctly
 // in RecomputeDirty() and don't cause deps to be loaded multiple times.
 TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) {
@@ -347,13 +384,13 @@ TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) {
   fs_.Create("dep.d", "a: b\n");
 
   string err;
-  Edge* edge = GetNode("a")->in_edge();
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
-  ASSERT_EQ("", err);
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  ASSERT_EQ("dependency cycle: b -> b", err);
 
   // Despite the depfile causing edge to be a cycle (it has outputs a and b,
   // but the depfile also adds b as an input), the deps should have been loaded
   // only once:
+  Edge* edge = GetNode("a")->in_edge();
   EXPECT_EQ(1, edge->inputs_.size());
   EXPECT_EQ("b", edge->inputs_[0]->path());
 }
@@ -372,13 +409,13 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfile) {
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  Edge* edge = GetNode("a")->in_edge();
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
-  ASSERT_EQ("", err);
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
   // but c's in_edge has b as input but the depfile also adds |edge| as
   // output)), the deps should have been loaded only once:
+  Edge* edge = GetNode("a")->in_edge();
   EXPECT_EQ(1, edge->inputs_.size());
   EXPECT_EQ("c", edge->inputs_[0]->path());
 }
@@ -399,8 +436,8 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) {
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d")->in_edge(), &err));
-  ASSERT_EQ("", err);
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), &err));
+  ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
   // but c's in_edge has b as input but the depfile also adds |edge| as
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() {