imports: extract fastWalk into new package internal/fastwalk

It is going to be used by a new tool.
Moved to an internal package so it does not become a publicly supported
api.
Modified the tests so they don't depend on the fix_test infrastructure.

Change-Id: Ib8ebef24dc23e180960af04aa3d06b5f41a7c02b
Reviewed-on: https://go-review.googlesource.com/99678
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

7 files changed, 4 insertions, 543 deletions

diff --git a/imports/fastwalk.go b/imports/fastwalk.go
deleted file mode 100644
index 31e6e27b0..000000000
--- a/imports/fastwalk.go
+++ /dev/null
@@ -1,187 +0,0 @@
-// Copyright 2016 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// A faster implementation of filepath.Walk.
-//
-// filepath.Walk's design necessarily calls os.Lstat on each file,
-// even if the caller needs less info. And goimports only need to know
-// the type of each file. The kernel interface provides the type in
-// the Readdir call but the standard library ignored it.
-// fastwalk_unix.go contains a fork of the syscall routines.
-//
-// See golang.org/issue/16399
-
-package imports
-
-import (
-	"errors"
-	"os"
-	"path/filepath"
-	"runtime"
-	"sync"
-)
-
-// traverseLink is a sentinel error for fastWalk, similar to filepath.SkipDir.
-var traverseLink = errors.New("traverse symlink, assuming target is a directory")
-
-// fastWalk walks the file tree rooted at root, calling walkFn for
-// each file or directory in the tree, including root.
-//
-// If fastWalk returns filepath.SkipDir, the directory is skipped.
-//
-// Unlike filepath.Walk:
-//   * file stat calls must be done by the user.
-//     The only provided metadata is the file type, which does not include
-//     any permission bits.
-//   * multiple goroutines stat the filesystem concurrently. The provided
-//     walkFn must be safe for concurrent use.
-//   * fastWalk can follow symlinks if walkFn returns the traverseLink
-//     sentinel error. It is the walkFn's responsibility to prevent
-//     fastWalk from going into symlink cycles.
-func fastWalk(root string, walkFn func(path string, typ os.FileMode) error) error {
-	// TODO(bradfitz): make numWorkers configurable? 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 {
-		numWorkers = n
-	}
-
-	// Make sure to wait for all workers to finish, otherwise
-	// walkFn could still be called after returning. This Wait call
-	// runs after close(e.donec) below.
-	var wg sync.WaitGroup
-	defer wg.Wait()
-
-	w := &walker{
-		fn:       walkFn,
-		enqueuec: make(chan walkItem, numWorkers), // buffered for performance
-		workc:    make(chan walkItem, numWorkers), // buffered for performance
-		donec:    make(chan struct{}),
-
-		// buffered for correctness & not leaking goroutines:
-		resc: make(chan error, numWorkers),
-	}
-	defer close(w.donec)
-
-	for i := 0; i < numWorkers; i++ {
-		wg.Add(1)
-		go w.doWork(&wg)
-	}
-	todo := []walkItem{{dir: root}}
-	out := 0
-	for {
-		workc := w.workc
-		var workItem walkItem
-		if len(todo) == 0 {
-			workc = nil
-		} else {
-			workItem = todo[len(todo)-1]
-		}
-		select {
-		case workc <- workItem:
-			todo = todo[:len(todo)-1]
-			out++
-		case it := <-w.enqueuec:
-			todo = append(todo, it)
-		case err := <-w.resc:
-			out--
-			if err != nil {
-				return err
-			}
-			if out == 0 && len(todo) == 0 {
-				// It's safe to quit here, as long as the buffered
-				// enqueue channel isn't also readable, which might
-				// happen if the worker sends both another unit of
-				// work and its result before the other select was
-				// scheduled and both w.resc and w.enqueuec were
-				// readable.
-				select {
-				case it := <-w.enqueuec:
-					todo = append(todo, it)
-				default:
-					return nil
-				}
-			}
-		}
-	}
-}
-
-// doWork reads directories as instructed (via workc) and runs the
-// user's callback function.
-func (w *walker) doWork(wg *sync.WaitGroup) {
-	defer wg.Done()
-	for {
-		select {
-		case <-w.donec:
-			return
-		case it := <-w.workc:
-			select {
-			case <-w.donec:
-				return
-			case w.resc <- w.walk(it.dir, !it.callbackDone):
-			}
-		}
-	}
-}
-
-type walker struct {
-	fn func(path string, typ os.FileMode) error
-
-	donec    chan struct{} // closed on fastWalk's return
-	workc    chan walkItem // to workers
-	enqueuec chan walkItem // from workers
-	resc     chan error    // from workers
-}
-
-type walkItem struct {
-	dir          string
-	callbackDone bool // callback already called; don't do it again
-}
-
-func (w *walker) enqueue(it walkItem) {
-	select {
-	case w.enqueuec <- it:
-	case <-w.donec:
-	}
-}
-
-func (w *walker) onDirEnt(dirName, baseName string, typ os.FileMode) error {
-	joined := dirName + string(os.PathSeparator) + baseName
-	if typ == os.ModeDir {
-		w.enqueue(walkItem{dir: joined})
-		return nil
-	}
-
-	err := w.fn(joined, typ)
-	if typ == os.ModeSymlink {
-		if err == traverseLink {
-			// 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 err == filepath.SkipDir {
-			// Permit SkipDir on symlinks too.
-			return nil
-		}
-	}
-	return err
-}
-
-func (w *walker) walk(root string, runUserCallback bool) error {
-	if runUserCallback {
-		err := w.fn(root, os.ModeDir)
-		if err == filepath.SkipDir {
-			return nil
-		}
-		if err != nil {
-			return err
-		}
-	}
-
-	return readDir(root, w.onDirEnt)
-}
diff --git a/imports/fastwalk_dirent_fileno.go b/imports/fastwalk_dirent_fileno.go
deleted file mode 100644
index f1fd64949..000000000
--- a/imports/fastwalk_dirent_fileno.go
+++ /dev/null
@@ -1,13 +0,0 @@
-// Copyright 2016 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build freebsd openbsd netbsd
-
-package imports
-
-import "syscall"
-
-func direntInode(dirent *syscall.Dirent) uint64 {
-	return uint64(dirent.Fileno)
-}
diff --git a/imports/fastwalk_dirent_ino.go b/imports/fastwalk_dirent_ino.go
deleted file mode 100644
index 9fc6de038..000000000
--- a/imports/fastwalk_dirent_ino.go
+++ /dev/null
@@ -1,14 +0,0 @@
-// Copyright 2016 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build linux darwin
-// +build !appengine
-
-package imports
-
-import "syscall"
-
-func direntInode(dirent *syscall.Dirent) uint64 {
-	return uint64(dirent.Ino)
-}
diff --git a/imports/fastwalk_portable.go b/imports/fastwalk_portable.go
deleted file mode 100644
index 6c2658347..000000000
--- a/imports/fastwalk_portable.go
+++ /dev/null
@@ -1,29 +0,0 @@
-// Copyright 2016 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build appengine !linux,!darwin,!freebsd,!openbsd,!netbsd
-
-package imports
-
-import (
-	"io/ioutil"
-	"os"
-)
-
-// readDir calls fn for each directory entry in dirName.
-// It does not descend into directories or follow symlinks.
-// If fn returns a non-nil error, readDir returns with that error
-// immediately.
-func readDir(dirName string, fn func(dirName, entName string, typ os.FileMode) error) error {
-	fis, err := ioutil.ReadDir(dirName)
-	if err != nil {
-		return err
-	}
-	for _, fi := range fis {
-		if err := fn(dirName, fi.Name(), fi.Mode()&os.ModeType); err != nil {
-			return err
-		}
-	}
-	return nil
-}
diff --git a/imports/fastwalk_test.go b/imports/fastwalk_test.go
deleted file mode 100644
index 5b307d11b..000000000
--- a/imports/fastwalk_test.go
+++ /dev/null
@@ -1,171 +0,0 @@
-// Copyright 2016 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package imports
-
-import (
-	"bytes"
-	"flag"
-	"fmt"
-	"os"
-	"path/filepath"
-	"reflect"
-	"runtime"
-	"sort"
-	"strings"
-	"sync"
-	"testing"
-)
-
-func formatFileModes(m map[string]os.FileMode) string {
-	var keys []string
-	for k := range m {
-		keys = append(keys, k)
-	}
-	sort.Strings(keys)
-	var buf bytes.Buffer
-	for _, k := range keys {
-		fmt.Fprintf(&buf, "%-20s: %v\n", k, m[k])
-	}
-	return buf.String()
-}
-
-func testFastWalk(t *testing.T, files map[string]string, callback func(path string, typ os.FileMode) error, want map[string]os.FileMode) {
-	testConfig{
-		gopathFiles: files,
-	}.test(t, func(t *goimportTest) {
-		got := map[string]os.FileMode{}
-		var mu sync.Mutex
-		if err := fastWalk(t.gopath, func(path string, typ os.FileMode) error {
-			mu.Lock()
-			defer mu.Unlock()
-			if !strings.HasPrefix(path, t.gopath) {
-				t.Fatalf("bogus prefix on %q, expect %q", path, t.gopath)
-			}
-			key := filepath.ToSlash(strings.TrimPrefix(path, t.gopath))
-			if old, dup := got[key]; dup {
-				t.Fatalf("callback called twice for key %q: %v -> %v", key, old, typ)
-			}
-			got[key] = typ
-			return callback(path, typ)
-		}); err != nil {
-			t.Fatalf("callback returned: %v", err)
-		}
-		if !reflect.DeepEqual(got, want) {
-			t.Errorf("walk mismatch.\n got:\n%v\nwant:\n%v", formatFileModes(got), formatFileModes(want))
-		}
-	})
-}
-
-func TestFastWalk_Basic(t *testing.T) {
-	testFastWalk(t, map[string]string{
-		"foo/foo.go":   "one",
-		"bar/bar.go":   "two",
-		"skip/skip.go": "skip",
-	},
-		func(path string, typ os.FileMode) error {
-			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,
-		})
-}
-
-func TestFastWalk_Symlink(t *testing.T) {
-	switch runtime.GOOS {
-	case "windows", "plan9":
-		t.Skipf("skipping on %s", runtime.GOOS)
-	}
-	testFastWalk(t, map[string]string{
-		"foo/foo.go": "one",
-		"bar/bar.go": "LINK:../foo.go",
-		"symdir":     "LINK:foo",
-	},
-		func(path string, typ os.FileMode) error {
-			return nil
-		},
-		map[string]os.FileMode{
-			"":                os.ModeDir,
-			"/src":            os.ModeDir,
-			"/src/bar":        os.ModeDir,
-			"/src/bar/bar.go": os.ModeSymlink,
-			"/src/foo":        os.ModeDir,
-			"/src/foo/foo.go": 0,
-			"/src/symdir":     os.ModeSymlink,
-		})
-}
-
-func TestFastWalk_SkipDir(t *testing.T) {
-	testFastWalk(t, map[string]string{
-		"foo/foo.go":   "one",
-		"bar/bar.go":   "two",
-		"skip/skip.go": "skip",
-	},
-		func(path string, typ os.FileMode) error {
-			if typ == os.ModeDir && strings.HasSuffix(path, "skip") {
-				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,
-		})
-}
-
-func TestFastWalk_TraverseSymlink(t *testing.T) {
-	switch runtime.GOOS {
-	case "windows", "plan9":
-		t.Skipf("skipping on %s", runtime.GOOS)
-	}
-
-	testFastWalk(t, map[string]string{
-		"foo/foo.go":   "one",
-		"bar/bar.go":   "two",
-		"skip/skip.go": "skip",
-		"symdir":       "LINK:foo",
-	},
-		func(path string, typ os.FileMode) error {
-			if typ == os.ModeSymlink {
-				return traverseLink
-			}
-			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,
-			"/src/symdir":        os.ModeSymlink,
-			"/src/symdir/foo.go": 0,
-		})
-}
-
-var benchDir = flag.String("benchdir", runtime.GOROOT(), "The directory to scan for BenchmarkFastWalk")
-
-func BenchmarkFastWalk(b *testing.B) {
-	b.ReportAllocs()
-	for i := 0; i < b.N; i++ {
-		err := fastWalk(*benchDir, func(path string, typ os.FileMode) error { return nil })
-		if err != nil {
-			b.Fatal(err)
-		}
-	}
-}
diff --git a/imports/fastwalk_unix.go b/imports/fastwalk_unix.go
deleted file mode 100644
index e0fc8b7ce..000000000
--- a/imports/fastwalk_unix.go
+++ /dev/null
@@ -1,123 +0,0 @@
-// Copyright 2016 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build linux darwin freebsd openbsd netbsd
-// +build !appengine
-
-package imports
-
-import (
-	"bytes"
-	"fmt"
-	"os"
-	"syscall"
-	"unsafe"
-)
-
-const blockSize = 8 << 10
-
-// unknownFileMode is a sentinel (and bogus) os.FileMode
-// value used to represent a syscall.DT_UNKNOWN Dirent.Type.
-const unknownFileMode os.FileMode = os.ModeNamedPipe | os.ModeSocket | os.ModeDevice
-
-func readDir(dirName string, fn func(dirName, entName string, typ os.FileMode) error) error {
-	fd, err := syscall.Open(dirName, 0, 0)
-	if err != nil {
-		return &os.PathError{Op: "open", Path: dirName, Err: err}
-	}
-	defer syscall.Close(fd)
-
-	// The buffer must be at least a block long.
-	buf := make([]byte, blockSize) // stack-allocated; doesn't escape
-	bufp := 0                      // starting read position in buf
-	nbuf := 0                      // end valid data in buf
-	for {
-		if bufp >= nbuf {
-			bufp = 0
-			nbuf, err = syscall.ReadDirent(fd, buf)
-			if err != nil {
-				return os.NewSyscallError("readdirent", err)
-			}
-			if nbuf <= 0 {
-				return nil
-			}
-		}
-		consumed, name, typ := parseDirEnt(buf[bufp:nbuf])
-		bufp += consumed
-		if name == "" || name == "." || name == ".." {
-			continue
-		}
-		// Fallback for filesystems (like old XFS) that don't
-		// support Dirent.Type and have DT_UNKNOWN (0) there
-		// instead.
-		if typ == unknownFileMode {
-			fi, err := os.Lstat(dirName + "/" + name)
-			if err != nil {
-				// It got deleted in the meantime.
-				if os.IsNotExist(err) {
-					continue
-				}
-				return err
-			}
-			typ = fi.Mode() & os.ModeType
-		}
-		if err := fn(dirName, name, typ); err != nil {
-			return err
-		}
-	}
-}
-
-func parseDirEnt(buf []byte) (consumed int, name string, typ os.FileMode) {
-	// golang.org/issue/15653
-	dirent := (*syscall.Dirent)(unsafe.Pointer(&buf[0]))
-	if v := unsafe.Offsetof(dirent.Reclen) + unsafe.Sizeof(dirent.Reclen); uintptr(len(buf)) < v {
-		panic(fmt.Sprintf("buf size of %d smaller than dirent header size %d", len(buf), v))
-	}
-	if len(buf) < int(dirent.Reclen) {
-		panic(fmt.Sprintf("buf size %d < record length %d", len(buf), dirent.Reclen))
-	}
-	consumed = int(dirent.Reclen)
-	if direntInode(dirent) == 0 { // File absent in directory.
-		return
-	}
-	switch dirent.Type {
-	case syscall.DT_REG:
-		typ = 0
-	case syscall.DT_DIR:
-		typ = os.ModeDir
-	case syscall.DT_LNK:
-		typ = os.ModeSymlink
-	case syscall.DT_BLK:
-		typ = os.ModeDevice
-	case syscall.DT_FIFO:
-		typ = os.ModeNamedPipe
-	case syscall.DT_SOCK:
-		typ = os.ModeSocket
-	case syscall.DT_UNKNOWN:
-		typ = unknownFileMode
-	default:
-		// Skip weird things.
-		// It's probably a DT_WHT (http://lwn.net/Articles/325369/)
-		// or something. Revisit if/when this package is moved outside
-		// of goimports. goimports only cares about regular files,
-		// symlinks, and directories.
-		return
-	}
-
-	nameBuf := (*[unsafe.Sizeof(dirent.Name)]byte)(unsafe.Pointer(&dirent.Name[0]))
-	nameLen := bytes.IndexByte(nameBuf[:], 0)
-	if nameLen < 0 {
-		panic("failed to find terminating 0 byte in dirent")
-	}
-
-	// Special cases for common things:
-	if nameLen == 1 && nameBuf[0] == '.' {
-		name = "."
-	} else if nameLen == 2 && nameBuf[0] == '.' && nameBuf[1] == '.' {
-		name = ".."
-	} else {
-		name = string(nameBuf[:nameLen])
-	}
-	return
-}
diff --git a/imports/fix.go b/imports/fix.go
index 68961ba65..73f939a13 100644
--- a/imports/fix.go
+++ b/imports/fix.go
@@ -22,6 +22,7 @@ import (
 	"sync"
 
 	"golang.org/x/tools/go/ast/astutil"
+	"golang.org/x/tools/internal/fastwalk"
 )
 
 // Debug controls verbose logging.
@@ -545,16 +546,13 @@ func skipDir(fi os.FileInfo) bool {
 	return false
 }
 
-// shouldTraverse reports whether the symlink fi should, found in dir,
+// shouldTraverse reports whether the symlink fi, found in dir,
 // should be followed.  It makes sure symlinks were never visited
 // before to avoid symlink loops.
 func shouldTraverse(dir string, fi os.FileInfo) bool {
 	path := filepath.Join(dir, fi.Name())
 	target, err := filepath.EvalSymlinks(path)
 	if err != nil {
-		if !os.IsNotExist(err) {
-			fmt.Fprintln(os.Stderr, err)
-		}
 		return false
 	}
 	ts, err := os.Stat(target)
@@ -674,12 +672,12 @@ func scanGoDirs(goRoot bool) {
 					return nil
 				}
 				if shouldTraverse(dir, fi) {
-					return traverseLink
+					return fastwalk.TraverseLink
 				}
 			}
 			return nil
 		}
-		if err := fastWalk(srcDir, walkFn); err != nil {
+		if err := fastwalk.Walk(srcDir, walkFn); err != nil {
 			log.Printf("goimports: scanning directory %v: %v", srcDir, err)
 		}
 	}