v1.11.0v1.11.0

63 files changed, 3434 insertions, 922 deletions

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 @@ jobs:
       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 @@ jobs:
     - 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 @@ jobs:
       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 @@ jobs:
     - 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 @@ endif()
 # --- 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 @@ if(RE2C)
 	# 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 @@ target_include_directories(libninja-re2c PRIVATE src)
 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 @@ function(check_platform_supports_browse_mode RESULT)
 	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 @@ add_library(libninja OBJECT
 	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 @@ if(WIN32)
 		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 @@ endif()
 # 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 @@ if(platform_supports_ninja_browse)
 		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 @@ if(platform_supports_ninja_browse)
 	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 @@ if(BUILD_TESTING)
     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(BUILD_TESTING)
 
   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 @@ to build Ninja with itself.
 ### 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 @@ class Platform(object):
         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 @@ def has_re2c():
         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 @@ for name in ['build',
              '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 @@ for name in ['build_log_test',
              '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 @@ than the _depth_ mode.
 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 @@ _Available since Ninja 1.2._
 `deps`:: show all dependencies stored in the `.ninja_deps` file. When given a
 target, show just the target's dependencies. _Available since Ninja 1.4._
 
+`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 @@ nothing, but phony rules are handled specially in that they aren't
 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 @@ A file is a series of declarations.  A declaration can be one of:
    Order-only dependencies may be tacked on the end with +||
    _dependency1_ _dependency2_+.  (See <<ref_dependencies,the reference on
    dependency types>>.)
+   Validations may be taked on the end with +|@ _validation1_ _validation2_+.
+   (See <<validations,the reference on validations>>.)
 +
 Implicit outputs _(available since Ninja 1.7)_ may be added before
 the `:` with +| _output1_ _output2_+ and do not appear in `$out`.
@@ -950,8 +1023,9 @@ source file of a compile command.
 +
 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 @@ express the implicit dependency.)
 File paths are compared as is, which means that an absolute path and a
 relative path, pointing to the same file, are considered different by Ninja.
 
+[[validations]]
+Validations
+~~~~~~~~~~~
+Validations listed on the build line cause the specified files to be
+added to the top level of the build graph (as if they were specified
+on the Ninja command line) whenever the build line is a transitive
+dependency of one of the targets specified on the command line or a
+default target.
+
+Validations are added to the build graph regardless of whether the output
+files of the build statement are dirty are not, and the dirty state of
+the build statement that outputs the file being used as a validation
+has no effect on the dirty state of the build statement that requested it.
+
+A build edge can list another build edge as a validation even if the second
+edge depends on the first.
+
+Validations are designed to handle rules that perform error checking but
+don't produce any artifacts needed by the build, for example static
+analysis tools.  Marking the static analysis rule as an implicit input
+of the main build rule of the source files or of the rules that depend
+on the main build rule would slow down the critical path of the build,
+but using a validation would allow the build to proceed in parallel with
+the static analysis rule once the main build rule is complete.
+
 Variable expansion
 ~~~~~~~~~~~~~~~~~~
 
diff --git a/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 @@ class Writer(object):
             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 @@ class Writer(object):
                                      ' '.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 @@ def run(build_ninja, flags='', pipe=False, env=default_env):
 
 @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 @@ red
 
     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 @@ class GenRandom(object):
     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 @@ class GenRandom(object):
     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 @@ class GenRandom(object):
     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 @@ def random_targets(num_targets, src_dir):
     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 @@ bool DryRunCommandRunner::WaitForCommand(Result* result) {
 
 }  // 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 @@ void Plan::Reset() {
   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 @@ void Plan::EdgeWanted(const Edge* edge) {
 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 @@ bool Plan::RefreshDyndepDependents(DependencyScan* scan, const Node* node,
     Node* n = *i;
 
     // Check if this dependent node is now dirty.  Also checks for new cycles.
-    if (!scan->RecomputeDirty(n, err))
+    std::vector<Node*> validation_nodes;
+    if (!scan->RecomputeDirty(n, &validation_nodes, err))
       return false;
+
+    // Add any validation nodes found during RecomputeDirty as new top level
+    // targets.
+    for (std::vector<Node*>::iterator v = validation_nodes.begin();
+         v != validation_nodes.end(); ++v) {
+      if (Edge* in_edge = (*v)->in_edge()) {
+        if (!in_edge->outputs_ready() &&
+            !AddTarget(*v, err)) {
+          return false;
+        }
+      }
+    }
     if (!n->dirty())
       continue;
 
@@ -729,12 +512,12 @@ bool RealCommandRunner::WaitForCommand(Result* result) {
 
 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 @@ void Builder::Cleanup() {
         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 @@ Node* Builder::AddTarget(const string& name, string* err) {
   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 @@ bool Builder::StartEdge(Edge* edge, string* err) {
   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 @@ bool Builder::FinishCommand(CommandRunner::Result* result, string* err) {
     }
   }
 
-  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 @@ bool Builder::FinishCommand(CommandRunner::Result* result, string* err) {
     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 @@ bool Builder::ExtractDeps(CommandRunner::Result* result,
     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 @@ struct Plan {
   /// 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 @@ private:
   /// we want for the edge.
   std::map<Edge*, Want> want_;
 
-  std::set<Edge*> ready_;
+  EdgeSet ready_;
 
   Builder* builder_;
 
@@ -162,8 +159,9 @@ struct BuildConfig {
                   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 BuildConfig {
 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,118 +220,26 @@ struct Builder {
 #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);
 
-  DiskInterface* disk_interface_;
-  DependencyScan scan_;
-
-  // Unimplemented copy ctor and operator= ensure we don't copy the auto_ptr.
-  Builder(const Builder &other);        // DO NOT IMPLEMENT
-  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_;
-  };
+  /// Time the build started.
+  int64_t start_time_millis_;
 
-  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_;
-  };
+  DiskInterface* disk_interface_;
+  DependencyScan scan_;
 
-  mutable RateInfo overall_rate_;
-  mutable SlidingRateInfo current_rate_;
+  // Unimplemented copy ctor and operator= ensure we don't copy the auto_ptr.
+  Builder(const Builder &other);        // DO NOT IMPLEMENT
+  void operator=(const Builder &other); // DO NOT IMPLEMENT
 };
 
 #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 @@ int main() {
   {
     // 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 @@ int main() {
   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 @@ int main() {
 
   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 FakeCommandRunner : public CommandRunner {
 };
 
 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 @@ struct BuildTest : public StateTestWithBuiltinRules, public BuildLogUser {
   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 @@ void BuildTest::RebuildTarget(const string& target, const char* manifest,
     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 @@ bool FakeCommandRunner::StartCommand(Edge* edge) {
     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 @@ TEST_F(BuildTest, MissingTarget) {
   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 @@ TEST_F(BuildTest, PhonySelfReference) {
   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 @@ struct BuildWithLogTest : public BuildTest {
   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 @@ TEST_F(BuildWithLogTest, RestatTest) {
   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 @@ TEST_F(BuildWithLogTest, RestatMissingInput) {
   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 @@ TEST_F(BuildTest, StatusFormatElapsed) {
   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 @@ struct BuildWithDepsLogTest : public BuildTest {
   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 @@ TEST_F(BuildWithDepsLogTest, Straightforward) {
     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 @@ TEST_F(BuildWithDepsLogTest, Straightforward) {
     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 @@ TEST_F(BuildWithDepsLogTest, ObsoleteDeps) {
     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 @@ TEST_F(BuildWithDepsLogTest, ObsoleteDeps) {
     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 @@ TEST_F(BuildWithDepsLogTest, DepsIgnoredInDryRun) {
 
   // 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 @@ TEST_F(BuildWithDepsLogTest, RestatDepfileDependencyDepsLog) {
     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 @@ TEST_F(BuildWithDepsLogTest, RestatDepfileDependencyDepsLog) {
     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 @@ TEST_F(BuildWithDepsLogTest, DepFileOKDepsLog) {
     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 @@ TEST_F(BuildWithDepsLogTest, DepFileOKDepsLog) {
     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, DepFileOKDepsLog) {
   }
 }
 
+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 @@ TEST_F(BuildWithDepsLogTest, DepFileDepsLogCanonicalize) {
     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 @@ TEST_F(BuildWithDepsLogTest, DepFileDepsLogCanonicalize) {
     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 @@ TEST_F(BuildTest, DyndepBuildDiscoverNewInput) {
   EXPECT_EQ("touch out", command_runner_.commands_ran_[2]);
 }
 
+TEST_F(BuildTest, DyndepBuildDiscoverNewInputWithValidation) {
+  // Verify that a dyndep file cannot contain the |@ validation
+  // syntax.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+));
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep |@ validation\n"
+);
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_FALSE(builder_.Build(&err));
+
+  string err_first_line = err.substr(0, err.find("\n"));
+  EXPECT_EQ("dd:2: expected newline, got '|@'", err_first_line);
+}
+
+TEST_F(BuildTest, DyndepBuildDiscoverNewInputWithTransitiveValidation) {
+  // Verify that a dyndep file can be built and loaded to discover
+  // a new input to an edge that has a validation edge.
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+"rule touch\n"
+"  command = touch $out\n"
+"rule cp\n"
+"  command = cp $in $out\n"
+"build dd: cp dd-in\n"
+"build in: touch |@ validation\n"
+"build validation: touch in out\n"
+"build out: touch || dd\n"
+"  dyndep = dd\n"
+  ));
+  fs_.Create("dd-in",
+"ninja_dyndep_version = 1\n"
+"build out: dyndep | in\n"
+);
+  fs_.Tick();
+  fs_.Create("out", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+  ASSERT_EQ(4u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cp dd-in dd", command_runner_.commands_ran_[0]);
+  EXPECT_EQ("touch in", command_runner_.commands_ran_[1]);
+  EXPECT_EQ("touch out", command_runner_.commands_ran_[2]);
+  EXPECT_EQ("touch validation", command_runner_.commands_ran_[3]);
+}
+
 TEST_F(BuildTest, DyndepBuildDiscoverImplicitConnection) {
   // Verify that a dyndep file can be built and loaded to discover
   // that one edge has an implicit output that is also an implicit
@@ -2933,6 +3330,48 @@ TEST_F(BuildTest, DyndepBuildDiscoverImplicitConnection) {
   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 @@ TEST_F(BuildTest, DyndepTwoLevelDiscoveredDirty) {
   EXPECT_EQ("touch tmp", command_runner_.commands_ran_[3]);
   EXPECT_EQ("touch out", command_runner_.commands_ran_[4]);
 }
+
+TEST_F(BuildTest, Validation) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ validate\n"
+    "build validate: cat in2\n"));
+
+  fs_.Create("in", "");
+  fs_.Create("in2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in" only rebuilds "out" ("validate" doesn't depend on
+  // "out").
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in > out", command_runner_.commands_ran_[0]);
+
+  // Test touching "in2" only rebuilds "validate" ("out" doesn't depend on
+  // "validate").
+  fs_.Tick();
+  fs_.Create("in2", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in2 > validate", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildTest, ValidationDependsOnOutput) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ validate\n"
+    "build validate: cat in2 | out\n"));
+
+  fs_.Create("in", "");
+  fs_.Create("in2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in" rebuilds "out" and "validate".
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in2" only rebuilds "validate" ("out" doesn't depend on
+  // "validate").
+  fs_.Tick();
+  fs_.Create("in2", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in2 > validate", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildWithDepsLogTest, ValidationThroughDepfile) {
+  const char* manifest =
+      "build out: cat in |@ validate\n"
+      "build validate: cat in2 | out\n"
+      "build out2: cat in3\n"
+      "  deps = gcc\n"
+      "  depfile = out2.d\n";
+
+  string err;
+
+  {
+    fs_.Create("in", "");
+    fs_.Create("in2", "");
+    fs_.Create("in3", "");
+    fs_.Create("out2.d", "out: out");
+
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
+    builder.command_runner_.reset(&command_runner_);
+
+    EXPECT_TRUE(builder.AddTarget("out2", &err));
+    ASSERT_EQ("", err);
+
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    // On the first build, only the out2 command is run.
+    ASSERT_EQ(command_runner_.commands_ran_.size(), 1);
+    EXPECT_EQ("cat in3 > out2", command_runner_.commands_ran_[0]);
+
+    // The deps file should have been removed.
+    EXPECT_EQ(0, fs_.Stat("out2.d", &err));
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+
+  fs_.Tick();
+  command_runner_.commands_ran_.clear();
+
+  {
+    fs_.Create("in2", "");
+    fs_.Create("in3", "");
+
+    State state;
+    ASSERT_NO_FATAL_FAILURE(AddCatRule(&state));
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, manifest));
+
+    DepsLog deps_log;
+    ASSERT_TRUE(deps_log.Load("ninja_deps", &state, &err));
+    ASSERT_TRUE(deps_log.OpenForWrite("ninja_deps", &err));
+    ASSERT_EQ("", err);
+
+    Builder builder(&state, config_, NULL, &deps_log, &fs_, &status_, 0);
+    builder.command_runner_.reset(&command_runner_);
+
+    EXPECT_TRUE(builder.AddTarget("out2", &err));
+    ASSERT_EQ("", err);
+
+    EXPECT_TRUE(builder.Build(&err));
+    EXPECT_EQ("", err);
+
+    // The out and validate actions should have been run as well as out2.
+    ASSERT_EQ(command_runner_.commands_ran_.size(), 3);
+    // out has to run first, as both out2 and validate depend on it.
+    EXPECT_EQ("cat in > out", command_runner_.commands_ran_[0]);
+
+    deps_log.Close();
+    builder.command_runner_.release();
+  }
+}
+
+TEST_F(BuildTest, ValidationCircular) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ out2\n"
+    "build out2: cat in2 |@ out\n"));
+
+  fs_.Create("in", "");
+  fs_.Create("in2", "");
+
+  string err;
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  EXPECT_EQ(2u, command_runner_.commands_ran_.size());
+
+  // Test touching "in" rebuilds "out".
+  fs_.Tick();
+  fs_.Create("in", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in > out", command_runner_.commands_ran_[0]);
+
+  // Test touching "in2" rebuilds "out2".
+  fs_.Tick();
+  fs_.Create("in2", "");
+
+  err.clear();
+  command_runner_.commands_ran_.clear();
+  state_.Reset();
+  EXPECT_TRUE(builder_.AddTarget("out", &err));
+  ASSERT_EQ("", err);
+
+  EXPECT_TRUE(builder_.Build(&err));
+  EXPECT_EQ("", err);
+
+  ASSERT_EQ(1u, command_runner_.commands_ran_.size());
+  EXPECT_EQ("cat in2 > out2", command_runner_.commands_ran_[0]);
+}
+
+TEST_F(BuildTest, ValidationWithCircularDependency) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
+    "build out: cat in |@ validate\n"
+    "build validate: cat validate_in | out\n"
+    "build validate_in: cat validate\n"));
+
+  fs_.Create("in", "");
+
+  string err;
+  EXPECT_FALSE(builder_.AddTarget("out", &err));
+  EXPECT_EQ("dependency cycle: validate -> validate_in -> validate", err);
+}
diff --git a/src/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 @@ const char kPath[] =
 
 int main() {
   vector<int> times;
-  string err;
 
   char buf[200];
   size_t len = strlen(kPath);
@@ -37,7 +36,7 @@ int main() {
     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 @@ int Cleaner::CleanDead(const BuildLog::Entries& entries) {
   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 @@ int Cleaner::CleanTargets(int target_count, char* targets[]) {
   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 @@ TEST_F(CleanDeadTest, CleanDead) {
   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 @@ bool CLParser::FilterInputFilename(string line) {
   return EndsWith(line, ".c") ||
       EndsWith(line, ".cc") ||
       EndsWith(line, ".cxx") ||
-      EndsWith(line, ".cpp");
+      EndsWith(line, ".cpp") ||
+      EndsWith(line, ".c++");
 }
 
 // static
@@ -83,6 +84,7 @@ bool CLParser::Parse(const string& output, const string& deps_prefix,
   // 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 @@ bool CLParser::Parse(const string& output, const string& deps_prefix,
 
     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 @@ bool CLParser::Parse(const string& output, const string& deps_prefix,
       // 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 @@ TEST(CLParserTest, ParseFilenameFilter) {
   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 @@ DepsLog::Deps* DepsLog::GetDeps(Node* node) {
   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 @@ struct DepsLog {
   };
   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 @@ TEST_F(DepsLogTest, Truncated) {
     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, TruncatedRecovery) {
   }
 }
 
+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 @@ TimeStamp RealDiskInterface::Stat(const string& path, string* err) const {
     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 @@ FileReader::Status RealDiskInterface::ReadFile(const string& path,
 }
 
 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 @@ int RealDiskInterface::RemoveFile(const string& path) {
         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 @@ TEST_F(DiskInterfaceTest, RemoveFile) {
   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 @@ TEST_F(StatTest, Simple) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_EQ(2u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_EQ("in",  stats_[1]);
@@ -274,7 +288,7 @@ TEST_F(StatTest, TwoStep) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_EQ(3u, stats_.size());
   ASSERT_EQ("out", stats_[0]);
   ASSERT_TRUE(GetNode("out")->dirty());
@@ -294,7 +308,7 @@ TEST_F(StatTest, Tree) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_EQ(1u + 6u, stats_.size());
   ASSERT_EQ("mid1", stats_[1]);
   ASSERT_TRUE(GetNode("mid1")->dirty());
@@ -315,7 +329,7 @@ TEST_F(StatTest, Middle) {
   EXPECT_TRUE(out->Stat(this, &err));
   EXPECT_EQ("", err);
   ASSERT_EQ(1u, stats_.size());
-  scan_.RecomputeDirty(out, NULL);
+  scan_.RecomputeDirty(out, NULL, NULL);
   ASSERT_FALSE(GetNode("in")->dirty());
   ASSERT_TRUE(GetNode("mid")->dirty());
   ASSERT_TRUE(GetNode("out")->dirty());
diff --git a/src/dyndep.cc b/src/dyndep.cc
index b388e9b..dd4ed09 100644
--- a/src/dyndep.cc
+++ b/src/dyndep.cc
@@ -97,9 +97,15 @@ bool DyndepLoader::UpdateEdge(Edge* edge, Dyndeps const* dyndeps,
   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 @@ bool DyndepParser::ParseEdge(string* err) {
       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 @@ bool DyndepParser::ParseEdge(string* err) {
   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 @@ bool DyndepParser::ParseEdge(string* err) {
   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 @@ private:
   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 @@ bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
     //   Later during the build the dyndep file will become ready and be
     //   loaded to update this edge before it can possibly be scheduled.
     if (edge->dyndep_ && edge->dyndep_->dyndep_pending()) {
-      if (!RecomputeDirty(edge->dyndep_, stack, err))
+      if (!RecomputeNodeDirty(edge->dyndep_, stack, validation_nodes, err))
         return false;
 
       if (!edge->dyndep_->in_edge() ||
@@ -115,12 +157,20 @@ bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack,
     }
   }
 
+  // Store any validation nodes from the edge for adding to the initial
+  // nodes.  Don't recurse into them, that would trigger the dependency
+  // cycle detector if the validation node depends on this node.
+  // RecomputeDirty will add the validation nodes to the initial nodes
+  // and recurse into them.
+  validation_nodes->insert(validation_nodes->end(),
+      edge->validations_.begin(), edge->validations_.end());
+
   // Visit all inputs; we're dirty if any of the inputs are dirty.
   Node* most_recent_input = NULL;
   for (vector<Node*>::iterator i = edge->inputs_.begin();
        i != edge->inputs_.end(); ++i) {
     // Visit this input.
-    if (!RecomputeDirty(*i, stack, err))
+    if (!RecomputeNodeDirty(*i, stack, validation_nodes, err))
       return false;
 
     // If an input is not ready, neither are our outputs.
@@ -237,6 +287,14 @@ bool DependencyScan::RecomputeOutputDirty(const Edge* edge,
               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 @@ std::string EdgeEnv::MakePathList(const Node* const* const span,
   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 @@ void Edge::Dump(const char* prefix) const {
        i != outputs_.end() && *i != NULL; ++i) {
     printf("%s ", (*i)->path().c_str());
   }
+  if (!validations_.empty()) {
+    printf(" validations ");
+    for (std::vector<Node*>::const_iterator i = validations_.begin();
+         i != validations_.end() && *i != NULL; ++i) {
+      printf("%s ", (*i)->path().c_str());
+    }
+  }
   if (pool_) {
     if (!pool_->name().empty()) {
       printf("(in pool '%s')", pool_->name().c_str());
@@ -487,7 +574,7 @@ string Node::PathDecanonicalized(const string& path, uint64_t slash_bits) {
 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 @@ void Node::Dump(const char* prefix) const {
        e != out_edges().end() && *e != NULL; ++e) {
     (*e)->Dump(" +- ");
   }
+  if (!validation_out_edges().empty()) {
+    printf(" validation out edges:\n");
+    for (std::vector<Edge*>::const_iterator e = validation_out_edges().begin();
+         e != validation_out_edges().end() && *e != NULL; ++e) {
+      (*e)->Dump(" +- ");
+    }
+  }
 }
 
 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
@@ -515,7 +609,7 @@ bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
 }
 
 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 @@ bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
 
   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 @@ bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
     }
   }
 
+  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 @@ void ImplicitDepLoader::CreatePhonyInEdge(Node* node) {
     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 @@ struct Node {
       : path_(path),
         slash_bits_(slash_bits),
         mtime_(-1),
+        exists_(ExistenceStatusUnknown),
         dirty_(false),
         dyndep_pending_(false),
         in_edge_(NULL),
@@ -47,6 +50,9 @@ struct Node {
   /// 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 @@ struct Node {
   /// 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 @@ struct Node {
   void set_id(int id) { id_ = id; }
 
   const std::vector<Edge*>& out_edges() const { return out_edges_; }
+  const std::vector<Edge*>& validation_out_edges() const { return validation_out_edges_; }
   void AddOutEdge(Edge* edge) { out_edges_.push_back(edge); }
+  void AddValidationOutEdge(Edge* edge) { validation_out_edges_.push_back(edge); }
 
   void Dump(const char* prefix="") const;
 
@@ -112,9 +124,19 @@ private:
   /// 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 @@ private:
   /// All Edges that use this Node as an input.
   std::vector<Edge*> out_edges_;
 
+  /// All Edges that use this Node as a validation.
+  std::vector<Edge*> validation_out_edges_;
+
   /// A dense integer id for the node, assigned and used by DepsLog.
   int id_;
 };
@@ -143,10 +168,11 @@ struct Edge {
     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 @@ struct Edge {
 
   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 @@ struct Edge {
   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 @@ struct ImplicitDepLoader {
     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 @@ struct DependencyScan {
         dep_loader_(state, deps_log, disk_interface, depfile_parser_options),
         dyndep_loader_(state, disk_interface) {}
 
-  /// Update the |dirty_| state of the given node by inspecting its input edge.
+  /// Update the |dirty_| state of the given nodes by transitively inspecting
+  /// their input edges.
   /// Examine inputs, outputs, and command lines to judge whether an edge
   /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
   /// state accordingly.
+  /// Appends any validation nodes found to the nodes parameter.
   /// Returns false on failure.
-  bool RecomputeDirty(Node* node, std::string* err);
+  bool RecomputeDirty(Node* node, std::vector<Node*>* validation_nodes, std::string* err);
 
   /// Recompute whether any output of the edge is dirty, if so sets |*dirty|.
   /// Returns false on failure.
@@ -304,7 +351,8 @@ struct DependencyScan {
   bool LoadDyndeps(Node* node, DyndepFile* ddf, std::string* err) const;
 
  private:
-  bool RecomputeDirty(Node* node, std::vector<Node*>* stack, std::string* err);
+  bool RecomputeNodeDirty(Node* node, std::vector<Node*>* stack,
+                          std::vector<Node*>* validation_nodes, std::string* err);
   bool VerifyDAG(Node* node, std::vector<Node*>* stack, std::string* err);
 
   /// Recompute whether a given single output should be marked dirty.
diff --git a/src/graph_test.cc b/src/graph_test.cc
index 14f6375..9dba8af 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -33,7 +33,7 @@ TEST_F(GraphTest, MissingImplicit) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   // A missing implicit dep *should* make the output dirty.
@@ -51,7 +51,7 @@ TEST_F(GraphTest, ModifiedImplicit) {
   fs_.Create("implicit", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   // A modified implicit dep should make the output dirty.
@@ -71,7 +71,7 @@ TEST_F(GraphTest, FunkyMakefilePath) {
   fs_.Create("implicit.h", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   // implicit.h has changed, though our depfile refers to it with a
@@ -94,7 +94,7 @@ TEST_F(GraphTest, ExplicitImplicit) {
   fs_.Create("data", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   // We have both an implicit and an explicit dep on implicit.h.
@@ -122,7 +122,7 @@ TEST_F(GraphTest, ImplicitOutputMissing) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -138,7 +138,7 @@ TEST_F(GraphTest, ImplicitOutputOutOfDate) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out")->dirty());
@@ -162,7 +162,7 @@ TEST_F(GraphTest, ImplicitOutputOnlyMissing) {
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -176,7 +176,7 @@ TEST_F(GraphTest, ImplicitOutputOnlyOutOfDate) {
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("out.imp")->dirty());
@@ -193,7 +193,7 @@ TEST_F(GraphTest, PathWithCurrentDirectory) {
   fs_.Create("out.o", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -215,6 +215,39 @@ TEST_F(GraphTest, RootNodes) {
   }
 }
 
+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 @@ TEST_F(GraphTest, DepfileWithCanonicalizablePath) {
   fs_.Create("out.o", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("out.o")->dirty());
@@ -261,13 +294,13 @@ TEST_F(GraphTest, DepfileRemoved) {
   fs_.Create("out.o", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
   EXPECT_FALSE(GetNode("out.o")->dirty());
 
   state_.Reset();
   fs_.RemoveFile("out.o.d");
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), NULL, &err));
   ASSERT_EQ("", err);
   EXPECT_TRUE(GetNode("out.o")->dirty());
 }
@@ -314,7 +347,7 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) {
 "build n2: phony n1\n"
   );
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), NULL, &err));
   ASSERT_EQ("", err);
 
   Plan plan_;
@@ -333,7 +366,7 @@ TEST_F(GraphTest, PhonySelfReferenceError) {
   parser_opts);
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> a [-w phonycycle=err]", err);
 }
 
@@ -345,7 +378,7 @@ TEST_F(GraphTest, DependencyCycle) {
 "build pre: cat out\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err);
 }
 
@@ -353,7 +386,7 @@ TEST_F(GraphTest, CycleInEdgesButNotInNodes1) {
   string err;
   AssertParse(&state_,
 "build a b: cat a\n");
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> a", err);
 }
 
@@ -361,7 +394,7 @@ TEST_F(GraphTest, CycleInEdgesButNotInNodes2) {
   string err;
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build b a: cat a\n"));
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> a", err);
 }
 
@@ -370,7 +403,7 @@ TEST_F(GraphTest, CycleInEdgesButNotInNodes3) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 "build a b: cat c\n"
 "build c: cat a\n"));
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> c -> a", err);
 }
 
@@ -382,7 +415,7 @@ TEST_F(GraphTest, CycleInEdgesButNotInNodes4) {
 "build b: cat a\n"
 "build a e: cat d\n"
 "build f: cat e\n"));
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), NULL, &err));
   ASSERT_EQ("dependency cycle: a -> d -> c -> b -> a", err);
 }
 
@@ -398,7 +431,7 @@ TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) {
   fs_.Create("dep.d", "a: b\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), NULL, &err));
   ASSERT_EQ("dependency cycle: b -> b", err);
 
   // Despite the depfile causing edge to be a cycle (it has outputs a and b,
@@ -423,7 +456,7 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfile) {
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), NULL, &err));
   ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
@@ -450,7 +483,7 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) {
   fs_.Create("dep.d", "a: c\n");
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), NULL, &err));
   ASSERT_EQ("dependency cycle: b -> c -> b", err);
 
   // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b,
@@ -511,6 +544,37 @@ TEST_F(GraphTest, DyndepLoadTrivial) {
   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 @@ TEST_F(GraphTest, DyndepFileMissing) {
   );
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("loading 'dd': No such file or directory", err);
 }
 
@@ -690,7 +754,7 @@ TEST_F(GraphTest, DyndepFileError) {
   );
 
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("'out' not mentioned in its dyndep file 'dd'", err);
 }
 
@@ -710,7 +774,7 @@ TEST_F(GraphTest, DyndepImplicitInputNewer) {
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("in")->dirty());
@@ -738,7 +802,7 @@ TEST_F(GraphTest, DyndepFileReady) {
   fs_.Create("in", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("in")->dirty());
@@ -763,7 +827,7 @@ TEST_F(GraphTest, DyndepFileNotClean) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("dd")->dirty());
@@ -789,7 +853,7 @@ TEST_F(GraphTest, DyndepFileNotReady) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_FALSE(GetNode("dd")->dirty());
@@ -817,7 +881,7 @@ TEST_F(GraphTest, DyndepFileSecondNotReady) {
   fs_.Create("out", "");
 
   string err;
-  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   ASSERT_EQ("", err);
 
   EXPECT_TRUE(GetNode("dd1")->dirty());
@@ -846,7 +910,7 @@ TEST_F(GraphTest, DyndepFileCircular) {
 
   Edge* edge = GetNode("out")->in_edge();
   string err;
-  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err));
+  EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), NULL, &err));
   EXPECT_EQ("dependency cycle: circ -> in -> circ", err);
 
   // Verify that "out.d" was loaded exactly once despite
@@ -858,3 +922,58 @@ TEST_F(GraphTest, DyndepFileCircular) {
   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 @@ struct GraphViz {
 
   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 @@ bool IsPathSeparator(char c) {
 }
 
 // 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 @@ bool IncludesNormalize::Normalize(const string& input,
   }
   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 @@ const char* Lexer::TokenName(Token t) {
   case NEWLINE:  return "newline";
   case PIPE2:    return "'||'";
   case PIPE:     return "'|'";
+  case PIPEAT:   return "'|@'";
   case POOL:     return "'pool'";
   case RULE:     return "'rule'";
   case SUBNINJA: return "'subninja'";
@@ -291,7 +292,8 @@ yy25:
 	goto yy14;
 yy26:
 	yych = *++p;
-	if (yych == '|') goto yy42;
+	if (yych == '@') goto yy42;
+	if (yych == '|') goto yy44;
 	{ token = PIPE;     break; }
 yy28:
 	++p;
@@ -317,126 +319,129 @@ yy33:
 	{ continue; }
 yy36:
 	yych = *++p;
-	if (yych == 'i') goto yy44;
+	if (yych == 'i') goto yy46;
 	goto yy14;
 yy37:
 	yych = *++p;
-	if (yych == 'f') goto yy45;
+	if (yych == 'f') goto yy47;
 	goto yy14;
 yy38:
 	yych = *++p;
-	if (yych == 'c') goto yy46;
+	if (yych == 'c') goto yy48;
 	goto yy14;
 yy39:
 	yych = *++p;
-	if (yych == 'o') goto yy47;
+	if (yych == 'o') goto yy49;
 	goto yy14;
 yy40:
 	yych = *++p;
-	if (yych == 'l') goto yy48;
+	if (yych == 'l') goto yy50;
 	goto yy14;
 yy41:
 	yych = *++p;
-	if (yych == 'b') goto yy49;
+	if (yych == 'b') goto yy51;
 	goto yy14;
 yy42:
 	++p;
-	{ token = PIPE2;    break; }
+	{ token = PIPEAT;   break; }
 yy44:
-	yych = *++p;
-	if (yych == 'l') goto yy50;
-	goto yy14;
-yy45:
-	yych = *++p;
-	if (yych == 'a') goto yy51;
-	goto yy14;
+	++p;
+	{ token = PIPE2;    break; }
 yy46:
 	yych = *++p;
 	if (yych == 'l') goto yy52;
 	goto yy14;
 yy47:
 	yych = *++p;
-	if (yych == 'l') goto yy53;
+	if (yych == 'a') goto yy53;
 	goto yy14;
 yy48:
 	yych = *++p;
-	if (yych == 'e') goto yy55;
+	if (yych == 'l') goto yy54;
 	goto yy14;
 yy49:
 	yych = *++p;
-	if (yych == 'n') goto yy57;
+	if (yych == 'l') goto yy55;
 	goto yy14;
 yy50:
 	yych = *++p;
-	if (yych == 'd') goto yy58;
+	if (yych == 'e') goto yy57;
 	goto yy14;
 yy51:
 	yych = *++p;
-	if (yych == 'u') goto yy60;
+	if (yych == 'n') goto yy59;
 	goto yy14;
 yy52:
 	yych = *++p;
-	if (yych == 'u') goto yy61;
+	if (yych == 'd') goto yy60;
 	goto yy14;
 yy53:
 	yych = *++p;
+	if (yych == 'u') goto yy62;
+	goto yy14;
+yy54:
+	yych = *++p;
+	if (yych == 'u') goto yy63;
+	goto yy14;
+yy55:
+	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = POOL;     break; }
-yy55:
+yy57:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = RULE;     break; }
-yy57:
+yy59:
 	yych = *++p;
-	if (yych == 'i') goto yy62;
+	if (yych == 'i') goto yy64;
 	goto yy14;
-yy58:
+yy60:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = BUILD;    break; }
-yy60:
-	yych = *++p;
-	if (yych == 'l') goto yy63;
-	goto yy14;
-yy61:
-	yych = *++p;
-	if (yych == 'd') goto yy64;
-	goto yy14;
 yy62:
 	yych = *++p;
-	if (yych == 'n') goto yy65;
+	if (yych == 'l') goto yy65;
 	goto yy14;
 yy63:
 	yych = *++p;
-	if (yych == 't') goto yy66;
+	if (yych == 'd') goto yy66;
 	goto yy14;
 yy64:
 	yych = *++p;
-	if (yych == 'e') goto yy68;
+	if (yych == 'n') goto yy67;
 	goto yy14;
 yy65:
 	yych = *++p;
-	if (yych == 'j') goto yy70;
+	if (yych == 't') goto yy68;
 	goto yy14;
 yy66:
 	yych = *++p;
+	if (yych == 'e') goto yy70;
+	goto yy14;
+yy67:
+	yych = *++p;
+	if (yych == 'j') goto yy72;
+	goto yy14;
+yy68:
+	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = DEFAULT;  break; }
-yy68:
+yy70:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
 		goto yy13;
 	}
 	{ token = INCLUDE;  break; }
-yy70:
+yy72:
 	yych = *++p;
 	if (yych != 'a') goto yy14;
 	yych = *++p;
@@ -507,38 +512,38 @@ void Lexer::EatWhitespace() {
 	};
 	yych = *p;
 	if (yybm[0+yych] & 128) {
-		goto yy79;
+		goto yy81;
 	}
-	if (yych <= 0x00) goto yy75;
-	if (yych == '$') goto yy82;
-	goto yy77;
-yy75:
-	++p;
-	{ break; }
+	if (yych <= 0x00) goto yy77;
+	if (yych == '$') goto yy84;
+	goto yy79;
 yy77:
 	++p;
-yy78:
 	{ break; }
 yy79:
+	++p;
+yy80:
+	{ break; }
+yy81:
 	yych = *++p;
 	if (yybm[0+yych] & 128) {
-		goto yy79;
+		goto yy81;
 	}
 	{ continue; }
-yy82:
+yy84:
 	yych = *(q = ++p);
-	if (yych == '\n') goto yy83;
-	if (yych == '\r') goto yy85;
-	goto yy78;
-yy83:
+	if (yych == '\n') goto yy85;
+	if (yych == '\r') goto yy87;
+	goto yy80;
+yy85:
 	++p;
 	{ continue; }
-yy85:
+yy87:
 	yych = *++p;
-	if (yych == '\n') goto yy87;
+	if (yych == '\n') goto yy89;
 	p = q;
-	goto yy78;
-yy87:
+	goto yy80;
+yy89:
 	++p;
 	{ continue; }
 }
@@ -590,17 +595,17 @@ bool Lexer::ReadIdent(string* out) {
 	};
 	yych = *p;
 	if (yybm[0+yych] & 128) {
-		goto yy93;
+		goto yy95;
 	}
 	++p;
 	{
       last_token_ = start;
       return false;
     }
-yy93:
+yy95:
 	yych = *++p;
 	if (yybm[0+yych] & 128) {
-		goto yy93;
+		goto yy95;
 	}
 	{
       out->assign(start, p - start);
@@ -660,33 +665,33 @@ bool Lexer::ReadEvalString(EvalString* eval, bool path, string* err) {
 	};
 	yych = *p;
 	if (yybm[0+yych] & 16) {
-		goto yy100;
+		goto yy102;
 	}
 	if (yych <= '\r') {
-		if (yych <= 0x00) goto yy98;
-		if (yych <= '\n') goto yy103;
-		goto yy105;
+		if (yych <= 0x00) goto yy100;
+		if (yych <= '\n') goto yy105;
+		goto yy107;
 	} else {
-		if (yych <= ' ') goto yy103;
-		if (yych <= '$') goto yy107;
-		goto yy103;
+		if (yych <= ' ') goto yy105;
+		if (yych <= '$') goto yy109;
+		goto yy105;
 	}
-yy98:
+yy100:
 	++p;
 	{
       last_token_ = start;
       return Error("unexpected EOF", err);
     }
-yy100:
+yy102:
 	yych = *++p;
 	if (yybm[0+yych] & 16) {
-		goto yy100;
+		goto yy102;
 	}
 	{
       eval->AddText(StringPiece(start, p - start));
       continue;
     }
-yy103:
+yy105:
 	++p;
 	{
       if (path) {
@@ -699,112 +704,112 @@ yy103:
         continue;
       }
     }
-yy105:
+yy107:
 	yych = *++p;
-	if (yych == '\n') goto yy108;
+	if (yych == '\n') goto yy110;
 	{
       last_token_ = start;
       return Error(DescribeLastError(), err);
     }
-yy107:
+yy109:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
-		goto yy120;
+		goto yy122;
 	}
 	if (yych <= ' ') {
 		if (yych <= '\f') {
-			if (yych == '\n') goto yy112;
-			goto yy110;
+			if (yych == '\n') goto yy114;
+			goto yy112;
 		} else {
-			if (yych <= '\r') goto yy115;
-			if (yych <= 0x1F) goto yy110;
-			goto yy116;
+			if (yych <= '\r') goto yy117;
+			if (yych <= 0x1F) goto yy112;
+			goto yy118;
 		}
 	} else {
 		if (yych <= '/') {
-			if (yych == '$') goto yy118;
-			goto yy110;
+			if (yych == '$') goto yy120;
+			goto yy112;
 		} else {
-			if (yych <= ':') goto yy123;
-			if (yych <= '`') goto yy110;
-			if (yych <= '{') goto yy125;
-			goto yy110;
+			if (yych <= ':') goto yy125;
+			if (yych <= '`') goto yy112;
+			if (yych <= '{') goto yy127;
+			goto yy112;
 		}
 	}
-yy108:
+yy110:
 	++p;
 	{
       if (path)
         p = start;
       break;
     }
-yy110:
+yy112:
 	++p;
-yy111:
+yy113:
 	{
       last_token_ = start;
       return Error("bad $-escape (literal $ must be written as $$)", err);
     }
-yy112:
+yy114:
 	yych = *++p;
 	if (yybm[0+yych] & 32) {
-		goto yy112;
+		goto yy114;
 	}
 	{
       continue;
     }
-yy115:
+yy117:
 	yych = *++p;
-	if (yych == '\n') goto yy126;
-	goto yy111;
-yy116:
+	if (yych == '\n') goto yy128;
+	goto yy113;
+yy118:
 	++p;
 	{
       eval->AddText(StringPiece(" ", 1));
       continue;
     }
-yy118:
+yy120:
 	++p;
 	{
       eval->AddText(StringPiece("$", 1));
       continue;
     }
-yy120:
+yy122:
 	yych = *++p;
 	if (yybm[0+yych] & 64) {
-		goto yy120;
+		goto yy122;
 	}
 	{
       eval->AddSpecial(StringPiece(start + 1, p - start - 1));
       continue;
     }
-yy123:
+yy125:
 	++p;
 	{
       eval->AddText(StringPiece(":", 1));
       continue;
     }
-yy125:
+yy127:
 	yych = *(q = ++p);
 	if (yybm[0+yych] & 128) {
-		goto yy129;
+		goto yy131;
 	}
-	goto yy111;
-yy126:
+	goto yy113;
+yy128:
 	yych = *++p;
-	if (yych == ' ') goto yy126;
+	if (yych == ' ') goto yy128;
 	{
       continue;
     }
-yy129:
+yy131:
 	yych = *++p;
 	if (yybm[0+yych] & 128) {
-		goto yy129;
+		goto yy131;
 	}
-	if (yych == '}') goto yy132;
+	if (yych == '}') goto yy134;
 	p = q;
-	goto yy111;
-yy132:
+	goto yy113;
+yy134:
 	++p;
 	{
       eval->AddSpecial(StringPiece(start + 2, p - start - 3));
diff --git a/src/lexer.h b/src/lexer.h
index 788d948..683fd6c 100644
--- a/src/lexer.h
+++ b/src/lexer.h
@@ -41,6 +41,7 @@ struct Lexer {
     NEWLINE,
     PIPE,
     PIPE2,
+    PIPEAT,
     POOL,
     RULE,
     SUBNINJA,
diff --git a/src/lexer.in.cc b/src/lexer.in.cc
index 88007e7..6f1d8e7 100644
--- a/src/lexer.in.cc
+++ b/src/lexer.in.cc
@@ -84,6 +84,7 @@ const char* Lexer::TokenName(Token t) {
   case NEWLINE:  return "newline";
   case PIPE2:    return "'||'";
   case PIPE:     return "'|'";
+  case PIPEAT:   return "'|@'";
   case POOL:     return "'pool'";
   case RULE:     return "'rule'";
   case SUBNINJA: return "'subninja'";
@@ -142,6 +143,7 @@ Lexer::Token Lexer::ReadToken() {
     "default"  { token = DEFAULT;  break; }
     "="        { token = EQUALS;   break; }
     ":"        { token = COLON;    break; }
+    "|@"       { token = PIPEAT;   break; }
     "||"       { token = PIPE2;    break; }
     "|"        { token = PIPE;     break; }
     "include"  { token = INCLUDE;  break; }
diff --git a/src/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 @@ LinePrinter::LinePrinter() : have_blank_line_(true), console_locked_(false) {
 #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 @@ void LinePrinter::Print(string to_print, LineType type) {
     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 @@ bool ManifestParser::ParseDefault(string* err) {
 
   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 @@ bool ManifestParser::ParseEdge(string* err) {
     }
   }
 
+  // Add all validations, counting how many as we go.
+  if (lexer_.PeekToken(Lexer::PIPEAT)) {
+    for (;;) {
+      EvalString validation;
+      if (!lexer_.ReadPath(&validation, err))
+        return false;
+      if (validation.empty())
+        break;
+      validations.push_back(validation);
+    }
+  }
+
   if (!ExpectToken(Lexer::NEWLINE, err))
     return false;
 
@@ -320,27 +330,27 @@ bool ManifestParser::ParseEdge(string* err) {
   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 @@ bool ManifestParser::ParseEdge(string* err) {
   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 @@ bool ManifestParser::ParseEdge(string* err) {
   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 @@ TEST_F(ParserTest, DuplicateEdgeWithMultipleOutputsError) {
   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 @@ TEST_F(ParserTest, DuplicateEdgeInIncludedFile) {
   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 @@ TEST_F(ParserTest, OrderOnly) {
   ASSERT_TRUE(edge->is_order_only(1));
 }
 
+TEST_F(ParserTest, Validations) {
+  ASSERT_NO_FATAL_FAILURE(AssertParse(
+"rule cat\n  command = cat $in > $out\n"
+"build foo: cat bar |@ baz\n"));
+
+  Edge* edge = state.LookupNode("foo")->in_edge();
+  ASSERT_EQ(edge->validations_.size(), 1);
+  EXPECT_EQ(edge->validations_[0]->path(), "baz");
+}
+
 TEST_F(ParserTest, ImplicitOutput) {
   ASSERT_NO_FATAL_FAILURE(AssertParse(
 "rule cat\n"
diff --git a/src/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 @@ struct Options {
 /// 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 @@ struct NinjaMain : public BuildLogUser {
   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 @@ struct NinjaMain : public BuildLogUser {
   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 @@ struct NinjaMain : public BuildLogUser {
   /// 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 @@ struct NinjaMain : public BuildLogUser {
       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 @@ void Usage(const BuildConfig& config) {
 "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 @@ int GuessParallelism() {
 
 /// 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 @@ bool NinjaMain::RebuildManifest(const char* input_file, string* err) {
 
 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 @@ Node* NinjaMain::CollectTarget(const char* cpath, string* err) {
   if (node) {
     if (first_dependent) {
       if (node->out_edges().empty()) {
-        *err = "'" + path + "' has no out edge";
-        return NULL;
-      }
-      Edge* edge = node->out_edges()[0];
-      if (edge->outputs_.empty()) {
-        edge->Dump();
-        Fatal("edge has no outputs");
+        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];
       }
-      node = edge->outputs_[0];
     }
     return node;
   } else {
@@ -381,6 +407,13 @@ int NinjaMain::ToolQuery(const Options* options, int argc, char* argv[]) {
           label = "|| ";
         printf("    %s%s\n", label, edge->inputs_[in]->path().c_str());
       }
+      if (!edge->validations_.empty()) {
+        printf("  validations:\n");
+        for (std::vector<Node*>::iterator validation = edge->validations_.begin();
+             validation != edge->validations_.end(); ++validation) {
+          printf("    %s\n", (*validation)->path().c_str());
+        }
+      }
     }
     printf("  outputs:\n");
     for (vector<Edge*>::const_iterator edge = node->out_edges().begin();
@@ -390,6 +423,17 @@ int NinjaMain::ToolQuery(const Options* options, int argc, char* argv[]) {
         printf("    %s\n", (*out)->path().c_str());
       }
     }
+    const std::vector<Edge*> validation_edges = node->validation_out_edges();
+    if (!validation_edges.empty()) {
+      printf("  validation for:\n");
+      for (std::vector<Edge*>::const_iterator edge = validation_edges.begin();
+           edge != validation_edges.end(); ++edge) {
+        for (vector<Node*>::iterator out = (*edge)->outputs_.begin();
+             out != (*edge)->outputs_.end(); ++out) {
+          printf("    %s\n", (*out)->path().c_str());
+        }
+      }
+    }
   }
   return 0;
 }
@@ -407,7 +451,7 @@ int NinjaMain::ToolBrowse(const Options*, int, char**) {
 }
 #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 @@ int NinjaMain::ToolDeps(const Options* options, int argc, char** argv) {
   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 @@ int NinjaMain::ToolRules(const Options* options, int argc, char* argv[]) {
   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 @@ void PrintCommands(Edge* edge, set<Edge*>* seen, PrintCommandMode mode) {
 }
 
 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 @@ int NinjaMain::ToolCommands(const Options* options, int argc, char* argv[]) {
     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 @@ int NinjaMain::ToolCleanDead(const Options* options, int argc, char* argv[]) {
   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 @@ std::string EvaluateCommandWithRspfile(const Edge* edge,
 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 @@ int NinjaMain::ToolRecompact(const Options* options, int argc, char* argv[]) {
   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 @@ const Tool* ChooseTool(const string& tool_name) {
   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 @@ const Tool* ChooseTool(const string& tool_name) {
       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 @@ const Tool* ChooseTool(const string& tool_name) {
     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 DebugEnable(const string& name) {
 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 @@ bool NinjaMain::EnsureBuildDirExists() {
   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 @@ int NinjaMain::RunBuild(int argc, char** argv) {
   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 @@ int ExceptionFilter(unsigned int code, struct _EXCEPTION_POINTERS *ep) {
 
 #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 @@ int ReadFlags(int* argc, char*** argv,
         // 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 @@ int ReadFlags(int* argc, char*** argv,
       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 @@ int ReadFlags(int* argc, char*** argv,
         return 0;
       case 'h':
       default:
+        deferGuessParallelism.Refresh();
         Usage(*config);
         return 1;
     }
@@ -1359,14 +1522,16 @@ NORETURN void real_main(int argc, char** argv) {
   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 @@ NORETURN void real_main(int argc, char** argv) {
     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 @@ NORETURN void real_main(int argc, char** argv) {
       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 @@ NORETURN void real_main(int argc, char** argv) {
       // 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 @@ void Usage() {
 "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 @@ void Pool::DelayEdge(Edge* edge) {
   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 @@ void Pool::Dump() const {
   }
 }
 
-// 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* State::AddEdge(const Rule* rule) {
   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::GetNode(StringPiece path, uint64_t slash_bits) {
 }
 
 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 @@ bool State::AddOut(Edge* edge, StringPiece path, uint64_t slash_bits) {
   return true;
 }
 
+void State::AddValidation(Edge* edge, StringPiece path, uint64_t slash_bits) {
+  Node* node = GetNode(path, slash_bits);
+  edge->validations_.push_back(node);
+  node->AddValidationOutEdge(edge);
+}
+
 bool State::AddDefault(StringPiece path, string* err) {
   Node* node = LookupNode(path);
   if (!node) {
diff --git a/src/state.h b/src/state.h
index 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 @@ struct Rule;
 /// 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 @@ struct Pool {
   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 @@ struct Pool {
   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 @@ struct State {
 
   void AddIn(Edge* edge, StringPiece path, uint64_t slash_bits);
   bool AddOut(Edge* edge, StringPiece path, uint64_t slash_bits);
+  void AddValidation(Edge* edge, StringPiece path, uint64_t slash_bits);
   bool AddDefault(StringPiece path, std::string* error);
 
   /// Reset state.  Keeps all nodes and edges, but restores them to the
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 @@ void Fatal(const char* msg, ...) {
 #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 @@ static bool IsPathSeparator(char c) {
 #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 @@ bool CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits,
 #else
   *slash_bits = 0;
 #endif
-  return true;
 }
 
 static inline bool IsKnownShellSafeCharacter(char ch) {
@@ -333,7 +353,8 @@ int ReadFile(const string& path, string* contents, string* err) {
     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 @@ string StripAnsiEscapeCodes(const string& in) {
   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 @@ double GetLoadAverage() {
     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 @@ NORETURN void Fatal(const char* msg, ...);
 
 /// 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 @@ using namespace std;
 
 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 @@ TEST(CanonicalizePath, PathSamples) {
 #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 @@ TEST(CanonicalizePath, CanonicalizeNotExceedingLen) {
   // 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 @@ TEST(CanonicalizePath, TooManyComponents) {
       "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, TooManyComponents) {
 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>