Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

spec: document/explain which interfaces implement comparable #50646

Closed
bobg opened this issue Jan 16, 2022 · 40 comments
Closed

spec: document/explain which interfaces implement comparable #50646

bobg opened this issue Jan 16, 2022 · 40 comments
Assignees
Milestone

Comments

@bobg
Copy link

@bobg bobg commented Jan 16, 2022

What version of Go are you using (go version)?

$ go version
go version go1.18beta1 linux/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE="on"
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/bobg/.cache/go-build"
GOENV="/home/bobg/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/bobg/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/bobg/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/bobg/sdk/go1.18beta1"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/bobg/sdk/go1.18beta1/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="go1.18beta1"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/bobg/go/src/github.com/bobg/modver/go.mod"
GOWORK=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build3923542930=/tmp/go-build -gno-record-gcc-switches"

What did you do?

https://go.dev/play/p/S-ijx-XOlu8?v=gotip

var (
	anyType        = types.Universe.Lookup("any").Type()
	comparableType = types.Universe.Lookup("comparable").Type()
)
fmt.Println(types.AssignableTo(comparableType, anyType))
fmt.Println(types.AssignableTo(anyType, comparableType))

What did you expect to see?

true
false

That is, I (naively?) expected the same check that prevents me using non-comparable types as map keys to tell me that I cannot assign a value of an unconstrained type to a variable of a comparable type.

What did you see instead?

true
true

@bobg
Copy link
Author

@bobg bobg commented Jan 16, 2022

A little more context: I am updating github.com/bobg/modver to be generics-aware. This package can compare two versions of a Go module and tell whether a major, minor, or patchlevel version-number bump is needed, according to semver rules.

If two versions of a Go object differ only in the constraint on a type parameter, what should the result be? The answer depends on the type set implied by the constraint.

If the two type sets are identical, the result should be None. If the older type set is a strict subset of the newer type set, that is a backward-compatible change and the result should be Minor. Otherwise it's an incompatible change and the result should be Major.

I had hoped to use types.Identical and types.AssignableTo to distinguish these cases, but if I can't, what's the best way to do it instead? Must I write my own type-set-comparing logic, or is there something in the stdlib I can use?

Thanks...

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jan 16, 2022

CC @griesemer @findleyr

In the current language no variable can have the type comparable, so at least at present it doesn't necessarily make sense to call AssignableTo. On the other hand, Implements does make sense, but it also returns true for both directions.

The question you want to ask seems like a reasonable one but I don't know whether the go/types package supports answering that question yet.

@ianlancetaylor ianlancetaylor added the NeedsInvestigation label Jan 16, 2022
@ianlancetaylor ianlancetaylor added this to the Go1.18 milestone Jan 16, 2022
@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 17, 2022

This is simply a bug and needs to be fixed. Thanks for the report.

@griesemer griesemer self-assigned this Jan 17, 2022
@griesemer griesemer changed the title go/types: AssignableTo does not distinguish between any and comparable go/types, types2: AssignableTo does not distinguish between any and comparable Jan 17, 2022
@griesemer griesemer added NeedsFix and removed NeedsInvestigation labels Jan 17, 2022
@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 24, 2022

When we check whether a (a value of) type V can be assigned to a (variable of) interface type T (types.AssignableTo(V, T)), because T is an interface, we need to check if V implements T. In this specific case we need to check if the empty interface (any) implements comparable. The comparable interface is implemented by any type that supports == and !=. (Even) in non-generic Go, == and != can be used with a variable of interface type (even the empty interface!), it's just that we might get a run-time panic if the dynamic type doesn't support comparison with == and !=. Thus, any interface (including any) supports == and !=, which leads to the (admittedly counter-intuitive at first) conclusion that any actually implements comparable and thus any is assignable to comparable.

If comparable is used as (or embedded in a constraint), it is therefore ok to instantiate the respective type parameter with an arbitrary interface (that satisfies all the other aspects of the constraint), because comparison is always supported by all interfaces. However, when running that instantiated code, we may get a run-time panic if the dynamic type of the interface does not support comparison (as we do in regular Go).

In short, this is not a bug but simply a consequence of existing rules.

Leaving this issue open for now so we can close it with a CL that adds some more tests.

@griesemer griesemer added Documentation and removed NeedsFix labels Jan 24, 2022
@griesemer griesemer changed the title go/types, types2: AssignableTo does not distinguish between any and comparable go/types, types2: document that all interfaces implement comparable Jan 24, 2022
@gopherbot
Copy link

@gopherbot gopherbot commented Jan 25, 2022

Change https://golang.org/cl/380654 mentions this issue: cmd/compile: all interfaces implement comparable (add tests)

@griesemer griesemer changed the title go/types, types2: document that all interfaces implement comparable spec: document that all interfaces implement comparable Jan 25, 2022
@bobg
Copy link
Author

@bobg bobg commented Jan 25, 2022

any actually implements comparable

OK, I can buy that (though I don't love it).

But there's something that distinguishes any from comparable, otherwise the compiler would not report "invalid map key type K (missing comparable constraint)" for this code snippet.

type X[K, V any] map[K]V

Is that distinction surfaced in the stdlib? What is the right way to detect it? Will an explicit call to types.Comparable do the job? Or can there be other pairs of constraint types, not involving comparable, with a symmetrical Implements relationship but an asymmetrical "Satisfies" relationship? Do we need / can we get types.Satisfies?

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 25, 2022

In this code snippet, the type of K is a type parameter - the operations == and != are only available on K if it is comparable: type parameters are a new kind of type with their own new rules - operators on type parameters are only available if their constraints explicitly say so. The spec requires that == and != are defined on the key types for maps. If you make K comparable, it's still possible to instantiate X with an arbitrary interface.

types.Comparable will tell you for a type parameter if it is comparable.

There won't be a types.Satisfies, satisfying a constraint means exactly implementing the constraint interface; i.e., the function to use is types.Implements (possibly after instantiation of the constraint).

What is missing in the in-progress spec is not extra rules for this, just a sentence highlighting the fact that all interfaces implement comparable, as a consequence of pre-existing rules.

@go101
Copy link

@go101 go101 commented Jan 25, 2022

It is some weird to view any (as a value type) and comparable (as a type constraint) as the same thing.

It is not a problem to view any (as a type constraint) and comparable as the same thing.

Maybe the types package should add a function types.Subset(C1, C2 *types.Interface) function, for constraints.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jan 25, 2022

Nobody is saying that any and comparable are the same thing. They are not the same as a type constraint, and if comparable is ever accepted as the type of a variable, they will not be the same as a variable type.

However, values of type comparable (if such values were permitted) could be assigned to variables of type any (because any value can be assigned to a variable of type any). And values of type any could be assigned to variables of type comparable (because any is an interface type, and all interface types are comparable). This doesn't mean that they are the same; it means that they can each be assigned to the other.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jan 25, 2022

To put it another way, this code, which instantiates a type parameter of type comparable with the type argument any, is valid.

func Eq[T comparable](a, b T) bool {
	return a == b
}

func EqAny(x, y any) bool {
	return Eq(x, y)
}

gopherbot pushed a commit that referenced this issue Jan 25, 2022
For #50646.

Change-Id: I7420545556e0df2659836364a62ce2c32ad7a8b1
Reviewed-on: https://go-review.googlesource.com/c/go/+/380654
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
@go101
Copy link

@go101 go101 commented Jan 26, 2022

And values of type any could be assigned to variables of type comparable (because any is an interface type, and all interface types are comparable).

This listens some weird. An interface value may never box another interface value.
When an any value is assigned to a comparable, the dynamic value of the any value is actually assigned to the comparable.
If the assignment is allowed, then will a panic occur when the dynamic is incomparable?

@go101
Copy link

@go101 go101 commented Jan 26, 2022

func Eq[T comparable](a, b T) bool {
	return a == b
}

func EqAny(x, y any) bool {
	return Eq(x, y)
}

This example is legal because any and comparable in it are two different things. any is a value type, which satisfies comparable, which is a type constraint.

On the contrary, the following code should not work:

func Eq(a, b comparable) bool {
	return a == b
}

func EqAny(x, y any) bool {
	return Eq(x, y)
}

I understand that a type constraint might be directly used as a value type (sum type) later.
But it is really weird that a subset constraint (here any) implements a superset constraint (here comparable).

Edit: here "subset" and "superset" mean rule set. If they mean type set, then comparable is the subset.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jan 26, 2022

On the contrary, the following code should not work:

I disagree.

This code works today:

func EqIface(x, y any) bool {
    return x == y
}

That seems basically the same as the version that you wrote.

@go101
Copy link

@go101 go101 commented Jan 26, 2022

Different from a method set, a comparable just has an operator set.
I don't understand why an operator set could get special treatments over method sets.

type Comparable interface {
	==(another Comparable) bool
}

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jan 26, 2022

Yes, we could have gone that way in the language. But we didn't.

(Part of the reason we didn't is that the interface definition you wrote permits using the == method with any type that implements Comparable. But the actual == operator does not permit that; it only permits using the exact same type (or, in some cases, an untyped constant).)

@go101
Copy link

@go101 go101 commented Jan 26, 2022

I agree my above operator method definition is not perfect. It is just used to make the explanation.

@go101
Copy link

@go101 go101 commented Jan 26, 2022

And if comparable may be used as a value type and any implements it.
What should the following program print? true or false?
By the current rules, two answers are both reasonable.

var x any = []int{}
var c, ok = x.(comparable)
print(ok)

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jan 26, 2022

By the rules of type assertions, I think your code would have to print false.

You're right that it's an interesting case.

@go101
Copy link

@go101 go101 commented Jan 26, 2022

In the current implementation rule, if any implements comparable, compilers are able to evaluate ok as true, at compile time.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 27, 2022

Maybe this is not valid for constraints? For example, the type sets of the any and comparable constraints both include all interface types.

We say that interface any is implemented by all interface types because the type sets of all interface types are subsets of the type set of any. That is not the quite the same as saying that an interface type is an element of the type set of any. Interface types are never elements of type sets. If they were, we would get into all kinds of logic problems. Type sets (== interfaces) consist of concrete (non-interface) types only.

For instance, it's not possible to store an interface (i.e., a value of interface type) in another interface (i.e., in a variable of interface type): what is stored is the dynamic type of one interface in the variable of the other interface. That is the manifestation of the fact that an interface cannot be an element of the typeset of another interface. Analogously, type assertions and type switches always test the dynamic type of an interface variable - the dynamic type is always a concrete type.

Constraints are interfaces. The only difference (for now) is that we permit more powerful type set descriptions for interfaces that are used as constraints only. Perhaps, in a future version, we can eliminate this difference as well.

It may all be a bit confusing because we call an interface also a type in Go. But interfaces have always behaved differently from non-interface types. Interfaces are abstract types which define sets of types. That was true before generics (they described the sets of types implementing their methods) and it's true with generics with the more fine-grained way of describing type sets. Non-interface types are concrete types which define a single type. We must not mix sets of types with single types. It's clear if we talk about abstract vs concrete types - two different things. But at some point we need to tie the things together in the language and we call them all types. Perhaps the spec can be clearer in this respect.

@bobg
Copy link
Author

@bobg bobg commented Jan 27, 2022

We must not mix sets of types with single types

Shades of Russell and Whitehead.

I wish to re-raise a question from an earlier comment:

Regardless of the outcome of this discussion - whether or not we stick with the idea that any implements comparable - clearly the difference between them is not solely a panic at runtime. There is a compile-time distinction too.

For the purposes of updating modver (the reason I opened this issue), I am interested to know the exact right formula for detecting that compile-time distinction at runtime. Maybe types.Implements and types.AssignableTo alone can't do the job, but disambiguating with types.Comparable can.

But!

Can there be other type constraints that are "special" like comparable, in the sense that they have a symmetric Implements relationship with some other type despite describing a different type set? And if so, what's the right formula in that case?

PS: This is a super-interesting discussion, thanks all.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jan 27, 2022

@griesemer

In retrospect, the original assessment may have been correct, and this is simply a (long-standing) bug. When we check if an interface implements comparable, we perhaps should not rely on the fact that == and != is permitted on all interfaces, even the ones that are not explicitly comparable. If we change that, this apparent contradiction goes away: any wont implement comparable anymore.

I'm not sure what this means in practice.

I think I agree that interface types aren't members of type sets. Nevertheless, we can pass interface types as type arguments for type parameters. An interface type can be used as a type argument if it satisfies the constraint. If the constraint includes any concrete types then the interface type can't satisfy the constraint, by definition. If the constraint includes any methods, then the interface type must include the same methods with the same signatures. If the constraint does not include comparable, that does not affect whether the interface type satisfies it. If the constraint includes comparable and the interface type also includes comparable, then the interface type satisfies the constraint. That all seems reasonably clear.

So the only question is: if the constraint includes comparable, and the interface type does not include comparable, should the interface type satisfy that constraint?

The argument that it should satisfy the constraint is that all interface types are in fact comparable.

The argument that it should not satisfy the constraint is based on type sets. I'm not sure that the current spec clearly states the rule for when a value of interface type may be assigned to a variable of some different interface types, or, equivalently, the rule for when one interface type implements a different interface type. One way to write that rule would be to say that interface I1 implements interface I2 if the type set of I1 is a (possibly improper) subset of the type set of I2. Clearly the type set of comparable is a subset of the type set of any, so comparable implements any. Clearly the type set of any is not a subset of the type set of comparable, so any does not implement comparable. So if we follow this rule we can't instantiate a constraint of any with the interface type comparable (in fact the only interface type that comparable implements is comparable itself).

So if use the type set argument, then I guess that most of what I've been saying above is simply wrong. I'm not sure I'm completely convinced, but it seems like a plausible argument.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 27, 2022

I believe that we must rely on the type set (and previously method set) property of interfaces to determine whether a type implements an interface. I also agree that this is not clearly spelled out in the forthcoming spec, but it should be.

There were also (at least) three compounding bugs in the implementation that lead to the odd behavior: interface identity didn't check for the comparable property, the interface implements test used the wrong predicate for testing comparability, and AssignableTo didn't use the interface implements test that was updated to deal with type sets. With these fixed (CLs forthcoming), the API functions Comparable, Implements, an AssignableTo now behave as expected (note that Comparable must return true for all non-type parameter interfaces for historic reasons). With these changes, any won't implement comparable anymore, which seems much more sensible.

Stepping back for a moment: Had we introduced a notation (some special mark) for interfaces for which we expect to use == and != in the beginning of Go, all this would have been a non-issue: clearly one wouldn't be able to compare two interfaces that don't support comparison. Such a mark would also have made it impossible to assign a non-comparable value to non-comparable interfaces, etc. Instead we relied on a run-time test, at considerable implementation cost, for that matter. This is something we cannot change. But generic code will now be type-safe with respect to this.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 27, 2022

@bobg You should be able to use Interface.IsComparable to tell whether an interface expects comparable types (either because comparable was embedded or because the type set contains only types that are comparable).

@gopherbot
Copy link

@gopherbot gopherbot commented Jan 27, 2022

Change https://golang.org/cl/381434 mentions this issue: cmd/compile/internal/types2: better error reporting for Checker.implements

@gopherbot
Copy link

@gopherbot gopherbot commented Jan 27, 2022

Change https://golang.org/cl/381435 mentions this issue: cmd/compile/internal/types2: use Checker.implements in operand.assignableTo

@griesemer griesemer removed the NeedsInvestigation label Jan 27, 2022
gopherbot pushed a commit that referenced this issue Jan 28, 2022
This CL copies (and adjusts as needed) the logic for error reporting
from operand.assignableTo to Checker.implements in the case of a missing
method failure and assignment to an interface pointer.

Preparation for using Checker.implements in operand.assignableTo
rather than implementing the same logic twice.

This also leads to better errors from Checker.implements as it's
using the same logic we already use elsewhere.

For #50646.

Change-Id: I199a1e02cf328b222ae52c10131db871539863bf
Reviewed-on: https://go-review.googlesource.com/c/go/+/381434
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
gopherbot pushed a commit that referenced this issue Jan 28, 2022
Now that we have the detailed error reporting in Checker.implements
we don't need it anymore in operand.assignableTo and can simply call
Checker.implements. This also more directly matches the spec.

For #50646.

Change-Id: Ic44ced999c75be6cc9edaab01177ee0495147ea1
Reviewed-on: https://go-review.googlesource.com/c/go/+/381435
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
@gopherbot
Copy link

@gopherbot gopherbot commented Jan 29, 2022

Change https://golang.org/cl/381896 mentions this issue: spec: add section on comparable constraint

gopherbot pushed a commit that referenced this issue Jan 31, 2022
- Use the correct predicate in Checker.implements: for interfaces
  we cannot use the API Comparable because it always returns true
  for all non-type parameter interface types: Comparable simply
  answers if == and != is permitted, and it's always been permitted
  for interfaces. Instead we must use Interface.IsComparable which
  looks at the type set of an interface.

- When comparing interfaces for identity, we must also consider the
  whether the type sets have the comparable bit set.

With this change, `any` doesn't implement `comparable` anymore. This
only matters for generic functions and types, and the API functions.
It does mean that for now (until we allow type-constrained interfaces
for general non-constraint use, at some point in the future) a type
parameter that needs to be comparable cannot be instantiated with an
interface anymore.

For #50646.

Change-Id: I7e7f711bdcf94461f330c90509211ec0c2cf3633
Reviewed-on: https://go-review.googlesource.com/c/go/+/381254
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 31, 2022

This is now fixed in the type checker. What is outstanding is the documentation in the spec. Not a release blocker anymore.

@tinytina2021
Copy link

@tinytina2021 tinytina2021 commented Feb 1, 2022

@griesemer "... This is something we cannot change."
Why not? We can now still introduce a new notation like =! for this case that was not legal Go pre 1.18 while all previously working Go programs would still compile and 1.18+ programs will still remain fully backward compatible.

gopherbot pushed a commit that referenced this issue Feb 1, 2022
For #50646.
Fixes #50791.

Change-Id: I8fec25ae3f0280c5b5a778011d23842b886ba79e
Reviewed-on: https://go-review.googlesource.com/c/go/+/381896
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
@griesemer
Copy link
Contributor

@griesemer griesemer commented Feb 1, 2022

@tinytina2021 I'm not sure I follow: we cannot change the behavior of == and != for interfaces as that would invalidate existing programs. But we can have different rules for type parameters, which is what we're doing. I'm not sure how introducing =! (and what about the negation of =!?) would help or why it would be useful.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Feb 1, 2022

The implementation of AssignableTo has been fixed and https://golang.org/cl/381896 documents the behavior or comparable. Closing.

@billinghamj
Copy link

@billinghamj billinghamj commented Feb 18, 2022

@griesemer Just to flag, the change so that any no longer counts as comparable makes it difficult to write generic code in some quite common situations

It kinda seems like this change has been made a little last-minute and without particularly widespread discussion, but may have a fairly significant impact on people's ability to use generics in Go

For example, when using golang-set, it's pretty reasonable that you might want to make a set containing any comparable type - e.g.:

	NewSetFromSlice[any](
		[]any{
			1,
			2,
			3,
			"test",
		},
	)

The code cannot be written as NewSetFromSlice[comparable]([]comparable{ - this results in the error interface is (or embeds) comparable compiler(ErrorCode(142))

So as far as I can see, it is no longer possible to write this code at all - though maybe I'm missing something obvious?

If you're firm that any will never implement comparable, maybe comparable should be allowed in non-type constraint interfaces?

Honestly, this seems significant enough to be a release blocker, although it probably could be fixed later without a breaking change

Edit: opened as a new issue - #51257 - as I appreciate this one has been closed for a couple of weeks now

@griesemer
Copy link
Contributor

@griesemer griesemer commented Feb 23, 2022

I think the correct answer here is to allow comparable as a regular type. See #51257 for more.

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 23, 2022

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

9 participants