Merge branch 'master' into release

38 files changed, 2340 insertions, 814 deletions

diff --git a/src/build.cc b/src/build.cc
index ae47a50..5cf9d27 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -15,25 +15,21 @@
 #include "build.h"
 
 #include <assert.h>
+#include <errno.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <functional>
 
-#ifdef _WIN32
-#include <windows.h>
-#else
-#include <unistd.h>
-#include <sys/ioctl.h>
-#include <sys/time.h>
-#endif
-
 #if defined(__SVR4) && defined(__sun)
 #include <sys/termios.h>
 #endif
 
 #include "build_log.h"
+#include "depfile_parser.h"
+#include "deps_log.h"
 #include "disk_interface.h"
 #include "graph.h"
+#include "msvc_helper.h"
 #include "state.h"
 #include "subprocess.h"
 #include "util.h"
@@ -47,7 +43,7 @@ struct DryRunCommandRunner : public CommandRunner {
   // Overridden from CommandRunner:
   virtual bool CanRunMore();
   virtual bool StartCommand(Edge* edge);
-  virtual Edge* WaitForCommand(ExitStatus* status, string* /* output */);
+  virtual bool WaitForCommand(Result* result);
 
  private:
   queue<Edge*> finished_;
@@ -62,16 +58,14 @@ bool DryRunCommandRunner::StartCommand(Edge* edge) {
   return true;
 }
 
-Edge* DryRunCommandRunner::WaitForCommand(ExitStatus* status,
-                                          string* /*output*/) {
-   if (finished_.empty()) {
-     *status = ExitFailure;
-     return NULL;
-   }
-   *status = ExitSuccess;
-   Edge* edge = finished_.front();
+bool DryRunCommandRunner::WaitForCommand(Result* result) {
+   if (finished_.empty())
+     return false;
+
+   result->status = ExitSuccess;
+   result->edge = finished_.front();
    finished_.pop();
-   return edge;
+   return true;
 }
 
 }  // namespace
@@ -80,25 +74,12 @@ BuildStatus::BuildStatus(const BuildConfig& config)
     : config_(config),
       start_time_millis_(GetTimeMillis()),
       started_edges_(0), finished_edges_(0), total_edges_(0),
-      have_blank_line_(true), progress_status_format_(NULL),
+      progress_status_format_(NULL),
       overall_rate_(), current_rate_(config.parallelism) {
-#ifndef _WIN32
-  const char* term = getenv("TERM");
-  smart_terminal_ = isatty(1) && term && string(term) != "dumb";
-#else
-  // Disable output buffer.  It'd be nice to use line buffering but
-  // MSDN says: "For some systems, [_IOLBF] provides line
-  // buffering. However, for Win32, the behavior is the same as _IOFBF
-  // - Full Buffering."
-  setvbuf(stdout, NULL, _IONBF, 0);
-  console_ = GetStdHandle(STD_OUTPUT_HANDLE);
-  CONSOLE_SCREEN_BUFFER_INFO csbi;
-  smart_terminal_ = GetConsoleScreenBufferInfo(console_, &csbi);
-#endif
 
   // Don't do anything fancy in verbose mode.
   if (config_.verbosity != BuildConfig::NORMAL)
-    smart_terminal_ = false;
+    printer_.set_smart_terminal(false);
 
   progress_status_format_ = getenv("NINJA_STATUS");
   if (!progress_status_format_)
@@ -133,17 +114,14 @@ void BuildStatus::BuildEdgeFinished(Edge* edge,
   if (config_.verbosity == BuildConfig::QUIET)
     return;
 
-  if (smart_terminal_)
+  if (printer_.is_smart_terminal())
     PrintStatus(edge);
 
-  if (!success || !output.empty()) {
-    if (smart_terminal_)
-      printf("\n");
-
-    // Print the command that is spewing before printing its output.
-    if (!success)
-      printf("FAILED: %s\n", edge->EvaluateCommand().c_str());
+  // Print the command that is spewing before printing its output.
+  if (!success)
+    printer_.PrintOnNewLine("FAILED: " + edge->EvaluateCommand() + "\n");
 
+  if (!output.empty()) {
     // ninja sets stdout and stderr of subprocesses to a pipe, to be able to
     // check if the output is empty. Some compilers, e.g. clang, check
     // isatty(stderr) to decide if they should print colored output.
@@ -157,21 +135,16 @@ void BuildStatus::BuildEdgeFinished(Edge* edge,
     // thousands of parallel compile commands.)
     // TODO: There should be a flag to disable escape code stripping.
     string final_output;
-    if (!smart_terminal_)
+    if (!printer_.is_smart_terminal())
       final_output = StripAnsiEscapeCodes(output);
     else
       final_output = output;
-
-    if (!final_output.empty())
-      printf("%s", final_output.c_str());
-
-    have_blank_line_ = true;
+    printer_.PrintOnNewLine(final_output);
   }
 }
 
 void BuildStatus::BuildFinished() {
-  if (smart_terminal_ && !have_blank_line_)
-    printf("\n");
+  printer_.PrintOnNewLine("");
 }
 
 string BuildStatus::FormatProgressStatus(
@@ -267,72 +240,14 @@ void BuildStatus::PrintStatus(Edge* edge) {
   if (to_print.empty() || force_full_command)
     to_print = edge->GetBinding("command");
 
-#ifdef _WIN32
-  CONSOLE_SCREEN_BUFFER_INFO csbi;
-  GetConsoleScreenBufferInfo(console_, &csbi);
-#endif
-
-  if (smart_terminal_) {
-#ifndef _WIN32
-    printf("\r");  // Print over previous line, if any.
-#else
-    csbi.dwCursorPosition.X = 0;
-    SetConsoleCursorPosition(console_, csbi.dwCursorPosition);
-#endif
-  }
-
   if (finished_edges_ == 0) {
     overall_rate_.Restart();
     current_rate_.Restart();
   }
   to_print = FormatProgressStatus(progress_status_format_) + to_print;
 
-  if (smart_terminal_ && !force_full_command) {
-#ifndef _WIN32
-    // Limit output to width of the terminal if provided so we don't cause
-    // line-wrapping.
-    winsize size;
-    if ((ioctl(0, TIOCGWINSZ, &size) == 0) && size.ws_col) {
-      to_print = ElideMiddle(to_print, size.ws_col);
-    }
-#else
-    // Don't use the full width or console will move to next line.
-    size_t width = static_cast<size_t>(csbi.dwSize.X) - 1;
-    to_print = ElideMiddle(to_print, width);
-#endif
-  }
-
-  if (smart_terminal_ && !force_full_command) {
-#ifndef _WIN32
-    printf("%s", to_print.c_str());
-    printf("\x1B[K");  // Clear to end of line.
-    fflush(stdout);
-    have_blank_line_ = false;
-#else
-    // We don't want to have the cursor spamming back and forth, so
-    // use WriteConsoleOutput instead which updates the contents of
-    // the buffer, but doesn't move the cursor position.
-    GetConsoleScreenBufferInfo(console_, &csbi);
-    COORD buf_size = { csbi.dwSize.X, 1 };
-    COORD zero_zero = { 0, 0 };
-    SMALL_RECT target = { csbi.dwCursorPosition.X, csbi.dwCursorPosition.Y,
-                          (SHORT)(csbi.dwCursorPosition.X + csbi.dwSize.X - 1),
-                          csbi.dwCursorPosition.Y };
-    CHAR_INFO* char_data = new CHAR_INFO[csbi.dwSize.X];
-    memset(char_data, 0, sizeof(CHAR_INFO) * csbi.dwSize.X);
-    for (int i = 0; i < csbi.dwSize.X; ++i) {
-      char_data[i].Char.AsciiChar = ' ';
-      char_data[i].Attributes = csbi.wAttributes;
-    }
-    for (size_t i = 0; i < to_print.size(); ++i)
-      char_data[i].Char.AsciiChar = to_print[i];
-    WriteConsoleOutput(console_, char_data, buf_size, zero_zero, &target);
-    delete[] char_data;
-    have_blank_line_ = false;
-#endif
-  } else {
-    printf("%s\n", to_print.c_str());
-  }
+  printer_.Print(to_print,
+                 force_full_command ? LinePrinter::FULL : LinePrinter::ELIDE);
 }
 
 Plan::Plan() : command_edges_(0), wanted_edges_(0) {}
@@ -514,7 +429,7 @@ void Plan::CleanNode(DependencyScan* scan, Node* node) {
         if (!(*ni)->dirty())
           continue;
 
-        if (scan->RecomputeOutputDirty(*ei, most_recent_input,
+        if (scan->RecomputeOutputDirty(*ei, most_recent_input, 0,
                                        command, *ni)) {
           (*ni)->MarkDirty();
           all_outputs_clean = false;
@@ -549,7 +464,7 @@ struct RealCommandRunner : public CommandRunner {
   virtual ~RealCommandRunner() {}
   virtual bool CanRunMore();
   virtual bool StartCommand(Edge* edge);
-  virtual Edge* WaitForCommand(ExitStatus* status, string* output);
+  virtual bool WaitForCommand(Result* result);
   virtual vector<Edge*> GetActiveEdges();
   virtual void Abort();
 
@@ -586,31 +501,30 @@ bool RealCommandRunner::StartCommand(Edge* edge) {
   return true;
 }
 
-Edge* RealCommandRunner::WaitForCommand(ExitStatus* status, string* output) {
+bool RealCommandRunner::WaitForCommand(Result* result) {
   Subprocess* subproc;
   while ((subproc = subprocs_.NextFinished()) == NULL) {
     bool interrupted = subprocs_.DoWork();
-    if (interrupted) {
-      *status = ExitInterrupted;
-      return 0;
-    }
+    if (interrupted)
+      return false;
   }
 
-  *status = subproc->Finish();
-  *output = subproc->GetOutput();
+  result->status = subproc->Finish();
+  result->output = subproc->GetOutput();
 
   map<Subprocess*, Edge*>::iterator i = subproc_to_edge_.find(subproc);
-  Edge* edge = i->second;
+  result->edge = i->second;
   subproc_to_edge_.erase(i);
 
   delete subproc;
-  return edge;
+  return true;
 }
 
 Builder::Builder(State* state, const BuildConfig& config,
-                 BuildLog* log, DiskInterface* disk_interface)
+                 BuildLog* build_log, DepsLog* deps_log,
+                 DiskInterface* disk_interface)
     : state_(state), config_(config), disk_interface_(disk_interface),
-      scan_(state, log, disk_interface) {
+      scan_(state, build_log, deps_log, disk_interface) {
   status_ = new BuildStatus(config);
 }
 
@@ -696,8 +610,6 @@ bool Builder::Build(string* err) {
   // First, we attempt to start as many commands as allowed by the
   // command runner.
   // Second, we attempt to wait for / reap the next finished command.
-  // If we can do neither of those, the build is stuck, and we report
-  // an error.
   while (plan_.more_to_do()) {
     // See if we can start any more commands.
     if (failures_allowed && command_runner_->CanRunMore()) {
@@ -707,10 +619,11 @@ bool Builder::Build(string* err) {
           return false;
         }
 
-        if (edge->is_phony())
-          FinishEdge(edge, true, "");
-        else
+        if (edge->is_phony()) {
+          plan_.EdgeFinished(edge);
+        } else {
           ++pending_commands;
+        }
 
         // We made some progress; go back to the main loop.
         continue;
@@ -719,34 +632,24 @@ bool Builder::Build(string* err) {
 
     // See if we can reap any finished commands.
     if (pending_commands) {
-      ExitStatus status;
-      string output;
-      Edge* edge = command_runner_->WaitForCommand(&status, &output);
-      if (edge && status != ExitInterrupted) {
-        bool success = (status == ExitSuccess);
-        --pending_commands;
-        FinishEdge(edge, success, output);
-        if (!success) {
-          if (failures_allowed)
-            failures_allowed--;
-        }
-
-        // We made some progress; start the main loop over.
-        continue;
-      }
-
-      if (status == ExitInterrupted) {
+      CommandRunner::Result result;
+      if (!command_runner_->WaitForCommand(&result) ||
+          result.status == ExitInterrupted) {
         status_->BuildFinished();
         *err = "interrupted by user";
         return false;
       }
-    }
 
-    // If we get here, we can neither enqueue new commands nor are any running.
-    if (pending_commands) {
-      status_->BuildFinished();
-      *err = "stuck: pending commands but none to wait for? [this is a bug]";
-      return false;
+      --pending_commands;
+      FinishCommand(&result);
+
+      if (!result.success()) {
+        if (failures_allowed)
+          failures_allowed--;
+      }
+
+      // We made some progress; start the main loop over.
+      continue;
     }
 
     // If we get here, we cannot make any more progress.
@@ -801,63 +704,145 @@ bool Builder::StartEdge(Edge* edge, string* err) {
   return true;
 }
 
-void Builder::FinishEdge(Edge* edge, bool success, const string& output) {
-  METRIC_RECORD("FinishEdge");
-  TimeStamp restat_mtime = 0;
+void Builder::FinishCommand(CommandRunner::Result* result) {
+  METRIC_RECORD("FinishCommand");
+
+  Edge* edge = result->edge;
+
+  // First try to extract dependencies from the result, if any.
+  // This must happen first as it filters the command output (we want
+  // to filter /showIncludes output, even on compile failure) and
+  // extraction itself can fail, which makes the command fail from a
+  // build perspective.
+  vector<Node*> deps_nodes;
+  string deps_type = edge->GetBinding("deps");
+  if (!deps_type.empty()) {
+    string extract_err;
+    if (!ExtractDeps(result, deps_type, &deps_nodes, &extract_err) &&
+        result->success()) {
+      if (!result->output.empty())
+        result->output.append("\n");
+      result->output.append(extract_err);
+      result->status = ExitFailure;
+    }
+  }
 
-  if (success) {
-    if (edge->GetBindingBool("restat") && !config_.dry_run) {
-      bool node_cleaned = false;
-
-      for (vector<Node*>::iterator i = edge->outputs_.begin();
-           i != edge->outputs_.end(); ++i) {
-        TimeStamp new_mtime = disk_interface_->Stat((*i)->path());
-        if ((*i)->mtime() == new_mtime) {
-          // The rule command did not change the output.  Propagate the clean
-          // state through the build graph.
-          // Note that this also applies to nonexistent outputs (mtime == 0).
-          plan_.CleanNode(&scan_, *i);
-          node_cleaned = true;
-        }
-      }
+  int start_time, end_time;
+  status_->BuildEdgeFinished(edge, result->success(), result->output,
+                             &start_time, &end_time);
 
-      if (node_cleaned) {
-        // If any output was cleaned, find the most recent mtime of any
-        // (existing) non-order-only input or the depfile.
-        for (vector<Node*>::iterator i = edge->inputs_.begin();
-             i != edge->inputs_.end() - edge->order_only_deps_; ++i) {
-          TimeStamp input_mtime = disk_interface_->Stat((*i)->path());
-          if (input_mtime > restat_mtime)
-            restat_mtime = input_mtime;
-        }
+  // The rest of this function only applies to successful commands.
+  if (!result->success())
+    return;
 
-        string depfile = edge->GetBinding("depfile");
-        if (restat_mtime != 0 && !depfile.empty()) {
-          TimeStamp depfile_mtime = disk_interface_->Stat(depfile);
-          if (depfile_mtime > restat_mtime)
-            restat_mtime = depfile_mtime;
-        }
+  // Restat the edge outputs, if necessary.
+  TimeStamp restat_mtime = 0;
+  if (edge->GetBindingBool("restat") && !config_.dry_run) {
+    bool node_cleaned = false;
+
+    for (vector<Node*>::iterator i = edge->outputs_.begin();
+         i != edge->outputs_.end(); ++i) {
+      TimeStamp new_mtime = disk_interface_->Stat((*i)->path());
+      if ((*i)->mtime() == new_mtime) {
+        // The rule command did not change the output.  Propagate the clean
+        // state through the build graph.
+        // Note that this also applies to nonexistent outputs (mtime == 0).
+        plan_.CleanNode(&scan_, *i);
+        node_cleaned = true;
+      }
+    }
 
-        // The total number of edges in the plan may have changed as a result
-        // of a restat.
-        status_->PlanHasTotalEdges(plan_.command_edge_count());
+    if (node_cleaned) {
+      // If any output was cleaned, find the most recent mtime of any
+      // (existing) non-order-only input or the depfile.
+      for (vector<Node*>::iterator i = edge->inputs_.begin();
+           i != edge->inputs_.end() - edge->order_only_deps_; ++i) {
+        TimeStamp input_mtime = disk_interface_->Stat((*i)->path());
+        if (input_mtime > restat_mtime)
+          restat_mtime = input_mtime;
       }
+
+      string depfile = edge->GetBinding("depfile");
+      if (restat_mtime != 0 && !depfile.empty()) {
+        TimeStamp depfile_mtime = disk_interface_->Stat(depfile);
+        if (depfile_mtime > restat_mtime)
+          restat_mtime = depfile_mtime;
+      }
+
+      // The total number of edges in the plan may have changed as a result
+      // of a restat.
+      status_->PlanHasTotalEdges(plan_.command_edge_count());
     }
+  }
+
+  plan_.EdgeFinished(edge);
 
-    // Delete the response file on success (if exists)
-    string rspfile = edge->GetBinding("rspfile");
-    if (!rspfile.empty())
-      disk_interface_->RemoveFile(rspfile);
+  // Delete any left over response file.
+  string rspfile = edge->GetBinding("rspfile");
+  if (!rspfile.empty())
+    disk_interface_->RemoveFile(rspfile);
 
-    plan_.EdgeFinished(edge);
+  if (scan_.build_log()) {
+    scan_.build_log()->RecordCommand(edge, start_time, end_time,
+                                     restat_mtime);
   }
 
-  if (edge->is_phony())
-    return;
+  if (!deps_type.empty() && !config_.dry_run) {
+    assert(edge->outputs_.size() == 1 && "should have been rejected by parser");
+    Node* out = edge->outputs_[0];
+    TimeStamp deps_mtime = disk_interface_->Stat(out->path());
+    scan_.deps_log()->RecordDeps(out, deps_mtime, deps_nodes);
+  }
 
-  int start_time, end_time;
-  status_->BuildEdgeFinished(edge, success, output, &start_time, &end_time);
-  if (success && scan_.build_log())
-    scan_.build_log()->RecordCommand(edge, start_time, end_time, restat_mtime);
 }
 
+bool Builder::ExtractDeps(CommandRunner::Result* result,
+                          const string& deps_type,
+                          vector<Node*>* deps_nodes,
+                          string* err) {
+#ifdef _WIN32
+  if (deps_type == "msvc") {
+    CLParser parser;
+    result->output = parser.Parse(result->output);
+    for (set<string>::iterator i = parser.includes_.begin();
+         i != parser.includes_.end(); ++i) {
+      deps_nodes->push_back(state_->GetNode(*i));
+    }
+  } else
+#endif
+  if (deps_type == "gcc") {
+    string depfile = result->edge->GetBinding("depfile");
+    if (depfile.empty()) {
+      *err = string("edge with deps=gcc but no depfile makes no sense");
+      return false;
+    }
+
+    string content = disk_interface_->ReadFile(depfile, err);
+    if (!err->empty())
+      return false;
+    if (content.empty())
+      return true;
+
+    DepfileParser deps;
+    if (!deps.Parse(&content, err))
+      return false;
+
+    // XXX check depfile matches expected output.
+    deps_nodes->reserve(deps.ins_.size());
+    for (vector<StringPiece>::iterator i = deps.ins_.begin();
+         i != deps.ins_.end(); ++i) {
+      if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, err))
+        return false;
+      deps_nodes->push_back(state_->GetNode(*i));
+    }
+
+    if (disk_interface_->RemoveFile(depfile) < 0) {
+      *err = string("deleting depfile: ") + strerror(errno) + string("\n");
+      return false;
+    }
+  } else {
+    Fatal("unknown deps type '%s'", deps_type.c_str());
+  }
+
+  return true;
+}
diff --git a/src/build.h b/src/build.h
index 5747170..2715c0c 100644
--- a/src/build.h
+++ b/src/build.h
@@ -25,6 +25,7 @@
 
 #include "graph.h"  // XXX needed for DependencyScan; should rearrange.
 #include "exit_status.h"
+#include "line_printer.h"
 #include "metrics.h"
 #include "util.h"  // int64_t
 
@@ -103,8 +104,18 @@ struct CommandRunner {
   virtual ~CommandRunner() {}
   virtual bool CanRunMore() = 0;
   virtual bool StartCommand(Edge* edge) = 0;
-  /// Wait for a command to complete.
-  virtual Edge* WaitForCommand(ExitStatus* status, string* output) = 0;
+
+  /// The result of waiting for a command.
+  struct Result {
+    Result() : edge(NULL) {}
+    Edge* edge;
+    ExitStatus status;
+    string output;
+    bool success() const { return status == ExitSuccess; }
+  };
+  /// Wait for a command to complete, or return false if interrupted.
+  virtual bool WaitForCommand(Result* result) = 0;
+
   virtual vector<Edge*> GetActiveEdges() { return vector<Edge*>(); }
   virtual void Abort() {}
 };
@@ -131,7 +142,8 @@ struct BuildConfig {
 /// Builder wraps the build process: starting commands, updating status.
 struct Builder {
   Builder(State* state, const BuildConfig& config,
-          BuildLog* log, DiskInterface* disk_interface);
+          BuildLog* build_log, DepsLog* deps_log,
+          DiskInterface* disk_interface);
   ~Builder();
 
   /// Clean up after interrupted commands by deleting output files.
@@ -151,7 +163,7 @@ struct Builder {
   bool Build(string* err);
 
   bool StartEdge(Edge* edge, string* err);
-  void FinishEdge(Edge* edge, bool success, const string& output);
+  void FinishCommand(CommandRunner::Result* result);
 
   /// Used for tests.
   void SetBuildLog(BuildLog* log) {
@@ -165,6 +177,9 @@ struct Builder {
   BuildStatus* status_;
 
  private:
+  bool ExtractDeps(CommandRunner::Result* result, const string& deps_type,
+                   vector<Node*>* deps_nodes, string* err);
+
   DiskInterface* disk_interface_;
   DependencyScan scan_;
 
@@ -198,14 +213,12 @@ struct BuildStatus {
 
   int started_edges_, finished_edges_, total_edges_;
 
-  bool have_blank_line_;
-
   /// Map of running edge to time the edge started running.
   typedef map<Edge*, int> RunningEdgeMap;
   RunningEdgeMap running_edges_;
 
-  /// Whether we can do fancy terminal control codes.
-  bool smart_terminal_;
+  /// Prints progress output.
+  LinePrinter printer_;
 
   /// The custom progress status format to use.
   const char* progress_status_format_;
@@ -255,17 +268,12 @@ struct BuildStatus {
     double rate_;
     Stopwatch stopwatch_;
     const size_t N;
-    std::queue<double> times_;
+    queue<double> times_;
     int last_update_;
   };
 
   mutable RateInfo overall_rate_;
   mutable SlidingRateInfo current_rate_;
-
-#ifdef _WIN32
-  void* console_;
-#endif
 };
 
 #endif  // NINJA_BUILD_H_
-
diff --git a/src/build_log.h b/src/build_log.h
index 231bfd9..6eae89f 100644
--- a/src/build_log.h
+++ b/src/build_log.h
@@ -15,7 +15,6 @@
 #ifndef NINJA_BUILD_LOG_H_
 #define NINJA_BUILD_LOG_H_
 
-#include <map>
 #include <string>
 #include <stdio.h>
 using namespace std;
diff --git a/src/build_log_test.cc b/src/build_log_test.cc
index 2dd6500..4639bc9 100644
--- a/src/build_log_test.cc
+++ b/src/build_log_test.cc
@@ -143,15 +143,7 @@ TEST_F(BuildLogTest, Truncate) {
     log2.RecordCommand(state_.edges_[1], 20, 25);
     log2.Close();
 
-#ifndef _WIN32
-    ASSERT_EQ(0, truncate(kTestFilename, size));
-#else
-    int fh;
-    fh = _sopen(kTestFilename, _O_RDWR | _O_CREAT, _SH_DENYNO,
-                _S_IREAD | _S_IWRITE);
-    ASSERT_EQ(0, _chsize(fh, size));
-    _close(fh);
-#endif
+    ASSERT_TRUE(Truncate(kTestFilename, size, &err));
 
     BuildLog log3;
     err.clear();
diff --git a/src/build_test.cc b/src/build_test.cc
index 40a82ed..90c328a 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -15,6 +15,7 @@
 #include "build.h"
 
 #include "build_log.h"
+#include "deps_log.h"
 #include "graph.h"
 #include "test.h"
 
@@ -23,6 +24,26 @@
 // to create Nodes and Edges.
 struct PlanTest : public StateTestWithBuiltinRules {
   Plan plan_;
+
+  /// Because FindWork does not return Edges in any sort of predictable order,
+  // provide a means to get available Edges in order and in a format which is
+  // easy to write tests around.
+  void FindWorkSorted(deque<Edge*>* ret, int count) {
+    struct CompareEdgesByOutput {
+      static bool cmp(const Edge* a, const Edge* b) {
+        return a->outputs_[0]->path() < b->outputs_[0]->path();
+      }
+    };
+
+    for (int i = 0; i < count; ++i) {
+      ASSERT_TRUE(plan_.more_to_do());
+      Edge* edge = plan_.FindWork();
+      ASSERT_TRUE(edge);
+      ret->push_back(edge);
+    }
+    ASSERT_FALSE(plan_.FindWork());
+    sort(ret->begin(), ret->end(), CompareEdgesByOutput::cmp);
+  }
 };
 
 TEST_F(PlanTest, Basic) {
@@ -241,8 +262,8 @@ TEST_F(PlanTest, PoolsWithDepthTwo) {
 ));
   // Mark all the out* nodes dirty
   for (int i = 0; i < 3; ++i) {
-    GetNode("out" + string(1, '1' + i))->MarkDirty();
-    GetNode("outb" + string(1, '1' + i))->MarkDirty();
+    GetNode("out" + string(1, '1' + static_cast<char>(i)))->MarkDirty();
+    GetNode("outb" + string(1, '1' + static_cast<char>(i)))->MarkDirty();
   }
   GetNode("allTheThings")->MarkDirty();
 
@@ -250,27 +271,21 @@ TEST_F(PlanTest, PoolsWithDepthTwo) {
   EXPECT_TRUE(plan_.AddTarget(GetNode("allTheThings"), &err));
   ASSERT_EQ("", err);
 
-  // Grab the first 4 edges, out1 out2 outb1 outb2
   deque<Edge*> edges;
+  FindWorkSorted(&edges, 5);
+
   for (int i = 0; i < 4; ++i) {
-    ASSERT_TRUE(plan_.more_to_do());
-    Edge* edge = plan_.FindWork();
-    ASSERT_TRUE(edge);
+    Edge *edge = edges[i];
     ASSERT_EQ("in",  edge->inputs_[0]->path());
     string base_name(i < 2 ? "out" : "outb");
     ASSERT_EQ(base_name + string(1, '1' + (i % 2)), edge->outputs_[0]->path());
-    edges.push_back(edge);
   }
 
   // outb3 is exempt because it has an empty pool
-  ASSERT_TRUE(plan_.more_to_do());
-  Edge* edge = plan_.FindWork();
+  Edge* edge = edges[4];
   ASSERT_TRUE(edge);
   ASSERT_EQ("in",  edge->inputs_[0]->path());
   ASSERT_EQ("outb3", edge->outputs_[0]->path());
-  edges.push_back(edge);
-
-  ASSERT_FALSE(plan_.FindWork());
 
   // finish out1
   plan_.EdgeFinished(edges.front());
@@ -292,11 +307,11 @@ TEST_F(PlanTest, PoolsWithDepthTwo) {
     plan_.EdgeFinished(*it);
   }
 
-  Edge* final = plan_.FindWork();
-  ASSERT_TRUE(final);
-  ASSERT_EQ("allTheThings", final->outputs_[0]->path());
+  Edge* last = plan_.FindWork();
+  ASSERT_TRUE(last);
+  ASSERT_EQ("allTheThings", last->outputs_[0]->path());
 
-  plan_.EdgeFinished(final);
+  plan_.EdgeFinished(last);
 
   ASSERT_FALSE(plan_.more_to_do());
   ASSERT_FALSE(plan_.FindWork());
@@ -333,25 +348,28 @@ TEST_F(PlanTest, PoolWithRedundantEdges) {
 
   Edge* edge = NULL;
 
-  edge = plan_.FindWork();
-  ASSERT_TRUE(edge);
+  deque<Edge*> initial_edges;
+  FindWorkSorted(&initial_edges, 2);
+
+  edge = initial_edges[1];  // Foo first
   ASSERT_EQ("foo.cpp", edge->outputs_[0]->path());
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
+  ASSERT_FALSE(plan_.FindWork());
   ASSERT_EQ("foo.cpp", edge->inputs_[0]->path());
   ASSERT_EQ("foo.cpp", edge->inputs_[1]->path());
   ASSERT_EQ("foo.cpp.obj", edge->outputs_[0]->path());
   plan_.EdgeFinished(edge);
 
-  edge = plan_.FindWork();
-  ASSERT_TRUE(edge);
+  edge = initial_edges[0];  // Now for bar
   ASSERT_EQ("bar.cpp", edge->outputs_[0]->path());
   plan_.EdgeFinished(edge);
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
+  ASSERT_FALSE(plan_.FindWork());
   ASSERT_EQ("bar.cpp", edge->inputs_[0]->path());
   ASSERT_EQ("bar.cpp", edge->inputs_[1]->path());
   ASSERT_EQ("bar.cpp.obj", edge->outputs_[0]->path());
@@ -359,6 +377,7 @@ TEST_F(PlanTest, PoolWithRedundantEdges) {
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
+  ASSERT_FALSE(plan_.FindWork());
   ASSERT_EQ("foo.cpp.obj", edge->inputs_[0]->path());
   ASSERT_EQ("bar.cpp.obj", edge->inputs_[1]->path());
   ASSERT_EQ("libfoo.a", edge->outputs_[0]->path());
@@ -366,6 +385,7 @@ TEST_F(PlanTest, PoolWithRedundantEdges) {
 
   edge = plan_.FindWork();
   ASSERT_TRUE(edge);
+  ASSERT_FALSE(plan_.FindWork());
   ASSERT_EQ("libfoo.a", edge->inputs_[0]->path());
   ASSERT_EQ("all", edge->outputs_[0]->path());
   plan_.EdgeFinished(edge);
@@ -375,20 +395,40 @@ TEST_F(PlanTest, PoolWithRedundantEdges) {
   ASSERT_FALSE(plan_.more_to_do());
 }
 
+/// Fake implementation of CommandRunner, useful for tests.
+struct FakeCommandRunner : public CommandRunner {
+  explicit FakeCommandRunner(VirtualFileSystem* fs) :
+      last_command_(NULL), fs_(fs) {}
+
+  // CommandRunner impl
+  virtual bool CanRunMore();
+  virtual bool StartCommand(Edge* edge);
+  virtual bool WaitForCommand(Result* result);
+  virtual vector<Edge*> GetActiveEdges();
+  virtual void Abort();
+
+  vector<string> commands_ran_;
+  Edge* last_command_;
+  VirtualFileSystem* fs_;
+};
+
+struct BuildTest : public StateTestWithBuiltinRules {
+  BuildTest() : config_(MakeConfig()), command_runner_(&fs_),
+                builder_(&state_, config_, NULL, NULL, &fs_),
+                status_(config_) {
+  }
+
+  virtual void SetUp() {
+    StateTestWithBuiltinRules::SetUp();
 
-struct BuildTest : public StateTestWithBuiltinRules,
-                   public CommandRunner {
-  BuildTest() : config_(MakeConfig()),
-                builder_(&state_, config_, NULL, &fs_),
-                now_(1), last_command_(NULL), status_(config_) {
-    builder_.command_runner_.reset(this);
+    builder_.command_runner_.reset(&command_runner_);
     AssertParse(&state_,
 "build cat1: cat in1\n"
 "build cat2: cat in1 in2\n"
 "build cat12: cat cat1 cat2\n");
 
-    fs_.Create("in1", now_, "");
-    fs_.Create("in2", now_, "");
+    fs_.Create("in1", "");
+    fs_.Create("in2", "");
   }
 
   ~BuildTest() {
@@ -398,13 +438,6 @@ struct BuildTest : public StateTestWithBuiltinRules,
   // Mark a path dirty.
   void Dirty(const string& path);
 
-  // CommandRunner impl
-  virtual bool CanRunMore();
-  virtual bool StartCommand(Edge* edge);
-  virtual Edge* WaitForCommand(ExitStatus* status, string* output);
-  virtual vector<Edge*> GetActiveEdges();
-  virtual void Abort();
-
   BuildConfig MakeConfig() {
     BuildConfig config;
     config.verbosity = BuildConfig::QUIET;
@@ -412,31 +445,19 @@ struct BuildTest : public StateTestWithBuiltinRules,
   }
 
   BuildConfig config_;
+  FakeCommandRunner command_runner_;
   VirtualFileSystem fs_;
   Builder builder_;
-  int now_;
 
-  vector<string> commands_ran_;
-  Edge* last_command_;
   BuildStatus status_;
 };
 
-void BuildTest::Dirty(const string& path) {
-  Node* node = GetNode(path);
-  node->MarkDirty();
-
-  // If it's an input file, mark that we've already stat()ed it and
-  // it's missing.
-  if (!node->in_edge())
-    node->MarkMissing();
-}
-
-bool BuildTest::CanRunMore() {
+bool FakeCommandRunner::CanRunMore() {
   // Only run one at a time.
   return last_command_ == NULL;
 }
 
-bool BuildTest::StartCommand(Edge* edge) {
+bool FakeCommandRunner::StartCommand(Edge* edge) {
   assert(!last_command_);
   commands_ran_.push_back(edge->EvaluateCommand());
   if (edge->rule().name() == "cat"  ||
@@ -446,7 +467,7 @@ bool BuildTest::StartCommand(Edge* edge) {
       edge->rule().name() == "touch-interrupt") {
     for (vector<Node*>::iterator out = edge->outputs_.begin();
          out != edge->outputs_.end(); ++out) {
-      fs_.Create((*out)->path(), now_, "");
+      fs_->Create((*out)->path(), "");
     }
   } else if (edge->rule().name() == "true" ||
              edge->rule().name() == "fail" ||
@@ -461,36 +482,48 @@ bool BuildTest::StartCommand(Edge* edge) {
   return true;
 }
 
-Edge* BuildTest::WaitForCommand(ExitStatus* status, string* /* output */) {
-  if (Edge* edge = last_command_) {
-    if (edge->rule().name() == "interrupt" ||
-        edge->rule().name() == "touch-interrupt") {
-      *status = ExitInterrupted;
-      return NULL;
-    }
+bool FakeCommandRunner::WaitForCommand(Result* result) {
+  if (!last_command_)
+    return false;
 
-    if (edge->rule().name() == "fail")
-      *status = ExitFailure;
-    else
-      *status = ExitSuccess;
-    last_command_ = NULL;
-    return edge;
+  Edge* edge = last_command_;
+  result->edge = edge;
+
+  if (edge->rule().name() == "interrupt" ||
+      edge->rule().name() == "touch-interrupt") {
+    result->status = ExitInterrupted;
+    return true;
   }
-  *status = ExitFailure;
-  return NULL;
+
+  if (edge->rule().name() == "fail")
+    result->status = ExitFailure;
+  else
+    result->status = ExitSuccess;
+  last_command_ = NULL;
+  return true;
 }
 
-vector<Edge*> BuildTest::GetActiveEdges() {
+vector<Edge*> FakeCommandRunner::GetActiveEdges() {
   vector<Edge*> edges;
   if (last_command_)
     edges.push_back(last_command_);
   return edges;
 }
 
-void BuildTest::Abort() {
+void FakeCommandRunner::Abort() {
   last_command_ = NULL;
 }
 
+void BuildTest::Dirty(const string& path) {
+  Node* node = GetNode(path);
+  node->MarkDirty();
+
+  // If it's an input file, mark that we've already stat()ed it and
+  // it's missing.
+  if (!node->in_edge())
+    node->MarkMissing();
+}
+
 TEST_F(BuildTest, NoWork) {
   string err;
   EXPECT_TRUE(builder_.AlreadyUpToDate());
@@ -506,8 +539,8 @@ TEST_F(BuildTest, OneStep) {
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
 
-  ASSERT_EQ(1u, commands_ran_.size());
-  EXPECT_EQ("cat in1 > cat1", commands_ran_[0]);
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in1 > cat1", command_runner_.commands_ran_[0]);
 }
 
 TEST_F(BuildTest, OneStep2) {
@@ -520,8 +553,8 @@ TEST_F(BuildTest, OneStep2) {
   EXPECT_TRUE(builder_.Build(&err));
   EXPECT_EQ("", err);
 
-  ASSERT_EQ(1u, commands_ran_.size());
-  EXPECT_EQ("cat in1 > cat1", commands_ran_[0]);
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in1 > cat1", command_runner_.commands_ran_[0]);
 }
 
 TEST_F(BuildTest, TwoStep) {
@@ -530,29 +563,29 @@ TEST_F(BuildTest, TwoStep) {
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
   EXPECT_EQ("", err);
-  ASSERT_EQ(3u, commands_ran_.size());
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
   // Depending on how the pointers work out, we could've ran
   // the first two commands in either order.
-  EXPECT_TRUE((commands_ran_[0] == "cat in1 > cat1" &&
-               commands_ran_[1] == "cat in1 in2 > cat2") ||
-              (commands_ran_[1] == "cat in1 > cat1" &&
-               commands_ran_[0] == "cat in1 in2 > cat2"));
+  EXPECT_TRUE((command_runner_.commands_ran_[0] == "cat in1 > cat1" &&
+               command_runner_.commands_ran_[1] == "cat in1 in2 > cat2") ||
+              (command_runner_.commands_ran_[1] == "cat in1 > cat1" &&
+               command_runner_.commands_ran_[0] == "cat in1 in2 > cat2"));
 
-  EXPECT_EQ("cat cat1 cat2 > cat12", commands_ran_[2]);
+  EXPECT_EQ("cat cat1 cat2 > cat12", command_runner_.commands_ran_[2]);
 
-  now_++;
+  fs_.Tick();
 
   // Modifying in2 requires rebuilding one intermediate file
   // and the final file.
-  fs_.Create("in2", now_, "");
+  fs_.Create("in2", "");
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("cat12", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  ASSERT_EQ(5u, commands_ran_.size());
-  EXPECT_EQ("cat in1 in2 > cat2", commands_ran_[3]);
-  EXPECT_EQ("cat cat1 cat2 > cat12", commands_ran_[4]);
+  ASSERT_EQ(5u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in1 in2 > cat2", command_runner_.commands_ran_[3]);
+  EXPECT_EQ("cat cat1 cat2 > cat12", command_runner_.commands_ran_[4]);
 }
 
 TEST_F(BuildTest, TwoOutputs) {
@@ -561,15 +594,15 @@ TEST_F(BuildTest, TwoOutputs) {
 "  command = touch $out\n"
 "build out1 out2: touch in.txt\n"));
 
-  fs_.Create("in.txt", now_, "");
+  fs_.Create("in.txt", "");
 
   string err;
   EXPECT_TRUE(builder_.AddTarget("out1", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
   EXPECT_EQ("", err);
-  ASSERT_EQ(1u, commands_ran_.size());
-  EXPECT_EQ("touch out1 out2", commands_ran_[0]);
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("touch out1 out2", command_runner_.commands_ran_[0]);
 }
 
 // Test case from
@@ -581,8 +614,9 @@ TEST_F(BuildTest, MultiOutIn) {
 "build in1 otherfile: touch in\n"
 "build out: touch in | in1\n"));
 
-  fs_.Create("in", now_, "");
-  fs_.Create("in1", ++now_, "");
+  fs_.Create("in", "");
+  fs_.Tick();
+  fs_.Create("in1", "");
 
   string err;
   EXPECT_TRUE(builder_.AddTarget("out", &err));
@@ -598,33 +632,33 @@ TEST_F(BuildTest, Chain) {
 "build c4: cat c3\n"
 "build c5: cat c4\n"));
 
-  fs_.Create("c1", now_, "");
+  fs_.Create("c1", "");
 
   string err;
   EXPECT_TRUE(builder_.AddTarget("c5", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
   EXPECT_EQ("", err);
-  ASSERT_EQ(4u, commands_ran_.size());
+  ASSERT_EQ(4u, command_runner_.commands_ran_.size());
 
   err.clear();
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("c5", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.AlreadyUpToDate());
 
-  now_++;
+  fs_.Tick();
 
-  fs_.Create("c3", now_, "");
+  fs_.Create("c3", "");
   err.clear();
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("c5", &err));
   ASSERT_EQ("", err);
   EXPECT_FALSE(builder_.AlreadyUpToDate());
   EXPECT_TRUE(builder_.Build(&err));
-  ASSERT_EQ(2u, commands_ran_.size());  // 3->4, 4->5
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size());  // 3->4, 4->5
 }
 
 TEST_F(BuildTest, MissingInput) {
@@ -657,7 +691,6 @@ TEST_F(BuildTest, MakeDirs) {
 #endif
 
   EXPECT_EQ("", err);
-  now_ = 0;  // Make all stat()s return file not found.
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
   ASSERT_EQ(2u, fs_.directories_made_.size());
@@ -674,7 +707,7 @@ TEST_F(BuildTest, DepFileMissing) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "rule cc\n  command = cc $in\n  depfile = $out.d\n"
 "build foo.o: cc foo.c\n"));
-  fs_.Create("foo.c", now_, "");
+  fs_.Create("foo.c", "");
 
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   ASSERT_EQ("", err);
@@ -690,9 +723,9 @@ TEST_F(BuildTest, DepFileOK) {
 "build foo.o: cc foo.c\n"));
   Edge* edge = state_.edges_.back();
 
-  fs_.Create("foo.c", now_, "");
+  fs_.Create("foo.c", "");
   GetNode("bar.h")->MarkDirty();  // Mark bar.h as missing.
-  fs_.Create("foo.o.d", now_, "foo.o: blah.h bar.h\n");
+  fs_.Create("foo.o.d", "foo.o: blah.h bar.h\n");
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   ASSERT_EQ("", err);
   ASSERT_EQ(1u, fs_.files_read_.size());
@@ -713,8 +746,8 @@ TEST_F(BuildTest, DepFileParseError) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "rule cc\n  command = cc $in\n  depfile = $out.d\n"
 "build foo.o: cc foo.c\n"));
-  fs_.Create("foo.c", now_, "");
-  fs_.Create("foo.o.d", now_, "randomtext\n");
+  fs_.Create("foo.c", "");
+  fs_.Create("foo.o.d", "randomtext\n");
   EXPECT_FALSE(builder_.AddTarget("foo.o", &err));
   EXPECT_EQ("expected depfile 'foo.o.d' to mention 'foo.o', got 'randomtext'",
             err);
@@ -727,9 +760,9 @@ TEST_F(BuildTest, OrderOnlyDeps) {
 "build foo.o: cc foo.c || otherfile\n"));
   Edge* edge = state_.edges_.back();
 
-  fs_.Create("foo.c", now_, "");
-  fs_.Create("otherfile", now_, "");
-  fs_.Create("foo.o.d", now_, "foo.o: blah.h bar.h\n");
+  fs_.Create("foo.c", "");
+  fs_.Create("otherfile", "");
+  fs_.Create("foo.o.d", "foo.o: blah.h bar.h\n");
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   ASSERT_EQ("", err);
 
@@ -750,25 +783,31 @@ TEST_F(BuildTest, OrderOnlyDeps) {
   // explicit dep dirty, expect a rebuild.
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
 
-  now_++;
+  fs_.Tick();
+
+  // Recreate the depfile, as it should have been deleted by the build.
+  fs_.Create("foo.o.d", "foo.o: blah.h bar.h\n");
 
   // implicit dep dirty, expect a rebuild.
-  fs_.Create("blah.h", now_, "");
-  fs_.Create("bar.h", now_, "");
-  commands_ran_.clear();
+  fs_.Create("blah.h", "");
+  fs_.Create("bar.h", "");
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+
+  fs_.Tick();
 
-  now_++;
+  // Recreate the depfile, as it should have been deleted by the build.
+  fs_.Create("foo.o.d", "foo.o: blah.h bar.h\n");
 
   // order only dep dirty, no rebuild.
-  fs_.Create("otherfile", now_, "");
-  commands_ran_.clear();
+  fs_.Create("otherfile", "");
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_EQ("", err);
@@ -776,12 +815,12 @@ TEST_F(BuildTest, OrderOnlyDeps) {
 
   // implicit dep missing, expect rebuild.
   fs_.RemoveFile("bar.h");
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
 }
 
 TEST_F(BuildTest, RebuildOrderOnlyDeps) {
@@ -792,17 +831,17 @@ TEST_F(BuildTest, RebuildOrderOnlyDeps) {
 "build oo.h: cc oo.h.in\n"
 "build foo.o: cc foo.c || oo.h\n"));
 
-  fs_.Create("foo.c", now_, "");
-  fs_.Create("oo.h.in", now_, "");
+  fs_.Create("foo.c", "");
+  fs_.Create("oo.h.in", "");
 
   // foo.o and order-only dep dirty, build both.
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  ASSERT_EQ(2u, commands_ran_.size());
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size());
 
   // all clean, no rebuild.
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_EQ("", err);
@@ -810,25 +849,25 @@ TEST_F(BuildTest, RebuildOrderOnlyDeps) {
 
   // order-only dep missing, build it only.
   fs_.RemoveFile("oo.h");
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  ASSERT_EQ(1u, commands_ran_.size());
-  ASSERT_EQ("cc oo.h.in", commands_ran_[0]);
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  ASSERT_EQ("cc oo.h.in", command_runner_.commands_ran_[0]);
 
-  now_++;
+  fs_.Tick();
 
   // order-only dep dirty, build it only.
-  fs_.Create("oo.h.in", now_, "");
-  commands_ran_.clear();
+  fs_.Create("oo.h.in", "");
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("foo.o", &err));
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  ASSERT_EQ(1u, commands_ran_.size());
-  ASSERT_EQ("cc oo.h.in", commands_ran_[0]);
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  ASSERT_EQ("cc oo.h.in", command_runner_.commands_ran_[0]);
 }
 
 TEST_F(BuildTest, Phony) {
@@ -836,7 +875,7 @@ TEST_F(BuildTest, Phony) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build out: cat bar.cc\n"
 "build all: phony out\n"));
-  fs_.Create("bar.cc", now_, "");
+  fs_.Create("bar.cc", "");
 
   EXPECT_TRUE(builder_.AddTarget("all", &err));
   ASSERT_EQ("", err);
@@ -845,7 +884,7 @@ TEST_F(BuildTest, Phony) {
   EXPECT_FALSE(builder_.AlreadyUpToDate());
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
 }
 
 TEST_F(BuildTest, PhonyNoWork) {
@@ -853,8 +892,8 @@ TEST_F(BuildTest, PhonyNoWork) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build out: cat bar.cc\n"
 "build all: phony out\n"));
-  fs_.Create("bar.cc", now_, "");
-  fs_.Create("out", now_, "");
+  fs_.Create("bar.cc", "");
+  fs_.Create("out", "");
 
   EXPECT_TRUE(builder_.AddTarget("all", &err));
   ASSERT_EQ("", err);
@@ -872,7 +911,7 @@ TEST_F(BuildTest, Fail) {
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(builder_.Build(&err));
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
   ASSERT_EQ("subcommand failed", err);
 }
 
@@ -893,7 +932,7 @@ TEST_F(BuildTest, SwallowFailures) {
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(builder_.Build(&err));
-  ASSERT_EQ(3u, commands_ran_.size());
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
   ASSERT_EQ("subcommands failed", err);
 }
 
@@ -914,7 +953,7 @@ TEST_F(BuildTest, SwallowFailuresLimit) {
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(builder_.Build(&err));
-  ASSERT_EQ(3u, commands_ran_.size());
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
   ASSERT_EQ("cannot make progress due to previous errors", err);
 }
 
@@ -934,8 +973,8 @@ TEST_F(BuildWithLogTest, NotInLogButOnDisk) {
 
   // Create input/output that would be considered up to date when
   // not considering the command line hash.
-  fs_.Create("in", now_, "");
-  fs_.Create("out1", now_, "");
+  fs_.Create("in", "");
+  fs_.Create("out1", "");
   string err;
 
   // Because it's not in the log, it should not be up-to-date until
@@ -943,7 +982,7 @@ TEST_F(BuildWithLogTest, NotInLogButOnDisk) {
   EXPECT_TRUE(builder_.AddTarget("out1", &err));
   EXPECT_FALSE(builder_.AlreadyUpToDate());
 
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
 
   EXPECT_TRUE(builder_.AddTarget("out1", &err));
@@ -963,13 +1002,13 @@ TEST_F(BuildWithLogTest, RestatTest) {
 "build out2: true out1\n"
 "build out3: cat out2\n"));
 
-  fs_.Create("out1", now_, "");
-  fs_.Create("out2", now_, "");
-  fs_.Create("out3", now_, "");
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
+  fs_.Create("out3", "");
 
-  now_++;
+  fs_.Tick();
 
-  fs_.Create("in", now_, "");
+  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 out3 to rebuild
@@ -979,39 +1018,39 @@ TEST_F(BuildWithLogTest, RestatTest) {
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
 
-  now_++;
+  fs_.Tick();
 
-  fs_.Create("in", now_, "");
+  fs_.Create("in", "");
   // "cc" touches out1, so we should build out2.  But because "true" does not
   // touch out2, we should cancel the build of out3.
   EXPECT_TRUE(builder_.AddTarget("out3", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
-  ASSERT_EQ(2u, commands_ran_.size());
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size());
 
   // If we run again, it should be a no-op, because the build log has recorded
   // that we've already built out2 with an input timestamp of 2 (from out1).
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("out3", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.AlreadyUpToDate());
 
-  now_++;
+  fs_.Tick();
 
-  fs_.Create("in", now_, "");
+  fs_.Create("in", "");
 
   // The build log entry should not, however, prevent us from rebuilding out2
   // if out1 changes.
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("out3", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
-  ASSERT_EQ(2u, commands_ran_.size());
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size());
 }
 
 TEST_F(BuildWithLogTest, RestatMissingFile) {
@@ -1028,8 +1067,8 @@ TEST_F(BuildWithLogTest, RestatMissingFile) {
 "build out1: true in\n"
 "build out2: cc out1\n"));
 
-  fs_.Create("in", now_, "");
-  fs_.Create("out2", now_, "");
+  fs_.Create("in", "");
+  fs_.Create("out2", "");
 
   // 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
@@ -1039,12 +1078,12 @@ TEST_F(BuildWithLogTest, RestatMissingFile) {
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
 
-  now_++;
-  fs_.Create("in", now_, "");
-  fs_.Create("out2", now_, "");
+  fs_.Tick();
+  fs_.Create("in", "");
+  fs_.Create("out2", "");
 
   // Run a build, expect only the first command to run.
   // It doesn't touch its output (due to being the "true" command), so
@@ -1052,7 +1091,7 @@ TEST_F(BuildWithLogTest, RestatMissingFile) {
   EXPECT_TRUE(builder_.AddTarget("out2", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
 }
 
 // Test scenario, in which an input file is removed, but output isn't changed
@@ -1069,21 +1108,21 @@ TEST_F(BuildWithLogTest, RestatMissingInput) {
     "build out2: cc out1\n"));
 
   // Create all necessary files
-  fs_.Create("in", now_, "");
+  fs_.Create("in", "");
 
   // The implicit dependencies and the depfile itself
   // are newer than the output
-  TimeStamp restat_mtime = ++now_;
-  fs_.Create("out1.d", now_, "out1: will.be.deleted restat.file\n");
-  fs_.Create("will.be.deleted", now_, "");
-  fs_.Create("restat.file", now_, "");
+  TimeStamp restat_mtime = fs_.Tick();
+  fs_.Create("out1.d", "out1: will.be.deleted restat.file\n");
+  fs_.Create("will.be.deleted", "");
+  fs_.Create("restat.file", "");
 
   // Run the build, out1 and out2 get built
   string err;
   EXPECT_TRUE(builder_.AddTarget("out2", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
-  ASSERT_EQ(2u, commands_ran_.size());
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size());
 
   // See that an entry in the logfile is created, capturing
   // the right mtime
@@ -1096,12 +1135,12 @@ TEST_F(BuildWithLogTest, RestatMissingInput) {
   fs_.RemoveFile("will.be.deleted");
 
   // Trigger the build again - only out1 gets built
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("out2", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
 
   // Check that the logfile entry remains correctly set
   log_entry = build_log_.LookupByOutput("out1");
@@ -1127,13 +1166,13 @@ TEST_F(BuildDryRun, AllCommandsShown) {
 "build out2: true out1\n"
 "build out3: cat out2\n"));
 
-  fs_.Create("out1", now_, "");
-  fs_.Create("out2", now_, "");
-  fs_.Create("out3", now_, "");
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
+  fs_.Create("out3", "");
 
-  now_++;
+  fs_.Tick();
 
-  fs_.Create("in", now_, "");
+  fs_.Create("in", "");
 
   // "cc" touches out1, so we should build out2.  But because "true" does not
   // touch out2, we should cancel the build of out3.
@@ -1141,7 +1180,7 @@ TEST_F(BuildDryRun, AllCommandsShown) {
   EXPECT_TRUE(builder_.AddTarget("out3", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
-  ASSERT_EQ(3u, commands_ran_.size());
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
 }
 
 // Test that RSP files are created when & where appropriate and deleted after
@@ -1158,13 +1197,13 @@ TEST_F(BuildTest, RspFileSuccess)
     "  rspfile = out2.rsp\n"
     "  long_command = Some very long command\n"));
 
-  fs_.Create("out1", now_, "");
-  fs_.Create("out2", now_, "");
-  fs_.Create("out3", now_, "");
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
+  fs_.Create("out3", "");
 
-  now_++;
+  fs_.Tick();
 
-  fs_.Create("in", now_, "");
+  fs_.Create("in", "");
 
   string err;
   EXPECT_TRUE(builder_.AddTarget("out1", &err));
@@ -1176,7 +1215,7 @@ TEST_F(BuildTest, RspFileSuccess)
   size_t files_removed = fs_.files_removed_.size();
 
   EXPECT_TRUE(builder_.Build(&err));
-  ASSERT_EQ(2u, commands_ran_.size()); // cat + cat_rsp
+  ASSERT_EQ(2u, command_runner_.commands_ran_.size()); // cat + cat_rsp
 
   // The RSP file was created
   ASSERT_EQ(files_created + 1, fs_.files_created_.size());
@@ -1198,9 +1237,9 @@ TEST_F(BuildTest, RspFileFailure) {
     "  rspfile = out.rsp\n"
     "  long_command = Another very long command\n"));
 
-  fs_.Create("out", now_, "");
-  now_++;
-  fs_.Create("in", now_, "");
+  fs_.Create("out", "");
+  fs_.Tick();
+  fs_.Create("in", "");
 
   string err;
   EXPECT_TRUE(builder_.AddTarget("out", &err));
@@ -1211,7 +1250,7 @@ TEST_F(BuildTest, RspFileFailure) {
 
   EXPECT_FALSE(builder_.Build(&err));
   ASSERT_EQ("subcommand failed", err);
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
 
   // The RSP file was created
   ASSERT_EQ(files_created + 1, fs_.files_created_.size());
@@ -1237,9 +1276,9 @@ TEST_F(BuildWithLogTest, RspFileCmdLineChange) {
     "  rspfile = out.rsp\n"
     "  long_command = Original very long command\n"));
 
-  fs_.Create("out", now_, "");
-  now_++;
-  fs_.Create("in", now_, "");
+  fs_.Create("out", "");
+  fs_.Tick();
+  fs_.Create("in", "");
 
   string err;
   EXPECT_TRUE(builder_.AddTarget("out", &err));
@@ -1247,10 +1286,10 @@ TEST_F(BuildWithLogTest, RspFileCmdLineChange) {
 
   // 1. Build for the 1st time (-> populate log)
   EXPECT_TRUE(builder_.Build(&err));
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
 
   // 2. Build again (no change)
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("out", &err));
   EXPECT_EQ("", err);
@@ -1265,12 +1304,12 @@ TEST_F(BuildWithLogTest, RspFileCmdLineChange) {
         log_entry->command_hash));
   log_entry->command_hash++;  // Change the command hash to something else.
   // Now expect the target to be rebuilt
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("out", &err));
   EXPECT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
-  EXPECT_EQ(1u, commands_ran_.size());
+  EXPECT_EQ(1u, command_runner_.commands_ran_.size());
 }
 
 TEST_F(BuildTest, InterruptCleanup) {
@@ -1282,11 +1321,11 @@ TEST_F(BuildTest, InterruptCleanup) {
 "build out1: interrupt in1\n"
 "build out2: touch-interrupt in2\n"));
 
-  fs_.Create("out1", now_, "");
-  fs_.Create("out2", now_, "");
-  now_++;
-  fs_.Create("in1", now_, "");
-  fs_.Create("in2", now_, "");
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
+  fs_.Tick();
+  fs_.Create("in1", "");
+  fs_.Create("in2", "");
 
   // An untouched output of an interrupted command should be retained.
   string err;
@@ -1295,7 +1334,7 @@ TEST_F(BuildTest, InterruptCleanup) {
   EXPECT_FALSE(builder_.Build(&err));
   EXPECT_EQ("interrupted by user", err);
   builder_.Cleanup();
-  EXPECT_EQ(now_-1, fs_.Stat("out1"));
+  EXPECT_GT(fs_.Stat("out1"), 0);
   err = "";
 
   // A touched output of an interrupted command should be deleted.
@@ -1312,8 +1351,8 @@ TEST_F(BuildTest, PhonyWithNoInputs) {
 "build nonexistent: phony\n"
 "build out1: cat || nonexistent\n"
 "build out2: cat nonexistent\n"));
-  fs_.Create("out1", now_, "");
-  fs_.Create("out2", now_, "");
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
 
   // out1 should be up to date even though its input is dirty, because its
   // order-only dependency has nothing to do.
@@ -1324,13 +1363,31 @@ TEST_F(BuildTest, PhonyWithNoInputs) {
 
   // out2 should still be out of date though, because its input is dirty.
   err.clear();
-  commands_ran_.clear();
+  command_runner_.commands_ran_.clear();
   state_.Reset();
   EXPECT_TRUE(builder_.AddTarget("out2", &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
   EXPECT_EQ("", err);
-  ASSERT_EQ(1u, commands_ran_.size());
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+}
+
+TEST_F(BuildTest, DepsGccWithEmptyDepfileErrorsOut) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule cc\n"
+"  command = cc\n"
+"  deps = gcc\n"
+"build out: cc\n"));
+  Dirty("out");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+  EXPECT_FALSE(builder_.AlreadyUpToDate());
+
+  EXPECT_FALSE(builder_.Build(&err));
+  ASSERT_EQ("subcommand failed", err);
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
 }
 
 TEST_F(BuildTest, StatusFormatReplacePlaceholder) {
@@ -1338,3 +1395,210 @@ TEST_F(BuildTest, StatusFormatReplacePlaceholder) {
             status_.FormatProgressStatus("[%%/s%s/t%t/r%r/u%u/f%f]"));
 }
 
+TEST_F(BuildTest, FailedDepsParse) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build bad_deps.o: cat in1\n"
+"  deps = gcc\n"
+"  depfile = in1.d\n"));
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("bad_deps.o", &err));
+  ASSERT_EQ("", err);
+
+  // These deps will fail to parse, as they should only have one
+  // path to the left of the colon.
+  fs_.Create("in1.d", "AAA BBB");
+
+  EXPECT_FALSE(builder_.Build(&err));
+  EXPECT_EQ("subcommand failed", err);
+}
+
+/// Tests of builds involving deps logs necessarily must span
+/// multiple builds.  We reuse methods on BuildTest but not the
+/// builder_ it sets up, because we want pristine objects for
+/// each build.
+struct BuildWithDepsLogTest : public BuildTest {
+  BuildWithDepsLogTest() {}
+
+  virtual void SetUp() {
+    BuildTest::SetUp();
+
+    temp_dir_.CreateAndEnter("BuildWithDepsLogTest");
+  }
+
+  virtual void TearDown() {
+    temp_dir_.Cleanup();
+  }
+
+  ScopedTempDir temp_dir_;
+
+  /// Shadow parent class builder_ so we don't accidentally use it.
+  void* builder_;
+};
+
+/// Run a straightforwad build where the deps log is used.
+TEST_F(BuildWithDepsLogTest, Straightforward) {
+  string err;
+  // Note: in1 was created by the superclass SetUp().
+  const char* manifest =
+      "build out: cat in1\n"
+      "  deps = gcc\n"
+      "  depfile = in1.d\n";
+  {
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    // Run the build once, everything should be ok.
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    builder.command_runner_.reset(&command_runner_);
+    EXPECT_TRUE(builder.AddTarget("out", &err));
+    ASSERT_EQ("", err);
+    fs_.Create("in1.d", "out: in2");
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    // The deps file should have been removed.
+    EXPECT_EQ(0, fs_.Stat("in1.d"));
+    // Recreate it for the next step.
+    fs_.Create("in1.d", "out: in2");
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+
+  {
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    // Touch the file only mentioned in the deps.
+    fs_.Tick();
+    fs_.Create("in2", "");
+
+    // Run the build again.
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.Load("ninja_deps", &state, &err));
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    builder.command_runner_.reset(&command_runner_);
+    command_runner_.commands_ran_.clear();
+    EXPECT_TRUE(builder.AddTarget("out", &err));
+    ASSERT_EQ("", err);
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    // We should have rebuilt the output due to in2 being
+    // out of date.
+    EXPECT_EQ(1u, command_runner_.commands_ran_.size());
+
+    builder.command_runner_.release();
+  }
+}
+
+/// Verify that obsolete dependency info causes a rebuild.
+/// 1) Run a successful build where everything has time t, record deps.
+/// 2) Move input/output to time t+1 -- despite files in alignment,
+///    should still need to rebuild due to deps at older time.
+TEST_F(BuildWithDepsLogTest, ObsoleteDeps) {
+  string err;
+  // Note: in1 was created by the superclass SetUp().
+  const char* manifest =
+      "build out: cat in1\n"
+      "  deps = gcc\n"
+      "  depfile = in1.d\n";
+  {
+    // Run an ordinary build that gathers dependencies.
+    fs_.Create("in1", "");
+    fs_.Create("in1.d", "out: ");
+
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    // Run the build once, everything should be ok.
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    builder.command_runner_.reset(&command_runner_);
+    EXPECT_TRUE(builder.AddTarget("out", &err));
+    ASSERT_EQ("", err);
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+
+  // Push all files one tick forward so that only the deps are out
+  // of date.
+  fs_.Tick();
+  fs_.Create("in1", "");
+  fs_.Create("out", "");
+
+  // The deps file should have been removed, so no need to timestamp it.
+  EXPECT_EQ(0, fs_.Stat("in1.d"));
+
+  {
+    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));
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    builder.command_runner_.reset(&command_runner_);
+    command_runner_.commands_ran_.clear();
+    EXPECT_TRUE(builder.AddTarget("out", &err));
+    ASSERT_EQ("", err);
+
+    // Recreate the deps file here because the build expects them to exist.
+    fs_.Create("in1.d", "out: ");
+
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    // We should have rebuilt the output due to the deps being
+    // out of date.
+    EXPECT_EQ(1u, command_runner_.commands_ran_.size());
+
+    builder.command_runner_.release();
+  }
+}
+
+TEST_F(BuildWithDepsLogTest, DepsIgnoredInDryRun) {
+  const char* manifest =
+      "build out: cat in1\n"
+      "  deps = gcc\n"
+      "  depfile = in1.d\n";
+
+  fs_.Create("out", "");
+  fs_.Tick();
+  fs_.Create("in1", "");
+
+  State state;
+  ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+  // The deps log is NULL in dry runs.
+  config_.dry_run = true;
+  Builder builder(&state, config_, NULL, NULL, &fs_);
+  builder.command_runner_.reset(&command_runner_);
+  command_runner_.commands_ran_.clear();
+
+  string err;
+  EXPECT_TRUE(builder.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder.Build(&err));
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+
+  builder.command_runner_.release();
+}
diff --git a/src/clean.cc b/src/clean.cc
index 12afb98..5d1974e 100644
--- a/src/clean.cc
+++ b/src/clean.cc
@@ -15,10 +15,7 @@
 #include "clean.h"
 
 #include <assert.h>
-#include <errno.h>
 #include <stdio.h>
-#include <string.h>
-#include <sys/stat.h>
 
 #include "disk_interface.h"
 #include "graph.h"
diff --git a/src/clean_test.cc b/src/clean_test.cc
index 5ed48da..04cff73 100644
--- a/src/clean_test.cc
+++ b/src/clean_test.cc
@@ -31,10 +31,10 @@ TEST_F(CleanTest, CleanAll) {
 "build out1: cat in1\n"
 "build in2: cat src2\n"
 "build out2: cat in2\n"));
-  fs_.Create("in1", 1, "");
-  fs_.Create("out1", 1, "");
-  fs_.Create("in2", 1, "");
-  fs_.Create("out2", 1, "");
+  fs_.Create("in1", "");
+  fs_.Create("out1", "");
+  fs_.Create("in2", "");
+  fs_.Create("out2", "");
 
   Cleaner cleaner(&state_, config_, &fs_);
 
@@ -61,10 +61,10 @@ TEST_F(CleanTest, CleanAllDryRun) {
 "build out1: cat in1\n"
 "build in2: cat src2\n"
 "build out2: cat in2\n"));
-  fs_.Create("in1", 1, "");
-  fs_.Create("out1", 1, "");
-  fs_.Create("in2", 1, "");
-  fs_.Create("out2", 1, "");
+  fs_.Create("in1", "");
+  fs_.Create("out1", "");
+  fs_.Create("in2", "");
+  fs_.Create("out2", "");
 
   config_.dry_run = true;
   Cleaner cleaner(&state_, config_, &fs_);
@@ -92,10 +92,10 @@ TEST_F(CleanTest, CleanTarget) {
 "build out1: cat in1\n"
 "build in2: cat src2\n"
 "build out2: cat in2\n"));
-  fs_.Create("in1", 1, "");
-  fs_.Create("out1", 1, "");
-  fs_.Create("in2", 1, "");
-  fs_.Create("out2", 1, "");
+  fs_.Create("in1", "");
+  fs_.Create("out1", "");
+  fs_.Create("in2", "");
+  fs_.Create("out2", "");
 
   Cleaner cleaner(&state_, config_, &fs_);
 
@@ -122,10 +122,10 @@ TEST_F(CleanTest, CleanTargetDryRun) {
 "build out1: cat in1\n"
 "build in2: cat src2\n"
 "build out2: cat in2\n"));
-  fs_.Create("in1", 1, "");
-  fs_.Create("out1", 1, "");
-  fs_.Create("in2", 1, "");
-  fs_.Create("out2", 1, "");
+  fs_.Create("in1", "");
+  fs_.Create("out1", "");
+  fs_.Create("in2", "");
+  fs_.Create("out2", "");
 
   config_.dry_run = true;
   Cleaner cleaner(&state_, config_, &fs_);
@@ -155,10 +155,10 @@ TEST_F(CleanTest, CleanRule) {
 "build out1: cat in1\n"
 "build in2: cat_e src2\n"
 "build out2: cat in2\n"));
-  fs_.Create("in1", 1, "");
-  fs_.Create("out1", 1, "");
-  fs_.Create("in2", 1, "");
-  fs_.Create("out2", 1, "");
+  fs_.Create("in1", "");
+  fs_.Create("out1", "");
+  fs_.Create("in2", "");
+  fs_.Create("out2", "");
 
   Cleaner cleaner(&state_, config_, &fs_);
 
@@ -187,10 +187,10 @@ TEST_F(CleanTest, CleanRuleDryRun) {
 "build out1: cat in1\n"
 "build in2: cat_e src2\n"
 "build out2: cat in2\n"));
-  fs_.Create("in1", 1, "");
-  fs_.Create("out1", 1, "");
-  fs_.Create("in2", 1, "");
-  fs_.Create("out2", 1, "");
+  fs_.Create("in1", "");
+  fs_.Create("out1", "");
+  fs_.Create("in2", "");
+  fs_.Create("out2", "");
 
   config_.dry_run = true;
   Cleaner cleaner(&state_, config_, &fs_);
@@ -219,15 +219,15 @@ TEST_F(CleanTest, CleanRuleGenerator) {
 "  generator = 1\n"
 "build out1: cat in1\n"
 "build out2: regen in2\n"));
-  fs_.Create("out1", 1, "");
-  fs_.Create("out2", 1, "");
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
 
   Cleaner cleaner(&state_, config_, &fs_);
   EXPECT_EQ(0, cleaner.CleanAll());
   EXPECT_EQ(1, cleaner.cleaned_files_count());
   EXPECT_EQ(1u, fs_.files_removed_.size());
 
-  fs_.Create("out1", 1, "");
+  fs_.Create("out1", "");
 
   EXPECT_EQ(0, cleaner.CleanAll(/*generator=*/true));
   EXPECT_EQ(2, cleaner.cleaned_files_count());
@@ -240,8 +240,8 @@ TEST_F(CleanTest, CleanDepFile) {
 "  command = cc $in > $out\n"
 "  depfile = $out.d\n"
 "build out1: cc in1\n"));
-  fs_.Create("out1", 1, "");
-  fs_.Create("out1.d", 1, "");
+  fs_.Create("out1", "");
+  fs_.Create("out1.d", "");
 
   Cleaner cleaner(&state_, config_, &fs_);
   EXPECT_EQ(0, cleaner.CleanAll());
@@ -255,8 +255,8 @@ TEST_F(CleanTest, CleanDepFileOnCleanTarget) {
 "  command = cc $in > $out\n"
 "  depfile = $out.d\n"
 "build out1: cc in1\n"));
-  fs_.Create("out1", 1, "");
-  fs_.Create("out1.d", 1, "");
+  fs_.Create("out1", "");
+  fs_.Create("out1.d", "");
 
   Cleaner cleaner(&state_, config_, &fs_);
   EXPECT_EQ(0, cleaner.CleanTarget("out1"));
@@ -270,8 +270,8 @@ TEST_F(CleanTest, CleanDepFileOnCleanRule) {
 "  command = cc $in > $out\n"
 "  depfile = $out.d\n"
 "build out1: cc in1\n"));
-  fs_.Create("out1", 1, "");
-  fs_.Create("out1.d", 1, "");
+  fs_.Create("out1", "");
+  fs_.Create("out1.d", "");
 
   Cleaner cleaner(&state_, config_, &fs_);
   EXPECT_EQ(0, cleaner.CleanRule("cc"));
@@ -288,8 +288,8 @@ TEST_F(CleanTest, CleanRspFile) {
 "build out1: cc in1\n"
 "  rspfile = cc1.rsp\n"
 "  rspfile_content=$in\n"));
-  fs_.Create("out1", 1, "");
-  fs_.Create("cc1.rsp", 1, "");
+  fs_.Create("out1", "");
+  fs_.Create("cc1.rsp", "");
 
   Cleaner cleaner(&state_, config_, &fs_);
   EXPECT_EQ(0, cleaner.CleanAll());
@@ -311,12 +311,12 @@ TEST_F(CleanTest, CleanRsp) {
 "build out2: cat_rsp in2\n"
 "  rspfile=out2.rsp\n"
 "  rspfile_content=$in\n"));
-  fs_.Create("in1", 1, "");
-  fs_.Create("out1", 1, "");
-  fs_.Create("in2.rsp", 1, "");
-  fs_.Create("out2.rsp", 1, "");
-  fs_.Create("in2", 1, "");
-  fs_.Create("out2", 1, "");
+  fs_.Create("in1", "");
+  fs_.Create("out1", "");
+  fs_.Create("in2.rsp", "");
+  fs_.Create("out2.rsp", "");
+  fs_.Create("in2", "");
+  fs_.Create("out2", "");
 
   Cleaner cleaner(&state_, config_, &fs_);
   ASSERT_EQ(0, cleaner.cleaned_files_count());
@@ -354,9 +354,9 @@ TEST_F(CleanTest, CleanPhony) {
 "build t1: cat\n"
 "build t2: cat\n"));
 
-  fs_.Create("phony", 1, "");
-  fs_.Create("t1", 1, "");
-  fs_.Create("t2", 1, "");
+  fs_.Create("phony", "");
+  fs_.Create("t1", "");
+  fs_.Create("t2", "");
 
   // Check that CleanAll does not remove "phony".
   Cleaner cleaner(&state_, config_, &fs_);
@@ -364,8 +364,8 @@ TEST_F(CleanTest, CleanPhony) {
   EXPECT_EQ(2, cleaner.cleaned_files_count());
   EXPECT_NE(0, fs_.Stat("phony"));
 
-  fs_.Create("t1", 1, "");
-  fs_.Create("t2", 1, "");
+  fs_.Create("t1", "");
+  fs_.Create("t2", "");
 
   // Check that CleanTarget does not remove "phony".
   EXPECT_EQ(0, cleaner.CleanTarget("phony"));
diff --git a/src/deps_log.cc b/src/deps_log.cc
new file mode 100644
index 0000000..931cc77
--- /dev/null
+++ b/src/deps_log.cc
@@ -0,0 +1,326 @@
+// Copyright 2012 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 "deps_log.h"
+
+#include <assert.h>
+#include <stdio.h>
+#include <errno.h>
+#include <string.h>
+#ifndef _WIN32
+#include <unistd.h>
+#endif
+
+#include "graph.h"
+#include "metrics.h"
+#include "state.h"
+#include "util.h"
+
+// The version is stored as 4 bytes after the signature and also serves as a
+// byte order mark. Signature and version combined are 16 bytes long.
+const char kFileSignature[] = "# ninjadeps\n";
+const int kCurrentVersion = 1;
+
+DepsLog::~DepsLog() {
+  Close();
+}
+
+bool DepsLog::OpenForWrite(const string& path, string* err) {
+  if (needs_recompaction_) {
+    Close();
+    if (!Recompact(path, err))
+      return false;
+  }
+  
+  file_ = fopen(path.c_str(), "ab");
+  if (!file_) {
+    *err = strerror(errno);
+    return false;
+  }
+  SetCloseOnExec(fileno(file_));
+
+  // Opening a file in append mode doesn't set the file pointer to the file's
+  // end on Windows. Do that explicitly.
+  fseek(file_, 0, SEEK_END);
+
+  if (ftell(file_) == 0) {
+    if (fwrite(kFileSignature, sizeof(kFileSignature) - 1, 1, file_) < 1) {
+      *err = strerror(errno);
+      return false;
+    }
+    if (fwrite(&kCurrentVersion, 4, 1, file_) < 1) {
+      *err = strerror(errno);
+      return false;
+    }
+  }
+
+  return true;
+}
+
+bool DepsLog::RecordDeps(Node* node, TimeStamp mtime,
+                         const vector<Node*>& nodes) {
+  return RecordDeps(node, mtime, nodes.size(),
+                    nodes.empty() ? NULL : (Node**)&nodes.front());
+}
+
+bool DepsLog::RecordDeps(Node* node, TimeStamp mtime,
+                         int node_count, Node** nodes) {
+  // Track whether there's any new data to be recorded.
+  bool made_change = false;
+
+  // Assign ids to all nodes that are missing one.
+  if (node->id() < 0) {
+    RecordId(node);
+    made_change = true;
+  }
+  for (int i = 0; i < node_count; ++i) {
+    if (nodes[i]->id() < 0) {
+      RecordId(nodes[i]);
+      made_change = true;
+    }
+  }
+
+  // See if the new data is different than the existing data, if any.
+  if (!made_change) {
+    Deps* deps = GetDeps(node);
+    if (!deps ||
+        deps->mtime != mtime ||
+        deps->node_count != node_count) {
+      made_change = true;
+    } else {
+      for (int i = 0; i < node_count; ++i) {
+        if (deps->nodes[i] != nodes[i]) {
+          made_change = true;
+          break;
+        }
+      }
+    }
+  }
+
+  // Don't write anything if there's no new info.
+  if (!made_change)
+    return true;
+
+  // Update on-disk representation.
+  uint16_t size = 4 * (1 + 1 + (uint16_t)node_count);
+  size |= 0x8000;  // Deps record: set high bit.
+  fwrite(&size, 2, 1, file_);
+  int id = node->id();
+  fwrite(&id, 4, 1, file_);
+  int timestamp = mtime;
+  fwrite(&timestamp, 4, 1, file_);
+  for (int i = 0; i < node_count; ++i) {
+    id = nodes[i]->id();
+    fwrite(&id, 4, 1, file_);
+  }
+
+  // Update in-memory representation.
+  Deps* deps = new Deps(mtime, node_count);
+  for (int i = 0; i < node_count; ++i)
+    deps->nodes[i] = nodes[i];
+  UpdateDeps(node->id(), deps);
+
+  return true;
+}
+
+void DepsLog::Close() {
+  if (file_)
+    fclose(file_);
+  file_ = NULL;
+}
+
+bool DepsLog::Load(const string& path, State* state, string* err) {
+  METRIC_RECORD(".ninja_deps load");
+  char buf[32 << 10];
+  FILE* f = fopen(path.c_str(), "rb");
+  if (!f) {
+    if (errno == ENOENT)
+      return true;
+    *err = strerror(errno);
+    return false;
+  }
+
+  bool valid_header = true;
+  int version = 0;
+  if (!fgets(buf, sizeof(buf), f) || fread(&version, 4, 1, f) < 1)
+    valid_header = false;
+  if (!valid_header || strcmp(buf, kFileSignature) != 0 ||
+      version != kCurrentVersion) {
+    *err = "bad deps log signature or version; starting over";
+    fclose(f);
+    unlink(path.c_str());
+    // Don't report this as a failure.  An empty deps log will cause
+    // us to rebuild the outputs anyway.
+    return true;
+  }
+
+  long offset;
+  bool read_failed = false;
+  int unique_dep_record_count = 0;
+  int total_dep_record_count = 0;
+  for (;;) {
+    offset = ftell(f);
+
+    uint16_t size;
+    if (fread(&size, 2, 1, f) < 1) {
+      if (!feof(f))
+        read_failed = true;
+      break;
+    }
+    bool is_deps = (size >> 15) != 0;
+    size = size & 0x7FFF;
+
+    if (fread(buf, size, 1, f) < 1) {
+      read_failed = true;
+      break;
+    }
+
+    if (is_deps) {
+      assert(size % 4 == 0);
+      int* deps_data = reinterpret_cast<int*>(buf);
+      int out_id = deps_data[0];
+      int mtime = deps_data[1];
+      deps_data += 2;
+      int deps_count = (size / 4) - 2;
+
+      Deps* deps = new Deps(mtime, deps_count);
+      for (int i = 0; i < deps_count; ++i) {
+        assert(deps_data[i] < (int)nodes_.size());
+        assert(nodes_[deps_data[i]]);
+        deps->nodes[i] = nodes_[deps_data[i]];
+      }
+
+      total_dep_record_count++;
+      if (!UpdateDeps(out_id, deps))
+        ++unique_dep_record_count;
+    } else {
+      StringPiece path(buf, size);
+      Node* node = state->GetNode(path);
+      assert(node->id() < 0);
+      node->set_id(nodes_.size());
+      nodes_.push_back(node);
+    }
+  }
+
+  if (read_failed) {
+    // An error occurred while loading; try to recover by truncating the
+    // file to the last fully-read record.
+    if (ferror(f)) {
+      *err = strerror(ferror(f));
+    } else {
+      *err = "premature end of file";
+    }
+    fclose(f);
+
+    if (!Truncate(path.c_str(), offset, err))
+      return false;
+
+    // The truncate succeeded; we'll just report the load error as a
+    // warning because the build can proceed.
+    *err += "; recovering";
+    return true;
+  }
+
+  fclose(f);
+
+  // Rebuild the log if there are too many dead records.
+  int kMinCompactionEntryCount = 1000;
+  int kCompactionRatio = 3;
+  if (total_dep_record_count > kMinCompactionEntryCount &&
+      total_dep_record_count > unique_dep_record_count * kCompactionRatio) {
+    needs_recompaction_ = true;
+  }
+
+  return true;
+}
+
+DepsLog::Deps* DepsLog::GetDeps(Node* node) {
+  // Abort if the node has no id (never referenced in the deps) or if
+  // there's no deps recorded for the node.
+  if (node->id() < 0 || node->id() >= (int)deps_.size())
+    return NULL;
+  return deps_[node->id()];
+}
+
+bool DepsLog::Recompact(const string& path, string* err) {
+  METRIC_RECORD(".ninja_deps recompact");
+  printf("Recompacting deps...\n");
+
+  string temp_path = path + ".recompact";
+
+  // OpenForWrite() opens for append.  Make sure it's not appending to a
+  // left-over file from a previous recompaction attempt that crashed somehow.
+  unlink(temp_path.c_str());
+
+  DepsLog new_log;
+  if (!new_log.OpenForWrite(temp_path, err))
+    return false;
+
+  // Clear all known ids so that new ones can be reassigned.  The new indices
+  // will refer to the ordering in new_log, not in the current log.
+  for (vector<Node*>::iterator i = nodes_.begin(); i != nodes_.end(); ++i)
+    (*i)->set_id(-1);
+  
+  // Write out all deps again.
+  for (int old_id = 0; old_id < (int)deps_.size(); ++old_id) {
+    Deps* deps = deps_[old_id];
+    if (!deps) continue;  // If nodes_[old_id] is a leaf, it has no deps.
+
+    if (!new_log.RecordDeps(nodes_[old_id], deps->mtime,
+                            deps->node_count, deps->nodes)) {
+      new_log.Close();
+      return false;
+    }
+  }
+
+  new_log.Close();
+
+  // All nodes now have ids that refer to new_log, so steal its data.
+  deps_.swap(new_log.deps_);
+  nodes_.swap(new_log.nodes_);
+
+  if (unlink(path.c_str()) < 0) {
+    *err = strerror(errno);
+    return false;
+  }
+
+  if (rename(temp_path.c_str(), path.c_str()) < 0) {
+    *err = strerror(errno);
+    return false;
+  }
+
+  return true;
+}
+
+bool DepsLog::UpdateDeps(int out_id, Deps* deps) {
+  if (out_id >= (int)deps_.size())
+    deps_.resize(out_id + 1);
+
+  bool delete_old = deps_[out_id] != NULL;
+  if (delete_old)
+    delete deps_[out_id];
+  deps_[out_id] = deps;
+  return delete_old;
+}
+
+bool DepsLog::RecordId(Node* node) {
+  uint16_t size = (uint16_t)node->path().size();
+  fwrite(&size, 2, 1, file_);
+  fwrite(node->path().data(), node->path().size(), 1, file_);
+
+  node->set_id(nodes_.size());
+  nodes_.push_back(node);
+
+  return true;
+}
diff --git a/src/deps_log.h b/src/deps_log.h
new file mode 100644
index 0000000..de0fe63
--- /dev/null
+++ b/src/deps_log.h
@@ -0,0 +1,110 @@
+// Copyright 2012 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_DEPS_LOG_H_
+#define NINJA_DEPS_LOG_H_
+
+#include <string>
+#include <vector>
+using namespace std;
+
+#include <stdio.h>
+
+#include "timestamp.h"
+
+struct Node;
+struct State;
+
+/// As build commands run they can output extra dependency information
+/// (e.g. header dependencies for C source) dynamically.  DepsLog collects
+/// that information at build time and uses it for subsequent builds.
+///
+/// The on-disk format is based on two primary design constraints:
+/// - it must be written to as a stream (during the build, which may be
+///   interrupted);
+/// - it can be read all at once on startup.  (Alternative designs, where
+///   it contains indexing information, were considered and discarded as
+///   too complicated to implement; if the file is small than reading it
+///   fully on startup is acceptable.)
+/// Here are some stats from the Windows Chrome dependency files, to
+/// help guide the design space.  The total text in the files sums to
+/// 90mb so some compression is warranted to keep load-time fast.
+/// There's about 10k files worth of dependencies that reference about
+/// 40k total paths totalling 2mb of unique strings.
+///
+/// Based on these stats, here's the current design.
+/// The file is structured as version header followed by a sequence of records.
+/// Each record is either a path string or a dependency list.
+/// Numbering the path strings in file order gives them dense integer ids.
+/// A dependency list maps an output id to a list of input ids.
+///
+/// Concretely, a record is:
+///    two bytes record length, high bit indicates record type
+///      (implies max record length 32k)
+///    path records contain just the string name of the path
+///    dependency records are an array of 4-byte integers
+///      [output path id, output path mtime, input path id, input path id...]
+///      (The mtime is compared against the on-disk output path mtime
+///      to verify the stored data is up-to-date.)
+/// If two records reference the same output the latter one in the file
+/// wins, allowing updates to just be appended to the file.  A separate
+/// repacking step can run occasionally to remove dead records.
+struct DepsLog {
+  DepsLog() : needs_recompaction_(false), file_(NULL) {}
+  ~DepsLog();
+
+  // Writing (build-time) interface.
+  bool OpenForWrite(const string& path, string* err);
+  bool RecordDeps(Node* node, TimeStamp mtime, const vector<Node*>& nodes);
+  bool RecordDeps(Node* node, TimeStamp mtime, int node_count, Node** nodes);
+  void Close();
+
+  // Reading (startup-time) interface.
+  struct Deps {
+    Deps(int mtime, int node_count)
+        : mtime(mtime), node_count(node_count), nodes(new Node*[node_count]) {}
+    ~Deps() { delete [] nodes; }
+    int mtime;
+    int node_count;
+    Node** nodes;
+  };
+  bool Load(const string& path, State* state, string* err);
+  Deps* GetDeps(Node* node);
+
+  /// Rewrite the known log entries, throwing away old data.
+  bool Recompact(const string& path, string* err);
+
+  /// Used for tests.
+  const vector<Node*>& nodes() const { return nodes_; }
+  const vector<Deps*>& deps() const { return deps_; }
+
+ private:
+  // Updates the in-memory representation.  Takes ownership of |deps|.
+  // Returns true if a prior deps record was deleted.
+  bool UpdateDeps(int out_id, Deps* deps);
+  // Write a node name record, assigning it an id.
+  bool RecordId(Node* node);
+
+  bool needs_recompaction_;
+  FILE* file_;
+
+  /// Maps id -> Node.
+  vector<Node*> nodes_;
+  /// Maps id -> deps of that id.
+  vector<Deps*> deps_;
+
+  friend struct DepsLogTest;
+};
+
+#endif  // NINJA_DEPS_LOG_H_
diff --git a/src/deps_log_test.cc b/src/deps_log_test.cc
new file mode 100644
index 0000000..0591736
--- /dev/null
+++ b/src/deps_log_test.cc
@@ -0,0 +1,383 @@
+// Copyright 2012 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 "deps_log.h"
+
+#include "graph.h"
+#include "util.h"
+#include "test.h"
+
+namespace {
+
+const char kTestFilename[] = "DepsLogTest-tempfile";
+
+struct DepsLogTest : public testing::Test {
+  virtual void SetUp() {
+    // In case a crashing test left a stale file behind.
+    unlink(kTestFilename);
+  }
+  virtual void TearDown() {
+    unlink(kTestFilename);
+  }
+};
+
+TEST_F(DepsLogTest, WriteRead) {
+  State state1;
+  DepsLog log1;
+  string err;
+  EXPECT_TRUE(log1.OpenForWrite(kTestFilename, &err));
+  ASSERT_EQ("", err);
+
+  {
+    vector<Node*> deps;
+    deps.push_back(state1.GetNode("foo.h"));
+    deps.push_back(state1.GetNode("bar.h"));
+    log1.RecordDeps(state1.GetNode("out.o"), 1, deps);
+
+    deps.clear();
+    deps.push_back(state1.GetNode("foo.h"));
+    deps.push_back(state1.GetNode("bar2.h"));
+    log1.RecordDeps(state1.GetNode("out2.o"), 2, deps);
+
+    DepsLog::Deps* log_deps = log1.GetDeps(state1.GetNode("out.o"));
+    ASSERT_TRUE(log_deps);
+    ASSERT_EQ(1, log_deps->mtime);
+    ASSERT_EQ(2, log_deps->node_count);
+    ASSERT_EQ("foo.h", log_deps->nodes[0]->path());
+    ASSERT_EQ("bar.h", log_deps->nodes[1]->path());
+  }
+
+  log1.Close();
+
+  State state2;
+  DepsLog log2;
+  EXPECT_TRUE(log2.Load(kTestFilename, &state2, &err));
+  ASSERT_EQ("", err);
+
+  ASSERT_EQ(log1.nodes().size(), log2.nodes().size());
+  for (int i = 0; i < (int)log1.nodes().size(); ++i) {
+    Node* node1 = log1.nodes()[i];
+    Node* node2 = log2.nodes()[i];
+    ASSERT_EQ(i, node1->id());
+    ASSERT_EQ(node1->id(), node2->id());
+  }
+
+  // Spot-check the entries in log2.
+  DepsLog::Deps* log_deps = log2.GetDeps(state2.GetNode("out2.o"));
+  ASSERT_TRUE(log_deps);
+  ASSERT_EQ(2, log_deps->mtime);
+  ASSERT_EQ(2, log_deps->node_count);
+  ASSERT_EQ("foo.h", log_deps->nodes[0]->path());
+  ASSERT_EQ("bar2.h", log_deps->nodes[1]->path());
+}
+
+// Verify that adding the same deps twice doesn't grow the file.
+TEST_F(DepsLogTest, DoubleEntry) {
+  // Write some deps to the file and grab its size.
+  int file_size;
+  {
+    State state;
+    DepsLog log;
+    string err;
+    EXPECT_TRUE(log.OpenForWrite(kTestFilename, &err));
+    ASSERT_EQ("", err);
+
+    vector<Node*> deps;
+    deps.push_back(state.GetNode("foo.h"));
+    deps.push_back(state.GetNode("bar.h"));
+    log.RecordDeps(state.GetNode("out.o"), 1, deps);
+    log.Close();
+
+    struct stat st;
+    ASSERT_EQ(0, stat(kTestFilename, &st));
+    file_size = (int)st.st_size;
+    ASSERT_GT(file_size, 0);
+  }
+
+  // Now reload the file, and readd the same deps.
+  {
+    State state;
+    DepsLog log;
+    string err;
+    EXPECT_TRUE(log.Load(kTestFilename, &state, &err));
+
+    EXPECT_TRUE(log.OpenForWrite(kTestFilename, &err));
+    ASSERT_EQ("", err);
+
+    vector<Node*> deps;
+    deps.push_back(state.GetNode("foo.h"));
+    deps.push_back(state.GetNode("bar.h"));
+    log.RecordDeps(state.GetNode("out.o"), 1, deps);
+    log.Close();
+
+    struct stat st;
+    ASSERT_EQ(0, stat(kTestFilename, &st));
+    int file_size_2 = (int)st.st_size;
+    ASSERT_EQ(file_size, file_size_2);
+  }
+}
+
+// Verify that adding the new deps works and can be compacted away.
+TEST_F(DepsLogTest, Recompact) {
+  // Write some deps to the file and grab its size.
+  int file_size;
+  {
+    State state;
+    DepsLog log;
+    string err;
+    ASSERT_TRUE(log.OpenForWrite(kTestFilename, &err));
+    ASSERT_EQ("", err);
+
+    vector<Node*> deps;
+    deps.push_back(state.GetNode("foo.h"));
+    deps.push_back(state.GetNode("bar.h"));
+    log.RecordDeps(state.GetNode("out.o"), 1, deps);
+
+    deps.clear();
+    deps.push_back(state.GetNode("foo.h"));
+    deps.push_back(state.GetNode("baz.h"));
+    log.RecordDeps(state.GetNode("other_out.o"), 1, deps);
+
+    log.Close();
+
+    struct stat st;
+    ASSERT_EQ(0, stat(kTestFilename, &st));
+    file_size = (int)st.st_size;
+    ASSERT_GT(file_size, 0);
+  }
+
+  // Now reload the file, and add slighly different deps.
+  int file_size_2;
+  {
+    State state;
+    DepsLog log;
+    string err;
+    ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
+
+    ASSERT_TRUE(log.OpenForWrite(kTestFilename, &err));
+    ASSERT_EQ("", err);
+
+    vector<Node*> deps;
+    deps.push_back(state.GetNode("foo.h"));
+    log.RecordDeps(state.GetNode("out.o"), 1, deps);
+    log.Close();
+
+    struct stat st;
+    ASSERT_EQ(0, stat(kTestFilename, &st));
+    file_size_2 = (int)st.st_size;
+    // The file should grow to record the new deps.
+    ASSERT_GT(file_size_2, file_size);
+  }
+
+  // Now reload the file, verify the new deps have replaced the old, then
+  // recompact.
+  {
+    State state;
+    DepsLog log;
+    string err;
+    ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
+
+    Node* out = state.GetNode("out.o");
+    DepsLog::Deps* deps = log.GetDeps(out);
+    ASSERT_TRUE(deps);
+    ASSERT_EQ(1, deps->mtime);
+    ASSERT_EQ(1, deps->node_count);
+    ASSERT_EQ("foo.h", deps->nodes[0]->path());
+
+    Node* other_out = state.GetNode("other_out.o");
+    deps = log.GetDeps(other_out);
+    ASSERT_TRUE(deps);
+    ASSERT_EQ(1, deps->mtime);
+    ASSERT_EQ(2, deps->node_count);
+    ASSERT_EQ("foo.h", deps->nodes[0]->path());
+    ASSERT_EQ("baz.h", deps->nodes[1]->path());
+
+    ASSERT_TRUE(log.Recompact(kTestFilename, &err));
+
+    // The in-memory deps graph should still be valid after recompaction.
+    deps = log.GetDeps(out);
+    ASSERT_TRUE(deps);
+    ASSERT_EQ(1, deps->mtime);
+    ASSERT_EQ(1, deps->node_count);
+    ASSERT_EQ("foo.h", deps->nodes[0]->path());
+    ASSERT_EQ(out, log.nodes()[out->id()]);
+
+    deps = log.GetDeps(other_out);
+    ASSERT_TRUE(deps);
+    ASSERT_EQ(1, deps->mtime);
+    ASSERT_EQ(2, deps->node_count);
+    ASSERT_EQ("foo.h", deps->nodes[0]->path());
+    ASSERT_EQ("baz.h", deps->nodes[1]->path());
+    ASSERT_EQ(other_out, log.nodes()[other_out->id()]);
+
+    // The file should have shrunk a bit for the smaller deps.
+    struct stat st;
+    ASSERT_EQ(0, stat(kTestFilename, &st));
+    int file_size_3 = (int)st.st_size;
+    ASSERT_LT(file_size_3, file_size_2);
+  }
+}
+
+// Verify that invalid file headers cause a new build.
+TEST_F(DepsLogTest, InvalidHeader) {
+  const char *kInvalidHeaders[] = {
+    "",                              // Empty file.
+    "# ninjad",                      // Truncated first line.
+    "# ninjadeps\n",                 // No version int.
+    "# ninjadeps\n\001\002",         // Truncated version int.
+    "# ninjadeps\n\001\002\003\004"  // Invalid version int.
+  };
+  for (size_t i = 0; i < sizeof(kInvalidHeaders) / sizeof(kInvalidHeaders[0]);
+       ++i) {
+    FILE* deps_log = fopen(kTestFilename, "wb");
+    ASSERT_TRUE(deps_log != NULL);
+    ASSERT_EQ(
+        strlen(kInvalidHeaders[i]),
+        fwrite(kInvalidHeaders[i], 1, strlen(kInvalidHeaders[i]), deps_log));
+    ASSERT_EQ(0 ,fclose(deps_log));
+
+    string err;
+    DepsLog log;
+    State state;
+    ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
+    EXPECT_EQ("bad deps log signature or version; starting over", err);
+  }
+}
+
+// Simulate what happens when loading a truncated log file.
+TEST_F(DepsLogTest, Truncated) {
+  // Create a file with some entries.
+  {
+    State state;
+    DepsLog log;
+    string err;
+    EXPECT_TRUE(log.OpenForWrite(kTestFilename, &err));
+    ASSERT_EQ("", err);
+
+    vector<Node*> deps;
+    deps.push_back(state.GetNode("foo.h"));
+    deps.push_back(state.GetNode("bar.h"));
+    log.RecordDeps(state.GetNode("out.o"), 1, deps);
+
+    deps.clear();
+    deps.push_back(state.GetNode("foo.h"));
+    deps.push_back(state.GetNode("bar2.h"));
+    log.RecordDeps(state.GetNode("out2.o"), 2, deps);
+
+    log.Close();
+  }
+
+  // Get the file size.
+  struct stat st;
+  ASSERT_EQ(0, stat(kTestFilename, &st));
+
+  // Try reloading at truncated sizes.
+  // Track how many nodes/deps were found; they should decrease with
+  // smaller sizes.
+  int node_count = 5;
+  int deps_count = 2;
+  for (int size = (int)st.st_size; size > 0; --size) {
+    string err;
+    ASSERT_TRUE(Truncate(kTestFilename, size, &err));
+
+    State state;
+    DepsLog log;
+    EXPECT_TRUE(log.Load(kTestFilename, &state, &err));
+    if (!err.empty()) {
+      // At some point the log will be so short as to be unparseable.
+      break;
+    }
+
+    ASSERT_GE(node_count, (int)log.nodes().size());
+    node_count = log.nodes().size();
+
+    // Count how many non-NULL deps entries there are.
+    int new_deps_count = 0;
+    for (vector<DepsLog::Deps*>::const_iterator i = log.deps().begin();
+         i != log.deps().end(); ++i) {
+      if (*i)
+        ++new_deps_count;
+    }
+    ASSERT_GE(deps_count, new_deps_count);
+    deps_count = new_deps_count;
+  }
+}
+
+// Run the truncation-recovery logic.
+TEST_F(DepsLogTest, TruncatedRecovery) {
+  // Create a file with some entries.
+  {
+    State state;
+    DepsLog log;
+    string err;
+    EXPECT_TRUE(log.OpenForWrite(kTestFilename, &err));
+    ASSERT_EQ("", err);
+
+    vector<Node*> deps;
+    deps.push_back(state.GetNode("foo.h"));
+    deps.push_back(state.GetNode("bar.h"));
+    log.RecordDeps(state.GetNode("out.o"), 1, deps);
+
+    deps.clear();
+    deps.push_back(state.GetNode("foo.h"));
+    deps.push_back(state.GetNode("bar2.h"));
+    log.RecordDeps(state.GetNode("out2.o"), 2, deps);
+
+    log.Close();
+  }
+
+  // Shorten the file, corrupting the last record.
+  struct stat st;
+  ASSERT_EQ(0, stat(kTestFilename, &st));
+  ASSERT_EQ(0, truncate(kTestFilename, st.st_size - 2));
+
+  // Load the file again, add an entry.
+  {
+    State state;
+    DepsLog log;
+    string err;
+    EXPECT_TRUE(log.Load(kTestFilename, &state, &err));
+    ASSERT_EQ("premature end of file; recovering", err);
+    err.clear();
+
+    // The truncated entry should've been discarded.
+    EXPECT_EQ(NULL, log.GetDeps(state.GetNode("out2.o")));
+
+    EXPECT_TRUE(log.OpenForWrite(kTestFilename, &err));
+    ASSERT_EQ("", err);
+
+    // Add a new entry.
+    vector<Node*> deps;
+    deps.push_back(state.GetNode("foo.h"));
+    deps.push_back(state.GetNode("bar2.h"));
+    log.RecordDeps(state.GetNode("out2.o"), 3, deps);
+
+    log.Close();
+  }
+
+  // Load the file a third time to verify appending after a mangled
+  // entry doesn't break things.
+  {
+    State state;
+    DepsLog log;
+    string err;
+    EXPECT_TRUE(log.Load(kTestFilename, &state, &err));
+
+    // The truncated entry should exist.
+    DepsLog::Deps* deps = log.GetDeps(state.GetNode("out2.o"));
+    ASSERT_TRUE(deps);
+  }
+}
+
+}  // anonymous namespace
diff --git a/src/disk_interface.cc b/src/disk_interface.cc
index 7c557cd..ee3e99a 100644
--- a/src/disk_interface.cc
+++ b/src/disk_interface.cc
@@ -80,8 +80,10 @@ TimeStamp RealDiskInterface::Stat(const string& path) {
   // MSDN: "Naming Files, Paths, and Namespaces"
   // http://msdn.microsoft.com/en-us/library/windows/desktop/aa365247(v=vs.85).aspx
   if (!path.empty() && path[0] != '\\' && path.size() > MAX_PATH) {
-    Error("Stat(%s): Filename longer than %i characters",
-          path.c_str(), MAX_PATH);
+    if (!quiet_) {
+      Error("Stat(%s): Filename longer than %i characters",
+            path.c_str(), MAX_PATH);
+    }
     return -1;
   }
   WIN32_FILE_ATTRIBUTE_DATA attrs;
@@ -89,8 +91,10 @@ TimeStamp RealDiskInterface::Stat(const string& path) {
     DWORD err = GetLastError();
     if (err == ERROR_FILE_NOT_FOUND || err == ERROR_PATH_NOT_FOUND)
       return 0;
-    Error("GetFileAttributesEx(%s): %s", path.c_str(),
-          GetLastErrorString().c_str());
+    if (!quiet_) {
+      Error("GetFileAttributesEx(%s): %s", path.c_str(),
+            GetLastErrorString().c_str());
+    }
     return -1;
   }
   const FILETIME& filetime = attrs.ftLastWriteTime;
@@ -107,7 +111,9 @@ TimeStamp RealDiskInterface::Stat(const string& path) {
   if (stat(path.c_str(), &st) < 0) {
     if (errno == ENOENT || errno == ENOTDIR)
       return 0;
-    Error("stat(%s): %s", path.c_str(), strerror(errno));
+    if (!quiet_) {
+      Error("stat(%s): %s", path.c_str(), strerror(errno));
+    }
     return -1;
   }
   return st.st_mtime;
diff --git a/src/disk_interface.h b/src/disk_interface.h
index 55f8a21..ff1e21c 100644
--- a/src/disk_interface.h
+++ b/src/disk_interface.h
@@ -55,12 +55,16 @@ struct DiskInterface {
 
 /// Implementation of DiskInterface that actually hits the disk.
 struct RealDiskInterface : public DiskInterface {
+  RealDiskInterface() : quiet_(false) {}
   virtual ~RealDiskInterface() {}
   virtual TimeStamp Stat(const string& path);
   virtual bool MakeDir(const string& path);
   virtual bool WriteFile(const string& path, const string& contents);
   virtual string ReadFile(const string& path, string* err);
   virtual int RemoveFile(const string& path);
+
+  /// Whether to print on errors.  Used to make a test quieter.
+  bool quiet_;
 };
 
 #endif  // NINJA_DISK_INTERFACE_H_
diff --git a/src/disk_interface_test.cc b/src/disk_interface_test.cc
index c2315c7..55822a6 100644
--- a/src/disk_interface_test.cc
+++ b/src/disk_interface_test.cc
@@ -60,6 +60,7 @@ TEST_F(DiskInterfaceTest, StatMissingFile) {
 }
 
 TEST_F(DiskInterfaceTest, StatBadPath) {
+  disk_.quiet_ = true;
 #ifdef _WIN32
   string bad_path("cc:\\foo");
   EXPECT_EQ(-1, disk_.Stat(bad_path));
@@ -67,6 +68,7 @@ TEST_F(DiskInterfaceTest, StatBadPath) {
   string too_long_name(512, 'x');
   EXPECT_EQ(-1, disk_.Stat(too_long_name));
 #endif
+  disk_.quiet_ = false;
 }
 
 TEST_F(DiskInterfaceTest, StatExistingFile) {
@@ -104,7 +106,7 @@ TEST_F(DiskInterfaceTest, RemoveFile) {
 
 struct StatTest : public StateTestWithBuiltinRules,
                   public DiskInterface {
-  StatTest() : scan_(&state_, NULL, this) {}
+  StatTest() : scan_(&state_, NULL, NULL, this) {}
 
   // DiskInterface implementation.
   virtual TimeStamp Stat(const string& path);
diff --git a/src/edit_distance.cc b/src/edit_distance.cc
index 22db4fe..cc4483f 100644
--- a/src/edit_distance.cc
+++ b/src/edit_distance.cc
@@ -32,8 +32,8 @@ int EditDistance(const StringPiece& s1,
   int m = s1.len_;
   int n = s2.len_;
 
-  std::vector<int> previous(n + 1);
-  std::vector<int> current(n + 1);
+  vector<int> previous(n + 1);
+  vector<int> current(n + 1);
 
   for (int i = 0; i <= n; ++i)
     previous[i] = i;
diff --git a/src/graph.cc b/src/graph.cc
index b000c48..b245e52 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -19,6 +19,7 @@
 
 #include "build_log.h"
 #include "depfile_parser.h"
+#include "deps_log.h"
 #include "disk_interface.h"
 #include "explain.h"
 #include "manifest_parser.h"
@@ -48,6 +49,7 @@ bool Rule::IsReservedBinding(const string& var) {
   return var == "command" ||
       var == "depfile" ||
       var == "description" ||
+      var == "deps" ||
       var == "generator" ||
       var == "pool" ||
       var == "restat" ||
@@ -59,15 +61,12 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
   bool dirty = false;
   edge->outputs_ready_ = true;
 
-  string depfile = edge->GetBinding("depfile");
-  if (!depfile.empty()) {
-    if (!LoadDepFile(edge, depfile, err)) {
-      if (!err->empty())
-        return false;
-      EXPLAIN("Edge targets are dirty because depfile '%s' is missing",
-              depfile.c_str());
-      dirty = true;
-    }
+  TimeStamp deps_mtime = 0;
+  if (!dep_loader_.LoadDeps(edge, &deps_mtime, err)) {
+    if (!err->empty())
+      return false;
+    // Failed to load dependency info: rebuild to regenerate it.
+    dirty = true;
   }
 
   // Visit all inputs; we're dirty if any of the inputs are dirty.
@@ -114,7 +113,8 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
     for (vector<Node*>::iterator i = edge->outputs_.begin();
          i != edge->outputs_.end(); ++i) {
       (*i)->StatIfNecessary(disk_interface_);
-      if (RecomputeOutputDirty(edge, most_recent_input, command, *i)) {
+      if (RecomputeOutputDirty(edge, most_recent_input, deps_mtime,
+                               command, *i)) {
         dirty = true;
         break;
       }
@@ -143,6 +143,7 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
 
 bool DependencyScan::RecomputeOutputDirty(Edge* edge,
                                           Node* most_recent_input,
+                                          TimeStamp deps_mtime,
                                           const string& command,
                                           Node* output) {
   if (edge->is_phony()) {
@@ -161,28 +162,36 @@ bool DependencyScan::RecomputeOutputDirty(Edge* edge,
 
   // Dirty if the output is older than the input.
   if (most_recent_input && output->mtime() < most_recent_input->mtime()) {
+    TimeStamp output_mtime = output->mtime();
+
     // If this is a restat rule, we may have cleaned the output with a restat
     // rule in a previous run and stored the most recent input mtime in the
     // build log.  Use that mtime instead, so that the file will only be
     // considered dirty if an input was modified since the previous run.
-    TimeStamp most_recent_stamp = most_recent_input->mtime();
+    bool used_restat = false;
     if (edge->GetBindingBool("restat") && build_log() &&
         (entry = build_log()->LookupByOutput(output->path()))) {
-      if (entry->restat_mtime < most_recent_stamp) {
-        EXPLAIN("restat of output %s older than most recent input %s "
-                "(%d vs %d)",
-                output->path().c_str(), most_recent_input->path().c_str(),
-                entry->restat_mtime, most_recent_stamp);
-        return true;
-      }
-    } else {
-      EXPLAIN("output %s older than most recent input %s (%d vs %d)",
-          output->path().c_str(), most_recent_input->path().c_str(),
-          output->mtime(), most_recent_stamp);
+      output_mtime = entry->restat_mtime;
+      used_restat = true;
+    }
+
+    if (output_mtime < most_recent_input->mtime()) {
+      EXPLAIN("%soutput %s older than most recent input %s "
+              "(%d vs %d)",
+              used_restat ? "restat of " : "", output->path().c_str(),
+              most_recent_input->path().c_str(),
+              output_mtime, most_recent_input->mtime());
       return true;
     }
   }
 
+  // Dirty if the output is newer than the deps.
+  if (deps_mtime && output->mtime() > deps_mtime) {
+    EXPLAIN("stored deps info out of date for for %s (%d vs %d)",
+            output->path().c_str(), deps_mtime, output->mtime());
+    return true;
+  }
+
   // May also be dirty due to the command changing since the last build.
   // But if this is a generator rule, the command changing does not make us
   // dirty.
@@ -281,7 +290,77 @@ bool Edge::GetBindingBool(const string& key) {
   return !GetBinding(key).empty();
 }
 
-bool DependencyScan::LoadDepFile(Edge* edge, const string& path, string* err) {
+void Edge::Dump(const char* prefix) const {
+  printf("%s[ ", prefix);
+  for (vector<Node*>::const_iterator i = inputs_.begin();
+       i != inputs_.end() && *i != NULL; ++i) {
+    printf("%s ", (*i)->path().c_str());
+  }
+  printf("--%s-> ", rule_->name().c_str());
+  for (vector<Node*>::const_iterator i = outputs_.begin();
+       i != outputs_.end() && *i != NULL; ++i) {
+    printf("%s ", (*i)->path().c_str());
+  }
+  if (pool_) {
+    if (!pool_->name().empty()) {
+      printf("(in pool '%s')", pool_->name().c_str());
+    }
+  } else {
+    printf("(null pool?)");
+  }
+  printf("] 0x%p\n", this);
+}
+
+bool Edge::is_phony() const {
+  return rule_ == &State::kPhonyRule;
+}
+
+void Node::Dump(const char* prefix) const {
+  printf("%s <%s 0x%p> mtime: %d%s, (:%s), ",
+         prefix, path().c_str(), this,
+         mtime(), mtime() ? "" : " (:missing)",
+         dirty() ? " dirty" : " clean");
+  if (in_edge()) {
+    in_edge()->Dump("in-edge: ");
+  } else {
+    printf("no in-edge\n");
+  }
+  printf(" out edges:\n");
+  for (vector<Edge*>::const_iterator e = out_edges().begin();
+       e != out_edges().end() && *e != NULL; ++e) {
+    (*e)->Dump(" +- ");
+  }
+}
+
+bool ImplicitDepLoader::LoadDeps(Edge* edge, TimeStamp* mtime, string* err) {
+  string deps_type = edge->GetBinding("deps");
+  if (!deps_type.empty()) {
+    if (!LoadDepsFromLog(edge, mtime, err)) {
+      if (!err->empty())
+        return false;
+      EXPLAIN("deps for %s are missing", edge->outputs_[0]->path().c_str());
+      return false;
+    }
+    return true;
+  }
+
+  string depfile = edge->GetBinding("depfile");
+  if (!depfile.empty()) {
+    if (!LoadDepFile(edge, depfile, err)) {
+      if (!err->empty())
+        return false;
+      EXPLAIN("depfile '%s' is missing", depfile.c_str());
+      return false;
+    }
+    return true;
+  }
+
+  // No deps to load.
+  return true;
+}
+
+bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
+                                    string* err) {
   METRIC_RECORD("depfile load");
   string content = disk_interface_->ReadFile(path, err);
   if (!err->empty()) {
@@ -309,11 +388,8 @@ bool DependencyScan::LoadDepFile(Edge* edge, const string& path, string* err) {
   }
 
   // Preallocate space in edge->inputs_ to be filled in below.
-  edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
-                       depfile.ins_.size(), 0);
-  edge->implicit_deps_ += depfile.ins_.size();
   vector<Node*>::iterator implicit_dep =
-      edge->inputs_.end() - edge->order_only_deps_ - depfile.ins_.size();
+      PreallocateSpace(edge, depfile.ins_.size());
 
   // Add all its in-edges.
   for (vector<StringPiece>::iterator i = depfile.ins_.begin();
@@ -324,66 +400,50 @@ bool DependencyScan::LoadDepFile(Edge* edge, const string& path, string* err) {
     Node* node = state_->GetNode(*i);
     *implicit_dep = node;
     node->AddOutEdge(edge);
-
-    // If we don't have a edge that generates this input already,
-    // create one; this makes us not abort if the input is missing,
-    // but instead will rebuild in that circumstance.
-    if (!node->in_edge()) {
-      Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
-      node->set_in_edge(phony_edge);
-      phony_edge->outputs_.push_back(node);
-
-      // RecomputeDirty might not be called for phony_edge if a previous call
-      // to RecomputeDirty had caused the file to be stat'ed.  Because previous
-      // invocations of RecomputeDirty would have seen this node without an
-      // input edge (and therefore ready), we have to set outputs_ready_ to true
-      // to avoid a potential stuck build.  If we do call RecomputeDirty for
-      // this node, it will simply set outputs_ready_ to the correct value.
-      phony_edge->outputs_ready_ = true;
-    }
+    CreatePhonyInEdge(node);
   }
 
   return true;
 }
 
-void Edge::Dump(const char* prefix) const {
-  printf("%s[ ", prefix);
-  for (vector<Node*>::const_iterator i = inputs_.begin();
-       i != inputs_.end() && *i != NULL; ++i) {
-    printf("%s ", (*i)->path().c_str());
-  }
-  printf("--%s-> ", rule_->name().c_str());
-  for (vector<Node*>::const_iterator i = outputs_.begin();
-       i != outputs_.end() && *i != NULL; ++i) {
-    printf("%s ", (*i)->path().c_str());
-  }
-  if (pool_) {
-    if (!pool_->name().empty()) {
-      printf("(in pool '%s')", pool_->name().c_str());
-    }
-  } else {
-    printf("(null pool?)");
+bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, TimeStamp* deps_mtime,
+                                        string* err) {
+  DepsLog::Deps* deps = deps_log_->GetDeps(edge->outputs_[0]);
+  if (!deps)
+    return false;
+
+  *deps_mtime = deps->mtime;
+
+  vector<Node*>::iterator implicit_dep =
+      PreallocateSpace(edge, deps->node_count);
+  for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) {
+    *implicit_dep = deps->nodes[i];
+    CreatePhonyInEdge(*implicit_dep);
   }
-  printf("] 0x%p\n", this);
+  return true;
 }
 
-bool Edge::is_phony() const {
-  return rule_ == &State::kPhonyRule;
+vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge,
+                                                            int count) {
+  edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
+                       (size_t)count, 0);
+  edge->implicit_deps_ += count;
+  return edge->inputs_.end() - edge->order_only_deps_ - count;
 }
 
-void Node::Dump(const char* prefix) const {
-  printf("%s <%s 0x%p> mtime: %d%s, (:%s), ",
-         prefix, path().c_str(), this,
-         mtime(), mtime() ? "" : " (:missing)",
-         dirty() ? " dirty" : " clean");
-  if (in_edge()) {
-    in_edge()->Dump("in-edge: ");
-  } else {
-    printf("no in-edge\n");
-  }
-  printf(" out edges:\n");
-  for (vector<Edge*>::const_iterator e = out_edges().begin();
-       e != out_edges().end() && *e != NULL; ++e) {
-    (*e)->Dump(" +- ");
-  }
+void ImplicitDepLoader::CreatePhonyInEdge(Node* node) {
+  if (node->in_edge())
+    return;
+
+  Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
+  node->set_in_edge(phony_edge);
+  phony_edge->outputs_.push_back(node);
+
+  // RecomputeDirty might not be called for phony_edge if a previous call
+  // to RecomputeDirty had caused the file to be stat'ed.  Because previous
+  // invocations of RecomputeDirty would have seen this node without an
+  // input edge (and therefore ready), we have to set outputs_ready_ to true
+  // to avoid a potential stuck build.  If we do call RecomputeDirty for
+  // this node, it will simply set outputs_ready_ to the correct value.
+  phony_edge->outputs_ready_ = true;
 }
diff --git a/src/graph.h b/src/graph.h
index 8b93e29..428ba01 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -22,8 +22,13 @@ using namespace std;
 #include "eval_env.h"
 #include "timestamp.h"
 
+struct BuildLog;
 struct DiskInterface;
+struct DepsLog;
 struct Edge;
+struct Node;
+struct Pool;
+struct State;
 
 /// Information about a node in the dependency graph: the file, whether
 /// it's dirty, mtime, etc.
@@ -32,7 +37,8 @@ struct Node {
       : path_(path),
         mtime_(-1),
         dirty_(false),
-        in_edge_(NULL) {}
+        in_edge_(NULL),
+        id_(-1) {}
 
   /// Return true if the file exists (mtime_ got a value).
   bool Stat(DiskInterface* disk_interface);
@@ -74,6 +80,9 @@ struct Node {
   Edge* in_edge() const { return in_edge_; }
   void set_in_edge(Edge* edge) { in_edge_ = edge; }
 
+  int id() const { return id_; }
+  void set_id(int id) { id_ = id; }
+
   const vector<Edge*>& out_edges() const { return out_edges_; }
   void AddOutEdge(Edge* edge) { out_edges_.push_back(edge); }
 
@@ -98,6 +107,9 @@ private:
 
   /// All Edges that use this Node as an input.
   vector<Edge*> out_edges_;
+
+  /// A dense integer id for the node, assigned and used by DepsLog.
+  int id_;
 };
 
 /// An invokable build command and associated metadata (description, etc.).
@@ -121,11 +133,6 @@ struct Rule {
   map<string, EvalString> bindings_;
 };
 
-struct BuildLog;
-struct Node;
-struct State;
-struct Pool;
-
 /// An edge in the dependency graph; links between Nodes using Rules.
 struct Edge {
   Edge() : rule_(NULL), env_(NULL), outputs_ready_(false), implicit_deps_(0),
@@ -178,13 +185,54 @@ struct Edge {
 };
 
 
+/// ImplicitDepLoader loads implicit dependencies, as referenced via the
+/// "depfile" attribute in build files.
+struct ImplicitDepLoader {
+  ImplicitDepLoader(State* state, DepsLog* deps_log,
+                    DiskInterface* disk_interface)
+      : state_(state), disk_interface_(disk_interface), deps_log_(deps_log) {}
+
+  /// Load implicit dependencies for \a edge.  May fill in \a mtime with
+  /// the timestamp of the loaded information.
+  /// @return false on error (without filling \a err if info is just missing).
+  bool LoadDeps(Edge* edge, TimeStamp* mtime, string* err);
+
+  DepsLog* deps_log() const {
+    return deps_log_;
+  }
+
+ private:
+  /// Load implicit dependencies for \a edge from a depfile attribute.
+  /// @return false on error (without filling \a err if info is just missing).
+  bool LoadDepFile(Edge* edge, const string& path, string* err);
+
+  /// Load implicit dependencies for \a edge from the DepsLog.
+  /// @return false on error (without filling \a err if info is just missing).
+  bool LoadDepsFromLog(Edge* edge, TimeStamp* mtime, string* err);
+
+  /// Preallocate \a count spaces in the input array on \a edge, returning
+  /// an iterator pointing at the first new space.
+  vector<Node*>::iterator PreallocateSpace(Edge* edge, int count);
+
+  /// If we don't have a edge that generates this input already,
+  /// create one; this makes us not abort if the input is missing,
+  /// but instead will rebuild in that circumstance.
+  void CreatePhonyInEdge(Node* node);
+
+  State* state_;
+  DiskInterface* disk_interface_;
+  DepsLog* deps_log_;
+};
+
+
 /// DependencyScan manages the process of scanning the files in a graph
 /// and updating the dirty/outputs_ready state of all the nodes and edges.
 struct DependencyScan {
-  DependencyScan(State* state, BuildLog* build_log,
+  DependencyScan(State* state, BuildLog* build_log, DepsLog* deps_log,
                  DiskInterface* disk_interface)
-      : state_(state), build_log_(build_log),
-        disk_interface_(disk_interface) {}
+      : build_log_(build_log),
+        disk_interface_(disk_interface),
+        dep_loader_(state, deps_log, disk_interface) {}
 
   /// Examine inputs, outputs, and command lines to judge whether an edge
   /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
@@ -195,10 +243,9 @@ struct DependencyScan {
   /// Recompute whether a given single output should be marked dirty.
   /// Returns true if so.
   bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input,
+                            TimeStamp deps_mtime,
                             const string& command, Node* output);
 
-  bool LoadDepFile(Edge* edge, const string& path, string* err);
-
   BuildLog* build_log() const {
     return build_log_;
   }
@@ -206,10 +253,14 @@ struct DependencyScan {
     build_log_ = log;
   }
 
+  DepsLog* deps_log() const {
+    return dep_loader_.deps_log();
+  }
+
  private:
-  State* state_;
   BuildLog* build_log_;
   DiskInterface* disk_interface_;
+  ImplicitDepLoader dep_loader_;
 };
 
 #endif  // NINJA_GRAPH_H_
diff --git a/src/graph_test.cc b/src/graph_test.cc
index 396def4..63d5757 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -17,7 +17,7 @@
 #include "test.h"
 
 struct GraphTest : public StateTestWithBuiltinRules {
-  GraphTest() : scan_(&state_, NULL, &fs_) {}
+  GraphTest() : scan_(&state_, NULL, NULL, &fs_) {}
 
   VirtualFileSystem fs_;
   DependencyScan scan_;
@@ -26,8 +26,8 @@ struct GraphTest : public StateTestWithBuiltinRules {
 TEST_F(GraphTest, MissingImplicit) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build out: cat in | implicit\n"));
-  fs_.Create("in", 1, "");
-  fs_.Create("out", 1, "");
+  fs_.Create("in", "");
+  fs_.Create("out", "");
 
   Edge* edge = GetNode("out")->in_edge();
   string err;
@@ -43,9 +43,10 @@ TEST_F(GraphTest, MissingImplicit) {
 TEST_F(GraphTest, ModifiedImplicit) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build out: cat in | implicit\n"));
-  fs_.Create("in", 1, "");
-  fs_.Create("out", 1, "");
-  fs_.Create("implicit", 2, "");
+  fs_.Create("in", "");
+  fs_.Create("out", "");
+  fs_.Tick();
+  fs_.Create("implicit", "");
 
   Edge* edge = GetNode("out")->in_edge();
   string err;
@@ -62,10 +63,11 @@ TEST_F(GraphTest, FunkyMakefilePath) {
 "  depfile = $out.d\n"
 "  command = cat $in > $out\n"
 "build out.o: catdep foo.cc\n"));
-  fs_.Create("implicit.h", 2, "");
-  fs_.Create("foo.cc", 1, "");
-  fs_.Create("out.o.d", 1, "out.o: ./foo/../implicit.h\n");
-  fs_.Create("out.o", 1, "");
+  fs_.Create("foo.cc",  "");
+  fs_.Create("out.o.d", "out.o: ./foo/../implicit.h\n");
+  fs_.Create("out.o", "");
+  fs_.Tick();
+  fs_.Create("implicit.h", "");
 
   Edge* edge = GetNode("out.o")->in_edge();
   string err;
@@ -84,11 +86,12 @@ TEST_F(GraphTest, ExplicitImplicit) {
 "  command = cat $in > $out\n"
 "build implicit.h: cat data\n"
 "build out.o: catdep foo.cc || implicit.h\n"));
-  fs_.Create("data", 2, "");
-  fs_.Create("implicit.h", 1, "");
-  fs_.Create("foo.cc", 1, "");
-  fs_.Create("out.o.d", 1, "out.o: implicit.h\n");
-  fs_.Create("out.o", 1, "");
+  fs_.Create("implicit.h", "");
+  fs_.Create("foo.cc", "");
+  fs_.Create("out.o.d", "out.o: implicit.h\n");
+  fs_.Create("out.o", "");
+  fs_.Tick();
+  fs_.Create("data", "");
 
   Edge* edge = GetNode("out.o")->in_edge();
   string err;
@@ -107,9 +110,9 @@ TEST_F(GraphTest, PathWithCurrentDirectory) {
 "  depfile = $out.d\n"
 "  command = cat $in > $out\n"
 "build ./out.o: catdep ./foo.cc\n"));
-  fs_.Create("foo.cc", 1, "");
-  fs_.Create("out.o.d", 1, "out.o: foo.cc\n");
-  fs_.Create("out.o", 1, "");
+  fs_.Create("foo.cc", "");
+  fs_.Create("out.o.d", "out.o: foo.cc\n");
+  fs_.Create("out.o", "");
 
   Edge* edge = GetNode("out.o")->in_edge();
   string err;
@@ -151,9 +154,9 @@ TEST_F(GraphTest, DepfileWithCanonicalizablePath) {
 "  depfile = $out.d\n"
 "  command = cat $in > $out\n"
 "build ./out.o: catdep ./foo.cc\n"));
-  fs_.Create("foo.cc", 1, "");
-  fs_.Create("out.o.d", 1, "out.o: bar/../foo.cc\n");
-  fs_.Create("out.o", 1, "");
+  fs_.Create("foo.cc", "");
+  fs_.Create("out.o.d", "out.o: bar/../foo.cc\n");
+  fs_.Create("out.o", "");
 
   Edge* edge = GetNode("out.o")->in_edge();
   string err;
@@ -170,10 +173,11 @@ TEST_F(GraphTest, DepfileRemoved) {
 "  depfile = $out.d\n"
 "  command = cat $in > $out\n"
 "build ./out.o: catdep ./foo.cc\n"));
-  fs_.Create("foo.h", 1, "");
-  fs_.Create("foo.cc", 1, "");
-  fs_.Create("out.o.d", 2, "out.o: foo.h\n");
-  fs_.Create("out.o", 2, "");
+  fs_.Create("foo.h", "");
+  fs_.Create("foo.cc", "");
+  fs_.Tick();
+  fs_.Create("out.o.d", "out.o: foo.h\n");
+  fs_.Create("out.o", "");
 
   Edge* edge = GetNode("out.o")->in_edge();
   string err;
diff --git a/src/line_printer.cc b/src/line_printer.cc
new file mode 100644
index 0000000..a75eb05
--- /dev/null
+++ b/src/line_printer.cc
@@ -0,0 +1,109 @@
+// Copyright 2013 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 "line_printer.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#ifdef _WIN32
+#include <windows.h>
+#else
+#include <unistd.h>
+#include <sys/ioctl.h>
+#include <sys/time.h>
+#endif
+
+#include "util.h"
+
+LinePrinter::LinePrinter() : have_blank_line_(true) {
+#ifndef _WIN32
+  const char* term = getenv("TERM");
+  smart_terminal_ = isatty(1) && term && string(term) != "dumb";
+#else
+  // Disable output buffer.  It'd be nice to use line buffering but
+  // MSDN says: "For some systems, [_IOLBF] provides line
+  // buffering. However, for Win32, the behavior is the same as _IOFBF
+  // - Full Buffering."
+  setvbuf(stdout, NULL, _IONBF, 0);
+  console_ = GetStdHandle(STD_OUTPUT_HANDLE);
+  CONSOLE_SCREEN_BUFFER_INFO csbi;
+  smart_terminal_ = GetConsoleScreenBufferInfo(console_, &csbi);
+#endif
+}
+
+void LinePrinter::Print(string to_print, LineType type) {
+#ifdef _WIN32
+  CONSOLE_SCREEN_BUFFER_INFO csbi;
+  GetConsoleScreenBufferInfo(console_, &csbi);
+#endif
+
+  if (smart_terminal_) {
+#ifndef _WIN32
+    printf("\r");  // Print over previous line, if any.
+#else
+    csbi.dwCursorPosition.X = 0;
+    SetConsoleCursorPosition(console_, csbi.dwCursorPosition);
+#endif
+  }
+
+  if (smart_terminal_ && type == ELIDE) {
+#ifdef _WIN32
+    // Don't use the full width or console will move to next line.
+    size_t width = static_cast<size_t>(csbi.dwSize.X) - 1;
+    to_print = ElideMiddle(to_print, width);
+    // We don't want to have the cursor spamming back and forth, so
+    // use WriteConsoleOutput instead which updates the contents of
+    // the buffer, but doesn't move the cursor position.
+    GetConsoleScreenBufferInfo(console_, &csbi);
+    COORD buf_size = { csbi.dwSize.X, 1 };
+    COORD zero_zero = { 0, 0 };
+    SMALL_RECT target = {
+      csbi.dwCursorPosition.X, csbi.dwCursorPosition.Y,
+      static_cast<SHORT>(csbi.dwCursorPosition.X + csbi.dwSize.X - 1),
+      csbi.dwCursorPosition.Y
+    };
+    CHAR_INFO* char_data = new CHAR_INFO[csbi.dwSize.X];
+    memset(char_data, 0, sizeof(CHAR_INFO) * csbi.dwSize.X);
+    for (int i = 0; i < csbi.dwSize.X; ++i) {
+      char_data[i].Char.AsciiChar = ' ';
+      char_data[i].Attributes = csbi.wAttributes;
+    }
+    for (size_t i = 0; i < to_print.size(); ++i)
+      char_data[i].Char.AsciiChar = to_print[i];
+    WriteConsoleOutput(console_, char_data, buf_size, zero_zero, &target);
+    delete[] char_data;
+#else
+    // Limit output to width of the terminal if provided so we don't cause
+    // line-wrapping.
+    winsize size;
+    if ((ioctl(0, TIOCGWINSZ, &size) == 0) && size.ws_col) {
+      to_print = ElideMiddle(to_print, size.ws_col);
+    }
+    printf("%s", to_print.c_str());
+    printf("\x1B[K");  // Clear to end of line.
+    fflush(stdout);
+#endif
+
+    have_blank_line_ = false;
+  } else {
+    printf("%s\n", to_print.c_str());
+  }
+}
+
+void LinePrinter::PrintOnNewLine(const string& to_print) {
+  if (!have_blank_line_)
+    printf("\n");
+  printf("%s", to_print.c_str());
+  have_blank_line_ = to_print.empty() || *to_print.rbegin() == '\n';
+}
diff --git a/src/line_printer.h b/src/line_printer.h
new file mode 100644
index 0000000..c292464
--- /dev/null
+++ b/src/line_printer.h
@@ -0,0 +1,53 @@
+// Copyright 2013 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_LINE_PRINTER_H_
+#define NINJA_LINE_PRINTER_H_
+
+#include <string>
+using namespace std;
+
+/// Prints lines of text, possibly overprinting previously printed lines
+/// if the terminal supports it.
+class LinePrinter {
+ public:
+  LinePrinter();
+
+  bool is_smart_terminal() const { return smart_terminal_; }
+  void set_smart_terminal(bool smart) { smart_terminal_ = smart; }
+
+  enum LineType {
+    FULL,
+    ELIDE
+  };
+  /// Overprints the current line. If type is ELIDE, elides to_print to fit on
+  /// one line.
+  void Print(string to_print, LineType type);
+
+  /// Prints a string on a new line, not overprinting previous output.
+  void PrintOnNewLine(const string& to_print);
+
+ private:
+  /// Whether we can do fancy terminal control codes.
+  bool smart_terminal_;
+
+  /// Whether the caret is at the beginning of a blank line.
+  bool have_blank_line_;
+
+#ifdef _WIN32
+  void* console_;
+#endif
+};
+
+#endif  // NINJA_LINE_PRINTER_H_
diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc
index 14fca73..3593567 100644
--- a/src/manifest_parser.cc
+++ b/src/manifest_parser.cc
@@ -14,10 +14,8 @@
 
 #include "manifest_parser.h"
 
-#include <assert.h>
-#include <errno.h>
 #include <stdio.h>
-#include <string.h>
+#include <vector>
 
 #include "graph.h"
 #include "metrics.h"
@@ -329,6 +327,14 @@ bool ManifestParser::ParseEdge(string* err) {
   edge->implicit_deps_ = implicit;
   edge->order_only_deps_ = order_only;
 
+  // Multiple outputs aren't (yet?) supported with depslog.
+  string deps_type = edge->GetBinding("deps");
+  if (!deps_type.empty() && edge->outputs_.size() > 1) {
+    return lexer_.Error("multiple outputs aren't (yet?) supported by depslog; "
+                        "bring this up on the mailing list if it affects you",
+                        err);
+  }
+
   return true;
 }
 
diff --git a/src/manifest_parser.h b/src/manifest_parser.h
index a08e5af..967dfdd 100644
--- a/src/manifest_parser.h
+++ b/src/manifest_parser.h
@@ -16,13 +16,10 @@
 #define NINJA_MANIFEST_PARSER_H_
 
 #include <string>
-#include <vector>
-#include <limits>
 
 using namespace std;
 
 #include "lexer.h"
-#include "string_piece.h"
 
 struct BindingEnv;
 struct EvalString;
diff --git a/src/manifest_parser_test.cc b/src/manifest_parser_test.cc
index 4ac093f..2638edc 100644
--- a/src/manifest_parser_test.cc
+++ b/src/manifest_parser_test.cc
@@ -14,6 +14,9 @@
 
 #include "manifest_parser.h"
 
+#include <map>
+#include <vector>
+
 #include <gtest/gtest.h>
 
 #include "graph.h"
@@ -71,6 +74,7 @@ TEST_F(ParserTest, RuleAttributes) {
 "rule cat\n"
 "  command = a\n"
 "  depfile = a\n"
+"  deps = a\n"
 "  description = a\n"
 "  generator = a\n"
 "  restat = a\n"
@@ -599,6 +603,17 @@ TEST_F(ParserTest, MultipleOutputs) {
   EXPECT_EQ("", err);
 }
 
+TEST_F(ParserTest, MultipleOutputsWithDeps) {
+  State state;
+  ManifestParser parser(&state, NULL);
+  string err;
+  EXPECT_FALSE(parser.ParseTest("rule cc\n  command = foo\n  deps = gcc\n"
+                               "build a.o b.o: cc c.cc\n",
+                               &err));
+  EXPECT_EQ("input:5: multiple outputs aren't (yet?) supported by depslog; "
+            "bring this up on the mailing list if it affects you\n", err);
+}
+
 TEST_F(ParserTest, SubNinja) {
   files_["test.ninja"] =
     "var = inner\n"
@@ -689,7 +704,7 @@ TEST_F(ParserTest, DefaultStatements) {
 "default $third\n"));
 
   string err;
-  std::vector<Node*> nodes = state.DefaultNodes(&err);
+  vector<Node*> nodes = state.DefaultNodes(&err);
   EXPECT_EQ("", err);
   ASSERT_EQ(3u, nodes.size());
   EXPECT_EQ("a", nodes[0]->path());
diff --git a/src/msvc_helper-win32.cc b/src/msvc_helper-win32.cc
index fd9b671..be2a5e0 100644
--- a/src/msvc_helper-win32.cc
+++ b/src/msvc_helper-win32.cc
@@ -39,15 +39,15 @@ string Replace(const string& input, const string& find, const string& replace) {
   return result;
 }
 
+}  // anonymous namespace
+
 string EscapeForDepfile(const string& path) {
   // Depfiles don't escape single \.
   return Replace(path, " ", "\\ ");
 }
 
-}  // anonymous namespace
-
 // static
-string CLWrapper::FilterShowIncludes(const string& line) {
+string CLParser::FilterShowIncludes(const string& line) {
   static const char kMagicPrefix[] = "Note: including file: ";
   const char* in = line.c_str();
   const char* end = in + line.size();
@@ -63,14 +63,14 @@ string CLWrapper::FilterShowIncludes(const string& line) {
 }
 
 // static
-bool CLWrapper::IsSystemInclude(const string& path) {
+bool CLParser::IsSystemInclude(const string& path) {
   // TODO: this is a heuristic, perhaps there's a better way?
   return (path.find("program files") != string::npos ||
           path.find("microsoft visual studio") != string::npos);
 }
 
 // static
-bool CLWrapper::FilterInputFilename(const string& line) {
+bool CLParser::FilterInputFilename(const string& line) {
   // TODO: other extensions, like .asm?
   return EndsWith(line, ".c") ||
       EndsWith(line, ".cc") ||
@@ -78,7 +78,42 @@ bool CLWrapper::FilterInputFilename(const string& line) {
       EndsWith(line, ".cpp");
 }
 
-int CLWrapper::Run(const string& command, string* extra_output) {
+string CLParser::Parse(const string& output) {
+  string filtered_output;
+
+  // Loop over all lines in the output to process them.
+  size_t start = 0;
+  while (start < output.size()) {
+    size_t end = output.find_first_of("\r\n", start);
+    if (end == string::npos)
+      end = output.size();
+    string line = output.substr(start, end - start);
+
+    string include = FilterShowIncludes(line);
+    if (!include.empty()) {
+      include = IncludesNormalize::Normalize(include, NULL);
+      if (!IsSystemInclude(include))
+        includes_.insert(include);
+    } else if (FilterInputFilename(line)) {
+      // Drop it.
+      // TODO: if we support compiling multiple output files in a single
+      // cl.exe invocation, we should stash the filename.
+    } else {
+      filtered_output.append(line);
+      filtered_output.append("\n");
+    }
+
+    if (end < output.size() && output[end] == '\r')
+      ++end;
+    if (end < output.size() && output[end] == '\n')
+      ++end;
+    start = end;
+  }
+
+  return filtered_output;
+}
+
+int CLWrapper::Run(const string& command, string* output) {
   SECURITY_ATTRIBUTES security_attributes = {};
   security_attributes.nLength = sizeof(SECURITY_ATTRIBUTES);
   security_attributes.bInheritHandle = TRUE;
@@ -118,8 +153,7 @@ int CLWrapper::Run(const string& command, string* extra_output) {
     Win32Fatal("CloseHandle");
   }
 
-  // Read output of the subprocess and parse it.
-  string output;
+  // Read all output of the subprocess.
   DWORD read_len = 1;
   while (read_len) {
     char buf[64 << 10];
@@ -128,44 +162,12 @@ int CLWrapper::Run(const string& command, string* extra_output) {
         GetLastError() != ERROR_BROKEN_PIPE) {
       Win32Fatal("ReadFile");
     }
-    output.append(buf, read_len);
-
-    // Loop over all lines in the output and process them.
-    for (;;) {
-      size_t ofs = output.find_first_of("\r\n");
-      if (ofs == string::npos)
-        break;
-      string line = output.substr(0, ofs);
-
-      string include = FilterShowIncludes(line);
-      if (!include.empty()) {
-        include = IncludesNormalize::Normalize(include, NULL);
-        if (!IsSystemInclude(include))
-          includes_.insert(include);
-      } else if (FilterInputFilename(line)) {
-        // Drop it.
-        // TODO: if we support compiling multiple output files in a single
-        // cl.exe invocation, we should stash the filename.
-      } else {
-        if (extra_output) {
-          extra_output->append(line);
-          extra_output->append("\n");
-        } else {
-          printf("%s\n", line.c_str());
-        }
-      }
-
-      if (ofs < output.size() && output[ofs] == '\r')
-        ++ofs;
-      if (ofs < output.size() && output[ofs] == '\n')
-        ++ofs;
-      output = output.substr(ofs);
-    }
+    output->append(buf, read_len);
   }
 
+  // Wait for it to exit and grab its exit code.
   if (WaitForSingleObject(process_info.hProcess, INFINITE) == WAIT_FAILED)
     Win32Fatal("WaitForSingleObject");
-
   DWORD exit_code = 0;
   if (!GetExitCodeProcess(process_info.hProcess, &exit_code))
     Win32Fatal("GetExitCodeProcess");
@@ -178,11 +180,3 @@ int CLWrapper::Run(const string& command, string* extra_output) {
 
   return exit_code;
 }
-
-vector<string> CLWrapper::GetEscapedResult() {
-  vector<string> result;
-  for (set<string>::iterator i = includes_.begin(); i != includes_.end(); ++i) {
-    result.push_back(EscapeForDepfile(*i));
-  }
-  return result;
-}
diff --git a/src/msvc_helper.h b/src/msvc_helper.h
index 102201b..32ab606 100644
--- a/src/msvc_helper.h
+++ b/src/msvc_helper.h
@@ -17,23 +17,13 @@
 #include <vector>
 using namespace std;
 
+string EscapeForDepfile(const string& path);
+
 /// Visual Studio's cl.exe requires some massaging to work with Ninja;
 /// for example, it emits include information on stderr in a funny
-/// format when building with /showIncludes.  This class wraps a CL
-/// process and parses that output to extract the file list.
-struct CLWrapper {
-  CLWrapper() : env_block_(NULL) {}
-
-  /// Set the environment block (as suitable for CreateProcess) to be used
-  /// by Run().
-  void SetEnvBlock(void* env_block) { env_block_ = env_block; }
-
-  /// Start a process and parse its output.  Returns its exit code.
-  /// Any non-parsed output is buffered into \a extra_output if provided,
-  /// otherwise it is printed to stdout while the process runs.
-  /// Crashes (calls Fatal()) on error.
-  int Run(const string& command, string* extra_output=NULL);
-
+/// format when building with /showIncludes.  This class parses this
+/// output.
+struct CLParser {
   /// Parse a line of cl.exe output and extract /showIncludes info.
   /// If a dependency is extracted, returns a nonempty string.
   /// Exposed for testing.
@@ -50,10 +40,24 @@ struct CLWrapper {
   /// Exposed for testing.
   static bool FilterInputFilename(const string& line);
 
-  /// Fill a vector with the unique'd headers, escaped for output as a .d
-  /// file.
-  vector<string> GetEscapedResult();
+  /// Parse the full output of cl, returning the output (if any) that
+  /// should printed.
+  string Parse(const string& output);
 
-  void* env_block_;
   set<string> includes_;
 };
+
+/// Wraps a synchronous execution of a CL subprocess.
+struct CLWrapper {
+  CLWrapper() : env_block_(NULL) {}
+
+  /// Set the environment block (as suitable for CreateProcess) to be used
+  /// by Run().
+  void SetEnvBlock(void* env_block) { env_block_ = env_block; }
+
+  /// Start a process and gather its raw output.  Returns its exit code.
+  /// Crashes (calls Fatal()) on error.
+  int Run(const string& command, string* output);
+
+  void* env_block_;
+};
diff --git a/src/msvc_helper_main-win32.cc b/src/msvc_helper_main-win32.cc
index 0bbe98b..ef91450 100644
--- a/src/msvc_helper_main-win32.cc
+++ b/src/msvc_helper_main-win32.cc
@@ -44,12 +44,13 @@ void PushPathIntoEnvironment(const string& env_block) {
   }
 }
 
-void WriteDepFileOrDie(const char* object_path, CLWrapper* cl) {
+void WriteDepFileOrDie(const char* object_path, const CLParser& parse) {
   string depfile_path = string(object_path) + ".d";
   FILE* depfile = fopen(depfile_path.c_str(), "w");
   if (!depfile) {
     unlink(object_path);
-    Fatal("opening %s: %s", depfile_path.c_str(), GetLastErrorString().c_str());
+    Fatal("opening %s: %s", depfile_path.c_str(),
+          GetLastErrorString().c_str());
   }
   if (fprintf(depfile, "%s: ", object_path) < 0) {
     unlink(object_path);
@@ -57,9 +58,10 @@ void WriteDepFileOrDie(const char* object_path, CLWrapper* cl) {
     unlink(depfile_path.c_str());
     Fatal("writing %s", depfile_path.c_str());
   }
-  vector<string> headers = cl->GetEscapedResult();
-  for (vector<string>::iterator i = headers.begin(); i != headers.end(); ++i) {
-    if (fprintf(depfile, "%s\n", i->c_str()) < 0) {
+  const set<string>& headers = parse.includes_;
+  for (set<string>::const_iterator i = headers.begin();
+       i != headers.end(); ++i) {
+    if (fprintf(depfile, "%s\n", EscapeForDepfile(*i).c_str()) < 0) {
       unlink(object_path);
       fclose(depfile);
       unlink(depfile_path.c_str());
@@ -95,11 +97,6 @@ int MSVCHelperMain(int argc, char** argv) {
     }
   }
 
-  if (!output_filename) {
-    Usage();
-    Fatal("-o required");
-  }
-
   string env;
   if (envfile) {
     string err;
@@ -118,9 +115,15 @@ int MSVCHelperMain(int argc, char** argv) {
   CLWrapper cl;
   if (!env.empty())
     cl.SetEnvBlock((void*)env.data());
-  int exit_code = cl.Run(command);
+  string output;
+  int exit_code = cl.Run(command, &output);
 
-  WriteDepFileOrDie(output_filename, &cl);
+  if (output_filename) {
+    CLParser parser;
+    output = parser.Parse(output);
+    WriteDepFileOrDie(output_filename, parser);
+  }
+  printf("%s\n", output.c_str());
 
   return exit_code;
 }
diff --git a/src/msvc_helper_test.cc b/src/msvc_helper_test.cc
index 7730425..1e1cbde 100644
--- a/src/msvc_helper_test.cc
+++ b/src/msvc_helper_test.cc
@@ -19,100 +19,93 @@
 #include "test.h"
 #include "util.h"
 
-TEST(MSVCHelperTest, ShowIncludes) {
-  ASSERT_EQ("", CLWrapper::FilterShowIncludes(""));
+TEST(CLParserTest, ShowIncludes) {
+  ASSERT_EQ("", CLParser::FilterShowIncludes(""));
 
-  ASSERT_EQ("", CLWrapper::FilterShowIncludes("Sample compiler output"));
+  ASSERT_EQ("", CLParser::FilterShowIncludes("Sample compiler output"));
   ASSERT_EQ("c:\\Some Files\\foobar.h",
-            CLWrapper::FilterShowIncludes("Note: including file: "
-                                          "c:\\Some Files\\foobar.h"));
+            CLParser::FilterShowIncludes("Note: including file: "
+                                         "c:\\Some Files\\foobar.h"));
   ASSERT_EQ("c:\\initspaces.h",
-            CLWrapper::FilterShowIncludes("Note: including file:    "
-                                          "c:\\initspaces.h"));
+            CLParser::FilterShowIncludes("Note: including file:    "
+                                         "c:\\initspaces.h"));
 }
 
-TEST(MSVCHelperTest, FilterInputFilename) {
-  ASSERT_TRUE(CLWrapper::FilterInputFilename("foobar.cc"));
-  ASSERT_TRUE(CLWrapper::FilterInputFilename("foo bar.cc"));
-  ASSERT_TRUE(CLWrapper::FilterInputFilename("baz.c"));
+TEST(CLParserTest, FilterInputFilename) {
+  ASSERT_TRUE(CLParser::FilterInputFilename("foobar.cc"));
+  ASSERT_TRUE(CLParser::FilterInputFilename("foo bar.cc"));
+  ASSERT_TRUE(CLParser::FilterInputFilename("baz.c"));
 
-  ASSERT_FALSE(CLWrapper::FilterInputFilename(
+  ASSERT_FALSE(CLParser::FilterInputFilename(
                    "src\\cl_helper.cc(166) : fatal error C1075: end "
                    "of file found ..."));
 }
 
-TEST(MSVCHelperTest, Run) {
-  CLWrapper cl;
-  string output;
-  cl.Run("cmd /c \"echo foo&& echo Note: including file:  foo.h&&echo bar\"",
-         &output);
+TEST(CLParserTest, ParseSimple) {
+  CLParser parser;
+  string output = parser.Parse(
+      "foo\r\n"
+      "Note: including file:  foo.h\r\n"
+      "bar\r\n");
+
   ASSERT_EQ("foo\nbar\n", output);
-  ASSERT_EQ(1u, cl.includes_.size());
-  ASSERT_EQ("foo.h", *cl.includes_.begin());
+  ASSERT_EQ(1u, parser.includes_.size());
+  ASSERT_EQ("foo.h", *parser.includes_.begin());
 }
 
-TEST(MSVCHelperTest, RunFilenameFilter) {
-  CLWrapper cl;
-  string output;
-  cl.Run("cmd /c \"echo foo.cc&& echo cl: warning\"",
-         &output);
+TEST(CLParserTest, ParseFilenameFilter) {
+  CLParser parser;
+  string output = parser.Parse(
+      "foo.cc\r\n"
+      "cl: warning\r\n");
   ASSERT_EQ("cl: warning\n", output);
 }
 
-TEST(MSVCHelperTest, RunSystemInclude) {
-  CLWrapper cl;
-  string output;
-  cl.Run("cmd /c \"echo Note: including file: c:\\Program Files\\foo.h&&"
-         "echo Note: including file: d:\\Microsoft Visual Studio\\bar.h&&"
-         "echo Note: including file: path.h\"",
-         &output);
+TEST(CLParserTest, ParseSystemInclude) {
+  CLParser parser;
+  string output = parser.Parse(
+      "Note: including file: c:\\Program Files\\foo.h\r\n"
+      "Note: including file: d:\\Microsoft Visual Studio\\bar.h\r\n"
+      "Note: including file: path.h\r\n");
   // We should have dropped the first two includes because they look like
   // system headers.
   ASSERT_EQ("", output);
-  ASSERT_EQ(1u, cl.includes_.size());
-  ASSERT_EQ("path.h", *cl.includes_.begin());
-}
-
-TEST(MSVCHelperTest, EnvBlock) {
-  char env_block[] = "foo=bar\0";
-  CLWrapper cl;
-  cl.SetEnvBlock(env_block);
-  string output;
-  cl.Run("cmd /c \"echo foo is %foo%", &output);
-  ASSERT_EQ("foo is bar\n", output);
+  ASSERT_EQ(1u, parser.includes_.size());
+  ASSERT_EQ("path.h", *parser.includes_.begin());
 }
 
-TEST(MSVCHelperTest, DuplicatedHeader) {
-  CLWrapper cl;
-  string output;
-  cl.Run("cmd /c \"echo Note: including file: foo.h&&"
-         "echo Note: including file: bar.h&&"
-         "echo Note: including file: foo.h\"",
-         &output);
+TEST(CLParserTest, DuplicatedHeader) {
+  CLParser parser;
+  string output = parser.Parse(
+      "Note: including file: foo.h\r\n"
+      "Note: including file: bar.h\r\n"
+      "Note: including file: foo.h\r\n");
   // We should have dropped one copy of foo.h.
   ASSERT_EQ("", output);
-  ASSERT_EQ(2u, cl.includes_.size());
+  ASSERT_EQ(2u, parser.includes_.size());
 }
 
-TEST(MSVCHelperTest, DuplicatedHeaderPathConverted) {
-  CLWrapper cl;
-  string output;
-  cl.Run("cmd /c \"echo Note: including file: sub/foo.h&&"
-         "echo Note: including file: bar.h&&"
-         "echo Note: including file: sub\\foo.h\"",
-         &output);
+TEST(CLParserTest, DuplicatedHeaderPathConverted) {
+  CLParser parser;
+  string output = parser.Parse(
+      "Note: including file: sub/foo.h\r\n"
+      "Note: including file: bar.h\r\n"
+      "Note: including file: sub\\foo.h\r\n");
   // We should have dropped one copy of foo.h.
   ASSERT_EQ("", output);
-  ASSERT_EQ(2u, cl.includes_.size());
+  ASSERT_EQ(2u, parser.includes_.size());
 }
 
-TEST(MSVCHelperTest, SpacesInFilename) {
+TEST(CLParserTest, SpacesInFilename) {
+  ASSERT_EQ("sub\\some\\ sdk\\foo.h",
+            EscapeForDepfile("sub\\some sdk\\foo.h"));
+}
+
+TEST(MSVCHelperTest, EnvBlock) {
+  char env_block[] = "foo=bar\0";
   CLWrapper cl;
+  cl.SetEnvBlock(env_block);
   string output;
-  cl.Run("cmd /c \"echo Note: including file: sub\\some sdk\\foo.h",
-         &output);
-  ASSERT_EQ("", output);
-  vector<string> headers = cl.GetEscapedResult();
-  ASSERT_EQ(1u, headers.size());
-  ASSERT_EQ("sub\\some\\ sdk\\foo.h", headers[0]);
+  cl.Run("cmd /c \"echo foo is %foo%", &output);
+  ASSERT_EQ("foo is bar\r\n", output);
 }
diff --git a/src/ninja.cc b/src/ninja.cc
index 69646e1..b4797ed 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -17,8 +17,6 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
-#include <sys/stat.h>
-#include <sys/types.h>
 
 #ifdef _WIN32
 #include "getopt.h"
@@ -32,9 +30,9 @@
 #include "browse.h"
 #include "build.h"
 #include "build_log.h"
+#include "deps_log.h"
 #include "clean.h"
 #include "disk_interface.h"
-#include "edit_distance.h"
 #include "explain.h"
 #include "graph.h"
 #include "graphviz.h"
@@ -641,20 +639,13 @@ bool DebugEnable(const string& name, Globals* globals) {
   }
 }
 
-bool OpenLog(BuildLog* build_log, Globals* globals,
-             DiskInterface* disk_interface) {
-  const string build_dir =
-      globals->state->bindings_.LookupVariable("builddir");
-  const char* kLogPath = ".ninja_log";
-  string log_path = kLogPath;
-  if (!build_dir.empty()) {
-    log_path = build_dir + "/" + kLogPath;
-    if (!disk_interface->MakeDirs(log_path) && errno != EEXIST) {
-      Error("creating build directory %s: %s",
-            build_dir.c_str(), strerror(errno));
-      return false;
-    }
-  }
+/// Open the build log.
+/// @return false on error.
+bool OpenBuildLog(BuildLog* build_log, const string& build_dir,
+                  Globals* globals, DiskInterface* disk_interface) {
+  string log_path = ".ninja_log";
+  if (!build_dir.empty())
+    log_path = build_dir + "/" + log_path;
 
   string err;
   if (!build_log->Load(log_path, &err)) {
@@ -677,6 +668,36 @@ bool OpenLog(BuildLog* build_log, Globals* globals,
   return true;
 }
 
+/// Open the deps log: load it, then open for writing.
+/// @return false on error.
+bool OpenDepsLog(DepsLog* deps_log, const string& build_dir,
+                 Globals* globals, DiskInterface* disk_interface) {
+  string path = ".ninja_deps";
+  if (!build_dir.empty())
+    path = build_dir + "/" + path;
+
+  string err;
+  if (!deps_log->Load(path, globals->state, &err)) {
+    Error("loading deps log %s: %s", path.c_str(), err.c_str());
+    return false;
+  }
+  if (!err.empty()) {
+    // Hack: Load() can return a warning via err by returning true.
+    Warning("%s", err.c_str());
+    err.clear();
+  }
+
+  if (!globals->config->dry_run) {
+    if (!deps_log->OpenForWrite(path, &err)) {
+      Error("opening deps log: %s", err.c_str());
+      return false;
+    }
+  }
+
+  return true;
+}
+
+
 /// Dump the output requested by '-d stats'.
 void DumpMetrics(Globals* globals) {
   g_metrics->Report();
@@ -872,14 +893,30 @@ reload:
   if (tool && tool->when == Tool::RUN_AFTER_LOAD)
     return tool->func(&globals, argc, argv);
 
-  BuildLog build_log;
   RealDiskInterface disk_interface;
-  if (!OpenLog(&build_log, &globals, &disk_interface))
+
+  // Create the build dir if it doesn't exist.
+  const string build_dir = globals.state->bindings_.LookupVariable("builddir");
+  if (!build_dir.empty() && !config.dry_run) {
+    if (!disk_interface.MakeDirs(build_dir + "/.") &&
+        errno != EEXIST) {
+      Error("creating build directory %s: %s",
+            build_dir.c_str(), strerror(errno));
+      return 1;
+    }
+  }
+
+  BuildLog build_log;
+  if (!OpenBuildLog(&build_log, build_dir, &globals, &disk_interface))
+    return 1;
+
+  DepsLog deps_log;
+  if (!OpenDepsLog(&deps_log, build_dir, &globals, &disk_interface))
     return 1;
 
   if (!rebuilt_manifest) { // Don't get caught in an infinite loop by a rebuild
                            // target that is never up to date.
-    Builder manifest_builder(globals.state, config, &build_log,
+    Builder manifest_builder(globals.state, config, &build_log, &deps_log,
                              &disk_interface);
     if (RebuildManifest(&manifest_builder, input_file, &err)) {
       rebuilt_manifest = true;
@@ -891,7 +928,8 @@ reload:
     }
   }
 
-  Builder builder(globals.state, config, &build_log, &disk_interface);
+  Builder builder(globals.state, config, &build_log, &deps_log,
+                  &disk_interface);
   int result = RunBuild(&builder, argc, argv);
   if (g_metrics)
     DumpMetrics(&globals);
diff --git a/src/ninja_test.cc b/src/ninja_test.cc
new file mode 100644
index 0000000..31754f2
--- /dev/null
+++ b/src/ninja_test.cc
@@ -0,0 +1,89 @@
+// Copyright 2013 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 <stdarg.h>
+#include <stdio.h>
+
+#include "gtest/gtest.h"
+#include "line_printer.h"
+
+string StringPrintf(const char* format, ...) {
+  const int N = 1024;
+  char buf[N];
+
+  va_list ap;
+  va_start(ap, format);
+  vsnprintf(buf, N, format, ap);
+  va_end(ap);
+
+  return buf;
+}
+
+/// A test result printer that's less wordy than gtest's default.
+class LaconicPrinter : public testing::EmptyTestEventListener {
+ public:
+  LaconicPrinter() : tests_started_(0), test_count_(0), iteration_(0) {}
+  virtual void OnTestProgramStart(const testing::UnitTest& unit_test) {
+    test_count_ = unit_test.test_to_run_count();
+  }
+
+  virtual void OnTestIterationStart(const testing::UnitTest& test_info,
+                                    int iteration) {
+    tests_started_ = 0;
+    iteration_ = iteration;
+  }
+
+  virtual void OnTestStart(const testing::TestInfo& test_info) {
+    ++tests_started_;
+    printer_.Print(
+        StringPrintf("[%d/%d%s] %s.%s",
+                     tests_started_,
+                     test_count_,
+                     iteration_ ? StringPrintf(" iter %d", iteration_).c_str()
+                                : "",
+                     test_info.test_case_name(),
+                     test_info.name()),
+        LinePrinter::ELIDE);
+  }
+
+  virtual void OnTestPartResult(
+      const testing::TestPartResult& test_part_result) {
+    if (!test_part_result.failed())
+      return;
+    printer_.PrintOnNewLine(StringPrintf(
+        "*** Failure in %s:%d\n%s\n", test_part_result.file_name(),
+        test_part_result.line_number(), test_part_result.summary()));
+  }
+
+  virtual void OnTestProgramEnd(const testing::UnitTest& unit_test) {
+    printer_.PrintOnNewLine(unit_test.Passed() ? "passed\n" : "failed\n");
+  }
+
+ private:
+  LinePrinter printer_;
+  int tests_started_;
+  int test_count_;
+  int iteration_;
+};
+
+int main(int argc, char **argv) {
+  testing::InitGoogleTest(&argc, argv);
+
+  testing::TestEventListeners& listeners =
+      testing::UnitTest::GetInstance()->listeners();
+  delete listeners.Release(listeners.default_result_printer());
+  listeners.Append(new LaconicPrinter);
+
+  return RUN_ALL_TESTS();
+}
diff --git a/src/state.cc b/src/state.cc
index 9f46fee..9b6160b 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -154,7 +154,8 @@ void State::AddOut(Edge* edge, StringPiece path) {
   edge->outputs_.push_back(node);
   if (node->in_edge()) {
     Warning("multiple rules generate %s. "
-            "build will not be correct; continuing anyway",
+            "builds involving this target will not be correct; "
+            "continuing anyway",
             path.AsString().c_str());
   }
   node->set_in_edge(edge);
@@ -202,10 +203,11 @@ void State::Reset() {
 void State::Dump() {
   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
     Node* node = i->second;
-    printf("%s %s\n",
+    printf("%s %s [id:%d]\n",
            node->path().c_str(),
            node->status_known() ? (node->dirty() ? "dirty" : "clean")
-                                : "unknown");
+                                : "unknown",
+           node->id());
   }
   if (!pools_.empty()) {
     printf("resource_pools:\n");
diff --git a/src/state.h b/src/state.h
index 7e3aead..bde75ff 100644
--- a/src/state.h
+++ b/src/state.h
@@ -16,7 +16,6 @@
 #define NINJA_STATE_H_
 
 #include <map>
-#include <deque>
 #include <set>
 #include <string>
 #include <vector>
diff --git a/src/subprocess-posix.cc b/src/subprocess-posix.cc
index 8f1a04e..339edfe 100644
--- a/src/subprocess-posix.cc
+++ b/src/subprocess-posix.cc
@@ -14,8 +14,6 @@
 
 #include "subprocess.h"
 
-#include <algorithm>
-#include <map>
 #include <assert.h>
 #include <errno.h>
 #include <fcntl.h>
@@ -25,13 +23,6 @@
 #include <string.h>
 #include <sys/wait.h>
 
-// Older versions of glibc (like 2.4) won't find this in <poll.h>.  glibc
-// 2.4 keeps it in <asm-generic/poll.h>, though attempting to include that
-// will redefine the pollfd structure.
-#ifndef POLLRDHUP
-#define POLLRDHUP 0x2000
-#endif
-
 #include "util.h"
 
 Subprocess::Subprocess() : fd_(-1), pid_(-1) {
@@ -49,12 +40,12 @@ bool Subprocess::Start(SubprocessSet* set, const string& command) {
   if (pipe(output_pipe) < 0)
     Fatal("pipe: %s", strerror(errno));
   fd_ = output_pipe[0];
-#if !defined(linux)
-  // On linux we use ppoll in DoWork(); elsewhere we use pselect and so must
-  // avoid overly-large FDs.
+#if !defined(linux) && !defined(__OpenBSD__)
+  // On Linux and OpenBSD, we use ppoll in DoWork(); elsewhere we use pselect
+  // and so must avoid overly-large FDs.
   if (fd_ >= static_cast<int>(FD_SETSIZE))
     Fatal("pipe: %s", strerror(EMFILE));
-#endif  // !linux
+#endif  // !linux && !__OpenBSD__
   SetCloseOnExec(fd_);
 
   pid_ = fork();
@@ -155,8 +146,6 @@ void SubprocessSet::SetInterruptedFlag(int signum) {
 }
 
 SubprocessSet::SubprocessSet() {
-  interrupted_ = false;
-
   sigset_t set;
   sigemptyset(&set);
   sigaddset(&set, SIGINT);
@@ -189,7 +178,7 @@ Subprocess *SubprocessSet::Add(const string& command) {
   return subprocess;
 }
 
-#ifdef linux
+#if defined(linux) || defined(__OpenBSD__)
 bool SubprocessSet::DoWork() {
   vector<pollfd> fds;
   nfds_t nfds = 0;
@@ -199,20 +188,19 @@ bool SubprocessSet::DoWork() {
     int fd = (*i)->fd_;
     if (fd < 0)
       continue;
-    pollfd pfd = { fd, POLLIN | POLLPRI | POLLRDHUP, 0 };
+    pollfd pfd = { fd, POLLIN | POLLPRI, 0 };
     fds.push_back(pfd);
     ++nfds;
   }
 
+  interrupted_ = false;
   int ret = ppoll(&fds.front(), nfds, NULL, &old_mask_);
   if (ret == -1) {
     if (errno != EINTR) {
       perror("ninja: ppoll");
       return false;
     }
-    bool interrupted = interrupted_;
-    interrupted_ = false;
-    return interrupted;
+    return interrupted_;
   }
 
   nfds_t cur_nfd = 0;
@@ -233,10 +221,10 @@ bool SubprocessSet::DoWork() {
     ++i;
   }
 
-  return false;
+  return interrupted_;
 }
 
-#else  // linux
+#else  // linux || __OpenBSD__
 bool SubprocessSet::DoWork() {
   fd_set set;
   int nfds = 0;
@@ -252,15 +240,14 @@ bool SubprocessSet::DoWork() {
     }
   }
 
+  interrupted_ = false;
   int ret = pselect(nfds, &set, 0, 0, 0, &old_mask_);
   if (ret == -1) {
     if (errno != EINTR) {
       perror("ninja: pselect");
       return false;
     }
-    bool interrupted = interrupted_;
-    interrupted_ = false;
-    return interrupted;
+    return interrupted_;
   }
 
   for (vector<Subprocess*>::iterator i = running_.begin();
@@ -277,9 +264,9 @@ bool SubprocessSet::DoWork() {
     ++i;
   }
 
-  return false;
+  return interrupted_;
 }
-#endif  // linux
+#endif  // linux || __OpenBSD__
 
 Subprocess* SubprocessSet::NextFinished() {
   if (finished_.empty())
diff --git a/src/subprocess_test.cc b/src/subprocess_test.cc
index c3175da..afd9008 100644
--- a/src/subprocess_test.cc
+++ b/src/subprocess_test.cc
@@ -152,7 +152,7 @@ TEST_F(SubprocessTest, SetWithMulti) {
 
 // OS X's process limit is less than 1025 by default
 // (|sysctl kern.maxprocperuid| is 709 on 10.7 and 10.8 and less prior to that).
-#ifdef linux
+#if defined(linux) || defined(__OpenBSD__)
 TEST_F(SubprocessTest, SetWithLots) {
   // Arbitrary big number; needs to be over 1024 to confirm we're no longer
   // hostage to pselect.
@@ -179,7 +179,7 @@ TEST_F(SubprocessTest, SetWithLots) {
   }
   ASSERT_EQ(kNumProcs, subprocs_.finished_.size());
 }
-#endif  // linux
+#endif  // linux || __OpenBSD__
 
 // TODO: this test could work on Windows, just not sure how to simply
 // read stdin.
diff --git a/src/test.cc b/src/test.cc
index 0138b3a..45a9226 100644
--- a/src/test.cc
+++ b/src/test.cc
@@ -74,7 +74,11 @@ string GetSystemTempDir() {
 }  // anonymous namespace
 
 StateTestWithBuiltinRules::StateTestWithBuiltinRules() {
-  AssertParse(&state_,
+  AddCatRule(&state_);
+}
+
+void StateTestWithBuiltinRules::AddCatRule(State* state) {
+  AssertParse(state,
 "rule cat\n"
 "  command = cat $in > $out\n");
 }
@@ -94,9 +98,9 @@ void AssertHash(const char* expected, uint64_t actual) {
   ASSERT_EQ(BuildLog::LogEntry::HashCommand(expected), actual);
 }
 
-void VirtualFileSystem::Create(const string& path, int time,
+void VirtualFileSystem::Create(const string& path,
                                const string& contents) {
-  files_[path].mtime = time;
+  files_[path].mtime = now_;
   files_[path].contents = contents;
   files_created_.insert(path);
 }
@@ -109,7 +113,7 @@ TimeStamp VirtualFileSystem::Stat(const string& path) {
 }
 
 bool VirtualFileSystem::WriteFile(const string& path, const string& contents) {
-  Create(path, 0, contents);
+  Create(path, contents);
   return true;
 }
 
diff --git a/src/test.h b/src/test.h
index 37ca1f9..9f29e07 100644
--- a/src/test.h
+++ b/src/test.h
@@ -29,6 +29,12 @@ struct Node;
 /// builtin "cat" rule.
 struct StateTestWithBuiltinRules : public testing::Test {
   StateTestWithBuiltinRules();
+
+  /// Add a "cat" rule to \a state.  Used by some tests; it's
+  /// otherwise done by the ctor to state_.
+  void AddCatRule(State* state);
+
+  /// Short way to get a Node by its path from state_.
   Node* GetNode(const string& path);
 
   State state_;
@@ -41,8 +47,16 @@ void AssertHash(const char* expected, uint64_t actual);
 /// of disk state.  It also logs file accesses and directory creations
 /// so it can be used by tests to verify disk access patterns.
 struct VirtualFileSystem : public DiskInterface {
-  /// "Create" a file with a given mtime and contents.
-  void Create(const string& path, int time, const string& contents);
+  VirtualFileSystem() : now_(1) {}
+
+  /// "Create" a file with contents.
+  void Create(const string& path, const string& contents);
+
+  /// Tick "time" forwards; subsequent file operations will be newer than
+  /// previous ones.
+  int Tick() {
+    return ++now_;
+  }
 
   // DiskInterface
   virtual TimeStamp Stat(const string& path);
@@ -63,6 +77,9 @@ struct VirtualFileSystem : public DiskInterface {
   FileMap files_;
   set<string> files_removed_;
   set<string> files_created_;
+
+  /// A simple fake timestamp for file operations.
+  int now_;
 };
 
 struct ScopedTempDir {
diff --git a/src/util.cc b/src/util.cc
index 91e8fad..fa72dd2 100644
--- a/src/util.cc
+++ b/src/util.cc
@@ -17,6 +17,7 @@
 #ifdef _WIN32
 #include <windows.h>
 #include <io.h>
+#include <share.h>
 #endif
 
 #include <errno.h>
@@ -29,6 +30,7 @@
 #include <sys/types.h>
 
 #ifndef _WIN32
+#include <unistd.h>
 #include <sys/time.h>
 #endif
 
@@ -354,3 +356,21 @@ string ElideMiddle(const string& str, size_t width) {
   }
   return result;
 }
+
+bool Truncate(const string& path, size_t size, string* err) {
+#ifdef _WIN32
+  int fh = _sopen(path.c_str(), _O_RDWR | _O_CREAT, _SH_DENYNO,
+                  _S_IREAD | _S_IWRITE);
+  int success = _chsize(fh, size);
+  _close(fh);
+#else
+  int success = truncate(path.c_str(), size);
+#endif
+  // Both truncate() and _chsize() return 0 on success and set errno and return
+  // -1 on failure.
+  if (success < 0) {
+    *err = strerror(errno);
+    return false;
+  }
+  return true;
+}
diff --git a/src/util.h b/src/util.h
index 3c2a297..9740565 100644
--- a/src/util.h
+++ b/src/util.h
@@ -25,8 +25,14 @@
 #include <vector>
 using namespace std;
 
+#ifdef _MSC_VER
+#define NORETURN __declspec(noreturn)
+#else
+#define NORETURN __attribute__((noreturn))
+#endif
+
 /// Log a fatal message and exit.
-void Fatal(const char* msg, ...);
+NORETURN void Fatal(const char* msg, ...);
 
 /// Log a warning message.
 void Warning(const char* msg, ...);
@@ -70,6 +76,9 @@ double GetLoadAverage();
 /// exceeds @a width.
 string ElideMiddle(const string& str, size_t width);
 
+/// Truncates a file to the given size.
+bool Truncate(const string& path, size_t size, string* err);
+
 #ifdef _MSC_VER
 #define snprintf _snprintf
 #define fileno _fileno
@@ -85,7 +94,7 @@ string ElideMiddle(const string& str, size_t width);
 string GetLastErrorString();
 
 /// Calls Fatal() with a function name and GetLastErrorString.
-void Win32Fatal(const char* function);
+NORETURN void Win32Fatal(const char* function);
 #endif
 
 #endif  // NINJA_UTIL_H_
diff --git a/src/util_test.cc b/src/util_test.cc
index 4776546..1e29053 100644
--- a/src/util_test.cc
+++ b/src/util_test.cc
@@ -101,7 +101,7 @@ TEST(CanonicalizePath, EmptyResult) {
 }
 
 TEST(CanonicalizePath, UpDir) {
-  std::string path, err;
+  string path, err;
   path = "../../foo/bar.h";
   EXPECT_TRUE(CanonicalizePath(&path, &err));
   EXPECT_EQ("../../foo/bar.h", path);
diff --git a/src/version.cc b/src/version.cc
index 45fb040..07167fe 100644
--- a/src/version.cc
+++ b/src/version.cc
@@ -18,7 +18,7 @@
 
 #include "util.h"
 
-const char* kNinjaVersion = "1.2.0";
+const char* kNinjaVersion = "1.3.0";
 
 void ParseVersion(const string& version, int* major, int* minor) {
   size_t end = version.find('.');
@@ -51,7 +51,3 @@ void CheckNinjaVersion(const string& version) {
           kNinjaVersion, version.c_str());
   }
 }
-
-
-
-