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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@28833 268f45cc-cd09-0410-ab3c-d52691b4dbfc

diff --git a/JavaScriptCore/ChangeLog b/JavaScriptCore/ChangeLog
index 2d44db2a92be66da8dc77e7e128b3b5bd73aa6b6..e10b42220e3b0908f443f6a826612631a89fd365 100644 (file)
--- a/JavaScriptCore/ChangeLog
+++ b/JavaScriptCore/ChangeLog
@@ -1,3 +1,23 @@
+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>
 
         - speculative build fix for non-gcc platforms

diff --git a/JavaScriptCore/pcre/pcre.h b/JavaScriptCore/pcre/pcre.h
index 9d1671bc931f6f14163c82521fe04624631bca5c..1be4523d834a4916fd04e4f07f413fbe3ff6ea4a 100644 (file)
--- a/JavaScriptCore/pcre/pcre.h
+++ b/JavaScriptCore/pcre/pcre.h
@@ -51,7 +51,7 @@ enum JSRegExpMultilineOption { JSRegExpSingleLine, JSRegExpMultiline };
 
 /* jsRegExpExecute error codes */
 const int JSRegExpErrorNoMatch = -1;
-const int JSRegExpErrorRecursionLimit = -2;
+const int JSRegExpErrorHitLimit = -2;
 const int JSRegExpErrorNoMemory = -3;
 const int JSRegExpErrorInternal = -4;
 

diff --git a/JavaScriptCore/pcre/pcre_exec.cpp b/JavaScriptCore/pcre/pcre_exec.cpp
index bee77b9c841ecd991ff8f475efcdfb38fc4b9f7f..2abfe6f5816411e6454cc344df116eda06e670fa 100644 (file)
--- a/JavaScriptCore/pcre/pcre_exec.cpp
+++ b/JavaScriptCore/pcre/pcre_exec.cpp
@@ -121,25 +121,15 @@ struct MatchData {
   bool   ignoreCase;
 };
 
-/* 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. */
 
 #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. */
+/* The below limit restricts the number of "recursive" match calls in order to
+avoid spending exponential time on complex regular expressions. */
 
-#define MATCH_RECURSION_LIMIT 100000
+static const unsigned matchLimit = 100000;
 
 #ifdef DEBUG
 /*************************************************
@@ -251,8 +241,6 @@ a bit more code and notice if we use conflicting numbers.*/
 #endif
 
 #define RECURSIVE_MATCH_COMMON(num) \
-    if (stack.size >= MATCH_RECURSION_LIMIT) \
-        return matchError(JSRegExpErrorRecursionLimit, stack); \
     goto RECURSE;\
     RRETURN_##num: \
     stack.popCurrentFrame();
@@ -291,8 +279,8 @@ Arguments:
    offsetTop  current top pointer
    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)
 */
@@ -407,9 +395,10 @@ static inline void repeatInformationFromInstructionOffset(short instructionOffse
 
 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;
 
@@ -442,6 +431,8 @@ static int match(const UChar* subjectPtr, const unsigned char* instructionPtr, i
     /* This is where control jumps back to to effect "recursion" */
     
 RECURSE:
+    if (++matchCount > matchLimit)
+        return matchError(JSRegExpErrorHitLimit, stack);
 
     /* Now start processing the operations. */
     
@@ -563,7 +554,7 @@ RECURSE:
             }
                 
             /* 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. */
                 
@@ -1779,7 +1770,6 @@ RRETURN_SWITCH:
 #endif
     
 RETURN:
-    ASSERT(isMatch == MATCH_MATCH || isMatch == MATCH_NOMATCH);
     return isMatch;
 }
 
@@ -2012,13 +2002,13 @@ int jsRegExpExecute(const JSRegExp* re,
         
         /* 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;
         }

diff --git a/LayoutTests/ChangeLog b/LayoutTests/ChangeLog
index 7ab7b55cb92c088156a8b3cd74e05535e49b618f..1ca74028b3dbf720d0b86f2ee6b156ffee4d2bd3 100644 (file)
--- a/LayoutTests/ChangeLog
+++ b/LayoutTests/ChangeLog
@@ -1,3 +1,16 @@
+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>
 
         Reviewed by John Sullivan.

diff --git a/LayoutTests/fast/regex/resources/TEMPLATE.html b/LayoutTests/fast/regex/resources/TEMPLATE.html
new file mode 100644 (file)
index 0000000..82e186c
--- /dev/null
+++ b/LayoutTests/fast/regex/resources/TEMPLATE.html
@@ -0,0 +1,13 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="YOUR_JS_FILE_HERE"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>

diff --git a/LayoutTests/fast/regex/resources/slow.js b/LayoutTests/fast/regex/resources/slow.js
new file mode 100644 (file)
index 0000000..54b6b81
--- /dev/null
+++ b/LayoutTests/fast/regex/resources/slow.js
@@ -0,0 +1,7 @@
+description(
+'Test for expressions that would hang when evaluated due to exponential matching behavior. If the test does not hang it is a success.'
+);
+
+shouldBe('/(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/")', 'false');
+
+var successfullyParsed = true;

diff --git a/LayoutTests/fast/regex/slow-expected.txt b/LayoutTests/fast/regex/slow-expected.txt
new file mode 100644 (file)
index 0000000..105f24f
--- /dev/null
+++ b/LayoutTests/fast/regex/slow-expected.txt
@@ -0,0 +1,10 @@
+Test for expressions that would hang when evaluated due to exponential matching behavior. If the test does not hang it is a success.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS /(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/") is false
+PASS successfullyParsed is true
+
+TEST COMPLETE
+

diff --git a/LayoutTests/fast/regex/slow.html b/LayoutTests/fast/regex/slow.html
new file mode 100644 (file)
index 0000000..aabad2d
--- /dev/null
+++ b/LayoutTests/fast/regex/slow.html
@@ -0,0 +1,13 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/slow.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>