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

proposal: spec: permit non-interface types that support == to satisfy the comparable constraint #52474

Closed
ianlancetaylor opened this issue Apr 21, 2022 · 76 comments
Labels
generics Proposal
Milestone

Comments

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 21, 2022

Background

In Go 1.18 we introduced a type constraint comparable. The type constraint is satisfied by any type that supports == and for which == will not panic. For example, it is satisfied by int and string and by composite types like struct { f int } or [10]string. On the other hand, it is not satisfied by types like any or interface { String() } or struct { f any } or [10]interface{ String() }.

This decision has led to considerable discussion; for example, #50646, #51257, #51338.

When considering whether a type argument satisfies the comparable constraint, there are two cases to consider.

For an interface type, the rule in the spec is simple: an interface type T implements an interface I if "the type set of T is a subset of the type set of I." By this definition the type any does not implement comparable: there are many elements in the type set of any that are not in the type set of comparable. More generally, no basic interface implements comparable. Some general interfaces, such as interface { ~int }, implement comparable; it is not possible today to use this kind of general interface as an ordinary type, but a type parameter constrained by such a general interface will implement comparable.

For a non-interface type, the rule is different. A non-interface type T implements an interface I if it "is an element of the type set of I." For a language-defined type like comparable, the language defines that type set. The current definition says that comparable "denotes the set of all non-interface types that are comparable."

However, the current implementation is slightly different. In the current implementation, a composite type that includes an element of interface type does not implement comparable, although such a composite type is "comparable" according to the definition in the spec. The implementation was written that way based on the belief that comparable should only be implemented by types that will not panic when not used in a comparison. This is a valuable property, but it leads to some complications.

For example (this is based on a comment by @Merovius), consider a package "annotated" that implements an annotated value type:

type Value struct {
	Annotation string
	Val        any
}
// Various methods on Value.

Now consider a package "p" that uses that type, and suppose that package p ensures that it only stores values with comparable types in the Val field. It's fine for package p to use the type map[annotated.Value]bool. That works because the type annotated.Value is comparable according to the language definition. However, annotated.Value does not implement comparable, because the type of the element Val is an interface type that does not implement comparable. That means that code like this does not work:

type Set[Elem comparable] map[Elem]bool
var ValSet Set[annotated.Value]

Since annotated.Value does not implement comparable, the compiler will reject this code.

There is no good workaround for package p in this scenario. There is no way for p to say that it wants a version of the type annotated.Value that restricts Val to comparable types. It wouldn't be appropriate to change the annotated package, since that package can also be used by other packages that don't want to restrict Val to comparable types.

Proposal

Therefore, we propose that we change the implementation. Arguably the implementation is not quite following the spec here, so there may be no need to change the spec.

The new rule is:

As before:

  • an interface type implements comparable if the type set of the interface type is a subset of the type set of comparable
  • a non-interface type implements comparable if it is a member of the type set of comparable

For example, by this definition, annotated.Value implements comparable, and the problem outlined above goes away.

Note on interface types

This change means that there is little reason to seek the comparable version of a non-interface type T, as such types are now always comparable or never comparable. However, people may still want to get the comparable version of an interface type. For example, code might want the fmt.Stringer type but only permitting comparable types. If we adopt #51338, then people can get this type by writing interface { comparable; fmt.Stringer }. However, that is not part of this proposal.

Timing

Because of the confusion in this area, and the apparent discrepancy between the spec and the implementation, it may be worth implementing this in the 1.19 release, even though that is soon.

@DeedleFake
Copy link

@DeedleFake DeedleFake commented Apr 21, 2022

So, to clarify, this would allow the following?

func Equal[T comparable](t1, t2 T) bool {
  return t1 == t2
}

type Example struct {
  Val any
}

func main() {
  Equal(Example{""}, Example{""}) // true
  Equal(Example{[]int(nil)}, Example{[]int(nil)}) // panic
}

However, Equal(any(0), any(0)) would still not be allowed, correct? And in the panicking case where it is allowed, it would just be up to the user to make sure that nothing that isn't actually comparable is used with a comparable constraint?

Without allowing any to be used directly, it would allow a workaround for the issue of CustomMap[K comparable, V any] not working as CustomMap[any, string], but it would be kind of messy because it would require that it be wrapped in a struct type first. That seems like it'll be confusing to new users.

@zephyrtronium
Copy link
Contributor

@zephyrtronium zephyrtronium commented Apr 21, 2022

Practically, this seems no different to me from just removing the special case that interface types are comparable types that are not in the type set of comparable. If I have a generic wrapper for sync.Map and I want the type behavior that sync.Map currently provides, I write var m Map[[1]any]any instead of var m Map[any]any, along with extra syntax around uses.

@atdiar
Copy link

@atdiar atdiar commented Apr 21, 2022

The issue is that an interface can reside at an arbitrary deep level within a struct. (struct of struct of struct...)

Hence, it may not be obvious that a comparison may panic.

I'm not too convinced and would rather keep the current, stricter, behavior.
It seems to me that this example exposes a rather rare pathological case where the comparison intent is being guaranteed by convention and not code.

On the other hand, I see the other issue: it forces the creators of packages to find out in advance whether an interface field should require comparable or not.
That definitely deserves more thinking.
Would be great to get such examples from the corpus of Go code that exists at large.
I looked but I don't have such examples myself.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Apr 21, 2022

I think ultimately the least confusing thing to allow interface values to match the comparable constraint. That doesn't stop you from allowing values of the comparable interface later. It is admittedly somewhat confusing but this is carpet stuck under furniture that's too heavy to move so it's going to stick up somewhere.

@atdiar
Copy link

@atdiar atdiar commented Apr 21, 2022

I think ultimately the least confusing thing to allow interface values to match the comparable constraint. That doesn't stop you from allowing values of the comparable interface later. It is admittedly somewhat confusing but this is carpet stuck under furniture that's too heavy to move so it's going to stick up somewhere.

Unfortunately, I don't think that it would mix well with allowing constraint interfaces (such as comparable) as regular interfaces.
That would make any interface embedding comparable only usable as a constraint. A "color" that could be more annoying to deal with.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Apr 21, 2022

You can't put interface values in other interfaces so you could still allow values of the comparable interface.

@atdiar
Copy link

@atdiar atdiar commented Apr 21, 2022

You can't put interface values in other interfaces so you could still allow values of the comparable interface.

Edit: (I had misunderstood.your response)

The issue lies with asserting an interface value to comparable or any interface embedding comparable. That would cause an incongruity.
Which would also occur on variable assignment.

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Apr 21, 2022

@DeedleFake I agree with what you wrote above.

@DeedleFake @zephyrtronium Yes, it is easy to use a struct or array to permit using an arbitrary interface type to satisfy a comparable constraint. I think that's OK. As noted, I think that #51338 will provide a cleaner way to do the same thing while avoiding the potential panic.

@jimmyfrasche We could do that. In fact we could do that even after adopting this proposal if we decide to. I'm not personally sure that it's the least confusing approach; see the lengthy discussion in #50646 when we started down that path before changing our minds. I think it's become clear that any approach in this area is confusing.

@Merovius
Copy link

@Merovius Merovius commented Apr 21, 2022

@atdiar

Unfortunately, I don't think that it would mix well with allowing constraint interfaces

I think it is clear that we should either allow comparable as a normal interface type or make interface-types implement comparable, but not both. They are complementary, equally simple solutions to the issues.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Apr 21, 2022

@Merovius that's not at all clear to me. Doing both seems like a perfectly fine thing to do me—and the best thing to do overall. It's possible I'm missing something, though.

@atdiar
Copy link

@atdiar atdiar commented Apr 21, 2022

@atdiar

Unfortunately, I don't think that it would mix well with allowing constraint interfaces

I think it is clear that we should either allow comparable as a normal interface type or make interface-types implement comparable, but not both. They are complementary, equally simple solutions to the issues.

Well, it also depends on whether there are plans to make all constraint interfaces usable as regular interface types (which was in consideration, I recall).
The present decisions could preclude some future plans to do just that.

@Merovius
Copy link

@Merovius Merovius commented Apr 21, 2022

@jimmyfrasche If all interface types implement comparable and comparable is a type, then

var a any = func() {}
var b comparable = a

should be allowed. In that case, I don't see the point of making comparable a type, as it does not seem to provide better guarantees than any.

To me, making comparable a type is a specific solution to guarantee that func Eq[T comparable](a, b T) bool { return a == b } never panics. To me, that goal isn't achieved if you can then instantiate Eq[any].

i.e. to me, they are both different solutions to the same problem, attacking it from opposite angles.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Apr 22, 2022

You would have to write

var a any = func() {}
var b comparable = a.(comparable)

replace comparable with any other nonempty interface and your example fails at compile time and my rewrite fails at runtime so I would assume that the same would hold true for comparable.

@Merovius
Copy link

@Merovius Merovius commented Apr 22, 2022

@ianlancetaylor

As noted, I think that #51338 will provide a cleaner way to do the same thing while avoiding the potential panic.

Personally, I think that if we make comparable a type and only comparable types assignable to that, it seems non-committal not to go all the way with that. If comparable is added, it should actually provide a guarantee that the comparison never panics. Otherwise, why even introduce it? That is, if we accept #51338, I'd be in favor of biting the bullet on making comparable viral and reject this proposal.

@Merovius
Copy link

@Merovius Merovius commented Apr 22, 2022

@jimmyfrasche

replace comparable with any other nonempty interface and your example fails at compile time

Right, but not all interface types implement any other nonempty interface. But all interface types would implement comparable.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Apr 22, 2022

If any as a type/interface satisfies comparable as a metatype/constraint, then that does not imply that the dynamic type of an interface value is necessarily comparable

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Apr 22, 2022

@Merovius How do you think we should address the problem with annotated.Value (which was based on one of your comments)?

The comparable constraint and interface types are a bad mix no matter what we do. I think that comparable still serves a purpose even if we adopt this proposal, though: it rejects types that are clearly not comparable, and it rejects attempts to instantiate with an interface type that may not be comparable. As @jimmyfrasche said above the carpet is going to stick up somewhere, and this proposal is suggesting a specific spot where it will stick up: composite types that contain interface types.

@atdiar
Copy link

@atdiar atdiar commented Apr 22, 2022

There is also the option of not using a generic Set but rather an interface-based set (i.e. based on map[interface{}]bool) when one wants to be able to force comparison of potentially non-comparable values.

If applicable, then there might not be a need to special-case the generics implementation for composite types that contain interface types.

But really it depends on the cases and how widespread there are. Would be great to have real code examples.

@zephyrtronium
Copy link
Contributor

@zephyrtronium zephyrtronium commented Apr 22, 2022

There is also the option of not using a generic Set but rather an interface-based set (i.e. based on map[interface{}]bool) when one wants to be able to force comparison of potentially non-comparable values.

The problem isn't really with "potentially non-comparable values." There are interface types other than any which I might want to use as map keys, where what I want is to use several different concrete types in one map. reflect.Type has been a common example. ast.Node – for several different packages named ast – have been another. Since interfaces don't implement comparable, there is no way to write type-generic code for this case.

I have to duplicate the code, or at least a type-safe wrapper, for every interface type I want to use as a map key. This is exactly the problem that generics should be solving. Out of caution, for situations where comparable types are useful, it was chosen to address code duplication for all comparable types except interface types by introducing a special case for comparable. In my view, this proposal attempts to make that special case even more special and adds extra steps for actually writing the code I want to write, instead of simply making comparable consistent with the type system I've been using for eleven years.

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented Apr 22, 2022

Another tact might be to allow the use of (possibly panicking) == with [T any]. Then you would only use the comparable constraint when you want assurances that no incomparables can be passed in.

@leaxoy
Copy link

@leaxoy leaxoy commented Apr 22, 2022

The correct approach is redesign the type-system, not patch it, it would make type-system not self-consistent.

Comparable should be ordinary interface type, and primitive type, struct of comparable type, array of comparable type, pointer etc implement Comparable default.

@Merovius
Copy link

@Merovius Merovius commented Apr 22, 2022

@ianlancetaylor

How do you think we should address the problem with annotated.Value (which was based on one of your comments)?

Require to duplicate the type and write custom conversions. That's a hassle, of course. But to me, that's an argument against #51338, not in favor of patching something worse over it. In my opinion, if we think we need #51338, we ought to accept this problem and see how much it comes up - at least at first.

There are two other ways (apart from this proposal) how I think we could address it, if need be:

  1. Make type-assertion on comparable "recursively" assert comparability. That is, var v annotated.Value; v.(comparable) succeeds, if the dynamic value of the Val field is comparable. This might feel a bit strange, but it makes sense in spirit of a type-assertion and I think it would keep the guarantee of comparable.
  2. Make struct types convertible, if interface fields only differ in comparabaleness, similar to how we do it with tags. That is, make annotated.Value convertible to struct{ Annotation string; Val comparable }. That would still require to duplicate the type, but at least a) you don't need a manual conversion and b) the compiler will check if the struct-definitions drift. It would still mean that the guarantee of comparable is violated, but not worse than this proposal and it would require an explicit conversion to do so.

@Merovius
Copy link

@Merovius Merovius commented Apr 22, 2022

@carlmjohnson

Another tact might be to allow the use of (possibly panicking) == with [T any]. Then you would only use the comparable constraint when you want assurances that no incomparables can be passed in.

We forbade interface-types from implementing comparable because it was deemed unacceptable for == to panic, when using it. I don't think extending this problem to all types makes sense, then. i.e. this seems strictly worse than the original situation of having interface-types implement comparable - it extends the downsides to more situations, while also making comparable less useful.

@changkun
Copy link
Member

@changkun changkun commented Apr 22, 2022

Just a clarifying question: why it was deemed unacceptable for == to panic?

@atdiar
Copy link

@atdiar atdiar commented Apr 22, 2022

@zephyrtronium that's a fair remark.

I guess another alternative would be to modify the concept of constraint so that it's not necessarily seen as an interface ( i.e. a constraint applicable to types belonging to a typeset) but rather a constraint applicable to any type of the type system.

So that we can constrain interfaces effectively. Typically by using predicates as constraints. (hasComparisonOperator etc.)

This would be an extension. We could still have the constraint interfaces so that we can keep comparable as a compile-time enforcer.

But effectively, there would be two kinds of constraints. One would not be "reifable" as a type and stems from the bootstrap of the type system in terms of predicates. (or maybe it could too but with different semantics, I'm not sure)

The issue to solve is that so far, we really constrain non-interface types only and we try to constrain interface types indirectly through their typesets.
Just an idea.

@Merovius
Copy link

@Merovius Merovius commented Apr 22, 2022

@atdiar We have that differentiation today. It's the difference between an interface having only methods and one which also has type elements (or is/embeds comparable).

@Merovius
Copy link

@Merovius Merovius commented Apr 22, 2022

@jimmyfrasche If I understand you correctly, that's exactly what #51388 proposes - making comparable a type, which only (recursively) comparable types can be assigned to.

@Merovius
Copy link

@Merovius Merovius commented Apr 22, 2022

@zephyrtronium

If we suppose #51338 is accepted and interface values are included in the type set of comparable, then the fact that any is not assignable to comparable is a consequence of the definition of assignability that we've had since the beginning

I think that can be argued, but it can also be argued against. The definition of assignability for interface types today is

T is an interface type, but not a type parameter, and x implements T.

The suggestion is for interface types to implement comparable, therefore if x's type is any, it implements comparable and should be assignable to a variable of type comparable.

I don't think we can argue with current semantics here. The point is exactly to introduce a completely new type comparable and make that type more restrictive than other interfaces. What those restrictions are remains to be sussed out, but they certainly should be as useful and consistent as possible.

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented Apr 22, 2022

Personally, I'd prefer if we tried to largely stick with jargon which is already established.

My argument is that this discussion is particularly thorny because the current jargon is missing a necessary term. It makes everything harder to think about when you can't use a proper noun to stick something in your mind.

Looking at Jimmy's 3 kinds + 3 sub-kinds, do we need to distinguish between truly incomparable and 0-comparable for this discussion? No, they can both be lumped under "incomparable" for our purposes here. But failure to pick apart the three sub-kinds of comparability has caused all of the other problems.

@Merovius
Copy link

@Merovius Merovius commented Apr 22, 2022

I think phrases like "comparable, but might panic at runtime" is within currently established jargon and, while a bit less wieldy, not that hard to use. But FWIW arguing about this is off-topic here, I was just trying to point out that I find it confusing to introduce new jargon, if we have not agreed on it. At least what's in the spec leaves a pretty good definition of what's "agreed upon jargon".

@atdiar
Copy link

@atdiar atdiar commented Apr 22, 2022

@atdiar I'm still confused what you are trying to say. comparable already does exactly what you describe - it's a constraint, which can't be used as a type and it means (among other things) "can be used as a map key". I don't understand why you are trying to introduce a third kind of type constraint, if it does exactly the same as one of the ones we already have.

@Merovius
It's mainly because the current implementation enables us to answer #49587 (and more)
and that might be something we want to keep since it provides compile-time guarantees.

There is also the fact that typesets are currently transitive sets and I think it plays well with the concept of interface embedding.
I have a hunch that it simplifies the computation of operation sets derived from type sets.

IF interfaces are deemed comparable where comparable is an interface, we lose the transitivity. Which is why I argue that in that case, comparable should not be an interface (i.e. it would not define a typeset).

So, of course, we could change comparable, but one may still want a way to get the current semantics back in some shape or form. In the end, that would still equate to introducing something.

@apparentlymart
Copy link

@apparentlymart apparentlymart commented Apr 22, 2022

I must confess that I'm getting a bit lost in the different permutations being discussed in this now-long thread, and so I'm sorry if I'm repeating something that was already said in different words above.


My existing intuition is that whenever I use a value of an interface type I'm opting in to various things being checked at runtime rather than compile time, because the purpose of an interface type is to allow dynamically choosing a concrete type dynamically at runtime and so runtime checks are a necessary cost in return for that flexibility. With runtime checks comes the possibility of panics if my code is found incorrect at runtime, which is the risk I take in return for the benefit of choosing types dynamically.

With the introduction of type parameters, I extended that intuition to say that if I use a type parameter then I am expecting to fix a specific type at compile time. In return, the compiler should be able to guarantee that my chosen type is suitable and thus ensure that anything type-related which would have been a runtime panic will be a compile-time error instead.

My intuitions above make me feel like currently the type parameter handling is overreaching into world of interface types, with this rule aiming to make a certain subset of runtime panics impossible even though I've opted in to that risk by using interface types. It isn't a responsibility of the compiler to prevent me from using interface types in a way which might panic, only to prevent me from using them in a way that would certainly panic.

I would therefore be in favor of a design like what is proposed here, where I am allowed to use a value of any interface type (or an otherwise-comparable type containing one) to satisfy the comparable type constraint.

I do see the argument above that it would therefore be no different than any. I suspect that is be true from the perspective of what the compiler can guarantee, but it still carries an additional meaning that I can take into account as a developer: if a type parameter is constrained as comparable and I'm intending to pass an interface type into it, I know I must take care to only pass comparable types through that interface value in order to avoid a runtime panic. Conversely, if I want the compiler to guarantee at compile time that the given type is valid, I (as the caller) can be sure to only use non-interface types.

If map types didn't already allow the calling program to take this risk when desired then perhaps my existing intuitions here would have developed differently, but with the language as it existed before type parameters the current restriction seems inconsistent and it subverts my ability to opt in to dynamic type checking and the possibility of runtime panics by using interface types.

(I am considering the current prose in the spec about what is allowed as a map key to imply that the generic signature of a map type would be map[K comparable]V any, and I would prefer the implementation to behave that way, by changing comparable to match the map behavior rather than the other way around.)

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Apr 23, 2022

There are three major definitions of comparable relevant to this thread:

  • comparable/S - the current spec definition of comparable
  • comparable/RPF - the recursively panic-free definition of comparable generics use now
  • comparable/1PF - the 1-layer of panic free comparable being proposed (which is any non-interface comparable type)

Regardless of definition, there are two uses of comparable:

  • C(comparable) - as a constraint
  • T(comparable) - as an interface value [should that be allowed in the future]

Note that as interface vaules don't nest T(comparable/1PF) and T(comparable/S) are identical.

If we continue to use C(comparable/RPF) and permit T(comparable/RPF) [this is #51338]

  • == never panics
  • comparable/RPF needs to be enshrined in the spec
  • T(comparable/RPF) is viral and lots of interfaces will have to be marked comparable for it to be useful

If we permit C(comparable/1PF) [this proposal]

  • == may panic
  • comparable/1PF needs to be enshrined in the spec
  • T(comparable/1PF) could be permited later
  • this can be later relaxed to C(comparable/S) without any operational changes to T(comparable)

If we permit C(comparable/S)

  • == may panic
  • T(comparable/S) could be permitted later
  • no additional notions of comparable needed

Did I get anything wrong?

@neild
Copy link
Contributor

@neild neild commented Apr 23, 2022

I am exceedingly confused by who is arguing for what behavior here, and must apologize for increasing the amount of confusion in the world by offering an opinion.

The Go spec has a definition of comparable, which clearly states that "interface values are comparable". I find it very surprising that the comparable constraint excludes interface values, given that these values are comparable under the spec's definition.

I'm further surprised that the compiler believes struct { V any } doesn't satisfy the comparable constraint, since the spec states that "a type T implements comparable if T is not an interface type and T supports the operations == and !=." struct { V any } is not an interface type, and it supports == and != (although these operators may cause a run-time panic, of course).

I think the simplest available option is to state that all comparable types (under the spec's definition) implement the comparable constraint, so that there's one consistent definition of "comparable".

This means that it is impossible to write a type constraint for values which support == and != and also guarantee that these operators will not cause a run-time panic. That's entirely consistent with the treatment of comparable interface values in non-generic code, which seems fine to me.

@beoran
Copy link

@beoran beoran commented Apr 23, 2022

@carlmjohnson

I think you have it right. The core problem is that the concept of comparability is not clean cut, so with a single comparable type, we cannot cover all cases. The simplest solution would be to add additional predefined interfaces such as hashable, strictlycomparable , etc. Would that work?

@Merovius
Copy link

@Merovius Merovius commented Apr 23, 2022

@jimmyfrasche

Did I get anything wrong?

No, I believe everything you say is correct. With the caveat that "could" and "should"/"it would be a good idea" are different.

@beoran

The core problem is that the concept of comparability is not clean cut, so with a single comparable type, we cannot cover all cases. The simplest solution would be to add additional predefined interfaces such as hashable, strictlycomparable , etc. Would that work?

Lots of things might work, but I don't think this is a good idea at all. We don't really want to expose more pre-declared identifiers unless we absolutely have to. I also don't really think it does solve the problem. The real question is how interface types should behave. If we have an answer to that, we don't need to actually introduce new identifiers for those behaviors, we can just enshrine the behavior we want.

@zephyrtronium
Copy link
Contributor

@zephyrtronium zephyrtronium commented Apr 23, 2022

I opened #52509 to hopefully keep the "comparable and comparable could be the same" comments focused on a proposal about doing that, rather than filling the comments of this one.

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 23, 2022

Change https://go.dev/cl/401874 mentions this issue: spec: clarify type set and interface are different

@abligh
Copy link

@abligh abligh commented Apr 23, 2022

I am a little confused as to how the proposal solves the problem stated.

In Go 1.18 we introduced a type constraint comparable. The type constraint is satisfied by any type that supports == and for which == will not panic. For example, it is satisfied by int and string and by composite types like struct { f int } or [10]string. On the other hand, it is not satisfied by types like any or interface { String() } or struct { f any } or [10]interface{ String() }.

For background, my interest is mainly in making generic versions of (e.g.) sync.Map.

As I understand it you can have a map of any interface type, because 'Interface values are comparable. Two interface values are equal if they have identical dynamic types and equal dynamic values or if both have value nil.' (source). However, under this proposal despite interface values being comparable, the interface types would not in general still implement comparable. This is not only confusing but makes it difficult to write code like the following which works for all types eligible to be keys for maps:

func Make[K comparable](k K) map[K]bool {
	m := make(map[K]bool)
	m[k] = true
	return m
}

This is despite the fact that comparison of interface values can never panic (as far as I know).

I wonder whether the issue (specifically with generic versions of maps, sets etc) is that we're trying to use comparable as the constraint, which ... overconstrains things. The notion of 'comparable' (the language definition, not the current interface / keyword) corresponds well to what is currently accepted as a map key: 'The comparison operators == and != must be fully defined for operands of the key type; thus the key type must not be a function, map, or slice. If the key type is an interface type, these comparison operators must be defined for the dynamic key values; failure will cause a run-time panic.'.

If we can't make the definition of comparable the same as what the language spec treats as 'comparable' (which is as far as I can see 'everything you can use as a map key'), then could we at least have some form of constraint mapkey which includes only those types that are used as map keys - I think this is a superset of comparable.

@Merovius
Copy link

@Merovius Merovius commented Apr 23, 2022

@abligh

This is despite the fact that comparison of interface values can never panic (as far as I know).

It can

could we at least have some form of constraint mapkey which includes only those types that are used as map keys - I think this is a superset of comparable

It's not a superset. The types usable as map keys are exactly the same as the types which can be compared using ==. And storing an interface value in a map panics exactly if comparing that value panics.

@abligh
Copy link

@abligh abligh commented Apr 23, 2022

@Merovius

could we at least have some form of constraint mapkey which includes only those types that are used as map keys - I think this is a superset of comparable

It's not a superset. The types usable as map keys are exactly the same as the types which can be compared using ==. And storing an interface value in a map panics exactly if comparing that value panics.

Sorry, I put comparable in backticks meaning the keyword not the language definition, accidentally illustrating the confusion :-). I meant "could we at least have some form of constraint mapkey which includes only those types that are used as map keys - I think this is a superset of comparable" - i.e. the set of things that can be used as keys of maps is a superset of the things which implement comparable either under this proposal or Go 1.18. I know the set of things that can be used as keys of maps is exactly equal to the things that are comparable (per the language spec) (i.e. can be compared using ==), though as you point out some comparisons may panic at runtime.

@Merovius
Copy link

@Merovius Merovius commented Apr 23, 2022

@abligh My point was kind of that, if we think the behavior of mapkey is better, then comparable should just behave that way. There is no difference between "useful as a map key" and "useful for comparisons", both would panic or not panic in the same situations and allow or disallow the same operations to happen. I don't think we should have two things in the language to mean the same thing, where the only difference is that one behaves worse than the other (or, let's say "some people think one of them is worse, others think the other is worse, but neither is actually better or worse").

If we think mapkey is the better behavior, we should adopt #52509.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Apr 23, 2022

Meta. I think regardless of the outcome of these various proposals what comparable means needs to match what the spec defines as comparable, even if that means coming up with a new term for types that permit == but don't match this hypothetical new definition of comparable.

@atdiar
Copy link

@atdiar atdiar commented Apr 24, 2022

Created a sort of counter-proposal #52531
I think it might be a way to address the issue about comparability in its entirety.
(it's also my first proposal and issue ever 🙂)

@changkun
Copy link
Member

@changkun changkun commented Apr 25, 2022

Will the following code panic if this proposal is accepted?

package main

type s struct {
	f any
}

func eq[T comparable](x, y T) bool { return x == y }

func main() {
	_ = eq(s{func() {}}, s{func() {}})
}

If yes, how does it differ from the following case?

package main

func eq[T comparable](x, y T) bool { return x == y }

func main() {
	_ = eq(any(func() {}), any(func() {}))
}

@Merovius
Copy link

@Merovius Merovius commented Apr 25, 2022

@changkun

Will the following code panic if this proposal is accepted?

Yes.

If yes, how does it differ from the following case?

That case is not valid, currently or under this proposal. If you mean "it doesn't seem very different, so if we should allow one, why not allow the other?", I agree.

@changkun
Copy link
Member

@changkun changkun commented Apr 25, 2022

Yes.

That's great. So we can't prevent panic anyway. I think this might clarify #52474 (comment) and left for the decision.

@Merovius
Copy link

@Merovius Merovius commented Apr 25, 2022

FWIW I think there is an argument to be made that preventing panics is important (not in favor of this proposal, because it doesn't, but e.g. for #51338), even if we didn't do it so far, which goes like this:

  1. We maybe want, at some point, want to use type element interfaces to add variant types to Go
  2. If we do that, we probably want to be able to do it for comparable as well, because it would be strange to have an exception to this
  3. If comparable becomes a full type, it should probably be distinguished by preventing panics on comparison statically, because that would be the only thing differentiating it from any, in terms of real benefit in usage.
  4. For consistency, comparable as a constraint should then be fulfilled by the same set of types which are assignable to comparable.
  5. Therefore, we should maintain the meaning of comparable as a constraint to "types on which equality is statically prevented from panicing"

This chain would then argue against this proposal as well as #52509, as they don't maintain that meaning. So, if we want to use type element interfaces as variant types at some point, rejecting this proposal and #52509 and accepting #51338 will ultimately lead to the most consistent and simple language.

Personally, I don't like that this argument depends on wanting to do something which we haven't yet decided to do. I don't know how likely it is that we will and at what point that would happen. And we might want to solve the "instantiating comparable constrained generic types with interface types" before that. But it is a fair argument.

(I also agree with @jimmyfrasche here, that we should then make sure comparable reflects what the spec calls comparable)

@bcmills
Copy link
Member

@bcmills bcmills commented Apr 25, 2022

I went back to the discussion in #51338 to evaluate how this proposal compares.

As far as I can tell, it does have one advantage — namely, it allows type-assertions to comparable to succeed for all values that are actually comparable. (Compare #51338 (comment).)

However, that comes with an equivalent disadvantage: a successful type-assertion to comparable would not actually ensure that the value can be compared without panicking. So it would allow run-time weakening of static checks, but would not succeed in providing an equivalent dynamic check that programs could use to avoid the panic.

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Apr 26, 2022

Thanks for the good discussion. I'm persuaded that this proposal makes the language harder to understand without providing a commensurate improvement. I'm withdrawing it.

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Apr 29, 2022

See #52614 for another take on this problem.

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

No branches or pull requests