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: recursive embedded interface types cause stack overflow #25262

Open
nathanjcochran opened this Issue May 5, 2018 · 9 comments

Comments

Projects
None yet
8 participants
@nathanjcochran

nathanjcochran commented May 5, 2018

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

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

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

@namusyaka

This comment has been minimized.

Member

namusyaka commented May 5, 2018

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

@josharian

This comment has been minimized.

Contributor

josharian commented May 5, 2018

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

This comment has been minimized.

Member

mvdan commented May 6, 2018

The very old bug might be #1074.

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

@mdempsky

This comment has been minimized.

Member

mdempsky commented May 9, 2018

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 griesemer self-assigned this May 31, 2018

@griesemer

This comment has been minimized.

Contributor

griesemer commented May 31, 2018

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

This comment has been minimized.

Contributor

griesemer commented May 31, 2018

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

This comment has been minimized.

Member

odeke-em commented Jun 22, 2018

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

This comment has been minimized.

Contributor

griesemer commented Jun 22, 2018

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 griesemer modified the milestones: Go1.11, Go1.12 Jun 22, 2018

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

@griesemer

This comment has been minimized.

Contributor

griesemer commented Dec 5, 2018

Too late for 1.12.

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment