Merge remote-tracking branch 'aosp/upstream'android-n-preview-1

These commits should have fixed b/27381403 and made the code
slightly more robust against similar issues.

3835aca [C++] Update Android.bp
4a88802 [C++] Honor string length in FindEndOfLine
0140629 [C++] Finish FindEndOfLine at NULL characeter
0755047 [C++] NULL terminate the buffer of files

Bug: 27381403
Change-Id: Idd79743ce9a4718f7597573118115497f552c532

35 files changed, 390 insertions, 534 deletions

diff --git a/Android.bp b/Android.bp
index fea1241..91c2972 100644
--- a/Android.bp
+++ b/Android.bp
@@ -17,7 +17,6 @@ cc_library_host_static {
     srcs: [
         "affinity.cc",
         "command.cc",
-        "condvar.cc",
         "dep.cc",
         "eval.cc",
         "exec.cc",
@@ -30,7 +29,6 @@ cc_library_host_static {
         "func.cc",
         "io.cc",
         "log.cc",
-        "mutex.cc",
         "ninja.cc",
         "parser.cc",
         "regen.cc",
@@ -41,7 +39,6 @@ cc_library_host_static {
         "stringprintf.cc",
         "strutil.cc",
         "symtab.cc",
-        "thread.cc",
         "thread_pool.cc",
         "timeutil.cc",
         "var.cc",
diff --git a/Makefile b/Makefile
index 81dd938..5d0d45c 100644
--- a/Makefile
+++ b/Makefile
@@ -12,7 +12,7 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-all: kati ckati ckati_tests
+all: ckati ckati_tests
 
 include Makefile.kati
 include Makefile.ckati
diff --git a/Makefile.ckati b/Makefile.ckati
index 38e1feb..377e36d 100644
--- a/Makefile.ckati
+++ b/Makefile.ckati
@@ -24,7 +24,6 @@ KATI_BIN_PATH ?= .
 KATI_CXX_SRCS := \
 	affinity.cc \
 	command.cc \
-	condvar.cc \
 	dep.cc \
 	eval.cc \
 	exec.cc \
@@ -38,7 +37,6 @@ KATI_CXX_SRCS := \
 	io.cc \
 	log.cc \
 	main.cc \
-	mutex.cc \
 	ninja.cc \
 	parser.cc \
 	regen.cc \
@@ -49,7 +47,6 @@ KATI_CXX_SRCS := \
 	stringprintf.cc \
 	strutil.cc \
 	symtab.cc \
-	thread.cc \
 	thread_pool.cc \
 	timeutil.cc \
 	var.cc
diff --git a/command.cc b/command.cc
index ac7fadd..f75a8a0 100644
--- a/command.cc
+++ b/command.cc
@@ -171,12 +171,11 @@ void ParseCommandPrefixes(StringPiece* s, bool* echo, bool* ignore_error) {
 
 CommandEvaluator::CommandEvaluator(Evaluator* ev)
     : ev_(ev) {
-  Vars* vars = ev_->mutable_vars();
 #define INSERT_AUTO_VAR(name, sym) do {                                 \
     Var* v = new name(this, sym);                                       \
-    (*vars)[Intern(sym)] = v;                                           \
-    (*vars)[Intern(sym"D")] = new AutoSuffixDVar(this, sym"D", v);      \
-    (*vars)[Intern(sym"F")] = new AutoSuffixFVar(this, sym"F", v);      \
+    Intern(sym).SetGlobalVar(v);                                        \
+    Intern(sym"D").SetGlobalVar(new AutoSuffixDVar(this, sym"D", v));   \
+    Intern(sym"F").SetGlobalVar(new AutoSuffixFVar(this, sym"F", v));   \
   } while (0)
   INSERT_AUTO_VAR(AutoAtVar, "@");
   INSERT_AUTO_VAR(AutoLessVar, "<");
diff --git a/condvar.cc b/condvar.cc
deleted file mode 100644
index f8b488b..0000000
--- a/condvar.cc
+++ /dev/null
@@ -1,42 +0,0 @@
-// 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 "condvar.h"
-
-#include "log.h"
-
-condition_variable::condition_variable() {
-  if (pthread_cond_init(&cond_, NULL) != 0)
-    PERROR("pthread_cond_init");
-}
-
-condition_variable::~condition_variable() {
-  if (pthread_cond_destroy(&cond_) != 0)
-    PERROR("pthread_cond_destroy");
-}
-
-void condition_variable::wait(const UniqueLock<Mutex>& mu) {
-  if (pthread_cond_wait(&cond_, &mu.Mutex()->mu_) != 0)
-    PERROR("pthread_cond_wait");
-}
-
-void condition_variable::notify_one() {
-  if (pthread_cond_signal(&cond_) != 0)
-    PERROR("pthread_cond_signal");
-}
-
-void condition_variable::notify_all() {
-  if (pthread_cond_broadcast(&cond_) != 0)
-    PERROR("pthread_cond_broadcast");
-}
diff --git a/condvar.h b/condvar.h
deleted file mode 100644
index b75b9a4..0000000
--- a/condvar.h
+++ /dev/null
@@ -1,35 +0,0 @@
-// 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 CONDVAR_H_
-#define CONDVAR_H_
-
-#include <pthread.h>
-
-#include "mutex.h"
-
-class condition_variable {
- public:
-  condition_variable();
-  ~condition_variable();
-
-  void wait(const UniqueLock<Mutex>& mu);
-  void notify_one();
-  void notify_all();
-
- private:
-  pthread_cond_t cond_;
-};
-
-#endif  // CONDVAR_H_
diff --git a/dep.cc b/dep.cc
index 434d9ad..da209c7 100644
--- a/dep.cc
+++ b/dep.cc
@@ -45,6 +45,31 @@ static Symbol ReplaceSuffix(Symbol s, Symbol newsuf) {
   return Intern(r);
 }
 
+void ApplyOutputPattern(const Rule& r,
+                        Symbol output,
+                        const vector<Symbol>& inputs,
+                        vector<Symbol>* out_inputs) {
+  if (inputs.empty())
+    return;
+  if (r.is_suffix_rule) {
+    for (Symbol input : inputs) {
+      out_inputs->push_back(ReplaceSuffix(output, input));
+    }
+    return;
+  }
+  if (r.output_patterns.empty()) {
+    copy(inputs.begin(), inputs.end(), back_inserter(*out_inputs));
+    return;
+  }
+  CHECK(r.output_patterns.size() == 1);
+  Pattern pat(r.output_patterns[0].str());
+  for (Symbol input : inputs) {
+    string buf;
+    pat.AppendSubst(output.str(), input.str(), &buf);
+    out_inputs->push_back(Intern(buf));
+  }
+}
+
 class RuleTrie {
   struct Entry {
     Entry(const Rule* r, StringPiece s)
@@ -101,6 +126,98 @@ class RuleTrie {
   unordered_map<char, RuleTrie*> children_;
 };
 
+
+bool IsSuffixRule(Symbol output) {
+  if (output.empty() || output.str()[0] != '.')
+    return false;
+  const StringPiece rest = StringPiece(output.str()).substr(1);
+  size_t dot_index = rest.find('.');
+  // If there is only a single dot or the third dot, this is not a
+  // suffix rule.
+  if (dot_index == string::npos ||
+      rest.substr(dot_index+1).find('.') != string::npos) {
+    return false;
+  }
+  return true;
+}
+
+struct RuleMerger {
+  vector<const Rule*> rules;
+  const Rule* primary_rule;
+  bool is_double_colon;
+
+  RuleMerger()
+      : primary_rule(nullptr),
+        is_double_colon(false) {
+  }
+
+  void AddRule(Symbol output, const Rule* r) {
+    if (rules.empty()) {
+      is_double_colon = r->is_double_colon;
+    } else if (is_double_colon != r->is_double_colon) {
+      ERROR("%s:%d: *** target file `%s' has both : and :: entries.",
+            LOCF(r->loc), output.c_str());
+    }
+
+    if (primary_rule && !r->cmds.empty() &&
+        !IsSuffixRule(output) && !r->is_double_colon) {
+      WARN("%s:%d: warning: overriding commands for target `%s'",
+           LOCF(r->cmd_loc()), output.c_str());
+      WARN("%s:%d: warning: ignoring old commands for target `%s'",
+           LOCF(primary_rule->cmd_loc()), output.c_str());
+      primary_rule = r;
+    }
+    if (!primary_rule && !r->cmds.empty()) {
+      primary_rule = r;
+    }
+
+    rules.push_back(r);
+  }
+
+  void FillDepNodeFromRule(Symbol output,
+                           const Rule* r,
+                           DepNode* n) const {
+    if (is_double_colon)
+      copy(r->cmds.begin(), r->cmds.end(), back_inserter(n->cmds));
+
+    ApplyOutputPattern(*r, output, r->inputs, &n->actual_inputs);
+    ApplyOutputPattern(*r, output, r->order_only_inputs,
+                       &n->actual_order_only_inputs);
+
+    if (r->output_patterns.size() >= 1) {
+      CHECK(r->output_patterns.size() == 1);
+      n->output_pattern = r->output_patterns[0];
+    }
+  }
+
+  void FillDepNodeLoc(const Rule* r, DepNode* n) const {
+    n->loc = r->loc;
+    if (!r->cmds.empty() && r->cmd_lineno)
+      n->loc.lineno = r->cmd_lineno;
+  }
+
+  void FillDepNode(Symbol output,
+                   const Rule* pattern_rule,
+                   DepNode* n) const {
+    if (primary_rule) {
+      CHECK(!pattern_rule);
+      FillDepNodeFromRule(output, primary_rule, n);
+      FillDepNodeLoc(primary_rule, n);
+      n->cmds = primary_rule->cmds;
+    } else if (pattern_rule) {
+      FillDepNodeFromRule(output, pattern_rule, n);
+      FillDepNodeLoc(pattern_rule, n);
+      n->cmds = pattern_rule->cmds;
+    }
+
+    for (const Rule* r : rules) {
+      if (r == primary_rule)
+        continue;
+      FillDepNodeFromRule(output, r, n);
+    }
+  }
+};
+
 }  // namespace
 
 DepNode::DepNode(Symbol o, bool p, bool r)
@@ -123,34 +240,37 @@ class DepBuilder {
       : ev_(ev),
         rule_vars_(rule_vars),
         implicit_rules_(new RuleTrie()),
-        first_rule_(NULL),
+        first_rule_(Symbol::IsUninitialized{}),
         depfile_var_name_(Intern(".KATI_DEPFILE")) {
     ScopedTimeReporter tr("make dep (populate)");
     PopulateRules(rules);
-    LOG_STAT("%zu variables", ev->mutable_vars()->size());
+    // TODO?
+    //LOG_STAT("%zu variables", ev->mutable_vars()->size());
     LOG_STAT("%zu explicit rules", rules_.size());
     LOG_STAT("%zu implicit rules", implicit_rules_->size());
     LOG_STAT("%zu suffix rules", suffix_rules_.size());
 
-    auto found = rules_.find(Intern(".PHONY"));
-    if (found != rules_.end()) {
-      for (Symbol input : found->second->inputs) {
-        phony_.insert(input);
-      }
+    HandleSpecialTargets();
+  }
+
+  void HandleSpecialTargets() {
+    Loc loc;
+    vector<Symbol> targets;
+
+    if (GetRuleInputs(Intern(".PHONY"), &targets, &loc)) {
+      for (Symbol t : targets)
+        phony_.insert(t);
     }
-    found = rules_.find(Intern(".KATI_RESTAT"));
-    if (found != rules_.end()) {
-      for (Symbol input : found->second->inputs) {
-        restat_.insert(input);
-      }
+    if (GetRuleInputs(Intern(".KATI_RESTAT"), &targets, &loc)) {
+      for (Symbol t : targets)
+        restat_.insert(t);
     }
-    found = rules_.find(Intern(".SUFFIXES"));
-    if (found != rules_.end()) {
-      if (found->second->inputs.empty()) {
+    if (GetRuleInputs(Intern(".SUFFIXES"), &targets, &loc)) {
+      if (targets.empty()) {
         suffix_rules_.clear();
       } else {
         WARN("%s:%d: kati doesn't support .SUFFIXES with prerequisites",
-             LOCF(found->second->loc));
+             LOCF(loc));
       }
     }
 
@@ -171,9 +291,8 @@ class DepBuilder {
       NULL
     };
     for (const char** p = kUnsupportedBuiltinTargets; *p; p++) {
-      auto found = rules_.find(Intern(*p));
-      if (found != rules_.end()) {
-        WARN("%s:%d: kati doesn't support %s", LOCF(found->second->loc), *p);
+      if (GetRuleInputs(Intern(*p), &targets, &loc)) {
+        WARN("%s:%d: kati doesn't support %s", LOCF(loc), *p);
       }
     }
   }
@@ -182,21 +301,22 @@ class DepBuilder {
   }
 
   void Build(vector<Symbol> targets, vector<DepNode*>* nodes) {
-    if (!first_rule_) {
+    if (!first_rule_.IsValid()) {
       ERROR("*** No targets.");
     }
-    CHECK(!first_rule_->outputs.empty());
 
     if (!g_flags.gen_all_targets && targets.empty()) {
-      targets.push_back(first_rule_->outputs[0]);
+      targets.push_back(first_rule_);
     }
     if (g_flags.gen_all_targets) {
       unordered_set<Symbol> non_root_targets;
       for (const auto& p : rules_) {
-        for (Symbol t : p.second->inputs)
-          non_root_targets.insert(t);
-        for (Symbol t : p.second->order_only_inputs)
-          non_root_targets.insert(t);
+        for (const Rule* r : p.second.rules) {
+          for (Symbol t : r->inputs)
+            non_root_targets.insert(t);
+          for (Symbol t : r->order_only_inputs)
+            non_root_targets.insert(t);
+        }
       }
 
       for (const auto& p : rules_) {
@@ -229,6 +349,21 @@ class DepBuilder {
     return ::Exists(target.str());
   }
 
+  bool GetRuleInputs(Symbol s, vector<Symbol>* o, Loc* l) {
+    auto found = rules_.find(s);
+    if (found == rules_.end())
+      return false;
+
+    o->clear();
+    CHECK(!found->second.rules.empty());
+    *l = found->second.rules.front()->loc;
+    for (const Rule* r : found->second.rules) {
+      for (Symbol i : r->inputs)
+        o->push_back(i);
+    }
+    return true;
+  }
+
   void PopulateRules(const vector<const Rule*>& rules) {
     for (const Rule* rule : rules) {
       if (rule->outputs.empty()) {
@@ -243,17 +378,11 @@ class DepBuilder {
   }
 
   bool PopulateSuffixRule(const Rule* rule, Symbol output) {
-    if (output.empty() || output.str()[0] != '.')
+    if (!IsSuffixRule(output))
       return false;
 
     const StringPiece rest = StringPiece(output.str()).substr(1);
     size_t dot_index = rest.find('.');
-    // If there is only a single dot or the third dot, this is not a
-    // suffix rule.
-    if (dot_index == string::npos ||
-        rest.substr(dot_index+1).find('.') != string::npos) {
-      return false;
-    }
 
     StringPiece input_suffix = rest.substr(0, dot_index);
     StringPiece output_suffix = rest.substr(dot_index+1);
@@ -265,100 +394,13 @@ class DepBuilder {
     return true;
   }
 
-  void ApplyOutputPattern(const Rule& r,
-                          Symbol output,
-                          const vector<Symbol>& inputs,
-                          vector<Symbol>* out_inputs) {
-    if (inputs.empty())
-      return;
-    if (r.is_suffix_rule) {
-      for (Symbol input : inputs) {
-        out_inputs->push_back(ReplaceSuffix(output, input));
-      }
-      return;
-    }
-    if (r.output_patterns.empty()) {
-      copy(inputs.begin(), inputs.end(), back_inserter(*out_inputs));
-      return;
-    }
-    CHECK(r.output_patterns.size() == 1);
-    Pattern pat(r.output_patterns[0].str());
-    for (Symbol input : inputs) {
-      string buf;
-      pat.AppendSubst(output.str(), input.str(), &buf);
-      out_inputs->push_back(Intern(buf));
-    }
-  }
-
-  shared_ptr<Rule> MergeRules(const Rule& old_rule,
-                              const Rule& rule,
-                              Symbol output,
-                              bool is_suffix_rule) {
-    COLLECT_STATS("make dep (merge rule)");
-    if (old_rule.is_double_colon != rule.is_double_colon) {
-      ERROR("%s:%d: *** target file `%s' has both : and :: entries.",
-            LOCF(rule.loc), output.str().c_str());
-    }
-    if (!old_rule.cmds.empty() && !rule.cmds.empty() &&
-        !is_suffix_rule && !rule.is_double_colon) {
-      WARN("%s:%d: warning: overriding commands for target `%s'",
-           LOCF(rule.cmd_loc()), output.str().c_str());
-      WARN("%s:%d: warning: ignoring old commands for target `%s'",
-           LOCF(old_rule.cmd_loc()), output.str().c_str());
-    }
-
-    shared_ptr<Rule> r = make_shared<Rule>(rule);
-    if (rule.is_double_colon) {
-      r->cmds.clear();
-      for (Value* c : old_rule.cmds)
-        r->cmds.push_back(c);
-      for (Value* c : rule.cmds)
-        r->cmds.push_back(c);
-      if (!rule.output_patterns.empty() && !old_rule.output_patterns.empty() &&
-          rule.output_patterns != old_rule.output_patterns) {
-        ERROR("%s:%d: TODO: merging two double colon rules with output "
-              "patterns is not supported", LOCF(rule.loc));
-      }
-    } else if (!old_rule.cmds.empty() && rule.cmds.empty()) {
-      r->cmds = old_rule.cmds;
-    }
-
-    // If the latter rule has a command (regardless of the commands in
-    // |old_rule|), inputs in the latter rule has a priority.
-    if (rule.cmds.empty()) {
-      r->inputs = old_rule.inputs;
-      ApplyOutputPattern(rule, output, rule.inputs, &r->inputs);
-      r->order_only_inputs = old_rule.order_only_inputs;
-      ApplyOutputPattern(rule, output, rule.order_only_inputs,
-                         &r->order_only_inputs);
-      r->output_patterns = old_rule.output_patterns;
-    } else {
-      ApplyOutputPattern(old_rule, output, old_rule.inputs, &r->inputs);
-      ApplyOutputPattern(old_rule, output, old_rule.order_only_inputs,
-                         &r->order_only_inputs);
-    }
-    r->is_default_target |= old_rule.is_default_target;
-    return r;
-  }
-
-  void PopulateExplicitRule(const Rule* orig_rule) {
-    for (Symbol output : orig_rule->outputs) {
-      const bool is_suffix_rule = PopulateSuffixRule(orig_rule, output);
-
-      shared_ptr<Rule> rule = make_shared<Rule>(*orig_rule);
-      rule->outputs.clear();
-      rule->outputs.push_back(output);
-
-      auto p = rules_.emplace(output, rule);
-      if (p.second) {
-        if (!first_rule_ && output.get(0) != '.') {
-          rule->is_default_target = true;
-          first_rule_ = rule;
-        }
-      } else {
-        p.first->second =
-            MergeRules(*p.first->second, *rule, output, is_suffix_rule);
+  void PopulateExplicitRule(const Rule* rule) {
+    for (Symbol output : rule->outputs) {
+      if (!first_rule_.IsValid() && output.get(0) != '.') {
+        first_rule_ = output;
       }
+      rules_[output].AddRule(output, rule);
+      PopulateSuffixRule(rule, output);
     }
   }
 
@@ -383,18 +425,19 @@ class DepBuilder {
     }
   }
 
-  shared_ptr<Rule> LookupRule(Symbol o) {
+  const RuleMerger* LookupRuleMerger(Symbol o) {
     auto found = rules_.find(o);
-    if (found != rules_.end())
-      return found->second;
-    return NULL;
+    if (found != rules_.end()) {
+      return &found->second;
+    }
+    return nullptr;
   }
 
   Vars* LookupRuleVars(Symbol o) {
     auto found = rule_vars_.find(o);
     if (found != rule_vars_.end())
       return found->second;
-    return NULL;
+    return nullptr;
   }
 
   bool CanPickImplicitRule(const Rule* rule, Symbol output, DepNode* n,
@@ -454,54 +497,40 @@ class DepBuilder {
     return r;
   }
 
-  bool PickRule(Symbol output, DepNode* n,
-                shared_ptr<Rule>* out_rule, Vars** out_var) {
-    COLLECT_STATS("make dep (pick rule)");
-    shared_ptr<Rule> rule = LookupRule(output);
+  bool PickRule(Symbol output,
+                DepNode* n,
+                const RuleMerger** out_rule_merger,
+                shared_ptr<Rule>* pattern_rule,
+                Vars** out_var) {
+    const RuleMerger* rule_merger = LookupRuleMerger(output);
     Vars* vars = LookupRuleVars(output);
-    *out_rule = rule;
+    *out_rule_merger = rule_merger;
     *out_var = vars;
-    if (rule) {
-      if (!rule->cmds.empty()) {
-        return true;
-      }
-    }
+    if (rule_merger && rule_merger->primary_rule)
+      return true;
 
     vector<const Rule*> irules;
     implicit_rules_->Get(output.str(), &irules);
     for (auto iter = irules.rbegin(); iter != irules.rend(); ++iter) {
-      shared_ptr<Rule> irule;
-      if (!CanPickImplicitRule(*iter, output, n, &irule))
+      if (!CanPickImplicitRule(*iter, output, n, pattern_rule))
         continue;
-      if (rule) {
-        shared_ptr<Rule> r = make_shared<Rule>(*rule);
-        r->output_patterns = irule->output_patterns;
-        r->inputs.clear();
-        r->inputs = irule->inputs;
-        copy(rule->inputs.begin(), rule->inputs.end(),
-             back_inserter(r->inputs));
-        r->cmds = irule->cmds;
-        r->is_default_target |= irule->is_default_target;
-        r->loc = irule->loc;
-        r->cmd_lineno = irule->cmd_lineno;
-        *out_rule = r;
+      if (rule_merger) {
         return true;
       }
-      CHECK(irule->output_patterns.size() == 1);
-      vars = MergeImplicitRuleVars(irule->output_patterns[0], vars);
+      CHECK((*pattern_rule)->output_patterns.size() == 1);
+      vars = MergeImplicitRuleVars((*pattern_rule)->output_patterns[0], vars);
       *out_var = vars;
-      *out_rule = make_shared<Rule>(*irule);
       return true;
     }
 
     StringPiece output_suffix = GetExt(output.str());
     if (output_suffix.get(0) != '.')
-      return rule.get();
+      return rule_merger;
     output_suffix = output_suffix.substr(1);
 
     SuffixRuleMap::const_iterator found = suffix_rules_.find(output_suffix);
     if (found == suffix_rules_.end())
-      return rule.get();
+      return rule_merger;
 
     for (shared_ptr<Rule> irule : found->second) {
       CHECK(irule->inputs.size() == 1);
@@ -509,26 +538,18 @@ class DepBuilder {
       if (!Exists(input))
         continue;
 
-      if (rule) {
-        shared_ptr<Rule> r = make_shared<Rule>(*rule);
-        r->inputs.insert(r->inputs.begin(), input);
-        r->cmds = irule->cmds;
-        r->is_default_target |= irule->is_default_target;
-        r->loc = irule->loc;
-        r->cmd_lineno = irule->cmd_lineno;
-        *out_rule = r;
+      *pattern_rule = irule;
+      if (rule_merger)
         return true;
-      }
       if (vars) {
         CHECK(irule->outputs.size() == 1);
         vars = MergeImplicitRuleVars(irule->outputs[0], vars);
         *out_var = vars;
       }
-      *out_rule = irule;
       return true;
     }
 
-    return rule.get();
+    return rule_merger;
   }
 
   DepNode* BuildPlan(Symbol output, Symbol needed_by UNUSED) {
@@ -546,20 +567,19 @@ class DepBuilder {
                              restat_.count(output));
     done_[output] = n;
 
-    shared_ptr<Rule> rule;
+    const RuleMerger* rule_merger = nullptr;
+    shared_ptr<Rule> pattern_rule;
     Vars* vars;
-    if (!PickRule(output, n, &rule, &vars)) {
+    if (!PickRule(output, n, &rule_merger, &pattern_rule, &vars)) {
       return n;
     }
-
-    if (rule->output_patterns.size() >= 1) {
-      CHECK(rule->output_patterns.size() == 1);
-      n->output_pattern = rule->output_patterns[0];
-    }
+    if (rule_merger)
+      rule_merger->FillDepNode(output, pattern_rule.get(), n);
+    else
+      RuleMerger().FillDepNode(output, pattern_rule.get(), n);
 
     vector<unique_ptr<ScopedVar>> sv;
     if (vars) {
-      COLLECT_STATS("make dep (create scope)");
       for (const auto& p : *vars) {
         Symbol name = p.first;
         RuleVar* var = reinterpret_cast<RuleVar*>(p.second);
@@ -591,23 +611,18 @@ class DepBuilder {
       }
     }
 
-    ApplyOutputPattern(*rule, output, rule->inputs, &n->actual_inputs);
     for (Symbol input : n->actual_inputs) {
       DepNode* c = BuildPlan(input, output);
       n->deps.push_back(c);
     }
 
-    vector<Symbol> order_only_inputs;
-    ApplyOutputPattern(*rule, output, rule->order_only_inputs,
-                       &order_only_inputs);
-    for (Symbol input : order_only_inputs) {
+    for (Symbol input : n->actual_order_only_inputs) {
       DepNode* c = BuildPlan(input, output);
       n->order_onlys.push_back(c);
     }
 
     n->has_rule = true;
-    n->cmds = rule->cmds;
-    n->is_default_target = rule->is_default_target;
+    n->is_default_target = first_rule_ == output;
     if (cur_rule_vars_->empty()) {
       n->rule_vars = NULL;
     } else {
@@ -616,15 +631,12 @@ class DepBuilder {
         n->rule_vars->insert(p);
       }
     }
-    n->loc = rule->loc;
-    if (!rule->cmds.empty() && rule->cmd_lineno)
-      n->loc.lineno = rule->cmd_lineno;
 
     return n;
   }
 
   Evaluator* ev_;
-  map<Symbol, shared_ptr<Rule>> rules_;
+  map<Symbol, RuleMerger> rules_;
   const unordered_map<Symbol, Vars*>& rule_vars_;
   unique_ptr<Vars> cur_rule_vars_;
 
@@ -632,7 +644,7 @@ class DepBuilder {
   typedef unordered_map<StringPiece, vector<shared_ptr<Rule>>> SuffixRuleMap;
   SuffixRuleMap suffix_rules_;
 
-  shared_ptr<Rule> first_rule_;
+  Symbol first_rule_;
   unordered_map<Symbol, DepNode*> done_;
   unordered_set<Symbol> phony_;
   unordered_set<Symbol> restat_;
diff --git a/dep.h b/dep.h
index 05d10d0..4302997 100644
--- a/dep.h
+++ b/dep.h
@@ -42,6 +42,7 @@ struct DepNode {
   bool is_phony;
   bool is_restat;
   vector<Symbol> actual_inputs;
+  vector<Symbol> actual_order_only_inputs;
   Vars* rule_vars;
   Var* depfile_var;
   Symbol output_pattern;
diff --git a/eval.cc b/eval.cc
index be4bb34..6322fc1 100644
--- a/eval.cc
+++ b/eval.cc
@@ -30,9 +30,8 @@
 #include "symtab.h"
 #include "var.h"
 
-Evaluator::Evaluator(const Vars* vars)
-    : vars_(new Vars(*vars)),
-      last_rule_(NULL),
+Evaluator::Evaluator()
+    : last_rule_(NULL),
       current_scope_(NULL),
       avoid_io_(false),
       eval_depth_(0) {
@@ -102,7 +101,7 @@ void Evaluator::EvalAssign(const AssignStmt* stmt) {
   Var* rhs = EvalRHS(lhs, stmt->rhs, stmt->orig_rhs, stmt->op,
                      stmt->directive == AssignDirective::OVERRIDE);
   if (rhs)
-    vars_->Assign(lhs, rhs);
+    lhs.SetGlobalVar(rhs);
 }
 
 void Evaluator::EvalRule(const RuleStmt* stmt) {
@@ -284,7 +283,7 @@ void Evaluator::EvalExport(const ExportStmt* stmt) {
 }
 
 Var* Evaluator::LookupVarGlobal(Symbol name) {
-  Var* v = vars_->Lookup(name);
+  Var* v = name.GetGlobalVar();
   if (v->IsDefined())
     return v;
   used_undefined_vars_.insert(name);
diff --git a/eval.h b/eval.h
index cb03d5d..3eede2b 100644
--- a/eval.h
+++ b/eval.h
@@ -33,7 +33,7 @@ class Vars;
 
 class Evaluator {
  public:
-  Evaluator(const Vars* vars);
+  Evaluator();
   ~Evaluator();
 
   void EvalAssign(const AssignStmt* stmt);
@@ -56,7 +56,6 @@ class Evaluator {
   const unordered_map<Symbol, Vars*>& rule_vars() const {
     return rule_vars_;
   }
-  Vars* mutable_vars() { return vars_; }
   const unordered_map<Symbol, bool>& exports() const { return exports_; }
 
   void Error(const string& msg);
@@ -97,7 +96,6 @@ class Evaluator {
 
   Var* LookupVarGlobal(Symbol name);
 
-  Vars* vars_;
   unordered_map<Symbol, Vars*> rule_vars_;
   vector<const Rule*> rules_;
   unordered_map<Symbol, bool> exports_;
diff --git a/expr.cc b/expr.cc
index a629352..ad7d19e 100644
--- a/expr.cc
+++ b/expr.cc
@@ -63,7 +63,7 @@ class Literal : public Value {
   }
 
   virtual bool IsLiteral() const override { return true; }
-  virtual StringPiece GetLiteralValueUnsafe() const { return s_; }
+  virtual StringPiece GetLiteralValueUnsafe() const override { return s_; }
 
   virtual string DebugString_() const override {
     return s_.as_string();
diff --git a/file.cc b/file.cc
index 4c423e5..eca09dd 100644
--- a/file.cc
+++ b/file.cc
@@ -26,7 +26,7 @@
 #include "stmt.h"
 
 Makefile::Makefile(const string& filename)
-    : buf_(NULL), len_(0), mtime_(0), filename_(filename) {
+    : mtime_(0), filename_(filename), exists_(false) {
   int fd = open(filename.c_str(), O_RDONLY);
   if (fd < 0) {
     return;
@@ -37,14 +37,15 @@ Makefile::Makefile(const string& filename)
     PERROR("fstat failed for %s", filename.c_str());
   }
 
-  len_ = st.st_size;
+  size_t len = st.st_size;
   mtime_ = st.st_mtime;
-  buf_ = new char[len_];
-  ssize_t r = read(fd, buf_, len_);
-  if (r != static_cast<ssize_t>(len_)) {
+  buf_.resize(len);
+  exists_ = true;
+  ssize_t r = read(fd, &buf_[0], len);
+  if (r != static_cast<ssize_t>(len)) {
     if (r < 0)
       PERROR("read failed for %s", filename.c_str());
-    ERROR("Unexpected read length=%zd expected=%zu", r, len_);
+    ERROR("Unexpected read length=%zd expected=%zu", r, len);
   }
 
   if (close(fd) < 0) {
@@ -55,7 +56,6 @@ Makefile::Makefile(const string& filename)
 }
 
 Makefile::~Makefile() {
-  delete[] buf_;
   for (Stmt* stmt : stmts_)
     delete stmt;
 }
diff --git a/file.h b/file.h
index 1746343..6af6696 100644
--- a/file.h
+++ b/file.h
@@ -29,21 +29,20 @@ class Makefile {
   explicit Makefile(const string& filename);
   ~Makefile();
 
-  const char* buf() const { return buf_; }
-  size_t len() const { return len_; }
+  const string& buf() const { return buf_; }
   const string& filename() const { return filename_; }
 
   const vector<Stmt*>& stmts() const { return stmts_; }
   vector<Stmt*>* mutable_stmts() { return &stmts_; }
 
-  bool Exists() const { return buf_; }
+  bool Exists() const { return exists_; }
 
  private:
-  char* buf_;
-  size_t len_;
+  string buf_;
   uint64_t mtime_;
   string filename_;
   vector<Stmt*> stmts_;
+  bool exists_;
 };
 
 #endif  // FILE_H_
diff --git a/flags.cc b/flags.cc
index 73c7105..7623499 100644
--- a/flags.cc
+++ b/flags.cc
@@ -100,10 +100,6 @@ void Flags::Parse(int argc, char** argv) {
         "--ninja_dir", argv, &i, &ninja_dir)) {
     } else if (!strcmp(arg, "--use_find_emulator")) {
       use_find_emulator = true;
-    } else if (!strcmp(arg, "--gen_regen_rule")) {
-      // TODO: Make this default once we have removed unnecessary
-      // command line change from Android build.
-      gen_regen_rule = true;
     } else if (ParseCommandLineOptionWithArg(
         "--goma_dir", argv, &i, &goma_dir)) {
     } else if (ParseCommandLineOptionWithArg(
diff --git a/flags.h b/flags.h
index 275a3ee..905d5ee 100644
--- a/flags.h
+++ b/flags.h
@@ -29,7 +29,6 @@ struct Flags {
   bool enable_kati_warnings;
   bool enable_stat_logs;
   bool gen_all_targets;
-  bool gen_regen_rule;
   bool generate_ninja;
   bool is_dry_run;
   bool is_silent_mode;
diff --git a/func.cc b/func.cc
index 2ea8afa..876b274 100644
--- a/func.cc
+++ b/func.cc
@@ -595,7 +595,7 @@ void CallFunc(const vector<Value*>& args, Evaluator* ev, string* s) {
         new SimpleVar(args[i]->Eval(ev), VarOrigin::AUTOMATIC));
     av.push_back(move(s));
   }
-  vector<unique_ptr<ScopedVar>> sv;
+  vector<unique_ptr<ScopedGlobalVar>> sv;
   for (size_t i = 1; ; i++) {
     string s;
     Symbol tmpvar_name_sym(Symbol::IsUninitialized{});
@@ -606,8 +606,7 @@ void CallFunc(const vector<Value*>& args, Evaluator* ev, string* s) {
       tmpvar_name_sym = Intern(s);
     }
     if (i < args.size()) {
-      sv.emplace_back(new ScopedVar(ev->mutable_vars(),
-                                    tmpvar_name_sym, av[i-1].get()));
+      sv.emplace_back(new ScopedGlobalVar(tmpvar_name_sym, av[i-1].get()));
     } else {
       // We need to blank further automatic vars
       Var *v = ev->LookupVar(tmpvar_name_sym);
@@ -615,8 +614,7 @@ void CallFunc(const vector<Value*>& args, Evaluator* ev, string* s) {
       if (v->Origin() != VarOrigin::AUTOMATIC) break;
 
       av.emplace_back(new SimpleVar("", VarOrigin::AUTOMATIC));
-      sv.emplace_back(new ScopedVar(ev->mutable_vars(),
-                                    tmpvar_name_sym, av[i-1].get()));
+      sv.emplace_back(new ScopedGlobalVar(tmpvar_name_sym, av[i-1].get()));
     }
   }
 
@@ -633,7 +631,7 @@ void ForeachFunc(const vector<Value*>& args, Evaluator* ev, string* s) {
   for (StringPiece tok : WordScanner(list)) {
     unique_ptr<SimpleVar> v(new SimpleVar(
         tok.as_string(), VarOrigin::AUTOMATIC));
-    ScopedVar sv(ev->mutable_vars(), Intern(varname), v.get());
+    ScopedGlobalVar sv(Intern(varname), v.get());
     ww.MaybeAddWhitespace();
     args[2]->Eval(ev, s);
   }
diff --git a/main.cc b/main.cc
index c732dda..2627bfd 100644
--- a/main.cc
+++ b/main.cc
@@ -105,13 +105,13 @@ static void ReadBootstrapMakefile(const vector<Symbol>& targets,
   Parse(Intern(bootstrap).str(), Loc("*bootstrap*", 0), stmts);
 }
 
-static void SetVar(StringPiece l, VarOrigin origin, Vars* vars) {
+static void SetVar(StringPiece l, VarOrigin origin) {
   size_t found = l.find('=');
   CHECK(found != string::npos);
   Symbol lhs = Intern(l.substr(0, found));
   StringPiece rhs = l.substr(found + 1);
-  vars->Assign(lhs,
-               new RecursiveVar(NewLiteral(rhs.data()), origin, rhs.data()));
+  lhs.SetGlobalVar(
+      new RecursiveVar(NewLiteral(rhs.data()), origin, rhs.data()));
 }
 
 extern "C" char** environ;
@@ -138,14 +138,12 @@ static int Run(const vector<Symbol>& targets,
 
   MakefileCacheManager* cache_mgr = NewMakefileCacheManager();
 
-  Vars* vars = new Vars();
-  vars->Assign(Intern("MAKEFILE_LIST"),
-               new SimpleVar(StringPrintf(" %s", g_flags.makefile),
-                             VarOrigin::FILE));
+  Intern("MAKEFILE_LIST").SetGlobalVar(
+      new SimpleVar(StringPrintf(" %s", g_flags.makefile), VarOrigin::FILE));
   for (char** p = environ; *p; p++) {
-    SetVar(*p, VarOrigin::ENVIRONMENT, vars);
+    SetVar(*p, VarOrigin::ENVIRONMENT);
   }
-  Evaluator* ev = new Evaluator(vars);
+  Evaluator* ev = new Evaluator();
 
   vector<Stmt*> bootstrap_asts;
   ReadBootstrapMakefile(targets, &bootstrap_asts);
@@ -157,7 +155,7 @@ static int Run(const vector<Symbol>& targets,
   ev->set_is_bootstrap(false);
 
   for (StringPiece l : cl_vars) {
-    SetVar(l, VarOrigin::COMMAND_LINE, ev->mutable_vars());
+    SetVar(l, VarOrigin::COMMAND_LINE);
   }
 
   {
@@ -210,9 +208,6 @@ static int Run(const vector<Symbol>& targets,
   for (Stmt* stmt : bootstrap_asts)
     delete stmt;
   delete ev;
-  // Each Var will be deleted by |ev|.
-  vars->clear();
-  delete vars;
   delete cache_mgr;
 
   return 0;
diff --git a/mutex.cc b/mutex.cc
deleted file mode 100644
index 986366b..0000000
--- a/mutex.cc
+++ /dev/null
@@ -1,37 +0,0 @@
-// 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 "mutex.h"
-
-#include "log.h"
-
-Mutex::Mutex() {
-  if (pthread_mutex_init(&mu_, NULL) != 0)
-    PERROR("pthread_mutex_init");
-}
-
-Mutex::~Mutex() {
-  if (pthread_mutex_destroy(&mu_) != 0)
-    PERROR("pthread_mutex_destroy");
-}
-
-void Mutex::lock() {
-  if (pthread_mutex_lock(&mu_) != 0)
-    PERROR("pthread_mutex_lock");
-}
-
-void Mutex::unlock() {
-  if (pthread_mutex_unlock(&mu_) != 0)
-    PERROR("pthread_mutex_unlock");
-}
diff --git a/mutex.h b/mutex.h
deleted file mode 100644
index e730294..0000000
--- a/mutex.h
+++ /dev/null
@@ -1,50 +0,0 @@
-// 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 MUTEX_H_
-#define MUTEX_H_
-
-#include <pthread.h>
-
-class Mutex {
- public:
-  explicit Mutex();
-  ~Mutex();
-
-  void lock();
-  void unlock();
-
- private:
-  pthread_mutex_t mu_;
-
-  friend class condition_variable;
-};
-
-template<class T> class UniqueLock {
- public:
-  explicit UniqueLock(T& mu)
-      : mu_(mu) {
-    mu_.lock();
-  }
-  ~UniqueLock() {
-    mu_.unlock();
-  }
-
-  T* Mutex() const { return &mu_; }
-
- private:
-  T& mu_;
-};
-
-#endif  // MUTEX_H_
diff --git a/ninja.cc b/ninja.cc
index eeefce0..4a5d014 100644
--- a/ninja.cc
+++ b/ninja.cc
@@ -201,7 +201,7 @@ class NinjaGenerator {
                 const string& orig_args) {
     unlink(GetNinjaStampFilename().c_str());
     PopulateNinjaNodes(nodes);
-    GenerateNinja(orig_args);
+    GenerateNinja();
     GenerateShell();
     GenerateStamp(orig_args);
   }
@@ -569,34 +569,16 @@ class NinjaGenerator {
     if (use_local_pool)
       *o << " pool = local_pool\n";
     if (node->is_default_target) {
-      UniqueLock<Mutex> lock(mu_);
+      unique_lock<mutex> lock(mu_);
       default_target_ = node;
     }
   }
 
-  void EmitRegenRules(const string& orig_args) {
-    if (!g_flags.gen_regen_rule)
-      return;
-
-    fprintf(fp_, "rule regen_ninja\n");
-    fprintf(fp_, " command = %s\n", orig_args.c_str());
-    fprintf(fp_, " generator = 1\n");
-    fprintf(fp_, " description = Regenerate ninja files due to dependency\n");
-    fprintf(fp_, "build %s: regen_ninja", GetNinjaFilename().c_str());
-    unordered_set<string> makefiles;
-    MakefileCacheManager::Get()->GetAllFilenames(&makefiles);
-    for (const string& makefile : makefiles) {
-      fprintf(fp_, " %.*s", SPF(makefile));
-    }
-    fprintf(fp_, " %s", kati_binary_.c_str());
-    fprintf(fp_, "\n\n");
-  }
-
   static string GetEnvScriptFilename() {
     return GetFilename("env%s.sh");
   }
 
-  void GenerateNinja(const string& orig_args) {
+  void GenerateNinja() {
     ScopedTimeReporter tr("ninja gen (emit)");
     fp_ = fopen(GetNinjaFilename().c_str(), "wb");
     if (fp_ == NULL)
@@ -622,8 +604,6 @@ class NinjaGenerator {
 
     fprintf(fp_, "build _kati_always_build_: phony\n\n");
 
-    EmitRegenRules(orig_args);
-
     unique_ptr<ThreadPool> tp(NewThreadPool(g_flags.num_jobs));
     CHECK(g_flags.num_jobs);
     int num_nodes_per_task = nodes_.size() / (g_flags.num_jobs * 10) + 1;
@@ -807,7 +787,7 @@ class NinjaGenerator {
   const double start_time_;
   vector<NinjaNode*> nodes_;
 
-  Mutex mu_;
+  mutex mu_;
   const DepNode* default_target_;
 };
 
diff --git a/parser.cc b/parser.cc
index fff3a7d..4b4012e 100644
--- a/parser.cc
+++ b/parser.cc
@@ -529,7 +529,7 @@ class Parser {
 
 void Parse(Makefile* mk) {
   COLLECT_STATS("parse file time");
-  Parser parser(StringPiece(mk->buf(), mk->len()),
+  Parser parser(StringPiece(mk->buf()),
                 mk->filename().c_str(),
                 mk->mutable_stmts());
   parser.Parse();
diff --git a/regen.cc b/regen.cc
index a448612..23151b4 100644
--- a/regen.cc
+++ b/regen.cc
@@ -18,13 +18,13 @@
 
 #include <algorithm>
 #include <memory>
+#include <mutex>
 #include <vector>
 
 #include "fileutil.h"
 #include "find.h"
 #include "io.h"
 #include "log.h"
-#include "mutex.h"
 #include "ninja.h"
 #include "stats.h"
 #include "strutil.h"
@@ -364,7 +364,7 @@ class StampChecker {
         // TODO: Make glob cache thread safe and create a task for each glob.
         for (GlobResult* gr : globs_) {
           if (CheckGlobResult(gr, &err)) {
-            UniqueLock<Mutex> lock(mu_);
+            unique_lock<mutex> lock(mu_);
             if (!needs_regen_) {
               needs_regen_ = true;
               msg_ = err;
@@ -378,7 +378,7 @@ class StampChecker {
       tp->Submit([this, sr]() {
           string err;
           if (CheckShellResult(sr, &err)) {
-            UniqueLock<Mutex> lock(mu_);
+            unique_lock<mutex> lock(mu_);
             if (!needs_regen_) {
               needs_regen_ = true;
               msg_ = err;
@@ -398,7 +398,7 @@ class StampChecker {
   double gen_time_;
   vector<GlobResult*> globs_;
   vector<ShellResult*> commands_;
-  Mutex mu_;
+  mutex mu_;
   bool needs_regen_;
   string msg_;
 };
diff --git a/rule.cc b/rule.cc
index fb69c5a..f3f5203 100644
--- a/rule.cc
+++ b/rule.cc
@@ -50,8 +50,7 @@ bool IsPatternRule(StringPiece s) {
 Rule::Rule()
     : is_double_colon(false),
       is_suffix_rule(false),
-      cmd_lineno(0),
-      is_default_target(false) {
+      cmd_lineno(0) {
 }
 
 void ParseRule(Loc& loc, StringPiece line, char term,
@@ -167,8 +166,6 @@ string Rule::DebugString() const {
     v.push_back("is_double_colon");
   if (is_suffix_rule)
     v.push_back("is_suffix_rule");
-  if (is_default_target)
-    v.push_back("is_default_target");
   if (!cmds.empty()) {
     v.push_back(StringPrintf("cmds=[%s]", JoinValues(cmds, ",").c_str()));
   }
diff --git a/rule.h b/rule.h
index d94abce..2a67368 100644
--- a/rule.h
+++ b/rule.h
@@ -44,7 +44,6 @@ class Rule {
   vector<Value*> cmds;
   Loc loc;
   int cmd_lineno;
-  bool is_default_target;
 
  private:
   void Error(const string& msg) {
diff --git a/stats.cc b/stats.cc
index 60b3285..fc170f0 100644
--- a/stats.cc
+++ b/stats.cc
@@ -16,18 +16,18 @@
 
 #include "stats.h"
 
+#include <mutex>
 #include <vector>
 
 #include "flags.h"
 #include "log.h"
-#include "mutex.h"
 #include "stringprintf.h"
 #include "thread_local.h"
 #include "timeutil.h"
 
 namespace {
 
-Mutex g_mu;
+mutex g_mu;
 vector<Stats*>* g_stats;
 DEFINE_THREAD_LOCAL(double, g_start_time);
 
@@ -35,21 +35,21 @@ DEFINE_THREAD_LOCAL(double, g_start_time);
 
 Stats::Stats(const char* name)
     : name_(name), elapsed_(0), cnt_(0) {
-  UniqueLock<Mutex> lock(g_mu);
+  unique_lock<mutex> lock(g_mu);
   if (g_stats == NULL)
     g_stats = new vector<Stats*>;
   g_stats->push_back(this);
 }
 
 string Stats::String() const {
-  UniqueLock<Mutex> lock(mu_);
+  unique_lock<mutex> lock(mu_);
   return StringPrintf("%s: %f / %d", name_, elapsed_, cnt_);
 }
 
 void Stats::Start() {
   CHECK(!TLS_REF(g_start_time));
   TLS_REF(g_start_time) = GetTime();
-  UniqueLock<Mutex> lock(mu_);
+  unique_lock<mutex> lock(mu_);
   cnt_++;
 }
 
@@ -57,7 +57,7 @@ double Stats::End() {
   CHECK(TLS_REF(g_start_time));
   double e = GetTime() - TLS_REF(g_start_time);
   TLS_REF(g_start_time) = 0;
-  UniqueLock<Mutex> lock(mu_);
+  unique_lock<mutex> lock(mu_);
   elapsed_ += e;
   return e;
 }
diff --git a/stats.h b/stats.h
index 190fa57..63acc55 100644
--- a/stats.h
+++ b/stats.h
@@ -15,10 +15,9 @@
 #ifndef STATS_H_
 #define STATS_H_
 
+#include <mutex>
 #include <string>
 
-#include "mutex.h"
-
 using namespace std;
 
 class Stats {
@@ -36,7 +35,7 @@ class Stats {
   const char* name_;
   double elapsed_;
   int cnt_;
-  mutable Mutex mu_;
+  mutable mutex mu_;
 };
 
 class ScopedStatsRecorder {
diff --git a/strutil.cc b/strutil.cc
index 80a4b5b..d3c14d8 100644
--- a/strutil.cc
+++ b/strutil.cc
@@ -424,10 +424,16 @@ size_t FindThreeOutsideParen(StringPiece s, char c1, char c2, char c3) {
 
 size_t FindEndOfLine(StringPiece s, size_t e, size_t* lf_cnt) {
 #ifdef __SSE4_2__
-  static const char ranges[] = "\n\n\\\\";
+  static const char ranges[] = "\0\0\n\n\\\\";
   while (e < s.size()) {
-    e += SkipUntilSSE42(s.data() + e, s.size() - e, ranges, 4);
+    e += SkipUntilSSE42(s.data() + e, s.size() - e, ranges, 6);
+    if (e >= s.size()) {
+      CHECK(s.size() == e);
+      break;
+    }
     char c = s[e];
+    if (c == '\0')
+      break;
     if (c == '\\') {
       if (s[e+1] == '\n') {
         e += 2;
@@ -523,6 +529,32 @@ string EchoEscape(const string str) {
 }
 
 void EscapeShell(string* s) {
+#ifdef __SSE4_2__
+  static const char ranges[] = "\0\0\"\"$$\\\\``";
+  size_t prev = 0;
+  size_t i = SkipUntilSSE42(s->c_str(), s->size(), ranges, 10);
+  if (i == s->size())
+    return;
+
+  string r;
+  for (; i < s->size();) {
+    StringPiece(*s).substr(prev, i - prev).AppendToString(&r);
+    char c = (*s)[i];
+    r += '\\';
+    if (c == '$') {
+      if ((*s)[i+1] == '$') {
+        r += '$';
+        i++;
+      }
+    }
+    r += c;
+    i++;
+    prev = i;
+    i += SkipUntilSSE42(s->c_str() + i, s->size() - i, ranges, 10);
+  }
+  StringPiece(*s).substr(prev).AppendToString(&r);
+  s->swap(r);
+#else
   if (s->find_first_of("$`\\\"") == string::npos)
     return;
   string r;
@@ -550,4 +582,5 @@ void EscapeShell(string* s) {
     }
   }
   s->swap(r);
+#endif
 }
diff --git a/strutil_test.cc b/strutil_test.cc
index 069dc4d..a89786f 100644
--- a/strutil_test.cc
+++ b/strutil_test.cc
@@ -116,6 +116,28 @@ void TestNormalizePath() {
   ASSERT_EQ(NormalizePath("./../../a/b"), "../../a/b");
 }
 
+string EscapeShell(string s) {
+  ::EscapeShell(&s);
+  return s;
+}
+
+void TestEscapeShell() {
+  ASSERT_EQ(EscapeShell(""), "");
+  ASSERT_EQ(EscapeShell("foo"), "foo");
+  ASSERT_EQ(EscapeShell("foo$`\\baz\"bar"), "foo\\$\\`\\\\baz\\\"bar");
+  ASSERT_EQ(EscapeShell("$$"), "\\$$");
+  ASSERT_EQ(EscapeShell("$$$"), "\\$$\\$");
+  ASSERT_EQ(EscapeShell("\\\n"), "\\\\\n");
+}
+
+void TestFindEndOfLine() {
+  size_t lf_cnt = 0;
+  ASSERT_EQ(FindEndOfLine("foo", 0, &lf_cnt), 3);
+  char buf[10] = {'f', 'o', '\\', '\0', 'x', 'y'};
+  ASSERT_EQ(FindEndOfLine(StringPiece(buf, 6), 0, &lf_cnt), 3);
+  ASSERT_EQ(FindEndOfLine(StringPiece(buf, 2), 0, &lf_cnt), 2);
+}
+
 }  // namespace
 
 int main() {
@@ -126,5 +148,7 @@ int main() {
   TestNoLineBreak();
   TestHasWord();
   TestNormalizePath();
+  TestEscapeShell();
+  TestFindEndOfLine();
   assert(!g_failed);
 }
diff --git a/symtab.cc b/symtab.cc
index af0b620..fb81bfe 100644
--- a/symtab.cc
+++ b/symtab.cc
@@ -27,8 +27,18 @@
 
 #include "log.h"
 #include "strutil.h"
+#include "var.h"
+
+struct SymbolData {
+  SymbolData()
+      : gv(kUndefined) {
+  }
+
+  Var* gv;
+};
 
 vector<string*>* g_symbols;
+static vector<SymbolData> g_symbol_data;
 
 Symbol kEmptySym = Symbol(Symbol::IsUninitialized());
 Symbol kShellSym = Symbol(Symbol::IsUninitialized());
@@ -37,6 +47,45 @@ Symbol::Symbol(int v)
     : v_(v) {
 }
 
+Var* Symbol::GetGlobalVar() const {
+  if (static_cast<size_t>(v_) >= g_symbol_data.size()) {
+    g_symbol_data.resize(v_ + 1);
+  }
+  Var* v = g_symbol_data[v_].gv;
+  if (v->Origin() == VarOrigin::ENVIRONMENT ||
+      v->Origin() == VarOrigin::ENVIRONMENT_OVERRIDE) {
+    Vars::add_used_env_vars(*this);
+  }
+  return v;
+}
+
+void Symbol::SetGlobalVar(Var* v) const {
+  if (static_cast<size_t>(v_) >= g_symbol_data.size()) {
+    g_symbol_data.resize(v_ + 1);
+  }
+  Var* orig = g_symbol_data[v_].gv;
+  if (orig->Origin() == VarOrigin::OVERRIDE ||
+      orig->Origin() == VarOrigin::ENVIRONMENT_OVERRIDE) {
+    return;
+  }
+  if (orig->Origin() == VarOrigin::AUTOMATIC) {
+    ERROR("overriding automatic variable is not implemented yet");
+  }
+  if (orig->IsDefined())
+    delete orig;
+  g_symbol_data[v_].gv = v;
+}
+
+ScopedGlobalVar::ScopedGlobalVar(Symbol name, Var* var)
+    : name_(name), orig_(NULL) {
+  orig_ = name.GetGlobalVar();
+  g_symbol_data[name_.val()].gv = var;
+}
+
+ScopedGlobalVar::~ScopedGlobalVar() {
+  g_symbol_data[name_.val()].gv = orig_;
+}
+
 class Symtab {
  public:
   Symtab() {
diff --git a/symtab.h b/symtab.h
index 9d8a120..d1de4e1 100644
--- a/symtab.h
+++ b/symtab.h
@@ -25,6 +25,7 @@ using namespace std;
 extern vector<string*>* g_symbols;
 
 class Symtab;
+class Var;
 
 class Symbol {
  public:
@@ -54,6 +55,9 @@ class Symbol {
 
   bool IsValid() const { return v_ >= 0; }
 
+  Var* GetGlobalVar() const;
+  void SetGlobalVar(Var* v) const;
+
  private:
   explicit Symbol(int v);
 
@@ -62,6 +66,16 @@ class Symbol {
   friend class Symtab;
 };
 
+class ScopedGlobalVar {
+ public:
+  ScopedGlobalVar(Symbol name, Var* var);
+  ~ScopedGlobalVar();
+
+ private:
+  Symbol name_;
+  Var* orig_;
+};
+
 inline bool operator==(const Symbol& x, const Symbol& y) {
   return x.val() == y.val();
 }
diff --git a/thread.cc b/thread.cc
deleted file mode 100644
index 9733208..0000000
--- a/thread.cc
+++ /dev/null
@@ -1,34 +0,0 @@
-// 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 "log.h"
-
-thread::thread(const fn_t& fn) {
-  if (pthread_create(&th_, NULL, &thread::Run, new fn_t(fn)) != 0)
-    PERROR("pthread_create");
-}
-
-void thread::join() {
-  if (pthread_join(th_, NULL) != 0)
-    PERROR("pthread_join");
-}
-
-void* thread::Run(void* p) {
-  fn_t* fn = static_cast<fn_t*>(p);
-  (*fn)();
-  delete fn;
-  return NULL;
-}
diff --git a/thread.h b/thread.h
deleted file mode 100644
index 440fc5b..0000000
--- a/thread.h
+++ /dev/null
@@ -1,37 +0,0 @@
-// 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 <pthread.h>
-
-#include <functional>
-
-using namespace std;
-
-class thread {
-  typedef function<void(void)> fn_t;
-
- public:
-  explicit thread(const fn_t& fn);
-  void join();
-
- private:
-  static void* Run(void* p);
-
-  pthread_t th_;
-};
-
-#endif  // THREAD_H_
diff --git a/thread_pool.cc b/thread_pool.cc
index c504ef5..0a12bfa 100644
--- a/thread_pool.cc
+++ b/thread_pool.cc
@@ -14,13 +14,13 @@
 
 #include "thread_pool.h"
 
+#include <condition_variable>
+#include <mutex>
 #include <stack>
+#include <thread>
 #include <vector>
 
 #include "affinity.h"
-#include "condvar.h"
-#include "mutex.h"
-#include "thread.h"
 
 class ThreadPoolImpl : public ThreadPool {
  public:
@@ -37,14 +37,14 @@ class ThreadPoolImpl : public ThreadPool {
   }
 
   virtual void Submit(function<void(void)> task) override {
-    UniqueLock<Mutex> lock(mu_);
+    unique_lock<mutex> lock(mu_);
     tasks_.push(task);
     cond_.notify_one();
   }
 
   virtual void Wait() override {
     {
-      UniqueLock<Mutex> lock(mu_);
+      unique_lock<mutex> lock(mu_);
       is_waiting_ = true;
       cond_.notify_all();
     }
@@ -61,7 +61,7 @@ class ThreadPoolImpl : public ThreadPool {
     while (true) {
       function<void(void)> task;
       {
-        UniqueLock<Mutex> lock(mu_);
+        unique_lock<mutex> lock(mu_);
         if (tasks_.empty()) {
           if (is_waiting_)
             return;
@@ -79,7 +79,7 @@ class ThreadPoolImpl : public ThreadPool {
   }
 
   vector<thread> threads_;
-  Mutex mu_;
+  mutex mu_;
   condition_variable cond_;
   stack<function<void(void)>> tasks_;
   bool is_waiting_;
diff --git a/var.cc b/var.cc
index a5cde3e..73f542c 100644
--- a/var.cc
+++ b/var.cc
@@ -112,6 +112,10 @@ Vars::~Vars() {
   }
 }
 
+void Vars::add_used_env_vars(Symbol v) {
+  used_env_vars_.insert(v);
+}
+
 Var* Vars::Lookup(Symbol name) const {
   auto found = find(name);
   if (found == end())
diff --git a/var.h b/var.h
index 5ba5fcb..5fc09fa 100644
--- a/var.h
+++ b/var.h
@@ -179,6 +179,8 @@ class Vars : public unordered_map<Symbol, Var*> {
 
   void Assign(Symbol name, Var* v);
 
+  static void add_used_env_vars(Symbol v);
+
   static const unordered_set<Symbol>& used_env_vars() {
     return used_env_vars_;
   }