.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/types/typeutil/map.go

   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
  16 // Map is a hash-table-based mapping from types (types.Type) to
  17 // arbitrary interface{} values.  The concrete types that implement
  18 // the Type interface are pointers.  Since they are not canonicalized,
  19 // == cannot be used to check for equivalence, and thus we cannot
  20 // simply use a Go map.
  21 //
  22 // Just as with map[K]V, a nil *Map is a valid empty map.
  23 //
  24 // Not thread-safe.
  25 //
  26 type Map struct {
  27         hasher Hasher             // shared by many Maps
  28         table  map[uint32][]entry // maps hash to bucket; entry.key==nil means unused
  29         length int                // number of map entries
  30 }
  31
  32 // entry is an entry (key/value association) in a hash bucket.
  33 type entry struct {
  34         key   types.Type
  35         value interface{}
  36 }
  37
  38 // SetHasher sets the hasher used by Map.
  39 //
  40 // All Hashers are functionally equivalent but contain internal state
  41 // used to cache the results of hashing previously seen types.
  42 //
  43 // A single Hasher created by MakeHasher() may be shared among many
  44 // Maps.  This is recommended if the instances have many keys in
  45 // common, as it will amortize the cost of hash computation.
  46 //
  47 // A Hasher may grow without bound as new types are seen.  Even when a
  48 // type is deleted from the map, the Hasher never shrinks, since other
  49 // types in the map may reference the deleted type indirectly.
  50 //
  51 // Hashers are not thread-safe, and read-only operations such as
  52 // Map.Lookup require updates to the hasher, so a full Mutex lock (not a
  53 // read-lock) is require around all Map operations if a shared
  54 // hasher is accessed from multiple threads.
  55 //
  56 // If SetHasher is not called, the Map will create a private hasher at
  57 // the first call to Insert.
  58 //
  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 //
  66 func (m *Map) Delete(key types.Type) bool {
  67         if m != nil && m.table != nil {
  68                 hash := m.hasher.Hash(key)
  69                 bucket := m.table[hash]
  70                 for i, e := range bucket {
  71                         if e.key != nil && types.Identical(key, e.key) {
  72                                 // We can't compact the bucket as it
  73                                 // would disturb iterators.
  74                                 bucket[i] = entry{}
  75                                 m.length--
  76                                 return true
  77                         }
  78                 }
  79         }
  80         return false
  81 }
  82
  83 // At returns the map entry for the given key.
  84 // The result is nil if the entry is not present.
  85 //
  86 func (m *Map) At(key types.Type) interface{} {
  87         if m != nil && m.table != nil {
  88                 for _, e := range m.table[m.hasher.Hash(key)] {
  89                         if e.key != nil && types.Identical(key, e.key) {
  90                                 return e.value
  91                         }
  92                 }
  93         }
  94         return nil
  95 }
  96
  97 // Set sets the map entry for key to val,
  98 // and returns the previous entry, if any.
  99 func (m *Map) Set(key types.Type, value interface{}) (prev interface{}) {
 100         if m.table != nil {
 101                 hash := m.hasher.Hash(key)
 102                 bucket := m.table[hash]
 103                 var hole *entry
 104                 for i, e := range bucket {
 105                         if e.key == nil {
 106                                 hole = &bucket[i]
 107                         } else if types.Identical(key, e.key) {
 108                                 prev = e.value
 109                                 bucket[i].value = value
 110                                 return
 111                         }
 112                 }
 113
 114                 if hole != nil {
 115                         *hole = entry{key, value} // overwrite deleted entry
 116                 } else {
 117                         m.table[hash] = append(bucket, entry{key, value})
 118                 }
 119         } else {
 120                 if m.hasher.memo == nil {
 121                         m.hasher = MakeHasher()
 122                 }
 123                 hash := m.hasher.Hash(key)
 124                 m.table = map[uint32][]entry{hash: {entry{key, value}}}
 125         }
 126
 127         m.length++
 128         return
 129 }
 130
 131 // Len returns the number of map entries.
 132 func (m *Map) Len() int {
 133         if m != nil {
 134                 return m.length
 135         }
 136         return 0
 137 }
 138
 139 // Iterate calls function f on each entry in the map in unspecified order.
 140 //
 141 // If f should mutate the map, Iterate provides the same guarantees as
 142 // Go maps: if f deletes a map entry that Iterate has not yet reached,
 143 // f will not be invoked for it, but if f inserts a map entry that
 144 // Iterate has not yet reached, whether or not f will be invoked for
 145 // it is unspecified.
 146 //
 147 func (m *Map) Iterate(f func(key types.Type, value interface{})) {
 148         if m != nil {
 149                 for _, bucket := range m.table {
 150                         for _, e := range bucket {
 151                                 if e.key != nil {
 152                                         f(e.key, e.value)
 153                                 }
 154                         }
 155                 }
 156         }
 157 }
 158
 159 // Keys returns a new slice containing the set of map keys.
 160 // The order is unspecified.
 161 func (m *Map) Keys() []types.Type {
 162         keys := make([]types.Type, 0, m.Len())
 163         m.Iterate(func(key types.Type, _ interface{}) {
 164                 keys = append(keys, key)
 165         })
 166         return keys
 167 }
 168
 169 func (m *Map) toString(values bool) string {
 170         if m == nil {
 171                 return "{}"
 172         }
 173         var buf bytes.Buffer
 174         fmt.Fprint(&buf, "{")
 175         sep := ""
 176         m.Iterate(func(key types.Type, value interface{}) {
 177                 fmt.Fprint(&buf, sep)
 178                 sep = ", "
 179                 fmt.Fprint(&buf, key)
 180                 if values {
 181                         fmt.Fprintf(&buf, ": %q", value)
 182                 }
 183         })
 184         fmt.Fprint(&buf, "}")
 185         return buf.String()
 186 }
 187
 188 // String returns a string representation of the map's entries.
 189 // Values are printed using fmt.Sprintf("%v", v).
 190 // Order is unspecified.
 191 //
 192 func (m *Map) String() string {
 193         return m.toString(true)
 194 }
 195
 196 // KeysString returns a string representation of the map's key set.
 197 // Order is unspecified.
 198 //
 199 func (m *Map) KeysString() string {
 200         return m.toString(false)
 201 }
 202
 203 ////////////////////////////////////////////////////////////////////////
 204 // Hasher
 205
 206 // A Hasher maps each type to its hash value.
 207 // For efficiency, a hasher uses memoization; thus its memory
 208 // footprint grows monotonically over time.
 209 // Hashers are not thread-safe.
 210 // Hashers have reference semantics.
 211 // Call MakeHasher to create a Hasher.
 212 type Hasher struct {
 213         memo map[types.Type]uint32
 214 }
 215
 216 // MakeHasher returns a new Hasher instance.
 217 func MakeHasher() Hasher {
 218         return Hasher{make(map[types.Type]uint32)}
 219 }
 220
 221 // Hash computes a hash value for the given type t such that
 222 // Identical(t, t') => Hash(t) == Hash(t').
 223 func (h Hasher) Hash(t types.Type) uint32 {
 224         hash, ok := h.memo[t]
 225         if !ok {
 226                 hash = h.hashFor(t)
 227                 h.memo[t] = hash
 228         }
 229         return hash
 230 }
 231
 232 // hashString computes the Fowler–Noll–Vo hash of s.
 233 func hashString(s string) uint32 {
 234         var h uint32
 235         for i := 0; i < len(s); i++ {
 236                 h ^= uint32(s[i])
 237                 h *= 16777619
 238         }
 239         return h
 240 }
 241
 242 // hashFor computes the hash of t.
 243 func (h Hasher) hashFor(t types.Type) uint32 {
 244         // See Identical for rationale.
 245         switch t := t.(type) {
 246         case *types.Basic:
 247                 return uint32(t.Kind())
 248
 249         case *types.Array:
 250                 return 9043 + 2*uint32(t.Len()) + 3*h.Hash(t.Elem())
 251
 252         case *types.Slice:
 253                 return 9049 + 2*h.Hash(t.Elem())
 254
 255         case *types.Struct:
 256                 var hash uint32 = 9059
 257                 for i, n := 0, t.NumFields(); i < n; i++ {
 258                         f := t.Field(i)
 259                         if f.Anonymous() {
 260                                 hash += 8861
 261                         }
 262                         hash += hashString(t.Tag(i))
 263                         hash += hashString(f.Name()) // (ignore f.Pkg)
 264                         hash += h.Hash(f.Type())
 265                 }
 266                 return hash
 267
 268         case *types.Pointer:
 269                 return 9067 + 2*h.Hash(t.Elem())
 270
 271         case *types.Signature:
 272                 var hash uint32 = 9091
 273                 if t.Variadic() {
 274                         hash *= 8863
 275                 }
 276                 return hash + 3*h.hashTuple(t.Params()) + 5*h.hashTuple(t.Results())
 277
 278         case *types.Interface:
 279                 var hash uint32 = 9103
 280                 for i, n := 0, t.NumMethods(); i < n; i++ {
 281                         // See go/types.identicalMethods for rationale.
 282                         // Method order is not significant.
 283                         // Ignore m.Pkg().
 284                         m := t.Method(i)
 285                         hash += 3*hashString(m.Name()) + 5*h.Hash(m.Type())
 286                 }
 287                 return hash
 288
 289         case *types.Map:
 290                 return 9109 + 2*h.Hash(t.Key()) + 3*h.Hash(t.Elem())
 291
 292         case *types.Chan:
 293                 return 9127 + 2*uint32(t.Dir()) + 3*h.Hash(t.Elem())
 294
 295         case *types.Named:
 296                 // Not safe with a copying GC; objects may move.
 297                 return uint32(reflect.ValueOf(t.Obj()).Pointer())
 298
 299         case *types.Tuple:
 300                 return h.hashTuple(t)
 301         }
 302         panic(t)
 303 }
 304
 305 func (h Hasher) hashTuple(tuple *types.Tuple) uint32 {
 306         // See go/types.identicalTypes for rationale.
 307         n := tuple.Len()
 308         var hash uint32 = 9137 + 2*uint32(n)
 309         for i := 0; i < n; i++ {
 310                 hash += 3 * h.Hash(tuple.At(i).Type())
 311         }
 312         return hash
 313 }