74474 - switch() misbehaves with duplicated labels

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P3)

Description

[Harri Porten]

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.

Comment 1

[Phil Schwartau]

Attachment: ECMA Section 12.11, "The switch Statement"

Comment 2

[Phil Schwartau]

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

Comment 3

[rogerl (gone)]

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

[Phil Schwartau]

Testcase added to JS testsuite:

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

Currently passing in Rhino, but failing in SpiderMonkey and LiveConnect -

Comment 5

[Brendan Eich [:brendan]]

Attachment: proposed fix, please review

Comment 6

[Brendan Eich [:brendan]]

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

Comment 7

[Brendan Eich [:brendan]]

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

Comment 8

[rogerl (gone)]

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

[Phil Schwartau]

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

[Phil Schwartau]

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.

Comment 11

[Mike Shaver (:shaver emeritus)]

sr=shaver

Comment 12

[Brendan Eich [:brendan]]

Fix is in, thanks to all.

/be

Comment 13

[Phil Schwartau]

Testcase passing on WinNT, Linux in debug/optimized JS shells.
Marking Verified - 

Comment 14

[Brendan Eich [:brendan]]

Attachment: testcase that overflows the stack-allocated bitmap, exercising the patch's other bitmap allocation code path

Comment 15

[Brendan Eich [:brendan]]

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

[Phil Schwartau]

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

Comment 17

[Brendan Eich [:brendan]]

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

[Phil Schwartau]

Attachment: Here is the exact testcase; depends on ecma_3\shell.js

Comment 19

[Brendan Eich [:brendan]]

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

[Phil Schwartau]

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.

Comment 21

[Brendan Eich [:brendan]]

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

/be

Comment 22

[Phil Schwartau]

Attachment: The testcase with Section A commented out. Produces error.

Comment 23

[Phil Schwartau]

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

[Phil Schwartau]

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.

Comment 25

[Brendan Eich [:brendan]]

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

[Phil Schwartau]

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 - 

Comment 27

[Brendan Eich [:brendan]]

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

[Phil Schwartau]

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