2011-02-02 Michael Saboff <msaboff@apple.com>
Reviewed by Gavin Barraclough.
Improper backtrack of nested non-capturing greedy paren to prior paren
https://bugs.webkit.org/show_bug.cgi?id=53261
A paren that follows a non-capturing greedy paren nested within a
non-capturing fixed paren was back tracking to the last paren
processed instead of the immediately prior paren.
Refactored default backtracking of parens to prior paren to work for
both nested (within) and immediately prior (after) parens.
* yarr/YarrJIT.cpp:
(JSC::Yarr::YarrGenerator::GenerationState::addParenthesesTail):
(JSC::Yarr::YarrGenerator::TermGenerationState::TermGenerationState):
(JSC::Yarr::YarrGenerator::TermGenerationState::setJumpListToPriorParen):
(JSC::Yarr::YarrGenerator::TermGenerationState::getJumpListToPriorParen):
(JSC::Yarr::YarrGenerator::ParenthesesTail::ParenthesesTail):
(JSC::Yarr::YarrGenerator::ParenthesesTail::generateCode):
(JSC::Yarr::YarrGenerator::generateParenthesesDisjunction):
(JSC::Yarr::YarrGenerator::generateParenthesesSingle):
(JSC::Yarr::YarrGenerator::generateDisjunction):
2011-02-02 Michael Saboff <msaboff@apple.com>
Reviewed by Gavin Barraclough.
Improper backtrack of nested non-capturing greedy paren to prior paren
https://bugs.webkit.org/show_bug.cgi?id=53261
New tests to validate change.
* fast/regex/parentheses-expected.txt:
* fast/regex/script-tests/parentheses.js:
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@77439 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/LayoutTests/ChangeLog b/LayoutTests/ChangeLog
index 74e0fd8..6db339d 100644
--- a/LayoutTests/ChangeLog
+++ b/LayoutTests/ChangeLog
@@ -1,3 +1,15 @@
+2011-02-02 Michael Saboff <msaboff@apple.com>
+
+ Reviewed by Gavin Barraclough.
+
+ Improper backtrack of nested non-capturing greedy paren to prior paren
+ https://bugs.webkit.org/show_bug.cgi?id=53261
+
+ New tests to validate change.
+
+ * fast/regex/parentheses-expected.txt:
+ * fast/regex/script-tests/parentheses.js:
+
2011-02-02 Dirk Pranke <dpranke@chromium.org>
Reviewed by Mihai Parparita.
diff --git a/LayoutTests/fast/regex/parentheses-expected.txt b/LayoutTests/fast/regex/parentheses-expected.txt
index 0d4458d..872d633 100644
--- a/LayoutTests/fast/regex/parentheses-expected.txt
+++ b/LayoutTests/fast/regex/parentheses-expected.txt
@@ -79,6 +79,9 @@
PASS regexp46.exec('pk') is ['pk',undefined,undefined]
PASS regexp46.exec('Xw555') is ['w555','w',undefined]
PASS regexp46.exec('Xw55pk5') is ['w','w','']
+PASS regexp47.exec('/www.acme.com/this/is/a/path/file.txt') is ['/www.acme.com/this/is/a/path/file.txt','/www.acme.com/this/is/a/path/file.txt',undefined]
+PASS regexp48.exec('http://www.acme.com/this/is/a/path/file.txt') is ['http://www.acme.com/this/is/a/path/file.txt','http','www.acme.com',undefined,'this/is/a/path/file.txt',undefined,undefined]
+PASS regexp49.exec('http://www.acme.com/this/is/a/path/file.txt') is ['http://www.acme.com/this/is/a/path/file.txt',undefined,undefined,'http','www.acme.com',undefined,'this/is/a/path/file.txt',undefined,undefined]
PASS 'Hi Bob'.match(/(Rob)|(Bob)|(Robert)|(Bobby)/) is ['Bob',undefined,'Bob',undefined,undefined]
PASS successfullyParsed is true
diff --git a/LayoutTests/fast/regex/script-tests/parentheses.js b/LayoutTests/fast/regex/script-tests/parentheses.js
index f942e80..cb38974 100644
--- a/LayoutTests/fast/regex/script-tests/parentheses.js
+++ b/LayoutTests/fast/regex/script-tests/parentheses.js
@@ -208,6 +208,15 @@
shouldBe("regexp46.exec('Xw555')", "['w555','w',undefined]");
shouldBe("regexp46.exec('Xw55pk5')", "['w','w','']");
+var regexp47 = /(.*?)(?:(?:\?(.*?)?)?)(?:(?:#)?)$/;
+shouldBe("regexp47.exec('/www.acme.com/this/is/a/path/file.txt')", "['/www.acme.com/this/is/a/path/file.txt','/www.acme.com/this/is/a/path/file.txt',undefined]");
+
+var regexp48 = /^(?:(\w+):\/*([\w\.\-\d]+)(?::(\d+)|)(?=(?:\/|$))|)(?:$|\/?(.*?)(?:\?(.*?)?|)(?:#(.*)|)$)/;
+shouldBe("regexp48.exec('http://www.acme.com/this/is/a/path/file.txt')", "['http://www.acme.com/this/is/a/path/file.txt','http','www.acme.com',undefined,'this/is/a/path/file.txt',undefined,undefined]");
+
+var regexp49 = /(?:([^:]*?)(?:(?:\?(.*?)?)?)(?:(?:#)?)$)|(?:^(?:(\w+):\/*([\w\.\-\d]+)(?::(\d+)|)(?=(?:\/|$))|)(?:$|\/?(.*?)(?:\?(.*?)?|)(?:#(.*)|)$))/;
+shouldBe("regexp49.exec('http://www.acme.com/this/is/a/path/file.txt')", "['http://www.acme.com/this/is/a/path/file.txt',undefined,undefined,'http','www.acme.com',undefined,'this/is/a/path/file.txt',undefined,undefined]");
+
shouldBe("'Hi Bob'.match(/(Rob)|(Bob)|(Robert)|(Bobby)/)", "['Bob',undefined,'Bob',undefined,undefined]");
var successfullyParsed = true;
diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
index 4a9082e..fa2f4ce 100644
--- a/Source/JavaScriptCore/ChangeLog
+++ b/Source/JavaScriptCore/ChangeLog
@@ -1,3 +1,27 @@
+2011-02-02 Michael Saboff <msaboff@apple.com>
+
+ Reviewed by Gavin Barraclough.
+
+ Improper backtrack of nested non-capturing greedy paren to prior paren
+ https://bugs.webkit.org/show_bug.cgi?id=53261
+
+ A paren that follows a non-capturing greedy paren nested within a
+ non-capturing fixed paren was back tracking to the last paren
+ processed instead of the immediately prior paren.
+ Refactored default backtracking of parens to prior paren to work for
+ both nested (within) and immediately prior (after) parens.
+
+ * yarr/YarrJIT.cpp:
+ (JSC::Yarr::YarrGenerator::GenerationState::addParenthesesTail):
+ (JSC::Yarr::YarrGenerator::TermGenerationState::TermGenerationState):
+ (JSC::Yarr::YarrGenerator::TermGenerationState::setJumpListToPriorParen):
+ (JSC::Yarr::YarrGenerator::TermGenerationState::getJumpListToPriorParen):
+ (JSC::Yarr::YarrGenerator::ParenthesesTail::ParenthesesTail):
+ (JSC::Yarr::YarrGenerator::ParenthesesTail::generateCode):
+ (JSC::Yarr::YarrGenerator::generateParenthesesDisjunction):
+ (JSC::Yarr::YarrGenerator::generateParenthesesSingle):
+ (JSC::Yarr::YarrGenerator::generateDisjunction):
+
2011-02-02 Jeff Miller <jeffm@apple.com>
Reviewed by Darin Adler and Steve Falkenburg.
diff --git a/Source/JavaScriptCore/yarr/YarrJIT.cpp b/Source/JavaScriptCore/yarr/YarrJIT.cpp
index 9d13d45..cdb7136 100644
--- a/Source/JavaScriptCore/yarr/YarrJIT.cpp
+++ b/Source/JavaScriptCore/yarr/YarrJIT.cpp
@@ -407,9 +407,9 @@
--m_parenNestingLevel;
}
- ParenthesesTail* addParenthesesTail(PatternTerm& term, ParenthesesTail* nextOuterParenTail)
+ ParenthesesTail* addParenthesesTail(PatternTerm& term, JumpList* jumpListToPriorParen)
{
- ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, nextOuterParenTail);
+ ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, jumpListToPriorParen);
m_parenTails.append(parenthesesTail);
m_parenTailsForIteration.append(parenthesesTail);
@@ -815,7 +815,7 @@
, checkedTotal(checkedTotal)
, m_subParenNum(0)
, m_linkedBacktrack(0)
- , m_parenthesesTail(0)
+ , m_jumpList(0)
{
}
@@ -876,14 +876,14 @@
return !disjunction->m_parent;
}
- void setParenthesesTail(ParenthesesTail* parenthesesTail)
+ void setJumpListToPriorParen(JumpList* jumpList)
{
- m_parenthesesTail = parenthesesTail;
+ m_jumpList = jumpList;
}
- ParenthesesTail* getParenthesesTail()
+ JumpList* getJumpListToPriorParen()
{
- return m_parenthesesTail;
+ return m_jumpList;
}
PatternTerm& lookaheadTerm()
@@ -1018,15 +1018,15 @@
unsigned m_subParenNum;
BacktrackDestination m_backtrack;
BacktrackDestination* m_linkedBacktrack;
- ParenthesesTail* m_parenthesesTail;
+ JumpList* m_jumpList;
};
struct ParenthesesTail {
- ParenthesesTail(PatternTerm& term, int nestingLevel, ParenthesesTail* nextOuterParenTail)
+ ParenthesesTail(PatternTerm& term, int nestingLevel, JumpList* jumpListToPriorParen)
: m_term(term)
, m_nestingLevel(nestingLevel)
, m_subParenIndex(0)
- , m_nextOuterParenTail(nextOuterParenTail)
+ , m_jumpListToPriorParen(jumpListToPriorParen)
{
}
@@ -1052,7 +1052,7 @@
if (m_doDirectBacktrack)
state.propagateBacktrackingFrom(generator, m_parenBacktrack, false);
else {
- stateBacktrack.setBacktrackJumpList(&m_pattBacktrackJumps);
+ stateBacktrack.setBacktrackJumpList(&m_afterBacktrackJumps);
stateBacktrack.setBacktrackSourceLabel(&m_backtrackFromAfterParens);
}
}
@@ -1065,7 +1065,7 @@
void addAfterParenJump(Jump jump)
{
- m_pattBacktrackJumps.append(jump);
+ m_afterBacktrackJumps.append(jump);
}
bool generateCode(YarrGenerator* generator, JumpList& jumpsToNext, bool priorBackTrackFallThrough, bool nextBacktrackFallThrough)
@@ -1091,12 +1091,9 @@
if (m_backtrackToLabel.isSet()) {
m_backtrack.setLabel(m_backtrackToLabel);
nextBacktrackFallThrough = false;
- } else if (!m_subParenIndex && m_nextOuterParenTail) {
- // If we don't have a destination and we are the first term of a nested paren, go
- // back to the outer paren.
- // There is an optimization if the next outer paren is the next paren to be emitted.
- // In that case we really want the else clause.
- m_backtrack.setBacktrackJumpList(&m_nextOuterParenTail->m_withinBacktrackJumps);
+ } else if (m_jumpListToPriorParen) {
+ // If we don't have a destination, go back to either the prior paren or the next outer paren.
+ m_backtrack.setBacktrackJumpList(m_jumpListToPriorParen);
nextBacktrackFallThrough = false;
} else
m_backtrack.setBacktrackJumpList(&jumpsToNext);
@@ -1109,7 +1106,7 @@
if (m_dataAfterLabelPtr.isSet())
generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataAfterLabelPtr, m_backtrackFromAfterParens));
- m_pattBacktrackJumps.link(generator);
+ m_afterBacktrackJumps.link(generator);
if (m_term.quantityType == QuantifierGreedy) {
// If this is -1 we have now tested with both with and without the parens.
@@ -1149,14 +1146,14 @@
PatternTerm& m_term;
int m_nestingLevel;
unsigned m_subParenIndex;
- ParenthesesTail* m_nextOuterParenTail;
+ JumpList* m_jumpListToPriorParen;
Label m_nonGreedyTryParentheses;
Label m_fallThrough;
Label m_backtrackToLabel;
Label m_backtrackFromAfterParens;
DataLabelPtr m_dataAfterLabelPtr;
- JumpList m_pattBacktrackJumps;
JumpList m_withinBacktrackJumps;
+ JumpList m_afterBacktrackJumps;
BacktrackDestination m_parenBacktrack;
BacktrackDestination m_backtrack;
bool m_doDirectBacktrack;
@@ -1581,8 +1578,10 @@
JumpList successes;
bool propogateBacktrack = false;
- for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative()) {
+ // Save current state's paren jump list for use with each alternative
+ JumpList* outerJumpList = state.getJumpListToPriorParen();
+ for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative(), state.setJumpListToPriorParen(outerJumpList)) {
PatternAlternative* alternative = state.alternative();
optimizeAlternative(alternative);
@@ -1649,9 +1648,9 @@
m_expressionState.incrementParenNestingLevel();
TermGenerationState parenthesesState(disjunction, state.checkedTotal);
-
- // Use the current paren Tail to connect the nested parentheses.
- parenthesesState.setParenthesesTail(state.getParenthesesTail());
+
+ // Use the current state's jump list for the nested parentheses.
+ parenthesesState.setJumpListToPriorParen(state.getJumpListToPriorParen());
generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
// this expects that any backtracks back out of the parentheses will be in the
@@ -1663,6 +1662,8 @@
state.propagateBacktrackingFrom(this, parenthesesBacktrack);
stateBacktrack.propagateBacktrackToLabel(parenthesesBacktrack);
+ state.setJumpListToPriorParen(parenthesesState.getJumpListToPriorParen());
+
m_expressionState.decrementParenNestingLevel();
} else {
Jump nonGreedySkipParentheses;
@@ -1687,14 +1688,14 @@
store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
}
- ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getParenthesesTail());
+ ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getJumpListToPriorParen());
m_expressionState.incrementParenNestingLevel();
TermGenerationState parenthesesState(disjunction, state.checkedTotal);
// Save the parenthesesTail for backtracking from nested parens to this one.
- parenthesesState.setParenthesesTail(parenthesesTail);
+ parenthesesState.setJumpListToPriorParen(&parenthesesTail->m_withinBacktrackJumps);
// generate the body of the parentheses
generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
@@ -1718,6 +1719,8 @@
parenthesesTail->processBacktracks(this, state, parenthesesState, nonGreedyTryParentheses, label());
+ state.setJumpListToPriorParen(&parenthesesTail->m_afterBacktrackJumps);
+
parenthesesState.getBacktrackDestination().clear();
if (term.quantityType == QuantifierNonGreedy)
@@ -1977,6 +1980,7 @@
// if there are any more alternatives, plant the check for input before looping.
if (state.alternativeValid()) {
+ state.setJumpListToPriorParen(0);
PatternAlternative* nextAlternative = state.alternative();
if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) {
// We have handled non-repeating alternatives, jump to next iteration
