223535 - Regular expression with empty last alternative crashs, e.g. /x|/ [@ processOp]

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[zack-weg]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.5) Gecko/20031007
Build Identifier: js shell 20031024

A regular expression ending with '|' crashs at compile time.
Regression of the regexp rewrite landing (bug 85721).


Reproducible: Always

Steps to Reproduce:
1. Enter js shell
2. Type /|/

Actual Results:  
Crash.


Expected Results:  
Print /|/ .

Comment 1

[timeless]

        if ((((RENode *)(result->kid))->op == REOP_FLAT)
                && (((RENode *)(result->u.kid2))->op == REOP_FLAT)
                && ((state->flags & JSREG_FOLD) == 0) ) {

-	(RENode*)(result->kid) 	0x00080101
	op	CXX0030: Error: expression cannot be evaluated
	next	CXX0030: Error: expression cannot be evaluated
	kid	CXX0030: Error: expression cannot be evaluated
+	u	{...}

processOp(CompilerState * 0x0012ebec, REOpData * 0x00411648, RENode * *
0x00411c50, int 1) line 346 + 6 bytes
parseRegExp(CompilerState * 0x0012ebec) line 549 + 29 bytes
js_NewRegExp(JSContext * 0x002f6ca8, JSTokenStream * 0x00411228, JSString *
0x002f87b8, unsigned int 0, int 0) line 1581 + 9 bytes
js_NewRegExpObject(JSContext * 0x002f6ca8, JSTokenStream * 0x00411228, unsigned
short * 0x00411520, unsigned int 1, unsigned int 0) line 3722 + 23 bytes
js_GetToken(JSContext * 0x002f6ca8, JSTokenStream * 0x00411228) line 1180 + 51 bytes
js_PeekToken(JSContext * 0x002f6ca8, JSTokenStream * 0x00411228) line 642 + 13 bytes
Statements(JSContext * 0x002f6ca8, JSTokenStream * 0x00411228, JSTreeContext *
0x0012edd0) line 979 + 13 bytes
js_ParseTokenStream(JSContext * 0x002f6ca8, JSObject * 0x002f8348, JSTokenStream
* 0x00411228) line 414 + 17 bytes
JS_BufferIsCompilableUnit(JSContext * 0x002f6ca8, JSObject * 0x002f8348, const
char * 0x0012eea8, unsigned int 4) line 3104 + 17 bytes
Process(JSContext * 0x002f6ca8, JSObject * 0x002f8348, char * 0x00000000) line
384 + 31 bytes

Comment 2

[timeless]

Attachment: guess (not tested against regression suite)

the problem is here:
processOp(CompilerState *state, REOpData *opData, RENode **operandStack, intN
operandSP)
	result->kid = operandStack[operandSP - 2];
	result->u.kid2 = operandStack[operandSP - 1];
	operandSP	1
So it's an ABR

Comment 3

[Brendan Eich [:brendan]]

Not my rewrite, but I checked it in (silly me).

The code tries to make an empty node for some cases, but seems to miss others. 
I don't think the patch is going to recover from all such missed cases, although
it might.  But it's still patching the symptom, not the cause.

/be

Comment 4

[timeless]

# Retest List, smdebug, generated Fri Oct 24 10:23:17 2003.
# Original test base was: All tests.
# 1355 of 1355 test(s) were completed, 153 failures reported.
js1_5/Array/regress-101964.js
js1_5/Regress/regress-192465.js
js1_5/Regress/regress-96128-n.js

all other failures are liveconnect (i should have told jsDriver to skip that but
i am not awake enough to do that). i cvs updated tests before running so i
should be current. None of these seem to relate to this regexps so i'm not
concerned.

For my reference, spidermonkey (current and a snapshot of mine from 08/31/2003)
and msjscript
evaluate:
t="o]";[t.match(/\]|0/),t.match(/\]|/),t.match(/]|0/),t.match(/]|/),t.match(/o|/),"_end_"]

to:
],,],,o,_end_

I exected something else.

Next: fun with ||'s
(first on boffo)
js> /||/
typein:2: SyntaxError: syntax error:
typein:2: /||/

typein:2: .^
js> /|||/
./run-mozilla.sh: line 72:  3272 Segmentation fault      "$prog" ${1+"$@"}
mozhack@boffo:~/obj-i686-pc-linux-gnu-qt/dist/bin$

boffo is a tinderbox, so the code is whatever is current.

raistlin(patched):
I:\build\mozilla\js\src\WINNT5.0_DBG.OBJ>js
js> /1|2|/
/1|2|/
js> /(1|2|)|/
/(1|2|)|/
js> /(1|2|)|(1|)/
/(1|2|)|(1|)/
js> /(1|2|)|(1||)/
/(1|2|)|(1||)/
js> /(1|2|)|(1||)|/
/(1|2|)|(1||)|/
js> /(1|2|)|(1|.?|)|/
/(1|2|)|(1|.?|)|/
js> /(1|2|)|(1|.?|)|?/
7: SyntaxError: invalid quantifier ?:
7: /(1|2|)|(1|.?|)|?/
7: ^
js> /(1|2|)|(1|.?|)?|/
/(1|2|)|(1|.?|)?|/
js> /(1|2|)|(1|.?|)?|[]/
/(1|2|)|(1|.?|)?|[]/
js> /(1|2|)|(1|.?|)?|[]|/
/(1|2|)|(1|.?|)?|[]|/
js> /(1|2|)|(1|.?|)?|[]|(|[])/
/(1|2|)|(1|.?|)?|[]|(|[])/
js> /(1|2|)|(1|.?|)?|[]|(|[])|/
/(1|2|)|(1|.?|)?|[]|(|[])|/
js> /(1|2|)|(1|.?|)?|[]|(|[])|(?:|)}/
/(1|2|)|(1|.?|)?|[]|(|[])|(?:|)}/
js> /(1|2|)|(1|.?|)?|[]|(|[])|(?:|)||/
/(1|2|)|(1|.?|)?|[]|(|[])|(?:|)||/
js> /||/
/||/
js> /|||/
/|||/
js>

-- many |s:
(first on raistlin - patched)
js> a=[];a[1000000]=null;RegExp(a.join('|')).test("1")
Assertion failure: ((diff) >= -32768) && ((diff) <= 32767), at jsregexp.c:1380
emitREBytecode(CompilerState * 0x0012e4b8, JSRegExp * 0x22150020, int 1000000,
unsigned char * 0x22709ffb, RENode * 0x1fad49a0) line 1380 + 40 bytes
        case REOP_ENDALT:
            diff = pc - emitStateSP->nextTermFixup;
            CHECK_OFFSET(diff);

I:\build\mozilla\js\src\WINNT5.0_OPT.OBJ.08_31_2003>js
js> a=[];a[1000000]=null;RegExp(a.join('|')).test("1")
true

IE reports an OOM error instead of crashing.
-- empties:
(first on raistlin - patched)
js> RegExp("")
//
js> RegExp(undefined)
/undefined/
js> RegExp(null)
RegExp(JSContext * 0x002f7398, JSObject * 0x002f8b48, unsigned int 1, long *
0x00414b74, long * 0x0012e64c) line 3676 + 46 bytes
        ok = native(cx, frame.thisp, argc, frame.argv, &frame.rval);

I:\build\mozilla\js\src\WINNT5.0_OPT.OBJ.08_31_2003>js
js> RegExp("")
//
js> RegExp(undefined)
/undefined/
js> RegExp(null)
(crash, no stack posted or investigated since it doesn't matter and i don't have
the source)

IE gives:
RegExp("")
//
RegExp(undefined)
//
RegExp(null)
/null/

Brendan: a few thoughts about my patch:
1. returning was wrong here:
if (!dummy)
    return JS_FALSE;
should be goto out;
2. I don't think we can do it much better, i tried looking at a few other approaches
A. moving the if outside the while loop, but then i had to use the extra if in
pushOperand to mayberealloc the operandstack.
B. trying to recycle pushOperand - I couldn't find a way to use it that wouldn't
require a lot of messy hacking
C. splitting (which i didn't actually play with or reject)
            while (operatorSP) {MAYBEADDDUMMY; OLDCODE;} ENDCODE;
into
            while (operatorSP > 1) {OLDCODE;}
            if (operatorSP) {ADDDUMMY; OLDCODE;}
            ENDCODE
or:
            if (!operatorSP) {ENDCODE;}
            while (operatorSP > 1) {OLDCODE;}
            ADDDUMMY; OLDCODE; ENDCODE;

Anyway, i really think there's only one case that it misses which is
regexpstring =~ m%|$%
i'm going to think about it a bit more, it might be the case that the place
where it tries to handle it is just wrong :) in which case my code copying
should be a move. Actually, that's what I was doing, i was trying to figure out
how to tickle the current code to actually make that dummy node. i was having a
really hard time doing that :).

Comment 5

[Phil Schwartau]

Testcase added to JS testsuite:

      mozilla/js/tests/ecma_3/RegExp/regress-223535.js

Currently passing in the Rhino shell, crashing in SpiderMonkey (debug and opt).

Comment 6

[Brendan Eich [:brendan]]

Attachment: proposed fix

I think this covers the missing case.

Timeless, no need to goto out before the stacks have been malloc'd (malloc
happy code here, as an aside, but the early return for empty regexp is ok -- it
just needs to propagate false if NewRENode failed).

/be

Comment 7

[timeless]

Comment on attachment 134054 [details] [diff] [review]
proposed fix

i like it :)

# Retest List, smdebug, generated Fri Oct 24 15:55:38 2003.
# Original test base was: All tests.
# 1111 of 1111 test(s) were completed, 5 failures reported.
js1_5/Array/regress-101964.js
js1_5/Regress/regress-152646.js
js1_5/Regress/regress-192414.js
js1_5/Regress/regress-192465.js
js1_5/Regress/regress-96128-n.js

I'm not sure why the first run i made had 3 failures instead of 5, but i did a
run before this run and had 5 again.

Comment 8

[Mike Shaver (:shaver emeritus)]

Comment on attachment 134054 [details] [diff] [review]
proposed fix

Sure.  (Is it regexp week or something?)

Comment 9

[Asa Dotzler [:asa]]

Comment on attachment 134054 [details] [diff] [review]
proposed fix

a=asa (on behalf of drivers) for checkin to 1.6alpha

Comment 10

[Brendan Eich [:brendan]]

Fixed.

/be

Comment 11

[Phil Schwartau]

Verified FIXED.

The above test now passes in the debug and optimized SpiderMonkey shell.
In fact all tests pass, in directory mozilla/js/tests/ecma_3/RegExp/  -