README.md

@@ -13,8 +13,24 @@ Package fastwalk provides a fast parallel version of [`filepath.WalkDir`](https: that is \~4x faster on Linux, \~2x faster on macOS, allocates 50% less memory, and requires 25% fewer memory allocations. +Inspired by and based off of [golang.org/x/tools/internal/fastwalk](https://pkg.go.dev/golang.org/x/tools@v0.1.9/internal/fastwalk).+ <!-- TODO: mention EntryFilter --> +## Features++<!--  and execution of the [`filepath.WalkDir`](https://pkg.go.dev/io/fs#WalkDirFunc) callback -->++* Fast: multiple goroutines stat the filesystem and call the+  [`filepath.WalkDir`](https://pkg.go.dev/io/fs#WalkDirFunc) callback concurrently+* Safe symbolic link traversal ([`Config.Follow`](https://pkg.go.dev/github.com/charlievieth/fastwalk#Config))+* Same behavior and callback signature as [`filepath.WalkDir`](https://pkg.go.dev/path/filepath@go1.17.7#WalkDir)+* Wrapper functions are provided to ignore duplicate files and directories:+	[`IgnoreDuplicateFiles()`](https://pkg.go.dev/github.com/charlievieth/fastwalk#IgnoreDuplicateFiles)+	and+	[`IgnoreDuplicateDirs()`](https://pkg.go.dev/github.com/charlievieth/fastwalk#IgnoreDuplicateDirs)+* Extensively tested on macOS, Linux, and Windows+ ## Usage  Usage is the same as [`filepath.WalkDir`](https://pkg.go.dev/io/fs#WalkDirFunc),@@ -22,100 +38,73 @@ but the [`walkFn`](https://pkg.go.dev/path/filepath@go1.17.7#WalkFunc) argument to [`fastwalk.Walk`](https://pkg.go.dev/github.com/charlievieth/fastwalk#Walk) must be safe for concurrent use. +Examples can be found in the [examples](./examples) directory.+ <!-- TODO: this example is large move it to an examples folder --> -The below example recursively walks a directory following symbolic links and-prints the number of lines found in each file (or symbolic link that references-a file) to stdout:+The below example is a very simple version of the POSIX+[find](https://pubs.opengroup.org/onlinepubs/007904975/utilities/find.html) utility: ```go+// fwfind is a an example program that is similar to POSIX find,+// but faster and worse (it's an example).+package main+ import (-	"bytes"+	"flag" 	"fmt"-	"io" 	"io/fs" 	"os"+	"path/filepath"  	"github.com/charlievieth/fastwalk" ) -var newLine = []byte{'\n'}+const usageMsg = `Usage: %[1]s [-L] [-name] [PATH...]: -// countLinesInFile returns the number of newlines ('\n') in file name.-func countLinesInFile(name string) (int64, error) {-	f, err := os.Open(name)-	if err != nil {-		return 0, err+%[1]s is a poor replacement for the POSIX find utility++`++func main() {+	flag.Usage = func() {+		fmt.Fprintf(os.Stdout, usageMsg, filepath.Base(os.Args[0]))+		flag.PrintDefaults() 	}-	defer f.Close()--	buf := make([]byte, 96*1024)-	var lines int64-	for {-		n, e := f.Read(buf)-		if n > 0 {-			lines += int64(bytes.Count(buf[:n], newLine))-		}-		if e != nil {-			if e != io.EOF {-				err = e-			}-			break-		}+	pattern := flag.String("name", "", "Pattern to match file names against.")+	followLinks := flag.Bool("L", false, "Follow symbolic links")+	flag.Parse()++	// If no paths are provided default to the current directory: "."+	args := flag.Args()+	if len(args) == 0 {+		args = append(args, ".")+	}++	// Follow links if the "-L" flag is provided+	conf := fastwalk.Config{+		Follow: *followLinks, 	}-	return lines, err-} -// LineCount recursively walks directory root printing the number of lines in-// file encountered.-func LineCount(root string) error {-	countLinesWalkFn := func(path string, d fs.DirEntry, err error) error {-		// We wrap this with fastwalk.IgnorePermissionErrors so we know the-		// error is not a permission error (common when walking outside a users-		// home directory) and is likely something worse so we should return it-		// and abort the walk.-		//-		// A common error here is "too many open files", which can occur if the-		// walkFn opens, but does not close, files.+	walkFn := func(path string, d fs.DirEntry, err error) error { 		if err != nil {-			return err+			fmt.Fprintf(os.Stderr, "%s: %v\n", path, err)+			return nil // returning the error stops iteration 		}--		// If the entry is a symbolic link get the type of file that-		// it references.-		typ := d.Type()-		if typ&fs.ModeSymlink != 0 {-			if fi, err := fastwalk.StatDirEntry(path, d); err == nil {-				typ = fi.Mode().Type()+		if *pattern != "" {+			if ok, err := filepath.Match(*pattern, d.Name()); !ok {+				// invalid pattern (err != nil) or name does not match+				return err 			} 		}--		if typ.IsRegular() {-			lines, err := countLinesInFile(path)-			if err == nil {-				fmt.Printf("%8d %s\n", lines, path)-			} else {-				// Print but do not return the error.-				fmt.Fprintf(os.Stderr, "%s: %s\n", path, err)-			}-		}-		return nil+		_, err = fmt.Println(path)+		return err 	}--	// Ignore permission errors traversing directories.-	//-	// Note: this only ignores permission errors when traversing directories.-	// Permission errors may still be encountered when accessing files.-	walkFn := fastwalk.IgnorePermissionErrors(countLinesWalkFn)--	// Safely follow symbolic links. This can also be achieved by setting-	// fastwalk.Config.Follow to true.-	walkFn = fastwalk.FollowSymlinks(walkFn)--	// If Walk is called with a nil Config the DefaultConfig is used.-	if err := fastwalk.Walk(nil, root, walkFn); err != nil {-                return fmt.Errorf("walking directory %s: %v", root, err)+	for _, root := range args {+		if err := fastwalk.Walk(&conf, root, walkFn); err != nil {+			fmt.Fprintf(os.Stderr, "%s: %v\n", root, err)+			os.Exit(1)+		} 	}-        return nil } ``` 

examples/fwfind/.gitignore

new file mode 100644@@ -0,0 +1,2 @@+/fwfind+*.exe

examples/fwfind/main.go

new file mode 100644@@ -0,0 +1,61 @@+// fwfind is a an example program that is similar to POSIX find,+// but faster and worse (it's an example).+package main++import (+	"flag"+	"fmt"+	"io/fs"+	"os"+	"path/filepath"++	"github.com/charlievieth/fastwalk"+)++const usageMsg = `Usage: %[1]s [-L] [-name] [PATH...]:++%[1]s is a poor replacement for the POSIX find utility++`++func main() {+	flag.Usage = func() {+		fmt.Fprintf(os.Stdout, usageMsg, filepath.Base(os.Args[0]))+		flag.PrintDefaults()+	}+	pattern := flag.String("name", "", "Pattern to match file names against.")+	followLinks := flag.Bool("L", false, "Follow symbolic links")+	flag.Parse()++	// If no paths are provided default to the current directory: "."+	args := flag.Args()+	if len(args) == 0 {+		args = append(args, ".")+	}++	// Follow links if the "-L" flag is provided+	conf := fastwalk.Config{+		Follow: *followLinks,+	}++	walkFn := func(path string, d fs.DirEntry, err error) error {+		if err != nil {+			fmt.Fprintf(os.Stderr, "%s: %v\n", path, err)+			return nil // returning the error stops iteration+		}+		if *pattern != "" {+			if ok, err := filepath.Match(*pattern, d.Name()); !ok {+				// invalid pattern (err != nil) or name does not match+				return err+			}+		}+		_, err = fmt.Println(path)+		return err+	}+	for _, root := range args {+		if err := fastwalk.Walk(&conf, root, walkFn); err != nil {+			fmt.Fprintf(os.Stderr, "%s: %v\n", root, err)+			os.Exit(1)+		}+	}+}

examples/fwwc/.gitignore

new file mode 100644@@ -0,0 +1,2 @@+/fwwc+*.exe

examples/fwwc/main.go

new file mode 100644@@ -0,0 +1,134 @@+// fwwc is a an example program that recursively walks directories and+// prints the number of lines in each file it encounters.+package main++import (+	"bytes"+	"flag"+	"fmt"+	"io"+	"io/fs"+	"os"+	"path/filepath"++	"github.com/charlievieth/fastwalk"+)++var newLine = []byte{'\n'}++// countLinesInFile returns the number of newlines ('\n') in file name.+func countLinesInFile(name string) (int64, error) {+	f, err := os.Open(name)+	if err != nil {+		return 0, err+	}+	defer f.Close()++	buf := make([]byte, 16*1024)+	var lines int64+	for {+		n, e := f.Read(buf)+		if n > 0 {+			lines += int64(bytes.Count(buf[:n], newLine))+		}+		if e != nil {+			if e != io.EOF {+				err = e+			}+			break+		}+	}+	return lines, err+}++func LineCount(root string, followLinks bool) error {+	countLinesWalkFn := func(path string, d fs.DirEntry, err error) error {+		// We wrap this with fastwalk.IgnorePermissionErrors so we know the+		// error is not a permission error (common when walking outside a users+		// home directory) and is likely something worse so we should return it+		// and abort the walk.+		//+		// A common error here is "too many open files", which can occur if the+		// walkFn opens, but does not close, files.+		if err != nil {+			return err+		}++		// If the entry is a symbolic link get the type of file that+		// it references.+		typ := d.Type()+		if typ&fs.ModeSymlink != 0 {+			if fi, err := fastwalk.StatDirEntry(path, d); err == nil {+				typ = fi.Mode().Type()+			}+		}++		// Skip dot (".") files (but allow "." / PWD as the path)+		if path != "." && typ.IsDir() {+			name := d.Name()+			if name == "" || name[0] == '.' || name[0] == '_' {+				return fastwalk.SkipDir+			}+			return nil+		}+		if typ.IsRegular() {+			lines, err := countLinesInFile(path)+			if err == nil {+				fmt.Printf("%8d %s\n", lines, path)+			} else {+				// Print but do not return the error.+				fmt.Fprintf(os.Stderr, "%s: %s\n", path, err)+			}+		}+		return nil+	}++	// Ignore permission errors traversing directories.+	//+	// Note: this only ignores permission errors when traversing directories.+	// Permission errors may still be encountered when accessing files.+	walkFn := fastwalk.IgnorePermissionErrors(countLinesWalkFn)++	conf := fastwalk.Config{+		// Safely follow symbolic links. This can also be achieved by+		// wrapping walkFn with fastwalk.FollowSymlinks().+		Follow: followLinks,++		// If NumWorkers is ≤ 0 the default is used, which is sufficient+		// for most use cases.+	}+	// Note: Walk can also be called with a nil Config, in which case+	// fastwalk.DefaultConfig is used.+	if err := fastwalk.Walk(&conf, root, walkFn); err != nil {+		return fmt.Errorf("walking directory %s: %w", root, err)+	}+	return nil+}++const UsageMsg = `Usage: %[1]s [-L] [PATH...]:++%[1]s prints the number of lines in each file it finds,+ignoring directories that start with '.' or '_'.++`++func main() {+	flag.Usage = func() {+		fmt.Fprintf(os.Stdout, UsageMsg, filepath.Base(os.Args[0]))+		flag.PrintDefaults()+	}+	followLinks := flag.Bool("L", false, "Follow symbolic links")+	flag.Parse()++	args := flag.Args()+	if len(args) == 0 {+		args = append(args, ".")+	}+	for _, root := range args {+		// fmt.Println("ROOT:", root)+		if err := LineCount(root, *followLinks); err != nil {+			fmt.Fprintln(os.Stderr, "error:", err)+			os.Exit(1)+		}+	}+}

fastwalk.go

@@ -154,7 +154,7 @@ type DirEntry interface { //     file. The result of Stat() may be cached. //   * Multiple goroutines stat the filesystem concurrently. The provided //     walkFn must be safe for concurrent use.-//   * Walk can follow symlinks if walkFn returns the TraverseLink+//   * Walk can follow symlinks if walkFn returns the ErrTraverseLink //     sentinel error. It is the walkFn's responsibility to prevent //     Walk from going into symlink cycles. func Walk(conf *Config, root string, walkFn fs.WalkDirFunc) error {