Modified: trunk/LayoutTests/ChangeLog (165299 => 165300)
--- trunk/LayoutTests/ChangeLog 2014-03-08 00:33:55 UTC (rev 165299)
+++ trunk/LayoutTests/ChangeLog 2014-03-08 00:40:11 UTC (rev 165300)
@@ -1,3 +1,15 @@
+2014-03-07 Benjamin Poulain <[email protected]>
+
+ Traversal failure in a direct adjacent chain with tail backtracking lacks the path to clear the tail
+ https://bugs.webkit.org/show_bug.cgi?id=129863
+
+ Reviewed by Gavin Barraclough.
+
+ Test the faulty case.
+
+ * fast/selectors/long-adjacent-backtracking-expected.txt: Added.
+ * fast/selectors/long-adjacent-backtracking.html: Added.
+
2014-03-07 Bear Travis <[email protected]>
[CSS Shapes] Correctly serialize ellipse positions
Added: trunk/LayoutTests/fast/selectors/long-adjacent-backtracking-expected.txt (0 => 165300)
--- trunk/LayoutTests/fast/selectors/long-adjacent-backtracking-expected.txt (rev 0)
+++ trunk/LayoutTests/fast/selectors/long-adjacent-backtracking-expected.txt 2014-03-08 00:40:11 UTC (rev 165300)
@@ -0,0 +1,12 @@
+Test very long backtracking of a direct adjacent chain.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS document.querySelectorAll("li.first+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li~li").length is 20
+PASS allItems.length is 41
+PASS coloredCount is 20
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/fast/selectors/long-adjacent-backtracking.html (0 => 165300)
--- trunk/LayoutTests/fast/selectors/long-adjacent-backtracking.html (rev 0)
+++ trunk/LayoutTests/fast/selectors/long-adjacent-backtracking.html 2014-03-08 00:40:11 UTC (rev 165300)
@@ -0,0 +1,75 @@
+<!doctype html>
+<html>
+<head>
+<script src=""
+<style>
+li.first+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li~li {
+ background-color: rgb(1, 2, 3);
+}
+</style>
+</head>
+<body>
+<div style="display:none">
+ <ul id=targetTree>
+ <li class=first></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ <li class=target></li>
+ </ul>
+</div>
+</body>
+<script>
+description('Test very long backtracking of a direct adjacent chain.');
+
+shouldBe('document.querySelectorAll("li.first+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li+li~li").length', '20');
+
+var allItems = document.getElementById('targetTree').querySelectorAll('li');
+var coloredCount = 0;
+for (var i = 0; i < allItems.length; ++i) {
+ if (getComputedStyle(allItems[i]).backgroundColor === 'rgb(1, 2, 3)')
+ coloredCount++;
+}
+
+shouldBe('allItems.length', '41');
+shouldBe('coloredCount', '20');
+
+</script>
+<script src=""
+</html>
Modified: trunk/Source/WebCore/ChangeLog (165299 => 165300)
--- trunk/Source/WebCore/ChangeLog 2014-03-08 00:33:55 UTC (rev 165299)
+++ trunk/Source/WebCore/ChangeLog 2014-03-08 00:40:11 UTC (rev 165300)
@@ -1,3 +1,31 @@
+2014-03-07 Benjamin Poulain <[email protected]>
+
+ Traversal failure in a direct adjacent chain with tail backtracking lacks the path to clear the tail
+ https://bugs.webkit.org/show_bug.cgi?id=129863
+
+ Reviewed by Gavin Barraclough.
+
+ Direct adjacent backtracking use the stack to push the backtracking entry point and recover from there.
+ In case of traversal failure, their is no point in recovering from the indirect adjancent entry point and
+ we should clear entry point from the stack (which is the purpose of the tail).
+
+ The adjancent tail was missing the part for clearing the stack in one case.
+
+ The case with adjancent backtracking inside descendant backtracing was doing everything right. This patch
+ generalize this code and the correct tail is fully generated by generateAdjacentBacktrackingTail().
+
+ JumpToClearAdjacentDescendantTail becomes JumpToClearAdjacentTail, and this new backtracking state is added
+ to the missing traversal action.
+
+ Test: fast/selectors/long-adjacent-backtracking.html
+
+ * cssjit/SelectorCompiler.cpp:
+ (WebCore::SelectorCompiler::solveBacktrackingAction):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateSelectorChecker):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::linkFailures):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateAdjacentBacktrackingTail):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateBacktrackingTailsIfNeeded):
+
2014-03-07 Andreas Kling <[email protected]>
[Mac] Notify system malloc of fake memory pressure.
Modified: trunk/Source/WebCore/cssjit/SelectorCompiler.cpp (165299 => 165300)
--- trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2014-03-08 00:33:55 UTC (rev 165299)
+++ trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2014-03-08 00:40:11 UTC (rev 165300)
@@ -61,8 +61,8 @@
JumpToIndirectAdjacentEntryPoint,
JumpToDescendantTreeWalkerEntryPoint,
JumpToDescendantTail,
- JumpToClearAdjacentDescendantTail,
- JumpToDirectAdjacentTail
+ JumpToDirectAdjacentTail,
+ JumpToClearAdjacentTail
};
struct BacktrackingFlag {
@@ -161,9 +161,9 @@
void markParentElementIfResolvingStyle(JSC::FunctionPtr);
void linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction, Assembler::JumpList& localFailureCases);
- void generateAdjacentBacktrackingTail(StackAllocator& adjacentTailStack);
+ void generateAdjacentBacktrackingTail(Assembler::JumpList& failureCases);
void generateDescendantBacktrackingTail();
- void generateBacktrackingTailsIfNeeded(const SelectorFragment&);
+ void generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
// Element properties matchers.
void generateElementMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
@@ -199,7 +199,7 @@
Assembler::JumpList m_descendantBacktrackingFailureCases;
StackAllocator::StackReference m_adjacentBacktrackingStart;
Assembler::JumpList m_adjacentBacktrackingFailureCases;
- Assembler::JumpList m_clearAdjacentEntryPointDescendantFailureCases;
+ Assembler::JumpList m_clearAdjacentBacktrackingFailureCases;
#if CSS_SELECTOR_JIT_DEBUGGING
const CSSSelector* m_originalSelector;
@@ -545,8 +545,12 @@
if (!hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain || isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk))
fragment.traversalBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
else
- fragment.traversalBacktrackingAction = BacktrackingAction::JumpToClearAdjacentDescendantTail;
+ fragment.traversalBacktrackingAction = BacktrackingAction::JumpToClearAdjacentTail;
}
+ } else {
+ // If we are in a direct adjacent chain with backtracking, we need to clear the backtracking register on the stack.
+ if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain && !isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk))
+ fragment.traversalBacktrackingAction = BacktrackingAction::JumpToClearAdjacentTail;
}
// If the rightmost relation is a indirect adjacent, matching sould resume from there.
@@ -559,7 +563,7 @@
} else if (hasDescendantRelationOnTheRight) {
if (isAfterChildRelation(ancestorPositionSinceDescendantRelation))
fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
- else if (hasDescendantRelationOnTheRight)
+ else
fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
}
break;
@@ -667,7 +671,7 @@
generateIndirectAdjacentTreeWalker(failureCases, fragment);
break;
}
- generateBacktrackingTailsIfNeeded(fragment);
+ generateBacktrackingTailsIfNeeded(failureCases, fragment);
}
m_registerAllocator.deallocateRegister(elementAddressRegister);
@@ -706,7 +710,7 @@
StackAllocator failureStack = m_stackAllocator;
LocalRegister checkingContextRegister(m_registerAllocator);
- successStack.pop(m_checkingContextStackReference, checkingContextRegister);
+ successStack.popAndDiscardUpTo(m_checkingContextStackReference);
// Failure.
if (!failureCases.empty()) {
@@ -900,18 +904,32 @@
case BacktrackingAction::JumpToDirectAdjacentTail:
m_adjacentBacktrackingFailureCases.append(localFailureCases);
break;
- case BacktrackingAction::JumpToClearAdjacentDescendantTail:
- m_clearAdjacentEntryPointDescendantFailureCases.append(localFailureCases);
+ case BacktrackingAction::JumpToClearAdjacentTail:
+ m_clearAdjacentBacktrackingFailureCases.append(localFailureCases);
break;
}
}
-void SelectorCodeGenerator::generateAdjacentBacktrackingTail(StackAllocator& adjacentTailStack)
+void SelectorCodeGenerator::generateAdjacentBacktrackingTail(Assembler::JumpList& successCases)
{
+ StackAllocator successStack = m_stackAllocator;
+ StackAllocator recoveryStack = m_stackAllocator;
+ StackAllocator failureStack = m_stackAllocator;
+
+ successStack.popAndDiscard(m_adjacentBacktrackingStart);
+ successCases.append(m_assembler.jump());
+
+ // Recovering tail.
m_adjacentBacktrackingFailureCases.link(&m_assembler);
m_adjacentBacktrackingFailureCases.clear();
- adjacentTailStack.pop(m_adjacentBacktrackingStart, elementAddressRegister);
+ recoveryStack.pop(m_adjacentBacktrackingStart, elementAddressRegister);
m_assembler.jump(m_indirectAdjacentEntryPoint);
+
+ // Total failure tail.
+ m_clearAdjacentBacktrackingFailureCases.link(&m_assembler);
+ failureStack.popAndDiscard(m_adjacentBacktrackingStart);
+
+ m_stackAllocator.merge(std::move(successStack), std::move(recoveryStack), std::move(failureStack));
}
void SelectorCodeGenerator::generateDescendantBacktrackingTail()
@@ -923,39 +941,18 @@
m_assembler.jump(m_descendantEntryPoint);
}
-void SelectorCodeGenerator::generateBacktrackingTailsIfNeeded(const SelectorFragment& fragment)
+void SelectorCodeGenerator::generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
{
if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail && fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
- StackAllocator successStack = m_stackAllocator;
- StackAllocator adjacentTailStack = m_stackAllocator;
- StackAllocator descendantTailStack = m_stackAllocator;
-
- successStack.popAndDiscard(m_adjacentBacktrackingStart);
-
- Assembler::Jump normalCase = m_assembler.jump();
-
- generateAdjacentBacktrackingTail(adjacentTailStack);
-
- m_clearAdjacentEntryPointDescendantFailureCases.link(&m_assembler);
- m_clearAdjacentEntryPointDescendantFailureCases.clear();
- descendantTailStack.popAndDiscard(m_adjacentBacktrackingStart);
-
+ Assembler::JumpList successCases;
+ generateAdjacentBacktrackingTail(successCases);
generateDescendantBacktrackingTail();
-
- normalCase.link(&m_assembler);
-
- m_stackAllocator.merge(std::move(successStack), std::move(adjacentTailStack), std::move(descendantTailStack));
+ successCases.link(&m_assembler);
} else if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail) {
- StackAllocator successStack = m_stackAllocator;
- StackAllocator adjacentTailStack = m_stackAllocator;
-
- successStack.popAndDiscard(m_adjacentBacktrackingStart);
-
- Assembler::Jump normalCase = m_assembler.jump();
- generateAdjacentBacktrackingTail(adjacentTailStack);
- normalCase.link(&m_assembler);
-
- m_stackAllocator.merge(std::move(successStack), std::move(adjacentTailStack));
+ Assembler::JumpList successCases;
+ generateAdjacentBacktrackingTail(successCases);
+ failureCases.append(m_assembler.jump());
+ successCases.link(&m_assembler);
} else if (fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
Assembler::Jump normalCase = m_assembler.jump();
generateDescendantBacktrackingTail();
