Refactor content/renderer/accessibility to use AXTreeSerializer (re-land).

content/renderer/accessibility/renderer_accessibility_complete.cc

Index: content/renderer/accessibility/renderer_accessibility_complete.cc
diff --git a/content/renderer/accessibility/renderer_accessibility_complete.cc b/content/renderer/accessibility/renderer_accessibility_complete.cc
index b4ea81e803f53e5ad47ea9539abffb6bacb08e1f..cd17e244ad2d884d2f745ce3b8cee4b489e13c4d 100644
--- a/content/renderer/accessibility/renderer_accessibility_complete.cc
+++ b/content/renderer/accessibility/renderer_accessibility_complete.cc
@@ -8,7 +8,6 @@
 
 #include "base/bind.h"
 #include "base/message_loop/message_loop.h"
-#include "content/renderer/accessibility/accessibility_node_serializer.h"
 #include "content/renderer/accessibility/blink_ax_enum_conversion.h"
 #include "content/renderer/render_view_impl.h"
 #include "third_party/WebKit/public/web/WebAXObject.h"
@@ -34,7 +33,8 @@ RendererAccessibilityComplete::RendererAccessibilityComplete(
     RenderViewImpl* render_view)
     : RendererAccessibility(render_view),
       weak_factory_(this),
-      browser_root_(NULL),
+      tree_source_(render_view),
+      serializer_(&tree_source_),
       last_scroll_offset_(gfx::Size()),
       ack_pending_(false) {
   WebAXObject::enableAccessibility();
@@ -57,12 +57,6 @@ RendererAccessibilityComplete::RendererAccessibilityComplete(
 }
 
 RendererAccessibilityComplete::~RendererAccessibilityComplete() {
-  if (browser_root_) {
-    ClearBrowserTreeNode(browser_root_);
-    browser_id_map_.erase(browser_root_->id);
-    delete browser_root_;
-  }
-  DCHECK(browser_id_map_.empty());
 }
 
 bool RendererAccessibilityComplete::OnMessageReceived(
@@ -102,14 +96,6 @@ void RendererAccessibilityComplete::DidFinishLoad(blink::WebFrame* frame) {
   const WebDocument& document = GetMainDocument();
   if (document.isNull())
     return;
-
-  // Check to see if the root accessibility object has changed, to work
-  // around Blink bugs that cause AXObjectCache to be cleared
-  // unnecessarily.
-  // TODO(dmazzoni): remove this once rdar://5794454 is fixed.
-  WebAXObject new_root = document.accessibilityObject();
-  if (!browser_root_ || new_root.axID() != browser_root_->id)
-    HandleAXEvent(new_root, ui::AX_EVENT_LAYOUT_COMPLETE);
 }
 
 
@@ -169,10 +155,6 @@ RendererAccessibilityType RendererAccessibilityComplete::GetType() {
   return RendererAccessibilityTypeComplete;
 }
 
-RendererAccessibilityComplete::BrowserTreeNode::BrowserTreeNode() : id(0) {}
-
-RendererAccessibilityComplete::BrowserTreeNode::~BrowserTreeNode() {}
-
 void RendererAccessibilityComplete::SendPendingAccessibilityEvents() {
   const WebDocument& document = GetMainDocument();
   if (document.isNull())
@@ -211,83 +193,22 @@ void RendererAccessibilityComplete::SendPendingAccessibilityEvents() {
     // selection state, so make sure we re-send that whole subtree.
     if (event.event_type ==
         ui::AX_EVENT_SELECTED_CHILDREN_CHANGED) {
-      base::hash_map<int32, BrowserTreeNode*>::iterator iter =
-          browser_id_map_.find(obj.axID());
-      if (iter != browser_id_map_.end())
-        ClearBrowserTreeNode(iter->second);
-    }
-
-    // The browser may not have this object yet, for example if we get a
-    // event on an object that was recently added, or if we get a
-    // event on a node before the page has loaded. Work our way
-    // up the parent chain until we find a node the browser has, or until
-    // we reach the root.
-    WebAXObject root_object = document.accessibilityObject();
-    int root_id = root_object.axID();
-    while (browser_id_map_.find(obj.axID()) == browser_id_map_.end() &&
-           !obj.isDetached() &&
-           obj.axID() != root_id) {
-      obj = obj.parentObject();
-      if (event.event_type ==
-          ui::AX_EVENT_CHILDREN_CHANGED) {
-        event.id = obj.axID();
-      }
-    }
-
-    if (obj.isDetached()) {
-#ifndef NDEBUG
-      LOG(WARNING) << "Got event on object that is invalid or has"
-                   << " invalid ancestor. Id: " << obj.axID();
-#endif
-      continue;
-    }
-
-    // Another potential problem is that this event may be on an
-    // object that is detached from the tree. Determine if this node is not a
-    // child of its parent, and if so move the event to the parent.
-    // TODO(dmazzoni): see if this can be removed after
-    // https://bugs.webkit.org/show_bug.cgi?id=68466 is fixed.
-    if (obj.axID() != root_id) {
-      WebAXObject parent = obj.parentObject();
-      while (!parent.isDetached() &&
-             parent.accessibilityIsIgnored()) {
-        parent = parent.parentObject();
-      }
-
-      if (parent.isDetached()) {
-        NOTREACHED();
-        continue;
-      }
-      bool is_child_of_parent = false;
-      for (unsigned int i = 0; i < parent.childCount(); ++i) {
-        if (parent.childAt(i).equals(obj)) {
-          is_child_of_parent = true;
-          break;
-        }
-      }
-
-      if (!is_child_of_parent) {
-        obj = parent;
-        event.id = obj.axID();
-      }
+      serializer_.DeleteClientSubtree(obj);
     }
 
     // Allow Blink to cache intermediate results since we're doing a bunch
     // of read-only queries at once.
-    root_object.startCachingComputedObjectAttributesUntilTreeMutates();
+    obj.startCachingComputedObjectAttributesUntilTreeMutates();
 
     AccessibilityHostMsg_EventParams event_msg;
     event_msg.event_type = event.event_type;
     event_msg.id = event.id;
-    std::set<int> ids_serialized;
-    SerializeChangedNodes(obj, &event_msg.nodes, &ids_serialized);
+    serializer_.SerializeChanges(obj, &event_msg.update);
     event_msgs.push_back(event_msg);
 
 #ifndef NDEBUG
     ui::AXTree tree;
-    ui::AXTreeUpdate update;
-    update.nodes = event_msg.nodes;
-    tree.Unserialize(update);
+    tree.Unserialize(event_msg.update);
     VLOG(0) << "Accessibility update: \n"
             << "routing id=" << routing_id()
             << " event="
@@ -302,200 +223,38 @@ void RendererAccessibilityComplete::SendPendingAccessibilityEvents() {
 }
 
 void RendererAccessibilityComplete::SendLocationChanges() {
-  std::queue<WebAXObject> objs_to_explore;
-  std::vector<BrowserTreeNode*> location_changes;
-  WebAXObject root_object = GetMainDocument().accessibilityObject();
-  objs_to_explore.push(root_object);
+  std::vector<AccessibilityHostMsg_LocationChangeParams> messages;
 
+  // Do a breadth-first explore of the whole blink AX tree.
+  base::hash_map<int, gfx::Rect> new_locations;
+  std::queue<WebAXObject> objs_to_explore;
+  objs_to_explore.push(tree_source_.GetRoot());
   while (objs_to_explore.size()) {
     WebAXObject obj = objs_to_explore.front();
     objs_to_explore.pop();
-    int id = obj.axID();
-    if (browser_id_map_.find(id) != browser_id_map_.end()) {
-      BrowserTreeNode* browser_node = browser_id_map_[id];
-      gfx::Rect new_location = obj.boundingBoxRect();
-      if (browser_node->location != new_location) {
-        browser_node->location = new_location;
-        location_changes.push_back(browser_node);
-      }
-    }
-
-    for (unsigned i = 0; i < obj.childCount(); ++i)
-      objs_to_explore.push(obj.childAt(i));
-  }
-
-  if (location_changes.size() == 0)
-    return;
-
-  std::vector<AccessibilityHostMsg_LocationChangeParams> messages;
-  messages.resize(location_changes.size());
-  for (size_t i = 0; i < location_changes.size(); i++) {
-    messages[i].id = location_changes[i]->id;
-    messages[i].new_location = location_changes[i]->location;
-  }
-  Send(new AccessibilityHostMsg_LocationChanges(routing_id(), messages));
-}
-
-RendererAccessibilityComplete::BrowserTreeNode*
-RendererAccessibilityComplete::CreateBrowserTreeNode() {
-  return new RendererAccessibilityComplete::BrowserTreeNode();
-}
-
-void RendererAccessibilityComplete::SerializeChangedNodes(
-    const blink::WebAXObject& obj,
-    std::vector<ui::AXNodeData>* dst,
-    std::set<int>* ids_serialized) {
-  if (ids_serialized->find(obj.axID()) != ids_serialized->end())
-    return;
-  ids_serialized->insert(obj.axID());
-
-  // This method has three responsibilities:
-  // 1. Serialize |obj| into an ui::AXNodeData, and append it to
-  //    the end of the |dst| vector to be send to the browser process.
-  // 2. Determine if |obj| has any new children that the browser doesn't
-  //    know about yet, and call SerializeChangedNodes recursively on those.
-  // 3. Update our internal data structure that keeps track of what nodes
-  //    the browser knows about.
-
-  // First, find the BrowserTreeNode for this id in our data structure where
-  // we keep track of what accessibility objects the browser already knows
-  // about. If we don't find it, then this must be the new root of the
-  // accessibility tree.
-  BrowserTreeNode* browser_node = NULL;
-  base::hash_map<int32, BrowserTreeNode*>::iterator iter =
-    browser_id_map_.find(obj.axID());
-  if (iter != browser_id_map_.end()) {
-    browser_node = iter->second;
-  } else {
-    if (browser_root_) {
-      ClearBrowserTreeNode(browser_root_);
-      browser_id_map_.erase(browser_root_->id);
-      delete browser_root_;
-    }
-    browser_root_ = CreateBrowserTreeNode();
-    browser_node = browser_root_;
-    browser_node->id = obj.axID();
-    browser_node->location = obj.boundingBoxRect();
-    browser_node->parent = NULL;
-    browser_id_map_[browser_node->id] = browser_node;
-  }
-
-  // Iterate over the ids of the children of |obj|.
-  // 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 browser tree
-  // data structure with a different parent, and make sure the old parent
-  // clears this node first.
-  base::hash_set<int32> new_child_ids;
-  const WebDocument& document = GetMainDocument();
-  for (unsigned i = 0; i < obj.childCount(); i++) {
-    WebAXObject child = obj.childAt(i);
-    if (ShouldIncludeChildNode(obj, child)) {
-      int new_child_id = child.axID();
-      new_child_ids.insert(new_child_id);
-
-      BrowserTreeNode* child = browser_id_map_[new_child_id];
-      if (child && child->parent != browser_node) {
-        // The child is being reparented. Find the Blink accessibility
-        // object corresponding to the old parent, or the closest ancestor
-        // still in the tree.
-        BrowserTreeNode* parent = child->parent;
-        WebAXObject parent_obj;
-        while (parent) {
-          parent_obj = document.accessibilityObjectFromID(parent->id);
-
-          if (!parent_obj.isDetached())
-            break;
-          parent = 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_obj, dst, ids_serialized);
-      }
-    }
-  }
-
-  // Go through the old children and delete subtrees for child
-  // ids that are no longer present, and create a map from
-  // id to BrowserTreeNode 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, BrowserTreeNode*> browser_child_id_map;
-  std::vector<BrowserTreeNode*> old_children;
-  old_children.swap(browser_node->children);
-  for (size_t i = 0; i < old_children.size(); i++) {
-    BrowserTreeNode* old_child = old_children[i];
-    int old_child_id = old_child->id;
-    if (new_child_ids.find(old_child_id) == new_child_ids.end()) {
-      browser_id_map_.erase(old_child_id);
-      ClearBrowserTreeNode(old_child);
-      delete old_child;
-    } else {
-      browser_child_id_map[old_child_id] = old_child;
-    }
-  }
-
-  // Serialize this node. This fills in all of the fields in
-  // ui::AXNodeData except child_ids, which we handle below.
-  dst->push_back(ui::AXNodeData());
-  ui::AXNodeData* serialized_node = &dst->back();
-  SerializeAccessibilityNode(obj, serialized_node);
-  if (serialized_node->id == browser_root_->id)
-    serialized_node->role = ui::AX_ROLE_ROOT_WEB_AREA;
-
-  // Iterate over the children, make note of the ones that are new
-  // and need to be serialized, and update the BrowserTreeNode
-  // data structure to reflect the new tree.
-  std::vector<WebAXObject> children_to_serialize;
-  int child_count = obj.childCount();
-  browser_node->children.reserve(child_count);
-  for (int i = 0; i < child_count; i++) {
-    WebAXObject child = obj.childAt(i);
-    int child_id = child.axID();
-
-    // Checks to make sure the child is valid, attached to this node,
-    // and one we want to include in the tree.
-    if (!ShouldIncludeChildNode(obj, child))
-      continue;
 
-    // No need to do anything more with children that aren't new;
-    // the browser will reuse its existing object.
-    if (new_child_ids.find(child_id) == new_child_ids.end())
+    // See if we had a previous location. If not, this whole subtree must
+    // be new, so don't continue to explore this branch.
+    int id = obj.axID();
+    base::hash_map<int, gfx::Rect>::iterator iter = locations_.find(id);
+    if (iter == locations_.end())
       continue;
 
-    new_child_ids.erase(child_id);
-    serialized_node->child_ids.push_back(child_id);
-    if (browser_child_id_map.find(child_id) != browser_child_id_map.end()) {
-      BrowserTreeNode* reused_child = browser_child_id_map[child_id];
-      browser_node->children.push_back(reused_child);
-    } else {
-      BrowserTreeNode* new_child = CreateBrowserTreeNode();
-      new_child->id = child_id;
-      new_child->location = obj.boundingBoxRect();
-      new_child->parent = browser_node;
-      browser_node->children.push_back(new_child);
-      browser_id_map_[child_id] = new_child;
-      children_to_serialize.push_back(child);
+    // If the location has changed, append it to the IPC message.
+    gfx::Rect new_location = obj.boundingBoxRect();
+    if (iter != locations_.end() && iter->second != new_location) {
+      AccessibilityHostMsg_LocationChangeParams message;
+      message.id = id;
+      message.new_location = new_location;
+      messages.push_back(message);
     }
-  }
-
-  // Serialize all of the new children, recursively.
-  for (size_t i = 0; i < children_to_serialize.size(); ++i)
-    SerializeChangedNodes(children_to_serialize[i], dst, ids_serialized);
-}
 
-void RendererAccessibilityComplete::ClearBrowserTreeNode(
-    BrowserTreeNode* browser_node) {
-  for (size_t i = 0; i < browser_node->children.size(); ++i) {
-    browser_id_map_.erase(browser_node->children[i]->id);
-    ClearBrowserTreeNode(browser_node->children[i]);
-    delete browser_node->children[i];
+    // Save the new location.
+    new_locations[id] = new_location;
   }
-  browser_node->children.clear();
+  locations_.swap(new_locations);
+
+  Send(new AccessibilityHostMsg_LocationChanges(routing_id(), messages));
 }
 
 void RendererAccessibilityComplete::OnDoDefaultAction(int acc_obj_id) {