src

cursor.go (17471B)

---

 // Copyright 2025 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
 
 import (
 	"fmt"
 	"go/ast"
 	"go/token"
 	"iter"
 	"reflect"
 	"strings"
 
 	"golang.org/x/tools/go/ast/edge"
 )
 
 // A Cursor represents an [ast.Node]. It is immutable.
 //
 // Two Cursors compare equal if they represent the same node.
 //
 // The zero value of Cursor is not valid.
 //
 // Call [Inspector.Root] to obtain a cursor for the virtual root node
 // of the traversal. This is the sole valid cursor for which [Cursor.Node]
 // returns nil.
 //
 // Use the following methods to navigate efficiently around the tree:
 //   - for ancestors, use [Cursor.Parent] and [Cursor.Enclosing];
 //   - for children, use [Cursor.Child], [Cursor.Children],
 //     [Cursor.FirstChild], and [Cursor.LastChild];
 //   - for siblings, use [Cursor.PrevSibling] and [Cursor.NextSibling];
 //   - for descendants, use [Cursor.FindByPos], [Cursor.FindNode],
 //     [Cursor.Inspect], and [Cursor.Preorder].
 //
 // Use the [Cursor.ChildAt] and [Cursor.ParentEdge] methods for
 // information about the edges in a tree: which field (and slice
 // element) of the parent node holds the child.
 type Cursor struct {
 	in    *Inspector
 	index int32 // index of push node; -1 for virtual root node
 }
 
 // Root returns a valid cursor for the virtual root node,
 // whose children are the files provided to [New].
 //
 // Its [Cursor.Node] method return nil.
 func (in *Inspector) Root() Cursor {
 	return Cursor{in, -1}
 }
 
 // At returns the cursor at the specified index in the traversal,
 // which must have been obtained from [Cursor.Index] on a Cursor
 // belonging to the same Inspector (see [Cursor.Inspector]).
 func (in *Inspector) At(index int32) Cursor {
 	if index < 0 {
 		panic("negative index")
 	}
 	if int(index) >= len(in.events) {
 		panic("index out of range for this inspector")
 	}
 	if in.events[index].index < index {
 		panic("invalid index") // (a push, not a pop)
 	}
 	return Cursor{in, index}
 }
 
 // Valid reports whether the cursor is valid.
 // The zero value of cursor is invalid.
 // Unless otherwise documented, it is not safe to call
 // any other method on an invalid cursor.
 func (c Cursor) Valid() bool {
 	return c.in != nil
 }
 
 // Inspector returns the cursor's Inspector.
 // It returns nil if the Cursor is not valid.
 func (c Cursor) Inspector() *Inspector { return c.in }
 
 // Index returns the index of this cursor position within the package.
 //
 // Clients should not assume anything about the numeric Index value
 // except that it increases monotonically throughout the traversal.
 // It is provided for use with [Inspector.At].
 //
 // Index must not be called on the Root node.
 func (c Cursor) Index() int32 {
 	if c.index < 0 {
 		panic("Index called on Root node")
 	}
 	return c.index
 }
 
 // Node returns the node at the current cursor position,
 // or nil for the cursor returned by [Inspector.Root].
 func (c Cursor) Node() ast.Node {
 	if c.index < 0 {
 		return nil
 	}
 	return c.in.events[c.index].node
 }
 
 // String returns information about the cursor's node, if any.
 func (c Cursor) String() string {
 	if !c.Valid() {
 		return "(invalid)"
 	}
 	if c.index < 0 {
 		return "(root)"
 	}
 	return reflect.TypeOf(c.Node()).String()
 }
 
 // GoString returns a string describing the cursor's path from the
 // root, if any.
 func (c Cursor) GoString() string {
 	if !c.Valid() {
 		return "(invalid)"
 	}
 	if c.index < 0 {
 		return "(root)"
 	}
 	// e.g "File.Decls[1].(*ast.GenDecl).Specs[0].(*ast.TypeSpec)"
 	//
 	// In hindsight even the File node should have reported a
 	// virtual ParentEdge of (Root_Files, i) where i is the index
 	// among the files passed to NewInspector. Then the path would
 	// read "(root).Files[i]", etc; but we missed the boat.
 	var buf strings.Builder
 	buf.WriteString("File")
 	var visit func(Cursor)
 	visit = func(c Cursor) {
 		ek, idx := c.ParentEdge()
 		if ek == edge.Invalid {
 			return // File
 		}
 		visit(c.Parent())
 		fmt.Fprintf(&buf, ".%s", ek.FieldName())
 		if idx >= 0 {
 			fmt.Fprintf(&buf, "[%d]", idx)
 		}
 		ftype := ek.FieldType()
 		if idx >= 0 {
 			ftype = ftype.Elem() // []T -> T
 		}
 		if ftype.Kind() == reflect.Interface {
 			fmt.Fprintf(&buf, ".(%T)", c.Node())
 		}
 	}
 	visit(c)
 	return buf.String()
 }
 
 // indices return the [start, end) half-open interval of event indices.
 func (c Cursor) indices() (int32, int32) {
 	if c.index < 0 {
 		return 0, int32(len(c.in.events)) // root: all events
 	} else {
 		return c.index, c.in.events[c.index].index + 1 // just one subtree
 	}
 }
 
 // Preorder returns an iterator over the nodes of the subtree
 // represented by c in depth-first order. Each node in the sequence is
 // represented by a Cursor that allows access to the Node, but may
 // also be used to start a new traversal, or to obtain the stack of
 // nodes enclosing the cursor.
 //
 // The traversal sequence is determined by [ast.Inspect]. 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.
 //
 // If you need control over descent into subtrees,
 // or need both pre- and post-order notifications, use [Cursor.Inspect]
 func (c Cursor) Preorder(types ...ast.Node) iter.Seq[Cursor] {
 	mask := maskOf(types)
 
 	return func(yield func(Cursor) bool) {
 		events := c.in.events
 
 		for i, limit := c.indices(); i < limit; {
 			ev := events[i]
 			if ev.index > i { // push?
 				if ev.typ&mask != 0 && !yield(Cursor{c.in, i}) {
 					break
 				}
 				pop := ev.index
 				if events[pop].typ&mask == 0 {
 					// Subtree does not contain types: skip.
 					i = pop + 1
 					continue
 				}
 			}
 			i++
 		}
 	}
 }
 
 // Inspect visits the nodes of the subtree represented by c in
 // depth-first order. It calls f(n) for each node n before it
 // visits n's children. If f returns true, Inspect invokes f
 // recursively for each of the non-nil children of the node.
 //
 // Each node is represented by a Cursor that allows access to the
 // Node, but may also be used to start a new traversal, or to obtain
 // the stack of nodes enclosing the cursor.
 //
 // The complete traversal sequence is determined by [ast.Inspect].
 // 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 (c Cursor) Inspect(types []ast.Node, f func(c Cursor) (descend bool)) {
 	mask := maskOf(types)
 	events := c.in.events
 	for i, limit := c.indices(); i < limit; {
 		ev := events[i]
 		if ev.index > i {
 			// push
 			pop := ev.index
 			if ev.typ&mask != 0 && !f(Cursor{c.in, i}) ||
 				events[pop].typ&mask == 0 {
 				// The user opted not to descend, or the
 				// subtree does not contain types:
 				// skip past the pop.
 				i = pop + 1
 				continue
 			}
 		}
 		i++
 	}
 }
 
 // Enclosing returns an iterator over the nodes enclosing the current
 // current node, starting with the Cursor itself.
 //
 // Enclosing must not be called on the Root node (whose [Cursor.Node] returns nil).
 //
 // The types argument, if non-empty, enables type-based filtering of
 // events: the sequence includes only enclosing nodes whose type
 // matches an element of the types slice.
 func (c Cursor) Enclosing(types ...ast.Node) iter.Seq[Cursor] {
 	if c.index < 0 {
 		panic("Cursor.Enclosing called on Root node")
 	}
 
 	mask := maskOf(types)
 
 	return func(yield func(Cursor) bool) {
 		events := c.in.events
 		for i := c.index; i >= 0; i = events[i].parent {
 			if events[i].typ&mask != 0 && !yield(Cursor{c.in, i}) {
 				break
 			}
 		}
 	}
 }
 
 // Parent returns the parent of the current node.
 //
 // Parent must not be called on the Root node (whose [Cursor.Node] returns nil).
 func (c Cursor) Parent() Cursor {
 	if c.index < 0 {
 		panic("Cursor.Parent called on Root node")
 	}
 
 	return Cursor{c.in, c.in.events[c.index].parent}
 }
 
 // ParentEdge returns the identity of the field in the parent node
 // that holds this cursor's node, and if it is a list, the index within it.
 //
 // For example, f(x, y) is a CallExpr whose three children are Idents.
 // f has edge kind [edge.CallExpr_Fun] and index -1.
 // x and y have kind [edge.CallExpr_Args] and indices 0 and 1, respectively.
 //
 // If called on a child of the Root node, it returns ([edge.Invalid], -1).
 //
 // ParentEdge must not be called on the Root node (whose [Cursor.Node] returns nil).
 func (c Cursor) ParentEdge() (edge.Kind, int) {
 	if c.index < 0 {
 		panic("Cursor.ParentEdge called on Root node")
 	}
 	events := c.in.events
 	pop := events[c.index].index
 	return unpackEdgeKindAndIndex(events[pop].parent)
 }
 
 // ParentEdgeKind returns the kind component of the result of [Cursor.ParentEdge].
 func (c Cursor) ParentEdgeKind() edge.Kind {
 	ek, _ := c.ParentEdge()
 	return ek
 }
 
 // ParentEdgeIndex returns the index component of the result of [Cursor.ParentEdge].
 func (c Cursor) ParentEdgeIndex() int {
 	_, index := c.ParentEdge()
 	return index
 }
 
 // ChildAt returns the cursor for the child of the
 // current node identified by its edge and index.
 // The index must be -1 if the edge.Kind is not a slice.
 // The indicated child node must exist.
 //
 // ChildAt must not be called on the Root node (whose [Cursor.Node] returns nil).
 //
 // Invariant: c.Parent().ChildAt(c.ParentEdge()) == c.
 func (c Cursor) ChildAt(k edge.Kind, idx int) Cursor {
 	target := packEdgeKindAndIndex(k, idx)
 
 	// Unfortunately there's no shortcut to looping.
 	events := c.in.events
 	i := c.index + 1
 	for {
 		pop := events[i].index
 		if pop < i {
 			break
 		}
 		if events[pop].parent == target {
 			return Cursor{c.in, i}
 		}
 		i = pop + 1
 	}
 	panic(fmt.Sprintf("ChildAt(%v, %d): no such child of %v", k, idx, c))
 }
 
 // Child returns the cursor for n, which must be a direct child of c's Node.
 //
 // Child must not be called on the Root node (whose [Cursor.Node] returns nil).
 func (c Cursor) Child(n ast.Node) Cursor {
 	if c.index < 0 {
 		panic("Cursor.Child called on Root node")
 	}
 
 	if false {
 		// reference implementation
 		for child := range c.Children() {
 			if child.Node() == n {
 				return child
 			}
 		}
 
 	} else {
 		// optimized implementation
 		events := c.in.events
 		for i := c.index + 1; events[i].index > i; i = events[i].index + 1 {
 			if events[i].node == n {
 				return Cursor{c.in, i}
 			}
 		}
 	}
 	panic(fmt.Sprintf("Child(%T): not a child of %v", n, c))
 }
 
 // NextSibling returns the cursor for the next sibling node in the same list
 // (for example, of files, decls, specs, statements, fields, or expressions) as
 // the current node. It returns (zero, false) if the node is the last node in
 // the list, or is not part of a list.
 //
 // NextSibling must not be called on the Root node.
 //
 // See note at [Cursor.Children].
 func (c Cursor) NextSibling() (Cursor, bool) {
 	if c.index < 0 {
 		panic("Cursor.NextSibling called on Root node")
 	}
 
 	events := c.in.events
 	i := events[c.index].index + 1 // after corresponding pop
 	if i < int32(len(events)) {
 		if events[i].index > i { // push?
 			return Cursor{c.in, i}, true
 		}
 	}
 	return Cursor{}, false
 }
 
 // PrevSibling returns the cursor for the previous sibling node in the
 // same list (for example, of files, decls, specs, statements, fields,
 // or expressions) as the current node. It returns zero if the node is
 // the first node in the list, or is not part of a list.
 //
 // It must not be called on the Root node.
 //
 // See note at [Cursor.Children].
 func (c Cursor) PrevSibling() (Cursor, bool) {
 	if c.index < 0 {
 		panic("Cursor.PrevSibling called on Root node")
 	}
 
 	events := c.in.events
 	i := c.index - 1
 	if i >= 0 {
 		if j := events[i].index; j < i { // pop?
 			return Cursor{c.in, j}, true
 		}
 	}
 	return Cursor{}, false
 }
 
 // FirstChild returns the first direct child of the current node,
 // or zero if it has no children.
 func (c Cursor) FirstChild() (Cursor, bool) {
 	events := c.in.events
 	i := c.index + 1                                   // i=0 if c is root
 	if i < int32(len(events)) && events[i].index > i { // push?
 		return Cursor{c.in, i}, true
 	}
 	return Cursor{}, false
 }
 
 // LastChild returns the last direct child of the current node,
 // or zero if it has no children.
 func (c Cursor) LastChild() (Cursor, bool) {
 	events := c.in.events
 	if c.index < 0 { // root?
 		if len(events) > 0 {
 			// return push of final event (a pop)
 			return Cursor{c.in, events[len(events)-1].index}, true
 		}
 	} else {
 		j := events[c.index].index - 1 // before corresponding pop
 		// Inv: j == c.index if c has no children
 		//  or  j is last child's pop.
 		if j > c.index { // c has children
 			return Cursor{c.in, events[j].index}, true
 		}
 	}
 	return Cursor{}, false
 }
 
 // Children returns an iterator over the direct children of the
 // current node, if any.
 //
 // When using Children, NextChild, and PrevChild, bear in mind that a
 // Node's children may come from different fields, some of which may
 // be lists of nodes without a distinguished intervening container
 // such as [ast.BlockStmt].
 //
 // For example, [ast.CaseClause] has a field List of expressions and a
 // field Body of statements, so the children of a CaseClause are a mix
 // of expressions and statements. Other nodes that have "uncontained"
 // list fields include:
 //
 //   - [ast.ValueSpec] (Names, Values)
 //   - [ast.CompositeLit] (Type, Elts)
 //   - [ast.IndexListExpr] (X, Indices)
 //   - [ast.CallExpr] (Fun, Args)
 //   - [ast.AssignStmt] (Lhs, Rhs)
 //
 // So, do not assume that the previous sibling of an ast.Stmt is also
 // an ast.Stmt, or if it is, that they are executed sequentially,
 // unless you have established that, say, its parent is a BlockStmt
 // or its [Cursor.ParentEdge] is [edge.BlockStmt_List].
 // For example, given "for S1; ; S2 {}", the predecessor of S2 is S1,
 // even though they are not executed in sequence.
 func (c Cursor) Children() iter.Seq[Cursor] {
 	return func(yield func(Cursor) bool) {
 		c, ok := c.FirstChild()
 		for ok && yield(c) {
 			c, ok = c.NextSibling()
 		}
 	}
 }
 
 // Contains reports whether c contains or is equal to c2.
 //
 // Both Cursors must belong to the same [Inspector];
 // neither may be its Root node.
 func (c Cursor) Contains(c2 Cursor) bool {
 	if c.in != c2.in {
 		panic("different inspectors")
 	}
 	events := c.in.events
 	return c.index <= c2.index && events[c2.index].index <= events[c.index].index
 }
 
 // FindNode returns the cursor for node n if it belongs to the subtree
 // rooted at c. It returns zero if n is not found.
 func (c Cursor) FindNode(n ast.Node) (Cursor, bool) {
 
 	// FindNode is equivalent to this code,
 	// but more convenient and 15-20% faster:
 	if false {
 		for candidate := range c.Preorder(n) {
 			if candidate.Node() == n {
 				return candidate, true
 			}
 		}
 		return Cursor{}, false
 	}
 
 	// TODO(adonovan): opt: should we assume Node.Pos is accurate
 	// and combine type-based filtering with position filtering
 	// like FindByPos?
 
 	mask := maskOf([]ast.Node{n})
 	events := c.in.events
 
 	for i, limit := c.indices(); i < limit; i++ {
 		ev := events[i]
 		if ev.index > i { // push?
 			if ev.typ&mask != 0 && ev.node == n {
 				return Cursor{c.in, i}, true
 			}
 			pop := ev.index
 			if events[pop].typ&mask == 0 {
 				// Subtree does not contain type of n: skip.
 				i = pop
 			}
 		}
 	}
 	return Cursor{}, false
 }
 
 // FindByPos returns the cursor for the innermost node n in the tree
 // rooted at c such that n.Pos() <= start && end <= n.End().
 // (For an *ast.File, it uses the bounds n.FileStart-n.FileEnd.)
 //
 // An empty range (start == end) between two adjacent nodes is
 // considered to belong to the first node.
 //
 // It returns zero if none is found.
 // Precondition: start <= end.
 //
 // See also [astutil.PathEnclosingInterval], which
 // tolerates adjoining whitespace.
 func (c Cursor) FindByPos(start, end token.Pos) (Cursor, bool) {
 	if end < start {
 		panic("end < start")
 	}
 	events := c.in.events
 
 	// This algorithm could be implemented using c.Inspect,
 	// but it is about 2.5x slower.
 
 	// best is the push-index of the latest (=innermost) node containing range.
 	// (Beware: latest is not always innermost because FuncDecl.{Name,Type} overlap.)
 	best := int32(-1)
 	for i, limit := c.indices(); i < limit; i++ {
 		ev := events[i]
 		if ev.index > i { // push?
 			n := ev.node
 			var nodeEnd token.Pos
 			if file, ok := n.(*ast.File); ok {
 				nodeEnd = file.FileEnd
 				// Note: files may be out of Pos order.
 				if file.FileStart > start {
 					i = ev.index // disjoint, after; skip to next file
 					continue
 				}
 			} else {
 				// Edge case: FuncDecl.Name and .Type overlap:
 				// Don't update best from Name to FuncDecl.Type.
 				//
 				// The condition can be read as:
 				// - n is FuncType
 				// - n.parent is FuncDecl
 				// - best is strictly beneath the FuncDecl
 				if ev.typ == 1<<nFuncType &&
 					events[ev.parent].typ == 1<<nFuncDecl &&
 					best > ev.parent {
 					continue
 				}
 
 				nodeEnd = n.End()
 				if n.Pos() > start {
 					break // disjoint, after; stop
 				}
 			}
 
 			// Inv: node.{Pos,FileStart} <= start
 			if end <= nodeEnd {
 				// node fully contains target range
 				best = i
 
 				// Don't search beyond end of the first match.
 				// This is important only for an empty range (start=end)
 				// between two adjoining nodes, which would otherwise
 				// match both nodes; we want to match only the first.
 				limit = ev.index
 			} else if nodeEnd < start {
 				i = ev.index // disjoint, before; skip forward
 			}
 		}
 	}
 	if best >= 0 {
 		return Cursor{c.in, best}, true
 	}
 	return Cursor{}, false
 }