Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

x/tools/cmd/callgraph: calls to interface implementation not reported in cha callgraph #66429

Open
samuknet opened this issue Mar 20, 2024 · 3 comments
Open

x/tools/cmd/callgraph: calls to interface implementation not reported in cha callgraph #66429

samuknet opened this issue Mar 20, 2024 · 3 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Tools This label describes issues relating to any tools in the x/tools repository.
Milestone
Unreleased

Comments

@samuknet
Copy link

Go version

go version go1.22.1 darwin/arm64

Output of go env in your module/workspace:

GO111MODULE='auto'
GOARCH='arm64'
GOBIN=''
GOCACHE='/Users/usr/Library/Caches/go-build'
GOENV='/Users/usr/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/usr/pkg/mod'
GONOPROXY='github.com/redacted-org'
GONOSUMDB='github.com/redacted-org'
GOOS='darwin'
GOPATH='/Users/usr'
GOPRIVATE='github.com/redacted-org'
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/opt/homebrew/Cellar/go/1.22.1/libexec'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/opt/homebrew/Cellar/go/1.22.1/libexec/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.22.1'
GCCGO='gccgo'
AR='ar'
CC='cc'
CXX='c++'
CGO_ENABLED='1'
GOMOD='/Users/usr/src/github.com/samuknet/ssa-bug-report/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 arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/q3/l93pryxj2dz39p1d2gy9v2p40000gn/T/go-build1879381070=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

  1. Create example.go in a temporary package
package example

func EntryPoint(ex exampleInterface) {
	ex.InterfaceFn()
}

type exampleInterface interface {
	InterfaceFn()
}

type exampleA struct{}

func (u *exampleA) InterfaceFn() {}

type exampleB struct{}

func (u *exampleB) InterfaceFn() {}

// NewA() returns an exampleA.  Note return type is exampleInterface.
// Results in exampleA.InterfaceFn() being added to the callgraph, as expected.
func NewA() exampleInterface {
	return &exampleA{}
}

// NewB() returns an exampleB. Note the return type is *exampleB.
// exampleB.InterfaceFn() is not included in the callgraph.
func NewB() *exampleB {
	return &exampleB{}
}
  1. Install latest version of callgraph
go mod init
go get golang.org/x/tools/callgraph
    go: added golang.org/x/mod v0.16.0
    go: added golang.org/x/tools v0.19.0
go install golang.org/x/tools/cmd/callgraph
  1. Run callgraph -algo=cha . in the directory of example.go

Output is

github.com/samuknet/ssa-bug-report.EntryPoint   --dynamic-9:16-->       (*github.com/samuknet/ssa-bug-report.exampleA).InterfaceFn

What did you see happen?

Output includes just exampleA.InterfaceFn():

github.com/samuknet/ssa-bug-report.EntryPoint   --dynamic-9:16-->       (*github.com/samuknet/ssa-bug-report.exampleA).InterfaceFn

What did you expect to see?

Output to also include exampleB.InterfaceFn() in addition to exampleA.InterfaceFn().

Note this report is similar to this issue, but more specific to interfaces and reproduces regardless of whether the interface type is exported.

In particular:

  • if the function signature uses the interface as the return type, then the interface implementation is included in the callgraph. See NewA() example above.
  • if the function signature uses the concrete struct as the return type, then the interface implementation is not included in the callgraph. See NewB() above.

The issue persists regardless of whether or not the interface type is exported.

Findings so far
We've identified this commit resulted in the change of behaviour.

Prior to this commit, the callgraph for example.go contains both interface implementations. After the commit it includes just exampleA.InterfaceFn() but not exampleB.InterfaceFn().

From the commit I can see it's now expected for unexported types not to be included in the callgraph by default. Though I'd like to understand whether this change also intended to no longer include interface implementations in the callgraph in the example above.
@gopherbot gopherbot added the Tools This label describes issues relating to any tools in the x/tools repository. label Mar 20, 2024
@gopherbot gopherbot added this to the Unreleased milestone Mar 20, 2024
@dr2chase
Copy link
Contributor

@taking @adonovan @zpavlinovic

@dr2chase dr2chase added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 21, 2024
@zpavlinovic
Copy link
Contributor

zpavlinovic commented Mar 21, 2024 •
edited

It seems to me that what happens is that the function exampleB.InterfaceFn is not even considered by the core cha algorithm. That is, ssautil.AllFunctions is called first to collect all functions potentially needed by the program in a linker-style fashion and this linker does not pull in exampleB.InterfaceFn.

This linker is conservative, but it will try to remove functions that clearly cannot be called. Here, it figures out that since exampleB is not passed to any interface in the program, then it cannot be called in EntryPoint. Hence, exampleB cannot be really used anywhere in this particular program.

On the other hand, exampleA is returned as an interface exampleInterface so in principle exampleA.InterfaceFn can be called in EntryPoint.

You can see this if you change the return type of newB to be the interface or you do something like this:

// NewB() returns an exampleB. Note the return type is *exampleB.
func NewB() *exampleB {
        b := &exampleB{}
        var i exampleInterface
        i = b
        fmt.Printf("%v\n", i)
        return b
}

@adonovan
Copy link
Member

adonovan commented Mar 21, 2024 •
edited

Thanks for the report.

This seems to be a regression introduced by my CL https://go.dev/cl/538357, which caused AllFunctions to return fewer items in this case. But fundamentally I think the problem is that CHA should not be using AllFunctions: its name is misleading, as it doesn't return all functions, it does (and always has done) a reachability analysis, which is not appropriate for CHA, which wants to return the maximal sound call graph without any reachability filtering at all.

I think the solution is for CHA to (like VTA) stop using AllFunctions.

Even more reduced example demonstrating the significance of exportedness:

package example

func EntryPoint(i I) { i.f() }

type I interface{ f() }

type A struct{}

func (*A) f() {}

func NewA() I { return new(A) }

type b struct{}

func (*b) f() {}

func Newb() *b { return new(b) }

type C struct{}

func (*C) f() {}

func NewC() *C { return new(C) }

$ go run ./cmd/callgraph -algo=cha ./a.go 
command-line-arguments.EntryPoint       --dynamic-3:27-->       (*command-line-arguments.A).f
command-line-arguments.EntryPoint       --dynamic-3:27-->       (*command-line-arguments.C).f

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Tools This label describes issues relating to any tools in the x/tools repository.
Projects
None yet
Milestone
Unreleased
Development

No branches or pull requests
5 participants
@zpavlinovic @dr2chase @adonovan @gopherbot @samuknet