Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 5a5af81309ac3798f83128299fca8e17bbe9e988
https://github.com/WebKit/WebKit/commit/5a5af81309ac3798f83128299fca8e17bbe9e988
Author: Ryosuke Niwa <[email protected]>
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
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
