1 // Copyright 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "ui/accessibility/ax_tree_combiner.h"
6
7 #include "ui/accessibility/ax_enums.mojom.h"
8 #include "ui/accessibility/ax_tree.h"
9 #include "ui/gfx/geometry/rect_f.h"
10
11 namespace ui {
12
AXTreeCombiner()13 AXTreeCombiner::AXTreeCombiner() {
14 }
15
~AXTreeCombiner()16 AXTreeCombiner::~AXTreeCombiner() {
17 }
18
AddTree(const AXTreeUpdate & tree,bool is_root)19 void AXTreeCombiner::AddTree(const AXTreeUpdate& tree, bool is_root) {
20 trees_.push_back(tree);
21 if (is_root) {
22 DCHECK_EQ(root_tree_id_, AXTreeIDUnknown());
23 root_tree_id_ = tree.tree_data.tree_id;
24 }
25 }
26
Combine()27 bool AXTreeCombiner::Combine() {
28 // First create a map from tree ID to tree update.
29 for (const auto& tree : trees_) {
30 AXTreeID tree_id = tree.tree_data.tree_id;
31 if (tree_id_map_.find(tree_id) != tree_id_map_.end())
32 return false;
33 tree_id_map_[tree.tree_data.tree_id] = &tree;
34 }
35
36 // Make sure the root tree ID is in the map, otherwise fail.
37 if (tree_id_map_.find(root_tree_id_) == tree_id_map_.end())
38 return false;
39
40 // Process the nodes recursively, starting with the root tree.
41 const AXTreeUpdate* root = tree_id_map_.find(root_tree_id_)->second;
42 ProcessTree(root);
43
44 // Set the root id.
45 combined_.root_id = combined_.nodes.size() > 0 ? combined_.nodes[0].id : 0;
46
47 // Finally, handle the tree ID, taking into account which subtree might
48 // have focus and mapping IDs from the tree data appropriately.
49 combined_.has_tree_data = true;
50 combined_.tree_data = root->tree_data;
51 AXTreeID focused_tree_id = root->tree_data.focused_tree_id;
52 const AXTreeUpdate* focused_tree = root;
53 if (tree_id_map_.find(focused_tree_id) != tree_id_map_.end())
54 focused_tree = tree_id_map_[focused_tree_id];
55 combined_.tree_data.focus_id =
56 MapId(focused_tree_id, focused_tree->tree_data.focus_id);
57 combined_.tree_data.sel_is_backward =
58 MapId(focused_tree_id, focused_tree->tree_data.sel_is_backward);
59 combined_.tree_data.sel_anchor_object_id =
60 MapId(focused_tree_id, focused_tree->tree_data.sel_anchor_object_id);
61 combined_.tree_data.sel_focus_object_id =
62 MapId(focused_tree_id, focused_tree->tree_data.sel_focus_object_id);
63 combined_.tree_data.sel_anchor_offset =
64 focused_tree->tree_data.sel_anchor_offset;
65 combined_.tree_data.sel_focus_offset =
66 focused_tree->tree_data.sel_focus_offset;
67
68 // Debug-mode check that the resulting combined tree is valid.
69 AXTree tree;
70 DCHECK(tree.Unserialize(combined_))
71 << combined_.ToString() << "\n" << tree.error();
72
73 return true;
74 }
75
MapId(AXTreeID tree_id,int32_t node_id)76 int32_t AXTreeCombiner::MapId(AXTreeID tree_id, int32_t node_id) {
77 auto tree_id_node_id = std::make_pair(tree_id, node_id);
78 if (tree_id_node_id_map_[tree_id_node_id] == 0)
79 tree_id_node_id_map_[tree_id_node_id] = next_id_++;
80 return tree_id_node_id_map_[tree_id_node_id];
81 }
82
ProcessTree(const AXTreeUpdate * tree)83 void AXTreeCombiner::ProcessTree(const AXTreeUpdate* tree) {
84 AXTreeID tree_id = tree->tree_data.tree_id;
85 for (size_t i = 0; i < tree->nodes.size(); ++i) {
86 AXNodeData node = tree->nodes[i];
87 AXTreeID child_tree_id = AXTreeID::FromString(
88 node.GetStringAttribute(ax::mojom::StringAttribute::kChildTreeId));
89
90 // Map the node's ID.
91 node.id = MapId(tree_id, node.id);
92
93 // Map the node's child IDs.
94 for (size_t j = 0; j < node.child_ids.size(); ++j)
95 node.child_ids[j] = MapId(tree_id, node.child_ids[j]);
96
97 // Map the container id.
98 if (node.relative_bounds.offset_container_id > 0)
99 node.relative_bounds.offset_container_id =
100 MapId(tree_id, node.relative_bounds.offset_container_id);
101
102 // Map other int attributes that refer to node IDs.
103 for (size_t j = 0; j < node.int_attributes.size(); ++j) {
104 auto& attr = node.int_attributes[j];
105 if (IsNodeIdIntAttribute(attr.first))
106 attr.second = MapId(tree_id, attr.second);
107 }
108
109 // Map other int list attributes that refer to node IDs.
110 for (size_t j = 0; j < node.intlist_attributes.size(); ++j) {
111 auto& attr = node.intlist_attributes[j];
112 if (IsNodeIdIntListAttribute(attr.first)) {
113 for (size_t k = 0; k < attr.second.size(); k++)
114 attr.second[k] = MapId(tree_id, attr.second[k]);
115 }
116 }
117
118 // Remove the ax::mojom::StringAttribute::kChildTreeId attribute.
119 for (size_t j = 0; j < node.string_attributes.size(); ++j) {
120 auto& attr = node.string_attributes[j];
121 if (attr.first == ax::mojom::StringAttribute::kChildTreeId) {
122 attr.first = ax::mojom::StringAttribute::kNone;
123 attr.second = "";
124 }
125 }
126
127 // See if this node has a child tree. As a sanity check make sure the
128 // child tree lists this tree as its parent tree id.
129 const AXTreeUpdate* child_tree = nullptr;
130 if (tree_id_map_.find(child_tree_id) != tree_id_map_.end()) {
131 child_tree = tree_id_map_.find(child_tree_id)->second;
132 if (child_tree->tree_data.parent_tree_id != tree_id)
133 child_tree = nullptr;
134 if (child_tree && child_tree->nodes.empty())
135 child_tree = nullptr;
136 if (child_tree) {
137 node.child_ids.push_back(MapId(child_tree_id,
138 child_tree->nodes[0].id));
139 }
140 }
141
142 // Put the rewritten AXNodeData into the output data structure.
143 combined_.nodes.push_back(node);
144
145 // Recurse into the child tree now, if any.
146 if (child_tree)
147 ProcessTree(child_tree);
148 }
149 }
150
151 } // namespace ui
152