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

cmd/compile/internal/types2: make type inference independent of function argument order #43056

Open
mdempsky opened this issue Dec 7, 2020 · 7 comments
Assignees
Labels
generics NeedsDecision TypeInference
Milestone

Comments

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Dec 7, 2020

In the test case at https://go2goplay.golang.org/p/gEl3-egETB2, F(i, j) is accepted, but F(j, i) is not. Both of F's value parameters have identical type, so the behavior here should be consistent (either both accepted, or both rejected).

Based on my understanding from Robert (that type inference requires arguments to have identical type to the parameter, not mere assignability to it), I suspect the correct, consistent behavior is for both to be rejected.

Some more tests at https://go2goplay.golang.org/p/aVaXxBbK1j5. I plan to write a program to exhaustively generate test cases.

(My motivation for looking into this was adding type parameter support to rf, for type-polymorphic rewriting rules: rsc/rf#6)

/cc @griesemer @ianlancetaylor

@mdempsky mdempsky added the NeedsInvestigation label Dec 7, 2020
@griesemer griesemer self-assigned this Dec 7, 2020
@griesemer griesemer added this to the Go1.17 milestone Dec 7, 2020
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Dec 7, 2020

I don't see why the type parameters have identical type. One is type I. The other is type interface{ Equal(I) bool }. A named type is not identical to an unnamed type. What am I missing?

@mdempsky
Copy link
Member Author

@mdempsky mdempsky commented Dec 7, 2020

The calls' value arguments i and j have different types; but F's value parameters are a and b, which are both declared as type T. (There's only one type parameter in the simplified test case: T.)

@griesemer
Copy link
Contributor

@griesemer griesemer commented Dec 7, 2020

I agree that either both of these calls of F should succeed or fail as the only difference is the order of the arguments.

Unfortunately, we currently have an asymmetry in the unification algorithm: If one of the involved types is a defined type (here I) and the other one is not (here interface{ Equal(I) bool }), w/o any further steps, unification would fail right away (the two types are different). In cases like these we take the underlying type of the named type I, so interface{ Equal(I) bool } and try to unify that with the type of j which is also interface{ Equal(I) bool } and everything is fine.

Since we started with I (first argument), the inferred type is I. As a result we get the invocation F[I](i, j); I which satisfies the constraint, and both i and j can be assigned to a I parameter.

In the 2nd case we start with interface{ Equal(I) bool } (type of j). We use the same rule as above, unification succeeds, but the inferred type is now interface{ Equal(I) bool }. As a result we get the invocation F[interface{ Equal(I) bool}](j, i). This type does not satisfy the constraint because the constraint's Equal method is (after substitution) Equal(interface{Equal(I) bool}) bool which is not equal to Equal(I) bool, and instantiation fails.

In summary, unification produces the following calls:

F[I](i, j)
F[interface{ Equal(I) bool}](j, i)

It seems reasonable to postulate that if we enter unification with an underlying type of a named type to make it succeed, the inferred type should be the underlying type (here interface{Equal(I) bool}). We probably should make that change to make the algorithm symmetric.

But then both calls in this example would fail (because instantiation fails).

Alternatively, maybe the interface I and interface{Equal(I) bool} should be considered identical recursively, which is essentially #8082. Or maybe #8082 but only for unification purposes.

This problem only occurs with interfaces because those are the only types for which we can provide methods in the type literal; for all other types, we need a defined type to attach methods.

There may be other work-arounds and changes to the inference algorithm that make this work "as expected". But is does seems accepting #8082 would solve this problem for interfaces.

@griesemer griesemer added Thinking and removed NeedsInvestigation labels Dec 7, 2020
@gopherbot
Copy link

@gopherbot gopherbot commented Dec 14, 2020

Change https://golang.org/cl/276692 mentions this issue: [dev.typeparams] go/types: import unify.go and infer.go from dev.go2go

gopherbot pushed a commit that referenced this issue Dec 15, 2020
After review, the only non-superficial change was to delegate the call
to under(...) to structuralType. Otherwise, update a few stale comments:
 + correct indices in the documentation for tparamsList
 + update smap->substMap in a few places
 + update type parameter syntax in a couple places

I've spent a good amount of time reviewing this code, and it
fundamentally LGTM (though I wish we didn't have to copy the logic from
identical0). However, as demonstrated in #43056, this code is
complicated and not always easy to reason about, particularly in the
context of type checking where not all types may be complete.

To further understand and verify this code I'd like to write more tests,
but that must wait until the rest of the changes in go/types are
imported from dev.go2go.

Change-Id: Iabb9d3a6af988a2e1b3445cde6bc2431a80f8bfe
Reviewed-on: https://go-review.googlesource.com/c/go/+/276692
Run-TryBot: Robert Findley <rfindley@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Robert Findley <rfindley@google.com>
Reviewed-by: Robert Griesemer <gri@golang.org>
@griesemer griesemer added the NeedsDecision label Apr 14, 2021
@griesemer griesemer removed this from the Go1.17 milestone Apr 20, 2021
@griesemer griesemer added this to the Go1.18 milestone Apr 20, 2021
@griesemer griesemer added NeedsFix okay-after-beta1 release-blocker and removed NeedsDecision Thinking labels Oct 28, 2021
@cherrymui cherrymui removed the okay-after-beta1 label Dec 14, 2021
@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 11, 2022

Slightly simpler, analogous case:

package p

func f[T ~func(T)](a, b T) {}

type F func(F)

func _() {
	var i F
	var j func(F)

	f(i, j)
	f(j, i)
}

@gopherbot
Copy link

@gopherbot gopherbot commented Jan 11, 2022

Change https://golang.org/cl/377894 mentions this issue: go/types, types2: make function type inference argument-order independent

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jan 12, 2022

The above CL addresses this issue, but it also adds complexity to the description of type inference. Per discussion w/ @ianlancetaylor , this is not necessarily a "bug": the error can be explained given the existing spec rules (in progress). It is also an extremely esoteric case that seems unlikely to occur frequently in practice.

Decision is to postpone any action on this for the time being. We can keep the code in place as it is guarded by a flag. If we decide to act upon this, it will be trivial to enable this specific fix.

@griesemer griesemer added NeedsDecision and removed NeedsFix release-blocker labels Jan 12, 2022
@griesemer griesemer changed the title cmd/compile/internal/types2: inconsistent type inference involving anonymous interfaces cmd/compile/internal/types2: make type inference independent of function argument order Jan 12, 2022
@griesemer griesemer removed this from the Go1.18 milestone Jan 12, 2022
@griesemer griesemer added this to the Go1.19 milestone Jan 12, 2022
gopherbot pushed a commit that referenced this issue Jan 12, 2022
…dent

If we have more than 2 arguments, we may have arguments with named and
unnamed types. If that is the case, permutate params and args such that
the arguments with named types are first in the list. This doesn't affect
type inference if all types are taken as is. But when we have inexact
unification enabled (as is the case for function type inference), when
a named type is unified with an unnamed type, unification proceeds with
the underlying type of the named type because otherwise unification would
fail right away. This leads to an asymmetry in type inference: in cases
where arguments of named and unnamed types are passed to parameters with
identical type, different types (named vs underlying) may be inferred
depending on the order of the arguments.
By ensuring that named types are seen first, order dependence is avoided
and unification succeeds where it can.

This CL implements the respectice code but keeps it disabled for now,
pending decision whether we want to address this issue in the first
place.

For #43056.

Change-Id: Ibe3b08ec2afe90a24a8c30cd1875d504bcc2ef39
Reviewed-on: https://go-review.googlesource.com/c/go/+/377894
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
@ianlancetaylor ianlancetaylor added generics TypeInference labels Apr 18, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
generics NeedsDecision TypeInference
Projects
None yet
Development

No branches or pull requests

5 participants