Changeset 200946 in webkit

Timestamp:

May 16, 2016 10:40:15 AM (8 years ago)

Author:

msaboff@apple.com

Message:

RegExp /y flag incorrect handling of mixed-length alternation
​https://bugs.webkit.org/show_bug.cgi?id=157723

Reviewed by Filip Pizlo.

Source/JavaScriptCore:

Previously for sticky patterns, we were bailing out and exiting when backtracking
alternatives with dissimilar match lengths. Deleted that code. Instead, for
sticky patterns we need to process the backtracking except for advancing to the
next input index.

• yarr/YarrJIT.cpp:

(JSC::Yarr::YarrGenerator::backtrack):

LayoutTests:

Added tests for alternatives with shorter to longer lengths.

• js/regexp-sticky-expected.txt:
• js/script-tests/regexp-sticky.js:

Location:

trunk

Files:

• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/js/regexp-sticky-expected.txt (modified) (1 diff)
• LayoutTests/js/script-tests/regexp-sticky.js (modified) (1 diff)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/yarr/YarrJIT.cpp (modified) (2 diffs)

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2016-05-16  Michael Saboff  <msaboff@apple.com>
+
+        RegExp /y flag incorrect handling of mixed-length alternation
+        https://bugs.webkit.org/show_bug.cgi?id=157723
+
+        Reviewed by Filip Pizlo.
+
+        Added tests for alternatives with shorter to longer lengths.
+
+        * js/regexp-sticky-expected.txt:
+        * js/script-tests/regexp-sticky.js:
+
 2016-05-16  Brent Fulgham  <bfulgham@apple.com>
 

trunk/LayoutTests/js/regexp-sticky-expected.txt

@@ -7 +7 @@
 PASS Test lastIndex resets
 PASS Ignore Case
-PASS Alternates
+PASS Alternates, differing lengths long to short
+PASS Alternates, differing lengths long to short with mutliple matches 
+PASS Alternates, differing lengths, short to long
 PASS BOL Anchored, starting at 0
 PASS BOL Anchored, starting at 1

trunk/LayoutTests/js/script-tests/regexp-sticky.js

@@ -73 +73 @@
 testStickyExec("Test lastIndex resets", /\d/y, "12345", 0, ["1", "2", "3", "4", "5", null, "1", "2", "3", "4", "5", null]);
 testStickyExec("Ignore Case", new RegExp("test", "iy"), "TESTtestTest", 0, ["TEST", "test", "Test", null]);
-testStickyExec("Alternates", new RegExp("Dog |Cat |Mouse ", "y"), "Mouse Dog Cat ", 0, ["Mouse ", "Dog ", "Cat ", null]);
+testStickyExec("Alternates, differing lengths long to short", new RegExp("bb|a", "y"), "a", 0, ["a", null]);
+testStickyExec("Alternates, differing lengths long to short with mutliple matches ", new RegExp("abc|ab|a", "y"), "aababcaabcab", 0, ["a", "ab", "abc", "a", "abc", "ab", null]);
+testStickyExec("Alternates, differing lengths, short to long", new RegExp("Dog |Cat |Mouse ", "y"), "Mouse Dog Cat ", 0, ["Mouse ", "Dog ", "Cat ", null]);
 testStickyExec("BOL Anchored, starting at 0", /^X/y, "XXX", 0, ["X", null]);
 testStickyExec("BOL Anchored, starting at 1", /^X/y, "XXX", 1, [null, "X", null]);

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2016-05-15  Michael Saboff  <msaboff@apple.com>
+
+        RegExp /y flag incorrect handling of mixed-length alternation
+        https://bugs.webkit.org/show_bug.cgi?id=157723
+
+        Reviewed by Filip Pizlo.
+
+        Previously for sticky patterns, we were bailing out and exiting when backtracking
+        alternatives with dissimilar match lengths.  Deleted that code.  Instead, for
+        sticky patterns we need to process the backtracking except for advancing to the
+        next input index.
+
+        * yarr/YarrJIT.cpp:
+        (JSC::Yarr::YarrGenerator::backtrack):
+
 2016-05-15  Filip Pizlo  <fpizlo@apple.com>
 

trunk/Source/JavaScriptCore/yarr/YarrJIT.cpp

@@ -1889 +1889 @@
                 }
 
-                if (m_pattern.sticky()) {
-                    // We have failed matching from the initial index and we're a sticky expression.
-                    // We are done matching. Link failures for any reason to here.
-                    YarrOp* tempOp = beginOp;
-                    do {
-                        tempOp->m_jumps.link(this);
-                        tempOp = &m_ops[tempOp->m_nextOp];
-                    } while (tempOp->m_op != OpBodyAlternativeEnd);
-
-                    removeCallFrame();
-                    generateFailReturn();
-                    break;
-                }
-
                 // We can reach this point in the code in two ways:
                 //  - Fallthrough from the code above (a repeating alternative backtracked out of its
@@ -1966 +1952 @@
                 }
 
-                // Check whether there is sufficient input to loop. Increment the input position by
-                // one, and check. Also add in the minimum disjunction size before checking - there
-                // is no point in looping if we're just going to fail all the input checks around
-                // the next iteration.
-                ASSERT(alternative->m_minimumSize >= m_pattern.m_body->m_minimumSize);
-                if (alternative->m_minimumSize == m_pattern.m_body->m_minimumSize) {
-                    // If the last alternative had the same minimum size as the disjunction,
-                    // just simply increment input pos by 1, no adjustment based on minimum size.
-                    add32(TrustedImm32(1), index);
-                } else {
-                    // If the minumum for the last alternative was one greater than than that
-                    // for the disjunction, we're already progressed by 1, nothing to do!
-                    unsigned delta = (alternative->m_minimumSize - m_pattern.m_body->m_minimumSize) - 1;
-                    if (delta)
-                        sub32(Imm32(delta), index);
-                }
-                Jump matchFailed = jumpIfNoAvailableInput();
-
-                if (needsToUpdateMatchStart) {
-                    if (!m_pattern.m_body->m_minimumSize)
-                        setMatchStart(index);
+                if (!m_pattern.sticky()) {
+                    // Check whether there is sufficient input to loop. Increment the input position by
+                    // one, and check. Also add in the minimum disjunction size before checking - there
+                    // is no point in looping if we're just going to fail all the input checks around
+                    // the next iteration.
+                    ASSERT(alternative->m_minimumSize >= m_pattern.m_body->m_minimumSize);
+                    if (alternative->m_minimumSize == m_pattern.m_body->m_minimumSize) {
+                        // If the last alternative had the same minimum size as the disjunction,
+                        // just simply increment input pos by 1, no adjustment based on minimum size.
+                        add32(TrustedImm32(1), index);
+                    } else {
+                        // If the minumum for the last alternative was one greater than than that
+                        // for the disjunction, we're already progressed by 1, nothing to do!
+                        unsigned delta = (alternative->m_minimumSize - m_pattern.m_body->m_minimumSize) - 1;
+                        if (delta)
+                            sub32(Imm32(delta), index);
+                    }
+                    Jump matchFailed = jumpIfNoAvailableInput();
+
+                    if (needsToUpdateMatchStart) {
+                        if (!m_pattern.m_body->m_minimumSize)
+                            setMatchStart(index);
+                        else {
+                            move(index, regT0);
+                            sub32(Imm32(m_pattern.m_body->m_minimumSize), regT0);
+                            setMatchStart(regT0);
+                        }
+                    }
+
+                    // Calculate how much more input the first alternative requires than the minimum
+                    // for the body as a whole. If no more is needed then we dont need an additional
+                    // input check here - jump straight back up to the start of the first alternative.
+                    if (beginOp->m_alternative->m_minimumSize == m_pattern.m_body->m_minimumSize)
+                        jump(beginOp->m_reentry);
                     else {
-                        move(index, regT0);
-                        sub32(Imm32(m_pattern.m_body->m_minimumSize), regT0);
-                        setMatchStart(regT0);
+                        if (beginOp->m_alternative->m_minimumSize > m_pattern.m_body->m_minimumSize)
+                            add32(Imm32(beginOp->m_alternative->m_minimumSize - m_pattern.m_body->m_minimumSize), index);
+                        else
+                            sub32(Imm32(m_pattern.m_body->m_minimumSize - beginOp->m_alternative->m_minimumSize), index);
+                        checkInput().linkTo(beginOp->m_reentry, this);
+                        jump(firstInputCheckFailed);
                     }
-                }
-
-                // Calculate how much more input the first alternative requires than the minimum
-                // for the body as a whole. If no more is needed then we dont need an additional
-                // input check here - jump straight back up to the start of the first alternative.
-                if (beginOp->m_alternative->m_minimumSize == m_pattern.m_body->m_minimumSize)
-                    jump(beginOp->m_reentry);
-                else {
-                    if (beginOp->m_alternative->m_minimumSize > m_pattern.m_body->m_minimumSize)
-                        add32(Imm32(beginOp->m_alternative->m_minimumSize - m_pattern.m_body->m_minimumSize), index);
-                    else
-                        sub32(Imm32(m_pattern.m_body->m_minimumSize - beginOp->m_alternative->m_minimumSize), index);
-                    checkInput().linkTo(beginOp->m_reentry, this);
-                    jump(firstInputCheckFailed);
-                }
-
-                // We jump to here if we iterate to the point that there is insufficient input to
-                // run any matches, and need to return a failure state from JIT code.
-                matchFailed.link(this);
-
+
+                    // We jump to here if we iterate to the point that there is insufficient input to
+                    // run any matches, and need to return a failure state from JIT code.
+                    matchFailed.link(this);
+                }
                 removeCallFrame();
                 generateFailReturn();