Implement Cache for pos_in_set and set_size values
Improve upon previous implementation of GetPosInSet and GetSetSize
for AXNode, which computed pos_in_set and set_size values upon every
call of either function. Introduced cache for these values in AXTree,
which maps a node's id to a struct holding its pos_in_set and set_size
values. Cache is invalidated upon updates to the AXTree.
Change-Id: I70c0878b05b53b98648af1f2b76d1e1bf6e6d294
Reviewed-on: https://chromium-review.googlesource.com/c/1351782
Reviewed-by: Dominic Mazzoni <[email protected]>
Commit-Queue: Akihiro Ota <[email protected]>
Cr-Commit-Position: refs/heads/master@{#613316}diff --git a/ui/accessibility/ax_node.cc b/ui/accessibility/ax_node.cc
index bc78724..2c95578 100644
--- a/ui/accessibility/ax_node.cc
+++ b/ui/accessibility/ax_node.cc
@@ -512,87 +512,78 @@
}
}
-// Returns true if the node's role uses PosInSet and SetSize
-// Returns false otherwise.
-bool AXNode::IsSetSizePosInSetUsedInRole() const {
- switch (data().role) {
- case ax::mojom::Role::kArticle:
- case ax::mojom::Role::kListItem:
- case ax::mojom::Role::kMenuItem:
- case ax::mojom::Role::kMenuItemRadio:
- case ax::mojom::Role::kTab:
- case ax::mojom::Role::kMenuItemCheckBox:
- case ax::mojom::Role::kTreeItem:
- case ax::mojom::Role::kListBoxOption:
- case ax::mojom::Role::kRadioButton:
- return true;
-
- default:
- return false;
- }
-}
-
-// Returns true if a node's role matches with the role of its container.
-// Returns false otherwise.
-bool AXNode::ContainerRoleMatches(AXNode* container) const {
- ax::mojom::Role container_role = container->data().role;
- switch (data().role) {
- case ax::mojom::Role::kArticle:
- return container_role == ax::mojom::Role::kFeed;
-
- case ax::mojom::Role::kListItem:
- return container_role == ax::mojom::Role::kList ||
- container_role == ax::mojom::Role::kGroup;
-
- case ax::mojom::Role::kMenuItem:
- return container_role == ax::mojom::Role::kMenu ||
- container_role == ax::mojom::Role::kGroup ||
- container_role == ax::mojom::Role::kMenuBar;
-
- case ax::mojom::Role::kMenuItemRadio:
- return container_role == ax::mojom::Role::kGroup ||
- container_role == ax::mojom::Role::kMenu ||
- container_role == ax::mojom::Role::kMenuBar;
-
- case ax::mojom::Role::kTab:
- return container_role == ax::mojom::Role::kTabList;
-
- case ax::mojom::Role::kMenuItemCheckBox:
- return container_role == ax::mojom::Role::kMenu ||
- container_role == ax::mojom::Role::kMenuBar;
-
- case ax::mojom::Role::kTreeItem:
- return container_role == ax::mojom::Role::kTree ||
- container_role == ax::mojom::Role::kGroup;
-
- case ax::mojom::Role::kListBoxOption:
- return container_role == ax::mojom::Role::kListBox;
-
- case ax::mojom::Role::kRadioButton:
- return container_role == ax::mojom::Role::kRadioGroup;
-
- default:
- return false;
- }
-}
-
+// pos_in_set and set_size related functions.
+// Uses AXTree's cache to calculate node's pos_in_set.
int32_t AXNode::GetPosInSet() {
- int32_t pos = -1;
- int32_t size = -1;
- ComputeSetSizePosInSet(&pos, &size);
- return pos;
-}
-int32_t AXNode::GetSetSize() {
- int32_t pos = -1;
- int32_t size = -1;
- ComputeSetSizePosInSet(&pos, &size);
- return size;
+ // Only allow this to be called on nodes that can hold pos_in_set values,
+ // which are defined in the ARIA spec.
+ if (!IsItemLike(data().role))
+ return 0;
+
+ // See AXTree::GetPosInSet
+ return tree_->GetPosInSet(*this);
}
-// Finds and returns a pointer to node's container.
-// Is not required to have a role that matches node's role.
-// Returns nullptr if node is not contained within container.
-AXNode* AXNode::GetContainer() const {
+// Uses AXTree's cache to calculate node's pos_in_set.
+int32_t AXNode::GetSetSize() {
+ // Only allow this to be called on nodes that can hold set_size values, which
+ // are defined in the ARIA spec.
+ if (!(IsItemLike(data().role) || IsSetLike(data().role)))
+ return 0;
+
+ // See AXTree::GetSetSize
+ return tree_->GetSetSize(*this);
+}
+
+// Returns true if the role of ordered set matches the role of item.
+// Returns false otherwise.
+bool AXNode::SetRoleMatchesItemRole(const AXNode* ordered_set) const {
+ ax::mojom::Role item_role = data().role;
+
+ // Switch on role of ordered set
+ switch (ordered_set->data().role) {
+ case ax::mojom::Role::kFeed:
+ return item_role == ax::mojom::Role::kArticle;
+
+ case ax::mojom::Role::kList:
+ return item_role == ax::mojom::Role::kListItem;
+
+ case ax::mojom::Role::kGroup:
+ return item_role == ax::mojom::Role::kListItem ||
+ item_role == ax::mojom::Role::kMenuItem ||
+ item_role == ax::mojom::Role::kMenuItemRadio ||
+ item_role == ax::mojom::Role::kTreeItem;
+
+ case ax::mojom::Role::kMenu:
+ return item_role == ax::mojom::Role::kMenuItem ||
+ item_role == ax::mojom::Role::kMenuItemRadio ||
+ item_role == ax::mojom::Role::kMenuItemCheckBox;
+
+ case ax::mojom::Role::kMenuBar:
+ return item_role == ax::mojom::Role::kMenuItem ||
+ item_role == ax::mojom::Role::kMenuItemRadio ||
+ item_role == ax::mojom::Role::kMenuItemCheckBox;
+
+ case ax::mojom::Role::kTabList:
+ return item_role == ax::mojom::Role::kTab;
+
+ case ax::mojom::Role::kTree:
+ return item_role == ax::mojom::Role::kTreeItem;
+
+ case ax::mojom::Role::kListBox:
+ return item_role == ax::mojom::Role::kListBoxOption;
+
+ case ax::mojom::Role::kRadioGroup:
+ return item_role == ax::mojom::Role::kRadioButton;
+
+ default:
+ return false;
+ }
+}
+
+// Finds ordered set that immediately contains node.
+// Is not required for set's role to match node's role.
+AXNode* AXNode::GetOrderedSet() const {
AXNode* result = parent();
// Continue walking up while parent is invalid, ignored, or is a generic
// container.
@@ -604,126 +595,4 @@
return result;
}
-// Populates items vector with all nodes within container whose roles match.
-void AXNode::PopulateContainerItems(AXNode* container,
- AXNode* local_parent,
- std::vector<AXNode*>& items) const {
- // Stop searching current path if roles of local_parent and container match.
- // Don't compare the container to itself.
- if (!(container == local_parent))
- if (local_parent->data().role == container->data().role)
- return;
-
- for (int i = 0; i < local_parent->child_count(); ++i) {
- AXNode* child = local_parent->children_[i];
- // Add child to items if role matches with root container's role.
- if (child->ContainerRoleMatches(container))
- items.push_back(child);
- // Recurse if there is a generic container or is ignored.
- if (child->data().role == ax::mojom::Role::kGenericContainer ||
- child->data().role == ax::mojom::Role::kIgnored) {
- PopulateContainerItems(container, child, items);
- }
- }
-}
-
-// Computes pos_in_set and set_size values for this node.
-void AXNode::ComputeSetSizePosInSet(int32_t* out_pos_in_set,
- int32_t* out_set_size) {
- // Error checks
- AXNode* container = GetContainer();
- if (!(container && IsSetSizePosInSetUsedInRole() &&
- ContainerRoleMatches(container))) {
- *out_pos_in_set = 0;
- *out_set_size = 0;
- return;
- }
-
- // Find all items within parent container and add to vector.
- std::vector<AXNode*> items;
- PopulateContainerItems(container, container, items);
-
- // Necessary for calculating set_size. Keeps track of largest assigned
- // kSetSize for each role.
- std::unordered_map<ax::mojom::Role, int> largest_assigned_set_size;
-
- // Iterate over vector of items and calculate pos_in_set and set_size for
- // each. Items is not guaranteed to be populated with items of the same role.
- // Use dictionary that maps role to frequency to calculate pos_in_set.
- std::unordered_map<ax::mojom::Role, int> role_counts;
- AXNode* node;
- ax::mojom::Role node_role;
-
- // Compute pos_in_set values.
- for (unsigned int i = 0; i < items.size(); ++i) {
- node = items[i];
- node_role = node->data().role;
- int32_t pos_in_set_value = 0;
-
- if (role_counts.find(node_role) == role_counts.end())
- // This is the first node with its role.
- pos_in_set_value = 1;
- else {
- // This is the next node with its role.
- pos_in_set_value = role_counts[node_role] + 1;
- }
-
- // Check if node has kPosInSet assigned. This assignment takes precedence
- // over previous assignment.
- if (node->HasIntAttribute(ax::mojom::IntAttribute::kPosInSet)) {
- pos_in_set_value =
- node->GetIntAttribute(ax::mojom::IntAttribute::kPosInSet);
- // If invalid assignment (decrease or duplicate), adjust value.
- if (pos_in_set_value <= role_counts[node_role]) {
- pos_in_set_value = role_counts[node_role] + 1;
- }
- }
-
- // Assign pos_in_set and update role counts.
- if (node == this) {
- *out_pos_in_set = pos_in_set_value;
- }
- role_counts[node_role] = pos_in_set_value;
-
- // Check if kSetSize is assigned and update if it's the largest assigned
- // kSetSize.
- if (node->HasIntAttribute(ax::mojom::IntAttribute::kSetSize))
- largest_assigned_set_size[node_role] =
- std::max(largest_assigned_set_size[node_role],
- node->GetIntAttribute(ax::mojom::IntAttribute::kSetSize));
- }
-
- // Compute set_size values.
- for (unsigned int j = 0; j < items.size(); ++j) {
- node = items[j];
- node_role = node->data().role;
-
- // TODO (akihiroota): List objects should report SetSize
-
- // The SetSize of a node is the maximum of the following candidate values:
- // 1. The PosInSet of the last value in the container (with same role as
- // node's)
- // 2. The Largest assigned SetSize in the container
- // 3. The SetSize assigned within the node's container
- int32_t pos_candidate = role_counts[node_role];
- int32_t largest_set_size_candidate = 0;
- if (largest_assigned_set_size.find(node_role) !=
- largest_assigned_set_size.end()) {
- largest_set_size_candidate = largest_assigned_set_size[node_role];
- }
- int32_t container_candidate = 0;
- if (container->HasIntAttribute(ax::mojom::IntAttribute::kSetSize)) {
- container_candidate =
- container->GetIntAttribute(ax::mojom::IntAttribute::kSetSize);
- }
-
- // Assign set_size
- if (node == this) {
- *out_set_size =
- std::max(std::max(pos_candidate, largest_set_size_candidate),
- container_candidate);
- }
- }
-}
-
} // namespace ui
diff --git a/ui/accessibility/ax_node.h b/ui/accessibility/ax_node.h
index 3349c38..7b2893c5 100644
--- a/ui/accessibility/ax_node.h
+++ b/ui/accessibility/ax_node.h
@@ -32,6 +32,9 @@
virtual AXTableInfo* GetTableInfo(const AXNode* table_node) const = 0;
// See AXTree.
virtual AXNode* GetFromId(int32_t id) const = 0;
+
+ virtual int32_t GetPosInSet(const AXNode& item) = 0;
+ virtual int32_t GetSetSize(const AXNode& node) = 0;
};
// The constructor requires a parent, id, and index in parent, but
@@ -186,6 +189,12 @@
// PosInSet and SetSize public methods
int32_t GetPosInSet();
int32_t GetSetSize();
+ // Finds and returns a pointer to ordered set containing node.
+ AXNode* GetOrderedSet() const;
+ // Helpers for GetPosInSet and GetSetSize.
+ // Returns true if the role of ordered set matches the role of item.
+ // Returns false otherwise.
+ bool SetRoleMatchesItemRole(const AXNode* ordered_set) const;
const std::string& GetInheritedStringAttribute(
ax::mojom::StringAttribute attribute) const;
@@ -262,21 +271,6 @@
void IdVectorToNodeVector(std::vector<int32_t>& ids,
std::vector<AXNode*>* nodes) const;
- // Helpers for GetPosInSet and GetSetSize.
- // Returns true if the role of parent container matches the role of node.
- // Returns false otherwise.
- bool ContainerRoleMatches(AXNode* parent) const;
- // Returns true if the node's role uses PosInSet and SetSize
- // Returns false otherwise.
- bool IsSetSizePosInSetUsedInRole() const;
- // Finds and returns a pointer to node's container.
- AXNode* GetContainer() const;
- // Populates items vector with all nodes within container whose roles match.
- void PopulateContainerItems(AXNode* container,
- AXNode* local_parent,
- std::vector<AXNode*>& items) const;
- // Computes pos_in_set and set_size values for this node.
- void ComputeSetSizePosInSet(int32_t* out_pos_in_set, int32_t* out_set_size);
OwnerTree* tree_; // Owns this.
int index_in_parent_;
diff --git a/ui/accessibility/ax_role_properties.cc b/ui/accessibility/ax_role_properties.cc
index 0c851bb..a73a9e6 100644
--- a/ui/accessibility/ax_role_properties.cc
+++ b/ui/accessibility/ax_role_properties.cc
@@ -160,6 +160,23 @@
}
}
+bool IsItemLike(const ax::mojom::Role role) {
+ switch (role) {
+ case ax::mojom::Role::kArticle:
+ case ax::mojom::Role::kListItem:
+ case ax::mojom::Role::kMenuItem:
+ case ax::mojom::Role::kMenuItemRadio:
+ case ax::mojom::Role::kTab:
+ case ax::mojom::Role::kMenuItemCheckBox:
+ case ax::mojom::Role::kTreeItem:
+ case ax::mojom::Role::kListBoxOption:
+ case ax::mojom::Role::kRadioButton:
+ return true;
+ default:
+ return false;
+ }
+}
+
bool IsLink(const ax::mojom::Role role) {
switch (role) {
case ax::mojom::Role::kDocBackLink:
@@ -241,6 +258,23 @@
}
}
+bool IsSetLike(const ax::mojom::Role role) {
+ switch (role) {
+ case ax::mojom::Role::kFeed:
+ case ax::mojom::Role::kList:
+ case ax::mojom::Role::kGroup:
+ case ax::mojom::Role::kMenu:
+ case ax::mojom::Role::kMenuBar:
+ case ax::mojom::Role::kTabList:
+ case ax::mojom::Role::kTree:
+ case ax::mojom::Role::kListBox:
+ case ax::mojom::Role::kRadioGroup:
+ return true;
+ default:
+ return false;
+ }
+}
+
bool IsTableHeader(ax::mojom::Role role) {
switch (role) {
case ax::mojom::Role::kColumnHeader:
diff --git a/ui/accessibility/ax_role_properties.h b/ui/accessibility/ax_role_properties.h
index c6a8026..d9a1e73 100644
--- a/ui/accessibility/ax_role_properties.h
+++ b/ui/accessibility/ax_role_properties.h
@@ -41,6 +41,10 @@
// Returns true if the provided role belongs to an image, graphic, canvas, etc.
AX_EXPORT bool IsImage(const ax::mojom::Role role);
+// Returns true if the provided role is item-like, specifically if it can hold
+// pos_in_set and set_size values.
+AX_EXPORT bool IsItemLike(const ax::mojom::Role role);
+
// Returns true if the provided role belongs to a link.
AX_EXPORT bool IsLink(const ax::mojom::Role role);
@@ -61,6 +65,10 @@
// table or grid row.
AX_EXPORT bool IsRowContainer(const ax::mojom::Role role);
+// Returns true if the provided role is ordered-set like, specifically if it
+// can hold set_size values.
+AX_EXPORT bool IsSetLike(const ax::mojom::Role role);
+
// Returns true if the provided role belongs to a table header.
AX_EXPORT bool IsTableHeader(ax::mojom::Role role);
diff --git a/ui/accessibility/ax_tree.cc b/ui/accessibility/ax_tree.cc
index 1b5932fb..b9fb4ae 100644
--- a/ui/accessibility/ax_tree.cc
+++ b/ui/accessibility/ax_tree.cc
@@ -13,6 +13,7 @@
#include "base/strings/stringprintf.h"
#include "ui/accessibility/accessibility_switches.h"
#include "ui/accessibility/ax_node.h"
+#include "ui/accessibility/ax_role_properties.h"
#include "ui/accessibility/ax_table_info.h"
#include "ui/gfx/transform.h"
@@ -468,6 +469,9 @@
this, root_->id() != old_root_id, changes);
}
+ // Clear list_info_map_
+ ordered_set_info_map_.clear();
+
return true;
}
@@ -878,4 +882,133 @@
return return_value;
}
+// Populates items vector with all items within ordered set whose roles match.
+void AXTree::PopulateOrderedSetItems(const AXNode* ordered_set,
+ const AXNode* local_parent,
+ std::vector<const AXNode*>& items) const {
+ // Stop searching current path if roles of local_parent and ordered set match.
+ // Don't compare the container to itself.
+ if (!(ordered_set == local_parent)) {
+ if (local_parent->data().role == ordered_set->data().role)
+ return;
+ }
+
+ for (int i = 0; i < local_parent->child_count(); ++i) {
+ const AXNode* child = local_parent->GetUnignoredChildAtIndex(i);
+ // Add child to items if role matches with ordered set's role.
+ if (child->SetRoleMatchesItemRole(ordered_set))
+ items.push_back(child);
+ // Recurse if there is a generic container or is ignored.
+ if (child->data().role == ax::mojom::Role::kGenericContainer ||
+ child->data().role == ax::mojom::Role::kIgnored) {
+ PopulateOrderedSetItems(ordered_set, child, items);
+ }
+ }
+}
+
+// Given an ordered_set, compute pos_in_set and set_size for all of its items
+// and store values in cache.
+void AXTree::ComputeSetSizePosInSetAndCache(const AXNode* ordered_set) {
+ // Default ordered_set's pos_in_set and set_size to 0.
+ ordered_set_info_map_[ordered_set->id()] = OrderedSetInfo();
+
+ // Find all items within ordered_set and add to vector.
+ std::vector<const AXNode*> items;
+ PopulateOrderedSetItems(ordered_set, ordered_set, items);
+
+ // Keep track of the number of elements ordered_set has
+ int32_t num_elements = 0;
+
+ // Necessary for calculating set_size.
+ int32_t largest_assigned_set_size = 0;
+
+ // Compute pos_in_set_values.
+ for (size_t i = 0; i < items.size(); ++i) {
+ const AXNode* item = items[i];
+ ordered_set_info_map_[item->id()] = OrderedSetInfo();
+ int32_t pos_in_set_value = 0;
+
+ pos_in_set_value = num_elements + 1;
+
+ // Check if item has a valid kPosInSet assignment, which takes precedence
+ // over previous assignment. Invalid assignments are decreasing or
+ // duplicates, and should be ignored.
+ pos_in_set_value =
+ std::max(pos_in_set_value,
+ item->GetIntAttribute(ax::mojom::IntAttribute::kPosInSet));
+
+ // Assign pos_in_set and update role counts.
+ ordered_set_info_map_[item->id()].pos_in_set = pos_in_set_value;
+ num_elements = pos_in_set_value;
+
+ // Check if kSetSize is assigned and update if it's the largest assigned
+ // kSetSize.
+ if (item->HasIntAttribute(ax::mojom::IntAttribute::kSetSize))
+ largest_assigned_set_size =
+ std::max(largest_assigned_set_size,
+ item->GetIntAttribute(ax::mojom::IntAttribute::kSetSize));
+ }
+
+ // Compute set_size value.
+ // The SetSize of an ordered set (and all of its items) is the maximum of the
+ // following candidate values:
+ // 1. The PosInSet of the last item in the ordered set
+ // 2. The Largest assigned SetSize in the ordered set.
+ // 3. The SetSize assigned within the ordered set.
+ int32_t pos_candidate = num_elements;
+ int32_t largest_set_size_candidate = largest_assigned_set_size;
+ int32_t ordered_set_candidate = 0;
+ if (ordered_set->HasIntAttribute(ax::mojom::IntAttribute::kSetSize)) {
+ ordered_set_candidate =
+ ordered_set->GetIntAttribute(ax::mojom::IntAttribute::kSetSize);
+ }
+ int32_t set_size_value =
+ std::max(std::max(pos_candidate, largest_set_size_candidate),
+ ordered_set_candidate);
+
+ // Assign set_size to ordered set
+ ordered_set_info_map_[ordered_set->id()].set_size = set_size_value;
+
+ // Assign set_size to items
+ for (size_t j = 0; j < items.size(); ++j) {
+ const AXNode* item = items[j];
+ ordered_set_info_map_[item->id()].set_size = set_size_value;
+ }
+}
+
+// Returns the pos_in_set of item. Looks in ordered_set_info_map_ for cached
+// value. Calculates pos_in_set and set_size for item (and all other items in
+// the same ordered set) if no value is present in the cache.
+// This function is guaranteed to be only called on nodes that can hold
+// pos_in_set values, minimizing the size of the cache.
+int32_t AXTree::GetPosInSet(const AXNode& item) {
+ // If item's id is not in the cache, compute it.
+ if (ordered_set_info_map_.find(item.id()) == ordered_set_info_map_.end())
+ ComputeSetSizePosInSetAndCache(item.GetOrderedSet());
+
+ return ordered_set_info_map_[item.id()].pos_in_set;
+}
+
+// Returns the set_size of node. node could be an ordered set or an item.
+// Looks in ordered_set_info_map_ for cached value. Calculates pos_inset_set
+// and set_size for all nodes in same ordered set if no value is present in the
+// cache.
+// This function is guaranteed to be only called on nodes that can hold
+// set_size values, minimizing the size of the cache.
+int32_t AXTree::GetSetSize(const AXNode& node) {
+ const AXNode* ordered_set;
+
+ // If node's id is not in the cache, compute it.
+ if (ordered_set_info_map_.find(node.id()) == ordered_set_info_map_.end()) {
+ // If node is item-like, find its outerlying ordered set
+ if (IsItemLike(node.data().role))
+ ordered_set = node.GetOrderedSet();
+ // If its set-like, then it is the ordered set
+ else
+ ordered_set = &node;
+ ComputeSetSizePosInSetAndCache(ordered_set);
+ }
+ return ordered_set_info_map_[node.id()].set_size;
+}
+
} // namespace ui
diff --git a/ui/accessibility/ax_tree.h b/ui/accessibility/ax_tree.h
index fb8f2b74..1c36cd2 100644
--- a/ui/accessibility/ax_tree.h
+++ b/ui/accessibility/ax_tree.h
@@ -257,6 +257,19 @@
// conflict with positive-numbered node IDs from tree sources.
int32_t GetNextNegativeInternalNodeId();
+ // Returns the pos_in_set of item. Looks in ordered_set_info_map_ for cached
+ // value. Calculates pos_in_set and set_size for item (and all other items in
+ // the same ordered set) if no value is present in the cache.
+ // This function is guaranteed to be only called on nodes that can hold
+ // pos_in_set values, minimizing the size of the cache.
+ int32_t GetPosInSet(const AXNode& item) override;
+ // Returns the set_size of node. Looks in ordered_set_info_map_ for cached
+ // value. Calculates pos_inset_set and set_size for node (and all other nodes
+ // in the same ordered set) if no value is present in the cache.
+ // This function is guaranteed to be only called on nodes that can hold
+ // set_size values, minimizing the size of the cache.
+ int32_t GetSetSize(const AXNode& node) override;
+
private:
friend class AXTableInfoTest;
@@ -340,6 +353,27 @@
// this code to be unit-tested on other platforms (for example, more
// code sanitizers run on Linux).
bool enable_extra_mac_nodes_ = false;
+
+ // Contains pos_in_set and set_size data for an AXNode.
+ struct OrderedSetInfo {
+ int32_t pos_in_set;
+ int32_t set_size;
+ OrderedSetInfo() : pos_in_set(0), set_size(0) {}
+ ~OrderedSetInfo() {}
+ };
+
+ // Populates items vector with all items within ordered_set whose roles match.
+ void PopulateOrderedSetItems(const AXNode* ordered_set,
+ const AXNode* local_parent,
+ std::vector<const AXNode*>& items) const;
+ // Helper for GetPosInSet and GetSetSize. Computes the pos_in_set and set_size
+ // values of all items in ordered_set and caches those values.
+ void ComputeSetSizePosInSetAndCache(const AXNode* ordered_set);
+
+ // Map from node ID to OrderedSetInfo, if the given node
+ // is an element within an ordered set.
+ // Invalidated every time the tree is updated.
+ mutable std::unordered_map<int32_t, OrderedSetInfo> ordered_set_info_map_;
};
} // namespace ui
diff --git a/ui/accessibility/ax_tree_unittest.cc b/ui/accessibility/ax_tree_unittest.cc
index 109eda9..b5a6452 100644
--- a/ui/accessibility/ax_tree_unittest.cc
+++ b/ui/accessibility/ax_tree_unittest.cc
@@ -1472,7 +1472,7 @@
EXPECT_EQ(0U, child_tree_93_nodes.size());
}
-// Tests PosInSet and SetSize int attributes work if assigned.
+// Tests GetPosInSet and GetSetSize return the assigned int attribute values.
TEST(AXTreeTest, TestSetSizePosInSetAssigned) {
AXTreeUpdate tree_update;
tree_update.root_id = 1;
@@ -1505,7 +1505,7 @@
EXPECT_EQ(item3->GetSetSize(), 12);
}
-// Tests that PosInSet and SetSize can be calculated if not assigned.
+// Tests that pos_in_set and set_size can be calculated if not assigned.
TEST(AXTreeTest, TestSetSizePosInSetUnassigned) {
AXTreeUpdate tree_update;
tree_update.root_id = 1;
@@ -1532,7 +1532,8 @@
EXPECT_EQ(item3->GetSetSize(), 3);
}
-// Tests PosInSet unassigned, while SetSize assigned in container.
+// Tests pos_in_set can be calculated if unassigned, and set_size can be
+// assigned on the outerlying ordered set.
TEST(AXTreeTest, TestSetSizeAssignedInContainer) {
AXTreeUpdate tree_update;
tree_update.root_id = 1;
@@ -1549,7 +1550,7 @@
tree_update.nodes[3].role = ax::mojom::Role::kListItem;
AXTree tree(tree_update);
- // Items should inherit SetSize from container if not specified.
+ // Items should inherit set_size from ordered set if not specified.
AXNode* item1 = tree.GetFromId(2);
EXPECT_EQ(item1->GetSetSize(), 7);
AXNode* item2 = tree.GetFromId(3);
@@ -1558,60 +1559,45 @@
EXPECT_EQ(item3->GetSetSize(), 7);
}
-// Tests PosInSet and SetSize on a list containing various roles.
-// Roles for items and associated container should match up.
+// Tests GetPosInSet and GetSetSize on a list containing various roles.
+// Roles for items and associated ordered set should match up.
TEST(AXTreeTest, TestSetSizePosInSetDiverseList) {
AXTreeUpdate tree_update;
tree_update.root_id = 1;
- tree_update.nodes.resize(9);
+ tree_update.nodes.resize(6);
tree_update.nodes[0].id = 1;
- tree_update.nodes[0].role = ax::mojom::Role::kList;
- tree_update.nodes[0].child_ids = {2, 3, 4, 5, 6, 7, 8, 9};
+ tree_update.nodes[0].role = ax::mojom::Role::kMenu;
+ tree_update.nodes[0].child_ids = {2, 3, 4, 5, 6};
tree_update.nodes[1].id = 2;
- tree_update.nodes[1].role = ax::mojom::Role::kListItem; // 1 of 3
+ tree_update.nodes[1].role = ax::mojom::Role::kMenuItem; // 1 of 4
tree_update.nodes[2].id = 3;
- tree_update.nodes[2].role = ax::mojom::Role::kMenuItem; // 0 of 0
+ tree_update.nodes[2].role = ax::mojom::Role::kMenuItem; // 2 of 4
tree_update.nodes[3].id = 4;
- tree_update.nodes[3].role = ax::mojom::Role::kListItem; // 2 of 3
+ tree_update.nodes[3].role = ax::mojom::Role::kMenuItemRadio; // 3 of 4
tree_update.nodes[4].id = 5;
- tree_update.nodes[4].role = ax::mojom::Role::kMenuItem; // 0 of 0
+ tree_update.nodes[4].role = ax::mojom::Role::kMenuItem; // 4 of 4
tree_update.nodes[5].id = 6;
- tree_update.nodes[5].role = ax::mojom::Role::kArticle; // 0 of 0
- tree_update.nodes[6].id = 7;
- tree_update.nodes[6].role = ax::mojom::Role::kArticle; // 0 of 0
- tree_update.nodes[7].id = 8;
- tree_update.nodes[7].role = ax::mojom::Role::kListItem; // 3 of 3
- tree_update.nodes[8].id = 9;
- tree_update.nodes[8].role = ax::mojom::Role::kImage; // 0 of 0
+ tree_update.nodes[5].role = ax::mojom::Role::kTab; // 0 of 0
AXTree tree(tree_update);
- AXNode* listitem1 = tree.GetFromId(2);
- EXPECT_EQ(listitem1->GetPosInSet(), 1);
- EXPECT_EQ(listitem1->GetSetSize(), 3);
- AXNode* menuitem1 = tree.GetFromId(3);
- EXPECT_EQ(menuitem1->GetPosInSet(), 0);
- EXPECT_EQ(menuitem1->GetSetSize(), 0);
- AXNode* listitem2 = tree.GetFromId(4);
- EXPECT_EQ(listitem2->GetPosInSet(), 2);
- EXPECT_EQ(listitem2->GetSetSize(), 3);
- AXNode* menuitem2 = tree.GetFromId(5);
- EXPECT_EQ(menuitem2->GetPosInSet(), 0);
- EXPECT_EQ(menuitem2->GetSetSize(), 0);
- AXNode* article1 = tree.GetFromId(6);
- EXPECT_EQ(article1->GetPosInSet(), 0);
- EXPECT_EQ(article1->GetSetSize(), 0);
- AXNode* article2 = tree.GetFromId(7);
- EXPECT_EQ(article2->GetPosInSet(), 0);
- EXPECT_EQ(article2->GetSetSize(), 0);
- AXNode* listitem3 = tree.GetFromId(8);
- EXPECT_EQ(listitem3->GetPosInSet(), 3);
- EXPECT_EQ(listitem3->GetSetSize(), 3);
- AXNode* image = tree.GetFromId(9);
+ AXNode* item1 = tree.GetFromId(2);
+ EXPECT_EQ(item1->GetPosInSet(), 1);
+ EXPECT_EQ(item1->GetSetSize(), 4);
+ AXNode* item2 = tree.GetFromId(3);
+ EXPECT_EQ(item2->GetPosInSet(), 2);
+ EXPECT_EQ(item2->GetSetSize(), 4);
+ AXNode* radio = tree.GetFromId(4);
+ EXPECT_EQ(radio->GetPosInSet(), 3);
+ EXPECT_EQ(radio->GetSetSize(), 4);
+ AXNode* item3 = tree.GetFromId(5);
+ EXPECT_EQ(item3->GetPosInSet(), 4);
+ EXPECT_EQ(item3->GetSetSize(), 4);
+ AXNode* image = tree.GetFromId(6);
EXPECT_EQ(image->GetPosInSet(), 0);
EXPECT_EQ(image->GetSetSize(), 0);
}
-// Tests PosInSet and SetSize on a nested list.
+// Tests GetPosInSet and GetSetSize on a nested list.
TEST(AXTreeTest, TestSetSizePosInSetNestedList) {
AXTreeUpdate tree_update;
tree_update.root_id = 1;
@@ -1641,12 +1627,6 @@
EXPECT_EQ(outer_item2->GetPosInSet(), 2);
EXPECT_EQ(outer_item2->GetSetSize(), 3);
- // List object itself should not report posinset or setsize.
- // TODO (akihiroota): Lists should report setsize in the future.
- AXNode* inner_list = tree.GetFromId(4);
- EXPECT_EQ(inner_list->GetPosInSet(), 0);
- EXPECT_EQ(inner_list->GetSetSize(), 0);
-
AXNode* inner_item1 = tree.GetFromId(5);
EXPECT_EQ(inner_item1->GetPosInSet(), 1);
EXPECT_EQ(inner_item1->GetSetSize(), 2);
@@ -1659,8 +1639,8 @@
EXPECT_EQ(outer_item3->GetSetSize(), 3);
}
-// Tests PosInSet can be calculated if one item specifies PosInSet, but others
-// are missing.
+// Tests pos_in_set can be calculated if one item specifies pos_in_set, but
+// other assignments are missing.
TEST(AXTreeTest, TestPosInSetMissing) {
AXTreeUpdate tree_update;
tree_update.root_id = 1;
@@ -1691,7 +1671,7 @@
EXPECT_EQ(item3->GetSetSize(), 20);
}
-// A more difficult test that invovles missing PosInSet and SetSize values.
+// A more difficult test that invovles missing pos_in_set and set_size values.
TEST(AXTreeTest, TestSetSizePosInSetMissingDifficult) {
AXTreeUpdate tree_update;
tree_update.root_id = 1;
@@ -1732,7 +1712,7 @@
EXPECT_EQ(item5->GetSetSize(), 11);
}
-// Tests that code overwrites decreasing SetSize assignments to largest of
+// Tests that code overwrites decreasing set_size assignments to largest of
// assigned values.
TEST(AXTreeTest, TestSetSizeDecreasing) {
AXTreeUpdate tree_update;
@@ -1762,7 +1742,7 @@
EXPECT_EQ(item3->GetSetSize(), 5);
}
-// Tests that code overwrites decreasing PosInSet values.
+// Tests that code overwrites decreasing pos_in_set values.
TEST(AXTreeTest, TestPosInSetDecreasing) {
AXTreeUpdate tree_update;
tree_update.root_id = 1;
@@ -1791,7 +1771,7 @@
EXPECT_EQ(item3->GetSetSize(), 8);
}
-// Tests that code overwrites duplicate PosInSet values. Note this case is
+// Tests that code overwrites duplicate pos_in_set values. Note this case is
// tricky; an update to the second element causes an update to the third
// element.
TEST(AXTreeTest, TestPosInSetDuplicates) {
@@ -1823,7 +1803,7 @@
EXPECT_EQ(item3->GetSetSize(), 8);
}
-// Tests PosInSet and SetSize when some list items are nested in a generic
+// Tests GetPosInSet and GetSetSize when some list items are nested in a generic
// container.
TEST(AXTreeTest, TestSetSizePosInSetNestedContainer) {
AXTreeUpdate tree_update;
@@ -1868,4 +1848,183 @@
EXPECT_EQ(item4->GetSetSize(), 4);
}
+// Tests GetSetSize and GetPosInSet are correct, even when list items change.
+// This test is directed at the caching functionality of pos_in_set and
+// set_size. Tests that previously calculated values are not used after
+// tree is updated.
+TEST(AXTreeTest, TestSetSizePosInSetDeleteItem) {
+ AXTreeUpdate initial_state;
+ initial_state.root_id = 1;
+ initial_state.nodes.resize(4);
+ initial_state.nodes[0].id = 1;
+ initial_state.nodes[0].role = ax::mojom::Role::kList;
+ initial_state.nodes[0].child_ids = {2, 3, 4};
+ initial_state.nodes[1].id = 2;
+ initial_state.nodes[1].role = ax::mojom::Role::kListItem; // 1 of 3
+ initial_state.nodes[2].id = 3;
+ initial_state.nodes[2].role = ax::mojom::Role::kListItem; // 2 of 3
+ initial_state.nodes[3].id = 4;
+ initial_state.nodes[3].role = ax::mojom::Role::kListItem; // 3 of 3
+ AXTree tree(initial_state);
+
+ AXNode* item1 = tree.GetFromId(2);
+ EXPECT_EQ(item1->GetPosInSet(), 1);
+ EXPECT_EQ(item1->GetSetSize(), 3);
+ AXNode* item2 = tree.GetFromId(3);
+ EXPECT_EQ(item2->GetPosInSet(), 2);
+ EXPECT_EQ(item2->GetSetSize(), 3);
+ AXNode* item3 = tree.GetFromId(4);
+ EXPECT_EQ(item3->GetPosInSet(), 3);
+ EXPECT_EQ(item3->GetSetSize(), 3);
+
+ // TreeUpdates only need to describe what changed in tree.
+ AXTreeUpdate update = initial_state;
+ update.nodes.resize(1);
+ update.nodes[0].child_ids = {2, 4}; // Delete item 2 of 3 from list.
+ EXPECT_TRUE(tree.Unserialize(update));
+
+ AXNode* new_item1 = tree.GetFromId(2);
+ EXPECT_EQ(new_item1->GetPosInSet(), 1);
+ EXPECT_EQ(new_item1->GetSetSize(), 2);
+ AXNode* new_item2 = tree.GetFromId(4);
+ EXPECT_EQ(new_item2->GetPosInSet(), 2);
+ EXPECT_EQ(new_item2->GetSetSize(), 2);
+}
+
+// Tests GetSetSize and GetPosInSet are correct, even when list items change.
+// This test adds an item to the front of a list, which invalidates previously
+// calculated pos_in_set and set_size values. Tests that old values are not
+// used after tree is updated.
+TEST(AXTreeTest, TestSetSizePosInSetAddItem) {
+ AXTreeUpdate initial_state;
+ initial_state.root_id = 1;
+ initial_state.nodes.resize(4);
+ initial_state.nodes[0].id = 1;
+ initial_state.nodes[0].role = ax::mojom::Role::kList;
+ initial_state.nodes[0].child_ids = {2, 3, 4};
+ initial_state.nodes[1].id = 2;
+ initial_state.nodes[1].role = ax::mojom::Role::kListItem; // 1 of 3
+ initial_state.nodes[2].id = 3;
+ initial_state.nodes[2].role = ax::mojom::Role::kListItem; // 2 of 3
+ initial_state.nodes[3].id = 4;
+ initial_state.nodes[3].role = ax::mojom::Role::kListItem; // 3 of 3
+ AXTree tree(initial_state);
+
+ AXNode* item1 = tree.GetFromId(2);
+ EXPECT_EQ(item1->GetPosInSet(), 1);
+ EXPECT_EQ(item1->GetSetSize(), 3);
+ AXNode* item2 = tree.GetFromId(3);
+ EXPECT_EQ(item2->GetPosInSet(), 2);
+ EXPECT_EQ(item2->GetSetSize(), 3);
+ AXNode* item3 = tree.GetFromId(4);
+ EXPECT_EQ(item3->GetPosInSet(), 3);
+ EXPECT_EQ(item3->GetSetSize(), 3);
+
+ // Insert item at beginning of list
+ AXTreeUpdate update = initial_state;
+ update.nodes.resize(2);
+ update.nodes[0].id = 1;
+ update.nodes[0].child_ids = {5, 2, 3, 4};
+ update.nodes[1].id = 5;
+ update.nodes[1].role = ax::mojom::Role::kListItem;
+ EXPECT_TRUE(tree.Unserialize(update));
+
+ AXNode* new_item1 = tree.GetFromId(5);
+ EXPECT_EQ(new_item1->GetPosInSet(), 1);
+ EXPECT_EQ(new_item1->GetSetSize(), 4);
+ AXNode* new_item2 = tree.GetFromId(2);
+ EXPECT_EQ(new_item2->GetPosInSet(), 2);
+ EXPECT_EQ(new_item2->GetSetSize(), 4);
+ AXNode* new_item3 = tree.GetFromId(3);
+ EXPECT_EQ(new_item3->GetPosInSet(), 3);
+ EXPECT_EQ(new_item3->GetSetSize(), 4);
+ AXNode* new_item4 = tree.GetFromId(4);
+ EXPECT_EQ(new_item4->GetPosInSet(), 4);
+ EXPECT_EQ(new_item4->GetSetSize(), 4);
+}
+
+// Tests that the outerlying ordered set reports its set_size. Ordered sets
+// should not report a pos_in_set value other than 0, since they are not
+// considered to be items within a set (even when nested).
+TEST(AXTreeTest, TestOrderedSetReportsSetSize) {
+ AXTreeUpdate tree_update;
+ tree_update.root_id = 1;
+ tree_update.nodes.resize(12);
+ tree_update.nodes[0].id = 1;
+ tree_update.nodes[0].role = ax::mojom::Role::kList; // set_size = 3
+ tree_update.nodes[0].child_ids = {2, 3, 4, 7, 8, 9, 12};
+ tree_update.nodes[1].id = 2;
+ tree_update.nodes[1].role = ax::mojom::Role::kListItem; // 1 of 3
+ tree_update.nodes[2].id = 3;
+ tree_update.nodes[2].role = ax::mojom::Role::kListItem; // 2 of 3
+ tree_update.nodes[3].id = 4;
+ tree_update.nodes[3].role = ax::mojom::Role::kList; // set_size = 2
+ tree_update.nodes[3].child_ids = {5, 6};
+ tree_update.nodes[4].id = 5;
+ tree_update.nodes[4].role = ax::mojom::Role::kListItem; // 1 of 2
+ tree_update.nodes[5].id = 6;
+ tree_update.nodes[5].role = ax::mojom::Role::kListItem; // 2 of 2
+ tree_update.nodes[6].id = 7;
+ tree_update.nodes[6].role = ax::mojom::Role::kListItem; // 3 of 3
+ tree_update.nodes[7].id = 8;
+ tree_update.nodes[7].role = ax::mojom::Role::kList; // set_size = 0
+ tree_update.nodes[8].id = 9;
+ tree_update.nodes[8].role =
+ ax::mojom::Role::kList; // set_size = 1 because only 1 item whose role
+ // matches
+ tree_update.nodes[8].child_ids = {10, 11};
+ tree_update.nodes[9].id = 10;
+ tree_update.nodes[9].role = ax::mojom::Role::kArticle;
+ tree_update.nodes[10].id = 11;
+ tree_update.nodes[10].role = ax::mojom::Role::kListItem;
+ tree_update.nodes[11].id = 12;
+ tree_update.nodes[11].role = ax::mojom::Role::kList;
+ tree_update.nodes[11].AddIntAttribute(ax::mojom::IntAttribute::kSetSize, 5);
+ AXTree tree(tree_update);
+
+ AXNode* outer_list = tree.GetFromId(1);
+ EXPECT_EQ(outer_list->GetPosInSet(), 0); // Ordered sets have pos of 0
+ EXPECT_EQ(outer_list->GetSetSize(), 3);
+ AXNode* outer_list_item1 = tree.GetFromId(2);
+ EXPECT_EQ(outer_list_item1->GetPosInSet(), 1);
+ EXPECT_EQ(outer_list_item1->GetSetSize(), 3);
+ AXNode* outer_list_item2 = tree.GetFromId(3);
+ EXPECT_EQ(outer_list_item2->GetPosInSet(), 2);
+ EXPECT_EQ(outer_list_item2->GetSetSize(), 3);
+ AXNode* outer_list_item3 = tree.GetFromId(7);
+ EXPECT_EQ(outer_list_item3->GetPosInSet(), 3);
+ EXPECT_EQ(outer_list_item3->GetSetSize(), 3);
+
+ AXNode* inner_list1 = tree.GetFromId(4);
+ EXPECT_EQ(inner_list1->GetPosInSet(),
+ 0); // Ordered sets have pos of 0, even when nested
+ EXPECT_EQ(inner_list1->GetSetSize(), 2);
+ AXNode* inner_list1_item1 = tree.GetFromId(5);
+ EXPECT_EQ(inner_list1_item1->GetPosInSet(), 1);
+ EXPECT_EQ(inner_list1_item1->GetSetSize(), 2);
+ AXNode* inner_list1_item2 = tree.GetFromId(6);
+ EXPECT_EQ(inner_list1_item2->GetPosInSet(), 2);
+ EXPECT_EQ(inner_list1_item2->GetSetSize(), 2);
+
+ AXNode* inner_list2 = tree.GetFromId(8); // Empty list
+ EXPECT_EQ(inner_list2->GetPosInSet(), 0);
+ EXPECT_EQ(inner_list2->GetSetSize(), 0);
+
+ AXNode* inner_list3 = tree.GetFromId(9);
+ EXPECT_EQ(inner_list3->GetPosInSet(), 0);
+ EXPECT_EQ(inner_list3->GetSetSize(), 1); // Only 1 item whose role matches
+ AXNode* inner_list3_article1 = tree.GetFromId(10);
+ EXPECT_EQ(inner_list3_article1->GetPosInSet(), 0);
+ EXPECT_EQ(inner_list3_article1->GetSetSize(), 0);
+ AXNode* inner_list3_item1 = tree.GetFromId(11);
+ EXPECT_EQ(inner_list3_item1->GetPosInSet(), 1);
+ EXPECT_EQ(inner_list3_item1->GetSetSize(), 1);
+
+ AXNode* inner_list4 = tree.GetFromId(12);
+ EXPECT_EQ(inner_list4->GetPosInSet(), 0);
+ // Even though list is empty, kSetSize attribute was set, so it takes
+ // precedence
+ EXPECT_EQ(inner_list4->GetSetSize(), 5);
+}
+
} // namespace ui
