Home | History | Annotate | Download | only in kati 
      1 // Copyright 2015 Google Inc. All rights reserved
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //      http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 
     15 package kati
     16 
     17 import (
     18 	"bytes"
     19 	"errors"
     20 	"fmt"
     21 	"io"
     22 	"os"
     23 	"path/filepath"
     24 	"strconv"
     25 	"strings"
     26 	"sync"
     27 	"syscall"
     28 
     29 	"github.com/golang/glog"
     30 )
     31 
     32 type fileid struct {
     33 	dev, ino uint64
     34 }
     35 
     36 var (
     37 	unknownFileid = fileid{}
     38 	invalidFileid = fileid{dev: 1<<64 - 1, ino: 1<<64 - 1}
     39 )
     40 
     41 type dirent struct {
     42 	id    fileid
     43 	name  string
     44 	lmode os.FileMode
     45 	mode  os.FileMode
     46 	// add other fields to support more find commands?
     47 }
     48 
     49 type fsCacheT struct {
     50 	mu      sync.Mutex
     51 	ids     map[string]fileid
     52 	dirents map[fileid][]dirent
     53 }
     54 
     55 var fsCache = &fsCacheT{
     56 	ids: make(map[string]fileid),
     57 	dirents: map[fileid][]dirent{
     58 		invalidFileid: nil,
     59 	},
     60 }
     61 
     62 func init() {
     63 	fsCache.readdir(".", unknownFileid)
     64 }
     65 
     66 func (c *fsCacheT) dirs() int {
     67 	c.mu.Lock()
     68 	defer c.mu.Unlock()
     69 	return len(c.dirents)
     70 }
     71 
     72 func (c *fsCacheT) files() int {
     73 	c.mu.Lock()
     74 	defer c.mu.Unlock()
     75 	n := 0
     76 	for _, ents := range c.dirents {
     77 		n += len(ents)
     78 	}
     79 	return n
     80 }
     81 
     82 func hasWildcardMeta(pat string) bool {
     83 	return strings.IndexAny(pat, "*?[") >= 0
     84 }
     85 
     86 func hasWildcardMetaByte(pat []byte) bool {
     87 	return bytes.IndexAny(pat, "*?[") >= 0
     88 }
     89 
     90 func wildcardUnescape(pat string) string {
     91 	var buf bytes.Buffer
     92 	for i := 0; i < len(pat); i++ {
     93 		if pat[i] == '\\' && i+1 < len(pat) {
     94 			switch pat[i+1] {
     95 			case '*', '?', '[', '\\':
     96 				buf.WriteByte(pat[i])
     97 			}
     98 			continue
     99 		}
    100 		buf.WriteByte(pat[i])
    101 	}
    102 	return buf.String()
    103 }
    104 
    105 func filepathJoin(names ...string) string {
    106 	var dir string
    107 	for i, n := range names {
    108 		dir += n
    109 		if i != len(names)-1 && n != "" && n[len(n)-1] != '/' {
    110 			dir += "/"
    111 		}
    112 	}
    113 	return dir
    114 }
    115 
    116 func filepathClean(path string) string {
    117 	var names []string
    118 	if filepath.IsAbs(path) {
    119 		names = append(names, "")
    120 	}
    121 	paths := strings.Split(path, string(filepath.Separator))
    122 Loop:
    123 	for _, n := range paths {
    124 		if n == "" || n == "." {
    125 			continue Loop
    126 		}
    127 		if n == ".." && len(names) > 0 {
    128 			dir, last := names[:len(names)-1], names[len(names)-1]
    129 			parent := strings.Join(dir, string(filepath.Separator))
    130 			if parent == "" {
    131 				parent = "."
    132 			}
    133 			_, ents := fsCache.readdir(parent, unknownFileid)
    134 			for _, e := range ents {
    135 				if e.name != last {
    136 					continue
    137 				}
    138 				if e.lmode&os.ModeSymlink == os.ModeSymlink && e.mode&os.ModeDir == os.ModeDir {
    139 					// preserve .. if last is symlink dir.
    140 					names = append(names, "..")
    141 					continue Loop
    142 				}
    143 				// last is not symlink, maybe safe to clean.
    144 				names = names[:len(names)-1]
    145 				continue Loop
    146 			}
    147 			// parent doesn't exists? preserve ..
    148 			names = append(names, "..")
    149 			continue Loop
    150 		}
    151 		names = append(names, n)
    152 	}
    153 	if len(names) == 0 {
    154 		return "."
    155 	}
    156 	return strings.Join(names, string(filepath.Separator))
    157 }
    158 
    159 func (c *fsCacheT) fileid(dir string) fileid {
    160 	c.mu.Lock()
    161 	id := c.ids[dir]
    162 	c.mu.Unlock()
    163 	return id
    164 }
    165 
    166 func (c *fsCacheT) readdir(dir string, id fileid) (fileid, []dirent) {
    167 	glog.V(3).Infof("readdir: %s [%v]", dir, id)
    168 	c.mu.Lock()
    169 	if id == unknownFileid {
    170 		id = c.ids[dir]
    171 	}
    172 	ents, ok := c.dirents[id]
    173 	c.mu.Unlock()
    174 	if ok {
    175 		return id, ents
    176 	}
    177 	glog.V(3).Infof("opendir: %s", dir)
    178 	d, err := os.Open(dir)
    179 	if err != nil {
    180 		c.mu.Lock()
    181 		c.ids[dir] = invalidFileid
    182 		c.mu.Unlock()
    183 		return invalidFileid, nil
    184 	}
    185 	defer d.Close()
    186 	fi, err := d.Stat()
    187 	if err != nil {
    188 		c.mu.Lock()
    189 		c.ids[dir] = invalidFileid
    190 		c.mu.Unlock()
    191 		return invalidFileid, nil
    192 	}
    193 	if stat, ok := fi.Sys().(*syscall.Stat_t); ok {
    194 		id = fileid{dev: uint64(stat.Dev), ino: stat.Ino}
    195 	}
    196 	names, _ := d.Readdirnames(-1)
    197 	// need sort?
    198 	ents = nil
    199 	var path string
    200 	for _, name := range names {
    201 		path = filepath.Join(dir, name)
    202 		fi, err := os.Lstat(path)
    203 		if err != nil {
    204 			glog.Warningf("readdir %s: %v", name, err)
    205 			ents = append(ents, dirent{name: name})
    206 			continue
    207 		}
    208 		lmode := fi.Mode()
    209 		mode := lmode
    210 		var id fileid
    211 		if stat, ok := fi.Sys().(*syscall.Stat_t); ok {
    212 			id = fileid{dev: uint64(stat.Dev), ino: stat.Ino}
    213 		}
    214 		if lmode&os.ModeSymlink == os.ModeSymlink {
    215 			fi, err = os.Stat(path)
    216 			if err != nil {
    217 				glog.Warningf("readdir %s: %v", name, err)
    218 			} else {
    219 				mode = fi.Mode()
    220 				if stat, ok := fi.Sys().(*syscall.Stat_t); ok {
    221 					id = fileid{dev: uint64(stat.Dev), ino: stat.Ino}
    222 				}
    223 			}
    224 		}
    225 		ents = append(ents, dirent{id: id, name: name, lmode: lmode, mode: mode})
    226 	}
    227 	glog.V(3).Infof("readdir:%s => %v: %v", dir, id, ents)
    228 	c.mu.Lock()
    229 	c.ids[dir] = id
    230 	c.dirents[id] = ents
    231 	c.mu.Unlock()
    232 	return id, ents
    233 }
    234 
    235 // glob searches for files matching pattern in the directory dir
    236 // and appends them to matches. ignore I/O errors.
    237 func (c *fsCacheT) glob(dir, pattern string, matches []string) ([]string, error) {
    238 	_, ents := c.readdir(filepathClean(dir), unknownFileid)
    239 	switch dir {
    240 	case "", string(filepath.Separator):
    241 		// nothing
    242 	default:
    243 		dir += string(filepath.Separator) // add trailing separator back
    244 	}
    245 	for _, ent := range ents {
    246 		matched, err := filepath.Match(pattern, ent.name)
    247 		if err != nil {
    248 			return nil, err
    249 		}
    250 		if matched {
    251 			matches = append(matches, dir+ent.name)
    252 		}
    253 	}
    254 	return matches, nil
    255 }
    256 
    257 func (c *fsCacheT) Glob(pat string) ([]string, error) {
    258 	// TODO(ukai): expand ~ to user's home directory.
    259 	// TODO(ukai): use find cache for glob if exists
    260 	// or use wildcardCache for find cache.
    261 	pat = wildcardUnescape(pat)
    262 	dir, file := filepath.Split(pat)
    263 	switch dir {
    264 	case "", string(filepath.Separator):
    265 		// nothing
    266 	default:
    267 		dir = dir[:len(dir)-1] // chop off trailing separator
    268 	}
    269 	if !hasWildcardMeta(dir) {
    270 		return c.glob(dir, file, nil)
    271 	}
    272 
    273 	m, err := c.Glob(dir)
    274 	if err != nil {
    275 		return nil, err
    276 	}
    277 	var matches []string
    278 	for _, d := range m {
    279 		matches, err = c.glob(d, file, matches)
    280 		if err != nil {
    281 			return nil, err
    282 		}
    283 	}
    284 	return matches, nil
    285 }
    286 
    287 func wildcard(w evalWriter, pat string) error {
    288 	files, err := fsCache.Glob(pat)
    289 	if err != nil {
    290 		return err
    291 	}
    292 	for _, file := range files {
    293 		w.writeWordString(file)
    294 	}
    295 	return nil
    296 }
    297 
    298 type findOp interface {
    299 	apply(evalWriter, string, dirent) (test bool, prune bool)
    300 }
    301 
    302 type findOpName string
    303 
    304 func (op findOpName) apply(w evalWriter, path string, ent dirent) (bool, bool) {
    305 	matched, err := filepath.Match(string(op), ent.name)
    306 	if err != nil {
    307 		glog.Warningf("find -name %q: %v", string(op), err)
    308 		return false, false
    309 	}
    310 	return matched, false
    311 }
    312 
    313 type findOpType struct {
    314 	mode           os.FileMode
    315 	followSymlinks bool
    316 }
    317 
    318 func (op findOpType) apply(w evalWriter, path string, ent dirent) (bool, bool) {
    319 	mode := ent.lmode
    320 	if op.followSymlinks && ent.mode != 0 {
    321 		mode = ent.mode
    322 	}
    323 	return op.mode&mode == op.mode, false
    324 }
    325 
    326 type findOpRegular struct {
    327 	followSymlinks bool
    328 }
    329 
    330 func (op findOpRegular) apply(w evalWriter, path string, ent dirent) (bool, bool) {
    331 	mode := ent.lmode
    332 	if op.followSymlinks && ent.mode != 0 {
    333 		mode = ent.mode
    334 	}
    335 	return mode.IsRegular(), false
    336 }
    337 
    338 type findOpNot struct {
    339 	op findOp
    340 }
    341 
    342 func (op findOpNot) apply(w evalWriter, path string, ent dirent) (bool, bool) {
    343 	test, prune := op.op.apply(w, path, ent)
    344 	return !test, prune
    345 }
    346 
    347 type findOpAnd []findOp
    348 
    349 func (op findOpAnd) apply(w evalWriter, path string, ent dirent) (bool, bool) {
    350 	var prune bool
    351 	for _, o := range op {
    352 		test, p := o.apply(w, path, ent)
    353 		if p {
    354 			prune = true
    355 		}
    356 		if !test {
    357 			return test, prune
    358 		}
    359 	}
    360 	return true, prune
    361 }
    362 
    363 type findOpOr struct {
    364 	op1, op2 findOp
    365 }
    366 
    367 func (op findOpOr) apply(w evalWriter, path string, ent dirent) (bool, bool) {
    368 	test, prune := op.op1.apply(w, path, ent)
    369 	if test {
    370 		return test, prune
    371 	}
    372 	return op.op2.apply(w, path, ent)
    373 }
    374 
    375 type findOpPrune struct{}
    376 
    377 func (op findOpPrune) apply(w evalWriter, path string, ent dirent) (bool, bool) {
    378 	return true, true
    379 }
    380 
    381 type findOpPrint struct{}
    382 
    383 func (op findOpPrint) apply(w evalWriter, path string, ent dirent) (bool, bool) {
    384 	var name string
    385 	if path == "" {
    386 		name = ent.name
    387 	} else if ent.name == "." {
    388 		name = path
    389 	} else {
    390 		name = filepathJoin(path, ent.name)
    391 	}
    392 	glog.V(3).Infof("find print: %s", name)
    393 	w.writeWordString(name)
    394 	return true, false
    395 }
    396 
    397 func (c *fsCacheT) find(w evalWriter, fc findCommand, path string, id fileid, depth int, seen map[fileid]string) {
    398 	glog.V(2).Infof("find: path:%s id:%v depth:%d", path, id, depth)
    399 	id, ents := c.readdir(filepathClean(filepathJoin(fc.chdir, path)), id)
    400 	if ents == nil {
    401 		glog.V(1).Infof("find: %s %s not found", fc.chdir, path)
    402 		return
    403 	}
    404 	for _, ent := range ents {
    405 		glog.V(3).Infof("find: path:%s ent:%s depth:%d", path, ent.name, depth)
    406 		_, prune := fc.apply(w, path, ent)
    407 		mode := ent.lmode
    408 		if fc.followSymlinks {
    409 			if mode&os.ModeSymlink == os.ModeSymlink {
    410 				lpath := filepathJoin(path, ent.name)
    411 				if p, ok := seen[ent.id]; ok {
    412 					// stderr?
    413 					glog.Errorf("find: File system loop detected; `%s' is part of the same file system loop as `%s'.", lpath, p)
    414 					return
    415 				}
    416 				seen[ent.id] = lpath
    417 			}
    418 			mode = ent.mode
    419 		}
    420 		if !mode.IsDir() {
    421 			glog.V(3).Infof("find: not dir: %s/%s", path, ent.name)
    422 			continue
    423 		}
    424 		if prune {
    425 			glog.V(3).Infof("find: prune: %s", path)
    426 			continue
    427 		}
    428 		if depth >= fc.depth {
    429 			glog.V(3).Infof("find: depth: %d >= %d", depth, fc.depth)
    430 			continue
    431 		}
    432 		c.find(w, fc, filepathJoin(path, ent.name), ent.id, depth+1, seen)
    433 	}
    434 }
    435 
    436 type findCommand struct {
    437 	testdir        string // before chdir
    438 	chdir          string
    439 	finddirs       []string // after chdir
    440 	followSymlinks bool
    441 	ops            []findOp
    442 	depth          int
    443 }
    444 
    445 func parseFindCommand(cmd string) (findCommand, error) {
    446 	if !strings.Contains(cmd, "find") {
    447 		return findCommand{}, errNotFind
    448 	}
    449 	fcp := findCommandParser{
    450 		shellParser: shellParser{
    451 			cmd: cmd,
    452 		},
    453 	}
    454 	err := fcp.parse()
    455 	if err != nil {
    456 		return fcp.fc, err
    457 	}
    458 	if len(fcp.fc.finddirs) == 0 {
    459 		fcp.fc.finddirs = append(fcp.fc.finddirs, ".")
    460 	}
    461 	if fcp.fc.chdir != "" {
    462 		fcp.fc.chdir = filepathClean(fcp.fc.chdir)
    463 	}
    464 	if filepath.IsAbs(fcp.fc.chdir) {
    465 		return fcp.fc, errFindAbspath
    466 	}
    467 	for _, dir := range fcp.fc.finddirs {
    468 		if filepath.IsAbs(dir) {
    469 			return fcp.fc, errFindAbspath
    470 		}
    471 	}
    472 	glog.V(3).Infof("find command: %#v", fcp.fc)
    473 
    474 	// TODO(ukai): handle this in run() instead of fallback shell.
    475 	_, ents := fsCache.readdir(filepathClean(fcp.fc.testdir), unknownFileid)
    476 	if ents == nil {
    477 		glog.V(1).Infof("find: testdir %s - not dir", fcp.fc.testdir)
    478 		return fcp.fc, errFindNoSuchDir
    479 	}
    480 	_, ents = fsCache.readdir(filepathClean(fcp.fc.chdir), unknownFileid)
    481 	if ents == nil {
    482 		glog.V(1).Infof("find: cd %s: No such file or directory", fcp.fc.chdir)
    483 		return fcp.fc, errFindNoSuchDir
    484 	}
    485 
    486 	return fcp.fc, nil
    487 }
    488 
    489 func (fc findCommand) run(w evalWriter) {
    490 	glog.V(3).Infof("find: %#v", fc)
    491 	for _, dir := range fc.finddirs {
    492 		seen := make(map[fileid]string)
    493 		id, _ := fsCache.readdir(filepathClean(filepathJoin(fc.chdir, dir)), unknownFileid)
    494 		_, prune := fc.apply(w, dir, dirent{id: id, name: ".", mode: os.ModeDir, lmode: os.ModeDir})
    495 		if prune {
    496 			glog.V(3).Infof("find: prune: %s", dir)
    497 			continue
    498 		}
    499 		if 0 >= fc.depth {
    500 			glog.V(3).Infof("find: depth: 0 >= %d", fc.depth)
    501 			continue
    502 		}
    503 		fsCache.find(w, fc, dir, id, 1, seen)
    504 	}
    505 }
    506 
    507 func (fc findCommand) apply(w evalWriter, path string, ent dirent) (test, prune bool) {
    508 	var p bool
    509 	for _, op := range fc.ops {
    510 		test, p = op.apply(w, path, ent)
    511 		if p {
    512 			prune = true
    513 		}
    514 		if !test {
    515 			break
    516 		}
    517 	}
    518 	glog.V(2).Infof("apply path:%s ent:%v => test=%t, prune=%t", path, ent, test, prune)
    519 	return test, prune
    520 }
    521 
    522 var (
    523 	errNotFind             = errors.New("not find command")
    524 	errFindBackground      = errors.New("find command: background")
    525 	errFindUnbalancedQuote = errors.New("find command: unbalanced quote")
    526 	errFindDupChdir        = errors.New("find command: dup chdir")
    527 	errFindDupTestdir      = errors.New("find command: dup testdir")
    528 	errFindExtra           = errors.New("find command: extra")
    529 	errFindUnexpectedEnd   = errors.New("find command: unexpected end")
    530 	errFindAbspath         = errors.New("find command: abs path")
    531 	errFindNoSuchDir       = errors.New("find command: no such dir")
    532 )
    533 
    534 type findCommandParser struct {
    535 	fc findCommand
    536 	shellParser
    537 }
    538 
    539 func (p *findCommandParser) parse() error {
    540 	p.fc.depth = 1<<31 - 1 // max int32
    541 	var hasIf bool
    542 	var hasFind bool
    543 	for {
    544 		tok, err := p.token()
    545 		if err == io.EOF || tok == "" {
    546 			if !hasFind {
    547 				return errNotFind
    548 			}
    549 			return nil
    550 		}
    551 		if err != nil {
    552 			return err
    553 		}
    554 		switch tok {
    555 		case "cd":
    556 			if p.fc.chdir != "" {
    557 				return errFindDupChdir
    558 			}
    559 			p.fc.chdir, err = p.token()
    560 			if err != nil {
    561 				return err
    562 			}
    563 			err = p.expect(";", "&&")
    564 			if err != nil {
    565 				return err
    566 			}
    567 		case "if":
    568 			err = p.expect("[")
    569 			if err != nil {
    570 				return err
    571 			}
    572 			if hasIf {
    573 				return errFindDupTestdir
    574 			}
    575 			err = p.parseTest()
    576 			if err != nil {
    577 				return err
    578 			}
    579 			err = p.expectSeq("]", ";", "then")
    580 			if err != nil {
    581 				return err
    582 			}
    583 			hasIf = true
    584 		case "test":
    585 			if hasIf {
    586 				return errFindDupTestdir
    587 			}
    588 			err = p.parseTest()
    589 			if err != nil {
    590 				return err
    591 			}
    592 			err = p.expect("&&")
    593 			if err != nil {
    594 				return err
    595 			}
    596 		case "find":
    597 			err = p.parseFind()
    598 			if err != nil {
    599 				return err
    600 			}
    601 			if hasIf {
    602 				err = p.expect("fi")
    603 				if err != nil {
    604 					return err
    605 				}
    606 			}
    607 			tok, err = p.token()
    608 			if err != io.EOF || tok != "" {
    609 				return errFindExtra
    610 			}
    611 			hasFind = true
    612 			return nil
    613 		}
    614 	}
    615 }
    616 
    617 func (p *findCommandParser) parseTest() error {
    618 	if p.fc.testdir != "" {
    619 		return errFindDupTestdir
    620 	}
    621 	err := p.expect("-d")
    622 	if err != nil {
    623 		return err
    624 	}
    625 	p.fc.testdir, err = p.token()
    626 	return err
    627 }
    628 
    629 func (p *findCommandParser) parseFind() error {
    630 	for {
    631 		tok, err := p.token()
    632 		if err == io.EOF || tok == "" || tok == ";" {
    633 			var print findOpPrint
    634 			if len(p.fc.ops) == 0 || p.fc.ops[len(p.fc.ops)-1] != print {
    635 				p.fc.ops = append(p.fc.ops, print)
    636 			}
    637 			return nil
    638 		}
    639 		if err != nil {
    640 			return err
    641 		}
    642 		if tok != "" && (tok[0] == '-' || tok == "\\(") {
    643 			p.unget(tok)
    644 			op, err := p.parseFindCond()
    645 			if err != nil {
    646 				return err
    647 			}
    648 			if op != nil {
    649 				p.fc.ops = append(p.fc.ops, op)
    650 			}
    651 			continue
    652 		}
    653 		p.fc.finddirs = append(p.fc.finddirs, tok)
    654 	}
    655 }
    656 
    657 func (p *findCommandParser) parseFindCond() (findOp, error) {
    658 	return p.parseExpr()
    659 }
    660 
    661 func (p *findCommandParser) parseExpr() (findOp, error) {
    662 	op, err := p.parseTerm()
    663 	if err != nil {
    664 		return nil, err
    665 	}
    666 	if op == nil {
    667 		return nil, nil
    668 	}
    669 	for {
    670 		tok, err := p.token()
    671 		if err == io.EOF || tok == "" {
    672 			return op, nil
    673 		}
    674 		if err != nil {
    675 			return nil, err
    676 		}
    677 		if tok != "-or" && tok != "-o" {
    678 			p.unget(tok)
    679 			return op, nil
    680 		}
    681 		op2, err := p.parseTerm()
    682 		if err != nil {
    683 			return nil, err
    684 		}
    685 		op = findOpOr{op, op2}
    686 	}
    687 }
    688 
    689 func (p *findCommandParser) parseTerm() (findOp, error) {
    690 	op, err := p.parseFact()
    691 	if err != nil {
    692 		return nil, err
    693 	}
    694 	if op == nil {
    695 		return nil, nil
    696 	}
    697 	var ops []findOp
    698 	ops = append(ops, op)
    699 	for {
    700 		tok, err := p.token()
    701 		if err == io.EOF || tok == "" {
    702 			if len(ops) == 1 {
    703 				return ops[0], nil
    704 			}
    705 			return findOpAnd(ops), nil
    706 		}
    707 		if err != nil {
    708 			return nil, err
    709 		}
    710 		if tok != "-and" && tok != "-a" {
    711 			p.unget(tok)
    712 		}
    713 		op, err = p.parseFact()
    714 		if err != nil {
    715 			return nil, err
    716 		}
    717 		if op == nil {
    718 			if len(ops) == 1 {
    719 				return ops[0], nil
    720 			}
    721 			return findOpAnd(ops), nil
    722 		}
    723 		ops = append(ops, op) // findAndOp?
    724 	}
    725 }
    726 
    727 func (p *findCommandParser) parseFact() (findOp, error) {
    728 	tok, err := p.token()
    729 	if err != nil {
    730 		return nil, err
    731 	}
    732 	switch tok {
    733 	case "-L":
    734 		p.fc.followSymlinks = true
    735 		return nil, nil
    736 	case "-prune":
    737 		return findOpPrune{}, nil
    738 	case "-print":
    739 		return findOpPrint{}, nil
    740 	case "-maxdepth":
    741 		tok, err = p.token()
    742 		if err != nil {
    743 			return nil, err
    744 		}
    745 		i, err := strconv.ParseInt(tok, 10, 32)
    746 		if err != nil {
    747 			return nil, err
    748 		}
    749 		if i < 0 {
    750 			return nil, fmt.Errorf("find commnad: -maxdepth negative: %d", i)
    751 		}
    752 		p.fc.depth = int(i)
    753 		return nil, nil
    754 	case "-not", "\\!":
    755 		op, err := p.parseFact()
    756 		if err != nil {
    757 			return nil, err
    758 		}
    759 		return findOpNot{op}, nil
    760 	case "\\(":
    761 		op, err := p.parseExpr()
    762 		if err != nil {
    763 			return nil, err
    764 		}
    765 		err = p.expect("\\)")
    766 		if err != nil {
    767 			return nil, err
    768 		}
    769 		return op, nil
    770 	case "-name":
    771 		tok, err = p.token()
    772 		if err != nil {
    773 			return nil, err
    774 		}
    775 		return findOpName(tok), nil
    776 	case "-type":
    777 		tok, err = p.token()
    778 		if err != nil {
    779 			return nil, err
    780 		}
    781 		var m os.FileMode
    782 		switch tok {
    783 		case "b":
    784 			m = os.ModeDevice
    785 		case "c":
    786 			m = os.ModeDevice | os.ModeCharDevice
    787 		case "d":
    788 			m = os.ModeDir
    789 		case "p":
    790 			m = os.ModeNamedPipe
    791 		case "l":
    792 			m = os.ModeSymlink
    793 		case "f":
    794 			return findOpRegular{p.fc.followSymlinks}, nil
    795 		case "s":
    796 			m = os.ModeSocket
    797 		default:
    798 			return nil, fmt.Errorf("find command: unsupported -type %s", tok)
    799 		}
    800 		return findOpType{m, p.fc.followSymlinks}, nil
    801 	case "-o", "-or", "-a", "-and":
    802 		p.unget(tok)
    803 		return nil, nil
    804 	default:
    805 		if tok != "" && tok[0] == '-' {
    806 			return nil, fmt.Errorf("find command: unsupported %s", tok)
    807 		}
    808 		p.unget(tok)
    809 		return nil, nil
    810 	}
    811 }
    812 
    813 type findleavesCommand struct {
    814 	name     string
    815 	dirs     []string
    816 	prunes   []string
    817 	mindepth int
    818 }
    819 
    820 func parseFindleavesCommand(cmd string) (findleavesCommand, error) {
    821 	if !strings.Contains(cmd, "build/tools/findleaves.py") {
    822 		return findleavesCommand{}, errNotFindleaves
    823 	}
    824 	fcp := findleavesCommandParser{
    825 		shellParser: shellParser{
    826 			cmd: cmd,
    827 		},
    828 	}
    829 	err := fcp.parse()
    830 	if err != nil {
    831 		return fcp.fc, err
    832 	}
    833 	glog.V(3).Infof("findleaves command: %#v", fcp.fc)
    834 	return fcp.fc, nil
    835 }
    836 
    837 func (fc findleavesCommand) run(w evalWriter) {
    838 	glog.V(3).Infof("findleaves: %#v", fc)
    839 	for _, dir := range fc.dirs {
    840 		seen := make(map[fileid]string)
    841 		id, _ := fsCache.readdir(filepathClean(dir), unknownFileid)
    842 		fc.walk(w, dir, id, 1, seen)
    843 	}
    844 }
    845 
    846 func (fc findleavesCommand) walk(w evalWriter, dir string, id fileid, depth int, seen map[fileid]string) {
    847 	glog.V(3).Infof("findleaves walk: dir:%d id:%v depth:%d", dir, id, depth)
    848 	id, ents := fsCache.readdir(filepathClean(dir), id)
    849 	var subdirs []dirent
    850 	for _, ent := range ents {
    851 		if ent.mode.IsDir() {
    852 			if fc.isPrune(ent.name) {
    853 				glog.V(3).Infof("findleaves prune %s in %s", ent.name, dir)
    854 				continue
    855 			}
    856 			subdirs = append(subdirs, ent)
    857 			continue
    858 		}
    859 		if depth < fc.mindepth {
    860 			glog.V(3).Infof("findleaves depth=%d mindepth=%d", depth, fc.mindepth)
    861 			continue
    862 		}
    863 		if ent.name == fc.name {
    864 			glog.V(2).Infof("findleaves %s in %s", ent.name, dir)
    865 			w.writeWordString(filepathJoin(dir, ent.name))
    866 			// no recurse subdirs
    867 			return
    868 		}
    869 	}
    870 	for _, subdir := range subdirs {
    871 		if subdir.lmode&os.ModeSymlink == os.ModeSymlink {
    872 			lpath := filepathJoin(dir, subdir.name)
    873 			if p, ok := seen[subdir.id]; ok {
    874 				// symlink loop detected.
    875 				glog.Errorf("findleaves: loop detected %q was %q", lpath, p)
    876 				continue
    877 			}
    878 			seen[subdir.id] = lpath
    879 		}
    880 		fc.walk(w, filepathJoin(dir, subdir.name), subdir.id, depth+1, seen)
    881 	}
    882 }
    883 
    884 func (fc findleavesCommand) isPrune(name string) bool {
    885 	for _, p := range fc.prunes {
    886 		if p == name {
    887 			return true
    888 		}
    889 	}
    890 	return false
    891 }
    892 
    893 var (
    894 	errNotFindleaves        = errors.New("not findleaves command")
    895 	errFindleavesEmptyPrune = errors.New("findleaves: empty prune")
    896 	errFindleavesNoFilename = errors.New("findleaves: no filename")
    897 )
    898 
    899 type findleavesCommandParser struct {
    900 	fc findleavesCommand
    901 	shellParser
    902 }
    903 
    904 func (p *findleavesCommandParser) parse() error {
    905 	var args []string
    906 	p.fc.mindepth = -1
    907 	tok, err := p.token()
    908 	if err != nil {
    909 		return err
    910 	}
    911 	if tok != "build/tools/findleaves.py" {
    912 		return errNotFindleaves
    913 	}
    914 	for {
    915 		tok, err := p.token()
    916 		if err == io.EOF || tok == "" {
    917 			break
    918 		}
    919 		if err != nil {
    920 			return err
    921 		}
    922 		switch {
    923 		case strings.HasPrefix(tok, "--prune="):
    924 			prune := filepath.Base(strings.TrimPrefix(tok, "--prune="))
    925 			if prune == "" {
    926 				return errFindleavesEmptyPrune
    927 			}
    928 			p.fc.prunes = append(p.fc.prunes, prune)
    929 		case strings.HasPrefix(tok, "--mindepth="):
    930 			md := strings.TrimPrefix(tok, "--mindepth=")
    931 			i, err := strconv.ParseInt(md, 10, 32)
    932 			if err != nil {
    933 				return err
    934 			}
    935 			p.fc.mindepth = int(i)
    936 		default:
    937 			args = append(args, tok)
    938 		}
    939 	}
    940 	if len(args) < 2 {
    941 		return errFindleavesNoFilename
    942 	}
    943 	p.fc.dirs, p.fc.name = args[:len(args)-1], args[len(args)-1]
    944 	return nil
    945 }
    946