123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155 |
- // Copyright 2014 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "ui/accessibility/tree_generator.h"
- #include "ui/accessibility/ax_serializable_tree.h"
- #include "ui/accessibility/ax_tree.h"
- #include "ui/accessibility/ax_tree_data.h"
- #include "ui/accessibility/ax_tree_id.h"
- namespace ui {
- TreeGenerator::TreeGenerator(int max_node_count, bool permutations)
- : max_node_count_(max_node_count),
- permutations_(permutations),
- total_unique_tree_count_(0) {
- unique_tree_count_by_size_.push_back(0);
- for (int i = 1; i <= max_node_count; ++i) {
- int unique_tree_count = UniqueTreeCountForNodeCount(i, permutations);
- unique_tree_count_by_size_.push_back(unique_tree_count);
- total_unique_tree_count_ += unique_tree_count;
- }
- }
- TreeGenerator::~TreeGenerator() {
- }
- int TreeGenerator::UniqueTreeCount() const {
- return total_unique_tree_count_;
- }
- void TreeGenerator::BuildUniqueTree(int tree_index, AXTree* out_tree) const {
- AXTreeUpdate update;
- BuildUniqueTreeUpdate(tree_index, &update);
- CHECK(out_tree->Unserialize(update)) << out_tree->error();
- }
- int TreeGenerator::IgnoredPermutationCountPerUniqueTree(int tree_index) const {
- int unique_tree_count_so_far = 0;
- for (int node_count = 1; node_count <= max_node_count_; ++node_count) {
- int unique_tree_count = unique_tree_count_by_size_[node_count];
- if (tree_index - unique_tree_count_so_far < unique_tree_count) {
- // Each node other than the root can be either ignored or not,
- // so return 2 ^ (node_count - 1)
- return 1 << (node_count - 1);
- }
- unique_tree_count_so_far += unique_tree_count;
- }
- NOTREACHED();
- return 0;
- }
- void TreeGenerator::BuildUniqueTreeWithIgnoredNodes(
- int tree_index,
- int ignored_index,
- absl::optional<int> focused_node,
- AXTree* out_tree) const {
- // Enable the behavior whereby all focused nodes will be exposed to the
- // platform accessibility layer. This behavior is currently disabled in
- // production code, but is enabled in tests so that it could be tested
- // thoroughly before it is turned on for all code.
- //
- // TODO(nektar): Turn this on in a followup patch.
- // AXTree::SetFocusedNodeShouldNeverBeIgnored();
- AXTreeUpdate update;
- BuildUniqueTreeUpdate(tree_index, &update);
- int node_count = static_cast<int>(update.nodes.size());
- CHECK_GE(ignored_index, 0);
- CHECK_LT(ignored_index, 1 << (node_count - 1));
- CHECK(!focused_node || *focused_node >= 0);
- CHECK(!focused_node || *focused_node < node_count);
- for (int i = 0; i < node_count - 1; i++) {
- if (ignored_index & (1 << i))
- update.nodes[i + 1].AddState(ax::mojom::State::kIgnored);
- }
- if (focused_node) {
- AXTreeData tree_data;
- tree_data.tree_id = AXTreeID::CreateNewAXTreeID();
- tree_data.focused_tree_id = tree_data.tree_id;
- tree_data.focus_id = update.nodes[*focused_node].id;
- update.has_tree_data = true;
- update.tree_data = tree_data;
- }
- CHECK(out_tree->Unserialize(update)) << out_tree->error();
- }
- void TreeGenerator::BuildUniqueTreeUpdate(int tree_index,
- AXTreeUpdate* out_update) const {
- CHECK_LT(tree_index, total_unique_tree_count_);
- int unique_tree_count_so_far = 0;
- for (int node_count = 1; node_count <= max_node_count_; ++node_count) {
- int unique_tree_count = unique_tree_count_by_size_[node_count];
- if (tree_index - unique_tree_count_so_far < unique_tree_count) {
- BuildUniqueTreeUpdateWithSize(
- node_count, tree_index - unique_tree_count_so_far, out_update);
- return;
- }
- unique_tree_count_so_far += unique_tree_count;
- }
- }
- void TreeGenerator::BuildUniqueTreeUpdateWithSize(
- int node_count,
- int tree_index,
- AXTreeUpdate* out_update) const {
- std::vector<int> indices;
- std::vector<int> permuted;
- int unique_tree_count = unique_tree_count_by_size_[node_count];
- CHECK_LT(tree_index, unique_tree_count);
- if (permutations_) {
- // Use the first few bits of |tree_index| to permute the indices.
- for (int i = 0; i < node_count; ++i)
- indices.push_back(i + 1);
- for (int i = 0; i < node_count; ++i) {
- int p = (node_count - i);
- int index = tree_index % p;
- tree_index /= p;
- permuted.push_back(indices[index]);
- indices.erase(indices.begin() + index);
- }
- } else {
- for (int i = 0; i < node_count; ++i)
- permuted.push_back(i + 1);
- }
- // Build an AXTreeUpdate. The first two nodes of the tree always
- // go in the same place.
- out_update->root_id = permuted[0];
- out_update->nodes.resize(node_count);
- out_update->nodes[0].id = permuted[0];
- if (node_count > 1) {
- out_update->nodes[0].child_ids.push_back(permuted[1]);
- out_update->nodes[1].id = permuted[1];
- }
- // The remaining nodes are assigned based on their parent
- // selected from the next bits from |tree_index|.
- for (int i = 2; i < node_count; ++i) {
- out_update->nodes[i].id = permuted[i];
- int parent_index = (tree_index % i);
- tree_index /= i;
- out_update->nodes[parent_index].child_ids.push_back(permuted[i]);
- }
- }
- } // namespace ui
|