Skip to content

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

Closed

Description

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

Activity

  1. DeedleFake commented on Jun 17, 2020

    @DeedleFake
    Author
  2. self-assigned this
    on Jun 17, 2020
  3. added this to the Unreleased milestone on Jun 17, 2020
  4. added
    NeedsInvestigationSomeone must examine and confirm this is a valid issue and not a duplicate of an existing one.
    on Jun 17, 2020
  5. ianlancetaylor commented on Jun 17, 2020

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

  6. gertcuykens commented on Jun 17, 2020

    @gertcuykens
    Contributor

    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.

  7. DeedleFake commented on Jun 17, 2020

    @DeedleFake
    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)
    }
  8. griesemer commented on Jun 18, 2020

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

  9. rogpeppe commented on Jun 18, 2020

    @rogpeppe
    Contributor

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

  10. gertcuykens commented on Jun 18, 2020

    @gertcuykens
    Contributor

    @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{}))
    }
  11. bcmills commented on Jun 23, 2020

    @bcmills
    Contributor

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

  12. mcgraw-bb25 commented on Jul 2, 2020

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

  13. changed the title [-]cmd/go2go: type inference failing for nested type parameters[/-] [+]cmd/compile: type inference failing for nested type parameters[/+] on Mar 8, 2023
  14. griesemer commented on Mar 8, 2023

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

  15. griesemer commented on Mar 8, 2023

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

  16. gopherbot commented on May 31, 2023

    @gopherbot
    Contributor

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

  17. locked and limited conversation to collaborators on May 30, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    FrozenDueToAgeNeedsInvestigationSomeone must examine and confirm this is a valid issue and not a duplicate of an existing one.TypeInferenceIssue is related to generic type inferencecompiler/runtimeIssues related to the Go compiler and/or runtime.

    Type

    No type

    Projects

    No projects

      Milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions