proposal: go/ast: add PreorderStack, a wrapper around ast.Inspect that maintains a stack

[adonovan]

Background: It is common when using ast.Inspect to need to record a stack of nodes. The easiest way to do this is to append to a slice when n is non-nil (an "enter" event) and to slice it when n is nil (a "leave" event):

var stack []ast.Node
ast.Inspect(root, func(n ast.Node) bool {
    if n != nil {
        stack = append(stack, n) // push
    } else {
        stack = stack[:len(stack)-1] // pop
    }
    ... use n ...
    return true
})

This pattern appears dozens of times throughout x/tools. However, it is subtly wrong: if the "...use n..." portion of the code executes return false, traversal of the subtree n is skipped, and in that case the user's function is never called with a corresponding nil to indicate the "leaving n" event; the stack gets misaligned. We make this mistake nearly every time we use a stack and "return false" in the same traversal.

Proposal: We propose to provide a wrapper function around ast.Inspect that constructs the stack (correctly), passing it to the user's callback.

// PreorderStack traverses the tree rooted at root,
// calling f before visiting each node.
//
// Each call to f provides the current node and traversal stack,
// consisting of the original value of stack appended with all nodes
// from root to n, excluding n itself. (This design allows calls
// to PreorderStack to be nested without double counting.)
//
// If f returns false, the traversal skips over that subtree. Unlike
// [ast.Inspect], no second call to f is made after visiting node n.
// In practice, the second call is nearly always used only to pop the
// stack, and it is surprisingly tricky to do this correctly; see
// https://go.dev/issue/73319.
func PreorderStack(root ast.Node, stack []ast.Node, f func(n ast.Node, stack []ast.Node) bool)

[gopherbot]

Change https://go.dev/cl/664635 mentions this issue: internal/astutil: PreorderStack: a safer ast.Inspect for stacks