Merge branch 'aosp/upstream' into master

am: 18e9d8b32b

Change-Id: I357149786bb93c3c76757f37bfc9ed1f7589b5e5

23 files changed, 763 insertions, 453 deletions

diff --git a/Makefile b/Makefile
index 2754488..9a2aefc 100644
--- a/Makefile
+++ b/Makefile
@@ -17,8 +17,14 @@ all: ckati ckati_tests
 include Makefile.kati
 include Makefile.ckati
 
-test: all ckati_tests
-	ruby runtest.rb -c -n
+test: run_tests
+
+test_quietly: run_tests
+test_quietly: RUN_TESTS_QUIETLY := -q
+
+run_tests: all ckati_tests
+	ruby runtest.rb -c -n $(RUN_TESTS_QUIETLY)
+
 
 clean: ckati_clean
 
diff --git a/command.cc b/command.cc
index b072a6a..04bb168 100644
--- a/command.cc
+++ b/command.cc
@@ -30,8 +30,8 @@ namespace {
 
 class AutoVar : public Var {
  public:
+  AutoVar() : Var(VarOrigin::AUTOMATIC) {}
   virtual const char* Flavor() const override { return "undefined"; }
-  virtual VarOrigin Origin() const override { return VarOrigin::AUTOMATIC; }
 
   virtual void AppendVar(Evaluator*, Value*) override { CHECK(false); }
 
diff --git a/dep.cc b/dep.cc
index 3993c4a..6223a69 100644
--- a/dep.cc
+++ b/dep.cc
@@ -150,7 +150,6 @@ struct RuleMerger {
   RuleMerger()
       : primary_rule(nullptr),
         parent(nullptr),
-        parent_sym(Symbol::IsUninitialized()),
         is_double_colon(false) {}
 
   void AddImplicitOutput(Symbol output, RuleMerger* merger) {
@@ -268,8 +267,7 @@ DepNode::DepNode(Symbol o, bool p, bool r)
       is_restat(r),
       rule_vars(NULL),
       depfile_var(NULL),
-      ninja_pool_var(NULL),
-      output_pattern(Symbol::IsUninitialized()) {
+      ninja_pool_var(NULL) {
   g_dep_node_pool->push_back(this);
 }
 
@@ -281,7 +279,6 @@ class DepBuilder {
       : ev_(ev),
         rule_vars_(rule_vars),
         implicit_rules_(new RuleTrie()),
-        first_rule_(Symbol::IsUninitialized{}),
         depfile_var_name_(Intern(".KATI_DEPFILE")),
         implicit_outputs_var_name_(Intern(".KATI_IMPLICIT_OUTPUTS")),
         ninja_pool_var_name_(Intern(".KATI_NINJA_POOL")) {
@@ -347,7 +344,7 @@ class DepBuilder {
       targets.push_back(first_rule_);
     }
     if (g_flags.gen_all_targets) {
-      unordered_set<Symbol> non_root_targets;
+      SymbolSet non_root_targets;
       for (const auto& p : rules_) {
         if (p.first.get(0) == '.')
           continue;
@@ -361,7 +358,7 @@ class DepBuilder {
 
       for (const auto& p : rules_) {
         Symbol t = p.first;
-        if (!non_root_targets.count(t) && t.get(0) != '.') {
+        if (!non_root_targets.exists(t) && t.get(0) != '.') {
           targets.push_back(p.first);
         }
       }
@@ -381,12 +378,8 @@ class DepBuilder {
 
  private:
   bool Exists(Symbol target) {
-    auto found = rules_.find(target);
-    if (found != rules_.end())
-      return true;
-    if (phony_.count(target))
-      return true;
-    return ::Exists(target.str());
+    return (rules_.find(target) != rules_.end()) || phony_.exists(target) ||
+           ::Exists(target.str());
   }
 
   bool GetRuleInputs(Symbol s, vector<Symbol>* o, Loc* l) {
@@ -519,7 +512,7 @@ class DepBuilder {
                            Symbol output,
                            DepNode* n,
                            shared_ptr<Rule>* out_rule) {
-    Symbol matched(Symbol::IsUninitialized{});
+    Symbol matched;
     for (Symbol output_pattern : rule->output_patterns) {
       Pattern pat(output_pattern.str());
       if (pat.Match(output.str())) {
@@ -643,7 +636,7 @@ class DepBuilder {
     }
 
     DepNode* n =
-        new DepNode(output, phony_.count(output), restat_.count(output));
+        new DepNode(output, phony_.exists(output), restat_.exists(output));
     done_[output] = n;
 
     const RuleMerger* rule_merger = nullptr;
@@ -669,9 +662,9 @@ class DepBuilder {
     if (vars) {
       for (const auto& p : *vars) {
         Symbol name = p.first;
-        RuleVar* var = reinterpret_cast<RuleVar*>(p.second);
+        Var* var = p.second;
         CHECK(var);
-        Var* new_var = var->v();
+        Var* new_var = var;
         if (var->op() == AssignOp::PLUS_EQ) {
           Var* old_var = ev_->LookupVar(name);
           if (old_var->IsDefined()) {
@@ -820,8 +813,8 @@ class DepBuilder {
 
   Symbol first_rule_;
   unordered_map<Symbol, DepNode*> done_;
-  unordered_set<Symbol> phony_;
-  unordered_set<Symbol> restat_;
+  SymbolSet phony_;
+  SymbolSet restat_;
   Symbol depfile_var_name_;
   Symbol implicit_outputs_var_name_;
   Symbol ninja_pool_var_name_;
diff --git a/eval.cc b/eval.cc
index fa7bebb..1370fb1 100644
--- a/eval.cc
+++ b/eval.cc
@@ -38,8 +38,7 @@ Evaluator::Evaluator()
       eval_depth_(0),
       posix_sym_(Intern(".POSIX")),
       is_posix_(false),
-      export_error_(false),
-      kati_readonly_(Intern(".KATI_READONLY")) {
+      export_error_(false) {
 #if defined(__APPLE__)
   stack_size_ = pthread_get_stacksize_np(pthread_self());
   stack_addr_ = (char*)pthread_get_stackaddr_np(pthread_self()) - stack_size_;
@@ -65,50 +64,49 @@ Var* Evaluator::EvalRHS(Symbol lhs,
                         Value* rhs_v,
                         StringPiece orig_rhs,
                         AssignOp op,
-                        bool is_override) {
+                        bool is_override,
+                        bool *needs_assign) {
   VarOrigin origin =
       ((is_bootstrap_ ? VarOrigin::DEFAULT
                       : is_commandline_ ? VarOrigin::COMMAND_LINE
                                         : is_override ? VarOrigin::OVERRIDE
                                                       : VarOrigin::FILE));
 
-  Var* rhs = NULL;
+  Var* result = NULL;
   Var* prev = NULL;
-  bool needs_assign = true;
+  *needs_assign = true;
 
   switch (op) {
     case AssignOp::COLON_EQ: {
       prev = PeekVarInCurrentScope(lhs);
-      SimpleVar* sv = new SimpleVar(origin);
-      rhs_v->Eval(this, sv->mutable_value());
-      rhs = sv;
+      result = new SimpleVar(origin, this, rhs_v);
       break;
     }
     case AssignOp::EQ:
       prev = PeekVarInCurrentScope(lhs);
-      rhs = new RecursiveVar(rhs_v, origin, orig_rhs);
+      result = new RecursiveVar(rhs_v, origin, orig_rhs);
       break;
     case AssignOp::PLUS_EQ: {
       prev = LookupVarInCurrentScope(lhs);
       if (!prev->IsDefined()) {
-        rhs = new RecursiveVar(rhs_v, origin, orig_rhs);
+        result = new RecursiveVar(rhs_v, origin, orig_rhs);
       } else if (prev->ReadOnly()) {
         Error(StringPrintf("*** cannot assign to readonly variable: %s",
                            lhs.c_str()));
       } else {
-        prev->AppendVar(this, rhs_v);
-        rhs = prev;
-        needs_assign = false;
+        result = prev;
+        result->AppendVar(this, rhs_v);
+        *needs_assign = false;
       }
       break;
     }
     case AssignOp::QUESTION_EQ: {
       prev = LookupVarInCurrentScope(lhs);
       if (!prev->IsDefined()) {
-        rhs = new RecursiveVar(rhs_v, origin, orig_rhs);
+        result = new RecursiveVar(rhs_v, origin, orig_rhs);
       } else {
-        rhs = prev;
-        needs_assign = false;
+        result = prev;
+        *needs_assign = false;
       }
       break;
     }
@@ -116,18 +114,13 @@ Var* Evaluator::EvalRHS(Symbol lhs,
 
   if (prev != NULL) {
     prev->Used(this, lhs);
-    if (prev->Deprecated()) {
-      if (needs_assign) {
-        rhs->SetDeprecated(prev->DeprecatedMessage());
-      }
+    if (prev->Deprecated() && *needs_assign) {
+      result->SetDeprecated(prev->DeprecatedMessage());
     }
   }
 
-  LOG("Assign: %s=%s", lhs.c_str(), rhs->DebugString().c_str());
-  if (needs_assign) {
-    return rhs;
-  }
-  return NULL;
+  LOG("Assign: %s=%s", lhs.c_str(), result->DebugString().c_str());
+  return result;
 }
 
 void Evaluator::EvalAssign(const AssignStmt* stmt) {
@@ -137,7 +130,7 @@ void Evaluator::EvalAssign(const AssignStmt* stmt) {
   if (lhs.empty())
     Error("*** empty variable name.");
 
-  if (lhs == kati_readonly_) {
+  if (lhs == kKatiReadonlySym) {
     string rhs;
     stmt->rhs->Eval(this, &rhs);
     for (auto const& name : WordScanner(rhs)) {
@@ -151,105 +144,203 @@ void Evaluator::EvalAssign(const AssignStmt* stmt) {
     return;
   }
 
-  Var* rhs = EvalRHS(lhs, stmt->rhs, stmt->orig_rhs, stmt->op,
-                     stmt->directive == AssignDirective::OVERRIDE);
-  if (rhs) {
+  bool needs_assign;
+  Var* var = EvalRHS(lhs, stmt->rhs, stmt->orig_rhs, stmt->op,
+                     stmt->directive == AssignDirective::OVERRIDE,
+                     &needs_assign);
+  if (needs_assign) {
     bool readonly;
-    lhs.SetGlobalVar(rhs, stmt->directive == AssignDirective::OVERRIDE,
+    lhs.SetGlobalVar(var, stmt->directive == AssignDirective::OVERRIDE,
                      &readonly);
     if (readonly) {
       Error(StringPrintf("*** cannot assign to readonly variable: %s",
                          lhs.c_str()));
     }
   }
+
+  if (stmt->is_final) {
+    var->SetReadOnly();
+  }
+}
+
+// With rule broken into
+//   <before_term> <term> <after_term>
+// parses <before_term> into Symbol instances until encountering ':'
+// Returns the remainder of <before_term>.
+static StringPiece ParseRuleTargets(const Loc& loc,
+                                    const StringPiece& before_term,
+                                    vector<Symbol>* targets,
+                                    bool* is_pattern_rule) {
+  size_t pos = before_term.find(':');
+  if (pos == string::npos) {
+    ERROR_LOC(loc, "*** missing separator.");
+  }
+  StringPiece targets_string = before_term.substr(0, pos);
+  size_t pattern_rule_count = 0;
+  for (auto const& word : WordScanner(targets_string)) {
+    StringPiece target = TrimLeadingCurdir(word);
+    targets->push_back(Intern(target));
+    if (Rule::IsPatternRule(target)) {
+      ++pattern_rule_count;
+    }
+  }
+  // Check consistency: either all outputs are patterns or none.
+  if (pattern_rule_count && (pattern_rule_count != targets->size())) {
+    ERROR_LOC(loc, "*** mixed implicit and normal rules: deprecated syntax");
+  }
+  *is_pattern_rule = pattern_rule_count;
+  return before_term.substr(pos + 1);
+}
+
+
+void Evaluator::MarkVarsReadonly(Value* vars_list) {
+  string vars_list_string;
+  vars_list->Eval(this, &vars_list_string);
+  for (auto const& name : WordScanner(vars_list_string)) {
+    Var* var = current_scope_->Lookup(Intern(name));
+    if (!var->IsDefined()) {
+      Error(StringPrintf("*** unknown variable: %s", name.as_string().c_str()));
+    }
+    var->SetReadOnly();
+  }
+}
+
+void Evaluator::EvalRuleSpecificAssign(const vector<Symbol>& targets,
+                                       const RuleStmt* stmt,
+                                       const StringPiece& after_targets,
+                                       size_t separator_pos) {
+  StringPiece var_name;
+  StringPiece rhs_string;
+  AssignOp assign_op;
+  ParseAssignStatement(after_targets, separator_pos, &var_name, &rhs_string,
+                       &assign_op);
+  Symbol var_sym = Intern(var_name);
+  bool is_final = (stmt->sep == RuleStmt::SEP_FINALEQ);
+  for (Symbol target : targets) {
+    auto p = rule_vars_.emplace(target, nullptr);
+    if (p.second) {
+      p.first->second = new Vars;
+    }
+
+    Value* rhs;
+    if (rhs_string.empty()) {
+      rhs = stmt->rhs;
+    } else if (stmt->rhs) {
+      StringPiece sep(stmt->sep == RuleStmt::SEP_SEMICOLON ? " ; " : " = ");
+      rhs = Value::NewExpr(Value::NewLiteral(rhs_string), Value::NewLiteral(sep),
+                           stmt->rhs);
+    } else {
+      rhs = Value::NewLiteral(rhs_string);
+    }
+
+    current_scope_ = p.first->second;
+    if (var_sym == kKatiReadonlySym) {
+      MarkVarsReadonly(rhs);
+    } else {
+      bool needs_assign;
+      Var* rhs_var = EvalRHS(var_sym, rhs, StringPiece("*TODO*"), assign_op, false, &needs_assign);
+      if (needs_assign) {
+        bool readonly;
+        rhs_var->SetAssignOp(assign_op);
+        current_scope_->Assign(var_sym, rhs_var, &readonly);
+        if (readonly) {
+          Error(StringPrintf("*** cannot assign to readonly variable: %s",
+                             var_name));
+        }
+      }
+      if (is_final) {
+        rhs_var->SetReadOnly();
+      }
+    }
+    current_scope_ = NULL;
+  }
 }
 
 void Evaluator::EvalRule(const RuleStmt* stmt) {
   loc_ = stmt->loc();
   last_rule_ = NULL;
 
-  const string&& expr = stmt->expr->Eval(this);
+  const string&& before_term = stmt->lhs->Eval(this);
   // See semicolon.mk.
-  if (expr.find_first_not_of(" \t;") == string::npos) {
-    if (stmt->term == ';')
+  if (before_term.find_first_not_of(" \t;") == string::npos) {
+    if (stmt->sep == RuleStmt::SEP_SEMICOLON)
       Error("*** missing rule before commands.");
     return;
   }
 
-  Rule* rule;
-  RuleVarAssignment rule_var;
-  function<string()> after_term_fn = [this, stmt]() {
-    return stmt->after_term ? stmt->after_term->Eval(this) : "";
-  };
-  ParseRule(loc_, expr, stmt->term, after_term_fn, &rule, &rule_var);
-
-  if (rule) {
-    if (stmt->term == ';') {
-      rule->cmds.push_back(stmt->after_term);
-    }
+  vector<Symbol> targets;
+  bool is_pattern_rule;
+  StringPiece after_targets =
+      ParseRuleTargets(loc_, before_term, &targets, &is_pattern_rule);
+  bool is_double_colon = (after_targets[0] == ':');
+  if (is_double_colon) {
+    after_targets = after_targets.substr(1);
+  }
 
-    for (Symbol o : rule->outputs) {
-      if (o == posix_sym_)
-        is_posix_ = true;
-    }
+  // Figure out if this is a rule-specific variable assignment.
+  // It is an assignment when either after_targets contains an assignment token
+  // or separator is an assignment token, but only if there is no ';' before the
+  // first assignment token.
+  size_t separator_pos = after_targets.find_first_of("=;");
+  char separator = '\0';
+  if (separator_pos != string::npos) {
+    separator = after_targets[separator_pos];
+  } else if (separator_pos == string::npos &&
+             (stmt->sep == RuleStmt::SEP_EQ || stmt->sep == RuleStmt::SEP_FINALEQ)) {
+    separator_pos = after_targets.size();
+    separator = '=';
+  }
 
-    LOG("Rule: %s", rule->DebugString().c_str());
-    rules_.push_back(rule);
-    last_rule_ = rule;
+  // If variable name is not empty, we have rule- or target-specific
+  // variable assignment.
+  if (separator == '=' && separator_pos) {
+    EvalRuleSpecificAssign(targets, stmt, after_targets, separator_pos);
     return;
   }
 
-  Symbol lhs = Intern(rule_var.lhs);
-  for (Symbol output : rule_var.outputs) {
-    auto p = rule_vars_.emplace(output, nullptr);
-    if (p.second) {
-      p.first->second = new Vars;
+  // "test: =foo" is questionable but a valid rule definition (not a
+  // target specific variable).
+  // See https://github.com/google/kati/issues/83
+  string buf;
+  if (!separator_pos) {
+    KATI_WARN_LOC(loc_,
+                  "defining a target which starts with `=', "
+                  "which is not probably what you meant");
+    buf = after_targets.as_string();
+    if (stmt->sep == RuleStmt::SEP_SEMICOLON) {
+      buf += ';';
+    } else if (stmt->sep == RuleStmt::SEP_EQ || stmt->sep == RuleStmt::SEP_FINALEQ) {
+      buf += '=';
     }
-
-    Value* rhs = stmt->after_term;
-    if (!rule_var.rhs.empty()) {
-      Value* lit = NewLiteral(rule_var.rhs);
-      if (rhs) {
-        // TODO: We always insert two whitespaces around the
-        // terminator. Preserve whitespaces properly.
-        if (stmt->term == ';') {
-          rhs = NewExpr3(lit, NewLiteral(StringPiece(" ; ")), rhs);
-        } else {
-          rhs = NewExpr3(lit, NewLiteral(StringPiece(" = ")), rhs);
-        }
-      } else {
-        rhs = lit;
-      }
+    if (stmt->rhs) {
+      buf += stmt->rhs->Eval(this);
     }
+    after_targets = buf;
+    separator_pos = string::npos;
+  }
 
-    current_scope_ = p.first->second;
+  Rule* rule = new Rule();
+  rule->loc = loc_;
+  rule->is_double_colon = is_double_colon;
+  if (is_pattern_rule) {
+    rule->output_patterns.swap(targets);
+  } else {
+    rule->outputs.swap(targets);
+  }
+  rule->ParsePrerequisites(after_targets, separator_pos, stmt);
 
-    if (lhs == kati_readonly_) {
-      string rhs_value;
-      rhs->Eval(this, &rhs_value);
-      for (auto const& name : WordScanner(rhs_value)) {
-        Var* var = current_scope_->Lookup(Intern(name));
-        if (!var->IsDefined()) {
-          Error(StringPrintf("*** unknown variable: %s",
-                             name.as_string().c_str()));
-        }
-        var->SetReadOnly();
-      }
-      current_scope_ = NULL;
-      continue;
-    }
+  if (stmt->sep == RuleStmt::SEP_SEMICOLON) {
+    rule->cmds.push_back(stmt->rhs);
+  }
 
-    Var* rhs_var = EvalRHS(lhs, rhs, StringPiece("*TODO*"), rule_var.op);
-    if (rhs_var) {
-      bool readonly;
-      current_scope_->Assign(lhs, new RuleVar(rhs_var, rule_var.op), &readonly);
-      if (readonly) {
-        Error(StringPrintf("*** cannot assign to readonly variable: %s",
-                           lhs.c_str()));
-      }
-    }
-    current_scope_ = NULL;
+  for (Symbol o : rule->outputs) {
+    if (o == posix_sym_)
+      is_posix_ = true;
   }
+
+  LOG("Rule: %s", rule->DebugString().c_str());
+  rules_.push_back(rule);
+  last_rule_ = rule;
 }
 
 void Evaluator::EvalCommand(const CommandStmt* stmt) {
@@ -266,7 +357,7 @@ void Evaluator::EvalCommand(const CommandStmt* stmt) {
   last_rule_->cmds.push_back(stmt->expr);
   if (last_rule_->cmd_lineno == 0)
     last_rule_->cmd_lineno = stmt->loc().lineno;
-  LOG("Command: %s", stmt->expr->DebugString().c_str());
+  LOG("Command: %s", Value::DebugString(stmt->expr).c_str());
 }
 
 void Evaluator::EvalIf(const IfStmt* stmt) {
@@ -318,7 +409,7 @@ void Evaluator::DoInclude(const string& fname) {
   }
 
   Var* var_list = LookupVar(Intern("MAKEFILE_LIST"));
-  var_list->AppendVar(this, NewLiteral(Intern(TrimLeadingCurdir(fname)).str()));
+  var_list->AppendVar(this, Value::NewLiteral(Intern(TrimLeadingCurdir(fname)).str()));
   for (Stmt* stmt : mk->stmts()) {
     LOG("%s", stmt->DebugString().c_str());
     stmt->Eval(this);
@@ -462,4 +553,4 @@ void Evaluator::DumpStackStats() const {
            LOCF(lowest_loc_));
 }
 
-unordered_set<Symbol> Evaluator::used_undefined_vars_;
+SymbolSet Evaluator::used_undefined_vars_;
diff --git a/eval.h b/eval.h
index 4fb5f05..41942d0 100644
--- a/eval.h
+++ b/eval.h
@@ -78,7 +78,7 @@ class Evaluator {
   }
   void clear_delayed_output_commands() { delayed_output_commands_.clear(); }
 
-  static const unordered_set<Symbol>& used_undefined_vars() {
+  static const SymbolSet& used_undefined_vars() {
     return used_undefined_vars_;
   }
 
@@ -114,7 +114,8 @@ class Evaluator {
                Value* rhs,
                StringPiece orig_rhs,
                AssignOp op,
-               bool is_override = false);
+               bool is_override,
+               bool *needs_assign);
   void DoInclude(const string& fname);
 
   Var* LookupVarGlobal(Symbol name);
@@ -122,6 +123,12 @@ class Evaluator {
   // Equivalent to LookupVarInCurrentScope, but doesn't mark as used.
   Var* PeekVarInCurrentScope(Symbol name);
 
+  void MarkVarsReadonly(Value *var_list);
+
+  void EvalRuleSpecificAssign(const vector<Symbol>& targets,
+                              const RuleStmt *stmt,
+                              const StringPiece& lhs_string, size_t separator_pos);
+
   unordered_map<Symbol, Vars*> rule_vars_;
   vector<const Rule*> rules_;
   unordered_map<Symbol, bool> exports_;
@@ -153,9 +160,7 @@ class Evaluator {
   unique_ptr<string> export_message_;
   bool export_error_;
 
-  static unordered_set<Symbol> used_undefined_vars_;
-
-  Symbol kati_readonly_;
+  static SymbolSet used_undefined_vars_;
 };
 
 #endif  // EVAL_H_
diff --git a/expr.cc b/expr.cc
index 5419900..93e268e 100644
--- a/expr.cc
+++ b/expr.cc
@@ -39,11 +39,8 @@ Value::Value() {}
 
 Value::~Value() {}
 
-string Value::DebugString() const {
-  if (static_cast<const Value*>(this)) {
-    return NoLineBreak(DebugString_());
-  }
-  return "(null)";
+string Value::DebugString(const Value *v) {
+  return v ? NoLineBreak(v->DebugString_()) : "(null)";
 }
 
 class Literal : public Value {
@@ -66,19 +63,37 @@ class Literal : public Value {
   StringPiece s_;
 };
 
-class Expr : public Value {
+class ValueList : public Value {
  public:
-  Expr() {}
+  ValueList() {}
+
+  ValueList(Value *v1, Value *v2, Value *v3)
+      :ValueList(){
+    vals_.reserve(3);
+    vals_.push_back(v1);
+    vals_.push_back(v2);
+    vals_.push_back(v3);
+  }
+
+  ValueList(Value *v1, Value *v2):
+      ValueList() {
+    vals_.reserve(2);
+    vals_.push_back(v1);
+    vals_.push_back(v2);
+  }
 
-  virtual ~Expr() {
+  ValueList(vector<Value *> *values):ValueList() {
+    values->shrink_to_fit();
+    values->swap(vals_);
+  }
+
+
+  virtual ~ValueList() {
     for (Value* v : vals_) {
       delete v;
     }
   }
 
-  // Takes the ownership of |v|.
-  void AddValue(Value* v) { vals_.push_back(v); }
-
   virtual void Eval(Evaluator* ev, string* s) const override {
     ev->CheckStack();
     for (Value* v : vals_) {
@@ -90,27 +105,17 @@ class Expr : public Value {
     string r;
     for (Value* v : vals_) {
       if (r.empty()) {
-        r += "Expr(";
+        r += "ValueList(";
       } else {
         r += ", ";
       }
-      r += v->DebugString();
+      r += DebugString(v);
     }
     if (!r.empty())
       r += ")";
     return r;
   }
 
-  virtual Value* Compact() override {
-    if (vals_.size() != 1) {
-      return this;
-    }
-    Value* r = vals_[0];
-    vals_.clear();
-    delete this;
-    return r;
-  }
-
  private:
   vector<Value*> vals_;
 };
@@ -152,7 +157,7 @@ class VarRef : public Value {
   }
 
   virtual string DebugString_() const override {
-    return StringPrintf("VarRef(%s)", name_->DebugString().c_str());
+    return StringPrintf("VarRef(%s)", Value::DebugString(name_).c_str());
   }
 
  private:
@@ -189,9 +194,9 @@ class VarSubst : public Value {
   }
 
   virtual string DebugString_() const override {
-    return StringPrintf("VarSubst(%s:%s=%s)", name_->DebugString().c_str(),
-                        pat_->DebugString().c_str(),
-                        subst_->DebugString().c_str());
+    return StringPrintf("VarSubst(%s:%s=%s)", Value::DebugString(name_).c_str(),
+                        Value::DebugString(pat_).c_str(),
+                        Value::DebugString(subst_).c_str());
   }
 
  private:
@@ -261,6 +266,27 @@ static size_t SkipSpaces(StringPiece s, const char* terms) {
   return s.size();
 }
 
+Value* Value::NewExpr(Value* v1, Value* v2) {
+  return new ValueList(v1, v2);
+}
+
+Value* Value::NewExpr(Value* v1, Value* v2, Value* v3) {
+  return new ValueList(v1, v2, v3);
+}
+
+Value* Value::NewExpr(vector<Value *> *values) {
+  if (values->size() == 1) {
+    Value *v = (*values)[0];
+    values->clear();
+    return v;
+  }
+  return new ValueList(values);
+}
+
+Value* Value::NewLiteral(StringPiece s) {
+  return new Literal(s);
+}
+
 bool ShouldHandleComments(ParseExprOpt opt) {
   return opt != ParseExprOpt::DEFINE && opt != ParseExprOpt::COMMAND;
 }
@@ -399,12 +425,8 @@ Value* ParseDollar(const Loc& loc, StringPiece s, size_t* index_out) {
           ParseExprImpl(loc, s.substr(i + 1), terms, ParseExprOpt::NORMAL, &n);
       i += 1 + n;
       if (s[i] == cp) {
-        Expr* v = new Expr;
-        v->AddValue(vname);
-        v->AddValue(new Literal(":"));
-        v->AddValue(pat);
         *index_out = i + 1;
-        return new VarRef(v);
+        return new VarRef(Value::NewExpr(vname, new Literal(":"), pat));
       }
 
       terms[1] = '\0';
@@ -412,7 +434,7 @@ Value* ParseDollar(const Loc& loc, StringPiece s, size_t* index_out) {
           ParseExprImpl(loc, s.substr(i + 1), terms, ParseExprOpt::NORMAL, &n);
       i += 1 + n;
       *index_out = i + 1;
-      return new VarSubst(vname->Compact(), pat, subst);
+      return new VarSubst(vname, pat, subst);
     }
 
     // GNU make accepts expressions like $((). See unmatched_paren*.mk
@@ -436,11 +458,11 @@ Value* ParseExprImpl(const Loc& loc,
   if (s.get(s.size() - 1) == '\r')
     s.remove_suffix(1);
 
-  Expr* r = new Expr;
   size_t b = 0;
   char save_paren = 0;
   int paren_depth = 0;
   size_t i;
+  vector<Value *> list;
   for (i = 0; i < s.size(); i++) {
     char c = s[i];
     if (terms && strchr(terms, c) && !save_paren) {
@@ -450,13 +472,13 @@ Value* ParseExprImpl(const Loc& loc,
     // Handle a comment.
     if (!terms && c == '#' && ShouldHandleComments(opt)) {
       if (i > b)
-        r->AddValue(new Literal(s.substr(b, i - b)));
+        list.push_back(new Literal(s.substr(b, i - b)));
       bool was_backslash = false;
       for (; i < s.size() && !(s[i] == '\n' && !was_backslash); i++) {
         was_backslash = !was_backslash && s[i] == '\\';
       }
       *index_out = i;
-      return r->Compact();
+      return Value::NewExpr(&list);
     }
 
     if (c == '$') {
@@ -465,10 +487,10 @@ Value* ParseExprImpl(const Loc& loc,
       }
 
       if (i > b)
-        r->AddValue(new Literal(s.substr(b, i - b)));
+        list.push_back(new Literal(s.substr(b, i - b)));
 
       if (s[i + 1] == '$') {
-        r->AddValue(new Literal(StringPiece("$")));
+        list.push_back(new Literal(StringPiece("$")));
         i += 1;
         b = i + 1;
         continue;
@@ -476,15 +498,14 @@ Value* ParseExprImpl(const Loc& loc,
 
       if (terms && strchr(terms, s[i + 1])) {
         *index_out = i + 1;
-        return r->Compact();
+        return Value::NewExpr(&list);
       }
 
       size_t n;
-      Value* v = ParseDollar(loc, s.substr(i), &n);
+      list.push_back(ParseDollar(loc, s.substr(i), &n));
       i += n;
       b = i;
       i--;
-      r->AddValue(v);
       continue;
     }
 
@@ -515,7 +536,7 @@ Value* ParseExprImpl(const Loc& loc,
         continue;
       }
       if (n == '#' && ShouldHandleComments(opt)) {
-        r->AddValue(new Literal(s.substr(b, i - b)));
+        list.push_back(new Literal(s.substr(b, i - b)));
         i++;
         b = i;
         continue;
@@ -525,9 +546,9 @@ Value* ParseExprImpl(const Loc& loc,
           break;
         }
         if (i > b) {
-          r->AddValue(new Literal(TrimRightSpace(s.substr(b, i - b))));
+          list.push_back(new Literal(TrimRightSpace(s.substr(b, i - b))));
         }
-        r->AddValue(new Literal(StringPiece(" ")));
+        list.push_back(new Literal(StringPiece(" ")));
         // Skip the current escaped newline
         i += 2;
         if (n == '\r' && s.get(i) == '\n')
@@ -553,10 +574,10 @@ Value* ParseExprImpl(const Loc& loc,
     if (trim_right_space)
       rest = TrimRightSpace(rest);
     if (!rest.empty())
-      r->AddValue(new Literal(rest));
+      list.push_back(new Literal(rest));
   }
   *index_out = i;
-  return r->Compact();
+  return Value::NewExpr(&list);
 }
 
 Value* ParseExpr(const Loc& loc, StringPiece s, ParseExprOpt opt) {
@@ -567,26 +588,7 @@ Value* ParseExpr(const Loc& loc, StringPiece s, ParseExprOpt opt) {
 string JoinValues(const vector<Value*>& vals, const char* sep) {
   vector<string> val_strs;
   for (Value* v : vals) {
-    val_strs.push_back(v->DebugString());
+    val_strs.push_back(Value::DebugString(v));
   }
   return JoinStrings(val_strs, sep);
 }
-
-Value* NewExpr2(Value* v1, Value* v2) {
-  Expr* e = new Expr();
-  e->AddValue(v1);
-  e->AddValue(v2);
-  return e;
-}
-
-Value* NewExpr3(Value* v1, Value* v2, Value* v3) {
-  Expr* e = new Expr();
-  e->AddValue(v1);
-  e->AddValue(v2);
-  e->AddValue(v3);
-  return e;
-}
-
-Value* NewLiteral(StringPiece s) {
-  return new Literal(s);
-}
diff --git a/expr.h b/expr.h
index 588c6f7..97dbaa5 100644
--- a/expr.h
+++ b/expr.h
@@ -37,15 +37,18 @@ class Evaluable {
 
 class Value : public Evaluable {
  public:
-  virtual ~Value();
-
-  virtual Value* Compact() { return this; }
+  // All NewExpr calls take ownership of the Value instances.
+  static Value *NewExpr(Value *v1, Value *v2);
+  static Value *NewExpr(Value *v1, Value *v2, Value *v3);
+  static Value *NewExpr(vector<Value *> *values);
 
+  static Value *NewLiteral(StringPiece s);
+  virtual ~Value();
   virtual bool IsLiteral() const { return false; }
   // Only safe after IsLiteral() returns true.
   virtual StringPiece GetLiteralValueUnsafe() const { return ""; }
 
-  string DebugString() const;
+  static string DebugString(const Value *);
 
  protected:
   Value();
@@ -71,9 +74,4 @@ Value* ParseExpr(const Loc& loc,
 
 string JoinValues(const vector<Value*>& vals, const char* sep);
 
-Value* NewExpr2(Value* v1, Value* v2);
-Value* NewExpr3(Value* v1, Value* v2, Value* v3);
-
-Value* NewLiteral(StringPiece s);
-
 #endif  // EXPR_H_
diff --git a/func.cc b/func.cc
index c033d3b..15b202d 100644
--- a/func.cc
+++ b/func.cc
@@ -64,6 +64,7 @@ void StripShellComment(string* cmd) {
             in++;
           break;
         }
+        /* FALLTHRU */
 
       case '\'':
       case '"':
@@ -613,7 +614,7 @@ void CallFunc(const vector<Value*>& args, Evaluator* ev, string* s) {
   vector<unique_ptr<ScopedGlobalVar>> sv;
   for (size_t i = 1;; i++) {
     string s;
-    Symbol tmpvar_name_sym(Symbol::IsUninitialized{});
+    Symbol tmpvar_name_sym;
     if (i < sizeof(tmpvar_names) / sizeof(tmpvar_names[0])) {
       tmpvar_name_sym = tmpvar_names[i];
     } else {
diff --git a/main.cc b/main.cc
index 25edbbc..f2360cf 100644
--- a/main.cc
+++ b/main.cc
@@ -121,7 +121,7 @@ static void SetVar(StringPiece l, VarOrigin origin) {
   Symbol lhs = Intern(l.substr(0, found));
   StringPiece rhs = l.substr(found + 1);
   lhs.SetGlobalVar(
-      new RecursiveVar(NewLiteral(rhs.data()), origin, rhs.data()));
+      new RecursiveVar(Value::NewLiteral(rhs.data()), origin, rhs.data()));
 }
 
 extern "C" char** environ;
diff --git a/ninja.cc b/ninja.cc
index d872fb1..495f2f1 100644
--- a/ninja.cc
+++ b/ninja.cc
@@ -228,9 +228,10 @@ class NinjaGenerator {
   }
 
   void PopulateNinjaNode(DepNode* node) {
-    auto p = done_.insert(node->output);
-    if (!p.second)
+    if (done_.exists(node->output)) {
       return;
+    }
+    done_.insert(node->output);
 
     // A hack to exclude out phony target in Android. If this exists,
     // "ninja -t clean" tries to remove this directory and fails.
@@ -628,7 +629,7 @@ class NinjaGenerator {
       fprintf(fp_, "%s", buf.str().c_str());
     }
 
-    unordered_set<Symbol> used_env_vars(Vars::used_env_vars());
+    SymbolSet used_env_vars(Vars::used_env_vars());
     // PATH changes $(shell).
     used_env_vars.insert(Intern("PATH"));
     for (Symbol e : used_env_vars) {
@@ -716,7 +717,6 @@ class NinjaGenerator {
     for (Symbol v : Evaluator::used_undefined_vars()) {
       DumpString(fp, v.str());
     }
-
     DumpInt(fp, used_envs_.size());
     for (const auto& p : used_envs_) {
       DumpString(fp, p.first);
@@ -785,7 +785,7 @@ class NinjaGenerator {
   CommandEvaluator ce_;
   Evaluator* ev_;
   FILE* fp_;
-  unordered_set<Symbol> done_;
+  SymbolSet done_;
   int rule_id_;
   bool use_goma_;
   string gomacc_;
diff --git a/parser.cc b/parser.cc
index 8041c28..050f35d 100644
--- a/parser.cc
+++ b/parser.cc
@@ -221,35 +221,54 @@ class Parser {
     }
 
     const bool is_rule = sep != string::npos && line[sep] == ':';
-    RuleStmt* stmt = new RuleStmt();
-    stmt->set_loc(loc_);
+    RuleStmt* rule_stmt = new RuleStmt();
+    rule_stmt->set_loc(loc_);
 
     size_t found = FindTwoOutsideParen(line.substr(sep + 1), '=', ';');
     if (found != string::npos) {
       found += sep + 1;
-      stmt->term = line[found];
+      rule_stmt->lhs = ParseExpr(TrimSpace(line.substr(0, found)));
+      if (line[found] == ';') {
+        rule_stmt->sep = RuleStmt::SEP_SEMICOLON;
+      } else if (line[found] == '=') {
+        if (line.size() > (found + 2) && line[found + 1] == '$' && line[found + 2] == '=') {
+          rule_stmt->sep = RuleStmt::SEP_FINALEQ;
+          found += 2;
+        } else {
+          rule_stmt->sep = RuleStmt::SEP_EQ;
+        }
+      }
       ParseExprOpt opt =
-          stmt->term == ';' ? ParseExprOpt::COMMAND : ParseExprOpt::NORMAL;
-      stmt->after_term = ParseExpr(TrimLeftSpace(line.substr(found + 1)), opt);
-      stmt->expr = ParseExpr(TrimSpace(line.substr(0, found)));
+          rule_stmt->sep == RuleStmt::SEP_SEMICOLON ? ParseExprOpt::COMMAND : ParseExprOpt::NORMAL;
+      rule_stmt->rhs = ParseExpr(TrimLeftSpace(line.substr(found + 1)), opt);
     } else {
-      stmt->term = 0;
-      stmt->after_term = NULL;
-      stmt->expr = ParseExpr(line);
+      rule_stmt->lhs = ParseExpr(line);
+      rule_stmt->sep = RuleStmt::SEP_NULL;
+      rule_stmt->rhs = NULL;
     }
-    out_stmts_->push_back(stmt);
+    out_stmts_->push_back(rule_stmt);
     state_ = is_rule ? ParserState::AFTER_RULE : ParserState::MAYBE_AFTER_RULE;
   }
 
-  void ParseAssign(StringPiece line, size_t sep) {
-    if (sep == 0) {
+  void ParseAssign(StringPiece line, size_t separator_pos) {
+    if (separator_pos == 0) {
       Error("*** empty variable name ***");
       return;
     }
     StringPiece lhs;
     StringPiece rhs;
     AssignOp op;
-    ParseAssignStatement(line, sep, &lhs, &rhs, &op);
+    ParseAssignStatement(line, separator_pos, &lhs, &rhs, &op);
+
+    // If rhs starts with '$=', this is 'final assignment',
+    // e.g., a combination of the assignment and
+    //  .KATI_READONLY := <lhs>
+    // statement. Note that we assume that ParseAssignStatement
+    // trimmed the left
+    bool is_final = (rhs.size() >= 2 && rhs[0] == '$' && rhs[1] == '=');
+    if (is_final) {
+      rhs = TrimLeftSpace(rhs.substr(2));
+    }
 
     AssignStmt* stmt = new AssignStmt();
     stmt->set_loc(loc_);
@@ -258,6 +277,7 @@ class Parser {
     stmt->orig_rhs = rhs;
     stmt->op = op;
     stmt->directive = current_directive_;
+    stmt->is_final = is_final;
     out_stmts_->push_back(stmt);
     state_ = ParserState::NOT_AFTER_RULE;
   }
diff --git a/rule.cc b/rule.cc
index d4d6610..862a9b8 100644
--- a/rule.cc
+++ b/rule.cc
@@ -23,152 +23,80 @@
 #include "strutil.h"
 #include "symtab.h"
 
-namespace {
+Rule::Rule() : is_double_colon(false), is_suffix_rule(false), cmd_lineno(0) {}
+
 
-static void ParseInputs(Rule* r, StringPiece s) {
+void Rule::ParseInputs(const StringPiece &inputs_str) {
   bool is_order_only = false;
-  for (StringPiece input : WordScanner(s)) {
+  for (auto const& input : WordScanner(inputs_str)) {
     if (input == "|") {
       is_order_only = true;
       continue;
     }
     Symbol input_sym = Intern(TrimLeadingCurdir(input));
-    if (is_order_only) {
-      r->order_only_inputs.push_back(input_sym);
-    } else {
-      r->inputs.push_back(input_sym);
-    }
+    (is_order_only ? order_only_inputs : inputs).push_back(input_sym);
   }
 }
 
-bool IsPatternRule(StringPiece s) {
-  return s.find('%') != string::npos;
-}
-
-}  // namespace
-
-Rule::Rule() : is_double_colon(false), is_suffix_rule(false), cmd_lineno(0) {}
-
-void ParseRule(Loc& loc,
-               StringPiece line,
-               char term,
-               const function<string()>& after_term_fn,
-               Rule** out_rule,
-               RuleVarAssignment* rule_var) {
-  size_t index = line.find(':');
-  if (index == string::npos) {
-    ERROR_LOC(loc, "*** missing separator.");
-  }
-
-  StringPiece first = line.substr(0, index);
-  vector<Symbol> outputs;
-  for (StringPiece tok : WordScanner(first)) {
-    outputs.push_back(Intern(TrimLeadingCurdir(tok)));
-  }
-
-  const bool is_first_pattern =
-      (!outputs.empty() && IsPatternRule(outputs[0].str()));
-  for (size_t i = 1; i < outputs.size(); i++) {
-    if (IsPatternRule(outputs[i].str()) != is_first_pattern) {
-      ERROR_LOC(loc, "*** mixed implicit and normal rules: deprecated syntax");
-    }
-  }
-
-  bool is_double_colon = false;
-  index++;
-  if (line.get(index) == ':') {
-    is_double_colon = true;
-    index++;
-  }
-
-  StringPiece rest = line.substr(index);
-  size_t term_index = rest.find_first_of("=;");
-  string buf;
-  if ((term_index != string::npos && rest[term_index] == '=') ||
-      (term_index == string::npos && term == '=')) {
-    if (term_index == string::npos)
-      term_index = rest.size();
-    // "test: =foo" is questionable but a valid rule definition (not a
-    // target specific variable).
-    // See https://github.com/google/kati/issues/83
-    if (term_index == 0) {
-      KATI_WARN_LOC(loc,
-                    "defining a target which starts with `=', "
-                    "which is not probably what you meant");
-      buf = line.as_string();
-      if (term)
-        buf += term;
-      buf += after_term_fn();
-      line = buf;
-      rest = line.substr(index);
-      term_index = string::npos;
-    } else {
-      rule_var->outputs.swap(outputs);
-      ParseAssignStatement(rest, term_index, &rule_var->lhs, &rule_var->rhs,
-                           &rule_var->op);
-      *out_rule = NULL;
-      return;
-    }
-  }
-
-  Rule* rule = new Rule();
-  *out_rule = rule;
-  rule->loc = loc;
-  rule->is_double_colon = is_double_colon;
-  if (is_first_pattern) {
-    rule->output_patterns.swap(outputs);
-  } else {
-    rule->outputs.swap(outputs);
-  }
-  if (term_index != string::npos && term != ';') {
-    CHECK(rest[term_index] == ';');
+void Rule::ParsePrerequisites(const StringPiece& line,
+                              size_t separator_pos,
+                              const RuleStmt *rule_stmt) {
+  // line is either
+  //    prerequisites [ ; command ]
+  // or
+  //    target-prerequisites : prereq-patterns [ ; command ]
+  // First, separate command. At this point separator_pos should point to ';'
+  // unless null.
+  StringPiece prereq_string = line;
+  if (separator_pos != string::npos && rule_stmt->sep != RuleStmt::SEP_SEMICOLON) {
+    CHECK(line[separator_pos] == ';');
     // TODO: Maybe better to avoid Intern here?
-    rule->cmds.push_back(
-        NewLiteral(Intern(TrimLeftSpace(rest.substr(term_index + 1))).str()));
-    rest = rest.substr(0, term_index);
+    cmds.push_back(Value::NewLiteral(
+        Intern(TrimLeftSpace(line.substr(separator_pos + 1))).str()));
+    prereq_string = line.substr(0, separator_pos);
   }
 
-  index = rest.find(':');
-  if (index == string::npos) {
-    ParseInputs(rule, rest);
+  if ((separator_pos = prereq_string.find(':')) == string::npos) {
+    // Simple prerequisites
+    ParseInputs(prereq_string);
     return;
   }
 
-  if (is_first_pattern) {
+  // Static pattern rule.
+  if (!output_patterns.empty()) {
     ERROR_LOC(loc, "*** mixed implicit and normal rules: deprecated syntax");
   }
 
-  // Empty static patterns should not produce rules, but need to eat the commands
-  // So return a rule with no outputs nor output_patterns
-  if (rule->outputs.empty()) {
+  // Empty static patterns should not produce rules, but need to eat the
+  // commands So return a rule with no outputs nor output_patterns
+  if (outputs.empty()) {
     return;
   }
 
-  StringPiece second = rest.substr(0, index);
-  StringPiece third = rest.substr(index + 1);
+  StringPiece target_prereq = prereq_string.substr(0, separator_pos);
+  StringPiece prereq_patterns = prereq_string.substr(separator_pos + 1);
 
-  for (StringPiece tok : WordScanner(second)) {
-    tok = TrimLeadingCurdir(tok);
-    for (Symbol output : rule->outputs) {
-      if (!Pattern(tok).Match(output.str())) {
+  for (StringPiece target_pattern : WordScanner(target_prereq)) {
+    target_pattern = TrimLeadingCurdir(target_pattern);
+    for (Symbol target : outputs) {
+      if (!Pattern(target_pattern).Match(target.str())) {
         WARN_LOC(loc, "target `%s' doesn't match the target pattern",
-                 output.c_str());
+                 target.c_str());
       }
     }
-
-    rule->output_patterns.push_back(Intern(tok));
+    output_patterns.push_back(Intern(target_pattern));
   }
 
-  if (rule->output_patterns.empty()) {
+  if (output_patterns.empty()) {
     ERROR_LOC(loc, "*** missing target pattern.");
   }
-  if (rule->output_patterns.size() > 1) {
+  if (output_patterns.size() > 1) {
     ERROR_LOC(loc, "*** multiple target patterns.");
   }
-  if (!IsPatternRule(rule->output_patterns[0].str())) {
+  if (!IsPatternRule(output_patterns[0].str())) {
     ERROR_LOC(loc, "*** target pattern contains no '%%'.");
   }
-  ParseInputs(rule, third);
+  ParseInputs(prereq_patterns);
 }
 
 string Rule::DebugString() const {
diff --git a/rule.h b/rule.h
index 4cbca8e..2a555b8 100644
--- a/rule.h
+++ b/rule.h
@@ -37,6 +37,16 @@ class Rule {
 
   string DebugString() const;
 
+  void ParseInputs(const StringPiece& inputs_string);
+
+  void ParsePrerequisites(const StringPiece& line,
+                          size_t pos,
+                          const RuleStmt* rule_stmt);
+
+  static bool IsPatternRule(const StringPiece& target_string) {
+    return target_string.find('%') != string::npos;
+  }
+
   vector<Symbol> outputs;
   vector<Symbol> inputs;
   vector<Symbol> order_only_inputs;
@@ -51,22 +61,5 @@ class Rule {
   void Error(const string& msg) { ERROR_LOC(loc, "%s", msg.c_str()); }
 };
 
-struct RuleVarAssignment {
-  vector<Symbol> outputs;
-  StringPiece lhs;
-  StringPiece rhs;
-  AssignOp op;
-};
-
-// If |rule| is not NULL, |rule_var| is filled. If the expression
-// after the terminator |term| is needed (this happens only when
-// |term| is '='), |after_term_fn| will be called to obtain the right
-// hand side.
-void ParseRule(Loc& loc,
-               StringPiece line,
-               char term,
-               const function<string()>& after_term_fn,
-               Rule** rule,
-               RuleVarAssignment* rule_var);
 
 #endif  // RULE_H_
diff --git a/runtest.rb b/runtest.rb
index 1a341f1..a3c4197 100755
--- a/runtest.rb
+++ b/runtest.rb
@@ -39,6 +39,9 @@ while true
   elsif ARGV[0] == '-v'
     show_failing = true
     ARGV.shift
+  elsif ARGV[0] == "-q"
+    hide_passing = true
+    ARGV.shift
   else
     break
   end
@@ -294,7 +297,9 @@ run_make_test = proc do |mk|
 
     if expected != output
       if expected_failure
-        puts "#{name}: FAIL (expected)"
+        if !hide_passing
+          puts "#{name}: FAIL (expected)"
+        end
         expected_failures << name
       else
         puts "#{name}: FAIL"
@@ -308,7 +313,9 @@ run_make_test = proc do |mk|
         puts "#{name}: PASS (unexpected)"
         unexpected_passes << name
       else
-        puts "#{name}: PASS"
+        if !hide_passing
+          puts "#{name}: PASS"
+        end
         passes << name
       end
     end
@@ -380,7 +387,9 @@ run_shell_test = proc do |sh|
       puts `diff -u out.make out.kati`
       failures << name
     else
-      puts "#{name}: PASS"
+      if !hide_passing
+        puts "#{name}: PASS"
+      end
       passes << name
     end
   end
@@ -398,7 +407,7 @@ end
 
 puts
 
-if !expected_failures.empty?
+if !expected_failures.empty? && !hide_passing
   puts "=== Expected failures ==="
   expected_failures.each do |n|
     puts n
diff --git a/stmt.cc b/stmt.cc
index 44875d0..b558fcc 100644
--- a/stmt.cc
+++ b/stmt.cc
@@ -26,9 +26,9 @@ Stmt::Stmt() {}
 Stmt::~Stmt() {}
 
 string RuleStmt::DebugString() const {
-  return StringPrintf("RuleStmt(expr=%s term=%d after_term=%s loc=%s:%d)",
-                      expr->DebugString().c_str(), term,
-                      after_term->DebugString().c_str(), LOCF(loc()));
+  return StringPrintf("RuleStmt(lhs=%s sep=%d rhs=%s loc=%s:%d)",
+                      Value::DebugString(lhs).c_str(), sep,
+                      Value::DebugString(rhs).c_str(), LOCF(loc()));
 }
 
 string AssignStmt::DebugString() const {
@@ -62,7 +62,7 @@ string AssignStmt::DebugString() const {
   return StringPrintf(
       "AssignStmt(lhs=%s rhs=%s (%s) "
       "opstr=%s dir=%s loc=%s:%d)",
-      lhs->DebugString().c_str(), rhs->DebugString().c_str(),
+      Value::DebugString(lhs).c_str(), Value::DebugString(rhs).c_str(),
       NoLineBreak(orig_rhs.as_string()).c_str(), opstr, dirstr, LOCF(loc()));
 }
 
@@ -80,7 +80,7 @@ Symbol AssignStmt::GetLhsSymbol(Evaluator* ev) const {
 }
 
 string CommandStmt::DebugString() const {
-  return StringPrintf("CommandStmt(%s, loc=%s:%d)", expr->DebugString().c_str(),
+  return StringPrintf("CommandStmt(%s, loc=%s:%d)", Value::DebugString(expr).c_str(),
                       LOCF(loc()));
 }
 
@@ -101,19 +101,19 @@ string IfStmt::DebugString() const {
       break;
   }
   return StringPrintf("IfStmt(op=%s, lhs=%s, rhs=%s t=%zu f=%zu loc=%s:%d)",
-                      opstr, lhs->DebugString().c_str(),
-                      rhs->DebugString().c_str(), true_stmts.size(),
+                      opstr, Value::DebugString(lhs).c_str(),
+                      Value::DebugString(rhs).c_str(), true_stmts.size(),
                       false_stmts.size(), LOCF(loc()));
 }
 
 string IncludeStmt::DebugString() const {
-  return StringPrintf("IncludeStmt(%s, loc=%s:%d)", expr->DebugString().c_str(),
+  return StringPrintf("IncludeStmt(%s, loc=%s:%d)", Value::DebugString(expr).c_str(),
                       LOCF(loc()));
 }
 
 string ExportStmt::DebugString() const {
   return StringPrintf("ExportStmt(%s, %d, loc=%s:%d)",
-                      expr->DebugString().c_str(), is_export, LOCF(loc()));
+                      Value::DebugString(expr).c_str(), is_export, LOCF(loc()));
 }
 
 string ParseErrorStmt::DebugString() const {
@@ -122,8 +122,8 @@ string ParseErrorStmt::DebugString() const {
 }
 
 RuleStmt::~RuleStmt() {
-  delete expr;
-  delete after_term;
+  delete lhs;
+  delete rhs;
 }
 
 void RuleStmt::Eval(Evaluator* ev) const {
diff --git a/stmt.h b/stmt.h
index a08cc87..d7fd067 100644
--- a/stmt.h
+++ b/stmt.h
@@ -27,7 +27,7 @@ using namespace std;
 class Evaluator;
 class Value;
 
-enum struct AssignOp {
+enum struct AssignOp : char {
   EQ,
   COLON_EQ,
   PLUS_EQ,
@@ -67,10 +67,17 @@ struct Stmt {
   StringPiece orig_;
 };
 
+/* Parsed "rule statement" before evaluation is kept as
+ *    <lhs> <sep> <rhs>
+ * where <lhs> and <rhs> as Value instances. <sep> is either command
+ * separator (';') or an assignment ('=' or '=$=').
+ * Until we evaluate <lhs>, we don't know whether it is a rule or
+ * a rule-specific variable assignment.
+ */
 struct RuleStmt : public Stmt {
-  Value* expr;
-  char term;
-  Value* after_term;
+  Value* lhs;
+  enum { SEP_NULL, SEP_SEMICOLON, SEP_EQ, SEP_FINALEQ } sep;
+  Value* rhs;
 
   virtual ~RuleStmt();
 
@@ -85,8 +92,9 @@ struct AssignStmt : public Stmt {
   StringPiece orig_rhs;
   AssignOp op;
   AssignDirective directive;
+  bool is_final;
 
-  AssignStmt() : lhs_sym_cache_(Symbol::IsUninitialized{}) {}
+  AssignStmt() : is_final(false) {}
   virtual ~AssignStmt();
 
   virtual void Eval(Evaluator* ev) const;
diff --git a/symtab.cc b/symtab.cc
index b25e4d6..3d49f2e 100644
--- a/symtab.cc
+++ b/symtab.cc
@@ -30,7 +30,7 @@
 #include "var.h"
 
 struct SymbolData {
-  SymbolData() : gv(kUndefined) {}
+  SymbolData() : gv(Var::Undefined()) {}
 
   Var* gv;
 };
@@ -38,14 +38,15 @@ struct SymbolData {
 vector<string*>* g_symbols;
 static vector<SymbolData> g_symbol_data;
 
-Symbol kEmptySym = Symbol(Symbol::IsUninitialized());
-Symbol kShellSym = Symbol(Symbol::IsUninitialized());
+Symbol kEmptySym;
+Symbol kShellSym;
+Symbol kKatiReadonlySym;
 
 Symbol::Symbol(int v) : v_(v) {}
 
 Var* Symbol::PeekGlobalVar() const {
   if (static_cast<size_t>(v_) >= g_symbol_data.size()) {
-    return kUndefined;
+    return Var::Undefined();
   }
   return g_symbol_data[v_].gv;
 }
@@ -125,6 +126,7 @@ class Symtab {
 
     kEmptySym = Intern("");
     kShellSym = Intern("SHELL");
+    kKatiReadonlySym = Intern(".KATI_READONLY");
   }
 
   ~Symtab() {
diff --git a/symtab.h b/symtab.h
index e9788cf..cd748c8 100644
--- a/symtab.h
+++ b/symtab.h
@@ -15,6 +15,7 @@
 #ifndef SYMTAB_H_
 #define SYMTAB_H_
 
+#include <bitset>
 #include <string>
 #include <vector>
 
@@ -29,8 +30,7 @@ class Var;
 
 class Symbol {
  public:
-  struct IsUninitialized {};
-  explicit Symbol(IsUninitialized) : v_(-1) {}
+  explicit Symbol() : v_(-1) {}
 
   const string& str() const { return *((*g_symbols)[v_]); }
 
@@ -61,6 +61,137 @@ class Symbol {
   int v_;
 
   friend class Symtab;
+  friend class SymbolSet;
+};
+
+/* A set of symbols represented as bitmap indexed by Symbol's ordinal value. */
+class SymbolSet {
+ public:
+  SymbolSet():low_(0), high_(0) {}
+
+  /* Returns true if Symbol belongs to this set. */
+  bool exists(Symbol sym) const {
+    size_t bit_nr = static_cast<size_t>(sym.val());
+    return sym.IsValid() && bit_nr >= low_ && bit_nr < high_ &&
+        bits_[(bit_nr - low_) / 64][(bit_nr - low_) % 64];
+  }
+
+  /* Adds Symbol to this set.  */
+  void insert(Symbol sym) {
+    if (!sym.IsValid()) {
+      return;
+    }
+    size_t bit_nr = static_cast<size_t>(sym.val());
+    if (bit_nr < low_ || bit_nr >= high_) {
+        resize(bit_nr);
+    }
+    bits_[(bit_nr - low_) / 64][(bit_nr - low_) % 64] = true;
+  }
+
+  /* Returns the number of Symbol's in this set.  */
+  size_t size() const {
+    size_t n = 0;
+    for (auto const& bitset : bits_) {
+      n += bitset.count();
+    }
+    return n;
+  }
+
+  /* Allow using foreach.
+   * E.g.,
+   *   SymbolSet symbol_set;
+   *   for (auto const& symbol: symbol_set) { ... }
+   */
+  class iterator {
+    const SymbolSet* bitset_;
+    size_t pos_;
+
+    iterator(const SymbolSet* bitset, size_t pos)
+        :bitset_(bitset), pos_(pos) {
+    }
+
+    /* Proceed to the next Symbol.  */
+    void next() {
+      size_t bit_nr = (pos_ > bitset_->low_) ? pos_ - bitset_->low_ : 0;
+      while (bit_nr < (bitset_->high_ - bitset_->low_)) {
+        if ((bit_nr % 64) == 0 && !bitset_->bits_[bit_nr / 64].any()) {
+          bit_nr += 64;
+          continue;
+        }
+        if (bitset_->bits_[bit_nr / 64][bit_nr % 64]) {
+          break;
+        }
+        ++bit_nr;
+      }
+      pos_ = bitset_->low_ + bit_nr;
+    }
+
+   public:
+    iterator& operator++() {
+      if (pos_ < bitset_->high_) {
+        ++pos_;
+        next();
+      }
+      return *this;
+    }
+
+    bool operator==(iterator other) const {
+      return bitset_ == other.bitset_ && pos_ == other.pos_;
+    }
+
+    bool operator!=(iterator other) const {
+      return !(*this == other);
+    }
+
+    Symbol operator*() {return Symbol(pos_); }
+
+    friend class SymbolSet;
+  };
+
+  iterator begin() const {
+    iterator it(this, low_);
+    it.next();
+    return it;
+  }
+
+  iterator end() const {
+    return iterator(this, high_);
+  }
+
+ private:
+  friend class iterator;
+
+  /* Ensure that given bit number is in [low_, high_)  */
+  void resize(size_t bit_nr) {
+    size_t new_low = bit_nr & ~63;
+    size_t new_high = (bit_nr + 64) & ~63;
+    if (bits_.empty()) {
+      high_ = low_ = new_low;
+    }
+    if (new_low > low_) {
+      new_low = low_;
+    }
+    if (new_high <= high_) {
+      new_high = high_;
+    }
+    if (new_low == low_) {
+      bits_.resize((new_high - new_low) / 64);
+    } else {
+      std::vector<std::bitset<64> > newbits((new_high - new_low)/64);
+      std::copy(bits_.begin(), bits_.end(), newbits.begin() + (low_ - new_low) / 64);
+      bits_.swap(newbits);
+    }
+    low_ = new_low;
+    high_ = new_high;
+  }
+
+  /* Keep only the (aligned) range where at least one bit has been set.
+   * E.g., if we only ever set bits 65 and 141, |low_| will be 64, |high_|
+   * will be 192, and |bits_| will have 2 elements.
+   */
+  size_t low_;
+  size_t high_;
+  std::vector<std::bitset<64> > bits_;
 };
 
 class ScopedGlobalVar {
@@ -90,6 +221,7 @@ struct hash<Symbol> {
 
 extern Symbol kEmptySym;
 extern Symbol kShellSym;
+extern Symbol kKatiReadonlySym;
 
 void InitSymtab();
 void QuitSymtab();
diff --git a/testcase/final_global.sh b/testcase/final_global.sh
new file mode 100644
index 0000000..aae8ab9
--- /dev/null
+++ b/testcase/final_global.sh
@@ -0,0 +1,47 @@
+#!/bin/bash
+#
+# Copyright 2018 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.
+
+set -u
+
+mk="$@"
+
+function build() {
+  cat <<EOF > Makefile
+FOO $1$= bar
+FOO $2 baz
+all:
+EOF
+
+  echo "Testcase: $1 $2"
+  if echo "${mk}" | grep -q "^make"; then
+    # Make doesn't support final assignment
+    echo "Makefile:2: *** cannot assign to readonly variable: FOO"
+  else
+    ${mk} 2>&1 && echo "Clean exit"
+  fi
+}
+
+build "=" "="
+build "=" ":="
+build "=" "+="
+
+build ":=" ":="
+build ":=" "+="
+build ":=" "="
+
+build "+=" ":="
+build "+=" "+="
+build "+=" "="
diff --git a/testcase/final_rule.sh b/testcase/final_rule.sh
new file mode 100644
index 0000000..99a1e74
--- /dev/null
+++ b/testcase/final_rule.sh
@@ -0,0 +1,33 @@
+#!/bin/bash
+#
+# Copyright 2018 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.
+
+set -u
+
+mk="$@"
+
+if echo "${mk}" | grep -q "^make"; then
+  # Make doesn't support final assignment
+  echo "Makefile:3: *** cannot assign to readonly variable: FOO"
+else
+  cat <<EOF > Makefile
+all: FOO :=$= bar
+FOO +=$= foo
+all: FOO +=$= baz
+all:
+EOF
+
+  ${mk} 2>&1 && echo "Clean exit"
+fi
diff --git a/testcase/final_rule2.sh b/testcase/final_rule2.sh
new file mode 100644
index 0000000..fe770c6
--- /dev/null
+++ b/testcase/final_rule2.sh
@@ -0,0 +1,33 @@
+#!/bin/bash
+#
+# Copyright 2018 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.
+
+set -u
+
+mk="$@"
+
+if echo "${mk}" | grep -q "^make"; then
+  # Make doesn't support final assignment
+  echo "Makefile:3: *** cannot assign to readonly variable: FOO"
+else
+  cat <<EOF > Makefile
+all: FOO +=$= bar
+FOO +=$= foo
+all: FOO +=$= baz
+all:
+EOF
+
+  ${mk} 2>&1 && echo "Clean exit"
+fi
diff --git a/var.cc b/var.cc
index 7485c90..6009bb9 100644
--- a/var.cc
+++ b/var.cc
@@ -20,8 +20,7 @@
 #include "expr.h"
 #include "log.h"
 
-UndefinedVar kUndefinedBuf;
-UndefinedVar* kUndefined = &kUndefinedBuf;
+unordered_map<const Var *, string> Var::diagnostic_messages_;
 
 const char* GetOriginStr(VarOrigin origin) {
   switch (origin) {
@@ -46,18 +45,67 @@ const char* GetOriginStr(VarOrigin origin) {
   return "*** broken origin ***";
 }
 
-Var::Var() : readonly_(false), message_(), error_(false) {}
+Var::Var() : Var(VarOrigin::UNDEFINED) {}
 
-Var::~Var() {}
+Var::Var(VarOrigin origin):
+    origin_(origin), readonly_(false), deprecated_(false), obsolete_(false) {
+}
+
+Var::~Var() {
+  diagnostic_messages_.erase(this);
+}
 
 void Var::AppendVar(Evaluator*, Value*) {
   CHECK(false);
 }
 
-SimpleVar::SimpleVar(VarOrigin origin) : origin_(origin) {}
+void Var::SetDeprecated(const StringPiece& msg) {
+  deprecated_ = true;
+  diagnostic_messages_[this] = msg.as_string();
+}
+
+void Var::SetObsolete(const StringPiece& msg) {
+  obsolete_ = true;
+  diagnostic_messages_[this] = msg.as_string();
+}
+
+
+void Var::Used(Evaluator* ev, const Symbol& sym) const {
+  if (obsolete_) {
+    ev->Error(StringPrintf("*** %s is obsolete%s.", sym.c_str(), diagnostic_message_text()));
+  } else if (deprecated_) {
+    WARN_LOC(ev->loc(), "%s has been deprecated%s.", sym.c_str(), diagnostic_message_text());
+  }
+}
+
+const char *Var::diagnostic_message_text() const {
+  auto it = diagnostic_messages_.find(this);
+  return it == diagnostic_messages_.end() ? "" : it->second.c_str();
+}
+
+const string& Var::DeprecatedMessage() const {
+  static const string empty_string;
+  auto it = diagnostic_messages_.find(this);
+  return it == diagnostic_messages_.end() ? empty_string : it->second;
+}
+
+Var *Var::Undefined() {
+  static Var *undefined_var;
+  if (!undefined_var) {
+    undefined_var = new UndefinedVar();
+  }
+  return undefined_var;
+}
+
+SimpleVar::SimpleVar(VarOrigin origin) : Var(origin) {}
 
 SimpleVar::SimpleVar(const string& v, VarOrigin origin)
-    : v_(v), origin_(origin) {}
+    : Var(origin), v_(v) {}
+
+SimpleVar::SimpleVar(VarOrigin origin, Evaluator* ev, Value* v)
+    : Var(origin) {
+  v->Eval(ev, &v_);
+}
 
 void SimpleVar::Eval(Evaluator* ev, string* s) const {
   ev->CheckStack();
@@ -80,7 +128,7 @@ string SimpleVar::DebugString() const {
 }
 
 RecursiveVar::RecursiveVar(Value* v, VarOrigin origin, StringPiece orig)
-    : v_(v), origin_(origin), orig_(orig) {}
+    : Var(origin), v_(v), orig_(orig) {}
 
 void RecursiveVar::Eval(Evaluator* ev, string* s) const {
   ev->CheckStack();
@@ -89,7 +137,7 @@ void RecursiveVar::Eval(Evaluator* ev, string* s) const {
 
 void RecursiveVar::AppendVar(Evaluator* ev, Value* v) {
   ev->CheckStack();
-  v_ = NewExpr3(v_, NewLiteral(" "), v);
+  v_ = Value::NewExpr(v_, Value::NewLiteral(" "), v);
 }
 
 StringPiece RecursiveVar::String() const {
@@ -97,7 +145,7 @@ StringPiece RecursiveVar::String() const {
 }
 
 string RecursiveVar::DebugString() const {
-  return v_->DebugString();
+  return Value::DebugString(v_);
 }
 
 UndefinedVar::UndefinedVar() {}
@@ -127,7 +175,7 @@ void Vars::add_used_env_vars(Symbol v) {
 Var* Vars::Lookup(Symbol name) const {
   auto found = find(name);
   if (found == end())
-    return kUndefined;
+    return Var::Undefined();
   Var* v = found->second;
   if (v->Origin() == VarOrigin::ENVIRONMENT ||
       v->Origin() == VarOrigin::ENVIRONMENT_OVERRIDE) {
@@ -138,9 +186,7 @@ Var* Vars::Lookup(Symbol name) const {
 
 Var* Vars::Peek(Symbol name) const {
   auto found = find(name);
-  if (found == end())
-    return kUndefined;
-  return found->second;
+  return found == end() ? Var::Undefined() : found->second;
 }
 
 void Vars::Assign(Symbol name, Var* v, bool* readonly) {
@@ -165,7 +211,7 @@ void Vars::Assign(Symbol name, Var* v, bool* readonly) {
   }
 }
 
-unordered_set<Symbol> Vars::used_env_vars_;
+SymbolSet Vars::used_env_vars_;
 
 ScopedVar::ScopedVar(Vars* vars, Symbol name, Var* var)
     : vars_(vars), orig_(NULL) {
diff --git a/var.h b/var.h
index be6363f..e1ae105 100644
--- a/var.h
+++ b/var.h
@@ -32,7 +32,7 @@ using namespace std;
 class Evaluator;
 class Value;
 
-enum struct VarOrigin {
+enum struct VarOrigin : char {
   UNDEFINED,
   DEFAULT,
   ENVIRONMENT,
@@ -50,7 +50,8 @@ class Var : public Evaluable {
   virtual ~Var();
 
   virtual const char* Flavor() const = 0;
-  virtual VarOrigin Origin() const = 0;
+
+  VarOrigin Origin() { return origin_; }
   virtual bool IsDefined() const { return true; }
 
   virtual void AppendVar(Evaluator* ev, Value* v);
@@ -62,50 +63,45 @@ class Var : public Evaluable {
   bool ReadOnly() const { return readonly_; }
   void SetReadOnly() { readonly_ = true; }
 
-  bool Deprecated() const { return message_ && !error_; }
-  void SetDeprecated(StringPiece msg) {
-    message_.reset(new string(msg.as_string()));
-  }
+  bool Deprecated() const { return deprecated_; }
+  void SetDeprecated(const StringPiece& msg);
 
-  bool Obsolete() const { return error_; }
-  void SetObsolete(StringPiece msg) {
-    message_.reset(new string(msg.as_string()));
-    error_ = true;
-  }
+  bool Obsolete() const { return obsolete_; }
+  void SetObsolete(const StringPiece& msg);
 
-  const string& DeprecatedMessage() const { return *message_; }
+  const string& DeprecatedMessage() const;
 
   // This variable was used (either written or read from)
-  void Used(Evaluator* ev, const Symbol& sym) const {
-    if (!message_) {
-      return;
-    }
-
-    if (error_) {
-      ev->Error(StringPrintf("*** %s is obsolete%s.", sym.c_str(),
-                             message_->c_str()));
-    } else {
-      WARN_LOC(ev->loc(), "%s has been deprecated%s.", sym.c_str(),
-               message_->c_str());
-    }
-  }
+  void Used(Evaluator* ev, const Symbol& sym) const;
+
+  AssignOp op() const { return assign_op_; }
+  void SetAssignOp(AssignOp op) { assign_op_ = op; }
+
+  static Var *Undefined();
 
  protected:
   Var();
+  explicit Var(VarOrigin origin);
 
  private:
-  bool readonly_;
-  unique_ptr<string> message_;
-  bool error_;
+  const VarOrigin origin_;
+  AssignOp assign_op_;
+  bool readonly_:1;
+  bool deprecated_:1;
+  bool obsolete_:1;
+
+  const char *diagnostic_message_text() const;
+
+  static unordered_map<const Var *, string> diagnostic_messages_;
 };
 
 class SimpleVar : public Var {
  public:
   explicit SimpleVar(VarOrigin origin);
   SimpleVar(const string& v, VarOrigin origin);
+  SimpleVar(VarOrigin, Evaluator* ev, Value* v);
 
   virtual const char* Flavor() const override { return "simple"; }
-  virtual VarOrigin Origin() const override { return origin_; }
 
   virtual void Eval(Evaluator* ev, string* s) const override;
 
@@ -115,11 +111,8 @@ class SimpleVar : public Var {
 
   virtual string DebugString() const override;
 
-  string* mutable_value() { return &v_; }
-
  private:
   string v_;
-  VarOrigin origin_;
 };
 
 class RecursiveVar : public Var {
@@ -127,7 +120,6 @@ class RecursiveVar : public Var {
   RecursiveVar(Value* v, VarOrigin origin, StringPiece orig);
 
   virtual const char* Flavor() const override { return "recursive"; }
-  virtual VarOrigin Origin() const override { return origin_; }
 
   virtual void Eval(Evaluator* ev, string* s) const override;
 
@@ -139,7 +131,6 @@ class RecursiveVar : public Var {
 
  private:
   Value* v_;
-  VarOrigin origin_;
   StringPiece orig_;
 };
 
@@ -148,7 +139,6 @@ class UndefinedVar : public Var {
   UndefinedVar();
 
   virtual const char* Flavor() const override { return "undefined"; }
-  virtual VarOrigin Origin() const override { return VarOrigin::UNDEFINED; }
   virtual bool IsDefined() const override { return false; }
 
   virtual void Eval(Evaluator* ev, string* s) const override;
@@ -158,33 +148,6 @@ class UndefinedVar : public Var {
   virtual string DebugString() const override;
 };
 
-extern UndefinedVar* kUndefined;
-
-class RuleVar : public Var {
- public:
-  RuleVar(Var* v, AssignOp op) : v_(v), op_(op) {}
-  virtual ~RuleVar() { delete v_; }
-
-  virtual const char* Flavor() const override { return v_->Flavor(); }
-  virtual VarOrigin Origin() const override { return v_->Origin(); }
-  virtual bool IsDefined() const override { return v_->IsDefined(); }
-  virtual void Eval(Evaluator* ev, string* s) const override {
-    v_->Eval(ev, s);
-  }
-  virtual void AppendVar(Evaluator* ev, Value* v) override {
-    v_->AppendVar(ev, v);
-  }
-  virtual StringPiece String() const override { return v_->String(); }
-  virtual string DebugString() const override { return v_->DebugString(); }
-
-  Var* v() const { return v_; }
-  AssignOp op() const { return op_; }
-
- private:
-  Var* v_;
-  AssignOp op_;
-};
-
 class Vars : public unordered_map<Symbol, Var*> {
  public:
   ~Vars();
@@ -196,10 +159,10 @@ class Vars : public unordered_map<Symbol, Var*> {
 
   static void add_used_env_vars(Symbol v);
 
-  static const unordered_set<Symbol>& used_env_vars() { return used_env_vars_; }
+  static const SymbolSet used_env_vars() { return used_env_vars_; }
 
  private:
-  static unordered_set<Symbol> used_env_vars_;
+  static SymbolSet used_env_vars_;
 };
 
 class ScopedVar {