Quelle Selection.cpp Sprache: C

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=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/. */

/*
* Implementation of mozilla::dom::Selection
*/

#include "Selection.h"

#include "ErrorList.h"
#include "LayoutConstants.h"
#include "mozilla/AccessibleCaretEventHub.h"
#include "mozilla/Assertions.h"
#include "mozilla/AsyncEventDispatcher.h"
#include "mozilla/Attributes.h"
#include "mozilla/AutoCopyListener.h"
#include "mozilla/AutoRestore.h"
#include "mozilla/BasePrincipal.h"
#include "mozilla/CaretAssociationHint.h"
#include "mozilla/ContentIterator.h"
#include "mozilla/dom/Element.h"
#include "mozilla/dom/ChildIterator.h"
#include "mozilla/dom/SelectionBinding.h"
#include "mozilla/dom/ShadowRoot.h"
#include "mozilla/dom/StaticRange.h"
#include "mozilla/dom/ShadowIncludingTreeIterator.h"
#include "mozilla/ErrorResult.h"
#include "mozilla/HTMLEditor.h"
#include "mozilla/IntegerRange.h"
#include "mozilla/intl/Bidi.h"
#include "mozilla/intl/BidiEmbeddingLevel.h"
#include "mozilla/Logging.h"
#include "mozilla/PresShell.h"
#include "mozilla/RangeBoundary.h"
#include "mozilla/RangeUtils.h"
#include "mozilla/SelectionMovementUtils.h"
#include "mozilla/StackWalk.h"
#include "mozilla/StaticPrefs_dom.h"
#include "mozilla/Telemetry.h"
#include "mozilla/Try.h"

#include "nsCOMPtr.h"
#include "nsDebug.h"
#include "nsDirection.h"
#include "nsString.h"
#include "nsFrameSelection.h"
#include "nsISelectionListener.h"
#include "nsDeviceContext.h"
#include "nsIContent.h"
#include "nsIContentInlines.h"
#include "nsRange.h"
#include "nsITableCellLayout.h"
#include "nsTArray.h"
#include "nsTableWrapperFrame.h"
#include "nsTableCellFrame.h"
#include "nsCCUncollectableMarker.h"
#include "nsIDocumentEncoder.h"
#include "nsTextFragment.h"
#include <algorithm>
#include "nsContentUtils.h"

#include "nsGkAtoms.h"
#include "nsLayoutUtils.h"
#include "nsBidiPresUtils.h"
#include "nsTextFrame.h"

#include "nsThreadUtils.h"

#include "nsPresContext.h"
#include "nsCaret.h"

#include "nsITimer.h"
#include "mozilla/dom/Document.h"
#include "nsINamed.h"

#include "nsISelectionController.h"  //for the enums
#include "nsCopySupport.h"
#include "nsIFrameInlines.h"
#include "nsRefreshDriver.h"

#include "nsError.h"
#include "nsViewManager.h"

#include "nsFocusManager.h"
#include "nsPIDOMWindow.h"

#ifdef ACCESSIBILITY
#  include "nsAccessibilityService.h"
#endif

namespace mozilla {
// "Selection" logs only the calls of AddRangesForSelectableNodes and
// NotifySelectionListeners in debug level.
static LazyLogModule sSelectionLog("Selection");
// "SelectionAPI" logs all API calls (both internal ones and exposed to script
// ones) of normal selection which may change selection ranges.
// 3. Info: Calls of APIs
// 4. Debug: Call stacks with 7 ancestor callers of APIs
// 5. Verbose: Complete call stacks of APIs.
LazyLogModule sSelectionAPILog("SelectionAPI");

MOZ_ALWAYS_INLINE bool NeedsToLogSelectionAPI(dom::Selection& aSelection) {
  return aSelection.Type() == SelectionType::eNormal &&
         MOZ_LOG_TEST(sSelectionAPILog, LogLevel::Info);
}

void LogStackForSelectionAPI() {
  if (!MOZ_LOG_TEST(sSelectionAPILog, LogLevel::Debug)) {
    return;
  }
  static nsAutoCString* sBufPtr = nullptr;
  MOZ_ASSERT(!sBufPtr);
  nsAutoCString buf;
  sBufPtr = &buf;
  auto writer = [](const char* aBuf) { sBufPtr->Append(aBuf); };
  const LogLevel logLevel = MOZ_LOG_TEST(sSelectionAPILog, LogLevel::Verbose)
                                ? LogLevel::Verbose
                                : LogLevel::Debug;
  MozWalkTheStackWithWriter(writer, CallerPC(),
                            logLevel == LogLevel::Verbose
                                ? 0u /* all */
                                : 8u /* 8 inclusive ancestors */);
  MOZ_LOG(sSelectionAPILog, logLevel, ("\n%s", buf.get()));
  sBufPtr = nullptr;
}

static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName) {
  MOZ_LOG(sSelectionAPILog, LogLevel::Info,
          ("%p Selection::%s()", aSelection, aFuncName));
}

static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName, const char* aArgName,
                            const nsINode* aNode) {
  MOZ_LOG(sSelectionAPILog, LogLevel::Info,
          ("%p Selection::%s(%s=%s)", aSelection, aFuncName, aArgName,
           aNode ? ToString(*aNode).c_str() : "nullptr"));
}

static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName, const char* aArgName,
                            const dom::AbstractRange& aRange) {
  MOZ_LOG(sSelectionAPILog, LogLevel::Info,
          ("%p Selection::%s(%s=%s)", aSelection, aFuncName, aArgName,
           ToString(aRange).c_str()));
}

static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName, const char* aArgName1,
                            const nsINode* aNode, const char* aArgName2,
                            uint32_t aOffset) {
  MOZ_LOG(sSelectionAPILog, LogLevel::Info,
          ("%p Selection::%s(%s=%s, %s=%u)", aSelection, aFuncName, aArgName1,
           aNode ? ToString(*aNode).c_str() : "nullptr", aArgName2, aOffset));
}

static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName, const char* aArgName,
                            const RawRangeBoundary& aBoundary) {
  MOZ_LOG(sSelectionAPILog, LogLevel::Info,
          ("%p Selection::%s(%s=%s)", aSelection, aFuncName, aArgName,
           ToString(aBoundary).c_str()));
}

static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName, const char* aArgName1,
                            const nsAString& aStr1, const char* aArgName2,
                            const nsAString& aStr2, const char* aArgName3,
                            const nsAString& aStr3) {
  MOZ_LOG(sSelectionAPILog, LogLevel::Info,
          ("%p Selection::%s(%s=%s, %s=%s, %s=%s)", aSelection, aFuncName,
           aArgName1, NS_ConvertUTF16toUTF8(aStr1).get(), aArgName2,
           NS_ConvertUTF16toUTF8(aStr2).get(), aArgName3,
           NS_ConvertUTF16toUTF8(aStr3).get()));
}

static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName, const char* aNodeArgName1,
                            const nsINode& aNode1, const char* aOffsetArgName1,
                            uint32_t aOffset1, const char* aNodeArgName2,
                            const nsINode& aNode2, const char* aOffsetArgName2,
                            uint32_t aOffset2) {
  if (&aNode1 == &aNode2 && aOffset1 == aOffset2) {
    MOZ_LOG(sSelectionAPILog, LogLevel::Info,
            ("%p Selection::%s(%s=%s=%s, %s=%s=%u)", aSelection, aFuncName,
             aNodeArgName1, aNodeArgName2, ToString(aNode1).c_str(),
             aOffsetArgName1, aOffsetArgName2, aOffset1));
  } else {
    MOZ_LOG(
        sSelectionAPILog, LogLevel::Info,
        ("%p Selection::%s(%s=%s, %s=%u, %s=%s, %s=%u)", aSelection, aFuncName,
         aNodeArgName1, ToString(aNode1).c_str(), aOffsetArgName1, aOffset1,
         aNodeArgName2, ToString(aNode2).c_str(), aOffsetArgName2, aOffset2));
  }
}

static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName, const char* aNodeArgName1,
                            const nsINode& aNode1, const char* aOffsetArgName1,
                            uint32_t aOffset1, const char* aNodeArgName2,
                            const nsINode& aNode2, const char* aOffsetArgName2,
                            uint32_t aOffset2, const char* aDirArgName,
                            nsDirection aDirection, const char* aReasonArgName,
                            int16_t aReason) {
  if (&aNode1 == &aNode2 && aOffset1 == aOffset2) {
    MOZ_LOG(sSelectionAPILog, LogLevel::Info,
            ("%p Selection::%s(%s=%s=%s, %s=%s=%u, %s=%s, %s=%d)", aSelection,
             aFuncName, aNodeArgName1, aNodeArgName2, ToString(aNode1).c_str(),
             aOffsetArgName1, aOffsetArgName2, aOffset1, aDirArgName,
             ToString(aDirection).c_str(), aReasonArgName, aReason));
  } else {
    MOZ_LOG(sSelectionAPILog, LogLevel::Info,
            ("%p Selection::%s(%s=%s, %s=%u, %s=%s, %s=%u, %s=%s, %s=%d)",
             aSelection, aFuncName, aNodeArgName1, ToString(aNode1).c_str(),
             aOffsetArgName1, aOffset1, aNodeArgName2, ToString(aNode2).c_str(),
             aOffsetArgName2, aOffset2, aDirArgName,
             ToString(aDirection).c_str(), aReasonArgName, aReason));
  }
}

static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName, const char* aArgName1,
                            const RawRangeBoundary& aBoundary1,
                            const char* aArgName2,
                            const RawRangeBoundary& aBoundary2) {
  if (aBoundary1 == aBoundary2) {
    MOZ_LOG(sSelectionAPILog, LogLevel::Info,
            ("%p Selection::%s(%s=%s=%s)", aSelection, aFuncName, aArgName1,
             aArgName2, ToString(aBoundary1).c_str()));
  } else {
    MOZ_LOG(sSelectionAPILog, LogLevel::Info,
            ("%p Selection::%s(%s=%s, %s=%s)", aSelection, aFuncName, aArgName1,
             ToString(aBoundary1).c_str(), aArgName2,
             ToString(aBoundary2).c_str()));
  }
}
}  // namespace mozilla

using namespace mozilla;
using namespace mozilla::dom;

// #define DEBUG_TABLE 1

#ifdef PRINT_RANGE
static void printRange(nsRange* aDomRange);
#  define DEBUG_OUT_RANGE(x) printRange(x)
#else
#  define DEBUG_OUT_RANGE(x)
#endif  // PRINT_RANGE

static constexpr nsLiteralCString kNoDocumentTypeNodeError =
    "DocumentType nodes are not supported"_ns;
static constexpr nsLiteralCString kNoRangeExistsError =
    "No selection range exists"_ns;

namespace mozilla {

/******************************************************************************
* Utility methods defined in nsISelectionListener.idl
******************************************************************************/

nsCString SelectionChangeReasonsToCString(int16_t aReasons) {
  nsCString reasons;
  if (!aReasons) {
    reasons.AssignLiteral("NO_REASON");
    return reasons;
  }
  auto EnsureSeparator = [](nsCString& aString) -> void {
    if (!aString.IsEmpty()) {
      aString.AppendLiteral(" | ");
    }
  };
  struct ReasonData {
    int16_t mReason;
    const char* mReasonStr;

    ReasonData(int16_t aReason, const char* aReasonStr)
        : mReason(aReason), mReasonStr(aReasonStr) {}
  };
  for (const ReasonData& reason :
       {ReasonData(nsISelectionListener::DRAG_REASON, "DRAG_REASON"),
        ReasonData(nsISelectionListener::MOUSEDOWN_REASON, "MOUSEDOWN_REASON"),
        ReasonData(nsISelectionListener::MOUSEUP_REASON, "MOUSEUP_REASON"),
        ReasonData(nsISelectionListener::KEYPRESS_REASON, "KEYPRESS_REASON"),
        ReasonData(nsISelectionListener::SELECTALL_REASON, "SELECTALL_REASON"),
        ReasonData(nsISelectionListener::COLLAPSETOSTART_REASON,
                   "COLLAPSETOSTART_REASON"),
        ReasonData(nsISelectionListener::COLLAPSETOEND_REASON,
                   "COLLAPSETOEND_REASON"),
        ReasonData(nsISelectionListener::IME_REASON, "IME_REASON"),
        ReasonData(nsISelectionListener::JS_REASON, "JS_REASON")}) {
    if (aReasons & reason.mReason) {
      EnsureSeparator(reasons);
      reasons.Append(reason.mReasonStr);
    }
  }
  return reasons;
}

}  // namespace mozilla

SelectionNodeCache::SelectionNodeCache(PresShell& aOwningPresShell)
    : mOwningPresShell(aOwningPresShell) {
  MOZ_ASSERT(!mOwningPresShell.mSelectionNodeCache);
  mOwningPresShell.mSelectionNodeCache = this;
}

SelectionNodeCache::~SelectionNodeCache() {
  mOwningPresShell.mSelectionNodeCache = nullptr;
}

bool SelectionNodeCache::MaybeCollectNodesAndCheckIfFullySelectedInAnyOf(
    const nsINode* aNode, const nsTArray<Selection*>& aSelections) {
  for (const auto* sel : aSelections) {
    if (MaybeCollectNodesAndCheckIfFullySelected(aNode, sel)) {
      return true;
    }
  }
  return false;
}

const nsTHashSet<const nsINode*>& SelectionNodeCache::MaybeCollect(
    const Selection* aSelection) {
  MOZ_ASSERT(aSelection);
  return mSelectedNodes.LookupOrInsertWith(aSelection, [sel = RefPtr(
                                                            aSelection)] {
    nsTHashSet<const nsINode*> fullySelectedNodes;
    for (size_t rangeIndex = 0; rangeIndex < sel->RangeCount(); ++rangeIndex) {
      AbstractRange* range = sel->GetAbstractRangeAt(rangeIndex);
      MOZ_ASSERT(range);
      if (range->Collapsed()) {
        continue;
      }
      if (range->IsStaticRange() && !range->AsStaticRange()->IsValid()) {
        continue;
      }
      const RangeBoundary& startRef = range->MayCrossShadowBoundaryStartRef();
      const RangeBoundary& endRef = range->MayCrossShadowBoundaryEndRef();

      const nsINode* startContainer =
          startRef.IsStartOfContainer() ? nullptr : startRef.Container();
      const nsINode* endContainer =
          endRef.IsEndOfContainer() ? nullptr : endRef.Container();
      UnsafePreContentIterator iter;
      nsresult rv = iter.Init(range);
      if (NS_FAILED(rv)) {
        continue;
      }
      for (; !iter.IsDone(); iter.Next()) {
        if (const nsINode* node = iter.GetCurrentNode()) {
          // Only collect start and end container if they are fully
          // selected (they are null in that case).
          if (node == startContainer || node == endContainer) {
            continue;
          }
          fullySelectedNodes.Insert(node);
        }
      }
    }
    return fullySelectedNodes;
  });
}

// #define DEBUG_SELECTION // uncomment for printf describing every collapse and
//  extend. #define DEBUG_NAVIGATION

// #define DEBUG_TABLE_SELECTION 1

struct CachedOffsetForFrame {
  CachedOffsetForFrame()
      : mCachedFrameOffset(0, 0)  // nsPoint ctor
        ,
        mLastCaretFrame(nullptr),
        mLastContentOffset(0),
        mCanCacheFrameOffset(false) {}

  nsPoint mCachedFrameOffset;  // cached frame offset
  nsIFrame* mLastCaretFrame;   // store the frame the caret was last drawn in.
  int32_t mLastContentOffset;  // store last content offset
  bool mCanCacheFrameOffset;   // cached frame offset is valid?
};

class AutoScroller final : public nsITimerCallback, public nsINamed {
public:
  NS_DECL_ISUPPORTS

  explicit AutoScroller(nsFrameSelection* aFrameSelection)
      : mFrameSelection(aFrameSelection),
        mPresContext(0),
        mPoint(0, 0),
        mDelayInMs(30),
        mFurtherScrollingAllowed(FurtherScrollingAllowed::kYes) {
    MOZ_ASSERT(mFrameSelection);
  }

  MOZ_CAN_RUN_SCRIPT nsresult DoAutoScroll(nsIFrame* aFrame, nsPoint aPoint);

private:
  // aPoint is relative to aPresContext's root frame
  nsresult ScheduleNextDoAutoScroll(nsPresContext* aPresContext,
                                    nsPoint& aPoint) {
    if (NS_WARN_IF(mFurtherScrollingAllowed == FurtherScrollingAllowed::kNo)) {
      return NS_ERROR_FAILURE;
    }

    mPoint = aPoint;

    // Store the presentation context. The timer will be
    // stopped by the selection if the prescontext is destroyed.
    mPresContext = aPresContext;

    mContent = PresShell::GetCapturingContent();

    if (!mTimer) {
      mTimer = NS_NewTimer(GetMainThreadSerialEventTarget());
      if (!mTimer) {
        return NS_ERROR_OUT_OF_MEMORY;
      }
    }

    return mTimer->InitWithCallback(this, mDelayInMs, nsITimer::TYPE_ONE_SHOT);
  }

public:
  enum class FurtherScrollingAllowed { kYes, kNo };

  void Stop(const FurtherScrollingAllowed aFurtherScrollingAllowed) {
    MOZ_ASSERT((aFurtherScrollingAllowed == FurtherScrollingAllowed::kNo) ||
               (mFurtherScrollingAllowed == FurtherScrollingAllowed::kYes));

    if (mTimer) {
      mTimer->Cancel();
      mTimer = nullptr;
    }

    mContent = nullptr;
    mFurtherScrollingAllowed = aFurtherScrollingAllowed;
  }

  void SetDelay(uint32_t aDelayInMs) { mDelayInMs = aDelayInMs; }

  MOZ_CAN_RUN_SCRIPT_BOUNDARY NS_IMETHOD Notify(nsITimer* timer) override {
    if (mPresContext) {
      AutoWeakFrame frame =
          mContent ? mPresContext->GetPrimaryFrameFor(mContent) : nullptr;
      if (!frame) {
        return NS_OK;
      }
      mContent = nullptr;

      nsPoint pt = mPoint - frame->GetOffsetTo(
                                mPresContext->PresShell()->GetRootFrame());
      RefPtr<nsFrameSelection> frameSelection = mFrameSelection;
      frameSelection->HandleDrag(frame, pt);
      if (!frame.IsAlive()) {
        return NS_OK;
      }

      NS_ASSERTION(frame->PresContext() == mPresContext, "document mismatch?");
      DoAutoScroll(frame, pt);
    }
    return NS_OK;
  }

  NS_IMETHOD GetName(nsACString& aName) override {
    aName.AssignLiteral("AutoScroller");
    return NS_OK;
  }

protected:
  virtual ~AutoScroller() {
    if (mTimer) {
      mTimer->Cancel();
    }
  }

private:
  nsFrameSelection* const mFrameSelection;
  nsPresContext* mPresContext;
  // relative to mPresContext's root frame
  nsPoint mPoint;
  nsCOMPtr<nsITimer> mTimer;
  nsCOMPtr<nsIContent> mContent;
  uint32_t mDelayInMs;
  FurtherScrollingAllowed mFurtherScrollingAllowed;
};

NS_IMPL_ISUPPORTS(AutoScroller, nsITimerCallback, nsINamed)

#ifdef PRINT_RANGE
void printRange(nsRange* aDomRange) {
  if (!aDomRange) {
    printf("NULL Range\n");
  }
  nsINode* startNode = aDomRange->GetStartContainer();
  nsINode* endNode = aDomRange->GetEndContainer();
  int32_t startOffset = aDomRange->StartOffset();
  int32_t endOffset = aDomRange->EndOffset();

  printf("range: 0x%lx\t start: 0x%lx %ld, \t end: 0x%lx,%ld\n",
         (unsigned long)aDomRange, (unsigned long)startNode, (long)startOffset,
         (unsigned long)endNode, (long)endOffset);
}
#endif /* PRINT_RANGE */

void Selection::Stringify(nsAString& aResult, FlushFrames aFlushFrames) {
  if (aFlushFrames == FlushFrames::Yes) {
    // We need FlushType::Frames here to make sure frames have been created for
    // the selected content.  Use mFrameSelection->GetPresShell() which returns
    // null if the Selection has been disconnected (the shell is Destroyed).
    RefPtr<PresShell> presShell =
        mFrameSelection ? mFrameSelection->GetPresShell() : nullptr;
    if (!presShell) {
      aResult.Truncate();
      return;
    }
    presShell->FlushPendingNotifications(FlushType::Frames);
  }

  IgnoredErrorResult rv;
  ToStringWithFormat(u"text/plain"_ns, nsIDocumentEncoder::SkipInvisibleContent,
                     0, aResult, rv);
  if (rv.Failed()) {
    aResult.Truncate();
  }
}

void Selection::ToStringWithFormat(const nsAString& aFormatType,
                                   uint32_t aFlags, int32_t aWrapCol,
                                   nsAString& aReturn, ErrorResult& aRv) {
  nsCOMPtr<nsIDocumentEncoder> encoder =
      do_createDocumentEncoder(NS_ConvertUTF16toUTF8(aFormatType).get());
  if (!encoder) {
    aRv.Throw(NS_ERROR_FAILURE);
    return;
  }

  PresShell* presShell = GetPresShell();
  if (!presShell) {
    aRv.Throw(NS_ERROR_FAILURE);
    return;
  }

  Document* doc = presShell->GetDocument();

  // Flags should always include OutputSelectionOnly if we're coming from here:
  aFlags |= nsIDocumentEncoder::OutputSelectionOnly;
  nsAutoString readstring;
  readstring.Assign(aFormatType);
  nsresult rv = encoder->Init(doc, readstring, aFlags);
  if (NS_FAILED(rv)) {
    aRv.Throw(rv);
    return;
  }

  encoder->SetSelection(this);
  if (aWrapCol != 0) encoder->SetWrapColumn(aWrapCol);

  rv = encoder->EncodeToString(aReturn);
  if (NS_FAILED(rv)) {
    aRv.Throw(rv);
  }
}

nsresult Selection::SetInterlinePosition(InterlinePosition aInterlinePosition) {
  MOZ_ASSERT(mSelectionType == SelectionType::eNormal);
  MOZ_ASSERT(aInterlinePosition != InterlinePosition::Undefined);

  if (!mFrameSelection) {
    return NS_ERROR_NOT_INITIALIZED;  // Can't do selection
  }

  mFrameSelection->SetHint(aInterlinePosition ==
                                   InterlinePosition::StartOfNextLine
                               ? CaretAssociationHint::After
                               : CaretAssociationHint::Before);
  return NS_OK;
}

Selection::InterlinePosition Selection::GetInterlinePosition() const {
  MOZ_ASSERT(mSelectionType == SelectionType::eNormal);

  if (!mFrameSelection) {
    return InterlinePosition::Undefined;
  }
  return mFrameSelection->GetHint() == CaretAssociationHint::After
             ? InterlinePosition::StartOfNextLine
             : InterlinePosition::EndOfLine;
}

void Selection::SetInterlinePositionJS(bool aHintRight, ErrorResult& aRv) {
  MOZ_ASSERT(mSelectionType == SelectionType::eNormal);

  aRv = SetInterlinePosition(aHintRight ? InterlinePosition::StartOfNextLine
                                        : InterlinePosition::EndOfLine);
}

bool Selection::GetInterlinePositionJS(ErrorResult& aRv) const {
  const InterlinePosition interlinePosition = GetInterlinePosition();
  if (interlinePosition == InterlinePosition::Undefined) {
    aRv.Throw(NS_ERROR_NOT_INITIALIZED);  // Can't do selection
    return false;
  }
  return interlinePosition == InterlinePosition::StartOfNextLine;
}

static bool IsEditorNode(const nsINode* aNode) {
  if (!aNode) {
    return false;
  }

  if (aNode->IsEditable()) {
    return true;
  }

  auto* element = Element::FromNode(aNode);
  return element && element->State().HasState(ElementState::READWRITE);
}

bool Selection::IsEditorSelection() const {
  return IsEditorNode(GetFocusNode());
}

Nullable<int16_t> Selection::GetCaretBidiLevel(
    mozilla::ErrorResult& aRv) const {
  MOZ_ASSERT(mSelectionType == SelectionType::eNormal);

  if (!mFrameSelection) {
    aRv.Throw(NS_ERROR_NOT_INITIALIZED);
    return Nullable<int16_t>();
  }
  mozilla::intl::BidiEmbeddingLevel caretBidiLevel =
      static_cast<mozilla::intl::BidiEmbeddingLevel>(
          mFrameSelection->GetCaretBidiLevel());
  return (caretBidiLevel & BIDI_LEVEL_UNDEFINED)
             ? Nullable<int16_t>()
             : Nullable<int16_t>(caretBidiLevel);
}

void Selection::SetCaretBidiLevel(const Nullable<int16_t>& aCaretBidiLevel,
                                  mozilla::ErrorResult& aRv) {
  MOZ_ASSERT(mSelectionType == SelectionType::eNormal);

  if (!mFrameSelection) {
    aRv.Throw(NS_ERROR_NOT_INITIALIZED);
    return;
  }
  if (aCaretBidiLevel.IsNull()) {
    mFrameSelection->UndefineCaretBidiLevel();
  } else {
    mFrameSelection->SetCaretBidiLevelAndMaybeSchedulePaint(
        mozilla::intl::BidiEmbeddingLevel(aCaretBidiLevel.Value()));
  }
}

/**
* Test whether the supplied range points to a single table element.
* Result is one of the TableSelectionMode constants. "None" means
* a table element isn't selected.
*/
// TODO: Figure out TableSelectionMode::Column and TableSelectionMode::AllCells
static nsresult GetTableSelectionMode(const nsRange& aRange,
                                      TableSelectionMode* aTableSelectionType) {
  if (!aTableSelectionType) {
    return NS_ERROR_NULL_POINTER;
  }

  *aTableSelectionType = TableSelectionMode::None;

  nsINode* startNode = aRange.GetStartContainer();
  if (!startNode) {
    return NS_ERROR_FAILURE;
  }

  nsINode* endNode = aRange.GetEndContainer();
  if (!endNode) {
    return NS_ERROR_FAILURE;
  }

  // Not a single selected node
  if (startNode != endNode) {
    return NS_OK;
  }

  nsIContent* child = aRange.GetChildAtStartOffset();

  // Not a single selected node
  if (!child || child->GetNextSibling() != aRange.GetChildAtEndOffset()) {
    return NS_OK;
  }

  if (!startNode->IsHTMLElement()) {
    // Implies a check for being an element; if we ever make this work
    // for non-HTML, need to keep checking for elements.
    return NS_OK;
  }

  if (startNode->IsHTMLElement(nsGkAtoms::tr)) {
    *aTableSelectionType = TableSelectionMode::Cell;
  } else  // check to see if we are selecting a table or row (column and all
          // cells not done yet)
  {
    if (child->IsHTMLElement(nsGkAtoms::table)) {
      *aTableSelectionType = TableSelectionMode::Table;
    } else if (child->IsHTMLElement(nsGkAtoms::tr)) {
      *aTableSelectionType = TableSelectionMode::Row;
    }
  }

  return NS_OK;
}

nsresult Selection::MaybeAddTableCellRange(nsRange& aRange,
                                           Maybe<size_t>* aOutIndex) {
  if (!aOutIndex) {
    return NS_ERROR_NULL_POINTER;
  }

  MOZ_ASSERT(aOutIndex->isNothing());

  if (!mFrameSelection) {
    return NS_OK;
  }

  // Get if we are adding a cell selection and the row, col of cell if we are
  TableSelectionMode tableMode;
  nsresult result = GetTableSelectionMode(aRange, &tableMode);
  if (NS_FAILED(result)) return result;

  // If not adding a cell range, we are done here
  if (tableMode != TableSelectionMode::Cell) {
    mFrameSelection->mTableSelection.mMode = tableMode;
    // Don't fail if range isn't a selected cell, aDidAddRange tells caller if
    // we didn't proceed
    return NS_OK;
  }

  // Set frame selection mode only if not already set to a table mode
  // so we don't lose the select row and column flags (not detected by
  // getTableCellLocation)
  if (mFrameSelection->mTableSelection.mMode == TableSelectionMode::None) {
    mFrameSelection->mTableSelection.mMode = tableMode;
  }

  return AddRangesForSelectableNodes(&aRange, aOutIndex,
                                     DispatchSelectstartEvent::Maybe);
}

Selection::Selection(SelectionType aSelectionType,
                     nsFrameSelection* aFrameSelection)
    : mFrameSelection(aFrameSelection),
      mCachedOffsetForFrame(nullptr),
      mDirection(eDirNext),
      mSelectionType(aSelectionType),
      mCustomColors(nullptr),
      mSelectionChangeBlockerCount(0),
      mUserInitiated(false),
      mCalledByJS(false),
      mNotifyAutoCopy(false) {}

Selection::~Selection() { Disconnect(); }

void Selection::Disconnect() {
  RemoveAnchorFocusRange();

  mStyledRanges.UnregisterSelection();

  if (mAutoScroller) {
    mAutoScroller->Stop(AutoScroller::FurtherScrollingAllowed::kNo);
    mAutoScroller = nullptr;
  }

  mScrollEvent.Revoke();

  if (mCachedOffsetForFrame) {
    delete mCachedOffsetForFrame;
    mCachedOffsetForFrame = nullptr;
  }
}

Document* Selection::GetParentObject() const {
  PresShell* presShell = GetPresShell();
  return presShell ? presShell->GetDocument() : nullptr;
}

DocGroup* Selection::GetDocGroup() const {
  PresShell* presShell = GetPresShell();
  if (!presShell) {
    return nullptr;
  }
  Document* doc = presShell->GetDocument();
  return doc ? doc->GetDocGroup() : nullptr;
}

NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE_CLASS(Selection)

MOZ_CAN_RUN_SCRIPT_BOUNDARY
NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(Selection)
  // Unlink the selection listeners *before* we do RemoveAllRangesInternal since
  // we don't want to notify the listeners during JS GC (they could be
  // in JS!).
  tmp->mNotifyAutoCopy = false;
  if (tmp->mAccessibleCaretEventHub) {
    tmp->StopNotifyingAccessibleCaretEventHub();
  }
  NS_IMPL_CYCLE_COLLECTION_UNLINK(mSelectionChangeEventDispatcher)
  NS_IMPL_CYCLE_COLLECTION_UNLINK(mSelectionListeners)
  MOZ_KnownLive(tmp)->RemoveAllRangesInternal(IgnoreErrors());
  NS_IMPL_CYCLE_COLLECTION_UNLINK(mFrameSelection)
  NS_IMPL_CYCLE_COLLECTION_UNLINK(mHighlightData.mHighlight)
  NS_IMPL_CYCLE_COLLECTION_UNLINK_PRESERVED_WRAPPER
  NS_IMPL_CYCLE_COLLECTION_UNLINK_WEAK_PTR
  NS_IMPL_CYCLE_COLLECTION_UNLINK_WEAK_REFERENCE
NS_IMPL_CYCLE_COLLECTION_UNLINK_END
NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN(Selection)
  {
    uint32_t i, count = tmp->mStyledRanges.Length();
    for (i = 0; i < count; ++i) {
      NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mStyledRanges.mRanges[i].mRange)
    }
    count = tmp->mStyledRanges.mInvalidStaticRanges.Length();
    for (i = 0; i < count; ++i) {
      NS_IMPL_CYCLE_COLLECTION_TRAVERSE(
          mStyledRanges.mInvalidStaticRanges[i].mRange);
    }
  }
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mAnchorFocusRange)
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mFrameSelection)
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mHighlightData.mHighlight)
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mSelectionChangeEventDispatcher)
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mSelectionListeners)
NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END

// QueryInterface implementation for Selection
NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(Selection)
  NS_WRAPPERCACHE_INTERFACE_MAP_ENTRY
  NS_INTERFACE_MAP_ENTRY(nsISupportsWeakReference)
  NS_INTERFACE_MAP_ENTRY(nsISupports)
NS_INTERFACE_MAP_END

NS_IMPL_CYCLE_COLLECTING_ADDREF(Selection)
NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_LAST_RELEASE(Selection, Disconnect())

const RangeBoundary& Selection::AnchorRef(
    AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) const {
  if (!mAnchorFocusRange) {
    static RangeBoundary sEmpty;
    return sEmpty;
  }

  if (GetDirection() == eDirNext) {
    return aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes
               ? mAnchorFocusRange->MayCrossShadowBoundaryStartRef()
               : mAnchorFocusRange->StartRef();
  }

  return aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes
             ? mAnchorFocusRange->MayCrossShadowBoundaryEndRef()
             : mAnchorFocusRange->EndRef();
}

const RangeBoundary& Selection::FocusRef(
    AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) const {
  if (!mAnchorFocusRange) {
    static RangeBoundary sEmpty;
    return sEmpty;
  }

  if (GetDirection() == eDirNext) {
    return aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes
               ? mAnchorFocusRange->MayCrossShadowBoundaryEndRef()
               : mAnchorFocusRange->EndRef();
  }
  return aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes
             ? mAnchorFocusRange->MayCrossShadowBoundaryStartRef()
             : mAnchorFocusRange->StartRef();
}

void Selection::SetAnchorFocusRange(size_t aIndex) {
  if (aIndex >= mStyledRanges.Length()) {
    return;
  }
  // Highlight selections may contain static ranges.
  MOZ_ASSERT(mSelectionType != SelectionType::eHighlight);
  AbstractRange* anchorFocusRange = mStyledRanges.mRanges[aIndex].mRange;
  mAnchorFocusRange = anchorFocusRange->AsDynamicRange();
}

static int32_t CompareToRangeStart(const nsINode& aCompareNode,
                                   uint32_t aCompareOffset,
                                   const AbstractRange& aRange,
                                   nsContentUtils::NodeIndexCache* aCache) {
  MOZ_ASSERT(aRange.GetMayCrossShadowBoundaryStartContainer());
  nsINode* start = aRange.GetMayCrossShadowBoundaryStartContainer();
  // If the nodes that we're comparing are not in the same document, assume that
  // aCompareNode will fall at the end of the ranges.
  if (aCompareNode.GetComposedDoc() != start->GetComposedDoc() ||
      !start->GetComposedDoc()) {
    NS_WARNING(
        "`CompareToRangeStart` couldn't compare nodes, pretending some order.");
    return 1;
  }

  // The points are in the same subtree, hence there has to be an order.
  return *nsContentUtils::ComparePoints(
      &aCompareNode, aCompareOffset, start,
      aRange.MayCrossShadowBoundaryStartOffset(), aCache);
}

static int32_t CompareToRangeStart(const nsINode& aCompareNode,
                                   uint32_t aCompareOffset,
                                   const AbstractRange& aRange) {
  return CompareToRangeStart(aCompareNode, aCompareOffset, aRange, nullptr);
}

static int32_t CompareToRangeEnd(const nsINode& aCompareNode,
                                 uint32_t aCompareOffset,
                                 const AbstractRange& aRange) {
  MOZ_ASSERT(aRange.IsPositioned());
  nsINode* end = aRange.GetMayCrossShadowBoundaryEndContainer();
  // If the nodes that we're comparing are not in the same document or in the
  // same subtree, assume that aCompareNode will fall at the end of the ranges.
  if (aCompareNode.GetComposedDoc() != end->GetComposedDoc() ||
      !end->GetComposedDoc()) {
    NS_WARNING(
        "`CompareToRangeEnd` couldn't compare nodes, pretending some order.");
    return 1;
  }

  // The points are in the same subtree, hence there has to be an order.
  return *nsContentUtils::ComparePoints(
      &aCompareNode, aCompareOffset, end,
      aRange.MayCrossShadowBoundaryEndOffset());
}

// static
size_t Selection::StyledRanges::FindInsertionPoint(
    const nsTArray<StyledRange>* aElementArray, const nsINode& aPointNode,
    uint32_t aPointOffset,
    int32_t (*aComparator)(const nsINode&, uint32_t, const AbstractRange&)) {
  int32_t beginSearch = 0;
  int32_t endSearch = aElementArray->Length();  // one beyond what to check

  if (endSearch) {
    int32_t center = endSearch - 1;  // Check last index, then binary search
    do {
      const AbstractRange* range = (*aElementArray)[center].mRange;

      int32_t cmp{aComparator(aPointNode, aPointOffset, *range)};

      if (cmp < 0) {  // point < cur
        endSearch = center;
      } else if (cmp > 0) {  // point > cur
        beginSearch = center + 1;
      } else {  // found match, done
        beginSearch = center;
        break;
      }
      center = (endSearch - beginSearch) / 2 + beginSearch;
    } while (endSearch - beginSearch > 0);
  }

  return AssertedCast<size_t>(beginSearch);
}

// Selection::SubtractRange
//
//    A helper function that subtracts aSubtract from aRange, and adds
//    1 or 2 StyledRange objects representing the remaining non-overlapping
//    difference to aOutput. It is assumed that the caller has checked that
//    aRange and aSubtract do indeed overlap

// static
nsresult Selection::StyledRanges::SubtractRange(
    StyledRange& aRange, nsRange& aSubtract, nsTArray<StyledRange>* aOutput) {
  AbstractRange* range = aRange.mRange;
  if (NS_WARN_IF(!range->IsPositioned())) {
    return NS_ERROR_UNEXPECTED;
  }

  if (range->GetStartContainer()->SubtreeRoot() !=
      aSubtract.GetStartContainer()->SubtreeRoot()) {
    // These are ranges for different shadow trees, we can't subtract them in
    // any sensible way.
    aOutput->InsertElementAt(0, aRange);
    return NS_OK;
  }

  // First we want to compare to the range start
  int32_t cmp{CompareToRangeStart(*range->GetStartContainer(),
                                  range->StartOffset(), aSubtract)};

  // Also, make a comparison to the range end
  int32_t cmp2{CompareToRangeEnd(*range->GetEndContainer(), range->EndOffset(),
                                 aSubtract)};

  // If the existing range left overlaps the new range (aSubtract) then
  // cmp < 0, and cmp2 < 0
  // If it right overlaps the new range then cmp > 0 and cmp2 > 0
  // If it fully contains the new range, then cmp < 0 and cmp2 > 0

  if (cmp2 > 0) {
    // We need to add a new StyledRange to the output, running from
    // the end of aSubtract to the end of range
    ErrorResult error;
    RefPtr<nsRange> postOverlap =
        nsRange::Create(aSubtract.EndRef(), range->EndRef(), error);
    if (NS_WARN_IF(error.Failed())) {
      return error.StealNSResult();
    }
    MOZ_ASSERT(postOverlap);
    if (!postOverlap->Collapsed()) {
      // XXX(Bug 1631371) Check if this should use a fallible operation as it
      // pretended earlier.
      aOutput->InsertElementAt(0, StyledRange(postOverlap));
      (*aOutput)[0].mTextRangeStyle = aRange.mTextRangeStyle;
    }
  }

  if (cmp < 0) {
    // We need to add a new StyledRange to the output, running from
    // the start of the range to the start of aSubtract
    ErrorResult error;
    RefPtr<nsRange> preOverlap =
        nsRange::Create(range->StartRef(), aSubtract.StartRef(), error);
    if (NS_WARN_IF(error.Failed())) {
      return error.StealNSResult();
    }
    MOZ_ASSERT(preOverlap);
    if (!preOverlap->Collapsed()) {
      // XXX(Bug 1631371) Check if this should use a fallible operation as it
      // pretended earlier.
      aOutput->InsertElementAt(0, StyledRange(preOverlap));
      (*aOutput)[0].mTextRangeStyle = aRange.mTextRangeStyle;
    }
  }

  return NS_OK;
}

static void UserSelectRangesToAdd(nsRange* aItem,
                                  nsTArray<RefPtr<nsRange>>& aRangesToAdd) {
  // We cannot directly call IsEditorSelection() because we may be in an
  // inconsistent state during Collapse() (we're cleared already but we haven't
  // got a new focus node yet).
  if (IsEditorNode(aItem->GetStartContainer()) &&
      IsEditorNode(aItem->GetEndContainer())) {
    // Don't mess with the selection ranges for editing, editor doesn't really
    // deal well with multi-range selections.
    aRangesToAdd.AppendElement(aItem);
  } else {
    aItem->ExcludeNonSelectableNodes(&aRangesToAdd);
  }
}

static nsINode* DetermineSelectstartEventTarget(
    const bool aSelectionEventsOnTextControlsEnabled, const nsRange& aRange) {
  nsINode* target = aRange.GetStartContainer();
  if (aSelectionEventsOnTextControlsEnabled) {
    // Get the first element which isn't in a native anonymous subtree
    while (target && target->IsInNativeAnonymousSubtree()) {
      target = target->GetParent();
    }
  } else {
    if (target->IsInNativeAnonymousSubtree()) {
      // This is a selection under a text control, so don't dispatch the
      // event.
      target = nullptr;
    }
  }
  return target;
}

/**
* @return true, iff the default action should be executed.
*/
static bool MaybeDispatchSelectstartEvent(
    const nsRange& aRange, const bool aSelectionEventsOnTextControlsEnabled,
    Document* aDocument) {
  nsCOMPtr<nsINode> selectstartEventTarget = DetermineSelectstartEventTarget(
      aSelectionEventsOnTextControlsEnabled, aRange);

  bool executeDefaultAction = true;

  if (selectstartEventTarget) {
    nsContentUtils::DispatchTrustedEvent(
        aDocument, selectstartEventTarget, u"selectstart"_ns, CanBubble::eYes,
        Cancelable::eYes, &executeDefaultAction);
  }

  return executeDefaultAction;
}

// static
bool Selection::IsUserSelectionCollapsed(
    const nsRange& aRange, nsTArray<RefPtr<nsRange>>& aTempRangesToAdd) {
  MOZ_ASSERT(aTempRangesToAdd.IsEmpty());

  RefPtr<nsRange> scratchRange = aRange.CloneRange();
  UserSelectRangesToAdd(scratchRange, aTempRangesToAdd);
  const bool userSelectionCollapsed =
      (aTempRangesToAdd.Length() == 0) ||
      ((aTempRangesToAdd.Length() == 1) && aTempRangesToAdd[0]->Collapsed());

  aTempRangesToAdd.ClearAndRetainStorage();

  return userSelectionCollapsed;
}

nsresult Selection::AddRangesForUserSelectableNodes(
    nsRange* aRange, Maybe<size_t>* aOutIndex,
    const DispatchSelectstartEvent aDispatchSelectstartEvent) {
  MOZ_ASSERT(mUserInitiated);
  MOZ_ASSERT(aOutIndex);
  MOZ_ASSERT(aOutIndex->isNothing());

  if (!aRange) {
    return NS_ERROR_NULL_POINTER;
  }

  if (!aRange->IsPositioned()) {
    return NS_ERROR_UNEXPECTED;
  }

  AutoTArray<RefPtr<nsRange>, 4> rangesToAdd;
  if (mStyledRanges.Length()) {
    aOutIndex->emplace(mStyledRanges.Length() - 1);
  }

  Document* doc = GetDocument();

  if (aDispatchSelectstartEvent == DispatchSelectstartEvent::Maybe &&
      mSelectionType == SelectionType::eNormal && IsCollapsed() &&
      !IsBlockingSelectionChangeEvents()) {
    // We consider a selection to be starting if we are currently collapsed,
    // and the selection is becoming uncollapsed, and this is caused by a
    // user initiated event.

    // First, we generate the ranges to add with a scratch range, which is a
    // clone of the original range passed in. We do this seperately, because
    // the selectstart event could have caused the world to change, and
    // required ranges to be re-generated

    const bool userSelectionCollapsed =
        IsUserSelectionCollapsed(*aRange, rangesToAdd);
    MOZ_ASSERT(userSelectionCollapsed || nsContentUtils::IsSafeToRunScript());
    if (!userSelectionCollapsed && nsContentUtils::IsSafeToRunScript()) {
      // The spec currently doesn't say that we should dispatch this event
      // on text controls, so for now we only support doing that under a
      // pref, disabled by default.
      // See https://github.com/w3c/selection-api/issues/53.
      const bool executeDefaultAction = MaybeDispatchSelectstartEvent(
          *aRange,
          StaticPrefs::dom_select_events_textcontrols_selectstart_enabled(),
          doc);

      if (!executeDefaultAction) {
        return NS_OK;
      }

      // As we potentially dispatched an event to the DOM, something could have
      // changed under our feet. Re-generate the rangesToAdd array, and
      // ensure that the range we are about to add is still valid.
      if (!aRange->IsPositioned()) {
        return NS_ERROR_UNEXPECTED;
      }
    }
  }

  // Generate the ranges to add
  UserSelectRangesToAdd(aRange, rangesToAdd);
  size_t newAnchorFocusIndex =
      GetDirection() == eDirPrevious ? 0 : rangesToAdd.Length() - 1;
  for (size_t i = 0; i < rangesToAdd.Length(); ++i) {
    Maybe<size_t> index;
    // `MOZ_KnownLive` needed because of broken static analysis
    // (https://bugzilla.mozilla.org/show_bug.cgi?id=1622253#c1).
    nsresult rv = mStyledRanges.MaybeAddRangeAndTruncateOverlaps(
        MOZ_KnownLive(rangesToAdd[i]), &index);
    NS_ENSURE_SUCCESS(rv, rv);
    if (i == newAnchorFocusIndex) {
      *aOutIndex = index;
      rangesToAdd[i]->SetIsGenerated(false);
    } else {
      rangesToAdd[i]->SetIsGenerated(true);
    }
  }
  return NS_OK;
}

nsresult Selection::AddRangesForSelectableNodes(
    nsRange* aRange, Maybe<size_t>* aOutIndex,
    const DispatchSelectstartEvent aDispatchSelectstartEvent) {
  MOZ_ASSERT(aOutIndex);
  MOZ_ASSERT(aOutIndex->isNothing());

  if (!aRange) {
    return NS_ERROR_NULL_POINTER;
  }

  if (!aRange->IsPositioned()) {
    return NS_ERROR_UNEXPECTED;
  }

  MOZ_LOG(
      sSelectionLog, LogLevel::Debug,
      ("%s: selection=%p, type=%i, range=(%p, StartOffset=%u, EndOffset=%u)",
       __FUNCTION__, this, static_cast<int>(GetType()), aRange,
       aRange->StartOffset(), aRange->EndOffset()));

  if (mUserInitiated) {
    return AddRangesForUserSelectableNodes(aRange, aOutIndex,
                                           aDispatchSelectstartEvent);
  }

  return mStyledRanges.MaybeAddRangeAndTruncateOverlaps(aRange, aOutIndex);
}

nsresult Selection::StyledRanges::AddRangeAndIgnoreOverlaps(
    AbstractRange* aRange) {
  MOZ_ASSERT(aRange);
  MOZ_ASSERT(aRange->IsPositioned());
  MOZ_ASSERT(mSelection.mSelectionType == SelectionType::eHighlight);
  if (aRange->IsStaticRange() && !aRange->AsStaticRange()->IsValid()) {
    mInvalidStaticRanges.AppendElement(StyledRange(aRange));
    aRange->RegisterSelection(MOZ_KnownLive(mSelection));
    return NS_OK;
  }

  // a common case is that we have no ranges yet
  if (mRanges.Length() == 0) {
    mRanges.AppendElement(StyledRange(aRange));
    aRange->RegisterSelection(MOZ_KnownLive(mSelection));
#ifdef ACCESSIBILITY
    a11y::SelectionManager::SelectionRangeChanged(mSelection.GetType(),
                                                  *aRange);
#endif
    return NS_OK;
  }

  Maybe<size_t> maybeStartIndex, maybeEndIndex;
  nsresult rv =
      GetIndicesForInterval(aRange->GetStartContainer(), aRange->StartOffset(),
                            aRange->GetEndContainer(), aRange->EndOffset(),
                            false, maybeStartIndex, maybeEndIndex);
  NS_ENSURE_SUCCESS(rv, rv);

  size_t startIndex(0);
  if (maybeEndIndex.isNothing()) {
    // All ranges start after the given range. We can insert our range at
    // position 0.
    startIndex = 0;
  } else if (maybeStartIndex.isNothing()) {
    // All ranges end before the given range. We can insert our range at
    // the end of the array.
    startIndex = mRanges.Length();
  } else {
    startIndex = *maybeStartIndex;
  }

  mRanges.InsertElementAt(startIndex, StyledRange(aRange));
  aRange->RegisterSelection(MOZ_KnownLive(mSelection));
#ifdef ACCESSIBILITY
  a11y::SelectionManager::SelectionRangeChanged(mSelection.GetType(), *aRange);
#endif
  return NS_OK;
}

nsresult Selection::StyledRanges::MaybeAddRangeAndTruncateOverlaps(
    nsRange* aRange, Maybe<size_t>* aOutIndex) {
  MOZ_ASSERT(aRange);
  MOZ_ASSERT(aRange->IsPositioned());
  MOZ_ASSERT(aOutIndex);
  MOZ_ASSERT(aOutIndex->isNothing());

  // a common case is that we have no ranges yet
  if (mRanges.Length() == 0) {
    // XXX(Bug 1631371) Check if this should use a fallible operation as it
    // pretended earlier.
    mRanges.AppendElement(StyledRange(aRange));
    aRange->RegisterSelection(MOZ_KnownLive(mSelection));
#ifdef ACCESSIBILITY
    a11y::SelectionManager::SelectionRangeChanged(mSelection.GetType(),
                                                  *aRange);
#endif

    aOutIndex->emplace(0u);
    return NS_OK;
  }

  Maybe<size_t> maybeStartIndex, maybeEndIndex;
  nsresult rv =
      GetIndicesForInterval(aRange->GetStartContainer(), aRange->StartOffset(),
                            aRange->GetEndContainer(), aRange->EndOffset(),
                            false, maybeStartIndex, maybeEndIndex);
  NS_ENSURE_SUCCESS(rv, rv);

  size_t startIndex, endIndex;
  if (maybeEndIndex.isNothing()) {
    // All ranges start after the given range. We can insert our range at
    // position 0, knowing there are no overlaps (handled below)
    startIndex = endIndex = 0;
  } else if (maybeStartIndex.isNothing()) {
    // All ranges end before the given range. We can insert our range at
    // the end of the array, knowing there are no overlaps (handled below)
    startIndex = endIndex = mRanges.Length();
  } else {
    startIndex = *maybeStartIndex;
    endIndex = *maybeEndIndex;
  }

  // If the range is already contained in mRanges, silently
  // succeed
  const bool sameRange = HasEqualRangeBoundariesAt(*aRange, startIndex);
  if (sameRange) {
    aOutIndex->emplace(startIndex);
    return NS_OK;
  }

  // Beyond this point, we will expand the selection to cover aRange.
  // Accessibility doesn't need to know about ranges split due to overlaps. It
  // just needs a range that covers any text leaf that is impacted by the
  // change.
#ifdef ACCESSIBILITY
  a11y::SelectionManager::SelectionRangeChanged(mSelection.GetType(), *aRange);
#endif

  if (startIndex == endIndex) {
    // The new range doesn't overlap any existing ranges
    // XXX(Bug 1631371) Check if this should use a fallible operation as it
    // pretended earlier.
    mRanges.InsertElementAt(startIndex, StyledRange(aRange));
    aRange->RegisterSelection(MOZ_KnownLive(mSelection));
    aOutIndex->emplace(startIndex);
    return NS_OK;
  }

  // We now know that at least 1 existing range overlaps with the range that
  // we are trying to add. In fact, the only ranges of interest are those at
  // the two end points, startIndex and endIndex - 1 (which may point to the
  // same range) as these may partially overlap the new range. Any ranges
  // between these indices are fully overlapped by the new range, and so can be
  // removed.
  AutoTArray<StyledRange, 2> overlaps;
  overlaps.AppendElement(mRanges[startIndex]);
  if (endIndex - 1 != startIndex) {
    overlaps.AppendElement(mRanges[endIndex - 1]);
  }

  // Remove all the overlapping ranges
  for (size_t i = startIndex; i < endIndex; ++i) {
    mRanges[i].mRange->UnregisterSelection(mSelection);
  }
  mRanges.RemoveElementsAt(startIndex, endIndex - startIndex);

  AutoTArray<StyledRange, 3> temp;
  for (const size_t i : Reversed(IntegerRange(overlaps.Length()))) {
    nsresult rv = SubtractRange(overlaps[i], *aRange, &temp);
    NS_ENSURE_SUCCESS(rv, rv);
  }

  // Insert the new element into our "leftovers" array
  // `aRange` is positioned, so it has to have a start container.
  size_t insertionPoint{FindInsertionPoint(&temp, *aRange->GetStartContainer(),
                                           aRange->StartOffset(),
                                           CompareToRangeStart)};

  temp.InsertElementAt(insertionPoint, StyledRange(aRange));

  // Merge the leftovers back in to mRanges
  mRanges.InsertElementsAt(startIndex, temp);

  for (uint32_t i = 0; i < temp.Length(); ++i) {
    if (temp[i].mRange->IsDynamicRange()) {
      MOZ_KnownLive(temp[i].mRange->AsDynamicRange())
          ->RegisterSelection(MOZ_KnownLive(mSelection));
      // `MOZ_KnownLive` is required because of
      // https://bugzilla.mozilla.org/show_bug.cgi?id=1622253.
    }
  }

  aOutIndex->emplace(startIndex + insertionPoint);
  return NS_OK;
}

nsresult Selection::StyledRanges::RemoveRangeAndUnregisterSelection(
    AbstractRange& aRange) {
  // Find the range's index & remove it. We could use FindInsertionPoint to
  // get O(log n) time, but that requires many expensive DOM comparisons.
  // For even several thousand items, this is probably faster because the
  // comparisons are so fast.
  int32_t idx = -1;
  uint32_t i;
  for (i = 0; i < mRanges.Length(); i++) {
    if (mRanges[i].mRange == &aRange) {
      idx = (int32_t)i;
      break;
    }
  }
  if (idx < 0) return NS_ERROR_DOM_NOT_FOUND_ERR;

  mRanges.RemoveElementAt(idx);
  aRange.UnregisterSelection(mSelection);
#ifdef ACCESSIBILITY
  a11y::SelectionManager::SelectionRangeChanged(mSelection.GetType(), aRange);
#endif

  return NS_OK;
}
nsresult Selection::RemoveCollapsedRanges() {
  if (NeedsToLogSelectionAPI(*this)) {
    LogSelectionAPI(this, __FUNCTION__);
    LogStackForSelectionAPI();
  }

  return mStyledRanges.RemoveCollapsedRanges();
}

nsresult Selection::StyledRanges::RemoveCollapsedRanges() {
  uint32_t i = 0;
  while (i < mRanges.Length()) {
    const AbstractRange* range = mRanges[i].mRange;
    // If nsRange::mCrossShadowBoundaryRange exists, it means
    // there's a cross boundary selection, so obviously
    // we shouldn't remove this range.
    const bool collapsed =
        range->Collapsed() && !range->MayCrossShadowBoundary();
    // Cross boundary range should always be uncollapsed.
    MOZ_ASSERT_IF(
        range->MayCrossShadowBoundary(),
        !range->AsDynamicRange()->CrossShadowBoundaryRangeCollapsed());

    if (collapsed) {
      nsresult rv = RemoveRangeAndUnregisterSelection(*mRanges[i].mRange);
      NS_ENSURE_SUCCESS(rv, rv);
    } else {
      ++i;
    }
  }
  return NS_OK;
}

void Selection::Clear(nsPresContext* aPresContext) {
  RemoveAnchorFocusRange();

  mStyledRanges.UnregisterSelection();
  for (uint32_t i = 0; i < mStyledRanges.Length(); ++i) {
    SelectFrames(aPresContext, *mStyledRanges.mRanges[i].mRange, false);
  }
  mStyledRanges.Clear();

  // Reset direction so for more dependable table selection range handling
  SetDirection(eDirNext);

  // If this was an ATTENTION selection, change it back to normal now
  if (mFrameSelection && mFrameSelection->GetDisplaySelection() ==
                             nsISelectionController::SELECTION_ATTENTION) {
    mFrameSelection->SetDisplaySelection(nsISelectionController::SELECTION_ON);
  }
}

bool Selection::StyledRanges::HasEqualRangeBoundariesAt(
    const AbstractRange& aRange, size_t aRangeIndex) const {
  if (aRangeIndex < mRanges.Length()) {
    const AbstractRange* range = mRanges[aRangeIndex].mRange;
    return range->HasEqualBoundaries(aRange);
  }
  return false;
}

void Selection::GetRangesForInterval(nsINode& aBeginNode, uint32_t aBeginOffset,
                                     nsINode& aEndNode, uint32_t aEndOffset,
                                     bool aAllowAdjacent,
                                     nsTArray<RefPtr<nsRange>>& aReturn,
                                     mozilla::ErrorResult& aRv) {
  AutoTArray<nsRange*, 2> results;
  nsresult rv =
      GetDynamicRangesForIntervalArray(&aBeginNode, aBeginOffset, &aEndNode,
                                       aEndOffset, aAllowAdjacent, &results);
  if (NS_FAILED(rv)) {
    aRv.Throw(rv);
    return;
  }

  aReturn.SetLength(results.Length());
  for (size_t i = 0; i < results.Length(); ++i) {
    aReturn[i] = results[i];  // AddRefs
  }
}

nsresult Selection::GetAbstractRangesForIntervalArray(
    nsINode* aBeginNode, uint32_t aBeginOffset, nsINode* aEndNode,
    uint32_t aEndOffset, bool aAllowAdjacent,
    nsTArray<AbstractRange*>* aRanges) {
  if (NS_WARN_IF(!aBeginNode)) {
    return NS_ERROR_UNEXPECTED;
  }

  if (NS_WARN_IF(!aEndNode)) {
    return NS_ERROR_UNEXPECTED;
  }

  aRanges->Clear();
  Maybe<size_t> maybeStartIndex, maybeEndIndex;
  nsresult res = mStyledRanges.GetIndicesForInterval(
      aBeginNode, aBeginOffset, aEndNode, aEndOffset, aAllowAdjacent,
      maybeStartIndex, maybeEndIndex);
  NS_ENSURE_SUCCESS(res, res);

  if (maybeStartIndex.isNothing() || maybeEndIndex.isNothing()) {
    return NS_OK;
  }

  for (const size_t i : IntegerRange(*maybeStartIndex, *maybeEndIndex)) {
    // XXX(Bug 1631371) Check if this should use a fallible operation as it
    // pretended earlier.
    aRanges->AppendElement(mStyledRanges.mRanges[i].mRange);
  }

  return NS_OK;
}

nsresult Selection::GetDynamicRangesForIntervalArray(
    nsINode* aBeginNode, uint32_t aBeginOffset, nsINode* aEndNode,
    uint32_t aEndOffset, bool aAllowAdjacent, nsTArray<nsRange*>* aRanges) {
  MOZ_ASSERT(mSelectionType != SelectionType::eHighlight);
  AutoTArray<AbstractRange*, 2> abstractRanges;
  nsresult rv = GetAbstractRangesForIntervalArray(
      aBeginNode, aBeginOffset, aEndNode, aEndOffset, aAllowAdjacent,
      &abstractRanges);
  NS_ENSURE_SUCCESS(rv, rv);
  aRanges->Clear();
  aRanges->SetCapacity(abstractRanges.Length());
  for (auto* abstractRange : abstractRanges) {
    aRanges->AppendElement(abstractRange->AsDynamicRange());
  }
  return NS_OK;
}

void Selection::StyledRanges::ReorderRangesIfNecessary() {
  const Document* doc = mSelection.GetDocument();
  if (!doc) {
    return;
  }
  if (mRanges.Length() < 2 && mInvalidStaticRanges.IsEmpty()) {
    // There is nothing to be reordered.
    return;
  }
  const int32_t currentDocumentGeneration = doc->GetGeneration();
  const bool domMutationHasHappened =
      currentDocumentGeneration != mDocumentGeneration;
  if (domMutationHasHappened) {
    // After a DOM mutation, invalid static ranges might have become valid and
    // valid static ranges might have become invalid.
    StyledRangeArray invalidStaticRanges;
    for (StyledRangeArray::const_iterator iter = mRanges.begin();
         iter != mRanges.end();) {
      const AbstractRange* range = iter->mRange;
      if (range->IsStaticRange() && !range->AsStaticRange()->IsValid()) {
        invalidStaticRanges.AppendElement(*iter);
        iter = mRanges.RemoveElementAt(iter);
      } else {
        ++iter;
      }
    }
    for (StyledRangeArray::const_iterator iter = mInvalidStaticRanges.begin();
         iter != mInvalidStaticRanges.end();) {
      MOZ_ASSERT(iter->mRange->IsStaticRange());
      if (iter->mRange->AsStaticRange()->IsValid()) {
        mRanges.AppendElement(*iter);
        iter = mInvalidStaticRanges.RemoveElementAt(iter);
      } else {
        ++iter;
      }
    }
    mInvalidStaticRanges.AppendElements(std::move(invalidStaticRanges));
  }
  if (domMutationHasHappened || mRangesMightHaveChanged) {
    // This is hot code. Proceed with caution.
    // This path uses a cache that keep the last 100 node/index combinations
    // in a stack-allocated array to save up on expensive calls to
    // nsINode::ComputeIndexOf() (which happen in
    // nsContentUtils::ComparePoints()).
    // The second expensive call here is the sort() below, which should be
    // avoided if possible. Sorting can be avoided if the ranges are still in
    // order. Checking the order is cheap compared to sorting (also, it fills up
    // the cache, which is reused by the sort call).
    nsContentUtils::NodeIndexCache cache;
    bool rangeOrderHasChanged = false;
    const nsINode* prevStartContainer = nullptr;
    uint32_t prevStartOffset = 0;
    for (const StyledRange& range : mRanges) {
      const nsINode* startContainer = range.mRange->GetStartContainer();
      uint32_t startOffset = range.mRange->StartOffset();
      if (!prevStartContainer) {
        prevStartContainer = startContainer;
        prevStartOffset = startOffset;
        continue;
      }
      // Calling ComparePoints here saves one call of
      // AbstractRange::StartOffset() per iteration (which is surprisingly
      // expensive).
      const Maybe<int32_t> compareResult = nsContentUtils::ComparePoints(
          startContainer, startOffset, prevStartContainer, prevStartOffset,
          &cache);
      // If the nodes are in different subtrees, the Maybe is empty.
      // Since CompareToRangeStart pretends ranges to be ordered, this aligns
      // to that behavior.
      if (compareResult.valueOr(1) != 1) {
        rangeOrderHasChanged = true;
        break;
      }
      prevStartContainer = startContainer;
      prevStartOffset = startOffset;
    }
    if (rangeOrderHasChanged) {
      mRanges.Sort([&cache](const StyledRange& a, const StyledRange& ;b) -> int {
        return CompareToRangeStart(*a.mRange->GetStartContainer(),
                                   a.mRange->StartOffset(), *b.mRange, &cache);
      });
    }
    mDocumentGeneration = currentDocumentGeneration;
    mRangesMightHaveChanged = false;
  }
}

nsresult Selection::StyledRanges::GetIndicesForInterval(
    const nsINode* aBeginNode, uint32_t aBeginOffset, const nsINode* aEndNode,
    uint32_t aEndOffset, bool aAllowAdjacent, Maybe<size_t>& aStartIndex,
    Maybe<size_t>& aEndIndex) {
  MOZ_ASSERT(aStartIndex.isNothing());
  MOZ_ASSERT(aEndIndex.isNothing());

  if (NS_WARN_IF(!aBeginNode)) {
    return NS_ERROR_INVALID_POINTER;
  }

  if (NS_WARN_IF(!aEndNode)) {
    return NS_ERROR_INVALID_POINTER;
  }

  ReorderRangesIfNecessary();

  if (mRanges.Length() == 0) {
    return NS_OK;
  }

  const bool intervalIsCollapsed =
      aBeginNode == aEndNode && aBeginOffset == aEndOffset;

  // Ranges that end before the given interval and begin after the given
  // interval can be discarded
  size_t endsBeforeIndex{FindInsertionPoint(&mRanges, *aEndNode, aEndOffset,
                                            &CompareToRangeStart)};

  if (endsBeforeIndex == 0) {
    const AbstractRange* endRange = mRanges[endsBeforeIndex].mRange;

    // If the interval is strictly before the range at index 0, we can optimize
    // by returning now - all ranges start after the given interval
    if (!endRange->StartRef().Equals(aEndNode, aEndOffset)) {
      return NS_OK;
    }

    // We now know that the start point of mRanges[0].mRange
    // equals the end of the interval. Thus, when aAllowadjacent is true, the
    // caller is always interested in this range. However, when excluding
    // adjacencies, we must remember to include the range when both it and the
    // given interval are collapsed to the same point
    if (!aAllowAdjacent && !(endRange->Collapsed() && intervalIsCollapsed))
      return NS_OK;
  }
  aEndIndex.emplace(endsBeforeIndex);

  size_t beginsAfterIndex{FindInsertionPoint(&mRanges, *aBeginNode,
                                             aBeginOffset, &CompareToRangeEnd)};

  if (beginsAfterIndex == mRanges.Length()) {
    return NS_OK;  // optimization: all ranges are strictly before us
  }

  if (aAllowAdjacent) {
    // At this point, one of the following holds:
    //   endsBeforeIndex == mRanges.Length(),
    //   endsBeforeIndex points to a range whose start point does not equal the
    //     given interval's start point
    //   endsBeforeIndex points to a range whose start point equals the given
    //     interval's start point
    // In the final case, there can be two such ranges, a collapsed range, and
    // an adjacent range (they will appear in mRanges in that
    // order). For this final case, we need to increment endsBeforeIndex, until
    // one of the first two possibilities hold
    while (endsBeforeIndex < mRanges.Length()) {
      const AbstractRange* endRange = mRanges[endsBeforeIndex].mRange;
      if (!endRange->StartRef().Equals(aEndNode, aEndOffset)) {
        break;
      }
      endsBeforeIndex++;
    }

    // Likewise, one of the following holds:
    //   beginsAfterIndex == 0,
    //   beginsAfterIndex points to a range whose end point does not equal
    //     the given interval's end point
    //   beginsOnOrAfter points to a range whose end point equals the given
    //     interval's end point
    // In the final case, there can be two such ranges, an adjacent range, and
    // a collapsed range (they will appear in mRanges in that
    // order). For this final case, we only need to take action if both those
    // ranges exist, and we are pointing to the collapsed range - we need to
    // point to the adjacent range
    const AbstractRange* beginRange = mRanges[beginsAfterIndex].mRange;
    if (beginsAfterIndex > 0 && beginRange->Collapsed() &&
        beginRange->EndRef().Equals(aBeginNode, aBeginOffset)) {
      beginRange = mRanges[beginsAfterIndex - 1].mRange;
      if (beginRange->EndRef().Equals(aBeginNode, aBeginOffset)) {
        beginsAfterIndex--;
      }
    }
  } else {
    // See above for the possibilities at this point. The only case where we
    // need to take action is when the range at beginsAfterIndex ends on
    // the given interval's start point, but that range isn't collapsed (a
    // collapsed range should be included in the returned results).
    const AbstractRange* beginRange = mRanges[beginsAfterIndex].mRange;
    if (beginRange->MayCrossShadowBoundaryEndRef().Equals(aBeginNode,
                                                          aBeginOffset) &&
        !beginRange->Collapsed()) {
      beginsAfterIndex++;
    }

    // Again, see above for the meaning of endsBeforeIndex at this point.
    // In particular, endsBeforeIndex may point to a collaped range which
    // represents the point at the end of the interval - this range should be
    // included
    if (endsBeforeIndex < mRanges.Length()) {
      const AbstractRange* endRange = mRanges[endsBeforeIndex].mRange;
      if (endRange->MayCrossShadowBoundaryStartRef().Equals(aEndNode,
                                                            aEndOffset) &&
          endRange->Collapsed()) {
        endsBeforeIndex++;
      }
    }
  }

  NS_ASSERTION(beginsAfterIndex <= endsBeforeIndex, "Is mRanges not ordered?");
  NS_ENSURE_STATE(beginsAfterIndex <= endsBeforeIndex);

  aStartIndex.emplace(beginsAfterIndex);
  aEndIndex = Some(endsBeforeIndex);
  return NS_OK;
}

nsIFrame* Selection::GetPrimaryFrameForAnchorNode() const {
  MOZ_ASSERT(mSelectionType == SelectionType::eNormal);

  nsCOMPtr<nsIContent> content = do_QueryInterface(GetAnchorNode());
  if (content && mFrameSelection) {
    return SelectionMovementUtils::GetFrameForNodeOffset(
        content, AnchorOffset(), mFrameSelection->GetHint());
  }
  return nullptr;
}

PrimaryFrameData Selection::GetPrimaryFrameForCaretAtFocusNode(
    bool aVisual) const {
  nsIContent* content = nsIContent::FromNodeOrNull(GetFocusNode());
  if (!content || !mFrameSelection || !mFrameSelection->GetPresShell()) {
    return {};
  }

  MOZ_ASSERT(mFrameSelection->GetPresShell()->GetDocument() ==
             content->GetComposedDoc());

  CaretAssociationHint hint = mFrameSelection->GetHint();
  intl::BidiEmbeddingLevel caretBidiLevel =
      mFrameSelection->GetCaretBidiLevel();
  return SelectionMovementUtils::GetPrimaryFrameForCaret(
      content, FocusOffset(), aVisual, hint, caretBidiLevel);
}

void Selection::SelectFramesOf(nsIContent* aContent, bool aSelected) const {
  nsIFrame* frame = aContent->GetPrimaryFrame();
  if (!frame) {
    return;
  }
  // The frame could be an SVG text frame, in which case we don't treat it
  // as a text frame.
  if (frame->IsTextFrame()) {
    nsTextFrame* textFrame = static_cast<nsTextFrame*>(frame);
    textFrame->SelectionStateChanged(0, textFrame->TextFragment()->GetLength(),
                                     aSelected, mSelectionType);
  } else {
    frame->SelectionStateChanged();
  }
}

nsresult Selection::SelectFramesOfInclusiveDescendantsOfContent(
    PostContentIterator& aPostOrderIter, nsIContent* aContent,
    bool aSelected) const {
  // If aContent doesn't have children, we should avoid to use the content
  // iterator for performance reason.
  if (!aContent->HasChildren()) {
    SelectFramesOf(aContent, aSelected);
    return NS_OK;
  }

  if (NS_WARN_IF(NS_FAILED(aPostOrderIter.Init(aContent)))) {
    return NS_ERROR_FAILURE;
  }

  for (; !aPostOrderIter.IsDone(); aPostOrderIter.Next()) {
    nsINode* node = aPostOrderIter.GetCurrentNode();
    MOZ_ASSERT(node);
    nsIContent* innercontent = node->IsContent() ? node->AsContent() : nullptr;
    SelectFramesOf(innercontent, aSelected);
  }

  return NS_OK;
}

void Selection::SelectFramesOfShadowIncludingDescendantsOfContent(
    nsIContent* aContent, bool aSelected) const {
  MOZ_ASSERT(aContent);
  MOZ_ASSERT(StaticPrefs::dom_shadowdom_selection_across_boundary_enabled());
  for (nsINode* node : ShadowIncludingTreeIterator(*aContent)) {
    nsIContent* innercontent = node->IsContent() ? node->AsContent() : nullptr;
    SelectFramesOf(innercontent, aSelected);
  }
}

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

--> maximum size reached

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

quality93%

¤ Dauer der Verarbeitung: 0.42 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.