From df8e5a69b08c132cdce518b545d9987460f2fcce Mon Sep 17 00:00:00 2001 From: "benjamin@webkit.org" Date: Tue, 21 Oct 2014 00:43:29 +0000 Subject: [PATCH] Generalize the compilation of :not() to support arbitrary selector lists https://bugs.webkit.org/show_bug.cgi?id=137843 Patch by Benjamin Poulain on 2014-10-20 Reviewed by Andreas Kling. This builds :not() on top of the code created for :nth-child(An+B of selectorList) to support any selector list. The tests for the JIT were added previously: -not-boundaries.html -not-backtracking.html * cssjit/SelectorCompiler.cpp: (WebCore::SelectorCompiler::addPseudoClassType): Any :not() of a selector is handled through a simple selector list. Cases like :not(foo, bar) simply generate not([fragmentFoo, bragmentBar]). Old cases like :not(foo):not(bar) simply add those cases to the selector list, generating not([fragmentFoo, bragmentBar]). (WebCore::SelectorCompiler::minimumRegisterRequirements): Register pressure is now tracked through computeBacktrackingMemoryRequirements. (WebCore::SelectorCompiler::hasAnyCombinators): (WebCore::SelectorCompiler::computeBacktrackingMemoryRequirements): (WebCore::SelectorCompiler::computeBacktrackingInformation): Abstract the code creating Selector Lists from :nth-child(of). Use that for :not() and :nth-child(of). (WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatchesNotPseudoClass): git-svn-id: https://svn.webkit.org/repository/webkit/trunk@174914 268f45cc-cd09-0410-ab3c-d52691b4dbfc --- Source/WebCore/ChangeLog | 33 ++++++++ Source/WebCore/cssjit/SelectorCompiler.cpp | 117 ++++++++++++++++------------- 2 files changed, 97 insertions(+), 53 deletions(-) diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog index d343161..e2b5f82 100644 --- a/Source/WebCore/ChangeLog +++ b/Source/WebCore/ChangeLog @@ -1,3 +1,36 @@ +2014-10-20 Benjamin Poulain + + Generalize the compilation of :not() to support arbitrary selector lists + https://bugs.webkit.org/show_bug.cgi?id=137843 + + Reviewed by Andreas Kling. + + This builds :not() on top of the code created for :nth-child(An+B of selectorList) + to support any selector list. + + The tests for the JIT were added previously: + -not-boundaries.html + -not-backtracking.html + + * cssjit/SelectorCompiler.cpp: + (WebCore::SelectorCompiler::addPseudoClassType): + Any :not() of a selector is handled through a simple selector list. Cases like + :not(foo, bar) simply generate not([fragmentFoo, bragmentBar]). + + Old cases like :not(foo):not(bar) simply add those cases to the selector list, + generating not([fragmentFoo, bragmentBar]). + + (WebCore::SelectorCompiler::minimumRegisterRequirements): + Register pressure is now tracked through computeBacktrackingMemoryRequirements. + + (WebCore::SelectorCompiler::hasAnyCombinators): + (WebCore::SelectorCompiler::computeBacktrackingMemoryRequirements): + (WebCore::SelectorCompiler::computeBacktrackingInformation): + Abstract the code creating Selector Lists from :nth-child(of). Use that for :not() + and :nth-child(of). + + (WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatchesNotPseudoClass): + 2014-10-20 Gyuyoung Kim Use std::unique_ptr<>|make_unique<> in PluginView::scheduleRequest() diff --git a/Source/WebCore/cssjit/SelectorCompiler.cpp b/Source/WebCore/cssjit/SelectorCompiler.cpp index aee3723..bc88707 100755 --- a/Source/WebCore/cssjit/SelectorCompiler.cpp +++ b/Source/WebCore/cssjit/SelectorCompiler.cpp @@ -195,7 +195,7 @@ struct SelectorFragment { Vector attributes; Vector, 2> nthChildFilters; Vector nthChildOfFilters; - Vector notFilters; + SelectorList notFilters; Vector> anyFilters; const CSSSelector* pseudoElementSelector; @@ -661,33 +661,28 @@ static inline FunctionType addPseudoClassType(const CSSSelector& selector, Selec { const CSSSelectorList* selectorList = selector.selectorList(); + ASSERT_WITH_MESSAGE(selectorList, "The CSS Parser should never produce valid :not() CSSSelector with an empty selectorList."); if (!selectorList) return FunctionType::CannotMatchAnything; -#if ENABLE(CSS_SELECTORS_LEVEL4) - if (selectorList->first()->tagHistory() || CSSSelectorList::next(selectorList->first())) - return FunctionType::CannotCompile; -#endif - - SelectorFragmentList notFragments; - VisitedMode ignoreVisitedMode = VisitedMode::None; - FunctionType functionType = constructFragments(selectorList->first(), selectorContext, notFragments, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments, visitedMatchEnabled, ignoreVisitedMode); - ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes"); - - // Since this is not pseudo class filter, CannotMatchAnything implies this filter always passes. - if (functionType == FunctionType::CannotMatchAnything) - return FunctionType::SimpleSelectorChecker; + FunctionType functionType = FunctionType::SimpleSelectorChecker; + for (const CSSSelector* subselector = selectorList->first(); subselector; subselector = CSSSelectorList::next(subselector)) { + SelectorFragmentList selectorFragments; + VisitedMode ignoreVisitedMode = VisitedMode::None; + FunctionType localFunctionType = constructFragments(subselector, selectorContext, selectorFragments, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments, visitedMatchEnabled, ignoreVisitedMode); + ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes"); - if (functionType == FunctionType::CannotCompile) - return functionType; + // Since this is not pseudo class filter, CannotMatchAnything implies this filter always passes. + if (localFunctionType == FunctionType::CannotMatchAnything) + continue; - ASSERT(notFragments.size() == 1); - if (notFragments.size() != 1) - return FunctionType::CannotCompile; + if (localFunctionType == FunctionType::CannotCompile) + return FunctionType::CannotCompile; - const SelectorFragment& subFragment = notFragments.first(); + functionType = std::max(functionType, localFunctionType); + fragment.notFilters.append(selectorFragments); + } - fragment.notFilters.append(subFragment); return functionType; } @@ -982,12 +977,6 @@ static unsigned minimumRegisterRequirements(const SelectorFragment& selectorFrag minimum = std::max(minimum, minimumRequiredRegisterCountForNthChildFilter); #endif - // :not pseudo class filters cause some register pressure. - for (const SelectorFragment& subFragment : selectorFragment.notFilters) { - unsigned notFilterMinimum = minimumRegisterRequirements(subFragment); - minimum = std::max(minimum, notFilterMinimum); - } - // :any pseudo class filters cause some register pressure. for (const auto& subFragments : selectorFragment.anyFilters) { for (const SelectorFragment& subFragment : subFragments) { @@ -1019,6 +1008,8 @@ bool hasAnyCombinators(const Vector& selectorF return false; if (selectorFragmentList.size() != 1) return true; + if (hasAnyCombinators(selectorFragmentList.first().notFilters)) + return true; for (const NthChildOfSelectorInfo& nthChildOfSelectorInfo : selectorFragmentList.first().nthChildOfFilters) { if (hasAnyCombinators(nthChildOfSelectorInfo.selectorList)) return true; @@ -1029,7 +1020,31 @@ bool hasAnyCombinators(const Vector& selectorF // The CSS JIT has only been validated with a strict minimum of 6 allocated registers. const unsigned minimumRegisterRequirement = 6; -static void computeBacktrackingMemoryRequirements(SelectorFragmentList& selectorFragments, bool backtrackingRegisterReserved = false) +void computeBacktrackingMemoryRequirements(SelectorFragmentList& selectorFragments, bool backtrackingRegisterReserved = false); + +static void computeBacktrackingMemoryRequirements(SelectorList& selectorList, unsigned& totalRegisterRequirements, unsigned& totalStackRequirements, bool backtrackingRegisterReservedForFragment = false) +{ + unsigned selectorListRegisterRequirements = 0; + unsigned selectorListStackRequirements = 0; + bool clobberElementAddressRegister = false; + + for (SelectorFragmentList& selectorFragmentList : selectorList) { + computeBacktrackingMemoryRequirements(selectorFragmentList, backtrackingRegisterReservedForFragment); + + selectorListRegisterRequirements = std::max(selectorListRegisterRequirements, selectorFragmentList.registerRequirements); + selectorListStackRequirements = std::max(selectorListStackRequirements, selectorFragmentList.stackRequirements); + clobberElementAddressRegister = clobberElementAddressRegister || selectorFragmentList.clobberElementAddressRegister; + } + + totalRegisterRequirements = std::max(totalRegisterRequirements, selectorListRegisterRequirements); + totalStackRequirements = std::max(totalStackRequirements, selectorListStackRequirements); + + selectorList.registerRequirements = std::max(selectorListRegisterRequirements, minimumRegisterRequirement); + selectorList.stackRequirements = selectorListStackRequirements; + selectorList.clobberElementAddressRegister = clobberElementAddressRegister; +} + +void computeBacktrackingMemoryRequirements(SelectorFragmentList& selectorFragments, bool backtrackingRegisterReserved) { selectorFragments.registerRequirements = minimumRegisterRequirement; selectorFragments.stackRequirements = 0; @@ -1039,26 +1054,12 @@ static void computeBacktrackingMemoryRequirements(SelectorFragmentList& selector unsigned fragmentRegisterRequirements = minimumRegisterRequirements(selectorFragment); unsigned fragmentStackRequirements = 0; - if (!selectorFragment.nthChildOfFilters.isEmpty()) { - bool backtrackingRegisterReservedForFragment = backtrackingRegisterReserved || selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail; + bool backtrackingRegisterReservedForFragment = backtrackingRegisterReserved || selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail; - for (NthChildOfSelectorInfo& nthChildOfSelectorInfo : selectorFragment.nthChildOfFilters) { - unsigned nthChildOfSelectorInfoRegisterRequirements = minimumRegisterRequirement; - bool clobberElementAddressRegister = false; + computeBacktrackingMemoryRequirements(selectorFragment.notFilters, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment); - for (SelectorFragmentList& nestedSelectorFragmentList : nthChildOfSelectorInfo.selectorList) { - computeBacktrackingMemoryRequirements(nestedSelectorFragmentList, backtrackingRegisterReservedForFragment); - - nthChildOfSelectorInfoRegisterRequirements = std::max(nthChildOfSelectorInfoRegisterRequirements, nestedSelectorFragmentList.registerRequirements); - clobberElementAddressRegister = clobberElementAddressRegister || nestedSelectorFragmentList.clobberElementAddressRegister; - - fragmentStackRequirements = std::max(fragmentStackRequirements, nestedSelectorFragmentList.stackRequirements); - } - fragmentRegisterRequirements = std::max(fragmentRegisterRequirements, nthChildOfSelectorInfoRegisterRequirements); - nthChildOfSelectorInfo.selectorList.registerRequirements = nthChildOfSelectorInfoRegisterRequirements; - nthChildOfSelectorInfo.selectorList.clobberElementAddressRegister = clobberElementAddressRegister; - } - } + for (NthChildOfSelectorInfo& nthChildOfSelectorInfo : selectorFragment.nthChildOfFilters) + computeBacktrackingMemoryRequirements(nthChildOfSelectorInfo.selectorList, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment); if (selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail) { if (!backtrackingRegisterReserved) @@ -1470,6 +1471,18 @@ void computeBacktrackingInformation(SelectorFragmentList& selectorFragments, uns } for (SelectorFragment& fragment : selectorFragments) { + if (!fragment.notFilters.isEmpty()) { +#if CSS_SELECTOR_JIT_DEBUGGING + dataLogF(" "); + dataLogF("Subselectors for :not():\n"); +#endif + + for (SelectorFragmentList& selectorList : fragment.notFilters) + computeBacktrackingInformation(selectorList, level + 1); + } + } + + for (SelectorFragment& fragment : selectorFragments) { for (NthChildOfSelectorInfo& nthChildOfSelectorInfo : fragment.nthChildOfFilters) { #if CSS_SELECTOR_JIT_DEBUGGING for (unsigned i = level; i; --i) @@ -3453,13 +3466,11 @@ void SelectorCodeGenerator::generateElementIsNthChildOf(Assembler::JumpList& fai void SelectorCodeGenerator::generateElementMatchesNotPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment& fragment) { - for (const auto& subFragment : fragment.notFilters) { - Assembler::JumpList localFailureCases; - generateElementMatching(localFailureCases, localFailureCases, subFragment); - // Since this is a not pseudo class filter, reaching here is a failure. - failureCases.append(m_assembler.jump()); - localFailureCases.link(&m_assembler); - } + Assembler::JumpList localFailureCases; + generateElementMatchesSelectorList(localFailureCases, elementAddressRegister, fragment.notFilters); + // Since this is a not pseudo class filter, reaching here is a failure. + failureCases.append(m_assembler.jump()); + localFailureCases.link(&m_assembler); } void SelectorCodeGenerator::generateElementMatchesAnyPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment& fragment) -- 1.8.3.1