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: invalidly inferred type for interface that doesn't use type parameter #60377

Closed
griesemer opened this issue May 23, 2023 · 26 comments
Assignees
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@griesemer
Copy link
Contributor

In the following code:

type T[P any] interface {
	m()
}

func g[P any](T[P]) {}

func _() {
	var x T[int]
	g(x)         // here we infer P == int, but in fact any type of P would be ok
	g[string](x) // here we set P == string
}

we infer the type int for P of g. But in fact any type would make this code work. Type inference should not succeed in this case.

@griesemer griesemer added the NeedsFix The path to resolution is known, but the work has not been done. label May 23, 2023
@griesemer griesemer added this to the Go1.21 milestone May 23, 2023
@griesemer griesemer self-assigned this May 23, 2023
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label May 23, 2023
@griesemer griesemer changed the title cmd/compile: cmd/compile: invalidly inferred type for interface that doesn't use type parameter May 23, 2023
@jimmyfrasche
Copy link
Member

I'm not sure I follow.

In my mind

  • unifying P = int is correct because that's what x is
  • g[string](x) should be an error because string ≠ int

That P is not currently used by T does not seem relevant. Say you allow g[string] but then in a later version T is updated to

type T[P any] interface {
	m() P
}

now g[string] is an error and the correct inference would be int but the only thing that changed was an implementation detail

@griesemer
Copy link
Contributor Author

Consider this case:

type T1[P any] interface {
	m()
}

type T2[P any] interface {
	m()
}

func g[P any](T1[P]) {}

func _() {
	var x T2[int]
	g(x)         // here we infer P == int, but in fact any type of P would be ok
	g[string](x) // here we set P == string
}

Now we get an error for g(x) but g[string](x) is ok. That seems inconsistent. We should not be able to infer a type for P in the first case.

@jimmyfrasche
Copy link
Member

I see what you are saying. The interfaces-as-constraints are identical to each other and interface { m() } so P does not matter for the constraint.

However, it seems like the parameterization of the interface-as-type should still be part of its identity.

@atdiar
Copy link

atdiar commented May 23, 2023

@jimmyfrasche that's why it's inference which would fail.

But not instantiation.

@jimmyfrasche
Copy link
Member

I expect it to behave like this, since the interface(s) aren't used as constraints and are just ordinary types:

type T[P any] struct{}

func g[P any](T[P]) {}

func _() {
	var x T[int]
	g(x)         // here we infer P == int
	g[string](x) // here we fail to set P == string as P = int
}

https://go.dev/play/p/0Wj38UCOijw

@griesemer
Copy link
Contributor Author

@jimmyfrasche But the rules for interface assignment are quite different from non-interface assignment. But here is a counter-example:

type T[P any] interface{ m() }

func g[P any](func(T[P])) {}

func _() {
	var f func(T[int])
	g(f)
	g[int](f)
	g[string](f) // ERROR cannot use f (variable of type func(T[int])) as func(T[string]) value in argument to g[string]
}

Because the interface is a component type, now it must match exactly.

@griesemer griesemer modified the milestones: Go1.21, Go1.22 May 23, 2023
@griesemer griesemer added the NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. label May 23, 2023
@gopherbot gopherbot removed the NeedsFix The path to resolution is known, but the work has not been done. label May 23, 2023
@jimmyfrasche
Copy link
Member

Ah, I was so fixated on the type inference I wasn't thinking about assignability. g[string](x) makes total sense.

I still do not see why that implies that int should not be inferred, though. Even if other choices are valid, it seems reasonable to go with what's provided.

@griesemer
Copy link
Contributor Author

I believe type inference should only infer a type if it is the only one possible, if a valid type argument exists in the first place (ignoring the fact that in many cases any is also a valid type argument).

This may mean that in some cases (like this one) we cannot infer a type argument. That's ok.

@jimmyfrasche
Copy link
Member

I agree that type inference should not invent a type but I disagree that it should discard the provided type. I don't think this would matter much given how niche the edge case is, though.

Would g(T[int](x)) also fail? This case is identical but it feels more wrong written like this.

@griesemer
Copy link
Contributor Author

griesemer commented May 24, 2023

g(T[int](x)) is the same as g(x) if x is of type T[int]. So g(T[string](nil)) currently works but would fail if we consider this issue a bug. Consider g[int](T[string](nil)) which works either way.

In other words, currently we have an exception for defined generic interface types: if a defined generic interface type T which is instantiated with a concrete type X (assuming there's one type parameter) is then matched against the same interface type "instantiated" with a type parameter, we infer the type X for the type parameter, even if the type parameter is never used by the methods: T[X] unified against T[P] leads to the inference of X for P.

If we consider this issue a bug, then a) we don't need an exception anymore, but b) in this example we wouldn't be able to infer X anymore.

I think this is a pretty esoteric case and doesn't really justify the exception.

See also #8082 which applies when the interface types are components of other types.

@griesemer
Copy link
Contributor Author

cc: @mdempsky @findleyr for input, especially considering also #8082.

@atdiar
Copy link

atdiar commented May 24, 2023

@jimmyfrasche the way I see it, inference is the reverse of instantiation.
Similarly to solving an equation, we start from the result and try to find the unknown (the type argument).

We know that a type parameter can only have one instantiation at a time. So the solution is unique.

Each constructed type is unique and new: T[int] and T[string] are different but compatible in assignment to each other.

That last part tripped me a little bit though, I admit 😅. This is the type identity/equality of interfaces that @griesemer linked and which impacts composite type definitions.

But non generic go code still considers that two type definitions are different although possibly compatible.

@griesemer
Copy link
Contributor Author

We know that a type parameter can only have one instantiation at a time. So the solution is unique.

A type parameter can have only one instantiation at a time but that doesn't mean the solution to inference is unique: in the original example in this issue type inference infers int but in fact any type would solve the equation. So the solution is not unique at all.

@atdiar
Copy link

atdiar commented May 24, 2023

Exactly, that's why inference fails.

It's a case similar to f(x) = c where c is constant.

Given c, we are still trying to find the one value of x that we passed to f.

That's what was meant by unique, I don't disagree at all.

@findleyr
Copy link
Contributor

I think the framing provided by @griesemer and @atdiar is useful: if the solution is not unique, inference should fail. Otherwise, we run the risk of inferring a different type in the future (and that's exactly why we need the special case currently).

I'll note that there are other cases where there is one unique solution, and inference fails because of the current implementation:

type S[P any] interface{}

func F[P any](S[P], P) {}

func _() {
	var s S[int]
	F(s, "")
}

@griesemer griesemer added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. labels May 25, 2023
@griesemer griesemer modified the milestones: Go1.22, Go1.21 May 25, 2023
@griesemer
Copy link
Contributor Author

griesemer commented May 25, 2023

@findleyr 's example is very convincing. Fix forthcoming.

Clarification: It is better to not be able to infer a (possible) type argument when we could than to infer an incorrect type argument (which is the case in this example). The former is a shortcoming of the inference mechanism, while the latter is a bug.

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/498315 mentions this issue: go/types, types2: don't infer type argument for unused parameter in interfaces

@findleyr
Copy link
Contributor

Here's an example where inference will continue to succeed, but infer a different type:

type S[P any] interface{}

func F[P any](S[P], P) P { var x P; return x }

func main() {
	var s S[float64]
	y := F(s, 1)
	_ = y
}

IMO this is an example of the current algorithm inferring the "wrong" type. The type of y is inferred to be float64, but should be int (and will be after this issue is fixed).

@atdiar
Copy link

atdiar commented May 25, 2023

@findleyr can inference work with untyped const values here?
After the change, I might try to assign y to a float64 variable for instance (somewhere else in the code after the call to F)

Perhaps it should fail here too because there are several solutions, 1 could be int or float32 or float64 etc...?

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

Edit: ha I think I see what you meant:

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

That's indeed something that should be dealt with by the fix.

@griesemer
Copy link
Contributor Author

@atdiar Your 2nd example will work with the fix.

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/498895 mentions this issue: go/types, types2: use exact unification for component types

gopherbot pushed a commit that referenced this issue May 30, 2023
This change defines two unification modes used to control unification:

- assign  set when unifying types involved in an assignment
- exact   if set, types unify if they can be made identical

Currently, unification is inexact: when a defined type is compared
against a type literal, the underlying type of the defined type is
considered. When channel types are compared, the channel direction
is ignored. And when defined types are compared where one (or both)
are interfaces, interface unification is used.

By contrast, exact unification requires types to match exactly:
if they can be unified, the types must be identical (with suitable
type arguments).

Exact unification is required when comparing component types.
For instance, when unifying func(x P) with func(x Q), the two
signatures unify only if P is identical to Q per Go's assignment
rules.

Until now we have ignored exact unification and made due with inexact
unification everywhere, even for component types. In some cases this
led to infinite recursions in the unifier, which we guarded against
with a depth limit (and unification failure).

Go's assignmemt rules allow inexact matching at the top-level but
require exact matching for element types.

This change passes 'assign' to the unifier when unifying parameter
against argument types because those follow assignment rules.
When comparing constraints, inexact unification is used as before.

In 'assign' mode, when comparing element types, the unifyier is
called recursively, this time with the 'exact' mode set, causing
element types to be compared exactly. If unification succeeds for
element types, they are identical (with suitable type arguments).

This change fixes #60460. It also fixes a bug in the test for
issue #60377. We also don't need to rely anymore on the recursion
depth limit (a temporary fix) for #59740. Finally, because we use
exact unification when comparing element types which are channels,
errors caused by assignment failures (due to inexact inference which
succeeded when it shouldn't have) now produce the correct inference
error.

Fixes #60460.
For #60377.
For #59740.

Change-Id: Icb6a9b4dbd34294f99328a06d52135cb499cab85
Reviewed-on: https://go-review.googlesource.com/c/go/+/498895
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
Run-TryBot: Robert Griesemer <gri@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
@hajimehoshi
Copy link
Member

hajimehoshi commented Aug 18, 2023

This should be too late, and I am sorry if this was already discussed, but wouldn't it be possible to forbide unused type parameters by the Go compiler? In other words, couldn't Go compiler forbid the following code?

type T[P any] interface {
	m()
}

I realized that unused type parameters tend to cause counterintuitive implicit conversions (https://go.dev/play/p/VLb031yF1z6, inspired by #61903). Also, unused parameters are unused then these should be useless. (If we really want to have a unused type parameter, we can add a member like [0]T somewhere).

What do you think?

@atdiar
Copy link

atdiar commented Aug 18, 2023

@hajimehoshi then someone will want this (probably with some good reason), asking: "Where are my phantom types?"

:o)

(phantom type is the usual name of this feature)

Edit: now that I think of it, since you only want to disable it for interface types, I think it will depend on how the question of interface identity is solved.

@hajimehoshi
Copy link
Member

hajimehoshi commented Aug 18, 2023

OK so my question is when phantom types are useful.

EDIT: https://doc.rust-lang.org/rust-by-example/generics/phantom.html

I see, so if they need to use phantom types, I was wondering if it would be possible to 'convince' the Go compiler by adding a member like [0]T somewhere.

@atdiar
Copy link

atdiar commented Aug 18, 2023

@hajimehoshi in general to express units.

type Distance[Unit any] float64
type Miles struct{}
type Meters struct{} 

type DistanceMiles = Distance[Miles] 
type DistanceMeters = Distance[Meters] 

I'd think.

But your question is more interesting and I responded a bit too fast, since you are especially targeting the case of interface types.

I'm curious as well to see what people think.

@hajimehoshi
Copy link
Member

hajimehoshi commented Aug 18, 2023

Edit: now that I think of it, since you only want to disable it for interface types, I think it will depend on how the question of interface identity is solved.

Good point. Probably what I want to solve is counterintuitve assignment to an interface type. For non-interface types, such a counterintuitive assignment should not happen as far as I understand. So, forbidding an unused parameter for an interface type might be enough, beside consistency.

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. NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

No branches or pull requests

6 participants