map.go

Documentation: golang.org/x/tools/go/types/typeutil

     1  // Copyright 2014 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 typeutil defines various utilities for types, such as Map,
     6  // a mapping from types.Type to interface{} values.
     7  package typeutil // import "golang.org/x/tools/go/types/typeutil"
     8  
     9  import (
    10  	"bytes"
    11  	"fmt"
    12  	"go/types"
    13  	"reflect"
    14  
    15  	"golang.org/x/tools/internal/typeparams"
    16  )
    17  
    18  // Map is a hash-table-based mapping from types (types.Type) to
    19  // arbitrary interface{} values.  The concrete types that implement
    20  // the Type interface are pointers.  Since they are not canonicalized,
    21  // == cannot be used to check for equivalence, and thus we cannot
    22  // simply use a Go map.
    23  //
    24  // Just as with map[K]V, a nil *Map is a valid empty map.
    25  //
    26  // Not thread-safe.
    27  type Map struct {
    28  	hasher Hasher             // shared by many Maps
    29  	table  map[uint32][]entry // maps hash to bucket; entry.key==nil means unused
    30  	length int                // number of map entries
    31  }
    32  
    33  // entry is an entry (key/value association) in a hash bucket.
    34  type entry struct {
    35  	key   types.Type
    36  	value interface{}
    37  }
    38  
    39  // SetHasher sets the hasher used by Map.
    40  //
    41  // All Hashers are functionally equivalent but contain internal state
    42  // used to cache the results of hashing previously seen types.
    43  //
    44  // A single Hasher created by MakeHasher() may be shared among many
    45  // Maps.  This is recommended if the instances have many keys in
    46  // common, as it will amortize the cost of hash computation.
    47  //
    48  // A Hasher may grow without bound as new types are seen.  Even when a
    49  // type is deleted from the map, the Hasher never shrinks, since other
    50  // types in the map may reference the deleted type indirectly.
    51  //
    52  // Hashers are not thread-safe, and read-only operations such as
    53  // Map.Lookup require updates to the hasher, so a full Mutex lock (not a
    54  // read-lock) is require around all Map operations if a shared
    55  // hasher is accessed from multiple threads.
    56  //
    57  // If SetHasher is not called, the Map will create a private hasher at
    58  // the first call to Insert.
    59  func (m *Map) SetHasher(hasher Hasher) {
    60  	m.hasher = hasher
    61  }
    62  
    63  // Delete removes the entry with the given key, if any.
    64  // It returns true if the entry was found.
    65  func (m *Map) Delete(key types.Type) bool {
    66  	if m != nil && m.table != nil {
    67  		hash := m.hasher.Hash(key)
    68  		bucket := m.table[hash]
    69  		for i, e := range bucket {
    70  			if e.key != nil && types.Identical(key, e.key) {
    71  				// We can't compact the bucket as it
    72  				// would disturb iterators.
    73  				bucket[i] = entry{}
    74  				m.length--
    75  				return true
    76  			}
    77  		}
    78  	}
    79  	return false
    80  }
    81  
    82  // At returns the map entry for the given key.
    83  // The result is nil if the entry is not present.
    84  func (m *Map) At(key types.Type) interface{} {
    85  	if m != nil && m.table != nil {
    86  		for _, e := range m.table[m.hasher.Hash(key)] {
    87  			if e.key != nil && types.Identical(key, e.key) {
    88  				return e.value
    89  			}
    90  		}
    91  	}
    92  	return nil
    93  }
    94  
    95  // Set sets the map entry for key to val,
    96  // and returns the previous entry, if any.
    97  func (m *Map) Set(key types.Type, value interface{}) (prev interface{}) {
    98  	if m.table != nil {
    99  		hash := m.hasher.Hash(key)
   100  		bucket := m.table[hash]
   101  		var hole *entry
   102  		for i, e := range bucket {
   103  			if e.key == nil {
   104  				hole = &bucket[i]
   105  			} else if types.Identical(key, e.key) {
   106  				prev = e.value
   107  				bucket[i].value = value
   108  				return
   109  			}
   110  		}
   111  
   112  		if hole != nil {
   113  			*hole = entry{key, value} // overwrite deleted entry
   114  		} else {
   115  			m.table[hash] = append(bucket, entry{key, value})
   116  		}
   117  	} else {
   118  		if m.hasher.memo == nil {
   119  			m.hasher = MakeHasher()
   120  		}
   121  		hash := m.hasher.Hash(key)
   122  		m.table = map[uint32][]entry{hash: {entry{key, value}}}
   123  	}
   124  
   125  	m.length++
   126  	return
   127  }
   128  
   129  // Len returns the number of map entries.
   130  func (m *Map) Len() int {
   131  	if m != nil {
   132  		return m.length
   133  	}
   134  	return 0
   135  }
   136  
   137  // Iterate calls function f on each entry in the map in unspecified order.
   138  //
   139  // If f should mutate the map, Iterate provides the same guarantees as
   140  // Go maps: if f deletes a map entry that Iterate has not yet reached,
   141  // f will not be invoked for it, but if f inserts a map entry that
   142  // Iterate has not yet reached, whether or not f will be invoked for
   143  // it is unspecified.
   144  func (m *Map) Iterate(f func(key types.Type, value interface{})) {
   145  	if m != nil {
   146  		for _, bucket := range m.table {
   147  			for _, e := range bucket {
   148  				if e.key != nil {
   149  					f(e.key, e.value)
   150  				}
   151  			}
   152  		}
   153  	}
   154  }
   155  
   156  // Keys returns a new slice containing the set of map keys.
   157  // The order is unspecified.
   158  func (m *Map) Keys() []types.Type {
   159  	keys := make([]types.Type, 0, m.Len())
   160  	m.Iterate(func(key types.Type, _ interface{}) {
   161  		keys = append(keys, key)
   162  	})
   163  	return keys
   164  }
   165  
   166  func (m *Map) toString(values bool) string {
   167  	if m == nil {
   168  		return "{}"
   169  	}
   170  	var buf bytes.Buffer
   171  	fmt.Fprint(&buf, "{")
   172  	sep := ""
   173  	m.Iterate(func(key types.Type, value interface{}) {
   174  		fmt.Fprint(&buf, sep)
   175  		sep = ", "
   176  		fmt.Fprint(&buf, key)
   177  		if values {
   178  			fmt.Fprintf(&buf, ": %q", value)
   179  		}
   180  	})
   181  	fmt.Fprint(&buf, "}")
   182  	return buf.String()
   183  }
   184  
   185  // String returns a string representation of the map's entries.
   186  // Values are printed using fmt.Sprintf("%v", v).
   187  // Order is unspecified.
   188  func (m *Map) String() string {
   189  	return m.toString(true)
   190  }
   191  
   192  // KeysString returns a string representation of the map's key set.
   193  // Order is unspecified.
   194  func (m *Map) KeysString() string {
   195  	return m.toString(false)
   196  }
   197  
   198  ////////////////////////////////////////////////////////////////////////
   199  // Hasher
   200  
   201  // A Hasher maps each type to its hash value.
   202  // For efficiency, a hasher uses memoization; thus its memory
   203  // footprint grows monotonically over time.
   204  // Hashers are not thread-safe.
   205  // Hashers have reference semantics.
   206  // Call MakeHasher to create a Hasher.
   207  type Hasher struct {
   208  	memo map[types.Type]uint32
   209  
   210  	// ptrMap records pointer identity.
   211  	ptrMap map[interface{}]uint32
   212  
   213  	// sigTParams holds type parameters from the signature being hashed.
   214  	// Signatures are considered identical modulo renaming of type parameters, so
   215  	// within the scope of a signature type the identity of the signature's type
   216  	// parameters is just their index.
   217  	//
   218  	// Since the language does not currently support referring to uninstantiated
   219  	// generic types or functions, and instantiated signatures do not have type
   220  	// parameter lists, we should never encounter a second non-empty type
   221  	// parameter list when hashing a generic signature.
   222  	sigTParams *typeparams.TypeParamList
   223  }
   224  
   225  // MakeHasher returns a new Hasher instance.
   226  func MakeHasher() Hasher {
   227  	return Hasher{
   228  		memo:       make(map[types.Type]uint32),
   229  		ptrMap:     make(map[interface{}]uint32),
   230  		sigTParams: nil,
   231  	}
   232  }
   233  
   234  // Hash computes a hash value for the given type t such that
   235  // Identical(t, t') => Hash(t) == Hash(t').
   236  func (h Hasher) Hash(t types.Type) uint32 {
   237  	hash, ok := h.memo[t]
   238  	if !ok {
   239  		hash = h.hashFor(t)
   240  		h.memo[t] = hash
   241  	}
   242  	return hash
   243  }
   244  
   245  // hashString computes the Fowler–Noll–Vo hash of s.
   246  func hashString(s string) uint32 {
   247  	var h uint32
   248  	for i := 0; i < len(s); i++ {
   249  		h ^= uint32(s[i])
   250  		h *= 16777619
   251  	}
   252  	return h
   253  }
   254  
   255  // hashFor computes the hash of t.
   256  func (h Hasher) hashFor(t types.Type) uint32 {
   257  	// See Identical for rationale.
   258  	switch t := t.(type) {
   259  	case *types.Basic:
   260  		return uint32(t.Kind())
   261  
   262  	case *types.Array:
   263  		return 9043 + 2*uint32(t.Len()) + 3*h.Hash(t.Elem())
   264  
   265  	case *types.Slice:
   266  		return 9049 + 2*h.Hash(t.Elem())
   267  
   268  	case *types.Struct:
   269  		var hash uint32 = 9059
   270  		for i, n := 0, t.NumFields(); i < n; i++ {
   271  			f := t.Field(i)
   272  			if f.Anonymous() {
   273  				hash += 8861
   274  			}
   275  			hash += hashString(t.Tag(i))
   276  			hash += hashString(f.Name()) // (ignore f.Pkg)
   277  			hash += h.Hash(f.Type())
   278  		}
   279  		return hash
   280  
   281  	case *types.Pointer:
   282  		return 9067 + 2*h.Hash(t.Elem())
   283  
   284  	case *types.Signature:
   285  		var hash uint32 = 9091
   286  		if t.Variadic() {
   287  			hash *= 8863
   288  		}
   289  
   290  		// Use a separate hasher for types inside of the signature, where type
   291  		// parameter identity is modified to be (index, constraint). We must use a
   292  		// new memo for this hasher as type identity may be affected by this
   293  		// masking. For example, in func[T any](*T), the identity of *T depends on
   294  		// whether we are mapping the argument in isolation, or recursively as part
   295  		// of hashing the signature.
   296  		//
   297  		// We should never encounter a generic signature while hashing another
   298  		// generic signature, but defensively set sigTParams only if h.mask is
   299  		// unset.
   300  		tparams := typeparams.ForSignature(t)
   301  		if h.sigTParams == nil && tparams.Len() != 0 {
   302  			h = Hasher{
   303  				// There may be something more efficient than discarding the existing
   304  				// memo, but it would require detecting whether types are 'tainted' by
   305  				// references to type parameters.
   306  				memo: make(map[types.Type]uint32),
   307  				// Re-using ptrMap ensures that pointer identity is preserved in this
   308  				// hasher.
   309  				ptrMap:     h.ptrMap,
   310  				sigTParams: tparams,
   311  			}
   312  		}
   313  
   314  		for i := 0; i < tparams.Len(); i++ {
   315  			tparam := tparams.At(i)
   316  			hash += 7 * h.Hash(tparam.Constraint())
   317  		}
   318  
   319  		return hash + 3*h.hashTuple(t.Params()) + 5*h.hashTuple(t.Results())
   320  
   321  	case *typeparams.Union:
   322  		return h.hashUnion(t)
   323  
   324  	case *types.Interface:
   325  		// Interfaces are identical if they have the same set of methods, with
   326  		// identical names and types, and they have the same set of type
   327  		// restrictions. See go/types.identical for more details.
   328  		var hash uint32 = 9103
   329  
   330  		// Hash methods.
   331  		for i, n := 0, t.NumMethods(); i < n; i++ {
   332  			// Method order is not significant.
   333  			// Ignore m.Pkg().
   334  			m := t.Method(i)
   335  			// Use shallow hash on method signature to
   336  			// avoid anonymous interface cycles.
   337  			hash += 3*hashString(m.Name()) + 5*h.shallowHash(m.Type())
   338  		}
   339  
   340  		// Hash type restrictions.
   341  		terms, err := typeparams.InterfaceTermSet(t)
   342  		// if err != nil t has invalid type restrictions.
   343  		if err == nil {
   344  			hash += h.hashTermSet(terms)
   345  		}
   346  
   347  		return hash
   348  
   349  	case *types.Map:
   350  		return 9109 + 2*h.Hash(t.Key()) + 3*h.Hash(t.Elem())
   351  
   352  	case *types.Chan:
   353  		return 9127 + 2*uint32(t.Dir()) + 3*h.Hash(t.Elem())
   354  
   355  	case *types.Named:
   356  		hash := h.hashPtr(t.Obj())
   357  		targs := typeparams.NamedTypeArgs(t)
   358  		for i := 0; i < targs.Len(); i++ {
   359  			targ := targs.At(i)
   360  			hash += 2 * h.Hash(targ)
   361  		}
   362  		return hash
   363  
   364  	case *typeparams.TypeParam:
   365  		return h.hashTypeParam(t)
   366  
   367  	case *types.Tuple:
   368  		return h.hashTuple(t)
   369  	}
   370  
   371  	panic(fmt.Sprintf("%T: %v", t, t))
   372  }
   373  
   374  func (h Hasher) hashTuple(tuple *types.Tuple) uint32 {
   375  	// See go/types.identicalTypes for rationale.
   376  	n := tuple.Len()
   377  	hash := 9137 + 2*uint32(n)
   378  	for i := 0; i < n; i++ {
   379  		hash += 3 * h.Hash(tuple.At(i).Type())
   380  	}
   381  	return hash
   382  }
   383  
   384  func (h Hasher) hashUnion(t *typeparams.Union) uint32 {
   385  	// Hash type restrictions.
   386  	terms, err := typeparams.UnionTermSet(t)
   387  	// if err != nil t has invalid type restrictions. Fall back on a non-zero
   388  	// hash.
   389  	if err != nil {
   390  		return 9151
   391  	}
   392  	return h.hashTermSet(terms)
   393  }
   394  
   395  func (h Hasher) hashTermSet(terms []*typeparams.Term) uint32 {
   396  	hash := 9157 + 2*uint32(len(terms))
   397  	for _, term := range terms {
   398  		// term order is not significant.
   399  		termHash := h.Hash(term.Type())
   400  		if term.Tilde() {
   401  			termHash *= 9161
   402  		}
   403  		hash += 3 * termHash
   404  	}
   405  	return hash
   406  }
   407  
   408  // hashTypeParam returns a hash of the type parameter t, with a hash value
   409  // depending on whether t is contained in h.sigTParams.
   410  //
   411  // If h.sigTParams is set and contains t, then we are in the process of hashing
   412  // a signature, and the hash value of t must depend only on t's index and
   413  // constraint: signatures are considered identical modulo type parameter
   414  // renaming. To avoid infinite recursion, we only hash the type parameter
   415  // index, and rely on types.Identical to handle signatures where constraints
   416  // are not identical.
   417  //
   418  // Otherwise the hash of t depends only on t's pointer identity.
   419  func (h Hasher) hashTypeParam(t *typeparams.TypeParam) uint32 {
   420  	if h.sigTParams != nil {
   421  		i := t.Index()
   422  		if i >= 0 && i < h.sigTParams.Len() && t == h.sigTParams.At(i) {
   423  			return 9173 + 3*uint32(i)
   424  		}
   425  	}
   426  	return h.hashPtr(t.Obj())
   427  }
   428  
   429  // hashPtr hashes the pointer identity of ptr. It uses h.ptrMap to ensure that
   430  // pointers values are not dependent on the GC.
   431  func (h Hasher) hashPtr(ptr interface{}) uint32 {
   432  	if hash, ok := h.ptrMap[ptr]; ok {
   433  		return hash
   434  	}
   435  	hash := uint32(reflect.ValueOf(ptr).Pointer())
   436  	h.ptrMap[ptr] = hash
   437  	return hash
   438  }
   439  
   440  // shallowHash computes a hash of t without looking at any of its
   441  // element Types, to avoid potential anonymous cycles in the types of
   442  // interface methods.
   443  //
   444  // When an unnamed non-empty interface type appears anywhere among the
   445  // arguments or results of an interface method, there is a potential
   446  // for endless recursion. Consider:
   447  //
   448  //	type X interface { m() []*interface { X } }
   449  //
   450  // The problem is that the Methods of the interface in m's result type
   451  // include m itself; there is no mention of the named type X that
   452  // might help us break the cycle.
   453  // (See comment in go/types.identical, case *Interface, for more.)
   454  func (h Hasher) shallowHash(t types.Type) uint32 {
   455  	// t is the type of an interface method (Signature),
   456  	// its params or results (Tuples), or their immediate
   457  	// elements (mostly Slice, Pointer, Basic, Named),
   458  	// so there's no need to optimize anything else.
   459  	switch t := t.(type) {
   460  	case *types.Signature:
   461  		var hash uint32 = 604171
   462  		if t.Variadic() {
   463  			hash *= 971767
   464  		}
   465  		// The Signature/Tuple recursion is always finite
   466  		// and invariably shallow.
   467  		return hash + 1062599*h.shallowHash(t.Params()) + 1282529*h.shallowHash(t.Results())
   468  
   469  	case *types.Tuple:
   470  		n := t.Len()
   471  		hash := 9137 + 2*uint32(n)
   472  		for i := 0; i < n; i++ {
   473  			hash += 53471161 * h.shallowHash(t.At(i).Type())
   474  		}
   475  		return hash
   476  
   477  	case *types.Basic:
   478  		return 45212177 * uint32(t.Kind())
   479  
   480  	case *types.Array:
   481  		return 1524181 + 2*uint32(t.Len())
   482  
   483  	case *types.Slice:
   484  		return 2690201
   485  
   486  	case *types.Struct:
   487  		return 3326489
   488  
   489  	case *types.Pointer:
   490  		return 4393139
   491  
   492  	case *typeparams.Union:
   493  		return 562448657
   494  
   495  	case *types.Interface:
   496  		return 2124679 // no recursion here
   497  
   498  	case *types.Map:
   499  		return 9109
   500  
   501  	case *types.Chan:
   502  		return 9127
   503  
   504  	case *types.Named:
   505  		return h.hashPtr(t.Obj())
   506  
   507  	case *typeparams.TypeParam:
   508  		return h.hashPtr(t.Obj())
   509  	}
   510  	panic(fmt.Sprintf("shallowHash: %T: %v", t, t))
   511  }
   512
View as plain text