1 // Copyright 2013 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.h"
6
7 #include <stddef.h>
8
9 #include <algorithm>
10 #include <numeric>
11 #include <utility>
12
13 #include "base/auto_reset.h"
14 #include "base/command_line.h"
15 #include "base/logging.h"
16 #include "base/memory/ptr_util.h"
17 #include "base/no_destructor.h"
18 #include "base/stl_util.h"
19 #include "base/strings/stringprintf.h"
20 #include "ui/accessibility/accessibility_switches.h"
21 #include "ui/accessibility/ax_enums.mojom.h"
22 #include "ui/accessibility/ax_language_detection.h"
23 #include "ui/accessibility/ax_node.h"
24 #include "ui/accessibility/ax_node_position.h"
25 #include "ui/accessibility/ax_role_properties.h"
26 #include "ui/accessibility/ax_table_info.h"
27 #include "ui/accessibility/ax_tree_observer.h"
28 #include "ui/gfx/transform.h"
29
30 namespace ui {
31
32 namespace {
33
TreeToStringHelper(const AXNode * node,int indent)34 std::string TreeToStringHelper(const AXNode* node, int indent) {
35 if (!node)
36 return "";
37
38 return std::accumulate(
39 node->children().cbegin(), node->children().cend(),
40 std::string(2 * indent, ' ') + node->data().ToString() + "\n",
41 [indent](const std::string& str, const auto* child) {
42 return str + TreeToStringHelper(child, indent + 1);
43 });
44 }
45
46 template <typename K, typename V>
KeyValuePairsKeysMatch(std::vector<std::pair<K,V>> pairs1,std::vector<std::pair<K,V>> pairs2)47 bool KeyValuePairsKeysMatch(std::vector<std::pair<K, V>> pairs1,
48 std::vector<std::pair<K, V>> pairs2) {
49 if (pairs1.size() != pairs2.size())
50 return false;
51 for (size_t i = 0; i < pairs1.size(); ++i) {
52 if (pairs1[i].first != pairs2[i].first)
53 return false;
54 }
55 return true;
56 }
57
58 template <typename K, typename V>
MapFromKeyValuePairs(std::vector<std::pair<K,V>> pairs)59 std::map<K, V> MapFromKeyValuePairs(std::vector<std::pair<K, V>> pairs) {
60 std::map<K, V> result;
61 for (size_t i = 0; i < pairs.size(); ++i)
62 result[pairs[i].first] = pairs[i].second;
63 return result;
64 }
65
66 // Given two vectors of <K, V> key, value pairs representing an "old" vs "new"
67 // state, or "before" vs "after", calls a callback function for each key that
68 // changed value. Note that if an attribute is removed, that will result in
69 // a call to the callback with the value changing from the previous value to
70 // |empty_value|, and similarly when an attribute is added.
71 template <typename K, typename V, typename F>
CallIfAttributeValuesChanged(const std::vector<std::pair<K,V>> & pairs1,const std::vector<std::pair<K,V>> & pairs2,const V & empty_value,F callback)72 void CallIfAttributeValuesChanged(const std::vector<std::pair<K, V>>& pairs1,
73 const std::vector<std::pair<K, V>>& pairs2,
74 const V& empty_value,
75 F callback) {
76 // Fast path - if they both have the same keys in the same order.
77 if (KeyValuePairsKeysMatch(pairs1, pairs2)) {
78 for (size_t i = 0; i < pairs1.size(); ++i) {
79 if (pairs1[i].second != pairs2[i].second)
80 callback(pairs1[i].first, pairs1[i].second, pairs2[i].second);
81 }
82 return;
83 }
84
85 // Slower path - they don't have the same keys in the same order, so
86 // check all keys against each other, using maps to prevent this from
87 // becoming O(n^2) as the size grows.
88 auto map1 = MapFromKeyValuePairs(pairs1);
89 auto map2 = MapFromKeyValuePairs(pairs2);
90 for (size_t i = 0; i < pairs1.size(); ++i) {
91 const auto& new_iter = map2.find(pairs1[i].first);
92 if (pairs1[i].second != empty_value && new_iter == map2.end())
93 callback(pairs1[i].first, pairs1[i].second, empty_value);
94 }
95
96 for (size_t i = 0; i < pairs2.size(); ++i) {
97 const auto& iter = map1.find(pairs2[i].first);
98 if (iter == map1.end())
99 callback(pairs2[i].first, empty_value, pairs2[i].second);
100 else if (iter->second != pairs2[i].second)
101 callback(pairs2[i].first, iter->second, pairs2[i].second);
102 }
103 }
104
IsCollapsed(const AXNode * node)105 bool IsCollapsed(const AXNode* node) {
106 return node && node->data().HasState(ax::mojom::State::kCollapsed);
107 }
108
109 } // namespace
110
111 // This object is used to track structure changes that will occur for a specific
112 // AXID. This includes how many times we expect that a node with a specific AXID
113 // will be created and/or destroyed, and how many times a subtree rooted at AXID
114 // expects to be destroyed during an AXTreeUpdate.
115 //
116 // An AXTreeUpdate is a serialized representation of an atomic change to an
117 // AXTree. See also |AXTreeUpdate| which documents the nature and invariants
118 // required to atomically update the AXTree.
119 //
120 // The reason that we must track these counts, and the reason these are counts
121 // rather than a bool/flag is because an AXTreeUpdate may contain multiple
122 // AXNodeData updates for a given AXID. A common way that this occurs is when
123 // multiple AXTreeUpdates are merged together, combining their AXNodeData list.
124 // Additionally AXIDs may be reused after being removed from the tree,
125 // most notably when "reparenting" a node. A "reparent" occurs when an AXID is
126 // first destroyed from the tree then created again in the same AXTreeUpdate,
127 // which may also occur multiple times with merged updates.
128 //
129 // We need to accumulate these counts for 3 reasons :
130 // 1. To determine what structure changes *will* occur before applying
131 // updates to the tree so that we can notify observers of structure changes
132 // when the tree is still in a stable and unchanged state.
133 // 2. Capture any errors *before* applying updates to the tree structure
134 // due to the order of (or lack of) AXNodeData entries in the update
135 // so we can abort a bad update instead of applying it partway.
136 // 3. To validate that the expectations we accumulate actually match
137 // updates that are applied to the tree.
138 //
139 // To reiterate the invariants that this structure is taking a dependency on
140 // from |AXTreeUpdate|, suppose that the next AXNodeData to be applied is
141 // |node|. The following invariants must hold:
142 // 1. Either
143 // a) |node.id| is already in the tree, or
144 // b) the tree is empty, and
145 // |node| is the new root of the tree, and
146 // |node.role| == WebAXRoleRootWebArea.
147 // 2. Every child id in |node.child_ids| must either be already a child
148 // of this node, or a new id not previously in the tree. It is not
149 // allowed to "reparent" a child to this node without first removing
150 // that child from its previous parent.
151 // 3. When a new id appears in |node.child_ids|, the tree should create a
152 // new uninitialized placeholder node for it immediately. That
153 // placeholder must be updated within the same AXTreeUpdate, otherwise
154 // it's a fatal error. This guarantees the tree is always complete
155 // before or after an AXTreeUpdate.
156 struct PendingStructureChanges {
PendingStructureChangesui::PendingStructureChanges157 explicit PendingStructureChanges(const AXNode* node)
158 : destroy_subtree_count(0),
159 destroy_node_count(0),
160 create_node_count(0),
161 node_exists(!!node),
162 parent_node_id((node && node->parent())
163 ? base::Optional<AXNode::AXID>{node->parent()->id()}
164 : base::nullopt),
165 last_known_data(node ? &node->data() : nullptr) {}
166
167 // Returns true if this node has any changes remaining.
168 // This includes pending subtree or node destruction, and node creation.
DoesNodeExpectAnyStructureChangesui::PendingStructureChanges169 bool DoesNodeExpectAnyStructureChanges() const {
170 return DoesNodeExpectSubtreeWillBeDestroyed() ||
171 DoesNodeExpectNodeWillBeDestroyed() ||
172 DoesNodeExpectNodeWillBeCreated();
173 }
174
175 // Returns true if there are any pending changes that require destroying
176 // this node or its subtree.
DoesNodeExpectSubtreeOrNodeWillBeDestroyedui::PendingStructureChanges177 bool DoesNodeExpectSubtreeOrNodeWillBeDestroyed() const {
178 return DoesNodeExpectSubtreeWillBeDestroyed() ||
179 DoesNodeExpectNodeWillBeDestroyed();
180 }
181
182 // Returns true if the subtree rooted at this node needs to be destroyed
183 // during the update, but this may not be the next action that needs to be
184 // performed on the node.
DoesNodeExpectSubtreeWillBeDestroyedui::PendingStructureChanges185 bool DoesNodeExpectSubtreeWillBeDestroyed() const {
186 return destroy_subtree_count;
187 }
188
189 // Returns true if this node needs to be destroyed during the update, but this
190 // may not be the next action that needs to be performed on the node.
DoesNodeExpectNodeWillBeDestroyedui::PendingStructureChanges191 bool DoesNodeExpectNodeWillBeDestroyed() const { return destroy_node_count; }
192
193 // Returns true if this node needs be created during the update, but this
194 // may not be the next action that needs to be performed on the node.
DoesNodeExpectNodeWillBeCreatedui::PendingStructureChanges195 bool DoesNodeExpectNodeWillBeCreated() const { return create_node_count; }
196
197 // Returns true if this node would exist in the tree as of the last pending
198 // update that was processed, and the node has not been provided node data.
DoesNodeRequireInitui::PendingStructureChanges199 bool DoesNodeRequireInit() const { return node_exists && !last_known_data; }
200
201 // Keep track of the number of times the subtree rooted at this node
202 // will be destroyed.
203 // An example of when this count may be larger than 1 is if updates were
204 // merged together. A subtree may be [created,] destroyed, created, and
205 // destroyed again within the same |AXTreeUpdate|. The important takeaway here
206 // is that an update may request destruction of a subtree rooted at an
207 // AXID more than once, not that a specific subtree is being destroyed
208 // more than once.
209 int32_t destroy_subtree_count;
210
211 // Keep track of the number of times this node will be destroyed.
212 // An example of when this count may be larger than 1 is if updates were
213 // merged together. A node may be [created,] destroyed, created, and destroyed
214 // again within the same |AXTreeUpdate|. The important takeaway here is that
215 // an AXID may request destruction more than once, not that a specific node
216 // is being destroyed more than once.
217 int32_t destroy_node_count;
218
219 // Keep track of the number of times this node will be created.
220 // An example of when this count may be larger than 1 is if updates were
221 // merged together. A node may be [destroyed,] created, destroyed, and created
222 // again within the same |AXTreeUpdate|. The important takeaway here is that
223 // an AXID may request creation more than once, not that a specific node is
224 // being created more than once.
225 int32_t create_node_count;
226
227 // Keep track of whether this node exists in the tree as of the last pending
228 // update that was processed.
229 bool node_exists;
230
231 // Keep track of the parent id for this node as of the last pending
232 // update that was processed.
233 base::Optional<AXNode::AXID> parent_node_id;
234
235 // Keep track of the last known node data for this node.
236 // This will be null either when a node does not exist in the tree, or
237 // when the node is new and has not been initialized with node data yet.
238 // This is needed to determine what children have changed between pending
239 // updates.
240 const AXNodeData* last_known_data;
241 };
242
243 // Represents the different states when computing PendingStructureChanges
244 // required for tree Unserialize.
245 enum class AXTreePendingStructureStatus {
246 // PendingStructureChanges have not begun computation.
247 kNotStarted,
248 // PendingStructureChanges are currently being computed.
249 kComputing,
250 // All PendingStructureChanges have successfully been computed.
251 kComplete,
252 // An error occurred when computing pending changes.
253 kFailed,
254 };
255
256 // Intermediate state to keep track of during a tree update.
257 struct AXTreeUpdateState {
AXTreeUpdateStateui::AXTreeUpdateState258 explicit AXTreeUpdateState(const AXTree& tree)
259 : pending_update_status(AXTreePendingStructureStatus::kNotStarted),
260 root_will_be_created(false),
261 tree(tree) {}
262
263 // Returns whether this update removes |node|.
IsRemovedNodeui::AXTreeUpdateState264 bool IsRemovedNode(const AXNode* node) const {
265 return base::Contains(removed_node_ids, node->id());
266 }
267
268 // Returns whether this update creates a node marked by |node_id|.
IsCreatedNodeui::AXTreeUpdateState269 bool IsCreatedNode(AXNode::AXID node_id) const {
270 return base::Contains(new_node_ids, node_id);
271 }
272
273 // Returns whether this update creates |node|.
IsCreatedNodeui::AXTreeUpdateState274 bool IsCreatedNode(const AXNode* node) const {
275 return IsCreatedNode(node->id());
276 }
277
278 // Returns whether this update reparents |node|.
IsReparentedNodeui::AXTreeUpdateState279 bool IsReparentedNode(const AXNode* node) const {
280 DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
281 << "This method should not be called before pending changes have "
282 "finished computing.";
283 PendingStructureChanges* data = GetPendingStructureChanges(node->id());
284 if (!data)
285 return false;
286 // In order to know if the node will be reparented during the update,
287 // we check if either the node will be destroyed or has been destroyed at
288 // least once during the update.
289 // Since this method is only allowed to be called after calculating all
290 // pending structure changes, |node_exists| tells us if the node should
291 // exist after all updates have been applied.
292 return (data->DoesNodeExpectNodeWillBeDestroyed() || IsRemovedNode(node)) &&
293 data->node_exists;
294 }
295
296 // Returns true if the node should exist in the tree but doesn't have
297 // any node data yet.
DoesPendingNodeRequireInitui::AXTreeUpdateState298 bool DoesPendingNodeRequireInit(AXNode::AXID node_id) const {
299 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
300 << "This method should only be called while computing pending changes, "
301 "before updates are made to the tree.";
302 PendingStructureChanges* data = GetPendingStructureChanges(node_id);
303 return data && data->DoesNodeRequireInit();
304 }
305
306 // Returns the parent node id for the pending node.
GetParentIdForPendingNodeui::AXTreeUpdateState307 base::Optional<AXNode::AXID> GetParentIdForPendingNode(AXNode::AXID node_id) {
308 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
309 << "This method should only be called while computing pending changes, "
310 "before updates are made to the tree.";
311 PendingStructureChanges* data = GetOrCreatePendingStructureChanges(node_id);
312 DCHECK(!data->parent_node_id ||
313 ShouldPendingNodeExistInTree(*data->parent_node_id));
314 return data->parent_node_id;
315 }
316
317 // Returns true if this node should exist in the tree.
ShouldPendingNodeExistInTreeui::AXTreeUpdateState318 bool ShouldPendingNodeExistInTree(AXNode::AXID node_id) {
319 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
320 << "This method should only be called while computing pending changes, "
321 "before updates are made to the tree.";
322 return GetOrCreatePendingStructureChanges(node_id)->node_exists;
323 }
324
325 // Returns the last known node data for a pending node.
GetLastKnownPendingNodeDataui::AXTreeUpdateState326 const AXNodeData& GetLastKnownPendingNodeData(AXNode::AXID node_id) const {
327 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
328 << "This method should only be called while computing pending changes, "
329 "before updates are made to the tree.";
330 static base::NoDestructor<ui::AXNodeData> empty_data;
331 PendingStructureChanges* data = GetPendingStructureChanges(node_id);
332 return (data && data->last_known_data) ? *data->last_known_data
333 : *empty_data;
334 }
335
336 // Clear the last known pending data for |node_id|.
ClearLastKnownPendingNodeDataui::AXTreeUpdateState337 void ClearLastKnownPendingNodeData(AXNode::AXID node_id) {
338 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
339 << "This method should only be called while computing pending changes, "
340 "before updates are made to the tree.";
341 GetOrCreatePendingStructureChanges(node_id)->last_known_data = nullptr;
342 }
343
344 // Update the last known pending node data for |node_data.id|.
SetLastKnownPendingNodeDataui::AXTreeUpdateState345 void SetLastKnownPendingNodeData(const AXNodeData* node_data) {
346 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
347 << "This method should only be called while computing pending changes, "
348 "before updates are made to the tree.";
349 GetOrCreatePendingStructureChanges(node_data->id)->last_known_data =
350 node_data;
351 }
352
353 // Returns the number of times the update is expected to destroy a
354 // subtree rooted at |node_id|.
GetPendingDestroySubtreeCountui::AXTreeUpdateState355 int32_t GetPendingDestroySubtreeCount(AXNode::AXID node_id) const {
356 DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
357 << "This method should not be called before pending changes have "
358 "finished computing.";
359 if (PendingStructureChanges* data = GetPendingStructureChanges(node_id))
360 return data->destroy_subtree_count;
361 return 0;
362 }
363
364 // Increments the number of times the update is expected to
365 // destroy a subtree rooted at |node_id|.
366 // Returns true on success, false on failure when the node will not exist.
IncrementPendingDestroySubtreeCountui::AXTreeUpdateState367 bool IncrementPendingDestroySubtreeCount(AXNode::AXID node_id) {
368 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
369 << "This method should only be called while computing pending changes, "
370 "before updates are made to the tree.";
371 PendingStructureChanges* data = GetOrCreatePendingStructureChanges(node_id);
372 if (!data->node_exists)
373 return false;
374
375 ++data->destroy_subtree_count;
376 return true;
377 }
378
379 // Decrements the number of times the update is expected to
380 // destroy a subtree rooted at |node_id|.
DecrementPendingDestroySubtreeCountui::AXTreeUpdateState381 void DecrementPendingDestroySubtreeCount(AXNode::AXID node_id) {
382 DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
383 << "This method should not be called before pending changes have "
384 "finished computing.";
385 if (PendingStructureChanges* data = GetPendingStructureChanges(node_id)) {
386 DCHECK_GT(data->destroy_subtree_count, 0);
387 --data->destroy_subtree_count;
388 }
389 }
390
391 // Returns the number of times the update is expected to destroy
392 // a node with |node_id|.
GetPendingDestroyNodeCountui::AXTreeUpdateState393 int32_t GetPendingDestroyNodeCount(AXNode::AXID node_id) const {
394 DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
395 << "This method should not be called before pending changes have "
396 "finished computing.";
397 if (PendingStructureChanges* data = GetPendingStructureChanges(node_id))
398 return data->destroy_node_count;
399 return 0;
400 }
401
402 // Increments the number of times the update is expected to
403 // destroy a node with |node_id|.
404 // Returns true on success, false on failure when the node will not exist.
IncrementPendingDestroyNodeCountui::AXTreeUpdateState405 bool IncrementPendingDestroyNodeCount(AXNode::AXID node_id) {
406 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
407 << "This method should only be called while computing pending changes, "
408 "before updates are made to the tree.";
409 PendingStructureChanges* data = GetOrCreatePendingStructureChanges(node_id);
410 if (!data->node_exists)
411 return false;
412
413 ++data->destroy_node_count;
414 data->node_exists = false;
415 data->last_known_data = nullptr;
416 data->parent_node_id = base::nullopt;
417 if (pending_root_id == node_id)
418 pending_root_id = base::nullopt;
419 return true;
420 }
421
422 // Decrements the number of times the update is expected to
423 // destroy a node with |node_id|.
DecrementPendingDestroyNodeCountui::AXTreeUpdateState424 void DecrementPendingDestroyNodeCount(AXNode::AXID node_id) {
425 DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
426 << "This method should not be called before pending changes have "
427 "finished computing.";
428 if (PendingStructureChanges* data = GetPendingStructureChanges(node_id)) {
429 DCHECK_GT(data->destroy_node_count, 0);
430 --data->destroy_node_count;
431 }
432 }
433
434 // Returns the number of times the update is expected to create
435 // a node with |node_id|.
GetPendingCreateNodeCountui::AXTreeUpdateState436 int32_t GetPendingCreateNodeCount(AXNode::AXID node_id) const {
437 DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
438 << "This method should not be called before pending changes have "
439 "finished computing.";
440 if (PendingStructureChanges* data = GetPendingStructureChanges(node_id))
441 return data->create_node_count;
442 return 0;
443 }
444
445 // Increments the number of times the update is expected to
446 // create a node with |node_id|.
447 // Returns true on success, false on failure when the node will already exist.
IncrementPendingCreateNodeCountui::AXTreeUpdateState448 bool IncrementPendingCreateNodeCount(
449 AXNode::AXID node_id,
450 base::Optional<AXNode::AXID> parent_node_id) {
451 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
452 << "This method should only be called while computing pending changes, "
453 "before updates are made to the tree.";
454 PendingStructureChanges* data = GetOrCreatePendingStructureChanges(node_id);
455 if (data->node_exists)
456 return false;
457
458 ++data->create_node_count;
459 data->node_exists = true;
460 data->parent_node_id = parent_node_id;
461 return true;
462 }
463
464 // Decrements the number of times the update is expected to
465 // create a node with |node_id|.
DecrementPendingCreateNodeCountui::AXTreeUpdateState466 void DecrementPendingCreateNodeCount(AXNode::AXID node_id) {
467 DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
468 << "This method should not be called before pending changes have "
469 "finished computing.";
470 if (PendingStructureChanges* data = GetPendingStructureChanges(node_id)) {
471 DCHECK_GT(data->create_node_count, 0);
472 --data->create_node_count;
473 }
474 }
475
476 // Returns whether this update must invalidate the unignored cached
477 // values for |node_id|.
InvalidatesUnignoredCachedValuesui::AXTreeUpdateState478 bool InvalidatesUnignoredCachedValues(AXNode::AXID node_id) {
479 return base::Contains(invalidate_unignored_cached_values_ids, node_id);
480 }
481
482 // Adds the parent of |node_id| to the list of nodes to invalidate unignored
483 // cached values.
InvalidateParentNodeUnignoredCacheValuesui::AXTreeUpdateState484 void InvalidateParentNodeUnignoredCacheValues(AXNode::AXID node_id) {
485 DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
486 << "This method should only be called while computing pending changes, "
487 "before updates are made to the tree.";
488 base::Optional<AXNode::AXID> parent_node_id =
489 GetParentIdForPendingNode(node_id);
490 if (parent_node_id) {
491 invalidate_unignored_cached_values_ids.insert(*parent_node_id);
492 }
493 }
494
495 // Indicates the status for calculating what changes will occur during
496 // an update before the update applies changes.
497 AXTreePendingStructureStatus pending_update_status;
498
499 // Keeps track of the root node id when calculating what changes will occur
500 // during an update before the update applies changes.
501 base::Optional<AXNode::AXID> pending_root_id;
502
503 // Keeps track of whether the root node will need to be created as a new node.
504 // This may occur either when the root node does not exist before applying
505 // updates to the tree (new tree), or if the root is the |node_id_to_clear|
506 // and will be destroyed before applying AXNodeData updates to the tree.
507 bool root_will_be_created;
508
509 // During an update, this keeps track of all nodes that have been
510 // implicitly referenced as part of this update, but haven't been
511 // updated yet. It's an error if there are any pending nodes at the
512 // end of Unserialize.
513 std::set<AXNode::AXID> pending_nodes;
514
515 // Keeps track of nodes whose cached unignored child count, or unignored
516 // index in parent may have changed, and must be updated.
517 std::set<AXNode::AXID> invalidate_unignored_cached_values_ids;
518
519 // Keeps track of nodes that have changed their node data.
520 std::set<AXNode::AXID> node_data_changed_ids;
521
522 // Keeps track of new nodes created during this update.
523 std::set<AXNode::AXID> new_node_ids;
524
525 // Keeps track of any nodes removed. Nodes are removed when their AXID no
526 // longer exist in the parent |child_ids| list, or the node is part of to the
527 // subtree of the AXID that was explicitally cleared with |node_id_to_clear|.
528 // Used to identify re-parented nodes. A re-parented occurs when any AXID
529 // is first removed from the tree then added to the tree again.
530 std::set<AXNode::AXID> removed_node_ids;
531
532 // Maps between a node id and its pending update information.
533 std::map<AXNode::AXID, std::unique_ptr<PendingStructureChanges>>
534 node_id_to_pending_data;
535
536 // Maps between a node id and the data it owned before being updated.
537 // We need to keep this around in order to correctly fire post-update events.
538 std::map<AXNode::AXID, AXNodeData> old_node_id_to_data;
539
540 // Optional copy of the old tree data, only populated when the tree
541 // data has changed.
542 base::Optional<AXTreeData> old_tree_data;
543
544 private:
GetPendingStructureChangesui::AXTreeUpdateState545 PendingStructureChanges* GetPendingStructureChanges(
546 AXNode::AXID node_id) const {
547 auto iter = node_id_to_pending_data.find(node_id);
548 return (iter != node_id_to_pending_data.cend()) ? iter->second.get()
549 : nullptr;
550 }
551
GetOrCreatePendingStructureChangesui::AXTreeUpdateState552 PendingStructureChanges* GetOrCreatePendingStructureChanges(
553 AXNode::AXID node_id) {
554 auto iter = node_id_to_pending_data.find(node_id);
555 if (iter == node_id_to_pending_data.cend()) {
556 const AXNode* node = tree.GetFromId(node_id);
557 iter = node_id_to_pending_data
558 .emplace(std::make_pair(
559 node_id, std::make_unique<PendingStructureChanges>(node)))
560 .first;
561 }
562 return iter->second.get();
563 }
564
565 // We need to hold onto a reference to the AXTree so that we can
566 // lazily initialize |PendingStructureChanges| objects.
567 const AXTree& tree;
568 };
569
570 struct AXTree::OrderedSetContent {
OrderedSetContentui::AXTree::OrderedSetContent571 explicit OrderedSetContent(const AXNode* ordered_set = nullptr)
572 : ordered_set_(ordered_set) {}
573 ~OrderedSetContent() = default;
574
575 std::vector<const AXNode*> set_items_;
576
577 // Some ordered set items may not be associated with an ordered set.
578 const AXNode* ordered_set_;
579 };
580
581 struct AXTree::OrderedSetItemsMap {
582 OrderedSetItemsMap() = default;
583 ~OrderedSetItemsMap() = default;
584
585 // Check if a particular hierarchical level exists in this map.
HierarchicalLevelExistsui::AXTree::OrderedSetItemsMap586 bool HierarchicalLevelExists(base::Optional<int> level) {
587 if (items_map_.find(level) == items_map_.end())
588 return false;
589 return true;
590 }
591
592 // Add the OrderedSetContent to the corresponding hierarchical level in the
593 // map.
Addui::AXTree::OrderedSetItemsMap594 void Add(base::Optional<int> level,
595 const OrderedSetContent& ordered_set_content) {
596 if (!HierarchicalLevelExists(level))
597 items_map_[level] = std::vector<OrderedSetContent>();
598
599 items_map_[level].push_back(ordered_set_content);
600 }
601
602 // Add an ordered set item to the OrderedSetItemsMap given its hierarchical
603 // level. We always want to append the item to the last OrderedSetContent of
604 // that hierarchical level, due to the following:
605 // - The last OrderedSetContent on any level of the items map is in progress
606 // of being populated.
607 // - All other OrderedSetContent other than the last one on a level
608 // represents a complete ordered set and should not be modified.
AddItemToBackui::AXTree::OrderedSetItemsMap609 void AddItemToBack(base::Optional<int> level, const AXNode* item) {
610 if (!HierarchicalLevelExists(level))
611 return;
612
613 std::vector<OrderedSetContent>& sets_list = items_map_[level];
614 if (!sets_list.empty()) {
615 OrderedSetContent& ordered_set_content = sets_list.back();
616 ordered_set_content.set_items_.push_back(item);
617 }
618 }
619
620 // Retrieve the first OrderedSetContent of the OrderedSetItemsMap.
GetFirstOrderedSetContentui::AXTree::OrderedSetItemsMap621 OrderedSetContent* GetFirstOrderedSetContent() {
622 if (items_map_.empty())
623 return nullptr;
624
625 std::vector<OrderedSetContent>& sets_list = items_map_.begin()->second;
626 if (sets_list.empty())
627 return nullptr;
628
629 return &(sets_list.front());
630 }
631
632 // Clears all the content in the map.
Clearui::AXTree::OrderedSetItemsMap633 void Clear() { items_map_.clear(); }
634
635 // Maps a hierarchical level to a list of OrderedSetContent.
636 std::map<base::Optional<int32_t>, std::vector<OrderedSetContent>> items_map_;
637 };
638
AXTree()639 AXTree::AXTree() {
640 AXNodeData root;
641 root.id = AXNode::kInvalidAXID;
642
643 AXTreeUpdate initial_state;
644 initial_state.root_id = AXNode::kInvalidAXID;
645 initial_state.nodes.push_back(root);
646 CHECK(Unserialize(initial_state)) << error();
647 // TODO(chrishall): should language_detection_manager be a member or pointer?
648 // TODO(chrishall): do we want to initialize all the time, on demand, or only
649 // when feature flag is set?
650 DCHECK(!language_detection_manager);
651 language_detection_manager =
652 std::make_unique<AXLanguageDetectionManager>(this);
653 }
654
AXTree(const AXTreeUpdate & initial_state)655 AXTree::AXTree(const AXTreeUpdate& initial_state) {
656 CHECK(Unserialize(initial_state)) << error();
657 DCHECK(!language_detection_manager);
658 language_detection_manager =
659 std::make_unique<AXLanguageDetectionManager>(this);
660 }
661
~AXTree()662 AXTree::~AXTree() {
663 Destroy();
664 }
665
AddObserver(AXTreeObserver * observer)666 void AXTree::AddObserver(AXTreeObserver* observer) {
667 observers_.AddObserver(observer);
668 }
669
HasObserver(AXTreeObserver * observer)670 bool AXTree::HasObserver(AXTreeObserver* observer) {
671 return observers_.HasObserver(observer);
672 }
673
RemoveObserver(AXTreeObserver * observer)674 void AXTree::RemoveObserver(AXTreeObserver* observer) {
675 observers_.RemoveObserver(observer);
676 }
677
GetAXTreeID() const678 AXTreeID AXTree::GetAXTreeID() const {
679 return data().tree_id;
680 }
681
GetFromId(int32_t id) const682 AXNode* AXTree::GetFromId(int32_t id) const {
683 auto iter = id_map_.find(id);
684 return iter != id_map_.end() ? iter->second : nullptr;
685 }
686
Destroy()687 void AXTree::Destroy() {
688 table_info_map_.clear();
689 if (root_) {
690 RecursivelyNotifyNodeDeletedForTreeTeardown(root_);
691 base::AutoReset<bool> update_state_resetter(&tree_update_in_progress_,
692 true);
693 DestroyNodeAndSubtree(root_, nullptr);
694 root_ = nullptr;
695 }
696 }
697
UpdateData(const AXTreeData & new_data)698 void AXTree::UpdateData(const AXTreeData& new_data) {
699 if (data_ == new_data)
700 return;
701
702 AXTreeData old_data = data_;
703 data_ = new_data;
704 for (AXTreeObserver& observer : observers_)
705 observer.OnTreeDataChanged(this, old_data, new_data);
706 }
707
RelativeToTreeBoundsInternal(const AXNode * node,gfx::RectF bounds,bool * offscreen,bool clip_bounds,bool allow_recursion) const708 gfx::RectF AXTree::RelativeToTreeBoundsInternal(const AXNode* node,
709 gfx::RectF bounds,
710 bool* offscreen,
711 bool clip_bounds,
712 bool allow_recursion) const {
713 // If |bounds| is uninitialized, which is not the same as empty,
714 // start with the node bounds.
715 if (bounds.width() == 0 && bounds.height() == 0) {
716 bounds = node->data().relative_bounds.bounds;
717
718 // If the node bounds is empty (either width or height is zero),
719 // try to compute good bounds from the children.
720 // If a tree update is in progress, skip this step as children may be in a
721 // bad state.
722 if (bounds.IsEmpty() && !GetTreeUpdateInProgressState() &&
723 allow_recursion) {
724 for (size_t i = 0; i < node->children().size(); i++) {
725 ui::AXNode* child = node->children()[i];
726
727 bool ignore_offscreen;
728 gfx::RectF child_bounds = RelativeToTreeBoundsInternal(
729 child, gfx::RectF(), &ignore_offscreen, clip_bounds,
730 /* allow_recursion = */ false);
731 bounds.Union(child_bounds);
732 }
733 if (bounds.width() > 0 && bounds.height() > 0) {
734 return bounds;
735 }
736 }
737 } else {
738 bounds.Offset(node->data().relative_bounds.bounds.x(),
739 node->data().relative_bounds.bounds.y());
740 }
741
742 const AXNode* original_node = node;
743 while (node != nullptr) {
744 if (node->data().relative_bounds.transform)
745 node->data().relative_bounds.transform->TransformRect(&bounds);
746 // Apply any transforms and offsets for each node and then walk up to
747 // its offset container. If no offset container is specified, coordinates
748 // are relative to the root node.
749 const AXNode* container =
750 GetFromId(node->data().relative_bounds.offset_container_id);
751 if (!container && container != root())
752 container = root();
753 if (!container || container == node)
754 break;
755
756 gfx::RectF container_bounds = container->data().relative_bounds.bounds;
757 bounds.Offset(container_bounds.x(), container_bounds.y());
758
759 int scroll_x = 0;
760 int scroll_y = 0;
761 if (container->data().GetIntAttribute(ax::mojom::IntAttribute::kScrollX,
762 &scroll_x) &&
763 container->data().GetIntAttribute(ax::mojom::IntAttribute::kScrollY,
764 &scroll_y)) {
765 bounds.Offset(-scroll_x, -scroll_y);
766 }
767
768 // Get the intersection between the bounds and the container.
769 gfx::RectF intersection = bounds;
770 intersection.Intersect(container_bounds);
771
772 // Calculate the clipped bounds to determine offscreen state.
773 gfx::RectF clipped = bounds;
774 // If this node has the kClipsChildren attribute set, clip the rect to fit.
775 if (container->data().GetBoolAttribute(
776 ax::mojom::BoolAttribute::kClipsChildren)) {
777 if (!intersection.IsEmpty()) {
778 // We can simply clip it to the container.
779 clipped = intersection;
780 } else {
781 // Totally offscreen. Find the nearest edge or corner.
782 // Make the minimum dimension 1 instead of 0.
783 if (clipped.x() >= container_bounds.width()) {
784 clipped.set_x(container_bounds.right() - 1);
785 clipped.set_width(1);
786 } else if (clipped.x() + clipped.width() <= 0) {
787 clipped.set_x(container_bounds.x());
788 clipped.set_width(1);
789 }
790 if (clipped.y() >= container_bounds.height()) {
791 clipped.set_y(container_bounds.bottom() - 1);
792 clipped.set_height(1);
793 } else if (clipped.y() + clipped.height() <= 0) {
794 clipped.set_y(container_bounds.y());
795 clipped.set_height(1);
796 }
797 }
798 }
799
800 if (clip_bounds)
801 bounds = clipped;
802
803 if (container->data().GetBoolAttribute(
804 ax::mojom::BoolAttribute::kClipsChildren) &&
805 intersection.IsEmpty() && !clipped.IsEmpty()) {
806 // If it is offscreen with respect to its parent, and the node itself is
807 // not empty, label it offscreen.
808 // Here we are extending the definition of offscreen to include elements
809 // that are clipped by their parents in addition to those clipped by
810 // the rootWebArea.
811 // No need to update |offscreen| if |intersection| is not empty, because
812 // it should be false by default.
813 if (offscreen != nullptr)
814 *offscreen |= true;
815 }
816
817 node = container;
818 }
819
820 // If we don't have any size yet, try to adjust the bounds to fill the
821 // nearest ancestor that does have bounds.
822 //
823 // The rationale is that it's not useful to the user for an object to
824 // have no width or height and it's probably a bug; it's better to
825 // reflect the bounds of the nearest ancestor rather than a 0x0 box.
826 // Tag this node as 'offscreen' because it has no true size, just a
827 // size inherited from the ancestor.
828 if (bounds.width() == 0 && bounds.height() == 0) {
829 const AXNode* ancestor = original_node->parent();
830 gfx::RectF ancestor_bounds;
831 while (ancestor) {
832 ancestor_bounds = ancestor->data().relative_bounds.bounds;
833 if (ancestor_bounds.width() > 0 || ancestor_bounds.height() > 0)
834 break;
835 ancestor = ancestor->parent();
836 }
837
838 if (ancestor && allow_recursion) {
839 bool ignore_offscreen;
840 bool allow_recursion = false;
841 ancestor_bounds = RelativeToTreeBoundsInternal(
842 ancestor, gfx::RectF(), &ignore_offscreen, clip_bounds,
843 allow_recursion);
844
845 gfx::RectF original_bounds = original_node->data().relative_bounds.bounds;
846 if (original_bounds.x() == 0 && original_bounds.y() == 0) {
847 bounds = ancestor_bounds;
848 } else {
849 bounds.set_width(std::max(0.0f, ancestor_bounds.right() - bounds.x()));
850 bounds.set_height(
851 std::max(0.0f, ancestor_bounds.bottom() - bounds.y()));
852 }
853 if (offscreen != nullptr)
854 *offscreen |= true;
855 }
856 }
857
858 return bounds;
859 }
860
RelativeToTreeBounds(const AXNode * node,gfx::RectF bounds,bool * offscreen,bool clip_bounds) const861 gfx::RectF AXTree::RelativeToTreeBounds(const AXNode* node,
862 gfx::RectF bounds,
863 bool* offscreen,
864 bool clip_bounds) const {
865 bool allow_recursion = true;
866 return RelativeToTreeBoundsInternal(node, bounds, offscreen, clip_bounds,
867 allow_recursion);
868 }
869
GetTreeBounds(const AXNode * node,bool * offscreen,bool clip_bounds) const870 gfx::RectF AXTree::GetTreeBounds(const AXNode* node,
871 bool* offscreen,
872 bool clip_bounds) const {
873 return RelativeToTreeBounds(node, gfx::RectF(), offscreen, clip_bounds);
874 }
875
GetReverseRelations(ax::mojom::IntAttribute attr,int32_t dst_id) const876 std::set<int32_t> AXTree::GetReverseRelations(ax::mojom::IntAttribute attr,
877 int32_t dst_id) const {
878 DCHECK(IsNodeIdIntAttribute(attr));
879
880 // Conceptually, this is the "const" version of:
881 // return int_reverse_relations_[attr][dst_id];
882 const auto& attr_relations = int_reverse_relations_.find(attr);
883 if (attr_relations != int_reverse_relations_.end()) {
884 const auto& result = attr_relations->second.find(dst_id);
885 if (result != attr_relations->second.end())
886 return result->second;
887 }
888 return std::set<int32_t>();
889 }
890
GetReverseRelations(ax::mojom::IntListAttribute attr,int32_t dst_id) const891 std::set<int32_t> AXTree::GetReverseRelations(ax::mojom::IntListAttribute attr,
892 int32_t dst_id) const {
893 DCHECK(IsNodeIdIntListAttribute(attr));
894
895 // Conceptually, this is the "const" version of:
896 // return intlist_reverse_relations_[attr][dst_id];
897 const auto& attr_relations = intlist_reverse_relations_.find(attr);
898 if (attr_relations != intlist_reverse_relations_.end()) {
899 const auto& result = attr_relations->second.find(dst_id);
900 if (result != attr_relations->second.end())
901 return result->second;
902 }
903 return std::set<int32_t>();
904 }
905
GetNodeIdsForChildTreeId(AXTreeID child_tree_id) const906 std::set<int32_t> AXTree::GetNodeIdsForChildTreeId(
907 AXTreeID child_tree_id) const {
908 // Conceptually, this is the "const" version of:
909 // return child_tree_id_reverse_map_[child_tree_id];
910 const auto& result = child_tree_id_reverse_map_.find(child_tree_id);
911 if (result != child_tree_id_reverse_map_.end())
912 return result->second;
913 return std::set<int32_t>();
914 }
915
GetAllChildTreeIds() const916 const std::set<AXTreeID> AXTree::GetAllChildTreeIds() const {
917 std::set<AXTreeID> result;
918 for (auto entry : child_tree_id_reverse_map_)
919 result.insert(entry.first);
920 return result;
921 }
922
Unserialize(const AXTreeUpdate & update)923 bool AXTree::Unserialize(const AXTreeUpdate& update) {
924 AXTreeUpdateState update_state(*this);
925 const AXNode::AXID old_root_id = root_ ? root_->id() : AXNode::kInvalidAXID;
926
927 // Accumulates the work that will be required to update the AXTree.
928 // This allows us to notify observers of structure changes when the
929 // tree is still in a stable and unchanged state.
930 if (!ComputePendingChanges(update, &update_state))
931 return false;
932
933 // Notify observers of subtrees and nodes that are about to be destroyed or
934 // reparented, this must be done before applying any updates to the tree.
935 for (auto&& pair : update_state.node_id_to_pending_data) {
936 const AXNode::AXID node_id = pair.first;
937 const std::unique_ptr<PendingStructureChanges>& data = pair.second;
938 if (data->DoesNodeExpectSubtreeOrNodeWillBeDestroyed()) {
939 if (AXNode* node = GetFromId(node_id)) {
940 if (data->DoesNodeExpectSubtreeWillBeDestroyed())
941 NotifySubtreeWillBeReparentedOrDeleted(node, &update_state);
942 if (data->DoesNodeExpectNodeWillBeDestroyed())
943 NotifyNodeWillBeReparentedOrDeleted(node, &update_state);
944 }
945 }
946 }
947
948 // Notify observers of nodes that are about to change their data.
949 // This must be done before applying any updates to the tree.
950 // This is iterating in reverse order so that we only notify once per node id,
951 // and that we only notify the initial node data against the final node data,
952 // unless the node is a new root.
953 std::set<int32_t> notified_node_data_will_change;
954 for (size_t i = update.nodes.size(); i-- > 0;) {
955 const AXNodeData& new_data = update.nodes[i];
956 const bool is_new_root =
957 update_state.root_will_be_created && new_data.id == update.root_id;
958 if (!is_new_root) {
959 AXNode* node = GetFromId(new_data.id);
960 if (node && notified_node_data_will_change.insert(new_data.id).second)
961 NotifyNodeDataWillChange(node->data(), new_data);
962 }
963 }
964
965 // Now that we have finished sending events for changes that will happen,
966 // set update state to true. |tree_update_in_progress_| gets set back to
967 // false whenever this function exits.
968 base::AutoReset<bool> update_state_resetter(&tree_update_in_progress_, true);
969
970 // Handle |node_id_to_clear| before applying ordinary node updates.
971 // We distinguish between updating the root, e.g. changing its children or
972 // some of its attributes, or replacing the root completely. If the root is
973 // being updated, update.node_id_to_clear should hold the current root's ID.
974 // Otherwise if the root is being replaced, update.root_id should hold the ID
975 // of the new root.
976 bool root_updated = false;
977 if (update.node_id_to_clear != AXNode::kInvalidAXID) {
978 if (AXNode* cleared_node = GetFromId(update.node_id_to_clear)) {
979 DCHECK(root_);
980 if (cleared_node == root_) {
981 // Only destroy the root if the root was replaced and not if it's simply
982 // updated. To figure out if the root was simply updated, we compare
983 // the ID of the new root with the existing root ID.
984 if (update.root_id != old_root_id) {
985 // Clear root_ before calling DestroySubtree so that root_ doesn't
986 // ever point to an invalid node.
987 AXNode* old_root = root_;
988 root_ = nullptr;
989 DestroySubtree(old_root, &update_state);
990 } else {
991 // If the root has simply been updated, we treat it like an update to
992 // any other node.
993 root_updated = true;
994 }
995 }
996
997 // If the tree doesn't exists any more because the root has just been
998 // replaced, there is nothing more to clear.
999 if (root_) {
1000 for (auto* child : cleared_node->children())
1001 DestroySubtree(child, &update_state);
1002 std::vector<AXNode*> children;
1003 cleared_node->SwapChildren(&children);
1004 update_state.pending_nodes.insert(cleared_node->id());
1005 }
1006 }
1007 }
1008
1009 DCHECK_EQ(!GetFromId(update.root_id), update_state.root_will_be_created);
1010
1011 // Update the tree data, do not call |UpdateData| since we want to defer
1012 // the |OnTreeDataChanged| event until after the tree has finished updating.
1013 if (update.has_tree_data && data_ != update.tree_data) {
1014 update_state.old_tree_data = data_;
1015 data_ = update.tree_data;
1016 }
1017
1018 // Update all of the nodes in the update.
1019 for (size_t i = 0; i < update.nodes.size(); ++i) {
1020 const bool is_new_root = update_state.root_will_be_created &&
1021 update.nodes[i].id == update.root_id;
1022 if (!UpdateNode(update.nodes[i], is_new_root, &update_state))
1023 return false;
1024 }
1025
1026 if (!root_) {
1027 error_ = "Tree has no root.";
1028 return false;
1029 }
1030
1031 if (!ValidatePendingChangesComplete(update_state))
1032 return false;
1033
1034 // Look for changes to nodes that are a descendant of a table,
1035 // and invalidate their table info if so. We have to walk up the
1036 // ancestry of every node that was updated potentially, so keep track of
1037 // ids that were checked to eliminate duplicate work.
1038 std::set<int32_t> table_ids_checked;
1039 for (size_t i = 0; i < update.nodes.size(); ++i) {
1040 AXNode* node = GetFromId(update.nodes[i].id);
1041 while (node) {
1042 if (table_ids_checked.find(node->id()) != table_ids_checked.end())
1043 break;
1044 // Remove any table infos.
1045 const auto& table_info_entry = table_info_map_.find(node->id());
1046 if (table_info_entry != table_info_map_.end())
1047 table_info_entry->second->Invalidate();
1048 table_ids_checked.insert(node->id());
1049 node = node->parent();
1050 }
1051 }
1052
1053 // Clears |node_set_size_pos_in_set_info_map_|
1054 node_set_size_pos_in_set_info_map_.clear();
1055
1056 std::vector<AXTreeObserver::Change> changes;
1057 changes.reserve(update.nodes.size());
1058 std::set<AXNode::AXID> visited_observer_changes;
1059 for (size_t i = 0; i < update.nodes.size(); ++i) {
1060 AXNode* node = GetFromId(update.nodes[i].id);
1061 if (!node || !visited_observer_changes.emplace(update.nodes[i].id).second)
1062 continue;
1063
1064 bool is_new_node = update_state.IsCreatedNode(node);
1065 bool is_reparented_node = update_state.IsReparentedNode(node);
1066
1067 AXTreeObserver::ChangeType change = AXTreeObserver::NODE_CHANGED;
1068 if (is_new_node) {
1069 if (is_reparented_node) {
1070 // A reparented subtree is any new node whose parent either doesn't
1071 // exist, or whose parent is not new.
1072 // Note that we also need to check for the special case when we update
1073 // the root without replacing it.
1074 bool is_subtree = !node->parent() ||
1075 !update_state.IsCreatedNode(node->parent()) ||
1076 (node->parent() == root_ && root_updated);
1077 change = is_subtree ? AXTreeObserver::SUBTREE_REPARENTED
1078 : AXTreeObserver::NODE_REPARENTED;
1079 } else {
1080 // A new subtree is any new node whose parent is either not new, or
1081 // whose parent happens to be new only because it has been reparented.
1082 // Note that we also need to check for the special case when we update
1083 // the root without replacing it.
1084 bool is_subtree = !node->parent() ||
1085 !update_state.IsCreatedNode(node->parent()) ||
1086 update_state.IsRemovedNode(node->parent()) ||
1087 (node->parent() == root_ && root_updated);
1088 change = is_subtree ? AXTreeObserver::SUBTREE_CREATED
1089 : AXTreeObserver::NODE_CREATED;
1090 }
1091 }
1092 changes.push_back(AXTreeObserver::Change(node, change));
1093 }
1094
1095 // Update the unignored cached values as necessary, ensuring that we only
1096 // update once for each unignored node.
1097 // If the node is ignored, we must update from an unignored ancestor.
1098 std::set<AXNode::AXID> updated_unignored_cached_values_ids;
1099 for (AXNode::AXID node_id :
1100 update_state.invalidate_unignored_cached_values_ids) {
1101 AXNode* node = GetFromId(node_id);
1102 while (node && node->data().IsIgnored())
1103 node = node->parent();
1104 if (node && updated_unignored_cached_values_ids.insert(node->id()).second)
1105 node->UpdateUnignoredCachedValues();
1106 }
1107
1108 // Tree is no longer updating.
1109 SetTreeUpdateInProgressState(false);
1110
1111 // Now that the tree is stable and its nodes have been updated, notify if
1112 // the tree data changed. We must do this after updating nodes in case the
1113 // root has been replaced, so observers have the most up-to-date information.
1114 if (update_state.old_tree_data) {
1115 for (AXTreeObserver& observer : observers_)
1116 observer.OnTreeDataChanged(this, *update_state.old_tree_data, data_);
1117 }
1118
1119 // Now that the unignored cached values are up to date, update observers to
1120 // the nodes that were deleted from the tree but not reparented.
1121 for (AXNode::AXID node_id : update_state.removed_node_ids) {
1122 if (!update_state.IsCreatedNode(node_id))
1123 NotifyNodeHasBeenDeleted(node_id);
1124 }
1125
1126 // Now that the unignored cached values are up to date, update observers to
1127 // new nodes in the tree.
1128 for (AXNode::AXID node_id : update_state.new_node_ids)
1129 NotifyNodeHasBeenReparentedOrCreated(GetFromId(node_id), &update_state);
1130
1131 // Now that the unignored cached values are up to date, update observers to
1132 // node changes.
1133 for (AXNode::AXID node_data_changed_id : update_state.node_data_changed_ids) {
1134 AXNode* node = GetFromId(node_data_changed_id);
1135 DCHECK(node);
1136
1137 // If the node exists and is in the old data map, then the node data
1138 // may have changed unless this is a new root.
1139 const bool is_new_root = update_state.root_will_be_created &&
1140 node_data_changed_id == update.root_id;
1141 if (!is_new_root) {
1142 auto it = update_state.old_node_id_to_data.find(node_data_changed_id);
1143 if (it != update_state.old_node_id_to_data.end()) {
1144 const AXNodeData& old_node_data = it->second;
1145 NotifyNodeDataHasBeenChanged(node, old_node_data, node->data());
1146 }
1147 }
1148
1149 // |OnNodeChanged| should be fired for all nodes that have been updated.
1150 for (AXTreeObserver& observer : observers_)
1151 observer.OnNodeChanged(this, node);
1152 }
1153
1154 for (AXTreeObserver& observer : observers_)
1155 observer.OnAtomicUpdateFinished(this, root_->id() != old_root_id, changes);
1156
1157 return true;
1158 }
1159
GetTableInfo(const AXNode * const_table_node) const1160 AXTableInfo* AXTree::GetTableInfo(const AXNode* const_table_node) const {
1161 DCHECK(!GetTreeUpdateInProgressState());
1162 // Note: the const_casts are here because we want this function to be able
1163 // to be called from a const virtual function on AXNode. AXTableInfo is
1164 // computed on demand and cached, but that's an implementation detail
1165 // we want to hide from users of this API.
1166 AXNode* table_node = const_cast<AXNode*>(const_table_node);
1167 AXTree* tree = const_cast<AXTree*>(this);
1168
1169 DCHECK(table_node);
1170 const auto& cached = table_info_map_.find(table_node->id());
1171 if (cached != table_info_map_.end()) {
1172 // Get existing table info, and update if invalid because the
1173 // tree has changed since the last time we accessed it.
1174 AXTableInfo* table_info = cached->second.get();
1175 if (!table_info->valid()) {
1176 if (!table_info->Update()) {
1177 // If Update() returned false, this is no longer a valid table.
1178 // Remove it from the map.
1179 table_info_map_.erase(table_node->id());
1180 return nullptr;
1181 }
1182 }
1183 return table_info;
1184 }
1185
1186 AXTableInfo* table_info = AXTableInfo::Create(tree, table_node);
1187 if (!table_info)
1188 return nullptr;
1189
1190 table_info_map_[table_node->id()] = base::WrapUnique<AXTableInfo>(table_info);
1191 return table_info;
1192 }
1193
ToString() const1194 std::string AXTree::ToString() const {
1195 return "AXTree" + data_.ToString() + "\n" + TreeToStringHelper(root_, 0);
1196 }
1197
CreateNode(AXNode * parent,AXNode::AXID id,size_t index_in_parent,AXTreeUpdateState * update_state)1198 AXNode* AXTree::CreateNode(AXNode* parent,
1199 AXNode::AXID id,
1200 size_t index_in_parent,
1201 AXTreeUpdateState* update_state) {
1202 DCHECK(GetTreeUpdateInProgressState());
1203 // |update_state| must already contain information about all of the expected
1204 // changes and invalidations to apply. If any of these are missing, observers
1205 // may not be notified of changes.
1206 DCHECK(!GetFromId(id));
1207 DCHECK_GT(update_state->GetPendingCreateNodeCount(id), 0);
1208 DCHECK(update_state->InvalidatesUnignoredCachedValues(id));
1209 DCHECK(!parent ||
1210 update_state->InvalidatesUnignoredCachedValues(parent->id()));
1211 update_state->DecrementPendingCreateNodeCount(id);
1212 update_state->new_node_ids.insert(id);
1213 // If this node is the root, use the given index_in_parent as the unignored
1214 // index in parent to provide consistency with index_in_parent.
1215 AXNode* new_node = new AXNode(this, parent, id, index_in_parent,
1216 parent ? 0 : index_in_parent);
1217 id_map_[new_node->id()] = new_node;
1218 return new_node;
1219 }
1220
ComputePendingChanges(const AXTreeUpdate & update,AXTreeUpdateState * update_state)1221 bool AXTree::ComputePendingChanges(const AXTreeUpdate& update,
1222 AXTreeUpdateState* update_state) {
1223 DCHECK_EQ(AXTreePendingStructureStatus::kNotStarted,
1224 update_state->pending_update_status)
1225 << "Pending changes have already started being computed.";
1226 update_state->pending_update_status =
1227 AXTreePendingStructureStatus::kComputing;
1228
1229 base::AutoReset<base::Optional<AXNode::AXID>> pending_root_id_resetter(
1230 &update_state->pending_root_id,
1231 root_ ? base::Optional<AXNode::AXID>{root_->id()} : base::nullopt);
1232
1233 // We distinguish between updating the root, e.g. changing its children or
1234 // some of its attributes, or replacing the root completely. If the root is
1235 // being updated, update.node_id_to_clear should hold the current root's ID.
1236 // Otherwise if the root is being replaced, update.root_id should hold the ID
1237 // of the new root.
1238 if (update.node_id_to_clear != AXNode::kInvalidAXID) {
1239 if (AXNode* cleared_node = GetFromId(update.node_id_to_clear)) {
1240 DCHECK(root_);
1241 if (cleared_node == root_ &&
1242 update.root_id != update_state->pending_root_id) {
1243 // Only destroy the root if the root was replaced and not if it's simply
1244 // updated. To figure out if the root was simply updated, we compare
1245 // the ID of the new root with the existing root ID.
1246 MarkSubtreeForDestruction(*update_state->pending_root_id, update_state);
1247 }
1248
1249 // If the tree has been marked for destruction because the root will be
1250 // replaced, there is nothing more to clear.
1251 if (update_state->ShouldPendingNodeExistInTree(root_->id())) {
1252 update_state->invalidate_unignored_cached_values_ids.insert(
1253 cleared_node->id());
1254 update_state->ClearLastKnownPendingNodeData(cleared_node->id());
1255 for (AXNode* child : cleared_node->children()) {
1256 MarkSubtreeForDestruction(child->id(), update_state);
1257 }
1258 }
1259 }
1260 }
1261
1262 update_state->root_will_be_created =
1263 !GetFromId(update.root_id) ||
1264 !update_state->ShouldPendingNodeExistInTree(update.root_id);
1265
1266 // Populate |update_state| with all of the changes that will be performed
1267 // on the tree during the update.
1268 for (const AXNodeData& new_data : update.nodes) {
1269 bool is_new_root =
1270 update_state->root_will_be_created && new_data.id == update.root_id;
1271 if (!ComputePendingChangesToNode(new_data, is_new_root, update_state)) {
1272 update_state->pending_update_status =
1273 AXTreePendingStructureStatus::kFailed;
1274 return false;
1275 }
1276 }
1277
1278 update_state->pending_update_status = AXTreePendingStructureStatus::kComplete;
1279 return true;
1280 }
1281
ComputePendingChangesToNode(const AXNodeData & new_data,bool is_new_root,AXTreeUpdateState * update_state)1282 bool AXTree::ComputePendingChangesToNode(const AXNodeData& new_data,
1283 bool is_new_root,
1284 AXTreeUpdateState* update_state) {
1285 // Compare every child's index in parent in the update with the existing
1286 // index in parent. If the order has changed, invalidate the cached
1287 // unignored index in parent.
1288 for (size_t j = 0; j < new_data.child_ids.size(); j++) {
1289 AXNode* node = GetFromId(new_data.child_ids[j]);
1290 if (node && node->GetIndexInParent() != j)
1291 update_state->InvalidateParentNodeUnignoredCacheValues(node->id());
1292 }
1293
1294 // If the node does not exist in the tree throw an error unless this
1295 // is the new root and it can be created.
1296 if (!update_state->ShouldPendingNodeExistInTree(new_data.id)) {
1297 if (!is_new_root) {
1298 error_ = base::StringPrintf(
1299 "%d will not be in the tree and is not the new root", new_data.id);
1300 return false;
1301 }
1302
1303 // Creation is implicit for new root nodes. If |new_data.id| is already
1304 // pending for creation, then it must be a duplicate entry in the tree.
1305 if (!update_state->IncrementPendingCreateNodeCount(new_data.id,
1306 base::nullopt)) {
1307 error_ = base::StringPrintf(
1308 "Node %d is already pending for creation, cannot be the new root",
1309 new_data.id);
1310 return false;
1311 }
1312 if (update_state->pending_root_id) {
1313 MarkSubtreeForDestruction(*update_state->pending_root_id, update_state);
1314 }
1315 update_state->pending_root_id = new_data.id;
1316 }
1317
1318 // Create a set of new child ids so we can use it to find the nodes that
1319 // have been added and removed. Returns false if a duplicate is found.
1320 std::set<AXNode::AXID> new_child_id_set;
1321 for (AXNode::AXID new_child_id : new_data.child_ids) {
1322 if (base::Contains(new_child_id_set, new_child_id)) {
1323 error_ = base::StringPrintf("Node %d has duplicate child id %d",
1324 new_data.id, new_child_id);
1325 return false;
1326 }
1327 new_child_id_set.insert(new_child_id);
1328 }
1329
1330 // If the node has not been initialized yet then its node data has either been
1331 // cleared when handling |node_id_to_clear|, or it's a new node.
1332 // In either case, all children must be created.
1333 if (update_state->DoesPendingNodeRequireInit(new_data.id)) {
1334 update_state->invalidate_unignored_cached_values_ids.insert(new_data.id);
1335
1336 // If this node has been cleared via |node_id_to_clear| or is a new node,
1337 // the last-known parent's unignored cache needs to be updated.
1338 update_state->InvalidateParentNodeUnignoredCacheValues(new_data.id);
1339
1340 for (AXNode::AXID child_id : new_child_id_set) {
1341 // If a |child_id| is already pending for creation, then it must be a
1342 // duplicate entry in the tree.
1343 update_state->invalidate_unignored_cached_values_ids.insert(child_id);
1344 if (!update_state->IncrementPendingCreateNodeCount(child_id,
1345 new_data.id)) {
1346 error_ = base::StringPrintf(
1347 "Node %d is already pending for creation, cannot be a new child",
1348 child_id);
1349 return false;
1350 }
1351 }
1352
1353 update_state->SetLastKnownPendingNodeData(&new_data);
1354 return true;
1355 }
1356
1357 const AXNodeData& old_data =
1358 update_state->GetLastKnownPendingNodeData(new_data.id);
1359
1360 // Create a set of old child ids so we can use it to find the nodes that
1361 // have been added and removed.
1362 std::set<AXNode::AXID> old_child_id_set(old_data.child_ids.cbegin(),
1363 old_data.child_ids.cend());
1364
1365 std::vector<AXNode::AXID> create_or_destroy_ids;
1366 std::set_symmetric_difference(
1367 old_child_id_set.cbegin(), old_child_id_set.cend(),
1368 new_child_id_set.cbegin(), new_child_id_set.cend(),
1369 std::back_inserter(create_or_destroy_ids));
1370
1371 // If the node has changed ignored state or there are any differences in
1372 // its children, then its unignored cached values must be invalidated.
1373 const bool ignored_changed = old_data.IsIgnored() != new_data.IsIgnored();
1374 if (!create_or_destroy_ids.empty() || ignored_changed) {
1375 update_state->invalidate_unignored_cached_values_ids.insert(new_data.id);
1376
1377 // If this ignored state had changed also invalidate the parent.
1378 update_state->InvalidateParentNodeUnignoredCacheValues(new_data.id);
1379 }
1380
1381 for (AXNode::AXID child_id : create_or_destroy_ids) {
1382 if (base::Contains(new_child_id_set, child_id)) {
1383 // This is a serious error - nodes should never be reparented without
1384 // first being removed from the tree. If a node exists in the tree already
1385 // then adding it to a new parent would mean stealing the node from its
1386 // old parent which hadn't been updated to reflect the change.
1387 if (update_state->ShouldPendingNodeExistInTree(child_id)) {
1388 error_ = base::StringPrintf(
1389 "Node %d is not marked for destruction, would be reparented to %d",
1390 child_id, new_data.id);
1391 return false;
1392 }
1393
1394 // If a |child_id| is already pending for creation, then it must be a
1395 // duplicate entry in the tree.
1396 update_state->invalidate_unignored_cached_values_ids.insert(child_id);
1397 if (!update_state->IncrementPendingCreateNodeCount(child_id,
1398 new_data.id)) {
1399 error_ = base::StringPrintf(
1400 "Node %d is already pending for creation, cannot be a new child",
1401 child_id);
1402 return false;
1403 }
1404 } else {
1405 // If |child_id| does not exist in the new set, then it has
1406 // been removed from |node|, and the subtree must be deleted.
1407 MarkSubtreeForDestruction(child_id, update_state);
1408 }
1409 }
1410
1411 update_state->SetLastKnownPendingNodeData(&new_data);
1412 return true;
1413 }
1414
UpdateNode(const AXNodeData & src,bool is_new_root,AXTreeUpdateState * update_state)1415 bool AXTree::UpdateNode(const AXNodeData& src,
1416 bool is_new_root,
1417 AXTreeUpdateState* update_state) {
1418 DCHECK(GetTreeUpdateInProgressState());
1419 // This method updates one node in the tree based on serialized data
1420 // received in an AXTreeUpdate. See AXTreeUpdate for pre and post
1421 // conditions.
1422
1423 // Look up the node by id. If it's not found, then either the root
1424 // of the tree is being swapped, or we're out of sync with the source
1425 // and this is a serious error.
1426 AXNode* node = GetFromId(src.id);
1427 if (node) {
1428 update_state->pending_nodes.erase(node->id());
1429 UpdateReverseRelations(node, src);
1430 if (!update_state->IsCreatedNode(node) ||
1431 update_state->IsReparentedNode(node)) {
1432 update_state->old_node_id_to_data.insert(
1433 std::make_pair(node->id(), node->TakeData()));
1434 }
1435 node->SetData(src);
1436 } else {
1437 if (!is_new_root) {
1438 error_ = base::StringPrintf(
1439 "%d is not in the tree and not the new root", src.id);
1440 return false;
1441 }
1442
1443 node = CreateNode(nullptr, src.id, 0, update_state);
1444 UpdateReverseRelations(node, src);
1445 node->SetData(src);
1446 }
1447
1448 // If we come across a page breaking object, mark the tree as a paginated root
1449 if (src.GetBoolAttribute(ax::mojom::BoolAttribute::kIsPageBreakingObject))
1450 has_pagination_support_ = true;
1451
1452 update_state->node_data_changed_ids.insert(node->id());
1453
1454 // First, delete nodes that used to be children of this node but aren't
1455 // anymore.
1456 DeleteOldChildren(node, src.child_ids, update_state);
1457
1458 // Now build a new children vector, reusing nodes when possible,
1459 // and swap it in.
1460 std::vector<AXNode*> new_children;
1461 bool success = CreateNewChildVector(
1462 node, src.child_ids, &new_children, update_state);
1463 node->SwapChildren(&new_children);
1464
1465 // Update the root of the tree if needed.
1466 if (is_new_root) {
1467 // Make sure root_ always points to something valid or null_, even inside
1468 // DestroySubtree.
1469 AXNode* old_root = root_;
1470 root_ = node;
1471 if (old_root && old_root != node)
1472 DestroySubtree(old_root, update_state);
1473 }
1474
1475 return success;
1476 }
1477
NotifySubtreeWillBeReparentedOrDeleted(AXNode * node,const AXTreeUpdateState * update_state)1478 void AXTree::NotifySubtreeWillBeReparentedOrDeleted(
1479 AXNode* node,
1480 const AXTreeUpdateState* update_state) {
1481 DCHECK(!GetTreeUpdateInProgressState());
1482 if (node->id() == AXNode::kInvalidAXID)
1483 return;
1484
1485 for (AXTreeObserver& observer : observers_) {
1486 if (update_state->IsReparentedNode(node)) {
1487 observer.OnSubtreeWillBeReparented(this, node);
1488 } else {
1489 observer.OnSubtreeWillBeDeleted(this, node);
1490 }
1491 }
1492 }
1493
NotifyNodeWillBeReparentedOrDeleted(AXNode * node,const AXTreeUpdateState * update_state)1494 void AXTree::NotifyNodeWillBeReparentedOrDeleted(
1495 AXNode* node,
1496 const AXTreeUpdateState* update_state) {
1497 DCHECK(!GetTreeUpdateInProgressState());
1498
1499 AXNode::AXID id = node->id();
1500 if (id == AXNode::kInvalidAXID)
1501 return;
1502
1503 table_info_map_.erase(id);
1504
1505 for (AXTreeObserver& observer : observers_) {
1506 if (update_state->IsReparentedNode(node)) {
1507 observer.OnNodeWillBeReparented(this, node);
1508 } else {
1509 observer.OnNodeWillBeDeleted(this, node);
1510 }
1511 }
1512
1513 DCHECK(table_info_map_.find(id) == table_info_map_.end())
1514 << "Table info should never be recreated during node deletion";
1515 }
1516
RecursivelyNotifyNodeDeletedForTreeTeardown(AXNode * node)1517 void AXTree::RecursivelyNotifyNodeDeletedForTreeTeardown(AXNode* node) {
1518 DCHECK(!GetTreeUpdateInProgressState());
1519 if (node->id() == AXNode::kInvalidAXID)
1520 return;
1521
1522 for (AXTreeObserver& observer : observers_)
1523 observer.OnNodeDeleted(this, node->id());
1524 for (auto* child : node->children())
1525 RecursivelyNotifyNodeDeletedForTreeTeardown(child);
1526 }
1527
NotifyNodeHasBeenDeleted(AXNode::AXID node_id)1528 void AXTree::NotifyNodeHasBeenDeleted(AXNode::AXID node_id) {
1529 DCHECK(!GetTreeUpdateInProgressState());
1530
1531 if (node_id == AXNode::kInvalidAXID)
1532 return;
1533
1534 for (AXTreeObserver& observer : observers_)
1535 observer.OnNodeDeleted(this, node_id);
1536 }
1537
NotifyNodeHasBeenReparentedOrCreated(AXNode * node,const AXTreeUpdateState * update_state)1538 void AXTree::NotifyNodeHasBeenReparentedOrCreated(
1539 AXNode* node,
1540 const AXTreeUpdateState* update_state) {
1541 DCHECK(!GetTreeUpdateInProgressState());
1542 if (node->id() == AXNode::kInvalidAXID)
1543 return;
1544
1545 for (AXTreeObserver& observer : observers_) {
1546 if (update_state->IsReparentedNode(node)) {
1547 observer.OnNodeReparented(this, node);
1548 } else {
1549 observer.OnNodeCreated(this, node);
1550 }
1551 }
1552 }
1553
NotifyNodeDataWillChange(const AXNodeData & old_data,const AXNodeData & new_data)1554 void AXTree::NotifyNodeDataWillChange(const AXNodeData& old_data,
1555 const AXNodeData& new_data) {
1556 DCHECK(!GetTreeUpdateInProgressState());
1557 if (new_data.id == AXNode::kInvalidAXID)
1558 return;
1559
1560 for (AXTreeObserver& observer : observers_)
1561 observer.OnNodeDataWillChange(this, old_data, new_data);
1562 }
1563
NotifyNodeDataHasBeenChanged(AXNode * node,const AXNodeData & old_data,const AXNodeData & new_data)1564 void AXTree::NotifyNodeDataHasBeenChanged(AXNode* node,
1565 const AXNodeData& old_data,
1566 const AXNodeData& new_data) {
1567 DCHECK(!GetTreeUpdateInProgressState());
1568 if (node->id() == AXNode::kInvalidAXID)
1569 return;
1570
1571 for (AXTreeObserver& observer : observers_)
1572 observer.OnNodeDataChanged(this, old_data, new_data);
1573
1574 if (old_data.role != new_data.role) {
1575 for (AXTreeObserver& observer : observers_)
1576 observer.OnRoleChanged(this, node, old_data.role, new_data.role);
1577 }
1578
1579 if (old_data.state != new_data.state) {
1580 for (int32_t i = static_cast<int32_t>(ax::mojom::State::kNone) + 1;
1581 i <= static_cast<int32_t>(ax::mojom::State::kMaxValue); ++i) {
1582 ax::mojom::State state = static_cast<ax::mojom::State>(i);
1583 if (old_data.HasState(state) != new_data.HasState(state)) {
1584 for (AXTreeObserver& observer : observers_)
1585 observer.OnStateChanged(this, node, state, new_data.HasState(state));
1586 }
1587 }
1588 }
1589
1590 auto string_callback = [this, node](ax::mojom::StringAttribute attr,
1591 const std::string& old_string,
1592 const std::string& new_string) {
1593 for (AXTreeObserver& observer : observers_) {
1594 observer.OnStringAttributeChanged(this, node, attr, old_string,
1595 new_string);
1596 }
1597 };
1598 CallIfAttributeValuesChanged(old_data.string_attributes,
1599 new_data.string_attributes, std::string(),
1600 string_callback);
1601
1602 auto bool_callback = [this, node](ax::mojom::BoolAttribute attr,
1603 const bool& old_bool,
1604 const bool& new_bool) {
1605 for (AXTreeObserver& observer : observers_)
1606 observer.OnBoolAttributeChanged(this, node, attr, new_bool);
1607 };
1608 CallIfAttributeValuesChanged(old_data.bool_attributes,
1609 new_data.bool_attributes, false, bool_callback);
1610
1611 auto float_callback = [this, node](ax::mojom::FloatAttribute attr,
1612 const float& old_float,
1613 const float& new_float) {
1614 for (AXTreeObserver& observer : observers_)
1615 observer.OnFloatAttributeChanged(this, node, attr, old_float, new_float);
1616 };
1617 CallIfAttributeValuesChanged(old_data.float_attributes,
1618 new_data.float_attributes, 0.0f, float_callback);
1619
1620 auto int_callback = [this, node](ax::mojom::IntAttribute attr,
1621 const int& old_int, const int& new_int) {
1622 for (AXTreeObserver& observer : observers_)
1623 observer.OnIntAttributeChanged(this, node, attr, old_int, new_int);
1624 };
1625 CallIfAttributeValuesChanged(old_data.int_attributes, new_data.int_attributes,
1626 0, int_callback);
1627
1628 auto intlist_callback = [this, node](
1629 ax::mojom::IntListAttribute attr,
1630 const std::vector<int32_t>& old_intlist,
1631 const std::vector<int32_t>& new_intlist) {
1632 for (AXTreeObserver& observer : observers_)
1633 observer.OnIntListAttributeChanged(this, node, attr, old_intlist,
1634 new_intlist);
1635 };
1636 CallIfAttributeValuesChanged(old_data.intlist_attributes,
1637 new_data.intlist_attributes,
1638 std::vector<int32_t>(), intlist_callback);
1639
1640 auto stringlist_callback =
1641 [this, node](ax::mojom::StringListAttribute attr,
1642 const std::vector<std::string>& old_stringlist,
1643 const std::vector<std::string>& new_stringlist) {
1644 for (AXTreeObserver& observer : observers_)
1645 observer.OnStringListAttributeChanged(this, node, attr,
1646 old_stringlist, new_stringlist);
1647 };
1648 CallIfAttributeValuesChanged(old_data.stringlist_attributes,
1649 new_data.stringlist_attributes,
1650 std::vector<std::string>(), stringlist_callback);
1651 }
1652
UpdateReverseRelations(AXNode * node,const AXNodeData & new_data)1653 void AXTree::UpdateReverseRelations(AXNode* node, const AXNodeData& new_data) {
1654 DCHECK(GetTreeUpdateInProgressState());
1655 const AXNodeData& old_data = node->data();
1656 int id = new_data.id;
1657 auto int_callback = [this, id](ax::mojom::IntAttribute attr,
1658 const int& old_id, const int& new_id) {
1659 if (!IsNodeIdIntAttribute(attr))
1660 return;
1661
1662 // Remove old_id -> id from the map, and clear map keys if their
1663 // values are now empty.
1664 auto& map = int_reverse_relations_[attr];
1665 if (map.find(old_id) != map.end()) {
1666 map[old_id].erase(id);
1667 if (map[old_id].empty())
1668 map.erase(old_id);
1669 }
1670
1671 // Add new_id -> id to the map, unless new_id is zero indicating that
1672 // we're only removing a relation.
1673 if (new_id)
1674 map[new_id].insert(id);
1675 };
1676 CallIfAttributeValuesChanged(old_data.int_attributes, new_data.int_attributes,
1677 0, int_callback);
1678
1679 auto intlist_callback = [this, id](ax::mojom::IntListAttribute attr,
1680 const std::vector<int32_t>& old_idlist,
1681 const std::vector<int32_t>& new_idlist) {
1682 if (!IsNodeIdIntListAttribute(attr))
1683 return;
1684
1685 auto& map = intlist_reverse_relations_[attr];
1686 for (int32_t old_id : old_idlist) {
1687 if (map.find(old_id) != map.end()) {
1688 map[old_id].erase(id);
1689 if (map[old_id].empty())
1690 map.erase(old_id);
1691 }
1692 }
1693 for (int32_t new_id : new_idlist)
1694 intlist_reverse_relations_[attr][new_id].insert(id);
1695 };
1696 CallIfAttributeValuesChanged(old_data.intlist_attributes,
1697 new_data.intlist_attributes,
1698 std::vector<int32_t>(), intlist_callback);
1699
1700 auto string_callback = [this, id](ax::mojom::StringAttribute attr,
1701 const std::string& old_string,
1702 const std::string& new_string) {
1703 if (attr == ax::mojom::StringAttribute::kChildTreeId) {
1704 // Remove old_string -> id from the map, and clear map keys if
1705 // their values are now empty.
1706 AXTreeID old_ax_tree_id = AXTreeID::FromString(old_string);
1707 if (child_tree_id_reverse_map_.find(old_ax_tree_id) !=
1708 child_tree_id_reverse_map_.end()) {
1709 child_tree_id_reverse_map_[old_ax_tree_id].erase(id);
1710 if (child_tree_id_reverse_map_[old_ax_tree_id].empty())
1711 child_tree_id_reverse_map_.erase(old_ax_tree_id);
1712 }
1713
1714 // Add new_string -> id to the map, unless new_id is zero indicating that
1715 // we're only removing a relation.
1716 if (!new_string.empty()) {
1717 AXTreeID new_ax_tree_id = AXTreeID::FromString(new_string);
1718 child_tree_id_reverse_map_[new_ax_tree_id].insert(id);
1719 }
1720 }
1721 };
1722
1723 CallIfAttributeValuesChanged(old_data.string_attributes,
1724 new_data.string_attributes, std::string(),
1725 string_callback);
1726 }
1727
ValidatePendingChangesComplete(const AXTreeUpdateState & update_state)1728 bool AXTree::ValidatePendingChangesComplete(
1729 const AXTreeUpdateState& update_state) {
1730 if (!update_state.pending_nodes.empty()) {
1731 error_ = "Nodes left pending by the update:";
1732 for (const AXNode::AXID pending_id : update_state.pending_nodes)
1733 error_ += base::StringPrintf(" %d", pending_id);
1734 return false;
1735 }
1736
1737 if (!update_state.node_id_to_pending_data.empty()) {
1738 std::string destroy_subtree_ids;
1739 std::string destroy_node_ids;
1740 std::string create_node_ids;
1741
1742 bool has_pending_changes = false;
1743 for (auto&& pair : update_state.node_id_to_pending_data) {
1744 const AXNode::AXID pending_id = pair.first;
1745 const std::unique_ptr<PendingStructureChanges>& data = pair.second;
1746 if (data->DoesNodeExpectAnyStructureChanges()) {
1747 if (data->DoesNodeExpectSubtreeWillBeDestroyed())
1748 destroy_subtree_ids += base::StringPrintf(" %d", pending_id);
1749 if (data->DoesNodeExpectNodeWillBeDestroyed())
1750 destroy_node_ids += base::StringPrintf(" %d", pending_id);
1751 if (data->DoesNodeExpectNodeWillBeCreated())
1752 create_node_ids += base::StringPrintf(" %d", pending_id);
1753 has_pending_changes = true;
1754 }
1755 }
1756 if (has_pending_changes) {
1757 error_ = base::StringPrintf(
1758 "Changes left pending by the update; "
1759 "destroy subtrees: %s, destroy nodes: %s, create nodes: %s",
1760 destroy_subtree_ids.c_str(), destroy_node_ids.c_str(),
1761 create_node_ids.c_str());
1762 }
1763 return !has_pending_changes;
1764 }
1765
1766 return true;
1767 }
1768
MarkSubtreeForDestruction(AXNode::AXID node_id,AXTreeUpdateState * update_state)1769 void AXTree::MarkSubtreeForDestruction(AXNode::AXID node_id,
1770 AXTreeUpdateState* update_state) {
1771 update_state->IncrementPendingDestroySubtreeCount(node_id);
1772 MarkNodesForDestructionRecursive(node_id, update_state);
1773 }
1774
MarkNodesForDestructionRecursive(AXNode::AXID node_id,AXTreeUpdateState * update_state)1775 void AXTree::MarkNodesForDestructionRecursive(AXNode::AXID node_id,
1776 AXTreeUpdateState* update_state) {
1777 // If this subtree has already been marked for destruction, return so
1778 // we don't walk it again.
1779 if (!update_state->ShouldPendingNodeExistInTree(node_id))
1780 return;
1781
1782 const AXNodeData& last_known_data =
1783 update_state->GetLastKnownPendingNodeData(node_id);
1784
1785 update_state->IncrementPendingDestroyNodeCount(node_id);
1786 for (AXNode::AXID child_id : last_known_data.child_ids) {
1787 MarkNodesForDestructionRecursive(child_id, update_state);
1788 }
1789 }
1790
DestroySubtree(AXNode * node,AXTreeUpdateState * update_state)1791 void AXTree::DestroySubtree(AXNode* node,
1792 AXTreeUpdateState* update_state) {
1793 DCHECK(GetTreeUpdateInProgressState());
1794 // |update_state| must already contain information about all of the expected
1795 // changes and invalidations to apply. If any of these are missing, observers
1796 // may not be notified of changes.
1797 DCHECK(update_state);
1798 DCHECK_GT(update_state->GetPendingDestroySubtreeCount(node->id()), 0);
1799 DCHECK(!node->parent() ||
1800 update_state->InvalidatesUnignoredCachedValues(node->parent()->id()));
1801 update_state->DecrementPendingDestroySubtreeCount(node->id());
1802 DestroyNodeAndSubtree(node, update_state);
1803 }
1804
DestroyNodeAndSubtree(AXNode * node,AXTreeUpdateState * update_state)1805 void AXTree::DestroyNodeAndSubtree(AXNode* node,
1806 AXTreeUpdateState* update_state) {
1807 DCHECK(GetTreeUpdateInProgressState());
1808 DCHECK(!update_state ||
1809 update_state->GetPendingDestroyNodeCount(node->id()) > 0);
1810
1811 // Clear out any reverse relations.
1812 AXNodeData empty_data;
1813 empty_data.id = node->id();
1814 UpdateReverseRelations(node, empty_data);
1815
1816 id_map_.erase(node->id());
1817 for (auto* child : node->children())
1818 DestroyNodeAndSubtree(child, update_state);
1819 if (update_state) {
1820 update_state->pending_nodes.erase(node->id());
1821 update_state->DecrementPendingDestroyNodeCount(node->id());
1822 update_state->removed_node_ids.insert(node->id());
1823 update_state->new_node_ids.erase(node->id());
1824 update_state->node_data_changed_ids.erase(node->id());
1825 if (update_state->IsReparentedNode(node)) {
1826 update_state->old_node_id_to_data.emplace(
1827 std::make_pair(node->id(), node->TakeData()));
1828 }
1829 }
1830 node->Destroy();
1831 }
1832
DeleteOldChildren(AXNode * node,const std::vector<int32_t> & new_child_ids,AXTreeUpdateState * update_state)1833 void AXTree::DeleteOldChildren(AXNode* node,
1834 const std::vector<int32_t>& new_child_ids,
1835 AXTreeUpdateState* update_state) {
1836 DCHECK(GetTreeUpdateInProgressState());
1837 // Create a set of child ids in |src| for fast lookup, we know the set does
1838 // not contain duplicate entries already, because that was handled when
1839 // populating |update_state| with information about all of the expected
1840 // changes to be applied.
1841 std::set<int32_t> new_child_id_set(new_child_ids.begin(),
1842 new_child_ids.end());
1843
1844 // Delete the old children.
1845 for (AXNode* child : node->children()) {
1846 if (!base::Contains(new_child_id_set, child->id()))
1847 DestroySubtree(child, update_state);
1848 }
1849 }
1850
CreateNewChildVector(AXNode * node,const std::vector<int32_t> & new_child_ids,std::vector<AXNode * > * new_children,AXTreeUpdateState * update_state)1851 bool AXTree::CreateNewChildVector(AXNode* node,
1852 const std::vector<int32_t>& new_child_ids,
1853 std::vector<AXNode*>* new_children,
1854 AXTreeUpdateState* update_state) {
1855 DCHECK(GetTreeUpdateInProgressState());
1856 bool success = true;
1857 for (size_t i = 0; i < new_child_ids.size(); ++i) {
1858 int32_t child_id = new_child_ids[i];
1859 AXNode* child = GetFromId(child_id);
1860 if (child) {
1861 if (child->parent() != node) {
1862 // This is a serious error - nodes should never be reparented.
1863 // If this case occurs, continue so this node isn't left in an
1864 // inconsistent state, but return failure at the end.
1865 error_ = base::StringPrintf(
1866 "Node %d reparented from %d to %d",
1867 child->id(),
1868 child->parent() ? child->parent()->id() : 0,
1869 node->id());
1870 success = false;
1871 continue;
1872 }
1873 child->SetIndexInParent(i);
1874 } else {
1875 child = CreateNode(node, child_id, i, update_state);
1876 update_state->pending_nodes.insert(child->id());
1877 }
1878 new_children->push_back(child);
1879 }
1880
1881 return success;
1882 }
1883
SetEnableExtraMacNodes(bool enabled)1884 void AXTree::SetEnableExtraMacNodes(bool enabled) {
1885 if (enable_extra_mac_nodes_ == enabled)
1886 return; // No change.
1887 if (enable_extra_mac_nodes_ && !enabled) {
1888 NOTREACHED()
1889 << "We don't support disabling the extra Mac nodes once enabled.";
1890 return;
1891 }
1892
1893 DCHECK_EQ(0U, table_info_map_.size());
1894 enable_extra_mac_nodes_ = enabled;
1895 }
1896
GetNextNegativeInternalNodeId()1897 int32_t AXTree::GetNextNegativeInternalNodeId() {
1898 int32_t return_value = next_negative_internal_node_id_;
1899 next_negative_internal_node_id_--;
1900 if (next_negative_internal_node_id_ > 0)
1901 next_negative_internal_node_id_ = -1;
1902 return return_value;
1903 }
1904
PopulateOrderedSetItemsMap(const AXNode & original_node,const AXNode * ordered_set,OrderedSetItemsMap * items_map_to_be_populated) const1905 void AXTree::PopulateOrderedSetItemsMap(
1906 const AXNode& original_node,
1907 const AXNode* ordered_set,
1908 OrderedSetItemsMap* items_map_to_be_populated) const {
1909 // Ignored nodes are not a part of ordered sets.
1910 if (original_node.IsIgnored())
1911 return;
1912
1913 // Not all ordered set containers support hierarchical level, but their set
1914 // items may support hierarchical level. For example, container <tree> does
1915 // not support level, but <treeitem> supports level. For ordered sets like
1916 // this, the set container (e.g. <tree>) will take on the min of the levels
1917 // of its direct children(e.g. <treeitem>), if the children's levels are
1918 // defined.
1919 base::Optional<int> ordered_set_min_level =
1920 ordered_set->GetHierarchicalLevel();
1921
1922 for (AXNode::UnignoredChildIterator child =
1923 ordered_set->UnignoredChildrenBegin();
1924 child != ordered_set->UnignoredChildrenEnd(); ++child) {
1925 base::Optional<int> child_level = child->GetHierarchicalLevel();
1926 if (child_level) {
1927 ordered_set_min_level = ordered_set_min_level
1928 ? std::min(child_level, ordered_set_min_level)
1929 : child_level;
1930 }
1931 }
1932
1933 RecursivelyPopulateOrderedSetItemsMap(original_node, ordered_set, ordered_set,
1934 ordered_set_min_level, base::nullopt,
1935 items_map_to_be_populated);
1936
1937 // If after RecursivelyPopulateOrderedSetItemsMap() call, the corresponding
1938 // level (i.e. |ordered_set_min_level|) does not exist in
1939 // |items_map_to_be_populated|, and |original_node| equals |ordered_set|, we
1940 // know |original_node| is an empty ordered set and contains no set items.
1941 // However, |original_node| may still have set size attribute, so we still
1942 // want to add this empty set (i.e. original_node/ordered_set) to
1943 // |items_map_to_be_populated|.
1944 if (&original_node == ordered_set &&
1945 !items_map_to_be_populated->HierarchicalLevelExists(
1946 ordered_set_min_level)) {
1947 items_map_to_be_populated->Add(ordered_set_min_level,
1948 OrderedSetContent(&original_node));
1949 }
1950 }
1951
RecursivelyPopulateOrderedSetItemsMap(const AXNode & original_node,const AXNode * ordered_set,const AXNode * local_parent,base::Optional<int> ordered_set_min_level,base::Optional<int> prev_level,OrderedSetItemsMap * items_map_to_be_populated) const1952 void AXTree::RecursivelyPopulateOrderedSetItemsMap(
1953 const AXNode& original_node,
1954 const AXNode* ordered_set,
1955 const AXNode* local_parent,
1956 base::Optional<int> ordered_set_min_level,
1957 base::Optional<int> prev_level,
1958 OrderedSetItemsMap* items_map_to_be_populated) const {
1959 // For optimization purpose, we want to only populate set items that are
1960 // direct descendants of |ordered_set|, since we will only be calculating
1961 // PosInSet & SetSize of items of that level. So we skip items on deeper
1962 // levels by stop searching recursively on node |local_parent| that turns out
1963 // to be an ordered set whose role matches that of |ordered_set|. However,
1964 // when we encounter a flattened structure such as the following:
1965 // <div role="tree">
1966 // <div role="treeitem" aria-level="1"></div>
1967 // <div role="treeitem" aria-level="2"></div>
1968 // <div role="treeitem" aria-level="3"></div>
1969 // </div>
1970 // This optimization won't apply, we will end up populating items from all
1971 // levels.
1972 if (ordered_set->data().role == local_parent->data().role &&
1973 ordered_set != local_parent)
1974 return;
1975
1976 for (AXNode::UnignoredChildIterator itr =
1977 local_parent->UnignoredChildrenBegin();
1978 itr != local_parent->UnignoredChildrenEnd(); ++itr) {
1979 const AXNode* child = itr.get();
1980
1981 // Invisible children should not be counted.
1982 // However, in the collapsed container case (e.g. a combobox), items can
1983 // still be chosen/navigated. However, the options in these collapsed
1984 // containers are historically marked invisible. Therefore, in that case,
1985 // count the invisible items. Only check 2 levels up, as combobox containers
1986 // are never higher.
1987 if (child->data().HasState(ax::mojom::State::kInvisible) &&
1988 !IsCollapsed(local_parent) && !IsCollapsed(local_parent->parent())) {
1989 continue;
1990 }
1991
1992 base::Optional<int> curr_level = child->GetHierarchicalLevel();
1993
1994 // Add child to |items_map_to_be_populated| if role matches with the role of
1995 // |ordered_set|. If role of node is kRadioButton, don't add items of other
1996 // roles, even if item role matches the role of |ordered_set|.
1997 if (child->data().role == ax::mojom::Role::kComment ||
1998 (original_node.data().role == ax::mojom::Role::kRadioButton &&
1999 child->data().role == ax::mojom::Role::kRadioButton) ||
2000 (original_node.data().role != ax::mojom::Role::kRadioButton &&
2001 child->SetRoleMatchesItemRole(ordered_set))) {
2002 // According to WAI-ARIA spec, some ordered set items do not support
2003 // hierarchical level while its ordered set container does. For example,
2004 // <tab> does not support level, while <tablist> supports level.
2005 // https://www.w3.org/WAI/PF/aria/roles#tab
2006 // https://www.w3.org/WAI/PF/aria/roles#tablist
2007 // For this special case, when we add set items (e.g. tab) to
2008 // |items_map_to_be_populated|, set item is placed at the same level as
2009 // its container (e.g. tablist) in |items_map_to_be_populated|.
2010 if (!curr_level && child->GetUnignoredParent() == ordered_set)
2011 curr_level = ordered_set_min_level;
2012
2013 // We only add child to |items_map_to_be_populated| if the child set item
2014 // is at the same hierarchical level as |ordered_set|'s level.
2015 if (!items_map_to_be_populated->HierarchicalLevelExists(curr_level)) {
2016 bool use_ordered_set = child->SetRoleMatchesItemRole(ordered_set) &&
2017 ordered_set_min_level == curr_level;
2018 const AXNode* child_ordered_set =
2019 use_ordered_set ? ordered_set : nullptr;
2020 items_map_to_be_populated->Add(curr_level,
2021 OrderedSetContent(child_ordered_set));
2022 }
2023
2024 items_map_to_be_populated->AddItemToBack(curr_level, child);
2025 }
2026
2027 // If |child| is an ignored container for ordered set and should not be used
2028 // to contribute to |items_map_to_be_populated|, we recurse into |child|'s
2029 // descendants to populate |items_map_to_be_populated|.
2030 if (child->IsIgnoredContainerForOrderedSet()) {
2031 RecursivelyPopulateOrderedSetItemsMap(original_node, ordered_set, child,
2032 ordered_set_min_level, curr_level,
2033 items_map_to_be_populated);
2034 }
2035
2036 // If |curr_level| goes up one level from |prev_level|, which indicates
2037 // the ordered set of |prev_level| is closed, we add a new OrderedSetContent
2038 // on the previous level of |items_map_to_be_populated| to signify this.
2039 // Consider the example below:
2040 // <div role="tree">
2041 // <div role="treeitem" aria-level="1"></div>
2042 // <!--- set1-level2 -->
2043 // <div role="treeitem" aria-level="2"></div>
2044 // <div role="treeitem" aria-level="2"></div> <--|prev_level|
2045 // <div role="treeitem" aria-level="1" id="item2-level1"> <--|curr_level|
2046 // </div>
2047 // <!--- set2-level2 -->
2048 // <div role="treeitem" aria-level="2"></div>
2049 // <div role="treeitem" aria-level="2"></div>
2050 // </div>
2051 // |prev_level| is on the last item of "set1-level2" and |curr_level| is on
2052 // "item2-level1". Since |curr_level| is up one level from |prev_level|, we
2053 // already completed adding all items from "set1-level2" to
2054 // |items_map_to_be_populated|. So we close up "set1-level2" by adding a new
2055 // OrderedSetContent to level 2. When |curr_level| ends up on the items of
2056 // "set2-level2" next, it has a fresh new set to be populated.
2057 if (child->SetRoleMatchesItemRole(ordered_set) && curr_level < prev_level)
2058 items_map_to_be_populated->Add(prev_level, OrderedSetContent());
2059
2060 prev_level = curr_level;
2061 }
2062 }
2063
2064 // Given an ordered_set, compute pos_in_set and set_size for all of its items
2065 // and store values in cache.
2066 // Ordered_set should never be nullptr.
ComputeSetSizePosInSetAndCache(const AXNode & node,const AXNode * ordered_set)2067 void AXTree::ComputeSetSizePosInSetAndCache(const AXNode& node,
2068 const AXNode* ordered_set) {
2069 DCHECK(ordered_set);
2070
2071 // Set items role::kComment and role::kRadioButton are special cases and do
2072 // not necessarily need to be contained in an ordered set.
2073 if (node.data().role != ax::mojom::Role::kComment &&
2074 node.data().role != ax::mojom::Role::kRadioButton &&
2075 !node.SetRoleMatchesItemRole(ordered_set) && !IsSetLike(node.data().role))
2076 return;
2077
2078 // Find all items within ordered_set and add to |items_map_to_be_populated|.
2079 OrderedSetItemsMap items_map_to_be_populated;
2080 PopulateOrderedSetItemsMap(node, ordered_set, &items_map_to_be_populated);
2081
2082 // If ordered_set role is kPopUpButton and it wraps a kMenuListPopUp, then we
2083 // would like it to inherit the SetSize from the kMenuListPopUp it wraps. To
2084 // do this, we treat the kMenuListPopUp as the ordered_set and eventually
2085 // assign its SetSize value to the kPopUpButton.
2086 if (node.data().role == ax::mojom::Role::kPopUpButton) {
2087 // kPopUpButtons are only allowed to contain one kMenuListPopUp.
2088 // The single element is guaranteed to be a kMenuListPopUp because that is
2089 // the only item role that matches the ordered set role of kPopUpButton.
2090 // Please see AXNode::SetRoleMatchesItemRole for more details.
2091 OrderedSetContent* set_content =
2092 items_map_to_be_populated.GetFirstOrderedSetContent();
2093 if (set_content && set_content->set_items_.size() == 1) {
2094 const AXNode* menu_list_popup = set_content->set_items_.front();
2095 if (menu_list_popup->data().role == ax::mojom::Role::kMenuListPopup) {
2096 items_map_to_be_populated.Clear();
2097 PopulateOrderedSetItemsMap(node, menu_list_popup,
2098 &items_map_to_be_populated);
2099 set_content = items_map_to_be_populated.GetFirstOrderedSetContent();
2100 // Replace |set_content|'s ordered set container with |node|
2101 // (Role::kPopUpButton), which acts as the set container for nodes with
2102 // Role::kMenuListOptions (children of |menu_list_popup|).
2103 if (set_content)
2104 set_content->ordered_set_ = &node;
2105 }
2106 }
2107 }
2108
2109 // Iterate over all items from OrderedSetItemsMap to compute and cache each
2110 // ordered set item's PosInSet and SetSize and corresponding ordered set
2111 // container's SetSize.
2112 for (auto element : items_map_to_be_populated.items_map_) {
2113 for (const OrderedSetContent& ordered_set_content : element.second) {
2114 ComputeSetSizePosInSetAndCacheHelper(ordered_set_content);
2115 }
2116 }
2117 }
2118
ComputeSetSizePosInSetAndCacheHelper(const OrderedSetContent & ordered_set_content)2119 void AXTree::ComputeSetSizePosInSetAndCacheHelper(
2120 const OrderedSetContent& ordered_set_content) {
2121 // Keep track of number of items in the set.
2122 int32_t num_elements = 0;
2123 // Keep track of largest ordered set item's |aria-setsize| attribute value.
2124 int32_t max_item_set_size_from_attribute = 0;
2125
2126 for (const AXNode* item : ordered_set_content.set_items_) {
2127 // |item|'s PosInSet value is the maximum of accumulated number of
2128 // elements count and the value from its |aria-posinset| attribute.
2129 int32_t pos_in_set_value =
2130 std::max(num_elements + 1,
2131 item->GetIntAttribute(ax::mojom::IntAttribute::kPosInSet));
2132
2133 // For |item| that has defined hierarchical level and |aria-posinset|
2134 // attribute, the attribute value takes precedence.
2135 // Note: According to WAI-ARIA spec, items that support
2136 // |aria-posinset| do not necessarily support hierarchical level.
2137 if (item->GetHierarchicalLevel() &&
2138 item->HasIntAttribute(ax::mojom::IntAttribute::kPosInSet))
2139 pos_in_set_value =
2140 item->GetIntAttribute(ax::mojom::IntAttribute::kPosInSet);
2141
2142 num_elements = pos_in_set_value;
2143
2144 // Cache computed PosInSet value for |item|.
2145 node_set_size_pos_in_set_info_map_[item->id()] = NodeSetSizePosInSetInfo();
2146 node_set_size_pos_in_set_info_map_[item->id()].pos_in_set =
2147 pos_in_set_value;
2148
2149 // Track the largest set size for this OrderedSetContent.
2150 max_item_set_size_from_attribute =
2151 std::max(max_item_set_size_from_attribute,
2152 item->GetIntAttribute(ax::mojom::IntAttribute::kSetSize));
2153 } // End of iterating over each item in |ordered_set_content|.
2154
2155 // The SetSize of an ordered set (and all of its items) is the maximum of
2156 // the following values:
2157 // 1. The number of elements in the ordered set.
2158 // 2. The largest item set size from |aria-setsize| attribute.
2159 // 3. The ordered set container's |aria-setsize| attribute value.
2160 int32_t set_size_value =
2161 std::max(num_elements, max_item_set_size_from_attribute);
2162
2163 // Cache the hierarchical level and set size of |ordered_set_content|'s set
2164 // container, if the container exists.
2165 if (const AXNode* ordered_set = ordered_set_content.ordered_set_) {
2166 set_size_value = std::max(
2167 set_size_value,
2168 ordered_set->GetIntAttribute(ax::mojom::IntAttribute::kSetSize));
2169
2170 // Cache |ordered_set|'s hierarchical level.
2171 base::Optional<int> ordered_set_level = ordered_set->GetHierarchicalLevel();
2172 if (node_set_size_pos_in_set_info_map_.find(ordered_set->id()) ==
2173 node_set_size_pos_in_set_info_map_.end()) {
2174 node_set_size_pos_in_set_info_map_[ordered_set->id()] =
2175 NodeSetSizePosInSetInfo();
2176 node_set_size_pos_in_set_info_map_[ordered_set->id()]
2177 .lowest_hierarchical_level = ordered_set_level;
2178 } else if (node_set_size_pos_in_set_info_map_[ordered_set->id()]
2179 .lowest_hierarchical_level > ordered_set_level) {
2180 node_set_size_pos_in_set_info_map_[ordered_set->id()]
2181 .lowest_hierarchical_level = ordered_set_level;
2182 }
2183 // Cache |ordered_set|'s set size.
2184 node_set_size_pos_in_set_info_map_[ordered_set->id()].set_size =
2185 set_size_value;
2186 }
2187
2188 // Cache the set size of |ordered_set_content|'s set items.
2189 for (const AXNode* item : ordered_set_content.set_items_) {
2190 // If item's hierarchical level and |aria-setsize| attribute are specified,
2191 // the item's |aria-setsize| value takes precedence.
2192 if (item->GetHierarchicalLevel() &&
2193 item->HasIntAttribute(ax::mojom::IntAttribute::kSetSize))
2194 node_set_size_pos_in_set_info_map_[item->id()].set_size =
2195 item->GetIntAttribute(ax::mojom::IntAttribute::kSetSize);
2196 else
2197 node_set_size_pos_in_set_info_map_[item->id()].set_size = set_size_value;
2198 } // End of iterating over each item in |ordered_set_content|.
2199 }
2200
2201 // Returns the pos_in_set of item. Looks in |node_set_size_pos_in_set_info_map_|
2202 // for cached value. Calculates pos_in_set and set_size for item (and all other
2203 // items in the same ordered set) if no value is present in the cache. This
2204 // function is guaranteed to be only called on nodes that can hold pos_in_set
2205 // values, minimizing the size of the cache.
GetPosInSet(const AXNode & node,const AXNode * ordered_set)2206 int32_t AXTree::GetPosInSet(const AXNode& node, const AXNode* ordered_set) {
2207 // If item's id is not in the cache, compute it.
2208 if (node_set_size_pos_in_set_info_map_.find(node.id()) ==
2209 node_set_size_pos_in_set_info_map_.end())
2210 ComputeSetSizePosInSetAndCache(node, ordered_set);
2211 return node_set_size_pos_in_set_info_map_[node.id()].pos_in_set;
2212 }
2213
2214 // Returns the set_size of node. node could be an ordered set or an item.
2215 // Looks in |node_set_size_pos_in_set_info_map_| for cached value. Calculates
2216 // pos_in_set and set_size for all nodes in same ordered set if no value is
2217 // present in the cache. This function is guaranteed to be only called on nodes
2218 // that can hold set_size values, minimizing the size of the cache.
GetSetSize(const AXNode & node,const AXNode * ordered_set)2219 int32_t AXTree::GetSetSize(const AXNode& node, const AXNode* ordered_set) {
2220 // If node's id is not in the cache, compute it.
2221 if (node_set_size_pos_in_set_info_map_.find(node.id()) ==
2222 node_set_size_pos_in_set_info_map_.end())
2223 ComputeSetSizePosInSetAndCache(node, ordered_set);
2224 return node_set_size_pos_in_set_info_map_[node.id()].set_size;
2225 }
2226
GetUnignoredSelection() const2227 AXTree::Selection AXTree::GetUnignoredSelection() const {
2228 Selection unignored_selection = {
2229 data().sel_is_backward, data().sel_anchor_object_id,
2230 data().sel_anchor_offset, data().sel_anchor_affinity,
2231 data().sel_focus_object_id, data().sel_focus_offset,
2232 data().sel_focus_affinity};
2233 AXNode* anchor_node = GetFromId(data().sel_anchor_object_id);
2234 AXNode* focus_node = GetFromId(data().sel_focus_object_id);
2235
2236 AXNodePosition::AXPositionInstance anchor_position =
2237 anchor_node ? AXNodePosition::CreatePosition(*anchor_node,
2238 data().sel_anchor_offset,
2239 data().sel_anchor_affinity)
2240 : AXNodePosition::CreateNullPosition();
2241
2242 // Null positions are never ignored.
2243 if (anchor_position->IsIgnored()) {
2244 anchor_position = anchor_position->AsUnignoredPosition(
2245 data().sel_is_backward ? AXPositionAdjustmentBehavior::kMoveForward
2246 : AXPositionAdjustmentBehavior::kMoveBackward);
2247
2248 // Any selection endpoint that is inside a leaf node is expressed as a text
2249 // position in AXTreeData.
2250 if (anchor_position->IsLeafTreePosition())
2251 anchor_position = anchor_position->AsTextPosition();
2252
2253 // We do not expect the selection to have an endpoint on an inline text
2254 // box as this will create issues with parts of the code that don't use
2255 // inline text boxes.
2256 if (anchor_position->IsTextPosition() &&
2257 anchor_position->GetAnchor()->data().role ==
2258 ax::mojom::Role::kInlineTextBox) {
2259 anchor_position = anchor_position->CreateParentPosition();
2260 }
2261
2262 switch (anchor_position->kind()) {
2263 case AXPositionKind::NULL_POSITION:
2264 // If one of the selection endpoints is invalid, then both endpoints
2265 // should be unset.
2266 unignored_selection.anchor_object_id = AXNode::kInvalidAXID;
2267 unignored_selection.anchor_offset = -1;
2268 unignored_selection.anchor_affinity =
2269 ax::mojom::TextAffinity::kDownstream;
2270 unignored_selection.focus_object_id = AXNode::kInvalidAXID;
2271 unignored_selection.focus_offset = -1;
2272 unignored_selection.focus_affinity =
2273 ax::mojom::TextAffinity::kDownstream;
2274 return unignored_selection;
2275 case AXPositionKind::TREE_POSITION:
2276 unignored_selection.anchor_object_id = anchor_position->anchor_id();
2277 unignored_selection.anchor_offset = anchor_position->child_index();
2278 unignored_selection.anchor_affinity =
2279 ax::mojom::TextAffinity::kDownstream;
2280 break;
2281 case AXPositionKind::TEXT_POSITION:
2282 unignored_selection.anchor_object_id = anchor_position->anchor_id();
2283 unignored_selection.anchor_offset = anchor_position->text_offset();
2284 unignored_selection.anchor_affinity = anchor_position->affinity();
2285 break;
2286 }
2287 }
2288
2289 AXNodePosition::AXPositionInstance focus_position =
2290 focus_node
2291 ? AXNodePosition::CreatePosition(*focus_node, data().sel_focus_offset,
2292 data().sel_focus_affinity)
2293 : AXNodePosition::CreateNullPosition();
2294
2295 // Null positions are never ignored.
2296 if (focus_position->IsIgnored()) {
2297 focus_position = focus_position->AsUnignoredPosition(
2298 !data().sel_is_backward ? AXPositionAdjustmentBehavior::kMoveForward
2299 : AXPositionAdjustmentBehavior::kMoveBackward);
2300
2301 // Any selection endpoint that is inside a leaf node is expressed as a text
2302 // position in AXTreeData.
2303 if (focus_position->IsLeafTreePosition())
2304 focus_position = focus_position->AsTextPosition();
2305
2306 // We do not expect the selection to have an endpoint on an inline text
2307 // box as this will create issues with parts of the code that don't use
2308 // inline text boxes.
2309 if (focus_position->IsTextPosition() &&
2310 focus_position->GetAnchor()->data().role ==
2311 ax::mojom::Role::kInlineTextBox) {
2312 focus_position = focus_position->CreateParentPosition();
2313 }
2314
2315 switch (focus_position->kind()) {
2316 case AXPositionKind::NULL_POSITION:
2317 // If one of the selection endpoints is invalid, then both endpoints
2318 // should be unset.
2319 unignored_selection.anchor_object_id = AXNode::kInvalidAXID;
2320 unignored_selection.anchor_offset = -1;
2321 unignored_selection.anchor_affinity =
2322 ax::mojom::TextAffinity::kDownstream;
2323 unignored_selection.focus_object_id = AXNode::kInvalidAXID;
2324 unignored_selection.focus_offset = -1;
2325 unignored_selection.focus_affinity =
2326 ax::mojom::TextAffinity::kDownstream;
2327 return unignored_selection;
2328 case AXPositionKind::TREE_POSITION:
2329 unignored_selection.focus_object_id = focus_position->anchor_id();
2330 unignored_selection.focus_offset = focus_position->child_index();
2331 unignored_selection.focus_affinity =
2332 ax::mojom::TextAffinity::kDownstream;
2333 break;
2334 case AXPositionKind::TEXT_POSITION:
2335 unignored_selection.focus_object_id = focus_position->anchor_id();
2336 unignored_selection.focus_offset = focus_position->text_offset();
2337 unignored_selection.focus_affinity = focus_position->affinity();
2338 break;
2339 }
2340 }
2341
2342 return unignored_selection;
2343 }
2344
GetTreeUpdateInProgressState() const2345 bool AXTree::GetTreeUpdateInProgressState() const {
2346 return tree_update_in_progress_;
2347 }
2348
SetTreeUpdateInProgressState(bool set_tree_update_value)2349 void AXTree::SetTreeUpdateInProgressState(bool set_tree_update_value) {
2350 tree_update_in_progress_ = set_tree_update_value;
2351 }
2352
HasPaginationSupport() const2353 bool AXTree::HasPaginationSupport() const {
2354 return has_pagination_support_;
2355 }
2356
2357 } // namespace ui
2358