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/typeparams"
    21  )
    22  
    23  //// Sanity checking utilities
    24  
    25  // assert panics with the mesage msg if p is false.
    26  // Avoid combining with expensive string formatting.
    27  func assert(p bool, msg string) {
    28  	if !p {
    29  		panic(msg)
    30  	}
    31  }
    32  
    33  //// AST utilities
    34  
    35  func unparen(e ast.Expr) ast.Expr { return astutil.Unparen(e) }
    36  
    37  // isBlankIdent returns true iff e is an Ident with name "_".
    38  // They have no associated types.Object, and thus no type.
    39  func isBlankIdent(e ast.Expr) bool {
    40  	id, ok := e.(*ast.Ident)
    41  	return ok && id.Name == "_"
    42  }
    43  
    44  //// Type utilities.  Some of these belong in go/types.
    45  
    46  // isPointer returns true for types whose underlying type is a pointer.
    47  func isPointer(typ types.Type) bool {
    48  	_, ok := typ.Underlying().(*types.Pointer)
    49  	return ok
    50  }
    51  
    52  // isNonTypeParamInterface reports whether t is an interface type but not a type parameter.
    53  func isNonTypeParamInterface(t types.Type) bool {
    54  	return !typeparams.IsTypeParam(t) && types.IsInterface(t)
    55  }
    56  
    57  // isBasic reports whether t is a basic type.
    58  func isBasic(t types.Type) bool {
    59  	_, ok := t.(*types.Basic)
    60  	return ok
    61  }
    62  
    63  // isString reports whether t is exactly a string type.
    64  func isString(t types.Type) bool {
    65  	return isBasic(t) && t.(*types.Basic).Info()&types.IsString != 0
    66  }
    67  
    68  // isByteSlice reports whether t is []byte.
    69  func isByteSlice(t types.Type) bool {
    70  	if b, ok := t.(*types.Slice); ok {
    71  		e, _ := b.Elem().(*types.Basic)
    72  		return e != nil && e.Kind() == types.Byte
    73  	}
    74  	return false
    75  }
    76  
    77  // isRuneSlice reports whether t is []rune.
    78  func isRuneSlice(t types.Type) bool {
    79  	if b, ok := t.(*types.Slice); ok {
    80  		e, _ := b.Elem().(*types.Basic)
    81  		return e != nil && e.Kind() == types.Rune
    82  	}
    83  	return false
    84  }
    85  
    86  // isBasicConvType returns true when a type set can be
    87  // 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(tset termList) bool {
    92  	basics := 0
    93  	all := underIs(tset, func(t types.Type) bool {
    94  		if isBasic(t) {
    95  			basics++
    96  			return true
    97  		}
    98  		return isByteSlice(t) || isRuneSlice(t)
    99  	})
   100  	return all && basics >= 1 && tset.Len()-basics <= 1
   101  }
   102  
   103  // deref returns a pointer's element type; otherwise it returns typ.
   104  func deref(typ types.Type) types.Type {
   105  	if p, ok := typ.Underlying().(*types.Pointer); ok {
   106  		return p.Elem()
   107  	}
   108  	return typ
   109  }
   110  
   111  // recvType returns the receiver type of method obj.
   112  func recvType(obj *types.Func) types.Type {
   113  	return obj.Type().(*types.Signature).Recv().Type()
   114  }
   115  
   116  // isUntyped returns true for types that are untyped.
   117  func isUntyped(typ types.Type) bool {
   118  	b, ok := typ.(*types.Basic)
   119  	return ok && b.Info()&types.IsUntyped != 0
   120  }
   121  
   122  // logStack prints the formatted "start" message to stderr and
   123  // returns a closure that prints the corresponding "end" message.
   124  // Call using 'defer logStack(...)()' to show builder stack on panic.
   125  // Don't forget trailing parens!
   126  func logStack(format string, args ...interface{}) func() {
   127  	msg := fmt.Sprintf(format, args...)
   128  	io.WriteString(os.Stderr, msg)
   129  	io.WriteString(os.Stderr, "\n")
   130  	return func() {
   131  		io.WriteString(os.Stderr, msg)
   132  		io.WriteString(os.Stderr, " end\n")
   133  	}
   134  }
   135  
   136  // newVar creates a 'var' for use in a types.Tuple.
   137  func newVar(name string, typ types.Type) *types.Var {
   138  	return types.NewParam(token.NoPos, nil, name, typ)
   139  }
   140  
   141  // anonVar creates an anonymous 'var' for use in a types.Tuple.
   142  func anonVar(typ types.Type) *types.Var {
   143  	return newVar("", typ)
   144  }
   145  
   146  var lenResults = types.NewTuple(anonVar(tInt))
   147  
   148  // makeLen returns the len builtin specialized to type func(T)int.
   149  func makeLen(T types.Type) *Builtin {
   150  	lenParams := types.NewTuple(anonVar(T))
   151  	return &Builtin{
   152  		name: "len",
   153  		sig:  types.NewSignature(nil, lenParams, lenResults, false),
   154  	}
   155  }
   156  
   157  // nonbasicTypes returns a list containing all of the types T in ts that are non-basic.
   158  func nonbasicTypes(ts []types.Type) []types.Type {
   159  	if len(ts) == 0 {
   160  		return nil
   161  	}
   162  	added := make(map[types.Type]bool) // additionally filter duplicates
   163  	var filtered []types.Type
   164  	for _, T := range ts {
   165  		if !isBasic(T) {
   166  			if !added[T] {
   167  				added[T] = true
   168  				filtered = append(filtered, T)
   169  			}
   170  		}
   171  	}
   172  	return filtered
   173  }
   174  
   175  // receiverTypeArgs returns the type arguments to a function's reciever.
   176  // Returns an empty list if obj does not have a reciever or its reciever does not have type arguments.
   177  func receiverTypeArgs(obj *types.Func) []types.Type {
   178  	rtype := recvType(obj)
   179  	if rtype == nil {
   180  		return nil
   181  	}
   182  	if isPointer(rtype) {
   183  		rtype = rtype.(*types.Pointer).Elem()
   184  	}
   185  	named, ok := rtype.(*types.Named)
   186  	if !ok {
   187  		return nil
   188  	}
   189  	ts := typeparams.NamedTypeArgs(named)
   190  	if ts.Len() == 0 {
   191  		return nil
   192  	}
   193  	targs := make([]types.Type, ts.Len())
   194  	for i := 0; i < ts.Len(); i++ {
   195  		targs[i] = ts.At(i)
   196  	}
   197  	return targs
   198  }
   199  
   200  // recvAsFirstArg takes a method signature and returns a function
   201  // signature with receiver as the first parameter.
   202  func recvAsFirstArg(sig *types.Signature) *types.Signature {
   203  	params := make([]*types.Var, 0, 1+sig.Params().Len())
   204  	params = append(params, sig.Recv())
   205  	for i := 0; i < sig.Params().Len(); i++ {
   206  		params = append(params, sig.Params().At(i))
   207  	}
   208  	return typeparams.NewSignatureType(nil, nil, nil, types.NewTuple(params...), sig.Results(), sig.Variadic())
   209  }
   210  
   211  // instance returns whether an expression is a simple or qualified identifier
   212  // that is a generic instantiation.
   213  func instance(info *types.Info, expr ast.Expr) bool {
   214  	// Compare the logic here against go/types.instantiatedIdent,
   215  	// which also handles  *IndexExpr and *IndexListExpr.
   216  	var id *ast.Ident
   217  	switch x := expr.(type) {
   218  	case *ast.Ident:
   219  		id = x
   220  	case *ast.SelectorExpr:
   221  		id = x.Sel
   222  	default:
   223  		return false
   224  	}
   225  	_, ok := typeparams.GetInstances(info)[id]
   226  	return ok
   227  }
   228  
   229  // instanceArgs returns the Instance[id].TypeArgs as a slice.
   230  func instanceArgs(info *types.Info, id *ast.Ident) []types.Type {
   231  	targList := typeparams.GetInstances(info)[id].TypeArgs
   232  	if targList == nil {
   233  		return nil
   234  	}
   235  
   236  	targs := make([]types.Type, targList.Len())
   237  	for i, n := 0, targList.Len(); i < n; i++ {
   238  		targs[i] = targList.At(i)
   239  	}
   240  	return targs
   241  }
   242  
   243  // Mapping of a type T to a canonical instance C s.t. types.Indentical(T, C).
   244  // Thread-safe.
   245  type canonizer struct {
   246  	mu    sync.Mutex
   247  	types typeutil.Map // map from type to a canonical instance
   248  	lists typeListMap  // map from a list of types to a canonical instance
   249  }
   250  
   251  func newCanonizer() *canonizer {
   252  	c := &canonizer{}
   253  	h := typeutil.MakeHasher()
   254  	c.types.SetHasher(h)
   255  	c.lists.hasher = h
   256  	return c
   257  }
   258  
   259  // List returns a canonical representative of a list of types.
   260  // Representative of the empty list is nil.
   261  func (c *canonizer) List(ts []types.Type) *typeList {
   262  	if len(ts) == 0 {
   263  		return nil
   264  	}
   265  
   266  	c.mu.Lock()
   267  	defer c.mu.Unlock()
   268  	return c.lists.rep(ts)
   269  }
   270  
   271  // Type returns a canonical representative of type T.
   272  func (c *canonizer) Type(T types.Type) types.Type {
   273  	c.mu.Lock()
   274  	defer c.mu.Unlock()
   275  
   276  	if r := c.types.At(T); r != nil {
   277  		return r.(types.Type)
   278  	}
   279  	c.types.Set(T, T)
   280  	return T
   281  }
   282  
   283  // A type for representating an canonized list of types.
   284  type typeList []types.Type
   285  
   286  func (l *typeList) identical(ts []types.Type) bool {
   287  	if l == nil {
   288  		return len(ts) == 0
   289  	}
   290  	n := len(*l)
   291  	if len(ts) != n {
   292  		return false
   293  	}
   294  	for i, left := range *l {
   295  		right := ts[i]
   296  		if !types.Identical(left, right) {
   297  			return false
   298  		}
   299  	}
   300  	return true
   301  }
   302  
   303  type typeListMap struct {
   304  	hasher  typeutil.Hasher
   305  	buckets map[uint32][]*typeList
   306  }
   307  
   308  // rep returns a canonical representative of a slice of types.
   309  func (m *typeListMap) rep(ts []types.Type) *typeList {
   310  	if m == nil || len(ts) == 0 {
   311  		return nil
   312  	}
   313  
   314  	if m.buckets == nil {
   315  		m.buckets = make(map[uint32][]*typeList)
   316  	}
   317  
   318  	h := m.hash(ts)
   319  	bucket := m.buckets[h]
   320  	for _, l := range bucket {
   321  		if l.identical(ts) {
   322  			return l
   323  		}
   324  	}
   325  
   326  	// not present. create a representative.
   327  	cp := make(typeList, len(ts))
   328  	copy(cp, ts)
   329  	rep := &cp
   330  
   331  	m.buckets[h] = append(bucket, rep)
   332  	return rep
   333  }
   334  
   335  func (m *typeListMap) hash(ts []types.Type) uint32 {
   336  	if m == nil {
   337  		return 0
   338  	}
   339  	// Some smallish prime far away from typeutil.Hash.
   340  	n := len(ts)
   341  	h := uint32(13619) + 2*uint32(n)
   342  	for i := 0; i < n; i++ {
   343  		h += 3 * m.hasher.Hash(ts[i])
   344  	}
   345  	return h
   346  }
   347  
   348  // instantiateMethod instantiates m with targs and returns a canonical representative for this method.
   349  func (canon *canonizer) instantiateMethod(m *types.Func, targs []types.Type, ctxt *typeparams.Context) *types.Func {
   350  	recv := recvType(m)
   351  	if p, ok := recv.(*types.Pointer); ok {
   352  		recv = p.Elem()
   353  	}
   354  	named := recv.(*types.Named)
   355  	inst, err := typeparams.Instantiate(ctxt, typeparams.NamedTypeOrigin(named), targs, false)
   356  	if err != nil {
   357  		panic(err)
   358  	}
   359  	rep := canon.Type(inst)
   360  	obj, _, _ := types.LookupFieldOrMethod(rep, true, m.Pkg(), m.Name())
   361  	return obj.(*types.Func)
   362  }
   363
View as plain text