cmd/compile: type inference failing for nested type parameters

[DeedleFake]

Filing a bug as per #15292 (comment).

If a function is called that takes an argument of a generic type that in turn has its own type parameter, the inference of the subtype fails. For example,

Playground

package main

type Getter(type T) interface {
	Get() T
}

type Impl struct {
	v string
}

func (i Impl) Get() string {
	return i.v
}

func Bug(type G Getter(T), T interface{})(g G) {
}

func main() {
	i := Impl{v: "example"}
	Bug(i)
}

Output:

type checking failed for main
prog.go2:20:7: cannot infer T (prog.go2:15:28)

This code works if the call to Bug is changed to Bug(Impl, string).

[DeedleFake]

@gopherbot, assign @griesemer.

[ianlancetaylor]

I don't think the algorithm in the design draft explains how to handle this case. If we fix this, we should update the description of the algorithm.

[gertcuykens]

This code works if the call to Bug is changed to Bug(Impl, string).

go tool go2go run hello.go2
type checking failed for main
hello.go2:20:2: Bug(Impl, string) (value of type func(g Impl)) is not used

@DeedleFake Doesn't work for me? Can you paste the working example please.

[DeedleFake]

@gertcuykens:

Playground

package main

type Getter(type T) interface {
	Get() T
}

type Impl struct {
	v string
}

func (i Impl) Get() string {
	return i.v
}

func Bug(type G Getter(T), T interface{})(g G) G {
	return g
}

func main() {
	i := Impl{v: "example"}
	Bug(Impl, string)(i)
}

[griesemer]

I concur with @ianlancetaylor: I believe the current inference algorithm is not designed to handle this case. Though it seems that perhaps it could (should?). Keeping open for future investigation.

[rogpeppe]

Here's a slightly simpler example. I think this should be made to work: https://go2goplay.golang.org/p/3-aVhD6Y9R2

[gertcuykens]

@rogpeppe Took the liberty to include the current solution for your problem https://go2goplay.golang.org/p/44c92Nqchqx For me its very important work arounds are always included because people like me who aren't that smart spend hours sometimes understanding why it doesn't work. Including a work around helps allot understanding the problem.

package main

import (
	"fmt"
)

type F(type T) interface {
	X() T
}

func callx(type T)(f F(T)) T {
	return f.X()
}

type foo struct{}

func (foo) X() int {
	return 99
}

func main() {
	// fmt.Println(callx(foo{})) // this should be made to work also
	fmt.Println(callx(int)(foo{}))
}

[bcmills]

This crops up in a number of other places too, such as append and analogous libraries for transforming and/or aggregating slices and maps.

[mcgraw-bb25]

I apologize if my comment is unrelated, but based on the example and the error code I wanted to see whether it was related, or if I'm doing something wrong with my code. I couldn't find an explicit reason in the design doc that would prohibit this case from working.

Go Version: https://go2goplay.golang.org/

Reproduce via: https://go2goplay.golang.org/p/UDaKcuC6pVd

Goal: I am trying to write a generic version of a quicksort algorithm that uses generic constraints. The example given is the design doc introduces a typed interface called Ordered which is useful for built in types, but is inaccessible for user defined structs. Therefore I have introduced a QuickSortable interface which exposes an Ordered value.

// Ordered is a type constraint that matches all ordered types.
// (An ordered type is one that supports the < <= >= > operators.)
// In practice this type constraint would likely be defined in
// a standard library package.
// Taken from the proposal
type Ordered interface {
    type int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr, float32, float64, string
}

/* package quicksort */

// QuickSortable is the generic interface required to use the QuickSort
// function.  This interface allows arbitrary user defined types
// to take advantage of the generic sorting algorithm.
type QuickSortable(type T Ordered) interface {
    Orderable() T
}

I have three function signatures that relate the types in the following way:

// partition runs a single sorting iteration.  Given a slice to sort,
// partition begins at the low index, and while iterating to the high index
// swapping out of place elements on the way.
func partition(type O Ordered, Q QuickSortable(O))(q []Q, lowIdx int, highIdx int) (int, error) {...}

// quickSort is the recursive component of the quicksort implementation.
// It delegates down to partition to run a single iteration
// and exhausts itself when the low index is greater than the high index.
func quickSort(type O Ordered, Q QuickSortable(O))(q []Q, lowIdx int, highIdx int) error {...}

// QuickSort is the generic outer shell, which delegates to the
// private quickSort function, that is exported as the public API.
// type O Ordered is used so that the operator <= is legal.
// type Q is used to produce an instance of type O via the call to Orderable(),
// which allows any user defined type to take advantage of QuickSort.
// The type signature is propagated down to the internal functions.
func QuickSort(type O Ordered, Q QuickSortable(O))(q []Q) error {...}

The user struct implements the QuickSortable interface in the following ways:

// QSInt is a type alias of int, which allows a slice of QSInt
// to utilize quicksort.
type QSInt int

// Orderable implements the QuickSortable interface so that QSInt
// can be used in the QuickSort function.
func (q QSInt) Orderable() int {
    return int(q)
}

// Guest is a domain object of some application that needs sorting
type Guest struct {
    name string
    age  int
}

// Orderable implements the QuickSortable interface so that Guest
// can be used in the quicksort function.
func (g Guest) Orderable() int {
    return int(g.age)
}

Later I try to invoke the QuickSort function in the following ways:

var sortList []QuickSortable(int)
// other code
err := QuickSort(int, QuickSortable(int))(sortList)

var guestList []QuickSortable(int)
// other code
err = QuickSort(int, QuickSortable(int))(guestList)

Output: The type checking fails because O (Orderable) cannot be inferred.

type checking failed for main
prog.go2:63:52: cannot infer O (prog.go2:40:21)
prog.go2:68:38: cannot infer O (prog.go2:61:21)
prog.go2:69:39: cannot infer O (prog.go2:61:21)
prog.go2:81:33: cannot infer O (prog.go2:61:21)

I have made a few attempts to get this working, and the only method that would run the code as expected required dropping the type O Orderable, and instead injecting int directly into the QuickSortable type parameter: https://go2goplay.golang.org/p/KElHD5oZWgf

func partition(type Q QuickSortable(int))(q []Q, lowIdx int, highIdx int) (int, error) {}
func quickSort(type Q QuickSortable(int))(q []Q, lowIdx int, highIdx int) error {}
func QuickSort(type Q QuickSortable(int))(q []Q) error {}
// ...
var guestList []QuickSortable(int)
// ...
err = QuickSort(QuickSortable(int))(guestList)

Can you please confirm is this is an actual issue or I'm misinterpreting the design doc and this shouldn't be possible?

Thank you very much.