Generalize the compilation of :not() to support arbitrary selector lists
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 21 Oct 2014 00:43:29 +0000 (00:43 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 21 Oct 2014 00:43:29 +0000 (00:43 +0000)
https://bugs.webkit.org/show_bug.cgi?id=137843

Patch by Benjamin Poulain <bpoulain@apple.com> 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
Source/WebCore/cssjit/SelectorCompiler.cpp

index d343161..e2b5f82 100644 (file)
@@ -1,3 +1,36 @@
+2014-10-20  Benjamin Poulain  <bpoulain@apple.com>
+
+        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  <gyuyoung.kim@samsung.com>
 
         Use std::unique_ptr<>|make_unique<> in PluginView::scheduleRequest()
index aee3723..bc88707 100755 (executable)
@@ -195,7 +195,7 @@ struct SelectorFragment {
     Vector<AttributeMatchingInfo, 4> attributes;
     Vector<std::pair<int, int>, 2> nthChildFilters;
     Vector<NthChildOfSelectorInfo> nthChildOfFilters;
-    Vector<SelectorFragment> notFilters;
+    SelectorList notFilters;
     Vector<Vector<SelectorFragment>> 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<SelectorFragment, inlineCapacity>& 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<SelectorFragment, inlineCapacity>& 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)