+++ /dev/null
-package unused
-
-import (
- "fmt"
- "go/ast"
- "go/token"
- "go/types"
- "io"
- "strings"
- "sync"
- "sync/atomic"
-
- "golang.org/x/tools/go/analysis"
- "honnef.co/go/tools/code"
- "honnef.co/go/tools/go/types/typeutil"
- "honnef.co/go/tools/internal/passes/buildir"
- "honnef.co/go/tools/ir"
- "honnef.co/go/tools/lint"
-)
-
-// The graph we construct omits nodes along a path that do not
-// contribute any new information to the solution. For example, the
-// full graph for a function with a receiver would be Func ->
-// Signature -> Var -> Type. However, since signatures cannot be
-// unused, and receivers are always considered used, we can compact
-// the graph down to Func -> Type. This makes the graph smaller, but
-// harder to debug.
-
-// TODO(dh): conversions between structs mark fields as used, but the
-// conversion itself isn't part of that subgraph. even if the function
-// containing the conversion is unused, the fields will be marked as
-// used.
-
-// TODO(dh): we cannot observe function calls in assembly files.
-
-/*
-
-- packages use:
- - (1.1) exported named types (unless in package main)
- - (1.2) exported functions (unless in package main)
- - (1.3) exported variables (unless in package main)
- - (1.4) exported constants (unless in package main)
- - (1.5) init functions
- - (1.6) functions exported to cgo
- - (1.7) the main function iff in the main package
- - (1.8) symbols linked via go:linkname
-
-- named types use:
- - (2.1) exported methods
- - (2.2) the type they're based on
- - (2.3) all their aliases. we can't easily track uses of aliases
- because go/types turns them into uses of the aliased types. assume
- that if a type is used, so are all of its aliases.
- - (2.4) the pointer type. this aids with eagerly implementing
- interfaces. if a method that implements an interface is defined on
- a pointer receiver, and the pointer type is never used, but the
- named type is, then we still want to mark the method as used.
-
-- variables and constants use:
- - their types
-
-- functions use:
- - (4.1) all their arguments, return parameters and receivers
- - (4.2) anonymous functions defined beneath them
- - (4.3) closures and bound methods.
- this implements a simplified model where a function is used merely by being referenced, even if it is never called.
- that way we don't have to keep track of closures escaping functions.
- - (4.4) functions they return. we assume that someone else will call the returned function
- - (4.5) functions/interface methods they call
- - types they instantiate or convert to
- - (4.7) fields they access
- - (4.8) types of all instructions
- - (4.9) package-level variables they assign to iff in tests (sinks for benchmarks)
-
-- conversions use:
- - (5.1) when converting between two equivalent structs, the fields in
- either struct use each other. the fields are relevant for the
- conversion, but only if the fields are also accessed outside the
- conversion.
- - (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
-
-- structs use:
- - (6.1) fields of type NoCopy sentinel
- - (6.2) exported fields
- - (6.3) embedded fields that help implement interfaces (either fully implements it, or contributes required methods) (recursively)
- - (6.4) embedded fields that have exported methods (recursively)
- - (6.5) embedded structs that have exported fields (recursively)
-
-- (7.1) field accesses use fields
-- (7.2) fields use their types
-
-- (8.0) How we handle interfaces:
- - (8.1) We do not technically care about interfaces that only consist of
- exported methods. Exported methods on concrete types are always
- marked as used.
- - Any concrete type implements all known interfaces. Even if it isn't
- assigned to any interfaces in our code, the user may receive a value
- of the type and expect to pass it back to us through an interface.
-
- Concrete types use their methods that implement interfaces. If the
- type is used, it uses those methods. Otherwise, it doesn't. This
- way, types aren't incorrectly marked reachable through the edge
- from method to type.
-
- - (8.3) All interface methods are marked as used, even if they never get
- called. This is to accommodate sum types (unexported interface
- method that must exist but never gets called.)
-
- - (8.4) All embedded interfaces are marked as used. This is an
- extension of 8.3, but we have to explicitly track embedded
- interfaces because in a chain C->B->A, B wouldn't be marked as
- used by 8.3 just because it contributes A's methods to C.
-
-- Inherent uses:
- - thunks and other generated wrappers call the real function
- - (9.2) variables use their types
- - (9.3) types use their underlying and element types
- - (9.4) conversions use the type they convert to
- - (9.5) instructions use their operands
- - (9.6) instructions use their operands' types
- - (9.7) variable _reads_ use variables, writes do not, except in tests
- - (9.8) runtime functions that may be called from user code via the compiler
-
-
-- const groups:
- (10.1) if one constant out of a block of constants is used, mark all
- of them used. a lot of the time, unused constants exist for the sake
- of completeness. See also
- https://github.com/dominikh/go-tools/issues/365
-
-
-- (11.1) anonymous struct types use all their fields. we cannot
- deduplicate struct types, as that leads to order-dependent
- reportings. we can't not deduplicate struct types while still
- tracking fields, because then each instance of the unnamed type in
- the data flow chain will get its own fields, causing false
- positives. Thus, we only accurately track fields of named struct
- types, and assume that unnamed struct types use all their fields.
-
-
-- Differences in whole program mode:
- - (e2) types aim to implement all exported interfaces from all packages
- - (e3) exported identifiers aren't automatically used. for fields and
- methods this poses extra issues due to reflection. We assume
- that all exported fields are used. We also maintain a list of
- known reflection-based method callers.
-
-*/
-
-func assert(b bool) {
- if !b {
- panic("failed assertion")
- }
-}
-
-func typString(obj types.Object) string {
- switch obj := obj.(type) {
- case *types.Func:
- return "func"
- case *types.Var:
- if obj.IsField() {
- return "field"
- }
- return "var"
- case *types.Const:
- return "const"
- case *types.TypeName:
- return "type"
- default:
- return "identifier"
- }
-}
-
-// /usr/lib/go/src/runtime/proc.go:433:6: func badmorestackg0 is unused (U1000)
-
-// Functions defined in the Go runtime that may be called through
-// compiler magic or via assembly.
-var runtimeFuncs = map[string]bool{
- // The first part of the list is copied from
- // cmd/compile/internal/gc/builtin.go, var runtimeDecls
- "newobject": true,
- "panicindex": true,
- "panicslice": true,
- "panicdivide": true,
- "panicmakeslicelen": true,
- "throwinit": true,
- "panicwrap": true,
- "gopanic": true,
- "gorecover": true,
- "goschedguarded": true,
- "printbool": true,
- "printfloat": true,
- "printint": true,
- "printhex": true,
- "printuint": true,
- "printcomplex": true,
- "printstring": true,
- "printpointer": true,
- "printiface": true,
- "printeface": true,
- "printslice": true,
- "printnl": true,
- "printsp": true,
- "printlock": true,
- "printunlock": true,
- "concatstring2": true,
- "concatstring3": true,
- "concatstring4": true,
- "concatstring5": true,
- "concatstrings": true,
- "cmpstring": true,
- "intstring": true,
- "slicebytetostring": true,
- "slicebytetostringtmp": true,
- "slicerunetostring": true,
- "stringtoslicebyte": true,
- "stringtoslicerune": true,
- "slicecopy": true,
- "slicestringcopy": true,
- "decoderune": true,
- "countrunes": true,
- "convI2I": true,
- "convT16": true,
- "convT32": true,
- "convT64": true,
- "convTstring": true,
- "convTslice": true,
- "convT2E": true,
- "convT2Enoptr": true,
- "convT2I": true,
- "convT2Inoptr": true,
- "assertE2I": true,
- "assertE2I2": true,
- "assertI2I": true,
- "assertI2I2": true,
- "panicdottypeE": true,
- "panicdottypeI": true,
- "panicnildottype": true,
- "ifaceeq": true,
- "efaceeq": true,
- "fastrand": true,
- "makemap64": true,
- "makemap": true,
- "makemap_small": true,
- "mapaccess1": true,
- "mapaccess1_fast32": true,
- "mapaccess1_fast64": true,
- "mapaccess1_faststr": true,
- "mapaccess1_fat": true,
- "mapaccess2": true,
- "mapaccess2_fast32": true,
- "mapaccess2_fast64": true,
- "mapaccess2_faststr": true,
- "mapaccess2_fat": true,
- "mapassign": true,
- "mapassign_fast32": true,
- "mapassign_fast32ptr": true,
- "mapassign_fast64": true,
- "mapassign_fast64ptr": true,
- "mapassign_faststr": true,
- "mapiterinit": true,
- "mapdelete": true,
- "mapdelete_fast32": true,
- "mapdelete_fast64": true,
- "mapdelete_faststr": true,
- "mapiternext": true,
- "mapclear": true,
- "makechan64": true,
- "makechan": true,
- "chanrecv1": true,
- "chanrecv2": true,
- "chansend1": true,
- "closechan": true,
- "writeBarrier": true,
- "typedmemmove": true,
- "typedmemclr": true,
- "typedslicecopy": true,
- "selectnbsend": true,
- "selectnbrecv": true,
- "selectnbrecv2": true,
- "selectsetpc": true,
- "selectgo": true,
- "block": true,
- "makeslice": true,
- "makeslice64": true,
- "growslice": true,
- "memmove": true,
- "memclrNoHeapPointers": true,
- "memclrHasPointers": true,
- "memequal": true,
- "memequal8": true,
- "memequal16": true,
- "memequal32": true,
- "memequal64": true,
- "memequal128": true,
- "int64div": true,
- "uint64div": true,
- "int64mod": true,
- "uint64mod": true,
- "float64toint64": true,
- "float64touint64": true,
- "float64touint32": true,
- "int64tofloat64": true,
- "uint64tofloat64": true,
- "uint32tofloat64": true,
- "complex128div": true,
- "racefuncenter": true,
- "racefuncenterfp": true,
- "racefuncexit": true,
- "raceread": true,
- "racewrite": true,
- "racereadrange": true,
- "racewriterange": true,
- "msanread": true,
- "msanwrite": true,
- "x86HasPOPCNT": true,
- "x86HasSSE41": true,
- "arm64HasATOMICS": true,
-
- // The second part of the list is extracted from assembly code in
- // the standard library, with the exception of the runtime package itself
- "abort": true,
- "aeshashbody": true,
- "args": true,
- "asminit": true,
- "badctxt": true,
- "badmcall2": true,
- "badmcall": true,
- "badmorestackg0": true,
- "badmorestackgsignal": true,
- "badsignal2": true,
- "callbackasm1": true,
- "callCfunction": true,
- "cgocallback_gofunc": true,
- "cgocallbackg": true,
- "checkgoarm": true,
- "check": true,
- "debugCallCheck": true,
- "debugCallWrap": true,
- "emptyfunc": true,
- "entersyscall": true,
- "exit": true,
- "exits": true,
- "exitsyscall": true,
- "externalthreadhandler": true,
- "findnull": true,
- "goexit1": true,
- "gostring": true,
- "i386_set_ldt": true,
- "_initcgo": true,
- "init_thread_tls": true,
- "ldt0setup": true,
- "libpreinit": true,
- "load_g": true,
- "morestack": true,
- "mstart": true,
- "nacl_sysinfo": true,
- "nanotimeQPC": true,
- "nanotime": true,
- "newosproc0": true,
- "newproc": true,
- "newstack": true,
- "noted": true,
- "nowQPC": true,
- "osinit": true,
- "printf": true,
- "racecallback": true,
- "reflectcallmove": true,
- "reginit": true,
- "rt0_go": true,
- "save_g": true,
- "schedinit": true,
- "setldt": true,
- "settls": true,
- "sighandler": true,
- "sigprofNonGo": true,
- "sigtrampgo": true,
- "_sigtramp": true,
- "sigtramp": true,
- "stackcheck": true,
- "syscall_chdir": true,
- "syscall_chroot": true,
- "syscall_close": true,
- "syscall_dup2": true,
- "syscall_execve": true,
- "syscall_exit": true,
- "syscall_fcntl": true,
- "syscall_forkx": true,
- "syscall_gethostname": true,
- "syscall_getpid": true,
- "syscall_ioctl": true,
- "syscall_pipe": true,
- "syscall_rawsyscall6": true,
- "syscall_rawSyscall6": true,
- "syscall_rawsyscall": true,
- "syscall_RawSyscall": true,
- "syscall_rawsysvicall6": true,
- "syscall_setgid": true,
- "syscall_setgroups": true,
- "syscall_setpgid": true,
- "syscall_setsid": true,
- "syscall_setuid": true,
- "syscall_syscall6": true,
- "syscall_syscall": true,
- "syscall_Syscall": true,
- "syscall_sysvicall6": true,
- "syscall_wait4": true,
- "syscall_write": true,
- "traceback": true,
- "tstart": true,
- "usplitR0": true,
- "wbBufFlush": true,
- "write": true,
-}
-
-type pkg struct {
- Fset *token.FileSet
- Files []*ast.File
- Pkg *types.Package
- TypesInfo *types.Info
- TypesSizes types.Sizes
- IR *ir.Package
- SrcFuncs []*ir.Function
-}
-
-type Checker struct {
- WholeProgram bool
- Debug io.Writer
-
- mu sync.Mutex
- initialPackages map[*types.Package]struct{}
- allPackages map[*types.Package]struct{}
- graph *Graph
-}
-
-func NewChecker(wholeProgram bool) *Checker {
- return &Checker{
- initialPackages: map[*types.Package]struct{}{},
- allPackages: map[*types.Package]struct{}{},
- WholeProgram: wholeProgram,
- }
-}
-
-func (c *Checker) Analyzer() *analysis.Analyzer {
- name := "U1000"
- if c.WholeProgram {
- name = "U1001"
- }
- return &analysis.Analyzer{
- Name: name,
- Doc: "Unused code",
- Run: c.Run,
- Requires: []*analysis.Analyzer{buildir.Analyzer},
- }
-}
-
-func (c *Checker) Run(pass *analysis.Pass) (interface{}, error) {
- c.mu.Lock()
- if c.graph == nil {
- c.graph = NewGraph()
- c.graph.wholeProgram = c.WholeProgram
- c.graph.fset = pass.Fset
- }
-
- var visit func(pkg *types.Package)
- visit = func(pkg *types.Package) {
- if _, ok := c.allPackages[pkg]; ok {
- return
- }
- c.allPackages[pkg] = struct{}{}
- for _, imp := range pkg.Imports() {
- visit(imp)
- }
- }
- visit(pass.Pkg)
-
- c.initialPackages[pass.Pkg] = struct{}{}
- c.mu.Unlock()
-
- irpkg := pass.ResultOf[buildir.Analyzer].(*buildir.IR)
- pkg := &pkg{
- Fset: pass.Fset,
- Files: pass.Files,
- Pkg: pass.Pkg,
- TypesInfo: pass.TypesInfo,
- TypesSizes: pass.TypesSizes,
- IR: irpkg.Pkg,
- SrcFuncs: irpkg.SrcFuncs,
- }
-
- c.processPkg(c.graph, pkg)
-
- return nil, nil
-}
-
-func (c *Checker) ProblemObject(fset *token.FileSet, obj types.Object) lint.Problem {
- name := obj.Name()
- if sig, ok := obj.Type().(*types.Signature); ok && sig.Recv() != nil {
- switch sig.Recv().Type().(type) {
- case *types.Named, *types.Pointer:
- typ := types.TypeString(sig.Recv().Type(), func(*types.Package) string { return "" })
- if len(typ) > 0 && typ[0] == '*' {
- name = fmt.Sprintf("(%s).%s", typ, obj.Name())
- } else if len(typ) > 0 {
- name = fmt.Sprintf("%s.%s", typ, obj.Name())
- }
- }
- }
-
- checkName := "U1000"
- if c.WholeProgram {
- checkName = "U1001"
- }
- return lint.Problem{
- Pos: lint.DisplayPosition(fset, obj.Pos()),
- Message: fmt.Sprintf("%s %s is unused", typString(obj), name),
- Check: checkName,
- }
-}
-
-func (c *Checker) Result() []types.Object {
- out := c.results()
-
- out2 := make([]types.Object, 0, len(out))
- for _, v := range out {
- if _, ok := c.initialPackages[v.Pkg()]; !ok {
- continue
- }
- out2 = append(out2, v)
- }
-
- return out2
-}
-
-func (c *Checker) debugf(f string, v ...interface{}) {
- if c.Debug != nil {
- fmt.Fprintf(c.Debug, f, v...)
- }
-}
-
-func (graph *Graph) quieten(node *Node) {
- if node.seen {
- return
- }
- switch obj := node.obj.(type) {
- case *types.Named:
- for i := 0; i < obj.NumMethods(); i++ {
- m := obj.Method(i)
- if node, ok := graph.nodeMaybe(m); ok {
- node.quiet = true
- }
- }
- case *types.Struct:
- for i := 0; i < obj.NumFields(); i++ {
- if node, ok := graph.nodeMaybe(obj.Field(i)); ok {
- node.quiet = true
- }
- }
- case *types.Interface:
- for i := 0; i < obj.NumExplicitMethods(); i++ {
- m := obj.ExplicitMethod(i)
- if node, ok := graph.nodeMaybe(m); ok {
- node.quiet = true
- }
- }
- }
-}
-
-func (c *Checker) results() []types.Object {
- if c.graph == nil {
- // We never analyzed any packages
- return nil
- }
-
- var out []types.Object
-
- if c.WholeProgram {
- var ifaces []*types.Interface
- var notIfaces []types.Type
-
- // implement as many interfaces as possible
- c.graph.seenTypes.Iterate(func(t types.Type, _ interface{}) {
- switch t := t.(type) {
- case *types.Interface:
- if t.NumMethods() > 0 {
- ifaces = append(ifaces, t)
- }
- default:
- if _, ok := t.Underlying().(*types.Interface); !ok {
- notIfaces = append(notIfaces, t)
- }
- }
- })
-
- for pkg := range c.allPackages {
- for _, iface := range interfacesFromExportData(pkg) {
- if iface.NumMethods() > 0 {
- ifaces = append(ifaces, iface)
- }
- }
- }
-
- ctx := &context{
- g: c.graph,
- seenTypes: &c.graph.seenTypes,
- }
- // (8.0) handle interfaces
- // (e2) types aim to implement all exported interfaces from all packages
- for _, t := range notIfaces {
- // OPT(dh): it is unfortunate that we do not have access
- // to a populated method set at this point.
- ms := types.NewMethodSet(t)
- for _, iface := range ifaces {
- if sels, ok := c.graph.implements(t, iface, ms); ok {
- for _, sel := range sels {
- c.graph.useMethod(ctx, t, sel, t, edgeImplements)
- }
- }
- }
- }
- }
-
- if c.Debug != nil {
- debugNode := func(node *Node) {
- if node.obj == nil {
- c.debugf("n%d [label=\"Root\"];\n", node.id)
- } else {
- c.debugf("n%d [label=%q];\n", node.id, fmt.Sprintf("(%T) %s", node.obj, node.obj))
- }
- for _, e := range node.used {
- for i := edgeKind(1); i < 64; i++ {
- if e.kind.is(1 << i) {
- c.debugf("n%d -> n%d [label=%q];\n", node.id, e.node.id, edgeKind(1<<i))
- }
- }
- }
- }
-
- c.debugf("digraph{\n")
- debugNode(c.graph.Root)
- for _, v := range c.graph.Nodes {
- debugNode(v)
- }
- c.graph.TypeNodes.Iterate(func(key types.Type, value interface{}) {
- debugNode(value.(*Node))
- })
-
- c.debugf("}\n")
- }
-
- c.graph.color(c.graph.Root)
- // if a node is unused, don't report any of the node's
- // children as unused. for example, if a function is unused,
- // don't flag its receiver. if a named type is unused, don't
- // flag its methods.
-
- for _, v := range c.graph.Nodes {
- c.graph.quieten(v)
- }
- c.graph.TypeNodes.Iterate(func(_ types.Type, value interface{}) {
- c.graph.quieten(value.(*Node))
- })
-
- report := func(node *Node) {
- if node.seen {
- return
- }
- if node.quiet {
- c.debugf("n%d [color=purple];\n", node.id)
- return
- }
-
- c.debugf("n%d [color=red];\n", node.id)
- switch obj := node.obj.(type) {
- case *types.Var:
- // don't report unnamed variables (interface embedding)
- if obj.Name() != "" || obj.IsField() {
- out = append(out, obj)
- }
- return
- case types.Object:
- if obj.Name() != "_" {
- out = append(out, obj)
- }
- return
- }
- c.debugf("n%d [color=gray];\n", node.id)
- }
- for _, v := range c.graph.Nodes {
- report(v)
- }
- c.graph.TypeNodes.Iterate(func(_ types.Type, value interface{}) {
- report(value.(*Node))
- })
-
- return out
-}
-
-func (c *Checker) processPkg(graph *Graph, pkg *pkg) {
- if pkg.Pkg.Path() == "unsafe" {
- return
- }
- graph.entry(pkg)
-}
-
-func objNodeKeyFor(fset *token.FileSet, obj types.Object) objNodeKey {
- var kind objType
- switch obj.(type) {
- case *types.PkgName:
- kind = otPkgName
- case *types.Const:
- kind = otConst
- case *types.TypeName:
- kind = otTypeName
- case *types.Var:
- kind = otVar
- case *types.Func:
- kind = otFunc
- case *types.Label:
- kind = otLabel
- case *types.Builtin:
- kind = otBuiltin
- case *types.Nil:
- kind = otNil
- default:
- panic(fmt.Sprintf("unreachable: %T", obj))
- }
-
- position := fset.PositionFor(obj.Pos(), false)
- position.Column = 0
- position.Offset = 0
- return objNodeKey{
- position: position,
- kind: kind,
- name: obj.Name(),
- }
-}
-
-type objType uint8
-
-const (
- otPkgName objType = iota
- otConst
- otTypeName
- otVar
- otFunc
- otLabel
- otBuiltin
- otNil
-)
-
-// An objNodeKey describes a types.Object node in the graph.
-//
-// Due to test variants we may end up with multiple instances of the
-// same object, which is why we have to deduplicate based on their
-// source position. And because export data lacks column information,
-// we also have to incorporate the object's string representation in
-// the key.
-//
-// Previously we used the object's full string representation
-// (types.ObjectString), but that causes a significant amount of
-// allocations. Currently we're using the object's type and name, in
-// the hope that it is impossible for two objects to have the same
-// type, name and file position.
-type objNodeKey struct {
- position token.Position
- kind objType
- name string
-}
-
-type Graph struct {
- // accessed atomically
- nodeOffset uint64
-
- // Safe for concurrent use
- fset *token.FileSet
- Root *Node
- seenTypes typeutil.Map
-
- // read-only
- wholeProgram bool
-
- // need synchronisation
- mu sync.Mutex
- TypeNodes typeutil.Map
- Nodes map[interface{}]*Node
- objNodes map[objNodeKey]*Node
-}
-
-type context struct {
- g *Graph
- pkg *pkg
- seenFns map[string]struct{}
- seenTypes *typeutil.Map
- nodeCounter uint64
-}
-
-func NewGraph() *Graph {
- g := &Graph{
- Nodes: map[interface{}]*Node{},
- objNodes: map[objNodeKey]*Node{},
- }
- g.Root = g.newNode(&context{}, nil)
- return g
-}
-
-func (g *Graph) color(root *Node) {
- if root.seen {
- return
- }
- root.seen = true
- for _, e := range root.used {
- g.color(e.node)
- }
-}
-
-type ConstGroup struct {
- // give the struct a size to get unique pointers
- _ byte
-}
-
-func (ConstGroup) String() string { return "const group" }
-
-type edge struct {
- node *Node
- kind edgeKind
-}
-
-type Node struct {
- obj interface{}
- id uint64
-
- mu sync.Mutex
- used []edge
-
- // set during final graph walk if node is reachable
- seen bool
- // a parent node (e.g. the struct type containing a field) is
- // already unused, don't report children
- quiet bool
-}
-
-func (g *Graph) nodeMaybe(obj types.Object) (*Node, bool) {
- g.mu.Lock()
- defer g.mu.Unlock()
- if node, ok := g.Nodes[obj]; ok {
- return node, true
- }
- return nil, false
-}
-
-func (g *Graph) node(ctx *context, obj interface{}) (node *Node, new bool) {
- g.mu.Lock()
- defer g.mu.Unlock()
- switch obj := obj.(type) {
- case types.Type:
- if v := g.TypeNodes.At(obj); v != nil {
- return v.(*Node), false
- }
- node := g.newNode(ctx, obj)
- g.TypeNodes.Set(obj, node)
- return node, true
- case types.Object:
- if node, ok := g.Nodes[obj]; ok {
- return node, false
- }
-
- key := objNodeKeyFor(g.fset, obj)
- if onode, ok := g.objNodes[key]; ok {
- return onode, false
- }
-
- node = g.newNode(ctx, obj)
- g.Nodes[obj] = node
- g.objNodes[key] = node
- return node, true
- default:
- if node, ok := g.Nodes[obj]; ok {
- return node, false
- }
-
- node = g.newNode(ctx, obj)
- g.Nodes[obj] = node
- return node, true
- }
-}
-
-func (g *Graph) newNode(ctx *context, obj interface{}) *Node {
- ctx.nodeCounter++
- return &Node{
- obj: obj,
- id: ctx.nodeCounter,
- }
-}
-
-func (n *Node) use(node *Node, kind edgeKind) {
- n.mu.Lock()
- defer n.mu.Unlock()
- assert(node != nil)
- n.used = append(n.used, edge{node: node, kind: kind})
-}
-
-// isIrrelevant reports whether an object's presence in the graph is
-// of any relevance. A lot of objects will never have outgoing edges,
-// nor meaningful incoming ones. Examples are basic types and empty
-// signatures, among many others.
-//
-// Dropping these objects should have no effect on correctness, but
-// may improve performance. It also helps with debugging, as it
-// greatly reduces the size of the graph.
-func isIrrelevant(obj interface{}) bool {
- if obj, ok := obj.(types.Object); ok {
- switch obj := obj.(type) {
- case *types.Var:
- if obj.IsField() {
- // We need to track package fields
- return false
- }
- if obj.Pkg() != nil && obj.Parent() == obj.Pkg().Scope() {
- // We need to track package-level variables
- return false
- }
- return isIrrelevant(obj.Type())
- default:
- return false
- }
- }
- if T, ok := obj.(types.Type); ok {
- switch T := T.(type) {
- case *types.Array:
- return isIrrelevant(T.Elem())
- case *types.Slice:
- return isIrrelevant(T.Elem())
- case *types.Basic:
- return true
- case *types.Tuple:
- for i := 0; i < T.Len(); i++ {
- if !isIrrelevant(T.At(i).Type()) {
- return false
- }
- }
- return true
- case *types.Signature:
- if T.Recv() != nil {
- return false
- }
- for i := 0; i < T.Params().Len(); i++ {
- if !isIrrelevant(T.Params().At(i)) {
- return false
- }
- }
- for i := 0; i < T.Results().Len(); i++ {
- if !isIrrelevant(T.Results().At(i)) {
- return false
- }
- }
- return true
- case *types.Interface:
- return T.NumMethods() == 0 && T.NumEmbeddeds() == 0
- case *types.Pointer:
- return isIrrelevant(T.Elem())
- case *types.Map:
- return isIrrelevant(T.Key()) && isIrrelevant(T.Elem())
- case *types.Struct:
- return T.NumFields() == 0
- case *types.Chan:
- return isIrrelevant(T.Elem())
- default:
- return false
- }
- }
- return false
-}
-
-func (ctx *context) see(obj interface{}) *Node {
- if isIrrelevant(obj) {
- return nil
- }
-
- assert(obj != nil)
- // add new node to graph
- node, _ := ctx.g.node(ctx, obj)
- return node
-}
-
-func (ctx *context) use(used, by interface{}, kind edgeKind) {
- if isIrrelevant(used) {
- return
- }
-
- assert(used != nil)
- if obj, ok := by.(types.Object); ok && obj.Pkg() != nil {
- if !ctx.g.wholeProgram && obj.Pkg() != ctx.pkg.Pkg {
- return
- }
- }
- usedNode, new := ctx.g.node(ctx, used)
- assert(!new)
- if by == nil {
- ctx.g.Root.use(usedNode, kind)
- } else {
- byNode, new := ctx.g.node(ctx, by)
- assert(!new)
- byNode.use(usedNode, kind)
- }
-}
-
-func (ctx *context) seeAndUse(used, by interface{}, kind edgeKind) *Node {
- node := ctx.see(used)
- ctx.use(used, by, kind)
- return node
-}
-
-// trackExportedIdentifier reports whether obj should be considered
-// used due to being exported, checking various conditions that affect
-// the decision.
-func (g *Graph) trackExportedIdentifier(ctx *context, obj types.Object) bool {
- if !obj.Exported() {
- // object isn't exported, the question is moot
- return false
- }
- path := g.fset.Position(obj.Pos()).Filename
- if g.wholeProgram {
- // Example functions without "Output:" comments aren't being
- // run and thus don't show up in the graph.
- if strings.HasSuffix(path, "_test.go") && strings.HasPrefix(obj.Name(), "Example") {
- return true
- }
- // whole program mode tracks exported identifiers accurately
- return false
- }
-
- if ctx.pkg.Pkg.Name() == "main" && !strings.HasSuffix(path, "_test.go") {
- // exported identifiers in package main can't be imported.
- // However, test functions can be called, and xtest packages
- // even have access to exported identifiers.
- return false
- }
-
- if strings.HasSuffix(path, "_test.go") {
- if strings.HasPrefix(obj.Name(), "Test") ||
- strings.HasPrefix(obj.Name(), "Benchmark") ||
- strings.HasPrefix(obj.Name(), "Example") {
- return true
- }
- return false
- }
-
- return true
-}
-
-func (g *Graph) entry(pkg *pkg) {
- no := atomic.AddUint64(&g.nodeOffset, 1)
- ctx := &context{
- g: g,
- pkg: pkg,
- nodeCounter: no * 1e9,
- seenFns: map[string]struct{}{},
- }
- if g.wholeProgram {
- ctx.seenTypes = &g.seenTypes
- } else {
- ctx.seenTypes = &typeutil.Map{}
- }
-
- scopes := map[*types.Scope]*ir.Function{}
- for _, fn := range pkg.SrcFuncs {
- if fn.Object() != nil {
- scope := fn.Object().(*types.Func).Scope()
- scopes[scope] = fn
- }
- }
-
- for _, f := range pkg.Files {
- for _, cg := range f.Comments {
- for _, c := range cg.List {
- if strings.HasPrefix(c.Text, "//go:linkname ") {
- // FIXME(dh): we're looking at all comments. The
- // compiler only looks at comments in the
- // left-most column. The intention probably is to
- // only look at top-level comments.
-
- // (1.8) packages use symbols linked via go:linkname
- fields := strings.Fields(c.Text)
- if len(fields) == 3 {
- if m, ok := pkg.IR.Members[fields[1]]; ok {
- var obj types.Object
- switch m := m.(type) {
- case *ir.Global:
- obj = m.Object()
- case *ir.Function:
- obj = m.Object()
- default:
- panic(fmt.Sprintf("unhandled type: %T", m))
- }
- assert(obj != nil)
- ctx.seeAndUse(obj, nil, edgeLinkname)
- }
- }
- }
- }
- }
- }
-
- surroundingFunc := func(obj types.Object) *ir.Function {
- scope := obj.Parent()
- for scope != nil {
- if fn := scopes[scope]; fn != nil {
- return fn
- }
- scope = scope.Parent()
- }
- return nil
- }
-
- // IR form won't tell us about locally scoped types that aren't
- // being used. Walk the list of Defs to get all named types.
- //
- // IR form also won't tell us about constants; use Defs and Uses
- // to determine which constants exist and which are being used.
- for _, obj := range pkg.TypesInfo.Defs {
- switch obj := obj.(type) {
- case *types.TypeName:
- // types are being handled by walking the AST
- case *types.Const:
- ctx.see(obj)
- fn := surroundingFunc(obj)
- if fn == nil && g.trackExportedIdentifier(ctx, obj) {
- // (1.4) packages use exported constants (unless in package main)
- ctx.use(obj, nil, edgeExportedConstant)
- }
- g.typ(ctx, obj.Type(), nil)
- ctx.seeAndUse(obj.Type(), obj, edgeType)
- }
- }
-
- // Find constants being used inside functions, find sinks in tests
- for _, fn := range pkg.SrcFuncs {
- if fn.Object() != nil {
- ctx.see(fn.Object())
- }
- node := fn.Source()
- if node == nil {
- continue
- }
- ast.Inspect(node, func(node ast.Node) bool {
- switch node := node.(type) {
- case *ast.Ident:
- obj, ok := pkg.TypesInfo.Uses[node]
- if !ok {
- return true
- }
- switch obj := obj.(type) {
- case *types.Const:
- ctx.seeAndUse(obj, owningObject(fn), edgeUsedConstant)
- }
- case *ast.AssignStmt:
- for _, expr := range node.Lhs {
- ident, ok := expr.(*ast.Ident)
- if !ok {
- continue
- }
- obj := pkg.TypesInfo.ObjectOf(ident)
- if obj == nil {
- continue
- }
- path := g.fset.File(obj.Pos()).Name()
- if strings.HasSuffix(path, "_test.go") {
- if obj.Parent() != nil && obj.Parent().Parent() != nil && obj.Parent().Parent().Parent() == nil {
- // object's scope is the package, whose
- // parent is the file, whose parent is nil
-
- // (4.9) functions use package-level variables they assign to iff in tests (sinks for benchmarks)
- // (9.7) variable _reads_ use variables, writes do not, except in tests
- ctx.seeAndUse(obj, owningObject(fn), edgeTestSink)
- }
- }
- }
- }
-
- return true
- })
- }
- // Find constants being used in non-function contexts
- for _, obj := range pkg.TypesInfo.Uses {
- _, ok := obj.(*types.Const)
- if !ok {
- continue
- }
- ctx.seeAndUse(obj, nil, edgeUsedConstant)
- }
-
- var fns []*types.Func
- var fn *types.Func
- var stack []ast.Node
- for _, f := range pkg.Files {
- ast.Inspect(f, func(n ast.Node) bool {
- if n == nil {
- pop := stack[len(stack)-1]
- stack = stack[:len(stack)-1]
- if _, ok := pop.(*ast.FuncDecl); ok {
- fns = fns[:len(fns)-1]
- if len(fns) == 0 {
- fn = nil
- } else {
- fn = fns[len(fns)-1]
- }
- }
- return true
- }
- stack = append(stack, n)
- switch n := n.(type) {
- case *ast.FuncDecl:
- fn = pkg.TypesInfo.ObjectOf(n.Name).(*types.Func)
- fns = append(fns, fn)
- ctx.see(fn)
- case *ast.GenDecl:
- switch n.Tok {
- case token.CONST:
- groups := code.GroupSpecs(pkg.Fset, n.Specs)
- for _, specs := range groups {
- if len(specs) > 1 {
- cg := &ConstGroup{}
- ctx.see(cg)
- for _, spec := range specs {
- for _, name := range spec.(*ast.ValueSpec).Names {
- obj := pkg.TypesInfo.ObjectOf(name)
- // (10.1) const groups
- ctx.seeAndUse(obj, cg, edgeConstGroup)
- ctx.use(cg, obj, edgeConstGroup)
- }
- }
- }
- }
- case token.VAR:
- for _, spec := range n.Specs {
- v := spec.(*ast.ValueSpec)
- for _, name := range v.Names {
- T := pkg.TypesInfo.TypeOf(name)
- if fn != nil {
- ctx.seeAndUse(T, fn, edgeVarDecl)
- } else {
- // TODO(dh): we likely want to make
- // the type used by the variable, not
- // the package containing the
- // variable. But then we have to take
- // special care of blank identifiers.
- ctx.seeAndUse(T, nil, edgeVarDecl)
- }
- g.typ(ctx, T, nil)
- }
- }
- case token.TYPE:
- for _, spec := range n.Specs {
- // go/types doesn't provide a way to go from a
- // types.Named to the named type it was based on
- // (the t1 in type t2 t1). Therefore we walk the
- // AST and process GenDecls.
- //
- // (2.2) named types use the type they're based on
- v := spec.(*ast.TypeSpec)
- T := pkg.TypesInfo.TypeOf(v.Type)
- obj := pkg.TypesInfo.ObjectOf(v.Name)
- ctx.see(obj)
- ctx.see(T)
- ctx.use(T, obj, edgeType)
- g.typ(ctx, obj.Type(), nil)
- g.typ(ctx, T, nil)
-
- if v.Assign != 0 {
- aliasFor := obj.(*types.TypeName).Type()
- // (2.3) named types use all their aliases. we can't easily track uses of aliases
- if isIrrelevant(aliasFor) {
- // We do not track the type this is an
- // alias for (for example builtins), so
- // just mark the alias used.
- //
- // FIXME(dh): what about aliases declared inside functions?
- ctx.use(obj, nil, edgeAlias)
- } else {
- ctx.see(aliasFor)
- ctx.seeAndUse(obj, aliasFor, edgeAlias)
- }
- }
- }
- }
- }
- return true
- })
- }
-
- for _, m := range pkg.IR.Members {
- switch m := m.(type) {
- case *ir.NamedConst:
- // nothing to do, we collect all constants from Defs
- case *ir.Global:
- if m.Object() != nil {
- ctx.see(m.Object())
- if g.trackExportedIdentifier(ctx, m.Object()) {
- // (1.3) packages use exported variables (unless in package main)
- ctx.use(m.Object(), nil, edgeExportedVariable)
- }
- }
- case *ir.Function:
- mObj := owningObject(m)
- if mObj != nil {
- ctx.see(mObj)
- }
- //lint:ignore SA9003 handled implicitly
- if m.Name() == "init" {
- // (1.5) packages use init functions
- //
- // This is handled implicitly. The generated init
- // function has no object, thus everything in it will
- // be owned by the package.
- }
- // This branch catches top-level functions, not methods.
- if m.Object() != nil && g.trackExportedIdentifier(ctx, m.Object()) {
- // (1.2) packages use exported functions (unless in package main)
- ctx.use(mObj, nil, edgeExportedFunction)
- }
- if m.Name() == "main" && pkg.Pkg.Name() == "main" {
- // (1.7) packages use the main function iff in the main package
- ctx.use(mObj, nil, edgeMainFunction)
- }
- if pkg.Pkg.Path() == "runtime" && runtimeFuncs[m.Name()] {
- // (9.8) runtime functions that may be called from user code via the compiler
- ctx.use(mObj, nil, edgeRuntimeFunction)
- }
- if m.Source() != nil {
- doc := m.Source().(*ast.FuncDecl).Doc
- if doc != nil {
- for _, cmt := range doc.List {
- if strings.HasPrefix(cmt.Text, "//go:cgo_export_") {
- // (1.6) packages use functions exported to cgo
- ctx.use(mObj, nil, edgeCgoExported)
- }
- }
- }
- }
- g.function(ctx, m)
- case *ir.Type:
- if m.Object() != nil {
- ctx.see(m.Object())
- if g.trackExportedIdentifier(ctx, m.Object()) {
- // (1.1) packages use exported named types (unless in package main)
- ctx.use(m.Object(), nil, edgeExportedType)
- }
- }
- g.typ(ctx, m.Type(), nil)
- default:
- panic(fmt.Sprintf("unreachable: %T", m))
- }
- }
-
- if !g.wholeProgram {
- // When not in whole program mode we reset seenTypes after each package,
- // which means g.seenTypes only contains types of
- // interest to us. In whole program mode, we're better off
- // processing all interfaces at once, globally, both for
- // performance reasons and because in whole program mode we
- // actually care about all interfaces, not just the subset
- // that has unexported methods.
-
- var ifaces []*types.Interface
- var notIfaces []types.Type
-
- ctx.seenTypes.Iterate(func(t types.Type, _ interface{}) {
- switch t := t.(type) {
- case *types.Interface:
- // OPT(dh): (8.1) we only need interfaces that have unexported methods
- ifaces = append(ifaces, t)
- default:
- if _, ok := t.Underlying().(*types.Interface); !ok {
- notIfaces = append(notIfaces, t)
- }
- }
- })
-
- // (8.0) handle interfaces
- for _, t := range notIfaces {
- ms := pkg.IR.Prog.MethodSets.MethodSet(t)
- for _, iface := range ifaces {
- if sels, ok := g.implements(t, iface, ms); ok {
- for _, sel := range sels {
- g.useMethod(ctx, t, sel, t, edgeImplements)
- }
- }
- }
- }
- }
-}
-
-func (g *Graph) useMethod(ctx *context, t types.Type, sel *types.Selection, by interface{}, kind edgeKind) {
- obj := sel.Obj()
- path := sel.Index()
- assert(obj != nil)
- if len(path) > 1 {
- base := code.Dereference(t).Underlying().(*types.Struct)
- for _, idx := range path[:len(path)-1] {
- next := base.Field(idx)
- // (6.3) structs use embedded fields that help implement interfaces
- ctx.see(base)
- ctx.seeAndUse(next, base, edgeProvidesMethod)
- base, _ = code.Dereference(next.Type()).Underlying().(*types.Struct)
- }
- }
- ctx.seeAndUse(obj, by, kind)
-}
-
-func owningObject(fn *ir.Function) types.Object {
- if fn.Object() != nil {
- return fn.Object()
- }
- if fn.Parent() != nil {
- return owningObject(fn.Parent())
- }
- return nil
-}
-
-func (g *Graph) function(ctx *context, fn *ir.Function) {
- if fn.Package() != nil && fn.Package() != ctx.pkg.IR {
- return
- }
-
- name := fn.RelString(nil)
- if _, ok := ctx.seenFns[name]; ok {
- return
- }
- ctx.seenFns[name] = struct{}{}
-
- // (4.1) functions use all their arguments, return parameters and receivers
- g.signature(ctx, fn.Signature, owningObject(fn))
- g.instructions(ctx, fn)
- for _, anon := range fn.AnonFuncs {
- // (4.2) functions use anonymous functions defined beneath them
- //
- // This fact is expressed implicitly. Anonymous functions have
- // no types.Object, so their owner is the surrounding
- // function.
- g.function(ctx, anon)
- }
-}
-
-func (g *Graph) typ(ctx *context, t types.Type, parent types.Type) {
- if g.wholeProgram {
- g.mu.Lock()
- }
- if ctx.seenTypes.At(t) != nil {
- if g.wholeProgram {
- g.mu.Unlock()
- }
- return
- }
- if g.wholeProgram {
- g.mu.Unlock()
- }
- if t, ok := t.(*types.Named); ok && t.Obj().Pkg() != nil {
- if t.Obj().Pkg() != ctx.pkg.Pkg {
- return
- }
- }
-
- if g.wholeProgram {
- g.mu.Lock()
- }
- ctx.seenTypes.Set(t, struct{}{})
- if g.wholeProgram {
- g.mu.Unlock()
- }
- if isIrrelevant(t) {
- return
- }
-
- ctx.see(t)
- switch t := t.(type) {
- case *types.Struct:
- for i := 0; i < t.NumFields(); i++ {
- ctx.see(t.Field(i))
- if t.Field(i).Exported() {
- // (6.2) structs use exported fields
- ctx.use(t.Field(i), t, edgeExportedField)
- } else if t.Field(i).Name() == "_" {
- ctx.use(t.Field(i), t, edgeBlankField)
- } else if isNoCopyType(t.Field(i).Type()) {
- // (6.1) structs use fields of type NoCopy sentinel
- ctx.use(t.Field(i), t, edgeNoCopySentinel)
- } else if parent == nil {
- // (11.1) anonymous struct types use all their fields.
- ctx.use(t.Field(i), t, edgeAnonymousStruct)
- }
- if t.Field(i).Anonymous() {
- // (e3) exported identifiers aren't automatically used.
- if !g.wholeProgram {
- // does the embedded field contribute exported methods to the method set?
- T := t.Field(i).Type()
- if _, ok := T.Underlying().(*types.Pointer); !ok {
- // An embedded field is addressable, so check
- // the pointer type to get the full method set
- T = types.NewPointer(T)
- }
- ms := ctx.pkg.IR.Prog.MethodSets.MethodSet(T)
- for j := 0; j < ms.Len(); j++ {
- if ms.At(j).Obj().Exported() {
- // (6.4) structs use embedded fields that have exported methods (recursively)
- ctx.use(t.Field(i), t, edgeExtendsExportedMethodSet)
- break
- }
- }
- }
-
- seen := map[*types.Struct]struct{}{}
- var hasExportedField func(t types.Type) bool
- hasExportedField = func(T types.Type) bool {
- t, ok := code.Dereference(T).Underlying().(*types.Struct)
- if !ok {
- return false
- }
- if _, ok := seen[t]; ok {
- return false
- }
- seen[t] = struct{}{}
- for i := 0; i < t.NumFields(); i++ {
- field := t.Field(i)
- if field.Exported() {
- return true
- }
- if field.Embedded() && hasExportedField(field.Type()) {
- return true
- }
- }
- return false
- }
- // does the embedded field contribute exported fields?
- if hasExportedField(t.Field(i).Type()) {
- // (6.5) structs use embedded structs that have exported fields (recursively)
- ctx.use(t.Field(i), t, edgeExtendsExportedFields)
- }
-
- }
- g.variable(ctx, t.Field(i))
- }
- case *types.Basic:
- // Nothing to do
- case *types.Named:
- // (9.3) types use their underlying and element types
- ctx.seeAndUse(t.Underlying(), t, edgeUnderlyingType)
- ctx.seeAndUse(t.Obj(), t, edgeTypeName)
- ctx.seeAndUse(t, t.Obj(), edgeNamedType)
-
- // (2.4) named types use the pointer type
- if _, ok := t.Underlying().(*types.Interface); !ok && t.NumMethods() > 0 {
- ctx.seeAndUse(types.NewPointer(t), t, edgePointerType)
- }
-
- for i := 0; i < t.NumMethods(); i++ {
- ctx.see(t.Method(i))
- // don't use trackExportedIdentifier here, we care about
- // all exported methods, even in package main or in tests.
- if t.Method(i).Exported() && !g.wholeProgram {
- // (2.1) named types use exported methods
- ctx.use(t.Method(i), t, edgeExportedMethod)
- }
- g.function(ctx, ctx.pkg.IR.Prog.FuncValue(t.Method(i)))
- }
-
- g.typ(ctx, t.Underlying(), t)
- case *types.Slice:
- // (9.3) types use their underlying and element types
- ctx.seeAndUse(t.Elem(), t, edgeElementType)
- g.typ(ctx, t.Elem(), nil)
- case *types.Map:
- // (9.3) types use their underlying and element types
- ctx.seeAndUse(t.Elem(), t, edgeElementType)
- // (9.3) types use their underlying and element types
- ctx.seeAndUse(t.Key(), t, edgeKeyType)
- g.typ(ctx, t.Elem(), nil)
- g.typ(ctx, t.Key(), nil)
- case *types.Signature:
- g.signature(ctx, t, nil)
- case *types.Interface:
- for i := 0; i < t.NumMethods(); i++ {
- m := t.Method(i)
- // (8.3) All interface methods are marked as used
- ctx.seeAndUse(m, t, edgeInterfaceMethod)
- ctx.seeAndUse(m.Type().(*types.Signature), m, edgeSignature)
- g.signature(ctx, m.Type().(*types.Signature), nil)
- }
- for i := 0; i < t.NumEmbeddeds(); i++ {
- tt := t.EmbeddedType(i)
- // (8.4) All embedded interfaces are marked as used
- ctx.seeAndUse(tt, t, edgeEmbeddedInterface)
- }
- case *types.Array:
- // (9.3) types use their underlying and element types
- ctx.seeAndUse(t.Elem(), t, edgeElementType)
- g.typ(ctx, t.Elem(), nil)
- case *types.Pointer:
- // (9.3) types use their underlying and element types
- ctx.seeAndUse(t.Elem(), t, edgeElementType)
- g.typ(ctx, t.Elem(), nil)
- case *types.Chan:
- // (9.3) types use their underlying and element types
- ctx.seeAndUse(t.Elem(), t, edgeElementType)
- g.typ(ctx, t.Elem(), nil)
- case *types.Tuple:
- for i := 0; i < t.Len(); i++ {
- // (9.3) types use their underlying and element types
- ctx.seeAndUse(t.At(i).Type(), t, edgeTupleElement|edgeType)
- g.typ(ctx, t.At(i).Type(), nil)
- }
- default:
- panic(fmt.Sprintf("unreachable: %T", t))
- }
-}
-
-func (g *Graph) variable(ctx *context, v *types.Var) {
- // (9.2) variables use their types
- ctx.seeAndUse(v.Type(), v, edgeType)
- g.typ(ctx, v.Type(), nil)
-}
-
-func (g *Graph) signature(ctx *context, sig *types.Signature, fn types.Object) {
- var user interface{} = fn
- if fn == nil {
- user = sig
- ctx.see(sig)
- }
- if sig.Recv() != nil {
- ctx.seeAndUse(sig.Recv().Type(), user, edgeReceiver|edgeType)
- g.typ(ctx, sig.Recv().Type(), nil)
- }
- for i := 0; i < sig.Params().Len(); i++ {
- param := sig.Params().At(i)
- ctx.seeAndUse(param.Type(), user, edgeFunctionArgument|edgeType)
- g.typ(ctx, param.Type(), nil)
- }
- for i := 0; i < sig.Results().Len(); i++ {
- param := sig.Results().At(i)
- ctx.seeAndUse(param.Type(), user, edgeFunctionResult|edgeType)
- g.typ(ctx, param.Type(), nil)
- }
-}
-
-func (g *Graph) instructions(ctx *context, fn *ir.Function) {
- fnObj := owningObject(fn)
- for _, b := range fn.Blocks {
- for _, instr := range b.Instrs {
- ops := instr.Operands(nil)
- switch instr.(type) {
- case *ir.Store:
- // (9.7) variable _reads_ use variables, writes do not
- ops = ops[1:]
- case *ir.DebugRef:
- ops = nil
- }
- for _, arg := range ops {
- walkPhi(*arg, func(v ir.Value) {
- switch v := v.(type) {
- case *ir.Function:
- // (4.3) functions use closures and bound methods.
- // (4.5) functions use functions they call
- // (9.5) instructions use their operands
- // (4.4) functions use functions they return. we assume that someone else will call the returned function
- if owningObject(v) != nil {
- ctx.seeAndUse(owningObject(v), fnObj, edgeInstructionOperand)
- }
- g.function(ctx, v)
- case *ir.Const:
- // (9.6) instructions use their operands' types
- ctx.seeAndUse(v.Type(), fnObj, edgeType)
- g.typ(ctx, v.Type(), nil)
- case *ir.Global:
- if v.Object() != nil {
- // (9.5) instructions use their operands
- ctx.seeAndUse(v.Object(), fnObj, edgeInstructionOperand)
- }
- }
- })
- }
- if v, ok := instr.(ir.Value); ok {
- if _, ok := v.(*ir.Range); !ok {
- // See https://github.com/golang/go/issues/19670
-
- // (4.8) instructions use their types
- // (9.4) conversions use the type they convert to
- ctx.seeAndUse(v.Type(), fnObj, edgeType)
- g.typ(ctx, v.Type(), nil)
- }
- }
- switch instr := instr.(type) {
- case *ir.Field:
- st := instr.X.Type().Underlying().(*types.Struct)
- field := st.Field(instr.Field)
- // (4.7) functions use fields they access
- ctx.seeAndUse(field, fnObj, edgeFieldAccess)
- case *ir.FieldAddr:
- st := code.Dereference(instr.X.Type()).Underlying().(*types.Struct)
- field := st.Field(instr.Field)
- // (4.7) functions use fields they access
- ctx.seeAndUse(field, fnObj, edgeFieldAccess)
- case *ir.Store:
- // nothing to do, handled generically by operands
- case *ir.Call:
- c := instr.Common()
- if !c.IsInvoke() {
- // handled generically as an instruction operand
-
- if g.wholeProgram {
- // (e3) special case known reflection-based method callers
- switch code.CallName(c) {
- case "net/rpc.Register", "net/rpc.RegisterName", "(*net/rpc.Server).Register", "(*net/rpc.Server).RegisterName":
- var arg ir.Value
- switch code.CallName(c) {
- case "net/rpc.Register":
- arg = c.Args[0]
- case "net/rpc.RegisterName":
- arg = c.Args[1]
- case "(*net/rpc.Server).Register":
- arg = c.Args[1]
- case "(*net/rpc.Server).RegisterName":
- arg = c.Args[2]
- }
- walkPhi(arg, func(v ir.Value) {
- if v, ok := v.(*ir.MakeInterface); ok {
- walkPhi(v.X, func(vv ir.Value) {
- ms := ctx.pkg.IR.Prog.MethodSets.MethodSet(vv.Type())
- for i := 0; i < ms.Len(); i++ {
- if ms.At(i).Obj().Exported() {
- g.useMethod(ctx, vv.Type(), ms.At(i), fnObj, edgeNetRPCRegister)
- }
- }
- })
- }
- })
- }
- }
- } else {
- // (4.5) functions use functions/interface methods they call
- ctx.seeAndUse(c.Method, fnObj, edgeInterfaceCall)
- }
- case *ir.Return:
- // nothing to do, handled generically by operands
- case *ir.ChangeType:
- // conversion type handled generically
-
- s1, ok1 := code.Dereference(instr.Type()).Underlying().(*types.Struct)
- s2, ok2 := code.Dereference(instr.X.Type()).Underlying().(*types.Struct)
- if ok1 && ok2 {
- // Converting between two structs. The fields are
- // relevant for the conversion, but only if the
- // fields are also used outside of the conversion.
- // Mark fields as used by each other.
-
- assert(s1.NumFields() == s2.NumFields())
- for i := 0; i < s1.NumFields(); i++ {
- ctx.see(s1.Field(i))
- ctx.see(s2.Field(i))
- // (5.1) when converting between two equivalent structs, the fields in
- // either struct use each other. the fields are relevant for the
- // conversion, but only if the fields are also accessed outside the
- // conversion.
- ctx.seeAndUse(s1.Field(i), s2.Field(i), edgeStructConversion)
- ctx.seeAndUse(s2.Field(i), s1.Field(i), edgeStructConversion)
- }
- }
- case *ir.MakeInterface:
- // nothing to do, handled generically by operands
- case *ir.Slice:
- // nothing to do, handled generically by operands
- case *ir.RunDefers:
- // nothing to do, the deferred functions are already marked use by defering them.
- case *ir.Convert:
- // to unsafe.Pointer
- if typ, ok := instr.Type().(*types.Basic); ok && typ.Kind() == types.UnsafePointer {
- if ptr, ok := instr.X.Type().Underlying().(*types.Pointer); ok {
- if st, ok := ptr.Elem().Underlying().(*types.Struct); ok {
- for i := 0; i < st.NumFields(); i++ {
- // (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
- ctx.seeAndUse(st.Field(i), fnObj, edgeUnsafeConversion)
- }
- }
- }
- }
- // from unsafe.Pointer
- if typ, ok := instr.X.Type().(*types.Basic); ok && typ.Kind() == types.UnsafePointer {
- if ptr, ok := instr.Type().Underlying().(*types.Pointer); ok {
- if st, ok := ptr.Elem().Underlying().(*types.Struct); ok {
- for i := 0; i < st.NumFields(); i++ {
- // (5.2) when converting to or from unsafe.Pointer, mark all fields as used.
- ctx.seeAndUse(st.Field(i), fnObj, edgeUnsafeConversion)
- }
- }
- }
- }
- case *ir.TypeAssert:
- // nothing to do, handled generically by instruction
- // type (possibly a tuple, which contains the asserted
- // to type). redundantly handled by the type of
- // ir.Extract, too
- case *ir.MakeClosure:
- // nothing to do, handled generically by operands
- case *ir.Alloc:
- // nothing to do
- case *ir.UnOp:
- // nothing to do
- case *ir.BinOp:
- // nothing to do
- case *ir.If:
- // nothing to do
- case *ir.Jump:
- // nothing to do
- case *ir.Unreachable:
- // nothing to do
- case *ir.IndexAddr:
- // nothing to do
- case *ir.Extract:
- // nothing to do
- case *ir.Panic:
- // nothing to do
- case *ir.DebugRef:
- // nothing to do
- case *ir.BlankStore:
- // nothing to do
- case *ir.Phi:
- // nothing to do
- case *ir.Sigma:
- // nothing to do
- case *ir.MakeMap:
- // nothing to do
- case *ir.MapUpdate:
- // nothing to do
- case *ir.MapLookup:
- // nothing to do
- case *ir.StringLookup:
- // nothing to do
- case *ir.MakeSlice:
- // nothing to do
- case *ir.Send:
- // nothing to do
- case *ir.MakeChan:
- // nothing to do
- case *ir.Range:
- // nothing to do
- case *ir.Next:
- // nothing to do
- case *ir.Index:
- // nothing to do
- case *ir.Select:
- // nothing to do
- case *ir.ChangeInterface:
- // nothing to do
- case *ir.Load:
- // nothing to do
- case *ir.Go:
- // nothing to do
- case *ir.Defer:
- // nothing to do
- case *ir.Parameter:
- // nothing to do
- case *ir.Const:
- // nothing to do
- case *ir.Recv:
- // nothing to do
- case *ir.TypeSwitch:
- // nothing to do
- case *ir.ConstantSwitch:
- // nothing to do
- default:
- panic(fmt.Sprintf("unreachable: %T", instr))
- }
- }
- }
-}
-
-// isNoCopyType reports whether a type represents the NoCopy sentinel
-// type. The NoCopy type is a named struct with no fields and exactly
-// one method `func Lock()` that is empty.
-//
-// FIXME(dh): currently we're not checking that the function body is
-// empty.
-func isNoCopyType(typ types.Type) bool {
- st, ok := typ.Underlying().(*types.Struct)
- if !ok {
- return false
- }
- if st.NumFields() != 0 {
- return false
- }
-
- named, ok := typ.(*types.Named)
- if !ok {
- return false
- }
- if named.NumMethods() != 1 {
- return false
- }
- meth := named.Method(0)
- if meth.Name() != "Lock" {
- return false
- }
- sig := meth.Type().(*types.Signature)
- if sig.Params().Len() != 0 || sig.Results().Len() != 0 {
- return false
- }
- return true
-}
-
-func walkPhi(v ir.Value, fn func(v ir.Value)) {
- phi, ok := v.(*ir.Phi)
- if !ok {
- fn(v)
- return
- }
-
- seen := map[ir.Value]struct{}{}
- var impl func(v *ir.Phi)
- impl = func(v *ir.Phi) {
- if _, ok := seen[v]; ok {
- return
- }
- seen[v] = struct{}{}
- for _, e := range v.Edges {
- if ev, ok := e.(*ir.Phi); ok {
- impl(ev)
- } else {
- fn(e)
- }
- }
- }
- impl(phi)
-}
-
-func interfacesFromExportData(pkg *types.Package) []*types.Interface {
- var out []*types.Interface
- scope := pkg.Scope()
- for _, name := range scope.Names() {
- obj := scope.Lookup(name)
- out = append(out, interfacesFromObject(obj)...)
- }
- return out
-}
-
-func interfacesFromObject(obj types.Object) []*types.Interface {
- var out []*types.Interface
- switch obj := obj.(type) {
- case *types.Func:
- sig := obj.Type().(*types.Signature)
- for i := 0; i < sig.Results().Len(); i++ {
- out = append(out, interfacesFromObject(sig.Results().At(i))...)
- }
- for i := 0; i < sig.Params().Len(); i++ {
- out = append(out, interfacesFromObject(sig.Params().At(i))...)
- }
- case *types.TypeName:
- if named, ok := obj.Type().(*types.Named); ok {
- for i := 0; i < named.NumMethods(); i++ {
- out = append(out, interfacesFromObject(named.Method(i))...)
- }
-
- if iface, ok := named.Underlying().(*types.Interface); ok {
- out = append(out, iface)
- }
- }
- case *types.Var:
- // No call to Underlying here. We want unnamed interfaces
- // only. Named interfaces are gotten directly from the
- // package's scope.
- if iface, ok := obj.Type().(*types.Interface); ok {
- out = append(out, iface)
- }
- case *types.Const:
- case *types.Builtin:
- default:
- panic(fmt.Sprintf("unhandled type: %T", obj))
- }
- return out
-}