Rewriting automation_node update handling based on ax_tree

BUG=309681

Review URL: https://codereview.chromium.org/326233002

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

22 files changed, 840 insertions, 194 deletions

diff --git a/chrome/browser/extensions/api/automation/automation_apitest.cc b/chrome/browser/extensions/api/automation/automation_apitest.cc
index 692df7b..e2a42df 100644
--- a/chrome/browser/extensions/api/automation/automation_apitest.cc
+++ b/chrome/browser/extensions/api/automation/automation_apitest.cc
@@ -5,18 +5,27 @@
 #include "base/files/file_path.h"
 #include "base/path_service.h"
 #include "base/strings/string_number_conversions.h"
+#include "chrome/browser/extensions/api/automation_internal/automation_util.h"
+#include "chrome/browser/extensions/chrome_extension_function.h"
 #include "chrome/browser/extensions/extension_apitest.h"
 #include "chrome/browser/extensions/extension_test_message_listener.h"
 #include "chrome/browser/ui/tabs/tab_strip_model.h"
 #include "chrome/common/chrome_paths.h"
 #include "chrome/common/chrome_switches.h"
+#include "chrome/common/extensions/api/automation_internal.h"
 #include "chrome/test/base/ui_test_utils.h"
+#include "content/public/browser/ax_event_notification_details.h"
 #include "content/public/browser/render_widget_host.h"
 #include "content/public/browser/render_widget_host_view.h"
 #include "content/public/browser/web_contents.h"
 #include "net/dns/mock_host_resolver.h"
 #include "net/test/embedded_test_server/embedded_test_server.h"
 #include "testing/gtest/include/gtest/gtest.h"
+#include "ui/accessibility/ax_node.h"
+#include "ui/accessibility/ax_serializable_tree.h"
+#include "ui/accessibility/ax_tree.h"
+#include "ui/accessibility/ax_tree_serializer.h"
+#include "ui/accessibility/tree_generator.h"
 
 namespace extensions {
 
@@ -183,4 +192,324 @@ IN_PROC_BROWSER_TEST_F(AutomationApiTest, DesktopNotSupported) {
 }
 #endif
 
+static const int kPid = 1;
+static const int kTab0Rid = 1;
+static const int kTab1Rid = 2;
+
+using content::BrowserContext;
+
+typedef ui::AXTreeSerializer<const ui::AXNode*> TreeSerializer;
+typedef ui::AXTreeSource<const ui::AXNode*> TreeSource;
+
+#define AX_EVENT_ASSERT_EQUAL ui::AX_EVENT_LOAD_COMPLETE
+#define AX_EVENT_ASSERT_NOT_EQUAL ui::AX_EVENT_ACTIVEDESCENDANTCHANGED
+#define AX_EVENT_IGNORE ui::AX_EVENT_CHILDREN_CHANGED
+#define AX_EVENT_TEST_COMPLETE ui::AX_EVENT_BLUR
+
+// This test is based on ui/accessibility/ax_generated_tree_unittest.cc
+// However, because the tree updates need to be sent to the extension, we can't
+// use a straightforward set of nested loops as that test does, so this class
+// keeps track of where we're up to in our imaginary loops, while the extension
+// function classes below do the work of actually incrementing the state when
+// appropriate.
+// The actual deserialization and comparison happens in the API bindings and the
+// test extension respectively: see
+// c/t/data/extensions/api_test/automation/tests/generated/generated_trees.js
+class TreeSerializationState {
+ public:
+  TreeSerializationState()
+      : tree_size(3),
+        generator(tree_size),
+        num_trees(generator.UniqueTreeCount()),
+        tree0_version(0),
+        tree1_version(0) {
+  }
+
+  // Serializes tree and sends it as an accessibility event to the extension.
+  void SendDataForTree(const ui::AXTree* tree,
+                       TreeSerializer* serializer,
+                       int routing_id,
+                       BrowserContext* browser_context) {
+    ui::AXTreeUpdate update;
+    serializer->SerializeChanges(tree->GetRoot(), &update);
+    SendUpdate(update,
+               ui::AX_EVENT_LAYOUT_COMPLETE,
+               tree->GetRoot()->id(),
+               routing_id,
+               browser_context);
+  }
+
+  // Sends the given AXTreeUpdate to the extension as an accessibility event.
+  void SendUpdate(ui::AXTreeUpdate update,
+                  ui::AXEvent event,
+                  int node_id,
+                  int routing_id,
+                  BrowserContext* browser_context) {
+    content::AXEventNotificationDetails detail(update.node_id_to_clear,
+                                               update.nodes,
+                                               event,
+                                               node_id,
+                                               kPid,
+                                               routing_id);
+    std::vector<content::AXEventNotificationDetails> details;
+    details.push_back(detail);
+    automation_util::DispatchAccessibilityEventsToAutomation(details,
+                                                             browser_context);
+  }
+
+  // Notify the extension bindings to destroy the tree for the given tab
+  // (identified by routing_id)
+  void SendTreeDestroyedEvent(int routing_id, BrowserContext* browser_context) {
+    automation_util::DispatchTreeDestroyedEventToAutomation(
+        kPid, routing_id, browser_context);
+  }
+
+  // Reset tree0 to a new generated tree based on tree0_version, reset
+  // tree0_source accordingly.
+  void ResetTree0() {
+    tree0.reset(new ui::AXSerializableTree);
+    tree0_source.reset(tree0->CreateTreeSource());
+    generator.BuildUniqueTree(tree0_version, tree0.get());
+    if (!serializer0.get())
+      serializer0.reset(new TreeSerializer(tree0_source.get()));
+  }
+
+  // Reset tree0, set up serializer0, send down the initial tree data to create
+  // the tree in the extension
+  void InitializeTree0(BrowserContext* browser_context) {
+    ResetTree0();
+    serializer0->ChangeTreeSourceForTesting(tree0_source.get());
+    serializer0->Reset();
+    SendDataForTree(tree0.get(), serializer0.get(), kTab0Rid, browser_context);
+  }
+
+  // Reset tree1 to a new generated tree based on tree1_version, reset
+  // tree1_source accordingly.
+  void ResetTree1() {
+    tree1.reset(new ui::AXSerializableTree);
+    tree1_source.reset(tree1->CreateTreeSource());
+    generator.BuildUniqueTree(tree1_version, tree1.get());
+    if (!serializer1.get())
+      serializer1.reset(new TreeSerializer(tree1_source.get()));
+  }
+
+  // Reset tree1, set up serializer1, send down the initial tree data to create
+  // the tree in the extension
+  void InitializeTree1(BrowserContext* browser_context) {
+    ResetTree1();
+    serializer1->ChangeTreeSourceForTesting(tree1_source.get());
+    serializer1->Reset();
+    SendDataForTree(tree1.get(), serializer1.get(), kTab1Rid, browser_context);
+  }
+
+  const int tree_size;
+  const ui::TreeGenerator generator;
+
+  // The loop variables: comments indicate which variables in
+  // ax_generated_tree_unittest they correspond to.
+  const int num_trees; // n
+  int tree0_version;   // i
+  int tree1_version;   // j
+  int starting_node;   // k
+
+  // Tree infrastructure; tree0 and tree1 need to be regenerated whenever
+  // tree0_version and tree1_version change, respectively; tree0_source and
+  // tree1_source need to be reset whenever that happens.
+  scoped_ptr<ui::AXSerializableTree> tree0, tree1;
+  scoped_ptr<TreeSource> tree0_source, tree1_source;
+  scoped_ptr<TreeSerializer> serializer0, serializer1;
+
+  // Whether tree0 needs to be destroyed after the extension has performed its
+  // checks
+  bool destroy_tree0;
+};
+
+static TreeSerializationState state;
+
+// Override for chrome.automationInternal.enableTab
+// This fakes out the process and routing IDs for two "tabs", which contain the
+// source and target trees, respectively, and sends down the current tree for
+// the requested tab - tab 1 always has tree1, and tab 0 starts with tree0
+// and then has a series of updates intended to translate tree0 to tree1.
+// Once all the updates have been sent, the extension asserts that both trees
+// are equivalent, and then one or both of the trees are reset to a new version.
+class FakeAutomationInternalEnableTabFunction
+    : public UIThreadExtensionFunction {
+ public:
+  FakeAutomationInternalEnableTabFunction() {}
+
+  ExtensionFunction::ResponseAction Run() OVERRIDE {
+    using api::automation_internal::EnableTab::Params;
+    scoped_ptr<Params> params(Params::Create(*args_));
+    EXTENSION_FUNCTION_VALIDATE(params.get());
+    if (!params->tab_id.get())
+      return RespondNow(Error("tab_id not specified"));
+    int tab_id = *params->tab_id;
+    if (tab_id == 0) {
+      // tab 0 <--> tree0
+      base::MessageLoop::current()->PostTask(
+          FROM_HERE,
+          base::Bind(&TreeSerializationState::InitializeTree0,
+                     base::Unretained(&state),
+                     base::Unretained(browser_context())));
+      return RespondNow(
+          ArgumentList(api::automation_internal::EnableTab::Results::Create(
+              kPid, kTab0Rid)));
+    }
+    if (tab_id == 1) {
+      // tab 1 <--> tree1
+      base::MessageLoop::current()->PostTask(
+          FROM_HERE,
+          base::Bind(&TreeSerializationState::InitializeTree1,
+                     base::Unretained(&state),
+                     base::Unretained(browser_context())));
+      return RespondNow(
+          ArgumentList(api::automation_internal::EnableTab::Results::Create(
+              kPid, kTab1Rid)));
+    }
+    return RespondNow(Error("Unrecognised tab_id"));
+  }
+};
+
+// Factory method for use in OverrideFunction()
+ExtensionFunction* FakeAutomationInternalEnableTabFunctionFactory() {
+  return new FakeAutomationInternalEnableTabFunction();
+}
+
+// Helper method to serialize a series of updates via source_serializer to
+// transform the tree which source_serializer was initialized from into
+// target_tree, and then trigger the test code to assert the two tabs contain
+// the same tree.
+void TransformTree(TreeSerializer* source_serializer,
+                   ui::AXTree* target_tree,
+                   TreeSource* target_tree_source,
+                   content::BrowserContext* browser_context) {
+  source_serializer->ChangeTreeSourceForTesting(target_tree_source);
+  for (int node_delta = 0; node_delta < state.tree_size; ++node_delta) {
+    int id = 1 + (state.starting_node + node_delta) % state.tree_size;
+    ui::AXTreeUpdate update;
+    source_serializer->SerializeChanges(target_tree->GetFromId(id), &update);
+    bool is_last_update = node_delta == state.tree_size - 1;
+    ui::AXEvent event =
+        is_last_update ? AX_EVENT_ASSERT_EQUAL : AX_EVENT_IGNORE;
+    state.SendUpdate(
+        update, event, target_tree->GetRoot()->id(), kTab0Rid, browser_context);
+  }
+}
+
+// Helper method to send a no-op tree update to tab 0 with the given event.
+void SendEvent(ui::AXEvent event, content::BrowserContext* browser_context) {
+  ui::AXTreeUpdate update;
+  ui::AXNode* root = state.tree0->GetRoot();
+  state.serializer0->SerializeChanges(root, &update);
+  state.SendUpdate(update, event, root->id(), kTab0Rid, browser_context);
+}
+
+// Override for chrome.automationInternal.performAction
+// This is used as a synchronization mechanism; the general flow is:
+// 1. The extension requests tree0 and tree1 (on tab 0 and tab 1 respectively)
+// 2. FakeAutomationInternalEnableTabFunction sends down the trees
+// 3. When the callback for getTree(0) fires, the extension calls doDefault() on
+//    the root node of tree0, which calls into this class's Run() method.
+// 4. In the normal case, we're in the "inner loop" (iterating over
+//    starting_node). For each value of starting_node, we do the following:
+//    a. Serialize a sequence of updates which should transform tree0 into
+//       tree1. Each of these updates is sent as a childrenChanged event,
+//       except for the last which is sent as a loadComplete event.
+//    b. state.destroy_tree0 is set to true
+//    c. state.starting_node gets incremented
+//    d. The loadComplete event triggers an assertion in the extension.
+//    e. The extension performs another doDefault() on the root node of the
+//       tree.
+//    f. This time, we send a destroy event to tab0, so that the tree can be
+//       reset.
+//    g. The extension is notified of the tree's destruction and requests the
+//       tree for tab 0 again, returning to step 2.
+// 5. When starting_node exceeds state.tree_size, we increment tree0_version if
+//    it would not exceed state.num_trees, or increment tree1_version and reset
+//    tree0_version to 0 otherwise, and reset starting_node to 0.
+//    Then we reset one or both trees as appropriate, and send down destroyed
+//    events similarly, causing the extension to re-request the tree and going
+//    back to step 2 again.
+// 6. When tree1_version has gone through all possible values, we send a blur
+//    event, signaling the extension to call chrome.test.succeed() and finish
+//    the test.
+class FakeAutomationInternalPerformActionFunction
+    : public UIThreadExtensionFunction {
+ public:
+  FakeAutomationInternalPerformActionFunction() {}
+
+  ExtensionFunction::ResponseAction Run() OVERRIDE {
+    if (state.destroy_tree0) {
+      // Step 4.f: tell the extension to destroy the tree and re-request it.
+      state.SendTreeDestroyedEvent(kTab0Rid, browser_context());
+      state.destroy_tree0 = false;
+      return RespondNow(NoArguments());
+    }
+
+    TreeSerializer* serializer0 = state.serializer0.get();
+    if (state.starting_node < state.tree_size) {
+      // As a sanity check, if the trees are not equal, assert that they are not
+      // equal before serializing changes.
+      if (state.tree0_version != state.tree1_version)
+        SendEvent(AX_EVENT_ASSERT_NOT_EQUAL, browser_context());
+
+      // Step 4.a: pretend that tree0 turned into tree1, and serialize
+      // a sequence of updates to tab 0 to match.
+      TransformTree(serializer0,
+                    state.tree1.get(),
+                    state.tree1_source.get(),
+                    browser_context());
+
+      // Step 4.b: remember that we need to tell the extension to destroy and
+      // re-request the tree on the next action.
+      state.destroy_tree0 = true;
+
+      // Step 4.c: increment starting_node.
+      state.starting_node++;
+    } else if (state.tree0_version < state.num_trees - 1) {
+      // Step 5: Increment tree0_version and reset starting_node
+      state.tree0_version++;
+      state.starting_node = 0;
+
+      // Step 5: Reset tree0 and tell the extension to destroy and re-request it
+      state.SendTreeDestroyedEvent(kTab0Rid, browser_context());
+    } else if (state.tree1_version < state.num_trees - 1) {
+      // Step 5: Increment tree1_version and reset tree0_version and
+      // starting_node
+      state.tree1_version++;
+      state.tree0_version = 0;
+      state.starting_node = 0;
+
+      // Step 5: Reset tree0 and tell the extension to destroy and re-request it
+      state.SendTreeDestroyedEvent(kTab0Rid, browser_context());
+
+      // Step 5: Reset tree1 and tell the extension to destroy and re-request it
+      state.SendTreeDestroyedEvent(kTab1Rid, browser_context());
+    } else {
+      // Step 6: Send a TEST_COMPLETE (blur) event to signal the extension to
+      // call chrome.test.succeed().
+      SendEvent(AX_EVENT_TEST_COMPLETE, browser_context());
+    }
+
+    return RespondNow(NoArguments());
+  }
+};
+
+// Factory method for use in OverrideFunction()
+ExtensionFunction* FakeAutomationInternalPerformActionFunctionFactory() {
+  return new FakeAutomationInternalPerformActionFunction();
+}
+
+IN_PROC_BROWSER_TEST_F(AutomationApiTest, GeneratedTree) {
+  ASSERT_TRUE(extensions::ExtensionFunctionDispatcher::OverrideFunction(
+      "automationInternal.enableTab",
+      FakeAutomationInternalEnableTabFunctionFactory));
+  ASSERT_TRUE(extensions::ExtensionFunctionDispatcher::OverrideFunction(
+      "automationInternal.performAction",
+      FakeAutomationInternalPerformActionFunctionFactory));
+  ASSERT_TRUE(RunExtensionSubtest("automation/tests/generated",
+                                  "generated_trees.html")) << message_;
+}
+
 }  // namespace extensions
diff --git a/chrome/browser/extensions/api/automation_internal/automation_util.cc b/chrome/browser/extensions/api/automation_internal/automation_util.cc
index 6510af02..591a86f 100644
--- a/chrome/browser/extensions/api/automation_internal/automation_util.cc
+++ b/chrome/browser/extensions/api/automation_internal/automation_util.cc
@@ -127,18 +127,21 @@ void DispatchAccessibilityEventsToAutomation(
     const std::vector<content::AXEventNotificationDetails>& details,
     content::BrowserContext* browser_context) {
   using api::automation_internal::AXEventParams;
+  using api::automation_internal::AXTreeUpdate;
 
   std::vector<content::AXEventNotificationDetails>::const_iterator iter =
       details.begin();
   for (; iter != details.end(); ++iter) {
     const content::AXEventNotificationDetails& event = *iter;
 
-    AXEventParams ax_tree_update;
-    ax_tree_update.process_id = event.process_id;
-    ax_tree_update.routing_id = event.routing_id;
-    ax_tree_update.event_type = ToString(iter->event_type);
-    ax_tree_update.target_id = event.id;
+    AXEventParams ax_event_params;
+    ax_event_params.process_id = event.process_id;
+    ax_event_params.routing_id = event.routing_id;
+    ax_event_params.event_type = ToString(iter->event_type);
+    ax_event_params.target_id = event.id;
 
+    AXTreeUpdate& ax_tree_update = ax_event_params.update;
+    ax_tree_update.node_id_to_clear = event.node_id_to_clear;
     for (size_t i = 0; i < event.nodes.size(); ++i) {
       linked_ptr<api::automation_internal::AXNodeData> out_node(
           new api::automation_internal::AXNodeData());
@@ -150,12 +153,25 @@ void DispatchAccessibilityEventsToAutomation(
     // should match the behavior from renderer -> browser and send a
     // collection of tree updates over (to the extension); see
     // |AccessibilityHostMsg_EventParams| and |AccessibilityHostMsg_Events|.
-    DispatchEventInternal(browser_context,
+    DispatchEventInternal(
+        browser_context,
         api::automation_internal::OnAccessibilityEvent::kEventName,
-        api::automation_internal::OnAccessibilityEvent::Create(ax_tree_update));
+        api::automation_internal::OnAccessibilityEvent::Create(
+            ax_event_params));
   }
 }
 
+void DispatchTreeDestroyedEventToAutomation(
+    int process_id,
+    int routing_id,
+    content::BrowserContext* browser_context) {
+  DispatchEventInternal(
+      browser_context,
+      api::automation_internal::OnAccessibilityTreeDestroyed::kEventName,
+      api::automation_internal::OnAccessibilityTreeDestroyed::Create(
+          process_id, routing_id));
+}
+
 }  // namespace automation_util
 
 }  // namespace extensions
diff --git a/chrome/browser/extensions/api/automation_internal/automation_util.h b/chrome/browser/extensions/api/automation_internal/automation_util.h
index 8b51add..981f008 100644
--- a/chrome/browser/extensions/api/automation_internal/automation_util.h
+++ b/chrome/browser/extensions/api/automation_internal/automation_util.h
@@ -29,6 +29,10 @@ void DispatchAccessibilityEventsToAutomation(
     const std::vector<content::AXEventNotificationDetails>& details,
     content::BrowserContext* browser_context);
 
+void DispatchTreeDestroyedEventToAutomation(
+    int process_id,
+    int routing_id,
+    content::BrowserContext* browser_context);
 }  // namespace automation_util
 
 }  // namespace extensions
diff --git a/chrome/browser/ui/ash/accessibility/automation_manager_ash.cc b/chrome/browser/ui/ash/accessibility/automation_manager_ash.cc
index bbf302f..455148c 100644
--- a/chrome/browser/ui/ash/accessibility/automation_manager_ash.cc
+++ b/chrome/browser/ui/ash/accessibility/automation_manager_ash.cc
@@ -103,7 +103,8 @@ void AutomationManagerAsh::SendEvent(BrowserContext* context,
   // Route this event to special process/routing ids recognized by the
   // Automation API as the desktop tree.
   // TODO(dtseng): Would idealy define these special desktop constants in idl.
-  content::AXEventNotificationDetails detail(update.nodes,
+  content::AXEventNotificationDetails detail(update.node_id_to_clear,
+                                             update.nodes,
                                              event_type,
                                              aura_obj->GetID(),
                                              0, /* process_id */
diff --git a/chrome/chrome_tests.gypi b/chrome/chrome_tests.gypi
index 10fd5a1..94be7b9 100644
--- a/chrome/chrome_tests.gypi
+++ b/chrome/chrome_tests.gypi
@@ -830,6 +830,7 @@
         '../third_party/libjingle/libjingle.gyp:peerconnection_server',
         '../third_party/safe_browsing/safe_browsing.gyp:safe_browsing',
         '../third_party/widevine/cdm/widevine_cdm.gyp:widevine_cdm_version_h',
+        '../ui/accessibility/accessibility.gyp:accessibility_test_support',
         '../ui/compositor/compositor.gyp:compositor_test_support',
         '../ui/resources/ui_resources.gyp:ui_resources',
         '../ui/web_dialogs/web_dialogs.gyp:web_dialogs_test_support',
diff --git a/chrome/common/extensions/api/automation_internal.idl b/chrome/common/extensions/api/automation_internal.idl
index 1b1d721..e95701d 100644
--- a/chrome/common/extensions/api/automation_internal.idl
+++ b/chrome/common/extensions/api/automation_internal.idl
@@ -32,6 +32,16 @@ namespace automationInternal {
     long[] childIds;
   };
 
+  dictionary AXTreeUpdate {
+    // ID of the node, if any, which should be invalidated before the new data
+    // is applied.
+    long nodeIdToClear;
+
+    // A vector of nodes to update according to the rules described in
+    // ui/accesibility/ax_tree_update.h.
+    AXNodeData[] nodes;
+  };
+
   // Data for an accessibility event and/or an atomic change to an accessibility
   // tree. See ui/accessibility/ax_tree_update.h for an extended explanation of
   // the tree update format.
@@ -48,9 +58,9 @@ namespace automationInternal {
     // The type of event that this update represents.
     DOMString eventType;
 
-    // A vector of nodes to update according to the rules described in
-    // ui/ax_tree_update.h.
-    AXNodeData[] nodes;
+    // Serialized changes to the tree structure and node data that should be
+    // applied before processing the event.
+    AXTreeUpdate update;
   };
 
   // All possible actions that can be performed on automation nodes.
@@ -99,5 +109,7 @@ namespace automationInternal {
   interface Events {
     // Fired when an accessibility event occurs
     static void onAccessibilityEvent(AXEventParams update);
+
+    static void onAccessibilityTreeDestroyed(long processID, long routingID);
   };
 };
diff --git a/chrome/renderer/resources/extensions/automation/automation_node.js b/chrome/renderer/resources/extensions/automation/automation_node.js
index 838de6e..4f8dd71 100644
--- a/chrome/renderer/resources/extensions/automation/automation_node.js
+++ b/chrome/renderer/resources/extensions/automation/automation_node.js
@@ -5,10 +5,14 @@
 var AutomationEvent = require('automationEvent').AutomationEvent;
 var automationInternal =
     require('binding').Binding.create('automationInternal').generate();
-var utils = require('utils');
 var IsInteractPermitted =
     requireNative('automationInternal').IsInteractPermitted;
 
+var lastError = require('lastError');
+var logging = requireNative('logging');
+var schema = requireNative('automationInternal').GetSchemaAdditions();
+var utils = require('utils');
+
 /**
  * A single node in the Automation tree.
  * @param {AutomationRootNodeImpl} root The root of the tree.
@@ -49,8 +53,10 @@ AutomationNodeImpl.prototype = {
 
   children: function() {
     var children = [];
-    for (var i = 0, childID; childID = this.childIds[i]; i++)
+    for (var i = 0, childID; childID = this.childIds[i]; i++) {
+      logging.CHECK(this.rootImpl.get(childID));
       children.push(this.rootImpl.get(childID));
+    }
     return children;
   },
 
@@ -130,6 +136,7 @@ AutomationNodeImpl.prototype = {
     return 'node id=' + this.id +
         ' role=' + this.role +
         ' state=' + JSON.stringify(this.state) +
+        ' parentID=' + this.parentID +
         ' childIds=' + JSON.stringify(this.childIds) +
         ' attributes=' + JSON.stringify(this.attributes);
   },
@@ -254,17 +261,108 @@ AutomationRootNodeImpl.prototype = {
   isRootNode: true,
 
   get: function(id) {
+    if (id == undefined)
+      return undefined;
+
     return this.axNodeDataCache_[id];
   },
 
-  invalidate: function(node) {
+  unserialize: function(update) {
+    var updateState = { pendingNodes: {}, newNodes: {} };
+    var oldRootId = this.id;
+
+    if (update.nodeIdToClear < 0) {
+        logging.WARNING('Bad nodeIdToClear: ' + update.nodeIdToClear);
+        lastError.set('automation',
+                      'Bad update received on automation tree',
+                      null,
+                      chrome);
+        return false;
+    } else if (update.nodeIdToClear > 0) {
+      var nodeToClear = this.axNodeDataCache_[update.nodeIdToClear];
+      if (!nodeToClear) {
+        logging.WARNING('Bad nodeIdToClear: ' + update.nodeIdToClear +
+                        ' (not in cache)');
+        lastError.set('automation',
+                      'Bad update received on automation tree',
+                      null,
+                      chrome);
+        return false;
+      }
+      if (nodeToClear === this.wrapper) {
+        this.invalidate_(nodeToClear);
+      } else {
+        var children = nodeToClear.children();
+        for (var i = 0; i < children.length; i++)
+          this.invalidate_(children[i]);
+        privates(nodeToClear).impl.childIds = []
+        updateState.pendingNodes[nodeToClear.id] = nodeToClear;
+      }
+    }
+
+    for (var i = 0; i < update.nodes.length; i++) {
+      if (!this.updateNode_(update.nodes[i], updateState))
+        return false;
+    }
+
+    if (Object.keys(updateState.pendingNodes).length > 0) {
+      logging.WARNING('Nodes left pending by the update: ' +
+                   updateState.pendingNodes.join(', '));
+      lastError.set('automation',
+                    'Bad update received on automation tree',
+                    null,
+                    chrome);
+      return false;
+    }
+    return true;
+  },
+
+  destroy: function() {
+    this.dispatchEvent(schema.EventType.destroyed);
+    this.invalidate_(this.wrapper);
+  },
+
+  onAccessibilityEvent: function(eventParams) {
+    if (!this.unserialize(eventParams.update)) {
+      logging.WARNING('unserialization failed');
+      return false;
+    }
+
+    var targetNode = this.get(eventParams.targetID);
+    if (targetNode) {
+      var targetNodeImpl = privates(targetNode).impl;
+      targetNodeImpl.dispatchEvent(eventParams.eventType);
+    } else {
+      logging.WARNING('Got ' + eventParams.eventType +
+                      ' event on unknown node: ' + eventParams.targetID +
+                      '; this: ' + this.toString());
+    }
+    return true;
+  },
+
+  toString: function() {
+    function toStringInternal(node, indent) {
+      if (!node)
+        return '';
+      var output =
+          new Array(indent).join(' ') +
+          AutomationNodeImpl.prototype.toString.call(node) +
+          '\n';
+      indent += 2;
+      for (var i = 0; i < node.children().length; i++)
+        output += toStringInternal(node.children()[i], indent);
+      return output;
+    }
+    return toStringInternal(this, 0);
+  },
+
+  invalidate_: function(node) {
     if (!node)
       return;
-
     var children = node.children();
 
     for (var i = 0, child; child = children[i]; i++)
-      this.invalidate(child);
+      this.invalidate_(child);
 
     // Retrieve the internal AutomationNodeImpl instance for this node.
     // This object is not accessible outside of bindings code, but we can access
@@ -274,97 +372,144 @@ AutomationRootNodeImpl.prototype = {
     for (var key in AutomationAttributeDefaults) {
       nodeImpl[key] = AutomationAttributeDefaults[key];
     }
+    nodeImpl.childIds = [];
     nodeImpl.loaded = false;
     nodeImpl.id = id;
-    this.axNodeDataCache_[id] = undefined;
-  },
 
-  update: function(data) {
-    var didUpdateRoot = false;
-
-    if (data.nodes.length == 0)
-      return false;
+    // TODO(aboxhall): use privates(node.root).impl instead of |this| once we
+    // have nesting trees.
+    delete this.axNodeDataCache_[id];
+  },
 
-    for (var i = 0; i < data.nodes.length; i++) {
-      var nodeData = data.nodes[i];
-      var node = this.axNodeDataCache_[nodeData.id];
-      if (!node) {
-        if (nodeData.role == 'rootWebArea' || nodeData.role == 'desktop') {
-          // |this| is an AutomationRootNodeImpl; retrieve the
-          // AutomationRootNode instance instead.
-          node = this.wrapper;
-          didUpdateRoot = true;
-        } else {
-          node = new AutomationNode(this);
-        }
+  deleteOldChildren_: function(node, newChildIds) {
+    // Create a set of child ids in |src| for fast lookup, and return false
+    // if a duplicate is found;
+    var newChildIdSet = {};
+    for (var i = 0; i < newChildIds.length; i++) {
+      var childId = newChildIds[i];
+      if (newChildIdSet[childId]) {
+        logging.WARNING('Node ' + node.id + ' has duplicate child id ' +
+                        childId);
+        lastError.set('automation',
+                      'Bad update received on automation tree',
+                      null,
+                      chrome);
+        return false;
       }
-      var nodeImpl = privates(node).impl;
-
-      // Update children.
-      var oldChildIDs = nodeImpl.childIds;
-      var newChildIDs = nodeData.childIds || [];
-      var newChildIDsHash = {};
-
-      for (var j = 0, newId; newId = newChildIDs[j]; j++) {
-        // Hash the new child ids for faster lookup.
-        newChildIDsHash[newId] = newId;
-
-        // We need to update all new children's parent id regardless.
-        var childNode = this.get(newId);
-        if (!childNode) {
-          childNode = new AutomationNode(this);
-          this.axNodeDataCache_[newId] = childNode;
-          privates(childNode).impl.id = newId;
-        }
-        privates(childNode).impl.indexInParent = j;
-        privates(childNode).impl.parentID = nodeData.id;
+      newChildIdSet[newChildIds[i]] = true;
+    }
+
+    // Delete the old children.
+    var nodeImpl = privates(node).impl;
+    var oldChildIds = nodeImpl.childIds;
+    for (var i = 0; i < oldChildIds.length;) {
+      var oldId = oldChildIds[i];
+      if (!newChildIdSet[oldId]) {
+        this.invalidate_(this.axNodeDataCache_[oldId]);
+        oldChildIds.splice(i, 1);
+      } else {
+        i++;
       }
+    }
+    nodeImpl.childIds = oldChildIds;
 
-      for (var k = 0, oldId; oldId = oldChildIDs[k]; k++) {
-        // However, we must invalidate all old child ids that are no longer
-        // children.
-        if (!newChildIDsHash[oldId]) {
-          this.invalidate(this.get(oldId));
+    return true;
+  },
+
+  createNewChildren_: function(node, newChildIds, updateState) {
+    logging.CHECK(node);
+    var success = true;
+    for (var i = 0; i < newChildIds.length; i++) {
+      var childId = newChildIds[i];
+      var childNode = this.axNodeDataCache_[childId];
+      if (childNode) {
+        if (childNode.parent() != node) {
+          var parentId = 0;
+          if (childNode.parent()) parentId = childNode.parent().id;
+          // 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.
+          logging.WARNING('Node ' + childId + ' reparented from ' +
+                          parentId + ' to ' + node.id);
+          lastError.set('automation',
+                        'Bad update received on automation tree',
+                        null,
+                        chrome);
+          success = false;
+          continue;
         }
+      } else {
+        childNode = new AutomationNode(this);
+        this.axNodeDataCache_[childId] = childNode;
+        privates(childNode).impl.id = childId;
+        updateState.pendingNodes[childNode.id] = childNode;
+        updateState.newNodes[childNode.id] = childNode;
       }
+      privates(childNode).impl.indexInParent = i;
+      privates(childNode).impl.parentID = node.id;
+    }
 
-      for (var key in AutomationAttributeDefaults) {
-        if (key in nodeData)
-          nodeImpl[key] = nodeData[key];
-        else
-          nodeImpl[key] = AutomationAttributeDefaults[key];
-      }
-      for (var attributeTypeIndex = 0;
-           attributeTypeIndex < AutomationAttributeTypes.length;
-           attributeTypeIndex++) {
-        var attributeType = AutomationAttributeTypes[attributeTypeIndex];
-        for (var attributeID in nodeData[attributeType]) {
-          nodeImpl.attributes[attributeID] =
-              nodeData[attributeType][attributeID];
-        }
+    return success;
+  },
+
+  setData_: function(node, nodeData) {
+    var nodeImpl = privates(node).impl;
+    for (var key in AutomationAttributeDefaults) {
+      if (key in nodeData)
+        nodeImpl[key] = nodeData[key];
+      else
+        nodeImpl[key] = AutomationAttributeDefaults[key];
+    }
+    for (var i = 0; i < AutomationAttributeTypes.length; i++) {
+      var attributeType = AutomationAttributeTypes[i];
+      for (var attributeName in nodeData[attributeType]) {
+        nodeImpl.attributes[attributeName] =
+          nodeData[attributeType][attributeName];
       }
-      nodeImpl.childIds = newChildIDs;
-      nodeImpl.loaded = true;
-      this.axNodeDataCache_[node.id] = node;
     }
-    var node = this.get(data.targetID);
-    if (node)
-      nodeImpl.dispatchEvent(data.eventType);
-    return true;
   },
 
-  toString: function() {
-    function toStringInternal(node, indent) {
-      if (!node)
-        return '';
-      var output =
-        new Array(indent).join(' ') + privates(node).impl.toString() + '\n';
-      indent += 2;
-      for (var i = 0; i < node.children().length; i++)
-        output += toStringInternal(node.children()[i], indent);
-      return output;
+  updateNode_: function(nodeData, updateState) {
+    var node = this.axNodeDataCache_[nodeData.id];
+    var didUpdateRoot = false;
+    if (node) {
+      delete updateState.pendingNodes[node.id];
+    } else {
+      if (nodeData.role != schema.RoleType.rootWebArea &&
+          nodeData.role != schema.RoleType.desktop) {
+        logging.WARNING(String(nodeData.id) +
+                     ' is not in the cache and not the new root.');
+        lastError.set('automation',
+                      'Bad update received on automation tree',
+                      null,
+                      chrome);
+        return false;
+      }
+      // |this| is an AutomationRootNodeImpl; retrieve the
+      // AutomationRootNode instance instead.
+      node = this.wrapper;
+      didUpdateRoot = true;
+      updateState.newNodes[this.id] = this.wrapper;
     }
-    return toStringInternal(this, 0);
+    this.setData_(node, nodeData);
+
+    // TODO(aboxhall): send onChanged event?
+    logging.CHECK(node);
+    if (!this.deleteOldChildren_(node, nodeData.childIds)) {
+      if (didUpdateRoot) {
+        this.invalidate_(this.wrapper);
+      }
+      return false;
+    }
+    var nodeImpl = privates(node).impl;
+
+    var success = this.createNewChildren_(node,
+                                          nodeData.childIds,
+                                          updateState);
+    nodeImpl.childIds = nodeData.childIds;
+    this.axNodeDataCache_[node.id] = node;
+
+    return success;
   }
 };
 
@@ -382,13 +527,16 @@ var AutomationNode = utils.expose('AutomationNode',
                                                 'makeVisible',
                                                 'setSelection',
                                                 'addEventListener',
-                                                'removeEventListener'],
+                                                'removeEventListener',
+                                                'toString'],
                                     readonly: ['isRootNode',
                                                'id',
                                                'role',
                                                'state',
                                                'location',
-                                               'attributes'] });
+                                               'attributes',
+                                               'root',
+                                               'toString'] });
 
 var AutomationRootNode = utils.expose('AutomationRootNode',
                                       AutomationRootNodeImpl,
diff --git a/chrome/renderer/resources/extensions/automation_custom_bindings.js b/chrome/renderer/resources/extensions/automation_custom_bindings.js
index 8a0fe48..4d869e9 100644
--- a/chrome/renderer/resources/extensions/automation_custom_bindings.js
+++ b/chrome/renderer/resources/extensions/automation_custom_bindings.js
@@ -12,8 +12,7 @@ var eventBindings = require('event_bindings');
 var Event = eventBindings.Event;
 var forEach = require('utils').forEach;
 var lastError = require('lastError');
-var schema =
-    requireNative('automationInternal').GetSchemaAdditions();
+var schema = requireNative('automationInternal').GetSchemaAdditions();
 
 // TODO(aboxhall): Look into using WeakMap
 var idToAutomationRootNode = {};
@@ -87,7 +86,7 @@ automation.registerCustomHook(function(bindingsAPI) {
   });
 });
 
-// Listen to the automationInternal.onaccessibilityEvent event, which is
+// Listen to the automationInternal.onAccessibilityEvent event, which is
 // essentially a proxy for the AccessibilityHostMsg_Events IPC from the
 // renderer.
 automationInternal.onAccessibilityEvent.addListener(function(data) {
@@ -102,7 +101,8 @@ automationInternal.onAccessibilityEvent.addListener(function(data) {
     targetTree = new AutomationRootNode(pid, rid);
     idToAutomationRootNode[id] = targetTree;
   }
-  privates(targetTree).impl.update(data);
+  if (!privates(targetTree).impl.onAccessibilityEvent(data))
+    return;
   var eventType = data.eventType;
   if (eventType == 'loadComplete' || eventType == 'layoutComplete') {
     // If the tree wasn't available when getTree() was called, the callback will
@@ -118,6 +118,15 @@ automationInternal.onAccessibilityEvent.addListener(function(data) {
   }
 });
 
+automationInternal.onAccessibilityTreeDestroyed.addListener(function(pid, rid) {
+  var id = createAutomationRootNodeID(pid, rid);
+  var targetTree = idToAutomationRootNode[id];
+  if (targetTree)
+    privates(targetTree).impl.destroy();
+  else
+    console.log('no targetTree to destroy');
+  delete idToAutomationRootNode[id];
+});
 exports.binding = automation.generate();
 
 // Add additional accessibility bindings not specified in the automation IDL.
diff --git a/chrome/test/data/extensions/api_test/automation/tests/generated/generated_trees.html b/chrome/test/data/extensions/api_test/automation/tests/generated/generated_trees.html
new file mode 100644
index 0000000..a786547
--- /dev/null
+++ b/chrome/test/data/extensions/api_test/automation/tests/generated/generated_trees.html
@@ -0,0 +1,6 @@
+<!--
+ * Copyright 2014 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.
+-->
+<script src="generated_trees.js"></script>
diff --git a/chrome/test/data/extensions/api_test/automation/tests/generated/generated_trees.js b/chrome/test/data/extensions/api_test/automation/tests/generated/generated_trees.js
new file mode 100644
index 0000000..8b285f8
--- /dev/null
+++ b/chrome/test/data/extensions/api_test/automation/tests/generated/generated_trees.js
@@ -0,0 +1,49 @@
+// Copyright 2014 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.
+
+var assertEq = chrome.test.assertEq;
+var assertFalse = chrome.test.assertFalse;
+var assertTrue = chrome.test.assertTrue;
+var deepEq = chrome.test.checkDeepEq;
+
+var EventType = chrome.automation.EventType;
+var assertEqualEvent = EventType.loadComplete;
+var assertNotEqualEvent = EventType.activedescendantchanged;
+var testCompleteEvent = EventType.blur;
+
+var allTests = [
+  function testDeserializeGeneratedTrees() {
+    var tree0, tree1;
+    function onTree1Retrieved(rootNode) {
+      tree1 = rootNode;
+      tree1.addEventListener(EventType.destroyed, function() {
+        chrome.automation.getTree(1, onTree1Retrieved);
+      });
+    }
+    chrome.automation.getTree(1, onTree1Retrieved);
+
+    function onTree0Retrieved(rootNode) {
+      tree0 = rootNode;
+      tree0.addEventListener(assertEqualEvent, function() {
+        assertEq(tree0.toString(), tree1.toString(),
+                 'tree0 should be equal to tree1 after loadComplete');
+        tree0.doDefault();
+      });
+      tree0.addEventListener(assertNotEqualEvent, function() {
+        assertFalse(tree0.toString() == tree1.toString(),
+                    'tree0 should not be equal to tree1');
+      });
+      tree0.addEventListener(EventType.destroyed, function() {
+        chrome.automation.getTree(0, onTree0Retrieved);
+      });
+      tree0.addEventListener(testCompleteEvent, function() {
+        chrome.test.succeed();
+      });
+      tree0.doDefault();
+    }
+    chrome.automation.getTree(0, onTree0Retrieved);
+  }
+];
+
+chrome.test.runTests(allTests);
diff --git a/chrome/test/data/extensions/api_test/automation/tests/generated/manifest.json b/chrome/test/data/extensions/api_test/automation/tests/generated/manifest.json
new file mode 100644
index 0000000..9db55ff
--- /dev/null
+++ b/chrome/test/data/extensions/api_test/automation/tests/generated/manifest.json
@@ -0,0 +1,9 @@
+{
+  "name": "chrome.automation.generated",
+  "version": "0.1",
+  "manifest_version": 2,
+  "description": "Tests for the Automation API.",
+  "automation": {
+    "interact": true
+  }
+}
diff --git a/chrome/test/data/extensions/api_test/automation/tests/tabs/sanity_check.js b/chrome/test/data/extensions/api_test/automation/tests/tabs/sanity_check.js
index 4667fc9..5d495cd 100644
--- a/chrome/test/data/extensions/api_test/automation/tests/tabs/sanity_check.js
+++ b/chrome/test/data/extensions/api_test/automation/tests/tabs/sanity_check.js
@@ -19,6 +19,7 @@ var allTests = [
       {enabled: true, focusable: true, readOnly: true},
       rootNode.state);
     var children = rootNode.children();
+    assertEq(RoleType.rootWebArea, rootNode.role);
     assertEq(1, children.length);
     var body = children[0];
     assertEq('body', body.attributes.htmlTag);
diff --git a/content/browser/renderer_host/render_view_host_impl.cc b/content/browser/renderer_host/render_view_host_impl.cc
index e14b364..75f2af2 100644
--- a/content/browser/renderer_host/render_view_host_impl.cc
+++ b/content/browser/renderer_host/render_view_host_impl.cc
@@ -1548,7 +1548,8 @@ void RenderViewHostImpl::OnAccessibilityEvents(
     std::vector<AXEventNotificationDetails> details;
     for (unsigned int i = 0; i < params.size(); ++i) {
       const AccessibilityHostMsg_EventParams& param = params[i];
-      AXEventNotificationDetails detail(param.update.nodes,
+      AXEventNotificationDetails detail(param.update.node_id_to_clear,
+                                        param.update.nodes,
                                         param.event_type,
                                         param.id,
                                         GetProcess()->GetID(),
diff --git a/content/public/browser/ax_event_notification_details.cc b/content/public/browser/ax_event_notification_details.cc
index 87ff4df..dfebb87 100644
--- a/content/public/browser/ax_event_notification_details.cc
+++ b/content/public/browser/ax_event_notification_details.cc
@@ -7,16 +7,19 @@
 namespace content {
 
 AXEventNotificationDetails::AXEventNotificationDetails(
+    int node_id_to_clear,
     const std::vector<ui::AXNodeData>& nodes,
     ui::AXEvent event_type,
     int id,
     int process_id,
     int routing_id)
-    : nodes(nodes),
+    : node_id_to_clear(node_id_to_clear),
+      nodes(nodes),
       event_type(event_type),
       id(id),
       process_id(process_id),
-      routing_id(routing_id) {}
+      routing_id(routing_id) {
+}
 
 AXEventNotificationDetails::~AXEventNotificationDetails() {}
 
diff --git a/content/public/browser/ax_event_notification_details.h b/content/public/browser/ax_event_notification_details.h
index 3065e59d..0f4d8dc 100644
--- a/content/public/browser/ax_event_notification_details.h
+++ b/content/public/browser/ax_event_notification_details.h
@@ -17,7 +17,8 @@ namespace content {
 // |WebContentsObserver::AccessibilityEventReceived| method.
 struct CONTENT_EXPORT AXEventNotificationDetails {
  public:
-  AXEventNotificationDetails(const std::vector<ui::AXNodeData>& nodes,
+  AXEventNotificationDetails(int node_id_to_clear,
+                             const std::vector<ui::AXNodeData>& nodes,
                              ui::AXEvent event_type,
                              int id,
                              int process_id,
@@ -25,6 +26,7 @@ struct CONTENT_EXPORT AXEventNotificationDetails {
 
   ~AXEventNotificationDetails();
 
+  int node_id_to_clear;
   std::vector<ui::AXNodeData> nodes;
   ui::AXEvent event_type;
   int id;
diff --git a/ui/accessibility/BUILD.gn b/ui/accessibility/BUILD.gn
index 66a04da..e1c61d2 100644
--- a/ui/accessibility/BUILD.gn
+++ b/ui/accessibility/BUILD.gn
@@ -37,6 +37,17 @@ component("accessibility") {
   ]
 }
 
+source_set("accessibility_test_support") {
+  sources = [
+    "tree_generator.cc",
+    "tree_generator.h"
+  ]
+
+  deps = [
+    ":accessibility"
+  ]
+}
+
 test("accessibility_unittests") {
   sources = [
     "ax_generated_tree_unittest.cc",
@@ -46,6 +57,7 @@ test("accessibility_unittests") {
 
   deps = [
     ":accessibility",
+    ":accessibility_test_support",
     "//base",
     "//base/test:run_all_unittests",
     "//testing/gtest",
diff --git a/ui/accessibility/accessibility.gyp b/ui/accessibility/accessibility.gyp
index bdc4212..6c05a39 100644
--- a/ui/accessibility/accessibility.gyp
+++ b/ui/accessibility/accessibility.gyp
@@ -46,6 +46,18 @@
       ]
     },
     {
+      'target_name': 'accessibility_test_support',
+      'type': 'static_library',
+      'dependencies': [
+        '../../base/base.gyp:base',
+        'accessibility'
+      ],
+      'sources': [
+        'tree_generator.cc',
+        'tree_generator.h'
+      ]
+    },
+    {
       'target_name': 'accessibility_unittests',
       'type': 'executable',
       'dependencies': [
@@ -55,6 +67,7 @@
         '../gfx/gfx.gyp:gfx',
         '../gfx/gfx.gyp:gfx_geometry',
         'accessibility',
+        'accessibility_test_support',
         'ax_gen',
       ],
       'sources': [
diff --git a/ui/accessibility/ax_enums.idl b/ui/accessibility/ax_enums.idl
index ef3b5e6..adab1aa 100644
--- a/ui/accessibility/ax_enums.idl
+++ b/ui/accessibility/ax_enums.idl
@@ -16,6 +16,7 @@
     blur,
     checked_state_changed,
     children_changed,
+    destroyed,
     focus,
     hide,
     hover,
diff --git a/ui/accessibility/ax_generated_tree_unittest.cc b/ui/accessibility/ax_generated_tree_unittest.cc
index 835200c..3845886 100644
--- a/ui/accessibility/ax_generated_tree_unittest.cc
+++ b/ui/accessibility/ax_generated_tree_unittest.cc
@@ -9,6 +9,7 @@
 #include "ui/accessibility/ax_serializable_tree.h"
 #include "ui/accessibility/ax_tree.h"
 #include "ui/accessibility/ax_tree_serializer.h"
+#include "ui/accessibility/tree_generator.h"
 
 namespace ui {
 namespace {
@@ -46,93 +47,6 @@ std::string TreeToString(const AXTree& tree) {
 
 }  // anonymous namespace
 
-// A class to create all possible trees with <n> nodes and the ids [1...n].
-//
-// There are two parts to the algorithm:
-//
-// The tree structure is formed as follows: without loss of generality,
-// the first node becomes the root and the second node becomes its
-// child. Thereafter, choose every possible parent for every other node.
-//
-// So for node i in (3...n), there are (i - 1) possible choices for its
-// parent, for a total of (n-1)! (n minus 1 factorial) possible trees.
-//
-// The second part is the assignment of ids to the nodes in the tree.
-// There are exactly n! (n factorial) permutations of the sequence 1...n,
-// and each of these is assigned to every node in every possible tree.
-//
-// The total number of trees returned for a given <n>, then, is
-// n! * (n-1)!
-//
-// n = 2: 2 trees
-// n = 3: 12 trees
-// n = 4: 144 trees
-// n = 5: 2880 trees
-//
-// This grows really fast! Luckily it's very unlikely that there'd be
-// bugs that affect trees with >4 nodes that wouldn't affect a smaller tree
-// too.
-class TreeGenerator {
- public:
-  TreeGenerator(int node_count)
-      : node_count_(node_count),
-        unique_tree_count_(1) {
-    // (n-1)! for the possible trees.
-    for (int i = 2; i < node_count_; i++)
-      unique_tree_count_ *= i;
-    // n! for the permutations of ids.
-    for (int i = 2; i <= node_count_; i++)
-      unique_tree_count_ *= i;
-  }
-
-  int UniqueTreeCount() {
-    return unique_tree_count_;
-  }
-
-  void BuildUniqueTree(int tree_index, AXTree* out_tree) {
-    std::vector<int> indices;
-    std::vector<int> permuted;
-    CHECK(tree_index <= unique_tree_count_);
-
-    // Use the first few bits of |tree_index| to permute
-    // the indices.
-    for (int i = 0; i < node_count_; i++)
-      indices.push_back(i + 1);
-    for (int i = 0; i < node_count_; i++) {
-      int p = (node_count_ - i);
-      int index = tree_index % p;
-      tree_index /= p;
-      permuted.push_back(indices[index]);
-      indices.erase(indices.begin() + index);
-    }
-
-    // Build an AXTreeUpdate. The first two nodes of the tree always
-    // go in the same place.
-    AXTreeUpdate update;
-    update.nodes.resize(node_count_);
-    update.nodes[0].id = permuted[0];
-    update.nodes[0].role = AX_ROLE_ROOT_WEB_AREA;
-    update.nodes[0].child_ids.push_back(permuted[1]);
-    update.nodes[1].id = permuted[1];
-
-    // The remaining nodes are assigned based on their parent
-    // selected from the next bits from |tree_index|.
-    for (int i = 2; i < node_count_; i++) {
-      update.nodes[i].id = permuted[i];
-      int parent_index = (tree_index % i);
-      tree_index /= i;
-      update.nodes[parent_index].child_ids.push_back(permuted[i]);
-    }
-
-    // Unserialize the tree update into the destination tree.
-    CHECK(out_tree->Unserialize(update));
-  }
-
- private:
-  int node_count_;
-  int unique_tree_count_;
-};
-
 // Test the TreeGenerator class by building all possible trees with
 // 3 nodes and the ids [1...3].
 TEST(AXGeneratedTreeTest, TestTreeGenerator) {
diff --git a/ui/accessibility/ax_tree.cc b/ui/accessibility/ax_tree.cc
index 359c8e2..ecfbae8 100644
--- a/ui/accessibility/ax_tree.cc
+++ b/ui/accessibility/ax_tree.cc
@@ -153,7 +153,7 @@ bool AXTree::UpdateNode(
   // of the tree is being swapped, or we're out of sync with the source
   // and this is a serious error.
   AXNode* node = GetFromId(src.id);
-  AXNode* new_node = NULL;
+  AXNode* new_root = NULL;
   if (node) {
     update_state->pending_nodes.erase(node);
     node->SetData(src);
@@ -163,8 +163,8 @@ bool AXTree::UpdateNode(
           "%d is not in the tree and not the new root", src.id);
       return false;
     }
-    new_node = CreateNode(NULL, src.id, 0);
-    node = new_node;
+    new_root = CreateNode(NULL, src.id, 0);
+    node = new_root;
     update_state->new_nodes.insert(node);
     node->SetData(src);
   }
@@ -175,8 +175,8 @@ bool AXTree::UpdateNode(
   // First, delete nodes that used to be children of this node but aren't
   // anymore.
   if (!DeleteOldChildren(node, src.child_ids)) {
-    if (new_node)
-      DestroyNodeAndSubtree(new_node);
+    if (new_root)
+      DestroyNodeAndSubtree(new_root);
     return false;
   }
 
diff --git a/ui/accessibility/tree_generator.cc b/ui/accessibility/tree_generator.cc
new file mode 100644
index 0000000..8eb4502
--- /dev/null
+++ b/ui/accessibility/tree_generator.cc
@@ -0,0 +1,67 @@
+// Copyright 2014 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 "ui/accessibility/tree_generator.h"
+
+#include "ui/accessibility/ax_serializable_tree.h"
+#include "ui/accessibility/ax_tree.h"
+
+namespace ui {
+
+TreeGenerator::TreeGenerator(int node_count)
+    : node_count_(node_count), unique_tree_count_(1) {
+  // (n-1)! for the possible trees.
+  for (int i = 2; i < node_count_; i++)
+    unique_tree_count_ *= i;
+  // n! for the permutations of ids.
+  for (int i = 2; i <= node_count_; i++)
+    unique_tree_count_ *= i;
+};
+
+int TreeGenerator::UniqueTreeCount() const {
+  return unique_tree_count_;
+};
+
+void TreeGenerator::BuildUniqueTree(int tree_index, AXTree* out_tree) const {
+  std::vector<int> indices;
+  std::vector<int> permuted;
+  CHECK(tree_index <= unique_tree_count_);
+
+  // Use the first few bits of |tree_index| to permute the indices.
+  for (int i = 0; i < node_count_; i++)
+    indices.push_back(i + 1);
+  for (int i = 0; i < node_count_; i++) {
+    int p = (node_count_ - i);
+    int index = tree_index % p;
+    tree_index /= p;
+    permuted.push_back(indices[index]);
+    indices.erase(indices.begin() + index);
+  }
+
+  // Build an AXTreeUpdate. The first two nodes of the tree always
+  // go in the same place.
+  AXTreeUpdate update;
+  update.nodes.resize(node_count_);
+  update.nodes[0].id = permuted[0];
+  update.nodes[0].role = AX_ROLE_ROOT_WEB_AREA;
+  update.nodes[0].state = AX_STATE_NONE;
+  update.nodes[0].child_ids.push_back(permuted[1]);
+  update.nodes[1].id = permuted[1];
+  update.nodes[1].state = AX_STATE_NONE;
+
+  // The remaining nodes are assigned based on their parent
+  // selected from the next bits from |tree_index|.
+  for (int i = 2; i < node_count_; i++) {
+    update.nodes[i].id = permuted[i];
+    update.nodes[i].state = AX_STATE_NONE;
+    int parent_index = (tree_index % i);
+    tree_index /= i;
+    update.nodes[parent_index].child_ids.push_back(permuted[i]);
+  }
+
+  // Unserialize the tree update into the destination tree.
+  CHECK(out_tree->Unserialize(update)) << out_tree->error();
+};
+
+}  // namespace ui
diff --git a/ui/accessibility/tree_generator.h b/ui/accessibility/tree_generator.h
new file mode 100644
index 0000000..3041d92
--- /dev/null
+++ b/ui/accessibility/tree_generator.h
@@ -0,0 +1,48 @@
+// Copyright 2014 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.
+
+namespace ui {
+
+class AXTree;
+
+// A class to create all possible trees with <n> nodes and the ids [1...n].
+//
+// There are two parts to the algorithm:
+//
+// The tree structure is formed as follows: without loss of generality,
+// the first node becomes the root and the second node becomes its
+// child. Thereafter, choose every possible parent for every other node.
+//
+// So for node i in (3...n), there are (i - 1) possible choices for its
+// parent, for a total of (n-1)! (n minus 1 factorial) possible trees.
+//
+// The second part is the assignment of ids to the nodes in the tree.
+// There are exactly n! (n factorial) permutations of the sequence 1...n,
+// and each of these is assigned to every node in every possible tree.
+//
+// The total number of trees returned for a given <n>, then, is
+// n! * (n-1)!
+//
+// n = 2: 2 trees
+// n = 3: 12 trees
+// n = 4: 144 trees
+// n = 5: 2880 trees
+//
+// This grows really fast! Luckily it's very unlikely that there'd be
+// bugs that affect trees with >4 nodes that wouldn't affect a smaller tree
+// too.
+class TreeGenerator {
+ public:
+  TreeGenerator(int node_count);
+
+  int UniqueTreeCount() const;
+
+  void BuildUniqueTree(int tree_index, AXTree* out_tree) const;
+
+ private:
+  int node_count_;
+  int unique_tree_count_;
+};
+
+}  // namespace ui