1
2
3
4
5
6
7 package typeutil
8
9 import (
10 "bytes"
11 "fmt"
12 "go/types"
13 "reflect"
14
15 "golang.org/x/tools/internal/typeparams"
16 )
17
18
19
20
21
22
23
24
25
26
27 type Map struct {
28 hasher Hasher
29 table map[uint32][]entry
30 length int
31 }
32
33
34 type entry struct {
35 key types.Type
36 value interface{}
37 }
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 func (m *Map) SetHasher(hasher Hasher) {
60 m.hasher = hasher
61 }
62
63
64
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
72
73 bucket[i] = entry{}
74 m.length--
75 return true
76 }
77 }
78 }
79 return false
80 }
81
82
83
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
96
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}
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
130 func (m *Map) Len() int {
131 if m != nil {
132 return m.length
133 }
134 return 0
135 }
136
137
138
139
140
141
142
143
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
157
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
186
187
188 func (m *Map) String() string {
189 return m.toString(true)
190 }
191
192
193
194 func (m *Map) KeysString() string {
195 return m.toString(false)
196 }
197
198
199
200
201
202
203
204
205
206
207 type Hasher struct {
208 memo map[types.Type]uint32
209
210
211 ptrMap map[interface{}]uint32
212
213
214
215
216
217
218
219
220
221
222 sigTParams *typeparams.TypeParamList
223 }
224
225
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
235
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
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
256 func (h Hasher) hashFor(t types.Type) uint32 {
257
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())
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
291
292
293
294
295
296
297
298
299
300 tparams := typeparams.ForSignature(t)
301 if h.sigTParams == nil && tparams.Len() != 0 {
302 h = Hasher{
303
304
305
306 memo: make(map[types.Type]uint32),
307
308
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
326
327
328 var hash uint32 = 9103
329
330
331 for i, n := 0, t.NumMethods(); i < n; i++ {
332
333
334 m := t.Method(i)
335
336
337 hash += 3*hashString(m.Name()) + 5*h.shallowHash(m.Type())
338 }
339
340
341 terms, err := typeparams.InterfaceTermSet(t)
342
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
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
386 terms, err := typeparams.UnionTermSet(t)
387
388
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
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
409
410
411
412
413
414
415
416
417
418
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
430
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
441
442
443
444
445
446
447
448
449
450
451
452
453
454 func (h Hasher) shallowHash(t types.Type) uint32 {
455
456
457
458
459 switch t := t.(type) {
460 case *types.Signature:
461 var hash uint32 = 604171
462 if t.Variadic() {
463 hash *= 971767
464 }
465
466
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
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