108440 - JS array cycle crashes join and toString via infinite recursion

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[David "liorean" Andersson]

From Bugzilla Helper:
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.5) Gecko/20011011
BuildID:    2001101117

Placing a reference to an array variable inside the array variable crashes browser.

Reproducible: Always
Steps to Reproduce:
1.Open JSConsole
2.Write "var a=[];for(var i in window){alert(i)alert(a[a.length]=window[i])}" in
expression field.
3.Evaluate

(Same effect can be reached by including the same code in a webpage)

Actual Results:  Browser crashes after alerting 'a', in other words it crashes
when the variable itself is placed in the variable...

(Infinite loop perhaps? a contains a which contains a which contains a...)

Expected Results:  Break in execution, error of the style "Object can not
contain itself" thrown.

Comment 1

[David "liorean" Andersson]

Small typing error there:
"var a=[];for(var i in window){alert(i)alert(a[a.length]=window[i])}"
should be:
"var a=[];for(var i in window){alert(i);alert(a[a.length]=window[i])}"


After testing, "var a=[];alert(a[a.length]=a)" also crashes the browser.


The best handling of this would be to either throw an error telling me I'm
forbidden to insert an array into itself, or doing like IE: simply leave it empty.

Comment 2

[Boris Zbarsky [:bzbarsky]]

This would be an infinite loop all right:

#0  0x40066182 in array_join_sub (cx=0x87229c0, obj=0x8669dd8, sep=0x4011229c, 
    literalize=0, rval=0xbfe02114, localeString=0) at jsarray.c:317
#1  0x40066826 in array_toString (cx=0x87229c0, obj=0x8669dd8, argc=0,
argv=0x88d8fd0, 
    rval=0xbfe02114) at jsarray.c:493
#2  0x4009c632 in js_Invoke (cx=0x87229c0, argc=0, flags=2) at jsinterp.c:832
#3  0x4009c9cc in js_InternalInvoke (cx=0x87229c0, obj=0x8669dd8, fval=140241072, 
    flags=0, argc=0, argv=0x0, rval=0xbfe02240) at jsinterp.c:924
#4  0x400d0294 in js_TryMethod (cx=0x87229c0, obj=0x8669dd8, atom=0x8125ac8,
argc=0, 
    argv=0x0, rval=0xbfe02240) at jsobj.c:3369
#5  0x400ce4b2 in js_DefaultValue (cx=0x87229c0, obj=0x8669dd8, hint=JSTYPE_STRING, 
    vp=0xbfe02278) at jsobj.c:2888
#6  0x400fe99b in js_ValueToString (cx=0x87229c0, v=140942808) at jsstr.c:2566
#7  0x40066402 in array_join_sub (cx=0x87229c0, obj=0x8669dd8, sep=0x4011229c, 
    literalize=0, rval=0xbfe023a0, localeString=0) at jsarray.c:401
#8  0x40066826 in array_toString (cx=0x87229c0, obj=0x8669dd8, argc=0,
argv=0x88d8fc8, 
    rval=0xbfe023a0) at jsarray.c:493
#9  0x4009c632 in js_Invoke (cx=0x87229c0, argc=0, flags=2) at jsinterp.c:832
#10 0x4009c9cc in js_InternalInvoke (cx=0x87229c0, obj=0x8669dd8, fval=140241072, 
    flags=0, argc=0, argv=0x0, rval=0xbfe024cc) at jsinterp.c:924
#11 0x400d0294 in js_TryMethod (cx=0x87229c0, obj=0x8669dd8, atom=0x8125ac8,
argc=0, 
    argv=0x0, rval=0xbfe024cc) at jsobj.c:3369
#12 0x400ce4b2 in js_DefaultValue (cx=0x87229c0, obj=0x8669dd8, hint=JSTYPE_STRING, 
    vp=0xbfe02504) at jsobj.c:2888
#13 0x400fe99b in js_ValueToString (cx=0x87229c0, v=140942808) at jsstr.c:2566
#14 0x40066402 in array_join_sub (cx=0x87229c0, obj=0x8669dd8, sep=0x4011229c, 
    literalize=0, rval=0xbfe0262c, localeString=0) at jsarray.c:401
#15 0x40066826 in array_toString (cx=0x87229c0, obj=0x8669dd8, argc=0,
argv=0x88d8fc0, 
    rval=0xbfe0262c) at jsarray.c:493
#16 0x4009c632 in js_Invoke (cx=0x87229c0, argc=0, flags=2) at jsinterp.c:832
#17 0x4009c9cc in js_InternalInvoke (cx=0x87229c0, obj=0x8669dd8, fval=140241072, 
    flags=0, argc=0, argv=0x0, rval=0xbfe02758) at jsinterp.c:924
#18 0x400d0294 in js_TryMethod (cx=0x87229c0, obj=0x8669dd8, atom=0x8125ac8,
argc=0, 
    argv=0x0, rval=0xbfe02758) at jsobj.c:3369

Comment 3

[David "liorean" Andersson]

I was curious if this bug affected objects as well...
Code: "var a={};for(var i in window)a[i]=window[i];for(var i in
a)if(a[i]===a)alert('a['+i+'] === a');"

alerts 'a[a] === a', which means objects can do this without crashing browser,
unlike arrays.



Does this mean that a temporary way for me to deal with it could be to use an
object instead of an array? (/me goes coding a new constructor with all the
functionality of Array)

Comment 4

[Brendan Eich [:brendan]]

This is a regression, not sure since what change.  Both array and object
toString and similar methods have recursion prevention, but somehow, arrays are
busted.

/be

Comment 5

[Brendan Eich [:brendan]]

Correction, I meant the JS1.2-era, non-standard toSource methods -- both Array
and Object toSource safely deal with cycles, and correctly deal with cycles and
join points in object graphs using "sharp variables" (#n=, #n#).  But it appears
that Array.prototype.toString is unsafe, and what's more, ECMA-262 Edition 3 has
no helpful words about avoiding recursive death on a cycle.

/be

Comment 6

[Brendan Eich [:brendan]]

Attachment: proposed fix

Comment 7

[Brendan Eich [:brendan]]

This should be fixed for 0.9.6 -- you cc: list buddies r= and sr= soon, ok?

/be

Comment 8

[Brendan Eich [:brendan]]

IE does the same thing as this patch, at least for the trivial cycle case that
jst tested for me: it joins "" instead of recursively attempting to join the
array into itself.  I added a BUSY bit to the sharp object map value rather than
usurp SHARP, to simplify things (SHARP should be set via MAKE_SHARP(he) by a
caller of js_EnterSharpObject who finds on successful return (non-null he) that
the |chars| out param is non-null; |chars| will be a string of the form "#n="
initially; once MAKE_SHARP(he) has run, it will be "#n#").

The BUSY bit is used to detect a cycle.  It is set on a given sharp object map
entry |he| if not already set, and cleared after joining the array into a
string. If |he| is already marked BUSY upon js_EnterSharpObject successful
return, then array_join_sub must be active on the stack above the current
activation, i.e., a cycle has been detected and the empty string should be returned.

/be

Comment 9

[Brendan Eich [:brendan]]

So jst can read about what he helped test.

/be

Comment 10

[John Bandhauer]

Comment on attachment 56693 [details] [diff] [review]
proposed fix

sr=jband

Comment 11

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Comment on attachment 56693 [details] [diff] [review]
proposed fix

r=shaver. monkey >> ECMA.

Comment 12

[Brendan Eich [:brendan]]

Fixed.

/be

Comment 13

[Phil Schwartau]

Testcase added to JS testsuite:

           mozilla/js/tests/js1_5/Array/regress-108440.js

Before the fix, this crashed in both the optimized and debug SpiderMonkey 
shells, but passed in both the compiled and interpreted Rhino shells on WinNT. 
After the fix, it passes in both SpiderMonkey shells.

Marking VERIFIED FIXED.