| OLD | NEW |
| 1 // Copyright 2013 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_ | 5 #ifndef UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_ |
| 6 #define UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_ | 6 #define UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_ |
| 7 | 7 |
| 8 #include <stddef.h> |
| 9 #include <stdint.h> |
| 10 |
| 8 #include <set> | 11 #include <set> |
| 9 | 12 |
| 10 #include "base/containers/hash_tables.h" | 13 #include "base/containers/hash_tables.h" |
| 11 #include "base/logging.h" | 14 #include "base/logging.h" |
| 12 #include "base/stl_util.h" | 15 #include "base/stl_util.h" |
| 13 #include "ui/accessibility/ax_export.h" | 16 #include "ui/accessibility/ax_export.h" |
| 14 #include "ui/accessibility/ax_tree_source.h" | 17 #include "ui/accessibility/ax_tree_source.h" |
| 15 #include "ui/accessibility/ax_tree_update.h" | 18 #include "ui/accessibility/ax_tree_update.h" |
| 16 | 19 |
| 17 namespace ui { | 20 namespace ui { |
| (...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 133 // source node and client node. | 136 // source node and client node. |
| 134 AXSourceNode LeastCommonAncestor(AXSourceNode node); | 137 AXSourceNode LeastCommonAncestor(AXSourceNode node); |
| 135 | 138 |
| 136 // Walk the subtree rooted at |node| and return true if any nodes that | 139 // Walk the subtree rooted at |node| and return true if any nodes that |
| 137 // would be updated are being reparented. If so, update |out_lca| to point | 140 // would be updated are being reparented. If so, update |out_lca| to point |
| 138 // to the least common ancestor of the previous LCA and the previous | 141 // to the least common ancestor of the previous LCA and the previous |
| 139 // parent of the node being reparented. | 142 // parent of the node being reparented. |
| 140 bool AnyDescendantWasReparented(AXSourceNode node, | 143 bool AnyDescendantWasReparented(AXSourceNode node, |
| 141 AXSourceNode* out_lca); | 144 AXSourceNode* out_lca); |
| 142 | 145 |
| 143 ClientTreeNode* ClientTreeNodeById(int32 id); | 146 ClientTreeNode* ClientTreeNodeById(int32_t id); |
| 144 | 147 |
| 145 // Delete the given client tree node and recursively delete all of its | 148 // Delete the given client tree node and recursively delete all of its |
| 146 // descendants. | 149 // descendants. |
| 147 void DeleteClientSubtree(ClientTreeNode* client_node); | 150 void DeleteClientSubtree(ClientTreeNode* client_node); |
| 148 | 151 |
| 149 // Helper function, called recursively with each new node to serialize. | 152 // Helper function, called recursively with each new node to serialize. |
| 150 void SerializeChangedNodes( | 153 void SerializeChangedNodes( |
| 151 AXSourceNode node, | 154 AXSourceNode node, |
| 152 AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update); | 155 AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update); |
| 153 | 156 |
| 154 // Visit all of the descendants of |node| once. | 157 // Visit all of the descendants of |node| once. |
| 155 void WalkAllDescendants(AXSourceNode node); | 158 void WalkAllDescendants(AXSourceNode node); |
| 156 | 159 |
| 157 // The tree source. | 160 // The tree source. |
| 158 AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree_; | 161 AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree_; |
| 159 | 162 |
| 160 // The tree data most recently sent to the client. | 163 // The tree data most recently sent to the client. |
| 161 AXTreeData client_tree_data_; | 164 AXTreeData client_tree_data_; |
| 162 | 165 |
| 163 // Our representation of the client tree. | 166 // Our representation of the client tree. |
| 164 ClientTreeNode* client_root_; | 167 ClientTreeNode* client_root_; |
| 165 | 168 |
| 166 // A map from IDs to nodes in the client tree. | 169 // A map from IDs to nodes in the client tree. |
| 167 base::hash_map<int32, ClientTreeNode*> client_id_map_; | 170 base::hash_map<int32_t, ClientTreeNode*> client_id_map_; |
| 168 | 171 |
| 169 // The maximum number of nodes to serialize in a given call to | 172 // The maximum number of nodes to serialize in a given call to |
| 170 // SerializeChanges, or 0 if there's no maximum. | 173 // SerializeChanges, or 0 if there's no maximum. |
| 171 size_t max_node_count_; | 174 size_t max_node_count_; |
| 172 }; | 175 }; |
| 173 | 176 |
| 174 // In order to keep track of what nodes the client knows about, we keep a | 177 // In order to keep track of what nodes the client knows about, we keep a |
| 175 // representation of the client tree - just IDs and parent/child | 178 // representation of the client tree - just IDs and parent/child |
| 176 // relationships. | 179 // relationships. |
| 177 struct AX_EXPORT ClientTreeNode { | 180 struct AX_EXPORT ClientTreeNode { |
| 178 ClientTreeNode(); | 181 ClientTreeNode(); |
| 179 virtual ~ClientTreeNode(); | 182 virtual ~ClientTreeNode(); |
| 180 int32 id; | 183 int32_t id; |
| 181 ClientTreeNode* parent; | 184 ClientTreeNode* parent; |
| 182 std::vector<ClientTreeNode*> children; | 185 std::vector<ClientTreeNode*> children; |
| 183 }; | 186 }; |
| 184 | 187 |
| 185 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData> | 188 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData> |
| 186 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::AXTreeSerializer( | 189 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::AXTreeSerializer( |
| 187 AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree) | 190 AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree) |
| 188 : tree_(tree), client_root_(NULL), max_node_count_(0) {} | 191 : tree_(tree), client_root_(NULL), max_node_count_(0) {} |
| 189 | 192 |
| 190 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData> | 193 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData> |
| (...skipping 106 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 297 // This is a new child or reparented child, check it recursively. | 300 // This is a new child or reparented child, check it recursively. |
| 298 if (AnyDescendantWasReparented(child, out_lca)) | 301 if (AnyDescendantWasReparented(child, out_lca)) |
| 299 result = true; | 302 result = true; |
| 300 } | 303 } |
| 301 return result; | 304 return result; |
| 302 } | 305 } |
| 303 | 306 |
| 304 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData> | 307 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData> |
| 305 ClientTreeNode* | 308 ClientTreeNode* |
| 306 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::ClientTreeNodeById( | 309 AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::ClientTreeNodeById( |
| 307 int32 id) { | 310 int32_t id) { |
| 308 base::hash_map<int32, ClientTreeNode*>::iterator iter = | 311 base::hash_map<int32_t, ClientTreeNode*>::iterator iter = |
| 309 client_id_map_.find(id); | 312 client_id_map_.find(id); |
| 310 if (iter != client_id_map_.end()) | 313 if (iter != client_id_map_.end()) |
| 311 return iter->second; | 314 return iter->second; |
| 312 else | 315 else |
| 313 return NULL; | 316 return NULL; |
| 314 } | 317 } |
| 315 | 318 |
| 316 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData> | 319 template <typename AXSourceNode, typename AXNodeData, typename AXTreeData> |
| 317 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::SerializeChanges( | 320 void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::SerializeChanges( |
| 318 AXSourceNode node, | 321 AXSourceNode node, |
| (...skipping 104 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 423 client_node->parent = NULL; | 426 client_node->parent = NULL; |
| 424 client_id_map_[client_node->id] = client_node; | 427 client_id_map_[client_node->id] = client_node; |
| 425 } | 428 } |
| 426 | 429 |
| 427 // Iterate over the ids of the children of |node|. | 430 // Iterate over the ids of the children of |node|. |
| 428 // Create a set of the child ids so we can quickly look | 431 // Create a set of the child ids so we can quickly look |
| 429 // up which children are new and which ones were there before. | 432 // up which children are new and which ones were there before. |
| 430 // If we've hit the maximum number of serialized nodes, pretend | 433 // If we've hit the maximum number of serialized nodes, pretend |
| 431 // this node has no children but keep going so that we get | 434 // this node has no children but keep going so that we get |
| 432 // consistent results. | 435 // consistent results. |
| 433 base::hash_set<int32> new_child_ids; | 436 base::hash_set<int32_t> new_child_ids; |
| 434 std::vector<AXSourceNode> children; | 437 std::vector<AXSourceNode> children; |
| 435 if (max_node_count_ == 0 || out_update->nodes.size() < max_node_count_) { | 438 if (max_node_count_ == 0 || out_update->nodes.size() < max_node_count_) { |
| 436 tree_->GetChildren(node, &children); | 439 tree_->GetChildren(node, &children); |
| 437 } else if (max_node_count_ > 0) { | 440 } else if (max_node_count_ > 0) { |
| 438 static bool logged_once = false; | 441 static bool logged_once = false; |
| 439 if (!logged_once) { | 442 if (!logged_once) { |
| 440 LOG(WARNING) << "Warning: not serializing AX nodes after a max of " | 443 LOG(WARNING) << "Warning: not serializing AX nodes after a max of " |
| 441 << max_node_count_; | 444 << max_node_count_; |
| 442 logged_once = true; | 445 logged_once = true; |
| 443 } | 446 } |
| 444 } | 447 } |
| 445 for (size_t i = 0; i < children.size(); ++i) { | 448 for (size_t i = 0; i < children.size(); ++i) { |
| 446 AXSourceNode& child = children[i]; | 449 AXSourceNode& child = children[i]; |
| 447 int new_child_id = tree_->GetId(child); | 450 int new_child_id = tree_->GetId(child); |
| 448 new_child_ids.insert(new_child_id); | 451 new_child_ids.insert(new_child_id); |
| 449 | 452 |
| 450 // This is a sanity check - there shouldn't be any reparenting | 453 // This is a sanity check - there shouldn't be any reparenting |
| 451 // because we've already handled it above. | 454 // because we've already handled it above. |
| 452 ClientTreeNode* client_child = client_id_map_[new_child_id]; | 455 ClientTreeNode* client_child = client_id_map_[new_child_id]; |
| 453 CHECK(!client_child || client_child->parent == client_node); | 456 CHECK(!client_child || client_child->parent == client_node); |
| 454 } | 457 } |
| 455 | 458 |
| 456 // Go through the old children and delete subtrees for child | 459 // Go through the old children and delete subtrees for child |
| 457 // ids that are no longer present, and create a map from | 460 // ids that are no longer present, and create a map from |
| 458 // id to ClientTreeNode for the rest. It's important to delete | 461 // id to ClientTreeNode for the rest. It's important to delete |
| 459 // first in a separate pass so that nodes that are reparented | 462 // first in a separate pass so that nodes that are reparented |
| 460 // don't end up children of two different parents in the middle | 463 // don't end up children of two different parents in the middle |
| 461 // of an update, which can lead to a double-free. | 464 // of an update, which can lead to a double-free. |
| 462 base::hash_map<int32, ClientTreeNode*> client_child_id_map; | 465 base::hash_map<int32_t, ClientTreeNode*> client_child_id_map; |
| 463 std::vector<ClientTreeNode*> old_children; | 466 std::vector<ClientTreeNode*> old_children; |
| 464 old_children.swap(client_node->children); | 467 old_children.swap(client_node->children); |
| 465 for (size_t i = 0; i < old_children.size(); ++i) { | 468 for (size_t i = 0; i < old_children.size(); ++i) { |
| 466 ClientTreeNode* old_child = old_children[i]; | 469 ClientTreeNode* old_child = old_children[i]; |
| 467 int old_child_id = old_child->id; | 470 int old_child_id = old_child->id; |
| 468 if (new_child_ids.find(old_child_id) == new_child_ids.end()) { | 471 if (new_child_ids.find(old_child_id) == new_child_ids.end()) { |
| 469 client_id_map_.erase(old_child_id); | 472 client_id_map_.erase(old_child_id); |
| 470 DeleteClientSubtree(old_child); | 473 DeleteClientSubtree(old_child); |
| 471 delete old_child; | 474 delete old_child; |
| 472 } else { | 475 } else { |
| (...skipping 13 matching lines...) Expand all Loading... |
| 486 | 489 |
| 487 tree_->SerializeNode(node, serialized_node); | 490 tree_->SerializeNode(node, serialized_node); |
| 488 // TODO(dmazzoni/dtseng): Make the serializer not depend on roles to | 491 // TODO(dmazzoni/dtseng): Make the serializer not depend on roles to |
| 489 // identify the root. | 492 // identify the root. |
| 490 if (serialized_node->id == client_root_->id && !serialized_node->IsRoot()) | 493 if (serialized_node->id == client_root_->id && !serialized_node->IsRoot()) |
| 491 serialized_node->SetRoot(); | 494 serialized_node->SetRoot(); |
| 492 } | 495 } |
| 493 | 496 |
| 494 // Iterate over the children, serialize them, and update the ClientTreeNode | 497 // Iterate over the children, serialize them, and update the ClientTreeNode |
| 495 // data structure to reflect the new tree. | 498 // data structure to reflect the new tree. |
| 496 std::vector<int32> actual_serialized_node_child_ids; | 499 std::vector<int32_t> actual_serialized_node_child_ids; |
| 497 client_node->children.reserve(children.size()); | 500 client_node->children.reserve(children.size()); |
| 498 for (size_t i = 0; i < children.size(); ++i) { | 501 for (size_t i = 0; i < children.size(); ++i) { |
| 499 AXSourceNode& child = children[i]; | 502 AXSourceNode& child = children[i]; |
| 500 int child_id = tree_->GetId(child); | 503 int child_id = tree_->GetId(child); |
| 501 | 504 |
| 502 // Skip if the child isn't valid. | 505 // Skip if the child isn't valid. |
| 503 if (!tree_->IsValid(child)) | 506 if (!tree_->IsValid(child)) |
| 504 continue; | 507 continue; |
| 505 | 508 |
| 506 // Skip if the same child is included more than once. | 509 // Skip if the same child is included more than once. |
| (...skipping 26 matching lines...) Expand all Loading... |
| 533 AXSourceNode node) { | 536 AXSourceNode node) { |
| 534 std::vector<AXSourceNode> children; | 537 std::vector<AXSourceNode> children; |
| 535 tree_->GetChildren(node, &children); | 538 tree_->GetChildren(node, &children); |
| 536 for (size_t i = 0; i < children.size(); ++i) | 539 for (size_t i = 0; i < children.size(); ++i) |
| 537 WalkAllDescendants(children[i]); | 540 WalkAllDescendants(children[i]); |
| 538 } | 541 } |
| 539 | 542 |
| 540 } // namespace ui | 543 } // namespace ui |
| 541 | 544 |
| 542 #endif // UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_ | 545 #endif // UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_ |
| OLD | NEW |