diff --git a/.clang-tidy b/.clang-tidy
index df4c1ed..e0afd47 100644
--- a/.clang-tidy
+++ b/.clang-tidy
@@ -1,13 +1,17 @@
 ---
 Checks: '
   ,readability-avoid-const-params-in-decls,
+  ,readability-inconsistent-declaration-parameter-name,
   ,readability-non-const-parameter,
   ,readability-redundant-string-cstr,
   ,readability-redundant-string-init,
+  ,readability-simplify-boolean-expr,
 '
 WarningsAsErrors: '
   ,readability-avoid-const-params-in-decls,
+  ,readability-inconsistent-declaration-parameter-name,
   ,readability-non-const-parameter,
   ,readability-redundant-string-cstr,
   ,readability-redundant-string-init,
+  ,readability-simplify-boolean-expr,
 '
diff --git a/.github/workflows/linux.yml b/.github/workflows/linux.yml
index 9062d98..3c93e00 100644
--- a/.github/workflows/linux.yml
+++ b/.github/workflows/linux.yml
@@ -13,15 +13,18 @@
       image: centos:7
     steps:
     - uses: actions/checkout@v2
+    - uses: codespell-project/actions-codespell@master
+      with:
+        ignore_words_list: fo,wee
     - name: Install dependencies
       run: |
         curl -L -O https://github.com/Kitware/CMake/releases/download/v3.16.4/cmake-3.16.4-Linux-x86_64.sh
         chmod +x cmake-3.16.4-Linux-x86_64.sh
         ./cmake-3.16.4-Linux-x86_64.sh --skip-license --prefix=/usr/local
-        curl -L -O https://www.mirrorservice.org/sites/dl.fedoraproject.org/pub/epel/7/x86_64/Packages/p/p7zip-16.02-10.el7.x86_64.rpm
-        curl -L -O https://www.mirrorservice.org/sites/dl.fedoraproject.org/pub/epel/7/x86_64/Packages/p/p7zip-plugins-16.02-10.el7.x86_64.rpm
-        rpm -U --quiet p7zip-16.02-10.el7.x86_64.rpm
-        rpm -U --quiet p7zip-plugins-16.02-10.el7.x86_64.rpm
+        curl -L -O https://www.mirrorservice.org/sites/dl.fedoraproject.org/pub/epel/7/x86_64/Packages/p/p7zip-16.02-20.el7.x86_64.rpm
+        curl -L -O https://www.mirrorservice.org/sites/dl.fedoraproject.org/pub/epel/7/x86_64/Packages/p/p7zip-plugins-16.02-20.el7.x86_64.rpm
+        rpm -U --quiet p7zip-16.02-20.el7.x86_64.rpm
+        rpm -U --quiet p7zip-plugins-16.02-20.el7.x86_64.rpm
         yum install -y make gcc-c++ libasan clang-analyzer
 
     - name: Build debug ninja
@@ -123,3 +126,24 @@
     - name: clang-tidy
       run: /usr/lib/llvm-10/share/clang/run-clang-tidy.py -header-filter=src
       working-directory: build-clang
+
+  build-with-python:
+    runs-on: [ubuntu-latest]
+    container:
+      image: ${{ matrix.image }}
+    strategy:
+      matrix:
+        image: ['ubuntu:14.04', 'ubuntu:16.04', 'ubuntu:18.04']
+    steps:
+    - uses: actions/checkout@v2
+    - name: Install dependencies
+      run: |
+        apt update
+        apt install -y g++ python3
+    - name: ${{ matrix.image }}
+      run: |
+        python3 configure.py --bootstrap
+        ./ninja all
+        ./ninja_test --gtest_filter=-SubprocessTest.SetWithLots
+        python3 misc/ninja_syntax_test.py
+        ./misc/output_test.py
diff --git a/.github/workflows/macos.yml b/.github/workflows/macos.yml
index 4ea958f..0797433 100644
--- a/.github/workflows/macos.yml
+++ b/.github/workflows/macos.yml
@@ -21,12 +21,11 @@
       env:
         MACOSX_DEPLOYMENT_TARGET: 10.12
       run: |
-        sudo xcode-select -s /Applications/Xcode_12.2.app
         cmake -Bbuild -GXcode '-DCMAKE_OSX_ARCHITECTURES=arm64;x86_64'
         cmake --build build --config Release
 
     - name: Test ninja
-      run: ctest -vv
+      run: ctest -C Release -vv
       working-directory: build
 
     - name: Create ninja archive
diff --git a/.github/workflows/windows.yml b/.github/workflows/windows.yml
index 04fc2f6..e4fe7bd 100644
--- a/.github/workflows/windows.yml
+++ b/.github/workflows/windows.yml
@@ -19,10 +19,15 @@
     - name: Build ninja
       shell: bash
       run: |
-        cmake -DCMAKE_BUILD_TYPE=Release -B build
+        cmake -Bbuild
+        cmake --build build --parallel --config Debug
         cmake --build build --parallel --config Release
 
-    - name: Test ninja
+    - name: Test ninja (Debug)
+      run: .\ninja_test.exe
+      working-directory: build/Debug
+
+    - name: Test ninja (Release)
       run: .\ninja_test.exe
       working-directory: build/Release
 
diff --git a/.gitignore b/.gitignore
index dca1129..ca36ec8 100644
--- a/.gitignore
+++ b/.gitignore
@@ -38,3 +38,12 @@
 
 # Qt Creator project files
 /CMakeLists.txt.user
+
+# clangd
+/.clangd/
+/compile_commands.json
+/.cache/
+
+# Visual Studio files
+/.vs/
+/out/
diff --git a/.travis.yml b/.travis.yml
deleted file mode 100644
index e5d7d2b..0000000
--- a/.travis.yml
+++ /dev/null
@@ -1,36 +0,0 @@
-matrix:
-  include:
-    - os: linux
-      dist: precise
-      compiler: gcc
-    - os: linux
-      dist: precise
-      compiler: clang
-    - os: linux
-      dist: trusty
-      compiler: gcc
-    - os: linux
-      dist: trusty
-      compiler: clang
-    - os: linux
-      dist: xenial
-      compiler: gcc
-    - os: linux
-      dist: xenial
-      compiler: clang
-    - os: osx
-      osx_image: xcode10
-    - os: osx
-      osx_image: xcode10.1
-sudo: false
-language: cpp
-before_install:
-  - if [[ "$TRAVIS_OS_NAME" == "osx" ]]; then brew install re2c             ; fi
-  - if [[ "$TRAVIS_OS_NAME" == "windows" ]]; then choco install re2c python ; fi
-script:
-  - ./misc/ci.py
-  - python3 configure.py --bootstrap
-  - ./ninja all
-  - ./ninja_test --gtest_filter=-SubprocessTest.SetWithLots
-  - ./misc/ninja_syntax_test.py
-  - ./misc/output_test.py
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 7f03c35..70fc5e9 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1,6 +1,6 @@
 cmake_minimum_required(VERSION 3.15)
 
-include(CheckIncludeFileCXX)
+include(CheckSymbolExists)
 include(CheckIPOSupported)
 
 project(ninja)
@@ -18,16 +18,18 @@
 # --- compiler flags
 if(MSVC)
 	set(CMAKE_MSVC_RUNTIME_LIBRARY "MultiThreaded$<$<CONFIG:Debug>:Debug>")
-	string(APPEND CMAKE_CXX_FLAGS " /W4 /GR- /Zc:__cplusplus")
+	string(REPLACE "/GR" "" CMAKE_CXX_FLAGS ${CMAKE_CXX_FLAGS})
+	add_compile_options(/W4 /wd4100 /wd4267 /wd4706 /wd4702 /wd4244 /GR- /Zc:__cplusplus)
+	add_compile_definitions(_CRT_SECURE_NO_WARNINGS)
 else()
 	include(CheckCXXCompilerFlag)
 	check_cxx_compiler_flag(-Wno-deprecated flag_no_deprecated)
 	if(flag_no_deprecated)
-		string(APPEND CMAKE_CXX_FLAGS " -Wno-deprecated")
+		add_compile_options(-Wno-deprecated)
 	endif()
 	check_cxx_compiler_flag(-fdiagnostics-color flag_color_diag)
 	if(flag_color_diag)
-		string(APPEND CMAKE_CXX_FLAGS " -fdiagnostics-color")
+		add_compile_options(-fdiagnostics-color)
 	endif()
 endif()
 
@@ -37,7 +39,7 @@
 	# the depfile parser and ninja lexers are generated using re2c.
 	function(re2c IN OUT)
 		add_custom_command(DEPENDS ${IN} OUTPUT ${OUT}
-			COMMAND ${RE2C} -b -i --no-generation-date -o ${OUT} ${IN}
+			COMMAND ${RE2C} -b -i --no-generation-date --no-version -o ${OUT} ${IN}
 		)
 	endfunction()
 	re2c(${PROJECT_SOURCE_DIR}/src/depfile_parser.in.cc ${PROJECT_BINARY_DIR}/depfile_parser.cc)
@@ -53,9 +55,10 @@
 function(check_platform_supports_browse_mode RESULT)
 	# Make sure the inline.sh script works on this platform.
 	# It uses the shell commands such as 'od', which may not be available.
+
 	execute_process(
 		COMMAND sh -c "echo 'TEST' | src/inline.sh var"
-		WORKING_DIRECTORY ${CMAKE_SOURCE_DIR}
+		WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
 		RESULT_VARIABLE inline_result
 		OUTPUT_QUIET
 		ERROR_QUIET
@@ -63,12 +66,24 @@
 	if(NOT inline_result EQUAL "0")
 		# The inline script failed, so browse mode is not supported.
 		set(${RESULT} "0" PARENT_SCOPE)
+		if(NOT WIN32)
+			message(WARNING "browse feature omitted due to inline script failure")
+		endif()
 		return()
 	endif()
 
 	# Now check availability of the unistd header
-	check_include_file_cxx(unistd.h PLATFORM_HAS_UNISTD_HEADER)
-	set(${RESULT} "${PLATFORM_HAS_UNISTD_HEADER}" PARENT_SCOPE)
+	check_symbol_exists(fork "unistd.h" HAVE_FORK)
+	check_symbol_exists(pipe "unistd.h" HAVE_PIPE)
+	set(browse_supported 0)
+	if (HAVE_FORK AND HAVE_PIPE)
+		set(browse_supported 1)
+	endif ()
+	set(${RESULT} "${browse_supported}" PARENT_SCOPE)
+	if(NOT browse_supported)
+		message(WARNING "browse feature omitted due to missing `fork` and `pipe` functions")
+	endif()
+
 endfunction()
 
 check_platform_supports_browse_mode(platform_supports_ninja_browse)
@@ -88,11 +103,14 @@
 	src/eval_env.cc
 	src/graph.cc
 	src/graphviz.cc
+	src/json.cc
 	src/line_printer.cc
 	src/manifest_parser.cc
 	src/metrics.cc
+	src/missing_deps.cc
 	src/parser.cc
 	src/state.cc
+	src/status.cc
 	src/string_piece_util.cc
 	src/util.cc
 	src/version.cc
@@ -104,10 +122,8 @@
 		src/msvc_helper-win32.cc
 		src/msvc_helper_main-win32.cc
 		src/getopt.c
+		src/minidump-win32.cc
 	)
-	if(MSVC)
-		target_sources(libninja PRIVATE src/minidump-win32.cc)
-	endif()
 else()
 	target_sources(libninja PRIVATE src/subprocess-posix.cc)
 	if(CMAKE_SYSTEM_NAME STREQUAL "OS400" OR CMAKE_SYSTEM_NAME STREQUAL "AIX")
@@ -128,13 +144,17 @@
 # On IBM i (identified as "OS400" for compatibility reasons) and AIX, this fixes missing
 # PRId64 (and others) at compile time in C++ sources
 if(CMAKE_SYSTEM_NAME STREQUAL "OS400" OR CMAKE_SYSTEM_NAME STREQUAL "AIX")
-	string(APPEND CMAKE_CXX_FLAGS " -D__STDC_FORMAT_MACROS")
+	add_compile_definitions(__STDC_FORMAT_MACROS)
 endif()
 
 # Main executable is library plus main() function.
 add_executable(ninja src/ninja.cc)
 target_link_libraries(ninja PRIVATE libninja libninja-re2c)
 
+if(WIN32)
+  target_sources(ninja PRIVATE windows/ninja.manifest)
+endif()
+
 # Adds browse mode into the ninja binary if it's supported by the host platform.
 if(platform_supports_ninja_browse)
 	# Inlines src/browse.py into the browse_py.h header, so that it can be included
@@ -143,11 +163,11 @@
 		OUTPUT build/browse_py.h
 		MAIN_DEPENDENCY src/browse.py
 		DEPENDS src/inline.sh
-		COMMAND ${CMAKE_COMMAND} -E make_directory ${CMAKE_BINARY_DIR}/build
+		COMMAND ${CMAKE_COMMAND} -E make_directory ${PROJECT_BINARY_DIR}/build
 		COMMAND src/inline.sh kBrowsePy
 						< src/browse.py
-						> ${CMAKE_BINARY_DIR}/build/browse_py.h
-		WORKING_DIRECTORY ${CMAKE_SOURCE_DIR}
+						> ${PROJECT_BINARY_DIR}/build/browse_py.h
+		WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
 		VERBATIM
 	)
 
@@ -155,8 +175,8 @@
 	target_sources(ninja PRIVATE src/browse.cc)
 	set_source_files_properties(src/browse.cc
 		PROPERTIES
-			OBJECT_DEPENDS "${CMAKE_BINARY_DIR}/build/browse_py.h"
-			INCLUDE_DIRECTORIES "${CMAKE_BINARY_DIR}"
+			OBJECT_DEPENDS "${PROJECT_BINARY_DIR}/build/browse_py.h"
+			INCLUDE_DIRECTORIES "${PROJECT_BINARY_DIR}"
 			COMPILE_DEFINITIONS NINJA_PYTHON="python"
 	)
 endif()
@@ -175,8 +195,10 @@
     src/dyndep_parser_test.cc
     src/edit_distance_test.cc
     src/graph_test.cc
+    src/json_test.cc
     src/lexer_test.cc
     src/manifest_parser_test.cc
+    src/missing_deps_test.cc
     src/ninja_test.cc
     src/state_test.cc
     src/string_piece_util_test.cc
@@ -203,11 +225,11 @@
 
   if(CMAKE_SYSTEM_NAME STREQUAL "AIX" AND CMAKE_SIZEOF_VOID_P EQUAL 4)
     # These tests require more memory than will fit in the standard AIX shared stack/heap (256M)
-    target_link_libraries(hash_collision_bench PRIVATE "-Wl,-bmaxdata:0x80000000")
-    target_link_libraries(manifest_parser_perftest PRIVATE "-Wl,-bmaxdata:0x80000000")
+    target_link_options(hash_collision_bench PRIVATE "-Wl,-bmaxdata:0x80000000")
+    target_link_options(manifest_parser_perftest PRIVATE "-Wl,-bmaxdata:0x80000000")
   endif()
 
-  add_test(NinjaTest ninja_test)
+  add_test(NAME NinjaTest COMMAND ninja_test)
 endif()
 
-install(TARGETS ninja DESTINATION bin)
+install(TARGETS ninja)
diff --git a/README.md b/README.md
index d11fd33..d763766 100644
--- a/README.md
+++ b/README.md
@@ -37,7 +37,7 @@
 ### CMake
 
 ```
-cmake -Bbuild-cmake -H.
+cmake -Bbuild-cmake
 cmake --build build-cmake
 ```
 
diff --git a/configure.py b/configure.py
index cded265..4390434 100755
--- a/configure.py
+++ b/configure.py
@@ -84,7 +84,7 @@
         return self._platform == 'msvc'
 
     def msvc_needs_fs(self):
-        popen = subprocess.Popen(['cl', '/nologo', '/?'],
+        popen = subprocess.Popen(['cl', '/nologo', '/help'],
                                  stdout=subprocess.PIPE,
                                  stderr=subprocess.PIPE)
         out, err = popen.communicate()
@@ -479,7 +479,7 @@
         return False
 if has_re2c():
     n.rule('re2c',
-           command='re2c -b -i --no-generation-date -o $out $in',
+           command='re2c -b -i --no-generation-date --no-version -o $out $in',
            description='RE2C $out')
     # Generate the .cc files in the source directory so we can check them in.
     n.build(src('depfile_parser.cc'), 're2c', src('depfile_parser.in.cc'))
@@ -507,12 +507,15 @@
              'eval_env',
              'graph',
              'graphviz',
+             'json',
              'lexer',
              'line_printer',
              'manifest_parser',
              'metrics',
+             'missing_deps',
              'parser',
              'state',
+             'status',
              'string_piece_util',
              'util',
              'version']:
@@ -575,10 +578,13 @@
              'disk_interface_test',
              'edit_distance_test',
              'graph_test',
+             'json_test',
              'lexer_test',
              'manifest_parser_test',
+             'missing_deps_test',
              'ninja_test',
              'state_test',
+             'status_test',
              'string_piece_util_test',
              'subprocess_test',
              'test',
diff --git a/doc/manual.asciidoc b/doc/manual.asciidoc
index 388410f..a78bbf5 100644
--- a/doc/manual.asciidoc
+++ b/doc/manual.asciidoc
@@ -1,6 +1,6 @@
 The Ninja build system
 ======================
-v1.10.2, Nov 2020
+v1.11.0, Nov 2020
 
 
 Introduction
@@ -258,6 +258,10 @@
 executed in order, may be used to rebuild those targets, assuming that all
 output files are out of date.
 
+`inputs`:: given a list of targets, print a list of all inputs used to
+rebuild those targets.
+_Available since Ninja 1.11._
+
 `clean`:: remove built files. By default it removes all built files
 except for those created by the generator.  Adding the `-g` flag also
 removes built files created by the generator (see <<ref_rule,the rule
@@ -285,14 +289,76 @@
 `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._
 
+`missingdeps`:: given a list of targets, look for targets that depend on
+a generated file, but do not have a properly (possibly transitive) dependency
+on the generator.  Such targets may cause build flakiness on clean builds.
++
+The broken targets can be found assuming deps log / depfile dependency
+information is correct.  Any target that depends on a generated file (output
+of a generator-target) implicitly, but does not have an explicit or order-only
+dependency path to the generator-target, is considered broken.
++
+The tool's findings can be verified by trying to build the listed targets in
+a clean outdir without building any other targets.  The build should fail for
+each of them with a missing include error or equivalent pointing to the
+generated file.
+_Available since Ninja 1.11._
+
 `recompact`:: recompact the `.ninja_deps` file. _Available since Ninja 1.4._
 
 `restat`:: updates all recorded file modification timestamps in the `.ninja_log`
 file. _Available since Ninja 1.10._
 
-`rules`:: output the list of all rules (eventually with their description
-if they have one).  It can be used to know which rule name to pass to
-+ninja -t targets rule _name_+ or +ninja -t compdb+.
+`rules`:: output the list of all rules. It can be used to know which rule name
+to pass to +ninja -t targets rule _name_+ or +ninja -t compdb+. Adding the `-d`
+flag also prints the description of the rules.
+
+`msvc`:: Available on Windows hosts only.
+Helper tool to invoke the `cl.exe` compiler with a pre-defined set of
+environment variables, as in:
++
+----
+ninja -t msvc -e ENVFILE -- cl.exe <arguments>
+----
++
+Where `ENVFILE` is a binary file that contains an environment block suitable
+for CreateProcessA() on Windows (i.e. a series of zero-terminated strings that
+look like NAME=VALUE, followed by an extra zero terminator). Note that this uses
+the local codepage encoding.
+
+This tool also supports a deprecated way of parsing the compiler's output when
+the `/showIncludes` flag is used, and generating a GCC-compatible depfile from it.
++
+---
+ninja -t msvc -o DEPFILE [-p STRING] -- cl.exe /showIncludes <arguments>
+---
++
+
+When using this option, `-p STRING` can be used to pass the localized line prefix
+that `cl.exe` uses to output dependency information. For English-speaking regions
+this is `"Note: including file: "` without the double quotes, but will be different
+for other regions.
+
+Note that Ninja supports this natively now, with the use of `deps = msvc` and
+`msvc_deps_prefix` in Ninja files. Native support also avoids launching an extra
+tool process each time the compiler must be called, which can speed up builds
+noticeably on Windows.
+
+`wincodepage`:: Available on Windows hosts (_since Ninja 1.11_).
+Prints the Windows code page whose encoding is expected in the build file.
+The output has the form:
++
+----
+Build file encoding: <codepage>
+----
++
+Additional lines may be added in future versions of Ninja.
++
+The `<codepage>` is one of:
+
+`UTF-8`::: Encode as UTF-8.
+
+`ANSI`::: Encode to the system-wide ANSI code page.
 
 Writing your own Ninja files
 ----------------------------
@@ -453,6 +519,11 @@
 printed when run, logged (see below), nor do they contribute to the
 command count printed as part of the build process.
 
+When a `phony` target is used as an input to another build rule, the
+other build rule will, semantically, consider the inputs of the
+`phony` rule as its own. Therefore, `phony` rules can be used to group
+inputs, e.g. header files.
+
 `phony` can also be used to create dummy targets for files which
 may not exist at build time.  If a phony build statement is written
 without any dependencies, the target will be considered out of date if
@@ -713,6 +784,8 @@
    Order-only dependencies may be tacked on the end with +||
    _dependency1_ _dependency2_+.  (See <<ref_dependencies,the reference on
    dependency types>>.)
+   Validations may be taked on the end with +|@ _validation1_ _validation2_+.
+   (See <<validations,the reference on validations>>.)
 +
 Implicit outputs _(available since Ninja 1.7)_ may be added before
 the `:` with +| _output1_ _output2_+ and do not appear in `$out`.
@@ -950,8 +1023,9 @@
 +
 This is for expressing dependencies that don't show up on the
 command line of the command; for example, for a rule that runs a
-script, the script itself should be an implicit dependency, as
-changes to the script should cause the output to rebuild.
+script that reads a hardcoded file, the hardcoded file should
+be an implicit dependency, as changes to the file should cause
+the output to rebuild, even though it doesn't show up in the arguments.
 +
 Note that dependencies as loaded through depfiles have slightly different
 semantics, as described in the <<ref_rule,rule reference>>.
@@ -970,6 +1044,31 @@
 File paths are compared as is, which means that an absolute path and a
 relative path, pointing to the same file, are considered different by Ninja.
 
+[[validations]]
+Validations
+~~~~~~~~~~~
+Validations listed on the build line cause the specified files to be
+added to the top level of the build graph (as if they were specified
+on the Ninja command line) whenever the build line is a transitive
+dependency of one of the targets specified on the command line or a
+default target.
+
+Validations are added to the build graph regardless of whether the output
+files of the build statement are dirty are not, and the dirty state of
+the build statement that outputs the file being used as a validation
+has no effect on the dirty state of the build statement that requested it.
+
+A build edge can list another build edge as a validation even if the second
+edge depends on the first.
+
+Validations are designed to handle rules that perform error checking but
+don't produce any artifacts needed by the build, for example static
+analysis tools.  Marking the static analysis rule as an implicit input
+of the main build rule of the source files or of the rules that depend
+on the main build rule would slow down the critical path of the build,
+but using a validation would allow the build to proceed in parallel with
+the static analysis rule once the main build rule is complete.
+
 Variable expansion
 ~~~~~~~~~~~~~~~~~~
 
diff --git a/misc/manifest_fuzzer.cc b/misc/manifest_fuzzer.cc
new file mode 100644
index 0000000..0e1261a
--- /dev/null
+++ b/misc/manifest_fuzzer.cc
@@ -0,0 +1,41 @@
+// Copyright 2020 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 "stdint.h"
+#include <string>
+#include "disk_interface.h"
+#include "state.h"
+#include "manifest_parser.h"
+#include <filesystem>
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
+{
+	char build_file[256];
+	sprintf(build_file, "/tmp/build.ninja");
+	FILE *fp = fopen(build_file, "wb");
+	if (!fp)
+		return 0;
+	fwrite(data, size, 1, fp);
+	fclose(fp);	
+	
+	std::string err;
+	RealDiskInterface disk_interface;
+	State state;
+	ManifestParser parser(&state, &disk_interface);
+	
+	parser.Load("/tmp/build.ninja", &err);
+	
+	std::__fs::filesystem::remove_all("/tmp/build.ninja");
+	return 0;
+}
diff --git a/misc/ninja_syntax.py b/misc/ninja_syntax.py
index ab5c0d4..ca73b5b 100644
--- a/misc/ninja_syntax.py
+++ b/misc/ninja_syntax.py
@@ -74,7 +74,7 @@
             self.variable('deps', deps, indent=1)
 
     def build(self, outputs, rule, inputs=None, implicit=None, order_only=None,
-              variables=None, implicit_outputs=None, pool=None):
+              variables=None, implicit_outputs=None, pool=None, dyndep=None):
         outputs = as_list(outputs)
         out_outputs = [escape_path(x) for x in outputs]
         all_inputs = [escape_path(x) for x in as_list(inputs)]
@@ -97,6 +97,8 @@
                                      ' '.join([rule] + all_inputs)))
         if pool is not None:
             self._line('  pool = %s' % pool)
+        if dyndep is not None:
+            self._line('  dyndep = %s' % dyndep)
 
         if variables:
             if isinstance(variables, dict):
diff --git a/misc/oss-fuzz/build.sh b/misc/oss-fuzz/build.sh
new file mode 100644
index 0000000..4328feb
--- /dev/null
+++ b/misc/oss-fuzz/build.sh
@@ -0,0 +1,29 @@
+#!/bin/bash -eu
+# Copyright 2020 Google Inc.
+#
+# 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.
+#
+################################################################################
+
+cmake -Bbuild-cmake -H.
+cmake --build build-cmake
+
+cd $SRC/ninja/misc
+
+$CXX $CXXFLAGS -fdiagnostics-color -I/src/ninja/src -o fuzzer.o -c manifest_fuzzer.cc
+
+find .. -name "*.o" -exec ar rcs fuzz_lib.a {} \;
+
+$CXX $CXXFLAGS $LIB_FUZZING_ENGINE fuzzer.o -o $OUT/fuzzer fuzz_lib.a
+
+zip $OUT/fuzzer_seed_corpus.zip $SRC/sample_ninja_build
diff --git a/misc/oss-fuzz/sample_ninja_build b/misc/oss-fuzz/sample_ninja_build
new file mode 100644
index 0000000..7b513be
--- /dev/null
+++ b/misc/oss-fuzz/sample_ninja_build
@@ -0,0 +1,14 @@
+# build.ninja
+cc     = clang
+cflags = -Weverything
+
+rule compile
+  command = $cc $cflags -c $in -o $out
+
+rule link
+  command = $cc $in -o $out
+
+build hello.o: compile hello.c
+build hello: link hello.o
+
+default hello
diff --git a/misc/output_test.py b/misc/output_test.py
index b63520f..141716c 100755
--- a/misc/output_test.py
+++ b/misc/output_test.py
@@ -48,6 +48,15 @@
 
 @unittest.skipIf(platform.system() == 'Windows', 'These test methods do not work on Windows')
 class Output(unittest.TestCase):
+    BUILD_SIMPLE_ECHO = '\n'.join((
+        'rule echo',
+        '  command = printf "do thing"',
+        '  description = echo $out',
+        '',
+        'build a: echo',
+        '',
+    ))
+
     def test_issue_1418(self):
         self.assertEqual(run(
 '''rule echo
@@ -110,6 +119,38 @@
 
     def test_status(self):
         self.assertEqual(run(''), 'ninja: no work to do.\n')
+        self.assertEqual(run('', pipe=True), 'ninja: no work to do.\n')
+
+    def test_ninja_status_default(self):
+        'Do we show the default status by default?'
+        self.assertEqual(run(Output.BUILD_SIMPLE_ECHO), '[1/1] echo a\x1b[K\ndo thing\n')
+
+    def test_ninja_status_quiet(self):
+        'Do we suppress the status information when --quiet is specified?'
+        output = run(Output.BUILD_SIMPLE_ECHO, flags='--quiet')
+        self.assertEqual(output, 'do thing\n')
+
+    def test_entering_directory_on_stdout(self):
+        output = run(Output.BUILD_SIMPLE_ECHO, flags='-C$PWD', pipe=True)
+        self.assertEqual(output.splitlines()[0][:25], "ninja: Entering directory")
+
+    def test_tool_inputs(self):
+        plan = '''
+rule cat
+  command = cat $in $out
+build out1 : cat in1
+build out2 : cat in2 out1
+build out3 : cat out2 out1 | implicit || order_only
+'''
+        self.assertEqual(run(plan, flags='-t inputs out3'),
+'''implicit
+in1
+in2
+order_only
+out1
+out2
+''')
+
 
 if __name__ == '__main__':
     unittest.main()
diff --git a/misc/write_fake_manifests.py b/misc/write_fake_manifests.py
index b3594de..abcb677 100644
--- a/misc/write_fake_manifests.py
+++ b/misc/write_fake_manifests.py
@@ -65,7 +65,7 @@
     def _n_unique_strings(self, n):
         seen = set([None])
         return [self._unique_string(seen, avg_options=3, p_suffix=0.4)
-                for _ in xrange(n)]
+                for _ in range(n)]
 
     def target_name(self):
         return self._unique_string(p_suffix=0, seen=self.seen_names)
@@ -73,7 +73,7 @@
     def path(self):
         return os.path.sep.join([
             self._unique_string(self.seen_names, avg_options=1, p_suffix=0)
-            for _ in xrange(1 + paretoint(0.6, alpha=4))])
+            for _ in range(1 + paretoint(0.6, alpha=4))])
 
     def src_obj_pairs(self, path, name):
         num_sources = paretoint(55, alpha=2) + 1
@@ -84,7 +84,7 @@
     def defines(self):
         return [
             '-DENABLE_' + self._unique_string(self.seen_defines).upper()
-            for _ in xrange(paretoint(20, alpha=3))]
+            for _ in range(paretoint(20, alpha=3))]
 
 
 LIB, EXE = 0, 1
@@ -227,7 +227,7 @@
     gen = GenRandom(src_dir)
 
     # N-1 static libraries, and 1 executable depending on all of them.
-    targets = [Target(gen, LIB) for i in xrange(num_targets - 1)]
+    targets = [Target(gen, LIB) for i in range(num_targets - 1)]
     for i in range(len(targets)):
         targets[i].deps = [t for t in targets[0:i] if random.random() < 0.05]
 
diff --git a/src/build.cc b/src/build.cc
index 2fb2aa4..6f11ed7 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -20,11 +20,6 @@
 #include <stdlib.h>
 #include <functional>
 
-#ifdef _WIN32
-#include <fcntl.h>
-#include <io.h>
-#endif
-
 #if defined(__SVR4) && defined(__sun)
 #include <sys/termios.h>
 #endif
@@ -36,7 +31,9 @@
 #include "deps_log.h"
 #include "disk_interface.h"
 #include "graph.h"
+#include "metrics.h"
 #include "state.h"
+#include "status.h"
 #include "subprocess.h"
 #include "util.h"
 
@@ -78,233 +75,6 @@
 
 }  // namespace
 
-BuildStatus::BuildStatus(const BuildConfig& config)
-    : config_(config), start_time_millis_(GetTimeMillis()), started_edges_(0),
-      finished_edges_(0), total_edges_(0), progress_status_format_(NULL),
-      current_rate_(config.parallelism) {
-  // Don't do anything fancy in verbose mode.
-  if (config_.verbosity != BuildConfig::NORMAL)
-    printer_.set_smart_terminal(false);
-
-  progress_status_format_ = getenv("NINJA_STATUS");
-  if (!progress_status_format_)
-    progress_status_format_ = "[%f/%t] ";
-}
-
-void BuildStatus::PlanHasTotalEdges(int total) {
-  total_edges_ = total;
-}
-
-void BuildStatus::BuildEdgeStarted(const Edge* edge) {
-  assert(running_edges_.find(edge) == running_edges_.end());
-  int start_time = (int)(GetTimeMillis() - start_time_millis_);
-  running_edges_.insert(make_pair(edge, start_time));
-  ++started_edges_;
-
-  if (edge->use_console() || printer_.is_smart_terminal())
-    PrintStatus(edge, kEdgeStarted);
-
-  if (edge->use_console())
-    printer_.SetConsoleLocked(true);
-}
-
-void BuildStatus::BuildEdgeFinished(Edge* edge,
-                                    bool success,
-                                    const string& output,
-                                    int* start_time,
-                                    int* end_time) {
-  int64_t now = GetTimeMillis();
-
-  ++finished_edges_;
-
-  RunningEdgeMap::iterator i = running_edges_.find(edge);
-  *start_time = i->second;
-  *end_time = (int)(now - start_time_millis_);
-  running_edges_.erase(i);
-
-  if (edge->use_console())
-    printer_.SetConsoleLocked(false);
-
-  if (config_.verbosity == BuildConfig::QUIET)
-    return;
-
-  if (!edge->use_console())
-    PrintStatus(edge, kEdgeFinished);
-
-  // Print the command that is spewing before printing its output.
-  if (!success) {
-    string outputs;
-    for (vector<Node*>::const_iterator o = edge->outputs_.begin();
-         o != edge->outputs_.end(); ++o)
-      outputs += (*o)->path() + " ";
-
-    if (printer_.supports_color()) {
-        printer_.PrintOnNewLine("\x1B[31m" "FAILED: " "\x1B[0m" + outputs + "\n");
-    } else {
-        printer_.PrintOnNewLine("FAILED: " + outputs + "\n");
-    }
-    printer_.PrintOnNewLine(edge->EvaluateCommand() + "\n");
-  }
-
-  if (!output.empty()) {
-    // ninja sets stdout and stderr of subprocesses to a pipe, to be able to
-    // check if the output is empty. Some compilers, e.g. clang, check
-    // isatty(stderr) to decide if they should print colored output.
-    // To make it possible to use colored output with ninja, subprocesses should
-    // be run with a flag that forces them to always print color escape codes.
-    // To make sure these escape codes don't show up in a file if ninja's output
-    // is piped to a file, ninja strips ansi escape codes again if it's not
-    // writing to a |smart_terminal_|.
-    // (Launching subprocesses in pseudo ttys doesn't work because there are
-    // only a few hundred available on some systems, and ninja can launch
-    // thousands of parallel compile commands.)
-    string final_output;
-    if (!printer_.supports_color())
-      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
-  }
-}
-
-void BuildStatus::BuildLoadDyndeps() {
-  // The DependencyScan calls EXPLAIN() to print lines explaining why
-  // it considers a portion of the graph to be out of date.  Normally
-  // this is done before the build starts, but our caller is about to
-  // load a dyndep file during the build.  Doing so may generate more
-  // explanation lines (via fprintf directly to stderr), but in an
-  // interactive console the cursor is currently at the end of a status
-  // line.  Start a new line so that the first explanation does not
-  // append to the status line.  After the explanations are done a
-  // new build status line will appear.
-  if (g_explaining)
-    printer_.PrintOnNewLine("");
-}
-
-void BuildStatus::BuildStarted() {
-  overall_rate_.Restart();
-  current_rate_.Restart();
-}
-
-void BuildStatus::BuildFinished() {
-  printer_.SetConsoleLocked(false);
-  printer_.PrintOnNewLine("");
-}
-
-string BuildStatus::FormatProgressStatus(
-    const char* progress_status_format, EdgeStatus status) const {
-  string out;
-  char buf[32];
-  int percent;
-  for (const char* s = progress_status_format; *s != '\0'; ++s) {
-    if (*s == '%') {
-      ++s;
-      switch (*s) {
-      case '%':
-        out.push_back('%');
-        break;
-
-        // Started edges.
-      case 's':
-        snprintf(buf, sizeof(buf), "%d", started_edges_);
-        out += buf;
-        break;
-
-        // Total edges.
-      case 't':
-        snprintf(buf, sizeof(buf), "%d", total_edges_);
-        out += buf;
-        break;
-
-        // Running edges.
-      case 'r': {
-        int running_edges = started_edges_ - finished_edges_;
-        // count the edge that just finished as a running edge
-        if (status == kEdgeFinished)
-          running_edges++;
-        snprintf(buf, sizeof(buf), "%d", running_edges);
-        out += buf;
-        break;
-      }
-
-        // Unstarted edges.
-      case 'u':
-        snprintf(buf, sizeof(buf), "%d", total_edges_ - started_edges_);
-        out += buf;
-        break;
-
-        // Finished edges.
-      case 'f':
-        snprintf(buf, sizeof(buf), "%d", finished_edges_);
-        out += buf;
-        break;
-
-        // Overall finished edges per second.
-      case 'o':
-        overall_rate_.UpdateRate(finished_edges_);
-        SnprintfRate(overall_rate_.rate(), buf, "%.1f");
-        out += buf;
-        break;
-
-        // Current rate, average over the last '-j' jobs.
-      case 'c':
-        current_rate_.UpdateRate(finished_edges_);
-        SnprintfRate(current_rate_.rate(), buf, "%.1f");
-        out += buf;
-        break;
-
-        // Percentage
-      case 'p':
-        percent = (100 * finished_edges_) / total_edges_;
-        snprintf(buf, sizeof(buf), "%3i%%", percent);
-        out += buf;
-        break;
-
-      case 'e': {
-        double elapsed = overall_rate_.Elapsed();
-        snprintf(buf, sizeof(buf), "%.3f", elapsed);
-        out += buf;
-        break;
-      }
-
-      default:
-        Fatal("unknown placeholder '%%%c' in $NINJA_STATUS", *s);
-        return "";
-      }
-    } else {
-      out.push_back(*s);
-    }
-  }
-
-  return out;
-}
-
-void BuildStatus::PrintStatus(const Edge* edge, EdgeStatus status) {
-  if (config_.verbosity == BuildConfig::QUIET)
-    return;
-
-  bool force_full_command = config_.verbosity == BuildConfig::VERBOSE;
-
-  string to_print = edge->GetBinding("description");
-  if (to_print.empty() || force_full_command)
-    to_print = edge->GetBinding("command");
-
-  to_print = FormatProgressStatus(progress_status_format_, status) + to_print;
-
-  printer_.Print(to_print,
-                 force_full_command ? LinePrinter::FULL : LinePrinter::ELIDE);
-}
-
 Plan::Plan(Builder* builder)
   : builder_(builder)
   , command_edges_(0)
@@ -318,8 +88,8 @@
   want_.clear();
 }
 
-bool Plan::AddTarget(const Node* node, string* err) {
-  return AddSubTarget(node, NULL, err, NULL);
+bool Plan::AddTarget(const Node* target, string* err) {
+  return AddSubTarget(target, NULL, err, NULL);
 }
 
 bool Plan::AddSubTarget(const Node* node, const Node* dependent, string* err,
@@ -381,7 +151,7 @@
 Edge* Plan::FindWork() {
   if (ready_.empty())
     return NULL;
-  set<Edge*>::iterator e = ready_.begin();
+  EdgeSet::iterator e = ready_.begin();
   Edge* edge = *e;
   ready_.erase(e);
   return edge;
@@ -614,8 +384,21 @@
     Node* n = *i;
 
     // Check if this dependent node is now dirty.  Also checks for new cycles.
-    if (!scan->RecomputeDirty(n, err))
+    std::vector<Node*> validation_nodes;
+    if (!scan->RecomputeDirty(n, &validation_nodes, err))
       return false;
+
+    // Add any validation nodes found during RecomputeDirty as new top level
+    // targets.
+    for (std::vector<Node*>::iterator v = validation_nodes.begin();
+         v != validation_nodes.end(); ++v) {
+      if (Edge* in_edge = (*v)->in_edge()) {
+        if (!in_edge->outputs_ready() &&
+            !AddTarget(*v, err)) {
+          return false;
+        }
+      }
+    }
     if (!n->dirty())
       continue;
 
@@ -729,12 +512,12 @@
 
 Builder::Builder(State* state, const BuildConfig& config,
                  BuildLog* build_log, DepsLog* deps_log,
-                 DiskInterface* disk_interface)
-    : state_(state), config_(config),
-      plan_(this), disk_interface_(disk_interface),
+                 DiskInterface* disk_interface, Status *status,
+                 int64_t start_time_millis)
+    : state_(state), config_(config), plan_(this), status_(status),
+      start_time_millis_(start_time_millis), disk_interface_(disk_interface),
       scan_(state, build_log, deps_log, disk_interface,
             &config_.depfile_parser_options) {
-  status_ = new BuildStatus(config);
 }
 
 Builder::~Builder() {
@@ -761,7 +544,7 @@
         string err;
         TimeStamp new_mtime = disk_interface_->Stat((*o)->path(), &err);
         if (new_mtime == -1)  // Log and ignore Stat() errors.
-          Error("%s", err.c_str());
+          status_->Error("%s", err.c_str());
         if (!depfile.empty() || (*o)->mtime() != new_mtime)
           disk_interface_->RemoveFile((*o)->path());
       }
@@ -782,17 +565,29 @@
   return node;
 }
 
-bool Builder::AddTarget(Node* node, string* err) {
-  if (!scan_.RecomputeDirty(node, err))
+bool Builder::AddTarget(Node* target, string* err) {
+  std::vector<Node*> validation_nodes;
+  if (!scan_.RecomputeDirty(target, &validation_nodes, err))
     return false;
 
-  if (Edge* in_edge = node->in_edge()) {
-    if (in_edge->outputs_ready())
-      return true;  // Nothing to do.
+  Edge* in_edge = target->in_edge();
+  if (!in_edge || !in_edge->outputs_ready()) {
+    if (!plan_.AddTarget(target, err)) {
+      return false;
+    }
   }
 
-  if (!plan_.AddTarget(node, err))
-    return false;
+  // Also add any validation nodes found during RecomputeDirty as top level
+  // targets.
+  for (std::vector<Node*>::iterator n = validation_nodes.begin();
+       n != validation_nodes.end(); ++n) {
+    if (Edge* validation_in_edge = (*n)->in_edge()) {
+      if (!validation_in_edge->outputs_ready() &&
+          !plan_.AddTarget(*n, err)) {
+        return false;
+      }
+    }
+  }
 
   return true;
 }
@@ -904,7 +699,10 @@
   if (edge->is_phony())
     return true;
 
-  status_->BuildEdgeStarted(edge);
+  int64_t start_time_millis = GetTimeMillis() - start_time_millis_;
+  running_edges_.insert(make_pair(edge, start_time_millis));
+
+  status_->BuildEdgeStarted(edge, start_time_millis);
 
   // Create directories necessary for outputs.
   // XXX: this will block; do we care?
@@ -957,9 +755,14 @@
     }
   }
 
-  int start_time, end_time;
-  status_->BuildEdgeFinished(edge, result->success(), result->output,
-                             &start_time, &end_time);
+  int64_t start_time_millis, end_time_millis;
+  RunningEdgeMap::iterator it = running_edges_.find(edge);
+  start_time_millis = it->second;
+  end_time_millis = GetTimeMillis() - start_time_millis_;
+  running_edges_.erase(it);
+
+  status_->BuildEdgeFinished(edge, end_time_millis, result->success(),
+                             result->output);
 
   // The rest of this function only applies to successful commands.
   if (!result->success()) {
@@ -1028,8 +831,8 @@
     disk_interface_->RemoveFile(rspfile);
 
   if (scan_.build_log()) {
-    if (!scan_.build_log()->RecordCommand(edge, start_time, end_time,
-                                          output_mtime)) {
+    if (!scan_.build_log()->RecordCommand(edge, start_time_millis,
+                                          end_time_millis, output_mtime)) {
       *err = string("Error writing to build log: ") + strerror(errno);
       return false;
     }
@@ -1100,9 +903,7 @@
     for (vector<StringPiece>::iterator i = deps.ins_.begin();
          i != deps.ins_.end(); ++i) {
       uint64_t slash_bits;
-      if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits,
-                            err))
-        return false;
+      CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits);
       deps_nodes->push_back(state_->GetNode(*i, slash_bits));
     }
 
diff --git a/src/build.h b/src/build.h
index 2798693..d697dfb 100644
--- a/src/build.h
+++ b/src/build.h
@@ -19,24 +19,21 @@
 #include <map>
 #include <memory>
 #include <queue>
-#include <set>
 #include <string>
 #include <vector>
 
 #include "depfile_parser.h"
 #include "graph.h"  // XXX needed for DependencyScan; should rearrange.
 #include "exit_status.h"
-#include "line_printer.h"
-#include "metrics.h"
 #include "util.h"  // int64_t
 
 struct BuildLog;
-struct BuildStatus;
 struct Builder;
 struct DiskInterface;
 struct Edge;
 struct Node;
 struct State;
+struct Status;
 
 /// Plan stores the state of a build plan: what we intend to build,
 /// which steps we're ready to execute.
@@ -46,7 +43,7 @@
   /// Add a target to our plan (including all its dependencies).
   /// Returns false if we don't need to build this target; may
   /// fill in |err| with an error message if there's a problem.
-  bool AddTarget(const Node* node, std::string* err);
+  bool AddTarget(const Node* target, std::string* err);
 
   // Pop a ready edge off the queue of edges to build.
   // Returns NULL if there's no work to do.
@@ -122,7 +119,7 @@
   /// we want for the edge.
   std::map<Edge*, Want> want_;
 
-  std::set<Edge*> ready_;
+  EdgeSet ready_;
 
   Builder* builder_;
 
@@ -162,8 +159,9 @@
                   failures_allowed(1), max_load_average(-0.0f) {}
 
   enum Verbosity {
-    NORMAL,
     QUIET,  // No output -- used when testing.
+    NO_STATUS_UPDATE,  // just regular output but suppress status update
+    NORMAL,  // regular output and status update
     VERBOSE
   };
   Verbosity verbosity;
@@ -180,7 +178,8 @@
 struct Builder {
   Builder(State* state, const BuildConfig& config,
           BuildLog* build_log, DepsLog* deps_log,
-          DiskInterface* disk_interface);
+          DiskInterface* disk_interface, Status* status,
+          int64_t start_time_millis);
   ~Builder();
 
   /// Clean up after interrupted commands by deleting output files.
@@ -221,13 +220,20 @@
 #else
   std::unique_ptr<CommandRunner> command_runner_;  // auto_ptr was removed in C++17.
 #endif
-  BuildStatus* status_;
+  Status* status_;
 
  private:
   bool ExtractDeps(CommandRunner::Result* result, const std::string& deps_type,
                    const std::string& deps_prefix,
                    std::vector<Node*>* deps_nodes, std::string* err);
 
+  /// Map of running edge to time the edge started running.
+  typedef std::map<const Edge*, int> RunningEdgeMap;
+  RunningEdgeMap running_edges_;
+
+  /// Time the build started.
+  int64_t start_time_millis_;
+
   DiskInterface* disk_interface_;
   DependencyScan scan_;
 
@@ -236,103 +242,4 @@
   void operator=(const Builder &other); // DO NOT IMPLEMENT
 };
 
-/// Tracks the status of a build: completion fraction, printing updates.
-struct BuildStatus {
-  explicit BuildStatus(const BuildConfig& config);
-  void PlanHasTotalEdges(int total);
-  void BuildEdgeStarted(const Edge* edge);
-  void BuildEdgeFinished(Edge* edge, bool success, const std::string& output,
-                         int* start_time, int* end_time);
-  void BuildLoadDyndeps();
-  void BuildStarted();
-  void BuildFinished();
-
-  enum EdgeStatus {
-    kEdgeStarted,
-    kEdgeFinished,
-  };
-
-  /// Format the progress status string by replacing the placeholders.
-  /// See the user manual for more information about the available
-  /// placeholders.
-  /// @param progress_status_format The format of the progress status.
-  /// @param status The status of the edge.
-  std::string FormatProgressStatus(const char* progress_status_format,
-                                   EdgeStatus status) const;
-
- private:
-  void PrintStatus(const Edge* edge, EdgeStatus status);
-
-  const BuildConfig& config_;
-
-  /// Time the build started.
-  int64_t start_time_millis_;
-
-  int started_edges_, finished_edges_, total_edges_;
-
-  /// Map of running edge to time the edge started running.
-  typedef std::map<const Edge*, int> RunningEdgeMap;
-  RunningEdgeMap running_edges_;
-
-  /// Prints progress output.
-  LinePrinter printer_;
-
-  /// The custom progress status format to use.
-  const char* progress_status_format_;
-
-  template<size_t S>
-  void SnprintfRate(double rate, char(&buf)[S], const char* format) const {
-    if (rate == -1)
-      snprintf(buf, S, "?");
-    else
-      snprintf(buf, S, format, rate);
-  }
-
-  struct RateInfo {
-    RateInfo() : rate_(-1) {}
-
-    void Restart() { stopwatch_.Restart(); }
-    double Elapsed() const { return stopwatch_.Elapsed(); }
-    double rate() { return rate_; }
-
-    void UpdateRate(int edges) {
-      if (edges && stopwatch_.Elapsed())
-        rate_ = edges / stopwatch_.Elapsed();
-    }
-
-  private:
-    double rate_;
-    Stopwatch stopwatch_;
-  };
-
-  struct SlidingRateInfo {
-    SlidingRateInfo(int n) : rate_(-1), N(n), last_update_(-1) {}
-
-    void Restart() { stopwatch_.Restart(); }
-    double rate() { return rate_; }
-
-    void UpdateRate(int update_hint) {
-      if (update_hint == last_update_)
-        return;
-      last_update_ = update_hint;
-
-      if (times_.size() == N)
-        times_.pop();
-      times_.push(stopwatch_.Elapsed());
-      if (times_.back() != times_.front())
-        rate_ = times_.size() / (times_.back() - times_.front());
-    }
-
-  private:
-    double rate_;
-    Stopwatch stopwatch_;
-    const size_t N;
-    std::queue<double> times_;
-    int last_update_;
-  };
-
-  mutable RateInfo overall_rate_;
-  mutable SlidingRateInfo current_rate_;
-};
-
 #endif  // NINJA_BUILD_H_
diff --git a/src/build_log_perftest.cc b/src/build_log_perftest.cc
index ced0df9..5a93619 100644
--- a/src/build_log_perftest.cc
+++ b/src/build_log_perftest.cc
@@ -112,7 +112,7 @@
   {
     // Read once to warm up disk cache.
     BuildLog log;
-    if (!log.Load(kTestFilename, &err)) {
+    if (log.Load(kTestFilename, &err) == LOAD_ERROR) {
       fprintf(stderr, "Failed to read test data: %s\n", err.c_str());
       return 1;
     }
@@ -121,7 +121,7 @@
   for (int i = 0; i < kNumRepetitions; ++i) {
     int64_t start = GetTimeMillis();
     BuildLog log;
-    if (!log.Load(kTestFilename, &err)) {
+    if (log.Load(kTestFilename, &err) == LOAD_ERROR) {
       fprintf(stderr, "Failed to read test data: %s\n", err.c_str());
       return 1;
     }
@@ -148,4 +148,3 @@
 
   return 0;
 }
-
diff --git a/src/build_test.cc b/src/build_test.cc
index 078080d..4ef62b2 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -19,6 +19,7 @@
 #include "build_log.h"
 #include "deps_log.h"
 #include "graph.h"
+#include "status.h"
 #include "test.h"
 
 using namespace std;
@@ -485,15 +486,13 @@
 };
 
 struct BuildTest : public StateTestWithBuiltinRules, public BuildLogUser {
-  BuildTest() : config_(MakeConfig()), command_runner_(&fs_),
-                builder_(&state_, config_, NULL, NULL, &fs_),
-                status_(config_) {
+  BuildTest() : config_(MakeConfig()), command_runner_(&fs_), status_(config_),
+                builder_(&state_, config_, NULL, NULL, &fs_, &status_, 0) {
   }
 
-  BuildTest(DepsLog* log) : config_(MakeConfig()), command_runner_(&fs_),
-                            builder_(&state_, config_, NULL, log, &fs_),
-                            status_(config_) {
-  }
+  explicit BuildTest(DepsLog* log)
+      : config_(MakeConfig()), command_runner_(&fs_), status_(config_),
+        builder_(&state_, config_, NULL, log, &fs_, &status_, 0) {}
 
   virtual void SetUp() {
     StateTestWithBuiltinRules::SetUp();
@@ -533,9 +532,8 @@
   BuildConfig config_;
   FakeCommandRunner command_runner_;
   VirtualFileSystem fs_;
+  StatusPrinter status_;
   Builder builder_;
-
-  BuildStatus status_;
 };
 
 void BuildTest::RebuildTarget(const string& target, const char* manifest,
@@ -564,7 +562,7 @@
     pdeps_log = &deps_log;
   }
 
-  Builder builder(pstate, config_, pbuild_log, pdeps_log, &fs_);
+  Builder builder(pstate, config_, pbuild_log, pdeps_log, &fs_, &status_, 0);
   EXPECT_TRUE(builder.AddTarget(target, &err));
 
   command_runner_.commands_ran_.clear();
@@ -611,6 +609,32 @@
     if (fs_->ReadFile(edge->inputs_[0]->path(), &content, &err) ==
         DiskInterface::Okay)
       fs_->WriteFile(edge->outputs_[0]->path(), content);
+  } else if (edge->rule().name() == "touch-implicit-dep-out") {
+    string dep = edge->GetBinding("test_dependency");
+    fs_->Create(dep, "");
+    fs_->Tick();
+    for (vector<Node*>::iterator out = edge->outputs_.begin();
+         out != edge->outputs_.end(); ++out) {
+      fs_->Create((*out)->path(), "");
+    }
+  } else if (edge->rule().name() == "touch-out-implicit-dep") {
+    string dep = edge->GetBinding("test_dependency");
+    for (vector<Node*>::iterator out = edge->outputs_.begin();
+         out != edge->outputs_.end(); ++out) {
+      fs_->Create((*out)->path(), "");
+    }
+    fs_->Tick();
+    fs_->Create(dep, "");
+  } else if (edge->rule().name() == "generate-depfile") {
+    string dep = edge->GetBinding("test_dependency");
+    string depfile = edge->GetUnescapedDepfile();
+    string contents;
+    for (vector<Node*>::iterator out = edge->outputs_.begin();
+         out != edge->outputs_.end(); ++out) {
+      contents += (*out)->path() + ": " + dep + "\n";
+      fs_->Create((*out)->path(), "");
+    }
+    fs_->Create(depfile, contents);
   } else {
     printf("unknown command\n");
     return false;
@@ -873,6 +897,14 @@
   EXPECT_EQ("unknown target: 'meow'", err);
 }
 
+TEST_F(BuildTest, MissingInputTarget) {
+  // Target is a missing input file
+  string err;
+  Dirty("in1");
+  EXPECT_FALSE(builder_.AddTarget("in1", &err));
+  EXPECT_EQ("'in1' missing and no known rule to make it", err);
+}
+
 TEST_F(BuildTest, MakeDirs) {
   string err;
 
@@ -1158,6 +1190,152 @@
   EXPECT_TRUE(builder_.AlreadyUpToDate());
 }
 
+// There are 6 different cases for phony rules:
+//
+// 1. output edge does not exist, inputs are not real
+// 2. output edge does not exist, no inputs
+// 3. output edge does not exist, inputs are real, newest mtime is M
+// 4. output edge is real, inputs are not real
+// 5. output edge is real, no inputs
+// 6. output edge is real, inputs are real, newest mtime is M
+//
+// Expected results :
+// 1. Edge is marked as clean, mtime is newest mtime of dependents.
+//     Touching inputs will cause dependents to rebuild.
+// 2. Edge is marked as dirty, causing dependent edges to always rebuild
+// 3. Edge is marked as clean, mtime is newest mtime of dependents.
+//     Touching inputs will cause dependents to rebuild.
+// 4. Edge is marked as clean, mtime is newest mtime of dependents.
+//     Touching inputs will cause dependents to rebuild.
+// 5. Edge is marked as dirty, causing dependent edges to always rebuild
+// 6. Edge is marked as clean, mtime is newest mtime of dependents.
+//     Touching inputs will cause dependents to rebuild.
+void TestPhonyUseCase(BuildTest* t, int i) {
+  State& state_ = t->state_;
+  Builder& builder_ = t->builder_;
+  FakeCommandRunner& command_runner_ = t->command_runner_;
+  VirtualFileSystem& fs_ = t->fs_;
+
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+" command = touch $out\n"
+"build notreal: phony blank\n"
+"build phony1: phony notreal\n"
+"build phony2: phony\n"
+"build phony3: phony blank\n"
+"build phony4: phony notreal\n"
+"build phony5: phony\n"
+"build phony6: phony blank\n"
+"\n"
+"build test1: touch phony1\n"
+"build test2: touch phony2\n"
+"build test3: touch phony3\n"
+"build test4: touch phony4\n"
+"build test5: touch phony5\n"
+"build test6: touch phony6\n"
+));
+
+  // Set up test.
+  builder_.command_runner_.release(); // BuildTest owns the CommandRunner
+  builder_.command_runner_.reset(&command_runner_);
+
+  fs_.Create("blank", "");  // a "real" file
+  EXPECT_TRUE(builder_.AddTarget("test1", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.AddTarget("test2", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.AddTarget("test3", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.AddTarget("test4", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.AddTarget("test5", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.AddTarget("test6", &err));
+  ASSERT_EQ("", err);
+  EXPECT_TRUE(builder_.Build(&err));
+  ASSERT_EQ("", err);
+
+  string ci;
+  ci += static_cast<char>('0' + i);
+
+  // Tests 1, 3, 4, and 6 should rebuild when the input is updated.
+  if (i != 2 && i != 5) {
+    Node* testNode  = t->GetNode("test" + ci);
+    Node* phonyNode = t->GetNode("phony" + ci);
+    Node* inputNode = t->GetNode("blank");
+
+    state_.Reset();
+    TimeStamp startTime = fs_.now_;
+
+    // Build number 1
+    EXPECT_TRUE(builder_.AddTarget("test" + ci, &err));
+    ASSERT_EQ("", err);
+    if (!builder_.AlreadyUpToDate())
+      EXPECT_TRUE(builder_.Build(&err));
+    ASSERT_EQ("", err);
+
+    // Touch the input file
+    state_.Reset();
+    command_runner_.commands_ran_.clear();
+    fs_.Tick();
+    fs_.Create("blank", "");  // a "real" file
+    EXPECT_TRUE(builder_.AddTarget("test" + ci, &err));
+    ASSERT_EQ("", err);
+
+    // Second build, expect testN edge to be rebuilt
+    // and phonyN node's mtime to be updated.
+    EXPECT_FALSE(builder_.AlreadyUpToDate());
+    EXPECT_TRUE(builder_.Build(&err));
+    ASSERT_EQ("", err);
+    ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+    EXPECT_EQ(string("touch test") + ci, command_runner_.commands_ran_[0]);
+    EXPECT_TRUE(builder_.AlreadyUpToDate());
+
+    TimeStamp inputTime = inputNode->mtime();
+
+    EXPECT_FALSE(phonyNode->exists());
+    EXPECT_FALSE(phonyNode->dirty());
+
+    EXPECT_GT(phonyNode->mtime(), startTime);
+    EXPECT_EQ(phonyNode->mtime(), inputTime);
+    ASSERT_TRUE(testNode->Stat(&fs_, &err));
+    EXPECT_TRUE(testNode->exists());
+    EXPECT_GT(testNode->mtime(), startTime);
+  } else {
+    // Tests 2 and 5: Expect dependents to always rebuild.
+
+    state_.Reset();
+    command_runner_.commands_ran_.clear();
+    fs_.Tick();
+    command_runner_.commands_ran_.clear();
+    EXPECT_TRUE(builder_.AddTarget("test" + ci, &err));
+    ASSERT_EQ("", err);
+    EXPECT_FALSE(builder_.AlreadyUpToDate());
+    EXPECT_TRUE(builder_.Build(&err));
+    ASSERT_EQ("", err);
+    ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+    EXPECT_EQ("touch test" + ci, command_runner_.commands_ran_[0]);
+
+    state_.Reset();
+    command_runner_.commands_ran_.clear();
+    EXPECT_TRUE(builder_.AddTarget("test" + ci, &err));
+    ASSERT_EQ("", err);
+    EXPECT_FALSE(builder_.AlreadyUpToDate());
+    EXPECT_TRUE(builder_.Build(&err));
+    ASSERT_EQ("", err);
+    ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+    EXPECT_EQ("touch test" + ci, command_runner_.commands_ran_[0]);
+  }
+}
+
+TEST_F(BuildTest, PhonyUseCase1) { TestPhonyUseCase(this, 1); }
+TEST_F(BuildTest, PhonyUseCase2) { TestPhonyUseCase(this, 2); }
+TEST_F(BuildTest, PhonyUseCase3) { TestPhonyUseCase(this, 3); }
+TEST_F(BuildTest, PhonyUseCase4) { TestPhonyUseCase(this, 4); }
+TEST_F(BuildTest, PhonyUseCase5) { TestPhonyUseCase(this, 5); }
+TEST_F(BuildTest, PhonyUseCase6) { TestPhonyUseCase(this, 6); }
+
 TEST_F(BuildTest, Fail) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "rule fail\n"
@@ -1272,6 +1450,55 @@
   BuildLog build_log_;
 };
 
+TEST_F(BuildWithLogTest, ImplicitGeneratedOutOfDate) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"  generator = 1\n"
+"build out.imp: touch | in\n"));
+  fs_.Create("out.imp", "");
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  string err;
+
+  EXPECT_TRUE(builder_.AddTarget("out.imp", &err));
+  EXPECT_FALSE(builder_.AlreadyUpToDate());
+
+  EXPECT_TRUE(GetNode("out.imp")->dirty());
+}
+
+TEST_F(BuildWithLogTest, ImplicitGeneratedOutOfDate2) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch-implicit-dep-out\n"
+"  command = touch $test_dependency ; sleep 1 ; touch $out\n"
+"  generator = 1\n"
+"build out.imp: touch-implicit-dep-out | inimp inimp2\n"
+"  test_dependency = inimp\n"));
+  fs_.Create("inimp", "");
+  fs_.Create("out.imp", "");
+  fs_.Tick();
+  fs_.Create("inimp2", "");
+  fs_.Tick();
+
+  string err;
+
+  EXPECT_TRUE(builder_.AddTarget("out.imp", &err));
+  EXPECT_FALSE(builder_.AlreadyUpToDate());
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_TRUE(builder_.AlreadyUpToDate());
+
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  builder_.Cleanup();
+  builder_.plan_.Reset();
+
+  EXPECT_TRUE(builder_.AddTarget("out.imp", &err));
+  EXPECT_TRUE(builder_.AlreadyUpToDate());
+  EXPECT_FALSE(GetNode("out.imp")->dirty());
+}
+
 TEST_F(BuildWithLogTest, NotInLogButOnDisk) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "rule cc\n"
@@ -1401,8 +1628,8 @@
   ASSERT_EQ("", err);
   EXPECT_TRUE(builder_.Build(&err));
   ASSERT_EQ("", err);
-  EXPECT_EQ("[3/3]", builder_.status_->FormatProgressStatus("[%s/%t]",
-      BuildStatus::kEdgeStarted));
+  EXPECT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ(3u, builder_.plan_.command_edge_count());
   command_runner_.commands_ran_.clear();
   state_.Reset();
 
@@ -1573,6 +1800,33 @@
   ASSERT_EQ(restat_mtime, log_entry->mtime);
 }
 
+TEST_F(BuildWithLogTest, GeneratedPlainDepfileMtime) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule generate-depfile\n"
+"  command = touch $out ; echo \"$out: $test_dependency\" > $depfile\n"
+"build out: generate-depfile\n"
+"  test_dependency = inimp\n"
+"  depfile = out.d\n"));
+  fs_.Create("inimp", "");
+  fs_.Tick();
+
+  string err;
+
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_FALSE(builder_.AlreadyUpToDate());
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_TRUE(builder_.AlreadyUpToDate());
+
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  builder_.Cleanup();
+  builder_.plan_.Reset();
+
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_TRUE(builder_.AlreadyUpToDate());
+}
+
 struct BuildDryRun : public BuildWithLogTest {
   BuildDryRun() {
     config_.dry_run = true;
@@ -1844,14 +2098,12 @@
   status_.BuildStarted();
   // Before any task is done, the elapsed time must be zero.
   EXPECT_EQ("[%/e0.000]",
-            status_.FormatProgressStatus("[%%/e%e]",
-                BuildStatus::kEdgeStarted));
+            status_.FormatProgressStatus("[%%/e%e]", 0));
 }
 
 TEST_F(BuildTest, StatusFormatReplacePlaceholder) {
   EXPECT_EQ("[%/s0/t0/r0/u0/f0]",
-            status_.FormatProgressStatus("[%%/s%s/t%t/r%r/u%u/f%f]",
-                BuildStatus::kEdgeStarted));
+            status_.FormatProgressStatus("[%%/s%s/t%t/r%r/u%u/f%f]", 0));
 }
 
 TEST_F(BuildTest, FailedDepsParse) {
@@ -2103,7 +2355,7 @@
   void* builder_;
 };
 
-/// Run a straightforwad build where the deps log is used.
+/// Run a straightforward build where the deps log is used.
 TEST_F(BuildWithDepsLogTest, Straightforward) {
   string err;
   // Note: in1 was created by the superclass SetUp().
@@ -2121,7 +2373,7 @@
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
     ASSERT_EQ("", err);
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
     EXPECT_TRUE(builder.AddTarget("out", &err));
     ASSERT_EQ("", err);
@@ -2151,7 +2403,7 @@
     ASSERT_TRUE(deps_log.Load("ninja_deps", &state, &err));
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
     command_runner_.commands_ran_.clear();
     EXPECT_TRUE(builder.AddTarget("out", &err));
@@ -2192,7 +2444,7 @@
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
     ASSERT_EQ("", err);
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
     EXPECT_TRUE(builder.AddTarget("out", &err));
     ASSERT_EQ("", err);
@@ -2221,7 +2473,7 @@
     ASSERT_TRUE(deps_log.Load("ninja_deps", &state, &err));
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
     command_runner_.commands_ran_.clear();
     EXPECT_TRUE(builder.AddTarget("out", &err));
@@ -2257,7 +2509,7 @@
 
   // The deps log is NULL in dry runs.
   config_.dry_run = true;
-  Builder builder(&state, config_, NULL, NULL, &fs_);
+  Builder builder(&state, config_, NULL, NULL, &fs_, &status_, 0);
   builder.command_runner_.reset(&command_runner_);
   command_runner_.commands_ran_.clear();
 
@@ -2315,7 +2567,7 @@
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
     ASSERT_EQ("", err);
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
     EXPECT_TRUE(builder.AddTarget("out", &err));
     ASSERT_EQ("", err);
@@ -2341,7 +2593,7 @@
     ASSERT_TRUE(deps_log.Load("ninja_deps", &state, &err));
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
     command_runner_.commands_ran_.clear();
     EXPECT_TRUE(builder.AddTarget("out", &err));
@@ -2374,7 +2626,7 @@
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
     ASSERT_EQ("", err);
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
     EXPECT_TRUE(builder.AddTarget("fo o.o", &err));
     ASSERT_EQ("", err);
@@ -2395,7 +2647,7 @@
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
     ASSERT_EQ("", err);
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
 
     Edge* edge = state.edges_.back();
@@ -2418,6 +2670,90 @@
   }
 }
 
+TEST_F(BuildWithDepsLogTest, DiscoveredDepDuringBuildChanged) {
+  string err;
+  const char* manifest =
+    "rule touch-out-implicit-dep\n"
+    "  command = touch $out ; sleep 1 ; touch $test_dependency\n"
+    "rule generate-depfile\n"
+    "  command = touch $out ; echo \"$out: $test_dependency\" > $depfile\n"
+    "build out1: touch-out-implicit-dep in1\n"
+    "  test_dependency = inimp\n"
+    "build out2: generate-depfile in1 || out1\n"
+    "  test_dependency = inimp\n"
+    "  depfile = out2.d\n"
+    "  deps = gcc\n";
+
+  fs_.Create("in1", "");
+  fs_.Tick();
+
+  BuildLog build_log;
+
+  {
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, &build_log, &deps_log, &fs_, &status_, 0);
+    builder.command_runner_.reset(&command_runner_);
+    EXPECT_TRUE(builder.AddTarget("out2", &err));
+    EXPECT_FALSE(builder.AlreadyUpToDate());
+
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_TRUE(builder.AlreadyUpToDate());
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+
+  fs_.Tick();
+  fs_.Create("in1", "");
+
+  {
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.Load("ninja_deps", &state, &err));
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, &build_log, &deps_log, &fs_, &status_, 0);
+    builder.command_runner_.reset(&command_runner_);
+    EXPECT_TRUE(builder.AddTarget("out2", &err));
+    EXPECT_FALSE(builder.AlreadyUpToDate());
+
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_TRUE(builder.AlreadyUpToDate());
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+
+  fs_.Tick();
+
+  {
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.Load("ninja_deps", &state, &err));
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, &build_log, &deps_log, &fs_, &status_, 0);
+    builder.command_runner_.reset(&command_runner_);
+    EXPECT_TRUE(builder.AddTarget("out2", &err));
+    EXPECT_TRUE(builder.AlreadyUpToDate());
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+}
+
 #ifdef _WIN32
 TEST_F(BuildWithDepsLogTest, DepFileDepsLogCanonicalize) {
   string err;
@@ -2436,7 +2772,7 @@
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
     ASSERT_EQ("", err);
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
     EXPECT_TRUE(builder.AddTarget("a/b/c/d/e/fo o.o", &err));
     ASSERT_EQ("", err);
@@ -2459,7 +2795,7 @@
     ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
     ASSERT_EQ("", err);
 
-    Builder builder(&state, config_, NULL, &deps_log, &fs_);
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
     builder.command_runner_.reset(&command_runner_);
 
     Edge* edge = state.edges_.back();
@@ -2901,6 +3237,67 @@
   EXPECT_EQ("touch out", command_runner_.commands_ran_[2]);
 }
 
+TEST_F(BuildTest, DyndepBuildDiscoverNewInputWithValidation) {
+  // Verify that a dyndep file cannot contain the |@ validation
+  // syntax.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+));
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep |@ validation\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_FALSE(builder_.Build(&err));
+
+  string err_first_line = err.substr(0, err.find("\n"));
+  EXPECT_EQ("dd:2: expected newline, got '|@'", err_first_line);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverNewInputWithTransitiveValidation) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // a new input to an edge that has a validation edge.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build in: touch |@ validation\n"
+"build validation: touch in out\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+  ));
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep | in\n"
+);
+  fs_.Tick();
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(4u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch in", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch out", command_runner_.commands_ran_[2]);
+  EXPECT_EQ("touch validation", command_runner_.commands_ran_[3]);
+}
+
 TEST_F(BuildTest, DyndepBuildDiscoverImplicitConnection) {
   // Verify that a dyndep file can be built and loaded to discover
   // that one edge has an implicit output that is also an implicit
@@ -2933,6 +3330,48 @@
   EXPECT_EQ("touch out out.imp", command_runner_.commands_ran_[2]);
 }
 
+TEST_F(BuildTest, DyndepBuildDiscoverOutputAndDepfileInput) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // that one edge has an implicit output that is also reported by
+  // a depfile as an input of another edge.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out $out.imp\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build tmp: touch || dd\n"
+"  dyndep = dd\n"
+"build out: cp tmp\n"
+"  depfile = out.d\n"
+));
+  fs_.Create("out.d", "out: tmp.imp\n");
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build tmp | tmp.imp: dyndep\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  // Loading the depfile gave tmp.imp a phony input edge.
+  ASSERT_TRUE(GetNode("tmp.imp")->in_edge()->is_phony());
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  // Loading the dyndep file gave tmp.imp a real input edge.
+  ASSERT_FALSE(GetNode("tmp.imp")->in_edge()->is_phony());
+
+  ASSERT_EQ(3u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch tmp tmp.imp", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("cp tmp out", command_runner_.commands_ran_[2]);
+  EXPECT_EQ(1u, fs_.files_created_.count("tmp.imp"));
+  EXPECT_TRUE(builder_.AlreadyUpToDate());
+}
+
 TEST_F(BuildTest, DyndepBuildDiscoverNowWantEdge) {
   // Verify that a dyndep file can be built and loaded to discover
   // that an edge is actually wanted due to a missing implicit output.
@@ -3302,3 +3741,247 @@
   EXPECT_EQ("touch tmp", command_runner_.commands_ran_[3]);
   EXPECT_EQ("touch out", command_runner_.commands_ran_[4]);
 }
+
+TEST_F(BuildTest, Validation) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ validate\n"
+    "build validate: cat in2\n"));
+
+  fs_.Create("in", "");
+  fs_.Create("in2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in" only rebuilds "out" ("validate" doesn't depend on
+  // "out").
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in > out", command_runner_.commands_ran_[0]);
+
+  // Test touching "in2" only rebuilds "validate" ("out" doesn't depend on
+  // "validate").
+  fs_.Tick();
+  fs_.Create("in2", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in2 > validate", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildTest, ValidationDependsOnOutput) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ validate\n"
+    "build validate: cat in2 | out\n"));
+
+  fs_.Create("in", "");
+  fs_.Create("in2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in" rebuilds "out" and "validate".
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in2" only rebuilds "validate" ("out" doesn't depend on
+  // "validate").
+  fs_.Tick();
+  fs_.Create("in2", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in2 > validate", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildWithDepsLogTest, ValidationThroughDepfile) {
+  const char* manifest =
+      "build out: cat in |@ validate\n"
+      "build validate: cat in2 | out\n"
+      "build out2: cat in3\n"
+      "  deps = gcc\n"
+      "  depfile = out2.d\n";
+
+  string err;
+
+  {
+    fs_.Create("in", "");
+    fs_.Create("in2", "");
+    fs_.Create("in3", "");
+    fs_.Create("out2.d", "out: out");
+
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
+    builder.command_runner_.reset(&command_runner_);
+
+    EXPECT_TRUE(builder.AddTarget("out2", &err));
+    ASSERT_EQ("", err);
+
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    // On the first build, only the out2 command is run.
+    ASSERT_EQ(command_runner_.commands_ran_.size(), 1);
+    EXPECT_EQ("cat in3 > out2", command_runner_.commands_ran_[0]);
+
+    // The deps file should have been removed.
+    EXPECT_EQ(0, fs_.Stat("out2.d", &err));
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+
+  fs_.Tick();
+  command_runner_.commands_ran_.clear();
+
+  {
+    fs_.Create("in2", "");
+    fs_.Create("in3", "");
+
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.Load("ninja_deps", &state, &err));
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
+    builder.command_runner_.reset(&command_runner_);
+
+    EXPECT_TRUE(builder.AddTarget("out2", &err));
+    ASSERT_EQ("", err);
+
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    // The out and validate actions should have been run as well as out2.
+    ASSERT_EQ(command_runner_.commands_ran_.size(), 3);
+    // out has to run first, as both out2 and validate depend on it.
+    EXPECT_EQ("cat in > out", command_runner_.commands_ran_[0]);
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+}
+
+TEST_F(BuildTest, ValidationCircular) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ out2\n"
+    "build out2: cat in2 |@ out\n"));
+
+  fs_.Create("in", "");
+  fs_.Create("in2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in" rebuilds "out".
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in > out", command_runner_.commands_ran_[0]);
+
+  // Test touching "in2" rebuilds "out2".
+  fs_.Tick();
+  fs_.Create("in2", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in2 > out2", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildTest, ValidationWithCircularDependency) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ validate\n"
+    "build validate: cat validate_in | out\n"
+    "build validate_in: cat validate\n"));
+
+  fs_.Create("in", "");
+
+  string err;
+  EXPECT_FALSE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("dependency cycle: validate -> validate_in -> validate", err);
+}
diff --git a/src/canon_perftest.cc b/src/canon_perftest.cc
index 088bd45..6b5e382 100644
--- a/src/canon_perftest.cc
+++ b/src/canon_perftest.cc
@@ -26,7 +26,6 @@
 
 int main() {
   vector<int> times;
-  string err;
 
   char buf[200];
   size_t len = strlen(kPath);
@@ -37,7 +36,7 @@
     int64_t start = GetTimeMillis();
     uint64_t slash_bits;
     for (int i = 0; i < kNumRepetitions; ++i) {
-      CanonicalizePath(buf, &len, &slash_bits, &err);
+      CanonicalizePath(buf, &len, &slash_bits);
     }
     int delta = (int)(GetTimeMillis() - start);
     times.push_back(delta);
diff --git a/src/clean.cc b/src/clean.cc
index 3e57437..575bf6b 100644
--- a/src/clean.cc
+++ b/src/clean.cc
@@ -129,7 +129,16 @@
   PrintHeader();
   for (BuildLog::Entries::const_iterator i = entries.begin(); i != entries.end(); ++i) {
     Node* n = state_->LookupNode(i->first);
-    if (!n || !n->in_edge()) {
+    // Detecting stale outputs works as follows:
+    //
+    // - If it has no Node, it is not in the build graph, or the deps log
+    //   anymore, hence is stale.
+    //
+    // - If it isn't an output or input for any edge, it comes from a stale
+    //   entry in the deps log, but no longer referenced from the build
+    //   graph.
+    //
+    if (!n || (!n->in_edge() && n->out_edges().empty())) {
       Remove(i->first.AsString());
     }
   }
@@ -189,21 +198,21 @@
   LoadDyndeps();
   for (int i = 0; i < target_count; ++i) {
     string target_name = targets[i];
-    uint64_t slash_bits;
-    string err;
-    if (!CanonicalizePath(&target_name, &slash_bits, &err)) {
-      Error("failed to canonicalize '%s': %s", target_name.c_str(), err.c_str());
+    if (target_name.empty()) {
+      Error("failed to canonicalize '': empty path");
       status_ = 1;
+      continue;
+    }
+    uint64_t slash_bits;
+    CanonicalizePath(&target_name, &slash_bits);
+    Node* target = state_->LookupNode(target_name);
+    if (target) {
+      if (IsVerbose())
+        printf("Target %s\n", target_name.c_str());
+      DoCleanTarget(target);
     } else {
-      Node* target = state_->LookupNode(target_name);
-      if (target) {
-        if (IsVerbose())
-          printf("Target %s\n", target_name.c_str());
-        DoCleanTarget(target);
-      } else {
-        Error("unknown target '%s'", target_name.c_str());
-        status_ = 1;
-      }
+      Error("unknown target '%s'", target_name.c_str());
+      status_ = 1;
     }
   }
   PrintFooter();
diff --git a/src/clean_test.cc b/src/clean_test.cc
index 1b843a2..e99909c 100644
--- a/src/clean_test.cc
+++ b/src/clean_test.cc
@@ -537,4 +537,65 @@
   EXPECT_NE(0, fs_.Stat("out2", &err));
   log2.Close();
 }
+
+TEST_F(CleanDeadTest, CleanDeadPreservesInputs) {
+  State state;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state,
+"rule cat\n"
+"  command = cat $in > $out\n"
+"build out1: cat in\n"
+"build out2: cat in\n"
+));
+  // This manifest does not build out1 anymore, but makes
+  // it an implicit input. CleanDead should detect this
+  // and preserve it.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build out2: cat in | out1\n"
+));
+  fs_.Create("in", "");
+  fs_.Create("out1", "");
+  fs_.Create("out2", "");
+
+  BuildLog log1;
+  string err;
+  EXPECT_TRUE(log1.OpenForWrite(kTestFilename, *this, &err));
+  ASSERT_EQ("", err);
+  log1.RecordCommand(state.edges_[0], 15, 18);
+  log1.RecordCommand(state.edges_[1], 20, 25);
+  log1.Close();
+
+  BuildLog log2;
+  EXPECT_TRUE(log2.Load(kTestFilename, &err));
+  ASSERT_EQ("", err);
+  ASSERT_EQ(2u, log2.entries().size());
+  ASSERT_TRUE(log2.LookupByOutput("out1"));
+  ASSERT_TRUE(log2.LookupByOutput("out2"));
+
+  // First use the manifest that describe how to build out1.
+  Cleaner cleaner1(&state, config_, &fs_);
+  EXPECT_EQ(0, cleaner1.CleanDead(log2.entries()));
+  EXPECT_EQ(0, cleaner1.cleaned_files_count());
+  EXPECT_EQ(0u, fs_.files_removed_.size());
+  EXPECT_NE(0, fs_.Stat("in", &err));
+  EXPECT_NE(0, fs_.Stat("out1", &err));
+  EXPECT_NE(0, fs_.Stat("out2", &err));
+
+  // Then use the manifest that does not build out1 anymore.
+  Cleaner cleaner2(&state_, config_, &fs_);
+  EXPECT_EQ(0, cleaner2.CleanDead(log2.entries()));
+  EXPECT_EQ(0, cleaner2.cleaned_files_count());
+  EXPECT_EQ(0u, fs_.files_removed_.size());
+  EXPECT_NE(0, fs_.Stat("in", &err));
+  EXPECT_NE(0, fs_.Stat("out1", &err));
+  EXPECT_NE(0, fs_.Stat("out2", &err));
+
+  // Nothing to do now.
+  EXPECT_EQ(0, cleaner2.CleanDead(log2.entries()));
+  EXPECT_EQ(0, cleaner2.cleaned_files_count());
+  EXPECT_EQ(0u, fs_.files_removed_.size());
+  EXPECT_NE(0, fs_.Stat("in", &err));
+  EXPECT_NE(0, fs_.Stat("out1", &err));
+  EXPECT_NE(0, fs_.Stat("out2", &err));
+  log2.Close();
+}
 }  // anonymous namespace
diff --git a/src/clparser.cc b/src/clparser.cc
index 275641e..3d3e7de 100644
--- a/src/clparser.cc
+++ b/src/clparser.cc
@@ -72,7 +72,8 @@
   return EndsWith(line, ".c") ||
       EndsWith(line, ".cc") ||
       EndsWith(line, ".cxx") ||
-      EndsWith(line, ".cpp");
+      EndsWith(line, ".cpp") ||
+      EndsWith(line, ".c++");
 }
 
 // static
@@ -83,6 +84,7 @@
   // Loop over all lines in the output to process them.
   assert(&output != filtered_output);
   size_t start = 0;
+  bool seen_show_includes = false;
 #ifdef _WIN32
   IncludesNormalize normalizer(".");
 #endif
@@ -95,6 +97,7 @@
 
     string include = FilterShowIncludes(line, deps_prefix);
     if (!include.empty()) {
+      seen_show_includes = true;
       string normalized;
 #ifdef _WIN32
       if (!normalizer.Normalize(include, &normalized, err))
@@ -103,12 +106,11 @@
       // TODO: should this make the path relative to cwd?
       normalized = include;
       uint64_t slash_bits;
-      if (!CanonicalizePath(&normalized, &slash_bits, err))
-        return false;
+      CanonicalizePath(&normalized, &slash_bits);
 #endif
       if (!IsSystemInclude(normalized))
         includes_.insert(normalized);
-    } else if (FilterInputFilename(line)) {
+    } else if (!seen_show_includes && FilterInputFilename(line)) {
       // Drop it.
       // TODO: if we support compiling multiple output files in a single
       // cl.exe invocation, we should stash the filename.
diff --git a/src/clparser_test.cc b/src/clparser_test.cc
index 0b829c1..f141680 100644
--- a/src/clparser_test.cc
+++ b/src/clparser_test.cc
@@ -70,6 +70,17 @@
   ASSERT_EQ("cl: warning\n", output);
 }
 
+TEST(CLParserTest, NoFilenameFilterAfterShowIncludes) {
+  CLParser parser;
+  string output, err;
+  ASSERT_TRUE(parser.Parse(
+      "foo.cc\r\n"
+      "Note: including file: foo.h\r\n"
+      "something something foo.cc\r\n",
+      "", &output, &err));
+  ASSERT_EQ("something something foo.cc\n", output);
+}
+
 TEST(CLParserTest, ParseSystemInclude) {
   CLParser parser;
   string output, err;
diff --git a/src/depfile_parser.cc b/src/depfile_parser.cc
index bffeb76..98fba2e 100644
--- a/src/depfile_parser.cc
+++ b/src/depfile_parser.cc
@@ -1,4 +1,4 @@
-/* Generated by re2c 1.3 */
+/* Generated by re2c */
 // Copyright 2011 Google Inc. All Rights Reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
diff --git a/src/deps_log.cc b/src/deps_log.cc
index 191f300..7e48b38 100644
--- a/src/deps_log.cc
+++ b/src/deps_log.cc
@@ -295,6 +295,19 @@
   return deps_[node->id()];
 }
 
+Node* DepsLog::GetFirstReverseDepsNode(Node* node) {
+  for (size_t id = 0; id < deps_.size(); ++id) {
+    Deps* deps = deps_[id];
+    if (!deps)
+      continue;
+    for (int i = 0; i < deps->node_count; ++i) {
+      if (deps->nodes[i] == node)
+        return nodes_[id];
+    }
+  }
+  return NULL;
+}
+
 bool DepsLog::Recompact(const string& path, string* err) {
   METRIC_RECORD(".ninja_deps recompact");
 
diff --git a/src/deps_log.h b/src/deps_log.h
index cc44b41..09cc41c 100644
--- a/src/deps_log.h
+++ b/src/deps_log.h
@@ -86,6 +86,7 @@
   };
   LoadStatus Load(const std::string& path, State* state, std::string* err);
   Deps* GetDeps(Node* node);
+  Node* GetFirstReverseDepsNode(Node* node);
 
   /// Rewrite the known log entries, throwing away old data.
   bool Recompact(const std::string& path, std::string* err);
diff --git a/src/deps_log_test.cc b/src/deps_log_test.cc
index 4055941..13fcc78 100644
--- a/src/deps_log_test.cc
+++ b/src/deps_log_test.cc
@@ -390,7 +390,7 @@
     DepsLog log;
     EXPECT_TRUE(log.Load(kTestFilename, &state, &err));
     if (!err.empty()) {
-      // At some point the log will be so short as to be unparseable.
+      // At some point the log will be so short as to be unparsable.
       break;
     }
 
@@ -478,4 +478,31 @@
   }
 }
 
+TEST_F(DepsLogTest, ReverseDepsNodes) {
+  State state;
+  DepsLog log;
+  string err;
+  EXPECT_TRUE(log.OpenForWrite(kTestFilename, &err));
+  ASSERT_EQ("", err);
+
+  vector<Node*> deps;
+  deps.push_back(state.GetNode("foo.h", 0));
+  deps.push_back(state.GetNode("bar.h", 0));
+  log.RecordDeps(state.GetNode("out.o", 0), 1, deps);
+
+  deps.clear();
+  deps.push_back(state.GetNode("foo.h", 0));
+  deps.push_back(state.GetNode("bar2.h", 0));
+  log.RecordDeps(state.GetNode("out2.o", 0), 2, deps);
+
+  log.Close();
+
+  Node* rev_deps = log.GetFirstReverseDepsNode(state.GetNode("foo.h", 0));
+  EXPECT_TRUE(rev_deps == state.GetNode("out.o", 0) ||
+              rev_deps == state.GetNode("out2.o", 0));
+
+  rev_deps = log.GetFirstReverseDepsNode(state.GetNode("bar.h", 0));
+  EXPECT_TRUE(rev_deps == state.GetNode("out.o", 0));
+}
+
 }  // anonymous namespace
diff --git a/src/disk_interface.cc b/src/disk_interface.cc
index 49af001..e73d901 100644
--- a/src/disk_interface.cc
+++ b/src/disk_interface.cc
@@ -180,12 +180,13 @@
     dir = path;
   }
 
-  transform(dir.begin(), dir.end(), dir.begin(), ::tolower);
+  string dir_lowercase = dir;
+  transform(dir.begin(), dir.end(), dir_lowercase.begin(), ::tolower);
   transform(base.begin(), base.end(), base.begin(), ::tolower);
 
-  Cache::iterator ci = cache_.find(dir);
+  Cache::iterator ci = cache_.find(dir_lowercase);
   if (ci == cache_.end()) {
-    ci = cache_.insert(make_pair(dir, DirCache())).first;
+    ci = cache_.insert(make_pair(dir_lowercase, DirCache())).first;
     if (!StatAllFilesInDir(dir.empty() ? "." : dir, &ci->second, err)) {
       cache_.erase(ci);
       return -1;
@@ -265,6 +266,47 @@
 }
 
 int RealDiskInterface::RemoveFile(const string& path) {
+#ifdef _WIN32
+  DWORD attributes = GetFileAttributes(path.c_str());
+  if (attributes == INVALID_FILE_ATTRIBUTES) {
+    DWORD win_err = GetLastError();
+    if (win_err == ERROR_FILE_NOT_FOUND || win_err == ERROR_PATH_NOT_FOUND) {
+      return 1;
+    }
+  } else if (attributes & FILE_ATTRIBUTE_READONLY) {
+    // On non-Windows systems, remove() will happily delete read-only files.
+    // On Windows Ninja should behave the same:
+    //   https://github.com/ninja-build/ninja/issues/1886
+    // Skip error checking.  If this fails, accept whatever happens below.
+    SetFileAttributes(path.c_str(), attributes & ~FILE_ATTRIBUTE_READONLY);
+  }
+  if (attributes & FILE_ATTRIBUTE_DIRECTORY) {
+    // remove() deletes both files and directories. On Windows we have to 
+    // select the correct function (DeleteFile will yield Permission Denied when
+    // used on a directory)
+    // This fixes the behavior of ninja -t clean in some cases
+    // https://github.com/ninja-build/ninja/issues/828
+    if (!RemoveDirectory(path.c_str())) {
+      DWORD win_err = GetLastError();
+      if (win_err == ERROR_FILE_NOT_FOUND || win_err == ERROR_PATH_NOT_FOUND) {
+        return 1;
+      }
+      // Report remove(), not RemoveDirectory(), for cross-platform consistency.
+      Error("remove(%s): %s", path.c_str(), GetLastErrorString().c_str());
+      return -1;
+    }
+  } else {
+    if (!DeleteFile(path.c_str())) {
+      DWORD win_err = GetLastError();
+      if (win_err == ERROR_FILE_NOT_FOUND || win_err == ERROR_PATH_NOT_FOUND) {
+        return 1;
+      }
+      // Report as remove(), not DeleteFile(), for cross-platform consistency.
+      Error("remove(%s): %s", path.c_str(), GetLastErrorString().c_str());
+      return -1;
+    }
+  }
+#else
   if (remove(path.c_str()) < 0) {
     switch (errno) {
       case ENOENT:
@@ -273,9 +315,9 @@
         Error("remove(%s): %s", path.c_str(), strerror(errno));
         return -1;
     }
-  } else {
-    return 0;
   }
+#endif
+  return 0;
 }
 
 void RealDiskInterface::AllowStatCache(bool allow) {
diff --git a/src/disk_interface_test.cc b/src/disk_interface_test.cc
index 066c770..5e952ed 100644
--- a/src/disk_interface_test.cc
+++ b/src/disk_interface_test.cc
@@ -211,6 +211,20 @@
   EXPECT_EQ(0, disk_.RemoveFile(kFileName));
   EXPECT_EQ(1, disk_.RemoveFile(kFileName));
   EXPECT_EQ(1, disk_.RemoveFile("does not exist"));
+#ifdef _WIN32
+  ASSERT_TRUE(Touch(kFileName));
+  EXPECT_EQ(0, system((std::string("attrib +R ") + kFileName).c_str()));
+  EXPECT_EQ(0, disk_.RemoveFile(kFileName));
+  EXPECT_EQ(1, disk_.RemoveFile(kFileName));
+#endif
+}
+
+TEST_F(DiskInterfaceTest, RemoveDirectory) {
+  const char* kDirectoryName = "directory-to-remove";
+  EXPECT_TRUE(disk_.MakeDir(kDirectoryName));
+  EXPECT_EQ(0, disk_.RemoveFile(kDirectoryName));
+  EXPECT_EQ(1, disk_.RemoveFile(kDirectoryName));
+  EXPECT_EQ(1, disk_.RemoveFile("does not exist"));
 }
 
 struct StatTest : public StateTestWithBuiltinRules,
@@ -258,7 +272,7 @@
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_EQ(2u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_EQ("in",  stats_[1]);
@@ -274,7 +288,7 @@
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_EQ(3u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_TRUE(GetNode("out")->dirty());
@@ -294,7 +308,7 @@
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_EQ(1u + 6u, stats_.size());
   ASSERT_EQ("mid1", stats_[1]);
   ASSERT_TRUE(GetNode("mid1")->dirty());
@@ -315,7 +329,7 @@
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_FALSE(GetNode("in")->dirty());
   ASSERT_TRUE(GetNode("mid")->dirty());
   ASSERT_TRUE(GetNode("out")->dirty());
diff --git a/src/dyndep.cc b/src/dyndep.cc
index b388e9b..dd4ed09 100644
--- a/src/dyndep.cc
+++ b/src/dyndep.cc
@@ -97,9 +97,15 @@
   for (std::vector<Node*>::const_iterator i =
            dyndeps->implicit_outputs_.begin();
        i != dyndeps->implicit_outputs_.end(); ++i) {
-    if ((*i)->in_edge() != NULL) {
-      *err = "multiple rules generate " + (*i)->path();
-      return false;
+    if (Edge* old_in_edge = (*i)->in_edge()) {
+      // This node already has an edge producing it.  Fail with an error
+      // unless the edge was generated by ImplicitDepLoader, in which
+      // case we can replace it with the now-known real producer.
+      if (!old_in_edge->generated_by_dep_loader_) {
+        *err = "multiple rules generate " + (*i)->path();
+        return false;
+      }
+      old_in_edge->outputs_.clear();
     }
     (*i)->set_in_edge(edge);
   }
diff --git a/src/dyndep_parser.cc b/src/dyndep_parser.cc
index 56da16f..1b4dddd 100644
--- a/src/dyndep_parser.cc
+++ b/src/dyndep_parser.cc
@@ -115,10 +115,10 @@
       return lexer_.Error("expected path", err);
 
     string path = out0.Evaluate(&env_);
-    string path_err;
+    if (path.empty())
+      return lexer_.Error("empty path", err);
     uint64_t slash_bits;
-    if (!CanonicalizePath(&path, &slash_bits, &path_err))
-      return lexer_.Error(path_err, err);
+    CanonicalizePath(&path, &slash_bits);
     Node* node = state_->LookupNode(path);
     if (!node || !node->in_edge())
       return lexer_.Error("no build statement exists for '" + path + "'", err);
@@ -202,10 +202,10 @@
   dyndeps->implicit_inputs_.reserve(ins.size());
   for (vector<EvalString>::iterator i = ins.begin(); i != ins.end(); ++i) {
     string path = i->Evaluate(&env_);
-    string path_err;
+    if (path.empty())
+      return lexer_.Error("empty path", err);
     uint64_t slash_bits;
-    if (!CanonicalizePath(&path, &slash_bits, &path_err))
-      return lexer_.Error(path_err, err);
+    CanonicalizePath(&path, &slash_bits);
     Node* n = state_->GetNode(path, slash_bits);
     dyndeps->implicit_inputs_.push_back(n);
   }
@@ -213,10 +213,11 @@
   dyndeps->implicit_outputs_.reserve(outs.size());
   for (vector<EvalString>::iterator i = outs.begin(); i != outs.end(); ++i) {
     string path = i->Evaluate(&env_);
+    if (path.empty())
+      return lexer_.Error("empty path", err);
     string path_err;
     uint64_t slash_bits;
-    if (!CanonicalizePath(&path, &slash_bits, &path_err))
-      return lexer_.Error(path_err, err);
+    CanonicalizePath(&path, &slash_bits);
     Node* n = state_->GetNode(path, slash_bits);
     dyndeps->implicit_outputs_.push_back(n);
   }
diff --git a/src/eval_env.h b/src/eval_env.h
index ca7daa4..677dc21 100644
--- a/src/eval_env.h
+++ b/src/eval_env.h
@@ -55,7 +55,7 @@
   TokenList parsed_;
 };
 
-/// An invokable build command and associated metadata (description, etc.).
+/// An invocable build command and associated metadata (description, etc.).
 struct Rule {
   explicit Rule(const std::string& name) : name_(name) {}
 
diff --git a/src/graph.cc b/src/graph.cc
index ea11360..43ba45a 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -15,6 +15,7 @@
 #include "graph.h"
 
 #include <algorithm>
+#include <deque>
 #include <assert.h>
 #include <stdio.h>
 
@@ -31,16 +32,57 @@
 using namespace std;
 
 bool Node::Stat(DiskInterface* disk_interface, string* err) {
-  return (mtime_ = disk_interface->Stat(path_, err)) != -1;
+  METRIC_RECORD("node stat");
+  mtime_ = disk_interface->Stat(path_, err);
+  if (mtime_ == -1) {
+    return false;
+  }
+  exists_ = (mtime_ != 0) ? ExistenceStatusExists : ExistenceStatusMissing;
+  return true;
 }
 
-bool DependencyScan::RecomputeDirty(Node* node, string* err) {
-  vector<Node*> stack;
-  return RecomputeDirty(node, &stack, err);
+void Node::UpdatePhonyMtime(TimeStamp mtime) {
+  if (!exists()) {
+    mtime_ = std::max(mtime_, mtime);
+  }
 }
 
-bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
+bool DependencyScan::RecomputeDirty(Node* initial_node,
+                                    std::vector<Node*>* validation_nodes,
                                     string* err) {
+  std::vector<Node*> stack;
+  std::vector<Node*> new_validation_nodes;
+
+  std::deque<Node*> nodes(1, initial_node);
+
+  // RecomputeNodeDirty might return new validation nodes that need to be
+  // checked for dirty state, keep a queue of nodes to visit.
+  while (!nodes.empty()) {
+    Node* node = nodes.front();
+    nodes.pop_front();
+
+    stack.clear();
+    new_validation_nodes.clear();
+
+    if (!RecomputeNodeDirty(node, &stack, &new_validation_nodes, err))
+      return false;
+    nodes.insert(nodes.end(), new_validation_nodes.begin(),
+                              new_validation_nodes.end());
+    if (!new_validation_nodes.empty()) {
+      assert(validation_nodes &&
+          "validations require RecomputeDirty to be called with validation_nodes");
+      validation_nodes->insert(validation_nodes->end(),
+                           new_validation_nodes.begin(),
+                           new_validation_nodes.end());
+    }
+  }
+
+  return true;
+}
+
+bool DependencyScan::RecomputeNodeDirty(Node* node, std::vector<Node*>* stack,
+                                        std::vector<Node*>* validation_nodes,
+                                        string* err) {
   Edge* edge = node->in_edge();
   if (!edge) {
     // If we already visited this leaf node then we are done.
@@ -84,7 +126,7 @@
     //   Later during the build the dyndep file will become ready and be
     //   loaded to update this edge before it can possibly be scheduled.
     if (edge->dyndep_ && edge->dyndep_->dyndep_pending()) {
-      if (!RecomputeDirty(edge->dyndep_, stack, err))
+      if (!RecomputeNodeDirty(edge->dyndep_, stack, validation_nodes, err))
         return false;
 
       if (!edge->dyndep_->in_edge() ||
@@ -115,12 +157,20 @@
     }
   }
 
+  // Store any validation nodes from the edge for adding to the initial
+  // nodes.  Don't recurse into them, that would trigger the dependency
+  // cycle detector if the validation node depends on this node.
+  // RecomputeDirty will add the validation nodes to the initial nodes
+  // and recurse into them.
+  validation_nodes->insert(validation_nodes->end(),
+      edge->validations_.begin(), edge->validations_.end());
+
   // Visit all inputs; we're dirty if any of the inputs are dirty.
   Node* most_recent_input = NULL;
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
     // Visit this input.
-    if (!RecomputeDirty(*i, stack, err))
+    if (!RecomputeNodeDirty(*i, stack, validation_nodes, err))
       return false;
 
     // If an input is not ready, neither are our outputs.
@@ -237,6 +287,14 @@
               output->path().c_str());
       return true;
     }
+
+    // Update the mtime with the newest input. Dependents can thus call mtime()
+    // on the fake node and get the latest mtime of the dependencies
+    if (most_recent_input) {
+      output->UpdatePhonyMtime(most_recent_input->mtime());
+    }
+
+    // Phony edges are clean, nothing to do
     return false;
   }
 
@@ -398,6 +456,28 @@
   return result;
 }
 
+void Edge::CollectInputs(bool shell_escape,
+                         std::vector<std::string>* out) const {
+  for (std::vector<Node*>::const_iterator it = inputs_.begin();
+       it != inputs_.end(); ++it) {
+    std::string path = (*it)->PathDecanonicalized();
+    if (shell_escape) {
+      std::string unescaped;
+      unescaped.swap(path);
+#ifdef _WIN32
+      GetWin32EscapedString(unescaped, &path);
+#else
+      GetShellEscapedString(unescaped, &path);
+#endif
+    }
+#if __cplusplus >= 201103L
+    out->push_back(std::move(path));
+#else
+    out->push_back(path);
+#endif
+  }
+}
+
 std::string Edge::EvaluateCommand(const bool incl_rsp_file) const {
   string command = GetBinding("command");
   if (incl_rsp_file) {
@@ -443,6 +523,13 @@
        i != outputs_.end() && *i != NULL; ++i) {
     printf("%s ", (*i)->path().c_str());
   }
+  if (!validations_.empty()) {
+    printf(" validations ");
+    for (std::vector<Node*>::const_iterator i = validations_.begin();
+         i != validations_.end() && *i != NULL; ++i) {
+      printf("%s ", (*i)->path().c_str());
+    }
+  }
   if (pool_) {
     if (!pool_->name().empty()) {
       printf("(in pool '%s')", pool_->name().c_str());
@@ -487,7 +574,7 @@
 void Node::Dump(const char* prefix) const {
   printf("%s <%s 0x%p> mtime: %" PRId64 "%s, (:%s), ",
          prefix, path().c_str(), this,
-         mtime(), mtime() ? "" : " (:missing)",
+         mtime(), exists() ? "" : " (:missing)",
          dirty() ? " dirty" : " clean");
   if (in_edge()) {
     in_edge()->Dump("in-edge: ");
@@ -499,6 +586,13 @@
        e != out_edges().end() && *e != NULL; ++e) {
     (*e)->Dump(" +- ");
   }
+  if (!validation_out_edges().empty()) {
+    printf(" validation out edges:\n");
+    for (std::vector<Edge*>::const_iterator e = validation_out_edges().begin();
+         e != validation_out_edges().end() && *e != NULL; ++e) {
+      (*e)->Dump(" +- ");
+    }
+  }
 }
 
 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
@@ -515,7 +609,7 @@
 }
 
 struct matches {
-  matches(std::vector<StringPiece>::iterator i) : i_(i) {}
+  explicit matches(std::vector<StringPiece>::iterator i) : i_(i) {}
 
   bool operator()(const Node* node) const {
     StringPiece opath = StringPiece(node->path());
@@ -562,11 +656,8 @@
 
   uint64_t unused;
   std::vector<StringPiece>::iterator primary_out = depfile.outs_.begin();
-  if (!CanonicalizePath(const_cast<char*>(primary_out->str_),
-                        &primary_out->len_, &unused, err)) {
-    *err = path + ": " + *err;
-    return false;
-  }
+  CanonicalizePath(const_cast<char*>(primary_out->str_), &primary_out->len_,
+                   &unused);
 
   // Check that this depfile matches the edge's output, if not return false to
   // mark the edge as dirty.
@@ -588,18 +679,20 @@
     }
   }
 
+  return ProcessDepfileDeps(edge, &depfile.ins_, err);
+}
+
+bool ImplicitDepLoader::ProcessDepfileDeps(
+    Edge* edge, std::vector<StringPiece>* depfile_ins, std::string* err) {
   // Preallocate space in edge->inputs_ to be filled in below.
   vector<Node*>::iterator implicit_dep =
-      PreallocateSpace(edge, depfile.ins_.size());
+      PreallocateSpace(edge, depfile_ins->size());
 
   // Add all its in-edges.
-  for (vector<StringPiece>::iterator i = depfile.ins_.begin();
-       i != depfile.ins_.end(); ++i, ++implicit_dep) {
+  for (std::vector<StringPiece>::iterator i = depfile_ins->begin();
+       i != depfile_ins->end(); ++i, ++implicit_dep) {
     uint64_t slash_bits;
-    if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits,
-                          err))
-      return false;
-
+    CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits);
     Node* node = state_->GetNode(*i, slash_bits);
     *implicit_dep = node;
     node->AddOutEdge(edge);
@@ -649,6 +742,7 @@
     return;
 
   Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
+  phony_edge->generated_by_dep_loader_ = true;
   node->set_in_edge(phony_edge);
   phony_edge->outputs_.push_back(node);
 
diff --git a/src/graph.h b/src/graph.h
index 4833f49..9de67d2 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -15,6 +15,8 @@
 #ifndef NINJA_GRAPH_H_
 #define NINJA_GRAPH_H_
 
+#include <algorithm>
+#include <set>
 #include <string>
 #include <vector>
 
@@ -39,6 +41,7 @@
       : path_(path),
         slash_bits_(slash_bits),
         mtime_(-1),
+        exists_(ExistenceStatusUnknown),
         dirty_(false),
         dyndep_pending_(false),
         in_edge_(NULL),
@@ -47,6 +50,9 @@
   /// Return false on error.
   bool Stat(DiskInterface* disk_interface, std::string* err);
 
+  /// If the file doesn't exist, set the mtime_ from its dependencies
+  void UpdatePhonyMtime(TimeStamp mtime);
+
   /// Return false on error.
   bool StatIfNecessary(DiskInterface* disk_interface, std::string* err) {
     if (status_known())
@@ -57,20 +63,24 @@
   /// Mark as not-yet-stat()ed and not dirty.
   void ResetState() {
     mtime_ = -1;
+    exists_ = ExistenceStatusUnknown;
     dirty_ = false;
   }
 
   /// Mark the Node as already-stat()ed and missing.
   void MarkMissing() {
-    mtime_ = 0;
+    if (mtime_ == -1) {
+      mtime_ = 0;
+    }
+    exists_ = ExistenceStatusMissing;
   }
 
   bool exists() const {
-    return mtime_ != 0;
+    return exists_ == ExistenceStatusExists;
   }
 
   bool status_known() const {
-    return mtime_ != -1;
+    return exists_ != ExistenceStatusUnknown;
   }
 
   const std::string& path() const { return path_; }
@@ -98,7 +108,9 @@
   void set_id(int id) { id_ = id; }
 
   const std::vector<Edge*>& out_edges() const { return out_edges_; }
+  const std::vector<Edge*>& validation_out_edges() const { return validation_out_edges_; }
   void AddOutEdge(Edge* edge) { out_edges_.push_back(edge); }
+  void AddValidationOutEdge(Edge* edge) { validation_out_edges_.push_back(edge); }
 
   void Dump(const char* prefix="") const;
 
@@ -112,9 +124,19 @@
   /// Possible values of mtime_:
   ///   -1: file hasn't been examined
   ///   0:  we looked, and file doesn't exist
-  ///   >0: actual file's mtime
+  ///   >0: actual file's mtime, or the latest mtime of its dependencies if it doesn't exist
   TimeStamp mtime_;
 
+  enum ExistenceStatus {
+    /// The file hasn't been examined.
+    ExistenceStatusUnknown,
+    /// The file doesn't exist. mtime_ will be the latest mtime of its dependencies.
+    ExistenceStatusMissing,
+    /// The path is an actual file. mtime_ will be the file's mtime.
+    ExistenceStatusExists
+  };
+  ExistenceStatus exists_;
+
   /// Dirty is true when the underlying file is out-of-date.
   /// But note that Edge::outputs_ready_ is also used in judging which
   /// edges to build.
@@ -131,6 +153,9 @@
   /// All Edges that use this Node as an input.
   std::vector<Edge*> out_edges_;
 
+  /// All Edges that use this Node as a validation.
+  std::vector<Edge*> validation_out_edges_;
+
   /// A dense integer id for the node, assigned and used by DepsLog.
   int id_;
 };
@@ -143,10 +168,11 @@
     VisitDone
   };
 
-  Edge() : rule_(NULL), pool_(NULL), dyndep_(NULL), env_(NULL),
-           mark_(VisitNone), outputs_ready_(false), deps_loaded_(false),
-           deps_missing_(false), implicit_deps_(0), order_only_deps_(0),
-           implicit_outs_(0) {}
+  Edge()
+      : rule_(NULL), pool_(NULL), dyndep_(NULL), env_(NULL), mark_(VisitNone),
+        id_(0), outputs_ready_(false), deps_loaded_(false),
+        deps_missing_(false), generated_by_dep_loader_(false),
+        implicit_deps_(0), order_only_deps_(0), implicit_outs_(0) {}
 
   /// Return true if all inputs' in-edges are ready.
   bool AllInputsReady() const;
@@ -169,16 +195,22 @@
 
   void Dump(const char* prefix="") const;
 
+  // Append all edge explicit inputs to |*out|. Possibly with shell escaping.
+  void CollectInputs(bool shell_escape, std::vector<std::string>* out) const;
+
   const Rule* rule_;
   Pool* pool_;
   std::vector<Node*> inputs_;
   std::vector<Node*> outputs_;
+  std::vector<Node*> validations_;
   Node* dyndep_;
   BindingEnv* env_;
   VisitMark mark_;
+  size_t id_;
   bool outputs_ready_;
   bool deps_loaded_;
   bool deps_missing_;
+  bool generated_by_dep_loader_;
 
   const Rule& rule() const { return *rule_; }
   Pool* pool() const { return pool_; }
@@ -218,6 +250,13 @@
   bool maybe_phonycycle_diagnostic() const;
 };
 
+struct EdgeCmp {
+  bool operator()(const Edge* a, const Edge* b) const {
+    return a->id_ < b->id_;
+  }
+};
+
+typedef std::set<Edge*, EdgeCmp> EdgeSet;
 
 /// ImplicitDepLoader loads implicit dependencies, as referenced via the
 /// "depfile" attribute in build files.
@@ -237,7 +276,13 @@
     return deps_log_;
   }
 
- private:
+ protected:
+  /// Process loaded implicit dependencies for \a edge and update the graph
+  /// @return false on error (without filling \a err if info is just missing)
+  virtual bool ProcessDepfileDeps(Edge* edge,
+                                  std::vector<StringPiece>* depfile_ins,
+                                  std::string* err);
+
   /// Load implicit dependencies for \a edge from a depfile attribute.
   /// @return false on error (without filling \a err if info is just missing).
   bool LoadDepFile(Edge* edge, const std::string& path, std::string* err);
@@ -273,12 +318,14 @@
         dep_loader_(state, deps_log, disk_interface, depfile_parser_options),
         dyndep_loader_(state, disk_interface) {}
 
-  /// Update the |dirty_| state of the given node by inspecting its input edge.
+  /// Update the |dirty_| state of the given nodes by transitively inspecting
+  /// their input edges.
   /// Examine inputs, outputs, and command lines to judge whether an edge
   /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
   /// state accordingly.
+  /// Appends any validation nodes found to the nodes parameter.
   /// Returns false on failure.
-  bool RecomputeDirty(Node* node, std::string* err);
+  bool RecomputeDirty(Node* node, std::vector<Node*>* validation_nodes, std::string* err);
 
   /// Recompute whether any output of the edge is dirty, if so sets |*dirty|.
   /// Returns false on failure.
@@ -304,7 +351,8 @@
   bool LoadDyndeps(Node* node, DyndepFile* ddf, std::string* err) const;
 
  private:
-  bool RecomputeDirty(Node* node, std::vector<Node*>* stack, std::string* err);
+  bool RecomputeNodeDirty(Node* node, std::vector<Node*>* stack,
+                          std::vector<Node*>* validation_nodes, std::string* err);
   bool VerifyDAG(Node* node, std::vector<Node*>* stack, std::string* err);
 
   /// Recompute whether a given single output should be marked dirty.
diff --git a/src/graph_test.cc b/src/graph_test.cc
index 14f6375..9dba8af 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -33,7 +33,7 @@
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   // A missing implicit dep *should* make the output dirty.
@@ -51,7 +51,7 @@
   fs_.Create("implicit", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   // A modified implicit dep should make the output dirty.
@@ -71,7 +71,7 @@
   fs_.Create("implicit.h", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   // implicit.h has changed, though our depfile refers to it with a
@@ -94,7 +94,7 @@
   fs_.Create("data", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   // We have both an implicit and an explicit dep on implicit.h.
@@ -122,7 +122,7 @@
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -138,7 +138,7 @@
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -162,7 +162,7 @@
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -176,7 +176,7 @@
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -193,7 +193,7 @@
   fs_.Create("out.o", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -215,6 +215,39 @@
   }
 }
 
+TEST_F(GraphTest, CollectInputs) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+      &state_,
+      "build out$ 1: cat in1 in2 in$ with$ space | implicit || order_only\n"));
+
+  std::vector<std::string> inputs;
+  Edge* edge = GetNode("out 1")->in_edge();
+
+  // Test without shell escaping.
+  inputs.clear();
+  edge->CollectInputs(false, &inputs);
+  EXPECT_EQ(5u, inputs.size());
+  EXPECT_EQ("in1", inputs[0]);
+  EXPECT_EQ("in2", inputs[1]);
+  EXPECT_EQ("in with space", inputs[2]);
+  EXPECT_EQ("implicit", inputs[3]);
+  EXPECT_EQ("order_only", inputs[4]);
+
+  // Test with shell escaping.
+  inputs.clear();
+  edge->CollectInputs(true, &inputs);
+  EXPECT_EQ(5u, inputs.size());
+  EXPECT_EQ("in1", inputs[0]);
+  EXPECT_EQ("in2", inputs[1]);
+#ifdef _WIN32
+  EXPECT_EQ("\"in with space\"", inputs[2]);
+#else
+  EXPECT_EQ("'in with space'", inputs[2]);
+#endif
+  EXPECT_EQ("implicit", inputs[3]);
+  EXPECT_EQ("order_only", inputs[4]);
+}
+
 TEST_F(GraphTest, VarInOutPathEscaping) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build a$ b: cat no'space with$ space$$ no\"space2\n"));
@@ -241,7 +274,7 @@
   fs_.Create("out.o", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -261,13 +294,13 @@
   fs_.Create("out.o", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
   EXPECT_FALSE(GetNode("out.o")->dirty());
 
   state_.Reset();
   fs_.RemoveFile("out.o.d");
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(GetNode("out.o")->dirty());
 }
@@ -314,7 +347,7 @@
 "build n2: phony n1\n"
   );
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), NULL, &err));
   ASSERT_EQ("", err);
 
   Plan plan_;
@@ -333,7 +366,7 @@
   parser_opts);
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> a [-w phonycycle=err]", err);
 }
 
@@ -345,7 +378,7 @@
 "build pre: cat out\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
 }
 
@@ -353,7 +386,7 @@
   string err;
   AssertParse(&state_,
 "build a b: cat a\n");
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> a", err);
 }
 
@@ -361,7 +394,7 @@
   string err;
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build b a: cat a\n"));
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> a", err);
 }
 
@@ -370,7 +403,7 @@
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build a b: cat c\n"
 "build c: cat a\n"));
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> c -> a", err);
 }
 
@@ -382,7 +415,7 @@
 "build b: cat a\n"
 "build a e: cat d\n"
 "build f: cat e\n"));
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> d -> c -> b -> a", err);
 }
 
@@ -398,7 +431,7 @@
   fs_.Create("dep.d", "a: b\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), NULL, &err));
   ASSERT_EQ("dependency cycle: b -> b", err);
 
   // Despite the depfile causing edge to be a cycle (it has outputs a and b,
@@ -423,7 +456,7 @@
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), NULL, &err));
   ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
@@ -450,7 +483,7 @@
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), NULL, &err));
   ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
@@ -511,6 +544,37 @@
   EXPECT_FALSE(edge->GetBindingBool("restat"));
 }
 
+TEST_F(GraphTest, DyndepLoadImplicit) {
+  AssertParse(&state_,
+"rule r\n"
+"  command = unused\n"
+"build out1: r in || dd\n"
+"  dyndep = dd\n"
+"build out2: r in\n"
+  );
+  fs_.Create("dd",
+"ninja_dyndep_version = 1\n"
+"build out1: dyndep | out2\n"
+  );
+
+  string err;
+  ASSERT_TRUE(GetNode("dd")->dyndep_pending());
+  EXPECT_TRUE(scan_.LoadDyndeps(GetNode("dd"), &err));
+  EXPECT_EQ("", err);
+  EXPECT_FALSE(GetNode("dd")->dyndep_pending());
+
+  Edge* edge = GetNode("out1")->in_edge();
+  ASSERT_EQ(1u, edge->outputs_.size());
+  EXPECT_EQ("out1", edge->outputs_[0]->path());
+  ASSERT_EQ(3u, edge->inputs_.size());
+  EXPECT_EQ("in", edge->inputs_[0]->path());
+  EXPECT_EQ("out2", edge->inputs_[1]->path());
+  EXPECT_EQ("dd", edge->inputs_[2]->path());
+  EXPECT_EQ(1u, edge->implicit_deps_);
+  EXPECT_EQ(1u, edge->order_only_deps_);
+  EXPECT_FALSE(edge->GetBindingBool("restat"));
+}
+
 TEST_F(GraphTest, DyndepLoadMissingFile) {
   AssertParse(&state_,
 "rule r\n"
@@ -674,7 +738,7 @@
   );
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("loading 'dd': No such file or directory", err);
 }
 
@@ -690,7 +754,7 @@
   );
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("'out' not mentioned in its dyndep file 'dd'", err);
 }
 
@@ -710,7 +774,7 @@
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("in")->dirty());
@@ -738,7 +802,7 @@
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("in")->dirty());
@@ -763,7 +827,7 @@
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("dd")->dirty());
@@ -789,7 +853,7 @@
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("dd")->dirty());
@@ -817,7 +881,7 @@
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("dd1")->dirty());
@@ -846,7 +910,7 @@
 
   Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   EXPECT_EQ("dependency cycle: circ -> in -> circ", err);
 
   // Verify that "out.d" was loaded exactly once despite
@@ -858,3 +922,58 @@
   EXPECT_EQ(1u, edge->implicit_deps_);
   EXPECT_EQ(1u, edge->order_only_deps_);
 }
+
+TEST_F(GraphTest, Validation) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"build out: cat in |@ validate\n"
+"build validate: cat in\n"));
+
+  fs_.Create("in", "");
+  string err;
+  std::vector<Node*> validation_nodes;
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &validation_nodes, &err));
+  ASSERT_EQ("", err);
+
+  ASSERT_EQ(validation_nodes.size(), 1);
+  EXPECT_EQ(validation_nodes[0]->path(), "validate");
+
+  EXPECT_TRUE(GetNode("out")->dirty());
+  EXPECT_TRUE(GetNode("validate")->dirty());
+}
+
+// Check that phony's dependencies' mtimes are propagated.
+TEST_F(GraphTest, PhonyDepsMtimes) {
+  string err;
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+" command = touch $out\n"
+"build in_ph: phony in1\n"
+"build out1: touch in_ph\n"
+));
+  fs_.Create("in1", "");
+  fs_.Create("out1", "");
+  Node* out1 = GetNode("out1");
+  Node* in1  = GetNode("in1");
+
+  EXPECT_TRUE(scan_.RecomputeDirty(out1, NULL, &err));
+  EXPECT_TRUE(!out1->dirty());
+
+  // Get the mtime of out1
+  ASSERT_TRUE(in1->Stat(&fs_, &err));
+  ASSERT_TRUE(out1->Stat(&fs_, &err));
+  TimeStamp out1Mtime1 = out1->mtime();
+  TimeStamp in1Mtime1 = in1->mtime();
+
+  // Touch in1. This should cause out1 to be dirty
+  state_.Reset();
+  fs_.Tick();
+  fs_.Create("in1", "");
+
+  ASSERT_TRUE(in1->Stat(&fs_, &err));
+  EXPECT_GT(in1->mtime(), in1Mtime1);
+
+  EXPECT_TRUE(scan_.RecomputeDirty(out1, NULL, &err));
+  EXPECT_GT(in1->mtime(), in1Mtime1);
+  EXPECT_EQ(out1->mtime(), out1Mtime1);
+  EXPECT_TRUE(out1->dirty());
+}
diff --git a/src/graphviz.h b/src/graphviz.h
index 601c9b2..3a3282e 100644
--- a/src/graphviz.h
+++ b/src/graphviz.h
@@ -18,6 +18,7 @@
 #include <set>
 
 #include "dyndep.h"
+#include "graph.h"
 
 struct DiskInterface;
 struct Node;
@@ -34,7 +35,7 @@
 
   DyndepLoader dyndep_loader_;
   std::set<Node*> visited_nodes_;
-  std::set<Edge*> visited_edges_;
+  EdgeSet visited_edges_;
 };
 
 #endif  // NINJA_GRAPHVIZ_H_
diff --git a/src/includes_normalize-win32.cc b/src/includes_normalize-win32.cc
index 9f8dfc2..081e364 100644
--- a/src/includes_normalize-win32.cc
+++ b/src/includes_normalize-win32.cc
@@ -48,7 +48,7 @@
 }
 
 // Return true if paths a and b are on the same windows drive.
-// Return false if this funcation cannot check
+// Return false if this function cannot check
 // whether or not on the same windows drive.
 bool SameDriveFast(StringPiece a, StringPiece b) {
   if (a.size() < 3 || b.size() < 3) {
@@ -191,8 +191,7 @@
   }
   strncpy(copy, input.c_str(), input.size() + 1);
   uint64_t slash_bits;
-  if (!CanonicalizePath(copy, &len, &slash_bits, err))
-    return false;
+  CanonicalizePath(copy, &len, &slash_bits);
   StringPiece partially_fixed(copy, len);
   string abs_input = AbsPath(partially_fixed, err);
   if (!err->empty())
diff --git a/src/json.cc b/src/json.cc
new file mode 100644
index 0000000..4bbf6e1
--- /dev/null
+++ b/src/json.cc
@@ -0,0 +1,53 @@
+// Copyright 2021 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 "json.h"
+
+#include <cstdio>
+#include <string>
+
+std::string EncodeJSONString(const std::string& in) {
+  static const char* hex_digits = "0123456789abcdef";
+  std::string out;
+  out.reserve(in.length() * 1.2);
+  for (std::string::const_iterator it = in.begin(); it != in.end(); ++it) {
+    char c = *it;
+    if (c == '\b')
+      out += "\\b";
+    else if (c == '\f')
+      out += "\\f";
+    else if (c == '\n')
+      out += "\\n";
+    else if (c == '\r')
+      out += "\\r";
+    else if (c == '\t')
+      out += "\\t";
+    else if (0x0 <= c && c < 0x20) {
+      out += "\\u00";
+      out += hex_digits[c >> 4];
+      out += hex_digits[c & 0xf];
+    } else if (c == '\\')
+      out += "\\\\";
+    else if (c == '\"')
+      out += "\\\"";
+    else
+      out += c;
+  }
+  return out;
+}
+
+void PrintJSONString(const std::string& in) {
+  std::string out = EncodeJSONString(in);
+  fwrite(out.c_str(), 1, out.length(), stdout);
+}
diff --git a/src/json.h b/src/json.h
new file mode 100644
index 0000000..f39c759
--- /dev/null
+++ b/src/json.h
@@ -0,0 +1,26 @@
+// Copyright 2021 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_JSON_H_
+#define NINJA_JSON_H_
+
+#include <string>
+
+// Encode a string in JSON format without encolsing quotes
+std::string EncodeJSONString(const std::string& in);
+
+// Print a string in JSON format to stdout without enclosing quotes
+void PrintJSONString(const std::string& in);
+
+#endif
diff --git a/src/json_test.cc b/src/json_test.cc
new file mode 100644
index 0000000..b4afc73
--- /dev/null
+++ b/src/json_test.cc
@@ -0,0 +1,40 @@
+// Copyright 2021 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 "json.h"
+
+#include "test.h"
+
+TEST(JSONTest, RegularAscii) {
+  EXPECT_EQ(EncodeJSONString("foo bar"), "foo bar");
+}
+
+TEST(JSONTest, EscapedChars) {
+  EXPECT_EQ(EncodeJSONString("\"\\\b\f\n\r\t"),
+            "\\\""
+            "\\\\"
+            "\\b\\f\\n\\r\\t");
+}
+
+// codepoints between 0 and 0x1f should be escaped
+TEST(JSONTest, ControlChars) {
+  EXPECT_EQ(EncodeJSONString("\x01\x1f"), "\\u0001\\u001f");
+}
+
+// Leave them alone as JSON accepts unicode literals
+// out of control character range
+TEST(JSONTest, UTF8) {
+  const char* utf8str = "\xe4\xbd\xa0\xe5\xa5\xbd";
+  EXPECT_EQ(EncodeJSONString(utf8str), utf8str);
+}
diff --git a/src/lexer.cc b/src/lexer.cc
index 6e4a470..e5729f0 100644
--- a/src/lexer.cc
+++ b/src/lexer.cc
@@ -1,4 +1,4 @@
-/* Generated by re2c 1.1.1 */
+/* Generated by re2c */
 // Copyright 2011 Google Inc. All Rights Reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
@@ -85,6 +85,7 @@
   case NEWLINE:  return "newline";
   case PIPE2:    return "'||'";
   case PIPE:     return "'|'";
+  case PIPEAT:   return "'|@'";
   case POOL:     return "'pool'";
   case RULE:     return "'rule'";
   case SUBNINJA: return "'subninja'";
@@ -291,7 +292,8 @@
 	goto yy14;
 yy26:
 	yych = *++p;
-	if (yych == '|') goto yy42;
+	if (yych == '@') goto yy42;
+	if (yych == '|') goto yy44;
 	{ token = PIPE;     break; }
 yy28:
 	++p;
@@ -317,127 +319,130 @@
 	{ continue; }
 yy36:
 	yych = *++p;
-	if (yych == 'i') goto yy44;
+	if (yych == 'i') goto yy46;
 	goto yy14;
 yy37:
 	yych = *++p;
-	if (yych == 'f') goto yy45;
+	if (yych == 'f') goto yy47;
 	goto yy14;
 yy38:
 	yych = *++p;
-	if (yych == 'c') goto yy46;
+	if (yych == 'c') goto yy48;
 	goto yy14;
 yy39:
 	yych = *++p;
-	if (yych == 'o') goto yy47;
+	if (yych == 'o') goto yy49;
 	goto yy14;
 yy40:
 	yych = *++p;
-	if (yych == 'l') goto yy48;
+	if (yych == 'l') goto yy50;
 	goto yy14;
 yy41:
 	yych = *++p;
-	if (yych == 'b') goto yy49;
+	if (yych == 'b') goto yy51;
 	goto yy14;
 yy42:
 	++p;
-	{ token = PIPE2;    break; }
+	{ token = PIPEAT;   break; }
 yy44:
-	yych = *++p;
-	if (yych == 'l') goto yy50;
-	goto yy14;
-yy45:
-	yych = *++p;
-	if (yych == 'a') goto yy51;
-	goto yy14;
+	++p;
+	{ token = PIPE2;    break; }
 yy46:
 	yych = *++p;
 	if (yych == 'l') goto yy52;
 	goto yy14;
 yy47:
 	yych = *++p;
-	if (yych == 'l') goto yy53;
+	if (yych == 'a') goto yy53;
 	goto yy14;
 yy48:
 	yych = *++p;
-	if (yych == 'e') goto yy55;
+	if (yych == 'l') goto yy54;
 	goto yy14;
 yy49:
 	yych = *++p;
-	if (yych == 'n') goto yy57;
+	if (yych == 'l') goto yy55;
 	goto yy14;
 yy50:
 	yych = *++p;
-	if (yych == 'd') goto yy58;
+	if (yych == 'e') goto yy57;
 	goto yy14;
 yy51:
 	yych = *++p;
-	if (yych == 'u') goto yy60;
+	if (yych == 'n') goto yy59;
 	goto yy14;
 yy52:
 	yych = *++p;
-	if (yych == 'u') goto yy61;
+	if (yych == 'd') goto yy60;
 	goto yy14;
 yy53:
 	yych = *++p;
-	if (yybm[0+yych] & 64) {
-		goto yy13;
-	}
-	{ token = POOL;     break; }
+	if (yych == 'u') goto yy62;
+	goto yy14;
+yy54:
+	yych = *++p;
+	if (yych == 'u') goto yy63;
+	goto yy14;
 yy55:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
-	{ token = RULE;     break; }
+	{ token = POOL;     break; }
 yy57:
 	yych = *++p;
-	if (yych == 'i') goto yy62;
+	if (yybm[0+yych] & 64) {
+		goto yy13;
+	}
+	{ token = RULE;     break; }
+yy59:
+	yych = *++p;
+	if (yych == 'i') goto yy64;
 	goto yy14;
-yy58:
+yy60:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = BUILD;    break; }
-yy60:
-	yych = *++p;
-	if (yych == 'l') goto yy63;
-	goto yy14;
-yy61:
-	yych = *++p;
-	if (yych == 'd') goto yy64;
-	goto yy14;
 yy62:
 	yych = *++p;
-	if (yych == 'n') goto yy65;
+	if (yych == 'l') goto yy65;
 	goto yy14;
 yy63:
 	yych = *++p;
-	if (yych == 't') goto yy66;
+	if (yych == 'd') goto yy66;
 	goto yy14;
 yy64:
 	yych = *++p;
-	if (yych == 'e') goto yy68;
+	if (yych == 'n') goto yy67;
 	goto yy14;
 yy65:
 	yych = *++p;
-	if (yych == 'j') goto yy70;
+	if (yych == 't') goto yy68;
 	goto yy14;
 yy66:
 	yych = *++p;
-	if (yybm[0+yych] & 64) {
-		goto yy13;
-	}
-	{ token = DEFAULT;  break; }
+	if (yych == 'e') goto yy70;
+	goto yy14;
+yy67:
+	yych = *++p;
+	if (yych == 'j') goto yy72;
+	goto yy14;
 yy68:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
-	{ token = INCLUDE;  break; }
+	{ token = DEFAULT;  break; }
 yy70:
 	yych = *++p;
+	if (yybm[0+yych] & 64) {
+		goto yy13;
+	}
+	{ token = INCLUDE;  break; }
+yy72:
+	yych = *++p;
 	if (yych != 'a') goto yy14;
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
@@ -507,38 +512,38 @@
 	};
 	yych = *p;
 	if (yybm[0+yych] & 128) {
-		goto yy79;
+		goto yy81;
 	}
-	if (yych <= 0x00) goto yy75;
-	if (yych == '$') goto yy82;
-	goto yy77;
-yy75:
-	++p;
-	{ break; }
+	if (yych <= 0x00) goto yy77;
+	if (yych == '$') goto yy84;
+	goto yy79;
 yy77:
 	++p;
-yy78:
 	{ break; }
 yy79:
+	++p;
+yy80:
+	{ break; }
+yy81:
 	yych = *++p;
 	if (yybm[0+yych] & 128) {
-		goto yy79;
+		goto yy81;
 	}
 	{ continue; }
-yy82:
+yy84:
 	yych = *(q = ++p);
-	if (yych == '\n') goto yy83;
-	if (yych == '\r') goto yy85;
-	goto yy78;
-yy83:
+	if (yych == '\n') goto yy85;
+	if (yych == '\r') goto yy87;
+	goto yy80;
+yy85:
 	++p;
 	{ continue; }
-yy85:
-	yych = *++p;
-	if (yych == '\n') goto yy87;
-	p = q;
-	goto yy78;
 yy87:
+	yych = *++p;
+	if (yych == '\n') goto yy89;
+	p = q;
+	goto yy80;
+yy89:
 	++p;
 	{ continue; }
 }
@@ -590,17 +595,17 @@
 	};
 	yych = *p;
 	if (yybm[0+yych] & 128) {
-		goto yy93;
+		goto yy95;
 	}
 	++p;
 	{
       last_token_ = start;
       return false;
     }
-yy93:
+yy95:
 	yych = *++p;
 	if (yybm[0+yych] & 128) {
-		goto yy93;
+		goto yy95;
 	}
 	{
       out->assign(start, p - start);
@@ -660,33 +665,33 @@
 	};
 	yych = *p;
 	if (yybm[0+yych] & 16) {
-		goto yy100;
+		goto yy102;
 	}
 	if (yych <= '\r') {
-		if (yych <= 0x00) goto yy98;
-		if (yych <= '\n') goto yy103;
-		goto yy105;
+		if (yych <= 0x00) goto yy100;
+		if (yych <= '\n') goto yy105;
+		goto yy107;
 	} else {
-		if (yych <= ' ') goto yy103;
-		if (yych <= '$') goto yy107;
-		goto yy103;
+		if (yych <= ' ') goto yy105;
+		if (yych <= '$') goto yy109;
+		goto yy105;
 	}
-yy98:
+yy100:
 	++p;
 	{
       last_token_ = start;
       return Error("unexpected EOF", err);
     }
-yy100:
+yy102:
 	yych = *++p;
 	if (yybm[0+yych] & 16) {
-		goto yy100;
+		goto yy102;
 	}
 	{
       eval->AddText(StringPiece(start, p - start));
       continue;
     }
-yy103:
+yy105:
 	++p;
 	{
       if (path) {
@@ -699,112 +704,112 @@
         continue;
       }
     }
-yy105:
+yy107:
 	yych = *++p;
-	if (yych == '\n') goto yy108;
+	if (yych == '\n') goto yy110;
 	{
       last_token_ = start;
       return Error(DescribeLastError(), err);
     }
-yy107:
+yy109:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
-		goto yy120;
+		goto yy122;
 	}
 	if (yych <= ' ') {
 		if (yych <= '\f') {
-			if (yych == '\n') goto yy112;
-			goto yy110;
+			if (yych == '\n') goto yy114;
+			goto yy112;
 		} else {
-			if (yych <= '\r') goto yy115;
-			if (yych <= 0x1F) goto yy110;
-			goto yy116;
+			if (yych <= '\r') goto yy117;
+			if (yych <= 0x1F) goto yy112;
+			goto yy118;
 		}
 	} else {
 		if (yych <= '/') {
-			if (yych == '$') goto yy118;
-			goto yy110;
+			if (yych == '$') goto yy120;
+			goto yy112;
 		} else {
-			if (yych <= ':') goto yy123;
-			if (yych <= '`') goto yy110;
-			if (yych <= '{') goto yy125;
-			goto yy110;
+			if (yych <= ':') goto yy125;
+			if (yych <= '`') goto yy112;
+			if (yych <= '{') goto yy127;
+			goto yy112;
 		}
 	}
-yy108:
+yy110:
 	++p;
 	{
       if (path)
         p = start;
       break;
     }
-yy110:
+yy112:
 	++p;
-yy111:
+yy113:
 	{
       last_token_ = start;
       return Error("bad $-escape (literal $ must be written as $$)", err);
     }
-yy112:
+yy114:
 	yych = *++p;
 	if (yybm[0+yych] & 32) {
-		goto yy112;
+		goto yy114;
 	}
 	{
       continue;
     }
-yy115:
+yy117:
 	yych = *++p;
-	if (yych == '\n') goto yy126;
-	goto yy111;
-yy116:
+	if (yych == '\n') goto yy128;
+	goto yy113;
+yy118:
 	++p;
 	{
       eval->AddText(StringPiece(" ", 1));
       continue;
     }
-yy118:
+yy120:
 	++p;
 	{
       eval->AddText(StringPiece("$", 1));
       continue;
     }
-yy120:
+yy122:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
-		goto yy120;
+		goto yy122;
 	}
 	{
       eval->AddSpecial(StringPiece(start + 1, p - start - 1));
       continue;
     }
-yy123:
+yy125:
 	++p;
 	{
       eval->AddText(StringPiece(":", 1));
       continue;
     }
-yy125:
+yy127:
 	yych = *(q = ++p);
 	if (yybm[0+yych] & 128) {
-		goto yy129;
+		goto yy131;
 	}
-	goto yy111;
-yy126:
+	goto yy113;
+yy128:
 	yych = *++p;
-	if (yych == ' ') goto yy126;
+	if (yych == ' ') goto yy128;
 	{
       continue;
     }
-yy129:
+yy131:
 	yych = *++p;
 	if (yybm[0+yych] & 128) {
-		goto yy129;
+		goto yy131;
 	}
-	if (yych == '}') goto yy132;
+	if (yych == '}') goto yy134;
 	p = q;
-	goto yy111;
-yy132:
+	goto yy113;
+yy134:
 	++p;
 	{
       eval->AddSpecial(StringPiece(start + 2, p - start - 3));
diff --git a/src/lexer.h b/src/lexer.h
index 788d948..683fd6c 100644
--- a/src/lexer.h
+++ b/src/lexer.h
@@ -41,6 +41,7 @@
     NEWLINE,
     PIPE,
     PIPE2,
+    PIPEAT,
     POOL,
     RULE,
     SUBNINJA,
diff --git a/src/lexer.in.cc b/src/lexer.in.cc
index 88007e7..6f1d8e7 100644
--- a/src/lexer.in.cc
+++ b/src/lexer.in.cc
@@ -84,6 +84,7 @@
   case NEWLINE:  return "newline";
   case PIPE2:    return "'||'";
   case PIPE:     return "'|'";
+  case PIPEAT:   return "'|@'";
   case POOL:     return "'pool'";
   case RULE:     return "'rule'";
   case SUBNINJA: return "'subninja'";
@@ -142,6 +143,7 @@
     "default"  { token = DEFAULT;  break; }
     "="        { token = EQUALS;   break; }
     ":"        { token = COLON;    break; }
+    "|@"       { token = PIPEAT;   break; }
     "||"       { token = PIPE2;    break; }
     "|"        { token = PIPE;     break; }
     "include"  { token = INCLUDE;  break; }
diff --git a/src/line_printer.cc b/src/line_printer.cc
index 68c58ad..a3d0528 100644
--- a/src/line_printer.cc
+++ b/src/line_printer.cc
@@ -37,14 +37,9 @@
 #ifndef _WIN32
   smart_terminal_ = isatty(1) && term && string(term) != "dumb";
 #else
-  // Disable output buffer.  It'd be nice to use line buffering but
-  // MSDN says: "For some systems, [_IOLBF] provides line
-  // buffering. However, for Win32, the behavior is the same as _IOFBF
-  // - Full Buffering."
   if (term && string(term) == "dumb") {
     smart_terminal_ = false;
   } else {
-    setvbuf(stdout, NULL, _IONBF, 0);
     console_ = GetStdHandle(STD_OUTPUT_HANDLE);
     CONSOLE_SCREEN_BUFFER_INFO csbi;
     smart_terminal_ = GetConsoleScreenBufferInfo(console_, &csbi);
@@ -87,22 +82,27 @@
     GetConsoleScreenBufferInfo(console_, &csbi);
 
     to_print = ElideMiddle(to_print, static_cast<size_t>(csbi.dwSize.X));
-    // We don't want to have the cursor spamming back and forth, so instead of
-    // printf use WriteConsoleOutput which updates the contents of the buffer,
-    // but doesn't move the cursor position.
-    COORD buf_size = { csbi.dwSize.X, 1 };
-    COORD zero_zero = { 0, 0 };
-    SMALL_RECT target = {
-      csbi.dwCursorPosition.X, csbi.dwCursorPosition.Y,
-      static_cast<SHORT>(csbi.dwCursorPosition.X + csbi.dwSize.X - 1),
-      csbi.dwCursorPosition.Y
-    };
-    vector<CHAR_INFO> char_data(csbi.dwSize.X);
-    for (size_t i = 0; i < static_cast<size_t>(csbi.dwSize.X); ++i) {
-      char_data[i].Char.AsciiChar = i < to_print.size() ? to_print[i] : ' ';
-      char_data[i].Attributes = csbi.wAttributes;
+    if (supports_color_) {  // this means ENABLE_VIRTUAL_TERMINAL_PROCESSING
+                            // succeeded
+      printf("%s\x1B[K", to_print.c_str());  // Clear to end of line.
+      fflush(stdout);
+    } else {
+      // We don't want to have the cursor spamming back and forth, so instead of
+      // printf use WriteConsoleOutput which updates the contents of the buffer,
+      // but doesn't move the cursor position.
+      COORD buf_size = { csbi.dwSize.X, 1 };
+      COORD zero_zero = { 0, 0 };
+      SMALL_RECT target = { csbi.dwCursorPosition.X, csbi.dwCursorPosition.Y,
+                            static_cast<SHORT>(csbi.dwCursorPosition.X +
+                                               csbi.dwSize.X - 1),
+                            csbi.dwCursorPosition.Y };
+      vector<CHAR_INFO> char_data(csbi.dwSize.X);
+      for (size_t i = 0; i < static_cast<size_t>(csbi.dwSize.X); ++i) {
+        char_data[i].Char.AsciiChar = i < to_print.size() ? to_print[i] : ' ';
+        char_data[i].Attributes = csbi.wAttributes;
+      }
+      WriteConsoleOutput(console_, &char_data[0], buf_size, zero_zero, &target);
     }
-    WriteConsoleOutput(console_, &char_data[0], buf_size, zero_zero, &target);
 #else
     // Limit output to width of the terminal if provided so we don't cause
     // line-wrapping.
diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc
index 860a8fc..8db6eb3 100644
--- a/src/manifest_parser.cc
+++ b/src/manifest_parser.cc
@@ -190,26 +190,24 @@
 
   do {
     string path = eval.Evaluate(env_);
-    string path_err;
+    if (path.empty())
+      return lexer_.Error("empty path", err);
     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))
-      return lexer_.Error(path_err, err);
+    CanonicalizePath(&path, &slash_bits);
+    std::string default_err;
+    if (!state_->AddDefault(path, &default_err))
+      return lexer_.Error(default_err, err);
 
     eval.Clear();
     if (!lexer_.ReadPath(&eval, err))
       return false;
   } while (!eval.empty());
 
-  if (!ExpectToken(Lexer::NEWLINE, err))
-    return false;
-
-  return true;
+  return ExpectToken(Lexer::NEWLINE, err);
 }
 
 bool ManifestParser::ParseEdge(string* err) {
-  vector<EvalString> ins, outs;
+  vector<EvalString> ins, outs, validations;
 
   {
     EvalString out;
@@ -290,6 +288,18 @@
     }
   }
 
+  // Add all validations, counting how many as we go.
+  if (lexer_.PeekToken(Lexer::PIPEAT)) {
+    for (;;) {
+      EvalString validation;
+      if (!lexer_.ReadPath(&validation, err))
+        return false;
+      if (validation.empty())
+        break;
+      validations.push_back(validation);
+    }
+  }
+
   if (!ExpectToken(Lexer::NEWLINE, err))
     return false;
 
@@ -320,27 +330,27 @@
   edge->outputs_.reserve(outs.size());
   for (size_t i = 0, e = outs.size(); i != e; ++i) {
     string path = outs[i].Evaluate(env);
-    string path_err;
+    if (path.empty())
+      return lexer_.Error("empty path", err);
     uint64_t slash_bits;
-    if (!CanonicalizePath(&path, &slash_bits, &path_err))
-      return lexer_.Error(path_err, err);
+    CanonicalizePath(&path, &slash_bits);
     if (!state_->AddOut(edge, path, slash_bits)) {
       if (options_.dupe_edge_action_ == kDupeEdgeActionError) {
-        lexer_.Error("multiple rules generate " + path + " [-w dupbuild=err]",
-                     err);
+        lexer_.Error("multiple rules generate " + path, err);
         return false;
       } else {
         if (!quiet_) {
-          Warning("multiple rules generate %s. "
-                  "builds involving this target will not be correct; "
-                  "continuing anyway [-w dupbuild=warn]",
-                  path.c_str());
+          Warning(
+              "multiple rules generate %s. builds involving this target will "
+              "not be correct; continuing anyway",
+              path.c_str());
         }
         if (e - i <= static_cast<size_t>(implicit_outs))
           --implicit_outs;
       }
     }
   }
+
   if (edge->outputs_.empty()) {
     // All outputs of the edge are already created by other edges. Don't add
     // this edge.  Do this check before input nodes are connected to the edge.
@@ -353,15 +363,26 @@
   edge->inputs_.reserve(ins.size());
   for (vector<EvalString>::iterator i = ins.begin(); i != ins.end(); ++i) {
     string path = i->Evaluate(env);
-    string path_err;
+    if (path.empty())
+      return lexer_.Error("empty path", err);
     uint64_t slash_bits;
-    if (!CanonicalizePath(&path, &slash_bits, &path_err))
-      return lexer_.Error(path_err, err);
+    CanonicalizePath(&path, &slash_bits);
     state_->AddIn(edge, path, slash_bits);
   }
   edge->implicit_deps_ = implicit;
   edge->order_only_deps_ = order_only;
 
+  edge->validations_.reserve(validations.size());
+  for (std::vector<EvalString>::iterator v = validations.begin();
+      v != validations.end(); ++v) {
+    string path = v->Evaluate(env);
+    if (path.empty())
+      return lexer_.Error("empty path", err);
+    uint64_t slash_bits;
+    CanonicalizePath(&path, &slash_bits);
+    state_->AddValidation(edge, path, slash_bits);
+  }
+
   if (options_.phony_cycle_action_ == kPhonyCycleActionWarn &&
       edge->maybe_phonycycle_diagnostic()) {
     // CMake 2.8.12.x and 3.0.x incorrectly write phony build statements
@@ -387,8 +408,7 @@
   string dyndep = edge->GetUnescapedDyndep();
   if (!dyndep.empty()) {
     uint64_t slash_bits;
-    if (!CanonicalizePath(&dyndep, &slash_bits, err))
-      return false;
+    CanonicalizePath(&dyndep, &slash_bits);
     edge->dyndep_ = state_->GetNode(dyndep, slash_bits);
     edge->dyndep_->set_dyndep_pending(true);
     vector<Node*>::iterator dgi =
diff --git a/src/manifest_parser_test.cc b/src/manifest_parser_test.cc
index ec2eeed..66b72e2 100644
--- a/src/manifest_parser_test.cc
+++ b/src/manifest_parser_test.cc
@@ -365,7 +365,7 @@
   ManifestParser parser(&state, &fs_, parser_opts);
   string err;
   EXPECT_FALSE(parser.ParseTest(kInput, &err));
-  EXPECT_EQ("input:5: multiple rules generate out1 [-w dupbuild=err]\n", err);
+  EXPECT_EQ("input:5: multiple rules generate out1\n", err);
 }
 
 TEST_F(ParserTest, DuplicateEdgeInIncludedFile) {
@@ -382,8 +382,7 @@
   ManifestParser parser(&state, &fs_, parser_opts);
   string err;
   EXPECT_FALSE(parser.ParseTest(kInput, &err));
-  EXPECT_EQ("sub.ninja:5: multiple rules generate out1 [-w dupbuild=err]\n",
-            err);
+  EXPECT_EQ("sub.ninja:5: multiple rules generate out1\n", err);
 }
 
 TEST_F(ParserTest, PhonySelfReferenceIgnored) {
@@ -966,6 +965,16 @@
   ASSERT_TRUE(edge->is_order_only(1));
 }
 
+TEST_F(ParserTest, Validations) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"rule cat\n  command = cat $in > $out\n"
+"build foo: cat bar |@ baz\n"));
+
+  Edge* edge = state.LookupNode("foo")->in_edge();
+  ASSERT_EQ(edge->validations_.size(), 1);
+  EXPECT_EQ(edge->validations_[0]->path(), "baz");
+}
+
 TEST_F(ParserTest, ImplicitOutput) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(
 "rule cat\n"
diff --git a/src/missing_deps.cc b/src/missing_deps.cc
new file mode 100644
index 0000000..de76620
--- /dev/null
+++ b/src/missing_deps.cc
@@ -0,0 +1,192 @@
+// Copyright 2019 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 "missing_deps.h"
+
+#include <string.h>
+
+#include <iostream>
+
+#include "depfile_parser.h"
+#include "deps_log.h"
+#include "disk_interface.h"
+#include "graph.h"
+#include "state.h"
+#include "util.h"
+
+namespace {
+
+/// ImplicitDepLoader variant that stores dep nodes into the given output
+/// without updating graph deps like the base loader does.
+struct NodeStoringImplicitDepLoader : public ImplicitDepLoader {
+  NodeStoringImplicitDepLoader(
+      State* state, DepsLog* deps_log, DiskInterface* disk_interface,
+      DepfileParserOptions const* depfile_parser_options,
+      std::vector<Node*>* dep_nodes_output)
+      : ImplicitDepLoader(state, deps_log, disk_interface,
+                          depfile_parser_options),
+        dep_nodes_output_(dep_nodes_output) {}
+
+ protected:
+  virtual bool ProcessDepfileDeps(Edge* edge,
+                                  std::vector<StringPiece>* depfile_ins,
+                                  std::string* err);
+
+ private:
+  std::vector<Node*>* dep_nodes_output_;
+};
+
+bool NodeStoringImplicitDepLoader::ProcessDepfileDeps(
+    Edge* edge, std::vector<StringPiece>* depfile_ins, std::string* err) {
+  for (std::vector<StringPiece>::iterator i = depfile_ins->begin();
+       i != depfile_ins->end(); ++i) {
+    uint64_t slash_bits;
+    CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits);
+    Node* node = state_->GetNode(*i, slash_bits);
+    dep_nodes_output_->push_back(node);
+  }
+  return true;
+}
+
+}  // namespace
+
+MissingDependencyScannerDelegate::~MissingDependencyScannerDelegate() {}
+
+void MissingDependencyPrinter::OnMissingDep(Node* node, const std::string& path,
+                                            const Rule& generator) {
+  std::cout << "Missing dep: " << node->path() << " uses " << path
+            << " (generated by " << generator.name() << ")\n";
+}
+
+MissingDependencyScanner::MissingDependencyScanner(
+    MissingDependencyScannerDelegate* delegate, DepsLog* deps_log, State* state,
+    DiskInterface* disk_interface)
+    : delegate_(delegate), deps_log_(deps_log), state_(state),
+      disk_interface_(disk_interface), missing_dep_path_count_(0) {}
+
+void MissingDependencyScanner::ProcessNode(Node* node) {
+  if (!node)
+    return;
+  Edge* edge = node->in_edge();
+  if (!edge)
+    return;
+  if (!seen_.insert(node).second)
+    return;
+
+  for (std::vector<Node*>::iterator in = edge->inputs_.begin();
+       in != edge->inputs_.end(); ++in) {
+    ProcessNode(*in);
+  }
+
+  std::string deps_type = edge->GetBinding("deps");
+  if (!deps_type.empty()) {
+    DepsLog::Deps* deps = deps_log_->GetDeps(node);
+    if (deps)
+      ProcessNodeDeps(node, deps->nodes, deps->node_count);
+  } else {
+    DepfileParserOptions parser_opts;
+    std::vector<Node*> depfile_deps;
+    NodeStoringImplicitDepLoader dep_loader(state_, deps_log_, disk_interface_,
+                                            &parser_opts, &depfile_deps);
+    std::string err;
+    dep_loader.LoadDeps(edge, &err);
+    if (!depfile_deps.empty())
+      ProcessNodeDeps(node, &depfile_deps[0], depfile_deps.size());
+  }
+}
+
+void MissingDependencyScanner::ProcessNodeDeps(Node* node, Node** dep_nodes,
+                                               int dep_nodes_count) {
+  Edge* edge = node->in_edge();
+  std::set<Edge*> deplog_edges;
+  for (int i = 0; i < dep_nodes_count; ++i) {
+    Node* deplog_node = dep_nodes[i];
+    // Special exception: A dep on build.ninja can be used to mean "always
+    // rebuild this target when the build is reconfigured", but build.ninja is
+    // often generated by a configuration tool like cmake or gn. The rest of
+    // the build "implicitly" depends on the entire build being reconfigured,
+    // so a missing dep path to build.ninja is not an actual missing dependency
+    // problem.
+    if (deplog_node->path() == "build.ninja")
+      return;
+    Edge* deplog_edge = deplog_node->in_edge();
+    if (deplog_edge) {
+      deplog_edges.insert(deplog_edge);
+    }
+  }
+  std::vector<Edge*> missing_deps;
+  for (std::set<Edge*>::iterator de = deplog_edges.begin();
+       de != deplog_edges.end(); ++de) {
+    if (!PathExistsBetween(*de, edge)) {
+      missing_deps.push_back(*de);
+    }
+  }
+
+  if (!missing_deps.empty()) {
+    std::set<std::string> missing_deps_rule_names;
+    for (std::vector<Edge*>::iterator ne = missing_deps.begin();
+         ne != missing_deps.end(); ++ne) {
+      for (int i = 0; i < dep_nodes_count; ++i) {
+        if (dep_nodes[i]->in_edge() == *ne) {
+          generated_nodes_.insert(dep_nodes[i]);
+          generator_rules_.insert(&(*ne)->rule());
+          missing_deps_rule_names.insert((*ne)->rule().name());
+          delegate_->OnMissingDep(node, dep_nodes[i]->path(), (*ne)->rule());
+        }
+      }
+    }
+    missing_dep_path_count_ += missing_deps_rule_names.size();
+    nodes_missing_deps_.insert(node);
+  }
+}
+
+void MissingDependencyScanner::PrintStats() {
+  std::cout << "Processed " << seen_.size() << " nodes.\n";
+  if (HadMissingDeps()) {
+    std::cout << "Error: There are " << missing_dep_path_count_
+              << " missing dependency paths.\n";
+    std::cout << nodes_missing_deps_.size()
+              << " targets had depfile dependencies on "
+              << generated_nodes_.size() << " distinct generated inputs "
+              << "(from " << generator_rules_.size() << " rules) "
+              << " without a non-depfile dep path to the generator.\n";
+    std::cout << "There might be build flakiness if any of the targets listed "
+                 "above are built alone, or not late enough, in a clean output "
+                 "directory.\n";
+  } else {
+    std::cout << "No missing dependencies on generated files found.\n";
+  }
+}
+
+bool MissingDependencyScanner::PathExistsBetween(Edge* from, Edge* to) {
+  AdjacencyMap::iterator it = adjacency_map_.find(from);
+  if (it != adjacency_map_.end()) {
+    InnerAdjacencyMap::iterator inner_it = it->second.find(to);
+    if (inner_it != it->second.end()) {
+      return inner_it->second;
+    }
+  } else {
+    it = adjacency_map_.insert(std::make_pair(from, InnerAdjacencyMap())).first;
+  }
+  bool found = false;
+  for (size_t i = 0; i < to->inputs_.size(); ++i) {
+    Edge* e = to->inputs_[i]->in_edge();
+    if (e && (e == from || PathExistsBetween(from, e))) {
+      found = true;
+      break;
+    }
+  }
+  it->second.insert(std::make_pair(to, found));
+  return found;
+}
diff --git a/src/missing_deps.h b/src/missing_deps.h
new file mode 100644
index 0000000..ae57074
--- /dev/null
+++ b/src/missing_deps.h
@@ -0,0 +1,81 @@
+// Copyright 2019 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_MISSING_DEPS_H_
+#define NINJA_MISSING_DEPS_H_
+
+#include <map>
+#include <set>
+#include <string>
+
+#if __cplusplus >= 201103L
+#include <unordered_map>
+#endif
+
+struct DepsLog;
+struct DiskInterface;
+struct Edge;
+struct Node;
+struct Rule;
+struct State;
+
+class MissingDependencyScannerDelegate {
+ public:
+  virtual ~MissingDependencyScannerDelegate();
+  virtual void OnMissingDep(Node* node, const std::string& path,
+                            const Rule& generator) = 0;
+};
+
+class MissingDependencyPrinter : public MissingDependencyScannerDelegate {
+  void OnMissingDep(Node* node, const std::string& path, const Rule& generator);
+  void OnStats(int nodes_processed, int nodes_missing_deps,
+               int missing_dep_path_count, int generated_nodes,
+               int generator_rules);
+};
+
+struct MissingDependencyScanner {
+ public:
+  MissingDependencyScanner(MissingDependencyScannerDelegate* delegate,
+                           DepsLog* deps_log, State* state,
+                           DiskInterface* disk_interface);
+  void ProcessNode(Node* node);
+  void PrintStats();
+  bool HadMissingDeps() { return !nodes_missing_deps_.empty(); }
+
+  void ProcessNodeDeps(Node* node, Node** dep_nodes, int dep_nodes_count);
+
+  bool PathExistsBetween(Edge* from, Edge* to);
+
+  MissingDependencyScannerDelegate* delegate_;
+  DepsLog* deps_log_;
+  State* state_;
+  DiskInterface* disk_interface_;
+  std::set<Node*> seen_;
+  std::set<Node*> nodes_missing_deps_;
+  std::set<Node*> generated_nodes_;
+  std::set<const Rule*> generator_rules_;
+  int missing_dep_path_count_;
+
+ private:
+#if __cplusplus >= 201103L
+  using InnerAdjacencyMap = std::unordered_map<Edge*, bool>;
+  using AdjacencyMap = std::unordered_map<Edge*, InnerAdjacencyMap>;
+#else
+  typedef std::map<Edge*, bool> InnerAdjacencyMap;
+  typedef std::map<Edge*, InnerAdjacencyMap> AdjacencyMap;
+#endif
+  AdjacencyMap adjacency_map_;
+};
+
+#endif  // NINJA_MISSING_DEPS_H_
diff --git a/src/missing_deps_test.cc b/src/missing_deps_test.cc
new file mode 100644
index 0000000..db66885
--- /dev/null
+++ b/src/missing_deps_test.cc
@@ -0,0 +1,162 @@
+// Copyright 2019 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 <memory>
+
+#include "deps_log.h"
+#include "graph.h"
+#include "missing_deps.h"
+#include "state.h"
+#include "test.h"
+
+const char kTestDepsLogFilename[] = "MissingDepTest-tempdepslog";
+
+class MissingDependencyTestDelegate : public MissingDependencyScannerDelegate {
+  void OnMissingDep(Node* node, const std::string& path,
+                    const Rule& generator) {}
+};
+
+struct MissingDependencyScannerTest : public testing::Test {
+  MissingDependencyScannerTest()
+      : generator_rule_("generator_rule"), compile_rule_("compile_rule"),
+        scanner_(&delegate_, &deps_log_, &state_, &filesystem_) {
+    std::string err;
+    deps_log_.OpenForWrite(kTestDepsLogFilename, &err);
+    ASSERT_EQ("", err);
+  }
+
+  MissingDependencyScanner& scanner() { return scanner_; }
+
+  void RecordDepsLogDep(const std::string& from, const std::string& to) {
+    Node* node_deps[] = { state_.LookupNode(to) };
+    deps_log_.RecordDeps(state_.LookupNode(from), 0, 1, node_deps);
+  }
+
+  void ProcessAllNodes() {
+    std::string err;
+    std::vector<Node*> nodes = state_.RootNodes(&err);
+    EXPECT_EQ("", err);
+    for (std::vector<Node*>::iterator it = nodes.begin(); it != nodes.end();
+         ++it) {
+      scanner().ProcessNode(*it);
+    }
+  }
+
+  void CreateInitialState() {
+    EvalString deps_type;
+    deps_type.AddText("gcc");
+    compile_rule_.AddBinding("deps", deps_type);
+    generator_rule_.AddBinding("deps", deps_type);
+    Edge* header_edge = state_.AddEdge(&generator_rule_);
+    state_.AddOut(header_edge, "generated_header", 0);
+    Edge* compile_edge = state_.AddEdge(&compile_rule_);
+    state_.AddOut(compile_edge, "compiled_object", 0);
+  }
+
+  void CreateGraphDependencyBetween(const char* from, const char* to) {
+    Node* from_node = state_.LookupNode(from);
+    Edge* from_edge = from_node->in_edge();
+    state_.AddIn(from_edge, to, 0);
+  }
+
+  void AssertMissingDependencyBetween(const char* flaky, const char* generated,
+                                      Rule* rule) {
+    Node* flaky_node = state_.LookupNode(flaky);
+    ASSERT_EQ(1u, scanner().nodes_missing_deps_.count(flaky_node));
+    Node* generated_node = state_.LookupNode(generated);
+    ASSERT_EQ(1u, scanner().generated_nodes_.count(generated_node));
+    ASSERT_EQ(1u, scanner().generator_rules_.count(rule));
+  }
+
+  MissingDependencyTestDelegate delegate_;
+  Rule generator_rule_;
+  Rule compile_rule_;
+  DepsLog deps_log_;
+  State state_;
+  VirtualFileSystem filesystem_;
+  MissingDependencyScanner scanner_;
+};
+
+TEST_F(MissingDependencyScannerTest, EmptyGraph) {
+  ProcessAllNodes();
+  ASSERT_FALSE(scanner().HadMissingDeps());
+}
+
+TEST_F(MissingDependencyScannerTest, NoMissingDep) {
+  CreateInitialState();
+  ProcessAllNodes();
+  ASSERT_FALSE(scanner().HadMissingDeps());
+}
+
+TEST_F(MissingDependencyScannerTest, MissingDepPresent) {
+  CreateInitialState();
+  // compiled_object uses generated_header, without a proper dependency
+  RecordDepsLogDep("compiled_object", "generated_header");
+  ProcessAllNodes();
+  ASSERT_TRUE(scanner().HadMissingDeps());
+  ASSERT_EQ(1u, scanner().nodes_missing_deps_.size());
+  ASSERT_EQ(1u, scanner().missing_dep_path_count_);
+  AssertMissingDependencyBetween("compiled_object", "generated_header",
+                                 &generator_rule_);
+}
+
+TEST_F(MissingDependencyScannerTest, MissingDepFixedDirect) {
+  CreateInitialState();
+  // Adding the direct dependency fixes the missing dep
+  CreateGraphDependencyBetween("compiled_object", "generated_header");
+  RecordDepsLogDep("compiled_object", "generated_header");
+  ProcessAllNodes();
+  ASSERT_FALSE(scanner().HadMissingDeps());
+}
+
+TEST_F(MissingDependencyScannerTest, MissingDepFixedIndirect) {
+  CreateInitialState();
+  // Adding an indirect dependency also fixes the issue
+  Edge* intermediate_edge = state_.AddEdge(&generator_rule_);
+  state_.AddOut(intermediate_edge, "intermediate", 0);
+  CreateGraphDependencyBetween("compiled_object", "intermediate");
+  CreateGraphDependencyBetween("intermediate", "generated_header");
+  RecordDepsLogDep("compiled_object", "generated_header");
+  ProcessAllNodes();
+  ASSERT_FALSE(scanner().HadMissingDeps());
+}
+
+TEST_F(MissingDependencyScannerTest, CyclicMissingDep) {
+  CreateInitialState();
+  RecordDepsLogDep("generated_header", "compiled_object");
+  RecordDepsLogDep("compiled_object", "generated_header");
+  // In case of a cycle, both paths are reported (and there is
+  // no way to fix the issue by adding deps).
+  ProcessAllNodes();
+  ASSERT_TRUE(scanner().HadMissingDeps());
+  ASSERT_EQ(2u, scanner().nodes_missing_deps_.size());
+  ASSERT_EQ(2u, scanner().missing_dep_path_count_);
+  AssertMissingDependencyBetween("compiled_object", "generated_header",
+                                 &generator_rule_);
+  AssertMissingDependencyBetween("generated_header", "compiled_object",
+                                 &compile_rule_);
+}
+
+TEST_F(MissingDependencyScannerTest, CycleInGraph) {
+  CreateInitialState();
+  CreateGraphDependencyBetween("compiled_object", "generated_header");
+  CreateGraphDependencyBetween("generated_header", "compiled_object");
+  // The missing-deps tool doesn't deal with cycles in the graph, because
+  // there will be an error loading the graph before we get to the tool.
+  // This test is to illustrate that.
+  std::string err;
+  std::vector<Node*> nodes = state_.RootNodes(&err);
+  ASSERT_NE("", err);
+}
+
diff --git a/src/ninja.cc b/src/ninja.cc
index 471a023..2b71eb1 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -17,6 +17,8 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+
+#include <algorithm>
 #include <cstdlib>
 
 #ifdef _WIN32
@@ -37,18 +39,22 @@
 #include "deps_log.h"
 #include "clean.h"
 #include "debug_flags.h"
+#include "depfile_parser.h"
 #include "disk_interface.h"
 #include "graph.h"
 #include "graphviz.h"
+#include "json.h"
 #include "manifest_parser.h"
 #include "metrics.h"
+#include "missing_deps.h"
 #include "state.h"
+#include "status.h"
 #include "util.h"
 #include "version.h"
 
 using namespace std;
 
-#ifdef _MSC_VER
+#ifdef _WIN32
 // Defined in msvc_helper_main-win32.cc.
 int MSVCHelperMain(int argc, char** argv);
 
@@ -82,7 +88,8 @@
 /// to poke into these, so store them as fields on an object.
 struct NinjaMain : public BuildLogUser {
   NinjaMain(const char* ninja_command, const BuildConfig& config) :
-      ninja_command_(ninja_command), config_(config) {}
+      ninja_command_(ninja_command), config_(config),
+      start_time_millis_(GetTimeMillis()) {}
 
   /// Command line used to run Ninja.
   const char* ninja_command_;
@@ -117,10 +124,12 @@
   int ToolGraph(const Options* options, int argc, char* argv[]);
   int ToolQuery(const Options* options, int argc, char* argv[]);
   int ToolDeps(const Options* options, int argc, char* argv[]);
+  int ToolMissingDeps(const Options* options, int argc, char* argv[]);
   int ToolBrowse(const Options* options, int argc, char* argv[]);
   int ToolMSVC(const Options* options, int argc, char* argv[]);
   int ToolTargets(const Options* options, int argc, char* argv[]);
   int ToolCommands(const Options* options, int argc, char* argv[]);
+  int ToolInputs(const Options* options, int argc, char* argv[]);
   int ToolClean(const Options* options, int argc, char* argv[]);
   int ToolCleanDead(const Options* options, int argc, char* argv[]);
   int ToolCompilationDatabase(const Options* options, int argc, char* argv[]);
@@ -128,13 +137,14 @@
   int ToolRestat(const Options* options, int argc, char* argv[]);
   int ToolUrtle(const Options* options, int argc, char** argv);
   int ToolRules(const Options* options, int argc, char* argv[]);
+  int ToolWinCodePage(const Options* options, int argc, char* argv[]);
 
   /// Open the build log.
-  /// @return LOAD_ERROR on error.
+  /// @return false on error.
   bool OpenBuildLog(bool recompact_only = false);
 
   /// Open the deps log: load it, then open for writing.
-  /// @return LOAD_ERROR on error.
+  /// @return false on error.
   bool OpenDepsLog(bool recompact_only = false);
 
   /// Ensure the build directory exists, creating it if necessary.
@@ -144,11 +154,11 @@
   /// Rebuild the manifest, if necessary.
   /// Fills in \a err on error.
   /// @return true if the manifest was rebuilt.
-  bool RebuildManifest(const char* input_file, string* err);
+  bool RebuildManifest(const char* input_file, string* err, Status* status);
 
   /// Build the targets listed on the command line.
   /// @return an exit code.
-  int RunBuild(int argc, char** argv);
+  int RunBuild(int argc, char** argv, Status* status);
 
   /// Dump the output requested by '-d stats'.
   void DumpMetrics();
@@ -172,6 +182,8 @@
       Error("%s", err.c_str());  // Log and ignore Stat() errors.
     return mtime == 0;
   }
+
+  int64_t start_time_millis_;
 };
 
 /// Subtools, accessible via "-t foo".
@@ -209,6 +221,7 @@
 "options:\n"
 "  --version      print ninja version (\"%s\")\n"
 "  -v, --verbose  show all command lines while building\n"
+"  --quiet        don't show progress status, just command output\n"
 "\n"
 "  -C DIR   change to DIR before doing anything else\n"
 "  -f FILE  specify input build file [default=build.ninja]\n"
@@ -240,16 +253,21 @@
 
 /// Rebuild the build manifest, if necessary.
 /// Returns true if the manifest was rebuilt.
-bool NinjaMain::RebuildManifest(const char* input_file, string* err) {
+bool NinjaMain::RebuildManifest(const char* input_file, string* err,
+                                Status* status) {
   string path = input_file;
-  uint64_t slash_bits;  // Unused because this path is only used for lookup.
-  if (!CanonicalizePath(&path, &slash_bits, err))
+  if (path.empty()) {
+    *err = "empty path";
     return false;
+  }
+  uint64_t slash_bits;  // Unused because this path is only used for lookup.
+  CanonicalizePath(&path, &slash_bits);
   Node* node = state_.LookupNode(path);
   if (!node)
     return false;
 
-  Builder builder(&state_, config_, &build_log_, &deps_log_, &disk_interface_);
+  Builder builder(&state_, config_, &build_log_, &deps_log_, &disk_interface_,
+                  status, start_time_millis_);
   if (!builder.AddTarget(node, err))
     return false;
 
@@ -273,9 +291,12 @@
 
 Node* NinjaMain::CollectTarget(const char* cpath, string* err) {
   string path = cpath;
-  uint64_t slash_bits;
-  if (!CanonicalizePath(&path, &slash_bits, err))
+  if (path.empty()) {
+    *err = "empty path";
     return NULL;
+  }
+  uint64_t slash_bits;
+  CanonicalizePath(&path, &slash_bits);
 
   // Special syntax: "foo.cc^" means "the first output of foo.cc".
   bool first_dependent = false;
@@ -288,15 +309,20 @@
   if (node) {
     if (first_dependent) {
       if (node->out_edges().empty()) {
-        *err = "'" + path + "' has no out edge";
-        return NULL;
+        Node* rev_deps = deps_log_.GetFirstReverseDepsNode(node);
+        if (!rev_deps) {
+          *err = "'" + path + "' has no out edge";
+          return NULL;
+        }
+        node = rev_deps;
+      } else {
+        Edge* edge = node->out_edges()[0];
+        if (edge->outputs_.empty()) {
+          edge->Dump();
+          Fatal("edge has no outputs");
+        }
+        node = edge->outputs_[0];
       }
-      Edge* edge = node->out_edges()[0];
-      if (edge->outputs_.empty()) {
-        edge->Dump();
-        Fatal("edge has no outputs");
-      }
-      node = edge->outputs_[0];
     }
     return node;
   } else {
@@ -381,6 +407,13 @@
           label = "|| ";
         printf("    %s%s\n", label, edge->inputs_[in]->path().c_str());
       }
+      if (!edge->validations_.empty()) {
+        printf("  validations:\n");
+        for (std::vector<Node*>::iterator validation = edge->validations_.begin();
+             validation != edge->validations_.end(); ++validation) {
+          printf("    %s\n", (*validation)->path().c_str());
+        }
+      }
     }
     printf("  outputs:\n");
     for (vector<Edge*>::const_iterator edge = node->out_edges().begin();
@@ -390,6 +423,17 @@
         printf("    %s\n", (*out)->path().c_str());
       }
     }
+    const std::vector<Edge*> validation_edges = node->validation_out_edges();
+    if (!validation_edges.empty()) {
+      printf("  validation for:\n");
+      for (std::vector<Edge*>::const_iterator edge = validation_edges.begin();
+           edge != validation_edges.end(); ++edge) {
+        for (vector<Node*>::iterator out = (*edge)->outputs_.begin();
+             out != (*edge)->outputs_.end(); ++out) {
+          printf("    %s\n", (*out)->path().c_str());
+        }
+      }
+    }
   }
   return 0;
 }
@@ -407,7 +451,7 @@
 }
 #endif
 
-#if defined(_MSC_VER)
+#if defined(_WIN32)
 int NinjaMain::ToolMSVC(const Options* options, int argc, char* argv[]) {
   // Reset getopt: push one argument onto the front of argv, reset optind.
   argc++;
@@ -523,6 +567,26 @@
   return 0;
 }
 
+int NinjaMain::ToolMissingDeps(const Options* options, int argc, char** argv) {
+  vector<Node*> nodes;
+  string err;
+  if (!CollectTargetsFromArgs(argc, argv, &nodes, &err)) {
+    Error("%s", err.c_str());
+    return 1;
+  }
+  RealDiskInterface disk_interface;
+  MissingDependencyPrinter printer;
+  MissingDependencyScanner scanner(&printer, &deps_log_, &state_,
+                                   &disk_interface);
+  for (vector<Node*>::iterator it = nodes.begin(); it != nodes.end(); ++it) {
+    scanner.ProcessNode(*it);
+  }
+  scanner.PrintStats();
+  if (scanner.HadMissingDeps())
+    return 3;
+  return 0;
+}
+
 int NinjaMain::ToolTargets(const Options* options, int argc, char* argv[]) {
   int depth = 1;
   if (argc >= 1) {
@@ -612,8 +676,19 @@
   return 0;
 }
 
+#ifdef _WIN32
+int NinjaMain::ToolWinCodePage(const Options* options, int argc, char* argv[]) {
+  if (argc != 0) {
+    printf("usage: ninja -t wincodepage\n");
+    return 1;
+  }
+  printf("Build file encoding: %s\n", GetACP() == CP_UTF8? "UTF-8" : "ANSI");
+  return 0;
+}
+#endif
+
 enum PrintCommandMode { PCM_Single, PCM_All };
-void PrintCommands(Edge* edge, set<Edge*>* seen, PrintCommandMode mode) {
+void PrintCommands(Edge* edge, EdgeSet* seen, PrintCommandMode mode) {
   if (!edge)
     return;
   if (!seen->insert(edge).second)
@@ -630,7 +705,7 @@
 }
 
 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 commands tool uses getopt, and expects argv[0] to contain the name of
   // the tool, i.e. "commands".
   ++argc;
   --argv;
@@ -664,13 +739,79 @@
     return 1;
   }
 
-  set<Edge*> seen;
+  EdgeSet seen;
   for (vector<Node*>::iterator in = nodes.begin(); in != nodes.end(); ++in)
     PrintCommands((*in)->in_edge(), &seen, mode);
 
   return 0;
 }
 
+void CollectInputs(Edge* edge, std::set<Edge*>* seen,
+                   std::vector<std::string>* result) {
+  if (!edge)
+    return;
+  if (!seen->insert(edge).second)
+    return;
+
+  for (vector<Node*>::iterator in = edge->inputs_.begin();
+       in != edge->inputs_.end(); ++in)
+    CollectInputs((*in)->in_edge(), seen, result);
+
+  if (!edge->is_phony()) {
+    edge->CollectInputs(true, result);
+  }
+}
+
+int NinjaMain::ToolInputs(const Options* options, int argc, char* argv[]) {
+  // The inputs tool uses getopt, and expects argv[0] to contain the name of
+  // the tool, i.e. "inputs".
+  argc++;
+  argv--;
+  optind = 1;
+  int opt;
+  const option kLongOptions[] = { { "help", no_argument, NULL, 'h' },
+                                  { NULL, 0, NULL, 0 } };
+  while ((opt = getopt_long(argc, argv, "h", kLongOptions, NULL)) != -1) {
+    switch (opt) {
+    case 'h':
+    default:
+      // clang-format off
+      printf(
+"Usage '-t inputs [options] [targets]\n"
+"\n"
+"List all inputs used for a set of targets. Note that this includes\n"
+"explicit, implicit and order-only inputs, but not validation ones.\n\n"
+"Options:\n"
+"  -h, --help   Print this message.\n");
+      // clang-format on
+      return 1;
+    }
+  }
+  argv += optind;
+  argc -= optind;
+
+  vector<Node*> nodes;
+  string err;
+  if (!CollectTargetsFromArgs(argc, argv, &nodes, &err)) {
+    Error("%s", err.c_str());
+    return 1;
+  }
+
+  std::set<Edge*> seen;
+  std::vector<std::string> result;
+  for (vector<Node*>::iterator in = nodes.begin(); in != nodes.end(); ++in)
+    CollectInputs((*in)->in_edge(), &seen, &result);
+
+  // Make output deterministic by sorting then removing duplicates.
+  std::sort(result.begin(), result.end());
+  result.erase(std::unique(result.begin(), result.end()), result.end());
+
+  for (size_t n = 0; n < result.size(); ++n)
+    puts(result[n].c_str());
+
+  return 0;
+}
+
 int NinjaMain::ToolClean(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. "clean".
@@ -725,15 +866,6 @@
   return cleaner.CleanDead(build_log_.entries());
 }
 
-void EncodeJSONString(const char *str) {
-  while (*str) {
-    if (*str == '"' || *str == '\\')
-      putchar('\\');
-    putchar(*str);
-    str++;
-  }
-}
-
 enum EvaluateCommandMode {
   ECM_NORMAL,
   ECM_EXPAND_RSPFILE
@@ -766,13 +898,13 @@
 void printCompdb(const char* const directory, const Edge* const edge,
                  const EvaluateCommandMode eval_mode) {
   printf("\n  {\n    \"directory\": \"");
-  EncodeJSONString(directory);
+  PrintJSONString(directory);
   printf("\",\n    \"command\": \"");
-  EncodeJSONString(EvaluateCommandWithRspfile(edge, eval_mode).c_str());
+  PrintJSONString(EvaluateCommandWithRspfile(edge, eval_mode));
   printf("\",\n    \"file\": \"");
-  EncodeJSONString(edge->inputs_[0]->path().c_str());
+  PrintJSONString(edge->inputs_[0]->path());
   printf("\",\n    \"output\": \"");
-  EncodeJSONString(edge->outputs_[0]->path().c_str());
+  PrintJSONString(edge->outputs_[0]->path());
   printf("\"\n  }");
 }
 
@@ -853,8 +985,8 @@
   if (!EnsureBuildDirExists())
     return 1;
 
-  if (OpenBuildLog(/*recompact_only=*/true) == LOAD_ERROR ||
-      OpenDepsLog(/*recompact_only=*/true) == LOAD_ERROR)
+  if (!OpenBuildLog(/*recompact_only=*/true) ||
+      !OpenDepsLog(/*recompact_only=*/true))
     return 1;
 
   return 0;
@@ -950,16 +1082,20 @@
   static const Tool kTools[] = {
     { "browse", "browse dependency graph in a web browser",
       Tool::RUN_AFTER_LOAD, &NinjaMain::ToolBrowse },
-#if defined(_MSC_VER)
-    { "msvc", "build helper for MSVC cl.exe (EXPERIMENTAL)",
+#ifdef _WIN32
+    { "msvc", "build helper for MSVC cl.exe (DEPRECATED)",
       Tool::RUN_AFTER_FLAGS, &NinjaMain::ToolMSVC },
 #endif
     { "clean", "clean built files",
       Tool::RUN_AFTER_LOAD, &NinjaMain::ToolClean },
     { "commands", "list all commands required to rebuild given targets",
       Tool::RUN_AFTER_LOAD, &NinjaMain::ToolCommands },
+    { "inputs", "list all inputs required to rebuild given targets",
+      Tool::RUN_AFTER_LOAD, &NinjaMain::ToolInputs},
     { "deps", "show dependencies stored in the deps log",
       Tool::RUN_AFTER_LOGS, &NinjaMain::ToolDeps },
+    { "missingdeps", "check deps log dependencies on generated files",
+      Tool::RUN_AFTER_LOGS, &NinjaMain::ToolMissingDeps },
     { "graph", "output graphviz dot file for targets",
       Tool::RUN_AFTER_LOAD, &NinjaMain::ToolGraph },
     { "query", "show inputs/outputs for a path",
@@ -978,6 +1114,10 @@
       Tool::RUN_AFTER_LOGS, &NinjaMain::ToolCleanDead },
     { "urtle", NULL,
       Tool::RUN_AFTER_FLAGS, &NinjaMain::ToolUrtle },
+#ifdef _WIN32
+    { "wincodepage", "print the Windows code page used by ninja",
+      Tool::RUN_AFTER_FLAGS, &NinjaMain::ToolWinCodePage },
+#endif
     { NULL, NULL, Tool::RUN_AFTER_FLAGS, NULL }
   };
 
@@ -985,7 +1125,7 @@
     printf("ninja subtools:\n");
     for (const Tool* tool = &kTools[0]; tool->name; ++tool) {
       if (tool->desc)
-        printf("%10s  %s\n", tool->name, tool->desc);
+        printf("%11s  %s\n", tool->name, tool->desc);
     }
     return NULL;
   }
@@ -1057,7 +1197,6 @@
 bool WarningEnable(const string& name, Options* options) {
   if (name == "list") {
     printf("warning flags:\n"
-"  dupbuild={err,warn}  multiple build lines for one target\n"
 "  phonycycle={err,warn}  phony build statement references itself\n"
     );
     return false;
@@ -1189,21 +1328,22 @@
   return true;
 }
 
-int NinjaMain::RunBuild(int argc, char** argv) {
+int NinjaMain::RunBuild(int argc, char** argv, Status* status) {
   string err;
   vector<Node*> targets;
   if (!CollectTargetsFromArgs(argc, argv, &targets, &err)) {
-    Error("%s", err.c_str());
+    status->Error("%s", err.c_str());
     return 1;
   }
 
   disk_interface_.AllowStatCache(g_experimental_statcache);
 
-  Builder builder(&state_, config_, &build_log_, &deps_log_, &disk_interface_);
+  Builder builder(&state_, config_, &build_log_, &deps_log_, &disk_interface_,
+                  status, start_time_millis_);
   for (size_t i = 0; i < targets.size(); ++i) {
     if (!builder.AddTarget(targets[i], &err)) {
       if (!err.empty()) {
-        Error("%s", err.c_str());
+        status->Error("%s", err.c_str());
         return 1;
       } else {
         // Added a target that is already up-to-date; not really
@@ -1216,12 +1356,12 @@
   disk_interface_.AllowStatCache(false);
 
   if (builder.AlreadyUpToDate()) {
-    printf("ninja: no work to do.\n");
+    status->Info("no work to do.");
     return 0;
   }
 
   if (!builder.Build(&err)) {
-    printf("ninja: build stopped: %s.\n", err.c_str());
+    status->Info("build stopped: %s.", err.c_str());
     if (err.find("interrupted by user") != string::npos) {
       return 2;
     }
@@ -1254,17 +1394,35 @@
 
 #endif  // _MSC_VER
 
+class DeferGuessParallelism {
+ public:
+  bool needGuess;
+  BuildConfig* config;
+
+  DeferGuessParallelism(BuildConfig* config)
+      : config(config), needGuess(true) {}
+
+  void Refresh() {
+    if (needGuess) {
+      needGuess = false;
+      config->parallelism = GuessParallelism();
+    }
+  }
+  ~DeferGuessParallelism() { Refresh(); }
+};
+
 /// Parse argv for command-line options.
 /// Returns an exit code, or -1 if Ninja should continue.
 int ReadFlags(int* argc, char*** argv,
               Options* options, BuildConfig* config) {
-  config->parallelism = GuessParallelism();
+  DeferGuessParallelism deferGuessParallelism(config);
 
-  enum { OPT_VERSION = 1 };
+  enum { OPT_VERSION = 1, OPT_QUIET = 2 };
   const option kLongOptions[] = {
     { "help", no_argument, NULL, 'h' },
     { "version", no_argument, NULL, OPT_VERSION },
     { "verbose", no_argument, NULL, 'v' },
+    { "quiet", no_argument, NULL, OPT_QUIET },
     { NULL, 0, NULL, 0 }
   };
 
@@ -1289,6 +1447,7 @@
         // We want to run N jobs in parallel. For N = 0, INT_MAX
         // is close enough to infinite for most sane builds.
         config->parallelism = value > 0 ? value : INT_MAX;
+        deferGuessParallelism.needGuess = false;
         break;
       }
       case 'k': {
@@ -1322,6 +1481,9 @@
       case 'v':
         config->verbosity = BuildConfig::VERBOSE;
         break;
+      case OPT_QUIET:
+        config->verbosity = BuildConfig::NO_STATUS_UPDATE;
+        break;
       case 'w':
         if (!WarningEnable(optarg, options))
           return 1;
@@ -1334,6 +1496,7 @@
         return 0;
       case 'h':
       default:
+        deferGuessParallelism.Refresh();
         Usage(*config);
         return 1;
     }
@@ -1359,14 +1522,16 @@
   if (exit_code >= 0)
     exit(exit_code);
 
+  Status* status = new StatusPrinter(config);
+
   if (options.working_dir) {
     // The formatting of this string, complete with funny quotes, is
     // so Emacs can properly identify that the cwd has changed for
     // subsequent commands.
     // Don't print this if a tool is being used, so that tool output
     // can be piped into a file without this string showing up.
-    if (!options.tool)
-      printf("ninja: Entering directory `%s'\n", options.working_dir);
+    if (!options.tool && config.verbosity != BuildConfig::NO_STATUS_UPDATE)
+      status->Info("Entering directory `%s'", options.working_dir);
     if (chdir(options.working_dir) < 0) {
       Fatal("chdir to '%s' - %s", options.working_dir, strerror(errno));
     }
@@ -1394,7 +1559,7 @@
     ManifestParser parser(&ninja.state_, &ninja.disk_interface_, parser_opts);
     string err;
     if (!parser.Load(options.input_file, &err)) {
-      Error("%s", err.c_str());
+      status->Error("%s", err.c_str());
       exit(1);
     }
 
@@ -1411,7 +1576,7 @@
       exit((ninja.*options.tool->func)(&options, argc, argv));
 
     // Attempt to rebuild the manifest before building anything else
-    if (ninja.RebuildManifest(options.input_file, &err)) {
+    if (ninja.RebuildManifest(options.input_file, &err, status)) {
       // In dry_run mode the regeneration will succeed without changing the
       // manifest forever. Better to return immediately.
       if (config.dry_run)
@@ -1419,17 +1584,17 @@
       // Start the build over with the new manifest.
       continue;
     } else if (!err.empty()) {
-      Error("rebuilding '%s': %s", options.input_file, err.c_str());
+      status->Error("rebuilding '%s': %s", options.input_file, err.c_str());
       exit(1);
     }
 
-    int result = ninja.RunBuild(argc, argv);
+    int result = ninja.RunBuild(argc, argv, status);
     if (g_metrics)
       ninja.DumpMetrics();
     exit(result);
   }
 
-  Error("manifest '%s' still dirty after %d tries\n",
+  status->Error("manifest '%s' still dirty after %d tries, perhaps system time is not set",
       options.input_file, kCycleLimit);
   exit(1);
 }
diff --git a/src/ninja_test.cc b/src/ninja_test.cc
index b40e176..6720dec 100644
--- a/src/ninja_test.cc
+++ b/src/ninja_test.cc
@@ -67,7 +67,7 @@
 "usage: ninja_tests [options]\n"
 "\n"
 "options:\n"
-"  --gtest_filter=POSTIVE_PATTERN[-NEGATIVE_PATTERN]\n"
+"  --gtest_filter=POSITIVE_PATTERN[-NEGATIVE_PATTERN]\n"
 "      Run tests whose names match the positive but not the negative pattern.\n"
 "      '*' matches any substring. (gtest's ':', '?' are not implemented).\n");
 }
diff --git a/src/state.cc b/src/state.cc
index d3a9e29..556b0d8 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -19,7 +19,6 @@
 
 #include "edit_distance.h"
 #include "graph.h"
-#include "metrics.h"
 #include "util.h"
 
 using namespace std;
@@ -39,7 +38,7 @@
   delayed_.insert(edge);
 }
 
-void Pool::RetrieveReadyEdges(set<Edge*>* ready_queue) {
+void Pool::RetrieveReadyEdges(EdgeSet* ready_queue) {
   DelayedEdges::iterator it = delayed_.begin();
   while (it != delayed_.end()) {
     Edge* edge = *it;
@@ -62,14 +61,6 @@
   }
 }
 
-// static
-bool Pool::WeightedEdgeCmp(const Edge* a, const Edge* b) {
-  if (!a) return b;
-  if (!b) return false;
-  int weight_diff = a->weight() - b->weight();
-  return ((weight_diff < 0) || (weight_diff == 0 && a < b));
-}
-
 Pool State::kDefaultPool("", 0);
 Pool State::kConsolePool("console", 1);
 const Rule State::kPhonyRule("phony");
@@ -97,6 +88,7 @@
   edge->rule_ = rule;
   edge->pool_ = &State::kDefaultPool;
   edge->env_ = &bindings_;
+  edge->id_ = edges_.size();
   edges_.push_back(edge);
   return edge;
 }
@@ -111,7 +103,6 @@
 }
 
 Node* State::LookupNode(StringPiece path) const {
-  METRIC_RECORD("lookup node");
   Paths::const_iterator i = paths_.find(path);
   if (i != paths_.end())
     return i->second;
@@ -150,6 +141,12 @@
   return true;
 }
 
+void State::AddValidation(Edge* edge, StringPiece path, uint64_t slash_bits) {
+  Node* node = GetNode(path, slash_bits);
+  edge->validations_.push_back(node);
+  node->AddValidationOutEdge(edge);
+}
+
 bool State::AddDefault(StringPiece path, string* err) {
   Node* node = LookupNode(path);
   if (!node) {
diff --git a/src/state.h b/src/state.h
index f553ed4..878ac6d 100644
--- a/src/state.h
+++ b/src/state.h
@@ -21,6 +21,7 @@
 #include <vector>
 
 #include "eval_env.h"
+#include "graph.h"
 #include "hash_map.h"
 #include "util.h"
 
@@ -38,7 +39,7 @@
 /// completes).
 struct Pool {
   Pool(const std::string& name, int depth)
-    : name_(name), current_use_(0), depth_(depth), delayed_(&WeightedEdgeCmp) {}
+    : name_(name), current_use_(0), depth_(depth), delayed_() {}
 
   // A depth of 0 is infinite
   bool is_valid() const { return depth_ >= 0; }
@@ -61,7 +62,7 @@
   void DelayEdge(Edge* edge);
 
   /// Pool will add zero or more edges to the ready_queue
-  void RetrieveReadyEdges(std::set<Edge*>* ready_queue);
+  void RetrieveReadyEdges(EdgeSet* ready_queue);
 
   /// Dump the Pool and its edges (useful for debugging).
   void Dump() const;
@@ -74,9 +75,16 @@
   int current_use_;
   int depth_;
 
-  static bool WeightedEdgeCmp(const Edge* a, const Edge* b);
+  struct WeightedEdgeCmp {
+    bool operator()(const Edge* a, const Edge* b) const {
+      if (!a) return b;
+      if (!b) return false;
+      int weight_diff = a->weight() - b->weight();
+      return ((weight_diff < 0) || (weight_diff == 0 && EdgeCmp()(a, b)));
+    }
+  };
 
-  typedef std::set<Edge*,bool(*)(const Edge*, const Edge*)> DelayedEdges;
+  typedef std::set<Edge*, WeightedEdgeCmp> DelayedEdges;
   DelayedEdges delayed_;
 };
 
@@ -99,6 +107,7 @@
 
   void AddIn(Edge* edge, StringPiece path, uint64_t slash_bits);
   bool AddOut(Edge* edge, StringPiece path, uint64_t slash_bits);
+  void AddValidation(Edge* edge, StringPiece path, uint64_t slash_bits);
   bool AddDefault(StringPiece path, std::string* error);
 
   /// Reset state.  Keeps all nodes and edges, but restores them to the
diff --git a/src/status.cc b/src/status.cc
new file mode 100644
index 0000000..88b7781
--- /dev/null
+++ b/src/status.cc
@@ -0,0 +1,267 @@
+// Copyright 2016 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 "status.h"
+
+#include <stdarg.h>
+#include <stdlib.h>
+
+#ifdef _WIN32
+#include <fcntl.h>
+#include <io.h>
+#endif
+
+#include "debug_flags.h"
+
+using namespace std;
+
+StatusPrinter::StatusPrinter(const BuildConfig& config)
+    : config_(config),
+      started_edges_(0), finished_edges_(0), total_edges_(0), running_edges_(0),
+      time_millis_(0), progress_status_format_(NULL),
+      current_rate_(config.parallelism) {
+
+  // Don't do anything fancy in verbose mode.
+  if (config_.verbosity != BuildConfig::NORMAL)
+    printer_.set_smart_terminal(false);
+
+  progress_status_format_ = getenv("NINJA_STATUS");
+  if (!progress_status_format_)
+    progress_status_format_ = "[%f/%t] ";
+}
+
+void StatusPrinter::PlanHasTotalEdges(int total) {
+  total_edges_ = total;
+}
+
+void StatusPrinter::BuildEdgeStarted(const Edge* edge,
+                                     int64_t start_time_millis) {
+  ++started_edges_;
+  ++running_edges_;
+  time_millis_ = start_time_millis;
+
+  if (edge->use_console() || printer_.is_smart_terminal())
+    PrintStatus(edge, start_time_millis);
+
+  if (edge->use_console())
+    printer_.SetConsoleLocked(true);
+}
+
+void StatusPrinter::BuildEdgeFinished(Edge* edge, int64_t end_time_millis,
+                                      bool success, const string& output) {
+  time_millis_ = end_time_millis;
+  ++finished_edges_;
+
+  if (edge->use_console())
+    printer_.SetConsoleLocked(false);
+
+  if (config_.verbosity == BuildConfig::QUIET)
+    return;
+
+  if (!edge->use_console())
+    PrintStatus(edge, end_time_millis);
+
+  --running_edges_;
+
+  // Print the command that is spewing before printing its output.
+  if (!success) {
+    string outputs;
+    for (vector<Node*>::const_iterator o = edge->outputs_.begin();
+         o != edge->outputs_.end(); ++o)
+      outputs += (*o)->path() + " ";
+
+    if (printer_.supports_color()) {
+        printer_.PrintOnNewLine("\x1B[31m" "FAILED: " "\x1B[0m" + outputs + "\n");
+    } else {
+        printer_.PrintOnNewLine("FAILED: " + outputs + "\n");
+    }
+    printer_.PrintOnNewLine(edge->EvaluateCommand() + "\n");
+  }
+
+  if (!output.empty()) {
+    // ninja sets stdout and stderr of subprocesses to a pipe, to be able to
+    // check if the output is empty. Some compilers, e.g. clang, check
+    // isatty(stderr) to decide if they should print colored output.
+    // To make it possible to use colored output with ninja, subprocesses should
+    // be run with a flag that forces them to always print color escape codes.
+    // To make sure these escape codes don't show up in a file if ninja's output
+    // is piped to a file, ninja strips ansi escape codes again if it's not
+    // writing to a |smart_terminal_|.
+    // (Launching subprocesses in pseudo ttys doesn't work because there are
+    // only a few hundred available on some systems, and ninja can launch
+    // thousands of parallel compile commands.)
+    string final_output;
+    if (!printer_.supports_color())
+      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
+  }
+}
+
+void StatusPrinter::BuildLoadDyndeps() {
+  // The DependencyScan calls EXPLAIN() to print lines explaining why
+  // it considers a portion of the graph to be out of date.  Normally
+  // this is done before the build starts, but our caller is about to
+  // load a dyndep file during the build.  Doing so may generate more
+  // explanation lines (via fprintf directly to stderr), but in an
+  // interactive console the cursor is currently at the end of a status
+  // line.  Start a new line so that the first explanation does not
+  // append to the status line.  After the explanations are done a
+  // new build status line will appear.
+  if (g_explaining)
+    printer_.PrintOnNewLine("");
+}
+
+void StatusPrinter::BuildStarted() {
+  started_edges_ = 0;
+  finished_edges_ = 0;
+  running_edges_ = 0;
+}
+
+void StatusPrinter::BuildFinished() {
+  printer_.SetConsoleLocked(false);
+  printer_.PrintOnNewLine("");
+}
+
+string StatusPrinter::FormatProgressStatus(const char* progress_status_format,
+                                           int64_t time_millis) const {
+  string out;
+  char buf[32];
+  for (const char* s = progress_status_format; *s != '\0'; ++s) {
+    if (*s == '%') {
+      ++s;
+      switch (*s) {
+      case '%':
+        out.push_back('%');
+        break;
+
+        // Started edges.
+      case 's':
+        snprintf(buf, sizeof(buf), "%d", started_edges_);
+        out += buf;
+        break;
+
+        // Total edges.
+      case 't':
+        snprintf(buf, sizeof(buf), "%d", total_edges_);
+        out += buf;
+        break;
+
+        // Running edges.
+      case 'r': {
+        snprintf(buf, sizeof(buf), "%d", running_edges_);
+        out += buf;
+        break;
+      }
+
+        // Unstarted edges.
+      case 'u':
+        snprintf(buf, sizeof(buf), "%d", total_edges_ - started_edges_);
+        out += buf;
+        break;
+
+        // Finished edges.
+      case 'f':
+        snprintf(buf, sizeof(buf), "%d", finished_edges_);
+        out += buf;
+        break;
+
+        // Overall finished edges per second.
+      case 'o':
+        SnprintfRate(finished_edges_ / (time_millis_ / 1e3), buf, "%.1f");
+        out += buf;
+        break;
+
+        // Current rate, average over the last '-j' jobs.
+      case 'c':
+        current_rate_.UpdateRate(finished_edges_, time_millis_);
+        SnprintfRate(current_rate_.rate(), buf, "%.1f");
+        out += buf;
+        break;
+
+        // Percentage
+      case 'p': {
+        int percent = (100 * finished_edges_) / total_edges_;
+        snprintf(buf, sizeof(buf), "%3i%%", percent);
+        out += buf;
+        break;
+      }
+
+      case 'e': {
+        snprintf(buf, sizeof(buf), "%.3f", time_millis_ / 1e3);
+        out += buf;
+        break;
+      }
+
+      default:
+        Fatal("unknown placeholder '%%%c' in $NINJA_STATUS", *s);
+        return "";
+      }
+    } else {
+      out.push_back(*s);
+    }
+  }
+
+  return out;
+}
+
+void StatusPrinter::PrintStatus(const Edge* edge, int64_t time_millis) {
+  if (config_.verbosity == BuildConfig::QUIET
+      || config_.verbosity == BuildConfig::NO_STATUS_UPDATE)
+    return;
+
+  bool force_full_command = config_.verbosity == BuildConfig::VERBOSE;
+
+  string to_print = edge->GetBinding("description");
+  if (to_print.empty() || force_full_command)
+    to_print = edge->GetBinding("command");
+
+  to_print = FormatProgressStatus(progress_status_format_, time_millis)
+      + to_print;
+
+  printer_.Print(to_print,
+                 force_full_command ? LinePrinter::FULL : LinePrinter::ELIDE);
+}
+
+void StatusPrinter::Warning(const char* msg, ...) {
+  va_list ap;
+  va_start(ap, msg);
+  ::Warning(msg, ap);
+  va_end(ap);
+}
+
+void StatusPrinter::Error(const char* msg, ...) {
+  va_list ap;
+  va_start(ap, msg);
+  ::Error(msg, ap);
+  va_end(ap);
+}
+
+void StatusPrinter::Info(const char* msg, ...) {
+  va_list ap;
+  va_start(ap, msg);
+  ::Info(msg, ap);
+  va_end(ap);
+}
diff --git a/src/status.h b/src/status.h
new file mode 100644
index 0000000..e211ba3
--- /dev/null
+++ b/src/status.h
@@ -0,0 +1,117 @@
+// Copyright 2016 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_STATUS_H_
+#define NINJA_STATUS_H_
+
+#include <map>
+#include <string>
+
+#include "build.h"
+#include "line_printer.h"
+
+/// Abstract interface to object that tracks the status of a build:
+/// completion fraction, printing updates.
+struct Status {
+  virtual void PlanHasTotalEdges(int total) = 0;
+  virtual void BuildEdgeStarted(const Edge* edge, int64_t start_time_millis) = 0;
+  virtual void BuildEdgeFinished(Edge* edge, int64_t end_time_millis,
+                                 bool success, const std::string& output) = 0;
+  virtual void BuildLoadDyndeps() = 0;
+  virtual void BuildStarted() = 0;
+  virtual void BuildFinished() = 0;
+
+  virtual void Info(const char* msg, ...) = 0;
+  virtual void Warning(const char* msg, ...) = 0;
+  virtual void Error(const char* msg, ...) = 0;
+
+  virtual ~Status() { }
+};
+
+/// Implementation of the Status interface that prints the status as
+/// human-readable strings to stdout
+struct StatusPrinter : Status {
+  explicit StatusPrinter(const BuildConfig& config);
+  virtual void PlanHasTotalEdges(int total);
+  virtual void BuildEdgeStarted(const Edge* edge, int64_t start_time_millis);
+  virtual void BuildEdgeFinished(Edge* edge, int64_t end_time_millis,
+                                 bool success, const std::string& output);
+  virtual void BuildLoadDyndeps();
+  virtual void BuildStarted();
+  virtual void BuildFinished();
+
+  virtual void Info(const char* msg, ...);
+  virtual void Warning(const char* msg, ...);
+  virtual void Error(const char* msg, ...);
+
+  virtual ~StatusPrinter() { }
+
+  /// Format the progress status string by replacing the placeholders.
+  /// See the user manual for more information about the available
+  /// placeholders.
+  /// @param progress_status_format The format of the progress status.
+  /// @param status The status of the edge.
+  std::string FormatProgressStatus(const char* progress_status_format,
+                                   int64_t time_millis) const;
+
+ private:
+  void PrintStatus(const Edge* edge, int64_t time_millis);
+
+  const BuildConfig& config_;
+
+  int started_edges_, finished_edges_, total_edges_, running_edges_;
+  int64_t time_millis_;
+
+  /// Prints progress output.
+  LinePrinter printer_;
+
+  /// The custom progress status format to use.
+  const char* progress_status_format_;
+
+  template<size_t S>
+  void SnprintfRate(double rate, char(&buf)[S], const char* format) const {
+    if (rate == -1)
+      snprintf(buf, S, "?");
+    else
+      snprintf(buf, S, format, rate);
+  }
+
+  struct SlidingRateInfo {
+    SlidingRateInfo(int n) : rate_(-1), N(n), last_update_(-1) {}
+
+    double rate() { return rate_; }
+
+    void UpdateRate(int update_hint, int64_t time_millis_) {
+      if (update_hint == last_update_)
+        return;
+      last_update_ = update_hint;
+
+      if (times_.size() == N)
+        times_.pop();
+      times_.push(time_millis_);
+      if (times_.back() != times_.front())
+        rate_ = times_.size() / ((times_.back() - times_.front()) / 1e3);
+    }
+
+  private:
+    double rate_;
+    const size_t N;
+    std::queue<double> times_;
+    int last_update_;
+  };
+
+  mutable SlidingRateInfo current_rate_;
+};
+
+#endif // NINJA_STATUS_H_
diff --git a/src/status_test.cc b/src/status_test.cc
new file mode 100644
index 0000000..6e42490
--- /dev/null
+++ b/src/status_test.cc
@@ -0,0 +1,35 @@
+// Copyright 2011 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 "status.h"
+
+#include "test.h"
+
+TEST(StatusTest, StatusFormatElapsed) {
+  BuildConfig config;
+  StatusPrinter status(config);
+
+  status.BuildStarted();
+  // Before any task is done, the elapsed time must be zero.
+  EXPECT_EQ("[%/e0.000]",
+            status.FormatProgressStatus("[%%/e%e]", 0));
+}
+
+TEST(StatusTest, StatusFormatReplacePlaceholder) {
+  BuildConfig config;
+  StatusPrinter status(config);
+
+  EXPECT_EQ("[%/s0/t0/r0/u0/f0]",
+            status.FormatProgressStatus("[%%/s%s/t%t/r%r/u%u/f%f]", 0));
+}
diff --git a/src/util.cc b/src/util.cc
index c76f730..483f4a6 100644
--- a/src/util.cc
+++ b/src/util.cc
@@ -49,10 +49,16 @@
 #include <libperfstat.h>
 #elif defined(linux) || defined(__GLIBC__)
 #include <sys/sysinfo.h>
+#include <fstream>
+#include <map>
+#include "string_piece_util.h"
+#endif
+
+#if defined(__FreeBSD__)
+#include <sys/cpuset.h>
 #endif
 
 #include "edit_distance.h"
-#include "metrics.h"
 
 using namespace std;
 
@@ -74,34 +80,52 @@
 #endif
 }
 
+void Warning(const char* msg, va_list ap) {
+  fprintf(stderr, "ninja: warning: ");
+  vfprintf(stderr, msg, ap);
+  fprintf(stderr, "\n");
+}
+
 void Warning(const char* msg, ...) {
   va_list ap;
-  fprintf(stderr, "ninja: warning: ");
   va_start(ap, msg);
-  vfprintf(stderr, msg, ap);
+  Warning(msg, ap);
   va_end(ap);
+}
+
+void Error(const char* msg, va_list ap) {
+  fprintf(stderr, "ninja: error: ");
+  vfprintf(stderr, msg, ap);
   fprintf(stderr, "\n");
 }
 
 void Error(const char* msg, ...) {
   va_list ap;
-  fprintf(stderr, "ninja: error: ");
   va_start(ap, msg);
-  vfprintf(stderr, msg, ap);
+  Error(msg, ap);
   va_end(ap);
-  fprintf(stderr, "\n");
 }
 
-bool CanonicalizePath(string* path, uint64_t* slash_bits, string* err) {
-  METRIC_RECORD("canonicalize str");
+void Info(const char* msg, va_list ap) {
+  fprintf(stdout, "ninja: ");
+  vfprintf(stdout, msg, ap);
+  fprintf(stdout, "\n");
+}
+
+void Info(const char* msg, ...) {
+  va_list ap;
+  va_start(ap, msg);
+  Info(msg, ap);
+  va_end(ap);
+}
+
+void CanonicalizePath(string* path, uint64_t* slash_bits) {
   size_t len = path->size();
   char* str = 0;
   if (len > 0)
     str = &(*path)[0];
-  if (!CanonicalizePath(str, &len, slash_bits, err))
-    return false;
+  CanonicalizePath(str, &len, slash_bits);
   path->resize(len);
-  return true;
 }
 
 static bool IsPathSeparator(char c) {
@@ -112,14 +136,11 @@
 #endif
 }
 
-bool CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits,
-                      string* err) {
+void CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits) {
   // WARNING: this function is performance-critical; please benchmark
   // any changes you make to it.
-  METRIC_RECORD("canonicalize path");
   if (*len == 0) {
-    *err = "empty path";
-    return false;
+    return;
   }
 
   const int kMaxPathComponents = 60;
@@ -209,7 +230,6 @@
 #else
   *slash_bits = 0;
 #endif
-  return true;
 }
 
 static inline bool IsKnownShellSafeCharacter(char ch) {
@@ -333,7 +353,8 @@
     if (!::ReadFile(f, buf, sizeof(buf), &len, NULL)) {
       err->assign(GetLastErrorString());
       contents->clear();
-      return -1;
+      ::CloseHandle(f);
+      return -EIO;
     }
     if (len == 0)
       break;
@@ -481,20 +502,226 @@
   return stripped;
 }
 
+#if defined(linux) || defined(__GLIBC__)
+std::pair<int64_t, bool> readCount(const std::string& path) {
+  std::ifstream file(path.c_str());
+  if (!file.is_open())
+    return std::make_pair(0, false);
+  int64_t n = 0;
+  file >> n;
+  if (file.good())
+    return std::make_pair(n, true);
+  return std::make_pair(0, false);
+}
+
+struct MountPoint {
+  int mountId;
+  int parentId;
+  StringPiece deviceId;
+  StringPiece root;
+  StringPiece mountPoint;
+  vector<StringPiece> options;
+  vector<StringPiece> optionalFields;
+  StringPiece fsType;
+  StringPiece mountSource;
+  vector<StringPiece> superOptions;
+  bool parse(const string& line) {
+    vector<StringPiece> pieces = SplitStringPiece(line, ' ');
+    if (pieces.size() < 10)
+      return false;
+    size_t optionalStart = 0;
+    for (size_t i = 6; i < pieces.size(); i++) {
+      if (pieces[i] == "-") {
+        optionalStart = i + 1;
+        break;
+      }
+    }
+    if (optionalStart == 0)
+      return false;
+    if (optionalStart + 3 != pieces.size())
+      return false;
+    mountId = atoi(pieces[0].AsString().c_str());
+    parentId = atoi(pieces[1].AsString().c_str());
+    deviceId = pieces[2];
+    root = pieces[3];
+    mountPoint = pieces[4];
+    options = SplitStringPiece(pieces[5], ',');
+    optionalFields =
+        vector<StringPiece>(&pieces[6], &pieces[optionalStart - 1]);
+    fsType = pieces[optionalStart];
+    mountSource = pieces[optionalStart + 1];
+    superOptions = SplitStringPiece(pieces[optionalStart + 2], ',');
+    return true;
+  }
+  string translate(string& path) const {
+    // path must be sub dir of root
+    if (path.compare(0, root.len_, root.str_, root.len_) != 0) {
+      return string();
+    }
+    path.erase(0, root.len_);
+    if (path == ".." || (path.length() > 2 && path.compare(0, 3, "../") == 0)) {
+      return string();
+    }
+    return mountPoint.AsString() + "/" + path;
+  }
+};
+
+struct CGroupSubSys {
+  int id;
+  string name;
+  vector<string> subsystems;
+  bool parse(string& line) {
+    size_t first = line.find(':');
+    if (first == string::npos)
+      return false;
+    line[first] = '\0';
+    size_t second = line.find(':', first + 1);
+    if (second == string::npos)
+      return false;
+    line[second] = '\0';
+    id = atoi(line.c_str());
+    name = line.substr(second + 1);
+    vector<StringPiece> pieces =
+        SplitStringPiece(StringPiece(line.c_str() + first + 1), ',');
+    for (size_t i = 0; i < pieces.size(); i++) {
+      subsystems.push_back(pieces[i].AsString());
+    }
+    return true;
+  }
+};
+
+map<string, string> ParseMountInfo(map<string, CGroupSubSys>& subsystems) {
+  map<string, string> cgroups;
+  ifstream mountinfo("/proc/self/mountinfo");
+  if (!mountinfo.is_open())
+    return cgroups;
+  while (!mountinfo.eof()) {
+    string line;
+    getline(mountinfo, line);
+    MountPoint mp;
+    if (!mp.parse(line))
+      continue;
+    if (mp.fsType != "cgroup")
+      continue;
+    for (size_t i = 0; i < mp.superOptions.size(); i++) {
+      string opt = mp.superOptions[i].AsString();
+      map<string, CGroupSubSys>::iterator subsys = subsystems.find(opt);
+      if (subsys == subsystems.end())
+        continue;
+      string newPath = mp.translate(subsys->second.name);
+      if (!newPath.empty())
+        cgroups.insert(make_pair(opt, newPath));
+    }
+  }
+  return cgroups;
+}
+
+map<string, CGroupSubSys> ParseSelfCGroup() {
+  map<string, CGroupSubSys> cgroups;
+  ifstream cgroup("/proc/self/cgroup");
+  if (!cgroup.is_open())
+    return cgroups;
+  string line;
+  while (!cgroup.eof()) {
+    getline(cgroup, line);
+    CGroupSubSys subsys;
+    if (!subsys.parse(line))
+      continue;
+    for (size_t i = 0; i < subsys.subsystems.size(); i++) {
+      cgroups.insert(make_pair(subsys.subsystems[i], subsys));
+    }
+  }
+  return cgroups;
+}
+
+int ParseCPUFromCGroup() {
+  map<string, CGroupSubSys> subsystems = ParseSelfCGroup();
+  map<string, string> cgroups = ParseMountInfo(subsystems);
+  map<string, string>::iterator cpu = cgroups.find("cpu");
+  if (cpu == cgroups.end())
+    return -1;
+  std::pair<int64_t, bool> quota = readCount(cpu->second + "/cpu.cfs_quota_us");
+  if (!quota.second || quota.first == -1)
+    return -1;
+  std::pair<int64_t, bool> period =
+      readCount(cpu->second + "/cpu.cfs_period_us");
+  if (!period.second)
+    return -1;
+  return quota.first / period.first;
+}
+#endif
+
 int GetProcessorCount() {
 #ifdef _WIN32
-  return GetActiveProcessorCount(ALL_PROCESSOR_GROUPS);
+  DWORD cpuCount = 0;
+#ifndef _WIN64
+  // Need to use GetLogicalProcessorInformationEx to get real core count on
+  // machines with >64 cores. See https://stackoverflow.com/a/31209344/21475
+  DWORD len = 0;
+  if (!GetLogicalProcessorInformationEx(RelationProcessorCore, nullptr, &len)
+        && GetLastError() == ERROR_INSUFFICIENT_BUFFER) {
+    std::vector<char> buf(len);
+    int cores = 0;
+    if (GetLogicalProcessorInformationEx(RelationProcessorCore,
+          reinterpret_cast<PSYSTEM_LOGICAL_PROCESSOR_INFORMATION_EX>(
+            buf.data()), &len)) {
+      for (DWORD i = 0; i < len; ) {
+        auto info = reinterpret_cast<PSYSTEM_LOGICAL_PROCESSOR_INFORMATION_EX>(
+            buf.data() + i);
+        if (info->Relationship == RelationProcessorCore &&
+            info->Processor.GroupCount == 1) {
+          for (KAFFINITY core_mask = info->Processor.GroupMask[0].Mask;
+               core_mask; core_mask >>= 1) {
+            cores += (core_mask & 1);
+          }
+        }
+        i += info->Size;
+      }
+      if (cores != 0) {
+        cpuCount = cores;
+      }
+    }
+  }
+#endif
+  if (cpuCount == 0) {
+    cpuCount = GetActiveProcessorCount(ALL_PROCESSOR_GROUPS);
+  }
+  JOBOBJECT_CPU_RATE_CONTROL_INFORMATION info;
+  // reference:
+  // https://docs.microsoft.com/en-us/windows/win32/api/winnt/ns-winnt-jobobject_cpu_rate_control_information
+  if (QueryInformationJobObject(NULL, JobObjectCpuRateControlInformation, &info,
+                                sizeof(info), NULL)) {
+    if (info.ControlFlags & (JOB_OBJECT_CPU_RATE_CONTROL_ENABLE |
+                             JOB_OBJECT_CPU_RATE_CONTROL_HARD_CAP)) {
+      return cpuCount * info.CpuRate / 10000;
+    }
+  }
+  return cpuCount;
 #else
-#ifdef CPU_COUNT
+  int cgroupCount = -1;
+  int schedCount = -1;
+#if defined(linux) || defined(__GLIBC__)
+  cgroupCount = ParseCPUFromCGroup();
+#endif
   // The number of exposed processors might not represent the actual number of
   // processors threads can run on. This happens when a CPU set limitation is
   // active, see https://github.com/ninja-build/ninja/issues/1278
+#if defined(__FreeBSD__)
+  cpuset_t mask;
+  CPU_ZERO(&mask);
+  if (cpuset_getaffinity(CPU_LEVEL_WHICH, CPU_WHICH_TID, -1, sizeof(mask),
+    &mask) == 0) {
+    return CPU_COUNT(&mask);
+  }
+#elif defined(CPU_COUNT)
   cpu_set_t set;
   if (sched_getaffinity(getpid(), sizeof(set), &set) == 0) {
-    return CPU_COUNT(&set);
+    schedCount = CPU_COUNT(&set);
   }
 #endif
-  return sysconf(_SC_NPROCESSORS_ONLN);
+  if (cgroupCount >= 0 && schedCount >= 0) return std::min(cgroupCount, schedCount);
+  if (cgroupCount < 0 && schedCount < 0) return sysconf(_SC_NPROCESSORS_ONLN);
+  return std::max(cgroupCount, schedCount);
 #endif
 }
 
@@ -585,6 +812,10 @@
     return -0.0f;
   return 1.0 / (1 << SI_LOAD_SHIFT) * si.loads[0];
 }
+#elif defined(__HAIKU__)
+double GetLoadAverage() {
+    return -0.0f;
+}
 #else
 double GetLoadAverage() {
   double loadavg[3] = { 0.0f, 0.0f, 0.0f };
diff --git a/src/util.h b/src/util.h
index 4e6ebb8..4a7fea2 100644
--- a/src/util.h
+++ b/src/util.h
@@ -21,6 +21,8 @@
 #include <stdint.h>
 #endif
 
+#include <stdarg.h>
+
 #include <string>
 #include <vector>
 
@@ -49,17 +51,21 @@
 
 /// Log a warning message.
 void Warning(const char* msg, ...);
+void Warning(const char* msg, va_list ap);
 
 /// Log an error message.
 void Error(const char* msg, ...);
+void Error(const char* msg, va_list ap);
+
+/// Log an informational message.
+void Info(const char* msg, ...);
+void Info(const char* msg, va_list ap);
 
 /// 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(std::string* path, uint64_t* slash_bits,
-                      std::string* err);
-bool CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits,
-                      std::string* err);
+void CanonicalizePath(std::string* path, uint64_t* slash_bits);
+void CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits);
 
 /// Appends |input| to |*result|, escaping according to the whims of either
 /// Bash, or Win32's CommandLineToArgvW().
diff --git a/src/util_test.cc b/src/util_test.cc
index 1621c91..d58b170 100644
--- a/src/util_test.cc
+++ b/src/util_test.cc
@@ -20,70 +20,69 @@
 
 namespace {
 
-bool CanonicalizePath(string* path, string* err) {
+void CanonicalizePath(string* path) {
   uint64_t unused;
-  return ::CanonicalizePath(path, &unused, err);
+  ::CanonicalizePath(path, &unused);
 }
 
 }  // namespace
 
 TEST(CanonicalizePath, PathSamples) {
   string path;
-  string err;
 
-  EXPECT_FALSE(CanonicalizePath(&path, &err));
-  EXPECT_EQ("empty path", err);
+  CanonicalizePath(&path);
+  EXPECT_EQ("", path);
 
-  path = "foo.h"; err = "";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  path = "foo.h";
+  CanonicalizePath(&path);
   EXPECT_EQ("foo.h", path);
 
   path = "./foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo.h", path);
 
   path = "./foo/./bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo/bar.h", path);
 
   path = "./x/foo/../bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("x/bar.h", path);
 
   path = "./x/foo/../../bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("bar.h", path);
 
   path = "foo//bar";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo/bar", path);
 
   path = "foo//.//..///bar";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("bar", path);
 
   path = "./x/../foo/../../bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("../bar.h", path);
 
   path = "foo/./.";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo", path);
 
   path = "foo/bar/..";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo", path);
 
   path = "foo/.hidden_bar";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo/.hidden_bar", path);
 
   path = "/foo";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("/foo", path);
 
   path = "//foo";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
 #ifdef _WIN32
   EXPECT_EQ("//foo", path);
 #else
@@ -91,173 +90,171 @@
 #endif
 
   path = "/";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("", path);
 
   path = "/foo/..";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("", path);
 
   path = ".";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ(".", path);
 
   path = "./.";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ(".", path);
 
   path = "foo/..";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ(".", path);
 }
 
 #ifdef _WIN32
 TEST(CanonicalizePath, PathSamplesWindows) {
   string path;
-  string err;
 
-  EXPECT_FALSE(CanonicalizePath(&path, &err));
-  EXPECT_EQ("empty path", err);
+  CanonicalizePath(&path);
+  EXPECT_EQ("", path);
 
-  path = "foo.h"; err = "";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  path = "foo.h";
+  CanonicalizePath(&path);
   EXPECT_EQ("foo.h", path);
 
   path = ".\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo.h", path);
 
   path = ".\\foo\\.\\bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo/bar.h", path);
 
   path = ".\\x\\foo\\..\\bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("x/bar.h", path);
 
   path = ".\\x\\foo\\..\\..\\bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("bar.h", path);
 
   path = "foo\\\\bar";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo/bar", path);
 
   path = "foo\\\\.\\\\..\\\\\\bar";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("bar", path);
 
   path = ".\\x\\..\\foo\\..\\..\\bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("../bar.h", path);
 
   path = "foo\\.\\.";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo", path);
 
   path = "foo\\bar\\..";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo", path);
 
   path = "foo\\.hidden_bar";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("foo/.hidden_bar", path);
 
   path = "\\foo";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("/foo", path);
 
   path = "\\\\foo";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("//foo", path);
 
   path = "\\";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("", path);
 }
 
 TEST(CanonicalizePath, SlashTracking) {
   string path;
-  string err;
   uint64_t slash_bits;
 
-  path = "foo.h"; err = "";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  path = "foo.h";
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("foo.h", path);
   EXPECT_EQ(0, slash_bits);
 
   path = "a\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/foo.h", path);
   EXPECT_EQ(1, slash_bits);
 
   path = "a/bcd/efh\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/bcd/efh/foo.h", path);
   EXPECT_EQ(4, slash_bits);
 
   path = "a\\bcd/efh\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/bcd/efh/foo.h", path);
   EXPECT_EQ(5, slash_bits);
 
   path = "a\\bcd\\efh\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/bcd/efh/foo.h", path);
   EXPECT_EQ(7, slash_bits);
 
   path = "a/bcd/efh/foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/bcd/efh/foo.h", path);
   EXPECT_EQ(0, slash_bits);
 
   path = "a\\./efh\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/efh/foo.h", path);
   EXPECT_EQ(3, slash_bits);
 
   path = "a\\../efh\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("efh/foo.h", path);
   EXPECT_EQ(1, slash_bits);
 
   path = "a\\b\\c\\d\\e\\f\\g\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/b/c/d/e/f/g/foo.h", path);
   EXPECT_EQ(127, slash_bits);
 
   path = "a\\b\\c\\..\\..\\..\\g\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("g/foo.h", path);
   EXPECT_EQ(1, slash_bits);
 
   path = "a\\b/c\\../../..\\g\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("g/foo.h", path);
   EXPECT_EQ(1, slash_bits);
 
   path = "a\\b/c\\./../..\\g\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/g/foo.h", path);
   EXPECT_EQ(3, slash_bits);
 
   path = "a\\b/c\\./../..\\g/foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/g/foo.h", path);
   EXPECT_EQ(1, slash_bits);
 
   path = "a\\\\\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/foo.h", path);
   EXPECT_EQ(1, slash_bits);
 
   path = "a/\\\\foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/foo.h", path);
   EXPECT_EQ(0, slash_bits);
 
   path = "a\\//foo.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ("a/foo.h", path);
   EXPECT_EQ(1, slash_bits);
 }
@@ -266,22 +263,20 @@
   // Make sure searching \/ doesn't go past supplied len.
   char buf[] = "foo/bar\\baz.h\\";  // Last \ past end.
   uint64_t slash_bits;
-  string err;
   size_t size = 13;
-  EXPECT_TRUE(::CanonicalizePath(buf, &size, &slash_bits, &err));
+  ::CanonicalizePath(buf, &size, &slash_bits);
   EXPECT_EQ(0, strncmp("foo/bar/baz.h", buf, size));
   EXPECT_EQ(2, slash_bits);  // Not including the trailing one.
 }
 
 TEST(CanonicalizePath, TooManyComponents) {
   string path;
-  string err;
   uint64_t slash_bits;
 
   // 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));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ(slash_bits, 0x0);
 
   // Backslashes version.
@@ -291,44 +286,40 @@
       "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));
+  CanonicalizePath(&path, &slash_bits);
   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/./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));
+  CanonicalizePath(&path, &slash_bits);
   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\\.\\x\\y.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err));
+  CanonicalizePath(&path, &slash_bits);
   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));
+  CanonicalizePath(&path, &slash_bits);
   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));
+  CanonicalizePath(&path, &slash_bits);
   EXPECT_EQ(slash_bits, 0x3ffffffffffffff);
 }
 #endif
@@ -336,36 +327,35 @@
 TEST(CanonicalizePath, UpDir) {
   string path, err;
   path = "../../foo/bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("../../foo/bar.h", path);
 
   path = "test/../../foo/bar.h";
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("../foo/bar.h", path);
 }
 
 TEST(CanonicalizePath, AbsolutePath) {
   string path = "/usr/include/stdio.h";
   string err;
-  EXPECT_TRUE(CanonicalizePath(&path, &err));
+  CanonicalizePath(&path);
   EXPECT_EQ("/usr/include/stdio.h", path);
 }
 
 TEST(CanonicalizePath, NotNullTerminated) {
   string path;
-  string err;
   size_t len;
   uint64_t unused;
 
   path = "foo/. bar/.";
   len = strlen("foo/.");  // Canonicalize only the part before the space.
-  EXPECT_TRUE(CanonicalizePath(&path[0], &len, &unused, &err));
+  CanonicalizePath(&path[0], &len, &unused);
   EXPECT_EQ(strlen("foo"), len);
   EXPECT_EQ("foo/. bar/.", string(path));
 
   path = "foo/../file bar/.";
   len = strlen("foo/../file");
-  EXPECT_TRUE(CanonicalizePath(&path[0], &len, &unused, &err));
+  CanonicalizePath(&path[0], &len, &unused);
   EXPECT_EQ(strlen("file"), len);
   EXPECT_EQ("file ./file bar/.", string(path));
 }
diff --git a/src/version.cc b/src/version.cc
index 7fee744..34167b6 100644
--- a/src/version.cc
+++ b/src/version.cc
@@ -20,7 +20,7 @@
 
 using namespace std;
 
-const char* kNinjaVersion = "1.10.2";
+const char* kNinjaVersion = "1.11.0";
 
 void ParseVersion(const string& version, int* major, int* minor) {
   size_t end = version.find('.');
diff --git a/windows/ninja.manifest b/windows/ninja.manifest
new file mode 100644
index 0000000..dab929e
--- /dev/null
+++ b/windows/ninja.manifest
@@ -0,0 +1,8 @@
+<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
+<assembly manifestVersion="1.0" xmlns="urn:schemas-microsoft-com:asm.v1">
+  <application>
+    <windowsSettings>
+      <activeCodePage xmlns="http://schemas.microsoft.com/SMI/2019/WindowsSettings">UTF-8</activeCodePage>
+    </windowsSettings>
+  </application>
+</assembly>