dom/base/AbstractRange.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 #include "mozilla/dom/AbstractRange.h"
   8 #include "mozilla/dom/AbstractRangeBinding.h"
   9
  10 #include "mozilla/Assertions.h"
  11 #include "mozilla/Attributes.h"
  12 #include "mozilla/RangeUtils.h"
  13 #include "mozilla/dom/Document.h"
  14 #include "mozilla/dom/StaticRange.h"
  15 #include "mozilla/dom/Selection.h"
  16 #include "nsContentUtils.h"
  17 #include "nsCycleCollectionParticipant.h"
  18 #include "nsGkAtoms.h"
  19 #include "nsINode.h"
  20 #include "nsRange.h"
  21 #include "nsTArray.h"
  22
  23 namespace mozilla::dom {
  24
  25 template nsresult AbstractRange::SetStartAndEndInternal(
  26     const RangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary,
  27     nsRange* aRange);
  28 template nsresult AbstractRange::SetStartAndEndInternal(
  29     const RangeBoundary& aStartBoundary, const RawRangeBoundary& aEndBoundary,
  30     nsRange* aRange);
  31 template nsresult AbstractRange::SetStartAndEndInternal(
  32     const RawRangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary,
  33     nsRange* aRange);
  34 template nsresult AbstractRange::SetStartAndEndInternal(
  35     const RawRangeBoundary& aStartBoundary,
  36     const RawRangeBoundary& aEndBoundary, nsRange* aRange);
  37 template nsresult AbstractRange::SetStartAndEndInternal(
  38     const RangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary,
  39     StaticRange* aRange);
  40 template nsresult AbstractRange::SetStartAndEndInternal(
  41     const RangeBoundary& aStartBoundary, const RawRangeBoundary& aEndBoundary,
  42     StaticRange* aRange);
  43 template nsresult AbstractRange::SetStartAndEndInternal(
  44     const RawRangeBoundary& aStartBoundary, const RangeBoundary& aEndBoundary,
  45     StaticRange* aRange);
  46 template nsresult AbstractRange::SetStartAndEndInternal(
  47     const RawRangeBoundary& aStartBoundary,
  48     const RawRangeBoundary& aEndBoundary, StaticRange* aRange);
  49 template bool AbstractRange::MaybeCacheToReuse(nsRange& aInstance);
  50 template bool AbstractRange::MaybeCacheToReuse(StaticRange& aInstance);
  51
  52 bool AbstractRange::sHasShutDown = false;
  53
  54 NS_IMPL_CYCLE_COLLECTING_ADDREF(AbstractRange)
  55 NS_IMPL_CYCLE_COLLECTING_RELEASE(AbstractRange)
  56
  57 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(AbstractRange)
  58   NS_WRAPPERCACHE_INTERFACE_MAP_ENTRY
  59   NS_INTERFACE_MAP_ENTRY(nsISupports)
  60 NS_INTERFACE_MAP_END
  61
  62 NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE_CLASS(AbstractRange)
  63
  64 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(AbstractRange)
  65   NS_IMPL_CYCLE_COLLECTION_UNLINK(mOwner);
  66   // mStart and mEnd may depend on or be depended on some other members in
  67   // concrete classes so that they should be unlinked in sub classes.
  68   NS_IMPL_CYCLE_COLLECTION_UNLINK_PRESERVED_WRAPPER
  69   tmp->mSelections.Clear();
  70   // Unregistering of the common inclusive ancestors would by design
  71   // also happen when the actual implementations unlink `mStart`/`mEnd`.
  72   // This may introduce additional overhead which is not needed when unlinking,
  73   // therefore this is done here beforehand.
  74   if (tmp->mRegisteredClosestCommonInclusiveAncestor) {
  75     tmp->UnregisterClosestCommonInclusiveAncestor(
  76         tmp->mRegisteredClosestCommonInclusiveAncestor, true);
  77   }
  78   MOZ_DIAGNOSTIC_ASSERT(!tmp->isInList(),
  79                         "Shouldn't be registered now that we're unlinking");
  80
  81 NS_IMPL_CYCLE_COLLECTION_UNLINK_END
  82
  83 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN(AbstractRange)
  84   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mOwner)
  85   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mStart)
  86   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mEnd)
  87   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mRegisteredClosestCommonInclusiveAncestor)
  88 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
  89
  90 void AbstractRange::MarkDescendants(const nsINode& aNode) {
  91   // Set NodeIsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection on
  92   // aNode's descendants unless aNode is already marked as a range common
  93   // ancestor or a descendant of one, in which case all of our descendants have
  94   // the bit set already.
  95   if (!aNode.IsMaybeSelected()) {
  96     // don't set the Descendant bit on |aNode| itself
  97     nsINode* node = aNode.GetNextNode(&aNode);
  98     while (node) {
  99       node->SetDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
 100       if (!node->IsClosestCommonInclusiveAncestorForRangeInSelection()) {
 101         node = node->GetNextNode(&aNode);
 102       } else {
 103         // optimize: skip this sub-tree since it's marked already.
 104         node = node->GetNextNonChildNode(&aNode);
 105       }
 106     }
 107   }
 108 }
 109
 110 void AbstractRange::UnmarkDescendants(const nsINode& aNode) {
 111   // Unset NodeIsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection
 112   // on aNode's descendants unless aNode is a descendant of another range common
 113   // ancestor. Also, exclude descendants of range common ancestors (but not the
 114   // common ancestor itself).
 115   if (!aNode
 116            .IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
 117     // we know |aNode| doesn't have any bit set
 118     nsINode* node = aNode.GetNextNode(&aNode);
 119     while (node) {
 120       node->ClearDescendantOfClosestCommonInclusiveAncestorForRangeInSelection();
 121       if (!node->IsClosestCommonInclusiveAncestorForRangeInSelection()) {
 122         node = node->GetNextNode(&aNode);
 123       } else {
 124         // We found an ancestor of an overlapping range, skip its descendants.
 125         node = node->GetNextNonChildNode(&aNode);
 126       }
 127     }
 128   }
 129 }
 130
 131 // NOTE: If you need to change default value of members of AbstractRange,
 132 //       update nsRange::Create(nsINode* aNode) and ClearForReuse() too.
 133 AbstractRange::AbstractRange(nsINode* aNode, bool aIsDynamicRange)
 134     : mRegisteredClosestCommonInclusiveAncestor(nullptr),
 135       mIsPositioned(false),
 136       mIsGenerated(false),
 137       mCalledByJS(false),
 138       mIsDynamicRange(aIsDynamicRange) {
 139   mRefCnt.SetIsOnMainThread();
 140   Init(aNode);
 141 }
 142
 143 AbstractRange::~AbstractRange() = default;
 144
 145 void AbstractRange::Init(nsINode* aNode) {
 146   MOZ_ASSERT(aNode, "range isn't in a document!");
 147   mOwner = aNode->OwnerDoc();
 148 }
 149
 150 // static
 151 void AbstractRange::Shutdown() {
 152   sHasShutDown = true;
 153   if (nsTArray<RefPtr<nsRange>>* cachedRanges = nsRange::sCachedRanges) {
 154     nsRange::sCachedRanges = nullptr;
 155     cachedRanges->Clear();
 156     delete cachedRanges;
 157   }
 158   if (nsTArray<RefPtr<StaticRange>>* cachedRanges =
 159           StaticRange::sCachedRanges) {
 160     StaticRange::sCachedRanges = nullptr;
 161     cachedRanges->Clear();
 162     delete cachedRanges;
 163   }
 164 }
 165
 166 // static
 167 template <class RangeType>
 168 bool AbstractRange::MaybeCacheToReuse(RangeType& aInstance) {
 169   static const size_t kMaxRangeCache = 64;
 170
 171   // If the instance is not used by JS and the cache is not yet full, we
 172   // should reuse it.  Otherwise, delete it.
 173   if (sHasShutDown || aInstance.GetWrapperMaybeDead() || aInstance.GetFlags() ||
 174       (RangeType::sCachedRanges &&
 175        RangeType::sCachedRanges->Length() == kMaxRangeCache)) {
 176     return false;
 177   }
 178
 179   aInstance.ClearForReuse();
 180
 181   if (!RangeType::sCachedRanges) {
 182     RangeType::sCachedRanges = new nsTArray<RefPtr<RangeType>>(16);
 183   }
 184   RangeType::sCachedRanges->AppendElement(&aInstance);
 185   return true;
 186 }
 187
 188 nsINode* AbstractRange::GetClosestCommonInclusiveAncestor() const {
 189   return mIsPositioned ? nsContentUtils::GetClosestCommonInclusiveAncestor(
 190                              mStart.Container(), mEnd.Container())
 191                        : nullptr;
 192 }
 193
 194 // static
 195 template <typename SPT, typename SRT, typename EPT, typename ERT,
 196           typename RangeType>
 197 nsresult AbstractRange::SetStartAndEndInternal(
 198     const RangeBoundaryBase<SPT, SRT>& aStartBoundary,
 199     const RangeBoundaryBase<EPT, ERT>& aEndBoundary, RangeType* aRange) {
 200   if (NS_WARN_IF(!aStartBoundary.IsSet()) ||
 201       NS_WARN_IF(!aEndBoundary.IsSet())) {
 202     return NS_ERROR_INVALID_ARG;
 203   }
 204
 205   nsINode* newStartRoot =
 206       RangeUtils::ComputeRootNode(aStartBoundary.Container());
 207   if (!newStartRoot) {
 208     return NS_ERROR_DOM_INVALID_NODE_TYPE_ERR;
 209   }
 210   if (!aStartBoundary.IsSetAndValid()) {
 211     return NS_ERROR_DOM_INDEX_SIZE_ERR;
 212   }
 213
 214   if (aStartBoundary.Container() == aEndBoundary.Container()) {
 215     if (!aEndBoundary.IsSetAndValid()) {
 216       return NS_ERROR_DOM_INDEX_SIZE_ERR;
 217     }
 218     // XXX: Offsets - handle this more efficiently.
 219     // If the end offset is less than the start offset, this should be
 220     // collapsed at the end offset.
 221     if (*aStartBoundary.Offset(
 222             RangeBoundaryBase<SPT, SRT>::OffsetFilter::kValidOffsets) >
 223         *aEndBoundary.Offset(
 224             RangeBoundaryBase<EPT, ERT>::OffsetFilter::kValidOffsets)) {
 225       aRange->DoSetRange(aEndBoundary, aEndBoundary, newStartRoot);
 226     } else {
 227       aRange->DoSetRange(aStartBoundary, aEndBoundary, newStartRoot);
 228     }
 229     return NS_OK;
 230   }
 231
 232   nsINode* newEndRoot = RangeUtils::ComputeRootNode(aEndBoundary.Container());
 233   if (!newEndRoot) {
 234     return NS_ERROR_DOM_INVALID_NODE_TYPE_ERR;
 235   }
 236   if (!aEndBoundary.IsSetAndValid()) {
 237     return NS_ERROR_DOM_INDEX_SIZE_ERR;
 238   }
 239
 240   // If they have different root, this should be collapsed at the end point.
 241   if (newStartRoot != newEndRoot) {
 242     aRange->DoSetRange(aEndBoundary, aEndBoundary, newEndRoot);
 243     return NS_OK;
 244   }
 245
 246   const Maybe<int32_t> pointOrder =
 247       nsContentUtils::ComparePoints(aStartBoundary, aEndBoundary);
 248   if (!pointOrder) {
 249     // Safely return a value but also detected this in debug builds.
 250     MOZ_ASSERT_UNREACHABLE();
 251     return NS_ERROR_INVALID_ARG;
 252   }
 253
 254   // If the end point is before the start point, this should be collapsed at
 255   // the end point.
 256   if (*pointOrder == 1) {
 257     aRange->DoSetRange(aEndBoundary, aEndBoundary, newEndRoot);
 258     return NS_OK;
 259   }
 260
 261   // Otherwise, set the range as specified.
 262   aRange->DoSetRange(aStartBoundary, aEndBoundary, newStartRoot);
 263   return NS_OK;
 264 }
 265
 266 bool AbstractRange::IsInSelection(const Selection& aSelection) const {
 267   return mSelections.Contains(&aSelection);
 268 }
 269
 270 void AbstractRange::RegisterSelection(Selection& aSelection) {
 271   if (IsInSelection(aSelection)) {
 272     return;
 273   }
 274   bool isFirstSelection = mSelections.IsEmpty();
 275   mSelections.AppendElement(&aSelection);
 276   if (isFirstSelection && !mRegisteredClosestCommonInclusiveAncestor) {
 277     nsINode* commonAncestor = GetClosestCommonInclusiveAncestor();
 278     MOZ_ASSERT(commonAncestor, "unexpected disconnected nodes");
 279     RegisterClosestCommonInclusiveAncestor(commonAncestor);
 280   }
 281 }
 282
 283 const nsTArray<WeakPtr<Selection>>& AbstractRange::GetSelections() const {
 284   return mSelections;
 285 }
 286
 287 void AbstractRange::UnregisterSelection(const Selection& aSelection) {
 288   mSelections.RemoveElement(&aSelection);
 289   if (mSelections.IsEmpty() && mRegisteredClosestCommonInclusiveAncestor) {
 290     UnregisterClosestCommonInclusiveAncestor(
 291         mRegisteredClosestCommonInclusiveAncestor, false);
 292     MOZ_DIAGNOSTIC_ASSERT(
 293         !mRegisteredClosestCommonInclusiveAncestor,
 294         "How can we have a registered common ancestor when we "
 295         "just unregistered?");
 296     MOZ_DIAGNOSTIC_ASSERT(
 297         !isInList(),
 298         "Shouldn't be registered if we have no "
 299         "mRegisteredClosestCommonInclusiveAncestor after unregistering");
 300   }
 301 }
 302
 303 void AbstractRange::RegisterClosestCommonInclusiveAncestor(nsINode* aNode) {
 304   MOZ_ASSERT(aNode, "bad arg");
 305
 306   MOZ_DIAGNOSTIC_ASSERT(IsInAnySelection(),
 307                         "registering range not in selection");
 308
 309   mRegisteredClosestCommonInclusiveAncestor = aNode;
 310
 311   MarkDescendants(*aNode);
 312
 313   UniquePtr<LinkedList<AbstractRange>>& ranges =
 314       aNode->GetClosestCommonInclusiveAncestorRangesPtr();
 315   if (!ranges) {
 316     ranges = MakeUnique<LinkedList<AbstractRange>>();
 317   }
 318
 319   MOZ_DIAGNOSTIC_ASSERT(!isInList());
 320   ranges->insertBack(this);
 321   aNode->SetClosestCommonInclusiveAncestorForRangeInSelection();
 322 }
 323
 324 void AbstractRange::UnregisterClosestCommonInclusiveAncestor(
 325     nsINode* aNode, bool aIsUnlinking) {
 326   MOZ_ASSERT(aNode, "bad arg");
 327   NS_ASSERTION(aNode->IsClosestCommonInclusiveAncestorForRangeInSelection(),
 328                "wrong node");
 329   MOZ_DIAGNOSTIC_ASSERT(aNode == mRegisteredClosestCommonInclusiveAncestor,
 330                         "wrong node");
 331   LinkedList<AbstractRange>* ranges =
 332       aNode->GetExistingClosestCommonInclusiveAncestorRanges();
 333   MOZ_ASSERT(ranges);
 334
 335   mRegisteredClosestCommonInclusiveAncestor = nullptr;
 336
 337 #ifdef DEBUG
 338   bool found = false;
 339   for (AbstractRange* range : *ranges) {
 340     if (range == this) {
 341       found = true;
 342       break;
 343     }
 344   }
 345   MOZ_ASSERT(found,
 346              "We should be in the list on our registered common ancestor");
 347 #endif  // DEBUG
 348
 349   remove();
 350
 351   // We don't want to waste time unmarking flags on nodes that are
 352   // being unlinked anyway.
 353   if (!aIsUnlinking && ranges->isEmpty()) {
 354     aNode->ClearClosestCommonInclusiveAncestorForRangeInSelection();
 355     UnmarkDescendants(*aNode);
 356   }
 357 }
 358
 359 void AbstractRange::UpdateCommonAncestorIfNecessary() {
 360   nsINode* oldCommonAncestor = mRegisteredClosestCommonInclusiveAncestor;
 361   nsINode* newCommonAncestor = GetClosestCommonInclusiveAncestor();
 362   if (newCommonAncestor != oldCommonAncestor) {
 363     if (oldCommonAncestor) {
 364       UnregisterClosestCommonInclusiveAncestor(oldCommonAncestor, false);
 365     }
 366     if (newCommonAncestor) {
 367       RegisterClosestCommonInclusiveAncestor(newCommonAncestor);
 368     } else {
 369       MOZ_DIAGNOSTIC_ASSERT(!mIsPositioned, "unexpected disconnected nodes");
 370       mSelections.Clear();
 371       MOZ_DIAGNOSTIC_ASSERT(
 372           !mRegisteredClosestCommonInclusiveAncestor,
 373           "How can we have a registered common ancestor when we "
 374           "didn't register ourselves?");
 375       MOZ_DIAGNOSTIC_ASSERT(!isInList(),
 376                             "Shouldn't be registered if we have no "
 377                             "mRegisteredClosestCommonInclusiveAncestor");
 378     }
 379   }
 380 }
 381
 382 nsINode* AbstractRange::GetParentObject() const { return mOwner; }
 383
 384 JSObject* AbstractRange::WrapObject(JSContext* aCx,
 385                                     JS::Handle<JSObject*> aGivenProto) {
 386   MOZ_CRASH("Must be overridden");
 387 }
 388
 389 void AbstractRange::ClearForReuse() {
 390   mOwner = nullptr;
 391   mStart = RangeBoundary();
 392   mEnd = RangeBoundary();
 393   mIsPositioned = false;
 394   mIsGenerated = false;
 395   mCalledByJS = false;
 396 }
 397
 398 }  // namespace mozilla::dom