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

7 files changed, 147 insertions, 92 deletions

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