proposal: x/tools/go/types/typeutil: add TypeMap[V]

[adonovan]

[EDIT: withdrawn in favor of this proposal:]

• proposal: go/types: add Hash function #69420

We propose to add a generic wrapper around typeutil.Map. The obvious name is TypeMap[V]. Only the necessary methods need to be parameterized; the remainder will be promoted from a non-exported embedding of Map.

(Aside: this technique seems quite general. If in future Map should ever sprout a method that we don't want promoted to TypeMap, but nor do we want to shadow it with a parameterized variant, it's possible for TypeMap to embed another field, of size zero, that defines a conflicting method, so the two annihilate.)

package typeutil // import "golang.org/x/tools/go/types/typeutil"

// TypeMap[V] is a generic wrapper around a [Map] from [types.Type] to V.
//
// The following methods are promoted from Map:
// [Map.SetHasher], [Map.Delete], [Map.String], [Map.Keys],
// [Map.KeysString], [Map.Len], [Map.Iterate].
type TypeMap[V any] struct{ _map }

type _map = Map // avoid exposing representation

// At returns the value corresponding to the key type,
// or zero if not present.
func (m *TypeMap[V]) At(key types.Type) (value V) {
	if m != nil {
		value, _ = m._map.At(key).(V)
	}
	return
}

// Set updates the value corresponding to the specified key type,
// and returns the previous value, or zero if the entry is new.
func (m *TypeMap[V]) Set(key types.Type, value V) (prev V) {
	if m != nil {
		prev, _ = m._map.Set(key, value).(V)
	}
	return
}

// This function would be declared in a file with a go1.23 tag:

// All returns a go1.23 iterator over the key/value entries of the map.
func (m *TypeMap[V]) All() iter.Seq2[Type, V] { ... }

[Update: I changed the declaration of All to use iter.Seq2, requiring a go1.23 build tag.]

@findleyr @griesemer

[gopherbot]

Change https://go.dev/cl/581435 mentions this issue: go/types/typeutil: TypeMap, a generic wrapper with go1.23 iterator

[findleyr]

Nice, this would be handy.

Though I think we should either have All return an iter.Seq2, or hold off on this API addition until the idiom has stabilized. I'm also not sure whether the All naming convention will win out over, say, Iter. IMO, no particular reason to bundle this with the proposal for a generic API.

[adonovan]

Good point. Since iter.Seq (which I think @rsc may merge this week) is not an alias, we can't spell out the func type for now in the declaration of All, and then replace it with iter.Seq later once go1.23 is assured, as that would be a breaking change. The All method would need to either be go1.23-tagged, or else permanently forgo the use of the informative type Seq. So, I propose to do that (tag it), as part of this proposal.

I think All is the right name. Generally the pattern seems to be that iterators describe the sequence, they don't just say "iterator".

[findleyr]

Hmm, I just considered the following:

• It's unfortunate that typeutil.{Map, TypeMap} both exist.
• I've always thought it would be nice to use typeutil.Map as a better implementation of types.Context. The current implementation of Context overloads the traversal of TypeString, which is tangled and can't be efficient.
• In general, this is a very useful helper type.

Therefore, what if we instead promoted this proposal to go/types.TypeMap, with a generic API?

[adonovan]

Therefore, what if we instead promoted this proposal to go/types.TypeMap, with a generic API?

I could get behind that. We'd have to scrutinize the API extra carefully, but I think typeutil.Map has proven itself by now.

@griesemer?

[findleyr]

@adonovan independent of promoting this to the standard library, I think we should reconsider the API:

• There's no need for Iterate, since it is not generic and redundant with All.
• I don't think we should include the KeysString and Keys methods, as they have resp. 0 and 1 non-test usages in x/tools, and don't seem to fit. If we want, we can later have TypeSet which behaves likes a set.
• SetHasher seems like it may be a premature optimization (to me). I could be convinced otherwise. If we move this proposal to go/types, I'd feel more strongly that we should leave out SetHasher.

[adonovan]

There's no need for Iterate, since it is not generic and redundant with All.

Agreed.

I don't think we should include the KeysString and Keys methods, as they have resp. 0 and 1 non-test usages in x/tools, and don't seem to fit. If we want, we can later have TypeSet which behaves likes a set.

Agreed. And it's only a matter of time before the iter package (or some other std one) provides iter.ToKeysSlice(Seq2[K,V]) []K.

SetHasher seems like it may be a premature optimization (to me). I could be convinced otherwise. If we move this proposal to go/types, I'd feel more strongly that we should leave out SetHasher.

Quite possibly, but IIRC it was motivated by profiling go/ssa and the observation that several Maps had highly correlated key sets. In particular, Program.RuntimeTypes did (still does) a lot of transitive reachability accumulation. (I would like to change that, by making the transitive step lazy and factoring ssa.forEachReachable in common with rta.addRuntimeType.) We should measure then decide.

Remember that even read-only operations on a typeutil.Map require a read-write change to the hasher, which complicates the locking story for the At accessor: RLock is not sufficient. That wouldn't change if we made the hasher private.

[griesemer]

I'm ok with a go/types.TypeMap if we have a stable API.
But we should also consider if we can make use of the upcoming package unique (#62483) and that way get process-wide unique type identifiers.

[adonovan]

consider if we can make use of the upcoming package unique (#62483) and that way get process-wide unique type identifiers.

I don't see the connection. TypeMap is a hashtable with custom hash/equivalence operators. Unique is about a global interning pool. We definitely don't want to mingle types.Objects from different "realms".

[findleyr]

We definitely don't want to mingle types.Objects from different "realms".

We may be able to benefit from the internal map implementation of unique, since it shares similar concerns. But we won't be able to use unique directly.

[rsc]

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

[adonovan]

Regarding moving this to go/types and eliminating the Hasher API: even if performance doesn't suffer (which we haven't shown yet), this won't work because go/ssa's support for generics needs a way to canonicalize a tuple of Types (not Vars, so types.Tuple won't do). Today it does this externally, making Hasher calls directly. So we would need to either expose the Hasher, or make the new TypeMap allow tuples of types as keys. (go/types defines TypeList as a tuple of types, but it's not a Type, and they can't be created externally.)

I think this needs more thought than than the go1.23 freeze allows. Let's put this on hold (both parts, typeutil and go/types).

[rsc]

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

[rsc]

Sorry, not sure why my bot moved it to active. Back to hold.

[gopherbot]

Change https://go.dev/cl/612217 mentions this issue: go/types: TypeMap and Hash, a hash map keyed by types

[adonovan]

Withdrawing this proposal in favor of #69420, which adds the new API direct to go/types.

[gopherbot]

This proposal has been declined as retracted.
— aclements for the proposal review group