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
15package kati
16
17import (
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
32type fileid struct {
33	dev, ino uint64
34}
35
36var (
37	unknownFileid = fileid{}
38	invalidFileid = fileid{dev: 1<<64 - 1, ino: 1<<64 - 1}
39)
40
41type 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
49type fsCacheT struct {
50	mu      sync.Mutex
51	ids     map[string]fileid
52	dirents map[fileid][]dirent
53}
54
55var fsCache = &fsCacheT{
56	ids: make(map[string]fileid),
57	dirents: map[fileid][]dirent{
58		invalidFileid: nil,
59	},
60}
61
62func init() {
63	fsCache.readdir(".", unknownFileid)
64}
65
66func (c *fsCacheT) dirs() int {
67	c.mu.Lock()
68	defer c.mu.Unlock()
69	return len(c.dirents)
70}
71
72func (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
82func hasWildcardMeta(pat string) bool {
83	return strings.IndexAny(pat, "*?[") >= 0
84}
85
86func hasWildcardMetaByte(pat []byte) bool {
87	return bytes.IndexAny(pat, "*?[") >= 0
88}
89
90func 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
105func 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
116func 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))
122Loop:
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
159func (c *fsCacheT) fileid(dir string) fileid {
160	c.mu.Lock()
161	id := c.ids[dir]
162	c.mu.Unlock()
163	return id
164}
165
166func (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: 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: 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: 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.
237func (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
257func (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
287func 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
298type findOp interface {
299	apply(evalWriter, string, dirent) (test bool, prune bool)
300}
301
302type findOpName string
303
304func (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
313type findOpType struct {
314	mode           os.FileMode
315	followSymlinks bool
316}
317
318func (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
326type findOpRegular struct {
327	followSymlinks bool
328}
329
330func (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
338type findOpNot struct {
339	op findOp
340}
341
342func (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
347type findOpAnd []findOp
348
349func (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
363type findOpOr struct {
364	op1, op2 findOp
365}
366
367func (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
375type findOpPrune struct{}
376
377func (op findOpPrune) apply(w evalWriter, path string, ent dirent) (bool, bool) {
378	return true, true
379}
380
381type findOpPrint struct{}
382
383func (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
397func (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
436type 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
445func 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
489func (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
507func (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
522var (
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
534type findCommandParser struct {
535	fc findCommand
536	shellParser
537}
538
539func (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
617func (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
629func (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
657func (p *findCommandParser) parseFindCond() (findOp, error) {
658	return p.parseExpr()
659}
660
661func (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
689func (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
727func (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
813type findleavesCommand struct {
814	name     string
815	dirs     []string
816	prunes   []string
817	mindepth int
818}
819
820func 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
837func (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
846func (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
884func (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
893var (
894	errNotFindleaves        = errors.New("not findleaves command")
895	errFindleavesEmptyPrune = errors.New("findleaves: empty prune")
896	errFindleavesNoFilename = errors.New("findleaves: no filename")
897)
898
899type findleavesCommandParser struct {
900	fc findleavesCommand
901	shellParser
902}
903
904func (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