diff --git a/.gitignore b/.gitignore
index 5a85203..a86205b 100644
--- a/.gitignore
+++ b/.gitignore
@@ -10,6 +10,7 @@
 /ninja.bootstrap
 /build_log_perftest
 /canon_perftest
+/clparser_perftest
 /depfile_parser_perftest
 /hash_collision_bench
 /ninja_test
diff --git a/.travis.yml b/.travis.yml
index 216b8b0..093139b 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -3,4 +3,4 @@
 compiler:
   - gcc
   - clang
-script: ./configure.py --bootstrap && ./ninja ninja_test && ./ninja_test --gtest_filter=-SubprocessTest.SetWithLots && ./misc/ninja_syntax_test.py
+script: ./configure.py --bootstrap && ./ninja all && ./ninja_test --gtest_filter=-SubprocessTest.SetWithLots && ./misc/ninja_syntax_test.py
diff --git a/HACKING.md b/HACKING.md
index c9c6601..e7c91ef 100644
--- a/HACKING.md
+++ b/HACKING.md
@@ -105,7 +105,7 @@
 * Lines are 80 columns maximum.
 * All source files should have the Google Inc. license header.
 
-[Google C++ coding style]: http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml
+[Google C++ coding style]: https://google.github.io/styleguide/cppguide.html
 
 ## Documentation
 
diff --git a/RELEASING b/RELEASING
index 880a55d..5f51b73 100644
--- a/RELEASING
+++ b/RELEASING
@@ -2,17 +2,18 @@
 
 Push new release branch:
 1. Consider sending a heads-up to the ninja-build mailing list first
-2. update src/version.cc with new version (with ".git"), then
-       git commit -a -m 'mark this 1.5.0.git'
-3. git checkout release; git merge master
-4. fix version number in src/version.cc (it will likely conflict in the above)
-5. fix version in doc/manual.asciidoc
-6. commit, tag, push (don't forget to push --tags)
-       git commit -a -m v1.5.0; git push origin release
+2. Make sure branches 'master' and 'release' are synced up locally
+3. update src/version.cc with new version (with ".git"), then
+       git commit -am 'mark this 1.5.0.git'
+4. git checkout release; git merge master
+5. fix version number in src/version.cc (it will likely conflict in the above)
+6. fix version in doc/manual.asciidoc (exists only on release branch)
+7. commit, tag, push (don't forget to push --tags)
+       git commit -am v1.5.0; git push origin release
        git tag v1.5.0; git push --tags
        # Push the 1.5.0.git change on master too:
        git checkout master; git push origin master
-7. construct release notes from prior notes
+8. construct release notes from prior notes
    credits: git shortlog -s --no-merges REV..
 
 Release on github:
diff --git a/configure.py b/configure.py
index 9ec368f..a443748 100755
--- a/configure.py
+++ b/configure.py
@@ -60,11 +60,14 @@
             self._platform = 'netbsd'
         elif self._platform.startswith('aix'):
             self._platform = 'aix'
+        elif self._platform.startswith('dragonfly'):
+            self._platform = 'dragonfly'
 
     @staticmethod
     def known_platforms():
       return ['linux', 'darwin', 'freebsd', 'openbsd', 'solaris', 'sunos5',
-              'mingw', 'msvc', 'gnukfreebsd', 'bitrig', 'netbsd', 'aix']
+              'mingw', 'msvc', 'gnukfreebsd', 'bitrig', 'netbsd', 'aix',
+              'dragonfly']
 
     def platform(self):
         return self._platform
@@ -95,10 +98,11 @@
         return self._platform == 'aix'
 
     def uses_usr_local(self):
-        return self._platform in ('freebsd', 'openbsd', 'bitrig')
+        return self._platform in ('freebsd', 'openbsd', 'bitrig', 'dragonfly')
 
     def supports_ppoll(self):
-        return self._platform in ('freebsd', 'linux', 'openbsd', 'bitrig')
+        return self._platform in ('freebsd', 'linux', 'openbsd', 'bitrig',
+                                  'dragonfly')
 
     def supports_ninja_browse(self):
         return (not self.is_windows()
@@ -302,7 +306,7 @@
               '/Zi',  # Create pdb with debug info.
               '/W4',  # Highest warning level.
               '/WX',  # Warnings as errors.
-              '/wd4530', '/wd4100', '/wd4706',
+              '/wd4530', '/wd4100', '/wd4706', '/wd4244',
               '/wd4512', '/wd4800', '/wd4702', '/wd4819',
               # Disable warnings about constant conditional expressions.
               '/wd4127',
@@ -489,6 +493,7 @@
              'manifest_parser',
              'metrics',
              'state',
+             'string_piece_util',
              'util',
              'version']:
     objs += cxx(name)
@@ -551,6 +556,7 @@
              'manifest_parser_test',
              'ninja_test',
              'state_test',
+             'string_piece_util_test',
              'subprocess_test',
              'test',
              'util_test']:
@@ -566,21 +572,17 @@
 
 
 n.comment('Ancillary executables.')
-objs = cxx('build_log_perftest')
-all_targets += n.build(binary('build_log_perftest'), 'link', objs,
-                       implicit=ninja_lib, variables=[('libs', libs)])
-objs = cxx('canon_perftest')
-all_targets += n.build(binary('canon_perftest'), 'link', objs,
-                       implicit=ninja_lib, variables=[('libs', libs)])
-objs = cxx('depfile_parser_perftest')
-all_targets += n.build(binary('depfile_parser_perftest'), 'link', objs,
-                       implicit=ninja_lib, variables=[('libs', libs)])
-objs = cxx('hash_collision_bench')
-all_targets += n.build(binary('hash_collision_bench'), 'link', objs,
-                              implicit=ninja_lib, variables=[('libs', libs)])
-objs = cxx('manifest_parser_perftest')
-all_targets += n.build(binary('manifest_parser_perftest'), 'link', objs,
-                              implicit=ninja_lib, variables=[('libs', libs)])
+
+for name in ['build_log_perftest',
+             'canon_perftest',
+             'depfile_parser_perftest',
+             'hash_collision_bench',
+             'manifest_parser_perftest',
+             'clparser_perftest']:
+  objs = cxx(name)
+  all_targets += n.build(binary(name), 'link', objs,
+                         implicit=ninja_lib, variables=[('libs', libs)])
+
 n.newline()
 
 n.comment('Generate a graph using the "graph" tool.')
diff --git a/doc/manual.asciidoc b/doc/manual.asciidoc
index 1e6ea92..2410083 100644
--- a/doc/manual.asciidoc
+++ b/doc/manual.asciidoc
@@ -1,6 +1,6 @@
 The Ninja build system
 ======================
-v1.7.2, Nov 2016
+v1.8.0, Sep 2017
 
 
 Introduction
@@ -280,6 +280,11 @@
 by the Clang tooling interface.
 _Available since Ninja 1.2._
 
+`deps`:: show all dependencies stored in the `.ninja_deps` file. When given a
+target, show just the target's dependencies. _Available since Ninja 1.4._
+
+`recompact`:: recompact the `.ninja_deps` file. _Available since Ninja 1.4._
+
 
 Writing your own Ninja files
 ----------------------------
diff --git a/misc/zsh-completion b/misc/zsh-completion
index 446e269..bf23fac 100644
--- a/misc/zsh-completion
+++ b/misc/zsh-completion
@@ -22,7 +22,12 @@
   then
     eval dir="${opt_args[-C]}"
   fi
-  targets_command="ninja -C \"${dir}\" -t targets all"
+  file="build.ninja"
+  if [ -n "${opt_args[-f]}" ];
+  then
+    eval file="${opt_args[-f]}"
+  fi
+  targets_command="ninja -f \"${file}\" -C \"${dir}\" -t targets all"
   eval ${targets_command} 2>/dev/null | cut -d: -f1
 }
 
diff --git a/src/browse.py b/src/browse.py
index 4b4faa8..64a16f2 100755
--- a/src/browse.py
+++ b/src/browse.py
@@ -193,6 +193,8 @@
 parser = argparse.ArgumentParser(prog='ninja -t browse')
 parser.add_argument('--port', '-p', default=8000, type=int,
     help='Port number to use (default %(default)d)')
+parser.add_argument('--hostname', '-a', default='localhost', type=str,
+    help='Hostname to bind to (default %(default)s)')
 parser.add_argument('--no-browser', action='store_true',
     help='Do not open a webbrowser on startup.')
 
@@ -205,9 +207,11 @@
 
 args = parser.parse_args()
 port = args.port
-httpd = httpserver.HTTPServer(('',port), RequestHandler)
+hostname = args.hostname
+httpd = httpserver.HTTPServer((hostname,port), RequestHandler)
 try:
-    hostname = socket.gethostname()
+    if hostname == "":
+        hostname = socket.gethostname()
     print('Web server running on %s:%d, ctl-C to abort...' % (hostname,port) )
     print('Web server pid %d' % os.getpid(), file=sys.stderr )
     if not args.no_browser:
diff --git a/src/build.cc b/src/build.cc
index 64710dd..61ef0e8 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -20,6 +20,11 @@
 #include <stdlib.h>
 #include <functional>
 
+#ifdef _WIN32
+#include <fcntl.h>
+#include <io.h>
+#endif
+
 #if defined(__SVR4) && defined(__sun)
 #include <sys/termios.h>
 #endif
@@ -155,7 +160,17 @@
       final_output = StripAnsiEscapeCodes(output);
     else
       final_output = output;
+
+#ifdef _WIN32
+    // Fix extra CR being added on Windows, writing out CR CR LF (#773)
+    _setmode(_fileno(stdout), _O_BINARY);  // Begin Windows extra CR fix
+#endif
+
     printer_.PrintOnNewLine(final_output);
+
+#ifdef _WIN32
+    _setmode(_fileno(stdout), _O_TEXT);  // End Windows extra CR fix
+#endif
   }
 }
 
@@ -275,27 +290,30 @@
 
 Plan::Plan() : command_edges_(0), wanted_edges_(0) {}
 
-bool Plan::AddTarget(Node* node, string* err) {
-  vector<Node*> stack;
-  return AddSubTarget(node, &stack, err);
+void Plan::Reset() {
+  command_edges_ = 0;
+  wanted_edges_ = 0;
+  ready_.clear();
+  want_.clear();
 }
 
-bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) {
+bool Plan::AddTarget(Node* node, string* err) {
+  return AddSubTarget(node, NULL, err);
+}
+
+bool Plan::AddSubTarget(Node* node, Node* dependent, string* err) {
   Edge* edge = node->in_edge();
   if (!edge) {  // Leaf node.
     if (node->dirty()) {
       string referenced;
-      if (!stack->empty())
-        referenced = ", needed by '" + stack->back()->path() + "',";
+      if (dependent)
+        referenced = ", needed by '" + dependent->path() + "',";
       *err = "'" + node->path() + "'" + referenced + " missing "
              "and no known rule to make it";
     }
     return false;
   }
 
-  if (CheckDependencyCycle(node, *stack, err))
-    return false;
-
   if (edge->outputs_ready())
     return false;  // Don't need to do anything.
 
@@ -319,50 +337,15 @@
   if (!want_ins.second)
     return true;  // We've already processed the inputs.
 
-  stack->push_back(node);
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
-    if (!AddSubTarget(*i, stack, err) && !err->empty())
+    if (!AddSubTarget(*i, node, err) && !err->empty())
       return false;
   }
-  assert(stack->back() == node);
-  stack->pop_back();
 
   return true;
 }
 
-bool Plan::CheckDependencyCycle(Node* node, const vector<Node*>& stack,
-                                string* err) {
-  vector<Node*>::const_iterator start = stack.begin();
-  while (start != stack.end() && (*start)->in_edge() != node->in_edge())
-    ++start;
-  if (start == stack.end())
-    return false;
-
-  // Build error string for the cycle.
-  vector<Node*> cycle(start, stack.end());
-  cycle.push_back(node);
-
-  if (cycle.front() != cycle.back()) {
-    // Consider
-    //   build a b: cat c
-    //   build c: cat a
-    // stack will contain [b, c], node will be a.  To not print b -> c -> a,
-    // shift by one to get c -> a -> c which makes the cycle clear.
-    cycle.erase(cycle.begin());
-    cycle.push_back(cycle.front());
-    assert(cycle.front() == cycle.back());
-  }
-
-  *err = "dependency cycle: ";
-  for (vector<Node*>::const_iterator i = cycle.begin(); i != cycle.end(); ++i) {
-    if (i != cycle.begin())
-      err->append(" -> ");
-    err->append((*i)->path());
-  }
-  return true;
-}
-
 Edge* Plan::FindWork() {
   if (ready_.empty())
     return NULL;
@@ -618,9 +601,10 @@
 }
 
 bool Builder::AddTarget(Node* node, string* err) {
+  if (!scan_.RecomputeDirty(node, err))
+    return false;
+
   if (Edge* in_edge = node->in_edge()) {
-    if (!scan_.RecomputeDirty(in_edge, err))
-      return false;
     if (in_edge->outputs_ready())
       return true;  // Nothing to do.
   }
@@ -793,9 +777,10 @@
     return true;
   }
 
-  // Restat the edge outputs, if necessary.
-  TimeStamp restat_mtime = 0;
-  if (edge->GetBindingBool("restat") && !config_.dry_run) {
+  // Restat the edge outputs
+  TimeStamp output_mtime = 0;
+  bool restat = edge->GetBindingBool("restat");
+  if (!config_.dry_run) {
     bool node_cleaned = false;
 
     for (vector<Node*>::iterator o = edge->outputs_.begin();
@@ -803,7 +788,9 @@
       TimeStamp new_mtime = disk_interface_->Stat((*o)->path(), err);
       if (new_mtime == -1)
         return false;
-      if ((*o)->mtime() == new_mtime) {
+      if (new_mtime > output_mtime)
+        output_mtime = new_mtime;
+      if ((*o)->mtime() == new_mtime && restat) {
         // 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).
@@ -814,6 +801,7 @@
     }
 
     if (node_cleaned) {
+      TimeStamp restat_mtime = 0;
       // 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();
@@ -837,6 +825,8 @@
       // The total number of edges in the plan may have changed as a result
       // of a restat.
       status_->PlanHasTotalEdges(plan_.command_edge_count());
+
+      output_mtime = restat_mtime;
     }
   }
 
@@ -849,7 +839,7 @@
 
   if (scan_.build_log()) {
     if (!scan_.build_log()->RecordCommand(edge, start_time, end_time,
-                                          restat_mtime)) {
+                                          output_mtime)) {
       *err = string("Error writing to build log: ") + strerror(errno);
       return false;
     }
@@ -918,7 +908,7 @@
     deps_nodes->reserve(deps.ins_.size());
     for (vector<StringPiece>::iterator i = deps.ins_.begin();
          i != deps.ins_.end(); ++i) {
-      unsigned int slash_bits;
+      uint64_t slash_bits;
       if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits,
                             err))
         return false;
diff --git a/src/build.h b/src/build.h
index 66ce607..43786f1 100644
--- a/src/build.h
+++ b/src/build.h
@@ -71,10 +71,11 @@
   /// Number of edges with commands to run.
   int command_edge_count() const { return command_edges_; }
 
+  /// Reset state.  Clears want and ready sets.
+  void Reset();
+
 private:
-  bool AddSubTarget(Node* node, vector<Node*>* stack, string* err);
-  bool CheckDependencyCycle(Node* node, const vector<Node*>& stack,
-                            string* err);
+  bool AddSubTarget(Node* node, Node* dependent, string* err);
   void NodeFinished(Node* node);
 
   /// Submits a ready edge as a candidate for execution.
diff --git a/src/build_log.cc b/src/build_log.cc
index 8a52514..333915a 100644
--- a/src/build_log.cc
+++ b/src/build_log.cc
@@ -105,7 +105,7 @@
 BuildLog::LogEntry::LogEntry(const string& output, uint64_t command_hash,
   int start_time, int end_time, TimeStamp restat_mtime)
   : output(output), command_hash(command_hash),
-    start_time(start_time), end_time(end_time), restat_mtime(restat_mtime)
+    start_time(start_time), end_time(end_time), mtime(restat_mtime)
 {}
 
 BuildLog::BuildLog()
@@ -145,7 +145,7 @@
 }
 
 bool BuildLog::RecordCommand(Edge* edge, int start_time, int end_time,
-                             TimeStamp restat_mtime) {
+                             TimeStamp mtime) {
   string command = edge->EvaluateCommand(true);
   uint64_t command_hash = LogEntry::HashCommand(command);
   for (vector<Node*>::iterator out = edge->outputs_.begin();
@@ -162,7 +162,7 @@
     log_entry->command_hash = command_hash;
     log_entry->start_time = start_time;
     log_entry->end_time = end_time;
-    log_entry->restat_mtime = restat_mtime;
+    log_entry->mtime = mtime;
 
     if (log_file_) {
       if (!WriteEntry(log_file_, *log_entry))
@@ -314,7 +314,7 @@
 
     entry->start_time = start_time;
     entry->end_time = end_time;
-    entry->restat_mtime = restat_mtime;
+    entry->mtime = restat_mtime;
     if (log_version >= 5) {
       char c = *end; *end = '\0';
       entry->command_hash = (uint64_t)strtoull(start, NULL, 16);
@@ -354,7 +354,7 @@
 
 bool BuildLog::WriteEntry(FILE* f, const LogEntry& entry) {
   return fprintf(f, "%d\t%d\t%d\t%s\t%" PRIx64 "\n",
-          entry.start_time, entry.end_time, entry.restat_mtime,
+          entry.start_time, entry.end_time, entry.mtime,
           entry.output.c_str(), entry.command_hash) > 0;
 }
 
diff --git a/src/build_log.h b/src/build_log.h
index 785961e..5268fab 100644
--- a/src/build_log.h
+++ b/src/build_log.h
@@ -45,7 +45,7 @@
 
   bool OpenForWrite(const string& path, const BuildLogUser& user, string* err);
   bool RecordCommand(Edge* edge, int start_time, int end_time,
-                     TimeStamp restat_mtime = 0);
+                     TimeStamp mtime = 0);
   void Close();
 
   /// Load the on-disk log.
@@ -56,7 +56,7 @@
     uint64_t command_hash;
     int start_time;
     int end_time;
-    TimeStamp restat_mtime;
+    TimeStamp mtime;
 
     static uint64_t HashCommand(StringPiece command);
 
@@ -64,7 +64,7 @@
     bool operator==(const LogEntry& o) {
       return output == o.output && command_hash == o.command_hash &&
           start_time == o.start_time && end_time == o.end_time &&
-          restat_mtime == o.restat_mtime;
+          mtime == o.mtime;
     }
 
     explicit LogEntry(const string& output);
diff --git a/src/build_log_perftest.cc b/src/build_log_perftest.cc
index 185c512..b4efb1d 100644
--- a/src/build_log_perftest.cc
+++ b/src/build_log_perftest.cc
@@ -92,7 +92,7 @@
     log.RecordCommand(state.edges_[i],
                       /*start_time=*/100 * i,
                       /*end_time=*/100 * i + 1,
-                      /*restat_mtime=*/0);
+                      /*mtime=*/0);
   }
 
   return true;
diff --git a/src/build_log_test.cc b/src/build_log_test.cc
index f4c9044..ad30380 100644
--- a/src/build_log_test.cc
+++ b/src/build_log_test.cc
@@ -181,7 +181,7 @@
   ASSERT_TRUE(e);
   ASSERT_EQ(123, e->start_time);
   ASSERT_EQ(456, e->end_time);
-  ASSERT_EQ(456, e->restat_mtime);
+  ASSERT_EQ(456, e->mtime);
   ASSERT_NO_FATAL_FAILURE(AssertHash("command", e->command_hash));
 }
 
@@ -205,14 +205,14 @@
   ASSERT_TRUE(e);
   ASSERT_EQ(123, e->start_time);
   ASSERT_EQ(456, e->end_time);
-  ASSERT_EQ(456, e->restat_mtime);
+  ASSERT_EQ(456, e->mtime);
   ASSERT_NO_FATAL_FAILURE(AssertHash("command", e->command_hash));
 
   e = log.LookupByOutput("out2");
   ASSERT_TRUE(e);
   ASSERT_EQ(456, e->start_time);
   ASSERT_EQ(789, e->end_time);
-  ASSERT_EQ(789, e->restat_mtime);
+  ASSERT_EQ(789, e->mtime);
   ASSERT_NO_FATAL_FAILURE(AssertHash("command2", e->command_hash));
 }
 
@@ -240,7 +240,7 @@
   ASSERT_TRUE(e);
   ASSERT_EQ(456, e->start_time);
   ASSERT_EQ(789, e->end_time);
-  ASSERT_EQ(789, e->restat_mtime);
+  ASSERT_EQ(789, e->mtime);
   ASSERT_NO_FATAL_FAILURE(AssertHash("command2", e->command_hash));
 }
 
diff --git a/src/build_test.cc b/src/build_test.cc
index 640e1b0..a0f898f 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -185,59 +185,6 @@
   ASSERT_FALSE(edge);  // done
 }
 
-TEST_F(PlanTest, DependencyCycle) {
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build out: cat mid\n"
-"build mid: cat in\n"
-"build in: cat pre\n"
-"build pre: cat out\n"));
-  GetNode("out")->MarkDirty();
-  GetNode("mid")->MarkDirty();
-  GetNode("in")->MarkDirty();
-  GetNode("pre")->MarkDirty();
-
-  string err;
-  EXPECT_FALSE(plan_.AddTarget(GetNode("out"), &err));
-  ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes1) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build a b: cat a\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err));
-  ASSERT_EQ("dependency cycle: a -> a", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes2) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build b a: cat a\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err));
-  ASSERT_EQ("dependency cycle: a -> a", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes3) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build a b: cat c\n"
-"build c: cat a\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err));
-  ASSERT_EQ("dependency cycle: c -> a -> c", err);
-}
-
-TEST_F(PlanTest, CycleInEdgesButNotInNodes4) {
-  string err;
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-"build d: cat c\n"
-"build c: cat b\n"
-"build b: cat a\n"
-"build a e: cat d\n"
-"build f: cat e\n"));
-  EXPECT_FALSE(plan_.AddTarget(GetNode("f"), &err));
-  ASSERT_EQ("dependency cycle: d -> c -> b -> a -> d", err);
-}
-
 void PlanTest::TestPoolWithDepthOne(const char* test_case) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, test_case));
   GetNode("out1")->MarkDirty();
@@ -608,7 +555,8 @@
       edge->rule().name() == "cat_rsp_out" ||
       edge->rule().name() == "cc" ||
       edge->rule().name() == "touch" ||
-      edge->rule().name() == "touch-interrupt") {
+      edge->rule().name() == "touch-interrupt" ||
+      edge->rule().name() == "touch-fail-tick2") {
     for (vector<Node*>::iterator out = edge->outputs_.begin();
          out != edge->outputs_.end(); ++out) {
       fs_->Create((*out)->path(), "");
@@ -649,7 +597,8 @@
     return true;
   }
 
-  if (edge->rule().name() == "fail")
+  if (edge->rule().name() == "fail" ||
+      (edge->rule().name() == "touch-fail-tick2" && fs_->now_ == 2))
     result->status = ExitFailure;
   else
     result->status = ExitSuccess;
@@ -1258,6 +1207,82 @@
   EXPECT_TRUE(builder_.AlreadyUpToDate());
 }
 
+TEST_F(BuildWithLogTest, RebuildAfterFailure) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch-fail-tick2\n"
+"  command = touch-fail-tick2\n"
+"build out1: touch-fail-tick2 in\n"));
+
+  string err;
+
+  fs_.Create("in", "");
+
+  // Run once successfully to get out1 in the log
+  EXPECT_TRUE(builder_.AddTarget("out1", &err));
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  EXPECT_EQ(1u, command_runner_.commands_ran_.size());
+
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  builder_.Cleanup();
+  builder_.plan_.Reset();
+
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  // Run again with a failure that updates the output file timestamp
+  EXPECT_TRUE(builder_.AddTarget("out1", &err));
+  EXPECT_FALSE(builder_.Build(&err));
+  EXPECT_EQ("subcommand failed", err);
+  EXPECT_EQ(1u, command_runner_.commands_ran_.size());
+
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  builder_.Cleanup();
+  builder_.plan_.Reset();
+
+  fs_.Tick();
+
+  // Run again, should rerun even though the output file is up to date on disk
+  EXPECT_TRUE(builder_.AddTarget("out1", &err));
+  EXPECT_FALSE(builder_.AlreadyUpToDate());
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("", err);
+}
+
+TEST_F(BuildWithLogTest, RebuildWithNoInputs) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch\n"
+"build out1: touch\n"
+"build out2: touch in\n"));
+
+  string err;
+
+  fs_.Create("in", "");
+
+  EXPECT_TRUE(builder_.AddTarget("out1", &err));
+  EXPECT_TRUE(builder_.AddTarget("out2", &err));
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+
+  fs_.Tick();
+
+  fs_.Create("in", "");
+
+  EXPECT_TRUE(builder_.AddTarget("out1", &err));
+  EXPECT_TRUE(builder_.AddTarget("out2", &err));
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  EXPECT_EQ(1u, command_runner_.commands_ran_.size());
+}
+
 TEST_F(BuildWithLogTest, RestatTest) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "rule true\n"
@@ -1438,7 +1463,7 @@
   // the right mtime
   BuildLog::LogEntry* log_entry = build_log_.LookupByOutput("out1");
   ASSERT_TRUE(NULL != log_entry);
-  ASSERT_EQ(restat_mtime, log_entry->restat_mtime);
+  ASSERT_EQ(restat_mtime, log_entry->mtime);
 
   // Now remove a file, referenced from depfile, so that target becomes
   // dirty, but the output does not change
@@ -1455,7 +1480,7 @@
   // Check that the logfile entry remains correctly set
   log_entry = build_log_.LookupByOutput("out1");
   ASSERT_TRUE(NULL != log_entry);
-  ASSERT_EQ(restat_mtime, log_entry->restat_mtime);
+  ASSERT_EQ(restat_mtime, log_entry->mtime);
 }
 
 struct BuildDryRun : public BuildWithLogTest {
@@ -1669,8 +1694,8 @@
 TEST_F(BuildTest, StatFailureAbortsBuild) {
   const string kTooLongToStat(400, 'i');
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-("build " + kTooLongToStat + ": cat " + kTooLongToStat + "\n").c_str()));
-  // Also cyclic, for good measure.
+("build " + kTooLongToStat + ": cat in\n").c_str()));
+  fs_.Create("in", "");
 
   // This simulates a stat failure:
   fs_.files_[kTooLongToStat].mtime = -1;
diff --git a/src/canon_perftest.cc b/src/canon_perftest.cc
index 389ac24..03f4a2f 100644
--- a/src/canon_perftest.cc
+++ b/src/canon_perftest.cc
@@ -33,7 +33,7 @@
   for (int j = 0; j < 5; ++j) {
     const int kNumRepetitions = 2000000;
     int64_t start = GetTimeMillis();
-    unsigned int slash_bits;
+    uint64_t slash_bits;
     for (int i = 0; i < kNumRepetitions; ++i) {
       CanonicalizePath(buf, &len, &slash_bits, &err);
     }
diff --git a/src/clparser.cc b/src/clparser.cc
index f73a8c1..7994c06 100644
--- a/src/clparser.cc
+++ b/src/clparser.cc
@@ -18,8 +18,12 @@
 #include <assert.h>
 #include <string.h>
 
+#include "metrics.h"
+#include "string_piece_util.h"
+
 #ifdef _WIN32
 #include "includes_normalize.h"
+#include "string_piece.h"
 #else
 #include "util.h"
 #endif
@@ -53,7 +57,7 @@
 
 // static
 bool CLParser::IsSystemInclude(string path) {
-  transform(path.begin(), path.end(), path.begin(), ::tolower);
+  transform(path.begin(), path.end(), path.begin(), ToLowerASCII);
   // 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);
@@ -61,7 +65,7 @@
 
 // static
 bool CLParser::FilterInputFilename(string line) {
-  transform(line.begin(), line.end(), line.begin(), ::tolower);
+  transform(line.begin(), line.end(), line.begin(), ToLowerASCII);
   // TODO: other extensions, like .asm?
   return EndsWith(line, ".c") ||
       EndsWith(line, ".cc") ||
@@ -72,9 +76,15 @@
 // static
 bool CLParser::Parse(const string& output, const string& deps_prefix,
                      string* filtered_output, string* err) {
+  METRIC_RECORD("CLParser::Parse");
+
   // Loop over all lines in the output to process them.
   assert(&output != filtered_output);
   size_t start = 0;
+#ifdef _WIN32
+  IncludesNormalize normalizer(".");
+#endif
+
   while (start < output.size()) {
     size_t end = output.find_first_of("\r\n", start);
     if (end == string::npos)
@@ -85,12 +95,12 @@
     if (!include.empty()) {
       string normalized;
 #ifdef _WIN32
-      if (!IncludesNormalize::Normalize(include, NULL, &normalized, err))
+      if (!normalizer.Normalize(include, &normalized, err))
         return false;
 #else
       // TODO: should this make the path relative to cwd?
       normalized = include;
-      unsigned int slash_bits;
+      uint64_t slash_bits;
       if (!CanonicalizePath(&normalized, &slash_bits, err))
         return false;
 #endif
diff --git a/src/clparser_perftest.cc b/src/clparser_perftest.cc
new file mode 100644
index 0000000..7ac5230
--- /dev/null
+++ b/src/clparser_perftest.cc
@@ -0,0 +1,157 @@
+// Copyright 2017 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 <stdio.h>
+#include <stdlib.h>
+
+#include "clparser.h"
+#include "metrics.h"
+
+int main(int argc, char* argv[]) {
+  // Output of /showIncludes from #include <iostream>
+  string perf_testdata =
+      "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\iostream\r\n"
+      "Note: including file:  C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\istream\r\n"
+      "Note: including file:   C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ostream\r\n"
+      "Note: including file:    C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ios\r\n"
+      "Note: including file:     C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xlocnum\r\n"
+      "Note: including file:      C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\climits\r\n"
+      "Note: including file:       C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\yvals.h\r\n"
+      "Note: including file:        C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xkeycheck.h\r\n"
+      "Note: including file:        C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\crtdefs.h\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:          C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\sal.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ConcurrencySal.h\r\n"
+      "Note: including file:          C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vadefs.h\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt.h\r\n"
+      "Note: including file:          C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:        C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\use_ansi.h\r\n"
+      "Note: including file:       C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\limits.h\r\n"
+      "Note: including file:        C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:      C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cmath\r\n"
+      "Note: including file:       C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\math.h\r\n"
+      "Note: including file:       C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xtgmath.h\r\n"
+      "Note: including file:        C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xtr1common\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstdlib\r\n"
+      "Note: including file:          C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\stdlib.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_malloc.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_search.h\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\stddef.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wstdlib.h\r\n"
+      "Note: including file:      C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstdio\r\n"
+      "Note: including file:       C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\stdio.h\r\n"
+      "Note: including file:        C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wstdio.h\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_stdio_config.h\r\n"
+      "Note: including file:      C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\streambuf\r\n"
+      "Note: including file:       C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xiosbase\r\n"
+      "Note: including file:        C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xlocale\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstring\r\n"
+      "Note: including file:          C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\string.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_memory.h\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_memcpy_s.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\errno.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_string.h\r\n"
+      "Note: including file:              C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wstring.h\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\stdexcept\r\n"
+      "Note: including file:          C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\exception\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\type_traits\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xstddef\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstddef\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\initializer_list\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\malloc.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_exception.h\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\eh.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_terminate.h\r\n"
+      "Note: including file:          C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xstring\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xmemory0\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstdint\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\stdint.h\r\n"
+      "Note: including file:              C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\limits\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ymath.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cfloat\r\n"
+      "Note: including file:              C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\float.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cwchar\r\n"
+      "Note: including file:              C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\wchar.h\r\n"
+      "Note: including file:               C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wconio.h\r\n"
+      "Note: including file:               C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wctype.h\r\n"
+      "Note: including file:               C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wdirect.h\r\n"
+      "Note: including file:               C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wio.h\r\n"
+      "Note: including file:                C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_share.h\r\n"
+      "Note: including file:               C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wprocess.h\r\n"
+      "Note: including file:               C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wtime.h\r\n"
+      "Note: including file:               C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\sys/stat.h\r\n"
+      "Note: including file:                C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\sys/types.h\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\new\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_new.h\r\n"
+      "Note: including file:              C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xutility\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\utility\r\n"
+      "Note: including file:              C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\iosfwd\r\n"
+      "Note: including file:               C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\crtdbg.h\r\n"
+      "Note: including file:                C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_new_debug.h\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xatomic0.h\r\n"
+      "Note: including file:            C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\intrin.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\setjmp.h\r\n"
+      "Note: including file:              C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\immintrin.h\r\n"
+      "Note: including file:              C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\wmmintrin.h\r\n"
+      "Note: including file:               C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\nmmintrin.h\r\n"
+      "Note: including file:                C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\smmintrin.h\r\n"
+      "Note: including file:                 C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\tmmintrin.h\r\n"
+      "Note: including file:                  C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\pmmintrin.h\r\n"
+      "Note: including file:                   C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\emmintrin.h\r\n"
+      "Note: including file:                    C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xmmintrin.h\r\n"
+      "Note: including file:                     C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\mmintrin.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ammintrin.h\r\n"
+      "Note: including file:             C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\mm3dnow.h\r\n"
+      "Note: including file:              C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\typeinfo\r\n"
+      "Note: including file:          C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_typeinfo.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xlocinfo\r\n"
+      "Note: including file:          C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xlocinfo.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\ctype.h\r\n"
+      "Note: including file:           C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\locale.h\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xfacet\r\n"
+      "Note: including file:        C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\system_error\r\n"
+      "Note: including file:         C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cerrno\r\n"
+      "Note: including file:        C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\share.h\r\n";
+
+  for (int limit = 1 << 10; limit < (1<<20); limit *= 2) {
+    int64_t start = GetTimeMillis();
+    for (int rep = 0; rep < limit; ++rep) {
+      string output;
+      string err;
+
+      CLParser parser;
+      if (!parser.Parse(perf_testdata, "", &output, &err)) {
+        printf("%s\n", err.c_str());
+        return 1;
+      }
+    }
+    int64_t end = GetTimeMillis();
+
+    if (end - start > 2000) {
+      int delta_ms = (int)(end - start);
+      printf("Parse %d times in %dms avg %.1fus\n",
+             limit, delta_ms, float(delta_ms * 1000) / limit);
+      break;
+    }
+  }
+
+  return 0;
+}
diff --git a/src/disk_interface.cc b/src/disk_interface.cc
index 451a9b4..28530b1 100644
--- a/src/disk_interface.cc
+++ b/src/disk_interface.cc
@@ -28,6 +28,7 @@
 #include <direct.h>  // _mkdir
 #endif
 
+#include "metrics.h"
 #include "util.h"
 
 namespace {
@@ -80,20 +81,15 @@
   return TimeStampFromFileTime(attrs.ftLastWriteTime);
 }
 
-#ifdef _MSC_VER
-#pragma warning(push)
-#pragma warning(disable: 4996)  // GetVersionExA is deprecated post SDK 8.1.
-#endif
 bool IsWindows7OrLater() {
-  OSVERSIONINFO version_info = { sizeof(version_info) };
-  if (!GetVersionEx(&version_info))
-    Fatal("GetVersionEx: %s", GetLastErrorString().c_str());
-  return version_info.dwMajorVersion > 6 ||
-         (version_info.dwMajorVersion == 6 && version_info.dwMinorVersion >= 1);
+  OSVERSIONINFOEX version_info =
+      { sizeof(OSVERSIONINFOEX), 6, 1, 0, 0, {0}, 0, 0, 0, 0, 0};
+  DWORDLONG comparison = 0;
+  VER_SET_CONDITION(comparison, VER_MAJORVERSION, VER_GREATER_EQUAL);
+  VER_SET_CONDITION(comparison, VER_MINORVERSION, VER_GREATER_EQUAL);
+  return VerifyVersionInfo(
+      &version_info, VER_MAJORVERSION | VER_MINORVERSION, comparison);
 }
-#ifdef _MSC_VER
-#pragma warning(pop)
-#endif
 
 bool StatAllFilesInDir(const string& dir, map<string, TimeStamp>* stamps,
                        string* err) {
@@ -153,6 +149,7 @@
 // RealDiskInterface -----------------------------------------------------------
 
 TimeStamp RealDiskInterface::Stat(const string& path, string* err) const {
+  METRIC_RECORD("node stat");
 #ifdef _WIN32
   // MSDN: "Naming Files, Paths, and Namespaces"
   // http://msdn.microsoft.com/en-us/library/windows/desktop/aa365247(v=vs.85).aspx
@@ -190,6 +187,11 @@
     *err = "stat(" + path + "): " + strerror(errno);
     return -1;
   }
+  // Some users (Flatpak) set mtime to 0, this should be harmless
+  // and avoids conflicting with our return value of 0 meaning
+  // that it doesn't exist.
+  if (st.st_mtime == 0)
+    return 1;
   return st.st_mtime;
 #endif
 }
diff --git a/src/disk_interface_test.cc b/src/disk_interface_test.cc
index 7187bdf..d7fb8f8 100644
--- a/src/disk_interface_test.cc
+++ b/src/disk_interface_test.cc
@@ -245,7 +245,7 @@
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out->in_edge(), NULL);
+  scan_.RecomputeDirty(out, NULL);
   ASSERT_EQ(2u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_EQ("in",  stats_[1]);
@@ -261,7 +261,7 @@
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out->in_edge(), NULL);
+  scan_.RecomputeDirty(out, NULL);
   ASSERT_EQ(3u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_TRUE(GetNode("out")->dirty());
@@ -281,7 +281,7 @@
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out->in_edge(), NULL);
+  scan_.RecomputeDirty(out, NULL);
   ASSERT_EQ(1u + 6u, stats_.size());
   ASSERT_EQ("mid1", stats_[1]);
   ASSERT_TRUE(GetNode("mid1")->dirty());
@@ -302,7 +302,7 @@
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out->in_edge(), NULL);
+  scan_.RecomputeDirty(out, NULL);
   ASSERT_FALSE(GetNode("in")->dirty());
   ASSERT_TRUE(GetNode("mid")->dirty());
   ASSERT_TRUE(GetNode("out")->dirty());
diff --git a/src/graph.cc b/src/graph.cc
index f1d9ca2..7dd9491 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -28,24 +28,47 @@
 #include "util.h"
 
 bool Node::Stat(DiskInterface* disk_interface, string* err) {
-  METRIC_RECORD("node stat");
   return (mtime_ = disk_interface->Stat(path_, err)) != -1;
 }
 
-bool DependencyScan::RecomputeDirty(Edge* edge, string* err) {
+bool DependencyScan::RecomputeDirty(Node* node, string* err) {
+  vector<Node*> stack;
+  return RecomputeDirty(node, &stack, err);
+}
+
+bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
+                                    string* err) {
+  Edge* edge = node->in_edge();
+  if (!edge) {
+    // If we already visited this leaf node then we are done.
+    if (node->status_known())
+      return true;
+    // This node has no in-edge; it is dirty if it is missing.
+    if (!node->StatIfNecessary(disk_interface_, err))
+      return false;
+    if (!node->exists())
+      EXPLAIN("%s has no in-edge and is missing", node->path().c_str());
+    node->set_dirty(!node->exists());
+    return true;
+  }
+
+  // If we already finished this edge then we are done.
+  if (edge->mark_ == Edge::VisitDone)
+    return true;
+
+  // If we encountered this edge earlier in the call stack we have a cycle.
+  if (!VerifyDAG(node, stack, err))
+    return false;
+
+  // Mark the edge temporarily while in the call stack.
+  edge->mark_ = Edge::VisitInStack;
+  stack->push_back(node);
+
   bool dirty = false;
   edge->outputs_ready_ = true;
   edge->deps_missing_ = false;
 
   // Load output mtimes so we can compare them to the most recent input below.
-  // RecomputeDirty() recursively walks the graph following the input nodes
-  // of |edge| and the in_edges of these nodes.  It uses the stat state of each
-  // node to mark nodes as visited and doesn't traverse across nodes that have
-  // been visited already.  To make sure that every edge is visited only once
-  // (important because an edge's deps are loaded every time it's visited), mark
-  // all outputs of |edge| visited as a first step.  This ensures that edges
-  // with multiple inputs and outputs are visited only once, even in cyclic
-  // graphs.
   for (vector<Node*>::iterator o = edge->outputs_.begin();
        o != edge->outputs_.end(); ++o) {
     if (!(*o)->StatIfNecessary(disk_interface_, err))
@@ -64,19 +87,9 @@
   Node* most_recent_input = NULL;
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
-    if (!(*i)->status_known()) {
-      if (!(*i)->StatIfNecessary(disk_interface_, err))
-        return false;
-      if (Edge* in_edge = (*i)->in_edge()) {
-        if (!RecomputeDirty(in_edge, err))
-          return false;
-      } else {
-        // This input has no in-edge; it is dirty if it is missing.
-        if (!(*i)->exists())
-          EXPLAIN("%s has no in-edge and is missing", (*i)->path().c_str());
-        (*i)->set_dirty(!(*i)->exists());
-      }
-    }
+    // Visit this input.
+    if (!RecomputeDirty(*i, stack, err))
+      return false;
 
     // If an input is not ready, neither are our outputs.
     if (Edge* in_edge = (*i)->in_edge()) {
@@ -119,9 +132,47 @@
   if (dirty && !(edge->is_phony() && edge->inputs_.empty()))
     edge->outputs_ready_ = false;
 
+  // Mark the edge as finished during this walk now that it will no longer
+  // be in the call stack.
+  edge->mark_ = Edge::VisitDone;
+  assert(stack->back() == node);
+  stack->pop_back();
+
   return true;
 }
 
+bool DependencyScan::VerifyDAG(Node* node, vector<Node*>* stack, string* err) {
+  Edge* edge = node->in_edge();
+  assert(edge != NULL);
+
+  // If we have no temporary mark on the edge then we do not yet have a cycle.
+  if (edge->mark_ != Edge::VisitInStack)
+    return true;
+
+  // We have this edge earlier in the call stack.  Find it.
+  vector<Node*>::iterator start = stack->begin();
+  while (start != stack->end() && (*start)->in_edge() != edge)
+    ++start;
+  assert(start != stack->end());
+
+  // Make the cycle clear by reporting its start as the node at its end
+  // instead of some other output of the starting edge.  For example,
+  // running 'ninja b' on
+  //   build a b: cat c
+  //   build c: cat a
+  // should report a -> c -> a instead of b -> c -> a.
+  *start = node;
+
+  // Construct the error message rejecting the cycle.
+  *err = "dependency cycle: ";
+  for (vector<Node*>::const_iterator i = start; i != stack->end(); ++i) {
+    err->append((*i)->path());
+    err->append(" -> ");
+  }
+  err->append((*start)->path());
+  return false;
+}
+
 bool DependencyScan::RecomputeOutputsDirty(Edge* edge, Node* most_recent_input,
                                            bool* outputs_dirty, string* err) {
   string command = edge->EvaluateCommand(/*incl_rsp_file=*/true);
@@ -169,7 +220,7 @@
     bool used_restat = false;
     if (edge->GetBindingBool("restat") && build_log() &&
         (entry = build_log()->LookupByOutput(output->path()))) {
-      output_mtime = entry->restat_mtime;
+      output_mtime = entry->mtime;
       used_restat = true;
     }
 
@@ -183,17 +234,29 @@
     }
   }
 
-  // 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.
-  if (!edge->GetBindingBool("generator") && build_log()) {
+  if (build_log()) {
+    bool generator = edge->GetBindingBool("generator");
     if (entry || (entry = build_log()->LookupByOutput(output->path()))) {
-      if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
+      if (!generator &&
+          BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
+        // 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.
         EXPLAIN("command line changed for %s", output->path().c_str());
         return true;
       }
+      if (most_recent_input && entry->mtime < most_recent_input->mtime()) {
+        // May also be dirty due to the mtime in the log being older than the
+        // mtime of the most recent input.  This can occur even when the mtime
+        // on disk is newer if a previous run wrote to the output file but
+        // exited with an error or was interrupted.
+        EXPLAIN("recorded mtime of %s older than most recent input %s (%d vs %d)",
+                output->path().c_str(), most_recent_input->path().c_str(),
+                entry->mtime, most_recent_input->mtime());
+        return true;
+      }
     }
-    if (!entry) {
+    if (!entry && !generator) {
       EXPLAIN("command line not found in log for %s", output->path().c_str());
       return true;
     }
@@ -348,10 +411,10 @@
 }
 
 // static
-string Node::PathDecanonicalized(const string& path, unsigned int slash_bits) {
+string Node::PathDecanonicalized(const string& path, uint64_t slash_bits) {
   string result = path;
 #ifdef _WIN32
-  unsigned int mask = 1;
+  uint64_t mask = 1;
   for (char* c = &result[0]; (c = strchr(c, '/')) != NULL;) {
     if (slash_bits & mask)
       *c = '\\';
@@ -420,10 +483,12 @@
     return false;
   }
 
-  unsigned int unused;
+  uint64_t unused;
   if (!CanonicalizePath(const_cast<char*>(depfile.out_.str_),
-                        &depfile.out_.len_, &unused, err))
+                        &depfile.out_.len_, &unused, err)) {
+    *err = path + ": " + *err;
     return false;
+  }
 
   // Check that this depfile matches the edge's output, if not return false to
   // mark the edge as dirty.
@@ -442,7 +507,7 @@
   // Add all its in-edges.
   for (vector<StringPiece>::iterator i = depfile.ins_.begin();
        i != depfile.ins_.end(); ++i, ++implicit_dep) {
-    unsigned int slash_bits;
+    uint64_t slash_bits;
     if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits,
                           err))
       return false;
diff --git a/src/graph.h b/src/graph.h
index add8d3d..586c588 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -21,6 +21,7 @@
 
 #include "eval_env.h"
 #include "timestamp.h"
+#include "util.h"
 
 struct BuildLog;
 struct DiskInterface;
@@ -33,7 +34,7 @@
 /// Information about a node in the dependency graph: the file, whether
 /// it's dirty, mtime, etc.
 struct Node {
-  Node(const string& path, unsigned int slash_bits)
+  Node(const string& path, uint64_t slash_bits)
       : path_(path),
         slash_bits_(slash_bits),
         mtime_(-1),
@@ -76,8 +77,8 @@
     return PathDecanonicalized(path_, slash_bits_);
   }
   static string PathDecanonicalized(const string& path,
-                                    unsigned int slash_bits);
-  unsigned int slash_bits() const { return slash_bits_; }
+                                    uint64_t slash_bits);
+  uint64_t slash_bits() const { return slash_bits_; }
 
   TimeStamp mtime() const { return mtime_; }
 
@@ -101,7 +102,7 @@
 
   /// Set bits starting from lowest for backslashes that were normalized to
   /// forward slashes by CanonicalizePath. See |PathDecanonicalized|.
-  unsigned int slash_bits_;
+  uint64_t slash_bits_;
 
   /// Possible values of mtime_:
   ///   -1: file hasn't been examined
@@ -127,7 +128,13 @@
 
 /// An edge in the dependency graph; links between Nodes using Rules.
 struct Edge {
-  Edge() : rule_(NULL), pool_(NULL), env_(NULL),
+  enum VisitMark {
+    VisitNone,
+    VisitInStack,
+    VisitDone
+  };
+
+  Edge() : rule_(NULL), pool_(NULL), env_(NULL), mark_(VisitNone),
            outputs_ready_(false), deps_missing_(false),
            implicit_deps_(0), order_only_deps_(0), implicit_outs_(0) {}
 
@@ -155,6 +162,7 @@
   vector<Node*> inputs_;
   vector<Node*> outputs_;
   BindingEnv* env_;
+  VisitMark mark_;
   bool outputs_ready_;
   bool deps_missing_;
 
@@ -245,11 +253,12 @@
         disk_interface_(disk_interface),
         dep_loader_(state, deps_log, disk_interface) {}
 
+  /// Update the |dirty_| state of the given node by inspecting its input edge.
   /// Examine inputs, outputs, and command lines to judge whether an edge
   /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
   /// state accordingly.
   /// Returns false on failure.
-  bool RecomputeDirty(Edge* edge, string* err);
+  bool RecomputeDirty(Node* node, string* err);
 
   /// Recompute whether any output of the edge is dirty, if so sets |*dirty|.
   /// Returns false on failure.
@@ -268,6 +277,9 @@
   }
 
  private:
+  bool RecomputeDirty(Node* node, vector<Node*>* stack, string* err);
+  bool VerifyDAG(Node* node, vector<Node*>* stack, string* err);
+
   /// Recompute whether a given single output should be marked dirty.
   /// Returns true if so.
   bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input,
diff --git a/src/graph_test.cc b/src/graph_test.cc
index be08b19..d4d2824 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -30,9 +30,8 @@
   fs_.Create("in", "");
   fs_.Create("out", "");
 
-  Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
   ASSERT_EQ("", err);
 
   // A missing implicit dep *should* make the output dirty.
@@ -49,9 +48,8 @@
   fs_.Tick();
   fs_.Create("implicit", "");
 
-  Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
   ASSERT_EQ("", err);
 
   // A modified implicit dep should make the output dirty.
@@ -70,9 +68,8 @@
   fs_.Tick();
   fs_.Create("implicit.h", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
 
   // implicit.h has changed, though our depfile refers to it with a
@@ -94,9 +91,8 @@
   fs_.Tick();
   fs_.Create("data", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
 
   // We have both an implicit and an explicit dep on implicit.h.
@@ -123,9 +119,8 @@
   fs_.Create("in", "");
   fs_.Create("out", "");
 
-  Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -140,9 +135,8 @@
   fs_.Create("in", "");
   fs_.Create("out", "");
 
-  Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -165,9 +159,8 @@
 "build | out.imp: cat in\n"));
   fs_.Create("in", "");
 
-  Edge* edge = GetNode("out.imp")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -180,9 +173,8 @@
   fs_.Tick();
   fs_.Create("in", "");
 
-  Edge* edge = GetNode("out.imp")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -198,9 +190,8 @@
   fs_.Create("out.o.d", "out.o: foo.cc\n");
   fs_.Create("out.o", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -247,9 +238,8 @@
   fs_.Create("out.o.d", "out.o: bar/../foo.cc\n");
   fs_.Create("out.o", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -268,15 +258,14 @@
   fs_.Create("out.o.d", "out.o: foo.h\n");
   fs_.Create("out.o", "");
 
-  Edge* edge = GetNode("out.o")->in_edge();
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
   EXPECT_FALSE(GetNode("out.o")->dirty());
 
   state_.Reset();
   fs_.RemoveFile("out.o.d");
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(GetNode("out.o")->dirty());
 }
@@ -323,8 +312,7 @@
 "build n2: phony n1\n"
   );
   string err;
-  Edge* edge = GetNode("n2")->in_edge();
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), &err));
   ASSERT_EQ("", err);
 
   Plan plan_;
@@ -335,6 +323,55 @@
   ASSERT_FALSE(plan_.more_to_do());
 }
 
+TEST_F(GraphTest, DependencyCycle) {
+  AssertParse(&state_,
+"build out: cat mid\n"
+"build mid: cat in\n"
+"build in: cat pre\n"
+"build pre: cat out\n");
+
+  string err;
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes1) {
+  string err;
+  AssertParse(&state_,
+"build a b: cat a\n");
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  ASSERT_EQ("dependency cycle: a -> a", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes2) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build b a: cat a\n"));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  ASSERT_EQ("dependency cycle: a -> a", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes3) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build a b: cat c\n"
+"build c: cat a\n"));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  ASSERT_EQ("dependency cycle: a -> c -> a", err);
+}
+
+TEST_F(GraphTest, CycleInEdgesButNotInNodes4) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build d: cat c\n"
+"build c: cat b\n"
+"build b: cat a\n"
+"build a e: cat d\n"
+"build f: cat e\n"));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), &err));
+  ASSERT_EQ("dependency cycle: a -> d -> c -> b -> a", err);
+}
+
 // Verify that cycles in graphs with multiple outputs are handled correctly
 // in RecomputeDirty() and don't cause deps to be loaded multiple times.
 TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) {
@@ -347,13 +384,13 @@
   fs_.Create("dep.d", "a: b\n");
 
   string err;
-  Edge* edge = GetNode("a")->in_edge();
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
-  ASSERT_EQ("", err);
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  ASSERT_EQ("dependency cycle: b -> b", err);
 
   // Despite the depfile causing edge to be a cycle (it has outputs a and b,
   // but the depfile also adds b as an input), the deps should have been loaded
   // only once:
+  Edge* edge = GetNode("a")->in_edge();
   EXPECT_EQ(1, edge->inputs_.size());
   EXPECT_EQ("b", edge->inputs_[0]->path());
 }
@@ -372,13 +409,13 @@
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  Edge* edge = GetNode("a")->in_edge();
-  EXPECT_TRUE(scan_.RecomputeDirty(edge, &err));
-  ASSERT_EQ("", err);
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
   // but c's in_edge has b as input but the depfile also adds |edge| as
   // output)), the deps should have been loaded only once:
+  Edge* edge = GetNode("a")->in_edge();
   EXPECT_EQ(1, edge->inputs_.size());
   EXPECT_EQ("c", edge->inputs_[0]->path());
 }
@@ -399,8 +436,8 @@
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d")->in_edge(), &err));
-  ASSERT_EQ("", err);
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), &err));
+  ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
   // but c's in_edge has b as input but the depfile also adds |edge| as
diff --git a/src/includes_normalize-win32.cc b/src/includes_normalize-win32.cc
index ca35012..459329b 100644
--- a/src/includes_normalize-win32.cc
+++ b/src/includes_normalize-win32.cc
@@ -15,6 +15,7 @@
 #include "includes_normalize.h"
 
 #include "string_piece.h"
+#include "string_piece_util.h"
 #include "util.h"
 
 #include <algorithm>
@@ -25,8 +26,39 @@
 
 namespace {
 
-/// Return true if paths a and b are on the same Windows drive.
+bool IsPathSeparator(char c) {
+  return c == '/' ||  c == '\\';
+}
+
+// Return true if paths a and b are on the same windows drive.
+// Return false if this funcation cannot check
+// whether or not on the same windows drive.
+bool SameDriveFast(StringPiece a, StringPiece b) {
+  if (a.size() < 3 || b.size() < 3) {
+    return false;
+  }
+
+  if (!islatinalpha(a[0]) || !islatinalpha(b[0])) {
+    return false;
+  }
+
+  if (ToLowerASCII(a[0]) != ToLowerASCII(b[0])) {
+    return false;
+  }
+
+  if (a[1] != ':' || b[1] != ':') {
+    return false;
+  }
+
+  return IsPathSeparator(a[2]) && IsPathSeparator(b[2]);
+}
+
+// Return true if paths a and b are on the same Windows drive.
 bool SameDrive(StringPiece a, StringPiece b)  {
+  if (SameDriveFast(a, b)) {
+    return true;
+  }
+
   char a_absolute[_MAX_PATH];
   char b_absolute[_MAX_PATH];
   GetFullPathName(a.AsString().c_str(), sizeof(a_absolute), a_absolute, NULL);
@@ -38,34 +70,57 @@
   return _stricmp(a_drive, b_drive) == 0;
 }
 
+// Check path |s| is FullPath style returned by GetFullPathName.
+// This ignores difference of path separator.
+// This is used not to call very slow GetFullPathName API.
+bool IsFullPathName(StringPiece s) {
+  if (s.size() < 3 ||
+      !islatinalpha(s[0]) ||
+      s[1] != ':' ||
+      !IsPathSeparator(s[2])) {
+    return false;
+  }
+
+  // Check "." or ".." is contained in path.
+  for (size_t i = 2; i < s.size(); ++i) {
+    if (!IsPathSeparator(s[i])) {
+      continue;
+    }
+
+    // Check ".".
+    if (i + 1 < s.size() && s[i+1] == '.' &&
+        (i + 2 >= s.size() || IsPathSeparator(s[i+2]))) {
+      return false;
+    }
+
+    // Check "..".
+    if (i + 2 < s.size() && s[i+1] == '.' && s[i+2] == '.' &&
+        (i + 3 >= s.size() || IsPathSeparator(s[i+3]))) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
 }  // anonymous namespace
 
-string IncludesNormalize::Join(const vector<string>& list, char sep) {
-  string ret;
-  for (size_t i = 0; i < list.size(); ++i) {
-    ret += list[i];
-    if (i != list.size() - 1)
-      ret += sep;
-  }
-  return ret;
-}
-
-vector<string> IncludesNormalize::Split(const string& input, char sep) {
-  vector<string> elems;
-  stringstream ss(input);
-  string item;
-  while (getline(ss, item, sep))
-    elems.push_back(item);
-  return elems;
-}
-
-string IncludesNormalize::ToLower(const string& s) {
-  string ret;
-  transform(s.begin(), s.end(), back_inserter(ret), ::tolower);
-  return ret;
+IncludesNormalize::IncludesNormalize(const string& relative_to) {
+  relative_to_ = AbsPath(relative_to);
+  split_relative_to_ = SplitStringPiece(relative_to_, '/');
 }
 
 string IncludesNormalize::AbsPath(StringPiece s) {
+  if (IsFullPathName(s)) {
+    string result = s.AsString();
+    for (size_t i = 0; i < result.size(); ++i) {
+      if (result[i] == '\\') {
+        result[i] = '/';
+      }
+    }
+    return result;
+  }
+
   char result[_MAX_PATH];
   GetFullPathName(s.AsString().c_str(), sizeof(result), result, NULL);
   for (char* c = result; *c; ++c)
@@ -74,28 +129,31 @@
   return result;
 }
 
-string IncludesNormalize::Relativize(StringPiece path, const string& start) {
-  vector<string> start_list = Split(AbsPath(start), '/');
-  vector<string> path_list = Split(AbsPath(path), '/');
+string IncludesNormalize::Relativize(
+    StringPiece path, const vector<StringPiece>& start_list) {
+  string abs_path = AbsPath(path);
+  vector<StringPiece> path_list = SplitStringPiece(abs_path, '/');
   int i;
   for (i = 0; i < static_cast<int>(min(start_list.size(), path_list.size()));
        ++i) {
-    if (ToLower(start_list[i]) != ToLower(path_list[i]))
+    if (!EqualsCaseInsensitiveASCII(start_list[i], path_list[i])) {
       break;
+    }
   }
 
-  vector<string> rel_list;
+  vector<StringPiece> rel_list;
+  rel_list.reserve(start_list.size() - i + path_list.size() - i);
   for (int j = 0; j < static_cast<int>(start_list.size() - i); ++j)
     rel_list.push_back("..");
   for (int j = i; j < static_cast<int>(path_list.size()); ++j)
     rel_list.push_back(path_list[j]);
   if (rel_list.size() == 0)
     return ".";
-  return Join(rel_list, '/');
+  return JoinStringPiece(rel_list, '/');
 }
 
-bool IncludesNormalize::Normalize(const string& input, const char* relative_to,
-                                  string* result, string* err) {
+bool IncludesNormalize::Normalize(const string& input,
+                                  string* result, string* err) const {
   char copy[_MAX_PATH + 1];
   size_t len = input.size();
   if (len > _MAX_PATH) {
@@ -103,20 +161,16 @@
     return false;
   }
   strncpy(copy, input.c_str(), input.size() + 1);
-  unsigned int slash_bits;
+  uint64_t slash_bits;
   if (!CanonicalizePath(copy, &len, &slash_bits, err))
     return false;
   StringPiece partially_fixed(copy, len);
+  string abs_input = AbsPath(partially_fixed);
 
-  string curdir;
-  if (!relative_to) {
-    curdir = AbsPath(".");
-    relative_to = curdir.c_str();
-  }
-  if (!SameDrive(partially_fixed, relative_to)) {
+  if (!SameDrive(abs_input, relative_to_)) {
     *result = partially_fixed.AsString();
     return true;
   }
-  *result = Relativize(partially_fixed, relative_to);
+  *result = Relativize(abs_input, split_relative_to_);
   return true;
 }
diff --git a/src/includes_normalize.h b/src/includes_normalize.h
index 98e912f..3811e53 100644
--- a/src/includes_normalize.h
+++ b/src/includes_normalize.h
@@ -21,15 +21,19 @@
 /// Utility functions for normalizing include paths on Windows.
 /// TODO: this likely duplicates functionality of CanonicalizePath; refactor.
 struct IncludesNormalize {
+  /// Normalize path relative to |relative_to|.
+  IncludesNormalize(const string& relative_to);
+
   // Internal utilities made available for testing, maybe useful otherwise.
-  static string Join(const vector<string>& list, char sep);
-  static vector<string> Split(const string& input, char sep);
-  static string ToLower(const string& s);
   static string AbsPath(StringPiece s);
-  static string Relativize(StringPiece path, const string& start);
+  static string Relativize(StringPiece path,
+                           const vector<StringPiece>& start_list);
 
   /// Normalize by fixing slashes style, fixing redundant .. and . and makes the
-  /// path relative to |relative_to|.
-  static bool Normalize(const string& input, const char* relative_to,
-                        string* result, string* err);
+  /// path |input| relative to |this->relative_to_| and store to |result|.
+  bool Normalize(const string& input, string* result, string* err) const;
+
+ private:
+  string relative_to_;
+  vector<StringPiece> split_relative_to_;
 };
diff --git a/src/includes_normalize_test.cc b/src/includes_normalize_test.cc
index f18795c..0bb14ec 100644
--- a/src/includes_normalize_test.cc
+++ b/src/includes_normalize_test.cc
@@ -18,6 +18,7 @@
 
 #include <direct.h>
 
+#include "string_piece_util.h"
 #include "test.h"
 #include "util.h"
 
@@ -26,13 +27,14 @@
 string GetCurDir() {
   char buf[_MAX_PATH];
   _getcwd(buf, sizeof(buf));
-  vector<string> parts = IncludesNormalize::Split(string(buf), '\\');
-  return parts[parts.size() - 1];
+  vector<StringPiece> parts = SplitStringPiece(buf, '\\');
+  return parts[parts.size() - 1].AsString();
 }
 
 string NormalizeAndCheckNoError(const string& input) {
   string result, err;
-  EXPECT_TRUE(IncludesNormalize::Normalize(input.c_str(), NULL, &result, &err));
+  IncludesNormalize normalizer(".");
+  EXPECT_TRUE(normalizer.Normalize(input, &result, &err));
   EXPECT_EQ("", err);
   return result;
 }
@@ -40,8 +42,8 @@
 string NormalizeRelativeAndCheckNoError(const string& input,
                                         const string& relative_to) {
   string result, err;
-  EXPECT_TRUE(IncludesNormalize::Normalize(input.c_str(), relative_to.c_str(),
-                                           &result, &err));
+  IncludesNormalize normalizer(relative_to);
+  EXPECT_TRUE(normalizer.Normalize(input, &result, &err));
   EXPECT_EQ("", err);
   return result;
 }
@@ -76,34 +78,6 @@
   EXPECT_EQ("A/B", NormalizeAndCheckNoError("A\\./B"));
 }
 
-TEST(IncludesNormalize, Join) {
-  vector<string> x;
-  EXPECT_EQ("", IncludesNormalize::Join(x, ':'));
-  x.push_back("alpha");
-  EXPECT_EQ("alpha", IncludesNormalize::Join(x, ':'));
-  x.push_back("beta");
-  x.push_back("gamma");
-  EXPECT_EQ("alpha:beta:gamma", IncludesNormalize::Join(x, ':'));
-}
-
-TEST(IncludesNormalize, Split) {
-  EXPECT_EQ("", IncludesNormalize::Join(IncludesNormalize::Split("", '/'),
-                                        ':'));
-  EXPECT_EQ("a", IncludesNormalize::Join(IncludesNormalize::Split("a", '/'),
-                                         ':'));
-  EXPECT_EQ("a:b:c",
-            IncludesNormalize::Join(
-                IncludesNormalize::Split("a/b/c", '/'), ':'));
-}
-
-TEST(IncludesNormalize, ToLower) {
-  EXPECT_EQ("", IncludesNormalize::ToLower(""));
-  EXPECT_EQ("stuff", IncludesNormalize::ToLower("Stuff"));
-  EXPECT_EQ("stuff and things", IncludesNormalize::ToLower("Stuff AND thINGS"));
-  EXPECT_EQ("stuff 3and thin43gs",
-            IncludesNormalize::ToLower("Stuff 3AND thIN43GS"));
-}
-
 TEST(IncludesNormalize, DifferentDrive) {
   EXPECT_EQ("stuff.h",
             NormalizeRelativeAndCheckNoError("p:\\vs08\\stuff.h", "p:\\vs08"));
@@ -129,8 +103,9 @@
       "instead of /Zi, but expect a similar error when you link your program.";
   // Too long, won't be canonicalized. Ensure doesn't crash.
   string result, err;
+  IncludesNormalize normalizer(".");
   EXPECT_FALSE(
-      IncludesNormalize::Normalize(kLongInputString, NULL, &result, &err));
+      normalizer.Normalize(kLongInputString, &result, &err));
   EXPECT_EQ("path too long", err);
 
   const char kExactlyMaxPath[] =
diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc
index d6dcf22..2164921 100644
--- a/src/manifest_parser.cc
+++ b/src/manifest_parser.cc
@@ -212,7 +212,7 @@
   do {
     string path = eval.Evaluate(env_);
     string path_err;
-    unsigned int slash_bits;  // Unused because this only does lookup.
+    uint64_t slash_bits;  // Unused because this only does lookup.
     if (!CanonicalizePath(&path, &slash_bits, &path_err))
       return lexer_.Error(path_err, err);
     if (!state_->AddDefault(path, &path_err))
@@ -342,7 +342,7 @@
   for (size_t i = 0, e = outs.size(); i != e; ++i) {
     string path = outs[i].Evaluate(env);
     string path_err;
-    unsigned int slash_bits;
+    uint64_t slash_bits;
     if (!CanonicalizePath(&path, &slash_bits, &path_err))
       return lexer_.Error(path_err, err);
     if (!state_->AddOut(edge, path, slash_bits)) {
@@ -375,7 +375,7 @@
   for (vector<EvalString>::iterator i = ins.begin(); i != ins.end(); ++i) {
     string path = i->Evaluate(env);
     string path_err;
-    unsigned int slash_bits;
+    uint64_t slash_bits;
     if (!CanonicalizePath(&path, &slash_bits, &path_err))
       return lexer_.Error(path_err, err);
     state_->AddIn(edge, path, slash_bits);
diff --git a/src/minidump-win32.cc b/src/minidump-win32.cc
index c611919..1efb085 100644
--- a/src/minidump-win32.cc
+++ b/src/minidump-win32.cc
@@ -34,7 +34,7 @@
   char temp_path[MAX_PATH];
   GetTempPath(sizeof(temp_path), temp_path);
   char temp_file[MAX_PATH];
-  sprintf(temp_file, "%s\\ninja_crash_dump_%d.dmp",
+  sprintf(temp_file, "%s\\ninja_crash_dump_%lu.dmp",
           temp_path, GetCurrentProcessId());
 
   // Delete any previous minidump of the same name.
diff --git a/src/ninja.cc b/src/ninja.cc
index 25eafe8..54de7b9 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -233,7 +233,7 @@
 /// Returns true if the manifest was rebuilt.
 bool NinjaMain::RebuildManifest(const char* input_file, string* err) {
   string path = input_file;
-  unsigned int slash_bits;  // Unused because this path is only used for lookup.
+  uint64_t slash_bits;  // Unused because this path is only used for lookup.
   if (!CanonicalizePath(&path, &slash_bits, err))
     return false;
   Node* node = state_.LookupNode(path);
@@ -247,15 +247,24 @@
   if (builder.AlreadyUpToDate())
     return false;  // Not an error, but we didn't rebuild.
 
-  // Even if the manifest was cleaned by a restat rule, claim that it was
-  // rebuilt.  Not doing so can lead to crashes, see
-  // https://github.com/ninja-build/ninja/issues/874
-  return builder.Build(err);
+  if (!builder.Build(err))
+    return false;
+
+  // The manifest was only rebuilt if it is now dirty (it may have been cleaned
+  // by a restat).
+  if (!node->dirty()) {
+    // Reset the state to prevent problems like
+    // https://github.com/ninja-build/ninja/issues/874
+    state_.Reset();
+    return false;
+  }
+
+  return true;
 }
 
 Node* NinjaMain::CollectTarget(const char* cpath, string* err) {
   string path = cpath;
-  unsigned int slash_bits;
+  uint64_t slash_bits;
   if (!CanonicalizePath(&path, &slash_bits, err))
     return NULL;
 
@@ -533,21 +542,51 @@
   }
 }
 
-void PrintCommands(Edge* edge, set<Edge*>* seen) {
+enum PrintCommandMode { PCM_Single, PCM_All };
+void PrintCommands(Edge* edge, set<Edge*>* seen, PrintCommandMode mode) {
   if (!edge)
     return;
   if (!seen->insert(edge).second)
     return;
 
-  for (vector<Node*>::iterator in = edge->inputs_.begin();
-       in != edge->inputs_.end(); ++in)
-    PrintCommands((*in)->in_edge(), seen);
+  if (mode == PCM_All) {
+    for (vector<Node*>::iterator in = edge->inputs_.begin();
+         in != edge->inputs_.end(); ++in)
+      PrintCommands((*in)->in_edge(), seen, mode);
+  }
 
   if (!edge->is_phony())
     puts(edge->EvaluateCommand().c_str());
 }
 
 int NinjaMain::ToolCommands(const Options* options, int argc, char* argv[]) {
+  // The clean tool uses getopt, and expects argv[0] to contain the name of
+  // the tool, i.e. "commands".
+  ++argc;
+  --argv;
+
+  PrintCommandMode mode = PCM_All;
+
+  optind = 1;
+  int opt;
+  while ((opt = getopt(argc, argv, const_cast<char*>("hs"))) != -1) {
+    switch (opt) {
+    case 's':
+      mode = PCM_Single;
+      break;
+    case 'h':
+    default:
+      printf("usage: ninja -t commands [options] [targets]\n"
+"\n"
+"options:\n"
+"  -s     only print the final command to build [target], not the whole chain\n"
+             );
+    return 1;
+    }
+  }
+  argv += optind;
+  argc -= optind;
+
   vector<Node*> nodes;
   string err;
   if (!CollectTargetsFromArgs(argc, argv, &nodes, &err)) {
@@ -557,7 +596,7 @@
 
   set<Edge*> seen;
   for (vector<Node*>::iterator in = nodes.begin(); in != nodes.end(); ++in)
-    PrintCommands((*in)->in_edge(), &seen);
+    PrintCommands((*in)->in_edge(), &seen, mode);
 
   return 0;
 }
diff --git a/src/state.cc b/src/state.cc
index d539e7b..9b3c7e1 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -100,7 +100,7 @@
   return edge;
 }
 
-Node* State::GetNode(StringPiece path, unsigned int slash_bits) {
+Node* State::GetNode(StringPiece path, uint64_t slash_bits) {
   Node* node = LookupNode(path);
   if (node)
     return node;
@@ -134,13 +134,13 @@
   return result;
 }
 
-void State::AddIn(Edge* edge, StringPiece path, unsigned int slash_bits) {
+void State::AddIn(Edge* edge, StringPiece path, uint64_t slash_bits) {
   Node* node = GetNode(path, slash_bits);
   edge->inputs_.push_back(node);
   node->AddOutEdge(edge);
 }
 
-bool State::AddOut(Edge* edge, StringPiece path, unsigned int slash_bits) {
+bool State::AddOut(Edge* edge, StringPiece path, uint64_t slash_bits) {
   Node* node = GetNode(path, slash_bits);
   if (node->in_edge())
     return false;
@@ -184,8 +184,10 @@
 void State::Reset() {
   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i)
     i->second->ResetState();
-  for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e)
+  for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) {
     (*e)->outputs_ready_ = false;
+    (*e)->mark_ = Edge::VisitNone;
+  }
 }
 
 void State::Dump() {
diff --git a/src/state.h b/src/state.h
index b530207..54e9dc5 100644
--- a/src/state.h
+++ b/src/state.h
@@ -23,6 +23,7 @@
 
 #include "eval_env.h"
 #include "hash_map.h"
+#include "util.h"
 
 struct Edge;
 struct Node;
@@ -93,12 +94,12 @@
 
   Edge* AddEdge(const Rule* rule);
 
-  Node* GetNode(StringPiece path, unsigned int slash_bits);
+  Node* GetNode(StringPiece path, uint64_t slash_bits);
   Node* LookupNode(StringPiece path) const;
   Node* SpellcheckNode(const string& path);
 
-  void AddIn(Edge* edge, StringPiece path, unsigned int slash_bits);
-  bool AddOut(Edge* edge, StringPiece path, unsigned int slash_bits);
+  void AddIn(Edge* edge, StringPiece path, uint64_t slash_bits);
+  bool AddOut(Edge* edge, StringPiece path, uint64_t slash_bits);
   bool AddDefault(StringPiece path, string* error);
 
   /// Reset state.  Keeps all nodes and edges, but restores them to the
diff --git a/src/string_piece.h b/src/string_piece.h
index b1bf105..031bda4 100644
--- a/src/string_piece.h
+++ b/src/string_piece.h
@@ -25,6 +25,8 @@
 /// externally.  It is useful for reducing the number of std::strings
 /// we need to allocate.
 struct StringPiece {
+  typedef const char* const_iterator;
+
   StringPiece() : str_(NULL), len_(0) {}
 
   /// The constructors intentionally allow for implicit conversions.
@@ -46,6 +48,22 @@
     return len_ ? string(str_, len_) : string();
   }
 
+  const_iterator begin() const {
+    return str_;
+  }
+
+  const_iterator end() const {
+    return str_ + len_;
+  }
+
+  char operator[](size_t pos) const {
+    return str_[pos];
+  }
+
+  size_t size() const {
+    return len_;
+  }
+
   const char* str_;
   size_t len_;
 };
diff --git a/src/string_piece_util.cc b/src/string_piece_util.cc
new file mode 100644
index 0000000..8e1ecfd
--- /dev/null
+++ b/src/string_piece_util.cc
@@ -0,0 +1,78 @@
+// Copyright 2017 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 "string_piece_util.h"
+
+#include <algorithm>
+#include <string>
+#include <vector>
+using namespace std;
+
+vector<StringPiece> SplitStringPiece(StringPiece input, char sep) {
+  vector<StringPiece> elems;
+  elems.reserve(count(input.begin(), input.end(), sep) + 1);
+
+  StringPiece::const_iterator pos = input.begin();
+
+  for (;;) {
+    const char* next_pos = find(pos, input.end(), sep);
+    if (next_pos == input.end()) {
+      elems.push_back(StringPiece(pos, input.end() - pos));
+      break;
+    }
+    elems.push_back(StringPiece(pos, next_pos - pos));
+    pos = next_pos + 1;
+  }
+
+  return elems;
+}
+
+string JoinStringPiece(const vector<StringPiece>& list, char sep) {
+  if (list.size() == 0){
+    return "";
+  }
+
+  string ret;
+
+  {
+    size_t cap = list.size() - 1;
+    for (size_t i = 0; i < list.size(); ++i) {
+      cap += list[i].len_;
+    }
+    ret.reserve(cap);
+  }
+
+  for (size_t i = 0; i < list.size(); ++i) {
+    if (i != 0) {
+      ret += sep;
+    }
+    ret.append(list[i].str_, list[i].len_);
+  }
+
+  return ret;
+}
+
+bool EqualsCaseInsensitiveASCII(StringPiece a, StringPiece b) {
+  if (a.len_ != b.len_) {
+    return false;
+  }
+
+  for (size_t i = 0; i < a.len_; ++i) {
+    if (ToLowerASCII(a.str_[i]) != ToLowerASCII(b.str_[i])) {
+      return false;
+    }
+  }
+
+  return true;
+}
diff --git a/src/string_piece_util.h b/src/string_piece_util.h
new file mode 100644
index 0000000..2e40b9f
--- /dev/null
+++ b/src/string_piece_util.h
@@ -0,0 +1,34 @@
+// Copyright 2017 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_STRINGPIECE_UTIL_H_
+#define NINJA_STRINGPIECE_UTIL_H_
+
+#include <string>
+#include <vector>
+
+#include "string_piece.h"
+using namespace std;
+
+vector<StringPiece> SplitStringPiece(StringPiece input, char sep);
+
+string JoinStringPiece(const vector<StringPiece>& list, char sep);
+
+inline char ToLowerASCII(char c) {
+  return (c >= 'A' && c <= 'Z') ? (c + ('a' - 'A')) : c;
+}
+
+bool EqualsCaseInsensitiveASCII(StringPiece a, StringPiece b);
+
+#endif  // NINJA_STRINGPIECE_UTIL_H_
diff --git a/src/string_piece_util_test.cc b/src/string_piece_util_test.cc
new file mode 100644
index 0000000..648c647
--- /dev/null
+++ b/src/string_piece_util_test.cc
@@ -0,0 +1,129 @@
+// Copyright 2017 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 "string_piece_util.h"
+
+#include "test.h"
+
+TEST(StringPieceUtilTest, SplitStringPiece) {
+  {
+    string input("a:b:c");
+    vector<StringPiece> list = SplitStringPiece(input, ':');
+
+    EXPECT_EQ(list.size(), 3);
+
+    EXPECT_EQ(list[0], "a");
+    EXPECT_EQ(list[1], "b");
+    EXPECT_EQ(list[2], "c");
+  }
+
+  {
+    string empty("");
+    vector<StringPiece> list = SplitStringPiece(empty, ':');
+
+    EXPECT_EQ(list.size(), 1);
+
+    EXPECT_EQ(list[0], "");
+  }
+
+  {
+    string one("a");
+    vector<StringPiece> list = SplitStringPiece(one, ':');
+
+    EXPECT_EQ(list.size(), 1);
+
+    EXPECT_EQ(list[0], "a");
+  }
+
+  {
+    string sep_only(":");
+    vector<StringPiece> list = SplitStringPiece(sep_only, ':');
+
+    EXPECT_EQ(list.size(), 2);
+
+    EXPECT_EQ(list[0], "");
+    EXPECT_EQ(list[1], "");
+  }
+
+  {
+    string sep(":a:b:c:");
+    vector<StringPiece> list = SplitStringPiece(sep, ':');
+
+    EXPECT_EQ(list.size(), 5);
+
+    EXPECT_EQ(list[0], "");
+    EXPECT_EQ(list[1], "a");
+    EXPECT_EQ(list[2], "b");
+    EXPECT_EQ(list[3], "c");
+    EXPECT_EQ(list[4], "");
+  }
+}
+
+TEST(StringPieceUtilTest, JoinStringPiece) {
+  {
+    string input("a:b:c");
+    vector<StringPiece> list = SplitStringPiece(input, ':');
+
+    EXPECT_EQ("a:b:c", JoinStringPiece(list, ':'));
+    EXPECT_EQ("a/b/c", JoinStringPiece(list, '/'));
+  }
+
+  {
+    string empty("");
+    vector<StringPiece> list = SplitStringPiece(empty, ':');
+
+    EXPECT_EQ("", JoinStringPiece(list, ':'));
+  }
+
+  {
+    vector<StringPiece> empty_list;
+
+    EXPECT_EQ("", JoinStringPiece(empty_list, ':'));
+  }
+
+  {
+    string one("a");
+    vector<StringPiece> single_list = SplitStringPiece(one, ':');
+
+    EXPECT_EQ("a", JoinStringPiece(single_list, ':'));
+  }
+
+  {
+    string sep(":a:b:c:");
+    vector<StringPiece> list = SplitStringPiece(sep, ':');
+
+    EXPECT_EQ(":a:b:c:", JoinStringPiece(list, ':'));
+  }
+}
+
+TEST(StringPieceUtilTest, ToLowerASCII) {
+  EXPECT_EQ('a', ToLowerASCII('A'));
+  EXPECT_EQ('z', ToLowerASCII('Z'));
+  EXPECT_EQ('a', ToLowerASCII('a'));
+  EXPECT_EQ('z', ToLowerASCII('z'));
+  EXPECT_EQ('/', ToLowerASCII('/'));
+  EXPECT_EQ('1', ToLowerASCII('1'));
+}
+
+TEST(StringPieceUtilTest, EqualsCaseInsensitiveASCII) {
+  EXPECT_TRUE(EqualsCaseInsensitiveASCII("abc", "abc"));
+  EXPECT_TRUE(EqualsCaseInsensitiveASCII("abc", "ABC"));
+  EXPECT_TRUE(EqualsCaseInsensitiveASCII("abc", "aBc"));
+  EXPECT_TRUE(EqualsCaseInsensitiveASCII("AbC", "aBc"));
+  EXPECT_TRUE(EqualsCaseInsensitiveASCII("", ""));
+
+  EXPECT_FALSE(EqualsCaseInsensitiveASCII("a", "ac"));
+  EXPECT_FALSE(EqualsCaseInsensitiveASCII("/", "\\"));
+  EXPECT_FALSE(EqualsCaseInsensitiveASCII("1", "10"));
+}
diff --git a/src/subprocess-posix.cc b/src/subprocess-posix.cc
index 5ffe85b..1de22c3 100644
--- a/src/subprocess-posix.cc
+++ b/src/subprocess-posix.cc
@@ -73,8 +73,6 @@
   // default action in the new process image, so no explicit
   // POSIX_SPAWN_SETSIGDEF parameter is needed.
 
-  // TODO: Consider using POSIX_SPAWN_USEVFORK on Linux with glibc?
-
   if (!use_console_) {
     // Put the child in its own process group, so ctrl-c won't reach it.
     flags |= POSIX_SPAWN_SETPGROUP;
@@ -90,9 +88,14 @@
       Fatal("posix_spawn_file_actions_adddup2: %s", strerror(errno));
     if (posix_spawn_file_actions_adddup2(&action, output_pipe[1], 2) != 0)
       Fatal("posix_spawn_file_actions_adddup2: %s", strerror(errno));
+    if (posix_spawn_file_actions_addclose(&action, output_pipe[1]) != 0)
+      Fatal("posix_spawn_file_actions_addclose: %s", strerror(errno));
     // In the console case, output_pipe is still inherited by the child and
     // closed when the subprocess finishes, which then notifies ninja.
   }
+#ifdef POSIX_SPAWN_USEVFORK
+  flags |= POSIX_SPAWN_USEVFORK;
+#endif
 
   if (posix_spawnattr_setflags(&attr, flags) != 0)
     Fatal("posix_spawnattr_setflags: %s", strerror(errno));
diff --git a/src/util.cc b/src/util.cc
index e31fd1f..ae94d34 100644
--- a/src/util.cc
+++ b/src/util.cc
@@ -90,7 +90,7 @@
   fprintf(stderr, "\n");
 }
 
-bool CanonicalizePath(string* path, unsigned int* slash_bits, string* err) {
+bool CanonicalizePath(string* path, uint64_t* slash_bits, string* err) {
   METRIC_RECORD("canonicalize str");
   size_t len = path->size();
   char* str = 0;
@@ -102,20 +102,15 @@
   return true;
 }
 
+static bool IsPathSeparator(char c) {
 #ifdef _WIN32
-static unsigned int ShiftOverBit(int offset, unsigned int bits) {
-  // e.g. for |offset| == 2:
-  // | ... 9 8 7 6 5 4 3 2 1 0 |
-  // \_________________/   \_/
-  //        above         below
-  // So we drop the bit at offset and move above "down" into its place.
-  unsigned int above = bits & ~((1 << (offset + 1)) - 1);
-  unsigned int below = bits & ((1 << offset) - 1);
-  return (above >> 1) | below;
-}
+  return c == '/' || c == '\\';
+#else
+  return c == '/';
 #endif
+}
 
-bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits,
+bool CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits,
                       string* err) {
   // WARNING: this function is performance-critical; please benchmark
   // any changes you make to it.
@@ -125,7 +120,7 @@
     return false;
   }
 
-  const int kMaxPathComponents = 30;
+  const int kMaxPathComponents = 60;
   char* components[kMaxPathComponents];
   int component_count = 0;
 
@@ -134,37 +129,13 @@
   const char* src = start;
   const char* end = start + *len;
 
+  if (IsPathSeparator(*src)) {
 #ifdef _WIN32
-  unsigned int bits = 0;
-  unsigned int bits_mask = 1;
-  int bits_offset = 0;
-  // Convert \ to /, setting a bit in |bits| for each \ encountered.
-  for (char* c = path; c < end; ++c) {
-    switch (*c) {
-      case '\\':
-        bits |= bits_mask;
-        *c = '/';
-        // Intentional fallthrough.
-      case '/':
-        bits_mask <<= 1;
-        bits_offset++;
-    }
-  }
-  if (bits_offset > 32) {
-    *err = "too many path components";
-    return false;
-  }
-  bits_offset = 0;
-#endif
 
-  if (*src == '/') {
-#ifdef _WIN32
-    bits_offset++;
     // network path starts with //
-    if (*len > 1 && *(src + 1) == '/') {
+    if (*len > 1 && IsPathSeparator(*(src + 1))) {
       src += 2;
       dst += 2;
-      bits_offset++;
     } else {
       ++src;
       ++dst;
@@ -177,24 +148,16 @@
 
   while (src < end) {
     if (*src == '.') {
-      if (src + 1 == end || src[1] == '/') {
+      if (src + 1 == end || IsPathSeparator(src[1])) {
         // '.' component; eliminate.
         src += 2;
-#ifdef _WIN32
-        bits = ShiftOverBit(bits_offset, bits);
-#endif
         continue;
-      } else if (src[1] == '.' && (src + 2 == end || src[2] == '/')) {
+      } else if (src[1] == '.' && (src + 2 == end || IsPathSeparator(src[2]))) {
         // '..' component.  Back up if possible.
         if (component_count > 0) {
           dst = components[component_count - 1];
           src += 3;
           --component_count;
-#ifdef _WIN32
-          bits = ShiftOverBit(bits_offset, bits);
-          bits_offset--;
-          bits = ShiftOverBit(bits_offset, bits);
-#endif
         } else {
           *dst++ = *src++;
           *dst++ = *src++;
@@ -204,11 +167,8 @@
       }
     }
 
-    if (*src == '/') {
+    if (IsPathSeparator(*src)) {
       src++;
-#ifdef _WIN32
-      bits = ShiftOverBit(bits_offset, bits);
-#endif
       continue;
     }
 
@@ -217,11 +177,8 @@
     components[component_count] = dst;
     ++component_count;
 
-    while (*src != '/' && src != end)
+    while (src != end && !IsPathSeparator(*src))
       *dst++ = *src++;
-#ifdef _WIN32
-    bits_offset++;
-#endif
     *dst++ = *src++;  // Copy '/' or final \0 character as well.
   }
 
@@ -232,6 +189,20 @@
 
   *len = dst - start - 1;
 #ifdef _WIN32
+  uint64_t bits = 0;
+  uint64_t bits_mask = 1;
+
+  for (char* c = start; c < start + *len; ++c) {
+    switch (*c) {
+      case '\\':
+        bits |= bits_mask;
+        *c = '/';
+        // Intentional fallthrough.
+      case '/':
+        bits_mask <<= 1;
+    }
+  }
+
   *slash_bits = bits;
 #else
   *slash_bits = 0;
@@ -471,7 +442,7 @@
 }
 #endif
 
-static bool islatinalpha(int c) {
+bool islatinalpha(int c) {
   // isalpha() is locale-dependent.
   return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
 }
@@ -585,6 +556,13 @@
   // Calculation taken from comment in libperfstats.h
   return double(cpu_stats.loadavg[0]) / double(1 << SBITS);
 }
+#elif defined(__UCLIBC__)
+double GetLoadAverage() {
+  struct sysinfo si;
+  if (sysinfo(&si) != 0)
+    return -0.0f;
+  return 1.0 / (1 << SI_LOAD_SHIFT) * si.loads[0];
+}
 #else
 double GetLoadAverage() {
   double loadavg[3] = { 0.0f, 0.0f, 0.0f };
diff --git a/src/util.h b/src/util.h
index cbdc1a6..4ee41a5 100644
--- a/src/util.h
+++ b/src/util.h
@@ -43,8 +43,8 @@
 /// Canonicalize a path like "foo/../bar.h" into just "bar.h".
 /// |slash_bits| has bits set starting from lowest for a backslash that was
 /// normalized to a forward slash. (only used on Windows)
-bool CanonicalizePath(string* path, unsigned int* slash_bits, string* err);
-bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits,
+bool CanonicalizePath(string* path, uint64_t* slash_bits, string* err);
+bool CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits,
                       string* err);
 
 /// Appends |input| to |*result|, escaping according to the whims of either
@@ -70,6 +70,8 @@
 /// Like SpellcheckStringV, but takes a NULL-terminated list.
 const char* SpellcheckString(const char* text, ...);
 
+bool islatinalpha(int c);
+
 /// Removes all Ansi escape codes (http://www.termsys.demon.co.uk/vtansi.htm).
 string StripAnsiEscapeCodes(const string& in);
 
diff --git a/src/util_test.cc b/src/util_test.cc
index 33a4107..b4b7516 100644
--- a/src/util_test.cc
+++ b/src/util_test.cc
@@ -19,7 +19,7 @@
 namespace {
 
 bool CanonicalizePath(string* path, string* err) {
-  unsigned int unused;
+  uint64_t unused;
   return ::CanonicalizePath(path, &unused, err);
 }
 
@@ -177,7 +177,7 @@
 TEST(CanonicalizePath, SlashTracking) {
   string path;
   string err;
-  unsigned int slash_bits;
+  uint64_t slash_bits;
 
   path = "foo.h"; err = "";
   EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
@@ -263,7 +263,7 @@
 TEST(CanonicalizePath, CanonicalizeNotExceedingLen) {
   // Make sure searching \/ doesn't go past supplied len.
   char buf[] = "foo/bar\\baz.h\\";  // Last \ past end.
-  unsigned int slash_bits;
+  uint64_t slash_bits;
   string err;
   size_t size = 13;
   EXPECT_TRUE(::CanonicalizePath(buf, &size, &slash_bits, &err));
@@ -274,33 +274,60 @@
 TEST(CanonicalizePath, TooManyComponents) {
   string path;
   string err;
-  unsigned int slash_bits;
+  uint64_t slash_bits;
 
-  // 32 is OK.
-  path = "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./x.h";
+  // 64 is OK.
+  path = "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./"
+         "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./x.h";
   EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  EXPECT_EQ(slash_bits, 0x0);
 
   // Backslashes version.
   path =
-      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\."
-      "\\a\\.\\a\\.\\a\\.\\a\\.\\x.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
-  EXPECT_EQ(slash_bits, 0xffff);
+      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\"
+      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\"
+      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\"
+      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\x.h";
 
-  // 33 is not.
+  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  EXPECT_EQ(slash_bits, 0xffffffff);
+
+  // 65 is OK if #component is less than 60 after path canonicalization.
   err = "";
-  path =
-      "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/x.h";
-  EXPECT_FALSE(CanonicalizePath(&path, &slash_bits, &err));
-  EXPECT_EQ(err, "too many path components");
+  path = "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./"
+         "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./x/y.h";
+  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  EXPECT_EQ(slash_bits, 0x0);
 
   // Backslashes version.
   err = "";
   path =
-      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\."
-      "\\a\\.\\a\\.\\a\\.\\a\\.\\a\\x.h";
-  EXPECT_FALSE(CanonicalizePath(&path, &slash_bits, &err));
-  EXPECT_EQ(err, "too many path components");
+      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\"
+      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\"
+      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\"
+      "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\x\\y.h";
+  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  EXPECT_EQ(slash_bits, 0x1ffffffff);
+
+
+  // 59 after canonicalization is OK.
+  err = "";
+  path = "a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/"
+         "a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/x/y.h";
+  EXPECT_EQ(58, std::count(path.begin(), path.end(), '/'));
+  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  EXPECT_EQ(slash_bits, 0x0);
+
+  // Backslashes version.
+  err = "";
+  path =
+      "a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\"
+      "a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\"
+      "a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\"
+      "a\\a\\a\\a\\a\\a\\a\\a\\a\\x\\y.h";
+  EXPECT_EQ(58, std::count(path.begin(), path.end(), '\\'));
+  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  EXPECT_EQ(slash_bits, 0x3ffffffffffffff);
 }
 #endif
 
@@ -326,7 +353,7 @@
   string path;
   string err;
   size_t len;
-  unsigned int unused;
+  uint64_t unused;
 
   path = "foo/. bar/.";
   len = strlen("foo/.");  // Canonicalize only the part before the space.
diff --git a/src/version.cc b/src/version.cc
index eafa082..ad2d09f 100644
--- a/src/version.cc
+++ b/src/version.cc
@@ -18,7 +18,7 @@
 
 #include "util.h"
 
-const char* kNinjaVersion = "1.7.2";
+const char* kNinjaVersion = "1.8.0";
 
 void ParseVersion(const string& version, int* major, int* minor) {
   size_t end = version.find('.');