1 // Package unused contains code for finding unused code.
2 package unused
3 4 import (
5 "fmt"
6 "go/ast"
7 "go/token"
8 "go/types"
9 "io"
10 "reflect"
11 "strings"
12 13 "honnef.co/go/tools/analysis/facts/directives"
14 "honnef.co/go/tools/analysis/facts/generated"
15 "honnef.co/go/tools/analysis/lint"
16 "honnef.co/go/tools/analysis/report"
17 "honnef.co/go/tools/go/ast/astutil"
18 "honnef.co/go/tools/go/types/typeutil"
19 20 "golang.org/x/tools/go/analysis"
21 "golang.org/x/tools/go/types/objectpath"
22 )
23 24 // OPT(dh): don't track local variables that can't have any interesting outgoing edges. For example, using a local
25 // variable of type int is meaningless; we don't care if `int` is used or not.
26 //
27 // Note that we do have to track variables with for example array types, because the array type could have involved a
28 // named constant.
29 //
30 // We probably have different culling needs depending on the mode of operation, too. If we analyze multiple packages in
31 // one graph (unused's "whole program" mode), we could remove further useless edges (e.g. into nodes that themselves
32 // have no outgoing edges and aren't meaningful objects on their own) after having analyzed a package, to keep the
33 // in-memory representation small on average. If we only analyze a single package, that step would just waste cycles, as
34 // we're about to throw the entire graph away, anyway.
35 36 // TODO(dh): currently, types use methods that implement interfaces. However, this makes a method used even if the
37 // relevant interface is never used. What if instead interfaces used those methods? Right now we cannot do that, because
38 // methods use their receivers, so using a method uses the type. But do we need that edge? Is there a way to refer to a
39 // method without explicitly mentioning the type somewhere? If not, the edge from method to receiver is superfluous.
40 41 // XXX vet all code for proper use of core types
42 43 // TODO(dh): we cannot observe function calls in assembly files.
44 45 /*
46 47 This overview is true when using the default options. Different options may change individual behaviors.
48 49 - packages use:
50 - (1.1) exported named types
51 - (1.2) exported functions (but not methods!)
52 - (1.3) exported variables
53 - (1.4) exported constants
54 - (1.5) init functions
55 - (1.6) functions exported to cgo
56 - (1.7) the main function iff in the main package
57 - (1.8) symbols linked via go:linkname
58 - (1.9) objects in generated files
59 60 - named types use:
61 - (2.1) exported methods
62 - (2.2) the type they're based on
63 - (2.5) all their type parameters. Unused type parameters are probably useless, but they're a brand new feature and we
64 don't want to introduce false positives because we couldn't anticipate some novel use-case.
65 - (2.6) all their type arguments
66 67 - functions use:
68 - (4.1) all their arguments, return parameters and receivers
69 - (4.2) anonymous functions defined beneath them
70 - (4.3) closures and bound methods.
71 this implements a simplified model where a function is used merely by being referenced, even if it is never called.
72 that way we don't have to keep track of closures escaping functions.
73 - (4.4) functions they return. we assume that someone else will call the returned function
74 - (4.5) functions/interface methods they call
75 - (4.6) types they instantiate or convert to
76 - (4.7) fields they access
77 - (4.9) package-level variables they assign to iff in tests (sinks for benchmarks)
78 - (4.10) all their type parameters. See 2.5 for reasoning.
79 - (4.11) local variables
80 - Note that the majority of this is handled implicitly by seeing idents be used. In particular, unlike the old
81 IR-based implementation, the AST-based one doesn't care about closures, bound methods or anonymous functions.
82 They're all just additional nodes in the AST.
83 84 - conversions use:
85 - (5.1) when converting between two equivalent structs, the fields in
86 either struct use each other. the fields are relevant for the
87 conversion, but only if the fields are also accessed outside the
88 conversion.
89 - (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
90 91 - structs use:
92 - (6.1) fields of type NoCopy sentinel
93 - (6.2) exported fields
94 - (6.3) embedded fields that help implement interfaces (either fully implements it, or contributes required methods) (recursively)
95 - (6.4) embedded fields that have exported methods (recursively)
96 - (6.5) embedded structs that have exported fields (recursively)
97 - (6.6) all fields if they have a structs.HostLayout field
98 99 - (7.1) field accesses use fields
100 - (7.2) fields use their types
101 102 - (8.0) How we handle interfaces:
103 - (8.1) We do not technically care about interfaces that only consist of
104 exported methods. Exported methods on concrete types are always
105 marked as used.
106 - (8.2) Any concrete type implements all known interfaces. Even if it isn't
107 assigned to any interfaces in our code, the user may receive a value
108 of the type and expect to pass it back to us through an interface.
109 110 Concrete types use their methods that implement interfaces. If the
111 type is used, it uses those methods. Otherwise, it doesn't. This
112 way, types aren't incorrectly marked reachable through the edge
113 from method to type.
114 115 - (8.3) All interface methods are marked as used, even if they never get
116 called. This is to accommodate sum types (unexported interface
117 method that must exist but never gets called.)
118 119 - (8.4) All embedded interfaces are marked as used. This is an
120 extension of 8.3, but we have to explicitly track embedded
121 interfaces because in a chain C->B->A, B wouldn't be marked as
122 used by 8.3 just because it contributes A's methods to C.
123 124 - Inherent uses:
125 - (9.2) variables use their types
126 - (9.3) types use their underlying and element types
127 - (9.4) conversions use the type they convert to
128 - (9.7) variable _reads_ use variables, writes do not, except in tests
129 - (9.8) runtime functions that may be called from user code via the compiler
130 - (9.9) objects named the blank identifier are used. They cannot be referred to and are usually used explicitly to
131 use something that would otherwise be unused.
132 - The majority of idents get marked as read by virtue of being in the AST.
133 134 - const groups:
135 - (10.1) if one constant out of a block of constants is used, mark all
136 of them used. a lot of the time, unused constants exist for the sake
137 of completeness. See also
138 https://github.com/dominikh/go-tools/issues/365
139 140 Do not, however, include constants named _ in constant groups.
141 142 143 - (11.1) anonymous struct types use all their fields. we cannot
144 deduplicate struct types, as that leads to order-dependent
145 reports. we can't not deduplicate struct types while still
146 tracking fields, because then each instance of the unnamed type in
147 the data flow chain will get its own fields, causing false
148 positives. Thus, we only accurately track fields of named struct
149 types, and assume that unnamed struct types use all their fields.
150 151 - type parameters use:
152 - (12.1) their constraint type
153 154 */
155 156 var Debug io.Writer
157 158 func assert(b bool) {
159 if !b {
160 panic("failed assertion")
161 }
162 }
163 164 // TODO(dh): should we return a map instead of two slices?
165 type Result struct {
166 Used []Object
167 Unused []Object
168 Quiet []Object
169 }
170 171 var Analyzer = &lint.Analyzer{
172 Doc: &lint.RawDocumentation{
173 Title: "Unused code",
174 },
175 Analyzer: &analysis.Analyzer{
176 Name: "U1000",
177 Doc: "Unused code",
178 Run: run,
179 Requires: []*analysis.Analyzer{generated.Analyzer, directives.Analyzer},
180 ResultType: reflect.TypeOf(Result{}),
181 },
182 }
183 184 func newGraph(
185 fset *token.FileSet,
186 files []*ast.File,
187 pkg *types.Package,
188 info *types.Info,
189 directives []lint.Directive,
190 generated map[string]generated.Generator,
191 opts Options,
192 ) *graph {
193 g := graph{
194 pkg: pkg,
195 info: info,
196 files: files,
197 directives: directives,
198 generated: generated,
199 fset: fset,
200 nodes: []Node{{}},
201 edges: map[edge]struct{}{},
202 objects: map[types.Object]NodeID{},
203 opts: opts,
204 }
205 206 return &g
207 }
208 209 func run(pass *analysis.Pass) (interface{}, error) {
210 g := newGraph(
211 pass.Fset,
212 pass.Files,
213 pass.Pkg,
214 pass.TypesInfo,
215 pass.ResultOf[directives.Analyzer].([]lint.Directive),
216 pass.ResultOf[generated.Analyzer].(map[string]generated.Generator),
217 DefaultOptions,
218 )
219 g.entry()
220 221 sg := &SerializedGraph{
222 nodes: g.nodes,
223 }
224 225 if Debug != nil {
226 Debug.Write([]byte(sg.Dot()))
227 }
228 229 return sg.Results(), nil
230 }
231 232 type Options struct {
233 FieldWritesAreUses bool
234 PostStatementsAreReads bool
235 ExportedIsUsed bool
236 ExportedFieldsAreUsed bool
237 ParametersAreUsed bool
238 LocalVariablesAreUsed bool
239 GeneratedIsUsed bool
240 }
241 242 var DefaultOptions = Options{
243 FieldWritesAreUses: true,
244 PostStatementsAreReads: false,
245 ExportedIsUsed: true,
246 ExportedFieldsAreUsed: true,
247 ParametersAreUsed: true,
248 LocalVariablesAreUsed: true,
249 GeneratedIsUsed: true,
250 }
251 252 type edgeKind uint8
253 254 const (
255 edgeKindUse = iota + 1
256 edgeKindOwn
257 )
258 259 type edge struct {
260 from, to NodeID
261 kind edgeKind
262 }
263 264 type graph struct {
265 pkg *types.Package
266 info *types.Info
267 files []*ast.File
268 fset *token.FileSet
269 directives []lint.Directive
270 generated map[string]generated.Generator
271 272 opts Options
273 274 // edges tracks all edges between nodes (uses and owns relationships). This data is also present in the Node struct,
275 // but there it can't be accessed in O(1) time. edges is used to deduplicate edges.
276 edges map[edge]struct{}
277 nodes []Node
278 objects map[types.Object]NodeID
279 280 // package-level named types
281 namedTypes []*types.TypeName
282 interfaceTypes []*types.Interface
283 }
284 285 type nodeState uint8
286 287 //gcassert:inline
288 func (ns nodeState) seen() bool { return ns&nodeStateSeen != 0 }
289 290 //gcassert:inline
291 func (ns nodeState) quiet() bool { return ns&nodeStateQuiet != 0 }
292 293 const (
294 nodeStateSeen nodeState = 1 << iota
295 nodeStateQuiet
296 )
297 298 // OPT(dh): 32 bits would be plenty, but the Node struct would end up with padding, anyway.
299 type NodeID uint64
300 301 type Node struct {
302 id NodeID
303 obj Object
304 305 // using slices instead of maps here helps make merging of graphs simpler and more efficient, because we can rewrite
306 // IDs in place instead of having to build new maps.
307 uses []NodeID
308 owns []NodeID
309 }
310 311 func (g *graph) objectToObject(obj types.Object) Object {
312 // OPT(dh): I think we only need object paths in whole-program mode. In other cases, position-based node merging
313 // should suffice.
314 315 // objectpath.For is an expensive function and we'd like to avoid calling it when we know that there cannot be a
316 // path, or when the path doesn't matter.
317 //
318 // Unexported global objects don't have paths. Local variables may have paths when they're parameters or return
319 // parameters, but we do not care about those, because they're not API that other packages can refer to directly. We
320 // do have to track fields, because they may be part of an anonymous type declared in a parameter or return
321 // parameter. We cannot categorically ignore unexported identifiers, because an exported field might have been
322 // embedded via an unexported field, which will be referred to.
323 324 var relevant bool
325 switch obj := obj.(type) {
326 case *types.Var:
327 // If it's a field or it's an exported top-level variable, we care about it. Otherwise, we don't.
328 // OPT(dh): same question as posed in the default branch
329 relevant = obj.IsField() || token.IsExported(obj.Name())
330 default:
331 // OPT(dh): See if it's worth checking that the object is actually in package scope, and doesn't just have a
332 // capitalized name.
333 relevant = token.IsExported(obj.Name())
334 }
335 336 var path ObjectPath
337 if relevant {
338 objPath, _ := objectpath.For(obj)
339 if objPath != "" {
340 path = ObjectPath{
341 PkgPath: obj.Pkg().Path(),
342 ObjPath: objPath,
343 }
344 }
345 }
346 name := obj.Name()
347 if sig, ok := obj.Type().(*types.Signature); ok && sig.Recv() != nil {
348 switch types.Unalias(sig.Recv().Type()).(type) {
349 case *types.Named, *types.Pointer:
350 typ := types.TypeString(sig.Recv().Type(), func(*types.Package) string { return "" })
351 if len(typ) > 0 && typ[0] == '*' {
352 name = fmt.Sprintf("(%s).%s", typ, obj.Name())
353 } else if len(typ) > 0 {
354 name = fmt.Sprintf("%s.%s", typ, obj.Name())
355 }
356 }
357 }
358 return Object{
359 Name: name,
360 ShortName: obj.Name(),
361 Kind: typString(obj),
362 Path: path,
363 Position: g.fset.PositionFor(obj.Pos(), false),
364 DisplayPosition: report.DisplayPosition(g.fset, obj.Pos()),
365 }
366 }
367 368 func typString(obj types.Object) string {
369 switch obj := obj.(type) {
370 case *types.Func:
371 return "func"
372 case *types.Var:
373 if obj.IsField() {
374 return "field"
375 }
376 return "var"
377 case *types.Const:
378 return "const"
379 case *types.TypeName:
380 if _, ok := obj.Type().(*types.TypeParam); ok {
381 return "type param"
382 } else {
383 return "type"
384 }
385 default:
386 return "identifier"
387 }
388 }
389 390 func (g *graph) newNode(obj types.Object) NodeID {
391 id := NodeID(len(g.nodes))
392 n := Node{
393 id: id,
394 obj: g.objectToObject(obj),
395 }
396 g.nodes = append(g.nodes, n)
397 if _, ok := g.objects[obj]; ok {
398 panic(fmt.Sprintf("already had a node for %s", obj))
399 }
400 g.objects[obj] = id
401 return id
402 }
403 404 func (g *graph) node(obj types.Object) NodeID {
405 if obj == nil {
406 return 0
407 }
408 obj = origin(obj)
409 if n, ok := g.objects[obj]; ok {
410 return n
411 }
412 n := g.newNode(obj)
413 return n
414 }
415 416 func origin(obj types.Object) types.Object {
417 switch obj := obj.(type) {
418 case *types.Var:
419 return obj.Origin()
420 case *types.Func:
421 return obj.Origin()
422 default:
423 return obj
424 }
425 }
426 427 func (g *graph) addEdge(e edge) bool {
428 if _, ok := g.edges[e]; ok {
429 return false
430 }
431 g.edges[e] = struct{}{}
432 return true
433 }
434 435 func (g *graph) addOwned(owner, owned NodeID) {
436 e := edge{owner, owned, edgeKindOwn}
437 if !g.addEdge(e) {
438 return
439 }
440 n := &g.nodes[owner]
441 n.owns = append(n.owns, owned)
442 }
443 444 func (g *graph) addUse(by, used NodeID) {
445 e := edge{by, used, edgeKindUse}
446 if !g.addEdge(e) {
447 return
448 }
449 nBy := &g.nodes[by]
450 nBy.uses = append(nBy.uses, used)
451 }
452 453 func (g *graph) see(obj, owner types.Object) {
454 if obj == nil {
455 panic("saw nil object")
456 }
457 458 if g.opts.ExportedIsUsed && obj.Pkg() != g.pkg || obj.Pkg() == nil {
459 return
460 }
461 462 nObj := g.node(obj)
463 if owner != nil {
464 nOwner := g.node(owner)
465 g.addOwned(nOwner, nObj)
466 }
467 }
468 469 func isIrrelevant(obj types.Object) bool {
470 switch obj.(type) {
471 case *types.PkgName:
472 return true
473 default:
474 return false
475 }
476 }
477 478 func (g *graph) use(used, by types.Object) {
479 if g.opts.ExportedIsUsed {
480 if used.Pkg() != g.pkg || used.Pkg() == nil {
481 return
482 }
483 if by != nil && by.Pkg() != g.pkg {
484 return
485 }
486 }
487 488 if isIrrelevant(used) {
489 return
490 }
491 492 nUsed := g.node(used)
493 nBy := g.node(by)
494 g.addUse(nBy, nUsed)
495 }
496 497 func (g *graph) entry() {
498 for _, f := range g.files {
499 for _, cg := range f.Comments {
500 for _, c := range cg.List {
501 if strings.HasPrefix(c.Text, "//go:linkname ") {
502 // FIXME(dh): we're looking at all comments. The
503 // compiler only looks at comments in the
504 // left-most column. The intention probably is to
505 // only look at top-level comments.
506 507 // (1.8) packages use symbols linked via go:linkname
508 fields := strings.Fields(c.Text)
509 if len(fields) == 3 {
510 obj := g.pkg.Scope().Lookup(fields[1])
511 if obj == nil {
512 continue
513 }
514 g.use(obj, nil)
515 }
516 }
517 }
518 }
519 }
520 521 for _, f := range g.files {
522 for _, decl := range f.Decls {
523 g.decl(decl, nil)
524 }
525 }
526 527 if g.opts.GeneratedIsUsed {
528 // OPT(dh): depending on the options used, we do not need to track all objects. For example, if local variables
529 // are always used, then it is enough to use their surrounding function.
530 for obj := range g.objects {
531 path := g.fset.PositionFor(obj.Pos(), false).Filename
532 if _, ok := g.generated[path]; ok {
533 g.use(obj, nil)
534 }
535 }
536 }
537 538 // We use a normal map instead of a typeutil.Map because we deduplicate
539 // these on a best effort basis, as an optimization.
540 allInterfaces := make(map[*types.Interface]struct{})
541 for _, typ := range g.interfaceTypes {
542 allInterfaces[typ] = struct{}{}
543 }
544 for _, ins := range g.info.Instances {
545 if typ, ok := ins.Type.(*types.Named); ok && typ.Obj().Pkg() == g.pkg {
546 if iface, ok := typ.Underlying().(*types.Interface); ok {
547 allInterfaces[iface] = struct{}{}
548 }
549 }
550 }
551 processMethodSet := func(named *types.TypeName, ms *types.MethodSet) {
552 if g.opts.ExportedIsUsed {
553 for i := 0; i < ms.Len(); i++ {
554 m := ms.At(i)
555 if token.IsExported(m.Obj().Name()) {
556 // (2.1) named types use exported methods
557 // (6.4) structs use embedded fields that have exported methods
558 //
559 // By reading the selection, we read all embedded fields that are part of the path
560 g.readSelection(m, named)
561 }
562 }
563 }
564 565 if _, ok := named.Type().Underlying().(*types.Interface); !ok {
566 // (8.0) handle interfaces
567 //
568 // We don't care about interfaces implementing interfaces; all their methods are already used, anyway
569 for iface := range allInterfaces {
570 if sels, ok := implements(named.Type(), iface, ms); ok {
571 for _, sel := range sels {
572 // (8.2) any concrete type implements all known interfaces
573 // (6.3) structs use embedded fields that help implement interfaces
574 g.readSelection(sel, named)
575 }
576 }
577 }
578 }
579 }
580 581 for _, named := range g.namedTypes {
582 // OPT(dh): do we already have the method set available?
583 processMethodSet(named, types.NewMethodSet(named.Type()))
584 processMethodSet(named, types.NewMethodSet(types.NewPointer(named.Type())))
585 586 }
587 588 type ignoredKey struct {
589 file string
590 line int
591 }
592 ignores := map[ignoredKey]struct{}{}
593 for _, dir := range g.directives {
594 if dir.Command != "ignore" && dir.Command != "file-ignore" {
595 continue
596 }
597 if len(dir.Arguments) == 0 {
598 continue
599 }
600 for _, check := range strings.Split(dir.Arguments[0], ",") {
601 if check == "U1000" {
602 pos := g.fset.PositionFor(dir.Node.Pos(), false)
603 var key ignoredKey
604 switch dir.Command {
605 case "ignore":
606 key = ignoredKey{
607 pos.Filename,
608 pos.Line,
609 }
610 case "file-ignore":
611 key = ignoredKey{
612 pos.Filename,
613 -1,
614 }
615 }
616 617 ignores[key] = struct{}{}
618 break
619 }
620 }
621 }
622 623 if len(ignores) > 0 {
624 // all objects annotated with a //lint:ignore U1000 are considered used
625 for obj := range g.objects {
626 pos := g.fset.PositionFor(obj.Pos(), false)
627 key1 := ignoredKey{
628 pos.Filename,
629 pos.Line,
630 }
631 key2 := ignoredKey{
632 pos.Filename,
633 -1,
634 }
635 _, ok := ignores[key1]
636 if !ok {
637 _, ok = ignores[key2]
638 }
639 if ok {
640 g.use(obj, nil)
641 642 // use methods and fields of ignored types
643 if obj, ok := obj.(*types.TypeName); ok {
644 if obj.IsAlias() {
645 if typ, ok := types.Unalias(obj.Type()).(*types.Named); ok && (g.opts.ExportedIsUsed && typ.Obj().Pkg() != obj.Pkg() || typ.Obj().Pkg() == nil) {
646 // This is an alias of a named type in another package.
647 // Don't walk its fields or methods; we don't have to.
648 //
649 // For aliases to types in the same package, we do want to ignore the fields and methods,
650 // because ignoring the alias should ignore the aliased type.
651 continue
652 }
653 }
654 if typ, ok := types.Unalias(obj.Type()).(*types.Named); ok {
655 for i := 0; i < typ.NumMethods(); i++ {
656 g.use(typ.Method(i), nil)
657 }
658 }
659 if typ, ok := obj.Type().Underlying().(*types.Struct); ok {
660 for i := 0; i < typ.NumFields(); i++ {
661 g.use(typ.Field(i), nil)
662 }
663 }
664 }
665 }
666 }
667 }
668 }
669 670 func isOfType[T any](x any) bool {
671 _, ok := x.(T)
672 return ok
673 }
674 675 func (g *graph) read(node ast.Node, by types.Object) {
676 if node == nil {
677 return
678 }
679 680 switch node := node.(type) {
681 case *ast.Ident:
682 // Among many other things, this handles
683 // (7.1) field accesses use fields
684 685 obj := g.info.ObjectOf(node)
686 g.use(obj, by)
687 688 case *ast.BasicLit:
689 // Nothing to do
690 691 case *ast.SliceExpr:
692 g.read(node.X, by)
693 g.read(node.Low, by)
694 g.read(node.High, by)
695 g.read(node.Max, by)
696 697 case *ast.UnaryExpr:
698 g.read(node.X, by)
699 700 case *ast.ParenExpr:
701 g.read(node.X, by)
702 703 case *ast.ArrayType:
704 g.read(node.Len, by)
705 g.read(node.Elt, by)
706 707 case *ast.SelectorExpr:
708 g.readSelectorExpr(node, by)
709 710 case *ast.IndexExpr:
711 // Among many other things, this handles
712 // (2.6) named types use all their type arguments
713 g.read(node.X, by)
714 g.read(node.Index, by)
715 716 case *ast.IndexListExpr:
717 // Among many other things, this handles
718 // (2.6) named types use all their type arguments
719 g.read(node.X, by)
720 for _, index := range node.Indices {
721 g.read(index, by)
722 }
723 724 case *ast.BinaryExpr:
725 g.read(node.X, by)
726 g.read(node.Y, by)
727 728 case *ast.CompositeLit:
729 g.read(node.Type, by)
730 // We get the type of the node itself, not of node.Type, to handle nested composite literals of the kind
731 // T{{...}}
732 typ, isStruct := typeutil.CoreType(g.info.TypeOf(node)).(*types.Struct)
733 734 if isStruct {
735 unkeyed := len(node.Elts) != 0 && !isOfType[*ast.KeyValueExpr](node.Elts[0])
736 if g.opts.FieldWritesAreUses && unkeyed {
737 // Untagged struct literal that specifies all fields. We have to manually use the fields in the type,
738 // because the unkeyd literal doesn't contain any nodes referring to the fields.
739 for i := 0; i < typ.NumFields(); i++ {
740 g.use(typ.Field(i), by)
741 }
742 }
743 if g.opts.FieldWritesAreUses || unkeyed {
744 for _, elt := range node.Elts {
745 g.read(elt, by)
746 }
747 } else {
748 for _, elt := range node.Elts {
749 kv := elt.(*ast.KeyValueExpr)
750 g.write(kv.Key, by)
751 g.read(kv.Value, by)
752 }
753 }
754 } else {
755 for _, elt := range node.Elts {
756 g.read(elt, by)
757 }
758 }
759 760 case *ast.KeyValueExpr:
761 g.read(node.Key, by)
762 g.read(node.Value, by)
763 764 case *ast.StarExpr:
765 g.read(node.X, by)
766 767 case *ast.MapType:
768 g.read(node.Key, by)
769 g.read(node.Value, by)
770 771 case *ast.FuncLit:
772 g.read(node.Type, by)
773 774 // See graph.decl's handling of ast.FuncDecl for why this bit of code is necessary.
775 fn := g.info.TypeOf(node).(*types.Signature)
776 for params, i := fn.Params(), 0; i < params.Len(); i++ {
777 g.see(params.At(i), by)
778 if params.At(i).Name() == "" {
779 g.use(params.At(i), by)
780 }
781 }
782 783 g.block(node.Body, by)
784 785 case *ast.FuncType:
786 m := map[*types.Var]struct{}{}
787 if !g.opts.ParametersAreUsed {
788 m = map[*types.Var]struct{}{}
789 // seeScope marks all local variables in the scope as used, but we don't want to unconditionally use
790 // parameters, as this is controlled by Options.ParametersAreUsed. Pass seeScope a list of variables it
791 // should skip.
792 for _, f := range node.Params.List {
793 for _, name := range f.Names {
794 m[g.info.ObjectOf(name).(*types.Var)] = struct{}{}
795 }
796 }
797 }
798 g.seeScope(node, by, m)
799 800 // (4.1) functions use all their arguments, return parameters and receivers
801 // (12.1) type parameters use their constraint type
802 g.read(node.TypeParams, by)
803 if g.opts.ParametersAreUsed {
804 g.read(node.Params, by)
805 }
806 g.read(node.Results, by)
807 808 case *ast.FieldList:
809 if node == nil {
810 return
811 }
812 813 // This branch is only hit for field lists enclosed by parentheses or square brackets, i.e. parameters. Fields
814 // (for structs) and method lists (for interfaces) are handled elsewhere.
815 816 for _, field := range node.List {
817 if len(field.Names) == 0 {
818 g.read(field.Type, by)
819 } else {
820 for _, name := range field.Names {
821 // OPT(dh): instead of by -> name -> type, we could just emit by -> type. We don't care about the
822 // (un)usedness of parameters of any kind.
823 obj := g.info.ObjectOf(name)
824 g.use(obj, by)
825 g.read(field.Type, obj)
826 }
827 }
828 }
829 830 case *ast.ChanType:
831 g.read(node.Value, by)
832 833 case *ast.StructType:
834 // This is only used for anonymous struct types, not named ones.
835 836 for _, field := range node.Fields.List {
837 if len(field.Names) == 0 {
838 // embedded field
839 840 f := g.embeddedField(field.Type, by)
841 g.use(f, by)
842 } else {
843 for _, name := range field.Names {
844 // (11.1) anonymous struct types use all their fields
845 // OPT(dh): instead of by -> name -> type, we could just emit by -> type. If the type is used, then the fields are used.
846 obj := g.info.ObjectOf(name)
847 g.see(obj, by)
848 g.use(obj, by)
849 g.read(field.Type, g.info.ObjectOf(name))
850 }
851 }
852 }
853 854 case *ast.TypeAssertExpr:
855 g.read(node.X, by)
856 g.read(node.Type, by)
857 858 case *ast.InterfaceType:
859 if len(node.Methods.List) != 0 {
860 g.interfaceTypes = append(g.interfaceTypes, g.info.TypeOf(node).(*types.Interface))
861 }
862 for _, meth := range node.Methods.List {
863 switch len(meth.Names) {
864 case 0:
865 // Embedded type or type union
866 // (8.4) all embedded interfaces are marked as used
867 // (this also covers type sets)
868 869 g.read(meth.Type, by)
870 case 1:
871 // Method
872 // (8.3) all interface methods are marked as used
873 obj := g.info.ObjectOf(meth.Names[0])
874 g.see(obj, by)
875 g.use(obj, by)
876 g.read(meth.Type, obj)
877 default:
878 panic(fmt.Sprintf("unexpected number of names: %d", len(meth.Names)))
879 }
880 }
881 882 case *ast.Ellipsis:
883 g.read(node.Elt, by)
884 885 case *ast.CallExpr:
886 g.read(node.Fun, by)
887 for _, arg := range node.Args {
888 g.read(arg, by)
889 }
890 891 // Handle conversions
892 conv := node
893 if len(conv.Args) != 1 || conv.Ellipsis.IsValid() {
894 return
895 }
896 897 dst := g.info.TypeOf(conv.Fun)
898 src := g.info.TypeOf(conv.Args[0])
899 900 // XXX use DereferenceR instead
901 // XXX guard against infinite recursion in DereferenceR
902 tSrc := typeutil.CoreType(typeutil.Dereference(src))
903 tDst := typeutil.CoreType(typeutil.Dereference(dst))
904 stSrc, okSrc := tSrc.(*types.Struct)
905 stDst, okDst := tDst.(*types.Struct)
906 if okDst && okSrc {
907 // Converting between two structs. The fields are
908 // relevant for the conversion, but only if the
909 // fields are also used outside of the conversion.
910 // Mark fields as used by each other.
911 912 assert(stDst.NumFields() == stSrc.NumFields())
913 for i := 0; i < stDst.NumFields(); i++ {
914 // (5.1) when converting between two equivalent structs, the fields in
915 // either struct use each other. the fields are relevant for the
916 // conversion, but only if the fields are also accessed outside the
917 // conversion.
918 g.use(stDst.Field(i), stSrc.Field(i))
919 g.use(stSrc.Field(i), stDst.Field(i))
920 }
921 } else if okSrc && tDst == types.Typ[types.UnsafePointer] {
922 // (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
923 g.useAllFieldsRecursively(stSrc, by)
924 } else if okDst && tSrc == types.Typ[types.UnsafePointer] {
925 // (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
926 g.useAllFieldsRecursively(stDst, by)
927 }
928 929 default:
930 lint.ExhaustiveTypeSwitch(node)
931 }
932 }
933 934 func (g *graph) useAllFieldsRecursively(typ types.Type, by types.Object) {
935 switch typ := typ.Underlying().(type) {
936 case *types.Struct:
937 for i := 0; i < typ.NumFields(); i++ {
938 field := typ.Field(i)
939 g.use(field, by)
940 g.useAllFieldsRecursively(field.Type(), by)
941 }
942 case *types.Array:
943 g.useAllFieldsRecursively(typ.Elem(), by)
944 default:
945 return
946 }
947 }
948 949 func (g *graph) write(node ast.Node, by types.Object) {
950 if node == nil {
951 return
952 }
953 954 switch node := node.(type) {
955 case *ast.Ident:
956 obj := g.info.ObjectOf(node)
957 if obj == nil {
958 // This can happen for `switch x := v.(type)`, where that x doesn't have an object
959 return
960 }
961 962 // (4.9) functions use package-level variables they assign to iff in tests (sinks for benchmarks)
963 // (9.7) variable _reads_ use variables, writes do not, except in tests
964 path := g.fset.File(obj.Pos()).Name()
965 if strings.HasSuffix(path, "_test.go") {
966 if isGlobal(obj) {
967 g.use(obj, by)
968 }
969 }
970 971 case *ast.IndexExpr:
972 g.read(node.X, by)
973 g.read(node.Index, by)
974 975 case *ast.SelectorExpr:
976 if g.opts.FieldWritesAreUses {
977 // Writing to a field constitutes a use. See https://staticcheck.dev/issues/288 for some discussion on that.
978 //
979 // This code can also get triggered by qualified package variables, in which case it doesn't matter what we do,
980 // because the object is in another package.
981 //
982 // FIXME(dh): ^ isn't true if we track usedness of exported identifiers
983 g.readSelectorExpr(node, by)
984 } else {
985 g.read(node.X, by)
986 g.write(node.Sel, by)
987 }
988 989 case *ast.StarExpr:
990 g.read(node.X, by)
991 992 case *ast.ParenExpr:
993 g.write(node.X, by)
994 995 default:
996 lint.ExhaustiveTypeSwitch(node)
997 }
998 }
999 1000 // readSelectorExpr reads all elements of a selector expression, including implicit fields.
1001 func (g *graph) readSelectorExpr(sel *ast.SelectorExpr, by types.Object) {
1002 // cover AST-based accesses
1003 g.read(sel.X, by)
1004 g.read(sel.Sel, by)
1005 1006 tsel, ok := g.info.Selections[sel]
1007 if !ok {
1008 return
1009 }
1010 g.readSelection(tsel, by)
1011 }
1012 1013 func (g *graph) readSelection(sel *types.Selection, by types.Object) {
1014 indices := sel.Index()
1015 base := sel.Recv()
1016 for _, idx := range indices[:len(indices)-1] {
1017 // XXX do we need core types here?
1018 field := typeutil.Dereference(base.Underlying()).Underlying().(*types.Struct).Field(idx)
1019 g.use(field, by)
1020 base = field.Type()
1021 }
1022 1023 g.use(sel.Obj(), by)
1024 }
1025 1026 func (g *graph) block(block *ast.BlockStmt, by types.Object) {
1027 if block == nil {
1028 return
1029 }
1030 1031 g.seeScope(block, by, nil)
1032 for _, stmt := range block.List {
1033 g.stmt(stmt, by)
1034 }
1035 }
1036 1037 func isGlobal(obj types.Object) bool {
1038 return obj.Parent() == obj.Pkg().Scope()
1039 }
1040 1041 func (g *graph) decl(decl ast.Decl, by types.Object) {
1042 switch decl := decl.(type) {
1043 case *ast.GenDecl:
1044 switch decl.Tok {
1045 case token.IMPORT:
1046 // Nothing to do
1047 1048 case token.CONST:
1049 for _, spec := range decl.Specs {
1050 vspec := spec.(*ast.ValueSpec)
1051 assert(len(vspec.Values) == 0 || len(vspec.Values) == len(vspec.Names))
1052 for i, name := range vspec.Names {
1053 obj := g.info.ObjectOf(name)
1054 g.see(obj, by)
1055 g.read(vspec.Type, obj)
1056 1057 if len(vspec.Values) != 0 {
1058 g.read(vspec.Values[i], obj)
1059 }
1060 1061 if name.Name == "_" {
1062 // (9.9) objects named the blank identifier are used
1063 g.use(obj, by)
1064 } else if token.IsExported(name.Name) && isGlobal(obj) && g.opts.ExportedIsUsed {
1065 g.use(obj, nil)
1066 }
1067 }
1068 }
1069 1070 groups := astutil.GroupSpecs(g.fset, decl.Specs)
1071 for _, group := range groups {
1072 // (10.1) if one constant out of a block of constants is used, mark all of them used
1073 //
1074 // We encode this as a ring. If we have a constant group 'const ( a; b; c )', then we'll produce the
1075 // following graph: a -> b -> c -> a.
1076 1077 var first, prev, last types.Object
1078 for _, spec := range group {
1079 for _, name := range spec.(*ast.ValueSpec).Names {
1080 if name.Name == "_" {
1081 // Having a blank constant in a group doesn't mark the whole group as used
1082 continue
1083 }
1084 1085 obj := g.info.ObjectOf(name)
1086 if first == nil {
1087 first = obj
1088 } else {
1089 g.use(obj, prev)
1090 }
1091 prev = obj
1092 last = obj
1093 }
1094 }
1095 if first != nil && first != last {
1096 g.use(first, last)
1097 }
1098 }
1099 1100 case token.TYPE:
1101 for _, spec := range decl.Specs {
1102 tspec := spec.(*ast.TypeSpec)
1103 obj := g.info.ObjectOf(tspec.Name).(*types.TypeName)
1104 g.see(obj, by)
1105 g.seeScope(tspec, obj, nil)
1106 if !tspec.Assign.IsValid() {
1107 g.namedTypes = append(g.namedTypes, obj)
1108 }
1109 if token.IsExported(tspec.Name.Name) && isGlobal(obj) && g.opts.ExportedIsUsed {
1110 // (1.1) packages use exported named types
1111 g.use(g.info.ObjectOf(tspec.Name), nil)
1112 }
1113 1114 // (2.5) named types use all their type parameters
1115 g.read(tspec.TypeParams, obj)
1116 1117 g.namedType(obj, tspec.Type)
1118 1119 if tspec.Name.Name == "_" {
1120 // (9.9) objects named the blank identifier are used
1121 g.use(obj, by)
1122 }
1123 }
1124 1125 case token.VAR:
1126 // We cannot rely on types.Initializer for package-level variables because
1127 // - initializers are only tracked for variables that are actually initialized
1128 // - we want to see the AST of the type, if specified, not just the rhs
1129 1130 for _, spec := range decl.Specs {
1131 vspec := spec.(*ast.ValueSpec)
1132 for i, name := range vspec.Names {
1133 obj := g.info.ObjectOf(name)
1134 g.see(obj, by)
1135 // variables and constants use their types
1136 g.read(vspec.Type, obj)
1137 1138 if len(vspec.Names) == len(vspec.Values) {
1139 // One value per variable
1140 g.read(vspec.Values[i], obj)
1141 } else if len(vspec.Values) != 0 {
1142 // Multiple variables initialized with a single rhs
1143 // assert(len(vspec.Values) == 1)
1144 if len(vspec.Values) != 1 {
1145 panic(g.fset.PositionFor(vspec.Pos(), false))
1146 }
1147 g.read(vspec.Values[0], obj)
1148 }
1149 1150 if token.IsExported(name.Name) && isGlobal(obj) && g.opts.ExportedIsUsed {
1151 // (1.3) packages use exported variables
1152 g.use(obj, nil)
1153 }
1154 1155 if name.Name == "_" {
1156 // (9.9) objects named the blank identifier are used
1157 g.use(obj, by)
1158 }
1159 }
1160 }
1161 1162 default:
1163 panic(fmt.Sprintf("unexpected token %s", decl.Tok))
1164 }
1165 1166 case *ast.FuncDecl:
1167 obj := g.info.ObjectOf(decl.Name).(*types.Func).Origin()
1168 g.see(obj, nil)
1169 1170 if token.IsExported(decl.Name.Name) && g.opts.ExportedIsUsed {
1171 if decl.Recv == nil {
1172 // (1.2) packages use exported functions
1173 g.use(obj, nil)
1174 }
1175 } else if decl.Name.Name == "init" {
1176 // (1.5) packages use init functions
1177 g.use(obj, nil)
1178 } else if decl.Name.Name == "main" && g.pkg.Name() == "main" {
1179 // (1.7) packages use the main function iff in the main package
1180 g.use(obj, nil)
1181 } else if g.pkg.Path() == "runtime" && runtimeFuncs[decl.Name.Name] {
1182 // (9.8) runtime functions that may be called from user code via the compiler
1183 g.use(obj, nil)
1184 } else if g.pkg.Path() == "runtime/coverage" && runtimeCoverageFuncs[decl.Name.Name] {
1185 // (9.8) runtime functions that may be called from user code via the compiler
1186 g.use(obj, nil)
1187 }
1188 1189 // (4.1) functions use their receivers
1190 g.read(decl.Recv, obj)
1191 g.read(decl.Type, obj)
1192 g.block(decl.Body, obj)
1193 1194 // g.read(decl.Type) will ultimately call g.seeScopes and see parameters that way. But because it relies
1195 // entirely on the AST, it cannot resolve unnamed parameters to types.Object. For that reason we explicitly
1196 // handle arguments here, as well as for FuncLits elsewhere.
1197 //
1198 // g.seeScopes can't get to the types.Signature for this function because there is no mapping from ast.FuncType to
1199 // types.Signature, only from ast.Ident to types.Signature.
1200 //
1201 // This code is only really relevant when Options.ParametersAreUsed is false. Otherwise, all parameters are
1202 // considered used, and if we never see a parameter then no harm done (we still see its type separately).
1203 fn := g.info.TypeOf(decl.Name).(*types.Signature)
1204 for params, i := fn.Params(), 0; i < params.Len(); i++ {
1205 g.see(params.At(i), obj)
1206 if params.At(i).Name() == "" {
1207 g.use(params.At(i), obj)
1208 }
1209 }
1210 1211 if decl.Name.Name == "_" {
1212 // (9.9) objects named the blank identifier are used
1213 g.use(obj, nil)
1214 }
1215 1216 if decl.Doc != nil {
1217 for _, cmt := range decl.Doc.List {
1218 if strings.HasPrefix(cmt.Text, "//go:cgo_export_") {
1219 // (1.6) packages use functions exported to cgo
1220 g.use(obj, nil)
1221 }
1222 }
1223 }
1224 1225 default:
1226 // We do not cover BadDecl, but we shouldn't ever see one of those
1227 lint.ExhaustiveTypeSwitch(decl)
1228 }
1229 }
1230 1231 // seeScope sees all objects in node's scope. If Options.LocalVariablesAreUsed is true, all objects that aren't fields
1232 // are marked as used. Variables set in skipLvars will not be marked as used.
1233 func (g *graph) seeScope(node ast.Node, by types.Object, skipLvars map[*types.Var]struct{}) {
1234 // A note on functions and scopes: for a function declaration, the body's BlockStmt can't be found in
1235 // types.Info.Scopes. Instead, the FuncType can, and that scope will contain receivers, parameters, return
1236 // parameters and immediate local variables.
1237 1238 scope := g.info.Scopes[node]
1239 if scope == nil {
1240 return
1241 }
1242 for _, name := range scope.Names() {
1243 obj := scope.Lookup(name)
1244 g.see(obj, by)
1245 1246 if g.opts.LocalVariablesAreUsed {
1247 if obj, ok := obj.(*types.Var); ok && !obj.IsField() {
1248 if _, ok := skipLvars[obj]; !ok {
1249 g.use(obj, by)
1250 }
1251 }
1252 }
1253 }
1254 }
1255 1256 func (g *graph) stmt(stmt ast.Stmt, by types.Object) {
1257 if stmt == nil {
1258 return
1259 }
1260 1261 for {
1262 // We don't care about labels, so unwrap LabeledStmts. Note that a label can itself be labeled.
1263 if labeled, ok := stmt.(*ast.LabeledStmt); ok {
1264 stmt = labeled.Stmt
1265 } else {
1266 break
1267 }
1268 }
1269 1270 switch stmt := stmt.(type) {
1271 case *ast.AssignStmt:
1272 for _, lhs := range stmt.Lhs {
1273 g.write(lhs, by)
1274 }
1275 for _, rhs := range stmt.Rhs {
1276 // Note: it would be more accurate to have the rhs used by the lhs, but it ultimately doesn't matter,
1277 // because local variables always end up used, anyway.
1278 //
1279 // TODO(dh): we'll have to change that once we allow tracking the usedness of parameters
1280 g.read(rhs, by)
1281 }
1282 1283 case *ast.BlockStmt:
1284 g.block(stmt, by)
1285 1286 case *ast.BranchStmt:
1287 // Nothing to do
1288 1289 case *ast.DeclStmt:
1290 g.decl(stmt.Decl, by)
1291 1292 case *ast.DeferStmt:
1293 g.read(stmt.Call, by)
1294 1295 case *ast.ExprStmt:
1296 g.read(stmt.X, by)
1297 1298 case *ast.ForStmt:
1299 g.seeScope(stmt, by, nil)
1300 g.stmt(stmt.Init, by)
1301 g.read(stmt.Cond, by)
1302 g.stmt(stmt.Post, by)
1303 g.block(stmt.Body, by)
1304 1305 case *ast.GoStmt:
1306 g.read(stmt.Call, by)
1307 1308 case *ast.IfStmt:
1309 g.seeScope(stmt, by, nil)
1310 g.stmt(stmt.Init, by)
1311 g.read(stmt.Cond, by)
1312 g.block(stmt.Body, by)
1313 g.stmt(stmt.Else, by)
1314 1315 case *ast.IncDecStmt:
1316 if g.opts.PostStatementsAreReads {
1317 g.read(stmt.X, by)
1318 g.write(stmt.X, by)
1319 } else {
1320 // We treat post-increment as a write only. This ends up using fields, and sinks in tests, but not other
1321 // variables.
1322 g.write(stmt.X, by)
1323 }
1324 1325 case *ast.RangeStmt:
1326 g.seeScope(stmt, by, nil)
1327 1328 g.write(stmt.Key, by)
1329 g.write(stmt.Value, by)
1330 g.read(stmt.X, by)
1331 g.block(stmt.Body, by)
1332 1333 case *ast.ReturnStmt:
1334 for _, ret := range stmt.Results {
1335 g.read(ret, by)
1336 }
1337 1338 case *ast.SelectStmt:
1339 for _, clause_ := range stmt.Body.List {
1340 clause := clause_.(*ast.CommClause)
1341 g.seeScope(clause, by, nil)
1342 switch comm := clause.Comm.(type) {
1343 case *ast.SendStmt:
1344 g.read(comm.Chan, by)
1345 g.read(comm.Value, by)
1346 case *ast.ExprStmt:
1347 g.read(astutil.Unparen(comm.X).(*ast.UnaryExpr).X, by)
1348 case *ast.AssignStmt:
1349 for _, lhs := range comm.Lhs {
1350 g.write(lhs, by)
1351 }
1352 for _, rhs := range comm.Rhs {
1353 g.read(rhs, by)
1354 }
1355 case nil:
1356 default:
1357 lint.ExhaustiveTypeSwitch(comm)
1358 }
1359 for _, body := range clause.Body {
1360 g.stmt(body, by)
1361 }
1362 }
1363 1364 case *ast.SendStmt:
1365 g.read(stmt.Chan, by)
1366 g.read(stmt.Value, by)
1367 1368 case *ast.SwitchStmt:
1369 g.seeScope(stmt, by, nil)
1370 g.stmt(stmt.Init, by)
1371 g.read(stmt.Tag, by)
1372 for _, clause_ := range stmt.Body.List {
1373 clause := clause_.(*ast.CaseClause)
1374 g.seeScope(clause, by, nil)
1375 for _, expr := range clause.List {
1376 g.read(expr, by)
1377 }
1378 for _, body := range clause.Body {
1379 g.stmt(body, by)
1380 }
1381 }
1382 1383 case *ast.TypeSwitchStmt:
1384 g.seeScope(stmt, by, nil)
1385 g.stmt(stmt.Init, by)
1386 g.stmt(stmt.Assign, by)
1387 for _, clause_ := range stmt.Body.List {
1388 clause := clause_.(*ast.CaseClause)
1389 g.seeScope(clause, by, nil)
1390 for _, expr := range clause.List {
1391 g.read(expr, by)
1392 }
1393 for _, body := range clause.Body {
1394 g.stmt(body, by)
1395 }
1396 }
1397 1398 case *ast.EmptyStmt:
1399 // Nothing to do
1400 1401 default:
1402 lint.ExhaustiveTypeSwitch(stmt)
1403 }
1404 }
1405 1406 // embeddedField sees the field declared by the embedded field node, and marks the type as used by the field.
1407 //
1408 // Embedded fields are special in two ways: they don't have names, so we don't have immediate access to an ast.Ident to
1409 // resolve to the field's types.Var and need to instead walk the AST, and we cannot use g.read on the type because
1410 // eventually we do get to an ast.Ident, and ObjectOf resolves embedded fields to the field they declare, not the type.
1411 // That's why we have code specially for handling embedded fields.
1412 func (g *graph) embeddedField(node ast.Node, by types.Object) *types.Var {
1413 // We need to traverse the tree to find the ast.Ident, but all the nodes we traverse should be used by the object we
1414 // get once we resolve the ident. Collect the nodes and process them once we've found the ident.
1415 nodes := make([]ast.Node, 0, 4)
1416 for {
1417 switch node_ := node.(type) {
1418 case *ast.Ident:
1419 // obj is the field
1420 obj := g.info.ObjectOf(node_).(*types.Var)
1421 // the field is declared by the enclosing type
1422 g.see(obj, by)
1423 for _, n := range nodes {
1424 g.read(n, obj)
1425 }
1426 1427 if tname, ok := g.info.Uses[node_].(*types.TypeName); ok && tname.IsAlias() {
1428 // When embedding an alias we want to use the alias, not what the alias points to.
1429 g.use(tname, obj)
1430 } else {
1431 switch typ := typeutil.Dereference(g.info.TypeOf(node_)).(type) {
1432 case *types.Named:
1433 // (7.2) fields use their types
1434 g.use(typ.Obj(), obj)
1435 case *types.Basic:
1436 // Nothing to do
1437 default:
1438 // Other types are only possible for aliases, which we've already handled
1439 lint.ExhaustiveTypeSwitch(typ)
1440 }
1441 }
1442 return obj
1443 case *ast.StarExpr:
1444 node = node_.X
1445 case *ast.SelectorExpr:
1446 node = node_.Sel
1447 nodes = append(nodes, node_.X)
1448 case *ast.IndexExpr:
1449 node = node_.X
1450 nodes = append(nodes, node_.Index)
1451 case *ast.IndexListExpr:
1452 node = node_.X
1453 default:
1454 lint.ExhaustiveTypeSwitch(node_)
1455 }
1456 }
1457 }
1458 1459 // isNoCopyType reports whether a type represents the NoCopy sentinel
1460 // type. The NoCopy type is a named struct with no fields and exactly
1461 // one method `func Lock()` that is empty.
1462 //
1463 // FIXME(dh): currently we're not checking that the function body is
1464 // empty.
1465 func isNoCopyType(typ types.Type) bool {
1466 st, ok := typ.Underlying().(*types.Struct)
1467 if !ok {
1468 return false
1469 }
1470 if st.NumFields() != 0 {
1471 return false
1472 }
1473 1474 named, ok := types.Unalias(typ).(*types.Named)
1475 if !ok {
1476 return false
1477 }
1478 switch num := named.NumMethods(); num {
1479 case 1, 2:
1480 for i := 0; i < num; i++ {
1481 meth := named.Method(i)
1482 if meth.Name() != "Lock" && meth.Name() != "Unlock" {
1483 return false
1484 }
1485 sig := meth.Type().(*types.Signature)
1486 if sig.Params().Len() != 0 || sig.Results().Len() != 0 {
1487 return false
1488 }
1489 }
1490 default:
1491 return false
1492 }
1493 return true
1494 }
1495 1496 func (g *graph) namedType(typ *types.TypeName, spec ast.Expr) {
1497 // (2.2) named types use the type they're based on
1498 1499 if st, ok := spec.(*ast.StructType); ok {
1500 var hasHostLayout bool
1501 1502 // Named structs are special in that their unexported fields are only
1503 // used if they're being written to. That is, the fields are not used by
1504 // the named type itself, nor are the types of the fields.
1505 for _, field := range st.Fields.List {
1506 seen := map[*types.Struct]struct{}{}
1507 // For `type x struct { *x; F int }`, don't visit the embedded x
1508 seen[g.info.TypeOf(st).(*types.Struct)] = struct{}{}
1509 var hasExportedField func(t types.Type) bool
1510 hasExportedField = func(T types.Type) bool {
1511 t, ok := typeutil.Dereference(T).Underlying().(*types.Struct)
1512 if !ok {
1513 return false
1514 }
1515 if _, ok := seen[t]; ok {
1516 return false
1517 }
1518 seen[t] = struct{}{}
1519 for i := 0; i < t.NumFields(); i++ {
1520 field := t.Field(i)
1521 if field.Exported() {
1522 return true
1523 }
1524 if field.Embedded() && hasExportedField(field.Type()) {
1525 return true
1526 }
1527 }
1528 return false
1529 }
1530 1531 if len(field.Names) == 0 {
1532 fieldVar := g.embeddedField(field.Type, typ)
1533 if token.IsExported(fieldVar.Name()) && g.opts.ExportedIsUsed {
1534 // (6.2) structs use exported fields
1535 g.use(fieldVar, typ)
1536 }
1537 if g.opts.ExportedIsUsed && g.opts.ExportedFieldsAreUsed && hasExportedField(fieldVar.Type()) {
1538 // (6.5) structs use embedded structs that have exported fields (recursively)
1539 g.use(fieldVar, typ)
1540 }
1541 } else {
1542 for _, name := range field.Names {
1543 obj := g.info.ObjectOf(name)
1544 g.see(obj, typ)
1545 // (7.2) fields use their types
1546 //
1547 // This handles aliases correctly because ObjectOf(alias) returns the TypeName of the alias, not
1548 // what the alias points to.
1549 g.read(field.Type, obj)
1550 if name.Name == "_" {
1551 // (9.9) objects named the blank identifier are used
1552 g.use(obj, typ)
1553 } else if token.IsExported(name.Name) && g.opts.ExportedIsUsed {
1554 // (6.2) structs use exported fields
1555 g.use(obj, typ)
1556 }
1557 1558 if isNoCopyType(obj.Type()) {
1559 // (6.1) structs use fields of type NoCopy sentinel
1560 g.use(obj, typ)
1561 }
1562 }
1563 }
1564 1565 // (6.6) if the struct has a field of type structs.HostLayout, then
1566 // this signals that all fields are relevant to match some
1567 // externally specified memory layout.
1568 //
1569 // This augments the 5.2 heuristic of using all fields when
1570 // converting via unsafe.Pointer. For example, 5.2 doesn't currently
1571 // handle conversions involving more than one level of pointer
1572 // indirection (although it probably should). Another example that
1573 // doesn't involve the use of unsafe at all is exporting symbols for
1574 // use by C libraries.
1575 //
1576 // The actual requirements for the use of structs.HostLayout fields
1577 // haven't been determined yet. It's an open question whether named
1578 // types of underlying type structs.HostLayout, aliases of it,
1579 // generic instantiations, or embedding structs that themselves
1580 // contain a HostLayout field count as valid uses of the marker (see
1581 // https://golang.org/issues/66408#issuecomment-2120644459)
1582 //
1583 // For now, we require a struct to have a field of type
1584 // structs.HostLayout or an alias of it, where the field itself may
1585 // be embedded. We don't handle fields whose types are type
1586 // parameters.
1587 fieldType := types.Unalias(g.info.TypeOf(field.Type))
1588 if fieldType, ok := fieldType.(*types.Named); ok {
1589 obj := fieldType.Obj()
1590 if obj.Name() == "HostLayout" && obj.Pkg().Path() == "structs" {
1591 hasHostLayout = true
1592 }
1593 }
1594 }
1595 1596 // For 6.6.
1597 if hasHostLayout {
1598 g.useAllFieldsRecursively(typ.Type(), typ)
1599 }
1600 } else {
1601 g.read(spec, typ)
1602 }
1603 }
1604 1605 func (g *SerializedGraph) color(rootID NodeID, states []nodeState) {
1606 root := g.nodes[rootID]
1607 if states[rootID].seen() {
1608 return
1609 }
1610 states[rootID] |= nodeStateSeen
1611 for _, n := range root.uses {
1612 g.color(n, states)
1613 }
1614 }
1615 1616 type Object struct {
1617 Name string
1618 ShortName string
1619 // OPT(dh): use an enum for the kind
1620 Kind string
1621 Path ObjectPath
1622 Position token.Position
1623 DisplayPosition token.Position
1624 }
1625 1626 func (g *SerializedGraph) Results() Result {
1627 // XXX objectpath does not return paths for unexported objects, which means that if we analyze the same code twice
1628 // (e.g. normal and test variant), then some objects will appear multiple times, but may not be used identically. we
1629 // have to deduplicate based on the token.Position. Actually we have to do that, anyway, because we may flag types
1630 // local to functions. Those are probably always both used or both unused, but we don't want to flag them twice,
1631 // either.
1632 //
1633 // Note, however, that we still need objectpaths to deduplicate exported identifiers when analyzing independent
1634 // packages in whole-program mode, because if package A uses an object from package B, B will have been imported
1635 // from export data, and we will not have column information.
1636 //
1637 // XXX ^ document that design requirement.
1638 1639 states := g.colorAndQuieten()
1640 1641 var res Result
1642 // OPT(dh): can we find meaningful initial capacities for the used and unused slices?
1643 for _, n := range g.nodes[1:] {
1644 state := states[n.id]
1645 if state.seen() {
1646 res.Used = append(res.Used, n.obj)
1647 } else if state.quiet() {
1648 res.Quiet = append(res.Quiet, n.obj)
1649 } else {
1650 res.Unused = append(res.Unused, n.obj)
1651 }
1652 }
1653 1654 return res
1655 }
1656 1657 func (g *SerializedGraph) colorAndQuieten() []nodeState {
1658 states := make([]nodeState, len(g.nodes)+1)
1659 g.color(0, states)
1660 1661 var quieten func(id NodeID)
1662 quieten = func(id NodeID) {
1663 states[id] |= nodeStateQuiet
1664 for _, owned := range g.nodes[id].owns {
1665 quieten(owned)
1666 }
1667 }
1668 1669 for _, n := range g.nodes {
1670 if states[n.id].seen() {
1671 continue
1672 }
1673 for _, owned := range n.owns {
1674 quieten(owned)
1675 }
1676 }
1677 1678 return states
1679 }
1680 1681 // Dot formats a graph in Graphviz dot format.
1682 func (g *SerializedGraph) Dot() string {
1683 b := &strings.Builder{}
1684 states := g.colorAndQuieten()
1685 // Note: We use addresses in our node names. This only works as long as Go's garbage collector doesn't move
1686 // memory around in the middle of our debug printing.
1687 debugNode := func(n Node) {
1688 if n.id == 0 {
1689 fmt.Fprintf(b, "n%d [label=\"Root\"];\n", n.id)
1690 } else {
1691 color := "red"
1692 if states[n.id].seen() {
1693 color = "green"
1694 } else if states[n.id].quiet() {
1695 color = "grey"
1696 }
1697 label := fmt.Sprintf("%s %s\n%s", n.obj.Kind, n.obj.Name, n.obj.Position)
1698 fmt.Fprintf(b, "n%d [label=%q, color=%q];\n", n.id, label, color)
1699 }
1700 for _, e := range n.uses {
1701 fmt.Fprintf(b, "n%d -> n%d;\n", n.id, e)
1702 }
1703 1704 for _, owned := range n.owns {
1705 fmt.Fprintf(b, "n%d -> n%d [style=dashed];\n", n.id, owned)
1706 }
1707 }
1708 1709 fmt.Fprintf(b, "digraph{\n")
1710 for _, v := range g.nodes {
1711 debugNode(v)
1712 }
1713 1714 fmt.Fprintf(b, "}\n")
1715 1716 return b.String()
1717 }
1718 1719 func Graph(fset *token.FileSet,
1720 files []*ast.File,
1721 pkg *types.Package,
1722 info *types.Info,
1723 directives []lint.Directive,
1724 generated map[string]generated.Generator,
1725 opts Options,
1726 ) []Node {
1727 g := newGraph(fset, files, pkg, info, directives, generated, opts)
1728 g.entry()
1729 return g.nodes
1730 }
1731