Teach builder to load dyndep files when they are ready

After finishing an edge that produces a dyndep file, load the file and
update the build graph structure.  Recompute the dirty state of all its
dependents and of newly reachable portions of the graph.  Add edges to
the build plan that are discovered to be wanted.  Finally, schedule
edges that are wanted and now ready to build.

1 files changed, 717 insertions, 0 deletions

diff --git a/src/build_test.cc b/src/build_test.cc
index 0ca7c3d..b5dbc6c 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -594,6 +594,14 @@ 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;
@@ -2360,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]);
+}