proposal: spec: permit values to have type "comparable"

As part of adding generics, Go 1.18 introduces a new predeclared interface type comparable. That interface type is implemented by any non-interface type that is comparable, and by any interface type that is or embeds comparable. Comparable non-interface types are numeric, string, boolean, pointer, and channel types, structs all of whose field types are comparable, and arrays whose element types are comparable. Slice, map, and function types are not comparable.

In Go, interface types are comparable in the sense that they can be compared with the == and != operators. However, interface types do not in general implement the predeclared interface type comparable. An interface type only implements comparable if it is or embeds comparable.

Developing this distinction between the predeclared type comparable and the general language notion of comparable has been confusing; see #50646. The distinction makes it hard to write certain kinds of generic code; see #51257.

For a specific example, you can today write a generic Set type of some specific (comparable) element type and write functions that work on sets of any element type:

type Set[E comparable] map[E]bool
func Union[E comparable](s1, s2 Set[E]) Set[E] { ... }

But there is no way today to instantiate this Set type to create a general set that works for any (comparable) value. That is, you can't write Set[any], because any does not satisfy the constraint comparable. You can get a very similar effect by writing map[any]bool, but then all the functions like Union have to be written anew for this new version.

We can reduce this kind of problem by permitting comparable to be an ordinary type. It then becomes possible to write Set[comparable].

As an ordinary type, comparable would be an interface type that is implemented by any comparable type.

Any comparable non-interface type could be assigned to a variable of type comparable.
A value of an interface type that is or embeds comparable could be assigned to a variable of type comparable.
A type assertion to comparable, as in x.(comparable), would succeed if the dynamic type of x is a comparable type.
Similarly for a type switch case comparable.

@griesemer

To be clear, this proposal is for Go 1.19 or later.

CC @griesemer

Amusingly, I wrote my first real generic code today and then immediately ran into this situation, in almost exactly the way described in the writeup.

My generic set type:

type Set[T comparable] map[T]T

I initially tested it with some simple cases involving T being a struct type containing only comparable fields, and I was just getting ready to call it done when I decided to write the following declarations as static assertions to verify it could support all of the types I wanted:

var _ Set[exampleInterface]
var _ Set[exampleComparableStruct]
var _ Set[*exampleUncomparableStruct] // pointers are comparable regardless of target type

type exampleInterface interface {
	comparable
	Boop()
}

type exampleComparableStruct struct {
	v [2]int
}

type exampleUncomparableStruct struct {
	f func(int)
}

This fails at compile time with the following error:

set_test.go:3:11: interface is (or embeds) comparable

I understand that this is one of the cases you already listed as what this proposal would allow:

A value of an interface type that is or embeds comparable could be assigned to a variable of type comparable.

However, I ended up here mostly by luck, because this error message happened to exactly match the text you used to describe the situation that would become valid. This error message was confusing to me because it just states something I know to be true: I intentionally embedded comparable in that interface type to try to make it possible to declare a set of that interface type. It doesn't say anything about why that statement is relevant, since it does seem to be valid to declare an interface which embeds comparable, just that it's not valid to then declare a value of that type.

I totally understand that making this work is not on the table until Go 1.19 at the earliest, but I wonder if it would be possible in the meantime to improve this error message to at least make a more direct statement about what I did wrong here:

set_test.go:3:11: cannot declare variable of interface type that is (or embeds) comparable

Perhaps I'm misunderstanding, but I believe from this writeup (and from my own further experimentation) that it's the declaration of the variable that is invalid, not the interface declaration itself.

In case it's helpful in evaluating the proposal, my underlying goal here is to make a set of values that are all comparable and all implement a specific interface, but that have different dynamic types.

This is actually part of an implementation of a directed acyclic graph (type Graph[V comparable], with Set[V] fields) where the nodes represent different actions, so in real usage there would be a type Action interface representing the idea of an action, and concrete implementations of that interface representing specific action types. The program will then walk the graph in a topological sort order and call a method of Action on each node, which is of course then a virtual call to perform the specific action represented by that value.

Action will actually be implemented only by pointers to the action types in practice, which will therefore all be comparable by pointer identity.

I'm not planning to pursue this any further for the moment, since it seems unlikely I will be able to achieve this goal with Go 1.18. I hope these details are helpful in evaluating the proposal.

Next day update: FWIW, I was able to work around this for now by separating the idea of a graph node (a pointer to a specific struct type) from the idea of an action, so that a graph node has an action, rather than is an action. For my purposes that seems to be sufficient for the moment, although this wrapping graph node struct isn't really adding anything right now except something concrete to save a pointer to.

type GraphNode struct {
	Action Action
}

type Action interface {
	// ...
}

type ActionGraph = graph.Graph[*GraphNode]

Is it possible to disallow comparisons with incomparable interfaces, to avoid runtime panics during comparisons? (looks hard).

I would think that disallowing comparisons with interfaces that aren't statically incomparable would be a breaking change at this point, since it's always been possible so far to carefully compare interface values and just make sure that you don't write any implementations that aren't themselves comparable. 🤔 I have several examples in the codebases I maintain in my dayjob which would immediately fail compile under that rule, even though in practice they can never panic at runtime today.

It does seem like a shame, since this seems like a clear win if this were a green field problem, but I think I'd rather have the ability to declare that all values of a particular interface type are guaranteed never to panic on comparison, even if it remains possible to accept the risk and try comparing interface values of a non-statically-guaranteed-comparable interface type.

@go101 We can't change the existing language, so it will continue to be possible to compare values of interface type which can possibly panic. That said, if we adopt this proposal, then programs that care can convert their interface types to be comparable, or embed comparable, and thus ensure that their interface comparisons can't panic. It would also, after a while, be possible to have vet or some other analyzer warn about comparisons of interface types that are not comparable.

I think this is a good change, but mostly because I see it as a step on the path to making any constraint useable as a normal interface value, which in turn opens the door to tagged union types. I know that using constraints as interface values has some wrinkles to work out (given type number interface{ int | uint }, var n number would be initially nil, rather than 0 [but what else could it be, since it's not specified as an int nor a uint yet?]), but it seems like the logical implication of the systems introduced in Go 1.18, so I'm not sure how long it can be excluded.

I fell at (nearly) the first hurdle at trying to make a generic sync.Map (details in #51384 ). More precisely my GenericMap[K,V] works fine except for things like GenericMap[interface{},bool] because interface{}/any do not implement comparable. So I support this proposal.

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

However, interface types do not in general implement the predeclared interface type comparable. An interface type only implements comparable if it is or embeds comparable.
[…]
But there is no way today to instantiate this Set type to create a general set that works for any (comparable) value. That is, you can't write Set[any], because any does not satisfy the constraint comparable.

TIL. This surprised me, I missed that discussion.

IMO that was a mistake and the answer to this problem is "interface types are comparable, so they should satisfy comparable".

Personally, I'm against this proposal for the reasons I mentioned when I last saw this idea being floated. Namely that embedding comparable becomes viral. For any interface-type:

Embedding comparable is bad. It disallows implementations with non-comparable values (e.g. http.HandlerFunc). In general, the author of an interface-types should have no opinion over what underlying type is used to implement it.
Not embedding comparable is bad. It disallows instantiating Set with it, even if the user of the interface knows all their actual values are comparable.

So you'll need both versions, in practice, for every interface. That's a color.

Moreover, the rules as stated don't actually seem to give meaningful additional guarantees about safety. For example, struct{ F any } would still implement comparable, AIUI. But its comparison is obviously not, in any way, safer than comparison of any. So, the claim that

~~That said, if we adopt this proposal, then programs that care can convert their interface types to be comparable, or embed comparable, and thus ensure that their interface comparisons can't panic.~~

~~doesn't seem to be actually true.~~ [edit] Well, when testing this, I realized that this isn't actually true - struct{any} does not implement comparable in Go 1.18, so this option is actually already the case.[/edit] Of course, we could extend the virality of comparable to struct-fields and array-elements. But that would also make the virality-problem above much worse. While it's not that unreasonable, to have to declare type ComparableType interface { reflect.Type; comparable } to instantiate Set[Type], if I want to use a struct with a reflect.Type field, I'd have to

Declare my own version of that struct, with the same fields, except all interfaces replaced with their comparable colors, potentially recursively.
Hope that definition stays in sync.
Presumably, manually write conversions between my comparable struct-flavor and the one I actually want (unless we do something like we did for struct-tags and allow conversions to ignore comparable coloring).
Convert back and forth, every time I want to put the struct I'm interested in into a Set or take it out from it.

That seems an unreasonable amount of effort, to me.

I understand why the decision was made, to have interface-types not satisfy comparable. It is confusing to be able to instantiate Set[any], even if the constraint is comparable. But confusion can be solved by education. We are living with the nil-pointers-in-interfaces-are-not-nil confusion, because it might be confusing, but the language is better for the semantics of it. The mess we are getting ourselves into with distinguishing comparable interface types from non-comparable ones, however, can't be solved by education. We are making it more cumbersome to use the language, to avoid having to explain to people that interface-types are in fact comparable. That seems a bad tradeoff.

Deciding that interface-types don't satisfy comparable was the conservative decision. We can't become more restrictive, but we can always become less restrictive. So starting out more restrictive until we learn more made sense. IMO, the arguments in favor of this issue really are arguments that we should exercise the option to become less restrictive and have interface-types satisfy comparable.

@Merovius

Is this proposal significantly different from the idea I floated here? #49587 (comment)

In that comment, I was under the impression that interface types would satisfy the comparable constraint. I guess I never actually tried it out!

Although I have a soft spot for this idea, I don't think it fits well with the language as is. reflect.Type is a good example - it's commonly used as a comparable value, but we can't currently use it as a comparable type parameter, which seems wrong. If this had all been done at the start, we'd probably have added comparable to the reflect.Type interface definition, but I don't believe that can be done now without breaking backward compatibility.

As a general rule, I think that if one is allowed to use == on a type outside generic code, one should be allowed to use it inside generic code.

That said, I would support a change to the language that's compatible with the goal expressed in the subject of this proposal: I think that values should be permitted to have type "comparable". I propose a much simpler rule: when used in a non-constraint context, comparable is a synonym for any.

Given:

type Set[E comparable] map[E]bool

it would be possible to write Set[comparable] but that would be exactly the same as Set[any].

The main benefit of doing this is that it would be possible to use a comparable constraint interface
as the parameter type too. For example given these definitions:

type MC interface {
    comparable
    M()
}

type MSet[T MC] map[T] bool

MSet[MC] would be a valid instantiation of MSet, but MSet[struct{_ [0]func(); MC] would not.

@Merovius

Embedding comparable is bad. It disallows implementations with non-comparable values (e.g. http.HandlerFunc). In general, the author of an interface-types should have no opinion over what underlying type is used to implement it.

For the record, I disagree with this. It's an important part of some interfaces that their implementations are comparable - that's part of the contract. reflect.Type is one example. Another is context.WithValue: if comparable as proposed here had been available at the time, we'd almost certainly have used it for that first argument.

@rogpeppe

@rogpeppe I agree that for some interfaces it's important. But for most it's counterproductive. By making interface types not satisfy comparable unless they embed it, we make most interface types impossible to use with generic types like Set even if that usage would be totally safe. And just because the author didn't want to require comparable, doesn't mean the user of an interface doesn't know all their values are.

That's kind of my point. comparable bisects the set of interface types into two universes, one with "types where it is considered essential that the interface is comparable" and one with "types where the author just wants to do some operations and doesn't care about the concrete type" - and a gray area in-between. In usage, they become incompatible. But there is overlap between them, which means duplication. The proposal text makes the argument:

But there is no way today to instantiate this Set type to create a general set that works for any (comparable) value. That is, you can't write Set[any], because any does not satisfy the constraint comparable. You can get a very similar effect by writing map[any]bool, but then all the functions like Union have to be written anew for this new version.

But I'd argue, we still need this duplication under the proposal, if we want to be able to use e.g. reflect.Type (or any other gray-area usage of an interface) in a Set. With the second being

// SetAny is a Set[T], which doesn't statically guarantee its values are comparable, for cases where
// you want to use an interface type which doesn't categorically require comparable, but where you know
// the values revelant for your case are. It panics at runtime, if you try adding non-comparable values to it.
type SetAny[T any] struct { m map[comparable]bool }
func (s SetAny[T]) Contains(v T) bool { return s.m[v.(comparable)] }
func (s SetAny[T]) Add(v T) { s.m[v.(comparable)] = true }
// etc

I also think that we need to keep current usage in mind. reflect.Type does not embed comparable and context.WithValue doesn't accept comparable and we can't really change that under compatibility rules. But that also means we can't have a Set[T comparable] which can take a reflect.Type. "If we had comparable from the beginning, we would've done that" is all well and good, but we didn't and we should consider how we go from here.

@rogpeppe

@rogpeppe Let me clarify: In my comment above, when I said "X is bad", i didn't mean "it is categorically bad, for all types", but "it has downsides". Both embedding and not embedding comparable has downsides, so no is strictly better, so we'll sometimes/often/usually/… need both.

I proposed that:

when used in a non-constraint context, comparable is a synonym for any.

For the record, that would imply that the following would be OK:

var x *comparable
var y *any = x

An alternative might be to consider comparable as a separate named type, as if it we defined as follows:

type comparable any

See #52614 for another take on this problem.

FWIW at this point, after all the discussion, I think I've fully come around to this proposal. I think my concerns are largely valid, but a) they happen relatively rarely, b) we might find ways to somewhat alleviate them and c) overall, after some transition pains, I think this leads to the most consistent language in the long term.

So, at least my personal opinion on this has changed.

It happens I've got here because I stumble on this issue while trying to refactor a simple code with generics, I cannot instantiate with a comparable type

type DupCount[T comparable] map[T]int

func (d DupCount[T]) Add(key T) {
	d[key]++
}

x := make(DupCount[comparable])

throw me an error

interface is (or embeds) comparable

This is the original code, been trying to replace the type check that prevents panic with a comparable constraint type and let the check happen on the compiler itself

type DupCount map[interface{}]int

func (d DupCount) Add(key interface{}) {
	if d.isAllowed(key) {
		d[key]++
	}
}

func (d DupCount) isAllowed(key interface{}) (ok bool) {
	allowedType := []reflect.Kind{
		reflect.Int,
		reflect.Int8,
		reflect.Int16,
		reflect.Int32,
		reflect.Int64,
		reflect.Uint,
		reflect.Uint8,
		reflect.Uint16,
		reflect.Uint32,
		reflect.Uint64,
		reflect.Float32,
		reflect.Float64,
		reflect.String,
	}

	for _, v := range allowedType {
		if v == reflect.ValueOf(key).Kind() {
			ok = true
			break
		}
	}
	return
}

x := make(DupCount)
x.Add(23452345)
x.Add("asdfasfd")

Is it possible for a Go team member to share the team's current thinking on this situ?

I'm wondering if you have an impression of a sensible path forward, or what would kind of consensus/changes would be needed in order to move forward?

I realise it's probably too late to get this resolved in 1.19, but it'd be great if we can get the info required to make sure we can get it figured out in time for 1.20.

@Merovius

It's fair to say that we're still deliberating this issue. One option might be to go back to the situation pre-Go 1.18 where ordinary interfaces did satisfy comparable, while non-comparable constraints did not. There's probably different ways we can get there. One way might be what @Merovius lined out in this comment a while back. Another approach might be to more closely match the definition to what the compiler actually implements with the existing restrictions, which is to treat method and type sets somewhat independently, and carve out a special case for non-type parameter interfaces. This may be a bit of a departure from what the spec says right now (interfaces are "just" type sets), but it wouldn't affect existing code.

Not much may happen in the next month or so as Gophers may be on vacation. But we do think it's important to solve this rather sooner than later, ideally for 1.20.

Retracting in favor of #56548.

It looks #56548 and this issue are for two different purposes.
#56548 is to use any interface type as type arguments of comparable constraints,
whereas this one is to let comparable be used as value types.

The two issues are two different approaches to solving the same problem.

Of course, we could also permit values to have type comparable for different reasons, but this issue was about doing it to address the #56548 problem. If we want to do it for other reasons we can open a new proposal.

Navigation Menu

Repository navigation

proposal: spec: permit values to have type "comparable" #51338

42 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

proposal: spec: permit values to have type "comparable" #51338

Description

Activity

ianlancetaylor commented on Feb 24, 2022

apparentlymart commented on Feb 24, 2022

zigo101 commented on Feb 24, 2022

apparentlymart commented on Feb 24, 2022

ianlancetaylor commented on Feb 25, 2022

earthboundkid commented on Feb 25, 2022

abligh commented on Feb 27, 2022

rsc commented on Mar 2, 2022

Merovius commented on Mar 3, 2022

rogpeppe commented on Mar 3, 2022

Merovius commented on Mar 3, 2022

Merovius commented on Mar 3, 2022

rogpeppe commented on Mar 3, 2022

42 remaining items

ianlancetaylor commented on Apr 29, 2022

Merovius commented on Apr 30, 2022

kh411d commented on May 20, 2022

billinghamj commented on Jul 5, 2022

griesemer commented on Jul 5, 2022

ianlancetaylor commented on Nov 3, 2022

zigo101 commented on Dec 8, 2022

ianlancetaylor commented on Dec 9, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions