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

[ianlancetaylor]

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.

[ianlancetaylor]

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

CC @griesemer

[apparentlymart]

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]

[zigo101]

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

[apparentlymart]

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.

[ianlancetaylor]

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

[earthboundkid]

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.

[abligh]

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.

[rsc]

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

[Merovius]

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:

1. 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.
2. 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

1. Declare my own version of that struct, with the same fields, except all interfaces replaced with their comparable colors, potentially recursively.
2. Hope that definition stays in sync.
3. 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).
4. 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.

[rogpeppe]

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.

[Merovius]

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

[Merovius]

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

[rogpeppe]

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

[atdiar]

Is there really a problem appart from reflect.Type ?

How often do people use any potentially non-comparable interface values in Set and why would they not type assert to comparable before insertion?

Embedding comparable does not seem like an absolute necessity every time. The proposal as it stands would enable us to test the dynamic type.

[Merovius]

@atdiar

How often do people use any potentially non-comparable interface values in Set

The majority of interface values should be non-comparable. There are only two reasons I can think of, to embed comparable: 1. You accept it and need to put it in a map (or otherwise compare it) yourself and 2. it's effectively a closed sum (like reflect.Type or ast.Node) and you want to guarantee that all implementations are comparable.

Those are relatively rare. Most interface usages are to abstract over behavior, which shouldn't care about the dynamic type of its value.

why would they not type assert to comparable before insertion?

Of course, they can do that. That's what I said here, under "we still need this duplication". Of course the author of the Set type might chose not to do that duplication, putting the onus instead on the user of the type to do it. But avoiding that was one of the benefits given for this proposal and I just don't see that.

And, of course, the even larger problem of using struct-types with interface-fields still persists after that. That's not something that can even be solved with a type-assertion.

[bcmills]

I am still mulling over the implications, but it seems to me that the migration for interfaces to comparable is analogous to the migration to const values in C.

Like const, comparable sets up a situation in which new APIs are more restrictive than old ones, and in which values must be cast or converted from the less-restrictive to the more-restrictive type in order to use them.

With const, if you have a const value, and you know that a function does not modify it, you can cast away the const and pass the value as a non-const type. With comparable, if you have an interface value, and you know that the caller always passes a value that is actually comparable, you can (in many cases) explicitly convert it to a comparable type.

However, I'm not sure that the comparable conversion is even always an option for, say, struct types with fields of interface types. You may know that the contents of a given field are always comparable, but you can't convert the struct type to an equivalent comparable type because struct types are not interfaces. (The comparable interface conversion would lose the struct fields.)

[bcmills]

It seems to me that the virality problems could be at least partially addressed by defining “comparable” as a parameterized type rather than (just) an interface type. Its behavior would be roughly analogous to the convertible.To and assignable.To interface types I described in my assignability writeup.

Here I'll describe that type as Comparable[T any].

Comparable[T] as a built-in type

Comparable[T] is a type with the same representation as T that holds the subset of values of type T for which the == operation is guaranteed not to panic.

1. A variable of type T is convertible to Comparable[T]. If the value held by the variable is not comparable, the conversion panics. (This essentially front-loads the panic that could later result from the == operation.)
2. A variable of type Comparable[T] is convertible to T.
3. The zero-value of Comparable[T] is the zero-value of T (which is itself always comparable).
4. If T is an interface type, Comparable[T] implements T. However, T only implements Comparable[T] if T is or embeds a Comparable interface type, or if the underlying types of all types in type-set of T are comparable.
5. The method set of Comparable[T] is the method set of T.
6. (optional) If T not an interface type and is itself comparable, T is assignable to Comparable[T]. (That is: because the conversion to Comparable[T] cannot fail, it may be implicit.)
7. (optional) Because every Comparable[T] is a T, a variable of type Comparable[T] is assignable to T.
8. (optional) If T is a comparable composite type, then T is assignable to Comparable[T]

I have not yet assessed whether this definition of Comparable[T] is coherent as an interface type. (The zero-value in particular is odd, since it is not nil like the usual zero-value for an interface type.)

This definition of Comparable is more useful for integrating generic types, because it allows, say, struct types with a field of an interface type to be used as a type with a comparable bound. However, I'm not sure whether Comparable[T] replaces or merely augments the non-parameterized comparable bound.

[bcmills]

At the very least, Comparable[T] could be used to adapt existing interface types to generic APIs with comparable constraints:

type MapOf[K comparable, V any] map[K]V

func assign(m MapOf[Comparable[any], any], k, v interface{}) {
	kc := Comparable[any](v)
	m[kc] = v
}

The ergonomics still aren't great, but at least the conversion becomes possible to write at all.

[atdiar]

What if we just don't apply comparable in a retroactive fashion. For map keys, we in effect wouldn't retroactively constrain with comparable.

On the other hand, it would be possible to offer a wrapping interface to maps that uses the comparable constraint if such a stronger constraint was needed. (henceforth eliminating all non-comparable interfaces from the list of potential values for type arguments)

Meaning that in Go, in general, map keys would remain unconstrained (using any) leaving the usage of comparable for future APIs.

Edit: Perhaps that the current constraint is not yet well defined and does not equal to comparable.
Perhaps a new predicate isInterface and the overall constraint would be equal to: {comparable | isInterface} rather.

Edit2: needs something more to deal with struct fields...

[bcmills]

I guess, to summarize my comments above: defining comparable as an interface type as proposed seems coherent, but as far as I can tell does almost nothing to address the problems described in #51257.

Consider the implementation of the Union function for a Set type that allows arbitrary key-types checked at runtime:

type Set[E any] map[comparable]bool

func Union[E any](s1, s2 Set[E]) Set[E] {
	result := make(Set[E])
	for k, ok := range s1 {
		if ok {
			result[k.(comparable)] = true
		}
	}
	for k, ok := range s2 {
		if ok {
			result[k.(comparable)] = true
		}
	}
}

Now consider what happens if we instantiate above with the type:

type S struct {
	I any
}

As currently proposed in #51338 (comment), the above implementation of Union would always panic for the type Set[S].

The problem is that the type-assertion rule is too weak (emphasis mine):

A type assertion to comparable, as in x.(comparable), would succeed if the dynamic type of x is a comparable type.

---

In order for the Union implementation to be viable, that rule would need to be revised to:

A type assertion to comparable, as in x.(comparable), would succeed if an interface comparison on the dynamic value of x would not panic.

But if we make that revision, now we have a bit of a paradox: comparable is no longer a coherent interface type, because a variable of type comparable could contain a value of a type that does not implement the comparable interface!

[atdiar]

What if a struct required all its fields to implement comparable?
That was how I was envisioning comparable.

Isn't that the only way to be sure at compile-time that a composite type implements comparable?

[bcmills]

@atdiar

What if a struct required all its fields to implement comparable?

Because comparable does not exist as an interface type today, no existing struct type has such a requirement, and adding such a requirement to any struct type would be a breaking change. I don't see a viable migration path to there from where we are today — hence the analogy with const in C. 😩

[Merovius]

@bcmills

At the very least, Comparable[T] could be used to adapt existing interface types to generic APIs with comparable constraints:

ISTM this isn't substantially different than the proposal, except that the proposal spells the conversion as a type-assertion. i.e. it spells x.(comparable), instead of Comparable[T](x).

[rittneje]

Maybe the language spec should just change to define comparability for slices, maps, and functions?

1. Slices are equal if they have the same slice header.
2. Maps are equal if they are literally the same map, from the same call to make.
3. Funcs are never equal to other funcs, or even themselves.

Then all types in Go are "comparable". Consequently any and comparable are the same thing, so the latter is essentially deprecated. (Or maybe it takes on new life as an alias of any that more directly conveys your intent.)

I haven't thought through any negative implications this might have, but it sidesteps the issues mentioned throughout this thread about the two flavors of "comparable".

[Merovius]

@rittneje Non-comparable types where made non-comparable for a reason. I don't think generics change the equation on that significantly.

[ianlancetaylor]

Thanks for all the discussion. We've tried to address the most pressing issue on #52474. If that proposal is accepted, I will most likely close this one and recreate it in simpler form.

[gopherbot]

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

[ianlancetaylor]

See #52614 for another take on this problem.

[Merovius]

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.

[kh411d]

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")

[billinghamj]

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.

[griesemer]

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.

[ianlancetaylor]

Retracting in favor of #56548.

[zigo101]

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.

[ianlancetaylor]

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.