Merge pull request #1521 from bradking/dyndep

dyndep: dynamically discovered dependencies for Fortran and C++20 modules

24 files changed, 2776 insertions, 155 deletions

diff --git a/src/build.cc b/src/build.cc
index b392803..a055738 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -97,6 +97,7 @@ void BuildStatus::PlanHasTotalEdges(int total) {
 }
 
 void BuildStatus::BuildEdgeStarted(Edge* edge) {
+  assert(running_edges_.find(edge) == running_edges_.end());
   int start_time = (int)(GetTimeMillis() - start_time_millis_);
   running_edges_.insert(make_pair(edge, start_time));
   ++started_edges_;
@@ -173,6 +174,20 @@ void BuildStatus::BuildEdgeFinished(Edge* edge,
   }
 }
 
+void BuildStatus::BuildLoadDyndeps() {
+  // The DependencyScan calls EXPLAIN() to print lines explaining why
+  // it considers a portion of the graph to be out of date.  Normally
+  // this is done before the build starts, but our caller is about to
+  // load a dyndep file during the build.  Doing so may generate more
+  // exlanation lines (via fprintf directly to stderr), but in an
+  // interactive console the cursor is currently at the end of a status
+  // line.  Start a new line so that the first explanation does not
+  // append to the status line.  After the explanations are done a
+  // new build status line will appear.
+  if (g_explaining)
+    printer_.PrintOnNewLine("");
+}
+
 void BuildStatus::BuildStarted() {
   overall_rate_.Restart();
   current_rate_.Restart();
@@ -287,7 +302,11 @@ void BuildStatus::PrintStatus(Edge* edge, EdgeStatus status) {
                  force_full_command ? LinePrinter::FULL : LinePrinter::ELIDE);
 }
 
-Plan::Plan() : command_edges_(0), wanted_edges_(0) {}
+Plan::Plan(Builder* builder)
+  : builder_(builder)
+  , command_edges_(0)
+  , wanted_edges_(0)
+{}
 
 void Plan::Reset() {
   command_edges_ = 0;
@@ -297,10 +316,11 @@ void Plan::Reset() {
 }
 
 bool Plan::AddTarget(Node* node, string* err) {
-  return AddSubTarget(node, NULL, err);
+  return AddSubTarget(node, NULL, err, NULL);
 }
 
-bool Plan::AddSubTarget(Node* node, Node* dependent, string* err) {
+bool Plan::AddSubTarget(Node* node, Node* dependent, string* err,
+                        set<Edge*>* dyndep_walk) {
   Edge* edge = node->in_edge();
   if (!edge) {  // Leaf node.
     if (node->dirty()) {
@@ -322,29 +342,39 @@ bool Plan::AddSubTarget(Node* node, Node* dependent, string* err) {
     want_.insert(make_pair(edge, kWantNothing));
   Want& want = want_ins.first->second;
 
+  if (dyndep_walk && want == kWantToFinish)
+    return false;  // Don't need to do anything with already-scheduled edge.
+
   // If we do need to build edge and we haven't already marked it as wanted,
   // mark it now.
   if (node->dirty() && want == kWantNothing) {
     want = kWantToStart;
-    ++wanted_edges_;
-    if (edge->AllInputsReady())
+    EdgeWanted(edge);
+    if (!dyndep_walk && edge->AllInputsReady())
       ScheduleWork(want_ins.first);
-    if (!edge->is_phony())
-      ++command_edges_;
   }
 
+  if (dyndep_walk)
+    dyndep_walk->insert(edge);
+
   if (!want_ins.second)
     return true;  // We've already processed the inputs.
 
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
-    if (!AddSubTarget(*i, node, err) && !err->empty())
+    if (!AddSubTarget(*i, node, err, dyndep_walk) && !err->empty())
       return false;
   }
 
   return true;
 }
 
+void Plan::EdgeWanted(Edge* edge) {
+  ++wanted_edges_;
+  if (!edge->is_phony())
+    ++command_edges_;
+}
+
 Edge* Plan::FindWork() {
   if (ready_.empty())
     return NULL;
@@ -376,7 +406,7 @@ void Plan::ScheduleWork(map<Edge*, Want>::iterator want_e) {
   }
 }
 
-void Plan::EdgeFinished(Edge* edge, EdgeResult result) {
+bool Plan::EdgeFinished(Edge* edge, EdgeResult result, string* err) {
   map<Edge*, Want>::iterator e = want_.find(edge);
   assert(e != want_.end());
   bool directly_wanted = e->second != kWantNothing;
@@ -388,7 +418,7 @@ void Plan::EdgeFinished(Edge* edge, EdgeResult result) {
 
   // The rest of this function only applies to successful commands.
   if (result != kEdgeSucceeded)
-    return;
+    return true;
 
   if (directly_wanted)
     --wanted_edges_;
@@ -398,11 +428,21 @@ void Plan::EdgeFinished(Edge* edge, EdgeResult result) {
   // Check off any nodes we were waiting for with this edge.
   for (vector<Node*>::iterator o = edge->outputs_.begin();
        o != edge->outputs_.end(); ++o) {
-    NodeFinished(*o);
+    if (!NodeFinished(*o, err))
+      return false;
   }
+  return true;
 }
 
-void Plan::NodeFinished(Node* node) {
+bool Plan::NodeFinished(Node* node, string* err) {
+  // If this node provides dyndep info, load it now.
+  if (node->dyndep_pending()) {
+    assert(builder_ && "dyndep requires Plan to have a Builder");
+    // Load the now-clean dyndep file.  This will also update the
+    // build plan and schedule any new work that is ready.
+    return builder_->LoadDyndeps(node, err);
+  }
+
   // See if we we want any edges from this node.
   for (vector<Edge*>::const_iterator oe = node->out_edges().begin();
        oe != node->out_edges().end(); ++oe) {
@@ -411,16 +451,25 @@ void Plan::NodeFinished(Node* node) {
       continue;
 
     // See if the edge is now ready.
-    if ((*oe)->AllInputsReady()) {
-      if (want_e->second != kWantNothing) {
-        ScheduleWork(want_e);
-      } else {
-        // We do not need to build this edge, but we might need to build one of
-        // its dependents.
-        EdgeFinished(*oe, kEdgeSucceeded);
-      }
+    if (!EdgeMaybeReady(want_e, err))
+      return false;
+  }
+  return true;
+}
+
+bool Plan::EdgeMaybeReady(map<Edge*, Want>::iterator want_e, string* err) {
+  Edge* edge = want_e->first;
+  if (edge->AllInputsReady()) {
+    if (want_e->second != kWantNothing) {
+      ScheduleWork(want_e);
+    } else {
+      // We do not need to build this edge, but we might need to build one of
+      // its dependents.
+      if (!EdgeFinished(edge, kEdgeSucceeded, err))
+        return false;
     }
   }
+  return true;
 }
 
 bool Plan::CleanNode(DependencyScan* scan, Node* node, string* err) {
@@ -480,6 +529,128 @@ bool Plan::CleanNode(DependencyScan* scan, Node* node, string* err) {
   return true;
 }
 
+bool Plan::DyndepsLoaded(DependencyScan* scan, Node* node,
+                         const DyndepFile& ddf, string* err) {
+  // Recompute the dirty state of all our direct and indirect dependents now
+  // that our dyndep information has been loaded.
+  if (!RefreshDyndepDependents(scan, node, err))
+    return false;
+
+  // We loaded dyndep information for those out_edges of the dyndep node that
+  // specify the node in a dyndep binding, but they may not be in the plan.
+  // Starting with those already in the plan, walk newly-reachable portion
+  // of the graph through the dyndep-discovered dependencies.
+
+  // Find edges in the the build plan for which we have new dyndep info.
+  std::vector<DyndepFile::const_iterator> dyndep_roots;
+  for (DyndepFile::const_iterator oe = ddf.begin(); oe != ddf.end(); ++oe) {
+    Edge* edge = oe->first;
+
+    // If the edge outputs are ready we do not need to consider it here.
+    if (edge->outputs_ready())
+      continue;
+
+    map<Edge*, Want>::iterator want_e = want_.find(edge);
+
+    // If the edge has not been encountered before then nothing already in the
+    // plan depends on it so we do not need to consider the edge yet either.
+    if (want_e == want_.end())
+      continue;
+
+    // This edge is already in the plan so queue it for the walk.
+    dyndep_roots.push_back(oe);
+  }
+
+  // Walk dyndep-discovered portion of the graph to add it to the build plan.
+  std::set<Edge*> dyndep_walk;
+  for (std::vector<DyndepFile::const_iterator>::iterator
+       oei = dyndep_roots.begin(); oei != dyndep_roots.end(); ++oei) {
+    DyndepFile::const_iterator oe = *oei;
+    for (vector<Node*>::const_iterator i = oe->second.implicit_inputs_.begin();
+         i != oe->second.implicit_inputs_.end(); ++i) {
+      if (!AddSubTarget(*i, oe->first->outputs_[0], err, &dyndep_walk) &&
+          !err->empty())
+        return false;
+    }
+  }
+
+  // Add out edges from this node that are in the plan (just as
+  // Plan::NodeFinished would have without taking the dyndep code path).
+  for (vector<Edge*>::const_iterator oe = node->out_edges().begin();
+       oe != node->out_edges().end(); ++oe) {
+    map<Edge*, Want>::iterator want_e = want_.find(*oe);
+    if (want_e == want_.end())
+      continue;
+    dyndep_walk.insert(want_e->first);
+  }
+
+  // See if any encountered edges are now ready.
+  for (set<Edge*>::iterator wi = dyndep_walk.begin();
+       wi != dyndep_walk.end(); ++wi) {
+    map<Edge*, Want>::iterator want_e = want_.find(*wi);
+    if (want_e == want_.end())
+      continue;
+    if (!EdgeMaybeReady(want_e, err))
+      return false;
+  }
+
+  return true;
+}
+
+bool Plan::RefreshDyndepDependents(DependencyScan* scan, Node* node,
+                                   string* err) {
+  // Collect the transitive closure of dependents and mark their edges
+  // as not yet visited by RecomputeDirty.
+  set<Node*> dependents;
+  UnmarkDependents(node, &dependents);
+
+  // Update the dirty state of all dependents and check if their edges
+  // have become wanted.
+  for (set<Node*>::iterator i = dependents.begin();
+       i != dependents.end(); ++i) {
+    Node* n = *i;
+
+    // Check if this dependent node is now dirty.  Also checks for new cycles.
+    if (!scan->RecomputeDirty(n, err))
+      return false;
+    if (!n->dirty())
+      continue;
+
+    // This edge was encountered before.  However, we may not have wanted to
+    // build it if the outputs were not known to be dirty.  With dyndep
+    // information an output is now known to be dirty, so we want the edge.
+    Edge* edge = n->in_edge();
+    assert(edge && !edge->outputs_ready());
+    map<Edge*, Want>::iterator want_e = want_.find(edge);
+    assert(want_e != want_.end());
+    if (want_e->second == kWantNothing) {
+      want_e->second = kWantToStart;
+      EdgeWanted(edge);
+    }
+  }
+  return true;
+}
+
+void Plan::UnmarkDependents(Node* node, set<Node*>* dependents) {
+  for (vector<Edge*>::const_iterator oe = node->out_edges().begin();
+       oe != node->out_edges().end(); ++oe) {
+    Edge* edge = *oe;
+
+    map<Edge*, Want>::iterator want_e = want_.find(edge);
+    if (want_e == want_.end())
+      continue;
+
+    if (edge->mark_ != Edge::VisitNone) {
+      edge->mark_ = Edge::VisitNone;
+      for (vector<Node*>::iterator o = edge->outputs_.begin();
+           o != edge->outputs_.end(); ++o) {
+        if (dependents->insert(*o).second)
+          UnmarkDependents(*o, dependents);
+      }
+    }
+  }
+}
+
 void Plan::Dump() {
   printf("pending: %d\n", (int)want_.size());
   for (map<Edge*, Want>::iterator e = want_.begin(); e != want_.end(); ++e) {
@@ -556,7 +727,8 @@ bool RealCommandRunner::WaitForCommand(Result* result) {
 Builder::Builder(State* state, const BuildConfig& config,
                  BuildLog* build_log, DepsLog* deps_log,
                  DiskInterface* disk_interface)
-    : state_(state), config_(config), disk_interface_(disk_interface),
+    : state_(state), config_(config),
+      plan_(this), disk_interface_(disk_interface),
       scan_(state, build_log, deps_log, disk_interface,
             &config_.depfile_parser_options) {
   status_ = new BuildStatus(config);
@@ -660,7 +832,11 @@ bool Builder::Build(string* err) {
         }
 
         if (edge->is_phony()) {
-          plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+          if (!plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, err)) {
+            Cleanup();
+            status_->BuildFinished();
+            return false;
+          }
         } else {
           ++pending_commands;
         }
@@ -780,8 +956,7 @@ bool Builder::FinishCommand(CommandRunner::Result* result, string* err) {
 
   // The rest of this function only applies to successful commands.
   if (!result->success()) {
-    plan_.EdgeFinished(edge, Plan::kEdgeFailed);
-    return true;
+    return plan_.EdgeFinished(edge, Plan::kEdgeFailed, err);
   }
 
   // Restat the edge outputs
@@ -837,7 +1012,8 @@ bool Builder::FinishCommand(CommandRunner::Result* result, string* err) {
     }
   }
 
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  if (!plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, err))
+    return false;
 
   // Delete any left over response file.
   string rspfile = edge->GetUnescapedRspfile();
@@ -934,3 +1110,21 @@ bool Builder::ExtractDeps(CommandRunner::Result* result,
 
   return true;
 }
+
+bool Builder::LoadDyndeps(Node* node, string* err) {
+  status_->BuildLoadDyndeps();
+
+  // Load the dyndep information provided by this node.
+  DyndepFile ddf;
+  if (!scan_.LoadDyndeps(node, &ddf, err))
+    return false;
+
+  // Update the build plan to account for dyndep modifications to the graph.
+  if (!plan_.DyndepsLoaded(&scan_, node, ddf, err))
+    return false;
+
+  // New command edges may have been added to the plan.
+  status_->PlanHasTotalEdges(plan_.command_edge_count());
+
+  return true;
+}
diff --git a/src/build.h b/src/build.h
index a42b8d4..ab59f0c 100644
--- a/src/build.h
+++ b/src/build.h
@@ -32,6 +32,7 @@
 
 struct BuildLog;
 struct BuildStatus;
+struct Builder;
 struct DiskInterface;
 struct Edge;
 struct Node;
@@ -40,7 +41,7 @@ struct State;
 /// Plan stores the state of a build plan: what we intend to build,
 /// which steps we're ready to execute.
 struct Plan {
-  Plan();
+  Plan(Builder* builder = NULL);
 
   /// Add a target to our plan (including all its dependencies).
   /// Returns false if we don't need to build this target; may
@@ -63,7 +64,10 @@ struct Plan {
   };
 
   /// Mark an edge as done building (whether it succeeded or failed).
-  void EdgeFinished(Edge* edge, EdgeResult result);
+  /// If any of the edge's outputs are dyndep bindings of their dependents,
+  /// this loads dynamic dependencies from the nodes' paths.
+  /// Returns 'false' if loading dyndep info fails and 'true' otherwise.
+  bool EdgeFinished(Edge* edge, EdgeResult result, string* err);
 
   /// Clean the given node during the build.
   /// Return false on error.
@@ -75,9 +79,21 @@ struct Plan {
   /// Reset state.  Clears want and ready sets.
   void Reset();
 
+  /// Update the build plan to account for modifications made to the graph
+  /// by information loaded from a dyndep file.
+  bool DyndepsLoaded(DependencyScan* scan, Node* node,
+                     const DyndepFile& ddf, string* err);
 private:
-  bool AddSubTarget(Node* node, Node* dependent, string* err);
-  void NodeFinished(Node* node);
+  bool RefreshDyndepDependents(DependencyScan* scan, Node* node, string* err);
+  void UnmarkDependents(Node* node, set<Node*>* dependents);
+  bool AddSubTarget(Node* node, Node* dependent, string* err,
+                    set<Edge*>* dyndep_walk);
+
+  /// Update plan with knowledge that the given node is up to date.
+  /// If the node is a dyndep binding on any of its dependents, this
+  /// loads dynamic dependencies from the node's path.
+  /// Returns 'false' if loading dyndep info fails and 'true' otherwise.
+  bool NodeFinished(Node* node, string* err);
 
   /// Enumerate possible steps we want for an edge.
   enum Want
@@ -92,6 +108,9 @@ private:
     kWantToFinish
   };
 
+  void EdgeWanted(Edge* edge);
+  bool EdgeMaybeReady(map<Edge*, Want>::iterator want_e, string* err);
+
   /// Submits a ready edge as a candidate for execution.
   /// The edge may be delayed from running, for example if it's a member of a
   /// currently-full pool.
@@ -105,6 +124,8 @@ private:
 
   set<Edge*> ready_;
 
+  Builder* builder_;
+
   /// Total number of edges that have commands (not phony).
   int command_edges_;
 
@@ -189,6 +210,9 @@ struct Builder {
     scan_.set_build_log(log);
   }
 
+  /// Load the dyndep information provided by the given node.
+  bool LoadDyndeps(Node* node, string* err);
+
   State* state_;
   const BuildConfig& config_;
   Plan plan_;
@@ -219,6 +243,7 @@ struct BuildStatus {
   void BuildEdgeStarted(Edge* edge);
   void BuildEdgeFinished(Edge* edge, bool success, const string& output,
                          int* start_time, int* end_time);
+  void BuildLoadDyndeps();
   void BuildStarted();
   void BuildFinished();
 
diff --git a/src/build_test.cc b/src/build_test.cc
index 46ab33e..b5dbc6c 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -21,6 +21,12 @@
 #include "graph.h"
 #include "test.h"
 
+struct CompareEdgesByOutput {
+  static bool cmp(const Edge* a, const Edge* b) {
+    return a->outputs_[0]->path() < b->outputs_[0]->path();
+  }
+};
+
 /// Fixture for tests involving Plan.
 // Though Plan doesn't use State, it's useful to have one around
 // to create Nodes and Edges.
@@ -31,12 +37,6 @@ struct PlanTest : public StateTestWithBuiltinRules {
   // provide a means to get available Edges in order and in a format which is
   // easy to write tests around.
   void FindWorkSorted(deque<Edge*>* ret, int count) {
-    struct CompareEdgesByOutput {
-      static bool cmp(const Edge* a, const Edge* b) {
-        return a->outputs_[0]->path() < b->outputs_[0]->path();
-      }
-    };
-
     for (int i = 0; i < count; ++i) {
       ASSERT_TRUE(plan_.more_to_do());
       Edge* edge = plan_.FindWork();
@@ -68,14 +68,16 @@ TEST_F(PlanTest, Basic) {
 
   ASSERT_FALSE(plan_.FindWork());
 
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
   ASSERT_EQ("mid", edge->inputs_[0]->path());
   ASSERT_EQ("out", edge->outputs_[0]->path());
 
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   ASSERT_FALSE(plan_.more_to_do());
   edge = plan_.FindWork();
@@ -99,11 +101,13 @@ TEST_F(PlanTest, DoubleOutputDirect) {
   Edge* edge;
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat in
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat mid1 mid2
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_FALSE(edge);  // done
@@ -129,19 +133,23 @@ TEST_F(PlanTest, DoubleOutputIndirect) {
   Edge* edge;
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat in
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat a1
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat a2
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat b1 b2
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_FALSE(edge);  // done
@@ -167,19 +175,23 @@ TEST_F(PlanTest, DoubleDependent) {
   Edge* edge;
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat in
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat mid
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat mid
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);  // cat a1 a2
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_FALSE(edge);  // done
@@ -204,7 +216,8 @@ void PlanTest::TestPoolWithDepthOne(const char* test_case) {
   // This will be false since poolcat is serialized
   ASSERT_FALSE(plan_.FindWork());
 
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
@@ -213,7 +226,8 @@ void PlanTest::TestPoolWithDepthOne(const char* test_case) {
 
   ASSERT_FALSE(plan_.FindWork());
 
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   ASSERT_FALSE(plan_.more_to_do());
   edge = plan_.FindWork();
@@ -289,7 +303,8 @@ TEST_F(PlanTest, PoolsWithDepthTwo) {
   ASSERT_EQ("outb3", edge->outputs_[0]->path());
 
   // finish out1
-  plan_.EdgeFinished(edges.front(), Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edges.front(), Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
   edges.pop_front();
 
   // out3 should be available
@@ -300,19 +315,22 @@ TEST_F(PlanTest, PoolsWithDepthTwo) {
 
   ASSERT_FALSE(plan_.FindWork());
 
-  plan_.EdgeFinished(out3, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(out3, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   ASSERT_FALSE(plan_.FindWork());
 
   for (deque<Edge*>::iterator it = edges.begin(); it != edges.end(); ++it) {
-    plan_.EdgeFinished(*it, Plan::kEdgeSucceeded);
+    plan_.EdgeFinished(*it, Plan::kEdgeSucceeded, &err);
+    ASSERT_EQ("", err);
   }
 
   Edge* last = plan_.FindWork();
   ASSERT_TRUE(last);
   ASSERT_EQ("allTheThings", last->outputs_[0]->path());
 
-  plan_.EdgeFinished(last, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(last, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   ASSERT_FALSE(plan_.more_to_do());
   ASSERT_FALSE(plan_.FindWork());
@@ -354,7 +372,8 @@ TEST_F(PlanTest, PoolWithRedundantEdges) {
 
   edge = initial_edges[1];  // Foo first
   ASSERT_EQ("foo.cpp", edge->outputs_[0]->path());
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
@@ -362,11 +381,13 @@ TEST_F(PlanTest, PoolWithRedundantEdges) {
   ASSERT_EQ("foo.cpp", edge->inputs_[0]->path());
   ASSERT_EQ("foo.cpp", edge->inputs_[1]->path());
   ASSERT_EQ("foo.cpp.obj", edge->outputs_[0]->path());
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = initial_edges[0];  // Now for bar
   ASSERT_EQ("bar.cpp", edge->outputs_[0]->path());
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
@@ -374,7 +395,8 @@ TEST_F(PlanTest, PoolWithRedundantEdges) {
   ASSERT_EQ("bar.cpp", edge->inputs_[0]->path());
   ASSERT_EQ("bar.cpp", edge->inputs_[1]->path());
   ASSERT_EQ("bar.cpp.obj", edge->outputs_[0]->path());
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
@@ -382,14 +404,16 @@ TEST_F(PlanTest, PoolWithRedundantEdges) {
   ASSERT_EQ("foo.cpp.obj", edge->inputs_[0]->path());
   ASSERT_EQ("bar.cpp.obj", edge->inputs_[1]->path());
   ASSERT_EQ("libfoo.a", edge->outputs_[0]->path());
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
   ASSERT_FALSE(plan_.FindWork());
   ASSERT_EQ("libfoo.a", edge->inputs_[0]->path());
   ASSERT_EQ("all", edge->outputs_[0]->path());
-  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded);
+  plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_FALSE(edge);
@@ -422,7 +446,8 @@ TEST_F(PlanTest, PoolWithFailingEdge) {
   // This will be false since poolcat is serialized
   ASSERT_FALSE(plan_.FindWork());
 
-  plan_.EdgeFinished(edge, Plan::kEdgeFailed);
+  plan_.EdgeFinished(edge, Plan::kEdgeFailed, &err);
+  ASSERT_EQ("", err);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
@@ -431,7 +456,8 @@ TEST_F(PlanTest, PoolWithFailingEdge) {
 
   ASSERT_FALSE(plan_.FindWork());
 
-  plan_.EdgeFinished(edge, Plan::kEdgeFailed);
+  plan_.EdgeFinished(edge, Plan::kEdgeFailed, &err);
+  ASSERT_EQ("", err);
 
   ASSERT_TRUE(plan_.more_to_do()); // Jobs have failed
   edge = plan_.FindWork();
@@ -441,7 +467,7 @@ TEST_F(PlanTest, PoolWithFailingEdge) {
 /// Fake implementation of CommandRunner, useful for tests.
 struct FakeCommandRunner : public CommandRunner {
   explicit FakeCommandRunner(VirtualFileSystem* fs) :
-      last_command_(NULL), fs_(fs) {}
+      max_active_edges_(1), fs_(fs) {}
 
   // CommandRunner impl
   virtual bool CanRunMore();
@@ -451,7 +477,8 @@ struct FakeCommandRunner : public CommandRunner {
   virtual void Abort();
 
   vector<string> commands_ran_;
-  Edge* last_command_;
+  vector<Edge*> active_edges_;
+  size_t max_active_edges_;
   VirtualFileSystem* fs_;
 };
 
@@ -543,12 +570,13 @@ void BuildTest::RebuildTarget(const string& target, const char* manifest,
 }
 
 bool FakeCommandRunner::CanRunMore() {
-  // Only run one at a time.
-  return last_command_ == NULL;
+  return active_edges_.size() < max_active_edges_;
 }
 
 bool FakeCommandRunner::StartCommand(Edge* edge) {
-  assert(!last_command_);
+  assert(active_edges_.size() < max_active_edges_);
+  assert(find(active_edges_.begin(), active_edges_.end(), edge)
+         == active_edges_.end());
   commands_ran_.push_back(edge->EvaluateCommand());
   if (edge->rule().name() == "cat"  ||
       edge->rule().name() == "cat_rsp" ||
@@ -566,20 +594,38 @@ bool FakeCommandRunner::StartCommand(Edge* edge) {
              edge->rule().name() == "interrupt" ||
              edge->rule().name() == "console") {
     // Don't do anything.
+  } else if (edge->rule().name() == "cp") {
+    assert(!edge->inputs_.empty());
+    assert(edge->outputs_.size() == 1);
+    string content;
+    string err;
+    if (fs_->ReadFile(edge->inputs_[0]->path(), &content, &err) ==
+        DiskInterface::Okay)
+      fs_->WriteFile(edge->outputs_[0]->path(), content);
   } else {
     printf("unknown command\n");
     return false;
   }
 
-  last_command_ = edge;
+  active_edges_.push_back(edge);
+
+  // Allow tests to control the order by the name of the first output.
+  sort(active_edges_.begin(), active_edges_.end(),
+       CompareEdgesByOutput::cmp);
+
   return true;
 }
 
 bool FakeCommandRunner::WaitForCommand(Result* result) {
-  if (!last_command_)
+  if (active_edges_.empty())
     return false;
 
-  Edge* edge = last_command_;
+  // All active edges were already completed immediately when started,
+  // so we can pick any edge here.  Pick the last edge.  Tests can
+  // control the order of edges by the name of the first output.
+  vector<Edge*>::iterator edge_iter = active_edges_.end() - 1;
+
+  Edge* edge = *edge_iter;
   result->edge = edge;
 
   if (edge->rule().name() == "interrupt" ||
@@ -593,7 +639,7 @@ bool FakeCommandRunner::WaitForCommand(Result* result) {
       result->status = ExitSuccess;
     else
       result->status = ExitFailure;
-    last_command_ = NULL;
+    active_edges_.erase(edge_iter);
     return true;
   }
 
@@ -602,19 +648,33 @@ bool FakeCommandRunner::WaitForCommand(Result* result) {
     result->status = ExitFailure;
   else
     result->status = ExitSuccess;
-  last_command_ = NULL;
+
+  // Provide a way for test cases to verify when an edge finishes that
+  // some other edge is still active.  This is useful for test cases
+  // covering behavior involving multiple active edges.
+  const string& verify_active_edge = edge->GetBinding("verify_active_edge");
+  if (!verify_active_edge.empty()) {
+    bool verify_active_edge_found = false;
+    for (vector<Edge*>::iterator i = active_edges_.begin();
+         i != active_edges_.end(); ++i) {
+      if ((*i)->outputs_.size() >= 1 &&
+          (*i)->outputs_[0]->path() == verify_active_edge) {
+        verify_active_edge_found = true;
+      }
+    }
+    EXPECT_TRUE(verify_active_edge_found);
+  }
+
+  active_edges_.erase(edge_iter);
   return true;
 }
 
 vector<Edge*> FakeCommandRunner::GetActiveEdges() {
-  vector<Edge*> edges;
-  if (last_command_)
-    edges.push_back(last_command_);
-  return edges;
+  return active_edges_;
 }
 
 void FakeCommandRunner::Abort() {
-  last_command_ = NULL;
+  active_edges_.clear();
 }
 
 void BuildTest::Dirty(const string& path) {
@@ -2308,3 +2368,712 @@ TEST_F(BuildTest, Console) {
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, command_runner_.commands_ran_.size());
 }
+
+TEST_F(BuildTest, DyndepMissingAndNoRule) {
+  // Verify that we can diagnose when a dyndep file is missing and
+  // has no rule to build it.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+));
+
+  string err;
+  EXPECT_FALSE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("loading 'dd': No such file or directory", err);
+}
+
+TEST_F(BuildTest, DyndepReadyImplicitConnection) {
+  // Verify that a dyndep file can be loaded immediately to discover
+  // that one edge has an implicit output that is also an implicit
+  // input of another edge.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"build tmp: touch || dd\n"
+"  dyndep = dd\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+));
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out | out.imp: dyndep | tmp.imp\n"
+"build tmp | tmp.imp: dyndep\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("touch tmp tmp.imp", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch out out.imp", command_runner_.commands_ran_[1]);
+}
+
+TEST_F(BuildTest, DyndepReadySyntaxError) {
+  // Verify that a dyndep file can be loaded immediately to discover
+  // and reject a syntax error in it.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+));
+  fs_.Create("dd",
+"build out: dyndep\n"
+);
+
+  string err;
+  EXPECT_FALSE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("dd:1: expected 'ninja_dyndep_version = ...'\n", err);
+}
+
+TEST_F(BuildTest, DyndepReadyCircular) {
+  // Verify that a dyndep file can be loaded immediately to discover
+  // and reject a circular dependency.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out: r in || dd\n"
+"  dyndep = dd\n"
+"build in: r circ\n"
+  ));
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out | circ: dyndep\n"
+  );
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_FALSE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("dependency cycle: circ -> in -> circ", err);
+}
+
+TEST_F(BuildTest, DyndepBuild) {
+  // Verify that a dyndep file can be built and loaded to discover nothing.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+));
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  size_t files_created = fs_.files_created_.size();
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch out", command_runner_.commands_ran_[1]);
+  ASSERT_EQ(2u, fs_.files_read_.size());
+  EXPECT_EQ("dd-in", fs_.files_read_[0]);
+  EXPECT_EQ("dd", fs_.files_read_[1]);
+  ASSERT_EQ(2u + files_created, fs_.files_created_.size());
+  EXPECT_EQ(1u, fs_.files_created_.count("dd"));
+  EXPECT_EQ(1u, fs_.files_created_.count("out"));
+}
+
+TEST_F(BuildTest, DyndepBuildSyntaxError) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // and reject a syntax error in it.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+));
+  fs_.Create("dd-in",
+"build out: dyndep\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_FALSE(builder_.Build(&err));
+  EXPECT_EQ("dd:1: expected 'ninja_dyndep_version = ...'\n", err);
+}
+
+TEST_F(BuildTest, DyndepBuildUnrelatedOutput) {
+  // Verify that a dyndep file can have dependents that do not specify
+  // it as their dyndep binding.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build unrelated: touch || dd\n"
+"build out: touch unrelated || dd\n"
+"  dyndep = dd\n"
+  ));
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+);
+  fs_.Tick();
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch unrelated", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch out", command_runner_.commands_ran_[2]);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverNewOutput) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // a new output of an edge.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build out: touch in || dd\n"
+"  dyndep = dd\n"
+  ));
+  fs_.Create("in", "");
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out | out.imp: dyndep\n"
+);
+  fs_.Tick();
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch out out.imp", command_runner_.commands_ran_[1]);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverNewOutputWithMultipleRules1) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // a new output of an edge that is already the output of another edge.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build out1 | out-twice.imp: touch in\n"
+"build out2: touch in || dd\n"
+"  dyndep = dd\n"
+  ));
+  fs_.Create("in", "");
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out2 | out-twice.imp: dyndep\n"
+);
+  fs_.Tick();
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out1", &err));
+  EXPECT_TRUE(builder_.AddTarget("out2", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_FALSE(builder_.Build(&err));
+  EXPECT_EQ("multiple rules generate out-twice.imp", err);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverNewOutputWithMultipleRules2) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // a new output of an edge that is already the output of another
+  // edge also discovered by dyndep.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd1: cp dd1-in\n"
+"build out1: touch || dd1\n"
+"  dyndep = dd1\n"
+"build dd2: cp dd2-in || dd1\n" // make order predictable for test
+"build out2: touch || dd2\n"
+"  dyndep = dd2\n"
+));
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
+  fs_.Create("dd1-in",
+"ninja_dyndep_version = 1\n"
+"build out1 | out-twice.imp: dyndep\n"
+);
+  fs_.Create("dd2-in", "");
+  fs_.Create("dd2",
+"ninja_dyndep_version = 1\n"
+"build out2 | out-twice.imp: dyndep\n"
+);
+  fs_.Tick();
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out1", &err));
+  EXPECT_TRUE(builder_.AddTarget("out2", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_FALSE(builder_.Build(&err));
+  EXPECT_EQ("multiple rules generate out-twice.imp", err);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverNewInput) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // a new input to an edge.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build in: touch\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+  ));
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep | in\n"
+);
+  fs_.Tick();
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch in", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch out", command_runner_.commands_ran_[2]);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverImplicitConnection) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // that one edge has an implicit output that is also an implicit
+  // input of another edge.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build tmp: touch || dd\n"
+"  dyndep = dd\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+));
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out | out.imp: dyndep | tmp.imp\n"
+"build tmp | tmp.imp: dyndep\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch tmp tmp.imp", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch out out.imp", command_runner_.commands_ran_[2]);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverNowWantEdge) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // that an edge is actually wanted due to a missing implicit output.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build tmp: touch || dd\n"
+"  dyndep = dd\n"
+"build out: touch tmp || dd\n"
+"  dyndep = dd\n"
+));
+  fs_.Create("tmp", "");
+  fs_.Create("out", "");
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+"build tmp | tmp.imp: dyndep\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch tmp tmp.imp", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch out out.imp", command_runner_.commands_ran_[2]);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverNowWantEdgeAndDependent) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // that an edge and a dependent are actually wanted.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build tmp: touch || dd\n"
+"  dyndep = dd\n"
+"build out: touch tmp\n"
+));
+  fs_.Create("tmp", "");
+  fs_.Create("out", "");
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build tmp | tmp.imp: dyndep\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch tmp tmp.imp", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch out out.imp", command_runner_.commands_ran_[2]);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverCircular) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // and reject a circular dependency.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build out: r in || dd\n"
+"  depfile = out.d\n"
+"  dyndep = dd\n"
+"build in: r || dd\n"
+"  dyndep = dd\n"
+  ));
+  fs_.Create("out.d", "out: inimp\n");
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out | circ: dyndep\n"
+"build in: dyndep | circ\n"
+  );
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_FALSE(builder_.Build(&err));
+  // Depending on how the pointers in Plan::ready_ work out, we could have
+  // discovered the cycle from either starting point.
+  EXPECT_TRUE(err == "dependency cycle: circ -> in -> circ" ||
+              err == "dependency cycle: in -> circ -> in");
+}
+
+TEST_F(BuildWithLogTest, DyndepBuildDiscoverRestat) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // that an edge has a restat binding.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule true\n"
+"  command = true\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build out1: true in || dd\n"
+"  dyndep = dd\n"
+"build out2: cat out1\n"));
+
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out1: dyndep\n"
+"  restat = 1\n"
+);
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  // Do a pre-build so that there's commands in the log for the outputs,
+  // otherwise, the lack of an entry in the build log will cause "out2" to
+  // rebuild regardless of restat.
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out2", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  ASSERT_EQ("", err);
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("true", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("cat out1 > out2", command_runner_.commands_ran_[2]);
+
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  // We touched "in", so we should build "out1".  But because "true" does not
+  // touch "out1", we should cancel the build of "out2".
+  EXPECT_TRUE(builder_.AddTarget("out2", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("true", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverScheduledEdge) {
+  // Verify that a dyndep file can be built and loaded to discover a
+  // new input that itself is an output from an edge that has already
+  // been scheduled but not finished.  We should not re-schedule it.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build out1 | out1.imp: touch\n"
+"build zdd: cp zdd-in\n"
+"  verify_active_edge = out1\n" // verify out1 is active when zdd is finished
+"build out2: cp out1 || zdd\n"
+"  dyndep = zdd\n"
+));
+  fs_.Create("zdd-in",
+"ninja_dyndep_version = 1\n"
+"build out2: dyndep | out1.imp\n"
+);
+
+  // Enable concurrent builds so that we can load the dyndep file
+  // while another edge is still active.
+  command_runner_.max_active_edges_ = 2;
+
+  // During the build "out1" and "zdd" should be built concurrently.
+  // The fake command runner will finish these in reverse order
+  // of the names of the first outputs, so "zdd" will finish first
+  // and we will load the dyndep file while the edge for "out1" is
+  // still active.  This will add a new dependency on "out1.imp",
+  // also produced by the active edge.  The builder should not
+  // re-schedule the already-active edge.
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out1", &err));
+  EXPECT_TRUE(builder_.AddTarget("out2", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  // Depending on how the pointers in Plan::ready_ work out, the first
+  // two commands may have run in either order.
+  EXPECT_TRUE((command_runner_.commands_ran_[0] == "touch out1 out1.imp" &&
+               command_runner_.commands_ran_[1] == "cp zdd-in zdd") ||
+              (command_runner_.commands_ran_[1] == "touch out1 out1.imp" &&
+               command_runner_.commands_ran_[0] == "cp zdd-in zdd"));
+  EXPECT_EQ("cp out1 out2", command_runner_.commands_ran_[2]);
+}
+
+TEST_F(BuildTest, DyndepTwoLevelDirect) {
+  // Verify that a clean dyndep file can depend on a dirty dyndep file
+  // and be loaded properly after the dirty one is built and loaded.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd1: cp dd1-in\n"
+"build out1 | out1.imp: touch || dd1\n"
+"  dyndep = dd1\n"
+"build dd2: cp dd2-in || dd1\n" // direct order-only dep on dd1
+"build out2: touch || dd2\n"
+"  dyndep = dd2\n"
+));
+  fs_.Create("out1.imp", "");
+  fs_.Create("out2", "");
+  fs_.Create("out2.imp", "");
+  fs_.Create("dd1-in",
+"ninja_dyndep_version = 1\n"
+"build out1: dyndep\n"
+);
+  fs_.Create("dd2-in", "");
+  fs_.Create("dd2",
+"ninja_dyndep_version = 1\n"
+"build out2 | out2.imp: dyndep | out1.imp\n"
+);
+
+  // During the build dd1 should be built and loaded.  The RecomputeDirty
+  // called as a result of loading dd1 should not cause dd2 to be loaded
+  // because the builder will never get a chance to update the build plan
+  // to account for dd2.  Instead dd2 should only be later loaded once the
+  // builder recognizes that it is now ready (as its order-only dependency
+  // on dd1 has been satisfied).  This test case verifies that each dyndep
+  // file is loaded to update the build graph independently.
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out2", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd1-in dd1", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch out1 out1.imp", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch out2 out2.imp", command_runner_.commands_ran_[2]);
+}
+
+TEST_F(BuildTest, DyndepTwoLevelIndirect) {
+  // Verify that dyndep files can add to an edge new implicit inputs that
+  // correspond to implicit outputs added to other edges by other dyndep
+  // files on which they (order-only) depend.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd1: cp dd1-in\n"
+"build out1: touch || dd1\n"
+"  dyndep = dd1\n"
+"build dd2: cp dd2-in || out1\n" // indirect order-only dep on dd1
+"build out2: touch || dd2\n"
+"  dyndep = dd2\n"
+));
+  fs_.Create("out1.imp", "");
+  fs_.Create("out2", "");
+  fs_.Create("out2.imp", "");
+  fs_.Create("dd1-in",
+"ninja_dyndep_version = 1\n"
+"build out1 | out1.imp: dyndep\n"
+);
+  fs_.Create("dd2-in", "");
+  fs_.Create("dd2",
+"ninja_dyndep_version = 1\n"
+"build out2 | out2.imp: dyndep | out1.imp\n"
+);
+
+  // During the build dd1 should be built and loaded.  Then dd2 should
+  // be built and loaded.  Loading dd2 should cause the builder to
+  // recognize that out2 needs to be built even though it was originally
+  // clean without dyndep info.
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out2", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd1-in dd1", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch out1 out1.imp", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch out2 out2.imp", command_runner_.commands_ran_[2]);
+}
+
+TEST_F(BuildTest, DyndepTwoLevelDiscoveredReady) {
+  // Verify that a dyndep file can discover a new input whose
+  // edge also has a dyndep file that is ready to load immediately.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd0: cp dd0-in\n"
+"build dd1: cp dd1-in\n"
+"build in: touch\n"
+"build tmp: touch || dd0\n"
+"  dyndep = dd0\n"
+"build out: touch || dd1\n"
+"  dyndep = dd1\n"
+  ));
+  fs_.Create("dd1-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep | tmp\n"
+);
+  fs_.Create("dd0-in", "");
+  fs_.Create("dd0",
+"ninja_dyndep_version = 1\n"
+"build tmp: dyndep | in\n"
+);
+  fs_.Tick();
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(4u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd1-in dd1", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch in", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch tmp", command_runner_.commands_ran_[2]);
+  EXPECT_EQ("touch out", command_runner_.commands_ran_[3]);
+}
+
+TEST_F(BuildTest, DyndepTwoLevelDiscoveredDirty) {
+  // Verify that a dyndep file can discover a new input whose
+  // edge also has a dyndep file that needs to be built.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd0: cp dd0-in\n"
+"build dd1: cp dd1-in\n"
+"build in: touch\n"
+"build tmp: touch || dd0\n"
+"  dyndep = dd0\n"
+"build out: touch || dd1\n"
+"  dyndep = dd1\n"
+  ));
+  fs_.Create("dd1-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep | tmp\n"
+);
+  fs_.Create("dd0-in",
+"ninja_dyndep_version = 1\n"
+"build tmp: dyndep | in\n"
+);
+  fs_.Tick();
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(5u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd1-in dd1", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("cp dd0-in dd0", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch in", command_runner_.commands_ran_[2]);
+  EXPECT_EQ("touch tmp", command_runner_.commands_ran_[3]);
+  EXPECT_EQ("touch out", command_runner_.commands_ran_[4]);
+}
diff --git a/src/clean.cc b/src/clean.cc
index ce6a575..d1f221d 100644
--- a/src/clean.cc
+++ b/src/clean.cc
@@ -22,21 +22,12 @@
 #include "state.h"
 #include "util.h"
 
-Cleaner::Cleaner(State* state, const BuildConfig& config)
-  : state_(state),
-    config_(config),
-    removed_(),
-    cleaned_(),
-    cleaned_files_count_(0),
-    disk_interface_(new RealDiskInterface),
-    status_(0) {
-}
-
 Cleaner::Cleaner(State* state,
                  const BuildConfig& config,
                  DiskInterface* disk_interface)
   : state_(state),
     config_(config),
+    dyndep_loader_(state, disk_interface),
     removed_(),
     cleaned_(),
     cleaned_files_count_(0),
@@ -113,6 +104,7 @@ void Cleaner::PrintFooter() {
 int Cleaner::CleanAll(bool generator) {
   Reset();
   PrintHeader();
+  LoadDyndeps();
   for (vector<Edge*>::iterator e = state_->edges_.begin();
        e != state_->edges_.end(); ++e) {
     // Do not try to remove phony targets
@@ -158,6 +150,7 @@ int Cleaner::CleanTarget(Node* target) {
 
   Reset();
   PrintHeader();
+  LoadDyndeps();
   DoCleanTarget(target);
   PrintFooter();
   return status_;
@@ -180,6 +173,7 @@ int Cleaner::CleanTarget(const char* target) {
 int Cleaner::CleanTargets(int target_count, char* targets[]) {
   Reset();
   PrintHeader();
+  LoadDyndeps();
   for (int i = 0; i < target_count; ++i) {
     string target_name = targets[i];
     uint64_t slash_bits;
@@ -223,6 +217,7 @@ int Cleaner::CleanRule(const Rule* rule) {
 
   Reset();
   PrintHeader();
+  LoadDyndeps();
   DoCleanRule(rule);
   PrintFooter();
   return status_;
@@ -247,6 +242,7 @@ int Cleaner::CleanRules(int rule_count, char* rules[]) {
 
   Reset();
   PrintHeader();
+  LoadDyndeps();
   for (int i = 0; i < rule_count; ++i) {
     const char* rule_name = rules[i];
     const Rule* rule = state_->bindings_.LookupRule(rule_name);
@@ -269,3 +265,16 @@ void Cleaner::Reset() {
   removed_.clear();
   cleaned_.clear();
 }
+
+void Cleaner::LoadDyndeps() {
+  // Load dyndep files that exist, before they are cleaned.
+  for (vector<Edge*>::iterator e = state_->edges_.begin();
+       e != state_->edges_.end(); ++e) {
+    if (Node* dyndep = (*e)->dyndep_) {
+      // Capture and ignore errors loading the dyndep file.
+      // We clean as much of the graph as we know.
+      std::string err;
+      dyndep_loader_.LoadDyndeps(dyndep, &err);
+    }
+  }
+}
diff --git a/src/clean.h b/src/clean.h
index 19432ab..d044fb1 100644
--- a/src/clean.h
+++ b/src/clean.h
@@ -19,6 +19,7 @@
 #include <string>
 
 #include "build.h"
+#include "dyndep.h"
 
 using namespace std;
 
@@ -28,11 +29,7 @@ struct Rule;
 struct DiskInterface;
 
 struct Cleaner {
-  /// Build a cleaner object with a real disk interface.
-  Cleaner(State* state, const BuildConfig& config);
-
   /// Build a cleaner object with the given @a disk_interface
-  /// (Useful for testing).
   Cleaner(State* state,
           const BuildConfig& config,
           DiskInterface* disk_interface);
@@ -95,8 +92,12 @@ struct Cleaner {
   void DoCleanRule(const Rule* rule);
   void Reset();
 
+  /// Load dependencies from dyndep bindings.
+  void LoadDyndeps();
+
   State* state_;
   const BuildConfig& config_;
+  DyndepLoader dyndep_loader_;
   set<string> removed_;
   set<Node*> cleaned_;
   int cleaned_files_count_;
diff --git a/src/clean_test.cc b/src/clean_test.cc
index 63734ac..45187f4 100644
--- a/src/clean_test.cc
+++ b/src/clean_test.cc
@@ -285,6 +285,55 @@ TEST_F(CleanTest, CleanDepFileOnCleanRule) {
   EXPECT_EQ(2u, fs_.files_removed_.size());
 }
 
+TEST_F(CleanTest, CleanDyndep) {
+  // Verify that a dyndep file can be loaded to discover a new output
+  // to be cleaned.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build out: cat in || dd\n"
+"  dyndep = dd\n"
+  ));
+  fs_.Create("in", "");
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out | out.imp: dyndep\n"
+);
+  fs_.Create("out", "");
+  fs_.Create("out.imp", "");
+
+  Cleaner cleaner(&state_, config_, &fs_);
+
+  ASSERT_EQ(0, cleaner.cleaned_files_count());
+  EXPECT_EQ(0, cleaner.CleanAll());
+  EXPECT_EQ(2, cleaner.cleaned_files_count());
+  EXPECT_EQ(2u, fs_.files_removed_.size());
+
+  string err;
+  EXPECT_EQ(0, fs_.Stat("out", &err));
+  EXPECT_EQ(0, fs_.Stat("out.imp", &err));
+}
+
+TEST_F(CleanTest, CleanDyndepMissing) {
+  // Verify that a missing dyndep file is tolerated.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build out: cat in || dd\n"
+"  dyndep = dd\n"
+  ));
+  fs_.Create("in", "");
+  fs_.Create("out", "");
+  fs_.Create("out.imp", "");
+
+  Cleaner cleaner(&state_, config_, &fs_);
+
+  ASSERT_EQ(0, cleaner.cleaned_files_count());
+  EXPECT_EQ(0, cleaner.CleanAll());
+  EXPECT_EQ(1, cleaner.cleaned_files_count());
+  EXPECT_EQ(1u, fs_.files_removed_.size());
+
+  string err;
+  EXPECT_EQ(0, fs_.Stat("out", &err));
+  EXPECT_EQ(1, fs_.Stat("out.imp", &err));
+}
+
 TEST_F(CleanTest, CleanRspFile) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "rule cc\n"
diff --git a/src/dyndep.cc b/src/dyndep.cc
new file mode 100644
index 0000000..2aee601
--- /dev/null
+++ b/src/dyndep.cc
@@ -0,0 +1,124 @@
+// Copyright 2015 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "dyndep.h"
+
+#include <assert.h>
+#include <stdio.h>
+
+#include "debug_flags.h"
+#include "disk_interface.h"
+#include "dyndep_parser.h"
+#include "graph.h"
+#include "state.h"
+#include "util.h"
+
+bool DyndepLoader::LoadDyndeps(Node* node, std::string* err) const {
+  DyndepFile ddf;
+  return LoadDyndeps(node, &ddf, err);
+}
+
+bool DyndepLoader::LoadDyndeps(Node* node, DyndepFile* ddf,
+                               std::string* err) const {
+  // We are loading the dyndep file now so it is no longer pending.
+  node->set_dyndep_pending(false);
+
+  // Load the dyndep information from the file.
+  EXPLAIN("loading dyndep file '%s'", node->path().c_str());
+  if (!LoadDyndepFile(node, ddf, err))
+    return false;
+
+  // Update each edge that specified this node as its dyndep binding.
+  std::vector<Edge*> const& out_edges = node->out_edges();
+  for (std::vector<Edge*>::const_iterator oe = out_edges.begin();
+       oe != out_edges.end(); ++oe) {
+    Edge* const edge = *oe;
+    if (edge->dyndep_ != node)
+      continue;
+
+    DyndepFile::iterator ddi = ddf->find(edge);
+    if (ddi == ddf->end()) {
+      *err = ("'" + edge->outputs_[0]->path() + "' "
+              "not mentioned in its dyndep file "
+              "'" + node->path() + "'");
+      return false;
+    }
+
+    ddi->second.used_ = true;
+    Dyndeps const& dyndeps = ddi->second;
+    if (!UpdateEdge(edge, &dyndeps, err)) {
+      return false;
+    }
+  }
+
+  // Reject extra outputs in dyndep file.
+  for (DyndepFile::const_iterator oe = ddf->begin(); oe != ddf->end();
+       ++oe) {
+    if (!oe->second.used_) {
+      Edge* const edge = oe->first;
+      *err = ("dyndep file '" + node->path() + "' mentions output "
+              "'" + edge->outputs_[0]->path() + "' whose build statement "
+              "does not have a dyndep binding for the file");
+      return false;
+    }
+  }
+
+  return true;
+}
+
+bool DyndepLoader::UpdateEdge(Edge* edge, Dyndeps const* dyndeps,
+                              std::string* err) const {
+  // Add dyndep-discovered bindings to the edge.
+  // We know the edge already has its own binding
+  // scope because it has a "dyndep" binding.
+  if (dyndeps->restat_)
+    edge->env_->AddBinding("restat", "1");
+
+  // Add the dyndep-discovered outputs to the edge.
+  edge->outputs_.insert(edge->outputs_.end(),
+                        dyndeps->implicit_outputs_.begin(),
+                        dyndeps->implicit_outputs_.end());
+  edge->implicit_outs_ += dyndeps->implicit_outputs_.size();
+
+  // Add this edge as incoming to each new output.
+  for (std::vector<Node*>::const_iterator i =
+           dyndeps->implicit_outputs_.begin();
+       i != dyndeps->implicit_outputs_.end(); ++i) {
+    if ((*i)->in_edge() != NULL) {
+      *err = "multiple rules generate " + (*i)->path();
+      return false;
+    }
+    (*i)->set_in_edge(edge);
+  }
+
+  // Add the dyndep-discovered inputs to the edge.
+  edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
+                       dyndeps->implicit_inputs_.begin(),
+                       dyndeps->implicit_inputs_.end());
+  edge->implicit_deps_ += dyndeps->implicit_inputs_.size();
+
+  // Add this edge as outgoing from each new input.
+  for (std::vector<Node*>::const_iterator i =
+           dyndeps->implicit_inputs_.begin();
+       i != dyndeps->implicit_inputs_.end(); ++i)
+    (*i)->AddOutEdge(edge);
+
+  return true;
+}
+
+bool DyndepLoader::LoadDyndepFile(Node* file, DyndepFile* ddf,
+                                  std::string* err) const {
+  DyndepParser parser(state_, disk_interface_, ddf);
+  return parser.Load(file->path(), err);
+}
diff --git a/src/dyndep.h b/src/dyndep.h
new file mode 100644
index 0000000..907f921
--- /dev/null
+++ b/src/dyndep.h
@@ -0,0 +1,64 @@
+// Copyright 2015 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef NINJA_DYNDEP_LOADER_H_
+#define NINJA_DYNDEP_LOADER_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+struct DiskInterface;
+struct Edge;
+struct Node;
+struct State;
+
+/// Store dynamically-discovered dependency information for one edge.
+struct Dyndeps {
+  Dyndeps() : used_(false), restat_(false) {}
+  bool used_;
+  bool restat_;
+  std::vector<Node*> implicit_inputs_;
+  std::vector<Node*> implicit_outputs_;
+};
+
+/// Store data loaded from one dyndep file.  Map from an edge
+/// to its dynamically-discovered dependency information.
+/// This is a struct rather than a typedef so that we can
+/// forward-declare it in other headers.
+struct DyndepFile: public std::map<Edge*, Dyndeps> {};
+
+/// DyndepLoader loads dynamically discovered dependencies, as
+/// referenced via the "dyndep" attribute in build files.
+struct DyndepLoader {
+  DyndepLoader(State* state, DiskInterface* disk_interface)
+      : state_(state), disk_interface_(disk_interface) {}
+
+  /// Load a dyndep file from the given node's path and update the
+  /// build graph with the new information.  One overload accepts
+  /// a caller-owned 'DyndepFile' object in which to store the
+  /// information loaded from the dyndep file.
+  bool LoadDyndeps(Node* node, std::string* err) const;
+  bool LoadDyndeps(Node* node, DyndepFile* ddf, std::string* err) const;
+
+ private:
+  bool LoadDyndepFile(Node* file, DyndepFile* ddf, std::string* err) const;
+
+  bool UpdateEdge(Edge* edge, Dyndeps const* dyndeps, std::string* err) const;
+
+  State* state_;
+  DiskInterface* disk_interface_;
+};
+
+#endif  // NINJA_DYNDEP_LOADER_H_
diff --git a/src/dyndep_parser.cc b/src/dyndep_parser.cc
new file mode 100644
index 0000000..baebbac
--- /dev/null
+++ b/src/dyndep_parser.cc
@@ -0,0 +1,223 @@
+// Copyright 2015 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "dyndep_parser.h"
+
+#include <vector>
+
+#include "dyndep.h"
+#include "graph.h"
+#include "state.h"
+#include "util.h"
+#include "version.h"
+
+DyndepParser::DyndepParser(State* state, FileReader* file_reader,
+                           DyndepFile* dyndep_file)
+    : Parser(state, file_reader)
+    , dyndep_file_(dyndep_file) {
+}
+
+bool DyndepParser::Parse(const string& filename, const string& input,
+                         string* err) {
+  lexer_.Start(filename, input);
+
+  // Require a supported ninja_dyndep_version value immediately so
+  // we can exit before encountering any syntactic surprises.
+  bool haveDyndepVersion = false;
+
+  for (;;) {
+    Lexer::Token token = lexer_.ReadToken();
+    switch (token) {
+    case Lexer::BUILD: {
+      if (!haveDyndepVersion)
+        return lexer_.Error("expected 'ninja_dyndep_version = ...'", err);
+      if (!ParseEdge(err))
+        return false;
+      break;
+    }
+    case Lexer::IDENT: {
+      lexer_.UnreadToken();
+      if (haveDyndepVersion)
+        return lexer_.Error(string("unexpected ") + Lexer::TokenName(token),
+                            err);
+      if (!ParseDyndepVersion(err))
+        return false;
+      haveDyndepVersion = true;
+      break;
+    }
+    case Lexer::ERROR:
+      return lexer_.Error(lexer_.DescribeLastError(), err);
+    case Lexer::TEOF:
+      if (!haveDyndepVersion)
+        return lexer_.Error("expected 'ninja_dyndep_version = ...'", err);
+      return true;
+    case Lexer::NEWLINE:
+      break;
+    default:
+      return lexer_.Error(string("unexpected ") + Lexer::TokenName(token),
+                          err);
+    }
+  }
+  return false;  // not reached
+}
+
+bool DyndepParser::ParseDyndepVersion(string* err) {
+  string name;
+  EvalString let_value;
+  if (!ParseLet(&name, &let_value, err))
+    return false;
+  if (name != "ninja_dyndep_version") {
+    return lexer_.Error("expected 'ninja_dyndep_version = ...'", err);
+  }
+  string version = let_value.Evaluate(&env_);
+  int major, minor;
+  ParseVersion(version, &major, &minor);
+  if (major != 1 || minor != 0) {
+    return lexer_.Error(
+      string("unsupported 'ninja_dyndep_version = ") + version + "'", err);
+    return false;
+  }
+  return true;
+}
+
+bool DyndepParser::ParseLet(string* key, EvalString* value, string* err) {
+  if (!lexer_.ReadIdent(key))
+    return lexer_.Error("expected variable name", err);
+  if (!ExpectToken(Lexer::EQUALS, err))
+    return false;
+  if (!lexer_.ReadVarValue(value, err))
+    return false;
+  return true;
+}
+
+bool DyndepParser::ParseEdge(string* err) {
+  // Parse one explicit output.  We expect it to already have an edge.
+  // We will record its dynamically-discovered dependency information.
+  Dyndeps* dyndeps = NULL;
+  {
+    EvalString out0;
+    if (!lexer_.ReadPath(&out0, err))
+      return false;
+    if (out0.empty())
+      return lexer_.Error("expected path", err);
+
+    string path = out0.Evaluate(&env_);
+    string path_err;
+    uint64_t slash_bits;
+    if (!CanonicalizePath(&path, &slash_bits, &path_err))
+      return lexer_.Error(path_err, err);
+    Node* node = state_->LookupNode(path);
+    if (!node || !node->in_edge())
+      return lexer_.Error("no build statement exists for '" + path + "'", err);
+    Edge* edge = node->in_edge();
+    std::pair<DyndepFile::iterator, bool> res =
+      dyndep_file_->insert(DyndepFile::value_type(edge, Dyndeps()));
+    if (!res.second)
+      return lexer_.Error("multiple statements for '" + path + "'", err);
+    dyndeps = &res.first->second;
+  }
+
+  // Disallow explicit outputs.
+  {
+    EvalString out;
+    if (!lexer_.ReadPath(&out, err))
+      return false;
+    if (!out.empty())
+      return lexer_.Error("explicit outputs not supported", err);
+  }
+
+  // Parse implicit outputs, if any.
+  vector<EvalString> outs;
+  if (lexer_.PeekToken(Lexer::PIPE)) {
+    for (;;) {
+      EvalString out;
+      if (!lexer_.ReadPath(&out, err))
+        return err;
+      if (out.empty())
+        break;
+      outs.push_back(out);
+    }
+  }
+
+  if (!ExpectToken(Lexer::COLON, err))
+    return false;
+
+  string rule_name;
+  if (!lexer_.ReadIdent(&rule_name) || rule_name != "dyndep")
+    return lexer_.Error("expected build command name 'dyndep'", err);
+
+  // Disallow explicit inputs.
+  {
+    EvalString in;
+    if (!lexer_.ReadPath(&in, err))
+      return false;
+    if (!in.empty())
+      return lexer_.Error("explicit inputs not supported", err);
+  }
+
+  // Parse implicit inputs, if any.
+  vector<EvalString> ins;
+  if (lexer_.PeekToken(Lexer::PIPE)) {
+    for (;;) {
+      EvalString in;
+      if (!lexer_.ReadPath(&in, err))
+        return err;
+      if (in.empty())
+        break;
+      ins.push_back(in);
+    }
+  }
+
+  // Disallow order-only inputs.
+  if (lexer_.PeekToken(Lexer::PIPE2))
+    return lexer_.Error("order-only inputs not supported", err);
+
+  if (!ExpectToken(Lexer::NEWLINE, err))
+    return false;
+
+  if (lexer_.PeekToken(Lexer::INDENT)) {
+    string key;
+    EvalString val;
+    if (!ParseLet(&key, &val, err))
+      return false;
+    if (key != "restat")
+      return lexer_.Error("binding is not 'restat'", err);
+    string value = val.Evaluate(&env_);
+    dyndeps->restat_ = !value.empty();
+  }
+
+  dyndeps->implicit_inputs_.reserve(ins.size());
+  for (vector<EvalString>::iterator i = ins.begin(); i != ins.end(); ++i) {
+    string path = i->Evaluate(&env_);
+    string path_err;
+    uint64_t slash_bits;
+    if (!CanonicalizePath(&path, &slash_bits, &path_err))
+      return lexer_.Error(path_err, err);
+    Node* n = state_->GetNode(path, slash_bits);
+    dyndeps->implicit_inputs_.push_back(n);
+  }
+
+  dyndeps->implicit_outputs_.reserve(outs.size());
+  for (vector<EvalString>::iterator i = outs.begin(); i != outs.end(); ++i) {
+    string path = i->Evaluate(&env_);
+    string path_err;
+    uint64_t slash_bits;
+    if (!CanonicalizePath(&path, &slash_bits, &path_err))
+      return lexer_.Error(path_err, err);
+    Node* n = state_->GetNode(path, slash_bits);
+    dyndeps->implicit_outputs_.push_back(n);
+  }
+
+  return true;
+}
diff --git a/src/dyndep_parser.h b/src/dyndep_parser.h
new file mode 100644
index 0000000..09a3722
--- /dev/null
+++ b/src/dyndep_parser.h
@@ -0,0 +1,46 @@
+// Copyright 2015 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef NINJA_DYNDEP_PARSER_H_
+#define NINJA_DYNDEP_PARSER_H_
+
+#include "eval_env.h"
+#include "parser.h"
+
+struct DyndepFile;
+struct EvalString;
+
+/// Parses dyndep files.
+struct DyndepParser: public Parser {
+  DyndepParser(State* state, FileReader* file_reader,
+               DyndepFile* dyndep_file);
+
+  /// Parse a text string of input.  Used by tests.
+  bool ParseTest(const string& input, string* err) {
+    return Parse("input", input, err);
+  }
+
+private:
+  /// Parse a file, given its contents as a string.
+  bool Parse(const string& filename, const string& input, string* err);
+
+  bool ParseDyndepVersion(string* err);
+  bool ParseLet(string* key, EvalString* val, string* err);
+  bool ParseEdge(string* err);
+
+  DyndepFile* dyndep_file_;
+  BindingEnv env_;
+};
+
+#endif  // NINJA_DYNDEP_PARSER_H_
diff --git a/src/dyndep_parser_test.cc b/src/dyndep_parser_test.cc
new file mode 100644
index 0000000..39ec657
--- /dev/null
+++ b/src/dyndep_parser_test.cc
@@ -0,0 +1,512 @@
+// Copyright 2015 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "dyndep_parser.h"
+
+#include <map>
+#include <vector>
+
+#include "dyndep.h"
+#include "graph.h"
+#include "state.h"
+#include "test.h"
+
+struct DyndepParserTest : public testing::Test {
+  void AssertParse(const char* input) {
+    DyndepParser parser(&state_, &fs_, &dyndep_file_);
+    string err;
+    EXPECT_TRUE(parser.ParseTest(input, &err));
+    ASSERT_EQ("", err);
+  }
+
+  virtual void SetUp() {
+    ::AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"build out otherout: touch\n");
+  }
+
+  State state_;
+  VirtualFileSystem fs_;
+  DyndepFile dyndep_file_;
+};
+
+TEST_F(DyndepParserTest, Empty) {
+  const char kInput[] =
+"";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:1: expected 'ninja_dyndep_version = ...'\n", err);
+}
+
+TEST_F(DyndepParserTest, Version1) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"));
+}
+
+TEST_F(DyndepParserTest, Version1Extra) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1-extra\n"));
+}
+
+TEST_F(DyndepParserTest, Version1_0) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1.0\n"));
+}
+
+TEST_F(DyndepParserTest, Version1_0Extra) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1.0-extra\n"));
+}
+
+TEST_F(DyndepParserTest, CommentVersion) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"# comment\n"
+"ninja_dyndep_version = 1\n"));
+}
+
+TEST_F(DyndepParserTest, BlankLineVersion) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"\n"
+"ninja_dyndep_version = 1\n"));
+}
+
+TEST_F(DyndepParserTest, VersionCRLF) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\r\n"));
+}
+
+TEST_F(DyndepParserTest, CommentVersionCRLF) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"# comment\r\n"
+"ninja_dyndep_version = 1\r\n"));
+}
+
+TEST_F(DyndepParserTest, BlankLineVersionCRLF) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"\r\n"
+"ninja_dyndep_version = 1\r\n"));
+}
+
+TEST_F(DyndepParserTest, VersionUnexpectedEOF) {
+  const char kInput[] =
+"ninja_dyndep_version = 1.0";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:1: unexpected EOF\n"
+            "ninja_dyndep_version = 1.0\n"
+            "                          ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, UnsupportedVersion0) {
+  const char kInput[] =
+"ninja_dyndep_version = 0\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:1: unsupported 'ninja_dyndep_version = 0'\n"
+            "ninja_dyndep_version = 0\n"
+            "                        ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, UnsupportedVersion1_1) {
+  const char kInput[] =
+"ninja_dyndep_version = 1.1\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:1: unsupported 'ninja_dyndep_version = 1.1'\n"
+            "ninja_dyndep_version = 1.1\n"
+            "                          ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, DuplicateVersion) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"ninja_dyndep_version = 1\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: unexpected identifier\n", err);
+}
+
+TEST_F(DyndepParserTest, MissingVersionOtherVar) {
+  const char kInput[] =
+"not_ninja_dyndep_version = 1\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:1: expected 'ninja_dyndep_version = ...'\n"
+            "not_ninja_dyndep_version = 1\n"
+            "                            ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, MissingVersionBuild) {
+  const char kInput[] =
+"build out: dyndep\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:1: expected 'ninja_dyndep_version = ...'\n", err);
+}
+
+TEST_F(DyndepParserTest, UnexpectedEqual) {
+  const char kInput[] =
+"= 1\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:1: unexpected '='\n", err);
+}
+
+TEST_F(DyndepParserTest, UnexpectedIndent) {
+  const char kInput[] =
+" = 1\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:1: unexpected indent\n", err);
+}
+
+TEST_F(DyndepParserTest, OutDuplicate) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+"build out: dyndep\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:3: multiple statements for 'out'\n"
+            "build out: dyndep\n"
+            "         ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, OutDuplicateThroughOther) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+"build otherout: dyndep\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:3: multiple statements for 'otherout'\n"
+            "build otherout: dyndep\n"
+            "              ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, NoOutEOF) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: unexpected EOF\n"
+            "build\n"
+            "     ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, NoOutColon) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build :\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: expected path\n"
+            "build :\n"
+            "      ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, OutNoStatement) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build missing: dyndep\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: no build statement exists for 'missing'\n"
+            "build missing: dyndep\n"
+            "             ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, OutEOF) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: unexpected EOF\n"
+            "build out\n"
+            "         ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, OutNoRule) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out:";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: expected build command name 'dyndep'\n"
+            "build out:\n"
+            "          ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, OutBadRule) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out: touch";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: expected build command name 'dyndep'\n"
+            "build out: touch\n"
+            "           ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, BuildEOF) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out: dyndep";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: unexpected EOF\n"
+            "build out: dyndep\n"
+            "                 ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, ExplicitOut) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out exp: dyndep\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: explicit outputs not supported\n"
+            "build out exp: dyndep\n"
+            "             ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, ExplicitIn) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out: dyndep exp\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: explicit inputs not supported\n"
+            "build out: dyndep exp\n"
+            "                     ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, OrderOnlyIn) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out: dyndep ||\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:2: order-only inputs not supported\n"
+            "build out: dyndep ||\n"
+            "                  ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, BadBinding) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+"  not_restat = 1\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:3: binding is not 'restat'\n"
+            "  not_restat = 1\n"
+            "                ^ near here", err);
+}
+
+TEST_F(DyndepParserTest, RestatTwice) {
+  const char kInput[] =
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+"  restat = 1\n"
+"  restat = 1\n";
+  DyndepParser parser(&state_, &fs_, &dyndep_file_);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(kInput, &err));
+  EXPECT_EQ("input:4: unexpected indent\n", err);
+}
+
+TEST_F(DyndepParserTest, NoImplicit) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"));
+
+  EXPECT_EQ(1u, dyndep_file_.size());
+  DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+  ASSERT_NE(i, dyndep_file_.end());
+  EXPECT_EQ(false, i->second.restat_);
+  EXPECT_EQ(0u, i->second.implicit_outputs_.size());
+  EXPECT_EQ(0u, i->second.implicit_inputs_.size());
+}
+
+TEST_F(DyndepParserTest, EmptyImplicit) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build out | : dyndep |\n"));
+
+  EXPECT_EQ(1u, dyndep_file_.size());
+  DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+  ASSERT_NE(i, dyndep_file_.end());
+  EXPECT_EQ(false, i->second.restat_);
+  EXPECT_EQ(0u, i->second.implicit_outputs_.size());
+  EXPECT_EQ(0u, i->second.implicit_inputs_.size());
+}
+
+TEST_F(DyndepParserTest, ImplicitIn) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build out: dyndep | impin\n"));
+
+  EXPECT_EQ(1u, dyndep_file_.size());
+  DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+  ASSERT_NE(i, dyndep_file_.end());
+  EXPECT_EQ(false, i->second.restat_);
+  EXPECT_EQ(0u, i->second.implicit_outputs_.size());
+  ASSERT_EQ(1u, i->second.implicit_inputs_.size());
+  EXPECT_EQ("impin", i->second.implicit_inputs_[0]->path());
+}
+
+TEST_F(DyndepParserTest, ImplicitIns) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build out: dyndep | impin1 impin2\n"));
+
+  EXPECT_EQ(1u, dyndep_file_.size());
+  DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+  ASSERT_NE(i, dyndep_file_.end());
+  EXPECT_EQ(false, i->second.restat_);
+  EXPECT_EQ(0u, i->second.implicit_outputs_.size());
+  ASSERT_EQ(2u, i->second.implicit_inputs_.size());
+  EXPECT_EQ("impin1", i->second.implicit_inputs_[0]->path());
+  EXPECT_EQ("impin2", i->second.implicit_inputs_[1]->path());
+}
+
+TEST_F(DyndepParserTest, ImplicitOut) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build out | impout: dyndep\n"));
+
+  EXPECT_EQ(1u, dyndep_file_.size());
+  DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+  ASSERT_NE(i, dyndep_file_.end());
+  EXPECT_EQ(false, i->second.restat_);
+  ASSERT_EQ(1u, i->second.implicit_outputs_.size());
+  EXPECT_EQ("impout", i->second.implicit_outputs_[0]->path());
+  EXPECT_EQ(0u, i->second.implicit_inputs_.size());
+}
+
+TEST_F(DyndepParserTest, ImplicitOuts) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build out | impout1 impout2 : dyndep\n"));
+
+  EXPECT_EQ(1u, dyndep_file_.size());
+  DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+  ASSERT_NE(i, dyndep_file_.end());
+  EXPECT_EQ(false, i->second.restat_);
+  ASSERT_EQ(2u, i->second.implicit_outputs_.size());
+  EXPECT_EQ("impout1", i->second.implicit_outputs_[0]->path());
+  EXPECT_EQ("impout2", i->second.implicit_outputs_[1]->path());
+  EXPECT_EQ(0u, i->second.implicit_inputs_.size());
+}
+
+TEST_F(DyndepParserTest, ImplicitInsAndOuts) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build out | impout1 impout2: dyndep | impin1 impin2\n"));
+
+  EXPECT_EQ(1u, dyndep_file_.size());
+  DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+  ASSERT_NE(i, dyndep_file_.end());
+  EXPECT_EQ(false, i->second.restat_);
+  ASSERT_EQ(2u, i->second.implicit_outputs_.size());
+  EXPECT_EQ("impout1", i->second.implicit_outputs_[0]->path());
+  EXPECT_EQ("impout2", i->second.implicit_outputs_[1]->path());
+  ASSERT_EQ(2u, i->second.implicit_inputs_.size());
+  EXPECT_EQ("impin1", i->second.implicit_inputs_[0]->path());
+  EXPECT_EQ("impin2", i->second.implicit_inputs_[1]->path());
+}
+
+TEST_F(DyndepParserTest, Restat) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+"  restat = 1\n"));
+
+  EXPECT_EQ(1u, dyndep_file_.size());
+  DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+  ASSERT_NE(i, dyndep_file_.end());
+  EXPECT_EQ(true, i->second.restat_);
+  EXPECT_EQ(0u, i->second.implicit_outputs_.size());
+  EXPECT_EQ(0u, i->second.implicit_inputs_.size());
+}
+
+TEST_F(DyndepParserTest, OtherOutput) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build otherout: dyndep\n"));
+
+  EXPECT_EQ(1u, dyndep_file_.size());
+  DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+  ASSERT_NE(i, dyndep_file_.end());
+  EXPECT_EQ(false, i->second.restat_);
+  EXPECT_EQ(0u, i->second.implicit_outputs_.size());
+  EXPECT_EQ(0u, i->second.implicit_inputs_.size());
+}
+
+TEST_F(DyndepParserTest, MultipleEdges) {
+    ::AssertParse(&state_,
+"build out2: touch\n");
+  ASSERT_EQ(2u, state_.edges_.size());
+  ASSERT_EQ(1u, state_.edges_[1]->outputs_.size());
+  EXPECT_EQ("out2", state_.edges_[1]->outputs_[0]->path());
+  EXPECT_EQ(0u, state_.edges_[0]->inputs_.size());
+
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+"build out2: dyndep\n"
+"  restat = 1\n"));
+
+  EXPECT_EQ(2u, dyndep_file_.size());
+  {
+    DyndepFile::iterator i = dyndep_file_.find(state_.edges_[0]);
+    ASSERT_NE(i, dyndep_file_.end());
+    EXPECT_EQ(false, i->second.restat_);
+    EXPECT_EQ(0u, i->second.implicit_outputs_.size());
+    EXPECT_EQ(0u, i->second.implicit_inputs_.size());
+  }
+  {
+    DyndepFile::iterator i = dyndep_file_.find(state_.edges_[1]);
+    ASSERT_NE(i, dyndep_file_.end());
+    EXPECT_EQ(true, i->second.restat_);
+    EXPECT_EQ(0u, i->second.implicit_outputs_.size());
+    EXPECT_EQ(0u, i->second.implicit_inputs_.size());
+  }
+}
diff --git a/src/eval_env.cc b/src/eval_env.cc
index 8817a87..aa3d2b6 100644
--- a/src/eval_env.cc
+++ b/src/eval_env.cc
@@ -65,6 +65,7 @@ const EvalString* Rule::GetBinding(const string& key) const {
 bool Rule::IsReservedBinding(const string& var) {
   return var == "command" ||
       var == "depfile" ||
+      var == "dyndep" ||
       var == "description" ||
       var == "deps" ||
       var == "generator" ||
diff --git a/src/graph.cc b/src/graph.cc
index 9c2f784..add7868 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -68,6 +68,31 @@ bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
   edge->outputs_ready_ = true;
   edge->deps_missing_ = false;
 
+  if (!edge->deps_loaded_) {
+    // This is our first encounter with this edge.
+    // If there is a pending dyndep file, visit it now:
+    // * If the dyndep file is ready then load it now to get any
+    //   additional inputs and outputs for this and other edges.
+    //   Once the dyndep file is loaded it will no longer be pending
+    //   if any other edges encounter it, but they will already have
+    //   been updated.
+    // * If the dyndep file is not ready then since is known to be an
+    //   input to this edge, the edge will not be considered ready below.
+    //   Later during the build the dyndep file will become ready and be
+    //   loaded to update this edge before it can possibly be scheduled.
+    if (edge->dyndep_ && edge->dyndep_->dyndep_pending()) {
+      if (!RecomputeDirty(edge->dyndep_, stack, err))
+        return false;
+
+      if (!edge->dyndep_->in_edge() ||
+          edge->dyndep_->in_edge()->outputs_ready()) {
+        // The dyndep file is ready, so load it now.
+        if (!LoadDyndeps(edge->dyndep_, err))
+          return false;
+      }
+    }
+  }
+
   // Load output mtimes so we can compare them to the most recent input below.
   for (vector<Node*>::iterator o = edge->outputs_.begin();
        o != edge->outputs_.end(); ++o) {
@@ -75,12 +100,16 @@ bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
       return false;
   }
 
-  if (!dep_loader_.LoadDeps(edge, err)) {
-    if (!err->empty())
-      return false;
-    // Failed to load dependency info: rebuild to regenerate it.
-    // LoadDeps() did EXPLAIN() already, no need to do it here.
-    dirty = edge->deps_missing_ = true;
+  if (!edge->deps_loaded_) {
+    // This is our first encounter with this edge.  Load discovered deps.
+    edge->deps_loaded_ = true;
+    if (!dep_loader_.LoadDeps(edge, err)) {
+      if (!err->empty())
+        return false;
+      // Failed to load dependency info: rebuild to regenerate it.
+      // LoadDeps() did EXPLAIN() already, no need to do it here.
+      dirty = edge->deps_missing_ = true;
+    }
   }
 
   // Visit all inputs; we're dirty if any of the inputs are dirty.
@@ -272,6 +301,15 @@ bool DependencyScan::RecomputeOutputDirty(Edge* edge,
   return false;
 }
 
+bool DependencyScan::LoadDyndeps(Node* node, string* err) const {
+  return dyndep_loader_.LoadDyndeps(node, err);
+}
+
+bool DependencyScan::LoadDyndeps(Node* node, DyndepFile* ddf,
+                                 string* err) const {
+  return dyndep_loader_.LoadDyndeps(node, ddf, err);
+}
+
 bool Edge::AllInputsReady() const {
   for (vector<Node*>::const_iterator i = inputs_.begin();
        i != inputs_.end(); ++i) {
@@ -383,6 +421,11 @@ string Edge::GetUnescapedDepfile() {
   return env.LookupVariable("depfile");
 }
 
+string Edge::GetUnescapedDyndep() {
+  EdgeEnv env(this, EdgeEnv::kDoNotEscape);
+  return env.LookupVariable("dyndep");
+}
+
 string Edge::GetUnescapedRspfile() {
   EdgeEnv env(this, EdgeEnv::kDoNotEscape);
   return env.LookupVariable("rspfile");
diff --git a/src/graph.h b/src/graph.h
index d58fecd..75edbc5 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -19,6 +19,7 @@
 #include <vector>
 using namespace std;
 
+#include "dyndep.h"
 #include "eval_env.h"
 #include "timestamp.h"
 #include "util.h"
@@ -40,6 +41,7 @@ struct Node {
         slash_bits_(slash_bits),
         mtime_(-1),
         dirty_(false),
+        dyndep_pending_(false),
         in_edge_(NULL),
         id_(-1) {}
 
@@ -87,6 +89,9 @@ struct Node {
   void set_dirty(bool dirty) { dirty_ = dirty; }
   void MarkDirty() { dirty_ = true; }
 
+  bool dyndep_pending() const { return dyndep_pending_; }
+  void set_dyndep_pending(bool pending) { dyndep_pending_ = pending; }
+
   Edge* in_edge() const { return in_edge_; }
   void set_in_edge(Edge* edge) { in_edge_ = edge; }
 
@@ -116,6 +121,10 @@ private:
   /// edges to build.
   bool dirty_;
 
+  /// Store whether dyndep information is expected from this node but
+  /// has not yet been loaded.
+  bool dyndep_pending_;
+
   /// The Edge that produces this Node, or NULL when there is no
   /// known edge to produce it.
   Edge* in_edge_;
@@ -135,9 +144,10 @@ struct Edge {
     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) {}
+  Edge() : rule_(NULL), pool_(NULL), dyndep_(NULL), env_(NULL),
+           mark_(VisitNone), outputs_ready_(false), deps_loaded_(false),
+           deps_missing_(false), implicit_deps_(0), order_only_deps_(0),
+           implicit_outs_(0) {}
 
   /// Return true if all inputs' in-edges are ready.
   bool AllInputsReady() const;
@@ -153,6 +163,8 @@ struct Edge {
 
   /// Like GetBinding("depfile"), but without shell escaping.
   string GetUnescapedDepfile();
+  /// Like GetBinding("dyndep"), but without shell escaping.
+  string GetUnescapedDyndep();
   /// Like GetBinding("rspfile"), but without shell escaping.
   string GetUnescapedRspfile();
 
@@ -162,9 +174,11 @@ struct Edge {
   Pool* pool_;
   vector<Node*> inputs_;
   vector<Node*> outputs_;
+  Node* dyndep_;
   BindingEnv* env_;
   VisitMark mark_;
   bool outputs_ready_;
+  bool deps_loaded_;
   bool deps_missing_;
 
   const Rule& rule() const { return *rule_; }
@@ -257,7 +271,8 @@ struct DependencyScan {
                  DepfileParserOptions const* depfile_parser_options)
       : build_log_(build_log),
         disk_interface_(disk_interface),
-        dep_loader_(state, deps_log, disk_interface, depfile_parser_options) {}
+        dep_loader_(state, deps_log, disk_interface, depfile_parser_options),
+        dyndep_loader_(state, 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
@@ -282,6 +297,13 @@ struct DependencyScan {
     return dep_loader_.deps_log();
   }
 
+  /// Load a dyndep file from the given node's path and update the
+  /// build graph with the new information.  One overload accepts
+  /// a caller-owned 'DyndepFile' object in which to store the
+  /// information loaded from the dyndep file.
+  bool LoadDyndeps(Node* node, string* err) const;
+  bool LoadDyndeps(Node* node, DyndepFile* ddf, string* err) const;
+
  private:
   bool RecomputeDirty(Node* node, vector<Node*>* stack, string* err);
   bool VerifyDAG(Node* node, vector<Node*>* stack, string* err);
@@ -294,6 +316,7 @@ struct DependencyScan {
   BuildLog* build_log_;
   DiskInterface* disk_interface_;
   ImplicitDepLoader dep_loader_;
+  DyndepLoader dyndep_loader_;
 };
 
 #endif  // NINJA_GRAPH_H_
diff --git a/src/graph_test.cc b/src/graph_test.cc
index 4a66831..c8cca1c 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -479,3 +479,380 @@ TEST_F(GraphTest, Decanonicalize) {
   EXPECT_EQ(root_nodes[3]->PathDecanonicalized(), "out4\\foo");
 }
 #endif
+
+TEST_F(GraphTest, DyndepLoadTrivial) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out: r in || dd\n"
+"  dyndep = dd\n"
+  );
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+  );
+
+  string err;
+  ASSERT_TRUE(GetNode("dd")->dyndep_pending());
+  EXPECT_TRUE(scan_.LoadDyndeps(GetNode("dd"), &err));
+  EXPECT_EQ("", err);
+  EXPECT_FALSE(GetNode("dd")->dyndep_pending());
+
+  Edge* edge = GetNode("out")->in_edge();
+  ASSERT_EQ(1u, edge->outputs_.size());
+  EXPECT_EQ("out", edge->outputs_[0]->path());
+  ASSERT_EQ(2u, edge->inputs_.size());
+  EXPECT_EQ("in", edge->inputs_[0]->path());
+  EXPECT_EQ("dd", edge->inputs_[1]->path());
+  EXPECT_EQ(0u, edge->implicit_deps_);
+  EXPECT_EQ(1u, edge->order_only_deps_);
+  EXPECT_FALSE(edge->GetBindingBool("restat"));
+}
+
+TEST_F(GraphTest, DyndepLoadMissingFile) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out: r in || dd\n"
+"  dyndep = dd\n"
+  );
+
+  string err;
+  ASSERT_TRUE(GetNode("dd")->dyndep_pending());
+  EXPECT_FALSE(scan_.LoadDyndeps(GetNode("dd"), &err));
+  EXPECT_EQ("loading 'dd': No such file or directory", err);
+}
+
+TEST_F(GraphTest, DyndepLoadMissingEntry) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out: r in || dd\n"
+"  dyndep = dd\n"
+  );
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+  );
+
+  string err;
+  ASSERT_TRUE(GetNode("dd")->dyndep_pending());
+  EXPECT_FALSE(scan_.LoadDyndeps(GetNode("dd"), &err));
+  EXPECT_EQ("'out' not mentioned in its dyndep file 'dd'", err);
+}
+
+TEST_F(GraphTest, DyndepLoadExtraEntry) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out: r in || dd\n"
+"  dyndep = dd\n"
+"build out2: r in || dd\n"
+  );
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep\n"
+"build out2: dyndep\n"
+  );
+
+  string err;
+  ASSERT_TRUE(GetNode("dd")->dyndep_pending());
+  EXPECT_FALSE(scan_.LoadDyndeps(GetNode("dd"), &err));
+  EXPECT_EQ("dyndep file 'dd' mentions output 'out2' whose build statement "
+            "does not have a dyndep binding for the file", err);
+}
+
+TEST_F(GraphTest, DyndepLoadOutputWithMultipleRules1) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out1 | out-twice.imp: r in1\n"
+"build out2: r in2 || dd\n"
+"  dyndep = dd\n"
+  );
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out2 | out-twice.imp: dyndep\n"
+  );
+
+  string err;
+  ASSERT_TRUE(GetNode("dd")->dyndep_pending());
+  EXPECT_FALSE(scan_.LoadDyndeps(GetNode("dd"), &err));
+  EXPECT_EQ("multiple rules generate out-twice.imp", err);
+}
+
+TEST_F(GraphTest, DyndepLoadOutputWithMultipleRules2) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out1: r in1 || dd1\n"
+"  dyndep = dd1\n"
+"build out2: r in2 || dd2\n"
+"  dyndep = dd2\n"
+  );
+  fs_.Create("dd1",
+"ninja_dyndep_version = 1\n"
+"build out1 | out-twice.imp: dyndep\n"
+  );
+  fs_.Create("dd2",
+"ninja_dyndep_version = 1\n"
+"build out2 | out-twice.imp: dyndep\n"
+  );
+
+  string err;
+  ASSERT_TRUE(GetNode("dd1")->dyndep_pending());
+  EXPECT_TRUE(scan_.LoadDyndeps(GetNode("dd1"), &err));
+  EXPECT_EQ("", err);
+  ASSERT_TRUE(GetNode("dd2")->dyndep_pending());
+  EXPECT_FALSE(scan_.LoadDyndeps(GetNode("dd2"), &err));
+  EXPECT_EQ("multiple rules generate out-twice.imp", err);
+}
+
+TEST_F(GraphTest, DyndepLoadMultiple) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out1: r in1 || dd\n"
+"  dyndep = dd\n"
+"build out2: r in2 || dd\n"
+"  dyndep = dd\n"
+"build outNot: r in3 || dd\n"
+  );
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out1 | out1imp: dyndep | in1imp\n"
+"build out2: dyndep | in2imp\n"
+"  restat = 1\n"
+  );
+
+  string err;
+  ASSERT_TRUE(GetNode("dd")->dyndep_pending());
+  EXPECT_TRUE(scan_.LoadDyndeps(GetNode("dd"), &err));
+  EXPECT_EQ("", err);
+  EXPECT_FALSE(GetNode("dd")->dyndep_pending());
+
+  Edge* edge1 = GetNode("out1")->in_edge();
+  ASSERT_EQ(2u, edge1->outputs_.size());
+  EXPECT_EQ("out1", edge1->outputs_[0]->path());
+  EXPECT_EQ("out1imp", edge1->outputs_[1]->path());
+  EXPECT_EQ(1u, edge1->implicit_outs_);
+  ASSERT_EQ(3u, edge1->inputs_.size());
+  EXPECT_EQ("in1", edge1->inputs_[0]->path());
+  EXPECT_EQ("in1imp", edge1->inputs_[1]->path());
+  EXPECT_EQ("dd", edge1->inputs_[2]->path());
+  EXPECT_EQ(1u, edge1->implicit_deps_);
+  EXPECT_EQ(1u, edge1->order_only_deps_);
+  EXPECT_FALSE(edge1->GetBindingBool("restat"));
+  EXPECT_EQ(edge1, GetNode("out1imp")->in_edge());
+  Node* in1imp = GetNode("in1imp");
+  ASSERT_EQ(1u, in1imp->out_edges().size());
+  EXPECT_EQ(edge1, in1imp->out_edges()[0]);
+
+  Edge* edge2 = GetNode("out2")->in_edge();
+  ASSERT_EQ(1u, edge2->outputs_.size());
+  EXPECT_EQ("out2", edge2->outputs_[0]->path());
+  EXPECT_EQ(0u, edge2->implicit_outs_);
+  ASSERT_EQ(3u, edge2->inputs_.size());
+  EXPECT_EQ("in2", edge2->inputs_[0]->path());
+  EXPECT_EQ("in2imp", edge2->inputs_[1]->path());
+  EXPECT_EQ("dd", edge2->inputs_[2]->path());
+  EXPECT_EQ(1u, edge2->implicit_deps_);
+  EXPECT_EQ(1u, edge2->order_only_deps_);
+  EXPECT_TRUE(edge2->GetBindingBool("restat"));
+  Node* in2imp = GetNode("in2imp");
+  ASSERT_EQ(1u, in2imp->out_edges().size());
+  EXPECT_EQ(edge2, in2imp->out_edges()[0]);
+}
+
+TEST_F(GraphTest, DyndepFileMissing) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out: r || dd\n"
+"  dyndep = dd\n"
+  );
+
+  string err;
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("loading 'dd': No such file or directory", err);
+}
+
+TEST_F(GraphTest, DyndepFileError) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out: r || dd\n"
+"  dyndep = dd\n"
+  );
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+  );
+
+  string err;
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("'out' not mentioned in its dyndep file 'dd'", err);
+}
+
+TEST_F(GraphTest, DyndepImplicitInputNewer) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out: r || dd\n"
+"  dyndep = dd\n"
+  );
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep | in\n"
+  );
+  fs_.Create("out", "");
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  string err;
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_FALSE(GetNode("in")->dirty());
+  EXPECT_FALSE(GetNode("dd")->dirty());
+
+  // "out" is dirty due to dyndep-specified implicit input
+  EXPECT_TRUE(GetNode("out")->dirty());
+}
+
+TEST_F(GraphTest, DyndepFileReady) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build dd: r dd-in\n"
+"build out: r || dd\n"
+"  dyndep = dd\n"
+  );
+  fs_.Create("dd-in", "");
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep | in\n"
+  );
+  fs_.Create("out", "");
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  string err;
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_FALSE(GetNode("in")->dirty());
+  EXPECT_FALSE(GetNode("dd")->dirty());
+  EXPECT_TRUE(GetNode("dd")->in_edge()->outputs_ready());
+
+  // "out" is dirty due to dyndep-specified implicit input
+  EXPECT_TRUE(GetNode("out")->dirty());
+}
+
+TEST_F(GraphTest, DyndepFileNotClean) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build dd: r dd-in\n"
+"build out: r || dd\n"
+"  dyndep = dd\n"
+  );
+  fs_.Create("dd", "this-should-not-be-loaded");
+  fs_.Tick();
+  fs_.Create("dd-in", "");
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(GetNode("dd")->dirty());
+  EXPECT_FALSE(GetNode("dd")->in_edge()->outputs_ready());
+
+  // "out" is clean but not ready since "dd" is not ready
+  EXPECT_FALSE(GetNode("out")->dirty());
+  EXPECT_FALSE(GetNode("out")->in_edge()->outputs_ready());
+}
+
+TEST_F(GraphTest, DyndepFileNotReady) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build tmp: r\n"
+"build dd: r dd-in || tmp\n"
+"build out: r || dd\n"
+"  dyndep = dd\n"
+  );
+  fs_.Create("dd", "this-should-not-be-loaded");
+  fs_.Create("dd-in", "");
+  fs_.Tick();
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_FALSE(GetNode("dd")->dirty());
+  EXPECT_FALSE(GetNode("dd")->in_edge()->outputs_ready());
+  EXPECT_FALSE(GetNode("out")->dirty());
+  EXPECT_FALSE(GetNode("out")->in_edge()->outputs_ready());
+}
+
+TEST_F(GraphTest, DyndepFileSecondNotReady) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build dd1: r dd1-in\n"
+"build dd2-in: r || dd1\n"
+"  dyndep = dd1\n"
+"build dd2: r dd2-in\n"
+"build out: r || dd2\n"
+"  dyndep = dd2\n"
+  );
+  fs_.Create("dd1", "");
+  fs_.Create("dd2", "");
+  fs_.Create("dd2-in", "");
+  fs_.Tick();
+  fs_.Create("dd1-in", "");
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(GetNode("dd1")->dirty());
+  EXPECT_FALSE(GetNode("dd1")->in_edge()->outputs_ready());
+  EXPECT_FALSE(GetNode("dd2")->dirty());
+  EXPECT_FALSE(GetNode("dd2")->in_edge()->outputs_ready());
+  EXPECT_FALSE(GetNode("out")->dirty());
+  EXPECT_FALSE(GetNode("out")->in_edge()->outputs_ready());
+}
+
+TEST_F(GraphTest, DyndepFileCircular) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out: r in || dd\n"
+"  depfile = out.d\n"
+"  dyndep = dd\n"
+"build in: r circ\n"
+  );
+  fs_.Create("out.d", "out: inimp\n");
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out | circ: dyndep\n"
+  );
+  fs_.Create("out", "");
+
+  Edge* edge = GetNode("out")->in_edge();
+  string err;
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_EQ("dependency cycle: circ -> in -> circ", err);
+
+  // Verify that "out.d" was loaded exactly once despite
+  // circular reference discovered from dyndep file.
+  ASSERT_EQ(3u, edge->inputs_.size());
+  EXPECT_EQ("in", edge->inputs_[0]->path());
+  EXPECT_EQ("inimp", edge->inputs_[1]->path());
+  EXPECT_EQ("dd", edge->inputs_[2]->path());
+  EXPECT_EQ(1u, edge->implicit_deps_);
+  EXPECT_EQ(1u, edge->order_only_deps_);
+}
diff --git a/src/graphviz.cc b/src/graphviz.cc
index dce8b32..0d07251 100644
--- a/src/graphviz.cc
+++ b/src/graphviz.cc
@@ -17,6 +17,7 @@
 #include <stdio.h>
 #include <algorithm>
 
+#include "dyndep.h"
 #include "graph.h"
 
 void GraphViz::AddTarget(Node* node) {
@@ -40,6 +41,13 @@ void GraphViz::AddTarget(Node* node) {
     return;
   visited_edges_.insert(edge);
 
+  if (edge->dyndep_ && edge->dyndep_->dyndep_pending()) {
+    std::string err;
+    if (!dyndep_loader_.LoadDyndeps(edge->dyndep_, &err)) {
+      Warning("%s\n", err.c_str());
+    }
+  }
+
   if (edge->inputs_.size() == 1 && edge->outputs_.size() == 1) {
     // Can draw simply.
     // Note extra space before label text -- this is cosmetic and feels
diff --git a/src/graphviz.h b/src/graphviz.h
index 408496d..601c9b2 100644
--- a/src/graphviz.h
+++ b/src/graphviz.h
@@ -17,15 +17,22 @@
 
 #include <set>
 
+#include "dyndep.h"
+
+struct DiskInterface;
 struct Node;
 struct Edge;
+struct State;
 
 /// Runs the process of creating GraphViz .dot file output.
 struct GraphViz {
+  GraphViz(State* state, DiskInterface* disk_interface)
+      : dyndep_loader_(state, disk_interface) {}
   void Start();
   void AddTarget(Node* node);
   void Finish();
 
+  DyndepLoader dyndep_loader_;
   std::set<Node*> visited_nodes_;
   std::set<Edge*> visited_edges_;
 };
diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc
index 27c423b..2011368 100644
--- a/src/manifest_parser.cc
+++ b/src/manifest_parser.cc
@@ -18,41 +18,18 @@
 #include <stdlib.h>
 #include <vector>
 
-#include "disk_interface.h"
 #include "graph.h"
-#include "metrics.h"
 #include "state.h"
 #include "util.h"
 #include "version.h"
 
 ManifestParser::ManifestParser(State* state, FileReader* file_reader,
                                ManifestParserOptions options)
-    : state_(state), file_reader_(file_reader),
+    : Parser(state, file_reader),
       options_(options), quiet_(false) {
   env_ = &state->bindings_;
 }
 
-bool ManifestParser::Load(const string& filename, string* err, Lexer* parent) {
-  METRIC_RECORD(".ninja parse");
-  string contents;
-  string read_err;
-  if (file_reader_->ReadFile(filename, &contents, &read_err) != FileReader::Okay) {
-    *err = "loading '" + filename + "': " + read_err;
-    if (parent)
-      parent->Error(string(*err), err);
-    return false;
-  }
-
-  // The lexer needs a nul byte at the end of its input, to know when it's done.
-  // It takes a StringPiece, and StringPiece's string constructor uses
-  // string::data().  data()'s return value isn't guaranteed to be
-  // null-terminated (although in practice - libc++, libstdc++, msvc's stl --
-  // it is, and C++11 demands that too), so add an explicit nul byte.
-  contents.resize(contents.size() + 1);
-
-  return Parse(filename, contents, err);
-}
-
 bool ManifestParser::Parse(const string& filename, const string& input,
                            string* err) {
   lexer_.Start(filename, input);
@@ -410,6 +387,23 @@ bool ManifestParser::ParseEdge(string* err) {
                         err);
   }
 
+  // Lookup, validate, and save any dyndep binding.  It will be used later
+  // to load generated dependency information dynamically, but it must
+  // be one of our manifest-specified inputs.
+  string dyndep = edge->GetUnescapedDyndep();
+  if (!dyndep.empty()) {
+    uint64_t slash_bits;
+    if (!CanonicalizePath(&dyndep, &slash_bits, err))
+      return false;
+    edge->dyndep_ = state_->GetNode(dyndep, slash_bits);
+    edge->dyndep_->set_dyndep_pending(true);
+    vector<Node*>::iterator dgi =
+      std::find(edge->inputs_.begin(), edge->inputs_.end(), edge->dyndep_);
+    if (dgi == edge->inputs_.end()) {
+      return lexer_.Error("dyndep '" + dyndep + "' is not an input", err);
+    }
+  }
+
   return true;
 }
 
@@ -434,14 +428,3 @@ bool ManifestParser::ParseFileInclude(bool new_scope, string* err) {
 
   return true;
 }
-
-bool ManifestParser::ExpectToken(Lexer::Token expected, string* err) {
-  Lexer::Token token = lexer_.ReadToken();
-  if (token != expected) {
-    string message = string("expected ") + Lexer::TokenName(expected);
-    message += string(", got ") + Lexer::TokenName(token);
-    message += Lexer::TokenErrorHint(expected);
-    return lexer_.Error(message, err);
-  }
-  return true;
-}
diff --git a/src/manifest_parser.h b/src/manifest_parser.h
index 2136018..e14d069 100644
--- a/src/manifest_parser.h
+++ b/src/manifest_parser.h
@@ -15,16 +15,10 @@
 #ifndef NINJA_MANIFEST_PARSER_H_
 #define NINJA_MANIFEST_PARSER_H_
 
-#include <string>
-
-using namespace std;
-
-#include "lexer.h"
+#include "parser.h"
 
 struct BindingEnv;
 struct EvalString;
-struct FileReader;
-struct State;
 
 enum DupeEdgeAction {
   kDupeEdgeActionWarn,
@@ -45,13 +39,10 @@ struct ManifestParserOptions {
 };
 
 /// Parses .ninja files.
-struct ManifestParser {
+struct ManifestParser : public Parser {
   ManifestParser(State* state, FileReader* file_reader,
                  ManifestParserOptions options = ManifestParserOptions());
 
-  /// Load and parse a file.
-  bool Load(const string& filename, string* err, Lexer* parent = NULL);
-
   /// Parse a text string of input.  Used by tests.
   bool ParseTest(const string& input, string* err) {
     quiet_ = true;
@@ -72,14 +63,7 @@ private:
   /// Parse either a 'subninja' or 'include' line.
   bool ParseFileInclude(bool new_scope, string* err);
 
-  /// If the next token is not \a expected, produce an error string
-  /// saying "expectd foo, got bar".
-  bool ExpectToken(Lexer::Token expected, string* err);
-
-  State* state_;
   BindingEnv* env_;
-  FileReader* file_reader_;
-  Lexer lexer_;
   ManifestParserOptions options_;
   bool quiet_;
 };
diff --git a/src/manifest_parser_test.cc b/src/manifest_parser_test.cc
index c91d8d1..f2b7467 100644
--- a/src/manifest_parser_test.cc
+++ b/src/manifest_parser_test.cc
@@ -1085,3 +1085,73 @@ TEST_F(ParserTest, CRLF) {
       "  description = YAY!\r\n",
       &err));
 }
+
+TEST_F(ParserTest, DyndepNotSpecified) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"rule cat\n"
+"  command = cat $in > $out\n"
+"build result: cat in\n"));
+  Edge* edge = state.GetNode("result", 0)->in_edge();
+  ASSERT_FALSE(edge->dyndep_);
+}
+
+TEST_F(ParserTest, DyndepNotInput) {
+  State lstate;
+  ManifestParser parser(&lstate, NULL);
+  string err;
+  EXPECT_FALSE(parser.ParseTest(
+"rule touch\n"
+"  command = touch $out\n"
+"build result: touch\n"
+"  dyndep = notin\n",
+                               &err));
+  EXPECT_EQ("input:5: dyndep 'notin' is not an input\n", err);
+}
+
+TEST_F(ParserTest, DyndepExplicitInput) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"rule cat\n"
+"  command = cat $in > $out\n"
+"build result: cat in\n"
+"  dyndep = in\n"));
+  Edge* edge = state.GetNode("result", 0)->in_edge();
+  ASSERT_TRUE(edge->dyndep_);
+  EXPECT_TRUE(edge->dyndep_->dyndep_pending());
+  EXPECT_EQ(edge->dyndep_->path(), "in");
+}
+
+TEST_F(ParserTest, DyndepImplicitInput) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"rule cat\n"
+"  command = cat $in > $out\n"
+"build result: cat in | dd\n"
+"  dyndep = dd\n"));
+  Edge* edge = state.GetNode("result", 0)->in_edge();
+  ASSERT_TRUE(edge->dyndep_);
+  EXPECT_TRUE(edge->dyndep_->dyndep_pending());
+  EXPECT_EQ(edge->dyndep_->path(), "dd");
+}
+
+TEST_F(ParserTest, DyndepOrderOnlyInput) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"rule cat\n"
+"  command = cat $in > $out\n"
+"build result: cat in || dd\n"
+"  dyndep = dd\n"));
+  Edge* edge = state.GetNode("result", 0)->in_edge();
+  ASSERT_TRUE(edge->dyndep_);
+  EXPECT_TRUE(edge->dyndep_->dyndep_pending());
+  EXPECT_EQ(edge->dyndep_->path(), "dd");
+}
+
+TEST_F(ParserTest, DyndepRuleInput) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"rule cat\n"
+"  command = cat $in > $out\n"
+"  dyndep = $in\n"
+"build result: cat in\n"));
+  Edge* edge = state.GetNode("result", 0)->in_edge();
+  ASSERT_TRUE(edge->dyndep_);
+  EXPECT_TRUE(edge->dyndep_->dyndep_pending());
+  EXPECT_EQ(edge->dyndep_->path(), "in");
+}
diff --git a/src/ninja.cc b/src/ninja.cc
index b608426..5f19a65 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -338,7 +338,7 @@ int NinjaMain::ToolGraph(const Options* options, int argc, char* argv[]) {
     return 1;
   }
 
-  GraphViz graph;
+  GraphViz graph(&state_, &disk_interface_);
   graph.Start();
   for (vector<Node*>::const_iterator n = nodes.begin(); n != nodes.end(); ++n)
     graph.AddTarget(*n);
@@ -353,6 +353,8 @@ int NinjaMain::ToolQuery(const Options* options, int argc, char* argv[]) {
     return 1;
   }
 
+  DyndepLoader dyndep_loader(&state_, &disk_interface_);
+
   for (int i = 0; i < argc; ++i) {
     string err;
     Node* node = CollectTarget(argv[i], &err);
@@ -363,6 +365,11 @@ int NinjaMain::ToolQuery(const Options* options, int argc, char* argv[]) {
 
     printf("%s:\n", node->path().c_str());
     if (Edge* edge = node->in_edge()) {
+      if (edge->dyndep_ && edge->dyndep_->dyndep_pending()) {
+        if (!dyndep_loader.LoadDyndeps(edge->dyndep_, &err)) {
+          Warning("%s\n", err.c_str());
+        }
+      }
       printf("  input: %s\n", edge->rule_->name().c_str());
       for (int in = 0; in < (int)edge->inputs_.size(); in++) {
         const char* label = "";
@@ -651,7 +658,7 @@ int NinjaMain::ToolClean(const Options* options, int argc, char* argv[]) {
     return 1;
   }
 
-  Cleaner cleaner(&state_, config_);
+  Cleaner cleaner(&state_, config_, &disk_interface_);
   if (argc >= 1) {
     if (clean_rules)
       return cleaner.CleanRules(argc, argv);
diff --git a/src/parser.cc b/src/parser.cc
new file mode 100644
index 0000000..745c532
--- /dev/null
+++ b/src/parser.cc
@@ -0,0 +1,51 @@
+// Copyright 2018 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "parser.h"
+
+#include "disk_interface.h"
+#include "metrics.h"
+
+bool Parser::Load(const string& filename, string* err, Lexer* parent) {
+  METRIC_RECORD(".ninja parse");
+  string contents;
+  string read_err;
+  if (file_reader_->ReadFile(filename, &contents, &read_err) !=
+      FileReader::Okay) {
+    *err = "loading '" + filename + "': " + read_err;
+    if (parent)
+      parent->Error(string(*err), err);
+    return false;
+  }
+
+  // The lexer needs a nul byte at the end of its input, to know when it's done.
+  // It takes a StringPiece, and StringPiece's string constructor uses
+  // string::data().  data()'s return value isn't guaranteed to be
+  // null-terminated (although in practice - libc++, libstdc++, msvc's stl --
+  // it is, and C++11 demands that too), so add an explicit nul byte.
+  contents.resize(contents.size() + 1);
+
+  return Parse(filename, contents, err);
+}
+
+bool Parser::ExpectToken(Lexer::Token expected, string* err) {
+  Lexer::Token token = lexer_.ReadToken();
+  if (token != expected) {
+    string message = string("expected ") + Lexer::TokenName(expected);
+    message += string(", got ") + Lexer::TokenName(token);
+    message += Lexer::TokenErrorHint(expected);
+    return lexer_.Error(message, err);
+  }
+  return true;
+}
diff --git a/src/parser.h b/src/parser.h
new file mode 100644
index 0000000..e2d2b97
--- /dev/null
+++ b/src/parser.h
@@ -0,0 +1,50 @@
+// Copyright 2018 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef NINJA_PARSER_H_
+#define NINJA_PARSER_H_
+
+#include <string>
+
+using namespace std;
+
+#include "lexer.h"
+
+struct FileReader;
+struct State;
+
+/// Base class for parsers.
+struct Parser {
+  Parser(State* state, FileReader* file_reader)
+      : state_(state), file_reader_(file_reader) {}
+
+  /// Load and parse a file.
+  bool Load(const string& filename, string* err, Lexer* parent = NULL);
+
+protected:
+  /// If the next token is not \a expected, produce an error string
+  /// saying "expected foo, got bar".
+  bool ExpectToken(Lexer::Token expected, string* err);
+
+  State* state_;
+  FileReader* file_reader_;
+  Lexer lexer_;
+
+private:
+  /// Parse a file, given its contents as a string.
+  virtual bool Parse(const string& filename, const string& input,
+                     string* err) = 0;
+};
+
+#endif  // NINJA_PARSER_H_
diff --git a/src/state.cc b/src/state.cc
index 9b3c7e1..74cf4c1 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -186,6 +186,7 @@ void State::Reset() {
     i->second->ResetState();
   for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) {
     (*e)->outputs_ready_ = false;
+    (*e)->deps_loaded_ = false;
     (*e)->mark_ = Edge::VisitNone;
   }
 }