Send fewer accessibility tree nodes from renderer to browser.

Previously, AccessibilityNodeData was a tree - it contained
its children. Now, each AccessibilityNodeData just stores
the ids of its children, and each message from the renderer
to the browser is a vector of nodes that changed, rather than
a complete subtree.

Any refactoring or changes to tests are just due to
consequences of this change.

This dramatically speeds up accessibility on large
pages like Gmail where notifications frequently get
fired on the root of the accessibility tree even
though very few nodes have changed.

BUG=173488


Review URL: https://chromiumcodereview.appspot.com/12079106

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@186553 0039d316-1c4b-4281-b951-d872f2087c98

7 files changed, 421 insertions, 132 deletions

diff --git a/content/renderer/accessibility/accessibility_node_serializer.cc b/content/renderer/accessibility/accessibility_node_serializer.cc
index 613a453..cb8f8f7f 100644
--- a/content/renderer/accessibility/accessibility_node_serializer.cc
+++ b/content/renderer/accessibility/accessibility_node_serializer.cc
@@ -350,8 +350,7 @@ uint32 ConvertState(const WebAccessibilityObject& o) {
 
 void SerializeAccessibilityNode(
     const WebAccessibilityObject& src,
-    AccessibilityNodeData* dst,
-    bool include_children) {
+    AccessibilityNodeData* dst) {
   dst->name = src.title();
   dst->role = ConvertRole(src.roleValue());
   dst->state = ConvertState(src);
@@ -404,9 +403,6 @@ void SerializeAccessibilityNode(
     dst->int_attributes[dst->ATTR_HIERARCHICAL_LEVEL] = src.hierarchicalLevel();
   }
 
-  if (dst->role == dst->ROLE_SLIDER)
-    include_children = false;
-
   // Treat the active list box item as focused.
   if (dst->role == dst->ROLE_LISTBOX_OPTION && src.isSelectedOptionActive())
     dst->state |= (1 << AccessibilityNodeData::STATE_FOCUSED);
@@ -440,9 +436,6 @@ void SerializeAccessibilityNode(
     if (dst->role == dst->ROLE_EDITABLE_TEXT ||
         dst->role == dst->ROLE_TEXTAREA ||
         dst->role == dst->ROLE_TEXT_FIELD) {
-      // Jaws gets confused by children of text fields, so we ignore them.
-      include_children = false;
-
       dst->int_attributes[dst->ATTR_TEXT_SEL_START] = src.selectionStart();
       dst->int_attributes[dst->ATTR_TEXT_SEL_END] = src.selectionEnd();
 
@@ -590,46 +583,49 @@ void SerializeAccessibilityNode(
     dst->int_attributes[dst->ATTR_TABLE_CELL_ROW_SPAN] = src.cellRowSpan();
   }
 
-  if (include_children) {
-    // Recursively create children.
-    int child_count = src.childCount();
-    std::set<int32> child_ids;
-    for (int i = 0; i < child_count; ++i) {
-      WebAccessibilityObject child = src.childAt(i);
-      int32 child_id = child.axID();
-
-      // The child may be invalid due to issues in webkit accessibility code.
-      // Don't add children that are invalid thus preventing a crash.
-      // https://bugs.webkit.org/show_bug.cgi?id=44149
-      // TODO(ctguil): We may want to remove this check as webkit stabilizes.
-      if (child.isDetached())
-        continue;
-
-      // Children may duplicated in the webkit accessibility tree. Only add a
-      // child once for the web accessibility tree.
-      // https://bugs.webkit.org/show_bug.cgi?id=58930
-      if (child_ids.find(child_id) != child_ids.end())
-        continue;
-      child_ids.insert(child_id);
-
-      // Some nodes appear in the tree in more than one place: for example,
-      // a cell in a table appears as a child of both a row and a column.
-      // Only recursively add child nodes that have this node as its
-      // unignored parent. For child nodes that are actually parented to
-      // somethinng else, store only the ID.
-      //
-      // As an exception, also add children of an iframe element.
-      // https://bugs.webkit.org/show_bug.cgi?id=57066
-      if (is_iframe || IsParentUnignoredOf(src, child)) {
-        dst->children.push_back(AccessibilityNodeData());
-        SerializeAccessibilityNode(child,
-                                   &dst->children.back(),
-                                   include_children);
-      } else {
-        dst->indirect_child_ids.push_back(child_id);
-      }
-    }
+  // Add the ids of *indirect* children - those who are children of this node,
+  // but whose parent is *not* this node. One example is a table
+  // cell, which is a child of both a row and a column. Because the cell's
+  // parent is the row, the row adds it as a child, and the column adds it
+  // as an indirect child.
+  int child_count = src.childCount();
+  for (int i = 0; i < child_count; ++i) {
+    WebAccessibilityObject child = src.childAt(i);
+    if (!is_iframe && !child.isDetached() && !IsParentUnignoredOf(src, child))
+      dst->indirect_child_ids.push_back(child.axID());
   }
 }
 
+bool ShouldIncludeChildNode(
+    const WebAccessibilityObject& parent,
+    const WebAccessibilityObject& child) {
+  switch(parent.roleValue()) {
+  case WebKit::WebAccessibilityRoleSlider:
+  case WebKit::WebAccessibilityRoleEditableText:
+  case WebKit::WebAccessibilityRoleTextArea:
+  case WebKit::WebAccessibilityRoleTextField:
+    return false;
+  default:
+    break;
+  }
+
+  // The child may be invalid due to issues in webkit accessibility code.
+  // Don't add children that are invalid thus preventing a crash.
+  // https://bugs.webkit.org/show_bug.cgi?id=44149
+  // TODO(ctguil): We may want to remove this check as webkit stabilizes.
+  if (child.isDetached())
+    return false;
+
+  // Skip children whose parent isn't this - see indirect_child_ids, above.
+  // As an exception, include children of an iframe element.
+  bool is_iframe = false;
+  WebNode node = parent.node();
+  if (!node.isNull() && node.isElementNode()) {
+    WebElement element = node.to<WebElement>();
+    is_iframe = (element.tagName() == ASCIIToUTF16("IFRAME"));
+  }
+
+  return (is_iframe || IsParentUnignoredOf(parent, child));
+}
+
 }  // namespace content
diff --git a/content/renderer/accessibility/accessibility_node_serializer.h b/content/renderer/accessibility/accessibility_node_serializer.h
index d0fd74b..f0e9525 100644
--- a/content/renderer/accessibility/accessibility_node_serializer.h
+++ b/content/renderer/accessibility/accessibility_node_serializer.h
@@ -12,8 +12,11 @@ namespace content {
 
 void SerializeAccessibilityNode(
     const WebKit::WebAccessibilityObject& src,
-    AccessibilityNodeData* dst,
-    bool include_children);
+    AccessibilityNodeData* dst);
+
+bool ShouldIncludeChildNode(
+    const WebKit::WebAccessibilityObject& parent,
+    const WebKit::WebAccessibilityObject& child);
 
 }  // namespace content
 
diff --git a/content/renderer/accessibility/renderer_accessibility.h b/content/renderer/accessibility/renderer_accessibility.h
index 8f33d2b..b4b56dd 100644
--- a/content/renderer/accessibility/renderer_accessibility.h
+++ b/content/renderer/accessibility/renderer_accessibility.h
@@ -49,7 +49,7 @@ class RenderViewImpl;
 //
 // What both subclasses have in common is that they are responsible for
 //
-class RendererAccessibility : public RenderViewObserver {
+class CONTENT_EXPORT RendererAccessibility : public RenderViewObserver {
  public:
   explicit RendererAccessibility(RenderViewImpl* render_view);
   virtual ~RendererAccessibility();
diff --git a/content/renderer/accessibility/renderer_accessibility_browsertest.cc b/content/renderer/accessibility/renderer_accessibility_browsertest.cc
index 304822e..fbd83367 100644
--- a/content/renderer/accessibility/renderer_accessibility_browsertest.cc
+++ b/content/renderer/accessibility/renderer_accessibility_browsertest.cc
@@ -3,17 +3,57 @@
 // found in the LICENSE file.
 
 #include "base/utf_string_conversions.h"
-#include "content/common/accessibility_messages.h"
 #include "content/common/accessibility_node_data.h"
 #include "content/common/view_messages.h"
 #include "content/public/test/render_view_test.h"
+#include "content/renderer/accessibility/renderer_accessibility_complete.h"
 #include "content/renderer/render_view_impl.h"
 #include "testing/gtest/include/gtest/gtest.h"
 #include "third_party/WebKit/Source/Platform/chromium/public/WebSize.h"
+#include "third_party/WebKit/Source/WebKit/chromium/public/WebAccessibilityObject.h"
+#include "third_party/WebKit/Source/WebKit/chromium/public/WebDocument.h"
 #include "third_party/WebKit/Source/WebKit/chromium/public/WebView.h"
 
+using WebKit::WebAccessibilityObject;
+using WebKit::WebDocument;
+
 namespace content {
 
+class TestRendererAccessibilityComplete : public RendererAccessibilityComplete {
+ public:
+  explicit TestRendererAccessibilityComplete(RenderViewImpl* render_view)
+    : RendererAccessibilityComplete(render_view),
+      browser_tree_node_count_(0) {
+  }
+
+  int browser_tree_node_count() { return browser_tree_node_count_; }
+
+  struct TestBrowserTreeNode : public BrowserTreeNode {
+    TestBrowserTreeNode(TestRendererAccessibilityComplete* owner)
+        : owner_(owner) {
+      owner_->browser_tree_node_count_++;
+    }
+
+    virtual ~TestBrowserTreeNode() {
+      owner_->browser_tree_node_count_--;
+    }
+
+   private:
+    TestRendererAccessibilityComplete* owner_;
+  };
+
+  virtual BrowserTreeNode* CreateBrowserTreeNode() {
+    return new TestBrowserTreeNode(this);
+  }
+
+  void SendPendingAccessibilityNotifications() {
+    RendererAccessibilityComplete::SendPendingAccessibilityNotifications();
+  }
+
+private:
+  int browser_tree_node_count_;
+};
+
 class RendererAccessibilityTest : public RenderViewTest {
  public:
   RendererAccessibilityTest() {}
@@ -38,10 +78,16 @@ class RendererAccessibilityTest : public RenderViewTest {
     ASSERT_TRUE(message);
     Tuple1<std::vector<AccessibilityHostMsg_NotificationParams> > param;
     AccessibilityHostMsg_Notifications::Read(message, &param);
-    ASSERT_EQ(param.a.size(), 1U);
+    ASSERT_GE(param.a.size(), 1U);
     *params = param.a[0];
   }
 
+  int CountAccessibilityNodesSentToBrowser() {
+    AccessibilityHostMsg_NotificationParams notification;
+    GetLastAccNotification(&notification);
+    return notification.nodes.size();
+  }
+
  protected:
   IPC::TestSink* sink_;
 
@@ -49,6 +95,10 @@ class RendererAccessibilityTest : public RenderViewTest {
 };
 
 TEST_F(RendererAccessibilityTest, EditableTextModeFocusNotifications) {
+  // This is not a test of true web accessibility, it's a test of
+  // a mode used on Windows 8 in Metro mode where an extremely simplified
+  // accessibility tree containing only the current focused node is
+  // generated.
   SetMode(AccessibilityModeEditableTextOnly);
 
   // Set a minimum size and give focus so simulated events work.
@@ -76,16 +126,16 @@ TEST_F(RendererAccessibilityTest, EditableTextModeFocusNotifications) {
     GetLastAccNotification(&notification);
     EXPECT_EQ(notification.notification_type,
               AccessibilityNotificationLayoutComplete);
-    EXPECT_EQ(notification.includes_children, true);
     EXPECT_EQ(notification.id, 1);
-    EXPECT_EQ(notification.acc_tree.id, 1);
-    EXPECT_EQ(notification.acc_tree.role,
+    EXPECT_EQ(notification.nodes.size(), 2U);
+    EXPECT_EQ(notification.nodes[0].id, 1);
+    EXPECT_EQ(notification.nodes[0].role,
               AccessibilityNodeData::ROLE_ROOT_WEB_AREA);
-    EXPECT_EQ(notification.acc_tree.state,
+    EXPECT_EQ(notification.nodes[0].state,
               (1U << AccessibilityNodeData::STATE_READONLY) |
               (1U << AccessibilityNodeData::STATE_FOCUSABLE) |
               (1U << AccessibilityNodeData::STATE_FOCUSED));
-    EXPECT_EQ(notification.acc_tree.children.size(), 1U);
+    EXPECT_EQ(notification.nodes[0].child_ids.size(), 1U);
   }
 
   // Now focus the input element, and check everything again.
@@ -97,19 +147,18 @@ TEST_F(RendererAccessibilityTest, EditableTextModeFocusNotifications) {
     GetLastAccNotification(&notification);
     EXPECT_EQ(notification.notification_type,
               AccessibilityNotificationFocusChanged);
-    EXPECT_EQ(notification.includes_children, true);
     EXPECT_EQ(notification.id, 3);
-    EXPECT_EQ(notification.acc_tree.id, 1);
-    EXPECT_EQ(notification.acc_tree.role,
+    EXPECT_EQ(notification.nodes[0].id, 1);
+    EXPECT_EQ(notification.nodes[0].role,
               AccessibilityNodeData::ROLE_ROOT_WEB_AREA);
-    EXPECT_EQ(notification.acc_tree.state,
+    EXPECT_EQ(notification.nodes[0].state,
               (1U << AccessibilityNodeData::STATE_READONLY) |
               (1U << AccessibilityNodeData::STATE_FOCUSABLE));
-    EXPECT_EQ(notification.acc_tree.children.size(), 1U);
-    EXPECT_EQ(notification.acc_tree.children[0].id, 3);
-    EXPECT_EQ(notification.acc_tree.children[0].role,
+    EXPECT_EQ(notification.nodes[0].child_ids.size(), 1U);
+    EXPECT_EQ(notification.nodes[1].id, 3);
+    EXPECT_EQ(notification.nodes[1].role,
               AccessibilityNodeData::ROLE_GROUP);
-    EXPECT_EQ(notification.acc_tree.children[0].state,
+    EXPECT_EQ(notification.nodes[1].state,
               (1U << AccessibilityNodeData::STATE_FOCUSABLE) |
               (1U << AccessibilityNodeData::STATE_FOCUSED));
   }
@@ -122,7 +171,7 @@ TEST_F(RendererAccessibilityTest, EditableTextModeFocusNotifications) {
     AccessibilityHostMsg_NotificationParams notification;
     GetLastAccNotification(&notification);
     EXPECT_EQ(notification.id, 4);
-    EXPECT_EQ(notification.acc_tree.children[0].state,
+    EXPECT_EQ(notification.nodes[1].state,
               (1U << AccessibilityNodeData::STATE_FOCUSABLE) |
               (1U << AccessibilityNodeData::STATE_FOCUSED));
   }
@@ -134,7 +183,7 @@ TEST_F(RendererAccessibilityTest, EditableTextModeFocusNotifications) {
     AccessibilityHostMsg_NotificationParams notification;
     GetLastAccNotification(&notification);
     EXPECT_EQ(notification.id, 5);
-    EXPECT_EQ(notification.acc_tree.children[0].state,
+    EXPECT_EQ(notification.nodes[1].state,
               (1U << AccessibilityNodeData::STATE_FOCUSABLE) |
               (1U << AccessibilityNodeData::STATE_FOCUSED));
   }
@@ -146,7 +195,7 @@ TEST_F(RendererAccessibilityTest, EditableTextModeFocusNotifications) {
     AccessibilityHostMsg_NotificationParams notification;
     GetLastAccNotification(&notification);
     EXPECT_EQ(notification.id, 6);
-    EXPECT_EQ(notification.acc_tree.children[0].state,
+    EXPECT_EQ(notification.nodes[1].state,
               (1U << AccessibilityNodeData::STATE_FOCUSABLE) |
               (1U << AccessibilityNodeData::STATE_FOCUSED));
   }
@@ -159,7 +208,7 @@ TEST_F(RendererAccessibilityTest, EditableTextModeFocusNotifications) {
     AccessibilityHostMsg_NotificationParams notification;
     GetLastAccNotification(&notification);
     EXPECT_EQ(notification.id, 7);
-    EXPECT_EQ(notification.acc_tree.children[0].state,
+    EXPECT_EQ(notification.nodes[1].state,
               (1U << AccessibilityNodeData::STATE_FOCUSABLE) |
               (1U << AccessibilityNodeData::STATE_FOCUSED) |
               (1U << AccessibilityNodeData::STATE_READONLY));
@@ -172,7 +221,7 @@ TEST_F(RendererAccessibilityTest, EditableTextModeFocusNotifications) {
     AccessibilityHostMsg_NotificationParams notification;
     GetLastAccNotification(&notification);
     EXPECT_EQ(notification.id, 8);
-    EXPECT_EQ(notification.acc_tree.children[0].state,
+    EXPECT_EQ(notification.nodes[1].state,
               (1U << AccessibilityNodeData::STATE_FOCUSABLE) |
               (1U << AccessibilityNodeData::STATE_FOCUSED) |
               (1U << AccessibilityNodeData::STATE_READONLY));
@@ -189,4 +238,163 @@ TEST_F(RendererAccessibilityTest, EditableTextModeFocusNotifications) {
   }
 }
 
+TEST_F(RendererAccessibilityTest, SendFullAccessibilityTreeOnReload) {
+  // The job of RendererAccessibilityComplete is to serialize the
+  // accessibility tree built by WebKit and send it to the browser.
+  // When the accessibility tree changes, it tries to send only
+  // the nodes that actually changed or were reparented. This test
+  // ensures that the messages sent are correct in cases when a page
+  // reloads, and that internal state is properly garbage-collected.
+  std::string html =
+      "<body>"
+      "  <div role='group' id='A'>"
+      "    <div role='group' id='A1'></div>"
+      "    <div role='group' id='A2'></div>"
+      "  </div>"
+      "</body>";
+  LoadHTML(html.c_str());
+
+  // Creating a RendererAccessibilityComplete should sent the tree
+  // to the browser.
+  scoped_ptr<TestRendererAccessibilityComplete> accessibility(
+      new TestRendererAccessibilityComplete(view()));
+  accessibility->SendPendingAccessibilityNotifications();
+  EXPECT_EQ(4, accessibility->browser_tree_node_count());
+  EXPECT_EQ(4, CountAccessibilityNodesSentToBrowser());
+
+  // If we post another notification but the tree doesn't change,
+  // we should only send 1 node to the browser.
+  sink_->ClearMessages();
+  WebDocument document = view()->GetWebView()->mainFrame()->document();
+  WebAccessibilityObject root_obj = document.accessibilityObject();
+  accessibility->HandleWebAccessibilityNotification(
+      root_obj,
+      WebKit::WebAccessibilityNotificationLayoutComplete);
+  accessibility->SendPendingAccessibilityNotifications();
+  EXPECT_EQ(4, accessibility->browser_tree_node_count());
+  EXPECT_EQ(1, CountAccessibilityNodesSentToBrowser());
+  {
+    // Make sure it's the root object that was updated.
+    AccessibilityHostMsg_NotificationParams notification;
+    GetLastAccNotification(&notification);
+    EXPECT_EQ(root_obj.axID(), notification.nodes[0].id);
+  }
+
+  // If we reload the page and send a notification, we should send
+  // all 4 nodes to the browser. Also double-check that we didn't
+  // leak any of the old BrowserTreeNodes.
+  LoadHTML(html.c_str());
+  document = view()->GetWebView()->mainFrame()->document();
+  root_obj = document.accessibilityObject();
+  sink_->ClearMessages();
+  accessibility->HandleWebAccessibilityNotification(
+      root_obj,
+      WebKit::WebAccessibilityNotificationLayoutComplete);
+  accessibility->SendPendingAccessibilityNotifications();
+  EXPECT_EQ(4, accessibility->browser_tree_node_count());
+  EXPECT_EQ(4, CountAccessibilityNodesSentToBrowser());
+
+  // Even if the first notification is sent on an element other than
+  // the root, the whole tree should be updated because we know
+  // the browser doesn't have the root element.
+  LoadHTML(html.c_str());
+  document = view()->GetWebView()->mainFrame()->document();
+  root_obj = document.accessibilityObject();
+  sink_->ClearMessages();
+  const WebAccessibilityObject& first_child = root_obj.firstChild();
+  accessibility->HandleWebAccessibilityNotification(
+      first_child,
+      WebKit::WebAccessibilityNotificationLiveRegionChanged);
+  accessibility->SendPendingAccessibilityNotifications();
+  EXPECT_EQ(4, accessibility->browser_tree_node_count());
+  EXPECT_EQ(4, CountAccessibilityNodesSentToBrowser());
+}
+
+TEST_F(RendererAccessibilityTest, HideAccessibilityObject) {
+  // Test RendererAccessibilityComplete and make sure it sends the
+  // proper notification to the browser when an object in the tree
+  // is hidden, but its children are not.
+  std::string html =
+      "<body>"
+      "  <div role='group' id='A'>"
+      "    <div role='group' id='B'>"
+      "      <div role='group' id='C' style='visibility:visible'>"
+      "      </div>"
+      "    </div>"
+      "  </div>"
+      "</body>";
+  LoadHTML(html.c_str());
+
+  scoped_ptr<TestRendererAccessibilityComplete> accessibility(
+      new TestRendererAccessibilityComplete(view()));
+  accessibility->SendPendingAccessibilityNotifications();
+  EXPECT_EQ(4, accessibility->browser_tree_node_count());
+  EXPECT_EQ(4, CountAccessibilityNodesSentToBrowser());
+
+  // Hide node 'B' ('C' stays visible).
+  ExecuteJavaScript(
+      "document.getElementById('B').style.visibility = 'hidden';");
+  // Force layout now.
+  ExecuteJavaScript("document.getElementById('B').offsetLeft;");
+
+  // Send a childrenChanged on 'A'.
+  sink_->ClearMessages();
+  WebDocument document = view()->GetWebView()->mainFrame()->document();
+  WebAccessibilityObject root_obj = document.accessibilityObject();
+  WebAccessibilityObject node_a = root_obj.childAt(0);
+  accessibility->HandleWebAccessibilityNotification(
+      node_a,
+      WebKit::WebAccessibilityNotificationChildrenChanged);
+
+  accessibility->SendPendingAccessibilityNotifications();
+  EXPECT_EQ(3, accessibility->browser_tree_node_count());
+  AccessibilityHostMsg_NotificationParams notification;
+  GetLastAccNotification(&notification);
+  ASSERT_EQ(2U, notification.nodes.size());
+  EXPECT_EQ(2, CountAccessibilityNodesSentToBrowser());
+}
+
+TEST_F(RendererAccessibilityTest, ShowAccessibilityObject) {
+  // Test RendererAccessibilityComplete and make sure it sends the
+  // proper notification to the browser when an object in the tree
+  // is shown, causing its own already-visible children to be
+  // reparented to it.
+  std::string html =
+      "<body>"
+      "  <div role='group' id='A'>"
+      "    <div role='group' id='B' style='visibility:hidden'>"
+      "      <div role='group' id='C' style='visibility:visible'>"
+      "      </div>"
+      "    </div>"
+      "  </div>"
+      "</body>";
+  LoadHTML(html.c_str());
+
+  scoped_ptr<TestRendererAccessibilityComplete> accessibility(
+      new TestRendererAccessibilityComplete(view()));
+  accessibility->SendPendingAccessibilityNotifications();
+  EXPECT_EQ(3, accessibility->browser_tree_node_count());
+  EXPECT_EQ(3, CountAccessibilityNodesSentToBrowser());
+
+  // Show node 'B', then send a childrenChanged on 'A'.
+  ExecuteJavaScript(
+      "document.getElementById('B').style.visibility = 'visible';");
+  ExecuteJavaScript("document.getElementById('B').offsetLeft;");
+
+  sink_->ClearMessages();
+  WebDocument document = view()->GetWebView()->mainFrame()->document();
+  WebAccessibilityObject root_obj = document.accessibilityObject();
+  WebAccessibilityObject node_a = root_obj.childAt(0);
+  accessibility->HandleWebAccessibilityNotification(
+      node_a,
+      WebKit::WebAccessibilityNotificationChildrenChanged);
+
+  accessibility->SendPendingAccessibilityNotifications();
+  EXPECT_EQ(4, accessibility->browser_tree_node_count());
+  AccessibilityHostMsg_NotificationParams notification;
+  GetLastAccNotification(&notification);
+  ASSERT_EQ(3U, notification.nodes.size());
+  EXPECT_EQ(3, CountAccessibilityNodesSentToBrowser());
+}
+
 }  // namespace content
diff --git a/content/renderer/accessibility/renderer_accessibility_complete.cc b/content/renderer/accessibility/renderer_accessibility_complete.cc
index 80923d1..6ece9dc 100644
--- a/content/renderer/accessibility/renderer_accessibility_complete.cc
+++ b/content/renderer/accessibility/renderer_accessibility_complete.cc
@@ -85,6 +85,9 @@ bool WebAccessibilityNotificationToAccessibilityNotification(
     case WebKit::WebAccessibilityNotificationSelectedTextChanged:
       *type = AccessibilityNotificationSelectedTextChanged;
       break;
+    case WebKit::WebAccessibilityNotificationTextChanged:
+      *type = AccessibilityNotificationTextChanged;
+      break;
     case WebKit::WebAccessibilityNotificationValueChanged:
       *type = AccessibilityNotificationValueChanged;
       break;
@@ -134,6 +137,7 @@ bool RendererAccessibilityComplete::OnMessageReceived(
                         OnScrollToPoint)
     IPC_MESSAGE_HANDLER(AccessibilityMsg_SetTextSelection,
                         OnSetTextSelection)
+    IPC_MESSAGE_HANDLER(AccessibilityMsg_FatalError, OnFatalError)
     IPC_MESSAGE_UNHANDLED(handled = false)
   IPC_END_MESSAGE_MAP()
   return handled;
@@ -261,11 +265,6 @@ void RendererAccessibilityComplete::SendPendingAccessibilityNotifications() {
     AccessibilityHostMsg_NotificationParams& notification =
         src_notifications[i];
 
-    // TODO(dtseng): Come up with a cleaner way of deciding to include children.
-    WebAccessibilityObject rootObject = document.accessibilityObject();
-    int root_id = rootObject.axID();
-    bool includes_children = ShouldIncludeChildren(notification) ||
-        root_id == notification.id;
     WebAccessibilityObject obj = document.accessibilityObjectFromID(
         notification.id);
     if (!obj.updateBackingStoreAndCheckValidity())
@@ -276,11 +275,12 @@ void RendererAccessibilityComplete::SendPendingAccessibilityNotifications() {
     // notification 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.
+    WebAccessibilityObject 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();
-      includes_children = true;
       if (notification.notification_type ==
           AccessibilityNotificationChildrenChanged) {
         notification.id = obj.axID();
@@ -323,39 +323,28 @@ void RendererAccessibilityComplete::SendPendingAccessibilityNotifications() {
       if (!is_child_of_parent) {
         obj = parent;
         notification.id = obj.axID();
-        includes_children = true;
       }
     }
 
     // Allow WebKit to cache intermediate results since we're doing a bunch
     // of read-only queries at once.
-    rootObject.startCachingComputedObjectAttributesUntilTreeMutates();
+    root_object.startCachingComputedObjectAttributesUntilTreeMutates();
 
     AccessibilityHostMsg_NotificationParams notification_msg;
     notification_msg.notification_type = notification.notification_type;
     notification_msg.id = notification.id;
-    notification_msg.includes_children = includes_children;
-    SerializeAccessibilityNode(obj,
-                               &notification_msg.acc_tree,
-                               includes_children);
-    if (obj.axID() == root_id) {
-      DCHECK_EQ(notification_msg.acc_tree.role,
-                AccessibilityNodeData::ROLE_WEB_AREA);
-      notification_msg.acc_tree.role =
-          AccessibilityNodeData::ROLE_ROOT_WEB_AREA;
-    }
+    SerializeChangedNodes(obj, &notification_msg.nodes);
     notification_msgs.push_back(notification_msg);
 
-    if (includes_children)
-      UpdateBrowserTree(notification_msg.acc_tree);
-
 #ifndef NDEBUG
     if (logging_) {
+      AccessibilityNodeDataTreeNode tree;
+      MakeAccessibilityNodeDataTree(notification_msg.nodes, &tree);
       LOG(INFO) << "Accessibility update: \n"
           << "routing id=" << routing_id()
           << " notification="
           << AccessibilityNotificationToString(notification.notification_type)
-          << "\n" << notification_msg.acc_tree.DebugString(true);
+          << "\n" << tree.DebugString(true);
     }
 #endif
   }
@@ -363,34 +352,118 @@ void RendererAccessibilityComplete::SendPendingAccessibilityNotifications() {
   Send(new AccessibilityHostMsg_Notifications(routing_id(), notification_msgs));
 }
 
-void RendererAccessibilityComplete::UpdateBrowserTree(
-    const AccessibilityNodeData& renderer_node) {
+RendererAccessibilityComplete::BrowserTreeNode*
+RendererAccessibilityComplete::CreateBrowserTreeNode() {
+  return new RendererAccessibilityComplete::BrowserTreeNode();
+}
+
+void RendererAccessibilityComplete::SerializeChangedNodes(
+    const WebKit::WebAccessibilityObject& obj,
+    std::vector<AccessibilityNodeData>* dst) {
+  // This method has three responsibilities:
+  // 1. Serialize |obj| into an AccessibilityNodeData, 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(renderer_node.id);
+    browser_id_map_.find(obj.axID());
   if (iter != browser_id_map_.end()) {
     browser_node = iter->second;
-    ClearBrowserTreeNode(browser_node);
   } else {
-    DCHECK_EQ(renderer_node.role, AccessibilityNodeData::ROLE_ROOT_WEB_AREA);
     if (browser_root_) {
       ClearBrowserTreeNode(browser_root_);
       browser_id_map_.erase(browser_root_->id);
       delete browser_root_;
     }
-    browser_root_ = new BrowserTreeNode;
+    browser_root_ = CreateBrowserTreeNode();
     browser_node = browser_root_;
-    browser_node->id = renderer_node.id;
+    browser_node->id = obj.axID();
     browser_id_map_[browser_node->id] = browser_node;
   }
-  browser_node->children.reserve(renderer_node.children.size());
-  for (size_t i = 0; i < renderer_node.children.size(); ++i) {
-    BrowserTreeNode* browser_child_node = new BrowserTreeNode;
-    browser_child_node->id = renderer_node.children[i].id;
-    browser_id_map_[browser_child_node->id] = browser_child_node;
-    browser_node->children.push_back(browser_child_node);
-    UpdateBrowserTree(renderer_node.children[i]);
+
+  // Serialize this node. This fills in all of the fields in
+  // AccessibilityNodeData except child_ids, which we handle below.
+  dst->push_back(AccessibilityNodeData());
+  AccessibilityNodeData* serialized_node = &dst->back();
+  SerializeAccessibilityNode(obj, serialized_node);
+  if (serialized_node->id == browser_root_->id)
+    serialized_node->role = AccessibilityNodeData::ROLE_ROOT_WEB_AREA;
+
+  // Create set of the ids of the children of |obj| so we can quickly look
+  // up which children are new and which ones were there before.
+  base::hash_set<int32> new_child_ids;
+  for (unsigned i = 0; i < obj.childCount(); i++) {
+    WebAccessibilityObject child = obj.childAt(i);
+    if (ShouldIncludeChildNode(obj, child)) {
+      new_child_ids.insert(child.axID());
+    }
+  }
+
+  // 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;
+    }
   }
+
+  // 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<WebAccessibilityObject> children_to_serialize;
+  int child_count = obj.childCount();
+  browser_node->children.reserve(child_count);
+  for (int i = 0; i < child_count; i++) {
+    WebAccessibilityObject 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())
+      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()) {
+      browser_node->children.push_back(browser_child_id_map[child_id]);
+    } else {
+      BrowserTreeNode* new_child = CreateBrowserTreeNode();
+      new_child->id = child_id;
+      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);
 }
 
 void RendererAccessibilityComplete::ClearBrowserTreeNode(
@@ -540,6 +613,10 @@ void RendererAccessibilityComplete::OnSetFocus(int acc_obj_id) {
     obj.setFocused(true);
 }
 
+void RendererAccessibilityComplete::OnFatalError() {
+  CHECK(false);
+}
+
 bool RendererAccessibilityComplete::ShouldIncludeChildren(
     const AccessibilityHostMsg_NotificationParams& notification) {
   AccessibilityNotification type = notification.notification_type;
diff --git a/content/renderer/accessibility/renderer_accessibility_complete.h b/content/renderer/accessibility/renderer_accessibility_complete.h
index e03c0e9..b338a90 100644
--- a/content/renderer/accessibility/renderer_accessibility_complete.h
+++ b/content/renderer/accessibility/renderer_accessibility_complete.h
@@ -31,7 +31,8 @@ class RenderViewImpl;
 // a serialized representation of that tree whenever it changes. It also
 // handles requests from the browser to perform accessibility actions on
 // nodes in the tree (e.g., change focus, or click on a button).
-class RendererAccessibilityComplete : public RendererAccessibility {
+class CONTENT_EXPORT RendererAccessibilityComplete
+    : public RendererAccessibility {
  public:
   explicit RendererAccessibilityComplete(RenderViewImpl* render_view);
   virtual ~RendererAccessibilityComplete();
@@ -46,28 +47,33 @@ class RendererAccessibilityComplete : public RendererAccessibility {
       const WebKit::WebAccessibilityObject& obj,
       WebKit::WebAccessibilityNotification notification) OVERRIDE;
 
- private:
-  // Handle an accessibility notification to be sent to the browser process.
-  void HandleAccessibilityNotification(
-      const WebKit::WebAccessibilityObject& obj,
-      AccessibilityNotification notification);
-
   // In order to keep track of what nodes the browser knows about, we keep a
   // representation of the browser tree - just IDs and parent/child
   // relationships.
-  struct BrowserTreeNode {
+  struct CONTENT_EXPORT BrowserTreeNode {
     BrowserTreeNode();
-    ~BrowserTreeNode();
+    virtual ~BrowserTreeNode();
     int32 id;
     std::vector<BrowserTreeNode*> children;
   };
 
+  virtual BrowserTreeNode* CreateBrowserTreeNode();
+
+ protected:
   // Send queued notifications from the renderer to the browser.
   void SendPendingAccessibilityNotifications();
 
-  // Update our representation of what nodes the browser has, given a
-  // tree of nodes.
-  void UpdateBrowserTree(const AccessibilityNodeData& renderer_node);
+ private:
+  // Handle an accessibility notification to be sent to the browser process.
+  void HandleAccessibilityNotification(
+      const WebKit::WebAccessibilityObject& obj,
+      AccessibilityNotification notification);
+
+  // Serialize the given accessibility object |obj| and append it to
+  // |dst|, and then recursively also serialize any *new* children of
+  // |obj|, based on what object ids we know the browser already has.
+  void SerializeChangedNodes(const WebKit::WebAccessibilityObject& obj,
+                             std::vector<AccessibilityNodeData>* dst);
 
   // Clear the given node and recursively delete all of its descendants
   // from the browser tree. (Does not delete |browser_node|).
@@ -80,8 +86,8 @@ class RendererAccessibilityComplete : public RendererAccessibility {
   void OnScrollToMakeVisible(int acc_obj_id, gfx::Rect subfocus);
   void OnScrollToPoint(int acc_obj_id, gfx::Point point);
   void OnSetFocus(int acc_obj_id);
-
   void OnSetTextSelection(int acc_obj_id, int start_offset, int end_offset);
+  void OnFatalError();
 
   // Whether or not this notification typically needs to send
   // updates to its children, too.
diff --git a/content/renderer/accessibility/renderer_accessibility_focus_only.cc b/content/renderer/accessibility/renderer_accessibility_focus_only.cc
index 601bc16..71da433 100644
--- a/content/renderer/accessibility/renderer_accessibility_focus_only.cc
+++ b/content/renderer/accessibility/renderer_accessibility_focus_only.cc
@@ -92,26 +92,25 @@ void RendererAccessibilityFocusOnly::HandleFocusedNodeChanged(
       AccessibilityNotificationFocusChanged :
       AccessibilityNotificationLayoutComplete;
 
-  // This means that the new tree we send supercedes any previous tree,
-  // not just a previous node.
-  notification.includes_children = true;
-
   // Set the id that the notification applies to: the root node if nothing
   // has focus, otherwise the focused node.
   notification.id = node_has_focus ? next_id_ : 1;
 
   // Always include the root of the tree, the document. It always has id 1.
-  notification.acc_tree.id = 1;
-  notification.acc_tree.role = AccessibilityNodeData::ROLE_ROOT_WEB_AREA;
-  notification.acc_tree.state =
+  notification.nodes.push_back(AccessibilityNodeData());
+  AccessibilityNodeData& root = notification.nodes[0];
+  root.id = 1;
+  root.role = AccessibilityNodeData::ROLE_ROOT_WEB_AREA;
+  root.state =
       (1 << AccessibilityNodeData::STATE_READONLY) |
       (1 << AccessibilityNodeData::STATE_FOCUSABLE);
   if (!node_has_focus)
-    notification.acc_tree.state |= (1 << AccessibilityNodeData::STATE_FOCUSED);
-  notification.acc_tree.location = gfx::Rect(render_view_->size());
+    root.state |= (1 << AccessibilityNodeData::STATE_FOCUSED);
+  root.location = gfx::Rect(render_view_->size());
+  root.child_ids.push_back(next_id_);
 
-  notification.acc_tree.children.push_back(AccessibilityNodeData());
-  AccessibilityNodeData& child = notification.acc_tree.children[0];
+  notification.nodes.push_back(AccessibilityNodeData());
+  AccessibilityNodeData& child = notification.nodes[1];
   child.id = next_id_;
   child.role = AccessibilityNodeData::ROLE_GROUP;
 
@@ -119,7 +118,7 @@ void RendererAccessibilityFocusOnly::HandleFocusedNodeChanged(
     child.location = gfx::Rect(
         const_cast<WebNode&>(node).to<WebElement>().boundsInViewportSpace());
   } else if (render_view_->HasIMETextFocus()) {
-    child.location = notification.acc_tree.location;
+    child.location = root.location;
   } else {
     child.location = gfx::Rect();
   }
@@ -138,7 +137,7 @@ void RendererAccessibilityFocusOnly::HandleFocusedNodeChanged(
         << "routing id=" << routing_id()
         << " notification="
         << AccessibilityNotificationToString(notification.notification_type)
-        << "\n" << notification.acc_tree.DebugString(true);
+        << "\n" << notification.nodes[0].DebugString(true);
   }
 #endif