Closed Bug 350531 Opened 14 years ago Closed 13 years ago

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

Categories

(Core :: JavaScript Engine, defect, P1)

All
Windows XP
defect

Tracking

()

VERIFIED FIXED
mozilla1.8.1

People

(Reporter: BijuMailList, Assigned: brendan)

References

(Blocks 1 open bug, )

Details

(Keywords: verified1.8.1)

Attachments

(4 files, 8 obsolete files)

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>
see bug 350532 for not showing syntax error on 

function (){
 return (@[1]).toXMLString()
}
Attached patch fix (obsolete) — Splinter Review
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
Assignee: general → brendan
Status: NEW → ASSIGNED
Attachment #235856 - Flags: review?(mrbkap)
Attachment #235856 - Flags: review?(sayrer)
This seems bad enough to want to fix in 1.8.1 -- explicit parens in source can break Function.prototype.toString.

/be
Priority: -- → P1
Hardware: PC → All
Target Milestone: --- → mozilla1.8.1
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
Attachment #235856 - Attachment is obsolete: true
Attachment #235856 - Flags: review?(sayrer)
Attachment #235856 - Flags: review?(mrbkap)
Blocks: 350417
Attached patch so much simpler (obsolete) — Splinter Review
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
Attachment #235862 - Flags: review?(mrbkap)
Attachment #235862 - Flags: approval1.8.1?
Attachment #235862 - Flags: review?(sayrer)
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
Attachment #235862 - Attachment is obsolete: true
Attachment #235862 - Flags: review?(sayrer)
Attachment #235862 - Flags: review?(mrbkap)
Attachment #235862 - Flags: approval1.8.1?
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
Attachment #235869 - Flags: review?(mrbkap)
Attachment #235869 - Flags: review?(sayrer)
No longer blocks: 350417
Comment on attachment 235869 [details] [diff] [review]
last patch, plus cleanup using saveop

>+                JS_ASSERT(ss->top);

LOCAL_ASSERT? r=mrbkap
Attachment #235869 - Flags: review?(mrbkap) → review+
Attachment #235869 - Flags: review?(sayrer) → review+
This is loaded by the next attachment, the test script ops.js.

/be
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
Attachment #235869 - Attachment is obsolete: true
Attachment #235990 - Attachment description: permcomb.js, after the classic Python permcomp.py → permcomb.js, after the classic Python permcomb.py
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
Attachment #235990 - Attachment is obsolete: true
Attached file 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
Attachment #236016 - Attachment is obsolete: true
This works with the patch I'll attach soon.  Still need ?: test coverage.

/be
Attachment #235991 - Attachment is obsolete: true
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
Attachment #236581 - Flags: review?(mrbkap)
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
Attachment #236581 - Flags: review?(sayrer)
Attachment #236581 - Attachment description: Use operator precedence as much as possible to automate and regularize parenthesization in the decompiler → Use operator precedence fully to automate and regularize parenthesization in the decompiler
Attached patch Fix, v2 (obsolete) — Splinter Review
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
Attachment #236581 - Attachment is obsolete: true
Attachment #236677 - Flags: review?(mrbkap)
Attachment #236581 - Flags: review?(sayrer)
Attachment #236581 - Flags: review?(mrbkap)
Attachment #236677 - Flags: review?(sayrer)
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
Attached patch Fix, v3Splinter Review
Attachment #236677 - Attachment is obsolete: true
Attachment #236678 - Flags: review?(mrbkap)
Attachment #236677 - Flags: review?(sayrer)
Attachment #236677 - Flags: review?(mrbkap)
Attachment #236678 - Flags: review?(sayrer)
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
Blocks: 351104
Attachment #236678 - Flags: review?(mrbkap) → review+
Attachment #236678 - Flags: review?(sayrer) → review+
Fixed on trunk.

/be
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
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
Attachment #236678 - Flags: approval1.8.1?
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.


Checking in regress-350531.js;
/cvsroot/mozilla/js/tests/e4x/Regress/regress-350531.js,v  <--  regress-350531.js
initial revision: 1.1
Flags: in-testsuite+
reopen due to hang.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Does this mean we should delay this patch for 1.8 branch?

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

I was wrong. If you let the test continue it will eventually complete.
Status: REOPENED → RESOLVED
Closed: 13 years ago13 years ago
Resolution: --- → FIXED
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
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
Blocks: 351597
Note separate one-line followup patch in bug 351597.

/be
Blocks: 351625
Blocks: 351626
Comment on attachment 236678 [details] [diff] [review]
Fix, v3

a=beltzner on behalf of 181drivers
Attachment #236678 - Flags: approval1.8.1? → approval1.8.1+
Blocks: 350226
Fixed on the 1.8 branch.

/be
Keywords: fixed1.8.1
Blocks: 351705
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.
Summary: uneval function (){ return (@['a'])=='b'} → use precedence-based parenthesization (was: uneval function (){ return (@['a'])=='b'})
Attached file 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.
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
verified fixed 1.8 20060916 windows/linux
(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.
verified 1.9 20060921 windows/linux
Status: RESOLVED → VERIFIED
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

You need to log in before you can comment on or make changes to this bug.