hash.go

     1  // Copyright 2026 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 types
     6  
     7  // This file defines a hash function for Types.
     8  
     9  import (
    10  	"fmt"
    11  	"hash/maphash"
    12  )
    13  
    14  type (
    15  	// Hasher defines a hash function and equivalence relation
    16  	// for [Types] that is consistent with [Identical].
    17  	// Hashers are stateless.
    18  	Hasher struct{}
    19  
    20  	// HasherIgnoreTags is a variant of [Hasher] that is
    21  	// consistent with [IdenticalIgnoreTags].
    22  	HasherIgnoreTags struct{}
    23  )
    24  
    25  var (
    26  	_ maphash.Hasher[Type] = Hasher{}
    27  	_ maphash.Hasher[Type] = HasherIgnoreTags{}
    28  )
    29  
    30  func (Hasher) Hash(h *maphash.Hash, t Type) {
    31  	// The two hashers use essentially the same hash function,
    32  	// which ignores tags; only the Equal methods vary.
    33  	// But for future-proofing we gratuitously force them
    34  	// to differ by one byte.
    35  	h.WriteByte(0)
    36  	hasher{inGenericSig: false}.hash(h, t)
    37  }
    38  func (HasherIgnoreTags) Hash(h *maphash.Hash, t Type) {
    39  	h.WriteByte(1)
    40  	hasher{inGenericSig: false}.hash(h, t)
    41  }
    42  
    43  func (Hasher) Equal(x, y Type) bool           { return Identical(x, y) }
    44  func (HasherIgnoreTags) Equal(x, y Type) bool { return IdenticalIgnoreTags(x, y) }
    45  
    46  // hasher holds the state of a single hash traversal, namely,
    47  // whether we are inside the signature of a generic function.
    48  // This is used to optimize [hasher.hashTypeParam].
    49  type hasher struct{ inGenericSig bool }
    50  
    51  func (hr hasher) hash(h *maphash.Hash, t Type) {
    52  	// See [Identical] for rationale.
    53  	switch t := t.(type) {
    54  	case *Alias:
    55  		hr.hash(h, Unalias(t))
    56  
    57  	case *Array:
    58  		h.WriteByte('A')
    59  		maphash.WriteComparable(h, t.Len())
    60  		hr.hash(h, t.Elem())
    61  
    62  	case *Basic:
    63  		h.WriteByte('B')
    64  		h.WriteByte(byte(t.Kind()))
    65  
    66  	case *Chan:
    67  		h.WriteByte('C')
    68  		h.WriteByte(byte(t.Dir()))
    69  		hr.hash(h, t.Elem())
    70  
    71  	case *Interface:
    72  		h.WriteByte('I')
    73  		h.WriteByte(byte(t.NumMethods()))
    74  
    75  		// Interfaces are identical if they have the same set of methods, with
    76  		// identical names and types, and they have the same set of type
    77  		// restrictions. See [Identical] for more details.
    78  
    79  		// Hash the methods.
    80  		//
    81  		// Because [Identical] treats Methods as an unordered set,
    82  		// we must either:
    83  		// (a) sort the methods into some canonical order; or
    84  		// (b) hash them each in parallel, combine them with a
    85  		//     commutative operation such as + or ^, and then
    86  		//     write this value into the primary hasher.
    87  		// Since (a) requires allocation, we choose (b).
    88  		var hash uint64
    89  		for m := range t.Methods() {
    90  			var subh maphash.Hash
    91  			subh.SetSeed(h.Seed())
    92  			// Ignore m.Pkg().
    93  			// Use shallow hash on method signature to
    94  			// avoid anonymous interface cycles.
    95  			subh.WriteString(m.Name())
    96  			hr.shallowHash(&subh, m.Type())
    97  			hash ^= subh.Sum64()
    98  		}
    99  		maphash.WriteComparable(h, hash)
   100  
   101  		// Hash type restrictions.
   102  		// TODO(adonovan): call (fork of) InterfaceTermSet from
   103  		// golang.org/x/tools/internal/typeparams/normalize.go.
   104  		// hr.hashTermSet(h, terms)
   105  
   106  	case *Map:
   107  		h.WriteByte('M')
   108  		hr.hash(h, t.Key())
   109  		hr.hash(h, t.Elem())
   110  
   111  	case *Named:
   112  		h.WriteByte('N')
   113  		hr.hashTypeName(h, t.Obj())
   114  		for targ := range t.TypeArgs().Types() {
   115  			hr.hash(h, targ)
   116  		}
   117  
   118  	case *Pointer:
   119  		h.WriteByte('P')
   120  		hr.hash(h, t.Elem())
   121  
   122  	case *Signature:
   123  		h.WriteByte('F')
   124  		maphash.WriteComparable(h, t.Variadic())
   125  		tparams := t.TypeParams()
   126  		if n := tparams.Len(); n > 0 {
   127  			hr.inGenericSig = true // affects constraints, params, and results
   128  
   129  			maphash.WriteComparable(h, n)
   130  			for tparam := range tparams.TypeParams() {
   131  				hr.hash(h, tparam.Constraint())
   132  			}
   133  		}
   134  		hr.hashTuple(h, t.Params())
   135  		hr.hashTuple(h, t.Results())
   136  
   137  	case *Slice:
   138  		h.WriteByte('S')
   139  		hr.hash(h, t.Elem())
   140  
   141  	case *Struct:
   142  		h.WriteByte('R') // mnemonic: a struct is a record type
   143  		n := t.NumFields()
   144  		h.WriteByte(byte(n))
   145  		for i := range n {
   146  			f := t.Field(i)
   147  			maphash.WriteComparable(h, f.Anonymous())
   148  			// Ignore t.Tag(i), so that a single hash function
   149  			// can be used with both [Identical] and [IdenticalIgnoreTags].
   150  			h.WriteString(f.Name()) // (ignore f.Pkg)
   151  			hr.hash(h, f.Type())
   152  		}
   153  
   154  	case *Tuple:
   155  		hr.hashTuple(h, t)
   156  
   157  	case *TypeParam:
   158  		hr.hashTypeParam(h, t)
   159  
   160  	case *Union:
   161  		h.WriteByte('U')
   162  		// TODO(adonovan): opt: call (fork of) UnionTermSet from
   163  		// golang.org/x/tools/internal/typeparams/normalize.go.
   164  		// hr.hashTermSet(h, terms)
   165  
   166  	default:
   167  		panic(fmt.Sprintf("%T: %v", t, t))
   168  	}
   169  }
   170  
   171  func (hr hasher) hashTuple(h *maphash.Hash, t *Tuple) {
   172  	h.WriteByte('T')
   173  	h.WriteByte(byte(t.Len()))
   174  	for v := range t.Variables() {
   175  		hr.hash(h, v.Type())
   176  	}
   177  }
   178  
   179  // func (hr hasher) hashTermSet(h *maphash.Hash, terms []*Term) {
   180  // 	h.WriteByte(byte(len(terms)))
   181  // 	for _, term := range terms {
   182  // 		// term order is not significant.
   183  // 		h.WriteByte(byte(btoi(term.Tilde())))
   184  // 		hr.hash(h, term.Type())
   185  // 	}
   186  // }
   187  
   188  // hashTypeParam encodes a type parameter into hasher h.
   189  func (hr hasher) hashTypeParam(h *maphash.Hash, t *TypeParam) {
   190  	h.WriteByte('P')
   191  	// Within the signature of a generic function, TypeParams are
   192  	// identical if they have the same index and constraint, so we
   193  	// hash them based on index.
   194  	//
   195  	// When we are outside a generic function, free TypeParams are
   196  	// identical iff they are the same object, so we can use a
   197  	// more discriminating hash consistent with object identity.
   198  	// This optimization saves [Map] about 4% when hashing all the
   199  	// Info.Types in the forward closure of net/http.
   200  	if !hr.inGenericSig {
   201  		// Optimization: outside a generic function signature,
   202  		// use a more discrimating hash consistent with object identity.
   203  		hr.hashTypeName(h, t.Obj())
   204  	} else {
   205  		h.WriteByte(byte(t.Index()))
   206  	}
   207  }
   208  
   209  // hashTypeName hashes the pointer of tname.
   210  func (hasher) hashTypeName(h *maphash.Hash, tname *TypeName) {
   211  	h.WriteByte('N')
   212  	// Since Identical uses == to compare TypeNames,
   213  	// the hash function uses maphash.Comparable.
   214  	maphash.WriteComparable(h, tname)
   215  }
   216  
   217  // shallowHash computes a hash of t without looking at any of its
   218  // element Types, to avoid potential anonymous cycles in the types of
   219  // interface methods.
   220  //
   221  // When an unnamed non-empty interface type appears anywhere among the
   222  // arguments or results of an interface method, there is a potential
   223  // for endless recursion. Consider:
   224  //
   225  //	type X interface { m() []*interface { X } }
   226  //
   227  // The problem is that the Methods of the interface in m's result type
   228  // include m itself; there is no mention of the named type X that
   229  // might help us break the cycle.
   230  // (See comment in [Identical], case *Interface, for more.)
   231  func (hr hasher) shallowHash(h *maphash.Hash, t Type) {
   232  	// t is the type of an interface method (Signature),
   233  	// its params or results (Tuples), or their immediate
   234  	// elements (mostly Slice, Pointer, Basic, Named),
   235  	// so there's no need to optimize anything else.
   236  	switch t := t.(type) {
   237  	case *Alias:
   238  		hr.shallowHash(h, Unalias(t))
   239  
   240  	case *Array:
   241  		h.WriteByte('A')
   242  		maphash.WriteComparable(h, t.Len())
   243  		// ignore t.Elem()
   244  
   245  	case *Basic:
   246  		h.WriteByte('B')
   247  		h.WriteByte(byte(t.Kind()))
   248  
   249  	case *Chan:
   250  		h.WriteByte('C')
   251  		// ignore Dir(), Elem()
   252  
   253  	case *Interface:
   254  		h.WriteByte('I')
   255  		// no recursion here
   256  
   257  	case *Map:
   258  		h.WriteByte('M')
   259  		// ignore Key(), Elem()
   260  
   261  	case *Named:
   262  		hr.hashTypeName(h, t.Obj())
   263  
   264  	case *Pointer:
   265  		h.WriteByte('P')
   266  		// ignore t.Elem()
   267  
   268  	case *Signature:
   269  		h.WriteByte(byte(btoi(t.Variadic())))
   270  		// The Signature/Tuple recursion is always
   271  		// finite and invariably shallow.
   272  		hr.shallowHash(h, t.Params())
   273  		hr.shallowHash(h, t.Results())
   274  
   275  	case *Slice:
   276  		h.WriteByte('S')
   277  		// ignore t.Elem()
   278  
   279  	case *Struct:
   280  		h.WriteByte('R') // mnemonic: a struct is a record type
   281  		h.WriteByte(byte(t.NumFields()))
   282  		// ignore t.Fields()
   283  
   284  	case *Tuple:
   285  		h.WriteByte('T')
   286  		h.WriteByte(byte(t.Len()))
   287  		for v := range t.Variables() {
   288  			hr.shallowHash(h, v.Type())
   289  		}
   290  
   291  	case *TypeParam:
   292  		hr.hashTypeParam(h, t)
   293  
   294  	case *Union:
   295  		h.WriteByte('U')
   296  		// ignore term set
   297  
   298  	default:
   299  		panic(fmt.Sprintf("shallowHash: %T: %v", t, t))
   300  	}
   301  }
   302  
   303  func btoi(b bool) int {
   304  	if b {
   305  		return 1
   306  	} else {
   307  		return 0
   308  	}
   309  }
   310
View as plain text