proposal: Go 2: allow interfaces to require comparable types

[jimmyfrasche]

Generally you needn't worry about what types satisfy an interface, only that they do.

Sometimes, you always need the value in the interface to be comparable. For example, if it is required to be a map key.

This has to be specified outside the type system in documentation or implicitly by panicing if the invariant is broken.

Sometimes you need to start requiring the value be comparable, which is a breaking change, but it is hard to communicate it to users.

I propose all interface types (not interface values) have a bit, that, if set, requires values assigned to them to be comparable.

Embedding an interface with this bit set in another interface propagates. This allows this invariant to be checked at compile time. It is conceptually similar to including a == "method" in the method set.

There are a few ways to handle this, syntactically.

A special sigil in the interface declaration like

type comparable interface=={}

A sigil applied to a named or unnamed interface, allowing named interfaces to be marked after the fact. For example, #fmt.Stringer, #interface{}, etc.

Another possibility is a predeclared type, comparable, that is interface{} with this bit set. It can be used as-is or embedded in another interface like

type ComparableStringer interface {
  comparable
  fmt.Stringer
}

[bradfitz]

It's not a terrible request, despite all the downvotes. I suspect many people don't like your proposed syntax. (For future proposals, you might want to stay clear of the syntax minefield and just describe what you're looking to express in the language, instead of how.)

[jimmyfrasche]

Fair enough. I'll give it another shot.

If you have type X map[interface{}]interface{} it's clear from the definition that the keys should be comparable.

It's less clear when you have something like

type X struct {
  // . . . 
  m map[interface{}]interface{}
}

any methods that add or look up values that came from the user need to specify that the value must be comparable, even if there are no other restrictions on it.

With the draft proposal for contracts you can specify that a type parameter have == but that only helps in the case when you have homogeneous keys. There are still use-cases for heterogeneous keys and cases where generics don't apply. Further, the contact can express that the type has == but all interfaces have == and I don't see a way to express a contract such as "this type is comparable or it is an interface with a comparable dynamic type" so if you need to instantiate a generic container with an interface you're back to == panicing sometimes.

This is useful with or without generics.

Without generics, you could make the key type on sync.Map a comparable empty interface to enforce the implicit constraint at compile time. With generics, you could instantiate it with a comparable interface for the key type to get the same static guarantees as if you used a non-interface type.

Even with generics, context.WithValue is going to use interface{} for its key type. Currently it uses reflect to assert comparability at runtime but with comparable interfaces it could make the restriction static. To be fair you could also do this, though:

func SafeWithValue(type T Comparable)(parent context.Context, key T, val interface{}) context.Context {
  return context.WithValue(parent, interface{}(key), val)
}

But it's not always possible to do that in general.

Also to be fair, this came up in my attempt to define generics solely with interfaces as the constraint on types even though I wasn't fussed about the other operators. It's necessary there but useful on its own.

[dwlnetnl]

I know it’s valid code to use an empty interface as a map key, but I as far as I know it is discouraged. As an example: what happens if there is int(42) and uint(42) as keys in the map. I don’t know of the top of my mind what the language spec says what should happens if you use a untyped constant 42 as a key in a subscript expression. To me at least it’s unclear and potentially confusing.

Because of this I am would be careful to implement the proposal as it is stands. That said I agree with @bradfitz that it’s not a terrible request.

[ianlancetaylor]

It seems to me to be hard to justify giving this special treatment to comparable but not to, say, ordered. (I get that comparable is a bit special because it is a feature required for a map key, but still.)

[jimmyfrasche]

This is for letting any interface, empty and nonempty be able to assert this property. And there are cases like context that doesn't use maps but needs to assert comparability over an empty interface.

FWIW, the untyped constant 42 has the default type int so it is the same as int(42).

[jimmyfrasche]

@ianlancetaylor you can already == interfaces but not < them. And many more types have == than have <.

All this would do is guarantee that == never panics by disallowing you from putting incomparable types in.

[jimmyfrasche]

Not to get myself in too much trouble by bringing up syntax again but reflecting on this paragraph from the contracts draft proposal

It is unclear how to represent operators using interface methods. We considered syntaxes like +(T, T) T, but that is confusing and repetitive. Also, a minor point, but ==(T, T) bool does not correspond to the == operator, which returns an untyped boolean value, not bool. We also considered writing simply + or ==. That seems to work but unfortunately the semicolon insertion rules require writing a semicolon after each operator at the end of a line. Using contracts that look like functions gives us a familiar syntax at the cost of some repetition. These are not fatal problems, but they are difficulties.

I think that

interface {
  (==)
}

would work. You can't use parens like that in interfaces and it would thwart the issue with semicolon insertion rules. While foreign to Go, similar syntax is used in some languages to use an operator in a context where a function is required. It would also let this limited proposal be accepted while leaving the door open for adding the likes of (<) and (+) later.

[jba]

Assuming we go with the syntax where comparable is an interface, what happens here:

func f(x, y comparable) bool { return x == y }
...
var a int
var b float64
f(a, b)

[jimmyfrasche]

It's an interface. It follows the standard rules for interface ==. The difference is that you can't do

var _ comparable = func(){}

[bcmills]

@jimmyfrasche I think the point @jba is getting at is that the existence of == today doesn't tell you the types of its operands. (The fact that it's an operator means that it isn't attached to a specific type, and the types of either operand can be somewhat relaxed.)

https://play.golang.org/p/lW2uHZmEcJN

[jba]

@jimmyfrasche It looks like you're saying that my example would result in a runtime panic. This contradicts what you said above, which is that this interface would

guarantee that == never panics.

I like your syntax

interface {
  (==)
}

because it really shows how this is just like

interface {
   M(int)
}

But the difference is that the language guarantees the type-safety of the call M(3) when the receiver implements that interface. It can't do that in the case of (==).

[jimmyfrasche]

I'm not saying it should change how interface comparison works.

in

func f(x, y comparable) bool { return x == y }
var a int
var b float64
f(a, b)

f returns false because a and b are different types. It works the same as if the signature were x, y interface{}.

The only difference from an ordinary interface is that you cannot put incomparable types into it, so

f(a, func() {})

would fail compile at time because func() {} is not a comparable type.

[jba]

Sorry, my mistake. I forgot == was special.

But this idea won't work for other operators. Re-do my example for interface { (<) }, for instance.

[jimmyfrasche]

I know it won't work with other operators without a lot of changes. I was just noting that the (==) syntax would allow making those changes later in a manner consistent with this proposal.

[myitcv]

@mvdan and I were discussing the old thread https://groups.google.com/d/msg/golang-nuts/aoevY2konbU/zG8EloYWCQAJ.

I'll save creating yet another issue (unless folks feel I'm just adding noise here/it's a sufficiently separate point) to note that I think we should also give a compile-time error for the following:

package main

import (
        "fmt"
)

type S struct {
        f func()
}

func (s S) Impl() {}

var _ I = S{}

type I interface {
        Impl()
}

func main() {
        m := make(map[I]bool)
        m[S{}] = true  // this will always result in a run-time panic
        fmt.Println(m)
}

As @ianlancetaylor noted in that thread, this would likely be a language change.

[jimmyfrasche]

That certainly sounds like a language change (a more generic one would be that implementations may reject programs with expressions that always non-explicitly panic, so that every case needn't be added to the language spec).

It would catch some errors but not that many since it only take a single level of indirection to invalidate the check. A static analyzer that specialized in this class of errors could probably find way more than a compiler could, like m[f()] where f() always returns an interface containing an incomparable value.

[vincent-163]

Sorry for the noise, I made a mistake in my last comment (just deleted).

There is another interesting point that might need discussion though. If comparable interfaces were implemented, will we force interfaces in map keys to be comparable? This is backward-incompatible but another idea is to automatically convert interfaces in map keys to comparable ones.

Since this will force a type assertion when converting a regular variable to a comparable variable, this might be another solution for @myitcv 's idea, where the compile-time error occurs due to an invalid interface assignment.

[jimmyfrasche]

Disallowing non-comparable interfaces from being map keys entirely would be a huge breaking change and make transitioning quite difficult since a lot of code would need to be updated all at once.

[fenollp]

Disallowing non-comparable interfaces from being map keys entirely would be a huge breaking change [...]
What kind of code makes use of non-comparables as map keys? How can this be usable?

Maybe we should augment the comparable idea to build more interfaces into the language?

1. All slice types (of non-empty types) could have a language-generated implementation of sort.Interface where Less relies on X being comparable:

type X ... // Some user type -- neither struct{} nor func()
type Xs []X

// Xs implements sort.Interface -- added by compiler
func (p Xs) Len() int           { return len(p) }
func (p Xs) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p Xs) Less(i, j int) bool { return p[i].Less(p[j]) }

// X implements some kind of comparable -- added by user
func (l X) Less(r X) bool { return l < r }

1. All built-in types that are usable today with one of the 6 ==, <=, ... could implement the corresponding type Equaler interface { (==)(bool) }, ... in the language (with again a special case on empty types). When in addition to the above, we'd get a usable sort.Sort on []int, []string, []float64, ... all slices of built-in non-empty types. Then there's more than just weak ordering...

2. Iterators could come in:

type Iter interface {
	NewIter() Iterable
}

// Iterable looks a lot like database/sql.Rows
type Iterable interface {
	Next() bool
	Scan(...interface{}) error
}

type XsIterator struct {
	pos int
	xs  Xs
}

func (xs Xs) NewIter() Iterable { return &XsIterator{pos: -1, xs: xs} }
func (it *XsIterator) Next() bool {
	it.pos++
	return it.pos < len(it.xs)
}

var (
	errScanWithoutNext   = errors.New("iterable: Scan called without calling Next")
	errNeedsExactly01Arg = errors.New("expected 1 destination argument")
	errNilPtr            = errors.New("expected non-nil destination pointer")
	errWrongDestType     = errors.New("unexpected destination value type")
)

func (it *XsIterator) Scan(xs ...interface{}) error {
	if it.pos < 0 {
		return errScanWithoutNext
	}
	if len(xs) != 1 {
		return errNeedsExactly01Arg
	}
	switch dest := xs[0].(type) {
	case *X:
		if dest == nil {
			return errNilPtr
		}
		*dest = it.xs[it.pos]
	default:
		return errWrongDestType
	}
	return nil
}

func main() {
	ss := Xs{"foo", "bar"}
	sort.Sort(ss)
	fmt.Println(ss)
	i := 0

	for it := ss.NewIter(); it.Next(); i++ {
		var x X
		if err := it.Scan(&x); err != nil {
			panic(err)
		}
		fmt.Println(">>>", x)
	}
}

1. Now if builtin types (and collections of them) implemented the Scanner interface in the language, we'd get for ranges, map, filtermap, fold:

type Scanner interface {
	Scan(interface{}) error
}

// Iterable looks a lot like database/sql.Rows
type Iterable interface {
	Next() bool
	Scan(...Scanner) error
}

func (x X) Scan(dest interface{}) error {
	switch dst := dest.(type) {
	case *X:
		if dst == nil {
			return errNilPtr
		}
		*dst = x
		return nil
	default:
	}
	return errWrongDstType
}

func (it *XsIterator) Scan(xs ...Scanner) error {
	if it.pos < 0 {
		return errScanWithoutNext
	}
	if len(xs) != 1 {
		return errNeedsExactly01Arg
	}
	return it.xs[it.pos].Scan(xs[0])
}

Surely there's been previous discussions about having such interfaces in the language and their implementations declared/cached when the type is created?
Does anyone have any links?
What was the general feeling regarding this idea? Was there some push back due to performance concerns?

Thanks

[ianlancetaylor]

Having the language define methods for types has been discussed. One concern can be seen in your Scanner interface: you wind up having to use empty interface types, and so you lose the benefits of static typing.

More generally, this is the language space of generics. We should not highjack this specific and focused issue into a general discussion of generics.

[jimmyfrasche]

Closing as duplicate of #51338 which is more up to date

[ianlancetaylor]

@jimmyfrasche Thanks, sorry for forgetting about this issue.