Add a parser for a new "dyndep" file format

Define a file format suitable for specifying dynamically-discovered
dependency information for build edges.  Design a format inspired by the
build manifest format and using the same lexer.  Start with a required
format version specification followed by "build" statements that add
implicit inputs and outputs to existing edges.

5 files changed, 821 insertions, 0 deletions

diff --git a/configure.py b/configure.py
index 6aece3f..b56ef89 100755
--- a/configure.py
+++ b/configure.py
@@ -496,6 +496,7 @@ for name in ['build',
              'depfile_parser',
              'deps_log',
              'disk_interface',
+             'dyndep_parser',
              'edit_distance',
              'eval_env',
              'graph',
@@ -564,6 +565,7 @@ for name in ['build_log_test',
              'clparser_test',
              'depfile_parser_test',
              'deps_log_test',
+             'dyndep_parser_test',
              'disk_interface_test',
              'edit_distance_test',
              'graph_test',
diff --git a/src/dyndep.h b/src/dyndep.h
new file mode 100644
index 0000000..80c5d1b
--- /dev/null
+++ b/src/dyndep.h
@@ -0,0 +1,38 @@
+// 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 <vector>
+
+struct Edge;
+struct Node;
+
+/// Store dynamically-discovered dependency information for one edge.
+struct Dyndeps {
+  Dyndeps() : restat_(false) {}
+  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> {};
+
+#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());
+  }
+}