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

[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.

[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?

[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