Revert of Refactor content/renderer/accessibility to use AXTreeSerializer.

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 cd17e244ad2d884d2f745ce3b8cee4b489e13c4d..b4ea81e803f53e5ad47ea9539abffb6bacb08e1f 100644
--- a/content/renderer/accessibility/renderer_accessibility_complete.cc
+++ b/content/renderer/accessibility/renderer_accessibility_complete.cc
@@ -8,6 +8,7 @@
 
 #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"
@@ -33,8 +34,7 @@
     RenderViewImpl* render_view)
     : RendererAccessibility(render_view),
       weak_factory_(this),
-      tree_source_(render_view),
-      serializer_(&tree_source_),
+      browser_root_(NULL),
       last_scroll_offset_(gfx::Size()),
       ack_pending_(false) {
   WebAXObject::enableAccessibility();
@@ -57,6 +57,12 @@
 }
 
 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(
@@ -96,6 +102,14 @@
   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);
 }
 
 
@@ -155,6 +169,10 @@
   return RendererAccessibilityTypeComplete;
 }
 
+RendererAccessibilityComplete::BrowserTreeNode::BrowserTreeNode() : id(0) {}
+
+RendererAccessibilityComplete::BrowserTreeNode::~BrowserTreeNode() {}
+
 void RendererAccessibilityComplete::SendPendingAccessibilityEvents() {
   const WebDocument& document = GetMainDocument();
   if (document.isNull())
@@ -193,22 +211,83 @@
     // selection state, so make sure we re-send that whole subtree.
     if (event.event_type ==
         ui::AX_EVENT_SELECTED_CHILDREN_CHANGED) {
-      serializer_.DeleteClientSubtree(obj);
+      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();
+      }
     }
 
     // Allow Blink to cache intermediate results since we're doing a bunch
     // of read-only queries at once.
-    obj.startCachingComputedObjectAttributesUntilTreeMutates();
+    root_object.startCachingComputedObjectAttributesUntilTreeMutates();
 
     AccessibilityHostMsg_EventParams event_msg;
     event_msg.event_type = event.event_type;
     event_msg.id = event.id;
-    serializer_.SerializeChanges(obj, &event_msg.update);
+    std::set<int> ids_serialized;
+    SerializeChangedNodes(obj, &event_msg.nodes, &ids_serialized);
     event_msgs.push_back(event_msg);
 
 #ifndef NDEBUG
     ui::AXTree tree;
-    tree.Unserialize(event_msg.update);
+    ui::AXTreeUpdate update;
+    update.nodes = event_msg.nodes;
+    tree.Unserialize(update);
     VLOG(0) << "Accessibility update: \n"
             << "routing id=" << routing_id()
             << " event="
@@ -223,38 +302,200 @@
 }
 
 void RendererAccessibilityComplete::SendLocationChanges() {
-  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());
+  std::vector<BrowserTreeNode*> location_changes;
+  WebAXObject root_object = GetMainDocument().accessibilityObject();
+  objs_to_explore.push(root_object);
+
   while (objs_to_explore.size()) {
     WebAXObject obj = objs_to_explore.front();
     objs_to_explore.pop();
-
-    // 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())
+    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;
 
-    // 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);
-    }
-
-    // Save the new location.
-    new_locations[id] = new_location;
-  }
-  locations_.swap(new_locations);
-
-  Send(new AccessibilityHostMsg_LocationChanges(routing_id(), messages));
+    // 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())
+      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);
+    }
+  }
+
+  // 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];
+  }
+  browser_node->children.clear();
 }
 
 void RendererAccessibilityComplete::OnDoDefaultAction(int acc_obj_id) {