proposal: go/types: add Hash function

[adonovan]

[Edit: this proposal is now just for the types.Hash function. The HashMap is another proposal.]

We propose to add the HashMap data type (a generic evolution of golang.org/x/tools/go/types/typeutil.Map) to the standard go/types package, with the following API:

package types // import "go/types"

// Hash computes a hash value for the given type t such that Identical(x, y) implies Hash(x) == Hash(y).
func Hash(t Type) uint64

Rescinded part of the proposal:

// HashMap[V] is a mapping from Type to values of type V.
// Map keys (types) are considered equivalent if they are Identical.
// As with map[K]V, a nil *HashMap is a valid empty map.
type HashMap[V any] struct { ... }

// All returns an iterator over the key/value entries of the map in undefined order.
func (m *HashMap[V]) All() iter.Seq2[Type, V]

// At returns the map entry for the given key. It returns zero if the entry is not present.
func (m *HashMap[V]) At(key Type) V

// Delete removes th//e entry with the given key, if any. It returns true if the entry was found.
func (m *HashMap[V]) Delete(key Type) bool

// Keys returns an iterator over the map keys in undefined order.
func (m *HashMap[V]) Keys() iter.Seq[Type]

// KeysString returns a string representation of the map's key set in unspecified order.
func (m *HashMap[V]) KeysString() string

// Len returns the number of map entries.
func (m *HashMap[V]) Len() int

// Set updates the map entry for key to value, and returns the previous entry, if any.
func (m *HashMap[V]) Set(key Type, value V) (prev V)

// String returns a string representation of the map's entries in unspecified order.
// Values are printed as if by fmt.Sprint.
func (m *HashMap[V]) String() string

Some notes:

• This proposal supersedes proposal: x/tools/go/types/typeutil: add TypeMap[V] #67161, to x/tools/go/types/typeutil.Map.
• It is generic, whereas typeutil.Map is not.
• It uses idiomatic Go 1.23 iterators.
• The typeutil.Hasher type and SetHasher method are not part of this proposal. They had no performance advantage, and the statefulness turned reads into writes. The hash recursion bottoms out at named types, so most types are shallow.
• There is still no way to distinguish "m[k] is zero" from "missing"; this has never been a problem in practice.
• The Hash function does not accept a seed and thus HashMap is vulnerable to flooding. But the type checker is vulnerable to various other performance problems if an attacker controls its input.

[gabyhelp]

Related Issues and Documentation

• proposal: x/tools/go/types/typeutil: add TypeMap[V] #67161
• hash/maphash: add func Comparable #54670
• x/tools/go/types/typeutil: gut Hasher #69407

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[ianlancetaylor]

1. What's the point of KeysString?
2. If this is going to be an exported type, I think we should support some way to distinguish the zero value from the non-existent value. We can keep At for convenience, and add Contains. We can change Set to return an additional bool.

[adonovan]

1. What's the point of KeysString?

This type is often used as a set, as this convenience method prints {T1, ..., Tn} without all the informationlessT: true values.

2. If this is going to be an exported type, I think we should support some way to distinguish the zero value from the non-existent value. We can keep At for convenience, and add Contains. We can change Set to return an additional bool.

Those are principled suggestions, but in practice the value has always been either a non-nil pointer (in which case nil => missing) or true (in which case false => missing), so it has never been a problem. But uses of this type are few enough between that the convenience of At/Set either way is a minor consideration.

[jimmyfrasche]

Is there anything Type-specific about HashMap other than using Hash?

Put another way, if there were an appropriately-defined "container/hashmap", could you just have something like

package types

import "container/hashmap"

func MakeHashMap[V any]() hashmap.Map[Type, V] {
  return hashmap.Make[Type, V](Hash)
}

[adonovan]

Is there anything Type-specific about HashMap other than using Hash?

Very good question. Now that you mention it, no, the HashMap is completely generic other than the fact it assumes (K=types.Type, hash=types.Hash, eq=types.Identical). If container/hashmap existed this proposal could reduce to just the Hash function, and perhaps a convenience constructor:

func Hash(Type) uint

type HashMap[V any] = hashmap.Map[Type, V] 

func NewHashMap[V any]() *HashMap[V] { return hashmap.New(Hash, Identical) }

[adonovan]

In light of @jimmyfrasche's idea, let's restrict this proposal to just the Hash function (the tricky part), with the expectation that a generic hash table (the easy part) will someday follow and that in the meantime it's easy enough for clients to write their own HashMap.

[adonovan]

cc @jba, who is thinking about unordered maps. Our generic unordered and ordered maps should be aligned.

[aclements]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.

[adonovan]

My only real question here is whether the Hash function needs to take a seed parameter to prevent flooding. As I mentioned above, I don't think hash flooding is a real concern because if you control its inputs, the type checker is already far more vulnerable than a hash table to DoS attacks. But what does concern me is ergonomics: the Hash function should interoperate with the proposed standard hash-based map, which may demand that hash functions accept a seed.

Perhaps @ianlancetaylor and @prattmic can opine.

[aclements]

I'm slightly inclined toward providing a seed in the style of the maphash package. That is, the seed is opaque and the only thing a caller can do is generate a new one. Partly this would be for consistency, partly it would be to preempt any question of flooding attacks on this hash.

We can always use a per-process seed to complicate an attack, though that's certainly not as good as a per-table seed. If we do that instead of an explicit seed, I think we would have to document that the hash function is not consistent from process to process. One advantage of requiring an explicit seed is that it makes it clear in the API where the boundary around comparable hashes lies.

[Merovius]

The proposed API seems to imply that the hash is stable across process invocations. Which implies that changing the hash function (or the hashing process) in the future would be a breaking change. Do we want to get locked into that?

The only advantage of a stable function that I can think of is that you could use the hash in process-external communication (like an on-disk cache or if you do something like running analyzers over the network). If we want that, we probably want the seed (if any) to not be opaque either.

If we don't want to commit, another advantage of a seed argument (IMO) is that it makes this instability more obvious in the API.

[adonovan]

The proposed API seems to imply that the hash is stable across process invocations. Which implies that changing the hash function (or the hashing process) in the future would be a breaking change. Do we want to get locked into that?

Good question. No, we certainly do not; but whether or not we have a seed parameter I think we can reserve the right to change the hash function arbitrarily with judicious documentation.

[adonovan]

This proposal is on hold until we resolve the fundamental question:

• proposal: hash: standardize the hash function #70471

[aclements]

The proposed API seems to imply that the hash is stable across process invocations.

As @adonovan mentioned above, we certainly want to be able to change the hash function, so we can't guarantee it will be stable across process invocations.

Given that, I would argue we need to make it aggressively unstable, much like how we randomize map iteration order, so that people don't start to depend on any sort of stability. Certainly the minimum bar for that is a per-process invocation seed.

[aclements]

Placed on hold.