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

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