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

[scott-cotton]

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.

I think this reasoning is more consistent w.r.t. how generics are treated. But I would guess a common use case (such as call graph construction) would tend to want to treat call sites uniformly -- whether or not they have instantiated type parameters. if Types["f"] for generic f at calsite in form f(...) is the instantiated type, then I guess it would be easier for analysers to consider function calls uniformly.

Although in any case, the call might be in scope of and make reference to a type parameter, if the type is the instantiated type, then an analyzer only needs to think about type parameters that are not bound. This seems easier to me for any analyzer which needs to treat call sites.

One thing is becoming clear: golang.org/x/tools/go has a long way to go to support type parameters. I am not even sure what a call graph is in a go library with type parameters... unless the call graph has type parameters but then maybe there is a type switch that will make it rather hairy to comprehend (all that on top of the different algos and static/dynamic distinctions in place now...)

@timothy-king perhaps a tracking issue is in order for golang.org/x/tools/go/....?

[mdempsky]

But I would guess a common use case (such as call graph construction) would tend to want to treat call sites uniformly -- whether or not they have instantiated type parameters.

Ack, this is the use case I have in mind from having worked on integrating types2 into cmd/compile. The uniformity in my proposal is that you can always strip away explicit instantiations and package qualification.

E.g., in unified IR, there's this logic:

go/src/cmd/compile/internal/noder/writer.go

Lines 1318 to 1327 in a6ff433

	if inf, ok := w.p.info.Inferred[expr]; ok {
	obj, _ := lookupObj(w.p.info, expr.Fun)
	assert(obj != nil)
	// As if w.expr(expr.Fun), but using inf.TArgs instead.
	w.code(exprName)
	w.obj(obj, inf.TArgs)
	} else {
	w.expr(expr.Fun)
	}

go/src/cmd/compile/internal/noder/writer.go

Lines 1773 to 1813 in a6ff433

	func lookupObj(info *types2.Info, expr syntax.Expr) (obj types2.Object, targs *types2.TypeList) {
	if index, ok := expr.(*syntax.IndexExpr); ok {
	if inf, ok := info.Inferred[index]; ok {
	targs = inf.TArgs
	} else {
	args := unpackListExpr(index.Index)
	if len(args) == 1 {
	tv, ok := info.Types[args[0]]
	assert(ok)
	if tv.IsValue() {
	return // normal index expression
	}
	}
	list := make([]types2.Type, len(args))
	for i, arg := range args {
	tv, ok := info.Types[arg]
	assert(ok)
	assert(tv.IsType())
	list[i] = tv.Type
	}
	targs = types2.NewTypeList(list)
	}
	expr = index.X
	}
	// Strip package qualifier, if present.
	if sel, ok := expr.(*syntax.SelectorExpr); ok {
	if !isPkgQual(info, sel) {
	return // normal selector expression
	}
	expr = sel.Sel
	}
	if name, ok := expr.(*syntax.Name); ok {
	obj, _ = info.Uses[name]
	}
	return
	}

My suggestions would simplify the first code to just w.expr(expr.Fun) and then the second to:

func lookupObj(info *types2.Info, expr syntax.Expr) (obj types2.Object, targs *types2.TypeList) {
	// Strip explicit instantiation, if present.
	if index, ok := expr.(*syntax.IndexExpr); ok {
		if args := unpackListExpr(index.Index); len(args) == 1 {
			tv, ok := info.Types[args[0]]
			assert(ok)
			if tv.IsValue() {
				return // normal index expression
			}
		}
		expr = index.X
	}

	// Strip package qualifier, if present.
	if sel, ok := expr.(*syntax.SelectorExpr); ok {
		if !isPkgQual(info, sel) {
			return // normal selector expression
		}
		expr = sel.Sel
	}

	if name, ok := expr.(*syntax.Name); ok {
		obj = info.Uses[name]
		targs = info.Inferred[name]
	}
	return
}

I am not even sure what a call graph is in a go library with type parameters

I expect most analysis will just ignore the type parameters. More sophisticated analysis will probably want to just treat them similarly to regular parameters.

[scott-cotton]

@mdempsky thanks for the clarification.

I still wonder whether there is existing code which supposes that, for call 'f.(args)', Types[f].(*types.Signature).Param(i) can be assigned from Types[args[I]].

Hard to say the behaviour impact w.r.t. compatibility.

[mdempsky]

I still wonder whether there is existing code which supposes that, for call 'f.(args)', Types[f].(*types.Signature).Param(i) can be assigned from Types[args[I]].

Sorry, I'm not sure I follow your concern here. I think my suggestion does ensure that would work. In particular, for any ast.CallExpr, I'm recommending that Types[call.Fun] will always be an instantiated Signature type, compatible with corresponding Types[call.Args[i]].

Unless I have your point backwards, and you're questioning whether we actually need to guarantee that? If so, I offer mdempsky/unconvert as an existence proof of a go/types application that expects that to work: https://github.com/mdempsky/unconvert/blob/95ecdbfc0b5f3e65790c43c77874ee5357ad8a8f/unconvert.go#L492

[scott-cotton]

@mdempsky sorry I misunderstood, I think we were saying the same thing but weren't aware :)

thanks for the link to unconvert; good to see it will work with your suggestion.

(I still think it is worth considering if .Orig() and .TArgs can be extended so that it works for call.Fun as well as Named)

[sbinet]

(not sure where to report this, so here it goes)

it seems there's a typo in the Type parameter and type argument lists section where:

type TParamList struct { /* ... */ }

func (*TypeList) Len() int
func (*TypeList) At(i int) *TypeParam

should actually read:

type TParamList struct { /* ... */ }

func (*TParamList) Len() int
func (*TParamList) At(i int) *TypeParam

[findleyr]

@sbinet yes you're right, thanks for pointing that out.

Fixed in https://golang.org/cl/346089.

[timothy-king]

There has been a lot of discussion so far about x/tools/go already. The one package I am somewhat worried about is x/tools/go/analysis/passes/buildssa. I need to confirm that building the ssa for the current package will not need generic function/method bodies from gcimporter. I think this will be clearer when the implementation is a bit further along.

[findleyr]

A brief summary of the current status of this proposal (some of this is contained in the comments above, some of it is from other discussions):

We've discussed a couple superficial changes to the proposal.

• As discussed in go/ast, go/token: additions to support type parameters #47781, we're going to move to spelling out 'Type' everywhere, as in TypeArgs and TypeParams rather than TArgs and TParams.
• To avoid confusion with the concept of typing environment, we're considering new names for the proposed Environment type. One leading contender is actually Context, though we'd tried to avoid that initially. On further consideration, it is probably unlikely that a types.Context would be confused with a context.Context.

Additionally, we still need to work out the following non-superficial changes:

• Whether or not to provide an API like TypeParam.UnderIs, for checking conditions on the type set of a type parameter.
• Whether a more general substitution API is needed by libraries like go/ssa.
• Whether we can cleanly support type parameters on aliases (spec: generics: permit type parameters on aliases #46477) without moving type parameters to TypeName.
• Whether there are any issues with the changes to types.Inferred proposed by @mdempsky above. (it looks good, but we want to try it out).

At least all of these points need to be resolved. I'll update the proposal doc and top comment of this issue to reflect this (likely tomorrow as today is a holiday in the US).

[findleyr]

Regarding the name types.Context: given that https://en.wikipedia.org/wiki/Typing_environment mentions 'typing context' as an alternative name for 'typing environment', I'm not sure whether renaming Environment to Context is a clear improvement. Context seems to suffer both from confusion with 'typing context', and with context.Context.

I think we should explore other alternative names.

[gopherbot]

Change https://golang.org/cl/348376 mentions this issue: go/types: spell out 'Type' in type parameter APIs

[findleyr]

Thanks everyone who helped solidify this proposal. This is a large API surface and I'm very grateful for the feedback.

I'm not closing this yet as there are a few edge cases that need to be cleaned up (notably some type strings need to be improved, and Instantiate needs to return an error rather than panicking given mismatching cardinality of type arguments).

[gopherbot]

Change https://golang.org/cl/363635 mentions this issue: go/types: return an error from Instantiate on incorrect len(targs)

[gopherbot]

Change https://golang.org/cl/364534 mentions this issue: cmd/compile/internal/types2: return an error from Instantiate on incorrect len(targs)

[gopherbot]

Change https://golang.org/cl/364535 mentions this issue: cmd/compile/internal/types2: tweaks to ArgumentError to be more idiomatic

[gopherbot]

Change https://golang.org/cl/364716 mentions this issue: go/types: underlying type of a type parameter is its constraint interface

[gopherbot]

Change https://golang.org/cl/368956 mentions this issue: 47916-parameterized-go-types.md: implicit interfaces, any, TypeParam Index

[gopherbot]

Change https://golang.org/cl/369475 mentions this issue: go/types, types2: unexport NewTypeList

[gopherbot]

Change https://golang.org/cl/373775 mentions this issue: doc/go1.18: mention new go/types/Config.Context field