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 <set> 9 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" 15 16 namespace ui { 17 18 struct ClientTreeNode; 19 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. 26 // 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. 29 // 30 // Usage: 31 // 32 // You must call SerializeChanges() every time a node in the tree changes, 33 // and send the generated AXTreeUpdate to the client. 34 // 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. 39 // 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. 46 // 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(); 59 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(); 64 65 // Serialize all changes to |node| and append them to |out_update|. 66 void SerializeChanges(AXSourceNode node, 67 AXTreeUpdate* out_update); 68 69 // Delete the client subtree for this node, ensuring that the subtree 70 // is re-serialized. 71 void DeleteClientSubtree(AXSourceNode node); 72 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); 80 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. 88 // 89 // Example 1: 90 // 91 // Client Tree Source tree | 92 // 1 1 | 93 // / \ / \ | 94 // 2 3 2 4 | 95 // 96 // LCA(source node 2, client node 2) is node 2. 97 // LCA(source node 3, client node 4) is node 1. 98 // 99 // Example 2: 100 // 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 | 109 // 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); 116 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); 122 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); 129 130 ClientTreeNode* ClientTreeNodeById(int32 id); 131 132 // Delete the given client tree node and recursively delete all of its 133 // descendants. 134 void DeleteClientSubtree(ClientTreeNode* client_node); 135 136 // Helper function, called recursively with each new node to serialize. 137 void SerializeChangedNodes(AXSourceNode node, 138 AXTreeUpdate* out_update); 139 140 // The tree source. 141 AXTreeSource<AXSourceNode>* tree_; 142 143 // Our representation of the client tree. 144 ClientTreeNode* client_root_; 145 146 // A map from IDs to nodes in the client tree. 147 base::hash_map<int32, ClientTreeNode*> client_id_map_; 148 }; 149 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; 159 }; 160 161 template<typename AXSourceNode> 162 AXTreeSerializer<AXSourceNode>::AXTreeSerializer( 163 AXTreeSource<AXSourceNode>* tree) 164 : tree_(tree), 165 client_root_(NULL) { 166 } 167 168 template<typename AXSourceNode> 169 AXTreeSerializer<AXSourceNode>::~AXTreeSerializer() { 170 Reset(); 171 } 172 173 template<typename AXSourceNode> 174 void AXTreeSerializer<AXSourceNode>::Reset() { 175 if (!client_root_) 176 return; 177 178 DeleteClientSubtree(client_root_); 179 client_id_map_.erase(client_root_->id); 180 delete client_root_; 181 client_root_ = NULL; 182 } 183 184 template<typename AXSourceNode> 185 void AXTreeSerializer<AXSourceNode>::ChangeTreeSourceForTesting( 186 AXTreeSource<AXSourceNode>* new_tree) { 187 tree_ = new_tree; 188 } 189 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(); 195 196 std::vector<AXSourceNode> ancestors; 197 while (tree_->IsValid(node)) { 198 ancestors.push_back(node); 199 node = tree_->GetParent(node); 200 } 201 202 std::vector<ClientTreeNode*> client_ancestors; 203 while (client_node) { 204 client_ancestors.push_back(client_node); 205 client_node = client_node->parent; 206 } 207 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; 218 } 219 lca = ancestors[source_index]; 220 source_index--; 221 client_index--; 222 } 223 return lca; 224 } 225 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)); 236 } 237 return LeastCommonAncestor(node, client_node); 238 } 239 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; 267 } 268 } 269 270 // This is a new child or reparented child, check it recursively. 271 if (AnyDescendantWasReparented(child, out_lca)) 272 result = true; 273 } 274 return result; 275 } 276 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; 285 } 286 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); 294 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; 303 } 304 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]; 321 } 322 client_lca->children.clear(); 323 } 324 } 325 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); 330 } 331 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); 337 } 338 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]; 346 } 347 client_node->children.clear(); 348 } 349 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. 361 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; 375 } 376 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); 387 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); 392 } 393 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; 412 } 413 } 414 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; 426 } 427 serialized_node->child_ids.clear(); 428 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); 437 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; 442 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); 455 } 456 } 457 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); 461 } 462 463 } // namespace ui 464 465 #endif // UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_ 466