| 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 |
Members