generics branch no longer works on go1.18rc1

[billinghamj]

I realise it is not intended for use at this point, but thought it might be useful to bring to your attention.

The generics branch works great on go1.18beta1 & go1.18beta2

But on go1.18rc1, it has these errors:

# github.com/deckarep/golang-set
./set.go:169:17: any does not implement comparable
./set.go:172:37: any does not implement comparable
./threadsafe.go:230:43: any does not implement comparable
./threadsafe.go:232:55: any does not implement comparable
./threadsafe.go:235:24: any does not implement comparable
./threadsafe.go:237:44: any does not implement comparable
./threadsafe.go:238:26: any does not implement comparable
./threadsafe.go:249:63: any does not implement comparable
./threadsafe.go:255:72: any does not implement comparable
./threadsafe.go:256:24: any does not implement comparable
./threadsafe.go:256:24: too many errors

I think this is as a consequence of golang/go#50646 (reference)

I've had a good look at it, and made some adjustments which seem to resolve most of it. But I wasn't able to find a way to get PowerSet working

For Pop:

func (s *threadUnsafeSet[T]) Pop() (v T, ok bool) {
	for item := range *s {
		delete(*s, item)
		return item, true
	}
	return
}

(Though this does require a change to the method signature - an alternative might be to introduce a new method and return the zero value on the old one, or to return a pointer)

Edit: For CartesianProduct, your intended code still seems to have the same problem

For PowerSet, the problem is that it won't allow Set[Set[T]] (Set[T] does not implement comparable), and the interface cannot be declared as comparable (interface is (or embeds) comparable)

Perhaps an alternative might be to return []Set[T](?)

[billinghamj]

Going through playing with some changes, for some of the tests, it seems there is no workaround to enable what they're trying to do

I've commented on the PR to flag that, as it seems odd to make this kind of code impossible to write

Edit: opened it as a new issue on the go repo - golang/go#51257

[billinghamj]

For now, I've released here without the problematic methods, as a workaround: https://github.com/billinghamj/golang-set

[deckarep]

Hey thanks for the vote of confidence on the new changes as well as the bug report.

PowerSet was added sometime back for completion sake but I will admit that I don’t think it’s used all that much. I have recently considered removing it because I couldn’t find a great solution that was generics compatible.

Your investigation is appreciated and I’ll see what I can do in the coming days.

[billinghamj]

No problem 🙂 I'm very happy to pitch in with anything if that'd be helpful too 👌

[billinghamj]

@deckarep Now that 1.18 is out, do you think you'd be interested in releasing the generics branch, perhaps with the 2 problematic methods removed?

[deckarep]

@billinghamj - sorry for the delay on this. I have finally got around to release a 2.0.0 tag using your changes to support the final release of Go 1.18.

Big thanks for sorting out the bug around any type not being comparable.

[fasaxc]

I found this while trying to make project calico's Set generic (PR) looking for a workaround for the "any not comparable" problem. The solution I happened on was to make an interface type Set[T any] and then two concrete implementations: type mapSet[T comparable] map[T]struct{} and type boxedSet[T any] map[any]struct{}. Then you can use mapSet if possible and boxedSet for interface types.

They both give type-safe methods 👍 but boxedSet has the overhead of boxing/unboxing into an any. They both implement Set[T] once T is specified so apart from picking the right constructor they're interchangable after that.

[billinghamj]

@deckarep btw, now that Go 1.20 is out, I think those methods could be added back :)

I believe the issue was finally resolved by golang/go#56548, and that change went out in 1.20