[go] implement find emulator

10 files changed, 1632 insertions, 771 deletions

diff --git a/cmd/kati/main.go b/cmd/kati/main.go
index 637f8bf..67c3a97 100644
--- a/cmd/kati/main.go
+++ b/cmd/kati/main.go
@@ -23,7 +23,6 @@ import (
 	"path/filepath"
 	"runtime"
 	"runtime/pprof"
-	"strings"
 	"text/template"
 	"time"
 
@@ -58,8 +57,6 @@ var (
 	ninjaSuffix         string
 	gomaDir             string
 	detectAndroidEcho   bool
-	findCachePrunes     string
-	findCacheLeafNames  string
 	shellDate           string
 )
 
@@ -91,10 +88,6 @@ func init() {
 	// TODO(ukai): implement --regen
 	flag.BoolVar(&detectAndroidEcho, "detect_android_echo", false, "detect echo as ninja description.")
 
-	flag.StringVar(&findCachePrunes, "find_cache_prunes", "",
-		"space separated prune directories for find cache.")
-	flag.StringVar(&findCacheLeafNames, "find_cache_leaf_names", "",
-		"space separated leaf names for find cache.")
 	flag.StringVar(&shellDate, "shell_date", "", "specify $(shell date) time as "+shellDateTimeformat)
 
 	flag.BoolVar(&kati.StatsFlag, "kati_stats", false, "Show a bunch of statistics")
@@ -104,7 +97,7 @@ func init() {
 	flag.BoolVar(&kati.DryRunFlag, "n", false, "Only print the commands that would be executed")
 
 	// TODO: Make this default.
-	flag.BoolVar(&kati.UseFindCache, "use_find_cache", false, "Use find cache.")
+	flag.BoolVar(&kati.UseFindEmulator, "use_find_emulator", false, "use find emulator")
 	flag.BoolVar(&kati.UseShellBuiltins, "use_shell_builtins", true, "Use shell builtins")
 	flag.StringVar(&kati.IgnoreOptionalInclude, "ignore_optional_include", "", "If specified, skip reading -include directives start with the specified path.")
 }
@@ -164,10 +157,7 @@ func m2nsetup() {
 	fmt.Println("kati: m2n mode")
 	generateNinja = true
 	kati.IgnoreOptionalInclude = "out/%.P"
-	kati.UseFindCache = true
-	if findCachePrunes == "" {
-		findCachePrunes = ".git .repo out"
-	}
+	kati.UseFindEmulator = true
 }
 
 func gomasetup() {
@@ -275,15 +265,6 @@ func katiMain(args []string) error {
 		kati.ShellDateTimestamp = t
 	}
 
-	var leafNames []string
-	if findCacheLeafNames != "" {
-		leafNames = strings.Fields(findCacheLeafNames)
-	}
-	if findCachePrunes != "" {
-		kati.UseFindCache = true
-		kati.AndroidFindCacheInit(strings.Fields(findCachePrunes), leafNames)
-	}
-
 	req := kati.FromCommandLine(args)
 	if makefileFlag != "" {
 		req.Makefile = makefileFlag
diff --git a/dep.go b/dep.go
index 0b27578..2c9870d 100644
--- a/dep.go
+++ b/dep.go
@@ -579,7 +579,7 @@ func (db *depBuilder) Eval(targets []string) ([]*DepNode, error) {
 		logStats("%d explicit rules", len(db.rules))
 		logStats("%d implicit rules", db.implicitRules.size())
 		logStats("%d suffix rules", len(db.suffixRules))
-		logStats("%d dirs %d files", wildcardCache.dirs(), wildcardCache.files())
+		logStats("%d dirs %d files", fsCache.dirs(), fsCache.files())
 	}
 
 	var nodes []*DepNode
diff --git a/flags.go b/flags.go
index 21535cd..f2353a2 100644
--- a/flags.go
+++ b/flags.go
@@ -22,7 +22,7 @@ var (
 
 	DryRunFlag bool
 
-	UseFindCache     bool
+	UseFindEmulator  bool
 	UseShellBuiltins bool
 
 	IgnoreOptionalInclude string
diff --git a/func.go b/func.go
index 2cfb7c4..25fd5b2 100644
--- a/func.go
+++ b/func.go
@@ -948,6 +948,17 @@ func (f *funcShell) Eval(w evalWriter, ev *Evaluator) error {
 	}
 	arg := abuf.String()
 	abuf.release()
+	if bc, err := parseBuiltinCommand(arg); err != nil {
+		glog.V(1).Infof("sh builtin: %v", err)
+	} else {
+		glog.Info("use sh builtin:", arg)
+		glog.V(2).Infof("builtin command: %#v", bc)
+		te := traceEvent.begin("sh-builtin", literal(arg), traceEventMain)
+		bc.run(w)
+		traceEvent.end(te)
+		return nil
+	}
+
 	shellVar, err := ev.EvaluateVar("SHELL")
 	if err != nil {
 		return err
@@ -976,7 +987,7 @@ func (f *funcShell) Compact() Value {
 	if len(f.args)-1 < 1 {
 		return f
 	}
-	if !UseFindCache && !UseShellBuiltins {
+	if !UseShellBuiltins {
 		return f
 	}
 
diff --git a/pathutil.go b/pathutil.go
index a0a76b6..61df1ca 100644
--- a/pathutil.go
+++ b/pathutil.go
@@ -18,38 +18,63 @@ import (
 	"bytes"
 	"errors"
 	"fmt"
+	"io"
 	"os"
 	"path/filepath"
-	"runtime"
-	"sort"
+	"strconv"
 	"strings"
 	"sync"
-	"time"
+	"syscall"
 
 	"github.com/golang/glog"
 )
 
-type wildcardCacheT struct {
-	mu     sync.Mutex
-	dirent map[string][]string
+type fileid struct {
+	dev, ino uint64
 }
 
-var wildcardCache = &wildcardCacheT{
-	dirent: make(map[string][]string),
+var (
+	unknownFileid = fileid{}
+	invalidFileid = fileid{dev: 1<<64 - 1, ino: 1<<64 - 1}
+)
+
+type dirent struct {
+	id    fileid
+	name  string
+	lmode os.FileMode
+	mode  os.FileMode
+	// add other fields to support more find commands?
+}
+
+type fsCacheT struct {
+	mu      sync.Mutex
+	ids     map[string]fileid
+	dirents map[fileid][]dirent
+}
+
+var fsCache = &fsCacheT{
+	ids: make(map[string]fileid),
+	dirents: map[fileid][]dirent{
+		invalidFileid: nil,
+	},
+}
+
+func init() {
+	fsCache.readdir(".", unknownFileid)
 }
 
-func (w *wildcardCacheT) dirs() int {
-	w.mu.Lock()
-	defer w.mu.Unlock()
-	return len(w.dirent)
+func (c *fsCacheT) dirs() int {
+	c.mu.Lock()
+	defer c.mu.Unlock()
+	return len(c.dirents)
 }
 
-func (w *wildcardCacheT) files() int {
-	w.mu.Lock()
-	defer w.mu.Unlock()
+func (c *fsCacheT) files() int {
+	c.mu.Lock()
+	defer c.mu.Unlock()
 	n := 0
-	for _, names := range w.dirent {
-		n += len(names)
+	for _, ents := range c.dirents {
+		n += len(ents)
 	}
 	return n
 }
@@ -77,74 +102,157 @@ func wildcardUnescape(pat string) string {
 	return buf.String()
 }
 
-func filepathClean(path string) string {
-	if path == "" {
-		return "."
+func filepathJoin(names ...string) string {
+	var dir string
+	for i, n := range names {
+		dir += n
+		if i != len(names)-1 && n != "" && n[len(n)-1] != '/' {
+			dir += "/"
+		}
 	}
-	dir, file := filepath.Split(path)
-	if dir == "" {
-		return file
+	return dir
+}
+
+func filepathClean(path string) string {
+	var names []string
+	if filepath.IsAbs(path) {
+		names = append(names, "")
 	}
-	if dir == string(filepath.Separator) {
-		return dir + file
+	paths := strings.Split(path, string(filepath.Separator))
+Loop:
+	for _, n := range paths {
+		if n == "" || n == "." {
+			continue Loop
+		}
+		if n == ".." && len(names) > 0 {
+			dir, last := names[:len(names)-1], names[len(names)-1]
+			parent := strings.Join(dir, string(filepath.Separator))
+			if parent == "" {
+				parent = "."
+			}
+			_, ents := fsCache.readdir(parent, unknownFileid)
+			for _, e := range ents {
+				if e.name != last {
+					continue
+				}
+				if e.lmode&os.ModeSymlink == os.ModeSymlink && e.mode&os.ModeDir == os.ModeDir {
+					// preserve .. if last is symlink dir.
+					names = append(names, "..")
+					continue Loop
+				}
+				// last is not symlink, maybe safe to clean.
+				names = names[:len(names)-1]
+				continue Loop
+			}
+			// parent doesn't exists? preserve ..
+			names = append(names, "..")
+			continue Loop
+		}
+		names = append(names, n)
 	}
-	dir = strings.TrimRight(dir, string(filepath.Separator))
-	dir = filepathClean(dir)
-	if file == "." {
-		return dir
+	if len(names) == 0 {
+		return "."
 	}
-	// TODO(ukai): when file == "..", and dir is not symlink,
-	// we can remove "..".
-	return dir + string(filepath.Separator) + file
+	return strings.Join(names, string(filepath.Separator))
 }
 
-func (w *wildcardCacheT) readdirnames(dir string) []string {
-	dir = filepathClean(dir)
-	w.mu.Lock()
-	names, ok := w.dirent[dir]
-	w.mu.Unlock()
+func (c *fsCacheT) fileid(dir string) fileid {
+	c.mu.Lock()
+	id := c.ids[dir]
+	c.mu.Unlock()
+	return id
+}
+
+func (c *fsCacheT) readdir(dir string, id fileid) (fileid, []dirent) {
+	glog.V(3).Infof("readdir: %s", dir)
+	c.mu.Lock()
+	if id == unknownFileid {
+		id = c.ids[dir]
+	}
+	ents, ok := c.dirents[id]
+	c.mu.Unlock()
 	if ok {
-		return names
+		return id, ents
 	}
 	d, err := os.Open(dir)
 	if err != nil {
-		w.mu.Lock()
-		w.dirent[dir] = nil
-		w.mu.Unlock()
-		return nil
+		c.mu.Lock()
+		c.ids[dir] = invalidFileid
+		c.mu.Unlock()
+		return invalidFileid, nil
 	}
 	defer d.Close()
-	names, _ = d.Readdirnames(-1)
-	sort.Strings(names)
-	w.mu.Lock()
-	w.dirent[dir] = names
-	w.mu.Unlock()
-	return names
+	fi, err := d.Stat()
+	if err != nil {
+		c.mu.Lock()
+		c.ids[dir] = invalidFileid
+		c.mu.Unlock()
+		return invalidFileid, nil
+	}
+	if stat, ok := fi.Sys().(*syscall.Stat_t); ok {
+		id = fileid{dev: stat.Dev, ino: stat.Ino}
+	}
+	names, _ := d.Readdirnames(-1)
+	// need sort?
+	ents = nil
+	var path string
+	for _, name := range names {
+		path = filepath.Join(dir, name)
+		fi, err := os.Lstat(path)
+		if err != nil {
+			glog.Warningf("readdir %s: %v", name, err)
+			ents = append(ents, dirent{name: name})
+			continue
+		}
+		lmode := fi.Mode()
+		mode := lmode
+		if stat, ok := fi.Sys().(*syscall.Stat_t); ok {
+			id = fileid{dev: stat.Dev, ino: stat.Ino}
+		}
+		if lmode&os.ModeSymlink == os.ModeSymlink {
+			fi, err = os.Stat(path)
+			if err != nil {
+				glog.Warningf("readdir %s: %v", name, err)
+			} else {
+				mode = fi.Mode()
+				if stat, ok := fi.Sys().(*syscall.Stat_t); ok {
+					id = fileid{dev: stat.Dev, ino: stat.Ino}
+				}
+			}
+		}
+		ents = append(ents, dirent{id: id, name: name, lmode: lmode, mode: mode})
+	}
+	glog.V(3).Infof("readdir:%s => %v: %v", dir, id, ents)
+	c.mu.Lock()
+	c.ids[dir] = id
+	c.dirents[id] = ents
+	c.mu.Unlock()
+	return id, ents
 }
 
 // glob searches for files matching pattern in the directory dir
 // and appends them to matches. ignore I/O errors.
-func (w *wildcardCacheT) glob(dir, pattern string, matches []string) ([]string, error) {
-	names := w.readdirnames(dir)
+func (c *fsCacheT) glob(dir, pattern string, matches []string) ([]string, error) {
+	_, ents := c.readdir(filepathClean(dir), unknownFileid)
 	switch dir {
 	case "", string(filepath.Separator):
 		// nothing
 	default:
 		dir += string(filepath.Separator) // add trailing separator back
 	}
-	for _, n := range names {
-		matched, err := filepath.Match(pattern, n)
+	for _, ent := range ents {
+		matched, err := filepath.Match(pattern, ent.name)
 		if err != nil {
 			return nil, err
 		}
 		if matched {
-			matches = append(matches, dir+n)
+			matches = append(matches, dir+ent.name)
 		}
 	}
 	return matches, nil
 }
 
-func (w *wildcardCacheT) Glob(pat string) ([]string, error) {
+func (c *fsCacheT) Glob(pat string) ([]string, error) {
 	// TODO(ukai): expand ~ to user's home directory.
 	// TODO(ukai): use find cache for glob if exists
 	// or use wildcardCache for find cache.
@@ -157,16 +265,16 @@ func (w *wildcardCacheT) Glob(pat string) ([]string, error) {
 		dir = dir[:len(dir)-1] // chop off trailing separator
 	}
 	if !hasWildcardMeta(dir) {
-		return w.glob(dir, file, nil)
+		return c.glob(dir, file, nil)
 	}
 
-	m, err := w.Glob(dir)
+	m, err := c.Glob(dir)
 	if err != nil {
 		return nil, err
 	}
 	var matches []string
 	for _, d := range m {
-		matches, err = w.glob(d, file, matches)
+		matches, err = c.glob(d, file, matches)
 		if err != nil {
 			return nil, err
 		}
@@ -175,7 +283,7 @@ func (w *wildcardCacheT) Glob(pat string) ([]string, error) {
 }
 
 func wildcard(w evalWriter, pat string) error {
-	files, err := wildcardCache.Glob(pat)
+	files, err := fsCache.Glob(pat)
 	if err != nil {
 		return err
 	}
@@ -185,430 +293,632 @@ func wildcard(w evalWriter, pat string) error {
 	return nil
 }
 
-type fileInfo struct {
-	path string
-	mode os.FileMode
+type findOp interface {
+	apply(evalWriter, string, dirent) (test bool, prune bool)
 }
 
-type androidFindCacheT struct {
-	once     sync.Once
-	filesch  chan []fileInfo
-	leavesch chan []fileInfo
-	files    []fileInfo
-	leaves   []fileInfo
-	scanTime time.Duration
+type findOpName string
+
+func (op findOpName) apply(w evalWriter, path string, ent dirent) (bool, bool) {
+	matched, err := filepath.Match(string(op), ent.name)
+	if err != nil {
+		glog.Warningf("find -name %q: %v", string(op), err)
+		return false, false
+	}
+	return matched, false
 }
 
-var (
-	androidFindCache        androidFindCacheT
-	androidDefaultLeafNames = []string{"CleanSpec.mk", "Android.mk"}
-)
+type findOpType struct {
+	mode           os.FileMode
+	followSymlinks bool
+}
 
-// AndroidFindCacheInit initializes find cache for android build.
-func AndroidFindCacheInit(prunes, leafNames []string) {
-	if !UseFindCache {
-		return
-	}
-	if leafNames != nil {
-		androidDefaultLeafNames = leafNames
+func (op findOpType) apply(w evalWriter, path string, ent dirent) (bool, bool) {
+	mode := ent.lmode
+	if op.followSymlinks && ent.mode != 0 {
+		mode = ent.mode
 	}
-	androidFindCache.init(prunes)
+	return op.mode&mode == op.mode, false
 }
 
-func (c *androidFindCacheT) ready() bool {
-	if !UseFindCache {
-		return false
-	}
-	if c.files != nil {
-		return true
-	}
-	select {
-	case c.files = <-c.filesch:
-	}
-	return c.files != nil
+type findOpRegular struct {
+	followSymlinks bool
 }
 
-func (c *androidFindCacheT) leavesReady() bool {
-	if !UseFindCache {
-		return false
+func (op findOpRegular) apply(w evalWriter, path string, ent dirent) (bool, bool) {
+	mode := ent.lmode
+	if op.followSymlinks && ent.mode != 0 {
+		mode = ent.mode
 	}
-	if c.leaves != nil {
-		return true
+	return mode.IsRegular(), false
+}
+
+type findOpNot struct {
+	op findOp
+}
+
+func (op findOpNot) apply(w evalWriter, path string, ent dirent) (bool, bool) {
+	test, prune := op.op.apply(w, path, ent)
+	return !test, prune
+}
+
+type findOpAnd []findOp
+
+func (op findOpAnd) apply(w evalWriter, path string, ent dirent) (bool, bool) {
+	var prune bool
+	for _, o := range op {
+		test, p := o.apply(w, path, ent)
+		if p {
+			prune = true
+		}
+		if !test {
+			return test, prune
+		}
 	}
-	select {
-	case c.leaves = <-c.leavesch:
+	return true, prune
+}
+
+type findOpOr struct {
+	op1, op2 findOp
+}
+
+func (op findOpOr) apply(w evalWriter, path string, ent dirent) (bool, bool) {
+	test, prune := op.op1.apply(w, path, ent)
+	if test {
+		return test, prune
 	}
-	return c.leaves != nil
+	return op.op2.apply(w, path, ent)
 }
 
-func (c *androidFindCacheT) init(prunes []string) {
-	if !UseFindCache {
+type findOpPrune struct{}
+
+func (op findOpPrune) apply(w evalWriter, path string, ent dirent) (bool, bool) {
+	return true, true
+}
+
+type findOpPrint struct{}
+
+func (op findOpPrint) apply(w evalWriter, path string, ent dirent) (bool, bool) {
+	var name string
+	if path == "" {
+		name = ent.name
+	} else if ent.name == "." {
+		name = path
+	} else {
+		name = filepathJoin(path, ent.name)
+	}
+	glog.V(3).Infof("find print: %s", name)
+	w.writeWordString(name)
+	return true, false
+}
+
+func (c *fsCacheT) find(w evalWriter, fc findCommand, path string, id fileid, depth int, seen map[fileid]string) {
+	glog.V(2).Infof("find: path:%s depth:%d", path, depth)
+	id, ents := c.readdir(filepathClean(filepathJoin(fc.chdir, path)), id)
+	if ents == nil {
+		glog.V(1).Infof("find: %s %s not found", fc.chdir, path)
 		return
 	}
-	c.once.Do(func() {
-		c.filesch = make(chan []fileInfo, 1)
-		c.leavesch = make(chan []fileInfo, 1)
-		go c.start(prunes, androidDefaultLeafNames)
-	})
-}
-
-func (c *androidFindCacheT) start(prunes, leafNames []string) {
-	glog.Infof("find cache init: prunes=%q leafNames=%q", prunes, leafNames)
-	te := traceEvent.begin("findcache", literal("init"), traceEventFindCache)
-	defer func() {
-		traceEvent.end(te)
-		c.scanTime = time.Since(te.t)
-		logStats("android find cache scan: %v", c.scanTime)
-	}()
-
-	dirs := make(chan string, 32)
-	filech := make(chan fileInfo, 1000)
-	leafch := make(chan fileInfo, 1000)
-	var wg sync.WaitGroup
-	numWorker := runtime.NumCPU() - 1
-	wg.Add(numWorker)
-	for i := 0; i < numWorker; i++ {
-		go func() {
-			defer wg.Done()
-			for dir := range dirs {
-				err := filepath.Walk(dir, func(path string, info os.FileInfo, err error) error {
-					if info.IsDir() {
-						for _, prune := range prunes {
-							if info.Name() == prune {
-								glog.V(1).Infof("find cache prune: %s", path)
-								return filepath.SkipDir
-							}
-						}
-					}
-					filech <- fileInfo{
-						path: path,
-						mode: info.Mode(),
-					}
-					for _, leaf := range leafNames {
-						if info.Name() == leaf {
-							glog.V(1).Infof("find cache leaf: %s", path)
-							leafch <- fileInfo{
-								path: path,
-								mode: info.Mode(),
-							}
-							break
-						}
-					}
-					return nil
-				})
-				if err != nil && err != filepath.SkipDir {
-					glog.Warningf("error in adnroid find cache: %v", err)
-					close(c.filesch)
-					close(c.leavesch)
+	for _, ent := range ents {
+		glog.V(3).Infof("find: path:%s ent:%s depth:%d", path, ent.name, depth)
+		_, prune := fc.apply(w, path, ent)
+		mode := ent.lmode
+		if fc.followSymlinks {
+			if mode&os.ModeSymlink == os.ModeSymlink {
+				lpath := filepathJoin(path, ent.name)
+				if p, ok := seen[ent.id]; ok {
+					// stderr?
+					glog.Errorf("find: File system loop detected; `%s' is part of the same file system loop as `%s'.", lpath, p)
 					return
 				}
+				seen[ent.id] = lpath
 			}
-		}()
-	}
-
-	go func() {
-		dirs := make(map[string]bool)
-		leavesTe := traceEvent.begin("findcache", literal("leaves"), traceEventFindCacheLeaves)
-		var leaves []fileInfo
-		nfiles := 0
-		for leaf := range leafch {
-			leaves = append(leaves, leaf)
-			nfiles++
-			for dir := filepath.Dir(leaf.path); dir != "."; dir = filepath.Dir(dir) {
-				if dirs[dir] {
-					break
-				}
-				leaves = append(leaves, fileInfo{
-					path: dir,
-					mode: leaf.mode | os.ModeDir,
-				})
-				dirs[dir] = true
-			}
+			mode = ent.mode
 		}
-		sort.Sort(fileInfoByLeaf(leaves))
-		c.leavesch <- leaves
-		traceEvent.end(leavesTe)
-		logStats("%d leaves %d dirs in find cache", nfiles, len(dirs))
-		if !glog.V(1) {
-			return
-		}
-		for i, leaf := range leaves {
-			glog.Infof("android findleaves cache: %d: %s %v", i, leaf.path, leaf.mode)
-		}
-	}()
-
-	go func() {
-		filesTe := traceEvent.begin("findcache", literal("files"), traceEventFindCacheFiles)
-		var files []fileInfo
-		for file := range filech {
-			files = append(files, file)
+		if !mode.IsDir() {
+			glog.V(3).Infof("find: not dir: %s/%s", path, ent.name)
+			continue
 		}
-		sort.Sort(fileInfoByName(files))
-		c.filesch <- files
-		traceEvent.end(filesTe)
-		logStats("%d files in find cache", len(files))
-		if !glog.V(1) {
-			return
+		if prune {
+			glog.V(3).Infof("find: prune: %s", path)
+			continue
 		}
-		for i, fi := range files {
-			glog.Infof("android find cache: %d: %s %v", i, fi.path, fi.mode)
+		if depth >= fc.depth {
+			glog.V(3).Infof("find: depth: %d >= %d", depth, fc.depth)
+			continue
 		}
-	}()
+		c.find(w, fc, filepathJoin(path, ent.name), ent.id, depth+1, seen)
+	}
+}
 
-	curdir, err := os.Open(".")
-	if err != nil {
-		glog.Warningf("open . failed: %v", err)
-		close(c.filesch)
-		close(c.leavesch)
-		return
+type findCommand struct {
+	testdir        string // before chdir
+	chdir          string
+	finddirs       []string // after chdir
+	followSymlinks bool
+	ops            []findOp
+	depth          int
+}
+
+func parseFindCommand(cmd string) (findCommand, error) {
+	if !strings.Contains(cmd, "find") {
+		return findCommand{}, errNotFind
 	}
-	names, err := curdir.Readdirnames(-1)
+	fcp := findCommandParser{
+		shellParser: shellParser{
+			cmd: cmd,
+		},
+	}
+	err := fcp.parse()
 	if err != nil {
-		glog.Warningf("readdir . failed: %v", err)
-		close(c.filesch)
-		close(c.leavesch)
+		return fcp.fc, err
+	}
+	if len(fcp.fc.finddirs) == 0 {
+		fcp.fc.finddirs = append(fcp.fc.finddirs, ".")
+	}
+	if fcp.fc.chdir != "" {
+		fcp.fc.chdir = filepathClean(fcp.fc.chdir)
+	}
+	if filepath.IsAbs(fcp.fc.chdir) {
+		return fcp.fc, errFindAbspath
+	}
+	for _, dir := range fcp.fc.finddirs {
+		if filepath.IsAbs(dir) {
+			return fcp.fc, errFindAbspath
+		}
+	}
+	return fcp.fc, nil
+}
+
+func (fc findCommand) run(w evalWriter) {
+	glog.V(3).Infof("find: %#v", fc)
+	_, ents := fsCache.readdir(filepathClean(fc.testdir), unknownFileid)
+	if ents == nil {
+		glog.V(1).Infof("find: testdir %s - not dir", fc.testdir)
 		return
 	}
-	curdir.Close()
+	for _, dir := range fc.finddirs {
+		seen := make(map[fileid]string)
+		id, _ := fsCache.readdir(filepathClean(filepathJoin(fc.chdir, dir)), unknownFileid)
+		_, prune := fc.apply(w, dir, dirent{id: id, name: ".", mode: os.ModeDir, lmode: os.ModeDir})
+		if prune {
+			glog.V(3).Infof("find: prune: %s", dir)
+			continue
+		}
+		if 0 >= fc.depth {
+			glog.V(3).Infof("find: depth: 0 >= %d", fc.depth)
+			continue
+		}
+		fsCache.find(w, fc, dir, id, 1, seen)
+	}
+}
 
-	for _, name := range names {
-		dirs <- name
+func (fc findCommand) apply(w evalWriter, path string, ent dirent) (test, prune bool) {
+	var p bool
+	for _, op := range fc.ops {
+		test, p = op.apply(w, path, ent)
+		if p {
+			prune = true
+		}
+		if !test {
+			break
+		}
 	}
-	close(dirs)
-	wg.Wait()
-	close(filech)
-	close(leafch)
+	glog.V(2).Infof("apply path:%s ent:%v => test=%t, prune=%t", path, ent, test, prune)
+	return test, prune
 }
 
-type fileInfoByName []fileInfo
+var (
+	errNotFind             = errors.New("not find command")
+	errFindBackground      = errors.New("find command: background")
+	errFindUnbalancedQuote = errors.New("find command: unbalanced quote")
+	errFindDupChdir        = errors.New("find command: dup chdir")
+	errFindDupTestdir      = errors.New("find command: dup testdir")
+	errFindExtra           = errors.New("find command: extra")
+	errFindUnexpectedEnd   = errors.New("find command: unexpected end")
+	errFindAbspath         = errors.New("find command: abs path")
+	errFindChdirAndTestdir = errors.New("find command: chdir, testdir")
+)
 
-func (f fileInfoByName) Len() int      { return len(f) }
-func (f fileInfoByName) Swap(i, j int) { f[i], f[j] = f[j], f[i] }
-func (f fileInfoByName) Less(i, j int) bool {
-	return f[i].path < f[j].path
+type findCommandParser struct {
+	fc findCommand
+	shellParser
 }
 
-type fileInfoByLeaf []fileInfo
-
-func (f fileInfoByLeaf) Len() int      { return len(f) }
-func (f fileInfoByLeaf) Swap(i, j int) { f[i], f[j] = f[j], f[i] }
-func (f fileInfoByLeaf) Less(i, j int) bool {
-	di := strings.Count(f[i].path, "/")
-	dj := strings.Count(f[j].path, "/")
-	if di != dj {
-		return di < dj
+func (p *findCommandParser) parse() error {
+	p.fc.depth = 1<<31 - 1 // max int32
+	var hasIf bool
+	for {
+		tok, err := p.token()
+		if err == io.EOF || tok == "" {
+			return nil
+		}
+		if err != nil {
+			return err
+		}
+		switch tok {
+		case "cd":
+			if p.fc.chdir != "" {
+				return errFindDupChdir
+			}
+			p.fc.chdir, err = p.token()
+			if err != nil {
+				return err
+			}
+			err = p.expect(";", "&&")
+			if err != nil {
+				return err
+			}
+		case "if":
+			err = p.expect("[")
+			if err != nil {
+				return err
+			}
+			if hasIf {
+				return errFindDupTestdir
+			}
+			err = p.parseTest()
+			if err != nil {
+				return err
+			}
+			err = p.expectSeq("]", ";", "then")
+			if err != nil {
+				return err
+			}
+			hasIf = true
+		case "test":
+			if hasIf {
+				return errFindDupTestdir
+			}
+			err = p.parseTest()
+			if err != nil {
+				return err
+			}
+			err = p.expect("&&")
+			if err != nil {
+				return err
+			}
+		case "find":
+			err = p.parseFind()
+			if err != nil {
+				return err
+			}
+			if hasIf {
+				err = p.expect("fi")
+				if err != nil {
+					return err
+				}
+			}
+			tok, err = p.token()
+			if err != io.EOF || tok != "" {
+				return errFindExtra
+			}
+			return nil
+		}
 	}
-	diri := filepath.Dir(f[i].path) + "/"
-	dirj := filepath.Dir(f[j].path) + "/"
-	if diri != dirj {
-		return diri < dirj
+}
+
+func (p *findCommandParser) parseTest() error {
+	if p.fc.testdir != "" {
+		return errFindDupTestdir
 	}
-	mdi := f[i].mode & os.ModeDir
-	mdj := f[j].mode & os.ModeDir
-	if mdi != mdj {
-		return mdi < mdj
+	err := p.expect("-d")
+	if err != nil {
+		return err
 	}
-	return f[i].path < f[j].path
+	p.fc.testdir, err = p.token()
+	return err
 }
 
-var errSkipDir = errors.New("skip dir")
-
-func (c *androidFindCacheT) walk(dir string, walkFn func(int, fileInfo) error) error {
-	i := sort.Search(len(c.files), func(i int) bool {
-		return c.files[i].path >= dir
-	})
-	glog.V(1).Infof("android find in dir cache: %s i=%d/%d", dir, i, len(c.files))
-	start := i
-	var skipdirs []string
-Loop:
-	for i := start; i < len(c.files); i++ {
-		if c.files[i].path == dir {
-			err := walkFn(i, c.files[i])
+func (p *findCommandParser) parseFind() error {
+	for {
+		tok, err := p.token()
+		if err == io.EOF || tok == "" || tok == ";" {
+			var print findOpPrint
+			if len(p.fc.ops) == 0 || p.fc.ops[len(p.fc.ops)-1] != print {
+				p.fc.ops = append(p.fc.ops, print)
+			}
+			return nil
+		}
+		if err != nil {
+			return err
+		}
+		if tok != "" && (tok[0] == '-' || tok == "\\(") {
+			p.unget(tok)
+			op, err := p.parseFindCond()
 			if err != nil {
 				return err
 			}
+			if op != nil {
+				p.fc.ops = append(p.fc.ops, op)
+			}
 			continue
 		}
-		if !strings.HasPrefix(c.files[i].path, dir) {
-			glog.V(1).Infof("android find in dir cache: %s end=%d/%d", dir, i, len(c.files))
-			return nil
+		p.fc.finddirs = append(p.fc.finddirs, tok)
+	}
+}
+
+func (p *findCommandParser) parseFindCond() (findOp, error) {
+	return p.parseExpr()
+}
+
+func (p *findCommandParser) parseExpr() (findOp, error) {
+	op, err := p.parseTerm()
+	if err != nil {
+		return nil, err
+	}
+	if op == nil {
+		return nil, nil
+	}
+	for {
+		tok, err := p.token()
+		if err == io.EOF || tok == "" {
+			return op, nil
 		}
-		if !strings.HasPrefix(c.files[i].path, dir+"/") {
-			continue
+		if err != nil {
+			return nil, err
 		}
-		for _, skip := range skipdirs {
-			if strings.HasPrefix(c.files[i].path, skip+"/") {
-				continue Loop
-			}
+		if tok != "-or" && tok != "-o" {
+			p.unget(tok)
+			return op, nil
 		}
+		op2, err := p.parseTerm()
+		if err != nil {
+			return nil, err
+		}
+		op = findOpOr{op, op2}
+	}
+}
 
-		err := walkFn(i, c.files[i])
-		if err == errSkipDir {
-			glog.V(1).Infof("android find in skip dir: %s", c.files[i].path)
-			skipdirs = append(skipdirs, c.files[i].path)
-			continue
+func (p *findCommandParser) parseTerm() (findOp, error) {
+	op, err := p.parseFact()
+	if err != nil {
+		return nil, err
+	}
+	if op == nil {
+		return nil, nil
+	}
+	var ops []findOp
+	ops = append(ops, op)
+	for {
+		tok, err := p.token()
+		if err == io.EOF || tok == "" {
+			if len(ops) == 1 {
+				return ops[0], nil
+			}
+			return findOpAnd(ops), nil
 		}
 		if err != nil {
-			return err
+			return nil, err
+		}
+		if tok != "-and" && tok != "-a" {
+			p.unget(tok)
+		}
+		op, err = p.parseFact()
+		if err != nil {
+			return nil, err
+		}
+		if op == nil {
+			if len(ops) == 1 {
+				return ops[0], nil
+			}
+			return findOpAnd(ops), nil
 		}
+		ops = append(ops, op) // findAndOp?
 	}
-	return nil
 }
 
-// pattern in repo/android/build/core/definitions.mk
-// find-subdir-assets
-// if [ -d $1 ] ; then cd $1 ; find ./ -not -name '.*' -and -type f -and -not -type l ; fi
-func (c *androidFindCacheT) findInDir(w evalWriter, dir string) {
-	dir = filepath.Clean(dir)
-	glog.V(1).Infof("android find in dir cache: %s", dir)
-	c.walk(dir, func(_ int, fi fileInfo) error {
-		// -not -name '.*'
-		if strings.HasPrefix(filepath.Base(fi.path), ".") {
-			return nil
+func (p *findCommandParser) parseFact() (findOp, error) {
+	tok, err := p.token()
+	if err != nil {
+		return nil, err
+	}
+	switch tok {
+	case "-L":
+		p.fc.followSymlinks = true
+		return nil, nil
+	case "-prune":
+		return findOpPrune{}, nil
+	case "-print":
+		return findOpPrint{}, nil
+	case "-maxdepth":
+		tok, err = p.token()
+		if err != nil {
+			return nil, err
 		}
-		// -type f and -not -type l
-		// regular type and not symlink
-		if !fi.mode.IsRegular() {
-			return nil
+		i, err := strconv.ParseInt(tok, 10, 32)
+		if err != nil {
+			return nil, err
 		}
-		name := strings.TrimPrefix(fi.path, dir+"/")
-		name = "./" + name
-		w.writeWordString(name)
-		glog.V(1).Infof("android find in dir cache: %s=> %s", dir, name)
-		return nil
-	})
-}
-
-// pattern in repo/android/build/core/definitions.mk
-// all-java-files-under etc
-// cd ${LOCAL_PATH} ; find -L $1 -name "*<ext>" -and -not -name ".*"
-// returns false if symlink is found.
-func (c *androidFindCacheT) findExtFilesUnder(w evalWriter, chdir, root, ext string) bool {
-	chdir = filepath.Clean(chdir)
-	dir := filepath.Join(chdir, root)
-	glog.V(1).Infof("android find %s in dir cache: %s %s", ext, chdir, root)
-	// check symlinks
-	var matches []int
-	err := c.walk(dir, func(i int, fi fileInfo) error {
-		if fi.mode&os.ModeSymlink == os.ModeSymlink {
-			glog.Warningf("android find %s in dir cache: detect symlink %s %v", ext, c.files[i].path, c.files[i].mode)
-			return fmt.Errorf("symlink %s", fi.path)
-		}
-		matches = append(matches, i)
-		return nil
-	})
+		if i < 0 {
+			return nil, fmt.Errorf("find commnad: -maxdepth negative: %d", i)
+		}
+		p.fc.depth = int(i)
+		return nil, nil
+	case "-not", "\\!":
+		op, err := p.parseFact()
+		if err != nil {
+			return nil, err
+		}
+		return findOpNot{op}, nil
+	case "\\(":
+		op, err := p.parseExpr()
+		if err != nil {
+			return nil, err
+		}
+		err = p.expect("\\)")
+		if err != nil {
+			return nil, err
+		}
+		return op, nil
+	case "-name":
+		tok, err = p.token()
+		if err != nil {
+			return nil, err
+		}
+		return findOpName(tok), nil
+	case "-type":
+		tok, err = p.token()
+		if err != nil {
+			return nil, err
+		}
+		var m os.FileMode
+		switch tok {
+		case "b":
+			m = os.ModeDevice
+		case "c":
+			m = os.ModeDevice | os.ModeCharDevice
+		case "d":
+			m = os.ModeDir
+		case "p":
+			m = os.ModeNamedPipe
+		case "l":
+			m = os.ModeSymlink
+		case "f":
+			return findOpRegular{p.fc.followSymlinks}, nil
+		case "s":
+			m = os.ModeSocket
+		default:
+			return nil, fmt.Errorf("find command: unsupported -type %s", tok)
+		}
+		return findOpType{m, p.fc.followSymlinks}, nil
+	case "-o", "-or", "-a", "-and":
+		p.unget(tok)
+		return nil, nil
+	default:
+		if tok != "" && tok[0] == '-' {
+			return nil, fmt.Errorf("find command: unsupported %s", tok)
+		}
+		p.unget(tok)
+		return nil, nil
+	}
+}
+
+type findleavesCommand struct {
+	name     string
+	dirs     []string
+	prunes   []string
+	mindepth int
+}
+
+func parseFindleavesCommand(cmd string) (findleavesCommand, error) {
+	if !strings.Contains(cmd, "build/tools/findleaves.py") {
+		return findleavesCommand{}, errNotFindleaves
+	}
+	fcp := findleavesCommandParser{
+		shellParser: shellParser{
+			cmd: cmd,
+		},
+	}
+	err := fcp.parse()
 	if err != nil {
-		return false
-	}
-	// no symlinks
-	for _, i := range matches {
-		fi := c.files[i]
-		base := filepath.Base(fi.path)
-		// -name "*<ext>"
-		if filepath.Ext(base) != ext {
+		return fcp.fc, err
+	}
+	return fcp.fc, nil
+}
+
+func (fc findleavesCommand) run(w evalWriter) {
+	glog.V(3).Infof("findleaves: %#v", fc)
+	for _, dir := range fc.dirs {
+		seen := make(map[fileid]string)
+		id, _ := fsCache.readdir(filepathClean(dir), unknownFileid)
+		fc.walk(w, dir, id, 1, seen)
+	}
+}
+
+func (fc findleavesCommand) walk(w evalWriter, dir string, id fileid, depth int, seen map[fileid]string) {
+	id, ents := fsCache.readdir(filepathClean(dir), id)
+	var subdirs []dirent
+	for _, ent := range ents {
+		if ent.mode.IsDir() {
+			if fc.isPrune(ent.name) {
+				continue
+			}
+			subdirs = append(subdirs, ent)
 			continue
 		}
-		// -not -name ".*"
-		if strings.HasPrefix(base, ".") {
+		if depth < fc.mindepth {
 			continue
 		}
-		name := strings.TrimPrefix(fi.path, chdir+"/")
-		w.writeWordString(name)
-		glog.V(1).Infof("android find %s in dir cache: %s=> %s", ext, dir, name)
+		if ent.name == fc.name {
+			w.writeWordString(filepathJoin(dir, ent.name))
+			// no recurse subdirs
+			return
+		}
+	}
+	for _, subdir := range subdirs {
+		if subdir.lmode&os.ModeSymlink == os.ModeSymlink {
+			lpath := filepathJoin(dir, subdir.name)
+			if p, ok := seen[subdir.id]; ok {
+				// symlink loop detected.
+				glog.Errorf("findleaves: loop detected %q was %q", lpath, p)
+				continue
+			}
+			seen[subdir.id] = lpath
+		}
+		fc.walk(w, filepathJoin(dir, subdir.name), subdir.id, depth+1, seen)
 	}
-	return true
 }
 
-// pattern: in repo/android/build/core/base_rules.mk
-// java_resource_file_groups+= ...
-// cd ${TOP_DIR}${LOCAL_PATH}/${dir} && find . -type d -a -name ".svn" -prune \
-// -o -type f -a \! -name "*.java" -a \! -name "package.html" -a \! \
-// -name "overview.html" -a \! -name ".*.swp" -a \! -name ".DS_Store" \
-// -a \! -name "*~" -print )
-func (c *androidFindCacheT) findJavaResourceFileGroup(w evalWriter, dir string) {
-	glog.V(1).Infof("android find java resource in dir cache: %s", dir)
-	c.walk(filepath.Clean(dir), func(_ int, fi fileInfo) error {
-		// -type d -a -name ".svn" -prune
-		if fi.mode.IsDir() && filepath.Base(fi.path) == ".svn" {
-			return errSkipDir
+func (fc findleavesCommand) isPrune(name string) bool {
+	for _, p := range fc.prunes {
+		if p == name {
+			return true
 		}
-		// -type f
-		if !fi.mode.IsRegular() {
-			return nil
+	}
+	return false
+}
+
+var (
+	errNotFindleaves        = errors.New("not findleaves command")
+	errFindleavesEmptyPrune = errors.New("findleaves: empty prune")
+	errFindleavesNoFilename = errors.New("findleaves: no filename")
+)
+
+type findleavesCommandParser struct {
+	fc findleavesCommand
+	shellParser
+}
+
+func (p *findleavesCommandParser) parse() error {
+	var args []string
+	p.fc.mindepth = -1
+	tok, err := p.token()
+	if err != nil {
+		return err
+	}
+	if tok != "build/tools/findleaves.py" {
+		return errNotFindleaves
+	}
+	for {
+		tok, err := p.token()
+		if err == io.EOF || tok == "" {
+			break
 		}
-		// ! -name "*.java" -a ! -name "package.html" -a
-		// ! -name "overview.html" -a ! -name ".*.swp" -a
-		// ! -name ".DS_Store" -a ! -name "*~"
-		base := filepath.Base(fi.path)
-		if filepath.Ext(base) == ".java" ||
-			base == "package.html" ||
-			base == "overview.html" ||
-			(strings.HasPrefix(base, ".") && strings.HasSuffix(base, ".swp")) ||
-			base == ".DS_Store" ||
-			strings.HasSuffix(base, "~") {
-			return nil
+		if err != nil {
+			return err
 		}
-		name := strings.TrimPrefix(fi.path, dir+"/")
-		name = "./" + name
-		w.writeWordString(name)
-		glog.V(1).Infof("android find java resource in dir cache: %s=> %s", dir, name)
-		return nil
-	})
-}
-
-func (c *androidFindCacheT) findleaves(w evalWriter, dir, name string, prunes []string, mindepth int) bool {
-	var found []string
-	var dirs []string
-	dir = filepath.Clean(dir)
-	topdepth := strings.Count(dir, "/")
-	dirs = append(dirs, dir)
-	for len(dirs) > 0 {
-		dir = filepath.Clean(dirs[0]) + "/"
-		dirs = dirs[1:]
-		if dir == "./" {
-			dir = ""
-		}
-		depth := strings.Count(dir, "/")
-		// glog.V(1).Infof("android findleaves dir=%q depth=%d dirs=%q", dir, depth, dirs)
-		i := sort.Search(len(c.leaves), func(i int) bool {
-			di := strings.Count(c.leaves[i].path, "/")
-			if di != depth {
-				return di >= depth
+		switch {
+		case strings.HasPrefix(tok, "--prune="):
+			prune := filepath.Base(strings.TrimPrefix(tok, "--prune="))
+			if prune == "" {
+				return errFindleavesEmptyPrune
 			}
-			diri := filepath.Dir(c.leaves[i].path) + "/"
-			if diri != dir {
-				return diri >= dir
-			}
-			return c.leaves[i].path >= dir
-		})
-		glog.V(1).Infof("android findleaves dir=%q i=%d/%d", dir, i, len(c.leaves))
-
-	Scandir:
-		for ; i < len(c.leaves); i++ {
-			if dir == "" && strings.Contains(c.leaves[i].path, "/") {
-				break
-			}
-			if !strings.HasPrefix(c.leaves[i].path, dir) {
-				break
-			}
-			if mindepth < 0 || depth >= topdepth+mindepth {
-				if !c.leaves[i].mode.IsDir() && filepath.Base(c.leaves[i].path) == name {
-					n := "./" + c.leaves[i].path
-					found = append(found, n)
-					glog.V(1).Infof("android findleaves name=%s=> %s (depth=%d topdepth=%d mindepth=%d)", name, n, depth, topdepth, mindepth)
-					break Scandir
-				}
-			}
-			if c.leaves[i].mode.IsDir() {
-				dirs = append(dirs, c.leaves[i].path)
+			p.fc.prunes = append(p.fc.prunes, prune)
+		case strings.HasPrefix(tok, "--mindepth="):
+			md := strings.TrimPrefix(tok, "--mindepth=")
+			i, err := strconv.ParseInt(md, 10, 32)
+			if err != nil {
+				return err
 			}
+			p.fc.mindepth = int(i)
+		default:
+			args = append(args, tok)
 		}
-		// glog.V(1).Infof("android findleaves next dirs=%q", dirs)
 	}
-	glog.V(1).Infof("android findleave done")
-	sort.Strings(found)
-	for _, f := range found {
-		w.writeWordString(f)
+	if len(args) < 2 {
+		return errFindleavesNoFilename
 	}
-	return true
+	p.fc.dirs, p.fc.name = args[:len(args)-1], args[len(args)-1]
+	return nil
 }
diff --git a/pathutil_test.go b/pathutil_test.go
new file mode 100644
index 0000000..d64bb65
--- /dev/null
+++ b/pathutil_test.go
@@ -0,0 +1,796 @@
+// Copyright 2015 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.
+
+package kati
+
+import (
+	"os"
+	"path/filepath"
+	"reflect"
+	"strings"
+	"testing"
+)
+
+type mockfs struct {
+	id       fileid
+	ofscache *fsCacheT
+}
+
+func newFS() *mockfs {
+	fs := &mockfs{
+		ofscache: fsCache,
+	}
+	fsCache = &fsCacheT{
+		ids:     make(map[string]fileid),
+		dirents: make(map[fileid][]dirent),
+	}
+	fsCache.ids["."] = fs.dir(".").id
+	return fs
+}
+
+func (m *mockfs) dump(t *testing.T) {
+	t.Log("fs ids:")
+	for name, id := range fsCache.ids {
+		t.Logf(" %q=%v", name, id)
+	}
+	t.Log("fs dirents:")
+	for id, ents := range fsCache.dirents {
+		t.Logf(" %v:", id)
+		for _, ent := range ents {
+			t.Logf("  %#v", ent)
+		}
+	}
+}
+
+func (m *mockfs) close() {
+	fsCache = m.ofscache
+}
+
+func (m *mockfs) dirent(name string, mode os.FileMode) dirent {
+	id := m.id
+	m.id.ino++
+	return dirent{id: id, name: name, mode: mode, lmode: mode}
+}
+
+func (m *mockfs) addent(name string, ent dirent) {
+	dir, name := filepath.Split(name)
+	dir = strings.TrimSuffix(dir, string(filepath.Separator))
+	if dir == "" {
+		dir = "."
+	}
+	di, ok := fsCache.ids[dir]
+	if !ok {
+		if dir == "." {
+			panic(". not found:" + name)
+		}
+		de := m.add(m.dir, dir)
+		fsCache.ids[dir] = de.id
+		di = de.id
+	}
+	for _, e := range fsCache.dirents[di] {
+		if e.name == ent.name {
+			return
+		}
+	}
+	fsCache.dirents[di] = append(fsCache.dirents[di], ent)
+}
+
+func (m *mockfs) add(t func(string) dirent, name string) dirent {
+	ent := t(filepath.Base(name))
+	m.addent(name, ent)
+	return ent
+}
+
+func (m *mockfs) symlink(name string, ent dirent) {
+	lent := ent
+	lent.lmode = os.ModeSymlink
+	lent.name = filepath.Base(name)
+	m.addent(name, lent)
+}
+
+func (m *mockfs) dirref(name string) dirent {
+	id := fsCache.ids[name]
+	return dirent{id: id, name: filepath.Base(name), mode: os.ModeDir, lmode: os.ModeDir}
+}
+
+func (m *mockfs) notfound() dirent        { return dirent{id: invalidFileid} }
+func (m *mockfs) dir(name string) dirent  { return m.dirent(name, os.ModeDir) }
+func (m *mockfs) file(name string) dirent { return m.dirent(name, os.FileMode(0644)) }
+
+func TestFilepathClean(t *testing.T) {
+	fs := newFS()
+	defer fs.close()
+	di := fs.add(fs.dir, "dir")
+	fs.symlink("link", di)
+
+	fs.dump(t)
+
+	for _, tc := range []struct {
+		path string
+		want string
+	}{
+		{path: "foo", want: "foo"},
+		{path: ".", want: "."},
+		{path: "./", want: "."},
+		{path: ".///", want: "."},
+		{path: "", want: "."},
+		{path: "foo/bar", want: "foo/bar"},
+		{path: "./foo", want: "foo"},
+		{path: "foo///", want: "foo"},
+		{path: "foo//bar", want: "foo/bar"},
+		{path: "foo/../bar", want: "foo/../bar"},   // foo doesn't exist
+		{path: "dir/../bar", want: "bar"},          // dir is real dir
+		{path: "link/../bar", want: "link/../bar"}, // link is symlink
+		{path: "foo/./bar", want: "foo/bar"},
+		{path: "/foo/bar", want: "/foo/bar"},
+	} {
+		if got, want := filepathClean(tc.path), tc.want; got != want {
+			t.Errorf("filepathClean(%q)=%q; want=%q", tc.path, got, want)
+		}
+	}
+}
+
+func TestParseFindCommand(t *testing.T) {
+	maxdepth := 1<<31 - 1
+	for _, tc := range []struct {
+		cmd  string
+		want findCommand
+	}{
+		{
+			cmd: "find testdir",
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: "find .",
+			want: findCommand{
+				finddirs: []string{"."},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: "find ",
+			want: findCommand{
+				finddirs: []string{"."},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: "find testdir/../testdir",
+			want: findCommand{
+				finddirs: []string{"testdir/../testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: "find testdir -print",
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: "find testdir -name foo",
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpName("foo"), findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "file1"`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpName("file1"), findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "*1"`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpName("*1"), findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "*1" -and -name "file*"`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpAnd{findOpName("*1"), findOpName("file*")}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "*1" -or -name "file*"`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpName("file*")}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "*1" -or -type f`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpRegular{}}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "*1" -or -not -type f`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpNot{findOpRegular{}}}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "*1" -or \! -type f`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpNot{findOpRegular{}}}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "*1" -or -type d`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpType{mode: os.ModeDir}}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "*1" -or -type l`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpType{mode: os.ModeSymlink}}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name "*1" -a -type l -o -name "dir*"`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpAnd([]findOp{findOpName("*1"), findOpType{mode: os.ModeSymlink}}), findOpName("dir*")}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir \( -name "dir*" -o -name "*1" \) -a -type f`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpAnd([]findOp{findOpOr{findOpName("dir*"), findOpName("*1")}, findOpRegular{}}), findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `cd testdir && find`,
+			want: findCommand{
+				chdir:    "testdir",
+				finddirs: []string{"."},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `test -d testdir && find testdir`,
+			want: findCommand{
+				testdir:  "testdir",
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `if [ -d testdir ] ; then find testdir ; fi`,
+			want: findCommand{
+				testdir:  "testdir",
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `if [ -d testdir ]; then find testdir; fi`,
+			want: findCommand{
+				testdir:  "testdir",
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `if [ -d testdir ]; then cd testdir && find .; fi`,
+			want: findCommand{
+				chdir:    "testdir",
+				testdir:  "testdir",
+				finddirs: []string{"."},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -name dir2 -prune -o -name file1`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpAnd([]findOp{findOpName("dir2"), findOpPrune{}}), findOpName("file1")}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir testdir`,
+			want: findCommand{
+				finddirs: []string{"testdir", "testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+		},
+		{
+			cmd: `find -L testdir -type f`,
+			want: findCommand{
+				finddirs:       []string{"testdir"},
+				followSymlinks: true,
+				ops:            []findOp{findOpRegular{followSymlinks: true}, findOpPrint{}},
+				depth:          maxdepth,
+			},
+		},
+		{
+			cmd: `cd testdir; find -L . -type f`,
+			want: findCommand{
+				chdir:          "testdir",
+				finddirs:       []string{"."},
+				followSymlinks: true,
+				ops:            []findOp{findOpRegular{followSymlinks: true}, findOpPrint{}},
+				depth:          maxdepth,
+			},
+		},
+		{
+			cmd: `find testdir -maxdepth 1`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    1,
+			},
+		},
+		{
+			cmd: `find testdir -maxdepth 0`,
+			want: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    0,
+			},
+		},
+	} {
+		fc, err := parseFindCommand(tc.cmd)
+		if err != nil {
+			t.Errorf("parseFindCommand(%q)=_, %v; want=_, <nil>", tc.cmd, err)
+			continue
+		}
+		if got, want := fc, tc.want; !reflect.DeepEqual(got, want) {
+			t.Errorf("parseFindCommand(%q)=%#v\n want=%#v\n", tc.cmd, got, want)
+		}
+	}
+
+}
+
+func TestParseFindCommandFail(t *testing.T) {
+	for _, cmd := range []string{
+		`find testdir -maxdepth hoge`,
+		`find testdir -maxdepth 1hoge`,
+		`find testdir -maxdepth -1`,
+	} {
+		_, err := parseFindCommand(cmd)
+		if err == nil {
+			t.Errorf("parseFindCommand(%q)=_, <nil>; want=_, err", cmd)
+		}
+	}
+}
+
+func TestFind(t *testing.T) {
+	fs := newFS()
+	defer fs.close()
+	fs.add(fs.file, "Makefile")
+	fs.add(fs.file, "testdir/file1")
+	fs.add(fs.file, "testdir/file2")
+	file1 := fs.add(fs.file, "testdir/dir1/file1")
+	dir1 := fs.dirref("testdir/dir1")
+	fs.add(fs.file, "testdir/dir1/file2")
+	fs.add(fs.file, "testdir/dir2/file1")
+	fs.add(fs.file, "testdir/dir2/file2")
+	fs.symlink("testdir/dir2/link1", file1)
+	fs.symlink("testdir/dir2/link2", dir1)
+	fs.symlink("testdir/dir2/link3", fs.notfound())
+
+	fs.dump(t)
+
+	maxdepth := 1<<31 - 1
+	for _, tc := range []struct {
+		fc   findCommand
+		want string
+	}{
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir testdir/file1 testdir/file2 testdir/dir1 testdir/dir1/file1 testdir/dir1/file2 testdir/dir2 testdir/dir2/file1 testdir/dir2/file2 testdir/dir2/link1 testdir/dir2/link2 testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"."},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `. ./Makefile ./testdir ./testdir/file1 ./testdir/file2 ./testdir/dir1 ./testdir/dir1/file1 ./testdir/dir1/file2 ./testdir/dir2 ./testdir/dir2/file1 ./testdir/dir2/file2 ./testdir/dir2/link1 ./testdir/dir2/link2 ./testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"./"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `./ ./Makefile ./testdir ./testdir/file1 ./testdir/file2 ./testdir/dir1 ./testdir/dir1/file1 ./testdir/dir1/file2 ./testdir/dir2 ./testdir/dir2/file1 ./testdir/dir2/file2 ./testdir/dir2/link1 ./testdir/dir2/link2 ./testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{".///"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `./// .///Makefile .///testdir .///testdir/file1 .///testdir/file2 .///testdir/dir1 .///testdir/dir1/file1 .///testdir/dir1/file2 .///testdir/dir2 .///testdir/dir2/file1 .///testdir/dir2/file2 .///testdir/dir2/link1 .///testdir/dir2/link2 .///testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"./."},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `./. ././Makefile ././testdir ././testdir/file1 ././testdir/file2 ././testdir/dir1 ././testdir/dir1/file1 ././testdir/dir1/file2 ././testdir/dir2 ././testdir/dir2/file1 ././testdir/dir2/file2 ././testdir/dir2/link1 ././testdir/dir2/link2 ././testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"././"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `././ ././Makefile ././testdir ././testdir/file1 ././testdir/file2 ././testdir/dir1 ././testdir/dir1/file1 ././testdir/dir1/file2 ././testdir/dir2 ././testdir/dir2/file1 ././testdir/dir2/file2 ././testdir/dir2/link1 ././testdir/dir2/link2 ././testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir/../testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/../testdir testdir/../testdir/file1 testdir/../testdir/file2 testdir/../testdir/dir1 testdir/../testdir/dir1/file1 testdir/../testdir/dir1/file2 testdir/../testdir/dir2 testdir/../testdir/dir2/file1 testdir/../testdir/dir2/file2 testdir/../testdir/dir2/link1 testdir/../testdir/dir2/link2 testdir/../testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpName("foo"), findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: ``,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpName("file1"), findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/file1 testdir/dir1/file1 testdir/dir2/file1`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpAnd{findOpName("*1"), findOpName("file*")}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/file1 testdir/dir1/file1 testdir/dir2/file1`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpName("file*")}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/file1 testdir/file2 testdir/dir1 testdir/dir1/file1 testdir/dir1/file2 testdir/dir2/file1 testdir/dir2/file2 testdir/dir2/link1`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpRegular{}}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/file1 testdir/file2 testdir/dir1 testdir/dir1/file1 testdir/dir1/file2 testdir/dir2/file1 testdir/dir2/file2 testdir/dir2/link1`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpNot{findOpRegular{}}}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir testdir/file1 testdir/dir1 testdir/dir1/file1 testdir/dir2 testdir/dir2/file1 testdir/dir2/link1 testdir/dir2/link2 testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpType{mode: os.ModeDir}}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir testdir/file1 testdir/dir1 testdir/dir1/file1 testdir/dir2 testdir/dir2/file1 testdir/dir2/link1`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpName("*1"), findOpType{mode: os.ModeSymlink}}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/file1 testdir/dir1 testdir/dir1/file1 testdir/dir2/file1 testdir/dir2/link1 testdir/dir2/link2 testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpAnd([]findOp{findOpName("*1"), findOpType{mode: os.ModeSymlink}}), findOpName("dir*")}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/dir1 testdir/dir2 testdir/dir2/link1`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpAnd([]findOp{findOpName("*1"), findOpType{mode: os.ModeSymlink}}), findOpName("dir*")}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/dir1 testdir/dir2 testdir/dir2/link1`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpAnd([]findOp{findOpOr{findOpName("dir*"), findOpName("*1")}, findOpRegular{}}), findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/file1 testdir/dir1/file1 testdir/dir2/file1`,
+		},
+		{
+			fc: findCommand{
+				chdir:    "testdir",
+				finddirs: []string{"."},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `. ./file1 ./file2 ./dir1 ./dir1/file1 ./dir1/file2 ./dir2 ./dir2/file1 ./dir2/file2 ./dir2/link1 ./dir2/link2 ./dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				chdir:    "testdir",
+				finddirs: []string{"../testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `../testdir ../testdir/file1 ../testdir/file2 ../testdir/dir1 ../testdir/dir1/file1 ../testdir/dir1/file2 ../testdir/dir2 ../testdir/dir2/file1 ../testdir/dir2/file2 ../testdir/dir2/link1 ../testdir/dir2/link2 ../testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				testdir:  "testdir",
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir testdir/file1 testdir/file2 testdir/dir1 testdir/dir1/file1 testdir/dir1/file2 testdir/dir2 testdir/dir2/file1 testdir/dir2/file2 testdir/dir2/link1 testdir/dir2/link2 testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				chdir:    "testdir",
+				testdir:  "testdir",
+				finddirs: []string{"."},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `. ./file1 ./file2 ./dir1 ./dir1/file1 ./dir1/file2 ./dir2 ./dir2/file1 ./dir2/file2 ./dir2/link1 ./dir2/link2 ./dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpOr{findOpAnd([]findOp{findOpName("dir2"), findOpPrune{}}), findOpName("file1")}, findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir/file1 testdir/dir1/file1 testdir/dir2`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir", "testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    maxdepth,
+			},
+			want: `testdir testdir/file1 testdir/file2 testdir/dir1 testdir/dir1/file1 testdir/dir1/file2 testdir/dir2 testdir/dir2/file1 testdir/dir2/file2 testdir/dir2/link1 testdir/dir2/link2 testdir/dir2/link3 testdir testdir/file1 testdir/file2 testdir/dir1 testdir/dir1/file1 testdir/dir1/file2 testdir/dir2 testdir/dir2/file1 testdir/dir2/file2 testdir/dir2/link1 testdir/dir2/link2 testdir/dir2/link3`,
+		},
+		// symlink
+		{
+			fc: findCommand{
+				finddirs:       []string{"testdir"},
+				followSymlinks: true,
+				ops:            []findOp{findOpRegular{followSymlinks: true}, findOpPrint{}},
+				depth:          maxdepth,
+			},
+			want: `testdir/file1 testdir/file2 testdir/dir1/file1 testdir/dir1/file2 testdir/dir2/file1 testdir/dir2/file2 testdir/dir2/link1 testdir/dir2/link2/file1 testdir/dir2/link2/file2`,
+		},
+		{
+			fc: findCommand{
+				finddirs:       []string{"testdir"},
+				followSymlinks: true,
+				ops:            []findOp{findOpType{mode: os.ModeDir, followSymlinks: true}, findOpPrint{}},
+				depth:          maxdepth,
+			},
+			want: `testdir testdir/dir1 testdir/dir2 testdir/dir2/link2`,
+		},
+		{
+			fc: findCommand{
+				finddirs:       []string{"testdir"},
+				followSymlinks: true,
+				ops:            []findOp{findOpType{mode: os.ModeSymlink, followSymlinks: true}, findOpPrint{}},
+				depth:          maxdepth,
+			},
+			want: `testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				chdir:          "testdir",
+				finddirs:       []string{"."},
+				followSymlinks: true,
+				ops:            []findOp{findOpRegular{followSymlinks: true}, findOpPrint{}},
+				depth:          maxdepth,
+			},
+			want: `./file1 ./file2 ./dir1/file1 ./dir1/file2 ./dir2/file1 ./dir2/file2 ./dir2/link1 ./dir2/link2/file1 ./dir2/link2/file2`,
+		},
+		// maxdepth
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    1,
+			},
+			want: `testdir testdir/file1 testdir/file2 testdir/dir1 testdir/dir2`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    2,
+			},
+			want: `testdir testdir/file1 testdir/file2 testdir/dir1 testdir/dir1/file1 testdir/dir1/file2 testdir/dir2 testdir/dir2/file1 testdir/dir2/file2 testdir/dir2/link1 testdir/dir2/link2 testdir/dir2/link3`,
+		},
+		{
+			fc: findCommand{
+				finddirs: []string{"testdir"},
+				ops:      []findOp{findOpPrint{}},
+				depth:    0,
+			},
+			want: `testdir`,
+		},
+	} {
+		var wb wordBuffer
+		tc.fc.run(&wb)
+		if got, want := wb.buf.String(), tc.want; got != want {
+			t.Errorf("%#v\n got  %q\n want %q", tc.fc, got, want)
+		}
+	}
+}
+
+func TestParseFindleavesCommand(t *testing.T) {
+	for _, tc := range []struct {
+		cmd  string
+		want findleavesCommand
+	}{
+		{
+			cmd: `build/tools/findleaves.py --prune=out --prune=.repo --prune=.git . CleanSpec.mk`,
+			want: findleavesCommand{
+				name:     "CleanSpec.mk",
+				dirs:     []string{"."},
+				prunes:   []string{"out", ".repo", ".git"},
+				mindepth: -1,
+			},
+		},
+		{
+			cmd: `build/tools/findleaves.py --prune=out --prune=.repo --prune=.git --mindepth=2  art bionic Android.mk`,
+			want: findleavesCommand{
+				name:     "Android.mk",
+				dirs:     []string{"art", "bionic"},
+				prunes:   []string{"out", ".repo", ".git"},
+				mindepth: 2,
+			},
+		},
+	} {
+		fc, err := parseFindleavesCommand(tc.cmd)
+		if err != nil {
+			t.Errorf("parseFindleavesCommand(%q)=_, %v; want=_, <nil", tc.cmd, err)
+			continue
+		}
+		if got, want := fc, tc.want; !reflect.DeepEqual(got, want) {
+			t.Errorf("parseFindleavesCommand(%q)=%#v\n want=%#v\n", tc.cmd, got, want)
+		}
+	}
+}
+
+func TestFindleaves(t *testing.T) {
+	fs := newFS()
+	defer fs.close()
+
+	fs.add(fs.file, "art/Android.mk")
+	fs.add(fs.file, "art/compiler/Android.mk")
+	fs.add(fs.file, "art/CleanSpec.mk")
+	fs.add(fs.file, "bionic/Android.mk")
+	fs.add(fs.file, "bionic/CleanSpec.mk")
+	fs.add(fs.file, "bootable/recovery/Android.mk")
+	fs.add(fs.file, "bootable/recovery/CleanSpec.mk")
+	fs.add(fs.file, "frameworks/base/Android.mk")
+	fs.add(fs.file, "frameworks/base/CleanSpec.mk")
+	fs.add(fs.file, "frameworks/base/cmds/am/Android.mk")
+	fs.add(fs.file, "frameworks/base/cmds/pm/Android.mk")
+	fs.add(fs.file, "frameworks/base/location/Android.mk")
+	fs.add(fs.file, "frameworks/base/packages/WAPPushManager/CleanSpec.mk")
+	fs.add(fs.file, "out/outputfile")
+	fs.add(fs.file, "art/.git/index")
+	fs.add(fs.file, ".repo/manifests")
+
+	fs.dump(t)
+
+	for _, tc := range []struct {
+		fc   findleavesCommand
+		want string
+	}{
+		{
+			fc: findleavesCommand{
+				name:     "CleanSpec.mk",
+				dirs:     []string{"."},
+				prunes:   []string{"out", ".repo", ".git"},
+				mindepth: -1,
+			},
+			want: `./art/CleanSpec.mk ./bionic/CleanSpec.mk ./bootable/recovery/CleanSpec.mk ./frameworks/base/CleanSpec.mk`,
+		},
+		{
+			fc: findleavesCommand{
+				name:     "Android.mk",
+				dirs:     []string{"art", "bionic", "frameworks/base"},
+				prunes:   []string{"out", ".repo", ".git"},
+				mindepth: 2,
+			},
+			want: `art/compiler/Android.mk frameworks/base/cmds/am/Android.mk frameworks/base/cmds/pm/Android.mk frameworks/base/location/Android.mk`,
+		},
+		{
+			fc: findleavesCommand{
+				name:     "Android.mk",
+				dirs:     []string{"art", "bionic", "frameworks/base"},
+				prunes:   []string{"out", ".repo", ".git"},
+				mindepth: 3,
+			},
+			want: `frameworks/base/cmds/am/Android.mk frameworks/base/cmds/pm/Android.mk`,
+		},
+	} {
+		var wb wordBuffer
+		tc.fc.run(&wb)
+		if got, want := wb.buf.String(), tc.want; got != want {
+			t.Errorf("%#v\n got  %q\n want %q", tc.fc, got, want)
+		}
+	}
+}
diff --git a/rule_parser.go b/rule_parser.go
index a02df0a..1bea505 100644
--- a/rule_parser.go
+++ b/rule_parser.go
@@ -129,7 +129,7 @@ func (r *rule) parseInputs(s []byte) {
 			add(internBytes(input))
 			continue
 		}
-		m, _ := wildcardCache.Glob(string(input))
+		m, _ := fsCache.Glob(string(input))
 		if len(m) == 0 {
 			add(internBytes(input))
 			continue
diff --git a/runtest.rb b/runtest.rb
index 86cb6f7..1d95187 100755
--- a/runtest.rb
+++ b/runtest.rb
@@ -200,7 +200,7 @@ run_make_test = proc do |mk|
     cleanup
     testcases.each do |tc|
       json = "#{tc.empty? ? 'test' : tc}"
-      cmd = "../../kati -save_json=#{json}.json -log_dir=."
+      cmd = "../../kati -save_json=#{json}.json -log_dir=. --use_find_emulator"
       if ckati
         cmd = "../../ckati --use_find_emulator"
       end
diff --git a/shellutil.go b/shellutil.go
index 6aa6b90..353a1a9 100644
--- a/shellutil.go
+++ b/shellutil.go
@@ -15,11 +15,11 @@
 package kati
 
 import (
+	"errors"
 	"fmt"
+	"io"
 	"strings"
 	"time"
-
-	"github.com/golang/glog"
 )
 
 var shBuiltins = []struct {
@@ -44,181 +44,6 @@ var shBuiltins = []struct {
 		},
 	},
 	{
-		name: "android:find-subdir-assets",
-		// in repo/android/build/core/definitions.mk
-		// if [ -d $1 ] ; then cd $1 ; find ./ -not -name '.*' -and -type f -and -not -type l ; fi
-		pattern: expr{
-			literal("if [ -d "),
-			matchVarref{},
-			literal(" ] ; then cd "),
-			matchVarref{},
-			literal(" ; find ./ -not -name '.*' -and -type f -and -not -type l ; fi"),
-		},
-		compact: func(sh *funcShell, v []Value) Value {
-			if v[0] != v[1] {
-				return sh
-			}
-			androidFindCache.init(nil)
-			return &funcShellAndroidFindFileInDir{
-				funcShell: sh,
-				dir:       v[0],
-			}
-		},
-	},
-	{
-		name: "android:all-java-files-under",
-		// in repo/android/build/core/definitions.mk
-		// cd ${LOCAL_PATH} ; find -L $1 -name "*.java" -and -not -name ".*"
-		pattern: expr{
-			literal("cd "),
-			matchVarref{},
-			literal(" ; find -L "),
-			matchVarref{},
-			literal(` -name "*.java" -and -not -name ".*"`),
-		},
-		compact: func(sh *funcShell, v []Value) Value {
-			androidFindCache.init(nil)
-			return &funcShellAndroidFindExtFilesUnder{
-				funcShell: sh,
-				chdir:     v[0],
-				roots:     v[1],
-				ext:       ".java",
-			}
-		},
-	},
-	{
-		name: "android:all-proto-files-under",
-		// in repo/android/build/core/definitions.mk
-		// cd $(LOCAL_PATH) ; \
-		// find -L $(1) -name "*.proto" -and -not -name ".*"
-		pattern: expr{
-			literal("cd "),
-			matchVarref{},
-			literal(" ; find -L "),
-			matchVarref{},
-			literal(" -name \"*.proto\" -and -not -name \".*\""),
-		},
-		compact: func(sh *funcShell, v []Value) Value {
-			androidFindCache.init(nil)
-			return &funcShellAndroidFindExtFilesUnder{
-				funcShell: sh,
-				chdir:     v[0],
-				roots:     v[1],
-				ext:       ".proto",
-			}
-		},
-	},
-	{
-		name: "android:java_resource_file_groups",
-		// in repo/android/build/core/base_rules.mk
-		// cd ${TOP_DIR}${LOCAL_PATH}/${dir} && find . -type d -a \
-		// -name ".svn" -prune -o -type f -a \! -name "*.java" \
-		// -a \! -name "package.html" -a \! -name "overview.html" \
-		// -a \! -name ".*.swp" -a \! -name ".DS_Store" \
-		// -a \! -name "*~" -print )
-		pattern: expr{
-			literal("cd "),
-			matchVarref{},
-			matchVarref{},
-			mustLiteralRE("(/)"),
-			matchVarref{},
-			literal(` && find . -type d -a -name ".svn" -prune -o -type f -a \! -name "*.java" -a \! -name "package.html" -a \! -name "overview.html" -a \! -name ".*.swp" -a \! -name ".DS_Store" -a \! -name "*~" -print `),
-		},
-		compact: func(sh *funcShell, v []Value) Value {
-			androidFindCache.init(nil)
-			return &funcShellAndroidFindJavaResourceFileGroup{
-				funcShell: sh,
-				dir:       expr(v),
-			}
-		},
-	},
-	{
-		name: "android:subdir_cleanspecs",
-		// in repo/android/build/core/cleanspec.mk
-		// build/tools/findleaves.py --prune=$(OUT_DIR) --prune=.repo --prune=.git . CleanSpec.mk)
-		pattern: expr{
-			literal("build/tools/findleaves.py --prune="),
-			matchVarref{},
-			literal(" --prune=.repo --prune=.git . CleanSpec.mk"),
-		},
-		compact: func(sh *funcShell, v []Value) Value {
-			if !contains(androidDefaultLeafNames, "CleanSpec.mk") {
-				return sh
-			}
-			androidFindCache.init(nil)
-			return &funcShellAndroidFindleaves{
-				funcShell: sh,
-				prunes: []Value{
-					v[0],
-					literal(".repo"),
-					literal(".git"),
-				},
-				dirlist:  literal("."),
-				name:     literal("CleanSpec.mk"),
-				mindepth: -1,
-			}
-		},
-	},
-	{
-		name: "android:subdir_makefiles",
-		// in repo/android/build/core/main.mk
-		// build/tools/findleaves.py --prune=$(OUT_DIR) --prune=.repo --prune=.git $(subdirs) Android.mk
-		pattern: expr{
-			literal("build/tools/findleaves.py --prune="),
-			matchVarref{},
-			literal(" --prune=.repo --prune=.git "),
-			matchVarref{},
-			literal(" Android.mk"),
-		},
-		compact: func(sh *funcShell, v []Value) Value {
-			if !contains(androidDefaultLeafNames, "Android.mk") {
-				return sh
-			}
-			androidFindCache.init(nil)
-			return &funcShellAndroidFindleaves{
-				funcShell: sh,
-				prunes: []Value{
-					v[0],
-					literal(".repo"),
-					literal(".git"),
-				},
-				dirlist:  v[1],
-				name:     literal("Android.mk"),
-				mindepth: -1,
-			}
-		},
-	},
-	{
-		name: "android:first-makefiles-under",
-		// in repo/android/build/core/definisions.mk
-		// build/tools/findleaves.py --prune=$(OUT_DIR) --prune=.repo --prune=.git \
-		// --mindepth=2 $(1) Android.mk
-		pattern: expr{
-			literal("build/tools/findleaves.py --prune="),
-			matchVarref{},
-			literal(" --prune=.repo --prune=.git --mindepth=2 "),
-			matchVarref{},
-			literal(" Android.mk"),
-		},
-		compact: func(sh *funcShell, v []Value) Value {
-			if !contains(androidDefaultLeafNames, "Android.mk") {
-				return sh
-			}
-			androidFindCache.init(nil)
-			return &funcShellAndroidFindleaves{
-				funcShell: sh,
-				prunes: []Value{
-					v[0],
-					literal(".repo"),
-					literal(".git"),
-				},
-				dirlist:  v[1],
-				name:     literal("Android.mk"),
-				mindepth: 2,
-			}
-		},
-	},
-	{
 		name: "shell-date",
 		pattern: expr{
 			mustLiteralRE(`date \+(\S+)`),
@@ -269,160 +94,6 @@ func (f *funcShellAndroidRot13) Eval(w evalWriter, ev *Evaluator) error {
 	return nil
 }
 
-type funcShellAndroidFindFileInDir struct {
-	*funcShell
-	dir Value
-}
-
-func (f *funcShellAndroidFindFileInDir) Eval(w evalWriter, ev *Evaluator) error {
-	abuf := newEbuf()
-	fargs, err := ev.args(abuf, f.dir)
-	if err != nil {
-		return err
-	}
-	dir := string(trimSpaceBytes(fargs[0]))
-	abuf.release()
-	glog.V(1).Infof("shellAndroidFindFileInDir %s => %s", f.dir.String(), dir)
-	if strings.Contains(dir, "..") {
-		glog.Warningf("shellAndroidFindFileInDir contains ..: call original shell")
-		return f.funcShell.Eval(w, ev)
-	}
-	if !androidFindCache.ready() {
-		glog.Warningf("shellAndroidFindFileInDir androidFindCache is not ready: call original shell")
-		return f.funcShell.Eval(w, ev)
-	}
-	androidFindCache.findInDir(w, dir)
-	return nil
-}
-
-type funcShellAndroidFindExtFilesUnder struct {
-	*funcShell
-	chdir Value
-	roots Value
-	ext   string
-}
-
-func (f *funcShellAndroidFindExtFilesUnder) Eval(w evalWriter, ev *Evaluator) error {
-	abuf := newEbuf()
-	err := f.chdir.Eval(abuf, ev)
-	if err != nil {
-		return err
-	}
-	chdir := string(trimSpaceBytes(abuf.Bytes()))
-	abuf.release()
-	wb := newWbuf()
-	err = f.roots.Eval(wb, ev)
-	if err != nil {
-		return err
-	}
-	hasDotDot := false
-	var roots []string
-	for _, word := range wb.words {
-		root := string(word)
-		if strings.Contains(root, "..") {
-			hasDotDot = true
-		}
-		roots = append(roots, root)
-	}
-	wb.release()
-	glog.V(1).Infof("shellAndroidFindExtFilesUnder %s,%s => %s,%s", f.chdir.String(), f.roots.String(), chdir, roots)
-	if strings.Contains(chdir, "..") || hasDotDot {
-		glog.Warningf("shellAndroidFindExtFilesUnder contains ..: call original shell")
-		return f.funcShell.Eval(w, ev)
-	}
-	if !androidFindCache.ready() {
-		glog.Warningf("shellAndroidFindExtFilesUnder androidFindCache is not ready: call original shell")
-		return f.funcShell.Eval(w, ev)
-	}
-	buf := newEbuf()
-	for _, root := range roots {
-		if !androidFindCache.findExtFilesUnder(buf, chdir, root, f.ext) {
-			buf.release()
-			glog.Warningf("shellAndroidFindExtFilesUnder androidFindCache couldn't handle: call original shell")
-			return f.funcShell.Eval(w, ev)
-		}
-	}
-	w.Write(buf.Bytes())
-	buf.release()
-	return nil
-}
-
-type funcShellAndroidFindJavaResourceFileGroup struct {
-	*funcShell
-	dir Value
-}
-
-func (f *funcShellAndroidFindJavaResourceFileGroup) Eval(w evalWriter, ev *Evaluator) error {
-	abuf := newEbuf()
-	fargs, err := ev.args(abuf, f.dir)
-	if err != nil {
-		return err
-	}
-	dir := string(trimSpaceBytes(fargs[0]))
-	abuf.release()
-	glog.V(1).Infof("shellAndroidFindJavaResourceFileGroup %s => %s", f.dir.String(), dir)
-	if strings.Contains(dir, "..") {
-		glog.Warningf("shellAndroidFindJavaResourceFileGroup contains ..: call original shell")
-		return f.funcShell.Eval(w, ev)
-	}
-	if !androidFindCache.ready() {
-		glog.Warningf("shellAndroidFindJavaResourceFileGroup androidFindCache is not ready: call original shell")
-		return f.funcShell.Eval(w, ev)
-	}
-	androidFindCache.findJavaResourceFileGroup(w, dir)
-	return nil
-}
-
-type funcShellAndroidFindleaves struct {
-	*funcShell
-	prunes   []Value
-	dirlist  Value
-	name     Value
-	mindepth int
-}
-
-func (f *funcShellAndroidFindleaves) Eval(w evalWriter, ev *Evaluator) error {
-	if !androidFindCache.leavesReady() {
-		glog.Warningf("shellAndroidFindleaves androidFindCache is not ready: call original shell")
-		return f.funcShell.Eval(w, ev)
-	}
-	abuf := newEbuf()
-	var params []Value
-	params = append(params, f.name)
-	params = append(params, f.prunes...)
-	fargs, err := ev.args(abuf, params...)
-	if err != nil {
-		return err
-	}
-	name := string(trimSpaceBytes(fargs[0]))
-	var prunes []string
-	for _, arg := range fargs[1:] {
-		prunes = append(prunes, string(trimSpaceBytes(arg)))
-	}
-	abuf.release()
-
-	wb := newWbuf()
-	err = f.dirlist.Eval(wb, ev)
-	if err != nil {
-		return err
-	}
-	var dirs []string
-	for _, word := range wb.words {
-		dir := string(word)
-		if strings.Contains(dir, "..") {
-			glog.Warningf("shellAndroidFindleaves contains .. in %s: call original shell", dir)
-			return f.funcShell.Eval(w, ev)
-		}
-		dirs = append(dirs, dir)
-	}
-	wb.release()
-
-	for _, dir := range dirs {
-		androidFindCache.findleaves(w, dir, name, prunes, f.mindepth)
-	}
-	return nil
-}
-
 var (
 	// ShellDateTimestamp is an timestamp used for $(shell date).
 	ShellDateTimestamp time.Time
@@ -465,3 +136,97 @@ func (f *funcShellDate) Eval(w evalWriter, ev *Evaluator) error {
 	fmt.Fprint(w, ShellDateTimestamp.Format(f.format))
 	return nil
 }
+
+type buildinCommand interface {
+	run(w evalWriter)
+}
+
+var errFindEmulatorDisabled = errors.New("builtin: find emulator disabled")
+
+func parseBuiltinCommand(cmd string) (buildinCommand, error) {
+	if !UseFindEmulator {
+		return nil, errFindEmulatorDisabled
+	}
+	if strings.HasPrefix(cmd, "build/tools/findleaves") {
+		return parseFindleavesCommand(cmd)
+	}
+	return parseFindCommand(cmd)
+}
+
+type shellParser struct {
+	cmd        string
+	ungetToken string
+}
+
+func (p *shellParser) token() (string, error) {
+	if p.ungetToken != "" {
+		tok := p.ungetToken
+		p.ungetToken = ""
+		return tok, nil
+	}
+	p.cmd = trimLeftSpace(p.cmd)
+	if len(p.cmd) == 0 {
+		return "", io.EOF
+	}
+	if p.cmd[0] == ';' {
+		tok := p.cmd[0:1]
+		p.cmd = p.cmd[1:]
+		return tok, nil
+	}
+	if p.cmd[0] == '&' {
+		if len(p.cmd) == 1 || p.cmd[1] != '&' {
+			return "", errFindBackground
+		}
+		tok := p.cmd[0:2]
+		p.cmd = p.cmd[2:]
+		return tok, nil
+	}
+	// TODO(ukai): redirect token.
+	i := 0
+	for i < len(p.cmd) {
+		if isWhitespace(rune(p.cmd[i])) || p.cmd[i] == ';' || p.cmd[i] == '&' {
+			break
+		}
+		i++
+	}
+	tok := p.cmd[0:i]
+	p.cmd = p.cmd[i:]
+	c := tok[0]
+	if c == '\'' || c == '"' {
+		if len(tok) < 2 || tok[len(tok)-1] != c {
+			return "", errFindUnbalancedQuote
+		}
+		// todo: unquote?
+		tok = tok[1 : len(tok)-1]
+	}
+	return tok, nil
+}
+
+func (p *shellParser) unget(s string) {
+	if s != "" {
+		p.ungetToken = s
+	}
+}
+
+func (p *shellParser) expect(toks ...string) error {
+	tok, err := p.token()
+	if err != nil {
+		return err
+	}
+	for _, t := range toks {
+		if tok == t {
+			return nil
+		}
+	}
+	return fmt.Errorf("shell: token=%q; want=%q", tok, toks)
+}
+
+func (p *shellParser) expectSeq(toks ...string) error {
+	for _, tok := range toks {
+		err := p.expect(tok)
+		if err != nil {
+			return err
+		}
+	}
+	return nil
+}
diff --git a/stats.go b/stats.go
index 2557888..a8ea461 100644
--- a/stats.go
+++ b/stats.go
@@ -32,9 +32,7 @@ type traceEventT struct {
 
 const (
 	traceEventMain = iota + 1
-	traceEventFindCache
-	traceEventFindCacheLeaves
-	traceEventFindCacheFiles
+	// add new ones to use new goroutine.
 )
 
 var traceEvent traceEventT
@@ -80,7 +78,7 @@ func (t *traceEventT) begin(name string, v Value, tid int) event {
 		e.v = v.String()
 	}
 	if t.f != nil {
-		e.emit = name == "include" || name == "shell" || name == "findcache"
+		e.emit = name == "include" || name == "shell"
 		if e.emit {
 			t.emit("B", e, e.t.Sub(t.t0))
 		}