[webkit-changes] [WebKit/WebKit] 5a5af8: updateRelativeLengthsInformation exhibits O(n^2) i...

[Ryosuke Niwa]

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 5a5af81309ac3798f83128299fca8e17bbe9e988
      https://github.com/WebKit/WebKit/commit/5a5af81309ac3798f83128299fca8e17bbe9e988
  Author: Ryosuke Niwa <rniwa at webkit.org>
  Date:   2024-02-01 (Thu, 01 Feb 2024)

  Changed paths:
    M Source/WebCore/svg/SVGElement.cpp
    M Source/WebCore/svg/SVGElement.h

  Log Message:
  -----------
  updateRelativeLengthsInformation exhibits O(n^2) in SVGElement::insertedIntoAncestor
https://bugs.webkit.org/show_bug.cgi?id=268522

Reviewed by Cameron McCormack.

When SVGElement::updateRelativeLengthsInformation() gets called in SVGElement::insertedIntoAncestor,
it traverses inclusive ancestors to update whether an SVGElement contains a child element or "this"
element which uses relative lengths. Because SVGElement::insertedIntoAncestor gets called on each
descendent of an inserted subtree, this results in O(n^2) behavior.

This PR rectifies this situation by avoiding ancestor traversal when we've already registered itself
to the parent. For this, this PR introduces SVGElement::m_hasRegisteredWithParentForRelativeLengths,
which remembers whether the element is registered in parent element's m_elementsWithRelativeLengths,
which is now renamed to m_childElementsWithRelativeLengths for clarity.

In addition, this PR introduces two more boolean member variables to SVGElement:
m_selfHasRelativeLengths, which is a cache for the selfHasRelativeLengths() virtual function call,
and m_hasInitializedRelativeLengthsState, which is initialized to false and set to true whenever
updateRelativeLengthsInformation is called to update m_selfHasRelativeLengths. When this flag is false,
the next invocation of SVGElement::insertedIntoAncestor will call updateRelativeLengthsInformation(),
which updates m_selfHasRelativeLengths and notifies its ancestor SVG elements.

* Source/WebCore/svg/SVGElement.cpp:
(WebCore::SVGElement::removedFromAncestor): Remove this element from old parent's
m_childElementWithRelativeLengths set if this element was removed from the parent.
removedFromAncestor can be called in other scenarios where an ancestor got removed from its parent
and we don't do anything in those cases as this element's parent did not change in such cases.
(WebCore::SVGElement::svgAttributeChanged): Set m_hasInitializedRelativeLengthsState to false so
that updateRelativeLengthsInformation() will be called next time this element is inserted to a tree.
(WebCore::SVGElement::insertedIntoAncestor): Call
(WebCore::SVGElement::updateRelativeLengthsInformation): Moved from .h file. Now updates
m_hasInitializedRelativeLengthsState and m_selfHasRelativeLengths before updating flags on this
element's ancestor SVG elements.
(WebCore::SVGElement::updateRelativeLengthsInformationForChild): Renamed from
updateRelativeLengthsInformation and added a debug assert that second argument's parent node is
"this" element, or we're dealing with an element that had been removed from this subtree.

* Source/WebCore/svg/SVGElement.h:
(WebCore::SVGElement::updateRelativeLengthsInformation): Moved to .cpp file.
(WebCore::SVGElement::hasRelativeLengths const):

Canonical link: https://commits.webkit.org/273936@main