title: All your comparable types date: 2023-02-17 by:
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!
If you‘re confused, you’ve come to the right place. Consider the valid map declaration
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
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:
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
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.
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.
Go 1.18 introduced generics and, with that, type parameters as a new language construct.
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.
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.
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
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.
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
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.)
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
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.
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.
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.
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.
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.
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 ==.
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?
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[[]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.
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.
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.
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.
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:
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. 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).
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?
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.
But this is also the problem because it prevents us from using non-strictly comparable types as type arguments for 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.
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:
A type
Tsatisfies a constraintCif
TimplementsC; orCcan be written in the forminterface{ comparable; E }, whereEis a basic interface andTis comparable and implementsE.
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).
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) }
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).
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. 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.
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!
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. 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]
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.
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:
type T struct { … }
We want to assert that T is strictly comparable. It's tempting to write something like:
// 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:
func _[P T]() { _ = isComparable[P] // P supports == only if T is strictly comparable }
Here is a passing and failing playground example illustrating this mechanism.
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. 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.
Thank you!