adapters.go

@@ -7,57 +7,94 @@ import ( )  func isDir(path string, d fs.DirEntry) bool {-	typ := d.Type()-	if typ&os.ModeSymlink != 0 {+	if d.IsDir() {+		return true+	}+	if d.Type()&os.ModeSymlink != 0 { 		if fi, err := StatDirEntry(path, d); err == nil {-			typ = fi.Mode().Type()+			return fi.IsDir() 		} 	}-	return typ.IsDir()+	return false } -// TODO: the following wrappers may be incorrect since we do not-// call the WalkDirFunc in all cases.--// FollowSymlinks wraps walkFn so that symlinks are followed.-func FollowSymlinks(walkFn fs.WalkDirFunc) fs.WalkDirFunc {+// IgnoreDuplicateDirs wraps fs.WalkDirFunc walkFn to make it follow symbolic+// links and ignore duplicate directories (if a symlink points to a directory+// that has already been traversed it is skipped). The walkFn is called for+// for skipped directories, but the directory is not traversed (this is+// required for error handling).+//+// The Config.Follow setting has no effect on the behavior of Walk when+// this wrapper is used.+//+// In most use cases, the returned fs.WalkDirFunc should not be reused between+// in another call to Walk. If it is reused, any previously visited file will+// be skipped.+//+// NOTE: The order of traversal is undefined. Given an "example" directory+// like the one below where "dir" is a directory and "smydir1" and "smydir2"+// are links to it, only one of "dir", "smydir1", or "smydir2" will be+// traversed, but which one is undefined.+//+// 	example+// 	├── dir+// 	├── smydir1 -> dir+// 	└── smydir2 -> dir+//+func IgnoreDuplicateDirs(walkFn fs.WalkDirFunc) fs.WalkDirFunc { 	filter := NewEntryFilter() 	return func(path string, d fs.DirEntry, err error) error {+		// Call walkFn before checking the entry filter so that we+		// don't record directories that are skipped with SkipDir.+		err = walkFn(path, d, err)+		if err != nil {+			if err != filepath.SkipDir && isDir(path, d) {+				filter.Entry(path, d)+			}+			return err+		} 		if isDir(path, d) {-			// TODO: call walkFn on these files or is that already handled? 			if filter.Entry(path, d) { 				return filepath.SkipDir 			}-			if d.Type()&os.ModeSymlink != 0 {+			if d.Type() == os.ModeSymlink { 				return ErrTraverseLink 			}-			return nil 		}-		return walkFn(path, d, err)+		return nil 	} }  // IgnoreDuplicateFiles wraps walkFn so that symlinks are followed and duplicate // files are ignored. If a symlink resolves to a file that has already been // visited it will be skipped.+//+// In most use cases, the returned fs.WalkDirFunc should not be reused between+// in another call to Walk. If it is reused, any previously visited file will+// be skipped.+//+// This can significantly slow Walk as os.Stat() is called for each path+// (on Windows, os.Stat() is only needed for symlinks). func IgnoreDuplicateFiles(walkFn fs.WalkDirFunc) fs.WalkDirFunc { 	filter := NewEntryFilter()-	return func(path string, ent fs.DirEntry, err error) error {-		typ := ent.Type()-		if filter.Entry(path, ent) {-			if typ.IsDir() {+	return func(path string, d fs.DirEntry, err error) error {+		// Skip all duplicate files, directories, and links+		if filter.Entry(path, d) {+			if isDir(path, d) { 				return filepath.SkipDir 			} 			return nil 		}-		if typ&os.ModeSymlink != 0 {-			return ErrTraverseLink+		err = walkFn(path, d, err)+		if err == nil && d.Type() == os.ModeSymlink && isDir(path, d) {+			err = ErrTraverseLink 		}-		return walkFn(path, ent, err)+		return err 	} }  // IgnorePermissionErrors wraps walkFn so that permission errors are ignored.+// The returned fs.WalkDirFunc may be reused. func IgnorePermissionErrors(walkFn fs.WalkDirFunc) fs.WalkDirFunc { 	return func(path string, d fs.DirEntry, err error) error { 		if err != nil && os.IsPermission(err) {

adapters_test.go

new file mode 100644@@ -0,0 +1,237 @@+package fastwalk_test++import (+	"errors"+	"io/fs"+	"io/ioutil"+	"os"+	"path/filepath"+	"reflect"+	"runtime"+	"sort"+	"strings"+	"sync"+	"sync/atomic"+	"testing"++	"github.com/charlievieth/fastwalk"+)++func TestIgnoreDuplicateDirs(t *testing.T) {+	tempdir, err := ioutil.TempDir("", "test-fast-walk")+	if err != nil {+		t.Fatal(err)+	}+	// on macOS the tempdir is a symlink+	tempdir, err = filepath.EvalSymlinks(tempdir)+	if err != nil {+		t.Fatal(err)+	}+	defer cleanupOrLogTempDir(t, tempdir)++	files := map[string]string{+		"bar/bar.go":  "one",+		"foo/foo.go":  "two",+		"skip/baz.go": "three", // we skip "skip", but visit "baz.go" via "symdir"+		"symdir":      "LINK:skip",+		"bar/symdir":  "LINK:../foo/",+		"bar/loop":    "LINK:../bar/", // symlink loop+	}+	testCreateFiles(t, tempdir, files)++	want := map[string]os.FileMode{+		"":                   os.ModeDir,+		"/src":               os.ModeDir,+		"/src/bar":           os.ModeDir,+		"/src/bar/bar.go":    0,+		"/src/bar/symdir":    os.ModeSymlink,+		"/src/bar/loop":      os.ModeSymlink,+		"/src/foo":           os.ModeDir,+		"/src/foo/foo.go":    0,+		"/src/symdir":        os.ModeSymlink,+		"/src/symdir/baz.go": 0,+		"/src/skip":          os.ModeDir,+	}++	runTest := func(t *testing.T, conf *fastwalk.Config) {+		var mu sync.Mutex+		got := make(map[string]os.FileMode)+		walkFn := fastwalk.IgnoreDuplicateDirs(func(path string, de fs.DirEntry, err error) error {+			requireNoError(t, err)+			if err != nil {+				return err+			}++			// Resolve links for regular files since we don't know which directory+			// or link we traversed to visit them. Exclude "baz.go" because we want+			// to test that we visited it through it's link.+			if de.Type().IsRegular() && de.Name() != "baz.go" {+				realpath, err := filepath.EvalSymlinks(path)+				if err != nil {+					t.Error(err)+					return err+				}+				path = realpath+			}+			if !strings.HasPrefix(path, tempdir) {+				t.Errorf("Path %q not a child of TMPDIR %q", path, tempdir)+				return errors.New("abort")+			}+			key := filepath.ToSlash(strings.TrimPrefix(path, tempdir))++			mu.Lock()+			defer mu.Unlock()+			got[key] = de.Type().Type()++			if de.Name() == "skip" {+				return filepath.SkipDir+			}+			return nil+		})+		if err := fastwalk.Walk(conf, tempdir, walkFn); err != nil {+			t.Error("fastwalk:", err)+		}+		if !reflect.DeepEqual(want, got) {+			t.Errorf("walk mismatch.\n got:\n%v\nwant:\n%v", formatFileModes(got), formatFileModes(want))+			diffFileModes(t, got, want)+		}+	}++	t.Run("NoFollow", func(t *testing.T) {+		runTest(t, &fastwalk.Config{Follow: false})+	})++	// Test that setting Follow to true has no impact on the behavior+	t.Run("Follow", func(t *testing.T) {+		runTest(t, &fastwalk.Config{Follow: true})+	})++	t.Run("Error", func(t *testing.T) {+		tempdir := t.TempDir()+		if err := os.WriteFile(tempdir+"/error_test", []byte("error"), 0644); err != nil {+			t.Fatal(err)+		}+		want := errors.New("my error")+		var callCount int32+		walkFn := fastwalk.IgnoreDuplicateDirs(func(path string, de fs.DirEntry, err error) error {+			atomic.AddInt32(&callCount, 1)+			return want+		})+		err := fastwalk.Walk(nil, tempdir, walkFn)+		if !errors.Is(err, want) {+			t.Errorf("Error: want: %v got: %v", want, err)+		}++	})+}++func TestIgnoreDuplicateFiles(t *testing.T) {+	tempdir := t.TempDir()+	files := map[string]string{+		"foo/foo.go":       "one",+		"bar/bar.go":       "LINK:../foo/foo.go",+		"bar/baz.go":       "two",+		"broken/broken.go": "LINK:../nonexistent",+		"bar/loop":         "LINK:../bar/", // symlink loop+		"file.go":          "three",++		// Use multiple symdirs to increase the chance that one+		// of these and not "foo" is followed first.+		"symdir1": "LINK:foo",+		"symdir2": "LINK:foo",+		"symdir3": "LINK:foo",+		"symdir4": "LINK:foo",+	}+	if runtime.GOOS == "windows" {+		delete(files, "broken/broken.go")+	}+	testCreateFiles(t, tempdir, files)++	var expectedContents []string+	for _, contents := range files {+		if !strings.HasPrefix(contents, "LINK:") {+			expectedContents = append(expectedContents, contents)+		}+	}+	sort.Strings(expectedContents)++	var (+		mu       sync.Mutex+		seen     []os.FileInfo+		contents []string+	)+	walkFn := fastwalk.IgnoreDuplicateFiles(func(path string, de fs.DirEntry, err error) error {+		requireNoError(t, err)+		fi1, err := fastwalk.StatDirEntry(path, de)+		if err != nil {+			t.Error(err)+			return err+		}+		mu.Lock()+		defer mu.Unlock()+		for _, fi2 := range seen {+			if os.SameFile(fi1, fi2) {+				t.Errorf("Visited file twice: %q (%s) and %q (%s)",+					path, fi1.Mode(), fi2.Name(), fi2.Mode())+			}+		}+		seen = append(seen, fi1)+		if fi1.Mode().IsRegular() {+			data, err := os.ReadFile(path)+			if err != nil {+				return err+			}+			contents = append(contents, string(data))+		}+		return nil+	})+	if err := fastwalk.Walk(nil, tempdir, walkFn); err != nil {+		t.Fatal(err)+	}++	sort.Strings(contents)+	if !reflect.DeepEqual(expectedContents, contents) {+		t.Errorf("File contents want: %q got: %q", expectedContents, contents)+	}+}++func TestIgnorePermissionErrors(t *testing.T) {+	var called bool+	fn := fastwalk.IgnorePermissionErrors(func(path string, _ fs.DirEntry, err error) error {+		called = true+		if err != nil {+			t.Fatal(err)+		}+		return nil+	})++	t.Run("PermissionError", func(t *testing.T) {+		err := fn("", nil, &os.PathError{Op: "open", Path: "foo.go", Err: os.ErrPermission})+		if err != nil {+			t.Fatal(err)+		}+		if called {+			t.Fatal("walkFn should not have been called with os.ErrPermission")+		}+	})++	t.Run("NilError", func(t *testing.T) {+		called = false+		if err := fn("", nil, nil); err != nil {+			t.Fatal(err)+		}+		if !called {+			t.Fatal("walkFn should have been called with nil error")+		}+	})++	t.Run("OtherError", func(t *testing.T) {+		fn := fastwalk.IgnorePermissionErrors(func(path string, _ fs.DirEntry, err error) error {+			return err+		})+		want := &os.PathError{Op: "open", Path: "foo.go", Err: os.ErrExist}+		if got := fn("", nil, want); got != want {+			t.Fatalf("want error: %v got: %v", want, got)+		}+	})+}

dirent_export_test.go

@@ -4,6 +4,7 @@ import ( 	"fmt" 	"io/fs" 	"os"+	"testing" 	"time" ) @@ -27,3 +28,27 @@ func FormatFileInfo(fi fs.FileInfo) string { 		Sys:     fmt.Sprintf("%+v", fi.Sys()), 	}) }++func TestCleanRootPath(t *testing.T) {+	tests := map[string]string{+		"":      "",+		"/":     "/",+		"//":    "/",+		"/foo":  "/foo",+		"/foo/": "/foo",+		"a":     "a",+		`C:/`:   `C:`,+	}+	if os.PathSeparator != '/' {+		const sep = string(os.PathSeparator)+		tests["C:"+sep] = `C:`+		tests["C:"+sep+sep] = `C:`+		tests[sep+sep] = sep+	}+	for in, want := range tests {+		got := cleanRootPath(in)+		if got != want {+			t.Errorf("cleanRootPath(%q) = %q; want: %q", in, got, want)+		}+	}+}

entry_filter_test.go

@@ -7,6 +7,7 @@ import ( 	"os" 	"path/filepath" 	"runtime"+	"sync" 	"testing" 	"time" @@ -14,80 +15,64 @@ import ( )  func TestEntryFilter(t *testing.T) {-	dirEntry := func(t *testing.T, name string) fs.DirEntry {-		t.Helper()-		fi, err := os.Lstat(name)-		if err != nil {-			t.Fatal(err)-		}-		return fs.FileInfoToDirEntry(fi)-	}- 	tempdir := t.TempDir()--	fileName := filepath.Join(tempdir, "file.txt")-	if err := writeFile(fileName, "file.txt", 0644); err != nil {-		t.Fatal(err)+	files := map[string]string{+		"foo/foo.go": "one",+		"bar/bar.go": "LINK:../foo/foo.go",+		"bar/baz.go": "two",+		"bar/loop":   "LINK:../bar/", // symlink loop+		"file.go":    "three",++		// Use multiple symdirs to increase the chance that one+		// of these and not "foo" is followed first.+		"symdir1": "LINK:foo",+		"symdir2": "LINK:foo",+		"symdir3": "LINK:foo",+		"symdir4": "LINK:foo", 	}+	testCreateFiles(t, tempdir, files) -	linkDir := filepath.Join(tempdir, "dir")-	if err := os.Mkdir(linkDir, 0755); err != nil {-		t.Fatal(err)-	}-	linkName := filepath.Join(linkDir, "link.link")-	if err := symlink(t, "../"+filepath.Base(fileName), linkName); err != nil {+	var mu sync.Mutex+	var seen []os.FileInfo+	filter := fastwalk.NewEntryFilter()+	walkFn := fastwalk.IgnoreDuplicateFiles(func(path string, de fs.DirEntry, err error) error {+		requireNoError(t, err)+		fi1, err := fastwalk.StatDirEntry(path, de)+		if err != nil {+			t.Error(err)+			return err+		}+		mu.Lock()+		defer mu.Unlock()+		if !filter.Entry(path, de) {+			for _, fi2 := range seen {+				if os.SameFile(fi1, fi2) {+					t.Errorf("Visited file twice: %q (%s) and %q (%s)",+						path, fi1.Mode(), fi2.Name(), fi2.Mode())+				}+			}+		}+		seen = append(seen, fi1)+		return nil+	})+	if err := fastwalk.Walk(nil, tempdir, walkFn); err != nil { 		t.Fatal(err) 	} -	// Sanity check-	{-		fi1, err := os.Stat(fileName)+	// Test that true is returned for a non-existent directory+	// On Windows the Info field of the returned DirEntry+	// is already populated so this will succeed.+	if runtime.GOOS != "windows" {+		path := filepath.Join(tempdir, "src", "foo/foo.go")+		fi, err := os.Lstat(path) 		if err != nil { 			t.Fatal(err) 		}-		fi2, err := os.Stat(linkName)-		if err != nil {+		if err := os.Remove(path); err != nil { 			t.Fatal(err) 		}-		if !os.SameFile(fi1, fi2) {-			t.Fatalf("os.SameFile(%q, %q) == false", fileName, linkName)-		}-	}--	filter := fastwalk.NewEntryFilter()-	if seen := filter.Entry(fileName, dirEntry(t, fileName)); seen {-		t.Errorf("filter.Entry(%q) = %t want: %t",-			filepath.Dir(fileName), seen, false)-	}-	if seen := filter.Entry(linkName, dirEntry(t, linkName)); !seen {-		t.Errorf("filter.Entry(%q) = %t want: %t",-			filepath.Dir(linkName), seen, true)-	}--	// Entry should return true (aka seen) if there is an error-	// stat'ing the file.--	infos, err := os.ReadDir(tempdir)-	if err != nil {-		t.Fatal(err)-	}--	// Remove the files-	if err := os.RemoveAll(tempdir); err != nil {-		t.Fatal(err)-	}--	for _, de := range infos {-		// On Windows the Info field of the returned DirEntry-		// is already populated so this will succeed.-		if runtime.GOOS != "windows" {-			if _, err := de.Info(); err == nil {-				t.Fatal(de.Name())-			}-		}-		path := filepath.Join(tempdir, de.Name())-		if seen := filter.Entry(path, de); !seen {-			t.Errorf("filter.Entry(%q) = %t want: %t", de.Name(), seen, true)+		if !filter.Entry(path, fs.FileInfoToDirEntry(fi)) {+			t.Error("EntryFilter should return true when the file does not exist") 		} 	} }

entry_filter_unix.go

@@ -48,6 +48,8 @@ func (e *EntryFilter) seen(dev, ino uint64) (seen bool) { 	return seen } +// TODO: this name is confusing and should be fixed+ // Entry returns if path and fs.DirEntry have been seen before. func (e *EntryFilter) Entry(path string, de fs.DirEntry) (seen bool) { 	fi, err := StatDirEntry(path, de)

entry_filter_unix_test.go

@@ -42,7 +42,7 @@ func generateDevIno(rr *rand.Rand, ndev, size int) []devIno { 	return pairs } -func TestEntryFilterFiles(t *testing.T) {+func TestEntryFilter_Unix(t *testing.T) { 	rr := rand.New(rand.NewSource(1)) 	pairs := generateDevIno(rr, 2, 100) @@ -59,7 +59,7 @@ func TestEntryFilterFiles(t *testing.T) { 	} } -func TestEntryFilterFiles_Parallel(t *testing.T) {+func TestEntryFilter_Unix_Parallel(t *testing.T) { 	if testing.Short() { 		t.Skip("Short test") 	}@@ -106,32 +106,12 @@ func TestEntryFilterFiles_Parallel(t *testing.T) { 	wg.Wait() } -// TODO: delete?-func BenchmarkEntryFilter_Seen(b *testing.B) {-	rr := rand.New(rand.NewSource(1))-	// pairs := GenerateDevIno(rr, 2, 8192)-	pairs := generateDevIno(rr, 1, 8192)-	x := NewEntryFilter()--	for _, p := range pairs {-		x.seen(p.Dev, p.Ino)-	}-	if len(pairs) != 8192 {-		panic("nope!")-	}--	b.ResetTimer()-	for i := 0; i < b.N; i++ {-		p := pairs[i%8192]-		x.seen(p.Dev, p.Ino)+func BenchmarkEntryFilter_Unix(b *testing.B) {+	if testing.Short() {+		b.Skip("Skipping: short test") 	}-}--// TODO: delete?-func BenchmarkEntryFilter_Seen_Parallel(b *testing.B) { 	rr := rand.New(rand.NewSource(1))-	// pairs := GenerateDevIno(rr, 2, 8192)-	pairs := generateDevIno(rr, 1, 8192)+	pairs := generateDevIno(rr, 2, 8192) 	x := NewEntryFilter()  	for _, p := range pairs {@@ -142,10 +122,19 @@ func BenchmarkEntryFilter_Seen_Parallel(b *testing.B) { 	}  	b.ResetTimer()-	b.RunParallel(func(pb *testing.PB) {-		for i := 0; pb.Next(); i++ {+	b.Run("Sequential", func(b *testing.B) {+		for i := 0; i < b.N; i++ { 			p := pairs[i%8192] 			x.seen(p.Dev, p.Ino) 		} 	})++	b.Run("Parallel", func(b *testing.B) {+		b.RunParallel(func(pb *testing.PB) {+			for i := 0; pb.Next(); i++ {+				p := pairs[i%8192]+				x.seen(p.Dev, p.Ino)+			}+		})+	}) }

fastwalk.go

@@ -54,29 +54,57 @@ var ErrTraverseLink = errors.New("fastwalk: traverse symlink, assuming target is // Child directories will still be traversed. var ErrSkipFiles = errors.New("fastwalk: skip remaining files in directory") -// DefaultNumWorkers is the default number of worker goroutines to use in-// fastwalk.Walk and is in the range of 4 to 32.-var DefaultNumWorkers = func() int {-	numCPU := runtime.NumCPU()+// SkipDir is used as a return value from WalkDirFuncs to indicate that+// the directory named in the call is to be skipped. It is not returned+// as an error by any function.+var SkipDir = fs.SkipDir++// DefaultNumWorkers returns the default number of worker goroutines to use in+// fastwalk.Walk and is the value of runtime.GOMAXPROCS(-1) clamped to a range+// of 4 to 32 except on Darwin where it is either 4 (8 cores or less) or 6+// (more than 8 cores). This is because Walk / IO performance on Darwin+// degrades with more concurrency.+//+// The optimal number for your workload may be lower or higher. The results+// of BenchmarkFastWalkNumWorkers benchmark may be informative.+func DefaultNumWorkers() int {+	numCPU := runtime.GOMAXPROCS(-1) 	if numCPU < 4 { 		return 4 	}+	// Darwin IO performance on APFS slows with more workers.+	// Stat performance is best around 2-4 and file IO is best+	// around 4-6. More workers only benefit CPU intensive tasks.+	if runtime.GOOS == "darwin" {+		if numCPU <= 8 {+			return 4+		}+		return 6+	} 	if numCPU > 32 { 		return 32 	} 	return numCPU-}()+}  // DefaultConfig is the default Config used when none is supplied. var DefaultConfig = Config{ 	Follow:     false,-	NumWorkers: DefaultNumWorkers,+	NumWorkers: DefaultNumWorkers(), }  type Config struct {-	// TODO: better document Follow+	// TODO: do we want to pass a sentinel error to WalkFunc if+	// a symlink loop is detected? -	// Follow symbolic links ignoring duplicate directories.+	// Follow symbolic links ignoring directories that would lead+	// to infinite loops; that is, entering a previously visited+	// directory that is an ancestor of the last file encountered.+	//+	// The sentinel error ErrTraverseLink is ignored when Follow+	// is true (this to prevent users from defeating the loop+	// detection logic), but SkipDir and ErrSkipFiles are still+	// respected. 	Follow bool  	// Number of parallel workers to use. If NumWorkers if ≤ 0 then@@ -147,16 +175,7 @@ func Walk(conf *Config, root string, walkFn fs.WalkDirFunc) error {  	numWorkers := conf.NumWorkers 	if numWorkers <= 0 {-		// TODO(bradfitz): We used a minimum of 4 to give the kernel more info-		// about multiple things we want, in hopes its I/O scheduling can take-		// advantage of that. Hopefully most are in cache. Maybe 4 is even too-		// low of a minimum. Profile more.-		numWorkers = 4-		if n := runtime.NumCPU(); n > numWorkers {-			// TODO(CEV): profile to see if we still want to limit-			// concurrency on macOS.-			numWorkers = n-		}+		numWorkers = DefaultNumWorkers() 	}  	w := &walker{@@ -167,9 +186,13 @@ func Walk(conf *Config, root string, walkFn fs.WalkDirFunc) error {  		// buffered for correctness & not leaking goroutines: 		resc: make(chan error, numWorkers),++		follow: conf.Follow, 	}-	if conf.Follow {-		w.filter = NewEntryFilter()+	if w.follow {+		if fi, err := os.Stat(root); err == nil {+			w.ignoredDirs = append(w.ignoredDirs, fi)+		} 	}  	defer close(w.donec)@@ -178,6 +201,8 @@ func Walk(conf *Config, root string, walkFn fs.WalkDirFunc) error { 		wg.Add(1) 		go w.doWork(&wg) 	}++	root = cleanRootPath(root) 	todo := []walkItem{{dir: root, info: fileInfoToDirEntry(filepath.Dir(root), fi)}} 	out := 0 	for {@@ -243,7 +268,8 @@ type walker struct { 	enqueuec chan walkItem // from workers 	resc     chan error    // from workers -	filter *EntryFilter // track files when walking links+	ignoredDirs []os.FileInfo+	follow      bool }  type walkItem struct {@@ -259,40 +285,79 @@ func (w *walker) enqueue(it walkItem) { 	} } -func (w *walker) onDirEnt(dirName, baseName string, de fs.DirEntry) error {-	joined := dirName + string(os.PathSeparator) + baseName-	typ := de.Type()-	if typ == os.ModeSymlink && w.filter != nil {-		// Check if the symlink points to a directory before potentially-		// enqueuing it.-		if fi, _ := StatDirEntry(joined, de); fi != nil && fi.IsDir() {-			if !w.filter.Entry(joined, de) {-				w.enqueue(walkItem{dir: joined, info: de})-			}+func (w *walker) shouldSkipDir(fi os.FileInfo) bool {+	for _, ignored := range w.ignoredDirs {+		if os.SameFile(ignored, fi) {+			return true 		}-		return nil 	}-	if typ == os.ModeDir {-		if w.filter == nil || !w.filter.Entry(joined, de) {-			w.enqueue(walkItem{dir: joined, info: de})+	return false+}++func (w *walker) shouldTraverse(path string, de fs.DirEntry) bool {+	// TODO: do we need to use filepath.EvalSymlinks() here?+	ts, err := StatDirEntry(path, de)+	if err != nil {+		return false+	}+	if !ts.IsDir() {+		return false+	}+	if w.shouldSkipDir(ts) {+		return false+	}+	for {+		parent := filepath.Dir(path)+		if parent == path {+			return true 		}+		parentInfo, err := os.Stat(parent)+		if err != nil {+			return false+		}+		if os.SameFile(ts, parentInfo) {+			return false+		}+		path = parent+	}+}++func joinPaths(dir, base string) string {+	// Handle the case where the root path argument to Walk is "/"+	// without this the returned path is prefixed with "//".+	if os.PathSeparator == '/' && dir == "/" {+		return dir + base+	}+	return dir + string(os.PathSeparator) + base+}++func (w *walker) onDirEnt(dirName, baseName string, de fs.DirEntry) error {+	joined := joinPaths(dirName, baseName)+	typ := de.Type()+	if typ == os.ModeDir {+		w.enqueue(walkItem{dir: joined, info: de}) 		return nil 	}  	err := w.fn(joined, de, nil) 	if typ == os.ModeSymlink {-		// TODO: note that this only occurs when not-following symlinks-		// (aka: w.seen == nil) 		if err == ErrTraverseLink {-			// Set callbackDone so we don't call it twice for both the-			// symlink-as-symlink and the symlink-as-directory later:-			w.enqueue(walkItem{dir: joined, callbackDone: true})-			return nil+			if !w.follow {+				// Set callbackDone so we don't call it twice for both the+				// symlink-as-symlink and the symlink-as-directory later:+				w.enqueue(walkItem{dir: joined, info: de, callbackDone: true})+				return nil+			}+			err = nil // Ignore ErrTraverseLink when Follow is true. 		} 		if err == filepath.SkipDir { 			// Permit SkipDir on symlinks too. 			return nil 		}+		if err == nil && w.follow && w.shouldTraverse(joined, de) {+			// Traverse symlink+			w.enqueue(walkItem{dir: joined, info: de, callbackDone: true})+		} 	} 	return err }@@ -315,3 +380,15 @@ func (w *walker) walk(root string, info fs.DirEntry, runUserCallback bool) error 	} 	return nil }++func cleanRootPath(root string) string {+	for i := len(root) - 1; i >= 0; i-- {+		if !os.IsPathSeparator(root[i]) {+			return root[:i+1]+		}+	}+	if root != "" {+		return root[0:1] // root is all path separators ("//")+	}+	return root+}

fastwalk_test.go

@@ -2,6 +2,7 @@ package fastwalk_test  import ( 	"bytes"+	"crypto/md5" 	"errors" 	"flag" 	"fmt"@@ -75,13 +76,19 @@ func symlink(t testing.TB, oldname, newname string) error { 	return err } -func testFastWalkConf(t *testing.T, conf *fastwalk.Config, files map[string]string, callback fs.WalkDirFunc, want map[string]os.FileMode) {-	tempdir, err := ioutil.TempDir("", "test-fast-walk")-	if err != nil {-		t.Fatal(err)+func cleanupOrLogTempDir(t *testing.T, tempdir string) {+	if e := recover(); e != nil {+		t.Log("TMPDIR:", tempdir)+		t.Fatal(e)+	}+	if t.Failed() {+		t.Log("TMPDIR:", tempdir)+	} else {+		os.RemoveAll(tempdir) 	}-	defer os.RemoveAll(tempdir)+} +func testCreateFiles(t *testing.T, tempdir string, files map[string]string) { 	symlinks := map[string]string{} 	for path, contents := range files { 		file := filepath.Join(tempdir, "/src", path)@@ -106,10 +113,24 @@ func testFastWalkConf(t *testing.T, conf *fastwalk.Config, files map[string]stri 			t.Fatal(err) 		} 	}+}++func testFastWalkConf(t *testing.T, conf *fastwalk.Config, files map[string]string, callback fs.WalkDirFunc, want map[string]os.FileMode) {+	tempdir, err := ioutil.TempDir("", "test-fast-walk")+	if err != nil {+		t.Fatal(err)+	}+	defer cleanupOrLogTempDir(t, tempdir)++	testCreateFiles(t, tempdir, files)  	got := map[string]os.FileMode{} 	var mu sync.Mutex 	err = fastwalk.Walk(conf, tempdir, func(path string, de fs.DirEntry, err error) error {+		if de == nil {+			t.Errorf("nil fs.DirEntry on %q", path)+			return nil+		} 		mu.Lock() 		defer mu.Unlock() 		if !strings.HasPrefix(path, tempdir) {@@ -128,6 +149,7 @@ func testFastWalkConf(t *testing.T, conf *fastwalk.Config, files map[string]stri 	} 	if !reflect.DeepEqual(got, want) { 		t.Errorf("walk mismatch.\n got:\n%v\nwant:\n%v", formatFileModes(got), formatFileModes(want))+		diffFileModes(t, got, want) 	} } @@ -215,10 +237,14 @@ func TestFastWalk_DirEntryType(t *testing.T) { 		"symdir":           "LINK:foo", 		"broken/broken.go": "LINK:../nonexistent", 	},-		func(path string, typ fs.DirEntry, err error) error {+		func(path string, de fs.DirEntry, err error) error { 			requireNoError(t, err)-			if _, ok := typ.(fastwalk.DirEntry); !ok {-				t.Errorf("%q: not a fastwalk.DirEntry: %T", path, typ)+			if _, ok := de.(fastwalk.DirEntry); !ok {+				t.Errorf("%q: not a fastwalk.DirEntry: %T", path, de)+			}+			if de.Type() != de.Type().Type() {+				t.Errorf("%s: type mismatch got: %q want: %q",+					path, de.Type(), de.Type().Type()) 			} 			return nil 		},@@ -295,10 +321,9 @@ func TestFastWalk_SkipFiles(t *testing.T) {  func TestFastWalk_TraverseSymlink(t *testing.T) { 	testFastWalk(t, map[string]string{-		"foo/foo.go":   "one",-		"bar/bar.go":   "two",-		"skip/skip.go": "skip",-		"symdir":       "LINK:foo",+		"foo/foo.go": "one",+		"bar/bar.go": "two",+		"symdir":     "LINK:foo", 	}, 		func(path string, de fs.DirEntry, err error) error { 			requireNoError(t, err)@@ -315,74 +340,123 @@ func TestFastWalk_TraverseSymlink(t *testing.T) { 			"/src/bar/bar.go":    0, 			"/src/foo":           os.ModeDir, 			"/src/foo/foo.go":    0,-			"/src/skip":          os.ModeDir,-			"/src/skip/skip.go":  0, 			"/src/symdir":        os.ModeSymlink, 			"/src/symdir/foo.go": 0, 		}) } -func TestFastWalk_TraverseSymlink_Follow(t *testing.T) {+func TestFastWalk_Follow(t *testing.T) {+	subTests := []struct {+		Name   string+		OnLink func(path string, d fs.DirEntry) error+	}{+		// Test that the walk func does *not* need to return+		// ErrTraverseLink for links to be followed.+		{+			Name:   "Default",+			OnLink: func(path string, d fs.DirEntry) error { return nil },+		},++		// Test that returning ErrTraverseLink does not interfere+		// with the Follow logic.+		{+			Name: "ErrTraverseLink",+			OnLink: func(path string, d fs.DirEntry) error {+				if d.Type()&os.ModeSymlink != 0 {+					if fi, err := fastwalk.StatDirEntry(path, d); err == nil && fi.IsDir() {+						return fastwalk.ErrTraverseLink+					}+				}+				return nil+			},+		},+	}+	for _, x := range subTests {+		t.Run(x.Name, func(t *testing.T) {+			conf := fastwalk.Config{+				Follow: true,+			}+			testFastWalkConf(t, &conf, map[string]string{+				"foo/foo.go":  "one",+				"bar/bar.go":  "two",+				"foo/symlink": "LINK:foo.go",+				"bar/symdir":  "LINK:../foo/",+				"bar/link1":   "LINK:../foo/",+			},+				func(path string, de fs.DirEntry, err error) error {+					requireNoError(t, err)+					if err != nil {+						return err+					}+					if de.Type()&os.ModeSymlink != 0 {+						return x.OnLink(path, de)+					}+					return nil+				},+				map[string]os.FileMode{+					"":                        os.ModeDir,+					"/src":                    os.ModeDir,+					"/src/bar":                os.ModeDir,+					"/src/bar/bar.go":         0,+					"/src/bar/link1":          os.ModeSymlink,+					"/src/bar/link1/foo.go":   0,+					"/src/bar/link1/symlink":  os.ModeSymlink,+					"/src/bar/symdir":         os.ModeSymlink,+					"/src/bar/symdir/foo.go":  0,+					"/src/bar/symdir/symlink": os.ModeSymlink,+					"/src/foo":                os.ModeDir,+					"/src/foo/foo.go":         0,+					"/src/foo/symlink":        os.ModeSymlink,+				})+		})+	}+}++func TestFastWalk_Follow_SkipDir(t *testing.T) { 	conf := fastwalk.Config{ 		Follow: true, 	} 	testFastWalkConf(t, &conf, map[string]string{-		"foo/foo.go":   "one",-		"bar/bar.go":   "two",-		"skip/skip.go": "skip",-		"foo/symdir":   "LINK:foo",-		"bar/symdir":   "LINK:../foo",+		".dot/baz.go": "one",+		"bar/bar.go":  "three",+		"bar/dot":     "LINK:../.dot/",+		"bar/symdir":  "LINK:../foo/",+		"foo/foo.go":  "two",+		"foo/symlink": "LINK:foo.go", 	}, 		func(path string, de fs.DirEntry, err error) error { 			requireNoError(t, err)-			typ := de.Type().Type()-			if typ == os.ModeSymlink {-				t.Errorf("unexpected symlink: %q", path)+			if err != nil {+				return err+			}+			if strings.HasPrefix(de.Name(), ".") {+				return filepath.SkipDir 			} 			return nil 		}, 		map[string]os.FileMode{-			"":                  os.ModeDir,-			"/src":              os.ModeDir,-			"/src/bar":          os.ModeDir,-			"/src/bar/bar.go":   0,-			"/src/foo":          os.ModeDir,-			"/src/foo/foo.go":   0,-			"/src/skip":         os.ModeDir,-			"/src/skip/skip.go": 0,+			"":                        os.ModeDir,+			"/src":                    os.ModeDir,+			"/src/.dot":               os.ModeDir,+			"/src/bar":                os.ModeDir,+			"/src/bar/bar.go":         0,+			"/src/bar/dot":            os.ModeSymlink,+			"/src/bar/dot/baz.go":     0,+			"/src/bar/symdir":         os.ModeSymlink,+			"/src/bar/symdir/foo.go":  0,+			"/src/bar/symdir/symlink": os.ModeSymlink,+			"/src/foo":                os.ModeDir,+			"/src/foo/foo.go":         0,+			"/src/foo/symlink":        os.ModeSymlink, 		}) } -func TestFastWalk_FollowSymlinks(t *testing.T) {-	testFastWalk(t, map[string]string{-		"foo/foo.go":   "one",-		"bar/bar.go":   "two",-		"skip/skip.go": "skip",-		"bar/loop":     "LINK:../bar/",-	},-		fastwalk.FollowSymlinks(func(path string, de fs.DirEntry, err error) error {-			requireNoError(t, err)-			return nil-		}),-		map[string]os.FileMode{-			"":                  os.ModeDir,-			"/src":              os.ModeDir,-			"/src/bar":          os.ModeDir,-			"/src/bar/loop":     os.ModeSymlink,-			"/src/bar/bar.go":   0,-			"/src/foo":          os.ModeDir,-			"/src/foo/foo.go":   0,-			"/src/skip":         os.ModeDir,-			"/src/skip/skip.go": 0,-		})-}--func TestFastWalk_SymlinkLoop(t *testing.T) {+func TestFastWalk_Follow_SymlinkLoop(t *testing.T) { 	tempdir, err := ioutil.TempDir("", "test-fast-walk") 	if err != nil { 		t.Fatal(err) 	}-	defer os.RemoveAll(tempdir)+	defer cleanupOrLogTempDir(t, tempdir)  	if err := writeFile(tempdir+"/src/foo.go", "hello", 0644); err != nil { 		t.Fatal(err)@@ -396,13 +470,12 @@ func TestFastWalk_SymlinkLoop(t *testing.T) { 	} 	var walked int32 	err = fastwalk.Walk(&conf, tempdir, func(path string, de fs.DirEntry, err error) error {-		requireNoError(t, err)+		if err != nil {+			return err+		} 		if n := atomic.AddInt32(&walked, 1); n > 20 { 			return fmt.Errorf("symlink loop: %d", n) 		}-		if de.Type()&os.ModeSymlink != 0 {-			return fastwalk.ErrTraverseLink-		} 		return nil 	}) 	if err != nil {@@ -410,6 +483,43 @@ func TestFastWalk_SymlinkLoop(t *testing.T) { 	} } +// Test that ErrTraverseLink is ignored when following symlinks+// if it would cause a symlink loop.+func TestFastWalk_Follow_ErrTraverseLink(t *testing.T) {+	conf := fastwalk.Config{+		Follow: true,+	}+	testFastWalkConf(t, &conf, map[string]string{+		"foo/foo.go": "one",+		"bar/bar.go": "two",+		"bar/symdir": "LINK:../foo/",+		"bar/loop":   "LINK:../bar/", // symlink loop+	},+		func(path string, de fs.DirEntry, err error) error {+			requireNoError(t, err)+			if err != nil {+				return err+			}+			if de.Type()&os.ModeSymlink != 0 {+				if fi, err := fastwalk.StatDirEntry(path, de); err == nil && fi.IsDir() {+					return fastwalk.ErrTraverseLink+				}+			}+			return nil+		},+		map[string]os.FileMode{+			"":                       os.ModeDir,+			"/src":                   os.ModeDir,+			"/src/bar":               os.ModeDir,+			"/src/bar/bar.go":        0,+			"/src/bar/loop":          os.ModeSymlink,+			"/src/bar/symdir":        os.ModeSymlink,+			"/src/bar/symdir/foo.go": 0,+			"/src/foo":               os.ModeDir,+			"/src/foo/foo.go":        0,+		})+}+ func TestFastWalk_Error(t *testing.T) { 	tmp := t.TempDir() 	for _, child := range []string{@@ -506,6 +616,54 @@ func TestFastWalk_ErrPermission(t *testing.T) { 	} 	if !reflect.DeepEqual(got, want) { 		t.Errorf("walk mismatch.\n got:\n%v\nwant:\n%v", formatFileModes(got), formatFileModes(want))+		diffFileModes(t, got, want)+	}+}++func diffFileModes(t *testing.T, got, want map[string]os.FileMode) {+	type Mode struct {+		Name string+		Mode os.FileMode+	}+	var extra []Mode+	for k, v := range got {+		if _, ok := want[k]; !ok {+			extra = append(extra, Mode{k, v})+		}+	}+	var missing []Mode+	for k, v := range want {+		if _, ok := got[k]; !ok {+			missing = append(missing, Mode{k, v})+		}+	}+	var delta []Mode+	for k, v := range got {+		if vv, ok := want[k]; ok && vv != v {+			delta = append(delta, Mode{k, v}, Mode{k, vv})+		}+	}+	w := new(strings.Builder)+	printMode := func(name string, modes []Mode) {+		if len(modes) == 0 {+			return+		}+		sort.Slice(modes, func(i, j int) bool {+			return modes[i].Name < modes[j].Name+		})+		if w.Len() == 0 {+			w.WriteString("\n")+		}+		fmt.Fprintf(w, "%s:\n", name)+		for _, m := range modes {+			fmt.Fprintf(w, "  %-20s: %s\n", m.Name, m.Mode.String())+		}+	}+	printMode("Extra", extra)+	printMode("Missing", missing)+	printMode("Delta", delta)+	if w.Len() != 0 {+		t.Error(w.String()) 	} } @@ -526,35 +684,156 @@ func init() { 	} } -func benchmarkFastWalk(b *testing.B, conf *fastwalk.Config) {+func noopWalkFunc(_ string, _ fs.DirEntry, _ error) error { return nil }++func benchmarkFastWalk(b *testing.B, conf *fastwalk.Config,+	adapter func(fs.WalkDirFunc) fs.WalkDirFunc) {+ 	b.ReportAllocs()-	for i := 0; i < b.N; i++ {-		err := fastwalk.Walk(conf, *benchDir, func(_ string, _ fs.DirEntry, _ error) error {-			return nil-		})-		if err != nil {-			b.Fatal(err)+	if adapter != nil {+		walkFn := noopWalkFunc+		for i := 0; i < b.N; i++ {+			err := fastwalk.Walk(conf, *benchDir, adapter(walkFn))+			if err != nil {+				b.Fatal(err)+			}+		}+	} else {+		for i := 0; i < b.N; i++ {+			err := fastwalk.Walk(conf, *benchDir, noopWalkFunc)+			if err != nil {+				b.Fatal(err)+			} 		} 	} }  func BenchmarkFastWalk(b *testing.B) {-	benchmarkFastWalk(b, nil)+	benchmarkFastWalk(b, nil, nil) }  func BenchmarkFastWalkFollow(b *testing.B) {-	benchmarkFastWalk(b, &fastwalk.Config{-		Follow: true,+	benchmarkFastWalk(b, &fastwalk.Config{Follow: true}, nil)+}++func BenchmarkFastWalkAdapters(b *testing.B) {+	if testing.Short() {+		b.Skip("Skipping: short test")+	}+	b.Run("IgnoreDuplicateDirs", func(b *testing.B) {+		benchmarkFastWalk(b, nil, fastwalk.IgnoreDuplicateDirs)+	})++	b.Run("IgnoreDuplicateFiles", func(b *testing.B) {+		benchmarkFastWalk(b, nil, fastwalk.IgnoreDuplicateFiles) 	}) } +// Benchmark various tasks with different worker counts.+//+// Observations:+// 	* Linux (Intel i9-9900K / Samsung Pro NVMe): consistently benefits from+// 	  more workers+// 	* Darwin (m1): IO heavy tasks (Readfile and Stat) and Traversal perform+// 	  best with 4 workers, and only CPU bound tasks benefit from more workers+// func BenchmarkFastWalkNumWorkers(b *testing.B) {-	maxWorkers := runtime.NumCPU() * 2-	for i := 2; i <= maxWorkers; i += 2 {-		b.Run(fmt.Sprint(i), func(b *testing.B) {-		})+	if testing.Short() {+		b.Skip("Skipping: short test")+	}++	runBench := func(b *testing.B, walkFn fs.WalkDirFunc) {+		maxWorkers := runtime.NumCPU()+		for i := 2; i <= maxWorkers; i += 2 {+			b.Run(fmt.Sprint(i), func(b *testing.B) {+				conf := fastwalk.Config{+					NumWorkers: i,+				}+				for i := 0; i < b.N; i++ {+					if err := fastwalk.Walk(&conf, *benchDir, walkFn); err != nil {+						b.Fatal(err)+					}+				}+			})+		} 	}-	benchmarkFastWalk(b, nil)++	// Bench pure traversal speed+	b.Run("NoOp", func(b *testing.B) {+		runBench(b, func(path string, d fs.DirEntry, err error) error {+			return err+		})+	})++	// No IO and light CPU+	b.Run("NoIO", func(b *testing.B) {+		runBench(b, func(path string, d fs.DirEntry, err error) error {+			if err == nil {+				fmt.Fprintf(io.Discard, "%s: %q\n", d.Type(), path)+			}+			return err+		})+	})++	// Stat each regular file+	b.Run("Stat", func(b *testing.B) {+		runBench(b, func(path string, d fs.DirEntry, err error) error {+			if err == nil && d.Type().IsRegular() {+				d.Info()+			}+			return err+		})+	})++	// IO heavy task+	b.Run("ReadFile", func(b *testing.B) {+		runBench(b, func(path string, d fs.DirEntry, err error) error {+			if err != nil || !d.Type().IsRegular() {+				return err+			}+			f, err := os.Open(path)+			if err != nil {+				if os.IsNotExist(err) || os.IsPermission(err) {+					return nil+				}+				return err+			}+			defer f.Close()++			_, err = io.Copy(io.Discard, f)+			return err+		})+	})++	// CPU and IO heavy task+	b.Run("Hash", func(b *testing.B) {+		bufPool := &sync.Pool{+			New: func() interface{} {+				b := make([]byte, 96*1024)+				return &b+			},+		}+		runBench(b, func(path string, d fs.DirEntry, err error) error {+			if err != nil || !d.Type().IsRegular() {+				return err+			}+			f, err := os.Open(path)+			if err != nil {+				if os.IsNotExist(err) || os.IsPermission(err) {+					return nil+				}+				return err+			}+			defer f.Close()++			p := bufPool.Get().(*[]byte)+			h := md5.New()+			_, err = io.CopyBuffer(h, f, *p)+			bufPool.Put(p)+			_ = h.Sum(nil)+			return err+		})+	}) }  var benchWalkFunc = flag.String("walkfunc", "fastwalk", "The function to use for BenchmarkWalkComparison")@@ -562,9 +841,12 @@ var benchWalkFunc = flag.String("walkfunc", "fastwalk", "The function to use for // BenchmarkWalkComparison generates benchmarks using different walk functions // so that the results can be easily compared with `benchcmp` and `benchstat`. func BenchmarkWalkComparison(b *testing.B) {+	if testing.Short() {+		b.Skip("Skipping: short test")+	} 	switch *benchWalkFunc { 	case "fastwalk":-		benchmarkFastWalk(b, nil)+		benchmarkFastWalk(b, nil, nil) 	case "godirwalk": 		opts := godirwalk.Options{ 			Unsorted: true,

fastwalk_unix.go

@@ -78,9 +78,7 @@ func readDir(dirName string, fn func(dirName, entName string, de fs.DirEntry) er 	} } -// TODO: we can probably use syscall.Dirent.Ino + the parents Dev to skip a call to stat func parseDirEnt(buf []byte) (consumed int, name string, typ os.FileMode) {- 	// golang.org/issue/37269 	dirent := &syscall.Dirent{} 	copy((*[unsafe.Sizeof(syscall.Dirent{})]byte)(unsafe.Pointer(dirent))[:], buf)

zsyscall_darwin.go

@@ -6,7 +6,6 @@ package fastwalk import ( 	"syscall" 	"unsafe"-	_ "unsafe" )  // TODO(charlie): implement the closedir and readdir_r functions here instead