Revert "Revert "Merge remote-tracking branch 'aosp/upstream'""

This reverts commit ed8db98c45fca52926d6c1bf88bf9e6752e0c453.

20 files changed, 739 insertions, 314 deletions

diff --git a/Makefile.ckati b/Makefile.ckati
index 9c1f016..f35824b 100644
--- a/Makefile.ckati
+++ b/Makefile.ckati
@@ -38,6 +38,7 @@ KATI_CXX_SRCS := \
 	main.cc \
 	ninja.cc \
 	parser.cc \
+	regen.cc \
 	rule.cc \
 	stats.cc \
 	stmt.cc \
@@ -45,6 +46,7 @@ KATI_CXX_SRCS := \
 	stringprintf.cc \
 	strutil.cc \
 	symtab.cc \
+	thread.cc \
 	timeutil.cc \
 	var.cc
 
@@ -69,7 +71,7 @@ KATI_CXXFLAGS += -O -DNOLOG
 #KATI_CXXFLAGS += -pg
 
 ifeq ($(shell uname),Linux)
-KATI_LIBS := -lrt
+KATI_LIBS := -lrt -lpthread
 endif
 
 # Rule to build ckati into KATI_BIN_PATH
diff --git a/Makefile.kati b/Makefile.kati
index 7d0984f..9d3a894 100644
--- a/Makefile.kati
+++ b/Makefile.kati
@@ -25,7 +25,7 @@ kati: go_src_stamp
 	GOPATH=${KATI_GOPATH} go install -ldflags "-X github.com/google/kati.gitVersion $(shell git rev-parse HEAD)" github.com/google/kati/cmd/kati
 	cp out/bin/kati $@
 
-go_src_stamp: $(GO_SRCS) cmd/*/*.go
+go_src_stamp: $(GO_SRCS) $(wildcard cmd/*/*.go)
 	-rm -rf out/{src,pkg/*}/github.com/google/kati
 	mkdir -p out/{src,pkg/*}/github.com/google/kati
 	cp -a $(GO_SRCS) cmd out/src/github.com/google/kati
diff --git a/dep.cc b/dep.cc
index 94f501a..219593d 100644
--- a/dep.cc
+++ b/dep.cc
@@ -442,11 +442,9 @@ class DepBuilder {
         *out_rule = r;
         return true;
       }
-      if (vars) {
-        CHECK(irule->output_patterns.size() == 1);
-        vars = MergeImplicitRuleVars(irule->output_patterns[0], vars);
-        *out_var = vars;
-      }
+      CHECK(irule->output_patterns.size() == 1);
+      vars = MergeImplicitRuleVars(irule->output_patterns[0], vars);
+      *out_var = vars;
       *out_rule = irule;
       return true;
     }
diff --git a/fileutil.cc b/fileutil.cc
index abfad9d..42e81a2 100644
--- a/fileutil.cc
+++ b/fileutil.cc
@@ -20,6 +20,7 @@
 #include <fcntl.h>
 #include <glob.h>
 #include <limits.h>
+#include <signal.h>
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <sys/wait.h>
@@ -109,8 +110,10 @@ int RunCommand(const string& shell, const string& cmd,
       shell.c_str(), "-c", cmd.c_str(), NULL
     };
     execvp(argv[0], const_cast<char**>(argv));
+    PLOG("execvp for %s failed", argv[0]);
+    kill(getppid(), SIGTERM);
+    _exit(1);
   }
-  abort();
 }
 
 void GetExecutablePath(string* path) {
diff --git a/log.h b/log.h
index 6507bde..11cf0e5 100644
--- a/log.h
+++ b/log.h
@@ -44,9 +44,13 @@ extern string* g_last_error;
       fprintf(stderr, "*kati*: %s\n", StringPrintf(args).c_str());  \
   } while(0)
 
-#define PERROR(...) do {                                            \
+#define PLOG(...) do {                                              \
     fprintf(stderr, "%s: %s\n", StringPrintf(__VA_ARGS__).c_str(),  \
             strerror(errno));                                       \
+  } while (0)
+
+#define PERROR(...) do {                                            \
+    PLOG(__VA_ARGS__);                                              \
     exit(1);                                                        \
   } while (0)
 
diff --git a/main.cc b/main.cc
index ff2b751..a64a37e 100644
--- a/main.cc
+++ b/main.cc
@@ -33,6 +33,7 @@
 #include "log.h"
 #include "ninja.h"
 #include "parser.h"
+#include "regen.h"
 #include "stats.h"
 #include "stmt.h"
 #include "string_piece.h"
diff --git a/ninja.cc b/ninja.cc
index 5b4b7df..f14610f 100644
--- a/ninja.cc
+++ b/ninja.cc
@@ -21,7 +21,6 @@
 #include <sys/stat.h>
 #include <unistd.h>
 
-#include <algorithm>
 #include <map>
 #include <string>
 #include <unordered_map>
@@ -189,28 +188,23 @@ class NinjaGenerator {
 
   void Generate(const vector<DepNode*>& nodes,
                 const string& orig_args) {
-    unlink(GetStampFilename().c_str());
+    unlink(GetNinjaStampFilename().c_str());
     GenerateNinja(nodes, orig_args);
     GenerateShell();
     GenerateStamp(orig_args);
   }
 
-  static string GetNinjaFilename() {
-    return GetFilename("build%s.ninja");
-  }
-
-  static string GetShellScriptFilename() {
-    return GetFilename("ninja%s.sh");
-  }
-
-  static string GetStampFilename() {
-    return GetFilename(".kati_stamp%s");
-  }
-
   static string GetStampTempFilename() {
     return GetFilename(".kati_stamp%s.tmp");
   }
 
+  static string GetFilename(const char* fmt) {
+    string r = g_flags.ninja_dir ? g_flags.ninja_dir : ".";
+    r += '/';
+    r += StringPrintf(fmt, g_flags.ninja_suffix ? g_flags.ninja_suffix : "");
+    return r;
+  }
+
  private:
   string GenRuleName() {
     return StringPrintf("rule%d", rule_id_++);
@@ -579,13 +573,6 @@ class NinjaGenerator {
     return GetFilename("env%s.sh");
   }
 
-  static string GetFilename(const char* fmt) {
-    string r = g_flags.ninja_dir ? g_flags.ninja_dir : ".";
-    r += '/';
-    r += StringPrintf(fmt, g_flags.ninja_suffix ? g_flags.ninja_suffix : "");
-    return r;
-  }
-
   void GenerateNinja(const vector<DepNode*>& nodes,
                      const string& orig_args) {
     fp_ = fopen(GetNinjaFilename().c_str(), "wb");
@@ -663,7 +650,7 @@ class NinjaGenerator {
 
     fclose(fp);
 
-    fp = fopen(GetShellScriptFilename().c_str(), "wb");
+    fp = fopen(GetNinjaShellScriptFilename().c_str(), "wb");
     if (fp == NULL)
       PERROR("fopen(ninja.sh) failed");
 
@@ -683,7 +670,7 @@ class NinjaGenerator {
 
     fclose(fp);
 
-    if (chmod(GetShellScriptFilename().c_str(), 0755) != 0)
+    if (chmod(GetNinjaShellScriptFilename().c_str(), 0755) != 0)
       PERROR("chmod ninja.sh failed");
   }
 
@@ -766,7 +753,7 @@ class NinjaGenerator {
 
     fclose(fp);
 
-    rename(GetStampTempFilename().c_str(), GetStampFilename().c_str());
+    rename(GetStampTempFilename().c_str(), GetNinjaStampFilename().c_str());
   }
 
   CommandEvaluator ce_;
@@ -782,6 +769,18 @@ class NinjaGenerator {
   DepNode* default_target_;
 };
 
+string GetNinjaFilename() {
+  return NinjaGenerator::GetFilename("build%s.ninja");
+}
+
+string GetNinjaShellScriptFilename() {
+  return NinjaGenerator::GetFilename("ninja%s.sh");
+}
+
+string GetNinjaStampFilename() {
+  return NinjaGenerator::GetFilename(".kati_stamp%s");
+}
+
 void GenerateNinja(const vector<DepNode*>& nodes,
                    Evaluator* ev,
                    const string& orig_args,
@@ -789,273 +788,3 @@ void GenerateNinja(const vector<DepNode*>& nodes,
   NinjaGenerator ng(ev, start_time);
   ng.Generate(nodes, orig_args);
 }
-
-static bool ShouldIgnoreDirty(StringPiece s) {
-  Pattern pat(g_flags.ignore_dirty_pattern);
-  Pattern nopat(g_flags.no_ignore_dirty_pattern);
-  return pat.Match(s) && !nopat.Match(s);
-}
-
-bool NeedsRegen(double start_time, const string& orig_args) {
-  bool retval = false;
-#define RETURN_TRUE do {                         \
-    if (g_flags.dump_kati_stamp)                 \
-      retval = true;                             \
-    else                                         \
-      return true;                               \
-  } while (0)
-
-#define LOAD_INT(fp) ({                                                 \
-      int v = LoadInt(fp);                                              \
-      if (v < 0) {                                                      \
-        fprintf(stderr, "incomplete kati_stamp, regenerating...\n");    \
-        RETURN_TRUE;                                                    \
-      }                                                                 \
-      v;                                                                \
-    })
-
-#define LOAD_STRING(fp, s) ({                                           \
-      if (!LoadString(fp, s)) {                                         \
-        fprintf(stderr, "incomplete kati_stamp, regenerating...\n");    \
-        RETURN_TRUE;                                                    \
-      }                                                                 \
-    })
-
-  if (!Exists(NinjaGenerator::GetNinjaFilename())) {
-    fprintf(stderr, "%s is missing, regenerating...\n",
-            NinjaGenerator::GetNinjaFilename().c_str());
-    return true;
-  }
-  if (!Exists(NinjaGenerator::GetShellScriptFilename())) {
-    fprintf(stderr, "%s is missing, regenerating...\n",
-            NinjaGenerator::GetShellScriptFilename().c_str());
-    return true;
-  }
-
-  const string& stamp_filename = NinjaGenerator::GetStampFilename();
-  FILE* fp = fopen(stamp_filename.c_str(), "rb+");
-  if (!fp) {
-    if (g_flags.dump_kati_stamp)
-      printf("%s: %s\n", stamp_filename.c_str(), strerror(errno));
-    return true;
-  }
-  ScopedFile sfp(fp);
-
-  double gen_time;
-  size_t r = fread(&gen_time, sizeof(gen_time), 1, fp);
-  if (r != 1) {
-    fprintf(stderr, "incomplete kati_stamp, regenerating...\n");
-    RETURN_TRUE;
-  }
-  if (g_flags.dump_kati_stamp)
-    printf("Generated time: %f\n", gen_time);
-
-  string s, s2;
-  int num_files = LOAD_INT(fp);
-  for (int i = 0; i < num_files; i++) {
-    LOAD_STRING(fp, &s);
-    double ts = GetTimestamp(s);
-    if (gen_time < ts) {
-      if (g_flags.regen_ignoring_kati_binary) {
-        string kati_binary;
-        GetExecutablePath(&kati_binary);
-        if (s == kati_binary) {
-          fprintf(stderr, "%s was modified, ignored.\n", s.c_str());
-          continue;
-        }
-      }
-      if (ShouldIgnoreDirty(s)) {
-        if (g_flags.dump_kati_stamp)
-          printf("file %s: ignored (%f)\n", s.c_str(), ts);
-        continue;
-      }
-      if (g_flags.dump_kati_stamp)
-        printf("file %s: dirty (%f)\n", s.c_str(), ts);
-      else
-        fprintf(stderr, "%s was modified, regenerating...\n", s.c_str());
-      RETURN_TRUE;
-    } else if (g_flags.dump_kati_stamp) {
-      printf("file %s: clean (%f)\n", s.c_str(), ts);
-    }
-  }
-
-  int num_undefineds = LOAD_INT(fp);
-  for (int i = 0; i < num_undefineds; i++) {
-    LOAD_STRING(fp, &s);
-    if (getenv(s.c_str())) {
-      if (g_flags.dump_kati_stamp) {
-        printf("env %s: dirty (unset => %s)\n", s.c_str(), getenv(s.c_str()));
-      } else {
-        fprintf(stderr, "Environment variable %s was set, regenerating...\n",
-                s.c_str());
-      }
-      RETURN_TRUE;
-    } else if (g_flags.dump_kati_stamp) {
-      printf("env %s: clean (unset)\n", s.c_str());
-    }
-  }
-
-  int num_envs = LOAD_INT(fp);
-  for (int i = 0; i < num_envs; i++) {
-    LOAD_STRING(fp, &s);
-    StringPiece val(getenv(s.c_str()));
-    LOAD_STRING(fp, &s2);
-    if (val != s2) {
-      if (g_flags.dump_kati_stamp) {
-        printf("env %s: dirty (%s => %.*s)\n",
-               s.c_str(), s2.c_str(), SPF(val));
-      } else {
-        fprintf(stderr, "Environment variable %s was modified (%s => %.*s), "
-                "regenerating...\n",
-                s.c_str(), s2.c_str(), SPF(val));
-      }
-      RETURN_TRUE;
-    } else if (g_flags.dump_kati_stamp) {
-      printf("env %s: clean (%.*s)\n", s.c_str(), SPF(val));
-    }
-  }
-
-  {
-    int num_globs = LOAD_INT(fp);
-    string pat;
-    for (int i = 0; i < num_globs; i++) {
-      COLLECT_STATS("glob time (regen)");
-      LOAD_STRING(fp, &pat);
-#if 0
-      bool needs_reglob = false;
-      int num_dirs = LOAD_INT(fp);
-      for (int j = 0; j < num_dirs; j++) {
-        LOAD_STRING(fp, &s);
-        // TODO: Handle removed files properly.
-        needs_reglob |= gen_time < GetTimestamp(s);
-      }
-#endif
-      int num_files = LOAD_INT(fp);
-      vector<string>* files;
-      Glob(pat.c_str(), &files);
-      sort(files->begin(), files->end());
-      bool needs_regen = files->size() != static_cast<size_t>(num_files);
-      for (int j = 0; j < num_files; j++) {
-        LOAD_STRING(fp, &s);
-        if (!needs_regen) {
-          if ((*files)[j] != s) {
-            needs_regen = true;
-            break;
-          }
-        }
-      }
-      if (needs_regen) {
-        if (ShouldIgnoreDirty(pat)) {
-          if (g_flags.dump_kati_stamp) {
-            printf("wildcard %s: ignored\n", pat.c_str());
-          }
-          continue;
-        }
-        if (g_flags.dump_kati_stamp) {
-          printf("wildcard %s: dirty\n", pat.c_str());
-        } else {
-          fprintf(stderr, "wildcard(%s) was changed, regenerating...\n",
-                  pat.c_str());
-        }
-        RETURN_TRUE;
-      } else if (g_flags.dump_kati_stamp) {
-        printf("wildcard %s: clean\n", pat.c_str());
-      }
-    }
-  }
-
-  int num_crs = LOAD_INT(fp);
-  for (int i = 0; i < num_crs; i++) {
-    string cmd, expected;
-    LOAD_STRING(fp, &cmd);
-    LOAD_STRING(fp, &expected);
-
-    {
-      COLLECT_STATS("stat time (regen)");
-      bool has_condition = LOAD_INT(fp);
-      if (has_condition) {
-        bool should_run_command = false;
-
-        int num_missing_dirs = LOAD_INT(fp);
-        for (int j = 0; j < num_missing_dirs; j++) {
-          LOAD_STRING(fp, &s);
-          should_run_command |= Exists(s);
-        }
-
-        int num_read_dirs = LOAD_INT(fp);
-        for (int j = 0; j < num_read_dirs; j++) {
-          LOAD_STRING(fp, &s);
-          // We assume we rarely do a significant change for the top
-          // directory which affects the results of find command.
-          if (s == "" || s == "." || ShouldIgnoreDirty(s))
-            continue;
-
-          struct stat st;
-          if (lstat(s.c_str(), &st) != 0) {
-            should_run_command = true;
-            continue;
-          }
-          double ts = GetTimestampFromStat(st);
-          if (gen_time < ts) {
-            should_run_command = true;
-            continue;
-          }
-          if (S_ISLNK(st.st_mode)) {
-            ts = GetTimestamp(s);
-            should_run_command |= (ts < 0 || gen_time < ts);
-          }
-        }
-
-        if (!should_run_command) {
-          if (g_flags.dump_kati_stamp)
-            printf("shell %s: clean (no rerun)\n", cmd.c_str());
-          continue;
-        }
-      }
-    }
-
-    FindCommand fc;
-    if (fc.Parse(cmd) && !fc.chdir.empty() && ShouldIgnoreDirty(fc.chdir)) {
-      if (g_flags.dump_kati_stamp)
-        printf("shell %s: ignored\n", cmd.c_str());
-      continue;
-    }
-
-    {
-      COLLECT_STATS_WITH_SLOW_REPORT("shell time (regen)", cmd.c_str());
-      string result;
-      RunCommand("/bin/sh", cmd, RedirectStderr::DEV_NULL, &result);
-      FormatForCommandSubstitution(&result);
-      if (expected != result) {
-        if (g_flags.dump_kati_stamp) {
-          printf("shell %s: dirty\n", cmd.c_str());
-        } else {
-          fprintf(stderr, "$(shell %s) was changed, regenerating...\n",
-                  cmd.c_str());
-#if 0
-          fprintf(stderr, "%s => %s\n",
-                  expected.c_str(), result.c_str());
-#endif
-        }
-        RETURN_TRUE;
-      } else if (g_flags.dump_kati_stamp) {
-        printf("shell %s: clean (rerun)\n", cmd.c_str());
-      }
-    }
-  }
-
-  LoadString(fp, &s);
-  if (orig_args != s) {
-    fprintf(stderr, "arguments changed, regenerating...\n");
-    RETURN_TRUE;
-  }
-
-  if (!retval) {
-    if (fseek(fp, 0, SEEK_SET) < 0)
-      PERROR("fseek");
-    size_t r = fwrite(&start_time, sizeof(start_time), 1, fp);
-    CHECK(r == 1);
-  }
-
-  return retval;
-}
diff --git a/ninja.h b/ninja.h
index f117f2b..89683e8 100644
--- a/ninja.h
+++ b/ninja.h
@@ -32,7 +32,9 @@ void GenerateNinja(const vector<DepNode*>& nodes,
                    const string& orig_args,
                    double start_time);
 
-bool NeedsRegen(double start_time, const string& orig_args);
+string GetNinjaFilename();
+string GetNinjaShellScriptFilename();
+string GetNinjaStampFilename();
 
 // Exposed only for test.
 bool GetDepfileFromCommand(string* cmd, string* out);
diff --git a/regen.cc b/regen.cc
new file mode 100644
index 0000000..81fd189
--- /dev/null
+++ b/regen.cc
@@ -0,0 +1,410 @@
+// 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 "regen.h"
+
+#include <sys/stat.h>
+
+#include <algorithm>
+#include <memory>
+#include <mutex>
+#include <vector>
+
+#include "fileutil.h"
+#include "find.h"
+#include "io.h"
+#include "log.h"
+#include "ninja.h"
+#include "stats.h"
+#include "strutil.h"
+#include "thread.h"
+
+namespace {
+
+#define RETURN_TRUE do {                        \
+      if (g_flags.dump_kati_stamp)              \
+        needs_regen_ = true;                    \
+      else                                      \
+        return true;                            \
+    } while (0)
+
+bool ShouldIgnoreDirty(StringPiece s) {
+  Pattern pat(g_flags.ignore_dirty_pattern);
+  Pattern nopat(g_flags.no_ignore_dirty_pattern);
+  return pat.Match(s) && !nopat.Match(s);
+}
+
+class StampChecker {
+  struct GlobResult {
+    string pat;
+    vector<string> result;
+  };
+
+  struct ShellResult {
+    string cmd;
+    string result;
+    vector<string> missing_dirs;
+    vector<string> read_dirs;
+    bool has_condition;
+  };
+
+ public:
+  StampChecker()
+      : needs_regen_(false) {
+  }
+
+  ~StampChecker() {
+    for (GlobResult* gr : globs_) {
+      delete gr;
+    }
+    for (ShellResult* sr : commands_) {
+      delete sr;
+    }
+  }
+
+  bool NeedsRegen(double start_time, const string& orig_args) {
+    if (IsMissingOutputs())
+      RETURN_TRUE;
+
+    if (CheckStep1(orig_args))
+      RETURN_TRUE;
+
+    if (CheckStep2())
+      RETURN_TRUE;
+
+    if (!needs_regen_) {
+      FILE* fp = fopen(GetNinjaStampFilename().c_str(), "rb+");
+      if (!fp)
+        return true;
+      ScopedFile sfp(fp);
+      if (fseek(fp, 0, SEEK_SET) < 0)
+        PERROR("fseek");
+      size_t r = fwrite(&start_time, sizeof(start_time), 1, fp);
+      CHECK(r == 1);
+    }
+    return needs_regen_;
+  }
+
+ private:
+  bool IsMissingOutputs() {
+    if (!Exists(GetNinjaFilename())) {
+      fprintf(stderr, "%s is missing, regenerating...\n",
+              GetNinjaFilename().c_str());
+      return true;
+    }
+    if (!Exists(GetNinjaShellScriptFilename())) {
+      fprintf(stderr, "%s is missing, regenerating...\n",
+              GetNinjaShellScriptFilename().c_str());
+      return true;
+    }
+    return false;
+  }
+
+  bool CheckStep1(const string& orig_args) {
+#define LOAD_INT(fp) ({                                                 \
+        int v = LoadInt(fp);                                            \
+        if (v < 0) {                                                    \
+          fprintf(stderr, "incomplete kati_stamp, regenerating...\n");  \
+          RETURN_TRUE;                                                  \
+        }                                                               \
+        v;                                                              \
+      })
+
+#define LOAD_STRING(fp, s) ({                                           \
+        if (!LoadString(fp, s)) {                                       \
+          fprintf(stderr, "incomplete kati_stamp, regenerating...\n");  \
+          RETURN_TRUE;                                                  \
+        }                                                               \
+      })
+
+    const string& stamp_filename = GetNinjaStampFilename();
+    FILE* fp = fopen(stamp_filename.c_str(), "rb");
+    if (!fp) {
+      if (g_flags.dump_kati_stamp)
+        printf("%s: %s\n", stamp_filename.c_str(), strerror(errno));
+      return true;
+    }
+    ScopedFile sfp(fp);
+
+    double gen_time;
+    size_t r = fread(&gen_time, sizeof(gen_time), 1, fp);
+    gen_time_ = gen_time;
+    if (r != 1) {
+      fprintf(stderr, "incomplete kati_stamp, regenerating...\n");
+      RETURN_TRUE;
+    }
+    if (g_flags.dump_kati_stamp)
+      printf("Generated time: %f\n", gen_time);
+
+    string s, s2;
+    int num_files = LOAD_INT(fp);
+    for (int i = 0; i < num_files; i++) {
+      LOAD_STRING(fp, &s);
+      double ts = GetTimestamp(s);
+      if (gen_time < ts) {
+        if (g_flags.regen_ignoring_kati_binary) {
+          string kati_binary;
+          GetExecutablePath(&kati_binary);
+          if (s == kati_binary) {
+            fprintf(stderr, "%s was modified, ignored.\n", s.c_str());
+            continue;
+          }
+        }
+        if (ShouldIgnoreDirty(s)) {
+          if (g_flags.dump_kati_stamp)
+            printf("file %s: ignored (%f)\n", s.c_str(), ts);
+          continue;
+        }
+        if (g_flags.dump_kati_stamp)
+          printf("file %s: dirty (%f)\n", s.c_str(), ts);
+        else
+          fprintf(stderr, "%s was modified, regenerating...\n", s.c_str());
+        RETURN_TRUE;
+      } else if (g_flags.dump_kati_stamp) {
+        printf("file %s: clean (%f)\n", s.c_str(), ts);
+      }
+    }
+
+    int num_undefineds = LOAD_INT(fp);
+    for (int i = 0; i < num_undefineds; i++) {
+      LOAD_STRING(fp, &s);
+      if (getenv(s.c_str())) {
+        if (g_flags.dump_kati_stamp) {
+          printf("env %s: dirty (unset => %s)\n", s.c_str(), getenv(s.c_str()));
+        } else {
+          fprintf(stderr, "Environment variable %s was set, regenerating...\n",
+                  s.c_str());
+        }
+        RETURN_TRUE;
+      } else if (g_flags.dump_kati_stamp) {
+        printf("env %s: clean (unset)\n", s.c_str());
+      }
+    }
+
+    int num_envs = LOAD_INT(fp);
+    for (int i = 0; i < num_envs; i++) {
+      LOAD_STRING(fp, &s);
+      StringPiece val(getenv(s.c_str()));
+      LOAD_STRING(fp, &s2);
+      if (val != s2) {
+        if (g_flags.dump_kati_stamp) {
+          printf("env %s: dirty (%s => %.*s)\n",
+                 s.c_str(), s2.c_str(), SPF(val));
+        } else {
+          fprintf(stderr, "Environment variable %s was modified (%s => %.*s), "
+                  "regenerating...\n",
+                  s.c_str(), s2.c_str(), SPF(val));
+        }
+        RETURN_TRUE;
+      } else if (g_flags.dump_kati_stamp) {
+        printf("env %s: clean (%.*s)\n", s.c_str(), SPF(val));
+      }
+    }
+
+    int num_globs = LOAD_INT(fp);
+    string pat;
+    for (int i = 0; i < num_globs; i++) {
+      GlobResult* gr = new GlobResult;
+      globs_.push_back(gr);
+
+      LOAD_STRING(fp, &gr->pat);
+      int num_files = LOAD_INT(fp);
+      gr->result.resize(num_files);
+      for (int j = 0; j < num_files; j++) {
+        LOAD_STRING(fp, &gr->result[j]);
+      }
+    }
+
+    int num_crs = LOAD_INT(fp);
+    for (int i = 0; i < num_crs; i++) {
+      ShellResult* sr = new ShellResult;
+      commands_.push_back(sr);
+      LOAD_STRING(fp, &sr->cmd);
+      LOAD_STRING(fp, &sr->result);
+      sr->has_condition = LOAD_INT(fp);
+      if (!sr->has_condition)
+        continue;
+
+      int num_missing_dirs = LOAD_INT(fp);
+      for (int j = 0; j < num_missing_dirs; j++) {
+        LOAD_STRING(fp, &s);
+        sr->missing_dirs.push_back(s);
+      }
+      int num_read_dirs = LOAD_INT(fp);
+      for (int j = 0; j < num_read_dirs; j++) {
+        LOAD_STRING(fp, &s);
+        sr->read_dirs.push_back(s);
+      }
+    }
+
+    LoadString(fp, &s);
+    if (orig_args != s) {
+      fprintf(stderr, "arguments changed, regenerating...\n");
+      RETURN_TRUE;
+    }
+
+    return needs_regen_;
+  }
+
+  bool CheckGlobResult(const GlobResult* gr, string* err) {
+    COLLECT_STATS("glob time (regen)");
+    vector<string>* files;
+    Glob(gr->pat.c_str(), &files);
+    sort(files->begin(), files->end());
+    bool needs_regen = files->size() != gr->result.size();
+    for (size_t i = 0; i < gr->result.size(); i++) {
+      if (!needs_regen) {
+        if ((*files)[i] != gr->result[i]) {
+          needs_regen = true;
+          break;
+        }
+      }
+    }
+    if (needs_regen) {
+      if (ShouldIgnoreDirty(gr->pat)) {
+        if (g_flags.dump_kati_stamp) {
+          printf("wildcard %s: ignored\n", gr->pat.c_str());
+        }
+        return false;
+      }
+      if (g_flags.dump_kati_stamp) {
+        printf("wildcard %s: dirty\n", gr->pat.c_str());
+      } else {
+        *err = StringPrintf("wildcard(%s) was changed, regenerating...\n",
+                            gr->pat.c_str());
+      }
+    } else if (g_flags.dump_kati_stamp) {
+      printf("wildcard %s: clean\n", gr->pat.c_str());
+    }
+    return needs_regen;
+  }
+
+  bool ShouldRunCommand(const ShellResult* sr) {
+    if (!sr->has_condition)
+      return true;
+
+    COLLECT_STATS("stat time (regen)");
+    for (const string& dir : sr->missing_dirs) {
+      if (Exists(dir))
+        return true;
+    }
+    for (const string& dir : sr->read_dirs) {
+      // We assume we rarely do a significant change for the top
+      // directory which affects the results of find command.
+      if (dir == "" || dir == "." || ShouldIgnoreDirty(dir))
+        continue;
+
+      struct stat st;
+      if (lstat(dir.c_str(), &st) != 0) {
+        return true;
+      }
+      double ts = GetTimestampFromStat(st);
+      if (gen_time_ < ts) {
+        return true;
+      }
+      if (S_ISLNK(st.st_mode)) {
+        ts = GetTimestamp(dir);
+        if (ts < 0 || gen_time_ < ts)
+          return true;
+      }
+    }
+    return false;
+  }
+
+  bool CheckShellResult(const ShellResult* sr, string* err) {
+    if (!ShouldRunCommand(sr)) {
+      if (g_flags.dump_kati_stamp)
+        printf("shell %s: clean (no rerun)\n", sr->cmd.c_str());
+      return false;
+    }
+
+    FindCommand fc;
+    if (fc.Parse(sr->cmd) &&
+        !fc.chdir.empty() && ShouldIgnoreDirty(fc.chdir)) {
+      if (g_flags.dump_kati_stamp)
+        printf("shell %s: ignored\n", sr->cmd.c_str());
+      return false;
+    }
+
+    COLLECT_STATS_WITH_SLOW_REPORT("shell time (regen)", sr->cmd.c_str());
+    string result;
+    RunCommand("/bin/sh", sr->cmd, RedirectStderr::DEV_NULL, &result);
+    FormatForCommandSubstitution(&result);
+    if (sr->result != result) {
+      if (g_flags.dump_kati_stamp) {
+        printf("shell %s: dirty\n", sr->cmd.c_str());
+      } else {
+        *err = StringPrintf("$(shell %s) was changed, regenerating...\n",
+                            sr->cmd.c_str());
+        //*err += StringPrintf("%s => %s\n", expected.c_str(), result.c_str());
+      }
+      return true;
+    } else if (g_flags.dump_kati_stamp) {
+      printf("shell %s: clean (rerun)\n", sr->cmd.c_str());
+    }
+    return false;
+  }
+
+  bool CheckStep2() {
+    unique_ptr<ThreadPool> tp(NewThreadPool(g_flags.num_jobs));
+
+    tp->Submit([this]() {
+        string err;
+        // TODO: Make glob cache thread safe and create a task for each glob.
+        for (GlobResult* gr : globs_) {
+          if (CheckGlobResult(gr, &err)) {
+            unique_lock<mutex> lock(mu_);
+            if (!needs_regen_) {
+              needs_regen_ = true;
+              msg_ = err;
+            }
+            break;
+          }
+        }
+      });
+
+    for (ShellResult* sr : commands_) {
+      tp->Submit([this, sr]() {
+          string err;
+          if (CheckShellResult(sr, &err)) {
+            unique_lock<mutex> lock(mu_);
+            if (!needs_regen_) {
+              needs_regen_ = true;
+              msg_ = err;
+            }
+          }
+        });
+    }
+
+    tp->Wait();
+    if (needs_regen_) {
+      fprintf(stderr, "%s", msg_.c_str());
+    }
+    return needs_regen_;
+  }
+
+ private:
+  double gen_time_;
+  vector<GlobResult*> globs_;
+  vector<ShellResult*> commands_;
+  mutex mu_;
+  bool needs_regen_;
+  string msg_;
+};
+
+}  // namespace
+
+bool NeedsRegen(double start_time, const string& orig_args) {
+  return StampChecker().NeedsRegen(start_time, orig_args);
+}
diff --git a/regen.h b/regen.h
new file mode 100644
index 0000000..3d43d70
--- /dev/null
+++ b/regen.h
@@ -0,0 +1,24 @@
+// 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 REGEN_H_
+#define REGEN_H_
+
+#include <string>
+
+using namespace std;
+
+bool NeedsRegen(double start_time, const string& orig_args);
+
+#endif  // REGEN_H_
diff --git a/rule.cc b/rule.cc
index 191db16..fb69c5a 100644
--- a/rule.cc
+++ b/rule.cc
@@ -128,6 +128,7 @@ void ParseRule(Loc& loc, StringPiece line, char term,
   StringPiece third = rest.substr(index+1);
 
   for (StringPiece tok : WordScanner(second)) {
+    tok = TrimLeadingCurdir(tok);
     for (Symbol output : rule->outputs) {
       if (!Pattern(tok).Match(output.str())) {
         WARN("%s:%d: target `%s' doesn't match the target pattern",
diff --git a/stats.cc b/stats.cc
index 1a108d1..e1e7992 100644
--- a/stats.cc
+++ b/stats.cc
@@ -16,49 +16,68 @@
 
 #include "stats.h"
 
+#include <mutex>
 #include <vector>
 
+#include "flags.h"
 #include "log.h"
 #include "stringprintf.h"
+#include "thread_local.h"
 #include "timeutil.h"
 
 namespace {
 
+mutex g_mu;
 vector<Stats*>* g_stats;
+#ifdef __linux__
+thread_local double g_start_time;
+#define REF(x) x
+#else
+DEFINE_THREAD_LOCAL(double, g_start_time);
+#define REF(x) x.Ref()
+#endif
 
 }  // namespace
 
 Stats::Stats(const char* name)
-    : name_(name), start_time_(0), elapsed_(0), cnt_(0) {
+    : name_(name), elapsed_(0), cnt_(0) {
+  unique_lock<mutex> lock(g_mu);
   if (g_stats == NULL)
     g_stats = new vector<Stats*>;
   g_stats->push_back(this);
 }
 
 string Stats::String() const {
+  unique_lock<mutex> lock(mu_);
   return StringPrintf("%s: %f / %d", name_, elapsed_, cnt_);
 }
 
 void Stats::Start() {
-  CHECK(!start_time_);
+  CHECK(!REF(g_start_time));
+  REF(g_start_time) = GetTime();
+  unique_lock<mutex> lock(mu_);
   cnt_++;
-  start_time_ = GetTime();
 }
 
 double Stats::End() {
-  CHECK(start_time_);
-  double e = GetTime() - start_time_;
+  CHECK(REF(g_start_time));
+  double e = GetTime() - REF(g_start_time);
+  REF(g_start_time) = 0;
+  unique_lock<mutex> lock(mu_);
   elapsed_ += e;
-  start_time_ = 0;
   return e;
 }
 
 ScopedStatsRecorder::ScopedStatsRecorder(Stats* st, const char* msg)
     : st_(st), msg_(msg) {
+  if (!g_flags.enable_stat_logs)
+    return;
   st_->Start();
 }
 
 ScopedStatsRecorder::~ScopedStatsRecorder() {
+  if (!g_flags.enable_stat_logs)
+    return;
   double e = st_->End();
   if (msg_ && e > 3.0) {
     LOG_STAT("slow %s (%f): %s", st_->name_, e, msg_);
diff --git a/stats.h b/stats.h
index 7b259ae..63acc55 100644
--- a/stats.h
+++ b/stats.h
@@ -15,6 +15,7 @@
 #ifndef STATS_H_
 #define STATS_H_
 
+#include <mutex>
 #include <string>
 
 using namespace std;
@@ -32,9 +33,9 @@ class Stats {
   friend class ScopedStatsRecorder;
 
   const char* name_;
-  double start_time_;
   double elapsed_;
   int cnt_;
+  mutable mutex mu_;
 };
 
 class ScopedStatsRecorder {
diff --git a/testcase/static_pattern.mk b/testcase/static_pattern.mk
index c669ea3..eb3a643 100644
--- a/testcase/static_pattern.mk
+++ b/testcase/static_pattern.mk
@@ -1,4 +1,3 @@
-# TODO(c): Fix
 srcs := a.cc b.cc c.cc
 srcs := $(addprefix ./,$(srcs))
 objs := $(patsubst ./%.cc,./%.o,$(srcs))
diff --git a/testcase/target_specific_var_with_pattern.mk b/testcase/target_specific_var_with_pattern.mk
index fe275be..c425caa 100644
--- a/testcase/target_specific_var_with_pattern.mk
+++ b/testcase/target_specific_var_with_pattern.mk
@@ -1,9 +1,18 @@
-test: foo.x
+# TODO(go): Fix
 
+test: foo.x bar.z
+
+Z:=FAIL
 foo.x: X:=PASS
 
 %.x: X+=FAIL
 %.x: Y:=PASS
+%.x: Z:=PASS
 
 %.x:
-	echo X=$(X) Y=$(Y)
+	echo X=$(X) Y=$(Y) Z=$(Z)
+
+X:=FAIL
+%.z: X:=PASS
+%.z:
+	echo $(X)
diff --git a/testcase/trim_leading_curdir.mk b/testcase/trim_leading_curdir.mk
new file mode 100644
index 0000000..102278f
--- /dev/null
+++ b/testcase/trim_leading_curdir.mk
@@ -0,0 +1,7 @@
+all: foo.bar
+
+./foo.bar: ./%.bar: ./%.baz
+	cp $< $@
+
+./foo.baz:
+	touch $@
diff --git a/testcase/wildcard_target.mk b/testcase/wildcard_target.mk
new file mode 100644
index 0000000..8cfbe1c
--- /dev/null
+++ b/testcase/wildcard_target.mk
@@ -0,0 +1,6 @@
+# TODO(c): Implement wildcard expansion in prerequisites.
+
+test1:
+	touch foo.x
+
+test2: *.x
diff --git a/thread.cc b/thread.cc
new file mode 100644
index 0000000..1450466
--- /dev/null
+++ b/thread.cc
@@ -0,0 +1,84 @@
+// 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 "thread.h"
+
+#include <condition_variable>
+#include <mutex>
+#include <stack>
+#include <thread>
+#include <vector>
+
+class ThreadPoolImpl : public ThreadPool {
+ public:
+  explicit ThreadPoolImpl(int num_threads)
+      : is_waiting_(false) {
+    for (int i = 0; i < num_threads; i++) {
+      threads_.push_back(thread([this]() { Loop(); }));
+    }
+  }
+
+  virtual ~ThreadPoolImpl() override {
+  }
+
+  virtual void Submit(function<void(void)> task) override {
+    unique_lock<mutex> lock(mu_);
+    tasks_.push(task);
+    cond_.notify_one();
+  }
+
+  virtual void Wait() override {
+    {
+      unique_lock<mutex> lock(mu_);
+      is_waiting_ = true;
+      cond_.notify_all();
+    }
+
+    for (thread& th : threads_) {
+      th.join();
+    }
+  }
+
+ private:
+  void Loop() {
+    while (true) {
+      function<void(void)> task;
+      {
+        unique_lock<mutex> lock(mu_);
+        if (tasks_.empty()) {
+          if (is_waiting_)
+            return;
+          cond_.wait(lock);
+        }
+
+        if (tasks_.empty())
+          continue;
+
+        task = tasks_.top();
+        tasks_.pop();
+      }
+      task();
+    }
+  }
+
+  vector<thread> threads_;
+  mutex mu_;
+  condition_variable cond_;
+  stack<function<void(void)>> tasks_;
+  bool is_waiting_;
+};
+
+ThreadPool* NewThreadPool(int num_threads) {
+  return new ThreadPoolImpl(num_threads);
+}
diff --git a/thread.h b/thread.h
new file mode 100644
index 0000000..8fd3842
--- /dev/null
+++ b/thread.h
@@ -0,0 +1,35 @@
+// 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 THREAD_H_
+#define THREAD_H_
+
+#include <functional>
+
+using namespace std;
+
+class ThreadPool {
+ public:
+  virtual ~ThreadPool() = default;
+
+  virtual void Submit(function<void(void)> task) = 0;
+  virtual void Wait() = 0;
+
+ protected:
+  ThreadPool() = default;
+};
+
+ThreadPool* NewThreadPool(int num_threads);
+
+#endif  // THREAD_H_
diff --git a/thread_local.h b/thread_local.h
new file mode 100644
index 0000000..3bbf663
--- /dev/null
+++ b/thread_local.h
@@ -0,0 +1,91 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// A simple cross platform thread local storage implementation.
+//
+// This is a drop-in replacement of __thread keyword. If your compiler
+// toolchain supports __thread keyword, the user of this code should
+// be as fast as the code which uses __thread. Chrome's
+// base::ThreadLocalPointer and base::ThreadLocalStorage cannot be as
+// fast as __thread.
+// TODO(crbug.com/249345): If pthread_getspecific is slow for our use,
+// expose bionic's internal TLS and stop using pthread_getspecific
+// based implementation.
+//
+// Usage:
+//
+// Before (linux):
+//
+// __thread Foo* foo;
+// foo = new Foo();
+// foo->func();
+//
+//
+// After:
+//
+// DEFINE_THREAD_LOCAL(Foo*, foo);
+// foo.Ref() = new Foo();
+// foo.Ref()->func();
+//
+// Thread local PODs are zero-initialized.
+// Thread local non-PODs are initialized with the default constructor.
+
+#ifndef THREAD_LOCAL_H_
+#define THREAD_LOCAL_H_
+
+#include <errno.h>
+#include <pthread.h>
+
+#include "log.h"
+
+// Thread local storage implementation which uses pthread.
+// Note that DEFINE_THREAD_LOCAL creates a global variable just like
+// thread local storage based on __thread keyword. So we should not use
+// constructor in ThreadLocal class to avoid static initializator.
+template <typename Type>
+void ThreadLocalDestructor(void* ptr) {
+  delete reinterpret_cast<Type>(ptr);
+}
+
+template<typename Type, pthread_key_t* key>
+void ThreadLocalInit() {
+  if (pthread_key_create(key, ThreadLocalDestructor<Type>))
+    ERROR("Failed to create a pthread key for TLS errno=%d", errno);
+}
+
+template<typename Type, pthread_key_t* key, pthread_once_t* once>
+class ThreadLocal {
+ public:
+  Type& Ref() {
+    return *GetPointer();
+  }
+  Type Get() {
+    return Ref();
+  }
+  void Set(const Type& value) {
+    Ref() = value;
+  }
+  Type* GetPointer() {
+    pthread_once(once, ThreadLocalInit<Type*, key>);
+    Type* value = reinterpret_cast<Type*>(pthread_getspecific(*key));
+    if (value) return value;
+    // new Type() for PODs means zero initialization.
+    value = new Type();
+    int error = pthread_setspecific(*key, value);
+    if (error != 0)
+      ERROR("Failed to set a TLS: error=%d", error);
+    return value;
+  }
+};
+
+// We need a namespace for name##_key and name##_once since template parameters
+// do not accept unnamed values such as static global variables.
+#define DEFINE_THREAD_LOCAL(Type, name)                 \
+  namespace {                                           \
+  pthread_once_t name##_once = PTHREAD_ONCE_INIT;       \
+  pthread_key_t name##_key;                             \
+  }                                                     \
+  ThreadLocal<Type, &name##_key, &name##_once> name;
+
+#endif  // THREAD_LOCAL_H_