ui/accessibility/ax_tree.cc

   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
  13 namespace ui {
  14
  15 namespace {
  16
  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;
  23 }
  24
  25 }  // anonymous namespace
  26
  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;
  34
  35   // Keeps track of new nodes created during this update.
  36   std::set<AXNode*> new_nodes;
  37 };
  38
  39 AXTreeDelegate::AXTreeDelegate() {
  40 }
  41
  42 AXTreeDelegate::~AXTreeDelegate() {
  43 }
  44
  45 AXTree::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
  56 AXTree::AXTree(const AXTreeUpdate& initial_state)
  57     : delegate_(NULL), root_(NULL) {
  58   CHECK(Unserialize(initial_state)) << error();
  59 }
  60
  61 AXTree::~AXTree() {
  62   if (root_)
  63     DestroyNodeAndSubtree(root_);
  64 }
  65
  66 void AXTree::SetDelegate(AXTreeDelegate* delegate) {
  67   delegate_ = delegate;
  68 }
  69
  70 AXNode* AXTree::GetRoot() const {
  71   return root_;
  72 }
  73
  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;
  77 }
  78
  79 bool 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       DestroySubtree(root_);
  92       root_ = NULL;
  93     } else {
  94       for (int i = 0; i < node->child_count(); ++i)
  95         DestroySubtree(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     std::set<AXNode*>& new_nodes = update_state.new_nodes;
 118     std::vector<AXTreeDelegate::Change> changes;
 119     changes.reserve(update.nodes.size());
 120     for (size_t i = 0; i < update.nodes.size(); ++i) {
 121       AXNode* node = GetFromId(update.nodes[i].id);
 122       if (new_nodes.find(node) != new_nodes.end()) {
 123         if (new_nodes.find(node->parent()) == new_nodes.end()) {
 124           changes.push_back(
 125               AXTreeDelegate::Change(node, AXTreeDelegate::SUBTREE_CREATED));
 126         } else {
 127           changes.push_back(
 128               AXTreeDelegate::Change(node, AXTreeDelegate::NODE_CREATED));
 129         }
 130       } else {
 131         changes.push_back(
 132             AXTreeDelegate::Change(node, AXTreeDelegate::NODE_CHANGED));
 133       }
 134     }
 135     delegate_->OnAtomicUpdateFinished(root_->id() != old_root_id, changes);
 136   }
 137
 138   return true;
 139 }
 140
 141 std::string AXTree::ToString() const {
 142   return TreeToStringHelper(root_, 0);
 143 }
 144
 145 AXNode* AXTree::CreateNode(AXNode* parent, int32 id, int32 index_in_parent) {
 146   AXNode* new_node = new AXNode(parent, id, index_in_parent);
 147   id_map_[new_node->id()] = new_node;
 148   if (delegate_)
 149     delegate_->OnNodeCreated(new_node);
 150   return new_node;
 151 }
 152
 153 bool AXTree::UpdateNode(const AXNodeData& src,
 154                         AXTreeUpdateState* update_state) {
 155   // This method updates one node in the tree based on serialized data
 156   // received in an AXTreeUpdate. See AXTreeUpdate for pre and post
 157   // conditions.
 158
 159   // Look up the node by id. If it's not found, then either the root
 160   // of the tree is being swapped, or we're out of sync with the source
 161   // and this is a serious error.
 162   AXNode* node = GetFromId(src.id);
 163   AXNode* new_root = NULL;
 164   if (node) {
 165     update_state->pending_nodes.erase(node);
 166     node->SetData(src);
 167   } else {
 168     if (src.role != AX_ROLE_ROOT_WEB_AREA) {
 169       error_ = base::StringPrintf(
 170           "%d is not in the tree and not the new root", src.id);
 171       return false;
 172     }
 173     new_root = CreateNode(NULL, src.id, 0);
 174     node = new_root;
 175     update_state->new_nodes.insert(node);
 176     node->SetData(src);
 177   }
 178
 179   if (delegate_)
 180     delegate_->OnNodeChanged(node);
 181
 182   // First, delete nodes that used to be children of this node but aren't
 183   // anymore.
 184   if (!DeleteOldChildren(node, src.child_ids)) {
 185     if (new_root)
 186       DestroySubtree(new_root);
 187     return false;
 188   }
 189
 190   // Now build a new children vector, reusing nodes when possible,
 191   // and swap it in.
 192   std::vector<AXNode*> new_children;
 193   bool success = CreateNewChildVector(
 194       node, src.child_ids, &new_children, update_state);
 195   node->SwapChildren(new_children);
 196
 197   // Update the root of the tree if needed.
 198   if (src.role == AX_ROLE_ROOT_WEB_AREA &&
 199       (!root_ || root_->id() != src.id)) {
 200     if (root_)
 201       DestroySubtree(root_);
 202     root_ = node;
 203   }
 204
 205   return success;
 206 }
 207
 208 void AXTree::DestroySubtree(AXNode* node) {
 209   if (delegate_)
 210     delegate_->OnSubtreeWillBeDeleted(node);
 211   DestroyNodeAndSubtree(node);
 212 }
 213
 214 void AXTree::DestroyNodeAndSubtree(AXNode* node) {
 215   id_map_.erase(node->id());
 216   for (int i = 0; i < node->child_count(); ++i)
 217     DestroyNodeAndSubtree(node->ChildAtIndex(i));
 218   if (delegate_)
 219     delegate_->OnNodeWillBeDeleted(node);
 220   node->Destroy();
 221 }
 222
 223 bool AXTree::DeleteOldChildren(AXNode* node,
 224                                const std::vector<int32>& new_child_ids) {
 225   // Create a set of child ids in |src| for fast lookup, and return false
 226   // if a duplicate is found;
 227   std::set<int32> new_child_id_set;
 228   for (size_t i = 0; i < new_child_ids.size(); ++i) {
 229     if (new_child_id_set.find(new_child_ids[i]) != new_child_id_set.end()) {
 230       error_ = base::StringPrintf("Node %d has duplicate child id %d",
 231                                   node->id(), new_child_ids[i]);
 232       return false;
 233     }
 234     new_child_id_set.insert(new_child_ids[i]);
 235   }
 236
 237   // Delete the old children.
 238   const std::vector<AXNode*>& old_children = node->children();
 239   for (size_t i = 0; i < old_children.size(); ++i) {
 240     int old_id = old_children[i]->id();
 241     if (new_child_id_set.find(old_id) == new_child_id_set.end())
 242       DestroySubtree(old_children[i]);
 243   }
 244
 245   return true;
 246 }
 247
 248 bool AXTree::CreateNewChildVector(AXNode* node,
 249                                   const std::vector<int32>& new_child_ids,
 250                                   std::vector<AXNode*>* new_children,
 251                                   AXTreeUpdateState* update_state) {
 252   bool success = true;
 253   for (size_t i = 0; i < new_child_ids.size(); ++i) {
 254     int32 child_id = new_child_ids[i];
 255     int32 index_in_parent = static_cast<int32>(i);
 256     AXNode* child = GetFromId(child_id);
 257     if (child) {
 258       if (child->parent() != node) {
 259         // This is a serious error - nodes should never be reparented.
 260         // If this case occurs, continue so this node isn't left in an
 261         // inconsistent state, but return failure at the end.
 262         error_ = base::StringPrintf(
 263             "Node %d reparented from %d to %d",
 264             child->id(),
 265             child->parent() ? child->parent()->id() : 0,
 266             node->id());
 267         success = false;
 268         continue;
 269       }
 270       child->SetIndexInParent(index_in_parent);
 271     } else {
 272       child = CreateNode(node, child_id, index_in_parent);
 273       update_state->pending_nodes.insert(child);
 274       update_state->new_nodes.insert(child);
 275     }
 276     new_children->push_back(child);
 277   }
 278
 279   return success;
 280 }
 281
 282 }  // namespace ui