cmd/compile: type sets are not correctly deduced for type conversion on type params

[nevkontakte]

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

Go Playground, 1.21

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

N/A, Go Playground

What did you do?

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

What did you expect to see?

Both convert() and convert2() are accepted by the compiler and are semantically equivalent.

What did you see instead?

convert2() is rejected by the compiler: cannot convert x (variable of type srcType constrained by string) to type dstType: cannot convert string (in srcType) to type []elType (in dstType)

Details

The spec says the following about type conversions of type params:

Additionally, if T or x's type V are type parameters, x can also be converted to type T if one of the following conditions applies:

• Both V and T are type parameters and a value of each type in V's type set can be converted to each type in T's type set.

Consider the following code:

type charLike interface{ byte | rune }

func convert2[elType charLike, srcType string, dstType []elType](x srcType) dstType {
	return dstType(x) // ERROR: cannot convert x (variable of type srcType constrained by string) to type dstType: cannot convert string (in srcType) to type []elType (in dstType)
}

Here srcType's type set should be just string, and dstType's type set is []rune|[]byte. As per spec, string can be converted to both []rune and []byte:

A non-constant value x can be converted to type T in any of these cases:

• ...
• x is a string and T is a slice of bytes or runes.

So, conversion should be allowed, assuming the compiler is able to correctly deduce type set for dstType.

The simplest example of the issue I was able to find:

func convert2[elType byte, dstType []elType](x string) dstType {
	return dstType(x) // ERROR: cannot convert x (variable of type string) to type dstType: cannot convert string to type []elType (in dstType)
}

The next step of eliminating elType makes the error disappear:

func convert2[dstType []byte](x string) dstType {
	return dstType(x)}

So it seems the compiler fails to flatten dstType's type set with indirection from elType.

Also, @Merovius was able to construct the following two semantically equivalent examples that hint that the issue is somehow specific to the type conversion operation:

• Rejected: https://go.dev/play/p/WH_JH6Gwim-
• Accepted: https://go.dev/play/p/p2n0fc1QoBj

[Merovius]

The type set of dstType is []elType, not []rune|[]byte (spec):

The type set of a non-interface type term is the set consisting of just that type.

Given that elType is a type parameter, I'm not sure what that implies for whether or not the conversion operation should be allowed. Intuitively, it is clear that for every valid instantiation of convert2, elType will be identical to either rune or byte and thus the "intuitive" type set is that union. But I'm not sure that the spec implies that the actual type set is that.

The original examples I constructed (and hence the point I was trying to make with them) where a bit different from what was given above:

Rejected: https://go.dev/play/p/DDn-SFzglUz
Accepted: https://go.dev/play/p/ling0sjUz8r

Note in particular, that the function-instantiation also requires you to explicitly specify that Dst has to satisfy stringLike (or S in my example). The conversion does seem relevant, as the instantiation still succeeds in cases where the conversion does not. But I find that unsurprising, given that they use different conditions. The conversion condition is given above and is explicitly phrased in terms of the type sets of both type parameters, whereas the the instantiation condition is about type arguments satisfying constraints:

After substitution, each type argument must satisfy the constraint (instantiated, if necessary) of the corresponding type parameter. Otherwise instantiation fails.

Intuitively, they should imply the same thing, but I'm honestly losing track of the precise wordings of the spec, when it comes to type parameters, type arguments and type sets. In particular, it is not entirely clear to me what it means for a type argument of type parameter type (sorry, this is probably exciting to parse) to satisfy a constraint.

The reason I constructed those examples is that to me, they hint that the problem has a similar structure to the restriction of requiring to mention methods in constraints explicitly. Just like

type C interface{ *strings.Reader | *bytes.Reader }
func F[R C](r R) { r.Read(nil) } // r.Read undefined (type R has no field or method Read)

is disallowed, but becomes allowed once we intersect the constraint with io.Reader:

type C interface { *strings.Reader | *bytes.Reader; io.Reader }
func F[R C](r R) { r.Read(nil) } // fine

So too does the example start working, once we intersect the constraint with another interface that should be implied by the union.

[zigo101]

Not a bug by the current spec. A simpler example:

func jon[T byte](x string) []T {
	return []T(x) // error
}

Similarly for assignment:

func pet[A, B []byte](x A, y B){
	x = y // error: cannot use y as type A in assignment
	y = x // error: cannot use x as type B in assignment
}

(Just two small examples from here.)

The rule might be relaxed later, but I don't know if it is worthy it.

[nevkontakte]

The type set of dstType is []elType, not []rune|[]byte (spec):

The type set of a non-interface type term is the set consisting of just that type.

Good point. I think that statement would have been uncontroversial if the set of operations allowed on a composite type did not depend on the types that it is composed of. And this is mostly true, string-slice conversions is the only exception I can think of off the top of my head.

Then I suppose the question is: did the spec intend to leave that difference between type params and concrete types or not?

[findleyr]

CC @griesemer

Yes, this is confusing -- it's too late to change the legality of constraints like []elType, but perhaps we can add a vet check for singleton type sets (I'll have to think about this a bit more).

[atdiar]

The question is probably about what do types that are composites of type parameters satisfy?

[]eltype should satisfy []byte | []rune iff eltype satisfies byte | rune.

Probably similar to the logic used in type inference, the slice type constructor could be seen as bijective on the domain of type sets.

The conversion here is probably special cased here too and simply not implemented in the general constraint checking algorithm.

[griesemer]

@go101 Just FYI: your assignment example is unrelated to this issue:

func pet[A, B []byte](x A, y B){
	x = y // error: cannot use y as type A in assignment
	y = x // error: cannot use x as type B in assignment
}

Type parameters are named types (spec). A named type is always different from any other type (spec). It's never possible to assign a value of one named type (A) to a variable of another named type (B).

[griesemer]

For this issue, it may help to look at really simple examples. In non-generic code, the following is valid:

type E byte
func f0(x []E) string { return string(x) }

The conversion is valid per the spec because "x is an integer or a slice of bytes or runes and T is a string type", and because []E is considered a "slice of bytes", and the implementation (crucially!) looks at the underlying type of E to make that determination. This has always (?) been like this and is arguably not very well specified.

The generic variant

func f1[T []byte](x T) string { return string(x) }

is also accepted because the conversion from T to string is permitted if it is permitted for each type in T, and there's just one: []byte. Similarly

func f2[T []E](x T) string    { return string(x) }

is ok (with E being globally defined as byte) as this is simply a combination of f0 and f1.

The generic variant

func f3[E byte](x []E) string { return string(x) } // ERROR cannot convert x (variable of type []E) to type string

fails for non-obvious reasons - though I believe this is actually just a bug: note that x's type is a slice type, it just so happens that the slice element is a type parameter. The type is clearly a slice, but is it a slice of bytes? The implementation looks at the underlying type of E which happens to be an interface, not a byte, and it fails. If we instead look at the core type, we would find that it exists and that it is byte and then this code would be accepted. (In fact, changing just the right under call to coreType in the implementation will make this work.) As mentioned above, I believe the spec is unclear about what a slice of bytes is and we should clarify that and make it consistent throughout (this also affects functions such as append, copy, etc.).

Similarly, the variant

func f4[T []E, E byte](x T) string { return string(x) }

will work with the very same change in the implementation.

So my inclination is to treat this as a bug: 1) it's not specified precisely enough in the spec, and 2) the implementation is not entirely consistent between generic and non-generic types.

I suspect (but I'm not 100% certain yet) we can make this change because it will simply enable code that so far was rejected.

Furthermore, we can argue that the code (f3 and f4) should work because we can instantiate those functions with types for which the conversions are valid (perhaps with suitable augmentation of ~ in the constraints). This might be argument with which we can rationalize the change. This essentially follows the argument about type sets that @Merovius is making; but there is a question of formulating this precisely.

Finally, all this doesn't address the issue where E is constrained by byte | rune as in the original examples of this issue because there is no core type in that case. I consider that an implementation restriction for now. Recalling the original generics proposal, the goal was always to permit all operations on values of type parameter types which are permitted on any type of the respective type sets (assuming that we really mean the "instantiated" type sets, which is what @Merovius has been alluding to, I believe). We are doing this in many cases, but certainly not in all cases. The escape in those other cases has been to resort to the core type. This is definitely something we'd love to clear up over time because it might help us getting rid of the notion of "core type" and as a result simplify the spec and thus the language (at the cost of a more complex implementation).

[griesemer]

Follow-up: "slice of bytes" (or "slice of runes") is not explicitly defined in the spec but examples were added in the past to make clear what is meant:

type myByte byte
string([]myByte{'w', 'o', 'r', 'l', 'd', '!'})       // "world!"

So []E is a "slice of bytes" if the underlying type of E is a byte.

[griesemer]

This is also related to #50421.