TL;DR

This is a restatement of proposal #52509 by @zephyrtronium. That issue has collected a lot of comments; starting anew will make it easier for readers to follow along again. The primary additional contributions in this issue are the formulation of the exact spec changes, a corresponding new API for go/types, and a discussion of these changes in the context of a future Go without the current implementation restrictions on interfaces. As a result, this issue is long, but the actually proposed change is small.

Background

The Go 1.18 release introduced the predeclared identifier comparable which denotes the set of all non-interface types that are comparable. More precisely, it is the set of (non-interface) types for which == and != are defined and for which these operations are guaranteed to not panic.

The types in the comparable type set do not correspond to the types of comparable operands: for instance, struct{ f any } is comparable but applying == on the field f may panic.

For clarity, in the following we use the term strictly comparable for the types in comparable, and spec-comparable for types of comparable operands. Strictly comparable types are spec-comparable, but not the other way around. Types that are not spec-comparable are simply not comparable.

Because in Go 1.18 and Go 1.19 constraint satisfaction means interface implementation, not all spec-comparable types satisfy the comparable constraint. The generic map type

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

cannot be instantiated with struct{ f any } for K, but the built-in map type permits that. This is a major handicap for the design of generic data structures. See #51257 for another example.

Over the course of this year, many ideas have been proposed to address this problem, while trying to preserve the rule that constraint satisfaction and interface implementation remain the same. Here's a (possibly incomplete) list of proposals for reference: #51338, #52474, #52531, #52614, #52624, #53734.

If we want any to satisfy comparable, then constraint satisfaction can't be the same as interface implementation. A non-comparable type T (say []int) implements any, but T does not implement comparable (T is not in comparable's type set). Therefore any cannot possibly implement comparable (the implements relation is transitive - we cannot change that). So if we want any to satisfy the comparable constraint, then constraint satisfaction can't be the same as interface implementation.

A pre-Go1.18 implementation of the compiler did not treat interface implementation and constraint satisfaction the same, which led to initial confusion because of the resulting inconsistency (see #50646). Eventually the inconsistency was considered an implementation bug (in hindsight this was done without enough consideration of all the implications). With more experience it appears that this inconsistency made it easier to use generic Go with commonly used Go types.

@zephyrtronium's #52509 and this issue propose that we go back to this pre-Go1.18 implementation of constraint satisfaction.

Proposal

We change the spec to use a different rule for constraint satisfaction than for interface implementation: we want spec-comparable types to satisfy comparable; i.e., we want to be able to use any type for which == is defined even if it may not be strictly comparable.

Specifically, in the language spec section on Instantiations, we propose to change the 2nd rule from (old):

After substitution, each type argument must implement the constraint (instantiated, if necessary) of the corresponding type parameter. Otherwise instantiation fails.

to (new):

After substitution, each type argument must satisfy the constraint (instantiated, if necessary) of the corresponding type parameter. Otherwise instantiation fails.

We also add a new paragraph defining what "satisfy" means:

A type T satisfies a constraint interface 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.

With this change, constraint satisfaction matches interface implementation but also contains an exception for spec-comparable types. This exception permits the use of interfaces as type arguments which require strict comparability.

This is the entire proposal.

Observations

1. The proposed change expands the set of types that satisfy a constraint, therefore no existing programs are invalidated and the proposal is fully backward-compatible. See the section on Implementation below for when the feature becomes available.

2. The spec has various implementation restrictions: interfaces that are not basic may only be used as type constraints, or as elements of other interfaces used as constraints. They cannot be the types of values or variables, or components of other, non-interface types. Because of these restrictions, if the type argument T is a (non-type parameter) interface, it must be a basic interface. Thus, we can ignore the case of type-constrained interfaces (such as interface{ ~[]int }) which can only hold non-comparable types. For the same reason, if T is a non-interface type with an interface field (such as struct{ f F } where F is an interface), F must be a basic interface. In other words, we don't need to complicate the rules to explicitly disallow such types for T: any interface that is or appears in a (non-type parameter) type argument must be a basic interface and therefore is spec-comparable.

3. The spec has additional implementation restrictions in place: comparable and interfaces containing methods may not appear as terms in a union (with more than one term). Because of these restrictions, if comparable appears in an interface (or an embedded element), it can be "factored out to the top"; the same is true for methods. More precisely, constraint interfaces can always be written in one of two forms: interface{ comparable; E } or interface{ U; E }, where E stands for all the interface's methods (if any), and U denotes a union of non-interface types (if any). (An interface of the form interface{ comparable; U; E } can always be reduced to the form interface{ U'; E } by eliminating all non-strictly-comparable terms from U).

4. For interface{ U; E } constraints, constraint satisfaction is the same as interface implementation: nothing changes. For a type T to satisfy the constraint, it must be in the union and satisfy all the methods, if any.

5. For interface{ comparable; E } constraints, constraint satisfaction is looser: we still expect a type argument T to implement all the methods E, but we allow any T which is spec-comparable, even if it is not strictly comparable. This is not statically type-safe and must be remedied with a run-time check for ==.

6. Because the new rule invalidates static type safety, the definition of strictly comparable is not quite correct anymore: == on an operand of a strictly comparable type parameter type may in fact panic at run-time. To be able to separate the various kinds of comparability, strictly comparable now more precisely denotes the set of types for which == and != are defined and for which these operations won't panic if type safety was never broken through the instantiation of a (strictly) comparable type parameter with a spec-comparable type argument.

7. If a type parameter P is spec-comparable, it is always strictly comparable (but see the previous observation). Therefore, if a type parameter is used as a type argument for a constraint of the form interface{ comparable; E }, the rule that P must "only" be spec-comparable doesn't weaken any static type guarantees because P will be strictly comparable.

8. The pre-Go 1.18 implementation, before the inconsistency documented in spec: document/explain which interfaces implement comparable #50646 was reported, matched the proposed rules.

Eventually we may want to remove the existing implementation restrictions. This will also require a generalization of the rule for constraint satisfaction. To ensure backward compatibility, the proposed rule here should match a future, more general rule adjusted for the current implementation restrictions. But at the very least, the proposed rule should not permit more programs now than might be permitted with a more general rule for constraint satisfaction. See the appendix for an attempt at such a generalization.

Examples

Currently, any does not implement the comparable constraint. With the proposed change any will be permitted as type argument for comparable: comparable can be written as interface{ comparable; E } and thus the new rule applies, and any is spec-comparable and implements E (where E is the empty interface in this case).

Currently, the type parameter P in the type parameter list

[P interface{ comparable; fmt.Stringer }]

cannot be instantiated with the type S

type S struct {
	data any
}

func (S) String() string

because S is not strictly comparable. With the proposed change, S must only be spec-comparable (which it is) and implement fmt.Stringer (which it does).

More examples

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

func _[P any, Q comparable]() {
	var (
		_ map[func()]string        // invalid with current and new rules: func() is not comparable
		_ map[struct{ f P }]string // invalid with current and new rules: P is not comparable
		_ map[struct{ f Q }]string // valid: key type is strictly comparable

		_ mymap[any, string]                // currently invalid, valid with new rules: any supports ==
		_ mymap[struct{ f any }, string]    // currently invalid, valid with new rules: type of f supports ==
		_ mymap[struct{ f func() }, string] // invalid with current and new rules: f is not comparable
		_ mymap[struct{ f int }, string]    // valid: key type is strictly comparable
		_ mymap[struct{ f P }, string]      // invalid with current and new rules: P is not comparable
		_ mymap[struct{ f Q }, string]      // valid: key type is strictly comparable
	)
}

Implementation

The proposal requires minor changes to the typechecker:

1. We have already implemented this alternative semantics at tip so that we can experiment. The new compiler flag -altcomparable enables the new behavior (disabled by default):

go tool compile -altcomparable <file.go>      // applied to a single file
go build -gcflags=-altcomparable <pkg path>   // applied to a package
etc.

If the proposal is accepted for Go version 1.nn, we will replace this flag with a version check that enables the new behavior starting with Go 1.nn.

2. Clients of go/types need to be able to check for constraint satisfaction, which is now slightly different from interface implementation. We cannot add a flag to the existing types.Implements function without breaking backward-compatibility. Instead, we propose to add the following exported function:

// Satisfies reports whether type V satisfies the constraint interface T.
//
// The behavior of Satisfies is unspecified if V is Typ[Invalid] or an uninstantiated
// generic type.
func Satisfies(V Type, T *Interface) bool

3. We may also want to provide a variant of types.Comparable that implements the notion of strict comparability. We can wait with this until a clear need arises.

All these changes are trivial (the internal implementations exist, they just need to be exported).

If this proposal is accepted in time, it could become effective with the Go 1.20 release.

Related spec issues

1. The current definition of the type set of the predeclared type comparable is incorrect in the spec. The definition is as follows:

The predeclared interface type comparable denotes the set of all non-interface types that are comparable. Specifically, a type T implements comparable if:

• T is not an interface type and T supports the operations == and !=; or
• T is an interface type and each type in T's type set implements comparable.

The first rule (T supports the operations == and !=) also includes types (such as structs) which may not be strictly comparable (see the structs used in the examples above). The rule needs to be amended to exclude types for which == may panic.

2. The definition of comparable operands in the spec is missing a dedicated rule for operands of type parameter type. Without it, type parameters (whose underlying types are their constraint interfaces) fall into the category of spec-comparable interface values. This is incorrect. A type parameter-specific rule needs to be added to this section.

Both these spec corrections should be made irrespective of whether this proposal is accepted or not.

Appendix

In a hypothetical future version of Go ("FutureGo") where generalized interfaces may be used as ordinary types, the constraint satisfaction rules must be suitably extended and expressed in terms of type sets. @ianlancetaylor proposes the following FutureGo rules:

Given a (constraint) interface C, we define two type sets S1 and S2 as follows:

• S1 is the type set of C computed in the usual way, except that wherever comparable appears in C
  it is treated as the set of all (spec-)comparable types (not just the strictly comparable types); and
• S2 is the type set of C computed in the usual way, except that wherever comparable appears in C
  it is treated as the set of all types, any.

Given these special type sets S1 and S2, we can define general constraint satisfaction as follows:

A type T satisfies a constraint interface C if

• T is not an interface type, and T is an element of type set S1; or
• T is a (non-type parameter) interface type, the type set of T is a subset of the type set S2,
  and the intersection of the type set of T with the type set S1 is not empty; or
• T is a type parameter and T implements C.

(The case for type parameters can be folded into the case of non-interface types, but for the following discussion it is clearer to handle it separately.)

If T is not an interface (or type parameter) type, it is not hard to see why the respective sub-rule makes sense: instead of only accepting strictly comparable types for comparable, the use of the type set S1 permits any spec-comparable type.

If T is an interface type, we also want to accept it as a type argument for comparable: more precisely, any interface type, irrespective of its type set, supports == and thus is spec-comparable (we could say that non-basic interfaces don't support == by default, but that's an separate discussion). Effectively this means that comparable is the same as any in this case, hence the type set S2. However, we (probably) want to exclude interface types with type sets for which we can prove that == can't possibly succeed. For instance, interface{ ~[]int } is spec-comparable (all interfaces support ==, but see the comment on that above), but its type set only contains non-comparable types: comparing operands of type interface{ ~[]int } will always panic. The intersection of the type set of such interfaces with the type set S1 will be empty (if it were not empty, the interface would contain at least one spec-comparable type and so == might always happen to succeed in a concrete application). This explains the second part of the rule for interfaces.

Finally, if T is a type parameter, nothing changes and we can simply ignore this case below.

To make sure we remain forward-compatible with FutureGo, i.e., that these generalized constraint satisfaction rules do not restrict our current, limited proposal, we need to show that our current proposal doesn't permit more types for a constraint than the FutureGo rules.

We can do this by applying the current implementation restrictions to the FutureGo constraint satisfaction rules. With those restrictions in place, from the Observations section we know that constraint interfaces can appear in only two (canonical) forms:

a) interface{ comparable; E }; or
b) interface{ U; E }

where E stands for all the methods in the constraint (if any), and U denotes a union of non-interface types (if any). Therefore, the respective type set S1 is either

S1a which is the type set of interface{ comparable; E } with comparable denoting all spec-comparable types; or
S1b which is the type set of interface{ U; E } (unchanged).

Similarly, the type set S2 is either

S2a which is the type set of interface{ E }; or
S2b which is the type set of interface{ U; E } (unchanged).

Now we can look at the type argument T and how the generalized rules apply:

If T is not an interface type, per the generalized rules, T must be an element of S1. Therefore, T must either be an element of S1a, or S1b. If the former is true, T must be spec-comparable and implement the methods E - this corresponds to the our proposed exception for interface satisfaction. If the latter is true, T is simply an element of the type set of the constraint, which means T implements the constraint. This corresponds to the non-exceptional part of the proposed rule for constraint satisfaction.

If T is a (non-type parameter) interface type, with the implementation restrictions in place, T must be a basic interface. Per the generalized rules, the type set of T must be a subset of S2a and the intersection of T's type set and S1a must not be empty, or the type set of T must be a subset of S2b and the intersection of T's type set and S1b must not be empty. If the former is true, T implements the methods E, and because T is a basic interface it is also spec-comparable. This corresponds to the proposed exception for constraint satisfaction. If the latter is true, T simply implements the constraint, which again corresponds to the non-exceptional part of the proposed rule for constraint satisfaction.

In summary, if we apply the current implementation restrictions to FutureGo, the FutureFo constraint satisfaction rules reduce to the rules proposed in this issue. This provides some insurance that the proposed rules won't cause problems in FutureGo.