Changeset 233451 in webkit

Timestamp:

Jul 2, 2018 5:49:48 PM (6 years ago)

Author:

Sukolsak Sakshuwong

Message:

RegExp.exec returns wrong value with a long integer quantifier
​https://bugs.webkit.org/show_bug.cgi?id=187042

Reviewed by Saam Barati.

JSTests:

• stress/regexp-large-quantifier.js: Added.

(testRegExp):

• stress/regress-159744.js:

Source/JavaScriptCore:

Prior to this patch, the Yarr parser checked for integer overflow when
parsing quantifiers in regular expressions by adding one digit at a time
to a number and checking if the result got larger. This is wrong;
The parser would fail to detect overflow when parsing, for example,
10,000,000,003 because (1000000000*10 + 3) % (2^{32) = 1410065411 > 1000000000.}

Another issue was that once it detected overflow, it stopped consuming
the remaining digits. Since it didn't find the closing bracket, it
parsed the quantifier as a normal string instead.

This patch fixes these issues by reading all the digits and checking for
overflow with Checked<unsigned, RecordOverflow>. If it overflows, it
returns the largest possible value (quantifyInfinite in this case). This
matches Chrome [1], Firefox [2], and Edge [3].

[1] ​https://chromium.googlesource.com/v8/v8.git/+/23222f0a88599dcf302ccf395883944620b70fd5/src/regexp/regexp-parser.cc#1042
[2] ​https://dxr.mozilla.org/mozilla-central/rev/aea3f3457f1531706923b8d4c595a1f271de83da/js/src/irregexp/RegExpParser.cpp#1310
[3] ​https://github.com/Microsoft/ChakraCore/blob/fc08987381da141bb686b5d0c71d75da96f9eb8a/lib/Parser/RegexParser.cpp#L1149

• yarr/YarrParser.h:

(JSC::Yarr::Parser::consumeNumber):

LayoutTests:

• fast/regex/overflow-expected.txt:
• fast/regex/script-tests/overflow.js:

Location:

trunk

Files:

• JSTests/ChangeLog (modified) (1 diff)
• JSTests/stress/regexp-large-quantifier.js (added)
• JSTests/stress/regress-159744.js (modified) (1 diff)
• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/fast/regex/overflow-expected.txt (modified) (1 diff)
• LayoutTests/fast/regex/script-tests/overflow.js (modified) (1 diff)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/yarr/YarrParser.h (modified) (1 diff)

trunk/JSTests/ChangeLog

@@ +1 @@
+2018-07-02  Sukolsak Sakshuwong  <sukolsak@gmail.com>
+
+        RegExp.exec returns wrong value with a long integer quantifier
+        https://bugs.webkit.org/show_bug.cgi?id=187042
+
+        Reviewed by Saam Barati.
+
+        * stress/regexp-large-quantifier.js: Added.
+        (testRegExp):
+        * stress/regress-159744.js:
+
 2018-07-02  Ryosuke Niwa  <rniwa@webkit.org>
 

trunk/JSTests/stress/regress-159744.js

@@ -8 +8 @@
 }
 
-testRegExp("((?=$))??(?:\\1){34359738368,}", "gm", "abc\nabc\nabc\nabc\n", null);
 testRegExp("(\\w+)(?:\\s(\\1)){1100000000,}", "i", "word Word WORD WoRd", null);
 testRegExp("\\d{4,}.{1073741825}", "", "1234567\u1234", null);

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2018-07-02  Sukolsak Sakshuwong  <sukolsak@gmail.com>
+
+        RegExp.exec returns wrong value with a long integer quantifier
+        https://bugs.webkit.org/show_bug.cgi?id=187042
+
+        Reviewed by Saam Barati.
+
+        * fast/regex/overflow-expected.txt:
+        * fast/regex/script-tests/overflow.js:
+
 2018-07-02  Myles C. Maxfield  <mmaxfield@apple.com>
 

trunk/LayoutTests/fast/regex/overflow-expected.txt

@@ -8 +8 @@
 PASS regexp3.exec(s3) is null
 PASS function f() { /[^a$]{4294967295}/ } threw exception SyntaxError: Invalid regular expression: number too large in {} quantifier.
+PASS new RegExp('((?=$))??(?:\\1){34359738368,}') threw exception SyntaxError: Invalid regular expression: number too large in {} quantifier.
 PASS successfullyParsed is true
 

trunk/LayoutTests/fast/regex/script-tests/overflow.js

@@ -12 +12 @@
 
 shouldThrow("function f() { /[^a$]{4294967295}/ }", '"SyntaxError: Invalid regular expression: number too large in {} quantifier"');
+
+shouldThrow("new RegExp('((?=$))??(?:\\\\1){34359738368,}')", '"SyntaxError: Invalid regular expression: number too large in {} quantifier"');

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2018-07-02  Sukolsak Sakshuwong  <sukolsak@gmail.com>
+
+        RegExp.exec returns wrong value with a long integer quantifier
+        https://bugs.webkit.org/show_bug.cgi?id=187042
+
+        Reviewed by Saam Barati.
+
+        Prior to this patch, the Yarr parser checked for integer overflow when
+        parsing quantifiers in regular expressions by adding one digit at a time
+        to a number and checking if the result got larger. This is wrong;
+        The parser would fail to detect overflow when parsing, for example,
+        10,000,000,003 because (1000000000*10 + 3) % (2^32) = 1410065411 > 1000000000.
+
+        Another issue was that once it detected overflow, it stopped consuming
+        the remaining digits. Since it didn't find the closing bracket, it
+        parsed the quantifier as a normal string instead.
+
+        This patch fixes these issues by reading all the digits and checking for
+        overflow with Checked<unsigned, RecordOverflow>. If it overflows, it
+        returns the largest possible value (quantifyInfinite in this case). This
+        matches Chrome [1], Firefox [2], and Edge [3].
+
+        [1] https://chromium.googlesource.com/v8/v8.git/+/23222f0a88599dcf302ccf395883944620b70fd5/src/regexp/regexp-parser.cc#1042
+        [2] https://dxr.mozilla.org/mozilla-central/rev/aea3f3457f1531706923b8d4c595a1f271de83da/js/src/irregexp/RegExpParser.cpp#1310
+        [3] https://github.com/Microsoft/ChakraCore/blob/fc08987381da141bb686b5d0c71d75da96f9eb8a/lib/Parser/RegexParser.cpp#L1149
+
+        * yarr/YarrParser.h:
+        (JSC::Yarr::Parser::consumeNumber):
+
 2018-07-02  Keith Miller  <keith_miller@apple.com>
 

trunk/Source/JavaScriptCore/yarr/YarrParser.h

@@ -975 +975 @@
     unsigned consumeNumber()
     {
-        unsigned n = consumeDigit();
-        // check for overflow.
-        for (unsigned newValue; peekIsDigit() && ((newValue = n * 10 + peekDigit()) >= n); ) {
-            n = newValue;
-            consume();
-        }
-        return n;
+        Checked<unsigned, RecordOverflow> n = consumeDigit();
+        while (peekIsDigit())
+            n = n * 10 + consumeDigit();
+        return n.hasOverflowed() ? quantifyInfinite : n.unsafeGet();
     }