1 // Copyright 2014 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "base/memory/scoped_ptr.h" 6 #include "base/strings/string_number_conversions.h" 7 #include "testing/gtest/include/gtest/gtest.h" 8 #include "ui/accessibility/ax_node.h" 9 #include "ui/accessibility/ax_serializable_tree.h" 10 #include "ui/accessibility/ax_tree.h" 11 #include "ui/accessibility/ax_tree_serializer.h" 12 13 namespace ui { 14 namespace { 15 16 // A function to turn a tree into a string, capturing only the node ids 17 // and their relationship to one another. 18 // 19 // The string format is kind of like an S-expression, with each expression 20 // being either a node id, or a node id followed by a subexpression 21 // representing its children. 22 // 23 // Examples: 24 // 25 // (1) is a tree with a single node with id 1. 26 // (1 (2 3)) is a tree with 1 as the root, and 2 and 3 as its children. 27 // (1 (2 (3))) has 1 as the root, 2 as its child, and then 3 as the child of 2. 28 void TreeToStringHelper(const AXNode* node, std::string* out_result) { 29 *out_result += base::IntToString(node->id()); 30 if (node->child_count() != 0) { 31 *out_result += " ("; 32 for (int i = 0; i < node->child_count(); ++i) { 33 if (i != 0) 34 *out_result += " "; 35 TreeToStringHelper(node->ChildAtIndex(i), out_result); 36 } 37 *out_result += ")"; 38 } 39 } 40 41 std::string TreeToString(const AXTree& tree) { 42 std::string result; 43 TreeToStringHelper(tree.GetRoot(), &result); 44 return "(" + result + ")"; 45 } 46 47 } // anonymous namespace 48 49 // A class to create all possible trees with <n> nodes and the ids [1...n]. 50 // 51 // There are two parts to the algorithm: 52 // 53 // The tree structure is formed as follows: without loss of generality, 54 // the first node becomes the root and the second node becomes its 55 // child. Thereafter, choose every possible parent for every other node. 56 // 57 // So for node i in (3...n), there are (i - 1) possible choices for its 58 // parent, for a total of (n-1)! (n minus 1 factorial) possible trees. 59 // 60 // The second part is the assignment of ids to the nodes in the tree. 61 // There are exactly n! (n factorial) permutations of the sequence 1...n, 62 // and each of these is assigned to every node in every possible tree. 63 // 64 // The total number of trees returned for a given <n>, then, is 65 // n! * (n-1)! 66 // 67 // n = 2: 2 trees 68 // n = 3: 12 trees 69 // n = 4: 144 trees 70 // n = 5: 2880 trees 71 // 72 // This grows really fast! Luckily it's very unlikely that there'd be 73 // bugs that affect trees with >4 nodes that wouldn't affect a smaller tree 74 // too. 75 class TreeGenerator { 76 public: 77 TreeGenerator(int node_count) 78 : node_count_(node_count), 79 unique_tree_count_(1) { 80 // (n-1)! for the possible trees. 81 for (int i = 2; i < node_count_; i++) 82 unique_tree_count_ *= i; 83 // n! for the permutations of ids. 84 for (int i = 2; i <= node_count_; i++) 85 unique_tree_count_ *= i; 86 } 87 88 int UniqueTreeCount() { 89 return unique_tree_count_; 90 } 91 92 void BuildUniqueTree(int tree_index, AXTree* out_tree) { 93 std::vector<int> indices; 94 std::vector<int> permuted; 95 CHECK(tree_index <= unique_tree_count_); 96 97 // Use the first few bits of |tree_index| to permute 98 // the indices. 99 for (int i = 0; i < node_count_; i++) 100 indices.push_back(i + 1); 101 for (int i = 0; i < node_count_; i++) { 102 int p = (node_count_ - i); 103 int index = tree_index % p; 104 tree_index /= p; 105 permuted.push_back(indices[index]); 106 indices.erase(indices.begin() + index); 107 } 108 109 // Build an AXTreeUpdate. The first two nodes of the tree always 110 // go in the same place. 111 AXTreeUpdate update; 112 update.nodes.resize(node_count_); 113 update.nodes[0].id = permuted[0]; 114 update.nodes[0].role = AX_ROLE_ROOT_WEB_AREA; 115 update.nodes[0].child_ids.push_back(permuted[1]); 116 update.nodes[1].id = permuted[1]; 117 118 // The remaining nodes are assigned based on their parent 119 // selected from the next bits from |tree_index|. 120 for (int i = 2; i < node_count_; i++) { 121 update.nodes[i].id = permuted[i]; 122 int parent_index = (tree_index % i); 123 tree_index /= i; 124 update.nodes[parent_index].child_ids.push_back(permuted[i]); 125 } 126 127 // Unserialize the tree update into the destination tree. 128 CHECK(out_tree->Unserialize(update)); 129 } 130 131 private: 132 int node_count_; 133 int unique_tree_count_; 134 }; 135 136 // Test the TreeGenerator class by building all possible trees with 137 // 3 nodes and the ids [1...3]. 138 TEST(AXGeneratedTreeTest, TestTreeGenerator) { 139 int tree_size = 3; 140 TreeGenerator generator(tree_size); 141 const char* EXPECTED_TREES[] = { 142 "(1 (2 3))", 143 "(2 (1 3))", 144 "(3 (1 2))", 145 "(1 (3 2))", 146 "(2 (3 1))", 147 "(3 (2 1))", 148 "(1 (2 (3)))", 149 "(2 (1 (3)))", 150 "(3 (1 (2)))", 151 "(1 (3 (2)))", 152 "(2 (3 (1)))", 153 "(3 (2 (1)))", 154 }; 155 156 int n = generator.UniqueTreeCount(); 157 ASSERT_EQ(static_cast<int>(arraysize(EXPECTED_TREES)), n); 158 159 for (int i = 0; i < n; i++) { 160 AXTree tree; 161 generator.BuildUniqueTree(i, &tree); 162 std::string str = TreeToString(tree); 163 EXPECT_EQ(EXPECTED_TREES[i], str); 164 } 165 } 166 167 // Test mutating every possible tree with <n> nodes to every other possible 168 // tree with <n> nodes, where <n> is 4 in release mode and 3 in debug mode 169 // (for speed). For each possible combination of trees, we also vary which 170 // node we serialize first. 171 // 172 // For every possible scenario, we check that the AXTreeUpdate is valid, 173 // that the destination tree can unserialize it and create a valid tree, 174 // and that after updating all nodes the resulting tree now matches the 175 // intended tree. 176 TEST(AXGeneratedTreeTest, SerializeGeneratedTrees) { 177 // Do a more exhaustive test in release mode. If you're modifying 178 // the algorithm you may want to try even larger tree sizes if you 179 // can afford the time. 180 #ifdef NDEBUG 181 int tree_size = 4; 182 #else 183 LOG(WARNING) << "Debug build, only testing trees with 3 nodes and not 4."; 184 int tree_size = 3; 185 #endif 186 187 TreeGenerator generator(tree_size); 188 int n = generator.UniqueTreeCount(); 189 190 for (int i = 0; i < n; i++) { 191 // Build the first tree, tree0. 192 AXSerializableTree tree0; 193 generator.BuildUniqueTree(i, &tree0); 194 SCOPED_TRACE("tree0 is " + TreeToString(tree0)); 195 196 for (int j = 0; j < n; j++) { 197 // Build the second tree, tree1. 198 AXSerializableTree tree1; 199 generator.BuildUniqueTree(j, &tree1); 200 SCOPED_TRACE("tree1 is " + TreeToString(tree0)); 201 202 // Now iterate over which node to update first, |k|. 203 for (int k = 0; k < tree_size; k++) { 204 SCOPED_TRACE("i=" + base::IntToString(i) + 205 " j=" + base::IntToString(j) + 206 " k=" + base::IntToString(k)); 207 208 // Start by serializing tree0 and unserializing it into a new 209 // empty tree |dst_tree|. 210 scoped_ptr<AXTreeSource<const AXNode*> > tree0_source( 211 tree0.CreateTreeSource()); 212 AXTreeSerializer<const AXNode*> serializer(tree0_source.get()); 213 AXTreeUpdate update0; 214 serializer.SerializeChanges(tree0.GetRoot(), &update0); 215 216 AXTree dst_tree; 217 ASSERT_TRUE(dst_tree.Unserialize(update0)); 218 219 // At this point, |dst_tree| should now be identical to |tree0|. 220 EXPECT_EQ(TreeToString(tree0), TreeToString(dst_tree)); 221 222 // Next, pretend that tree0 turned into tree1, and serialize 223 // a sequence of updates to |dst_tree| to match. 224 scoped_ptr<AXTreeSource<const AXNode*> > tree1_source( 225 tree1.CreateTreeSource()); 226 serializer.ChangeTreeSourceForTesting(tree1_source.get()); 227 228 for (int k_index = 0; k_index < tree_size; ++k_index) { 229 int id = 1 + (k + k_index) % tree_size; 230 AXTreeUpdate update; 231 serializer.SerializeChanges(tree1.GetFromId(id), &update); 232 ASSERT_TRUE(dst_tree.Unserialize(update)); 233 } 234 235 // After the sequence of updates, |dst_tree| should now be 236 // identical to |tree1|. 237 EXPECT_EQ(TreeToString(tree1), TreeToString(dst_tree)); 238 } 239 } 240 } 241 } 242 243 } // namespace ui 244