Quelle nsRange.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 the DOM Range object.
*/

#include "RangeBoundary.h"
#include "nscore.h"
#include "nsRange.h"

#include "nsDebug.h"
#include "nsString.h"
#include "nsReadableUtils.h"
#include "nsIContent.h"
#include "mozilla/dom/Document.h"
#include "nsError.h"
#include "nsINodeList.h"
#include "nsGkAtoms.h"
#include "nsContentUtils.h"
#include "nsFrameSelection.h"
#include "nsLayoutUtils.h"
#include "nsTextFrame.h"
#include "nsContainerFrame.h"
#include "mozilla/Assertions.h"
#include "mozilla/CheckedInt.h"
#include "mozilla/ContentIterator.h"
#include "mozilla/dom/CharacterData.h"
#include "mozilla/dom/ChildIterator.h"
#include "mozilla/dom/DOMRect.h"
#include "mozilla/dom/DOMStringList.h"
#include "mozilla/dom/DocumentFragment.h"
#include "mozilla/dom/DocumentType.h"
#include "mozilla/dom/RangeBinding.h"
#include "mozilla/dom/Selection.h"
#include "mozilla/dom/Text.h"
#include "mozilla/dom/TrustedTypeUtils.h"
#include "mozilla/dom/TrustedTypesConstants.h"
#include "mozilla/Logging.h"
#include "mozilla/Maybe.h"
#include "mozilla/PresShell.h"
#include "mozilla/RangeUtils.h"
#include "mozilla/Telemetry.h"
#include "mozilla/ToString.h"
#include "mozilla/UniquePtr.h"
#include "mozilla/Likely.h"
#include "nsCSSFrameConstructor.h"
#include "nsStyleStruct.h"
#include "nsStyleStructInlines.h"
#include "nsComputedDOMStyle.h"
#include "mozilla/dom/InspectorFontFace.h"

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

namespace mozilla {
extern LazyLogModule sSelectionAPILog;
extern void LogStackForSelectionAPI();

template <typename SPT, typename SRT, typename EPT, typename ERT>
static void LogSelectionAPI(const dom::Selection* aSelection,
                            const char* aFuncName, const char* aArgName1,
                            const RangeBoundaryBase<SPT, SRT>& aBoundary1,
                            const char* aArgName2,
                            const RangeBoundaryBase<EPT, ERT>& aBoundary2,
                            const char* aArgName3, bool aBoolArg) {
  if (aBoundary1 == aBoundary2) {
    MOZ_LOG(sSelectionAPILog, LogLevel::Info,
            ("%p nsRange::%s(%s=%s=%s, %s=%s)", aSelection, aFuncName,
             aArgName1, aArgName2, ToString(aBoundary1).c_str(), aArgName3,
             aBoolArg ? "true" : "false"));
  } else {
    MOZ_LOG(
        sSelectionAPILog, LogLevel::Info,
        ("%p nsRange::%s(%s=%s, %s=%s, %s=%s)", aSelection, aFuncName,
         aArgName1, ToString(aBoundary1).c_str(), aArgName2,
         ToString(aBoundary2).c_str(), aArgName3, aBoolArg ? "true" : "false"));
  }
}
}  // namespace mozilla

using namespace mozilla;
using namespace mozilla::dom;

template already_AddRefed<nsRange> nsRange::Create(
    const RangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary,
    ErrorResult& aRv);
template already_AddRefed<nsRange> nsRange::Create(
    const RangeBoundary& aStartBoundary, const RawRangeBoundary& aEndBoundary,
    ErrorResult& aRv);
template already_AddRefed<nsRange> nsRange::Create(
    const RawRangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary,
    ErrorResult& aRv);
template already_AddRefed<nsRange> nsRange::Create(
    const RawRangeBoundary& aStartBoundary,
    const RawRangeBoundary& aEndBoundary, ErrorResult& aRv);

template nsresult nsRange::SetStartAndEnd(const RangeBoundary& aStartBoundary,
                                          const RangeBoundary& aEndBoundary);
template nsresult nsRange::SetStartAndEnd(const RangeBoundary& aStartBoundary,
                                          const RawRangeBoundary& aEndBoundary);
template nsresult nsRange::SetStartAndEnd(
    const RawRangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary);
template nsresult nsRange::SetStartAndEnd(
    const RawRangeBoundary& aStartBoundary,
    const RawRangeBoundary& aEndBoundary);

template void nsRange::DoSetRange(const RangeBoundary& aStartBoundary,
                                  const RangeBoundary& aEndBoundary,
                                  nsINode* aRootNode, bool aNotInsertedYet,
                                  RangeBehaviour aRangeBehaviour);
template void nsRange::DoSetRange(const RangeBoundary& aStartBoundary,
                                  const RawRangeBoundary& aEndBoundary,
                                  nsINode* aRootNode, bool aNotInsertedYet,
                                  RangeBehaviour aRangeBehaviour);
template void nsRange::DoSetRange(const RawRangeBoundary& aStartBoundary,
                                  const RangeBoundary& aEndBoundary,
                                  nsINode* aRootNode, bool aNotInsertedYet,
                                  RangeBehaviour aRangeBehaviour);
template void nsRange::DoSetRange(const RawRangeBoundary& aStartBoundary,
                                  const RawRangeBoundary& aEndBoundary,
                                  nsINode* aRootNode, bool aNotInsertedYet,
                                  RangeBehaviour aRangeBehaviour);

template void nsRange::CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
    const RangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary);
template void nsRange::CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
    const RangeBoundary& aStartBoundary, const RawRangeBoundary& aEndBoundary);
template void nsRange::CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
    const RawRangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary);
template void nsRange::CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
    const RawRangeBoundary& aStartBoundary,
    const RawRangeBoundary& aEndBoundary);

JSObject* nsRange::WrapObject(JSContext* aCx,
                              JS::Handle<JSObject*> aGivenProto) {
  return Range_Binding::Wrap(aCx, this, aGivenProto);
}

DocGroup* nsRange::GetDocGroup() const {
  return mOwner ? mOwner->GetDocGroup() : nullptr;
}

/******************************************************
* stack based utility class for managing monitor
******************************************************/

static void InvalidateAllFrames(nsINode* aNode) {
  MOZ_ASSERT(aNode, "bad arg");

  nsIFrame* frame = nullptr;
  switch (aNode->NodeType()) {
    case nsINode::TEXT_NODE:
    case nsINode::ELEMENT_NODE: {
      nsIContent* content = static_cast<nsIContent*>(aNode);
      frame = content->GetPrimaryFrame();
      break;
    }
    case nsINode::DOCUMENT_NODE: {
      Document* doc = static_cast<Document*>(aNode);
      PresShell* presShell = doc ? doc->GetPresShell() : nullptr;
      frame = presShell ? presShell->GetRootFrame() : nullptr;
      break;
    }
  }
  for (nsIFrame* f = frame; f; f = f->GetNextContinuation()) {
    f->InvalidateFrameSubtree();
  }
}

/******************************************************
* constructor/destructor
******************************************************/

nsTArray<RefPtr<nsRange>>* nsRange::sCachedRanges = nullptr;

nsRange::~nsRange() {
  NS_ASSERTION(!IsInAnySelection(), "deleting nsRange that is in use");

  // we want the side effects (releases and list removals)
  DoSetRange(RawRangeBoundary(), RawRangeBoundary(), nullptr);
}

nsRange::nsRange(nsINode* aNode)
    : AbstractRange(aNode, /* aIsDynamicRange = */ true),
      mNextStartRef(nullptr),
      mNextEndRef(nullptr) {
  // printf("Size of nsRange: %zu\n", sizeof(nsRange));

  static_assert(sizeof(nsRange) <= 248,
                "nsRange size shouldn't be increased as far as possible");
}

/* static */
already_AddRefed<nsRange> nsRange::Create(nsINode* aNode) {
  MOZ_ASSERT(aNode);
  if (!sCachedRanges || sCachedRanges->IsEmpty()) {
    return do_AddRef(new nsRange(aNode));
  }
  RefPtr<nsRange> range = sCachedRanges->PopLastElement().forget();
  range->Init(aNode);
  return range.forget();
}

/* static */
template <typename SPT, typename SRT, typename EPT, typename ERT>
already_AddRefed<nsRange> nsRange::Create(
    const RangeBoundaryBase<SPT, SRT>& aStartBoundary,
    const RangeBoundaryBase<EPT, ERT>& aEndBoundary, ErrorResult& aRv) {
  // If we fail to initialize the range a lot, nsRange should have a static
  // initializer since the allocation cost is not cheap in hot path.
  RefPtr<nsRange> range = nsRange::Create(aStartBoundary.Container());
  aRv = range->SetStartAndEnd(aStartBoundary, aEndBoundary);
  if (NS_WARN_IF(aRv.Failed())) {
    return nullptr;
  }
  return range.forget();
}

/*
* When a new boundary is given to a nsRange, compare its position with other
* existing boundaries to see if we need to collapse the end points.
*
* aRange: The nsRange that aNewBoundary is being set to.
* aNewRoot: The shadow-including root of the container of aNewBoundary
* aNewBoundary: The new boundary
* aIsSetStart: true if GetRangeBehaviour is called by nsRange::SetStart,
* false otherwise
* aAllowCrossShadowBoundary: Indicates whether the boundaries allowed to cross
* shadow boundary or not
*/
static RangeBehaviour GetRangeBehaviour(
    const nsRange* aRange, const nsINode* aNewRoot,
    const RawRangeBoundary& aNewBoundary, const bool aIsSetStart,
    AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
  if (!aRange->IsPositioned()) {
    return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
  }

  MOZ_ASSERT(aRange->GetRoot());

  if (aNewRoot != aRange->GetRoot()) {
    // Boundaries are in different document (or not connected), so collapse
    // the both the default range and the crossBoundaryRange range.
    if (aNewRoot->GetComposedDoc() != aRange->GetRoot()->GetComposedDoc()) {
      return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
    }

    // Always collapse both ranges if the one of the roots is an UA widget
    // regardless whether the boundaries are allowed to cross shadow boundary
    // or not.
    if (AbstractRange::IsRootUAWidget(aNewRoot) ||
        AbstractRange::IsRootUAWidget(aRange->GetRoot())) {
      return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
    }

    if (const CrossShadowBoundaryRange* crossShadowBoundaryRange =
            aRange->GetCrossShadowBoundaryRange()) {
      // Check if the existing-other-side boundary in
      // aRange::mCrossShadowBoundaryRange has the same root
      // as aNewRoot. If this is the case, it means default range
      // is good enough to represent this range, so that we can
      // merge the cross-shadow-boundary range and the default range.
      const RangeBoundary& otherSideExistingBoundary =
          aIsSetStart ? crossShadowBoundaryRange->EndRef()
                      : crossShadowBoundaryRange->StartRef();
      const nsINode* otherSideRoot =
          RangeUtils::ComputeRootNode(otherSideExistingBoundary.Container());
      if (aNewRoot == otherSideRoot) {
        return RangeBehaviour::MergeDefaultRangeAndCrossShadowBoundaryRanges;
      }
    }

    // Different root, but same document. So we only collapse the
    // default range if boundaries are allowed to cross shadow boundary.
    return aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes
               ? RangeBehaviour::CollapseDefaultRange
               : RangeBehaviour::
                     CollapseDefaultRangeAndCrossShadowBoundaryRanges;
  }

  const RangeBoundary& otherSideExistingBoundary =
      aIsSetStart ? aRange->EndRef() : aRange->StartRef();

  // Both bondaries are in the same root, now check for their position
  const Maybe<int32_t> order =
      aIsSetStart ? nsContentUtils::ComparePoints(aNewBoundary,
                                                  otherSideExistingBoundary)
                  : nsContentUtils::ComparePoints(otherSideExistingBoundary,
                                                  aNewBoundary);

  if (order) {
    if (*order != 1) {
      // aNewBoundary is at a valid position.
      //
      // If aIsSetStart is true, this means
      // aNewBoundary <= otherSideExistingBoundary which is
      // good because aNewBoundary intends to be the start.
      //
      // If aIsSetStart is false, this means
      // otherSideExistingBoundary <= aNewBoundary which is good because
      // aNewBoundary intends to be the end.
      //
      // So no collapse for above cases.
      return RangeBehaviour::KeepDefaultRangeAndCrossShadowBoundaryRanges;
    }

    if (!aRange->MayCrossShadowBoundary() ||
        aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::No) {
      return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
    }

    const RangeBoundary& otherSideExistingCrossShadowBoundaryBoundary =
        aIsSetStart ? aRange->MayCrossShadowBoundaryEndRef()
                    : aRange->MayCrossShadowBoundaryStartRef();

    // Please see the comment for (*order != 1) to see what "valid" means.
    //
    // We reach to this line when (*order == 1), it means aNewBoundary is
    // at an invalid position, so we need to collapse aNewBoundary with
    // otherSideExistingBoundary. However, it's possible that aNewBoundary
    // is valid with the otherSideExistingCrossShadowBoundaryBoundary.
    const Maybe<int32_t> withCrossShadowBoundaryOrder =
        aIsSetStart
            ? nsContentUtils::ComparePoints(
                  aNewBoundary, otherSideExistingCrossShadowBoundaryBoundary)
            : nsContentUtils::ComparePoints(
                  otherSideExistingCrossShadowBoundaryBoundary, aNewBoundary);

    // Valid to the cross boundary boundary.
    if (withCrossShadowBoundaryOrder && *withCrossShadowBoundaryOrder != 1) {
      return RangeBehaviour::CollapseDefaultRange;
    }

    // Not valid to both existing boundaries.
    return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
  }

  MOZ_ASSERT_UNREACHABLE();
  return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
}
/******************************************************
* nsISupports
******************************************************/

NS_IMPL_CYCLE_COLLECTING_ADDREF(nsRange)
NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_INTERRUPTABLE_LAST_RELEASE(
    nsRange, DoSetRange(RawRangeBoundary(), RawRangeBoundary(), nullptr),
    MaybeInterruptLastRelease())

// QueryInterface implementation for nsRange
NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsRange)
  NS_INTERFACE_MAP_ENTRY(nsIMutationObserver)
NS_INTERFACE_MAP_END_INHERITING(AbstractRange)

NS_IMPL_CYCLE_COLLECTION_CLASS(nsRange)

NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN_INHERITED(nsRange, AbstractRange)
  // `Reset()` unlinks `mStart`, `mEnd` and `mRoot`.
  NS_IMPL_CYCLE_COLLECTION_UNLINK(mCrossShadowBoundaryRange);
  tmp->Reset();
NS_IMPL_CYCLE_COLLECTION_UNLINK_END

NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN_INHERITED(nsRange, AbstractRange)
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mRoot)
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mCrossShadowBoundaryRange);
NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END

NS_IMPL_CYCLE_COLLECTION_TRACE_BEGIN_INHERITED(nsRange, AbstractRange)
NS_IMPL_CYCLE_COLLECTION_TRACE_END

bool nsRange::MaybeInterruptLastRelease() {
  bool interrupt = AbstractRange::MaybeCacheToReuse(*this);
  ResetCrossShadowBoundaryRange();
  MOZ_ASSERT(!interrupt || IsCleared());
  return interrupt;
}

void nsRange::AdjustNextRefsOnCharacterDataSplit(
    const nsIContent& aContent, const CharacterDataChangeInfo& aInfo) {
  // If the splitted text node is immediately before a range boundary point
  // that refers to a child index (i.e. its parent is the boundary container)
  // then we need to adjust the corresponding boundary to account for the new
  // text node that will be inserted. However, because the new sibling hasn't
  // been inserted yet, that would result in an invalid boundary. Therefore,
  // we store the new child in mNext*Ref to make sure we adjust the boundary
  // in the next ContentInserted or ContentAppended call.
  nsINode* parentNode = aContent.GetParentNode();
  if (parentNode == mEnd.Container()) {
    if (&aContent == mEnd.Ref()) {
      MOZ_ASSERT(aInfo.mDetails->mNextSibling);
      mNextEndRef = aInfo.mDetails->mNextSibling;
    }
  }

  if (parentNode == mStart.Container()) {
    if (&aContent == mStart.Ref()) {
      MOZ_ASSERT(aInfo.mDetails->mNextSibling);
      mNextStartRef = aInfo.mDetails->mNextSibling;
    }
  }
}

nsRange::RangeBoundariesAndRoot
nsRange::DetermineNewRangeBoundariesAndRootOnCharacterDataMerge(
    nsIContent* aContent, const CharacterDataChangeInfo& aInfo) const {
  RawRangeBoundary newStart;
  RawRangeBoundary newEnd;
  nsINode* newRoot = nullptr;

  // normalize(), aInfo.mDetails->mNextSibling is the merged text node
  // that will be removed
  nsIContent* removed = aInfo.mDetails->mNextSibling;
  if (removed == mStart.Container()) {
    CheckedUint32 newStartOffset{
        *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets)};
    newStartOffset += aInfo.mChangeStart;

    // newStartOffset.isValid() isn't checked explicitly here, because
    // newStartOffset.value() contains an assertion.
    newStart = {aContent, newStartOffset.value()};
    if (MOZ_UNLIKELY(removed == mRoot)) {
      newRoot = RangeUtils::ComputeRootNode(newStart.Container());
    }
  }
  if (removed == mEnd.Container()) {
    CheckedUint32 newEndOffset{
        *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets)};
    newEndOffset += aInfo.mChangeStart;

    // newEndOffset.isValid() isn't checked explicitly here, because
    // newEndOffset.value() contains an assertion.
    newEnd = {aContent, newEndOffset.value()};
    if (MOZ_UNLIKELY(removed == mRoot)) {
      newRoot = {RangeUtils::ComputeRootNode(newEnd.Container())};
    }
  }
  // When the removed text node's parent is one of our boundary nodes we may
  // need to adjust the offset to account for the removed node. However,
  // there will also be a ContentRemoved notification later so the only cases
  // we need to handle here is when the removed node is the text node after
  // the boundary.  (The m*Offset > 0 check is an optimization - a boundary
  // point before the first child is never affected by normalize().)
  nsINode* parentNode = aContent->GetParentNode();
  if (parentNode == mStart.Container() &&
      *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) > 0 &&
      *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) <
          parentNode->GetChildCount() &&
      removed == mStart.GetChildAtOffset()) {
    newStart = {aContent, aInfo.mChangeStart};
  }
  if (parentNode == mEnd.Container() &&
      *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) > 0 &&
      *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) <
          parentNode->GetChildCount() &&
      removed == mEnd.GetChildAtOffset()) {
    newEnd = {aContent, aInfo.mChangeEnd};
  }

  return {newStart, newEnd, newRoot};
}

/******************************************************
* nsIMutationObserver implementation
******************************************************/
void nsRange::CharacterDataChanged(nsIContent* aContent,
                                   const CharacterDataChangeInfo& aInfo) {
  MOZ_ASSERT(aContent);
  MOZ_ASSERT(mIsPositioned);
  MOZ_ASSERT(!mNextEndRef);
  MOZ_ASSERT(!mNextStartRef);

  nsINode* newRoot = nullptr;
  RawRangeBoundary newStart;
  RawRangeBoundary newEnd;

  if (aInfo.mDetails &&
      aInfo.mDetails->mType == CharacterDataChangeInfo::Details::eSplit) {
    AdjustNextRefsOnCharacterDataSplit(*aContent, aInfo);
  }

  // If the changed node contains our start boundary and the change starts
  // before the boundary we'll need to adjust the offset.
  if (aContent == mStart.Container() &&
      aInfo.mChangeStart <
          *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets)) {
    if (aInfo.mDetails) {
      // splitText(), aInfo->mDetails->mNextSibling is the new text node
      NS_ASSERTION(
          aInfo.mDetails->mType == CharacterDataChangeInfo::Details::eSplit,
          "only a split can start before the end");
      NS_ASSERTION(
          *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) <=
              aInfo.mChangeEnd + 1,
          "mStart.Offset() is beyond the end of this node");
      const uint32_t newStartOffset =
          *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) -
          aInfo.mChangeStart;
      newStart = {aInfo.mDetails->mNextSibling, newStartOffset};
      if (MOZ_UNLIKELY(aContent == mRoot)) {
        newRoot = RangeUtils::ComputeRootNode(newStart.Container());
      }

      bool isCommonAncestor =
          IsInAnySelection() && mStart.Container() == mEnd.Container();
      if (isCommonAncestor) {
        MOZ_DIAGNOSTIC_ASSERT(mStart.Container() ==
                              mRegisteredClosestCommonInclusiveAncestor);
        UnregisterClosestCommonInclusiveAncestor();
        RegisterClosestCommonInclusiveAncestor(newStart.Container());
      }
      if (mStart.Container()
              ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
        newStart.Container()
            ->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
      }
    } else {
      newStart = ComputeNewBoundaryWhenBoundaryInsideChangedText(
          aInfo, mStart.AsRaw());
    }
  }

  // Do the same thing for the end boundary, except for splitText of a node
  // with no parent then only switch to the new node if the start boundary
  // did so too (otherwise the range would end up with disconnected nodes).
  if (aContent == mEnd.Container() &&
      aInfo.mChangeStart <
          *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets)) {
    if (aInfo.mDetails && (aContent->GetParentNode() || newStart.Container())) {
      // splitText(), aInfo.mDetails->mNextSibling is the new text node
      NS_ASSERTION(
          aInfo.mDetails->mType == CharacterDataChangeInfo::Details::eSplit,
          "only a split can start before the end");
      MOZ_ASSERT(
          *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) <=
              aInfo.mChangeEnd + 1,
          "mEnd.Offset() is beyond the end of this node");

      const uint32_t newEndOffset{
          *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) -
          aInfo.mChangeStart};
      newEnd = {aInfo.mDetails->mNextSibling, newEndOffset};

      bool isCommonAncestor =
          IsInAnySelection() && mStart.Container() == mEnd.Container();
      if (isCommonAncestor && !newStart.Container()) {
        MOZ_DIAGNOSTIC_ASSERT(mStart.Container() ==
                              mRegisteredClosestCommonInclusiveAncestor);
        // The split occurs inside the range.
        UnregisterClosestCommonInclusiveAncestor();
        RegisterClosestCommonInclusiveAncestor(
            mStart.Container()->GetParentNode());
        newEnd.Container()
            ->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
      } else if (
          mEnd.Container()
              ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
        newEnd.Container()
            ->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
      }
    } else {
      newEnd =
          ComputeNewBoundaryWhenBoundaryInsideChangedText(aInfo, mEnd.AsRaw());
    }
  }

  if (aInfo.mDetails &&
      aInfo.mDetails->mType == CharacterDataChangeInfo::Details::eMerge) {
    MOZ_ASSERT(!newStart.IsSet());
    MOZ_ASSERT(!newEnd.IsSet());

    RangeBoundariesAndRoot rangeBoundariesAndRoot =
        DetermineNewRangeBoundariesAndRootOnCharacterDataMerge(aContent, aInfo);

    newStart = rangeBoundariesAndRoot.mStart;
    newEnd = rangeBoundariesAndRoot.mEnd;
    newRoot = rangeBoundariesAndRoot.mRoot;
  }

  if (newStart.IsSet() || newEnd.IsSet()) {
    if (!newStart.IsSet()) {
      newStart.CopyFrom(mStart, RangeBoundaryIsMutationObserved::Yes);
    }
    if (!newEnd.IsSet()) {
      newEnd.CopyFrom(mEnd, RangeBoundaryIsMutationObserved::Yes);
    }
    DoSetRange(newStart, newEnd, newRoot ? newRoot : mRoot.get(),
               !newEnd.Container()->GetParentNode() ||
                   !newStart.Container()->GetParentNode());
  } else {
    nsRange::AssertIfMismatchRootAndRangeBoundaries(
        mStart, mEnd, mRoot,
        (mStart.IsSet() && !mStart.Container()->GetParentNode()) ||
            (mEnd.IsSet() && !mEnd.Container()->GetParentNode()));
  }
}

void nsRange::ContentAppended(nsIContent* aFirstNewContent) {
  MOZ_ASSERT(mIsPositioned);

  nsINode* container = aFirstNewContent->GetParentNode();
  MOZ_ASSERT(container);
  if (container->IsMaybeSelected() && IsInAnySelection()) {
    nsINode* child = aFirstNewContent;
    while (child) {
      if (!child
               ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
        MarkDescendants(*child);
        child
            ->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
      }
      child = child->GetNextSibling();
    }
  }

  if (mNextStartRef || mNextEndRef) {
    // A splitText has occurred, if any mNext*Ref was set, we need to adjust
    // the range boundaries.
    if (mNextStartRef) {
      mStart = {mStart.Container(), mNextStartRef};
      MOZ_ASSERT(mNextStartRef == aFirstNewContent);
      mNextStartRef = nullptr;
    }
    if (mNextEndRef) {
      mEnd = {mEnd.Container(), mNextEndRef};
      MOZ_ASSERT(mNextEndRef == aFirstNewContent);
      mNextEndRef = nullptr;
    }
    DoSetRange(mStart, mEnd, mRoot, true);
  } else {
    nsRange::AssertIfMismatchRootAndRangeBoundaries(mStart, mEnd, mRoot);
  }
}

void nsRange::ContentInserted(nsIContent* aChild) {
  MOZ_ASSERT(mIsPositioned);

  bool updateBoundaries = false;
  nsINode* container = aChild->GetParentNode();
  MOZ_ASSERT(container);
  RawRangeBoundary newStart(mStart, RangeBoundaryIsMutationObserved::Yes);
  RawRangeBoundary newEnd(mEnd, RangeBoundaryIsMutationObserved::Yes);
  MOZ_ASSERT(aChild->GetParentNode() == container);

  // Invalidate boundary offsets if a child that may have moved them was
  // inserted.
  if (container == mStart.Container()) {
    newStart.InvalidateOffset();
    updateBoundaries = true;
  }

  if (container == mEnd.Container()) {
    newEnd.InvalidateOffset();
    updateBoundaries = true;
  }

  if (container->IsMaybeSelected() &&
      !aChild
           ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
    MarkDescendants(*aChild);
    aChild->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
  }

  if (mNextStartRef || mNextEndRef) {
    if (mNextStartRef) {
      newStart = {mStart.Container(), mNextStartRef};
      MOZ_ASSERT(mNextStartRef == aChild);
      mNextStartRef = nullptr;
    }
    if (mNextEndRef) {
      newEnd = {mEnd.Container(), mNextEndRef};
      MOZ_ASSERT(mNextEndRef == aChild);
      mNextEndRef = nullptr;
    }

    updateBoundaries = true;
  }

  if (updateBoundaries) {
    DoSetRange(newStart, newEnd, mRoot);
  } else {
    nsRange::AssertIfMismatchRootAndRangeBoundaries(mStart, mEnd, mRoot);
  }
}

void nsRange::ContentWillBeRemoved(nsIContent* aChild,
                                   const BatchRemovalState*) {
  MOZ_ASSERT(mIsPositioned);

  nsINode* container = aChild->GetParentNode();
  MOZ_ASSERT(container);

  nsINode* startContainer = mStart.Container();
  nsINode* endContainer = mEnd.Container();

  RawRangeBoundary newStart;
  RawRangeBoundary newEnd;
  Maybe<bool> gravitateStart;
  bool gravitateEnd;

  // Adjust position if a sibling was removed...
  if (container == startContainer) {
    // We're only interested if our boundary reference was removed, otherwise
    // we can just invalidate the offset.
    if (aChild == mStart.Ref()) {
      newStart = {container, aChild->GetPreviousSibling()};
    } else {
      newStart.CopyFrom(mStart, RangeBoundaryIsMutationObserved::Yes);
      newStart.InvalidateOffset();
    }
  } else {
    gravitateStart = Some(startContainer->IsInclusiveDescendantOf(aChild));
    if (gravitateStart.value()) {
      newStart = {container, aChild->GetPreviousSibling()};
    }
  }

  // Do same thing for end boundry.
  if (container == endContainer) {
    if (aChild == mEnd.Ref()) {
      newEnd = {container, aChild->GetPreviousSibling()};
    } else {
      newEnd.CopyFrom(mEnd, RangeBoundaryIsMutationObserved::Yes);
      newEnd.InvalidateOffset();
    }
  } else {
    if (startContainer == endContainer && gravitateStart.isSome()) {
      gravitateEnd = gravitateStart.value();
    } else {
      gravitateEnd = endContainer->IsInclusiveDescendantOf(aChild);
    }
    if (gravitateEnd) {
      newEnd = {container, aChild->GetPreviousSibling()};
    }
  }

  bool newStartIsSet = newStart.IsSet();
  bool newEndIsSet = newEnd.IsSet();
  if (newStartIsSet || newEndIsSet) {
    DoSetRange(
        newStartIsSet ? newStart : mStart.AsRaw(),
        newEndIsSet ? newEnd : mEnd.AsRaw(), mRoot, false,
        // CrossShadowBoundaryRange mutates content
        // removal fot itself, so no need for nsRange to do anything with it.
        RangeBehaviour::KeepDefaultRangeAndCrossShadowBoundaryRanges);
  } else {
    nsRange::AssertIfMismatchRootAndRangeBoundaries(mStart, mEnd, mRoot);
  }

  MOZ_ASSERT(mStart.Ref() != aChild);
  MOZ_ASSERT(mEnd.Ref() != aChild);

  if (container->IsMaybeSelected() &&
      aChild
          ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
    aChild
        ->ClearDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
    UnmarkDescendants(*aChild);
  }
}

void nsRange::ParentChainChanged(nsIContent* aContent) {
  NS_ASSERTION(mRoot == aContent, "Wrong ParentChainChanged notification?");
  nsINode* newRoot = RangeUtils::ComputeRootNode(mStart.Container());
  NS_ASSERTION(newRoot, "No valid boundary or root found!");
  if (newRoot != RangeUtils::ComputeRootNode(mEnd.Container())) {
    // Sometimes ordering involved in cycle collection can lead to our
    // start parent and/or end parent being disconnected from our root
    // without our getting a ContentRemoved notification.
    // See bug 846096 for more details.
    NS_ASSERTION(mEnd.Container()->IsInNativeAnonymousSubtree(),
                 "This special case should happen only with "
                 "native-anonymous content");
    // When that happens, bail out and set pointers to null; since we're
    // in cycle collection and unreachable it shouldn't matter.
    Reset();
    return;
  }
  // This is safe without holding a strong ref to self as long as the change
  // of mRoot is the last thing in DoSetRange.
  DoSetRange(mStart, mEnd, newRoot);
}

bool nsRange::IsShadowIncludingInclusiveDescendantOfCrossBoundaryRangeAncestor(
    const nsINode& aContainer) const {
  MOZ_ASSERT(mCrossShadowBoundaryRange &&
             mCrossShadowBoundaryRange->GetCommonAncestor());
  return aContainer.IsShadowIncludingInclusiveDescendantOf(
      mCrossShadowBoundaryRange->GetCommonAncestor());
}

bool nsRange::IsPointComparableToRange(const nsINode& aContainer,
                                       uint32_t aOffset,
                                       bool aAllowCrossShadowBoundary,
                                       ErrorResult& aRv) const {
  // our range is in a good state?
  if (!mIsPositioned) {
    aRv.Throw(NS_ERROR_NOT_INITIALIZED);
    return false;
  }

  const bool isContainerInRange =
      aContainer.IsInclusiveDescendantOf(mRoot) ||
      (aAllowCrossShadowBoundary && mCrossShadowBoundaryRange &&
       IsShadowIncludingInclusiveDescendantOfCrossBoundaryRangeAncestor(
           aContainer));

  if (!isContainerInRange) {
    // TODO(emilio): Switch to ThrowWrongDocumentError, but IsPointInRange
    // relies on the error code right now in order to suppress the exception.
    aRv.Throw(NS_ERROR_DOM_WRONG_DOCUMENT_ERR);
    return false;
  }

  auto chromeOnlyAccess = mStart.Container()->ChromeOnlyAccess();
  NS_ASSERTION(chromeOnlyAccess == mEnd.Container()->ChromeOnlyAccess(),
               "Start and end of a range must be either both native anonymous "
               "content or not.");
  if (aContainer.ChromeOnlyAccess() != chromeOnlyAccess) {
    aRv.ThrowInvalidNodeTypeError(
        "Trying to compare restricted with unrestricted nodes");
    return false;
  }

  if (aContainer.NodeType() == nsINode::DOCUMENT_TYPE_NODE) {
    aRv.ThrowInvalidNodeTypeError("Trying to compare with a document");
    return false;
  }

  if (aOffset > aContainer.Length()) {
    aRv.ThrowIndexSizeError("Offset is out of bounds");
    return false;
  }

  return true;
}

bool nsRange::IsPointInRange(const nsINode& aContainer, uint32_t aOffset,
                             ErrorResult& aRv,
                             bool aAllowCrossShadowBoundary) const {
  int16_t compareResult =
      ComparePoint(aContainer, aOffset, aRv, aAllowCrossShadowBoundary);
  // If the node isn't in the range's document, it clearly isn't in the range.
  if (aRv.ErrorCodeIs(NS_ERROR_DOM_WRONG_DOCUMENT_ERR)) {
    aRv.SuppressException();
    return false;
  }

  return compareResult == 0;
}

int16_t nsRange::ComparePoint(const nsINode& aContainer, uint32_t aOffset,
                              ErrorResult& aRv,
                              bool aAllowCrossShadowBoundary) const {
  if (!IsPointComparableToRange(aContainer, aOffset, aAllowCrossShadowBoundary,
                                aRv)) {
    return 0;
  }

  const RawRangeBoundary point{const_cast<nsINode*>(&aContainer), aOffset};

  MOZ_ASSERT(point.IsSetAndValid());

  if (Maybe<int32_t> order = nsContentUtils::ComparePoints(
          point, aAllowCrossShadowBoundary ? MayCrossShadowBoundaryStartRef()
                                           : StartRef());
      order && *order <= 0) {
    return int16_t(*order);
  }
  if (Maybe<int32_t> order = nsContentUtils::ComparePoints(
          aAllowCrossShadowBoundary ? MayCrossShadowBoundaryEndRef() : EndRef(),
          point);
      order && *order == -1) {
    return 1;
  }
  return 0;
}

bool nsRange::IntersectsNode(nsINode& aNode, ErrorResult& aRv) {
  if (!mIsPositioned) {
    aRv.Throw(NS_ERROR_NOT_INITIALIZED);
    return false;
  }

  nsINode* parent = aNode.GetParentNode();
  if (!parent) {
    // |parent| is null, so |node|'s root is |node| itself.
    return GetRoot() == &aNode;
  }

  const Maybe<uint32_t> nodeIndex = parent->ComputeIndexOf(&aNode);
  if (nodeIndex.isNothing()) {
    return false;
  }

  if (!IsPointComparableToRange(*parent, *nodeIndex,
                                false /* aAllowCrossShadowBoundary */,
                                IgnoreErrors())) {
    return false;
  }

  const Maybe<int32_t> startOrder = nsContentUtils::ComparePoints(
      mStart.Container(),
      *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets), parent,
      *nodeIndex + 1u);
  if (startOrder && (*startOrder < 0)) {
    const Maybe<int32_t> endOrder = nsContentUtils::ComparePoints(
        parent, *nodeIndex, mEnd.Container(),
        *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets));
    return endOrder && (*endOrder < 0);
  }

  return false;
}

void nsRange::NotifySelectionListenersAfterRangeSet() {
  if (mSelections.IsEmpty()) {
    return;
  }

  // Our internal code should not move focus with using this instance while
  // it's calling Selection::NotifySelectionListeners() which may move focus
  // or calls selection listeners.  So, let's set mCalledByJS to false here
  // since non-*JS() methods don't set it to false.
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = false;

  // If this instance is not a proper range for selection, we need to remove
  // this from selections.
  const Document* const docForSelf =
      mStart.Container() ? mStart.Container()->GetComposedDoc() : nullptr;
  const nsFrameSelection* const frameSelection =
      mSelections[0]->GetFrameSelection();
  const Document* const docForSelection =
      frameSelection && frameSelection->GetPresShell()
          ? frameSelection->GetPresShell()->GetDocument()
          : nullptr;
  if (!IsPositioned() || docForSelf != docForSelection) {
    // XXX Why Selection::RemoveRangeAndUnselectFramesAndNotifyListeners() does
    // not set whether the caller is JS or not?
    if (IsPartOfOneSelectionOnly()) {
      RefPtr<Selection> selection = mSelections[0].get();
      selection->RemoveRangeAndUnselectFramesAndNotifyListeners(*this,
                                                                IgnoreErrors());
    } else {
      nsTArray<WeakPtr<Selection>> copiedSelections = mSelections.Clone();
      for (const auto& weakSelection : copiedSelections) {
        RefPtr<Selection> selection = weakSelection.get();
        if (MOZ_LIKELY(selection)) {
          selection->RemoveRangeAndUnselectFramesAndNotifyListeners(
              *this, IgnoreErrors());
        }
      }
    }
    // FYI: NotifySelectionListeners() should be called by
    // RemoveRangeAndUnselectFramesAndNotifyListeners() if it's required.
    // Therefore, we need to do nothing anymore.
    return;
  }

  // Notify all Selections. This may modify the range,
  // remove it from the selection, or the selection itself may have gone after
  // the call. Also, new selections may be added.
  // To ensure that listeners are notified for all *current* selections,
  // create a copy of the list of selections and use that for iterating. This
  // way selections can be added or removed safely during iteration.
  // To save allocation cost, the copy is only created if there is more than
  // one Selection present  (which will barely ever be the case).
  if (IsPartOfOneSelectionOnly()) {
    RefPtr<Selection> selection = mSelections[0].get();
#ifdef ACCESSIBILITY
    a11y::SelectionManager::SelectionRangeChanged(selection->GetType(), *this);
#endif
    selection->NotifySelectionListeners(calledByJSRestorer.SavedValue());
  } else {
    nsTArray<WeakPtr<Selection>> copiedSelections = mSelections.Clone();
    for (const auto& weakSelection : copiedSelections) {
      RefPtr<Selection> selection = weakSelection.get();
      if (MOZ_LIKELY(selection)) {
#ifdef ACCESSIBILITY
        a11y::SelectionManager::SelectionRangeChanged(selection->GetType(),
                                                      *this);
#endif
        selection->NotifySelectionListeners(calledByJSRestorer.SavedValue());
      }
    }
  }
}

/******************************************************
* Private helper routines
******************************************************/

// static
template <typename SPT, typename SRT, typename EPT, typename ERT>
void nsRange::AssertIfMismatchRootAndRangeBoundaries(
    const RangeBoundaryBase<SPT, SRT>& aStartBoundary,
    const RangeBoundaryBase<EPT, ERT>& aEndBoundary, const nsINode* aRootNode,
    bool aNotInsertedYet /* = false */) {
#ifdef DEBUG
  if (!aRootNode) {
    MOZ_ASSERT(!aStartBoundary.IsSet());
    MOZ_ASSERT(!aEndBoundary.IsSet());
    return;
  }

  MOZ_ASSERT(aStartBoundary.IsSet());
  MOZ_ASSERT(aEndBoundary.IsSet());
  if (!aNotInsertedYet) {
    // Compute temporary root for given range boundaries.  If a range in native
    // anonymous subtree is being removed, tempRoot may return the fragment's
    // root content, but it shouldn't be used for new root node because the node
    // may be bound to the root element again.
    nsINode* tempRoot = RangeUtils::ComputeRootNode(aStartBoundary.Container());
    // The new range should be in the temporary root node at least.
    MOZ_ASSERT(tempRoot ==
               RangeUtils::ComputeRootNode(aEndBoundary.Container()));
    MOZ_ASSERT(aStartBoundary.Container()->IsInclusiveDescendantOf(tempRoot));
    MOZ_ASSERT(aEndBoundary.Container()->IsInclusiveDescendantOf(tempRoot));
    // If the new range is not disconnected or not in native anonymous subtree,
    // the temporary root must be same as the new root node.  Otherwise,
    // aRootNode should be the parent of root of the NAC (e.g., `<input>` if the
    // range is in NAC under `<input>`), but tempRoot is now root content node
    // of the disconnected subtree (e.g., `<div>` element in `<input>` element).
    const bool tempRootIsDisconnectedNAC =
        tempRoot->IsInNativeAnonymousSubtree() && !tempRoot->GetParentNode();
    MOZ_ASSERT_IF(!tempRootIsDisconnectedNAC, tempRoot == aRootNode);
  }
  MOZ_ASSERT(aRootNode->IsDocument() || aRootNode->IsAttr() ||
             aRootNode->IsDocumentFragment() || aRootNode->IsContent());
#endif  // #ifdef DEBUG
}

// It's important that all setting of the range start/end points
// go through this function, which will do all the right voodoo
// for content notification of range ownership.
// Calling DoSetRange with either parent argument null will collapse
// the range to have both endpoints point to the other node
template <typename SPT, typename SRT, typename EPT, typename ERT>
void nsRange::
    DoSetRange(const RangeBoundaryBase<SPT, SRT>& aStartBoundary,
               const RangeBoundaryBase<EPT, ERT>& aEndBoundary,
               nsINode* aRootNode,
               bool aNotInsertedYet /* = false */, RangeBehaviour aRangeBehaviour /* = CollapseDefaultRangeAndCrossShadowBoundaryRanges */) {
  mIsPositioned = aStartBoundary.IsSetAndValid() &&
                  aEndBoundary.IsSetAndValid() && aRootNode;
  MOZ_ASSERT_IF(!mIsPositioned, !aStartBoundary.IsSet());
  MOZ_ASSERT_IF(!mIsPositioned, !aEndBoundary.IsSet());
  MOZ_ASSERT_IF(!mIsPositioned, !aRootNode);

  nsRange::AssertIfMismatchRootAndRangeBoundaries(aStartBoundary, aEndBoundary,
                                                  aRootNode, aNotInsertedYet);

  if (mRoot != aRootNode) {
    if (mRoot) {
      mRoot->RemoveMutationObserver(this);
    }
    if (aRootNode) {
      aRootNode->AddMutationObserver(this);
    }
  }
  bool checkCommonAncestor =
      (mStart.Container() != aStartBoundary.Container() ||
       mEnd.Container() != aEndBoundary.Container()) &&
      IsInAnySelection() && !aNotInsertedYet;

  // GetClosestCommonInclusiveAncestor is unreliable while we're unlinking
  // (could return null if our start/end have already been unlinked), so make
  // sure to not use it here to determine our "old" current ancestor.
  mStart.CopyFrom(aStartBoundary, RangeBoundaryIsMutationObserved::Yes);
  mEnd.CopyFrom(aEndBoundary, RangeBoundaryIsMutationObserved::Yes);

  if (aRangeBehaviour ==
      RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges) {
    ResetCrossShadowBoundaryRange();
  }

  if (checkCommonAncestor) {
    UpdateCommonAncestorIfNecessary();
  }

  // This needs to be the last thing this function does, other than notifying
  // selection listeners. See comment in ParentChainChanged.
  if (mRoot != aRootNode) {
    mRoot = aRootNode;
  }

  // Notify any selection listeners. This has to occur last because otherwise
  // the world could be observed by a selection listener while the range was in
  // an invalid state. So we run it off of a script runner to ensure it runs
  // after the mutation observers have finished running.
  if (!mSelections.IsEmpty()) {
    if (MOZ_LOG_TEST(sSelectionAPILog, LogLevel::Info)) {
      for (const auto& selection : mSelections) {
        if (selection && selection->Type() == SelectionType::eNormal) {
          LogSelectionAPI(selection, __FUNCTION__, "aStartBoundary",
                          aStartBoundary, "aEndBoundary", aEndBoundary,
                          "aNotInsertedYet", aNotInsertedYet);
          LogStackForSelectionAPI();
        }
      }
    }
    nsContentUtils::AddScriptRunner(
        NewRunnableMethod("NotifySelectionListenersAfterRangeSet", this,
                          &nsRange::NotifySelectionListenersAfterRangeSet));
  }
}

void nsRange::Reset() {
  DoSetRange(RawRangeBoundary(), RawRangeBoundary(), nullptr);
}

/******************************************************
* public functionality
******************************************************/

void nsRange::SetStartJS(nsINode& aNode, uint32_t aOffset, ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SetStart(aNode, aOffset, aErr);
}

bool nsRange::CanAccess(const nsINode& aNode) const {
  if (nsContentUtils::LegacyIsCallerNativeCode()) {
    return true;
  }
  return nsContentUtils::CanCallerAccess(&aNode);
}

void nsRange::SetStart(
    nsINode& aNode, uint32_t aOffset, ErrorResult& aRv,
    AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
  if (!CanAccess(aNode)) {
    aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
    return;
  }

  AutoInvalidateSelection atEndOfBlock(this);
  SetStart(RawRangeBoundary(&aNode, aOffset), aRv, aAllowCrossShadowBoundary);
}

void nsRange::SetStart(
    const RawRangeBoundary& aPoint, ErrorResult& aRv,
    AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
  nsINode* newRoot = RangeUtils::ComputeRootNode(aPoint.Container());
  if (!newRoot) {
    aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
    return;
  }

  if (!aPoint.IsSetAndValid()) {
    aRv.Throw(NS_ERROR_DOM_INDEX_SIZE_ERR);
    return;
  }

  RangeBehaviour behaviour =
      GetRangeBehaviour(this, newRoot, aPoint, true /* aIsSetStart= */,
                        aAllowCrossShadowBoundary);

  switch (behaviour) {
    case RangeBehaviour::KeepDefaultRangeAndCrossShadowBoundaryRanges:
      // EndRef(..) may be same as mStart or not, depends on
      // the value of mCrossShadowBoundaryRange->mEnd, We need to update
      // mCrossShadowBoundaryRange and the default boundaries separately
      if (aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes) {
        if (MayCrossShadowBoundaryEndRef() != mEnd) {
          CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
              aPoint, MayCrossShadowBoundaryEndRef());
        } else {
          // The normal range is good enough for this case, just use that.
          ResetCrossShadowBoundaryRange();
        }
      }
      DoSetRange(aPoint, mEnd, mRoot, false, behaviour);
      break;
    case RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges:
      DoSetRange(aPoint, aPoint, newRoot, false, behaviour);
      break;
    case RangeBehaviour::CollapseDefaultRange:
      MOZ_ASSERT(aAllowCrossShadowBoundary ==
                 AllowRangeCrossShadowBoundary::Yes);
      CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
          aPoint, MayCrossShadowBoundaryEndRef());
      DoSetRange(aPoint, aPoint, newRoot, false, behaviour);
      break;
    case RangeBehaviour::MergeDefaultRangeAndCrossShadowBoundaryRanges:
      DoSetRange(aPoint, MayCrossShadowBoundaryEndRef(), newRoot, false,
                 behaviour);
      ResetCrossShadowBoundaryRange();
      break;
    default:
      MOZ_ASSERT_UNREACHABLE();
  }
}

void nsRange::SetStartAllowCrossShadowBoundary(nsINode& aNode, uint32_t aOffset,
                                               ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SetStart(aNode, aOffset, aErr, AllowRangeCrossShadowBoundary::Yes);
}

void nsRange::SetStartBeforeJS(nsINode& aNode, ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SetStartBefore(aNode, aErr);
}

void nsRange::SetStartBefore(
    nsINode& aNode, ErrorResult& aRv,
    AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
  if (!CanAccess(aNode)) {
    aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
    return;
  }

  AutoInvalidateSelection atEndOfBlock(this);
  // If the node is being removed from its parent, GetRawRangeBoundaryBefore()
  // returns unset instance.  Then, SetStart() will throw
  // NS_ERROR_DOM_INVALID_NODE_TYPE_ERR.
  SetStart(RangeUtils::GetRawRangeBoundaryBefore(&aNode), aRv,
           aAllowCrossShadowBoundary);
}

void nsRange::SetStartAfterJS(nsINode& aNode, ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SetStartAfter(aNode, aErr);
}

void nsRange::SetStartAfter(nsINode& aNode, ErrorResult& aRv) {
  if (!CanAccess(aNode)) {
    aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
    return;
  }

  AutoInvalidateSelection atEndOfBlock(this);
  // If the node is being removed from its parent, GetRawRangeBoundaryAfter()
  // returns unset instance.  Then, SetStart() will throw
  // NS_ERROR_DOM_INVALID_NODE_TYPE_ERR.
  SetStart(RangeUtils::GetRawRangeBoundaryAfter(&aNode), aRv);
}

void nsRange::SetEndJS(nsINode& aNode, uint32_t aOffset, ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SetEnd(aNode, aOffset, aErr);
}

void nsRange::SetEnd(nsINode& aNode, uint32_t aOffset, ErrorResult& aRv,
                     AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
  if (!CanAccess(aNode)) {
    aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
    return;
  }
  AutoInvalidateSelection atEndOfBlock(this);
  SetEnd(RawRangeBoundary(&aNode, aOffset), aRv, aAllowCrossShadowBoundary);
}

void nsRange::SetEnd(const RawRangeBoundary& aPoint, ErrorResult& aRv,
                     AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
  nsINode* newRoot = RangeUtils::ComputeRootNode(aPoint.Container());
  if (!newRoot) {
    aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
    return;
  }

  if (!aPoint.IsSetAndValid()) {
    aRv.Throw(NS_ERROR_DOM_INDEX_SIZE_ERR);
    return;
  }

  RangeBehaviour policy =
      GetRangeBehaviour(this, newRoot, aPoint, false /* aIsStartStart */,
                        aAllowCrossShadowBoundary);

  switch (policy) {
    case RangeBehaviour::KeepDefaultRangeAndCrossShadowBoundaryRanges:
      // StartRef(..) may be same as mStart or not, depends on
      // the value of mCrossShadowBoundaryRange->mStart, so we need to update
      // mCrossShadowBoundaryRange and the default boundaries separately
      if (aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes) {
        if (MayCrossShadowBoundaryStartRef() != mStart) {
          CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
              MayCrossShadowBoundaryStartRef(), aPoint);
        } else {
          // The normal range is good enough for this case, just use that.
          ResetCrossShadowBoundaryRange();
        }
      }
      DoSetRange(mStart, aPoint, mRoot, false, policy);
      break;
    case RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges:
      DoSetRange(aPoint, aPoint, newRoot, false, policy);
      break;
    case RangeBehaviour::CollapseDefaultRange:
      MOZ_ASSERT(aAllowCrossShadowBoundary ==
                 AllowRangeCrossShadowBoundary::Yes);
      CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
          MayCrossShadowBoundaryStartRef(), aPoint);
      DoSetRange(aPoint, aPoint, newRoot, false, policy);
      break;
    case RangeBehaviour::MergeDefaultRangeAndCrossShadowBoundaryRanges:
      DoSetRange(MayCrossShadowBoundaryStartRef(), aPoint, newRoot, false,
                 policy);
      ResetCrossShadowBoundaryRange();
      break;
    default:
      MOZ_ASSERT_UNREACHABLE();
  }
}

void nsRange::SetEndAllowCrossShadowBoundary(nsINode& aNode, uint32_t aOffset,
                                             ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SetEnd(aNode, aOffset, aErr,
         AllowRangeCrossShadowBoundary::Yes /* aAllowCrossShadowBoundary */);
}

void nsRange::SelectNodesInContainer(nsINode* aContainer,
                                     nsIContent* aStartContent,
                                     nsIContent* aEndContent) {
  MOZ_ASSERT(aContainer);
  MOZ_ASSERT(aContainer->ComputeIndexOf(aStartContent).valueOr(0) <=
             aContainer->ComputeIndexOf(aEndContent).valueOr(0));
  MOZ_ASSERT(aStartContent &&
             aContainer->ComputeIndexOf(aStartContent).isSome());
  MOZ_ASSERT(aEndContent && aContainer->ComputeIndexOf(aEndContent).isSome());

  nsINode* newRoot = RangeUtils::ComputeRootNode(aContainer);
  MOZ_ASSERT(newRoot);
  if (!newRoot) {
    return;
  }

  RawRangeBoundary start(aContainer, aStartContent->GetPreviousSibling());
  RawRangeBoundary end(aContainer, aEndContent);
  DoSetRange(start, end, newRoot);
}

void nsRange::SetEndBeforeJS(nsINode& aNode, ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SetEndBefore(aNode, aErr);
}

void nsRange::SetEndBefore(
    nsINode& aNode, ErrorResult& aRv,
    AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
  if (!CanAccess(aNode)) {
    aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
    return;
  }

  AutoInvalidateSelection atEndOfBlock(this);
  // If the node is being removed from its parent, GetRawRangeBoundaryBefore()
  // returns unset instance.  Then, SetEnd() will throw
  // NS_ERROR_DOM_INVALID_NODE_TYPE_ERR.
  SetEnd(RangeUtils::GetRawRangeBoundaryBefore(&aNode), aRv,
         aAllowCrossShadowBoundary);
}

void nsRange::SetEndAfterJS(nsINode& aNode, ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SetEndAfter(aNode, aErr);
}

void nsRange::SetEndAfter(nsINode& aNode, ErrorResult& aRv) {
  if (!CanAccess(aNode)) {
    aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
    return;
  }

  AutoInvalidateSelection atEndOfBlock(this);
  // If the node is being removed from its parent, GetRawRangeBoundaryAfter()
  // returns unset instance.  Then, SetEnd() will throw
  // NS_ERROR_DOM_INVALID_NODE_TYPE_ERR.
  SetEnd(RangeUtils::GetRawRangeBoundaryAfter(&aNode), aRv);
}

void nsRange::Collapse(bool aToStart) {
  if (!mIsPositioned) return;

  AutoInvalidateSelection atEndOfBlock(this);
  if (aToStart) {
    DoSetRange(mStart, mStart, mRoot);
  } else {
    DoSetRange(mEnd, mEnd, mRoot);
  }
}

void nsRange::CollapseJS(bool aToStart) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  Collapse(aToStart);
}

void nsRange::SelectNodeJS(nsINode& aNode, ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SelectNode(aNode, aErr);
}

void nsRange::SelectNode(nsINode& aNode, ErrorResult& aRv) {
  if (!CanAccess(aNode)) {
    aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
    return;
  }

  nsINode* container = aNode.GetParentNode();
  nsINode* newRoot = RangeUtils::ComputeRootNode(container);
  if (!newRoot) {
    aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
    return;
  }

  const Maybe<uint32_t> index = container->ComputeIndexOf(&aNode);
  // MOZ_ASSERT(index.isSome());
  // We need to compute the index here unfortunately, because, while we have
  // support for XBL, |container| may be the node's binding parent without
  // actually containing it.
  if (MOZ_UNLIKELY(NS_WARN_IF(index.isNothing()))) {
    aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
    return;
  }

  AutoInvalidateSelection atEndOfBlock(this);
  DoSetRange(RawRangeBoundary{container, *index},
             RawRangeBoundary{container, *index + 1u}, newRoot);
}

void nsRange::SelectNodeContentsJS(nsINode& aNode, ErrorResult& aErr) {
  AutoCalledByJSRestore calledByJSRestorer(*this);
  mCalledByJS = true;
  SelectNodeContents(aNode, aErr);
}

void nsRange::SelectNodeContents(nsINode& aNode, ErrorResult& aRv) {
  if (!CanAccess(aNode)) {
    aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
    return;
  }

  nsINode* newRoot = RangeUtils::ComputeRootNode(&aNode);
  if (!newRoot) {
    aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
    return;
  }

  AutoInvalidateSelection atEndOfBlock(this);
  DoSetRange(RawRangeBoundary(&aNode, 0u),
             RawRangeBoundary(&aNode, aNode.Length()), newRoot);
}

// The Subtree Content Iterator only returns subtrees that are
// completely within a given range. It doesn't return a CharacterData
// node that contains either the start or end point of the range.,
// nor does it return element nodes when nothing in the element is selected.
// We need an iterator that will also include these start/end points
// so that our methods/algorithms aren't cluttered with special
// case code that tries to include these points while iterating.
//
// The RangeSubtreeIterator class mimics the ContentSubtreeIterator
// methods we need, so should the Content Iterator support the
// start/end points in the future, we can switchover relatively
// easy.

class MOZ_STACK_CLASS RangeSubtreeIterator {
private:
  enum RangeSubtreeIterState { eDone = 0, eUseStart, eUseIterator, eUseEnd };

  Maybe<ContentSubtreeIterator> mSubtreeIter;
  RangeSubtreeIterState mIterState;

  nsCOMPtr<nsINode> mStart;
  nsCOMPtr<nsINode> mEnd;

public:
  RangeSubtreeIterator() : mIterState(eDone) {}
  ~RangeSubtreeIterator() = default;

  nsresult Init(nsRange* aRange, AllowRangeCrossShadowBoundary =
                                     AllowRangeCrossShadowBoundary::No);
  already_AddRefed<nsINode> GetCurrentNode();
  void First();
  void Last();
  void Next();
  void Prev();

  bool IsDone() { return mIterState == eDone; }
};

nsresult RangeSubtreeIterator::Init(
    nsRange* aRange, AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
  mIterState = eDone;
  if (aRange->AreNormalRangeAndCrossShadowBoundaryRangeCollapsed()) {
    return NS_OK;
  }

  // Grab the start point of the range and QI it to
  // a CharacterData pointer. If it is CharacterData store
  // a pointer to the node.

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

  nsINode* node = aRange->GetMayCrossShadowBoundaryStartContainer();
  if (NS_WARN_IF(!node)) {
    return NS_ERROR_FAILURE;
  }

  if (node->IsCharacterData() ||
      (node->IsElement() && node->AsElement()->GetChildCount() ==
                                aRange->MayCrossShadowBoundaryStartOffset())) {
    mStart = node;
  }

  // Grab the end point of the range and QI it to
  // a CharacterData pointer. If it is CharacterData store
  // a pointer to the node.

  node = aRange->GetMayCrossShadowBoundaryEndContainer();
  if (NS_WARN_IF(!node)) {
    return NS_ERROR_FAILURE;
  }

  if (node->IsCharacterData() ||
      (node->IsElement() && aRange->MayCrossShadowBoundaryEndOffset() == 0)) {
    mEnd = node;
  }

  if (mStart && mStart == mEnd) {
    // The range starts and stops in the same CharacterData
    // node. Null out the end pointer so we only visit the
    // node once!

    mEnd = nullptr;
  } else {
    // Now create a Content Subtree Iterator to be used
    // for the subtrees between the end points!

    mSubtreeIter.emplace();

    nsresult res =
        aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes
            ? mSubtreeIter->InitWithAllowCrossShadowBoundary(aRange)
            : mSubtreeIter->Init(aRange);
    if (NS_FAILED(res)) return res;

    if (mSubtreeIter->IsDone()) {
      // The subtree iterator thinks there's nothing
      // to iterate over, so just free it up so we
      // don't accidentally call into it.

      mSubtreeIter.reset();
    }
  }

  // Initialize the iterator by calling First().
  // Note that we are ignoring the return value on purpose!

  First();

  return NS_OK;
}

already_AddRefed<nsINode> RangeSubtreeIterator::GetCurrentNode() {
  nsCOMPtr<nsINode> node;

  if (mIterState == eUseStart && mStart) {
    node = mStart;
  } else if (mIterState == eUseEnd && mEnd) {
    node = mEnd;
  } else if (mIterState == eUseIterator && mSubtreeIter) {
    node = mSubtreeIter->GetCurrentNode();
  }

  return node.forget();
}

void RangeSubtreeIterator::First() {
  if (mStart)
    mIterState = eUseStart;
  else if (mSubtreeIter) {
    mSubtreeIter->First();

    mIterState = eUseIterator;
  } else if (mEnd)
    mIterState = eUseEnd;
  else
    mIterState = eDone;
}

void RangeSubtreeIterator::Last() {
  if (mEnd)
    mIterState = eUseEnd;
  else if (mSubtreeIter) {
    mSubtreeIter->Last();

    mIterState = eUseIterator;
  } else if (mStart)
    mIterState = eUseStart;
  else
    mIterState = eDone;
}

void RangeSubtreeIterator::Next() {
  if (mIterState == eUseStart) {
    if (mSubtreeIter) {
      mSubtreeIter->First();

      mIterState = eUseIterator;
    } else if (mEnd)
      mIterState = eUseEnd;
    else
      mIterState = eDone;
  } else if (mIterState == eUseIterator) {
    mSubtreeIter->Next();

    if (mSubtreeIter->IsDone()) {
      if (mEnd)
        mIterState = eUseEnd;
      else
        mIterState = eDone;
    }
  } else
    mIterState = eDone;
}

void RangeSubtreeIterator::Prev() {
  if (mIterState == eUseEnd) {
    if (mSubtreeIter) {
      mSubtreeIter->Last();

      mIterState = eUseIterator;
    } else if (mStart)
      mIterState = eUseStart;
    else
      mIterState = eDone;
  } else if (mIterState == eUseIterator) {
    mSubtreeIter->Prev();

    if (mSubtreeIter->IsDone()) {
      if (mStart)
        mIterState = eUseStart;
      else
        mIterState = eDone;
    }
  } else
    mIterState = eDone;
}

// CollapseRangeAfterDelete() is a utility method that is used by
// DeleteContents() and ExtractContents() to collapse the range
// in the correct place, under the range's root container (the
// range end points common container) as outlined by the Range spec:
//
// http://www.w3.org/TR/2000/REC-DOM-Level-2-Traversal-Range-20001113/ranges.html
// The assumption made by this method is that the delete or extract
// has been done already, and left the range in a state where there is
// no content between the 2 end points.

static nsresult CollapseRangeAfterDelete(nsRange* aRange) {
  NS_ENSURE_ARG_POINTER(aRange);

  // Check if range gravity took care of collapsing the range for us!
  if (aRange->Collapsed()) {
    // aRange is collapsed so there's nothing for us to do.
    //
    // There are 2 possible scenarios here:
    //
    // 1. aRange could've been collapsed prior to the delete/extract,
    //    which would've resulted in nothing being removed, so aRange
    //    is already where it should be.
    //
    // 2. Prior to the delete/extract, aRange's start and end were in
    //    the same container which would mean everything between them
    //    was removed, causing range gravity to collapse the range.

    return NS_OK;
  }

  // aRange isn't collapsed so figure out the appropriate place to collapse!
  // First get both end points and their common ancestor.

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

  nsCOMPtr<nsINode> commonAncestor =
      aRange->GetClosestCommonInclusiveAncestor();

  nsCOMPtr<nsINode> startContainer = aRange->GetStartContainer();
  nsCOMPtr<nsINode> endContainer = aRange->GetEndContainer();

  // Collapse to one of the end points if they are already in the
  // commonAncestor. This should work ok since this method is called
  // immediately after a delete or extract that leaves no content
  // between the 2 end points!

  if (startContainer == commonAncestor) {
    aRange->Collapse(true);
    return NS_OK;
  }
  if (endContainer == commonAncestor) {
    aRange->Collapse(false);
    return NS_OK;
  }

  // End points are at differing levels. We want to collapse to the
  // point that is between the 2 subtrees that contain each point,
  // under the common ancestor.

  nsCOMPtr<nsINode> nodeToSelect(startContainer);

  while (nodeToSelect) {
    nsCOMPtr<nsINode> parent = nodeToSelect->GetParentNode();
    if (parent == commonAncestor) break;  // We found the nodeToSelect!

    nodeToSelect = parent;
  }

  if (!nodeToSelect) return NS_ERROR_FAILURE;  // This should never happen!

  ErrorResult error;
  aRange->SelectNode(*nodeToSelect, error);
  if (error.Failed()) {
    return error.StealNSResult();
  }

  aRange->Collapse(false);
  return NS_OK;
}

NS_IMETHODIMP
PrependChild(nsINode* aContainer, nsINode* aChild) {
  nsCOMPtr<nsINode> first = aContainer->GetFirstChild();
  ErrorResult rv;
  aContainer->InsertBefore(*aChild, first, rv);
  return rv.StealNSResult();
}

// Helper function for CutContents, making sure that the current node wasn't
// removed by mutation events (bug 766426)
static bool ValidateCurrentNode(nsRange* aRange, RangeSubtreeIterator& aIter) {
  bool before, after;
  nsCOMPtr<nsINode> node = aIter.GetCurrentNode();
  if (!node) {
    // We don't have to worry that the node was removed if it doesn't exist,
    // e.g., the iterator is done.
    return true;
  }

  nsresult rv = RangeUtils::CompareNodeToRange(node, aRange, &before, &after);
  if (NS_WARN_IF(NS_FAILED(rv))) {
    return false;
  }

  if (before || after) {
    if (node->IsCharacterData()) {
      // If we're dealing with the start/end container which is a character
      // node, pretend that the node is in the range.
      if (before && node == aRange->GetStartContainer()) {
        before = false;
      }
      if (after && node == aRange->GetEndContainer()) {
        after = false;
      }
    }
  }

  return !before && !after;
}

void nsRange::CutContents(DocumentFragment** aFragment, ErrorResult& aRv) {
  if (aFragment) {
    *aFragment = nullptr;
  }

  if (!CanAccess(*GetMayCrossShadowBoundaryStartContainer()) ||
      !CanAccess(*GetMayCrossShadowBoundaryEndContainer())) {
    aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
    return;
  }

  nsCOMPtr<Document> doc = mStart.Container()->OwnerDoc();

  nsCOMPtr<nsINode> commonAncestor = GetCommonAncestorContainer(
      aRv, StaticPrefs::dom_shadowdom_selection_across_boundary_enabled()
--> --------------------

--> maximum size reached

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

quality99%