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 AXTree::AXTree()
  30     : root_(NULL) {
  31   AXNodeData root;
  32   root.id = 0;
  33   root.role = AX_ROLE_ROOT_WEB_AREA;
  34
  35   AXTreeUpdate initial_state;
  36   initial_state.nodes.push_back(root);
  37   CHECK(Unserialize(initial_state)) << error();
  38 }
  39
  40 AXTree::AXTree(const AXTreeUpdate& initial_state)
  41     : root_(NULL) {
  42   CHECK(Unserialize(initial_state)) << error();
  43 }
  44
  45 AXTree::~AXTree() {
  46   if (root_)
  47     DestroyNodeAndSubtree(root_);
  48 }
  49
  50 AXNode* AXTree::GetRoot() const {
  51   return root_;
  52 }
  53
  54 AXNode* AXTree::GetFromId(int32 id) const {
  55   base::hash_map<int32, AXNode*>::const_iterator iter = id_map_.find(id);
  56   return iter != id_map_.end() ? (iter->second) : NULL;
  57 }
  58
  59 bool AXTree::Unserialize(const AXTreeUpdate& update) {
  60   std::set<AXNode*> pending_nodes;
  61
  62   if (update.node_id_to_clear != 0) {
  63     AXNode* node = GetFromId(update.node_id_to_clear);
  64     if (!node) {
  65       error_ = base::StringPrintf("Bad node_id_to_clear: %d",
  66                                   update.node_id_to_clear);
  67       return false;
  68     }
  69     if (node == root_) {
  70       DestroyNodeAndSubtree(root_);
  71       root_ = NULL;
  72     } else {
  73       for (int i = 0; i < node->child_count(); ++i)
  74         DestroyNodeAndSubtree(node->ChildAtIndex(i));
  75       std::vector<AXNode*> children;
  76       node->SwapChildren(children);
  77       pending_nodes.insert(node);
  78     }
  79   }
  80
  81   for (size_t i = 0; i < update.nodes.size(); ++i) {
  82     if (!UpdateNode(update.nodes[i], &pending_nodes))
  83       return false;
  84   }
  85
  86   if (!pending_nodes.empty()) {
  87     error_ = "Nodes left pending by the update:";
  88     for (std::set<AXNode*>::iterator iter = pending_nodes.begin();
  89          iter != pending_nodes.end(); ++iter) {
  90       error_ += base::StringPrintf(" %d", (*iter)->id());
  91     }
  92     return false;
  93   }
  94
  95   return true;
  96 }
  97
  98 std::string AXTree::ToString() const {
  99   return TreeToStringHelper(root_, 0);
 100 }
 101
 102 AXNode* AXTree::CreateNode(AXNode* parent, int32 id, int32 index_in_parent) {
 103   return new AXNode(parent, id, index_in_parent);
 104 }
 105
 106 bool AXTree::UpdateNode(
 107     const AXNodeData& src, std::set<AXNode*>* pending_nodes) {
 108   // This method updates one node in the tree based on serialized data
 109   // received in an AXTreeUpdate. See AXTreeUpdate for pre and post
 110   // conditions.
 111
 112   // Look up the node by id. If it's not found, then either the root
 113   // of the tree is being swapped, or we're out of sync with the source
 114   // and this is a serious error.
 115   AXNode* node = GetFromId(src.id);
 116   if (node) {
 117     pending_nodes->erase(node);
 118   } else {
 119     if (src.role != AX_ROLE_ROOT_WEB_AREA) {
 120       error_ = base::StringPrintf(
 121           "%d is not in the tree and not the new root", src.id);
 122       return false;
 123     }
 124     node = CreateAndInitializeNode(NULL, src.id, 0);
 125   }
 126
 127   // Set the node's data.
 128   node->SetData(src);
 129
 130   // First, delete nodes that used to be children of this node but aren't
 131   // anymore.
 132   if (!DeleteOldChildren(node, src.child_ids))
 133     return false;
 134
 135   // Now build a new children vector, reusing nodes when possible,
 136   // and swap it in.
 137   std::vector<AXNode*> new_children;
 138   bool success = CreateNewChildVector(
 139       node, src.child_ids, &new_children, pending_nodes);
 140   node->SwapChildren(new_children);
 141
 142   // Update the root of the tree if needed.
 143   if (src.role == AX_ROLE_ROOT_WEB_AREA &&
 144       (!root_ || root_->id() != src.id)) {
 145     if (root_)
 146       DestroyNodeAndSubtree(root_);
 147     root_ = node;
 148     OnRootChanged();
 149   }
 150
 151   return success;
 152 }
 153
 154 void AXTree::OnRootChanged() {
 155 }
 156
 157 AXNode* AXTree::CreateAndInitializeNode(
 158     AXNode* parent, int32 id, int32 index_in_parent) {
 159   AXNode* node = CreateNode(parent, id, index_in_parent);
 160   id_map_[node->id()] = node;
 161   return node;
 162 }
 163
 164 void AXTree::DestroyNodeAndSubtree(AXNode* node) {
 165   id_map_.erase(node->id());
 166   for (int i = 0; i < node->child_count(); ++i)
 167     DestroyNodeAndSubtree(node->ChildAtIndex(i));
 168   node->Destroy();
 169 }
 170
 171 bool AXTree::DeleteOldChildren(AXNode* node,
 172                                const std::vector<int32> new_child_ids) {
 173   // Create a set of child ids in |src| for fast lookup, and return false
 174   // if a duplicate is found;
 175   std::set<int32> new_child_id_set;
 176   for (size_t i = 0; i < new_child_ids.size(); ++i) {
 177     if (new_child_id_set.find(new_child_ids[i]) != new_child_id_set.end()) {
 178       error_ = base::StringPrintf("Node %d has duplicate child id %d",
 179                                   node->id(), new_child_ids[i]);
 180       return false;
 181     }
 182     new_child_id_set.insert(new_child_ids[i]);
 183   }
 184
 185   // Delete the old children.
 186   const std::vector<AXNode*>& old_children = node->children();
 187   for (size_t i = 0; i < old_children.size(); ++i) {
 188     int old_id = old_children[i]->id();
 189     if (new_child_id_set.find(old_id) == new_child_id_set.end())
 190       DestroyNodeAndSubtree(old_children[i]);
 191   }
 192
 193   return true;
 194 }
 195
 196 bool AXTree::CreateNewChildVector(AXNode* node,
 197                                   const std::vector<int32> new_child_ids,
 198                                   std::vector<AXNode*>* new_children,
 199                                   std::set<AXNode*>* pending_nodes) {
 200   bool success = true;
 201   for (size_t i = 0; i < new_child_ids.size(); ++i) {
 202     int32 child_id = new_child_ids[i];
 203     int32 index_in_parent = static_cast<int32>(i);
 204     AXNode* child = GetFromId(child_id);
 205     if (child) {
 206       if (child->parent() != node) {
 207         // This is a serious error - nodes should never be reparented.
 208         // If this case occurs, continue so this node isn't left in an
 209         // inconsistent state, but return failure at the end.
 210         error_ = base::StringPrintf(
 211             "Node %d reparented from %d to %d",
 212             child->id(),
 213             child->parent() ? child->parent()->id() : 0,
 214             node->id());
 215         success = false;
 216         continue;
 217       }
 218       child->SetIndexInParent(index_in_parent);
 219     } else {
 220       child = CreateAndInitializeNode(node, child_id, index_in_parent);
 221       pending_nodes->insert(child);
 222     }
 223     new_children->push_back(child);
 224   }
 225
 226   return success;
 227 }
 228
 229 }  // namespace ui