tree_generator.cc 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155
  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. #include "ui/accessibility/tree_generator.h"
  5. #include "ui/accessibility/ax_serializable_tree.h"
  6. #include "ui/accessibility/ax_tree.h"
  7. #include "ui/accessibility/ax_tree_data.h"
  8. #include "ui/accessibility/ax_tree_id.h"
  9. namespace ui {
  10. TreeGenerator::TreeGenerator(int max_node_count, bool permutations)
  11. : max_node_count_(max_node_count),
  12. permutations_(permutations),
  13. total_unique_tree_count_(0) {
  14. unique_tree_count_by_size_.push_back(0);
  15. for (int i = 1; i <= max_node_count; ++i) {
  16. int unique_tree_count = UniqueTreeCountForNodeCount(i, permutations);
  17. unique_tree_count_by_size_.push_back(unique_tree_count);
  18. total_unique_tree_count_ += unique_tree_count;
  19. }
  20. }
  21. TreeGenerator::~TreeGenerator() {
  22. }
  23. int TreeGenerator::UniqueTreeCount() const {
  24. return total_unique_tree_count_;
  25. }
  26. void TreeGenerator::BuildUniqueTree(int tree_index, AXTree* out_tree) const {
  27. AXTreeUpdate update;
  28. BuildUniqueTreeUpdate(tree_index, &update);
  29. CHECK(out_tree->Unserialize(update)) << out_tree->error();
  30. }
  31. int TreeGenerator::IgnoredPermutationCountPerUniqueTree(int tree_index) const {
  32. int unique_tree_count_so_far = 0;
  33. for (int node_count = 1; node_count <= max_node_count_; ++node_count) {
  34. int unique_tree_count = unique_tree_count_by_size_[node_count];
  35. if (tree_index - unique_tree_count_so_far < unique_tree_count) {
  36. // Each node other than the root can be either ignored or not,
  37. // so return 2 ^ (node_count - 1)
  38. return 1 << (node_count - 1);
  39. }
  40. unique_tree_count_so_far += unique_tree_count;
  41. }
  42. NOTREACHED();
  43. return 0;
  44. }
  45. void TreeGenerator::BuildUniqueTreeWithIgnoredNodes(
  46. int tree_index,
  47. int ignored_index,
  48. absl::optional<int> focused_node,
  49. AXTree* out_tree) const {
  50. // Enable the behavior whereby all focused nodes will be exposed to the
  51. // platform accessibility layer. This behavior is currently disabled in
  52. // production code, but is enabled in tests so that it could be tested
  53. // thoroughly before it is turned on for all code.
  54. //
  55. // TODO(nektar): Turn this on in a followup patch.
  56. // AXTree::SetFocusedNodeShouldNeverBeIgnored();
  57. AXTreeUpdate update;
  58. BuildUniqueTreeUpdate(tree_index, &update);
  59. int node_count = static_cast<int>(update.nodes.size());
  60. CHECK_GE(ignored_index, 0);
  61. CHECK_LT(ignored_index, 1 << (node_count - 1));
  62. CHECK(!focused_node || *focused_node >= 0);
  63. CHECK(!focused_node || *focused_node < node_count);
  64. for (int i = 0; i < node_count - 1; i++) {
  65. if (ignored_index & (1 << i))
  66. update.nodes[i + 1].AddState(ax::mojom::State::kIgnored);
  67. }
  68. if (focused_node) {
  69. AXTreeData tree_data;
  70. tree_data.tree_id = AXTreeID::CreateNewAXTreeID();
  71. tree_data.focused_tree_id = tree_data.tree_id;
  72. tree_data.focus_id = update.nodes[*focused_node].id;
  73. update.has_tree_data = true;
  74. update.tree_data = tree_data;
  75. }
  76. CHECK(out_tree->Unserialize(update)) << out_tree->error();
  77. }
  78. void TreeGenerator::BuildUniqueTreeUpdate(int tree_index,
  79. AXTreeUpdate* out_update) const {
  80. CHECK_LT(tree_index, total_unique_tree_count_);
  81. int unique_tree_count_so_far = 0;
  82. for (int node_count = 1; node_count <= max_node_count_; ++node_count) {
  83. int unique_tree_count = unique_tree_count_by_size_[node_count];
  84. if (tree_index - unique_tree_count_so_far < unique_tree_count) {
  85. BuildUniqueTreeUpdateWithSize(
  86. node_count, tree_index - unique_tree_count_so_far, out_update);
  87. return;
  88. }
  89. unique_tree_count_so_far += unique_tree_count;
  90. }
  91. }
  92. void TreeGenerator::BuildUniqueTreeUpdateWithSize(
  93. int node_count,
  94. int tree_index,
  95. AXTreeUpdate* out_update) const {
  96. std::vector<int> indices;
  97. std::vector<int> permuted;
  98. int unique_tree_count = unique_tree_count_by_size_[node_count];
  99. CHECK_LT(tree_index, unique_tree_count);
  100. if (permutations_) {
  101. // Use the first few bits of |tree_index| to permute the indices.
  102. for (int i = 0; i < node_count; ++i)
  103. indices.push_back(i + 1);
  104. for (int i = 0; i < node_count; ++i) {
  105. int p = (node_count - i);
  106. int index = tree_index % p;
  107. tree_index /= p;
  108. permuted.push_back(indices[index]);
  109. indices.erase(indices.begin() + index);
  110. }
  111. } else {
  112. for (int i = 0; i < node_count; ++i)
  113. permuted.push_back(i + 1);
  114. }
  115. // Build an AXTreeUpdate. The first two nodes of the tree always
  116. // go in the same place.
  117. out_update->root_id = permuted[0];
  118. out_update->nodes.resize(node_count);
  119. out_update->nodes[0].id = permuted[0];
  120. if (node_count > 1) {
  121. out_update->nodes[0].child_ids.push_back(permuted[1]);
  122. out_update->nodes[1].id = permuted[1];
  123. }
  124. // The remaining nodes are assigned based on their parent
  125. // selected from the next bits from |tree_index|.
  126. for (int i = 2; i < node_count; ++i) {
  127. out_update->nodes[i].id = permuted[i];
  128. int parent_index = (tree_index % i);
  129. tree_index /= i;
  130. out_update->nodes[parent_index].child_ids.push_back(permuted[i]);
  131. }
  132. }
  133. } // namespace ui