Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: type inference failing for nested type parameters #39661

Closed
DeedleFake opened this issue Jun 17, 2020 · 12 comments
Closed

cmd/compile: type inference failing for nested type parameters #39661

DeedleFake opened this issue Jun 17, 2020 · 12 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. TypeInference Issue is related to generic type inference
Milestone

Comments

@DeedleFake
Copy link

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
Copy link
Author

@gopherbot, assign @griesemer.

@griesemer griesemer self-assigned this Jun 17, 2020
@griesemer griesemer added this to the Unreleased milestone Jun 17, 2020
@griesemer griesemer added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jun 17, 2020
@ianlancetaylor
Copy link
Contributor

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
Copy link
Contributor

gertcuykens commented Jun 17, 2020

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
Copy link
Author

@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
Copy link
Contributor

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
Copy link
Contributor

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

@gertcuykens
Copy link
Contributor

gertcuykens commented Jun 18, 2020

@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
Copy link
Contributor

bcmills commented Jun 23, 2020

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
Copy link

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.

@griesemer griesemer added the TypeInference Issue is related to generic type inference label Mar 7, 2023
@griesemer griesemer changed the title cmd/go2go: type inference failing for nested type parameters cmd/compile: type inference failing for nested type parameters Mar 8, 2023
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Mar 8, 2023
@griesemer
Copy link
Contributor

The original example in this issue, updated to new syntax:

package main

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

type Impl struct {
	v string
}

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

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

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

works now on the 1.21 dev branch (playground). It was (most likely) addressed with CL 472298.

It is different from @rogpeppe 's example (updated and slightly simplified). That example is essentially covered with issue #41176 so I am going to close this specific issue as fixed.

@griesemer
Copy link
Contributor

@mcgraw-bb25 Your long example also seems to work fine when adjusted to new syntax (playground link). Again, this requires 1.21 dev branch. It doesn't work with 1.20.

@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue May 31, 2023
For #39661.
For #41176.
For #51593.
For #52397.
For #57192.
For #58645.
For #58650.
For #58671.
For #59338.
For #59750.
For #60353.

Change-Id: Ib731c9f2879beb541f44cb10e40c36a8677d3ad4
Reviewed-on: https://go-review.googlesource.com/c/go/+/499282
TryBot-Bypass: Robert Griesemer <gri@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. TypeInference Issue is related to generic type inference
Projects
None yet
Development

No branches or pull requests

8 participants