First step to move common accessibility code out of content.

content/common/ax_tree_serializer.h

+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CONTENT_COMMON_AX_TREE_SERIALIZER_H_
+#define CONTENT_COMMON_AX_TREE_SERIALIZER_H_
+
+#include <set>
+
+#include "base/containers/hash_tables.h"
+#include "base/logging.h"
+#include "content/common/ax_tree_source.h"
+#include "content/public/common/ax_tree_update.h"
+
+namespace content {
+
+struct ClientTreeNode;
+
+// AXTreeSerializer is a helper class that serializes incremental
+// updates to an AXTreeSource as a vector of AXNodeData structs.
+// These structs can be unserialized by an AXTree. An AXTreeSerializer
+// keeps track of the tree of node ids that its client is aware of, so
+// it will automatically include, as part of any update, any additional nodes
+// that the client is not aware of yet.
+//
+// Note that AXTreeSerializer does not know if any nodes in the tree
+// change state. You should call SerializeChanges() individually on
+// every node that changes state. What's handled automatically is if
+// the node that's changed has any ancestors or descendants that haven't
+// been serialized to send to the client at all yet, they'll be included
+// in the update to ensure that the client always has a valid tree.
+template<class AXSourceNode>
+class CONTENT_EXPORT AXTreeSerializer {

[David Tseng, 2013/11/11 19:27:18]

So, what's the difference between calling Serialize on an AXTree vs using this
class?

[dmazzoni, 2013/11/12 00:03:04]

AXTree just has a method to serialize one node. I renamed that one SerializeNode
to make it more clear.

The reason it has that is because of AXSourceTree.

+ public:
+  AXTreeSerializer(AXTreeSource<AXSourceNode>* tree);

[David Tseng, 2013/11/11 19:27:18]

explicit

[dmazzoni, 2013/11/12 00:03:04]

Done.

+
+  void Reset();

[David Tseng, 2013/11/11 19:27:18]

What and why? Comment  please.

[dmazzoni, 2013/11/12 00:03:04]

Done.

+  void SerializeChanges(const AXSourceNode* node,
+                        AXTreeUpdate* out_update);
+
+ private:
+  // Clear the given node and recursively delete all of its descendants
+  // from the client tree. (Does not delete |client_node|).
+  void ClearClientTreeNode(ClientTreeNode* client_node);
+
+  void SerializeChangedNodes(const AXSourceNode* node,
+                             std::set<int>* ids_serialized,
+                             AXTreeUpdate* out_update);
+
+  // The tree source.
+  AXTreeSource<AXSourceNode>* tree_;
+
+  // Our representation of the client tree.
+  ClientTreeNode* client_root_;
+
+  // A map from IDs to nodes in the client tree.
+  base::hash_map<int32, ClientTreeNode*> client_id_map_;
+};
+
+// In order to keep track of what nodes the client knows about, we keep a
+// representation of the client tree - just IDs and parent/child
+// relationships.
+struct CONTENT_EXPORT ClientTreeNode {
+  ClientTreeNode();
+  virtual ~ClientTreeNode();
+  int32 id;
+  ClientTreeNode* parent;
+  std::vector<ClientTreeNode*> children;
+};
+
+template<class AXSourceNode>
+AXTreeSerializer<AXSourceNode>::AXTreeSerializer(
+    AXTreeSource<AXSourceNode>* tree)
+    : tree_(tree),
+      client_root_(NULL) {
+}
+
+template<class AXSourceNode>
+void AXTreeSerializer<AXSourceNode>::Reset() {
+  if (client_root_) {
+    ClearClientTreeNode(client_root_);
+    client_root_ = NULL;

[aboxhall, 2013/11/11 18:20:35]

Why aren't we calling delete client_root_ here?

[dmazzoni, 2013/11/12 00:03:04]

That was a bug. Good catch.

Actually it looks easier to just delete it. I renamed it.

+  }
+}
+
+template<class AXSourceNode>
+void AXTreeSerializer<AXSourceNode>::SerializeChanges(const AXSourceNode* node,
+                                        AXTreeUpdate* out_update) {

[aboxhall, 2013/11/11 18:20:35]

Nit: alignment.

[dmazzoni, 2013/11/12 00:03:04]

Done.

+  std::set<int> ids_serialized;
+  SerializeChangedNodes(node, &ids_serialized, out_update);
+}
+
+template<class AXSourceNode>
+void AXTreeSerializer<AXSourceNode>::ClearClientTreeNode(
+    ClientTreeNode* client_node) {
+  for (size_t i = 0; i < client_node->children.size(); ++i) {
+    client_id_map_.erase(client_node->children[i]->id);
+    ClearClientTreeNode(client_node->children[i]);
+    delete client_node->children[i];
+  }
+  client_node->children.clear();
+}
+
+template<class AXSourceNode>
+void AXTreeSerializer<AXSourceNode>::SerializeChangedNodes(
+    const AXSourceNode* node,
+    std::set<int>* ids_serialized,
+    AXTreeUpdate* out_update) {
+  int id = tree_->GetId(node);
+  if (ids_serialized->find(id) != ids_serialized->end())
+    return;
+  ids_serialized->insert(id);
+
+  // This method has three responsibilities:
+  // 1. Serialize |node| into an AXNodeData, and append it to
+  //    the AXTreeUpdate to be sent to the client.
+  // 2. Determine if |node| has any new children that the client doesn't
+  //    know about yet, and call SerializeChangedNodes recursively on those.
+  // 3. Update our internal data structure that keeps track of what nodes
+  //    the client knows about.
+
+  // First, find the ClientTreeNode for this id in our data structure where
+  // we keep track of what accessibility objects the client already knows
+  // about. If we don't find it, then this must be the new root of the
+  // accessibility tree.
+  ClientTreeNode* client_node = NULL;
+  base::hash_map<int32, ClientTreeNode*>::iterator iter =
+      client_id_map_.find(id);
+  if (iter != client_id_map_.end()) {
+    client_node = iter->second;
+  } else {
+    if (client_root_) {
+      ClearClientTreeNode(client_root_);
+      client_id_map_.erase(client_root_->id);
+      delete client_root_;
+    }
+    client_root_ = new ClientTreeNode();
+    client_node = client_root_;
+    client_node->id = id;
+    //client_node->location = ...;
+    client_node->parent = NULL;
+    client_id_map_[client_node->id] = client_node;
+  }
+
+  // Iterate over the ids of the children of |node|.
+  // Create a set of the child ids so we can quickly look
+  // up which children are new and which ones were there before.
+  // Also catch the case where a child is already in the client tree
+  // data structure with a different parent, and make sure the old parent
+  // clears this node first.
+  base::hash_set<int32> new_child_ids;
+  int child_count = tree_->GetChildCount(node);
+  for (int i = 0; i < child_count; i++) {
+    AXSourceNode* child = tree_->GetChildAtIndex(node, i);
+    int new_child_id = tree_->GetId(child);
+    new_child_ids.insert(new_child_id);
+
+    ClientTreeNode* client_child = client_id_map_[new_child_id];
+    if (client_child && client_child->parent != client_node) {
+      // The child is being reparented. Find the source tree node
+      // corresponding to the old parent, or the closest ancestor
+      // still in the tree.
+      ClientTreeNode* client_parent = client_child->parent;
+      AXSourceNode* parent;
+      while (client_parent) {
+        parent = tree_->GetFromId(client_parent->id);
+        if (parent)
+          break;
+        client_parent = client_parent->parent;
+      }
+      CHECK(parent);
+
+      // Call SerializeChangedNodes recursively on the old parent,
+      // so that the update that clears |child| from its old parent
+      // occurs stricly before the update that adds |child| to its
+      // new parent.
+      SerializeChangedNodes(parent, ids_serialized, out_update);
+    }
+  }
+
+  // Go through the old children and delete subtrees for child
+  // ids that are no longer present, and create a map from
+  // id to ClientTreeNode for the rest. It's important to delete
+  // first in a separate pass so that nodes that are reparented
+  // don't end up children of two different parents in the middle
+  // of an update, which can lead to a double-free.
+  base::hash_map<int32, ClientTreeNode*> client_child_id_map;
+  std::vector<ClientTreeNode*> old_children;
+  old_children.swap(client_node->children);
+  for (size_t i = 0; i < old_children.size(); i++) {
+    ClientTreeNode* old_child = old_children[i];
+    int old_child_id = old_child->id;
+    if (new_child_ids.find(old_child_id) == new_child_ids.end()) {
+      client_id_map_.erase(old_child_id);
+      ClearClientTreeNode(old_child);
+      delete old_child;
+    } else {
+      client_child_id_map[old_child_id] = old_child;
+    }
+  }
+
+  // Serialize this node. This fills in all of the fields in
+  // AXNodeData except child_ids, which we handle below.
+  out_update->nodes.push_back(AXNodeData());
+  AXNodeData* serialized_node = &out_update->nodes.back();
+  tree_->Serialize(node, serialized_node);
+  if (serialized_node->id == client_root_->id)
+    serialized_node->role = WebKit::WebAXRoleRootWebArea;
+  serialized_node->child_ids.clear();
+
+  // Iterate over the children, make note of the ones that are new
+  // and need to be serialized, and update the ClientTreeNode
+  // data structure to reflect the new tree.
+  std::vector<AXSourceNode*> children_to_serialize;
+  client_node->children.reserve(child_count);
+  for (int i = 0; i < child_count; i++) {
+    AXSourceNode* child = tree_->GetChildAtIndex(node, i);
+    int child_id = tree_->GetId(child);
+
+    // No need to do anything more with children that aren't new;
+    // the client will reuse its existing object.
+    if (new_child_ids.find(child_id) == new_child_ids.end())
+      continue;
+
+    new_child_ids.erase(child_id);
+    serialized_node->child_ids.push_back(child_id);
+    if (client_child_id_map.find(child_id) != client_child_id_map.end()) {
+      ClientTreeNode* reused_child = client_child_id_map[child_id];
+      //reused_child->location = obj.boundingBoxRect();
+      client_node->children.push_back(reused_child);
+    } else {
+      ClientTreeNode* new_child = new ClientTreeNode();
+      new_child->id = child_id;
+      //new_child->location = obj.boundingBoxRect();
+      new_child->parent = client_node;
+      client_node->children.push_back(new_child);
+      client_id_map_[child_id] = new_child;
+      children_to_serialize.push_back(child);
+    }
+  }
+
+  // Serialize all of the new children, recursively.
+  for (size_t i = 0; i < children_to_serialize.size(); ++i)
+    SerializeChangedNodes(children_to_serialize[i], ids_serialized, out_update);
+}
+
+}  // namespace content
+
+#endif  // CONTENT_COMMON_AX_TREE_SERIALIZER_H_