Add validation nodes to ninja

A common problem in the Android build is inserting rules that perform
some sort of error checking that doesn't produce any artifacts needed
by the build, for example static analysis tools.  There are a few
patterns currently used, both of which have downsides.

The first is to have a rule that depends on all of the static analysis
results.  This ensures they run, but requires running static analysis
over everything, and not just the active parts of the build graph.

The second is to insert the static analysis rule into the build graph
between the artifact producing rule and anything that depends on it,
often copying the artifact as the output of the static analysis rule.
This increases the critical path of the build, often reducing
parallelism.  In the case of copying the artifact, it also wastes
disk space.

This patch adds "validation nodes" to edges in Ninja.  A build
statement can specify validation nodes using "|@" in the edge
inputs.  The validation nodes are not used as an input to the edge
(the edge can run before the validation node is ready), but are
added to the initial nodes of the build graph whenever the edge
is part of the build graph.  The edge that outputs the validation
node can depend on the output of the edge that is being validated
if desired.

Test: ninja_test
Change-Id: Ife27086c50c1b257a26509373199664680b2b247

16 files changed, 663 insertions, 160 deletions

diff --git a/doc/manual.asciidoc b/doc/manual.asciidoc
index 2b948b9..bdfa99b 100644
--- a/doc/manual.asciidoc
+++ b/doc/manual.asciidoc
@@ -748,6 +748,8 @@ A file is a series of declarations.  A declaration can be one of:
    Order-only dependencies may be tacked on the end with +||
    _dependency1_ _dependency2_+.  (See <<ref_dependencies,the reference on
    dependency types>>.)
+   Validations may be taked on the end with +|@ _validation1_ _validation2_+.
+   (See <<validations,the reference on validations>>.)
 +
 Implicit outputs _(available since Ninja 1.7)_ may be added before
 the `:` with +| _output1_ _output2_+ and do not appear in `$out`.
@@ -1006,6 +1008,31 @@ express the implicit dependency.)
 File paths are compared as is, which means that an absolute path and a
 relative path, pointing to the same file, are considered different by Ninja.
 
+[[validations]]
+Validations
+~~~~~~~~~~~
+Validations listed on the build line cause the specified files to be
+added to the top level of the build graph (as if they were specified
+on the Ninja command line) whenever the build line is a transitive
+dependency of one of the targets specified on the command line or a
+default target.
+
+Validations are added to the build graph regardless of whether the output
+files of the build statement are dirty are not, and the dirty state of
+the build statement that outputs the file being used as a validation
+has no effect on the dirty state of the build statement that requested it.
+
+A build edge can list another build edge as a validation even if the second
+edge depends on the first.
+
+Validations are designed to handle rules that perform error checking but
+don't produce any artifacts needed by the build, for example static
+analysis tools.  Marking the static analysis rule as an implicit input
+of the main build rule of the source files or of the rules that depend
+on the main build rule would slow down the critical path of the build,
+but using a validation would allow the build to proceed in parallel with
+the static analysis rule once the main build rule is complete.
+
 Variable expansion
 ~~~~~~~~~~~~~~~~~~
 
diff --git a/src/build.cc b/src/build.cc
index 735922b..6f11ed7 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -384,8 +384,21 @@ bool Plan::RefreshDyndepDependents(DependencyScan* scan, const Node* node,
     Node* n = *i;
 
     // Check if this dependent node is now dirty.  Also checks for new cycles.
-    if (!scan->RecomputeDirty(n, err))
+    std::vector<Node*> validation_nodes;
+    if (!scan->RecomputeDirty(n, &validation_nodes, err))
       return false;
+
+    // Add any validation nodes found during RecomputeDirty as new top level
+    // targets.
+    for (std::vector<Node*>::iterator v = validation_nodes.begin();
+         v != validation_nodes.end(); ++v) {
+      if (Edge* in_edge = (*v)->in_edge()) {
+        if (!in_edge->outputs_ready() &&
+            !AddTarget(*v, err)) {
+          return false;
+        }
+      }
+    }
     if (!n->dirty())
       continue;
 
@@ -553,7 +566,8 @@ Node* Builder::AddTarget(const string& name, string* err) {
 }
 
 bool Builder::AddTarget(Node* target, string* err) {
-  if (!scan_.RecomputeDirty(target, err))
+  std::vector<Node*> validation_nodes;
+  if (!scan_.RecomputeDirty(target, &validation_nodes, err))
     return false;
 
   Edge* in_edge = target->in_edge();
@@ -563,6 +577,17 @@ bool Builder::AddTarget(Node* target, string* err) {
     }
   }
 
+  // Also add any validation nodes found during RecomputeDirty as top level
+  // targets.
+  for (std::vector<Node*>::iterator n = validation_nodes.begin();
+       n != validation_nodes.end(); ++n) {
+    if (Edge* validation_in_edge = (*n)->in_edge()) {
+      if (!validation_in_edge->outputs_ready() &&
+          !plan_.AddTarget(*n, err)) {
+        return false;
+      }
+    }
+  }
 
   return true;
 }
diff --git a/src/build_test.cc b/src/build_test.cc
index 8da4698..36b723a 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -3236,6 +3236,67 @@ TEST_F(BuildTest, DyndepBuildDiscoverNewInput) {
   EXPECT_EQ("touch out", command_runner_.commands_ran_[2]);
 }
 
+TEST_F(BuildTest, DyndepBuildDiscoverNewInputWithValidation) {
+  // Verify that a dyndep file cannot contain the |@ validation
+  // syntax.
+  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 |@ validation\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_FALSE(builder_.Build(&err));
+
+  string err_first_line = err.substr(0, err.find("\n"));
+  EXPECT_EQ("dd:2: expected newline, got '|@'", err_first_line);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverNewInputWithTransitiveValidation) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // a new input to an edge that has a validation 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 |@ validation\n"
+"build validation: touch in out\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(4u, 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]);
+  EXPECT_EQ("touch validation", command_runner_.commands_ran_[3]);
+}
+
 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
@@ -3679,3 +3740,247 @@ TEST_F(BuildTest, DyndepTwoLevelDiscoveredDirty) {
   EXPECT_EQ("touch tmp", command_runner_.commands_ran_[3]);
   EXPECT_EQ("touch out", command_runner_.commands_ran_[4]);
 }
+
+TEST_F(BuildTest, Validation) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ validate\n"
+    "build validate: cat in2\n"));
+
+  fs_.Create("in", "");
+  fs_.Create("in2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in" only rebuilds "out" ("validate" doesn't depend on
+  // "out").
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in > out", command_runner_.commands_ran_[0]);
+
+  // Test touching "in2" only rebuilds "validate" ("out" doesn't depend on
+  // "validate").
+  fs_.Tick();
+  fs_.Create("in2", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in2 > validate", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildTest, ValidationDependsOnOutput) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ validate\n"
+    "build validate: cat in2 | out\n"));
+
+  fs_.Create("in", "");
+  fs_.Create("in2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in" rebuilds "out" and "validate".
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in2" only rebuilds "validate" ("out" doesn't depend on
+  // "validate").
+  fs_.Tick();
+  fs_.Create("in2", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in2 > validate", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildWithDepsLogTest, ValidationThroughDepfile) {
+  const char* manifest =
+      "build out: cat in |@ validate\n"
+      "build validate: cat in2 | out\n"
+      "build out2: cat in3\n"
+      "  deps = gcc\n"
+      "  depfile = out2.d\n";
+
+  string err;
+
+  {
+    fs_.Create("in", "");
+    fs_.Create("in2", "");
+    fs_.Create("in3", "");
+    fs_.Create("out2.d", "out: out");
+
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
+    builder.command_runner_.reset(&command_runner_);
+
+    EXPECT_TRUE(builder.AddTarget("out2", &err));
+    ASSERT_EQ("", err);
+
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    // On the first build, only the out2 command is run.
+    ASSERT_EQ(command_runner_.commands_ran_.size(), 1);
+    EXPECT_EQ("cat in3 > out2", command_runner_.commands_ran_[0]);
+
+    // The deps file should have been removed.
+    EXPECT_EQ(0, fs_.Stat("out2.d", &err));
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+
+  fs_.Tick();
+  command_runner_.commands_ran_.clear();
+
+  {
+    fs_.Create("in2", "");
+    fs_.Create("in3", "");
+
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.Load("ninja_deps", &state, &err));
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
+    builder.command_runner_.reset(&command_runner_);
+
+    EXPECT_TRUE(builder.AddTarget("out2", &err));
+    ASSERT_EQ("", err);
+
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    // The out and validate actions should have been run as well as out2.
+    ASSERT_EQ(command_runner_.commands_ran_.size(), 3);
+    // out has to run first, as both out2 and validate depend on it.
+    EXPECT_EQ("cat in > out", command_runner_.commands_ran_[0]);
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+}
+
+TEST_F(BuildTest, ValidationCircular) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ out2\n"
+    "build out2: cat in2 |@ out\n"));
+
+  fs_.Create("in", "");
+  fs_.Create("in2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in" rebuilds "out".
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in > out", command_runner_.commands_ran_[0]);
+
+  // Test touching "in2" rebuilds "out2".
+  fs_.Tick();
+  fs_.Create("in2", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in2 > out2", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildTest, ValidationWithCircularDependency) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ validate\n"
+    "build validate: cat validate_in | out\n"
+    "build validate_in: cat validate\n"));
+
+  fs_.Create("in", "");
+
+  string err;
+  EXPECT_FALSE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("dependency cycle: validate -> validate_in -> validate", err);
+}
diff --git a/src/depfile_parser.cc b/src/depfile_parser.cc
index bffeb76..2eca108 100644
--- a/src/depfile_parser.cc
+++ b/src/depfile_parser.cc
@@ -1,4 +1,4 @@
-/* Generated by re2c 1.3 */
+/* Generated by re2c 2.2 */
 // Copyright 2011 Google Inc. All Rights Reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
diff --git a/src/disk_interface_test.cc b/src/disk_interface_test.cc
index 339aea1..5e952ed 100644
--- a/src/disk_interface_test.cc
+++ b/src/disk_interface_test.cc
@@ -272,7 +272,7 @@ TEST_F(StatTest, Simple) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_EQ(2u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_EQ("in",  stats_[1]);
@@ -288,7 +288,7 @@ TEST_F(StatTest, TwoStep) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_EQ(3u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_TRUE(GetNode("out")->dirty());
@@ -308,7 +308,7 @@ TEST_F(StatTest, Tree) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_EQ(1u + 6u, stats_.size());
   ASSERT_EQ("mid1", stats_[1]);
   ASSERT_TRUE(GetNode("mid1")->dirty());
@@ -329,7 +329,7 @@ TEST_F(StatTest, Middle) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_FALSE(GetNode("in")->dirty());
   ASSERT_TRUE(GetNode("mid")->dirty());
   ASSERT_TRUE(GetNode("out")->dirty());
diff --git a/src/graph.cc b/src/graph.cc
index c875d3b..8d58587 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -15,6 +15,7 @@
 #include "graph.h"
 
 #include <algorithm>
+#include <deque>
 #include <assert.h>
 #include <stdio.h>
 
@@ -46,13 +47,42 @@ void Node::UpdatePhonyMtime(TimeStamp mtime) {
   }
 }
 
-bool DependencyScan::RecomputeDirty(Node* node, string* err) {
-  vector<Node*> stack;
-  return RecomputeDirty(node, &stack, err);
+bool DependencyScan::RecomputeDirty(Node* initial_node,
+                                    std::vector<Node*>* validation_nodes,
+                                    string* err) {
+  std::vector<Node*> stack;
+  std::vector<Node*> new_validation_nodes;
+
+  std::deque<Node*> nodes(1, initial_node);
+
+  // RecomputeNodeDirty might return new validation nodes that need to be
+  // checked for dirty state, keep a queue of nodes to visit.
+  while (!nodes.empty()) {
+    Node* node = nodes.front();
+    nodes.pop_front();
+
+    stack.clear();
+    new_validation_nodes.clear();
+
+    if (!RecomputeNodeDirty(node, &stack, &new_validation_nodes, err))
+      return false;
+    nodes.insert(nodes.end(), new_validation_nodes.begin(),
+                              new_validation_nodes.end());
+    if (!new_validation_nodes.empty()) {
+      assert(validation_nodes &&
+          "validations require RecomputeDirty to be called with validation_nodes");
+      validation_nodes->insert(validation_nodes->end(),
+                           new_validation_nodes.begin(),
+                           new_validation_nodes.end());
+    }
+  }
+
+  return true;
 }
 
-bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
-                                    string* err) {
+bool DependencyScan::RecomputeNodeDirty(Node* node, std::vector<Node*>* stack,
+                                        std::vector<Node*>* validation_nodes,
+                                        string* err) {
   Edge* edge = node->in_edge();
   if (!edge) {
     // If we already visited this leaf node then we are done.
@@ -96,7 +126,7 @@ bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
     //   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))
+      if (!RecomputeNodeDirty(edge->dyndep_, stack, validation_nodes, err))
         return false;
 
       if (!edge->dyndep_->in_edge() ||
@@ -127,12 +157,20 @@ bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
     }
   }
 
+  // Store any validation nodes from the edge for adding to the initial
+  // nodes.  Don't recurse into them, that would trigger the dependency
+  // cycle detector if the validation node depends on this node.
+  // RecomputeDirty will add the validation nodes to the initial nodes
+  // and recurse into them.
+  validation_nodes->insert(validation_nodes->end(),
+      edge->validations_.begin(), edge->validations_.end());
+
   // Visit all inputs; we're dirty if any of the inputs are dirty.
   Node* most_recent_input = NULL;
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
     // Visit this input.
-    if (!RecomputeDirty(*i, stack, err))
+    if (!RecomputeNodeDirty(*i, stack, validation_nodes, err))
       return false;
 
     // If an input is not ready, neither are our outputs.
@@ -463,6 +501,13 @@ void Edge::Dump(const char* prefix) const {
        i != outputs_.end() && *i != NULL; ++i) {
     printf("%s ", (*i)->path().c_str());
   }
+  if (!validations_.empty()) {
+    printf(" validations ");
+    for (std::vector<Node*>::const_iterator i = validations_.begin();
+         i != validations_.end() && *i != NULL; ++i) {
+      printf("%s ", (*i)->path().c_str());
+    }
+  }
   if (pool_) {
     if (!pool_->name().empty()) {
       printf("(in pool '%s')", pool_->name().c_str());
@@ -519,6 +564,13 @@ void Node::Dump(const char* prefix) const {
        e != out_edges().end() && *e != NULL; ++e) {
     (*e)->Dump(" +- ");
   }
+  if (!validation_out_edges().empty()) {
+    printf(" validation out edges:\n");
+    for (std::vector<Edge*>::const_iterator e = validation_out_edges().begin();
+         e != validation_out_edges().end() && *e != NULL; ++e) {
+      (*e)->Dump(" +- ");
+    }
+  }
 }
 
 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
diff --git a/src/graph.h b/src/graph.h
index fac8059..141b439 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -108,7 +108,9 @@ struct Node {
   void set_id(int id) { id_ = id; }
 
   const std::vector<Edge*>& out_edges() const { return out_edges_; }
+  const std::vector<Edge*>& validation_out_edges() const { return validation_out_edges_; }
   void AddOutEdge(Edge* edge) { out_edges_.push_back(edge); }
+  void AddValidationOutEdge(Edge* edge) { validation_out_edges_.push_back(edge); }
 
   void Dump(const char* prefix="") const;
 
@@ -151,6 +153,9 @@ private:
   /// All Edges that use this Node as an input.
   std::vector<Edge*> out_edges_;
 
+  /// All Edges that use this Node as a validation.
+  std::vector<Edge*> validation_out_edges_;
+
   /// A dense integer id for the node, assigned and used by DepsLog.
   int id_;
 };
@@ -194,6 +199,7 @@ struct Edge {
   Pool* pool_;
   std::vector<Node*> inputs_;
   std::vector<Node*> outputs_;
+  std::vector<Node*> validations_;
   Node* dyndep_;
   BindingEnv* env_;
   VisitMark mark_;
@@ -309,12 +315,14 @@ struct DependencyScan {
         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.
+  /// Update the |dirty_| state of the given nodes by transitively inspecting
+  /// their input edges.
   /// Examine inputs, outputs, and command lines to judge whether an edge
   /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
   /// state accordingly.
+  /// Appends any validation nodes found to the nodes parameter.
   /// Returns false on failure.
-  bool RecomputeDirty(Node* node, std::string* err);
+  bool RecomputeDirty(Node* node, std::vector<Node*>* validation_nodes, std::string* err);
 
   /// Recompute whether any output of the edge is dirty, if so sets |*dirty|.
   /// Returns false on failure.
@@ -340,7 +348,8 @@ struct DependencyScan {
   bool LoadDyndeps(Node* node, DyndepFile* ddf, std::string* err) const;
 
  private:
-  bool RecomputeDirty(Node* node, std::vector<Node*>* stack, std::string* err);
+  bool RecomputeNodeDirty(Node* node, std::vector<Node*>* stack,
+                          std::vector<Node*>* validation_nodes, std::string* err);
   bool VerifyDAG(Node* node, std::vector<Node*>* stack, std::string* err);
 
   /// Recompute whether a given single output should be marked dirty.
diff --git a/src/graph_test.cc b/src/graph_test.cc
index 4f0de98..5314bc5 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -33,7 +33,7 @@ TEST_F(GraphTest, MissingImplicit) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   // A missing implicit dep *should* make the output dirty.
@@ -51,7 +51,7 @@ TEST_F(GraphTest, ModifiedImplicit) {
   fs_.Create("implicit", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   // A modified implicit dep should make the output dirty.
@@ -71,7 +71,7 @@ TEST_F(GraphTest, FunkyMakefilePath) {
   fs_.Create("implicit.h", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   // implicit.h has changed, though our depfile refers to it with a
@@ -94,7 +94,7 @@ TEST_F(GraphTest, ExplicitImplicit) {
   fs_.Create("data", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   // We have both an implicit and an explicit dep on implicit.h.
@@ -122,7 +122,7 @@ TEST_F(GraphTest, ImplicitOutputMissing) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -138,7 +138,7 @@ TEST_F(GraphTest, ImplicitOutputOutOfDate) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -162,7 +162,7 @@ TEST_F(GraphTest, ImplicitOutputOnlyMissing) {
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -176,7 +176,7 @@ TEST_F(GraphTest, ImplicitOutputOnlyOutOfDate) {
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -193,7 +193,7 @@ TEST_F(GraphTest, PathWithCurrentDirectory) {
   fs_.Create("out.o", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -241,7 +241,7 @@ TEST_F(GraphTest, DepfileWithCanonicalizablePath) {
   fs_.Create("out.o", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -261,13 +261,13 @@ TEST_F(GraphTest, DepfileRemoved) {
   fs_.Create("out.o", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
   EXPECT_FALSE(GetNode("out.o")->dirty());
 
   state_.Reset();
   fs_.RemoveFile("out.o.d");
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(GetNode("out.o")->dirty());
 }
@@ -314,7 +314,7 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) {
 "build n2: phony n1\n"
   );
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), NULL, &err));
   ASSERT_EQ("", err);
 
   Plan plan_;
@@ -333,7 +333,7 @@ TEST_F(GraphTest, PhonySelfReferenceError) {
   parser_opts);
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> a [-w phonycycle=err]", err);
 }
 
@@ -345,7 +345,7 @@ TEST_F(GraphTest, DependencyCycle) {
 "build pre: cat out\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
 }
 
@@ -353,7 +353,7 @@ TEST_F(GraphTest, CycleInEdgesButNotInNodes1) {
   string err;
   AssertParse(&state_,
 "build a b: cat a\n");
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> a", err);
 }
 
@@ -361,7 +361,7 @@ TEST_F(GraphTest, CycleInEdgesButNotInNodes2) {
   string err;
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build b a: cat a\n"));
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> a", err);
 }
 
@@ -370,7 +370,7 @@ TEST_F(GraphTest, CycleInEdgesButNotInNodes3) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build a b: cat c\n"
 "build c: cat a\n"));
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> c -> a", err);
 }
 
@@ -382,7 +382,7 @@ TEST_F(GraphTest, CycleInEdgesButNotInNodes4) {
 "build b: cat a\n"
 "build a e: cat d\n"
 "build f: cat e\n"));
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> d -> c -> b -> a", err);
 }
 
@@ -398,7 +398,7 @@ TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) {
   fs_.Create("dep.d", "a: b\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), NULL, &err));
   ASSERT_EQ("dependency cycle: b -> b", err);
 
   // Despite the depfile causing edge to be a cycle (it has outputs a and b,
@@ -423,7 +423,7 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfile) {
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), NULL, &err));
   ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
@@ -450,7 +450,7 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) {
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), NULL, &err));
   ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
@@ -705,7 +705,7 @@ TEST_F(GraphTest, DyndepFileMissing) {
   );
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("loading 'dd': No such file or directory", err);
 }
 
@@ -721,7 +721,7 @@ TEST_F(GraphTest, DyndepFileError) {
   );
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("'out' not mentioned in its dyndep file 'dd'", err);
 }
 
@@ -741,7 +741,7 @@ TEST_F(GraphTest, DyndepImplicitInputNewer) {
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("in")->dirty());
@@ -769,7 +769,7 @@ TEST_F(GraphTest, DyndepFileReady) {
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("in")->dirty());
@@ -794,7 +794,7 @@ TEST_F(GraphTest, DyndepFileNotClean) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("dd")->dirty());
@@ -820,7 +820,7 @@ TEST_F(GraphTest, DyndepFileNotReady) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("dd")->dirty());
@@ -848,7 +848,7 @@ TEST_F(GraphTest, DyndepFileSecondNotReady) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("dd1")->dirty());
@@ -877,7 +877,7 @@ TEST_F(GraphTest, DyndepFileCircular) {
 
   Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   EXPECT_EQ("dependency cycle: circ -> in -> circ", err);
 
   // Verify that "out.d" was loaded exactly once despite
@@ -890,6 +890,24 @@ TEST_F(GraphTest, DyndepFileCircular) {
   EXPECT_EQ(1u, edge->order_only_deps_);
 }
 
+TEST_F(GraphTest, Validation) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build out: cat in |@ validate\n"
+"build validate: cat in\n"));
+
+  fs_.Create("in", "");
+  string err;
+  std::vector<Node*> validation_nodes;
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &validation_nodes, &err));
+  ASSERT_EQ("", err);
+
+  ASSERT_EQ(validation_nodes.size(), 1);
+  EXPECT_EQ(validation_nodes[0]->path(), "validate");
+
+  EXPECT_TRUE(GetNode("out")->dirty());
+  EXPECT_TRUE(GetNode("validate")->dirty());
+}
+
 // Check that phony's dependencies' mtimes are propagated.
 TEST_F(GraphTest, PhonyDepsMtimes) {
   string err;
@@ -904,7 +922,7 @@ TEST_F(GraphTest, PhonyDepsMtimes) {
   Node* out1 = GetNode("out1");
   Node* in1  = GetNode("in1");
 
-  EXPECT_TRUE(scan_.RecomputeDirty(out1, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(out1, NULL, &err));
   EXPECT_TRUE(!out1->dirty());
 
   // Get the mtime of out1
@@ -921,7 +939,7 @@ TEST_F(GraphTest, PhonyDepsMtimes) {
   ASSERT_TRUE(in1->Stat(&fs_, &err));
   EXPECT_GT(in1->mtime(), in1Mtime1);
 
-  EXPECT_TRUE(scan_.RecomputeDirty(out1, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(out1, NULL, &err));
   EXPECT_GT(in1->mtime(), in1Mtime1);
   EXPECT_EQ(out1->mtime(), out1Mtime1);
   EXPECT_TRUE(out1->dirty());
diff --git a/src/lexer.cc b/src/lexer.cc
index 6e4a470..af861ae 100644
--- a/src/lexer.cc
+++ b/src/lexer.cc
@@ -1,4 +1,4 @@
-/* Generated by re2c 1.1.1 */
+/* Generated by re2c 2.2 */
 // Copyright 2011 Google Inc. All Rights Reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
@@ -85,6 +85,7 @@ const char* Lexer::TokenName(Token t) {
   case NEWLINE:  return "newline";
   case PIPE2:    return "'||'";
   case PIPE:     return "'|'";
+  case PIPEAT:   return "'|@'";
   case POOL:     return "'pool'";
   case RULE:     return "'rule'";
   case SUBNINJA: return "'subninja'";
@@ -291,7 +292,8 @@ yy25:
 	goto yy14;
 yy26:
 	yych = *++p;
-	if (yych == '|') goto yy42;
+	if (yych == '@') goto yy42;
+	if (yych == '|') goto yy44;
 	{ token = PIPE;     break; }
 yy28:
 	++p;
@@ -317,126 +319,129 @@ yy33:
 	{ continue; }
 yy36:
 	yych = *++p;
-	if (yych == 'i') goto yy44;
+	if (yych == 'i') goto yy46;
 	goto yy14;
 yy37:
 	yych = *++p;
-	if (yych == 'f') goto yy45;
+	if (yych == 'f') goto yy47;
 	goto yy14;
 yy38:
 	yych = *++p;
-	if (yych == 'c') goto yy46;
+	if (yych == 'c') goto yy48;
 	goto yy14;
 yy39:
 	yych = *++p;
-	if (yych == 'o') goto yy47;
+	if (yych == 'o') goto yy49;
 	goto yy14;
 yy40:
 	yych = *++p;
-	if (yych == 'l') goto yy48;
+	if (yych == 'l') goto yy50;
 	goto yy14;
 yy41:
 	yych = *++p;
-	if (yych == 'b') goto yy49;
+	if (yych == 'b') goto yy51;
 	goto yy14;
 yy42:
 	++p;
-	{ token = PIPE2;    break; }
+	{ token = PIPEAT;   break; }
 yy44:
-	yych = *++p;
-	if (yych == 'l') goto yy50;
-	goto yy14;
-yy45:
-	yych = *++p;
-	if (yych == 'a') goto yy51;
-	goto yy14;
+	++p;
+	{ token = PIPE2;    break; }
 yy46:
 	yych = *++p;
 	if (yych == 'l') goto yy52;
 	goto yy14;
 yy47:
 	yych = *++p;
-	if (yych == 'l') goto yy53;
+	if (yych == 'a') goto yy53;
 	goto yy14;
 yy48:
 	yych = *++p;
-	if (yych == 'e') goto yy55;
+	if (yych == 'l') goto yy54;
 	goto yy14;
 yy49:
 	yych = *++p;
-	if (yych == 'n') goto yy57;
+	if (yych == 'l') goto yy55;
 	goto yy14;
 yy50:
 	yych = *++p;
-	if (yych == 'd') goto yy58;
+	if (yych == 'e') goto yy57;
 	goto yy14;
 yy51:
 	yych = *++p;
-	if (yych == 'u') goto yy60;
+	if (yych == 'n') goto yy59;
 	goto yy14;
 yy52:
 	yych = *++p;
-	if (yych == 'u') goto yy61;
+	if (yych == 'd') goto yy60;
 	goto yy14;
 yy53:
 	yych = *++p;
+	if (yych == 'u') goto yy62;
+	goto yy14;
+yy54:
+	yych = *++p;
+	if (yych == 'u') goto yy63;
+	goto yy14;
+yy55:
+	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = POOL;     break; }
-yy55:
+yy57:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = RULE;     break; }
-yy57:
+yy59:
 	yych = *++p;
-	if (yych == 'i') goto yy62;
+	if (yych == 'i') goto yy64;
 	goto yy14;
-yy58:
+yy60:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = BUILD;    break; }
-yy60:
-	yych = *++p;
-	if (yych == 'l') goto yy63;
-	goto yy14;
-yy61:
-	yych = *++p;
-	if (yych == 'd') goto yy64;
-	goto yy14;
 yy62:
 	yych = *++p;
-	if (yych == 'n') goto yy65;
+	if (yych == 'l') goto yy65;
 	goto yy14;
 yy63:
 	yych = *++p;
-	if (yych == 't') goto yy66;
+	if (yych == 'd') goto yy66;
 	goto yy14;
 yy64:
 	yych = *++p;
-	if (yych == 'e') goto yy68;
+	if (yych == 'n') goto yy67;
 	goto yy14;
 yy65:
 	yych = *++p;
-	if (yych == 'j') goto yy70;
+	if (yych == 't') goto yy68;
 	goto yy14;
 yy66:
 	yych = *++p;
+	if (yych == 'e') goto yy70;
+	goto yy14;
+yy67:
+	yych = *++p;
+	if (yych == 'j') goto yy72;
+	goto yy14;
+yy68:
+	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = DEFAULT;  break; }
-yy68:
+yy70:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = INCLUDE;  break; }
-yy70:
+yy72:
 	yych = *++p;
 	if (yych != 'a') goto yy14;
 	yych = *++p;
@@ -507,38 +512,38 @@ void Lexer::EatWhitespace() {
 	};
 	yych = *p;
 	if (yybm[0+yych] & 128) {
-		goto yy79;
+		goto yy81;
 	}
-	if (yych <= 0x00) goto yy75;
-	if (yych == '$') goto yy82;
-	goto yy77;
-yy75:
-	++p;
-	{ break; }
+	if (yych <= 0x00) goto yy77;
+	if (yych == '$') goto yy84;
+	goto yy79;
 yy77:
 	++p;
-yy78:
 	{ break; }
 yy79:
+	++p;
+yy80:
+	{ break; }
+yy81:
 	yych = *++p;
 	if (yybm[0+yych] & 128) {
-		goto yy79;
+		goto yy81;
 	}
 	{ continue; }
-yy82:
+yy84:
 	yych = *(q = ++p);
-	if (yych == '\n') goto yy83;
-	if (yych == '\r') goto yy85;
-	goto yy78;
-yy83:
+	if (yych == '\n') goto yy85;
+	if (yych == '\r') goto yy87;
+	goto yy80;
+yy85:
 	++p;
 	{ continue; }
-yy85:
+yy87:
 	yych = *++p;
-	if (yych == '\n') goto yy87;
+	if (yych == '\n') goto yy89;
 	p = q;
-	goto yy78;
-yy87:
+	goto yy80;
+yy89:
 	++p;
 	{ continue; }
 }
@@ -590,17 +595,17 @@ bool Lexer::ReadIdent(string* out) {
 	};
 	yych = *p;
 	if (yybm[0+yych] & 128) {
-		goto yy93;
+		goto yy95;
 	}
 	++p;
 	{
       last_token_ = start;
       return false;
     }
-yy93:
+yy95:
 	yych = *++p;
 	if (yybm[0+yych] & 128) {
-		goto yy93;
+		goto yy95;
 	}
 	{
       out->assign(start, p - start);
@@ -660,33 +665,33 @@ bool Lexer::ReadEvalString(EvalString* eval, bool path, string* err) {
 	};
 	yych = *p;
 	if (yybm[0+yych] & 16) {
-		goto yy100;
+		goto yy102;
 	}
 	if (yych <= '\r') {
-		if (yych <= 0x00) goto yy98;
-		if (yych <= '\n') goto yy103;
-		goto yy105;
+		if (yych <= 0x00) goto yy100;
+		if (yych <= '\n') goto yy105;
+		goto yy107;
 	} else {
-		if (yych <= ' ') goto yy103;
-		if (yych <= '$') goto yy107;
-		goto yy103;
+		if (yych <= ' ') goto yy105;
+		if (yych <= '$') goto yy109;
+		goto yy105;
 	}
-yy98:
+yy100:
 	++p;
 	{
       last_token_ = start;
       return Error("unexpected EOF", err);
     }
-yy100:
+yy102:
 	yych = *++p;
 	if (yybm[0+yych] & 16) {
-		goto yy100;
+		goto yy102;
 	}
 	{
       eval->AddText(StringPiece(start, p - start));
       continue;
     }
-yy103:
+yy105:
 	++p;
 	{
       if (path) {
@@ -699,112 +704,112 @@ yy103:
         continue;
       }
     }
-yy105:
+yy107:
 	yych = *++p;
-	if (yych == '\n') goto yy108;
+	if (yych == '\n') goto yy110;
 	{
       last_token_ = start;
       return Error(DescribeLastError(), err);
     }
-yy107:
+yy109:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
-		goto yy120;
+		goto yy122;
 	}
 	if (yych <= ' ') {
 		if (yych <= '\f') {
-			if (yych == '\n') goto yy112;
-			goto yy110;
+			if (yych == '\n') goto yy114;
+			goto yy112;
 		} else {
-			if (yych <= '\r') goto yy115;
-			if (yych <= 0x1F) goto yy110;
-			goto yy116;
+			if (yych <= '\r') goto yy117;
+			if (yych <= 0x1F) goto yy112;
+			goto yy118;
 		}
 	} else {
 		if (yych <= '/') {
-			if (yych == '$') goto yy118;
-			goto yy110;
+			if (yych == '$') goto yy120;
+			goto yy112;
 		} else {
-			if (yych <= ':') goto yy123;
-			if (yych <= '`') goto yy110;
-			if (yych <= '{') goto yy125;
-			goto yy110;
+			if (yych <= ':') goto yy125;
+			if (yych <= '`') goto yy112;
+			if (yych <= '{') goto yy127;
+			goto yy112;
 		}
 	}
-yy108:
+yy110:
 	++p;
 	{
       if (path)
         p = start;
       break;
     }
-yy110:
+yy112:
 	++p;
-yy111:
+yy113:
 	{
       last_token_ = start;
       return Error("bad $-escape (literal $ must be written as $$)", err);
     }
-yy112:
+yy114:
 	yych = *++p;
 	if (yybm[0+yych] & 32) {
-		goto yy112;
+		goto yy114;
 	}
 	{
       continue;
     }
-yy115:
+yy117:
 	yych = *++p;
-	if (yych == '\n') goto yy126;
-	goto yy111;
-yy116:
+	if (yych == '\n') goto yy128;
+	goto yy113;
+yy118:
 	++p;
 	{
       eval->AddText(StringPiece(" ", 1));
       continue;
     }
-yy118:
+yy120:
 	++p;
 	{
       eval->AddText(StringPiece("$", 1));
       continue;
     }
-yy120:
+yy122:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
-		goto yy120;
+		goto yy122;
 	}
 	{
       eval->AddSpecial(StringPiece(start + 1, p - start - 1));
       continue;
     }
-yy123:
+yy125:
 	++p;
 	{
       eval->AddText(StringPiece(":", 1));
       continue;
     }
-yy125:
+yy127:
 	yych = *(q = ++p);
 	if (yybm[0+yych] & 128) {
-		goto yy129;
+		goto yy131;
 	}
-	goto yy111;
-yy126:
+	goto yy113;
+yy128:
 	yych = *++p;
-	if (yych == ' ') goto yy126;
+	if (yych == ' ') goto yy128;
 	{
       continue;
     }
-yy129:
+yy131:
 	yych = *++p;
 	if (yybm[0+yych] & 128) {
-		goto yy129;
+		goto yy131;
 	}
-	if (yych == '}') goto yy132;
+	if (yych == '}') goto yy134;
 	p = q;
-	goto yy111;
-yy132:
+	goto yy113;
+yy134:
 	++p;
 	{
       eval->AddSpecial(StringPiece(start + 2, p - start - 3));
diff --git a/src/lexer.h b/src/lexer.h
index 788d948..683fd6c 100644
--- a/src/lexer.h
+++ b/src/lexer.h
@@ -41,6 +41,7 @@ struct Lexer {
     NEWLINE,
     PIPE,
     PIPE2,
+    PIPEAT,
     POOL,
     RULE,
     SUBNINJA,
diff --git a/src/lexer.in.cc b/src/lexer.in.cc
index 88007e7..6f1d8e7 100644
--- a/src/lexer.in.cc
+++ b/src/lexer.in.cc
@@ -84,6 +84,7 @@ const char* Lexer::TokenName(Token t) {
   case NEWLINE:  return "newline";
   case PIPE2:    return "'||'";
   case PIPE:     return "'|'";
+  case PIPEAT:   return "'|@'";
   case POOL:     return "'pool'";
   case RULE:     return "'rule'";
   case SUBNINJA: return "'subninja'";
@@ -142,6 +143,7 @@ Lexer::Token Lexer::ReadToken() {
     "default"  { token = DEFAULT;  break; }
     "="        { token = EQUALS;   break; }
     ":"        { token = COLON;    break; }
+    "|@"       { token = PIPEAT;   break; }
     "||"       { token = PIPE2;    break; }
     "|"        { token = PIPE;     break; }
     "include"  { token = INCLUDE;  break; }
diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc
index 521edb4..8db6eb3 100644
--- a/src/manifest_parser.cc
+++ b/src/manifest_parser.cc
@@ -207,7 +207,7 @@ bool ManifestParser::ParseDefault(string* err) {
 }
 
 bool ManifestParser::ParseEdge(string* err) {
-  vector<EvalString> ins, outs;
+  vector<EvalString> ins, outs, validations;
 
   {
     EvalString out;
@@ -288,6 +288,18 @@ bool ManifestParser::ParseEdge(string* err) {
     }
   }
 
+  // Add all validations, counting how many as we go.
+  if (lexer_.PeekToken(Lexer::PIPEAT)) {
+    for (;;) {
+      EvalString validation;
+      if (!lexer_.ReadPath(&validation, err))
+        return false;
+      if (validation.empty())
+        break;
+      validations.push_back(validation);
+    }
+  }
+
   if (!ExpectToken(Lexer::NEWLINE, err))
     return false;
 
@@ -338,6 +350,7 @@ bool ManifestParser::ParseEdge(string* err) {
       }
     }
   }
+
   if (edge->outputs_.empty()) {
     // All outputs of the edge are already created by other edges. Don't add
     // this edge.  Do this check before input nodes are connected to the edge.
@@ -359,6 +372,17 @@ bool ManifestParser::ParseEdge(string* err) {
   edge->implicit_deps_ = implicit;
   edge->order_only_deps_ = order_only;
 
+  edge->validations_.reserve(validations.size());
+  for (std::vector<EvalString>::iterator v = validations.begin();
+      v != validations.end(); ++v) {
+    string path = v->Evaluate(env);
+    if (path.empty())
+      return lexer_.Error("empty path", err);
+    uint64_t slash_bits;
+    CanonicalizePath(&path, &slash_bits);
+    state_->AddValidation(edge, path, slash_bits);
+  }
+
   if (options_.phony_cycle_action_ == kPhonyCycleActionWarn &&
       edge->maybe_phonycycle_diagnostic()) {
     // CMake 2.8.12.x and 3.0.x incorrectly write phony build statements
diff --git a/src/manifest_parser_test.cc b/src/manifest_parser_test.cc
index 5b0eddf..66b72e2 100644
--- a/src/manifest_parser_test.cc
+++ b/src/manifest_parser_test.cc
@@ -965,6 +965,16 @@ TEST_F(ParserTest, OrderOnly) {
   ASSERT_TRUE(edge->is_order_only(1));
 }
 
+TEST_F(ParserTest, Validations) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"rule cat\n  command = cat $in > $out\n"
+"build foo: cat bar |@ baz\n"));
+
+  Edge* edge = state.LookupNode("foo")->in_edge();
+  ASSERT_EQ(edge->validations_.size(), 1);
+  EXPECT_EQ(edge->validations_[0]->path(), "baz");
+}
+
 TEST_F(ParserTest, ImplicitOutput) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(
 "rule cat\n"
diff --git a/src/ninja.cc b/src/ninja.cc
index 3e5c971..89580ae 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -404,6 +404,13 @@ int NinjaMain::ToolQuery(const Options* options, int argc, char* argv[]) {
           label = "|| ";
         printf("    %s%s\n", label, edge->inputs_[in]->path().c_str());
       }
+      if (!edge->validations_.empty()) {
+        printf("  validations:\n");
+        for (std::vector<Node*>::iterator validation = edge->validations_.begin();
+             validation != edge->validations_.end(); ++validation) {
+          printf("    %s\n", (*validation)->path().c_str());
+        }
+      }
     }
     printf("  outputs:\n");
     for (vector<Edge*>::const_iterator edge = node->out_edges().begin();
@@ -413,6 +420,17 @@ int NinjaMain::ToolQuery(const Options* options, int argc, char* argv[]) {
         printf("    %s\n", (*out)->path().c_str());
       }
     }
+    const std::vector<Edge*> validation_edges = node->validation_out_edges();
+    if (!validation_edges.empty()) {
+      printf("  validation for:\n");
+      for (std::vector<Edge*>::const_iterator edge = validation_edges.begin();
+           edge != validation_edges.end(); ++edge) {
+        for (vector<Node*>::iterator out = (*edge)->outputs_.begin();
+             out != (*edge)->outputs_.end(); ++out) {
+          printf("    %s\n", (*out)->path().c_str());
+        }
+      }
+    }
   }
   return 0;
 }
diff --git a/src/state.cc b/src/state.cc
index fc37c8a..556b0d8 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -141,6 +141,12 @@ bool State::AddOut(Edge* edge, StringPiece path, uint64_t slash_bits) {
   return true;
 }
 
+void State::AddValidation(Edge* edge, StringPiece path, uint64_t slash_bits) {
+  Node* node = GetNode(path, slash_bits);
+  edge->validations_.push_back(node);
+  node->AddValidationOutEdge(edge);
+}
+
 bool State::AddDefault(StringPiece path, string* err) {
   Node* node = LookupNode(path);
   if (!node) {
diff --git a/src/state.h b/src/state.h
index 72c5b33..878ac6d 100644
--- a/src/state.h
+++ b/src/state.h
@@ -107,6 +107,7 @@ struct State {
 
   void AddIn(Edge* edge, StringPiece path, uint64_t slash_bits);
   bool AddOut(Edge* edge, StringPiece path, uint64_t slash_bits);
+  void AddValidation(Edge* edge, StringPiece path, uint64_t slash_bits);
   bool AddDefault(StringPiece path, std::string* error);
 
   /// Reset state.  Keeps all nodes and edges, but restores them to the