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: the rule is too restricted when ranging over values of type parameters #49551

Closed
go101 opened this issue Nov 12, 2021 · 11 comments
Closed
Labels
NeedsInvestigation
Milestone

Comments

@go101
Copy link

@go101 go101 commented Nov 12, 2021

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

$ go version
go version devel go1.18-23adc139bf Fri Nov 12 14:56:58 2021 +0000 linux/amd64

Does this issue reproduce with the latest release?

Yes, the latest tip.

What did you do?

package main

func Split[T []byte|string](s T, x byte) (a, b T) {
	var k = 0
	for ; k < len(s); k++ {
		if s[k] == x {
			goto End
		}
	}
	
	a = s
	return

End:
	return s[:k], s[k+1:] // invalid operation: cannot slice s (variable of type T constrained by []byte|string): T has no structural type
}

type MyByte byte
func Foo[T []byte|[]MyByte](s T) {
	for range s {} // cannot range over s (variable of type T constrained by []byte|[]MyByte) (T has no structural type)
} 

func Bar[T []byte|map[int]byte](s T) {
	for range s {} // cannot range over s (variable of type T constrained by []byte|map[int]byte) (T has no structural type)

}

func Duk[T []byte|string](s T) {
	for range s {} // cannot range over s (variable of type T constrained by []byte|string) (T has no structural type)

}

type Bytes []byte
func Zed[T []byte|Bytes](s T) {
	for range s {} // okay
}


func main() {}

What did you expect to see?

Compiles okay.

What did you see instead?

Some functions don't compile.

The rule is too restricted, which will limit the use scope of type parameters.

@go101 go101 changed the title cmd/compile: the rule is too restrict when ranging over values of type parameters cmd/compile: the rule is too restricted when ranging over values of type parameters Nov 12, 2021
@go101
Copy link
Author

@go101 go101 commented Nov 12, 2021

Sorry, the first function Split is for subslice and substring operation.
I will create a new issue for it if it is needed.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Nov 12, 2021

A problem is that range behaves very differently on []byte and string types. The value type of range on []byte is byte, and on string it is rune. I don't think there is any way that we can support range with a constraint that permits both []byte and string.

I'm not quite sure why a two-index slice doesn't work, though. An index expression works. CC @griesemer @findleyr

@ianlancetaylor ianlancetaylor added the NeedsInvestigation label Nov 12, 2021
@ianlancetaylor ianlancetaylor added this to the Go1.18 milestone Nov 12, 2021
@griesemer
Copy link
Contributor

@griesemer griesemer commented Nov 12, 2021

Please file a separate issue for the slice error and assign it to me. That's a simple oversight.

The range behavior is expected. Closing this issue as working as intended. Thanks.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Nov 12, 2021

If you haven't started yet - no need to file an issue. Fix is coming shortly. Thanks.

Never mind, this is a tad tricky to get right. Filed #49566 so it doesn't get forgotten.

@go101
Copy link
Author

@go101 go101 commented Nov 13, 2021

This is not only for []byte | string.

func ForEach[T []string|map[int]string](c T, f func(string)) {
	// cannot range over s (variable of type T constrained by []byte|map[int]byte) (T has no structural type)
	for _, v := range c {
		f(v)
	}
}

Even the following way also doesn't work:

func Max[T []E|map[int]E, E string](c T, f func(E)) {
	// cannot range over s (variable of type T constrained by []byte|map[int]byte) (T has no structural type)
	for _, v := range c {
		f(v)
	}
}

@go101
Copy link
Author

@go101 go101 commented Nov 13, 2021

If this is intended, I would like to submit a proposal to allow this.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Nov 13, 2021

This is intended. Mixing maps and slices this way in a range loop may seem appealing but quite possibly not a good idea because the behavior is so different (for one, map iteration is randomized, slice iteration is always the same). But you're welcome to file a proposal. Thanks.

@vsivsi
Copy link

@vsivsi vsivsi commented Jan 15, 2022

@griesemer

Range doesn't work for even much simpler cases, such as arrays of the same element type but with different lengths:

https://go.dev/play/p/Bz-XFdM-K8S?v=gotip

This really feels like it should work, but doesn't:

package main

import "fmt"

type multiArrayOfInt interface {
	[1]int | [2]int | [3]int | [4]int
}

func arraySummer[A multiArrayOfInt](array A) (sum int) {
	for _, v := range array {
		sum += v
	}
	return
}

func main() {
	fmt.Println(arraySummer([3]int{1, 2, 3}))
}

Errors with: cannot range over array (variable of type A constrained by multiArrayOfInt) (A has no structural type)

And it also doesn't work with only map types, even when only the keys types vary and are discarded by the range.

https://go.dev/play/p/wMG2KIU2wo8?v=gotip

If this code doesn't work, it basically means that map types are unusable as generics, since range is the only way to get at key values or iterate at all. At least in the array case above you can loop over ints up to len(array), but with map keys you're just completely locked out.

Duh, nevermind, for maps in this case you can just move the map type out of the interface constraint into the function parameter types. 😬

Still seems like the array case should work, but maybe it has something to do with the not being able to parameterize over constants (i.e. why the parameterized multiArrayOfInt type above is needed at all...)

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 18, 2022

range requires a structural type (range rules are not yet fully documented as the new spec is a work in progress) and the array case doesn't have a structural type. So this is working as intended.

Presumably this could be made to work, but it's not clear why this (array) case is important. We will not change this for 1.18. We have the proposal process to change things like this in the future. Thanks.

@vsivsi
Copy link

@vsivsi vsivsi commented Jan 18, 2022

@griesemer Thanks for the explanation, that makes sense, and I'm glad to hear this restriction is being documented more thoroughly.

Since parameterizing constants isn't in the current spec, I'm definitely using generic types with an enumerated list of short array types as in my example above. I need slices of arrays of uint64, where the arrays are relatively short (1, 2, 4, 8...) and the containing slice length is huge (billions). Using a slice of slices of uint64 in this case introduces unacceptable slice header overhead (and runtime bounds checking). Today I generate code for all of these different cases, so generics will eliminate a lot of that. I fought a very short battle to get parameterized integer constants into the spec, but quickly gave up when it became clear there was little interest in it.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 18, 2022

Note that allowing your array case to work with range may also introduce runtime bounds checking, depending on the implementation. In general, we don't promise that generic code is going to run faster than non-generic code. In some cases it may be slower.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation
Projects
None yet
Development

No branches or pull requests

4 participants