tree_generator.h 3.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
  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. #ifndef UI_ACCESSIBILITY_TREE_GENERATOR_H_
  5. #define UI_ACCESSIBILITY_TREE_GENERATOR_H_
  6. #include <vector>
  7. #include "third_party/abseil-cpp/absl/types/optional.h"
  8. #include "ui/accessibility/ax_tree_update_forward.h"
  9. namespace ui {
  10. class AXTree;
  11. // This class is only used for fuzz testing.
  12. //
  13. // A class to create all possible trees with up to <n> nodes and the
  14. // ids [1...n].
  15. //
  16. // There are two parts to the algorithm:
  17. //
  18. // The tree structure is formed as follows: without loss of generality,
  19. // the first node becomes the root and the second node becomes its
  20. // child. Thereafter, choose every possible parent for every other node.
  21. //
  22. // So for node i in (3...n), there are (i - 1) possible choices for its
  23. // parent, for a total of (n-1)! (n minus 1 factorial) possible trees.
  24. //
  25. // The second optional part is the assignment of ids to the nodes in the tree.
  26. // There are exactly n! (n factorial) permutations of the sequence 1...n,
  27. // and each of these is assigned to every node in every possible tree.
  28. //
  29. // The total number of trees for a given <n>, including permutations of ids, is
  30. // n! * (n-1)!
  31. //
  32. // n = 2: 2 trees
  33. // n = 3: 12 trees
  34. // n = 4: 144 trees
  35. // n = 5: 2880 trees
  36. //
  37. // Note that the generator returns all trees with sizes *up to* <n>, which
  38. // is a bit larger.
  39. //
  40. // This grows really fast! Still, it's very helpful for exhaustively testing
  41. // tree code on smaller trees at least.
  42. class TreeGenerator {
  43. public:
  44. // Compute total number of trees.
  45. static constexpr int ComputeUniqueTreeCount(int max_node_count,
  46. bool permutations) {
  47. int tree_count = 0;
  48. for (int i = 1; i <= max_node_count; ++i)
  49. tree_count += UniqueTreeCountForNodeCount(i, permutations);
  50. return tree_count;
  51. }
  52. // Will generate all trees with up to |max_node_count| nodes.
  53. // If |permutations| is true, will return every possible permutation of
  54. // ids, otherwise the root will always have id 1, and so on.
  55. TreeGenerator(int max_node_count, bool permutations);
  56. ~TreeGenerator();
  57. // Build all unique trees (no nodes ignored).
  58. int UniqueTreeCount() const;
  59. void BuildUniqueTree(int tree_index, AXTree* out_tree) const;
  60. // Support for returning every permutation of ignored nodes
  61. // (other than the root, which is never ignored) per unique tree.
  62. int IgnoredPermutationCountPerUniqueTree(int tree_index) const;
  63. // The focused node is never ignored, even if marked as such. To enable
  64. // testing how focus could affect the ignored state when unserializing
  65. // trees, the `focused_node` argument (if specified) indicates which node
  66. // should be focused.
  67. void BuildUniqueTreeWithIgnoredNodes(int tree_index,
  68. int ignored_index,
  69. absl::optional<int> focused_node,
  70. AXTree* out_tree) const;
  71. private:
  72. static constexpr int UniqueTreeCountForNodeCount(int node_count,
  73. bool permutations) {
  74. int unique_tree_count = 1;
  75. // (n-1)! for the possible trees.
  76. for (int i = 2; i < node_count; ++i)
  77. unique_tree_count *= i;
  78. // n! for the permutations of ids.
  79. if (permutations)
  80. unique_tree_count = unique_tree_count * unique_tree_count * node_count;
  81. return unique_tree_count;
  82. }
  83. void BuildUniqueTreeUpdate(int tree_index,
  84. AXTreeUpdate* out_tree_update) const;
  85. void BuildUniqueTreeUpdateWithSize(int node_count,
  86. int tree_index,
  87. AXTreeUpdate* out_tree_update) const;
  88. int max_node_count_;
  89. bool permutations_;
  90. int total_unique_tree_count_;
  91. std::vector<int> unique_tree_count_by_size_;
  92. };
  93. } // namespace ui
  94. #endif // UI_ACCESSIBILITY_TREE_GENERATOR_H_