Split exec.go into exec.go and eval_command.go
diff --git a/eval_command.go b/eval_command.go
new file mode 100644
index 0000000..d504bb4
--- /dev/null
+++ b/eval_command.go
@@ -0,0 +1,596 @@
+package main
+
+import (
+	"bytes"
+	"fmt"
+	"io"
+	"path/filepath"
+	"strings"
+)
+
+type Runner struct {
+	cmd         string
+	echo        bool
+	ignoreError bool
+	shell       string
+}
+
+type DepNode struct {
+	Output      string
+	Runners     []Runner
+	Deps        []*DepNode
+	HasRule     bool
+	IsOrderOnly bool
+}
+
+func (n *DepNode) String() string {
+	return fmt.Sprintf("Dep{output=%s runners=%d deps=%d hasRule=%t orderOnly=%t}",
+		n.Output, len(n.Runners), len(n.Deps), n.HasRule, n.IsOrderOnly)
+}
+
+type CommandEvaluator struct {
+	rules         map[string]*Rule
+	ruleVars      map[string]Vars
+	implicitRules []*Rule
+	suffixRules   map[string][]*Rule
+	firstRule     *Rule
+	shell         string
+	vars          Vars
+	done          map[string]*DepNode
+
+	currentOutput string
+	currentInputs []string
+	currentStem   string
+
+	trace                         []string
+	nodeCnt                       int
+	pickExplicitRuleCnt           int
+	pickImplicitRuleCnt           int
+	pickSuffixRuleCnt             int
+	pickExplicitRuleWithoutCmdCnt int
+}
+
+type AutoVar struct{ ce *CommandEvaluator }
+
+func (v AutoVar) Flavor() string  { return "undefined" }
+func (v AutoVar) Origin() string  { return "automatic" }
+func (v AutoVar) IsDefined() bool { panic("not implemented") }
+func (v AutoVar) String() string  { panic("not implemented") }
+func (v AutoVar) Append(*Evaluator, string) Var {
+	panic("must not be called")
+}
+func (v AutoVar) AppendVar(*Evaluator, Var) Var {
+	panic("must not be called")
+}
+
+type AutoAtVar struct{ AutoVar }
+
+func (v AutoAtVar) Eval(w io.Writer, ev *Evaluator) {
+	fmt.Fprint(w, v.ce.currentOutput)
+}
+
+type AutoLessVar struct{ AutoVar }
+
+func (v AutoLessVar) Eval(w io.Writer, ev *Evaluator) {
+	if len(v.ce.currentInputs) > 0 {
+		fmt.Fprint(w, v.ce.currentInputs[0])
+	}
+}
+
+type AutoHatVar struct{ AutoVar }
+
+func (v AutoHatVar) Eval(w io.Writer, ev *Evaluator) {
+	var uniqueInputs []string
+	seen := make(map[string]bool)
+	for _, input := range v.ce.currentInputs {
+		if !seen[input] {
+			seen[input] = true
+			uniqueInputs = append(uniqueInputs, input)
+		}
+	}
+	fmt.Fprint(w, strings.Join(uniqueInputs, " "))
+}
+
+type AutoPlusVar struct{ AutoVar }
+
+func (v AutoPlusVar) Eval(w io.Writer, ev *Evaluator) {
+	fmt.Fprint(w, strings.Join(v.ce.currentInputs, " "))
+}
+
+type AutoStarVar struct{ AutoVar }
+
+func (v AutoStarVar) Eval(w io.Writer, ev *Evaluator) {
+	// TODO: Use currentStem. See auto_stem_var.mk
+	fmt.Fprint(w, stripExt(v.ce.currentOutput))
+}
+
+type AutoSuffixDVar struct {
+	AutoVar
+	v Var
+}
+
+func (v AutoSuffixDVar) Eval(w io.Writer, ev *Evaluator) {
+	var buf bytes.Buffer
+	v.v.Eval(&buf, ev)
+	for i, tok := range splitSpaces(buf.String()) {
+		if i > 0 {
+			w.Write([]byte{' '})
+		}
+		fmt.Fprint(w, filepath.Dir(tok))
+	}
+}
+
+type AutoSuffixFVar struct {
+	AutoVar
+	v Var
+}
+
+func (v AutoSuffixFVar) Eval(w io.Writer, ev *Evaluator) {
+	var buf bytes.Buffer
+	v.v.Eval(&buf, ev)
+	for i, tok := range splitSpaces(buf.String()) {
+		if i > 0 {
+			w.Write([]byte{' '})
+		}
+		fmt.Fprint(w, filepath.Base(tok))
+	}
+}
+
+func replaceSuffix(s string, newsuf string) string {
+	// TODO: Factor out the logic around suffix rules and use
+	// it from substitution references.
+	// http://www.gnu.org/software/make/manual/make.html#Substitution-Refs
+	return fmt.Sprintf("%s.%s", stripExt(s), newsuf)
+}
+
+func (ce *CommandEvaluator) exists(target string) bool {
+	_, present := ce.rules[target]
+	if present {
+		return true
+	}
+	rule, present := ce.rules[".PHONY"]
+	if present {
+		for _, input := range rule.inputs {
+			if target == input {
+				return true
+			}
+		}
+	}
+	return exists(target)
+}
+
+func (ce *CommandEvaluator) canPickImplicitRule(rule *Rule, output string) bool {
+	outputPattern := rule.outputPatterns[0]
+	if !matchPattern(outputPattern, output) {
+		return false
+	}
+	for _, input := range rule.inputs {
+		input = substPattern(outputPattern, input, output)
+		if !ce.exists(input) {
+			return false
+		}
+	}
+	return true
+}
+
+func (ce *CommandEvaluator) mergeImplicitRuleVars(outputs []string, vars Vars) Vars {
+	if len(outputs) != 1 {
+		panic(fmt.Sprintf("Implicit rule should have only one output but %q", outputs))
+	}
+	Log("merge? %q", ce.ruleVars)
+	Log("merge? %q", outputs[0])
+	ivars, present := ce.ruleVars[outputs[0]]
+	if !present {
+		return vars
+	}
+	if vars == nil {
+		return ivars
+	}
+	Log("merge!")
+	v := make(Vars)
+	v.Merge(ivars)
+	v.Merge(vars)
+	return v
+}
+
+func (ce *CommandEvaluator) pickRule(output string) (*Rule, Vars, bool) {
+	rule, present := ce.rules[output]
+	vars := ce.ruleVars[output]
+	if present {
+		ce.pickExplicitRuleCnt++
+		if len(rule.cmds) > 0 {
+			return rule, vars, true
+		}
+		// If none of the explicit rules for a target has commands,
+		// then `make' searches for an applicable implicit rule to
+		// find some commands.
+		ce.pickExplicitRuleWithoutCmdCnt++
+	}
+
+	for _, irule := range ce.implicitRules {
+		if !ce.canPickImplicitRule(irule, output) {
+			continue
+		}
+		ce.pickImplicitRuleCnt++
+		if rule != nil {
+			r := &Rule{}
+			*r = *rule
+			r.outputPatterns = irule.outputPatterns
+			// implicit rule's prerequisites will be used for $<
+			r.inputs = append(irule.inputs, r.inputs...)
+			r.cmds = irule.cmds
+			// TODO(ukai): filename, lineno?
+			r.cmdLineno = irule.cmdLineno
+			return r, vars, true
+		}
+		if vars != nil {
+			vars = ce.mergeImplicitRuleVars(irule.outputPatterns, vars)
+		}
+		// TODO(ukai): check len(irule.cmd) ?
+		return irule, vars, true
+	}
+
+	outputSuffix := filepath.Ext(output)
+	if !strings.HasPrefix(outputSuffix, ".") {
+		return rule, vars, rule != nil
+	}
+	rules, present := ce.suffixRules[outputSuffix[1:]]
+	if !present {
+		return rule, vars, rule != nil
+	}
+	for _, irule := range rules {
+		if len(irule.inputs) != 1 {
+			panic(fmt.Sprintf("unexpected number of input for a suffix rule (%d)", len(irule.inputs)))
+		}
+		if !ce.exists(replaceSuffix(output, irule.inputs[0])) {
+			continue
+		}
+		ce.pickSuffixRuleCnt++
+		if rule != nil {
+			r := &Rule{}
+			*r = *rule
+			// TODO(ukai): input order is correct?
+			r.inputs = append([]string{replaceSuffix(output, irule.inputs[0])}, r.inputs...)
+			r.cmds = irule.cmds
+			// TODO(ukai): filename, lineno?
+			r.cmdLineno = irule.cmdLineno
+			return r, vars, true
+		}
+		if vars != nil {
+			vars = ce.mergeImplicitRuleVars(irule.outputs, vars)
+		}
+		// TODO(ukai): check len(irule.cmd) ?
+		return irule, vars, true
+	}
+	return rule, vars, rule != nil
+}
+
+func newRunner(r Runner, s string) Runner {
+	for {
+		s = trimLeftSpace(s)
+		if s == "" {
+			return Runner{}
+		}
+		switch s[0] {
+		case '@':
+			r.echo = false
+			s = s[1:]
+			continue
+		case '-':
+			r.ignoreError = true
+			s = s[1:]
+			continue
+		}
+		break
+	}
+	r.cmd = s
+	return r
+}
+
+func evalCmd(ev *Evaluator, r Runner, s string) []Runner {
+	r = newRunner(r, s)
+	if strings.IndexByte(r.cmd, '$') < 0 {
+		// fast path
+		return []Runner{r}
+	}
+	cmds := ev.evalExpr(r.cmd)
+	var runners []Runner
+	for _, cmd := range strings.Split(cmds, "\n") {
+		if len(runners) > 0 && strings.HasSuffix(runners[0].cmd, "\\") {
+			runners[0].cmd += "\n"
+			runners[0].cmd += cmd
+		} else {
+			runners = append(runners, newRunner(r, cmd))
+		}
+	}
+	return runners
+}
+
+func (ce *CommandEvaluator) buildPlan(output string, neededBy string) (*DepNode, error) {
+	Log("Evaluating command: %s", output)
+	ce.nodeCnt++
+	if ce.nodeCnt%100 == 0 {
+		ce.reportStats()
+	}
+
+	if n, present := ce.done[output]; present {
+		return n, nil
+	}
+	n := &DepNode{Output: output}
+	ce.done[output] = n
+
+	rule, vars, present := ce.pickRule(output)
+	if !present {
+		return n, nil
+	}
+
+	var restores []func()
+	if vars != nil {
+		for name, v := range vars {
+			tsv := v.(TargetSpecificVar)
+			restores = append(restores, ce.vars.save(name))
+			switch tsv.op {
+			case ":=", "=":
+				ce.vars[name] = tsv
+			case "+=":
+				oldVar, present := ce.vars[name]
+				if !present || oldVar.String() == "" {
+					ce.vars[name] = tsv
+				} else {
+					ce.vars[name] = oldVar.AppendVar(newEvaluator(ce.vars), tsv)
+				}
+			case "?=":
+				if _, present := ce.vars[name]; !present {
+					ce.vars[name] = tsv
+				}
+			}
+		}
+		defer func() {
+			for _, restore := range restores {
+				restore()
+			}
+		}()
+	}
+
+	var children []*DepNode
+	var actualInputs []string
+	Log("Evaluating command: %s inputs:%q", output, rule.inputs)
+	for _, input := range rule.inputs {
+		if len(rule.outputPatterns) > 0 {
+			if len(rule.outputPatterns) > 1 {
+				panic("TODO: multiple output pattern is not supported yet")
+			}
+			input = substPattern(rule.outputPatterns[0], input, output)
+		} else if rule.isSuffixRule {
+			input = replaceSuffix(output, input)
+		}
+		actualInputs = append(actualInputs, input)
+
+		ce.trace = append(ce.trace, input)
+		n, err := ce.buildPlan(input, output)
+		ce.trace = ce.trace[0 : len(ce.trace)-1]
+		if err != nil {
+			return nil, err
+		}
+		if n != nil {
+			children = append(children, n)
+		}
+	}
+
+	for _, input := range rule.orderOnlyInputs {
+		ce.trace = append(ce.trace, input)
+		n, err := ce.buildPlan(input, output)
+		ce.trace = ce.trace[0 : len(ce.trace)-1]
+		if err != nil {
+			return nil, err
+		}
+		if n != nil {
+			n.IsOrderOnly = true
+			children = append(children, n)
+		}
+	}
+
+	// For automatic variables.
+	ce.currentOutput = output
+	ce.currentInputs = actualInputs
+
+	ev := newEvaluator(ce.vars)
+	ev.filename = rule.filename
+	ev.lineno = rule.cmdLineno
+	var runners []Runner
+	Log("Evaluating command: %s cmds:%q", output, rule.cmds)
+	r := Runner{
+		echo:  true,
+		shell: ce.shell,
+	}
+	for _, cmd := range rule.cmds {
+		for _, r := range evalCmd(ev, r, cmd) {
+			if len(r.cmd) != 0 {
+				runners = append(runners, r)
+			}
+		}
+	}
+
+	n.Runners = runners
+	n.Deps = children
+	n.HasRule = true
+	return n, nil
+}
+
+func (ce *CommandEvaluator) populateSuffixRule(rule *Rule, output string) bool {
+	if len(output) == 0 || output[0] != '.' {
+		return false
+	}
+	rest := output[1:]
+	dotIndex := strings.IndexByte(rest, '.')
+	// If there is only a single dot or the third dot, this is not a
+	// suffix rule.
+	if dotIndex < 0 || strings.IndexByte(rest[dotIndex+1:], '.') >= 0 {
+		return false
+	}
+
+	// This is a suffix rule.
+	inputSuffix := rest[:dotIndex]
+	outputSuffix := rest[dotIndex+1:]
+	r := &Rule{}
+	*r = *rule
+	r.inputs = []string{inputSuffix}
+	r.isSuffixRule = true
+	ce.suffixRules[outputSuffix] = append([]*Rule{r}, ce.suffixRules[outputSuffix]...)
+	return true
+}
+
+func mergeRules(oldRule, rule *Rule, output string, isSuffixRule bool) *Rule {
+	if oldRule.isDoubleColon != rule.isDoubleColon {
+		Error(rule.filename, rule.lineno, "*** target file %q has both : and :: entries.", output)
+	}
+	if len(oldRule.cmds) > 0 && len(rule.cmds) > 0 && !isSuffixRule && !rule.isDoubleColon {
+		Warn(rule.filename, rule.cmdLineno, "overriding commands for target %q", output)
+		Warn(oldRule.filename, oldRule.cmdLineno, "ignoring old commands for target %q", output)
+	}
+
+	r := &Rule{}
+	*r = *rule
+	if rule.isDoubleColon {
+		r.cmds = append(oldRule.cmds, r.cmds...)
+	} else if len(oldRule.cmds) > 0 && len(rule.cmds) == 0 {
+		r.cmds = oldRule.cmds
+	}
+	// If the latter rule has a command (regardless of the
+	// commands in oldRule), inputs in the latter rule has a
+	// priority.
+	if len(rule.cmds) > 0 {
+		r.inputs = append(r.inputs, oldRule.inputs...)
+		r.orderOnlyInputs = append(r.orderOnlyInputs, oldRule.orderOnlyInputs...)
+	} else {
+		r.inputs = append(oldRule.inputs, r.inputs...)
+		r.orderOnlyInputs = append(oldRule.orderOnlyInputs, r.orderOnlyInputs...)
+	}
+	r.outputPatterns = append(r.outputPatterns, oldRule.outputPatterns...)
+	return r
+}
+
+func (ce *CommandEvaluator) populateExplicitRule(rule *Rule) {
+	// It seems rules with no outputs are siliently ignored.
+	if len(rule.outputs) == 0 {
+		return
+	}
+	for _, output := range rule.outputs {
+		output = filepath.Clean(output)
+
+		isSuffixRule := ce.populateSuffixRule(rule, output)
+
+		if oldRule, present := ce.rules[output]; present {
+			r := mergeRules(oldRule, rule, output, isSuffixRule)
+			ce.rules[output] = r
+		} else {
+			ce.rules[output] = rule
+			if ce.firstRule == nil && !strings.HasPrefix(output, ".") {
+				ce.firstRule = rule
+			}
+		}
+	}
+}
+
+func (ce *CommandEvaluator) populateImplicitRule(rule *Rule) {
+	for _, outputPattern := range rule.outputPatterns {
+		r := &Rule{}
+		*r = *rule
+		r.outputPatterns = []string{outputPattern}
+		ce.implicitRules = append(ce.implicitRules, r)
+	}
+}
+
+func (ce *CommandEvaluator) populateRules(er *EvalResult) {
+	for _, rule := range er.rules {
+		for i, input := range rule.inputs {
+			rule.inputs[i] = filepath.Clean(input)
+		}
+		for i, orderOnlyInput := range rule.orderOnlyInputs {
+			rule.orderOnlyInputs[i] = filepath.Clean(orderOnlyInput)
+		}
+		ce.populateExplicitRule(rule)
+
+		if len(rule.outputs) == 0 {
+			ce.populateImplicitRule(rule)
+		}
+	}
+
+	// Reverse the implicit rule for easier lookup.
+	for i, r := range ce.implicitRules {
+		if i >= len(ce.implicitRules)/2 {
+			break
+		}
+		j := len(ce.implicitRules) - i - 1
+		ce.implicitRules[i] = ce.implicitRules[j]
+		ce.implicitRules[j] = r
+	}
+}
+
+func (ce *CommandEvaluator) reportStats() {
+	if !katiLogFlag && !katiStatsFlag {
+		return
+	}
+
+	LogStats("node=%d explicit=%d implicit=%d suffix=%d explicitWOCmd=%d",
+		ce.nodeCnt, ce.pickExplicitRuleCnt, ce.pickImplicitRuleCnt, ce.pickSuffixRuleCnt, ce.pickExplicitRuleWithoutCmdCnt)
+	if len(ce.trace) > 1 {
+		LogStats("trace=%q", ce.trace)
+	}
+}
+
+func NewCommandEvaluator(er *EvalResult, vars Vars) *CommandEvaluator {
+	ce := &CommandEvaluator{
+		rules:       make(map[string]*Rule),
+		ruleVars:    er.ruleVars,
+		suffixRules: make(map[string][]*Rule),
+		vars:        vars,
+		done:        make(map[string]*DepNode),
+	}
+
+	for k, v := range map[string]Var{
+		"@": AutoAtVar{AutoVar: AutoVar{ce: ce}},
+		"<": AutoLessVar{AutoVar: AutoVar{ce: ce}},
+		"^": AutoHatVar{AutoVar: AutoVar{ce: ce}},
+		"+": AutoPlusVar{AutoVar: AutoVar{ce: ce}},
+		"*": AutoStarVar{AutoVar: AutoVar{ce: ce}},
+	} {
+		ce.vars[k] = v
+		ce.vars[k+"D"] = AutoSuffixDVar{v: v}
+		ce.vars[k+"F"] = AutoSuffixFVar{v: v}
+	}
+
+	// TODO: We should move this to somewhere around evalCmd so that
+	// we can handle SHELL in target specific variables.
+	shellVar := ce.vars.Lookup("SHELL")
+	ce.shell = shellVar.String()
+
+	ce.populateRules(er)
+	return ce
+}
+
+func (ce *CommandEvaluator) Eval(targets []string) ([]*DepNode, error) {
+	if len(targets) == 0 {
+		if ce.firstRule == nil {
+			ErrorNoLocation("*** No targets.")
+		}
+		targets = append(targets, ce.firstRule.outputs[0])
+	}
+
+	LogStats("%d variables", len(ce.vars))
+	LogStats("%d explicit rules", len(ce.rules))
+	LogStats("%d implicit rules", len(ce.implicitRules))
+	LogStats("%d suffix rules", len(ce.suffixRules))
+
+	var nodes []*DepNode
+	for _, target := range targets {
+		ce.trace = []string{target}
+		n, err := ce.buildPlan(target, "")
+		if err != nil {
+			return nil, err
+		}
+		nodes = append(nodes, n)
+	}
+	ce.reportStats()
+	return nodes, nil
+}
diff --git a/exec.go b/exec.go
index 6048224..7bc8610 100644
--- a/exec.go
+++ b/exec.go
@@ -1,13 +1,9 @@
 package main
 
 import (
-	"bytes"
 	"fmt"
-	"io"
 	"os"
 	"os/exec"
-	"path/filepath"
-	"strings"
 	"syscall"
 	"time"
 )
@@ -24,22 +20,15 @@
 	// currently being processed.
 	done map[string]int64
 
-	currentOutput string
-	currentInputs []string
-	currentStem   string
-
-	trace                         []string
-	buildCnt                      int
-	alreadyDoneCnt                int
-	noRuleCnt                     int
-	upToDateCnt                   int
-	runCommandCnt                 int
-	pickExplicitRuleCnt           int
-	pickImplicitRuleCnt           int
-	pickSuffixRuleCnt             int
-	pickExplicitRuleWithoutCmdCnt int
+	trace          []string
+	buildCnt       int
+	alreadyDoneCnt int
+	noRuleCnt      int
+	upToDateCnt    int
+	runCommandCnt  int
 }
 
+/*
 type AutoVar struct{ ex *Executor }
 
 func (v AutoVar) Flavor() string  { return "undefined" }
@@ -149,6 +138,7 @@
 
 	return ex
 }
+*/
 
 // TODO(ukai): use time.Time?
 func getTimestamp(filename string) int64 {
@@ -159,22 +149,7 @@
 	return st.ModTime().Unix()
 }
 
-func (ex *Executor) exists(target string) bool {
-	_, present := ex.rules[target]
-	if present {
-		return true
-	}
-	rule, present := ex.rules[".PHONY"]
-	if present {
-		for _, input := range rule.inputs {
-			if target == input {
-				return true
-			}
-		}
-	}
-	return exists(target)
-}
-
+/*
 type runner struct {
 	output      string
 	cmd         string
@@ -226,12 +201,13 @@
 	r.cmd = s
 	return r
 }
+*/
 
-func (r runner) run() error {
-	if r.echo {
+func (r Runner) run(output string) error {
+	if r.echo || dryRunFlag {
 		fmt.Printf("%s\n", r.cmd)
 	}
-	if r.dryRun {
+	if dryRunFlag {
 		return nil
 	}
 	args := []string{r.shell, "-c", r.cmd}
@@ -243,7 +219,7 @@
 	fmt.Printf("%s", out)
 	exit := exitStatus(err)
 	if r.ignoreError && exit != 0 {
-		fmt.Printf("[%s] Error %d (ignored)\n", r.output, exit)
+		fmt.Printf("[%s] Error %d (ignored)\n", output, exit)
 		err = nil
 	}
 	return err
@@ -262,6 +238,7 @@
 	return exit
 }
 
+/*
 func replaceSuffix(s string, newsuf string) string {
 	// TODO: Factor out the logic around suffix rules and use
 	// it from substitution references.
@@ -374,8 +351,10 @@
 	}
 	return rule, vars, rule != nil
 }
+*/
 
-func (ex *Executor) build(output string, neededBy string) (int64, error) {
+func (ex *Executor) build(n *DepNode, neededBy string) (int64, error) {
+	output := n.Output
 	Log("Building: %s", output)
 	ex.buildCnt++
 	if ex.buildCnt%100 == 0 {
@@ -394,8 +373,7 @@
 	ex.done[output] = -1
 	outputTs = getTimestamp(output)
 
-	rule, vars, present := ex.pickRule(output)
-	if !present {
+	if !n.HasRule {
 		if outputTs >= 0 {
 			ex.done[output] = outputTs
 			ex.noRuleCnt++
@@ -409,66 +387,15 @@
 		return outputTs, fmt.Errorf("no rule to make target %q", output)
 	}
 
-	var restores []func()
-	if vars != nil {
-		for name, v := range vars {
-			tsv := v.(TargetSpecificVar)
-			restores = append(restores, ex.vars.save(name))
-			switch tsv.op {
-			case ":=", "=":
-				ex.vars[name] = tsv
-			case "+=":
-				oldVar, present := ex.vars[name]
-				if !present || oldVar.String() == "" {
-					ex.vars[name] = tsv
-				} else {
-					ex.vars[name] = oldVar.AppendVar(newEvaluator(ex.vars), tsv)
-				}
-			case "?=":
-				if _, present := ex.vars[name]; !present {
-					ex.vars[name] = tsv
-				}
-			}
-		}
-		defer func() {
-			for _, restore := range restores {
-				restore()
-			}
-		}()
-	}
-
 	latest := int64(-1)
-	var actualInputs []string
-	Log("Building: %s inputs:%q", output, rule.inputs)
-	for _, input := range rule.inputs {
-		if len(rule.outputPatterns) > 0 {
-			if len(rule.outputPatterns) > 1 {
-				panic("TODO: multiple output pattern is not supported yet")
-			}
-			input = substPattern(rule.outputPatterns[0], input, output)
-		} else if rule.isSuffixRule {
-			input = replaceSuffix(output, input)
-		}
-		actualInputs = append(actualInputs, input)
-
-		ex.trace = append(ex.trace, input)
-		ts, err := ex.build(input, output)
-		ex.trace = ex.trace[0 : len(ex.trace)-1]
-		if err != nil {
-			return outputTs, err
-		}
-		if latest < ts {
-			latest = ts
-		}
-	}
-
-	for _, input := range rule.orderOnlyInputs {
-		if exists(input) {
+	Log("Building: %s inputs:%q", output, n.Deps)
+	for _, d := range n.Deps {
+		if d.IsOrderOnly && exists(d.Output) {
 			continue
 		}
 
-		ex.trace = append(ex.trace, input)
-		ts, err := ex.build(input, output)
+		ex.trace = append(ex.trace, d.Output)
+		ts, err := ex.build(d, output)
 		ex.trace = ex.trace[0 : len(ex.trace)-1]
 		if err != nil {
 			return outputTs, err
@@ -484,33 +411,11 @@
 		return outputTs, nil
 	}
 
-	// For automatic variables.
-	ex.currentOutput = output
-	ex.currentInputs = actualInputs
-
-	ev := newEvaluator(ex.vars)
-	ev.filename = rule.filename
-	ev.lineno = rule.cmdLineno
-	var runners []runner
-	Log("Building: %s cmds:%q", output, rule.cmds)
-	r := runner{
-		output: output,
-		echo:   true,
-		dryRun: dryRunFlag,
-		shell:  ex.shell,
-	}
-	for _, cmd := range rule.cmds {
-		for _, r := range evalCmd(ev, r, cmd) {
-			if len(r.cmd) != 0 {
-				runners = append(runners, r)
-			}
-		}
-	}
-	for _, r := range runners {
-		err := r.run()
+	for _, r := range n.Runners {
+		err := r.run(output)
 		if err != nil {
 			exit := exitStatus(err)
-			fmt.Printf("[%s] Error %d: %v\n", r.output, exit, err)
+			fmt.Printf("[%s] Error %d: %v\n", output, exit, err)
 			return outputTs, err
 		}
 	}
@@ -525,6 +430,7 @@
 	return outputTs, nil
 }
 
+/*
 func (ex *Executor) populateSuffixRule(rule *Rule, output string) bool {
 	if len(output) == 0 || output[0] != '.' {
 		return false
@@ -634,6 +540,7 @@
 		ex.implicitRules[j] = r
 	}
 }
+*/
 
 func (ex *Executor) reportStats() {
 	if !katiLogFlag && !katiStatsFlag {
@@ -642,44 +549,21 @@
 
 	LogStats("build=%d alreadyDone=%d noRule=%d, upToDate=%d runCommand=%d",
 		ex.buildCnt, ex.alreadyDoneCnt, ex.noRuleCnt, ex.upToDateCnt, ex.runCommandCnt)
-	LogStats("explicit=%d implicit=%d suffix=%d explicitWOCmd=%d",
-		ex.pickExplicitRuleCnt, ex.pickImplicitRuleCnt, ex.pickSuffixRuleCnt, ex.pickExplicitRuleWithoutCmdCnt)
 	if len(ex.trace) > 1 {
 		LogStats("trace=%q", ex.trace)
 	}
 }
 
-func NewExecutor(er *EvalResult, vars Vars) *Executor {
-	ex := newExecutor(vars, er.ruleVars)
-	// TODO: We should move this to somewhere around evalCmd so that
-	// we can handle SHELL in target specific variables.
-	shellVar := ex.vars.Lookup("SHELL")
-	ex.shell = shellVar.String()
-
-	ex.populateRules(er)
+func NewExecutor() *Executor {
+	ex := &Executor{
+		done: make(map[string]int64),
+	}
 	return ex
 }
 
-func (ex *Executor) Exec(targets []string) error {
-	if len(targets) == 0 {
-		if ex.firstRule == nil {
-			ErrorNoLocation("*** No targets.")
-		}
-		targets = append(targets, ex.firstRule.outputs[0])
+func (ex *Executor) Exec(roots []*DepNode) error {
+	for _, root := range roots {
+		ex.build(root, "")
 	}
-
-	LogStats("%d variables", len(ex.vars))
-	LogStats("%d explicit rules", len(ex.rules))
-	LogStats("%d implicit rules", len(ex.implicitRules))
-	LogStats("%d suffix rules", len(ex.suffixRules))
-
-	for _, target := range targets {
-		ex.trace = []string{target}
-		_, err := ex.build(target, "")
-		if err != nil {
-			return err
-		}
-	}
-	ex.reportStats()
 	return nil
 }
diff --git a/main.go b/main.go
index 5f81dc1..06a9477 100644
--- a/main.go
+++ b/main.go
@@ -152,11 +152,19 @@
 	LogStats("eval time: %q", time.Now().Sub(startTime))
 
 	startTime = time.Now()
-	ex := NewExecutor(er, vars)
-	LogStats("exec prepare time: %q", time.Now().Sub(startTime))
+	ce := NewCommandEvaluator(er, vars)
+	LogStats("eval command prepare time: %q", time.Now().Sub(startTime))
 
 	startTime = time.Now()
-	err = ex.Exec(targets)
+	nodes, err2 := ce.Eval(targets)
+	if err2 != nil {
+		panic(err2)
+	}
+	LogStats("eval command time: %q", time.Now().Sub(startTime))
+
+	startTime = time.Now()
+	ex := NewExecutor()
+	err = ex.Exec(nodes)
 	if err != nil {
 		panic(err)
 	}