2 files changed, 804 insertions, 0 deletions
diff --git a/src/cmd/go/internal/search/search.go b/src/cmd/go/internal/search/search.go
new file mode 100644
index 0000000..18738cf
--- /dev/null
+++ b/src/cmd/go/internal/search/search.go
@@ -0,0 +1,639 @@
+// Copyright 2017 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 search
+
+import (
+	"cmd/go/internal/base"
+	"cmd/go/internal/cfg"
+	"cmd/go/internal/fsys"
+	"fmt"
+	"go/build"
+	"io/fs"
+	"os"
+	"path"
+	"path/filepath"
+	"regexp"
+	"strings"
+)
+
+// A Match represents the result of matching a single package pattern.
+type Match struct {
+	pattern string   // the pattern itself
+	Dirs    []string // if the pattern is local, directories that potentially contain matching packages
+	Pkgs    []string // matching packages (import paths)
+	Errs    []error  // errors matching the patterns to packages, NOT errors loading those packages
+
+	// Errs may be non-empty even if len(Pkgs) > 0, indicating that some matching
+	// packages could be located but results may be incomplete.
+	// If len(Pkgs) == 0 && len(Errs) == 0, the pattern is well-formed but did not
+	// match any packages.
+}
+
+// NewMatch returns a Match describing the given pattern,
+// without resolving its packages or errors.
+func NewMatch(pattern string) *Match {
+	return &Match{pattern: pattern}
+}
+
+// Pattern returns the pattern to be matched.
+func (m *Match) Pattern() string { return m.pattern }
+
+// AddError appends a MatchError wrapping err to m.Errs.
+func (m *Match) AddError(err error) {
+	m.Errs = append(m.Errs, &MatchError{Match: m, Err: err})
+}
+
+// Literal reports whether the pattern is free of wildcards and meta-patterns.
+//
+// A literal pattern must match at most one package.
+func (m *Match) IsLiteral() bool {
+	return !strings.Contains(m.pattern, "...") && !m.IsMeta()
+}
+
+// Local reports whether the pattern must be resolved from a specific root or
+// directory, such as a filesystem path or a single module.
+func (m *Match) IsLocal() bool {
+	return build.IsLocalImport(m.pattern) || filepath.IsAbs(m.pattern)
+}
+
+// Meta reports whether the pattern is a “meta-package” keyword that represents
+// multiple packages, such as "std", "cmd", or "all".
+func (m *Match) IsMeta() bool {
+	return IsMetaPackage(m.pattern)
+}
+
+// IsMetaPackage checks if name is a reserved package name that expands to multiple packages.
+func IsMetaPackage(name string) bool {
+	return name == "std" || name == "cmd" || name == "all"
+}
+
+// A MatchError indicates an error that occurred while attempting to match a
+// pattern.
+type MatchError struct {
+	Match *Match
+	Err   error
+}
+
+func (e *MatchError) Error() string {
+	if e.Match.IsLiteral() {
+		return fmt.Sprintf("%s: %v", e.Match.Pattern(), e.Err)
+	}
+	return fmt.Sprintf("pattern %s: %v", e.Match.Pattern(), e.Err)
+}
+
+func (e *MatchError) Unwrap() error {
+	return e.Err
+}
+
+// MatchPackages sets m.Pkgs to a non-nil slice containing all the packages that
+// can be found under the $GOPATH directories and $GOROOT that match the
+// pattern. The pattern must be either "all" (all packages), "std" (standard
+// packages), "cmd" (standard commands), or a path including "...".
+//
+// If any errors may have caused the set of packages to be incomplete,
+// MatchPackages appends those errors to m.Errs.
+func (m *Match) MatchPackages() {
+	m.Pkgs = []string{}
+	if m.IsLocal() {
+		m.AddError(fmt.Errorf("internal error: MatchPackages: %s is not a valid package pattern", m.pattern))
+		return
+	}
+
+	if m.IsLiteral() {
+		m.Pkgs = []string{m.pattern}
+		return
+	}
+
+	match := func(string) bool { return true }
+	treeCanMatch := func(string) bool { return true }
+	if !m.IsMeta() {
+		match = MatchPattern(m.pattern)
+		treeCanMatch = TreeCanMatchPattern(m.pattern)
+	}
+
+	have := map[string]bool{
+		"builtin": true, // ignore pseudo-package that exists only for documentation
+	}
+	if !cfg.BuildContext.CgoEnabled {
+		have["runtime/cgo"] = true // ignore during walk
+	}
+
+	for _, src := range cfg.BuildContext.SrcDirs() {
+		if (m.pattern == "std" || m.pattern == "cmd") && src != cfg.GOROOTsrc {
+			continue
+		}
+		src = filepath.Clean(src) + string(filepath.Separator)
+		root := src
+		if m.pattern == "cmd" {
+			root += "cmd" + string(filepath.Separator)
+		}
+		err := fsys.Walk(root, func(path string, fi fs.FileInfo, err error) error {
+			if err != nil {
+				return err // Likely a permission error, which could interfere with matching.
+			}
+			if path == src {
+				return nil // GOROOT/src and GOPATH/src cannot contain packages.
+			}
+
+			want := true
+			// Avoid .foo, _foo, and testdata directory trees.
+			_, elem := filepath.Split(path)
+			if strings.HasPrefix(elem, ".") || strings.HasPrefix(elem, "_") || elem == "testdata" {
+				want = false
+			}
+
+			name := filepath.ToSlash(path[len(src):])
+			if m.pattern == "std" && (!IsStandardImportPath(name) || name == "cmd") {
+				// The name "std" is only the standard library.
+				// If the name is cmd, it's the root of the command tree.
+				want = false
+			}
+			if !treeCanMatch(name) {
+				want = false
+			}
+
+			if !fi.IsDir() {
+				if fi.Mode()&fs.ModeSymlink != 0 && want {
+					if target, err := fsys.Stat(path); err == nil && target.IsDir() {
+						fmt.Fprintf(os.Stderr, "warning: ignoring symlink %s\n", path)
+					}
+				}
+				return nil
+			}
+			if !want {
+				return filepath.SkipDir
+			}
+
+			if have[name] {
+				return nil
+			}
+			have[name] = true
+			if !match(name) {
+				return nil
+			}
+			pkg, err := cfg.BuildContext.ImportDir(path, 0)
+			if err != nil {
+				if _, noGo := err.(*build.NoGoError); noGo {
+					// The package does not actually exist, so record neither the package
+					// nor the error.
+					return nil
+				}
+				// There was an error importing path, but not matching it,
+				// which is all that Match promises to do.
+				// Ignore the import error.
+			}
+
+			// If we are expanding "cmd", skip main
+			// packages under cmd/vendor. At least as of
+			// March, 2017, there is one there for the
+			// vendored pprof tool.
+			if m.pattern == "cmd" && pkg != nil && strings.HasPrefix(pkg.ImportPath, "cmd/vendor") && pkg.Name == "main" {
+				return nil
+			}
+
+			m.Pkgs = append(m.Pkgs, name)
+			return nil
+		})
+		if err != nil {
+			m.AddError(err)
+		}
+	}
+}
+
+var modRoot string
+
+func SetModRoot(dir string) {
+	modRoot = dir
+}
+
+// MatchDirs sets m.Dirs to a non-nil slice containing all directories that
+// potentially match a local pattern. The pattern must begin with an absolute
+// path, or "./", or "../". On Windows, the pattern may use slash or backslash
+// separators or a mix of both.
+//
+// If any errors may have caused the set of directories to be incomplete,
+// MatchDirs appends those errors to m.Errs.
+func (m *Match) MatchDirs() {
+	m.Dirs = []string{}
+	if !m.IsLocal() {
+		m.AddError(fmt.Errorf("internal error: MatchDirs: %s is not a valid filesystem pattern", m.pattern))
+		return
+	}
+
+	if m.IsLiteral() {
+		m.Dirs = []string{m.pattern}
+		return
+	}
+
+	// Clean the path and create a matching predicate.
+	// filepath.Clean removes "./" prefixes (and ".\" on Windows). We need to
+	// preserve these, since they are meaningful in MatchPattern and in
+	// returned import paths.
+	cleanPattern := filepath.Clean(m.pattern)
+	isLocal := strings.HasPrefix(m.pattern, "./") || (os.PathSeparator == '\\' && strings.HasPrefix(m.pattern, `.\`))
+	prefix := ""
+	if cleanPattern != "." && isLocal {
+		prefix = "./"
+		cleanPattern = "." + string(os.PathSeparator) + cleanPattern
+	}
+	slashPattern := filepath.ToSlash(cleanPattern)
+	match := MatchPattern(slashPattern)
+
+	// Find directory to begin the scan.
+	// Could be smarter but this one optimization
+	// is enough for now, since ... is usually at the
+	// end of a path.
+	i := strings.Index(cleanPattern, "...")
+	dir, _ := filepath.Split(cleanPattern[:i])
+
+	// pattern begins with ./ or ../.
+	// path.Clean will discard the ./ but not the ../.
+	// We need to preserve the ./ for pattern matching
+	// and in the returned import paths.
+
+	if modRoot != "" {
+		abs, err := filepath.Abs(dir)
+		if err != nil {
+			m.AddError(err)
+			return
+		}
+		if !hasFilepathPrefix(abs, modRoot) {
+			m.AddError(fmt.Errorf("directory %s is outside module root (%s)", abs, modRoot))
+			return
+		}
+	}
+
+	err := fsys.Walk(dir, func(path string, fi fs.FileInfo, err error) error {
+		if err != nil {
+			return err // Likely a permission error, which could interfere with matching.
+		}
+		if !fi.IsDir() {
+			return nil
+		}
+		top := false
+		if path == dir {
+			// Walk starts at dir and recurses. For the recursive case,
+			// the path is the result of filepath.Join, which calls filepath.Clean.
+			// The initial case is not Cleaned, though, so we do this explicitly.
+			//
+			// This converts a path like "./io/" to "io". Without this step, running
+			// "cd $GOROOT/src; go list ./io/..." would incorrectly skip the io
+			// package, because prepending the prefix "./" to the unclean path would
+			// result in "././io", and match("././io") returns false.
+			top = true
+			path = filepath.Clean(path)
+		}
+
+		// Avoid .foo, _foo, and testdata directory trees, but do not avoid "." or "..".
+		_, elem := filepath.Split(path)
+		dot := strings.HasPrefix(elem, ".") && elem != "." && elem != ".."
+		if dot || strings.HasPrefix(elem, "_") || elem == "testdata" {
+			return filepath.SkipDir
+		}
+
+		if !top && cfg.ModulesEnabled {
+			// Ignore other modules found in subdirectories.
+			if fi, err := fsys.Stat(filepath.Join(path, "go.mod")); err == nil && !fi.IsDir() {
+				return filepath.SkipDir
+			}
+		}
+
+		name := prefix + filepath.ToSlash(path)
+		if !match(name) {
+			return nil
+		}
+
+		// We keep the directory if we can import it, or if we can't import it
+		// due to invalid Go source files. This means that directories containing
+		// parse errors will be built (and fail) instead of being silently skipped
+		// as not matching the pattern. Go 1.5 and earlier skipped, but that
+		// behavior means people miss serious mistakes.
+		// See golang.org/issue/11407.
+		if p, err := cfg.BuildContext.ImportDir(path, 0); err != nil && (p == nil || len(p.InvalidGoFiles) == 0) {
+			if _, noGo := err.(*build.NoGoError); noGo {
+				// The package does not actually exist, so record neither the package
+				// nor the error.
+				return nil
+			}
+			// There was an error importing path, but not matching it,
+			// which is all that Match promises to do.
+			// Ignore the import error.
+		}
+		m.Dirs = append(m.Dirs, name)
+		return nil
+	})
+	if err != nil {
+		m.AddError(err)
+	}
+}
+
+// TreeCanMatchPattern(pattern)(name) reports whether
+// name or children of name can possibly match pattern.
+// Pattern is the same limited glob accepted by matchPattern.
+func TreeCanMatchPattern(pattern string) func(name string) bool {
+	wildCard := false
+	if i := strings.Index(pattern, "..."); i >= 0 {
+		wildCard = true
+		pattern = pattern[:i]
+	}
+	return func(name string) bool {
+		return len(name) <= len(pattern) && hasPathPrefix(pattern, name) ||
+			wildCard && strings.HasPrefix(name, pattern)
+	}
+}
+
+// MatchPattern(pattern)(name) reports whether
+// name matches pattern. Pattern is a limited glob
+// pattern in which '...' means 'any string' and there
+// is no other special syntax.
+// Unfortunately, there are two special cases. Quoting "go help packages":
+//
+// First, /... at the end of the pattern can match an empty string,
+// so that net/... matches both net and packages in its subdirectories, like net/http.
+// Second, any slash-separated pattern element containing a wildcard never
+// participates in a match of the "vendor" element in the path of a vendored
+// package, so that ./... does not match packages in subdirectories of
+// ./vendor or ./mycode/vendor, but ./vendor/... and ./mycode/vendor/... do.
+// Note, however, that a directory named vendor that itself contains code
+// is not a vendored package: cmd/vendor would be a command named vendor,
+// and the pattern cmd/... matches it.
+func MatchPattern(pattern string) func(name string) bool {
+	// Convert pattern to regular expression.
+	// The strategy for the trailing /... is to nest it in an explicit ? expression.
+	// The strategy for the vendor exclusion is to change the unmatchable
+	// vendor strings to a disallowed code point (vendorChar) and to use
+	// "(anything but that codepoint)*" as the implementation of the ... wildcard.
+	// This is a bit complicated but the obvious alternative,
+	// namely a hand-written search like in most shell glob matchers,
+	// is too easy to make accidentally exponential.
+	// Using package regexp guarantees linear-time matching.
+
+	const vendorChar = "\x00"
+
+	if strings.Contains(pattern, vendorChar) {
+		return func(name string) bool { return false }
+	}
+
+	re := regexp.QuoteMeta(pattern)
+	re = replaceVendor(re, vendorChar)
+	switch {
+	case strings.HasSuffix(re, `/`+vendorChar+`/\.\.\.`):
+		re = strings.TrimSuffix(re, `/`+vendorChar+`/\.\.\.`) + `(/vendor|/` + vendorChar + `/\.\.\.)`
+	case re == vendorChar+`/\.\.\.`:
+		re = `(/vendor|/` + vendorChar + `/\.\.\.)`
+	case strings.HasSuffix(re, `/\.\.\.`):
+		re = strings.TrimSuffix(re, `/\.\.\.`) + `(/\.\.\.)?`
+	}
+	re = strings.ReplaceAll(re, `\.\.\.`, `[^`+vendorChar+`]*`)
+
+	reg := regexp.MustCompile(`^` + re + `$`)
+
+	return func(name string) bool {
+		if strings.Contains(name, vendorChar) {
+			return false
+		}
+		return reg.MatchString(replaceVendor(name, vendorChar))
+	}
+}
+
+// replaceVendor returns the result of replacing
+// non-trailing vendor path elements in x with repl.
+func replaceVendor(x, repl string) string {
+	if !strings.Contains(x, "vendor") {
+		return x
+	}
+	elem := strings.Split(x, "/")
+	for i := 0; i < len(elem)-1; i++ {
+		if elem[i] == "vendor" {
+			elem[i] = repl
+		}
+	}
+	return strings.Join(elem, "/")
+}
+
+// WarnUnmatched warns about patterns that didn't match any packages.
+func WarnUnmatched(matches []*Match) {
+	for _, m := range matches {
+		if len(m.Pkgs) == 0 && len(m.Errs) == 0 {
+			fmt.Fprintf(os.Stderr, "go: warning: %q matched no packages\n", m.pattern)
+		}
+	}
+}
+
+// ImportPaths returns the matching paths to use for the given command line.
+// It calls ImportPathsQuiet and then WarnUnmatched.
+func ImportPaths(patterns []string) []*Match {
+	matches := ImportPathsQuiet(patterns)
+	WarnUnmatched(matches)
+	return matches
+}
+
+// ImportPathsQuiet is like ImportPaths but does not warn about patterns with no matches.
+func ImportPathsQuiet(patterns []string) []*Match {
+	var out []*Match
+	for _, a := range CleanPatterns(patterns) {
+		m := NewMatch(a)
+		if m.IsLocal() {
+			m.MatchDirs()
+
+			// Change the file import path to a regular import path if the package
+			// is in GOPATH or GOROOT. We don't report errors here; LoadImport
+			// (or something similar) will report them later.
+			m.Pkgs = make([]string, len(m.Dirs))
+			for i, dir := range m.Dirs {
+				absDir := dir
+				if !filepath.IsAbs(dir) {
+					absDir = filepath.Join(base.Cwd, dir)
+				}
+				if bp, _ := cfg.BuildContext.ImportDir(absDir, build.FindOnly); bp.ImportPath != "" && bp.ImportPath != "." {
+					m.Pkgs[i] = bp.ImportPath
+				} else {
+					m.Pkgs[i] = dir
+				}
+			}
+		} else {
+			m.MatchPackages()
+		}
+
+		out = append(out, m)
+	}
+	return out
+}
+
+// CleanPatterns returns the patterns to use for the given command line. It
+// canonicalizes the patterns but does not evaluate any matches. For patterns
+// that are not local or absolute paths, it preserves text after '@' to avoid
+// modifying version queries.
+func CleanPatterns(patterns []string) []string {
+	if len(patterns) == 0 {
+		return []string{"."}
+	}
+	var out []string
+	for _, a := range patterns {
+		var p, v string
+		if build.IsLocalImport(a) || filepath.IsAbs(a) {
+			p = a
+		} else if i := strings.IndexByte(a, '@'); i < 0 {
+			p = a
+		} else {
+			p = a[:i]
+			v = a[i:]
+		}
+
+		// Arguments may be either file paths or import paths.
+		// As a courtesy to Windows developers, rewrite \ to /
+		// in arguments that look like import paths.
+		// Don't replace slashes in absolute paths.
+		if filepath.IsAbs(p) {
+			p = filepath.Clean(p)
+		} else {
+			if filepath.Separator == '\\' {
+				p = strings.ReplaceAll(p, `\`, `/`)
+			}
+
+			// Put argument in canonical form, but preserve leading ./.
+			if strings.HasPrefix(p, "./") {
+				p = "./" + path.Clean(p)
+				if p == "./." {
+					p = "."
+				}
+			} else {
+				p = path.Clean(p)
+			}
+		}
+
+		out = append(out, p+v)
+	}
+	return out
+}
+
+// hasPathPrefix reports whether the path s begins with the
+// elements in prefix.
+func hasPathPrefix(s, prefix string) bool {
+	switch {
+	default:
+		return false
+	case len(s) == len(prefix):
+		return s == prefix
+	case len(s) > len(prefix):
+		if prefix != "" && prefix[len(prefix)-1] == '/' {
+			return strings.HasPrefix(s, prefix)
+		}
+		return s[len(prefix)] == '/' && s[:len(prefix)] == prefix
+	}
+}
+
+// hasFilepathPrefix reports whether the path s begins with the
+// elements in prefix.
+func hasFilepathPrefix(s, prefix string) bool {
+	switch {
+	default:
+		return false
+	case len(s) == len(prefix):
+		return s == prefix
+	case len(s) > len(prefix):
+		if prefix != "" && prefix[len(prefix)-1] == filepath.Separator {
+			return strings.HasPrefix(s, prefix)
+		}
+		return s[len(prefix)] == filepath.Separator && s[:len(prefix)] == prefix
+	}
+}
+
+// IsStandardImportPath reports whether $GOROOT/src/path should be considered
+// part of the standard distribution. For historical reasons we allow people to add
+// their own code to $GOROOT instead of using $GOPATH, but we assume that
+// code will start with a domain name (dot in the first element).
+//
+// Note that this function is meant to evaluate whether a directory found in GOROOT
+// should be treated as part of the standard library. It should not be used to decide
+// that a directory found in GOPATH should be rejected: directories in GOPATH
+// need not have dots in the first element, and they just take their chances
+// with future collisions in the standard library.
+func IsStandardImportPath(path string) bool {
+	i := strings.Index(path, "/")
+	if i < 0 {
+		i = len(path)
+	}
+	elem := path[:i]
+	return !strings.Contains(elem, ".")
+}
+
+// IsRelativePath reports whether pattern should be interpreted as a directory
+// path relative to the current directory, as opposed to a pattern matching
+// import paths.
+func IsRelativePath(pattern string) bool {
+	return strings.HasPrefix(pattern, "./") || strings.HasPrefix(pattern, "../") || pattern == "." || pattern == ".."
+}
+
+// InDir checks whether path is in the file tree rooted at dir.
+// If so, InDir returns an equivalent path relative to dir.
+// If not, InDir returns an empty string.
+// InDir makes some effort to succeed even in the presence of symbolic links.
+// TODO(rsc): Replace internal/test.inDir with a call to this function for Go 1.12.
+func InDir(path, dir string) string {
+	if rel := inDirLex(path, dir); rel != "" {
+		return rel
+	}
+	xpath, err := filepath.EvalSymlinks(path)
+	if err != nil || xpath == path {
+		xpath = ""
+	} else {
+		if rel := inDirLex(xpath, dir); rel != "" {
+			return rel
+		}
+	}
+
+	xdir, err := filepath.EvalSymlinks(dir)
+	if err == nil && xdir != dir {
+		if rel := inDirLex(path, xdir); rel != "" {
+			return rel
+		}
+		if xpath != "" {
+			if rel := inDirLex(xpath, xdir); rel != "" {
+				return rel
+			}
+		}
+	}
+	return ""
+}
+
+// inDirLex is like inDir but only checks the lexical form of the file names.
+// It does not consider symbolic links.
+// TODO(rsc): This is a copy of str.HasFilePathPrefix, modified to
+// return the suffix. Most uses of str.HasFilePathPrefix should probably
+// be calling InDir instead.
+func inDirLex(path, dir string) string {
+	pv := strings.ToUpper(filepath.VolumeName(path))
+	dv := strings.ToUpper(filepath.VolumeName(dir))
+	path = path[len(pv):]
+	dir = dir[len(dv):]
+	switch {
+	default:
+		return ""
+	case pv != dv:
+		return ""
+	case len(path) == len(dir):
+		if path == dir {
+			return "."
+		}
+		return ""
+	case dir == "":
+		return path
+	case len(path) > len(dir):
+		if dir[len(dir)-1] == filepath.Separator {
+			if path[:len(dir)] == dir {
+				return path[len(dir):]
+			}
+			return ""
+		}
+		if path[len(dir)] == filepath.Separator && path[:len(dir)] == dir {
+			if len(path) == len(dir)+1 {
+				return "."
+			}
+			return path[len(dir)+1:]
+		}
+		return ""
+	}
+}
diff --git a/src/cmd/go/internal/search/search_test.go b/src/cmd/go/internal/search/search_test.go
new file mode 100644
index 0000000..5f27daf
--- /dev/null
+++ b/src/cmd/go/internal/search/search_test.go
@@ -0,0 +1,165 @@
+// Copyright 2012 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 search
+
+import (
+	"strings"
+	"testing"
+)
+
+var matchPatternTests = `
+	pattern ...
+	match foo
+	
+	pattern net
+	match net
+	not net/http
+	
+	pattern net/http
+	match net/http
+	not net
+	
+	pattern net...
+	match net net/http netchan
+	not not/http not/net/http
+	
+	# Special cases. Quoting docs:
+
+	# First, /... at the end of the pattern can match an empty string,
+	# so that net/... matches both net and packages in its subdirectories, like net/http.
+	pattern net/...
+	match net net/http
+	not not/http not/net/http netchan
+
+	# Second, any slash-separated pattern element containing a wildcard never
+	# participates in a match of the "vendor" element in the path of a vendored
+	# package, so that ./... does not match packages in subdirectories of
+	# ./vendor or ./mycode/vendor, but ./vendor/... and ./mycode/vendor/... do.
+	# Note, however, that a directory named vendor that itself contains code
+	# is not a vendored package: cmd/vendor would be a command named vendor,
+	# and the pattern cmd/... matches it.
+	pattern ./...
+	match ./vendor ./mycode/vendor
+	not ./vendor/foo ./mycode/vendor/foo
+	
+	pattern ./vendor/...
+	match ./vendor/foo ./vendor/foo/vendor
+	not ./vendor/foo/vendor/bar
+	
+	pattern mycode/vendor/...
+	match mycode/vendor mycode/vendor/foo mycode/vendor/foo/vendor
+	not mycode/vendor/foo/vendor/bar
+	
+	pattern x/vendor/y
+	match x/vendor/y
+	not x/vendor
+	
+	pattern x/vendor/y/...
+	match x/vendor/y x/vendor/y/z x/vendor/y/vendor x/vendor/y/z/vendor
+	not x/vendor/y/vendor/z
+	
+	pattern .../vendor/...
+	match x/vendor/y x/vendor/y/z x/vendor/y/vendor x/vendor/y/z/vendor
+`
+
+func TestMatchPattern(t *testing.T) {
+	testPatterns(t, "MatchPattern", matchPatternTests, func(pattern, name string) bool {
+		return MatchPattern(pattern)(name)
+	})
+}
+
+var treeCanMatchPatternTests = `
+	pattern ...
+	match foo
+	
+	pattern net
+	match net
+	not net/http
+	
+	pattern net/http
+	match net net/http
+	
+	pattern net...
+	match net netchan net/http
+	not not/http not/net/http
+
+	pattern net/...
+	match net net/http
+	not not/http netchan
+	
+	pattern abc.../def
+	match abcxyz
+	not xyzabc
+	
+	pattern x/y/z/...
+	match x x/y x/y/z x/y/z/w
+	
+	pattern x/y/z
+	match x x/y x/y/z
+	not x/y/z/w
+	
+	pattern x/.../y/z
+	match x/a/b/c
+	not y/x/a/b/c
+`
+
+func TestTreeCanMatchPattern(t *testing.T) {
+	testPatterns(t, "TreeCanMatchPattern", treeCanMatchPatternTests, func(pattern, name string) bool {
+		return TreeCanMatchPattern(pattern)(name)
+	})
+}
+
+var hasPathPrefixTests = []stringPairTest{
+	{"abc", "a", false},
+	{"a/bc", "a", true},
+	{"a", "a", true},
+	{"a/bc", "a/", true},
+}
+
+func TestHasPathPrefix(t *testing.T) {
+	testStringPairs(t, "hasPathPrefix", hasPathPrefixTests, hasPathPrefix)
+}
+
+type stringPairTest struct {
+	in1 string
+	in2 string
+	out bool
+}
+
+func testStringPairs(t *testing.T, name string, tests []stringPairTest, f func(string, string) bool) {
+	for _, tt := range tests {
+		if out := f(tt.in1, tt.in2); out != tt.out {
+			t.Errorf("%s(%q, %q) = %v, want %v", name, tt.in1, tt.in2, out, tt.out)
+		}
+	}
+}
+
+func testPatterns(t *testing.T, name, tests string, fn func(string, string) bool) {
+	var patterns []string
+	for _, line := range strings.Split(tests, "\n") {
+		if i := strings.Index(line, "#"); i >= 0 {
+			line = line[:i]
+		}
+		f := strings.Fields(line)
+		if len(f) == 0 {
+			continue
+		}
+		switch f[0] {
+		default:
+			t.Fatalf("unknown directive %q", f[0])
+		case "pattern":
+			patterns = f[1:]
+		case "match", "not":
+			want := f[0] == "match"
+			for _, pattern := range patterns {
+				for _, in := range f[1:] {
+					if fn(pattern, in) != want {
+						t.Errorf("%s(%q, %q) = %v, want %v", name, pattern, in, !want, want)
+					}
+				}
+			}
+		}
+	}
+}