[go: nahoru, domu]

Optimize AXRange::GetText to avoid multiple tree traversals

1. Refactoring `AXPosition::CreateNextLeafTextPosition` to take an
   optional input parameter `crossed_line_breaking_object` which will
   be set to `true` if any call to `CreateNextAnchorBoundary` made while
   moving to the next leaf anchor crosses a line breaking object.

2. Refactoring `AXRange::GetText` to remove usage of `AtEndOfParagraph`.

   This optimization comes from analyzing how paragraph boundaries are
   computed: in order to determine if the end of an anchor is the end of
   a paragraph, we traverse forward to the next unignored leaf node (if
   it exists), then go back to the previous non-whitespace unignored
   leaf node (if it exists) looking for any line breaking object
   boundary being crossed in our tree traversal.

   The procedure described above is very redundant if we're already
   traversing the leaf nodes of the tree to compute `GetText`, this
   change uses the new parameter in `CreateNextLeafTextPosition` to
   efficiently compute paragraph boundaries without "going back".

   Notice that we still need to call `AtStartOfParagraph` from the first
   non-whitespace leaf node in the range since there could be whitespace
   or ignored leaf nodes preceding the AXRange's start, but such
   scenario could only appear once in any given `GetText` call.

3. As a result of the previous changes, `AtEndOfParagraph` disappears
   completely from the `GetText` call stack, the `AtStartOfParagraph`
   call has no noticeable impact, and the weight of `GetText` is now
   entirely reliant on a single traversal over the tree's leaves.

   Considering the total weight of `CreateNextLeafTextPosition` as a
   reference of "linear" complexity, in average, computing `GetText`
   measures 3.41 times faster with the optimization.

Bug: 1029867
Change-Id: I4ec070a6f96d9118ded08af4c93eb181451bb387
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/2024910
Commit-Queue: Nektarios Paisios <nektar@chromium.org>
Reviewed-by: Nektarios Paisios <nektar@chromium.org>
Reviewed-by: Kevin Babbitt <kbabbitt@microsoft.com>
Cr-Commit-Position: refs/heads/master@{#741096}
2 files changed