1// Copyright 2018 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 packages
6
7import (
8	"bytes"
9	"encoding/json"
10	"fmt"
11	"go/types"
12	"io/ioutil"
13	"log"
14	"os"
15	"os/exec"
16	"path/filepath"
17	"reflect"
18	"regexp"
19	"strings"
20	"sync"
21	"time"
22
23	"golang.org/x/tools/internal/gopathwalk"
24	"golang.org/x/tools/internal/semver"
25)
26
27// debug controls verbose logging.
28const debug = false
29
30// A goTooOldError reports that the go command
31// found by exec.LookPath is too old to use the new go list behavior.
32type goTooOldError struct {
33	error
34}
35
36// goListDriver uses the go list command to interpret the patterns and produce
37// the build system package structure.
38// See driver for more details.
39func goListDriver(cfg *Config, patterns ...string) (*driverResponse, error) {
40	var sizes types.Sizes
41	var sizeserr error
42	var sizeswg sync.WaitGroup
43	if cfg.Mode >= LoadTypes {
44		sizeswg.Add(1)
45		go func() {
46			sizes, sizeserr = getSizes(cfg)
47			sizeswg.Done()
48		}()
49	}
50
51	// Determine files requested in contains patterns
52	var containFiles []string
53	var packagesNamed []string
54	restPatterns := make([]string, 0, len(patterns))
55	// Extract file= and other [querytype]= patterns. Report an error if querytype
56	// doesn't exist.
57extractQueries:
58	for _, pattern := range patterns {
59		eqidx := strings.Index(pattern, "=")
60		if eqidx < 0 {
61			restPatterns = append(restPatterns, pattern)
62		} else {
63			query, value := pattern[:eqidx], pattern[eqidx+len("="):]
64			switch query {
65			case "file":
66				containFiles = append(containFiles, value)
67			case "pattern":
68				restPatterns = append(restPatterns, value)
69			case "name":
70				packagesNamed = append(packagesNamed, value)
71			case "": // not a reserved query
72				restPatterns = append(restPatterns, pattern)
73			default:
74				for _, rune := range query {
75					if rune < 'a' || rune > 'z' { // not a reserved query
76						restPatterns = append(restPatterns, pattern)
77						continue extractQueries
78					}
79				}
80				// Reject all other patterns containing "="
81				return nil, fmt.Errorf("invalid query type %q in query pattern %q", query, pattern)
82			}
83		}
84	}
85	patterns = restPatterns
86
87	// TODO(matloob): Remove the definition of listfunc and just use golistPackages once go1.12 is released.
88	var listfunc driver
89	listfunc = func(cfg *Config, words ...string) (*driverResponse, error) {
90		response, err := golistDriverCurrent(cfg, words...)
91		if _, ok := err.(goTooOldError); ok {
92			listfunc = golistDriverFallback
93			return listfunc(cfg, words...)
94		}
95		listfunc = golistDriverCurrent
96		return response, err
97	}
98
99	var response *driverResponse
100	var err error
101
102	// see if we have any patterns to pass through to go list.
103	if len(restPatterns) > 0 {
104		response, err = listfunc(cfg, restPatterns...)
105		if err != nil {
106			return nil, err
107		}
108	} else {
109		response = &driverResponse{}
110	}
111
112	sizeswg.Wait()
113	if sizeserr != nil {
114		return nil, sizeserr
115	}
116	// types.SizesFor always returns nil or a *types.StdSizes
117	response.Sizes, _ = sizes.(*types.StdSizes)
118
119	if len(containFiles) == 0 && len(packagesNamed) == 0 {
120		return response, nil
121	}
122
123	seenPkgs := make(map[string]*Package) // for deduplication. different containing queries could produce same packages
124	for _, pkg := range response.Packages {
125		seenPkgs[pkg.ID] = pkg
126	}
127	addPkg := func(p *Package) {
128		if _, ok := seenPkgs[p.ID]; ok {
129			return
130		}
131		seenPkgs[p.ID] = p
132		response.Packages = append(response.Packages, p)
133	}
134
135	containsResults, err := runContainsQueries(cfg, listfunc, addPkg, containFiles)
136	if err != nil {
137		return nil, err
138	}
139	response.Roots = append(response.Roots, containsResults...)
140
141	namedResults, err := runNamedQueries(cfg, listfunc, addPkg, packagesNamed)
142	if err != nil {
143		return nil, err
144	}
145	response.Roots = append(response.Roots, namedResults...)
146	return response, nil
147}
148
149func runContainsQueries(cfg *Config, driver driver, addPkg func(*Package), queries []string) ([]string, error) {
150	var results []string
151	for _, query := range queries {
152		// TODO(matloob): Do only one query per directory.
153		fdir := filepath.Dir(query)
154		cfg.Dir = fdir
155		dirResponse, err := driver(cfg, ".")
156		if err != nil {
157			return nil, err
158		}
159		isRoot := make(map[string]bool, len(dirResponse.Roots))
160		for _, root := range dirResponse.Roots {
161			isRoot[root] = true
162		}
163		for _, pkg := range dirResponse.Packages {
164			// Add any new packages to the main set
165			// We don't bother to filter packages that will be dropped by the changes of roots,
166			// that will happen anyway during graph construction outside this function.
167			// Over-reporting packages is not a problem.
168			addPkg(pkg)
169			// if the package was not a root one, it cannot have the file
170			if !isRoot[pkg.ID] {
171				continue
172			}
173			for _, pkgFile := range pkg.GoFiles {
174				if filepath.Base(query) == filepath.Base(pkgFile) {
175					results = append(results, pkg.ID)
176					break
177				}
178			}
179		}
180	}
181	return results, nil
182}
183
184// modCacheRegexp splits a path in a module cache into module, module version, and package.
185var modCacheRegexp = regexp.MustCompile(`(.*)@([^/\\]*)(.*)`)
186
187func runNamedQueries(cfg *Config, driver driver, addPkg func(*Package), queries []string) ([]string, error) {
188	// calling `go env` isn't free; bail out if there's nothing to do.
189	if len(queries) == 0 {
190		return nil, nil
191	}
192	// Determine which directories are relevant to scan.
193	roots, modRoot, err := roots(cfg)
194	if err != nil {
195		return nil, err
196	}
197
198	// Scan the selected directories. Simple matches, from GOPATH/GOROOT
199	// or the local module, can simply be "go list"ed. Matches from the
200	// module cache need special treatment.
201	var matchesMu sync.Mutex
202	var simpleMatches, modCacheMatches []string
203	add := func(root gopathwalk.Root, dir string) {
204		// Walk calls this concurrently; protect the result slices.
205		matchesMu.Lock()
206		defer matchesMu.Unlock()
207
208		path := dir[len(root.Path)+1:]
209		if pathMatchesQueries(path, queries) {
210			switch root.Type {
211			case gopathwalk.RootModuleCache:
212				modCacheMatches = append(modCacheMatches, path)
213			case gopathwalk.RootCurrentModule:
214				// We'd need to read go.mod to find the full
215				// import path. Relative's easier.
216				rel, err := filepath.Rel(cfg.Dir, dir)
217				if err != nil {
218					// This ought to be impossible, since
219					// we found dir in the current module.
220					panic(err)
221				}
222				simpleMatches = append(simpleMatches, "./"+rel)
223			case gopathwalk.RootGOPATH, gopathwalk.RootGOROOT:
224				simpleMatches = append(simpleMatches, path)
225			}
226		}
227	}
228
229	startWalk := time.Now()
230	gopathwalk.Walk(roots, add, gopathwalk.Options{ModulesEnabled: modRoot != "", Debug: debug})
231	if debug {
232		log.Printf("%v for walk", time.Since(startWalk))
233	}
234
235	// Weird special case: the top-level package in a module will be in
236	// whatever directory the user checked the repository out into. It's
237	// more reasonable for that to not match the package name. So, if there
238	// are any Go files in the mod root, query it just to be safe.
239	if modRoot != "" {
240		rel, err := filepath.Rel(cfg.Dir, modRoot)
241		if err != nil {
242			panic(err) // See above.
243		}
244
245		files, err := ioutil.ReadDir(modRoot)
246		for _, f := range files {
247			if strings.HasSuffix(f.Name(), ".go") {
248				simpleMatches = append(simpleMatches, rel)
249				break
250			}
251		}
252	}
253
254	var results []string
255	addResponse := func(r *driverResponse) {
256		for _, pkg := range r.Packages {
257			addPkg(pkg)
258			for _, name := range queries {
259				if pkg.Name == name {
260					results = append(results, pkg.ID)
261					break
262				}
263			}
264		}
265	}
266
267	if len(simpleMatches) != 0 {
268		resp, err := driver(cfg, simpleMatches...)
269		if err != nil {
270			return nil, err
271		}
272		addResponse(resp)
273	}
274
275	// Module cache matches are tricky. We want to avoid downloading new
276	// versions of things, so we need to use the ones present in the cache.
277	// go list doesn't accept version specifiers, so we have to write out a
278	// temporary module, and do the list in that module.
279	if len(modCacheMatches) != 0 {
280		// Collect all the matches, deduplicating by major version
281		// and preferring the newest.
282		type modInfo struct {
283			mod   string
284			major string
285		}
286		mods := make(map[modInfo]string)
287		var imports []string
288		for _, modPath := range modCacheMatches {
289			matches := modCacheRegexp.FindStringSubmatch(modPath)
290			mod, ver := filepath.ToSlash(matches[1]), matches[2]
291			importPath := filepath.ToSlash(filepath.Join(matches[1], matches[3]))
292
293			major := semver.Major(ver)
294			if prevVer, ok := mods[modInfo{mod, major}]; !ok || semver.Compare(ver, prevVer) > 0 {
295				mods[modInfo{mod, major}] = ver
296			}
297
298			imports = append(imports, importPath)
299		}
300
301		// Build the temporary module.
302		var gomod bytes.Buffer
303		gomod.WriteString("module modquery\nrequire (\n")
304		for mod, version := range mods {
305			gomod.WriteString("\t" + mod.mod + " " + version + "\n")
306		}
307		gomod.WriteString(")\n")
308
309		tmpCfg := *cfg
310
311		// We're only trying to look at stuff in the module cache, so
312		// disable the network. This should speed things up, and has
313		// prevented errors in at least one case, #28518.
314		tmpCfg.Env = append(append([]string{"GOPROXY=off"}, cfg.Env...))
315
316		var err error
317		tmpCfg.Dir, err = ioutil.TempDir("", "gopackages-modquery")
318		if err != nil {
319			return nil, err
320		}
321		defer os.RemoveAll(tmpCfg.Dir)
322
323		if err := ioutil.WriteFile(filepath.Join(tmpCfg.Dir, "go.mod"), gomod.Bytes(), 0777); err != nil {
324			return nil, fmt.Errorf("writing go.mod for module cache query: %v", err)
325		}
326
327		// Run the query, using the import paths calculated from the matches above.
328		resp, err := driver(&tmpCfg, imports...)
329		if err != nil {
330			return nil, fmt.Errorf("querying module cache matches: %v", err)
331		}
332		addResponse(resp)
333	}
334
335	return results, nil
336}
337
338func getSizes(cfg *Config) (types.Sizes, error) {
339	stdout, err := invokeGo(cfg, "env", "GOARCH")
340	if err != nil {
341		return nil, err
342	}
343
344	goarch := strings.TrimSpace(stdout.String())
345	// Assume "gc" because SizesFor doesn't respond to other compilers.
346	// TODO(matloob): add support for gccgo as needed.
347	return types.SizesFor("gc", goarch), nil
348}
349
350// roots selects the appropriate paths to walk based on the passed-in configuration,
351// particularly the environment and the presence of a go.mod in cfg.Dir's parents.
352func roots(cfg *Config) ([]gopathwalk.Root, string, error) {
353	stdout, err := invokeGo(cfg, "env", "GOROOT", "GOPATH", "GOMOD")
354	if err != nil {
355		return nil, "", err
356	}
357
358	fields := strings.Split(stdout.String(), "\n")
359	if len(fields) != 4 || len(fields[3]) != 0 {
360		return nil, "", fmt.Errorf("go env returned unexpected output: %q", stdout.String())
361	}
362	goroot, gopath, gomod := fields[0], filepath.SplitList(fields[1]), fields[2]
363	var modDir string
364	if gomod != "" {
365		modDir = filepath.Dir(gomod)
366	}
367
368	var roots []gopathwalk.Root
369	// Always add GOROOT.
370	roots = append(roots, gopathwalk.Root{filepath.Join(goroot, "/src"), gopathwalk.RootGOROOT})
371	// If modules are enabled, scan the module dir.
372	if modDir != "" {
373		roots = append(roots, gopathwalk.Root{modDir, gopathwalk.RootCurrentModule})
374	}
375	// Add either GOPATH/src or GOPATH/pkg/mod, depending on module mode.
376	for _, p := range gopath {
377		if modDir != "" {
378			roots = append(roots, gopathwalk.Root{filepath.Join(p, "/pkg/mod"), gopathwalk.RootModuleCache})
379		} else {
380			roots = append(roots, gopathwalk.Root{filepath.Join(p, "/src"), gopathwalk.RootGOPATH})
381		}
382	}
383
384	return roots, modDir, nil
385}
386
387// These functions were copied from goimports. See further documentation there.
388
389// pathMatchesQueries is adapted from pkgIsCandidate.
390// TODO: is it reasonable to do Contains here, rather than an exact match on a path component?
391func pathMatchesQueries(path string, queries []string) bool {
392	lastTwo := lastTwoComponents(path)
393	for _, query := range queries {
394		if strings.Contains(lastTwo, query) {
395			return true
396		}
397		if hasHyphenOrUpperASCII(lastTwo) && !hasHyphenOrUpperASCII(query) {
398			lastTwo = lowerASCIIAndRemoveHyphen(lastTwo)
399			if strings.Contains(lastTwo, query) {
400				return true
401			}
402		}
403	}
404	return false
405}
406
407// lastTwoComponents returns at most the last two path components
408// of v, using either / or \ as the path separator.
409func lastTwoComponents(v string) string {
410	nslash := 0
411	for i := len(v) - 1; i >= 0; i-- {
412		if v[i] == '/' || v[i] == '\\' {
413			nslash++
414			if nslash == 2 {
415				return v[i:]
416			}
417		}
418	}
419	return v
420}
421
422func hasHyphenOrUpperASCII(s string) bool {
423	for i := 0; i < len(s); i++ {
424		b := s[i]
425		if b == '-' || ('A' <= b && b <= 'Z') {
426			return true
427		}
428	}
429	return false
430}
431
432func lowerASCIIAndRemoveHyphen(s string) (ret string) {
433	buf := make([]byte, 0, len(s))
434	for i := 0; i < len(s); i++ {
435		b := s[i]
436		switch {
437		case b == '-':
438			continue
439		case 'A' <= b && b <= 'Z':
440			buf = append(buf, b+('a'-'A'))
441		default:
442			buf = append(buf, b)
443		}
444	}
445	return string(buf)
446}
447
448// Fields must match go list;
449// see $GOROOT/src/cmd/go/internal/load/pkg.go.
450type jsonPackage struct {
451	ImportPath      string
452	Dir             string
453	Name            string
454	Export          string
455	GoFiles         []string
456	CompiledGoFiles []string
457	CFiles          []string
458	CgoFiles        []string
459	CXXFiles        []string
460	MFiles          []string
461	HFiles          []string
462	FFiles          []string
463	SFiles          []string
464	SwigFiles       []string
465	SwigCXXFiles    []string
466	SysoFiles       []string
467	Imports         []string
468	ImportMap       map[string]string
469	Deps            []string
470	TestGoFiles     []string
471	TestImports     []string
472	XTestGoFiles    []string
473	XTestImports    []string
474	ForTest         string // q in a "p [q.test]" package, else ""
475	DepOnly         bool
476
477	Error *jsonPackageError
478}
479
480type jsonPackageError struct {
481	ImportStack []string
482	Pos         string
483	Err         string
484}
485
486func otherFiles(p *jsonPackage) [][]string {
487	return [][]string{p.CFiles, p.CXXFiles, p.MFiles, p.HFiles, p.FFiles, p.SFiles, p.SwigFiles, p.SwigCXXFiles, p.SysoFiles}
488}
489
490// golistDriverCurrent uses the "go list" command to expand the
491// pattern words and return metadata for the specified packages.
492// dir may be "" and env may be nil, as per os/exec.Command.
493func golistDriverCurrent(cfg *Config, words ...string) (*driverResponse, error) {
494	// go list uses the following identifiers in ImportPath and Imports:
495	//
496	// 	"p"			-- importable package or main (command)
497	//      "q.test"		-- q's test executable
498	// 	"p [q.test]"		-- variant of p as built for q's test executable
499	//	"q_test [q.test]"	-- q's external test package
500	//
501	// The packages p that are built differently for a test q.test
502	// are q itself, plus any helpers used by the external test q_test,
503	// typically including "testing" and all its dependencies.
504
505	// Run "go list" for complete
506	// information on the specified packages.
507	buf, err := invokeGo(cfg, golistargs(cfg, words)...)
508	if err != nil {
509		return nil, err
510	}
511	seen := make(map[string]*jsonPackage)
512	// Decode the JSON and convert it to Package form.
513	var response driverResponse
514	for dec := json.NewDecoder(buf); dec.More(); {
515		p := new(jsonPackage)
516		if err := dec.Decode(p); err != nil {
517			return nil, fmt.Errorf("JSON decoding failed: %v", err)
518		}
519
520		if p.ImportPath == "" {
521			// The documentation for go list says that “[e]rroneous packages will have
522			// a non-empty ImportPath”. If for some reason it comes back empty, we
523			// prefer to error out rather than silently discarding data or handing
524			// back a package without any way to refer to it.
525			if p.Error != nil {
526				return nil, Error{
527					Pos: p.Error.Pos,
528					Msg: p.Error.Err,
529				}
530			}
531			return nil, fmt.Errorf("package missing import path: %+v", p)
532		}
533
534		if old, found := seen[p.ImportPath]; found {
535			if !reflect.DeepEqual(p, old) {
536				return nil, fmt.Errorf("go list repeated package %v with different values", p.ImportPath)
537			}
538			// skip the duplicate
539			continue
540		}
541		seen[p.ImportPath] = p
542
543		pkg := &Package{
544			Name:            p.Name,
545			ID:              p.ImportPath,
546			GoFiles:         absJoin(p.Dir, p.GoFiles, p.CgoFiles),
547			CompiledGoFiles: absJoin(p.Dir, p.CompiledGoFiles),
548			OtherFiles:      absJoin(p.Dir, otherFiles(p)...),
549		}
550
551		// Extract the PkgPath from the package's ID.
552		if i := strings.IndexByte(pkg.ID, ' '); i >= 0 {
553			pkg.PkgPath = pkg.ID[:i]
554		} else {
555			pkg.PkgPath = pkg.ID
556		}
557
558		if pkg.PkgPath == "unsafe" {
559			pkg.GoFiles = nil // ignore fake unsafe.go file
560		}
561
562		// Assume go list emits only absolute paths for Dir.
563		if p.Dir != "" && !filepath.IsAbs(p.Dir) {
564			log.Fatalf("internal error: go list returned non-absolute Package.Dir: %s", p.Dir)
565		}
566
567		if p.Export != "" && !filepath.IsAbs(p.Export) {
568			pkg.ExportFile = filepath.Join(p.Dir, p.Export)
569		} else {
570			pkg.ExportFile = p.Export
571		}
572
573		// imports
574		//
575		// Imports contains the IDs of all imported packages.
576		// ImportsMap records (path, ID) only where they differ.
577		ids := make(map[string]bool)
578		for _, id := range p.Imports {
579			ids[id] = true
580		}
581		pkg.Imports = make(map[string]*Package)
582		for path, id := range p.ImportMap {
583			pkg.Imports[path] = &Package{ID: id} // non-identity import
584			delete(ids, id)
585		}
586		for id := range ids {
587			if id == "C" {
588				continue
589			}
590
591			pkg.Imports[id] = &Package{ID: id} // identity import
592		}
593		if !p.DepOnly {
594			response.Roots = append(response.Roots, pkg.ID)
595		}
596
597		// TODO(matloob): Temporary hack since CompiledGoFiles isn't always set.
598		if len(pkg.CompiledGoFiles) == 0 {
599			pkg.CompiledGoFiles = pkg.GoFiles
600		}
601
602		if p.Error != nil {
603			pkg.Errors = append(pkg.Errors, Error{
604				Pos: p.Error.Pos,
605				Msg: p.Error.Err,
606			})
607		}
608
609		response.Packages = append(response.Packages, pkg)
610	}
611
612	return &response, nil
613}
614
615// absJoin absolutizes and flattens the lists of files.
616func absJoin(dir string, fileses ...[]string) (res []string) {
617	for _, files := range fileses {
618		for _, file := range files {
619			if !filepath.IsAbs(file) {
620				file = filepath.Join(dir, file)
621			}
622			res = append(res, file)
623		}
624	}
625	return res
626}
627
628func golistargs(cfg *Config, words []string) []string {
629	fullargs := []string{
630		"list", "-e", "-json", "-compiled",
631		fmt.Sprintf("-test=%t", cfg.Tests),
632		fmt.Sprintf("-export=%t", usesExportData(cfg)),
633		fmt.Sprintf("-deps=%t", cfg.Mode >= LoadImports),
634	}
635	fullargs = append(fullargs, cfg.BuildFlags...)
636	fullargs = append(fullargs, "--")
637	fullargs = append(fullargs, words...)
638	return fullargs
639}
640
641// invokeGo returns the stdout of a go command invocation.
642func invokeGo(cfg *Config, args ...string) (*bytes.Buffer, error) {
643	if debug {
644		defer func(start time.Time) { log.Printf("%s for %v", time.Since(start), cmdDebugStr(cfg, args...)) }(time.Now())
645	}
646	stdout := new(bytes.Buffer)
647	stderr := new(bytes.Buffer)
648	cmd := exec.CommandContext(cfg.Context, "go", args...)
649	// On darwin the cwd gets resolved to the real path, which breaks anything that
650	// expects the working directory to keep the original path, including the
651	// go command when dealing with modules.
652	// The Go stdlib has a special feature where if the cwd and the PWD are the
653	// same node then it trusts the PWD, so by setting it in the env for the child
654	// process we fix up all the paths returned by the go command.
655	cmd.Env = append(append([]string{}, cfg.Env...), "PWD="+cfg.Dir)
656	cmd.Dir = cfg.Dir
657	cmd.Stdout = stdout
658	cmd.Stderr = stderr
659	if err := cmd.Run(); err != nil {
660		exitErr, ok := err.(*exec.ExitError)
661		if !ok {
662			// Catastrophic error:
663			// - executable not found
664			// - context cancellation
665			return nil, fmt.Errorf("couldn't exec 'go %v': %s %T", args, err, err)
666		}
667
668		// Old go version?
669		if strings.Contains(stderr.String(), "flag provided but not defined") {
670			return nil, goTooOldError{fmt.Errorf("unsupported version of go: %s: %s", exitErr, stderr)}
671		}
672
673		// Export mode entails a build.
674		// If that build fails, errors appear on stderr
675		// (despite the -e flag) and the Export field is blank.
676		// Do not fail in that case.
677		if !usesExportData(cfg) {
678			return nil, fmt.Errorf("go %v: %s: %s", args, exitErr, stderr)
679		}
680	}
681
682	// As of writing, go list -export prints some non-fatal compilation
683	// errors to stderr, even with -e set. We would prefer that it put
684	// them in the Package.Error JSON (see http://golang.org/issue/26319).
685	// In the meantime, there's nowhere good to put them, but they can
686	// be useful for debugging. Print them if $GOPACKAGESPRINTGOLISTERRORS
687	// is set.
688	if len(stderr.Bytes()) != 0 && os.Getenv("GOPACKAGESPRINTGOLISTERRORS") != "" {
689		fmt.Fprintf(os.Stderr, "%s stderr: <<%s>>\n", cmdDebugStr(cfg, args...), stderr)
690	}
691
692	// debugging
693	if false {
694		fmt.Fprintf(os.Stderr, "%s stdout: <<%s>>\n", cmdDebugStr(cfg, args...), stdout)
695	}
696
697	return stdout, nil
698}
699
700func cmdDebugStr(cfg *Config, args ...string) string {
701	env := make(map[string]string)
702	for _, kv := range cfg.Env {
703		split := strings.Split(kv, "=")
704		k, v := split[0], split[1]
705		env[k] = v
706	}
707
708	return fmt.Sprintf("GOROOT=%v GOPATH=%v GO111MODULE=%v PWD=%v go %v", env["GOROOT"], env["GOPATH"], env["GO111MODULE"], env["PWD"], args)
709}
710