260106 - elisions in array literals should not create properties (js1_5/Array/11.1.4.js)

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P3)

Description

[David "liorean" Andersson]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.0; rv:1.7.3) Gecko/20040911 Firefox/0.10
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.0; rv:1.7.3) Gecko/20040911 Firefox/0.10

If you do
    javascript:var i,a=[],b=[,null];for(i in b)a.push(i+': ('+typeof b[i]+')
'+b[i]);a.join(';\n');
you will get a listing of two members, '0' and '1'. However, only the '1' member
should actually be set on the array object, according to [ECMA-262 3ed] 11.1.4
Array Initialiser. Thus, only the '1' property should be listed.

Reproducible: Always
Steps to Reproduce:

Comment 1

[Brendan Eich [:brendan]]

This is easy to fix in jsemit.c, but then the decompiler is busted.  Analyzing
why shows a bytecode inefficiency: JSOP_INITPROP always unstacks an index
operand that is a compile-time uint16 constant, so it should have been folded
into the bytecode stream.  Given that, the decompiler could easily cope with the
obvious jsemit.c patch.

We could break bytecode compatibility (bumping the XUL fastload file version!),
and fix JSOP_INITPROP.  Or we could hack the decompiler harder to cope.  Not
sure which I prefer right now.  Shaver?

/be

Comment 2

[Brendan Eich [:brendan]]

Attachment: partial fix, leaves decompiler busted

The decompiler works for the testcase in the bug, but not any testcase that
uses two or more adjacent commas at the front of the array initializer's
element list, or anywhere after the beginning.

/be

Comment 3

[Bob Clary [:bc] (inactive)]

js/tests/js1_5/Array/11.1.4.js checked in.

Comment 4

[Brendan Eich [:brendan]]

*** Bug 311568 has been marked as a duplicate of this bug. ***

Comment 5

[Brendan Eich [:brendan]]

Igor, would you be willing to take this bug?  If not I'll get to it, but I thought you might have an interest, and I need to offload bugs from my list.

/be

Comment 6

[Igor Bukanov]

*** Bug 355602 has been marked as a duplicate of this bug. ***

Comment 8

[Igor Bukanov]

I am not working on the bug.

Comment 9

[Mike Shaver (:shaver emeritus)]

Upcoming patch in 322889 fixes this.

Comment 10

[Igor Bukanov]

(In reply to comment #9)
> Upcoming patch in 322889 fixes this.

This bug has nothing to do with the array implementation. It comes from the fact that the generated bytecode for array literals uses JSOP_PUSH to push void for the corresponding array element instead of spiking it. It is not straightforward to fix the bug as it would require to fix the docimpiler. 

js> dis(function() { return [, "x"]; })
flags: LAMBDA INTERPRETED
main:
00000:  newinit 3
00002:  zero
00003:  push
00004:  initelem
00005:  one
00006:  string "x"
00009:  initelem
00010:  endinit
00011:  return
00012:  stop

Source notes:
js> uneval([, "x"])
[(void 0), "x"]
 

Comment 11

[Mike Shaver (:shaver emeritus)]

I don't know why you say it has nothing to do with the array implementation: by changing the array implementation to be dense and use JSVAL_HOLE for missing properties, along with JSOP_NEWARRAY for fast literal creation, we can "trivially" fix the decompilation issues as well as making things a fair bit faster.  Once the dense array parts land, it will be easy to make such a codegen change (the patch in 322889 uses Array() as a stand-in for JSOP_NEWARRAY, which breaks decompilation, but that part will be split out before landing; it's just useful for eyeballing the gains of the complete fix set).

Comment 12

[Igor Bukanov]

(In reply to comment #11)
> I don't know why you say it has nothing to do with the array implementation: 

The code generator currently translates [, 1] into the same bytecode as it would for [undefined, 1]. Thus changing the array implementation would not help here.

> along with JSOP_NEWARRAY for fast literal creation, we can
> "trivially" fix the decompilation issues as well...

But JSOP_NEWARRAY is not related to how the array is implemented, or do you mean that it would go into the same bug?

Comment 13

[Brendan Eich [:brendan]]

shaver meant he would fix it in the other bug's patch, not that it's formally related. But comment 12 raises a good point: this bug could be used to land just JSOP_HOLE, to reduce patch size in the other bug and spread regression testing.

/be

Comment 14

[Mike Shaver (:shaver emeritus)]

Yeah, I have that patch in a separate hg branch right now; I can finish independently rather than merge, in the name of better software engineering.  Thanks, all!

Comment 15

[Mike Shaver (:shaver emeritus)]

Attachment: JSOP_HOLE

Wafer-thin, really.

Comment 16

[Igor Bukanov]

(In reply to comment #15)
> Created an attachment (id=298301) [details]
> JSOP_HOLE

This is incomplete. There is no decompiler changes. Plus I am not sure that JSOP_HOLE should do anything with the stack. I.e. it may be an empty instructions just for the decompiler.

Comment 17

[Mike Shaver (:shaver emeritus)]

Attachment: JSOP_HOLE incl. decompilation

Quite, missed a file in the diff.

This was the minimal code change, and it's no worse performance than what we have today.  I don't want to invest too much in the initelem path, because I plan to destroy it once the array-ops stuff is done, in favour of JSOP_NEWARRAY.

Comment 18

[Mike Shaver (:shaver emeritus)]

Comment on attachment 298306 [details] [diff] [review]
JSOP_HOLE incl. decompilation

Bah, trailing elisions don't work, because we don't update .length when we skip the hole.

Comment 19

[Mike Shaver (:shaver emeritus)]

JSOP_NEWARRAY will just be immune to this, because it has an explicit length in the form of its argument, so I'll probably go that route here, instead of this minimalism.

Comment 20

[Brian Crowder]

This is fixed by shavarrays, yes?

Comment 21

[Blake Kaplan (:mrbkap) (inactive)]

js> dis(function() [,null])
flags: LAMBDA EXPR_CLOSURE INTERPRETED
main:
00000:  newinit 3
00002:  zero
00003:  push
00004:  initelem
00005:  one
...

suggests not (what happened to JSOP_NEWARRAY?).

Comment 22

[Mike Shaver (:shaver emeritus)]

JSOP_NEWARRAY hasn't happened yet, Waldo was going to give it a spin, suspect he got too busy.  I could try for it for b5, but probably wait until 3.1 at this rate.

Comment 23

[Brian Crowder]

I only ended up looking at this at all because it affects ACID3

Comment 24

[Brendan Eich [:brendan]]

Attachment: proposed fix

Passes js testsuite.

I made JSOP_NEWARRAY able to express all non-comprehension, non-sharp array initialisers (so JOF_UINT24 format -- big is back!). This requires the js_EmitN helper to skip UpdateDepth until its caller has filled in the immediate 3 bytes, at which point the caller is obligated to call UpdateDepth. If this comes up again, let's have js_Emit4 -- with only JSOP_NEWARRAY using the format in a way where stack use-count depends on immediate operand value, I did not want to add that helper).

See also the latent bug fixed in JSOP_INITELEM -- FETCH_ELEMENT_ID was being called before obj was set! Of course, that macro uses obj only in the id-is-object E4X freak-o case, so this didn't matter AFAIK. Handling JSVAL_HOLE in JSOP_INITELEM requires care.

/be

Comment 25

[Brendan Eich [:brendan]]

Passes js testsuite with js1_5/Array/11.1.4.js passing now, I should say. I checked a reference shell against the same pull of the testsuite for a baseline.

/be

Comment 26

[Brendan Eich [:brendan]]

This is worth doing more for array initialiser (scripted JSON, e.g.) perf, and to avoid O(n^2) badness in the decompiler on very large JSOP_NEWINIT-compiled array initialisers, than for ACID3 -- IMHO.

/be

Comment 27

[Brendan Eich [:brendan]]

Attachment: fix auto-parenthesization bug

With the last patch:

js> function f(a,b,c,d)[(a,b),(c,d)]
js> f
function f(a, b, c, d) [(a, b), , d)(c, d)];

With this patch:

js> function f(a,b,c,d)[(a,b),(c,d)]
js> f
function f(a, b, c, d) [(a, b), (c, d)];

The fix is to consult the stacked offsets from the array initialiser's elements' decompilations as they were recorded in ss->offsets. We can't dead-reckon our way through ss->sprinter's buffer by adding todo + PAREN_SLOP to from, because those elements that required auto-parenthesization consumed paren-slop and moved. You can see this in the buggy output.

/be

Comment 28

[Bob Clary [:bc] (inactive)]

(In reply to comment #20)
> This is fixed by shavarrays, yes?
> 

no. as can be seen in public-failures.txt.

Comment 29

[Mike Shaver (:shaver emeritus)]

Comment on attachment 307645 [details] [diff] [review]
fix auto-parenthesization bug

r=shaver if this mochis well, and you make sure we have test-suite coverage for ending holes, .length, and enumeration!

Comment 30

[Bob Clary [:bc] (inactive)]

Attachment: js1_8/decompilation/regress-260106.js

Comment 31

[Mike Shaver (:shaver emeritus)]

I think this is an ecma/ bug, since the property behaviour is specified there.  The javascript: URL for this bug would fit better for that than a decompilation one, though, since decompilation isn't specified to that detail by ECMA.

Alternatively:

expected = false
actual = ("1" in [0,,2]);

Comment 32

[Bob Clary [:bc] (inactive)]

(In reply to comment #31)

> expected = false
> actual = ("1" in [0,,2]);
> 

does js1_5/Array/11.1.4.js cover this and the javascript url sufficiently?

Comment 33

[Mike Shaver (:shaver emeritus)]

Oh, um, yes.  Should be in ecma/ for purity, possibly, but I'm not going to get too worked up about that.

Comment 34

[Mike Schroepfer]

So should we take this final patch?

Comment 35

[Brendan Eich [:brendan]]

Let me update the patch, re-test in js/tests and mochitest, and go for it.

/be

Comment 36

[Ryan VanderMeulen [:RyanVM]]

Brendan, is this still on the radar for b5?

Comment 37

[Bob Clary [:bc] (inactive)]

/cvsroot/mozilla/js/tests/js1_8/decompilation/regress-260106.js,v  <--  regress-260106.js
initial revision: 1.1

Comment 38

[Brendan Eich [:brendan]]

Where's my .next TM?

/be

Comment 39

[Mike Schroepfer]

Can we land in mozilla-central?

Comment 40

[Brendan Eich [:brendan]]

Attachment: fix patch updated to mozilla-central

Looking for a quick re-review, after which I'll land. Passes the regression test, building Firefox now...

/be

Comment 41

[Mike Shaver (:shaver emeritus)]

Comment on attachment 323763 [details] [diff] [review]
fix patch updated to mozilla-central

r=shaver, but please add a FIXME and follow-up bug extending js_NewArrayObject to take a count parameter (or "there are holes, go count 'em" parameter flag?), so that JSSLOT_ARRAY_COUNT is correct.  We'll need that to be correct for the enumeration optimization that's upcoming.

Comment 42

[Brendan Eich [:brendan]]

Attachment: patch on top of previous to maintain dense count

This was easy (yay C++ default parameters). It doesn't seem worth optimizing hole counting away with a fancier JSOP_NEWARRAY that conveys count through to runtime, given how rare holes in initialisers are, and how initialisers tend to be short.

One patch per bug means multiple commits to local hg db -- love it. Let me know if you want a single consolidated patch.

/be

Comment 43

[Brendan Eich [:brendan]]

Comment on attachment 307645 [details] [diff] [review]
fix auto-parenthesization bug

Obsolete cuz out of date and cvs.m.o based.

/be

Comment 44

[Brendan Eich [:brendan]]

Attachment: better followup patch to maintain dense count

Avoid copying and then iterating over vector again in the common (script-induced, i.e., array initialiser) case. Holes are rare, but array initialiser can be long where perf counts.

/be

Comment 45

[Mike Shaver (:shaver emeritus)]

Comment on attachment 323945 [details] [diff] [review]
better followup patch to maintain dense count

>@@ -2348,7 +2359,8 @@ array_concat(JSContext *cx, uintN argc, 
>     /* Create a new Array object and root it using *vp. */
>     aobj = JS_THIS_OBJECT(cx, vp);
>     if (OBJ_IS_DENSE_ARRAY(cx, aobj)) {
>-        nobj = js_NewArrayObject(cx, ARRAY_DENSE_LENGTH(aobj), aobj->dslots);
>+        nobj = js_NewArrayObject(cx, ARRAY_DENSE_LENGTH(aobj), aobj->dslots,
>+                                 JS_TRUE);

Holes are rare, and we know we don't have any if COUNT == LENGTH, so we can avoid walking and counting in that (common) case.

r=shaver with a tested change to compute holey from count-vs-length.

Comment 46

[Brendan Eich [:brendan]]

Attachment: final followup patch

Had to go over this with shaver on IRC, found a couple of things:

* EnsureLength may over-allocate, see the comment.
* shaver thought of "capacity" as better name than "dense length" -- works4me.

Followup bug fodder?

/be

Comment 47

[Mike Shaver (:shaver emeritus)]

Comment on attachment 324096 [details] [diff] [review]
final followup patch

r=shaver, thanks for the comment

Comment 48

[Brendan Eich [:brendan]]

Fixed (is this helpful? I used to cite CVS revs, but this seems noisy):

97d743dcdfe7
2008-06-06 13:23 -0700	Brendan Eich - Third and final followup patch for bug 260106.

aba6549b72d1
2008-06-05 16:00 -0700	Brendan Eich - Followup patch for bug 260106.

ddfa674923bd
2008-06-04 17:00 -0700	Brendan Eich - Fix 260106, r=shaver.

/be

Comment 49

[Brendan Eich [:brendan]]

Reopened. Broke Windows due to obscure codegen and/or interpreter stack imbalance problem not caught by codegen stack modeling (see bug 419743), and also by a bug in the JSON encoder that this fix exposes (bug 437724).

/be

Comment 50

[Bob Clary [:bc] (inactive)]

what more needs to be done with this bug? I am showing the test js1_5/Array/11.1.4.js passing on 1.9.1 now and js1_8/decompilation/regress-260106.js
 passing 1.9.0 and 1.9.1.

Comment 51

[Brendan Eich [:brendan]]

This bug should be marked FIXED and a followup filed to get JSOP_NEWARRAY emitted (after debugging any latent bug that remains in the wake of Igor's fix for bug 449494).

Bob, can you verify this? Resolving now, I'll try to test JSOP_NEWARRAY soon (the latent bug bit on Windows only).

/be

Comment 52

[Bob Clary [:bc] (inactive)]

verified 1.9.1 linux/mac/windows

Comment 53

[Jeff Walden [:Waldo]]

Comment 51 is now bug 466905.