tor-browser

TextLeafRange.cpp (99446B)

---

/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "TextLeafRange.h"

#include "HyperTextAccessible-inl.h"
#include "mozilla/a11y/Accessible.h"
#include "mozilla/a11y/CacheConstants.h"
#include "mozilla/a11y/DocAccessible.h"
#include "mozilla/a11y/DocAccessibleParent.h"
#include "mozilla/a11y/LocalAccessible.h"
#include "mozilla/BinarySearch.h"
#include "mozilla/Casting.h"
#include "mozilla/dom/AbstractRange.h"
#include "mozilla/dom/CharacterData.h"
#include "mozilla/dom/HTMLInputElement.h"
#include "mozilla/PresShell.h"
#include "mozilla/intl/Segmenter.h"
#include "mozilla/intl/WordBreaker.h"
#include "mozilla/StaticPrefs_layout.h"
#include "mozilla/TextEditor.h"
#include "nsAccUtils.h"
#include "nsBlockFrame.h"
#include "nsFocusManager.h"
#include "nsFrameSelection.h"
#include "nsIAccessiblePivot.h"
#include "nsILineIterator.h"
#include "nsINode.h"
#include "nsStyleStructInlines.h"
#include "nsTArray.h"
#include "nsTextFrame.h"
#include "nsUnicharUtils.h"
#include "Pivot.h"
#include "TextAttrs.h"
#include "TextRange.h"

using mozilla::intl::WordBreaker;
using FindWordOptions = mozilla::intl::WordBreaker::FindWordOptions;

namespace mozilla::a11y {

/*** Helpers ***/

/**
* These two functions convert between rendered and content text offsets.
* When text DOM nodes are rendered, the rendered text often does not contain
* all the whitespace from the source. For example, by default, the text
* "a   b" will be rendered as "a b"; i.e. multiple spaces are compressed to
* one. TextLeafAccessibles contain rendered text, but when we query layout, we
* need to provide offsets into the original content text. Similarly, layout
* returns content offsets, but we need to convert them to rendered offsets to
* map them to TextLeafAccessibles.
*/

static int32_t RenderedToContentOffset(LocalAccessible* aAcc,
                                      uint32_t aRenderedOffset) {
 nsTextFrame* frame = do_QueryFrame(aAcc->GetFrame());
 if (!frame) {
   MOZ_ASSERT(!aAcc->HasOwnContent() || aAcc->IsHTMLBr(),
              "No text frame because this is a XUL label[value] text leaf or "
              "a BR element.");
   return static_cast<int32_t>(aRenderedOffset);
 }

 if (frame->StyleText()->WhiteSpaceIsSignificant() &&
     frame->StyleText()->NewlineIsSignificant(frame)) {
   // Spaces and new lines aren't altered, so the content and rendered offsets
   // are the same. This happens in pre-formatted text and text fields.
   return static_cast<int32_t>(aRenderedOffset);
 }

 nsIFrame::RenderedText text =
     frame->GetRenderedText(aRenderedOffset, aRenderedOffset + 1,
                            nsIFrame::TextOffsetType::OffsetsInRenderedText,
                            nsIFrame::TrailingWhitespace::DontTrim);
 return text.mOffsetWithinNodeText;
}

static uint32_t ContentToRenderedOffset(LocalAccessible* aAcc,
                                       int32_t aContentOffset) {
 nsTextFrame* frame = do_QueryFrame(aAcc->GetFrame());
 if (!frame) {
   MOZ_ASSERT(!aAcc->HasOwnContent(),
              "No text frame because this is a XUL label[value] text leaf.");
   return aContentOffset;
 }

 if (frame->StyleText()->WhiteSpaceIsSignificant() &&
     frame->StyleText()->NewlineIsSignificant(frame)) {
   // Spaces and new lines aren't altered, so the content and rendered offsets
   // are the same. This happens in pre-formatted text and text fields.
   return aContentOffset;
 }

 nsIFrame::RenderedText text =
     frame->GetRenderedText(aContentOffset, aContentOffset + 1,
                            nsIFrame::TextOffsetType::OffsetsInContentText,
                            nsIFrame::TrailingWhitespace::DontTrim);
 return text.mOffsetWithinNodeRenderedText;
}

class LeafRule : public PivotRule {
public:
 explicit LeafRule(bool aIgnoreListItemMarker)
     : mIgnoreListItemMarker(aIgnoreListItemMarker) {}

 virtual uint16_t Match(Accessible* aAcc) override {
   if (aAcc->IsOuterDoc()) {
     // Treat an embedded doc as a single character in this document, but do
     // not descend inside it.
     return nsIAccessibleTraversalRule::FILTER_MATCH |
            nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
   }

   if (mIgnoreListItemMarker && aAcc->Role() == roles::LISTITEM_MARKER) {
     // Ignore list item markers if configured to do so.
     return nsIAccessibleTraversalRule::FILTER_IGNORE;
   }

   // We deliberately include Accessibles such as empty input elements and
   // empty containers, as these can be at the start of a line.
   if (!aAcc->HasChildren()) {
     return nsIAccessibleTraversalRule::FILTER_MATCH;
   }
   return nsIAccessibleTraversalRule::FILTER_IGNORE;
 }

private:
 bool mIgnoreListItemMarker;
};

static HyperTextAccessible* HyperTextFor(LocalAccessible* aAcc) {
 for (LocalAccessible* acc = aAcc; acc; acc = acc->LocalParent()) {
   if (HyperTextAccessible* ht = acc->AsHyperText()) {
     return ht;
   }
 }
 return nullptr;
}

static Accessible* NextLeaf(Accessible* aOrigin, bool aIsEditable = false,
                           bool aIgnoreListItemMarker = false) {
 MOZ_ASSERT(aOrigin);
 Accessible* doc = nsAccUtils::DocumentFor(aOrigin);
 Pivot pivot(doc);
 auto rule = LeafRule(aIgnoreListItemMarker);
 Accessible* leaf = pivot.Next(aOrigin, rule);
 if (aIsEditable && leaf) {
   return leaf->Parent() && (leaf->Parent()->State() & states::EDITABLE)
              ? leaf
              : nullptr;
 }
 return leaf;
}

static Accessible* PrevLeaf(Accessible* aOrigin, bool aIsEditable = false,
                           bool aIgnoreListItemMarker = false) {
 MOZ_ASSERT(aOrigin);
 Accessible* doc = nsAccUtils::DocumentFor(aOrigin);
 Pivot pivot(doc);
 auto rule = LeafRule(aIgnoreListItemMarker);
 Accessible* leaf = pivot.Prev(aOrigin, rule);
 if (aIsEditable && leaf) {
   return leaf->Parent() && (leaf->Parent()->State() & states::EDITABLE)
              ? leaf
              : nullptr;
 }
 return leaf;
}

static nsIFrame* GetFrameInBlock(const LocalAccessible* aAcc) {
 dom::HTMLInputElement* input =
     dom::HTMLInputElement::FromNodeOrNull(aAcc->GetContent());
 if (!input) {
   if (LocalAccessible* parent = aAcc->LocalParent()) {
     input = dom::HTMLInputElement::FromNodeOrNull(parent->GetContent());
   }
 }

 if (input) {
   // If this is a single line input (or a leaf of an input) we want to return
   // the top frame of the input element and not the text leaf's frame because
   // the leaf may be inside of an embedded block frame in the input's shadow
   // DOM that we aren't interested in.
   return input->GetPrimaryFrame();
 }

 return aAcc->GetFrame();
}

/**
* Returns true if the given frames are on different lines.
*/
static bool AreFramesOnDifferentLines(nsIFrame* aFrame1, nsIFrame* aFrame2) {
 MOZ_ASSERT(aFrame1 && aFrame2);
 if (aFrame1 == aFrame2) {
   // This can happen if two Accessibles share the same frame; e.g. image maps.
   return false;
 }
 auto [block1, lineFrame1] = aFrame1->GetContainingBlockForLine(
     /* aLockScroll */ false);
 if (!block1) {
   // Error; play it safe.
   return true;
 }
 auto [block2, lineFrame2] = aFrame2->GetContainingBlockForLine(
     /* aLockScroll */ false);
 if (lineFrame1 == lineFrame2) {
   return false;
 }
 if (block1 != block2) {
   // These frames are in different blocks, so they're on different lines.
   return true;
 }
 if (nsBlockFrame* block = do_QueryFrame(block1)) {
   // If we have a block frame, it's faster for us to use
   // BlockInFlowLineIterator because it uses the line cursor.
   bool found = false;
   block->SetupLineCursorForQuery();
   nsBlockInFlowLineIterator it1(block, lineFrame1, &found);
   if (!found) {
     // Error; play it safe.
     return true;
   }
   found = false;
   nsBlockInFlowLineIterator it2(block, lineFrame2, &found);
   return !found || it1.GetLineList() != it2.GetLineList() ||
          it1.GetLine() != it2.GetLine();
 }
 AutoAssertNoDomMutations guard;
 nsILineIterator* it = block1->GetLineIterator();
 MOZ_ASSERT(it, "GetLineIterator impl in line-container blocks is infallible");
 int32_t line1 = it->FindLineContaining(lineFrame1);
 if (line1 < 0) {
   // Error; play it safe.
   return true;
 }
 int32_t line2 = it->FindLineContaining(lineFrame2, line1);
 return line1 != line2;
}

static bool IsLocalAccAtLineStart(LocalAccessible* aAcc) {
 if (aAcc->NativeRole() == roles::LISTITEM_MARKER) {
   // A bullet always starts a line.
   return true;
 }
 // Splitting of content across lines is handled by layout.
 // nsIFrame::IsLogicallyAtLineEdge queries whether a frame is the first frame
 // on its line. However, we can't use that because the first frame on a line
 // might not be included in the a11y tree; e.g. an empty span, or space
 // in the DOM after a line break which is stripped when rendered. Instead, we
 // get the line number for this Accessible's frame and the line number for the
 // previous leaf Accessible's frame and compare them.
 Accessible* prev = PrevLeaf(aAcc);
 LocalAccessible* prevLocal = prev ? prev->AsLocal() : nullptr;
 if (!prevLocal) {
   // There's nothing before us, so this is the start of the first line.
   return true;
 }
 if (prevLocal->NativeRole() == roles::LISTITEM_MARKER) {
   // If there is  a bullet immediately before us and we're inside the same
   // list item, this is not the start of a line.
   LocalAccessible* listItem = prevLocal->LocalParent();
   MOZ_ASSERT(listItem);
   LocalAccessible* doc = listItem->Document();
   MOZ_ASSERT(doc);
   for (LocalAccessible* parent = aAcc->LocalParent(); parent && parent != doc;
        parent = parent->LocalParent()) {
     if (parent == listItem) {
       return false;
     }
   }
 }

 nsIFrame* thisFrame = GetFrameInBlock(aAcc);
 if (!thisFrame) {
   return false;
 }

 nsIFrame* prevFrame = GetFrameInBlock(prevLocal);
 if (!prevFrame) {
   return false;
 }

 // The previous leaf might cross lines. We want to compare against the last
 // line.
 prevFrame = prevFrame->LastContinuation();
 // if the lines are different, that means there's nothing before us on the
 // same line, so we're at the start.
 return AreFramesOnDifferentLines(thisFrame, prevFrame);
}

/**
* There are many kinds of word break, but we only need to treat punctuation and
* space specially.
*/
enum WordBreakClass { eWbcSpace = 0, eWbcPunct, eWbcOther };

static WordBreakClass GetWordBreakClass(char16_t aChar) {
 // Based on IsSelectionInlineWhitespace and IsSelectionNewline in
 // layout/generic/nsTextFrame.cpp.
 const char16_t kCharNbsp = 0xA0;
 switch (aChar) {
   case ' ':
   case kCharNbsp:
   case '\t':
   case '\f':
   case '\n':
   case '\r':
     return eWbcSpace;
   default:
     break;
 }
 return mozilla::IsPunctuationForWordSelect(aChar) ? eWbcPunct : eWbcOther;
}

/**
* Words can cross Accessibles. To work out whether we're at the start of a
* word, we might have to check the previous leaf. This class handles querying
* the previous WordBreakClass, crossing Accessibles if necessary.
*/
class PrevWordBreakClassWalker {
public:
 PrevWordBreakClassWalker(Accessible* aAcc, const nsAString& aText,
                          int32_t aOffset)
     : mAcc(aAcc), mText(aText), mOffset(aOffset) {
   mClass = GetWordBreakClass(mText.CharAt(mOffset));
 }

 WordBreakClass CurClass() { return mClass; }

 Maybe<WordBreakClass> PrevClass() {
   for (;;) {
     if (!PrevChar()) {
       return Nothing();
     }
     WordBreakClass curClass = GetWordBreakClass(mText.CharAt(mOffset));
     if (curClass != mClass) {
       mClass = curClass;
       return Some(curClass);
     }
   }
   MOZ_ASSERT_UNREACHABLE();
   return Nothing();
 }

 bool IsStartOfGroup() {
   if (!PrevChar()) {
     // There are no characters before us.
     return true;
   }
   WordBreakClass curClass = GetWordBreakClass(mText.CharAt(mOffset));
   // We wanted to peek at the previous character, not really move to it.
   ++mOffset;
   return curClass != mClass;
 }

private:
 bool PrevChar() {
   if (mOffset > 0) {
     --mOffset;
     return true;
   }
   if (!mAcc) {
     // PrevChar was called already and failed.
     return false;
   }
   mAcc = PrevLeaf(mAcc);
   if (!mAcc) {
     return false;
   }
   mText.Truncate();
   mAcc->AppendTextTo(mText);
   mOffset = static_cast<int32_t>(mText.Length()) - 1;
   return true;
 }

 Accessible* mAcc;
 nsAutoString mText;
 int32_t mOffset;
 WordBreakClass mClass;
};

/**
* WordBreaker breaks at all space, punctuation, etc. We want to emulate
* layout, so that's not what we want. This function determines whether this
* is acceptable as the start of a word for our purposes.
*/
static bool IsAcceptableWordStart(Accessible* aAcc, const nsAutoString& aText,
                                 int32_t aOffset) {
 PrevWordBreakClassWalker walker(aAcc, aText, aOffset);
 if (!walker.IsStartOfGroup()) {
   // If we're not at the start of a WordBreaker group, this can't be the
   // start of a word.
   return false;
 }
 WordBreakClass curClass = walker.CurClass();
 if (curClass == eWbcSpace) {
   // Space isn't the start of a word.
   return false;
 }
 Maybe<WordBreakClass> prevClass = walker.PrevClass();
 if (curClass == eWbcPunct && (!prevClass || prevClass.value() != eWbcSpace)) {
   // Punctuation isn't the start of a word (unless it is after space).
   return false;
 }
 if (!prevClass || prevClass.value() != eWbcPunct) {
   // If there's nothing before this or the group before this isn't
   // punctuation, this is the start of a word.
   return true;
 }
 // At this point, we know the group before this is punctuation.
 if (!StaticPrefs::layout_word_select_stop_at_punctuation()) {
   // When layout.word_select.stop_at_punctuation is false (defaults to true),
   // if there is punctuation before this, this is not the start of a word.
   return false;
 }
 Maybe<WordBreakClass> prevPrevClass = walker.PrevClass();
 if (!prevPrevClass || prevPrevClass.value() == eWbcSpace) {
   // If there is punctuation before this and space (or nothing) before the
   // punctuation, this is not the start of a word.
   return false;
 }
 return true;
}

class BlockRule : public PivotRule {
public:
 virtual uint16_t Match(Accessible* aAcc) override {
   if (RefPtr<nsAtom>(aAcc->DisplayStyle()) == nsGkAtoms::block ||
       aAcc->IsHTMLListItem() || aAcc->IsTableRow() || aAcc->IsTableCell()) {
     return nsIAccessibleTraversalRule::FILTER_MATCH;
   }
   return nsIAccessibleTraversalRule::FILTER_IGNORE;
 }
};

/**
* Find DOM ranges which map to text attributes overlapping the requested
* LocalAccessible and offsets. This includes ranges that begin or end outside
* of the given LocalAccessible. Note that the offset arguments are rendered
* offsets, but because the returned ranges are DOM ranges, those offsets are
* content offsets. See the documentation for
* dom::Selection::GetRangesForIntervalArray for information about the
* aAllowAdjacent argument.
*/
static nsTArray<std::pair<nsTArray<dom::AbstractRange*>, nsStaticAtom*>>
FindDOMTextOffsetAttributes(LocalAccessible* aAcc, int32_t aRenderedStart,
                           int32_t aRenderedEnd, bool aAllowAdjacent = false) {
 nsTArray<std::pair<nsTArray<dom::AbstractRange*>, nsStaticAtom*>> result;
 if (!aAcc->IsTextLeaf() || !aAcc->HasOwnContent() ||
     !aAcc->GetContent()->IsText()) {
   return result;
 }
 nsIFrame* frame = aAcc->GetFrame();
 RefPtr<nsFrameSelection> frameSel =
     frame ? frame->GetFrameSelection() : nullptr;
 if (!frameSel) {
   return result;
 }
 nsINode* node = aAcc->GetNode();
 uint32_t contentStart = RenderedToContentOffset(aAcc, aRenderedStart);
 uint32_t contentEnd =
     aRenderedEnd == nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT
         ? dom::CharacterData::FromNode(node)->TextLength()
         : RenderedToContentOffset(aAcc, aRenderedEnd);
 const std::pair<mozilla::SelectionType, nsStaticAtom*>
     kSelectionTypesToAttributes[] = {
         {SelectionType::eSpellCheck, nsGkAtoms::spelling},
         {SelectionType::eTargetText, nsGkAtoms::mark},
     };
 size_t highlightCount = frameSel->HighlightSelectionCount();
 result.SetCapacity(std::size(kSelectionTypesToAttributes) + highlightCount);

 auto appendRanges = [&](dom::Selection* aDomSel, nsStaticAtom* aAttr) {
   nsTArray<dom::AbstractRange*> domRanges;
   aDomSel->GetAbstractRangesForIntervalArray(
       node, contentStart, node, contentEnd, aAllowAdjacent, &domRanges);
   if (!domRanges.IsEmpty()) {
     result.AppendElement(std::make_pair(std::move(domRanges), aAttr));
   }
 };

 for (auto [selType, attr] : kSelectionTypesToAttributes) {
   dom::Selection* domSel = frameSel->GetSelection(selType);
   if (!domSel) {
     continue;
   }
   appendRanges(domSel, attr);
 }

 for (size_t h = 0; h < highlightCount; ++h) {
   RefPtr<dom::Selection> domSel = frameSel->HighlightSelection(h);
   MOZ_ASSERT(domSel);
   nsStaticAtom* attr = nullptr;
   MOZ_ASSERT(domSel->HighlightSelectionData().mHighlight);
   switch (domSel->HighlightSelectionData().mHighlight->Type()) {
     case dom::HighlightType::Highlight:
       attr = nsGkAtoms::mark;
       break;
     case dom::HighlightType::Spelling_error:
       attr = nsGkAtoms::spelling;
       break;
     case dom::HighlightType::Grammar_error:
       attr = nsGkAtoms::grammar;
       break;
   }
   MOZ_ASSERT(attr);
   appendRanges(domSel, attr);
 }

 return result;
}

/**
* Given two DOM nodes get DOM Selection object that is common
* to both of them.
*/
static dom::Selection* GetDOMSelection(const nsIContent* aStartContent,
                                      const nsIContent* aEndContent) {
 nsIFrame* startFrame = aStartContent->GetPrimaryFrame();
 const nsFrameSelection* startFrameSel =
     startFrame ? startFrame->GetConstFrameSelection() : nullptr;
 nsIFrame* endFrame = aEndContent->GetPrimaryFrame();
 const nsFrameSelection* endFrameSel =
     endFrame ? endFrame->GetConstFrameSelection() : nullptr;

 if (startFrameSel != endFrameSel) {
   // Start and end point don't share the same selection state.
   // This could happen when both points aren't in the same editable.
   return nullptr;
 }

 return startFrameSel ? &startFrameSel->NormalSelection() : nullptr;
}

std::pair<nsIContent*, uint32_t> TextLeafPoint::ToDOMPoint(
   bool aIncludeGenerated) const {
 if (!(*this) || !mAcc->IsLocal()) {
   MOZ_ASSERT_UNREACHABLE("Invalid point");
   return {nullptr, 0};
 }

 nsIContent* content = mAcc->AsLocal()->GetContent();
 nsIFrame* frame = content ? content->GetPrimaryFrame() : nullptr;
 MOZ_ASSERT(frame);

 if (!aIncludeGenerated && frame && frame->IsGeneratedContentFrame()) {
   // List markers accessibles represent the generated content element,
   // before/after text accessibles represent the child text nodes.
   auto generatedElement = content->IsGeneratedContentContainerForMarker()
                               ? content
                               : content->GetParentElement();
   auto parent = generatedElement ? generatedElement->GetParent() : nullptr;
   MOZ_ASSERT(parent);
   if (parent) {
     if (generatedElement->IsGeneratedContentContainerForAfter()) {
       // Use the end offset of the parent element for trailing generated
       // content.
       return {parent, parent->GetChildCount()};
     }

     if (generatedElement->IsGeneratedContentContainerForBefore() ||
         generatedElement->IsGeneratedContentContainerForMarker()) {
       // Use the start offset of the parent element for leading generated
       // content.
       return {parent, 0};
     }

     MOZ_ASSERT_UNREACHABLE("Unknown generated content type!");
   }
 }

 if (mAcc->IsTextLeaf()) {
   // For text nodes, DOM uses a character offset within the node.
   return {content, RenderedToContentOffset(mAcc->AsLocal(), mOffset)};
 }

 if (!mAcc->IsHyperText()) {
   // For non-text nodes (e.g. images), DOM points use the child index within
   // the parent. mOffset could be 0 (for the start of the node) or 1 (for the
   // end of the node). mOffset could be 1 if this is the last Accessible in a
   // container and the point is at the end of the container.
   MOZ_ASSERT(mOffset == 0 || mOffset == 1);
   nsIContent* parent = content->GetParent();
   MOZ_ASSERT(parent);
   // ComputeIndexOf() could return Nothing if this is an anonymous child.
   if (auto childIndex = parent->ComputeIndexOf(content)) {
     return {parent, mOffset == 0 ? *childIndex : *childIndex + 1};
   }
 }

 // This could be an empty editable container, whitespace or an empty doc. In
 // any case, the offset inside should be 0.
 MOZ_ASSERT(mOffset == 0);

 if (RefPtr<TextControlElement> textControlElement =
         TextControlElement::FromNodeOrNull(content)) {
   // This is an empty input, use the shadow root's element.
   if (RefPtr<TextEditor> textEditor = textControlElement->GetTextEditor()) {
     if (textEditor->IsEmpty()) {
       MOZ_ASSERT(mOffset == 0);
       return {textEditor->GetRoot(), 0};
     }
   }
 }

 return {content, 0};
}

static bool IsLineBreakContinuation(nsTextFrame* aContinuation) {
 // A fluid continuation always means a new line.
 if (aContinuation->HasAnyStateBits(NS_FRAME_IS_FLUID_CONTINUATION)) {
   return true;
 }
 // If both this continuation and the previous continuation are bidi
 // continuations, this continuation might be both a bidi split and on a new
 // line.
 if (!aContinuation->HasAnyStateBits(NS_FRAME_IS_BIDI)) {
   return true;
 }
 nsTextFrame* prev = aContinuation->GetPrevContinuation();
 if (!prev) {
   // aContinuation is the primary frame. We can't be sure if this starts a new
   // line, as there might be other nodes before it. That is handled by
   // IsLocalAccAtLineStart.
   return false;
 }
 if (!prev->HasAnyStateBits(NS_FRAME_IS_BIDI)) {
   return true;
 }
 return AreFramesOnDifferentLines(aContinuation, prev);
}

static bool IsCaretValid(TextLeafPoint aPoint) {
 Accessible* acc = aPoint.mAcc;
 if (!acc->IsHyperText()) {
   acc = acc->Parent();
 }
 if (!(acc->State() & states::EDITABLE)) {
   return true;
 }
 // The caret is within editable content.
 Accessible* focus = FocusMgr() ? FocusMgr()->FocusedAccessible() : nullptr;
 if (!focus) {
   return false;
 }
 // If the focus isn't an editor, the caret can't be inside an editor. This
 // can happen, for example, when a text input is the last element in a
 // container and a user clicks in the empty area at the end of the container.
 // In this case, the caret is actually at the end of the container outside the
 // input. This can also happen if there is an empty area in a container before
 // an input and a user clicks there. TextLeafPoint can't represent either of
 // these cases and it's generally not useful. We must not normalize this to
 // the nearest leaf because this would put the caret inside an editor which
 // isn't focused. Instead, we pretend there is no caret. See bug 1950748 for
 // more details.
 return focus->State() & states::EDITABLE;
}

/*** TextLeafPoint ***/

TextLeafPoint::TextLeafPoint(Accessible* aAcc, int32_t aOffset) {
 MOZ_ASSERT(aOffset >= 0 ||
            aOffset == nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT);
 if (!aAcc) {
   // Construct an invalid point.
   mAcc = nullptr;
   mOffset = 0;
   return;
 }

 // Even though an OuterDoc contains a document, we treat it as a leaf because
 // we don't want to move into another document.
 if (!aAcc->IsOuterDoc() && aAcc->HasChildren()) {
   // Find a leaf. This might not necessarily be a TextLeafAccessible; it
   // could be an empty container.
   auto GetChild = [&aOffset](Accessible* acc) -> Accessible* {
     if (acc->IsOuterDoc()) {
       return nullptr;
     }
     return aOffset != nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT
                ? acc->FirstChild()
                : acc->LastChild();
   };

   for (Accessible* acc = GetChild(aAcc); acc; acc = GetChild(acc)) {
     mAcc = acc;
   }
   mOffset = aOffset != nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT
                 ? 0
                 : nsAccUtils::TextLength(mAcc);
   return;
 }
 mAcc = aAcc;
 mOffset = aOffset != nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT
               ? aOffset
               : nsAccUtils::TextLength(mAcc);
}

bool TextLeafPoint::operator<(const TextLeafPoint& aPoint) const {
 if (mAcc == aPoint.mAcc) {
   return mOffset < aPoint.mOffset;
 }
 return mAcc->IsBefore(aPoint.mAcc);
}

bool TextLeafPoint::operator<=(const TextLeafPoint& aPoint) const {
 return *this == aPoint || *this < aPoint;
}

bool TextLeafPoint::IsDocEdge(nsDirection aDirection) const {
 if (aDirection == eDirPrevious) {
   return mOffset == 0 && !PrevLeaf(mAcc);
 }

 return mOffset == static_cast<int32_t>(nsAccUtils::TextLength(mAcc)) &&
        !NextLeaf(mAcc);
}

bool TextLeafPoint::IsLeafAfterListItemMarker() const {
 Accessible* prev = PrevLeaf(mAcc);
 return prev && prev->Role() == roles::LISTITEM_MARKER &&
        prev->Parent()->IsAncestorOf(mAcc);
}

bool TextLeafPoint::IsEmptyLastLine() const {
 if (mAcc->IsHTMLBr() && mOffset == 1) {
   return true;
 }
 if (!mAcc->IsTextLeaf()) {
   return false;
 }
 if (mOffset < static_cast<int32_t>(nsAccUtils::TextLength(mAcc))) {
   return false;
 }
 nsAutoString text;
 mAcc->AppendTextTo(text, mOffset - 1, 1);
 return text.CharAt(0) == '\n';
}

char16_t TextLeafPoint::GetChar() const {
 nsAutoString text;
 mAcc->AppendTextTo(text, mOffset, 1);
 return text.CharAt(0);
}

TextLeafPoint TextLeafPoint::FindPrevLineStartSameLocalAcc(
   bool aIncludeOrigin) const {
 LocalAccessible* acc = mAcc->AsLocal();
 MOZ_ASSERT(acc);
 if (mOffset == 0) {
   if (aIncludeOrigin && IsLocalAccAtLineStart(acc)) {
     return *this;
   }
   return TextLeafPoint();
 }
 nsIFrame* frame = acc->GetFrame();
 if (!frame) {
   // This can happen if this is an empty element with display: contents. In
   // that case, this Accessible contains no lines.
   return TextLeafPoint();
 }
 if (!frame->IsTextFrame()) {
   if (IsLocalAccAtLineStart(acc)) {
     return TextLeafPoint(acc, 0);
   }
   return TextLeafPoint();
 }
 // Each line of a text node is rendered as a continuation frame. Get the
 // continuation containing the origin.
 int32_t origOffset = mOffset;
 origOffset = RenderedToContentOffset(acc, origOffset);
 nsTextFrame* continuation = nullptr;
 int32_t unusedOffsetInContinuation = 0;
 frame->GetChildFrameContainingOffset(
     origOffset, true, &unusedOffsetInContinuation, (nsIFrame**)&continuation);
 MOZ_ASSERT(continuation);
 int32_t lineStart = continuation->GetContentOffset();
 if (lineStart > 0 && (
                          // A line starts at the origin, but the caller
                          // doesn't want this included.
                          (!aIncludeOrigin && lineStart == origOffset) ||
                          !IsLineBreakContinuation(continuation))) {
   // Go back one more, skipping continuations that aren't line breaks or the
   // primary frame.
   for (nsTextFrame* prev = continuation->GetPrevContinuation(); prev;
        prev = prev->GetPrevContinuation()) {
     continuation = prev;
     if (IsLineBreakContinuation(continuation)) {
       break;
     }
   }
   MOZ_ASSERT(continuation);
   lineStart = continuation->GetContentOffset();
 }
 MOZ_ASSERT(lineStart >= 0);
 MOZ_ASSERT(lineStart == 0 || IsLineBreakContinuation(continuation));
 if (lineStart == 0 && !IsLocalAccAtLineStart(acc)) {
   // This is the first line of this text node, but there is something else
   // on the same line before this text node, so don't return this as a line
   // start.
   return TextLeafPoint();
 }
 lineStart = static_cast<int32_t>(ContentToRenderedOffset(acc, lineStart));
 return TextLeafPoint(acc, lineStart);
}

TextLeafPoint TextLeafPoint::FindNextLineStartSameLocalAcc(
   bool aIncludeOrigin) const {
 LocalAccessible* acc = mAcc->AsLocal();
 MOZ_ASSERT(acc);
 if (aIncludeOrigin && mOffset == 0 && IsLocalAccAtLineStart(acc)) {
   return *this;
 }
 nsIFrame* frame = acc->GetFrame();
 if (!frame) {
   // This can happen if this is an empty element with display: contents. In
   // that case, this Accessible contains no lines.
   return TextLeafPoint();
 }
 if (!frame->IsTextFrame()) {
   // There can't be multiple lines in a non-text leaf.
   return TextLeafPoint();
 }
 // Each line of a text node is rendered as a continuation frame. Get the
 // continuation containing the origin.
 int32_t origOffset = mOffset;
 origOffset = RenderedToContentOffset(acc, origOffset);
 nsTextFrame* continuation = nullptr;
 int32_t unusedOffsetInContinuation = 0;
 frame->GetChildFrameContainingOffset(
     origOffset, true, &unusedOffsetInContinuation, (nsIFrame**)&continuation);
 MOZ_ASSERT(continuation);
 if (
     // A line starts at the origin and the caller wants this included.
     aIncludeOrigin && continuation->GetContentOffset() == origOffset &&
     IsLineBreakContinuation(continuation) &&
     // If this is the first line of this text node (offset 0), don't treat it
     // as a line start if there's something else on the line before this text
     // node.
     !(origOffset == 0 && !IsLocalAccAtLineStart(acc))) {
   return *this;
 }
 // Get the next continuation, skipping continuations that aren't line breaks.
 while ((continuation = continuation->GetNextContinuation())) {
   if (IsLineBreakContinuation(continuation)) {
     break;
   }
 }
 if (!continuation) {
   return TextLeafPoint();
 }
 int32_t lineStart = continuation->GetContentOffset();
 lineStart = static_cast<int32_t>(ContentToRenderedOffset(acc, lineStart));
 return TextLeafPoint(acc, lineStart);
}

TextLeafPoint TextLeafPoint::FindLineStartSameRemoteAcc(
   nsDirection aDirection, bool aIncludeOrigin) const {
 RemoteAccessible* acc = mAcc->AsRemote();
 MOZ_ASSERT(acc);
 auto lines = acc->GetCachedTextLines();
 if (!lines) {
   return TextLeafPoint();
 }
 size_t index;
 // If BinarySearch returns true, mOffset is in the array and index points at
 // it. If BinarySearch returns false, mOffset is not in the array and index
 // points at the next line start after mOffset.
 if (BinarySearch(*lines, 0, lines->Length(), mOffset, &index)) {
   if (aIncludeOrigin) {
     return *this;
   }
   if (aDirection == eDirNext) {
     // We don't want to include the origin. Get the next line start.
     ++index;
   }
 }
 MOZ_ASSERT(index <= lines->Length());
 if ((aDirection == eDirNext && index == lines->Length()) ||
     (aDirection == eDirPrevious && index == 0)) {
   return TextLeafPoint();
 }
 // index points at the line start after mOffset.
 if (aDirection == eDirPrevious) {
   --index;
 }
 return TextLeafPoint(mAcc, lines->ElementAt(index));
}

TextLeafPoint TextLeafPoint::FindLineStartSameAcc(
   nsDirection aDirection, bool aIncludeOrigin,
   bool aIgnoreListItemMarker) const {
 TextLeafPoint boundary;
 if (aIgnoreListItemMarker && aIncludeOrigin && mOffset == 0 &&
     IsLeafAfterListItemMarker()) {
   // If:
   // (1) we are ignoring list markers
   // (2) we should include origin
   // (3) we are at the start of a leaf that follows a list item marker
   // ...then return this point.
   return *this;
 }

 if (mAcc->IsLocal()) {
   boundary = aDirection == eDirNext
                  ? FindNextLineStartSameLocalAcc(aIncludeOrigin)
                  : FindPrevLineStartSameLocalAcc(aIncludeOrigin);
 } else {
   boundary = FindLineStartSameRemoteAcc(aDirection, aIncludeOrigin);
 }

 if (aIgnoreListItemMarker && aDirection == eDirPrevious && !boundary &&
     mOffset != 0 && IsLeafAfterListItemMarker()) {
   // If:
   // (1) we are ignoring list markers
   // (2) we are searching backwards in accessible
   // (3) we did not find a line start before this point
   // (4) we are in a leaf that follows a list item marker
   // ...then return the first point in this accessible.
   boundary = TextLeafPoint(mAcc, 0);
 }

 return boundary;
}

TextLeafPoint TextLeafPoint::FindPrevWordStartSameAcc(
   bool aIncludeOrigin) const {
 if (mOffset == 0 && !aIncludeOrigin) {
   // We can't go back any further and the caller doesn't want the origin
   // included, so there's nothing more to do.
   return TextLeafPoint();
 }
 nsAutoString text;
 mAcc->AppendTextTo(text);
 TextLeafPoint lineStart = *this;
 if (!aIncludeOrigin || (lineStart.mOffset == 1 && text.Length() == 1 &&
                         text.CharAt(0) == '\n')) {
   // We're not interested in a line that starts here, either because
   // aIncludeOrigin is false or because we're at the end of a line break
   // node.
   --lineStart.mOffset;
 }
 // A word never starts with a line feed character. If there are multiple
 // consecutive line feed characters and we're after the first of them, the
 // previous line start will be a line feed character. Skip this and any prior
 // consecutive line feed first.
 for (; lineStart.mOffset >= 0 && text.CharAt(lineStart.mOffset) == '\n';
      --lineStart.mOffset) {
 }
 if (lineStart.mOffset < 0) {
   // There's no line start for our purposes.
   lineStart = TextLeafPoint();
 } else {
   lineStart =
       lineStart.FindLineStartSameAcc(eDirPrevious, /* aIncludeOrigin */ true);
 }
 // Keep walking backward until we find an acceptable word start.
 intl::WordRange word;
 if (mOffset == 0) {
   word.mBegin = 0;
 } else if (mOffset == static_cast<int32_t>(text.Length())) {
   word = WordBreaker::FindWord(
       text, mOffset - 1,
       StaticPrefs::layout_word_select_stop_at_punctuation()
           ? FindWordOptions::StopAtPunctuation
           : FindWordOptions::None);
 } else {
   word = WordBreaker::FindWord(
       text, mOffset,
       StaticPrefs::layout_word_select_stop_at_punctuation()
           ? FindWordOptions::StopAtPunctuation
           : FindWordOptions::None);
 }
 for (;; word = WordBreaker::FindWord(
             text, word.mBegin - 1,
             StaticPrefs::layout_word_select_stop_at_punctuation()
                 ? FindWordOptions::StopAtPunctuation
                 : FindWordOptions::None)) {
   if (!aIncludeOrigin && static_cast<int32_t>(word.mBegin) == mOffset) {
     // A word possibly starts at the origin, but the caller doesn't want this
     // included.
     MOZ_ASSERT(word.mBegin != 0);
     continue;
   }
   if (lineStart && static_cast<int32_t>(word.mBegin) < lineStart.mOffset) {
     // A line start always starts a new word.
     return lineStart;
   }
   if (IsAcceptableWordStart(mAcc, text, static_cast<int32_t>(word.mBegin))) {
     break;
   }
   if (word.mBegin == 0) {
     // We can't go back any further.
     if (lineStart) {
       // A line start always starts a new word.
       return lineStart;
     }
     return TextLeafPoint();
   }
 }
 return TextLeafPoint(mAcc, static_cast<int32_t>(word.mBegin));
}

TextLeafPoint TextLeafPoint::FindNextWordStartSameAcc(
   bool aIncludeOrigin) const {
 nsAutoString text;
 mAcc->AppendTextTo(text);
 int32_t wordStart = mOffset;
 if (aIncludeOrigin) {
   if (wordStart == 0) {
     if (IsAcceptableWordStart(mAcc, text, 0)) {
       return *this;
     }
   } else {
     // The origin might start a word, so search from just before it.
     --wordStart;
   }
 }
 TextLeafPoint lineStart = FindLineStartSameAcc(eDirNext, aIncludeOrigin);
 if (lineStart) {
   // A word never starts with a line feed character. If there are multiple
   // consecutive line feed characters, lineStart will point at the second of
   // them. Skip this and any subsequent consecutive line feed.
   for (; lineStart.mOffset < static_cast<int32_t>(text.Length()) &&
          text.CharAt(lineStart.mOffset) == '\n';
        ++lineStart.mOffset) {
   }
   if (lineStart.mOffset == static_cast<int32_t>(text.Length())) {
     // There's no line start for our purposes.
     lineStart = TextLeafPoint();
   }
 }
 // Keep walking forward until we find an acceptable word start.
 intl::WordBreakIteratorUtf16 wordBreakIter(text);
 int32_t previousPos = wordStart;
 Maybe<uint32_t> nextBreak = wordBreakIter.Seek(wordStart);
 for (;;) {
   if (!nextBreak || *nextBreak == text.Length()) {
     if (lineStart) {
       // A line start always starts a new word.
       return lineStart;
     }
     if (StaticPrefs::layout_word_select_stop_at_punctuation()) {
       // If layout.word_select.stop_at_punctuation is true, we have to look
       // for punctuation class since it may not break state in UAX#29.
       for (int32_t i = previousPos + 1;
            i < static_cast<int32_t>(text.Length()); i++) {
         if (IsAcceptableWordStart(mAcc, text, i)) {
           return TextLeafPoint(mAcc, i);
         }
       }
     }
     return TextLeafPoint();
   }
   wordStart = AssertedCast<int32_t>(*nextBreak);
   if (lineStart && wordStart > lineStart.mOffset) {
     // A line start always starts a new word.
     return lineStart;
   }
   if (IsAcceptableWordStart(mAcc, text, wordStart)) {
     break;
   }

   if (StaticPrefs::layout_word_select_stop_at_punctuation()) {
     // If layout.word_select.stop_at_punctuation is true, we have to look
     // for punctuation class since it may not break state in UAX#29.
     for (int32_t i = previousPos + 1; i < wordStart; i++) {
       if (IsAcceptableWordStart(mAcc, text, i)) {
         return TextLeafPoint(mAcc, i);
       }
     }
   }
   previousPos = wordStart;
   nextBreak = wordBreakIter.Next();
 }
 return TextLeafPoint(mAcc, wordStart);
}

/* static */
TextLeafPoint TextLeafPoint::GetCaret(Accessible* aAcc) {
 if (LocalAccessible* localAcc = aAcc->AsLocal()) {
   // Use the HyperTextAccessible caret offset. Eventually, we'll want to move
   // that code into TextLeafPoint, but existing code depends on it being based
   // on HyperTextAccessible (including caret events).
   int32_t htOffset = -1;
   // Try the cached caret.
   HyperTextAccessible* ht = SelectionMgr()->AccessibleWithCaret(&htOffset);
   if (ht) {
     MOZ_ASSERT(htOffset != -1);
   } else {
     // There is no cached caret, but there might still be a caret; see bug
     // 1425112.
     ht = HyperTextFor(localAcc);
     if (!ht) {
       return TextLeafPoint();
     }
     // An offset can only refer to a child, but the caret might be in a deeper
     // descendant. Walk to the deepest HyperTextAccessible using CaretOffset.
     bool gotCaret = false;
     for (;;) {
       htOffset = ht->CaretOffset();
       if (htOffset == -1) {
         break;
       }
       // A descendant might return -1 in some cases, but it's okay as long as
       // the call on the outermost HyperTextAccessible succeeds.
       gotCaret = true;
       LocalAccessible* child = ht->GetChildAtOffset(htOffset);
       if (!child) {
         break;
       }
       if (HyperTextAccessible* childHt = child->AsHyperText()) {
         ht = childHt;
       } else {
         break;
       }
     }
     if (!gotCaret) {
       return TextLeafPoint();
     }
   }
   // As noted above, CaretOffset on a descendant might return -1. Use 0 in
   // that case.
   TextLeafPoint point = ht->ToTextLeafPoint(htOffset == -1 ? 0 : htOffset);
   if (!point) {
     // Bug 1905021: This happens in the wild, but we don't understand why.
     // ToTextLeafPoint should only fail if the HyperText offset is invalid,
     // but CaretOffset shouldn't return an invalid offset.
     MOZ_ASSERT_UNREACHABLE(
         "Got HyperText CaretOffset but ToTextLeafPoint failed");
     return point;
   }
   if (!IsCaretValid(point)) {
     return TextLeafPoint();
   }
   nsIFrame* frame = ht->GetFrame();
   RefPtr<nsFrameSelection> sel = frame ? frame->GetFrameSelection() : nullptr;
   if (sel && sel->GetHint() == CaretAssociationHint::Before) {
     // CaretAssociationHint::Before can mean that the caret is at the end of
     // a line. However, this can also occur in a few other situations:
     // 1. The caret is before the start of a node in the middle of a line.
     // This happens when moving the cursor forward to a new node.
     // 2. The user clicks the mouse on a character other than the first in a
     // node.
     // 3. The caret is somewhere other than the start of a line and the user
     // presses down or up arrow to move by line.
     if (point.mOffset <
         static_cast<int32_t>(nsAccUtils::TextLength(point.mAcc))) {
       // The caret is at the end of a line if the point is at the start of a
       // line but not at the start of a paragraph.
       point.mIsEndOfLineInsertionPoint =
           point.FindPrevLineStartSameLocalAcc(/* aIncludeOrigin */ true) ==
               point &&
           !point.IsParagraphStart();
     } else {
       // This is the end of a node. CaretAssociationHint::Before is only used
       // at the end of a node if the caret is at the end of a line.
       point.mIsEndOfLineInsertionPoint = true;
     }
   }
   return point;
 }

 // Ideally, we'd cache the caret as a leaf, but our events are based on
 // HyperText for now.
 DocAccessibleParent* remoteDoc = aAcc->AsRemote()->Document();
 auto [ht, htOffset] = remoteDoc->GetCaret();
 if (!ht) {
   return TextLeafPoint();
 }
 TextLeafPoint point = ht->ToTextLeafPoint(htOffset);
 if (!point) {
   // The caret offset should usually be in sync with the tree. However, tree
   // and selection updates happen using separate IPDL calls, so it's possible
   // for a client caret query to arrive between them. Thus, we can end up
   // with an invalid caret here.
   return point;
 }
 if (!IsCaretValid(point)) {
   return TextLeafPoint();
 }
 point.mIsEndOfLineInsertionPoint = remoteDoc->IsCaretAtEndOfLine();
 return point;
}

TextLeafPoint TextLeafPoint::AdjustEndOfLine() const {
 MOZ_ASSERT(mIsEndOfLineInsertionPoint);
 // Use the last character on the line so that we search for word and line
 // boundaries on the current line, not the next line.
 return TextLeafPoint(mAcc, mOffset)
     .FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirPrevious);
}

TextLeafPoint TextLeafPoint::FindBoundary(AccessibleTextBoundary aBoundaryType,
                                         nsDirection aDirection,
                                         BoundaryFlags aFlags) const {
 if (mIsEndOfLineInsertionPoint) {
   // In this block, we deliberately don't propagate mIsEndOfLineInsertionPoint
   // to derived points because otherwise, a call to FindBoundary on the
   // returned point would also return the same point.
   if (aBoundaryType == nsIAccessibleText::BOUNDARY_CHAR ||
       aBoundaryType == nsIAccessibleText::BOUNDARY_CLUSTER) {
     if (aDirection == eDirNext || (aDirection == eDirPrevious &&
                                    aFlags & BoundaryFlags::eIncludeOrigin)) {
       // The caller wants the current or next character/cluster. Return no
       // character, since otherwise, this would move past the first character
       // on the next line.
       return TextLeafPoint(mAcc, mOffset);
     }
     // The caller wants the previous character/cluster. Return that as normal.
     return TextLeafPoint(mAcc, mOffset)
         .FindBoundary(aBoundaryType, aDirection, aFlags);
   }
   // For any other boundary, we need to start on this line, not the next, even
   // though mOffset refers to the next.
   return AdjustEndOfLine().FindBoundary(aBoundaryType, aDirection, aFlags);
 }

 bool inEditableAndStopInIt = (aFlags & BoundaryFlags::eStopInEditable) &&
                              mAcc->Parent() &&
                              (mAcc->Parent()->State() & states::EDITABLE);
 if (aBoundaryType == nsIAccessibleText::BOUNDARY_LINE_END) {
   return FindLineEnd(aDirection,
                      inEditableAndStopInIt
                          ? aFlags
                          : (aFlags & ~BoundaryFlags::eStopInEditable));
 }
 if (aBoundaryType == nsIAccessibleText::BOUNDARY_WORD_END) {
   return FindWordEnd(aDirection,
                      inEditableAndStopInIt
                          ? aFlags
                          : (aFlags & ~BoundaryFlags::eStopInEditable));
 }
 if ((aBoundaryType == nsIAccessibleText::BOUNDARY_LINE_START ||
      aBoundaryType == nsIAccessibleText::BOUNDARY_PARAGRAPH) &&
     (aFlags & BoundaryFlags::eIncludeOrigin) && aDirection == eDirPrevious &&
     IsEmptyLastLine()) {
   // If we're at an empty line at the end of an Accessible,  we don't want to
   // walk into the previous line. For example, this can happen if the caret
   // is positioned on an empty line at the end of a textarea.
   return *this;
 }
 bool includeOrigin = !!(aFlags & BoundaryFlags::eIncludeOrigin);
 bool ignoreListItemMarker = !!(aFlags & BoundaryFlags::eIgnoreListItemMarker);
 Accessible* lastAcc = nullptr;
 for (TextLeafPoint searchFrom = *this; searchFrom;
      searchFrom = searchFrom.NeighborLeafPoint(
          aDirection, inEditableAndStopInIt, ignoreListItemMarker)) {
   lastAcc = searchFrom.mAcc;
   if (ignoreListItemMarker && searchFrom == *this &&
       searchFrom.mAcc->Role() == roles::LISTITEM_MARKER) {
     continue;
   }
   TextLeafPoint boundary;
   // Search for the boundary within the current Accessible.
   switch (aBoundaryType) {
     case nsIAccessibleText::BOUNDARY_CHAR:
       if (includeOrigin) {
         boundary = searchFrom;
       } else if (aDirection == eDirPrevious && searchFrom.mOffset > 0) {
         boundary.mAcc = searchFrom.mAcc;
         boundary.mOffset = searchFrom.mOffset - 1;
       } else if (aDirection == eDirNext &&
                  searchFrom.mOffset + 1 <
                      static_cast<int32_t>(
                          nsAccUtils::TextLength(searchFrom.mAcc))) {
         boundary.mAcc = searchFrom.mAcc;
         boundary.mOffset = searchFrom.mOffset + 1;
       }
       break;
     case nsIAccessibleText::BOUNDARY_WORD_START:
       if (aDirection == eDirPrevious) {
         boundary = searchFrom.FindPrevWordStartSameAcc(includeOrigin);
       } else {
         boundary = searchFrom.FindNextWordStartSameAcc(includeOrigin);
       }
       break;
     case nsIAccessibleText::BOUNDARY_LINE_START:
       boundary = searchFrom.FindLineStartSameAcc(aDirection, includeOrigin,
                                                  ignoreListItemMarker);
       break;
     case nsIAccessibleText::BOUNDARY_PARAGRAPH:
       boundary = searchFrom.FindParagraphSameAcc(aDirection, includeOrigin,
                                                  ignoreListItemMarker);
       break;
     case nsIAccessibleText::BOUNDARY_CLUSTER:
       boundary = searchFrom.FindClusterSameAcc(aDirection, includeOrigin);
       break;
     default:
       MOZ_ASSERT_UNREACHABLE();
       break;
   }
   if (boundary) {
     return boundary;
   }

   // The start/end of the Accessible might be a boundary. If so, we must stop
   // on it.
   includeOrigin = true;
 }

 MOZ_ASSERT(lastAcc);
 // No further leaf was found. Use the start/end of the first/last leaf.
 return TextLeafPoint(
     lastAcc, aDirection == eDirPrevious
                  ? 0
                  : static_cast<int32_t>(nsAccUtils::TextLength(lastAcc)));
}

TextLeafPoint TextLeafPoint::FindLineEnd(nsDirection aDirection,
                                        BoundaryFlags aFlags) const {
 if (aDirection == eDirPrevious && IsEmptyLastLine()) {
   // If we're at an empty line at the end of an Accessible,  we don't want to
   // walk into the previous line. For example, this can happen if the caret
   // is positioned on an empty line at the end of a textarea.
   // Because we want the line end, we must walk back to the line feed
   // character.
   return FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirPrevious,
                       aFlags & ~BoundaryFlags::eIncludeOrigin);
 }
 if ((aFlags & BoundaryFlags::eIncludeOrigin) && IsLineFeedChar()) {
   return *this;
 }
 if (aDirection == eDirPrevious && !(aFlags & BoundaryFlags::eIncludeOrigin)) {
   // If there is a line feed immediately before us, return that.
   TextLeafPoint prevChar =
       FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirPrevious,
                    aFlags & ~BoundaryFlags::eIncludeOrigin);
   if (prevChar.IsLineFeedChar()) {
     return prevChar;
   }
 }
 TextLeafPoint searchFrom = *this;
 if (aDirection == eDirNext && IsLineFeedChar()) {
   // If we search for the next line start from a line feed, we'll get the
   // character immediately following the line feed. We actually want the
   // next line start after that. Skip the line feed.
   searchFrom = FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirNext,
                             aFlags & ~BoundaryFlags::eIncludeOrigin);
 }
 TextLeafPoint lineStart = searchFrom.FindBoundary(
     nsIAccessibleText::BOUNDARY_LINE_START, aDirection, aFlags);
 if (aDirection == eDirNext && IsEmptyLastLine()) {
   // There is a line feed immediately before us, but that's actually the end
   // of the previous line, not the end of our empty line. Don't walk back.
   return lineStart;
 }
 // If there is a line feed before this line start (at the end of the previous
 // line), we must return that.
 TextLeafPoint prevChar =
     lineStart.FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirPrevious,
                            aFlags & ~BoundaryFlags::eIncludeOrigin);
 if (prevChar && prevChar.IsLineFeedChar()) {
   return prevChar;
 }
 return lineStart;
}

bool TextLeafPoint::IsSpace() const {
 return GetWordBreakClass(GetChar()) == eWbcSpace;
}

TextLeafPoint TextLeafPoint::FindWordEnd(nsDirection aDirection,
                                        BoundaryFlags aFlags) const {
 char16_t origChar = GetChar();
 const bool origIsSpace = GetWordBreakClass(origChar) == eWbcSpace;
 bool prevIsSpace = false;
 if (aDirection == eDirPrevious ||
     ((aFlags & BoundaryFlags::eIncludeOrigin) && origIsSpace) || !origChar) {
   TextLeafPoint prev =
       FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirPrevious,
                    aFlags & ~BoundaryFlags::eIncludeOrigin);
   if (aDirection == eDirPrevious && prev == *this) {
     return *this;  // Can't go any further.
   }
   prevIsSpace = prev.IsSpace();
   if ((aFlags & BoundaryFlags::eIncludeOrigin) &&
       (origIsSpace || IsDocEdge(eDirNext)) && !prevIsSpace) {
     // The origin is space or end of document, but the previous
     // character is not. This means we're at the end of a word.
     return *this;
   }
 }
 TextLeafPoint boundary = *this;
 if (aDirection == eDirPrevious && !prevIsSpace) {
   // If there isn't space immediately before us, first find the start of the
   // previous word.
   boundary = FindBoundary(nsIAccessibleText::BOUNDARY_WORD_START,
                           eDirPrevious, aFlags);
 } else if (aDirection == eDirNext &&
            (origIsSpace || (!origChar && prevIsSpace))) {
   // We're within the space at the end of the word. Skip over the space. We
   // can do that by searching for the next word start.
   boundary = FindBoundary(nsIAccessibleText::BOUNDARY_WORD_START, eDirNext,
                           aFlags & ~BoundaryFlags::eIncludeOrigin);
   if (boundary.IsSpace()) {
     // The next word starts with a space. This can happen if there is a space
     // after or at the start of a block element.
     return boundary;
   }
 }
 if (aDirection == eDirNext) {
   BoundaryFlags flags = aFlags;
   if (IsDocEdge(eDirPrevious)) {
     // If this is the start of the doc don't be inclusive in the word-start
     // search because there is no preceding block where this could be a
     // word-end for.
     flags &= ~BoundaryFlags::eIncludeOrigin;
   }
   boundary = boundary.FindBoundary(nsIAccessibleText::BOUNDARY_WORD_START,
                                    eDirNext, flags);
 }
 // At this point, boundary is either the start of a word or at a space. A
 // word ends at the beginning of consecutive space. Therefore, skip back to
 // the start of any space before us.
 TextLeafPoint prev = boundary;
 for (;;) {
   prev = prev.FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirPrevious,
                            aFlags & ~BoundaryFlags::eIncludeOrigin);
   if (prev == boundary) {
     break;  // Can't go any further.
   }
   if (!prev.IsSpace()) {
     break;
   }
   boundary = prev;
 }
 return boundary;
}

TextLeafPoint TextLeafPoint::FindParagraphSameAcc(
   nsDirection aDirection, bool aIncludeOrigin,
   bool aIgnoreListItemMarker) const {
 if (aIncludeOrigin && IsDocEdge(eDirPrevious)) {
   // The top of the document is a paragraph boundary.
   return *this;
 }

 if (aIgnoreListItemMarker && aIncludeOrigin && mOffset == 0 &&
     IsLeafAfterListItemMarker()) {
   // If we are in a list item and the previous sibling is
   // a bullet, the 0 offset in this leaf is a line start.
   return *this;
 }

 if (mAcc->IsTextLeaf() &&
     // We don't want to copy strings unnecessarily. See below for the context
     // of these individual conditions.
     ((aIncludeOrigin && mOffset > 0) || aDirection == eDirNext ||
      mOffset >= 2)) {
   // If there is a line feed, a new paragraph begins after it.
   nsAutoString text;
   mAcc->AppendTextTo(text);
   if (aIncludeOrigin && mOffset > 0 && text.CharAt(mOffset - 1) == '\n') {
     return TextLeafPoint(mAcc, mOffset);
   }
   int32_t lfOffset = -1;
   if (aDirection == eDirNext) {
     lfOffset = text.FindChar('\n', mOffset);
   } else if (mOffset >= 2) {
     // A line feed at mOffset - 1 means the origin begins a new paragraph,
     // but we already handled aIncludeOrigin above. Therefore, we search from
     // mOffset - 2.
     lfOffset = text.RFindChar('\n', mOffset - 2);
   }
   if (lfOffset != -1 && lfOffset + 1 < static_cast<int32_t>(text.Length())) {
     return TextLeafPoint(mAcc, lfOffset + 1);
   }
 }

 if (aIgnoreListItemMarker && mOffset > 0 && aDirection == eDirPrevious &&
     IsLeafAfterListItemMarker()) {
   // No line breaks were found in the preceding text to this offset.
   // If we are in a list item and the previous sibling is
   // a bullet, the 0 offset in this leaf is a line start.
   return TextLeafPoint(mAcc, 0);
 }

 // Check whether this Accessible begins a paragraph.
 if ((!aIncludeOrigin && mOffset == 0) ||
     (aDirection == eDirNext && mOffset > 0)) {
   // The caller isn't interested in whether this Accessible begins a
   // paragraph.
   return TextLeafPoint();
 }
 Accessible* prevLeaf = PrevLeaf(mAcc);
 BlockRule blockRule;
 Pivot pivot(nsAccUtils::DocumentFor(mAcc));
 Accessible* prevBlock = pivot.Prev(mAcc, blockRule);
 // Check if we're the first leaf after a block element.
 if (prevBlock) {
   if (
       // If there's no previous leaf, we must be the first leaf after the
       // block.
       !prevLeaf ||
       // A block can be a leaf; e.g. an empty div or paragraph.
       prevBlock == prevLeaf) {
     return TextLeafPoint(mAcc, 0);
   }
   if (prevBlock->IsAncestorOf(mAcc)) {
     // We're inside the block.
     if (!prevBlock->IsAncestorOf(prevLeaf)) {
       // The previous leaf isn't inside the block. That means we're the first
       // leaf in the block.
       return TextLeafPoint(mAcc, 0);
     }
   } else {
     // We aren't inside the block, so the block ends before us.
     if (prevBlock->IsAncestorOf(prevLeaf)) {
       // The previous leaf is inside the block. That means we're the first
       // leaf after the block. This case is necessary because a block causes a
       // paragraph break both before and after it.
       return TextLeafPoint(mAcc, 0);
     }
   }
 }
 if (!prevLeaf || prevLeaf->IsHTMLBr()) {
   // We're the first leaf after a line break or the start of the document.
   return TextLeafPoint(mAcc, 0);
 }
 if (prevLeaf->IsTextLeaf()) {
   // There's a text leaf before us. Check if it ends with a line feed.
   nsAutoString text;
   prevLeaf->AppendTextTo(text, nsAccUtils::TextLength(prevLeaf) - 1, 1);
   if (text.CharAt(0) == '\n') {
     return TextLeafPoint(mAcc, 0);
   }
 }
 return TextLeafPoint();
}

TextLeafPoint TextLeafPoint::FindClusterSameAcc(nsDirection aDirection,
                                               bool aIncludeOrigin) const {
 // We don't support clusters which cross nodes. We can live with that because
 // editor doesn't seem to fully support this either.
 if (aIncludeOrigin && mOffset == 0) {
   // Since we don't cross nodes, offset 0 always begins a cluster.
   return *this;
 }
 if (aDirection == eDirPrevious) {
   if (mOffset == 0) {
     // We can't go back any further.
     return TextLeafPoint();
   }
   if (!aIncludeOrigin && mOffset == 1) {
     // Since we don't cross nodes, offset 0 always begins a cluster. We can't
     // take this fast path if aIncludeOrigin is true because offset 1 might
     // start a cluster, but we don't know that yet.
     return TextLeafPoint(mAcc, 0);
   }
 }
 nsAutoString text;
 mAcc->AppendTextTo(text);
 if (text.IsEmpty()) {
   return TextLeafPoint();
 }
 if (aDirection == eDirNext &&
     mOffset == static_cast<int32_t>(text.Length())) {
   return TextLeafPoint();
 }
 // There is GraphemeClusterBreakReverseIteratorUtf16, but it "doesn't
 // handle conjoining Jamo and emoji". Therefore, we must use
 // GraphemeClusterBreakIteratorUtf16 even when moving backward.
 // GraphemeClusterBreakIteratorUtf16::Seek() always starts from the beginning
 // and repeatedly calls Next(), regardless of the seek offset. The best we
 // can do is call Next() until we find the offset we need.
 intl::GraphemeClusterBreakIteratorUtf16 iter(text);
 // Since we don't cross nodes, offset 0 always begins a cluster.
 int32_t prevCluster = 0;
 while (Maybe<uint32_t> next = iter.Next()) {
   int32_t cluster = static_cast<int32_t>(*next);
   if (aIncludeOrigin && cluster == mOffset) {
     return *this;
   }
   if (aDirection == eDirPrevious) {
     if (cluster >= mOffset) {
       return TextLeafPoint(mAcc, prevCluster);
     }
     prevCluster = cluster;
   } else if (cluster > mOffset) {
     MOZ_ASSERT(aDirection == eDirNext);
     return TextLeafPoint(mAcc, cluster);
   }
 }
 return TextLeafPoint();
}

void TextLeafPoint::AddTextOffsetAttributes(AccAttributes* aAttrs) const {
 auto expose = [aAttrs](nsAtom* aAttr) {
   if (aAttr == nsGkAtoms::spelling || aAttr == nsGkAtoms::grammar) {
     // XXX We don't correctly handle exposure of overlapping spelling and
     // grammar errors. See bug 1944217. For now, we expose the one we most
     // recently encountered.
     aAttrs->SetAttribute(nsGkAtoms::invalid, aAttr);
   } else if (aAttr == nsGkAtoms::mark) {
     aAttrs->SetAttribute(aAttr, true);
   }
 };

 if (LocalAccessible* acc = mAcc->AsLocal()) {
   auto ranges = FindDOMTextOffsetAttributes(acc, mOffset, mOffset + 1);
   for (auto& [domRanges, attr] : ranges) {
     MOZ_ASSERT(domRanges.Length() >= 1);
     expose(attr);
   }
   return;
 }

 RemoteAccessible* acc = mAcc->AsRemote();
 MOZ_ASSERT(acc);
 if (RequestDomainsIfInactive(CacheDomain::TextOffsetAttributes)) {
   return;
 }
 if (!acc->mCachedFields) {
   return;
 }
 auto offsetAttrs =
     acc->mCachedFields->GetAttribute<nsTArray<TextOffsetAttribute>>(
         CacheKey::TextOffsetAttributes);
 if (!offsetAttrs) {
   return;
 }
 // offsetAttrs is sorted by mStartOffset, but ranges can overlap each other.
 // Thus, we must check all ranges with an encompassing start offset.
 for (const TextOffsetAttribute& range : *offsetAttrs) {
   if (range.mStartOffset > mOffset) {
     // offsetAttrs is sorted by mStartOffset. Therefor, there aren't any
     // ranges of interest after this.
     break;
   }
   if (range.mEndOffset != TextOffsetAttribute::kOutsideLeaf &&
       range.mEndOffset <= mOffset) {
     // range ends inside mAcc but before mOffset, so it doesn't encompass us.
     continue;
   }
   // mOffset is within range.
   expose(range.mAttribute);
 }
}

TextLeafPoint TextLeafPoint::FindTextOffsetAttributeSameAcc(
   nsDirection aDirection, bool aIncludeOrigin) const {
 if (!aIncludeOrigin && mOffset == 0 && aDirection == eDirPrevious) {
   return TextLeafPoint();
 }
 if (LocalAccessible* acc = mAcc->AsLocal()) {
   nsINode* node = acc->GetNode();
   // There are multiple selection types. The ranges for each selection type
   // are sorted, but the ranges aren't sorted between selection types.
   // Therefore, we need to look for the closest matching offset in each
   // selection type. We keep track of that in the dest variable as we check
   // each selection type.
   int32_t dest = -1;
   if (aDirection == eDirNext) {
     // We want to find both start and end points, so we pass true for
     // aAllowAdjacent.
     auto ranges = FindDOMTextOffsetAttributes(
         acc, mOffset, nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT,
         /* aAllowAdjacent */ true);
     for (auto& [domRanges, attr] : ranges) {
       for (dom::AbstractRange* domRange : domRanges) {
         if (domRange->GetStartContainer() == node) {
           int32_t matchOffset = static_cast<int32_t>(ContentToRenderedOffset(
               acc, static_cast<int32_t>(domRange->StartOffset())));
           if (aIncludeOrigin && matchOffset == mOffset) {
             return *this;
           }
           if (matchOffset > mOffset) {
             if (dest == -1 || matchOffset <= dest) {
               dest = matchOffset;
             }
             // ranges is sorted by start, so there can't be a closer range
             // offset after this. This is the only case where we can break
             // out of the loop. In the cases below, we must keep iterating
             // because the end offsets aren't sorted.
             break;
           }
         }
         if (domRange->GetEndContainer() == node) {
           int32_t matchOffset = static_cast<int32_t>(ContentToRenderedOffset(
               acc, static_cast<int32_t>(domRange->EndOffset())));
           if (aIncludeOrigin && matchOffset == mOffset) {
             return *this;
           }
           if (matchOffset > mOffset && (dest == -1 || matchOffset <= dest)) {
             dest = matchOffset;
           }
         }
       }
     }
   } else {
     auto ranges = FindDOMTextOffsetAttributes(acc, 0, mOffset,
                                               /* aAllowAdjacent */ true);
     for (auto& [domRanges, attr] : ranges) {
       for (dom::AbstractRange* domRange : Reversed(domRanges)) {
         if (domRange->GetEndContainer() == node) {
           int32_t matchOffset = static_cast<int32_t>(ContentToRenderedOffset(
               acc, static_cast<int32_t>(domRange->EndOffset())));
           if (aIncludeOrigin && matchOffset == mOffset) {
             return *this;
           }
           if (matchOffset < mOffset && (dest == -1 || matchOffset >= dest)) {
             dest = matchOffset;
           }
         }
         if (domRange->GetStartContainer() == node) {
           int32_t matchOffset = static_cast<int32_t>(ContentToRenderedOffset(
               acc, static_cast<int32_t>(domRange->StartOffset())));
           if (aIncludeOrigin && matchOffset == mOffset) {
             return *this;
           }
           if (matchOffset < mOffset && (dest == -1 || matchOffset >= dest)) {
             dest = matchOffset;
           }
         }
       }
     }
   }
   if (dest == -1) {
     return TextLeafPoint();
   }
   return TextLeafPoint(mAcc, dest);
 }

 RemoteAccessible* acc = mAcc->AsRemote();
 MOZ_ASSERT(acc);
 if (RequestDomainsIfInactive(CacheDomain::TextOffsetAttributes)) {
   return TextLeafPoint();
 }
 if (!acc->mCachedFields) {
   return TextLeafPoint();
 }
 auto offsetAttrs =
     acc->mCachedFields->GetAttribute<nsTArray<TextOffsetAttribute>>(
         CacheKey::TextOffsetAttributes);
 if (!offsetAttrs) {
   return TextLeafPoint();
 }
 // offsetAttrs is sorted by mStartOffset, but ranges can overlap each other.
 // Therefore, we must consider all ranges with an encompassing start offset.
 // An earlier range might end after a later range, so we keep track of the
 // closest offset in the dest variable and adjust that as we iterate.
 int32_t dest = -1;
 for (const TextOffsetAttribute& range : *offsetAttrs) {
   // Although range end offsets are exclusive, we must still treat them as a
   // boundary, since the end of a range still means a change in text
   // attributes and text offset attribute ranges do not have to be adjacent.
   if (aIncludeOrigin &&
       (range.mStartOffset == mOffset || range.mEndOffset == mOffset)) {
     return *this;
   }
   if (aDirection == eDirNext) {
     if (range.mStartOffset > mOffset) {
       if (dest == -1 || range.mStartOffset < dest) {
         // range.mStartOffset is the closest offset we've seen thus far.
         dest = range.mStartOffset;
       }
       // offsetAttrs is sorted by mStartOffset, so there can't be a closer
       // range offset after this.
       break;
     }
     if (range.mEndOffset > mOffset &&
         (dest == -1 || range.mEndOffset < dest)) {
       // range.mEndOffset is the closest offset we've seen thus far.
       dest = range.mEndOffset;
     }
   } else {
     if (range.mEndOffset != TextOffsetAttribute::kOutsideLeaf &&
         range.mEndOffset < mOffset && range.mEndOffset > dest) {
       // range.mEndOffset is the closest offset we've seen thus far.
       dest = range.mEndOffset;
     }
     if (range.mStartOffset >= mOffset) {
       // offsetAttrs is sorted by mStartOffset, so any range hereafter is in
       // the wrong direction.
       break;
     }
     if (range.mStartOffset != TextOffsetAttribute::kOutsideLeaf &&
         range.mStartOffset > dest) {
       // range.mStartOffset is the closest offset we've seen thus far.
       dest = range.mStartOffset;
     }
   }
 }
 if (dest == -1) {
   // There's no boundary in the requested direction.
   return TextLeafPoint();
 }
 return TextLeafPoint(mAcc, dest);
}

TextLeafPoint TextLeafPoint::NeighborLeafPoint(
   nsDirection aDirection, bool aIsEditable,
   bool aIgnoreListItemMarker) const {
 Accessible* acc = aDirection == eDirPrevious
                       ? PrevLeaf(mAcc, aIsEditable, aIgnoreListItemMarker)
                       : NextLeaf(mAcc, aIsEditable, aIgnoreListItemMarker);
 if (!acc) {
   return TextLeafPoint();
 }

 return TextLeafPoint(
     acc, aDirection == eDirPrevious
              ? static_cast<int32_t>(nsAccUtils::TextLength(acc)) - 1
              : 0);
}

LayoutDeviceIntRect TextLeafPoint::ComputeBoundsFromFrame() const {
 LocalAccessible* local = mAcc->AsLocal();
 MOZ_ASSERT(local, "Can't compute bounds in frame from non-local acc");
 nsIFrame* frame = local->GetFrame();
 MOZ_ASSERT(frame, "No frame found for acc!");

 if (!frame || !frame->IsTextFrame()) {
   return local->Bounds();
 }

 // Substring must be entirely within the same text node.
 MOZ_ASSERT(frame->IsPrimaryFrame(),
            "Cannot compute content offset on non-primary frame");
 nsIFrame::RenderedText text = frame->GetRenderedText(
     mOffset, mOffset + 1, nsIFrame::TextOffsetType::OffsetsInRenderedText,
     nsIFrame::TrailingWhitespace::DontTrim);
 int32_t contentOffset = text.mOffsetWithinNodeText;
 int32_t contentOffsetInFrame;
 // Get the right frame continuation -- not really a child, but a sibling of
 // the primary frame passed in
 nsresult rv = frame->GetChildFrameContainingOffset(
     contentOffset, true, &contentOffsetInFrame, &frame);
 NS_ENSURE_SUCCESS(rv, LayoutDeviceIntRect());

 // Start with this frame's screen rect, which we will shrink based on
 // the char we care about within it.
 nsRect frameScreenRect = frame->GetScreenRectInAppUnits();

 // Add the point where the char starts to the frameScreenRect
 nsPoint frameTextStartPoint;
 rv = frame->GetPointFromOffset(contentOffset, &frameTextStartPoint);
 NS_ENSURE_SUCCESS(rv, LayoutDeviceIntRect());

 // Use the next offset to calculate the width
 // XXX(morgan) does this work for vertical text?
 nsPoint frameTextEndPoint;
 rv = frame->GetPointFromOffset(contentOffset + 1, &frameTextEndPoint);
 NS_ENSURE_SUCCESS(rv, LayoutDeviceIntRect());

 frameScreenRect.SetRectX(
     frameScreenRect.X() +
         std::min(frameTextStartPoint.x, frameTextEndPoint.x),
     mozilla::Abs(frameTextStartPoint.x - frameTextEndPoint.x));

 nsPresContext* presContext = local->Document()->PresContext();
 return LayoutDeviceIntRect::FromAppUnitsToNearest(
     frameScreenRect, presContext->AppUnitsPerDevPixel());
}

LayoutDeviceIntRect TextLeafPoint::InsertionPointBounds() const {
 if (TextLeafPoint::GetCaret(mAcc) == *this) {
   for (Accessible* acc = mAcc; acc; acc = acc->Parent()) {
     if (HyperTextAccessibleBase* ht = acc->AsHyperTextBase()) {
       return ht->GetCaretRect().first;
     }
   }
 }

 LayoutDeviceIntRect currentBounds = CharBounds();
 if (currentBounds.IsEmpty()) {
   return LayoutDeviceIntRect();
 }

 // When 'reversed' is true we calculate the writing direction using a
 // neighboring character that is past the current one (eg. in LTR the
 // character to the right.)
 bool reversed = false;
 // We are conservative here and stay within the bounds of the editable so
 // we don't get confused with other text-flows outside of this block.
 TextLeafPoint neighborChar =
     FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirPrevious,
                  BoundaryFlags::eStopInEditable);
 if (*this == neighborChar) {
   // If the current char is the first, use the next char past the current
   // to extrapolate the writing direction.
   neighborChar = FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirNext,
                               BoundaryFlags::eStopInEditable);
   reversed = true;
 } else {
   if (*this ==
       FindBoundary(
           nsIAccessibleText::BOUNDARY_LINE_START, eDirPrevious,
           BoundaryFlags::eStopInEditable | BoundaryFlags::eIncludeOrigin)) {
     // If this char is a newline the previous char will be on the previous
     // line either equal or past the current one (eg. in LTR the previous char
     // will be to the right of the current instead of the left.)
     reversed = true;
   }
 }

 LayoutDeviceIntRect neighborBounds = neighborChar.CharBounds();
 if (neighborBounds.IsEmpty()) {
   // Either the point is invalid or the accessible is not visible.
   // We tried, didn't we..
   return LayoutDeviceIntRect();
 }

 // An axis-agnostic function that determines writing direction and aligns
 // the caret where insertion point should be.
 auto alignRectToInsertion = [](int32_t neighborStart, bool reversed,
                                int32_t& currentStart,
                                int32_t& currentLength) {
   // The caret is always 1px wide (or tall, in vertical text).
   const int32_t caretLength = 1;
   int32_t delta = (neighborStart - currentStart);
   if (reversed) {
     delta *= -1;
   }
   if (delta > 0) {
     // Previous character is to the end (eg. right in ltr) of the current one,
     // or next character is to the start (eg. left in ltr) of the current one.
     // Align the caret to the end of the current character.
     currentStart += currentLength - caretLength;
   }
   currentLength = caretLength;
 };

 WritingMode wm = mAcc->GetWritingMode();
 if (wm == WritingMode() && mAcc->Parent()) {
   // mAcc is probably a text leaf with no stored writing mode, use its parent.
   wm = mAcc->Parent()->GetWritingMode();
 }

 if (!wm.IsVertical()) {
   // Horizontal text.
   alignRectToInsertion(neighborBounds.x, reversed, currentBounds.x,
                        currentBounds.width);
 } else {
   // Vertical text
   alignRectToInsertion(neighborBounds.y, reversed, currentBounds.y,
                        currentBounds.height);
 }

 return currentBounds;
}

/* static */
nsTArray<TextOffsetAttribute> TextLeafPoint::GetTextOffsetAttributes(
   LocalAccessible* aAcc) {
 nsINode* node = aAcc->GetNode();
 auto ranges = FindDOMTextOffsetAttributes(
     aAcc, 0, nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT);
 size_t capacity = 0;
 for (auto& [domRanges, attr] : ranges) {
   capacity += domRanges.Length();
 }
 nsTArray<TextOffsetAttribute> offsets(capacity);
 for (auto& [domRanges, attr] : ranges) {
   for (dom::AbstractRange* domRange : domRanges) {
     TextOffsetAttribute& data = *offsets.AppendElement();
     data.mAttribute = attr;
     if (domRange->GetStartContainer() == node) {
       data.mStartOffset = static_cast<int32_t>(ContentToRenderedOffset(
           aAcc, static_cast<int32_t>(domRange->StartOffset())));
     } else {
       // This range overlaps aAcc, but starts before it.
       // This can only happen for the first range.
       MOZ_ASSERT(domRange == *domRanges.begin());
       data.mStartOffset = TextOffsetAttribute::kOutsideLeaf;
     }
     if (domRange->GetEndContainer() == node) {
       data.mEndOffset = static_cast<int32_t>(ContentToRenderedOffset(
           aAcc, static_cast<int32_t>(domRange->EndOffset())));
     } else {
       // This range overlaps aAcc, but ends after it.
       // This can only happen for the last range.
       MOZ_ASSERT(domRange == *domRanges.rbegin());
       data.mEndOffset = TextOffsetAttribute::kOutsideLeaf;
     }
   }
 }
 offsets.Sort();
 return offsets;
}

/* static */
void TextLeafPoint::UpdateCachedTextOffsetAttributes(
   dom::Document* aDocument, const dom::AbstractRange& aRange) {
 DocAccessible* docAcc = GetExistingDocAccessible(aDocument);
 if (!docAcc) {
   return;
 }
 LocalAccessible* startAcc = docAcc->GetAccessible(aRange.GetStartContainer());
 LocalAccessible* endAcc = docAcc->GetAccessible(aRange.GetEndContainer());
 if (!startAcc || !endAcc) {
   return;
 }
 for (Accessible* acc = startAcc; acc; acc = NextLeaf(acc)) {
   if (acc->IsTextLeaf()) {
     docAcc->QueueCacheUpdate(acc->AsLocal(),
                              CacheDomain::TextOffsetAttributes);
   }
   if (acc == endAcc) {
     // Subtle: We check this here rather than in the loop condition because
     // we want to include endAcc but stop once we reach it. Putting it in the
     // loop condition would mean we stop at endAcc, but we would also exclude
     // it; i.e. we wouldn't push the cache for it.
     break;
   }
 }
}

already_AddRefed<AccAttributes> TextLeafPoint::GetTextAttributesLocalAcc(
   bool aIncludeDefaults) const {
 LocalAccessible* acc = mAcc->AsLocal();
 MOZ_ASSERT(acc);
 MOZ_ASSERT(acc->IsText());
 // TextAttrsMgr wants a HyperTextAccessible.
 LocalAccessible* parent = acc->LocalParent();
 if (!parent) {
   // This should only happen if a client query occurs after a hide event is
   // queued for acc and after acc is detached from the document, but before
   // the event is fired and thus before acc is shut down.
   MOZ_ASSERT(!acc->IsInDocument());
   return nullptr;
 }
 HyperTextAccessible* hyperAcc = parent->AsHyperText();
 MOZ_ASSERT(hyperAcc);
 RefPtr<AccAttributes> attributes = new AccAttributes();
 if (hyperAcc) {
   TextAttrsMgr mgr(hyperAcc, aIncludeDefaults, acc);
   mgr.GetAttributes(attributes);
 }
 return attributes.forget();
}

already_AddRefed<AccAttributes> TextLeafPoint::GetTextAttributes(
   bool aIncludeDefaults) const {
 if (!mAcc->IsText()) {
   return nullptr;
 }
 RefPtr<AccAttributes> attrs;
 if (mAcc->IsLocal()) {
   attrs = GetTextAttributesLocalAcc(aIncludeDefaults);
 } else {
   if (aIncludeDefaults) {
     attrs = mAcc->AsRemote()->DefaultTextAttributes();
   } else {
     attrs = new AccAttributes();
   }
   if (auto thisAttrs = mAcc->AsRemote()->GetCachedTextAttributes()) {
     thisAttrs->CopyTo(attrs);
   }
 }
 AddTextOffsetAttributes(attrs);
 return attrs.forget();
}

TextLeafPoint TextLeafPoint::FindTextAttrsStart(nsDirection aDirection,
                                               bool aIncludeOrigin) const {
 if (mIsEndOfLineInsertionPoint) {
   return AdjustEndOfLine().FindTextAttrsStart(aDirection, aIncludeOrigin);
 }
 RefPtr<const AccAttributes> lastAttrs;
 if (mAcc->IsText()) {
   lastAttrs = GetTextAttributes();
 }
 if (aIncludeOrigin && aDirection == eDirNext && mOffset == 0) {
   if (!mAcc->IsText()) {
     // Anything other than text breaks an attrs run.
     return *this;
   }
   // Even when searching forward, the only way to know whether the origin is
   // the start of a text attrs run is to compare with the previous sibling.
   TextLeafPoint point;
   point.mAcc = mAcc->PrevSibling();
   if (!point.mAcc || !point.mAcc->IsText()) {
     return *this;
   }
   RefPtr<const AccAttributes> attrs = point.GetTextAttributes();
   if (attrs && lastAttrs && !attrs->Equal(lastAttrs)) {
     return *this;
   }
 }
 TextLeafPoint lastPoint = *this;
 // If we're at the start of the container and searching for a previous start,
 // start the search from the previous leaf. Otherwise, we'll miss the previous
 // start.
 const bool shouldTraversePrevLeaf = [&]() {
   const bool shouldTraverse =
       !aIncludeOrigin && aDirection == eDirPrevious && mOffset == 0;
   Accessible* prevSibling = mAcc->PrevSibling();
   if (prevSibling) {
     return shouldTraverse && !prevSibling->IsText();
   }
   return shouldTraverse;
 }();
 if (shouldTraversePrevLeaf) {
   // Go to the previous leaf and start the search from there, if it exists.
   Accessible* prevLeaf = PrevLeaf(mAcc);
   if (!prevLeaf) {
     return *this;
   }
   lastPoint = TextLeafPoint(
       prevLeaf, static_cast<int32_t>(nsAccUtils::TextLength(prevLeaf)));
 }
 // This loop searches within a container (that is, it only looks at siblings).
 // We might cross containers before or after this loop, but not within it.
 for (;;) {
   if (TextLeafPoint offsetAttr = lastPoint.FindTextOffsetAttributeSameAcc(
           aDirection, aIncludeOrigin && lastPoint.mAcc == mAcc)) {
     // An offset attribute starts or ends somewhere in the Accessible we're
     // considering. This causes an attribute change, so return that point.
     return offsetAttr;
   }
   TextLeafPoint point;
   point.mAcc = aDirection == eDirNext ? lastPoint.mAcc->NextSibling()
                                       : lastPoint.mAcc->PrevSibling();
   if (!point.mAcc || !point.mAcc->IsText()) {
     break;
   }
   RefPtr<const AccAttributes> attrs = point.GetTextAttributes();
   if (((!lastAttrs || !attrs) && attrs != lastAttrs) ||
       (attrs && !attrs->Equal(lastAttrs))) {
     // The attributes change here. If we're moving forward, we want to return
     // this point.
     if (aDirection == eDirNext) {
       return point;
     }

     // Otherwise, we're moving backward and we've now moved before the start
     // point of the current text attributes run.
     const auto attrsStart = TextLeafPoint(lastPoint.mAcc, 0);

     // Return the current text attributes run start point if:
     //   1. The caller wants this function to include the origin in the
     //   search (aIncludeOrigin implies that we must return the first text
     //   attributes run start point that we find, even if that point is the
     //   origin)
     //   2. Our search did not begin on the text attributes run start point
     if (aIncludeOrigin || attrsStart != *this) {
       return attrsStart;
     }

     // Otherwise, the origin was the attributes run start point and the caller
     // wants this function to ignore it in its search. Keep searching.
   }
   lastPoint = point;
   if (aDirection == eDirPrevious) {
     // On the next iteration, we want to search for offset attributes from the
     // end of this Accessible.
     lastPoint.mOffset =
         static_cast<int32_t>(nsAccUtils::TextLength(point.mAcc));
   }
   lastAttrs = attrs;
 }

 // We couldn't move any further in this container.
 if (aDirection == eDirPrevious) {
   // Treat the start of a container as a format boundary.
   return TextLeafPoint(lastPoint.mAcc, 0);
 }
 // If we're at the end of the container then we have to use the start of the
 // next leaf.
 Accessible* nextLeaf = NextLeaf(lastPoint.mAcc);
 if (nextLeaf) {
   return TextLeafPoint(nextLeaf, 0);
 }
 // If there's no next leaf, then fall back to the end of the last point.
 return TextLeafPoint(
     lastPoint.mAcc,
     static_cast<int32_t>(nsAccUtils::TextLength(lastPoint.mAcc)));
}

LayoutDeviceIntRect TextLeafPoint::CharBounds() const {
 if (!mAcc) {
   return LayoutDeviceIntRect();
 }

 if (mAcc->IsHTMLBr()) {
   // HTML <br> elements don't provide character bounds, but do provide text (a
   // line feed). They also have 0 width and/or height, depending on the
   // doctype and writing mode. Expose minimum 1 x 1 so clients treat it as an
   // actual rectangle; e.g. when the caret is positioned on a <br>.
   LayoutDeviceIntRect bounds = mAcc->Bounds();
   if (bounds.width == 0) {
     bounds.width = 1;
   }
   if (bounds.height == 0) {
     bounds.height = 1;
   }
   return bounds;
 }

 if (!mAcc->IsTextLeaf()) {
   // This could be an empty container. Alternatively, it could be a list
   // bullet,which does provide text but doesn't support character bounds. In
   // either case, return the Accessible's bounds.
   return mAcc->Bounds();
 }

 auto maybeAdjustLineFeedBounds = [this](LayoutDeviceIntRect& aBounds) {
   if (!IsLineFeedChar()) {
     return;
   }
   // Line feeds have a 0 width or height, depending on the writing mode.
   // Use 1 instead so that clients treat it as an actual rectangle; e.g. when
   // displaying the caret when it is positioned on a line feed.
   MOZ_ASSERT(aBounds.IsZeroArea());
   if (aBounds.width == 0) {
     aBounds.width = 1;
   }
   if (aBounds.height == 0) {
     aBounds.height = 1;
   }
 };

 if (LocalAccessible* local = mAcc->AsLocal()) {
   if (mOffset >= 0 &&
       static_cast<uint32_t>(mOffset) >= nsAccUtils::TextLength(local)) {
     // It's valid for a caller to query the length because the caret might be
     // at the end of editable text. In that case, we should just silently
     // return. However, we assert that the offset isn't greater than the
     // length.
     NS_ASSERTION(
         static_cast<uint32_t>(mOffset) <= nsAccUtils::TextLength(local),
         "Wrong in offset");
     return LayoutDeviceIntRect();
   }

   LayoutDeviceIntRect bounds = ComputeBoundsFromFrame();

   // This document may have a resolution set, we will need to multiply
   // the document-relative coordinates by that value and re-apply the doc's
   // screen coordinates.
   nsPresContext* presContext = local->Document()->PresContext();
   nsIFrame* rootFrame = presContext->PresShell()->GetRootFrame();
   LayoutDeviceIntRect orgRectPixels =
       LayoutDeviceIntRect::FromAppUnitsToNearest(
           rootFrame->GetScreenRectInAppUnits(),
           presContext->AppUnitsPerDevPixel());
   bounds.MoveBy(-orgRectPixels.X(), -orgRectPixels.Y());
   bounds.ScaleRoundOut(presContext->PresShell()->GetResolution());
   bounds.MoveBy(orgRectPixels.X(), orgRectPixels.Y());
   maybeAdjustLineFeedBounds(bounds);
   return bounds;
 }

 if (RequestDomainsIfInactive(CacheDomain::TextBounds)) {
   return LayoutDeviceIntRect();
 }
 RemoteAccessible* remote = mAcc->AsRemote();
 if (!remote->mCachedFields) {
   return LayoutDeviceIntRect();
 }

 nsRect charBounds = remote->GetCachedCharRect(mOffset);
 // A character can have 0 width, but we still want its other coordinates.
 // Thus, we explicitly test for an all-0 rect here to determine whether this
 // is a valid char rect, rather than using IsZeroArea or IsEmpty.
 if (!charBounds.IsEqualRect(0, 0, 0, 0)) {
   LayoutDeviceIntRect bounds = remote->BoundsWithOffset(Some(charBounds));
   maybeAdjustLineFeedBounds(bounds);
   return bounds;
 }

 return LayoutDeviceIntRect();
}

bool TextLeafPoint::ContainsPoint(int32_t aX, int32_t aY) {
 if (mAcc && !mAcc->IsText()) {
   // If we're dealing with an empty embedded object, use the
   // accessible's non-text bounds.
   return mAcc->Bounds().Contains(aX, aY);
 }

 return CharBounds().Contains(aX, aY);
}

/*** TextLeafRange ***/

bool TextLeafRange::Crop(Accessible* aContainer) {
 TextLeafPoint containerStart(aContainer, 0);
 TextLeafPoint containerEnd(aContainer,
                            nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT);

 if (mEnd < containerStart || containerEnd < mStart) {
   // The range ends before the container, or starts after it.
   return false;
 }

 if (mStart < containerStart) {
   // If range start is before container start, adjust range start to
   // start of container.
   mStart = containerStart;
 }

 if (containerEnd < mEnd) {
   // If range end is after container end, adjust range end to end of
   // container.
   mEnd = containerEnd;
 }

 return true;
}

LayoutDeviceIntRect TextLeafRange::Bounds() const {
 // We can't simply query the first and last character, and union their bounds.
 // They might reside on different lines, so a simple union may yield an
 // incorrect width. We should use the length of the longest spanned line for
 // our width. To achieve this, walk all the lines and union them into the
 // result rectangle.
 LayoutDeviceIntRect result;
 const bool succeeded = WalkLineRects(
     [&result](TextLeafRange aLine, LayoutDeviceIntRect aLineRect) {
       result.UnionRect(result, aLineRect);
     });

 if (!succeeded) {
   return {};
 }
 return result;
}

nsTArray<LayoutDeviceIntRect> TextLeafRange::LineRects() const {
 // Get the bounds of the content so we can restrict our lines to just the
 // text visible within the bounds of the document.
 Maybe<LayoutDeviceIntRect> contentBounds;
 if (Accessible* doc = nsAccUtils::DocumentFor(mStart.mAcc)) {
   contentBounds.emplace(doc->Bounds());
 }

 nsTArray<LayoutDeviceIntRect> lineRects;
 WalkLineRects([&lineRects, &contentBounds](TextLeafRange aLine,
                                            LayoutDeviceIntRect aLineRect) {
   // Clip the bounds to the bounds of the content area.
   bool boundsVisible = true;
   if (contentBounds.isSome()) {
     boundsVisible = aLineRect.IntersectRect(aLineRect, *contentBounds);
   }
   if (boundsVisible) {
     lineRects.AppendElement(aLineRect);
   }
 });

 return lineRects;
}

TextLeafPoint TextLeafRange::TextLeafPointAtScreenPoint(int32_t aX,
                                                       int32_t aY) const {
 // Step backwards one character to make the endPoint inclusive. This means we
 // can use operator!= when comparing against endPoint below (which is very
 // fast), rather than operator< (which might be significantly slower).
 const TextLeafPoint endPoint =
     mEnd.FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirPrevious);

 // If there are no characters in this container, we might have moved endPoint
 // before mStart. In that case, we shouldn't try to move farther forward, as
 // that might result in an infinite loop.
 TextLeafPoint point = mStart;
 if (mStart <= endPoint) {
   for (; !point.ContainsPoint(aX, aY) && point != endPoint;
        point =
            point.FindBoundary(nsIAccessibleText::BOUNDARY_CHAR, eDirNext)) {
   }
 }

 return point;
}

bool TextLeafRange::SetSelection(int32_t aSelectionNum, bool aSetFocus) const {
 if (!mStart || !mEnd || mStart.mAcc->IsLocal() != mEnd.mAcc->IsLocal()) {
   return false;
 }

 if (mStart.mAcc->IsRemote()) {
   DocAccessibleParent* doc = mStart.mAcc->AsRemote()->Document();
   if (doc != mEnd.mAcc->AsRemote()->Document()) {
     return false;
   }

   (void)doc->SendSetTextSelection(mStart.mAcc->ID(), mStart.mOffset,
                                   mEnd.mAcc->ID(), mEnd.mOffset,
                                   aSelectionNum, aSetFocus);
   return true;
 }

 bool reversed = mEnd < mStart;
 auto [startContent, startContentOffset] =
     !reversed ? mStart.ToDOMPoint(false) : mEnd.ToDOMPoint(false);
 auto [endContent, endContentOffset] =
     !reversed ? mEnd.ToDOMPoint(false) : mStart.ToDOMPoint(false);
 if (!startContent || !endContent) {
   return false;
 }

 RefPtr<dom::Selection> domSel = GetDOMSelection(startContent, endContent);
 if (!domSel) {
   return false;
 }

 HyperTextAccessible* hyp = nullptr;
 if (mStart.mAcc->IsHyperText()) {
   hyp = mStart.mAcc->AsLocal()->AsHyperText();
 } else {
   Accessible* parent = mStart.mAcc->Parent();
   if (parent) {
     hyp = parent->AsLocal()->AsHyperText();
     // Note that hyp will still be null here if the parent is not a HyperText.
     // That's okay.
   }
 }

 // Before setting the selection range, we need to ensure that the editor
 // is initialized. (See bug 804927.)
 // Otherwise, it's possible that lazy editor initialization will override
 // the selection we set here and leave the caret at the end of the text.
 // By calling GetEditor here, we ensure that editor initialization is
 // completed before we set the selection.
 RefPtr<EditorBase> editor;
 if (hyp) {
   editor = hyp->GetEditor();
 }

 // XXX isFocusable will be false if mStart is not a direct child of the
 // contentEditable. However, contentEditables generally don't mess with
 // selection when they are focused. This has also been our behavior for a very
 // long time.
 const bool isFocusable = hyp && hyp->InteractiveState() & states::FOCUSABLE;
 // If the Accessible is focusable, focus it before setting the selection to
 // override the control's own selection changes on focus if any; e.g. inputs
 // that do select all on focus. This also ensures that the user can interact
 // with wherever they've moved the caret. See bug 524115.
 if (aSetFocus && isFocusable) {
   hyp->TakeFocus();
 }

 uint32_t rangeCount = 0;
 if (aSelectionNum == kRemoveAllExistingSelectedRanges) {
   domSel->RemoveAllRanges(IgnoreErrors());
 } else {
   rangeCount = domSel->RangeCount();
 }
 RefPtr<nsRange> domRange = nullptr;
 const bool newRange =
     aSelectionNum == static_cast<int32_t>(rangeCount) || aSelectionNum < 0;
 if (newRange) {
   domRange = nsRange::Create(startContent);
 } else {
   domRange = domSel->GetRangeAt(AssertedCast<uint32_t>(aSelectionNum));
 }
 if (!domRange) {
   return false;
 }

 domRange->SetStart(startContent, startContentOffset);
 domRange->SetEnd(endContent, endContentOffset);

 // If this is not a new range, notify selection listeners that the existing
 // selection range has changed. Otherwise, just add the new range.
 if (!newRange) {
   domSel->RemoveRangeAndUnselectFramesAndNotifyListeners(*domRange,
                                                          IgnoreErrors());
 }

 IgnoredErrorResult err;
 domSel->AddRangeAndSelectFramesAndNotifyListeners(*domRange, err);
 if (err.Failed()) {
   return false;
 }

 // Changing the direction of the selection assures that the caret
 // will be at the logical end of the selection.
 domSel->SetDirection(reversed ? eDirPrevious : eDirNext);

 // Make sure the selection is visible. See bug 1170242.
 domSel->ScrollIntoView(nsISelectionController::SELECTION_FOCUS_REGION,
                        ScrollAxis(), ScrollAxis(),
                        ScrollFlags::ScrollOverflowHidden);

 if (aSetFocus && mStart == mEnd && !isFocusable) {
   // We're moving the caret. Notify nsFocusManager so that the focus position
   // is correct. See bug 546068.
   if (nsFocusManager* DOMFocusManager = nsFocusManager::GetFocusManager()) {
     MOZ_ASSERT(mStart.mAcc->AsLocal()->Document());
     dom::Document* domDoc =
         mStart.mAcc->AsLocal()->Document()->DocumentNode();
     MOZ_ASSERT(domDoc);
     nsCOMPtr<nsPIDOMWindowOuter> window = domDoc->GetWindow();
     RefPtr<dom::Element> result;
     DOMFocusManager->MoveFocus(
         window, nullptr, nsIFocusManager::MOVEFOCUS_CARET,
         nsIFocusManager::FLAG_BYMOVEFOCUS, getter_AddRefs(result));
   }
 }
 return true;
}

/* static */
void TextLeafRange::GetSelection(Accessible* aAcc,
                                nsTArray<TextLeafRange>& aRanges) {
 // Use HyperTextAccessibleBase::SelectionRanges. Eventually, we'll want to
 // move that code into TextLeafPoint, but events and caching are based on
 // HyperText offsets for now.
 HyperTextAccessibleBase* hyp = aAcc->AsHyperTextBase();
 if (!hyp) {
   return;
 }
 AutoTArray<TextRange, 1> hypRanges;
 hyp->CroppedSelectionRanges(hypRanges);
 aRanges.SetCapacity(hypRanges.Length());
 for (TextRange& hypRange : hypRanges) {
   TextLeafPoint start =
       hypRange.StartContainer()->AsHyperTextBase()->ToTextLeafPoint(
           hypRange.StartOffset());
   TextLeafPoint end =
       hypRange.EndContainer()->AsHyperTextBase()->ToTextLeafPoint(
           hypRange.EndOffset());
   aRanges.EmplaceBack(start, end);
 }
}

void TextLeafRange::ScrollIntoView(uint32_t aScrollType) const {
 if (!mStart || !mEnd || mStart.mAcc->IsLocal() != mEnd.mAcc->IsLocal()) {
   return;
 }

 if (mStart.mAcc->IsRemote()) {
   DocAccessibleParent* doc = mStart.mAcc->AsRemote()->Document();
   if (doc != mEnd.mAcc->AsRemote()->Document()) {
     // Can't scroll range that spans docs.
     return;
   }

   (void)doc->SendScrollTextLeafRangeIntoView(mStart.mAcc->ID(),
                                              mStart.mOffset, mEnd.mAcc->ID(),
                                              mEnd.mOffset, aScrollType);
   return;
 }

 auto [startContent, startContentOffset] = mStart.ToDOMPoint();
 auto [endContent, endContentOffset] = mEnd.ToDOMPoint();

 if (!startContent || !endContent) {
   return;
 }

 ErrorResult er;
 RefPtr<nsRange> domRange = nsRange::Create(startContent, startContentOffset,
                                            endContent, endContentOffset, er);
 if (er.Failed()) {
   return;
 }

 nsCoreUtils::ScrollSubstringTo(mStart.mAcc->AsLocal()->GetFrame(), domRange,
                                aScrollType);
}

nsTArray<TextLeafRange> TextLeafRange::VisibleLines(
   Accessible* aContainer) const {
 MOZ_ASSERT(aContainer);
 nsTArray<TextLeafRange> lines;
 if (mStart == mEnd) {
   return lines;
 }
 // We want to restrict our lines to those visible within aContainer.
 LayoutDeviceIntRect containerBounds = aContainer->Bounds();
 WalkLineRects([&lines, &containerBounds](TextLeafRange aLine,
                                          LayoutDeviceIntRect aLineRect) {
   // XXX This doesn't correctly handle lines that are scrolled out where the
   // scroll container is a descendant of aContainer. Such lines might
   // intersect with containerBounds, but the scroll container could be a
   // descendant of aContainer and should thus exclude this line. See bug
   // 1945010 for more details.
   if (aLineRect.Intersects(containerBounds)) {
     lines.AppendElement(aLine);
   }
 });
 return lines;
}

bool TextLeafRange::WalkLineRects(LineRectCallback aCallback) const {
 if (mEnd < mStart) {
   return false;
 }
 if (mStart == mEnd) {
   // Return the insertion point bounds for the offset if range is collapsed.
   aCallback(*this, mStart.InsertionPointBounds());
   return true;
 }

 bool locatedFinalLine = false;
 TextLeafPoint currPoint = mStart;

 // Union the first and last chars of each line to create a line rect.
 while (!locatedFinalLine) {
   TextLeafPoint nextLineStartPoint = currPoint.FindBoundary(
       nsIAccessibleText::BOUNDARY_LINE_START, eDirNext);
   // If currPoint is at the end of the document, nextLineStartPoint will be
   // equal to currPoint. However, this can only happen if mEnd is also the end
   // of the document.
   MOZ_ASSERT(nextLineStartPoint != currPoint || nextLineStartPoint == mEnd);
   if (mEnd <= nextLineStartPoint) {
     // nextLineStart is past the end of the range. Constrain this last line to
     // the end of the range.
     nextLineStartPoint = mEnd;
     locatedFinalLine = true;
   }
   // Fetch the last point in the current line by going back one char from the
   // start of the next line.
   TextLeafPoint lastPointInLine = nextLineStartPoint.FindBoundary(
       nsIAccessibleText::BOUNDARY_CHAR, eDirPrevious);
   MOZ_ASSERT(currPoint <= lastPointInLine);

   LayoutDeviceIntRect currLineRect = currPoint.CharBounds();
   currLineRect.UnionRect(currLineRect, lastPointInLine.CharBounds());
   // The range we pass must include the last character and range ends are
   // exclusive, hence the use of nextLineStartPoint.
   TextLeafRange currLine = TextLeafRange(currPoint, nextLineStartPoint);
   aCallback(currLine, currLineRect);

   currPoint = nextLineStartPoint;
 }
 return true;
}

TextLeafRange::Iterator TextLeafRange::Iterator::BeginIterator(
   const TextLeafRange& aRange) {
 Iterator result(aRange);

 result.mSegmentStart = aRange.mStart;
 if (aRange.mStart.mAcc == aRange.mEnd.mAcc) {
   result.mSegmentEnd = aRange.mEnd;
 } else {
   result.mSegmentEnd = TextLeafPoint(
       aRange.mStart.mAcc, nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT);
 }

 return result;
}

TextLeafRange::Iterator TextLeafRange::Iterator::EndIterator(
   const TextLeafRange& aRange) {
 Iterator result(aRange);

 result.mSegmentEnd = TextLeafPoint();
 result.mSegmentStart = TextLeafPoint();

 return result;
}

TextLeafRange::Iterator& TextLeafRange::Iterator::operator++() {
 if (mSegmentEnd.mAcc == mRange.mEnd.mAcc) {
   mSegmentEnd = TextLeafPoint();
   mSegmentStart = TextLeafPoint();
   return *this;
 }

 if (Accessible* nextLeaf = NextLeaf(mSegmentEnd.mAcc)) {
   mSegmentStart = TextLeafPoint(nextLeaf, 0);
   if (nextLeaf == mRange.mEnd.mAcc) {
     mSegmentEnd = TextLeafPoint(nextLeaf, mRange.mEnd.mOffset);
   } else {
     mSegmentEnd =
         TextLeafPoint(nextLeaf, nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT);
   }
 } else {
   mSegmentEnd = TextLeafPoint();
   mSegmentStart = TextLeafPoint();
 }

 return *this;
}

}  // namespace mozilla::a11y