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 }  // namespace
  26
  27 // Intermediate state to keep track of during a tree update.
  28 struct AXTreeUpdateState {
  29   AXTreeUpdateState() : new_root(nullptr) {}
  30
  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   // The new root in this update, if any.
  41   AXNode* new_root;
  42 };
  43
  44 AXTreeDelegate::AXTreeDelegate() {
  45 }
  46
  47 AXTreeDelegate::~AXTreeDelegate() {
  48 }
  49
  50 AXTree::AXTree()
  51     : delegate_(NULL), root_(NULL) {
  52   AXNodeData root;
  53   root.id = -1;
  54   root.role = AX_ROLE_ROOT_WEB_AREA;
  55
  56   AXTreeUpdate<AXNodeData> initial_state;
  57   initial_state.nodes.push_back(root);
  58   CHECK(Unserialize(initial_state)) << error();
  59 }
  60
  61 AXTree::AXTree(const AXTreeUpdate<AXNodeData>& initial_state)
  62     : delegate_(NULL), root_(NULL) {
  63   CHECK(Unserialize(initial_state)) << error();
  64 }
  65
  66 AXTree::~AXTree() {
  67   if (root_)
  68     DestroyNodeAndSubtree(root_, nullptr);
  69 }
  70
  71 void AXTree::SetDelegate(AXTreeDelegate* delegate) {
  72   delegate_ = delegate;
  73 }
  74
  75 AXNode* AXTree::GetFromId(int32 id) const {
  76   base::hash_map<int32, AXNode*>::const_iterator iter = id_map_.find(id);
  77   return iter != id_map_.end() ? iter->second : NULL;
  78 }
  79
  80 bool AXTree::Unserialize(const AXTreeUpdate<AXNodeData>& update) {
  81   AXTreeUpdateState update_state;
  82   int32 old_root_id = root_ ? root_->id() : 0;
  83
  84   if (update.node_id_to_clear != 0) {
  85     AXNode* node = GetFromId(update.node_id_to_clear);
  86     if (!node) {
  87       error_ = base::StringPrintf("Bad node_id_to_clear: %d",
  88                                   update.node_id_to_clear);
  89       return false;
  90     }
  91     if (node == root_) {
  92       // Clear root_ before calling DestroySubtree so that root_ doesn't
  93       // ever point to an invalid node.
  94       AXNode* old_root = root_;
  95       root_ = nullptr;
  96       DestroySubtree(old_root, &update_state);
  97     } else {
  98       for (int i = 0; i < node->child_count(); ++i)
  99         DestroySubtree(node->ChildAtIndex(i), &update_state);
 100       std::vector<AXNode*> children;
 101       node->SwapChildren(children);
 102       update_state.pending_nodes.insert(node);
 103     }
 104   }
 105
 106   for (size_t i = 0; i < update.nodes.size(); ++i) {
 107     if (!UpdateNode(update.nodes[i], &update_state))
 108       return false;
 109   }
 110
 111   if (!update_state.pending_nodes.empty()) {
 112     error_ = "Nodes left pending by the update:";
 113     for (std::set<AXNode*>::iterator iter = update_state.pending_nodes.begin();
 114          iter != update_state.pending_nodes.end(); ++iter) {
 115       error_ += base::StringPrintf(" %d", (*iter)->id());
 116     }
 117     return false;
 118   }
 119
 120   if (delegate_) {
 121     std::set<AXNode*>& new_nodes = update_state.new_nodes;
 122     std::vector<AXTreeDelegate::Change> changes;
 123     changes.reserve(update.nodes.size());
 124     for (size_t i = 0; i < update.nodes.size(); ++i) {
 125       AXNode* node = GetFromId(update.nodes[i].id);
 126       if (new_nodes.find(node) != new_nodes.end()) {
 127         if (new_nodes.find(node->parent()) == new_nodes.end()) {
 128           changes.push_back(
 129               AXTreeDelegate::Change(node, AXTreeDelegate::SUBTREE_CREATED));
 130         } else {
 131           changes.push_back(
 132               AXTreeDelegate::Change(node, AXTreeDelegate::NODE_CREATED));
 133         }
 134       } else {
 135         changes.push_back(
 136             AXTreeDelegate::Change(node, AXTreeDelegate::NODE_CHANGED));
 137       }
 138     }
 139     delegate_->OnAtomicUpdateFinished(
 140         this, root_->id() != old_root_id, changes);
 141   }
 142
 143   return true;
 144 }
 145
 146 std::string AXTree::ToString() const {
 147   return TreeToStringHelper(root_, 0);
 148 }
 149
 150 AXNode* AXTree::CreateNode(AXNode* parent, int32 id, int32 index_in_parent) {
 151   AXNode* new_node = new AXNode(parent, id, index_in_parent);
 152   id_map_[new_node->id()] = new_node;
 153   if (delegate_)
 154     delegate_->OnNodeCreated(this, new_node);
 155   return new_node;
 156 }
 157
 158 bool AXTree::UpdateNode(const AXNodeData& src,
 159                         AXTreeUpdateState* update_state) {
 160   // This method updates one node in the tree based on serialized data
 161   // received in an AXTreeUpdate. See AXTreeUpdate for pre and post
 162   // conditions.
 163
 164   // Look up the node by id. If it's not found, then either the root
 165   // of the tree is being swapped, or we're out of sync with the source
 166   // and this is a serious error.
 167   AXNode* node = GetFromId(src.id);
 168   if (node) {
 169     update_state->pending_nodes.erase(node);
 170     node->SetData(src);
 171   } else {
 172     if (src.role != AX_ROLE_ROOT_WEB_AREA &&
 173         src.role != AX_ROLE_DESKTOP) {
 174       error_ = base::StringPrintf(
 175           "%d is not in the tree and not the new root", src.id);
 176       return false;
 177     }
 178     if (update_state->new_root) {
 179       error_ = "Tree update contains two new roots";
 180       return false;
 181     }
 182
 183     update_state->new_root = CreateNode(NULL, src.id, 0);
 184     node = update_state->new_root;
 185     update_state->new_nodes.insert(node);
 186     node->SetData(src);
 187   }
 188
 189   if (delegate_)
 190     delegate_->OnNodeChanged(this, node);
 191
 192   // First, delete nodes that used to be children of this node but aren't
 193   // anymore.
 194   if (!DeleteOldChildren(node, src.child_ids, update_state)) {
 195     if (update_state->new_root)
 196       DestroySubtree(update_state->new_root, update_state);
 197     return false;
 198   }
 199
 200   // Now build a new children vector, reusing nodes when possible,
 201   // and swap it in.
 202   std::vector<AXNode*> new_children;
 203   bool success = CreateNewChildVector(
 204       node, src.child_ids, &new_children, update_state);
 205   node->SwapChildren(new_children);
 206
 207   // Update the root of the tree if needed.
 208   if ((src.role == AX_ROLE_ROOT_WEB_AREA || src.role == AX_ROLE_DESKTOP) &&
 209       (!root_ || root_->id() != src.id)) {
 210     // Make sure root_ always points to something valid or null_, even inside
 211     // DestroySubtree.
 212     AXNode* old_root = root_;
 213     root_ = node;
 214     if (old_root)
 215       DestroySubtree(old_root, update_state);
 216   }
 217
 218   return success;
 219 }
 220
 221 void AXTree::DestroySubtree(AXNode* node,
 222                             AXTreeUpdateState* update_state) {
 223   if (delegate_)
 224     delegate_->OnSubtreeWillBeDeleted(this, node);
 225   DestroyNodeAndSubtree(node, update_state);
 226 }
 227
 228 void AXTree::DestroyNodeAndSubtree(AXNode* node,
 229                                    AXTreeUpdateState* update_state) {
 230   if (delegate_)
 231     delegate_->OnNodeWillBeDeleted(this, node);
 232   id_map_.erase(node->id());
 233   for (int i = 0; i < node->child_count(); ++i)
 234     DestroyNodeAndSubtree(node->ChildAtIndex(i), update_state);
 235   if (update_state) {
 236     update_state->pending_nodes.erase(node);
 237   }
 238   node->Destroy();
 239 }
 240
 241 bool AXTree::DeleteOldChildren(AXNode* node,
 242                                const std::vector<int32>& new_child_ids,
 243                                AXTreeUpdateState* update_state) {
 244   // Create a set of child ids in |src| for fast lookup, and return false
 245   // if a duplicate is found;
 246   std::set<int32> new_child_id_set;
 247   for (size_t i = 0; i < new_child_ids.size(); ++i) {
 248     if (new_child_id_set.find(new_child_ids[i]) != new_child_id_set.end()) {
 249       error_ = base::StringPrintf("Node %d has duplicate child id %d",
 250                                   node->id(), new_child_ids[i]);
 251       return false;
 252     }
 253     new_child_id_set.insert(new_child_ids[i]);
 254   }
 255
 256   // Delete the old children.
 257   const std::vector<AXNode*>& old_children = node->children();
 258   for (size_t i = 0; i < old_children.size(); ++i) {
 259     int old_id = old_children[i]->id();
 260     if (new_child_id_set.find(old_id) == new_child_id_set.end())
 261       DestroySubtree(old_children[i], update_state);
 262   }
 263
 264   return true;
 265 }
 266
 267 bool AXTree::CreateNewChildVector(AXNode* node,
 268                                   const std::vector<int32>& new_child_ids,
 269                                   std::vector<AXNode*>* new_children,
 270                                   AXTreeUpdateState* update_state) {
 271   bool success = true;
 272   for (size_t i = 0; i < new_child_ids.size(); ++i) {
 273     int32 child_id = new_child_ids[i];
 274     int32 index_in_parent = static_cast<int32>(i);
 275     AXNode* child = GetFromId(child_id);
 276     if (child) {
 277       if (child->parent() != node) {
 278         // This is a serious error - nodes should never be reparented.
 279         // If this case occurs, continue so this node isn't left in an
 280         // inconsistent state, but return failure at the end.
 281         error_ = base::StringPrintf(
 282             "Node %d reparented from %d to %d",
 283             child->id(),
 284             child->parent() ? child->parent()->id() : 0,
 285             node->id());
 286         success = false;
 287         continue;
 288       }
 289       child->SetIndexInParent(index_in_parent);
 290     } else {
 291       child = CreateNode(node, child_id, index_in_parent);
 292       update_state->pending_nodes.insert(child);
 293       update_state->new_nodes.insert(child);
 294     }
 295     new_children->push_back(child);
 296   }
 297
 298   return success;
 299 }
 300
 301 }  // namespace ui