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;
  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.
  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;
  36
  37   // Keeps track of new nodes created during this update.
  38   std::set<AXNode*> new_nodes;
  39 };
  40
  41 AXTreeDelegate::AXTreeDelegate() {
  42 }
  43
  44 AXTreeDelegate::~AXTreeDelegate() {
  45 }
  46
  47 AXTree::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
  58 AXTree::AXTree(const AXTreeUpdate& initial_state)
  59     : delegate_(NULL), root_(NULL) {
  60   CHECK(Unserialize(initial_state)) << error();
  61 }
  62
  63 AXTree::~AXTree() {
  64   if (root_)
  65     DestroyNodeAndSubtree(root_);
  66 }
  67
  68 void AXTree::SetDelegate(AXTreeDelegate* delegate) {
  69   delegate_ = delegate;
  70 }
  71
  72 AXNode* AXTree::GetRoot() const {
  73   return root_;
  74 }
  75
  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;
  79 }
  80
  81 bool 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
 135 std::string AXTree::ToString() const {
 136   return TreeToStringHelper(root_, 0);
 137 }
 138
 139 AXNode* AXTree::CreateNode(AXNode* parent, int32 id, int32 index_in_parent) {
 140   return new AXNode(parent, id, index_in_parent);
 141 }
 142
 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.
 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
 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;
 196 }
 197
 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();
 205 }
 206
 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;
 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
 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;
 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