Updating trunk VERSION from 2139.0 to 2140.0
[chromium-blink-merge.git] / ui / accessibility / ax_tree.cc
blobecfbae83005f21f4c19b24707a69c18fce6c4889
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.
5 #include "ui/accessibility/ax_tree.h"
7 #include <set>
9 #include "base/logging.h"
10 #include "base/strings/stringprintf.h"
11 #include "ui/accessibility/ax_node.h"
13 namespace ui {
15 namespace {
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;
25 } // anonymous namespace
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;
35 // Keeps track of new nodes created during this update.
36 std::set<AXNode*> new_nodes;
39 AXTreeDelegate::AXTreeDelegate() {
42 AXTreeDelegate::~AXTreeDelegate() {
45 AXTree::AXTree()
46 : delegate_(NULL), root_(NULL) {
47 AXNodeData root;
48 root.id = -1;
49 root.role = AX_ROLE_ROOT_WEB_AREA;
51 AXTreeUpdate initial_state;
52 initial_state.nodes.push_back(root);
53 CHECK(Unserialize(initial_state)) << error();
56 AXTree::AXTree(const AXTreeUpdate& initial_state)
57 : delegate_(NULL), root_(NULL) {
58 CHECK(Unserialize(initial_state)) << error();
61 AXTree::~AXTree() {
62 if (root_)
63 DestroyNodeAndSubtree(root_);
66 void AXTree::SetDelegate(AXTreeDelegate* delegate) {
67 delegate_ = delegate;
70 AXNode* AXTree::GetRoot() const {
71 return root_;
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;
79 bool AXTree::Unserialize(const AXTreeUpdate& update) {
80 AXTreeUpdateState update_state;
81 int32 old_root_id = root_ ? root_->id() : 0;
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;
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);
102 for (size_t i = 0; i < update.nodes.size(); ++i) {
103 if (!UpdateNode(update.nodes[i], &update_state))
104 return false;
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());
113 return false;
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);
126 if (root_->id() != old_root_id)
127 delegate_->OnRootChanged(root_);
130 return true;
133 std::string AXTree::ToString() const {
134 return TreeToStringHelper(root_, 0);
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;
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.
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;
166 new_root = CreateNode(NULL, src.id, 0);
167 node = new_root;
168 update_state->new_nodes.insert(node);
169 node->SetData(src);
172 if (delegate_)
173 delegate_->OnNodeChanged(node);
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;
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);
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;
198 return success;
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();
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;
221 new_child_id_set.insert(new_child_ids[i]);
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]);
232 return true;
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;
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);
263 new_children->push_back(child);
266 return success;
269 } // namespace ui