proposal: spec: remove cycle restriction for type parameters

[griesemer]

Go Programming Experience

Experienced

Other Languages Experience

No response

Related Idea

• Has this idea, or one like it, been proposed before?
• Does this affect error handling?
• Is this about generics?
• Is this change backward compatible? Breaking the Go 1 compatibility guarantee is a large cost and requires a large benefit

Has this idea, or one like it, been proposed before?

No.

Does this affect error handling?

No.

Is this about generics?

Yes.

It removes a restriction currently present for type parameters.

Proposal

Per the spec:

Within a type parameter list of a generic type T, a type constraint may not (directly, or indirectly through the type parameter list of another generic type) refer to T.

It seems that we should be able to remove this restriction. The respective examples don't seem to cause problems for the type checker anymore, at tip, now that issue #68162 has been addressed.

Language Spec Changes

No response

Informal Change

No response

Is this change backward compatible?

Yes.

Orthogonality: How does this change interact or overlap with existing features?

This feature will simply remove a restriction.
It may interact with other possible cycles (to be investigated).

Would this change make Go easier or harder to learn, and why?

It would make Go easier to learn because there's fewer rules.

Cost Description

Currently, the type checker doesn't enforce this restriction anymore, so the implementation cost appears to be zero at the moment but for additional tests.
That said, we may uncover as of yet unknown errors due to cycles that were not possible without this change.

Changes to Go ToolChain

Should be minimal because the relevant existing tools rely on the output produced by the type checker.

Performance Costs

There's no compile time cost. The implementation removed an extremely cheap 'if' statement.

Prototype

See fix for #68162.

[griesemer]

cc: @adonovan @findleyr @mrkfrmn

[gopherbot]

Change https://go.dev/cl/711422 mentions this issue: spec: remove cycle restriction for type parameters

[ianlancetaylor]

What about this kind of cycle?

// T is a type such that the methods of P are the methods of T, and vice-versa.
type T[P T[P]] interface { P }

[griesemer]

This case is not permitted because a "term" (P inside the interface) cannot be a type parameter. Per the spec, under General interfaces:

The type T in a term of the form T or ~T cannot be a type parameter, ...

[ianlancetaylor]

Hmmm, but interface { P } isn't a general interface. It's an ordinary interface with an embedded type. Isn't this covered by the "Embedded interfaces" section? That section doesn't seem to prohibit embedding a type parameter. Though perhaps it should.

[griesemer]

Ordinary interfaces are just a special case of general interfaces; i.e., a general interface with a single term that is an interface "degrades" into an ordinary interfaces. So I think this case is already covered.

The cycle restriction in this issue is specific to cycles that "pass through" the type parameter list, not other cycles.

[mrkfrmn]

I'm generally supportive of this idea — in terms of cycle detection rules, I (at least at a glance) don't see why a cycle via constraints is to be avoided.

How would this affect something like:

type T[P T[P]] int

type I T[int]

Is I a valid instantiation? Can T be instantiated at all?

I've been confused by this specific case in the past, but worth discussing here.

[griesemer]

Instantiation always proceeds in two steps:

1. The type argument is substituted for its corresponding type parameter.
   So P is replaced by int in the declaration of T and we get:

type T[int T[int]] int

2. After substitution, each type argument must satisfy the constraint.
   So we need to check if int satisfies T[int]; i.e. we need to check if int is in the typeset of the constraint. The constraint T[int] is a shortcut for interface{T[int]}, and T[int] is a instantiated named (and notably non-interface!) type, which is different from any other type, certainly different from int. So the type set consists of T[int] and int is not in the the typeset. Hence instantiation fails.

Because instantiation fails, this code is invalid.

(Note that the code would be valid if the declaration was an alias declaration T[P T[P]] = int because T[int] is an alias for int. Sadly that code crashes the type checker at the moment. See issue #75897.)

This particular definition cannot be instantiated at all because any instantiation produces a named non-interface type T[X] for some X and X is never in the type set interface{T[X]}.

But it looks different if the definition is, i.e., where T defines an interface type.

type T[P T[P]] interface{ m() }

This can be instantiated by (for instance):

type M struct{}
func (M) m() {}

because the constraint is now the interface T[M]and so the requirement is that M has a method m which it does.

Constraints are interfaces after all, and were initially meant to constrain method sets. It's the "type set feature" that we added to interfaces - while very useful in practice - leads to perhaps unusual behavior (in the initial example), not the other way round.

[findleyr]

+1, there's no need for this restriction, by construction: constraints can be checked in an entirely separate pass, since they do not affect substitution.

I'll note that types.Instantiate does this in the wrong order: it verifies first. That probably doesn't matter since it's primarily used by importers, but we should get it right.

[aclements]

@griesemer , could you add some examples of what doesn't work today but would work with this change?