x/tools/go/analysis/passes: opt: skip each ast.File that doesn't import the package of interest

[adonovan]

Many go/analysis checkers start by inspecting the import map of the package, and making an early return if a specific package of interest is not found, for example:

	if !analysisutil.Imports(pass.Pkg, "sync/atomic") {
		return nil, nil // doesn't directly import sync/atomic
	}

This check is a substantial optimization. Indeed, in recent experiments we discovered that all the traversals done by static checkers can be quite significant relative to type checking---so much so that gopls' separation of analyzer sets into "all" (for root packages) and "fact-only" (for dependencies) is well worth doing.

We could take it a step further by skipping individual files if they don't import the package of interest. That's easy when the traversal uses ast.Inspect, but harder if it uses the Inspector, since the latter searches all files of the package.

The task of this issue is to try to find a convenient way to skip traversal of files that lack the necessary import, and measure the benefit.

[timothy-king]

harder if it uses the Inspector, since the latter searches all files of the package.

Two approaches come to mind:

1. extend Inspector with a new function that is a version of Preorder but with a list of given Nodes to traverse within. A plausible contract is to consider the Nodes a list of token.Pos [begin, end) pairs and to allow pre-order traversal starting from any node in the inspector that is contained by some root (basically have an new outer loop for Preorder). This then enables a 2 pass solution to first find the relevant *ast.Files and then traverse only these.
2. switch the Inspector.Preorder to Inspector.Nodes to allow for skipping, add *ast.File to the node filter, and add a utility function to determine if an *ast.File should be skipped.

Both approaches would need to rely on *ast.ImportSpect.Path. There might be some subtle differences to types.Package.Path() ?

The breakeven for 1.4x slowdown for Preorder->Nodes is skipping >30% of files. I guess the empirical question underlying this issue is whether once we know a package is imported >= 1 times, then how frequently will it not be imported in some files in the package? For example, my intuition is that if "slog" is imported once, it is imported in most files. My intuition is that is not true for "sort" though. I guess we just need to experiment? (@zpavlinovic thoughts?)

2cents: this is really about speeding up analysis of static calls. There is a related and plausible direction for optimization of enabling more checkers that consider static methods to skip more packages by doing something like !analysisutil.Imports(pass.Pkg, "foo"). Right now this test is still imperfect for static method calls as "foo" does not need to be directly imported for its methods to be called. If one adds the check, there is a risk of missing some reports (e.g. "httpresponse"). But it also does seem plausible that a significant majority of packages can be skipped safely for these checkers (e.g. "slog"), but that seems to require a new fact pass of some kind (my WiP).

[zpavlinovic]

The breakeven for 1.4x slowdown for Preorder->Nodes is skipping >30% of files. I guess the empirical question underlying this issue is whether once we know a package is imported >= 1 times, then how frequently will it not be imported in some files in the package? For example, my intuition is that if "slog" is imported once, it is imported in most files. My intuition is that is not true for "sort" though. I guess we just need to experiment? (@zpavlinovic thoughts?)

I don't see a reason why we couldn't make this experiment on the analysis pipeline.