src/ui/accessibility/ax_tree_serializer.h

   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 #ifndef UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
   6 #define UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
   7
   8 #include <set>
   9
  10 #include "base/containers/hash_tables.h"
  11 #include "base/logging.h"
  12 #include "base/stl_util.h"
  13 #include "ui/accessibility/ax_tree_source.h"
  14 #include "ui/accessibility/ax_tree_update.h"
  15
  16 namespace ui {
  17
  18 struct ClientTreeNode;
  19
  20 // AXTreeSerializer is a helper class that serializes incremental
  21 // updates to an AXTreeSource as a AXTreeUpdate struct.
  22 // These structs can be unserialized by a client object such as an
  23 // AXTree. An AXTreeSerializer keeps track of the tree of node ids that its
  24 // client is aware of so that it will never generate an AXTreeUpdate that
  25 // results in an invalid tree.
  26 //
  27 // Every node in the source tree must have an id that's a unique positive
  28 // integer, the same node must not appear twice.
  29 //
  30 // Usage:
  31 //
  32 // You must call SerializeChanges() every time a node in the tree changes,
  33 // and send the generated AXTreeUpdate to the client.
  34 //
  35 // If a node is added, call SerializeChanges on its parent.
  36 // If a node is removed, call SerializeChanges on its parent.
  37 // If a whole new subtree is added, just call SerializeChanges on its root.
  38 // If the root of the tree changes, call SerializeChanges on the new root.
  39 //
  40 // AXTreeSerializer will avoid re-serializing nodes that do not change.
  41 // For example, if node 1 has children 2, 3, 4, 5 and then child 2 is
  42 // removed and a new child 6 is added, the AXTreeSerializer will only
  43 // update nodes 1 and 6 (and any children of node 6 recursively). It will
  44 // assume that nodes 3, 4, and 5 are not modified unless you explicitly
  45 // call SerializeChanges() on them.
  46 //
  47 // As long as the source tree has unique ids for every node and no loops,
  48 // and as long as every update is applied to the client tree, AXTreeSerializer
  49 // will continue to work. If the source tree makes a change but fails to
  50 // call SerializeChanges properly, the trees may get out of sync - but
  51 // because AXTreeSerializer always keeps track of what updates it's sent,
  52 // it will never send an invalid update and the client tree will not break,
  53 // it just may not contain all of the changes.
  54 template<typename AXSourceNode>
  55 class AXTreeSerializer {
  56  public:
  57   explicit AXTreeSerializer(AXTreeSource<AXSourceNode>* tree);
  58   ~AXTreeSerializer();
  59
  60   // Throw out the internal state that keeps track of the nodes the client
  61   // knows about. This has the effect that the next update will send the
  62   // entire tree over because it assumes the client knows nothing.
  63   void Reset();
  64
  65   // Serialize all changes to |node| and append them to |out_update|.
  66   void SerializeChanges(AXSourceNode node,
  67                         AXTreeUpdate* out_update);
  68
  69   // Delete the client subtree for this node, ensuring that the subtree
  70   // is re-serialized.
  71   void DeleteClientSubtree(AXSourceNode node);
  72
  73   // Only for unit testing. Normally this class relies on getting a call
  74   // to SerializeChanges() every time the source tree changes. For unit
  75   // testing, it's convenient to create a static AXTree for the initial
  76   // state and then call ChangeTreeSourceForTesting and then SerializeChanges
  77   // to simulate the changes you'd get if a tree changed from the initial
  78   // state to the second tree's state.
  79   void ChangeTreeSourceForTesting(AXTreeSource<AXSourceNode>* new_tree);
  80
  81  private:
  82   // Return the least common ancestor of a node in the source tree
  83   // and a node in the client tree, or NULL if there is no such node.
  84   // The least common ancestor is the closest ancestor to |node| (which
  85   // may be |node| itself) that's in both the source tree and client tree,
  86   // and for which both the source and client tree agree on their ancestor
  87   // chain up to the root.
  88   //
  89   // Example 1:
  90   //
  91   //    Client Tree    Source tree |
  92   //        1              1       |
  93   //       / \            / \      |
  94   //      2   3          2   4     |
  95   //
  96   // LCA(source node 2, client node 2) is node 2.
  97   // LCA(source node 3, client node 4) is node 1.
  98   //
  99   // Example 2:
 100   //
 101   //    Client Tree    Source tree |
 102   //        1              1       |
 103   //       / \            / \      |
 104   //      2   3          2   3     |
 105   //     / \            /   /      |
 106   //    4   7          8   4       |
 107   //   / \                / \      |
 108   //  5   6              5   6     |
 109   //
 110   // LCA(source node 8, client node 7) is node 2.
 111   // LCA(source node 5, client node 5) is node 1.
 112   // It's not node 5, because the two trees disagree on the parent of
 113   // node 4, so the LCA is the first ancestor both trees agree on.
 114   AXSourceNode LeastCommonAncestor(AXSourceNode node,
 115                                    ClientTreeNode* client_node);
 116
 117   // Return the least common ancestor of |node| that's in the client tree.
 118   // This just walks up the ancestors of |node| until it finds a node that's
 119   // also in the client tree, and then calls LeastCommonAncestor on the
 120   // source node and client node.
 121   AXSourceNode LeastCommonAncestor(AXSourceNode node);
 122
 123   // Walk the subtree rooted at |node| and return true if any nodes that
 124   // would be updated are being reparented. If so, update |out_lca| to point
 125   // to the least common ancestor of the previous LCA and the previous
 126   // parent of the node being reparented.
 127   bool AnyDescendantWasReparented(AXSourceNode node,
 128                                   AXSourceNode* out_lca);
 129
 130   ClientTreeNode* ClientTreeNodeById(int32 id);
 131
 132   // Delete the given client tree node and recursively delete all of its
 133   // descendants.
 134   void DeleteClientSubtree(ClientTreeNode* client_node);
 135
 136   // Helper function, called recursively with each new node to serialize.
 137   void SerializeChangedNodes(AXSourceNode node,
 138                              AXTreeUpdate* out_update);
 139
 140   // The tree source.
 141   AXTreeSource<AXSourceNode>* tree_;
 142
 143   // Our representation of the client tree.
 144   ClientTreeNode* client_root_;
 145
 146   // A map from IDs to nodes in the client tree.
 147   base::hash_map<int32, ClientTreeNode*> client_id_map_;
 148 };
 149
 150 // In order to keep track of what nodes the client knows about, we keep a
 151 // representation of the client tree - just IDs and parent/child
 152 // relationships.
 153 struct AX_EXPORT ClientTreeNode {
 154   ClientTreeNode();
 155   virtual ~ClientTreeNode();
 156   int32 id;
 157   ClientTreeNode* parent;
 158   std::vector<ClientTreeNode*> children;
 159 };
 160
 161 template<typename AXSourceNode>
 162 AXTreeSerializer<AXSourceNode>::AXTreeSerializer(
 163     AXTreeSource<AXSourceNode>* tree)
 164     : tree_(tree),
 165       client_root_(NULL) {
 166 }
 167
 168 template<typename AXSourceNode>
 169 AXTreeSerializer<AXSourceNode>::~AXTreeSerializer() {
 170   Reset();
 171 }
 172
 173 template<typename AXSourceNode>
 174 void AXTreeSerializer<AXSourceNode>::Reset() {
 175   if (!client_root_)
 176     return;
 177
 178   DeleteClientSubtree(client_root_);
 179   client_id_map_.erase(client_root_->id);
 180   delete client_root_;
 181   client_root_ = NULL;
 182 }
 183
 184 template<typename AXSourceNode>
 185 void AXTreeSerializer<AXSourceNode>::ChangeTreeSourceForTesting(
 186     AXTreeSource<AXSourceNode>* new_tree) {
 187   tree_ = new_tree;
 188 }
 189
 190 template<typename AXSourceNode>
 191 AXSourceNode AXTreeSerializer<AXSourceNode>::LeastCommonAncestor(
 192     AXSourceNode node, ClientTreeNode* client_node) {
 193   if (!tree_->IsValid(node) || client_node == NULL)
 194     return tree_->GetNull();
 195
 196   std::vector<AXSourceNode> ancestors;
 197   while (tree_->IsValid(node)) {
 198     ancestors.push_back(node);
 199     node = tree_->GetParent(node);
 200   }
 201
 202   std::vector<ClientTreeNode*> client_ancestors;
 203   while (client_node) {
 204     client_ancestors.push_back(client_node);
 205     client_node = client_node->parent;
 206   }
 207
 208   // Start at the root. Keep going until the source ancestor chain and
 209   // client ancestor chain disagree. The last node before they disagree
 210   // is the LCA.
 211   AXSourceNode lca = tree_->GetNull();
 212   int source_index = static_cast<int>(ancestors.size() - 1);
 213   int client_index = static_cast<int>(client_ancestors.size() - 1);
 214   while (source_index >= 0 && client_index >= 0) {
 215     if (tree_->GetId(ancestors[source_index]) !=
 216             client_ancestors[client_index]->id) {
 217       return lca;
 218     }
 219     lca = ancestors[source_index];
 220     source_index--;
 221     client_index--;
 222   }
 223   return lca;
 224 }
 225
 226 template<typename AXSourceNode>
 227 AXSourceNode AXTreeSerializer<AXSourceNode>::LeastCommonAncestor(
 228     AXSourceNode node) {
 229   // Walk up the tree until the source node's id also exists in the
 230   // client tree, then call LeastCommonAncestor on those two nodes.
 231   ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
 232   while (tree_->IsValid(node) && !client_node) {
 233     node = tree_->GetParent(node);
 234     if (tree_->IsValid(node))
 235       client_node = ClientTreeNodeById(tree_->GetId(node));
 236   }
 237   return LeastCommonAncestor(node, client_node);
 238 }
 239
 240 template<typename AXSourceNode>
 241 bool AXTreeSerializer<AXSourceNode>::AnyDescendantWasReparented(
 242     AXSourceNode node, AXSourceNode* out_lca) {
 243   bool result = false;
 244   int id = tree_->GetId(node);
 245   std::vector<AXSourceNode> children;
 246   tree_->GetChildren(node, &children);
 247   for (size_t i = 0; i < children.size(); ++i) {
 248     AXSourceNode& child = children[i];
 249     int child_id = tree_->GetId(child);
 250     ClientTreeNode* client_child = ClientTreeNodeById(child_id);
 251     if (client_child) {
 252       if (!client_child->parent) {
 253         // If the client child has no parent, it must have been the
 254         // previous root node, so there is no LCA and we can exit early.
 255         *out_lca = tree_->GetNull();
 256         return true;
 257       } else if (client_child->parent->id != id) {
 258         // If the client child's parent is not this node, update the LCA
 259         // and return true (reparenting was found).
 260         *out_lca = LeastCommonAncestor(*out_lca, client_child);
 261         result = true;
 262       } else {
 263         // This child is already in the client tree, we won't
 264         // recursively serialize it so we don't need to check this
 265         // subtree recursively for reparenting.
 266         continue;
 267       }
 268     }
 269
 270     // This is a new child or reparented child, check it recursively.
 271     if (AnyDescendantWasReparented(child, out_lca))
 272       result = true;
 273   }
 274   return result;
 275 }
 276
 277 template<typename AXSourceNode>
 278 ClientTreeNode* AXTreeSerializer<AXSourceNode>::ClientTreeNodeById(int32 id) {
 279   base::hash_map<int32, ClientTreeNode*>::iterator iter =
 280       client_id_map_.find(id);
 281   if (iter != client_id_map_.end())
 282     return iter->second;
 283   else
 284     return NULL;
 285 }
 286
 287 template<typename AXSourceNode>
 288 void AXTreeSerializer<AXSourceNode>::SerializeChanges(
 289     AXSourceNode node,
 290     AXTreeUpdate* out_update) {
 291   // If the node isn't in the client tree, we need to serialize starting
 292   // with the LCA.
 293   AXSourceNode lca = LeastCommonAncestor(node);
 294
 295   if (client_root_) {
 296     bool need_delete = false;
 297     if (tree_->IsValid(lca)) {
 298       // Check for any reparenting within this subtree - if there is
 299       // any, we need to delete and reserialize the whole subtree
 300       // that contains the old and new parents of the reparented node.
 301       if (AnyDescendantWasReparented(lca, &lca))
 302         need_delete = true;
 303     }
 304
 305     if (!tree_->IsValid(lca)) {
 306       // If there's no LCA, just tell the client to destroy the whole
 307       // tree and then we'll serialize everything from the new root.
 308       out_update->node_id_to_clear = client_root_->id;
 309       Reset();
 310     } else if (need_delete) {
 311       // Otherwise, if we need to reserialize a subtree, first we need
 312       // to delete those nodes in our client tree so that
 313       // SerializeChangedNodes() will be sure to send them again.
 314       out_update->node_id_to_clear = tree_->GetId(lca);
 315       ClientTreeNode* client_lca = ClientTreeNodeById(tree_->GetId(lca));
 316       CHECK(client_lca);
 317       for (size_t i = 0; i < client_lca->children.size(); ++i) {
 318         client_id_map_.erase(client_lca->children[i]->id);
 319         DeleteClientSubtree(client_lca->children[i]);
 320         delete client_lca->children[i];
 321       }
 322       client_lca->children.clear();
 323     }
 324   }
 325
 326   // Serialize from the LCA, or from the root if there isn't one.
 327   if (!tree_->IsValid(lca))
 328     lca = tree_->GetRoot();
 329   SerializeChangedNodes(lca, out_update);
 330 }
 331
 332 template<typename AXSourceNode>
 333 void AXTreeSerializer<AXSourceNode>::DeleteClientSubtree(AXSourceNode node) {
 334   ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
 335   if (client_node)
 336     DeleteClientSubtree(client_node);
 337 }
 338
 339 template<typename AXSourceNode>
 340 void AXTreeSerializer<AXSourceNode>::DeleteClientSubtree(
 341     ClientTreeNode* client_node) {
 342   for (size_t i = 0; i < client_node->children.size(); ++i) {
 343     client_id_map_.erase(client_node->children[i]->id);
 344     DeleteClientSubtree(client_node->children[i]);
 345     delete client_node->children[i];
 346   }
 347   client_node->children.clear();
 348 }
 349
 350 template<typename AXSourceNode>
 351 void AXTreeSerializer<AXSourceNode>::SerializeChangedNodes(
 352     AXSourceNode node,
 353     AXTreeUpdate* out_update) {
 354   // This method has three responsibilities:
 355   // 1. Serialize |node| into an AXNodeData, and append it to
 356   //    the AXTreeUpdate to be sent to the client.
 357   // 2. Determine if |node| has any new children that the client doesn't
 358   //    know about yet, and call SerializeChangedNodes recursively on those.
 359   // 3. Update our internal data structure that keeps track of what nodes
 360   //    the client knows about.
 361
 362   // First, find the ClientTreeNode for this id in our data structure where
 363   // we keep track of what accessibility objects the client already knows
 364   // about. If we don't find it, then this must be the new root of the
 365   // accessibility tree.
 366   int id = tree_->GetId(node);
 367   ClientTreeNode* client_node = ClientTreeNodeById(id);
 368   if (!client_node) {
 369     Reset();
 370     client_root_ = new ClientTreeNode();
 371     client_node = client_root_;
 372     client_node->id = id;
 373     client_node->parent = NULL;
 374     client_id_map_[client_node->id] = client_node;
 375   }
 376
 377   // Iterate over the ids of the children of |node|.
 378   // Create a set of the child ids so we can quickly look
 379   // up which children are new and which ones were there before.
 380   base::hash_set<int32> new_child_ids;
 381   std::vector<AXSourceNode> children;
 382   tree_->GetChildren(node, &children);
 383   for (size_t i = 0; i < children.size(); ++i) {
 384     AXSourceNode& child = children[i];
 385     int new_child_id = tree_->GetId(child);
 386     new_child_ids.insert(new_child_id);
 387
 388     // This is a sanity check - there shouldn't be any reparenting
 389     // because we've already handled it above.
 390     ClientTreeNode* client_child = client_id_map_[new_child_id];
 391     CHECK(!client_child || client_child->parent == client_node);
 392   }
 393
 394   // Go through the old children and delete subtrees for child
 395   // ids that are no longer present, and create a map from
 396   // id to ClientTreeNode for the rest. It's important to delete
 397   // first in a separate pass so that nodes that are reparented
 398   // don't end up children of two different parents in the middle
 399   // of an update, which can lead to a double-free.
 400   base::hash_map<int32, ClientTreeNode*> client_child_id_map;
 401   std::vector<ClientTreeNode*> old_children;
 402   old_children.swap(client_node->children);
 403   for (size_t i = 0; i < old_children.size(); ++i) {
 404     ClientTreeNode* old_child = old_children[i];
 405     int old_child_id = old_child->id;
 406     if (new_child_ids.find(old_child_id) == new_child_ids.end()) {
 407       client_id_map_.erase(old_child_id);
 408       DeleteClientSubtree(old_child);
 409       delete old_child;
 410     } else {
 411       client_child_id_map[old_child_id] = old_child;
 412     }
 413   }
 414
 415   // Serialize this node. This fills in all of the fields in
 416   // AXNodeData except child_ids, which we handle below.
 417   out_update->nodes.push_back(AXNodeData());
 418   AXNodeData* serialized_node = &out_update->nodes.back();
 419   tree_->SerializeNode(node, serialized_node);
 420   // TODO(dmazzoni/dtseng): Make the serializer not depend on roles to identify
 421   // the root.
 422   if (serialized_node->id == client_root_->id &&
 423       (serialized_node->role != AX_ROLE_ROOT_WEB_AREA &&
 424        serialized_node->role != AX_ROLE_DESKTOP)) {
 425     serialized_node->role = AX_ROLE_ROOT_WEB_AREA;
 426   }
 427   serialized_node->child_ids.clear();
 428
 429   // Iterate over the children, make note of the ones that are new
 430   // and need to be serialized, and update the ClientTreeNode
 431   // data structure to reflect the new tree.
 432   std::vector<AXSourceNode> children_to_serialize;
 433   client_node->children.reserve(children.size());
 434   for (size_t i = 0; i < children.size(); ++i) {
 435     AXSourceNode& child = children[i];
 436     int child_id = tree_->GetId(child);
 437
 438     // No need to do anything more with children that aren't new;
 439     // the client will reuse its existing object.
 440     if (new_child_ids.find(child_id) == new_child_ids.end())
 441       continue;
 442
 443     new_child_ids.erase(child_id);
 444     serialized_node->child_ids.push_back(child_id);
 445     if (client_child_id_map.find(child_id) != client_child_id_map.end()) {
 446       ClientTreeNode* reused_child = client_child_id_map[child_id];
 447       client_node->children.push_back(reused_child);
 448     } else {
 449       ClientTreeNode* new_child = new ClientTreeNode();
 450       new_child->id = child_id;
 451       new_child->parent = client_node;
 452       client_node->children.push_back(new_child);
 453       client_id_map_[child_id] = new_child;
 454       children_to_serialize.push_back(child);
 455     }
 456   }
 457
 458   // Serialize all of the new children, recursively.
 459   for (size_t i = 0; i < children_to_serialize.size(); ++i)
 460     SerializeChangedNodes(children_to_serialize[i], out_update);
 461 }
 462
 463 }  // namespace ui
 464
 465 #endif  // UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_