[webkit-changes] [WebKit/WebKit] 299bc2: [iOS] Typing is extremely slow when editing very l...

[Wenson Hsieh]

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 299bc278524d3ebfb4492df41811f8ed721313a1
      https://github.com/WebKit/WebKit/commit/299bc278524d3ebfb4492df41811f8ed721313a1
  Author: Wenson Hsieh <wenson_hsieh at apple.com>
  Date:   2023-05-15 (Mon, 15 May 2023)

  Changed paths:
    M Source/WebCore/platform/graphics/FontCascade.cpp
    M Source/WebCore/platform/graphics/FontCascade.h
    M Source/WebCore/rendering/RenderObject.cpp
    M Source/WebCore/rendering/RenderObject.h
    M Source/WebCore/rendering/RenderText.cpp
    M Source/WebCore/rendering/RenderText.h
    M Source/WebKit/WebProcess/WebPage/ios/WebPageIOS.mm
    M Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
    M Tools/TestWebKitAPI/Tests/WebKitCocoa/DocumentEditingContext.mm
    A Tools/TestWebKitAPI/Tests/WebKitCocoa/editable-body-mixed-text.html

  Log Message:
  -----------
  [iOS] Typing is extremely slow when editing very long sentences, with out-of-process keyboard
https://bugs.webkit.org/show_bug.cgi?id=256762
rdar://106950483

Reviewed by Myles Maxfield, Alan Baradlay and Tim Horton.

When out-of-process keyboard is enabled, UIKit requests document editing contexts upon every
selection change, and asks for three sentences-worth of context before and after the selection. For
extremely long sentences (e.g. 1000+ characters), each document context request can take hundreds of
milliseconds to process, causing the web process to noticeably hang during each keystroke. The vast
majority of this time is spent computing individual rects corresponding to each character in the
editing context range; the way we currently do this is by:

1.  Using `CharacterIterator` to construct a single-character `SimpleRange` for each character in
    the editing context range.
2.  Using `RenderObject::absoluteTextRects` on each character range, and uniting the results.
3.  Mapping each rect back into root view coordinate space.

The performance issues arise in step (2), since `RenderObject::absoluteTextRects` for a range in a
text run works by using text layout helpers to advance from the start of the run to the beginning
of the requested range, advancing to the end of the requested range, and using the difference in
width to compute the final rect. When called over *all* individual character ranges in a given text
run of length `N`, this means that the number of times we advance through the text run is `O(N^2)`.
As such, the current performance characteristics of step (2) above are `O(MN^2)`, where `M` is the
number of text runs in the context and `N` represents (on average) the number of characters per run.

To fix this, we improve the `O(N^2)` algorithm for computing character rects to just `O(N)`, by
introducing and adopting new helper methods to ask for a list of each individual character rect in
a given text run. In my testing on an iPad Pro 3rd generation with ~3000 characters worth of context
before and after the selection, this speeds document editing request time up by a factor of roughly
25x, which is enough to make typing and text interactions feel instantly responsive.

Though these changes shouldn't change behavior (since it's only a performance optimization), the
patch adds 4 new API tests to help exercise some additional corner cases that aren't already covered
by existing tests: `DocumentEditingContext.CharacterRectConsistency*`. See below for more details.

* Source/WebCore/layout/integration/inline/InlineIteratorTextBox.cpp:

* Source/WebCore/layout/integration/inline/InlineIteratorTextBox.h:
* Source/WebCore/platform/graphics/FontCascade.cpp:
(WebCore::FontCascade::characterSelectionRectsForText const):

Add a new helper method to return a list of character rects, in the given range in a text run. This
works similarly to the existing `adjustSelectionRectForText` method, except that it uses a single
complex text controller to advance from the start to the end, and emits a character rect every time
it advances.

* Source/WebCore/platform/graphics/FontCascade.h:
* Source/WebCore/rendering/RenderObject.cpp:
(WebCore::RenderObject::absoluteTextQuads):

Refactor this to pass the whole `OptionSet` of behaviors down to `absoluteQuadsForRange`.

(WebCore::absoluteRectsForRangeInText):
* Source/WebCore/rendering/RenderObject.h:

Add a new `BoundingRectBehavior` type: `ComputeIndividualCharacterRects`, which indicates that the
client wants a rect representing each individual text character.

* Source/WebCore/rendering/RenderText.cpp:
(WebCore::RenderText::absoluteRectsForRange const):

Refactor this to pass in an `OptionSet`.

(WebCore::characterRects const):

Add a new helper function to return a list of character rects, in the given range.

(WebCore::RenderText::absoluteQuadsForRange const):

Make this take an `OptionSet` of behaviors instead of individual boolean flags. I opted for this
approach over adding a third `bool` parameter to this function, since it would be cleaner (and make
this more extensible moving forward).

* Source/WebCore/rendering/RenderText.h:
(WebCore::RenderText::absoluteQuadsForRange):

Honor `ComputeIndividualCharacterRects` here by using the per-character helpers described above to
compute a list of character rects for each character in the given range.

* Source/WebKit/WebProcess/WebPage/ios/WebPageIOS.mm:
(WebKit::WebPage::requestDocumentEditingContext):

Switch from `CharacterIterator` to `TextIterator`, and ask for rects for each text run found by the
text iterator using the new `ComputeIndividualCharacterRects` option.

* Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* Tools/TestWebKitAPI/Tests/WebKitCocoa/DocumentEditingContext.mm:
(-[NSString composedCharacterRanges]):
(-[UIWKDocumentContext boundingRectForCharacterRange:]):
(-[TestWKWebView firstSelectionRect]):
(-[TestWKWebView waitForFirstSelectionRectToChange:]):

Add several API test helper methods.

(checkThatAllCharacterRectsAreConsistentWithSelectionRects):
* Tools/TestWebKitAPI/Tests/WebKitCocoa/editable-body-mixed-text.html: Added.

Add a few new test cases to verify that the character rects received via document editing context
are consistent with actual selection rects. To do this, we first use the document context API to
request character rects after focusing the test page; we then select every grapheme cluster in the
page, and verify that the final selection rect (as presented by UIKit) matches what we got in the
beginning, via the context's character rect info.

This approach keeps the tests robust over time against platform changes (as opposed to more naive
approaches like checking against hard-coded values). We also exercise various text layout scenarios
that aren't fully covered by existing tests:

- Emojis and other glyphs that span multiple codepoints
- Bidirectional text
- Left-to-right vs. right-to-left text on the body
- Horizontal vs. vertical writing mode on the body

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