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.
23 "golang.org/x/tools/cmd/guru/serial"
24 "golang.org/x/tools/go/buildutil"
25 "golang.org/x/tools/go/loader"
26 "golang.org/x/tools/imports"
27 "golang.org/x/tools/refactor/importgraph"
30 // The referrers function reports all identifiers that resolve to the same object
31 // as the queried identifier, within any package in the workspace.
32 func referrers(q *Query) error {
33 fset := token.NewFileSet()
34 lconf := loader.Config{Fset: fset, Build: q.Build}
37 if _, err := importQueryPackage(q.Pos, &lconf); err != nil {
41 // Load tests of the query package
42 // even if the query location is not in the tests.
43 for path := range lconf.ImportPkgs {
44 lconf.ImportPkgs[path] = true
47 // Load/parse/type-check the query package.
48 lprog, err := lconf.Load()
53 qpos, err := parseQueryPos(lprog, q.Pos, false)
58 id, _ := qpos.path[0].(*ast.Ident)
60 return fmt.Errorf("no identifier here")
63 obj := qpos.info.ObjectOf(id)
65 // Happens for y in "switch y := x.(type)",
66 // the package declaration,
67 // and unresolved identifiers.
68 if _, ok := qpos.path[1].(*ast.File); ok { // package decl?
69 return packageReferrers(q, qpos.info.Pkg.Path())
71 return fmt.Errorf("no object for identifier: %T", qpos.path[1])
74 // Imported package name?
75 if pkgname, ok := obj.(*types.PkgName); ok {
76 return packageReferrers(q, pkgname.Imported().Path())
80 return fmt.Errorf("references to predeclared %q are everywhere!", obj.Name())
83 q.Output(fset, &referrersInitialResult{
88 // For a globally accessible object defined in package P, we
89 // must load packages that depend on P. Specifically, for a
90 // package-level object, we need load only direct importers
91 // of P, but for a field or method, we must load
92 // any package that transitively imports P.
94 if global, pkglevel := classify(obj); global {
96 return globalReferrersPkgLevel(q, obj, fset)
98 // We'll use the object's position to identify it in the larger program.
99 objposn := fset.Position(obj.Pos())
100 defpkg := obj.Pkg().Path() // defining package
101 return globalReferrers(q, qpos.info.Pkg.Path(), defpkg, objposn)
104 outputUses(q, fset, usesOf(obj, qpos.info), obj.Pkg())
106 return nil // success
109 // classify classifies objects by how far
110 // we have to look to find references to them.
111 func classify(obj types.Object) (global, pkglevel bool) {
113 if obj.Parent() == nil {
114 // selectable object (field or method)
117 if obj.Parent() == obj.Pkg().Scope() {
118 // lexical object (package-level var/const/func/type)
122 // object with unexported named or defined in local scope
126 // packageReferrers reports all references to the specified package
127 // throughout the workspace.
128 func packageReferrers(q *Query, path string) error {
129 // Scan the workspace and build the import graph.
130 // Ignore broken packages.
131 _, rev, _ := importgraph.Build(q.Build)
133 // Find the set of packages that directly import the query package.
134 // Only those packages need typechecking of function bodies.
137 // Load the larger program.
138 fset := token.NewFileSet()
139 lconf := loader.Config{
142 TypeCheckFuncBodies: func(p string) bool {
143 return users[strings.TrimSuffix(p, "_test")]
148 // The importgraph doesn't treat external test packages
149 // as separate nodes, so we must use ImportWithTests.
150 for path := range users {
151 lconf.ImportWithTests(path)
154 // Subtle! AfterTypeCheck needs no mutex for qpkg because the
155 // topological import order gives us the necessary happens-before edges.
156 // TODO(adonovan): what about import cycles?
157 var qpkg *types.Package
159 // For efficiency, we scan each package for references
160 // just after it has been type-checked. The loader calls
161 // AfterTypeCheck (concurrently), providing us with a stream of
163 lconf.AfterTypeCheck = func(info *loader.PackageInfo, files []*ast.File) {
164 // AfterTypeCheck may be called twice for the same package due to augmentation.
166 if info.Pkg.Path() == path && qpkg == nil {
167 // Found the package of interest.
169 fakepkgname := types.NewPkgName(token.NoPos, qpkg, qpkg.Name(), qpkg)
170 q.Output(fset, &referrersInitialResult{
172 obj: fakepkgname, // bogus
176 // Only inspect packages that directly import the
177 // declaring package (and thus were type-checked).
178 if lconf.TypeCheckFuncBodies(info.Pkg.Path()) {
179 // Find PkgNames that refer to qpkg.
180 // TODO(adonovan): perhaps more useful would be to show imports
181 // of the package instead of qualified identifiers.
182 var refs []*ast.Ident
183 for id, obj := range info.Uses {
184 if obj, ok := obj.(*types.PkgName); ok && obj.Imported() == qpkg {
185 refs = append(refs, id)
188 outputUses(q, fset, refs, info.Pkg)
191 clearInfoFields(info) // save memory
194 lconf.Load() // ignore error
197 log.Fatalf("query package %q not found during reloading", path)
203 func usesOf(queryObj types.Object, info *loader.PackageInfo) []*ast.Ident {
204 var refs []*ast.Ident
205 for id, obj := range info.Uses {
206 if sameObj(queryObj, obj) {
207 refs = append(refs, id)
213 // outputUses outputs a result describing refs, which appear in the package denoted by info.
214 func outputUses(q *Query, fset *token.FileSet, refs []*ast.Ident, pkg *types.Package) {
216 sort.Sort(byNamePos{fset, refs})
217 q.Output(fset, &referrersPackageResult{
226 // globalReferrers reports references throughout the entire workspace to the
227 // object (a field or method) at the specified source position.
228 // Its defining package is defpkg, and the query package is qpkg.
229 func globalReferrers(q *Query, qpkg, defpkg string, objposn token.Position) error {
230 // Scan the workspace and build the import graph.
231 // Ignore broken packages.
232 _, rev, _ := importgraph.Build(q.Build)
234 // Find the set of packages that depend on defpkg.
235 // Only function bodies in those packages need type-checking.
236 users := rev.Search(defpkg) // transitive importers
238 // Prepare to load the larger program.
239 fset := token.NewFileSet()
240 lconf := loader.Config{
243 TypeCheckFuncBodies: func(p string) bool {
244 return users[strings.TrimSuffix(p, "_test")]
249 // The importgraph doesn't treat external test packages
250 // as separate nodes, so we must use ImportWithTests.
251 for path := range users {
252 lconf.ImportWithTests(path)
255 // The remainder of this function is somewhat tricky because it
256 // operates on the concurrent stream of packages observed by the
257 // loader's AfterTypeCheck hook. Most of guru's helper
258 // functions assume the entire program has already been loaded,
259 // so we can't use them here.
260 // TODO(adonovan): smooth things out once the other changes have landed.
262 // Results are reported concurrently from within the
263 // AfterTypeCheck hook. The program may provide a useful stream
264 // of information even if the user doesn't let the program run
272 // For efficiency, we scan each package for references
273 // just after it has been type-checked. The loader calls
274 // AfterTypeCheck (concurrently), providing us with a stream of
276 lconf.AfterTypeCheck = func(info *loader.PackageInfo, files []*ast.File) {
277 // AfterTypeCheck may be called twice for the same package due to augmentation.
279 // Only inspect packages that depend on the declaring package
280 // (and thus were type-checked).
281 if lconf.TypeCheckFuncBodies(info.Pkg.Path()) {
282 // Record the query object and its package when we see it.
284 if qobj == nil && info.Pkg.Path() == defpkg {
285 // Find the object by its position (slightly ugly).
286 qobj = findObject(fset, &info.Info, objposn)
288 // It really ought to be there;
289 // we found it once already.
290 log.Fatalf("object at %s not found in package %s",
297 // Look for references to the query object.
299 outputUses(q, fset, usesOf(obj, info), info.Pkg)
303 clearInfoFields(info) // save memory
306 lconf.Load() // ignore error
309 log.Fatal("query object not found during reloading")
312 return nil // success
315 // globalReferrersPkgLevel reports references throughout the entire workspace to the package-level object obj.
316 // It assumes that the query object itself has already been reported.
317 func globalReferrersPkgLevel(q *Query, obj types.Object, fset *token.FileSet) error {
318 // globalReferrersPkgLevel uses go/ast and friends instead of go/types.
319 // This affords a considerable performance benefit.
320 // It comes at the cost of some code complexity.
322 // Here's a high level summary.
324 // The goal is to find references to the query object p.Q.
325 // There are several possible scenarios, each handled differently.
327 // 1. We are looking in a package other than p, and p is not dot-imported.
328 // This is the simplest case. Q must be referred to as n.Q,
329 // where n is the name under which p is imported.
330 // We look at all imports of p to gather all names under which it is imported.
331 // (In the typical case, it is imported only once, under its default name.)
332 // Then we look at all selector expressions and report any matches.
334 // 2. We are looking in a package other than p, and p is dot-imported.
335 // In this case, Q will be referred to just as Q.
336 // Furthermore, go/ast's object resolution will not be able to resolve
337 // Q to any other object, unlike any local (file- or function- or block-scoped) object.
338 // So we look at all matching identifiers and report all unresolvable ones.
340 // 3. We are looking in package p.
341 // (Care must be taken to separate p and p_test (an xtest package),
342 // and make sure that they are treated as separate packages.)
343 // In this case, we give go/ast the entire package for object resolution,
344 // instead of going file by file.
345 // We then iterate over all identifiers that resolve to the query object.
346 // (The query object itself has already been reported, so we don't re-report it.)
348 // We always skip all files that don't contain the string Q, as they cannot be
349 // relevant to finding references to Q.
351 // We parse all files leniently. In the presence of parsing errors, results are best-effort.
353 // Scan the workspace and build the import graph.
354 // Ignore broken packages.
355 _, rev, _ := importgraph.Build(q.Build)
357 // Find the set of packages that directly import defpkg.
358 defpkg := obj.Pkg().Path()
359 defpkg = strings.TrimSuffix(defpkg, "_test") // package x_test actually has package name x
360 defpkg = imports.VendorlessPath(defpkg) // remove vendor goop
364 users = make(map[string]bool)
366 // We also need to check defpkg itself, and its xtests.
367 // For the reverse graph packages, we process xtests with the main package.
368 // defpkg gets special handling; we must distinguish between in-package vs out-of-package.
369 // To make the control flow below simpler, add defpkg and defpkg xtest placeholders.
370 // Use "!test" instead of "_test" because "!" is not a valid character in an import path.
371 // (More precisely, it is not guaranteed to be a valid character in an import path,
372 // so it is unlikely that it will be in use. See https://golang.org/ref/spec#Import_declarations.)
374 users[defpkg+"!test"] = true
376 cwd, err := os.Getwd()
381 defname := obj.Pkg().Name() // name of defining package, used for imports using import path only
382 isxtest := strings.HasSuffix(defname, "_test") // indicates whether the query object is defined in an xtest package
385 namebytes := []byte(name) // byte slice version of query object name, for early filtering
386 objpos := fset.Position(obj.Pos()) // position of query object, used to prevent re-emitting original decl
388 sema := make(chan struct{}, 20) // counting semaphore to limit I/O concurrency
389 var wg sync.WaitGroup
391 for u := range users {
397 uIsXTest := strings.HasSuffix(u, "!test") // indicates whether this package is the special defpkg xtest package
398 u = strings.TrimSuffix(u, "!test")
401 sema <- struct{}{} // acquire token
402 pkg, err := q.Build.Import(u, cwd, build.IgnoreVendor)
403 <-sema // release token
408 // If we're not in the query package,
409 // the object is in another package regardless,
410 // so we want to process all files.
411 // If we are in the query package,
412 // we want to only process the files that are
413 // part of that query package;
414 // that set depends on whether the query package itself is an xtest.
415 inQueryPkg := u == defpkg && isxtest == uIsXTest
417 if !inQueryPkg || !isxtest {
418 files = append(files, pkg.GoFiles...)
419 files = append(files, pkg.TestGoFiles...)
420 files = append(files, pkg.CgoFiles...) // use raw cgo files, as we're only parsing
422 if !inQueryPkg || isxtest {
423 files = append(files, pkg.XTestGoFiles...)
430 var deffiles map[string]*ast.File
432 deffiles = make(map[string]*ast.File)
435 buf := new(bytes.Buffer) // reusable buffer for reading files
437 for _, file := range files {
438 if !buildutil.IsAbsPath(q.Build, file) {
439 file = buildutil.JoinPath(q.Build, pkg.Dir, file)
442 sema <- struct{}{} // acquire token
443 src, err := readFile(q.Build, file, buf)
444 <-sema // release token
449 // Fast path: If the object's name isn't present anywhere in the source, ignore the file.
450 if !bytes.Contains(src, namebytes) {
455 // If we're in the query package, we defer final processing until we have
456 // parsed all of the candidate files in the package.
457 // Best effort; allow errors and use what we can from what remains.
458 f, _ := parser.ParseFile(fset, file, src, parser.AllErrors)
465 // We aren't in the query package. Go file by file.
467 // Parse out only the imports, to check whether the defining package
468 // was imported, and if so, under what names.
469 // Best effort; allow errors and use what we can from what remains.
470 f, _ := parser.ParseFile(fset, file, src, parser.ImportsOnly|parser.AllErrors)
475 // pkgnames is the set of names by which defpkg is imported in this file.
476 // (Multiple imports in the same file are legal but vanishingly rare.)
477 pkgnames := make([]string, 0, 1)
479 for _, imp := range f.Imports {
480 path, err := strconv.Unquote(imp.Path.Value)
481 if err != nil || path != defpkg {
485 case imp.Name == nil:
486 pkgnames = append(pkgnames, defname)
487 case imp.Name.Name == ".":
490 pkgnames = append(pkgnames, imp.Name.Name)
493 if len(pkgnames) == 0 && !isdotimport {
494 // Defining package not imported, bail.
498 // Re-parse the entire file.
499 // Parse errors are ok; we'll do the best we can with a partial AST, if we have one.
500 f, _ = parser.ParseFile(fset, file, src, parser.AllErrors)
505 // Walk the AST looking for references.
506 var refs []*ast.Ident
507 ast.Inspect(f, func(n ast.Node) bool {
508 // Check selector expressions.
509 // If the selector matches the target name,
510 // and the expression is one of the names
511 // that the defining package was imported under,
512 // then we have a match.
513 if sel, ok := n.(*ast.SelectorExpr); ok && sel.Sel.Name == name {
514 if id, ok := sel.X.(*ast.Ident); ok {
515 for _, n := range pkgnames {
517 refs = append(refs, sel.Sel)
518 // Don't recurse further, to avoid duplicate entries
519 // from the dot import check below.
525 // Dot imports are special.
526 // Objects imported from the defining package are placed in the package scope.
527 // go/ast does not resolve them to an object.
528 // At all other scopes (file, local), go/ast can do the resolution.
529 // So we're looking for object-free idents with the right name.
530 // The only other way to get something with the right name at the package scope
531 // is to *be* the defining package. We handle that case separately (inQueryPkg).
533 if id, ok := n.(*ast.Ident); ok && id.Obj == nil && id.Name == name {
534 refs = append(refs, id)
541 // Emit any references we found.
543 q.Output(fset, &referrersPackageResult{
544 pkg: types.NewPackage(pkg.ImportPath, pkg.Name),
552 // If we're in the query package, we've now collected all the files in the package.
553 // (Or at least the ones that might contain references to the object.)
554 // Find and emit refs.
556 // Bundle the files together into a package.
557 // This does package-level object resolution.
558 qpkg, _ := ast.NewPackage(fset, deffiles, nil, nil)
559 // Look up the query object; we know that it is defined in the package scope.
560 pkgobj := qpkg.Scope.Objects[name]
562 panic("missing defpkg object for " + defpkg + "." + name)
564 // Find all references to the query object.
565 var refs []*ast.Ident
566 ast.Inspect(qpkg, func(n ast.Node) bool {
567 if id, ok := n.(*ast.Ident); ok {
568 // Check both that this is a reference to the query object
569 // and that it is not the query object itself;
570 // the query object itself was already emitted.
571 if id.Obj == pkgobj && objpos != fset.Position(id.Pos()) {
572 refs = append(refs, id)
579 q.Output(fset, &referrersPackageResult{
580 pkg: types.NewPackage(pkg.ImportPath, pkg.Name),
586 deffiles = nil // allow GC
596 // findObject returns the object defined at the specified position.
597 func findObject(fset *token.FileSet, info *types.Info, objposn token.Position) types.Object {
598 good := func(obj types.Object) bool {
602 posn := fset.Position(obj.Pos())
603 return posn.Filename == objposn.Filename && posn.Offset == objposn.Offset
605 for _, obj := range info.Defs {
610 for _, obj := range info.Implicits {
618 // same reports whether x and y are identical, or both are PkgNames
619 // that import the same Package.
621 func sameObj(x, y types.Object) bool {
625 if x, ok := x.(*types.PkgName); ok {
626 if y, ok := y.(*types.PkgName); ok {
627 return x.Imported() == y.Imported()
633 func clearInfoFields(info *loader.PackageInfo) {
634 // TODO(adonovan): opt: save memory by eliminating unneeded scopes/objects.
635 // (Requires go/types change for Go 1.7.)
636 // info.Pkg.Scope().ClearChildren()
638 // Discard the file ASTs and their accumulated type
639 // information to save memory.
641 info.Defs = make(map[*ast.Ident]types.Object)
642 info.Uses = make(map[*ast.Ident]types.Object)
643 info.Implicits = make(map[ast.Node]types.Object)
645 // Also, disable future collection of wholly unneeded
646 // type information for the package in case there is
647 // more type-checking to do (augmentation).
650 info.Selections = nil
653 // -------- utils --------
655 // An deterministic ordering for token.Pos that doesn't
656 // depend on the order in which packages were loaded.
657 func lessPos(fset *token.FileSet, x, y token.Pos) bool {
661 return fx.Name() < fy.Name()
666 type byNamePos struct {
671 func (p byNamePos) Len() int { return len(p.ids) }
672 func (p byNamePos) Swap(i, j int) { p.ids[i], p.ids[j] = p.ids[j], p.ids[i] }
673 func (p byNamePos) Less(i, j int) bool {
674 return lessPos(p.fset, p.ids[i].NamePos, p.ids[j].NamePos)
677 // referrersInitialResult is the initial result of a "referrers" query.
678 type referrersInitialResult struct {
679 qinfo *loader.PackageInfo
680 obj types.Object // object it denotes
683 func (r *referrersInitialResult) PrintPlain(printf printfFunc) {
684 printf(r.obj, "references to %s",
685 types.ObjectString(r.obj, types.RelativeTo(r.qinfo.Pkg)))
688 func (r *referrersInitialResult) JSON(fset *token.FileSet) []byte {
690 if pos := r.obj.Pos(); pos.IsValid() {
691 objpos = fset.Position(pos).String()
693 return toJSON(&serial.ReferrersInitial{
694 Desc: r.obj.String(),
699 // referrersPackageResult is the streaming result for one package of a "referrers" query.
700 type referrersPackageResult struct {
704 refs []*ast.Ident // set of all other references to it
707 // forEachRef calls f(id, text) for id in r.refs, in order.
708 // Text is the text of the line on which id appears.
709 func (r *referrersPackageResult) foreachRef(f func(id *ast.Ident, text string)) {
710 // Show referring lines, like grep.
711 type fileinfo struct {
713 linenums []int // line number of refs[i]
714 data chan interface{} // file contents or error
716 var fileinfos []*fileinfo
717 fileinfosByName := make(map[string]*fileinfo)
719 // First pass: start the file reads concurrently.
720 sema := make(chan struct{}, 20) // counting semaphore to limit I/O concurrency
721 for _, ref := range r.refs {
722 posn := r.fset.Position(ref.Pos())
723 fi := fileinfosByName[posn.Filename]
725 fi = &fileinfo{data: make(chan interface{})}
726 fileinfosByName[posn.Filename] = fi
727 fileinfos = append(fileinfos, fi)
729 // First request for this file:
730 // start asynchronous read.
732 sema <- struct{}{} // acquire token
733 content, err := readFile(r.build, posn.Filename, nil)
734 <-sema // release token
742 fi.refs = append(fi.refs, ref)
743 fi.linenums = append(fi.linenums, posn.Line)
746 // Second pass: print refs in original order.
747 // One line may have several refs at different columns.
748 for _, fi := range fileinfos {
749 v := <-fi.data // wait for I/O completion
751 // Print one item for all refs in a file that could not
752 // be loaded (perhaps due to //line directives).
753 if err, ok := v.(error); ok {
755 if more := len(fi.refs) - 1; more > 0 {
756 suffix = fmt.Sprintf(" (+ %d more refs in this file)", more)
758 f(fi.refs[0], err.Error()+suffix)
762 lines := bytes.Split(v.([]byte), []byte("\n"))
763 for i, ref := range fi.refs {
764 f(ref, string(lines[fi.linenums[i]-1]))
769 // readFile is like ioutil.ReadFile, but
770 // it goes through the virtualized build.Context.
771 // If non-nil, buf must have been reset.
772 func readFile(ctxt *build.Context, filename string, buf *bytes.Buffer) ([]byte, error) {
773 rc, err := buildutil.OpenFile(ctxt, filename)
779 buf = new(bytes.Buffer)
781 if _, err := io.Copy(buf, rc); err != nil {
784 return buf.Bytes(), nil
787 func (r *referrersPackageResult) PrintPlain(printf printfFunc) {
788 r.foreachRef(func(id *ast.Ident, text string) {
789 printf(id, "%s", text)
793 func (r *referrersPackageResult) JSON(fset *token.FileSet) []byte {
794 refs := serial.ReferrersPackage{Package: r.pkg.Path()}
795 r.foreachRef(func(id *ast.Ident, text string) {
796 refs.Refs = append(refs.Refs, serial.Ref{
797 Pos: fset.Position(id.NamePos).String(),