Skip to content
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: infinite recursion generating symbol for recursive type #1909

Open
gopherbot opened this Issue Jun 2, 2011 · 33 comments

Comments

Projects
None yet
8 participants
@gopherbot
Copy link

gopherbot commented Jun 2, 2011

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

This comment has been minimized.

Copy link
Contributor

adg commented Jun 6, 2011

Comment 1:

Labels changed: added priority-medium, compilerbug.

Owner changed to @rsc.

Status changed to Accepted.

@lvdlvd

This comment has been minimized.

Copy link

lvdlvd commented Nov 3, 2011

Comment 2:

Owner changed to @lvdlvd.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Dec 9, 2011

Comment 3:

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

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Dec 12, 2011

Comment 4:

Labels changed: added priority-go1.

@gopherbot

This comment has been minimized.

Copy link
Author

gopherbot commented Jan 2, 2012

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

This comment has been minimized.

Copy link

lvdlvd commented Jan 6, 2012

Comment 6:

Status changed to Started.

@lvdlvd

This comment has been minimized.

Copy link

lvdlvd commented Jan 6, 2012

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

This comment has been minimized.

Copy link
Contributor

rsc commented Jan 9, 2012

Comment 8:

This issue was closed by revision aa63a92.

Status changed to Fixed.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Jan 9, 2012

Comment 9:

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

Status changed to Accepted.

@lvdlvd

This comment has been minimized.

Copy link

lvdlvd commented Jan 9, 2012

Comment 10:

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

Status changed to Started.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Jan 9, 2012

Comment 11:

This issue was closed by revision 8a4bd09.

Status changed to Fixed.

@lvdlvd

This comment has been minimized.

Copy link

lvdlvd commented Jan 9, 2012

Comment 12:

that revision was a rollback.

Status changed to Started.

@lvdlvd

This comment has been minimized.

Copy link

lvdlvd commented Jan 12, 2012

Comment 13:

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

This comment has been minimized.

Copy link
Contributor

robpike commented Jan 13, 2012

Comment 14:

Owner changed to builder@golang.org.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Jan 13, 2012

Comment 15:

Owner changed to @lvdlvd.

@lvdlvd

This comment has been minimized.

Copy link

lvdlvd commented Jan 17, 2012

Comment 16:

This issue was closed by revision 9523b4d.

Status changed to Fixed.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Jan 20, 2012

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

This comment has been minimized.

Copy link
Contributor

rsc commented Sep 12, 2012

Comment 19:

Labels changed: added go1.1.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Dec 10, 2012

Comment 20:

Labels changed: added size-xl.

@remyoudompheng

This comment has been minimized.

Copy link
Contributor

remyoudompheng commented Jan 28, 2013

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

This comment has been minimized.

Copy link
Contributor

remyoudompheng commented Mar 6, 2013

Comment 22:

This seems too hard and error-prone for Go 1.1
@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Mar 6, 2013

Comment 23:

Agreed.

Labels changed: removed go1.1.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Jul 30, 2013

Comment 24:

Labels changed: added go1.3maybe.

@robpike

This comment has been minimized.

Copy link
Contributor

robpike commented Aug 20, 2013

Comment 25:

Labels changed: removed go1.3maybe.

@griesemer

This comment has been minimized.

Copy link
Contributor

griesemer commented Oct 16, 2013

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

This comment has been minimized.

Copy link
Contributor

griesemer commented Oct 16, 2013

Comment 27:

See also issue #6589.
@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Dec 4, 2013

Comment 28:

Labels changed: added repo-main.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Mar 3, 2014

Comment 29:

Adding Release=None to all Priority=Someday bugs.

Labels changed: added release-none.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

ianlancetaylor commented Mar 26, 2014

Comment 30:

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

This comment has been minimized.

Copy link
Author

gopherbot commented Sep 26, 2014

Comment 31:

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

josharian added a commit to josharian/go that referenced this issue Dec 18, 2014

test: migrate remaining tests to run.go
* bug248 was split into a rundir half (bug248) and an errorcheckdir half (bug248b).
* bug345, bug369, and bug429 were ported from bash commands to run scripts. bug369 remains disabled.
* bug395 is a test for issue 1909, which is still open. It is marked as skip now and will be usable with compile with run.go when issue 1909 is fixed.

Fixes golang#4139

Updates golang#1909

Change-Id: Ibb5fbfb5cf72ddc285829245318eeacd3fb5a636

josharian added a commit to josharian/go that referenced this issue Dec 22, 2014

test: migrate remaining tests to run.go
* bug248, bug345, bug369, and bug429 were ported from bash commands to run scripts. bug369 remains disabled.
* bug395 is a test for issue 1909, which is still open. It is marked as skip now and will be usable with compile with run.go when issue 1909 is fixed.

Fixes golang#4139

Updates golang#1909

Change-Id: Ibb5fbfb5cf72ddc285829245318eeacd3fb5a636

josharian added a commit that referenced this issue Dec 22, 2014

test: migrate remaining tests to run.go
* bug248, bug345, bug369, and bug429 were ported from bash commands to run scripts. bug369 remains disabled.
* bug395 is a test for issue 1909, which is still open. It is marked as skip now and will be usable with compile with run.go when issue 1909 is fixed.

Fixes #4139

Updates #1909

Change-Id: Ibb5fbfb5cf72ddc285829245318eeacd3fb5a636
Reviewed-on: https://go-review.googlesource.com/1774
Reviewed-by: Russ Cox <rsc@golang.org>

@rsc rsc added this to the Unplanned milestone Apr 10, 2015

@rsc rsc changed the title cmd/gc: infinite recursion generating symbol for recursive type cmd/compile: infinite recursion generating symbol for recursive type Jun 8, 2015

@gopherbot

This comment has been minimized.

Copy link
Author

gopherbot commented Oct 2, 2015

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

@griesemer

This comment has been minimized.

Copy link
Contributor

griesemer commented Oct 8, 2015

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.

griesemer added a commit that referenced this issue Oct 22, 2015

cmd/compile/internal/gc: compact binary export format
The binary import/export format is significantly more
compact than the existing textual format. It should
also be faster to read and write (to be measured).

Use -newexport to enable, for instance:
export GO_GCFLAGS=-newexport; make.bash

The compiler can import packages using both the old
and the new format ("mixed mode").

Missing: export info for inlined functions bodies
(performance issue, does not affect correctness).

Disabled by default until we have inlined function
bodies and confirmation of no regression and equality
of binaries.

For #6110.
For #1909.

This change depends on:

   https://go-review.googlesource.com/16220
   https://go-review.googlesource.com/16222

(already submitted) for all.bash to work.

Some initial export data sizes for std lib packages. This data
is without exported functions with inlineable function bodies.

Package                                       old      new    new/old

archive/tar.................................13875.....3883    28%
archive/zip.................................19464.....5046    26%
bufio....................................... 7733.....2222    29%
bytes.......................................10342.....3347    32%
cmd/addr2line.................................242.......26    11%
cmd/api.....................................39305....10368    26%
cmd/asm/internal/arch.......................27732.....7939    29%
cmd/asm/internal/asm........................35264....10295    29%
cmd/asm/internal/flags........................629......178    28%
cmd/asm/internal/lex........................39248....11128    28%
cmd/asm.......................................306.......26     8%
cmd/cgo.....................................40197....10570    26%
cmd/compile/internal/amd64...................1106......214    19%
cmd/compile/internal/arm....................27891.....7710    28%
cmd/compile/internal/arm64....................891......153    17%
cmd/compile/internal/big....................21637.....8336    39%
cmd/compile/internal/gc....................109845....29727    27%
cmd/compile/internal/mips64...................972......168    17%
cmd/compile/internal/ppc64....................972......168    17%
cmd/compile/internal/x86.....................1104......195    18%
cmd/compile...................................329.......26     8%
cmd/cover...................................12986.....3749    29%
cmd/dist......................................477.......67    14%
cmd/doc.....................................23043.....6793    29%
cmd/expdump...................................167.......26    16%
cmd/fix......................................1190......208    17%
cmd/go......................................26399.....5629    21%
cmd/gofmt.....................................499.......26     5%
cmd/internal/gcprog..........................1342......490    37%
cmd/internal/goobj...........................2690......980    36%
cmd/internal/obj/arm........................32740....10057    31%
cmd/internal/obj/arm64......................46542....15364    33%
cmd/internal/obj/mips.......................42140....13731    33%
cmd/internal/obj/ppc64......................42140....13731    33%
cmd/internal/obj/x86........................52732....19015    36%
cmd/internal/obj............................36729....11690    32%
cmd/internal/objfile........................36365....10287    28%
cmd/link/internal/amd64.....................45893....12220    27%
cmd/link/internal/arm.........................307.......96    31%
cmd/link/internal/arm64.......................345.......98    28%
cmd/link/internal/ld.......................109300....46326    42%
cmd/link/internal/ppc64.......................344.......99    29%
cmd/link/internal/x86.........................334......107    32%
cmd/link......................................314.......26     8%
cmd/newlink..................................8110.....2544    31%
cmd/nm........................................210.......26    12%
cmd/objdump...................................244.......26    11%
cmd/pack....................................14248.....4066    29%
cmd/pprof/internal/commands..................5239.....1285    25%
cmd/pprof/internal/driver...................37967.....8860    23%
cmd/pprof/internal/fetch....................30962.....7337    24%
cmd/pprof/internal/plugin...................47734.....7719    16%
cmd/pprof/internal/profile..................22286.....6922    31%
cmd/pprof/internal/report...................31187.....7838    25%
cmd/pprof/internal/svg.......................4315......965    22%
cmd/pprof/internal/symbolizer...............30051.....7397    25%
cmd/pprof/internal/symbolz..................28545.....6949    24%
cmd/pprof/internal/tempfile.................12550.....3356    27%
cmd/pprof.....................................563.......26     5%
cmd/trace....................................1455......636    44%
cmd/vendor/golang.org/x/arch/arm/armasm....168035....64737    39%
cmd/vendor/golang.org/x/arch/x86/x86asm.....26871.....8578    32%
cmd/vet.....................................38980.....9913    25%
cmd/vet/whitelist.............................102.......49    48%
cmd/yacc.....................................2518......926    37%
compress/bzip2...............................6326......129     2%
compress/flate...............................7069.....2541    36%
compress/gzip...............................20143.....5069    25%
compress/lzw..................................828......295    36%
compress/zlib...............................10676.....2692    25%
container/heap................................523......181    35%
container/list...............................3517......740    21%
container/ring................................881......229    26%
crypto/aes....................................550......187    34%
crypto/cipher................................1966......825    42%
crypto.......................................1836......646    35%
crypto/des....................................632......235    37%
crypto/dsa..................................18718.....5035    27%
crypto/ecdsa................................23131.....6097    26%
crypto/elliptic.............................20790.....5740    28%
crypto/hmac...................................455......186    41%
crypto/md5...................................1375......171    12%
crypto/rand.................................18132.....4748    26%
crypto/rc4....................................561......240    43%
crypto/rsa..................................22094.....6380    29%
crypto/sha1..................................1416......172    12%
crypto/sha256.................................551......238    43%
crypto/sha512.................................839......378    45%
crypto/subtle................................1153......250    22%
crypto/tls..................................58203....17984    31%
crypto/x509/pkix............................29447.....8161    28%
database/sql/driver..........................3318.....1096    33%
database/sql................................11258.....3942    35%
debug/dwarf.................................18416.....7006    38%
debug/elf...................................57530....21014    37%
debug/gosym..................................4992.....2058    41%
debug/macho.................................23037.....6538    28%
debug/pe....................................21063.....6619    31%
debug/plan9obj...............................2467......802    33%
encoding/ascii85.............................1523......360    24%
encoding/asn1................................1718......527    31%
encoding/base32..............................2642......686    26%
encoding/base64..............................3077......800    26%
encoding/binary..............................4727.....1040    22%
encoding/csv................................12223.....2850    23%
encoding......................................383......217    57%
encoding/gob................................37563....10113    27%
encoding/hex.................................1327......390    29%
encoding/json...............................30897.....7804    25%
encoding/pem..................................595......200    34%
encoding/xml................................37798.....9336    25%
errors........................................274.......36    13%
expvar.......................................3155.....1021    32%
flag........................................19860.....2849    14%
fmt..........................................3137.....1263    40%
go/ast......................................44729....13422    30%
go/build....................................16336.....4657    29%
go/constant..................................3703......846    23%
go/doc.......................................9877.....2807    28%
go/format....................................5472.....1575    29%
go/importer..................................4980.....1301    26%
go/internal/gccgoimporter....................5587.....1525    27%
go/internal/gcimporter.......................8979.....2186    24%
go/parser...................................20692.....5304    26%
go/printer...................................7015.....2029    29%
go/scanner...................................9719.....2824    29%
go/token.....................................7933.....2465    31%
go/types....................................64569....19978    31%
hash/adler32.................................1176......176    15%
hash/crc32...................................1663......360    22%
hash/crc64...................................1587......306    19%
hash/fnv.....................................3964......260     7%
hash..........................................591......278    47%
html..........................................217.......74    34%
html/template...............................69623....12588    18%
image/color/palette...........................315.......98    31%
image/color..................................5565.....1036    19%
image/draw...................................6917.....1028    15%
image/gif....................................8894.....1654    19%
image/internal/imageutil.....................9112.....1476    16%
image/jpeg...................................6647.....1026    15%
image/png....................................6906.....1069    15%
image.......................................28992.....6139    21%
index/suffixarray...........................17106.....4773    28%
internal/singleflight........................1614......506    31%
internal/testenv............................12212.....3152    26%
internal/trace...............................2762.....1323    48%
io/ioutil...................................13502.....3682    27%
io...........................................6765.....2482    37%
log.........................................11620.....3317    29%
log/syslog..................................13516.....3821    28%
math/big....................................21819.....8320    38%
math/cmplx...................................2816......438    16%
math/rand....................................2317......929    40%
math.........................................7511.....2444    33%
mime/multipart..............................12679.....3360    27%
mime/quotedprintable.........................5458.....1235    23%
mime.........................................6076.....1628    27%
net/http/cgi................................59796....17173    29%
net/http/cookiejar..........................14781.....3739    25%
net/http/fcgi...............................57861....16426    28%
net/http/httptest...........................84100....24365    29%
net/http/httputil...........................67763....18869    28%
net/http/internal............................6907......637     9%
net/http/pprof..............................57945....16316    28%
net/http....................................95391....30210    32%
net/internal/socktest........................4555.....1453    32%
net/mail....................................14481.....3608    25%
net/rpc/jsonrpc.............................33335......988     3%
net/rpc.....................................79950....23106    29%
net/smtp....................................57790....16468    28%
net/textproto...............................11356.....3248    29%
net/url......................................3123.....1009    32%
os/exec.....................................20738.....5769    28%
os/signal.....................................437......167    38%
os..........................................24875.....6668    27%
path/filepath...............................11340.....2826    25%
path..........................................778......285    37%
reflect.....................................15469.....5198    34%
regexp......................................13627.....4661    34%
regexp/syntax................................5539.....2249    41%
runtime/debug................................9275.....2322    25%
runtime/pprof................................1355......477    35%
runtime/race...................................39.......17    44%
runtime/trace.................................228.......92    40%
runtime.....................................13498.....1821    13%
sort.........................................2848......842    30%
strconv......................................2947.....1252    42%
strings......................................7983.....2456    31%
sync/atomic..................................2666.....1149    43%
sync.........................................2568......845    33%
syscall.....................................81252....38398    47%
testing/iotest...............................2444......302    12%
testing/quick...............................18890.....5076    27%
testing.....................................16502.....4800    29%
text/scanner.................................6849.....2052    30%
text/tabwriter...............................6607.....1863    28%
text/template/parse.........................22978.....6183    27%
text/template...............................64153....11518    18%
time........................................12103.....3546    29%
unicode......................................9706.....3320    34%
unicode/utf16................................1055......148    14%
unicode/utf8.................................1118......513    46%
vendor/golang.org/x/net/http2/hpack..........8905.....2636    30%

All packages                              3518505  1017774    29%

Change-Id: Id657334f276383ff1e6fa91472d3d1db5a03349c
Reviewed-on: https://go-review.googlesource.com/13937
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Chris Manghane <cmang@golang.org>
@gopherbot

This comment has been minimized.

Copy link
Author

gopherbot commented Oct 24, 2016

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

gopherbot pushed a commit that referenced this issue Oct 25, 2016

test: delete bugs directory
It appears to be a vestigial holding ground for bugs.
But we have an issue tracker, and #1909 is there and open.

Change-Id: I912ff222a24c51fab483be0c67dad534f5a84488
Reviewed-on: https://go-review.googlesource.com/31859
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.