Changeset 271584 in webkit


Ignore:
Timestamp:
Jan 18, 2021 12:26:24 PM (18 months ago)
Author:
Antti Koivisto
Message:

Optimize :hover/:active style invalidation for deep trees and descendant selectors
​https://bugs.webkit.org/show_bug.cgi?id=220711

Reviewed by Zalan Bujtas.

Hover and active states are flipped for the entire ancestor chain. We compute invalidation for each flipped
element separately. If the selectors are of form ':active .descendant' then each of these invalidations needs
to traverse the whole subtree, leading to O(n2) behavior.

We really only need to traverse the descendants once, starting from the element closest to the root that changes state.

  • dom/Document.cpp:

(WebCore::Document::updateHoverActiveState):

Compute the change root and pass the information to setActive/Hover.
Reorganize the function a bit to allow this, and for general readability.

  • dom/Element.cpp:

(WebCore::Element::setActive):
(WebCore::Element::setHovered):

  • dom/Element.h:
  • html/HTMLAnchorElement.cpp:

(WebCore::HTMLAnchorElement::setActive):

  • html/HTMLAnchorElement.h:
  • html/HTMLLabelElement.cpp:

(WebCore::HTMLLabelElement::setActive):
(WebCore::HTMLLabelElement::setHovered):

  • html/HTMLLabelElement.h:
  • html/shadow/SpinButtonElement.cpp:

(WebCore::SpinButtonElement::setHovered):

  • html/shadow/SpinButtonElement.h:
  • style/PseudoClassChangeInvalidation.cpp:

(WebCore::Style::PseudoClassChangeInvalidation::computeInvalidation):

Only include descendant traversing rulesets for the change root.

  • style/PseudoClassChangeInvalidation.h:

(WebCore::Style::PseudoClassChangeInvalidation::PseudoClassChangeInvalidation):

Location:
trunk/Source/WebCore
Files:
12 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r271583 r271584  
     12021-01-18  Antti Koivisto  <antti@apple.com>
     2
     3        Optimize :hover/:active style invalidation for deep trees and descendant selectors
     4        https://bugs.webkit.org/show_bug.cgi?id=220711
     5
     6        Reviewed by Zalan Bujtas.
     7
     8        Hover and active states are flipped for the entire ancestor chain. We compute invalidation for each flipped
     9        element separately. If the selectors are of form ':active .descendant' then each of these invalidations needs
     10        to traverse the whole subtree, leading to O(n^2) behavior.
     11
     12        We really only need to traverse the descendants once, starting from the element closest to the root that changes state.
     13
     14        * dom/Document.cpp:
     15        (WebCore::Document::updateHoverActiveState):
     16
     17        Compute the change root and pass the information to setActive/Hover.
     18        Reorganize the function a bit to allow this, and for general readability.
     19
     20        * dom/Element.cpp:
     21        (WebCore::Element::setActive):
     22        (WebCore::Element::setHovered):
     23        * dom/Element.h:
     24        * html/HTMLAnchorElement.cpp:
     25        (WebCore::HTMLAnchorElement::setActive):
     26        * html/HTMLAnchorElement.h:
     27        * html/HTMLLabelElement.cpp:
     28        (WebCore::HTMLLabelElement::setActive):
     29        (WebCore::HTMLLabelElement::setHovered):
     30        * html/HTMLLabelElement.h:
     31        * html/shadow/SpinButtonElement.cpp:
     32        (WebCore::SpinButtonElement::setHovered):
     33        * html/shadow/SpinButtonElement.h:
     34        * style/PseudoClassChangeInvalidation.cpp:
     35        (WebCore::Style::PseudoClassChangeInvalidation::computeInvalidation):
     36
     37        Only include descendant traversing rulesets for the change root.
     38
     39        * style/PseudoClassChangeInvalidation.h:
     40        (WebCore::Style::PseudoClassChangeInvalidation::PseudoClassChangeInvalidation):
     41
    1422021-01-18  Fujii Hironori  <Hironori.Fujii@sony.com>
    243

  • trunk/Source/WebCore/dom/Document.cpp

    r271514 r271584  
    71297129    ASSERT(!request.readOnly());
    71307130
     7131    Vector<RefPtr<Element>, 32> elementsToClearActive;
     7132    Vector<RefPtr<Element>, 32> elementsToSetActive;
     7133    Vector<RefPtr<Element>, 32> elementsToClearHover;
     7134    Vector<RefPtr<Element>, 32> elementsToSetHover;
     7135
    71317136    Element* innerElementInDocument = innerElement;
    71327137    while (innerElementInDocument && &innerElementInDocument->document() != this) {
    … …  
    71387143    if (oldActiveElement && !request.active()) {
    71397144        // We are clearing the :active chain because the mouse has been released.
    7140         for (Element* currentElement = oldActiveElement; currentElement; currentElement = currentElement->parentElementInComposedTree()) {
    7141             currentElement->setActive(false);
     7145        for (auto* currentElement = oldActiveElement; currentElement; currentElement = currentElement->parentElementInComposedTree()) {
     7146            elementsToClearActive.append(currentElement);
    71427147            m_userActionElements.setInActiveChain(*currentElement, false);
    71437148        }
    … …  
    71847189    auto* commonAncestor = findNearestCommonComposedAncestor(oldHoveredElement.get(), newHoveredElement);
    71857190
    7186     Vector<RefPtr<Element>, 32> elementsToRemoveFromChain;
    7187     Vector<RefPtr<Element>, 32> elementsToAddToChain;
    7188 
    71897191    if (oldHoveredElement != newHoveredElement) {
    71907192        for (auto* element = oldHoveredElement.get(); element; element = element->parentElementInComposedTree()) {
    71917193            if (element == commonAncestor)
    71927194                break;
    7193             if (!mustBeInActiveChain || element->isInActiveChain())
    7194                 elementsToRemoveFromChain.append(element);
     7195            if (mustBeInActiveChain && !element->isInActiveChain())
     7196                continue;
     7197            elementsToClearHover.append(element);
    71957198        }
    71967199        // Unset hovered nodes in sub frame documents if the old hovered node was a frame owner.
    … …  
    72017204    }
    72027205
     7206    bool sawCommonAncestor = false;
    72037207    for (auto* element = newHoveredElement; element; element = element->parentElementInComposedTree()) {
    7204         if (!mustBeInActiveChain || element->isInActiveChain())
    7205             elementsToAddToChain.append(element);
    7206     }
    7207 
    7208     for (auto& element : elementsToRemoveFromChain)
    7209         element->setHovered(false);
    7210 
    7211     bool sawCommonAncestor = false;
    7212     for (auto& element : elementsToAddToChain) {
     7208        if (mustBeInActiveChain && !element->isInActiveChain())
     7209            continue;
    72137210        if (allowActiveChanges)
    7214             element->setActive(true);
     7211            elementsToSetActive.append(element);
    72157212        if (element == commonAncestor)
    72167213            sawCommonAncestor = true;
    7217         if (!sawCommonAncestor) {
    7218             // Elements after the common hover ancestor does not change hover state, but are iterated over because they may change active state.
    7219             element->setHovered(true);
    7220         }
    7221     }
     7214        if (!sawCommonAncestor)
     7215            elementsToSetHover.append(element);
     7216    }
     7217
     7218    for (auto& element : elementsToClearActive)
     7219        element->setActive(false, false, element == elementsToClearActive.last() ? Element::IsUserActionStateChangeRoot::Yes : Element::IsUserActionStateChangeRoot::No);
     7220    for (auto& element : elementsToSetActive)
     7221        element->setActive(true, false, element == elementsToSetActive.last() ? Element::IsUserActionStateChangeRoot::Yes : Element::IsUserActionStateChangeRoot::No);
     7222    for (auto& element : elementsToClearHover)
     7223        element->setHovered(false, element == elementsToClearHover.last() ? Element::IsUserActionStateChangeRoot::Yes : Element::IsUserActionStateChangeRoot::No);
     7224    for (auto& element : elementsToSetHover)
     7225        element->setHovered(true, element == elementsToSetHover.last() ? Element::IsUserActionStateChangeRoot::Yes : Element::IsUserActionStateChangeRoot::No);
    72227226}
    72237227

  • trunk/Source/WebCore/dom/Element.cpp

    r271446 r271584  
    679679}
    680680
    681 void Element::setActive(bool flag, bool pause)
     681void Element::setActive(bool flag, bool pause, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
    682682{
    683683    if (flag == active())
    684684        return;
    685685    {
    686         Style::PseudoClassChangeInvalidation styleInvalidation(*this, CSSSelector::PseudoClassActive);
     686        Style::PseudoClassChangeInvalidation styleInvalidation(*this, CSSSelector::PseudoClassActive, isUserActionStateChangeRoot);
    687687        document().userActionElements().setActive(*this, flag);
    688688    }
    … …  
    756756}
    757757
    758 void Element::setHovered(bool flag)
     758void Element::setHovered(bool flag, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
    759759{
    760760    if (flag == hovered())
    761761        return;
    762762    {
    763         Style::PseudoClassChangeInvalidation styleInvalidation(*this, CSSSelector::PseudoClassHover);
     763        Style::PseudoClassChangeInvalidation styleInvalidation(*this, CSSSelector::PseudoClassHover, isUserActionStateChangeRoot);
    764764        document().userActionElements().setHovered(*this, flag);
    765765    }

  • trunk/Source/WebCore/dom/Element.h

    r271439 r271584  
    322322    bool hasFocusWithin() const { return hasNodeFlag(NodeFlag::HasFocusWithin); };
    323323
    324     virtual void setActive(bool = true, bool pause = false);
    325     virtual void setHovered(bool = true);
     324    enum class IsUserActionStateChangeRoot { Yes, No };
     325    virtual void setActive(bool = true, bool pause = false, IsUserActionStateChangeRoot = IsUserActionStateChangeRoot::Yes);
     326    virtual void setHovered(bool = true, IsUserActionStateChangeRoot = IsUserActionStateChangeRoot::Yes);
    326327    virtual void setFocus(bool);
    327328    void setBeingDragged(bool);

  • trunk/Source/WebCore/html/HTMLAnchorElement.cpp

    r271124 r271584  
    212212}
    213213
    214 void HTMLAnchorElement::setActive(bool down, bool pause)
     214void HTMLAnchorElement::setActive(bool down, bool pause, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
    215215{
    216216    if (hasEditableStyle()) {
    … …  
    233233    }
    234234   
    235     HTMLElement::setActive(down, pause);
     235    HTMLElement::setActive(down, pause, isUserActionStateChangeRoot);
    236236}
    237237

  • trunk/Source/WebCore/html/HTMLAnchorElement.h

    r269712 r271584  
    8888    bool isKeyboardFocusable(KeyboardEvent*) const override;
    8989    void defaultEventHandler(Event&) final;
    90     void setActive(bool active = true, bool pause = false) final;
     90    void setActive(bool active, bool pause, IsUserActionStateChangeRoot) final;
    9191    bool accessKeyAction(bool sendMouseEvents) final;
    9292    bool isURLAttribute(const Attribute&) const final;

  • trunk/Source/WebCore/html/HTMLLabelElement.cpp

    r269587 r271584  
    8686}
    8787
    88 void HTMLLabelElement::setActive(bool down, bool pause)
     88void HTMLLabelElement::setActive(bool down, bool pause, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
    8989{
    9090    if (down == active())
    … …  
    9292
    9393    // Update our status first.
    94     HTMLElement::setActive(down, pause);
     94    HTMLElement::setActive(down, pause, isUserActionStateChangeRoot);
    9595
    9696    // Also update our corresponding control.
    … …  
    9999}
    100100
    101 void HTMLLabelElement::setHovered(bool over)
     101void HTMLLabelElement::setHovered(bool over, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
    102102{
    103103    if (over == hovered())
    … …  
    105105       
    106106    // Update our status first.
    107     HTMLElement::setHovered(over);
     107    HTMLElement::setHovered(over, isUserActionStateChangeRoot);
    108108
    109109    // Also update our corresponding control.

  • trunk/Source/WebCore/html/HTMLLabelElement.h

    r269587 r271584  
    4646
    4747    // Overridden to update the hover/active state of the corresponding control.
    48     void setActive(bool = true, bool pause = false) final;
    49     void setHovered(bool = true) final;
     48    void setActive(bool, bool pause, IsUserActionStateChangeRoot) final;
     49    void setHovered(bool, IsUserActionStateChangeRoot) final;
    5050
    5151    // Overridden to either click() or focus() the corresponding control.

  • trunk/Source/WebCore/html/shadow/SpinButtonElement.cpp

    r267074 r271584  
    250250}
    251251
    252 void SpinButtonElement::setHovered(bool flag)
     252void SpinButtonElement::setHovered(bool flag, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
    253253{
    254254    if (!flag)
    255255        m_upDownState = Indeterminate;
    256     HTMLDivElement::setHovered(flag);
     256    HTMLDivElement::setHovered(flag, isUserActionStateChangeRoot);
    257257}
    258258

  • trunk/Source/WebCore/html/shadow/SpinButtonElement.h

    r229694 r271584  
    8080    void stopRepeatingTimer();
    8181    void repeatingTimerFired();
    82     void setHovered(bool = true) override;
     82    void setHovered(bool, IsUserActionStateChangeRoot) override;
    8383    bool shouldRespondToMouseEvents();
    8484    bool isMouseFocusable() const override { return false; }

  • trunk/Source/WebCore/style/PseudoClassChangeInvalidation.cpp

    r258321 r271584  
    3333namespace Style {
    3434
    35 void PseudoClassChangeInvalidation::computeInvalidation(CSSSelector::PseudoClassType pseudoClass)
     35void PseudoClassChangeInvalidation::computeInvalidation(CSSSelector::PseudoClassType pseudoClass, Element::IsUserActionStateChangeRoot isUserActionStateChangeRoot)
    3636{
    3737    bool shouldInvalidateCurrent = false;
    … …  
    5555    auto& ruleSets = m_element.styleResolver().ruleSets();
    5656    if (auto* invalidationRuleSets = ruleSets.pseudoClassInvalidationRuleSets(pseudoClass)) {
    57         for (auto& invalidationRuleSet : *invalidationRuleSets)
     57        for (auto& invalidationRuleSet : *invalidationRuleSets) {
     58            // For focus/hover we flip the whole ancestor chain. We only need to do deep invalidation traversal in the change root.
     59            auto shouldInvalidate = [&] {
     60                if (isUserActionStateChangeRoot == Element::IsUserActionStateChangeRoot::Yes)
     61                    return true;
     62                return invalidationRuleSet.matchElement != MatchElement::Ancestor;
     63            }();
     64            if (!shouldInvalidate)
     65                continue;
    5866            Invalidator::addToMatchElementRuleSets(m_matchElementRuleSets, invalidationRuleSet);
     67        }
    5968    }
    6069}

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

    r258321 r271584  
    3636class PseudoClassChangeInvalidation {
    3737public:
    38     PseudoClassChangeInvalidation(Element&, CSSSelector::PseudoClassType);
     38    PseudoClassChangeInvalidation(Element&, CSSSelector::PseudoClassType, Element::IsUserActionStateChangeRoot = Element::IsUserActionStateChangeRoot::Yes);
    3939    ~PseudoClassChangeInvalidation();
    4040
    4141private:
    42     void computeInvalidation(CSSSelector::PseudoClassType);
     42    void computeInvalidation(CSSSelector::PseudoClassType, Element::IsUserActionStateChangeRoot);
    4343    void invalidateStyleWithRuleSets();
    4444
    … …  
    4949};
    5050
    51 inline PseudoClassChangeInvalidation::PseudoClassChangeInvalidation(Element& element, CSSSelector::PseudoClassType pseudoClassType)
     51inline PseudoClassChangeInvalidation::PseudoClassChangeInvalidation(Element& element, CSSSelector::PseudoClassType pseudoClassType, Element::IsUserActionStateChangeRoot isUserActionStateChangeRoot)
    5252    : m_isEnabled(element.needsStyleInvalidation())
    5353    , m_element(element)
    … …  
    5656    if (!m_isEnabled)
    5757        return;
    58     computeInvalidation(pseudoClassType);
     58    computeInvalidation(pseudoClassType, isUserActionStateChangeRoot);
    5959    invalidateStyleWithRuleSets();
    6060}
Note: See TracChangeset for help on using the changeset viewer.