Parent links in Go ASTs - Eli Bendersky's website

Go's go/ast package ships no parent pointers, a deliberate design choice shared by many AST libraries. Maintaining such links costs memory — a single extra pointer can notably enlarge a compact node — and CPU time to keep it accurate during construction and rewrites. In a garbage-collected runtime like Go there is a further penalty: every parent pointer becomes another reference the collector must trace. Those are fixed costs paid by every analyzer so that a minority can walk upward.

Suppose your analysis genuinely needs ancestor information. What follows is a survey of four ways to get it, using one artificial task as a running example.

The task

Find every multiplication expression that sits somewhere inside another binary expression. In this snippet

m = y + z * x

the sub-expression z * x, an ast.BinaryExpr, lives inside the +, which is itself an ast.BinaryExpr.

A looser reading of the requirement also accepts nesting through non-binary nodes:

m = x + foo(y*z)

Here the multiplication's immediate parent is a CallExpr; the enclosing binary addition is what counts.

Maintaining your own ancestor stack

The most direct generic fix is to reconstruct the parent chain by hand. ast.Inspect visits the AST depth-first and calls the supplied function with nil once it has finished a node's children — that sentinel value is all the bookkeeping signal needed. Push the current node on entry, pop on the nil call, and the slice standing in for the stack always holds the ancestors of the node under inspection:

func discoverNodeParentsManualStack(pkg *packages.Package) {
  for _, fileAst := range pkg.Syntax {
    var ancestors []ast.Node
    ast.Inspect(fileAst, func(n ast.Node) bool {
      if bexpr, ok := n.(*ast.BinaryExpr); ok && bexpr.Op == token.MUL {
        // Walk the ancestor stack to find if one of them is also a BinaryExpr
        for i := len(ancestors) - 1; i >= 0; i-- {
          if _, ok := ancestors[i].(*ast.BinaryExpr); ok {
            fmt.Printf("found BinaryExpr(*) as a child of another binary expr: %v\n",
              fset.Position(n.Pos()))
            break
          }
        }
      }

      if n == nil {
        // Pop, since we're done with this node and its children.
        ancestors = ancestors[:len(ancestors)-1]
      } else {
        // Push this node on the stack, since its children will be visited
        // next.
        ancestors = append(ancestors, n)
      }
      return true
    })
  }
}

Encountering a * node, you walk that stack looking for an ast.BinaryExpr and you have the answer. The traversal overhead is trivial: one push and one pop per node.

The alternative, working outward from each binary expression, is to start a fresh recursion over its children and report a hit when a binary * turns up. Returning false from the outer callback after inspecting both children prevents redundant work. This stays efficient because it does exactly as much traversal as the question demands, but it is bespoke: little of it transfers to the next analysis you write.

Ready-made helpers

Two traversals already exist in the wider Go tooling, so building the stack yourself is usually unnecessary.

Inspector.WithStack

The golang.org/x/tools/go/ast/inspector package offers traversal helpers, among them WithStack, which hands your callback the current node along with its enclosing path. For this problem it is the recommended route:

func discoverNodeParentsWithStack(pkg *packages.Package) {
  insp := inspector.New(pkg.Syntax)
  insp.WithStack(nil, func(n ast.Node, push bool, stack []ast.Node) bool {
    if bexpr, ok := n.(*ast.BinaryExpr); push && ok && bexpr.Op == token.MUL {
      for i := len(stack) - 2; i >= 0; i-- {
        if _, ok := stack[i].(*ast.BinaryExpr); ok {
          fmt.Printf("found BinaryExpr(*) as a child of another binary expr: %v\n",
            fset.Position(n.Pos()))
          break
        }
      }
    }
    return true
  })
}

PathEnclosingInterval

The ast/astutil package contains PathEnclosingInterval, which takes a token position and returns every AST node containing that position. Its home territory is text editors and similar position-driven tools, and it can be bent to answer this question as well:

func discoverNodeParentsPathInterval(pkg *packages.Package) {
  for _, fileAst := range pkg.Syntax {
    ast.Inspect(fileAst, func(n ast.Node) bool {
      if bexpr, ok := n.(*ast.BinaryExpr); ok && bexpr.Op == token.MUL {
        path, _ := astutil.PathEnclosingInterval(fileAst, bexpr.Pos(), bexpr.End())
        for i := len(path) - 1; i >= 0; i-- {
          if _, ok := path[i].(*ast.BinaryExpr); ok && path[i] != bexpr {
            fmt.Printf("found BinaryExpr(*) as a child of another binary expr: %v\n",
              fset.Position(n.Pos()))
            break
          }
        }
      }
      return true
    })
  }
}

This is included only for completeness; WithStack fits the problem far better.

Full code for all of the approaches is in the accompanying GitHub repository.

For comments, please send me an email.