cmd/compile: infinite recursion generating symbol for recursive type #1909
Labels
NeedsInvestigation
Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone
Comments
|
Labels changed: added priority-medium, compilerbug. Owner changed to @rsc. Status changed to Accepted. |
|
Owner changed to @lvdlvd. |
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:-
https://golang.org/cl/5504108/
|
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 https://golang.org/cl/5523047 |
|
This issue was closed by revision aa63a92. Status changed to Fixed. |
|
This issue was closed by revision 8a4bd09. Status changed to Fixed. |
Pending in https://golang.org/cl/5523047/, but that still needs a fix to exp/types/gcimporter. |
|
Owner changed to [email protected]. |
|
Owner changed to @lvdlvd. |
|
This issue was closed by revision 9523b4d. Status changed to Fixed. |
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 |
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).
|
See also issue #6589. |
CL https://golang.org/cl/147220043 mentions this issue. |
josharian
added a commit
to josharian/go
that referenced
this issue
Dec 18, 2014
* 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
* 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
* 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 <[email protected]>
|
CL https://golang.org/cl/13937 mentions this issue. |
|
There are (at least) two endless recursive function calls involved here:
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
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 <[email protected]>
Reviewed-by: Chris Manghane <[email protected]>
|
CL https://golang.org/cl/31859 mentions this issue. |
gopherbot
pushed a commit
that referenced
this issue
Oct 25, 2016
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 <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
by [email protected]:
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 i386The text was updated successfully, but these errors were encountered: