Everything You Need to Know About All Comparable Types

On February 1 we released our latest Go version, 1.20, which included a few language changes. Here we’ll discuss one of those changes: the predeclared comparable type constraint is now satisfied by all comparable types. Surprisingly, before Go 1.20, some comparable types did not satisfy comparable! comparable comparable types comparable If you’re confused, you’ve come to the right place. Consider the valid map declaration var lookupTable map[any]string var lookupTable map[any]string where the map’s key type is any (which is a comparable type). This works perfectly fine in Go. On the other hand, before Go 1.20, the seemingly equivalent generic map type any comparable type type genericLookupTable[K comparable, V any] map[K]V type genericLookupTable[K comparable, V any] map[K]V could be used just like a regular map type, but produced a compile-time error when any was used as the key type: any var lookupTable genericLookupTable[any, string] // ERROR: any does not implement comparable (Go 1.18 and Go 1.19) var lookupTable genericLookupTable[any, string] // ERROR: any does not implement comparable (Go 1.18 and Go 1.19) Starting with Go 1.20 this code will compile just fine. The pre-Go 1.20 behavior of comparable was particularly annoying because it prevented us from writing the kind of generic libraries we were hoping to write with generics in the first place. The proposed maps.Clone function comparable maps.Clone func Clone[M ~map[K]V, K comparable, V any](m M) M { … } func Clone[M ~map[K]V, K comparable, V any](m M) M { … } can be written but could not be used for a map such as lookupTable for the same reason our genericLookupTable could not be used with any as key type. lookupTable genericLookupTable any In this blog post, we hope to shine some light on the language mechanics behind all this. In order to do so, we start with a bit of background information. Type parameters and constraints Go 1.18 introduced generics and, with that, type parameters as a new language construct. type parameters type parameters In an ordinary function, a parameter ranges over a set of values that is restricted by its type. Analogously, in a generic function (or type), a type parameter ranges over a set of types that is restricted by its type constraint. Thus, a type constraint defines the set of types that are permissible as type arguments. type constraint type constraint set of types Go 1.18 also changed how we view interfaces: while in the past an interface defined a set of methods, now an interface defines a set of types. This new view is completely backward compatible: for any given set of methods defined by an interface, we can imagine the (infinite) set of all types that implement those methods. For instance, given an io.Writer interface, we can imagine the infinite set of all types that have a Write method with the appropriate signature. All of these types implement the interface because they all have the required Write method. io.Writer Write implement Write But the new type set view is more powerful than the old method set one: we can describe a set of types explicitly, not only indirectly through methods. This gives us new ways to control a type set. Starting with Go 1.18, an interface may embed not just other interfaces, but any type, a union of types, or an infinite set of types that share the same underlying type. These types are then included in the type set computation: the union notation A|B means “type A or type B”, and the ~T notation stands for “all types that have the underlying type T”. For instance, the interface underlying type type set computation A|B A B ~T T interface { ~int | ~string io.Writer } interface { ~int | ~string io.Writer } defines the set of all types whose underlying types are either int or string and that also implement io.Writer’s Write method. int string io.Writer Write Such generalized interfaces can’t be used as variable types. But because they describe type sets they are used as type constraints, which are sets of types. For instance, we can write a generic min function min func min[P interface{ ~int64 | ~float64 }](x, y P) P func min[P interface{ ~int64 | ~float64 }](x, y P) P which accepts any int64 or float64 argument. (Of course, a more realistic implementation would use a constraint that enumerates all basic types with an < operator.) int64 float64 < As an aside, because enumerating explicit types without methods is common, a little bit of syntactic sugar allows us to omit the enclosing interface{}, leading to the compact and more idiomatic syntactic sugar omit the enclosing interface{} func min[P ~int64 | ~float64](x, y P) P { … } func min[P ~int64 | ~float64](x, y P) P { … } With the new type set view we also need a new way to explain what it means to implement an interface. We say that a (non-interface) type T implements an interface I if T is an element of the interface’s type set. If T is an interface itself, it describes a type set. Every single type in that set must also be in the type set of I, otherwise T would contain types that do not implement I. Thus, if T is an interface, it implements interface I if the type set of T is a subset of the type set of I. implement implement T I T T I T I T I T I Now we have all the ingredients in place to understand constraint satisfaction. As we have seen earlier, a type constraint describes the set of acceptable argument types for a type parameter. A type argument satisfies the corresponding type parameter constraint if the type argument is in the set described by the constraint interface. This is another way of saying that the type argument implements the constraint. In Go 1.18 and Go 1.19, constraint satisfaction meant constraint implementation. As we’ll see in a bit, in Go 1.20 constraint satisfaction is not quite constraint implementation anymore. Operations on type parameter values A type constraint does not just specify what type arguments are acceptable for a type parameter, it also determines the operations that are possible on values of a type parameter. As we would expect, if a constraint defines a method such as Write, the Write method can be called on a value of the respective type parameter. More generally, an operation such as + or * that is supported by all types in the type set defined by a constraint is permitted with values of the corresponding type parameter. Write Write + * For instance, given the min example, in the function body any operation that is supported by int64 and float64 types is permitted on values of the type parameter P. That includes all the basic arithmetic operations, but also comparisons such as <. But it does not include bitwise operations such as & or | because those operations are not defined on float64 values. min int64 float64 P < & | float64 Comparable types In contrast to other unary and binary operations, == is defined on not just a limited set of predeclared types, but on an infinite variety of types, including arrays, structs, and interfaces. It is impossible to enumerate all these types in a constraint. We need a different mechanism to express that a type parameter must support == (and !=, of course) if we care about more than predeclared types. == predeclared types == != We solve this problem through the predeclared type comparable, introduced with Go 1.18. comparable is an interface type whose type set is the infinite set of comparable types, and that may be used as a constraint whenever we require a type argument to support ==. comparable comparable == Yet, the set of types comprised by comparable is not the same as the set of all comparable types defined by the Go spec. By construction, a type set specified by an interface (including comparable) does not contain the interface itself (or any other interface). Thus, an interface such as any is not included in comparable, even though all interfaces support ==. What gives? comparable comparable types By construction comparable any comparable == Comparison of interfaces (and of composite types containing them) may panic at run time: this happens when the dynamic type, the type of the actual value stored in the interface variable, is not comparable. Consider our original lookupTable example: it accepts arbitrary values as keys. But if we try to enter a value with a key that does not support ==, say a slice value, we get a run-time panic: lookupTable == lookupTable[[]int{}] = "slice" // PANIC: runtime error: hash of unhashable type []int lookupTable[[]int{}] = "slice" // PANIC: runtime error: hash of unhashable type []int By contrast, comparable contains only types that the compiler guarantees will not panic with ==. We call these types strictly comparable. comparable == strictly comparable Most of the time this is exactly what we want: it’s comforting to know that == in a generic function won’t panic if the operands are constrained by comparable, and it is what we would intuitively expect. == comparable Unfortunately, this definition of comparable together with the rules for constraint satisfaction prevented us from writing useful generic code, such as the genericLookupTable type shown earlier: for any to be an acceptable argument type, any must satisfy (and therefore implement) comparable. But the type set of any is larger than (not a subset of) the type set of comparable and therefore does not implement comparable. comparable genericLookupTable any any comparable any comparable comparable var lookupTable GenericLookupTable[any, string] // ERROR: any does not implement comparable (Go 1.18 and Go 1.19) var lookupTable GenericLookupTable[any, string] // ERROR: any does not implement comparable (Go 1.18 and Go 1.19) Users recognized the problem early on and filed a multitude of issues and proposals in short order (#51338, #52474, #52531, #52614, #52624, #53734, etc). Clearly this was a problem we needed to address. #51338 #52474 #52531 #52614 #52624 #53734 The “obvious” solution was simply to include even non-strictly comparable types in the comparable type set. But this leads to inconsistencies with the type set model. Consider the following example: comparable func f[Q comparable]() { … } func g[P any]() { _ = f[int] // (1) ok: int implements comparable _ = f[P] // (2) error: type parameter P does not implement comparable _ = f[any] // (3) error: any does not implement comparable (Go 1.18, Go.19) } func f[Q comparable]() { … } func g[P any]() { _ = f[int] // (1) ok: int implements comparable _ = f[P] // (2) error: type parameter P does not implement comparable _ = f[any] // (3) error: any does not implement comparable (Go 1.18, Go.19) } Function f requires a type argument that is strictly comparable. Obviously it is ok to instantiate f with int: int values never panic on == and thus int implements comparable (case 1). On the other hand, instantiating f with P is not permitted: P’s type set is defined by its constraint any, and any stands for the set of all possible types. f f int int == int comparable f P P any any This set includes types that are not comparable at all. Hence, P doesn’t implement comparable and thus cannot be used to instantiate f (case 2). And finally, using the type any (rather than a type parameter constrained by any) doesn’t work either, because of exactly the same problem (case 3). P comparable f any any Yet, we do want to be able to use the type any as type argument in this case. The only way out of this dilemma was to change the language somehow. But how? any Interface implementation vs constraint satisfaction As mentioned earlier, constraint satisfaction is interface implementation: a type argument T satisfies a constraint C if T implements C. This makes sense: T must be in the type set expected by C which is exactly the definition of interface implementation. T C T C T C But this is also the problem because it prevents us from using non-strictly comparable types as type arguments for comparable. comparable So for Go 1.20, after almost a year of publicly discussing numerous alternatives (see the issues mentioned above), we decided to introduce an exception for just this case. To avoid the inconsistency, rather than changing what comparable means, we differentiated between interface implementation, which is relevant for passing values to variables, and constraint satisfaction, which is relevant for passing type arguments to type parameters. Once separated, we could give each of those concepts (slightly) different rules, and that is exactly what we did with proposal #56548. comparable interface implementation constraint satisfaction #56548 The good news is that the exception is quite localized in the spec. Constraint satisfaction remains almost the same as interface implementation, with a caveat: spec A type T satisfies a constraint C if T implements C; or C can be written in the form interface{ comparable; E }, where E is a basic interface and T is comparable and implements E. A type T satisfies a constraint C if T C T implements C; or C can be written in the form interface{ comparable; E }, where E is a basic interface and T is comparable and implements E. T implements C; or T C C can be written in the form interface{ comparable; E }, where E is a basic interface and T is comparable and implements E. C interface{ comparable; E } E T comparable E The second bullet point is the exception. Without going too much into the formalism of the spec, what the exception says is the following: a constraint C that expects strictly comparable types (and which may also have other requirements such as methods E) is satisfied by any type argument T that supports == (and which also implements the methods in E, if any). Or even shorter: a type that supports == also satisfies comparable (even though it may not implement it). C E T == E == comparable We can immediately see that this change is backward-compatible: before Go 1.20, constraint satisfaction was the same as interface implementation, and we still have that rule (1st bullet point). All code that relied on that rule continues to work as before. Only if that rule fails do we need to consider the exception. Let’s revisit our previous example: func f[Q comparable]() { … } func g[P any]() { _ = f[int] // (1) ok: int satisfies comparable _ = f[P] // (2) error: type parameter P does not satisfy comparable _ = f[any] // (3) ok: satisfies comparable (Go 1.20) } func f[Q comparable]() { … } func g[P any]() { _ = f[int] // (1) ok: int satisfies comparable _ = f[P] // (2) error: type parameter P does not satisfy comparable _ = f[any] // (3) ok: satisfies comparable (Go 1.20) } Now, any does satisfy (but not implement!) comparable. Why? Because Go permits == to be used with values of type any (which corresponds to the type T in the spec rule), and because the constraint comparable (which corresponds to the constraint C in the rule) can be written as interface{ comparable; E } where E is simply the empty interface in this example (case 3). any comparable == any T comparable C interface{ comparable; E } E Interestingly, P still does not satisfy comparable (case 2). The reason is that P is a type parameter constrained by any (it is not any). The operation == is not available with all types in the type set of P and thus not available on P; it is not a comparable type. Therefore the exception doesn’t apply. P comparable P any is not any == not P P comparable type But this is ok: we do like to know that comparable, the strict comparability requirement, is enforced most of the time. We just need an exception for Go types that support ==, essentially for historical reasons: we always had the ability to compare non-strictly comparable types. comparable == Consequences and remedies We gophers take pride in the fact that language-specific behavior can be explained and reduced to a fairly compact set of rules, spelled out in the language spec. Over the years we have refined these rules, and when possible made them simpler and often more general. We also have been careful to keep the rules orthogonal, always on the lookout for unintended and unfortunate consequences. Disputes are resolved by consulting the spec, not by decree. That is what we have aspired to since the inception of Go. One does not simply add an exception to a carefully crafted type system without consequences! One does not simply add an exception to a carefully crafted type system without consequences! So where’s the catch? There’s an obvious (if mild) drawback, and a less obvious (and more severe) one. Obviously, we now have a more complex rule for constraint satisfaction which is arguably less elegant than what we had before. This is unlikely to affect our day-to-day work in any significant way. But we do pay a price for the exception: in Go 1.20, generic functions that rely on comparable are not statically type-safe anymore. The == and != operations may panic if applied to operands of comparable type parameters, even though the declaration says that they are strictly comparable. comparable == != comparable A single non-comparable value may sneak its way through multiple generic functions or types by way of a single non-strictly comparable type argument and cause a panic. In Go 1.20 we can now declare var lookupTable genericLookupTable[any, string] var lookupTable genericLookupTable[any, string] without compile-time error, but we will get a run-time panic if we ever use a non-strictly comparable key type in this case, exactly like we would with the built-in map type. We have given up static type safety for a run-time check. map There may be situations where this is not good enough, and where we want to enforce strict comparability. The following observation allows us to do exactly that, at least in limited form: type parameters do not benefit from the exception that we added to the constraint satisfaction rule. For instance, in our earlier example, the type parameter P in the function g is constrained by any (which by itself is comparable but not strictly comparable) and so P does not satisfy comparable. We can use this knowledge to craft a compile-time assertion of sorts for a given type T: P g any P comparable T type T struct { … } type T struct { … } We want to assert that T is strictly comparable. It’s tempting to write something like: T // isComparable may be instantiated with any type that supports == // including types that are not strictly comparable because of the // exception for constraint satisfaction. func isComparable[_ comparable]() {} // Tempting but not quite what we want: this declaration is also // valid for types T that are not strictly comparable. var _ = isComparable[T] // compile-time error if T does not support == // isComparable may be instantiated with any type that supports == // including types that are not strictly comparable because of the // exception for constraint satisfaction. func isComparable[_ comparable]() {} // Tempting but not quite what we want: this declaration is also // valid for types T that are not strictly comparable. var _ = isComparable[T] // compile-time error if T does not support == The dummy (blank) variable declaration serves as our “assertion”. But because of the exception in the constraint satisfaction rule, isComparable[T] only fails if T is not comparable at all; it will succeed if T supports ==. We can work around this problem by using T not as a type argument, but as a type constraint: isComparable[T] T T == T func _[P T]() { _ = isComparable[P] // P supports == only if T is strictly comparable } func _[P T]() { _ = isComparable[P] // P supports == only if T is strictly comparable } Here is a passing and failing playground example illustrating this mechanism. passing failing Final observations Interestingly, until two months before the Go 1.18 release, the compiler implemented constraint satisfaction exactly as we do now in Go 1.20. But because at that time constraint satisfaction meant interface implementation, we did have an implementation that was inconsistent with the language specification. We were alerted to this fact with issue #50646. issue #50646 We were extremely close to the release and had to make a decision quickly. In the absence of a convincing solution, it seemed safest to make the implementation consistent with the spec. A year later, and with plenty of time to consider different approaches, it seems that the implementation we had was the implementation we wanted in the first place. We have come full circle. As always, please let us know if anything doesn’t work as expected by filing issues at https://go.dev/issue/new. https://go.dev/issue/new Thank you! Robert Griesemer Robert Griesemer Photo by La-Rel Easter on Unsplash La-Rel Easter Unsplash This article is available on The Go Blog under a CC BY 4.0 DEED license. This article is available on The Go Blog under a CC BY 4.0 DEED license. The Go Blog The Go Blog