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