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 "ui/accessibility/tree_generator.h"
6
7 #include "ui/accessibility/ax_serializable_tree.h"
8 #include "ui/accessibility/ax_tree.h"
9
10 namespace ui {
11
UniqueTreeCountForNodeCount(int node_count,bool permutations)12 static int UniqueTreeCountForNodeCount(int node_count,
13 bool permutations) {
14 int unique_tree_count = 1;
15
16 // (n-1)! for the possible trees.
17 for (int i = 2; i < node_count; ++i)
18 unique_tree_count *= i;
19
20 // n! for the permutations of ids.
21 if (permutations)
22 unique_tree_count = unique_tree_count * unique_tree_count * node_count;
23
24 return unique_tree_count;
25 }
26
TreeGenerator(int max_node_count,bool permutations)27 TreeGenerator::TreeGenerator(int max_node_count, bool permutations)
28 : max_node_count_(max_node_count),
29 permutations_(permutations),
30 total_unique_tree_count_(0) {
31 unique_tree_count_by_size_.push_back(0);
32 for (int i = 1; i <= max_node_count; ++i) {
33 int unique_tree_count = UniqueTreeCountForNodeCount(i, permutations);
34 unique_tree_count_by_size_.push_back(unique_tree_count);
35 total_unique_tree_count_ += unique_tree_count;
36 }
37 }
38
~TreeGenerator()39 TreeGenerator::~TreeGenerator() {
40 }
41
UniqueTreeCount() const42 int TreeGenerator::UniqueTreeCount() const {
43 return total_unique_tree_count_;
44 }
45
BuildUniqueTree(int tree_index,AXTree * out_tree) const46 void TreeGenerator::BuildUniqueTree(int tree_index, AXTree* out_tree) const {
47 AXTreeUpdate update;
48 BuildUniqueTreeUpdate(tree_index, &update);
49 CHECK(out_tree->Unserialize(update)) << out_tree->error();
50 }
51
IgnoredPermutationCountPerUniqueTree(int tree_index) const52 int TreeGenerator::IgnoredPermutationCountPerUniqueTree(int tree_index) const {
53 int unique_tree_count_so_far = 0;
54 for (int node_count = 1; node_count <= max_node_count_; ++node_count) {
55 int unique_tree_count = unique_tree_count_by_size_[node_count];
56 if (tree_index - unique_tree_count_so_far < unique_tree_count) {
57 // Each node other than the root can be either ignored or not,
58 // so return 2 ^ (node_count - 1)
59 return 1 << (node_count - 1);
60 }
61 unique_tree_count_so_far += unique_tree_count;
62 }
63
64 NOTREACHED();
65 return 0;
66 }
67
BuildUniqueTreeWithIgnoredNodes(int tree_index,int ignored_index,AXTree * out_tree) const68 void TreeGenerator::BuildUniqueTreeWithIgnoredNodes(int tree_index,
69 int ignored_index,
70 AXTree* out_tree) const {
71 AXTreeUpdate update;
72 BuildUniqueTreeUpdate(tree_index, &update);
73
74 int node_count = int{update.nodes.size()};
75 CHECK_GE(ignored_index, 0);
76 CHECK_LT(ignored_index, 1 << (node_count - 1));
77
78 for (int i = 0; i < node_count - 1; i++) {
79 if (ignored_index & (1 << i))
80 update.nodes[i + 1].AddState(ax::mojom::State::kIgnored);
81 }
82 CHECK(out_tree->Unserialize(update)) << out_tree->error();
83 }
84
BuildUniqueTreeUpdate(int tree_index,AXTreeUpdate * out_update) const85 void TreeGenerator::BuildUniqueTreeUpdate(int tree_index,
86 AXTreeUpdate* out_update) const {
87 CHECK_LT(tree_index, total_unique_tree_count_);
88
89 int unique_tree_count_so_far = 0;
90 for (int node_count = 1; node_count <= max_node_count_; ++node_count) {
91 int unique_tree_count = unique_tree_count_by_size_[node_count];
92 if (tree_index - unique_tree_count_so_far < unique_tree_count) {
93 BuildUniqueTreeUpdateWithSize(
94 node_count, tree_index - unique_tree_count_so_far, out_update);
95 return;
96 }
97 unique_tree_count_so_far += unique_tree_count;
98 }
99 }
100
BuildUniqueTreeUpdateWithSize(int node_count,int tree_index,AXTreeUpdate * out_update) const101 void TreeGenerator::BuildUniqueTreeUpdateWithSize(
102 int node_count,
103 int tree_index,
104 AXTreeUpdate* out_update) const {
105 std::vector<int> indices;
106 std::vector<int> permuted;
107 int unique_tree_count = unique_tree_count_by_size_[node_count];
108 CHECK_LT(tree_index, unique_tree_count);
109
110 if (permutations_) {
111 // Use the first few bits of |tree_index| to permute the indices.
112 for (int i = 0; i < node_count; ++i)
113 indices.push_back(i + 1);
114 for (int i = 0; i < node_count; ++i) {
115 int p = (node_count - i);
116 int index = tree_index % p;
117 tree_index /= p;
118 permuted.push_back(indices[index]);
119 indices.erase(indices.begin() + index);
120 }
121 } else {
122 for (int i = 0; i < node_count; ++i)
123 permuted.push_back(i + 1);
124 }
125
126 // Build an AXTreeUpdate. The first two nodes of the tree always
127 // go in the same place.
128 out_update->root_id = permuted[0];
129 out_update->nodes.resize(node_count);
130 out_update->nodes[0].id = permuted[0];
131 if (node_count > 1) {
132 out_update->nodes[0].child_ids.push_back(permuted[1]);
133 out_update->nodes[1].id = permuted[1];
134 }
135
136 // The remaining nodes are assigned based on their parent
137 // selected from the next bits from |tree_index|.
138 for (int i = 2; i < node_count; ++i) {
139 out_update->nodes[i].id = permuted[i];
140 int parent_index = (tree_index % i);
141 tree_index /= i;
142 out_update->nodes[parent_index].child_ids.push_back(permuted[i]);
143 }
144 }
145
146 } // namespace ui
147