Debian Codegraph @

internal/typesinternal/typeindex/typeindex.go

raw
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 typeindex provides an [Index] of type information for a
6 // package, allowing efficient lookup of, say, whether a given symbol
7 // is referenced and, if so, where from; or of the [inspector.Cursor] for
8 // the declaration of a particular [types.Object] symbol.
9 package typeindex
10
11 import (
12 "encoding/binary"
13 "go/ast"
14 "go/types"
15 "iter"
16
17 "golang.org/x/tools/go/ast/edge"
18 "golang.org/x/tools/go/ast/inspector"
19 "golang.org/x/tools/go/types/typeutil"
20 )
21
22 // IsPackageLevel reports whether obj is a package-level symbol.
23 func IsPackageLevel(obj types.Object) bool {
24 return obj.Pkg() != nil && obj.Parent() == obj.Pkg().Scope()
25 }
26
27 // New constructs an Index for the package of type-annotated syntax
28 //
29 // TODO(adonovan): accept a FileSet too?
30 // We regret not requiring one in inspector.New.
31 func New(inspect *inspector.Inspector, pkg *types.Package, info *types.Info) *Index {
32 ix := &Index{
33 inspect: inspect,
34 info: info,
35 packages: make(map[string]*types.Package),
36 def: make(map[types.Object]inspector.Cursor),
37 uses: make(map[types.Object]*uses),
38 }
39
40 addPackage := func(pkg2 *types.Package) {
41 if pkg2 != nil && pkg2 != pkg {
42 ix.packages[pkg2.Path()] = pkg2
43 }
44 }
45
46 for cur := range inspect.Root().Preorder((*ast.ImportSpec)(nil), (*ast.Ident)(nil)) {
47 switch n := cur.Node().(type) {
48 case *ast.ImportSpec:
49 // Index direct imports, including blank ones.
50 if pkgname := info.PkgNameOf(n); pkgname != nil {
51 addPackage(pkgname.Imported())
52 }
53
54 case *ast.Ident:
55 // Index all defining and using identifiers.
56 if obj := info.Defs[n]; obj != nil {
57 ix.def[obj] = cur
58 }
59
60 if obj := info.Uses[n]; obj != nil {
61 // Index indirect dependencies (via fields and methods).
62 if !IsPackageLevel(obj) {
63 addPackage(obj.Pkg())
64 }
65
66 us, ok := ix.uses[obj]
67 if !ok {
68 us = &uses{}
69 us.code = us.initial[:0]
70 ix.uses[obj] = us
71 }
72 delta := cur.Index() - us.last
73 if delta < 0 {
74 panic("non-monotonic")
75 }
76 us.code = binary.AppendUvarint(us.code, uint64(delta))
77 us.last = cur.Index()
78 }
79 }
80 }
81 return ix
82 }
83
84 // An Index holds an index mapping [types.Object] symbols to their syntax.
85 // In effect, it is the inverse of [types.Info].
86 type Index struct {
87 inspect *inspector.Inspector
88 info *types.Info
89 packages map[string]*types.Package // packages of all symbols referenced from this package
90 def map[types.Object]inspector.Cursor // Cursor of *ast.Ident that defines the Object
91 uses map[types.Object]*uses // Cursors of *ast.Idents that use the Object
92 }
93
94 // A uses holds the list of Cursors of Idents that use a given symbol.
95 //
96 // The Uses map of [types.Info] is substantial, so it pays to compress
97 // its inverse mapping here, both in space and in CPU due to reduced
98 // allocation. A Cursor is 2 words; a Cursor.Index is 4 bytes; but
99 // since Cursors are naturally delivered in ascending order, we can
100 // use varint-encoded deltas at a cost of only ~1.7-2.2 bytes per use.
101 //
102 // Many variables have only one or two uses, so their encoded uses may
103 // fit in the 4 bytes of initial, saving further CPU and space
104 // essentially for free since the struct's size class is 4 words.
105 type uses struct {
106 code []byte // varint-encoded deltas of successive Cursor.Index values
107 last int32 // most recent Cursor.Index value; used during encoding
108 initial [4]byte // use slack in size class as initial space for code
109 }
110
111 // Uses returns the sequence of Cursors of [*ast.Ident]s in this package
112 // that refer to obj. If obj is nil, the sequence is empty.
113 func (ix *Index) Uses(obj types.Object) iter.Seq[inspector.Cursor] {
114 return func(yield func(inspector.Cursor) bool) {
115 if uses := ix.uses[obj]; uses != nil {
116 var last int32
117 for code := uses.code; len(code) > 0; {
118 delta, n := binary.Uvarint(code)
119 last += int32(delta)
120 if !yield(ix.inspect.At(last)) {
121 return
122 }
123 code = code[n:]
124 }
125 }
126 }
127 }
128
129 // Used reports whether any of the specified objects are used, in
130 // other words, obj != nil && Uses(obj) is non-empty for some obj in objs.
131 //
132 // (This treatment of nil allows Used to be called directly on the
133 // result of [Index.Object] so that analyzers can conveniently skip
134 // packages that don't use a symbol of interest.)
135 func (ix *Index) Used(objs ...types.Object) bool {
136 for _, obj := range objs {
137 if obj != nil && ix.uses[obj] != nil {
138 return true
139 }
140 }
141 return false
142 }
143
144 // Def returns the Cursor of the [*ast.Ident] in this package
145 // that declares the specified object, if any.
146 func (ix *Index) Def(obj types.Object) (inspector.Cursor, bool) {
147 cur, ok := ix.def[obj]
148 return cur, ok
149 }
150
151 // Package returns the package of the specified path,
152 // or nil if it is not referenced from this package.
153 func (ix *Index) Package(path string) *types.Package {
154 return ix.packages[path]
155 }
156
157 // Object returns the package-level symbol name within the package of
158 // the specified path, or nil if the package or symbol does not exist
159 // or is not visible from this package.
160 func (ix *Index) Object(path, name string) types.Object {
161 if pkg := ix.Package(path); pkg != nil {
162 return pkg.Scope().Lookup(name)
163 }
164 return nil
165 }
166
167 // Selection returns the named method or field belonging to the
168 // package-level type returned by Object(path, typename).
169 func (ix *Index) Selection(path, typename, name string) types.Object {
170 if obj := ix.Object(path, typename); obj != nil {
171 if tname, ok := obj.(*types.TypeName); ok {
172 obj, _, _ := types.LookupFieldOrMethod(tname.Type(), true, obj.Pkg(), name)
173 return obj
174 }
175 }
176 return nil
177 }
178
179 // Calls returns the sequence of cursors for *ast.CallExpr nodes that
180 // call the specified callee, as defined by [typeutil.Callee].
181 // If callee is nil, the sequence is empty.
182 func (ix *Index) Calls(callee types.Object) iter.Seq[inspector.Cursor] {
183 return func(yield func(inspector.Cursor) bool) {
184 for cur := range ix.Uses(callee) {
185 ek, _ := cur.ParentEdge()
186
187 // The call may be of the form f() or x.f(),
188 // optionally with parens; ascend from f to call.
189 //
190 // It is tempting but wrong to use the first
191 // CallExpr ancestor: we have to make sure the
192 // ident is in the CallExpr.Fun position, otherwise
193 // f(f, f) would have two spurious matches.
194 // Avoiding Enclosing is also significantly faster.
195
196 // inverse unparen: f -> (f)
197 for ek == edge.ParenExpr_X {
198 cur = cur.Parent()
199 ek, _ = cur.ParentEdge()
200 }
201
202 // ascend selector: f -> x.f
203 if ek == edge.SelectorExpr_Sel {
204 cur = cur.Parent()
205 ek, _ = cur.ParentEdge()
206 }
207
208 // inverse unparen again
209 for ek == edge.ParenExpr_X {
210 cur = cur.Parent()
211 ek, _ = cur.ParentEdge()
212 }
213
214 // ascend from f or x.f to call
215 if ek == edge.CallExpr_Fun {
216 curCall := cur.Parent()
217 call := curCall.Node().(*ast.CallExpr)
218 if typeutil.Callee(ix.info, call) == callee {
219 if !yield(curCall) {
220 return
221 }
222 }
223 }
224 }
225 }
226 }