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 13namespace ui { 14 15namespace { 16 17std::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. 28struct 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 39AXTreeDelegate::AXTreeDelegate() { 40} 41 42AXTreeDelegate::~AXTreeDelegate() { 43} 44 45AXTree::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 56AXTree::AXTree(const AXTreeUpdate& initial_state) 57 : delegate_(NULL), root_(NULL) { 58 CHECK(Unserialize(initial_state)) << error(); 59} 60 61AXTree::~AXTree() { 62 if (root_) 63 DestroyNodeAndSubtree(root_); 64} 65 66void AXTree::SetDelegate(AXTreeDelegate* delegate) { 67 delegate_ = delegate; 68} 69 70AXNode* AXTree::GetRoot() const { 71 return root_; 72} 73 74AXNode* 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 79bool 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 133std::string AXTree::ToString() const { 134 return TreeToStringHelper(root_, 0); 135} 136 137AXNode* 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 146bool 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 201void 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 210bool 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 235bool 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 270