Quelle  TextLeafRange.cpp   Sprache: C

/* -*- 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 "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()) {
    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},
      };
  result.SetCapacity(std::size(kSelectionTypesToAttributes));
  for (auto [selType, attr] : kSelectionTypesToAttributes) {
    dom::Selection* domSel = frameSel->GetSelection(selType);
    if (!domSel) {
      continue;
    }
    nsTArray<dom::AbstractRange*> domRanges;
    domSel->GetAbstractRangesForIntervalArray(
        node, contentStart, node, contentEnd, aAllowAdjacent, &domRanges);
    if (!domRanges.IsEmpty()) {
      result.AppendElement(std::make_pair(std::move(domRanges), 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*, int32_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() && !mAcc->IsHTMLBr() && !mAcc->HasChildren()) {
    // If this is not a text leaf it can 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};
  }

  return {content, RenderedToContentOffset(mAcc->AsLocal(), mOffset)};
}

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);
}

/*** TextLeafPoint ***/

TextLeafPoint::TextLeafPoint(Accessible* aAcc, int32_t aOffset) {
  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 (aOffset != nsIAccessibleText::TEXT_OFFSET_CARET && !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 HyperTextAccessible::CaretOffset. Eventually, we'll want to move
    // that code into TextLeafPoint, but existing code depends on it living in
    // HyperTextAccessible (including caret events).
    HyperTextAccessible* ht = HyperTextFor(localAcc);
    if (!ht) {
      return TextLeafPoint();
    }
    int32_t htOffset = ht->CaretOffset();
    if (htOffset == -1) {
      return TextLeafPoint();
    }
    TextLeafPoint point = ht->ToTextLeafPoint(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;
    }
    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, it can also mean that 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.
      if (point.mOffset == 0) {
        // The caret is before the start of a node. The caret is at the end of a
        // line if the node is at the start of a line but not at the start of a
        // paragraph.
        point.mIsEndOfLineInsertionPoint =
            IsLocalAccAtLineStart(point.mAcc->AsLocal()) &&
            !point.IsParagraphStart();
      } else {
        // This isn't the start of a node, so we must be 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);
  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) {
      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;
  }
  auto compare = [this](const TextOffsetAttribute& aItem) {
    if (aItem.mStartOffset <= mOffset &&
        (mOffset < aItem.mEndOffset || aItem.mEndOffset == -1)) {
      return 0;
    }
    if (aItem.mStartOffset > mOffset) {
      return -1;
    }
    return 1;
  };
  // With our compare function, EqualRange will find any item which includes
  // mOffset.
  auto [lower, upper] =
      EqualRange(*offsetAttrs, 0, offsetAttrs->Length(), compare);
  for (auto i = lower; i < upper; ++i) {
    expose((*offsetAttrs)[i].mAttribute);
  }
}

TextLeafPoint TextLeafPoint::FindTextOffsetAttributeSameAcc(
    nsDirection aDirection, bool aIncludeOrigin) const {
  if (!aIncludeOrigin && mOffset == 0 && aDirection == eDirPrevious) {
    return TextLeafPoint();
  }
  if (LocalAccessible* acc = mAcc->AsLocal()) {
    // We want to find both start and end points, so we pass true for
    // aAllowAdjacent.
    auto ranges =
        aDirection == eDirNext
            ? FindDOMTextOffsetAttributes(
                  acc, mOffset, nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT,
                  /* aAllowAdjacent */ true)
            : FindDOMTextOffsetAttributes(acc, 0, mOffset,
                                          /* aAllowAdjacent */ true);
    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) {
      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 && (dest == -1 || matchOffset <= dest)) {
              dest = matchOffset;
              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;
              break;
            }
          }
        }
      }
    } else {
      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;
              break;
            }
          }
          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;
              break;
            }
          }
        }
      }
    }
    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();
  }
  auto compare = [this](const TextOffsetAttribute& aItem) {
    // We want to match both start and end offsets, so we use <=
    // aItem.mEndOffset.
    if (aItem.mStartOffset <= mOffset &&
        (mOffset <= aItem.mEndOffset || aItem.mEndOffset == -1)) {
      return 0;
    }
    if (aItem.mStartOffset > mOffset) {
      return -1;
    }
    return 1;
  };
  size_t index;
  if (BinarySearchIf(*offsetAttrs, 0, offsetAttrs->Length(), compare, &index)) {
    // mOffset is within or the end of an offset attribute.
    if (aIncludeOrigin && ((*offsetAttrs)[index].mStartOffset == mOffset ||
                           (*offsetAttrs)[index].mEndOffset == mOffset)) {
      return *this;
    }
    // Check the boundaries of the offset attribute containing mOffset.
    if (aDirection == eDirNext) {
      if ((*offsetAttrs)[index].mEndOffset > mOffset) {
        MOZ_ASSERT((*offsetAttrs)[index].mEndOffset != -1);
        return TextLeafPoint(mAcc, (*offsetAttrs)[index].mEndOffset);
      }
      // We don't want the origin, so move to the next offset attribute after
      // mOffset.
      ++index;
    } else if ((*offsetAttrs)[index].mStartOffset < mOffset &&
               (*offsetAttrs)[index].mStartOffset != -1) {
      return TextLeafPoint(mAcc, (*offsetAttrs)[index].mStartOffset);
    }
  }
  // index points at the next offset attribute after mOffset.
  if (aDirection == eDirNext) {
    if (offsetAttrs->Length() == index) {
      return TextLeafPoint();  // No offset attribute boundary after us.
    }
    return TextLeafPoint(mAcc, (*offsetAttrs)[index].mStartOffset);
  }
  if (index == 0) {
    return TextLeafPoint();  // No offset attribute boundary before us.
  }
  // Decrement index so it points at an offset attribute before mOffset.
  --index;
  return TextLeafPoint(mAcc, (*offsetAttrs)[index].mEndOffset);
}

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());
}

/* 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());
        // Using -1 here means this won't be treated as the start of an
        // attribute range, while still indicating that we're within a text
        // offset attribute.
        data.mStartOffset = -1;
      }
--> --------------------

--> maximum size reached

--> --------------------