1// Copyright 2013 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5package imports 6 7import ( 8 "bufio" 9 "bytes" 10 "fmt" 11 "go/ast" 12 "go/build" 13 "go/parser" 14 "go/token" 15 "io/ioutil" 16 "log" 17 "os" 18 "path" 19 "path/filepath" 20 "sort" 21 "strings" 22 "sync" 23 24 "golang.org/x/tools/go/ast/astutil" 25) 26 27// Debug controls verbose logging. 28var Debug = false 29 30var ( 31 inTests = false // set true by fix_test.go; if false, no need to use testMu 32 testMu sync.RWMutex // guards globals reset by tests; used only if inTests 33) 34 35// LocalPrefix, if set, instructs Process to sort import paths with the given 36// prefix into another group after 3rd-party packages. 37var LocalPrefix string 38 39// importToGroup is a list of functions which map from an import path to 40// a group number. 41var importToGroup = []func(importPath string) (num int, ok bool){ 42 func(importPath string) (num int, ok bool) { 43 if LocalPrefix != "" && strings.HasPrefix(importPath, LocalPrefix) { 44 return 3, true 45 } 46 return 47 }, 48 func(importPath string) (num int, ok bool) { 49 if strings.HasPrefix(importPath, "appengine") { 50 return 2, true 51 } 52 return 53 }, 54 func(importPath string) (num int, ok bool) { 55 if strings.Contains(importPath, ".") { 56 return 1, true 57 } 58 return 59 }, 60} 61 62func importGroup(importPath string) int { 63 for _, fn := range importToGroup { 64 if n, ok := fn(importPath); ok { 65 return n 66 } 67 } 68 return 0 69} 70 71// importInfo is a summary of information about one import. 72type importInfo struct { 73 Path string // full import path (e.g. "crypto/rand") 74 Alias string // import alias, if present (e.g. "crand") 75} 76 77// packageInfo is a summary of features found in a package. 78type packageInfo struct { 79 Globals map[string]bool // symbol => true 80 Imports map[string]importInfo // pkg base name or alias => info 81 // refs are a set of package references currently satisfied by imports. 82 // first key: either base package (e.g. "fmt") or renamed package 83 // second key: referenced package symbol (e.g. "Println") 84 Refs map[string]map[string]bool 85} 86 87// dirPackageInfo exposes the dirPackageInfoFile function so that it can be overridden. 88var dirPackageInfo = dirPackageInfoFile 89 90// dirPackageInfoFile gets information from other files in the package. 91func dirPackageInfoFile(pkgName, srcDir, filename string) (*packageInfo, error) { 92 considerTests := strings.HasSuffix(filename, "_test.go") 93 94 fileBase := filepath.Base(filename) 95 packageFileInfos, err := ioutil.ReadDir(srcDir) 96 if err != nil { 97 return nil, err 98 } 99 100 info := &packageInfo{ 101 Globals: make(map[string]bool), 102 Imports: make(map[string]importInfo), 103 Refs: make(map[string]map[string]bool), 104 } 105 106 visitor := collectReferences(info.Refs) 107 for _, fi := range packageFileInfos { 108 if fi.Name() == fileBase || !strings.HasSuffix(fi.Name(), ".go") { 109 continue 110 } 111 if !considerTests && strings.HasSuffix(fi.Name(), "_test.go") { 112 continue 113 } 114 115 fileSet := token.NewFileSet() 116 root, err := parser.ParseFile(fileSet, filepath.Join(srcDir, fi.Name()), nil, 0) 117 if err != nil { 118 continue 119 } 120 121 for _, decl := range root.Decls { 122 genDecl, ok := decl.(*ast.GenDecl) 123 if !ok { 124 continue 125 } 126 127 for _, spec := range genDecl.Specs { 128 valueSpec, ok := spec.(*ast.ValueSpec) 129 if !ok { 130 continue 131 } 132 info.Globals[valueSpec.Names[0].Name] = true 133 } 134 } 135 136 for _, imp := range root.Imports { 137 impInfo := importInfo{Path: strings.Trim(imp.Path.Value, `"`)} 138 name := path.Base(impInfo.Path) 139 if imp.Name != nil { 140 name = strings.Trim(imp.Name.Name, `"`) 141 impInfo.Alias = name 142 } 143 info.Imports[name] = impInfo 144 } 145 146 ast.Walk(visitor, root) 147 } 148 return info, nil 149} 150 151// collectReferences returns a visitor that collects all exported package 152// references 153func collectReferences(refs map[string]map[string]bool) visitFn { 154 var visitor visitFn 155 visitor = func(node ast.Node) ast.Visitor { 156 if node == nil { 157 return visitor 158 } 159 switch v := node.(type) { 160 case *ast.SelectorExpr: 161 xident, ok := v.X.(*ast.Ident) 162 if !ok { 163 break 164 } 165 if xident.Obj != nil { 166 // if the parser can resolve it, it's not a package ref 167 break 168 } 169 pkgName := xident.Name 170 r := refs[pkgName] 171 if r == nil { 172 r = make(map[string]bool) 173 refs[pkgName] = r 174 } 175 if ast.IsExported(v.Sel.Name) { 176 r[v.Sel.Name] = true 177 } 178 } 179 return visitor 180 } 181 return visitor 182} 183 184func fixImports(fset *token.FileSet, f *ast.File, filename string) (added []string, err error) { 185 // refs are a set of possible package references currently unsatisfied by imports. 186 // first key: either base package (e.g. "fmt") or renamed package 187 // second key: referenced package symbol (e.g. "Println") 188 refs := make(map[string]map[string]bool) 189 190 // decls are the current package imports. key is base package or renamed package. 191 decls := make(map[string]*ast.ImportSpec) 192 193 abs, err := filepath.Abs(filename) 194 if err != nil { 195 return nil, err 196 } 197 srcDir := filepath.Dir(abs) 198 if Debug { 199 log.Printf("fixImports(filename=%q), abs=%q, srcDir=%q ...", filename, abs, srcDir) 200 } 201 202 var packageInfo *packageInfo 203 var loadedPackageInfo bool 204 205 // collect potential uses of packages. 206 var visitor visitFn 207 visitor = visitFn(func(node ast.Node) ast.Visitor { 208 if node == nil { 209 return visitor 210 } 211 switch v := node.(type) { 212 case *ast.ImportSpec: 213 if v.Name != nil { 214 decls[v.Name.Name] = v 215 break 216 } 217 ipath := strings.Trim(v.Path.Value, `"`) 218 if ipath == "C" { 219 break 220 } 221 local := importPathToName(ipath, srcDir) 222 decls[local] = v 223 case *ast.SelectorExpr: 224 xident, ok := v.X.(*ast.Ident) 225 if !ok { 226 break 227 } 228 if xident.Obj != nil { 229 // if the parser can resolve it, it's not a package ref 230 break 231 } 232 pkgName := xident.Name 233 if refs[pkgName] == nil { 234 refs[pkgName] = make(map[string]bool) 235 } 236 if !loadedPackageInfo { 237 loadedPackageInfo = true 238 packageInfo, _ = dirPackageInfo(f.Name.Name, srcDir, filename) 239 } 240 if decls[pkgName] == nil && (packageInfo == nil || !packageInfo.Globals[pkgName]) { 241 refs[pkgName][v.Sel.Name] = true 242 } 243 } 244 return visitor 245 }) 246 ast.Walk(visitor, f) 247 248 // Nil out any unused ImportSpecs, to be removed in following passes 249 unusedImport := map[string]string{} 250 for pkg, is := range decls { 251 if refs[pkg] == nil && pkg != "_" && pkg != "." { 252 name := "" 253 if is.Name != nil { 254 name = is.Name.Name 255 } 256 unusedImport[strings.Trim(is.Path.Value, `"`)] = name 257 } 258 } 259 for ipath, name := range unusedImport { 260 if ipath == "C" { 261 // Don't remove cgo stuff. 262 continue 263 } 264 astutil.DeleteNamedImport(fset, f, name, ipath) 265 } 266 267 for pkgName, symbols := range refs { 268 if len(symbols) == 0 { 269 // skip over packages already imported 270 delete(refs, pkgName) 271 } 272 } 273 274 // Fast path, all references already imported. 275 if len(refs) == 0 { 276 return nil, nil 277 } 278 279 // Can assume this will be necessary in all cases now. 280 if !loadedPackageInfo { 281 packageInfo, _ = dirPackageInfo(f.Name.Name, srcDir, filename) 282 } 283 284 // Search for imports matching potential package references. 285 searches := 0 286 type result struct { 287 ipath string // import path (if err == nil) 288 name string // optional name to rename import as 289 err error 290 } 291 results := make(chan result) 292 for pkgName, symbols := range refs { 293 go func(pkgName string, symbols map[string]bool) { 294 if packageInfo != nil { 295 sibling := packageInfo.Imports[pkgName] 296 if sibling.Path != "" { 297 refs := packageInfo.Refs[pkgName] 298 for symbol := range symbols { 299 if refs[symbol] { 300 results <- result{ipath: sibling.Path, name: sibling.Alias} 301 return 302 } 303 } 304 } 305 } 306 ipath, rename, err := findImport(pkgName, symbols, filename) 307 r := result{ipath: ipath, err: err} 308 if rename { 309 r.name = pkgName 310 } 311 results <- r 312 }(pkgName, symbols) 313 searches++ 314 } 315 for i := 0; i < searches; i++ { 316 result := <-results 317 if result.err != nil { 318 return nil, result.err 319 } 320 if result.ipath != "" { 321 if result.name != "" { 322 astutil.AddNamedImport(fset, f, result.name, result.ipath) 323 } else { 324 astutil.AddImport(fset, f, result.ipath) 325 } 326 added = append(added, result.ipath) 327 } 328 } 329 330 return added, nil 331} 332 333// importPathToName returns the package name for the given import path. 334var importPathToName func(importPath, srcDir string) (packageName string) = importPathToNameGoPath 335 336// importPathToNameBasic assumes the package name is the base of import path. 337func importPathToNameBasic(importPath, srcDir string) (packageName string) { 338 return path.Base(importPath) 339} 340 341// importPathToNameGoPath finds out the actual package name, as declared in its .go files. 342// If there's a problem, it falls back to using importPathToNameBasic. 343func importPathToNameGoPath(importPath, srcDir string) (packageName string) { 344 // Fast path for standard library without going to disk. 345 if pkg, ok := stdImportPackage[importPath]; ok { 346 return pkg 347 } 348 349 pkgName, err := importPathToNameGoPathParse(importPath, srcDir) 350 if Debug { 351 log.Printf("importPathToNameGoPathParse(%q, srcDir=%q) = %q, %v", importPath, srcDir, pkgName, err) 352 } 353 if err == nil { 354 return pkgName 355 } 356 return importPathToNameBasic(importPath, srcDir) 357} 358 359// importPathToNameGoPathParse is a faster version of build.Import if 360// the only thing desired is the package name. It uses build.FindOnly 361// to find the directory and then only parses one file in the package, 362// trusting that the files in the directory are consistent. 363func importPathToNameGoPathParse(importPath, srcDir string) (packageName string, err error) { 364 buildPkg, err := build.Import(importPath, srcDir, build.FindOnly) 365 if err != nil { 366 return "", err 367 } 368 d, err := os.Open(buildPkg.Dir) 369 if err != nil { 370 return "", err 371 } 372 names, err := d.Readdirnames(-1) 373 d.Close() 374 if err != nil { 375 return "", err 376 } 377 sort.Strings(names) // to have predictable behavior 378 var lastErr error 379 var nfile int 380 for _, name := range names { 381 if !strings.HasSuffix(name, ".go") { 382 continue 383 } 384 if strings.HasSuffix(name, "_test.go") { 385 continue 386 } 387 nfile++ 388 fullFile := filepath.Join(buildPkg.Dir, name) 389 390 fset := token.NewFileSet() 391 f, err := parser.ParseFile(fset, fullFile, nil, parser.PackageClauseOnly) 392 if err != nil { 393 lastErr = err 394 continue 395 } 396 pkgName := f.Name.Name 397 if pkgName == "documentation" { 398 // Special case from go/build.ImportDir, not 399 // handled by ctx.MatchFile. 400 continue 401 } 402 if pkgName == "main" { 403 // Also skip package main, assuming it's a +build ignore generator or example. 404 // Since you can't import a package main anyway, there's no harm here. 405 continue 406 } 407 return pkgName, nil 408 } 409 if lastErr != nil { 410 return "", lastErr 411 } 412 return "", fmt.Errorf("no importable package found in %d Go files", nfile) 413} 414 415var stdImportPackage = map[string]string{} // "net/http" => "http" 416 417func init() { 418 // Nothing in the standard library has a package name not 419 // matching its import base name. 420 for _, pkg := range stdlib { 421 if _, ok := stdImportPackage[pkg]; !ok { 422 stdImportPackage[pkg] = path.Base(pkg) 423 } 424 } 425} 426 427// Directory-scanning state. 428var ( 429 // scanGoRootOnce guards calling scanGoRoot (for $GOROOT) 430 scanGoRootOnce sync.Once 431 // scanGoPathOnce guards calling scanGoPath (for $GOPATH) 432 scanGoPathOnce sync.Once 433 434 // populateIgnoreOnce guards calling populateIgnore 435 populateIgnoreOnce sync.Once 436 ignoredDirs []os.FileInfo 437 438 dirScanMu sync.RWMutex 439 dirScan map[string]*pkg // abs dir path => *pkg 440) 441 442type pkg struct { 443 dir string // absolute file path to pkg directory ("/usr/lib/go/src/net/http") 444 importPath string // full pkg import path ("net/http", "foo/bar/vendor/a/b") 445 importPathShort string // vendorless import path ("net/http", "a/b") 446 distance int // relative distance to target 447} 448 449// byDistanceOrImportPathShortLength sorts by relative distance breaking ties 450// on the short import path length and then the import string itself. 451type byDistanceOrImportPathShortLength []*pkg 452 453func (s byDistanceOrImportPathShortLength) Len() int { return len(s) } 454func (s byDistanceOrImportPathShortLength) Less(i, j int) bool { 455 di, dj := s[i].distance, s[j].distance 456 if di == -1 { 457 return false 458 } 459 if dj == -1 { 460 return true 461 } 462 if di != dj { 463 return di < dj 464 } 465 466 vi, vj := s[i].importPathShort, s[j].importPathShort 467 if len(vi) != len(vj) { 468 return len(vi) < len(vj) 469 } 470 return vi < vj 471} 472func (s byDistanceOrImportPathShortLength) Swap(i, j int) { s[i], s[j] = s[j], s[i] } 473 474func distance(basepath, targetpath string) int { 475 p, err := filepath.Rel(basepath, targetpath) 476 if err != nil { 477 return -1 478 } 479 if p == "." { 480 return 0 481 } 482 return strings.Count(p, string(filepath.Separator)) + 1 483} 484 485// guarded by populateIgnoreOnce; populates ignoredDirs. 486func populateIgnore() { 487 for _, srcDir := range build.Default.SrcDirs() { 488 if srcDir == filepath.Join(build.Default.GOROOT, "src") { 489 continue 490 } 491 populateIgnoredDirs(srcDir) 492 } 493} 494 495// populateIgnoredDirs reads an optional config file at <path>/.goimportsignore 496// of relative directories to ignore when scanning for go files. 497// The provided path is one of the $GOPATH entries with "src" appended. 498func populateIgnoredDirs(path string) { 499 file := filepath.Join(path, ".goimportsignore") 500 slurp, err := ioutil.ReadFile(file) 501 if Debug { 502 if err != nil { 503 log.Print(err) 504 } else { 505 log.Printf("Read %s", file) 506 } 507 } 508 if err != nil { 509 return 510 } 511 bs := bufio.NewScanner(bytes.NewReader(slurp)) 512 for bs.Scan() { 513 line := strings.TrimSpace(bs.Text()) 514 if line == "" || strings.HasPrefix(line, "#") { 515 continue 516 } 517 full := filepath.Join(path, line) 518 if fi, err := os.Stat(full); err == nil { 519 ignoredDirs = append(ignoredDirs, fi) 520 if Debug { 521 log.Printf("Directory added to ignore list: %s", full) 522 } 523 } else if Debug { 524 log.Printf("Error statting entry in .goimportsignore: %v", err) 525 } 526 } 527} 528 529func skipDir(fi os.FileInfo) bool { 530 for _, ignoredDir := range ignoredDirs { 531 if os.SameFile(fi, ignoredDir) { 532 return true 533 } 534 } 535 return false 536} 537 538// shouldTraverse reports whether the symlink fi should, found in dir, 539// should be followed. It makes sure symlinks were never visited 540// before to avoid symlink loops. 541func shouldTraverse(dir string, fi os.FileInfo) bool { 542 path := filepath.Join(dir, fi.Name()) 543 target, err := filepath.EvalSymlinks(path) 544 if err != nil { 545 if !os.IsNotExist(err) { 546 fmt.Fprintln(os.Stderr, err) 547 } 548 return false 549 } 550 ts, err := os.Stat(target) 551 if err != nil { 552 fmt.Fprintln(os.Stderr, err) 553 return false 554 } 555 if !ts.IsDir() { 556 return false 557 } 558 if skipDir(ts) { 559 return false 560 } 561 // Check for symlink loops by statting each directory component 562 // and seeing if any are the same file as ts. 563 for { 564 parent := filepath.Dir(path) 565 if parent == path { 566 // Made it to the root without seeing a cycle. 567 // Use this symlink. 568 return true 569 } 570 parentInfo, err := os.Stat(parent) 571 if err != nil { 572 return false 573 } 574 if os.SameFile(ts, parentInfo) { 575 // Cycle. Don't traverse. 576 return false 577 } 578 path = parent 579 } 580 581} 582 583var testHookScanDir = func(dir string) {} 584 585var scanGoRootDone = make(chan struct{}) // closed when scanGoRoot is done 586 587func scanGoRoot() { 588 go func() { 589 scanGoDirs(true) 590 close(scanGoRootDone) 591 }() 592} 593 594func scanGoPath() { scanGoDirs(false) } 595 596func scanGoDirs(goRoot bool) { 597 if Debug { 598 which := "$GOROOT" 599 if !goRoot { 600 which = "$GOPATH" 601 } 602 log.Printf("scanning " + which) 603 defer log.Printf("scanned " + which) 604 } 605 dirScanMu.Lock() 606 if dirScan == nil { 607 dirScan = make(map[string]*pkg) 608 } 609 dirScanMu.Unlock() 610 611 for _, srcDir := range build.Default.SrcDirs() { 612 isGoroot := srcDir == filepath.Join(build.Default.GOROOT, "src") 613 if isGoroot != goRoot { 614 continue 615 } 616 testHookScanDir(srcDir) 617 walkFn := func(path string, typ os.FileMode) error { 618 dir := filepath.Dir(path) 619 if typ.IsRegular() { 620 if dir == srcDir { 621 // Doesn't make sense to have regular files 622 // directly in your $GOPATH/src or $GOROOT/src. 623 return nil 624 } 625 if !strings.HasSuffix(path, ".go") { 626 return nil 627 } 628 dirScanMu.Lock() 629 if _, dup := dirScan[dir]; !dup { 630 importpath := filepath.ToSlash(dir[len(srcDir)+len("/"):]) 631 dirScan[dir] = &pkg{ 632 importPath: importpath, 633 importPathShort: vendorlessImportPath(importpath), 634 dir: dir, 635 } 636 } 637 dirScanMu.Unlock() 638 return nil 639 } 640 if typ == os.ModeDir { 641 base := filepath.Base(path) 642 if base == "" || base[0] == '.' || base[0] == '_' || 643 base == "testdata" || base == "node_modules" { 644 return filepath.SkipDir 645 } 646 fi, err := os.Lstat(path) 647 if err == nil && skipDir(fi) { 648 if Debug { 649 log.Printf("skipping directory %q under %s", fi.Name(), dir) 650 } 651 return filepath.SkipDir 652 } 653 return nil 654 } 655 if typ == os.ModeSymlink { 656 base := filepath.Base(path) 657 if strings.HasPrefix(base, ".#") { 658 // Emacs noise. 659 return nil 660 } 661 fi, err := os.Lstat(path) 662 if err != nil { 663 // Just ignore it. 664 return nil 665 } 666 if shouldTraverse(dir, fi) { 667 return traverseLink 668 } 669 } 670 return nil 671 } 672 if err := fastWalk(srcDir, walkFn); err != nil { 673 log.Printf("goimports: scanning directory %v: %v", srcDir, err) 674 } 675 } 676} 677 678// vendorlessImportPath returns the devendorized version of the provided import path. 679// e.g. "foo/bar/vendor/a/b" => "a/b" 680func vendorlessImportPath(ipath string) string { 681 // Devendorize for use in import statement. 682 if i := strings.LastIndex(ipath, "/vendor/"); i >= 0 { 683 return ipath[i+len("/vendor/"):] 684 } 685 if strings.HasPrefix(ipath, "vendor/") { 686 return ipath[len("vendor/"):] 687 } 688 return ipath 689} 690 691// loadExports returns the set of exported symbols in the package at dir. 692// It returns nil on error or if the package name in dir does not match expectPackage. 693var loadExports func(expectPackage, dir string) map[string]bool = loadExportsGoPath 694 695func loadExportsGoPath(expectPackage, dir string) map[string]bool { 696 if Debug { 697 log.Printf("loading exports in dir %s (seeking package %s)", dir, expectPackage) 698 } 699 exports := make(map[string]bool) 700 701 ctx := build.Default 702 703 // ReadDir is like ioutil.ReadDir, but only returns *.go files 704 // and filters out _test.go files since they're not relevant 705 // and only slow things down. 706 ctx.ReadDir = func(dir string) (notTests []os.FileInfo, err error) { 707 all, err := ioutil.ReadDir(dir) 708 if err != nil { 709 return nil, err 710 } 711 notTests = all[:0] 712 for _, fi := range all { 713 name := fi.Name() 714 if strings.HasSuffix(name, ".go") && !strings.HasSuffix(name, "_test.go") { 715 notTests = append(notTests, fi) 716 } 717 } 718 return notTests, nil 719 } 720 721 files, err := ctx.ReadDir(dir) 722 if err != nil { 723 log.Print(err) 724 return nil 725 } 726 727 fset := token.NewFileSet() 728 729 for _, fi := range files { 730 match, err := ctx.MatchFile(dir, fi.Name()) 731 if err != nil || !match { 732 continue 733 } 734 fullFile := filepath.Join(dir, fi.Name()) 735 f, err := parser.ParseFile(fset, fullFile, nil, 0) 736 if err != nil { 737 if Debug { 738 log.Printf("Parsing %s: %v", fullFile, err) 739 } 740 return nil 741 } 742 pkgName := f.Name.Name 743 if pkgName == "documentation" { 744 // Special case from go/build.ImportDir, not 745 // handled by ctx.MatchFile. 746 continue 747 } 748 if pkgName != expectPackage { 749 if Debug { 750 log.Printf("scan of dir %v is not expected package %v (actually %v)", dir, expectPackage, pkgName) 751 } 752 return nil 753 } 754 for name := range f.Scope.Objects { 755 if ast.IsExported(name) { 756 exports[name] = true 757 } 758 } 759 } 760 761 if Debug { 762 exportList := make([]string, 0, len(exports)) 763 for k := range exports { 764 exportList = append(exportList, k) 765 } 766 sort.Strings(exportList) 767 log.Printf("loaded exports in dir %v (package %v): %v", dir, expectPackage, strings.Join(exportList, ", ")) 768 } 769 return exports 770} 771 772// findImport searches for a package with the given symbols. 773// If no package is found, findImport returns ("", false, nil) 774// 775// This is declared as a variable rather than a function so goimports 776// can be easily extended by adding a file with an init function. 777// 778// The rename value tells goimports whether to use the package name as 779// a local qualifier in an import. For example, if findImports("pkg", 780// "X") returns ("foo/bar", rename=true), then goimports adds the 781// import line: 782// import pkg "foo/bar" 783// to satisfy uses of pkg.X in the file. 784var findImport func(pkgName string, symbols map[string]bool, filename string) (foundPkg string, rename bool, err error) = findImportGoPath 785 786// findImportGoPath is the normal implementation of findImport. 787// (Some companies have their own internally.) 788func findImportGoPath(pkgName string, symbols map[string]bool, filename string) (foundPkg string, rename bool, err error) { 789 if inTests { 790 testMu.RLock() 791 defer testMu.RUnlock() 792 } 793 794 pkgDir, err := filepath.Abs(filename) 795 if err != nil { 796 return "", false, err 797 } 798 pkgDir = filepath.Dir(pkgDir) 799 800 // Fast path for the standard library. 801 // In the common case we hopefully never have to scan the GOPATH, which can 802 // be slow with moving disks. 803 if pkg, rename, ok := findImportStdlib(pkgName, symbols); ok { 804 return pkg, rename, nil 805 } 806 if pkgName == "rand" && symbols["Read"] { 807 // Special-case rand.Read. 808 // 809 // If findImportStdlib didn't find it above, don't go 810 // searching for it, lest it find and pick math/rand 811 // in GOROOT (new as of Go 1.6) 812 // 813 // crypto/rand is the safer choice. 814 return "", false, nil 815 } 816 817 // TODO(sameer): look at the import lines for other Go files in the 818 // local directory, since the user is likely to import the same packages 819 // in the current Go file. Return rename=true when the other Go files 820 // use a renamed package that's also used in the current file. 821 822 // Read all the $GOPATH/src/.goimportsignore files before scanning directories. 823 populateIgnoreOnce.Do(populateIgnore) 824 825 // Start scanning the $GOROOT asynchronously, then run the 826 // GOPATH scan synchronously if needed, and then wait for the 827 // $GOROOT to finish. 828 // 829 // TODO(bradfitz): run each $GOPATH entry async. But nobody 830 // really has more than one anyway, so low priority. 831 scanGoRootOnce.Do(scanGoRoot) // async 832 if !fileInDir(filename, build.Default.GOROOT) { 833 scanGoPathOnce.Do(scanGoPath) // blocking 834 } 835 <-scanGoRootDone 836 837 // Find candidate packages, looking only at their directory names first. 838 var candidates []*pkg 839 for _, pkg := range dirScan { 840 if pkgIsCandidate(filename, pkgName, pkg) { 841 pkg.distance = distance(pkgDir, pkg.dir) 842 candidates = append(candidates, pkg) 843 } 844 } 845 846 // Sort the candidates by their import package length, 847 // assuming that shorter package names are better than long 848 // ones. Note that this sorts by the de-vendored name, so 849 // there's no "penalty" for vendoring. 850 sort.Sort(byDistanceOrImportPathShortLength(candidates)) 851 if Debug { 852 for i, pkg := range candidates { 853 log.Printf("%s candidate %d/%d: %v in %v", pkgName, i+1, len(candidates), pkg.importPathShort, pkg.dir) 854 } 855 } 856 857 // Collect exports for packages with matching names. 858 859 done := make(chan struct{}) // closed when we find the answer 860 defer close(done) 861 862 rescv := make([]chan *pkg, len(candidates)) 863 for i := range candidates { 864 rescv[i] = make(chan *pkg) 865 } 866 const maxConcurrentPackageImport = 4 867 loadExportsSem := make(chan struct{}, maxConcurrentPackageImport) 868 869 go func() { 870 for i, pkg := range candidates { 871 select { 872 case loadExportsSem <- struct{}{}: 873 select { 874 case <-done: 875 return 876 default: 877 } 878 case <-done: 879 return 880 } 881 pkg := pkg 882 resc := rescv[i] 883 go func() { 884 if inTests { 885 testMu.RLock() 886 defer testMu.RUnlock() 887 } 888 defer func() { <-loadExportsSem }() 889 exports := loadExports(pkgName, pkg.dir) 890 891 // If it doesn't have the right 892 // symbols, send nil to mean no match. 893 for symbol := range symbols { 894 if !exports[symbol] { 895 pkg = nil 896 break 897 } 898 } 899 select { 900 case resc <- pkg: 901 case <-done: 902 } 903 }() 904 } 905 }() 906 for _, resc := range rescv { 907 pkg := <-resc 908 if pkg == nil { 909 continue 910 } 911 // If the package name in the source doesn't match the import path's base, 912 // return true so the rewriter adds a name (import foo "github.com/bar/go-foo") 913 needsRename := path.Base(pkg.importPath) != pkgName 914 return pkg.importPathShort, needsRename, nil 915 } 916 return "", false, nil 917} 918 919// pkgIsCandidate reports whether pkg is a candidate for satisfying the 920// finding which package pkgIdent in the file named by filename is trying 921// to refer to. 922// 923// This check is purely lexical and is meant to be as fast as possible 924// because it's run over all $GOPATH directories to filter out poor 925// candidates in order to limit the CPU and I/O later parsing the 926// exports in candidate packages. 927// 928// filename is the file being formatted. 929// pkgIdent is the package being searched for, like "client" (if 930// searching for "client.New") 931func pkgIsCandidate(filename, pkgIdent string, pkg *pkg) bool { 932 // Check "internal" and "vendor" visibility: 933 if !canUse(filename, pkg.dir) { 934 return false 935 } 936 937 // Speed optimization to minimize disk I/O: 938 // the last two components on disk must contain the 939 // package name somewhere. 940 // 941 // This permits mismatch naming like directory 942 // "go-foo" being package "foo", or "pkg.v3" being "pkg", 943 // or directory "google.golang.org/api/cloudbilling/v1" 944 // being package "cloudbilling", but doesn't 945 // permit a directory "foo" to be package 946 // "bar", which is strongly discouraged 947 // anyway. There's no reason goimports needs 948 // to be slow just to accomodate that. 949 lastTwo := lastTwoComponents(pkg.importPathShort) 950 if strings.Contains(lastTwo, pkgIdent) { 951 return true 952 } 953 if hasHyphenOrUpperASCII(lastTwo) && !hasHyphenOrUpperASCII(pkgIdent) { 954 lastTwo = lowerASCIIAndRemoveHyphen(lastTwo) 955 if strings.Contains(lastTwo, pkgIdent) { 956 return true 957 } 958 } 959 960 return false 961} 962 963func hasHyphenOrUpperASCII(s string) bool { 964 for i := 0; i < len(s); i++ { 965 b := s[i] 966 if b == '-' || ('A' <= b && b <= 'Z') { 967 return true 968 } 969 } 970 return false 971} 972 973func lowerASCIIAndRemoveHyphen(s string) (ret string) { 974 buf := make([]byte, 0, len(s)) 975 for i := 0; i < len(s); i++ { 976 b := s[i] 977 switch { 978 case b == '-': 979 continue 980 case 'A' <= b && b <= 'Z': 981 buf = append(buf, b+('a'-'A')) 982 default: 983 buf = append(buf, b) 984 } 985 } 986 return string(buf) 987} 988 989// canUse reports whether the package in dir is usable from filename, 990// respecting the Go "internal" and "vendor" visibility rules. 991func canUse(filename, dir string) bool { 992 // Fast path check, before any allocations. If it doesn't contain vendor 993 // or internal, it's not tricky: 994 // Note that this can false-negative on directories like "notinternal", 995 // but we check it correctly below. This is just a fast path. 996 if !strings.Contains(dir, "vendor") && !strings.Contains(dir, "internal") { 997 return true 998 } 999 1000 dirSlash := filepath.ToSlash(dir) 1001 if !strings.Contains(dirSlash, "/vendor/") && !strings.Contains(dirSlash, "/internal/") && !strings.HasSuffix(dirSlash, "/internal") { 1002 return true 1003 } 1004 // Vendor or internal directory only visible from children of parent. 1005 // That means the path from the current directory to the target directory 1006 // can contain ../vendor or ../internal but not ../foo/vendor or ../foo/internal 1007 // or bar/vendor or bar/internal. 1008 // After stripping all the leading ../, the only okay place to see vendor or internal 1009 // is at the very beginning of the path. 1010 absfile, err := filepath.Abs(filename) 1011 if err != nil { 1012 return false 1013 } 1014 absdir, err := filepath.Abs(dir) 1015 if err != nil { 1016 return false 1017 } 1018 rel, err := filepath.Rel(absfile, absdir) 1019 if err != nil { 1020 return false 1021 } 1022 relSlash := filepath.ToSlash(rel) 1023 if i := strings.LastIndex(relSlash, "../"); i >= 0 { 1024 relSlash = relSlash[i+len("../"):] 1025 } 1026 return !strings.Contains(relSlash, "/vendor/") && !strings.Contains(relSlash, "/internal/") && !strings.HasSuffix(relSlash, "/internal") 1027} 1028 1029// lastTwoComponents returns at most the last two path components 1030// of v, using either / or \ as the path separator. 1031func lastTwoComponents(v string) string { 1032 nslash := 0 1033 for i := len(v) - 1; i >= 0; i-- { 1034 if v[i] == '/' || v[i] == '\\' { 1035 nslash++ 1036 if nslash == 2 { 1037 return v[i:] 1038 } 1039 } 1040 } 1041 return v 1042} 1043 1044type visitFn func(node ast.Node) ast.Visitor 1045 1046func (fn visitFn) Visit(node ast.Node) ast.Visitor { 1047 return fn(node) 1048} 1049 1050func findImportStdlib(shortPkg string, symbols map[string]bool) (importPath string, rename, ok bool) { 1051 for symbol := range symbols { 1052 key := shortPkg + "." + symbol 1053 path := stdlib[key] 1054 if path == "" { 1055 if key == "rand.Read" { 1056 continue 1057 } 1058 return "", false, false 1059 } 1060 if importPath != "" && importPath != path { 1061 // Ambiguous. Symbols pointed to different things. 1062 return "", false, false 1063 } 1064 importPath = path 1065 } 1066 if importPath == "" && shortPkg == "rand" && symbols["Read"] { 1067 return "crypto/rand", false, true 1068 } 1069 return importPath, false, importPath != "" 1070} 1071 1072// fileInDir reports whether the provided file path looks like 1073// it's in dir. (without hitting the filesystem) 1074func fileInDir(file, dir string) bool { 1075 rest := strings.TrimPrefix(file, dir) 1076 if len(rest) == len(file) { 1077 // dir is not a prefix of file. 1078 return false 1079 } 1080 // Check for boundary: either nothing (file == dir), or a slash. 1081 return len(rest) == 0 || rest[0] == '/' || rest[0] == '\\' 1082} 1083