blob: e68b38c435af04d5aaca42b0fdacc040bfd7950e [file] [log] [blame]
// 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 <math.h>
#include <stdint.h>
#include <functional>
#include <memory>
#include <ostream>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
#include "base/containers/stack.h"
#include "base/i18n/break_iterator.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_tree_id.h"
#include "ui/gfx/utf16_indexing.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
};
// Describes in further detail what type of boundary a current position is on.
// For complex boundaries such as format boundaries, it can be useful to know
// why a particular boundary was chosen.
enum class AXBoundaryType {
// Not at a unit boundary.
kNone,
// At a unit boundary (e.g. a format boundary).
kUnitBoundary,
// At the start of a document.
kDocumentStart,
// At the end of a document.
kDocumentEnd
};
// When converting to an unignored position, determines how to adjust the new
// position in order to make it valid, either moving backward or forward in
// the accessibility tree.
enum class AXPositionAdjustmentBehavior { kMoveBackward, kMoveForward };
// 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
};
// Some platforms require empty objects to be represented by a replacement
// character in order for text navigation to work correctly. This enum controls
// whether a replacement character will be exposed for such objects.
//
// When an embedded object is replaced by a real character, the expectations
// are the same with this character as with other ordinary characters.
// For example, with UIA on Windows, we need to be able to navigate inside and
// outside of this character as if it was an ordinary character, using the
// AXPlatformNodeTextRangeProvider methods. Since an embedded object character
// is the only character in a node, we also treat this character as a word.
enum class AXEmbeddedObjectBehavior {
kExposeCharacter,
kSuppressCharacter,
};
// Controls whether embedded objects are represented by a replacement
// character. This is initialized to a per-platform default but can be
// overridden for testing.
AX_EXPORT extern AXEmbeddedObjectBehavior g_ax_embedded_object_behavior;
// 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&)>;
using BoundaryTextOffsetsFunc =
base::RepeatingCallback<std::vector<int32_t>(const AXPositionInstance&)>;
static const int BEFORE_TEXT = -1;
static const int INVALID_INDEX = -2;
static const int INVALID_OFFSET = -1;
// Replacement character used to represent an empty object. See
// AXEmbeddedObjectBehavior for more information.
//
// Duplicate of AXPlatformNodeBase::kEmbeddedCharacter because we don't want
// to include platform specific code in here.
static constexpr base::char16 kEmbeddedCharacter = L'\xfffc';
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;
// Implemented based on the copy and swap idiom.
AXPosition& operator=(const AXPosition& other) {
AXPositionInstance clone = other.Clone();
swap(*clone);
return *this;
}
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;
}
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;
base::string16 text = GetText();
DCHECK_GE(text_offset_, 0);
int max_text_offset = MaxTextOffset();
DCHECK_LE(text_offset_, max_text_offset);
base::string16 annotated_text;
if (text_offset_ == max_text_offset) {
annotated_text = text + base::WideToUTF16(L"<>");
} else {
annotated_text = text.substr(0, text_offset_) + base::WideToUTF16(L"<") +
text[text_offset_] + base::WideToUTF16(L">") +
text.substr(text_offset_ + 1);
}
return str + " annotated_text=" + base::UTF16ToUTF8(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;
return GetNodeInTree(tree_id_, anchor_id_);
}
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 IsIgnored() const {
if (IsNullPosition())
return false;
DCHECK(GetAnchor());
// If this position is anchored to an ignored node, then consider this
// position to be ignored.
if (GetAnchor()->IsIgnored())
return true;
switch (kind_) {
case AXPositionKind::NULL_POSITION:
NOTREACHED();
return false;
case AXPositionKind::TREE_POSITION: {
// If this is a "before text" or an "after text" tree position, it's
// pointing to the anchor itself, which we've determined to be
// unignored.
DCHECK(!IsLeaf() || child_index_ == BEFORE_TEXT || child_index_ == 0)
<< "\"Before text\" and \"after text\" tree positions are only "
"valid on leaf nodes.";
if (child_index_ == BEFORE_TEXT || IsLeaf())
return false;
// If this position is an "after children" position, consider the
// position to be ignored if the last child is ignored. This is because
// the last child will not be visible in the unignored tree. If the
// position is not adjusted, the resulting position would erroneously
// point before the second child in the unignored subtree rooted at the
// last child.
//
// 1 kRootWebArea
// ++2 kGenericContainer ignored
// ++++3 kStaticText "Line 1."
// ++++4 kStaticText "Line 2."
//
// Tree position anchor=kGenericContainer, child_index=1.
//
// Alternatively, if there is a node at the position pointed to by
// "child_index_", i.e. this position is neither a leaf position nor an
// "after children" position, consider this tree position to be ignored
// if the child node is ignored.
int adjusted_child_index = child_index_ != AnchorChildCount()
? child_index_
: child_index_ - 1;
AXPositionInstance child_position =
CreateChildPositionAt(adjusted_child_index);
DCHECK(child_position && !child_position->IsNullPosition());
return child_position->GetAnchor()->IsIgnored();
}
case AXPositionKind::TEXT_POSITION:
// If the corresponding leaf position is ignored, the current text
// offset will point to ignored text. Therefore, consider this position
// to be ignored.
if (!IsLeaf())
return AsLeafTreePosition()->IsIgnored();
return false;
}
}
bool IsNullPosition() const {
return kind_ == AXPositionKind::NULL_POSITION || !GetAnchor();
}
bool IsTreePosition() const {
return GetAnchor() && kind_ == AXPositionKind::TREE_POSITION;
}
bool IsLeafTreePosition() const { return IsTreePosition() && IsLeaf(); }
bool IsTextPosition() const {
return GetAnchor() && kind_ == AXPositionKind::TEXT_POSITION;
}
bool IsLeafTextPosition() const { return IsTextPosition() && IsLeaf(); }
bool IsLeaf() const {
if (IsNullPosition())
return false;
return !AnchorChildCount() || IsEmptyObjectReplacedByCharacter();
}
// Returns true if this is a valid position, e.g. the child_index_ or
// text_offset_ is within a valid range.
bool IsValid() const {
switch (kind_) {
case AXPositionKind::NULL_POSITION:
return tree_id_ == AXTreeIDUnknown() &&
anchor_id_ == AXNode::kInvalidAXID &&
child_index_ == INVALID_INDEX &&
text_offset_ == INVALID_OFFSET &&
affinity_ == ax::mojom::TextAffinity::kDownstream;
case AXPositionKind::TREE_POSITION:
return GetAnchor() &&
(child_index_ == BEFORE_TEXT ||
(child_index_ >= 0 && child_index_ <= AnchorChildCount())) &&
!IsInDescendantOfEmptyObject();
case AXPositionKind::TEXT_POSITION:
if (!GetAnchor() || IsInDescendantOfEmptyObject())
return false;
// For performance reasons we skip any validation of the text offset
// that involves retrieving the anchor's text, if the offset is set to
// 0, because 0 is frequently used and always valid regardless of the
// actual text.
return text_offset_ == 0 ||
(text_offset_ > 0 && text_offset_ <= MaxTextOffset());
}
}
// 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 (!IsLeaf() || 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,
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, 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, including but not limited to hard line
// breaks, might be used to separate lines. For example, an inline text
// box with just a single space character inside it can be used to
// represent a soft line break. If an inline text box containing white
// space separates two lines, it should always be connected to the first
// line via "kPreviousOnLineId". This is guaranteed by the renderer. If
// there are multiple line breaks separating the two lines, then only
// the first line break is connected to the first line via
// "kPreviousOnLineId".
//
// Sometimes there might be an inline text box with a single space in it
// at the end of a text field. We should not mark positions that are at
// the end of text fields, or in general at the end of their anchor, as
// being at the start of line, except when that anchor is an inline text
// box that is in the middle of a text span. Note that in most but not
// all cases, the parent of an inline text box is a static text object,
// whose end signifies the end of the text span. One exception is line
// breaks.
if (text_position->AtEndOfAnchor() &&
!text_position->AtEndOfTextSpan() &&
text_position->IsInWhiteSpace() &&
GetNextOnLineID(text_position->anchor_id_) ==
AXNode::kInvalidAXID) {
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 via "AsLeafTextPosition".
// If affinity had been set to upstream, the leaf text position should
// be pointing to the end of the inline text box that ends the first
// line. If it had been set to downstream, the leaf text position should
// be pointing to the start of the inline text box that starts the
// second line.
//
// In other cases, we assume that white space, including but not limited
// to hard line breaks, might be used to separate lines. For example, an
// inline text box with just a single space character inside it can be
// used to represent a soft line break. If an inline text box containing
// white space separates two lines, it should always be connected to the
// first line via "kPreviousOnLineId". This is guaranteed by the
// renderer. If there are multiple line breaks separating the two lines,
// then only the first line break is connected to the first line via
// "kPreviousOnLineId".
//
// 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. This is in order
// to enable screen readers to recognize and announce blank lines
// correctly. 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, i.e. on a blank line, as being at the end of that line.
//
// Sometimes there might be an inline text box with a single space in it
// at the end of a text field. We should mark positions that are at the
// end of text fields, or in general at the end of an anchor with no
// "kNextOnLineId", as being at end of line, except when that anchor is
// an inline text box that is in the middle of a text span. Note that
// in most but not all cases, the parent of an inline text box is a
// static text object, whose end signifies the end of the text span. One
// exception is line breaks.
if (GetNextOnLineID(text_position->anchor_id_) ==
AXNode::kInvalidAXID) {
return (!text_position->AtEndOfTextSpan() &&
text_position->IsInWhiteSpace() &&
GetPreviousOnLineID(text_position->anchor_id_) !=
AXNode::kInvalidAXID)
? text_position->AtStartOfAnchor()
: text_position->AtEndOfAnchor();
}
// 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 an unignored position 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 an unignored position at
// the start of an anchor.
if (text_position->IsIgnored() || !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_line_breaking_object_token = false;
const AbortMovePredicate abort_move_predicate =
base::BindRepeating(&AbortMoveAtParagraphBoundary,
std::ref(crossed_line_breaking_object_token));
AXPositionInstance 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() ||
previous_text_position->IsIgnored());
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 an unignored position 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 an unignored position at
// the end of an anchor.
if (text_position->IsIgnored() || !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_line_breaking_object_token = false;
const AbortMovePredicate abort_move_predicate =
base::BindRepeating(&AbortMoveAtParagraphBoundary,
std::ref(crossed_line_breaking_object_token));
AXPositionInstance next_text_position = text_position->Clone();
do {
next_text_position = next_text_position->CreateNextTextAnchorPosition(
abort_move_predicate);
} while (next_text_position->IsIgnored());
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.
AXPositionInstance 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.
AXPositionInstance next_text_position =
text_position->CreateNextTextAnchorPosition(
base::BindRepeating(&AbortMoveAtPageBoundary));
return next_text_position->IsNullPosition();
}
}
}
bool AtStartOfAXTree() const {
if (IsNullPosition())
return false;
if (AtStartOfAnchor()) {
AXPositionInstance previous_anchor = CreatePreviousAnchorPosition();
// Consider the start of the document as the start of an AXTree.
if (previous_anchor->IsNullPosition())
return true;
else
return previous_anchor->tree_id() != tree_id();
}
return false;
}
bool AtEndOfAXTree() const {
if (IsNullPosition())
return false;
if (AtEndOfAnchor()) {
AXPositionInstance next_anchor = CreateNextAnchorPosition();
// Consider the end of the document as the end of an AXTree.
if (next_anchor->IsNullPosition())
return true;
else
return next_anchor->tree_id() != tree_id();
}
return false;
}
AXBoundaryType GetFormatStartBoundaryType() 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 AXBoundaryType::kNone;
// Treat the first iterable node as a format boundary.
if (CreatePreviousLeafTreePosition()->IsNullPosition())
return AXBoundaryType::kDocumentStart;
// Ignored positions cannot be format boundaries.
if (IsIgnored())
return AXBoundaryType::kNone;
// Iterate over anchors until a format boundary is found. This will return a
// null position upon crossing a boundary. Make sure the previous position
// is not on an ignored node.
AXPositionInstance previous_position = Clone();
do {
previous_position = previous_position->CreatePreviousLeafTreePosition(
base::BindRepeating(&AbortMoveAtFormatBoundary));
} while (previous_position->IsIgnored());
if (previous_position->IsNullPosition())
return AXBoundaryType::kUnitBoundary;
return AXBoundaryType::kNone;
}
bool AtStartOfFormat() const {
return GetFormatStartBoundaryType() != AXBoundaryType::kNone;
}
AXBoundaryType GetFormatEndBoundaryType() 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 AXBoundaryType::kNone;
// Treat the last iterable node as a format boundary
if (CreateNextLeafTreePosition()->IsNullPosition())
return AXBoundaryType::kDocumentEnd;
// Ignored positions cannot be format boundaries.
if (IsIgnored())
return AXBoundaryType::kNone;
// Iterate over anchors until a format boundary is found. This will return a
// null position upon crossing a boundary. Make sure the next position is
// not on an ignored node.
AXPositionInstance next_position = Clone();
do {
next_position = next_position->CreateNextLeafTreePosition(
base::BindRepeating(&AbortMoveAtFormatBoundary));
} while (next_position->IsIgnored());
if (next_position->IsNullPosition())
return AXBoundaryType::kUnitBoundary;
return AXBoundaryType::kNone;
}
bool AtEndOfFormat() const {
return GetFormatEndBoundaryType() != AXBoundaryType::kNone;
}
bool AtStartOfInlineBlock() 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()) {
AXPositionInstance previous_position =
text_position->CreatePreviousLeafTreePosition();
// Check that this position is not the start of the first anchor.
if (!previous_position->IsNullPosition()) {
previous_position = text_position->CreatePreviousLeafTreePosition(
base::BindRepeating(&AbortMoveAtStartOfInlineBlock));
// If we get a null position here it means we have crossed an inline
// block's start, thus this position is located at such start.
if (previous_position->IsNullPosition())
return true;
}
}
if (text_position->AtEndOfAnchor()) {
AXPositionInstance next_position =
text_position->CreateNextLeafTreePosition();
// Check that this position is not the end of the last anchor.
if (!next_position->IsNullPosition()) {
next_position = text_position->CreateNextLeafTreePosition(
base::BindRepeating(&AbortMoveAtStartOfInlineBlock));
// If we get a null position here it means we have crossed an inline
// block's start, thus this position is located at such start.
if (next_position->IsNullPosition())
return true;
}
}
return false;
}
}
}
bool AtStartOfDocument() const {
if (IsNullPosition())
return false;
return IsDocument(GetAnchorRole()) && AtStartOfAnchor();
}
bool AtEndOfDocument() const {
if (IsNullPosition())
return false;
return AtLastNodeInTree() && AtEndOfAnchor();
}
bool AtLastNodeInTree() const {
if (IsNullPosition())
return false;
// Avoid a potentionally expensive MaxTextOffset call by only using tree
// positions. The only thing that matters is whether our anchor_id_ is at
// the last anchor of the document, so we're free to ignore text_offset_.
AXPositionInstance tree_position =
CreateTreePosition(tree_id_, anchor_id_, 0);
return tree_position->CreateNextAnchorPosition()->IsNullPosition();
}
// 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));
}
// See "CreateParentPosition" for an explanation of the use of
// |move_direction|.
AXPositionInstance CreateAncestorPosition(
const AXNodeType* ancestor_anchor,
ax::mojom::MoveDirection move_direction =
ax::mojom::MoveDirection::kForward) const {
if (!ancestor_anchor)
return CreateNullPosition();
AXPositionInstance ancestor_position = Clone();
while (!ancestor_position->IsNullPosition() &&
ancestor_position->GetAnchor() != ancestor_anchor) {
ancestor_position =
ancestor_position->CreateParentPosition(move_direction);
}
return ancestor_position;
}
// If the position is not valid, we return a new valid position that is
// closest to the original position if possible, or a null position otherwise.
AXPositionInstance AsValidPosition() const {
AXPositionInstance position = Clone();
switch (position->kind_) {
case AXPositionKind::NULL_POSITION:
// We avoid cloning to ensure that all fields will be valid.
return CreateNullPosition();
case AXPositionKind::TREE_POSITION: {
if (!position->GetAnchor())
return CreateNullPosition();
if (AXNodeType* empty_object_node = GetEmptyObjectAncestorNode()) {
// In this class and on certain platforms, we define the empty object
// as one that doesn't expose its underlying content. Its content is
// replaced by the empty object character (string of length 1). A
// position on a descendant of an empty object is invalid. To make it
// valid we move the position from the descendant to the empty object
// node itself.
return CreateTreePosition(
position->tree_id(), GetAnchorID(empty_object_node),
position->child_index() == BEFORE_TEXT ? BEFORE_TEXT : 0);
}
if (position->child_index_ == BEFORE_TEXT)
return position;
if (position->child_index_ < 0)
position->child_index_ = 0;
else if (position->child_index_ > position->AnchorChildCount())
position->child_index_ = position->AnchorChildCount();
break;
}
case AXPositionKind::TEXT_POSITION: {
if (!position->GetAnchor())
return CreateNullPosition();
if (AXNodeType* empty_object_node = GetEmptyObjectAncestorNode()) {
// This is needed because an empty object as defined in this class and
// on certain platforms can have descendants that should not be
// exposed. See comment above in similar implementation for
// AXPositionKind::TREE_POSITION.
//
// We set the |text_offset_| to either 0 or 1 here because the
// MaxTextOffset of an empty object is 1 (the empty object character,
// a string of length 1). If the invalid position was already at the
// start of the node, we set it to 0.
return CreateTextPosition(position->tree_id(),
GetAnchorID(empty_object_node),
position->text_offset() > 0 ? 1 : 0,
ax::mojom::TextAffinity::kDownstream);
}
if (position->text_offset_ <= 0) {
// 0 is always a valid offset, so skip calling MaxTextOffset in that
// case.
position->text_offset_ = 0;
position->affinity_ = ax::mojom::TextAffinity::kDownstream;
} else {
int max_text_offset = position->MaxTextOffset();
if (position->text_offset_ > max_text_offset) {
position->text_offset_ = max_text_offset;
position->affinity_ = ax::mojom::TextAffinity::kDownstream;
}
}
break;
}
}
DCHECK(position->IsValid());
return position;
}
AXPositionInstance AsTreePosition() const {
if (IsNullPosition() || IsTreePosition())
return Clone();
AXPositionInstance copy = Clone();
DCHECK(copy);
DCHECK_GE(copy->text_offset_, 0);
if (copy->IsLeaf()) {
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;
}
// We stop at the last child that we can reach with the current text offset
// and ignore any remaining children. This is for defensive programming
// purposes, in case "MaxTextOffset" doesn't match the total length of all
// our children. This may happen if, for example, there is a bug in the
// internal accessibility tree we get from the renderer. In contrast, the
// current offset could not be greater than the length of all our children
// because the position would have been invalid.
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 the text offset falls on the boundary between two adjacent children,
// we look at the affinity to decide whether to place the tree position on
// the first child vs. the second child. Upstream affinity would always
// choose the first child, whilst downstream affinity the second. This
// also has implications when converting the resulting tree position back
// to a text position. In that case, maintaining an upstream affinity
// would place the text position at the end of the first child, whilst
// maintaining a downstream affinity will place the text position at the
// beginning of the second child.
//
// This is vital for text positions on soft line breaks, as well as text
// positions before and after character, to work properly.
//
// See also `CreateLeafTextPositionBeforeCharacter` and
// `CreateLeafTextPositionAfterCharacter`.
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;
}
// This is an optimization over "AsLeafTextPosition", in cases when computing
// the corresponding text offset on the leaf node is not needed. If this
// method is called on a text position, it will conservatively fall back to
// the non-optimized "AsLeafTextPosition", if the current text offset is
// greater than 0, or the affinity is upstream, since converting to a tree
// position at any point before reaching the leaf node could potentially lose
// information.
AXPositionInstance AsLeafTreePosition() const {
if (IsNullPosition() || IsLeaf())
return AsTreePosition();
// If our text offset is greater than 0, or if our affinity is set to
// upstream, we need to ensure that text offset and affinity will be taken
// into consideration during our descend to the leaves. Switching to a tree
// position early in this case will potentially lose information, so we
// descend using a text position instead.
//
// We purposely don't check whether this position is a text position, to
// allow for the possibility that this position has recently been converted
// from a text to a tree position and text offset or affinity information
// has been left intact.
if (text_offset_ > 0 || affinity_ == ax::mojom::TextAffinity::kUpstream)
return AsLeafTextPosition()->AsTreePosition();
AXPositionInstance tree_position = AsTreePosition();
do {
if (tree_position->child_index_ == tree_position->AnchorChildCount()) {
tree_position =
tree_position
->CreateChildPositionAt(tree_position->child_index_ - 1)
->CreatePositionAtEndOfAnchor();
} else {
tree_position =
tree_position->CreateChildPositionAt(tree_position->child_index_);
}
DCHECK(tree_position && !tree_position->IsNullPosition());
} while (!tree_position->IsLeaf());
DCHECK(tree_position && tree_position->IsLeafTreePosition());
return tree_position;
}
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->IsLeaf());
// 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.
//
// We test for INVALID_OFFSET first, due to the possible performance
// implications of calling MaxTextOffset().
DCHECK_GE(copy->text_offset_, INVALID_OFFSET)
<< "Unrecognized text offset.";
if (copy->text_offset_ == INVALID_OFFSET ||
(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() || IsLeaf())
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->IsLeaf());
DCHECK(text_position);
DCHECK(text_position->IsLeafTextPosition());
text_position->text_offset_ = adjusted_offset;
// A leaf Text position is 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;
}
// We deploy three strategies in order to find the best match for an ignored
// position in the accessibility tree:
//
// 1. In the case of a text position, we move up the parent positions until we
// find the next unignored equivalent parent position. We don't do this for
// tree positions because, unlike text positions which maintain the
// corresponding text offset in the inner text of the parent node, tree
// positions would lose some information every time a parent position is
// computed. In other words, the parent position of a tree position is, in
// most cases, non-equivalent to the child position.
// 2. If no equivalent and unignored parent position can be computed, we try
// computing the leaf equivalent position. If this is unignored, we return it.
// This can happen both for tree and text positions, provided that the leaf
// node and its inner text is visible to platform APIs, i.e. it's unignored.
// 3. As a last resort, we move either to the next or previous unignored
// position in the accessibility tree, based on the "adjustment_behavior".
AXPositionInstance AsUnignoredPosition(
AXPositionAdjustmentBehavior adjustment_behavior) const {
if (IsNullPosition() || !IsIgnored())
return Clone();
AXPositionInstance leaf_tree_position = AsLeafTreePosition();
// If this is a text position, first try moving up to a parent equivalent
// position and check if the resulting position is still ignored. This
// won't result in the loss of any information. We can't do that in the
// case of tree positions, because we would be better off to move to the
// next or previous position within the same anchor, as this would lose
// less information than moving to a parent equivalent position.
//
// Text positions are considered ignored if either the current anchor is
// ignored, or if the equivalent leaf tree position is ignored.
// If this position is a leaf text position, or the equivalent leaf tree
// position is ignored, then it's not possible to create an ancestor text
// position that is unignored.
if (IsTextPosition() && !IsLeafTextPosition() &&
!leaf_tree_position->IsIgnored()) {
AXPositionInstance unignored_position = CreateParentPosition();
while (!unignored_position->IsNullPosition()) {
// Since the equivalent leaf tree position is unignored, search for the
// first unignored ancestor anchor and return that text position.
if (!unignored_position->GetAnchor()->IsIgnored()) {
DCHECK(!unignored_position->IsIgnored());
return unignored_position;
}
unignored_position = unignored_position->CreateParentPosition();
}
}
// There is a possibility that the position became unignored by moving to a
// leaf equivalent position. Otherwise, we have no choice but to move to the
// next or previous position and lose some information in the process.
while (leaf_tree_position->IsIgnored()) {
switch (adjustment_behavior) {
case AXPositionAdjustmentBehavior::kMoveForward:
leaf_tree_position = leaf_tree_position->CreateNextLeafTreePosition();
break;
case AXPositionAdjustmentBehavior::kMoveBackward:
leaf_tree_position =
leaf_tree_position->CreatePreviousLeafTreePosition();
// in case the unignored leaf node contains some text, ensure that the
// resulting position is an "after text" position, as such a position
// would be the closest to the ignored one, given the fact that we are
// moving backwards through the tree.
leaf_tree_position =
leaf_tree_position->CreatePositionAtEndOfAnchor();
break;
}
}
if (IsTextPosition())
return leaf_tree_position->AsTextPosition();
return leaf_tree_position;
}
// Searches backward and forward 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 ax::mojom::TextBoundary::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
// ax::mojom::TextBoundary::kObject and ax::mojom::TextBoundary::kWebPage
// because the range should be the same regardless if we first move left or
// right.
AXRangeType ExpandToEnclosingTextBoundary(
ax::mojom::TextBoundary boundary,
AXRangeExpandBehavior expand_behavior) const {
AXBoundaryBehavior boundary_behavior =
AXBoundaryBehavior::StopAtAnchorBoundary;
if (boundary == ax::mojom::TextBoundary::kWebPage)
boundary_behavior = AXBoundaryBehavior::CrossBoundary;
switch (expand_behavior) {
case AXRangeExpandBehavior::kLeftFirst: {
AXPositionInstance left_position = CreatePositionAtTextBoundary(
boundary, ax::mojom::MoveDirection::kBackward, boundary_behavior);
AXPositionInstance right_position =
left_position->CreatePositionAtTextBoundary(
boundary, ax::mojom::MoveDirection::kForward,
boundary_behavior);
return AXRangeType(std::move(left_position), std::move(right_position));
}
case AXRangeExpandBehavior::kRightFirst: {
AXPositionInstance right_position = CreatePositionAtTextBoundary(
boundary, ax::mojom::MoveDirection::kForward, boundary_behavior);
AXPositionInstance left_position =
right_position->CreatePositionAtTextBoundary(
boundary, ax::mojom::MoveDirection::kBackward,
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 backward direction, and the end
// boundary when moving in the forward direction.
AXPositionInstance CreatePositionAtTextBoundary(
ax::mojom::TextBoundary boundary,
ax::mojom::MoveDirection direction,
AXBoundaryBehavior boundary_behavior) const {
AXPositionInstance resulting_position = CreateNullPosition();
switch (boundary) {
case ax::mojom::TextBoundary::kNone:
NOTREACHED();
break;
case ax::mojom::TextBoundary::kCharacter:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousCharacterPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextCharacterPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kFormat:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousFormatStartPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextFormatEndPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kLineEnd:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousLineEndPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextLineEndPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kLineStart:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousLineStartPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextLineStartPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kLineStartOrEnd:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousLineStartPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextLineEndPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kObject:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position = CreatePositionAtStartOfAnchor();
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreatePositionAtEndOfAnchor();
break;
}
break;
case ax::mojom::TextBoundary::kPageEnd:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousPageEndPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextPageEndPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kPageStart:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousPageStartPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextPageStartPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kPageStartOrEnd:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousPageStartPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextPageEndPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kParagraphEnd:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousParagraphEndPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position =
CreateNextParagraphEndPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kParagraphStart:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousParagraphStartPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position =
CreateNextParagraphStartPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kParagraphStartOrEnd:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousParagraphStartPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position =
CreateNextParagraphEndPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kSentenceEnd:
NOTREACHED() << "Sentence boundaries are not yet supported.";
return CreateNullPosition();
case ax::mojom::TextBoundary::kSentenceStart:
NOTREACHED() << "Sentence boundaries are not yet supported.";
return CreateNullPosition();
case ax::mojom::TextBoundary::kSentenceStartOrEnd:
NOTREACHED() << "Sentence boundaries are not yet supported.";
return CreateNullPosition();
case ax::mojom::TextBoundary::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 ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position = CreatePositionAtStartOfDocument();
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreatePositionAtEndOfDocument();
break;
}
break;
case ax::mojom::TextBoundary::kWordEnd:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousWordEndPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextWordEndPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kWordStart:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousWordStartPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
resulting_position = CreateNextWordStartPosition(boundary_behavior);
break;
}
break;
case ax::mojom::TextBoundary::kWordStartOrEnd:
switch (direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
break;
case ax::mojom::MoveDirection::kBackward:
resulting_position =
CreatePreviousWordStartPosition(boundary_behavior);
break;
case ax::mojom::MoveDirection::kForward:
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 (IsLeaf())
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_,
IsEmptyObjectReplacedByCharacter() ? 0 : AnchorChildCount());
case AXPositionKind::TEXT_POSITION:
return CreateTextPosition(tree_id_, anchor_id_, MaxTextOffset(),
ax::mojom::TextAffinity::kDownstream);
}
return CreateNullPosition();
}
AXPositionInstance CreatePositionAtStartOfAXTree() const {
if (IsNullPosition() || AtStartOfAXTree())
return Clone();
// First check for positions on nodes which are AXTree boundaries, but where
// the text position on that node is not at the start of the anchor.
if (CreatePositionAtStartOfAnchor()->AtStartOfAXTree())
return CreatePositionAtStartOfAnchor();
// Iterate over tree positions until a boundary is reached.
AXPositionInstance previous_position = AsTreePosition();
do {
previous_position = previous_position->CreatePreviousAnchorPosition();
} while (!previous_position->AtStartOfAXTree());
// This method should not cross tree boundaries.
DCHECK_EQ(previous_position->tree_id(), tree_id());
if (IsTextPosition())
previous_position = previous_position->AsTextPosition();
return previous_position;
}
AXPositionInstance CreatePositionAtEndOfAXTree() const {
if (IsNullPosition() || AtEndOfAXTree())
return Clone();
// First check for positions on nodes which are AXTree boundaries, but where
// the text position on that node is not at the end of the anchor.
if (CreatePositionAtEndOfAnchor()->AtEndOfAXTree())
return CreatePositionAtEndOfAnchor();
// Iterate over tree positions until a boundary is reached.
AXPositionInstance next_position = AsTreePosition();
do {
next_position = next_position->CreateNextAnchorPosition()
->CreatePositionAtEndOfAnchor();
} while (!next_position->AtEndOfAXTree());
// This method should not cross tree boundaries.
DCHECK_EQ(next_position->tree_id(), tree_id());
if (IsTextPosition())
next_position = next_position->AsTextPosition();
return next_position->CreatePositionAtEndOfAnchor();
}
// "document" is defined here as a single, top-level, navigatable unit from
// a user's perspective. This means that all iframes are part of a single
// "document" that contains the top-level navigatable page. So this method
// will break out of an iframe and return a position at the start of the
// top-level document.
//
// Note that this definition is different than HTML's definition of
// "document", where each iframe has its own document object. For a similar
// method that stops at iframe boundaries, see
// CreatePositionAtStartOfAXTree().
AXPositionInstance CreatePositionAtStartOfDocument() const {
AXPositionInstance position =
AsTreePosition()->CreateDocumentAncestorPosition();
if (!position->IsNullPosition()) {
position = position->CreatePositionAtStartOfAnchor();
if (IsTextPosition())
position = position->AsTextPosition();
}
return position;
}
// "document" is defined here as a single, top-level, navigatable unit from
// a user's perspective. This means that all iframes are part of a single
// "document" that contains the top-level navigatable page. So this method
// will break out of an iframe and return a position at the end of the
// top-level document.
//
// Note that this definition is different than HTML's definition of
// "document", where each iframe has its own document object. For a similar
// method that stops at iframe boundaries, see CreatePositionAtEndOfAXTree().
AXPositionInstance CreatePositionAtEndOfDocument() const {
AXPositionInstance position =
AsTreePosition()->CreateDocumentAncestorPosition();
if (!position->IsNullPosition()) {
while (!position->IsLeaf()) {
position =
position->CreateChildPositionAt(position->AnchorChildCount() - 1);
}
position = position->CreatePositionAtEndOfAnchor();
if (IsTextPosition())
position = position->AsTextPosition();
}
return position;
}
AXPositionInstance CreateChildPositionAt(int child_index) const {
if (IsNullPosition() || IsLeaf())
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->IsLeaf())
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();
}
// Creates a parent equivalent position.
//
// "move_direction" is used only in the case of a text position, when in
// the process of searching for a text boundary, and on platforms where child
// nodes are represented by embedded object characters. On such platforms, the
// "IsEmbeddedObjectInParent" method returns true. We need to decide whether
// to create a parent equivalent position that is before or after the child
// node, since moving to a parent position would always cause us to lose some
// information. We can't simply re-use the text offset of the child position
// because by definition the parent node doesn't include all the text of the
// child node, but only a single embedded object character.
//
// staticText name='Line one' IA2-hypertext='<embedded_object>'
// ++inlineTextBox name='Line one'
//
// If we are given a text position pointing to somewhere inside the
// inlineTextBox, and we move to the parent equivalent position, we need to
// decide whether the parent position would be set to point to before the
// embedded object character or after it. Both are valid, depending on the
// direction on motion, e.g. if we are trying to find the start of the line
// vs. the end of the line.
AXPositionInstance CreateParentPosition(
ax::mojom::MoveDirection move_direction =
ax::mojom::MoveDirection::kForward) 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: {
// On some platforms, such as Android, Mac and Chrome OS, the inner text
// of a node is made up by concatenating the text of child nodes. On
// other platforms, such as Windows IA2 and Linux ATK, child nodes are
// represented by a single embedded object character.
//
// If our parent's inner text is a concatenation of all its children's
// text, we need to maintain the affinity and compute the corresponding
// text offset. Otherwise, we have no choice but to return a position
// that is either before or after this child, losing some information in
// the process. Regardless to whether our parent contains all our text,
// we always recompute the affinity when the position is after the
// child.
//
// Recomputing the affinity in the latter situation 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
// a position that represents the start of the next line. For example:
//
// staticText name='Line oneLine two'
// ++inlineTextBox name='Line one'
// ++inlineTextBox name='Line two'
//
// If the original position is at the end of the inline text box for
// "Line one", then the resulting parent equivalent position would be
// the same as the one that would have been computed if the original
// position were at the start of the inline text box for "Line two".
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) {
// Our parent contains all our text. No information would be lost when
// moving to a parent equivalent position.
parent_offset += text_offset_;
} else if (text_offset_ > 0) {
// If "text_offset_" == 0, then the child position is clearly before
// any embedded object character. No information would be lost when
// moving to a parent equivalent position, including affinity
// information. Otherwise, we should decide whether to set the parent
// position to be before or after the child, based on the direction of
// motion, and also reset the affinity.
switch (move_direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
return CreateNullPosition();
case ax::mojom::MoveDirection::kBackward:
// Keep the offset to be right before the embedded object
// character.
break;
case ax::mojom::MoveDirection::kForward:
// Set the offset to be after the embedded object character.
parent_offset += max_text_offset_in_parent;
break;
}
// The original affinity doesn't apply any more. In most cases, it
// should be downstream, unless there is an ambiguity as to whether
// the parent position is between the end of one line and the start of
// the next. We perform this check below.
parent_affinity = ax::mojom::TextAffinity::kDownstream;
}
AXPositionInstance parent_position = CreateTextPosition(
tree_id, parent_id, parent_offset, parent_affinity);
// If the current position is pointing at the end of its anchor, we need
// to check if the parent position has introduced ambiguity as to
// whether it refers to the end of a line or the start of the next.
// Ambiguity is only present when the parent position points to a text
// offset that is neither at the start nor at the end of its anchor. We
// check for ambiguity by creating the parent position and testing if it
// is erroneously at the start of the next line. Given that the current
// position, by the nature of being at the end of its anchor, could only
// be at end of line, the fact that the parent position is also
// determined to be at start of line demonstrates the presence of
// ambiguity which is resolved by setting its affinity to upstream.
//
// We could not have
// checked if the child was at the end of the line, because our
// "AtEndOfLine" predicate takes into account trailing line breaks,
// which would create false positives.
if (text_offset_ == max_text_offset &&
!parent_position->AtEndOfAnchor() &&
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 the next text position anchored at a leaf node of the AXTree.
//
// If a pointer |crossed_line_breaking_object| is provided, it'll be set to
// |true| if any line breaking object boundary was crossed by moving from this
// leaf text position to the next (if it exists), |false| otherwise.
AXPositionInstance CreateNextLeafTextPosition(
bool* crossed_line_breaking_object = nullptr) const {
if (crossed_line_breaking_object)
*crossed_line_breaking_object = false;
// If this is an ancestor text position, resolve to its leaf text position.
if (IsTextPosition() && !IsLeaf())
return AsLeafTextPosition();
AbortMovePredicate abort_move_predicate =
crossed_line_breaking_object
? base::BindRepeating(&UpdateCrossedLineBreakingObjectToken,
std::ref(*crossed_line_breaking_object))
: base::BindRepeating(&DefaultAbortMovePredicate);
return CreateNextLeafTreePosition(abort_move_predicate)->AsTextPosition();
}
// 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.
//
// Also, |text_offset| is adjusted to point to a valid character offset, i.e.
// it cannot be pointing to a low surrogate pair or to the middle of a
// grapheme cluster.
AXPositionInstance AsLeafTextPositionBeforeCharacter() const {
if (IsNullPosition())
return Clone();
AXPositionInstance text_position = AsTextPosition();
// In case the input affinity is upstream, reset it to downstream.
//
// This is to ensure that when we find the equivalent leaf text position, it
// will be at the start of anchor if the original position is anchored to a
// node higher up in the tree and pointing to a text offset that falls on
// the boundary between two leaf nodes. In other words, the returned
// position will always be "before character".
text_position->affinity_ = ax::mojom::TextAffinity::kDownstream;
text_position = text_position->AsLeafTextPosition();
DCHECK(!text_position->IsNullPosition())
<< "Adjusting to a leaf position should never turn a non-null position "
"into a null one.";
if (!text_position->IsIgnored() && !text_position->AtEndOfAnchor()) {
std::unique_ptr<base::i18n::BreakIterator> grapheme_iterator =
text_position->GetGraphemeIterator();
DCHECK_GE(text_position->text_offset_, 0);
DCHECK_LE(text_position->text_offset_,
int{text_position->name_.length()});
while (
!text_position->AtStartOfAnchor() &&
(!gfx::IsValidCodePointIndex(text_position->name_,
size_t{text_position->text_offset_}) ||
(grapheme_iterator && !grapheme_iterator->IsGraphemeBoundary(
size_t{text_position->text_offset_})))) {
--text_position->text_offset_;
}
return text_position;
}
text_position = text_position->CreateNextLeafTextPosition();
while (!text_position->IsNullPosition() &&
(text_position->IsIgnored() || !text_position->MaxTextOffset())) {
text_position = text_position->CreateNextLeafTextPosition();
}
return text_position;
}
// Returns a text position located right after the previous character (from
// this position) in the tree's text representation.
//
// See `AsLeafTextPositionBeforeCharacter`, as this is its "reversed" version.
AXPositionInstance AsLeafTextPositionAfterCharacter() const {
if (IsNullPosition())
return Clone();
AXPositionInstance text_position = AsTextPosition();
// Temporarily set the affinity to upstream.
//
// This is to ensure that when we find the equivalent leaf text position, it
// will be at the end of anchor if the original position is anchored to a
// node higher up in the tree and pointing to a text offset that falls on
// the boundary between two leaf nodes. In other words, the returned
// position will always be "after character".
text_position->affinity_ = ax::mojom::TextAffinity::kUpstream;
text_position = text_position->AsLeafTextPosition();
DCHECK(!text_position->IsNullPosition())
<< "Adjusting to a leaf position should never turn a non-null position "
"into a null one.";
if (!text_position->IsIgnored() && !text_position->AtStartOfAnchor()) {
std::unique_ptr<base::i18n::BreakIterator> grapheme_iterator =
text_position->GetGraphemeIterator();
// The following situation should not be possible but there are existing
// crashes in the field.
//
// TODO(nektar): Remove this workaround as soon as the source of the bug
// is identified.
if (text_position->text_offset_ > int{text_position->name_.length()})
return CreateNullPosition();
DCHECK_GE(text_position->text_offset_, 0);
DCHECK_LE(text_position->text_offset_,
int{text_position->name_.length()});
while (
!text_position->AtEndOfAnchor() &&
(!gfx::IsValidCodePointIndex(text_position->name_,
size_t{text_position->text_offset_}) ||
(grapheme_iterator && !grapheme_iterator->IsGraphemeBoundary(
size_t{text_position->text_offset_})))) {
++text_position->text_offset_;
}
// Reset the affinity to downstream, because an upstream affinity doesn't
// make sense on a leaf anchor.
text_position->affinity_ = ax::mojom::TextAffinity::kDownstream;
return text_position;
}
text_position = text_position->CreatePreviousLeafTextPosition();
while (!text_position->IsNullPosition() &&
(text_position->IsIgnored() || !text_position->MaxTextOffset())) {
text_position = text_position->CreatePreviousLeafTextPosition();
}
return text_position->CreatePositionAtEndOfAnchor();
}
// Creates a position pointing to before the next character, which is defined
// as the start of the next grapheme cluster. Also, ensures that the created
// position will not point to a low surrogate pair.
//
// A grapheme cluster is what an end-user would consider a character and it
// could include a letter with additional diacritics. It could be more than
// one Unicode code unit in length.
//
// See also http://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundaries
AXPositionInstance CreateNextCharacterPosition(
AXBoundaryBehavior boundary_behavior) const {
if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary &&
AtEndOfAnchor()) {
return Clone();
}
// There is no next character position.
AXPositionInstance text_position = AsLeafTextPositionBeforeCharacter();
if (text_position->IsNullPosition()) {
if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary ||
boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary) {
text_position = Clone();
}
return text_position;
}
if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary &&
*text_position == *this) {
return Clone();
}
DCHECK_LT(text_position->text_offset_, text_position->MaxTextOffset());
std::unique_ptr<base::i18n::BreakIterator> grapheme_iterator =
text_position->GetGraphemeIterator();
do {
++text_position->text_offset_;
} while (!text_position->AtEndOfAnchor() && grapheme_iterator &&
!grapheme_iterator->IsGraphemeBoundary(
size_t{text_position->text_offset_}));
DCHECK_GT(text_position->text_offset_, 0);
DCHECK_LE(text_position->text_offset_, text_position->MaxTextOffset());
// If the character 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, ax::mojom::MoveDirection::kForward);
} else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) {
// If the next character position crosses the current anchor boundary
// with StopAtAnchorBoundary, snap to the end of the current anchor.
return CreatePositionAtEndOfAnchor();
}
// Even if the resulting position is right on a soft line break, affinity is
// defaulted to downstream so that this method will always produce the same
// result regardless of the direction of motion or the input affinity.
text_position->affinity_ = ax::mojom::TextAffinity::kDownstream;
if (IsTreePosition())
return text_position->AsTreePosition();
return text_position;
}
// Creates a position pointing to before the previous character, which is
// defined as the start of the previous grapheme cluster. Also, ensures that
// the created position will not point to a low surrogate pair.
//
// See the comment above `CreateNextCharacterPosition` for the definition of a
// grapheme cluster.
AXPositionInstance CreatePreviousCharacterPosition(
AXBoundaryBehavior boundary_behavior) const {
if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary &&
AtStartOfAnchor()) {
return Clone();
}
// There is no previous character position.
AXPositionInstance text_position = AsLeafTextPositionAfterCharacter();
if (text_position->IsNullPosition()) {
if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary ||
boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary) {
text_position = Clone();
}
return text_position;
}
if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary &&
*text_position == *this) {
return Clone();
}
DCHECK_GT(text_position->text_offset_, 0);
std::unique_ptr<base::i18n::BreakIterator> grapheme_iterator =
text_position->GetGraphemeIterator();
do {
--text_position->text_offset_;
} while (!text_position->AtStartOfAnchor() && grapheme_iterator &&
!grapheme_iterator->IsGraphemeBoundary(
size_t{text_position->text_offset_}));
DCHECK_GE(text_position->text_offset_, 0);
DCHECK_LT(text_position->text_offset_, text_position->MaxTextOffset());
// The character boundary should be 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, ax::mojom::MoveDirection::kBackward);
} else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) {
// If the previous character position crosses the current anchor boundary
// with StopAtAnchorBoundary, snap to the start of the current anchor.
return CreatePositionAtStartOfAnchor();
}
// Even if the resulting position is right on a soft line break, affinity is
// defaulted to downstream so that this method will always produce the same
// result regardless of the direction of motion or the input affinity.
text_position->affinity_ = ax::mojom::TextAffinity::kDownstream;
if (IsTreePosition())
return text_position->AsTreePosition();
return text_position;
}
AXPositionInstance CreateNextWordStartPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryStartPosition(
boundary_behavior, ax::mojom::MoveDirection::kForward,
base::BindRepeating(&AtStartOfWordPredicate),
base::BindRepeating(&AtEndOfWordPredicate),
base::BindRepeating(&GetWordStartOffsetsFunc));
}
AXPositionInstance CreatePreviousWordStartPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryStartPosition(
boundary_behavior, ax::mojom::MoveDirection::kBackward,
base::BindRepeating(&AtStartOfWordPredicate),
base::BindRepeating(&AtEndOfWordPredicate),
base::BindRepeating(&GetWordStartOffsetsFunc));
}
// Word end positions are one past the last character of the word.
AXPositionInstance CreateNextWordEndPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryEndPosition(
boundary_behavior, ax::mojom::MoveDirection::kForward,
base::BindRepeating(&AtStartOfWordPredicate),
base::BindRepeating(&AtEndOfWordPredicate),
base::BindRepeating(&GetWordEndOffsetsFunc));
}
// Word end positions are one past the last character of the word.
AXPositionInstance CreatePreviousWordEndPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryEndPosition(
boundary_behavior, ax::mojom::MoveDirection::kBackward,
base::BindRepeating(&AtStartOfWordPredicate),
base::BindRepeating(&AtEndOfWordPredicate),
base::BindRepeating(&GetWordEndOffsetsFunc));
}
AXPositionInstance CreateNextLineStartPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryStartPosition(
boundary_behavior, ax::mojom::MoveDirection::kForward,
base::BindRepeating(&AtStartOfLinePredicate),
base::BindRepeating(&AtEndOfLinePredicate));
}
AXPositionInstance CreatePreviousLineStartPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryStartPosition(
boundary_behavior, ax::mojom::MoveDirection::kBackward,
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, ax::mojom::MoveDirection::kForward,
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, ax::mojom::MoveDirection::kBackward,
base::BindRepeating(&AtStartOfLinePredicate),
base::BindRepeating(&AtEndOfLinePredicate));
}
AXPositionInstance CreatePreviousFormatStartPosition(
AXBoundaryBehavior boundary_behavior) const {
if (IsNullPosition())
return Clone();
AXBoundaryType boundary_type = GetFormatStartBoundaryType();
if (boundary_type != AXBoundaryType::kNone) {
if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary ||
(boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary &&
boundary_type == AXBoundaryType::kDocumentStart)) {
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 &&
boundary_type == AXBoundaryType::kDocumentStart) {
// 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();
}
}
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 (boundary_type != AXBoundaryType::kDocumentStart &&
!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, ax::mojom::MoveDirection::kBackward);
} else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) {
return CreatePositionAtStartOfAnchor();
}
if (IsTextPosition())
return tree_position->AsTextPosition();
return tree_position;
}
AXPositionInstance CreateNextFormatEndPosition(
AXBoundaryBehavior boundary_behavior) const {
if (IsNullPosition())
return Clone();
AXBoundaryType boundary_type = GetFormatEndBoundaryType();
if (boundary_type != AXBoundaryType::kNone) {
if (boundary_behavior == AXBoundaryBehavior::StopIfAlreadyAtBoundary ||
(boundary_behavior == AXBoundaryBehavior::StopAtLastAnchorBoundary &&
boundary_type == AXBoundaryType::kDocumentEnd)) {
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 &&
boundary_type == AXBoundaryType::kDocumentEnd) {
// 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();
}
}
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 (boundary_type != AXBoundaryType::kDocumentEnd &&
!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, ax::mojom::MoveDirection::kForward);
} else if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) {
return CreatePositionAtEndOfAnchor();
}
if (IsTextPosition())
return tree_position->AsTextPosition();
return tree_position;
}
AXPositionInstance CreateNextParagraphStartPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryStartPosition(
boundary_behavior, ax::mojom::MoveDirection::kForward,
base::BindRepeating(&AtStartOfParagraphPredicate),
base::BindRepeating(&AtEndOfParagraphPredicate));
}
AXPositionInstance CreatePreviousParagraphStartPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryStartPosition(
boundary_behavior, ax::mojom::MoveDirection::kBackward,
base::BindRepeating(&AtStartOfParagraphPredicate),
base::BindRepeating(&AtEndOfParagraphPredicate));
}
AXPositionInstance CreateNextParagraphEndPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryEndPosition(
boundary_behavior, ax::mojom::MoveDirection::kForward,
base::BindRepeating(&AtStartOfParagraphPredicate),
base::BindRepeating(&AtEndOfParagraphPredicate));
}
AXPositionInstance CreatePreviousParagraphEndPosition(
AXBoundaryBehavior boundary_behavior) const {
AXPositionInstance previous_position = CreateBoundaryEndPosition(
boundary_behavior, ax::mojom::MoveDirection::kBackward,
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, ax::mojom::MoveDirection::kBackward,
base::BindRepeating(&AtStartOfParagraphPredicate),
base::BindRepeating(&AtEndOfParagraphPredicate));
}
}
return previous_position;
}
AXPositionInstance CreateNextPageStartPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryStartPosition(
boundary_behavior, ax::mojom::MoveDirection::kForward,
base::BindRepeating(&AtStartOfPagePredicate),
base::BindRepeating(&AtEndOfPagePredicate));
}
AXPositionInstance CreatePreviousPageStartPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryStartPosition(
boundary_behavior, ax::mojom::MoveDirection::kBackward,
base::BindRepeating(&AtStartOfPagePredicate),
base::BindRepeating(&AtEndOfPagePredicate));
}
AXPositionInstance CreateNextPageEndPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryEndPosition(
boundary_behavior, ax::mojom::MoveDirection::kForward,
base::BindRepeating(&AtStartOfPagePredicate),
base::BindRepeating(&AtEndOfPagePredicate));
}
AXPositionInstance CreatePreviousPageEndPosition(
AXBoundaryBehavior boundary_behavior) const {
return CreateBoundaryEndPosition(
boundary_behavior, ax::mojom::MoveDirection::kBackward,
base::BindRepeating(&AtStartOfPagePredicate),
base::BindRepeating(&AtEndOfPagePredicate));
}
AXPositionInstance CreateBoundaryStartPosition(
AXBoundaryBehavior boundary_behavior,
ax::mojom::MoveDirection move_direction,
BoundaryConditionPredicate at_start_condition,
BoundaryConditionPredicate at_end_condition,
BoundaryTextOffsetsFunc get_start_offsets =
BoundaryTextOffsetsFunc()) const {
AXPositionInstance text_position = AsLeafTextPosition();
if (text_position->IsNullPosition())
return text_position;
if (boundary_behavior != AXBoundaryBehavior::StopIfAlreadyAtBoundary) {
text_position =
text_position->CreateAdjacentLeafTextPosition(move_direction);
if (text_position->IsNullPosition()) {
// There is no adjacent position to move to; in such case, CrossBoundary
// behavior shall return a null position, while any other behavior shall
// fallback to return the initial position.
if (boundary_behavior == AXBoundaryBehavior::CrossBoundary)
return text_position;
return Clone();
}
}
if (!at_start_condition.Run(text_position)) {
text_position = text_position->CreatePositionAtNextOffsetBoundary(
move_direction, get_start_offsets);
while (!at_start_condition.Run(text_position)) {
AXPositionInstance next_position;
switch (move_direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
return CreateNullPosition();
case ax::mojom::MoveDirection::kBackward:
if (text_position->AtStartOfAnchor()) {
next_position = text_position->CreatePreviousLeafTextPosition();
} else {
text_position = text_position->CreatePositionAtStartOfAnchor();
DCHECK(!text_position->IsNullPosition());
continue;
}
break;
case ax::mojom::MoveDirection::kForward:
next_position = text_position->CreateNextLeafTextPosition();
break;
}
if (next_position->IsNullPosition()) {
if (boundary_behavior == AXBoundaryBehavior::StopAtAnchorBoundary) {
switch (move_direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
return CreateNullPosition();
case ax::mojom::MoveDirection::kBackward:
return CreatePositionAtStartOfAnchor()->AsUnignoredPosition(
AXPositionAdjustmentBehavior::kMoveBackward);
case ax::mojom::MoveDirection::kForward:
return CreatePositionAtEndOfAnchor()->AsUnignoredPosition(
AXPositionAdjustmentBehavior::kMoveForward);
}
}
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.
switch (move_direction) {
case ax::mojom::MoveDirection::kNone:
NOTREACHED();
return CreateNullPosition();
case ax::mojom::MoveDirection::kBackward:
text_position = text_position->CreatePositionAtStartOfAnchor();