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