optimization: use Pattern node types as Inspector type filter

[adonovan]

We've been thinking about AST pattern matching languages in x/tools, and there's an optimization I'd really like to design things around. I wonder if it's useful to staticcheck, or whether this would be a good place to prototype it.

The idea is to scan each Pattern for the set of ast.Node subtypes that must be present in any match; then turn this list into an Inspector type filter; then scan the input tree for matches of the pattern, skipping over any subtree that doesn't contain all the bits representing the nodes of the pattern.

For example, checkLoopSlideQ in S1018 looks like this:

	checkLoopSlideQ = pattern.MustParse(`
		(ForStmt
			(AssignStmt initvar@(Ident _) _ (IntegerLiteral "0"))
			(BinaryExpr initvar "<" limit@(Ident _))
			(IncDecStmt initvar "++")
			[(AssignStmt
				(IndexExpr slice@(Ident _) initvar)
				"="
				(IndexExpr slice (BinaryExpr offset@(Ident _) "+" initvar)))])`)

This means any match must contain all of {ForStmt, AssignStmt, Ident, IntegerLiteral, BinaryExpr, IncDecStmt, IndexExpr}. If we had an Inspector method that said "find me all trees rooted at a ForStmt that contain all these nodes" I think the traversals would be a lot more selective and efficient. The relevant Inspector API doesn't yet exist, but it's trivial to write.

[dominikh]

I'd be happy to prototype the necessary glue between Staticcheck patterns and such an Inspector API and benchmark its impact.

[dominikh]

@adonovan Do you have any news on the relevant Inspector (or presumably Cursor) API?

[adonovan]

Do you have any news on the relevant Inspector (or presumably Cursor) API?

I threw together a quick sketch in https://go.dev/cl/710655. Feedback welcome!