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: "panic: unification reached recursion depth limit" with recursive type constraint #67627

Open
camhux opened this issue May 23, 2024 · 6 comments
Assignees
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. early-in-cycle A change that should be done early in the 3 month dev cycle. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@camhux
Copy link

camhux commented May 23, 2024

Go version

go version go1.22.3 darwin/arm64

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='arm64'
GOBIN=''
GOCACHE='/Users/cameronmartin/Library/Caches/go-build'
GOENV='/Users/cameronmartin/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/cameronmartin/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='darwin'
GOPATH='/Users/cameronmartin/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/Users/cameronmartin/go/pkg/mod/golang.org/toolchain@v0.0.1-go1.22.3.darwin-arm64'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='go1.22.3+auto'
GOTOOLDIR='/Users/cameronmartin/go/pkg/mod/golang.org/toolchain@v0.0.1-go1.22.3.darwin-arm64/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.22.3'
GCCGO='gccgo'
AR='ar'
CC='clang'
CXX='clang++'
CGO_ENABLED='1'
GOMOD='/dev/null'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/k3/7h82b52d2gz972yl3nppjdtw0000gn/T/go-build29573479=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

https://go.dev/play/p/_dEZsvc-bV-

What did you see happen?

<unknown line number>: internal compiler error: panic: unification reached recursion depth limit

What did you expect to see?

I expected a non-panic compilation error.

(But maybe I shouldn't have; with a couple of tweaks, a similar program is valid: https://go.dev/play/p/jJ8fTc7Uhie)

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label May 23, 2024
@cagedmantis cagedmantis added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label May 24, 2024
@cagedmantis cagedmantis added this to the Backlog milestone May 24, 2024
@griesemer griesemer self-assigned this May 29, 2024
@griesemer griesemer modified the milestones: Backlog, Go1.23 May 29, 2024
@griesemer
Copy link
Contributor

Slightly simplified reproducer:

package p

type S *S

func f[R, T *R](T) {}

func _() {
	var s S
	f(s)
}

panics as described. But adding a ~ (or swapping the type parameters) in f avoids the crash:

package p

type S *S

func f[R, T ~*R](T) {}  // <<< no crash with `~`

func _() {
	var s S
	f(s)
}

@griesemer
Copy link
Contributor

griesemer commented May 29, 2024

The handling of type element unification may not be quite right (see unify.go:566 ff.)

Too late to fix for 1.23 as this is tricky and may introduce subtle bugs.
Moving to 1.24 since there's a work-around, and this is not a regression.

@griesemer griesemer modified the milestones: Go1.23, Go1.24 May 29, 2024
@griesemer griesemer added the early-in-cycle A change that should be done early in the 3 month dev cycle. label May 29, 2024
@griesemer
Copy link
Contributor

@taking and I looked at this some more. At the core of the issue we have the following situation.

  1. Type inference correctly infers that T ➞ S from the parameter assignment to the function f.
  2. Type inference then proceeds by trying to extract missing information for R.
  3. The constraint for R is *R, the core type of the constraint is *R and *R is the only type in the typeset of the constraint, so (constraint) type inference infers R ➞ *R
  4. Now inference looks at the constraint [T *R]. We know that T must be S so inference matches S against *R: S ≡ *R. This is the start of the cycle.
  5. Because S is a defined type and *R is type literal, inference compares under(S) ≡ *R which is *S ≡ *R.
  6. Both types are pointer types, so S ≡ R.
  7. The inferred type for R is *R (step 3), so we arrive at S ≡ *R, which is where we were at step 4.
    (In the inference trace, the cycle starts a bit later because the LHS and RHS are swapped in the first round, but this doesn't change the behavior - the inference is symmetric with respect to LHS and RHS.)

From the inference trace:

== infer : [R₃, T₄](T₄) ➞ [<nil>, <nil>]
== function parameters: (T₄)
-- function arguments : [s (variable of type p.S)]
.  T₄ ≡ p.S     // assign
.  T₄ ➞ p.S
=> [R₃, T₄] ➞ [<nil>, p.S]

== type parameters: [R₃, T₄]
-- iteration 0
-- type parameter R₃ = <nil>: core(R₃) = *R, single = true
R₃ ➞ *R₃
-- type parameter T₄ = p.S: core(T₄) = *R, single = true
.  p.S ≡ *R₃    // inexact
.  *R₃ ≡ p.S    // swap
.  *R₃ ≡ under p.S
.  .  R₃ ≡ p.S  // inexact
.  .  .  *R₃ ≡ p.S      // inexact
.  .  .  *R₃ ≡ under p.S
.  .  .  .  R₃ ≡ p.S    // inexact
.  .  .  .  .  *R₃ ≡ p.S        // inexact
.  .  .  .  .  etc.

It's not obvious what the correct "fix" is in a case like this. We end up in a cycle because of the cyclic definition of S, but if we start with comparing T against *R instead of R against *R we avoid the endless recursion.

One approach might be to start with type parameters for which we already have a type argument inferred when doing the constraint type inference step.

@gopherbot
Copy link
Contributor

This issue is currently labeled as early-in-cycle for Go 1.24.
That time is now, so a friendly reminder to look at it again.

@griesemer
Copy link
Contributor

Moving to 1.25; too late for 1.24.

@griesemer griesemer modified the milestones: Go1.24, Go1.25 Nov 11, 2024
@gopherbot
Copy link
Contributor

This issue is currently labeled as early-in-cycle for Go 1.25.
That time is now, so a friendly reminder to look at it again.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. early-in-cycle A change that should be done early in the 3 month dev cycle. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
Development

No branches or pull requests

4 participants