GitLab

Refactored the PosInSet & SetSize algorithm, more specifically:
  - AXTree::ComputeSetSizePosInSetAndCache
  - AXTree::PopulateOrderedSetItemsMap
To compute PosInSet & SetSize for ordered set items, we first need to
parse ordered set items from DOM structure and store/populate it into
a data structure, and from which we can perform PosInSet & SetSize
computations. Previously, we store these ordered set items into
std::vector<AXNode*>. Using std::vector works well when set items
from various hierarchical levels are nested in DOM structure. However,
for flattened structure where levels are distinguished by aria-level
attributes, the previous algorithm did not work well. Although
various changes (e.g. CL:1461539) have been made, the algorithm is
still not robust enough for handling flattened structures, Bug:952904.

The primary change in the current CL is to replace
|items_to_be_populated| from std::vector to std::map (and renaming it
to |items_map_to_be_populated|), where hierarchical levels are mapped
to lists of ordered sets:

  std::map<base::Optional<int32_t>, // Hierarchical level
        std::vector<OrderedSetContent>> // Ordered sets on that level

  struct AXTree::OrderedSetContent {
    std::vector<AXNode*> set_items_; // Ordered set items
    AXNode* set_container_; // Ordered set container
  };

This new data structure enables AXTree::PopulateOrderedSetItemsMap to
parse, sort, and store various ordered set items according to its
ordered set and hierarchical level, which greatly cleans up PosInSet
and SetSize algorithm, and more robust handlings for flattened ordered
set structures.

Bug: 952904
Change-Id: Ia856290b143afcf911d9083c735dd7bf9bb3ddf9
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/2036908Reviewed-by: Dominic Mazzoni <dmazzoni@chromium.org>
Reviewed-by: Ian Prest <iapres@microsoft.com>
Reviewed-by: Akihiro Ota <akihiroota@chromium.org>
Commit-Queue: Victor Fei <vicfei@microsoft.com>
Cr-Commit-Position: refs/heads/master@{#745315}