go/ast: add Preorder iterator

[adonovan]

Proposal Details

Programs that use go/ast often need to make traversals over the tree to find all nodes of a given type (or types), or to search for a specific node. The existing ast.Inspect function allows them to do this, but it can impose a significant syntactic overhead. This example shows a use of Inspect to print the first interesting node, aborting the traversal once the node is found:

	var found bool
	ast.Inspect(root, func(n ast.Node) bool {
		if !found && n != nil && interesting(n) {
			print(n)
			found = true
		}
		return !found
	})

We propose to add this function to go/ast:

// DepthFirst returns a go1.23 iterator over the nodes of the syntax
// tree beneath the specified root, in depth-first order.
//
// For greater control over the traversal of each subtree, use [Inspect].
func DepthFirst(root Node) func(yield func(Node) bool) { // = iter.Seq[Node]
	return func(yield func(Node) bool) {
		ok := true
		Inspect(root, func(n Node) bool {
			if n != nil {
				ok = ok && yield(n)
			}
			return ok
		})
	}
}

which would allow the previous example to be simplified to:

	for n := range ast.DepthFirst(root) {
		if interesting(n) {
			print(n)
			break
		}
	}

cc @findleyr @griesemer

[gopherbot]

Change https://go.dev/cl/570680 mentions this issue: go/ast: add DepthFirst go1.23 iterator

[adonovan]

For the curious, it adds 10-15% to the cost of a trivial traversal.

package ast_test

import (
	"go/ast"
	"go/parser"
	"go/token"
	"testing"
)

var file *ast.File

func init() {
	file, _ = parser.ParseFile(token.NewFileSet(), "ast.go", nil, 0)
}

const k = 2

func BenchmarkInspect(b *testing.B) {
	total := 0
	for range b.N {
		var nodes []ast.Node
		ast.Inspect(file, func(n ast.Node) bool {
			if n != nil {
				total++
				if total%k == 0 {
					nodes = append(nodes, n)
				}
			}
			return true
		})
	}
}

func BenchmarkRange(b *testing.B) {
	total := 0
	for range b.N {
		var nodes []ast.Node
		for n := range ast.DepthFirst(file) {
			total++
			if total%k == 0 {
				nodes = append(nodes, n)
			}
		}
	}
}

[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]

The name DepthFirst doesn't indicate whether its Preorder or Postorder. It sounds like we should call it Preorder.
(This matches Inspect, but Inspect is kind of both, it passes n before the visit of children and nil afterward. This function drops the nils.)

[rsc]

Have all remaining concerns about this proposal been addressed?

The proposal is to add:

// Preorder returns a go1.23 iterator over the nodes of the syntax
// tree beneath the specified root, in depth-first order.
// Each node is produced before its children.
//
// For greater control over the traversal of each subtree, use [Inspect].
func Preorder(root Node) iter.Seq[Node]

[rsc]

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

The proposal is to add:

// Preorder returns a go1.23 iterator over the nodes of the syntax
// tree beneath the specified root, in depth-first order.
// Each node is produced before its children.
//
// For greater control over the traversal of each subtree, use [Inspect].
func Preorder(root Node) iter.Seq[Node]

[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:

// Preorder returns a go1.23 iterator over the nodes of the syntax
// tree beneath the specified root, in depth-first order.
// Each node is produced before its children.
//
// For greater control over the traversal of each subtree, use [Inspect].
func Preorder(root Node) iter.Seq[Node]

[gopherbot]

Change https://go.dev/cl/585520 mentions this issue: go/ast: honor the result of yield in Preorder