cmd/compile: type inference fails using constraint with approximate map element #51229

blackgreen100 · 2022-02-16T22:04:14Z

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"

The text was updated successfully, but these errors were encountered:

randall77 · 2022-02-16T22:22:02Z

@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 · 2022-02-16T22:42:40Z

@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

griesemer · 2022-02-22T17:54:11Z

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₄] ➞ []

gopherbot · 2022-02-23T21:48:28Z

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

griesemer · 2022-02-24T22:30:09Z

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

gopherbot · 2022-02-25T06:14:31Z

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

gopherbot · 2022-03-04T15:31:35Z

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

…) 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 · 2022-03-12T13:35:29Z

It's unfortunate that this no longer works:

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

griesemer · 2022-03-12T17:12:25Z

@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 · 2022-03-12T17:29:28Z

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

Probably not :(

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 added the NeedsInvestigation label Feb 17, 2022

ianlancetaylor added this to the Go1.18 milestone Feb 17, 2022

ianlancetaylor assigned griesemer Feb 17, 2022

griesemer added NeedsFix and removed NeedsInvestigation labels Feb 22, 2022

gopherbot closed this as completed in c15527f Feb 24, 2022

griesemer reopened this Feb 24, 2022

griesemer mentioned this issue Feb 26, 2022

go/types, types2: revisit core type unification in the presence of ~ constraints #51376

Closed

gopherbot closed this as completed in 0807986 Mar 1, 2022

rsc unassigned griesemer Jun 22, 2022

golang locked and limited conversation to collaborators Jun 22, 2023

gopherbot added the FrozenDueToAge label Jun 22, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: type inference fails using constraint with approximate map element #51229

cmd/compile: type inference fails using constraint with approximate map element #51229

blackgreen100 commented Feb 16, 2022

randall77 commented Feb 16, 2022

blackgreen100 commented Feb 16, 2022

griesemer commented Feb 22, 2022

gopherbot commented Feb 23, 2022

griesemer commented Feb 24, 2022 •

edited

Loading

gopherbot commented Feb 25, 2022

gopherbot commented Mar 4, 2022

dominikh commented Mar 12, 2022

griesemer commented Mar 12, 2022

dominikh commented Mar 12, 2022

cmd/compile: type inference fails using constraint with approximate map element #51229

cmd/compile: type inference fails using constraint with approximate map element #51229

Comments

blackgreen100 commented Feb 16, 2022

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

Does this issue reproduce with the latest release?

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

What did you do?

What did you expect to see?

What did you see instead?

randall77 commented Feb 16, 2022

blackgreen100 commented Feb 16, 2022

griesemer commented Feb 22, 2022

gopherbot commented Feb 23, 2022

griesemer commented Feb 24, 2022 • edited Loading

gopherbot commented Feb 25, 2022

gopherbot commented Mar 4, 2022

dominikh commented Mar 12, 2022

griesemer commented Mar 12, 2022

dominikh commented Mar 12, 2022

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

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

griesemer commented Feb 24, 2022 •

edited

Loading