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