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

spec: constraint type inference should proceed even if an individual unification step fails #53650

Closed
RelicOfTesla opened this issue Jul 1, 2022 · 8 comments
Assignees
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. Documentation FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. TypeInference Issue is related to generic type inference
Milestone

Comments

@RelicOfTesla
Copy link

RelicOfTesla commented Jul 1, 2022

Edit: See #53650 (comment) for a summary of the problem.

What version of Go are you using (go version)?

$ go version
go version go1.18.3 windows/amd64

What did you do?

type BaseT interface {
	Type1 | Type2
}
type BaseType int
type Type1 BaseType
type Type2 BaseType // float64

type ValueT[T BaseT] struct {
	A1 T
}

func NewType1() *ValueT[Type1] {
	r := NewT[Type1]()
	return r
}
func NewType2() *ValueT[Type2] {
	r := NewT[Type2]()
	return r
}

func NewT[TBase BaseT, TVal ValueT[TBase]]() *TVal {
	ret := TVal{}
	return &ret
}
func TestGoType(t *testing.T) {
	r1 := NewType1()
	r2 := NewType2()
	t.Log(r1, r2)
	t.Log(reflect.TypeOf(r1), reflect.TypeOf(r2))
	fooT1(r1.A1)
	fooT2(r2.A1)
}

func fooT1(t1 Type1) {

}
func fooT2(t2 Type2) {

}

What did you expect to see?

Compile success

What did you see instead?

error:

TBase does not match int
TBase does not match int
@ianlancetaylor ianlancetaylor changed the title Type Parameters Inference dose not support same base type cmd/compile: unexpected error from constraint type inference Jul 1, 2022
@ianlancetaylor
Copy link
Contributor

CC @griesemer

Standalone reproducer:

package p

type BaseT interface {
	Type1 | Type2
}
type BaseType int
type Type1 BaseType
type Type2 BaseType

type ValueT[T BaseT] struct {
	A1 T
}

func NewType1() *ValueT[Type1] {
	r := NewT[Type1]()
	return r
}

func NewT[TInt BaseT, TVal ValueT[TInt]]() *TVal {
	ret := TVal{}
	return &ret
}
foo.go:15:18: TInt does not match int

@ianlancetaylor ianlancetaylor added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jul 1, 2022
@ianlancetaylor ianlancetaylor added this to the Go1.20 milestone Jul 1, 2022
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
@hopehook
Copy link
Member

hopehook commented Oct 3, 2022

I'm not good at generics, maybe there is a flaw here. And I find the compiler will be happy with these cases:

Case one based on @RelicOfTesla's code:

type BaseT interface {
	Type1 | Type2
}
type BaseType int
type Type1 BaseType
type Type2 BaseType // float64

type ValueT[T BaseT] struct {
	A1 T
}

func NewType1() *ValueT[Type1] {
	r := NewT[Type1, ValueT[Type1]]()
	return r
}
func NewType2() *ValueT[Type2] {
	r := NewT[Type2, ValueT[Type2]]()  // add `, ValueT[Type2]`
	return r
}

func NewT[TBase BaseT, TVal ValueT[TBase]]() *TVal {
	ret := TVal{}
	return &ret
}
func TestGoType(t *testing.T) {
	r1 := NewType1()
	r2 := NewType2()
	t.Log(r1, r2)
	t.Log(reflect.TypeOf(r1), reflect.TypeOf(r2))
	fooT1(r1.A1)
	fooT2(r2.A1)
}

func fooT1(t1 Type1) {

}
func fooT2(t2 Type2) {

}

Case two based on @ianlancetaylor's code:

package p

type BaseT interface {
	Type1 | Type2
}
type BaseType int
type Type1 BaseType
type Type2 BaseType

type ValueT[T BaseT] struct {
	A1 T
}

func NewType1() *ValueT[Type1] {
	r := NewT[Type1, ValueT[Type1]]()  // add `, ValueT[Type1]`
	return r
}

func NewT[TInt BaseT, TVal ValueT[TInt]]() *TVal {
	ret := TVal{}
	return &ret
}

Case three is modified by me:

package p

type BaseT interface {
	Type1 | Type2
}

type Type1 int
type Type2 int

var _ = NewT[Type1, Type1]()  // add `Type1` or `Type2`

func NewT[TInt, TVal BaseT]() TVal {
	return TVal(0)
}

From the results, it seems that we do not support indirect type deduction TVal now.

@griesemer
Copy link
Contributor

griesemer commented Nov 30, 2022

Smaller reproducer:

type T1 int
type T2 int // code works if this is changed to, say int8

type G[_ T1 | T2] struct{}

func _() {
	f[T1]()
	f[T2]()
}

func f[P T1 | T2, Q G[P]]() {}

This works:

type T1 struct{}
type T2 struct{}

type G[_ T1 | T2] struct{}

func _() {
	_ = f[T1]
}

func f[P T1 | T2, Q G[P]]() {}

@griesemer
Copy link
Contributor

Even smaller reproducer:

type T1 int
type T2 int

func f[P T1 | T2, _ []P]() {}

var _ = f[T1]

This is a bug with constraint type inference: P is assigned the type T1. Constraint type inference kicks in to determine the type of the 2nd type argument (it doesn't matter what it is). In order to proceed, constraint type inference attempts to unify the type argument T1 for P with the (adjusted) core type of P's constraint T1 | T2. That core type is int. But int and T1 cannot be unified (they are different, named types) and we get an (incorrect) error.

If T1 and T2 are defined as (for instance) struct{}, the core type is struct{} and T1 can be unified with struct{}.

If T1 and T2 have different underlying types, no core type exists, and no unification is attempted with the first type parameter and its constraint. Inference proceeds with the 2nd type parameter and the result is []T1 in that case.

So constraint type inference is a bit too aggressive here. This area is notoriously tricky. May not be safe to address at this point in the release cycle (TBD). Thinking.

For the release team: It's safe to kick this down to Go 1.21 if we don't find a safe fix in time. This is not a regression; the bug existed since 1.18. Also, providing all type arguments manually is a safe work-around.

FYI @findleyr

@griesemer griesemer added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Dec 1, 2022
@griesemer griesemer changed the title cmd/compile: unexpected error from constraint type inference cmd/compile: constraint type inference fails when it should succeed Dec 1, 2022
@gopherbot
Copy link

Change https://go.dev/cl/454655 mentions this issue: go/types, types2: do not abort constraint type inference eagerly

@griesemer
Copy link
Contributor

Per discussion with @findleyr, we believe https://go.dev/cl/454655 is almost certainly correct, but there's no rush to fix this for 1.20. Still thinking about possible ramifications.

@griesemer
Copy link
Contributor

In the section on constraint type inference, the spec states:

  1. For all type parameters with an adjusted core type, unify the type parameter with that type. If any unification fails, constraint type inference fails.

which is exactly what the implementation is doing. The fix (https://go.dev/cl/454655) does something else:

  1. For all type parameters with an adjusted core type, unify the type parameter with that type. Proceed even if the unification fails.

I believe this new approach is the correct approach (and does fix this issue), but it is in fact a (backward-compatible, I think) spec change. In other words, the current behavior is "correct" per the spec.

Making this a spec change and moving it to 1.21.

@griesemer griesemer modified the milestones: Go1.20, Go1.21 Dec 14, 2022
@griesemer griesemer changed the title cmd/compile: constraint type inference fails when it should succeed spec: constraint type inference should proceed even if an individual unification step fails Dec 14, 2022
@griesemer griesemer added TypeInference Issue is related to generic type inference Documentation labels Dec 14, 2022
@gopherbot
Copy link

Change https://go.dev/cl/470916 mentions this issue: go/types, types2: use new type inference algorithm

gopherbot pushed a commit that referenced this issue Mar 1, 2023
The primary change is that type inference now always reports
an error if a unification step fails (rather than ignoring that
case, see infer2.go). This brings the implementation closely to
the description in #58650; but the implementation is more direct
by always maintaining a simple (type parameter => type) mapping.

To make this work, there are two small but subtle changes in the
unifier:

1) When deciding whether to proceed with the underlying type of
   a defined type, we also use the underlying type if the other
   type is a basic type (switch from !hasName(x) to isTypeLit(x)
   in unifier.go). This makes the case in issue #53650 work out.
   See the comment in the code for a detailed explanation of this
   change.

2) When we unify against an unbound type parameter, we always
   proceed with its core type (if any).
   Again, see the comment in the code for a detailed explanation
   of this change.

The remaining changes are comment and test adjustments. Because
the new logic now results in failing type inference where it
succeeded before or vice versa, and then instatiation or parameter
passing failed, a handful of error messages changed.
As desired, we still have the same number of errors for the same
programs.

Also, because type inference now produces different results, we
cannot easily compare against infer1 anymore (also infer1 won't
work correctly anymore due to the changes in the unifier). This
comparison (together with infer1) is now disabled.

Because some errors and their positions have changed, we need a
slightly larger error position tolerance for types2 (which produces
less accurate error positions than go/types). Hence the change in
types2/check_test.go.

Finally, because type inference is now slightly more relaxed,
issue #51139 doesn't produce a type unification failure anymore
for a (previously correctly) inferred type argument.

Fixes #51139.

Change-Id: Id796eea42f1b706a248843ad855d9d429d077bd1
Reviewed-on: https://go-review.googlesource.com/c/go/+/470916
Reviewed-by: Robert Griesemer <gri@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Griesemer <gri@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
@golang golang locked and limited conversation to collaborators Feb 24, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. Documentation FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. TypeInference Issue is related to generic type inference
Projects
None yet
Development

No branches or pull requests

5 participants