Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 1f27ea47a3924a8c56faae0fbf2e1346682949f5
https://github.com/WebKit/WebKit/commit/1f27ea47a3924a8c56faae0fbf2e1346682949f5
Author: Ryosuke Niwa <[email protected]>
Date: 2023-11-02 (Thu, 02 Nov 2023)
Changed paths:
M Source/WebCore/rendering/svg/RenderSVGText.cpp
M Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.cpp
M Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.h
M Source/WebCore/rendering/svg/SVGTextMetricsBuilder.cpp
M Source/WebCore/rendering/svg/SVGTextMetricsBuilder.h
Log Message:
-----------
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
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
