commit | 781d63b1050778130966c0a6dfa915e617c03e3d | [log] [tgz] |
---|---|---|
author | Ethan Jimenez <ethavar@microsoft.com> | Thu Feb 13 17:06:00 2020 |
committer | Commit Bot <commit-bot@chromium.org> | Thu Feb 13 17:06:00 2020 |
tree | c7129d1e5d8b1b07180a9e23fcde5671e1476038 | |
parent | 9195b452e5c599363ef95bf43ab3517a08716394 [diff] |
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}
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all users to experience the web.
The project's web site is https://www.chromium.org.
Documentation in the source is rooted in docs/README.md.
Learn how to Get Around the Chromium Source Code Directory Structure .