| // Copyright 2016 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. |
| |
| #ifndef UI_ACCESSIBILITY_AX_POSITION_H_ |
| #define UI_ACCESSIBILITY_AX_POSITION_H_ |
| |
| #include <stdint.h> |
| |
| #include <memory> |
| #include <ostream> |
| #include <string> |
| #include <type_traits> |
| #include <utility> |
| #include <vector> |
| |
| #include "base/containers/stack.h" |
| #include "base/optional.h" |
| #include "base/stl_util.h" |
| #include "base/strings/string16.h" |
| #include "base/strings/string_number_conversions.h" |
| #include "base/strings/utf_string_conversions.h" |
| #include "ui/accessibility/ax_enum_util.h" |
| #include "ui/accessibility/ax_enums.mojom.h" |
| #include "ui/accessibility/ax_node.h" |
| #include "ui/accessibility/ax_node_text_styles.h" |
| #include "ui/accessibility/ax_role_properties.h" |
| #include "ui/accessibility/ax_text_boundary.h" |
| #include "ui/accessibility/ax_tree_id.h" |
| |
| namespace ui { |
| |
| // Defines the type of position in the accessibility tree. |
| // A tree position is used when referring to a specific child of a node in the |
| // accessibility tree. |
| // A text position is used when referring to a specific character of text inside |
| // a particular node. |
| // A null position is used to signify that the provided data is invalid or that |
| // a boundary has been reached. |
| enum class AXPositionKind { NULL_POSITION, TREE_POSITION, TEXT_POSITION }; |
| |
| // Defines how creating the next or previous position should behave whenever we |
| // are at or are crossing a boundary, such as at the start of an anchor, a word |
| // or a line. |
| enum class AXBoundaryBehavior { |
| CrossBoundary, |
| StopAtAnchorBoundary, |
| StopIfAlreadyAtBoundary, |
| StopAtLastAnchorBoundary |
| }; |
| |
| // Specifies how AXPosition::ExpandToEnclosingTextBoundary behaves. |
| // |
| // As an example, imagine we have the text "hello world" and a position before |
| // the space character. We want to expand to the surrounding word boundary. |
| // Since we are right at the end of the first word, we could either expand to |
| // the left first, find the start of the first word and then use that to find |
| // the corresponding word end, resulting in the word "Hello". Another |
| // possibility is to expand to the right first, find the end of the next word |
| // and use that as our starting point to find the previous word start, resulting |
| // in the word "world". |
| enum class AXRangeExpandBehavior { |
| // Expands to the left boundary first and then uses that position as the |
| // starting point to find the boundary to the right. |
| kLeftFirst, |
| // Expands to the right boundary first and then uses that position as the |
| // starting point to find the boundary to the left. |
| kRightFirst |
| }; |
| |
| // Forward declarations. |
| template <class AXPositionType, class AXNodeType> |
| class AXPosition; |
| template <class AXPositionType> |
| class AXRange; |
| template <class AXPositionType, class AXNodeType> |
| bool operator==(const AXPosition<AXPositionType, AXNodeType>& first, |
| const AXPosition<AXPositionType, AXNodeType>& second); |
| template <class AXPositionType, class AXNodeType> |
| bool operator!=(const AXPosition<AXPositionType, AXNodeType>& first, |
| const AXPosition<AXPositionType, AXNodeType>& second); |
| |
| // A position in the accessibility tree. |
| // |
| // This class could either represent a tree position or a text position. |
| // Tree positions point to either a child of a specific node or at the end of a |
| // node (i.e. an "after children" position). |
| // Text positions point to either a character offset in the text inside a |
| // particular node including text from all its children, or to the end of the |
| // node's text, (i.e. an "after text" position). |
| // On tree positions that have a leaf node as their anchor, we also need to |
| // distinguish between "before text" and "after text" positions. To do this, if |
| // the child index is 0 and the anchor is a leaf node, then it's an "after text" |
| // position. If the child index is |BEFORE_TEXT| and the anchor is a leaf node, |
| // then this is a "before text" position. |
| // It doesn't make sense to have a "before text" position on a text position, |
| // because it is identical to setting its offset to the first character. |
| // |
| // To avoid re-computing either the text offset or the child index when |
| // converting between the two types of positions, both values are saved after |
| // the first conversion. |
| // |
| // This class template uses static polymorphism in order to allow sub-classes to |
| // be created from the base class without the base class knowing the type of the |
| // sub-class in advance. |
| // The template argument |AXPositionType| should always be set to the type of |
| // any class that inherits from this template, making this a |
| // "curiously recursive template". |
| // |
| // This class can be copied using the |Clone| method. It is designed to be |
| // immutable. |
| template <class AXPositionType, class AXNodeType> |
| class AXPosition { |
| public: |
| using AXPositionInstance = |
| std::unique_ptr<AXPosition<AXPositionType, AXNodeType>>; |
| |
| using AXRangeType = AXRange<AXPosition<AXPositionType, AXNodeType>>; |
| |
| using BoundaryConditionPredicate = |
| base::RepeatingCallback<bool(const AXPositionInstance&)>; |
| |
| // When converting an unignored position, determines how to adjust the new |
| // position in order to make it valid. |
| enum class AdjustmentBehavior { kMoveLeft, kMoveRight }; |
| |
| static const int BEFORE_TEXT = -1; |
| static const int INVALID_INDEX = -2; |
| static const int INVALID_OFFSET = -1; |
| |
| static AXPositionInstance CreateNullPosition() { |
| AXPositionInstance new_position(new AXPositionType()); |
| new_position->Initialize( |
| AXPositionKind::NULL_POSITION, AXTreeIDUnknown(), AXNode::kInvalidAXID, |
| INVALID_INDEX, INVALID_OFFSET, ax::mojom::TextAffinity::kDownstream); |
| return new_position; |
| } |
| |
| static AXPositionInstance CreateTreePosition(AXTreeID tree_id, |
| AXNode::AXID anchor_id, |
| int child_index) { |
| AXPositionInstance new_position(new AXPositionType()); |
| new_position->Initialize(AXPositionKind::TREE_POSITION, tree_id, anchor_id, |
| child_index, INVALID_OFFSET, |
| ax::mojom::TextAffinity::kDownstream); |
| return new_position; |
| } |
| |
| static AXPositionInstance CreateTextPosition( |
| AXTreeID tree_id, |
| AXNode::AXID anchor_id, |
| int text_offset, |
| ax::mojom::TextAffinity affinity) { |
| AXPositionInstance new_position(new AXPositionType()); |
| new_position->Initialize(AXPositionKind::TEXT_POSITION, tree_id, anchor_id, |
| INVALID_INDEX, text_offset, affinity); |
| return new_position; |
| } |
| |
| virtual ~AXPosition() = default; |
| |
| virtual AXPositionInstance Clone() const = 0; |
| |
| // A serialization of a position as POD. Not for sharing on disk or sharing |
| // across thread or process boundaries, just for passing a position to an |
| // API that works with positions as opaque objects. |
| struct SerializedPosition { |
| AXPositionKind kind; |
| AXNode::AXID anchor_id; |
| int child_index; |
| int text_offset; |
| ax::mojom::TextAffinity affinity; |
| char tree_id[33]; |
| }; |
| |
| static_assert(std::is_trivially_copyable<SerializedPosition>::value, |
| "SerializedPosition must be POD"); |
| |
| SerializedPosition Serialize() { |
| SerializedPosition result; |
| result.kind = kind_; |
| |
| // A tree ID can be serialized as a 32-byte string. |
| std::string tree_id_string = tree_id_.ToString(); |
| DCHECK_LE(tree_id_string.size(), 32U); |
| strncpy(result.tree_id, tree_id_string.c_str(), 32); |
| result.tree_id[32] = 0; |
| |
| result.anchor_id = anchor_id_; |
| result.child_index = child_index_; |
| result.text_offset = text_offset_; |
| result.affinity = affinity_; |
| return result; |
| } |
| |
| static AXPositionInstance Unserialize( |
| const SerializedPosition& serialization) { |
| AXPositionInstance new_position(new AXPositionType()); |
| new_position->Initialize(serialization.kind, |
| ui::AXTreeID::FromString(serialization.tree_id), |
| serialization.anchor_id, serialization.child_index, |
| serialization.text_offset, serialization.affinity); |
| return new_position; |
| } |
| |
| virtual bool IsIgnoredPosition() const { return false; } |
| |
| virtual AXPositionInstance AsUnignoredTextPosition( |
| AdjustmentBehavior adjustment_behavior) const { |
| return Clone(); |
| } |
| |
| std::string ToString() const { |
| std::string str; |
| switch (kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return "NullPosition"; |
| case AXPositionKind::TREE_POSITION: { |
| std::string str_child_index; |
| if (child_index_ == BEFORE_TEXT) { |
| str_child_index = "before_text"; |
| } else if (child_index_ == INVALID_INDEX) { |
| str_child_index = "invalid"; |
| } else { |
| str_child_index = base::NumberToString(child_index_); |
| } |
| str = "TreePosition tree_id=" + tree_id_.ToString() + |
| " anchor_id=" + base::NumberToString(anchor_id_) + |
| " child_index=" + str_child_index; |
| break; |
| } |
| case AXPositionKind::TEXT_POSITION: { |
| std::string str_text_offset; |
| if (text_offset_ == INVALID_OFFSET) { |
| str_text_offset = "invalid"; |
| } else { |
| str_text_offset = base::NumberToString(text_offset_); |
| } |
| str = "TextPosition anchor_id=" + base::NumberToString(anchor_id_) + |
| " text_offset=" + str_text_offset + " affinity=" + |
| ui::ToString(static_cast<ax::mojom::TextAffinity>(affinity_)); |
| break; |
| } |
| } |
| |
| if (!IsTextPosition() || text_offset_ > MaxTextOffset()) |
| return str; |
| |
| std::string text = base::UTF16ToUTF8(GetText()); |
| DCHECK_GE(text_offset_, 0); |
| DCHECK_LE(text_offset_, static_cast<int>(text.length())); |
| std::string annotated_text; |
| if (text_offset_ == MaxTextOffset()) { |
| annotated_text = text + "<>"; |
| } else { |
| annotated_text = text.substr(0, text_offset_) + "<" + text[text_offset_] + |
| ">" + text.substr(text_offset_ + 1); |
| } |
| |
| return str + " annotated_text=" + annotated_text; |
| } |
| |
| AXTreeID tree_id() const { return tree_id_; } |
| AXNode::AXID anchor_id() const { return anchor_id_; } |
| |
| AXNodeType* GetAnchor() const { |
| if (tree_id_ == AXTreeIDUnknown() || anchor_id_ == AXNode::kInvalidAXID) |
| return nullptr; |
| DCHECK_GE(anchor_id_, 0); |
| return GetNodeInTree(tree_id_, anchor_id_); |
| } |
| |
| bool IsIgnored() const { |
| AXNodeType* anchor = GetAnchor(); |
| return anchor && anchor->IsIgnored(); |
| } |
| |
| AXPositionKind kind() const { return kind_; } |
| int child_index() const { return child_index_; } |
| int text_offset() const { return text_offset_; } |
| ax::mojom::TextAffinity affinity() const { return affinity_; } |
| |
| bool IsNullPosition() const { |
| return kind_ == AXPositionKind::NULL_POSITION || !GetAnchor(); |
| } |
| |
| bool IsTreePosition() const { |
| return GetAnchor() && kind_ == AXPositionKind::TREE_POSITION; |
| } |
| |
| bool IsTextPosition() const { |
| return GetAnchor() && kind_ == AXPositionKind::TEXT_POSITION; |
| } |
| |
| bool IsLeafTextPosition() const { |
| return IsTextPosition() && !AnchorChildCount(); |
| } |
| |
| // TODO(nektar): Update logic of AtStartOfAnchor() for text_offset_ == 0 and |
| // fix related bug. |
| bool AtStartOfAnchor() const { |
| if (!GetAnchor()) |
| return false; |
| switch (kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| if (text_offset_ > 0) |
| return false; |
| if (AnchorChildCount() || text_offset_ == 0) |
| return child_index_ == 0; |
| return child_index_ == BEFORE_TEXT; |
| case AXPositionKind::TEXT_POSITION: |
| return text_offset_ == 0; |
| } |
| } |
| |
| bool AtEndOfAnchor() const { |
| if (!GetAnchor()) |
| return false; |
| switch (kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| return child_index_ == AnchorChildCount(); |
| case AXPositionKind::TEXT_POSITION: |
| return text_offset_ == MaxTextOffset(); |
| } |
| } |
| |
| bool AtStartOfWord() const { |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| switch (text_position->kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| NOTREACHED(); |
| return false; |
| case AXPositionKind::TEXT_POSITION: { |
| const std::vector<int32_t> word_starts = |
| text_position->GetWordStartOffsets(); |
| return base::Contains( |
| word_starts, static_cast<int32_t>(text_position->text_offset_)); |
| } |
| } |
| } |
| |
| bool AtEndOfWord() const { |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| switch (text_position->kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| NOTREACHED(); |
| return false; |
| case AXPositionKind::TEXT_POSITION: { |
| const std::vector<int32_t> word_ends = |
| text_position->GetWordEndOffsets(); |
| return base::Contains( |
| word_ends, static_cast<int32_t>(text_position->text_offset_)); |
| } |
| } |
| } |
| |
| bool AtStartOfLine() const { |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| switch (text_position->kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| NOTREACHED(); |
| return false; |
| case AXPositionKind::TEXT_POSITION: |
| // We treat a position after some white space that is not connected to |
| // any node after it via "next on line ID", to be equivalent to a |
| // position before the next line, and therefore as being at start of |
| // line. |
| // |
| // We assume that white space separates lines. |
| if (text_position->IsInWhiteSpace() && |
| GetNextOnLineID(text_position->anchor_id_) == |
| AXNode::kInvalidAXID && |
| text_position->AtEndOfAnchor()) { |
| return true; |
| } |
| |
| return GetPreviousOnLineID(text_position->anchor_id_) == |
| AXNode::kInvalidAXID && |
| text_position->AtStartOfAnchor(); |
| } |
| } |
| |
| bool AtEndOfLine() const { |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| switch (text_position->kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| NOTREACHED(); |
| return false; |
| case AXPositionKind::TEXT_POSITION: |
| // Text positions on objects with no text should not be considered at |
| // end of line because the empty position may share a text offset with |
| // a non-empty text position in which case the end of line iterators |
| // must move to the line end of the non-empty content. Specified next |
| // line IDs are ignored. |
| if (!text_position->MaxTextOffset()) |
| return false; |
| |
| // If affinity has been used to specify whether the caret is at the end |
| // of a line or at the start of the next one, this should have been |
| // reflected in the leaf text position we got. In other cases, we |
| // assume that white space is being used to separate lines. |
| // |
| // We don't treat a position that is at the start of white space that is |
| // on a line by itself as being at the end of the line. However, we do |
| // treat positions at the start of white space that end a line of text |
| // as being at the end of that line. We also treat positions at the end |
| // of white space that is on a line by itself as being at the end of |
| // that line. Note that white space that ends a line of text should be |
| // connected to that text with a "previous on line ID". |
| if (GetNextOnLineID(text_position->anchor_id_) == AXNode::kInvalidAXID) |
| return (!text_position->IsInWhiteSpace() || |
| GetPreviousOnLineID(text_position->anchor_id_) == |
| AXNode::kInvalidAXID) |
| ? text_position->AtEndOfAnchor() |
| : text_position->AtStartOfAnchor(); |
| |
| // The current anchor might be followed by a soft line break. |
| return text_position->AtEndOfAnchor() && |
| text_position->CreateNextLeafTextPosition()->AtEndOfLine(); |
| } |
| } |
| |
| // |AtStartOfParagraph| is asymmetric from |AtEndOfParagraph| because of |
| // trailing whitespace collapse rules. |
| // The start of a paragraph should be a leaf text position (or equivalent), |
| // either at the start of the document, or at the start of the next leaf text |
| // position from the one representing the end of the previous paragraph. |
| // A position |AsLeafTextPosition| is the start of a paragraph if all of the |
| // following are true : |
| // 1. The current leaf text position must be at the start of an anchor. |
| // 2. The current position is not whitespace only, unless it is also |
| // the first leaf text position within the document. |
| // 3. Either (a) the current leaf text position is the first leaf text |
| // position in the document, or (b) there are no line breaking |
| // objects between it and the previous non-whitespace leaf text |
| // position. |
| bool AtStartOfParagraph() const { |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| switch (text_position->kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| NOTREACHED(); |
| return false; |
| case AXPositionKind::TEXT_POSITION: { |
| // 1. The current leaf text position must be at the start of an anchor. |
| if (!text_position->AtStartOfAnchor()) |
| return false; |
| |
| // 2. The current position is not whitespace only, unless it is also |
| // the first leaf text position within the document. |
| if (text_position->IsInWhiteSpace()) |
| return text_position->CreatePreviousLeafTextPosition() |
| ->IsNullPosition(); |
| |
| // 3. Either (a) the current leaf text position is the first leaf text |
| // position in the document, or (b) there are no line breaking |
| // objects between it and the previous non-whitespace leaf text |
| // position. |
| // |
| // Search for the previous text position within the current paragraph, |
| // using the paragraph boundary abort predicate. |
| // If a valid position was found, then this position cannot be |
| // the start of a paragraph. |
| // This will return a null position when an anchor movement would |
| // cross a paragraph boundary, or the start of document was reached. |
| bool crossed_potential_boundary_token = false; |
| const AbortMovePredicate abort_move_predicate = |
| base::BindRepeating(&AbortMoveAtParagraphBoundary, |
| std::ref(crossed_potential_boundary_token)); |
| auto previous_text_position = text_position->Clone(); |
| do { |
| previous_text_position = |
| previous_text_position->CreatePreviousTextAnchorPosition( |
| abort_move_predicate); |
| // If the previous position is whitespace, then continue searching |
| // until a non-whitespace leaf text position is found within the |
| // current paragraph because whitespace is supposed to be collapsed. |
| // There's a chance that |CreatePreviousTextAnchorPosition| will |
| // return whitespace that should be appended to a previous paragraph |
| // rather than separating two pieces of the current paragraph. |
| } while (previous_text_position->IsInWhiteSpace()); |
| return previous_text_position->IsNullPosition(); |
| } |
| } |
| } |
| |
| // |AtEndOfParagraph| is asymmetric from |AtStartOfParagraph| because of |
| // trailing whitespace collapse rules. |
| // The end of a paragraph should be a leaf text position (or equivalent), |
| // either at the end of the document, or at the end of the previous leaf text |
| // position from the one representing the start of the next paragraph. |
| // A position |AsLeafTextPosition| is the end of a paragraph if all of the |
| // following are true : |
| // 1. The current leaf text position must be at the end of an anchor. |
| // 2. Either (a) the current leaf text position is the last leaf text |
| // position in the document, or (b) there are no line breaking |
| // objects between it and the next leaf text position except when |
| // the next leaf text position is whitespace only since whitespace |
| // must be collapsed. |
| // 3. If there is a next leaf text position then it must not be |
| // whitespace only. |
| // 4. If there is a next leaf text position and it is not whitespace |
| // only, it must also be the start of a paragraph for the current |
| // position to be the end of a paragraph. |
| bool AtEndOfParagraph() const { |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| switch (text_position->kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| NOTREACHED(); |
| return false; |
| case AXPositionKind::TEXT_POSITION: { |
| // 1. The current leaf text position must be at the end of an anchor. |
| if (!text_position->AtEndOfAnchor()) |
| return false; |
| |
| // 2. Either (a) the current leaf text position is the last leaf text |
| // position in the document, or (b) there are no line breaking |
| // objects between it and the next leaf text position except when |
| // the next leaf text position is whitespace only since whitespace |
| // must be collapsed. |
| // |
| // Search for the next text position within the current paragraph, |
| // using the paragraph boundary abort predicate. |
| // If a null position was found, then this position must be the end of |
| // a paragraph. |
| // |CreateNextTextAnchorPosition| + |AbortMoveAtParagraphBoundary| |
| // will return a null position when an anchor movement would |
| // cross a paragraph boundary and there is no doubt that it is the end |
| // of a paragraph, or the end of document was reached. |
| // There are some fringe cases related to whitespace collapse that |
| // cannot be handled easily with only |AbortMoveAtParagraphBoundary|. |
| bool crossed_potential_boundary_token = false; |
| const AbortMovePredicate abort_move_predicate = |
| base::BindRepeating(&AbortMoveAtParagraphBoundary, |
| std::ref(crossed_potential_boundary_token)); |
| auto next_text_position = |
| text_position->CreateNextTextAnchorPosition(abort_move_predicate); |
| if (next_text_position->IsNullPosition()) |
| return true; |
| |
| // 3. If there is a next leaf text position then it must not be |
| // whitespace only. |
| if (next_text_position->IsInWhiteSpace()) |
| return false; |
| |
| // 4. If there is a next leaf text position and it is not whitespace |
| // only, it must also be the start of a paragraph for the current |
| // position to be the end of a paragraph. |
| // |
| // Consider the following example : |
| // ++{1} kStaticText "First Paragraph" |
| // ++++{2} kInlineTextBox "First Paragraph" |
| // ++{3} kStaticText "\n Second Paragraph" |
| // ++++{4} kInlineTextBox "\n" kIsLineBreakingObject |
| // ++++{5} kInlineTextBox " " |
| // ++++{6} kInlineTextBox "Second Paragraph" |
| // A position at the end of {5} is the end of a paragraph, because |
| // the first paragraph must collapse trailing whitespace and contain |
| // leaf text anchors {2, 4, 5}. The second paragraph is only {6}. |
| return next_text_position->CreatePositionAtStartOfAnchor() |
| ->AtStartOfParagraph(); |
| } |
| } |
| } |
| |
| bool AtStartOfPage() const { |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| switch (text_position->kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| NOTREACHED(); |
| return false; |
| case AXPositionKind::TEXT_POSITION: { |
| if (!text_position->AtStartOfAnchor()) |
| return false; |
| |
| // Search for the previous text position within the current page, |
| // using the page boundary abort predicate. |
| // If a valid position was found, then this position cannot be |
| // the start of a page. |
| // This will return a null position when an anchor movement would |
| // cross a page boundary, or the start of document was reached. |
| auto previous_text_position = |
| text_position->CreatePreviousTextAnchorPosition( |
| base::BindRepeating(&AbortMoveAtPageBoundary)); |
| return previous_text_position->IsNullPosition(); |
| } |
| } |
| } |
| |
| bool AtEndOfPage() const { |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| switch (text_position->kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return false; |
| case AXPositionKind::TREE_POSITION: |
| NOTREACHED(); |
| return false; |
| case AXPositionKind::TEXT_POSITION: { |
| if (!text_position->AtEndOfAnchor()) |
| return false; |
| |
| // Search for the next text position within the current page, |
| // using the page boundary abort predicate. |
| // If a valid position was found, then this position cannot be |
| // the end of a page. |
| // This will return a null position when an anchor movement would |
| // cross a page boundary, or the end of document was reached. |
| auto next_text_position = text_position->CreateNextTextAnchorPosition( |
| base::BindRepeating(&AbortMoveAtPageBoundary)); |
| return next_text_position->IsNullPosition(); |
| } |
| } |
| } |
| |
| bool AtStartOfFormat() const { |
| // Since formats are stored on text anchors, the start of a format boundary |
| // must be at the start of an anchor. |
| if (IsNullPosition() || !AtStartOfAnchor()) |
| return false; |
| |
| // Treat the first iterable node as a format boundary. |
| if (CreatePreviousLeafTreePosition()->IsNullPosition()) |
| return true; |
| |
| // Iterate over anchors until a format boundary is found. This will return a |
| // null position upon crossing a boundary. |
| auto previous_position = CreatePreviousLeafTreePosition( |
| base::BindRepeating(&AbortMoveAtFormatBoundary)); |
| return previous_position->IsNullPosition(); |
| } |
| |
| bool AtEndOfFormat() const { |
| // Since formats are stored on text anchors, the end of a format break must |
| // be at the end of an anchor. |
| if (IsNullPosition() || !AtEndOfAnchor()) |
| return false; |
| |
| // Treat the last iterable node as a format boundary |
| if (CreateNextLeafTreePosition()->IsNullPosition()) |
| return true; |
| |
| // Iterate over anchors until a format boundary is found. This will return a |
| // null position upon crossing a boundary. |
| auto next_position = CreateNextLeafTreePosition( |
| base::BindRepeating(&AbortMoveAtFormatBoundary)); |
| return next_position->IsNullPosition(); |
| } |
| |
| bool AtStartOfDocument() const { |
| if (IsNullPosition()) |
| return false; |
| return IsDocument(GetRole()) && AtStartOfAnchor(); |
| } |
| |
| bool AtEndOfDocument() const { |
| if (IsNullPosition()) |
| return false; |
| return CreateNextAnchorPosition()->IsNullPosition() && AtEndOfAnchor(); |
| } |
| |
| // This method finds the lowest common AXNodeType of |this| and |second|. |
| AXNodeType* LowestCommonAnchor(const AXPosition& second) const { |
| if (IsNullPosition() || second.IsNullPosition()) |
| return nullptr; |
| if (GetAnchor() == second.GetAnchor()) |
| return GetAnchor(); |
| |
| base::stack<AXNodeType*> our_ancestors = GetAncestorAnchors(); |
| base::stack<AXNodeType*> other_ancestors = second.GetAncestorAnchors(); |
| |
| AXNodeType* common_anchor = nullptr; |
| while (!our_ancestors.empty() && !other_ancestors.empty() && |
| our_ancestors.top() == other_ancestors.top()) { |
| common_anchor = our_ancestors.top(); |
| our_ancestors.pop(); |
| other_ancestors.pop(); |
| } |
| return common_anchor; |
| } |
| |
| // This method returns a position instead of a node because this allows us to |
| // return the corresponding text offset or child index in the ancestor that |
| // relates to the current position. |
| // Also, this method uses position instead of tree logic to traverse the tree, |
| // because positions can handle moving across multiple trees, while trees |
| // cannot. |
| AXPositionInstance LowestCommonAncestor(const AXPosition& second) const { |
| return CreateAncestorPosition(LowestCommonAnchor(second)); |
| } |
| |
| AXPositionInstance AsTreePosition() const { |
| if (IsNullPosition() || IsTreePosition()) |
| return Clone(); |
| |
| AXPositionInstance copy = Clone(); |
| DCHECK(copy); |
| DCHECK_GE(copy->text_offset_, 0); |
| if (!copy->AnchorChildCount()) { |
| const int max_text_offset = copy->MaxTextOffset(); |
| copy->child_index_ = |
| (max_text_offset != 0 && copy->text_offset_ != max_text_offset) |
| ? BEFORE_TEXT |
| : 0; |
| copy->kind_ = AXPositionKind::TREE_POSITION; |
| return copy; |
| } |
| |
| // Blink doesn't always remove all deleted whitespace at the end of a |
| // textarea even though it will have adjusted its value attribute, because |
| // the extra layout objects are invisible. Therefore, we will stop at the |
| // last child that we can reach with the current text offset and ignore any |
| // remaining children. |
| int current_offset = 0; |
| int child_index = 0; |
| for (; child_index < copy->AnchorChildCount(); ++child_index) { |
| AXPositionInstance child = copy->CreateChildPositionAt(child_index); |
| DCHECK(child); |
| int child_length = child->MaxTextOffsetInParent(); |
| if (copy->text_offset_ >= current_offset && |
| (copy->text_offset_ < (current_offset + child_length) || |
| (copy->affinity_ == ax::mojom::TextAffinity::kUpstream && |
| copy->text_offset_ == (current_offset + child_length)))) { |
| break; |
| } |
| |
| current_offset += child_length; |
| } |
| |
| copy->child_index_ = child_index; |
| copy->kind_ = AXPositionKind::TREE_POSITION; |
| return copy; |
| } |
| |
| AXPositionInstance AsTextPosition() const { |
| if (IsNullPosition() || IsTextPosition()) |
| return Clone(); |
| |
| AXPositionInstance copy = Clone(); |
| DCHECK(copy); |
| // Check if it is a "before text" position. |
| if (copy->child_index_ == BEFORE_TEXT) { |
| // "Before text" positions can only appear on leaf nodes. |
| DCHECK(!copy->AnchorChildCount()); |
| // If the current text offset is valid, we don't touch it to potentially |
| // allow converting from a text position to a tree position and back |
| // without losing information. |
| if (copy->text_offset_ < 0 || |
| (copy->text_offset_ > 0 && |
| copy->text_offset_ >= copy->MaxTextOffset())) { |
| copy->text_offset_ = 0; |
| } |
| } else if (copy->child_index_ == copy->AnchorChildCount()) { |
| copy->text_offset_ = copy->MaxTextOffset(); |
| } else { |
| DCHECK_GE(copy->child_index_, 0); |
| DCHECK_LT(copy->child_index_, copy->AnchorChildCount()); |
| int new_offset = 0; |
| for (int i = 0; i <= child_index_; ++i) { |
| AXPositionInstance child = copy->CreateChildPositionAt(i); |
| DCHECK(child); |
| // If the current text offset is valid, we don't touch it to |
| // potentially allow converting from a text position to a tree |
| // position and back without losing information. Otherwise, if the |
| // text_offset is invalid, equals to 0 or is smaller than |
| // |new_offset|, we reset it to the beginning of the current child |
| // node. |
| if (i == child_index_ && copy->text_offset_ <= new_offset) { |
| copy->text_offset_ = new_offset; |
| break; |
| } |
| |
| int child_length = child->MaxTextOffsetInParent(); |
| // Same comment as above: we don't touch the text offset if it's |
| // already valid. |
| if (i == child_index_ && |
| (copy->text_offset_ > (new_offset + child_length) || |
| // When the text offset is equal to the text's length but this is |
| // not an "after text" position. |
| (!copy->AtEndOfAnchor() && |
| copy->text_offset_ == (new_offset + child_length)))) { |
| copy->text_offset_ = new_offset; |
| break; |
| } |
| |
| new_offset += child_length; |
| } |
| } |
| |
| // Affinity should always be left as downstream. The only case when the |
| // resulting text position is at the end of the line is when we get an |
| // "after text" leaf position, but even in this case downstream is |
| // appropriate because there is no ambiguity whetehr the position is at the |
| // end of the current line vs. the start of the next line. It would always |
| // be the former. |
| copy->kind_ = AXPositionKind::TEXT_POSITION; |
| return copy; |
| } |
| |
| AXPositionInstance AsLeafTextPosition() const { |
| if (IsNullPosition() || !AnchorChildCount()) |
| return AsTextPosition(); |
| |
| // Adjust the text offset. |
| // No need to check for "before text" positions here because they are only |
| // present on leaf anchor nodes. |
| AXPositionInstance text_position = AsTextPosition(); |
| int adjusted_offset = text_position->text_offset_; |
| do { |
| AXPositionInstance child_position = |
| text_position->CreateChildPositionAt(0); |
| DCHECK(child_position); |
| |
| // If the text offset corresponds to multiple child positions because some |
| // of the children have empty text, the condition "adjusted_offset > 0" |
| // below ensures that the first child will be chosen. |
| for (int i = 1; |
| i < text_position->AnchorChildCount() && adjusted_offset > 0; ++i) { |
| const int max_text_offset_in_parent = |
| child_position->MaxTextOffsetInParent(); |
| if (adjusted_offset < max_text_offset_in_parent) { |
| break; |
| } |
| if (affinity_ == ax::mojom::TextAffinity::kUpstream && |
| adjusted_offset == max_text_offset_in_parent) { |
| // Maintain upstream affinity so that we'll be able to choose the |
| // correct leaf anchor if the text offset is right on the boundary |
| // between two leaves. |
| child_position->affinity_ = ax::mojom::TextAffinity::kUpstream; |
| break; |
| } |
| child_position = text_position->CreateChildPositionAt(i); |
| adjusted_offset -= max_text_offset_in_parent; |
| } |
| |
| text_position = std::move(child_position); |
| } while (text_position->AnchorChildCount()); |
| |
| DCHECK(text_position); |
| DCHECK(text_position->IsLeafTextPosition()); |
| text_position->text_offset_ = adjusted_offset; |
| // Leaf Text positions are always downstream since there is no ambiguity |
| // as to whether it refers to the end of the current or the start of |
| // the next line. |
| text_position->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| return text_position; |
| } |
| |
| // Searches backwards and forwards from this position until it finds the given |
| // text boundary, and creates an AXRange that spans from the former to the |
| // latter. The resulting AXRange is always a forward range: its anchor always |
| // comes before its focus in document order. The resulting AXRange is bounded |
| // by the anchor of this position, i.e. the AXBoundaryBehavior is set to |
| // StopAtAnchorBoundary. The exception is AXTextBoundary::kWebPage, where this |
| // behavior won't make sense. This behavior is based on current platform needs |
| // and might be relaxed if necessary in the future. |
| // |
| // Please note that |expand_behavior| should have no effect for |
| // AXTextBoundary::kObject and AXTextBoundary::kWebPage because the range |
| // should be the same regardless if we first move left or right. |
| AXRangeType ExpandToEnclosingTextBoundary( |
| AXTextBoundary boundary, |
| AXRangeExpandBehavior expand_behavior) const { |
| AXBoundaryBehavior boundary_behavior = |
| AXBoundaryBehavior::StopAtAnchorBoundary; |
| if (boundary == AXTextBoundary::kWebPage) |
| boundary_behavior = AXBoundaryBehavior::CrossBoundary; |
| |
| switch (expand_behavior) { |
| case AXRangeExpandBehavior::kLeftFirst: { |
| AXPositionInstance left_position = CreatePositionAtTextBoundary( |
| boundary, AXTextBoundaryDirection::kBackwards, boundary_behavior); |
| AXPositionInstance right_position = |
| left_position->CreatePositionAtTextBoundary( |
| boundary, AXTextBoundaryDirection::kForwards, |
| boundary_behavior); |
| return AXRangeType(std::move(left_position), std::move(right_position)); |
| } |
| case AXRangeExpandBehavior::kRightFirst: { |
| AXPositionInstance right_position = CreatePositionAtTextBoundary( |
| boundary, AXTextBoundaryDirection::kForwards, boundary_behavior); |
| AXPositionInstance left_position = |
| right_position->CreatePositionAtTextBoundary( |
| boundary, AXTextBoundaryDirection::kBackwards, |
| boundary_behavior); |
| return AXRangeType(std::move(left_position), std::move(right_position)); |
| } |
| } |
| } |
| |
| // Starting from this position, moves in the given direction until it finds |
| // the given text boundary, and creates a new position at that location. |
| // |
| // When a boundary has the "StartOrEnd" suffix, it means that this method will |
| // find the start boundary when moving in the backwards direction, and the end |
| // boundary when moving in the forwards direction. |
| AXPositionInstance CreatePositionAtTextBoundary( |
| AXTextBoundary boundary, |
| AXTextBoundaryDirection direction, |
| AXBoundaryBehavior boundary_behavior) const { |
| AXPositionInstance resulting_position = CreateNullPosition(); |
| switch (boundary) { |
| case AXTextBoundary::kCharacter: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousCharacterPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextCharacterPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kFormatChange: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousFormatStartPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextFormatEndPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kLineEnd: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousLineEndPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextLineEndPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kLineStart: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousLineStartPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextLineStartPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kLineStartOrEnd: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousLineStartPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextLineEndPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kObject: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = CreatePositionAtStartOfAnchor(); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreatePositionAtEndOfAnchor(); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kPageEnd: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousPageEndPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextPageEndPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kPageStart: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousPageStartPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextPageStartPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kPageStartOrEnd: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousPageStartPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextPageEndPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kParagraphEnd: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousParagraphEndPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = |
| CreateNextParagraphEndPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kParagraphStart: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousParagraphStartPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = |
| CreateNextParagraphStartPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kParagraphStartOrEnd: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousParagraphStartPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = |
| CreateNextParagraphEndPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kSentenceEnd: |
| NOTREACHED() << "Sentence boundaries are not yet supported."; |
| return CreateNullPosition(); |
| |
| case AXTextBoundary::kSentenceStart: |
| NOTREACHED() << "Sentence boundaries are not yet supported."; |
| return CreateNullPosition(); |
| |
| case AXTextBoundary::kSentenceStartOrEnd: |
| NOTREACHED() << "Sentence boundaries are not yet supported."; |
| return CreateNullPosition(); |
| |
| case AXTextBoundary::kWebPage: |
| DCHECK_EQ(boundary_behavior, AXBoundaryBehavior::CrossBoundary) |
| << "We can't reach the start of the document if we are disallowed " |
| "from crossing boundaries."; |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = CreatePositionAtStartOfDocument(); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreatePositionAtEndOfDocument(); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kWordEnd: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousWordEndPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextWordEndPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kWordStart: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousWordStartPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextWordStartPosition(boundary_behavior); |
| break; |
| } |
| break; |
| |
| case AXTextBoundary::kWordStartOrEnd: |
| switch (direction) { |
| case AXTextBoundaryDirection::kBackwards: |
| resulting_position = |
| CreatePreviousWordStartPosition(boundary_behavior); |
| break; |
| case AXTextBoundaryDirection::kForwards: |
| resulting_position = CreateNextWordEndPosition(boundary_behavior); |
| break; |
| } |
| break; |
| } |
| return resulting_position; |
| } |
| |
| AXPositionInstance CreatePositionAtStartOfAnchor() const { |
| switch (kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return CreateNullPosition(); |
| case AXPositionKind::TREE_POSITION: |
| if (!AnchorChildCount()) { |
| return CreateTreePosition(tree_id_, anchor_id_, BEFORE_TEXT); |
| } |
| return CreateTreePosition(tree_id_, anchor_id_, 0 /* child_index */); |
| case AXPositionKind::TEXT_POSITION: |
| return CreateTextPosition(tree_id_, anchor_id_, 0 /* text_offset */, |
| ax::mojom::TextAffinity::kDownstream); |
| } |
| return CreateNullPosition(); |
| } |
| |
| AXPositionInstance CreatePositionAtEndOfAnchor() const { |
| switch (kind_) { |
| case AXPositionKind::NULL_POSITION: |
| return CreateNullPosition(); |
| case AXPositionKind::TREE_POSITION: |
| return CreateTreePosition(tree_id_, anchor_id_, AnchorChildCount()); |
| case AXPositionKind::TEXT_POSITION: |
| return CreateTextPosition(tree_id_, anchor_id_, MaxTextOffset(), |
| ax::mojom::TextAffinity::kDownstream); |
| } |
| return CreateNullPosition(); |
| } |
| |
| AXPositionInstance CreatePositionAtStartOfDocument() const { |
| AXPositionInstance position = |
| AsTreePosition()->CreateDocumentAncestorPosition(); |
| if (!position->IsNullPosition()) { |
| position = position->CreatePositionAtStartOfAnchor(); |
| if (IsTextPosition()) |
| position = position->AsTextPosition(); |
| } |
| return position; |
| } |
| |
| AXPositionInstance CreatePositionAtEndOfDocument() const { |
| AXPositionInstance position = |
| AsTreePosition()->CreateDocumentAncestorPosition(); |
| if (!position->IsNullPosition()) { |
| while (position->AnchorChildCount()) { |
| position = |
| position->CreateChildPositionAt(position->AnchorChildCount() - 1); |
| } |
| position = position->CreatePositionAtEndOfAnchor(); |
| if (IsTextPosition()) |
| position = position->AsTextPosition(); |
| } |
| return position; |
| } |
| |
| AXPositionInstance CreateChildPositionAt(int child_index) const { |
| if (IsNullPosition()) |
| return CreateNullPosition(); |
| |
| if (child_index < 0 || child_index >= AnchorChildCount()) |
| return CreateNullPosition(); |
| |
| AXTreeID tree_id = AXTreeIDUnknown(); |
| AXNode::AXID child_id = AXNode::kInvalidAXID; |
| AnchorChild(child_index, &tree_id, &child_id); |
| DCHECK_NE(tree_id, AXTreeIDUnknown()); |
| DCHECK_NE(child_id, AXNode::kInvalidAXID); |
| switch (kind_) { |
| case AXPositionKind::NULL_POSITION: |
| NOTREACHED(); |
| return CreateNullPosition(); |
| case AXPositionKind::TREE_POSITION: { |
| AXPositionInstance child_position = |
| CreateTreePosition(tree_id, child_id, 0 /* child_index */); |
| // If the child's anchor is a leaf node, make this a "before text" |
| // position. |
| if (!child_position->AnchorChildCount()) |
| child_position->child_index_ = BEFORE_TEXT; |
| return child_position; |
| } |
| case AXPositionKind::TEXT_POSITION: |
| return CreateTextPosition(tree_id, child_id, 0 /* text_offset */, |
| ax::mojom::TextAffinity::kDownstream); |
| } |
| |
| return CreateNullPosition(); |
| } |
| |
| AXPositionInstance CreateParentPosition() const { |
| if (IsNullPosition()) |
| return CreateNullPosition(); |
| |
| AXTreeID tree_id = AXTreeIDUnknown(); |
| AXNode::AXID parent_id = AXNode::kInvalidAXID; |
| AnchorParent(&tree_id, &parent_id); |
| if (tree_id == AXTreeIDUnknown() || parent_id == AXNode::kInvalidAXID) |
| return CreateNullPosition(); |
| |
| switch (kind_) { |
| case AXPositionKind::NULL_POSITION: |
| NOTREACHED(); |
| return CreateNullPosition(); |
| case AXPositionKind::TREE_POSITION: |
| return CreateTreePosition(tree_id, parent_id, AnchorIndexInParent()); |
| case AXPositionKind::TEXT_POSITION: { |
| // If our parent contains all our text, we need to maintain the affinity |
| // and the text offset. Otherwise, we return a position that is either |
| // before or after the child. We always recompute the affinity when the |
| // position is after the child. |
| // Recomputing the affinity is important because even though a text |
| // position might unambiguously be at the end of a line, its parent |
| // position might be the same as the parent position of the position |
| // representing the start of the next line. |
| const int max_text_offset = MaxTextOffset(); |
| const int max_text_offset_in_parent = |
| IsEmbeddedObjectInParent() ? 1 : max_text_offset; |
| int parent_offset = AnchorTextOffsetInParent(); |
| ax::mojom::TextAffinity parent_affinity = affinity_; |
| if (max_text_offset == max_text_offset_in_parent) { |
| parent_offset += text_offset_; |
| } else if (text_offset_ > 0) { |
| parent_offset += max_text_offset_in_parent; |
| parent_affinity = ax::mojom::TextAffinity::kDownstream; |
| } |
| |
| AXPositionInstance parent_position = CreateTextPosition( |
| tree_id, parent_id, parent_offset, parent_affinity); |
| if (parent_position->IsNullPosition()) { |
| // Workaround: When the autofill feature populates a text field, it |
| // doesn't immediately update its value, which causes the text inside |
| // the user-agent shadow DOM to be different than the text in the text |
| // field itself. As a result, the parent_offset calculated above might |
| // appear to be temporarily invalid. |
| // TODO(nektar): Fix this better by ensuring that the text field's |
| // hypertext is always kept up to date. |
| parent_position = |
| CreateTextPosition(tree_id, parent_id, 0 /* text_offset */, |
| ax::mojom::TextAffinity::kDownstream); |
| } |
| |
| // We check if the parent position has introduced ambiguity as to |
| // whether it refers to the end of the current or the start of the next |
| // line. We do this check by creating the parent position and testing if |
| // it is erroneously at the start of the next line. We could not have |
| // checked if the child was at the end of the line, because our line end |
| // testing logic takes into account line breaks, which don't apply in |
| // this situation. |
| if (text_offset_ == max_text_offset && parent_position->AtStartOfLine()) |
| parent_position->affinity_ = ax::mojom::TextAffinity::kUpstream; |
| return parent_position; |
| } |
| } |
| |
| return CreateNullPosition(); |
| } |
| |
| // Creates a tree position using the next text-only node as its anchor. |
| // Assumes that text-only nodes are leaf nodes. |
| AXPositionInstance CreateNextLeafTreePosition() const { |
| return CreateNextLeafTreePosition( |
| base::BindRepeating(&DefaultAbortMovePredicate)); |
| } |
| |
| // Creates a tree position using the previous text-only node as its anchor. |
| // Assumes that text-only nodes are leaf nodes. |
| AXPositionInstance CreatePreviousLeafTreePosition() const { |
| return CreatePreviousLeafTreePosition( |
| base::BindRepeating(&DefaultAbortMovePredicate)); |
| } |
| |
| // Creates a text position using the next text-only node as its anchor. |
| // Assumes that text-only nodes are leaf nodes. |
| AXPositionInstance CreateNextLeafTextPosition() const { |
| return CreateNextTextAnchorPosition( |
| base::BindRepeating(&DefaultAbortMovePredicate)); |
| } |
| |
| // Creates a text position using the previous text-only node as its anchor. |
| // Assumes that text-only nodes are leaf nodes. |
| AXPositionInstance CreatePreviousLeafTextPosition() const { |
| return CreatePreviousTextAnchorPosition( |
| base::BindRepeating(&DefaultAbortMovePredicate)); |
| } |
| |
| // Returns a text position located right before the next character (from this |
| // position) in the tree's text representation, following these conditions: |
| // |
| // - If this position is at the end of its anchor, normalize it to the start |
| // of the next text anchor, regardless of the position's affinity. |
| // Both text positions are equal when compared, but we consider the start of |
| // an anchor to be a position BEFORE its first character and the end of the |
| // previous to be AFTER its last character. |
| // |
| // - Skip any empty text anchors; they're "invisible" to the text |
| // representation and the next character could be ahead. |
| // |
| // - Return a null position if there is no next character forward. |
| // |
| // If possible, return a position anchored at the current position's anchor; |
| // this is necessary because we don't want to return any position that might |
| // be located in the shadow DOM or in a position anchored at a node that is |
| // not visible to a specific platform's APIs. |
| AXPositionInstance AsPositionBeforeCharacter() const { |
| AXPositionInstance text_position = AsTextPosition(); |
| if (!text_position->AtEndOfAnchor() && !text_position->IsIgnored()) |
| return text_position; |
| |
| AXPositionInstance tree_position = CreateNextLeafTreePosition(); |
| while (!tree_position->MaxTextOffset() || tree_position->IsIgnored()) |
| tree_position = tree_position->CreateNextLeafTreePosition(); |
| return tree_position->AsTextPosition(); |
| } |
| |
| // Returns a text position located right after the previous character (from |
| // this position) in the tree's text representation. |
| // See `AsPositionBeforeCharacter`, as this is its "reversed" version. |
| AXPositionInstance AsPositionAfterCharacter() const { |
| AXPositionInstance text_position = AsTextPosition(); |
| if (!text_position->AtStartOfAnchor() && !text_position->IsIgnored()) |
| return text_position; |
| |
| AXPositionInstance tree_position = CreatePreviousLeafTreePosition(); |
| while (!tree_position->MaxTextOffset() || tree_position->IsIgnored()) |
| tree_position = tree_position->CreatePreviousLeafTreePosition(); |
| return tree_position->CreatePositionAtEndOfAnchor()->AsTextPosition(); |
| } |
| |
| AXPositionInstance CreateNextCharacterPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| DCHECK_NE(boundary_behavior, AXBoundaryBehavior::StopIfAlreadyAtBoundary) |
| << "StopIfAlreadyAtBoundary is unreasonable for character boundaries."; |
| if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary && |
| AtEndOfAnchor()) { |
| return Clone(); |
| } |
| |
| const bool was_tree_position = IsTreePosition(); |
| AXPositionInstance text_position = AsPositionBeforeCharacter(); |
| |
| // There is no next character position. |
| if (text_position->IsNullPosition()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary) |
| text_position = Clone(); |
| return text_position; |
| } |
| |
| ++text_position->text_offset_; |
| DCHECK_LE(text_position->text_offset_, text_position->MaxTextOffset()); |
| // Even if the position's affinity was upstream, moving to the next |
| // character should inevitably reset it to downstream. |
| text_position->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| |
| if (was_tree_position) |
| return text_position->AsTreePosition(); |
| return text_position; |
| } |
| |
| AXPositionInstance CreatePreviousCharacterPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| DCHECK_NE(boundary_behavior, AXBoundaryBehavior::StopIfAlreadyAtBoundary) |
| << "StopIfAlreadyAtBoundary is unreasonable for character boundaries."; |
| if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary && |
| AtStartOfAnchor()) { |
| return Clone(); |
| } |
| |
| const bool was_tree_position = IsTreePosition(); |
| AXPositionInstance text_position = AsPositionAfterCharacter(); |
| |
| // There is no previous character position. |
| if (text_position->IsNullPosition()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary) |
| text_position = Clone(); |
| return text_position; |
| } |
| |
| --text_position->text_offset_; |
| DCHECK_GE(text_position->text_offset_, 0); |
| // Even if the moved position is at the beginning of the line, the |
| // affinity is defaulted to downstream for simplicity. |
| text_position->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| |
| if (was_tree_position) |
| return text_position->AsTreePosition(); |
| return text_position; |
| } |
| |
| AXPositionInstance CreateNextWordStartPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| const bool was_tree_position = IsTreePosition(); |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| if (text_position->IsNullPosition()) |
| return text_position; |
| |
| if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| text_position->AtStartOfWord()) { |
| AXPositionInstance clone = Clone(); |
| clone->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| return clone; |
| } |
| |
| std::vector<int32_t> word_starts = text_position->GetWordStartOffsets(); |
| auto iterator = |
| std::upper_bound(word_starts.begin(), word_starts.end(), |
| static_cast<int32_t>(text_position->text_offset_)); |
| do { |
| if (iterator == word_starts.end()) { |
| bool at_last_anchor_boundary = false; |
| |
| // Ignore any nodes with no text or no word boundaries. |
| do { |
| AXPositionInstance next_position = |
| text_position->CreateNextLeafTextPosition(); |
| |
| if (next_position->IsNullPosition()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) |
| return CreatePositionAtEndOfAnchor(); |
| if (boundary_behavior == |
| AXBoundaryBehavior::StopAtLastAnchorBoundary) { |
| // We can't simply return the following position; after breaking |
| // both loops we'll try to do some adjustments to text_position. |
| text_position = text_position->CreatePositionAtEndOfAnchor(); |
| at_last_anchor_boundary = true; |
| break; |
| } |
| return next_position; |
| } |
| |
| text_position = std::move(next_position); |
| } while (!text_position->MaxTextOffset() || |
| text_position->GetWordStartOffsets().empty() || |
| (text_position->IsIgnored())); |
| |
| if (at_last_anchor_boundary) |
| break; |
| |
| word_starts = text_position->GetWordStartOffsets(); |
| DCHECK(!word_starts.empty()); |
| iterator = |
| std::upper_bound(word_starts.begin(), word_starts.end(), |
| static_cast<int32_t>(text_position->text_offset_)); |
| text_position->text_offset_ = static_cast<int>(word_starts[0]); |
| } else { |
| text_position->text_offset_ = static_cast<int>(*iterator); |
| text_position->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| iterator++; |
| } |
| |
| // Continue searching for the next word start until the next logical text |
| // position is reached. |
| } while (boundary_behavior != AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| *this == *text_position); |
| |
| // If the word boundary is in the same subtree, return a position rooted at |
| // this position's anchor. This is necessary because we don't want to return |
| // a position that might be in the shadow DOM when this position is not. |
| const AXNodeType* common_anchor = text_position->LowestCommonAnchor(*this); |
| if (GetAnchor() == common_anchor) { |
| text_position = text_position->CreateAncestorPosition(common_anchor); |
| } else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) { |
| return CreatePositionAtEndOfAnchor(); |
| } |
| |
| if (was_tree_position) |
| text_position = text_position->AsTreePosition(); |
| return text_position; |
| } |
| |
| AXPositionInstance CreatePreviousWordStartPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| const bool was_tree_position = IsTreePosition(); |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| if (text_position->IsNullPosition()) |
| return text_position; |
| |
| if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| text_position->AtStartOfWord()) { |
| AXPositionInstance clone = Clone(); |
| clone->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| return clone; |
| } |
| |
| std::vector<int32_t> word_starts = text_position->GetWordStartOffsets(); |
| auto iterator = |
| std::lower_bound(word_starts.begin(), word_starts.end(), |
| static_cast<int32_t>(text_position->text_offset_)); |
| do { |
| if (word_starts.empty() || iterator == word_starts.begin()) { |
| bool at_last_anchor_boundary = false; |
| |
| // Ignore any nodes with no text or no word boundaries. |
| do { |
| AXPositionInstance previous_position = |
| text_position->CreatePreviousLeafTextPosition() |
| ->CreatePositionAtEndOfAnchor(); |
| |
| if (previous_position->IsNullPosition()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) |
| return CreatePositionAtStartOfAnchor(); |
| if (boundary_behavior == |
| AXBoundaryBehavior::StopAtLastAnchorBoundary) { |
| // We can't simply return the following position; after breaking |
| // both loops we'll try to do some adjustments to text_position. |
| text_position = text_position->CreatePositionAtStartOfAnchor(); |
| at_last_anchor_boundary = true; |
| break; |
| } |
| return previous_position; |
| } |
| |
| text_position = std::move(previous_position); |
| } while (!text_position->MaxTextOffset() || |
| text_position->GetWordStartOffsets().empty() || |
| text_position->IsIgnored()); |
| |
| if (at_last_anchor_boundary) |
| break; |
| |
| word_starts = text_position->GetWordStartOffsets(); |
| DCHECK(!word_starts.empty()); |
| iterator = |
| std::upper_bound(word_starts.begin(), word_starts.end(), |
| static_cast<int32_t>(text_position->text_offset_)); |
| text_position->text_offset_ = |
| static_cast<int>(*(word_starts.end() - 1)); |
| } else { |
| text_position->text_offset_ = static_cast<int>(*(--iterator)); |
| text_position->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| } |
| |
| // Continue searching for the previous word start until the next logical |
| // text position is reached. |
| } while (boundary_behavior != AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| *this == *text_position); |
| |
| // If the word boundary is in the same subtree, return a position rooted at |
| // this position's anchor. This is necessary because we don't want to return |
| // a position that might be in the shadow DOM when this position is not. |
| const AXNodeType* common_anchor = text_position->LowestCommonAnchor(*this); |
| if (GetAnchor() == common_anchor) { |
| text_position = text_position->CreateAncestorPosition(common_anchor); |
| } else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) { |
| return CreatePositionAtStartOfAnchor(); |
| } |
| |
| if (was_tree_position) |
| text_position = text_position->AsTreePosition(); |
| return text_position; |
| } |
| |
| // Word end positions are one past the last character of the word. |
| AXPositionInstance CreateNextWordEndPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| const bool was_tree_position = IsTreePosition(); |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| if (text_position->IsNullPosition()) |
| return text_position; |
| |
| if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| text_position->AtEndOfWord()) { |
| AXPositionInstance clone = Clone(); |
| // If there is no ambiguity as to whether the position is at the end of |
| // the current line or the start of the next line, affinity should be |
| // reset in order to get consistent output from this function regardless |
| // of input affinity. |
| clone->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| if (clone->AtStartOfLine()) |
| clone->affinity_ = ax::mojom::TextAffinity::kUpstream; |
| return clone; |
| } |
| |
| std::vector<int32_t> word_ends = text_position->GetWordEndOffsets(); |
| auto iterator = |
| std::upper_bound(word_ends.begin(), word_ends.end(), |
| static_cast<int32_t>(text_position->text_offset_)); |
| do { |
| if (iterator == word_ends.end()) { |
| bool at_last_anchor_boundary = false; |
| |
| // Ignore any nodes with no text or no word boundaries. |
| do { |
| AXPositionInstance next_position = |
| text_position->CreateNextLeafTextPosition(); |
| |
| if (next_position->IsNullPosition()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) |
| return CreatePositionAtEndOfAnchor(); |
| if (boundary_behavior == |
| AXBoundaryBehavior::StopAtLastAnchorBoundary) { |
| // We can't simply return the following position; after breaking |
| // both loops we'll try to do some adjustments to text_position. |
| text_position = text_position->CreatePositionAtEndOfAnchor(); |
| at_last_anchor_boundary = true; |
| break; |
| } |
| return next_position; |
| } |
| |
| text_position = std::move(next_position); |
| } while (!text_position->MaxTextOffset() || |
| text_position->GetWordEndOffsets().empty() || |
| text_position->IsIgnored()); |
| |
| if (at_last_anchor_boundary) |
| break; |
| |
| word_ends = text_position->GetWordEndOffsets(); |
| DCHECK(!word_ends.empty()); |
| iterator = |
| std::upper_bound(word_ends.begin(), word_ends.end(), |
| static_cast<int32_t>(text_position->text_offset_)); |
| text_position->text_offset_ = static_cast<int>(word_ends[0]); |
| } else { |
| text_position->text_offset_ = static_cast<int>(*iterator); |
| text_position->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| iterator++; |
| } |
| |
| // Continue searching for the next word end until the next logical text |
| // position is reached. |
| } while (boundary_behavior != AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| *this == *text_position); |
| |
| // If the word boundary is in the same subtree, return a position rooted at |
| // this position's anchor. This is necessary because we don't want to return |
| // a position that might be in the shadow DOM when this position is not. |
| const AXNodeType* common_anchor = text_position->LowestCommonAnchor(*this); |
| if (GetAnchor() == common_anchor) { |
| text_position = text_position->CreateAncestorPosition(common_anchor); |
| } else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) { |
| return CreatePositionAtEndOfAnchor(); |
| } |
| |
| if (was_tree_position) |
| text_position = text_position->AsTreePosition(); |
| return text_position; |
| } |
| |
| // Word end positions are one past the last character of the word. |
| AXPositionInstance CreatePreviousWordEndPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| const bool was_tree_position = IsTreePosition(); |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| if (text_position->IsNullPosition()) |
| return text_position; |
| |
| if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| text_position->AtEndOfWord()) { |
| AXPositionInstance clone = Clone(); |
| // If there is no ambiguity as to whether the position is at the end of |
| // the current line or the start of the next line, affinity should be |
| // reset in order to get consistent output from this function regardless |
| // of input affinity. |
| clone->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| if (clone->AtStartOfLine()) |
| clone->affinity_ = ax::mojom::TextAffinity::kUpstream; |
| return clone; |
| } |
| |
| std::vector<int32_t> word_ends = text_position->GetWordEndOffsets(); |
| auto iterator = |
| std::lower_bound(word_ends.begin(), word_ends.end(), |
| static_cast<int32_t>(text_position->text_offset_)); |
| do { |
| if (word_ends.empty() || iterator == word_ends.begin()) { |
| bool at_last_anchor_boundary = false; |
| |
| // Ignore any nodes with no text or no word boundaries. |
| do { |
| AXPositionInstance previous_position = |
| text_position->CreatePreviousLeafTextPosition() |
| ->CreatePositionAtEndOfAnchor(); |
| |
| if (previous_position->IsNullPosition()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) |
| return CreatePositionAtStartOfAnchor(); |
| if (boundary_behavior == |
| AXBoundaryBehavior::StopAtLastAnchorBoundary) { |
| // We can't simply return the following position; after breaking |
| // both loops we'll try to do some adjustments to text_position. |
| text_position = text_position->CreatePositionAtStartOfAnchor(); |
| at_last_anchor_boundary = true; |
| break; |
| } |
| return previous_position; |
| } |
| |
| text_position = std::move(previous_position); |
| } while (!text_position->MaxTextOffset() || |
| text_position->GetWordStartOffsets().empty() || |
| text_position->IsIgnored()); |
| |
| if (at_last_anchor_boundary) |
| break; |
| |
| word_ends = text_position->GetWordEndOffsets(); |
| DCHECK(!word_ends.empty()); |
| iterator = |
| std::lower_bound(word_ends.begin(), word_ends.end(), |
| static_cast<int32_t>(text_position->text_offset_)); |
| text_position->text_offset_ = static_cast<int>(*(word_ends.end() - 1)); |
| } else { |
| text_position->text_offset_ = static_cast<int>(*(--iterator)); |
| text_position->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| } |
| |
| // Continue searching for the previous word end until the next logical |
| // text position is reached. |
| } while (boundary_behavior != AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| *this == *text_position); |
| |
| // If the word boundary is in the same subtree, return a position rooted at |
| // this position's anchor. This is necessary because we don't want to return |
| // a position that might be in the shadow DOM when this position is not. |
| const AXNodeType* common_anchor = text_position->LowestCommonAnchor(*this); |
| if (GetAnchor() == common_anchor) { |
| text_position = text_position->CreateAncestorPosition(common_anchor); |
| } else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) { |
| return CreatePositionAtStartOfAnchor(); |
| } |
| |
| if (was_tree_position) |
| text_position = text_position->AsTreePosition(); |
| return text_position; |
| } |
| |
| AXPositionInstance CreateNextLineStartPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryStartPosition( |
| boundary_behavior, AXTextBoundaryDirection::kForwards, |
| base::BindRepeating(&AtStartOfLinePredicate), |
| base::BindRepeating(&AtEndOfLinePredicate)); |
| } |
| |
| AXPositionInstance CreatePreviousLineStartPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryStartPosition( |
| boundary_behavior, AXTextBoundaryDirection::kBackwards, |
| base::BindRepeating(&AtStartOfLinePredicate), |
| base::BindRepeating(&AtEndOfLinePredicate)); |
| } |
| |
| // Line end positions are one past the last character of the line, excluding |
| // any white space or newline characters that separate the lines. |
| AXPositionInstance CreateNextLineEndPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryEndPosition( |
| boundary_behavior, AXTextBoundaryDirection::kForwards, |
| base::BindRepeating(&AtStartOfLinePredicate), |
| base::BindRepeating(&AtEndOfLinePredicate)); |
| } |
| |
| // Line end positions are one past the last character of the line, excluding |
| // any white space or newline characters separating the lines. |
| AXPositionInstance CreatePreviousLineEndPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryEndPosition( |
| boundary_behavior, AXTextBoundaryDirection::kBackwards, |
| base::BindRepeating(&AtStartOfLinePredicate), |
| base::BindRepeating(&AtEndOfLinePredicate)); |
| } |
| |
| AXPositionInstance CreatePreviousFormatStartPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| if (IsNullPosition()) |
| return Clone(); |
| |
| // AtStartOfFormat() always returns true if we are at the first iterable |
| // position, i.e. CreatePreviousLeafTreePosition()->IsNullPosition(). |
| if (AtStartOfFormat()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary || |
| (boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary && |
| CreatePreviousLeafTreePosition()->IsNullPosition())) { |
| AXPositionInstance clone = Clone(); |
| // In order to make equality checks simpler, affinity should be reset so |
| // that we would get consistent output from this function regardless of |
| // input affinity. |
| clone->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| return clone; |
| } else if (boundary_behavior == AXBoundaryBehavior::CrossBoundary && |
| CreatePreviousLeafTreePosition()->IsNullPosition()) { |
| // If we're at a format boundary and there are no more text positions |
| // to traverse, return a null position for cross-boundary moves. |
| return CreateNullPosition(); |
| } |
| } |
| |
| const bool was_text_position = IsTextPosition(); |
| AXPositionInstance tree_position = |
| AsTreePosition()->CreatePositionAtStartOfAnchor(); |
| AXPositionInstance previous_tree_position = |
| tree_position->CreatePreviousLeafTreePosition(); |
| |
| // If moving to the start of the current anchor hasn't changed our position |
| // from the original position, we need to test the previous leaf tree |
| // position. |
| if (AtStartOfAnchor() && |
| boundary_behavior != AXBoundaryBehavior::StopIfAlreadyAtBoundary) { |
| tree_position = std::move(previous_tree_position); |
| previous_tree_position = tree_position->CreatePreviousLeafTreePosition(); |
| } |
| |
| // The first position in the document is also a format start boundary, so we |
| // should not return NullPosition unless we started from that location. |
| while (!previous_tree_position->IsNullPosition() && |
| !tree_position->AtStartOfFormat()) { |
| tree_position = std::move(previous_tree_position); |
| previous_tree_position = tree_position->CreatePreviousLeafTreePosition(); |
| } |
| |
| // If the format boundary is in the same subtree, return a position rooted |
| // at the current position. |
| // This is necessary because we don't want to return any position that might |
| // be in the shadow DOM if the original position was not. |
| const AXNodeType* common_anchor = tree_position->LowestCommonAnchor(*this); |
| if (GetAnchor() == common_anchor) { |
| tree_position = tree_position->CreateAncestorPosition(common_anchor); |
| } else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) { |
| return CreatePositionAtStartOfAnchor(); |
| } |
| |
| if (was_text_position) |
| tree_position = tree_position->AsTextPosition(); |
| return tree_position; |
| } |
| |
| AXPositionInstance CreateNextFormatEndPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| if (IsNullPosition()) |
| return Clone(); |
| |
| // AtEndOfFormat() always returns true if we are at the last iterable |
| // position, i.e. CreateNextLeafTreePosition()->IsNullPosition(). |
| if (AtEndOfFormat()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary || |
| (boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary && |
| CreateNextLeafTreePosition()->IsNullPosition())) { |
| AXPositionInstance clone = Clone(); |
| // In order to make equality checks simpler, affinity should be reset so |
| // that we would get consistent output from this function regardless of |
| // input affinity. |
| clone->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| return clone; |
| } else if (boundary_behavior == AXBoundaryBehavior::CrossBoundary && |
| CreateNextLeafTreePosition()->IsNullPosition()) { |
| // If we're at a format boundary and there are no more text positions |
| // to traverse, return a null position for cross-boundary moves. |
| return CreateNullPosition(); |
| } |
| } |
| |
| const bool was_text_position = IsTextPosition(); |
| AXPositionInstance tree_position = |
| AsTreePosition()->CreatePositionAtEndOfAnchor(); |
| AXPositionInstance next_tree_position = |
| tree_position->CreateNextLeafTreePosition() |
| ->CreatePositionAtEndOfAnchor(); |
| |
| // If moving to the end of the current anchor hasn't changed our original |
| // position, we need to test the next leaf tree position. |
| if (AtEndOfAnchor() && |
| boundary_behavior != AXBoundaryBehavior::StopIfAlreadyAtBoundary) { |
| tree_position = std::move(next_tree_position); |
| next_tree_position = tree_position->CreateNextLeafTreePosition() |
| ->CreatePositionAtEndOfAnchor(); |
| } |
| |
| // The last position in the document is also a format end boundary, so we |
| // should not return NullPosition unless we started from that location. |
| while (!next_tree_position->IsNullPosition() && |
| !tree_position->AtEndOfFormat()) { |
| tree_position = std::move(next_tree_position); |
| next_tree_position = tree_position->CreateNextLeafTreePosition() |
| ->CreatePositionAtEndOfAnchor(); |
| } |
| |
| // If the format boundary is in the same subtree, return a position |
| // rooted at the current position. |
| // This is necessary because we don't want to return any position that might |
| // be in the shadow DOM if the original position was not. |
| const AXNodeType* common_anchor = tree_position->LowestCommonAnchor(*this); |
| if (GetAnchor() == common_anchor) { |
| tree_position = tree_position->CreateAncestorPosition(common_anchor); |
| } else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) { |
| return CreatePositionAtEndOfAnchor(); |
| } |
| |
| if (was_text_position) |
| tree_position = tree_position->AsTextPosition(); |
| return tree_position; |
| } |
| |
| AXPositionInstance CreateNextParagraphStartPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryStartPosition( |
| boundary_behavior, AXTextBoundaryDirection::kForwards, |
| base::BindRepeating(&AtStartOfParagraphPredicate), |
| base::BindRepeating(&AtEndOfParagraphPredicate)); |
| } |
| |
| AXPositionInstance CreatePreviousParagraphStartPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryStartPosition( |
| boundary_behavior, AXTextBoundaryDirection::kBackwards, |
| base::BindRepeating(&AtStartOfParagraphPredicate), |
| base::BindRepeating(&AtEndOfParagraphPredicate)); |
| } |
| |
| AXPositionInstance CreateNextParagraphEndPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryEndPosition( |
| boundary_behavior, AXTextBoundaryDirection::kForwards, |
| base::BindRepeating(&AtStartOfParagraphPredicate), |
| base::BindRepeating(&AtEndOfParagraphPredicate)); |
| } |
| |
| AXPositionInstance CreatePreviousParagraphEndPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| AXPositionInstance previous_position = CreateBoundaryEndPosition( |
| boundary_behavior, AXTextBoundaryDirection::kBackwards, |
| base::BindRepeating(&AtStartOfParagraphPredicate), |
| base::BindRepeating(&AtEndOfParagraphPredicate)); |
| if (boundary_behavior == AXBoundaryBehavior::CrossBoundary || |
| boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary) { |
| // This is asymmetric with CreateNextParagraphEndPosition due to |
| // asymmetries in text anchor movement. Consider: |
| // |
| // ++1 rootWebArea |
| // ++++2 staticText name="FIRST" |
| // ++++3 genericContainer isLineBreakingObject=true |
| // ++++++4 genericContainer isLineBreakingObject=true |
| // ++++++5 staticText name="SECOND" |
| // |
| // Node 2 offset 5 FIRST<> is a paragraph end since node 3 is a line- |
| // breaking object that's not collapsible (since it's not a leaf). When |
| // looking for the next text anchor position from there, we advance to |
| // sibling node 3, then since that node has descendants, we convert to a |
| // tree position to find the leaf node that maps to "node 3 offset 0". |
| // Since node 4 has no text, we skip it and land on node 5. We end up at |
| // node 5 offset 6 SECOND<> as our next paragraph end. |
| // |
| // The set of paragraph ends should be consistent when moving in the |
| // reverse direction. But starting from node 5 offset 6, the previous text |
| // anchor position is previous sibling node 4. We'll consider that a |
| // paragraph end since it's a leaf line-breaking object and stop. |
| // |
| // Essentially, we have two consecutive line-breaking objects, each of |
| // which stops movement in the "outward" direction, for different reasons. |
| // |
| // We handle this by looking back one more step after finding a candidate |
| // for previous paragraph end, then testing a forward step from the look- |
| // back position. That will land us on the candidate position if it's a |
| // valid paragraph boundary. |
| // |
| while (!previous_position->IsNullPosition()) { |
| AXPositionInstance look_back_position = |
| previous_position->AsLeafTextPosition() |
| ->CreatePreviousLeafTextPosition() |
| ->CreatePositionAtEndOfAnchor(); |
| if (look_back_position->IsNullPosition()) { |
| // Nowhere to look back to, so our candidate must be a valid paragraph |
| // boundary. |
| break; |
| } |
| AXPositionInstance forward_step_position = |
| look_back_position->CreateNextLeafTextPosition() |
| ->CreatePositionAtEndOfAnchor(); |
| if (*forward_step_position == *previous_position) |
| break; |
| |
| previous_position = previous_position->CreateBoundaryEndPosition( |
| boundary_behavior, AXTextBoundaryDirection::kBackwards, |
| base::BindRepeating(&AtStartOfParagraphPredicate), |
| base::BindRepeating(&AtEndOfParagraphPredicate)); |
| } |
| } |
| |
| return previous_position; |
| } |
| |
| AXPositionInstance CreateNextPageStartPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryStartPosition( |
| boundary_behavior, AXTextBoundaryDirection::kForwards, |
| base::BindRepeating(&AtStartOfPagePredicate), |
| base::BindRepeating(&AtEndOfPagePredicate)); |
| } |
| |
| AXPositionInstance CreatePreviousPageStartPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryStartPosition( |
| boundary_behavior, AXTextBoundaryDirection::kBackwards, |
| base::BindRepeating(&AtStartOfPagePredicate), |
| base::BindRepeating(&AtEndOfPagePredicate)); |
| } |
| |
| AXPositionInstance CreateNextPageEndPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryEndPosition( |
| boundary_behavior, AXTextBoundaryDirection::kForwards, |
| base::BindRepeating(&AtStartOfPagePredicate), |
| base::BindRepeating(&AtEndOfPagePredicate)); |
| } |
| |
| AXPositionInstance CreatePreviousPageEndPosition( |
| AXBoundaryBehavior boundary_behavior) const { |
| return CreateBoundaryEndPosition( |
| boundary_behavior, AXTextBoundaryDirection::kBackwards, |
| base::BindRepeating(&AtStartOfPagePredicate), |
| base::BindRepeating(&AtEndOfPagePredicate)); |
| } |
| |
| AXPositionInstance CreateBoundaryStartPosition( |
| AXBoundaryBehavior boundary_behavior, |
| AXTextBoundaryDirection boundary_direction, |
| BoundaryConditionPredicate at_start_condition, |
| BoundaryConditionPredicate at_end_condition) const { |
| const bool was_tree_position = IsTreePosition(); |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| if (text_position->IsNullPosition()) |
| return text_position; |
| |
| if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| at_start_condition.Run(text_position)) { |
| AXPositionInstance clone = Clone(); |
| clone->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| return clone; |
| } |
| |
| do { |
| AXPositionInstance next_position; |
| if (boundary_direction == AXTextBoundaryDirection::kForwards) |
| next_position = text_position->CreateNextLeafTextPosition(); |
| else |
| next_position = text_position->AtStartOfAnchor() |
| ? text_position->CreatePreviousLeafTextPosition() |
| : text_position->CreatePositionAtStartOfAnchor(); |
| |
| if (next_position->IsNullPosition()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) |
| return (boundary_direction == AXTextBoundaryDirection::kForwards) |
| ? CreatePositionAtEndOfAnchor() |
| : CreatePositionAtStartOfAnchor(); |
| if (boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary) { |
| // We can't simply return the following position; break and after this |
| // loop we'll try to do some adjustments to text_position. |
| text_position = |
| (boundary_direction == AXTextBoundaryDirection::kForwards) |
| ? text_position->CreatePositionAtEndOfAnchor() |
| : text_position->CreatePositionAtStartOfAnchor(); |
| break; |
| } |
| return next_position; |
| } |
| |
| // Continue searching for the next boundary end in the specified direction |
| // until the next logical text position is reached. |
| text_position = std::move(next_position); |
| } while ( |
| !at_start_condition.Run(text_position) || |
| (boundary_behavior != AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| *this == *text_position)); |
| |
| // If the boundary is in the same subtree, return a position rooted at this |
| // position's anchor. This is necessary because we don't want to return a |
| // position that might be in the shadow DOM when this position is not. |
| const AXNodeType* common_anchor = text_position->LowestCommonAnchor(*this); |
| if (GetAnchor() == common_anchor) { |
| text_position = text_position->CreateAncestorPosition(common_anchor); |
| } else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) { |
| return (boundary_direction == AXTextBoundaryDirection::kForwards) |
| ? CreatePositionAtEndOfAnchor() |
| : CreatePositionAtStartOfAnchor(); |
| } |
| |
| if (was_tree_position) |
| text_position = text_position->AsTreePosition(); |
| return text_position; |
| } |
| |
| AXPositionInstance CreateBoundaryEndPosition( |
| AXBoundaryBehavior boundary_behavior, |
| AXTextBoundaryDirection boundary_direction, |
| BoundaryConditionPredicate at_start_condition, |
| BoundaryConditionPredicate at_end_condition) const { |
| const bool was_tree_position = IsTreePosition(); |
| AXPositionInstance text_position = AsLeafTextPosition(); |
| if (text_position->IsNullPosition()) |
| return text_position; |
| |
| if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| at_end_condition.Run(text_position)) { |
| AXPositionInstance clone = Clone(); |
| // If there is no ambiguity as to whether the position is at the end of |
| // the current boundary or the start of the next boundary, affinity should |
| // be reset in order to get consistent output from this method, regardless |
| // of input affinity. |
| clone->affinity_ = ax::mojom::TextAffinity::kDownstream; |
| if (at_start_condition.Run(clone)) |
| clone->affinity_ = ax::mojom::TextAffinity::kUpstream; |
| return clone; |
| } |
| |
| do { |
| AXPositionInstance next_position; |
| if (boundary_direction == AXTextBoundaryDirection::kForwards) |
| next_position = !text_position->AtEndOfAnchor() |
| ? text_position->CreatePositionAtEndOfAnchor() |
| : text_position->CreateNextLeafTextPosition() |
| ->CreatePositionAtEndOfAnchor(); |
| else |
| next_position = text_position->CreatePreviousLeafTextPosition() |
| ->CreatePositionAtEndOfAnchor(); |
| |
| if (next_position->IsNullPosition()) { |
| if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) |
| return (boundary_direction == AXTextBoundaryDirection::kForwards) |
| ? CreatePositionAtEndOfAnchor() |
| : CreatePositionAtStartOfAnchor(); |
| if (boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary) { |
| // We can't simply return the following position; break and after this |
| // loop we'll try to do some adjustments to text_position. |
| text_position = |
| (boundary_direction == AXTextBoundaryDirection::kForwards) |
| ? text_position->CreatePositionAtEndOfAnchor() |
| : text_position->CreatePositionAtStartOfAnchor(); |
| break; |
| } |
| return next_position; |
| } |
| |
| // Continue searching for the next boundary end in the specified direction |
| // until the next logical text position is reached. |
| text_position = std::move(next_position); |
| } while ( |
| !at_end_condition.Run(text_position) || |
| (boundary_behavior != AXBoundaryBehavior::StopIfAlreadyAtBoundary && |
| *this == *text_position)); |
| |
| // If the boundary is in the same subtree, return a position rooted at this |
| // position's anchor. This is necessary because we don't want to return a |
| // position that might be in the shadow DOM when this position is not. |
| const AXNodeType* common_anchor = text_position->LowestCommonAnchor(*this); |
| if (GetAnchor() == common_anchor) { |
| text_position = text_position->CreateAncestorPosition(common_anchor); |
| } else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) { |
| return (boundary_direction == AXTextBoundaryDirection::kForwards) |
| ? CreatePositionAtEndOfAnchor() |
| : CreatePositionAtStartOfAnchor(); |
| } |
| |
| if (was_tree_position) |
| text_position = text_position->AsTreePosition(); |
| return text_position; |
| } |
| |
| // TODO(nektar): Add sentence navigation methods. |
| |
| // Uses depth-first pre-order traversal. |
| AXPositionInstance CreateNextAnchorPosition() const { |
| return CreateNextAnchorPosition( |
| base::BindRepeating(&DefaultAbortMovePredicate)); |
| } |
| |
| // Uses depth-first pre-order traversal. |
| AXPositionInstance CreatePreviousAnchorPosition() const { |
| return CreatePreviousAnchorPosition( |
| base::BindRepeating(&DefaultAbortMovePredicate)); |
| } |
| |
| // Returns an optional integer indicating the logical order of this position |
| // compared to another position or returns an empty optional if the positions |
| // are not comparable. Any text position at the same character location is |
| // logically equivalent although they may be on different anchors or have |
| // different text offsets. Positions are not comparable when one position is |
| // null and the other is not or if the positions do not have any common |
| // ancestor. |
| // 0: if this position is logically equivalent to the other position |
| // <0: if this position is logically less than the other position |
| // >0: if this position is logically greater than the other position |
| base::Optional<int> CompareTo(const AXPosition& other) const { |
| if (this->IsNullPosition() && other.IsNullPosition()) |
| return base::Optional<int>(0); |
| if (this->IsNullPosition() || other.IsNullPosition()) |
| return base::Optional<int>(base::nullopt); |
| |
| // It is potentially costly to compute the parent position of a text |
| // position, whilst computing the parent position of a tree position is |
| // really inexpensive. In order to find the lowest common ancestor, |
| // especially if that ancestor is all the way up to the root of the tree, |
| // this will need to be done repeatedly. We avoid the performance hit by |
| // converting both positions to tree positions and only falling back to text |
| // positions if both are text positions and the lowest common ancestor is |
| // not one of their anchors. Essentially, the question we need to answer is: |
| // "When are two non equivalent positions going to have the same lowest |
| // common ancestor position when converted to tree positions?" The answer is |
| // when they are both text positions and they either have the same anchor, |
| // or one is the ancestor of the other. |
| const AXNodeType* common_anchor = this->LowestCommonAnchor(other); |
| if (!common_anchor) |
| return base::Optional<int>(base::nullopt); |
| |
| // Attempt to avoid recomputing the lowest common ancestor because we may |
| // already have its anchor in which case just find the text offset. |
| if (this->IsTextPosition() && other.IsTextPosition()) { |
| // This text position's anchor is the common ancestor of the other text |
| // position's anchor. |
| if (this->GetAnchor() == common_anchor) { |
| AXPositionInstance other_text_position = |
| other.CreateAncestorPosition(common_anchor); |
| return base::Optional<int>(this->text_offset_ - |
| other_text_position->text_offset_); |
| } |
| |
| // The other text position's anchor is the common ancestor of this text |
| // position's anchor. |
| if (other.GetAnchor() == common_anchor) { |
| AXPositionInstance this_text_position = |
| this->CreateAncestorPosition(common_anchor); |
| return base::Optional<int>(this_text_position->text_offset_ - |
| other.text_offset_); |
| } |
| |
| // All optimizations failed. Fall back to comparing text positions with |
| // the common text position ancestor. |
| AXPositionInstance this_text_position_ancestor = |
| this->CreateAncestorPosition(common_anchor); |
| AXPositionInstance other_text_position_ancestor = |
| other.CreateAncestorPosition(common_anchor); |
| DCHECK(this_text_position_ancestor->IsTextPosition()); |
| DCHECK(other_text_position_ancestor->IsTextPosition()); |
| DCHECK_EQ(common_anchor, this_text_position_ancestor->GetAnchor()); |
| DCHECK_EQ(common_anchor, other_text_position_ancestor->GetAnchor()); |
| |
| // TODO - This does not take into account |affinity_|, so we may return |
| // a false positive when comparing at the end of a line. |
| // For example : |
| // ++1 kRootWebArea |
| // ++++2 kTextField "Line 1\nLine 2" |
| // ++++++3 kStaticText "Line 1" |
| // ++++++++4 kInlineTextBox "Line 1" |
| // ++++++5 kLineBreak "\n" |
| // ++++++6 kStaticText "Line 2" |
| // ++++++++7 kInlineTextBox "Line 2" |
| // |
| // TextPosition anchor_id=5 text_offset=1 |
| // affinity=downstream annotated_text=\n<> |
| // |
| // TextPosition anchor_id=7 text_offset=0 |
| // affinity=downstream annotated_text=<L>ine 2 |
| // |
| // |LowestCommonAncestor| for both will be : |
| // TextPosition anchor_id=2 text_offset=7 |
| // ... except anchor_id=5 creates a kUpstream position, while |
| // anchor_id=7 creates a kDownstream position. |
| return base::Optional<int>(this_text_position_ancestor->text_offset_ - |
| other_text_position_ancestor->text_offset_); |
| } |
| |
| // All optimizations failed. Fall back to comparing child index with |
| // the common tree position ancestor. |
| AXPositionInstance this_tree_position_ancestor = |
| this->AsTreePosition()->CreateAncestorPosition(common_anchor); |
| AXPositionInstance other_tree_position_ancestor = |
| other.AsTreePosition()->CreateAncestorPosition(common_anchor); |
| DCHECK(this_tree_position_ancestor->IsTreePosition()); |
| DCHECK(other_tree_position_ancestor->IsTreePosition()); |
| DCHECK_EQ(common_anchor, this_tree_position_ancestor->GetAnchor()); |
| DCHECK_EQ(common_anchor, other_tree_position_ancestor->GetAnchor()); |
| |
| return base::Optional<int>(this_tree_position_ancestor->child_index() - |
| other_tree_position_ancestor->child_index()); |
| } |
| |
| // Returns the length of the text that is present inside the anchor node, |
| // including any text found in descendant text nodes. |
| virtual int MaxTextOffset() const { |
| if (IsNullPosition()) |
| return INVALID_OFFSET; |
| return static_cast<int>(GetText().length()); |
| } |
| |
| // Abstract methods. |
| |
| // Determines if the anchor containing this position is a <br> or a text |
| // object whose parent's anchor is an enclosing <br>. |
| virtual bool IsInLineBreak() const = 0; |
| |
| // Determines if the anchor containing this position is a text object. |
| virtual bool IsInTextObject() const = 0; |
| |
| // Determines if the text representation of this position's anchor contains |
| // only whitespace characters; <br> objects span a single '\n' character, so |
| // positions inside line breaks are also considered "in whitespace". |
| virtual bool IsInWhiteSpace() const = 0; |
| |
| // Returns the text that is present inside the anchor node, where the |
| // representation of text found in descendant nodes depends on the platform. |
| // For example some platforms may include descendant text while while other |
| // platforms may use a special character to represent descendant text. |
| virtual base::string16 GetText() const = 0; |
| |
| protected: |
| AXPosition() = default; |
| AXPosition(const AXPosition& other) = default; |
| virtual AXPosition& operator=(const AXPosition& other) = default; |
| |
| virtual void Initialize(AXPositionKind kind, |
| AXTreeID tree_id, |
| int32_t anchor_id, |
| int child_index, |
| int text_offset, |
| ax::mojom::TextAffinity affinity) { |
| kind_ = kind; |
| tree_id_ = tree_id; |
| anchor_id_ = anchor_id; |
| child_index_ = child_index; |
| text_offset_ = text_offset; |
| affinity_ = affinity; |
| |
| if (!GetAnchor() || kind_ == AXPositionKind::NULL_POSITION || |
| (kind_ == AXPositionKind::TREE_POSITION && |
| (child_index_ != BEFORE_TEXT && |
| (child_index_ < 0 || child_index_ > AnchorChildCount()))) || |
| (kind_ == AXPositionKind::TEXT_POSITION && |
| (text_offset_ < 0 || |
| (text_offset > 0 && text_offset_ > MaxTextOffset())))) { |
| // Reset to the null position. |
| kind_ = AXPositionKind::NULL_POSITION; |
| tree_id_ = AXTreeIDUnknown(); |
| anchor_id_ = AXNode::kInvalidAXID; |
| child_index_ = INVALID_INDEX; |
| text_offset_ = INVALID_OFFSET; |
| affinity_ = ax::mojom::TextAffinity::kDownstream; |
| } |
| } |
| |
| // Returns the character offset inside our anchor's parent at which our text |
| // starts. |
| int AnchorTextOffsetInParent() const { |
| if (IsNullPosition()) |
| return INVALID_OFFSET; |
| |
| // Calculate how much text there is to the left of this anchor. |
| AXPositionInstance tree_position = AsTreePosition(); |
| DCHECK(tree_position); |
| AXPositionInstance parent_position = tree_position->CreateParentPosition(); |
| DCHECK(parent_position); |
| if (parent_position->IsNullPosition()) |
| return 0; |
| |
| int offset_in_parent = 0; |
| for (int i = 0; i < parent_position->child_index(); ++i) { |
| AXPositionInstance child = parent_position->CreateChildPositionAt(i); |
| DCHECK(child); |
| offset_in_parent += child->MaxTextOffsetInParent(); |
| } |
| return offset_in_parent; |
| } |
| |
| // Abstract methods. |
| virtual void AnchorChild(int child_index, |
| AXTreeID* tree_id, |
| int32_t* child_id) const = 0; |
| virtual int AnchorChildCount() const = 0; |
| virtual int AnchorIndexInParent() const = 0; |
| virtual base::stack<AXNodeType*> GetAncestorAnchors() const = 0; |
| virtual void AnchorParent(AXTreeID* tree_id, int32_t* parent_id) const = 0; |
| virtual AXNodeType* GetNodeInTree(AXTreeID tree_id, |
| int32_t node_id) const = 0; |
| |
| // Returns the length of text that this anchor node takes up in its parent. |
| // On some platforms, embedded objects are represented in their parent with a |
| // single embedded object character. |
| int MaxTextOffsetInParent() const { |
| return IsEmbeddedObjectInParent() ? 1 : MaxTextOffset(); |
| } |
| |
| // Returns whether or not this anchor is represented in their parent with a |
| // single embedded object character. |
| virtual bool IsEmbeddedObjectInParent() const { return false; } |
| |
| // Determines if the anchor containing this position produces a hard line |
| // break in the text representation, e.g. a block level element or a <br>. |
| virtual bool IsInLineBreakingObject() const = 0; |
| |
| virtual ax::mojom::Role GetRole() const = 0; |
| virtual AXNodeTextStyles GetTextStyles() const = 0; |
| virtual std::vector<int32_t> GetWordStartOffsets() const = 0; |
| virtual std::vector<int32_t> GetWordEndOffsets() const = 0; |
| virtual int32_t GetNextOnLineID(int32_t node_id) const = 0; |
| virtual int32_t GetPreviousOnLineID(int32_t node_id) const = 0; |
| |
| private: |
| // Defines the relationship between positions during traversal. |
| // For example, moving from a descendant to an ancestor, is a kAncestor move. |
| enum class AXMoveType { |
| kAncestor, |
| kDescendant, |
| kSibling, |
| }; |
| |
| // Defines the direction of position movement, either next / previous in tree. |
| enum class AXMoveDirection { |
| kNextInTree, |
| kPreviousInTree, |
| }; |
| |
| // Type of predicate function called during anchor navigation. |
| // When the predicate returns |true|, the navigation stops and returns a |
| // null position object. |
| using AbortMovePredicate = |
| base::RepeatingCallback<bool(const AXPosition& move_from, |
| const AXPosition& move_to, |
| const AXMoveType type, |
| const AXMoveDirection direction)>; |
| |
| // Uses depth-first pre-order traversal. |
| AXPositionInstance CreateNextAnchorPosition( |
| const AbortMovePredicate& abort_predicate) const { |
| if (IsNullPosition()) |
| return CreateNullPosition(); |
| |
| AXPositionInstance current_position = AsTreePosition(); |
| DCHECK(!current_position->IsNullPosition()); |
| |
| if (AnchorChildCount()) { |
| const int child_index = current_position->child_index_; |
| if (child_index < current_position->AnchorChildCount()) { |
| AXPositionInstance child_position = |
| current_position->CreateChildPositionAt(child_index); |
| |
| if (abort_predicate.Run(*current_position, *child_position, |
| AXMoveType::kDescendant, |
| AXMoveDirection::kNextInTree)) { |
| return CreateNullPosition(); |
| } |
| return child_position; |
| } |
| } |
| |
| AXPositionInstance parent_position = |
| current_position->CreateParentPosition(); |
| |
| // Get the next sibling if it exists, otherwise move up the AXTree to the |
| // lowest next sibling of this position's ancestors. |
| while (!parent_position->IsNullPosition()) { |
| const int index_in_parent = current_position->AnchorIndexInParent(); |
| if (index_in_parent + 1 < parent_position->AnchorChildCount()) { |
| AXPositionInstance next_sibling = |
| parent_position->CreateChildPositionAt(index_in_parent + 1); |
| DCHECK(!next_sibling->IsNullPosition()); |
| |
| if (abort_predicate.Run(*current_position, *next_sibling, |
| AXMoveType::kSibling, |
| AXMoveDirection::kNextInTree)) { |
| return CreateNullPosition(); |
| } |
| return next_sibling; |
| } |
| |
| if (abort_predicate.Run(*current_position, *parent_position, |
| AXMoveType::kAncestor, |
| AXMoveDirection::kNextInTree)) { |
| return CreateNullPosition(); |
| } |
| |
| current_position = std::move(parent_position); |
| parent_position = current_position->CreateParentPosition(); |
| } |
| return CreateNullPosition(); |
| } |
| |
| // Uses depth-first pre-order traversal. |
| AXPositionInstance CreatePreviousAnchorPosition( |
| const AbortMovePredicate& abort_predicate) const { |
| if (IsNullPosition()) |
| return CreateNullPosition(); |
| |
| AXPositionInstance current_position = AsTreePosition(); |
| DCHECK(!current_position->IsNullPosition()); |
| |
| AXPositionInstance parent_position = |
| current_position->CreateParentPosition(); |
| if (parent_position->IsNullPosition()) |
| return CreateNullPosition(); |
| |
| // If there is no previous sibling, move up to the parent. |
| const int index_in_parent = current_position->AnchorIndexInParent(); |
| if (index_in_parent <= 0) { |
| if (abort_predicate.Run(*current_position, *parent_position, |
| AXMoveType::kAncestor, |
| AXMoveDirection::kPreviousInTree)) { |
| return CreateNullPosition(); |
| } |
| return parent_position; |
| } |
| |
| // Get the previous sibling's deepest last child. |
| AXPositionInstance rightmost_leaf = |
| parent_position->CreateChildPositionAt(index_in_parent - 1); |
| DCHECK(!rightmost_leaf->IsNullPosition()); |
| |
| if (abort_predicate.Run(*current_position, *rightmost_leaf, |
| AXMoveType::kSibling, |
| AXMoveDirection::kPreviousInTree)) { |
| return CreateNullPosition(); |
| } |
| |
| while (rightmost_leaf->AnchorChildCount()) { |
| parent_position = std::move(rightmost_leaf); |
| rightmost_leaf = parent_position->CreateChildPositionAt( |
| parent_position->AnchorChildCount() - 1); |
| DCHECK(!rightmost_leaf->IsNullPosition()); |
| |
| if (abort_predicate.Run(*parent_position, *rightmost_leaf, |
| AXMoveType::kDescendant, |
| AXMoveDirection::kPreviousInTree)) { |
| return CreateNullPosition(); |
| } |
| } |
| return rightmost_leaf; |
| } |
| |
| // Creates a position using the next text-only node as its anchor. |
| // Assumes that text-only nodes are leaf nodes. |
| AXPositionInstance CreateNextTextAnchorPosition( |
| const AbortMovePredicate& abort_predicate) const { |
| // If this is an ancestor text position, resolve to its leaf text position. |
| if (IsTextPosition() && AnchorChildCount()) |
| return AsLeafTextPosition(); |
| |
| AXPositionInstance next_leaf = CreateNextAnchorPosition(abort_predicate); |
| while (!next_leaf->IsNullPosition() && next_leaf->AnchorChildCount()) { |
| next_leaf = next_leaf->CreateNextAnchorPosition(abort_predicate); |
| } |
| |
| DCHECK(next_leaf); |
| return next_leaf->AsLeafTextPosition(); |
| } |
| |
| // Creates a position using the previous text-only node as its anchor. |
| // Assumes that text-only nodes are leaf nodes. |
| AXPositionInstance CreatePreviousTextAnchorPosition( |
| const AbortMovePredicate& abort_predicate) const { |
| // If this is an ancestor text position, resolve to its leaf text position. |
| if (IsTextPosition() && AnchorChildCount()) |
| return AsLeafTextPosition(); |
| |
| AXPositionInstance previous_leaf = |
| CreatePreviousAnchorPosition(abort_predicate); |
| while (!previous_leaf->IsNullPosition() && |
| previous_leaf->AnchorChildCount()) { |
| previous_leaf = |
| previous_leaf->CreatePreviousAnchorPosition(abort_predicate); |
| } |
| |
| DCHECK(previous_leaf); |
| return previous_leaf->AsLeafTextPosition(); |
| } |
| |
| // Creates a tree position using the next text-only node as its anchor. |
| // Assumes that text-only nodes are leaf nodes. |
| AXPositionInstance CreateNextLeafTreePosition( |
| const AbortMovePredicate abort_predicate) const { |
| AXPositionInstance next_leaf = |
| AsTreePosition()->CreateNextAnchorPosition(abort_predicate); |
| while (!next_leaf->IsNullPosition() && next_leaf->AnchorChildCount()) { |
| next_leaf = next_leaf->CreateNextAnchorPosition(abort_predicate); |
| } |
| |
| DCHECK(next_leaf); |
| return next_leaf; |
| } |
| |
| // Creates a tree position using the previous text-only node as its anchor. |
| // Assumes that text-only nodes are leaf nodes. |
| AXPositionInstance CreatePreviousLeafTreePosition( |
| const AbortMovePredicate abort_predicate) const { |
| AXPositionInstance previous_leaf = |
| AsTreePosition()->CreatePreviousAnchorPosition(abort_predicate); |
| while (!previous_leaf->IsNullPosition() && |
| previous_leaf->AnchorChildCount()) { |
| previous_leaf = |
| previous_leaf->CreatePreviousAnchorPosition(abort_predicate); |
| } |
| |
| DCHECK(previous_leaf); |
| return previous_leaf; |
| } |
| |
| // Static helpers for lambda usage. |
| static bool AtStartOfParagraphPredicate(const AXPositionInstance& position) { |
| return position->AtStartOfParagraph(); |
| } |
| |
| static bool AtEndOfParagraphPredicate(const AXPositionInstance& position) { |
| return position->AtEndOfParagraph(); |
| } |
| |
| static bool AtStartOfPagePredicate(const AXPositionInstance& position) { |
| return !position->IsIgnored() && position->AtStartOfPage(); |
| } |
| |
| static bool AtEndOfPagePredicate(const AXPositionInstance& position) { |
| return !position->IsIgnored() && position->AtEndOfPage(); |
| } |
| |
| static bool AtStartOfLinePredicate(const AXPositionInstance& position) { |
| return !position->IsIgnored() && position->AtStartOfLine(); |
| } |
| |
| static bool AtEndOfLinePredicate(const AXPositionInstance& position) { |
| return !position->IsIgnored() && position->AtEndOfLine(); |
| } |
| |
| // Default behavior is to never abort. |
| static bool DefaultAbortMovePredicate(const AXPosition& move_from, |
| const AXPosition& move_to, |
| const AXMoveType move_type, |
| const AXMoveDirection direction) { |
| return false; |
| } |
| |
| // AbortMovePredicate function used to detect format boundaries. |
| static bool AbortMoveAtFormatBoundary(const AXPosition& move_from, |
| const AXPosition& move_to, |
| const AXMoveType move_type, |
| const AXMoveDirection direction) { |
| if (move_from.IsNullPosition() || move_to.IsNullPosition()) |
| return true; |
| |
| // Treat moving to a leaf with different tags as a format break. |
| if ((move_to.AnchorChildCount() == 0) && |
| move_from.GetAnchor()->GetStringAttribute( |
| ax::mojom::StringAttribute::kHtmlTag) != |
| move_to.GetAnchor()->GetStringAttribute( |
| ax::mojom::StringAttribute::kHtmlTag)) { |
| return true; |
| } |
| |
| // Stop moving when text styles differ. |
| return move_from.AsLeafTextPosition()->GetTextStyles() != |
| move_to.AsLeafTextPosition()->GetTextStyles(); |
| } |
| |
| // AbortMovePredicate function used to detect paragraph boundaries. |
| static bool AbortMoveAtParagraphBoundary( |
| bool& crossed_potential_boundary_token, |
| const AXPosition& move_from, |
| const AXPosition& move_to, |
| const AXMoveType move_type, |
| const AXMoveDirection direction) { |
| if (move_from.IsNullPosition() || move_to.IsNullPosition()) |
| return true; |
| |
| const bool move_from_break = move_from.IsInLineBreakingObject(); |
| const bool move_to_break = move_to.IsInLineBreakingObject(); |
| |
| switch (move_type) { |
| case AXMoveType::kAncestor: |
| // For Ancestor moves, only abort when exiting a block descendant. |
| // We don't care if the ancestor is a block or not, since the |
| // descendant is contained by it. |
| crossed_potential_boundary_token |= move_from_break; |
| break; |
| case AXMoveType::kDescendant: |
| // For Descendant moves, only abort when entering a block descendant. |
| // We don't care if the ancestor is a block or not, since the |
| // descendant is contained by it. |
| crossed_potential_boundary_token |= move_to_break; |
| break; |
| case AXMoveType::kSibling: |
| // For Sibling moves, abort if at least one of the siblings are a block, |
| // because that would mean exiting and/or entering a block. |
| crossed_potential_boundary_token |= (move_from_break || move_to_break); |
| break; |
| } |
| |
| if (crossed_potential_boundary_token && !move_to.AnchorChildCount()) { |
| // If there's a sequence of whitespace-only anchors, collapse so only the |
| // last whitespace-only anchor is considered a paragraph boundary. |
| if (direction == AXMoveDirection::kNextInTree && |
| move_to.IsInWhiteSpace()) { |
| return false; |
| } |
| return true; |
| } |
| return false; |
| } |
| |
| // AbortMovePredicate function used to detect page boundaries. |
| static bool AbortMoveAtPageBoundary(const AXPosition& move_from, |
| const AXPosition& move_to, |
| const AXMoveType move_type, |
| const AXMoveDirection direction) { |
| if (move_from.IsNullPosition() || move_to.IsNullPosition()) |
| return true; |
| |
| const bool move_from_break = move_from.GetAnchor()->GetBoolAttribute( |
| ax::mojom::BoolAttribute::kIsPageBreakingObject); |
| const bool move_to_break = move_to.GetAnchor()->GetBoolAttribute( |
| ax::mojom::BoolAttribute::kIsPageBreakingObject); |
| |
| switch (move_type) { |
| case AXMoveType::kAncestor: |
| // For Ancestor moves, only abort when exiting a page break. |
| // We don't care if the ancestor is a page break or not, since the |
| // descendant is contained by it. |
| return move_from_break; |
| case AXMoveType::kDescendant: |
| // For Descendant moves, only abort when entering a page break |
| // descendant. We don't care if the ancestor is a page break or not, |
| // since the descendant is contained by it. |
| return move_to_break; |
| case AXMoveType::kSibling: |
| // For Sibling moves, abort if at both of the siblings are a page |
| // break, because that would mean exiting and/or entering a page break. |
| return move_from_break && move_to_break; |
| } |
| NOTREACHED(); |
| return false; |
| } |
| |
| AXPositionInstance CreateDocumentAncestorPosition() const { |
| AXPositionInstance iterator = Clone(); |
| while (!iterator->IsNullPosition()) { |
| if (IsDocument(iterator->GetRole()) && |
| iterator->CreateParentPosition()->IsNullPosition()) { |
| break; |
| } |
| iterator = iterator->CreateParentPosition(); |
| } |
| return iterator; |
| } |
| |
| AXPositionInstance CreateAncestorPosition( |
| const AXNodeType* ancestor_anchor) const { |
| if (!ancestor_anchor) |
| return CreateNullPosition(); |
| |
| AXPositionInstance ancestor_position = Clone(); |
| while (!ancestor_position->IsNullPosition() && |
| ancestor_position->GetAnchor() != ancestor_anchor) { |
| ancestor_position = ancestor_position->CreateParentPosition(); |
| } |
| return ancestor_position; |
| } |
| |
| AXPositionKind kind_; |
| AXTreeID tree_id_; |
| int32_t anchor_id_; |
| |
| // For text positions, |child_index_| is initially set to |-1| and only |
| // computed on demand. The same with tree positions and |text_offset_|. |
| int child_index_; |
| int text_offset_; |
| |
| // TODO(nektar): Get rid of affinity and make Blink handle affinity |
| // internally since inline text objects don't span lines. |
| ax::mojom::TextAffinity affinity_; |
| }; |
| |
| template <class AXPositionType, class AXNodeType> |
| const int AXPosition<AXPositionType, AXNodeType>::BEFORE_TEXT; |
| template <class AXPositionType, class AXNodeType> |
| const int AXPosition<AXPositionType, AXNodeType>::INVALID_INDEX; |
| template <class AXPositionType, class AXNodeType> |
| const int AXPosition<AXPositionType, AXNodeType>::INVALID_OFFSET; |
| |
| template <class AXPositionType, class AXNodeType> |
| bool operator==(const AXPosition<AXPositionType, AXNodeType>& first, |
| const AXPosition<AXPositionType, AXNodeType>& second) { |
| const base::Optional<int> compare_to_optional = first.CompareTo(second); |
| return compare_to_optional.has_value() && compare_to_optional.value() == 0; |
| } |
| |
| template <class AXPositionType, class AXNodeType> |
| bool operator!=(const AXPosition<AXPositionType, AXNodeType>& first, |
| const AXPosition<AXPositionType, AXNodeType>& second) { |
| const base::Optional<int> compare_to_optional = first.CompareTo(second); |
| return compare_to_optional.has_value() && compare_to_optional.value() != 0; |
| } |
| |
| template <class AXPositionType, class AXNodeType> |
| bool operator<(const AXPosition<AXPositionType, AXNodeType>& first, |
| const AXPosition<AXPositionType, AXNodeType>& second) { |
| const base::Optional<int> compare_to_optional = first.CompareTo(second); |
| return compare_to_optional.has_value() && compare_to_optional.value() < 0; |
| } |
| |
| template <class AXPositionType, class AXNodeType> |
| bool operator<=(const AXPosition<AXPositionType, AXNodeType>& first, |
| const AXPosition<AXPositionType, AXNodeType>& second) { |
| const base::Optional<int> compare_to_optional = first.CompareTo(second); |
| return compare_to_optional.has_value() && compare_to_optional.value() <= 0; |
| } |
| |
| template <class AXPositionType, class AXNodeType> |
| bool operator>(const AXPosition<AXPositionType, AXNodeType>& first, |
| const AXPosition<AXPositionType, AXNodeType>& second) { |
| const base::Optional<int> compare_to_optional = first.CompareTo(second); |
| return compare_to_optional.has_value() && compare_to_optional.value() > 0; |
| } |
| |
| template <class AXPositionType, class AXNodeType> |
| bool operator>=(const AXPosition<AXPositionType, AXNodeType>& first, |
| const AXPosition<AXPositionType, AXNodeType>& second) { |
| const base::Optional<int> compare_to_optional = first.CompareTo(second); |
| return compare_to_optional.has_value() && compare_to_optional.value() >= 0; |
| } |
| |
| template <class AXPositionType, class AXNodeType> |
| std::ostream& operator<<( |
| std::ostream& stream, |
| const AXPosition<AXPositionType, AXNodeType>& position) { |
| return stream << position.ToString(); |
| } |
| |
| } // namespace ui |
| |
| #endif // UI_ACCESSIBILITY_AX_POSITION_H_ |