Home | History | Annotate | Download | only in accessibility 
      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.GetRoot(), &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.GetRoot(), &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
    158