[EDIT: withdrawn in favor of this proposal:] - https://github.com/golang/go/issues/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

Comment From: gopherbot

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

Comment From: 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.

Comment From: 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".

Comment From: 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?

Comment From: 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?

Comment From: 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.

Comment From: 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.

Comment From: 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.

Comment From: adonovan

consider if we can make use of the upcoming package unique (https://github.com/golang/go/issues/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".

Comment From: 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.

Comment From: 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

Comment From: 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).

Comment From: 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

Comment From: rsc

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

Comment From: gopherbot

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

Comment From: adonovan

Withdrawing this proposal in favor of https://github.com/golang/go/issues/69420, which adds the new API direct to go/types.

Comment From: gopherbot

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