Diff
Modified: branches/safari-611-branch/Source/WebCore/ChangeLog (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/ChangeLog 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/ChangeLog 2021-01-25 22:13:14 UTC (rev 271851)
@@ -1,5 +1,92 @@
2021-01-25 Alan Coon <alanc...@apple.com>
+ Cherry-pick r271584. rdar://problem/73473616
+
+ 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(n^2) 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):
+
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@271584 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 2021-01-18 Antti Koivisto <an...@apple.com>
+
+ 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(n^2) 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):
+
+2021-01-25 Alan Coon <alanc...@apple.com>
+
Cherry-pick r271542. rdar://problem/73477309
(REGRESSION) Playback pauses upon entering PiP via media controls on trailers.apple.com
Modified: branches/safari-611-branch/Source/WebCore/dom/Document.cpp (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/dom/Document.cpp 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/dom/Document.cpp 2021-01-25 22:13:14 UTC (rev 271851)
@@ -7123,6 +7123,11 @@
{
ASSERT(!request.readOnly());
+ Vector<RefPtr<Element>, 32> elementsToClearActive;
+ Vector<RefPtr<Element>, 32> elementsToSetActive;
+ Vector<RefPtr<Element>, 32> elementsToClearHover;
+ Vector<RefPtr<Element>, 32> elementsToSetHover;
+
Element* innerElementInDocument = innerElement;
while (innerElementInDocument && &innerElementInDocument->document() != this) {
innerElementInDocument->document().updateHoverActiveState(request, innerElementInDocument);
@@ -7132,8 +7137,8 @@
Element* oldActiveElement = m_activeElement.get();
if (oldActiveElement && !request.active()) {
// We are clearing the :active chain because the mouse has been released.
- for (Element* currentElement = oldActiveElement; currentElement; currentElement = currentElement->parentElementInComposedTree()) {
- currentElement->setActive(false);
+ for (auto* currentElement = oldActiveElement; currentElement; currentElement = currentElement->parentElementInComposedTree()) {
+ elementsToClearActive.append(currentElement);
m_userActionElements.setInActiveChain(*currentElement, false);
}
m_activeElement = nullptr;
@@ -7178,15 +7183,13 @@
auto* commonAncestor = findNearestCommonComposedAncestor(oldHoveredElement.get(), newHoveredElement);
- Vector<RefPtr<Element>, 32> elementsToRemoveFromChain;
- Vector<RefPtr<Element>, 32> elementsToAddToChain;
-
if (oldHoveredElement != newHoveredElement) {
for (auto* element = oldHoveredElement.get(); element; element = element->parentElementInComposedTree()) {
if (element == commonAncestor)
break;
- if (!mustBeInActiveChain || element->isInActiveChain())
- elementsToRemoveFromChain.append(element);
+ if (mustBeInActiveChain && !element->isInActiveChain())
+ continue;
+ elementsToClearHover.append(element);
}
// Unset hovered nodes in sub frame documents if the old hovered node was a frame owner.
if (is<HTMLFrameOwnerElement>(oldHoveredElement)) {
@@ -7195,25 +7198,26 @@
}
}
+ bool sawCommonAncestor = false;
for (auto* element = newHoveredElement; element; element = element->parentElementInComposedTree()) {
- if (!mustBeInActiveChain || element->isInActiveChain())
- elementsToAddToChain.append(element);
- }
-
- for (auto& element : elementsToRemoveFromChain)
- element->setHovered(false);
-
- bool sawCommonAncestor = false;
- for (auto& element : elementsToAddToChain) {
+ if (mustBeInActiveChain && !element->isInActiveChain())
+ continue;
if (allowActiveChanges)
- element->setActive(true);
+ elementsToSetActive.append(element);
if (element == commonAncestor)
sawCommonAncestor = true;
- if (!sawCommonAncestor) {
- // Elements after the common hover ancestor does not change hover state, but are iterated over because they may change active state.
- element->setHovered(true);
- }
+ if (!sawCommonAncestor)
+ elementsToSetHover.append(element);
}
+
+ for (auto& element : elementsToClearActive)
+ element->setActive(false, false, element == elementsToClearActive.last() ? Element::IsUserActionStateChangeRoot::Yes : Element::IsUserActionStateChangeRoot::No);
+ for (auto& element : elementsToSetActive)
+ element->setActive(true, false, element == elementsToSetActive.last() ? Element::IsUserActionStateChangeRoot::Yes : Element::IsUserActionStateChangeRoot::No);
+ for (auto& element : elementsToClearHover)
+ element->setHovered(false, element == elementsToClearHover.last() ? Element::IsUserActionStateChangeRoot::Yes : Element::IsUserActionStateChangeRoot::No);
+ for (auto& element : elementsToSetHover)
+ element->setHovered(true, element == elementsToSetHover.last() ? Element::IsUserActionStateChangeRoot::Yes : Element::IsUserActionStateChangeRoot::No);
}
bool Document::haveStylesheetsLoaded() const
Modified: branches/safari-611-branch/Source/WebCore/dom/Element.cpp (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/dom/Element.cpp 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/dom/Element.cpp 2021-01-25 22:13:14 UTC (rev 271851)
@@ -678,12 +678,12 @@
return document().userActionElements().isBeingDragged(*this);
}
-void Element::setActive(bool flag, bool pause)
+void Element::setActive(bool flag, bool pause, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
{
if (flag == active())
return;
{
- Style::PseudoClassChangeInvalidation styleInvalidation(*this, CSSSelector::PseudoClassActive);
+ Style::PseudoClassChangeInvalidation styleInvalidation(*this, CSSSelector::PseudoClassActive, isUserActionStateChangeRoot);
document().userActionElements().setActive(*this, flag);
}
@@ -755,12 +755,12 @@
}
}
-void Element::setHovered(bool flag)
+void Element::setHovered(bool flag, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
{
if (flag == hovered())
return;
{
- Style::PseudoClassChangeInvalidation styleInvalidation(*this, CSSSelector::PseudoClassHover);
+ Style::PseudoClassChangeInvalidation styleInvalidation(*this, CSSSelector::PseudoClassHover, isUserActionStateChangeRoot);
document().userActionElements().setHovered(*this, flag);
}
Modified: branches/safari-611-branch/Source/WebCore/dom/Element.h (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/dom/Element.h 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/dom/Element.h 2021-01-25 22:13:14 UTC (rev 271851)
@@ -321,8 +321,9 @@
bool isBeingDragged() const { return isUserActionElement() && isUserActionElementDragged(); }
bool hasFocusWithin() const { return hasNodeFlag(NodeFlag::HasFocusWithin); };
- virtual void setActive(bool = true, bool pause = false);
- virtual void setHovered(bool = true);
+ enum class IsUserActionStateChangeRoot { Yes, No };
+ virtual void setActive(bool = true, bool pause = false, IsUserActionStateChangeRoot = IsUserActionStateChangeRoot::Yes);
+ virtual void setHovered(bool = true, IsUserActionStateChangeRoot = IsUserActionStateChangeRoot::Yes);
virtual void setFocus(bool);
void setBeingDragged(bool);
void setHasFocusWithin(bool);
Modified: branches/safari-611-branch/Source/WebCore/html/HTMLAnchorElement.cpp (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/html/HTMLAnchorElement.cpp 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/html/HTMLAnchorElement.cpp 2021-01-25 22:13:14 UTC (rev 271851)
@@ -211,7 +211,7 @@
HTMLElement::defaultEventHandler(event);
}
-void HTMLAnchorElement::setActive(bool down, bool pause)
+void HTMLAnchorElement::setActive(bool down, bool pause, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
{
if (hasEditableStyle()) {
switch (document().settings().editableLinkBehavior()) {
@@ -232,7 +232,7 @@
}
}
- HTMLElement::setActive(down, pause);
+ HTMLElement::setActive(down, pause, isUserActionStateChangeRoot);
}
void HTMLAnchorElement::parseAttribute(const QualifiedName& name, const AtomString& value)
Modified: branches/safari-611-branch/Source/WebCore/html/HTMLAnchorElement.h (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/html/HTMLAnchorElement.h 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/html/HTMLAnchorElement.h 2021-01-25 22:13:14 UTC (rev 271851)
@@ -87,7 +87,7 @@
bool isMouseFocusable() const override;
bool isKeyboardFocusable(KeyboardEvent*) const override;
void defaultEventHandler(Event&) final;
- void setActive(bool active = true, bool pause = false) final;
+ void setActive(bool active, bool pause, IsUserActionStateChangeRoot) final;
bool accessKeyAction(bool sendMouseEvents) final;
bool isURLAttribute(const Attribute&) const final;
bool canStartSelection() const final;
Modified: branches/safari-611-branch/Source/WebCore/html/HTMLLabelElement.cpp (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/html/HTMLLabelElement.cpp 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/html/HTMLLabelElement.cpp 2021-01-25 22:13:14 UTC (rev 271851)
@@ -85,13 +85,13 @@
return downcast<HTMLFormControlElement>(control.get())->form();
}
-void HTMLLabelElement::setActive(bool down, bool pause)
+void HTMLLabelElement::setActive(bool down, bool pause, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
{
if (down == active())
return;
// Update our status first.
- HTMLElement::setActive(down, pause);
+ HTMLElement::setActive(down, pause, isUserActionStateChangeRoot);
// Also update our corresponding control.
if (auto element = control())
@@ -98,13 +98,13 @@
element->setActive(down, pause);
}
-void HTMLLabelElement::setHovered(bool over)
+void HTMLLabelElement::setHovered(bool over, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
{
if (over == hovered())
return;
// Update our status first.
- HTMLElement::setHovered(over);
+ HTMLElement::setHovered(over, isUserActionStateChangeRoot);
// Also update our corresponding control.
if (auto element = control())
Modified: branches/safari-611-branch/Source/WebCore/html/HTMLLabelElement.h (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/html/HTMLLabelElement.h 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/html/HTMLLabelElement.h 2021-01-25 22:13:14 UTC (rev 271851)
@@ -45,8 +45,8 @@
bool accessKeyAction(bool sendMouseEvents) final;
// Overridden to update the hover/active state of the corresponding control.
- void setActive(bool = true, bool pause = false) final;
- void setHovered(bool = true) final;
+ void setActive(bool, bool pause, IsUserActionStateChangeRoot) final;
+ void setHovered(bool, IsUserActionStateChangeRoot) final;
// Overridden to either click() or focus() the corresponding control.
void defaultEventHandler(Event&) final;
Modified: branches/safari-611-branch/Source/WebCore/html/shadow/SpinButtonElement.cpp (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/html/shadow/SpinButtonElement.cpp 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/html/shadow/SpinButtonElement.cpp 2021-01-25 22:13:14 UTC (rev 271851)
@@ -249,11 +249,11 @@
step(m_upDownState == Up ? 1 : -1);
}
-void SpinButtonElement::setHovered(bool flag)
+void SpinButtonElement::setHovered(bool flag, IsUserActionStateChangeRoot isUserActionStateChangeRoot)
{
if (!flag)
m_upDownState = Indeterminate;
- HTMLDivElement::setHovered(flag);
+ HTMLDivElement::setHovered(flag, isUserActionStateChangeRoot);
}
bool SpinButtonElement::shouldRespondToMouseEvents()
Modified: branches/safari-611-branch/Source/WebCore/html/shadow/SpinButtonElement.h (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/html/shadow/SpinButtonElement.h 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/html/shadow/SpinButtonElement.h 2021-01-25 22:13:14 UTC (rev 271851)
@@ -79,7 +79,7 @@
void startRepeatingTimer();
void stopRepeatingTimer();
void repeatingTimerFired();
- void setHovered(bool = true) override;
+ void setHovered(bool, IsUserActionStateChangeRoot) override;
bool shouldRespondToMouseEvents();
bool isMouseFocusable() const override { return false; }
Modified: branches/safari-611-branch/Source/WebCore/style/PseudoClassChangeInvalidation.cpp (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/style/PseudoClassChangeInvalidation.cpp 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/style/PseudoClassChangeInvalidation.cpp 2021-01-25 22:13:14 UTC (rev 271851)
@@ -32,7 +32,7 @@
namespace WebCore {
namespace Style {
-void PseudoClassChangeInvalidation::computeInvalidation(CSSSelector::PseudoClassType pseudoClass)
+void PseudoClassChangeInvalidation::computeInvalidation(CSSSelector::PseudoClassType pseudoClass, Element::IsUserActionStateChangeRoot isUserActionStateChangeRoot)
{
bool shouldInvalidateCurrent = false;
bool mayAffectStyleInShadowTree = false;
@@ -54,8 +54,17 @@
auto& ruleSets = m_element.styleResolver().ruleSets();
if (auto* invalidationRuleSets = ruleSets.pseudoClassInvalidationRuleSets(pseudoClass)) {
- for (auto& invalidationRuleSet : *invalidationRuleSets)
+ for (auto& invalidationRuleSet : *invalidationRuleSets) {
+ // For focus/hover we flip the whole ancestor chain. We only need to do deep invalidation traversal in the change root.
+ auto shouldInvalidate = [&] {
+ if (isUserActionStateChangeRoot == Element::IsUserActionStateChangeRoot::Yes)
+ return true;
+ return invalidationRuleSet.matchElement != MatchElement::Ancestor;
+ }();
+ if (!shouldInvalidate)
+ continue;
Invalidator::addToMatchElementRuleSets(m_matchElementRuleSets, invalidationRuleSet);
+ }
}
}
Modified: branches/safari-611-branch/Source/WebCore/style/PseudoClassChangeInvalidation.h (271850 => 271851)
--- branches/safari-611-branch/Source/WebCore/style/PseudoClassChangeInvalidation.h 2021-01-25 22:13:09 UTC (rev 271850)
+++ branches/safari-611-branch/Source/WebCore/style/PseudoClassChangeInvalidation.h 2021-01-25 22:13:14 UTC (rev 271851)
@@ -35,11 +35,11 @@
class PseudoClassChangeInvalidation {
public:
- PseudoClassChangeInvalidation(Element&, CSSSelector::PseudoClassType);
+ PseudoClassChangeInvalidation(Element&, CSSSelector::PseudoClassType, Element::IsUserActionStateChangeRoot = Element::IsUserActionStateChangeRoot::Yes);
~PseudoClassChangeInvalidation();
private:
- void computeInvalidation(CSSSelector::PseudoClassType);
+ void computeInvalidation(CSSSelector::PseudoClassType, Element::IsUserActionStateChangeRoot);
void invalidateStyleWithRuleSets();
const bool m_isEnabled;
@@ -48,7 +48,7 @@
Invalidator::MatchElementRuleSets m_matchElementRuleSets;
};
-inline PseudoClassChangeInvalidation::PseudoClassChangeInvalidation(Element& element, CSSSelector::PseudoClassType pseudoClassType)
+inline PseudoClassChangeInvalidation::PseudoClassChangeInvalidation(Element& element, CSSSelector::PseudoClassType pseudoClassType, Element::IsUserActionStateChangeRoot isUserActionStateChangeRoot)
: m_isEnabled(element.needsStyleInvalidation())
, m_element(element)
@@ -55,7 +55,7 @@
{
if (!m_isEnabled)
return;
- computeInvalidation(pseudoClassType);
+ computeInvalidation(pseudoClassType, isUserActionStateChangeRoot);
invalidateStyleWithRuleSets();
}
