diff options
Diffstat (limited to '')
| -rw-r--r-- | dom/base/RangeBoundary.h | 467 |
1 files changed, 467 insertions, 0 deletions
diff --git a/dom/base/RangeBoundary.h b/dom/base/RangeBoundary.h new file mode 100644 index 0000000000..2e4ab42397 --- /dev/null +++ b/dom/base/RangeBoundary.h @@ -0,0 +1,467 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef mozilla_RangeBoundary_h +#define mozilla_RangeBoundary_h + +#include "nsCOMPtr.h" +#include "nsIContent.h" +#include "mozilla/Assertions.h" +#include "mozilla/Maybe.h" + +class nsRange; + +namespace mozilla { + +template <typename T, typename U> +class EditorDOMPointBase; + +// This class will maintain a reference to the child immediately +// before the boundary's offset. We try to avoid computing the +// offset as much as possible and just ensure mRef points to the +// correct child. +// +// mParent +// | +// [child0] [child1] [child2] +// / | +// mRef mOffset=2 +// +// If mOffset == 0, mRef is null. +// For text nodes, mRef will always be null and the offset will +// be kept up-to-date. + +template <typename ParentType, typename RefType> +class RangeBoundaryBase; + +typedef RangeBoundaryBase<nsCOMPtr<nsINode>, nsCOMPtr<nsIContent>> + RangeBoundary; +typedef RangeBoundaryBase<nsINode*, nsIContent*> RawRangeBoundary; + +/** + * There are two ways of ensuring that `mRef` points to the correct node. + * In most cases, the `RangeBoundary` is used by an object that is a + * `MutationObserver` (i.e. `nsRange`) and replaces its `RangeBoundary` + * objects when its parent chain changes. + * However, there are Ranges which are not `MutationObserver`s (i.e. + * `StaticRange`). `mRef` may become invalid when a DOM mutation happens. + * Therefore, it needs to be recomputed using `mOffset` before it is being + * accessed. + * Because recomputing / validating of `mRef` could be an expensive operation, + * it should be ensured that `Ref()` is called as few times as possible, i.e. + * only once per method of `RangeBoundaryBase`. + * + * Furthermore, there are special implications when the `RangeBoundary` is not + * used by an `MutationObserver`: + * After a DOM mutation, the Boundary may point to something that is not valid + * anymore, i.e. the `mOffset` is larger than `Container()->Length()`. In this + * case, `Ref()` and `Get*ChildAtOffset()` return `nullptr` as an indication + * that this RangeBoundary is not valid anymore. Also, `IsSetAndValid()` + * returns false. However, `IsSet()` will still return true. + * + */ +enum class RangeBoundaryIsMutationObserved { No = 0, Yes = 1 }; + +// This class has two specializations, one using reference counting +// pointers and one using raw pointers. This helps us avoid unnecessary +// AddRef/Release calls. +template <typename ParentType, typename RefType> +class RangeBoundaryBase { + template <typename T, typename U> + friend class RangeBoundaryBase; + template <typename T, typename U> + friend class EditorDOMPointBase; + + friend nsRange; + + friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&, + RangeBoundary&, const char*, + uint32_t); + friend void ImplCycleCollectionUnlink(RangeBoundary&); + + static const uint32_t kFallbackOffset = 0; + + public: + RangeBoundaryBase(nsINode* aContainer, nsIContent* aRef) + : mParent(aContainer), mRef(aRef), mIsMutationObserved(true) { + if (mRef) { + NS_WARNING_ASSERTION(mRef->GetParentNode() == mParent, + "Initializing RangeBoundary with invalid value"); + } else { + mOffset.emplace(0); + } + } + + RangeBoundaryBase(nsINode* aContainer, uint32_t aOffset, + RangeBoundaryIsMutationObserved aRangeIsMutationObserver = + RangeBoundaryIsMutationObserved::Yes) + : mParent(aContainer), + mRef(nullptr), + mOffset(mozilla::Some(aOffset)), + mIsMutationObserved(bool(aRangeIsMutationObserver)) { + if (mIsMutationObserved && mParent && mParent->IsContainerNode()) { + // Find a reference node + if (aOffset == mParent->GetChildCount()) { + mRef = mParent->GetLastChild(); + } else if (aOffset > 0) { + mRef = mParent->GetChildAt_Deprecated(aOffset - 1); + } + NS_WARNING_ASSERTION(mRef || aOffset == 0, + "Constructing RangeBoundary with invalid value"); + } + NS_WARNING_ASSERTION(!mRef || mRef->GetParentNode() == mParent, + "Constructing RangeBoundary with invalid value"); + } + + RangeBoundaryBase() + : mParent(nullptr), mRef(nullptr), mIsMutationObserved(true) {} + + // Needed for initializing RawRangeBoundary from an existing RangeBoundary. + template <typename PT, typename RT> + RangeBoundaryBase(const RangeBoundaryBase<PT, RT>& aOther, + RangeBoundaryIsMutationObserved aIsMutationObserved) + : mParent(aOther.mParent), + mRef(aOther.mRef), + mOffset(aOther.mOffset), + mIsMutationObserved(bool(aIsMutationObserved)) {} + + /** + * This method may return `nullptr` in two cases: + * 1. `mIsMutationObserved` is true and the boundary points to the first + * child of `mParent`. + * 2. `mIsMutationObserved` is false and `mOffset` is out of bounds for + * `mParent`s child list. + * If `mIsMutationObserved` is false, this method may do some significant + * computation. Therefore it is advised to call it as seldom as possible. + * Code inside of this class should call this method exactly one time and + * afterwards refer to `mRef` directly. + */ + nsIContent* Ref() const { + if (mIsMutationObserved) { + return mRef; + } + MOZ_ASSERT(mParent); + MOZ_ASSERT(mOffset); + + // `mRef` may have become invalid due to some DOM mutation, + // which is not monitored here. Therefore, we need to validate `mRef` + // manually. + if (*mOffset > Container()->Length()) { + // offset > child count means that the range boundary has become invalid + // due to a DOM mutation. + mRef = nullptr; + } else if (*mOffset == Container()->Length()) { + mRef = mParent->GetLastChild(); + } else if (*mOffset) { + // validate and update `mRef`. + // If `ComputeIndexOf()` returns `Nothing`, then `mRef` is not a child of + // `mParent` anymore. + // If the returned index for `mRef` does not match to `mOffset`, `mRef` + // needs to be updated. + auto indexOfRefObject = mParent->ComputeIndexOf(mRef); + if (indexOfRefObject.isNothing() || *mOffset != *indexOfRefObject + 1) { + mRef = mParent->GetChildAt_Deprecated(*mOffset - 1); + } + } else { + mRef = nullptr; + } + return mRef; + } + + nsINode* Container() const { return mParent; } + + /** + * This method may return `nullptr` if `mIsMutationObserved` is false and + * `mOffset` is out of bounds. + */ + nsIContent* GetChildAtOffset() const { + if (!mParent || !mParent->IsContainerNode()) { + return nullptr; + } + nsIContent* const ref = Ref(); + if (!ref) { + if (!mIsMutationObserved && *mOffset != 0) { + // This means that this boundary is invalid. + // `mOffset` is out of bounds. + return nullptr; + } + MOZ_ASSERT(*Offset(OffsetFilter::kValidOrInvalidOffsets) == 0, + "invalid RangeBoundary"); + return mParent->GetFirstChild(); + } + MOZ_ASSERT(mParent->GetChildAt_Deprecated( + *Offset(OffsetFilter::kValidOrInvalidOffsets)) == + ref->GetNextSibling()); + return ref->GetNextSibling(); + } + + /** + * GetNextSiblingOfChildOffset() returns next sibling of a child at offset. + * If this refers after the last child or the container cannot have children, + * this returns nullptr with warning. + */ + nsIContent* GetNextSiblingOfChildAtOffset() const { + if (NS_WARN_IF(!mParent) || NS_WARN_IF(!mParent->IsContainerNode())) { + return nullptr; + } + nsIContent* const ref = Ref(); + if (!ref) { + if (!mIsMutationObserved && *mOffset != 0) { + // This means that this boundary is invalid. + // `mOffset` is out of bounds. + return nullptr; + } + MOZ_ASSERT(*Offset(OffsetFilter::kValidOffsets) == 0, + "invalid RangeBoundary"); + nsIContent* firstChild = mParent->GetFirstChild(); + if (NS_WARN_IF(!firstChild)) { + // Already referring the end of the container. + return nullptr; + } + return firstChild->GetNextSibling(); + } + if (NS_WARN_IF(!ref->GetNextSibling())) { + // Already referring the end of the container. + return nullptr; + } + return ref->GetNextSibling()->GetNextSibling(); + } + + /** + * GetPreviousSiblingOfChildAtOffset() returns previous sibling of a child + * at offset. If this refers the first child or the container cannot have + * children, this returns nullptr with warning. + */ + nsIContent* GetPreviousSiblingOfChildAtOffset() const { + if (NS_WARN_IF(!mParent) || NS_WARN_IF(!mParent->IsContainerNode())) { + return nullptr; + } + nsIContent* const ref = Ref(); + if (NS_WARN_IF(!ref)) { + // Already referring the start of the container. + return nullptr; + } + return ref; + } + + enum class OffsetFilter { kValidOffsets, kValidOrInvalidOffsets }; + + /** + * @return maybe an offset, depending on aOffsetFilter. If it is: + * kValidOffsets: if the offset is valid, it, Nothing{} otherwise. + * kValidOrInvalidOffsets: the internally stored offset, even if + * invalid, or if not available, a defined + * default value. That is, always some value. + */ + Maybe<uint32_t> Offset(const OffsetFilter aOffsetFilter) const { + switch (aOffsetFilter) { + case OffsetFilter::kValidOffsets: { + if (IsSetAndValid()) { + MOZ_ASSERT_IF(!mIsMutationObserved, mOffset); + if (!mOffset && mIsMutationObserved) { + DetermineOffsetFromReference(); + } + } + return !mIsMutationObserved && *mOffset > Container()->Length() + ? Nothing{} + : mOffset; + } + case OffsetFilter::kValidOrInvalidOffsets: { + MOZ_ASSERT_IF(!mIsMutationObserved, mOffset.isSome()); + if (mOffset.isSome()) { + return mOffset; + } + if (mParent && mIsMutationObserved) { + DetermineOffsetFromReference(); + if (mOffset.isSome()) { + return mOffset; + } + } + + return Some(kFallbackOffset); + } + } + + // Needed to calm the compiler. There was deliberately no default case added + // to the above switch-statement, because it would prevent build-errors when + // not all enumerators are handled. + MOZ_ASSERT_UNREACHABLE(); + return Some(kFallbackOffset); + } + + friend std::ostream& operator<<( + std::ostream& aStream, + const RangeBoundaryBase<ParentType, RefType>& aRangeBoundary) { + aStream << "{ mParent=" << aRangeBoundary.Container(); + if (aRangeBoundary.Container()) { + aStream << " (" << *aRangeBoundary.Container() + << ", Length()=" << aRangeBoundary.Container()->Length() << ")"; + } + if (aRangeBoundary.mIsMutationObserved) { + aStream << ", mRef=" << aRangeBoundary.mRef; + if (aRangeBoundary.mRef) { + aStream << " (" << *aRangeBoundary.mRef << ")"; + } + } + + aStream << ", mOffset=" << aRangeBoundary.mOffset; + aStream << ", mIsMutationObserved=" + << (aRangeBoundary.mIsMutationObserved ? "true" : "false") << " }"; + return aStream; + } + + private: + void DetermineOffsetFromReference() const { + MOZ_ASSERT(mParent); + MOZ_ASSERT(mRef); + MOZ_ASSERT(mRef->GetParentNode() == mParent); + MOZ_ASSERT(mIsMutationObserved); + MOZ_ASSERT(mOffset.isNothing()); + + if (mRef->IsBeingRemoved()) { + // ComputeIndexOf would return nothing because mRef has already been + // removed from the child node chain of mParent. + return; + } + + const Maybe<uint32_t> index = mParent->ComputeIndexOf(mRef); + MOZ_ASSERT(*index != UINT32_MAX); + mOffset.emplace(MOZ_LIKELY(index.isSome()) ? *index + 1u : 0u); + } + + void InvalidateOffset() { + MOZ_ASSERT(mParent); + MOZ_ASSERT(mParent->IsContainerNode(), + "Range is positioned on a text node!"); + if (!mIsMutationObserved) { + // RangeBoundaries that are not used in the context of a + // `MutationObserver` use the offset as main source of truth to compute + // `mRef`. Therefore, it must not be updated or invalidated. + return; + } + if (!mRef) { + MOZ_ASSERT(mOffset.isSome() && mOffset.value() == 0, + "Invalidating offset of invalid RangeBoundary?"); + return; + } + mOffset.reset(); + } + + public: + bool IsSet() const { return mParent && (mRef || mOffset.isSome()); } + + bool IsSetAndValid() const { + if (!IsSet()) { + return false; + } + + if (mIsMutationObserved && Ref()) { + // XXX mRef refers previous sibling of pointing child. Therefore, it + // seems odd that this becomes invalid due to its removal. Should we + // change RangeBoundaryBase to refer child at offset directly? + return Ref()->GetParentNode() == Container() && !Ref()->IsBeingRemoved(); + } + + MOZ_ASSERT(mOffset.isSome()); + return *mOffset <= Container()->Length(); + } + + bool IsStartOfContainer() const { + // We're at the first point in the container if we don't have a reference, + // and our offset is 0. If we don't have a Ref, we should already have an + // offset, so we can just directly fetch it. + return mIsMutationObserved ? !Ref() && mOffset.value() == 0 + : mOffset.value() == 0; + } + + bool IsEndOfContainer() const { + // We're at the last point in the container if Ref is a pointer to the last + // child in Container(), or our Offset() is the same as the length of our + // container. If we don't have a Ref, then we should already have an offset, + // so we can just directly fetch it. + return mIsMutationObserved && Ref() + ? !Ref()->GetNextSibling() + : mOffset.value() == Container()->Length(); + } + + // Convenience methods for switching between the two types + // of RangeBoundary. + RangeBoundaryBase<nsINode*, nsIContent*> AsRaw() const { + return RangeBoundaryBase<nsINode*, nsIContent*>( + *this, RangeBoundaryIsMutationObserved(mIsMutationObserved)); + } + + template <typename A, typename B> + RangeBoundaryBase& operator=(const RangeBoundaryBase<A, B>& aOther) = delete; + + template <typename A, typename B> + RangeBoundaryBase& CopyFrom( + const RangeBoundaryBase<A, B>& aOther, + RangeBoundaryIsMutationObserved aIsMutationObserved) { + // mParent and mRef can be strong pointers, so better to try to avoid any + // extra AddRef/Release calls. + if (mParent != aOther.mParent) { + mParent = aOther.mParent; + } + if (mRef != aOther.mRef) { + mRef = aOther.mRef; + } + mOffset = aOther.mOffset; + mIsMutationObserved = bool(aIsMutationObserved); + return *this; + } + + bool Equals(const nsINode* aNode, uint32_t aOffset) const { + if (mParent != aNode) { + return false; + } + + const Maybe<uint32_t> offset = Offset(OffsetFilter::kValidOffsets); + return offset && (*offset == aOffset); + } + + template <typename A, typename B> + bool operator==(const RangeBoundaryBase<A, B>& aOther) const { + return mParent == aOther.mParent && + (mIsMutationObserved && aOther.mIsMutationObserved && mRef + ? mRef == aOther.mRef + : Offset(OffsetFilter::kValidOrInvalidOffsets) == + aOther.Offset( + RangeBoundaryBase< + A, B>::OffsetFilter::kValidOrInvalidOffsets)); + } + + template <typename A, typename B> + bool operator!=(const RangeBoundaryBase<A, B>& aOther) const { + return !(*this == aOther); + } + + private: + ParentType mParent; + mutable RefType mRef; + + mutable mozilla::Maybe<uint32_t> mOffset; + bool mIsMutationObserved; +}; + +template <typename ParentType, typename RefType> +const uint32_t RangeBoundaryBase<ParentType, RefType>::kFallbackOffset; + +inline void ImplCycleCollectionUnlink(RangeBoundary& aField) { + ImplCycleCollectionUnlink(aField.mParent); + ImplCycleCollectionUnlink(aField.mRef); +} + +inline void ImplCycleCollectionTraverse( + nsCycleCollectionTraversalCallback& aCallback, RangeBoundary& aField, + const char* aName, uint32_t aFlags) { + ImplCycleCollectionTraverse(aCallback, aField.mParent, "mParent", 0); + ImplCycleCollectionTraverse(aCallback, aField.mRef, "mRef", 0); +} + +} // namespace mozilla + +#endif // defined(mozilla_RangeBoundary_h) |