.config/coc/extensions/coc-go-data/tools/pkg/mod/honnef.co/go/tools@v0.0.1-2020.1.5/unused/unused.go

   1 package unused
   2
   3 import (
   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/code"
  15         "honnef.co/go/tools/go/types/typeutil"
  16         "honnef.co/go/tools/internal/passes/buildir"
  17         "honnef.co/go/tools/ir"
  18         "honnef.co/go/tools/lint"
  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 accommodate 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
 150 func assert(b bool) {
 151         if !b {
 152                 panic("failed assertion")
 153         }
 154 }
 155
 156 func 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.
 178 var 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
 416 type pkg struct {
 417         Fset       *token.FileSet
 418         Files      []*ast.File
 419         Pkg        *types.Package
 420         TypesInfo  *types.Info
 421         TypesSizes types.Sizes
 422         IR         *ir.Package
 423         SrcFuncs   []*ir.Function
 424 }
 425
 426 type 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
 436 func 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
 444 func (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{buildir.Analyzer},
 454         }
 455 }
 456
 457 func (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         irpkg := pass.ResultOf[buildir.Analyzer].(*buildir.IR)
 481         pkg := &pkg{
 482                 Fset:       pass.Fset,
 483                 Files:      pass.Files,
 484                 Pkg:        pass.Pkg,
 485                 TypesInfo:  pass.TypesInfo,
 486                 TypesSizes: pass.TypesSizes,
 487                 IR:         irpkg.Pkg,
 488                 SrcFuncs:   irpkg.SrcFuncs,
 489         }
 490
 491         c.processPkg(c.graph, pkg)
 492
 493         return nil, nil
 494 }
 495
 496 func (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
 521 func (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
 535 func (c *Checker) debugf(f string, v ...interface{}) {
 536         if c.Debug != nil {
 537                 fmt.Fprintf(c.Debug, f, v...)
 538         }
 539 }
 540
 541 func (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
 569 func (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                 for _, v := range c.graph.Nodes {
 642                         debugNode(v)
 643                 }
 644                 c.graph.TypeNodes.Iterate(func(key types.Type, value interface{}) {
 645                         debugNode(value.(*Node))
 646                 })
 647
 648                 c.debugf("}\n")
 649         }
 650
 651         c.graph.color(c.graph.Root)
 652         // if a node is unused, don't report any of the node's
 653         // children as unused. for example, if a function is unused,
 654         // don't flag its receiver. if a named type is unused, don't
 655         // flag its methods.
 656
 657         for _, v := range c.graph.Nodes {
 658                 c.graph.quieten(v)
 659         }
 660         c.graph.TypeNodes.Iterate(func(_ types.Type, value interface{}) {
 661                 c.graph.quieten(value.(*Node))
 662         })
 663
 664         report := func(node *Node) {
 665                 if node.seen {
 666                         return
 667                 }
 668                 if node.quiet {
 669                         c.debugf("n%d [color=purple];\n", node.id)
 670                         return
 671                 }
 672
 673                 c.debugf("n%d [color=red];\n", node.id)
 674                 switch obj := node.obj.(type) {
 675                 case *types.Var:
 676                         // don't report unnamed variables (interface embedding)
 677                         if obj.Name() != "" || obj.IsField() {
 678                                 out = append(out, obj)
 679                         }
 680                         return
 681                 case types.Object:
 682                         if obj.Name() != "_" {
 683                                 out = append(out, obj)
 684                         }
 685                         return
 686                 }
 687                 c.debugf("n%d [color=gray];\n", node.id)
 688         }
 689         for _, v := range c.graph.Nodes {
 690                 report(v)
 691         }
 692         c.graph.TypeNodes.Iterate(func(_ types.Type, value interface{}) {
 693                 report(value.(*Node))
 694         })
 695
 696         return out
 697 }
 698
 699 func (c *Checker) processPkg(graph *Graph, pkg *pkg) {
 700         if pkg.Pkg.Path() == "unsafe" {
 701                 return
 702         }
 703         graph.entry(pkg)
 704 }
 705
 706 func objNodeKeyFor(fset *token.FileSet, obj types.Object) objNodeKey {
 707         var kind objType
 708         switch obj.(type) {
 709         case *types.PkgName:
 710                 kind = otPkgName
 711         case *types.Const:
 712                 kind = otConst
 713         case *types.TypeName:
 714                 kind = otTypeName
 715         case *types.Var:
 716                 kind = otVar
 717         case *types.Func:
 718                 kind = otFunc
 719         case *types.Label:
 720                 kind = otLabel
 721         case *types.Builtin:
 722                 kind = otBuiltin
 723         case *types.Nil:
 724                 kind = otNil
 725         default:
 726                 panic(fmt.Sprintf("unreachable: %T", obj))
 727         }
 728
 729         position := fset.PositionFor(obj.Pos(), false)
 730         position.Column = 0
 731         position.Offset = 0
 732         return objNodeKey{
 733                 position: position,
 734                 kind:     kind,
 735                 name:     obj.Name(),
 736         }
 737 }
 738
 739 type objType uint8
 740
 741 const (
 742         otPkgName objType = iota
 743         otConst
 744         otTypeName
 745         otVar
 746         otFunc
 747         otLabel
 748         otBuiltin
 749         otNil
 750 )
 751
 752 // An objNodeKey describes a types.Object node in the graph.
 753 //
 754 // Due to test variants we may end up with multiple instances of the
 755 // same object, which is why we have to deduplicate based on their
 756 // source position. And because export data lacks column information,
 757 // we also have to incorporate the object's string representation in
 758 // the key.
 759 //
 760 // Previously we used the object's full string representation
 761 // (types.ObjectString), but that causes a significant amount of
 762 // allocations. Currently we're using the object's type and name, in
 763 // the hope that it is impossible for two objects to have the same
 764 // type, name and file position.
 765 type objNodeKey struct {
 766         position token.Position
 767         kind     objType
 768         name     string
 769 }
 770
 771 type Graph struct {
 772         // accessed atomically
 773         nodeOffset uint64
 774
 775         // Safe for concurrent use
 776         fset      *token.FileSet
 777         Root      *Node
 778         seenTypes typeutil.Map
 779
 780         // read-only
 781         wholeProgram bool
 782
 783         // need synchronisation
 784         mu        sync.Mutex
 785         TypeNodes typeutil.Map
 786         Nodes     map[interface{}]*Node
 787         objNodes  map[objNodeKey]*Node
 788 }
 789
 790 type context struct {
 791         g           *Graph
 792         pkg         *pkg
 793         seenFns     map[string]struct{}
 794         seenTypes   *typeutil.Map
 795         nodeCounter uint64
 796 }
 797
 798 func NewGraph() *Graph {
 799         g := &Graph{
 800                 Nodes:    map[interface{}]*Node{},
 801                 objNodes: map[objNodeKey]*Node{},
 802         }
 803         g.Root = g.newNode(&context{}, nil)
 804         return g
 805 }
 806
 807 func (g *Graph) color(root *Node) {
 808         if root.seen {
 809                 return
 810         }
 811         root.seen = true
 812         for _, e := range root.used {
 813                 g.color(e.node)
 814         }
 815 }
 816
 817 type ConstGroup struct {
 818         // give the struct a size to get unique pointers
 819         _ byte
 820 }
 821
 822 func (ConstGroup) String() string { return "const group" }
 823
 824 type edge struct {
 825         node *Node
 826         kind edgeKind
 827 }
 828
 829 type Node struct {
 830         obj interface{}
 831         id  uint64
 832
 833         mu   sync.Mutex
 834         used []edge
 835
 836         // set during final graph walk if node is reachable
 837         seen bool
 838         // a parent node (e.g. the struct type containing a field) is
 839         // already unused, don't report children
 840         quiet bool
 841 }
 842
 843 func (g *Graph) nodeMaybe(obj types.Object) (*Node, bool) {
 844         g.mu.Lock()
 845         defer g.mu.Unlock()
 846         if node, ok := g.Nodes[obj]; ok {
 847                 return node, true
 848         }
 849         return nil, false
 850 }
 851
 852 func (g *Graph) node(ctx *context, obj interface{}) (node *Node, new bool) {
 853         g.mu.Lock()
 854         defer g.mu.Unlock()
 855         switch obj := obj.(type) {
 856         case types.Type:
 857                 if v := g.TypeNodes.At(obj); v != nil {
 858                         return v.(*Node), false
 859                 }
 860                 node := g.newNode(ctx, obj)
 861                 g.TypeNodes.Set(obj, node)
 862                 return node, true
 863         case types.Object:
 864                 if node, ok := g.Nodes[obj]; ok {
 865                         return node, false
 866                 }
 867
 868                 key := objNodeKeyFor(g.fset, obj)
 869                 if onode, ok := g.objNodes[key]; ok {
 870                         return onode, false
 871                 }
 872
 873                 node = g.newNode(ctx, obj)
 874                 g.Nodes[obj] = node
 875                 g.objNodes[key] = node
 876                 return node, true
 877         default:
 878                 if node, ok := g.Nodes[obj]; ok {
 879                         return node, false
 880                 }
 881
 882                 node = g.newNode(ctx, obj)
 883                 g.Nodes[obj] = node
 884                 return node, true
 885         }
 886 }
 887
 888 func (g *Graph) newNode(ctx *context, obj interface{}) *Node {
 889         ctx.nodeCounter++
 890         return &Node{
 891                 obj: obj,
 892                 id:  ctx.nodeCounter,
 893         }
 894 }
 895
 896 func (n *Node) use(node *Node, kind edgeKind) {
 897         n.mu.Lock()
 898         defer n.mu.Unlock()
 899         assert(node != nil)
 900         n.used = append(n.used, edge{node: node, kind: kind})
 901 }
 902
 903 // isIrrelevant reports whether an object's presence in the graph is
 904 // of any relevance. A lot of objects will never have outgoing edges,
 905 // nor meaningful incoming ones. Examples are basic types and empty
 906 // signatures, among many others.
 907 //
 908 // Dropping these objects should have no effect on correctness, but
 909 // may improve performance. It also helps with debugging, as it
 910 // greatly reduces the size of the graph.
 911 func isIrrelevant(obj interface{}) bool {
 912         if obj, ok := obj.(types.Object); ok {
 913                 switch obj := obj.(type) {
 914                 case *types.Var:
 915                         if obj.IsField() {
 916                                 // We need to track package fields
 917                                 return false
 918                         }
 919                         if obj.Pkg() != nil && obj.Parent() == obj.Pkg().Scope() {
 920                                 // We need to track package-level variables
 921                                 return false
 922                         }
 923                         return isIrrelevant(obj.Type())
 924                 default:
 925                         return false
 926                 }
 927         }
 928         if T, ok := obj.(types.Type); ok {
 929                 switch T := T.(type) {
 930                 case *types.Array:
 931                         return isIrrelevant(T.Elem())
 932                 case *types.Slice:
 933                         return isIrrelevant(T.Elem())
 934                 case *types.Basic:
 935                         return true
 936                 case *types.Tuple:
 937                         for i := 0; i < T.Len(); i++ {
 938                                 if !isIrrelevant(T.At(i).Type()) {
 939                                         return false
 940                                 }
 941                         }
 942                         return true
 943                 case *types.Signature:
 944                         if T.Recv() != nil {
 945                                 return false
 946                         }
 947                         for i := 0; i < T.Params().Len(); i++ {
 948                                 if !isIrrelevant(T.Params().At(i)) {
 949                                         return false
 950                                 }
 951                         }
 952                         for i := 0; i < T.Results().Len(); i++ {
 953                                 if !isIrrelevant(T.Results().At(i)) {
 954                                         return false
 955                                 }
 956                         }
 957                         return true
 958                 case *types.Interface:
 959                         return T.NumMethods() == 0 && T.NumEmbeddeds() == 0
 960                 case *types.Pointer:
 961                         return isIrrelevant(T.Elem())
 962                 case *types.Map:
 963                         return isIrrelevant(T.Key()) && isIrrelevant(T.Elem())
 964                 case *types.Struct:
 965                         return T.NumFields() == 0
 966                 case *types.Chan:
 967                         return isIrrelevant(T.Elem())
 968                 default:
 969                         return false
 970                 }
 971         }
 972         return false
 973 }
 974
 975 func (ctx *context) see(obj interface{}) *Node {
 976         if isIrrelevant(obj) {
 977                 return nil
 978         }
 979
 980         assert(obj != nil)
 981         // add new node to graph
 982         node, _ := ctx.g.node(ctx, obj)
 983         return node
 984 }
 985
 986 func (ctx *context) use(used, by interface{}, kind edgeKind) {
 987         if isIrrelevant(used) {
 988                 return
 989         }
 990
 991         assert(used != nil)
 992         if obj, ok := by.(types.Object); ok && obj.Pkg() != nil {
 993                 if !ctx.g.wholeProgram && obj.Pkg() != ctx.pkg.Pkg {
 994                         return
 995                 }
 996         }
 997         usedNode, new := ctx.g.node(ctx, used)
 998         assert(!new)
 999         if by == nil {
1000                 ctx.g.Root.use(usedNode, kind)
1001         } else {
1002                 byNode, new := ctx.g.node(ctx, by)
1003                 assert(!new)
1004                 byNode.use(usedNode, kind)
1005         }
1006 }
1007
1008 func (ctx *context) seeAndUse(used, by interface{}, kind edgeKind) *Node {
1009         node := ctx.see(used)
1010         ctx.use(used, by, kind)
1011         return node
1012 }
1013
1014 // trackExportedIdentifier reports whether obj should be considered
1015 // used due to being exported, checking various conditions that affect
1016 // the decision.
1017 func (g *Graph) trackExportedIdentifier(ctx *context, obj types.Object) bool {
1018         if !obj.Exported() {
1019                 // object isn't exported, the question is moot
1020                 return false
1021         }
1022         path := g.fset.Position(obj.Pos()).Filename
1023         if g.wholeProgram {
1024                 // Example functions without "Output:" comments aren't being
1025                 // run and thus don't show up in the graph.
1026                 if strings.HasSuffix(path, "_test.go") && strings.HasPrefix(obj.Name(), "Example") {
1027                         return true
1028                 }
1029                 // whole program mode tracks exported identifiers accurately
1030                 return false
1031         }
1032
1033         if ctx.pkg.Pkg.Name() == "main" && !strings.HasSuffix(path, "_test.go") {
1034                 // exported identifiers in package main can't be imported.
1035                 // However, test functions can be called, and xtest packages
1036                 // even have access to exported identifiers.
1037                 return false
1038         }
1039
1040         if strings.HasSuffix(path, "_test.go") {
1041                 if strings.HasPrefix(obj.Name(), "Test") ||
1042                         strings.HasPrefix(obj.Name(), "Benchmark") ||
1043                         strings.HasPrefix(obj.Name(), "Example") {
1044                         return true
1045                 }
1046                 return false
1047         }
1048
1049         return true
1050 }
1051
1052 func (g *Graph) entry(pkg *pkg) {
1053         no := atomic.AddUint64(&g.nodeOffset, 1)
1054         ctx := &context{
1055                 g:           g,
1056                 pkg:         pkg,
1057                 nodeCounter: no * 1e9,
1058                 seenFns:     map[string]struct{}{},
1059         }
1060         if g.wholeProgram {
1061                 ctx.seenTypes = &g.seenTypes
1062         } else {
1063                 ctx.seenTypes = &typeutil.Map{}
1064         }
1065
1066         scopes := map[*types.Scope]*ir.Function{}
1067         for _, fn := range pkg.SrcFuncs {
1068                 if fn.Object() != nil {
1069                         scope := fn.Object().(*types.Func).Scope()
1070                         scopes[scope] = fn
1071                 }
1072         }
1073
1074         for _, f := range pkg.Files {
1075                 for _, cg := range f.Comments {
1076                         for _, c := range cg.List {
1077                                 if strings.HasPrefix(c.Text, "//go:linkname ") {
1078                                         // FIXME(dh): we're looking at all comments. The
1079                                         // compiler only looks at comments in the
1080                                         // left-most column. The intention probably is to
1081                                         // only look at top-level comments.
1082
1083                                         // (1.8) packages use symbols linked via go:linkname
1084                                         fields := strings.Fields(c.Text)
1085                                         if len(fields) == 3 {
1086                                                 if m, ok := pkg.IR.Members[fields[1]]; ok {
1087                                                         var obj types.Object
1088                                                         switch m := m.(type) {
1089                                                         case *ir.Global:
1090                                                                 obj = m.Object()
1091                                                         case *ir.Function:
1092                                                                 obj = m.Object()
1093                                                         default:
1094                                                                 panic(fmt.Sprintf("unhandled type: %T", m))
1095                                                         }
1096                                                         assert(obj != nil)
1097                                                         ctx.seeAndUse(obj, nil, edgeLinkname)
1098                                                 }
1099                                         }
1100                                 }
1101                         }
1102                 }
1103         }
1104
1105         surroundingFunc := func(obj types.Object) *ir.Function {
1106                 scope := obj.Parent()
1107                 for scope != nil {
1108                         if fn := scopes[scope]; fn != nil {
1109                                 return fn
1110                         }
1111                         scope = scope.Parent()
1112                 }
1113                 return nil
1114         }
1115
1116         // IR form won't tell us about locally scoped types that aren't
1117         // being used. Walk the list of Defs to get all named types.
1118         //
1119         // IR form also won't tell us about constants; use Defs and Uses
1120         // to determine which constants exist and which are being used.
1121         for _, obj := range pkg.TypesInfo.Defs {
1122                 switch obj := obj.(type) {
1123                 case *types.TypeName:
1124                         // types are being handled by walking the AST
1125                 case *types.Const:
1126                         ctx.see(obj)
1127                         fn := surroundingFunc(obj)
1128                         if fn == nil && g.trackExportedIdentifier(ctx, obj) {
1129                                 // (1.4) packages use exported constants (unless in package main)
1130                                 ctx.use(obj, nil, edgeExportedConstant)
1131                         }
1132                         g.typ(ctx, obj.Type(), nil)
1133                         ctx.seeAndUse(obj.Type(), obj, edgeType)
1134                 }
1135         }
1136
1137         // Find constants being used inside functions, find sinks in tests
1138         for _, fn := range pkg.SrcFuncs {
1139                 if fn.Object() != nil {
1140                         ctx.see(fn.Object())
1141                 }
1142                 node := fn.Source()
1143                 if node == nil {
1144                         continue
1145                 }
1146                 ast.Inspect(node, func(node ast.Node) bool {
1147                         switch node := node.(type) {
1148                         case *ast.Ident:
1149                                 obj, ok := pkg.TypesInfo.Uses[node]
1150                                 if !ok {
1151                                         return true
1152                                 }
1153                                 switch obj := obj.(type) {
1154                                 case *types.Const:
1155                                         ctx.seeAndUse(obj, owningObject(fn), edgeUsedConstant)
1156                                 }
1157                         case *ast.AssignStmt:
1158                                 for _, expr := range node.Lhs {
1159                                         ident, ok := expr.(*ast.Ident)
1160                                         if !ok {
1161                                                 continue
1162                                         }
1163                                         obj := pkg.TypesInfo.ObjectOf(ident)
1164                                         if obj == nil {
1165                                                 continue
1166                                         }
1167                                         path := g.fset.File(obj.Pos()).Name()
1168                                         if strings.HasSuffix(path, "_test.go") {
1169                                                 if obj.Parent() != nil && obj.Parent().Parent() != nil && obj.Parent().Parent().Parent() == nil {
1170                                                         // object's scope is the package, whose
1171                                                         // parent is the file, whose parent is nil
1172
1173                                                         // (4.9) functions use package-level variables they assign to iff in tests (sinks for benchmarks)
1174                                                         // (9.7) variable _reads_ use variables, writes do not, except in tests
1175                                                         ctx.seeAndUse(obj, owningObject(fn), edgeTestSink)
1176                                                 }
1177                                         }
1178                                 }
1179                         }
1180
1181                         return true
1182                 })
1183         }
1184         // Find constants being used in non-function contexts
1185         for _, obj := range pkg.TypesInfo.Uses {
1186                 _, ok := obj.(*types.Const)
1187                 if !ok {
1188                         continue
1189                 }
1190                 ctx.seeAndUse(obj, nil, edgeUsedConstant)
1191         }
1192
1193         var fns []*types.Func
1194         var fn *types.Func
1195         var stack []ast.Node
1196         for _, f := range pkg.Files {
1197                 ast.Inspect(f, func(n ast.Node) bool {
1198                         if n == nil {
1199                                 pop := stack[len(stack)-1]
1200                                 stack = stack[:len(stack)-1]
1201                                 if _, ok := pop.(*ast.FuncDecl); ok {
1202                                         fns = fns[:len(fns)-1]
1203                                         if len(fns) == 0 {
1204                                                 fn = nil
1205                                         } else {
1206                                                 fn = fns[len(fns)-1]
1207                                         }
1208                                 }
1209                                 return true
1210                         }
1211                         stack = append(stack, n)
1212                         switch n := n.(type) {
1213                         case *ast.FuncDecl:
1214                                 fn = pkg.TypesInfo.ObjectOf(n.Name).(*types.Func)
1215                                 fns = append(fns, fn)
1216                                 ctx.see(fn)
1217                         case *ast.GenDecl:
1218                                 switch n.Tok {
1219                                 case token.CONST:
1220                                         groups := code.GroupSpecs(pkg.Fset, n.Specs)
1221                                         for _, specs := range groups {
1222                                                 if len(specs) > 1 {
1223                                                         cg := &ConstGroup{}
1224                                                         ctx.see(cg)
1225                                                         for _, spec := range specs {
1226                                                                 for _, name := range spec.(*ast.ValueSpec).Names {
1227                                                                         obj := pkg.TypesInfo.ObjectOf(name)
1228                                                                         // (10.1) const groups
1229                                                                         ctx.seeAndUse(obj, cg, edgeConstGroup)
1230                                                                         ctx.use(cg, obj, edgeConstGroup)
1231                                                                 }
1232                                                         }
1233                                                 }
1234                                         }
1235                                 case token.VAR:
1236                                         for _, spec := range n.Specs {
1237                                                 v := spec.(*ast.ValueSpec)
1238                                                 for _, name := range v.Names {
1239                                                         T := pkg.TypesInfo.TypeOf(name)
1240                                                         if fn != nil {
1241                                                                 ctx.seeAndUse(T, fn, edgeVarDecl)
1242                                                         } else {
1243                                                                 // TODO(dh): we likely want to make
1244                                                                 // the type used by the variable, not
1245                                                                 // the package containing the
1246                                                                 // variable. But then we have to take
1247                                                                 // special care of blank identifiers.
1248                                                                 ctx.seeAndUse(T, nil, edgeVarDecl)
1249                                                         }
1250                                                         g.typ(ctx, T, nil)
1251                                                 }
1252                                         }
1253                                 case token.TYPE:
1254                                         for _, spec := range n.Specs {
1255                                                 // go/types doesn't provide a way to go from a
1256                                                 // types.Named to the named type it was based on
1257                                                 // (the t1 in type t2 t1). Therefore we walk the
1258                                                 // AST and process GenDecls.
1259                                                 //
1260                                                 // (2.2) named types use the type they're based on
1261                                                 v := spec.(*ast.TypeSpec)
1262                                                 T := pkg.TypesInfo.TypeOf(v.Type)
1263                                                 obj := pkg.TypesInfo.ObjectOf(v.Name)
1264                                                 ctx.see(obj)
1265                                                 ctx.see(T)
1266                                                 ctx.use(T, obj, edgeType)
1267                                                 g.typ(ctx, obj.Type(), nil)
1268                                                 g.typ(ctx, T, nil)
1269
1270                                                 if v.Assign != 0 {
1271                                                         aliasFor := obj.(*types.TypeName).Type()
1272                                                         // (2.3) named types use all their aliases. we can't easily track uses of aliases
1273                                                         if isIrrelevant(aliasFor) {
1274                                                                 // We do not track the type this is an
1275                                                                 // alias for (for example builtins), so
1276                                                                 // just mark the alias used.
1277                                                                 //
1278                                                                 // FIXME(dh): what about aliases declared inside functions?
1279                                                                 ctx.use(obj, nil, edgeAlias)
1280                                                         } else {
1281                                                                 ctx.see(aliasFor)
1282                                                                 ctx.seeAndUse(obj, aliasFor, edgeAlias)
1283                                                         }
1284                                                 }
1285                                         }
1286                                 }
1287                         }
1288                         return true
1289                 })
1290         }
1291
1292         for _, m := range pkg.IR.Members {
1293                 switch m := m.(type) {
1294                 case *ir.NamedConst:
1295                         // nothing to do, we collect all constants from Defs
1296                 case *ir.Global:
1297                         if m.Object() != nil {
1298                                 ctx.see(m.Object())
1299                                 if g.trackExportedIdentifier(ctx, m.Object()) {
1300                                         // (1.3) packages use exported variables (unless in package main)
1301                                         ctx.use(m.Object(), nil, edgeExportedVariable)
1302                                 }
1303                         }
1304                 case *ir.Function:
1305                         mObj := owningObject(m)
1306                         if mObj != nil {
1307                                 ctx.see(mObj)
1308                         }
1309                         //lint:ignore SA9003 handled implicitly
1310                         if m.Name() == "init" {
1311                                 // (1.5) packages use init functions
1312                                 //
1313                                 // This is handled implicitly. The generated init
1314                                 // function has no object, thus everything in it will
1315                                 // be owned by the package.
1316                         }
1317                         // This branch catches top-level functions, not methods.
1318                         if m.Object() != nil && g.trackExportedIdentifier(ctx, m.Object()) {
1319                                 // (1.2) packages use exported functions (unless in package main)
1320                                 ctx.use(mObj, nil, edgeExportedFunction)
1321                         }
1322                         if m.Name() == "main" && pkg.Pkg.Name() == "main" {
1323                                 // (1.7) packages use the main function iff in the main package
1324                                 ctx.use(mObj, nil, edgeMainFunction)
1325                         }
1326                         if pkg.Pkg.Path() == "runtime" && runtimeFuncs[m.Name()] {
1327                                 // (9.8) runtime functions that may be called from user code via the compiler
1328                                 ctx.use(mObj, nil, edgeRuntimeFunction)
1329                         }
1330                         if m.Source() != nil {
1331                                 doc := m.Source().(*ast.FuncDecl).Doc
1332                                 if doc != nil {
1333                                         for _, cmt := range doc.List {
1334                                                 if strings.HasPrefix(cmt.Text, "//go:cgo_export_") {
1335                                                         // (1.6) packages use functions exported to cgo
1336                                                         ctx.use(mObj, nil, edgeCgoExported)
1337                                                 }
1338                                         }
1339                                 }
1340                         }
1341                         g.function(ctx, m)
1342                 case *ir.Type:
1343                         if m.Object() != nil {
1344                                 ctx.see(m.Object())
1345                                 if g.trackExportedIdentifier(ctx, m.Object()) {
1346                                         // (1.1) packages use exported named types (unless in package main)
1347                                         ctx.use(m.Object(), nil, edgeExportedType)
1348                                 }
1349                         }
1350                         g.typ(ctx, m.Type(), nil)
1351                 default:
1352                         panic(fmt.Sprintf("unreachable: %T", m))
1353                 }
1354         }
1355
1356         if !g.wholeProgram {
1357                 // When not in whole program mode we reset seenTypes after each package,
1358                 // which means g.seenTypes only contains types of
1359                 // interest to us. In whole program mode, we're better off
1360                 // processing all interfaces at once, globally, both for
1361                 // performance reasons and because in whole program mode we
1362                 // actually care about all interfaces, not just the subset
1363                 // that has unexported methods.
1364
1365                 var ifaces []*types.Interface
1366                 var notIfaces []types.Type
1367
1368                 ctx.seenTypes.Iterate(func(t types.Type, _ interface{}) {
1369                         switch t := t.(type) {
1370                         case *types.Interface:
1371                                 // OPT(dh): (8.1) we only need interfaces that have unexported methods
1372                                 ifaces = append(ifaces, t)
1373                         default:
1374                                 if _, ok := t.Underlying().(*types.Interface); !ok {
1375                                         notIfaces = append(notIfaces, t)
1376                                 }
1377                         }
1378                 })
1379
1380                 // (8.0) handle interfaces
1381                 for _, t := range notIfaces {
1382                         ms := pkg.IR.Prog.MethodSets.MethodSet(t)
1383                         for _, iface := range ifaces {
1384                                 if sels, ok := g.implements(t, iface, ms); ok {
1385                                         for _, sel := range sels {
1386                                                 g.useMethod(ctx, t, sel, t, edgeImplements)
1387                                         }
1388                                 }
1389                         }
1390                 }
1391         }
1392 }
1393
1394 func (g *Graph) useMethod(ctx *context, t types.Type, sel *types.Selection, by interface{}, kind edgeKind) {
1395         obj := sel.Obj()
1396         path := sel.Index()
1397         assert(obj != nil)
1398         if len(path) > 1 {
1399                 base := code.Dereference(t).Underlying().(*types.Struct)
1400                 for _, idx := range path[:len(path)-1] {
1401                         next := base.Field(idx)
1402                         // (6.3) structs use embedded fields that help implement interfaces
1403                         ctx.see(base)
1404                         ctx.seeAndUse(next, base, edgeProvidesMethod)
1405                         base, _ = code.Dereference(next.Type()).Underlying().(*types.Struct)
1406                 }
1407         }
1408         ctx.seeAndUse(obj, by, kind)
1409 }
1410
1411 func owningObject(fn *ir.Function) types.Object {
1412         if fn.Object() != nil {
1413                 return fn.Object()
1414         }
1415         if fn.Parent() != nil {
1416                 return owningObject(fn.Parent())
1417         }
1418         return nil
1419 }
1420
1421 func (g *Graph) function(ctx *context, fn *ir.Function) {
1422         if fn.Package() != nil && fn.Package() != ctx.pkg.IR {
1423                 return
1424         }
1425
1426         name := fn.RelString(nil)
1427         if _, ok := ctx.seenFns[name]; ok {
1428                 return
1429         }
1430         ctx.seenFns[name] = struct{}{}
1431
1432         // (4.1) functions use all their arguments, return parameters and receivers
1433         g.signature(ctx, fn.Signature, owningObject(fn))
1434         g.instructions(ctx, fn)
1435         for _, anon := range fn.AnonFuncs {
1436                 // (4.2) functions use anonymous functions defined beneath them
1437                 //
1438                 // This fact is expressed implicitly. Anonymous functions have
1439                 // no types.Object, so their owner is the surrounding
1440                 // function.
1441                 g.function(ctx, anon)
1442         }
1443 }
1444
1445 func (g *Graph) typ(ctx *context, t types.Type, parent types.Type) {
1446         if g.wholeProgram {
1447                 g.mu.Lock()
1448         }
1449         if ctx.seenTypes.At(t) != nil {
1450                 if g.wholeProgram {
1451                         g.mu.Unlock()
1452                 }
1453                 return
1454         }
1455         if g.wholeProgram {
1456                 g.mu.Unlock()
1457         }
1458         if t, ok := t.(*types.Named); ok && t.Obj().Pkg() != nil {
1459                 if t.Obj().Pkg() != ctx.pkg.Pkg {
1460                         return
1461                 }
1462         }
1463
1464         if g.wholeProgram {
1465                 g.mu.Lock()
1466         }
1467         ctx.seenTypes.Set(t, struct{}{})
1468         if g.wholeProgram {
1469                 g.mu.Unlock()
1470         }
1471         if isIrrelevant(t) {
1472                 return
1473         }
1474
1475         ctx.see(t)
1476         switch t := t.(type) {
1477         case *types.Struct:
1478                 for i := 0; i < t.NumFields(); i++ {
1479                         ctx.see(t.Field(i))
1480                         if t.Field(i).Exported() {
1481                                 // (6.2) structs use exported fields
1482                                 ctx.use(t.Field(i), t, edgeExportedField)
1483                         } else if t.Field(i).Name() == "_" {
1484                                 ctx.use(t.Field(i), t, edgeBlankField)
1485                         } else if isNoCopyType(t.Field(i).Type()) {
1486                                 // (6.1) structs use fields of type NoCopy sentinel
1487                                 ctx.use(t.Field(i), t, edgeNoCopySentinel)
1488                         } else if parent == nil {
1489                                 // (11.1) anonymous struct types use all their fields.
1490                                 ctx.use(t.Field(i), t, edgeAnonymousStruct)
1491                         }
1492                         if t.Field(i).Anonymous() {
1493                                 // (e3) exported identifiers aren't automatically used.
1494                                 if !g.wholeProgram {
1495                                         // does the embedded field contribute exported methods to the method set?
1496                                         T := t.Field(i).Type()
1497                                         if _, ok := T.Underlying().(*types.Pointer); !ok {
1498                                                 // An embedded field is addressable, so check
1499                                                 // the pointer type to get the full method set
1500                                                 T = types.NewPointer(T)
1501                                         }
1502                                         ms := ctx.pkg.IR.Prog.MethodSets.MethodSet(T)
1503                                         for j := 0; j < ms.Len(); j++ {
1504                                                 if ms.At(j).Obj().Exported() {
1505                                                         // (6.4) structs use embedded fields that have exported methods (recursively)
1506                                                         ctx.use(t.Field(i), t, edgeExtendsExportedMethodSet)
1507                                                         break
1508                                                 }
1509                                         }
1510                                 }
1511
1512                                 seen := map[*types.Struct]struct{}{}
1513                                 var hasExportedField func(t types.Type) bool
1514                                 hasExportedField = func(T types.Type) bool {
1515                                         t, ok := code.Dereference(T).Underlying().(*types.Struct)
1516                                         if !ok {
1517                                                 return false
1518                                         }
1519                                         if _, ok := seen[t]; ok {
1520                                                 return false
1521                                         }
1522                                         seen[t] = struct{}{}
1523                                         for i := 0; i < t.NumFields(); i++ {
1524                                                 field := t.Field(i)
1525                                                 if field.Exported() {
1526                                                         return true
1527                                                 }
1528                                                 if field.Embedded() && hasExportedField(field.Type()) {
1529                                                         return true
1530                                                 }
1531                                         }
1532                                         return false
1533                                 }
1534                                 // does the embedded field contribute exported fields?
1535                                 if hasExportedField(t.Field(i).Type()) {
1536                                         // (6.5) structs use embedded structs that have exported fields (recursively)
1537                                         ctx.use(t.Field(i), t, edgeExtendsExportedFields)
1538                                 }
1539
1540                         }
1541                         g.variable(ctx, t.Field(i))
1542                 }
1543         case *types.Basic:
1544                 // Nothing to do
1545         case *types.Named:
1546                 // (9.3) types use their underlying and element types
1547                 ctx.seeAndUse(t.Underlying(), t, edgeUnderlyingType)
1548                 ctx.seeAndUse(t.Obj(), t, edgeTypeName)
1549                 ctx.seeAndUse(t, t.Obj(), edgeNamedType)
1550
1551                 // (2.4) named types use the pointer type
1552                 if _, ok := t.Underlying().(*types.Interface); !ok && t.NumMethods() > 0 {
1553                         ctx.seeAndUse(types.NewPointer(t), t, edgePointerType)
1554                 }
1555
1556                 for i := 0; i < t.NumMethods(); i++ {
1557                         ctx.see(t.Method(i))
1558                         // don't use trackExportedIdentifier here, we care about
1559                         // all exported methods, even in package main or in tests.
1560                         if t.Method(i).Exported() && !g.wholeProgram {
1561                                 // (2.1) named types use exported methods
1562                                 ctx.use(t.Method(i), t, edgeExportedMethod)
1563                         }
1564                         g.function(ctx, ctx.pkg.IR.Prog.FuncValue(t.Method(i)))
1565                 }
1566
1567                 g.typ(ctx, t.Underlying(), t)
1568         case *types.Slice:
1569                 // (9.3) types use their underlying and element types
1570                 ctx.seeAndUse(t.Elem(), t, edgeElementType)
1571                 g.typ(ctx, t.Elem(), nil)
1572         case *types.Map:
1573                 // (9.3) types use their underlying and element types
1574                 ctx.seeAndUse(t.Elem(), t, edgeElementType)
1575                 // (9.3) types use their underlying and element types
1576                 ctx.seeAndUse(t.Key(), t, edgeKeyType)
1577                 g.typ(ctx, t.Elem(), nil)
1578                 g.typ(ctx, t.Key(), nil)
1579         case *types.Signature:
1580                 g.signature(ctx, t, nil)
1581         case *types.Interface:
1582                 for i := 0; i < t.NumMethods(); i++ {
1583                         m := t.Method(i)
1584                         // (8.3) All interface methods are marked as used
1585                         ctx.seeAndUse(m, t, edgeInterfaceMethod)
1586                         ctx.seeAndUse(m.Type().(*types.Signature), m, edgeSignature)
1587                         g.signature(ctx, m.Type().(*types.Signature), nil)
1588                 }
1589                 for i := 0; i < t.NumEmbeddeds(); i++ {
1590                         tt := t.EmbeddedType(i)
1591                         // (8.4) All embedded interfaces are marked as used
1592                         ctx.seeAndUse(tt, t, edgeEmbeddedInterface)
1593                 }
1594         case *types.Array:
1595                 // (9.3) types use their underlying and element types
1596                 ctx.seeAndUse(t.Elem(), t, edgeElementType)
1597                 g.typ(ctx, t.Elem(), nil)
1598         case *types.Pointer:
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.Chan:
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.Tuple:
1607                 for i := 0; i < t.Len(); i++ {
1608                         // (9.3) types use their underlying and element types
1609                         ctx.seeAndUse(t.At(i).Type(), t, edgeTupleElement|edgeType)
1610                         g.typ(ctx, t.At(i).Type(), nil)
1611                 }
1612         default:
1613                 panic(fmt.Sprintf("unreachable: %T", t))
1614         }
1615 }
1616
1617 func (g *Graph) variable(ctx *context, v *types.Var) {
1618         // (9.2) variables use their types
1619         ctx.seeAndUse(v.Type(), v, edgeType)
1620         g.typ(ctx, v.Type(), nil)
1621 }
1622
1623 func (g *Graph) signature(ctx *context, sig *types.Signature, fn types.Object) {
1624         var user interface{} = fn
1625         if fn == nil {
1626                 user = sig
1627                 ctx.see(sig)
1628         }
1629         if sig.Recv() != nil {
1630                 ctx.seeAndUse(sig.Recv().Type(), user, edgeReceiver|edgeType)
1631                 g.typ(ctx, sig.Recv().Type(), nil)
1632         }
1633         for i := 0; i < sig.Params().Len(); i++ {
1634                 param := sig.Params().At(i)
1635                 ctx.seeAndUse(param.Type(), user, edgeFunctionArgument|edgeType)
1636                 g.typ(ctx, param.Type(), nil)
1637         }
1638         for i := 0; i < sig.Results().Len(); i++ {
1639                 param := sig.Results().At(i)
1640                 ctx.seeAndUse(param.Type(), user, edgeFunctionResult|edgeType)
1641                 g.typ(ctx, param.Type(), nil)
1642         }
1643 }
1644
1645 func (g *Graph) instructions(ctx *context, fn *ir.Function) {
1646         fnObj := owningObject(fn)
1647         for _, b := range fn.Blocks {
1648                 for _, instr := range b.Instrs {
1649                         ops := instr.Operands(nil)
1650                         switch instr.(type) {
1651                         case *ir.Store:
1652                                 // (9.7) variable _reads_ use variables, writes do not
1653                                 ops = ops[1:]
1654                         case *ir.DebugRef:
1655                                 ops = nil
1656                         }
1657                         for _, arg := range ops {
1658                                 walkPhi(*arg, func(v ir.Value) {
1659                                         switch v := v.(type) {
1660                                         case *ir.Function:
1661                                                 // (4.3) functions use closures and bound methods.
1662                                                 // (4.5) functions use functions they call
1663                                                 // (9.5) instructions use their operands
1664                                                 // (4.4) functions use functions they return. we assume that someone else will call the returned function
1665                                                 if owningObject(v) != nil {
1666                                                         ctx.seeAndUse(owningObject(v), fnObj, edgeInstructionOperand)
1667                                                 }
1668                                                 g.function(ctx, v)
1669                                         case *ir.Const:
1670                                                 // (9.6) instructions use their operands' types
1671                                                 ctx.seeAndUse(v.Type(), fnObj, edgeType)
1672                                                 g.typ(ctx, v.Type(), nil)
1673                                         case *ir.Global:
1674                                                 if v.Object() != nil {
1675                                                         // (9.5) instructions use their operands
1676                                                         ctx.seeAndUse(v.Object(), fnObj, edgeInstructionOperand)
1677                                                 }
1678                                         }
1679                                 })
1680                         }
1681                         if v, ok := instr.(ir.Value); ok {
1682                                 if _, ok := v.(*ir.Range); !ok {
1683                                         // See https://github.com/golang/go/issues/19670
1684
1685                                         // (4.8) instructions use their types
1686                                         // (9.4) conversions use the type they convert to
1687                                         ctx.seeAndUse(v.Type(), fnObj, edgeType)
1688                                         g.typ(ctx, v.Type(), nil)
1689                                 }
1690                         }
1691                         switch instr := instr.(type) {
1692                         case *ir.Field:
1693                                 st := instr.X.Type().Underlying().(*types.Struct)
1694                                 field := st.Field(instr.Field)
1695                                 // (4.7) functions use fields they access
1696                                 ctx.seeAndUse(field, fnObj, edgeFieldAccess)
1697                         case *ir.FieldAddr:
1698                                 st := code.Dereference(instr.X.Type()).Underlying().(*types.Struct)
1699                                 field := st.Field(instr.Field)
1700                                 // (4.7) functions use fields they access
1701                                 ctx.seeAndUse(field, fnObj, edgeFieldAccess)
1702                         case *ir.Store:
1703                                 // nothing to do, handled generically by operands
1704                         case *ir.Call:
1705                                 c := instr.Common()
1706                                 if !c.IsInvoke() {
1707                                         // handled generically as an instruction operand
1708
1709                                         if g.wholeProgram {
1710                                                 // (e3) special case known reflection-based method callers
1711                                                 switch code.CallName(c) {
1712                                                 case "net/rpc.Register", "net/rpc.RegisterName", "(*net/rpc.Server).Register", "(*net/rpc.Server).RegisterName":
1713                                                         var arg ir.Value
1714                                                         switch code.CallName(c) {
1715                                                         case "net/rpc.Register":
1716                                                                 arg = c.Args[0]
1717                                                         case "net/rpc.RegisterName":
1718                                                                 arg = c.Args[1]
1719                                                         case "(*net/rpc.Server).Register":
1720                                                                 arg = c.Args[1]
1721                                                         case "(*net/rpc.Server).RegisterName":
1722                                                                 arg = c.Args[2]
1723                                                         }
1724                                                         walkPhi(arg, func(v ir.Value) {
1725                                                                 if v, ok := v.(*ir.MakeInterface); ok {
1726                                                                         walkPhi(v.X, func(vv ir.Value) {
1727                                                                                 ms := ctx.pkg.IR.Prog.MethodSets.MethodSet(vv.Type())
1728                                                                                 for i := 0; i < ms.Len(); i++ {
1729                                                                                         if ms.At(i).Obj().Exported() {
1730                                                                                                 g.useMethod(ctx, vv.Type(), ms.At(i), fnObj, edgeNetRPCRegister)
1731                                                                                         }
1732                                                                                 }
1733                                                                         })
1734                                                                 }
1735                                                         })
1736                                                 }
1737                                         }
1738                                 } else {
1739                                         // (4.5) functions use functions/interface methods they call
1740                                         ctx.seeAndUse(c.Method, fnObj, edgeInterfaceCall)
1741                                 }
1742                         case *ir.Return:
1743                                 // nothing to do, handled generically by operands
1744                         case *ir.ChangeType:
1745                                 // conversion type handled generically
1746
1747                                 s1, ok1 := code.Dereference(instr.Type()).Underlying().(*types.Struct)
1748                                 s2, ok2 := code.Dereference(instr.X.Type()).Underlying().(*types.Struct)
1749                                 if ok1 && ok2 {
1750                                         // Converting between two structs. The fields are
1751                                         // relevant for the conversion, but only if the
1752                                         // fields are also used outside of the conversion.
1753                                         // Mark fields as used by each other.
1754
1755                                         assert(s1.NumFields() == s2.NumFields())
1756                                         for i := 0; i < s1.NumFields(); i++ {
1757                                                 ctx.see(s1.Field(i))
1758                                                 ctx.see(s2.Field(i))
1759                                                 // (5.1) when converting between two equivalent structs, the fields in
1760                                                 // either struct use each other. the fields are relevant for the
1761                                                 // conversion, but only if the fields are also accessed outside the
1762                                                 // conversion.
1763                                                 ctx.seeAndUse(s1.Field(i), s2.Field(i), edgeStructConversion)
1764                                                 ctx.seeAndUse(s2.Field(i), s1.Field(i), edgeStructConversion)
1765                                         }
1766                                 }
1767                         case *ir.MakeInterface:
1768                                 // nothing to do, handled generically by operands
1769                         case *ir.Slice:
1770                                 // nothing to do, handled generically by operands
1771                         case *ir.RunDefers:
1772                                 // nothing to do, the deferred functions are already marked use by defering them.
1773                         case *ir.Convert:
1774                                 // to unsafe.Pointer
1775                                 if typ, ok := instr.Type().(*types.Basic); ok && typ.Kind() == types.UnsafePointer {
1776                                         if ptr, ok := instr.X.Type().Underlying().(*types.Pointer); ok {
1777                                                 if st, ok := ptr.Elem().Underlying().(*types.Struct); ok {
1778                                                         for i := 0; i < st.NumFields(); i++ {
1779                                                                 // (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
1780                                                                 ctx.seeAndUse(st.Field(i), fnObj, edgeUnsafeConversion)
1781                                                         }
1782                                                 }
1783                                         }
1784                                 }
1785                                 // from unsafe.Pointer
1786                                 if typ, ok := instr.X.Type().(*types.Basic); ok && typ.Kind() == types.UnsafePointer {
1787                                         if ptr, ok := instr.Type().Underlying().(*types.Pointer); ok {
1788                                                 if st, ok := ptr.Elem().Underlying().(*types.Struct); ok {
1789                                                         for i := 0; i < st.NumFields(); i++ {
1790                                                                 // (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
1791                                                                 ctx.seeAndUse(st.Field(i), fnObj, edgeUnsafeConversion)
1792                                                         }
1793                                                 }
1794                                         }
1795                                 }
1796                         case *ir.TypeAssert:
1797                                 // nothing to do, handled generically by instruction
1798                                 // type (possibly a tuple, which contains the asserted
1799                                 // to type). redundantly handled by the type of
1800                                 // ir.Extract, too
1801                         case *ir.MakeClosure:
1802                                 // nothing to do, handled generically by operands
1803                         case *ir.Alloc:
1804                                 // nothing to do
1805                         case *ir.UnOp:
1806                                 // nothing to do
1807                         case *ir.BinOp:
1808                                 // nothing to do
1809                         case *ir.If:
1810                                 // nothing to do
1811                         case *ir.Jump:
1812                                 // nothing to do
1813                         case *ir.Unreachable:
1814                                 // nothing to do
1815                         case *ir.IndexAddr:
1816                                 // nothing to do
1817                         case *ir.Extract:
1818                                 // nothing to do
1819                         case *ir.Panic:
1820                                 // nothing to do
1821                         case *ir.DebugRef:
1822                                 // nothing to do
1823                         case *ir.BlankStore:
1824                                 // nothing to do
1825                         case *ir.Phi:
1826                                 // nothing to do
1827                         case *ir.Sigma:
1828                                 // nothing to do
1829                         case *ir.MakeMap:
1830                                 // nothing to do
1831                         case *ir.MapUpdate:
1832                                 // nothing to do
1833                         case *ir.MapLookup:
1834                                 // nothing to do
1835                         case *ir.StringLookup:
1836                                 // nothing to do
1837                         case *ir.MakeSlice:
1838                                 // nothing to do
1839                         case *ir.Send:
1840                                 // nothing to do
1841                         case *ir.MakeChan:
1842                                 // nothing to do
1843                         case *ir.Range:
1844                                 // nothing to do
1845                         case *ir.Next:
1846                                 // nothing to do
1847                         case *ir.Index:
1848                                 // nothing to do
1849                         case *ir.Select:
1850                                 // nothing to do
1851                         case *ir.ChangeInterface:
1852                                 // nothing to do
1853                         case *ir.Load:
1854                                 // nothing to do
1855                         case *ir.Go:
1856                                 // nothing to do
1857                         case *ir.Defer:
1858                                 // nothing to do
1859                         case *ir.Parameter:
1860                                 // nothing to do
1861                         case *ir.Const:
1862                                 // nothing to do
1863                         case *ir.Recv:
1864                                 // nothing to do
1865                         case *ir.TypeSwitch:
1866                                 // nothing to do
1867                         case *ir.ConstantSwitch:
1868                                 // nothing to do
1869                         default:
1870                                 panic(fmt.Sprintf("unreachable: %T", instr))
1871                         }
1872                 }
1873         }
1874 }
1875
1876 // isNoCopyType reports whether a type represents the NoCopy sentinel
1877 // type. The NoCopy type is a named struct with no fields and exactly
1878 // one method `func Lock()` that is empty.
1879 //
1880 // FIXME(dh): currently we're not checking that the function body is
1881 // empty.
1882 func isNoCopyType(typ types.Type) bool {
1883         st, ok := typ.Underlying().(*types.Struct)
1884         if !ok {
1885                 return false
1886         }
1887         if st.NumFields() != 0 {
1888                 return false
1889         }
1890
1891         named, ok := typ.(*types.Named)
1892         if !ok {
1893                 return false
1894         }
1895         if named.NumMethods() != 1 {
1896                 return false
1897         }
1898         meth := named.Method(0)
1899         if meth.Name() != "Lock" {
1900                 return false
1901         }
1902         sig := meth.Type().(*types.Signature)
1903         if sig.Params().Len() != 0 || sig.Results().Len() != 0 {
1904                 return false
1905         }
1906         return true
1907 }
1908
1909 func walkPhi(v ir.Value, fn func(v ir.Value)) {
1910         phi, ok := v.(*ir.Phi)
1911         if !ok {
1912                 fn(v)
1913                 return
1914         }
1915
1916         seen := map[ir.Value]struct{}{}
1917         var impl func(v *ir.Phi)
1918         impl = func(v *ir.Phi) {
1919                 if _, ok := seen[v]; ok {
1920                         return
1921                 }
1922                 seen[v] = struct{}{}
1923                 for _, e := range v.Edges {
1924                         if ev, ok := e.(*ir.Phi); ok {
1925                                 impl(ev)
1926                         } else {
1927                                 fn(e)
1928                         }
1929                 }
1930         }
1931         impl(phi)
1932 }
1933
1934 func interfacesFromExportData(pkg *types.Package) []*types.Interface {
1935         var out []*types.Interface
1936         scope := pkg.Scope()
1937         for _, name := range scope.Names() {
1938                 obj := scope.Lookup(name)
1939                 out = append(out, interfacesFromObject(obj)...)
1940         }
1941         return out
1942 }
1943
1944 func interfacesFromObject(obj types.Object) []*types.Interface {
1945         var out []*types.Interface
1946         switch obj := obj.(type) {
1947         case *types.Func:
1948                 sig := obj.Type().(*types.Signature)
1949                 for i := 0; i < sig.Results().Len(); i++ {
1950                         out = append(out, interfacesFromObject(sig.Results().At(i))...)
1951                 }
1952                 for i := 0; i < sig.Params().Len(); i++ {
1953                         out = append(out, interfacesFromObject(sig.Params().At(i))...)
1954                 }
1955         case *types.TypeName:
1956                 if named, ok := obj.Type().(*types.Named); ok {
1957                         for i := 0; i < named.NumMethods(); i++ {
1958                                 out = append(out, interfacesFromObject(named.Method(i))...)
1959                         }
1960
1961                         if iface, ok := named.Underlying().(*types.Interface); ok {
1962                                 out = append(out, iface)
1963                         }
1964                 }
1965         case *types.Var:
1966                 // No call to Underlying here. We want unnamed interfaces
1967                 // only. Named interfaces are gotten directly from the
1968                 // package's scope.
1969                 if iface, ok := obj.Type().(*types.Interface); ok {
1970                         out = append(out, iface)
1971                 }
1972         case *types.Const:
1973         case *types.Builtin:
1974         default:
1975                 panic(fmt.Sprintf("unhandled type: %T", obj))
1976         }
1977         return out
1978 }