Bug 67455 – Different regular expression result

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Dave Mandelin]

This is https://bugzilla.mozilla.org/show_bug.cgi?id=683838

In JSC:

var rg = /(X(?:.(?!X))*?Y)|(Y(?:.(?!Y))*?Z)/g;
var str = "Y aaa X Match1 Y aaa Y Match2 Z";
print(str.match(rg));

==> Y Match2 Z

should be 

==> X Match1 Y,Y Match2 Z

[Julien Chaffraix]

Confirmed on ToT for JSC. V8 is not impacted nor is Opera or IE.

[Gavin Barraclough]

Reduction:

print(/a|b(?:[^b])*?c/.exec("badbc"));

should print a, prints bc.

[Gavin Barraclough]

Looks like the problem is in YARR interpreter, in backtrackParentheses with QuantifierNonGreedy, and where the expression is passed input to match against that will match the parentheses more than once but then fail.

For the above reduction I believe the interpreter will have torn off a couple of disjunction contexts (recording the matches of 'a' and 'd'), but only one of these contexts gets backtracked back into.  Since the minimum size of these matches is one, failing to backtrack means the input position has not been reverted correctly.  When the match has failed starting at input position 0, we try again at input +1, but instead of starting at position 1 the second pass starts at position 2, hence the first alternative doesn't get a chance to match.

[Gavin Barraclough]

The bug was introduced by r72140.  It added a return to the backtracking loop for backtrackParentheses/QuantifierNonGreedy, so it always returns after one iteration.  We've already returned if the match succeeded, the additional return should only be triggered if an error is detected.

[Gavin Barraclough]

Created attachment 109427 [details]
Patch, needs change log & layout test

[Gavin Barraclough]

Created attachment 109429 [details]
Fix

[WebKit Review Bot]

Attachment 109429 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1

LayoutTests/ChangeLog:1:  ChangeLog entry has no bug number  [changelog/bugnumber] [5]
Source/JavaScriptCore/ChangeLog:1:  ChangeLog entry has no bug number  [changelog/bugnumber] [5]
Total errors found: 2 in 5 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Gavin Barraclough]

Fixed in r96479