util.go

Documentation: golang.org/x/tools/go/ssa

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