350531 - use precedence-based parenthesization (was: uneval function (){ return (@['a'])=='b'})

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Biju]

by running Jesse's fuzzer (see bug 349611 ) found following....

Case 1

uneval:-

function (){
 return (@['a'])=='b'
}


gives ==>
function () {
    return @[""b" == "b";
}



Case 2

uneval:-

function (){
 return (@['a']).toXMLString()
}

gives ==>
function () {
    return @["toXMLString.toXMLString();
}




Case 3

uneval:-

function (){
 return (@[1]).toXMLString()
}

gives ==>

function () {
    return @[1toXMLString.toXMLString();
}



(PS: case 3 is of no use it is better to give a compile time syntax error)



a useage eg. for these function is:-

x = <x><y a="a"><p/></y><y a="b"><q/></y><y a="c"><r/></y></x>;

x.y.((function (){
 return (@['a'])=='b'
})())


to give ==>

<y a="b">
  <q/>
</y>

Comment 1

[Biju]

see bug 350532 for not showing syntax error on 

function (){
 return (@[1]).toXMLString()
}

Comment 2

[Brendan Eich [:brendan]]

Attachment: fix

This is a very ancient bug.  I'm not sure why it didn't bite noticeably until now.

Fix is to avoid popping at all, and then wrongly leaving the unparenthesized expression popped(!) if it doesn't need to be reparenthesized by the decompiler's precedence judgment.  Instead, only if parens are needed do we (a) retract (the buffer primitive underlying pop); (b) overwrite via Sprint.

Sprint is memory-safe, rval is computed from a previous Sprint, so the whole combination is memory-safe.

/be

Comment 3

[Brendan Eich [:brendan]]

This seems bad enough to want to fix in 1.8.1 -- explicit parens in source can break Function.prototype.toString.

/be

Comment 4

[Brendan Eich [:brendan]]

Comment on attachment 235856 [details] [diff] [review]
fix

Oops, can't retract and then set todo non-negative, as that will push on top of the stacked offset indexing rval...

/be

Comment 5

[Brendan Eich [:brendan]]

Attachment: so much simpler

The decompiler already knows how to parenthesize where needed.  All JSOP_GROUP need do is replace its opcode with lastop and let the consumer of its result do the parenthesizing, if necessary.

/be

Comment 6

[Brendan Eich [:brendan]]

Comment on attachment 235862 [details] [diff] [review]
so much simpler

The hacking of op (setting it to JSOP_NOP, or for JSOP_SETPROP, to JSOP_GETPROP) breaks this nice patch.

/be

Comment 7

[Brendan Eich [:brendan]]

Attachment: last patch, plus cleanup using saveop

The deal is that too many cases hack op, but the top of the loop sets saveop = op, so we can use saveop when pushing todo at the bottom of the loop.  This requires a few changes to update saveop when unrolling the loop in individual cases.

/be

Comment 8

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 235869 [details] [diff] [review]
last patch, plus cleanup using saveop

>+                JS_ASSERT(ss->top);

LOCAL_ASSERT? r=mrbkap

Comment 9

[Brendan Eich [:brendan]]

Attachment: permcomb.js, after the classic Python permcomb.py

This is loaded by the next attachment, the test script ops.js.

/be

Comment 10

[Brendan Eich [:brendan]]

Attachment: exhaustively test parenthesization of binary operator combinations

This test all combinations of 2 to 5 operators for correct parenthesization.  It doesn't bother with the unary ops, and ?: needs special care (and another bugfix, so new patch coming, which builds on the previous patch -- warning: it renumbers precedences in jsopcode.tbl).

/be

Comment 11

[Brendan Eich [:brendan]]

Attachment: permcomb.js, after the classic Python permcomb.py, v2

Just a few optimizations (while one can't test ![] to get true, !list.length does detect the empty array and empty string, so is generic enough) and another JS beef vis a vis Python (lack of range, if not xrange).

/be

Comment 12

[Brendan Eich [:brendan]]

Attachment: permcomb.js, v3

Forgot that I did manage to get String.prototype.concat added, so it's just an append analogue that String lacks.

/be

Comment 13

[Brendan Eich [:brendan]]

Attachment: exhaustively test parenthesization of binary operator subsets

This works with the patch I'll attach soon.  Still need ?: test coverage.

/be

Comment 14

[Brendan Eich [:brendan]]

Attachment: Use operator precedence fully to automate and regularize parenthesization in the decompiler

The jsopcode.tbl diff requires careful reading, or a perl script I may hack up to show consistent expansion of precedence to insert new low levels for comma and the assignment ops.

/be

Comment 15

[Brendan Eich [:brendan]]

Comment on attachment 236581 [details] [diff] [review]
Use operator precedence fully to automate and regularize parenthesization in the decompiler

This does not regress bug 349499, although it fixes it differently and more generally.

/be

Comment 16

[Brendan Eich [:brendan]]

Attachment: Fix, v2

I hacked a perl script to automate incrementing precedence levels to insert new or missing operators, and found some errors in the last patch.

/be

Comment 17

[Brendan Eich [:brendan]]

Here's that perl script:

while (<>) {
    if (/^OPDEF/) {
        /(1[0-9]|[1-9])(?=, *JOF_)/;
        $prec = $1;
        if ($prec == 1) {
            $prec += 2;
        } elsif ($prec > 1) {
            $prec += 5;
        }
        s/(1[0-9]|[1-9])(?=, *JOF_)/$prec/;
    }
    print "$_";
}

Here is a commented plain diff of running that perl script on a top-of-trunk jsopcode.tbl against the jsopcode.tbl from the latest patch, excluding the first hunk that contains the precedence table comment:

80c104
< OPDEF(JSOP_IFEQ,      7,  "ifeq",       NULL,         3,  1,  0,  0,  JOF_JUMP|JOF_DETECTING)
---
> OPDEF(JSOP_IFEQ,      7,  "ifeq",       NULL,         3,  1,  0,  4,  JOF_JUMP|JOF_DETECTING)

JSOP_IFEQ is for ?:, which has precedence 4 (after assignment, before ||).

84c108
< OPDEF(JSOP_ARGUMENTS, 9, js_arguments_str, js_arguments_str, 1, 0, 1, 17, JOF_BYTE)
---
> OPDEF(JSOP_ARGUMENTS, 9, js_arguments_str, js_arguments_str, 1, 0, 1, 18, JOF_BYTE)

Old too-low-by-one bug in JSOP_ARGUMENTS' precedence.

147,148c171,172
< OPDEF(JSOP_OR,        68, "or",         NULL,         3,  1,  0,  0,  JOF_JUMP|JOF_DETECTING)
< OPDEF(JSOP_AND,       69, "and",        NULL,         3,  1,  0,  0,  JOF_JUMP|JOF_DETECTING)
---
> OPDEF(JSOP_OR,        68, "or",         NULL,         3,  1,  0,  5,  JOF_JUMP|JOF_DETECTING)
> OPDEF(JSOP_AND,       69, "and",        NULL,         3,  1,  0,  6,  JOF_JUMP|JOF_DETECTING)

|| and && have precedence levels 5 and 6 now.

172c196
< OPDEF(JSOP_POP,       81, "pop",        NULL,         1,  1,  0,  0,  JOF_BYTE)
---
> OPDEF(JSOP_POP,       81, "pop",        NULL,         1,  1,  0,  2,  JOF_BYTE)

JSOP_POP when annotated with a SRC_PCDELTA is a comma operator, which comes after let and before assignment.

280c304
< OPDEF(JSOP_SETLOCALPOP, 130, "setlocalpop", NULL,     3,  1,  0,  0,  JOF_LOCAL|JOF_NAME|JOF_SET)
---
> OPDEF(JSOP_SETLOCALPOP, 130, "setlocalpop", NULL,     3,  1,  0,  3,  JOF_LOCAL|JOF_NAME|JOF_SET)

Assignment + pop, should have precedence level 3 (assignment) -- I've fixed this here but it's wrong in the patch that I just attached.  Reattaching.

306,307c330,331
< OPDEF(JSOP_ARGSUB,      136,"argsub",     NULL,       3,  0,  1, 18,  JOF_QARG |JOF_NAME)
< OPDEF(JSOP_ARGCNT,      137,"argcnt",     NULL,       1,  0,  1, 18,  JOF_BYTE)
---
> OPDEF(JSOP_ARGSUB,      136,"argsub",     NULL,       3,  0,  1, 17,  JOF_QARG |JOF_NAME)
> OPDEF(JSOP_ARGCNT,      137,"argcnt",     NULL,       1,  0,  1, 17,  JOF_BYTE)

Related to JSOP_ARGUMENTS precedence bug noted above.

318c342
< OPDEF(JSOP_IFEQX,         140,"ifeqx",    NULL,       5,  1,  0,  0,  JOF_JUMPX|JOF_DETECTING)
---
> OPDEF(JSOP_IFEQX,         140,"ifeqx",    NULL,       5,  1,  0,  3,  JOF_JUMPX|JOF_DETECTING)

Extended-jump form of JSOP_IFEQ, for *really big* ?: expressions.

320,321c344,345
< OPDEF(JSOP_ORX,           142,"orx",      NULL,       5,  1,  0,  0,  JOF_JUMPX|JOF_DETECTING)
< OPDEF(JSOP_ANDX,          143,"andx",     NULL,       5,  1,  0,  0,  JOF_JUMPX|JOF_DETECTING)
---
> OPDEF(JSOP_ORX,           142,"orx",      NULL,       5,  1,  0,  5,  JOF_JUMPX|JOF_DETECTING)
> OPDEF(JSOP_ANDX,          143,"andx",     NULL,       5,  1,  0,  6,  JOF_JUMPX|JOF_DETECTING)

Similarly.

388c412
< OPDEF(JSOP_LITOPX,        191,"litopx",     NULL,     5,  0,  0, 18,  JOF_LITOPX)
---
> OPDEF(JSOP_LITOPX,        191,"litopx",     NULL,     5,  0,  0,  0,  JOF_LITOPX)

JSOP_LITOPX is a prefix op, so its precedence doesn't matter.

395c419
< OPDEF(JSOP_SETMETHOD,     194,"setmethod",   NULL,    3,  2,  1,  3,  JOF_CONST|JOF_PROP)
---
> OPDEF(JSOP_SETMETHOD,     194,"setmethod",   NULL,    3,  2,  1,  3,  JOF_CONST|JOF_PROP|JOF_SET|JOF_ASSIGNING|JOF_DETECTING)

Forgot a bunch of format flags.

445,446c469,470
<  * LEAVEBLOCKEXPR's precedence is 1 to help the decompiler with new let (...)
<  * expressions. See bug 349499.
---
>  * Variant of JSOP_LEAVEBLOCK has a result on the stack above the locals,
>  * which must be moved down when the block pops.
448c472
< OPDEF(JSOP_LEAVEBLOCKEXPR,215,"leaveblockexpr",NULL,  3,  0,  0,  3,  JOF_UINT16)
---
> OPDEF(JSOP_LEAVEBLOCKEXPR,215,"leaveblockexpr",NULL,  3,  0,  0,  1,  JOF_UINT16)

A let (x = y) z, w (e.g.) is the lowest-precedence expression, since it parses a comma expression after the head.

Since JSOP_POP is used for other cases than comma operators, the decompiler logic there has to avoid auto-parenthesizing most pops, re-enabling when the SRC_PCDELTA has been discerned.

/be

Comment 18

[Brendan Eich [:brendan]]

Attachment: Fix, v3

Comment 19

[Brendan Eich [:brendan]]

Bugzilla's interdiff works between versions 1, 2 and 3 -- hope it helps.  You might want to run the perl script for yourself and then plain-diff.

/be

Comment 20

[Brendan Eich [:brendan]]

Fixed on trunk.

/be

Comment 21

[Brendan Eich [:brendan]]

Comment on attachment 236678 [details] [diff] [review]
Fix, v3

This fixes not only the reported bug, but several other bugs to do with parenthesization.  The exhaustive test (I'll update this bug with an even more exhaustive test version tomorrow) shows safety and covers all combinations -- more than the fuzz tester may by chance, unless run for a very long time.

/be

Comment 22

[Bob Clary [:bc] (inactive)]

exhaustive test parenthesization of binary operator subsets:
Checking in regress-350531.js;
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-350531.js,v  <--  regress-350531.js
initial revision: 1.1

from earlier today in browser and shell this reported
BROKEN! input: (function () {x |= x = x;}) output: (function () {x |= (x = x);})

but in a recent pull and shell test this test locks up and hangs.

Am adding the other tests from Biju in a moment.

Comment 23

[Bob Clary [:bc] (inactive)]

Checking in regress-350531.js;
/cvsroot/mozilla/js/tests/e4x/Regress/regress-350531.js,v  <--  regress-350531.js
initial revision: 1.1

Comment 24

[Bob Clary [:bc] (inactive)]

reopen due to hang.

Comment 25

[Mike Schroepfer]

Does this mean we should delay this patch for 1.8 branch?

(In reply to comment #24)
> reopen due to hang.
> 

Comment 26

[Bob Clary [:bc] (inactive)]

I was wrong. If you let the test continue it will eventually complete.

Comment 27

[Brendan Eich [:brendan]]

Anomalously long shell execution is probably due to GC, but it's not happening on Mac OS X.  Need profiling or poor-man's profiling (interrupt in debugger during the "hang", note call stacks, find longest common stack prefix).  Separate bug if needed.

This patch is clean ;-).

/be

Comment 28

[Brendan Eich [:brendan]]

Again the exhaustive test uses permcomb.py's subset to compute all permutations of operators taking m at a time, for m from 2 to 4.  That uses n!/(m!(n-m)!) for n the number of operators (aops.length) and m from 2 to 4.  Lots of temporaries, a fair amount of garbage to collect.

/be

Comment 29

[Brendan Eich [:brendan]]

Note separate one-line followup patch in bug 351597.

/be

Comment 30

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 236678 [details] [diff] [review]
Fix, v3

a=beltzner on behalf of 181drivers

Comment 31

[Brendan Eich [:brendan]]

Fixed on the 1.8 branch.

/be

Comment 32

[Bob Clary [:bc] (inactive)]

e4x/Regress/regress-350531.js
pass 1.8 20060909 windows/mac*/linux
pass 1.9 20060909 mac*/linux

I show time outs (900 seconds) for the 1.9 windows opt and dbg browser tests but the other OS completed quickly and testing with my local winxp builds complete quickly. 

js1_5/Regress/regress-350531.js
all 1.8 1.9 builds time out.

I'll have to verify this manually later.

Comment 33

[Jesse Ruderman]

Attachment: faster combo()

This version of combo() acts as a generator and avoids copying the array (and recursing).  It's about 30 times faster; I think most of the speed gain is due to avoiding copying.

Comment 34

[Brendan Eich [:brendan]]

At this point, I would appreciate two spin-off bugs:

1.  Write a complete, correct exhaustive operator-grammar decompiler tester.  This could use an optimized version of subset to good effect.  It should handle unary operators as well as binary, plus let, function, and ?: of course.

2.  Optimize slicing via copy-on-write so that Jesse's optimization (which btw does not work on strings, but could with a small fix) is not necessary.

Who will file these?  Who wants to fix 'em?  They're both fun.

/be

Comment 35

[Bob Clary [:bc] (inactive)]

verified fixed 1.8 20060916 windows/linux

Comment 36

[Robert Sayre]

(In reply to comment #34)
> 1.  Write a complete, correct exhaustive operator-grammar decompiler tester. 
> This could use an optimized version of subset to good effect.  It should handle
> unary operators as well as binary, plus let, function, and ?: of course.

Bug 353055.

> 2.  Optimize slicing via copy-on-write so that Jesse's optimization (which btw
> does not work on strings, but could with a small fix) is not necessary.

Bug 353054.

Comment 37

[Bob Clary [:bc] (inactive)]

verified 1.9 20060921 windows/linux

Comment 38

[Bob Clary [:bc] (inactive)]

reduce test output not related to success/failure

Checking in regress-350531.js;
/cvsroot/mozilla/js/tests/js1_5/extensions/regress-350531.js,v  <--  regress-350531.js
new revision: 1.2; previous revision: 1.1