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