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: cannot index pointer to generic array #49447

Closed
josharian opened this issue Nov 8, 2021 · 9 comments
Closed

cmd/compile: cannot index pointer to generic array #49447

josharian opened this issue Nov 8, 2021 · 9 comments
Labels
FrozenDueToAge NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Milestone

Comments

@josharian
Copy link
Contributor

josharian commented Nov 8, 2021

This does not compile:

package p

type a1 [16]byte
type a2 [32]byte

type A interface {
	a1 | a2
}

func elem0[T A](t *T) *byte {
	return &t[0]
}

Error: ./x.go:11:10: invalid operation: cannot index t (variable of type *T)

This shows up in practice if you want to embed an array in a generic struct to avoid extra indirection/allocs, like this:

type S struct {
  // other fields
  arr A
}

but pass pointers to the array around internally to avoid making lots of copies of it (particularly as the array gets large).

The equivalent non-generic code compiles:

func elem0concrete(t *a1) *byte {
	return &t[0]
}
@ianlancetaylor
Copy link
Contributor

CC @griesemer @findleyr

I think this may be expected at present.

@ianlancetaylor ianlancetaylor added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 8, 2021
@ianlancetaylor ianlancetaylor added this to the Go1.18 milestone Nov 8, 2021
@griesemer griesemer added NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Nov 8, 2021
@griesemer
Copy link
Contributor

This is currently as expected. Note that the existing rules in the spec require a pointer to an array. Expanding this to type parameters requires that we have pointers to arrays in the type parameter type set (which is accepted). We'd need a new rule to generalize this also across a type parameter boundary. I'm not saying we can't do that, but it's an exception to the otherwise relatively regular rules.

This works:

package p

type a1 [16]byte
type a2 [32]byte

type A interface {
	*a1 | *a2
}

func elem0[T A](t T) *byte {
	return &t[0]
}

is that not sufficient?

@josharian
Copy link
Contributor Author

josharian commented Nov 8, 2021

is that not sufficient?

This is what I mentioned above about embedding an array in a generic struct to avoid extra indirections and allocs. struct { x [16]byte } is importantly different than struct { x *[16]byte }.

(But maybe I'm missing something. I find I still do not yet know how to make good use of generics.)

@ianlancetaylor
Copy link
Contributor

Can you show us more context? Show us the program that doesn't work with @griesemer 's suggestion.

@josharian
Copy link
Contributor Author

josharian commented Nov 9, 2021

In the course of writing a minimized program, I found a workaround:

func elem0[T A](t *T) *byte {
	switch a := any(t).(type) {
	case *a1:
		return &a[0]
	case *a2:
		return &a[0]
	default:
		panic("unreachable")
	}
}

It's ugly, but it works.

@findleyr
Copy link
Contributor

findleyr commented Nov 9, 2021

Just catching up and curious about this.

@josharian why is that type switch necessary? Why can't you use @griesemer's suggestion of including the pointer-to-array types in the type parameter type set?

type A interface {
	*a1 | *a2
}

func elem0[T A](t T) *byte {
	return &t[0]
}

But also, @griesemer I'm not sure that supporting this would make the spec less regular, and supporting this seems straightforward (I have a CL that does it...). I actually think that @josharian demonstrated that it would be less surprising if this worked, than if it doesn't.

@findleyr findleyr reopened this Nov 9, 2021
@griesemer
Copy link
Contributor

I agree that supporting it is straight-forward. But we need an extra rule. We may also need to look into other situations where we may need to apply this (pointer-to-struct in some cases).

@findleyr
Copy link
Contributor

findleyr commented Nov 9, 2021

Ok, thought about this a bit more. I think it may more generally be a source of confusion that type expressions do not 'map over' type sets; i.e. the type set of *T is not "the set of pointers to types in the type set of T", but rather a single type. This is why some of the places where type substitution would work are disallowed by the type checker. I understand the reasons for this (I think). However, I expect that most users will not memorize all the rules for type parameters, and will instead apply the 'substitution' heuristic. Anything we can do to align the spec more closely to the substitution heuristic may actually reduce user confusion, even if it complicates the spec.

But I don't think anything needs to be done for 1.18. I'll re-close this issue again and we can revisit if there is further confusion of this sort.

I would still be interested in @josharian's use-case though.

@findleyr findleyr closed this as completed Nov 9, 2021
@josharian
Copy link
Contributor Author

josharian commented Nov 9, 2021

The use case is a trie for looking up IP addresses (without zones). For space reasons, it'd be nice to have an IPv4 trie [4]byte and an IPv6 trie [16]byte. Generics seemed like an obvious fit. This is performance sensitive, so it is important that the array be a struct field, rather than a pointer to an array (data locality, fewer allocs, no nil checks).

I was definitely using the mental heuristic you indicated.

I also just encountered an identical issue with slicing:

func asSlice[T A](t T) []byte {
	return t[:]
}

also does not compile, even though it compiles for each of the types in T.

Here's a more complete program:

package p

type a1 [16]byte
type a2 [32]byte

type A interface {
	a1 | a2
}

type S[T A] struct {
	arr T // initial backing array for buf
	buf []byte
}

func makeT[T A]() *S[T] {
	var s S[T]
	switch a := any(s.arr).(type) {
	case a1:
		s.buf = a[:]
	case a2:
		s.buf = a[:]
	default:
		panic("unreachable")
	}
	return &s
}

It'd be nice to be able to remove the dynamic type switch from makeT and just unilaterally write s.buf = a[:].

Note that defining T as *a1 | *a2 doesn't make any sense: The T field exists to provide an initial backing array, which is pointless if you have to allocate separately in order to use it.

@golang golang locked and limited conversation to collaborators Nov 9, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Projects
None yet
Development

No branches or pull requests

5 participants