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

[ianlancetaylor]

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:

• the type set of comparable is all non-interface types that are comparable per the language spec

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.

[zephyrtronium]

@Merovius

I was, in that particular comment, just observing that many people have above commented that it's strange for any to not be comparable, but struct{ any } to be and that that's what they didn't like about this proposal. And that your suggestion would have the same flaw, to those people.

I see them as different circumstances.

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, and the fact that struct{any} would be assignable to comparable is a consequence of the definition of comparability that we've had since the beginning.

If this proposal is accepted and the definition of comparable does not change, then the fact that any is not in the type set of comparable is a consequence of a special-case rule that interfaces are not in the type set of comparable despite being comparable, and the fact that struct{any} is therein is a consequence of a special-case rule that comparable doesn't care about the recursive structure of types like comparability does.

Edit: I should say, I do understand that having both #51338 and comparable interfaces leads to asymmetry, but I can easily describe and explain that asymmetry and how to work around it to someone transitioning to Go with generics. I think it is easier to explain things as they are, and as proposed, to new Go programmers than to those with some experience.

[Merovius]

@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]

@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.

[earthboundkid]

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]

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]

@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 https://github.com/golang/go/issues/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, comparableshould 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]

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]

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]

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]

@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]

@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]

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]

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

[abligh]

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]

@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]

@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]

@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]

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]

Created a sort of counter-proposal https://github.com/golang/go/issues/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]

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]

@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]

Yes.

That's great. So we can't prevent panic anyway. I think this might clarify https://github.com/golang/go/issues/52474#issuecomment-1106059058 and left for the decision.

[Merovius]

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]

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 https://github.com/golang/go/issues/51338#issuecomment-1058223193.)

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]

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]

See #52614 for another take on this problem.