go/types: additions to support type parameters

[findleyr]

This proposal formally introduces the changes we've made to support parameterized functions and types in go/types. See the full write-up here:
https://go.googlesource.com/proposal/+/master/design/47916-parameterized-go-types.md

Also see the corresponding proposal for go/ast and go/token: #47781.

Any feedback is appreciated. In recognition that this proposal contains a large new API surface, we will not start to evaluate whether discussion is resolved at least a few weeks. If there appears to be consensus that a change is required to the original proposal, we'll update the document and add a note here.

CC @griesemer

Changelog: (changes from the initial proposal)

• TParamList was renamed to TypeParamList
• TParams fields were renamed to TypeParams
• TArgs was renamed to TypeArgs
• RParams was renamed to RecvTypeParams
• Orig was renamed to Origin
• Info.Inferred was renamed to Info.Instances, changed to use the *ast.Ident as key, and updated to capture all type and signature instantiation.
• ArgumentError was tweaked to be more idiomatic.
• Environment was renamed to Context
• Setters on the *Signature type were replaced with a new constructor: NewSignatureType
• The TypeParams.Index accessor was added.
• Interface.IsConstraint was replaced by Interface.IsMethodSet.

Note: there are a few caveats/discrepancies in the current implementation. I'll keep this updated as they are resolved to coincide with the proposal.

• Instantiate will panic if passed anything other than a *Named or *Signature type, or with incorrect length targs. In the proposal we decided to instead make this return an error, but that is not yet done.

[scott-cotton]

Thanks for sharing.

Some initial surface reactions:

*Interface.IsConstraint could be renamed to *Interface.IsConstraintOnly or *Interface.HasTypeList, I would find find this more clear, to distinguish whether "IsConstraint" means that the *Interface.IsConstraint is actually used as a constraint.

Question: Why

func (*TypeParam) Constraint() *Interface
func (*TypeParam) SetConstraint(Type)

is *Interface on get and Type on set? Shouldn't that be exactly the same type?

From A high level, I think everything which provides an interface for instantiation should be coupled with an actual use case (eg as we discussed plans to treat x/tools/go/ssa, maybe it would be used there). I think also this section should describe how one navigates already instantiated types.

[mdempsky]

Are the SetTParams/SetRParams methods necessary? They feel out of character for the go/types API, where most data types are immutable. The other SetFoo methods (e.g., Named.SetUnderlying, TypeParams.SetConstraint) exist to break cycles, but at least Signatures can't be in cycles. I don't think Named can be either; e.g., type I[T I[int]] interface{} isn't accepted by go/types.

--

I'd suggest the following changes to Info.Inferred:

1. Key the map based on the *ast.Ident that uses the generic function, the same as is used to key the Info.Uses map.
2. Always have an Info.Inferred entry for any *ast.Ident that uses a generic function, not just when some of them are omitted in source. (Perhaps then rename the field too.)
3. Get rid of Sig; if a generic function is accessed without instantiation, then just set Types to the instantiated type, and users can use Uses to get the Func's original type. (Similar to how untyped constants work: Types records the context-appropriate implicit conversion type, whereas you can use Uses if you want to know the Const's original untyped type.)

I think this would considerably simplify the task of decomposing the use of a generic function into its Func and TypeList components.

--

We'll probably want to extend the Importer API again to allow passing Environment so it can use Instantiate. (The compiler avoids this because it uses its own importers and manages the cyclic dependency between Importer and Checker itself.)

I'd suggest this time, instead of just adding interface with more arguments (a la ImporterFrom) we define an interface method that takes a struct type (e.g., ImportConfig) as an argument. Then we can just extend that struct with additional fields as necessary in the future.

[findleyr]

@mdempsky

Are the SetTParams/SetRParams methods necessary? They feel out of character for the go/types API, where most data types are immutable.

Indeed they are out of character, and in fact the original (internal) draft of this API had new constructors (I think they were called e.g. NewGenericNamed, but we wouldn't use that naming convention now due to avoiding the word 'Generic'). The rationale for using setters is to avoid multiple constructors or having to deprecate NewNamed or NewSignature. There is precedent for using multiple steps to set up a type, though as you point out that precedent is restricted to cases where it is necessary to break cycles.

I'd suggest the following changes to Info.Inferred:

Thanks, I think we do need something to simplify Info.Inferred, and perhaps your suggestion is it. With your suggestions, all of the subtle cases in the document are reduced to the same lookup. Originally there was an additional implicit piece of data which was "at which expr does inference occur" (because sometimes we were using constraint type inference at the index expression alone if function argument inference was not necessary), but actually we now defer all inference to consider the full call expression.

I don't see a reason not to take your suggestions.

Always have an Info.Inferred entry for any *ast.Ident that uses a generic function

Get rid of Sig

Just to be clear, suppose I have f[...](...), and want to know (1) what is the instantiated function type, (2) what type arguments were used to instantiate, and (3) what was the original function type. You're suggesting that Info.Types[f] be the instantiated type, Info.Inferred[f] contain the type arguments, and then we use Info.Uses[f] to find the generic function type, right? That seems clean (also, FWIW I think all of this storage is strictly necessary if we want to be able to access this information from the identifier f alone). It's a bit strange to have Info.Types[f] be non-generic, but not that different from reporting the implied type for untyped constants.

Perhaps we should have a func (*Info) InstanceOf(*ast.Ident) (*Signature, *TypeList, *Signature) helper to consolidate this logic.

[findleyr]

@scott-cotton

Shouldn't that be exactly the same type?

Thanks very much, you're right: Constraint returns a Type (which may be *Named or *Interface), not an *Interface. This matches the current implementation, but was an error in the write-up. Fixed.

I think everything which provides an interface for instantiation should be coupled with an actual use case

Could you say more about what you mean? I think you mean "all the new APIs related to type and function instances should have examples"? In this case, you're right that it would be good to provide some examples of using TParams, TArgs, Inferred, etc. to interrogate instances.

[scott-cotton]

I think everything which provides an interface for instantiation should be coupled with an actual use case

Could you say more about what you mean? I think you mean "all the new APIs related to type and function instances should have examples"? In this case, you're right that it would be good to provide some examples of using TParams, TArgs, Inferred, etc. to interrogate instances.

Examples are good and I think they would suffice, given time constraints for 1.18. But what I was trying to bring up was more encouragement for generally considering use cases. From the point of view of everything that depends on stdlib go/*, its great that you have seriously considered backward compatibility already (for inputs which have no type params), but those things will tend to need to be extended to handle type parameters, and it is not yet clear how they will be extended. So this was more encouragement to consider end-to-end use cases.

(The compiler/internal implementations do not have this problem, because they are "the" implementation)

I thought of one such example which might be interesting to consider (also pulling in the ast and token changes): the printf vetter. Will it for example work on

type Intish interface { ~int, ~int64, ~uint64, ... }

func F[Int Intish](v Int, names ...string) string {
   buf := bytes.NewBuffer() 
   for _, name := range names {
       fmt.Fprintf(buf, "%s %d", name, v) // what if we use %s in stead of %d?
    }
    return buf.String()
}

More generally, the introduction of typeparams gives a lot of use cases for go/ast and go/types which are not read-only. In the example above, instantiating F for the types in Intish could be one thing the printf checker could do.

This feedback is more about process than content: I just have an intuition that keeping tabs of a running end-to-end example use case can help confirm, and possibly guide, the designs of std go/* for type parameters. If you (or we) have got the cycles for this kind of thing, great, I think it will help. But there is no specific content in this feedback point to address, so please don't take it as an objection of any kind to address.

(on a side note the development of typeparams based on compiler internal packages makes me curious about the possibility of exposing some of them, like ir)

[scott-cotton]

Some thoughts about

Notably, as *Signature does not have the equivalent of Named.TArgs, and there may not be explicit type arguments in the syntax, the existing content of the Info struct does not provide a way to look up the type arguments used for instantiation. For this we need a new construct, the Inferred type, which holds both the inferred type arguments and resulting non-parameterized signature. This may be looked up in a new Inferred map on the Info struct, which contains an entry for each expression where type inference occurred.

and the discussion on Inferred above.

To me, that the type of a function at a call site may be inferred or not (ie with different syntax) should not affect the representation of the type associated with the function expression at the call site. I think it would be most natural if the Info.Type of a function or method value at a call site were always instantiated (always instantiated if named, but func lits cannot be generic, so maybe that is ok). Then the simple mechanism for types.Named can be used to retrieve the generic type and arguments, and that will be more uniform.

Thoughts? Am I missing something?

[scott-cotton]

As a follow-up, I guess what I am trying to say in the last remark above about Inferred, is it seems like it would be much easier to use if both Signatures and Named had TArgs had TArgs() and Orig(), and then at all call sites, the Info.Type of the caller expression would always be the instantiated type.

[findleyr]

@scott-cotton, quick follow-up below. I'll follow-up in more detail next week (I'm currently traveling).

but those things will tend to need to be extended to handle type parameters, and it is not yet clear how they will be extended.

A couple related points here:

• We need to consider how existing APIs behave with respect to the new constructs. In the proposal write-up I've tried to call out types.Info and types.Identical specifically; others (such as AssignableTo) should follow from the spec. A fair bit of tool / analyzer behavior is determined by how the new constructs behave in these existing APIs.
• It is important to consider "what additional tools/analyzers" are needed for generic code, and ask whether the APIs proposed here suffice for implementing this additional functionality.

Any examples that inform these two points are very valuable.

The printf analyzer suggestion is a good example, because the implementation verifies properties of the underlying type of a variable. This could be updated to handle type parameters by accessing their constraints, considering embedded Unions, and walking their type set expression. However, we have an unexported method on type parameters: func (t *TypeParam) underIs(func (Type) bool) bool that would likely make updating the printf analyzer trivial. I wonder if we should expose it.

More generally, the introduction of typeparams gives a lot of use cases for go/ast and go/types which are not read-only. In the example above, instantiating F for the types in Intish could be one thing the printf checker could do.

The current APIs don't provide a high-level mechanism for "instantiating" function bodies. However, one good thing about keeping go/types and cmd/compile/internal/types2 in sync is that we know these APIs must be sufficient for this purpose, since they suffice for the compiler.

is it seems like it would be much easier to use if both Signatures and Named had TArgs had TArgs() and Orig()

I need to think about this a bit more.

[findleyr]

The current APIs don't provide a high-level mechanism for "instantiating" function bodies. However...

After writing this, it occurred to me that it might be helpful to provide a more general 'substitution' API, independent of Instantiate, for cases like this:

func _[T any](...) {
  tests := []struct { t T }{ ... }
  ...

That is to say, an API for substituting for type parameters in arbitrary types, not just the types associated with parameterized declarations.

[mdempsky]

Just to be clear, suppose I have f[...](...), and want to know (1) what is the instantiated function type, (2) what type arguments were used to instantiate, and (3) what was the original function type.

If there's an explicit (even partial) instantiation like f[...](...), then I would suggest Types["f"] be the generic type (the same as Uses["f"].Type()), and Types["f[...]"] be the instantiated type. It's only in the case of (fully) implicit instantiation like f(...) that Types["f"] would be the instantiated type and thus differ from Uses["f"].Type().

For f(...) we're forced to decide whether Types["f"] should be the instantiated type that matches the CallExpr or to be the generic type that matches Uses["f"].Type(). Since there's already a good way to get the latter, it seems sensible to me that Types["f"] should provide the former instead. (And as mentioned, I think it's consistent with how untyped constants work.)

For f[...](...) there's no such conflict. It would seem a little inconsistent in that case to have Types["f"] be the instantiated type.

Perhaps we should have a func (*Info) InstanceOf(*ast.Ident) (*Signature, *TypeList, *Signature) helper to consolidate this logic.

In principle, I like the idea of an API like that (but replacing the first Signature with Func). But I'll note that in practice, I almost never use Info.TypeOf.

[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