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 #ifndef UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
6 #define UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
7
8 #include <stddef.h>
9 #include <stdint.h>
10
11 #include <unordered_map>
12 #include <unordered_set>
13 #include <vector>
14
15 #include "base/logging.h"
16 #include "ui/accessibility/ax_export.h"
17 #include "ui/accessibility/ax_tree_source.h"
18 #include "ui/accessibility/ax_tree_update.h"
19
20 namespace ui {
21
22 struct ClientTreeNode;
23
24 // AXTreeSerializer is a helper class that serializes incremental
25 // updates to an AXTreeSource as a AXTreeUpdate struct.
26 // These structs can be unserialized by a client object such as an
27 // AXTree. An AXTreeSerializer keeps track of the tree of node ids that its
28 // client is aware of so that it will never generate an AXTreeUpdate that
29 // results in an invalid tree.
30 //
31 // Every node in the source tree must have an id that's a unique positive
32 // integer, the same node must not appear twice.
33 //
34 // Usage:
35 //
36 // You must call SerializeChanges() every time a node in the tree changes,
37 // and send the generated AXTreeUpdate to the client. Changes to the
38 // AXTreeData, if any, are also automatically included in the AXTreeUpdate.
39 //
40 // If a node is added, call SerializeChanges on its parent.
41 // If a node is removed, call SerializeChanges on its parent.
42 // If a whole new subtree is added, just call SerializeChanges on its root.
43 // If the root of the tree changes, call SerializeChanges on the new root.
44 //
45 // AXTreeSerializer will avoid re-serializing nodes that do not change.
46 // For example, if node 1 has children 2, 3, 4, 5 and then child 2 is
47 // removed and a new child 6 is added, the AXTreeSerializer will only
48 // update nodes 1 and 6 (and any children of node 6 recursively). It will
49 // assume that nodes 3, 4, and 5 are not modified unless you explicitly
50 // call SerializeChanges() on them.
51 //
52 // As long as the source tree has unique ids for every node and no loops,
53 // and as long as every update is applied to the client tree, AXTreeSerializer
54 // will continue to work. If the source tree makes a change but fails to
55 // call SerializeChanges properly, the trees may get out of sync - but
56 // because AXTreeSerializer always keeps track of what updates it's sent,
57 // it will never send an invalid update and the client tree will not break,
58 // it just may not contain all of the changes.
59 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
60 class AXTreeSerializer {
61 public:
62 explicit AXTreeSerializer(
63 AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree);
64 ~AXTreeSerializer();
65
66 // Throw out the internal state that keeps track of the nodes the client
67 // knows about. This has the effect that the next update will send the
68 // entire tree over because it assumes the client knows nothing.
69 void Reset();
70
71 // Sets the maximum number of nodes that will be serialized, or zero
72 // for no maximum. This is not a hard maximum - once it hits or
73 // exceeds this maximum it stops walking the children of nodes, but
74 // it may exceed this value a bit in order to create a consistent
75 // tree.
set_max_node_count(size_t max_node_count)76 void set_max_node_count(size_t max_node_count) {
77 max_node_count_ = max_node_count;
78 }
79
80 // Serialize all changes to |node| and append them to |out_update|.
81 // Returns true on success. On failure, returns false and calls Reset();
82 // this only happens when the source tree has a problem like duplicate
83 // ids or changing during serialization.
84 bool SerializeChanges(AXSourceNode node,
85 AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update);
86
87 // Invalidate the subtree rooted at this node, ensuring that the whole
88 // subtree is re-serialized the next time any of those nodes end up
89 // being serialized.
90 void InvalidateSubtree(AXSourceNode node);
91
92 // Return whether or not this node is in the client tree. If you call
93 // this immediately after serializing, this indicates whether a given
94 // node is in the set of nodes that the client (the recipient of
95 // the AXTreeUpdates) is aware of.
96 //
97 // For example, you could use this to determine if a given node is
98 // reachable. If one of its ancestors is hidden and it was pruned
99 // from the accessibility tree, this would return false.
100 bool IsInClientTree(AXSourceNode node);
101
102 // Only for unit testing. Normally this class relies on getting a call
103 // to SerializeChanges() every time the source tree changes. For unit
104 // testing, it's convenient to create a static AXTree for the initial
105 // state and then call ChangeTreeSourceForTesting and then SerializeChanges
106 // to simulate the changes you'd get if a tree changed from the initial
107 // state to the second tree's state.
108 void ChangeTreeSourceForTesting(
109 AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* new_tree);
110
111 private:
112 // Return the least common ancestor of a node in the source tree
113 // and a node in the client tree, or nullptr if there is no such node.
114 // The least common ancestor is the closest ancestor to |node| (which
115 // may be |node| itself) that's in both the source tree and client tree,
116 // and for which both the source and client tree agree on their ancestor
117 // chain up to the root.
118 //
119 // Example 1:
120 //
121 // Client Tree Source tree |
122 // 1 1 |
123 // / \ / \ |
124 // 2 3 2 4 |
125 //
126 // LCA(source node 2, client node 2) is node 2.
127 // LCA(source node 3, client node 4) is node 1.
128 //
129 // Example 2:
130 //
131 // Client Tree Source tree |
132 // 1 1 |
133 // / \ / \ |
134 // 2 3 2 3 |
135 // / \ / / |
136 // 4 7 8 4 |
137 // / \ / \ |
138 // 5 6 5 6 |
139 //
140 // LCA(source node 8, client node 7) is node 2.
141 // LCA(source node 5, client node 5) is node 1.
142 // It's not node 5, because the two trees disagree on the parent of
143 // node 4, so the LCA is the first ancestor both trees agree on.
144 AXSourceNode LeastCommonAncestor(AXSourceNode node,
145 ClientTreeNode* client_node);
146
147 // Return the least common ancestor of |node| that's in the client tree.
148 // This just walks up the ancestors of |node| until it finds a node that's
149 // also in the client tree and not inside an invalid subtree, and then calls
150 // LeastCommonAncestor on the source node and client node.
151 AXSourceNode LeastCommonAncestor(AXSourceNode node);
152
153 // Walk the subtree rooted at |node| and return true if any nodes that
154 // would be updated are being reparented. If so, update |out_lca| to point
155 // to the least common ancestor of the previous LCA and the previous
156 // parent of the node being reparented.
157 bool AnyDescendantWasReparented(AXSourceNode node,
158 AXSourceNode* out_lca);
159
160 ClientTreeNode* ClientTreeNodeById(int32_t id);
161
162 // Invalidate the subtree rooted at this node.
163 void InvalidateClientSubtree(ClientTreeNode* client_node);
164
165 // Delete all descendants of this node.
166 void DeleteDescendants(ClientTreeNode* client_node);
167
168 // Delete the client subtree rooted at this node.
169 void DeleteClientSubtree(ClientTreeNode* client_node);
170
171 // Helper function, called recursively with each new node to serialize.
172 bool SerializeChangedNodes(
173 AXSourceNode node,
174 AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update);
175
176 // Visit all of the descendants of |node| once.
177 void WalkAllDescendants(AXSourceNode node);
178
179 // Delete the entire client subtree but don't set the did_reset_ flag
180 // like when Reset() is called.
181 void InternalReset();
182
183 ClientTreeNode* GetClientTreeNodeParent(ClientTreeNode* obj);
184
185 // The tree source.
186 AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree_;
187
188 // The tree data most recently sent to the client.
189 AXTreeData client_tree_data_;
190
191 // Our representation of the client tree.
192 ClientTreeNode* client_root_ = nullptr;
193
194 // A map from IDs to nodes in the client tree.
195 std::unordered_map<int32_t, ClientTreeNode*> client_id_map_;
196
197 // The maximum number of nodes to serialize in a given call to
198 // SerializeChanges, or 0 if there's no maximum.
199 size_t max_node_count_ = 0;
200
201 // Keeps track of if Reset() was called. If so, we need to always
202 // explicitly set node_id_to_clear to ensure that the next serialized
203 // tree is treated as a completely new tree and not a partial update.
204 bool did_reset_ = false;
205 };
206
207 // In order to keep track of what nodes the client knows about, we keep a
208 // representation of the client tree - just IDs and parent/child
209 // relationships, and a marker indicating whether it's been invalidated.
210 struct AX_EXPORT ClientTreeNode {
211 ClientTreeNode();
212 virtual ~ClientTreeNode();
213 int32_t id;
214 ClientTreeNode* parent;
215 std::vector<ClientTreeNode*> children;
216 bool ignored;
217 bool invalid;
218 };
219
220 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
AXTreeSerializer(AXTreeSource<AXSourceNode,AXNodeData,AXTreeData> * tree)221 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::AXTreeSerializer(
222 AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree)
223 : tree_(tree) {}
224
225 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
~AXTreeSerializer()226 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::~AXTreeSerializer() {
227 Reset();
228 }
229
230 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
Reset()231 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::Reset() {
232 InternalReset();
233 did_reset_ = true;
234 }
235
236 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
InternalReset()237 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::InternalReset() {
238 client_tree_data_ = AXTreeData();
239
240 // Normally we use DeleteClientSubtree to remove nodes from the tree,
241 // but Reset() needs to work even if the tree is in a broken state.
242 // Instead, iterate over |client_id_map_| to ensure we clear all nodes and
243 // start from scratch.
244 for (auto&& item : client_id_map_)
245 delete item.second;
246 client_id_map_.clear();
247 client_root_ = nullptr;
248 }
249
250 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
251 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
ChangeTreeSourceForTesting(AXTreeSource<AXSourceNode,AXNodeData,AXTreeData> * new_tree)252 ChangeTreeSourceForTesting(
253 AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* new_tree) {
254 tree_ = new_tree;
255 }
256
257 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
258 AXSourceNode
LeastCommonAncestor(AXSourceNode node,ClientTreeNode * client_node)259 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::LeastCommonAncestor(
260 AXSourceNode node,
261 ClientTreeNode* client_node) {
262 if (!tree_->IsValid(node) || client_node == nullptr)
263 return tree_->GetNull();
264
265 std::vector<AXSourceNode> ancestors;
266 while (tree_->IsValid(node)) {
267 ancestors.push_back(node);
268 node = tree_->GetParent(node);
269 }
270
271 std::vector<ClientTreeNode*> client_ancestors;
272 while (client_node) {
273 client_ancestors.push_back(client_node);
274 client_node = GetClientTreeNodeParent(client_node);
275 }
276
277 // Start at the root. Keep going until the source ancestor chain and
278 // client ancestor chain disagree. The last node before they disagree
279 // is the LCA.
280 AXSourceNode lca = tree_->GetNull();
281 int source_index = static_cast<int>(ancestors.size() - 1);
282 int client_index = static_cast<int>(client_ancestors.size() - 1);
283 while (source_index >= 0 && client_index >= 0) {
284 if (tree_->GetId(ancestors[source_index]) !=
285 client_ancestors[client_index]->id) {
286 return lca;
287 }
288 lca = ancestors[source_index];
289 source_index--;
290 client_index--;
291 }
292 return lca;
293 }
294
295 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
296 AXSourceNode
LeastCommonAncestor(AXSourceNode node)297 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::LeastCommonAncestor(
298 AXSourceNode node) {
299 // Walk up the tree until the source node's id also exists in the
300 // client tree, whose parent is not invalid, then call LeastCommonAncestor
301 // on those two nodes.
302 //
303 // Note that it's okay if |client_node| is invalid - the LCA can be the
304 // root of an invalid subtree, since we're going to serialize the
305 // LCA. But it's not okay if |client_node->parent| is invalid - that means
306 // that we're inside of an invalid subtree that all needs to be
307 // re-serialized, so the LCA should be higher.
308 ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
309 while (tree_->IsValid(node)) {
310 if (client_node) {
311 ClientTreeNode* parent = GetClientTreeNodeParent(client_node);
312 if (!parent || !parent->invalid)
313 break;
314 }
315 node = tree_->GetParent(node);
316 if (tree_->IsValid(node))
317 client_node = ClientTreeNodeById(tree_->GetId(node));
318 }
319 return LeastCommonAncestor(node, client_node);
320 }
321
322 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
323 bool AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
AnyDescendantWasReparented(AXSourceNode node,AXSourceNode * out_lca)324 AnyDescendantWasReparented(AXSourceNode node, AXSourceNode* out_lca) {
325 bool result = false;
326 int id = tree_->GetId(node);
327 std::vector<AXSourceNode> children;
328 tree_->GetChildren(node, &children);
329 for (size_t i = 0; i < children.size(); ++i) {
330 AXSourceNode& child = children[i];
331 int child_id = tree_->GetId(child);
332 ClientTreeNode* client_child = ClientTreeNodeById(child_id);
333 if (client_child) {
334 ClientTreeNode* parent = client_child->parent;
335 if (!parent) {
336 // If the client child has no parent, it must have been the
337 // previous root node, so there is no LCA and we can exit early.
338 *out_lca = tree_->GetNull();
339 return true;
340 } else if (parent->id != id) {
341 // If the client child's parent is not this node, update the LCA
342 // and return true (reparenting was found).
343 *out_lca = LeastCommonAncestor(*out_lca, client_child);
344 result = true;
345 continue;
346 } else if (!client_child->invalid) {
347 // This child is already in the client tree and valid, we won't
348 // recursively serialize it so we don't need to check this
349 // subtree recursively for reparenting.
350 // However, if the child is ignored, the children may now be
351 // considered as reparented, so continue recursion in that case.
352 if (!client_child->ignored)
353 continue;
354 }
355 }
356
357 // This is a new child or reparented child, check it recursively.
358 if (AnyDescendantWasReparented(child, out_lca))
359 result = true;
360 }
361 return result;
362 }
363
364 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
365 ClientTreeNode*
ClientTreeNodeById(int32_t id)366 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::ClientTreeNodeById(
367 int32_t id) {
368 std::unordered_map<int32_t, ClientTreeNode*>::iterator iter =
369 client_id_map_.find(id);
370 if (iter != client_id_map_.end())
371 return iter->second;
372 return nullptr;
373 }
374
375 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
376 ClientTreeNode*
GetClientTreeNodeParent(ClientTreeNode * obj)377 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::GetClientTreeNodeParent(
378 ClientTreeNode* obj) {
379 ClientTreeNode* parent = obj->parent;
380 #if DCHECK_IS_ON()
381 if (!parent)
382 return nullptr;
383 DCHECK(ClientTreeNodeById(parent->id)) << "Parent not in id map.";
384 #endif // DCHECK_IS_ON()
385 return parent;
386 }
387
388 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
SerializeChanges(AXSourceNode node,AXTreeUpdateBase<AXNodeData,AXTreeData> * out_update)389 bool AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::SerializeChanges(
390 AXSourceNode node,
391 AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update) {
392 // Send the tree data if it's changed since the last update, or if
393 // out_update->has_tree_data is already set to true.
394 AXTreeData new_tree_data;
395 if (tree_->GetTreeData(&new_tree_data) &&
396 (out_update->has_tree_data || new_tree_data != client_tree_data_)) {
397 out_update->has_tree_data = true;
398 out_update->tree_data = new_tree_data;
399 client_tree_data_ = new_tree_data;
400 }
401
402 // If the node isn't in the client tree, we need to serialize starting
403 // with the LCA.
404 AXSourceNode lca = LeastCommonAncestor(node);
405
406 // This loop computes the least common ancestor that includes the old
407 // and new parents of any nodes that have been reparented, and clears the
408 // whole client subtree of that LCA if necessary. If we do end up clearing
409 // any client nodes, keep looping because we have to search for more
410 // nodes that may have been reparented from this new LCA.
411 bool need_delete;
412 do {
413 need_delete = false;
414 if (client_root_) {
415 if (tree_->IsValid(lca)) {
416 // Check for any reparenting within this subtree - if there is
417 // any, we need to delete and reserialize the whole subtree
418 // that contains the old and new parents of the reparented node.
419 if (AnyDescendantWasReparented(lca, &lca))
420 need_delete = true;
421 }
422
423 if (!tree_->IsValid(lca)) {
424 // If there's no LCA, just tell the client to destroy the whole
425 // tree and then we'll serialize everything from the new root.
426 out_update->node_id_to_clear = client_root_->id;
427 InternalReset();
428 } else if (need_delete) {
429 // Otherwise, if we need to reserialize a subtree, first we need
430 // to delete those nodes in our client tree so that
431 // SerializeChangedNodes() will be sure to send them again.
432 out_update->node_id_to_clear = tree_->GetId(lca);
433 ClientTreeNode* client_lca = ClientTreeNodeById(tree_->GetId(lca));
434 CHECK(client_lca);
435 DeleteDescendants(client_lca);
436 }
437 }
438 } while (need_delete);
439
440 // Serialize from the LCA, or from the root if there isn't one.
441 if (!tree_->IsValid(lca))
442 lca = tree_->GetRoot();
443
444 // Work around flaky source trees where nodes don't figure out their
445 // correct parent/child relationships until you walk the whole tree once.
446 // Covered by this test in the content_browsertests suite:
447 // DumpAccessibilityTreeTest.AccessibilityAriaOwns.
448 WalkAllDescendants(lca);
449
450 if (!SerializeChangedNodes(lca, out_update))
451 return false;
452
453 // If we had a reset, ensure that the old tree is cleared before the client
454 // unserializes this update. If we didn't do this, there's a chance that
455 // treating this update as an incremental update could result in some
456 // reparenting.
457 if (did_reset_) {
458 out_update->node_id_to_clear = tree_->GetId(lca);
459 did_reset_ = false;
460 }
461
462 return true;
463 }
464
465 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
InvalidateSubtree(AXSourceNode node)466 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::InvalidateSubtree(
467 AXSourceNode node) {
468 ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
469 if (client_node)
470 InvalidateClientSubtree(client_node);
471 }
472
473 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
IsInClientTree(AXSourceNode node)474 bool AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::IsInClientTree(
475 AXSourceNode node) {
476 ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
477 return client_node ? !client_node->invalid : false;
478 }
479
480 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
481 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
InvalidateClientSubtree(ClientTreeNode * client_node)482 InvalidateClientSubtree(ClientTreeNode* client_node) {
483 client_node->invalid = true;
484 for (size_t i = 0; i < client_node->children.size(); ++i)
485 InvalidateClientSubtree(client_node->children[i]);
486 }
487
488 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
489 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
DeleteClientSubtree(ClientTreeNode * client_node)490 DeleteClientSubtree(ClientTreeNode* client_node) {
491 if (client_node == client_root_) {
492 Reset(); // Do not try to reuse a bad root later.
493 } else {
494 DeleteDescendants(client_node);
495 client_id_map_.erase(client_node->id);
496 delete client_node;
497 }
498 }
499
500 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
DeleteDescendants(ClientTreeNode * client_node)501 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::DeleteDescendants(
502 ClientTreeNode* client_node) {
503 for (size_t i = 0; i < client_node->children.size(); ++i)
504 DeleteClientSubtree(client_node->children[i]);
505 client_node->children.clear();
506 }
507
508 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
509 bool AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
SerializeChangedNodes(AXSourceNode node,AXTreeUpdateBase<AXNodeData,AXTreeData> * out_update)510 SerializeChangedNodes(
511 AXSourceNode node,
512 AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update) {
513 // This method has three responsibilities:
514 // 1. Serialize |node| into an AXNodeData, and append it to
515 // the AXTreeUpdate to be sent to the client.
516 // 2. Determine if |node| has any new children that the client doesn't
517 // know about yet, and call SerializeChangedNodes recursively on those.
518 // 3. Update our internal data structure that keeps track of what nodes
519 // the client knows about.
520
521 // First, find the ClientTreeNode for this id in our data structure where
522 // we keep track of what accessibility objects the client already knows
523 // about. If we don't find it, then this must be the new root of the
524 // accessibility tree.
525 int id = tree_->GetId(node);
526 ClientTreeNode* client_node = ClientTreeNodeById(id);
527 if (!client_node) {
528 if (client_root_)
529 Reset();
530 client_root_ = new ClientTreeNode();
531 client_node = client_root_;
532 client_node->id = id;
533 client_node->parent = nullptr;
534 client_id_map_[client_node->id] = client_node;
535 }
536
537 // We're about to serialize it, so mark it as valid.
538 client_node->invalid = false;
539 client_node->ignored = tree_->IsIgnored(node);
540
541 // Iterate over the ids of the children of |node|.
542 // Create a set of the child ids so we can quickly look
543 // up which children are new and which ones were there before.
544 // If we've hit the maximum number of serialized nodes, pretend
545 // this node has no children but keep going so that we get
546 // consistent results.
547 std::unordered_set<int32_t> new_ignored_ids;
548 std::unordered_set<int32_t> new_child_ids;
549 std::vector<AXSourceNode> children;
550 if (max_node_count_ == 0 || out_update->nodes.size() < max_node_count_) {
551 tree_->GetChildren(node, &children);
552 } else if (max_node_count_ > 0) {
553 static bool logged_once = false;
554 if (!logged_once) {
555 LOG(WARNING) << "Warning: not serializing AX nodes after a max of "
556 << max_node_count_;
557 logged_once = true;
558 }
559 }
560 for (size_t i = 0; i < children.size(); ++i) {
561 AXSourceNode& child = children[i];
562 int new_child_id = tree_->GetId(child);
563 new_child_ids.insert(new_child_id);
564 if (tree_->IsIgnored(child))
565 new_ignored_ids.insert(new_child_id);
566
567 // There shouldn't be any reparenting because we've already handled it
568 // above. If this happens, reset and return an error.
569
570 ClientTreeNode* client_child = ClientTreeNodeById(new_child_id);
571 if (client_child && GetClientTreeNodeParent(client_child) != client_node) {
572 DVLOG(1) << "Illegal reparenting detected";
573 #if defined(ADDRESS_SANITIZER)
574 // Wrapping this in ADDRESS_SANITIZER will cause it to run on
575 // clusterfuzz, which should help us narrow down the issue.
576 NOTREACHED() << "Illegal reparenting detected";
577 #endif
578 Reset();
579 return false;
580 }
581 }
582
583 // Go through the old children and delete subtrees for child
584 // ids that are no longer present, and create a map from
585 // id to ClientTreeNode for the rest. It's important to delete
586 // first in a separate pass so that nodes that are reparented
587 // don't end up children of two different parents in the middle
588 // of an update, which can lead to a double-free.
589 std::unordered_map<int32_t, ClientTreeNode*> client_child_id_map;
590 std::vector<ClientTreeNode*> old_children;
591 old_children.swap(client_node->children);
592 for (size_t i = 0; i < old_children.size(); ++i) {
593 ClientTreeNode* old_child = old_children[i];
594 int old_child_id = old_child->id;
595 if (new_child_ids.find(old_child_id) == new_child_ids.end()) {
596 DeleteClientSubtree(old_child);
597 } else {
598 client_child_id_map[old_child_id] = old_child;
599 }
600 }
601
602 // Serialize this node. This fills in all of the fields in
603 // AXNodeData except child_ids, which we handle below.
604 size_t serialized_node_index = out_update->nodes.size();
605 out_update->nodes.push_back(AXNodeData());
606 {
607 // Take the address of an element in a vector only within a limited
608 // scope because otherwise the pointer can become invalid if the
609 // vector is resized.
610 AXNodeData* serialized_node = &out_update->nodes[serialized_node_index];
611
612 tree_->SerializeNode(node, serialized_node);
613 if (serialized_node->id == client_root_->id)
614 out_update->root_id = serialized_node->id;
615 }
616
617 // Iterate over the children, serialize them, and update the ClientTreeNode
618 // data structure to reflect the new tree.
619 std::vector<int32_t> actual_serialized_node_child_ids;
620 client_node->children.reserve(children.size());
621 for (size_t i = 0; i < children.size(); ++i) {
622 AXSourceNode& child = children[i];
623 int child_id = tree_->GetId(child);
624
625 // Skip if the child isn't valid.
626 if (!tree_->IsValid(child))
627 continue;
628
629 // Skip if the same child is included more than once.
630 if (new_child_ids.find(child_id) == new_child_ids.end())
631 continue;
632
633 new_child_ids.erase(child_id);
634 actual_serialized_node_child_ids.push_back(child_id);
635 ClientTreeNode* reused_child = nullptr;
636 if (client_child_id_map.find(child_id) != client_child_id_map.end())
637 reused_child = ClientTreeNodeById(child_id);
638 if (reused_child) {
639 client_node->children.push_back(reused_child);
640 const bool ignored_state_changed =
641 reused_child->ignored !=
642 (new_ignored_ids.find(reused_child->id) != new_ignored_ids.end());
643 // Re-serialize it if the child is marked as invalid, otherwise
644 // we don't have to because the client already has it.
645 if (reused_child->invalid || ignored_state_changed) {
646 if (!SerializeChangedNodes(child, out_update))
647 return false;
648 }
649 } else {
650 ClientTreeNode* new_child = new ClientTreeNode();
651 new_child->id = child_id;
652 new_child->parent = client_node;
653 new_child->ignored = tree_->IsIgnored(child);
654 new_child->invalid = false;
655 client_node->children.push_back(new_child);
656 client_id_map_[child_id] = new_child;
657 if (!SerializeChangedNodes(child, out_update))
658 return false;
659 }
660 }
661
662 // Finally, update the child ids of this node to reflect the actual child
663 // ids that were valid during serialization.
664 out_update->nodes[serialized_node_index].child_ids.swap(
665 actual_serialized_node_child_ids);
666
667 return true;
668 }
669
670 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
WalkAllDescendants(AXSourceNode node)671 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::WalkAllDescendants(
672 AXSourceNode node) {
673 std::vector<AXSourceNode> children;
674 tree_->GetChildren(node, &children);
675 for (size_t i = 0; i < children.size(); ++i)
676 WalkAllDescendants(children[i]);
677 }
678
679 } // namespace ui
680
681 #endif // UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
682