First step to move common accessibility code out of content.

content/common/ax_tree_impl.cc

Index: content/common/ax_tree_impl.cc
diff --git a/content/common/ax_tree_impl.cc b/content/common/ax_tree_impl.cc
new file mode 100644
index 0000000000000000000000000000000000000000..3b110c259518a4ceb7300f8f20cc434b11f2fa9f
--- /dev/null
+++ b/content/common/ax_tree_impl.cc
@@ -0,0 +1,227 @@
+// 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.
+
+#include "content/common/ax_tree_impl.h"
+
+#include <set>
+
+#include "content/common/ax_node_impl.h"
+
+namespace content {
+
+// This class is an implementation of the AXTreeSource interface with
+// AXNode as the node type, that just delegates to an AXTree. The purpose
+// of this is so that AXTreeSerializer only needs to work with the
+// AXTreeSource abstraction and doesn't need to actually know about
+// AXTree directly. Another AXTreeSource is used to abstract the Blink
+// accessibility tree.
+class CONTENT_EXPORT AXTreeSourceAdapter : public AXTreeSource<AXNode> {
+ public:
+  AXTreeSourceAdapter(AXTree* tree) : tree_(tree) {}
+  virtual ~AXTreeSourceAdapter() {}
+
+  // AXTreeSource implementation.
+  virtual AXNode* GetRoot() const OVERRIDE {
+    return tree_->GetRoot();
+  }
+
+  virtual int32 GetRootId() const OVERRIDE {
+    return tree_->GetRoot()->GetId();
+  }
+
+  virtual AXNode* GetFromId(int32 id) const OVERRIDE {
+    return tree_->GetFromId(id);
+  }
+
+  virtual int32 GetId(const AXNode* node) const OVERRIDE {
+    return node->GetId();
+  }
+
+  virtual int GetChildCount(const AXNode* node) const OVERRIDE {
+    return node->GetChildCount();
+  }
+
+  virtual AXNode* GetChildAtIndex(const AXNode* node, int index)
+      const OVERRIDE {
+    return node->ChildAtIndex(index);
+  }
+
+  virtual int32 GetParentId(const AXNode* node) const OVERRIDE {
+    if (node->GetParent())
+      return node->GetParent()->GetId();
+    else
+      return 0;
+  }
+
+  virtual void SerializeNode(
+      const AXNode* node, AXNodeData* out_data) const OVERRIDE {
+    *out_data = node->data();
+  }
+
+ private:
+  AXTree* tree_;
+};
+
+// static
+AXTree* AXTree::Create(const AXTreeUpdate& initial_state) {
+  return new AXTreeImpl(initial_state);
+}
+
+AXTreeImpl::AXTreeImpl()
+    : root_(NULL) {
+  AXNodeData root;
+  root.id = 0;
+  root.role = WebKit::WebAXRoleRootWebArea;
+
+  AXTreeUpdate initial_state;
+  initial_state.nodes.push_back(root);
+  Unserialize(initial_state);
+}
+
+AXTreeImpl::AXTreeImpl(const AXTreeUpdate& initial_state)
+    : root_(NULL) {
+  Unserialize(initial_state);
+}
+
+AXTreeImpl::~AXTreeImpl() {
+  if (root_)
+    DestroyNodeAndSubtree(root_);
+}
+
+AXNode* AXTreeImpl::GetRoot() const {
+  return root_;
+}
+
+AXNode* AXTreeImpl::GetFromId(int32 id) const {
+  base::hash_map<int32, AXNodeImpl*>::const_iterator iter = id_map_.find(id);
+  return iter != id_map_.end() ? (iter->second) : NULL;
+}
+
+bool AXTreeImpl::Unserialize(const AXTreeUpdate& update) {
+  for (size_t i = 0; i < update.nodes.size(); ++i) {
+    if (!UpdateNode(update.nodes[i]))
+      return false;
+  }
+
+  return true;
+}
+
+AXTreeSource<AXNode>* AXTreeImpl::CreateTreeSource() {
+  return new AXTreeSourceAdapter(this);
+}
+
+AXNodeImpl* AXTreeImpl::CreateNode() {
+  return new AXNodeImpl();
+}
+
+bool AXTreeImpl::UpdateNode(const AXNodeData& src) {
+  // This method updates one node in the tree based on serialized data
+  // received in an AXTreeUpdate. See AXTreeUpdate for pre and post
+  // conditions.
+
+  // Look up the node by id. If it's not found, then either the root
+  // of the tree is being swapped, or we're out of sync with the source
+  // and this is a serious error.
+  AXNodeImpl* node = static_cast<AXNodeImpl*>(GetFromId(src.id));
+  if (!node) {
+    if (src.role != WebKit::WebAXRoleRootWebArea)
+      return false;
+    node = CreateAndInitializeNode(NULL, src.id, 0);
+  }
+
+  // Set the node's data.
+  node->SetData(src);
+
+  // First, delete nodes that used to be children of this node but aren't
+  // anymore.
+  if (!DeleteOldChildren(node, src.child_ids))
+    return false;
+
+  // Now build a new children vector, reusing nodes when possible,
+  // and swap it in.
+  std::vector<AXNodeImpl*> new_children;
+  bool success = CreateNewChildVector(node, src.child_ids, &new_children);
+  node->SwapChildren(new_children);
+
+  // Update the root of the tree if needed.
+  if (src.role == WebKit::WebAXRoleRootWebArea &&
+      (!root_ || root_->GetId() != src.id)) {
+    if (root_)
+      DestroyNodeAndSubtree(root_);
+    root_ = node;
+    OnRootChanged();
+  }
+
+  return success;
+}
+
+void AXTreeImpl::OnRootChanged() {
+}
+
+AXNodeImpl* AXTreeImpl::CreateAndInitializeNode(
+    AXNodeImpl* parent, int32 id, int32 index_in_parent) {
+  AXNodeImpl* node = CreateNode();
+  node->Init(parent, id, index_in_parent);
+  id_map_[node->GetId()] = node;
+  return node;
+}
+
+void AXTreeImpl::DestroyNodeAndSubtree(AXNodeImpl* node) {
+  id_map_.erase(node->GetId());
+  for (int i = 0; i < node->GetChildCount(); ++i) {
+    AXNodeImpl* child = static_cast<AXNodeImpl*>(node->ChildAtIndex(i));
+    child->Destroy();
+  }
+  node->Destroy();
+}
+
+bool AXTreeImpl::DeleteOldChildren(AXNodeImpl* node,
+                                   const std::vector<int32> new_child_ids) {
+  // Create a set of child ids in |src| for fast lookup, and return false
+  // if a duplicate is found;
+  std::set<int32> new_child_id_set;
+  for (size_t i = 0; i < new_child_ids.size(); ++i) {
+    if (new_child_id_set.find(new_child_ids[i]) != new_child_id_set.end())
+      return false;
+    new_child_id_set.insert(new_child_ids[i]);
+  }
+
+  // Delete the old children.
+  const std::vector<AXNodeImpl*>& old_children = node->children();
+  for (size_t i = 0; i < old_children.size(); ++i) {
+    int old_id = old_children[i]->GetId();
+    if (new_child_id_set.find(old_id) == new_child_id_set.end())
+      DestroyNodeAndSubtree(old_children[i]);
+  }
+
+  return true;
+}
+
+bool AXTreeImpl::CreateNewChildVector(AXNodeImpl* node,
+                                      const std::vector<int32> new_child_ids,
+                                      std::vector<AXNodeImpl*>* new_children) {
+  bool success = true;
+  for (size_t i = 0; i < new_child_ids.size(); ++i) {
+    int32 child_id = new_child_ids[i];
+    int32 index_in_parent = static_cast<int32>(i);
+    AXNodeImpl* child = static_cast<AXNodeImpl*>(GetFromId(child_id));
+    if (child) {
+      if (child->GetParent() != node) {
+        // This is a serious error - nodes should never be reparented.
+        // If this case occurs, continue so this node isn't left in an
+        // inconsistent state, but return failure at the end.
+        success = false;
+        continue;
+      }
+      child->UpdateIndexInParent(index_in_parent);
+    } else {
+      child = CreateAndInitializeNode(node, child_id, index_in_parent);
+    }
+    new_children->push_back(child);
+  }
+
+  return success;
+}
+
+}  // namespace content