cmd/compile: infinite recursion generating symbol for recursive type

[gopherbot]

by lcampbell@ironclad.mobi:

1. What is a short input program that triggers the error?

package test

type Foo interface {
       Bar() *interface{Foo}
       Baz() *interface{Foo}
       Bug() *interface{Foo}
}

2. What is the full compiler output?

It seems to exhaust system memory before outputting anything. Once I was able to get it
to output

Compile error:
/Users/lcampbell/Projects/asset-tracker/app/mobi.ironclad/aec/interfaces.go:34: internal
compiler error: missing PTR64 case during export

2011/06/02 20:10:26 go-app-builder: Failed building app: 6g exited with status 1

But I am unable to reproduce it effectively.

3. What version of the compiler are you using?  (Run it with the -V flag.)

$ 6g -V
6g version release.r57.1 8294

$ uname -a
Darwin fffffuuuuuuuuuuuu 10.7.0 Darwin Kernel Version 10.7.0: Sat Jan 29 15:17:16 PST
2011; root:xnu-1504.9.37~1/RELEASE_I386 i386

[adg]

Comment 1:

Labels changed: added priority-medium, compilerbug.

Owner changed to @rsc.

Status changed to Accepted.

[lvdlvd]

Comment 2:

Owner changed to @lvdlvd.

[rsc]

Comment 3:

Labels changed: added priority-later, removed priority-medium.

[rsc]

Comment 4:

Labels changed: added priority-go1.

[gopherbot]

Comment 5 by lstoakes:

I think this underlines a more serious problem which is that code like:-
type Foo interface {
    Bar() interface { Foo }
}
Compiles without error which seems to me to be an invalid recursive type (unless I'm
missing something here). I am happy to submit a new issue for this (with reproducing
code - you get nonsensical syntax errors regarding the < of '<...>' when trying
to import a package with such a type in, for example).
src/cmd/gc/fmt.c:1453 has a mechanism for detecting + dealing with overly deep recursive
types when dumping output, i.e.:-
    if(t->trecur > 4)
        return fmtstrcpy(fp, "<...>");
However, a small increase in the number of functions within an interface which exhibits
this recursive behaviour seems to result in exponentially increasing size of the output
type (as inserted at the start of the  .6/.8/.? file).
This also varies with the limit put on t->trecur, e.g.:-
> 0 -> https://gist.github.com/1552355, 69 lines
> 1 -> https://gist.github.com/1552361, 1089 lines
> 2 -> https://gist.github.com/1552363  20,997 lines
I have submitted a trivial patch which puts a limit on the nfmt field of fp to a
somewhat arbitrary limit, which fixes the issue with the compiler going down the garden
path, but obviously not whether it identifies this situation as invalid recursion:-
http://golang.org/cl/5504108/

[lvdlvd]

Comment 6:

Status changed to Started.

[lvdlvd]

Comment 7:

The underlying problem is that embedded interfaces are substituted by their methods
early on, and then the original embedded field is lost.  I started by making
tointerface() retain the originals, and mark them and their imported methods as
->embedded.  then typefmt can print skip the embedded methods and print the interface
they came from (possibly only for recursive types).   This involves skipping over the
now-retained TINTER fields in some places and making go.y accept them too.  
Since it's nearly weekend and there's no rsc to bounce this off off, i thought i'd write
it up here.
work in progress in http://golang.org/cl/5523047

[rsc]

Comment 8:

This issue was closed by revision aa63a928ea6b2fb6b2edb10fd8d98c98f20d527.

Status changed to Fixed.

[rsc]

Comment 9:

This is not actually fixed, but the CL does make it a little less crashy.

Status changed to Accepted.

[lvdlvd]

Comment 10:

i'm in the middle of a real fix, marking 'started' to prevent duplicate effort

Status changed to Started.

[rsc]

Comment 11:

This issue was closed by revision 8a4bd094a033ceb00f7f5a504e4bc652ea5a164.

Status changed to Fixed.

[lvdlvd]

Comment 12:

that revision was a rollback.

Status changed to Started.

[lvdlvd]

Comment 13:

Pending in http://golang.org/cl/5523047/, but that still needs a fix to
exp/types/gcimporter.

[robpike]

Comment 14:

Owner changed to builder@golang.org.

[rsc]

Comment 15:

Owner changed to @lvdlvd.

[lvdlvd]

Comment 16:

This issue was closed by revision 9523b4d59c9a902abce9c584ded795376d875d1.

Status changed to Fixed.

[rsc]

Comment 17:

This issue was reopened by revision f74a2a538435.
Do not fix again before Go 1.  The required compiler changes are subtle enough that we
do not have time to soak them.

Labels changed: added priority-someday, removed priority-go1.

Owner changed to ---.

Status changed to LongTerm.

[rsc]

Comment 19:

Labels changed: added go1.1.

[rsc]

Comment 20:

Labels changed: added size-xl.

[remyoudompheng]

Comment 21:

The original patch for this had quite many problems: I have given a try in
https://golang.org/cl/7232050/ but it still doesn't work.
The suggested approach raises certain problems:
 * interfaces defined in export data may forward declare types. Types are necessary: to resolve embedded interfaces, to typecheck signatures, to check equality of interface types. The current parser assumes a particular order in export data which is no longer satisfied after patching.
 * things must be correctly exported to make sure the binary does not end up with two type definitions and names for identical interface types: a program may compile fine but fail at runtime because conversion to interface is lost in method tables

[remyoudompheng]

Comment 22:

This seems too hard and error-prone for Go 1.1

[rsc]

Comment 23:

Agreed.

Labels changed: removed go1.1.

[rsc]

Comment 24:

Labels changed: added go1.3maybe.

[robpike]

Comment 25:

Labels changed: removed go1.3maybe.

[griesemer]

Comment 26:

Here's another good test case:
package main
type (
    A interface {
        a() interface {
            ABC1
        }
    }
    B interface {
        b() interface {
            ABC2
        }
    }
    C interface {
        c() interface {
            ABC3
        }
    }
    AB interface {
        A
        B
    }
    BC interface {
        B
        C
    }
    ABC1 interface {
        A
        B
        C
    }
    ABC2 interface {
        AB
        C
    }
    ABC3 interface {
        A
        BC
    }
)
var (
    x1 ABC1
    x2 ABC2
    x3 ABC3
)
func main() {
    x1 = x2
    x2 = x3
    x2 = x3
}
This causes the compiler to go into an infinite (probably) recursion (memory is consumed
until machine becomes unresponsive).
All types ABC1, ABC2, ABC3 are identical interface types, but they are constructed in
different ways in the source. Here's a black-box analysis. There are several problems
for a front-end to solve:
1) It must correctly create the internal cyclic type representation for these interface
types. The representation must be based on the methods, not the actual source code
(since there are different ways to get to the same method set). That representation is
cyclic in this case, and the recursion is not represented by ending in a named type
(since the method result types here are unnamed); it's a true cycle in the type
representation.
2) When type-checking the assignments, the compiler must verify that the lhs and rhs
have identical types. That is, in this case it must verify that the cyclic graph on the
lhs matches the cyclic graph on the rhs. Because the cycles are not created with named
types, the graph-comparison algorithm must use some marking scheme (visited map) to
detect cycles.
3) The export data structure for such types (currently we can only have this for
interface types) must be able to represent such recursion. Specifically, it either
reproduces the original source definition (w/ embedding information intact) so it can
use the existing type names to express the recursion; or it needs some other mechanism
(linearization of arbitrary cyclic graph comes to mind - easy, but not done at the
moment).

[griesemer]

Comment 27:

See also issue #6589.

[rsc]

Comment 28:

Labels changed: added repo-main.

[rsc]

Comment 29:

Adding Release=None to all Priority=Someday bugs.

Labels changed: added release-none.

[ianlancetaylor]

Comment 30:

Still a problem as of today with gc.  gccgo has no problem with this code.

[gopherbot]

Comment 31:

CL https://golang.org/cl/147220043 mentions this issue.

[gopherbot]

CL https://golang.org/cl/13937 mentions this issue.

[griesemer]

There are (at least) two endless recursive function calls involved here:

• generating information for reflection (cmd/compile/internal/gc/reflect.go:dumptypestructs)
• generating export data

Both of these use gc's fmt.go facilities to print and then run into endless recursion.

The new binary export format (https://go-review.googlesource.com/13937) fixes the 2nd problem since it can handle arbitrary cycles in types: If we immediately return from dumptypestructs (i.e., just don't dump reflection info for the test), exporting works fine with -newexport. If we use the old export format, we get into an endless recursion while exporting.

We may need to use a similar mechanism to export reflection info as we use for the new binary export.

[gopherbot]

CL https://golang.org/cl/31859 mentions this issue.