[webkit-changes] [WebKit/WebKit] 1f27ea: SVGTextMetricsBuilder::measureTextRenderer exhibit...

Ryosuke Niwa noreply at github.com
Thu Nov 2 08:57:20 PDT 2023


  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 1f27ea47a3924a8c56faae0fbf2e1346682949f5
      https://github.com/WebKit/WebKit/commit/1f27ea47a3924a8c56faae0fbf2e1346682949f5
  Author: Ryosuke Niwa <rniwa at webkit.org>
  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




More information about the webkit-changes mailing list