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