Updating trunk VERSION from 2139.0 to 2140.0
[chromium-blink-merge.git] / ui / accessibility / ax_tree_serializer.h
blobf1cbfcea1053760d218d8686fe310273c6a0f7e5
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.
5 #ifndef UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
6 #define UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
8 #include <set>
10 #include "base/containers/hash_tables.h"
11 #include "base/logging.h"
12 #include "base/stl_util.h"
13 #include "ui/accessibility/ax_tree_source.h"
14 #include "ui/accessibility/ax_tree_update.h"
16 namespace ui {
18 struct ClientTreeNode;
20 // AXTreeSerializer is a helper class that serializes incremental
21 // updates to an AXTreeSource as a AXTreeUpdate struct.
22 // These structs can be unserialized by a client object such as an
23 // AXTree. An AXTreeSerializer keeps track of the tree of node ids that its
24 // client is aware of so that it will never generate an AXTreeUpdate that
25 // results in an invalid tree.
27 // Every node in the source tree must have an id that's a unique positive
28 // integer, the same node must not appear twice.
30 // Usage:
32 // You must call SerializeChanges() every time a node in the tree changes,
33 // and send the generated AXTreeUpdate to the client.
35 // If a node is added, call SerializeChanges on its parent.
36 // If a node is removed, call SerializeChanges on its parent.
37 // If a whole new subtree is added, just call SerializeChanges on its root.
38 // If the root of the tree changes, call SerializeChanges on the new root.
40 // AXTreeSerializer will avoid re-serializing nodes that do not change.
41 // For example, if node 1 has children 2, 3, 4, 5 and then child 2 is
42 // removed and a new child 6 is added, the AXTreeSerializer will only
43 // update nodes 1 and 6 (and any children of node 6 recursively). It will
44 // assume that nodes 3, 4, and 5 are not modified unless you explicitly
45 // call SerializeChanges() on them.
47 // As long as the source tree has unique ids for every node and no loops,
48 // and as long as every update is applied to the client tree, AXTreeSerializer
49 // will continue to work. If the source tree makes a change but fails to
50 // call SerializeChanges properly, the trees may get out of sync - but
51 // because AXTreeSerializer always keeps track of what updates it's sent,
52 // it will never send an invalid update and the client tree will not break,
53 // it just may not contain all of the changes.
54 template<typename AXSourceNode>
55 class AXTreeSerializer {
56 public:
57 explicit AXTreeSerializer(AXTreeSource<AXSourceNode>* tree);
58 ~AXTreeSerializer();
60 // Throw out the internal state that keeps track of the nodes the client
61 // knows about. This has the effect that the next update will send the
62 // entire tree over because it assumes the client knows nothing.
63 void Reset();
65 // Serialize all changes to |node| and append them to |out_update|.
66 void SerializeChanges(AXSourceNode node,
67 AXTreeUpdate* out_update);
69 // Delete the client subtree for this node, ensuring that the subtree
70 // is re-serialized.
71 void DeleteClientSubtree(AXSourceNode node);
73 // Only for unit testing. Normally this class relies on getting a call
74 // to SerializeChanges() every time the source tree changes. For unit
75 // testing, it's convenient to create a static AXTree for the initial
76 // state and then call ChangeTreeSourceForTesting and then SerializeChanges
77 // to simulate the changes you'd get if a tree changed from the initial
78 // state to the second tree's state.
79 void ChangeTreeSourceForTesting(AXTreeSource<AXSourceNode>* new_tree);
81 private:
82 // Return the least common ancestor of a node in the source tree
83 // and a node in the client tree, or NULL if there is no such node.
84 // The least common ancestor is the closest ancestor to |node| (which
85 // may be |node| itself) that's in both the source tree and client tree,
86 // and for which both the source and client tree agree on their ancestor
87 // chain up to the root.
89 // Example 1:
91 // Client Tree Source tree |
92 // 1 1 |
93 // / \ / \ |
94 // 2 3 2 4 |
96 // LCA(source node 2, client node 2) is node 2.
97 // LCA(source node 3, client node 4) is node 1.
99 // Example 2:
101 // Client Tree Source tree |
102 // 1 1 |
103 // / \ / \ |
104 // 2 3 2 3 |
105 // / \ / / |
106 // 4 7 8 4 |
107 // / \ / \ |
108 // 5 6 5 6 |
110 // LCA(source node 8, client node 7) is node 2.
111 // LCA(source node 5, client node 5) is node 1.
112 // It's not node 5, because the two trees disagree on the parent of
113 // node 4, so the LCA is the first ancestor both trees agree on.
114 AXSourceNode LeastCommonAncestor(AXSourceNode node,
115 ClientTreeNode* client_node);
117 // Return the least common ancestor of |node| that's in the client tree.
118 // This just walks up the ancestors of |node| until it finds a node that's
119 // also in the client tree, and then calls LeastCommonAncestor on the
120 // source node and client node.
121 AXSourceNode LeastCommonAncestor(AXSourceNode node);
123 // Walk the subtree rooted at |node| and return true if any nodes that
124 // would be updated are being reparented. If so, update |out_lca| to point
125 // to the least common ancestor of the previous LCA and the previous
126 // parent of the node being reparented.
127 bool AnyDescendantWasReparented(AXSourceNode node,
128 AXSourceNode* out_lca);
130 ClientTreeNode* ClientTreeNodeById(int32 id);
132 // Delete the given client tree node and recursively delete all of its
133 // descendants.
134 void DeleteClientSubtree(ClientTreeNode* client_node);
136 // Helper function, called recursively with each new node to serialize.
137 void SerializeChangedNodes(AXSourceNode node,
138 AXTreeUpdate* out_update);
140 // The tree source.
141 AXTreeSource<AXSourceNode>* tree_;
143 // Our representation of the client tree.
144 ClientTreeNode* client_root_;
146 // A map from IDs to nodes in the client tree.
147 base::hash_map<int32, ClientTreeNode*> client_id_map_;
150 // In order to keep track of what nodes the client knows about, we keep a
151 // representation of the client tree - just IDs and parent/child
152 // relationships.
153 struct AX_EXPORT ClientTreeNode {
154 ClientTreeNode();
155 virtual ~ClientTreeNode();
156 int32 id;
157 ClientTreeNode* parent;
158 std::vector<ClientTreeNode*> children;
161 template<typename AXSourceNode>
162 AXTreeSerializer<AXSourceNode>::AXTreeSerializer(
163 AXTreeSource<AXSourceNode>* tree)
164 : tree_(tree),
165 client_root_(NULL) {
168 template<typename AXSourceNode>
169 AXTreeSerializer<AXSourceNode>::~AXTreeSerializer() {
170 Reset();
173 template<typename AXSourceNode>
174 void AXTreeSerializer<AXSourceNode>::Reset() {
175 if (!client_root_)
176 return;
178 DeleteClientSubtree(client_root_);
179 client_id_map_.erase(client_root_->id);
180 delete client_root_;
181 client_root_ = NULL;
184 template<typename AXSourceNode>
185 void AXTreeSerializer<AXSourceNode>::ChangeTreeSourceForTesting(
186 AXTreeSource<AXSourceNode>* new_tree) {
187 tree_ = new_tree;
190 template<typename AXSourceNode>
191 AXSourceNode AXTreeSerializer<AXSourceNode>::LeastCommonAncestor(
192 AXSourceNode node, ClientTreeNode* client_node) {
193 if (!tree_->IsValid(node) || client_node == NULL)
194 return tree_->GetNull();
196 std::vector<AXSourceNode> ancestors;
197 while (tree_->IsValid(node)) {
198 ancestors.push_back(node);
199 node = tree_->GetParent(node);
202 std::vector<ClientTreeNode*> client_ancestors;
203 while (client_node) {
204 client_ancestors.push_back(client_node);
205 client_node = client_node->parent;
208 // Start at the root. Keep going until the source ancestor chain and
209 // client ancestor chain disagree. The last node before they disagree
210 // is the LCA.
211 AXSourceNode lca = tree_->GetNull();
212 int source_index = static_cast<int>(ancestors.size() - 1);
213 int client_index = static_cast<int>(client_ancestors.size() - 1);
214 while (source_index >= 0 && client_index >= 0) {
215 if (tree_->GetId(ancestors[source_index]) !=
216 client_ancestors[client_index]->id) {
217 return lca;
219 lca = ancestors[source_index];
220 source_index--;
221 client_index--;
223 return lca;
226 template<typename AXSourceNode>
227 AXSourceNode AXTreeSerializer<AXSourceNode>::LeastCommonAncestor(
228 AXSourceNode node) {
229 // Walk up the tree until the source node's id also exists in the
230 // client tree, then call LeastCommonAncestor on those two nodes.
231 ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
232 while (tree_->IsValid(node) && !client_node) {
233 node = tree_->GetParent(node);
234 if (tree_->IsValid(node))
235 client_node = ClientTreeNodeById(tree_->GetId(node));
237 return LeastCommonAncestor(node, client_node);
240 template<typename AXSourceNode>
241 bool AXTreeSerializer<AXSourceNode>::AnyDescendantWasReparented(
242 AXSourceNode node, AXSourceNode* out_lca) {
243 bool result = false;
244 int id = tree_->GetId(node);
245 std::vector<AXSourceNode> children;
246 tree_->GetChildren(node, &children);
247 for (size_t i = 0; i < children.size(); ++i) {
248 AXSourceNode& child = children[i];
249 int child_id = tree_->GetId(child);
250 ClientTreeNode* client_child = ClientTreeNodeById(child_id);
251 if (client_child) {
252 if (!client_child->parent) {
253 // If the client child has no parent, it must have been the
254 // previous root node, so there is no LCA and we can exit early.
255 *out_lca = tree_->GetNull();
256 return true;
257 } else if (client_child->parent->id != id) {
258 // If the client child's parent is not this node, update the LCA
259 // and return true (reparenting was found).
260 *out_lca = LeastCommonAncestor(*out_lca, client_child);
261 result = true;
262 } else {
263 // This child is already in the client tree, we won't
264 // recursively serialize it so we don't need to check this
265 // subtree recursively for reparenting.
266 continue;
270 // This is a new child or reparented child, check it recursively.
271 if (AnyDescendantWasReparented(child, out_lca))
272 result = true;
274 return result;
277 template<typename AXSourceNode>
278 ClientTreeNode* AXTreeSerializer<AXSourceNode>::ClientTreeNodeById(int32 id) {
279 base::hash_map<int32, ClientTreeNode*>::iterator iter =
280 client_id_map_.find(id);
281 if (iter != client_id_map_.end())
282 return iter->second;
283 else
284 return NULL;
287 template<typename AXSourceNode>
288 void AXTreeSerializer<AXSourceNode>::SerializeChanges(
289 AXSourceNode node,
290 AXTreeUpdate* out_update) {
291 // If the node isn't in the client tree, we need to serialize starting
292 // with the LCA.
293 AXSourceNode lca = LeastCommonAncestor(node);
295 if (client_root_) {
296 bool need_delete = false;
297 if (tree_->IsValid(lca)) {
298 // Check for any reparenting within this subtree - if there is
299 // any, we need to delete and reserialize the whole subtree
300 // that contains the old and new parents of the reparented node.
301 if (AnyDescendantWasReparented(lca, &lca))
302 need_delete = true;
305 if (!tree_->IsValid(lca)) {
306 // If there's no LCA, just tell the client to destroy the whole
307 // tree and then we'll serialize everything from the new root.
308 out_update->node_id_to_clear = client_root_->id;
309 Reset();
310 } else if (need_delete) {
311 // Otherwise, if we need to reserialize a subtree, first we need
312 // to delete those nodes in our client tree so that
313 // SerializeChangedNodes() will be sure to send them again.
314 out_update->node_id_to_clear = tree_->GetId(lca);
315 ClientTreeNode* client_lca = ClientTreeNodeById(tree_->GetId(lca));
316 CHECK(client_lca);
317 for (size_t i = 0; i < client_lca->children.size(); ++i) {
318 client_id_map_.erase(client_lca->children[i]->id);
319 DeleteClientSubtree(client_lca->children[i]);
320 delete client_lca->children[i];
322 client_lca->children.clear();
326 // Serialize from the LCA, or from the root if there isn't one.
327 if (!tree_->IsValid(lca))
328 lca = tree_->GetRoot();
329 SerializeChangedNodes(lca, out_update);
332 template<typename AXSourceNode>
333 void AXTreeSerializer<AXSourceNode>::DeleteClientSubtree(AXSourceNode node) {
334 ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
335 if (client_node)
336 DeleteClientSubtree(client_node);
339 template<typename AXSourceNode>
340 void AXTreeSerializer<AXSourceNode>::DeleteClientSubtree(
341 ClientTreeNode* client_node) {
342 for (size_t i = 0; i < client_node->children.size(); ++i) {
343 client_id_map_.erase(client_node->children[i]->id);
344 DeleteClientSubtree(client_node->children[i]);
345 delete client_node->children[i];
347 client_node->children.clear();
350 template<typename AXSourceNode>
351 void AXTreeSerializer<AXSourceNode>::SerializeChangedNodes(
352 AXSourceNode node,
353 AXTreeUpdate* out_update) {
354 // This method has three responsibilities:
355 // 1. Serialize |node| into an AXNodeData, and append it to
356 // the AXTreeUpdate to be sent to the client.
357 // 2. Determine if |node| has any new children that the client doesn't
358 // know about yet, and call SerializeChangedNodes recursively on those.
359 // 3. Update our internal data structure that keeps track of what nodes
360 // the client knows about.
362 // First, find the ClientTreeNode for this id in our data structure where
363 // we keep track of what accessibility objects the client already knows
364 // about. If we don't find it, then this must be the new root of the
365 // accessibility tree.
366 int id = tree_->GetId(node);
367 ClientTreeNode* client_node = ClientTreeNodeById(id);
368 if (!client_node) {
369 Reset();
370 client_root_ = new ClientTreeNode();
371 client_node = client_root_;
372 client_node->id = id;
373 client_node->parent = NULL;
374 client_id_map_[client_node->id] = client_node;
377 // Iterate over the ids of the children of |node|.
378 // Create a set of the child ids so we can quickly look
379 // up which children are new and which ones were there before.
380 base::hash_set<int32> new_child_ids;
381 std::vector<AXSourceNode> children;
382 tree_->GetChildren(node, &children);
383 for (size_t i = 0; i < children.size(); ++i) {
384 AXSourceNode& child = children[i];
385 int new_child_id = tree_->GetId(child);
386 new_child_ids.insert(new_child_id);
388 // This is a sanity check - there shouldn't be any reparenting
389 // because we've already handled it above.
390 ClientTreeNode* client_child = client_id_map_[new_child_id];
391 CHECK(!client_child || client_child->parent == client_node);
394 // Go through the old children and delete subtrees for child
395 // ids that are no longer present, and create a map from
396 // id to ClientTreeNode for the rest. It's important to delete
397 // first in a separate pass so that nodes that are reparented
398 // don't end up children of two different parents in the middle
399 // of an update, which can lead to a double-free.
400 base::hash_map<int32, ClientTreeNode*> client_child_id_map;
401 std::vector<ClientTreeNode*> old_children;
402 old_children.swap(client_node->children);
403 for (size_t i = 0; i < old_children.size(); ++i) {
404 ClientTreeNode* old_child = old_children[i];
405 int old_child_id = old_child->id;
406 if (new_child_ids.find(old_child_id) == new_child_ids.end()) {
407 client_id_map_.erase(old_child_id);
408 DeleteClientSubtree(old_child);
409 delete old_child;
410 } else {
411 client_child_id_map[old_child_id] = old_child;
415 // Serialize this node. This fills in all of the fields in
416 // AXNodeData except child_ids, which we handle below.
417 out_update->nodes.push_back(AXNodeData());
418 AXNodeData* serialized_node = &out_update->nodes.back();
419 tree_->SerializeNode(node, serialized_node);
420 // TODO(dmazzoni/dtseng): Make the serializer not depend on roles to identify
421 // the root.
422 if (serialized_node->id == client_root_->id &&
423 (serialized_node->role != AX_ROLE_ROOT_WEB_AREA &&
424 serialized_node->role != AX_ROLE_DESKTOP)) {
425 serialized_node->role = AX_ROLE_ROOT_WEB_AREA;
427 serialized_node->child_ids.clear();
429 // Iterate over the children, make note of the ones that are new
430 // and need to be serialized, and update the ClientTreeNode
431 // data structure to reflect the new tree.
432 std::vector<AXSourceNode> children_to_serialize;
433 client_node->children.reserve(children.size());
434 for (size_t i = 0; i < children.size(); ++i) {
435 AXSourceNode& child = children[i];
436 int child_id = tree_->GetId(child);
438 // No need to do anything more with children that aren't new;
439 // the client will reuse its existing object.
440 if (new_child_ids.find(child_id) == new_child_ids.end())
441 continue;
443 new_child_ids.erase(child_id);
444 serialized_node->child_ids.push_back(child_id);
445 if (client_child_id_map.find(child_id) != client_child_id_map.end()) {
446 ClientTreeNode* reused_child = client_child_id_map[child_id];
447 client_node->children.push_back(reused_child);
448 } else {
449 ClientTreeNode* new_child = new ClientTreeNode();
450 new_child->id = child_id;
451 new_child->parent = client_node;
452 client_node->children.push_back(new_child);
453 client_id_map_[child_id] = new_child;
454 children_to_serialize.push_back(child);
458 // Serialize all of the new children, recursively.
459 for (size_t i = 0; i < children_to_serialize.size(); ++i)
460 SerializeChangedNodes(children_to_serialize[i], out_update);
463 } // namespace ui
465 #endif // UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_