[C++] The first commit for C++ version

16 tests out of 169 are passing.

38 files changed, 2662 insertions, 7 deletions

diff --git a/Makefile b/Makefile
index 68007db..57e82c5 100644
--- a/Makefile
+++ b/Makefile
@@ -12,24 +12,59 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-GOSRC = $(wildcard *.go)
+GO_SRCS:=$(wildcard *.go)
+CXX_SRCS:= \
+	ast.cc \
+	dep.cc \
+	eval.cc \
+	exec.cc \
+	file.cc \
+	file_cache.cc \
+	fileutil.cc \
+	func.cc \
+	main.cc \
+	parser.cc \
+	rule.cc \
+	string_piece.cc \
+	string_pool.cc \
+	stringprintf.cc \
+	strutil.cc \
+	value.cc \
+	var.cc
+CXX_TEST_SRCS:= \
+	$(wildcard *_test.cc)
+CXX_OBJS:=$(CXX_SRCS:.cc=.o)
+CXX_TEST_OBJS:=$(CXX_TEST_SRCS:.cc=.o)
+CXX_ALL_OBJS:=$(CXX_SRCS:.cc=.o) $(CXX_TEST_SRCS:.cc=.o)
+CXX_TEST_EXES:=$(CXX_TEST_OBJS:.o=)
+CXXFLAGS:=-g -W -Wall -MMD # -O
 
-all: kati go_test para
+all: kati para ckati $(CXX_TEST_EXES)
 
-kati: $(GOSRC)
+kati: $(GO_SRCS)
 	env $(shell go env) go build -o $@ *.go
 
-go_test: $(GOSRC) para
+ckati: $(CXX_OBJS)
+	$(CXX) -std=c++11 $(CXXFLAGS) -o $@ $(CXX_OBJS)
+
+$(CXX_ALL_OBJS): %.o: %.cc
+	$(CXX) -c -std=c++11 $(CXXFLAGS) -o $@ $<
+
+$(CXX_TEST_EXES): $(filter-out main.o,$(CXX_OBJS))
+$(CXX_TEST_EXES): %: %.o
+	$(CXX) $^ -o $@
+
+go_test: $(GO_SRCS) para
 	env $(shell go env) go test *.go
 
 para: para.cc
 	$(CXX) -std=c++11 -g -O -W -Wall -MMD -o $@ $<
 
-test: all
+test: all go_test
 	ruby runtest.rb
 
 clean:
-	rm -rf out kati
+	rm -rf out kati ckati *.o *.d
 
 .PHONY: test
 
diff --git a/ast.cc b/ast.cc
new file mode 100644
index 0000000..fdd4588
--- /dev/null
+++ b/ast.cc
@@ -0,0 +1,67 @@
+#include "ast.h"
+
+#include "eval.h"
+#include "stringprintf.h"
+#include "value.h"
+
+AST::AST() {}
+
+AST::~AST() {}
+
+string RuleAST::DebugString() const {
+  return StringPrintf("RuleAST(expr=%s term=%d after_term=%s)",
+                      expr->DebugString().c_str(),
+                      term,
+                      after_term->DebugString().c_str());
+}
+
+string AssignAST::DebugString() const {
+  const char* opstr = "???";
+  switch (op) {
+    case AssignOp::EQ: opstr = "EQ"; break;
+    case AssignOp::COLON_EQ: opstr = "COLON_EQ"; break;
+    case AssignOp::PLUS_EQ: opstr = "PLUS_EQ"; break;
+    case AssignOp::QUESTION_EQ: opstr = "QUESTION_EQ"; break;
+  }
+  const char* dirstr = "???";
+  switch (directive) {
+    case AssignDirective::NONE: dirstr = ""; break;
+    case AssignDirective::OVERRIDE: dirstr = "override"; break;
+    case AssignDirective::EXPORT: dirstr = "export"; break;
+  }
+  return StringPrintf("AssignAST(lhs=%s rhs=%s opstr=%s dir=%s)",
+                      lhs->DebugString().c_str(),
+                      rhs->DebugString().c_str(),
+                      opstr, dirstr);
+}
+
+string CommandAST::DebugString() const {
+  return StringPrintf("CommandAST(%s)",
+                      expr->DebugString().c_str());
+}
+
+RuleAST::~RuleAST() {
+  delete expr;
+  delete after_term;
+}
+
+void RuleAST::Eval(Evaluator* ev) const {
+  ev->EvalRule(this);
+}
+
+AssignAST::~AssignAST() {
+  delete lhs;
+  delete rhs;
+}
+
+void AssignAST::Eval(Evaluator* ev) const {
+  ev->EvalAssign(this);
+}
+
+CommandAST::~CommandAST() {
+  delete expr;
+}
+
+void CommandAST::Eval(Evaluator* ev) const {
+  ev->EvalCommand(this);
+}
diff --git a/ast.h b/ast.h
new file mode 100644
index 0000000..8c0ceea
--- /dev/null
+++ b/ast.h
@@ -0,0 +1,82 @@
+#ifndef AST_H_
+#define AST_H_
+
+#include <string>
+
+#include "loc.h"
+#include "string_piece.h"
+
+using namespace std;
+
+class Evaluator;
+struct Value;
+
+enum struct AssignOp {
+  EQ,
+  COLON_EQ,
+  PLUS_EQ,
+  QUESTION_EQ,
+};
+
+enum struct AssignDirective {
+  NONE,
+  OVERRIDE,
+  EXPORT,
+};
+
+struct AST {
+ public:
+  virtual ~AST();
+
+  Loc loc() const { return loc_; }
+  void set_loc(Loc loc) { loc_ = loc; }
+  StringPiece orig() const { return orig_; }
+
+  virtual void Eval(Evaluator* ev) const = 0;
+
+  virtual string DebugString() const = 0;
+
+ protected:
+  AST();
+
+ private:
+  Loc loc_;
+  StringPiece orig_;
+};
+
+struct RuleAST : public AST {
+  Value* expr;
+  char term;
+  Value* after_term;
+
+  virtual ~RuleAST();
+
+  virtual void Eval(Evaluator* ev) const;
+
+  virtual string DebugString() const;
+};
+
+struct AssignAST : public AST {
+  Value* lhs;
+  Value* rhs;
+  AssignOp op;
+  AssignDirective directive;
+
+  virtual ~AssignAST();
+
+  virtual void Eval(Evaluator* ev) const;
+
+  virtual string DebugString() const;
+};
+
+struct CommandAST : public AST {
+  Value* expr;
+
+  virtual ~CommandAST();
+
+  virtual void Eval(Evaluator* ev) const;
+
+  virtual string DebugString() const;
+};
+
+#endif  // AST_H_
diff --git a/dep.cc b/dep.cc
new file mode 100644
index 0000000..426b1a2
--- /dev/null
+++ b/dep.cc
@@ -0,0 +1,193 @@
+#include "dep.h"
+
+#include <memory>
+
+#include "log.h"
+#include "rule.h"
+#include "var.h"
+
+static vector<DepNode*>* g_dep_node_pool;
+
+DepNode::DepNode(StringPiece o, bool p)
+    : output(o),
+      has_rule(false),
+      is_order_only(false),
+      is_phony(p),
+      target_specific_vars(NULL) {
+  g_dep_node_pool->push_back(this);
+}
+
+class DepBuilder {
+ public:
+  DepBuilder(const vector<Rule*>& rules,
+             const Vars& vars,
+             const unordered_map<StringPiece, Vars*>& rule_vars)
+      : vars_(vars),
+        rule_vars_(rule_vars),
+        first_rule_(NULL) {
+    PopulateRules(rules);
+  }
+
+  void Build(vector<StringPiece> targets,
+             vector<DepNode*>* nodes) {
+    if (targets.empty()) {
+      if (!first_rule_) {
+        ERROR("*** No targets.");
+      }
+      CHECK(!first_rule_->outputs.empty());
+      targets.push_back(first_rule_->outputs[0]);
+    }
+
+    // TODO: LogStats?
+
+    for (StringPiece target : targets) {
+      unique_ptr<Vars> tsvs(new Vars);
+      DepNode* n = BuildPlan(target, "", tsvs.get());
+      nodes->push_back(n);
+    }
+  }
+
+ private:
+  void PopulateRules(const vector<Rule*>& rules) {
+    for (Rule* rule : rules) {
+      if (rule->outputs.empty()) {
+        PopulateImplicitRule(rule);
+      } else {
+        PopulateExplicitRule(rule);
+      }
+    }
+  }
+
+  void PopulateExplicitRule(Rule* rule) {
+    for (StringPiece output : rule->outputs) {
+      // isSuffixRule := db.populateSuffixRule(rule, output)
+
+
+      /*
+          if oldRule, present := db.rules[output]; present {
+     r := mergeRules(oldRule, rule, output, isSuffixRule)
+                                                         db.rules[output] = r
+                                                         } else {
+        db.rules[output] = rule
+            if db.firstRule == nil && !strings.HasPrefix(output, ".") {
+                db.firstRule = rule
+              }
+      }
+      */
+
+      auto p = rules_.insert(make_pair(output, rule));
+      if (p.second) {
+        if (!first_rule_ && output.get(0) != '.') {
+          first_rule_ = rule;
+        }
+      } else {
+        // TODO: merge
+        CHECK(false);
+      }
+    }
+  }
+
+  void PopulateImplicitRule(Rule*) {
+    CHECK(false);
+  }
+
+  Rule* LookupRule(StringPiece o) {
+    auto found = rules_.find(o);
+    if (found != rules_.end())
+      return found->second;
+    return NULL;
+  }
+
+  Vars* LookupRuleVars(StringPiece o) {
+    auto found = rule_vars_.find(o);
+    if (found != rule_vars_.end())
+      return found->second;
+    return NULL;
+  }
+
+  bool PickRule(StringPiece output, Rule** r, Vars** v) {
+    Rule* rule = LookupRule(output);
+    Vars* vars = LookupRuleVars(output);
+    *r = rule;
+    *v = vars;
+    if (rule) {
+      if (!rule->cmds.empty()) {
+        return true;
+      }
+    }
+    return rule;
+  }
+
+  DepNode* BuildPlan(StringPiece output, StringPiece needed_by, Vars* tsvs) {
+    LOG("BuildPlan: %s for %s",
+        output.as_string().c_str(),
+        needed_by.as_string().c_str());
+
+    auto found = done_.find(output);
+    if (found != done_.end()) {
+      return found->second;
+    }
+
+    DepNode* n = new DepNode(output, phony_[output]);
+    done_[output] = n;
+
+    Rule* rule;
+    Vars* vars;
+    if (!PickRule(output, &rule, &vars)) {
+      return n;
+    }
+
+    // TODO: Handle TSVs
+
+    for (StringPiece input : rule->inputs) {
+      if (rule->output_patterns.size() > 0) {
+        if (rule->output_patterns.size() > 1) {
+          ERROR("TODO: multiple output pattern is not supported yet");
+        }
+        ERROR("TODO");
+      }
+
+      n->actual_inputs.push_back(input);
+      DepNode* c = BuildPlan(input, output, tsvs);
+      n->deps.push_back(c);
+    }
+
+    // TODO: order only
+    n->has_rule = true;
+    n->cmds = rule->cmds;
+
+    return n;
+  }
+
+  unordered_map<StringPiece, Rule*> rules_;
+  const Vars& vars_;
+  const unordered_map<StringPiece, Vars*>& rule_vars_;
+
+  vector<Rule*> implicit_rules_;   // pattern=%. no prefix,suffix.
+  //vector<Rule*> iprefix_rules_;   // pattern=prefix%..  may have suffix
+  //vector<Rule*> isuffix_rules_;   // pattern=%suffix  no prefix
+
+  unordered_map<StringPiece, vector<Rule*>> suffix_rules_;
+  Rule* first_rule_;
+  unordered_map<StringPiece, DepNode*> done_;
+  unordered_map<StringPiece, bool> phony_;
+};
+
+void MakeDep(const vector<Rule*>& rules,
+             const Vars& vars,
+             const unordered_map<StringPiece, Vars*>& rule_vars,
+             const vector<StringPiece>& targets,
+             vector<DepNode*>* nodes) {
+  DepBuilder db(rules, vars, rule_vars);
+  db.Build(targets, nodes);
+}
+
+void InitDepNodePool() {
+  g_dep_node_pool = new vector<DepNode*>;
+}
+
+void QuitDepNodePool() {
+  for (DepNode* n : *g_dep_node_pool)
+    delete n;
+  delete g_dep_node_pool;
+}
diff --git a/dep.h b/dep.h
new file mode 100644
index 0000000..d829b10
--- /dev/null
+++ b/dep.h
@@ -0,0 +1,39 @@
+#ifndef DEP_H_
+#define DEP_H_
+
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include "loc.h"
+#include "string_piece.h"
+
+class Rule;
+class Value;
+class Vars;
+
+struct DepNode {
+  DepNode(StringPiece output, bool is_phony);
+
+  StringPiece output;
+  vector<Value*> cmds;
+  vector<DepNode*> deps;
+  vector<DepNode*> parents;
+  bool has_rule;
+  bool is_order_only;
+  bool is_phony;
+  vector<StringPiece> actual_inputs;
+  Vars* target_specific_vars;
+  Loc loc;
+};
+
+void InitDepNodePool();
+void QuitDepNodePool();
+
+void MakeDep(const vector<Rule*>& rules,
+             const Vars& vars,
+             const unordered_map<StringPiece, Vars*>& rule_vars,
+             const vector<StringPiece>& targets,
+             vector<DepNode*>* nodes);
+
+#endif  // DEP_H_
diff --git a/eval.cc b/eval.cc
new file mode 100644
index 0000000..bd2e253
--- /dev/null
+++ b/eval.cc
@@ -0,0 +1,128 @@
+#include "eval.h"
+
+#include "ast.h"
+#include "file.h"
+#include "rule.h"
+#include "strutil.h"
+#include "value.h"
+#include "var.h"
+
+EvalResult::~EvalResult() {
+  for (Rule* r : rules)
+    delete r;
+  for (auto p : rule_vars)
+    delete p.second;
+  delete vars;
+}
+
+Evaluator::Evaluator(const Vars* vars)
+    : in_vars_(vars),
+      vars_(new Vars()),
+      last_rule_(NULL) {
+}
+
+Evaluator::~Evaluator() {
+  for (Rule* r : rules_) {
+    delete r;
+  }
+  delete vars_;
+  // for (auto p : rule_vars) {
+  //   delete p.second;
+  // }
+}
+
+void Evaluator::EvalAssign(const AssignAST* ast) {
+  loc_ = ast->loc();
+  last_rule_ = NULL;
+
+  const char* origin = "file";
+
+  StringPiece lhs = Intern(*ast->lhs->Eval(this));
+  Var* rhs = NULL;
+  switch (ast->op) {
+    case AssignOp::COLON_EQ:
+      rhs = new SimpleVar(ast->rhs->Eval(this), origin);
+      break;
+    case AssignOp::EQ:
+      rhs = new RecursiveVar(ast->rhs, origin);
+      break;
+    case AssignOp::PLUS_EQ: {
+      Var* prev = LookupVarInCurrentScope(lhs);
+      if (!prev->IsDefined()) {
+        rhs = new RecursiveVar(ast->rhs, origin);
+      } else {
+        // TODO
+        abort();
+      }
+      break;
+    }
+    case AssignOp::QUESTION_EQ: {
+      Var* prev = LookupVarInCurrentScope(lhs);
+      if (!prev->IsDefined()) {
+        rhs = new RecursiveVar(ast->rhs, origin);
+      } else {
+        // TODO
+        abort();
+      }
+      break;
+    }
+  }
+
+  LOG("Assign: %.*s=%s", SPF(lhs), rhs->DebugString().c_str());
+  vars_->Assign(lhs, rhs);
+}
+
+void Evaluator::EvalRule(const RuleAST* ast) {
+  loc_ = ast->loc();
+  last_rule_ = NULL;
+
+  shared_ptr<string> expr = ast->expr->Eval(this);
+  // See semicolon.mk.
+  if (expr->find_first_not_of(" \t\n;") == string::npos)
+    return;
+
+  Rule* rule = new Rule;
+  rule->loc = loc_;
+  rule->Parse(*expr);
+
+  LOG("Rule: %s", rule->DebugString().c_str());
+  rules_.push_back(rule);
+  last_rule_ = rule;
+}
+
+void Evaluator::EvalCommand(const CommandAST* ast) {
+  loc_ = ast->loc();
+
+  if (!last_rule_) {
+    // TODO:
+    ERROR("TODO");
+  }
+
+  last_rule_->cmds.push_back(ast->expr);
+  LOG("Command: %s", ast->expr->DebugString().c_str());
+}
+
+Var* Evaluator::LookupVar(StringPiece name) {
+  // TODO: TSV.
+  Var* v = vars_->Lookup(name);
+  if (v->IsDefined())
+    return v;
+  return in_vars_->Lookup(name);
+}
+
+Var* Evaluator::LookupVarInCurrentScope(StringPiece name) {
+  // TODO: TSV.
+  Var* v = vars_->Lookup(name);
+  if (v->IsDefined())
+    return v;
+  return in_vars_->Lookup(name);
+}
+
+EvalResult* Evaluator::GetEvalResult() {
+  EvalResult* er = new EvalResult;
+  er->rules.swap(rules_);
+  er->vars = vars_;
+  vars_ = NULL;
+  er->rule_vars.swap(rule_vars_);
+  return er;
+}
diff --git a/eval.h b/eval.h
new file mode 100644
index 0000000..78cc307
--- /dev/null
+++ b/eval.h
@@ -0,0 +1,62 @@
+#ifndef EVAL_H_
+#define EVAL_H_
+
+#include <unordered_map>
+#include <vector>
+
+#include "loc.h"
+#include "string_piece.h"
+
+using namespace std;
+
+class AssignAST;
+class CommandAST;
+class Makefile;
+class Rule;
+class RuleAST;
+class Var;
+class Vars;
+
+struct EvalResult {
+  ~EvalResult();
+  vector<Rule*> rules;
+  Vars* vars;
+  unordered_map<StringPiece, Vars*> rule_vars;
+  // TODO: read_mks
+  unordered_map<StringPiece, bool> exports;
+};
+
+class Evaluator {
+ public:
+  Evaluator(const Vars* vars);
+  ~Evaluator();
+
+  void EvalAssign(const AssignAST* ast);
+  void EvalRule(const RuleAST* ast);
+  void EvalCommand(const CommandAST* ast);
+
+  Var* LookupVar(StringPiece name);
+  // For target specific variables.
+  Var* LookupVarInCurrentScope(StringPiece name);
+
+  EvalResult* GetEvalResult();
+
+#if 0
+  const vector<Rule*>& rules() const { return rules_; }
+  const Vars* vars() const { return vars_; }
+  const unordered_map<StringPiece, Vars*>& rule_vars() const {
+    return rule_vars_;
+  }
+#endif
+
+ private:
+  const Vars* in_vars_;
+  Vars* vars_;
+  unordered_map<StringPiece, Vars*> rule_vars_;
+  vector<Rule*> rules_;
+  Rule* last_rule_;
+
+  Loc loc_;
+};
+
+#endif  // EVAL_H_
diff --git a/exec.cc b/exec.cc
new file mode 100644
index 0000000..82f49b0
--- /dev/null
+++ b/exec.cc
@@ -0,0 +1,85 @@
+#include "exec.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <memory>
+#include <unordered_map>
+
+#include "dep.h"
+#include "eval.h"
+#include "log.h"
+#include "string_piece.h"
+#include "value.h"
+
+namespace {
+
+struct Runner {
+  Runner()
+      : echo(true), ignore_error(false) {
+  }
+  StringPiece output;
+  shared_ptr<string> cmd;
+  bool echo;
+  bool ignore_error;
+  //StringPiece shell;
+};
+
+}  // namespace
+
+class Executor {
+ public:
+  explicit Executor(const Vars* vars)
+      : vars_(vars) {
+  }
+
+  void ExecNode(DepNode* n, DepNode* needed_by) {
+    if (done_[n->output])
+      return;
+
+    LOG("ExecNode: %s for %s",
+        n->output.as_string().c_str(),
+        needed_by ? needed_by->output.as_string().c_str() : "(null)");
+
+    for (DepNode* d : n->deps) {
+#if 0
+      if (d.is_order_only && exists(d->output)) {
+      }
+#endif
+      ExecNode(d, n);
+    }
+
+    vector<Runner*> runners;
+    CreateRunners(n, &runners);
+    for (Runner* runner : runners) {
+      if (runner->echo) {
+        printf("%s\n", runner->cmd->c_str());
+        fflush(stdout);
+      }
+      system(runner->cmd->c_str());
+      delete runner;
+    }
+  }
+
+  void CreateRunners(DepNode* n, vector<Runner*>* runners) {
+    unique_ptr<Evaluator> ev(new Evaluator(vars_));
+    for (Value* v : n->cmds) {
+      Runner* runner = new Runner;
+      runner->output = n->output;
+      runner->cmd = v->Eval(ev.get());
+      runners->push_back(runner);
+    }
+  }
+
+ private:
+  const Vars* vars_;
+  unordered_map<StringPiece, bool> done_;
+
+};
+
+void Exec(const vector<DepNode*>& roots, const Vars* vars) {
+  unique_ptr<Executor> executor(new Executor(vars));
+  for (DepNode* root : roots) {
+    executor->ExecNode(root, NULL);
+  }
+}
diff --git a/exec.h b/exec.h
new file mode 100644
index 0000000..0f5944a
--- /dev/null
+++ b/exec.h
@@ -0,0 +1,13 @@
+#ifndef EXEC_H_
+#define EXEC_H_
+
+#include <vector>
+
+using namespace std;
+
+class DepNode;
+class Vars;
+
+void Exec(const vector<DepNode*>& roots, const Vars* vars);
+
+#endif  // EXEC_H_
diff --git a/file.cc b/file.cc
new file mode 100644
index 0000000..9f3c147
--- /dev/null
+++ b/file.cc
@@ -0,0 +1,45 @@
+#include "file.h"
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include "ast.h"
+#include "log.h"
+#include "parser.h"
+
+Makefile::Makefile(const string& filename)
+    : len_(0), mtime_(0), filename_(filename) {
+  int fd = open(filename.c_str(), O_RDONLY);
+  if (fd < 0) {
+    return;
+  }
+
+  struct stat st;
+  if (fstat(fd, &st) < 0) {
+    PERROR("fstat failed for %s", filename.c_str());
+  }
+
+  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_)) {
+    if (r < 0)
+      PERROR("read failed for %s", filename.c_str());
+    ERROR("Unexpected read length=%zd expected=%zu", r, len_);
+  }
+
+  if (close(fd) < 0) {
+    PERROR("close failed for %s", filename.c_str());
+  }
+
+  Parse(this);
+}
+
+Makefile::~Makefile() {
+  delete[] buf_;
+  for (AST* ast : asts_)
+    delete ast;
+}
diff --git a/file.h b/file.h
new file mode 100644
index 0000000..a053073
--- /dev/null
+++ b/file.h
@@ -0,0 +1,37 @@
+#ifndef FILE_H_
+#define FILE_H_
+
+#include <stdint.h>
+
+#include <string>
+#include <vector>
+
+#include "string_pool.h"
+
+using namespace std;
+
+class AST;
+
+class Makefile {
+ public:
+  explicit Makefile(const string& filename);
+  ~Makefile();
+
+  const char* buf() const { return buf_; }
+  size_t len() const { return len_; }
+  const string& filename() const { return filename_; }
+
+  StringPool* mutable_pool() { return &pool_; }
+  const vector<AST*>& asts() const { return asts_; }
+  vector<AST*>* mutable_asts() { return &asts_; }
+
+ private:
+  char* buf_;
+  size_t len_;
+  uint64_t mtime_;
+  string filename_;
+  StringPool pool_;
+  vector<AST*> asts_;
+};
+
+#endif  // FILE_H_
diff --git a/file_cache.cc b/file_cache.cc
new file mode 100644
index 0000000..eb64328
--- /dev/null
+++ b/file_cache.cc
@@ -0,0 +1,36 @@
+#include "file_cache.h"
+
+#include <unordered_map>
+
+#include "file.h"
+
+MakefileCacheManager::MakefileCacheManager() {}
+
+MakefileCacheManager::~MakefileCacheManager() {}
+
+class MakefileCacheManagerImpl : public MakefileCacheManager {
+ public:
+  virtual ~MakefileCacheManagerImpl() {
+    for (auto p : cache_) {
+      delete p.second;
+    }
+  }
+
+  virtual Makefile* ReadMakefile(const string& filename) override {
+    Makefile* result = NULL;
+    auto p = cache_.insert(make_pair(filename, result));
+    if (p.second) {
+      p.first->second = result = new Makefile(filename);
+    } else {
+      result = p.first->second;
+    }
+    return result;
+  }
+
+private:
+  unordered_map<string, Makefile*> cache_;
+};
+
+MakefileCacheManager* NewMakefileCacheManager() {
+  return new MakefileCacheManagerImpl();
+}
diff --git a/file_cache.h b/file_cache.h
new file mode 100644
index 0000000..7b3b3ff
--- /dev/null
+++ b/file_cache.h
@@ -0,0 +1,23 @@
+#ifndef FILE_CACHE_H_
+#define FILE_CACHE_H_
+
+#include <string>
+
+using namespace std;
+
+class Makefile;
+
+class MakefileCacheManager {
+ public:
+  virtual ~MakefileCacheManager();
+
+  virtual Makefile* ReadMakefile(const string& filename) = 0;
+
+ protected:
+  MakefileCacheManager();
+
+};
+
+MakefileCacheManager* NewMakefileCacheManager();
+
+#endif  // FILE_CACHE_H_
diff --git a/fileutil.cc b/fileutil.cc
new file mode 100644
index 0000000..51f080e
--- /dev/null
+++ b/fileutil.cc
@@ -0,0 +1,20 @@
+#include "fileutil.h"
+
+#include <errno.h>
+#include <limits.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include "log.h"
+
+bool Exists(StringPiece filename) {
+  CHECK(filename.size() < PATH_MAX);
+  char buf[PATH_MAX+1];
+  memcpy(buf, filename.data(), filename.size());
+  buf[filename.size()] = 0;
+  struct stat st;
+  if (stat(buf, &st) < 0) {
+    return false;
+  }
+  return true;
+}
diff --git a/fileutil.h b/fileutil.h
new file mode 100644
index 0000000..31b7318
--- /dev/null
+++ b/fileutil.h
@@ -0,0 +1,8 @@
+#ifndef FILEUTIL_H_
+#define FILEUTIL_H_
+
+#include "string_piece.h"
+
+bool Exists(StringPiece f);
+
+#endif  // FILEUTIL_H_
diff --git a/func.cc b/func.cc
new file mode 100644
index 0000000..2910193
--- /dev/null
+++ b/func.cc
@@ -0,0 +1,44 @@
+#include "func.h"
+
+#include <stdio.h>
+
+#include <unordered_map>
+
+#include "log.h"
+#include "strutil.h"
+
+namespace {
+
+void BuiltinInfoFunc(const vector<Value*>& args, Evaluator* ev, string*) {
+  shared_ptr<string> a = args[0]->Eval(ev);
+  printf("%s\n", a->c_str());
+  fflush(stdout);
+}
+
+FuncInfo g_func_infos[] = {
+  { "info", &BuiltinInfoFunc, 1 },
+};
+
+unordered_map<StringPiece, FuncInfo*>* g_func_info_map;
+
+}  // namespace
+
+void InitFuncTable() {
+  g_func_info_map = new unordered_map<StringPiece, FuncInfo*>;
+  for (size_t i = 0; i < sizeof(g_func_infos) / sizeof(g_func_infos[0]); i++) {
+    FuncInfo* fi = &g_func_infos[i];
+    bool ok = g_func_info_map->insert(make_pair(Intern(fi->name), fi)).second;
+    CHECK(ok);
+  }
+}
+
+void QuitFuncTable() {
+  delete g_func_info_map;
+}
+
+FuncInfo* GetFuncInfo(StringPiece name) {
+  auto found = g_func_info_map->find(name);
+  if (found == g_func_info_map->end())
+    return NULL;
+  return found->second;
+}
diff --git a/func.h b/func.h
new file mode 100644
index 0000000..cd5f3b3
--- /dev/null
+++ b/func.h
@@ -0,0 +1,21 @@
+#ifndef FUNC_H_
+#define FUNC_H_
+
+#include <vector>
+
+#include "value.h"
+
+using namespace std;
+
+struct FuncInfo {
+  const char* name;
+  void (*func)(const vector<Value*>& args, Evaluator* ev, string* s);
+  int arity;
+};
+
+void InitFuncTable();
+void QuitFuncTable();
+
+FuncInfo* GetFuncInfo(StringPiece name);
+
+#endif  // FUNC_H_
diff --git a/loc.h b/loc.h
new file mode 100644
index 0000000..2884915
--- /dev/null
+++ b/loc.h
@@ -0,0 +1,19 @@
+#ifndef LOC_H_
+#define LOC_H_
+
+#include <string>
+
+#include "stringprintf.h"
+
+struct Loc {
+  Loc()
+      : filename(0), lineno(-1) {}
+  Loc(const char* f, int l)
+      : filename(f), lineno(l) {
+  }
+
+  const char* filename;
+  int lineno;
+};
+
+#endif  // LOC_H_
diff --git a/log.h b/log.h
new file mode 100644
index 0000000..6fb0326
--- /dev/null
+++ b/log.h
@@ -0,0 +1,31 @@
+#ifndef LOG_H_
+#define LOG_H_
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define LOG(fmt, ...) do {                                              \
+    char buf[999];                                                      \
+    sprintf(buf, fmt, __VA_ARGS__);                                     \
+    fprintf(stderr, "*kati*: %s\n", buf);                               \
+  } while(0)
+
+#define PERROR(...) do {                                        \
+    char buf[999];                                              \
+    sprintf(buf, __VA_ARGS__);                                  \
+    fprintf(stderr, "%s: %s\n", buf, strerror(errno));          \
+    exit(1);                                                    \
+  } while (0)
+
+#define ERROR(...) do {                                         \
+    char buf[999];                                              \
+    sprintf(buf, __VA_ARGS__);                                  \
+    fprintf(stderr, "%s\n", buf);                               \
+    exit(1);                                                    \
+  } while (0)
+
+#define CHECK(c) if (!(c)) ERROR("%s:%d: %s", __FILE__, __LINE__, #c)
+
+#endif  // LOG_H_
diff --git a/main.cc b/main.cc
new file mode 100644
index 0000000..cdb06ee
--- /dev/null
+++ b/main.cc
@@ -0,0 +1,96 @@
+#include <stdio.h>
+#include <string.h>
+
+#include "ast.h"
+#include "dep.h"
+#include "eval.h"
+#include "exec.h"
+#include "file.h"
+#include "file_cache.h"
+#include "fileutil.h"
+#include "func.h"
+#include "log.h"
+#include "string_piece.h"
+#include "strutil.h"
+#include "var.h"
+
+static const char* g_makefile;
+
+static void ParseCommandLine(int argc, char* argv[],
+                             vector<StringPiece>* targets) {
+  for (int i = 1; i < argc; i++) {
+    const char* arg = argv[i];
+    if (!strcmp(arg, "-f")) {
+      g_makefile = argv[++i];
+    } else if (arg[0] == '-') {
+      ERROR("Unknown flag: %s", arg);
+    } else {
+      targets->push_back(Intern(arg));
+    }
+  }
+}
+
+static void Init() {
+  InitSymtab();
+  InitFuncTable();
+  InitDepNodePool();
+
+  if (g_makefile == NULL) {
+    if (Exists("GNUmakefile")) {
+      g_makefile = "GNUmakefile";
+    } else if (Exists("makefile")) {
+      g_makefile = "makefile";
+    } else if (Exists("Makefile")) {
+      g_makefile = "Makefile";
+    } else {
+      ERROR("*** No targets specified and no makefile found.");
+    }
+  }
+}
+
+static void Quit() {
+  QuitDepNodePool();
+  QuitFuncTable();
+  QuitSymtab();
+}
+
+static int Run(const vector<StringPiece>& targets) {
+  MakefileCacheManager* cache_mgr = NewMakefileCacheManager();
+  Makefile* mk = cache_mgr->ReadMakefile(g_makefile);
+
+  // TODO: Fill env, etc.
+  Vars* vars = new Vars();
+  Evaluator* ev = new Evaluator(vars);
+  for (AST* ast : mk->asts()) {
+    LOG("%s", ast->DebugString().c_str());
+
+    ast->Eval(ev);
+  }
+
+  EvalResult* er = ev->GetEvalResult();
+  for (auto p : *er->vars) {
+    vars->Assign(p.first, p.second);
+  }
+  er->vars->clear();
+
+  vector<DepNode*> nodes;
+  MakeDep(er->rules, *vars, er->rule_vars, targets, &nodes);
+
+  Exec(nodes, vars);
+
+  delete er;
+  delete ev;
+  delete vars;
+  delete cache_mgr;
+
+  return mk != 0;
+}
+
+int main(int argc, char* argv[]) {
+  Init();
+  vector<StringPiece> targets;
+  ParseCommandLine(argc, argv, &targets);
+  int r = Run(targets);
+  Quit();
+  return r;
+}
diff --git a/parser.cc b/parser.cc
new file mode 100644
index 0000000..526b8fe
--- /dev/null
+++ b/parser.cc
@@ -0,0 +1,164 @@
+#include "parser.h"
+
+#include "ast.h"
+#include "file.h"
+#include "loc.h"
+#include "log.h"
+#include "string_piece.h"
+#include "value.h"
+
+enum struct ParserState {
+  NOT_AFTER_RULE = 0,
+  AFTER_RULE,
+  MAYBE_AFTER_RULE,
+};
+
+class Parser {
+ public:
+  Parser(StringPiece buf, const char* filename, vector<AST*>* asts)
+      : buf_(buf),
+        state_(ParserState::NOT_AFTER_RULE),
+        out_asts_(asts),
+        loc_(filename, 0),
+        fixed_lineno_(false) {
+  }
+
+  ~Parser() {
+  }
+
+  void Parse() {
+    l_ = 0;
+
+    for (l_ = 0; l_ < buf_.size();) {
+      if (!fixed_lineno_)
+        ++loc_.lineno;
+      size_t lf_cnt = 0;
+      size_t e = FindEndOfLine(&lf_cnt);
+      StringPiece line(buf_.data() + l_, e - l_);
+      ParseLine(line);
+      if (e == buf_.size())
+        break;
+
+      l_ = e + 1;
+      loc_.lineno += lf_cnt;
+    }
+  }
+
+ private:
+  void Error(const string& msg) {
+    ERROR("%s:%d: %s", loc_.filename, loc_.lineno, msg.c_str());
+  }
+
+  size_t FindEndOfLine(size_t* lf_cnt) {
+    size_t e = l_;
+    bool prev_backslash = false;
+    for (; e < buf_.size(); e++) {
+      char c = buf_[e];
+      if (c == '\\') {
+        prev_backslash = !prev_backslash;
+      } else if (c == '\n') {
+        ++*lf_cnt;
+        if (!prev_backslash) {
+          return e;
+        }
+      } else if (c != '\r') {
+        prev_backslash = false;
+      }
+    }
+    return e;
+  }
+
+  void ParseLine(StringPiece line) {
+    if (line.empty() || (line.size() == 1 && line[0] == '\r'))
+      return;
+
+    if (line[0] == '\t' && state_ != ParserState::NOT_AFTER_RULE) {
+      CommandAST* ast = new CommandAST();
+      ast->expr = ParseExpr(line.substr(1), true);
+      out_asts_->push_back(ast);
+      return;
+    }
+
+    // TODO: directive.
+
+    size_t sep = line.find_first_of(STRING_PIECE("=:"));
+    if (sep == string::npos) {
+      ParseRuleAST(line, sep);
+    } else if (line[sep] == '=') {
+      ParseAssignAST(line, sep);
+    } else if (line.get(sep+1) == '=') {
+      ParseAssignAST(line, sep+1);
+    } else if (line[sep] == ':') {
+      ParseRuleAST(line, sep);
+    } else {
+      CHECK(false);
+    }
+  }
+
+  void ParseRuleAST(StringPiece line, size_t sep) {
+    const bool is_rule = line.find(':') != string::npos;
+    RuleAST* ast = new RuleAST;
+    ast->set_loc(loc_);
+
+    size_t found = line.substr(sep + 1).find_first_of("=;");
+    if (found != string::npos) {
+      found += sep + 1;
+      ast->term = line[found];
+      ast->after_term = ParseExpr(line.substr(found + 1).StripLeftSpaces(),
+                                  ast->term == ';');
+      ast->expr = ParseExpr(line.substr(0, found).StripSpaces(), false);
+    } else {
+      ast->term = 0;
+      ast->after_term = NULL;
+      ast->expr = ParseExpr(line.StripSpaces(), false);
+    }
+    out_asts_->push_back(ast);
+    state_ = is_rule ? ParserState::AFTER_RULE : ParserState::MAYBE_AFTER_RULE;
+  }
+
+  void ParseAssignAST(StringPiece line, size_t sep) {
+    if (sep == 0)
+      Error("*** empty variable name ***");
+    AssignOp op = AssignOp::EQ;
+    size_t lhs_end = sep;
+    switch (line[sep-1]) {
+      case ':':
+        lhs_end--;
+        op = AssignOp::COLON_EQ;
+        break;
+      case '+':
+        lhs_end--;
+        op = AssignOp::PLUS_EQ;
+        break;
+      case '?':
+        lhs_end--;
+        op = AssignOp::QUESTION_EQ;
+        break;
+    }
+
+    AssignAST* ast = new AssignAST;
+    ast->set_loc(loc_);
+    ast->lhs = ParseExpr(line.substr(0, lhs_end).StripSpaces(), false);
+    ast->rhs = ParseExpr(line.substr(sep + 1).StripLeftSpaces(), false);
+    ast->op = op;
+    ast->directive = AssignDirective::NONE;
+    out_asts_->push_back(ast);
+    state_ = ParserState::NOT_AFTER_RULE;
+  }
+
+  StringPiece buf_;
+  size_t l_;
+  ParserState state_;
+
+  vector<AST*>* out_asts_;
+
+  Loc loc_;
+  bool fixed_lineno_;
+};
+
+void Parse(Makefile* mk) {
+  Parser parser(StringPiece(mk->buf(), mk->len()),
+                mk->filename().c_str(),
+                mk->mutable_asts());
+  parser.Parse();
+}
diff --git a/parser.h b/parser.h
new file mode 100644
index 0000000..b82741b
--- /dev/null
+++ b/parser.h
@@ -0,0 +1,8 @@
+#ifndef PARSER_H_
+#define PARSER_H_
+
+class Makefile;
+
+void Parse(Makefile* mk);
+
+#endif  // PARSER_H_
diff --git a/rule.cc b/rule.cc
new file mode 100644
index 0000000..54280a3
--- /dev/null
+++ b/rule.cc
@@ -0,0 +1,88 @@
+#include "rule.h"
+
+#include "log.h"
+#include "stringprintf.h"
+#include "strutil.h"
+#include "value.h"
+
+// Strip leading sequences of './' from file names, so that ./file
+// and file are considered to be the same file.
+// From http://www.gnu.org/software/make/manual/make.html#Features
+StringPiece TrimLeadingCurdir(StringPiece s) {
+  if (s.substr(0, 2) != "./")
+    return s;
+  return s.substr(2);
+}
+
+static void ParseInputs(Rule* r, StringPiece s) {
+  bool is_order_only = false;
+  for (StringPiece input : WordScanner(s)) {
+    if (input == "|") {
+      is_order_only = true;
+      continue;
+    }
+    input = Intern(TrimLeadingCurdir(input));
+    if (is_order_only) {
+      r->order_only_inputs.push_back(input);
+    } else {
+      r->inputs.push_back(input);
+    }
+  }
+}
+
+Rule::Rule()
+    : is_double_colon(false),
+      is_suffix_rule(false),
+      cmd_lineno(0) {
+}
+
+void Rule::Parse(StringPiece line) {
+  size_t index = line.find(':');
+  if (index == string::npos) {
+    Error("*** missing separator.");
+  }
+
+  StringPiece first = line.substr(0, index);
+  // TODO: isPattern?
+  if (false) {
+  } else {
+    for (StringPiece tok : WordScanner(first)) {
+      outputs.push_back(Intern(TrimLeadingCurdir(tok)));
+    }
+  }
+
+  index++;
+  if (line.get(index) == ':') {
+    is_double_colon = true;
+    index++;
+  }
+
+  StringPiece rest = line.substr(index);
+
+  // TODO: TSV
+  //if (
+
+  index = rest.find(':');
+  if (index == string::npos) {
+    ParseInputs(this, rest);
+    return;
+  }
+}
+
+string Rule::DebugString() const {
+  vector<string> v;
+  v.push_back(StringPrintf("outputs=[%s]", JoinStrings(outputs, ",").c_str()));
+  v.push_back(StringPrintf("inputs=[%s]", JoinStrings(inputs, ",").c_str()));
+  if (!order_only_inputs.empty()) {
+    v.push_back(StringPrintf("order_only_inputs=[%s]",
+                             JoinStrings(order_only_inputs, ",").c_str()));
+  }
+  if (is_double_colon)
+    v.push_back("is_double_colon");
+  if (is_suffix_rule)
+    v.push_back("is_suffix_rule");
+  if (!cmds.empty()) {
+    v.push_back(StringPrintf("cmds=[%s]", JoinValues(cmds, ",").c_str()));
+  }
+  return JoinStrings(v, " ");
+}
diff --git a/rule.h b/rule.h
new file mode 100644
index 0000000..071ad48
--- /dev/null
+++ b/rule.h
@@ -0,0 +1,37 @@
+#ifndef RULE_H_
+#define RULE_H_
+
+#include <vector>
+
+#include "loc.h"
+#include "log.h"
+#include "string_piece.h"
+
+using namespace std;
+
+class Value;
+
+class Rule {
+ public:
+  Rule();
+  void Parse(StringPiece line);
+
+  string DebugString() const;
+
+  vector<StringPiece> outputs;
+  vector<StringPiece> inputs;
+  vector<StringPiece> order_only_inputs;
+  vector<string> output_patterns;
+  bool is_double_colon;
+  bool is_suffix_rule;
+  vector<Value*> cmds;
+  Loc loc;
+  int cmd_lineno;
+
+ private:
+  void Error(const string& msg) {
+    ERROR("%s:%d: %s", loc.filename, loc.lineno, msg.c_str());
+  }
+};
+
+#endif  // RULE_H_
diff --git a/runtest.rb b/runtest.rb
index 2313a10..e3f4e6c 100755
--- a/runtest.rb
+++ b/runtest.rb
@@ -18,6 +18,9 @@ require 'fileutils'
 
 if ARGV[0] == '-s'
   test_serialization = true
+elsif ARGV[0] == '-c'
+  ckati = true
+  ARGV.shift
 end
 
 def get_output_filenames
@@ -110,6 +113,11 @@ run_make_test = proc do |mk|
   expected_failure = c =~ /\A# TODO/
 
   run_in_testdir(mk) do |name|
+    # TODO: Fix
+    if name =~ /eval_assign/ && ckati
+      next
+    end
+
     File.open("Makefile", 'w') do |ofile|
       ofile.print(c)
     end
@@ -135,6 +143,9 @@ run_make_test = proc do |mk|
     testcases.each do |tc|
       json = "#{tc.empty? ? 'test' : tc}"
       cmd = "../../kati -save_json=#{json}.json -kati_log #{tc} 2>&1"
+      if ckati
+        cmd = "../../ckati #{tc} 2>&1"
+      end
       res = IO.popen(cmd, 'r:binary', &:read)
       res = normalize_kati_log(res)
       output += "=== #{tc} ===\n" + res
@@ -251,7 +262,7 @@ end
 puts
 
 if !unexpected_passes.empty? || !failures.empty?
-  puts 'FAIL!'
+  puts "FAIL! (#{failures.size + unexpected_passes.size} fails #{passes.size} passes)"
 else
   puts 'PASS!'
 end
diff --git a/string_piece.cc b/string_piece.cc
new file mode 100644
index 0000000..074acf3
--- /dev/null
+++ b/string_piece.cc
@@ -0,0 +1,231 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+// Copied from strings/stringpiece.cc with modifications
+
+#include <ctype.h>
+#include <limits.h>
+
+#include <algorithm>
+#include <ostream>
+
+#include "string_piece.h"
+
+typedef StringPiece::size_type size_type;
+
+bool operator==(const StringPiece& x, const StringPiece& y) {
+  if (x.size() != y.size())
+    return false;
+
+  return StringPiece::wordmemcmp(x.data(), y.data(), x.size()) == 0;
+}
+
+void StringPiece::CopyToString(std::string* target) const {
+  target->assign(!empty() ? data() : "", size());
+}
+
+void StringPiece::AppendToString(std::string* target) const {
+  if (!empty())
+    target->append(data(), size());
+}
+
+size_type StringPiece::copy(char* buf, size_type n, size_type pos) const {
+  size_type ret = std::min(length_ - pos, n);
+  memcpy(buf, ptr_ + pos, ret);
+  return ret;
+}
+
+size_type StringPiece::find(const StringPiece& s, size_type pos) const {
+  if (pos > length_)
+    return npos;
+
+  const char* result = std::search(ptr_ + pos, ptr_ + length_,
+                                   s.ptr_, s.ptr_ + s.length_);
+  const size_type xpos = result - ptr_;
+  return xpos + s.length_ <= length_ ? xpos : npos;
+}
+
+size_type StringPiece::find(char c, size_type pos) const {
+  if (pos >= length_)
+    return npos;
+
+  const char* result = std::find(ptr_ + pos, ptr_ + length_, c);
+  return result != ptr_ + length_ ? static_cast<size_t>(result - ptr_) : npos;
+}
+
+size_type StringPiece::rfind(const StringPiece& s, size_type pos) const {
+  if (length_ < s.length_)
+    return npos;
+
+  if (s.empty())
+    return std::min(length_, pos);
+
+  const char* last = ptr_ + std::min(length_ - s.length_, pos) + s.length_;
+  const char* result = std::find_end(ptr_, last, s.ptr_, s.ptr_ + s.length_);
+  return result != last ? static_cast<size_t>(result - ptr_) : npos;
+}
+
+size_type StringPiece::rfind(char c, size_type pos) const {
+  if (length_ == 0)
+    return npos;
+
+  for (size_type i = std::min(pos, length_ - 1); ; --i) {
+    if (ptr_[i] == c)
+      return i;
+    if (i == 0)
+      break;
+  }
+  return npos;
+}
+
+// For each character in characters_wanted, sets the index corresponding
+// to the ASCII code of that character to 1 in table.  This is used by
+// the find_.*_of methods below to tell whether or not a character is in
+// the lookup table in constant time.
+// The argument `table' must be an array that is large enough to hold all
+// the possible values of an unsigned char.  Thus it should be be declared
+// as follows:
+//   bool table[UCHAR_MAX + 1]
+static inline void BuildLookupTable(const StringPiece& characters_wanted,
+                                    bool* table) {
+  const size_type length = characters_wanted.length();
+  const char* const data = characters_wanted.data();
+  for (size_type i = 0; i < length; ++i) {
+    table[static_cast<unsigned char>(data[i])] = true;
+  }
+}
+
+size_type StringPiece::find_first_of(const StringPiece& s,
+                                     size_type pos) const {
+  if (length_ == 0 || s.length_ == 0)
+    return npos;
+
+  // Avoid the cost of BuildLookupTable() for a single-character search.
+  if (s.length_ == 1)
+    return find_first_of(s.ptr_[0], pos);
+
+  bool lookup[UCHAR_MAX + 1] = { false };
+  BuildLookupTable(s, lookup);
+  for (size_type i = pos; i < length_; ++i) {
+    if (lookup[static_cast<unsigned char>(ptr_[i])]) {
+      return i;
+    }
+  }
+  return npos;
+}
+
+size_type StringPiece::find_first_not_of(const StringPiece& s,
+                                         size_type pos) const {
+  if (length_ == 0)
+    return npos;
+
+  if (s.length_ == 0)
+    return 0;
+
+  // Avoid the cost of BuildLookupTable() for a single-character search.
+  if (s.length_ == 1)
+    return find_first_not_of(s.ptr_[0], pos);
+
+  bool lookup[UCHAR_MAX + 1] = { false };
+  BuildLookupTable(s, lookup);
+  for (size_type i = pos; i < length_; ++i) {
+    if (!lookup[static_cast<unsigned char>(ptr_[i])]) {
+      return i;
+    }
+  }
+  return npos;
+}
+
+size_type StringPiece::find_first_not_of(char c, size_type pos) const {
+  if (length_ == 0)
+    return npos;
+
+  for (; pos < length_; ++pos) {
+    if (ptr_[pos] != c) {
+      return pos;
+    }
+  }
+  return npos;
+}
+
+size_type StringPiece::find_last_of(const StringPiece& s, size_type pos) const {
+  if (length_ == 0 || s.length_ == 0)
+    return npos;
+
+  // Avoid the cost of BuildLookupTable() for a single-character search.
+  if (s.length_ == 1)
+    return find_last_of(s.ptr_[0], pos);
+
+  bool lookup[UCHAR_MAX + 1] = { false };
+  BuildLookupTable(s, lookup);
+  for (size_type i = std::min(pos, length_ - 1); ; --i) {
+    if (lookup[static_cast<unsigned char>(ptr_[i])])
+      return i;
+    if (i == 0)
+      break;
+  }
+  return npos;
+}
+
+size_type StringPiece::find_last_not_of(const StringPiece& s,
+                                        size_type pos) const {
+  if (length_ == 0)
+    return npos;
+
+  size_type i = std::min(pos, length_ - 1);
+  if (s.length_ == 0)
+    return i;
+
+  // Avoid the cost of BuildLookupTable() for a single-character search.
+  if (s.length_ == 1)
+    return find_last_not_of(s.ptr_[0], pos);
+
+  bool lookup[UCHAR_MAX + 1] = { false };
+  BuildLookupTable(s, lookup);
+  for (; ; --i) {
+    if (!lookup[static_cast<unsigned char>(ptr_[i])])
+      return i;
+    if (i == 0)
+      break;
+  }
+  return npos;
+}
+
+size_type StringPiece::find_last_not_of(char c, size_type pos) const {
+  if (length_ == 0)
+    return npos;
+
+  for (size_type i = std::min(pos, length_ - 1); ; --i) {
+    if (ptr_[i] != c)
+      return i;
+    if (i == 0)
+      break;
+  }
+  return npos;
+}
+
+StringPiece StringPiece::substr(size_type pos, size_type n) const {
+  if (pos > length_) pos = length_;
+  if (n > length_ - pos) n = length_ - pos;
+  return StringPiece(ptr_ + pos, n);
+}
+
+const StringPiece::size_type StringPiece::npos = size_type(-1);
+
+StringPiece StringPiece::StripLeftSpaces() const {
+  size_t i = 0;
+  while (i < size() && isspace(ptr_[i]))
+    i++;
+  return StringPiece(ptr_ + i, size() - i);
+}
+
+StringPiece StringPiece::StripRightSpaces() const {
+  size_t i = 0;
+  while (i < size() && isspace(ptr_[size() - 1 - i]))
+    i++;
+  return StringPiece(ptr_, size() - i);
+}
+
+StringPiece StringPiece::StripSpaces() const {
+  return StripLeftSpaces().StripRightSpaces();
+}
diff --git a/string_piece.h b/string_piece.h
new file mode 100644
index 0000000..7e20e13
--- /dev/null
+++ b/string_piece.h
@@ -0,0 +1,217 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+// Copied from strings/stringpiece.h with modifications
+//
+// A string-like object that points to a sized piece of memory.
+//
+// Functions or methods may use const StringPiece& parameters to accept either
+// a "const char*" or a "string" value that will be implicitly converted to
+// a StringPiece.  The implicit conversion means that it is often appropriate
+// to include this .h file in other files rather than forward-declaring
+// StringPiece as would be appropriate for most other Google classes.
+//
+// Systematic usage of StringPiece is encouraged as it will reduce unnecessary
+// conversions from "const char*" to "string" and back again.
+//
+
+#ifndef BASE_STRING_PIECE_H_
+#define BASE_STRING_PIECE_H_
+#pragma once
+
+#include <stddef.h>
+#include <string.h>
+
+#include <string>
+
+//#include "base/base_api.h"
+//#include "base/basictypes.h"
+
+#define STRING_PIECE(s) StringPiece(s, sizeof(s) - 1)
+
+class StringPiece {
+ public:
+  // standard STL container boilerplate
+  typedef size_t size_type;
+  typedef char value_type;
+  typedef const char* pointer;
+  typedef const char& reference;
+  typedef const char& const_reference;
+  typedef ptrdiff_t difference_type;
+  typedef const char* const_iterator;
+  typedef const char* iterator;
+  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+  typedef std::reverse_iterator<iterator> reverse_iterator;
+
+  static const size_type npos;
+
+ public:
+  // We provide non-explicit singleton constructors so users can pass
+  // in a "const char*" or a "string" wherever a "StringPiece" is
+  // expected.
+  StringPiece() : ptr_(NULL), length_(0) { }
+  StringPiece(const char* str)
+    : ptr_(str), length_((str == NULL) ? 0 : strlen(str)) { }
+  StringPiece(const std::string& str)
+    : ptr_(str.data()), length_(str.size()) { }
+  StringPiece(const char* offset, size_type len)
+    : ptr_(offset), length_(len) { }
+
+  // data() may return a pointer to a buffer with embedded NULs, and the
+  // returned buffer may or may not be null terminated.  Therefore it is
+  // typically a mistake to pass data() to a routine that expects a NUL
+  // terminated string.
+  const char* data() const { return ptr_; }
+  size_type size() const { return length_; }
+  size_type length() const { return length_; }
+  bool empty() const { return length_ == 0; }
+
+  void clear() {
+    ptr_ = NULL;
+    length_ = 0;
+  }
+  void set(const char* data, size_type len) {
+    ptr_ = data;
+    length_ = len;
+  }
+  void set(const char* str) {
+    ptr_ = str;
+    length_ = str ? strlen(str) : 0;
+  }
+  void set(const void* data, size_type len) {
+    ptr_ = reinterpret_cast<const char*>(data);
+    length_ = len;
+  }
+
+  char operator[](size_type i) const { return ptr_[i]; }
+
+  void remove_prefix(size_type n) {
+    ptr_ += n;
+    length_ -= n;
+  }
+
+  void remove_suffix(size_type n) {
+    length_ -= n;
+  }
+
+  int compare(const StringPiece& x) const {
+    int r = wordmemcmp(
+        ptr_, x.ptr_, (length_ < x.length_ ? length_ : x.length_));
+    if (r == 0) {
+      if (length_ < x.length_) r = -1;
+      else if (length_ > x.length_) r = +1;
+    }
+    return r;
+  }
+
+  std::string as_string() const {
+    // std::string doesn't like to take a NULL pointer even with a 0 size.
+    return std::string(!empty() ? data() : "", size());
+  }
+
+  void CopyToString(std::string* target) const;
+  void AppendToString(std::string* target) const;
+
+  // Does "this" start with "x"
+  bool starts_with(const StringPiece& x) const {
+    return ((length_ >= x.length_) &&
+            (wordmemcmp(ptr_, x.ptr_, x.length_) == 0));
+  }
+
+  // Does "this" end with "x"
+  bool ends_with(const StringPiece& x) const {
+    return ((length_ >= x.length_) &&
+            (wordmemcmp(ptr_ + (length_-x.length_), x.ptr_, x.length_) == 0));
+  }
+
+  iterator begin() const { return ptr_; }
+  iterator end() const { return ptr_ + length_; }
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(ptr_ + length_);
+  }
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(ptr_);
+  }
+
+  size_type max_size() const { return length_; }
+  size_type capacity() const { return length_; }
+
+  size_type copy(char* buf, size_type n, size_type pos = 0) const;
+
+  size_type find(const StringPiece& s, size_type pos = 0) const;
+  size_type find(char c, size_type pos = 0) const;
+  size_type rfind(const StringPiece& s, size_type pos = npos) const;
+  size_type rfind(char c, size_type pos = npos) const;
+
+  size_type find_first_of(const StringPiece& s, size_type pos = 0) const;
+  size_type find_first_of(char c, size_type pos = 0) const {
+    return find(c, pos);
+  }
+  size_type find_first_not_of(const StringPiece& s, size_type pos = 0) const;
+  size_type find_first_not_of(char c, size_type pos = 0) const;
+  size_type find_last_of(const StringPiece& s, size_type pos = npos) const;
+  size_type find_last_of(char c, size_type pos = npos) const {
+    return rfind(c, pos);
+  }
+  size_type find_last_not_of(const StringPiece& s, size_type pos = npos) const;
+  size_type find_last_not_of(char c, size_type pos = npos) const;
+
+  StringPiece substr(size_type pos, size_type n = npos) const;
+
+  static int wordmemcmp(const char* p, const char* p2, size_type N) {
+    return memcmp(p, p2, N);
+  }
+
+  // kati specific functions will follow.
+
+  char get(size_type i) const { return i < length_ ? ptr_[i] : 0; }
+
+  StringPiece StripLeftSpaces() const;
+  StringPiece StripRightSpaces() const;
+  StringPiece StripSpaces() const;
+
+ private:
+  const char*   ptr_;
+  size_type     length_;
+};
+
+bool operator==(const StringPiece& x, const StringPiece& y);
+
+inline bool operator!=(const StringPiece& x, const StringPiece& y) {
+  return !(x == y);
+}
+
+inline bool operator<(const StringPiece& x, const StringPiece& y) {
+  const int r = StringPiece::wordmemcmp(
+      x.data(), y.data(), (x.size() < y.size() ? x.size() : y.size()));
+  return ((r < 0) || ((r == 0) && (x.size() < y.size())));
+}
+
+inline bool operator>(const StringPiece& x, const StringPiece& y) {
+  return y < x;
+}
+
+inline bool operator<=(const StringPiece& x, const StringPiece& y) {
+  return !(x > y);
+}
+
+inline bool operator>=(const StringPiece& x, const StringPiece& y) {
+  return !(x < y);
+}
+
+namespace std {
+template<> struct hash<StringPiece> {
+  size_t operator()(const StringPiece& s) const {
+    size_t result = 0;
+    for (char c : s) {
+      result = (result * 131) + c;
+    }
+    return result;
+  }
+};
+
+}
+
+#define SPF(s) static_cast<int>((s).size()), (s).data()
+
+#endif  // BASE_STRING_PIECE_H_
diff --git a/string_piece_test.cc b/string_piece_test.cc
new file mode 100644
index 0000000..8e16731
--- /dev/null
+++ b/string_piece_test.cc
@@ -0,0 +1,17 @@
+#include "string_piece.h"
+
+#include <assert.h>
+
+#include <unordered_set>
+
+using namespace std;
+
+int main() {
+  unordered_set<StringPiece> sps;
+  sps.insert(STRING_PIECE("foo"));
+  sps.insert(STRING_PIECE("foo"));
+  sps.insert(STRING_PIECE("bar"));
+  assert(sps.size() == 2);
+  assert(sps.count(STRING_PIECE("foo")) == 1);
+  assert(sps.count(STRING_PIECE("bar")) == 1);
+}
diff --git a/string_pool.cc b/string_pool.cc
new file mode 100644
index 0000000..a71a4d4
--- /dev/null
+++ b/string_pool.cc
@@ -0,0 +1,19 @@
+#include "string_pool.h"
+
+#include <stdlib.h>
+
+StringPool::StringPool() {
+}
+
+StringPool::~StringPool() {
+  for (char* b : pool_) {
+    free(b);
+  }
+}
+
+StringPiece StringPool::Add(StringPiece s) {
+  char* b = static_cast<char*>(malloc(s.size()));
+  memcpy(b, s.data(), s.size());
+  pool_.push_back(b);
+  return StringPiece(b, s.size());
+}
diff --git a/string_pool.h b/string_pool.h
new file mode 100644
index 0000000..c084b16
--- /dev/null
+++ b/string_pool.h
@@ -0,0 +1,22 @@
+#ifndef STRING_POOL_H_
+#define STRING_POOL_H_
+
+#include <string>
+#include <vector>
+
+#include "string_piece.h"
+
+using namespace std;
+
+class StringPool {
+ public:
+  StringPool();
+  ~StringPool();
+
+  StringPiece Add(StringPiece s);
+
+ private:
+  vector<char*> pool_;
+};
+
+#endif  // STRING_POOL_H_
diff --git a/stringprintf.cc b/stringprintf.cc
new file mode 100644
index 0000000..d4fe74f
--- /dev/null
+++ b/stringprintf.cc
@@ -0,0 +1,22 @@
+#include "stringprintf.h"
+
+#include <assert.h>
+#include <stdarg.h>
+
+string StringPrintf(const char* format, ...) {
+  string str;
+  str.resize(128);
+  for (int i = 0; i < 2; i++) {
+    va_list args;
+    va_start(args, format);
+    int ret = vsnprintf(&str[0], str.size(), format, args);
+    va_end(args);
+    assert(ret >= 0);
+    if (static_cast<size_t>(ret) < str.size()) {
+      str.resize(ret);
+      return str;
+    }
+    str.resize(ret + 1);
+  }
+  assert(false);
+}
diff --git a/stringprintf.h b/stringprintf.h
new file mode 100644
index 0000000..bdeaec4
--- /dev/null
+++ b/stringprintf.h
@@ -0,0 +1,10 @@
+#ifndef STRINGPRINTF_H_
+#define STRINGPRINTF_H_
+
+#include <string>
+
+using namespace std;
+
+string StringPrintf(const char* fmt, ...);
+
+#endif  // STRINGPRINTF_H_
diff --git a/strutil.cc b/strutil.cc
new file mode 100644
index 0000000..7747c01
--- /dev/null
+++ b/strutil.cc
@@ -0,0 +1,76 @@
+#include "strutil.h"
+
+#include <ctype.h>
+#include <string.h>
+
+#include <unordered_map>
+#include <utility>
+
+WordScanner::Iterator& WordScanner::Iterator::operator++() {
+  int len = static_cast<int>(in->size());
+  for (s = i; s < len; s++) {
+    if (!isspace((*in)[s]))
+      break;
+  }
+  if (s == len) {
+    in = NULL;
+    s = 0;
+    i = 0;
+    return *this;
+  }
+  for (i = s; i < len; i++) {
+    if (isspace((*in)[s]))
+      break;
+  }
+  return *this;
+}
+
+StringPiece WordScanner::Iterator::operator*() const {
+  return in->substr(s, i);
+}
+
+WordScanner::WordScanner(StringPiece in)
+    : in_(in) {
+}
+
+WordScanner::Iterator WordScanner::begin() const {
+  Iterator iter;
+  iter.in = &in_;
+  iter.s = 0;
+  iter.i = 0;
+  ++iter;
+  return iter;
+}
+
+WordScanner::Iterator WordScanner::end() const {
+  Iterator iter;
+  iter.in = NULL;
+  iter.s = 0;
+  iter.i = 0;
+  return iter;
+}
+
+static unordered_map<StringPiece, char*>* g_symtab;
+
+void InitSymtab() {
+  g_symtab = new unordered_map<StringPiece, char*>;
+}
+
+void QuitSymtab() {
+  for (auto p : *g_symtab) {
+    free(p.second);
+  }
+  delete g_symtab;
+}
+
+StringPiece Intern(StringPiece s) {
+  auto found = g_symtab->find(s);
+  if (found != g_symtab->end())
+    return found->first;
+
+  char* b = static_cast<char*>(malloc(s.size()+1));
+  memcpy(b, s.data(), s.size());
+  s = StringPiece(b, s.size());
+  (*g_symtab)[s] = b;
+  return s;
+}
diff --git a/strutil.h b/strutil.h
new file mode 100644
index 0000000..a4e5ae5
--- /dev/null
+++ b/strutil.h
@@ -0,0 +1,50 @@
+#ifndef STRUTIL_H_
+#define STRUTIL_H_
+
+#include <string>
+#include <vector>
+
+#include "string_piece.h"
+
+using namespace std;
+
+class WordScanner {
+ public:
+  struct Iterator {
+    Iterator& operator++();
+    StringPiece operator*() const;
+    bool operator!=(const Iterator& r) const {
+      return in != r.in || s != r.s || i != r.i;
+    }
+
+    const StringPiece* in;
+    int s;
+    int i;
+  };
+
+  explicit WordScanner(StringPiece in);
+
+  Iterator begin() const;
+  Iterator end() const;
+
+ private:
+  StringPiece in_;
+};
+
+void InitSymtab();
+void QuitSymtab();
+StringPiece Intern(StringPiece s);
+
+template <class String>
+inline string JoinStrings(vector<String> v, const char* sep) {
+  string r;
+  for (StringPiece s : v) {
+    if (!r.empty()) {
+      r += sep;
+    }
+    r.append(s.begin(), s.end());
+  }
+  return r;
+}
+
+#endif  // STRUTIL_H_
diff --git a/value.cc b/value.cc
new file mode 100644
index 0000000..ef84cb4
--- /dev/null
+++ b/value.cc
@@ -0,0 +1,389 @@
+#include "value.h"
+
+#include <vector>
+
+#include "eval.h"
+#include "func.h"
+#include "log.h"
+#include "stringprintf.h"
+#include "strutil.h"
+#include "var.h"
+
+Evaluable::Evaluable() {
+}
+
+Evaluable::~Evaluable() {
+}
+
+shared_ptr<string> Evaluable::Eval(Evaluator* ev) const {
+  shared_ptr<string> s = make_shared<string>();
+  Eval(ev, s.get());
+  return s;
+}
+
+Value::Value() {
+}
+
+Value::~Value() {
+}
+
+string Value::DebugString() const {
+  if (this) {
+    return DebugString_();
+  }
+  return "(null)";
+}
+
+class Literal : public Value {
+ public:
+  explicit Literal(StringPiece s)
+      : s_(s) {
+  }
+
+  StringPiece val() const { return s_; }
+
+  virtual void Eval(Evaluator*, string* s) const override {
+    s->append(s_.begin(), s_.end());
+  }
+
+  virtual string DebugString_() const override {
+    return s_.as_string();
+  }
+
+ private:
+  StringPiece s_;
+};
+
+class Expr : public Value {
+ public:
+  Expr() {
+  }
+
+  virtual ~Expr() {
+    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 {
+    for (Value* v : vals_) {
+      v->Eval(ev, s);
+    }
+  }
+
+  virtual string DebugString_() const override {
+    string r;
+    for (Value* v : vals_) {
+      if (r.empty()) {
+        r += "Expr(";
+      } else {
+        r += ", ";
+      }
+      r += v->DebugString();
+    }
+    r += ")";
+    return r;
+  }
+
+  virtual Value* Compact() {
+    if (vals_.size() != 1) {
+      return this;
+    }
+    Value* r = vals_[0];
+    vals_.clear();
+    delete this;
+    return r;
+  }
+
+ private:
+  vector<Value*> vals_;
+};
+
+class VarRef : public Value {
+ public:
+  explicit VarRef(Value* n)
+      : name_(n) {
+  }
+  virtual ~VarRef() {
+    delete name_;
+  }
+
+  virtual shared_ptr<string> Eval(Evaluator* ev) const override {
+    shared_ptr<string> name = name_->Eval(ev);
+    Var* v = ev->LookupVar(*name);
+    return v->Eval(ev);
+  }
+
+  virtual void Eval(Evaluator* ev, string* s) const override {
+    shared_ptr<string> name = name_->Eval(ev);
+    Var* v = ev->LookupVar(*name);
+    v->Eval(ev, s);
+  }
+
+  virtual string DebugString_() const override {
+    return StringPrintf("VarRef(%s)", name_->DebugString().c_str());
+  }
+
+ private:
+  Value* name_;
+};
+
+class Func : public Value {
+ public:
+  explicit Func(FuncInfo* fi)
+      : fi_(fi) {
+  }
+
+  virtual void Eval(Evaluator* ev, string* s) const override {
+    LOG("Invoke func %s(%s)", name(), JoinValues(args_, ",").c_str());
+    fi_->func(args_, ev, s);
+  }
+
+  virtual string DebugString_() const override {
+    return StringPrintf("Func(%s %s)",
+                        fi_->name,
+                        JoinValues(args_, ",").c_str());
+  }
+
+  void AddArg(Value* v) {
+    args_.push_back(v);
+  }
+
+  const char* name() const { return fi_->name; }
+  int arity() const { return fi_->arity; }
+
+ private:
+  FuncInfo* fi_;
+  vector<Value*> args_;
+};
+
+static char CloseParen(char c) {
+  switch (c) {
+    case '(':
+      return ')';
+    case '{':
+      return '}';
+  }
+  return 0;
+}
+
+static size_t SkipSpaces(StringPiece s, const char* terms) {
+  for (size_t i = 0; i < s.size(); i++) {
+    char c = s[i];
+    if ((c != ' ' && c != '\t') || strchr(terms, c))
+      return i;
+  }
+  return s.size();
+}
+
+static Value* ParseExprImpl(StringPiece s, const char* terms, bool is_command,
+                            size_t* index_out);
+
+Value* ParseFunc(Func* f, StringPiece s, size_t i, char* terms,
+                 size_t* index_out) {
+  terms[1] = ',';
+  terms[2] = '\0';
+  i += SkipSpaces(s.substr(i), terms);
+  if (i == s.size()) {
+    *index_out = i;
+    return f;
+  }
+
+  int nargs = 1;
+  while (true) {
+    if (f->arity() && nargs >= f->arity()) {
+      terms[1] = '\0';  // Drop ','.
+    }
+
+    size_t n;
+    Value* v = ParseExprImpl(s.substr(i), terms, false, &n);
+    // TODO: concatLine???
+    // TODO: trimLiteralSpace for conditional functions.
+    f->AddArg(v);
+    i += n;
+    nargs++;
+    if (s[i] == terms[0]) {
+      i++;
+      break;
+    }
+    i++;  // Should be ','.
+    if (i == s.size())
+      break;
+  }
+
+  *index_out = i;
+  return f;
+}
+
+Value* ParseDollar(StringPiece s, size_t* index_out) {
+  CHECK(s.size() >= 2);
+  CHECK(s[0] == '$');
+  CHECK(s[1] != '$');
+
+  char cp = CloseParen(s[1]);
+  if (cp == 0) {
+    *index_out = 2;
+    return new VarRef(new Literal(s.substr(1, 1)));
+  }
+
+  char terms[] = {cp, ':', ' ', 0};
+  for (size_t i = 2;;) {
+    size_t n;
+    Value* vname = ParseExprImpl(s.substr(i), terms, false, &n);
+    i += n;
+    if (s[i] == cp) {
+      *index_out = i + 1;
+      return new VarRef(vname);
+    }
+
+    if (s[i] == ' ') {
+      // ${func ...}
+      if (Literal* lit = reinterpret_cast<Literal*>(vname)) {
+        if (FuncInfo* fi = GetFuncInfo(lit->val())) {
+          Func* func = new Func(fi);
+          return ParseFunc(func, s, i+1, terms, index_out);
+        }
+      }
+
+      // Not a function. Drop ' ' from |terms| and parse it
+      // again. This is inefficient, but this code path should be
+      // rarely used.
+      delete vname;
+      terms[2] = 0;
+      i = 2;
+      continue;
+    }
+
+    if (s[i] == ':') {
+      // Implement substr ref.
+      CHECK(false);
+    }
+
+    CHECK(false);
+  }
+}
+
+static Value* ParseExprImpl(StringPiece s, const char* terms, bool is_command,
+                            size_t* index_out) {
+  // TODO: A faulty optimization.
+#if 0
+  char specials[] = "$(){}\\\n";
+  size_t found = s.find_first_of(specials);
+  if (found == string::npos) {
+    *index_out = s.size();
+    return new Literal(s);
+  }
+  if (terms && strchr(terms, s[found])) {
+    *index_out = found;
+    return new Literal(s.substr(0, found));
+  }
+#endif
+
+  Expr* r = new Expr;
+  size_t b = 0;
+  char save_paren = 0;
+  int paren_depth = 0;
+  size_t i;
+  for (i = 0; i < s.size(); i++) {
+    char c = s[i];
+    if (terms && strchr(terms, c)) {
+      break;
+    }
+
+    // Handle a comment.
+    if (!terms && c == '#' && !is_command) {
+      if (i > b)
+        r->AddValue(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();
+    }
+
+    if (c == '$') {
+      if (i + 1 >= s.size()) {
+        break;
+      }
+
+      if (i > b)
+        r->AddValue(new Literal(s.substr(b, i-b)));
+
+      if (s[i+1] == '$') {
+        r->AddValue(new Literal(STRING_PIECE("$")));
+        i += 2;
+        b = i;
+        continue;
+      }
+
+      if (terms && strchr(terms, s[i+1])) {
+        *index_out = i + 1;
+        return r->Compact();
+      }
+
+      size_t n;
+      Value* v = ParseDollar(s.substr(i), &n);
+      i += n;
+      b = i;
+      i--;
+      r->AddValue(v);
+      continue;
+    }
+
+    if (c == '(' || c == '{') {
+      char cp = CloseParen(c);
+      if (terms && terms[0] == cp) {
+        paren_depth++;
+        save_paren = cp;
+        terms++;
+      } else if (cp == save_paren) {
+        paren_depth++;
+      }
+      continue;
+    }
+
+    if (c == save_paren) {
+      paren_depth--;
+      if (paren_depth == 0) {
+        terms--;
+        save_paren = 0;
+      }
+    }
+
+    if (c == '\\' && i + 1 < s.size() && !is_command) {
+      char n = s[i+1];
+      if (n == '\\') {
+        i++;
+        continue;
+      }
+      if (n == '\r' || n == '\n') {
+        // TODO
+        CHECK(false);
+      }
+    }
+  }
+
+  if (i > b)
+    r->AddValue(new Literal(s.substr(b, i-b)));
+  *index_out = i;
+  return r->Compact();
+}
+
+Value* ParseExpr(StringPiece s, bool is_command) {
+  size_t n;
+  return ParseExprImpl(s, NULL, is_command, &n);
+}
+
+string JoinValues(const vector<Value*> vals, const char* sep) {
+  vector<string> val_strs;
+  for (Value* v : vals) {
+    val_strs.push_back(v->DebugString());
+  }
+  return JoinStrings(val_strs, sep);
+}
diff --git a/value.h b/value.h
new file mode 100644
index 0000000..0236b42
--- /dev/null
+++ b/value.h
@@ -0,0 +1,41 @@
+#ifndef VALUE_H_
+#define VALUE_H_
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "string_piece.h"
+
+using namespace std;
+
+class Evaluator;
+
+class Evaluable {
+ public:
+  virtual void Eval(Evaluator* ev, string* s) const = 0;
+  virtual shared_ptr<string> Eval(Evaluator*) const;
+
+ protected:
+  Evaluable();
+  virtual ~Evaluable();
+};
+
+class Value : public Evaluable {
+ public:
+  virtual ~Value();
+
+  virtual Value* Compact() { return this; }
+
+  string DebugString() const;
+
+ protected:
+  Value();
+  virtual string DebugString_() const = 0;
+};
+
+Value* ParseExpr(StringPiece s, bool is_command);
+
+string JoinValues(const vector<Value*> vals, const char* sep);
+
+#endif  // VALUE_H_
diff --git a/var.cc b/var.cc
new file mode 100644
index 0000000..9bac8a2
--- /dev/null
+++ b/var.cc
@@ -0,0 +1,68 @@
+#include "var.h"
+
+#include "value.h"
+
+UndefinedVar kUndefinedBuf;
+UndefinedVar* kUndefined = &kUndefinedBuf;
+
+Var::Var() {
+}
+
+Var::~Var() {
+}
+
+SimpleVar::SimpleVar(shared_ptr<string> v, const char* origin)
+    : v_(v), origin_(origin) {
+}
+
+void SimpleVar::Eval(Evaluator*, string* s) const {
+  *s += *v_;
+}
+
+string SimpleVar::DebugString() const {
+  return *v_;
+}
+
+RecursiveVar::RecursiveVar(Value* v, const char* origin)
+    : v_(v), origin_(origin) {
+}
+
+void RecursiveVar::Eval(Evaluator* ev, string* s) const {
+  v_->Eval(ev, s);
+}
+
+string RecursiveVar::DebugString() const {
+  return v_->DebugString();
+}
+
+UndefinedVar::UndefinedVar() {}
+
+void UndefinedVar::Eval(Evaluator*, string*) const {
+  // Nothing to do.
+}
+
+string UndefinedVar::DebugString() const {
+  return "*undefined*";
+}
+
+Vars::~Vars() {
+  for (auto p : *this) {
+    delete p.second;
+  }
+}
+
+Var* Vars::Lookup(StringPiece name) const {
+  auto found = find(name);
+  if (found == end())
+    return kUndefined;
+  return found->second;
+}
+
+void Vars::Assign(StringPiece name, Var* v) {
+  auto p = insert(make_pair(name, v));
+  if (!p.second) {
+    if (p.first->second->IsDefined())
+      delete p.first->second;
+    p.first->second = v;
+  }
+}
diff --git a/var.h b/var.h
new file mode 100644
index 0000000..bb7ab31
--- /dev/null
+++ b/var.h
@@ -0,0 +1,101 @@
+#ifndef VAR_H_
+#define VAR_H_
+
+#include <memory>
+#include <string>
+#include <unordered_map>
+
+#include "string_piece.h"
+#include "value.h"
+
+using namespace std;
+
+class Evaluator;
+class Value;
+
+class Var : public Evaluable {
+ public:
+  virtual ~Var();
+
+  virtual const char* Flavor() const = 0;
+  virtual const char* Origin() const = 0;
+  virtual bool IsDefined() const { return true; }
+
+  virtual string DebugString() const = 0;
+
+ protected:
+  Var();
+};
+
+class SimpleVar : public Var {
+ public:
+  SimpleVar(shared_ptr<string> v, const char* origin);
+
+  virtual const char* Flavor() const {
+    return "simple";
+  }
+  virtual const char* Origin() const {
+    return origin_;
+  }
+
+  virtual shared_ptr<string> Eval(Evaluator*) const override {
+    return v_;
+  }
+  virtual void Eval(Evaluator* ev, string* s) const override;
+
+  string DebugString() const override;
+
+ private:
+  shared_ptr<string> v_;
+  const char* origin_;
+};
+
+class RecursiveVar : public Var {
+ public:
+  RecursiveVar(Value* v, const char* origin);
+
+  virtual const char* Flavor() const {
+    return "recursive";
+  }
+  virtual const char* Origin() const {
+    return origin_;
+  }
+
+  virtual void Eval(Evaluator* ev, string* s) const override;
+
+  string DebugString() const override;
+
+ private:
+  Value* v_;
+  const char* origin_;
+};
+
+class UndefinedVar : public Var {
+ public:
+  UndefinedVar();
+
+  virtual const char* Flavor() const {
+    return "undefined";
+  }
+  virtual const char* Origin() const {
+    return "undefined";
+  }
+  virtual bool IsDefined() const { return false; }
+
+  virtual void Eval(Evaluator* ev, string* s) const override;
+
+  string DebugString() const override;
+};
+
+extern UndefinedVar* kUndefined;
+
+class Vars : public unordered_map<StringPiece, Var*> {
+ public:
+  ~Vars();
+
+  Var* Lookup(StringPiece name) const;
+
+  void Assign(StringPiece name, Var* v);
+};
+
+#endif  // VAR_H_