Tcl Source Code

View Ticket
Login
Ticket UUID: c31f72813b3966d13deb165f957033d514acd99
Title: Tcl crashes when calculating the string representation of deep nested lists
Type: Bug Version: 8.5.13/8.6.0/8.6.1
Submitter: JKU Created on: 2013-11-08 19:14:10
Subsystem: 14. List Object Assigned To: dgp
Priority: 6 Severity: Severe
Status: Open Last Modified: 2013-11-09 07:41:58
Resolution: None Closed By: nobody
    Closed on:
Description:

Tcl crashes with a SEGFAULT when calculating the string representation of a deeply nested list.

Code to reproduce:

set a a
for {set i 0} {$i < 100000} {incr i} {
    set a [list $a]
}
puts $a

If it does not crash, use a higher number.

User Comments: dkf added on 2013-11-09 07:41:58:

Reproduced with supplied script using system 64-bit build of 8.5.9 on OSX.

I don't think the fix I used for deallocation will work here; there's no practical tail-calll decomposition that I can think of offhand. That's because — in general — you can only compute the string representation of a list from the string representations of the pieces, and can't assume that the operation is a no-op. The amount of code it would take to make this specific case work would be substantial, and setting a to “a a” initially would sidestep all that work.

Assigning to dgp; he's thought more about limits than I have.

Curious fact: I actually got a SIGSEGV when running this, and not a SIGBUS. That's pretty rare actually. It must've run out of stack space in an unusual way.


JKU added on 2013-11-08 19:21:06:

Relevant Tcler Chat:

<Johannes13> set a a; for {set i 0} {$i < 10000} {incr i} {set a [list $a]}; set a
<suchenwi> Should be idempotent, on 1-word lists without spaces:
<suchenwi> (Videos) 1 % set a a
<suchenwi> a
<suchenwi> (Videos) 2 % set a [list $a]
<suchenwi> a
<suchenwi> (Videos) 3 % set a [list $a]
<suchenwi> a
<Johannes13> suchenwi: on my machine Tcl crashes.
<suchenwi> johannes13: let me try here...
<suchenwi> suchenwi@suchenwi-NC10:~$ tclsh
<suchenwi> % set a a;for {set i 0} {$i<10000} {incr i} {set a [list $a]}; set a
<suchenwi> a
<suchenwi> % info patch
<suchenwi> 8.5.13
<Johannes13> increase the interations..
<suchenwi> johannes13: works here as expected, Lubuntu 13.04
<suchenwi> johannes13: with 1000000 it crashes indeed.
<suchenwi> rlwrap: warning: tclsh killed by SIGSEGV (core dumped).
<suchenwi> rlwrap has not crashed, but for transparency,
<suchenwi> it will now kill itself with the same signal
<suchenwi> Speicherzugriffsfehler (Speicherabzug geschrieben)
<Johannes13> it crashes when calculating the string representation of a list of a list of a list...
<jima> a really good compiled would have guessed the answer without iterating?
<Zarutian> rereads what Johannes13 and suchenwi saids
<Zarutian> -s
<jima> s/compiled/compiler
<thommey> yes, it does create a nested list structure
<Zarutian> Johannes13: got a core dump from the crash?
<Johannes13> no, windows..
<Zarutian> oh, right
<thommey> { set a [list $a]; set a [string range $a 0 end] } works ;)
* Zarutian tries to recall what that system event viewer is called in windows
<suchenwi> The crash happens between 40000 and 43000 iterations.
<thommey> stack explosion probably, the backtrace is thousands of iterations of Tcl_GetStringFromObj -> Tcl_GetString -> UpdateStringOfList -> Tcl_GetStringFromObj
<suchenwi> But it's not descending in recursion, it iterates flatly...
* jon8 hat die Verbindung getrennt (Remote host closed the connection)
<thommey> the C function calls recurse
<suchenwi> ah
<thommey> the "set a" triggers it, generating the string rep, it doesn't have any issues building the nested list
<evilotto> that crash is surprising to me at least...
<Johannes13> exactly.
<thommey> (until a certain higher nesting limit I assume)
<miguel> thommey: reminds of a similar problem we had on freeing such lists (discovered by salvatore iirc) - dkf fixed that
<ijchain> <miguel> do file a bug, assign it to dkf
<giftpflanze> gawd, i'm so stupid
<laomaiweng>  Also crashes with 100000 on 8.6.1.
<thommey> -> Johannes13 :P

So I assigned it to dkf...