x/tools/go/ast/inspector: add Inspector.PreorderSeq and top-level func All

[adonovan]

The golang.org/x/tools/go/ast/inspector package is all about iteration. We propose to add these two methods, which return go1.23 iterators. The first makes it easier to use break/return/continue within a Preorder-style iteration, and the second simplifies the most common case, of searching for nodes of a single type.

package inspector

// Filter returns a go1.23 iterator over all the nodes, in preorder.
//
// The types argument, if non-empty, enables type-based filtering.
// The function f if is called only for nodes whose type matches
// an element of the types slice.
//
// Example:
//
//	nodeTypes := []ast.Node{(*ast.CallExpr)(nil), (*ast.Ident)(nil)}
//	for n := range in.Filter(nodeTypes) { ... }
func (in *Inspector) Filter(types ...ast.Node) iter.Seq[ast.Node]

// One[N] returns a go1.23 iterator over all the nodes of type N.
// N must be a pointer-to-struct type that implements ast.Node.
//
// Example:
//
//     for call := range One[*ast.CallExpr](in) { ... }
func One[N interface { *S; ast.Node }, S any](in *Inspector) iter.Seq[N]

Naming suggestions welcome.

[gopherbot]

Change https://go.dev/cl/589955 mentions this issue: go/ast/inspector: add go1.23 iterators Filter, One[N]

[MikeMitchellWebDev]

Filter makes a lot of sense. I'd prefer Each to One.

[meling]

I’ve seen the “go1.23 iterator” phrase a few times now. Do you we need to mention the “go1.23” in doc comments? I prefer to just say iterator.

[adonovan]

I’ve seen the “go1.23 iterator” phrase a few times now. Do you we need to mention the “go1.23” in doc comments? I prefer to just say iterator.

Initially I used that phrase because it wasn't obvious what the type of the function meant, especially when we spelled out the func(yield func(T) bool)) result explicitly so that we could declare these methods in pre-1.23 files. But I suppose now that we return iter.Seq, the result is self-documenting, as is the fact that go1.23 is required, so we can just say iterator.

[rsc]

Based on Inspector already having a non-Seq form of the first method named Preorder, it seems like the Seq form should be PreorderSeq, so it is clear they are the same thing, with two different APIs.

The top-level generic range seems like it could be called All to match our use of All elsewhere:

for call := range inspector.All[*ast.CallExpr](in) {
    ...
}

That seems pretty nice. (It would still be documented as Preorder.)

[jimmyfrasche]

inspector.All[T] is only a good name when T cannot be inferred or is specified even where it can be inferred. Admittedly there are few places where it can be inferred currently and even if that number grows the vast majority of uses would still require the explicit T. Still, it seems a potential reading hazard to have f = inspector.All not mean All but All such that [context omitted].

[ianlancetaylor]

@jimmyfrasche As far as I can see the type argument to All as proposed here can never be inferred, so I'm not sure that concern arises in this particular case.

[jimmyfrasche]

The example I provided is the only case currently: https://go.dev/play/p/BJqAA5eHLif

More cases may present themselves in the future if inference expands. Here are some reasonable example of (hypothetical) type inference clashing with the name.

for n := range F(inspector.All) {} // type inferred from F

for n = range inspector.All(p) {} // type inferred from n

return inspector.All // type inferred from enclosing function

Presumably it would be still be easy to figure out T from further context but it's still an easy thing for the eye to skip over without noticing that something may be going on here as it's indistinguishable from code where nothing special is happening.

[jimmyfrasche]

AllOf works. It reads nicely when T is explicit and hints that something has been implied otherwise.

[rsc]

FooOf for generics has been proposed many times and to date we have resisted each of them. I think we should continue to resist. That is, I don't think FooOf is an idiom we want to adopt in Go. The problem is that Of can be applied to many many functions that take arguments. Why not

strings.ToLowerOf(s)
bytes.NewBufferOf(data)
ast.NewPackageOf(fset, files, importer, universe)

and so on.

We have not been entirely successful - reflect and go/types have some arguably spurious Of's - but let's not add more.

[fzipp]

I agree, 'Of' is just a redundant way of saying ( or [.

[jimmyfrasche]

My intent was only to signify that it's always conditional so that it stands out when that condition is not present.

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[rsc]

Have all remaining concerns about this proposal been addressed?

The proposal is to add:

// PreorderSeq returns an iterator that visits all the nodes of the files 
// supplied to New in depth-first order. It visits each node n before n’s children.
// The complete traversal sequence is determined by ast.Inspect. The types
// argument, if non-empty, enables type-based filtering of events: only nodes
// whose type matches an element of the types slice are included in the
// sequence.
func (in *Inspector) PreorderSeq(types ...ast.Node) iter.Seq[ast.Node]

// All[N] returns an iterator over all the nodes of type N.
// N must be a pointer-to-struct type that implements ast.Node.
//
// Example:
//
//     for call := range All[*ast.CallExpr](in) { ... }
func All[N interface { *S; ast.Node }, S any](in *Inspector) iter.Seq[N]

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

The proposal is to add:

// PreorderSeq returns an iterator that visits all the nodes of the files 
// supplied to New in depth-first order. It visits each node n before n’s children.
// The complete traversal sequence is determined by ast.Inspect. The types
// argument, if non-empty, enables type-based filtering of events: only nodes
// whose type matches an element of the types slice are included in the
// sequence.
func (in *Inspector) PreorderSeq(types ...ast.Node) iter.Seq[ast.Node]

// All[N] returns an iterator over all the nodes of type N.
// N must be a pointer-to-struct type that implements ast.Node.
//
// Example:
//
//     for call := range All[*ast.CallExpr](in) { ... }
func All[N interface { *S; ast.Node }, S any](in *Inspector) iter.Seq[N]

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

The proposal is to add:

// PreorderSeq returns an iterator that visits all the nodes of the files 
// supplied to New in depth-first order. It visits each node n before n’s children.
// The complete traversal sequence is determined by ast.Inspect. The types
// argument, if non-empty, enables type-based filtering of events: only nodes
// whose type matches an element of the types slice are included in the
// sequence.
func (in *Inspector) PreorderSeq(types ...ast.Node) iter.Seq[ast.Node]

// All[N] returns an iterator over all the nodes of type N.
// N must be a pointer-to-struct type that implements ast.Node.
//
// Example:
//
//     for call := range All[*ast.CallExpr](in) { ... }
func All[N interface { *S; ast.Node }, S any](in *Inspector) iter.Seq[N]

[gopherbot]

Change https://go.dev/cl/616218 mentions this issue: go/ast/inspector: add PreorderSeq and All iterators