Debian Codegraph @

unused/unused.go

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