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

Comments

@bobg
Copy link

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

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 Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jan 16, 2022
@ianlancetaylor ianlancetaylor added this to the Go1.18 milestone Jan 16, 2022
@griesemer
Copy link
Contributor

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 The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Jan 17, 2022
@griesemer
Copy link
Contributor

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 The path to resolution is known, but the work has not been done. 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

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

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

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

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

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 commented Jan 26, 2022

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

@gopherbot
Copy link

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

@griesemer griesemer removed the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. 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

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

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

@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

@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

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

@billinghamj
Copy link

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

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

@gopherbot
Copy link

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

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

No branches or pull requests

9 participants