.config/coc/extensions/coc-go-data/tools/pkg/mod/mvdan.cc/gofumpt@v0.0.0-20200802201014-ab5a8192947d/gofumports/internal/imports/fix.go

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