Changeset 287091 in webkit


Ignore:
Timestamp:
Dec 15, 2021 11:45:12 AM (7 months ago)
Author:
Antti Koivisto
Message:

[:has() pseudo-class] Use Bloom filter to quickly reject :has() selectors
​https://bugs.webkit.org/show_bug.cgi?id=234341

Reviewed by Dean Jackson.

We can dramatically speed up cases where there are many :has rules, most of which don't match their argument
by building a Bloom filter describing the features of the subtree.

  • Sources.txt:
  • WebCore.xcodeproj/project.pbxproj:
  • css/SelectorChecker.cpp:

(WebCore::SelectorChecker::matchHasPseudoClass const):

Build and cache HasSelectorFilter per element/filter type. It will be constructed only if multiple :has()
selectors are tested for the same element (otherwise the regular match cache is more efficient).
Use it to quickly reject selectors.
Also add a basic inital optimization to bail out if there are no child/sibling elements that could match.

  • css/SelectorFilter.cpp:

(WebCore::SelectorFilter::collectElementIdentifierHashes):
(WebCore::SelectorFilter::collectSimpleSelectorHash):
(WebCore::SelectorFilter::collectSelectorHashes):
(WebCore::SelectorFilter::chooseSelectorHashesForFilter):
(WebCore::collectElementIdentifierHashes): Deleted.
(WebCore::collectSimpleSelectorHash): Deleted.
(WebCore::collectSelectorHashes): Deleted.
(WebCore::chooseSelectorHashesForFilter): Deleted.

  • css/SelectorFilter.h:
  • style/HasSelectorFilter.cpp: Added.

(WebCore::Style::HasSelectorFilter::HasSelectorFilter):
(WebCore::Style::HasSelectorFilter::typeForMatchElement):
(WebCore::Style::HasSelectorFilter::makeKey):

The key consists of the most specific string in the rightmost compound of the selector along with
:hover pseudo class, if any.

(WebCore::Style::HasSelectorFilter::add):

Add an Element to the filter.
The features collected are the same as for the regular selector filter, plus permutations with
:hover pseudo-class if it would match.

  • style/HasSelectorFilter.h: Copied from Source/WebCore/style/SelectorMatchingState.h.

(WebCore::Style::HasSelectorFilter::type const):
(WebCore::Style::HasSelectorFilter::reject const):

Add HasSelectorFilter which uses non-counting BloomFilter internally. The size of the filter is 512 bytes.

  • style/SelectorMatchingState.h:

(WebCore::Style::makeHasPseudoClassSelectorFilterKey):

Location:
trunk/Source/WebCore
Files:
1 added
7 edited
1 copied

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r287089 r287091  
     12021-12-15  Antti Koivisto  <antti@apple.com>
     2
     3        [:has() pseudo-class] Use Bloom filter to quickly reject :has() selectors
     4        https://bugs.webkit.org/show_bug.cgi?id=234341
     5
     6        Reviewed by Dean Jackson.
     7
     8        We can dramatically speed up cases where there are many :has rules, most of which don't match their argument
     9        by building a Bloom filter describing the features of the subtree.
     10
     11        * Sources.txt:
     12        * WebCore.xcodeproj/project.pbxproj:
     13        * css/SelectorChecker.cpp:
     14        (WebCore::SelectorChecker::matchHasPseudoClass const):
     15
     16        Build and cache HasSelectorFilter per element/filter type. It will be constructed only if multiple :has()
     17        selectors are tested for the same element (otherwise the regular match cache is more efficient).
     18        Use it to quickly reject selectors.
     19        Also add a basic inital optimization to bail out if there are no child/sibling elements that could match.
     20
     21        * css/SelectorFilter.cpp:
     22        (WebCore::SelectorFilter::collectElementIdentifierHashes):
     23        (WebCore::SelectorFilter::collectSimpleSelectorHash):
     24        (WebCore::SelectorFilter::collectSelectorHashes):
     25        (WebCore::SelectorFilter::chooseSelectorHashesForFilter):
     26        (WebCore::collectElementIdentifierHashes): Deleted.
     27        (WebCore::collectSimpleSelectorHash): Deleted.
     28        (WebCore::collectSelectorHashes): Deleted.
     29        (WebCore::chooseSelectorHashesForFilter): Deleted.
     30        * css/SelectorFilter.h:
     31        * style/HasSelectorFilter.cpp: Added.
     32        (WebCore::Style::HasSelectorFilter::HasSelectorFilter):
     33        (WebCore::Style::HasSelectorFilter::typeForMatchElement):
     34        (WebCore::Style::HasSelectorFilter::makeKey):
     35
     36        The key consists of the most specific string in the rightmost compound of the selector along with
     37        :hover pseudo class, if any.
     38
     39        (WebCore::Style::HasSelectorFilter::add):
     40
     41        Add an Element to the filter.
     42        The features collected are the same as for the regular selector filter, plus permutations with
     43        :hover pseudo-class if it would match.
     44
     45        * style/HasSelectorFilter.h: Copied from Source/WebCore/style/SelectorMatchingState.h.
     46        (WebCore::Style::HasSelectorFilter::type const):
     47        (WebCore::Style::HasSelectorFilter::reject const):
     48
     49        Add HasSelectorFilter which uses non-counting BloomFilter internally. The size of the filter is 512 bytes.
     50
     51        * style/SelectorMatchingState.h:
     52        (WebCore::Style::makeHasPseudoClassSelectorFilterKey):
     53
    1542021-12-15  Alexey Shvayka  <ashvayka@apple.com>
    255

  • trunk/Source/WebCore/Sources.txt

    r287015 r287091  
    25442544style/ClassChangeInvalidation.cpp
    25452545style/ElementRuleCollector.cpp
     2546style/HasSelectorFilter.cpp
    25462547style/IdChangeInvalidation.cpp
    25472548style/InlineTextBoxStyle.cpp

  • trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj

    r287079 r287091  
    53855385                E4E8B4F5216B956500B8834D /* FontCascadeDescription.h in Headers */ = {isa = PBXBuildFile; fileRef = E4E8B4F2216B8B6000B8834D /* FontCascadeDescription.h */; settings = {ATTRIBUTES = (Private, ); }; };
    53865386                E4E94D6122FF158A00DD191F /* LegacyLineLayout.h in Headers */ = {isa = PBXBuildFile; fileRef = E4A1AC7822FAFD500017B75B /* LegacyLineLayout.h */; settings = {ATTRIBUTES = (Private, ); }; };
     5387                E4ED3ECC2768A51D00F17AC8 /* HasSelectorFilter.h in Headers */ = {isa = PBXBuildFile; fileRef = E4ED3ECA2768A51C00F17AC8 /* HasSelectorFilter.h */; };
    53875388                E4F0BE3125712F6E009E7431 /* CaretRectComputation.h in Headers */ = {isa = PBXBuildFile; fileRef = E4F0BE2E25710A75009E7431 /* CaretRectComputation.h */; };
    53885389                E4F38D1B2626F13B007B1064 /* DefaultResourceLoadPriority.h in Headers */ = {isa = PBXBuildFile; fileRef = E4F38D192626F13B007B1064 /* DefaultResourceLoadPriority.h */; };
    … …  
    1746717468                E4E8B4F0216B8B5F00B8834D /* FontCascadeDescription.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FontCascadeDescription.cpp; sourceTree = "<group>"; };
    1746817469                E4E8B4F2216B8B6000B8834D /* FontCascadeDescription.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FontCascadeDescription.h; sourceTree = "<group>"; };
     17470                E4ED3ECA2768A51C00F17AC8 /* HasSelectorFilter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HasSelectorFilter.h; sourceTree = "<group>"; };
     17471                E4ED3ECD2768A68800F17AC8 /* HasSelectorFilter.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = HasSelectorFilter.cpp; sourceTree = "<group>"; };
    1746917472                E4F0BE2E25710A75009E7431 /* CaretRectComputation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CaretRectComputation.h; sourceTree = "<group>"; };
    1747017473                E4F0BE3025710A76009E7431 /* CaretRectComputation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CaretRectComputation.cpp; sourceTree = "<group>"; };
    … …  
    3108131084                                FBDB619A16D6032A00BB3394 /* ElementRuleCollector.cpp */,
    3108231085                                FBDB619E16D6036500BB3394 /* ElementRuleCollector.h */,
     31086                                E4ED3ECD2768A68800F17AC8 /* HasSelectorFilter.cpp */,
     31087                                E4ED3ECA2768A51C00F17AC8 /* HasSelectorFilter.h */,
    3108331088                                E4A814DD1C7338D100BF85AC /* IdChangeInvalidation.cpp */,
    3108431089                                E4A814DF1C7338EB00BF85AC /* IdChangeInvalidation.h */,
    … …  
    3447434479                                8482B7461198C35400BFB005 /* HashChangeEvent.h in Headers */,
    3447534480                                A8748BE012CBF2DC001FBA41 /* HashTools.h in Headers */,
     34481                                E4ED3ECC2768A51D00F17AC8 /* HasSelectorFilter.h in Headers */,
    3447634482                                CD3EEF3D25799FB5006563BB /* HdrMetadataType.h in Headers */,
    3447734483                                CDA595932146DEC300A84185 /* HEVCUtilities.h in Headers */,

  • trunk/Source/WebCore/css/SelectorChecker.cpp

    r286494 r287091  
    12501250bool SelectorChecker::matchHasPseudoClass(CheckingContext& checkingContext, const Element& element, const CSSSelector& hasSelector) const
    12511251{
     1252    auto matchElement = Style::computeHasPseudoClassMatchElement(hasSelector);
     1253
     1254    auto canMatch = [&] {
     1255        switch (matchElement) {
     1256        case Style::MatchElement::HasChild:
     1257        case Style::MatchElement::HasDescendant:
     1258            return !!element.firstElementChild();
     1259        case Style::MatchElement::HasSibling:
     1260        case Style::MatchElement::HasSiblingDescendant:
     1261            return !!element.nextElementSibling();
     1262        default:
     1263            return true;
     1264        };
     1265    };
     1266
     1267    // See if there are any elements that this :has() selector could match.
     1268    if (!canMatch())
     1269        return false;
     1270
    12521271    auto* cache = checkingContext.selectorMatchingState ? &checkingContext.selectorMatchingState->hasPseudoClassMatchCache : nullptr;
    12531272
    1254     Style::HasPseudoClassMatch* cachedMatch = nullptr;
    1255     if (cache) {
    1256         cachedMatch = &cache->add(Style::makeHasPseudoClassCacheKey(hasSelector, element), Style::HasPseudoClassMatch::None).iterator->value;
    1257         switch (*cachedMatch) {
     1273    auto checkForCachedMatch = [&]() -> std::optional<bool> {
     1274        if (!cache)
     1275            return { };
     1276        switch (cache->get(Style::makeHasPseudoClassCacheKey(element, hasSelector))) {
    12581277        case Style::HasPseudoClassMatch::Matches:
    12591278            return true;
    … …  
    12641283            break;
    12651284        }
     1285        return { };
     1286    };
     1287
     1288    // See if we know the result already.
     1289    if (auto match = checkForCachedMatch())
     1290        return *match;
     1291
     1292    auto filterForElement = [&]() -> Style::HasSelectorFilter* {
     1293        if (!checkingContext.selectorMatchingState)
     1294            return nullptr;
     1295        auto type = Style::HasSelectorFilter::typeForMatchElement(matchElement);
     1296        if (!type)
     1297            return nullptr;
     1298        auto& filtersMap = checkingContext.selectorMatchingState->hasPseudoClassSelectorFilters;
     1299        auto addResult = filtersMap.add(Style::makeHasPseudoClassFilterKey(element, *type), std::unique_ptr<Style::HasSelectorFilter>());
     1300        // Only build a filter if the same element gets checked second time with a different selector (misses the match cache).
     1301        if (addResult.isNewEntry)
     1302            return nullptr;
     1303
     1304        if (!addResult.iterator->value)
     1305            addResult.iterator->value = makeUnique<Style::HasSelectorFilter>(element, *type);
     1306        return addResult.iterator->value.get();
     1307    };
     1308
     1309    // Check if the bloom filter rejects this selector
     1310    if (auto* filter = filterForElement()) {
     1311        if (filter->reject(hasSelector))
     1312            return false;
    12661313    }
    12671314
    … …  
    12841331        for (auto it = descendantsOfType<Element>(descendantRoot).begin(); it;) {
    12851332            auto& descendant = *it;
    1286             if (cache) {
    1287                 auto key = Style::makeHasPseudoClassCacheKey(hasSelector, descendant);
     1333            if (cache && descendant.firstElementChild()) {
     1334                auto key = Style::makeHasPseudoClassCacheKey(descendant, hasSelector);
    12881335                if (cache->get(key) == Style::HasPseudoClassMatch::FailsSubtree) {
    12891336                    it.traverseNextSkippingChildren();
    … …  
    13011348
    13021349    auto match = [&] {
    1303         auto matchElement = Style::computeHasPseudoClassMatchElement(hasSelector);
    1304 
    13051350        switch (matchElement) {
    13061351        // :has(> .child)
    … …  
    13131358        // :has(.descendant)
    13141359        case Style::MatchElement::HasDescendant: {
    1315             if (!element.firstElementChild())
    1316                 return false;
    13171360            if (cache) {
    13181361                // See if we already know this descendant selector doesn't match in this subtree.
    13191362                for (auto* ancestor = element.parentElement(); ancestor; ancestor = ancestor->parentElement()) {
    1320                     auto key = Style::makeHasPseudoClassCacheKey(hasSelector, *ancestor);
     1363                    auto key = Style::makeHasPseudoClassCacheKey(*ancestor, hasSelector);
    13211364                    if (cache->get(key) == Style::HasPseudoClassMatch::FailsSubtree)
    13221365                        return false;
    … …  
    13251368            if (checkDescendants(element))
    13261369                return true;
     1370
    13271371            break;
    13281372        }
    … …  
    13551399    auto result = match();
    13561400
    1357     if (cachedMatch) {
    1358         *cachedMatch = [&] {
    1359             if (result)
    1360                 return Style::HasPseudoClassMatch::Matches;
    1361             if (matchedInsideScope)
    1362                 return Style::HasPseudoClassMatch::Fails;
    1363             return Style::HasPseudoClassMatch::FailsSubtree;
    1364         }();
    1365     }
     1401    auto matchTypeForCache = [&] {
     1402        if (result)
     1403            return Style::HasPseudoClassMatch::Matches;
     1404        if (matchedInsideScope)
     1405            return Style::HasPseudoClassMatch::Fails;
     1406        return Style::HasPseudoClassMatch::FailsSubtree;
     1407    };
     1408
     1409    if (cache)
     1410        cache->add(Style::makeHasPseudoClassCacheKey(element, hasSelector), matchTypeForCache());
    13661411
    13671412    return result;

  • trunk/Source/WebCore/css/SelectorFilter.cpp

    r285195 r287091  
    4646}
    4747
    48 static inline void collectElementIdentifierHashes(const Element& element, Vector<unsigned, 4>& identifierHashes)
     48void SelectorFilter::collectElementIdentifierHashes(const Element& element, Vector<unsigned, 4>& identifierHashes)
    4949{
    5050    AtomString tagLowercaseLocalName = element.localName().convertToASCIILowercase();
    … …  
    135135}
    136136
    137 struct CollectedSelectorHashes {
    138     using HashVector = Vector<unsigned, 8>;
    139     HashVector ids;
    140     HashVector classes;
    141     HashVector tags;
    142     HashVector attributes;
    143 };
    144 
    145 static inline void collectSimpleSelectorHash(CollectedSelectorHashes& collectedHashes, const CSSSelector& selector)
     137void SelectorFilter::collectSimpleSelectorHash(CollectedSelectorHashes& collectedHashes, const CSSSelector& selector)
    146138{
    147139    switch (selector.match()) {
    … …  
    177169}
    178170
    179 static CollectedSelectorHashes collectSelectorHashes(const CSSSelector& rightmostSelector)
     171auto SelectorFilter::collectSelectorHashes(const CSSSelector& rightmostSelector) -> CollectedSelectorHashes
    180172{
    181173    CollectedSelectorHashes collectedHashes;
    … …  
    211203}
    212204
    213 static SelectorFilter::Hashes chooseSelectorHashesForFilter(const CollectedSelectorHashes& collectedSelectorHashes)
    214 {
    215     SelectorFilter::Hashes resultHashes;
     205auto SelectorFilter::chooseSelectorHashesForFilter(const CollectedSelectorHashes& collectedSelectorHashes) -> Hashes
     206{
     207    Hashes resultHashes;
    216208    unsigned index = 0;
    217209

  • trunk/Source/WebCore/css/SelectorFilter.h

    r228729 r287091  
    5151    static Hashes collectHashes(const CSSSelector&);
    5252
     53    static void collectElementIdentifierHashes(const Element&, Vector<unsigned, 4>&);
     54
     55    struct CollectedSelectorHashes {
     56        using HashVector = Vector<unsigned, 8>;
     57        HashVector ids;
     58        HashVector classes;
     59        HashVector tags;
     60        HashVector attributes;
     61    };
     62    static void collectSimpleSelectorHash(CollectedSelectorHashes&, const CSSSelector&);
     63
    5364private:
    5465    void initializeParentStack(Element& parent);
     66    static CollectedSelectorHashes collectSelectorHashes(const CSSSelector& rightmostSelector);
     67    static Hashes chooseSelectorHashesForFilter(const CollectedSelectorHashes&);
    5568
    5669    struct ParentStackFrame {

  • trunk/Source/WebCore/style/HasSelectorFilter.h

    r287090 r287091  
    2525#pragma once
    2626
    27 #include "SelectorFilter.h"
    28 #include <wtf/HashMap.h>
     27#include "CSSSelector.h"
     28#include <wtf/BloomFilter.h>
    2929
    30 namespace WebCore::Style {
     30namespace WebCore {
     31namespace Style {
    3132
    32 using HasPseudoClassCacheKey = std::pair<const CSSSelector*, const Element*>;
     33enum class MatchElement : uint8_t;
    3334
    34 enum class HasPseudoClassMatch : uint8_t { None, Matches, Fails, FailsSubtree };
     35class HasSelectorFilter {
     36    WTF_MAKE_FAST_ALLOCATED;
     37public:
     38    enum class Type : uint8_t { Children, Descendants };
     39    HasSelectorFilter(const Element&, Type);
    3540
    36 struct SelectorMatchingState {
    37     SelectorFilter selectorFilter;
    38     HashMap<HasPseudoClassCacheKey, HasPseudoClassMatch> hasPseudoClassMatchCache;
     41    Type type() const { return m_type; }
     42    static std::optional<Type> typeForMatchElement(MatchElement);
     43
     44    using Key = unsigned;
     45    static Key makeKey(const CSSSelector& hasSelector);
     46
     47    bool reject(const CSSSelector& hasSelector) const { return reject(makeKey(hasSelector)); }
     48    bool reject(Key key) const { return !m_filter.mayContain(key); }
     49
     50
     51private:
     52    void add(const Element&);
     53
     54    const Type m_type;
     55    BloomFilter<12> m_filter;
    3956};
    4057
    41 inline HasPseudoClassCacheKey makeHasPseudoClassCacheKey(const CSSSelector& selector, const Element& element)
    42 {
    43     return { &selector, &element };
    4458}
    45 
    4659}

  • trunk/Source/WebCore/style/SelectorMatchingState.h

    r286494 r287091  
    2525#pragma once
    2626
     27#include "HasSelectorFilter.h"
    2728#include "SelectorFilter.h"
    2829#include <wtf/HashMap.h>
    … …  
    3031namespace WebCore::Style {
    3132
    32 using HasPseudoClassCacheKey = std::pair<const CSSSelector*, const Element*>;
     33using HasPseudoClassCacheKey = std::pair<const Element*, const CSSSelector*>;
     34using HasPseudoClassFilterKey = std::pair<const Element*, uint8_t>;
    3335
    3436enum class HasPseudoClassMatch : uint8_t { None, Matches, Fails, FailsSubtree };
    … …  
    3638struct SelectorMatchingState {
    3739    SelectorFilter selectorFilter;
     40
    3841    HashMap<HasPseudoClassCacheKey, HasPseudoClassMatch> hasPseudoClassMatchCache;
     42    HashMap<HasPseudoClassFilterKey, std::unique_ptr<HasSelectorFilter>> hasPseudoClassSelectorFilters;
    3943};
    4044
    41 inline HasPseudoClassCacheKey makeHasPseudoClassCacheKey(const CSSSelector& selector, const Element& element)
     45inline HasPseudoClassCacheKey makeHasPseudoClassCacheKey(const Element& element, const CSSSelector& selector)
    4246{
    43     return { &selector, &element };
     47    return { &element, &selector };
     48}
     49
     50inline HasPseudoClassFilterKey makeHasPseudoClassFilterKey(const Element& element, HasSelectorFilter::Type type)
     51{
     52    return { &element, static_cast<uint8_t>(type) };
    4453}
    4554
Note: See TracChangeset for help on using the changeset viewer.