635417 - Regular expression bug (breaks splinter patch review)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[otaylor]

Tested with Feb 18 nightly build firefox-4.0b12pre.en-US.linux-x86_64 - the bug is at least a few week old, but don't know exactly when it started.

The regular expression:

 /^@(A*)x(B)*/

does not match the string:

 "@xB"

I'll attach an obvious HTML/JS test case. The above is pretty much minimal - if you remove either of the parentheses the problem goes away. If you change the @ to a letter like C the problem goes away (?!?!) - though $ also reproduces the problem.

Comment 1

[Mike Shaver (:shaver emeritus)]

cdleary LOVES HIM SOME REGEXP. boy howdy.

Comment 2

[otaylor]

Attachment: Test case

Comment 3

[David Mandelin [:dmandelin]]

I got this regression window while waiting for a build:

http://hg.mozilla.org/mozilla-central/pushloghtml?startdate=2011-01-31&enddate=2011-02-01

It's probably bug 627609.

Comment 4

[David Mandelin [:dmandelin]]

The cause here is pretty simple: in our modified PCRE, we (try to) look at the op just before a bracket to see if it is OP_BRAZERO ("make the next bracket optional") and then "do stuff" based on that. It turns out that OP_BRAZERO == 64 == '@'--in this case, the position just before the first bracket is the character of the single-char match, not an actual opcode. We need to use a more robust way of tracking which brackets are supposed to be optional. I think we can put it in the BracketChainNode or something like that.

Taking, but cdleary should feel free to steal.

Comment 5

[Brendan Eich [:brendan]]

PCRE die die die!

:-|.

/be

Comment 6

[David Mandelin [:dmandelin]]

Attachment: WIP

This doesn't work yet. It correctly passes the minSatisfied value from OP_BRAZERO to the bracket op. But it doesn't get to the KET that matches that bracket. ISTR that this seemed tricky and motivated the original incorrect solution.

Comment 7

[David Mandelin [:dmandelin]]

This is proving fairly hard. I'm in the process of completely rewriting the empty-groups-handling logic. (That should sound somewhat scary but not too--probably less than 100 LOC.) ETA (median estimate) for patch ready for review is Thursday afternoon.

Comment 8

[David Mandelin [:dmandelin]]

Attachment: Patch

Comment 9

[David Mandelin [:dmandelin]]

I'm seeing some failures on xpcshell and mochitest-(browser-)chrome, so probably not quite done yet.

Comment 10

[David Mandelin [:dmandelin]]

Attachment: Smaller patch

This patch fixes the problem in this bug without fully overhauling the min-sat propagation logic. This is probably a better bet than the previous patch: the previous patch may fix some bugs we don't know about yet, but they are probably pretty subtle, and that patch has higher risk.

Comment 11

[David Mandelin [:dmandelin]]

http://hg.mozilla.org/tracemonkey/rev/a5e1f6c87d91

Comment 12

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/a5e1f6c87d91