aboutsummaryrefslogtreecommitdiff
path: root/vendor/honnef.co/go/tools/unused/unused.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/honnef.co/go/tools/unused/unused.go')
-rw-r--r--vendor/honnef.co/go/tools/unused/unused.go1964
1 files changed, 1964 insertions, 0 deletions
diff --git a/vendor/honnef.co/go/tools/unused/unused.go b/vendor/honnef.co/go/tools/unused/unused.go
new file mode 100644
index 0000000..152d369
--- /dev/null
+++ b/vendor/honnef.co/go/tools/unused/unused.go
@@ -0,0 +1,1964 @@
1package unused
2
3import (
4 "fmt"
5 "go/ast"
6 "go/token"
7 "go/types"
8 "io"
9 "strings"
10 "sync"
11 "sync/atomic"
12
13 "golang.org/x/tools/go/analysis"
14 "honnef.co/go/tools/go/types/typeutil"
15 "honnef.co/go/tools/internal/passes/buildssa"
16 "honnef.co/go/tools/lint"
17 "honnef.co/go/tools/lint/lintdsl"
18 "honnef.co/go/tools/ssa"
19)
20
21// The graph we construct omits nodes along a path that do not
22// contribute any new information to the solution. For example, the
23// full graph for a function with a receiver would be Func ->
24// Signature -> Var -> Type. However, since signatures cannot be
25// unused, and receivers are always considered used, we can compact
26// the graph down to Func -> Type. This makes the graph smaller, but
27// harder to debug.
28
29// TODO(dh): conversions between structs mark fields as used, but the
30// conversion itself isn't part of that subgraph. even if the function
31// containing the conversion is unused, the fields will be marked as
32// used.
33
34// TODO(dh): we cannot observe function calls in assembly files.
35
36/*
37
38- packages use:
39 - (1.1) exported named types (unless in package main)
40 - (1.2) exported functions (unless in package main)
41 - (1.3) exported variables (unless in package main)
42 - (1.4) exported constants (unless in package main)
43 - (1.5) init functions
44 - (1.6) functions exported to cgo
45 - (1.7) the main function iff in the main package
46 - (1.8) symbols linked via go:linkname
47
48- named types use:
49 - (2.1) exported methods
50 - (2.2) the type they're based on
51 - (2.3) all their aliases. we can't easily track uses of aliases
52 because go/types turns them into uses of the aliased types. assume
53 that if a type is used, so are all of its aliases.
54 - (2.4) the pointer type. this aids with eagerly implementing
55 interfaces. if a method that implements an interface is defined on
56 a pointer receiver, and the pointer type is never used, but the
57 named type is, then we still want to mark the method as used.
58
59- variables and constants use:
60 - their types
61
62- functions use:
63 - (4.1) all their arguments, return parameters and receivers
64 - (4.2) anonymous functions defined beneath them
65 - (4.3) closures and bound methods.
66 this implements a simplified model where a function is used merely by being referenced, even if it is never called.
67 that way we don't have to keep track of closures escaping functions.
68 - (4.4) functions they return. we assume that someone else will call the returned function
69 - (4.5) functions/interface methods they call
70 - types they instantiate or convert to
71 - (4.7) fields they access
72 - (4.8) types of all instructions
73 - (4.9) package-level variables they assign to iff in tests (sinks for benchmarks)
74
75- conversions use:
76 - (5.1) when converting between two equivalent structs, the fields in
77 either struct use each other. the fields are relevant for the
78 conversion, but only if the fields are also accessed outside the
79 conversion.
80 - (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
81
82- structs use:
83 - (6.1) fields of type NoCopy sentinel
84 - (6.2) exported fields
85 - (6.3) embedded fields that help implement interfaces (either fully implements it, or contributes required methods) (recursively)
86 - (6.4) embedded fields that have exported methods (recursively)
87 - (6.5) embedded structs that have exported fields (recursively)
88
89- (7.1) field accesses use fields
90- (7.2) fields use their types
91
92- (8.0) How we handle interfaces:
93 - (8.1) We do not technically care about interfaces that only consist of
94 exported methods. Exported methods on concrete types are always
95 marked as used.
96 - Any concrete type implements all known interfaces. Even if it isn't
97 assigned to any interfaces in our code, the user may receive a value
98 of the type and expect to pass it back to us through an interface.
99
100 Concrete types use their methods that implement interfaces. If the
101 type is used, it uses those methods. Otherwise, it doesn't. This
102 way, types aren't incorrectly marked reachable through the edge
103 from method to type.
104
105 - (8.3) All interface methods are marked as used, even if they never get
106 called. This is to accomodate sum types (unexported interface
107 method that must exist but never gets called.)
108
109 - (8.4) All embedded interfaces are marked as used. This is an
110 extension of 8.3, but we have to explicitly track embedded
111 interfaces because in a chain C->B->A, B wouldn't be marked as
112 used by 8.3 just because it contributes A's methods to C.
113
114- Inherent uses:
115 - thunks and other generated wrappers call the real function
116 - (9.2) variables use their types
117 - (9.3) types use their underlying and element types
118 - (9.4) conversions use the type they convert to
119 - (9.5) instructions use their operands
120 - (9.6) instructions use their operands' types
121 - (9.7) variable _reads_ use variables, writes do not, except in tests
122 - (9.8) runtime functions that may be called from user code via the compiler
123
124
125- const groups:
126 (10.1) if one constant out of a block of constants is used, mark all
127 of them used. a lot of the time, unused constants exist for the sake
128 of completeness. See also
129 https://github.com/dominikh/go-tools/issues/365
130
131
132- (11.1) anonymous struct types use all their fields. we cannot
133 deduplicate struct types, as that leads to order-dependent
134 reportings. we can't not deduplicate struct types while still
135 tracking fields, because then each instance of the unnamed type in
136 the data flow chain will get its own fields, causing false
137 positives. Thus, we only accurately track fields of named struct
138 types, and assume that unnamed struct types use all their fields.
139
140
141- Differences in whole program mode:
142 - (e2) types aim to implement all exported interfaces from all packages
143 - (e3) exported identifiers aren't automatically used. for fields and
144 methods this poses extra issues due to reflection. We assume
145 that all exported fields are used. We also maintain a list of
146 known reflection-based method callers.
147
148*/
149
150func assert(b bool) {
151 if !b {
152 panic("failed assertion")
153 }
154}
155
156func typString(obj types.Object) string {
157 switch obj := obj.(type) {
158 case *types.Func:
159 return "func"
160 case *types.Var:
161 if obj.IsField() {
162 return "field"
163 }
164 return "var"
165 case *types.Const:
166 return "const"
167 case *types.TypeName:
168 return "type"
169 default:
170 return "identifier"
171 }
172}
173
174// /usr/lib/go/src/runtime/proc.go:433:6: func badmorestackg0 is unused (U1000)
175
176// Functions defined in the Go runtime that may be called through
177// compiler magic or via assembly.
178var runtimeFuncs = map[string]bool{
179 // The first part of the list is copied from
180 // cmd/compile/internal/gc/builtin.go, var runtimeDecls
181 "newobject": true,
182 "panicindex": true,
183 "panicslice": true,
184 "panicdivide": true,
185 "panicmakeslicelen": true,
186 "throwinit": true,
187 "panicwrap": true,
188 "gopanic": true,
189 "gorecover": true,
190 "goschedguarded": true,
191 "printbool": true,
192 "printfloat": true,
193 "printint": true,
194 "printhex": true,
195 "printuint": true,
196 "printcomplex": true,
197 "printstring": true,
198 "printpointer": true,
199 "printiface": true,
200 "printeface": true,
201 "printslice": true,
202 "printnl": true,
203 "printsp": true,
204 "printlock": true,
205 "printunlock": true,
206 "concatstring2": true,
207 "concatstring3": true,
208 "concatstring4": true,
209 "concatstring5": true,
210 "concatstrings": true,
211 "cmpstring": true,
212 "intstring": true,
213 "slicebytetostring": true,
214 "slicebytetostringtmp": true,
215 "slicerunetostring": true,
216 "stringtoslicebyte": true,
217 "stringtoslicerune": true,
218 "slicecopy": true,
219 "slicestringcopy": true,
220 "decoderune": true,
221 "countrunes": true,
222 "convI2I": true,
223 "convT16": true,
224 "convT32": true,
225 "convT64": true,
226 "convTstring": true,
227 "convTslice": true,
228 "convT2E": true,
229 "convT2Enoptr": true,
230 "convT2I": true,
231 "convT2Inoptr": true,
232 "assertE2I": true,
233 "assertE2I2": true,
234 "assertI2I": true,
235 "assertI2I2": true,
236 "panicdottypeE": true,
237 "panicdottypeI": true,
238 "panicnildottype": true,
239 "ifaceeq": true,
240 "efaceeq": true,
241 "fastrand": true,
242 "makemap64": true,
243 "makemap": true,
244 "makemap_small": true,
245 "mapaccess1": true,
246 "mapaccess1_fast32": true,
247 "mapaccess1_fast64": true,
248 "mapaccess1_faststr": true,
249 "mapaccess1_fat": true,
250 "mapaccess2": true,
251 "mapaccess2_fast32": true,
252 "mapaccess2_fast64": true,
253 "mapaccess2_faststr": true,
254 "mapaccess2_fat": true,
255 "mapassign": true,
256 "mapassign_fast32": true,
257 "mapassign_fast32ptr": true,
258 "mapassign_fast64": true,
259 "mapassign_fast64ptr": true,
260 "mapassign_faststr": true,
261 "mapiterinit": true,
262 "mapdelete": true,
263 "mapdelete_fast32": true,
264 "mapdelete_fast64": true,
265 "mapdelete_faststr": true,
266 "mapiternext": true,
267 "mapclear": true,
268 "makechan64": true,
269 "makechan": true,
270 "chanrecv1": true,
271 "chanrecv2": true,
272 "chansend1": true,
273 "closechan": true,
274 "writeBarrier": true,
275 "typedmemmove": true,
276 "typedmemclr": true,
277 "typedslicecopy": true,
278 "selectnbsend": true,
279 "selectnbrecv": true,
280 "selectnbrecv2": true,
281 "selectsetpc": true,
282 "selectgo": true,
283 "block": true,
284 "makeslice": true,
285 "makeslice64": true,
286 "growslice": true,
287 "memmove": true,
288 "memclrNoHeapPointers": true,
289 "memclrHasPointers": true,
290 "memequal": true,
291 "memequal8": true,
292 "memequal16": true,
293 "memequal32": true,
294 "memequal64": true,
295 "memequal128": true,
296 "int64div": true,
297 "uint64div": true,
298 "int64mod": true,
299 "uint64mod": true,
300 "float64toint64": true,
301 "float64touint64": true,
302 "float64touint32": true,
303 "int64tofloat64": true,
304 "uint64tofloat64": true,
305 "uint32tofloat64": true,
306 "complex128div": true,
307 "racefuncenter": true,
308 "racefuncenterfp": true,
309 "racefuncexit": true,
310 "raceread": true,
311 "racewrite": true,
312 "racereadrange": true,
313 "racewriterange": true,
314 "msanread": true,
315 "msanwrite": true,
316 "x86HasPOPCNT": true,
317 "x86HasSSE41": true,
318 "arm64HasATOMICS": true,
319
320 // The second part of the list is extracted from assembly code in
321 // the standard library, with the exception of the runtime package itself
322 "abort": true,
323 "aeshashbody": true,
324 "args": true,
325 "asminit": true,
326 "badctxt": true,
327 "badmcall2": true,
328 "badmcall": true,
329 "badmorestackg0": true,
330 "badmorestackgsignal": true,
331 "badsignal2": true,
332 "callbackasm1": true,
333 "callCfunction": true,
334 "cgocallback_gofunc": true,
335 "cgocallbackg": true,
336 "checkgoarm": true,
337 "check": true,
338 "debugCallCheck": true,
339 "debugCallWrap": true,
340 "emptyfunc": true,
341 "entersyscall": true,
342 "exit": true,
343 "exits": true,
344 "exitsyscall": true,
345 "externalthreadhandler": true,
346 "findnull": true,
347 "goexit1": true,
348 "gostring": true,
349 "i386_set_ldt": true,
350 "_initcgo": true,
351 "init_thread_tls": true,
352 "ldt0setup": true,
353 "libpreinit": true,
354 "load_g": true,
355 "morestack": true,
356 "mstart": true,
357 "nacl_sysinfo": true,
358 "nanotimeQPC": true,
359 "nanotime": true,
360 "newosproc0": true,
361 "newproc": true,
362 "newstack": true,
363 "noted": true,
364 "nowQPC": true,
365 "osinit": true,
366 "printf": true,
367 "racecallback": true,
368 "reflectcallmove": true,
369 "reginit": true,
370 "rt0_go": true,
371 "save_g": true,
372 "schedinit": true,
373 "setldt": true,
374 "settls": true,
375 "sighandler": true,
376 "sigprofNonGo": true,
377 "sigtrampgo": true,
378 "_sigtramp": true,
379 "sigtramp": true,
380 "stackcheck": true,
381 "syscall_chdir": true,
382 "syscall_chroot": true,
383 "syscall_close": true,
384 "syscall_dup2": true,
385 "syscall_execve": true,
386 "syscall_exit": true,
387 "syscall_fcntl": true,
388 "syscall_forkx": true,
389 "syscall_gethostname": true,
390 "syscall_getpid": true,
391 "syscall_ioctl": true,
392 "syscall_pipe": true,
393 "syscall_rawsyscall6": true,
394 "syscall_rawSyscall6": true,
395 "syscall_rawsyscall": true,
396 "syscall_RawSyscall": true,
397 "syscall_rawsysvicall6": true,
398 "syscall_setgid": true,
399 "syscall_setgroups": true,
400 "syscall_setpgid": true,
401 "syscall_setsid": true,
402 "syscall_setuid": true,
403 "syscall_syscall6": true,
404 "syscall_syscall": true,
405 "syscall_Syscall": true,
406 "syscall_sysvicall6": true,
407 "syscall_wait4": true,
408 "syscall_write": true,
409 "traceback": true,
410 "tstart": true,
411 "usplitR0": true,
412 "wbBufFlush": true,
413 "write": true,
414}
415
416type pkg struct {
417 Fset *token.FileSet
418 Files []*ast.File
419 Pkg *types.Package
420 TypesInfo *types.Info
421 TypesSizes types.Sizes
422 SSA *ssa.Package
423 SrcFuncs []*ssa.Function
424}
425
426type Checker struct {
427 WholeProgram bool
428 Debug io.Writer
429
430 mu sync.Mutex
431 initialPackages map[*types.Package]struct{}
432 allPackages map[*types.Package]struct{}
433 graph *Graph
434}
435
436func NewChecker(wholeProgram bool) *Checker {
437 return &Checker{
438 initialPackages: map[*types.Package]struct{}{},
439 allPackages: map[*types.Package]struct{}{},
440 WholeProgram: wholeProgram,
441 }
442}
443
444func (c *Checker) Analyzer() *analysis.Analyzer {
445 name := "U1000"
446 if c.WholeProgram {
447 name = "U1001"
448 }
449 return &analysis.Analyzer{
450 Name: name,
451 Doc: "Unused code",
452 Run: c.Run,
453 Requires: []*analysis.Analyzer{buildssa.Analyzer},
454 }
455}
456
457func (c *Checker) Run(pass *analysis.Pass) (interface{}, error) {
458 c.mu.Lock()
459 if c.graph == nil {
460 c.graph = NewGraph()
461 c.graph.wholeProgram = c.WholeProgram
462 c.graph.fset = pass.Fset
463 }
464
465 var visit func(pkg *types.Package)
466 visit = func(pkg *types.Package) {
467 if _, ok := c.allPackages[pkg]; ok {
468 return
469 }
470 c.allPackages[pkg] = struct{}{}
471 for _, imp := range pkg.Imports() {
472 visit(imp)
473 }
474 }
475 visit(pass.Pkg)
476
477 c.initialPackages[pass.Pkg] = struct{}{}
478 c.mu.Unlock()
479
480 ssapkg := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA)
481 pkg := &pkg{
482 Fset: pass.Fset,
483 Files: pass.Files,
484 Pkg: pass.Pkg,
485 TypesInfo: pass.TypesInfo,
486 TypesSizes: pass.TypesSizes,
487 SSA: ssapkg.Pkg,
488 SrcFuncs: ssapkg.SrcFuncs,
489 }
490
491 c.processPkg(c.graph, pkg)
492
493 return nil, nil
494}
495
496func (c *Checker) ProblemObject(fset *token.FileSet, obj types.Object) lint.Problem {
497 name := obj.Name()
498 if sig, ok := obj.Type().(*types.Signature); ok && sig.Recv() != nil {
499 switch sig.Recv().Type().(type) {
500 case *types.Named, *types.Pointer:
501 typ := types.TypeString(sig.Recv().Type(), func(*types.Package) string { return "" })
502 if len(typ) > 0 && typ[0] == '*' {
503 name = fmt.Sprintf("(%s).%s", typ, obj.Name())
504 } else if len(typ) > 0 {
505 name = fmt.Sprintf("%s.%s", typ, obj.Name())
506 }
507 }
508 }
509
510 checkName := "U1000"
511 if c.WholeProgram {
512 checkName = "U1001"
513 }
514 return lint.Problem{
515 Pos: lint.DisplayPosition(fset, obj.Pos()),
516 Message: fmt.Sprintf("%s %s is unused", typString(obj), name),
517 Check: checkName,
518 }
519}
520
521func (c *Checker) Result() []types.Object {
522 out := c.results()
523
524 out2 := make([]types.Object, 0, len(out))
525 for _, v := range out {
526 if _, ok := c.initialPackages[v.Pkg()]; !ok {
527 continue
528 }
529 out2 = append(out2, v)
530 }
531
532 return out2
533}
534
535func (c *Checker) debugf(f string, v ...interface{}) {
536 if c.Debug != nil {
537 fmt.Fprintf(c.Debug, f, v...)
538 }
539}
540
541func (graph *Graph) quieten(node *Node) {
542 if node.seen {
543 return
544 }
545 switch obj := node.obj.(type) {
546 case *types.Named:
547 for i := 0; i < obj.NumMethods(); i++ {
548 m := obj.Method(i)
549 if node, ok := graph.nodeMaybe(m); ok {
550 node.quiet = true
551 }
552 }
553 case *types.Struct:
554 for i := 0; i < obj.NumFields(); i++ {
555 if node, ok := graph.nodeMaybe(obj.Field(i)); ok {
556 node.quiet = true
557 }
558 }
559 case *types.Interface:
560 for i := 0; i < obj.NumExplicitMethods(); i++ {
561 m := obj.ExplicitMethod(i)
562 if node, ok := graph.nodeMaybe(m); ok {
563 node.quiet = true
564 }
565 }
566 }
567}
568
569func (c *Checker) results() []types.Object {
570 if c.graph == nil {
571 // We never analyzed any packages
572 return nil
573 }
574
575 var out []types.Object
576
577 if c.WholeProgram {
578 var ifaces []*types.Interface
579 var notIfaces []types.Type
580
581 // implement as many interfaces as possible
582 c.graph.seenTypes.Iterate(func(t types.Type, _ interface{}) {
583 switch t := t.(type) {
584 case *types.Interface:
585 if t.NumMethods() > 0 {
586 ifaces = append(ifaces, t)
587 }
588 default:
589 if _, ok := t.Underlying().(*types.Interface); !ok {
590 notIfaces = append(notIfaces, t)
591 }
592 }
593 })
594
595 for pkg := range c.allPackages {
596 for _, iface := range interfacesFromExportData(pkg) {
597 if iface.NumMethods() > 0 {
598 ifaces = append(ifaces, iface)
599 }
600 }
601 }
602
603 ctx := &context{
604 g: c.graph,
605 seenTypes: &c.graph.seenTypes,
606 }
607 // (8.0) handle interfaces
608 // (e2) types aim to implement all exported interfaces from all packages
609 for _, t := range notIfaces {
610 // OPT(dh): it is unfortunate that we do not have access
611 // to a populated method set at this point.
612 ms := types.NewMethodSet(t)
613 for _, iface := range ifaces {
614 if sels, ok := c.graph.implements(t, iface, ms); ok {
615 for _, sel := range sels {
616 c.graph.useMethod(ctx, t, sel, t, edgeImplements)
617 }
618 }
619 }
620 }
621 }
622
623 if c.Debug != nil {
624 debugNode := func(node *Node) {
625 if node.obj == nil {
626 c.debugf("n%d [label=\"Root\"];\n", node.id)
627 } else {
628 c.debugf("n%d [label=%q];\n", node.id, fmt.Sprintf("(%T) %s", node.obj, node.obj))
629 }
630 for _, e := range node.used {
631 for i := edgeKind(1); i < 64; i++ {
632 if e.kind.is(1 << i) {
633 c.debugf("n%d -> n%d [label=%q];\n", node.id, e.node.id, edgeKind(1<<i))
634 }
635 }
636 }
637 }
638
639 c.debugf("digraph{\n")
640 debugNode(c.graph.Root)
641 c.graph.Nodes.Range(func(k, v interface{}) bool {
642 debugNode(v.(*Node))
643 return true
644 })
645 c.graph.TypeNodes.Iterate(func(key types.Type, value interface{}) {
646 debugNode(value.(*Node))
647 })
648
649 c.debugf("}\n")
650 }
651
652 c.graph.color(c.graph.Root)
653 // if a node is unused, don't report any of the node's
654 // children as unused. for example, if a function is unused,
655 // don't flag its receiver. if a named type is unused, don't
656 // flag its methods.
657
658 c.graph.Nodes.Range(func(k, v interface{}) bool {
659 c.graph.quieten(v.(*Node))
660 return true
661 })
662 c.graph.TypeNodes.Iterate(func(_ types.Type, value interface{}) {
663 c.graph.quieten(value.(*Node))
664 })
665
666 report := func(node *Node) {
667 if node.seen {
668 return
669 }
670 if node.quiet {
671 c.debugf("n%d [color=purple];\n", node.id)
672 return
673 }
674
675 c.debugf("n%d [color=red];\n", node.id)
676 switch obj := node.obj.(type) {
677 case *types.Var:
678 // don't report unnamed variables (interface embedding)
679 if obj.Name() != "" || obj.IsField() {
680 out = append(out, obj)
681 }
682 return
683 case types.Object:
684 if obj.Name() != "_" {
685 out = append(out, obj)
686 }
687 return
688 }
689 c.debugf("n%d [color=gray];\n", node.id)
690 }
691 c.graph.Nodes.Range(func(k, v interface{}) bool {
692 report(v.(*Node))
693 return true
694 })
695 c.graph.TypeNodes.Iterate(func(_ types.Type, value interface{}) {
696 report(value.(*Node))
697 })
698
699 return out
700}
701
702func (c *Checker) processPkg(graph *Graph, pkg *pkg) {
703 if pkg.Pkg.Path() == "unsafe" {
704 return
705 }
706 graph.entry(pkg)
707}
708
709func objNodeKeyFor(fset *token.FileSet, obj types.Object) objNodeKey {
710 var kind objType
711 switch obj.(type) {
712 case *types.PkgName:
713 kind = otPkgName
714 case *types.Const:
715 kind = otConst
716 case *types.TypeName:
717 kind = otTypeName
718 case *types.Var:
719 kind = otVar
720 case *types.Func:
721 kind = otFunc
722 case *types.Label:
723 kind = otLabel
724 case *types.Builtin:
725 kind = otBuiltin
726 case *types.Nil:
727 kind = otNil
728 default:
729 panic(fmt.Sprintf("unreachable: %T", obj))
730 }
731
732 position := fset.PositionFor(obj.Pos(), false)
733 position.Column = 0
734 position.Offset = 0
735 return objNodeKey{
736 position: position,
737 kind: kind,
738 name: obj.Name(),
739 }
740}
741
742type objType uint8
743
744const (
745 otPkgName objType = iota
746 otConst
747 otTypeName
748 otVar
749 otFunc
750 otLabel
751 otBuiltin
752 otNil
753)
754
755// An objNodeKey describes a types.Object node in the graph.
756//
757// Due to test variants we may end up with multiple instances of the
758// same object, which is why we have to deduplicate based on their
759// source position. And because export data lacks column information,
760// we also have to incorporate the object's string representation in
761// the key.
762//
763// Previously we used the object's full string representation
764// (types.ObjectString), but that causes a significant amount of
765// allocations. Currently we're using the object's type and name, in
766// the hope that it is impossible for two objects to have the same
767// type, name and file position.
768type objNodeKey struct {
769 position token.Position
770 kind objType
771 name string
772}
773
774type Graph struct {
775 // accessed atomically
776 nodeOffset uint64
777
778 // Safe for concurrent use
779 fset *token.FileSet
780 Root *Node
781 seenTypes typeutil.Map
782 Nodes sync.Map // map[interface{}]*Node
783 objNodes sync.Map // map[objNodeKey]*Node
784
785 // read-only
786 wholeProgram bool
787
788 // need synchronisation
789 mu sync.Mutex
790 TypeNodes typeutil.Map
791}
792
793type context struct {
794 g *Graph
795 pkg *pkg
796 seenFns map[string]struct{}
797 seenTypes *typeutil.Map
798 nodeCounter uint64
799
800 // local cache for the map in Graph
801 typeNodes typeutil.Map
802}
803
804func NewGraph() *Graph {
805 g := &Graph{}
806 g.Root = g.newNode(&context{}, nil)
807 return g
808}
809
810func (g *Graph) color(root *Node) {
811 if root.seen {
812 return
813 }
814 root.seen = true
815 for _, e := range root.used {
816 g.color(e.node)
817 }
818}
819
820type ConstGroup struct {
821 // give the struct a size to get unique pointers
822 _ byte
823}
824
825func (ConstGroup) String() string { return "const group" }
826
827type edge struct {
828 node *Node
829 kind edgeKind
830}
831
832type Node struct {
833 obj interface{}
834 id uint64
835
836 mu sync.Mutex
837 used []edge
838
839 // set during final graph walk if node is reachable
840 seen bool
841 // a parent node (e.g. the struct type containing a field) is
842 // already unused, don't report children
843 quiet bool
844}
845
846func (g *Graph) nodeMaybe(obj types.Object) (*Node, bool) {
847 if node, ok := g.Nodes.Load(obj); ok {
848 return node.(*Node), true
849 }
850 return nil, false
851}
852
853func (g *Graph) node(ctx *context, obj interface{}) (node *Node, new bool) {
854 if t, ok := obj.(types.Type); ok {
855 if v := ctx.typeNodes.At(t); v != nil {
856 return v.(*Node), false
857 }
858 g.mu.Lock()
859 defer g.mu.Unlock()
860
861 if v := g.TypeNodes.At(t); v != nil {
862 return v.(*Node), false
863 }
864 node := g.newNode(ctx, t)
865 g.TypeNodes.Set(t, node)
866 ctx.typeNodes.Set(t, node)
867 return node, true
868 }
869
870 if node, ok := g.Nodes.Load(obj); ok {
871 return node.(*Node), false
872 }
873
874 if obj, ok := obj.(types.Object); ok {
875 key := objNodeKeyFor(g.fset, obj)
876 if o, ok := g.objNodes.Load(key); ok {
877 onode := o.(*Node)
878 return onode, false
879 }
880
881 node = g.newNode(ctx, obj)
882 g.Nodes.Store(obj, node)
883 g.objNodes.Store(key, node)
884 return node, true
885 }
886
887 node = g.newNode(ctx, obj)
888 g.Nodes.Store(obj, node)
889 return node, true
890}
891
892func (g *Graph) newNode(ctx *context, obj interface{}) *Node {
893 ctx.nodeCounter++
894 return &Node{
895 obj: obj,
896 id: ctx.nodeCounter,
897 }
898}
899
900func (n *Node) use(node *Node, kind edgeKind) {
901 n.mu.Lock()
902 defer n.mu.Unlock()
903 assert(node != nil)
904 n.used = append(n.used, edge{node: node, kind: kind})
905}
906
907// isIrrelevant reports whether an object's presence in the graph is
908// of any relevance. A lot of objects will never have outgoing edges,
909// nor meaningful incoming ones. Examples are basic types and empty
910// signatures, among many others.
911//
912// Dropping these objects should have no effect on correctness, but
913// may improve performance. It also helps with debugging, as it
914// greatly reduces the size of the graph.
915func isIrrelevant(obj interface{}) bool {
916 if obj, ok := obj.(types.Object); ok {
917 switch obj := obj.(type) {
918 case *types.Var:
919 if obj.IsField() {
920 // We need to track package fields
921 return false
922 }
923 if obj.Pkg() != nil && obj.Parent() == obj.Pkg().Scope() {
924 // We need to track package-level variables
925 return false
926 }
927 return isIrrelevant(obj.Type())
928 default:
929 return false
930 }
931 }
932 if T, ok := obj.(types.Type); ok {
933 switch T := T.(type) {
934 case *types.Array:
935 return isIrrelevant(T.Elem())
936 case *types.Slice:
937 return isIrrelevant(T.Elem())
938 case *types.Basic:
939 return true
940 case *types.Tuple:
941 for i := 0; i < T.Len(); i++ {
942 if !isIrrelevant(T.At(i).Type()) {
943 return false
944 }
945 }
946 return true
947 case *types.Signature:
948 if T.Recv() != nil {
949 return false
950 }
951 for i := 0; i < T.Params().Len(); i++ {
952 if !isIrrelevant(T.Params().At(i)) {
953 return false
954 }
955 }
956 for i := 0; i < T.Results().Len(); i++ {
957 if !isIrrelevant(T.Results().At(i)) {
958 return false
959 }
960 }
961 return true
962 case *types.Interface:
963 return T.NumMethods() == 0 && T.NumEmbeddeds() == 0
964 case *types.Pointer:
965 return isIrrelevant(T.Elem())
966 case *types.Map:
967 return isIrrelevant(T.Key()) && isIrrelevant(T.Elem())
968 case *types.Struct:
969 return T.NumFields() == 0
970 case *types.Chan:
971 return isIrrelevant(T.Elem())
972 default:
973 return false
974 }
975 }
976 return false
977}
978
979func (ctx *context) see(obj interface{}) *Node {
980 if isIrrelevant(obj) {
981 return nil
982 }
983
984 assert(obj != nil)
985 // add new node to graph
986 node, _ := ctx.g.node(ctx, obj)
987 return node
988}
989
990func (ctx *context) use(used, by interface{}, kind edgeKind) {
991 if isIrrelevant(used) {
992 return
993 }
994
995 assert(used != nil)
996 if obj, ok := by.(types.Object); ok && obj.Pkg() != nil {
997 if !ctx.g.wholeProgram && obj.Pkg() != ctx.pkg.Pkg {
998 return
999 }
1000 }
1001 usedNode, new := ctx.g.node(ctx, used)
1002 assert(!new)
1003 if by == nil {
1004 ctx.g.Root.use(usedNode, kind)
1005 } else {
1006 byNode, new := ctx.g.node(ctx, by)
1007 assert(!new)
1008 byNode.use(usedNode, kind)
1009 }
1010}
1011
1012func (ctx *context) seeAndUse(used, by interface{}, kind edgeKind) *Node {
1013 node := ctx.see(used)
1014 ctx.use(used, by, kind)
1015 return node
1016}
1017
1018// trackExportedIdentifier reports whether obj should be considered
1019// used due to being exported, checking various conditions that affect
1020// the decision.
1021func (g *Graph) trackExportedIdentifier(ctx *context, obj types.Object) bool {
1022 if !obj.Exported() {
1023 // object isn't exported, the question is moot
1024 return false
1025 }
1026 path := g.fset.Position(obj.Pos()).Filename
1027 if g.wholeProgram {
1028 // Example functions without "Output:" comments aren't being
1029 // run and thus don't show up in the graph.
1030 if strings.HasSuffix(path, "_test.go") && strings.HasPrefix(obj.Name(), "Example") {
1031 return true
1032 }
1033 // whole program mode tracks exported identifiers accurately
1034 return false
1035 }
1036
1037 if ctx.pkg.Pkg.Name() == "main" && !strings.HasSuffix(path, "_test.go") {
1038 // exported identifiers in package main can't be imported.
1039 // However, test functions can be called, and xtest packages
1040 // even have access to exported identifiers.
1041 return false
1042 }
1043
1044 if strings.HasSuffix(path, "_test.go") {
1045 if strings.HasPrefix(obj.Name(), "Test") ||
1046 strings.HasPrefix(obj.Name(), "Benchmark") ||
1047 strings.HasPrefix(obj.Name(), "Example") {
1048 return true
1049 }
1050 return false
1051 }
1052
1053 return true
1054}
1055
1056func (g *Graph) entry(pkg *pkg) {
1057 no := atomic.AddUint64(&g.nodeOffset, 1)
1058 ctx := &context{
1059 g: g,
1060 pkg: pkg,
1061 nodeCounter: no * 1e9,
1062 seenFns: map[string]struct{}{},
1063 }
1064 if g.wholeProgram {
1065 ctx.seenTypes = &g.seenTypes
1066 } else {
1067 ctx.seenTypes = &typeutil.Map{}
1068 }
1069
1070 scopes := map[*types.Scope]*ssa.Function{}
1071 for _, fn := range pkg.SrcFuncs {
1072 if fn.Object() != nil {
1073 scope := fn.Object().(*types.Func).Scope()
1074 scopes[scope] = fn
1075 }
1076 }
1077
1078 for _, f := range pkg.Files {
1079 for _, cg := range f.Comments {
1080 for _, c := range cg.List {
1081 if strings.HasPrefix(c.Text, "//go:linkname ") {
1082 // FIXME(dh): we're looking at all comments. The
1083 // compiler only looks at comments in the
1084 // left-most column. The intention probably is to
1085 // only look at top-level comments.
1086
1087 // (1.8) packages use symbols linked via go:linkname
1088 fields := strings.Fields(c.Text)
1089 if len(fields) == 3 {
1090 if m, ok := pkg.SSA.Members[fields[1]]; ok {
1091 var obj types.Object
1092 switch m := m.(type) {
1093 case *ssa.Global:
1094 obj = m.Object()
1095 case *ssa.Function:
1096 obj = m.Object()
1097 default:
1098 panic(fmt.Sprintf("unhandled type: %T", m))
1099 }
1100 assert(obj != nil)
1101 ctx.seeAndUse(obj, nil, edgeLinkname)
1102 }
1103 }
1104 }
1105 }
1106 }
1107 }
1108
1109 surroundingFunc := func(obj types.Object) *ssa.Function {
1110 scope := obj.Parent()
1111 for scope != nil {
1112 if fn := scopes[scope]; fn != nil {
1113 return fn
1114 }
1115 scope = scope.Parent()
1116 }
1117 return nil
1118 }
1119
1120 // SSA form won't tell us about locally scoped types that aren't
1121 // being used. Walk the list of Defs to get all named types.
1122 //
1123 // SSA form also won't tell us about constants; use Defs and Uses
1124 // to determine which constants exist and which are being used.
1125 for _, obj := range pkg.TypesInfo.Defs {
1126 switch obj := obj.(type) {
1127 case *types.TypeName:
1128 // types are being handled by walking the AST
1129 case *types.Const:
1130 ctx.see(obj)
1131 fn := surroundingFunc(obj)
1132 if fn == nil && g.trackExportedIdentifier(ctx, obj) {
1133 // (1.4) packages use exported constants (unless in package main)
1134 ctx.use(obj, nil, edgeExportedConstant)
1135 }
1136 g.typ(ctx, obj.Type(), nil)
1137 ctx.seeAndUse(obj.Type(), obj, edgeType)
1138 }
1139 }
1140
1141 // Find constants being used inside functions, find sinks in tests
1142 for _, fn := range pkg.SrcFuncs {
1143 if fn.Object() != nil {
1144 ctx.see(fn.Object())
1145 }
1146 node := fn.Syntax()
1147 if node == nil {
1148 continue
1149 }
1150 ast.Inspect(node, func(node ast.Node) bool {
1151 switch node := node.(type) {
1152 case *ast.Ident:
1153 obj, ok := pkg.TypesInfo.Uses[node]
1154 if !ok {
1155 return true
1156 }
1157 switch obj := obj.(type) {
1158 case *types.Const:
1159 ctx.seeAndUse(obj, owningObject(fn), edgeUsedConstant)
1160 }
1161 case *ast.AssignStmt:
1162 for _, expr := range node.Lhs {
1163 ident, ok := expr.(*ast.Ident)
1164 if !ok {
1165 continue
1166 }
1167 obj := pkg.TypesInfo.ObjectOf(ident)
1168 if obj == nil {
1169 continue
1170 }
1171 path := g.fset.File(obj.Pos()).Name()
1172 if strings.HasSuffix(path, "_test.go") {
1173 if obj.Parent() != nil && obj.Parent().Parent() != nil && obj.Parent().Parent().Parent() == nil {
1174 // object's scope is the package, whose
1175 // parent is the file, whose parent is nil
1176
1177 // (4.9) functions use package-level variables they assign to iff in tests (sinks for benchmarks)
1178 // (9.7) variable _reads_ use variables, writes do not, except in tests
1179 ctx.seeAndUse(obj, owningObject(fn), edgeTestSink)
1180 }
1181 }
1182 }
1183 }
1184
1185 return true
1186 })
1187 }
1188 // Find constants being used in non-function contexts
1189 for _, obj := range pkg.TypesInfo.Uses {
1190 _, ok := obj.(*types.Const)
1191 if !ok {
1192 continue
1193 }
1194 ctx.seeAndUse(obj, nil, edgeUsedConstant)
1195 }
1196
1197 var fns []*types.Func
1198 var fn *types.Func
1199 var stack []ast.Node
1200 for _, f := range pkg.Files {
1201 ast.Inspect(f, func(n ast.Node) bool {
1202 if n == nil {
1203 pop := stack[len(stack)-1]
1204 stack = stack[:len(stack)-1]
1205 if _, ok := pop.(*ast.FuncDecl); ok {
1206 fns = fns[:len(fns)-1]
1207 if len(fns) == 0 {
1208 fn = nil
1209 } else {
1210 fn = fns[len(fns)-1]
1211 }
1212 }
1213 return true
1214 }
1215 stack = append(stack, n)
1216 switch n := n.(type) {
1217 case *ast.FuncDecl:
1218 fn = pkg.TypesInfo.ObjectOf(n.Name).(*types.Func)
1219 fns = append(fns, fn)
1220 ctx.see(fn)
1221 case *ast.GenDecl:
1222 switch n.Tok {
1223 case token.CONST:
1224 groups := lintdsl.GroupSpecs(pkg.Fset, n.Specs)
1225 for _, specs := range groups {
1226 if len(specs) > 1 {
1227 cg := &ConstGroup{}
1228 ctx.see(cg)
1229 for _, spec := range specs {
1230 for _, name := range spec.(*ast.ValueSpec).Names {
1231 obj := pkg.TypesInfo.ObjectOf(name)
1232 // (10.1) const groups
1233 ctx.seeAndUse(obj, cg, edgeConstGroup)
1234 ctx.use(cg, obj, edgeConstGroup)
1235 }
1236 }
1237 }
1238 }
1239 case token.VAR:
1240 for _, spec := range n.Specs {
1241 v := spec.(*ast.ValueSpec)
1242 for _, name := range v.Names {
1243 T := pkg.TypesInfo.TypeOf(name)
1244 if fn != nil {
1245 ctx.seeAndUse(T, fn, edgeVarDecl)
1246 } else {
1247 // TODO(dh): we likely want to make
1248 // the type used by the variable, not
1249 // the package containing the
1250 // variable. But then we have to take
1251 // special care of blank identifiers.
1252 ctx.seeAndUse(T, nil, edgeVarDecl)
1253 }
1254 g.typ(ctx, T, nil)
1255 }
1256 }
1257 case token.TYPE:
1258 for _, spec := range n.Specs {
1259 // go/types doesn't provide a way to go from a
1260 // types.Named to the named type it was based on
1261 // (the t1 in type t2 t1). Therefore we walk the
1262 // AST and process GenDecls.
1263 //
1264 // (2.2) named types use the type they're based on
1265 v := spec.(*ast.TypeSpec)
1266 T := pkg.TypesInfo.TypeOf(v.Type)
1267 obj := pkg.TypesInfo.ObjectOf(v.Name)
1268 ctx.see(obj)
1269 ctx.see(T)
1270 ctx.use(T, obj, edgeType)
1271 g.typ(ctx, obj.Type(), nil)
1272 g.typ(ctx, T, nil)
1273
1274 if v.Assign != 0 {
1275 aliasFor := obj.(*types.TypeName).Type()
1276 // (2.3) named types use all their aliases. we can't easily track uses of aliases
1277 if isIrrelevant(aliasFor) {
1278 // We do not track the type this is an
1279 // alias for (for example builtins), so
1280 // just mark the alias used.
1281 //
1282 // FIXME(dh): what about aliases declared inside functions?
1283 ctx.use(obj, nil, edgeAlias)
1284 } else {
1285 ctx.see(aliasFor)
1286 ctx.seeAndUse(obj, aliasFor, edgeAlias)
1287 }
1288 }
1289 }
1290 }
1291 }
1292 return true
1293 })
1294 }
1295
1296 for _, m := range pkg.SSA.Members {
1297 switch m := m.(type) {
1298 case *ssa.NamedConst:
1299 // nothing to do, we collect all constants from Defs
1300 case *ssa.Global:
1301 if m.Object() != nil {
1302 ctx.see(m.Object())
1303 if g.trackExportedIdentifier(ctx, m.Object()) {
1304 // (1.3) packages use exported variables (unless in package main)
1305 ctx.use(m.Object(), nil, edgeExportedVariable)
1306 }
1307 }
1308 case *ssa.Function:
1309 mObj := owningObject(m)
1310 if mObj != nil {
1311 ctx.see(mObj)
1312 }
1313 //lint:ignore SA9003 handled implicitly
1314 if m.Name() == "init" {
1315 // (1.5) packages use init functions
1316 //
1317 // This is handled implicitly. The generated init
1318 // function has no object, thus everything in it will
1319 // be owned by the package.
1320 }
1321 // This branch catches top-level functions, not methods.
1322 if m.Object() != nil && g.trackExportedIdentifier(ctx, m.Object()) {
1323 // (1.2) packages use exported functions (unless in package main)
1324 ctx.use(mObj, nil, edgeExportedFunction)
1325 }
1326 if m.Name() == "main" && pkg.Pkg.Name() == "main" {
1327 // (1.7) packages use the main function iff in the main package
1328 ctx.use(mObj, nil, edgeMainFunction)
1329 }
1330 if pkg.Pkg.Path() == "runtime" && runtimeFuncs[m.Name()] {
1331 // (9.8) runtime functions that may be called from user code via the compiler
1332 ctx.use(mObj, nil, edgeRuntimeFunction)
1333 }
1334 if m.Syntax() != nil {
1335 doc := m.Syntax().(*ast.FuncDecl).Doc
1336 if doc != nil {
1337 for _, cmt := range doc.List {
1338 if strings.HasPrefix(cmt.Text, "//go:cgo_export_") {
1339 // (1.6) packages use functions exported to cgo
1340 ctx.use(mObj, nil, edgeCgoExported)
1341 }
1342 }
1343 }
1344 }
1345 g.function(ctx, m)
1346 case *ssa.Type:
1347 if m.Object() != nil {
1348 ctx.see(m.Object())
1349 if g.trackExportedIdentifier(ctx, m.Object()) {
1350 // (1.1) packages use exported named types (unless in package main)
1351 ctx.use(m.Object(), nil, edgeExportedType)
1352 }
1353 }
1354 g.typ(ctx, m.Type(), nil)
1355 default:
1356 panic(fmt.Sprintf("unreachable: %T", m))
1357 }
1358 }
1359
1360 if !g.wholeProgram {
1361 // When not in whole program mode we reset seenTypes after each package,
1362 // which means g.seenTypes only contains types of
1363 // interest to us. In whole program mode, we're better off
1364 // processing all interfaces at once, globally, both for
1365 // performance reasons and because in whole program mode we
1366 // actually care about all interfaces, not just the subset
1367 // that has unexported methods.
1368
1369 var ifaces []*types.Interface
1370 var notIfaces []types.Type
1371
1372 ctx.seenTypes.Iterate(func(t types.Type, _ interface{}) {
1373 switch t := t.(type) {
1374 case *types.Interface:
1375 // OPT(dh): (8.1) we only need interfaces that have unexported methods
1376 ifaces = append(ifaces, t)
1377 default:
1378 if _, ok := t.Underlying().(*types.Interface); !ok {
1379 notIfaces = append(notIfaces, t)
1380 }
1381 }
1382 })
1383
1384 // (8.0) handle interfaces
1385 for _, t := range notIfaces {
1386 ms := pkg.SSA.Prog.MethodSets.MethodSet(t)
1387 for _, iface := range ifaces {
1388 if sels, ok := g.implements(t, iface, ms); ok {
1389 for _, sel := range sels {
1390 g.useMethod(ctx, t, sel, t, edgeImplements)
1391 }
1392 }
1393 }
1394 }
1395 }
1396}
1397
1398func (g *Graph) useMethod(ctx *context, t types.Type, sel *types.Selection, by interface{}, kind edgeKind) {
1399 obj := sel.Obj()
1400 path := sel.Index()
1401 assert(obj != nil)
1402 if len(path) > 1 {
1403 base := lintdsl.Dereference(t).Underlying().(*types.Struct)
1404 for _, idx := range path[:len(path)-1] {
1405 next := base.Field(idx)
1406 // (6.3) structs use embedded fields that help implement interfaces
1407 ctx.see(base)
1408 ctx.seeAndUse(next, base, edgeProvidesMethod)
1409 base, _ = lintdsl.Dereference(next.Type()).Underlying().(*types.Struct)
1410 }
1411 }
1412 ctx.seeAndUse(obj, by, kind)
1413}
1414
1415func owningObject(fn *ssa.Function) types.Object {
1416 if fn.Object() != nil {
1417 return fn.Object()
1418 }
1419 if fn.Parent() != nil {
1420 return owningObject(fn.Parent())
1421 }
1422 return nil
1423}
1424
1425func (g *Graph) function(ctx *context, fn *ssa.Function) {
1426 if fn.Package() != nil && fn.Package() != ctx.pkg.SSA {
1427 return
1428 }
1429
1430 name := fn.RelString(nil)
1431 if _, ok := ctx.seenFns[name]; ok {
1432 return
1433 }
1434 ctx.seenFns[name] = struct{}{}
1435
1436 // (4.1) functions use all their arguments, return parameters and receivers
1437 g.signature(ctx, fn.Signature, owningObject(fn))
1438 g.instructions(ctx, fn)
1439 for _, anon := range fn.AnonFuncs {
1440 // (4.2) functions use anonymous functions defined beneath them
1441 //
1442 // This fact is expressed implicitly. Anonymous functions have
1443 // no types.Object, so their owner is the surrounding
1444 // function.
1445 g.function(ctx, anon)
1446 }
1447}
1448
1449func (g *Graph) typ(ctx *context, t types.Type, parent types.Type) {
1450 if g.wholeProgram {
1451 g.mu.Lock()
1452 }
1453 if ctx.seenTypes.At(t) != nil {
1454 if g.wholeProgram {
1455 g.mu.Unlock()
1456 }
1457 return
1458 }
1459 if g.wholeProgram {
1460 g.mu.Unlock()
1461 }
1462 if t, ok := t.(*types.Named); ok && t.Obj().Pkg() != nil {
1463 if t.Obj().Pkg() != ctx.pkg.Pkg {
1464 return
1465 }
1466 }
1467
1468 if g.wholeProgram {
1469 g.mu.Lock()
1470 }
1471 ctx.seenTypes.Set(t, struct{}{})
1472 if g.wholeProgram {
1473 g.mu.Unlock()
1474 }
1475 if isIrrelevant(t) {
1476 return
1477 }
1478
1479 ctx.see(t)
1480 switch t := t.(type) {
1481 case *types.Struct:
1482 for i := 0; i < t.NumFields(); i++ {
1483 ctx.see(t.Field(i))
1484 if t.Field(i).Exported() {
1485 // (6.2) structs use exported fields
1486 ctx.use(t.Field(i), t, edgeExportedField)
1487 } else if t.Field(i).Name() == "_" {
1488 ctx.use(t.Field(i), t, edgeBlankField)
1489 } else if isNoCopyType(t.Field(i).Type()) {
1490 // (6.1) structs use fields of type NoCopy sentinel
1491 ctx.use(t.Field(i), t, edgeNoCopySentinel)
1492 } else if parent == nil {
1493 // (11.1) anonymous struct types use all their fields.
1494 ctx.use(t.Field(i), t, edgeAnonymousStruct)
1495 }
1496 if t.Field(i).Anonymous() {
1497 // (e3) exported identifiers aren't automatically used.
1498 if !g.wholeProgram {
1499 // does the embedded field contribute exported methods to the method set?
1500 T := t.Field(i).Type()
1501 if _, ok := T.Underlying().(*types.Pointer); !ok {
1502 // An embedded field is addressable, so check
1503 // the pointer type to get the full method set
1504 T = types.NewPointer(T)
1505 }
1506 ms := ctx.pkg.SSA.Prog.MethodSets.MethodSet(T)
1507 for j := 0; j < ms.Len(); j++ {
1508 if ms.At(j).Obj().Exported() {
1509 // (6.4) structs use embedded fields that have exported methods (recursively)
1510 ctx.use(t.Field(i), t, edgeExtendsExportedMethodSet)
1511 break
1512 }
1513 }
1514 }
1515
1516 seen := map[*types.Struct]struct{}{}
1517 var hasExportedField func(t types.Type) bool
1518 hasExportedField = func(T types.Type) bool {
1519 t, ok := lintdsl.Dereference(T).Underlying().(*types.Struct)
1520 if !ok {
1521 return false
1522 }
1523 if _, ok := seen[t]; ok {
1524 return false
1525 }
1526 seen[t] = struct{}{}
1527 for i := 0; i < t.NumFields(); i++ {
1528 field := t.Field(i)
1529 if field.Exported() {
1530 return true
1531 }
1532 if field.Embedded() && hasExportedField(field.Type()) {
1533 return true
1534 }
1535 }
1536 return false
1537 }
1538 // does the embedded field contribute exported fields?
1539 if hasExportedField(t.Field(i).Type()) {
1540 // (6.5) structs use embedded structs that have exported fields (recursively)
1541 ctx.use(t.Field(i), t, edgeExtendsExportedFields)
1542 }
1543
1544 }
1545 g.variable(ctx, t.Field(i))
1546 }
1547 case *types.Basic:
1548 // Nothing to do
1549 case *types.Named:
1550 // (9.3) types use their underlying and element types
1551 ctx.seeAndUse(t.Underlying(), t, edgeUnderlyingType)
1552 ctx.seeAndUse(t.Obj(), t, edgeTypeName)
1553 ctx.seeAndUse(t, t.Obj(), edgeNamedType)
1554
1555 // (2.4) named types use the pointer type
1556 if _, ok := t.Underlying().(*types.Interface); !ok && t.NumMethods() > 0 {
1557 ctx.seeAndUse(types.NewPointer(t), t, edgePointerType)
1558 }
1559
1560 for i := 0; i < t.NumMethods(); i++ {
1561 ctx.see(t.Method(i))
1562 // don't use trackExportedIdentifier here, we care about
1563 // all exported methods, even in package main or in tests.
1564 if t.Method(i).Exported() && !g.wholeProgram {
1565 // (2.1) named types use exported methods
1566 ctx.use(t.Method(i), t, edgeExportedMethod)
1567 }
1568 g.function(ctx, ctx.pkg.SSA.Prog.FuncValue(t.Method(i)))
1569 }
1570
1571 g.typ(ctx, t.Underlying(), t)
1572 case *types.Slice:
1573 // (9.3) types use their underlying and element types
1574 ctx.seeAndUse(t.Elem(), t, edgeElementType)
1575 g.typ(ctx, t.Elem(), nil)
1576 case *types.Map:
1577 // (9.3) types use their underlying and element types
1578 ctx.seeAndUse(t.Elem(), t, edgeElementType)
1579 // (9.3) types use their underlying and element types
1580 ctx.seeAndUse(t.Key(), t, edgeKeyType)
1581 g.typ(ctx, t.Elem(), nil)
1582 g.typ(ctx, t.Key(), nil)
1583 case *types.Signature:
1584 g.signature(ctx, t, nil)
1585 case *types.Interface:
1586 for i := 0; i < t.NumMethods(); i++ {
1587 m := t.Method(i)
1588 // (8.3) All interface methods are marked as used
1589 ctx.seeAndUse(m, t, edgeInterfaceMethod)
1590 ctx.seeAndUse(m.Type().(*types.Signature), m, edgeSignature)
1591 g.signature(ctx, m.Type().(*types.Signature), nil)
1592 }
1593 for i := 0; i < t.NumEmbeddeds(); i++ {
1594 tt := t.EmbeddedType(i)
1595 // (8.4) All embedded interfaces are marked as used
1596 ctx.seeAndUse(tt, t, edgeEmbeddedInterface)
1597 }
1598 case *types.Array:
1599 // (9.3) types use their underlying and element types
1600 ctx.seeAndUse(t.Elem(), t, edgeElementType)
1601 g.typ(ctx, t.Elem(), nil)
1602 case *types.Pointer:
1603 // (9.3) types use their underlying and element types
1604 ctx.seeAndUse(t.Elem(), t, edgeElementType)
1605 g.typ(ctx, t.Elem(), nil)
1606 case *types.Chan:
1607 // (9.3) types use their underlying and element types
1608 ctx.seeAndUse(t.Elem(), t, edgeElementType)
1609 g.typ(ctx, t.Elem(), nil)
1610 case *types.Tuple:
1611 for i := 0; i < t.Len(); i++ {
1612 // (9.3) types use their underlying and element types
1613 ctx.seeAndUse(t.At(i).Type(), t, edgeTupleElement|edgeType)
1614 g.typ(ctx, t.At(i).Type(), nil)
1615 }
1616 default:
1617 panic(fmt.Sprintf("unreachable: %T", t))
1618 }
1619}
1620
1621func (g *Graph) variable(ctx *context, v *types.Var) {
1622 // (9.2) variables use their types
1623 ctx.seeAndUse(v.Type(), v, edgeType)
1624 g.typ(ctx, v.Type(), nil)
1625}
1626
1627func (g *Graph) signature(ctx *context, sig *types.Signature, fn types.Object) {
1628 var user interface{} = fn
1629 if fn == nil {
1630 user = sig
1631 ctx.see(sig)
1632 }
1633 if sig.Recv() != nil {
1634 ctx.seeAndUse(sig.Recv().Type(), user, edgeReceiver|edgeType)
1635 g.typ(ctx, sig.Recv().Type(), nil)
1636 }
1637 for i := 0; i < sig.Params().Len(); i++ {
1638 param := sig.Params().At(i)
1639 ctx.seeAndUse(param.Type(), user, edgeFunctionArgument|edgeType)
1640 g.typ(ctx, param.Type(), nil)
1641 }
1642 for i := 0; i < sig.Results().Len(); i++ {
1643 param := sig.Results().At(i)
1644 ctx.seeAndUse(param.Type(), user, edgeFunctionResult|edgeType)
1645 g.typ(ctx, param.Type(), nil)
1646 }
1647}
1648
1649func (g *Graph) instructions(ctx *context, fn *ssa.Function) {
1650 fnObj := owningObject(fn)
1651 for _, b := range fn.Blocks {
1652 for _, instr := range b.Instrs {
1653 ops := instr.Operands(nil)
1654 switch instr.(type) {
1655 case *ssa.Store:
1656 // (9.7) variable _reads_ use variables, writes do not
1657 ops = ops[1:]
1658 case *ssa.DebugRef:
1659 ops = nil
1660 }
1661 for _, arg := range ops {
1662 walkPhi(*arg, func(v ssa.Value) {
1663 switch v := v.(type) {
1664 case *ssa.Function:
1665 // (4.3) functions use closures and bound methods.
1666 // (4.5) functions use functions they call
1667 // (9.5) instructions use their operands
1668 // (4.4) functions use functions they return. we assume that someone else will call the returned function
1669 if owningObject(v) != nil {
1670 ctx.seeAndUse(owningObject(v), fnObj, edgeInstructionOperand)
1671 }
1672 g.function(ctx, v)
1673 case *ssa.Const:
1674 // (9.6) instructions use their operands' types
1675 ctx.seeAndUse(v.Type(), fnObj, edgeType)
1676 g.typ(ctx, v.Type(), nil)
1677 case *ssa.Global:
1678 if v.Object() != nil {
1679 // (9.5) instructions use their operands
1680 ctx.seeAndUse(v.Object(), fnObj, edgeInstructionOperand)
1681 }
1682 }
1683 })
1684 }
1685 if v, ok := instr.(ssa.Value); ok {
1686 if _, ok := v.(*ssa.Range); !ok {
1687 // See https://github.com/golang/go/issues/19670
1688
1689 // (4.8) instructions use their types
1690 // (9.4) conversions use the type they convert to
1691 ctx.seeAndUse(v.Type(), fnObj, edgeType)
1692 g.typ(ctx, v.Type(), nil)
1693 }
1694 }
1695 switch instr := instr.(type) {
1696 case *ssa.Field:
1697 st := instr.X.Type().Underlying().(*types.Struct)
1698 field := st.Field(instr.Field)
1699 // (4.7) functions use fields they access
1700 ctx.seeAndUse(field, fnObj, edgeFieldAccess)
1701 case *ssa.FieldAddr:
1702 st := lintdsl.Dereference(instr.X.Type()).Underlying().(*types.Struct)
1703 field := st.Field(instr.Field)
1704 // (4.7) functions use fields they access
1705 ctx.seeAndUse(field, fnObj, edgeFieldAccess)
1706 case *ssa.Store:
1707 // nothing to do, handled generically by operands
1708 case *ssa.Call:
1709 c := instr.Common()
1710 if !c.IsInvoke() {
1711 // handled generically as an instruction operand
1712
1713 if g.wholeProgram {
1714 // (e3) special case known reflection-based method callers
1715 switch lintdsl.CallName(c) {
1716 case "net/rpc.Register", "net/rpc.RegisterName", "(*net/rpc.Server).Register", "(*net/rpc.Server).RegisterName":
1717 var arg ssa.Value
1718 switch lintdsl.CallName(c) {
1719 case "net/rpc.Register":
1720 arg = c.Args[0]
1721 case "net/rpc.RegisterName":
1722 arg = c.Args[1]
1723 case "(*net/rpc.Server).Register":
1724 arg = c.Args[1]
1725 case "(*net/rpc.Server).RegisterName":
1726 arg = c.Args[2]
1727 }
1728 walkPhi(arg, func(v ssa.Value) {
1729 if v, ok := v.(*ssa.MakeInterface); ok {
1730 walkPhi(v.X, func(vv ssa.Value) {
1731 ms := ctx.pkg.SSA.Prog.MethodSets.MethodSet(vv.Type())
1732 for i := 0; i < ms.Len(); i++ {
1733 if ms.At(i).Obj().Exported() {
1734 g.useMethod(ctx, vv.Type(), ms.At(i), fnObj, edgeNetRPCRegister)
1735 }
1736 }
1737 })
1738 }
1739 })
1740 }
1741 }
1742 } else {
1743 // (4.5) functions use functions/interface methods they call
1744 ctx.seeAndUse(c.Method, fnObj, edgeInterfaceCall)
1745 }
1746 case *ssa.Return:
1747 // nothing to do, handled generically by operands
1748 case *ssa.ChangeType:
1749 // conversion type handled generically
1750
1751 s1, ok1 := lintdsl.Dereference(instr.Type()).Underlying().(*types.Struct)
1752 s2, ok2 := lintdsl.Dereference(instr.X.Type()).Underlying().(*types.Struct)
1753 if ok1 && ok2 {
1754 // Converting between two structs. The fields are
1755 // relevant for the conversion, but only if the
1756 // fields are also used outside of the conversion.
1757 // Mark fields as used by each other.
1758
1759 assert(s1.NumFields() == s2.NumFields())
1760 for i := 0; i < s1.NumFields(); i++ {
1761 ctx.see(s1.Field(i))
1762 ctx.see(s2.Field(i))
1763 // (5.1) when converting between two equivalent structs, the fields in
1764 // either struct use each other. the fields are relevant for the
1765 // conversion, but only if the fields are also accessed outside the
1766 // conversion.
1767 ctx.seeAndUse(s1.Field(i), s2.Field(i), edgeStructConversion)
1768 ctx.seeAndUse(s2.Field(i), s1.Field(i), edgeStructConversion)
1769 }
1770 }
1771 case *ssa.MakeInterface:
1772 // nothing to do, handled generically by operands
1773 case *ssa.Slice:
1774 // nothing to do, handled generically by operands
1775 case *ssa.RunDefers:
1776 // nothing to do, the deferred functions are already marked use by defering them.
1777 case *ssa.Convert:
1778 // to unsafe.Pointer
1779 if typ, ok := instr.Type().(*types.Basic); ok && typ.Kind() == types.UnsafePointer {
1780 if ptr, ok := instr.X.Type().Underlying().(*types.Pointer); ok {
1781 if st, ok := ptr.Elem().Underlying().(*types.Struct); ok {
1782 for i := 0; i < st.NumFields(); i++ {
1783 // (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
1784 ctx.seeAndUse(st.Field(i), fnObj, edgeUnsafeConversion)
1785 }
1786 }
1787 }
1788 }
1789 // from unsafe.Pointer
1790 if typ, ok := instr.X.Type().(*types.Basic); ok && typ.Kind() == types.UnsafePointer {
1791 if ptr, ok := instr.Type().Underlying().(*types.Pointer); ok {
1792 if st, ok := ptr.Elem().Underlying().(*types.Struct); ok {
1793 for i := 0; i < st.NumFields(); i++ {
1794 // (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
1795 ctx.seeAndUse(st.Field(i), fnObj, edgeUnsafeConversion)
1796 }
1797 }
1798 }
1799 }
1800 case *ssa.TypeAssert:
1801 // nothing to do, handled generically by instruction
1802 // type (possibly a tuple, which contains the asserted
1803 // to type). redundantly handled by the type of
1804 // ssa.Extract, too
1805 case *ssa.MakeClosure:
1806 // nothing to do, handled generically by operands
1807 case *ssa.Alloc:
1808 // nothing to do
1809 case *ssa.UnOp:
1810 // nothing to do
1811 case *ssa.BinOp:
1812 // nothing to do
1813 case *ssa.If:
1814 // nothing to do
1815 case *ssa.Jump:
1816 // nothing to do
1817 case *ssa.IndexAddr:
1818 // nothing to do
1819 case *ssa.Extract:
1820 // nothing to do
1821 case *ssa.Panic:
1822 // nothing to do
1823 case *ssa.DebugRef:
1824 // nothing to do
1825 case *ssa.BlankStore:
1826 // nothing to do
1827 case *ssa.Phi:
1828 // nothing to do
1829 case *ssa.MakeMap:
1830 // nothing to do
1831 case *ssa.MapUpdate:
1832 // nothing to do
1833 case *ssa.Lookup:
1834 // nothing to do
1835 case *ssa.MakeSlice:
1836 // nothing to do
1837 case *ssa.Send:
1838 // nothing to do
1839 case *ssa.MakeChan:
1840 // nothing to do
1841 case *ssa.Range:
1842 // nothing to do
1843 case *ssa.Next:
1844 // nothing to do
1845 case *ssa.Index:
1846 // nothing to do
1847 case *ssa.Select:
1848 // nothing to do
1849 case *ssa.ChangeInterface:
1850 // nothing to do
1851 case *ssa.Go:
1852 // nothing to do, handled generically by operands
1853 case *ssa.Defer:
1854 // nothing to do, handled generically by operands
1855 default:
1856 panic(fmt.Sprintf("unreachable: %T", instr))
1857 }
1858 }
1859 }
1860}
1861
1862// isNoCopyType reports whether a type represents the NoCopy sentinel
1863// type. The NoCopy type is a named struct with no fields and exactly
1864// one method `func Lock()` that is empty.
1865//
1866// FIXME(dh): currently we're not checking that the function body is
1867// empty.
1868func isNoCopyType(typ types.Type) bool {
1869 st, ok := typ.Underlying().(*types.Struct)
1870 if !ok {
1871 return false
1872 }
1873 if st.NumFields() != 0 {
1874 return false
1875 }
1876
1877 named, ok := typ.(*types.Named)
1878 if !ok {
1879 return false
1880 }
1881 if named.NumMethods() != 1 {
1882 return false
1883 }
1884 meth := named.Method(0)
1885 if meth.Name() != "Lock" {
1886 return false
1887 }
1888 sig := meth.Type().(*types.Signature)
1889 if sig.Params().Len() != 0 || sig.Results().Len() != 0 {
1890 return false
1891 }
1892 return true
1893}
1894
1895func walkPhi(v ssa.Value, fn func(v ssa.Value)) {
1896 phi, ok := v.(*ssa.Phi)
1897 if !ok {
1898 fn(v)
1899 return
1900 }
1901
1902 seen := map[ssa.Value]struct{}{}
1903 var impl func(v *ssa.Phi)
1904 impl = func(v *ssa.Phi) {
1905 if _, ok := seen[v]; ok {
1906 return
1907 }
1908 seen[v] = struct{}{}
1909 for _, e := range v.Edges {
1910 if ev, ok := e.(*ssa.Phi); ok {
1911 impl(ev)
1912 } else {
1913 fn(e)
1914 }
1915 }
1916 }
1917 impl(phi)
1918}
1919
1920func interfacesFromExportData(pkg *types.Package) []*types.Interface {
1921 var out []*types.Interface
1922 scope := pkg.Scope()
1923 for _, name := range scope.Names() {
1924 obj := scope.Lookup(name)
1925 out = append(out, interfacesFromObject(obj)...)
1926 }
1927 return out
1928}
1929
1930func interfacesFromObject(obj types.Object) []*types.Interface {
1931 var out []*types.Interface
1932 switch obj := obj.(type) {
1933 case *types.Func:
1934 sig := obj.Type().(*types.Signature)
1935 for i := 0; i < sig.Results().Len(); i++ {
1936 out = append(out, interfacesFromObject(sig.Results().At(i))...)
1937 }
1938 for i := 0; i < sig.Params().Len(); i++ {
1939 out = append(out, interfacesFromObject(sig.Params().At(i))...)
1940 }
1941 case *types.TypeName:
1942 if named, ok := obj.Type().(*types.Named); ok {
1943 for i := 0; i < named.NumMethods(); i++ {
1944 out = append(out, interfacesFromObject(named.Method(i))...)
1945 }
1946
1947 if iface, ok := named.Underlying().(*types.Interface); ok {
1948 out = append(out, iface)
1949 }
1950 }
1951 case *types.Var:
1952 // No call to Underlying here. We want unnamed interfaces
1953 // only. Named interfaces are gotten directly from the
1954 // package's scope.
1955 if iface, ok := obj.Type().(*types.Interface); ok {
1956 out = append(out, iface)
1957 }
1958 case *types.Const:
1959 case *types.Builtin:
1960 default:
1961 panic(fmt.Sprintf("unhandled type: %T", obj))
1962 }
1963 return out
1964}
© 2015 Mike Crute