cmd/compile (types2, go/types): cannot infer generic interface types

[rogpeppe]

commit 8ea0120

The type inference algorithm does not work when the actual parameter is a concrete type and the formal parameter is a generic interface type. It looks like the type inference description in the proposal doesn't cover interfaces, but I suspect it should.

https://go2goplay.golang.org/p/C53vOfwA9vq

package main

type S struct {}

func (S) M() byte {
	return 0
}

type I[T any] interface {
	M() T
}

func F[T any](x I[T]) {
	x.M()
}

func main() {
	F(S{})
}

This fails with the error:

prog.go2:18:4: type S of (S literal) does not match I[T] (cannot infer T)

FWIW type interfence doesn't work when the interface argument is a type parameter either, but I can't work out if that's covered by the proposal or not: https://go2goplay.golang.org/p/pAouk3xkmOX

func F[X I[T], T any](x X) {
	x.M()
}

[dmitshur]

/cc @griesemer

[ianlancetaylor]

I agree that the current inference algorithm doesn't permit this inference. I'm not at all sure that it should. It requires that we go beyond looking at the type of the argument, to looking at the method set of the argument. And as far as I can see it would only be useful to infer the type parameter of a parameterized interface type. There is a pretty long step from argument method set to type argument for interface type. Our goal for type inference is not all possible type inference, it's straightforward and easily understood type inference. At least at first glance, I don't think this meets that goal.

[griesemer]

Marked as FeatureRequest as this is not a bug in the prototype.

[dmitshur]

@griesemer An issue should have one of NeedsInvestigation, NeedsDecision, or NeedsFix labels after being triaged (per https://golang.org/wiki/HandlingIssues#issue-states). I'll re-add NeedsInvestigation, but please feel to change it if another Needs label is more appropriate.

[griesemer]

@dmitshur ACK. Thanks for the reminder.

[rogpeppe]

FWIW I ran across this when experimenting with making the io package generic. When dealing with generic interfaces I suspect it will be very common to pass a concrete implementation to a function that accepts the generic interface as an argument, just as in current Go it's common to pass a concrete type to an interface parameter.

This issue will tend to arise when using any generic iterator interface AFAICS, so I think it would be worth addressing. It certainly seemed like it should work when I was adapting the code - I was surprised that it didn't.

[ianlancetaylor]

One of the common requests for the design draft is support for methods that have their own generic type parameters. We don't currently know how to implement that (https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#no-parameterized-methods). But if ever do figure out how to implement it, there is going to be some sort of relationship to parameterized interface types. I at least don't fully understand how this should all work together, so I'm wary of adding type inference into the mix.

[rogpeppe]

But if ever do figure out how to implement it, there is going to be some sort of relationship to parameterized interface types.

I'm sure there will be, but won't there also be some sort of relationship to concrete types too, and also to non-parameterized interface types? AFAICS adding methods with their own type parameters will largely be orthogonal to type inference in general, because the method type parameters are free and thus unrelated to the outer level type parameters.

As I see it, type inference on interfaces is not that far off from type inference on constants, which has good treatment in the proposal.

[rogpeppe]

Here's a little motivational example: https://go2goplay.golang.org/p/4wLqRDSTNZS

Function types and single-method interfaces are generally quite similar, so it's surprising,
I believe, that type inference works when passing a function value, but not when passing
an interface implementation.

It's very common in Go to pass a concrete implementation and have it implicitly
converted to an interface type. I'm pretty sure that type inference should work here.

package main

import (
	"fmt"
)

func main() {
	i := intGetter(99)
	// This works fine.
	fmt.Println(getf(i.get))
	// This also works fine.
	fmt.Println(geti(getter[int](i)))
	// ... but not when the argument is a concrete
	// type that implements the required interface.
	// An explicit [int] type parameter is needed.
	fmt.Println(geti(i))
}

type getter[T any] interface {
	get() T
}

type getterFunc[T any] func() T

func getf[T any](f getterFunc[T]) T {
	return f()
}

func geti[T any](f getter[T]) T {
	return f.get()
}

type intGetter int

func (i intGetter) get() int {
	return int(i)
}

[ianlancetaylor]

I think that what we are talking about here is extending the type inference rules so that if the function parameter's type T is a parameterized interface type I, then given type argument A we infer the arguments to I based on the methods of A. We would presumably do this by walking through the methods of I, finding the identically named methods of A, and trying to unify the types of the two methods. I agree that the results are likely to be unsurprising if A is a fully concrete type. I am much less certain about the case where A is a parameterized type, in particular where we are compiling a parameterized function for which A's methods are defined by a constraint.

Maximizing potential type inference is definitely not a goal. The primary guideline is that type inference must never be surprising. A secondary guideline is that it must come up often enough to be useful. I have no idea whether people will write many parameterized interface types (other than for use as constraints). I don't quite see the point of a parameterized interface type. Of course it must work, but will they be used frequently enough that it's worth writing type inference rules for them?

[rogpeppe]

I am much less certain about the case where A is a parameterized type, in particular where we are compiling a parameterized function for which A's methods are defined by a constraint

The rules would obviously need to be thought about, and codified but my intuition is that the method set of any type is known (even if generically typed) and once we've established the set of common methods, unifying should be very similar to unifying func types in the existing proposal.

I have no idea whether people will write many parameterized interface types (other than for use as constraints). I don't quite see the point of a parameterized interface type. Of course it must work, but will they be used frequently enough that it's worth writing type inference rules for them?

I have only one data point: my own experience; but I've played around with a couple of not-entirely-trivial pieces of generic Go code (I ported a concurrent ordered map implementation and I made the stdlib io library generic).

In both cases, generic interfaces were a key part of the design, and I'm pretty sure that they will continue to be as useful in general as I found them there.

This is a Good Thing IMHO. It's showing that Go's existing generic feature, the interface value concept, is entirely orthogonal to, and composable with, the proposed new type parameter feature.

One nice property of generically typed interface types is that values inside them can "hide" their own type parameters, which is something that a struct type cannot, because any generic member of the struct must have its type parameters declared on the containing type. Thus generic interface types are an important part of the backward-compatibility story: they are a way of adding potentially generic functionality without changing existing type parameters (any change to type parameters being a backwardly incompatible change)

And that's quite apart from the more direct applications such as for iterators (the io package being an example of a batched iterator package - it could be made generic without much difficulty. Why shouldn't we be able to use io.Pipe to pipe batches of floating point numbers, for example?).

[RussellLuo]

As another use case, I try to update my little validation library by leveraging Go generics. While the implementation code is largely simplified (e.g. Eq), the user has to add type arguments now (obviously tedious):

- err := v.Validate(v.Value(value, v.Eq(2)))
+ err := v.Validate(v.Validator[int](v.Value(value, v.Validator[int](v.Eq(2)))))

[rogpeppe]

@griesemer Here's another example. Here we're passing an interface type that actually embeds the expected interface. I think it should be able to infer the type in this case at least.

package main

func main() {
	var x I2[int]
	F(x)
}

type I[T any] interface {
	Get() T
}

type I2[T any] interface {
	I[T]
	Foo()
}

func F[T any](i I[T]) {
}

I get the error:

./prog.go:5:4: type I2[int] of x does not match I[T] (cannot infer T)

[rogpeppe]

One other motivational example that I haven't explicitly mentioned above:
It's common in Go to return a concrete type that implements an interface and adds extra methods to that interface (e.g. strings.Reader, bytes.Buffer, etc). If we want to do the same thing with type-parameterised interface types, there's
more friction because the type parameter must be passed explicitly.

[jordanorelli]

I think this limitation will encourage people to just stick extra identity methods onto their types to get the behavior they want.

Here's an example of what I mean:

package main

import "fmt"

type A struct{}

func (a A) Open() string             { return "open" }
func (a A) AsOpener() Opener[string] { return a }

type B struct{}

func (b B) Open() bool             { return true }
func (b B) AsOpener() Opener[bool] { return b }

type Opener[X any] interface {
	Open() X
}

func Open[X any](o Opener[X]) X {
	x := o.Open()
	fmt.Printf("Opened Value: %v of type %T\n", x, x)
	return x
}

func main() {
	a, b := A{}, B{}

	Open(a.AsOpener())
	Open(b.AsOpener())
}

https://gotipplay.golang.org/p/fIS34g_-N6N

Practically speaking you wind up with the situation that in order to utilize A with Open, you can either type Open[string](a) or Open(a.AsOpener()). You're incentivized to stick an identity method on your implementations of the interface and just use those methods instead. Now you use Open(a.AsOpener()) everywhere, and if you want to alter the definition of A to change the type to which it opens, you don't have to update your call sites as you would if you had written Open[string](a) instead. Change the return type of Open() on A without changing AsOpener()? Compile time error. There you go. Now you can keep it all neatly wrapped up in one place, the compiler gives you all the guarantees it was already giving you, and you don't have to state the type parameter of the generic interface at every callsite. With the current inferred limitations, why wouldn't you do this every time you implement a generic interface?

And if you want to enforce that everyone in your codebase defines every Opener[X] to have this AsOpener method for consistency, you just define the Open interface to require it:

type Opener[X any] interface {
	Open() X
	AsOpener() Opener[X]
}

[neild]

A surprising case which I ran into today, in which the compiler confusingly rejects a parameter after already inferring the type:

package main

type Setter[T any] interface {
	Set(T)
}

type Int32Setter int32

func (v *Int32Setter) Set(x int32) { *v = (Int32Setter)(x) }

func SetAToB[T any](x T, target Setter[T]) { target.Set(x) }
func SetBToA[T any](target Setter[T], x T) { target.Set(x) }

func main() {
	target := new(Int32Setter)
	value := int32(0)

	SetAToB[int32](value, target)         // ok
	SetBToA[int32](target, value)         // ok
	SetAToB(value, Setter[int32](target)) // ok
	SetBToA(Setter[int32](target), value) // ok
	SetAToB(value, target)                // type *Int32Setter of target does not match inferred type Setter[int32] for Setter[T]
	SetBToA(target, value)                // type *Int32Setter of target does not match Setter[T] (cannot infer T)
}

https://go.dev/play/p/QUMBrOsblkP

In the second to last line, the compiler infers that the type parameter T is int32, but then complains that the second function parameter does not match the inferred type. This is technically true, because the inferred type is the interface type Setter[int32] and the parameter is a concrete *Int32Setter, but confusing because the parameter type is assignable to the inferred type.

[ianlancetaylor]

Replying to @neild

Type inference never pays attention to assignabillity.

That said, there is something interesting about that example. We can infer T from the first argument: T must be int32. And at that point we have inferred all the type parameters. So this is different from the earlier examples. Here the problem is that function type inference always tries to unify all the function argument types with the type parameters. I think that is important for reasonable handling of untyped constants. But it's not necessarily important for handling of typed arguments. For typed arguments we could skip cases where the types do not unify. In this example that would tell us that T is int32, and then postpone everything else to the actual function call type checking. In this case that would succeed through the implicit conversion to an interface type.

I don't know whether that is a good idea or not. It depends on how often people want to use interface types with type parameters. I don't know often that will happen. In particular, I would write this code like this, which works today.

package main

type Setter[T any] interface {
	Set(T)
}

type Int32Setter int32

func (v *Int32Setter) Set(x int32) { *v = (Int32Setter)(x) }

func SetAToB[T any, Set Setter[T]](x T, target Set) { target.Set(x) }
func SetBToA[T any, Set Setter[T]](target Set, x T) { target.Set(x) }

func main() {
	target := new(Int32Setter)
	value := int32(0)

	SetAToB[int32](value, target)         // ok
	SetBToA[int32](target, value)         // ok
	SetAToB(value, Setter[int32](target)) // ok
	SetBToA(Setter[int32](target), value) // ok
	SetAToB(value, target)                // ok
	SetBToA(target, value)                // ok
}

[rogpeppe]

It depends on how often people want to use interface types with type parameters. I don't know often that will happen.

As one data point, in the generic code I've written, interface types with type parameters seem to come up about as often as interface types without type parameters in regular code. It's often seems preferable to use an interface value rather than an interface constraint on a type parameter because it's more flexible (such an interface can go inside a struct, for example, and be added later while preserving backward compatibility, something an additional type parameter cannot) and more ergonomic (type parameters tend to pollute all the code they touch, so having several type parameters is a pain because they have to passed through to every data structure and function that operates on them).

In fact, I wouldn't be surprised if interface types with type parameters become more popular than constraints on type parameters because they're more general. For example, a generic interface can define behaviour over arbitrary types that aren't necessarily owned by the package implementing the interface.

For example, rather than defining graph type by mutually recursive constraint types, it's arguably less awkward to define a graph like this:

type Graph[Node, Edge any] interface {
	Edges(n Node) []Edge
	Nodes(e Edge) (from, to Node)
}

func ShortestPath[Node, Edge any](graph Graph[Node, Edge]), from, to Node) []Edge

This allows the user to define a graph over any existing type that has a similar graph-like arrangement and also allows the interface methods to use arbitrary contextual information (stored in the Graph value) to influence behaviour.

[rogpeppe]

As a demonstration of how using generic interfaces can result in cleaner code, here's a concrete example of such a cleanup: ajwerner/btree@b6ce38b. The interface that made the difference is here. In many places, the number of type parameters in use went from 5 to 3, and I suspect that given the GC stenciling approach used by Go generics, the performance characteristics would stay quite similar.

[bmhatfield]

I wanted to offer that I've hit this in practice refactoring existing interface-heavy code to be generalized. In particular, this code has 4 very similar interfaces except that they each handle some different concrete type. This is a great use-case for generics!

I have a function like:

func handler.NewHandler[T any](r reducer.Reducers[T], vec handler.Vector[T], f filter.Filters[T]) handler.Handler[T]

handler.Vector[T] is an interface:

type Vector[T any] interface {
	Length() int
	Get(int) (*T, bool)
}

if I call the function:

handler.NewHandler(itn.Reducers(), vec, itn.Filters())

According to gopls, the first and last arguments infer properly, but vec does not, even though the argument is correct.

If I modify the call to:

handler.NewHandler[ConcreteType](itn.Reducers(), vec, itn.Filters())

The code compiles as expected.

It took me a long time staring at the error to understand what had occurred, as it felt very unexpected that the inference of this function was only partially supported.

[lawrencejones]

If I'm identifying the right issue, I think I've been hitting against the lack of inference for generic interfaces recently.

In hope that it's a useful example, we've been modelling modal forms in our app as the following:

type Modal[Props, State any] interface {
  DefaultState() *State
  BuildProps(context.Context, *State) (Props, error)
  Render(Props, *State) *slack.ModalViewRequest
}

With a lot omitted, but the basic principle being that you can implement a modal as a struct that operates on Props (built-at-runtime properties) and State (provided from the current state of the form) types.

One function that is very hard to write is an initial Render.

If we want to render the modal for the first time from the rest of the app, we'd like to build a generic Render function that can make this easy and type-safe.

Ideally:

func Render[Props, State any](modal Modal[Props, State], props Props) (*slack.ModalViewRequest, error) {
	return modal.Render(props, modal.DefaultState()).Build(modal)
}

So we can call it like so:

// We provide an IncidentPostCreate type, which implements DefaultState returning an
// IncidentPostCreateState pointer, which means we should be able to infer State.
Render(IncidentPostCreate{IncidentID: inc.ID}, IncidentPostCreateProps{
	Organisation: identity.Organisation,
	Incident:     inc,
})

But because Go doesn't look at the first modal parameter type and understand that DefaultState() returns *State, and infer the State type from being provided with a modal, we're forced to explicitly type the call:

// Required to provide Props and State
Render[IncidentPostCreateProps, IncidentPostCreateState](IncidentPostCreate{IncidentID: inc.ID}, IncidentPostCreateProps{
	Organisation: identity.Organisation,
	Incident:     inc,
})

It's not the end of the world, but it is pretty ugly. We can do something convoluted so we only need provide a State type parameter, rather than both:

func RenderView[State, Props any, ModalType Modal[Props, State]](modal ModalType, props Props) (*slack.ModalViewRequest, error) {
	return modal.Render(props, modal.DefaultState()).Build(modal)
}

// This works, as we can infer Props from the function argument, and explicitly typing
// the parameters of the Modal interface means we can identify they relate.
//
// But we still need to provide State, even though ModalType must implement a DefaultState
// that could help us infer it.
Render[IncidentPostCreateState](IncidentPostCreate{IncidentID: inc.ID}, IncidentPostCreateProps{
	Organisation: identity.Organisation,
	Incident:     inc,
})

Of course, the compiler will shout if we ever provided types that didn't match along these boundaries, so it felt intuitive that it could also make inferences.

This given with an understanding that full inference is a non-goal, but figured it would be worth an additional case study.

[griesemer]

This also needs a concrete proposal outlining what's in scope.

[griesemer]

Directly related to #40055 with a similar solution.

[gopherbot]

Change https://go.dev/cl/497015 mentions this issue: go/types, types2: consider shared methods when unifying against interfaces

[griesemer]

Submitted accidentally, revert in progress. Reopening.

[gopherbot]

Change https://go.dev/cl/497656 mentions this issue: go/types, types2: consider shared methods when unifying against interfaces

[gopherbot]

Change https://go.dev/cl/497657 mentions this issue: go/types, types2: enable interface inference

[gopherbot]

Change https://go.dev/cl/499282 mentions this issue: doc/go1.21: document type inference changes