cmd/compile: recursive embedded interface types cause stack overflow #25262

nathanjcochran · 2018-05-05T19:05:46Z

What did you do?

I tried to compile the following program, but it caused the compiler to hang indefinitely:

package main

func main() {}

type I interface {
	M1() interface {
		I
	}
	M2() interface {
		I
	}
}

If you remove either of the two interface method definitions (M1 or M2), it compiles. Furthermore, it seems to exhibit the same behavior whether the anonymous interfaces are for the method return types, parameter types, or a mixture of the two.

Go Playground: https://play.golang.org/p/UkT9bStm3tR (After the first run on the Go Playground, which hung until it timed out, the playground started responding immediately with what appears to be a cached error message).

Github: https://github.com/nathanjcochran/hung-compiler

go get -d github.com/nathanjcochran/hung-compiler
go install github.com/nathanjcochran/hung-compiler # Hangs indefinitely

What did you expect to see?

I expected it to compile.

What did you see instead?

The compiler hangs indefinitely.

Does this issue reproduce with the latest release (go1.10.2)?

I tried it with go1.10.1, but not go1.10.2

EDIT: I tried it with go1.10.2, and it still hung indefinitely

System details

go version go1.10.1 linux/amd64
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/nathan/.cache/go-build"
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/nathan/go"
GORACE=""
GOROOT="/usr/local/go"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build836785314=/tmp/go-build -gno-record-gcc-switches"
GOROOT/bin/go version: go version go1.10.1 linux/amd64
GOROOT/bin/go tool compile -V: compile version go1.10.1
uname -sr: Linux 4.4.0-122-generic
LSB Version:	core-9.20160110ubuntu0.2-amd64:core-9.20160110ubuntu0.2-noarch:security-9.20160110ubuntu0.2-amd64:security-9.20160110ubuntu0.2-noarch
Distributor ID:	LinuxMint
Description:	Linux Mint 18 Sarah
Release:	18
Codename:	sarah
/lib/x86_64-linux-gnu/libc.so.6: GNU C Library (Ubuntu GLIBC 2.23-0ubuntu10) stable release version 2.23, by Roland McGrath et al.
gdb --version: GNU gdb (Ubuntu 7.11.1-0ubuntu1~16.5) 7.11.1

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

namusyaka · 2018-05-05T20:51:22Z

@nathanjcochran Thanks for your report.
Looks like a bug. But I would like to hear other opinion from @mdempsky, @odeke-em and @josharian

josharian · 2018-05-05T20:55:56Z

I think this is a duplicate of a very old, known bug. Would be good to check older go versions. In any case, this is definitely in @mdempsky’s wheelhouse.

mvdan · 2018-05-06T05:44:57Z

The very old bug might be #1074.

mdempsky · 2018-05-09T00:47:04Z

The issue here is that we don't have a type encoding scheme for anonymous type cycles. For types that self-reference multiple times (e.g., I above), it ends up taking exponential time to generate a flattened string description of the type.

I think if we adopt a scheme that handles cycles better (examples), that would address this issue too.

griesemer · 2018-05-31T05:17:41Z

A simple approach (for now) might be to disallow such code as this is effectively the same as the following:

package main

func main() {}

type I alias
type alias = interface {
	M1() interface {
		alias
	}
	M2() interface {
		alias
	}
}

which is the same as

package main

func main() {}

type I alias
type alias = interface {
	M1() alias
	M2() alias
}

both of which are disallowed for the same reason the original code "explodes".

Forbidding this case would certainly be less surprising than have the compiler run out of memory. It still leaves the door open to remove the restriction down the road, in a backward-compatible way.

griesemer · 2018-05-31T05:19:07Z

Marking release-blocker for now. It would be nice to have this and the other cycle-related issues addressed for 1.11 if we can.

odeke-em · 2018-06-22T09:15:36Z

For comparison with other Go versions after running

$ go tool compile main.go

Version	Synopsis	Link	Comment
Go1.7	Stackoverflow	[1]
Go1.8	Cannot export unnamed types	[2]	Produces an object code file though
Go1.9	Infinite hang		Similar to what's on tip
Go1.10.3	Infinite hang		Similar to what's on tip
Go tip(pre-Go1.11 at `4991bc6`)	Infinite hang

[1]

$ go tool compile main.go 
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow
runtime stack:
runtime.throw(0x4fb0f7, 0xe)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/runtime/panic.go:566 +0x95
runtime.newstack()
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/runtime/stack.go:1061 +0x416
runtime.morestack()
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/runtime/asm_amd64.s:366 +0x7f

goroutine 1 [running]:
encoding/binary.PutVarint(0xc4404b0316, 0xa, 0xa, 0xfffffffffffffff2, 0x0)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/encoding/binary/varint.go:78 fp=0xc4404b02d8 sp=0xc4404b02d0
cmd/compile/internal/gc.(*exporter).rawInt64(0xc4604af890, 0xfffffffffffffff2)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:1712 +0x5d fp=0xc4404b0330 sp=0xc4404b02d8
cmd/compile/internal/gc.(*exporter).tag(0xc4604af890, 0xfffffffffffffff2)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:1658 +0x101 fp=0xc4404b0380 sp=0xc4404b0330
cmd/compile/internal/gc.(*exporter).typ(0xc4604af890, 0xc42041fc70)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:792 +0xeb1 fp=0xc4404b04e8 sp=0xc4404b0380
cmd/compile/internal/gc.(*exporter).param(0xc4604af890, 0xc42040d5c0, 0xffffffffffffffff, 0x0)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:938 +0x49 fp=0xc4404b0530 sp=0xc4404b04e8
cmd/compile/internal/gc.(*exporter).paramList(0xc4604af890, 0xc42041fc20, 0xc42040d600)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:928 +0xf1 fp=0xc4404b0588 sp=0xc4404b0530
cmd/compile/internal/gc.(*exporter).method(0xc4604af890, 0xc42040d680)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:863 +0xbc fp=0xc4404b05b0 sp=0xc4404b0588
cmd/compile/internal/gc.(*exporter).methodList(0xc4604af890, 0xc42041fc70)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:855 +0xb8 fp=0xc4404b0620 sp=0xc4404b05b0
cmd/compile/internal/gc.(*exporter).typ(0xc4604af890, 0xc42041fc70)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:797 +0xee9 fp=0xc4404b0788 sp=0xc4404b0620
cmd/compile/internal/gc.(*exporter).param(0xc4604af890, 0xc42040d5c0, 0xffffffffffffffff, 0x0)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:938 +0x49 fp=0xc4404b07d0 sp=0xc4404b0788
cmd/compile/internal/gc.(*exporter).paramList(0xc4604af890, 0xc42041fc20, 0xc42040d600)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:928 +0xf1 fp=0xc4404b0828 sp=0xc4404b07d0
cmd/compile/internal/gc.(*exporter).method(0xc4604af890, 0xc42040d680)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:863 +0xbc fp=0xc4404b0850 sp=0xc4404b0828
cmd/compile/internal/gc.(*exporter).methodList(0xc4604af890, 0xc42041fc70)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:855 +0xb8 fp=0xc4404b08c0 sp=0xc4404b0850
cmd/compile/internal/gc.(*exporter).typ(0xc4604af890, 0xc42041fc70)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:797 +0xee9 fp=0xc4404b0a28 sp=0xc4404b08c0
cmd/compile/internal/gc.(*exporter).param(0xc4604af890, 0xc42040d5c0, 0xffffffffffffffff, 0x0)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/bexport.go:938 +0x49 fp=0xc4404b0a70 sp=0xc4404b0a28
<frames_elided>

[2]

$ go tool compile main.go 
./main.go:8: cannot export unnamed recursive interface
./main.go:11: cannot export unnamed recursive interface
./main.go:11: too many errors

griesemer · 2018-06-22T18:11:27Z

Thanks, @odeke-em for this analysis; this is useful.

As this is not a regression, I'll push this to 1.12. A fix will likely be involved and it's too risky for 1.11 at this point.

griesemer · 2018-12-05T23:39:15Z

Too late for 1.12.

griesemer · 2022-03-18T04:01:43Z

This seems to work now with Go 1.18. Closing.

nathanjcochran changed the title ~~Program Causes Compiler To Hang Indefinitely~~ Program causes compiler to hang indefinitely May 5, 2018

namusyaka changed the title ~~Program causes compiler to hang indefinitely~~ cmd/compile: program causes compiler to hang indefinitely May 5, 2018

namusyaka added the NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. label May 5, 2018

ALTree added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. and removed NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. labels May 6, 2018

ALTree added this to the Go1.11 milestone May 6, 2018

griesemer self-assigned this May 31, 2018

griesemer added the release-blocker label May 31, 2018

griesemer mentioned this issue Jun 12, 2018

gccgo: internal compiler error for interface with cyclic result types #25851

Open

griesemer modified the milestones: Go1.11, Go1.12 Jun 22, 2018

griesemer removed the release-blocker label Jun 22, 2018

griesemer changed the title ~~cmd/compile: program causes compiler to hang indefinitely~~ cmd/compile: recursive embedded interface types cause stack overflow Sep 18, 2018

griesemer modified the milestones: Go1.12, Go1.13 Dec 5, 2018

griesemer modified the milestones: Go1.13, Go1.14 May 6, 2019

rsc modified the milestones: Go1.14, Backlog Oct 9, 2019

griesemer closed this as completed Mar 18, 2022

rsc unassigned griesemer Jun 23, 2022

mdempsky mentioned this issue Oct 8, 2022

spec: disallow anonymous interface cycles #56103

Open

golang locked and limited conversation to collaborators Jun 23, 2023

gopherbot added the FrozenDueToAge label Jun 23, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: recursive embedded interface types cause stack overflow #25262

cmd/compile: recursive embedded interface types cause stack overflow #25262

nathanjcochran commented May 5, 2018 •

edited

namusyaka commented May 5, 2018

josharian commented May 5, 2018 •

edited

mvdan commented May 6, 2018

mdempsky commented May 9, 2018

griesemer commented May 31, 2018

griesemer commented May 31, 2018

odeke-em commented Jun 22, 2018

griesemer commented Jun 22, 2018

griesemer commented Dec 5, 2018

griesemer commented Mar 18, 2022

cmd/compile: recursive embedded interface types cause stack overflow #25262

cmd/compile: recursive embedded interface types cause stack overflow #25262

Comments

nathanjcochran commented May 5, 2018 • edited

What did you do?

What did you expect to see?

What did you see instead?

Does this issue reproduce with the latest release (go1.10.2)?

System details

namusyaka commented May 5, 2018

josharian commented May 5, 2018 • edited

mvdan commented May 6, 2018

mdempsky commented May 9, 2018

griesemer commented May 31, 2018

griesemer commented May 31, 2018

odeke-em commented Jun 22, 2018

[1]

[2]

griesemer commented Jun 22, 2018

griesemer commented Dec 5, 2018

griesemer commented Mar 18, 2022

nathanjcochran commented May 5, 2018 •

edited

josharian commented May 5, 2018 •

edited