Golang go/ast: add Preorder iterator

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

Comment From: gopherbot

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

Comment From: 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)
            }
        }
    }
}

Comment From: 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

Comment From: 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.)

Comment From: 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]

Comment From: 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]

Comment From: 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]

Comment From: gopherbot

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