switch() misbehaves with duplicated labels

VERIFIED FIXED in mozilla0.9.1

Status

()

Core
JavaScript Engine
P3
normal
VERIFIED FIXED
17 years ago
17 years ago

People

(Reporter: Harri Porten, Assigned: brendan)

Tracking

({js1.5})

Trunk
mozilla0.9.1
x86
All
js1.5
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(5 attachments)

(Reporter)

Description

17 years ago
Consider the following piece of code:

  var result = "";
  switch (1) {
     case 1:
        result += 'a';
     case 1:
	result += 'b';
  }

My version of Mozilla gives 'b' as a result. The way I read section 12.11 of the
ECMAScript standard both cases should have been executed, resulting in 'ab'.

Harri.
Status: UNCONFIRMED → NEW
Ever confirmed: true

Comment 1

17 years ago
Created attachment 30356 [details]
ECMA Section 12.11,  "The switch Statement"

Comment 2

17 years ago
In this expanded version of Harri's test, I get the following results
in the standalone JS shell: 

ab
ab
b



var result;
test(1);

function test(x)
{
  result = "";
    switch(x)
    {
      case x:
        result += 'a';
      case x:
        result += 'b';
    }
  print(result);
}


result = "";
  switch ('1')
  {
    case '1':
      result += 'a';
    case '1':
      result += 'b';
  }
print(result);


result = "";
  switch (1)
  {
    case 1:
      result += 'a';
    case 1:
      result += 'b';
  }
print(result);




Notice the first result is Harri's test wrapped in a function, 
with the number 1 provided through the parameter x. 

The second result is Harri's test with '1' instead of 1.

The third result is the original test: using the numeric literal 1
OS: Linux → All

Comment 3

17 years ago
Brendan: I'm cc'ing you because I'd like your opinion on a possible fix. The bug 
arises because the parser has decided to use a tableswitch for the integer case, 
but should detect the duplicate case condition and back off. To do so would 
require:

- pre-building the jump table during the initial loop and detecting a collision.
(Wasting space, but not if the table is eventually used. The table needs to be
dynamically sized though.)
- building a bitmask during the initial loop and detecting a collision.
(Wasting space, less so but not re-usable. Again, a dynamic table.)
- re-iterating over the cases looking for a collision.
(Wasting time.)

any suggestions?
thanks

Comment 4

17 years ago
Testcase added to JS testsuite:

              js/tests/ecma_3/Statements/regress-74474.js

Currently passing in Rhino, but failing in SpiderMonkey and LiveConnect -
(Assignee)

Comment 5

17 years ago
Created attachment 33313 [details] [diff] [review]
proposed fix, please review
(Assignee)

Comment 6

17 years ago
rogerl, I went with your second idea, a bitmap.  It's stack allocated for
small-ish int cases.  Note that JSOP_TABLESWITCH handles 16-bit int constant
case labels, so if the stack-allocated bitmap isn't big enough, we switch to a
one-time-per-such-a-switch-allocated bitmap, got from cx->tempPool and returned
there in case later code generation can reuse the big arena that results.  So,
can you r= this?

Shaver, how about an sr=?

/be
(Assignee)

Comment 7

17 years ago
Testing would be good too!  I'm not overconfident, but I think I got all the
early return cases, and it cures the testcase in this bug.

Taking this bug, hope you don't mind!

/be
Assignee: rogerl → brendan
Keywords: js1.5, mozilla0.9.1
Priority: -- → P3
Target Milestone: --- → mozilla0.9.1
(Assignee)

Updated

17 years ago
Status: NEW → ASSIGNED

Comment 8

17 years ago
I couldn't apply the patch for some reason:

Hmm...  Looks like a unified diff to me...
The text leading up to this was:
--------------------------
|Index: jsemit.c
|==========================================================
|RCS file: /cvsroot/mozilla/js/src/jsemit.c,v
|retrieving revision 3.52
|diff -u -r3.52 jsemit.c
|--- jsemit.c   2001/03/22 02:52:34     3.52
|+++ jsemit.c   2001/05/06 00:39:14
--------------------------
Patching file jsemit.c using Plan A...
Hunk #1 failed at 1110.
Hunk #2 failed at 1146.
Hunk #3 failed at 1172.
Hunk #4 failed at 1203.
Hunk #5 failed at 1222.
5 out of 5 hunks failed--saving rejects to jsemit.c.rej
done

but I did it by hand and checked things out. Looks fine, r=rogerl

Comment 9

17 years ago
With patch id=33313 above, I'm getting two testcase failures

*-* Testcase js1_2/function/Function_object.js failed
*-* Testcase js1_2/function/tostring-1.js failed


Both testcases do things like (new Function()).toString()
and expect 

function () {
}

With the patch, we are getting this instead:

(function () {
})


Note this was the same problem as in bug 76634, 
"Has Function.prototype.toString() changed?"

Comment 10

17 years ago
Oops - I must have had a bad tree. I pulled js/src into a new directory,
applied the patch, and did not have the problem. Sorry for the false alarm.
(Assignee)

Comment 12

17 years ago
Fix is in, thanks to all.

/be
Status: ASSIGNED → RESOLVED
Last Resolved: 17 years ago
Resolution: --- → FIXED

Comment 13

17 years ago
Testcase passing on WinNT, Linux in debug/optimized JS shells.
Marking Verified - 
Status: RESOLVED → VERIFIED
(Assignee)

Comment 14

17 years ago
Created attachment 33620 [details] [diff] [review]
testcase that overflows the stack-allocated bitmap, exercising the patch's other bitmap allocation code path
(Assignee)

Comment 15

17 years ago
That testcase has no duplicate cases, so selects JSOP_TABLESWITCH for optimal
performance.  If you uncomment the first, commented-out case 3: label, then you
get the "ab" result because the code generator selects JSOP_LOOKUPSWITCH.  So
this attachment should be split into two testcases (which could be bodies of two
functions in one testcase file, of course).

/be

Comment 16

17 years ago
I'm all set to add this to the testsuite, but I keep getting this error
when I try to run it...

[/d/JS_TRUNK/mozilla/js/src/WINNT4.0_DBG.OBJ]./js
js> load('../../tests/ecma_3/shell.js')
js> load('../../tests/ecma_3/Statements/regress-74474-002.js')
17: InternalError: switch statement too large
(Assignee)

Comment 17

17 years ago
Phil, can you attach the exact big-switch testcase that fails for you with that
error?  It never happened for me, and should not unless there is some kind of
compiler- or platform-dependent bug.

/be

Comment 18

17 years ago
Created attachment 33739 [details]
Here is the exact testcase; depends on ecma_3\shell.js
(Assignee)

Comment 19

17 years ago
Yes, two such 9000-case switches will overflow the JS engine's jump offset
immediate operand format.  Wrap them both in functions and you'll be fine.  If
you want to bug me to add a long-format jump instruction, file away.

/be

Comment 20

17 years ago
I also got the error by running just one 9000-case switch (unwrapped).

I cannot seem to remove the error by wrapping. Even one 9000-case
switch, wrapped in a function, produces that same error on my WinNT box.
I don't even have to invoke the function to get the error -

Hope I'm not blundering in some way. Here is a sample:


function doSectionA()
{
  status = 'Section A of test: no duplicate labels';
  actual = '';
  x = 3;

  switch (x) 
  {
    case 0:
    case 1:
    case 2:
    //case 3:
      actual += 'a';
    case 3:
    case 4:
    case 5:

     etc. 
     etc.

    case 8996:
    case 8997:
    case 8998:
    case 8999:
      actual += 'b';
  }

  expect = 'b';
  addThis();
}


I don't even have to invoke doSectionA() to get the error.
(Assignee)

Comment 21

17 years ago
Phil, I chopped out the second switch and cannot get the error.  Can you attach
your single-switch-gets-error testcase?

/be

Comment 22

17 years ago
Created attachment 33894 [details]
The testcase with Section A commented out. Produces error.

Comment 23

17 years ago
It's really weird - if I comment out Section B of the test instead of 
Section A, I do NOT get the "switch statement too large" error -

Comment 24

17 years ago
Using the testcase at attachment id=33894 above: if I go to Section B 
of the test and change the duplicate label 3 to a distinct number 
from all the other cases (e.g. 9000), I don't get the "switch statement too 
large" error. If I change this label back to 3 or any other number between
0-8999, I have a duplicate label again, and I get the error again.

(Assignee)

Comment 25

17 years ago
Phil, that's expected: the duplicate label deoptimizes the bytecode that JS
selects from JSOP_TABLESWITCH, which is more time *and* space efficient, into
JSOP_LOOKUPSWITCH.

For a 9000-case switch, JSOP_TABLESWITCH needs 1+2+2+2+(2*9000) or 18007 bytes
(opcode, default offset, low case, high case, jump offsets for 9000 cases; a
jump offset is two bytes, signed).  JSOP_LOOKUPSWITCH, OTOH, requires
1+2+2+(4*9000) or 36005 bytes (opcode, default offset, number of cases, and 9000
(atom index, jump offset) pairs for the cases; an atom index is also two bytes,
but unsigned).

I think you should file a "please add an extended jump bytecode to JS and use it
to avoid "script too large", "switch too large", etc. errors.  In the mean time,
work around this with function wrapping.

/be

Comment 26

17 years ago
I have filed bug 80981 for the extended jump bytecode issue.

Note: my comment at 2001-05-09 16:45 above still applies. The relevant part 
of the test here is the 9001-case switch with the duplicated label. Even if 
I wrap that in a function, I get the "switch statement too large" error. 

I get the error without even invoking the function in the test. Just the 
fact that it exists in the testfile seems to provoke the error. I can't 
actually call the function and run the test because of this - 
(Assignee)

Comment 27

17 years ago
Do the math: the second switch is too large, in the sense that it is 36005 bytes
long, and any jump that has to cover it (as the jump to default case, i.e., jump
to next bytecode after the switch) has an offset that does not fit in signed 16
bits (32767 is the largest positive jump offset).

Thanks for filing the other bug.  Can you cope in the mean time with a reduced
testcase?  The stack bitmap overflows into a malloc'd one at 8193 cases (no
duplicates).  The switch with a duplicate at case 3 doesn't even use more than 4
bits in the bitmap before deoptimizing to JSOP_LOOKUPSWITCH, so I dont' see the
point in testing a large switch that contains an early duplicate.

/be

Comment 28

17 years ago
The original testcase above has been renamed, and two more testcases 
have been added:

           js/tests/ecma_3/Statements/regress-74474-001.js
           js/tests/ecma_3/Statements/regress-74474-002.js
           js/tests/ecma_3/Statements/regress-74474-003.js
You need to log in before you can comment on or make changes to this bug.