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:

https://github.com/golang/go/blob/a6ff433d6a927e8ad8eaa6828127233296d12ce5/src/cmd/compile/internal/noder/writer.go#L1318-L1327

https://github.com/golang/go/blob/a6ff433d6a927e8ad8eaa6828127233296d12ce5/src/cmd/compile/internal/noder/writer.go#L1773-L1813

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 #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 (#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

[rsc]

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.

For what it's worth, we have build.Context in go/build and I don't think that has been terribly confusing. It's also somewhat analogous to what types.Context would be.

I do think we need a better term than Environment.

[findleyr]

For what it's worth, we have build.Context in go/build and I don't think that has been terribly confusing. It's also somewhat analogous to what types.Context would be.

That's good precedent. types.Context is better than types.Environment. However, there do seem to be a fair number of academic references to 'typing context' (https://scholar.google.com/scholar?hl=en&as_sdt=0%2C33&q=%22typing+context%22&btnG=), and if we're worried about conceptual overloading for Environment, I think we should be worried about overloading Context as well.

[scott-cotton]

FWIW, I prefer types.Context, then types.Env, then types.Environment, with a close tie between the first 2.

[gopherbot]

Change https://golang.org/cl/348811 mentions this issue: go/types: rename Environment to Context

[gopherbot]

Change https://golang.org/cl/348810 mentions this issue: go/types, types2: rename RParams -> RecvTypeParams

[gopherbot]

Change https://golang.org/cl/348949 mentions this issue: 47916-parameterized-go-types.md: update some names to reflect discussion

[findleyr]

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.

Just wanted to point out that this suggestion by @scott-cotton still needs to be resolved -- I forgot to include it in https://github.com/golang/go/issues/47916#issuecomment-913751576 above. My intuition is that while this could be done, though the implementation may be a bit awkward. This needs experimentation.

[scott-cotton]

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.

@timothy-king are their proposals or can you share? What about ssa?

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

Just wanted to point out that this suggestion by @scott-cotton still needs to be resolved -- I forgot to include it in #47916 (comment) above. My intuition is that while this could be done, though the implementation may be a bit awkward. This needs experimentation.

Looking at the other outstanding non-surface issues, this point seems more cosmetic in a way, but perhaps more deep in the sense of "simplicity is complex". It would be nice if the relationship between instantiations and their parameterised types were uniform. But given everything else, I would just keep this suggestion in the background: it is more important at this stage that it works than that it works simply.

[scott-cotton]

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):

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

This seems like a Good Idea to me.

[gopherbot]

Change https://golang.org/cl/349412 mentions this issue: go/types: instantiate methods when instantiating Named types

[gopherbot]

Change https://golang.org/cl/349413 mentions this issue: go/types: implement Identical for *Union types

[findleyr]

@mdempsky I experimented with the first two of your suggested changes to Info.Inferred here: https://golang.org/cl/349629. This keys off of the *ast.Ident and always records type arguments even if no inference occurred. However, I didn't get rid of Sig: if the inferred function is imported (as in lib.F), we don't record type information for the identifier F, only for lib.F. I like the idea of being able to join on *ast.Ident to access all information, and having to find the SelectorExpr to get the instantiated type breaks this. WDYT?

@scott-cotton I thought more about having TypeArgs and Orig on Signature, and think that we should leave it as-is. In the case of a Named type, type arguments and the original type are part of the type identity, but this isn't the case for Signatures. I think a good general rule is that we should avoid exposing information on types that isn't part of their identity, both to keep the API minimal and to avoid memory bloat (applications like gopls hold a lot of types in memory). If we change our minds we can always add these methods to Signature, but we could never reverse the decision.

[mdempsky]

However, I didn't get rid of Sig: if the inferred function is imported (as in lib.F), we don't record type information for the identifier F, only for lib.F.

You mean we only set Info.Types for lib.F? Can't you use Info.Uses for (bare) F instead?

But I'm not opposed to keeping Sig if you think it's valuable.

[findleyr]

You mean we only set Info.Types for lib.F? Can't you use Info.Uses for (bare) F instead?

But I'm not opposed to keeping Sig if you think it's valuable.

I mean that in the following case: lib.F(args...), where do we look up the non-generic signature, if we don't provide Sig? We can look up Info.Uses["F"] to get the generic signature, but if we want non-generic type information we'd need to look up Info.Types["lib.F"] (assuming this type has been updated to the inferred type), or change the way we record type information for selectors. I feel like we shouldn't make users find the selector. For example, one can imagine a use case that starts from info.Inferred.

[mdempsky]

where do we look up the non-generic signature

Ohh, sorry, I forgot Sig is the instantiated signature. I was thinking it was the uninstantiated one.

Yeah, I think including the instantiated signature there makes sense then.

[findleyr]

In case anyone is interested in this proposal but doesn't follow the #tools slack, I'll be available at 15:30 UTC on Wednesday to go over this proposal and the AST proposal (#47781). My plan is to briefly go over the proposals, talk about some use-cases, and have a discussion with anyone who is interested (if anyone shows up!). More info here: https://groups.google.com/g/golang-tools/c/d5wjyBUjLEI

[gopherbot]

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

[gopherbot]

Change https://golang.org/cl/349772 mentions this issue: go/ast,go/parser: spell out 'Type' in type parameter unexported functions

[gopherbot]

Change https://golang.org/cl/349629 mentions this issue: go/types: record all instances, not just inferred instances

[findleyr]

After several discussions regarding Info.Inferred, with CL 349629 I think we've found a clean API. Specifically, this CL

• Renames Info.Inferred to Info.Instances
• Keys the Info.Instances map on the *ast.Ident denoting the parameterized object
• Changes type Inferred to type Instance struct { TypeArgs *TypeList; Type Type }
• Records all instances (both *Named and *Signature), not just inferred signatures

Here are some indicators that this is the correct API:

• It is easy to describe. The previous API required a longish doc comment describing which expressions could be map keys, and when information was recorded.
• It will be useful if/when we support inference for type instances, which is being discussed.
• It is easy to look up the generic type, via Info.Uses[id].Type().
• Keying on identifier is flexible: at whichever level you're considering an instantiation expression, you should have access to the identifier.
• Recording all instances helps answer the following question: what is the position of an instance? For *Named instances we had little option but to have Obj() return the generic declaration type name (else we'd depend on where the instance was first type-checked). But it is easy to imagine situations where we'd want to map an instance back to source positions where it occurs.
• Recording all instances makes it easy for users like go/ssa to precompute instantiated function bodies.

[findleyr]

We've made some good progress on this proposal over the past week.

• As mentioned in https://github.com/golang/go/issues/47916#issuecomment-920009890, I think we've found the correct additions to types.Info.
• We've figured out a clean way to instantiate methods on type instances during type checking.
• Instantation should now be concurrency-safe.
• We're pretty sure that we can (and should) support type parameters on aliases (#46477) via an Alias type, though I'd prefer if we worked out the details a bit more.

At this point, I am starting to feel satisfied with the proposed APIs, though I do think we'll need at least one additional API:

• For updating something like the printf analyzer, we really want a normalized view of the type set for a type parameter. Having users walk embedded Union types is not good enough: they'd need to re-implement the type set algorithms we use internally to compute things like intersections. We should expose something like func (*Interface) UnderIs(func(Type) bool) bool.
• For x/tools/go/ssa, we'll need a more generalized type substituter in order to instantiate function bodies. We should perhaps expose this from go/types (we have an internal substituter for instantiation), but in fact our types.subster is currently insufficient for generalized substitution -- it makes certain assumptions that are only valid in the context of a declaration. My current feeling on this after discussing with @timothy-king is that we should write our own subtituter while working on go/ssa, and perhaps consider porting it to go/types in the future.

I'll note that there are really two milestones for the go/types API: (1) the point at which existing new APIs don't change, and (2) the point at which we're satisfied with the completeness of our APIs. I don't think these milestones need to be the same proposal, so perhaps if there is no change in the current APIs over the next couple weeks, we should consider accepting this proposal to mean (1), with the understanding that if/when we encounter new APIs that would help us add support for type parameters in tools and libraries, we can have additional proposal(s).

[findleyr]

Thanks all who attended the tools call today. We had a good discussion, hopefully the first of several regarding support for type parameters in tools.

Unfortunately we forgot to start recording (:facepalm: my mistake). Here are some concrete suggestions that came up during the call:

• [x] @rogpeppe suggested that we rename Named.Orig to Origin; Origin is a better expansion than Original. I agree, and spelling it out is better.
• [ ] @mvdan suggested we switch from SetTypeParams APIs to new constructors (NewGenericNamed, NewGenericSignature), and others agreed. The point being that we should not expose a mutable API if it is not strictly necessary. We've gone back and forth on this, and perhaps we arrived at the wrong conclusion.
• [x] @rogpeppe suggested to use a pointer receiver for ArgumentError methods.
• [ ] @rogpeppe asked what Interface.IsConstraint will mean if type restricting elements are permitted in any interface? Will it always return false? What if others rely on it meaning 'has type restricting elements'? Maybe if we choose to expose something like Interface.UnderIs, this method can be removed.
• On that note, I think there was consensus that an UnderIs would be useful, though @jba questioned the name UnderIs, and pointed out that it should probably also provide a tilde bool argument to the given func. We should think of a better name before officially proposing this API.
• There also seemed to be consensus that providing a transitional package like x/tools/internal/typeparams would be helpful.

(to those who attended: please correct inaccuracies/omissions).

[gopherbot]

Change https://golang.org/cl/350996 mentions this issue: go/types: export Named._Orig as Named.Origin

[gopherbot]

Change https://golang.org/cl/351335 mentions this issue: go/types: tweaks to ArgumentError to be more idiomatic

[findleyr]

Status update: we've addressed a couple of the points from https://github.com/golang/go/issues/47916#issuecomment-920221299. We also want to revisit the name IsConstraint.

Here is the latest status on the outstanding large questions:

*Regarding whether to switch from SetTypeParams to new constructors** (most recently raised during the types call): currently Named.SetTypeParams is actually necessary to break cycles in the importer for cases like #46461's

type T[U interface{ M() T[U] }] int

We could probably work around this, but it would require changing the way the importer works such that we only set type parameter constraints after binding them to a type. I am hesitant to do this at this point. Signature does not suffer from these problems, however.

If we switch to constructors, we'd probably call them NewNamedType and NewSignatureType based on the precedent of NewInterfaceType. I think this is still T.B.D, but am leaning toward no changes here.

Regarding how to handle type parameters on aliases (#46477): @griesemer and I have sufficiently convinced ourselves that we can't do this without a new node type Alias. Especially something like type lexer[T any] = func(string, int) (T, int, bool) (mentioned by Russ), where there is no defined type, would be very hard to handle without having an intermediate Type. We already have trouble producing good error messages involving aliases.

(off topic: Our rough plan for how to proceed is to use a new Alias type by default only if there are type parameters on the alias (for compatibility's sake). We would also consider an opt-in flag on types.Config to produce Alias nodes for all aliases; the compiler would use this for types2 to get better error messages. This would help resolve some long-standing bugs related to aliases.)

Regarding exposing a representation for type sets or a more general Substitute API: I think we should decouple this from this proposal, and implement these in x/tools. We're unlikely to be confident that we've found the correct API before the freeze, and I think both of these can be implemented in x/tools as we work on things like go/ssa

Regarding the name Environment vs Context: I personally am fine with either at this point, but we're reaching out to some type theory experts to see if we're missing something.

---

We hope to resolve all of these this week. If you are reading this and have a question or perspective that you feel has not been adequately addressed, please comment soon! We're beginning to use these APIs significantly in x/tools, so changes are becoming increasingly painful at this point, and we need to freeze these APIs soon.

[gopherbot]

Change https://golang.org/cl/352615 mentions this issue: go/types: add a NewSignatureType constructor accepting type parameters

[gopherbot]

Change https://golang.org/cl/352616 mentions this issue: go/types: add the Interface.IsMethodSet method