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