1 // Copyright 2013 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
28 "golang.org/x/tools/go/ast/astutil"
29 "mvdan.cc/gofumpt/gofumports/internal/gocommand"
30 "mvdan.cc/gofumpt/gofumports/internal/gopathwalk"
33 // importToGroup is a list of functions which map from an import path to
35 var importToGroup = []func(localPrefix, importPath string) (num int, ok bool){
36 func(localPrefix, importPath string) (num int, ok bool) {
37 if localPrefix == "" {
40 for _, p := range strings.Split(localPrefix, ",") {
41 if strings.HasPrefix(importPath, p) || strings.TrimSuffix(p, "/") == importPath {
47 func(_, importPath string) (num int, ok bool) {
48 if strings.HasPrefix(importPath, "appengine") {
53 func(_, importPath string) (num int, ok bool) {
54 firstComponent := strings.Split(importPath, "/")[0]
55 if strings.Contains(firstComponent, ".") {
62 func importGroup(localPrefix, importPath string) int {
63 for _, fn := range importToGroup {
64 if n, ok := fn(localPrefix, importPath); ok {
71 type ImportFixType int
74 AddImport ImportFixType = iota
79 type ImportFix struct {
80 // StmtInfo represents the import statement this fix will add, remove, or change.
82 // IdentName is the identifier that this fix will add or remove.
84 // FixType is the type of fix this is (AddImport, DeleteImport, SetImportName).
86 Relevance float64 // see pkg
89 // An ImportInfo represents a single import statement.
90 type ImportInfo struct {
91 ImportPath string // import path, e.g. "crypto/rand".
92 Name string // import name, e.g. "crand", or "" if none.
95 // A packageInfo represents what's known about a package.
96 type packageInfo struct {
97 name string // real package name, if known.
98 exports map[string]bool // known exports.
101 // parseOtherFiles parses all the Go files in srcDir except filename, including
102 // test files if filename looks like a test.
103 func parseOtherFiles(fset *token.FileSet, srcDir, filename string) []*ast.File {
104 // This could use go/packages but it doesn't buy much, and it fails
105 // with https://golang.org/issue/26296 in LoadFiles mode in some cases.
106 considerTests := strings.HasSuffix(filename, "_test.go")
108 fileBase := filepath.Base(filename)
109 packageFileInfos, err := ioutil.ReadDir(srcDir)
114 var files []*ast.File
115 for _, fi := range packageFileInfos {
116 if fi.Name() == fileBase || !strings.HasSuffix(fi.Name(), ".go") {
119 if !considerTests && strings.HasSuffix(fi.Name(), "_test.go") {
123 f, err := parser.ParseFile(fset, filepath.Join(srcDir, fi.Name()), nil, 0)
128 files = append(files, f)
134 // addGlobals puts the names of package vars into the provided map.
135 func addGlobals(f *ast.File, globals map[string]bool) {
136 for _, decl := range f.Decls {
137 genDecl, ok := decl.(*ast.GenDecl)
142 for _, spec := range genDecl.Specs {
143 valueSpec, ok := spec.(*ast.ValueSpec)
147 globals[valueSpec.Names[0].Name] = true
152 // collectReferences builds a map of selector expressions, from
153 // left hand side (X) to a set of right hand sides (Sel).
154 func collectReferences(f *ast.File) references {
158 visitor = func(node ast.Node) ast.Visitor {
162 switch v := node.(type) {
163 case *ast.SelectorExpr:
164 xident, ok := v.X.(*ast.Ident)
168 if xident.Obj != nil {
169 // If the parser can resolve it, it's not a package ref.
172 if !ast.IsExported(v.Sel.Name) {
173 // Whatever this is, it's not exported from a package.
176 pkgName := xident.Name
179 r = make(map[string]bool)
190 // collectImports returns all the imports in f.
191 // Unnamed imports (., _) and "C" are ignored.
192 func collectImports(f *ast.File) []*ImportInfo {
193 var imports []*ImportInfo
194 for _, imp := range f.Imports {
199 if imp.Path.Value == `"C"` || name == "_" || name == "." {
202 path := strings.Trim(imp.Path.Value, `"`)
203 imports = append(imports, &ImportInfo{
211 // findMissingImport searches pass's candidates for an import that provides
212 // pkg, containing all of syms.
213 func (p *pass) findMissingImport(pkg string, syms map[string]bool) *ImportInfo {
214 for _, candidate := range p.candidates {
215 pkgInfo, ok := p.knownPackages[candidate.ImportPath]
219 if p.importIdentifier(candidate) != pkg {
224 for right := range syms {
225 if !pkgInfo.exports[right] {
238 // references is set of references found in a Go file. The first map key is the
239 // left hand side of a selector expression, the second key is the right hand
240 // side, and the value should always be true.
241 type references map[string]map[string]bool
243 // A pass contains all the inputs and state necessary to fix a file's imports.
244 // It can be modified in some ways during use; see comments below.
246 // Inputs. These must be set before a call to load, and not modified after.
247 fset *token.FileSet // fset used to parse f and its siblings.
248 f *ast.File // the file being fixed.
249 srcDir string // the directory containing f.
250 env *ProcessEnv // the environment to use for go commands, etc.
251 loadRealPackageNames bool // if true, load package names from disk rather than guessing them.
252 otherFiles []*ast.File // sibling files.
254 // Intermediate state, generated by load.
255 existingImports map[string]*ImportInfo
257 missingRefs references
259 // Inputs to fix. These can be augmented between successive fix calls.
260 lastTry bool // indicates that this is the last call and fix should clean up as best it can.
261 candidates []*ImportInfo // candidate imports in priority order.
262 knownPackages map[string]*packageInfo // information about all known packages.
265 // loadPackageNames saves the package names for everything referenced by imports.
266 func (p *pass) loadPackageNames(imports []*ImportInfo) error {
267 if p.env.Logf != nil {
268 p.env.Logf("loading package names for %v packages", len(imports))
270 p.env.Logf("done loading package names for %v packages", len(imports))
274 for _, imp := range imports {
275 if _, ok := p.knownPackages[imp.ImportPath]; ok {
278 unknown = append(unknown, imp.ImportPath)
281 resolver, err := p.env.GetResolver()
286 names, err := resolver.loadPackageNames(unknown, p.srcDir)
291 for path, name := range names {
292 p.knownPackages[path] = &packageInfo{
294 exports: map[string]bool{},
300 // importIdentifier returns the identifier that imp will introduce. It will
301 // guess if the package name has not been loaded, e.g. because the source
303 func (p *pass) importIdentifier(imp *ImportInfo) string {
307 known := p.knownPackages[imp.ImportPath]
308 if known != nil && known.name != "" {
311 return ImportPathToAssumedName(imp.ImportPath)
314 // load reads in everything necessary to run a pass, and reports whether the
315 // file already has all the imports it needs. It fills in p.missingRefs with the
316 // file's missing symbols, if any, or removes unused imports if not.
317 func (p *pass) load() ([]*ImportFix, bool) {
318 p.knownPackages = map[string]*packageInfo{}
319 p.missingRefs = references{}
320 p.existingImports = map[string]*ImportInfo{}
322 // Load basic information about the file in question.
323 p.allRefs = collectReferences(p.f)
325 // Load stuff from other files in the same package:
326 // global variables so we know they don't need resolving, and imports
327 // that we might want to mimic.
328 globals := map[string]bool{}
329 for _, otherFile := range p.otherFiles {
330 // Don't load globals from files that are in the same directory
331 // but a different package. Using them to suggest imports is OK.
332 if p.f.Name.Name == otherFile.Name.Name {
333 addGlobals(otherFile, globals)
335 p.candidates = append(p.candidates, collectImports(otherFile)...)
338 // Resolve all the import paths we've seen to package names, and store
339 // f's imports by the identifier they introduce.
340 imports := collectImports(p.f)
341 if p.loadRealPackageNames {
342 err := p.loadPackageNames(append(imports, p.candidates...))
344 if p.env.Logf != nil {
345 p.env.Logf("loading package names: %v", err)
350 for _, imp := range imports {
351 p.existingImports[p.importIdentifier(imp)] = imp
354 // Find missing references.
355 for left, rights := range p.allRefs {
359 _, ok := p.existingImports[left]
361 p.missingRefs[left] = rights
365 if len(p.missingRefs) != 0 {
372 // fix attempts to satisfy missing imports using p.candidates. If it finds
373 // everything, or if p.lastTry is true, it updates fixes to add the imports it found,
374 // delete anything unused, and update import names, and returns true.
375 func (p *pass) fix() ([]*ImportFix, bool) {
376 // Find missing imports.
377 var selected []*ImportInfo
378 for left, rights := range p.missingRefs {
379 if imp := p.findMissingImport(left, rights); imp != nil {
380 selected = append(selected, imp)
384 if !p.lastTry && len(selected) != len(p.missingRefs) {
388 // Found everything, or giving up. Add the new imports and remove any unused.
389 var fixes []*ImportFix
390 for _, imp := range p.existingImports {
391 // We deliberately ignore globals here, because we can't be sure
392 // they're in the same package. People do things like put multiple
393 // main packages in the same directory, and we don't want to
394 // remove imports if they happen to have the same name as a var in
395 // a different package.
396 if _, ok := p.allRefs[p.importIdentifier(imp)]; !ok {
397 fixes = append(fixes, &ImportFix{
399 IdentName: p.importIdentifier(imp),
400 FixType: DeleteImport,
405 // An existing import may need to update its import name to be correct.
406 if name := p.importSpecName(imp); name != imp.Name {
407 fixes = append(fixes, &ImportFix{
408 StmtInfo: ImportInfo{
410 ImportPath: imp.ImportPath,
412 IdentName: p.importIdentifier(imp),
413 FixType: SetImportName,
418 for _, imp := range selected {
419 fixes = append(fixes, &ImportFix{
420 StmtInfo: ImportInfo{
421 Name: p.importSpecName(imp),
422 ImportPath: imp.ImportPath,
424 IdentName: p.importIdentifier(imp),
432 // importSpecName gets the import name of imp in the import spec.
434 // When the import identifier matches the assumed import name, the import name does
435 // not appear in the import spec.
436 func (p *pass) importSpecName(imp *ImportInfo) string {
437 // If we did not load the real package names, or the name is already set,
438 // we just return the existing name.
439 if !p.loadRealPackageNames || imp.Name != "" {
443 ident := p.importIdentifier(imp)
444 if ident == ImportPathToAssumedName(imp.ImportPath) {
445 return "" // ident not needed since the assumed and real names are the same.
450 // apply will perform the fixes on f in order.
451 func apply(fset *token.FileSet, f *ast.File, fixes []*ImportFix) {
452 for _, fix := range fixes {
455 astutil.DeleteNamedImport(fset, f, fix.StmtInfo.Name, fix.StmtInfo.ImportPath)
457 astutil.AddNamedImport(fset, f, fix.StmtInfo.Name, fix.StmtInfo.ImportPath)
459 // Find the matching import path and change the name.
460 for _, spec := range f.Imports {
461 path := strings.Trim(spec.Path.Value, `"`)
462 if path == fix.StmtInfo.ImportPath {
463 spec.Name = &ast.Ident{
464 Name: fix.StmtInfo.Name,
473 // assumeSiblingImportsValid assumes that siblings' use of packages is valid,
474 // adding the exports they use.
475 func (p *pass) assumeSiblingImportsValid() {
476 for _, f := range p.otherFiles {
477 refs := collectReferences(f)
478 imports := collectImports(f)
479 importsByName := map[string]*ImportInfo{}
480 for _, imp := range imports {
481 importsByName[p.importIdentifier(imp)] = imp
483 for left, rights := range refs {
484 if imp, ok := importsByName[left]; ok {
485 if m, ok := stdlib[imp.ImportPath]; ok {
486 // We have the stdlib in memory; no need to guess.
487 rights = copyExports(m)
489 p.addCandidate(imp, &packageInfo{
490 // no name; we already know it.
498 // addCandidate adds a candidate import to p, and merges in the information
500 func (p *pass) addCandidate(imp *ImportInfo, pkg *packageInfo) {
501 p.candidates = append(p.candidates, imp)
502 if existing, ok := p.knownPackages[imp.ImportPath]; ok {
503 if existing.name == "" {
504 existing.name = pkg.name
506 for export := range pkg.exports {
507 existing.exports[export] = true
510 p.knownPackages[imp.ImportPath] = pkg
514 // fixImports adds and removes imports from f so that all its references are
515 // satisfied and there are no unused imports.
517 // This is declared as a variable rather than a function so goimports can
518 // easily be extended by adding a file with an init function.
519 var fixImports = fixImportsDefault
521 func fixImportsDefault(fset *token.FileSet, f *ast.File, filename string, env *ProcessEnv) error {
522 fixes, err := getFixes(fset, f, filename, env)
526 apply(fset, f, fixes)
530 // getFixes gets the import fixes that need to be made to f in order to fix the imports.
531 // It does not modify the ast.
532 func getFixes(fset *token.FileSet, f *ast.File, filename string, env *ProcessEnv) ([]*ImportFix, error) {
533 abs, err := filepath.Abs(filename)
537 srcDir := filepath.Dir(abs)
539 env.Logf("fixImports(filename=%q), abs=%q, srcDir=%q ...", filename, abs, srcDir)
542 // First pass: looking only at f, and using the naive algorithm to
543 // derive package names from import paths, see if the file is already
544 // complete. We can't add any imports yet, because we don't know
545 // if missing references are actually package vars.
546 p := &pass{fset: fset, f: f, srcDir: srcDir, env: env}
547 if fixes, done := p.load(); done {
551 otherFiles := parseOtherFiles(fset, srcDir, filename)
553 // Second pass: add information from other files in the same package,
554 // like their package vars and imports.
555 p.otherFiles = otherFiles
556 if fixes, done := p.load(); done {
560 // Now we can try adding imports from the stdlib.
561 p.assumeSiblingImportsValid()
562 addStdlibCandidates(p, p.missingRefs)
563 if fixes, done := p.fix(); done {
567 // Third pass: get real package names where we had previously used
568 // the naive algorithm.
569 p = &pass{fset: fset, f: f, srcDir: srcDir, env: env}
570 p.loadRealPackageNames = true
571 p.otherFiles = otherFiles
572 if fixes, done := p.load(); done {
576 if err := addStdlibCandidates(p, p.missingRefs); err != nil {
579 p.assumeSiblingImportsValid()
580 if fixes, done := p.fix(); done {
584 // Go look for candidates in $GOPATH, etc. We don't necessarily load
585 // the real exports of sibling imports, so keep assuming their contents.
586 if err := addExternalCandidates(p, p.missingRefs, filename); err != nil {
595 // MaxRelevance is the highest relevance, used for the standard library.
596 // Chosen arbitrarily to match pre-existing gopls code.
597 const MaxRelevance = 7.0
599 // getCandidatePkgs works with the passed callback to find all acceptable packages.
600 // It deduplicates by import path, and uses a cached stdlib rather than reading
602 func getCandidatePkgs(ctx context.Context, wrappedCallback *scanCallback, filename, filePkg string, env *ProcessEnv) error {
603 notSelf := func(p *pkg) bool {
604 return p.packageName != filePkg || p.dir != filepath.Dir(filename)
606 goenv, err := env.goEnv()
611 var mu sync.Mutex // to guard asynchronous access to dupCheck
612 dupCheck := map[string]struct{}{}
614 // Start off with the standard library.
615 for importPath, exports := range stdlib {
617 dir: filepath.Join(goenv["GOROOT"], "src", importPath),
618 importPathShort: importPath,
619 packageName: path.Base(importPath),
620 relevance: MaxRelevance,
622 dupCheck[importPath] = struct{}{}
623 if notSelf(p) && wrappedCallback.dirFound(p) && wrappedCallback.packageNameLoaded(p) {
624 wrappedCallback.exportsLoaded(p, exports)
628 scanFilter := &scanCallback{
629 rootFound: func(root gopathwalk.Root) bool {
630 // Exclude goroot results -- getting them is relatively expensive, not cached,
631 // and generally redundant with the in-memory version.
632 return root.Type != gopathwalk.RootGOROOT && wrappedCallback.rootFound(root)
634 dirFound: wrappedCallback.dirFound,
635 packageNameLoaded: func(pkg *pkg) bool {
638 if _, ok := dupCheck[pkg.importPathShort]; ok {
641 dupCheck[pkg.importPathShort] = struct{}{}
642 return notSelf(pkg) && wrappedCallback.packageNameLoaded(pkg)
644 exportsLoaded: func(pkg *pkg, exports []string) {
645 // If we're an x_test, load the package under test's test variant.
646 if strings.HasSuffix(filePkg, "_test") && pkg.dir == filepath.Dir(filename) {
648 _, exports, err = loadExportsFromFiles(ctx, env, pkg.dir, true)
653 wrappedCallback.exportsLoaded(pkg, exports)
656 resolver, err := env.GetResolver()
660 return resolver.scan(ctx, scanFilter)
663 func ScoreImportPaths(ctx context.Context, env *ProcessEnv, paths []string) (map[string]float64, error) {
664 result := make(map[string]float64)
665 resolver, err := env.GetResolver()
669 for _, path := range paths {
670 result[path] = resolver.scoreImportPath(ctx, path)
675 func PrimeCache(ctx context.Context, env *ProcessEnv) error {
676 // Fully scan the disk for directories, but don't actually read any Go files.
677 callback := &scanCallback{
678 rootFound: func(gopathwalk.Root) bool {
681 dirFound: func(pkg *pkg) bool {
684 packageNameLoaded: func(pkg *pkg) bool {
688 return getCandidatePkgs(ctx, callback, "", "", env)
691 func candidateImportName(pkg *pkg) string {
692 if ImportPathToAssumedName(pkg.importPathShort) != pkg.packageName {
693 return pkg.packageName
698 // GetAllCandidates calls wrapped for each package whose name starts with
699 // searchPrefix, and can be imported from filename with the package name filePkg.
700 func GetAllCandidates(ctx context.Context, wrapped func(ImportFix), searchPrefix, filename, filePkg string, env *ProcessEnv) error {
701 callback := &scanCallback{
702 rootFound: func(gopathwalk.Root) bool {
705 dirFound: func(pkg *pkg) bool {
706 if !canUse(filename, pkg.dir) {
709 // Try the assumed package name first, then a simpler path match
710 // in case of packages named vN, which are not uncommon.
711 return strings.HasPrefix(ImportPathToAssumedName(pkg.importPathShort), searchPrefix) ||
712 strings.HasPrefix(path.Base(pkg.importPathShort), searchPrefix)
714 packageNameLoaded: func(pkg *pkg) bool {
715 if !strings.HasPrefix(pkg.packageName, searchPrefix) {
719 StmtInfo: ImportInfo{
720 ImportPath: pkg.importPathShort,
721 Name: candidateImportName(pkg),
723 IdentName: pkg.packageName,
725 Relevance: pkg.relevance,
730 return getCandidatePkgs(ctx, callback, filename, filePkg, env)
733 // GetImportPaths calls wrapped for each package whose import path starts with
734 // searchPrefix, and can be imported from filename with the package name filePkg.
735 func GetImportPaths(ctx context.Context, wrapped func(ImportFix), searchPrefix, filename, filePkg string, env *ProcessEnv) error {
736 callback := &scanCallback{
737 rootFound: func(gopathwalk.Root) bool {
740 dirFound: func(pkg *pkg) bool {
741 if !canUse(filename, pkg.dir) {
744 return strings.HasPrefix(pkg.importPathShort, searchPrefix)
746 packageNameLoaded: func(pkg *pkg) bool {
748 StmtInfo: ImportInfo{
749 ImportPath: pkg.importPathShort,
750 Name: candidateImportName(pkg),
752 IdentName: pkg.packageName,
754 Relevance: pkg.relevance,
759 return getCandidatePkgs(ctx, callback, filename, filePkg, env)
762 // A PackageExport is a package and its exports.
763 type PackageExport struct {
768 // GetPackageExports returns all known packages with name pkg and their exports.
769 func GetPackageExports(ctx context.Context, wrapped func(PackageExport), searchPkg, filename, filePkg string, env *ProcessEnv) error {
770 callback := &scanCallback{
771 rootFound: func(gopathwalk.Root) bool {
774 dirFound: func(pkg *pkg) bool {
775 return pkgIsCandidate(filename, references{searchPkg: nil}, pkg)
777 packageNameLoaded: func(pkg *pkg) bool {
778 return pkg.packageName == searchPkg
780 exportsLoaded: func(pkg *pkg, exports []string) {
781 sort.Strings(exports)
782 wrapped(PackageExport{
784 StmtInfo: ImportInfo{
785 ImportPath: pkg.importPathShort,
786 Name: candidateImportName(pkg),
788 IdentName: pkg.packageName,
790 Relevance: pkg.relevance,
796 return getCandidatePkgs(ctx, callback, filename, filePkg, env)
799 var RequiredGoEnvVars = []string{"GO111MODULE", "GOFLAGS", "GOINSECURE", "GOMOD", "GOMODCACHE", "GONOPROXY", "GONOSUMDB", "GOPATH", "GOPROXY", "GOROOT", "GOSUMDB"}
801 // ProcessEnv contains environment variables and settings that affect the use of
802 // the go command, the go/build package, etc.
803 type ProcessEnv struct {
804 GocmdRunner *gocommand.Runner
810 // Env overrides the OS environment, and can be used to specify
811 // GOPROXY, GO111MODULE, etc. PATH cannot be set here, because
812 // exec.Command will not honor it.
813 // Specifying all of RequiredGoEnvVars avoids a call to `go env`.
814 Env map[string]string
818 // If Logf is non-nil, debug logging is enabled through this function.
819 Logf func(format string, args ...interface{})
826 func (e *ProcessEnv) goEnv() (map[string]string, error) {
827 if err := e.init(); err != nil {
833 func (e *ProcessEnv) matchFile(dir, name string) (bool, error) {
834 bctx, err := e.buildContext()
838 return bctx.MatchFile(dir, name)
841 // CopyConfig copies the env's configuration into a new env.
842 func (e *ProcessEnv) CopyConfig() *ProcessEnv {
844 GocmdRunner: e.GocmdRunner,
845 initialized: e.initialized,
846 BuildFlags: e.BuildFlags,
848 WorkingDir: e.WorkingDir,
850 Env: map[string]string{},
852 for k, v := range e.Env {
858 func (e *ProcessEnv) init() error {
863 foundAllRequired := true
864 for _, k := range RequiredGoEnvVars {
865 if _, ok := e.Env[k]; !ok {
866 foundAllRequired = false
870 if foundAllRequired {
876 e.Env = map[string]string{}
879 goEnv := map[string]string{}
880 stdout, err := e.invokeGo(context.TODO(), "env", append([]string{"-json"}, RequiredGoEnvVars...)...)
884 if err := json.Unmarshal(stdout.Bytes(), &goEnv); err != nil {
887 for k, v := range goEnv {
894 func (e *ProcessEnv) env() []string {
895 var env []string // the gocommand package will prepend os.Environ.
896 for k, v := range e.Env {
897 env = append(env, k+"="+v)
902 func (e *ProcessEnv) GetResolver() (Resolver, error) {
903 if e.resolver != nil {
904 return e.resolver, nil
906 if err := e.init(); err != nil {
909 if len(e.Env["GOMOD"]) == 0 {
910 e.resolver = newGopathResolver(e)
911 return e.resolver, nil
913 e.resolver = newModuleResolver(e)
914 return e.resolver, nil
917 func (e *ProcessEnv) buildContext() (*build.Context, error) {
919 goenv, err := e.goEnv()
923 ctx.GOROOT = goenv["GOROOT"]
924 ctx.GOPATH = goenv["GOPATH"]
926 // As of Go 1.14, build.Context has a Dir field
927 // (see golang.org/issue/34860).
928 // Populate it only if present.
929 rc := reflect.ValueOf(&ctx).Elem()
930 dir := rc.FieldByName("Dir")
931 if dir.IsValid() && dir.Kind() == reflect.String {
932 dir.SetString(e.WorkingDir)
935 // Since Go 1.11, go/build.Context.Import may invoke 'go list' depending on
936 // the value in GO111MODULE in the process's environment. We always want to
937 // run in GOPATH mode when calling Import, so we need to prevent this from
938 // happening. In Go 1.16, GO111MODULE defaults to "on", so this problem comes
939 // up more frequently.
941 // HACK: setting any of the Context I/O hooks prevents Import from invoking
942 // 'go list', regardless of GO111MODULE. This is undocumented, but it's
943 // unlikely to change before GOPATH support is removed.
944 ctx.ReadDir = ioutil.ReadDir
949 func (e *ProcessEnv) invokeGo(ctx context.Context, verb string, args ...string) (*bytes.Buffer, error) {
950 inv := gocommand.Invocation{
953 BuildFlags: e.BuildFlags,
956 WorkingDir: e.WorkingDir,
958 return e.GocmdRunner.Run(ctx, inv)
961 func addStdlibCandidates(pass *pass, refs references) error {
962 goenv, err := pass.env.goEnv()
966 add := func(pkg string) {
967 // Prevent self-imports.
968 if path.Base(pkg) == pass.f.Name.Name && filepath.Join(goenv["GOROOT"], "src", pkg) == pass.srcDir {
971 exports := copyExports(stdlib[pkg])
973 &ImportInfo{ImportPath: pkg},
974 &packageInfo{name: path.Base(pkg), exports: exports})
976 for left := range refs {
978 // Make sure we try crypto/rand before math/rand.
983 for importPath := range stdlib {
984 if path.Base(importPath) == left {
992 // A Resolver does the build-system-specific parts of goimports.
993 type Resolver interface {
994 // loadPackageNames loads the package names in importPaths.
995 loadPackageNames(importPaths []string, srcDir string) (map[string]string, error)
996 // scan works with callback to search for packages. See scanCallback for details.
997 scan(ctx context.Context, callback *scanCallback) error
998 // loadExports returns the set of exported symbols in the package at dir.
999 // loadExports may be called concurrently.
1000 loadExports(ctx context.Context, pkg *pkg, includeTest bool) (string, []string, error)
1001 // scoreImportPath returns the relevance for an import path.
1002 scoreImportPath(ctx context.Context, path string) float64
1007 // A scanCallback controls a call to scan and receives its results.
1008 // In general, minor errors will be silently discarded; a user should not
1009 // expect to receive a full series of calls for everything.
1010 type scanCallback struct {
1011 // rootFound is called before scanning a new root dir. If it returns true,
1012 // the root will be scanned. Returning false will not necessarily prevent
1013 // directories from that root making it to dirFound.
1014 rootFound func(gopathwalk.Root) bool
1015 // dirFound is called when a directory is found that is possibly a Go package.
1016 // pkg will be populated with everything except packageName.
1017 // If it returns true, the package's name will be loaded.
1018 dirFound func(pkg *pkg) bool
1019 // packageNameLoaded is called when a package is found and its name is loaded.
1020 // If it returns true, the package's exports will be loaded.
1021 packageNameLoaded func(pkg *pkg) bool
1022 // exportsLoaded is called when a package's exports have been loaded.
1023 exportsLoaded func(pkg *pkg, exports []string)
1026 func addExternalCandidates(pass *pass, refs references, filename string) error {
1028 found := make(map[string][]pkgDistance)
1029 callback := &scanCallback{
1030 rootFound: func(gopathwalk.Root) bool {
1031 return true // We want everything.
1033 dirFound: func(pkg *pkg) bool {
1034 return pkgIsCandidate(filename, refs, pkg)
1036 packageNameLoaded: func(pkg *pkg) bool {
1037 if _, want := refs[pkg.packageName]; !want {
1040 if pkg.dir == pass.srcDir && pass.f.Name.Name == pkg.packageName {
1041 // The candidate is in the same directory and has the
1042 // same package name. Don't try to import ourselves.
1045 if !canUse(filename, pkg.dir) {
1050 found[pkg.packageName] = append(found[pkg.packageName], pkgDistance{pkg, distance(pass.srcDir, pkg.dir)})
1051 return false // We'll do our own loading after we sort.
1054 resolver, err := pass.env.GetResolver()
1058 if err = resolver.scan(context.Background(), callback); err != nil {
1062 // Search for imports matching potential package references.
1063 type result struct {
1067 results := make(chan result, len(refs))
1069 ctx, cancel := context.WithCancel(context.TODO())
1070 var wg sync.WaitGroup
1077 firstErrOnce sync.Once
1079 for pkgName, symbols := range refs {
1081 go func(pkgName string, symbols map[string]bool) {
1084 found, err := findImport(ctx, pass, found[pkgName], pkgName, symbols, filename)
1086 firstErrOnce.Do(func() {
1094 return // No matching package.
1098 ImportPath: found.importPathShort,
1101 pkg := &packageInfo{
1105 results <- result{imp, pkg}
1113 for result := range results {
1114 pass.addCandidate(result.imp, result.pkg)
1119 // notIdentifier reports whether ch is an invalid identifier character.
1120 func notIdentifier(ch rune) bool {
1121 return !('a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' ||
1122 '0' <= ch && ch <= '9' ||
1124 ch >= utf8.RuneSelf && (unicode.IsLetter(ch) || unicode.IsDigit(ch)))
1127 // ImportPathToAssumedName returns the assumed package name of an import path.
1128 // It does this using only string parsing of the import path.
1129 // It picks the last element of the path that does not look like a major
1130 // version, and then picks the valid identifier off the start of that element.
1131 // It is used to determine if a local rename should be added to an import for
1133 // This function could be moved to a standard package and exported if we want
1134 // for use in other tools.
1135 func ImportPathToAssumedName(importPath string) string {
1136 base := path.Base(importPath)
1137 if strings.HasPrefix(base, "v") {
1138 if _, err := strconv.Atoi(base[1:]); err == nil {
1139 dir := path.Dir(importPath)
1141 base = path.Base(dir)
1145 base = strings.TrimPrefix(base, "go-")
1146 if i := strings.IndexFunc(base, notIdentifier); i >= 0 {
1152 // gopathResolver implements resolver for GOPATH workspaces.
1153 type gopathResolver struct {
1157 scanSema chan struct{} // scanSema prevents concurrent scans.
1160 func newGopathResolver(env *ProcessEnv) *gopathResolver {
1161 r := &gopathResolver{
1163 cache: &dirInfoCache{
1164 dirs: map[string]*directoryPackageInfo{},
1165 listeners: map[*int]cacheListener{},
1167 scanSema: make(chan struct{}, 1),
1169 r.scanSema <- struct{}{}
1173 func (r *gopathResolver) ClearForNewScan() {
1175 r.cache = &dirInfoCache{
1176 dirs: map[string]*directoryPackageInfo{},
1177 listeners: map[*int]cacheListener{},
1180 r.scanSema <- struct{}{}
1183 func (r *gopathResolver) loadPackageNames(importPaths []string, srcDir string) (map[string]string, error) {
1184 names := map[string]string{}
1185 bctx, err := r.env.buildContext()
1189 for _, path := range importPaths {
1190 names[path] = importPathToName(bctx, path, srcDir)
1195 // importPathToName finds out the actual package name, as declared in its .go files.
1196 func importPathToName(bctx *build.Context, importPath, srcDir string) string {
1197 // Fast path for standard library without going to disk.
1198 if _, ok := stdlib[importPath]; ok {
1199 return path.Base(importPath) // stdlib packages always match their paths.
1202 buildPkg, err := bctx.Import(importPath, srcDir, build.FindOnly)
1206 pkgName, err := packageDirToName(buildPkg.Dir)
1213 // packageDirToName is a faster version of build.Import if
1214 // the only thing desired is the package name. Given a directory,
1215 // packageDirToName then only parses one file in the package,
1216 // trusting that the files in the directory are consistent.
1217 func packageDirToName(dir string) (packageName string, err error) {
1218 d, err := os.Open(dir)
1222 names, err := d.Readdirnames(-1)
1227 sort.Strings(names) // to have predictable behavior
1230 for _, name := range names {
1231 if !strings.HasSuffix(name, ".go") {
1234 if strings.HasSuffix(name, "_test.go") {
1238 fullFile := filepath.Join(dir, name)
1240 fset := token.NewFileSet()
1241 f, err := parser.ParseFile(fset, fullFile, nil, parser.PackageClauseOnly)
1246 pkgName := f.Name.Name
1247 if pkgName == "documentation" {
1248 // Special case from go/build.ImportDir, not
1249 // handled by ctx.MatchFile.
1252 if pkgName == "main" {
1253 // Also skip package main, assuming it's a +build ignore generator or example.
1254 // Since you can't import a package main anyway, there's no harm here.
1262 return "", fmt.Errorf("no importable package found in %d Go files", nfile)
1266 dir string // absolute file path to pkg directory ("/usr/lib/go/src/net/http")
1267 importPathShort string // vendorless import path ("net/http", "a/b")
1268 packageName string // package name loaded from source if requested
1269 relevance float64 // a weakly-defined score of how relevant a package is. 0 is most relevant.
1272 type pkgDistance struct {
1274 distance int // relative distance to target
1277 // byDistanceOrImportPathShortLength sorts by relative distance breaking ties
1278 // on the short import path length and then the import string itself.
1279 type byDistanceOrImportPathShortLength []pkgDistance
1281 func (s byDistanceOrImportPathShortLength) Len() int { return len(s) }
1282 func (s byDistanceOrImportPathShortLength) Less(i, j int) bool {
1283 di, dj := s[i].distance, s[j].distance
1294 vi, vj := s[i].pkg.importPathShort, s[j].pkg.importPathShort
1295 if len(vi) != len(vj) {
1296 return len(vi) < len(vj)
1300 func (s byDistanceOrImportPathShortLength) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
1302 func distance(basepath, targetpath string) int {
1303 p, err := filepath.Rel(basepath, targetpath)
1310 return strings.Count(p, string(filepath.Separator)) + 1
1313 func (r *gopathResolver) scan(ctx context.Context, callback *scanCallback) error {
1314 add := func(root gopathwalk.Root, dir string) {
1315 // We assume cached directories have not changed. We can skip them and their
1317 if _, ok := r.cache.Load(dir); ok {
1321 importpath := filepath.ToSlash(dir[len(root.Path)+len("/"):])
1322 info := directoryPackageInfo{
1323 status: directoryScanned,
1325 rootType: root.Type,
1326 nonCanonicalImportPath: VendorlessPath(importpath),
1328 r.cache.Store(dir, info)
1330 processDir := func(info directoryPackageInfo) {
1331 // Skip this directory if we were not able to get the package information successfully.
1332 if scanned, err := info.reachedStatus(directoryScanned); !scanned || err != nil {
1337 importPathShort: info.nonCanonicalImportPath,
1339 relevance: MaxRelevance - 1,
1341 if info.rootType == gopathwalk.RootGOROOT {
1342 p.relevance = MaxRelevance
1345 if !callback.dirFound(p) {
1349 p.packageName, err = r.cache.CachePackageName(info)
1354 if !callback.packageNameLoaded(p) {
1357 if _, exports, err := r.loadExports(ctx, p, false); err == nil {
1358 callback.exportsLoaded(p, exports)
1361 stop := r.cache.ScanAndListen(ctx, processDir)
1364 goenv, err := r.env.goEnv()
1368 var roots []gopathwalk.Root
1369 roots = append(roots, gopathwalk.Root{filepath.Join(goenv["GOROOT"], "src"), gopathwalk.RootGOROOT})
1370 for _, p := range filepath.SplitList(goenv["GOPATH"]) {
1371 roots = append(roots, gopathwalk.Root{filepath.Join(p, "src"), gopathwalk.RootGOPATH})
1373 // The callback is not necessarily safe to use in the goroutine below. Process roots eagerly.
1374 roots = filterRoots(roots, callback.rootFound)
1375 // We can't cancel walks, because we need them to finish to have a usable
1376 // cache. Instead, run them in a separate goroutine and detach.
1377 scanDone := make(chan struct{})
1384 defer func() { r.scanSema <- struct{}{} }()
1385 gopathwalk.Walk(roots, add, gopathwalk.Options{Logf: r.env.Logf, ModulesEnabled: false})
1395 func (r *gopathResolver) scoreImportPath(ctx context.Context, path string) float64 {
1396 if _, ok := stdlib[path]; ok {
1399 return MaxRelevance - 1
1402 func filterRoots(roots []gopathwalk.Root, include func(gopathwalk.Root) bool) []gopathwalk.Root {
1403 var result []gopathwalk.Root
1404 for _, root := range roots {
1408 result = append(result, root)
1413 func (r *gopathResolver) loadExports(ctx context.Context, pkg *pkg, includeTest bool) (string, []string, error) {
1414 if info, ok := r.cache.Load(pkg.dir); ok && !includeTest {
1415 return r.cache.CacheExports(ctx, r.env, info)
1417 return loadExportsFromFiles(ctx, r.env, pkg.dir, includeTest)
1420 // VendorlessPath returns the devendorized version of the import path ipath.
1421 // For example, VendorlessPath("foo/bar/vendor/a/b") returns "a/b".
1422 func VendorlessPath(ipath string) string {
1423 // Devendorize for use in import statement.
1424 if i := strings.LastIndex(ipath, "/vendor/"); i >= 0 {
1425 return ipath[i+len("/vendor/"):]
1427 if strings.HasPrefix(ipath, "vendor/") {
1428 return ipath[len("vendor/"):]
1433 func loadExportsFromFiles(ctx context.Context, env *ProcessEnv, dir string, includeTest bool) (string, []string, error) {
1434 // Look for non-test, buildable .go files which could provide exports.
1435 all, err := ioutil.ReadDir(dir)
1439 var files []os.FileInfo
1440 for _, fi := range all {
1442 if !strings.HasSuffix(name, ".go") || (!includeTest && strings.HasSuffix(name, "_test.go")) {
1445 match, err := env.matchFile(dir, fi.Name())
1446 if err != nil || !match {
1449 files = append(files, fi)
1452 if len(files) == 0 {
1453 return "", nil, fmt.Errorf("dir %v contains no buildable, non-test .go files", dir)
1457 var exports []string
1458 fset := token.NewFileSet()
1459 for _, fi := range files {
1462 return "", nil, ctx.Err()
1466 fullFile := filepath.Join(dir, fi.Name())
1467 f, err := parser.ParseFile(fset, fullFile, nil, 0)
1469 if env.Logf != nil {
1470 env.Logf("error parsing %v: %v", fullFile, err)
1474 if f.Name.Name == "documentation" {
1475 // Special case from go/build.ImportDir, not
1476 // handled by MatchFile above.
1479 if includeTest && strings.HasSuffix(f.Name.Name, "_test") {
1480 // x_test package. We want internal test files only.
1483 pkgName = f.Name.Name
1484 for name := range f.Scope.Objects {
1485 if ast.IsExported(name) {
1486 exports = append(exports, name)
1491 if env.Logf != nil {
1492 sortedExports := append([]string(nil), exports...)
1493 sort.Strings(sortedExports)
1494 env.Logf("loaded exports in dir %v (package %v): %v", dir, pkgName, strings.Join(sortedExports, ", "))
1496 return pkgName, exports, nil
1499 // findImport searches for a package with the given symbols.
1500 // If no package is found, findImport returns ("", false, nil)
1501 func findImport(ctx context.Context, pass *pass, candidates []pkgDistance, pkgName string, symbols map[string]bool, filename string) (*pkg, error) {
1502 // Sort the candidates by their import package length,
1503 // assuming that shorter package names are better than long
1504 // ones. Note that this sorts by the de-vendored name, so
1505 // there's no "penalty" for vendoring.
1506 sort.Sort(byDistanceOrImportPathShortLength(candidates))
1507 if pass.env.Logf != nil {
1508 for i, c := range candidates {
1509 pass.env.Logf("%s candidate %d/%d: %v in %v", pkgName, i+1, len(candidates), c.pkg.importPathShort, c.pkg.dir)
1512 resolver, err := pass.env.GetResolver()
1517 // Collect exports for packages with matching names.
1518 rescv := make([]chan *pkg, len(candidates))
1519 for i := range candidates {
1520 rescv[i] = make(chan *pkg, 1)
1522 const maxConcurrentPackageImport = 4
1523 loadExportsSem := make(chan struct{}, maxConcurrentPackageImport)
1525 ctx, cancel := context.WithCancel(ctx)
1526 var wg sync.WaitGroup
1535 for i, c := range candidates {
1537 case loadExportsSem <- struct{}{}:
1543 go func(c pkgDistance, resc chan<- *pkg) {
1549 if pass.env.Logf != nil {
1550 pass.env.Logf("loading exports in dir %s (seeking package %s)", c.pkg.dir, pkgName)
1552 // If we're an x_test, load the package under test's test variant.
1553 includeTest := strings.HasSuffix(pass.f.Name.Name, "_test") && c.pkg.dir == pass.srcDir
1554 _, exports, err := resolver.loadExports(ctx, c.pkg, includeTest)
1556 if pass.env.Logf != nil {
1557 pass.env.Logf("loading exports in dir %s (seeking package %s): %v", c.pkg.dir, pkgName, err)
1563 exportsMap := make(map[string]bool, len(exports))
1564 for _, sym := range exports {
1565 exportsMap[sym] = true
1568 // If it doesn't have the right
1569 // symbols, send nil to mean no match.
1570 for symbol := range symbols {
1571 if !exportsMap[symbol] {
1581 for _, resc := range rescv {
1591 // pkgIsCandidate reports whether pkg is a candidate for satisfying the
1592 // finding which package pkgIdent in the file named by filename is trying
1595 // This check is purely lexical and is meant to be as fast as possible
1596 // because it's run over all $GOPATH directories to filter out poor
1597 // candidates in order to limit the CPU and I/O later parsing the
1598 // exports in candidate packages.
1600 // filename is the file being formatted.
1601 // pkgIdent is the package being searched for, like "client" (if
1602 // searching for "client.New")
1603 func pkgIsCandidate(filename string, refs references, pkg *pkg) bool {
1604 // Check "internal" and "vendor" visibility:
1605 if !canUse(filename, pkg.dir) {
1609 // Speed optimization to minimize disk I/O:
1610 // the last two components on disk must contain the
1611 // package name somewhere.
1613 // This permits mismatch naming like directory
1614 // "go-foo" being package "foo", or "pkg.v3" being "pkg",
1615 // or directory "google.golang.org/api/cloudbilling/v1"
1616 // being package "cloudbilling", but doesn't
1617 // permit a directory "foo" to be package
1618 // "bar", which is strongly discouraged
1619 // anyway. There's no reason goimports needs
1620 // to be slow just to accommodate that.
1621 for pkgIdent := range refs {
1622 lastTwo := lastTwoComponents(pkg.importPathShort)
1623 if strings.Contains(lastTwo, pkgIdent) {
1626 if hasHyphenOrUpperASCII(lastTwo) && !hasHyphenOrUpperASCII(pkgIdent) {
1627 lastTwo = lowerASCIIAndRemoveHyphen(lastTwo)
1628 if strings.Contains(lastTwo, pkgIdent) {
1636 func hasHyphenOrUpperASCII(s string) bool {
1637 for i := 0; i < len(s); i++ {
1639 if b == '-' || ('A' <= b && b <= 'Z') {
1646 func lowerASCIIAndRemoveHyphen(s string) (ret string) {
1647 buf := make([]byte, 0, len(s))
1648 for i := 0; i < len(s); i++ {
1653 case 'A' <= b && b <= 'Z':
1654 buf = append(buf, b+('a'-'A'))
1656 buf = append(buf, b)
1662 // canUse reports whether the package in dir is usable from filename,
1663 // respecting the Go "internal" and "vendor" visibility rules.
1664 func canUse(filename, dir string) bool {
1665 // Fast path check, before any allocations. If it doesn't contain vendor
1666 // or internal, it's not tricky:
1667 // Note that this can false-negative on directories like "notinternal",
1668 // but we check it correctly below. This is just a fast path.
1669 if !strings.Contains(dir, "vendor") && !strings.Contains(dir, "internal") {
1673 dirSlash := filepath.ToSlash(dir)
1674 if !strings.Contains(dirSlash, "/vendor/") && !strings.Contains(dirSlash, "/internal/") && !strings.HasSuffix(dirSlash, "/internal") {
1677 // Vendor or internal directory only visible from children of parent.
1678 // That means the path from the current directory to the target directory
1679 // can contain ../vendor or ../internal but not ../foo/vendor or ../foo/internal
1680 // or bar/vendor or bar/internal.
1681 // After stripping all the leading ../, the only okay place to see vendor or internal
1682 // is at the very beginning of the path.
1683 absfile, err := filepath.Abs(filename)
1687 absdir, err := filepath.Abs(dir)
1691 rel, err := filepath.Rel(absfile, absdir)
1695 relSlash := filepath.ToSlash(rel)
1696 if i := strings.LastIndex(relSlash, "../"); i >= 0 {
1697 relSlash = relSlash[i+len("../"):]
1699 return !strings.Contains(relSlash, "/vendor/") && !strings.Contains(relSlash, "/internal/") && !strings.HasSuffix(relSlash, "/internal")
1702 // lastTwoComponents returns at most the last two path components
1703 // of v, using either / or \ as the path separator.
1704 func lastTwoComponents(v string) string {
1706 for i := len(v) - 1; i >= 0; i-- {
1707 if v[i] == '/' || v[i] == '\\' {
1717 type visitFn func(node ast.Node) ast.Visitor
1719 func (fn visitFn) Visit(node ast.Node) ast.Visitor {
1723 func copyExports(pkg []string) map[string]bool {
1724 m := make(map[string]bool, len(pkg))
1725 for _, v := range pkg {