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: type inference fails using constraint with approximate map element #51229

Closed
blackgreen100 opened this issue Feb 16, 2022 · 10 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@blackgreen100
Copy link

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

go1.18beta2

Does this issue reproduce with the latest release?

Yes. It reproduces with go1.18beta2 and on the tip playground with go1.18-293ecd87c1.

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

go env Output
$ go env
GO111MODULE=""
GOARCH="arm64"
GOBIN=""
GOCACHE="/Users/blackgreen/Library/Caches/go-build"
GOENV="/Users/blackgreen/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="arm64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/blackgreen/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/blackgreen/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/Users/blackgreen/sdk/go1.18beta2"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/Users/blackgreen/sdk/go1.18beta2/pkg/tool/darwin_arm64"
GOVCS=""
GOVERSION="go1.18beta2"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/Users/blackgreen/gotest/go2/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 -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/zb/sywfjpc97cgc1f_gxwfsxtmh0000gn/T/go-build2315498769=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

I came across this stack overflow question:
https://stackoverflow.com/questions/71131665/generics-pass-map-with-derived-types

I attempted to answer the question with the following function:

func equal[M1 ~map[K1]V1, M2 ~map[K2]V2, K1, K2 ~uint32, V1, V2 ~string](m1 M1, m2 M2) bool {
        // ... function body
}

I thought it was possible to infer K1 and K2 from M1 and M2 respectively. The approximate constraints were used to allow conversion in the function body. It doesn't compile with error:

K2 does not match uint32

Instead this works, even though the type parameters K1 and K2 are defined the same way:

func equalFixed[K1, K2 ~uint32, V1, V2 ~string](m1 map[K1]V1, m2 map[K2]V2) bool {
    // ... function body
}

Go tip playground to demonstrate the issue: https://gotipplay.golang.org/p/NPpau1G0Hqp

What did you expect to see?

I expected the program to compile. Based on the Go 1.18 draft specs I expected he parameters K1 and K2 to be inferred separately from the approx elements in M1 and M2 constraints.

What did you see instead?

Compilation error "K2 does not match uint32"

@randall77
Copy link
Contributor

@griesemer @ianlancetaylor
If you list the types explicitly it works. Some sort of limitation of type inference, not sure if it is intended or not.

@blackgreen100
Copy link
Author

@randall77 interestingly, it works if you list all type params; even providing K1 and K2 explicitly and leaving V1 and V2 to be inferred produces the same error:

equal[map[uint32]string, map[someNumericID]someStringID, uint32, someNumericID](foo, bar) // K2 does not match uint32

@ianlancetaylor ianlancetaylor changed the title cmd/compile: incorrect type inference from constraint with approximate map element cmd/compile: type inference fails using constraint with approximate map element Feb 17, 2022
@ianlancetaylor ianlancetaylor added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Feb 17, 2022
@ianlancetaylor ianlancetaylor added this to the Go1.18 milestone Feb 17, 2022
@griesemer
Copy link
Contributor

Simpler reproducer resulting in the same error:

package p

func f[S1 ~[]E1, S2 ~[]E2, E1, E2 ~byte](S1, S2) {}

type myByte byte

func _() {
        f([]byte{}, []myByte{})
}

This looks like a bug in type inference: when comparing the inferred type of E2 against its constraint, we ignore the ~ in the constraint.

This may be trivial to fix. If so, we should fix this for 1.18. Otherwise, we may want to 1.19.

Here's the inference trace:

-- inferA [S1₁, S2₂, E1₃, E2₄](S1₁, S2₂) ➞ []
S1₁ ≡ []byte
.  S1₁ ➞ []byte
S2₂ ≡ []p.myByte
.  S2₂ ➞ []p.myByte
-- inferB [S1₁, S2₂, E1₃, E2₄] ➞ [[]byte, []myByte, <nil>, <nil>]
S1₁ ➞ []byte
S2₂ ➞ []p.myByte
S1₁ ≡ []E1₃
.  []byte ≡ []E1₃
.  .  byte ≡ E1₃
.  .  .  E1₃ ➞ byte
S2₂ ≡ []E2₄
.  []p.myByte ≡ []E2₄
.  .  p.myByte ≡ E2₄
.  .  .  E2₄ ➞ p.myByte
E1₃ ≡ byte
E2₄ ≡ byte
.  p.myByte ≡ byte
.  p.myByte ≢ byte
E2₄ ≢ byte
=> inferB [S1₁, S2₂, E1₃, E2₄] ➞ []
=> inferA [S1₁, S2₂, E1₃, E2₄] ➞ []

@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 Feb 22, 2022
@gopherbot
Copy link

Change https://go.dev/cl/387774 mentions this issue: types2: implement adjCoreType using TypeParam.is

@griesemer
Copy link
Contributor

griesemer commented Feb 24, 2022

This was closed by virtue of an unfortunately phrased commit message. Reopening.

@griesemer griesemer reopened this Feb 24, 2022
@gopherbot
Copy link

Change https://go.dev/cl/387977 mentions this issue: types2: correctly onsider ~ (tilde) in constraint type inference

@gopherbot
Copy link

Change https://go.dev/cl/390015 mentions this issue: [release-branch.go1.18] go/types, types2: correctly consider ~ (tilde) in constraint type inference

gopherbot pushed a commit that referenced this issue Mar 4, 2022
…) in constraint type inference

When doing constraint type inference, we must consider whether the
constraint's core type is precise (no tilde) or imprecise (tilde,
or not a single specific type). In the latter case, we cannot infer
an unknown type argument from the (imprecise) core type because there
are infinitely many possible types. For instance, given

        [E ~byte]

if we don't know E, we cannot infer that E must be byte (it could be
myByte, etc.). On the other hand, if we do know the type argument,
say for S in this example:

        [S ~[]E, E any]

we must consider the underlying type of S when matching against ~[]E
because we have a tilde.

Because constraint type inference may infer type arguments that were
not eligible initially (because they were unknown and the core type
is imprecise), we must iterate the process until nothing changes any-
more. For instance, given

        [S ~[]E, M ~map[string]S, E any]

where we initially only know the type argument for M, we must ignore
S (and E) at first. After one iteration of constraint type inference,
S is known at which point we can infer E as well.

The change is large-ish but the actual functional changes are small:

- There's a new method "unknowns" to determine the number of as of yet
  unknown type arguments.

- The adjCoreType function has been adjusted to also return tilde
  and single-type information. This is now conveniently returned
  as (*term, bool), and the function has been renamed to coreTerm.

- The original constraint type inference loop has been adjusted to
  consider tilde information.

- This adjusted original constraint type inference loop has been
  nested in another loop for iteration, together with some minimal
  logic to control termination.

The remaining changes are modifications to tests:

- There's a substantial new test for this issue.

- Several existing test cases were adjusted to accomodate the
  fact that they inferred incorrect types: tildes have been
  removed throughout. Most of these tests are for pathological
  cases.

- A couple of tests were adjusted where there was a difference
  between the go/types and types2 version.

Fixes #51229.

Change-Id: If0bf5fb70ec22913b5a2da89adbf8a27fbc921d9
Reviewed-on: https://go-review.googlesource.com/c/go/+/387977
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
(cherry picked from commit 0807986)
Reviewed-on: https://go-review.googlesource.com/c/go/+/390015
Trust: Dmitri Shuralyov <dmitshur@golang.org>
Run-TryBot: Dmitri Shuralyov <dmitshur@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
@dominikh
Copy link
Member

It's unfortunate that this no longer works:

func fn1[T ~float64](x T) {}
func fn2() {
  fn1(0)
}

@griesemer
Copy link
Contributor

@dominikh That was just wrong before: we can't possibly know the type of T. It must have an underlying type float64 but there are infinitely many such types. I suppose one could take more information into account: if the type parameter T doesn't "escape" fn1 (which is the case in this minimal example), then it would be ok to infer float64 because that's all that the function knows anyway about the type parameter.

But I'm not sure that's a worthwhile complication.

@dominikh
Copy link
Member

But I'm not sure that's a worthwhile complication.

Probably not :(

@golang golang locked and limited conversation to collaborators Jun 22, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

No branches or pull requests

6 participants