1 // Copyright 2013 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 ssa
6 7 // This file defines a number of miscellaneous utility functions.
8 9 import (
10 "fmt"
11 "go/ast"
12 "go/token"
13 "go/types"
14 "io"
15 "os"
16 "sync"
17 _ "unsafe" // for go:linkname hack
18 19 "golang.org/x/tools/go/types/typeutil"
20 "golang.org/x/tools/internal/typeparams"
21 "golang.org/x/tools/internal/typesinternal"
22 )
23 24 type unit struct{}
25 26 //// Sanity checking utilities
27 28 // assert panics with the message msg if p is false.
29 // Avoid combining with expensive string formatting.
30 func assert(p bool, msg string) {
31 if !p {
32 panic(msg)
33 }
34 }
35 36 //// AST utilities
37 38 // isBlankIdent returns true iff e is an Ident with name "_".
39 // They have no associated types.Object, and thus no type.
40 func isBlankIdent(e ast.Expr) bool {
41 id, ok := e.(*ast.Ident)
42 return ok && id.Name == "_"
43 }
44 45 //// Type utilities. Some of these belong in go/types.
46 47 // isNonTypeParamInterface reports whether t is an interface type but not a type parameter.
48 func isNonTypeParamInterface(t types.Type) bool {
49 return !typeparams.IsTypeParam(t) && types.IsInterface(t)
50 }
51 52 // isBasic reports whether t is a basic type.
53 // t is assumed to be an Underlying type (not Named or Alias).
54 func isBasic(t types.Type) bool {
55 _, ok := t.(*types.Basic)
56 return ok
57 }
58 59 // isString reports whether t is exactly a string type.
60 // t is assumed to be an Underlying type (not Named or Alias).
61 func isString(t types.Type) bool {
62 basic, ok := t.(*types.Basic)
63 return ok && basic.Info()&types.IsString != 0
64 }
65 66 // isByteSlice reports whether t is of the form []~bytes.
67 // t is assumed to be an Underlying type (not Named or Alias).
68 func isByteSlice(t types.Type) bool {
69 if b, ok := t.(*types.Slice); ok {
70 e, _ := b.Elem().Underlying().(*types.Basic)
71 return e != nil && e.Kind() == types.Byte
72 }
73 return false
74 }
75 76 // isRuneSlice reports whether t is of the form []~runes.
77 // t is assumed to be an Underlying type (not Named or Alias).
78 func isRuneSlice(t types.Type) bool {
79 if b, ok := t.(*types.Slice); ok {
80 e, _ := b.Elem().Underlying().(*types.Basic)
81 return e != nil && e.Kind() == types.Rune
82 }
83 return false
84 }
85 86 // isBasicConvTypes returns true when the type set of a type
87 // can be one side of a Convert operation. This is when:
88 // - All are basic, []byte, or []rune.
89 // - At least 1 is basic.
90 // - At most 1 is []byte or []rune.
91 func isBasicConvTypes(typ types.Type) bool {
92 basics, cnt := 0, 0
93 ok := underIs(typ, func(t types.Type) bool {
94 cnt++
95 if isBasic(t) {
96 basics++
97 return true
98 }
99 return isByteSlice(t) || isRuneSlice(t)
100 })
101 return ok && basics >= 1 && cnt-basics <= 1
102 }
103 104 // isPointer reports whether t's underlying type is a pointer.
105 func isPointer(t types.Type) bool {
106 return is[*types.Pointer](t.Underlying())
107 }
108 109 // isPointerCore reports whether t's core type is a pointer.
110 //
111 // (Most pointer manipulation is related to receivers, in which case
112 // isPointer is appropriate. tecallers can use isPointer(t).
113 func isPointerCore(t types.Type) bool {
114 return is[*types.Pointer](typeparams.CoreType(t))
115 }
116 117 func is[T any](x any) bool {
118 _, ok := x.(T)
119 return ok
120 }
121 122 // recvType returns the receiver type of method obj.
123 func recvType(obj *types.Func) types.Type {
124 return obj.Signature().Recv().Type()
125 }
126 127 // fieldOf returns the index'th field of the (core type of) a struct type;
128 // otherwise returns nil.
129 func fieldOf(typ types.Type, index int) *types.Var {
130 if st, ok := typeparams.CoreType(typ).(*types.Struct); ok {
131 if 0 <= index && index < st.NumFields() {
132 return st.Field(index)
133 }
134 }
135 return nil
136 }
137 138 // isUntyped reports whether typ is the type of an untyped constant.
139 func isUntyped(typ types.Type) bool {
140 // No Underlying/Unalias: untyped constant types cannot be Named or Alias.
141 b, ok := typ.(*types.Basic)
142 return ok && b.Info()&types.IsUntyped != 0
143 }
144 145 // declaredWithin reports whether an object is declared within a function.
146 //
147 // obj must not be a method or a field.
148 func declaredWithin(obj types.Object, fn *types.Func) bool {
149 if obj.Pos() != token.NoPos {
150 return fn.Scope().Contains(obj.Pos()) // trust the positions if they exist.
151 }
152 if fn.Pkg() != obj.Pkg() {
153 return false // fast path for different packages
154 }
155 156 // Traverse Parent() scopes for fn.Scope().
157 for p := obj.Parent(); p != nil; p = p.Parent() {
158 if p == fn.Scope() {
159 return true
160 }
161 }
162 return false
163 }
164 165 // logStack prints the formatted "start" message to stderr and
166 // returns a closure that prints the corresponding "end" message.
167 // Call using 'defer logStack(...)()' to show builder stack on panic.
168 // Don't forget trailing parens!
169 func logStack(format string, args ...any) func() {
170 msg := fmt.Sprintf(format, args...)
171 io.WriteString(os.Stderr, msg)
172 io.WriteString(os.Stderr, "\n")
173 return func() {
174 io.WriteString(os.Stderr, msg)
175 io.WriteString(os.Stderr, " end\n")
176 }
177 }
178 179 // newVar creates a 'var' for use in a types.Tuple.
180 func newVar(name string, typ types.Type) *types.Var {
181 return types.NewParam(token.NoPos, nil, name, typ)
182 }
183 184 // anonVar creates an anonymous 'var' for use in a types.Tuple.
185 func anonVar(typ types.Type) *types.Var {
186 return newVar("", typ)
187 }
188 189 var lenResults = types.NewTuple(anonVar(tInt))
190 191 // makeLen returns the len builtin specialized to type func(T)int.
192 func makeLen(T types.Type) *Builtin {
193 lenParams := types.NewTuple(anonVar(T))
194 return &Builtin{
195 name: "len",
196 sig: types.NewSignatureType(nil, nil, nil, lenParams, lenResults, false),
197 }
198 }
199 200 // receiverTypeArgs returns the type arguments to a method's receiver.
201 // Returns an empty list if the receiver does not have type arguments.
202 func receiverTypeArgs(method *types.Func) []types.Type {
203 recv := method.Signature().Recv()
204 _, named := typesinternal.ReceiverNamed(recv)
205 if named == nil {
206 return nil // recv is anonymous struct/interface
207 }
208 ts := named.TypeArgs()
209 if ts.Len() == 0 {
210 return nil
211 }
212 targs := make([]types.Type, ts.Len())
213 for i := 0; i < ts.Len(); i++ {
214 targs[i] = ts.At(i)
215 }
216 return targs
217 }
218 219 // recvAsFirstArg takes a method signature and returns a function
220 // signature with receiver as the first parameter.
221 func recvAsFirstArg(sig *types.Signature) *types.Signature {
222 params := make([]*types.Var, 0, 1+sig.Params().Len())
223 params = append(params, sig.Recv())
224 for v := range sig.Params().Variables() {
225 params = append(params, v)
226 }
227 return types.NewSignatureType(nil, nil, nil, types.NewTuple(params...), sig.Results(), sig.Variadic())
228 }
229 230 // instance returns whether an expression is a simple or qualified identifier
231 // that is a generic instantiation.
232 func instance(info *types.Info, expr ast.Expr) bool {
233 // Compare the logic here against go/types.instantiatedIdent,
234 // which also handles *IndexExpr and *IndexListExpr.
235 var id *ast.Ident
236 switch x := expr.(type) {
237 case *ast.Ident:
238 id = x
239 case *ast.SelectorExpr:
240 id = x.Sel
241 default:
242 return false
243 }
244 _, ok := info.Instances[id]
245 return ok
246 }
247 248 // instanceArgs returns the Instance[id].TypeArgs as a slice.
249 func instanceArgs(info *types.Info, id *ast.Ident) []types.Type {
250 targList := info.Instances[id].TypeArgs
251 if targList == nil {
252 return nil
253 }
254 255 targs := make([]types.Type, targList.Len())
256 for i, n := 0, targList.Len(); i < n; i++ {
257 targs[i] = targList.At(i)
258 }
259 return targs
260 }
261 262 // Mapping of a type T to a canonical instance C s.t. types.Identical(T, C).
263 // Thread-safe.
264 type canonizer struct {
265 mu sync.Mutex
266 types typeutil.Map // map from type to a canonical instance
267 lists typeListMap // map from a list of types to a canonical instance
268 }
269 270 func newCanonizer() *canonizer {
271 c := &canonizer{}
272 h := typeutil.MakeHasher()
273 c.types.SetHasher(h)
274 c.lists.hasher = h
275 return c
276 }
277 278 // List returns a canonical representative of a list of types.
279 // Representative of the empty list is nil.
280 func (c *canonizer) List(ts []types.Type) *typeList {
281 if len(ts) == 0 {
282 return nil
283 }
284 285 unaliasAll := func(ts []types.Type) []types.Type {
286 // Is there some top level alias?
287 var found bool
288 for _, t := range ts {
289 if _, ok := t.(*types.Alias); ok {
290 found = true
291 break
292 }
293 }
294 if !found {
295 return ts // no top level alias
296 }
297 298 cp := make([]types.Type, len(ts)) // copy with top level aliases removed.
299 for i, t := range ts {
300 cp[i] = types.Unalias(t)
301 }
302 return cp
303 }
304 l := unaliasAll(ts)
305 306 c.mu.Lock()
307 defer c.mu.Unlock()
308 return c.lists.rep(l)
309 }
310 311 // Type returns a canonical representative of type T.
312 // Removes top-level aliases.
313 //
314 // For performance, reasons the canonical instance is order-dependent,
315 // and may contain deeply nested aliases.
316 func (c *canonizer) Type(T types.Type) types.Type {
317 T = types.Unalias(T) // remove the top level alias.
318 319 c.mu.Lock()
320 defer c.mu.Unlock()
321 322 if r := c.types.At(T); r != nil {
323 return r.(types.Type)
324 }
325 c.types.Set(T, T)
326 return T
327 }
328 329 // A type for representing a canonized list of types.
330 type typeList []types.Type
331 332 func (l *typeList) identical(ts []types.Type) bool {
333 if l == nil {
334 return len(ts) == 0
335 }
336 n := len(*l)
337 if len(ts) != n {
338 return false
339 }
340 for i, left := range *l {
341 right := ts[i]
342 if !types.Identical(left, right) {
343 return false
344 }
345 }
346 return true
347 }
348 349 type typeListMap struct {
350 hasher typeutil.Hasher
351 buckets map[uint32][]*typeList
352 }
353 354 // rep returns a canonical representative of a slice of types.
355 func (m *typeListMap) rep(ts []types.Type) *typeList {
356 if m == nil || len(ts) == 0 {
357 return nil
358 }
359 360 if m.buckets == nil {
361 m.buckets = make(map[uint32][]*typeList)
362 }
363 364 h := m.hash(ts)
365 bucket := m.buckets[h]
366 for _, l := range bucket {
367 if l.identical(ts) {
368 return l
369 }
370 }
371 372 // not present. create a representative.
373 cp := make(typeList, len(ts))
374 copy(cp, ts)
375 rep := &cp
376 377 m.buckets[h] = append(bucket, rep)
378 return rep
379 }
380 381 func (m *typeListMap) hash(ts []types.Type) uint32 {
382 if m == nil {
383 return 0
384 }
385 // Some smallish prime far away from typeutil.Hash.
386 n := len(ts)
387 h := uint32(13619) + 2*uint32(n)
388 for i := range n {
389 h += 3 * m.hasher.Hash(ts[i])
390 }
391 return h
392 }
393 394 // instantiateMethod instantiates m with targs and returns a canonical representative for this method.
395 func (canon *canonizer) instantiateMethod(m *types.Func, targs []types.Type, ctxt *types.Context) *types.Func {
396 recv := recvType(m)
397 if p, ok := types.Unalias(recv).(*types.Pointer); ok {
398 recv = p.Elem()
399 }
400 named := types.Unalias(recv).(*types.Named)
401 inst, err := types.Instantiate(ctxt, named.Origin(), targs, false)
402 if err != nil {
403 panic(err)
404 }
405 rep := canon.Type(inst)
406 obj, _, _ := types.LookupFieldOrMethod(rep, true, m.Pkg(), m.Name())
407 return obj.(*types.Func)
408 }
409 410 // Exposed to ssautil using the linkname hack.
411 //
412 //go:linkname isSyntactic golang.org/x/tools/go/ssa.isSyntactic
413 func isSyntactic(pkg *Package) bool { return pkg.syntax }
414