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. 4 5package imports 6 7import ( 8 "bytes" 9 "context" 10 "encoding/json" 11 "fmt" 12 "go/ast" 13 "go/build" 14 "go/parser" 15 "go/token" 16 "io/ioutil" 17 "os" 18 "path" 19 "path/filepath" 20 "reflect" 21 "sort" 22 "strconv" 23 "strings" 24 "sync" 25 "unicode" 26 "unicode/utf8" 27 28 "golang.org/x/tools/go/ast/astutil" 29 "golang.org/x/tools/internal/gocommand" 30 "golang.org/x/tools/internal/gopathwalk" 31) 32 33// importToGroup is a list of functions which map from an import path to 34// a group number. 35var importToGroup = []func(localPrefix, importPath string) (num int, ok bool){ 36 func(localPrefix, importPath string) (num int, ok bool) { 37 if localPrefix == "" { 38 return 39 } 40 for _, p := range strings.Split(localPrefix, ",") { 41 if strings.HasPrefix(importPath, p) || strings.TrimSuffix(p, "/") == importPath { 42 return 3, true 43 } 44 } 45 return 46 }, 47 func(_, importPath string) (num int, ok bool) { 48 if strings.HasPrefix(importPath, "appengine") { 49 return 2, true 50 } 51 return 52 }, 53 func(_, importPath string) (num int, ok bool) { 54 firstComponent := strings.Split(importPath, "/")[0] 55 if strings.Contains(firstComponent, ".") { 56 return 1, true 57 } 58 return 59 }, 60} 61 62func importGroup(localPrefix, importPath string) int { 63 for _, fn := range importToGroup { 64 if n, ok := fn(localPrefix, importPath); ok { 65 return n 66 } 67 } 68 return 0 69} 70 71type ImportFixType int 72 73const ( 74 AddImport ImportFixType = iota 75 DeleteImport 76 SetImportName 77) 78 79type ImportFix struct { 80 // StmtInfo represents the import statement this fix will add, remove, or change. 81 StmtInfo ImportInfo 82 // IdentName is the identifier that this fix will add or remove. 83 IdentName string 84 // FixType is the type of fix this is (AddImport, DeleteImport, SetImportName). 85 FixType ImportFixType 86 Relevance int // see pkg 87} 88 89// An ImportInfo represents a single import statement. 90type ImportInfo struct { 91 ImportPath string // import path, e.g. "crypto/rand". 92 Name string // import name, e.g. "crand", or "" if none. 93} 94 95// A packageInfo represents what's known about a package. 96type packageInfo struct { 97 name string // real package name, if known. 98 exports map[string]bool // known exports. 99} 100 101// parseOtherFiles parses all the Go files in srcDir except filename, including 102// test files if filename looks like a test. 103func 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") 107 108 fileBase := filepath.Base(filename) 109 packageFileInfos, err := ioutil.ReadDir(srcDir) 110 if err != nil { 111 return nil 112 } 113 114 var files []*ast.File 115 for _, fi := range packageFileInfos { 116 if fi.Name() == fileBase || !strings.HasSuffix(fi.Name(), ".go") { 117 continue 118 } 119 if !considerTests && strings.HasSuffix(fi.Name(), "_test.go") { 120 continue 121 } 122 123 f, err := parser.ParseFile(fset, filepath.Join(srcDir, fi.Name()), nil, 0) 124 if err != nil { 125 continue 126 } 127 128 files = append(files, f) 129 } 130 131 return files 132} 133 134// addGlobals puts the names of package vars into the provided map. 135func addGlobals(f *ast.File, globals map[string]bool) { 136 for _, decl := range f.Decls { 137 genDecl, ok := decl.(*ast.GenDecl) 138 if !ok { 139 continue 140 } 141 142 for _, spec := range genDecl.Specs { 143 valueSpec, ok := spec.(*ast.ValueSpec) 144 if !ok { 145 continue 146 } 147 globals[valueSpec.Names[0].Name] = true 148 } 149 } 150} 151 152// collectReferences builds a map of selector expressions, from 153// left hand side (X) to a set of right hand sides (Sel). 154func collectReferences(f *ast.File) references { 155 refs := references{} 156 157 var visitor visitFn 158 visitor = func(node ast.Node) ast.Visitor { 159 if node == nil { 160 return visitor 161 } 162 switch v := node.(type) { 163 case *ast.SelectorExpr: 164 xident, ok := v.X.(*ast.Ident) 165 if !ok { 166 break 167 } 168 if xident.Obj != nil { 169 // If the parser can resolve it, it's not a package ref. 170 break 171 } 172 if !ast.IsExported(v.Sel.Name) { 173 // Whatever this is, it's not exported from a package. 174 break 175 } 176 pkgName := xident.Name 177 r := refs[pkgName] 178 if r == nil { 179 r = make(map[string]bool) 180 refs[pkgName] = r 181 } 182 r[v.Sel.Name] = true 183 } 184 return visitor 185 } 186 ast.Walk(visitor, f) 187 return refs 188} 189 190// collectImports returns all the imports in f. 191// Unnamed imports (., _) and "C" are ignored. 192func collectImports(f *ast.File) []*ImportInfo { 193 var imports []*ImportInfo 194 for _, imp := range f.Imports { 195 var name string 196 if imp.Name != nil { 197 name = imp.Name.Name 198 } 199 if imp.Path.Value == `"C"` || name == "_" || name == "." { 200 continue 201 } 202 path := strings.Trim(imp.Path.Value, `"`) 203 imports = append(imports, &ImportInfo{ 204 Name: name, 205 ImportPath: path, 206 }) 207 } 208 return imports 209} 210 211// findMissingImport searches pass's candidates for an import that provides 212// pkg, containing all of syms. 213func (p *pass) findMissingImport(pkg string, syms map[string]bool) *ImportInfo { 214 for _, candidate := range p.candidates { 215 pkgInfo, ok := p.knownPackages[candidate.ImportPath] 216 if !ok { 217 continue 218 } 219 if p.importIdentifier(candidate) != pkg { 220 continue 221 } 222 223 allFound := true 224 for right := range syms { 225 if !pkgInfo.exports[right] { 226 allFound = false 227 break 228 } 229 } 230 231 if allFound { 232 return candidate 233 } 234 } 235 return nil 236} 237 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. 241type references map[string]map[string]bool 242 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. 245type pass struct { 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. 253 254 // Intermediate state, generated by load. 255 existingImports map[string]*ImportInfo 256 allRefs references 257 missingRefs references 258 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. 263} 264 265// loadPackageNames saves the package names for everything referenced by imports. 266func (p *pass) loadPackageNames(imports []*ImportInfo) error { 267 if p.env.Logf != nil { 268 p.env.Logf("loading package names for %v packages", len(imports)) 269 defer func() { 270 p.env.Logf("done loading package names for %v packages", len(imports)) 271 }() 272 } 273 var unknown []string 274 for _, imp := range imports { 275 if _, ok := p.knownPackages[imp.ImportPath]; ok { 276 continue 277 } 278 unknown = append(unknown, imp.ImportPath) 279 } 280 281 resolver, err := p.env.GetResolver() 282 if err != nil { 283 return err 284 } 285 286 names, err := resolver.loadPackageNames(unknown, p.srcDir) 287 if err != nil { 288 return err 289 } 290 291 for path, name := range names { 292 p.knownPackages[path] = &packageInfo{ 293 name: name, 294 exports: map[string]bool{}, 295 } 296 } 297 return nil 298} 299 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 302// is not available. 303func (p *pass) importIdentifier(imp *ImportInfo) string { 304 if imp.Name != "" { 305 return imp.Name 306 } 307 known := p.knownPackages[imp.ImportPath] 308 if known != nil && known.name != "" { 309 return known.name 310 } 311 return ImportPathToAssumedName(imp.ImportPath) 312} 313 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. 317func (p *pass) load() ([]*ImportFix, bool) { 318 p.knownPackages = map[string]*packageInfo{} 319 p.missingRefs = references{} 320 p.existingImports = map[string]*ImportInfo{} 321 322 // Load basic information about the file in question. 323 p.allRefs = collectReferences(p.f) 324 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) 334 } 335 p.candidates = append(p.candidates, collectImports(otherFile)...) 336 } 337 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...)) 343 if err != nil { 344 if p.env.Logf != nil { 345 p.env.Logf("loading package names: %v", err) 346 } 347 return nil, false 348 } 349 } 350 for _, imp := range imports { 351 p.existingImports[p.importIdentifier(imp)] = imp 352 } 353 354 // Find missing references. 355 for left, rights := range p.allRefs { 356 if globals[left] { 357 continue 358 } 359 _, ok := p.existingImports[left] 360 if !ok { 361 p.missingRefs[left] = rights 362 continue 363 } 364 } 365 if len(p.missingRefs) != 0 { 366 return nil, false 367 } 368 369 return p.fix() 370} 371 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. 375func (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) 381 } 382 } 383 384 if !p.lastTry && len(selected) != len(p.missingRefs) { 385 return nil, false 386 } 387 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{ 398 StmtInfo: *imp, 399 IdentName: p.importIdentifier(imp), 400 FixType: DeleteImport, 401 }) 402 continue 403 } 404 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{ 409 Name: name, 410 ImportPath: imp.ImportPath, 411 }, 412 IdentName: p.importIdentifier(imp), 413 FixType: SetImportName, 414 }) 415 } 416 } 417 418 for _, imp := range selected { 419 fixes = append(fixes, &ImportFix{ 420 StmtInfo: ImportInfo{ 421 Name: p.importSpecName(imp), 422 ImportPath: imp.ImportPath, 423 }, 424 IdentName: p.importIdentifier(imp), 425 FixType: AddImport, 426 }) 427 } 428 429 return fixes, true 430} 431 432// importSpecName gets the import name of imp in the import spec. 433// 434// When the import identifier matches the assumed import name, the import name does 435// not appear in the import spec. 436func (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 != "" { 440 return imp.Name 441 } 442 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. 446 } 447 return ident 448} 449 450// apply will perform the fixes on f in order. 451func apply(fset *token.FileSet, f *ast.File, fixes []*ImportFix) { 452 for _, fix := range fixes { 453 switch fix.FixType { 454 case DeleteImport: 455 astutil.DeleteNamedImport(fset, f, fix.StmtInfo.Name, fix.StmtInfo.ImportPath) 456 case AddImport: 457 astutil.AddNamedImport(fset, f, fix.StmtInfo.Name, fix.StmtInfo.ImportPath) 458 case SetImportName: 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, 465 NamePos: spec.Pos(), 466 } 467 } 468 } 469 } 470 } 471} 472 473// assumeSiblingImportsValid assumes that siblings' use of packages is valid, 474// adding the exports they use. 475func (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 482 } 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) 488 } 489 p.addCandidate(imp, &packageInfo{ 490 // no name; we already know it. 491 exports: rights, 492 }) 493 } 494 } 495 } 496} 497 498// addCandidate adds a candidate import to p, and merges in the information 499// in pkg. 500func (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 505 } 506 for export := range pkg.exports { 507 existing.exports[export] = true 508 } 509 } else { 510 p.knownPackages[imp.ImportPath] = pkg 511 } 512} 513 514// fixImports adds and removes imports from f so that all its references are 515// satisfied and there are no unused imports. 516// 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. 519var fixImports = fixImportsDefault 520 521func fixImportsDefault(fset *token.FileSet, f *ast.File, filename string, env *ProcessEnv) error { 522 fixes, err := getFixes(fset, f, filename, env) 523 if err != nil { 524 return err 525 } 526 apply(fset, f, fixes) 527 return err 528} 529 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. 532func getFixes(fset *token.FileSet, f *ast.File, filename string, env *ProcessEnv) ([]*ImportFix, error) { 533 abs, err := filepath.Abs(filename) 534 if err != nil { 535 return nil, err 536 } 537 srcDir := filepath.Dir(abs) 538 if env.Logf != nil { 539 env.Logf("fixImports(filename=%q), abs=%q, srcDir=%q ...", filename, abs, srcDir) 540 } 541 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 { 548 return fixes, nil 549 } 550 551 otherFiles := parseOtherFiles(fset, srcDir, filename) 552 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 { 557 return fixes, nil 558 } 559 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 { 564 return fixes, nil 565 } 566 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 { 573 return fixes, nil 574 } 575 576 addStdlibCandidates(p, p.missingRefs) 577 p.assumeSiblingImportsValid() 578 if fixes, done := p.fix(); done { 579 return fixes, nil 580 } 581 582 // Go look for candidates in $GOPATH, etc. We don't necessarily load 583 // the real exports of sibling imports, so keep assuming their contents. 584 if err := addExternalCandidates(p, p.missingRefs, filename); err != nil { 585 return nil, err 586 } 587 588 p.lastTry = true 589 fixes, _ := p.fix() 590 return fixes, nil 591} 592 593// Highest relevance, used for the standard library. Chosen arbitrarily to 594// match pre-existing gopls code. 595const MaxRelevance = 7 596 597// getCandidatePkgs works with the passed callback to find all acceptable packages. 598// It deduplicates by import path, and uses a cached stdlib rather than reading 599// from disk. 600func getCandidatePkgs(ctx context.Context, wrappedCallback *scanCallback, filename, filePkg string, env *ProcessEnv) error { 601 notSelf := func(p *pkg) bool { 602 return p.packageName != filePkg || p.dir != filepath.Dir(filename) 603 } 604 // Start off with the standard library. 605 for importPath, exports := range stdlib { 606 p := &pkg{ 607 dir: filepath.Join(env.goroot(), "src", importPath), 608 importPathShort: importPath, 609 packageName: path.Base(importPath), 610 relevance: MaxRelevance, 611 } 612 if notSelf(p) && wrappedCallback.packageNameLoaded(p) { 613 wrappedCallback.exportsLoaded(p, exports) 614 } 615 } 616 617 var mu sync.Mutex 618 dupCheck := map[string]struct{}{} 619 620 scanFilter := &scanCallback{ 621 rootFound: func(root gopathwalk.Root) bool { 622 // Exclude goroot results -- getting them is relatively expensive, not cached, 623 // and generally redundant with the in-memory version. 624 return root.Type != gopathwalk.RootGOROOT && wrappedCallback.rootFound(root) 625 }, 626 dirFound: wrappedCallback.dirFound, 627 packageNameLoaded: func(pkg *pkg) bool { 628 mu.Lock() 629 defer mu.Unlock() 630 if _, ok := dupCheck[pkg.importPathShort]; ok { 631 return false 632 } 633 dupCheck[pkg.importPathShort] = struct{}{} 634 return notSelf(pkg) && wrappedCallback.packageNameLoaded(pkg) 635 }, 636 exportsLoaded: func(pkg *pkg, exports []string) { 637 // If we're an x_test, load the package under test's test variant. 638 if strings.HasSuffix(filePkg, "_test") && pkg.dir == filepath.Dir(filename) { 639 var err error 640 _, exports, err = loadExportsFromFiles(ctx, env, pkg.dir, true) 641 if err != nil { 642 return 643 } 644 } 645 wrappedCallback.exportsLoaded(pkg, exports) 646 }, 647 } 648 resolver, err := env.GetResolver() 649 if err != nil { 650 return err 651 } 652 return resolver.scan(ctx, scanFilter) 653} 654 655func ScoreImportPaths(ctx context.Context, env *ProcessEnv, paths []string) (map[string]int, error) { 656 result := make(map[string]int) 657 resolver, err := env.GetResolver() 658 if err != nil { 659 return nil, err 660 } 661 for _, path := range paths { 662 result[path] = resolver.scoreImportPath(ctx, path) 663 } 664 return result, nil 665} 666 667func PrimeCache(ctx context.Context, env *ProcessEnv) error { 668 // Fully scan the disk for directories, but don't actually read any Go files. 669 callback := &scanCallback{ 670 rootFound: func(gopathwalk.Root) bool { 671 return true 672 }, 673 dirFound: func(pkg *pkg) bool { 674 return false 675 }, 676 packageNameLoaded: func(pkg *pkg) bool { 677 return false 678 }, 679 } 680 return getCandidatePkgs(ctx, callback, "", "", env) 681} 682 683func candidateImportName(pkg *pkg) string { 684 if ImportPathToAssumedName(pkg.importPathShort) != pkg.packageName { 685 return pkg.packageName 686 } 687 return "" 688} 689 690// GetAllCandidates gets all of the packages starting with prefix that can be 691// imported by filename, sorted by import path. 692func GetAllCandidates(ctx context.Context, wrapped func(ImportFix), searchPrefix, filename, filePkg string, env *ProcessEnv) error { 693 callback := &scanCallback{ 694 rootFound: func(gopathwalk.Root) bool { 695 return true 696 }, 697 dirFound: func(pkg *pkg) bool { 698 if !canUse(filename, pkg.dir) { 699 return false 700 } 701 // Try the assumed package name first, then a simpler path match 702 // in case of packages named vN, which are not uncommon. 703 return strings.HasPrefix(ImportPathToAssumedName(pkg.importPathShort), searchPrefix) || 704 strings.HasPrefix(path.Base(pkg.importPathShort), searchPrefix) 705 }, 706 packageNameLoaded: func(pkg *pkg) bool { 707 if !strings.HasPrefix(pkg.packageName, searchPrefix) { 708 return false 709 } 710 wrapped(ImportFix{ 711 StmtInfo: ImportInfo{ 712 ImportPath: pkg.importPathShort, 713 Name: candidateImportName(pkg), 714 }, 715 IdentName: pkg.packageName, 716 FixType: AddImport, 717 Relevance: pkg.relevance, 718 }) 719 return false 720 }, 721 } 722 return getCandidatePkgs(ctx, callback, filename, filePkg, env) 723} 724 725// A PackageExport is a package and its exports. 726type PackageExport struct { 727 Fix *ImportFix 728 Exports []string 729} 730 731// GetPackageExports returns all known packages with name pkg and their exports. 732func GetPackageExports(ctx context.Context, wrapped func(PackageExport), searchPkg, filename, filePkg string, env *ProcessEnv) error { 733 callback := &scanCallback{ 734 rootFound: func(gopathwalk.Root) bool { 735 return true 736 }, 737 dirFound: func(pkg *pkg) bool { 738 return pkgIsCandidate(filename, references{searchPkg: nil}, pkg) 739 }, 740 packageNameLoaded: func(pkg *pkg) bool { 741 return pkg.packageName == searchPkg 742 }, 743 exportsLoaded: func(pkg *pkg, exports []string) { 744 sort.Strings(exports) 745 wrapped(PackageExport{ 746 Fix: &ImportFix{ 747 StmtInfo: ImportInfo{ 748 ImportPath: pkg.importPathShort, 749 Name: candidateImportName(pkg), 750 }, 751 IdentName: pkg.packageName, 752 FixType: AddImport, 753 Relevance: pkg.relevance, 754 }, 755 Exports: exports, 756 }) 757 }, 758 } 759 return getCandidatePkgs(ctx, callback, filename, filePkg, env) 760} 761 762var RequiredGoEnvVars = []string{"GO111MODULE", "GOFLAGS", "GOINSECURE", "GOMOD", "GOMODCACHE", "GONOPROXY", "GONOSUMDB", "GOPATH", "GOPROXY", "GOROOT", "GOSUMDB"} 763 764// ProcessEnv contains environment variables and settings that affect the use of 765// the go command, the go/build package, etc. 766type ProcessEnv struct { 767 GocmdRunner *gocommand.Runner 768 769 BuildFlags []string 770 771 // Env overrides the OS environment, and can be used to specify 772 // GOPROXY, GO111MODULE, etc. PATH cannot be set here, because 773 // exec.Command will not honor it. 774 // Specifying all of RequiredGoEnvVars avoids a call to `go env`. 775 Env map[string]string 776 777 WorkingDir string 778 779 // If Logf is non-nil, debug logging is enabled through this function. 780 Logf func(format string, args ...interface{}) 781 782 resolver Resolver 783} 784 785func (e *ProcessEnv) goroot() string { 786 return e.mustGetEnv("GOROOT") 787} 788 789func (e *ProcessEnv) gopath() string { 790 return e.mustGetEnv("GOPATH") 791} 792 793func (e *ProcessEnv) mustGetEnv(k string) string { 794 v, ok := e.Env[k] 795 if !ok { 796 panic(fmt.Sprintf("%v not set in evaluated environment", k)) 797 } 798 return v 799} 800 801// CopyConfig copies the env's configuration into a new env. 802func (e *ProcessEnv) CopyConfig() *ProcessEnv { 803 copy := *e 804 copy.resolver = nil 805 return © 806} 807 808func (e *ProcessEnv) init() error { 809 foundAllRequired := true 810 for _, k := range RequiredGoEnvVars { 811 if _, ok := e.Env[k]; !ok { 812 foundAllRequired = false 813 break 814 } 815 } 816 if foundAllRequired { 817 return nil 818 } 819 820 if e.Env == nil { 821 e.Env = map[string]string{} 822 } 823 824 goEnv := map[string]string{} 825 stdout, err := e.invokeGo(context.TODO(), "env", append([]string{"-json"}, RequiredGoEnvVars...)...) 826 if err != nil { 827 return err 828 } 829 if err := json.Unmarshal(stdout.Bytes(), &goEnv); err != nil { 830 return err 831 } 832 for k, v := range goEnv { 833 e.Env[k] = v 834 } 835 return nil 836} 837 838func (e *ProcessEnv) env() []string { 839 var env []string // the gocommand package will prepend os.Environ. 840 for k, v := range e.Env { 841 env = append(env, k+"="+v) 842 } 843 return env 844} 845 846func (e *ProcessEnv) GetResolver() (Resolver, error) { 847 if e.resolver != nil { 848 return e.resolver, nil 849 } 850 if err := e.init(); err != nil { 851 return nil, err 852 } 853 if len(e.Env["GOMOD"]) == 0 { 854 e.resolver = newGopathResolver(e) 855 return e.resolver, nil 856 } 857 e.resolver = newModuleResolver(e) 858 return e.resolver, nil 859} 860 861func (e *ProcessEnv) buildContext() *build.Context { 862 ctx := build.Default 863 ctx.GOROOT = e.goroot() 864 ctx.GOPATH = e.gopath() 865 866 // As of Go 1.14, build.Context has a Dir field 867 // (see golang.org/issue/34860). 868 // Populate it only if present. 869 rc := reflect.ValueOf(&ctx).Elem() 870 dir := rc.FieldByName("Dir") 871 if !dir.IsValid() { 872 // Working drafts of Go 1.14 named the field "WorkingDir" instead. 873 // TODO(bcmills): Remove this case after the Go 1.14 beta has been released. 874 dir = rc.FieldByName("WorkingDir") 875 } 876 if dir.IsValid() && dir.Kind() == reflect.String { 877 dir.SetString(e.WorkingDir) 878 } 879 880 return &ctx 881} 882 883func (e *ProcessEnv) invokeGo(ctx context.Context, verb string, args ...string) (*bytes.Buffer, error) { 884 inv := gocommand.Invocation{ 885 Verb: verb, 886 Args: args, 887 BuildFlags: e.BuildFlags, 888 Env: e.env(), 889 Logf: e.Logf, 890 WorkingDir: e.WorkingDir, 891 } 892 return e.GocmdRunner.Run(ctx, inv) 893} 894 895func addStdlibCandidates(pass *pass, refs references) { 896 add := func(pkg string) { 897 // Prevent self-imports. 898 if path.Base(pkg) == pass.f.Name.Name && filepath.Join(pass.env.goroot(), "src", pkg) == pass.srcDir { 899 return 900 } 901 exports := copyExports(stdlib[pkg]) 902 pass.addCandidate( 903 &ImportInfo{ImportPath: pkg}, 904 &packageInfo{name: path.Base(pkg), exports: exports}) 905 } 906 for left := range refs { 907 if left == "rand" { 908 // Make sure we try crypto/rand before math/rand. 909 add("crypto/rand") 910 add("math/rand") 911 continue 912 } 913 for importPath := range stdlib { 914 if path.Base(importPath) == left { 915 add(importPath) 916 } 917 } 918 } 919} 920 921// A Resolver does the build-system-specific parts of goimports. 922type Resolver interface { 923 // loadPackageNames loads the package names in importPaths. 924 loadPackageNames(importPaths []string, srcDir string) (map[string]string, error) 925 // scan works with callback to search for packages. See scanCallback for details. 926 scan(ctx context.Context, callback *scanCallback) error 927 // loadExports returns the set of exported symbols in the package at dir. 928 // loadExports may be called concurrently. 929 loadExports(ctx context.Context, pkg *pkg, includeTest bool) (string, []string, error) 930 // scoreImportPath returns the relevance for an import path. 931 scoreImportPath(ctx context.Context, path string) int 932 933 ClearForNewScan() 934} 935 936// A scanCallback controls a call to scan and receives its results. 937// In general, minor errors will be silently discarded; a user should not 938// expect to receive a full series of calls for everything. 939type scanCallback struct { 940 // rootFound is called before scanning a new root dir. If it returns true, 941 // the root will be scanned. Returning false will not necessarily prevent 942 // directories from that root making it to dirFound. 943 rootFound func(gopathwalk.Root) bool 944 // dirFound is called when a directory is found that is possibly a Go package. 945 // pkg will be populated with everything except packageName. 946 // If it returns true, the package's name will be loaded. 947 dirFound func(pkg *pkg) bool 948 // packageNameLoaded is called when a package is found and its name is loaded. 949 // If it returns true, the package's exports will be loaded. 950 packageNameLoaded func(pkg *pkg) bool 951 // exportsLoaded is called when a package's exports have been loaded. 952 exportsLoaded func(pkg *pkg, exports []string) 953} 954 955func addExternalCandidates(pass *pass, refs references, filename string) error { 956 var mu sync.Mutex 957 found := make(map[string][]pkgDistance) 958 callback := &scanCallback{ 959 rootFound: func(gopathwalk.Root) bool { 960 return true // We want everything. 961 }, 962 dirFound: func(pkg *pkg) bool { 963 return pkgIsCandidate(filename, refs, pkg) 964 }, 965 packageNameLoaded: func(pkg *pkg) bool { 966 if _, want := refs[pkg.packageName]; !want { 967 return false 968 } 969 if pkg.dir == pass.srcDir && pass.f.Name.Name == pkg.packageName { 970 // The candidate is in the same directory and has the 971 // same package name. Don't try to import ourselves. 972 return false 973 } 974 if !canUse(filename, pkg.dir) { 975 return false 976 } 977 mu.Lock() 978 defer mu.Unlock() 979 found[pkg.packageName] = append(found[pkg.packageName], pkgDistance{pkg, distance(pass.srcDir, pkg.dir)}) 980 return false // We'll do our own loading after we sort. 981 }, 982 } 983 resolver, err := pass.env.GetResolver() 984 if err != nil { 985 return err 986 } 987 if err = resolver.scan(context.Background(), callback); err != nil { 988 return err 989 } 990 991 // Search for imports matching potential package references. 992 type result struct { 993 imp *ImportInfo 994 pkg *packageInfo 995 } 996 results := make(chan result, len(refs)) 997 998 ctx, cancel := context.WithCancel(context.TODO()) 999 var wg sync.WaitGroup 1000 defer func() { 1001 cancel() 1002 wg.Wait() 1003 }() 1004 var ( 1005 firstErr error 1006 firstErrOnce sync.Once 1007 ) 1008 for pkgName, symbols := range refs { 1009 wg.Add(1) 1010 go func(pkgName string, symbols map[string]bool) { 1011 defer wg.Done() 1012 1013 found, err := findImport(ctx, pass, found[pkgName], pkgName, symbols, filename) 1014 1015 if err != nil { 1016 firstErrOnce.Do(func() { 1017 firstErr = err 1018 cancel() 1019 }) 1020 return 1021 } 1022 1023 if found == nil { 1024 return // No matching package. 1025 } 1026 1027 imp := &ImportInfo{ 1028 ImportPath: found.importPathShort, 1029 } 1030 1031 pkg := &packageInfo{ 1032 name: pkgName, 1033 exports: symbols, 1034 } 1035 results <- result{imp, pkg} 1036 }(pkgName, symbols) 1037 } 1038 go func() { 1039 wg.Wait() 1040 close(results) 1041 }() 1042 1043 for result := range results { 1044 pass.addCandidate(result.imp, result.pkg) 1045 } 1046 return firstErr 1047} 1048 1049// notIdentifier reports whether ch is an invalid identifier character. 1050func notIdentifier(ch rune) bool { 1051 return !('a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || 1052 '0' <= ch && ch <= '9' || 1053 ch == '_' || 1054 ch >= utf8.RuneSelf && (unicode.IsLetter(ch) || unicode.IsDigit(ch))) 1055} 1056 1057// ImportPathToAssumedName returns the assumed package name of an import path. 1058// It does this using only string parsing of the import path. 1059// It picks the last element of the path that does not look like a major 1060// version, and then picks the valid identifier off the start of that element. 1061// It is used to determine if a local rename should be added to an import for 1062// clarity. 1063// This function could be moved to a standard package and exported if we want 1064// for use in other tools. 1065func ImportPathToAssumedName(importPath string) string { 1066 base := path.Base(importPath) 1067 if strings.HasPrefix(base, "v") { 1068 if _, err := strconv.Atoi(base[1:]); err == nil { 1069 dir := path.Dir(importPath) 1070 if dir != "." { 1071 base = path.Base(dir) 1072 } 1073 } 1074 } 1075 base = strings.TrimPrefix(base, "go-") 1076 if i := strings.IndexFunc(base, notIdentifier); i >= 0 { 1077 base = base[:i] 1078 } 1079 return base 1080} 1081 1082// gopathResolver implements resolver for GOPATH workspaces. 1083type gopathResolver struct { 1084 env *ProcessEnv 1085 walked bool 1086 cache *dirInfoCache 1087 scanSema chan struct{} // scanSema prevents concurrent scans. 1088} 1089 1090func newGopathResolver(env *ProcessEnv) *gopathResolver { 1091 r := &gopathResolver{ 1092 env: env, 1093 cache: &dirInfoCache{ 1094 dirs: map[string]*directoryPackageInfo{}, 1095 listeners: map[*int]cacheListener{}, 1096 }, 1097 scanSema: make(chan struct{}, 1), 1098 } 1099 r.scanSema <- struct{}{} 1100 return r 1101} 1102 1103func (r *gopathResolver) ClearForNewScan() { 1104 <-r.scanSema 1105 r.cache = &dirInfoCache{ 1106 dirs: map[string]*directoryPackageInfo{}, 1107 listeners: map[*int]cacheListener{}, 1108 } 1109 r.walked = false 1110 r.scanSema <- struct{}{} 1111} 1112 1113func (r *gopathResolver) loadPackageNames(importPaths []string, srcDir string) (map[string]string, error) { 1114 names := map[string]string{} 1115 for _, path := range importPaths { 1116 names[path] = importPathToName(r.env, path, srcDir) 1117 } 1118 return names, nil 1119} 1120 1121// importPathToName finds out the actual package name, as declared in its .go files. 1122// If there's a problem, it returns "". 1123func importPathToName(env *ProcessEnv, importPath, srcDir string) (packageName string) { 1124 // Fast path for standard library without going to disk. 1125 if _, ok := stdlib[importPath]; ok { 1126 return path.Base(importPath) // stdlib packages always match their paths. 1127 } 1128 1129 buildPkg, err := env.buildContext().Import(importPath, srcDir, build.FindOnly) 1130 if err != nil { 1131 return "" 1132 } 1133 pkgName, err := packageDirToName(buildPkg.Dir) 1134 if err != nil { 1135 return "" 1136 } 1137 return pkgName 1138} 1139 1140// packageDirToName is a faster version of build.Import if 1141// the only thing desired is the package name. Given a directory, 1142// packageDirToName then only parses one file in the package, 1143// trusting that the files in the directory are consistent. 1144func packageDirToName(dir string) (packageName string, err error) { 1145 d, err := os.Open(dir) 1146 if err != nil { 1147 return "", err 1148 } 1149 names, err := d.Readdirnames(-1) 1150 d.Close() 1151 if err != nil { 1152 return "", err 1153 } 1154 sort.Strings(names) // to have predictable behavior 1155 var lastErr error 1156 var nfile int 1157 for _, name := range names { 1158 if !strings.HasSuffix(name, ".go") { 1159 continue 1160 } 1161 if strings.HasSuffix(name, "_test.go") { 1162 continue 1163 } 1164 nfile++ 1165 fullFile := filepath.Join(dir, name) 1166 1167 fset := token.NewFileSet() 1168 f, err := parser.ParseFile(fset, fullFile, nil, parser.PackageClauseOnly) 1169 if err != nil { 1170 lastErr = err 1171 continue 1172 } 1173 pkgName := f.Name.Name 1174 if pkgName == "documentation" { 1175 // Special case from go/build.ImportDir, not 1176 // handled by ctx.MatchFile. 1177 continue 1178 } 1179 if pkgName == "main" { 1180 // Also skip package main, assuming it's a +build ignore generator or example. 1181 // Since you can't import a package main anyway, there's no harm here. 1182 continue 1183 } 1184 return pkgName, nil 1185 } 1186 if lastErr != nil { 1187 return "", lastErr 1188 } 1189 return "", fmt.Errorf("no importable package found in %d Go files", nfile) 1190} 1191 1192type pkg struct { 1193 dir string // absolute file path to pkg directory ("/usr/lib/go/src/net/http") 1194 importPathShort string // vendorless import path ("net/http", "a/b") 1195 packageName string // package name loaded from source if requested 1196 relevance int // a weakly-defined score of how relevant a package is. 0 is most relevant. 1197} 1198 1199type pkgDistance struct { 1200 pkg *pkg 1201 distance int // relative distance to target 1202} 1203 1204// byDistanceOrImportPathShortLength sorts by relative distance breaking ties 1205// on the short import path length and then the import string itself. 1206type byDistanceOrImportPathShortLength []pkgDistance 1207 1208func (s byDistanceOrImportPathShortLength) Len() int { return len(s) } 1209func (s byDistanceOrImportPathShortLength) Less(i, j int) bool { 1210 di, dj := s[i].distance, s[j].distance 1211 if di == -1 { 1212 return false 1213 } 1214 if dj == -1 { 1215 return true 1216 } 1217 if di != dj { 1218 return di < dj 1219 } 1220 1221 vi, vj := s[i].pkg.importPathShort, s[j].pkg.importPathShort 1222 if len(vi) != len(vj) { 1223 return len(vi) < len(vj) 1224 } 1225 return vi < vj 1226} 1227func (s byDistanceOrImportPathShortLength) Swap(i, j int) { s[i], s[j] = s[j], s[i] } 1228 1229func distance(basepath, targetpath string) int { 1230 p, err := filepath.Rel(basepath, targetpath) 1231 if err != nil { 1232 return -1 1233 } 1234 if p == "." { 1235 return 0 1236 } 1237 return strings.Count(p, string(filepath.Separator)) + 1 1238} 1239 1240func (r *gopathResolver) scan(ctx context.Context, callback *scanCallback) error { 1241 add := func(root gopathwalk.Root, dir string) { 1242 // We assume cached directories have not changed. We can skip them and their 1243 // children. 1244 if _, ok := r.cache.Load(dir); ok { 1245 return 1246 } 1247 1248 importpath := filepath.ToSlash(dir[len(root.Path)+len("/"):]) 1249 info := directoryPackageInfo{ 1250 status: directoryScanned, 1251 dir: dir, 1252 rootType: root.Type, 1253 nonCanonicalImportPath: VendorlessPath(importpath), 1254 } 1255 r.cache.Store(dir, info) 1256 } 1257 processDir := func(info directoryPackageInfo) { 1258 // Skip this directory if we were not able to get the package information successfully. 1259 if scanned, err := info.reachedStatus(directoryScanned); !scanned || err != nil { 1260 return 1261 } 1262 1263 p := &pkg{ 1264 importPathShort: info.nonCanonicalImportPath, 1265 dir: info.dir, 1266 relevance: MaxRelevance - 1, 1267 } 1268 if info.rootType == gopathwalk.RootGOROOT { 1269 p.relevance = MaxRelevance 1270 } 1271 1272 if !callback.dirFound(p) { 1273 return 1274 } 1275 var err error 1276 p.packageName, err = r.cache.CachePackageName(info) 1277 if err != nil { 1278 return 1279 } 1280 1281 if !callback.packageNameLoaded(p) { 1282 return 1283 } 1284 if _, exports, err := r.loadExports(ctx, p, false); err == nil { 1285 callback.exportsLoaded(p, exports) 1286 } 1287 } 1288 stop := r.cache.ScanAndListen(ctx, processDir) 1289 defer stop() 1290 // The callback is not necessarily safe to use in the goroutine below. Process roots eagerly. 1291 roots := filterRoots(gopathwalk.SrcDirsRoots(r.env.buildContext()), callback.rootFound) 1292 // We can't cancel walks, because we need them to finish to have a usable 1293 // cache. Instead, run them in a separate goroutine and detach. 1294 scanDone := make(chan struct{}) 1295 go func() { 1296 select { 1297 case <-ctx.Done(): 1298 return 1299 case <-r.scanSema: 1300 } 1301 defer func() { r.scanSema <- struct{}{} }() 1302 gopathwalk.Walk(roots, add, gopathwalk.Options{Logf: r.env.Logf, ModulesEnabled: false}) 1303 close(scanDone) 1304 }() 1305 select { 1306 case <-ctx.Done(): 1307 case <-scanDone: 1308 } 1309 return nil 1310} 1311 1312func (r *gopathResolver) scoreImportPath(ctx context.Context, path string) int { 1313 if _, ok := stdlib[path]; ok { 1314 return MaxRelevance 1315 } 1316 return MaxRelevance - 1 1317} 1318 1319func filterRoots(roots []gopathwalk.Root, include func(gopathwalk.Root) bool) []gopathwalk.Root { 1320 var result []gopathwalk.Root 1321 for _, root := range roots { 1322 if !include(root) { 1323 continue 1324 } 1325 result = append(result, root) 1326 } 1327 return result 1328} 1329 1330func (r *gopathResolver) loadExports(ctx context.Context, pkg *pkg, includeTest bool) (string, []string, error) { 1331 if info, ok := r.cache.Load(pkg.dir); ok && !includeTest { 1332 return r.cache.CacheExports(ctx, r.env, info) 1333 } 1334 return loadExportsFromFiles(ctx, r.env, pkg.dir, includeTest) 1335} 1336 1337// VendorlessPath returns the devendorized version of the import path ipath. 1338// For example, VendorlessPath("foo/bar/vendor/a/b") returns "a/b". 1339func VendorlessPath(ipath string) string { 1340 // Devendorize for use in import statement. 1341 if i := strings.LastIndex(ipath, "/vendor/"); i >= 0 { 1342 return ipath[i+len("/vendor/"):] 1343 } 1344 if strings.HasPrefix(ipath, "vendor/") { 1345 return ipath[len("vendor/"):] 1346 } 1347 return ipath 1348} 1349 1350func loadExportsFromFiles(ctx context.Context, env *ProcessEnv, dir string, includeTest bool) (string, []string, error) { 1351 var exports []string 1352 1353 // Look for non-test, buildable .go files which could provide exports. 1354 all, err := ioutil.ReadDir(dir) 1355 if err != nil { 1356 return "", nil, err 1357 } 1358 var files []os.FileInfo 1359 for _, fi := range all { 1360 name := fi.Name() 1361 if !strings.HasSuffix(name, ".go") || (!includeTest && strings.HasSuffix(name, "_test.go")) { 1362 continue 1363 } 1364 match, err := env.buildContext().MatchFile(dir, fi.Name()) 1365 if err != nil || !match { 1366 continue 1367 } 1368 files = append(files, fi) 1369 } 1370 1371 if len(files) == 0 { 1372 return "", nil, fmt.Errorf("dir %v contains no buildable, non-test .go files", dir) 1373 } 1374 1375 var pkgName string 1376 fset := token.NewFileSet() 1377 for _, fi := range files { 1378 select { 1379 case <-ctx.Done(): 1380 return "", nil, ctx.Err() 1381 default: 1382 } 1383 1384 fullFile := filepath.Join(dir, fi.Name()) 1385 f, err := parser.ParseFile(fset, fullFile, nil, 0) 1386 if err != nil { 1387 if env.Logf != nil { 1388 env.Logf("error parsing %v: %v", fullFile, err) 1389 } 1390 continue 1391 } 1392 if f.Name.Name == "documentation" { 1393 // Special case from go/build.ImportDir, not 1394 // handled by MatchFile above. 1395 continue 1396 } 1397 if includeTest && strings.HasSuffix(f.Name.Name, "_test") { 1398 // x_test package. We want internal test files only. 1399 continue 1400 } 1401 pkgName = f.Name.Name 1402 for name := range f.Scope.Objects { 1403 if ast.IsExported(name) { 1404 exports = append(exports, name) 1405 } 1406 } 1407 } 1408 1409 if env.Logf != nil { 1410 sortedExports := append([]string(nil), exports...) 1411 sort.Strings(sortedExports) 1412 env.Logf("loaded exports in dir %v (package %v): %v", dir, pkgName, strings.Join(sortedExports, ", ")) 1413 } 1414 return pkgName, exports, nil 1415} 1416 1417// findImport searches for a package with the given symbols. 1418// If no package is found, findImport returns ("", false, nil) 1419func findImport(ctx context.Context, pass *pass, candidates []pkgDistance, pkgName string, symbols map[string]bool, filename string) (*pkg, error) { 1420 // Sort the candidates by their import package length, 1421 // assuming that shorter package names are better than long 1422 // ones. Note that this sorts by the de-vendored name, so 1423 // there's no "penalty" for vendoring. 1424 sort.Sort(byDistanceOrImportPathShortLength(candidates)) 1425 if pass.env.Logf != nil { 1426 for i, c := range candidates { 1427 pass.env.Logf("%s candidate %d/%d: %v in %v", pkgName, i+1, len(candidates), c.pkg.importPathShort, c.pkg.dir) 1428 } 1429 } 1430 resolver, err := pass.env.GetResolver() 1431 if err != nil { 1432 return nil, err 1433 } 1434 1435 // Collect exports for packages with matching names. 1436 rescv := make([]chan *pkg, len(candidates)) 1437 for i := range candidates { 1438 rescv[i] = make(chan *pkg, 1) 1439 } 1440 const maxConcurrentPackageImport = 4 1441 loadExportsSem := make(chan struct{}, maxConcurrentPackageImport) 1442 1443 ctx, cancel := context.WithCancel(ctx) 1444 var wg sync.WaitGroup 1445 defer func() { 1446 cancel() 1447 wg.Wait() 1448 }() 1449 1450 wg.Add(1) 1451 go func() { 1452 defer wg.Done() 1453 for i, c := range candidates { 1454 select { 1455 case loadExportsSem <- struct{}{}: 1456 case <-ctx.Done(): 1457 return 1458 } 1459 1460 wg.Add(1) 1461 go func(c pkgDistance, resc chan<- *pkg) { 1462 defer func() { 1463 <-loadExportsSem 1464 wg.Done() 1465 }() 1466 1467 if pass.env.Logf != nil { 1468 pass.env.Logf("loading exports in dir %s (seeking package %s)", c.pkg.dir, pkgName) 1469 } 1470 // If we're an x_test, load the package under test's test variant. 1471 includeTest := strings.HasSuffix(pass.f.Name.Name, "_test") && c.pkg.dir == pass.srcDir 1472 _, exports, err := resolver.loadExports(ctx, c.pkg, includeTest) 1473 if err != nil { 1474 if pass.env.Logf != nil { 1475 pass.env.Logf("loading exports in dir %s (seeking package %s): %v", c.pkg.dir, pkgName, err) 1476 } 1477 resc <- nil 1478 return 1479 } 1480 1481 exportsMap := make(map[string]bool, len(exports)) 1482 for _, sym := range exports { 1483 exportsMap[sym] = true 1484 } 1485 1486 // If it doesn't have the right 1487 // symbols, send nil to mean no match. 1488 for symbol := range symbols { 1489 if !exportsMap[symbol] { 1490 resc <- nil 1491 return 1492 } 1493 } 1494 resc <- c.pkg 1495 }(c, rescv[i]) 1496 } 1497 }() 1498 1499 for _, resc := range rescv { 1500 pkg := <-resc 1501 if pkg == nil { 1502 continue 1503 } 1504 return pkg, nil 1505 } 1506 return nil, nil 1507} 1508 1509// pkgIsCandidate reports whether pkg is a candidate for satisfying the 1510// finding which package pkgIdent in the file named by filename is trying 1511// to refer to. 1512// 1513// This check is purely lexical and is meant to be as fast as possible 1514// because it's run over all $GOPATH directories to filter out poor 1515// candidates in order to limit the CPU and I/O later parsing the 1516// exports in candidate packages. 1517// 1518// filename is the file being formatted. 1519// pkgIdent is the package being searched for, like "client" (if 1520// searching for "client.New") 1521func pkgIsCandidate(filename string, refs references, pkg *pkg) bool { 1522 // Check "internal" and "vendor" visibility: 1523 if !canUse(filename, pkg.dir) { 1524 return false 1525 } 1526 1527 // Speed optimization to minimize disk I/O: 1528 // the last two components on disk must contain the 1529 // package name somewhere. 1530 // 1531 // This permits mismatch naming like directory 1532 // "go-foo" being package "foo", or "pkg.v3" being "pkg", 1533 // or directory "google.golang.org/api/cloudbilling/v1" 1534 // being package "cloudbilling", but doesn't 1535 // permit a directory "foo" to be package 1536 // "bar", which is strongly discouraged 1537 // anyway. There's no reason goimports needs 1538 // to be slow just to accommodate that. 1539 for pkgIdent := range refs { 1540 lastTwo := lastTwoComponents(pkg.importPathShort) 1541 if strings.Contains(lastTwo, pkgIdent) { 1542 return true 1543 } 1544 if hasHyphenOrUpperASCII(lastTwo) && !hasHyphenOrUpperASCII(pkgIdent) { 1545 lastTwo = lowerASCIIAndRemoveHyphen(lastTwo) 1546 if strings.Contains(lastTwo, pkgIdent) { 1547 return true 1548 } 1549 } 1550 } 1551 return false 1552} 1553 1554func hasHyphenOrUpperASCII(s string) bool { 1555 for i := 0; i < len(s); i++ { 1556 b := s[i] 1557 if b == '-' || ('A' <= b && b <= 'Z') { 1558 return true 1559 } 1560 } 1561 return false 1562} 1563 1564func lowerASCIIAndRemoveHyphen(s string) (ret string) { 1565 buf := make([]byte, 0, len(s)) 1566 for i := 0; i < len(s); i++ { 1567 b := s[i] 1568 switch { 1569 case b == '-': 1570 continue 1571 case 'A' <= b && b <= 'Z': 1572 buf = append(buf, b+('a'-'A')) 1573 default: 1574 buf = append(buf, b) 1575 } 1576 } 1577 return string(buf) 1578} 1579 1580// canUse reports whether the package in dir is usable from filename, 1581// respecting the Go "internal" and "vendor" visibility rules. 1582func canUse(filename, dir string) bool { 1583 // Fast path check, before any allocations. If it doesn't contain vendor 1584 // or internal, it's not tricky: 1585 // Note that this can false-negative on directories like "notinternal", 1586 // but we check it correctly below. This is just a fast path. 1587 if !strings.Contains(dir, "vendor") && !strings.Contains(dir, "internal") { 1588 return true 1589 } 1590 1591 dirSlash := filepath.ToSlash(dir) 1592 if !strings.Contains(dirSlash, "/vendor/") && !strings.Contains(dirSlash, "/internal/") && !strings.HasSuffix(dirSlash, "/internal") { 1593 return true 1594 } 1595 // Vendor or internal directory only visible from children of parent. 1596 // That means the path from the current directory to the target directory 1597 // can contain ../vendor or ../internal but not ../foo/vendor or ../foo/internal 1598 // or bar/vendor or bar/internal. 1599 // After stripping all the leading ../, the only okay place to see vendor or internal 1600 // is at the very beginning of the path. 1601 absfile, err := filepath.Abs(filename) 1602 if err != nil { 1603 return false 1604 } 1605 absdir, err := filepath.Abs(dir) 1606 if err != nil { 1607 return false 1608 } 1609 rel, err := filepath.Rel(absfile, absdir) 1610 if err != nil { 1611 return false 1612 } 1613 relSlash := filepath.ToSlash(rel) 1614 if i := strings.LastIndex(relSlash, "../"); i >= 0 { 1615 relSlash = relSlash[i+len("../"):] 1616 } 1617 return !strings.Contains(relSlash, "/vendor/") && !strings.Contains(relSlash, "/internal/") && !strings.HasSuffix(relSlash, "/internal") 1618} 1619 1620// lastTwoComponents returns at most the last two path components 1621// of v, using either / or \ as the path separator. 1622func lastTwoComponents(v string) string { 1623 nslash := 0 1624 for i := len(v) - 1; i >= 0; i-- { 1625 if v[i] == '/' || v[i] == '\\' { 1626 nslash++ 1627 if nslash == 2 { 1628 return v[i:] 1629 } 1630 } 1631 } 1632 return v 1633} 1634 1635type visitFn func(node ast.Node) ast.Visitor 1636 1637func (fn visitFn) Visit(node ast.Node) ast.Visitor { 1638 return fn(node) 1639} 1640 1641func copyExports(pkg []string) map[string]bool { 1642 m := make(map[string]bool, len(pkg)) 1643 for _, v := range pkg { 1644 m[v] = true 1645 } 1646 return m 1647} 1648