find コマンドをGoで作成してみた

概要

ファイル検索を行う find コマンドに近いインターフェースの cli である fing を作成しました。
https://github.com/komem3/fing

モチベーション

find コマンドをよく使うのですがいかんせん遅いです。Rust製の fd などもありますが、あちらは find とインターフェースが全く違うのが何か嫌です。
ということで、Go には fs.WalkDirもありますし並列処理も得意なので自分でfindコマンドを作成しました。

使い方

ということで、まずはツールの紹介です。といっても使用感は find とほとんど同じです。option や引数の指定方法など可能な限り find に寄せています。
以下が-hの出力結果です。

Usage: fing [staring-point...] [flag] [expression]

Fing is a fast file finder that provides an interface similar to find.

flags are:
  -I
    Ignore files in .gitignore.
  -dry
    Only output parse result of expression.
    If this option is specified, the file will not be searched.
  -maxdepth
    The depth to search.
    Unlike find, it can be specified at the same time as prune.

expression are:
  -a -and
    This flag is skipped.
  -empty
    Search emptry file and directory.
    This is shothand of '-size 0c'.
  -executable
    Match files which are executable by current user.
  -iname string
    Like -name, but the match is case insensitive.
  -ipath string
    Like -path, but the match is case insensitive.
  -iregex string
    Like -regex, but the match is case insensitive.
  -irname string
    Like -rname, but the match is case insensitive.
  -name string
    Search for files using glob expressions.
    This option match only to file name.
  -not
    True if next expression false.
  -o -or
    Evaluate the previous and next expressions with or.
  -path string
    Search for files using wildcard expressions.
    This option match to file path.
    Unlike find, This option explicitly matched by using one or more <slash>.
  -prune
    Prunes directory that match before expressions.
  -regex string
    Search for files using regular expressions.
    This option match to file path.
  -rname string
    Search for files using regular expressions.
    This option match only to file name.
  -size [+|-]n[ckMG]
    The size of file. Should specify the unit of size.
    c(for bytes), k(for KiB), M(for MiB), G(for Gib).
  -type string
    File is type.
    Support file(f), directory(d), named piep(p) and socket(s).

例えば find コマンドで拡張子が jpg のファイルを探すときは以下のように書きます。

find -name "*.jpg"

fing の場合は以下のように書きます

fing -name "*.jpg"

find を fing にしただけです。find に慣れていれば簡単ですね。

また、fd コマンドで便利な .gitignore に書かれているものを無視するというのも便利なのでサポートしています。以下のように書きます。

fing -I -name "*.jpg"

fd の -I オプションの逆ですね。あちらはデフォルトで .gitignore の中身を無視する挙動で、-Iをつけることで、.gitignore のファイルを適用しなくなります。fing はあくまで find と同じ出力になることを意識しているため、デフォルトでは適用されずオプションで指定するようにしています。

---

find はあまりにも多くのオプションをサポートしているため、全てを網羅することはさすがに考えていません。ですが、基本的なユースケースは互換が効くようにしたいと考えています。

苦労した点

ただの自慢（？）もあれなのでここからは苦労した点という個人の感想です。ポエム記事にしていきましょう。

goroutine 多くなりすぎる問題

当初ファイルの検索と並列処理ということで以下のようなプログラムを作成してました。

func (w *Walker) walk(path string, ignores ignores) {
// ...
	if info.IsDir() {
		w.wg.Add(1)
		go func() {
			w.walk(path, ignores)
			w.wg.Done()
		}()
	}

このプログラムはディレクトリ数が少ないと高速ですが、ディレクトリ数が増えると途端に速度が遅くなりました。goroutine が大量に作られて遅くなっていることはわかったのですが、この簡単な再帰を諦めるのは悲しみでした。

結局幅優先探索で行うことにしました。各階層ごとに見つけたディレクトリは全て保存しておいて、その階層以下のディレクトリがある限り探索を行うイメージです。幅優先探索なら並列に実行する数を絞れたので問題も解決しました。

walker := &Walker{
		concurrency: make(chan struct{}, concurrencyMax),
	}
// ...
for i := range targets {
	w.wg.Add(1)
	w.concurrency <- struct{}{} // 並列に実行する数を絞っている
	go func(target *direcotryInfo) {
		w.walk(target.path, target.ignore)
		<-w.concurrency
		w.wg.Done()
	}(targes[i])
}
w.wg.Wait()

// walk 内
if info.IsDir() {
	w.dirMux.Lock()
	w.targets = append(w.targets, &direcotryInfo{path: path})
	w.dirMux.UnLock()
}

これでそこそこパフォーマンスは改善されました。

globない問題

find といったら glob マッチなのに、Go にそもそも glob がないことに困りました。filepath.Match は shell などでファイル名を展開するときのパターンマッチングであり、find で使用されるものとは異なっています。
実際 IEEE Std 1003.1-2017 の find にも以下のように書かれています。

-name pattern
The primary shall evaluate as true if the basename of the current pathname matches pattern using the pattern matching notation described in Pattern Matching Notation. The additional rules in Patterns Used for Filename Expansion do not apply as this is a matching operation, not an expansion.

このため諦めようかと思いましたが、年末年始だったので自分で実装しちゃいました。実際に作成したものは以下です。

https://github.com/komem3/glob

苦労したポイントというか、fing より手間がかかっています。この辺で、findコマンドにここまでやる必要があるか怪しくなってきています。

書き込みが遅く見える

これは bufio.Buffer を使用して最後に os.Stdout にまとめて書き込んでいたたのが原因でした。全てのディレクトリの精査が終わるまで出力されないため、いくらプログラムが早くても出力がないと何か遅く感じます。一瞬止まって一気に出力されるより、だらだら出力してる方が体感早く感じるんですから不思議なものです。
さすがに直で sdout に書き込むと遅すぎたのでちょっと工夫しました。体感ずっと書き込まれているように感じればいいので、定期的に flush するようにしました。

ch := make(chan struct{}, 1)
ticker := time.NewTicker(time.Millisecond)
go func() {
	walker.Walk(paths)
	walker.Wait()
	ch <- struct{}{}
}()
for end := false; !end; {
	select {
	case <-ch:
		end = true
	case <-ticker.C:
		walker.Flush()
	}
}
walker.Flush()

flush するようにしたことにより、体感も早くなりましたが、buffer への書き込みでメモリが使い回されるようになったため、普通に早くなりました。棚ぽたです。

まとめ

ということで、自作の find コマンド fing の話でした。個人的に使用する上で高速で使いやすくて満足しています。

余談ですが、僕は普段 emacs を使用しており、affe という fuzzy finder でファイル検索をしています。affe はファイル取得のコマンドを変更できるため以下のようにコマンドを変更しています。

(setq affe-find-command "fing -rname \\.git|tmp|vendor|node_modules -prune -type f")

.gitignore に入れてるけど検索には表示したいファイルがあるため上記のようにやっています。find であろうと fd であろうと同様のことはできるのですが、自分で作成したものは融通が効くのでいいですね。