ax_tree.cc revision a1401311d1ab56c4ed0a474bd38c108f75cb0cd9 
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;
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;
25}
26
27}  // anonymous namespace
28
29// Intermediate state to keep track of during a tree update.
30struct 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;
36
37  // Keeps track of new nodes created during this update.
38  std::set<AXNode*> new_nodes;
39};
40
41AXTreeDelegate::AXTreeDelegate() {
42}
43
44AXTreeDelegate::~AXTreeDelegate() {
45}
46
47AXTree::AXTree()
48    : delegate_(NULL), root_(NULL) {
49  AXNodeData root;
50  root.id = 0;
51  root.role = AX_ROLE_ROOT_WEB_AREA;
52
53  AXTreeUpdate initial_state;
54  initial_state.nodes.push_back(root);
55  CHECK(Unserialize(initial_state)) << error();
56}
57
58AXTree::AXTree(const AXTreeUpdate& initial_state)
59    : delegate_(NULL), root_(NULL) {
60  CHECK(Unserialize(initial_state)) << error();
61}
62
63AXTree::~AXTree() {
64  if (root_)
65    DestroyNodeAndSubtree(root_);
66}
67
68void AXTree::SetDelegate(AXTreeDelegate* delegate) {
69  delegate_ = delegate;
70}
71
72AXNode* AXTree::GetRoot() const {
73  return root_;
74}
75
76AXNode* 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;
79}
80
81bool AXTree::Unserialize(const AXTreeUpdate& update) {
82  AXTreeUpdateState update_state;
83  int32 old_root_id = root_ ? root_->id() : 0;
84
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;
91    }
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);
101    }
102  }
103
104  for (size_t i = 0; i < update.nodes.size(); ++i) {
105    if (!UpdateNode(update.nodes[i], &update_state))
106      return false;
107  }
108
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());
114    }
115    return false;
116  }
117
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);
126      }
127    }
128    if (root_->id() != old_root_id)
129      delegate_->OnRootChanged(root_);
130  }
131
132  return true;
133}
134
135std::string AXTree::ToString() const {
136  return TreeToStringHelper(root_, 0);
137}
138
139AXNode* AXTree::CreateNode(AXNode* parent, int32 id, int32 index_in_parent) {
140  return new AXNode(parent, id, index_in_parent);
141}
142
143bool 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.
148
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;
160    }
161    node = CreateAndInitializeNode(NULL, src.id, 0);
162    update_state->new_nodes.insert(node);
163  }
164
165  // Set the node's data.
166  node->SetData(src);
167
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;
172
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);
179
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;
186  }
187
188  return success;
189}
190
191AXNode* 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;
196}
197
198void 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();
205}
206
207bool 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;
217    }
218    new_child_id_set.insert(new_child_ids[i]);
219  }
220
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]);
227  }
228
229  return true;
230}
231
232bool 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;
253      }
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);
259    }
260    new_children->push_back(child);
261  }
262
263  return success;
264}
265
266}  // namespace ui
267