x/tools/cmd/callgraph: calls from unreachable unexported methods not reported in callgraph

[thesilentg]

Go version

go version go1.22.0 darwin/amd64

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='amd64'
GOBIN='/Users/aggnolek/go/bin'
GOCACHE='/Users/aggnolek/Library/Caches/go-build'
GOENV='/Users/aggnolek/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/aggnolek/go/pkg/mod'
GONOPROXY='*'
GONOSUMDB='*'
GOOS='darwin'
GOPATH='/Users/aggnolek/go'
GOPRIVATE='*'
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/Users/aggnolek/sdk/go1.22.0'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/Users/aggnolek/sdk/go1.22.0/pkg/tool/darwin_amd64'
GOVCS=''
GOVERSION='go1.22.0'
GCCGO='gccgo'
GOAMD64='v1'
AR='ar'
CC='cc'
CXX='c++'
CGO_ENABLED='1'
GOMOD='/Users/aggnolek/gorepos/aggnolek/scratchpad/go.mod'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/x7/2f8ynt3954s4y78yt_54v9fr0000gs/T/go-build886972198=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

go.mod

module scratchpad

go 1.21

example2/main.go

package main

func called() {}

type unexported struct{}

func (u unexported) Func1() {
	called()
}

type Exported struct{}

func (e Exported) Func1() {
	called()
}

func main() {
	
}

Ran callgraph -algo={algo} ./example2 for algo in [static, cha, rta, vta]

What did you see happen?

callgraph -algo=static ./example2

(scratchpad/example2.Exported).Func1	--static-14:8-->	scratchpad/example2.called

callgraph -algo=cha ./example2

(scratchpad/example2.Exported).Func1	--static-14:8-->	scratchpad/example2.called

callgraph -algo=rta ./example2

{Empty Output}

callgraph -algo=vta ./example2

(scratchpad/example2.Exported).Func1	--static-14:8-->	scratchpad/example2.called

What did you expect to see?

callgraph -algo=static ./example2

(scratchpad/example2.Exported).Func1	--static-14:8-->	scratchpad/example2.called
(scratchpad/example2.unexported).Func1	--static-8:8-->	scratchpad/example2.called

callgraph -algo=cha ./example2

(scratchpad/example2.Exported).Func1	--static-14:8-->	scratchpad/example2.called
(scratchpad/example2.unexported).Func1	--static-8:8-->	scratchpad/example2.called

callgraph -algo=rta ./example2

{Empty Output}

This is because rta only includes reachable funcs by design

callgraph -algo=vta ./example2

(scratchpad/example2.Exported).Func1	--static-14:8-->	scratchpad/example2.called
(scratchpad/example2.unexported).Func1	--static-8:8-->	scratchpad/example2.called

Note that the link from example2.unexported).Func1 to called is present when example2.unexported).Func1 is forced to be reachable. For example:

example2/main.go

func main() {
	unexported{}.Func1()
}

callgraph -algo=static ./example2

(scratchpad/example2.unexported).Func1	--static-8:8-->	scratchpad/example2.called
(scratchpad/example2.Exported).Func1	--static-14:8-->	scratchpad/example2.called
scratchpad/example2.main	--static-18:20-->	(scratchpad/example2.unexported).Func1

callgraph -algo=cha ./example2

(scratchpad/example2.unexported).Func1	--static-8:8-->	scratchpad/example2.called
(scratchpad/example2.Exported).Func1	--static-14:8-->	scratchpad/example2.called
scratchpad/example2.main	--static-18:20-->	(scratchpad/example2.unexported).Func1

callgraph -algo=rta ./example2

(scratchpad/example2.unexported).Func1	--static-8:8-->	scratchpad/example2.called
scratchpad/example2.main	--static-18:20-->	(scratchpad/example2.unexported).Func1

This is because rta only includes reachable funcs by design

callgraph -algo=vta ./example2

(scratchpad/example2.unexported).Func1	--static-8:8-->	scratchpad/example2.called
(scratchpad/example2.Exported).Func1	--static-14:8-->	scratchpad/example2.called
scratchpad/example2.main	--static-18:20-->	(scratchpad/example2.unexported).Func1

This likely has to do with the same usage of ssautil.AllFunctions (at least for vta) that resulted in this bug for the deadcode command.

[thesilentg]

@adonovan Given your closeness to the likely similar prior issue

[adonovan]

Thanks. I expect a patch along these lines should be effective:

        case "vta":
-               cg = vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
+               // Gather all source-level functions as entry points.
+               sourceFuncs := make(map[*ssa.Function]bool)
+               packages.Visit(initial, nil, func(p *packages.Package) {
+                       for _, file := range p.Syntax {
+                               for _, decl := range file.Decls {
+                                       if decl, ok := decl.(*ast.FuncDecl); ok {
+                                               obj := p.TypesInfo.Defs[decl.Name].(*types.Func)
+                                               fn := prog.FuncValue(obj)
+                                               sourceFuncs[fn] = true
+                                       }
+                               }
+                       }
+               })
+
+               cg = vta.CallGraph(sourceFuncs, cha.CallGraph(prog))

[thesilentg]

Agree with respect to rta, although based on my understanding both static and cha will require separate fixes as those don't take in sourceFuncs.

[thesilentg]

Based on my early testing, I believe you'll also need to filter out nil results for fn, as prog.FuncValue returns nil for interface methods and those nils cause panics within vta.CallGraph

[adonovan]

Agree with respect to rta, although based on my understanding both static and cha will require separate fixes as those don't take in sourceFuncs.

The bug in -algo=static was fixed yesterday by https://go.dev/cl/609280.

The fix for the bug in CHA (which is really a bug in AllFunctions) is something along the lines of https://go.dev/cl/609281, but as it stands that CL would cause CHA's analysis of main packages to no longer treat exported symbols as entry points, which is sound, but I need to think a little more about whether this is consistent with the expectations we have set for CHA. For example, that CL would cause the -algo=cha output on the example above to report the empty set (just like RTA), which is sound but is counter to the expectations you had when filing this bug report. I am inclined to think that the problem of executing the CHA analysis is really orthogonal to the problem of how one gathers up the initial set of functions it uses (and which of those functions are considered address-taken). We may need new API to do it justice.

[gopherbot]

Change https://go.dev/cl/609281 mentions this issue: go/callgraph/cha: make CHA, VTA faster and more precise

[adonovan]

On further reflection, I think the callgraph tool is working as intended when it shows no call edge from unexported.Func1 to called in your first example, because the unexported type is unreachable according to the reachability algorithm implemented by AllFunctions. AllFunctions has certainly had a history of bugs (see #69291), but it has always pretended to use a linker-style reachability algorithm, and any such algorithm should report that unexported is not reachable.

If you were to use a different algorithm to gather up functions ("ReallyAllFunctions(prog)"), the CHA algorithm would analyze the dynamic calls within even the unreachable functions. (We don't have a test for that because cmd/callgraph and the CHA tests both use AllFunction, but I'm confident it would work.) So if you really need that behavior, that's something you could do.

My apologies for the various contradictory things I have said on this and other related callgraph issues this week.