dom/base/nsRange.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /*
   8  * Implementation of the DOM Range object.
   9  */
  10
  11 #include "RangeBoundary.h"
  12 #include "nscore.h"
  13 #include "nsRange.h"
  14
  15 #include "nsDebug.h"
  16 #include "nsString.h"
  17 #include "nsReadableUtils.h"
  18 #include "nsIContent.h"
  19 #include "mozilla/dom/Document.h"
  20 #include "nsError.h"
  21 #include "nsINodeList.h"
  22 #include "nsGkAtoms.h"
  23 #include "nsContentUtils.h"
  24 #include "nsFrameSelection.h"
  25 #include "nsLayoutUtils.h"
  26 #include "nsTextFrame.h"
  27 #include "nsContainerFrame.h"
  28 #include "mozilla/Assertions.h"
  29 #include "mozilla/CheckedInt.h"
  30 #include "mozilla/ContentIterator.h"
  31 #include "mozilla/dom/CharacterData.h"
  32 #include "mozilla/dom/ChildIterator.h"
  33 #include "mozilla/dom/DOMRect.h"
  34 #include "mozilla/dom/DOMStringList.h"
  35 #include "mozilla/dom/DocumentFragment.h"
  36 #include "mozilla/dom/DocumentType.h"
  37 #include "mozilla/dom/RangeBinding.h"
  38 #include "mozilla/dom/Selection.h"
  39 #include "mozilla/dom/Text.h"
  40 #include "mozilla/dom/TrustedTypeUtils.h"
  41 #include "mozilla/dom/TrustedTypesConstants.h"
  42 #include "mozilla/Logging.h"
  43 #include "mozilla/Maybe.h"
  44 #include "mozilla/PresShell.h"
  45 #include "mozilla/RangeUtils.h"
  46 #include "mozilla/Telemetry.h"
  47 #include "mozilla/ToString.h"
  48 #include "mozilla/UniquePtr.h"
  49 #include "mozilla/Likely.h"
  50 #include "nsCSSFrameConstructor.h"
  51 #include "nsStyleStruct.h"
  52 #include "nsStyleStructInlines.h"
  53 #include "nsComputedDOMStyle.h"
  54 #include "mozilla/dom/InspectorFontFace.h"
  55
  56 #ifdef ACCESSIBILITY
  57 #  include "nsAccessibilityService.h"
  58 #endif
  59
  60 namespace mozilla {
  61 extern LazyLogModule sSelectionAPILog;
  62 extern void LogStackForSelectionAPI();
  63
  64 template <typename SPT, typename SRT, typename EPT, typename ERT>
  65 static void LogSelectionAPI(const dom::Selection* aSelection,
  66                             const char* aFuncName, const char* aArgName1,
  67                             const RangeBoundaryBase<SPT, SRT>& aBoundary1,
  68                             const char* aArgName2,
  69                             const RangeBoundaryBase<EPT, ERT>& aBoundary2,
  70                             const char* aArgName3, bool aBoolArg) {
  71   if (aBoundary1 == aBoundary2) {
  72     MOZ_LOG(sSelectionAPILog, LogLevel::Info,
  73             ("%p nsRange::%s(%s=%s=%s, %s=%s)", aSelection, aFuncName,
  74              aArgName1, aArgName2, ToString(aBoundary1).c_str(), aArgName3,
  75              aBoolArg ? "true" : "false"));
  76   } else {
  77     MOZ_LOG(
  78         sSelectionAPILog, LogLevel::Info,
  79         ("%p nsRange::%s(%s=%s, %s=%s, %s=%s)", aSelection, aFuncName,
  80          aArgName1, ToString(aBoundary1).c_str(), aArgName2,
  81          ToString(aBoundary2).c_str(), aArgName3, aBoolArg ? "true" : "false"));
  82   }
  83 }
  84 }  // namespace mozilla
  85
  86 using namespace mozilla;
  87 using namespace mozilla::dom;
  88
  89 template already_AddRefed<nsRange> nsRange::Create(
  90     const RangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary,
  91     ErrorResult& aRv);
  92 template already_AddRefed<nsRange> nsRange::Create(
  93     const RangeBoundary& aStartBoundary, const RawRangeBoundary& aEndBoundary,
  94     ErrorResult& aRv);
  95 template already_AddRefed<nsRange> nsRange::Create(
  96     const RawRangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary,
  97     ErrorResult& aRv);
  98 template already_AddRefed<nsRange> nsRange::Create(
  99     const RawRangeBoundary& aStartBoundary,
 100     const RawRangeBoundary& aEndBoundary, ErrorResult& aRv);
 101
 102 template nsresult nsRange::SetStartAndEnd(const RangeBoundary& aStartBoundary,
 103                                           const RangeBoundary& aEndBoundary);
 104 template nsresult nsRange::SetStartAndEnd(const RangeBoundary& aStartBoundary,
 105                                           const RawRangeBoundary& aEndBoundary);
 106 template nsresult nsRange::SetStartAndEnd(
 107     const RawRangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary);
 108 template nsresult nsRange::SetStartAndEnd(
 109     const RawRangeBoundary& aStartBoundary,
 110     const RawRangeBoundary& aEndBoundary);
 111
 112 template void nsRange::DoSetRange(const RangeBoundary& aStartBoundary,
 113                                   const RangeBoundary& aEndBoundary,
 114                                   nsINode* aRootNode, bool aNotInsertedYet,
 115                                   RangeBehaviour aRangeBehaviour);
 116 template void nsRange::DoSetRange(const RangeBoundary& aStartBoundary,
 117                                   const RawRangeBoundary& aEndBoundary,
 118                                   nsINode* aRootNode, bool aNotInsertedYet,
 119                                   RangeBehaviour aRangeBehaviour);
 120 template void nsRange::DoSetRange(const RawRangeBoundary& aStartBoundary,
 121                                   const RangeBoundary& aEndBoundary,
 122                                   nsINode* aRootNode, bool aNotInsertedYet,
 123                                   RangeBehaviour aRangeBehaviour);
 124 template void nsRange::DoSetRange(const RawRangeBoundary& aStartBoundary,
 125                                   const RawRangeBoundary& aEndBoundary,
 126                                   nsINode* aRootNode, bool aNotInsertedYet,
 127                                   RangeBehaviour aRangeBehaviour);
 128
 129 template void nsRange::CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
 130     const RangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary);
 131 template void nsRange::CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
 132     const RangeBoundary& aStartBoundary, const RawRangeBoundary& aEndBoundary);
 133 template void nsRange::CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
 134     const RawRangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary);
 135 template void nsRange::CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
 136     const RawRangeBoundary& aStartBoundary,
 137     const RawRangeBoundary& aEndBoundary);
 138
 139 JSObject* nsRange::WrapObject(JSContext* aCx,
 140                               JS::Handle<JSObject*> aGivenProto) {
 141   return Range_Binding::Wrap(aCx, this, aGivenProto);
 142 }
 143
 144 DocGroup* nsRange::GetDocGroup() const {
 145   return mOwner ? mOwner->GetDocGroup() : nullptr;
 146 }
 147
 148 /******************************************************
 149  * stack based utility class for managing monitor
 150  ******************************************************/
 151
 152 static void InvalidateAllFrames(nsINode* aNode) {
 153   MOZ_ASSERT(aNode, "bad arg");
 154
 155   nsIFrame* frame = nullptr;
 156   switch (aNode->NodeType()) {
 157     case nsINode::TEXT_NODE:
 158     case nsINode::ELEMENT_NODE: {
 159       nsIContent* content = static_cast<nsIContent*>(aNode);
 160       frame = content->GetPrimaryFrame();
 161       break;
 162     }
 163     case nsINode::DOCUMENT_NODE: {
 164       Document* doc = static_cast<Document*>(aNode);
 165       PresShell* presShell = doc ? doc->GetPresShell() : nullptr;
 166       frame = presShell ? presShell->GetRootFrame() : nullptr;
 167       break;
 168     }
 169   }
 170   for (nsIFrame* f = frame; f; f = f->GetNextContinuation()) {
 171     f->InvalidateFrameSubtree();
 172   }
 173 }
 174
 175 /******************************************************
 176  * constructor/destructor
 177  ******************************************************/
 178
 179 nsTArray<RefPtr<nsRange>>* nsRange::sCachedRanges = nullptr;
 180
 181 nsRange::~nsRange() {
 182   NS_ASSERTION(!IsInAnySelection(), "deleting nsRange that is in use");
 183
 184   // we want the side effects (releases and list removals)
 185   DoSetRange(RawRangeBoundary(), RawRangeBoundary(), nullptr);
 186 }
 187
 188 nsRange::nsRange(nsINode* aNode)
 189     : AbstractRange(aNode, /* aIsDynamicRange = */ true),
 190       mNextStartRef(nullptr),
 191       mNextEndRef(nullptr) {
 192   // printf("Size of nsRange: %zu\n", sizeof(nsRange));
 193
 194   static_assert(sizeof(nsRange) <= 248,
 195                 "nsRange size shouldn't be increased as far as possible");
 196 }
 197
 198 /* static */
 199 already_AddRefed<nsRange> nsRange::Create(nsINode* aNode) {
 200   MOZ_ASSERT(aNode);
 201   if (!sCachedRanges || sCachedRanges->IsEmpty()) {
 202     return do_AddRef(new nsRange(aNode));
 203   }
 204   RefPtr<nsRange> range = sCachedRanges->PopLastElement().forget();
 205   range->Init(aNode);
 206   return range.forget();
 207 }
 208
 209 /* static */
 210 template <typename SPT, typename SRT, typename EPT, typename ERT>
 211 already_AddRefed<nsRange> nsRange::Create(
 212     const RangeBoundaryBase<SPT, SRT>& aStartBoundary,
 213     const RangeBoundaryBase<EPT, ERT>& aEndBoundary, ErrorResult& aRv) {
 214   // If we fail to initialize the range a lot, nsRange should have a static
 215   // initializer since the allocation cost is not cheap in hot path.
 216   RefPtr<nsRange> range = nsRange::Create(aStartBoundary.Container());
 217   aRv = range->SetStartAndEnd(aStartBoundary, aEndBoundary);
 218   if (NS_WARN_IF(aRv.Failed())) {
 219     return nullptr;
 220   }
 221   return range.forget();
 222 }
 223
 224 /*
 225  * When a new boundary is given to a nsRange, compare its position with other
 226  * existing boundaries to see if we need to collapse the end points.
 227  *
 228  * aRange: The nsRange that aNewBoundary is being set to.
 229  * aNewRoot: The shadow-including root of the container of aNewBoundary
 230  * aNewBoundary: The new boundary
 231  * aIsSetStart: true if GetRangeBehaviour is called by nsRange::SetStart,
 232  * false otherwise
 233  * aAllowCrossShadowBoundary: Indicates whether the boundaries allowed to cross
 234  * shadow boundary or not
 235  */
 236 static RangeBehaviour GetRangeBehaviour(
 237     const nsRange* aRange, const nsINode* aNewRoot,
 238     const RawRangeBoundary& aNewBoundary, const bool aIsSetStart,
 239     AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
 240   if (!aRange->IsPositioned()) {
 241     return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
 242   }
 243
 244   MOZ_ASSERT(aRange->GetRoot());
 245
 246   if (aNewRoot != aRange->GetRoot()) {
 247     // Boundaries are in different document (or not connected), so collapse
 248     // the both the default range and the crossBoundaryRange range.
 249     if (aNewRoot->GetComposedDoc() != aRange->GetRoot()->GetComposedDoc()) {
 250       return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
 251     }
 252
 253     // Always collapse both ranges if the one of the roots is an UA widget
 254     // regardless whether the boundaries are allowed to cross shadow boundary
 255     // or not.
 256     if (AbstractRange::IsRootUAWidget(aNewRoot) ||
 257         AbstractRange::IsRootUAWidget(aRange->GetRoot())) {
 258       return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
 259     }
 260
 261     if (const CrossShadowBoundaryRange* crossShadowBoundaryRange =
 262             aRange->GetCrossShadowBoundaryRange()) {
 263       // Check if the existing-other-side boundary in
 264       // aRange::mCrossShadowBoundaryRange has the same root
 265       // as aNewRoot. If this is the case, it means default range
 266       // is good enough to represent this range, so that we can
 267       // merge the cross-shadow-boundary range and the default range.
 268       const RangeBoundary& otherSideExistingBoundary =
 269           aIsSetStart ? crossShadowBoundaryRange->EndRef()
 270                       : crossShadowBoundaryRange->StartRef();
 271       const nsINode* otherSideRoot =
 272           RangeUtils::ComputeRootNode(otherSideExistingBoundary.Container());
 273       if (aNewRoot == otherSideRoot) {
 274         return RangeBehaviour::MergeDefaultRangeAndCrossShadowBoundaryRanges;
 275       }
 276     }
 277
 278     // Different root, but same document. So we only collapse the
 279     // default range if boundaries are allowed to cross shadow boundary.
 280     return aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes
 281                ? RangeBehaviour::CollapseDefaultRange
 282                : RangeBehaviour::
 283                      CollapseDefaultRangeAndCrossShadowBoundaryRanges;
 284   }
 285
 286   const RangeBoundary& otherSideExistingBoundary =
 287       aIsSetStart ? aRange->EndRef() : aRange->StartRef();
 288
 289   // Both bondaries are in the same root, now check for their position
 290   const Maybe<int32_t> order =
 291       aIsSetStart ? nsContentUtils::ComparePoints(aNewBoundary,
 292                                                   otherSideExistingBoundary)
 293                   : nsContentUtils::ComparePoints(otherSideExistingBoundary,
 294                                                   aNewBoundary);
 295
 296   if (order) {
 297     if (*order != 1) {
 298       // aNewBoundary is at a valid position.
 299       //
 300       // If aIsSetStart is true, this means
 301       // aNewBoundary <= otherSideExistingBoundary which is
 302       // good because aNewBoundary intends to be the start.
 303       //
 304       // If aIsSetStart is false, this means
 305       // otherSideExistingBoundary <= aNewBoundary which is good because
 306       // aNewBoundary intends to be the end.
 307       //
 308       // So no collapse for above cases.
 309       return RangeBehaviour::KeepDefaultRangeAndCrossShadowBoundaryRanges;
 310     }
 311
 312     if (!aRange->MayCrossShadowBoundary() ||
 313         aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::No) {
 314       return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
 315     }
 316
 317     const RangeBoundary& otherSideExistingCrossShadowBoundaryBoundary =
 318         aIsSetStart ? aRange->MayCrossShadowBoundaryEndRef()
 319                     : aRange->MayCrossShadowBoundaryStartRef();
 320
 321     // Please see the comment for (*order != 1) to see what "valid" means.
 322     //
 323     // We reach to this line when (*order == 1), it means aNewBoundary is
 324     // at an invalid position, so we need to collapse aNewBoundary with
 325     // otherSideExistingBoundary. However, it's possible that aNewBoundary
 326     // is valid with the otherSideExistingCrossShadowBoundaryBoundary.
 327     const Maybe<int32_t> withCrossShadowBoundaryOrder =
 328         aIsSetStart
 329             ? nsContentUtils::ComparePoints(
 330                   aNewBoundary, otherSideExistingCrossShadowBoundaryBoundary)
 331             : nsContentUtils::ComparePoints(
 332                   otherSideExistingCrossShadowBoundaryBoundary, aNewBoundary);
 333
 334     // Valid to the cross boundary boundary.
 335     if (withCrossShadowBoundaryOrder && *withCrossShadowBoundaryOrder != 1) {
 336       return RangeBehaviour::CollapseDefaultRange;
 337     }
 338
 339     // Not valid to both existing boundaries.
 340     return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
 341   }
 342
 343   MOZ_ASSERT_UNREACHABLE();
 344   return RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges;
 345 }
 346 /******************************************************
 347  * nsISupports
 348  ******************************************************/
 349
 350 NS_IMPL_CYCLE_COLLECTING_ADDREF(nsRange)
 351 NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_INTERRUPTABLE_LAST_RELEASE(
 352     nsRange, DoSetRange(RawRangeBoundary(), RawRangeBoundary(), nullptr),
 353     MaybeInterruptLastRelease())
 354
 355 // QueryInterface implementation for nsRange
 356 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsRange)
 357   NS_INTERFACE_MAP_ENTRY(nsIMutationObserver)
 358 NS_INTERFACE_MAP_END_INHERITING(AbstractRange)
 359
 360 NS_IMPL_CYCLE_COLLECTION_CLASS(nsRange)
 361
 362 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN_INHERITED(nsRange, AbstractRange)
 363   // `Reset()` unlinks `mStart`, `mEnd` and `mRoot`.
 364   NS_IMPL_CYCLE_COLLECTION_UNLINK(mCrossShadowBoundaryRange);
 365   tmp->Reset();
 366 NS_IMPL_CYCLE_COLLECTION_UNLINK_END
 367
 368 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN_INHERITED(nsRange, AbstractRange)
 369   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mRoot)
 370   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mCrossShadowBoundaryRange);
 371 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
 372
 373 NS_IMPL_CYCLE_COLLECTION_TRACE_BEGIN_INHERITED(nsRange, AbstractRange)
 374 NS_IMPL_CYCLE_COLLECTION_TRACE_END
 375
 376 bool nsRange::MaybeInterruptLastRelease() {
 377   bool interrupt = AbstractRange::MaybeCacheToReuse(*this);
 378   ResetCrossShadowBoundaryRange();
 379   MOZ_ASSERT(!interrupt || IsCleared());
 380   return interrupt;
 381 }
 382
 383 void nsRange::AdjustNextRefsOnCharacterDataSplit(
 384     const nsIContent& aContent, const CharacterDataChangeInfo& aInfo) {
 385   // If the splitted text node is immediately before a range boundary point
 386   // that refers to a child index (i.e. its parent is the boundary container)
 387   // then we need to adjust the corresponding boundary to account for the new
 388   // text node that will be inserted. However, because the new sibling hasn't
 389   // been inserted yet, that would result in an invalid boundary. Therefore,
 390   // we store the new child in mNext*Ref to make sure we adjust the boundary
 391   // in the next ContentInserted or ContentAppended call.
 392   nsINode* parentNode = aContent.GetParentNode();
 393   if (parentNode == mEnd.Container()) {
 394     if (&aContent == mEnd.Ref()) {
 395       MOZ_ASSERT(aInfo.mDetails->mNextSibling);
 396       mNextEndRef = aInfo.mDetails->mNextSibling;
 397     }
 398   }
 399
 400   if (parentNode == mStart.Container()) {
 401     if (&aContent == mStart.Ref()) {
 402       MOZ_ASSERT(aInfo.mDetails->mNextSibling);
 403       mNextStartRef = aInfo.mDetails->mNextSibling;
 404     }
 405   }
 406 }
 407
 408 nsRange::RangeBoundariesAndRoot
 409 nsRange::DetermineNewRangeBoundariesAndRootOnCharacterDataMerge(
 410     nsIContent* aContent, const CharacterDataChangeInfo& aInfo) const {
 411   RawRangeBoundary newStart;
 412   RawRangeBoundary newEnd;
 413   nsINode* newRoot = nullptr;
 414
 415   // normalize(), aInfo.mDetails->mNextSibling is the merged text node
 416   // that will be removed
 417   nsIContent* removed = aInfo.mDetails->mNextSibling;
 418   if (removed == mStart.Container()) {
 419     CheckedUint32 newStartOffset{
 420         *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets)};
 421     newStartOffset += aInfo.mChangeStart;
 422
 423     // newStartOffset.isValid() isn't checked explicitly here, because
 424     // newStartOffset.value() contains an assertion.
 425     newStart = {aContent, newStartOffset.value()};
 426     if (MOZ_UNLIKELY(removed == mRoot)) {
 427       newRoot = RangeUtils::ComputeRootNode(newStart.Container());
 428     }
 429   }
 430   if (removed == mEnd.Container()) {
 431     CheckedUint32 newEndOffset{
 432         *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets)};
 433     newEndOffset += aInfo.mChangeStart;
 434
 435     // newEndOffset.isValid() isn't checked explicitly here, because
 436     // newEndOffset.value() contains an assertion.
 437     newEnd = {aContent, newEndOffset.value()};
 438     if (MOZ_UNLIKELY(removed == mRoot)) {
 439       newRoot = {RangeUtils::ComputeRootNode(newEnd.Container())};
 440     }
 441   }
 442   // When the removed text node's parent is one of our boundary nodes we may
 443   // need to adjust the offset to account for the removed node. However,
 444   // there will also be a ContentRemoved notification later so the only cases
 445   // we need to handle here is when the removed node is the text node after
 446   // the boundary.  (The m*Offset > 0 check is an optimization - a boundary
 447   // point before the first child is never affected by normalize().)
 448   nsINode* parentNode = aContent->GetParentNode();
 449   if (parentNode == mStart.Container() &&
 450       *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) > 0 &&
 451       *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) <
 452           parentNode->GetChildCount() &&
 453       removed == mStart.GetChildAtOffset()) {
 454     newStart = {aContent, aInfo.mChangeStart};
 455   }
 456   if (parentNode == mEnd.Container() &&
 457       *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) > 0 &&
 458       *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) <
 459           parentNode->GetChildCount() &&
 460       removed == mEnd.GetChildAtOffset()) {
 461     newEnd = {aContent, aInfo.mChangeEnd};
 462   }
 463
 464   return {newStart, newEnd, newRoot};
 465 }
 466
 467 /******************************************************
 468  * nsIMutationObserver implementation
 469  ******************************************************/
 470 void nsRange::CharacterDataChanged(nsIContent* aContent,
 471                                    const CharacterDataChangeInfo& aInfo) {
 472   MOZ_ASSERT(aContent);
 473   MOZ_ASSERT(mIsPositioned);
 474   MOZ_ASSERT(!mNextEndRef);
 475   MOZ_ASSERT(!mNextStartRef);
 476
 477   nsINode* newRoot = nullptr;
 478   RawRangeBoundary newStart;
 479   RawRangeBoundary newEnd;
 480
 481   if (aInfo.mDetails &&
 482       aInfo.mDetails->mType == CharacterDataChangeInfo::Details::eSplit) {
 483     AdjustNextRefsOnCharacterDataSplit(*aContent, aInfo);
 484   }
 485
 486   // If the changed node contains our start boundary and the change starts
 487   // before the boundary we'll need to adjust the offset.
 488   if (aContent == mStart.Container() &&
 489       aInfo.mChangeStart <
 490           *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets)) {
 491     if (aInfo.mDetails) {
 492       // splitText(), aInfo->mDetails->mNextSibling is the new text node
 493       NS_ASSERTION(
 494           aInfo.mDetails->mType == CharacterDataChangeInfo::Details::eSplit,
 495           "only a split can start before the end");
 496       NS_ASSERTION(
 497           *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) <=
 498               aInfo.mChangeEnd + 1,
 499           "mStart.Offset() is beyond the end of this node");
 500       const uint32_t newStartOffset =
 501           *mStart.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) -
 502           aInfo.mChangeStart;
 503       newStart = {aInfo.mDetails->mNextSibling, newStartOffset};
 504       if (MOZ_UNLIKELY(aContent == mRoot)) {
 505         newRoot = RangeUtils::ComputeRootNode(newStart.Container());
 506       }
 507
 508       bool isCommonAncestor =
 509           IsInAnySelection() && mStart.Container() == mEnd.Container();
 510       if (isCommonAncestor) {
 511         MOZ_DIAGNOSTIC_ASSERT(mStart.Container() ==
 512                               mRegisteredClosestCommonInclusiveAncestor);
 513         UnregisterClosestCommonInclusiveAncestor();
 514         RegisterClosestCommonInclusiveAncestor(newStart.Container());
 515       }
 516       if (mStart.Container()
 517               ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
 518         newStart.Container()
 519             ->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
 520       }
 521     } else {
 522       newStart = ComputeNewBoundaryWhenBoundaryInsideChangedText(
 523           aInfo, mStart.AsRaw());
 524     }
 525   }
 526
 527   // Do the same thing for the end boundary, except for splitText of a node
 528   // with no parent then only switch to the new node if the start boundary
 529   // did so too (otherwise the range would end up with disconnected nodes).
 530   if (aContent == mEnd.Container() &&
 531       aInfo.mChangeStart <
 532           *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets)) {
 533     if (aInfo.mDetails && (aContent->GetParentNode() || newStart.Container())) {
 534       // splitText(), aInfo.mDetails->mNextSibling is the new text node
 535       NS_ASSERTION(
 536           aInfo.mDetails->mType == CharacterDataChangeInfo::Details::eSplit,
 537           "only a split can start before the end");
 538       MOZ_ASSERT(
 539           *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) <=
 540               aInfo.mChangeEnd + 1,
 541           "mEnd.Offset() is beyond the end of this node");
 542
 543       const uint32_t newEndOffset{
 544           *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOrInvalidOffsets) -
 545           aInfo.mChangeStart};
 546       newEnd = {aInfo.mDetails->mNextSibling, newEndOffset};
 547
 548       bool isCommonAncestor =
 549           IsInAnySelection() && mStart.Container() == mEnd.Container();
 550       if (isCommonAncestor && !newStart.Container()) {
 551         MOZ_DIAGNOSTIC_ASSERT(mStart.Container() ==
 552                               mRegisteredClosestCommonInclusiveAncestor);
 553         // The split occurs inside the range.
 554         UnregisterClosestCommonInclusiveAncestor();
 555         RegisterClosestCommonInclusiveAncestor(
 556             mStart.Container()->GetParentNode());
 557         newEnd.Container()
 558             ->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
 559       } else if (
 560           mEnd.Container()
 561               ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
 562         newEnd.Container()
 563             ->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
 564       }
 565     } else {
 566       newEnd =
 567           ComputeNewBoundaryWhenBoundaryInsideChangedText(aInfo, mEnd.AsRaw());
 568     }
 569   }
 570
 571   if (aInfo.mDetails &&
 572       aInfo.mDetails->mType == CharacterDataChangeInfo::Details::eMerge) {
 573     MOZ_ASSERT(!newStart.IsSet());
 574     MOZ_ASSERT(!newEnd.IsSet());
 575
 576     RangeBoundariesAndRoot rangeBoundariesAndRoot =
 577         DetermineNewRangeBoundariesAndRootOnCharacterDataMerge(aContent, aInfo);
 578
 579     newStart = rangeBoundariesAndRoot.mStart;
 580     newEnd = rangeBoundariesAndRoot.mEnd;
 581     newRoot = rangeBoundariesAndRoot.mRoot;
 582   }
 583
 584   if (newStart.IsSet() || newEnd.IsSet()) {
 585     if (!newStart.IsSet()) {
 586       newStart.CopyFrom(mStart, RangeBoundaryIsMutationObserved::Yes);
 587     }
 588     if (!newEnd.IsSet()) {
 589       newEnd.CopyFrom(mEnd, RangeBoundaryIsMutationObserved::Yes);
 590     }
 591     DoSetRange(newStart, newEnd, newRoot ? newRoot : mRoot.get(),
 592                !newEnd.Container()->GetParentNode() ||
 593                    !newStart.Container()->GetParentNode());
 594   } else {
 595     nsRange::AssertIfMismatchRootAndRangeBoundaries(
 596         mStart, mEnd, mRoot,
 597         (mStart.IsSet() && !mStart.Container()->GetParentNode()) ||
 598             (mEnd.IsSet() && !mEnd.Container()->GetParentNode()));
 599   }
 600 }
 601
 602 void nsRange::ContentAppended(nsIContent* aFirstNewContent) {
 603   MOZ_ASSERT(mIsPositioned);
 604
 605   nsINode* container = aFirstNewContent->GetParentNode();
 606   MOZ_ASSERT(container);
 607   if (container->IsMaybeSelected() && IsInAnySelection()) {
 608     nsINode* child = aFirstNewContent;
 609     while (child) {
 610       if (!child
 611                ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
 612         MarkDescendants(*child);
 613         child
 614             ->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
 615       }
 616       child = child->GetNextSibling();
 617     }
 618   }
 619
 620   if (mNextStartRef || mNextEndRef) {
 621     // A splitText has occurred, if any mNext*Ref was set, we need to adjust
 622     // the range boundaries.
 623     if (mNextStartRef) {
 624       mStart = {mStart.Container(), mNextStartRef};
 625       MOZ_ASSERT(mNextStartRef == aFirstNewContent);
 626       mNextStartRef = nullptr;
 627     }
 628     if (mNextEndRef) {
 629       mEnd = {mEnd.Container(), mNextEndRef};
 630       MOZ_ASSERT(mNextEndRef == aFirstNewContent);
 631       mNextEndRef = nullptr;
 632     }
 633     DoSetRange(mStart, mEnd, mRoot, true);
 634   } else {
 635     nsRange::AssertIfMismatchRootAndRangeBoundaries(mStart, mEnd, mRoot);
 636   }
 637 }
 638
 639 void nsRange::ContentInserted(nsIContent* aChild) {
 640   MOZ_ASSERT(mIsPositioned);
 641
 642   bool updateBoundaries = false;
 643   nsINode* container = aChild->GetParentNode();
 644   MOZ_ASSERT(container);
 645   RawRangeBoundary newStart(mStart, RangeBoundaryIsMutationObserved::Yes);
 646   RawRangeBoundary newEnd(mEnd, RangeBoundaryIsMutationObserved::Yes);
 647   MOZ_ASSERT(aChild->GetParentNode() == container);
 648
 649   // Invalidate boundary offsets if a child that may have moved them was
 650   // inserted.
 651   if (container == mStart.Container()) {
 652     newStart.InvalidateOffset();
 653     updateBoundaries = true;
 654   }
 655
 656   if (container == mEnd.Container()) {
 657     newEnd.InvalidateOffset();
 658     updateBoundaries = true;
 659   }
 660
 661   if (container->IsMaybeSelected() &&
 662       !aChild
 663            ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
 664     MarkDescendants(*aChild);
 665     aChild->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
 666   }
 667
 668   if (mNextStartRef || mNextEndRef) {
 669     if (mNextStartRef) {
 670       newStart = {mStart.Container(), mNextStartRef};
 671       MOZ_ASSERT(mNextStartRef == aChild);
 672       mNextStartRef = nullptr;
 673     }
 674     if (mNextEndRef) {
 675       newEnd = {mEnd.Container(), mNextEndRef};
 676       MOZ_ASSERT(mNextEndRef == aChild);
 677       mNextEndRef = nullptr;
 678     }
 679
 680     updateBoundaries = true;
 681   }
 682
 683   if (updateBoundaries) {
 684     DoSetRange(newStart, newEnd, mRoot);
 685   } else {
 686     nsRange::AssertIfMismatchRootAndRangeBoundaries(mStart, mEnd, mRoot);
 687   }
 688 }
 689
 690 void nsRange::ContentWillBeRemoved(nsIContent* aChild,
 691                                    const BatchRemovalState*) {
 692   MOZ_ASSERT(mIsPositioned);
 693
 694   nsINode* container = aChild->GetParentNode();
 695   MOZ_ASSERT(container);
 696
 697   nsINode* startContainer = mStart.Container();
 698   nsINode* endContainer = mEnd.Container();
 699
 700   RawRangeBoundary newStart;
 701   RawRangeBoundary newEnd;
 702   Maybe<bool> gravitateStart;
 703   bool gravitateEnd;
 704
 705   // Adjust position if a sibling was removed...
 706   if (container == startContainer) {
 707     // We're only interested if our boundary reference was removed, otherwise
 708     // we can just invalidate the offset.
 709     if (aChild == mStart.Ref()) {
 710       newStart = {container, aChild->GetPreviousSibling()};
 711     } else {
 712       newStart.CopyFrom(mStart, RangeBoundaryIsMutationObserved::Yes);
 713       newStart.InvalidateOffset();
 714     }
 715   } else {
 716     gravitateStart = Some(startContainer->IsInclusiveDescendantOf(aChild));
 717     if (gravitateStart.value()) {
 718       newStart = {container, aChild->GetPreviousSibling()};
 719     }
 720   }
 721
 722   // Do same thing for end boundry.
 723   if (container == endContainer) {
 724     if (aChild == mEnd.Ref()) {
 725       newEnd = {container, aChild->GetPreviousSibling()};
 726     } else {
 727       newEnd.CopyFrom(mEnd, RangeBoundaryIsMutationObserved::Yes);
 728       newEnd.InvalidateOffset();
 729     }
 730   } else {
 731     if (startContainer == endContainer && gravitateStart.isSome()) {
 732       gravitateEnd = gravitateStart.value();
 733     } else {
 734       gravitateEnd = endContainer->IsInclusiveDescendantOf(aChild);
 735     }
 736     if (gravitateEnd) {
 737       newEnd = {container, aChild->GetPreviousSibling()};
 738     }
 739   }
 740
 741   bool newStartIsSet = newStart.IsSet();
 742   bool newEndIsSet = newEnd.IsSet();
 743   if (newStartIsSet || newEndIsSet) {
 744     DoSetRange(
 745         newStartIsSet ? newStart : mStart.AsRaw(),
 746         newEndIsSet ? newEnd : mEnd.AsRaw(), mRoot, false,
 747         // CrossShadowBoundaryRange mutates content
 748         // removal fot itself, so no need for nsRange to do anything with it.
 749         RangeBehaviour::KeepDefaultRangeAndCrossShadowBoundaryRanges);
 750   } else {
 751     nsRange::AssertIfMismatchRootAndRangeBoundaries(mStart, mEnd, mRoot);
 752   }
 753
 754   MOZ_ASSERT(mStart.Ref() != aChild);
 755   MOZ_ASSERT(mEnd.Ref() != aChild);
 756
 757   if (container->IsMaybeSelected() &&
 758       aChild
 759           ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
 760     aChild
 761         ->ClearDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
 762     UnmarkDescendants(*aChild);
 763   }
 764 }
 765
 766 void nsRange::ParentChainChanged(nsIContent* aContent) {
 767   NS_ASSERTION(mRoot == aContent, "Wrong ParentChainChanged notification?");
 768   nsINode* newRoot = RangeUtils::ComputeRootNode(mStart.Container());
 769   NS_ASSERTION(newRoot, "No valid boundary or root found!");
 770   if (newRoot != RangeUtils::ComputeRootNode(mEnd.Container())) {
 771     // Sometimes ordering involved in cycle collection can lead to our
 772     // start parent and/or end parent being disconnected from our root
 773     // without our getting a ContentRemoved notification.
 774     // See bug 846096 for more details.
 775     NS_ASSERTION(mEnd.Container()->IsInNativeAnonymousSubtree(),
 776                  "This special case should happen only with "
 777                  "native-anonymous content");
 778     // When that happens, bail out and set pointers to null; since we're
 779     // in cycle collection and unreachable it shouldn't matter.
 780     Reset();
 781     return;
 782   }
 783   // This is safe without holding a strong ref to self as long as the change
 784   // of mRoot is the last thing in DoSetRange.
 785   DoSetRange(mStart, mEnd, newRoot);
 786 }
 787
 788 bool nsRange::IsShadowIncludingInclusiveDescendantOfCrossBoundaryRangeAncestor(
 789     const nsINode& aContainer) const {
 790   MOZ_ASSERT(mCrossShadowBoundaryRange &&
 791              mCrossShadowBoundaryRange->GetCommonAncestor());
 792   return aContainer.IsShadowIncludingInclusiveDescendantOf(
 793       mCrossShadowBoundaryRange->GetCommonAncestor());
 794 }
 795
 796 bool nsRange::IsPointComparableToRange(const nsINode& aContainer,
 797                                        uint32_t aOffset,
 798                                        bool aAllowCrossShadowBoundary,
 799                                        ErrorResult& aRv) const {
 800   // our range is in a good state?
 801   if (!mIsPositioned) {
 802     aRv.Throw(NS_ERROR_NOT_INITIALIZED);
 803     return false;
 804   }
 805
 806   const bool isContainerInRange =
 807       aContainer.IsInclusiveDescendantOf(mRoot) ||
 808       (aAllowCrossShadowBoundary && mCrossShadowBoundaryRange &&
 809        IsShadowIncludingInclusiveDescendantOfCrossBoundaryRangeAncestor(
 810            aContainer));
 811
 812   if (!isContainerInRange) {
 813     // TODO(emilio): Switch to ThrowWrongDocumentError, but IsPointInRange
 814     // relies on the error code right now in order to suppress the exception.
 815     aRv.Throw(NS_ERROR_DOM_WRONG_DOCUMENT_ERR);
 816     return false;
 817   }
 818
 819   auto chromeOnlyAccess = mStart.Container()->ChromeOnlyAccess();
 820   NS_ASSERTION(chromeOnlyAccess == mEnd.Container()->ChromeOnlyAccess(),
 821                "Start and end of a range must be either both native anonymous "
 822                "content or not.");
 823   if (aContainer.ChromeOnlyAccess() != chromeOnlyAccess) {
 824     aRv.ThrowInvalidNodeTypeError(
 825         "Trying to compare restricted with unrestricted nodes");
 826     return false;
 827   }
 828
 829   if (aContainer.NodeType() == nsINode::DOCUMENT_TYPE_NODE) {
 830     aRv.ThrowInvalidNodeTypeError("Trying to compare with a document");
 831     return false;
 832   }
 833
 834   if (aOffset > aContainer.Length()) {
 835     aRv.ThrowIndexSizeError("Offset is out of bounds");
 836     return false;
 837   }
 838
 839   return true;
 840 }
 841
 842 bool nsRange::IsPointInRange(const nsINode& aContainer, uint32_t aOffset,
 843                              ErrorResult& aRv,
 844                              bool aAllowCrossShadowBoundary) const {
 845   int16_t compareResult =
 846       ComparePoint(aContainer, aOffset, aRv, aAllowCrossShadowBoundary);
 847   // If the node isn't in the range's document, it clearly isn't in the range.
 848   if (aRv.ErrorCodeIs(NS_ERROR_DOM_WRONG_DOCUMENT_ERR)) {
 849     aRv.SuppressException();
 850     return false;
 851   }
 852
 853   return compareResult == 0;
 854 }
 855
 856 int16_t nsRange::ComparePoint(const nsINode& aContainer, uint32_t aOffset,
 857                               ErrorResult& aRv,
 858                               bool aAllowCrossShadowBoundary) const {
 859   if (!IsPointComparableToRange(aContainer, aOffset, aAllowCrossShadowBoundary,
 860                                 aRv)) {
 861     return 0;
 862   }
 863
 864   const RawRangeBoundary point{const_cast<nsINode*>(&aContainer), aOffset};
 865
 866   MOZ_ASSERT(point.IsSetAndValid());
 867
 868   if (Maybe<int32_t> order = nsContentUtils::ComparePoints(
 869           point, aAllowCrossShadowBoundary ? MayCrossShadowBoundaryStartRef()
 870                                            : StartRef());
 871       order && *order <= 0) {
 872     return int16_t(*order);
 873   }
 874   if (Maybe<int32_t> order = nsContentUtils::ComparePoints(
 875           aAllowCrossShadowBoundary ? MayCrossShadowBoundaryEndRef() : EndRef(),
 876           point);
 877       order && *order == -1) {
 878     return 1;
 879   }
 880   return 0;
 881 }
 882
 883 bool nsRange::IntersectsNode(nsINode& aNode, ErrorResult& aRv) {
 884   if (!mIsPositioned) {
 885     aRv.Throw(NS_ERROR_NOT_INITIALIZED);
 886     return false;
 887   }
 888
 889   nsINode* parent = aNode.GetParentNode();
 890   if (!parent) {
 891     // |parent| is null, so |node|'s root is |node| itself.
 892     return GetRoot() == &aNode;
 893   }
 894
 895   const Maybe<uint32_t> nodeIndex = parent->ComputeIndexOf(&aNode);
 896   if (nodeIndex.isNothing()) {
 897     return false;
 898   }
 899
 900   if (!IsPointComparableToRange(*parent, *nodeIndex,
 901                                 false /* aAllowCrossShadowBoundary */,
 902                                 IgnoreErrors())) {
 903     return false;
 904   }
 905
 906   const Maybe<int32_t> startOrder = nsContentUtils::ComparePoints(
 907       mStart.Container(),
 908       *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets), parent,
 909       *nodeIndex + 1u);
 910   if (startOrder && (*startOrder < 0)) {
 911     const Maybe<int32_t> endOrder = nsContentUtils::ComparePoints(
 912         parent, *nodeIndex, mEnd.Container(),
 913         *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets));
 914     return endOrder && (*endOrder < 0);
 915   }
 916
 917   return false;
 918 }
 919
 920 void nsRange::NotifySelectionListenersAfterRangeSet() {
 921   if (mSelections.IsEmpty()) {
 922     return;
 923   }
 924
 925   // Our internal code should not move focus with using this instance while
 926   // it's calling Selection::NotifySelectionListeners() which may move focus
 927   // or calls selection listeners.  So, let's set mCalledByJS to false here
 928   // since non-*JS() methods don't set it to false.
 929   AutoCalledByJSRestore calledByJSRestorer(*this);
 930   mCalledByJS = false;
 931
 932   // If this instance is not a proper range for selection, we need to remove
 933   // this from selections.
 934   const Document* const docForSelf =
 935       mStart.Container() ? mStart.Container()->GetComposedDoc() : nullptr;
 936   const nsFrameSelection* const frameSelection =
 937       mSelections[0]->GetFrameSelection();
 938   const Document* const docForSelection =
 939       frameSelection && frameSelection->GetPresShell()
 940           ? frameSelection->GetPresShell()->GetDocument()
 941           : nullptr;
 942   if (!IsPositioned() || docForSelf != docForSelection) {
 943     // XXX Why Selection::RemoveRangeAndUnselectFramesAndNotifyListeners() does
 944     // not set whether the caller is JS or not?
 945     if (IsPartOfOneSelectionOnly()) {
 946       RefPtr<Selection> selection = mSelections[0].get();
 947       selection->RemoveRangeAndUnselectFramesAndNotifyListeners(*this,
 948                                                                 IgnoreErrors());
 949     } else {
 950       nsTArray<WeakPtr<Selection>> copiedSelections = mSelections.Clone();
 951       for (const auto& weakSelection : copiedSelections) {
 952         RefPtr<Selection> selection = weakSelection.get();
 953         if (MOZ_LIKELY(selection)) {
 954           selection->RemoveRangeAndUnselectFramesAndNotifyListeners(
 955               *this, IgnoreErrors());
 956         }
 957       }
 958     }
 959     // FYI: NotifySelectionListeners() should be called by
 960     // RemoveRangeAndUnselectFramesAndNotifyListeners() if it's required.
 961     // Therefore, we need to do nothing anymore.
 962     return;
 963   }
 964
 965   // Notify all Selections. This may modify the range,
 966   // remove it from the selection, or the selection itself may have gone after
 967   // the call. Also, new selections may be added.
 968   // To ensure that listeners are notified for all *current* selections,
 969   // create a copy of the list of selections and use that for iterating. This
 970   // way selections can be added or removed safely during iteration.
 971   // To save allocation cost, the copy is only created if there is more than
 972   // one Selection present  (which will barely ever be the case).
 973   if (IsPartOfOneSelectionOnly()) {
 974     RefPtr<Selection> selection = mSelections[0].get();
 975 #ifdef ACCESSIBILITY
 976     a11y::SelectionManager::SelectionRangeChanged(selection->GetType(), *this);
 977 #endif
 978     selection->NotifySelectionListeners(calledByJSRestorer.SavedValue());
 979   } else {
 980     nsTArray<WeakPtr<Selection>> copiedSelections = mSelections.Clone();
 981     for (const auto& weakSelection : copiedSelections) {
 982       RefPtr<Selection> selection = weakSelection.get();
 983       if (MOZ_LIKELY(selection)) {
 984 #ifdef ACCESSIBILITY
 985         a11y::SelectionManager::SelectionRangeChanged(selection->GetType(),
 986                                                       *this);
 987 #endif
 988         selection->NotifySelectionListeners(calledByJSRestorer.SavedValue());
 989       }
 990     }
 991   }
 992 }
 993
 994 /******************************************************
 995  * Private helper routines
 996  ******************************************************/
 997
 998 // static
 999 template <typename SPT, typename SRT, typename EPT, typename ERT>
1000 void nsRange::AssertIfMismatchRootAndRangeBoundaries(
1001     const RangeBoundaryBase<SPT, SRT>& aStartBoundary,
1002     const RangeBoundaryBase<EPT, ERT>& aEndBoundary, const nsINode* aRootNode,
1003     bool aNotInsertedYet /* = false */) {
1004 #ifdef DEBUG
1005   if (!aRootNode) {
1006     MOZ_ASSERT(!aStartBoundary.IsSet());
1007     MOZ_ASSERT(!aEndBoundary.IsSet());
1008     return;
1009   }
1010
1011   MOZ_ASSERT(aStartBoundary.IsSet());
1012   MOZ_ASSERT(aEndBoundary.IsSet());
1013   if (!aNotInsertedYet) {
1014     // Compute temporary root for given range boundaries.  If a range in native
1015     // anonymous subtree is being removed, tempRoot may return the fragment's
1016     // root content, but it shouldn't be used for new root node because the node
1017     // may be bound to the root element again.
1018     nsINode* tempRoot = RangeUtils::ComputeRootNode(aStartBoundary.Container());
1019     // The new range should be in the temporary root node at least.
1020     MOZ_ASSERT(tempRoot ==
1021                RangeUtils::ComputeRootNode(aEndBoundary.Container()));
1022     MOZ_ASSERT(aStartBoundary.Container()->IsInclusiveDescendantOf(tempRoot));
1023     MOZ_ASSERT(aEndBoundary.Container()->IsInclusiveDescendantOf(tempRoot));
1024     // If the new range is not disconnected or not in native anonymous subtree,
1025     // the temporary root must be same as the new root node.  Otherwise,
1026     // aRootNode should be the parent of root of the NAC (e.g., `<input>` if the
1027     // range is in NAC under `<input>`), but tempRoot is now root content node
1028     // of the disconnected subtree (e.g., `<div>` element in `<input>` element).
1029     const bool tempRootIsDisconnectedNAC =
1030         tempRoot->IsInNativeAnonymousSubtree() && !tempRoot->GetParentNode();
1031     MOZ_ASSERT_IF(!tempRootIsDisconnectedNAC, tempRoot == aRootNode);
1032   }
1033   MOZ_ASSERT(aRootNode->IsDocument() || aRootNode->IsAttr() ||
1034              aRootNode->IsDocumentFragment() || aRootNode->IsContent());
1035 #endif  // #ifdef DEBUG
1036 }
1037
1038 // It's important that all setting of the range start/end points
1039 // go through this function, which will do all the right voodoo
1040 // for content notification of range ownership.
1041 // Calling DoSetRange with either parent argument null will collapse
1042 // the range to have both endpoints point to the other node
1043 template <typename SPT, typename SRT, typename EPT, typename ERT>
1044 void nsRange::
1045     DoSetRange(const RangeBoundaryBase<SPT, SRT>& aStartBoundary,
1046                const RangeBoundaryBase<EPT, ERT>& aEndBoundary,
1047                nsINode* aRootNode,
1048                bool aNotInsertedYet /* = false */, RangeBehaviour aRangeBehaviour /* = CollapseDefaultRangeAndCrossShadowBoundaryRanges */) {
1049   mIsPositioned = aStartBoundary.IsSetAndValid() &&
1050                   aEndBoundary.IsSetAndValid() && aRootNode;
1051   MOZ_ASSERT_IF(!mIsPositioned, !aStartBoundary.IsSet());
1052   MOZ_ASSERT_IF(!mIsPositioned, !aEndBoundary.IsSet());
1053   MOZ_ASSERT_IF(!mIsPositioned, !aRootNode);
1054
1055   nsRange::AssertIfMismatchRootAndRangeBoundaries(aStartBoundary, aEndBoundary,
1056                                                   aRootNode, aNotInsertedYet);
1057
1058   if (mRoot != aRootNode) {
1059     if (mRoot) {
1060       mRoot->RemoveMutationObserver(this);
1061     }
1062     if (aRootNode) {
1063       aRootNode->AddMutationObserver(this);
1064     }
1065   }
1066   bool checkCommonAncestor =
1067       (mStart.Container() != aStartBoundary.Container() ||
1068        mEnd.Container() != aEndBoundary.Container()) &&
1069       IsInAnySelection() && !aNotInsertedYet;
1070
1071   // GetClosestCommonInclusiveAncestor is unreliable while we're unlinking
1072   // (could return null if our start/end have already been unlinked), so make
1073   // sure to not use it here to determine our "old" current ancestor.
1074   mStart.CopyFrom(aStartBoundary, RangeBoundaryIsMutationObserved::Yes);
1075   mEnd.CopyFrom(aEndBoundary, RangeBoundaryIsMutationObserved::Yes);
1076
1077   if (aRangeBehaviour ==
1078       RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges) {
1079     ResetCrossShadowBoundaryRange();
1080   }
1081
1082   if (checkCommonAncestor) {
1083     UpdateCommonAncestorIfNecessary();
1084   }
1085
1086   // This needs to be the last thing this function does, other than notifying
1087   // selection listeners. See comment in ParentChainChanged.
1088   if (mRoot != aRootNode) {
1089     mRoot = aRootNode;
1090   }
1091
1092   // Notify any selection listeners. This has to occur last because otherwise
1093   // the world could be observed by a selection listener while the range was in
1094   // an invalid state. So we run it off of a script runner to ensure it runs
1095   // after the mutation observers have finished running.
1096   if (!mSelections.IsEmpty()) {
1097     if (MOZ_LOG_TEST(sSelectionAPILog, LogLevel::Info)) {
1098       for (const auto& selection : mSelections) {
1099         if (selection && selection->Type() == SelectionType::eNormal) {
1100           LogSelectionAPI(selection, __FUNCTION__, "aStartBoundary",
1101                           aStartBoundary, "aEndBoundary", aEndBoundary,
1102                           "aNotInsertedYet", aNotInsertedYet);
1103           LogStackForSelectionAPI();
1104         }
1105       }
1106     }
1107     nsContentUtils::AddScriptRunner(
1108         NewRunnableMethod("NotifySelectionListenersAfterRangeSet", this,
1109                           &nsRange::NotifySelectionListenersAfterRangeSet));
1110   }
1111 }
1112
1113 void nsRange::Reset() {
1114   DoSetRange(RawRangeBoundary(), RawRangeBoundary(), nullptr);
1115 }
1116
1117 /******************************************************
1118  * public functionality
1119  ******************************************************/
1120
1121 void nsRange::SetStartJS(nsINode& aNode, uint32_t aOffset, ErrorResult& aErr) {
1122   AutoCalledByJSRestore calledByJSRestorer(*this);
1123   mCalledByJS = true;
1124   SetStart(aNode, aOffset, aErr);
1125 }
1126
1127 bool nsRange::CanAccess(const nsINode& aNode) const {
1128   if (nsContentUtils::LegacyIsCallerNativeCode()) {
1129     return true;
1130   }
1131   return nsContentUtils::CanCallerAccess(&aNode);
1132 }
1133
1134 void nsRange::SetStart(
1135     nsINode& aNode, uint32_t aOffset, ErrorResult& aRv,
1136     AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
1137   if (!CanAccess(aNode)) {
1138     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
1139     return;
1140   }
1141
1142   AutoInvalidateSelection atEndOfBlock(this);
1143   SetStart(RawRangeBoundary(&aNode, aOffset), aRv, aAllowCrossShadowBoundary);
1144 }
1145
1146 void nsRange::SetStart(
1147     const RawRangeBoundary& aPoint, ErrorResult& aRv,
1148     AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
1149   nsINode* newRoot = RangeUtils::ComputeRootNode(aPoint.Container());
1150   if (!newRoot) {
1151     aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
1152     return;
1153   }
1154
1155   if (!aPoint.IsSetAndValid()) {
1156     aRv.Throw(NS_ERROR_DOM_INDEX_SIZE_ERR);
1157     return;
1158   }
1159
1160   RangeBehaviour behaviour =
1161       GetRangeBehaviour(this, newRoot, aPoint, true /* aIsSetStart= */,
1162                         aAllowCrossShadowBoundary);
1163
1164   switch (behaviour) {
1165     case RangeBehaviour::KeepDefaultRangeAndCrossShadowBoundaryRanges:
1166       // EndRef(..) may be same as mStart or not, depends on
1167       // the value of mCrossShadowBoundaryRange->mEnd, We need to update
1168       // mCrossShadowBoundaryRange and the default boundaries separately
1169       if (aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes) {
1170         if (MayCrossShadowBoundaryEndRef() != mEnd) {
1171           CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
1172               aPoint, MayCrossShadowBoundaryEndRef());
1173         } else {
1174           // The normal range is good enough for this case, just use that.
1175           ResetCrossShadowBoundaryRange();
1176         }
1177       }
1178       DoSetRange(aPoint, mEnd, mRoot, false, behaviour);
1179       break;
1180     case RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges:
1181       DoSetRange(aPoint, aPoint, newRoot, false, behaviour);
1182       break;
1183     case RangeBehaviour::CollapseDefaultRange:
1184       MOZ_ASSERT(aAllowCrossShadowBoundary ==
1185                  AllowRangeCrossShadowBoundary::Yes);
1186       CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
1187           aPoint, MayCrossShadowBoundaryEndRef());
1188       DoSetRange(aPoint, aPoint, newRoot, false, behaviour);
1189       break;
1190     case RangeBehaviour::MergeDefaultRangeAndCrossShadowBoundaryRanges:
1191       DoSetRange(aPoint, MayCrossShadowBoundaryEndRef(), newRoot, false,
1192                  behaviour);
1193       ResetCrossShadowBoundaryRange();
1194       break;
1195     default:
1196       MOZ_ASSERT_UNREACHABLE();
1197   }
1198 }
1199
1200 void nsRange::SetStartAllowCrossShadowBoundary(nsINode& aNode, uint32_t aOffset,
1201                                                ErrorResult& aErr) {
1202   AutoCalledByJSRestore calledByJSRestorer(*this);
1203   mCalledByJS = true;
1204   SetStart(aNode, aOffset, aErr, AllowRangeCrossShadowBoundary::Yes);
1205 }
1206
1207 void nsRange::SetStartBeforeJS(nsINode& aNode, ErrorResult& aErr) {
1208   AutoCalledByJSRestore calledByJSRestorer(*this);
1209   mCalledByJS = true;
1210   SetStartBefore(aNode, aErr);
1211 }
1212
1213 void nsRange::SetStartBefore(
1214     nsINode& aNode, ErrorResult& aRv,
1215     AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
1216   if (!CanAccess(aNode)) {
1217     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
1218     return;
1219   }
1220
1221   AutoInvalidateSelection atEndOfBlock(this);
1222   // If the node is being removed from its parent, GetRawRangeBoundaryBefore()
1223   // returns unset instance.  Then, SetStart() will throw
1224   // NS_ERROR_DOM_INVALID_NODE_TYPE_ERR.
1225   SetStart(RangeUtils::GetRawRangeBoundaryBefore(&aNode), aRv,
1226            aAllowCrossShadowBoundary);
1227 }
1228
1229 void nsRange::SetStartAfterJS(nsINode& aNode, ErrorResult& aErr) {
1230   AutoCalledByJSRestore calledByJSRestorer(*this);
1231   mCalledByJS = true;
1232   SetStartAfter(aNode, aErr);
1233 }
1234
1235 void nsRange::SetStartAfter(nsINode& aNode, ErrorResult& aRv) {
1236   if (!CanAccess(aNode)) {
1237     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
1238     return;
1239   }
1240
1241   AutoInvalidateSelection atEndOfBlock(this);
1242   // If the node is being removed from its parent, GetRawRangeBoundaryAfter()
1243   // returns unset instance.  Then, SetStart() will throw
1244   // NS_ERROR_DOM_INVALID_NODE_TYPE_ERR.
1245   SetStart(RangeUtils::GetRawRangeBoundaryAfter(&aNode), aRv);
1246 }
1247
1248 void nsRange::SetEndJS(nsINode& aNode, uint32_t aOffset, ErrorResult& aErr) {
1249   AutoCalledByJSRestore calledByJSRestorer(*this);
1250   mCalledByJS = true;
1251   SetEnd(aNode, aOffset, aErr);
1252 }
1253
1254 void nsRange::SetEnd(nsINode& aNode, uint32_t aOffset, ErrorResult& aRv,
1255                      AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
1256   if (!CanAccess(aNode)) {
1257     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
1258     return;
1259   }
1260   AutoInvalidateSelection atEndOfBlock(this);
1261   SetEnd(RawRangeBoundary(&aNode, aOffset), aRv, aAllowCrossShadowBoundary);
1262 }
1263
1264 void nsRange::SetEnd(const RawRangeBoundary& aPoint, ErrorResult& aRv,
1265                      AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
1266   nsINode* newRoot = RangeUtils::ComputeRootNode(aPoint.Container());
1267   if (!newRoot) {
1268     aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
1269     return;
1270   }
1271
1272   if (!aPoint.IsSetAndValid()) {
1273     aRv.Throw(NS_ERROR_DOM_INDEX_SIZE_ERR);
1274     return;
1275   }
1276
1277   RangeBehaviour policy =
1278       GetRangeBehaviour(this, newRoot, aPoint, false /* aIsStartStart */,
1279                         aAllowCrossShadowBoundary);
1280
1281   switch (policy) {
1282     case RangeBehaviour::KeepDefaultRangeAndCrossShadowBoundaryRanges:
1283       // StartRef(..) may be same as mStart or not, depends on
1284       // the value of mCrossShadowBoundaryRange->mStart, so we need to update
1285       // mCrossShadowBoundaryRange and the default boundaries separately
1286       if (aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes) {
1287         if (MayCrossShadowBoundaryStartRef() != mStart) {
1288           CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
1289               MayCrossShadowBoundaryStartRef(), aPoint);
1290         } else {
1291           // The normal range is good enough for this case, just use that.
1292           ResetCrossShadowBoundaryRange();
1293         }
1294       }
1295       DoSetRange(mStart, aPoint, mRoot, false, policy);
1296       break;
1297     case RangeBehaviour::CollapseDefaultRangeAndCrossShadowBoundaryRanges:
1298       DoSetRange(aPoint, aPoint, newRoot, false, policy);
1299       break;
1300     case RangeBehaviour::CollapseDefaultRange:
1301       MOZ_ASSERT(aAllowCrossShadowBoundary ==
1302                  AllowRangeCrossShadowBoundary::Yes);
1303       CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
1304           MayCrossShadowBoundaryStartRef(), aPoint);
1305       DoSetRange(aPoint, aPoint, newRoot, false, policy);
1306       break;
1307     case RangeBehaviour::MergeDefaultRangeAndCrossShadowBoundaryRanges:
1308       DoSetRange(MayCrossShadowBoundaryStartRef(), aPoint, newRoot, false,
1309                  policy);
1310       ResetCrossShadowBoundaryRange();
1311       break;
1312     default:
1313       MOZ_ASSERT_UNREACHABLE();
1314   }
1315 }
1316
1317 void nsRange::SetEndAllowCrossShadowBoundary(nsINode& aNode, uint32_t aOffset,
1318                                              ErrorResult& aErr) {
1319   AutoCalledByJSRestore calledByJSRestorer(*this);
1320   mCalledByJS = true;
1321   SetEnd(aNode, aOffset, aErr,
1322          AllowRangeCrossShadowBoundary::Yes /* aAllowCrossShadowBoundary */);
1323 }
1324
1325 void nsRange::SelectNodesInContainer(nsINode* aContainer,
1326                                      nsIContent* aStartContent,
1327                                      nsIContent* aEndContent) {
1328   MOZ_ASSERT(aContainer);
1329   MOZ_ASSERT(aContainer->ComputeIndexOf(aStartContent).valueOr(0) <=
1330              aContainer->ComputeIndexOf(aEndContent).valueOr(0));
1331   MOZ_ASSERT(aStartContent &&
1332              aContainer->ComputeIndexOf(aStartContent).isSome());
1333   MOZ_ASSERT(aEndContent && aContainer->ComputeIndexOf(aEndContent).isSome());
1334
1335   nsINode* newRoot = RangeUtils::ComputeRootNode(aContainer);
1336   MOZ_ASSERT(newRoot);
1337   if (!newRoot) {
1338     return;
1339   }
1340
1341   RawRangeBoundary start(aContainer, aStartContent->GetPreviousSibling());
1342   RawRangeBoundary end(aContainer, aEndContent);
1343   DoSetRange(start, end, newRoot);
1344 }
1345
1346 void nsRange::SetEndBeforeJS(nsINode& aNode, ErrorResult& aErr) {
1347   AutoCalledByJSRestore calledByJSRestorer(*this);
1348   mCalledByJS = true;
1349   SetEndBefore(aNode, aErr);
1350 }
1351
1352 void nsRange::SetEndBefore(
1353     nsINode& aNode, ErrorResult& aRv,
1354     AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
1355   if (!CanAccess(aNode)) {
1356     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
1357     return;
1358   }
1359
1360   AutoInvalidateSelection atEndOfBlock(this);
1361   // If the node is being removed from its parent, GetRawRangeBoundaryBefore()
1362   // returns unset instance.  Then, SetEnd() will throw
1363   // NS_ERROR_DOM_INVALID_NODE_TYPE_ERR.
1364   SetEnd(RangeUtils::GetRawRangeBoundaryBefore(&aNode), aRv,
1365          aAllowCrossShadowBoundary);
1366 }
1367
1368 void nsRange::SetEndAfterJS(nsINode& aNode, ErrorResult& aErr) {
1369   AutoCalledByJSRestore calledByJSRestorer(*this);
1370   mCalledByJS = true;
1371   SetEndAfter(aNode, aErr);
1372 }
1373
1374 void nsRange::SetEndAfter(nsINode& aNode, ErrorResult& aRv) {
1375   if (!CanAccess(aNode)) {
1376     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
1377     return;
1378   }
1379
1380   AutoInvalidateSelection atEndOfBlock(this);
1381   // If the node is being removed from its parent, GetRawRangeBoundaryAfter()
1382   // returns unset instance.  Then, SetEnd() will throw
1383   // NS_ERROR_DOM_INVALID_NODE_TYPE_ERR.
1384   SetEnd(RangeUtils::GetRawRangeBoundaryAfter(&aNode), aRv);
1385 }
1386
1387 void nsRange::Collapse(bool aToStart) {
1388   if (!mIsPositioned) return;
1389
1390   AutoInvalidateSelection atEndOfBlock(this);
1391   if (aToStart) {
1392     DoSetRange(mStart, mStart, mRoot);
1393   } else {
1394     DoSetRange(mEnd, mEnd, mRoot);
1395   }
1396 }
1397
1398 void nsRange::CollapseJS(bool aToStart) {
1399   AutoCalledByJSRestore calledByJSRestorer(*this);
1400   mCalledByJS = true;
1401   Collapse(aToStart);
1402 }
1403
1404 void nsRange::SelectNodeJS(nsINode& aNode, ErrorResult& aErr) {
1405   AutoCalledByJSRestore calledByJSRestorer(*this);
1406   mCalledByJS = true;
1407   SelectNode(aNode, aErr);
1408 }
1409
1410 void nsRange::SelectNode(nsINode& aNode, ErrorResult& aRv) {
1411   if (!CanAccess(aNode)) {
1412     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
1413     return;
1414   }
1415
1416   nsINode* container = aNode.GetParentNode();
1417   nsINode* newRoot = RangeUtils::ComputeRootNode(container);
1418   if (!newRoot) {
1419     aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
1420     return;
1421   }
1422
1423   const Maybe<uint32_t> index = container->ComputeIndexOf(&aNode);
1424   // MOZ_ASSERT(index.isSome());
1425   // We need to compute the index here unfortunately, because, while we have
1426   // support for XBL, |container| may be the node's binding parent without
1427   // actually containing it.
1428   if (MOZ_UNLIKELY(NS_WARN_IF(index.isNothing()))) {
1429     aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
1430     return;
1431   }
1432
1433   AutoInvalidateSelection atEndOfBlock(this);
1434   DoSetRange(RawRangeBoundary{container, *index},
1435              RawRangeBoundary{container, *index + 1u}, newRoot);
1436 }
1437
1438 void nsRange::SelectNodeContentsJS(nsINode& aNode, ErrorResult& aErr) {
1439   AutoCalledByJSRestore calledByJSRestorer(*this);
1440   mCalledByJS = true;
1441   SelectNodeContents(aNode, aErr);
1442 }
1443
1444 void nsRange::SelectNodeContents(nsINode& aNode, ErrorResult& aRv) {
1445   if (!CanAccess(aNode)) {
1446     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
1447     return;
1448   }
1449
1450   nsINode* newRoot = RangeUtils::ComputeRootNode(&aNode);
1451   if (!newRoot) {
1452     aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
1453     return;
1454   }
1455
1456   AutoInvalidateSelection atEndOfBlock(this);
1457   DoSetRange(RawRangeBoundary(&aNode, 0u),
1458              RawRangeBoundary(&aNode, aNode.Length()), newRoot);
1459 }
1460
1461 // The Subtree Content Iterator only returns subtrees that are
1462 // completely within a given range. It doesn't return a CharacterData
1463 // node that contains either the start or end point of the range.,
1464 // nor does it return element nodes when nothing in the element is selected.
1465 // We need an iterator that will also include these start/end points
1466 // so that our methods/algorithms aren't cluttered with special
1467 // case code that tries to include these points while iterating.
1468 //
1469 // The RangeSubtreeIterator class mimics the ContentSubtreeIterator
1470 // methods we need, so should the Content Iterator support the
1471 // start/end points in the future, we can switchover relatively
1472 // easy.
1473
1474 class MOZ_STACK_CLASS RangeSubtreeIterator {
1475  private:
1476   enum RangeSubtreeIterState { eDone = 0, eUseStart, eUseIterator, eUseEnd };
1477
1478   Maybe<ContentSubtreeIterator> mSubtreeIter;
1479   RangeSubtreeIterState mIterState;
1480
1481   nsCOMPtr<nsINode> mStart;
1482   nsCOMPtr<nsINode> mEnd;
1483
1484  public:
1485   RangeSubtreeIterator() : mIterState(eDone) {}
1486   ~RangeSubtreeIterator() = default;
1487
1488   nsresult Init(nsRange* aRange, AllowRangeCrossShadowBoundary =
1489                                      AllowRangeCrossShadowBoundary::No);
1490   already_AddRefed<nsINode> GetCurrentNode();
1491   void First();
1492   void Last();
1493   void Next();
1494   void Prev();
1495
1496   bool IsDone() { return mIterState == eDone; }
1497 };
1498
1499 nsresult RangeSubtreeIterator::Init(
1500     nsRange* aRange, AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) {
1501   mIterState = eDone;
1502   if (aRange->AreNormalRangeAndCrossShadowBoundaryRangeCollapsed()) {
1503     return NS_OK;
1504   }
1505
1506   // Grab the start point of the range and QI it to
1507   // a CharacterData pointer. If it is CharacterData store
1508   // a pointer to the node.
1509
1510   if (!aRange->IsPositioned()) {
1511     return NS_ERROR_FAILURE;
1512   }
1513
1514   nsINode* node = aRange->GetMayCrossShadowBoundaryStartContainer();
1515   if (NS_WARN_IF(!node)) {
1516     return NS_ERROR_FAILURE;
1517   }
1518
1519   if (node->IsCharacterData() ||
1520       (node->IsElement() && node->AsElement()->GetChildCount() ==
1521                                 aRange->MayCrossShadowBoundaryStartOffset())) {
1522     mStart = node;
1523   }
1524
1525   // Grab the end point of the range and QI it to
1526   // a CharacterData pointer. If it is CharacterData store
1527   // a pointer to the node.
1528
1529   node = aRange->GetMayCrossShadowBoundaryEndContainer();
1530   if (NS_WARN_IF(!node)) {
1531     return NS_ERROR_FAILURE;
1532   }
1533
1534   if (node->IsCharacterData() ||
1535       (node->IsElement() && aRange->MayCrossShadowBoundaryEndOffset() == 0)) {
1536     mEnd = node;
1537   }
1538
1539   if (mStart && mStart == mEnd) {
1540     // The range starts and stops in the same CharacterData
1541     // node. Null out the end pointer so we only visit the
1542     // node once!
1543
1544     mEnd = nullptr;
1545   } else {
1546     // Now create a Content Subtree Iterator to be used
1547     // for the subtrees between the end points!
1548
1549     mSubtreeIter.emplace();
1550
1551     nsresult res =
1552         aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes
1553             ? mSubtreeIter->InitWithAllowCrossShadowBoundary(aRange)
1554             : mSubtreeIter->Init(aRange);
1555     if (NS_FAILED(res)) return res;
1556
1557     if (mSubtreeIter->IsDone()) {
1558       // The subtree iterator thinks there's nothing
1559       // to iterate over, so just free it up so we
1560       // don't accidentally call into it.
1561
1562       mSubtreeIter.reset();
1563     }
1564   }
1565
1566   // Initialize the iterator by calling First().
1567   // Note that we are ignoring the return value on purpose!
1568
1569   First();
1570
1571   return NS_OK;
1572 }
1573
1574 already_AddRefed<nsINode> RangeSubtreeIterator::GetCurrentNode() {
1575   nsCOMPtr<nsINode> node;
1576
1577   if (mIterState == eUseStart && mStart) {
1578     node = mStart;
1579   } else if (mIterState == eUseEnd && mEnd) {
1580     node = mEnd;
1581   } else if (mIterState == eUseIterator && mSubtreeIter) {
1582     node = mSubtreeIter->GetCurrentNode();
1583   }
1584
1585   return node.forget();
1586 }
1587
1588 void RangeSubtreeIterator::First() {
1589   if (mStart)
1590     mIterState = eUseStart;
1591   else if (mSubtreeIter) {
1592     mSubtreeIter->First();
1593
1594     mIterState = eUseIterator;
1595   } else if (mEnd)
1596     mIterState = eUseEnd;
1597   else
1598     mIterState = eDone;
1599 }
1600
1601 void RangeSubtreeIterator::Last() {
1602   if (mEnd)
1603     mIterState = eUseEnd;
1604   else if (mSubtreeIter) {
1605     mSubtreeIter->Last();
1606
1607     mIterState = eUseIterator;
1608   } else if (mStart)
1609     mIterState = eUseStart;
1610   else
1611     mIterState = eDone;
1612 }
1613
1614 void RangeSubtreeIterator::Next() {
1615   if (mIterState == eUseStart) {
1616     if (mSubtreeIter) {
1617       mSubtreeIter->First();
1618
1619       mIterState = eUseIterator;
1620     } else if (mEnd)
1621       mIterState = eUseEnd;
1622     else
1623       mIterState = eDone;
1624   } else if (mIterState == eUseIterator) {
1625     mSubtreeIter->Next();
1626
1627     if (mSubtreeIter->IsDone()) {
1628       if (mEnd)
1629         mIterState = eUseEnd;
1630       else
1631         mIterState = eDone;
1632     }
1633   } else
1634     mIterState = eDone;
1635 }
1636
1637 void RangeSubtreeIterator::Prev() {
1638   if (mIterState == eUseEnd) {
1639     if (mSubtreeIter) {
1640       mSubtreeIter->Last();
1641
1642       mIterState = eUseIterator;
1643     } else if (mStart)
1644       mIterState = eUseStart;
1645     else
1646       mIterState = eDone;
1647   } else if (mIterState == eUseIterator) {
1648     mSubtreeIter->Prev();
1649
1650     if (mSubtreeIter->IsDone()) {
1651       if (mStart)
1652         mIterState = eUseStart;
1653       else
1654         mIterState = eDone;
1655     }
1656   } else
1657     mIterState = eDone;
1658 }
1659
1660 // CollapseRangeAfterDelete() is a utility method that is used by
1661 // DeleteContents() and ExtractContents() to collapse the range
1662 // in the correct place, under the range's root container (the
1663 // range end points common container) as outlined by the Range spec:
1664 //
1665 // http://www.w3.org/TR/2000/REC-DOM-Level-2-Traversal-Range-20001113/ranges.html
1666 // The assumption made by this method is that the delete or extract
1667 // has been done already, and left the range in a state where there is
1668 // no content between the 2 end points.
1669
1670 static nsresult CollapseRangeAfterDelete(nsRange* aRange) {
1671   NS_ENSURE_ARG_POINTER(aRange);
1672
1673   // Check if range gravity took care of collapsing the range for us!
1674   if (aRange->Collapsed()) {
1675     // aRange is collapsed so there's nothing for us to do.
1676     //
1677     // There are 2 possible scenarios here:
1678     //
1679     // 1. aRange could've been collapsed prior to the delete/extract,
1680     //    which would've resulted in nothing being removed, so aRange
1681     //    is already where it should be.
1682     //
1683     // 2. Prior to the delete/extract, aRange's start and end were in
1684     //    the same container which would mean everything between them
1685     //    was removed, causing range gravity to collapse the range.
1686
1687     return NS_OK;
1688   }
1689
1690   // aRange isn't collapsed so figure out the appropriate place to collapse!
1691   // First get both end points and their common ancestor.
1692
1693   if (!aRange->IsPositioned()) {
1694     return NS_ERROR_NOT_INITIALIZED;
1695   }
1696
1697   nsCOMPtr<nsINode> commonAncestor =
1698       aRange->GetClosestCommonInclusiveAncestor();
1699
1700   nsCOMPtr<nsINode> startContainer = aRange->GetStartContainer();
1701   nsCOMPtr<nsINode> endContainer = aRange->GetEndContainer();
1702
1703   // Collapse to one of the end points if they are already in the
1704   // commonAncestor. This should work ok since this method is called
1705   // immediately after a delete or extract that leaves no content
1706   // between the 2 end points!
1707
1708   if (startContainer == commonAncestor) {
1709     aRange->Collapse(true);
1710     return NS_OK;
1711   }
1712   if (endContainer == commonAncestor) {
1713     aRange->Collapse(false);
1714     return NS_OK;
1715   }
1716
1717   // End points are at differing levels. We want to collapse to the
1718   // point that is between the 2 subtrees that contain each point,
1719   // under the common ancestor.
1720
1721   nsCOMPtr<nsINode> nodeToSelect(startContainer);
1722
1723   while (nodeToSelect) {
1724     nsCOMPtr<nsINode> parent = nodeToSelect->GetParentNode();
1725     if (parent == commonAncestor) break;  // We found the nodeToSelect!
1726
1727     nodeToSelect = parent;
1728   }
1729
1730   if (!nodeToSelect) return NS_ERROR_FAILURE;  // This should never happen!
1731
1732   ErrorResult error;
1733   aRange->SelectNode(*nodeToSelect, error);
1734   if (error.Failed()) {
1735     return error.StealNSResult();
1736   }
1737
1738   aRange->Collapse(false);
1739   return NS_OK;
1740 }
1741
1742 NS_IMETHODIMP
1743 PrependChild(nsINode* aContainer, nsINode* aChild) {
1744   nsCOMPtr<nsINode> first = aContainer->GetFirstChild();
1745   ErrorResult rv;
1746   aContainer->InsertBefore(*aChild, first, rv);
1747   return rv.StealNSResult();
1748 }
1749
1750 // Helper function for CutContents, making sure that the current node wasn't
1751 // removed by mutation events (bug 766426)
1752 static bool ValidateCurrentNode(nsRange* aRange, RangeSubtreeIterator& aIter) {
1753   bool before, after;
1754   nsCOMPtr<nsINode> node = aIter.GetCurrentNode();
1755   if (!node) {
1756     // We don't have to worry that the node was removed if it doesn't exist,
1757     // e.g., the iterator is done.
1758     return true;
1759   }
1760
1761   nsresult rv = RangeUtils::CompareNodeToRange(node, aRange, &before, &after);
1762   if (NS_WARN_IF(NS_FAILED(rv))) {
1763     return false;
1764   }
1765
1766   if (before || after) {
1767     if (node->IsCharacterData()) {
1768       // If we're dealing with the start/end container which is a character
1769       // node, pretend that the node is in the range.
1770       if (before && node == aRange->GetStartContainer()) {
1771         before = false;
1772       }
1773       if (after && node == aRange->GetEndContainer()) {
1774         after = false;
1775       }
1776     }
1777   }
1778
1779   return !before && !after;
1780 }
1781
1782 void nsRange::CutContents(DocumentFragment** aFragment, ErrorResult& aRv) {
1783   if (aFragment) {
1784     *aFragment = nullptr;
1785   }
1786
1787   if (!CanAccess(*GetMayCrossShadowBoundaryStartContainer()) ||
1788       !CanAccess(*GetMayCrossShadowBoundaryEndContainer())) {
1789     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
1790     return;
1791   }
1792
1793   nsCOMPtr<Document> doc = mStart.Container()->OwnerDoc();
1794
1795   nsCOMPtr<nsINode> commonAncestor = GetCommonAncestorContainer(
1796       aRv, StaticPrefs::dom_shadowdom_selection_across_boundary_enabled()
1797                ? AllowRangeCrossShadowBoundary::Yes
1798                : AllowRangeCrossShadowBoundary::No);
1799   if (aRv.Failed()) {
1800     return;
1801   }
1802
1803   // If aFragment isn't null, create a temporary fragment to hold our return.
1804   RefPtr<DocumentFragment> retval;
1805   if (aFragment) {
1806     retval =
1807         new (doc->NodeInfoManager()) DocumentFragment(doc->NodeInfoManager());
1808   }
1809   nsCOMPtr<nsINode> commonCloneAncestor = retval.get();
1810
1811   // Batch possible DOMSubtreeModified events.
1812   mozAutoSubtreeModified subtree(mRoot ? mRoot->OwnerDoc() : nullptr, nullptr);
1813
1814   // Save the range end points locally to avoid interference
1815   // of Range gravity during our edits!
1816
1817   nsCOMPtr<nsINode> startContainer = GetMayCrossShadowBoundaryStartContainer();
1818   // `GetCommonAncestorContainer()` above ensures the range is positioned, hence
1819   // there have to be valid offsets.
1820
1821   const uint32_t startOffset = *MayCrossShadowBoundaryStartRef().Offset(
1822       RangeBoundary::OffsetFilter::kValidOffsets);
1823
1824   nsCOMPtr<nsINode> endContainer = GetMayCrossShadowBoundaryEndContainer();
1825   const uint32_t endOffset = *MayCrossShadowBoundaryEndRef().Offset(
1826       RangeBoundary::OffsetFilter::kValidOffsets);
1827
1828   if (retval) {
1829     // For extractContents(), abort early if there's a doctype (bug 719533).
1830     // This can happen only if the common ancestor is a document, in which case
1831     // we just need to find its doctype child and check if that's in the range.
1832     nsCOMPtr<Document> commonAncestorDocument =
1833         do_QueryInterface(commonAncestor);
1834     if (commonAncestorDocument) {
1835       RefPtr<DocumentType> doctype = commonAncestorDocument->GetDoctype();
1836
1837       // `GetCommonAncestorContainer()` above ensured the range is positioned.
1838       // Hence, start and end are both set and valid. If available, `doctype`
1839       // has a common ancestor with start and end, hence both have to be
1840       // comparable to it.
1841       if (doctype &&
1842           *nsContentUtils::ComparePoints(startContainer, startOffset, doctype,
1843                                          0) < 0 &&
1844           *nsContentUtils::ComparePoints(doctype, 0, endContainer, endOffset) <
1845               0) {
1846         aRv.ThrowHierarchyRequestError("Start or end position isn't valid.");
1847         return;
1848       }
1849     }
1850   }
1851
1852   // Create and initialize a subtree iterator that will give
1853   // us all the subtrees within the range.
1854
1855   RangeSubtreeIterator iter;
1856
1857   aRv = iter.Init(this,
1858                   StaticPrefs::dom_shadowdom_selection_across_boundary_enabled()
1859                       ? AllowRangeCrossShadowBoundary::Yes
1860                       : AllowRangeCrossShadowBoundary::No);
1861   if (aRv.Failed()) {
1862     return;
1863   }
1864
1865   if (iter.IsDone()) {
1866     // There's nothing for us to delete.
1867     aRv = CollapseRangeAfterDelete(this);
1868     if (!aRv.Failed() && aFragment) {
1869       retval.forget(aFragment);
1870     }
1871     return;
1872   }
1873
1874   iter.First();
1875
1876   bool handled = false;
1877
1878   // With the exception of text nodes that contain one of the range
1879   // end points, the subtree iterator should only give us back subtrees
1880   // that are completely contained between the range's end points.
1881
1882   while (!iter.IsDone()) {
1883     nsCOMPtr<nsINode> nodeToResult;
1884     nsCOMPtr<nsINode> node = iter.GetCurrentNode();
1885
1886     // Before we delete anything, advance the iterator to the next node that's
1887     // not a descendant of this one.  XXX It's a bit silly to iterate through
1888     // the descendants only to throw them out, we should use an iterator that
1889     // skips the descendants to begin with.
1890
1891     iter.Next();
1892     nsCOMPtr<nsINode> nextNode = iter.GetCurrentNode();
1893     while (nextNode && nextNode->IsInclusiveDescendantOf(node)) {
1894       iter.Next();
1895       nextNode = iter.GetCurrentNode();
1896     }
1897
1898     handled = false;
1899
1900     // If it's CharacterData, make sure we might need to delete
1901     // part of the data, instead of removing the whole node.
1902     //
1903     // XXX_kin: We need to also handle ProcessingInstruction
1904     // XXX_kin: according to the spec.
1905
1906     if (auto charData = CharacterData::FromNode(node)) {
1907       uint32_t dataLength = 0;
1908
1909       if (node == startContainer) {
1910         if (node == endContainer) {
1911           // This range is completely contained within a single text node.
1912           // Delete or extract the data between startOffset and endOffset.
1913
1914           if (endOffset > startOffset) {
1915             if (retval) {
1916               nsAutoString cutValue;
1917               charData->SubstringData(startOffset, endOffset - startOffset,
1918                                       cutValue, aRv);
1919               if (NS_WARN_IF(aRv.Failed())) {
1920                 return;
1921               }
1922               nsCOMPtr<nsINode> clone = node->CloneNode(false, aRv);
1923               if (NS_WARN_IF(aRv.Failed())) {
1924                 return;
1925               }
1926               clone->SetNodeValue(cutValue, aRv);
1927               if (NS_WARN_IF(aRv.Failed())) {
1928                 return;
1929               }
1930               nodeToResult = clone;
1931             }
1932
1933             nsMutationGuard guard;
1934             charData->DeleteData(startOffset, endOffset - startOffset, aRv);
1935             if (NS_WARN_IF(aRv.Failed())) {
1936               return;
1937             }
1938             if (guard.Mutated(0) && !ValidateCurrentNode(this, iter)) {
1939               aRv.Throw(NS_ERROR_UNEXPECTED);
1940               return;
1941             }
1942           }
1943
1944           handled = true;
1945         } else {
1946           // Delete or extract everything after startOffset.
1947
1948           dataLength = charData->Length();
1949
1950           if (dataLength >= startOffset) {
1951             if (retval) {
1952               nsAutoString cutValue;
1953               charData->SubstringData(startOffset, dataLength, cutValue, aRv);
1954               if (NS_WARN_IF(aRv.Failed())) {
1955                 return;
1956               }
1957               nsCOMPtr<nsINode> clone = node->CloneNode(false, aRv);
1958               if (NS_WARN_IF(aRv.Failed())) {
1959                 return;
1960               }
1961               clone->SetNodeValue(cutValue, aRv);
1962               if (NS_WARN_IF(aRv.Failed())) {
1963                 return;
1964               }
1965               nodeToResult = clone;
1966             }
1967
1968             nsMutationGuard guard;
1969             charData->DeleteData(startOffset, dataLength, aRv);
1970             if (NS_WARN_IF(aRv.Failed())) {
1971               return;
1972             }
1973             if (guard.Mutated(0) && !ValidateCurrentNode(this, iter)) {
1974               aRv.Throw(NS_ERROR_UNEXPECTED);
1975               return;
1976             }
1977           }
1978
1979           handled = true;
1980         }
1981       } else if (node == endContainer) {
1982         // Delete or extract everything before endOffset.
1983         if (retval) {
1984           nsAutoString cutValue;
1985           charData->SubstringData(0, endOffset, cutValue, aRv);
1986           if (NS_WARN_IF(aRv.Failed())) {
1987             return;
1988           }
1989           nsCOMPtr<nsINode> clone = node->CloneNode(false, aRv);
1990           if (NS_WARN_IF(aRv.Failed())) {
1991             return;
1992           }
1993           clone->SetNodeValue(cutValue, aRv);
1994           if (NS_WARN_IF(aRv.Failed())) {
1995             return;
1996           }
1997           nodeToResult = clone;
1998         }
1999
2000         nsMutationGuard guard;
2001         charData->DeleteData(0, endOffset, aRv);
2002         if (NS_WARN_IF(aRv.Failed())) {
2003           return;
2004         }
2005         if (guard.Mutated(0) && !ValidateCurrentNode(this, iter)) {
2006           aRv.Throw(NS_ERROR_UNEXPECTED);
2007           return;
2008         }
2009         handled = true;
2010       }
2011     }
2012
2013     if (!handled && (node == endContainer || node == startContainer)) {
2014       if (node && node->IsElement() &&
2015           ((node == endContainer && endOffset == 0) ||
2016            (node == startContainer &&
2017             node->AsElement()->GetChildCount() == startOffset))) {
2018         if (retval) {
2019           nodeToResult = node->CloneNode(false, aRv);
2020           if (aRv.Failed()) {
2021             return;
2022           }
2023         }
2024         handled = true;
2025       }
2026     }
2027
2028     if (!handled) {
2029       // node was not handled above, so it must be completely contained
2030       // within the range. Just remove it from the tree!
2031       nodeToResult = node;
2032     }
2033
2034     uint32_t parentCount = 0;
2035     // Set the result to document fragment if we have 'retval'.
2036     if (retval) {
2037       nsCOMPtr<nsINode> oldCommonAncestor = commonAncestor;
2038       if (!iter.IsDone()) {
2039         // Setup the parameters for the next iteration of the loop.
2040         if (!nextNode) {
2041           aRv.Throw(NS_ERROR_UNEXPECTED);
2042           return;
2043         }
2044
2045         // Get node's and nextNode's common parent. Do this before moving
2046         // nodes from original DOM to result fragment.
2047         commonAncestor =
2048             nsContentUtils::GetClosestCommonInclusiveAncestor(node, nextNode);
2049         if (!commonAncestor) {
2050           aRv.Throw(NS_ERROR_UNEXPECTED);
2051           return;
2052         }
2053
2054         nsCOMPtr<nsINode> parentCounterNode = node;
2055         while (parentCounterNode && parentCounterNode != commonAncestor) {
2056           ++parentCount;
2057           parentCounterNode = parentCounterNode->GetParentNode();
2058           if (!parentCounterNode) {
2059             aRv.Throw(NS_ERROR_UNEXPECTED);
2060             return;
2061           }
2062         }
2063       }
2064
2065       // Clone the parent hierarchy between commonAncestor and node.
2066       nsCOMPtr<nsINode> closestAncestor, farthestAncestor;
2067       aRv = CloneParentsBetween(oldCommonAncestor, node,
2068                                 getter_AddRefs(closestAncestor),
2069                                 getter_AddRefs(farthestAncestor));
2070       if (aRv.Failed()) {
2071         return;
2072       }
2073
2074       if (farthestAncestor) {
2075         commonCloneAncestor->AppendChild(*farthestAncestor, aRv);
2076         if (NS_WARN_IF(aRv.Failed())) {
2077           return;
2078         }
2079       }
2080
2081       nsMutationGuard guard;
2082       nsCOMPtr<nsINode> parent = nodeToResult->GetParentNode();
2083       if (closestAncestor) {
2084         closestAncestor->AppendChild(*nodeToResult, aRv);
2085       } else {
2086         commonCloneAncestor->AppendChild(*nodeToResult, aRv);
2087       }
2088       if (NS_WARN_IF(aRv.Failed())) {
2089         return;
2090       }
2091       if (guard.Mutated(parent ? 2 : 1) && !ValidateCurrentNode(this, iter)) {
2092         aRv.Throw(NS_ERROR_UNEXPECTED);
2093         return;
2094       }
2095     } else if (nodeToResult) {
2096       nsMutationGuard guard;
2097       nsCOMPtr<nsINode> node = nodeToResult;
2098       nsCOMPtr<nsINode> parent = node->GetParentNode();
2099       if (parent) {
2100         parent->RemoveChild(*node, aRv);
2101         if (aRv.Failed()) {
2102           return;
2103         }
2104       }
2105       if (guard.Mutated(1) && !ValidateCurrentNode(this, iter)) {
2106         aRv.Throw(NS_ERROR_UNEXPECTED);
2107         return;
2108       }
2109     }
2110
2111     if (!iter.IsDone() && retval) {
2112       // Find the equivalent of commonAncestor in the cloned tree.
2113       nsCOMPtr<nsINode> newCloneAncestor = nodeToResult;
2114       for (uint32_t i = parentCount; i; --i) {
2115         newCloneAncestor = newCloneAncestor->GetParentNode();
2116         if (!newCloneAncestor) {
2117           aRv.Throw(NS_ERROR_UNEXPECTED);
2118           return;
2119         }
2120       }
2121       commonCloneAncestor = newCloneAncestor;
2122     }
2123   }
2124
2125   aRv = CollapseRangeAfterDelete(this);
2126   if (!aRv.Failed() && aFragment) {
2127     retval.forget(aFragment);
2128   }
2129 }
2130
2131 void nsRange::DeleteContents(ErrorResult& aRv) { CutContents(nullptr, aRv); }
2132
2133 already_AddRefed<DocumentFragment> nsRange::ExtractContents(ErrorResult& rv) {
2134   RefPtr<DocumentFragment> fragment;
2135   CutContents(getter_AddRefs(fragment), rv);
2136   return fragment.forget();
2137 }
2138
2139 int16_t nsRange::CompareBoundaryPoints(uint16_t aHow,
2140                                        const nsRange& aOtherRange,
2141                                        ErrorResult& aRv) {
2142   if (!mIsPositioned || !aOtherRange.IsPositioned()) {
2143     aRv.Throw(NS_ERROR_NOT_INITIALIZED);
2144     return 0;
2145   }
2146
2147   nsINode *ourNode, *otherNode;
2148   uint32_t ourOffset, otherOffset;
2149
2150   switch (aHow) {
2151     case Range_Binding::START_TO_START:
2152       ourNode = mStart.Container();
2153       ourOffset = *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets);
2154       otherNode = aOtherRange.GetStartContainer();
2155       otherOffset = aOtherRange.StartOffset();
2156       break;
2157     case Range_Binding::START_TO_END:
2158       ourNode = mEnd.Container();
2159       ourOffset = *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets);
2160       otherNode = aOtherRange.GetStartContainer();
2161       otherOffset = aOtherRange.StartOffset();
2162       break;
2163     case Range_Binding::END_TO_START:
2164       ourNode = mStart.Container();
2165       ourOffset = *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets);
2166       otherNode = aOtherRange.GetEndContainer();
2167       otherOffset = aOtherRange.EndOffset();
2168       break;
2169     case Range_Binding::END_TO_END:
2170       ourNode = mEnd.Container();
2171       ourOffset = *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets);
2172       otherNode = aOtherRange.GetEndContainer();
2173       otherOffset = aOtherRange.EndOffset();
2174       break;
2175     default:
2176       // We were passed an illegal value
2177       aRv.Throw(NS_ERROR_DOM_NOT_SUPPORTED_ERR);
2178       return 0;
2179   }
2180
2181   if (mRoot != aOtherRange.GetRoot()) {
2182     aRv.Throw(NS_ERROR_DOM_WRONG_DOCUMENT_ERR);
2183     return 0;
2184   }
2185
2186   const Maybe<int32_t> order =
2187       nsContentUtils::ComparePoints(ourNode, ourOffset, otherNode, otherOffset);
2188
2189   // `this` and `aOtherRange` share the same root and (ourNode, ourOffset),
2190   // (otherNode, otherOffset) correspond to some of their boundaries. Hence,
2191   // (ourNode, ourOffset) and (otherNode, otherOffset) have to be comparable.
2192   return *order;
2193 }
2194
2195 /* static */
2196 nsresult nsRange::CloneParentsBetween(nsINode* aAncestor, nsINode* aNode,
2197                                       nsINode** aClosestAncestor,
2198                                       nsINode** aFarthestAncestor) {
2199   NS_ENSURE_ARG_POINTER(
2200       (aAncestor && aNode && aClosestAncestor && aFarthestAncestor));
2201
2202   *aClosestAncestor = nullptr;
2203   *aFarthestAncestor = nullptr;
2204
2205   if (aAncestor == aNode) return NS_OK;
2206
2207   AutoTArray<nsCOMPtr<nsINode>, 16> parentStack;
2208
2209   nsCOMPtr<nsINode> parent = aNode->GetParentNode();
2210   while (parent && parent != aAncestor) {
2211     parentStack.AppendElement(parent);
2212     parent = parent->GetParentNode();
2213   }
2214
2215   nsCOMPtr<nsINode> firstParent;
2216   nsCOMPtr<nsINode> lastParent;
2217   for (int32_t i = parentStack.Length() - 1; i >= 0; i--) {
2218     ErrorResult rv;
2219     nsCOMPtr<nsINode> clone = parentStack[i]->CloneNode(false, rv);
2220
2221     if (rv.Failed()) {
2222       return rv.StealNSResult();
2223     }
2224     if (!clone) {
2225       return NS_ERROR_FAILURE;
2226     }
2227
2228     if (!lastParent) {
2229       lastParent = clone;
2230     } else {
2231       firstParent->AppendChild(*clone, rv);
2232       if (rv.Failed()) {
2233         return rv.StealNSResult();
2234       }
2235     }
2236
2237     firstParent = clone;
2238   }
2239
2240   firstParent.forget(aClosestAncestor);
2241   lastParent.forget(aFarthestAncestor);
2242
2243   return NS_OK;
2244 }
2245
2246 already_AddRefed<DocumentFragment> nsRange::CloneContents(ErrorResult& aRv) {
2247   nsCOMPtr<nsINode> commonAncestor = GetCommonAncestorContainer(aRv);
2248   MOZ_ASSERT(!aRv.Failed(), "GetCommonAncestorContainer() shouldn't fail!");
2249
2250   nsCOMPtr<Document> doc = mStart.Container()->OwnerDoc();
2251   NS_ASSERTION(doc, "CloneContents needs a document to continue.");
2252   if (!doc) {
2253     aRv.Throw(NS_ERROR_FAILURE);
2254     return nullptr;
2255   }
2256
2257   // Create a new document fragment in the context of this document,
2258   // which might be null
2259
2260   RefPtr<DocumentFragment> clonedFrag =
2261       new (doc->NodeInfoManager()) DocumentFragment(doc->NodeInfoManager());
2262
2263   if (Collapsed()) {
2264     return clonedFrag.forget();
2265   }
2266
2267   nsCOMPtr<nsINode> commonCloneAncestor = clonedFrag.get();
2268
2269   // Create and initialize a subtree iterator that will give
2270   // us all the subtrees within the range.
2271
2272   RangeSubtreeIterator iter;
2273
2274   aRv = iter.Init(this);
2275   if (aRv.Failed()) {
2276     return nullptr;
2277   }
2278
2279   if (iter.IsDone()) {
2280     // There's nothing to add to the doc frag, we must be done!
2281     return clonedFrag.forget();
2282   }
2283
2284   iter.First();
2285
2286   // With the exception of text nodes that contain one of the range
2287   // end points and elements which don't have any content selected the subtree
2288   // iterator should only give us back subtrees that are completely contained
2289   // between the range's end points.
2290   //
2291   // Unfortunately these subtrees don't contain the parent hierarchy/context
2292   // that the Range spec requires us to return. This loop clones the
2293   // parent hierarchy, adds a cloned version of the subtree, to it, then
2294   // correctly places this new subtree into the doc fragment.
2295
2296   while (!iter.IsDone()) {
2297     nsCOMPtr<nsINode> node = iter.GetCurrentNode();
2298     bool deepClone =
2299         !node->IsElement() ||
2300         (!(node == mEnd.Container() &&
2301            *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets) == 0) &&
2302          !(node == mStart.Container() &&
2303            *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets) ==
2304                node->AsElement()->GetChildCount()));
2305
2306     // Clone the current subtree!
2307
2308     nsCOMPtr<nsINode> clone = node->CloneNode(deepClone, aRv);
2309     if (aRv.Failed()) {
2310       return nullptr;
2311     }
2312
2313     // If it's CharacterData, make sure we only clone what
2314     // is in the range.
2315     //
2316     // XXX_kin: We need to also handle ProcessingInstruction
2317     // XXX_kin: according to the spec.
2318
2319     if (auto charData = CharacterData::FromNode(clone)) {
2320       if (node == mEnd.Container()) {
2321         // We only need the data before mEndOffset, so get rid of any
2322         // data after it.
2323
2324         uint32_t dataLength = charData->Length();
2325         if (dataLength >
2326             *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets)) {
2327           charData->DeleteData(
2328               *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
2329               dataLength -
2330                   *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
2331               aRv);
2332           if (aRv.Failed()) {
2333             return nullptr;
2334           }
2335         }
2336       }
2337
2338       if (node == mStart.Container()) {
2339         // We don't need any data before mStartOffset, so just
2340         // delete it!
2341
2342         if (*mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets) > 0) {
2343           charData->DeleteData(
2344               0, *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
2345               aRv);
2346           if (aRv.Failed()) {
2347             return nullptr;
2348           }
2349         }
2350       }
2351     }
2352
2353     // Clone the parent hierarchy between commonAncestor and node.
2354
2355     nsCOMPtr<nsINode> closestAncestor, farthestAncestor;
2356
2357     aRv = CloneParentsBetween(commonAncestor, node,
2358                               getter_AddRefs(closestAncestor),
2359                               getter_AddRefs(farthestAncestor));
2360
2361     if (aRv.Failed()) {
2362       return nullptr;
2363     }
2364
2365     // Hook the parent hierarchy/context of the subtree into the clone tree.
2366
2367     if (farthestAncestor) {
2368       commonCloneAncestor->AppendChild(*farthestAncestor, aRv);
2369
2370       if (aRv.Failed()) {
2371         return nullptr;
2372       }
2373     }
2374
2375     // Place the cloned subtree into the cloned doc frag tree!
2376
2377     nsCOMPtr<nsINode> cloneNode = clone;
2378     if (closestAncestor) {
2379       // Append the subtree under closestAncestor since it is the
2380       // immediate parent of the subtree.
2381
2382       closestAncestor->AppendChild(*cloneNode, aRv);
2383     } else {
2384       // If we get here, there is no missing parent hierarchy between
2385       // commonAncestor and node, so just append clone to commonCloneAncestor.
2386
2387       commonCloneAncestor->AppendChild(*cloneNode, aRv);
2388     }
2389     if (aRv.Failed()) {
2390       return nullptr;
2391     }
2392
2393     // Get the next subtree to be processed. The idea here is to setup
2394     // the parameters for the next iteration of the loop.
2395
2396     iter.Next();
2397
2398     if (iter.IsDone()) break;  // We must be done!
2399
2400     nsCOMPtr<nsINode> nextNode = iter.GetCurrentNode();
2401     if (!nextNode) {
2402       aRv.Throw(NS_ERROR_FAILURE);
2403       return nullptr;
2404     }
2405
2406     // Get node and nextNode's common parent.
2407     commonAncestor =
2408         nsContentUtils::GetClosestCommonInclusiveAncestor(node, nextNode);
2409
2410     if (!commonAncestor) {
2411       aRv.Throw(NS_ERROR_FAILURE);
2412       return nullptr;
2413     }
2414
2415     // Find the equivalent of commonAncestor in the cloned tree!
2416
2417     while (node && node != commonAncestor) {
2418       node = node->GetParentNode();
2419       if (aRv.Failed()) {
2420         return nullptr;
2421       }
2422
2423       if (!node) {
2424         aRv.Throw(NS_ERROR_FAILURE);
2425         return nullptr;
2426       }
2427
2428       cloneNode = cloneNode->GetParentNode();
2429       if (!cloneNode) {
2430         aRv.Throw(NS_ERROR_FAILURE);
2431         return nullptr;
2432       }
2433     }
2434
2435     commonCloneAncestor = cloneNode;
2436   }
2437
2438   return clonedFrag.forget();
2439 }
2440
2441 already_AddRefed<nsRange> nsRange::CloneRange() const {
2442   RefPtr<nsRange> range = nsRange::Create(mOwner);
2443   range->DoSetRange(mStart, mEnd, mRoot);
2444   if (mCrossShadowBoundaryRange) {
2445     range->CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
2446         mCrossShadowBoundaryRange->StartRef(),
2447         mCrossShadowBoundaryRange->EndRef());
2448   }
2449   return range.forget();
2450 }
2451
2452 void nsRange::InsertNode(nsINode& aNode, ErrorResult& aRv) {
2453   if (!CanAccess(aNode)) {
2454     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
2455     return;
2456   }
2457
2458   if (!IsPositioned()) {
2459     aRv.Throw(NS_ERROR_NOT_INITIALIZED);
2460     return;
2461   }
2462
2463   uint32_t tStartOffset = StartOffset();
2464
2465   nsCOMPtr<nsINode> tStartContainer = GetStartContainer();
2466
2467   if (!CanAccess(*tStartContainer)) {
2468     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
2469     return;
2470   }
2471
2472   if (&aNode == tStartContainer) {
2473     aRv.ThrowHierarchyRequestError(
2474         "The inserted node can not be range's start node.");
2475     return;
2476   }
2477
2478   // This is the node we'll be inserting before, and its parent
2479   nsCOMPtr<nsINode> referenceNode;
2480   nsCOMPtr<nsINode> referenceParentNode = tStartContainer;
2481
2482   RefPtr<Text> startTextNode = tStartContainer->GetAsText();
2483   nsCOMPtr<nsINodeList> tChildList;
2484   if (startTextNode) {
2485     referenceParentNode = tStartContainer->GetParentNode();
2486     if (!referenceParentNode) {
2487       aRv.ThrowHierarchyRequestError(
2488           "Can not get range's start node's parent.");
2489       return;
2490     }
2491
2492     referenceParentNode->EnsurePreInsertionValidity(aNode, tStartContainer,
2493                                                     aRv);
2494     if (aRv.Failed()) {
2495       return;
2496     }
2497
2498     RefPtr<Text> secondPart = startTextNode->SplitText(tStartOffset, aRv);
2499     if (aRv.Failed()) {
2500       return;
2501     }
2502
2503     referenceNode = secondPart;
2504   } else {
2505     tChildList = tStartContainer->ChildNodes();
2506
2507     // find the insertion point in the DOM and insert the Node
2508     referenceNode = tChildList->Item(tStartOffset);
2509
2510     tStartContainer->EnsurePreInsertionValidity(aNode, referenceNode, aRv);
2511     if (aRv.Failed()) {
2512       return;
2513     }
2514   }
2515
2516   // We might need to update the end to include the new node (bug 433662).
2517   // Ideally we'd only do this if needed, but it's tricky to know when it's
2518   // needed in advance (bug 765799).
2519   uint32_t newOffset;
2520
2521   if (referenceNode) {
2522     Maybe<uint32_t> indexInParent = referenceNode->ComputeIndexInParentNode();
2523     if (MOZ_UNLIKELY(NS_WARN_IF(indexInParent.isNothing()))) {
2524       aRv.Throw(NS_ERROR_FAILURE);
2525       return;
2526     }
2527     newOffset = *indexInParent;
2528   } else {
2529     newOffset = tChildList->Length();
2530   }
2531
2532   if (aNode.NodeType() == nsINode::DOCUMENT_FRAGMENT_NODE) {
2533     newOffset += aNode.GetChildCount();
2534   } else {
2535     newOffset++;
2536   }
2537
2538   // Now actually insert the node
2539   nsCOMPtr<nsINode> tResultNode;
2540   tResultNode = referenceParentNode->InsertBefore(aNode, referenceNode, aRv);
2541   if (aRv.Failed()) {
2542     return;
2543   }
2544
2545   if (Collapsed()) {
2546     aRv = SetEnd(referenceParentNode, newOffset);
2547   }
2548 }
2549
2550 void nsRange::SurroundContents(nsINode& aNewParent, ErrorResult& aRv) {
2551   if (!CanAccess(aNewParent)) {
2552     aRv.Throw(NS_ERROR_DOM_SECURITY_ERR);
2553     return;
2554   }
2555
2556   if (!mRoot) {
2557     aRv.Throw(NS_ERROR_DOM_INVALID_STATE_ERR);
2558     return;
2559   }
2560   // INVALID_STATE_ERROR: Raised if the Range partially selects a non-text
2561   // node.
2562   if (mStart.Container() != mEnd.Container()) {
2563     bool startIsText = mStart.Container()->IsText();
2564     bool endIsText = mEnd.Container()->IsText();
2565     nsINode* startGrandParent = mStart.Container()->GetParentNode();
2566     nsINode* endGrandParent = mEnd.Container()->GetParentNode();
2567     if (!((startIsText && endIsText && startGrandParent &&
2568            startGrandParent == endGrandParent) ||
2569           (startIsText && startGrandParent &&
2570            startGrandParent == mEnd.Container()) ||
2571           (endIsText && endGrandParent &&
2572            endGrandParent == mStart.Container()))) {
2573       aRv.Throw(NS_ERROR_DOM_INVALID_STATE_ERR);
2574       return;
2575     }
2576   }
2577
2578   // INVALID_NODE_TYPE_ERROR if aNewParent is something that can't be inserted
2579   // (Document, DocumentType, DocumentFragment)
2580   uint16_t nodeType = aNewParent.NodeType();
2581   if (nodeType == nsINode::DOCUMENT_NODE ||
2582       nodeType == nsINode::DOCUMENT_TYPE_NODE ||
2583       nodeType == nsINode::DOCUMENT_FRAGMENT_NODE) {
2584     aRv.Throw(NS_ERROR_DOM_INVALID_NODE_TYPE_ERR);
2585     return;
2586   }
2587
2588   // Extract the contents within the range.
2589
2590   RefPtr<DocumentFragment> docFrag = ExtractContents(aRv);
2591
2592   if (aRv.Failed()) {
2593     return;
2594   }
2595
2596   if (!docFrag) {
2597     aRv.Throw(NS_ERROR_FAILURE);
2598     return;
2599   }
2600
2601   // Spec says we need to remove all of aNewParent's
2602   // children prior to insertion.
2603
2604   nsCOMPtr<nsINodeList> children = aNewParent.ChildNodes();
2605   if (!children) {
2606     aRv.Throw(NS_ERROR_FAILURE);
2607     return;
2608   }
2609
2610   uint32_t numChildren = children->Length();
2611
2612   while (numChildren) {
2613     nsCOMPtr<nsINode> child = children->Item(--numChildren);
2614     if (!child) {
2615       aRv.Throw(NS_ERROR_FAILURE);
2616       return;
2617     }
2618
2619     aNewParent.RemoveChild(*child, aRv);
2620     if (aRv.Failed()) {
2621       return;
2622     }
2623   }
2624
2625   // Insert aNewParent at the range's start point.
2626
2627   InsertNode(aNewParent, aRv);
2628   if (aRv.Failed()) {
2629     return;
2630   }
2631
2632   // Append the content we extracted under aNewParent.
2633   aNewParent.AppendChild(*docFrag, aRv);
2634   if (aRv.Failed()) {
2635     return;
2636   }
2637
2638   // Select aNewParent, and its contents.
2639
2640   SelectNode(aNewParent, aRv);
2641 }
2642
2643 void nsRange::ToString(nsAString& aReturn, ErrorResult& aErr) {
2644   // clear the string
2645   aReturn.Truncate();
2646
2647   // If we're unpositioned, return the empty string
2648   if (!mIsPositioned) {
2649     return;
2650   }
2651
2652 #ifdef DEBUG_range
2653   printf("Range dump: -----------------------\n");
2654 #endif /* DEBUG */
2655
2656   // effeciency hack for simple case
2657   if (mStart.Container() == mEnd.Container()) {
2658     Text* textNode =
2659         mStart.Container() ? mStart.Container()->GetAsText() : nullptr;
2660
2661     if (textNode) {
2662 #ifdef DEBUG_range
2663       // If debug, dump it:
2664       textNode->List(stdout);
2665       printf("End Range dump: -----------------------\n");
2666 #endif /* DEBUG */
2667
2668       // grab the text
2669       textNode->SubstringData(
2670           *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
2671           *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets) -
2672               *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
2673           aReturn, aErr);
2674       return;
2675     }
2676   }
2677
2678   /* complex case: mStart.Container() != mEnd.Container(), or mStartParent not a
2679      text node revisit - there are potential optimizations here and also
2680      tradeoffs.
2681   */
2682
2683   PostContentIterator postOrderIter;
2684   nsresult rv = postOrderIter.Init(this);
2685   if (NS_WARN_IF(NS_FAILED(rv))) {
2686     aErr.Throw(rv);
2687     return;
2688   }
2689
2690   nsString tempString;
2691
2692   // loop through the content iterator, which returns nodes in the range in
2693   // close tag order, and grab the text from any text node
2694   for (; !postOrderIter.IsDone(); postOrderIter.Next()) {
2695     nsINode* n = postOrderIter.GetCurrentNode();
2696
2697 #ifdef DEBUG_range
2698     // If debug, dump it:
2699     n->List(stdout);
2700 #endif /* DEBUG */
2701     Text* textNode = n->GetAsText();
2702     if (textNode)  // if it's a text node, get the text
2703     {
2704       if (n == mStart.Container()) {  // only include text past start offset
2705         uint32_t strLength = textNode->Length();
2706         textNode->SubstringData(
2707             *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
2708             strLength -
2709                 *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
2710             tempString, IgnoreErrors());
2711         aReturn += tempString;
2712       } else if (n ==
2713                  mEnd.Container()) {  // only include text before end offset
2714         textNode->SubstringData(
2715             0, *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
2716             tempString, IgnoreErrors());
2717         aReturn += tempString;
2718       } else {  // grab the whole kit-n-kaboodle
2719         textNode->GetData(tempString);
2720         aReturn += tempString;
2721       }
2722     }
2723   }
2724
2725 #ifdef DEBUG_range
2726   printf("End Range dump: -----------------------\n");
2727 #endif /* DEBUG */
2728 }
2729
2730 void nsRange::Detach() {}
2731
2732 already_AddRefed<DocumentFragment> nsRange::CreateContextualFragment(
2733     const nsAString& aFragment, ErrorResult& aRv) const {
2734   if (!mIsPositioned) {
2735     aRv.Throw(NS_ERROR_FAILURE);
2736     return nullptr;
2737   }
2738
2739   return nsContentUtils::CreateContextualFragment(mStart.Container(), aFragment,
2740                                                   false, aRv);
2741 }
2742
2743 already_AddRefed<DocumentFragment> nsRange::CreateContextualFragment(
2744     const TrustedHTMLOrString& aFragment, ErrorResult& aRv) const {
2745   if (!mIsPositioned) {
2746     aRv.Throw(NS_ERROR_FAILURE);
2747     return nullptr;
2748   }
2749   MOZ_ASSERT(mStart.Container());
2750
2751   constexpr nsLiteralString sink = u"Range createContextualFragment"_ns;
2752   Maybe<nsAutoString> compliantStringHolder;
2753   nsCOMPtr<nsINode> node = mStart.Container();
2754   const nsAString* compliantString =
2755       TrustedTypeUtils::GetTrustedTypesCompliantString(
2756           aFragment, sink, kTrustedTypesOnlySinkGroup, *node,
2757           compliantStringHolder, aRv);
2758   if (aRv.Failed()) {
2759     return nullptr;
2760   }
2761
2762   return nsContentUtils::CreateContextualFragment(mStart.Container(),
2763                                                   *compliantString, false, aRv);
2764 }
2765
2766 static void ExtractRectFromOffset(nsIFrame* aFrame, const int32_t aOffset,
2767                                   nsRect* aR, bool aFlushToOriginEdge,
2768                                   bool aClampToEdge) {
2769   MOZ_ASSERT(aFrame);
2770   MOZ_ASSERT(aR);
2771
2772   nsPoint point;
2773   aFrame->GetPointFromOffset(aOffset, &point);
2774
2775   // Determine if aFrame has a vertical writing mode, which will change our math
2776   // on the output rect.
2777   bool isVertical = aFrame->GetWritingMode().IsVertical();
2778
2779   if (!aClampToEdge && !aR->Contains(point)) {
2780     // If point is outside aR, and we aren't clamping, output an empty rect
2781     // with origin at the point.
2782     if (isVertical) {
2783       aR->SetHeight(0);
2784       aR->y = point.y;
2785     } else {
2786       aR->SetWidth(0);
2787       aR->x = point.x;
2788     }
2789     return;
2790   }
2791
2792   if (aClampToEdge) {
2793     point = aR->ClampPoint(point);
2794   }
2795
2796   // point is within aR, and now we'll modify aR to output a rect that has point
2797   // on one edge. But which edge?
2798   if (aFlushToOriginEdge) {
2799     // The output rect should be flush to the edge of aR that contains the
2800     // origin.
2801     if (isVertical) {
2802       aR->SetHeight(point.y - aR->y);
2803     } else {
2804       aR->SetWidth(point.x - aR->x);
2805     }
2806   } else {
2807     // The output rect should be flush to the edge of aR opposite the origin.
2808     if (isVertical) {
2809       aR->SetHeight(aR->YMost() - point.y);
2810       aR->y = point.y;
2811     } else {
2812       aR->SetWidth(aR->XMost() - point.x);
2813       aR->x = point.x;
2814     }
2815   }
2816 }
2817
2818 static nsTextFrame* GetTextFrameForContent(nsIContent* aContent,
2819                                            bool aFlushLayout) {
2820   RefPtr<Document> doc = aContent->OwnerDoc();
2821   PresShell* presShell = doc->GetPresShell();
2822   if (!presShell) {
2823     return nullptr;
2824   }
2825
2826   // Try to un-suppress whitespace if needed, but only if we'll be able to flush
2827   // to immediately see the results of the un-suppression. If we can't flush
2828   // here, then calling EnsureFrameForTextNodeIsCreatedAfterFlush would be
2829   // pointless anyway.
2830   if (aFlushLayout) {
2831     const bool frameWillBeUnsuppressed =
2832         presShell->FrameConstructor()
2833             ->EnsureFrameForTextNodeIsCreatedAfterFlush(
2834                 static_cast<CharacterData*>(aContent));
2835     if (frameWillBeUnsuppressed) {
2836       doc->FlushPendingNotifications(FlushType::Layout);
2837     }
2838   }
2839
2840   nsIFrame* frame = aContent->GetPrimaryFrame();
2841   if (!frame || !frame->IsTextFrame()) {
2842     return nullptr;
2843   }
2844   return static_cast<nsTextFrame*>(frame);
2845 }
2846
2847 static nsresult GetPartialTextRect(RectCallback* aCallback,
2848                                    Sequence<nsString>* aTextList,
2849                                    nsIContent* aContent, int32_t aStartOffset,
2850                                    int32_t aEndOffset, bool aClampToEdge,
2851                                    bool aFlushLayout) {
2852   nsTextFrame* textFrame = GetTextFrameForContent(aContent, aFlushLayout);
2853   if (textFrame) {
2854     nsIFrame* relativeTo =
2855         nsLayoutUtils::GetContainingBlockForClientRect(textFrame);
2856
2857     for (nsTextFrame* f = textFrame->FindContinuationForOffset(aStartOffset); f;
2858          f = static_cast<nsTextFrame*>(f->GetNextContinuation())) {
2859       int32_t fstart = f->GetContentOffset(), fend = f->GetContentEnd();
2860       if (fend <= aStartOffset) {
2861         continue;
2862       }
2863       if (fstart >= aEndOffset) {
2864         break;
2865       }
2866
2867       // Calculate the text content offsets we'll need if text is requested.
2868       int32_t textContentStart = fstart;
2869       int32_t textContentEnd = fend;
2870
2871       // overlapping with the offset we want
2872       f->EnsureTextRun(nsTextFrame::eInflated);
2873       NS_ENSURE_TRUE(f->GetTextRun(nsTextFrame::eInflated),
2874                      NS_ERROR_OUT_OF_MEMORY);
2875       bool topLeftToBottomRight =
2876           !f->GetTextRun(nsTextFrame::eInflated)->IsInlineReversed();
2877       nsRect r = f->GetRectRelativeToSelf();
2878       if (fstart < aStartOffset) {
2879         // aStartOffset is within this frame
2880         ExtractRectFromOffset(f, aStartOffset, &r, !topLeftToBottomRight,
2881                               aClampToEdge);
2882         textContentStart = aStartOffset;
2883       }
2884       if (fend > aEndOffset) {
2885         // aEndOffset is in the middle of this frame
2886         ExtractRectFromOffset(f, aEndOffset, &r, topLeftToBottomRight,
2887                               aClampToEdge);
2888         textContentEnd = aEndOffset;
2889       }
2890       r = nsLayoutUtils::TransformFrameRectToAncestor(f, r, relativeTo);
2891       aCallback->AddRect(r);
2892
2893       // Finally capture the text, if requested.
2894       if (aTextList) {
2895         nsIFrame::RenderedText renderedText =
2896             f->GetRenderedText(textContentStart, textContentEnd,
2897                                nsIFrame::TextOffsetType::OffsetsInContentText,
2898                                nsIFrame::TrailingWhitespace::DontTrim);
2899
2900         NS_ENSURE_TRUE(aTextList->AppendElement(renderedText.mString, fallible),
2901                        NS_ERROR_OUT_OF_MEMORY);
2902       }
2903     }
2904   }
2905   return NS_OK;
2906 }
2907
2908 static void CollectClientRectsForSubtree(
2909     nsINode* aNode, RectCallback* aCollector, Sequence<nsString>* aTextList,
2910     nsINode* aStartContainer, uint32_t aStartOffset, nsINode* aEndContainer,
2911     uint32_t aEndOffset, bool aClampToEdge, bool aFlushLayout, bool aTextOnly) {
2912   auto* content = nsIContent::FromNode(aNode);
2913   if (!content) {
2914     return;
2915   }
2916
2917   const bool isText = content->IsText();
2918   if (isText) {
2919     if (aNode == aStartContainer) {
2920       int32_t offset = aStartContainer == aEndContainer
2921                            ? static_cast<int32_t>(aEndOffset)
2922                            : content->AsText()->TextDataLength();
2923       GetPartialTextRect(aCollector, aTextList, content,
2924                          static_cast<int32_t>(aStartOffset), offset,
2925                          aClampToEdge, aFlushLayout);
2926       return;
2927     }
2928
2929     if (aNode == aEndContainer) {
2930       GetPartialTextRect(aCollector, aTextList, content, 0,
2931                          static_cast<int32_t>(aEndOffset), aClampToEdge,
2932                          aFlushLayout);
2933       return;
2934     }
2935   }
2936
2937   if (nsIFrame* frame = content->GetPrimaryFrame()) {
2938     if (!aTextOnly || isText) {
2939       nsLayoutUtils::GetAllInFlowRectsAndTexts(
2940           frame, nsLayoutUtils::GetContainingBlockForClientRect(frame),
2941           aCollector, aTextList,
2942           nsLayoutUtils::GetAllInFlowRectsFlag::AccountForTransforms);
2943       if (isText) {
2944         return;
2945       }
2946       aTextOnly = true;
2947       // We just get the text when calling GetAllInFlowRectsAndTexts, so we
2948       // don't need to call it again when visiting the children.
2949       aTextList = nullptr;
2950     }
2951   } else if (!content->IsElement() ||
2952              !content->AsElement()->IsDisplayContents()) {
2953     return;
2954   }
2955
2956   FlattenedChildIterator childIter(content);
2957   for (nsIContent* child = childIter.GetNextChild(); child;
2958        child = childIter.GetNextChild()) {
2959     CollectClientRectsForSubtree(child, aCollector, aTextList, aStartContainer,
2960                                  aStartOffset, aEndContainer, aEndOffset,
2961                                  aClampToEdge, aFlushLayout, aTextOnly);
2962   }
2963 }
2964
2965 /* static */
2966 void nsRange::CollectClientRectsAndText(
2967     RectCallback* aCollector, Sequence<nsString>* aTextList, nsRange* aRange,
2968     nsINode* aStartContainer, uint32_t aStartOffset, nsINode* aEndContainer,
2969     uint32_t aEndOffset, bool aClampToEdge, bool aFlushLayout) {
2970   // Currently, this method is called with start of end offset of nsRange.
2971   // So, they must be between 0 - INT32_MAX.
2972   MOZ_ASSERT(RangeUtils::IsValidOffset(aStartOffset));
2973   MOZ_ASSERT(RangeUtils::IsValidOffset(aEndOffset));
2974
2975   // Hold strong pointers across the flush
2976   nsCOMPtr<nsINode> startContainer = aStartContainer;
2977   nsCOMPtr<nsINode> endContainer = aEndContainer;
2978
2979   // Flush out layout so our frames are up to date.
2980   if (!aStartContainer->IsInComposedDoc()) {
2981     return;
2982   }
2983
2984   if (aFlushLayout) {
2985     aStartContainer->OwnerDoc()->FlushPendingNotifications(FlushType::Layout);
2986     // Recheck whether we're still in the document
2987     if (!aStartContainer->IsInComposedDoc()) {
2988       return;
2989     }
2990   }
2991
2992   RangeSubtreeIterator iter;
2993
2994   nsresult rv = iter.Init(aRange);
2995   if (NS_FAILED(rv)) return;
2996
2997   if (iter.IsDone()) {
2998     // the range is collapsed, only continue if the cursor is in a text node
2999     if (aStartContainer->IsText()) {
3000       nsTextFrame* textFrame =
3001           GetTextFrameForContent(aStartContainer->AsText(), aFlushLayout);
3002       if (textFrame) {
3003         int32_t outOffset;
3004         nsIFrame* outFrame;
3005         textFrame->GetChildFrameContainingOffset(
3006             static_cast<int32_t>(aStartOffset), false, &outOffset, &outFrame);
3007         if (outFrame) {
3008           nsIFrame* relativeTo =
3009               nsLayoutUtils::GetContainingBlockForClientRect(outFrame);
3010           nsRect r = outFrame->GetRectRelativeToSelf();
3011           ExtractRectFromOffset(outFrame, static_cast<int32_t>(aStartOffset),
3012                                 &r, false, aClampToEdge);
3013           r.SetWidth(0);
3014           r = nsLayoutUtils::TransformFrameRectToAncestor(outFrame, r,
3015                                                           relativeTo);
3016           aCollector->AddRect(r);
3017         }
3018       }
3019     }
3020     return;
3021   }
3022
3023   do {
3024     nsCOMPtr<nsINode> node = iter.GetCurrentNode();
3025     iter.Next();
3026
3027     CollectClientRectsForSubtree(node, aCollector, aTextList, aStartContainer,
3028                                  aStartOffset, aEndContainer, aEndOffset,
3029                                  aClampToEdge, aFlushLayout, false);
3030   } while (!iter.IsDone());
3031 }
3032
3033 already_AddRefed<DOMRect> nsRange::GetBoundingClientRect(bool aClampToEdge,
3034                                                          bool aFlushLayout) {
3035   RefPtr<DOMRect> rect = new DOMRect(ToSupports(mOwner));
3036   if (!mIsPositioned) {
3037     return rect.forget();
3038   }
3039
3040   nsLayoutUtils::RectAccumulator accumulator;
3041   CollectClientRectsAndText(
3042       &accumulator, nullptr, this, mStart.Container(),
3043       *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
3044       mEnd.Container(),
3045       *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets), aClampToEdge,
3046       aFlushLayout);
3047
3048   nsRect r = accumulator.mResultRect.IsEmpty() ? accumulator.mFirstRect
3049                                                : accumulator.mResultRect;
3050   rect->SetLayoutRect(r);
3051   return rect.forget();
3052 }
3053
3054 already_AddRefed<DOMRectList> nsRange::GetClientRects(bool aClampToEdge,
3055                                                       bool aFlushLayout) {
3056   return GetClientRectsInner(AllowRangeCrossShadowBoundary::No, aClampToEdge,
3057                              aFlushLayout);
3058 }
3059
3060 already_AddRefed<DOMRectList> nsRange::GetAllowCrossShadowBoundaryClientRects(
3061     bool aClampToEdge, bool aFlushLayout) {
3062   return GetClientRectsInner(AllowRangeCrossShadowBoundary::Yes, aClampToEdge,
3063                              aFlushLayout);
3064 }
3065
3066 already_AddRefed<DOMRectList> nsRange::GetClientRectsInner(
3067     AllowRangeCrossShadowBoundary aAllowCrossShadowBoundaryRange,
3068     bool aClampToEdge, bool aFlushLayout) {
3069   if (!mIsPositioned) {
3070     return nullptr;
3071   }
3072
3073   RefPtr<DOMRectList> rectList = new DOMRectList(ToSupports(mOwner));
3074
3075   nsLayoutUtils::RectListBuilder builder(rectList);
3076
3077   const auto& startRef =
3078       aAllowCrossShadowBoundaryRange == AllowRangeCrossShadowBoundary::Yes
3079           ? MayCrossShadowBoundaryStartRef()
3080           : mStart;
3081   const auto& endRef =
3082       aAllowCrossShadowBoundaryRange == AllowRangeCrossShadowBoundary::Yes
3083           ? MayCrossShadowBoundaryEndRef()
3084           : mEnd;
3085
3086   CollectClientRectsAndText(
3087       &builder, nullptr, this, startRef.Container(),
3088       *startRef.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
3089       endRef.Container(),
3090       *endRef.Offset(RangeBoundary::OffsetFilter::kValidOffsets), aClampToEdge,
3091       aFlushLayout);
3092   return rectList.forget();
3093 }
3094
3095 void nsRange::GetClientRectsAndTexts(mozilla::dom::ClientRectsAndTexts& aResult,
3096                                      ErrorResult& aErr) {
3097   if (!mIsPositioned) {
3098     return;
3099   }
3100
3101   aResult.mRectList = new DOMRectList(ToSupports(mOwner));
3102
3103   nsLayoutUtils::RectListBuilder builder(aResult.mRectList);
3104
3105   CollectClientRectsAndText(
3106       &builder, &aResult.mTextList, this, mStart.Container(),
3107       *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
3108       mEnd.Container(),
3109       *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets), true, true);
3110 }
3111
3112 nsresult nsRange::GetUsedFontFaces(nsLayoutUtils::UsedFontFaceList& aResult,
3113                                    uint32_t aMaxRanges,
3114                                    bool aSkipCollapsedWhitespace) {
3115   NS_ENSURE_TRUE(mIsPositioned, NS_ERROR_UNEXPECTED);
3116
3117   nsCOMPtr<nsINode> startContainer = mStart.Container();
3118   nsCOMPtr<nsINode> endContainer = mEnd.Container();
3119
3120   // Flush out layout so our frames are up to date.
3121   Document* doc = mStart.Container()->OwnerDoc();
3122   NS_ENSURE_TRUE(doc, NS_ERROR_UNEXPECTED);
3123   doc->FlushPendingNotifications(FlushType::Frames);
3124
3125   // Recheck whether we're still in the document
3126   NS_ENSURE_TRUE(mStart.Container()->IsInComposedDoc(), NS_ERROR_UNEXPECTED);
3127
3128   // A table to map gfxFontEntry objects to InspectorFontFace objects.
3129   // This table does NOT own the InspectorFontFace objects, it only holds
3130   // raw pointers to them. They are owned by the aResult array.
3131   nsLayoutUtils::UsedFontFaceTable fontFaces;
3132
3133   RangeSubtreeIterator iter;
3134   nsresult rv = iter.Init(this);
3135   NS_ENSURE_SUCCESS(rv, rv);
3136
3137   while (!iter.IsDone()) {
3138     // only collect anything if the range is not collapsed
3139     nsCOMPtr<nsINode> node = iter.GetCurrentNode();
3140     iter.Next();
3141
3142     nsCOMPtr<nsIContent> content = do_QueryInterface(node);
3143     if (!content) {
3144       continue;
3145     }
3146     nsIFrame* frame = content->GetPrimaryFrame();
3147     if (!frame) {
3148       continue;
3149     }
3150
3151     if (content->IsText()) {
3152       if (node == startContainer) {
3153         int32_t offset =
3154             startContainer == endContainer
3155                 ? *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets)
3156                 : content->AsText()->TextDataLength();
3157         nsLayoutUtils::GetFontFacesForText(
3158             frame, *mStart.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
3159             offset, true, aResult, fontFaces, aMaxRanges,
3160             aSkipCollapsedWhitespace);
3161         continue;
3162       }
3163       if (node == endContainer) {
3164         nsLayoutUtils::GetFontFacesForText(
3165             frame, 0, *mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets),
3166             true, aResult, fontFaces, aMaxRanges, aSkipCollapsedWhitespace);
3167         continue;
3168       }
3169     }
3170
3171     nsLayoutUtils::GetFontFacesForFrames(frame, aResult, fontFaces, aMaxRanges,
3172                                          aSkipCollapsedWhitespace);
3173   }
3174
3175   return NS_OK;
3176 }
3177
3178 nsINode* nsRange::GetRegisteredClosestCommonInclusiveAncestor() {
3179   MOZ_ASSERT(IsInAnySelection(),
3180              "GetRegisteredClosestCommonInclusiveAncestor only valid for range "
3181              "in selection");
3182   MOZ_ASSERT(mRegisteredClosestCommonInclusiveAncestor);
3183   return mRegisteredClosestCommonInclusiveAncestor;
3184 }
3185
3186 /* static */
3187 bool nsRange::AutoInvalidateSelection::sIsNested;
3188
3189 nsRange::AutoInvalidateSelection::~AutoInvalidateSelection() {
3190   if (!mCommonAncestor) {
3191     return;
3192   }
3193   sIsNested = false;
3194   ::InvalidateAllFrames(mCommonAncestor);
3195
3196   // Our range might not be in a selection anymore, because one of our selection
3197   // listeners might have gone ahead and run script of various sorts that messed
3198   // with selections, ranges, etc.  But if it still is, we should check whether
3199   // we have a different common ancestor now, and if so invalidate its subtree
3200   // so it paints the selection it's in now.
3201   if (mRange->IsInAnySelection()) {
3202     nsINode* commonAncestor =
3203         mRange->GetRegisteredClosestCommonInclusiveAncestor();
3204     // XXXbz can commonAncestor really be null here?  I wouldn't think so!  If
3205     // it _were_, then in a debug build
3206     // GetRegisteredClosestCommonInclusiveAncestor() would have fatally
3207     // asserted.
3208     if (commonAncestor && commonAncestor != mCommonAncestor) {
3209       ::InvalidateAllFrames(commonAncestor);
3210     }
3211   }
3212 }
3213
3214 /* static */
3215 already_AddRefed<nsRange> nsRange::Constructor(const GlobalObject& aGlobal,
3216                                                ErrorResult& aRv) {
3217   nsCOMPtr<nsPIDOMWindowInner> window =
3218       do_QueryInterface(aGlobal.GetAsSupports());
3219   if (!window || !window->GetDoc()) {
3220     aRv.Throw(NS_ERROR_FAILURE);
3221     return nullptr;
3222   }
3223
3224   return window->GetDoc()->CreateRange(aRv);
3225 }
3226
3227 static bool ExcludeIfNextToNonSelectable(nsIContent* aContent) {
3228   return aContent->IsText() &&
3229          aContent->HasFlag(NS_CREATE_FRAME_IF_NON_WHITESPACE);
3230 }
3231
3232 void nsRange::ExcludeNonSelectableNodes(nsTArray<RefPtr<nsRange>>* aOutRanges) {
3233   if (!mIsPositioned) {
3234     MOZ_ASSERT(false);
3235     return;
3236   }
3237   MOZ_ASSERT(mEnd.Container());
3238   MOZ_ASSERT(mStart.Container());
3239
3240   nsRange* range = this;
3241   RefPtr<nsRange> newRange;
3242   while (range) {
3243     PreContentIterator preOrderIter;
3244     nsresult rv = preOrderIter.Init(range);
3245     if (NS_FAILED(rv)) {
3246       return;
3247     }
3248
3249     bool added = false;
3250     bool seenSelectable = false;
3251     // |firstNonSelectableContent| is the first node in a consecutive sequence
3252     // of non-IsSelectable nodes.  When we find a selectable node after such
3253     // a sequence we'll end the last nsRange, create a new one and restart
3254     // the outer loop.
3255     nsIContent* firstNonSelectableContent = nullptr;
3256     while (true) {
3257       nsINode* node = preOrderIter.GetCurrentNode();
3258       preOrderIter.Next();
3259       bool selectable = true;
3260       nsIContent* content =
3261           node && node->IsContent() ? node->AsContent() : nullptr;
3262       if (content) {
3263         if (firstNonSelectableContent &&
3264             ExcludeIfNextToNonSelectable(content)) {
3265           // Ignorable whitespace next to a sequence of non-selectable nodes
3266           // counts as non-selectable (bug 1216001).
3267           selectable = false;
3268         }
3269         if (selectable) {
3270           nsIFrame* frame = content->GetPrimaryFrame();
3271           for (nsIContent* p = content; !frame && (p = p->GetParent());) {
3272             frame = p->GetPrimaryFrame();
3273           }
3274           if (frame) {
3275             selectable = frame->IsSelectable(nullptr);
3276           }
3277         }
3278       }
3279
3280       if (!selectable) {
3281         if (!firstNonSelectableContent) {
3282           firstNonSelectableContent = content;
3283         }
3284         if (preOrderIter.IsDone()) {
3285           if (seenSelectable) {
3286             // The tail end of the initial range is non-selectable - truncate
3287             // the current range before the first non-selectable node.
3288             range->SetEndBefore(*firstNonSelectableContent, IgnoreErrors());
3289           }
3290           return;
3291         }
3292         continue;
3293       }
3294
3295       if (firstNonSelectableContent) {
3296         if (range == this && !seenSelectable) {
3297           // This is the initial range and all its nodes until now are
3298           // non-selectable so just trim them from the start.
3299           IgnoredErrorResult err;
3300           range->SetStartBefore(*node, err, AllowRangeCrossShadowBoundary::Yes);
3301           if (err.Failed()) {
3302             return;
3303           }
3304           break;  // restart the same range with a new iterator
3305         }
3306
3307         // Save the end point before truncating the range.
3308         nsINode* endContainer = range->mEnd.Container();
3309         const uint32_t endOffset =
3310             *range->mEnd.Offset(RangeBoundary::OffsetFilter::kValidOffsets);
3311
3312         // Truncate the current range before the first non-selectable node.
3313         IgnoredErrorResult err;
3314         range->SetEndBefore(*firstNonSelectableContent, err,
3315                             AllowRangeCrossShadowBoundary::Yes);
3316
3317         // Store it in the result (strong ref) - do this before creating
3318         // a new range in |newRange| below so we don't drop the last ref
3319         // to the range created in the previous iteration.
3320         if (!added && !err.Failed()) {
3321           aOutRanges->AppendElement(range);
3322         }
3323
3324         // Create a new range for the remainder.
3325         nsINode* startContainer = node;
3326         Maybe<uint32_t> startOffset = Some(0);
3327         // Don't start *inside* a node with independent selection though
3328         // (e.g. <input>).
3329         if (content && content->HasIndependentSelection()) {
3330           nsINode* parent = startContainer->GetParent();
3331           if (parent) {
3332             startOffset = parent->ComputeIndexOf(startContainer);
3333             startContainer = parent;
3334           }
3335         }
3336         newRange =
3337             nsRange::Create(startContainer, startOffset.valueOr(UINT32_MAX),
3338                             endContainer, endOffset, IgnoreErrors());
3339         if (!newRange || newRange->Collapsed()) {
3340           newRange = nullptr;
3341         }
3342         range = newRange;
3343         break;  // create a new iterator for the new range, if any
3344       }
3345
3346       seenSelectable = true;
3347       if (!added) {
3348         added = true;
3349         aOutRanges->AppendElement(range);
3350       }
3351       if (preOrderIter.IsDone()) {
3352         return;
3353       }
3354     }
3355   }
3356 }
3357
3358 struct InnerTextAccumulator {
3359   explicit InnerTextAccumulator(mozilla::dom::DOMString& aValue)
3360       : mString(aValue.AsAString()), mRequiredLineBreakCount(0) {}
3361   void FlushLineBreaks() {
3362     while (mRequiredLineBreakCount > 0) {
3363       // Required line breaks at the start of the text are suppressed.
3364       if (!mString.IsEmpty()) {
3365         mString.Append('\n');
3366       }
3367       --mRequiredLineBreakCount;
3368     }
3369   }
3370   void Append(char aCh) { Append(nsAutoString(aCh)); }
3371   void Append(const nsAString& aString) {
3372     if (aString.IsEmpty()) {
3373       return;
3374     }
3375     FlushLineBreaks();
3376     mString.Append(aString);
3377   }
3378   void AddRequiredLineBreakCount(int8_t aCount) {
3379     mRequiredLineBreakCount = std::max(mRequiredLineBreakCount, aCount);
3380   }
3381
3382   nsAString& mString;
3383   int8_t mRequiredLineBreakCount;
3384 };
3385
3386 static bool IsVisibleAndNotInReplacedElement(nsIFrame* aFrame) {
3387   if (!aFrame || !aFrame->StyleVisibility()->IsVisible() ||
3388       aFrame->HasAnyStateBits(NS_FRAME_IS_NONDISPLAY)) {
3389     return false;
3390   }
3391   if (aFrame->HidesContent()) {
3392     return false;
3393   }
3394   for (nsIFrame* f = aFrame->GetParent(); f; f = f->GetParent()) {
3395     if (f->HidesContent()) {
3396       return false;
3397     }
3398     if (f->IsReplaced() &&
3399         !f->GetContent()->IsAnyOfHTMLElements(nsGkAtoms::button,
3400                                               nsGkAtoms::select) &&
3401         !f->GetContent()->IsSVGElement()) {
3402       return false;
3403     }
3404   }
3405   return true;
3406 }
3407
3408 static void AppendTransformedText(InnerTextAccumulator& aResult,
3409                                   nsIContent* aContainer) {
3410   auto textNode = static_cast<CharacterData*>(aContainer);
3411
3412   nsIFrame* frame = textNode->GetPrimaryFrame();
3413   if (!IsVisibleAndNotInReplacedElement(frame)) {
3414     return;
3415   }
3416
3417   nsIFrame::RenderedText text =
3418       frame->GetRenderedText(0, aContainer->GetChildCount());
3419   aResult.Append(text.mString);
3420 }
3421
3422 /**
3423  * States for tree traversal. AT_NODE means that we are about to enter
3424  * the current DOM node. AFTER_NODE means that we have just finished traversing
3425  * the children of the current DOM node and are about to apply any
3426  * "after processing the node's children" steps before we finish visiting
3427  * the node.
3428  */
3429 enum TreeTraversalState { AT_NODE, AFTER_NODE };
3430
3431 static int8_t GetRequiredInnerTextLineBreakCount(nsIFrame* aFrame) {
3432   if (aFrame->GetContent()->IsHTMLElement(nsGkAtoms::p)) {
3433     return 2;
3434   }
3435   const nsStyleDisplay* styleDisplay = aFrame->StyleDisplay();
3436   if (styleDisplay->IsBlockOutside(aFrame) ||
3437       styleDisplay->mDisplay == StyleDisplay::TableCaption) {
3438     return 1;
3439   }
3440   return 0;
3441 }
3442
3443 static bool IsLastCellOfRow(nsIFrame* aFrame) {
3444   LayoutFrameType type = aFrame->Type();
3445   if (type != LayoutFrameType::TableCell) {
3446     return true;
3447   }
3448   for (nsIFrame* c = aFrame; c; c = c->GetNextContinuation()) {
3449     if (c->GetNextSibling()) {
3450       return false;
3451     }
3452   }
3453   return true;
3454 }
3455
3456 static bool IsLastRowOfRowGroup(nsIFrame* aFrame) {
3457   if (!aFrame->IsTableRowFrame()) {
3458     return true;
3459   }
3460   for (nsIFrame* c = aFrame; c; c = c->GetNextContinuation()) {
3461     if (c->GetNextSibling()) {
3462       return false;
3463     }
3464   }
3465   return true;
3466 }
3467
3468 static bool IsLastNonemptyRowGroupOfTable(nsIFrame* aFrame) {
3469   if (!aFrame->IsTableRowGroupFrame()) {
3470     return true;
3471   }
3472   for (nsIFrame* c = aFrame; c; c = c->GetNextContinuation()) {
3473     for (nsIFrame* next = c->GetNextSibling(); next;
3474          next = next->GetNextSibling()) {
3475       if (next->PrincipalChildList().FirstChild()) {
3476         return false;
3477       }
3478     }
3479   }
3480   return true;
3481 }
3482
3483 void nsRange::GetInnerTextNoFlush(DOMString& aValue, ErrorResult& aError,
3484                                   nsIContent* aContainer) {
3485   InnerTextAccumulator result(aValue);
3486
3487   if (aContainer->IsText()) {
3488     AppendTransformedText(result, aContainer);
3489     return;
3490   }
3491
3492   nsIContent* currentNode = aContainer;
3493   TreeTraversalState currentState = AFTER_NODE;
3494
3495   nsIContent* endNode = aContainer;
3496   TreeTraversalState endState = AFTER_NODE;
3497
3498   nsIContent* firstChild = aContainer->GetFirstChild();
3499   if (firstChild) {
3500     currentNode = firstChild;
3501     currentState = AT_NODE;
3502   }
3503
3504   while (currentNode != endNode || currentState != endState) {
3505     nsIFrame* f = currentNode->GetPrimaryFrame();
3506     bool isVisibleAndNotReplaced = IsVisibleAndNotInReplacedElement(f);
3507     if (currentState == AT_NODE) {
3508       bool isText = currentNode->IsText();
3509       if (isVisibleAndNotReplaced) {
3510         result.AddRequiredLineBreakCount(GetRequiredInnerTextLineBreakCount(f));
3511         if (isText) {
3512           nsIFrame::RenderedText text = f->GetRenderedText();
3513           result.Append(text.mString);
3514         }
3515       }
3516       nsIContent* child = currentNode->GetFirstChild();
3517       if (child) {
3518         currentNode = child;
3519         continue;
3520       }
3521       currentState = AFTER_NODE;
3522     }
3523     if (currentNode == endNode && currentState == endState) {
3524       break;
3525     }
3526     if (isVisibleAndNotReplaced) {
3527       if (currentNode->IsHTMLElement(nsGkAtoms::br)) {
3528         result.Append('\n');
3529       }
3530       switch (f->StyleDisplay()->DisplayInside()) {
3531         case StyleDisplayInside::TableCell:
3532           if (!IsLastCellOfRow(f)) {
3533             result.Append('\t');
3534           }
3535           break;
3536         case StyleDisplayInside::TableRow:
3537           if (!IsLastRowOfRowGroup(f) ||
3538               !IsLastNonemptyRowGroupOfTable(f->GetParent())) {
3539             result.Append('\n');
3540           }
3541           break;
3542         default:
3543           break;  // Do nothing
3544       }
3545       result.AddRequiredLineBreakCount(GetRequiredInnerTextLineBreakCount(f));
3546     }
3547     nsIContent* next = currentNode->GetNextSibling();
3548     if (next) {
3549       currentNode = next;
3550       currentState = AT_NODE;
3551     } else {
3552       currentNode = currentNode->GetParent();
3553     }
3554   }
3555
3556   // Do not flush trailing line breaks! Required breaks at the end of the text
3557   // are suppressed.
3558 }
3559
3560 template <typename SPT, typename SRT, typename EPT, typename ERT>
3561 void nsRange::CreateOrUpdateCrossShadowBoundaryRangeIfNeeded(
3562     const mozilla::RangeBoundaryBase<SPT, SRT>& aStartBoundary,
3563     const mozilla::RangeBoundaryBase<EPT, ERT>& aEndBoundary) {
3564   if (!StaticPrefs::dom_shadowdom_selection_across_boundary_enabled()) {
3565     return;
3566   }
3567
3568   MOZ_ASSERT(aStartBoundary.IsSetAndValid() && aEndBoundary.IsSetAndValid());
3569
3570   nsINode* startNode = aStartBoundary.Container();
3571   nsINode* endNode = aEndBoundary.Container();
3572
3573   if (!startNode && !endNode) {
3574     ResetCrossShadowBoundaryRange();
3575     return;
3576   }
3577
3578   // Nodes at least needs to be in the same document.
3579   if (startNode && endNode &&
3580       startNode->GetComposedDoc() != endNode->GetComposedDoc()) {
3581     return;
3582   }
3583
3584   auto CanBecomeCrossShadowBoundaryPoint = [](nsINode* aContainer) -> bool {
3585     if (!aContainer) {
3586       return true;
3587     }
3588
3589     // Unlike normal ranges, shadow cross ranges don't work
3590     // when the nodes aren't in document.
3591     if (!aContainer->IsInComposedDoc()) {
3592       return false;
3593     }
3594
3595     // AbstractRange::GetClosestCommonInclusiveAncestor only supports
3596     // Document and Content nodes.
3597     return aContainer->IsDocument() || aContainer->IsContent();
3598   };
3599
3600   if (!CanBecomeCrossShadowBoundaryPoint(startNode) ||
3601       !CanBecomeCrossShadowBoundaryPoint(endNode)) {
3602     ResetCrossShadowBoundaryRange();
3603     return;
3604   }
3605
3606   if (!mCrossShadowBoundaryRange) {
3607     mCrossShadowBoundaryRange =
3608         CrossShadowBoundaryRange::Create(aStartBoundary, aEndBoundary, this);
3609     return;
3610   }
3611
3612   mCrossShadowBoundaryRange->SetStartAndEnd(aStartBoundary, aEndBoundary);
3613 }
3614
3615 RawRangeBoundary nsRange::ComputeNewBoundaryWhenBoundaryInsideChangedText(
3616     const CharacterDataChangeInfo& aInfo, const RawRangeBoundary& aBoundary) {
3617   MOZ_ASSERT(aInfo.mChangeStart <
3618              *aBoundary.Offset(
3619                  RawRangeBoundary::OffsetFilter::kValidOrInvalidOffsets));
3620   // If boundary is inside changed text, position it before change
3621   // else adjust start offset for the change in length.
3622   CheckedUint32 newOffset{0};
3623   if (*aBoundary.Offset(
3624           RawRangeBoundary::OffsetFilter::kValidOrInvalidOffsets) <=
3625       aInfo.mChangeEnd) {
3626     newOffset = aInfo.mChangeStart;
3627   } else {
3628     newOffset = *aBoundary.Offset(
3629         RawRangeBoundary::OffsetFilter::kValidOrInvalidOffsets);
3630     newOffset -= aInfo.LengthOfRemovedText();
3631     newOffset += aInfo.mReplaceLength;
3632   }
3633
3634   // newOffset.isValid() isn't checked explicitly here, because
3635   // newOffset.value() contains an assertion.
3636   return {aBoundary.Container(), newOffset.value()};
3637 }