[telemetry] Short circuit Cloud Storage upload check if no hash files.
[chromium-blink-merge.git] / ui / accessibility / ax_tree.cc
blob17112742a424ce78d3d281e57fa253445a24d7c0
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;
19 for (int i = 0; i < indent; i++)
20 result += " ";
21 result += node->data().ToString() + "\n";
22 for (int i = 0; i < node->child_count(); ++i)
23 result += TreeToStringHelper(node->ChildAtIndex(i), indent + 1);
24 return result;
27 } // anonymous namespace
29 // Intermediate state to keep track of during a tree update.
30 struct AXTreeUpdateState {
31 // During an update, this keeps track of all nodes that have been
32 // implicitly referenced as part of this update, but haven't been
33 // updated yet. It's an error if there are any pending nodes at the
34 // end of Unserialize.
35 std::set<AXNode*> pending_nodes;
37 // Keeps track of new nodes created during this update.
38 std::set<AXNode*> new_nodes;
41 AXTreeDelegate::AXTreeDelegate() {
44 AXTreeDelegate::~AXTreeDelegate() {
47 AXTree::AXTree()
48 : delegate_(NULL), root_(NULL) {
49 AXNodeData root;
50 root.id = 0;
51 root.role = AX_ROLE_ROOT_WEB_AREA;
53 AXTreeUpdate initial_state;
54 initial_state.nodes.push_back(root);
55 CHECK(Unserialize(initial_state)) << error();
58 AXTree::AXTree(const AXTreeUpdate& initial_state)
59 : delegate_(NULL), root_(NULL) {
60 CHECK(Unserialize(initial_state)) << error();
63 AXTree::~AXTree() {
64 if (root_)
65 DestroyNodeAndSubtree(root_);
68 void AXTree::SetDelegate(AXTreeDelegate* delegate) {
69 delegate_ = delegate;
72 AXNode* AXTree::GetRoot() const {
73 return root_;
76 AXNode* AXTree::GetFromId(int32 id) const {
77 base::hash_map<int32, AXNode*>::const_iterator iter = id_map_.find(id);
78 return iter != id_map_.end() ? (iter->second) : NULL;
81 bool AXTree::Unserialize(const AXTreeUpdate& update) {
82 AXTreeUpdateState update_state;
83 int32 old_root_id = root_ ? root_->id() : 0;
85 if (update.node_id_to_clear != 0) {
86 AXNode* node = GetFromId(update.node_id_to_clear);
87 if (!node) {
88 error_ = base::StringPrintf("Bad node_id_to_clear: %d",
89 update.node_id_to_clear);
90 return false;
92 if (node == root_) {
93 DestroyNodeAndSubtree(root_);
94 root_ = NULL;
95 } else {
96 for (int i = 0; i < node->child_count(); ++i)
97 DestroyNodeAndSubtree(node->ChildAtIndex(i));
98 std::vector<AXNode*> children;
99 node->SwapChildren(children);
100 update_state.pending_nodes.insert(node);
104 for (size_t i = 0; i < update.nodes.size(); ++i) {
105 if (!UpdateNode(update.nodes[i], &update_state))
106 return false;
109 if (!update_state.pending_nodes.empty()) {
110 error_ = "Nodes left pending by the update:";
111 for (std::set<AXNode*>::iterator iter = update_state.pending_nodes.begin();
112 iter != update_state.pending_nodes.end(); ++iter) {
113 error_ += base::StringPrintf(" %d", (*iter)->id());
115 return false;
118 if (delegate_) {
119 for (size_t i = 0; i < update.nodes.size(); ++i) {
120 AXNode* node = GetFromId(update.nodes[i].id);
121 if (update_state.new_nodes.find(node) != update_state.new_nodes.end()) {
122 delegate_->OnNodeCreated(node);
123 update_state.new_nodes.erase(node);
124 } else {
125 delegate_->OnNodeChanged(node);
128 if (root_->id() != old_root_id)
129 delegate_->OnRootChanged(root_);
132 return true;
135 std::string AXTree::ToString() const {
136 return TreeToStringHelper(root_, 0);
139 AXNode* AXTree::CreateNode(AXNode* parent, int32 id, int32 index_in_parent) {
140 return new AXNode(parent, id, index_in_parent);
143 bool AXTree::UpdateNode(
144 const AXNodeData& src, AXTreeUpdateState* update_state) {
145 // This method updates one node in the tree based on serialized data
146 // received in an AXTreeUpdate. See AXTreeUpdate for pre and post
147 // conditions.
149 // Look up the node by id. If it's not found, then either the root
150 // of the tree is being swapped, or we're out of sync with the source
151 // and this is a serious error.
152 AXNode* node = GetFromId(src.id);
153 if (node) {
154 update_state->pending_nodes.erase(node);
155 } else {
156 if (src.role != AX_ROLE_ROOT_WEB_AREA) {
157 error_ = base::StringPrintf(
158 "%d is not in the tree and not the new root", src.id);
159 return false;
161 node = CreateAndInitializeNode(NULL, src.id, 0);
162 update_state->new_nodes.insert(node);
165 // Set the node's data.
166 node->SetData(src);
168 // First, delete nodes that used to be children of this node but aren't
169 // anymore.
170 if (!DeleteOldChildren(node, src.child_ids))
171 return false;
173 // Now build a new children vector, reusing nodes when possible,
174 // and swap it in.
175 std::vector<AXNode*> new_children;
176 bool success = CreateNewChildVector(
177 node, src.child_ids, &new_children, update_state);
178 node->SwapChildren(new_children);
180 // Update the root of the tree if needed.
181 if (src.role == AX_ROLE_ROOT_WEB_AREA &&
182 (!root_ || root_->id() != src.id)) {
183 if (root_)
184 DestroyNodeAndSubtree(root_);
185 root_ = node;
188 return success;
191 AXNode* AXTree::CreateAndInitializeNode(
192 AXNode* parent, int32 id, int32 index_in_parent) {
193 AXNode* node = CreateNode(parent, id, index_in_parent);
194 id_map_[node->id()] = node;
195 return node;
198 void AXTree::DestroyNodeAndSubtree(AXNode* node) {
199 id_map_.erase(node->id());
200 for (int i = 0; i < node->child_count(); ++i)
201 DestroyNodeAndSubtree(node->ChildAtIndex(i));
202 if (delegate_)
203 delegate_->OnNodeWillBeDeleted(node);
204 node->Destroy();
207 bool AXTree::DeleteOldChildren(AXNode* node,
208 const std::vector<int32> new_child_ids) {
209 // Create a set of child ids in |src| for fast lookup, and return false
210 // if a duplicate is found;
211 std::set<int32> new_child_id_set;
212 for (size_t i = 0; i < new_child_ids.size(); ++i) {
213 if (new_child_id_set.find(new_child_ids[i]) != new_child_id_set.end()) {
214 error_ = base::StringPrintf("Node %d has duplicate child id %d",
215 node->id(), new_child_ids[i]);
216 return false;
218 new_child_id_set.insert(new_child_ids[i]);
221 // Delete the old children.
222 const std::vector<AXNode*>& old_children = node->children();
223 for (size_t i = 0; i < old_children.size(); ++i) {
224 int old_id = old_children[i]->id();
225 if (new_child_id_set.find(old_id) == new_child_id_set.end())
226 DestroyNodeAndSubtree(old_children[i]);
229 return true;
232 bool AXTree::CreateNewChildVector(AXNode* node,
233 const std::vector<int32> new_child_ids,
234 std::vector<AXNode*>* new_children,
235 AXTreeUpdateState* update_state) {
236 bool success = true;
237 for (size_t i = 0; i < new_child_ids.size(); ++i) {
238 int32 child_id = new_child_ids[i];
239 int32 index_in_parent = static_cast<int32>(i);
240 AXNode* child = GetFromId(child_id);
241 if (child) {
242 if (child->parent() != node) {
243 // This is a serious error - nodes should never be reparented.
244 // If this case occurs, continue so this node isn't left in an
245 // inconsistent state, but return failure at the end.
246 error_ = base::StringPrintf(
247 "Node %d reparented from %d to %d",
248 child->id(),
249 child->parent() ? child->parent()->id() : 0,
250 node->id());
251 success = false;
252 continue;
254 child->SetIndexInParent(index_in_parent);
255 } else {
256 child = CreateAndInitializeNode(node, child_id, index_in_parent);
257 update_state->pending_nodes.insert(child);
258 update_state->new_nodes.insert(child);
260 new_children->push_back(child);
263 return success;
266 } // namespace ui