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..6373c3550dbcbd778512b2534eae0814875c91cb
--- /dev/null
+++ b/content/common/ax_tree_impl.cc
@@ -0,0 +1,193 @@
+// 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 {
+
+// static
+AXTree* AXTree::Create() {
+  return new AXTreeImpl();
+}
+
+// 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_)
+    root_->Destroy();
+}
+
+AXNode* AXTreeImpl::GetRoot() const {
+  return root_;
+}
+
+int32 AXTreeImpl::GetRootId() const {
+  return root_->GetId();
+}
+
+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;
+}
+
+int32 AXTreeImpl::GetId(const AXNode* node) const {

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

What is the purpose of this and the below two methods, given they just call a
public method on the node in each case? Is it in case some platform wants to
override them?

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

This is because AXSourceTree is an abstraction of an accessibility tree where
the type (AXNode here) is opaque. AXSourceTree allows us to abstract the
Blink accessibility tree and implement AXTreeSerializer once rather than
needing to duplicate that code.

[David Tseng, 2013/11/13 18:08:11]

I don't entirely understand this; the methods duplicated in this cl are on both
AXNode and AXTree; if you don't mean to potential subclasses to override them,
then make them private perhaps?

+  return node->GetId();
+}
+
+int AXTreeImpl::GetChildCount(const AXNode* node) const {
+  return node->GetChildCount();
+}
+
+AXNode* AXTreeImpl::GetChildAtIndex(const AXNode* node, int index) const {
+  return node->ChildAtIndex(index);
+}
+
+int32 AXTreeImpl::GetParentId(const AXNode* node) const {
+  return node->GetParent() ? node->GetParent()->GetId() : 0;
+}
+
+void AXTreeImpl::Serialize(const AXNode* node, AXNodeData* out_data) const {
+  *out_data = node->data();
+}
+
+bool AXTreeImpl::Unserialize(const AXTreeUpdate& update) {
+  for (size_t i = 0; i < update.nodes.size(); i++) {

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

nit: ++i

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

Done.

+    if (!UpdateNode(update.nodes[i]))
+      return false;

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

DCHECK? Is this ever acceptable?

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

It's not acceptable, but what we're currently doing in
BrowserAccessibilityManager is sending a message to crash the renderer, rather
than doing a DCHECK and crashing the browser.

It's also better at this level of abstraction to return false because then we
can just assert it in a test, and test that bad cases fail.

+  }
+
+  return true;
+}
+
+void AXTreeImpl::NodeWasDestroyed(AXNodeImpl* node) {
+  id_map_.erase(node->GetId());
+}
+
+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.
+
+  // Create a set of child ids in |src| for fast lookup. If a duplicate id is
+  // found, exit now with a fatal error before changing anything else.
+  std::set<int32> new_child_ids;
+  for (size_t i = 0; i < src.child_ids.size(); ++i) {

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

ditto

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

?

+    if (new_child_ids.find(src.child_ids[i]) != new_child_ids.end())
+      return false;

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

DCHECK?

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

Same

+    new_child_ids.insert(src.child_ids[i]);
+  }
+
+  // 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);
+
+  //
+  // Update the children in three steps:

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

This huge comment block indicates that the below should probably belong in its
own method (which should then be unit tested separately).

[dmazzoni, 2013/11/12 07:48:23]

Refactored. More comprehensive unit tests coming.

+  //
+  // 1. Iterate over the old children and delete nodes that are no longer
+  //    in the tree.
+  // 2. Build up a vector of new children, reusing children that haven't
+  //    changed (but may have been reordered) and adding new empty
+  //    objects for new children.
+  // 3. Swap in the new children vector for the old one.
+
+  // Delete any previous children of this node that are no longer

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

Suggestion:
// (1) Delete ...
(to refer back to steps above.)

[dmazzoni, 2013/11/12 07:48:23]

Refactored, please take a look.

+  // children first. We make a deletion-only pass first to prevent a
+  // node that's being reparented from being the child of both its old
+  // parent and new parent, which could lead to a double-free.
+  // If a node is reparented, the source will always send us a fresh
+  // copy of the node.
+  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_ids.find(old_id) == new_child_ids.end())
+      old_children[i]->Destroy();
+  }
+
+  // Now build a vector of new children, reusing objects that were already
+  // children of this node before.
+  std::vector<AXNodeImpl*> new_children;
+  bool success = true;
+  for (size_t i = 0; i < src.child_ids.size(); i++) {
+    int32 child_id = src.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);
+  }
+
+  // Finally, swap in the new children vector for the old.
+  node->SwapChildren(new_children);
+
+  // Handle the case where this node is the new root of the tree.

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

And perhaps a separate method for this as well. (i.e. OnDoUpdateChilfdren,
OnDoUpdateRoot, or the like).

[dmazzoni, 2013/11/12 07:48:23]

I thought this was fine here now that everything else was in another method,
take a look.

+  if (src.role == WebKit::WebAXRoleRootWebArea &&
+      (!root_ || root_->GetId() != src.id)) {
+    if (root_)
+      root_->Destroy();
+    root_ = node;
+    OnRootChanged();
+  }
+
+  return success;
+}
+
+void AXTreeImpl::OnRootChanged() {
+}
+
+AXNodeImpl* AXTreeImpl::CreateAndInitializeNode(
+    AXNodeImpl* parent, int32 id, int32 index_in_parent) {
+  AXNodeImpl* node = CreateNode();
+  node->Init(this, parent, id, index_in_parent);
+  id_map_[node->GetId()] = node;
+  return node;
+}
+
+}  // namespace content