ax_range.h 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503
  1. // Copyright 2016 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_AX_RANGE_H_
  5. #define UI_ACCESSIBILITY_AX_RANGE_H_
  6. #include <memory>
  7. #include <ostream>
  8. #include <string>
  9. #include <utility>
  10. #include <vector>
  11. #include "base/strings/utf_string_conversions.h"
  12. #include "third_party/abseil-cpp/absl/types/optional.h"
  13. #include "ui/accessibility/ax_clipping_behavior.h"
  14. #include "ui/accessibility/ax_node.h"
  15. #include "ui/accessibility/ax_node_position.h"
  16. #include "ui/accessibility/ax_offscreen_result.h"
  17. #include "ui/accessibility/ax_role_properties.h"
  18. #include "ui/accessibility/ax_tree_manager_map.h"
  19. namespace ui {
  20. // Specifies how AXRange::GetText treats any formatting changes, such as
  21. // paragraph breaks, that have been introduced by layout. For example, consider
  22. // the following HTML snippet: "A<div>B</div>C".
  23. enum class AXTextConcatenationBehavior {
  24. // Preserve any introduced formatting, such as paragraph breaks, e.g. GetText
  25. // = "A\nB\nC".
  26. kWithParagraphBreaks,
  27. // Ignore any introduced formatting, such as paragraph breaks, e.g. GetText =
  28. // "ABC".
  29. kWithoutParagraphBreaks
  30. };
  31. class AXRangeRectDelegate {
  32. public:
  33. virtual gfx::Rect GetInnerTextRangeBoundsRect(
  34. AXTreeID tree_id,
  35. AXNodeID node_id,
  36. int start_offset,
  37. int end_offset,
  38. ui::AXClippingBehavior clipping_behavior,
  39. AXOffscreenResult* offscreen_result) = 0;
  40. virtual gfx::Rect GetBoundsRect(AXTreeID tree_id,
  41. AXNodeID node_id,
  42. AXOffscreenResult* offscreen_result) = 0;
  43. };
  44. // A range delimited by two positions in the AXTree.
  45. //
  46. // In order to avoid any confusion regarding whether a deep or a shallow copy is
  47. // being performed, this class can be moved, but not copied.
  48. template <class AXPositionType>
  49. class AXRange {
  50. public:
  51. using AXPositionInstance = std::unique_ptr<AXPositionType>;
  52. // Creates an `AXRange` encompassing the contents of the given `AXNode`.
  53. static AXRange RangeOfContents(const AXNode& node) {
  54. AXPositionInstance start_position = AXNodePosition::CreatePosition(
  55. node, /* child_index_or_text_offset */ 0);
  56. AXPositionInstance end_position =
  57. start_position->CreatePositionAtEndOfAnchor();
  58. return AXRange(std::move(start_position), std::move(end_position));
  59. }
  60. AXRange()
  61. : anchor_(AXPositionType::CreateNullPosition()),
  62. focus_(AXPositionType::CreateNullPosition()) {}
  63. AXRange(AXPositionInstance anchor, AXPositionInstance focus) {
  64. anchor_ = anchor ? std::move(anchor) : AXPositionType::CreateNullPosition();
  65. focus_ = focus ? std::move(focus) : AXPositionType::CreateNullPosition();
  66. }
  67. AXRange(const AXRange& other) = delete;
  68. AXRange(AXRange&& other) : AXRange() {
  69. anchor_.swap(other.anchor_);
  70. focus_.swap(other.focus_);
  71. }
  72. virtual ~AXRange() = default;
  73. AXPositionType* anchor() const {
  74. DCHECK(anchor_);
  75. return anchor_.get();
  76. }
  77. AXPositionType* focus() const {
  78. DCHECK(focus_);
  79. return focus_.get();
  80. }
  81. AXRange& operator=(const AXRange& other) = delete;
  82. AXRange& operator=(AXRange&& other) {
  83. if (this != &other) {
  84. anchor_ = AXPositionType::CreateNullPosition();
  85. focus_ = AXPositionType::CreateNullPosition();
  86. anchor_.swap(other.anchor_);
  87. focus_.swap(other.focus_);
  88. }
  89. return *this;
  90. }
  91. bool operator==(const AXRange& other) const {
  92. if (IsNull())
  93. return other.IsNull();
  94. return !other.IsNull() && *anchor_ == *other.anchor() &&
  95. *focus_ == *other.focus();
  96. }
  97. bool operator!=(const AXRange& other) const { return !(*this == other); }
  98. // Given a pair of AXPosition, determines how the first compares with the
  99. // second, relative to the order they would be iterated over by using
  100. // AXRange::Iterator to traverse all leaf text ranges in a tree.
  101. //
  102. // Notice that this method is different from using AXPosition::CompareTo since
  103. // the following logic takes into account BOTH tree pre-order traversal and
  104. // text offsets when both positions are located within the same anchor.
  105. //
  106. // Returns:
  107. // 0 - If both positions are equivalent.
  108. // <0 - If the first position would come BEFORE the second.
  109. // >0 - If the first position would come AFTER the second.
  110. // nullopt - If positions are not comparable (see AXPosition::CompareTo).
  111. static absl::optional<int> CompareEndpoints(const AXPositionType* first,
  112. const AXPositionType* second) {
  113. absl::optional<int> tree_position_comparison =
  114. first->AsTreePosition()->CompareTo(*second->AsTreePosition());
  115. // When the tree comparison is nullopt, using value_or(1) forces a default
  116. // value of 1, making the following statement return nullopt as well.
  117. return (tree_position_comparison.value_or(1) != 0)
  118. ? tree_position_comparison
  119. : first->CompareTo(*second);
  120. }
  121. AXRange AsForwardRange() const {
  122. return (CompareEndpoints(anchor(), focus()).value_or(0) > 0)
  123. ? AXRange(focus_->Clone(), anchor_->Clone())
  124. : AXRange(anchor_->Clone(), focus_->Clone());
  125. }
  126. AXRange AsBackwardRange() const {
  127. return (CompareEndpoints(anchor(), focus()).value_or(0) < 0)
  128. ? AXRange(focus_->Clone(), anchor_->Clone())
  129. : AXRange(anchor_->Clone(), focus_->Clone());
  130. }
  131. bool IsCollapsed() const { return !IsNull() && *anchor_ == *focus_; }
  132. // We define a "leaf text range" as an AXRange whose endpoints are leaf text
  133. // positions located within the same anchor of the AXTree.
  134. bool IsLeafTextRange() const {
  135. return !IsNull() && anchor_->GetAnchor() == focus_->GetAnchor() &&
  136. anchor_->IsLeafTextPosition() && focus_->IsLeafTextPosition();
  137. }
  138. bool IsNull() const {
  139. DCHECK(anchor_ && focus_);
  140. return anchor_->IsNullPosition() || focus_->IsNullPosition();
  141. }
  142. std::string ToString() const {
  143. return "Range\nAnchor:" + anchor_->ToString() +
  144. "\nFocus:" + focus_->ToString();
  145. }
  146. // We can decompose any given AXRange into multiple "leaf text ranges".
  147. // As an example, consider the following HTML code:
  148. //
  149. // <p>line with text<br><input type="checkbox">line with checkbox</p>
  150. //
  151. // It will produce the following AXTree; notice that the leaf text nodes
  152. // (enclosed in parenthesis) compose its text representation:
  153. //
  154. // paragraph
  155. // staticText name='line with text'
  156. // (inlineTextBox name='line with text')
  157. // lineBreak name='<newline>'
  158. // (inlineTextBox name='<newline>')
  159. // (checkBox)
  160. // staticText name='line with checkbox'
  161. // (inlineTextBox name='line with checkbox')
  162. //
  163. // Suppose we have an AXRange containing all elements from the example above.
  164. // The text representation of such range, with AXRange's endpoints marked by
  165. // opening and closing brackets, will look like the following:
  166. //
  167. // "[line with text\n{checkBox}line with checkbox]"
  168. //
  169. // Note that in the text representation {checkBox} is not visible, but it is
  170. // effectively a "leaf text range", so we include it in the example above only
  171. // to visualize how the iterator should work.
  172. //
  173. // Decomposing the AXRange above into its "leaf text ranges" would result in:
  174. //
  175. // "[line with text][\n][{checkBox}][line with checkbox]"
  176. //
  177. // This class allows AXRange to be iterated through all "leaf text ranges"
  178. // contained between its endpoints, composing the entire range.
  179. class Iterator {
  180. public:
  181. using iterator_category = std::input_iterator_tag;
  182. using value_type = AXRange;
  183. using difference_type = std::ptrdiff_t;
  184. using pointer = AXRange*;
  185. using reference = AXRange&;
  186. Iterator()
  187. : current_start_(AXPositionType::CreateNullPosition()),
  188. iterator_end_(AXPositionType::CreateNullPosition()) {}
  189. Iterator(AXPositionInstance start, AXPositionInstance end) {
  190. if (end && !end->IsNullPosition()) {
  191. current_start_ = !start ? AXPositionType::CreateNullPosition()
  192. : start->AsLeafTextPosition();
  193. iterator_end_ = end->AsLeafTextPosition();
  194. } else {
  195. current_start_ = AXPositionType::CreateNullPosition();
  196. iterator_end_ = AXPositionType::CreateNullPosition();
  197. }
  198. }
  199. Iterator(const Iterator& other) = delete;
  200. Iterator(Iterator&& other)
  201. : current_start_(std::move(other.current_start_)),
  202. iterator_end_(std::move(other.iterator_end_)) {}
  203. ~Iterator() = default;
  204. bool operator==(const Iterator& other) const {
  205. return current_start_->GetAnchor() == other.current_start_->GetAnchor() &&
  206. iterator_end_->GetAnchor() == other.iterator_end_->GetAnchor() &&
  207. *current_start_ == *other.current_start_ &&
  208. *iterator_end_ == *other.iterator_end_;
  209. }
  210. bool operator!=(const Iterator& other) const { return !(*this == other); }
  211. // Only forward iteration is supported, so operator-- is not implemented.
  212. Iterator& operator++() {
  213. DCHECK(!current_start_->IsNullPosition());
  214. if (current_start_->GetAnchor() == iterator_end_->GetAnchor()) {
  215. current_start_ = AXPositionType::CreateNullPosition();
  216. } else {
  217. current_start_ = current_start_->CreateNextLeafTreePosition();
  218. DCHECK_LE(*current_start_, *iterator_end_);
  219. }
  220. return *this;
  221. }
  222. AXRange operator*() const {
  223. DCHECK(!current_start_->IsNullPosition());
  224. AXPositionInstance current_end =
  225. (current_start_->GetAnchor() != iterator_end_->GetAnchor())
  226. ? current_start_->CreatePositionAtEndOfAnchor()
  227. : iterator_end_->Clone();
  228. DCHECK_LE(*current_end, *iterator_end_);
  229. AXRange current_leaf_text_range(current_start_->AsTextPosition(),
  230. current_end->AsTextPosition());
  231. DCHECK(current_leaf_text_range.IsLeafTextRange());
  232. return std::move(current_leaf_text_range);
  233. }
  234. private:
  235. AXPositionInstance current_start_;
  236. AXPositionInstance iterator_end_;
  237. };
  238. Iterator begin() const {
  239. if (IsNull())
  240. return Iterator(nullptr, nullptr);
  241. AXRange forward_range = AsForwardRange();
  242. return Iterator(std::move(forward_range.anchor_),
  243. std::move(forward_range.focus_));
  244. }
  245. Iterator end() const {
  246. if (IsNull())
  247. return Iterator(nullptr, nullptr);
  248. AXRange forward_range = AsForwardRange();
  249. return Iterator(nullptr, std::move(forward_range.focus_));
  250. }
  251. // Returns the concatenation of the accessible names of all text nodes
  252. // contained between this AXRange's endpoints.
  253. // Pass a |max_count| of -1 to retrieve all text in the AXRange.
  254. // Note that if this AXRange has its anchor or focus located at an ignored
  255. // position, we shrink the range to the closest unignored positions.
  256. std::u16string GetText(
  257. AXTextConcatenationBehavior concatenation_behavior =
  258. AXTextConcatenationBehavior::kWithoutParagraphBreaks,
  259. AXEmbeddedObjectBehavior embedded_object_behavior =
  260. AXEmbeddedObjectBehavior::kExposeCharacter,
  261. int max_count = -1,
  262. bool include_ignored = false,
  263. size_t* appended_newlines_count = nullptr) const {
  264. if (max_count == 0 || IsNull())
  265. return std::u16string();
  266. absl::optional<int> endpoint_comparison =
  267. CompareEndpoints(anchor(), focus());
  268. if (!endpoint_comparison)
  269. return std::u16string();
  270. AXPositionInstance start = (endpoint_comparison.value() < 0)
  271. ? anchor_->AsLeafTextPosition()
  272. : focus_->AsLeafTextPosition();
  273. AXPositionInstance end = (endpoint_comparison.value() < 0)
  274. ? focus_->AsLeafTextPosition()
  275. : anchor_->AsLeafTextPosition();
  276. std::u16string range_text;
  277. size_t computed_newlines_count = 0;
  278. bool is_first_non_whitespace_leaf = true;
  279. bool crossed_paragraph_boundary = false;
  280. bool is_first_included_leaf = true;
  281. bool found_trailing_newline = false;
  282. while (!start->IsNullPosition()) {
  283. DCHECK(start->IsLeafTextPosition());
  284. DCHECK_GE(start->text_offset(), 0);
  285. const bool start_is_unignored = !start->IsIgnored();
  286. const bool start_is_in_white_space = start->IsInWhiteSpace();
  287. if (include_ignored || start_is_unignored) {
  288. if (concatenation_behavior ==
  289. AXTextConcatenationBehavior::kWithParagraphBreaks &&
  290. !start_is_in_white_space) {
  291. if (is_first_non_whitespace_leaf && !is_first_included_leaf) {
  292. // The first non-whitespace leaf in the range could be preceded by
  293. // whitespace spanning even before the start of this range, we need
  294. // to check such positions in order to correctly determine if this
  295. // is a paragraph's start (see |AXPosition::AtStartOfParagraph|).
  296. // However, if the first paragraph boundary in the range is ignored,
  297. // e.g. <div aria-hidden="true"></div>, we do not take it into
  298. // consideration even when `include_ignored` == true, because the
  299. // beginning of the text range, as experienced by the user, is after
  300. // any trailing ignored nodes.
  301. crossed_paragraph_boundary =
  302. start_is_unignored && start->AtStartOfParagraph();
  303. }
  304. // When preserving layout line breaks, don't append `\n` next if the
  305. // previous leaf position was a <br> (already ending with a newline).
  306. if (crossed_paragraph_boundary && !found_trailing_newline) {
  307. range_text += u"\n";
  308. computed_newlines_count++;
  309. }
  310. is_first_non_whitespace_leaf = false;
  311. crossed_paragraph_boundary = false;
  312. }
  313. int current_end_offset =
  314. (start->GetAnchor() != end->GetAnchor())
  315. ? start->MaxTextOffset(embedded_object_behavior)
  316. : end->text_offset();
  317. if (current_end_offset > start->text_offset()) {
  318. int characters_to_append =
  319. (max_count > 0)
  320. ? std::min(max_count - static_cast<int>(range_text.length()),
  321. current_end_offset - start->text_offset())
  322. : current_end_offset - start->text_offset();
  323. std::u16string position_text =
  324. start->GetText(embedded_object_behavior);
  325. if (start->text_offset() < static_cast<int>(position_text.length())) {
  326. range_text += position_text.substr(start->text_offset(),
  327. characters_to_append);
  328. }
  329. // To minimize user confusion, collapse all whitespace following any
  330. // line break unless it is a hard line break (<br> or a text node with
  331. // a single '\n' character), or an empty object such as an empty text
  332. // field.
  333. found_trailing_newline =
  334. start->GetAnchor()->IsLineBreak() ||
  335. (found_trailing_newline && start_is_in_white_space);
  336. }
  337. DCHECK(max_count < 0 ||
  338. static_cast<int>(range_text.length()) <= max_count);
  339. is_first_included_leaf = false;
  340. }
  341. if (start->GetAnchor() == end->GetAnchor() ||
  342. static_cast<int>(range_text.length()) == max_count) {
  343. break;
  344. }
  345. start = start->CreateNextLeafTextPosition();
  346. if (concatenation_behavior ==
  347. AXTextConcatenationBehavior::kWithParagraphBreaks &&
  348. !crossed_paragraph_boundary && !is_first_non_whitespace_leaf) {
  349. crossed_paragraph_boundary = start->AtStartOfParagraph();
  350. }
  351. }
  352. if (appended_newlines_count)
  353. *appended_newlines_count = computed_newlines_count;
  354. return range_text;
  355. }
  356. // Appends rects of all anchor nodes that span between anchor_ and focus_.
  357. // Rects outside of the viewport are skipped.
  358. // Coordinate system is determined by the passed-in delegate.
  359. std::vector<gfx::Rect> GetRects(AXRangeRectDelegate* delegate) const {
  360. std::vector<gfx::Rect> rects;
  361. AXPositionInstance range_start = anchor()->AsLeafTextPosition();
  362. AXPositionInstance range_end = focus()->AsLeafTextPosition();
  363. // For a degenerate range, we want to fetch unclipped bounding rect, because
  364. // text with the same start and end off set (i.e. degenerate) will have an
  365. // inner text bounding rect with height of the character and width of 0,
  366. // which the browser platform will consider as an empty rect and ends up
  367. // clipping it, resulting in size 0x1 rect.
  368. // After we retrieve the unclipped bounding rect, we want to set its width
  369. // to 1 to represent a caret/insertion point.
  370. //
  371. // Note: The caller of this function is only UIA TextPattern, so displaying
  372. // bounding rects for degenerate range is only limited for UIA currently.
  373. if (IsCollapsed() && range_start->IsInTextObject()) {
  374. AXOffscreenResult offscreen_result;
  375. gfx::Rect degenerate_range_rect = delegate->GetInnerTextRangeBoundsRect(
  376. range_start->tree_id(), range_start->anchor_id(),
  377. range_start->text_offset(), range_end->text_offset(),
  378. ui::AXClippingBehavior::kUnclipped, &offscreen_result);
  379. if (offscreen_result == AXOffscreenResult::kOnscreen) {
  380. DCHECK(degenerate_range_rect.width() == 0);
  381. degenerate_range_rect.set_width(1);
  382. rects.push_back(degenerate_range_rect);
  383. }
  384. return rects;
  385. }
  386. for (const AXRange& leaf_text_range : *this) {
  387. DCHECK(leaf_text_range.IsLeafTextRange());
  388. AXPositionType* current_line_start = leaf_text_range.anchor();
  389. AXPositionType* current_line_end = leaf_text_range.focus();
  390. // We want to skip ranges from ignored nodes.
  391. if (current_line_start->IsIgnored())
  392. continue;
  393. // For text anchors, we retrieve the bounding rectangles of its text
  394. // content. For non-text anchors (such as checkboxes, images, etc.), we
  395. // want to directly retrieve their bounding rectangles.
  396. AXOffscreenResult offscreen_result;
  397. gfx::Rect current_rect =
  398. (current_line_start->GetAnchor()->IsLineBreak() ||
  399. current_line_start->IsInTextObject())
  400. ? delegate->GetInnerTextRangeBoundsRect(
  401. current_line_start->tree_id(),
  402. current_line_start->anchor_id(),
  403. current_line_start->text_offset(),
  404. current_line_end->text_offset(),
  405. ui::AXClippingBehavior::kClipped, &offscreen_result)
  406. : delegate->GetBoundsRect(current_line_start->tree_id(),
  407. current_line_start->anchor_id(),
  408. &offscreen_result);
  409. // If the bounding box of the current range is clipped because it lies
  410. // outside an ancestor’s bounds, then the bounding box is pushed to the
  411. // nearest edge of such ancestor's bounds, with its width and height
  412. // forced to be 1, and the node will be marked as "offscreen".
  413. //
  414. // Only add rectangles that are not empty and not marked as "offscreen".
  415. //
  416. // See the documentation for how bounding boxes are calculated in AXTree:
  417. // https://chromium.googlesource.com/chromium/src/+/HEAD/docs/accessibility/offscreen.md
  418. if (!current_rect.IsEmpty() &&
  419. offscreen_result == AXOffscreenResult::kOnscreen)
  420. rects.push_back(current_rect);
  421. }
  422. return rects;
  423. }
  424. private:
  425. AXPositionInstance anchor_;
  426. AXPositionInstance focus_;
  427. };
  428. template <class AXPositionType>
  429. std::ostream& operator<<(std::ostream& stream,
  430. const AXRange<AXPositionType>& range) {
  431. return stream << range.ToString();
  432. }
  433. } // namespace ui
  434. #endif // UI_ACCESSIBILITY_AX_RANGE_H_