| OLD | NEW |
|---|
| (Empty) |
| 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_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
