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