| 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 #include "ui/accessibility/ax_tree.h" | |
| 6 | |
| 7 #include <set> | |
| 8 | |
| 9 #include "base/logging.h" | |
| 10 #include "base/strings/stringprintf.h" | |
| 11 #include "ui/accessibility/ax_node.h" | |
| 12 | |
| 13 namespace ui { | |
| 14 | |
| 15 namespace { | |
| 16 | |
| 17 std::string TreeToStringHelper(AXNode* node, int indent) { | |
| 18 std::string result = std::string(2 * indent, ' '); | |
| 19 result += node->data().ToString() + "\n"; | |
| 20 for (int i = 0; i < node->child_count(); ++i) | |
| 21 result += TreeToStringHelper(node->ChildAtIndex(i), indent + 1); | |
| 22 return result; | |
| 23 } | |
| 24 | |
| 25 } // anonymous namespace | |
| 26 | |
| 27 // Intermediate state to keep track of during a tree update. | |
| 28 struct AXTreeUpdateState { | |
| 29 // During an update, this keeps track of all nodes that have been | |
| 30 // 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 | |
| 32 // end of Unserialize. | |
| 33 std::set<AXNode*> pending_nodes; | |
| 34 | |
| 35 // Keeps track of new nodes created during this update. | |
| 36 std::set<AXNode*> new_nodes; | |
| 37 }; | |
| 38 | |
| 39 AXTreeDelegate::AXTreeDelegate() { | |
| 40 } | |
| 41 | |
| 42 AXTreeDelegate::~AXTreeDelegate() { | |
| 43 } | |
| 44 | |
| 45 AXTree::AXTree() | |
| 46 : delegate_(NULL), root_(NULL) { | |
| 47 AXNodeData root; | |
| 48 root.id = -1; | |
| 49 root.role = AX_ROLE_ROOT_WEB_AREA; | |
| 50 | |
| 51 AXTreeUpdate initial_state; | |
| 52 initial_state.nodes.push_back(root); | |
| 53 CHECK(Unserialize(initial_state)) << error(); | |
| 54 } | |
| 55 | |
| 56 AXTree::AXTree(const AXTreeUpdate& initial_state) | |
| 57 : delegate_(NULL), root_(NULL) { | |
| 58 CHECK(Unserialize(initial_state)) << error(); | |
| 59 } | |
| 60 | |
| 61 AXTree::~AXTree() { | |
| 62 if (root_) | |
| 63 DestroyNodeAndSubtree(root_); | |
| 64 } | |
| 65 | |
| 66 void AXTree::SetDelegate(AXTreeDelegate* delegate) { | |
| 67 delegate_ = delegate; | |
| 68 } | |
| 69 | |
| 70 AXNode* AXTree::GetRoot() const { | |
| 71 return root_; | |
| 72 } | |
| 73 | |
| 74 AXNode* AXTree::GetFromId(int32 id) const { | |
| 75 base::hash_map<int32, AXNode*>::const_iterator iter = id_map_.find(id); | |
| 76 return iter != id_map_.end() ? (iter->second) : NULL; | |
| 77 } | |
| 78 | |
| 79 bool AXTree::Unserialize(const AXTreeUpdate& update) { | |
| 80 AXTreeUpdateState update_state; | |
| 81 int32 old_root_id = root_ ? root_->id() : 0; | |
| 82 | |
| 83 if (update.node_id_to_clear != 0) { | |
| 84 AXNode* node = GetFromId(update.node_id_to_clear); | |
| 85 if (!node) { | |
| 86 error_ = base::StringPrintf("Bad node_id_to_clear: %d", | |
| 87 update.node_id_to_clear); | |
| 88 return false; | |
| 89 } | |
| 90 if (node == root_) { | |
| 91 DestroyNodeAndSubtree(root_); | |
| 92 root_ = NULL; | |
| 93 } else { | |
| 94 for (int i = 0; i < node->child_count(); ++i) | |
| 95 DestroyNodeAndSubtree(node->ChildAtIndex(i)); | |
| 96 std::vector<AXNode*> children; | |
| 97 node->SwapChildren(children); | |
| 98 update_state.pending_nodes.insert(node); | |
| 99 } | |
| 100 } | |
| 101 | |
| 102 for (size_t i = 0; i < update.nodes.size(); ++i) { | |
| 103 if (!UpdateNode(update.nodes[i], &update_state)) | |
| 104 return false; | |
| 105 } | |
| 106 | |
| 107 if (!update_state.pending_nodes.empty()) { | |
| 108 error_ = "Nodes left pending by the update:"; | |
| 109 for (std::set<AXNode*>::iterator iter = update_state.pending_nodes.begin(); | |
| 110 iter != update_state.pending_nodes.end(); ++iter) { | |
| 111 error_ += base::StringPrintf(" %d", (*iter)->id()); | |
| 112 } | |
| 113 return false; | |
| 114 } | |
| 115 | |
| 116 if (delegate_) { | |
| 117 for (size_t i = 0; i < update.nodes.size(); ++i) { | |
| 118 AXNode* node = GetFromId(update.nodes[i].id); | |
| 119 if (update_state.new_nodes.find(node) != update_state.new_nodes.end()) { | |
| 120 delegate_->OnNodeCreationFinished(node); | |
| 121 update_state.new_nodes.erase(node); | |
| 122 } else { | |
| 123 delegate_->OnNodeChangeFinished(node); | |
| 124 } | |
| 125 } | |
| 126 if (root_->id() != old_root_id) | |
| 127 delegate_->OnRootChanged(root_); | |
| 128 } | |
| 129 | |
| 130 return true; | |
| 131 } | |
| 132 | |
| 133 std::string AXTree::ToString() const { | |
| 134 return TreeToStringHelper(root_, 0); | |
| 135 } | |
| 136 | |
| 137 AXNode* AXTree::CreateNode( | |
| 138 AXNode* parent, int32 id, int32 index_in_parent) { | |
| 139 AXNode* new_node = new AXNode(parent, id, index_in_parent); | |
| 140 id_map_[new_node->id()] = new_node; | |
| 141 if (delegate_) | |
| 142 delegate_->OnNodeCreated(new_node); | |
| 143 return new_node; | |
| 144 } | |
| 145 | |
| 146 bool AXTree::UpdateNode( | |
| 147 const AXNodeData& src, AXTreeUpdateState* update_state) { | |
| 148 // This method updates one node in the tree based on serialized data | |
| 149 // received in an AXTreeUpdate. See AXTreeUpdate for pre and post | |
| 150 // conditions. | |
| 151 | |
| 152 // Look up the node by id. If it's not found, then either the root | |
| 153 // of the tree is being swapped, or we're out of sync with the source | |
| 154 // and this is a serious error. | |
| 155 AXNode* node = GetFromId(src.id); | |
| 156 AXNode* new_root = NULL; | |
| 157 if (node) { | |
| 158 update_state->pending_nodes.erase(node); | |
| 159 node->SetData(src); | |
| 160 } else { | |
| 161 if (src.role != AX_ROLE_ROOT_WEB_AREA) { | |
| 162 error_ = base::StringPrintf( | |
| 163 "%d is not in the tree and not the new root", src.id); | |
| 164 return false; | |
| 165 } | |
| 166 new_root = CreateNode(NULL, src.id, 0); | |
| 167 node = new_root; | |
| 168 update_state->new_nodes.insert(node); | |
| 169 node->SetData(src); | |
| 170 } | |
| 171 | |
| 172 if (delegate_) | |
| 173 delegate_->OnNodeChanged(node); | |
| 174 | |
| 175 // First, delete nodes that used to be children of this node but aren't | |
| 176 // anymore. | |
| 177 if (!DeleteOldChildren(node, src.child_ids)) { | |
| 178 if (new_root) | |
| 179 DestroyNodeAndSubtree(new_root); | |
| 180 return false; | |
| 181 } | |
| 182 | |
| 183 // Now build a new children vector, reusing nodes when possible, | |
| 184 // and swap it in. | |
| 185 std::vector<AXNode*> new_children; | |
| 186 bool success = CreateNewChildVector( | |
| 187 node, src.child_ids, &new_children, update_state); | |
| 188 node->SwapChildren(new_children); | |
| 189 | |
| 190 // Update the root of the tree if needed. | |
| 191 if (src.role == AX_ROLE_ROOT_WEB_AREA && | |
| 192 (!root_ || root_->id() != src.id)) { | |
| 193 if (root_) | |
| 194 DestroyNodeAndSubtree(root_); | |
| 195 root_ = node; | |
| 196 } | |
| 197 | |
| 198 return success; | |
| 199 } | |
| 200 | |
| 201 void AXTree::DestroyNodeAndSubtree(AXNode* node) { | |
| 202 id_map_.erase(node->id()); | |
| 203 for (int i = 0; i < node->child_count(); ++i) | |
| 204 DestroyNodeAndSubtree(node->ChildAtIndex(i)); | |
| 205 if (delegate_) | |
| 206 delegate_->OnNodeWillBeDeleted(node); | |
| 207 node->Destroy(); | |
| 208 } | |
| 209 | |
| 210 bool AXTree::DeleteOldChildren(AXNode* node, | |
| 211 const std::vector<int32> new_child_ids) { | |
| 212 // Create a set of child ids in |src| for fast lookup, and return false | |
| 213 // if a duplicate is found; | |
| 214 std::set<int32> new_child_id_set; | |
| 215 for (size_t i = 0; i < new_child_ids.size(); ++i) { | |
| 216 if (new_child_id_set.find(new_child_ids[i]) != new_child_id_set.end()) { | |
| 217 error_ = base::StringPrintf("Node %d has duplicate child id %d", | |
| 218 node->id(), new_child_ids[i]); | |
| 219 return false; | |
| 220 } | |
| 221 new_child_id_set.insert(new_child_ids[i]); | |
| 222 } | |
| 223 | |
| 224 // Delete the old children. | |
| 225 const std::vector<AXNode*>& old_children = node->children(); | |
| 226 for (size_t i = 0; i < old_children.size(); ++i) { | |
| 227 int old_id = old_children[i]->id(); | |
| 228 if (new_child_id_set.find(old_id) == new_child_id_set.end()) | |
| 229 DestroyNodeAndSubtree(old_children[i]); | |
| 230 } | |
| 231 | |
| 232 return true; | |
| 233 } | |
| 234 | |
| 235 bool AXTree::CreateNewChildVector(AXNode* node, | |
| 236 const std::vector<int32> new_child_ids, | |
| 237 std::vector<AXNode*>* new_children, | |
| 238 AXTreeUpdateState* update_state) { | |
| 239 bool success = true; | |
| 240 for (size_t i = 0; i < new_child_ids.size(); ++i) { | |
| 241 int32 child_id = new_child_ids[i]; | |
| 242 int32 index_in_parent = static_cast<int32>(i); | |
| 243 AXNode* child = GetFromId(child_id); | |
| 244 if (child) { | |
| 245 if (child->parent() != node) { | |
| 246 // This is a serious error - nodes should never be reparented. | |
| 247 // If this case occurs, continue so this node isn't left in an | |
| 248 // inconsistent state, but return failure at the end. | |
| 249 error_ = base::StringPrintf( | |
| 250 "Node %d reparented from %d to %d", | |
| 251 child->id(), | |
| 252 child->parent() ? child->parent()->id() : 0, | |
| 253 node->id()); | |
| 254 success = false; | |
| 255 continue; | |
| 256 } | |
| 257 child->SetIndexInParent(index_in_parent); | |
| 258 } else { | |
| 259 child = CreateNode(node, child_id, index_in_parent); | |
| 260 update_state->pending_nodes.insert(child); | |
| 261 update_state->new_nodes.insert(child); | |
| 262 } | |
| 263 new_children->push_back(child); | |
| 264 } | |
| 265 | |
| 266 return success; | |
| 267 } | |
| 268 | |
| 269 } // namespace ui | |
| OLD | NEW |
|---|
Chromium Code Reviews
