Source file src/cmd/vendor/golang.org/x/tools/internal/astutil/util.go
1 // Copyright 2025 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package astutil 6 7 import ( 8 "fmt" 9 "go/ast" 10 "go/printer" 11 "go/token" 12 "strings" 13 14 "golang.org/x/tools/go/ast/edge" 15 "golang.org/x/tools/go/ast/inspector" 16 "golang.org/x/tools/internal/moreiters" 17 ) 18 19 // PreorderStack traverses the tree rooted at root, 20 // calling f before visiting each node. 21 // 22 // Each call to f provides the current node and traversal stack, 23 // consisting of the original value of stack appended with all nodes 24 // from root to n, excluding n itself. (This design allows calls 25 // to PreorderStack to be nested without double counting.) 26 // 27 // If f returns false, the traversal skips over that subtree. Unlike 28 // [ast.Inspect], no second call to f is made after visiting node n. 29 // In practice, the second call is nearly always used only to pop the 30 // stack, and it is surprisingly tricky to do this correctly; see 31 // https://go.dev/issue/73319. 32 // 33 // TODO(adonovan): replace with [ast.PreorderStack] when go1.25 is assured. 34 func PreorderStack(root ast.Node, stack []ast.Node, f func(n ast.Node, stack []ast.Node) bool) { 35 before := len(stack) 36 ast.Inspect(root, func(n ast.Node) bool { 37 if n != nil { 38 if !f(n, stack) { 39 // Do not push, as there will be no corresponding pop. 40 return false 41 } 42 stack = append(stack, n) // push 43 } else { 44 stack = stack[:len(stack)-1] // pop 45 } 46 return true 47 }) 48 if len(stack) != before { 49 panic("push/pop mismatch") 50 } 51 } 52 53 // NodeContains reports whether the Pos/End range of node n encloses 54 // the given range. 55 // 56 // It is inclusive of both end points, to allow hovering (etc) when 57 // the cursor is immediately after a node. 58 // 59 // Like [NodeRange], it treats the range of an [ast.File] as the 60 // file's complete extent. 61 // 62 // Precondition: n must not be nil. 63 func NodeContains(n ast.Node, rng Range) bool { 64 return NodeRange(n).Contains(rng) 65 } 66 67 // NodeContainsPos reports whether the Pos/End range of node n encloses 68 // the given pos. 69 // 70 // Like [NodeRange], it treats the range of an [ast.File] as the 71 // file's complete extent. 72 func NodeContainsPos(n ast.Node, pos token.Pos) bool { 73 return NodeRange(n).ContainsPos(pos) 74 } 75 76 // IsChildOf reports whether cur.ParentEdge is ek. 77 // 78 // TODO(adonovan): promote to a method of Cursor. 79 func IsChildOf(cur inspector.Cursor, ek edge.Kind) bool { 80 got, _ := cur.ParentEdge() 81 return got == ek 82 } 83 84 // EnclosingFile returns the syntax tree for the file enclosing c. 85 // 86 // TODO(adonovan): promote this to a method of Cursor. 87 func EnclosingFile(c inspector.Cursor) *ast.File { 88 c, _ = moreiters.First(c.Enclosing((*ast.File)(nil))) 89 return c.Node().(*ast.File) 90 } 91 92 // DocComment returns the doc comment for a node, if any. 93 func DocComment(n ast.Node) *ast.CommentGroup { 94 switch n := n.(type) { 95 case *ast.FuncDecl: 96 return n.Doc 97 case *ast.GenDecl: 98 return n.Doc 99 case *ast.ValueSpec: 100 return n.Doc 101 case *ast.TypeSpec: 102 return n.Doc 103 case *ast.File: 104 return n.Doc 105 case *ast.ImportSpec: 106 return n.Doc 107 case *ast.Field: 108 return n.Doc 109 } 110 return nil 111 } 112 113 // Format returns a string representation of the node n. 114 func Format(fset *token.FileSet, n ast.Node) string { 115 var buf strings.Builder 116 printer.Fprint(&buf, fset, n) // ignore errors 117 return buf.String() 118 } 119 120 // -- Range -- 121 122 // Range is a Pos interval. 123 // It implements [analysis.Range] and [ast.Node]. 124 type Range struct{ Start, EndPos token.Pos } 125 126 // RangeOf constructs a Range. 127 // 128 // RangeOf exists to pacify the "unkeyed literal" (composites) vet 129 // check. It would be nice if there were a way for a type to add 130 // itself to the allowlist. 131 func RangeOf(start, end token.Pos) Range { return Range{start, end} } 132 133 // NodeRange returns the extent of node n as a Range. 134 // 135 // For unfortunate historical reasons, the Pos/End extent of an 136 // ast.File runs from the start of its package declaration---excluding 137 // copyright comments, build tags, and package documentation---to the 138 // end of its last declaration, excluding any trailing comments. So, 139 // as a special case, if n is an [ast.File], NodeContains uses 140 // n.FileStart <= pos && pos <= n.FileEnd to report whether the 141 // position lies anywhere within the file. 142 func NodeRange(n ast.Node) Range { 143 if file, ok := n.(*ast.File); ok { 144 return Range{file.FileStart, file.FileEnd} // entire file 145 } 146 return Range{n.Pos(), n.End()} 147 } 148 149 func (r Range) Pos() token.Pos { return r.Start } 150 func (r Range) End() token.Pos { return r.EndPos } 151 152 // ContainsPos reports whether the range (inclusive of both end points) 153 // includes the specified position. 154 func (r Range) ContainsPos(pos token.Pos) bool { 155 return r.Contains(RangeOf(pos, pos)) 156 } 157 158 // Contains reports whether the range (inclusive of both end points) 159 // includes the specified range. 160 func (r Range) Contains(rng Range) bool { 161 return r.Start <= rng.Start && rng.EndPos <= r.EndPos 162 } 163 164 // IsValid reports whether the range is valid. 165 func (r Range) IsValid() bool { return r.Start.IsValid() && r.Start <= r.EndPos } 166 167 // -- 168 169 // Select returns the syntax nodes identified by a user's text 170 // selection. It returns three nodes: the innermost node that wholly 171 // encloses the selection; and the first and last nodes that are 172 // wholly enclosed by the selection. 173 // 174 // For example, given this selection: 175 // 176 // { f(); g(); /* comment */ } 177 // ~~~~~~~~~~~ 178 // 179 // Select returns the enclosing BlockStmt, the f() CallExpr, and the g() CallExpr. 180 // 181 // Callers that require exactly one syntax tree (e.g. just f() or just 182 // g()) should check that the returned start and end nodes are 183 // identical. 184 // 185 // This function is intended to be called early in the handling of a 186 // user's request, since it is tolerant of sloppy selection including 187 // extraneous whitespace and comments. Use it in new code instead of 188 // PathEnclosingInterval. When the exact extent of a node is known, 189 // use [Cursor.FindByPos] instead. 190 func Select(curFile inspector.Cursor, start, end token.Pos) (_enclosing, _start, _end inspector.Cursor, _ error) { 191 curEnclosing, ok := curFile.FindByPos(start, end) 192 if !ok { 193 return noCursor, noCursor, noCursor, fmt.Errorf("invalid selection") 194 } 195 196 // Find the first and last node wholly within the (start, end) range. 197 // We'll narrow the effective selection to them, to exclude whitespace. 198 // (This matches the functionality of PathEnclosingInterval.) 199 var curStart, curEnd inspector.Cursor 200 rng := RangeOf(start, end) 201 for cur := range curEnclosing.Preorder() { 202 if rng.Contains(NodeRange(cur.Node())) { 203 // The start node has the least Pos. 204 if !CursorValid(curStart) { 205 curStart = cur 206 } 207 // The end node has the greatest End. 208 // End positions do not change monotonically, 209 // so we must compute the max. 210 if !CursorValid(curEnd) || 211 cur.Node().End() > curEnd.Node().End() { 212 curEnd = cur 213 } 214 } 215 } 216 if !CursorValid(curStart) { 217 return noCursor, noCursor, noCursor, fmt.Errorf("no syntax selected") 218 } 219 return curEnclosing, curStart, curEnd, nil 220 } 221 222 // CursorValid reports whether the cursor is valid. 223 // 224 // A valid cursor may yet be the virtual root node, 225 // cur.Inspector.Root(), which has no [Cursor.Node]. 226 // 227 // TODO(adonovan): move to cursorutil package, and move that package into x/tools. 228 // Ultimately, make this a method of Cursor. Needs a proposal. 229 func CursorValid(cur inspector.Cursor) bool { 230 return cur.Inspector() != nil 231 } 232 233 var noCursor inspector.Cursor 234