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