Changeset 28833 in webkit

Timestamp:

Dec 18, 2007 11:30:05 AM (16 years ago)

Author:

Darin Adler

Message:

JavaScriptCore:

Reviewed by Geoff.

• test for ​http://bugs.webkit.org/show_bug.cgi?id=16458 REGRESSION (r28164): regular expressions can now hang due to lack of a match limit <rdar://problem/5636067>

Test: fast/regex/slow.html

Slows down SunSpider a bit (about 1.01x); filed a bug to follow up on that:
​http://bugs.webkit.org/show_bug.cgi?id=16503

• pcre/pcre.h: Changed name of error code to not specifically mention "recursion".
• pcre/pcre_exec.cpp: (match): Replaced the depth limit, MATCH_RECURSION_LIMIT, with a total match looping limit, matchLimit. Also eliminated the constants for MATCH_MATCH and MATCH_NOMATCH, since they are just true and false (1 and 0). (jsRegExpExecute): More of the MATCH_MATCH change.

LayoutTests:

Reviewed by Geoff.

• test for ​http://bugs.webkit.org/show_bug.cgi?id=16458 REGRESSION (r28164): regular expressions can now hang due to lack of a match limit

• fast/regex/resources: Added.
• fast/regex/resources/TEMPLATE.html: Copied from fast/js/resources/TEMPLATE.html.
• fast/regex/resources/slow.js: Added.
• fast/regex/slow-expected.txt: Added.
• fast/regex/slow.html: Added.

Location:

trunk

Files:

• JavaScriptCore/ChangeLog (modified) (1 diff)
• JavaScriptCore/pcre/pcre.h (modified) (1 diff)
• JavaScriptCore/pcre/pcre_exec.cpp (modified) (9 diffs)
• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/fast/regex/resources (added)
• LayoutTests/fast/regex/resources/TEMPLATE.html (copied) (copied from trunk/LayoutTests/fast/js/resources/TEMPLATE.html)
• LayoutTests/fast/regex/resources/slow.js (added)
• LayoutTests/fast/regex/slow-expected.txt (added)
• LayoutTests/fast/regex/slow.html (added)

trunk/JavaScriptCore/ChangeLog

@@ +1 @@
+2007-12-18  Darin Adler  <darin@apple.com>
+
+        Reviewed by Geoff.
+
+        - test for http://bugs.webkit.org/show_bug.cgi?id=16458
+          REGRESSION (r28164): regular expressions can now hang due to lack of a match limit
+          <rdar://problem/5636067>
+
+        Test: fast/regex/slow.html
+
+        Slows down SunSpider a bit (about 1.01x); filed a bug to follow up on that:
+        http://bugs.webkit.org/show_bug.cgi?id=16503
+
+        * pcre/pcre.h: Changed name of error code to not specifically mention "recursion".
+        * pcre/pcre_exec.cpp:
+        (match): Replaced the depth limit, MATCH_RECURSION_LIMIT, with a total match looping
+        limit, matchLimit. Also eliminated the constants for MATCH_MATCH and MATCH_NOMATCH,
+        since they are just true and false (1 and 0).
+        (jsRegExpExecute): More of the MATCH_MATCH change.
+
 2007-12-17  Darin Adler  <darin@apple.com>
 

trunk/JavaScriptCore/pcre/pcre.h

@@ -52 +52 @@
 /* jsRegExpExecute error codes */
 const int JSRegExpErrorNoMatch = -1;
-const int JSRegExpErrorRecursionLimit = -2;
+const int JSRegExpErrorHitLimit = -2;
 const int JSRegExpErrorNoMemory = -3;
 const int JSRegExpErrorInternal = -4;

trunk/JavaScriptCore/pcre/pcre_exec.cpp

@@ -122 +122 @@
 };
 
-/* Non-error returns from the match() function. Error returns are externally
-defined error codes, which are all negative. */
-
-#define MATCH_MATCH        1
-#define MATCH_NOMATCH      0
-
 /* The maximum remaining length of subject we are prepared to search for a
 req_byte match. */
@@ -133 +127 @@
 #define REQ_BYTE_MAX 1000
 
-/* The below limit restricts the number of recursive match calls in order to
-limit the maximum amount of storage.
- 
-This limit is tied to the size of MatchFrame.  Right now we allow PCRE to allocate up
-to MATCH_RECURSION_LIMIT - 16 * sizeof(MatchFrame) bytes of "stack" space before we give up.
-Currently that's 100000 - 16 * (23 * 4)  ~ 90MB. */
-
-#define MATCH_RECURSION_LIMIT 100000
+/* The below limit restricts the number of "recursive" match calls in order to
+avoid spending exponential time on complex regular expressions. */
+
+static const unsigned matchLimit = 100000;
 
 #ifdef DEBUG
@@ -252 +242 @@
 
 #define RECURSIVE_MATCH_COMMON(num) \
-    if (stack.size >= MATCH_RECURSION_LIMIT) \
-        return matchError(JSRegExpErrorRecursionLimit, stack); \
     goto RECURSE;\
     RRETURN_##num: \
@@ -292 +280 @@
    md          pointer to "static" info for the match
 
-Returns:       MATCH_MATCH if matched            )  these values are >= 0
-               MATCH_NOMATCH if failed to match  )
+Returns:       1 if matched          )  these values are >= 0
+               0 if failed to match  )
                a negative error value if aborted by an error condition
                  (e.g. stopped by repeated call or recursion limit)
@@ -408 +396 @@
 static int match(const UChar* subjectPtr, const unsigned char* instructionPtr, int offsetTop, MatchData& md)
 {
-    int isMatch = false;
+    bool isMatch = false;
     int min;
     bool minimize = false; /* Initialization not really needed, but some compilers think so. */
+    unsigned matchCount = 0;
     
     MatchStack stack;
@@ -443 +432 @@
     
 RECURSE:
+    if (++matchCount > matchLimit)
+        return matchError(JSRegExpErrorHitLimit, stack);
 
     /* Now start processing the operations. */
@@ -564 +555 @@
                 
             /* End of a group, repeated or non-repeating. If we are at the end of
-             an assertion "group", stop matching and return MATCH_MATCH, but record the
+             an assertion "group", stop matching and return 1, but record the
              current high water mark for use by positive assertions. Do this also
              for the "once" (not-backup up) groups. */
@@ -1780 +1771 @@
     
 RETURN:
-    ASSERT(isMatch == MATCH_MATCH || isMatch == MATCH_NOMATCH);
     return isMatch;
 }
@@ -2013 +2003 @@
         /* When the result is no match, advance the pointer to the next character
          and continue. */
-        
-        if (returnCode == MATCH_NOMATCH) {
+        if (returnCode == false) {
             startMatch++;
             continue;
         }
-        
-        if (returnCode != MATCH_MATCH) {
+
+        if (returnCode != true) {
+            ASSERT(returnCode == JSRegExpErrorHitLimit || returnCode == JSRegExpErrorNoMemory);
             DPRINTF((">>>> error: returning %d\n", rc));
             return returnCode;

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2007-12-18  Darin Adler  <darin@apple.com>
+
+        Reviewed by Geoff.
+
+        - test for http://bugs.webkit.org/show_bug.cgi?id=16458
+          REGRESSION (r28164): regular expressions can now hang due to lack of a match limit
+
+        * fast/regex/resources: Added.
+        * fast/regex/resources/TEMPLATE.html: Copied from fast/js/resources/TEMPLATE.html.
+        * fast/regex/resources/slow.js: Added.
+        * fast/regex/slow-expected.txt: Added.
+        * fast/regex/slow.html: Added.
+
 2007-12-18  Dan Bernstein  <mitz@apple.com>