cmd/compile: infinite loop in types2

[reusee]

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

$ go version
go version devel go1.18-df4c625d88 Thu Sep 2 01:06:17 2021 +0000 windows/amd64

Does this issue reproduce with the latest release?

No

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

go env Output

$ go env
set GO111MODULE=
set GOARCH=amd64
set GOBIN=
set GOCACHE=C:\Users\reus\AppData\Local\go-build
set GOENV=C:\Users\reus\AppData\Roaming\go\env
set GOEXE=.exe
set GOEXPERIMENT=
set GOFLAGS=
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMODCACHE=C:\Users\reus\go\pkg\mod
set GONOPROXY=github.com/reusee/*
set GONOSUMDB=github.com/reusee/*
set GOOS=windows
set GOPATH=C:\Users\reus\go
set GOPRIVATE=github.com/reusee/*
set GOPROXY=https://goproxy.cn,direct
set GOROOT=C:\Users\reus\gotip
set GOSUMDB=sum.golang.org
set GOTMPDIR=
set GOTOOLDIR=C:\Users\reus\gotip\pkg\tool\windows_amd64
set GOVCS=
set GOVERSION=devel go1.18-df4c625d88 Thu Sep 2 01:06:17 2021 +0000
set GCCGO=gccgo
set AR=ar
set CC=gcc
set CXX=g++
set CGO_ENABLED=1
set GOMOD=NUL
set CGO_CFLAGS=-g -O2
set CGO_CPPFLAGS=
set CGO_CXXFLAGS=-g -O2
set CGO_FFLAGS=-g -O2
set CGO_LDFLAGS=-g -O2
set PKG_CONFIG=pkg-config
set GOGCCFLAGS=-m64 -mthreads -fmessage-length=0 -fdebug-prefix-map=C:\Users\reus\AppData\Local\Temp\go-build2732815147=/tmp/go-build -gno-record-gcc-switches
GOROOT/bin/go version: go version devel go1.18-df4c625d88 Thu Sep 2 01:06:17 2021 +0000 windows/amd64
GOROOT/bin/go tool compile -V: compile version devel go1.18-df4c625d88 Thu Sep 2 01:06:17 2021 +0000

What did you do?

go build

package main

func Foo[
        Src interface {
                func() Src
        },
]() Src {
        return Foo[Src]
}

func main() {
  Foo()
}

What did you expect to see?

Compile OK

What did you see instead?

# command-line-arguments
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc01ce01528 stack=[0xc01ce00000, 0xc03ce00000]
fatal error: stack overflow

runtime stack:
runtime.throw({0x143863c, 0x1a3afc0})
        C:/Users/reus/gotip/src/runtime/panic.go:965 +0x76
runtime.newstack()
        C:/Users/reus/gotip/src/runtime/stack.go:1085 +0x5cc
runtime.morestack()
        C:/Users/reus/gotip/src/runtime/asm_amd64.s:422 +0x93

goroutine 1 [running]:
cmd/compile/internal/types2.(*subster).typ(0xc03cdfde18, {0x1598640, 0xc004cc2a00})
        C:/Users/reus/gotip/src/cmd/compile/internal/types2/subst.go:87 +0x19e5 fp=0xc01ce01538 sp=0xc01ce01530 pc=0x12ac0c5
cmd/compile/internal/types2.(*subster).var_(0xc00ce017e8, 0xc004cc19e0)
        C:/Users/reus/gotip/src/cmd/compile/internal/types2/subst.go:297 +0x32 fp=0xc01ce01578 sp=0xc01ce01538 pc=0x12ac432
cmd/compile/internal/types2.(*subster).varList(0x0, {0xc004cb2a98, 0x1, 0x0})
        C:/Users/reus/gotip/src/cmd/compile/internal/types2/subst.go:318 +0x90 fp=0xc01ce015e8 sp=0xc01ce01578 pc=0x12ac690
cmd/compile/internal/types2.(*subster).tuple(0xc0085fde18, 0xc004cbb248)
        C:/Users/reus/gotip/src/cmd/compile/internal/types2/subst.go:308 +0x35 fp=0xc01ce01630 sp=0xc01ce015e8 pc=0x12ac555
cmd/compile/internal/types2.(*subster).typ(0xc03cdfde18, {0x1598640, 0xc004cc2a40})
        C:/Users/reus/gotip/src/cmd/compile/internal/types2/subst.go:127 +0x5df fp=0xc01ce01898 sp=0xc01ce01630 pc=0x12aacbf
cmd/compile/internal/types2.(*subster).var_(0xc00ce01b48, 0xc004cc1a40)
        C:/Users/reus/gotip/src/cmd/compile/internal/types2/subst.go:297 +0x32 fp=0xc01ce018d8 sp=0xc01ce01898 pc=0x12ac432
cmd/compile/internal/types2.(*subster).varList(0x0, {0xc004cb2aa0, 0x1, 0x0})
        C:/Users/reus/gotip/src/cmd/compile/internal/types2/subst.go:318 +0x90 fp=0xc01ce01948 sp=0xc01ce018d8 pc=0x12ac690
cmd/compile/internal/types2.(*subster).tuple(0xc0085fde18, 0xc004cbb260)

[danscales]

Infinite loop in types2 substituter. @griesemer

[findleyr]

Related: #45550 and #48098.

Compile OK

FWIW, I don't think this function can reasonably compile without errors. What is the type of Foo()? We'd need a type name to define this kind of recursive data type (e.g. https://play.golang.org/p/JMlAom-VMOt).

[griesemer]

Nice! Thanks for reporting @reusee .

[griesemer]

Simpler reproducer:

package p

func f[P interface { *P }]() {}

func _() {
        f()
}

[griesemer]

The issue here is that constraint type inference tries to unify P and *P which then leads to an infinite expansion loop (P = *P, P = **P, etc.). The fix requires detection of arbitrary cycles from (all) inferred types trough (all) type parameters. CL forthcoming.