cmd/compile: "panic: unification reached recursion depth limit" with recursive type constraint

[camhux]

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/[email protected]'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='go1.22.3+auto'
GOTOOLDIR='/Users/cameronmartin/go/pkg/mod/golang.org/[email protected]/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)

[griesemer]

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]

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]

@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]

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]

Moving to 1.25; too late for 1.24.

[gopherbot]

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.