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