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 |