From c2e4efaac47665e6b3de153b01616f7a9b3502ac Mon Sep 17 00:00:00 2001 From: Natalia Csoregi Date: Mon, 11 Mar 2024 10:47:07 +0200 Subject: [PATCH] Backed out changeset 37af5c6d011a (bug 1881695) for causing Bug 1884602 and Bug 1884601. CLOSED TREE --- dom/base/Selection.cpp | 54 +++----------------- dom/base/nsContentUtils.cpp | 33 +++++------- dom/base/nsContentUtils.h | 122 ++++++-------------------------------------- dom/base/nsINode.cpp | 10 ++-- 4 files changed, 36 insertions(+), 183 deletions(-) diff --git a/dom/base/Selection.cpp b/dom/base/Selection.cpp index d2b775d4b33c..e2d395d1086a 100644 --- a/dom/base/Selection.cpp +++ b/dom/base/Selection.cpp @@ -816,8 +816,7 @@ void Selection::SetAnchorFocusRange(size_t aIndex) { static int32_t CompareToRangeStart(const nsINode& aCompareNode, uint32_t aCompareOffset, - const AbstractRange& aRange, - nsContentUtils::NodeIndexCache* aCache) { + const AbstractRange& aRange) { MOZ_ASSERT(aRange.GetStartContainer()); nsINode* start = aRange.GetStartContainer(); // If the nodes that we're comparing are not in the same document, assume that @@ -831,13 +830,7 @@ static int32_t CompareToRangeStart(const nsINode& aCompareNode, // The points are in the same subtree, hence there has to be an order. return *nsContentUtils::ComparePoints(&aCompareNode, aCompareOffset, start, - aRange.StartOffset(), aCache); -} - -static int32_t CompareToRangeStart(const nsINode& aCompareNode, - uint32_t aCompareOffset, - const AbstractRange& aRange) { - return CompareToRangeStart(aCompareNode, aCompareOffset, aRange, nullptr); + aRange.StartOffset()); } static int32_t CompareToRangeEnd(const nsINode& aCompareNode, @@ -1469,45 +1462,10 @@ void Selection::StyledRanges::ReorderRangesIfNecessary() { mInvalidStaticRanges.AppendElements(std::move(invalidStaticRanges)); } if (domMutationHasHappened || mRangesMightHaveChanged) { - // This is hot code. Proceed with caution. - // This path uses a cache that keep the last 100 node/index combinations - // in a stack-allocated array to save up on expensive calls to - // nsINode::ComputeIndexOf() (which happen in - // nsContentUtils::ComparePoints()). - // The second expensive call here is the sort() below, which should be - // avoided if possible. Sorting can be avoided if the ranges are still in - // order. Checking the order is cheap compared to sorting (also, it fills up - // the cache, which is reused by the sort call). - nsContentUtils::NodeIndexCache cache; - bool rangeOrderHasChanged = false; - const nsINode* prevStartContainer = nullptr; - uint32_t prevStartOffset = 0; - for (const StyledRange& range : mRanges) { - const nsINode* startContainer = range.mRange->GetStartContainer(); - uint32_t startOffset = range.mRange->StartOffset(); - if (!prevStartContainer) { - prevStartContainer = startContainer; - prevStartOffset = startOffset; - continue; - } - // Calling ComparePoints here saves one call of - // AbstractRange::StartOffset() per iteration (which is surprisingly - // expensive). - if (*nsContentUtils::ComparePoints(startContainer, startOffset, - prevStartContainer, prevStartOffset, - &cache) != 1) { - rangeOrderHasChanged = true; - break; - } - prevStartContainer = startContainer; - prevStartOffset = startOffset; - } - if (rangeOrderHasChanged) { - mRanges.Sort([&cache](const StyledRange& a, const StyledRange& b) -> int { - return CompareToRangeStart(*a.mRange->GetStartContainer(), - a.mRange->StartOffset(), *b.mRange, &cache); - }); - } + mRanges.Sort([](const StyledRange& a, const StyledRange& b) -> int { + return CompareToRangeStart(*a.mRange->GetStartContainer(), + a.mRange->StartOffset(), *b.mRange); + }); mDocumentGeneration = currentDocumentGeneration; mRangesMightHaveChanged = false; } diff --git a/dom/base/nsContentUtils.cpp b/dom/base/nsContentUtils.cpp index c6f1687f73df..48e281ca0b95 100644 --- a/dom/base/nsContentUtils.cpp +++ b/dom/base/nsContentUtils.cpp @@ -3027,15 +3027,13 @@ bool nsContentUtils::PositionIsBefore(nsINode* aNode1, nsINode* aNode2, } /* static */ -Maybe nsContentUtils::ComparePoints(const nsINode* aParent1, - uint32_t aOffset1, - const nsINode* aParent2, - uint32_t aOffset2, - NodeIndexCache* aIndexCache) { +Maybe nsContentUtils::ComparePoints( + const nsINode* aParent1, uint32_t aOffset1, const nsINode* aParent2, + uint32_t aOffset2, ComparePointsCache* aParent1Cache) { bool disconnected{false}; const int32_t order = ComparePoints_Deprecated( - aParent1, aOffset1, aParent2, aOffset2, &disconnected, aIndexCache); + aParent1, aOffset1, aParent2, aOffset2, &disconnected, aParent1Cache); if (disconnected) { return Nothing(); } @@ -3046,7 +3044,7 @@ Maybe nsContentUtils::ComparePoints(const nsINode* aParent1, /* static */ int32_t nsContentUtils::ComparePoints_Deprecated( const nsINode* aParent1, uint32_t aOffset1, const nsINode* aParent2, - uint32_t aOffset2, bool* aDisconnected, NodeIndexCache* aIndexCache) { + uint32_t aOffset2, bool* aDisconnected, ComparePointsCache* aParent1Cache) { if (aParent1 == aParent2) { return aOffset1 < aOffset2 ? -1 : aOffset1 > aOffset2 ? 1 : 0; } @@ -3091,15 +3089,10 @@ int32_t nsContentUtils::ComparePoints_Deprecated( if (MOZ_UNLIKELY(child2->IsShadowRoot())) { return 1; } - Maybe child1Index; - Maybe child2Index; - if (aIndexCache) { - aIndexCache->ComputeIndicesOf(parent, child1, child2, child1Index, - child2Index); - } else { - child1Index = parent->ComputeIndexOf(child1); - child2Index = parent->ComputeIndexOf(child2); - } + const Maybe child1Index = + aParent1Cache ? aParent1Cache->ComputeIndexOf(parent, child1) + : parent->ComputeIndexOf(child1); + const Maybe child2Index = parent->ComputeIndexOf(child2); if (MOZ_LIKELY(child1Index.isSome() && child2Index.isSome())) { return *child1Index < *child2Index ? -1 : 1; } @@ -3117,9 +3110,7 @@ int32_t nsContentUtils::ComparePoints_Deprecated( if (!pos1) { const nsINode* child2 = parents2.ElementAt(--pos2); - const Maybe child2Index = - aIndexCache ? aIndexCache->ComputeIndexOf(parent, child2) - : parent->ComputeIndexOf(child2); + const Maybe child2Index = parent->ComputeIndexOf(child2); if (MOZ_UNLIKELY(NS_WARN_IF(child2Index.isNothing()))) { return 1; } @@ -3128,8 +3119,8 @@ int32_t nsContentUtils::ComparePoints_Deprecated( const nsINode* child1 = parents1.ElementAt(--pos1); const Maybe child1Index = - aIndexCache ? aIndexCache->ComputeIndexOf(parent, child1) - : parent->ComputeIndexOf(child1); + aParent1Cache ? aParent1Cache->ComputeIndexOf(parent, child1) + : parent->ComputeIndexOf(child1); if (MOZ_UNLIKELY(NS_WARN_IF(child1Index.isNothing()))) { return -1; } diff --git a/dom/base/nsContentUtils.h b/dom/base/nsContentUtils.h index 338fc097dede..46a89379a768 100644 --- a/dom/base/nsContentUtils.h +++ b/dom/base/nsContentUtils.h @@ -546,115 +546,26 @@ class nsContentUtils { mozilla::Maybe* aNode1Index = nullptr, mozilla::Maybe* aNode2Index = nullptr); - /** - * Cache implementation for ComparePoints(). - * - * This cache keeps the last cache_size child/index combinations - * in a stack-allocated array for fast lookup. - * If the cache is full, the entries are overridden, - * starting from the oldest entry. - * - * Note: This cache does not observe invalidation. As soon as script has - * run, this cache must not be used anymore. - * Also, this cache uses raw pointers. Beware! - */ - template - struct ResizableNodeIndexCache { - /** - * Looks up or computes two indices in one loop. - */ - void ComputeIndicesOf(const nsINode* aParent, const nsINode* aChild1, - const nsINode* aChild2, - mozilla::Maybe& aChild1Index, - mozilla::Maybe& aChild2Index) { - bool foundChild1 = false; - bool foundChild2 = false; - for (size_t cacheIndex = 0; cacheIndex < cache_size; ++cacheIndex) { - if (foundChild1 && foundChild2) { - return; - } - const nsINode* node = mNodes[cacheIndex]; - if (!node) { - // reached the end of not-fully-populated cache. - break; - } - if (!foundChild1 && node == aChild1) { - aChild1Index = mIndices[cacheIndex]; - foundChild1 = true; - continue; - } - if (!foundChild2 && node == aChild2) { - aChild2Index = mIndices[cacheIndex]; - foundChild2 = true; - continue; - } - } - if (!foundChild1) { - aChild1Index = ComputeAndInsertIndexIntoCache(aParent, aChild1); - } - if (!foundChild2) { - aChild2Index = ComputeAndInsertIndexIntoCache(aParent, aChild2); - } - } - /** - * Looks up or computes child index. - */ + struct ComparePointsCache { mozilla::Maybe ComputeIndexOf(const nsINode* aParent, const nsINode* aChild) { - for (size_t cacheIndex = 0; cacheIndex < cache_size; ++cacheIndex) { - const nsINode* node = mNodes[cacheIndex]; - if (!node) { - break; - } - if (node == aChild) { - return mIndices[cacheIndex]; - } + if (aParent == mParent && aChild == mChild) { + return mIndex; } - return ComputeAndInsertIndexIntoCache(aParent, aChild); - } - private: - /** - * Computes the index of aChild in aParent, inserts the index into the - * cache, and returns the index. - */ - mozilla::Maybe ComputeAndInsertIndexIntoCache( - const nsINode* aParent, const nsINode* aChild) { - mozilla::Maybe childIndex = aParent->ComputeIndexOf(aChild); - - mNodes[mNext] = aChild; - mIndices[mNext] = childIndex; - - ++mNext; - if (mNext == cache_size) { - // the last element of the cache has been reached. - // set mNext to 0 to start overriding the oldest cache entries. - mNext = 0; - } - return childIndex; + mIndex = aParent->ComputeIndexOf(aChild); + mParent = aParent; + mChild = aChild; + return mIndex; } - /// Node storage. The array is initialized to null - /// by the empty initializer list. - const nsINode* mNodes[cache_size]{}; - - mozilla::Maybe mIndices[cache_size]; - - /// The next element in the cache that will be written to. - /// If the cache is full (mNext == cache_size), - /// the oldest entries in the cache will be overridden, - /// ie. mNext will be set to 0. - size_t mNext{0}; + private: + const nsINode* mParent = nullptr; + const nsINode* mChild = nullptr; + mozilla::Maybe mIndex; }; /** - * Typedef with a reasonable default cache size. - * If Caches of different sizes are needed, - * ComparePoints would need to become templated. - */ - using NodeIndexCache = ResizableNodeIndexCache<100>; - - /** * Utility routine to compare two "points", where a point is a node/offset * pair. * Pass a cache object as aParent1Cache if you expect to repeatedly @@ -667,7 +578,7 @@ class nsContentUtils { */ static mozilla::Maybe ComparePoints( const nsINode* aParent1, uint32_t aOffset1, const nsINode* aParent2, - uint32_t aOffset2, NodeIndexCache* aIndexCache = nullptr); + uint32_t aOffset2, ComparePointsCache* aParent1Cache = nullptr); template static mozilla::Maybe ComparePoints( const mozilla::RangeBoundaryBase& aFirstBoundary, @@ -682,16 +593,13 @@ class nsContentUtils { * the result is 1, and the optional aDisconnected parameter * is set to true. * - * Pass a cache object as aIndexCache if you expect to repeatedly - * call this function. - * ComparePointsCache will store the last X (currently 100) node/index - * combinations in a stack-allocated array and does a lookup there - * before going into the expensive ComputeIndexOf() method. + * Pass a cache object as aParent1Cache if you expect to repeatedly + * call this function with the same value as aParent1. */ static int32_t ComparePoints_Deprecated( const nsINode* aParent1, uint32_t aOffset1, const nsINode* aParent2, uint32_t aOffset2, bool* aDisconnected = nullptr, - NodeIndexCache* aIndexCache = nullptr); + ComparePointsCache* aParent1Cache = nullptr); template static int32_t ComparePoints_Deprecated( const mozilla::RangeBoundaryBase& aFirstBoundary, diff --git a/dom/base/nsINode.cpp b/dom/base/nsINode.cpp index d5455e559639..b3cc6b3071b1 100644 --- a/dom/base/nsINode.cpp +++ b/dom/base/nsINode.cpp @@ -305,7 +305,7 @@ class IsItemInRangeComparator { // @param aStartOffset has to be less or equal to aEndOffset. IsItemInRangeComparator(const nsINode& aNode, const uint32_t aStartOffset, const uint32_t aEndOffset, - nsContentUtils::NodeIndexCache* aCache) + nsContentUtils::ComparePointsCache* aCache) : mNode(aNode), mStartOffset(aStartOffset), mEndOffset(aEndOffset), @@ -333,7 +333,7 @@ class IsItemInRangeComparator { const nsINode& mNode; const uint32_t mStartOffset; const uint32_t mEndOffset; - nsContentUtils::NodeIndexCache* mCache; + nsContentUtils::ComparePointsCache* mCache; }; bool nsINode::IsSelected(const uint32_t aStartOffset, @@ -368,7 +368,7 @@ bool nsINode::IsSelected(const uint32_t aStartOffset, } } - nsContentUtils::NodeIndexCache cache; + nsContentUtils::ComparePointsCache cache; IsItemInRangeComparator comparator{*this, aStartOffset, aEndOffset, &cache}; for (Selection* selection : ancestorSelections) { // Binary search the sorted ranges in this selection. @@ -1811,10 +1811,6 @@ Maybe nsINode::ComputeIndexOf(const nsINode* aPossibleChild) const { return Nothing(); } - if (aPossibleChild == GetFirstChild()) { - return Some(0); - } - if (aPossibleChild == GetLastChild()) { MOZ_ASSERT(GetChildCount()); return Some(GetChildCount() - 1); -- 2.11.4.GIT