Skip to content

cmd/compile: fails with stack overflow using generics and self referential function type #51832

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.

Sign up for GitHub

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

Jump to bottom
Closed
noclue opened this issue Mar 20, 2022 · 7 comments
Closed

cmd/compile: fails with stack overflow using generics and self referential function type #51832

noclue opened this issue Mar 20, 2022 · 7 comments
Labels
FrozenDueToAge generics Issue is related to generics NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Milestone
Go1.19

Comments

@noclue
Copy link

noclue commented Mar 20, 2022

What version of Go are you using (go version)? go version go1.18 windows/amd64

$ go version
 go version go1.18 windows/amd64

Does this issue reproduce with the latest release? Yes

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\karaa\AppData\Local\go-build
set GOENV=C:\Users\karaa\AppData\Roaming\go\env
set GOEXE=.exe
set GOEXPERIMENT=
set GOFLAGS=
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMODCACHE=C:\Users\karaa\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOPATH=C:\Users\karaa\go
set CGO_ENABLED=1
set GOMOD=C:\Users\karaa\projects\go\generics\go.mod
set GOWORK=
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 -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=C:\Users\karaa\AppData\Local\Temp\go-build2344714082=/tmp/go-build -gno-record-gcc-switches

What did you do?

I want to define a constraint on the pointer receiver of a type and also have a self referential function type.

This combination seem to trigger infinite recursion and stack overflow

Here is link to the go playground https://go.dev/play/p/aOb7OSImUuf

Here are the stack overflow discussions about adding interface constraint on the pointer receiver of a type T

https://stackoverflow.com/questions/71547015/how-to-define-type-constraint-on-pointer-receiver-ingolang/71547820#71547820
https://stackoverflow.com/questions/69573113/how-can-i-instantiate-a-new-pointer-of-type-argument-with-generic-go

Here is a working sample that does not have the self referring function type https://go.dev/play/p/myw6FAosPjK

Here is the failing code just in case

package main

import "fmt"

// In the real solution this function receives parameters and also returns error. As it has to process recursive structures 
// it sometimes has to create a new function with the same signature.
type Consumer func() Consumer 

type Doer[T any] interface {
	Do()
	*T
}

type Struct struct{}

func (s *Struct) Do() {
	return
}

// PT is a constraint on the T pointer receiver based on these discussions. In short I am trying to make sure *T implements Doer.
// https://stackoverflow.com/questions/71547015/how-to-define-type-constraint-on-pointer-receiver-ingolang/71547820#71547820
// https://stackoverflow.com/questions/69573113/how-can-i-instantiate-a-new-pointer-of-type-argument-with-generic-go
// and working sample https://go.dev/play/p/myw6FAosPjK
func CreateConsumer[PT Doer[T], T any]() Consumer {
	return nil
}

func main() {
	fmt.Println("Slice Consumer", CreateConsumer[*Struct]())
}

What did you expect to see?

Successful compilation and run.

What did you see instead?

Stack overflow error on go build ./...
@noclue
Copy link
Author

noclue commented Mar 20, 2022

I found this similar defect that may be related though the file exhibiting the recursion is different and the example is not well distilled #39695

@ianlancetaylor
Copy link
Member

CC @griesemer @findleyr

Error is

runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc0204604c0 stack=[0xc020460000, 0xc040460000]
fatal error: stack overflow

runtime stack:
runtime.throw({0xd10385?, 0x12cb2e0?})
	../../go/src/runtime/panic.go:992 +0x71
runtime.newstack()
	../../go/src/runtime/stack.go:1101 +0x5cc
runtime.morestack()
	../../go/src/runtime/asm_amd64.s:547 +0x8b

goroutine 1 [running]:
cmd/compile/internal/typecheck.(*Tsubster).typ1(0xc04045e528, 0xc0003df5e0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1051 +0x167c fp=0xc0204604d0 sp=0xc0204604c8 pc=0x61fc3c
cmd/compile/internal/typecheck.(*Tsubster).tstruct(0xc04045e528, 0xc0003df810, 0x0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1337 +0x168 fp=0xc020460578 sp=0xc0204604d0 pc=0x61fdc8
cmd/compile/internal/typecheck.(*Tsubster).typ1(0xc04045e528, 0xc0003df5e0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1168 +0x1cd fp=0xc0204607b0 sp=0xc020460578 pc=0x61e78d
cmd/compile/internal/typecheck.(*Tsubster).tstruct(0xc04045e528, 0xc0003df810, 0x0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1337 +0x168 fp=0xc020460858 sp=0xc0204607b0 pc=0x61fdc8
cmd/compile/internal/typecheck.(*Tsubster).typ1(0xc04045e528, 0xc0003df5e0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1168 +0x1cd fp=0xc020460a90 sp=0xc020460858 pc=0x61e78d
cmd/compile/internal/typecheck.(*Tsubster).tstruct(0xc04045e528, 0xc0003df810, 0x0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1337 +0x168 fp=0xc020460b38 sp=0xc020460a90 pc=0x61fdc8
cmd/compile/internal/typecheck.(*Tsubster).typ1(0xc04045e528, 0xc0003df5e0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1168 +0x1cd fp=0xc020460d70 sp=0xc020460b38 pc=0x61e78d
cmd/compile/internal/typecheck.(*Tsubster).tstruct(0xc04045e528, 0xc0003df810, 0x0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1337 +0x168 fp=0xc020460e18 sp=0xc020460d70 pc=0x61fdc8
cmd/compile/internal/typecheck.(*Tsubster).typ1(0xc04045e528, 0xc0003df5e0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1168 +0x1cd fp=0xc020461050 sp=0xc020460e18 pc=0x61e78d
cmd/compile/internal/typecheck.(*Tsubster).tstruct(0xc04045e528, 0xc0003df810, 0x0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1337 +0x168 fp=0xc0204610f8 sp=0xc020461050 pc=0x61fdc8
cmd/compile/internal/typecheck.(*Tsubster).typ1(0xc04045e528, 0xc0003df5e0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1168 +0x1cd fp=0xc020461330 sp=0xc0204610f8 pc=0x61e78d
cmd/compile/internal/typecheck.(*Tsubster).tstruct(0xc04045e528, 0xc0003df810, 0x0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1337 +0x168 fp=0xc0204613d8 sp=0xc020461330 pc=0x61fdc8
cmd/compile/internal/typecheck.(*Tsubster).typ1(0xc04045e528, 0xc0003df5e0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1168 +0x1cd fp=0xc020461610 sp=0xc0204613d8 pc=0x61e78d
cmd/compile/internal/typecheck.(*Tsubster).tstruct(0xc04045e528, 0xc0003df810, 0x0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1337 +0x168 fp=0xc0204616b8 sp=0xc020461610 pc=0x61fdc8
cmd/compile/internal/typecheck.(*Tsubster).typ1(0xc04045e528, 0xc0003df5e0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1168 +0x1cd fp=0xc0204618f0 sp=0xc0204616b8 pc=0x61e78d
cmd/compile/internal/typecheck.(*Tsubster).tstruct(0xc04045e528, 0xc0003df810, 0x0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1337 +0x168 fp=0xc020461998 sp=0xc0204618f0 pc=0x61fdc8
cmd/compile/internal/typecheck.(*Tsubster).typ1(0xc04045e528, 0xc0003df5e0)
	../../go/src/cmd/compile/internal/typecheck/subr.go:1168 +0x1cd fp=0xc020461bd0 sp=0xc020461998 pc=0x61e78d

etc.

@ianlancetaylor ianlancetaylor added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. release-blocker labels Mar 20, 2022
@ianlancetaylor ianlancetaylor added this to the Go1.19 milestone Mar 20, 2022
@griesemer
Copy link
Contributor

Looks like a bug in the 1.18 noder code. The type checker (types2) has no problems with this code. With the unified build this compiles and runs fine and prints Consumer <nil> which is the expected result.

cc @randall77 @mdempsky

@noclue
Copy link
Author

noclue commented Mar 21, 2022

I managed to distill the code further looking at the subr.go code that falls into recursion
https://github.com/golang/go/blob/release-branch.go1.18/src/cmd/compile/internal/typecheck/subr.go

There is no need for fancy generics. Just any generics used alongside self referring function type seem to trigger this
https://go.dev/play/p/1d2qLjzZrSu

package main

type F func() F

func do[T any]() F {
	return nil
}

func main() {
	do[int]()
}

@cuonglm cuonglm 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 Mar 22, 2022
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/394494 mentions this issue: cmd/compile: guard against recursive structural type in Tsubster

@seankhliao seankhliao changed the title go build: fails with stack overflow using generics and self referential function type cmd/conpile: fails with stack overflow using generics and self referential function type Mar 22, 2022
@thepudds thepudds changed the title cmd/conpile: fails with stack overflow using generics and self referential function type cmd/compile: fails with stack overflow using generics and self referential function type Mar 25, 2022
@cuonglm cuonglm mentioned this issue Apr 7, 2022
Closed
@ainar-g ainar-g mentioned this issue Apr 8, 2022
Closed
@heschi heschi added the generics Issue is related to generics label May 11, 2022
@heschi
Copy link
Contributor

heschi commented May 11, 2022

ping: this is a release blocker that hasn't been updated in a while.

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/406714 mentions this issue: cmd/compile: catch pointless recursion on function types

@kazu kazu mentioned this issue May 29, 2022
Draft
@golang golang locked and limited conversation to collaborators May 24, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge generics Issue is related to generics NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Projects
None yet
Milestone
Go1.19
Development

No branches or pull requests
6 participants
@noclue @ianlancetaylor @cuonglm @griesemer @gopherbot @heschi