go/types: considers non-identical constraint interfaces to be identical

[Merovius]

This is based on a recent golang-nuts thread.

The spec currently says

A named type is always different from any other type. Otherwise, two types are identical if their underlying type literals are structurally equivalent
[…]
Two interface types are identical if they define the same type set.

The definition of types sets is

• The type set of the empty interface is the set of all non-interface types.
• The type set of a non-empty interface is the intersection of the type sets of its interface elements.
• The type set of a method specification is the set of types whose method sets include that method.
• The type set of a non-interface type term is the set consisting of just that type.
• The type set of a term of the form ~T is the set of types whose underlying type is T.
• The type set of a union of terms t1|t2|…|tn is the union of the type sets of the terms.

By these definitions, interface{ int; m() } and interface{ string; m() } both have empty type sets (int and string have no methods, so neither has a method m()). The empty set is identical to itself, so these two interfaces should be considered identical.

go/types does not consider them identical though: https://go.dev/play/p/VfVgqmumilC

IMO the culprit here is the spec - it should not use type sets to define the identity of interfaces. Either way, I think the spec and go/types disagree here.

In practice this isn't really much of a problem. As far as I can tell these kinds of interfaces can't be used in any place where type identity matters. But we should consider this, if we ever want to allow constraint-interfaces as types.

[findleyr]

Thanks. go/types should agree with the spec, so this is either a go/types bug or the spec should be adjusted.

CC @griesemer

[griesemer]

Thanks for filing the issue. This is a known (but not properly documented) problem. I agree that it's not of any consequence for code right now as far as I can tell.

The correct fix is probably to compute type sets accurately by taking embedded element type sets properly into account. This also ties in with the problem of if and when to report a problem with an operator applied to a type parameter with an empty type set.

(If we adjust only the spec instead we may have a problem down the road: once we accurately compute all type sets, two interfaces that have identical, and possibly empty type sets should be considered identical, I think, even if they look different in the source. This is no different from the behavior of 1.17 interfaces where we look at method sets for identity, and not how those method sets were defined in the source.)

[griesemer]

Tentatively marking for 1.19, but we may not get to this before 1.20.

[zigo101]

Should an empty type set constraint implements any interface types?
Currently, it doesn't.

package main

func f1[T any](x T) {}
func f2[T comparable](x T) {}
func f3[T []int](x T) {}
func f4[T int](x T) {}

type C interface {
	[]int
	m()
}

func g[V C](v V) {
	f1(v) // okay
	f2(v) // error: V does not implement comparable
	f3(v) // okay
	f4(v) // error: V does not implement comparable
}

func main() {}

[Merovius]

@go101 The spec as is was written under the assumption that deciding if a type set is empty is prohibitively hard, I think. So, I think that's working as intended, as we can't really make decisions based on the idea of "this type set is empty, therefore any operation on the type should be allowed". That's also not a meaningful restriction, as writing such a function is nonsensical, as it can never be called.

[zigo101]

I understand that.

After re-checking the latest Go specification, I found three places meaningful for empty-type-set constraints:

A type T implements an interface I if

• ...
• T is an interface and the type set of T is a subset of the type set of I.

A generic function or type is instantiated by substituting type arguments for the type parameters. Instantiation proceeds in two steps:

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

Implementation restriction: A compiler need not report an error if an operand's type is a type parameter with an empty type set. Functions with such type parameters cannot be instantiated; any attempt will lead to an error at the instantiation site.

So I think the answer to my question is yes. Empty type set constraint implement any interface types. But the code in my last comment is not a bug.

[zigo101]

It would be better to change the wording in spec as

Implementation restriction: A compiler may or may not report an error ...

to make behaviors in the example in #51917 (comment) reasonable.

[Merovius]

@go101 it is undesirable to have the correctness of Go programs depend on the implementation. We either should require to report an error, or require not to report an error. That was an intentional decision made in #45346.

to make behaviors in the example in #51917 (comment) reasonable.

I don't understand what you mean. The behavior already seems completely reasonable to me.

[zigo101]

We either should require to report an error, or require not to report an error.

Now, ignoring the Implementation restriction paragraph mentioned above, gc sometimes report errors for the cases it should not, and sometimes doesn't report errors for the case it should.

[Merovius]

It would be helpful if you could explain why you think the compiler should not report errors in the case you constructed above. To me, the current behavior is entirely correct.

Note that the compiler does not ever complain about a type set being empty, for the reasons explained above. So, the change you suggest isn't necessary - the spec currently says the compiler doesn't need to complain about empty type sets and it does not.

It seems to me, that your argument about "the compiler should/should not complain about case X" always boils down to "the compiler needs to know that the type set is empty - but as complained above, there is a reason it doesn't know, currently. So, unless someone demonstrates that it can know, we should take it at face value that it can't and go from there.

[zigo101]

It would be helpful if you could explain why you think the compiler should not report errors in the case you constructed above

(By ignoring the Implementation restriction paragraph), as empty-type-set interfaces implement any interfaces, so a type parameter constrained by an empty-type-set interface may be used as type arguments and passed to any type parameters. So the example shown in #51917 (comment) should compile okay.

[Merovius]

@go101

(By ignoring the Implementation restriction paragraph)

Your suggestion is to touch that paragraph, therefore I don't see how you can possibly ignore it.

as empty-type-set interfaces implement any interfaces

So AIUI you are arguing that the spec should require the compiler to prove whether or not a type set is empty and make decisions based on that. See above as to why I don't think that's a good idea.

[zigo101]

Your suggestion is to touch that paragraph, therefore I don't see how you can possibly ignore it.

I mean "by ignoring the modified version of that paragraph" (aka, the "may or may not" version).
The current version doesn't cover the case in #51917 (comment).

The spec as is was written under the assumption that deciding if a type set is empty is prohibitively hard,

the compiler needs to know that the type set is empty - but as complained above, there is a reason it doesn't know, currently unless someone demonstrates that it can know

I don't think it is always hard. For many interface types, it is easily to determine that their type set are empty, either by compilers or by progrmamers. For example,

type C interface {
	[]int
	m()
}

[Edit]: BTW, in the example #51917 (comment), changing the above constraint to the following one will make the program compile okay.

type C interface {
	[]bool
	string
}

[Merovius]

@go101

I don't think it is always hard.

Of course not. But if we require the compiler to check, it has to be always easy.

[zigo101]

Honestly, I don't understand why it is not always easy.

[Merovius]

@go101 There is a proof that it is hard for an earlier version of the design. Since then some things have changed which mean that specific proof does not work anymore. But it shows that there is enough subtlety involved that we shouldn't rely on intuition. So until someone sits down and either proves that it's still hard, or proves that it's easy (most likely by writing an algorithm), I think we should assume it is hard. It's the safer assumption either way, it does not have a lot of downsides.

My intuition is, that it is likely still hard. And that if it isn't, the needed algorithm is likely too complex that I'd feel comfortable to put it into the spec. But I'm trained as a mathematician, so I know not to put too much stake into intuition either way.

[griesemer]

Things may change in the way we specify constraints/interfaces in the spec because we need to solve the comparable issue. There are multiple ways we could explain what the language permits and what it doesn't, without affecting backward-compatibility of existing code.

For instance, with the current restrictions in place, the type checker can treat methods, the type set specified by explicitly embedded non-interface types, and comparable embedding completely separately, there is no need to compute the "true" typeset as it is specified in the spec. What we see in this issue are artifacts caused by our simplified implementation, "the seams in the fabric".

As @Merovius points out, computing true type sets is likely expensive (or at the very least extremely subtle), so if we can we want to avoid it.

This all needs some dedicated time. Moving forward to 1.20.

[griesemer]

Moving to backlog. Existing code is not affected by this.