SVGTextMetricsBuilder::measureTextRenderer exhibits O(n^2) behavior by rniwa · P...

edited by webkit-early-warning-system

1f27ea4

SVGTextMetricsBuilder::measureTextRenderer exhibits O(n^2) behavior
https://bugs.webkit.org/show_bug.cgi?id=264076

Reviewed by Chris Dumez.

Prior to this PR, RenderSVGText::willLayout() called SVGTextLayoutAttributesBuilder's
rebuildMetricsForTextRenderer and therefore SVGTextMetricsBuilder's measureTextRenderer
on each descendant RenderObject of RenderSVGText. Since rebuildMetricsForTextRenderer
does a tree traversal from the ancestor RenderSVGText to the specified node, this
exhibited O(1+2+3+ ... +n) = O(n^2) behavior.

This PR rectifies this situation by combining all rebuildMetricsForTextRenderer calls
for descendants as a single call to SVGTextLayoutAttributesBuilder's now renamed
rebuildMetricsForSubtree.

This PR also eliminates O(n^2) behavior in updateFontInAllDescendants in RenderSVGText.cpp
by combining all calls to rebuildMetricsForTextRenderer.

* Source/WebCore/rendering/svg/RenderSVGText.cpp:
(WebCore::RenderSVGText::willLayout):
(WebCore::updateFontInAllDescendants):
(WebCore::RenderSVGText::layout):
* Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.cpp:
(WebCore::SVGTextLayoutAttributesBuilder::rebuildMetricsForSubtree):
(WebCore::SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer): Deleted.
* Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.h:
* Source/WebCore/rendering/svg/SVGTextMetricsBuilder.cpp:
(WebCore::SVGTextMetricsBuilder::measureTextRenderer):
* Source/WebCore/rendering/svg/SVGTextMetricsBuilder.h:

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

6e43ffb

Ahmad-S792 reacted with rocket emoji