diff options
Diffstat (limited to 'src/cmd/go/internal/search/search.go')
| -rw-r--r-- | src/cmd/go/internal/search/search.go | 639 |
1 files changed, 639 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 "" + } +} |