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 #include "ui/accessibility/ax_tree.h" | 5 #include "ui/accessibility/ax_tree.h" |
6 | 6 |
7 #include <set> | 7 #include <set> |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 #include "base/strings/stringprintf.h" | 10 #include "base/strings/stringprintf.h" |
11 #include "ui/accessibility/ax_node.h" | 11 #include "ui/accessibility/ax_node.h" |
12 | 12 |
13 namespace ui { | 13 namespace ui { |
14 | 14 |
15 namespace { | 15 namespace { |
16 | 16 |
17 std::string TreeToStringHelper(AXNode* node, int indent) { | 17 std::string TreeToStringHelper(AXNode* node, int indent) { |
18 std::string result = std::string(2 * indent, ' '); | 18 std::string result = std::string(2 * indent, ' '); |
19 result += node->data().ToString() + "\n"; | 19 result += node->data().ToString() + "\n"; |
20 for (int i = 0; i < node->child_count(); ++i) | 20 for (int i = 0; i < node->child_count(); ++i) |
21 result += TreeToStringHelper(node->ChildAtIndex(i), indent + 1); | 21 result += TreeToStringHelper(node->ChildAtIndex(i), indent + 1); |
22 return result; | 22 return result; |
23 } | 23 } |
24 | 24 |
25 } // namespace | 25 } // namespace |
26 | 26 |
27 // Intermediate state to keep track of during a tree update. | 27 // Intermediate state to keep track of during a tree update. |
28 struct AXTreeUpdateState { | 28 struct AXTreeUpdateState { |
| 29 AXTreeUpdateState() : new_root(nullptr) {} |
| 30 |
29 // During an update, this keeps track of all nodes that have been | 31 // During an update, this keeps track of all nodes that have been |
30 // implicitly referenced as part of this update, but haven't been | 32 // implicitly referenced as part of this update, but haven't been |
31 // updated yet. It's an error if there are any pending nodes at the | 33 // updated yet. It's an error if there are any pending nodes at the |
32 // end of Unserialize. | 34 // end of Unserialize. |
33 std::set<AXNode*> pending_nodes; | 35 std::set<AXNode*> pending_nodes; |
34 | 36 |
35 // Keeps track of new nodes created during this update. | 37 // Keeps track of new nodes created during this update. |
36 std::set<AXNode*> new_nodes; | 38 std::set<AXNode*> new_nodes; |
| 39 |
| 40 // The new root in this update, if any. |
| 41 AXNode* new_root; |
37 }; | 42 }; |
38 | 43 |
39 AXTreeDelegate::AXTreeDelegate() { | 44 AXTreeDelegate::AXTreeDelegate() { |
40 } | 45 } |
41 | 46 |
42 AXTreeDelegate::~AXTreeDelegate() { | 47 AXTreeDelegate::~AXTreeDelegate() { |
43 } | 48 } |
44 | 49 |
45 AXTree::AXTree() | 50 AXTree::AXTree() |
46 : delegate_(NULL), root_(NULL) { | 51 : delegate_(NULL), root_(NULL) { |
47 AXNodeData root; | 52 AXNodeData root; |
48 root.id = -1; | 53 root.id = -1; |
49 root.role = AX_ROLE_ROOT_WEB_AREA; | 54 root.role = AX_ROLE_ROOT_WEB_AREA; |
50 | 55 |
51 AXTreeUpdate initial_state; | 56 AXTreeUpdate initial_state; |
52 initial_state.nodes.push_back(root); | 57 initial_state.nodes.push_back(root); |
53 CHECK(Unserialize(initial_state)) << error(); | 58 CHECK(Unserialize(initial_state)) << error(); |
54 } | 59 } |
55 | 60 |
56 AXTree::AXTree(const AXTreeUpdate& initial_state) | 61 AXTree::AXTree(const AXTreeUpdate& initial_state) |
57 : delegate_(NULL), root_(NULL) { | 62 : delegate_(NULL), root_(NULL) { |
58 CHECK(Unserialize(initial_state)) << error(); | 63 CHECK(Unserialize(initial_state)) << error(); |
59 } | 64 } |
60 | 65 |
61 AXTree::~AXTree() { | 66 AXTree::~AXTree() { |
62 if (root_) | 67 if (root_) |
63 DestroyNodeAndSubtree(root_); | 68 DestroyNodeAndSubtree(root_, nullptr); |
64 } | 69 } |
65 | 70 |
66 void AXTree::SetDelegate(AXTreeDelegate* delegate) { | 71 void AXTree::SetDelegate(AXTreeDelegate* delegate) { |
67 delegate_ = delegate; | 72 delegate_ = delegate; |
68 } | 73 } |
69 | 74 |
70 AXNode* AXTree::GetFromId(int32 id) const { | 75 AXNode* AXTree::GetFromId(int32 id) const { |
71 base::hash_map<int32, AXNode*>::const_iterator iter = id_map_.find(id); | 76 base::hash_map<int32, AXNode*>::const_iterator iter = id_map_.find(id); |
72 return iter != id_map_.end() ? iter->second : NULL; | 77 return iter != id_map_.end() ? iter->second : NULL; |
73 } | 78 } |
74 | 79 |
75 bool AXTree::Unserialize(const AXTreeUpdate& update) { | 80 bool AXTree::Unserialize(const AXTreeUpdate& update) { |
76 AXTreeUpdateState update_state; | 81 AXTreeUpdateState update_state; |
77 int32 old_root_id = root_ ? root_->id() : 0; | 82 int32 old_root_id = root_ ? root_->id() : 0; |
78 | 83 |
79 if (update.node_id_to_clear != 0) { | 84 if (update.node_id_to_clear != 0) { |
80 AXNode* node = GetFromId(update.node_id_to_clear); | 85 AXNode* node = GetFromId(update.node_id_to_clear); |
81 if (!node) { | 86 if (!node) { |
82 error_ = base::StringPrintf("Bad node_id_to_clear: %d", | 87 error_ = base::StringPrintf("Bad node_id_to_clear: %d", |
83 update.node_id_to_clear); | 88 update.node_id_to_clear); |
84 return false; | 89 return false; |
85 } | 90 } |
86 if (node == root_) { | 91 if (node == root_) { |
87 DestroySubtree(root_); | 92 DestroySubtree(root_, &update_state); |
88 root_ = NULL; | 93 root_ = NULL; |
89 } else { | 94 } else { |
90 for (int i = 0; i < node->child_count(); ++i) | 95 for (int i = 0; i < node->child_count(); ++i) |
91 DestroySubtree(node->ChildAtIndex(i)); | 96 DestroySubtree(node->ChildAtIndex(i), &update_state); |
92 std::vector<AXNode*> children; | 97 std::vector<AXNode*> children; |
93 node->SwapChildren(children); | 98 node->SwapChildren(children); |
94 update_state.pending_nodes.insert(node); | 99 update_state.pending_nodes.insert(node); |
95 } | 100 } |
96 } | 101 } |
97 | 102 |
98 for (size_t i = 0; i < update.nodes.size(); ++i) { | 103 for (size_t i = 0; i < update.nodes.size(); ++i) { |
99 if (!UpdateNode(update.nodes[i], &update_state)) | 104 if (!UpdateNode(update.nodes[i], &update_state)) |
100 return false; | 105 return false; |
101 } | 106 } |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
149 bool AXTree::UpdateNode(const AXNodeData& src, | 154 bool AXTree::UpdateNode(const AXNodeData& src, |
150 AXTreeUpdateState* update_state) { | 155 AXTreeUpdateState* update_state) { |
151 // This method updates one node in the tree based on serialized data | 156 // This method updates one node in the tree based on serialized data |
152 // received in an AXTreeUpdate. See AXTreeUpdate for pre and post | 157 // received in an AXTreeUpdate. See AXTreeUpdate for pre and post |
153 // conditions. | 158 // conditions. |
154 | 159 |
155 // Look up the node by id. If it's not found, then either the root | 160 // Look up the node by id. If it's not found, then either the root |
156 // of the tree is being swapped, or we're out of sync with the source | 161 // of the tree is being swapped, or we're out of sync with the source |
157 // and this is a serious error. | 162 // and this is a serious error. |
158 AXNode* node = GetFromId(src.id); | 163 AXNode* node = GetFromId(src.id); |
159 AXNode* new_root = NULL; | |
160 if (node) { | 164 if (node) { |
161 update_state->pending_nodes.erase(node); | 165 update_state->pending_nodes.erase(node); |
162 node->SetData(src); | 166 node->SetData(src); |
163 } else { | 167 } else { |
164 if (src.role != AX_ROLE_ROOT_WEB_AREA) { | 168 if (src.role != AX_ROLE_ROOT_WEB_AREA) { |
165 error_ = base::StringPrintf( | 169 error_ = base::StringPrintf( |
166 "%d is not in the tree and not the new root", src.id); | 170 "%d is not in the tree and not the new root", src.id); |
167 return false; | 171 return false; |
168 } | 172 } |
169 new_root = CreateNode(NULL, src.id, 0); | 173 if (update_state->new_root) { |
170 node = new_root; | 174 error_ = "Tree update contains two new roots"; |
| 175 return false; |
| 176 } |
| 177 |
| 178 update_state->new_root = CreateNode(NULL, src.id, 0); |
| 179 node = update_state->new_root; |
171 update_state->new_nodes.insert(node); | 180 update_state->new_nodes.insert(node); |
172 node->SetData(src); | 181 node->SetData(src); |
173 } | 182 } |
174 | 183 |
175 if (delegate_) | 184 if (delegate_) |
176 delegate_->OnNodeChanged(node); | 185 delegate_->OnNodeChanged(node); |
177 | 186 |
178 // First, delete nodes that used to be children of this node but aren't | 187 // First, delete nodes that used to be children of this node but aren't |
179 // anymore. | 188 // anymore. |
180 if (!DeleteOldChildren(node, src.child_ids)) { | 189 if (!DeleteOldChildren(node, src.child_ids, update_state)) { |
181 if (new_root) | 190 if (update_state->new_root) |
182 DestroySubtree(new_root); | 191 DestroySubtree(update_state->new_root, update_state); |
183 return false; | 192 return false; |
184 } | 193 } |
185 | 194 |
186 // Now build a new children vector, reusing nodes when possible, | 195 // Now build a new children vector, reusing nodes when possible, |
187 // and swap it in. | 196 // and swap it in. |
188 std::vector<AXNode*> new_children; | 197 std::vector<AXNode*> new_children; |
189 bool success = CreateNewChildVector( | 198 bool success = CreateNewChildVector( |
190 node, src.child_ids, &new_children, update_state); | 199 node, src.child_ids, &new_children, update_state); |
191 node->SwapChildren(new_children); | 200 node->SwapChildren(new_children); |
192 | 201 |
193 // Update the root of the tree if needed. | 202 // Update the root of the tree if needed. |
194 if (src.role == AX_ROLE_ROOT_WEB_AREA && | 203 if (src.role == AX_ROLE_ROOT_WEB_AREA && |
195 (!root_ || root_->id() != src.id)) { | 204 (!root_ || root_->id() != src.id)) { |
196 if (root_) | 205 if (root_) |
197 DestroySubtree(root_); | 206 DestroySubtree(root_, update_state); |
198 root_ = node; | 207 root_ = node; |
199 } | 208 } |
200 | 209 |
201 return success; | 210 return success; |
202 } | 211 } |
203 | 212 |
204 void AXTree::DestroySubtree(AXNode* node) { | 213 void AXTree::DestroySubtree(AXNode* node, |
| 214 AXTreeUpdateState* update_state) { |
205 if (delegate_) | 215 if (delegate_) |
206 delegate_->OnSubtreeWillBeDeleted(node); | 216 delegate_->OnSubtreeWillBeDeleted(node); |
207 DestroyNodeAndSubtree(node); | 217 DestroyNodeAndSubtree(node, update_state); |
208 } | 218 } |
209 | 219 |
210 void AXTree::DestroyNodeAndSubtree(AXNode* node) { | 220 void AXTree::DestroyNodeAndSubtree(AXNode* node, |
| 221 AXTreeUpdateState* update_state) { |
211 id_map_.erase(node->id()); | 222 id_map_.erase(node->id()); |
212 for (int i = 0; i < node->child_count(); ++i) | 223 for (int i = 0; i < node->child_count(); ++i) |
213 DestroyNodeAndSubtree(node->ChildAtIndex(i)); | 224 DestroyNodeAndSubtree(node->ChildAtIndex(i), update_state); |
214 if (delegate_) | 225 if (delegate_) |
215 delegate_->OnNodeWillBeDeleted(node); | 226 delegate_->OnNodeWillBeDeleted(node); |
| 227 if (update_state) { |
| 228 update_state->pending_nodes.erase(node); |
| 229 } |
216 node->Destroy(); | 230 node->Destroy(); |
217 } | 231 } |
218 | 232 |
219 bool AXTree::DeleteOldChildren(AXNode* node, | 233 bool AXTree::DeleteOldChildren(AXNode* node, |
220 const std::vector<int32>& new_child_ids) { | 234 const std::vector<int32>& new_child_ids, |
| 235 AXTreeUpdateState* update_state) { |
221 // Create a set of child ids in |src| for fast lookup, and return false | 236 // Create a set of child ids in |src| for fast lookup, and return false |
222 // if a duplicate is found; | 237 // if a duplicate is found; |
223 std::set<int32> new_child_id_set; | 238 std::set<int32> new_child_id_set; |
224 for (size_t i = 0; i < new_child_ids.size(); ++i) { | 239 for (size_t i = 0; i < new_child_ids.size(); ++i) { |
225 if (new_child_id_set.find(new_child_ids[i]) != new_child_id_set.end()) { | 240 if (new_child_id_set.find(new_child_ids[i]) != new_child_id_set.end()) { |
226 error_ = base::StringPrintf("Node %d has duplicate child id %d", | 241 error_ = base::StringPrintf("Node %d has duplicate child id %d", |
227 node->id(), new_child_ids[i]); | 242 node->id(), new_child_ids[i]); |
228 return false; | 243 return false; |
229 } | 244 } |
230 new_child_id_set.insert(new_child_ids[i]); | 245 new_child_id_set.insert(new_child_ids[i]); |
231 } | 246 } |
232 | 247 |
233 // Delete the old children. | 248 // Delete the old children. |
234 const std::vector<AXNode*>& old_children = node->children(); | 249 const std::vector<AXNode*>& old_children = node->children(); |
235 for (size_t i = 0; i < old_children.size(); ++i) { | 250 for (size_t i = 0; i < old_children.size(); ++i) { |
236 int old_id = old_children[i]->id(); | 251 int old_id = old_children[i]->id(); |
237 if (new_child_id_set.find(old_id) == new_child_id_set.end()) | 252 if (new_child_id_set.find(old_id) == new_child_id_set.end()) |
238 DestroySubtree(old_children[i]); | 253 DestroySubtree(old_children[i], update_state); |
239 } | 254 } |
240 | 255 |
241 return true; | 256 return true; |
242 } | 257 } |
243 | 258 |
244 bool AXTree::CreateNewChildVector(AXNode* node, | 259 bool AXTree::CreateNewChildVector(AXNode* node, |
245 const std::vector<int32>& new_child_ids, | 260 const std::vector<int32>& new_child_ids, |
246 std::vector<AXNode*>* new_children, | 261 std::vector<AXNode*>* new_children, |
247 AXTreeUpdateState* update_state) { | 262 AXTreeUpdateState* update_state) { |
248 bool success = true; | 263 bool success = true; |
(...skipping 20 matching lines...) Expand all Loading... |
269 update_state->pending_nodes.insert(child); | 284 update_state->pending_nodes.insert(child); |
270 update_state->new_nodes.insert(child); | 285 update_state->new_nodes.insert(child); |
271 } | 286 } |
272 new_children->push_back(child); | 287 new_children->push_back(child); |
273 } | 288 } |
274 | 289 |
275 return success; | 290 return success; |
276 } | 291 } |
277 | 292 |
278 } // namespace ui | 293 } // namespace ui |
OLD | NEW |