Bug 68633 – Optimize matching of common pseudo classes

• Status: RESOLVED
• Resolution: FIXED
• Component: CSS

[Antti Koivisto]

:link, :visited and :focus are quite common. They often used as univeral selectors (including in our default stylesheet) so we try to match them for all elements in the document. They take always the slow matching path. In addition we match link styles twice due to visited link pseudo style generation so the overhead is doubled. As a result substantial portion of our style matching time is spend dealing with these pseudo classes. We should optimize the common cases.

[Antti Koivisto]

Created attachment 108379 [details]
patch

[WebKit Review Bot]

Attachment 108379 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/ChangeLog', u'Source/WebCor..." exit_code: 1

Source/WebCore/css/SelectorChecker.h:84:  The parameter name "selector" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/WebCore/css/SelectorChecker.h:85:  The parameter name "element" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/WebCore/css/SelectorChecker.h:85:  The parameter name "selector" adds no information, so it should be removed.  [readability/parameter_name] [5]
Total errors found: 3 in 5 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Dave Hyatt]

Comment on attachment 108379 [details]
patch

r=me. Fix the style errors though.

[Darin Adler]

Comment on attachment 108379 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=108379&action=review

The optimization here looks great. r=me as is (but I see Hyatt beat me to it). I have comments, but they are all optional ideas for possible improvement.

> Source/WebCore/ChangeLog:14
> +        This patch adds a new list to RuleSet for common pseude class rules. Selectors with the rightmost component of 

Typo: pseude

> Source/WebCore/css/CSSStyleSelector.cpp:237
>      const Vector<RuleData>* getIDRules(AtomicStringImpl* key) const { return m_idRules.get(key); }
>      const Vector<RuleData>* getClassRules(AtomicStringImpl* key) const { return m_classRules.get(key); }
>      const Vector<RuleData>* getTagRules(AtomicStringImpl* key) const { return m_tagRules.get(key); }
> -    const Vector<RuleData>* getPseudoRules(AtomicStringImpl* key) const { return m_pseudoRules.get(key); }
> +    const Vector<RuleData>* getShadowPseudoRules(AtomicStringImpl* key) const { return m_shadowPseudoRules.get(key); }
> +    const Vector<RuleData>* getCommonPseudoClassRules() const { return &m_commonPseudoClassRules; }
>      const Vector<RuleData>* getUniversalRules() const { return &m_universalRules; }
>      const Vector<RuleData>* getPageRules() const { return &m_pageRules; }

I’m getting increasingly annoyed that all of these functions use “get” in a way that does not match usual WebKit naming style.

> Source/WebCore/css/CSSStyleSelector.cpp:529
> +namespace {
> +inline bool fastReject(SelectorChecker& checker, bool canUseFastRejectSelector, const Element*, const RuleData& ruleData)
> +{ 
> +    if (!canUseFastRejectSelector)
> +        return false;
> +    return checker.fastRejectSelector<RuleData::maximumIdentifierCount>(ruleData.descendantSelectorIdentifierHashes());
> +}
> +inline bool pseudoClassReject(SelectorChecker& checker, bool canUseFastRejectSelector, const Element* element, const RuleData& ruleData)
> +{ 
> +    if (!checker.commonPseudoClassSelectorMatches(element, ruleData.selector()))
> +        return true;
> +    return fastReject(checker, canUseFastRejectSelector, element, ruleData);
> +}
> +}

While we can use an anonymous namespace to get internal linkage, normally we just use “static” to do that instead. Or maybe that doesn’t work because of the use of these functions as template arguments?

> Source/WebCore/css/CSSStyleSelector.cpp:556
> +        const Vector<RuleData>* commonPseudoClassRules = rules->getCommonPseudoClassRules();
> +        matchRulesForList<pseudoClassReject>(commonPseudoClassRules, firstRuleIndex, lastRuleIndex, includeEmptyRules);

Not sure the local variable makes this easier to read.

> Source/WebCore/css/SelectorChecker.cpp:378
> +    bool first = true;

I would call this onFirstSelector or something like that. The name first doesn’t make it clear it’s a boolean.

> Source/WebCore/css/SelectorChecker.cpp:386
>      for (; selector; selector = selector->tagHistory()) {
>          if (selector->relation() != CSSSelector::Descendant && selector->relation() != CSSSelector::Child && selector->relation() != CSSSelector::SubSelector)
>              return false;
> +        if (first) {
> +            first = false;
> +            if (isCommonPseudoClassSelector(selector))
> +                continue;
> +        }

Should we unroll the loop a little just to make the loop structure less confusing? It would make it possible to get rid of the boolean. I think that if the relation check and match checks were named inline helper functions it would be easy to unroll a bit and keep the code looking great.

> Source/WebCore/css/SelectorChecker.cpp:1308
> +bool SelectorChecker::commonPseudoClassSelectorMatches(const Element* element, const CSSSelector* selector) const

Is there code we could make this share with? It seems unpleasant to have those forcePseudoState calls in multiple places.

Is there a good reason the Element* is const? I think using const* for elements usually just gets in the way and makes for wordier code.

> Source/WebCore/css/SelectorChecker.cpp:1315
> +        return element->isLink() && (m_isMatchingVisitedPseudoClass || InspectorInstrumentation::forcePseudoState(const_cast<Element*>(element), CSSSelector::PseudoVisited));

Wow, that forcePseudoState thing is strange!

> Source/WebCore/css/SelectorChecker.cpp:1319
> +        return (element->focused() && element->document()->frame() && element->document()->frame()->selection()->isFocusedAndActive()) 

Seems like this expression should be in a helper function taking an element pointer, isFocusedInActiveFrame or something like that.

> Source/WebCore/css/SelectorChecker.cpp:1320
> +        || InspectorInstrumentation::forcePseudoState(const_cast<Element*>(element), CSSSelector::PseudoFocus);

This should be indented one more tab stop.

[Antti Koivisto]

(In reply to comment #4)
> I’m getting increasingly annoyed that all of these functions use “get” in a way that does not match usual WebKit naming style.

I'll rename them.

> While we can use an anonymous namespace to get internal linkage, normally we just use “static” to do that instead. Or maybe that doesn’t work because of the use of these functions as template arguments?

Last time I tried static (or anything else than this) it either failed to compile or failed to inline as a template argument.

> Should we unroll the loop a little just to make the loop structure less confusing? It would make it possible to get rid of the boolean. I think that if the relation check and match checks were named inline helper functions it would be easy to unroll a bit and keep the code looking great.

Yeah, it is ugly. I'll unroll.

> Is there code we could make this share with? It seems unpleasant to have those forcePseudoState calls in multiple places.

Maybe.

> Is there a good reason the Element* is const? I think using const* for elements usually just gets in the way and makes for wordier code.

It does verify and communicate that the funcition does not modify the element. It is bit awkward as it is not followed consistently elsewhere.

 
> > Source/WebCore/css/SelectorChecker.cpp:1315
> > +        return element->isLink() && (m_isMatchingVisitedPseudoClass || InspectorInstrumentation::forcePseudoState(const_cast<Element*>(element), CSSSelector::PseudoVisited));
> 
> Wow, that forcePseudoState thing is strange!

It is just copy code from checkOneSelector. I assume it makes some sense. Might deserve an inline function of its own at least.

Thanks for review.

[WebKit Review Bot]

Comment on attachment 108379 [details]
patch

Attachment 108379 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/9811172

New failing tests:
editing/deleting/5483370.html
editing/deleting/delete-after-span-ws-002.html
editing/deleting/delete-3959464-fix.html
editing/deleting/5369009.html
editing/deleting/5144139-2.html
editing/deleting/delete-after-span-ws-003.html
editing/deleting/delete-at-paragraph-boundaries-001.html
editing/deleting/4922367.html
editing/deleting/5272440.html
editing/deleting/5099303.html
editing/deleting/delete-and-undo.html
editing/deleting/delete-3608462-fix.html
editing/deleting/collapse-whitespace-3587601-fix.html
editing/deleting/5206311-1.html
editing/deleting/delete-3608445-fix.html
editing/deleting/delete-after-span-ws-001.html
editing/deleting/delete-at-paragraph-boundaries-002.html
editing/deleting/5433862-2.html
editing/deleting/5126166.html
editing/deleting/delete-4083333-fix.html

[WebKit Review Bot]

Created attachment 108442 [details]
Archive of layout-test-results from ec2-cr-linux-03

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: ec2-cr-linux-03  Port: Chromium  Platform: Linux-2.6.35-28-virtual-x86_64-with-Ubuntu-10.10-maverick

[Antti Koivisto]

Created attachment 108662 [details]
new approach

In the end I wasn't happy with the original patch. Here is an updated patch which takes slightly different approach. This uses separate lists for different pseudo class types instead putting everything to a single list. This both significantly faster (as the rightmost selector won't need any additional checking for match) and cleaner (no need for awkward templating of fastRejectSelector).

The patch also includes a bunch of cleanups as suggested by Darin.

Requesting a new review as the changes are substantial.

[Dimitri Glazkov (Google)]

Comment on attachment 108662 [details]
new approach

View in context: https://bugs.webkit.org/attachment.cgi?id=108662&action=review

This looks great, aside from a couple of boogers:

> Source/WebCore/ChangeLog:199
> +>>>>>>> .r95947

lolwut! :)

> Source/WebCore/css/SelectorChecker.cpp:417
> +//    printf("checkSelector: %s\n", sel->selectorText().latin1().data());

oopsie :)

[Antti Koivisto]

http://trac.webkit.org/changeset/95966