blob: af5e17feeeab6e2208fff9feec9073b6f21ef225 [file] [log] [blame]
// Copyright 2018 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package inspector provides helper functions for traversal over the
// syntax trees of a package, including node filtering by type, and
// materialization of the traversal stack.
//
// During construction, the inspector does a complete traversal and
// builds a list of push/pop events and their node type. Subsequent
// method calls that request a traversal scan this list, rather than walk
// the AST, and perform type filtering using efficient bit sets.
//
// Experiments suggest the inspector's traversals are about 2.5x faster
// than ast.Inspect, but it may take around 5 traversals for this
// benefit to amortize the inspector's construction cost.
// If efficiency is the primary concern, do not use Inspector for
// one-off traversals.
package inspector
// There are four orthogonal features in a traversal:
// 1 type filtering
// 2 pruning
// 3 postorder calls to f
// 4 stack
// Rather than offer all of them in the API,
// only a few combinations are exposed:
// - Preorder is the fastest and has fewest features,
// but is the most commonly needed traversal.
// - Nodes and WithStack both provide pruning and postorder calls,
// even though few clients need it, because supporting two versions
// is not justified.
// More combinations could be supported by expressing them as
// wrappers around a more generic traversal, but this was measured
// and found to degrade performance significantly (30%).
import (
"go/ast"
)
// An Inspector provides methods for inspecting
// (traversing) the syntax trees of a package.
type Inspector struct {
events []event
}
// New returns an Inspector for the specified syntax trees.
func New(files []*ast.File) *Inspector {
return &Inspector{traverse(files)}
}
// An event represents a push or a pop
// of an ast.Node during a traversal.
type event struct {
node ast.Node
typ uint64 // typeOf(node)
index int // 1 + index of corresponding pop event, or 0 if this is a pop
}
// Preorder visits all the nodes of the files supplied to New in
// depth-first order. It calls f(n) for each node n before it visits
// n's children.
//
// The types argument, if non-empty, enables type-based filtering of
// events. The function f if is called only for nodes whose type
// matches an element of the types slice.
func (in *Inspector) Preorder(types []ast.Node, f func(ast.Node)) {
// Because it avoids postorder calls to f, and the pruning
// check, Preorder is almost twice as fast as Nodes. The two
// features seem to contribute similar slowdowns (~1.4x each).
mask := maskOf(types)
for i := 0; i < len(in.events); {
ev := in.events[i]
if ev.typ&mask != 0 {
if ev.index > 0 {
f(ev.node)
}
}
i++
}
}
// Nodes visits the nodes of the files supplied to New in depth-first
// order. It calls f(n, true) for each node n before it visits n's
// children. If f returns true, Nodes invokes f recursively for each
// of the non-nil children of the node, followed by a call of
// f(n, false).
//
// The types argument, if non-empty, enables type-based filtering of
// events. The function f if is called only for nodes whose type
// matches an element of the types slice.
func (in *Inspector) Nodes(types []ast.Node, f func(n ast.Node, push bool) (proceed bool)) {
mask := maskOf(types)
for i := 0; i < len(in.events); {
ev := in.events[i]
if ev.typ&mask != 0 {
if ev.index > 0 {
// push
if !f(ev.node, true) {
i = ev.index // jump to corresponding pop + 1
continue
}
} else {
// pop
f(ev.node, false)
}
}
i++
}
}
// WithStack visits nodes in a similar manner to Nodes, but it
// supplies each call to f an additional argument, the current
// traversal stack. The stack's first element is the outermost node,
// an *ast.File; its last is the innermost, n.
func (in *Inspector) WithStack(types []ast.Node, f func(n ast.Node, push bool, stack []ast.Node) (proceed bool)) {
mask := maskOf(types)
var stack []ast.Node
for i := 0; i < len(in.events); {
ev := in.events[i]
if ev.index > 0 {
// push
stack = append(stack, ev.node)
if ev.typ&mask != 0 {
if !f(ev.node, true, stack) {
i = ev.index
stack = stack[:len(stack)-1]
continue
}
}
} else {
// pop
if ev.typ&mask != 0 {
f(ev.node, false, stack)
}
stack = stack[:len(stack)-1]
}
i++
}
}
// traverse builds the table of events representing a traversal.
func traverse(files []*ast.File) []event {
// Preallocate approximate number of events
// based on source file extent.
// This makes traverse faster by 4x (!).
var extent int
for _, f := range files {
extent += int(f.End() - f.Pos())
}
// This estimate is based on the net/http package.
capacity := extent * 33 / 100
if capacity > 1e6 {
capacity = 1e6 // impose some reasonable maximum
}
events := make([]event, 0, capacity)
var stack []event
for _, f := range files {
ast.Inspect(f, func(n ast.Node) bool {
if n != nil {
// push
ev := event{
node: n,
typ: typeOf(n),
index: len(events), // push event temporarily holds own index
}
stack = append(stack, ev)
events = append(events, ev)
} else {
// pop
ev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
events[ev.index].index = len(events) + 1 // make push refer to pop
ev.index = 0 // turn ev into a pop event
events = append(events, ev)
}
return true
})
}
return events
}