Skip to content

x/tools/go/ssa/ssautil: deprecate AllFunctions #69231

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.

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

Open
adonovan opened this issue Sep 3, 2024 · 9 comments
Open

x/tools/go/ssa/ssautil: deprecate AllFunctions #69231

adonovan opened this issue Sep 3, 2024 · 9 comments
Assignees
Labels
Tools This label describes issues relating to any tools in the x/tools repository.
Milestone

Comments

@adonovan
Copy link
Member

adonovan commented Sep 3, 2024

I would like to deprecate the AllFunctions helper function, because it's a poorly specified mess (my bad).
As its doc comment says:

// I think we should deprecate AllFunctions function in favor of two
// clearly defined ones:
//
//  1. The first would efficiently compute CHA reachability from a set
//     of main packages, making it suitable for a whole-program
//     analysis context with InstantiateGenerics, in conjunction with
//     Program.Build.
//
//  2. The second would return only the set of functions corresponding
//     to source Func{Decl,Lit} syntax, like SrcFunctions in
//     go/analysis/passes/buildssa; this is suitable for
//     package-at-a-time (or handful of packages) context.
//     ssa.Package could easily expose it as a field.

Before we can consider doing that (which will require a proposal), we should stop using it ourselves in x/tools and x/vuln. Its existing uses are:

// These test could use a simpler ad hoc algorithm, or an efficient CHA:
go/ssa/stdlib_test.go
go/ssa/builder_test.go

// both CHA and static do essentially the same reachability fixed point
// iteration and could do (the good bits of) AllFunctions themselves:
go/callgraph/cha/cha.go -- AllFunctions is not even correct here! see #66429
go/callgraph/static/static.go

--

// VTA uses AllFunctions to produce a set of entry points. 
// I suspect it is both a massive overapproximation and yet still not always correct (see #66251)
// What exactly does vta.CallGraph need?
cmd/callgraph/main.go
go/callgraph/vta/vta_test.go
go/callgraph/vta/graph_test.go
go/callgraph/callgraph_test.go
x/vuln/internal/vulncheck/utils.go

// just for debugging; could easily be deleted.
go/callgraph/vta/helpers_test.go 

I will tackle the first half. @zpavlinovic perhaps you could look at the VTA-related ones? What we need at this stage is just crisp descriptions of the exact requirements of each of these algorithms.

@gopherbot gopherbot added the Tools This label describes issues relating to any tools in the x/tools repository. label Sep 3, 2024
@gopherbot gopherbot added this to the Unreleased milestone Sep 3, 2024
@zpavlinovic zpavlinovic self-assigned this Sep 3, 2024
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/609280 mentions this issue: go/callgraph/static: avoid ssautil.AllFunctions

gopherbot pushed a commit to golang/tools that referenced this issue Sep 3, 2024
AllFunctions is complex mess. This change rewrites the static
algorithm to avoid it. It does reduce the number of
call graph nodes that are discovered (by something like 15%),
and the running time by a similar amount, but the principle
is slightly more defensible.

Also, document exactly what it does, and why it is the way
it is.

Updates golang/go#69231

Change-Id: I7e25237f0908315602ba0092083f247a140b9e22
Reviewed-on: https://go-review.googlesource.com/c/tools/+/609280
Reviewed-by: Zvonimir Pavlinovic <[email protected]>
LUCI-TryBot-Result: Go LUCI <[email protected]>
@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/611216 mentions this issue: internal/vulncheck: remove use of ssautil.AllFunctions

@gabyhelp
Copy link

gabyhelp commented Sep 5, 2024

Related Issues and Documentation

(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)

gopherbot pushed a commit to golang/vuln that referenced this issue Sep 5, 2024
This function was used to prune out the forward slice of functions
starting from roots. There weren't a lot of functions being pruned.
Measured on a few large projects, at most 0.08% of functions were
pruned. Keeping those functions is not expected to affect precision
or performance. Calling VTA two times will very likely get rid of
these functions anyhow.

Updates golang/go#69231

Change-Id: Id57f9697c5a5550b4d15fbeb88de30b8bee220da
Reviewed-on: https://go-review.googlesource.com/c/vuln/+/611216
LUCI-TryBot-Result: Go LUCI <[email protected]>
Reviewed-by: Alan Donovan <[email protected]>
@zpavlinovic
Copy link
Contributor

Regarding VTA:

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/611535 mentions this issue: internal/callgraph/chautil: add Reachable function

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/611536 mentions this issue: go/ssa: stop using ssautil.AllFunctions

@adonovan
Copy link
Member Author

adonovan commented Sep 6, 2024

With my https://go.dev/cl/609281 stack (the last CL needs some thought), there are no remaining uses of AllFunctions in x/tools. (Not even tests of it, alarmingly.)

I notice that AllFunctions returns uninstantiated generics whereas the new chautil.Reachable does not, and for this reason it's probably not safe for us ever to make AllFunctions a wrapper around Reachable; we'll just have to leave it there with a doc explaining what it does and why there are better solutions for most tasks, and what they are.

@StevenACoffman
Copy link

StevenACoffman commented Dec 6, 2024

@adonovan Reading through the current source code, I don't believe the second part of AllFunctions doc comment is available yet.

I was hoping for something like this:

// Funcs returns the package-level functions.
func (p *Package) Funcs() ([]*Function) {
	var funcs []*ssa.Function
	for _, f := range p.Members {
	  if f, ok = f.(*Function); ok {
	    funcs = append(funcs, f)
	  }
	}
	return funcs
}

This would be very convenient for some linters to have, so they don't need to waste time calling SrcFunctions in go/analysis/passes/buildssa if AllFunctions is no longer available.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Tools This label describes issues relating to any tools in the x/tools repository.
Projects
None yet
Development

No branches or pull requests

5 participants