Replace "default find command" with built-in directory traversal

9 files changed, 57 insertions, 82 deletions

diff --git a/BUILD.md b/BUILD.md
index af0a04e9..18630e14 100644
--- a/BUILD.md
+++ b/BUILD.md
@@ -42,6 +42,8 @@ Third-party libraries used
     - Licensed under [MIT](http://mattn.mit-license.org)
 - [tcell](https://github.com/gdamore/tcell)
     - Licensed under [Apache License 2.0](https://github.com/gdamore/tcell/blob/master/LICENSE)
+- [fastwalk](https://github.com/charlievieth/fastwalk)
+    - Licensed under [MIT](https://raw.githubusercontent.com/charlievieth/fastwalk/master/LICENSE)
 
 License
 -------
diff --git a/CHANGELOG.md b/CHANGELOG.md
index bf619c58..f94f6baf 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,6 +1,20 @@
 CHANGELOG
 =========
 
+0.47.0
+------
+- Replaced ["the default find command"][find] with a built-in directory traversal to simplify the code and to achieve better performance and consistent behavior across platforms.
+  This doesn't affect you if you have `$FZF_DEFAULT_COMMAND` set.
+    - Breaking changes:
+        - Unlike [the previous "find" command][find], the new traversal code will list hidden files, but hidden directories will still be ignored
+        - No filtering of `devtmpfs` or `proc` types
+        - Traversal is parallelized, so the order of the entries will be different each time
+    - You would wonder why fzf implements directory traversal anyway when it's a filter program following the Unix philosophy.
+      But fzf has had [the traversal code for years][walker] to tackle the performance problem on Windows. And I decided to use the same approach on different platforms as well for the benefits listed above.
+
+[find]: https://github.com/junegunn/fzf/blob/0.46.1/src/constants.go#L60-L64
+[walker]: https://github.com/junegunn/fzf/pull/1847
+
 0.46.1
 ------
 - Bug fixes and improvements
diff --git a/README-VIM.md b/README-VIM.md
index e02a97f6..6751d25a 100644
--- a/README-VIM.md
+++ b/README-VIM.md
@@ -238,19 +238,20 @@ call fzf#run({'sink': 'e'})
 ```
 
 We haven't specified the `source`, so this is equivalent to starting fzf on
-command line without standard input pipe; fzf will use find command (or
-`$FZF_DEFAULT_COMMAND` if defined) to list the files under the current
-directory. When you select one, it will open it with the sink, `:e` command.
-If you want to open it in a new tab, you can pass `:tabedit` command instead
-as the sink.
+command line without standard input pipe; fzf will traverse the file system
+under the current directory to get the list of files. (If
+`$FZF_DEFAULT_COMMAND` is set, fzf will use the output of the command
+instead.) When you select one, it will open it with the sink, `:e` command. If
+you want to open it in a new tab, you can pass `:tabedit` command instead as
+the sink.
 
 ```vim
 call fzf#run({'sink': 'tabedit'})
 ```
 
-Instead of using the default find command, you can use any shell command as
-the source. The following example will list the files managed by git. It's
-equivalent to running `git ls-files | fzf` on shell.
+You can use any shell command as the source to generate the list. The
+following example will list the files managed by git. It's equivalent to
+running `git ls-files | fzf` on shell.
 
 ```vim
 call fzf#run({'source': 'git ls-files', 'sink': 'e'})
diff --git a/README.md b/README.md
index df22120c..626973f5 100644
--- a/README.md
+++ b/README.md
@@ -230,9 +230,9 @@ selected item to STDOUT.
 find * -type f | fzf > selected
 ```
 
-Without STDIN pipe, fzf will use find command to fetch the list of
-files excluding hidden ones. (You can override the default command with
-`FZF_DEFAULT_COMMAND`)
+Without STDIN pipe, fzf will traverse the file system under the current
+directory to get the list of files, skipping hidden directories. (You can
+override the default behavior with `FZF_DEFAULT_COMMAND`)
 
 ```sh
 vim $(fzf)
@@ -488,8 +488,7 @@ export FZF_COMPLETION_TRIGGER='~~'
 # Options to fzf command
 export FZF_COMPLETION_OPTS='--border --info=inline'
 
-# Use fd (https://github.com/sharkdp/fd) instead of the default find
-# command for listing path candidates.
+# Use fd (https://github.com/sharkdp/fd) for listing path candidates.
 # - The first argument to the function ($1) is the base path to start traversal
 # - See the source code (completion.{bash,zsh}) for the details.
 _fzf_compgen_path() {
@@ -774,9 +773,8 @@ Tips
 
 You can use [fd](https://github.com/sharkdp/fd),
 [ripgrep](https://github.com/BurntSushi/ripgrep), or [the silver
-searcher](https://github.com/ggreer/the_silver_searcher) instead of the
-default find command to traverse the file system while respecting
-`.gitignore`.
+searcher](https://github.com/ggreer/the_silver_searcher) to traverse the file
+system while respecting `.gitignore`.
 
 ```sh
 # Feed the output of fd into fzf
diff --git a/doc/fzf.txt b/doc/fzf.txt
index 607637e7..cf8c6af3 100644
--- a/doc/fzf.txt
+++ b/doc/fzf.txt
@@ -1,4 +1,4 @@
-fzf.txt	fzf	Last change: January 1 2024
+fzf.txt	fzf	Last change: February 15 2024
 FZF - TABLE OF CONTENTS                                            *fzf* *fzf-toc*
 ==============================================================================
 
@@ -264,17 +264,18 @@ entry.
     call fzf#run({'sink': 'e'})
 <
 We haven't specified the `source`, so this is equivalent to starting fzf on
-command line without standard input pipe; fzf will use find command (or
-`$FZF_DEFAULT_COMMAND` if defined) to list the files under the current
-directory. When you select one, it will open it with the sink, `:e` command.
-If you want to open it in a new tab, you can pass `:tabedit` command instead
-as the sink.
+command line without standard input pipe; fzf will traverse the file system
+under the current directory to get the list of files. (If
+`$FZF_DEFAULT_COMMAND` is set, fzf will use the output of the command
+instead.) When you select one, it will open it with the sink, `:e` command. If
+you want to open it in a new tab, you can pass `:tabedit` command instead as
+the sink.
 >
     call fzf#run({'sink': 'tabedit'})
 <
-Instead of using the default find command, you can use any shell command as
-the source. The following example will list the files managed by git. It's
-equivalent to running `git ls-files | fzf` on shell.
+You can use any shell command as the source to generate the list. The
+following example will list the files managed by git. It's equivalent to
+running `git ls-files | fzf` on shell.
 >
     call fzf#run({'source': 'git ls-files', 'sink': 'e'})
 <
@@ -417,24 +418,12 @@ TIPS                                                                  *fzf-tips*
 < fzf inside terminal buffer >________________________________________________~
                                                     *fzf-inside-terminal-buffer*
 
-The latest versions of Vim and Neovim include builtin terminal emulator
-(`:terminal`) and fzf will start in a terminal buffer in the following cases:
-
- - On Neovim
- - On GVim
- - On Terminal Vim with a non-default layout
-   - `call fzf#run({'left': '30%'})` or `let g:fzf_layout = {'left': '30%'}`
 
 On the latest versions of Vim and Neovim, fzf will start in a terminal buffer.
 If you find the default ANSI colors to be different, consider configuring the
 colors using `g:terminal_ansi_colors` in regular Vim or `g:terminal_color_x`
 in Neovim.
 
-                   *g:terminal_color_15* *g:terminal_color_14* *g:terminal_color_13*
-*g:terminal_color_12* *g:terminal_color_11* *g:terminal_color_10* *g:terminal_color_9*
-   *g:terminal_color_8* *g:terminal_color_7* *g:terminal_color_6* *g:terminal_color_5*
-   *g:terminal_color_4* *g:terminal_color_3* *g:terminal_color_2* *g:terminal_color_1*
-                                                            *g:terminal_color_0*
 >
     " Terminal colors for seoul256 color scheme
     if has('nvim')
diff --git a/go.mod b/go.mod
index ebdad5fa..556f3753 100644
--- a/go.mod
+++ b/go.mod
@@ -1,11 +1,11 @@
 module github.com/junegunn/fzf
 
 require (
+	github.com/charlievieth/fastwalk v1.0.1
 	github.com/gdamore/tcell/v2 v2.7.0
 	github.com/mattn/go-isatty v0.0.17
 	github.com/mattn/go-shellwords v1.0.12
 	github.com/rivo/uniseg v0.4.7
-	github.com/saracen/walker v0.1.3
 	golang.org/x/sys v0.17.0
 	golang.org/x/term v0.17.0
 )
@@ -14,7 +14,6 @@ require (
 	github.com/gdamore/encoding v1.0.0 // indirect
 	github.com/lucasb-eyer/go-colorful v1.2.0 // indirect
 	github.com/mattn/go-runewidth v0.0.15 // indirect
-	golang.org/x/sync v0.5.0 // indirect
 	golang.org/x/text v0.14.0 // indirect
 )
 
diff --git a/go.sum b/go.sum
index 6d6dab26..7137dde0 100644
--- a/go.sum
+++ b/go.sum
@@ -1,7 +1,11 @@
+github.com/charlievieth/fastwalk v1.0.1 h1:jW01w8OCFdKS9JvAcnI+JHhWU/FuIEmNb24Ri9p7OVg=
+github.com/charlievieth/fastwalk v1.0.1/go.mod h1:dryXgMJyGHbMrAmmnF0/EJNBbZaihlwcNud5IuGyogU=
 github.com/gdamore/encoding v1.0.0 h1:+7OoQ1Bc6eTm5niUzBa0Ctsh6JbMW6Ra+YNuAtDBdko=
 github.com/gdamore/encoding v1.0.0/go.mod h1:alR0ol34c49FCSBLjhosxzcPHQbf2trDkoo5dl+VrEg=
 github.com/gdamore/tcell/v2 v2.7.0 h1:I5LiGTQuwrysAt1KS9wg1yFfOI3arI3ucFrxtd/xqaA=
 github.com/gdamore/tcell/v2 v2.7.0/go.mod h1:hl/KtAANGBecfIPxk+FzKvThTqI84oplgbPEmVX60b8=
+github.com/karrick/godirwalk v1.17.0 h1:b4kY7nqDdioR/6qnbHQyDvmA17u5G1cZ6J+CZXwSWoI=
+github.com/karrick/godirwalk v1.17.0/go.mod h1:j4mkqPuvaLI8mp1DroR3P6ad7cyYd4c1qeJ3RV7ULlk=
 github.com/lucasb-eyer/go-colorful v1.2.0 h1:1nnpGOrhyZZuNyfu1QjKiUICQ74+3FNCN69Aj6K7nkY=
 github.com/lucasb-eyer/go-colorful v1.2.0/go.mod h1:R4dSotOR9KMtayYi1e77YzuveK+i7ruzyGqttikkLy0=
 github.com/mattn/go-isatty v0.0.17 h1:BTarxUcIeDqL27Mc+vyvdWYSL28zpIhv3RoTdsLMPng=
@@ -14,8 +18,6 @@ github.com/rivo/uniseg v0.2.0/go.mod h1:J6wj4VEh+S6ZtnVlnTBMWIodfgj8LQOQFoIToxlJ
 github.com/rivo/uniseg v0.4.3/go.mod h1:FN3SvrM+Zdj16jyLfmOkMNblXMcoc8DfTHruCPUcx88=
 github.com/rivo/uniseg v0.4.7 h1:WUdvkW8uEhrYfLC4ZzdpI2ztxP1I582+49Oc5Mq64VQ=
 github.com/rivo/uniseg v0.4.7/go.mod h1:FN3SvrM+Zdj16jyLfmOkMNblXMcoc8DfTHruCPUcx88=
-github.com/saracen/walker v0.1.3 h1:YtcKKmpRPy6XJTHJ75J2QYXXZYWnZNQxPCVqZSHVV/g=
-github.com/saracen/walker v0.1.3/go.mod h1:FU+7qU8DeQQgSZDmmThMJi93kPkLFgy0oVAcLxurjIk=
 github.com/yuin/goldmark v1.4.13/go.mod h1:6yULJ656Px+3vBD8DxQVa3kxgyrAnzto9xy5taEt/CY=
 golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
 golang.org/x/crypto v0.0.0-20210921155107-089bfa567519/go.mod h1:GvvjBRRGRdwPK5ydBHafDWAxML/pGHZbMvKqRZ5+Abc=
@@ -26,11 +28,8 @@ golang.org/x/net v0.0.0-20210226172049-e18ecbb05110/go.mod h1:m0MpNAwzfU5UDzcl9v
 golang.org/x/net v0.0.0-20220722155237-a158d28d115b/go.mod h1:XRhObCWvk6IyKnWLug+ECip1KBveYUHfp+8e9klMJ9c=
 golang.org/x/net v0.6.0/go.mod h1:2Tu9+aMcznHK/AK1HMvgo6xiTLG5rD5rZLDS+rp2Bjs=
 golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
-golang.org/x/sync v0.0.0-20220601150217-0de741cfad7f/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
 golang.org/x/sync v0.0.0-20220722155255-886fb9371eb4/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
 golang.org/x/sync v0.1.0/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
-golang.org/x/sync v0.5.0 h1:60k92dhOjHxJkrqnwsfl8KuaHbn/5dl0lUPUklKo3qE=
-golang.org/x/sync v0.5.0/go.mod h1:Czt+wKu1gCyEFDUtn0jG5QVvpJ6rzVqr5aXyt9drQfk=
 golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
 golang.org/x/sys v0.0.0-20201119102817-f84b799fce68/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20210615035016-665e8c7367d1/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
diff --git a/src/constants.go b/src/constants.go
index 76211dcd..f5f8a939 100644
--- a/src/constants.go
+++ b/src/constants.go
@@ -2,7 +2,6 @@ package fzf
 
 import (
 	"math"
-	"os"
 	"time"
 
 	"github.com/junegunn/fzf/src/util"
@@ -54,16 +53,6 @@ const (
 	defaultJumpLabels string = "asdfghjklqwertyuiopzxcvbnm1234567890ASDFGHJKLQWERTYUIOPZXCVBNM`~;:,<.>/?'\"!@#$%^&*()[{]}-_=+"
 )
 
-var defaultCommand string
-
-func init() {
-	if !util.IsWindows() {
-		defaultCommand = `set -o pipefail; command find -L . -mindepth 1 \( -path '*/.*' -o -fstype 'sysfs' -o -fstype 'devfs' -o -fstype 'devtmpfs' -o -fstype 'proc' \) -prune -o -type f -print -o -type l -print 2> /dev/null | cut -b3-`
-	} else if os.Getenv("TERM") == "cygwin" {
-		defaultCommand = `sh -c "command find -L . -mindepth 1 -path '*/.*' -prune -o -type f -print -o -type l -print 2> /dev/null | cut -b3-"`
-	}
-}
-
 // fzf events
 const (
 	EvtReadNew util.EventType = iota
diff --git a/src/reader.go b/src/reader.go
index 494a2f72..ce5950d7 100644
--- a/src/reader.go
+++ b/src/reader.go
@@ -6,14 +6,13 @@ import (
 	"io"
 	"os"
 	"os/exec"
-	"path"
 	"path/filepath"
 	"sync"
 	"sync/atomic"
 	"time"
 
+	"github.com/charlievieth/fastwalk"
 	"github.com/junegunn/fzf/src/util"
-	"github.com/saracen/walker"
 )
 
 // Reader reads from command or standard input
@@ -77,14 +76,13 @@ func (r *Reader) fin(success bool) {
 
 func (r *Reader) terminate() {
 	r.mutex.Lock()
-	defer func() { r.mutex.Unlock() }()
-
 	r.killed = true
 	if r.exec != nil && r.exec.Process != nil {
 		util.KillCommand(r.exec)
-	} else if defaultCommand != "" {
+	} else {
 		os.Stdin.Close()
 	}
+	r.mutex.Unlock()
 }
 
 func (r *Reader) restart(command string) {
@@ -99,24 +97,9 @@ func (r *Reader) ReadSource() {
 	r.startEventPoller()
 	var success bool
 	if util.IsTty() {
-		// The default command for *nix requires a shell that supports "pipefail"
-		// https://unix.stackexchange.com/a/654932/62171
-		shell := "bash"
-		currentShell := os.Getenv("SHELL")
-		currentShellName := path.Base(currentShell)
-		for _, shellName := range []string{"bash", "zsh", "ksh", "ash", "hush", "mksh", "yash"} {
-			if currentShellName == shellName {
-				shell = currentShell
-				break
-			}
-		}
 		cmd := os.Getenv("FZF_DEFAULT_COMMAND")
 		if len(cmd) == 0 {
-			if defaultCommand != "" {
-				success = r.readFromCommand(&shell, defaultCommand)
-			} else {
-				success = r.readFiles()
-			}
+			success = r.readFiles()
 		} else {
 			success = r.readFromCommand(nil, cmd)
 		}
@@ -163,10 +146,14 @@ func (r *Reader) readFromStdin() bool {
 
 func (r *Reader) readFiles() bool {
 	r.killed = false
-	fn := func(path string, mode os.FileInfo) error {
+	conf := fastwalk.Config{Follow: true}
+	fn := func(path string, de os.DirEntry, err error) error {
+		if err != nil {
+			return nil
+		}
 		path = filepath.Clean(path)
 		if path != "." {
-			isDir := mode.Mode().IsDir()
+			isDir := de.IsDir()
 			if isDir && filepath.Base(path)[0] == '.' {
 				return filepath.SkipDir
 			}
@@ -181,10 +168,7 @@ func (r *Reader) readFiles() bool {
 		}
 		return nil
 	}
-	cb := walker.WithErrorCallback(func(pathname string, err error) error {
-		return nil
-	})
-	return walker.Walk(".", fn, cb) == nil
+	return fastwalk.Walk(&conf, ".", fn) == nil
 }
 
 func (r *Reader) readFromCommand(shell *string, command string) bool {