Changeset 73866 in webkit
- Timestamp:
- Dec 11, 2010 7:24:56 PM (13 years ago)
- Location:
- trunk
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/JavaScriptCore/ChangeLog
r73853 r73866 1 2010-12-10 Michael Saboff <msaboff@apple.com> 2 3 Reviewed by Gavin Barraclough. 4 5 REGRESSION Hang inside Yarr::RegexCodeBlock::execute when visiting 6 bugs.webkit.org 7 https://bugs.webkit.org/show_bug.cgi?id=50816 8 9 First nested parentheses of the second or greater alternative 10 where backtracking to the prior parentheses. Changed the default 11 handling of initial parentheses for all alternatives to go back 12 to the immediate outer paren. 13 14 * yarr/RegexJIT.cpp: 15 (JSC::Yarr::RegexGenerator::GenerationState::addParenthesesTail): 16 (JSC::Yarr::RegexGenerator::TermGenerationState::TermGenerationState): 17 (JSC::Yarr::RegexGenerator::TermGenerationState::isLastTerm): 18 (JSC::Yarr::RegexGenerator::TermGenerationState::getTermIndex): 19 (JSC::Yarr::RegexGenerator::TermGenerationState::setParenthesesTail): 20 (JSC::Yarr::RegexGenerator::TermGenerationState::getParenthesesTail): 21 (JSC::Yarr::RegexGenerator::ParenthesesTail::ParenthesesTail): 22 (JSC::Yarr::RegexGenerator::ParenthesesTail::processBacktracks): 23 (JSC::Yarr::RegexGenerator::ParenthesesTail::generateCode): 24 (JSC::Yarr::RegexGenerator::generateParenthesesSingle): 25 1 26 2010-12-11 Patrick Gansterer <paroga@webkit.org> 2 27 -
trunk/JavaScriptCore/yarr/RegexJIT.cpp
r73640 r73866 375 375 } 376 376 377 ParenthesesTail* addParenthesesTail(PatternTerm& term )378 { 379 ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel );377 ParenthesesTail* addParenthesesTail(PatternTerm& term, ParenthesesTail* nextOuterParenTail) 378 { 379 ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, nextOuterParenTail); 380 380 m_parenTails.append(parenthesesTail); 381 381 m_parenTailsForIteration.append(parenthesesTail); … … 767 767 : disjunction(disjunction) 768 768 , checkedTotal(checkedTotal) 769 , m_subParenNum(0) 769 770 , m_linkedBacktrack(0) 771 , m_parenthesesTail(0) 770 772 { 771 773 } … … 797 799 ASSERT(alternativeValid()); 798 800 t = 0; 801 m_subParenNum = 0; 799 802 } 800 803 bool termValid() … … 817 820 ASSERT(alternativeValid()); 818 821 return (t + 1) == alternative()->m_terms.size(); 822 } 823 unsigned getSubParenNum() 824 { 825 return m_subParenNum++; 819 826 } 820 827 bool isMainDisjunction() … … 822 829 return !disjunction->m_parent; 823 830 } 824 831 832 void setParenthesesTail(ParenthesesTail* parenthesesTail) 833 { 834 m_parenthesesTail = parenthesesTail; 835 } 836 837 ParenthesesTail* getParenthesesTail() 838 { 839 return m_parenthesesTail; 840 } 841 825 842 PatternTerm& lookaheadTerm() 826 843 { … … 950 967 unsigned alt; 951 968 unsigned t; 969 unsigned m_subParenNum; 952 970 BacktrackDestination m_backtrack; 953 971 BacktrackDestination* m_linkedBacktrack; 972 ParenthesesTail* m_parenthesesTail; 954 973 955 974 }; 956 975 957 976 struct ParenthesesTail { 958 ParenthesesTail(PatternTerm& term, int nestingLevel )977 ParenthesesTail(PatternTerm& term, int nestingLevel, ParenthesesTail* nextOuterParenTail) 959 978 : m_term(term) 960 979 , m_nestingLevel(nestingLevel) 980 , m_subParenIndex(0) 981 , m_nextOuterParenTail(nextOuterParenTail) 961 982 { 962 983 } … … 967 988 m_fallThrough = fallThrough; 968 989 990 m_subParenIndex = state.getSubParenNum(); 969 991 parenthesesState.getBacktrackDestination().copyTo(m_parenBacktrack); 970 992 state.chainBacktracks(&m_backtrack); … … 1024 1046 m_backtrack.setLabel(m_backtrackToLabel); 1025 1047 nextBacktrackFallThrough = false; 1048 } else if (!m_subParenIndex && m_nextOuterParenTail) { 1049 // If we don't have a destination and we are the first term of a nested paren, go 1050 // back to the outer paren. 1051 // There is an optimization if the next outer paren is the next paren to be emitted. 1052 // In that case we really want the else clause. 1053 m_backtrack.setBacktrackJumpList(&m_nextOuterParenTail->m_withinBacktrackJumps); 1054 nextBacktrackFallThrough = false; 1026 1055 } else 1027 1056 m_backtrack.setBacktrackJumpList(&jumpsToNext); … … 1054 1083 fromPriorBacktrack.link(generator); 1055 1084 m_parenBacktrack.linkAlternativeBacktracks(generator); 1085 m_withinBacktrackJumps.link(generator); 1056 1086 1057 1087 if (m_term.capture()) … … 1073 1103 PatternTerm& m_term; 1074 1104 int m_nestingLevel; 1105 unsigned m_subParenIndex; 1106 ParenthesesTail* m_nextOuterParenTail; 1075 1107 Label m_nonGreedyTryParentheses; 1076 1108 Label m_fallThrough; … … 1079 1111 DataLabelPtr m_dataAfterLabelPtr; 1080 1112 JumpList m_pattBacktrackJumps; 1113 JumpList m_withinBacktrackJumps; 1081 1114 BacktrackDestination m_parenBacktrack; 1082 1115 BacktrackDestination m_backtrack; … … 1599 1632 } 1600 1633 1601 ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term );1634 ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getParenthesesTail()); 1602 1635 1603 1636 m_expressionState.incrementParenNestingLevel(); 1604 1637 1638 TermGenerationState parenthesesState(disjunction, state.checkedTotal); 1639 1640 // Save the parenthesesTail for backtracking from nested parens to this one. 1641 parenthesesState.setParenthesesTail(parenthesesTail); 1642 1605 1643 // generate the body of the parentheses 1606 TermGenerationState parenthesesState(disjunction, state.checkedTotal);1607 1644 generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation); 1608 1645 -
trunk/LayoutTests/ChangeLog
r73863 r73866 1 2010-12-10 Michael Saboff <msaboff@apple.com> 2 3 Reviewed by Gavin Barraclough. 4 5 REGRESSION Hang inside Yarr::RegexCodeBlock::execute when visiting 6 bugs.webkit.org 7 https://bugs.webkit.org/show_bug.cgi?id=50816 8 9 New test to verify proper backtracking of alternative nested parens. 10 11 * fast/regex/parentheses-expected.txt: 12 * fast/regex/script-tests/parentheses.js: 13 1 14 2010-12-11 Pavel Feldman <pfeldman@chromium.org> 2 15 -
trunk/LayoutTests/fast/regex/parentheses-expected.txt
r73640 r73866 34 34 PASS regexp27.exec('file:///Users/Someone/Desktop/HelloWorld/index.html') is ['file:///Users/Someone/Desktop/HelloWorld/index.html','file','//','',undefined,undefined,undefined,'',undefined,'/Users/Someone/Desktop/HelloWorld/index.html',undefined,undefined] 35 35 PASS regexp28.exec('file:///Users/Someone/Desktop/HelloWorld/index.html') is ['file:','file',undefined,undefined,undefined,undefined,undefined] 36 PASS regexp29.exec('Committer:') is null 37 PASS regexp30.exec('Committer:') is null 38 PASS regexp31.exec('Committer:') is null 39 PASS regexp32.exec('Committer:') is null 36 40 PASS 'Hi Bob'.match(/(Rob)|(Bob)|(Robert)|(Bobby)/) is ['Bob',undefined,'Bob',undefined,undefined] 37 41 PASS successfullyParsed is true -
trunk/LayoutTests/fast/regex/script-tests/parentheses.js
r73640 r73866 126 126 shouldBe("regexp28.exec('file:///Users/Someone/Desktop/HelloWorld/index.html')", "['file:','file',undefined,undefined,undefined,undefined,undefined]"); 127 127 128 var regexp29 = /^\s*((\[[^\]]+\])|(u?)("[^"]+"))\s*/; 129 shouldBeNull("regexp29.exec('Committer:')"); 130 131 var regexp30 = /^\s*((\[[^\]]+\])|m(u?)("[^"]+"))\s*/; 132 shouldBeNull("regexp30.exec('Committer:')"); 133 134 var regexp31 = /^\s*(m(\[[^\]]+\])|m(u?)("[^"]+"))\s*/; 135 shouldBeNull("regexp31.exec('Committer:')"); 136 137 var regexp32 = /\s*(m(\[[^\]]+\])|m(u?)("[^"]+"))\s*/; 138 shouldBeNull("regexp32.exec('Committer:')"); 139 128 140 shouldBe("'Hi Bob'.match(/(Rob)|(Bob)|(Robert)|(Bobby)/)", "['Bob',undefined,'Bob',undefined,undefined]"); 129 141
Note: See TracChangeset
for help on using the changeset viewer.