ui/accessibility/ax_generated_tree_unittest.cc

   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 #include "ui/accessibility/tree_generator.h"
  13
  14 namespace ui {
  15 namespace {
  16
  17 // A function to turn a tree into a string, capturing only the node ids
  18 // and their relationship to one another.
  19 //
  20 // The string format is kind of like an S-expression, with each expression
  21 // being either a node id, or a node id followed by a subexpression
  22 // representing its children.
  23 //
  24 // Examples:
  25 //
  26 // (1) is a tree with a single node with id 1.
  27 // (1 (2 3)) is a tree with 1 as the root, and 2 and 3 as its children.
  28 // (1 (2 (3))) has 1 as the root, 2 as its child, and then 3 as the child of 2.
  29 void TreeToStringHelper(const AXNode* node, std::string* out_result) {
  30   *out_result += base::IntToString(node->id());
  31   if (node->child_count() != 0) {
  32     *out_result += " (";
  33     for (int i = 0; i < node->child_count(); ++i) {
  34       if (i != 0)
  35         *out_result += " ";
  36       TreeToStringHelper(node->ChildAtIndex(i), out_result);
  37     }
  38     *out_result += ")";
  39   }
  40 }
  41
  42 std::string TreeToString(const AXTree& tree) {
  43   std::string result;
  44   TreeToStringHelper(tree.root(), &result);
  45   return "(" + result + ")";
  46 }
  47
  48 }  // anonymous namespace
  49
  50 // Test the TreeGenerator class by building all possible trees with
  51 // 3 nodes and the ids [1...3].
  52 TEST(AXGeneratedTreeTest, TestTreeGenerator) {
  53   int tree_size = 3;
  54   TreeGenerator generator(tree_size);
  55   const char* EXPECTED_TREES[] = {
  56     "(1 (2 3))",
  57     "(2 (1 3))",
  58     "(3 (1 2))",
  59     "(1 (3 2))",
  60     "(2 (3 1))",
  61     "(3 (2 1))",
  62     "(1 (2 (3)))",
  63     "(2 (1 (3)))",
  64     "(3 (1 (2)))",
  65     "(1 (3 (2)))",
  66     "(2 (3 (1)))",
  67     "(3 (2 (1)))",
  68   };
  69
  70   int n = generator.UniqueTreeCount();
  71   ASSERT_EQ(static_cast<int>(arraysize(EXPECTED_TREES)), n);
  72
  73   for (int i = 0; i < n; i++) {
  74     AXTree tree;
  75     generator.BuildUniqueTree(i, &tree);
  76     std::string str = TreeToString(tree);
  77     EXPECT_EQ(EXPECTED_TREES[i], str);
  78   }
  79 }
  80
  81 // Test mutating every possible tree with <n> nodes to every other possible
  82 // tree with <n> nodes, where <n> is 4 in release mode and 3 in debug mode
  83 // (for speed). For each possible combination of trees, we also vary which
  84 // node we serialize first.
  85 //
  86 // For every possible scenario, we check that the AXTreeUpdate is valid,
  87 // that the destination tree can unserialize it and create a valid tree,
  88 // and that after updating all nodes the resulting tree now matches the
  89 // intended tree.
  90 TEST(AXGeneratedTreeTest, SerializeGeneratedTrees) {
  91   // Do a more exhaustive test in release mode. If you're modifying
  92   // the algorithm you may want to try even larger tree sizes if you
  93   // can afford the time.
  94 #ifdef NDEBUG
  95   int tree_size = 4;
  96 #else
  97   LOG(WARNING) << "Debug build, only testing trees with 3 nodes and not 4.";
  98   int tree_size = 3;
  99 #endif
 100
 101   TreeGenerator generator(tree_size);
 102   int n = generator.UniqueTreeCount();
 103
 104   for (int i = 0; i < n; i++) {
 105     // Build the first tree, tree0.
 106     AXSerializableTree tree0;
 107     generator.BuildUniqueTree(i, &tree0);
 108     SCOPED_TRACE("tree0 is " + TreeToString(tree0));
 109
 110     for (int j = 0; j < n; j++) {
 111       // Build the second tree, tree1.
 112       AXSerializableTree tree1;
 113       generator.BuildUniqueTree(j, &tree1);
 114       SCOPED_TRACE("tree1 is " + TreeToString(tree0));
 115
 116       // Now iterate over which node to update first, |k|.
 117       for (int k = 0; k < tree_size; k++) {
 118         SCOPED_TRACE("i=" + base::IntToString(i) +
 119                      " j=" + base::IntToString(j) +
 120                      " k=" + base::IntToString(k));
 121
 122         // Start by serializing tree0 and unserializing it into a new
 123         // empty tree |dst_tree|.
 124         scoped_ptr<AXTreeSource<const AXNode*> > tree0_source(
 125             tree0.CreateTreeSource());
 126         AXTreeSerializer<const AXNode*> serializer(tree0_source.get());
 127         AXTreeUpdate update0;
 128         serializer.SerializeChanges(tree0.root(), &update0);
 129
 130         AXTree dst_tree;
 131         ASSERT_TRUE(dst_tree.Unserialize(update0));
 132
 133         // At this point, |dst_tree| should now be identical to |tree0|.
 134         EXPECT_EQ(TreeToString(tree0), TreeToString(dst_tree));
 135
 136         // Next, pretend that tree0 turned into tree1, and serialize
 137         // a sequence of updates to |dst_tree| to match.
 138         scoped_ptr<AXTreeSource<const AXNode*> > tree1_source(
 139             tree1.CreateTreeSource());
 140         serializer.ChangeTreeSourceForTesting(tree1_source.get());
 141
 142         for (int k_index = 0; k_index < tree_size; ++k_index) {
 143           int id = 1 + (k + k_index) % tree_size;
 144           AXTreeUpdate update;
 145           serializer.SerializeChanges(tree1.GetFromId(id), &update);
 146           ASSERT_TRUE(dst_tree.Unserialize(update));
 147         }
 148
 149         // After the sequence of updates, |dst_tree| should now be
 150         // identical to |tree1|.
 151         EXPECT_EQ(TreeToString(tree1), TreeToString(dst_tree));
 152       }
 153     }
 154   }
 155 }
 156
 157 }  // namespace ui