diff options
Diffstat (limited to 'dom/base/FragmentDirective.cpp')
| -rw-r--r-- | dom/base/FragmentDirective.cpp | 879 |
1 files changed, 879 insertions, 0 deletions
diff --git a/dom/base/FragmentDirective.cpp b/dom/base/FragmentDirective.cpp new file mode 100644 index 0000000000..3300a85751 --- /dev/null +++ b/dom/base/FragmentDirective.cpp @@ -0,0 +1,879 @@ +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim:set ts=2 sw=2 sts=2 et cindent: */ +/* 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/. */ + +#include "FragmentDirective.h" +#include <cstdint> +#include "RangeBoundary.h" +#include "mozilla/Assertions.h" +#include "Document.h" +#include "mozilla/dom/FragmentDirectiveBinding.h" +#include "mozilla/dom/FragmentOrElement.h" +#include "mozilla/dom/NodeBinding.h" +#include "mozilla/dom/Text.h" +#include "mozilla/intl/WordBreaker.h" +#include "nsComputedDOMStyle.h" +#include "nsContentUtils.h" +#include "nsDOMAttributeMap.h" +#include "nsGkAtoms.h" +#include "nsICSSDeclaration.h" +#include "nsIFrame.h" +#include "nsINode.h" +#include "nsIURIMutator.h" +#include "nsRange.h" +#include "nsString.h" + +namespace mozilla::dom { +static LazyLogModule sFragmentDirectiveLog("FragmentDirective"); + +/** Converts a `TextDirective` into a percent-encoded string. */ +nsCString ToString(const TextDirective& aTextDirective) { + nsCString str; + create_text_directive(&aTextDirective, &str); + return str; +} + +NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE(FragmentDirective, mDocument) +NS_IMPL_CYCLE_COLLECTING_ADDREF(FragmentDirective) +NS_IMPL_CYCLE_COLLECTING_RELEASE(FragmentDirective) +NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(FragmentDirective) + NS_WRAPPERCACHE_INTERFACE_MAP_ENTRY + NS_INTERFACE_MAP_ENTRY(nsISupports) +NS_INTERFACE_MAP_END + +FragmentDirective::FragmentDirective(Document* aDocument) + : mDocument(aDocument) {} + +JSObject* FragmentDirective::WrapObject(JSContext* aCx, + JS::Handle<JSObject*> aGivenProto) { + return FragmentDirective_Binding::Wrap(aCx, this, aGivenProto); +} + +void FragmentDirective::ParseAndRemoveFragmentDirectiveFromFragment( + nsCOMPtr<nsIURI>& aURI, nsTArray<TextDirective>* aTextDirectives) { + if (!aURI || !StaticPrefs::dom_text_fragments_enabled()) { + return; + } + bool hasRef = false; + aURI->GetHasRef(&hasRef); + if (!hasRef) { + return; + } + + nsAutoCString hash; + aURI->GetRef(hash); + + ParsedFragmentDirectiveResult fragmentDirective; + const bool hasRemovedFragmentDirective = + parse_fragment_directive(&hash, &fragmentDirective); + if (!hasRemovedFragmentDirective) { + return; + } + Unused << NS_MutateURI(aURI) + .SetRef(fragmentDirective.url_without_fragment_directive) + .Finalize(aURI); + if (aTextDirectives) { + aTextDirectives->SwapElements(fragmentDirective.text_directives); + } +} + +nsTArray<RefPtr<nsRange>> FragmentDirective::FindTextFragmentsInDocument() { + MOZ_ASSERT(mDocument); + mDocument->FlushPendingNotifications(FlushType::Frames); + nsTArray<RefPtr<nsRange>> textDirectiveRanges; + for (const TextDirective& textDirective : mUninvokedTextDirectives) { + if (RefPtr<nsRange> range = FindRangeForTextDirective(textDirective)) { + textDirectiveRanges.AppendElement(range); + } + } + mUninvokedTextDirectives.Clear(); + return textDirectiveRanges; +} + +/** + * @brief Determine if `aNode` should be considered when traversing the DOM. + * + * A node is "search invisible" if it is an element in the HTML namespace and + * 1. The computed value of its `display` property is `none` + * 2. It serializes as void + * 3. It is one of the following types: + * - HTMLIFrameElement + * - HTMLImageElement + * - HTMLMeterElement + * - HTMLObjectElement + * - HTMLProgressElement + * - HTMLStyleElement + * - HTMLScriptElement + * - HTMLVideoElement + * - HTMLAudioElement + * 4. It is a `select` element whose `multiple` content attribute is absent + * + * see https://wicg.github.io/scroll-to-text-fragment/#search-invisible + */ +bool NodeIsSearchInvisible(nsINode& aNode) { + if (!aNode.IsElement()) { + return false; + } + // 2. If the node serializes as void. + nsAtom* nodeNameAtom = aNode.NodeInfo()->NameAtom(); + if (FragmentOrElement::IsHTMLVoid(nodeNameAtom)) { + return true; + } + // 3. Is any of the following types: HTMLIFrameElement, HTMLImageElement, + // HTMLMeterElement, HTMLObjectElement, HTMLProgressElement, HTMLStyleElement, + // HTMLScriptElement, HTMLVideoElement, HTMLAudioElement + if (aNode.IsAnyOfHTMLElements( + nsGkAtoms::iframe, nsGkAtoms::image, nsGkAtoms::meter, + nsGkAtoms::object, nsGkAtoms::progress, nsGkAtoms::style, + nsGkAtoms::script, nsGkAtoms::video, nsGkAtoms::audio)) { + return true; + } + // 4. Is a select element whose multiple content attribute is absent. + if (aNode.IsHTMLElement(nsGkAtoms::select)) { + return aNode.GetAttributes()->GetNamedItem(u"multiple"_ns) == nullptr; + } + // This is tested last because it's the most expensive check. + // 1. The computed value of its 'display' property is 'none'. + const Element* nodeAsElement = Element::FromNode(aNode); + const RefPtr<const ComputedStyle> computedStyle = + nsComputedDOMStyle::GetComputedStyleNoFlush(nodeAsElement); + return !computedStyle || + computedStyle->StyleDisplay()->mDisplay == StyleDisplay::None; +} + +/** + * @brief Returns true if `aNode` has block-level display. + * A node has block-level display if it is an element and the computed value + * of its display property is any of + * - block + * - table + * - flow-root + * - grid + * - flex + * - list-item + * + * See https://wicg.github.io/scroll-to-text-fragment/#has-block-level-display + */ +bool NodeHasBlockLevelDisplay(nsINode& aNode) { + if (!aNode.IsElement()) { + return false; + } + const Element* nodeAsElement = Element::FromNode(aNode); + const RefPtr<const ComputedStyle> computedStyle = + nsComputedDOMStyle::GetComputedStyleNoFlush(nodeAsElement); + if (!computedStyle) { + return false; + } + const StyleDisplay& styleDisplay = computedStyle->StyleDisplay()->mDisplay; + return styleDisplay == StyleDisplay::Block || + styleDisplay == StyleDisplay::Table || + styleDisplay == StyleDisplay::FlowRoot || + styleDisplay == StyleDisplay::Grid || + styleDisplay == StyleDisplay::Flex || styleDisplay.IsListItem(); +} + +/** + * @brief Get the Block Ancestor For `aNode`. + * + * see https://wicg.github.io/scroll-to-text-fragment/#nearest-block-ancestor + */ +nsINode* GetBlockAncestorForNode(nsINode* aNode) { + // 1. Let curNode be node. + RefPtr<nsINode> curNode = aNode; + // 2. While curNode is non-null + while (curNode) { + // 2.1. If curNode is not a Text node and it has block-level display then + // return curNode. + if (!curNode->IsText() && NodeHasBlockLevelDisplay(*curNode)) { + return curNode; + } + // 2.2. Otherwise, set curNode to curNode’s parent. + curNode = curNode->GetParentNode(); + } + // 3.Return node’s node document's document element. + return aNode->GetOwnerDocument(); +} + +/** + * @brief Returns true if `aNode` is part of a non-searchable subtree. + * + * A node is part of a non-searchable subtree if it is or has a shadow-including + * ancestor that is search invisible. + * + * see https://wicg.github.io/scroll-to-text-fragment/#non-searchable-subtree + */ +bool NodeIsPartOfNonSearchableSubTree(nsINode& aNode) { + nsINode* node = &aNode; + do { + if (NodeIsSearchInvisible(*node)) { + return true; + } + } while ((node = node->GetParentOrShadowHostNode())); + return false; +} + +/** + * @brief Return true if `aNode` is a visible Text node. + * + * A node is a visible text node if it is a Text node, the computed value of + * its parent element's visibility property is visible, and it is being + * rendered. + * + * see https://wicg.github.io/scroll-to-text-fragment/#visible-text-node + */ +bool NodeIsVisibleTextNode(const nsINode& aNode) { + const Text* text = Text::FromNode(aNode); + if (!text) { + return false; + } + const nsIFrame* frame = text->GetPrimaryFrame(); + return frame && frame->StyleVisibility()->IsVisible(); +} + +enum class TextScanDirection { Left = -1, Right = 1 }; + +/** + * @brief Tests if there is whitespace at the given position and direction. + * + * This algorithm tests for whitespaces and ` ` at `aPos`. + * It returns the size of the whitespace found at the position, i.e. 5/6 for + * ` /;` and 1 otherwise. + * + * This function follows a subsection of this section of the spec, but has been + * adapted to be able to scan in both directions: + * https://wicg.github.io/scroll-to-text-fragment/#next-non-whitespace-position + */ +uint32_t IsWhitespaceAtPosition(nsString& aText, uint32_t aPos, + TextScanDirection aDirection) { + if (aText.Length() == 0) { + return 0; + } + if (aDirection == TextScanDirection::Right) { + if (aText.Length() > (aPos + 5)) { + if (Substring(aText, aPos, 5).Equals(u" ")) { + return aText.Length() > (aPos + 6) && aText.CharAt(aPos + 6) == u';' + ? 6 + : 5; + } + } + } else { + if (aPos > 6 && Substring(aText, aPos - 6, 6).Equals(u" ")) { + return 6; + } + if (aPos > 5 && Substring(aText, aPos - 5, 5).Equals(u" ")) { + return 5; + } + } + return uint32_t(IsSpaceCharacter(aText.CharAt(aPos))); +} + +/** Advances the start of `aRange` to the next non-whitespace position. + * The function follows this section of the spec: + * https://wicg.github.io/scroll-to-text-fragment/#next-non-whitespace-position + */ +void AdvanceStartToNextNonWhitespacePosition(nsRange& aRange) { + // 1. While range is not collapsed: + while (!aRange.Collapsed()) { + // 1.1. Let node be range's start node. + RefPtr<nsINode> node = aRange.GetStartContainer(); + MOZ_ASSERT(node); + // 1.2. Let offset be range's start offset. + const uint32_t offset = aRange.StartOffset(); + // 1.3. If node is part of a non-searchable subtree or if node is not a + // visible text node or if offset is equal to node's length then: + if (NodeIsPartOfNonSearchableSubTree(*node) || + !NodeIsVisibleTextNode(*node) || offset == node->Length()) { + // 1.3.1. Set range's start node to the next node, in shadow-including + // tree order. + // 1.3.2. Set range's start offset to 0. + if (NS_FAILED(aRange.SetStart(node->GetNextNode(), 0))) { + return; + } + // 1.3.3. Continue. + continue; + } + const Text* text = Text::FromNode(node); + nsAutoString textData; + text->GetData(textData); + // These steps are moved to `IsWhitespaceAtPosition()`. + // 1.4. If the substring data of node at offset offset and count 6 is equal + // to the string " " then: + // 1.4.1. Add 6 to range’s start offset. + // 1.5. Otherwise, if the substring data of node at offset offset and count + // 5 is equal to the string " " then: + // 1.5.1. Add 5 to range’s start offset. + // 1.6. Otherwise: + // 1.6.1 Let cp be the code point at the offset index in node’s data. + // 1.6.2 If cp does not have the White_Space property set, return. + // 1.6.3 Add 1 to range’s start offset. + const uint32_t whitespace = + IsWhitespaceAtPosition(textData, offset, TextScanDirection::Right); + if (whitespace == 0) { + return; + } + + aRange.SetStart(node, offset + whitespace); + } +} + +/** + * @brief Moves `aRangeBoundary` one word in `aDirection`. + * + * Word boundaries are determined using `intl::WordBreaker::FindWord()`. + * + * + * @param aRangeBoundary[in] The range boundary that should be moved. + * Must be set and valid. + * @param aDirection[in] The direction into which to move. + * @return A new `RangeBoundary` which is moved to the next word. + */ +RangeBoundary MoveRangeBoundaryOneWord(const RangeBoundary& aRangeBoundary, + TextScanDirection aDirection) { + MOZ_ASSERT(aRangeBoundary.IsSetAndValid()); + RefPtr<nsINode> curNode = aRangeBoundary.Container(); + uint32_t offset = *aRangeBoundary.Offset( + RangeBoundary::OffsetFilter::kValidOrInvalidOffsets); + + const int offsetIncrement = int(aDirection); + // Get the text node of the start of the range and the offset. + // This is the current position of the start of the range. + nsAutoString text; + if (NodeIsVisibleTextNode(*curNode)) { + const Text* textNode = Text::FromNode(curNode); + textNode->GetData(text); + + // Assuming that the current position might not be at a word boundary, + // advance to the word boundary at word begin/end. + if (!IsWhitespaceAtPosition(text, offset, aDirection)) { + const intl::WordRange wordRange = + intl::WordBreaker::FindWord(text, offset); + if (aDirection == TextScanDirection::Right && + offset != wordRange.mBegin) { + offset = wordRange.mEnd; + } else if (aDirection == TextScanDirection::Left && + offset != wordRange.mEnd) { + // The additional -1 is necessary to move to offset to *before* the + // start of the word. + offset = wordRange.mBegin - 1; + } + } + } + // Now, skip any whitespace, so that `offset` points to the word boundary of + // the next word (which is the one this algorithm actually aims to move over). + while (curNode) { + if (!NodeIsVisibleTextNode(*curNode) || NodeIsSearchInvisible(*curNode) || + offset >= curNode->Length()) { + curNode = aDirection == TextScanDirection::Left ? curNode->GetPrevNode() + : curNode->GetNextNode(); + if (!curNode) { + break; + } + offset = + aDirection == TextScanDirection::Left ? curNode->Length() - 1 : 0; + if (const Text* textNode = Text::FromNode(curNode)) { + textNode->GetData(text); + } + continue; + } + if (const uint32_t whitespace = + IsWhitespaceAtPosition(text, offset, aDirection)) { + offset += offsetIncrement * whitespace; + continue; + } + + // At this point, the caret has been moved to the next non-whitespace + // position. + // find word boundaries at the current position + const intl::WordRange wordRange = intl::WordBreaker::FindWord(text, offset); + offset = aDirection == TextScanDirection::Left ? wordRange.mBegin + : wordRange.mEnd; + + return {curNode, offset}; + } + return {}; +} + +RefPtr<nsRange> FragmentDirective::FindRangeForTextDirective( + const TextDirective& aTextDirective) { + MOZ_LOG(sFragmentDirectiveLog, LogLevel::Info, + ("FragmentDirective::%s(): Find range for text directive '%s'.", + __FUNCTION__, ToString(aTextDirective).Data())); + // 1. Let searchRange be a range with start (document, 0) and end (document, + // document’s length) + ErrorResult rv; + RefPtr<nsRange> searchRange = + nsRange::Create(mDocument, 0, mDocument, mDocument->Length(), rv); + if (rv.Failed()) { + return nullptr; + } + // 2. While searchRange is not collapsed: + while (!searchRange->Collapsed()) { + // 2.1. Let potentialMatch be null. + RefPtr<nsRange> potentialMatch; + // 2.2. If parsedValues’s prefix is not null: + if (!aTextDirective.prefix.IsEmpty()) { + // 2.2.1. Let prefixMatch be the the result of running the find a string + // in range steps with query parsedValues’s prefix, searchRange + // searchRange, wordStartBounded true and wordEndBounded false. + RefPtr<nsRange> prefixMatch = + FindStringInRange(searchRange, aTextDirective.prefix, true, false); + // 2.2.2. If prefixMatch is null, return null. + if (!prefixMatch) { + return nullptr; + } + // 2.2.3. Set searchRange’s start to the first boundary point after + // prefixMatch’s start + const RangeBoundary boundaryPoint = MoveRangeBoundaryOneWord( + {prefixMatch->GetStartContainer(), prefixMatch->StartOffset()}, + TextScanDirection::Right); + if (!boundaryPoint.IsSetAndValid()) { + return nullptr; + } + searchRange->SetStart(boundaryPoint.AsRaw(), rv); + if (rv.Failed()) { + return nullptr; + } + + // 2.2.4. Let matchRange be a range whose start is prefixMatch’s end and + // end is searchRange’s end. + RefPtr<nsRange> matchRange = nsRange::Create( + prefixMatch->GetEndContainer(), prefixMatch->EndOffset(), + searchRange->GetEndContainer(), searchRange->EndOffset(), rv); + if (rv.Failed()) { + return nullptr; + } + // 2.2.5. Advance matchRange’s start to the next non-whitespace position. + AdvanceStartToNextNonWhitespacePosition(*matchRange); + // 2.2.6. If matchRange is collapsed return null. + // (This can happen if prefixMatch’s end or its subsequent non-whitespace + // position is at the end of the document.) + if (matchRange->Collapsed()) { + return nullptr; + } + // 2.2.7. Assert: matchRange’s start node is a Text node. + // (matchRange’s start now points to the next non-whitespace text data + // following a matched prefix.) + MOZ_ASSERT(matchRange->GetStartContainer()->IsText()); + + // 2.2.8. Let mustEndAtWordBoundary be true if parsedValues’s end is + // non-null or parsedValues’s suffix is null, false otherwise. + const bool mustEndAtWordBoundary = + !aTextDirective.end.IsEmpty() || aTextDirective.suffix.IsEmpty(); + // 2.2.9. Set potentialMatch to the result of running the find a string in + // range steps with query parsedValues’s start, searchRange matchRange, + // wordStartBounded false, and wordEndBounded mustEndAtWordBoundary. + potentialMatch = FindStringInRange(matchRange, aTextDirective.start, + false, mustEndAtWordBoundary); + // 2.2.10. If potentialMatch is null, return null. + if (!potentialMatch) { + return nullptr; + } + // 2.2.11. If potentialMatch’s start is not matchRange’s start, then + // continue. + // (In this case, we found a prefix but it was followed by something other + // than a matching text so we’ll continue searching for the next instance + // of prefix.) + if (potentialMatch->GetStartContainer() != + matchRange->GetStartContainer()) { + continue; + } + } + // 2.3. Otherwise: + else { + // 2.3.1. Let mustEndAtWordBoundary be true if parsedValues’s end is + // non-null or parsedValues’s suffix is null, false otherwise. + const bool mustEndAtWordBoundary = + !aTextDirective.end.IsEmpty() || aTextDirective.suffix.IsEmpty(); + // 2.3.2. Set potentialMatch to the result of running the find a string in + // range steps with query parsedValues’s start, searchRange searchRange, + // wordStartBounded true, and wordEndBounded mustEndAtWordBoundary. + potentialMatch = FindStringInRange(searchRange, aTextDirective.start, + true, mustEndAtWordBoundary); + // 2.3.3. If potentialMatch is null, return null. + if (!potentialMatch) { + return nullptr; + } + // 2.3.4. Set searchRange’s start to the first boundary point after + // potentialMatch’s start + RangeBoundary newRangeBoundary = MoveRangeBoundaryOneWord( + {potentialMatch->GetStartContainer(), potentialMatch->StartOffset()}, + TextScanDirection::Right); + if (!newRangeBoundary.IsSetAndValid()) { + return nullptr; + } + searchRange->SetStart(newRangeBoundary.AsRaw(), rv); + if (rv.Failed()) { + return nullptr; + } + } + // 2.4. Let rangeEndSearchRange be a range whose start is potentialMatch’s + // end and whose end is searchRange’s end. + RefPtr<nsRange> rangeEndSearchRange = nsRange::Create( + potentialMatch->GetEndContainer(), potentialMatch->EndOffset(), + searchRange->GetEndContainer(), searchRange->EndOffset(), rv); + if (rv.Failed()) { + return nullptr; + } + // 2.5. While rangeEndSearchRange is not collapsed: + while (!rangeEndSearchRange->Collapsed()) { + // 2.5.1. If parsedValues’s end item is non-null, then: + if (!aTextDirective.end.IsEmpty()) { + // 2.5.1.1. Let mustEndAtWordBoundary be true if parsedValues’s suffix + // is null, false otherwise. + const bool mustEndAtWordBoundary = aTextDirective.suffix.IsEmpty(); + // 2.5.1.2. Let endMatch be the result of running the find a string in + // range steps with query parsedValues’s end, searchRange + // rangeEndSearchRange, wordStartBounded true, and wordEndBounded + // mustEndAtWordBoundary. + RefPtr<nsRange> endMatch = + FindStringInRange(rangeEndSearchRange, aTextDirective.end, true, + mustEndAtWordBoundary); + // 2.5.1.3. If endMatch is null then return null. + if (!endMatch) { + return nullptr; + } + // 2.5.1.4. Set potentialMatch’s end to endMatch’s end. + potentialMatch->SetEnd(endMatch->GetEndContainer(), + endMatch->EndOffset()); + } + // 2.5.2. Assert: potentialMatch is non-null, not collapsed and represents + // a range exactly containing an instance of matching text. + MOZ_ASSERT(potentialMatch && !potentialMatch->Collapsed()); + + // 2.5.3. If parsedValues’s suffix is null, return potentialMatch. + if (aTextDirective.suffix.IsEmpty()) { + return potentialMatch; + } + // 2.5.4. Let suffixRange be a range with start equal to potentialMatch’s + // end and end equal to searchRange’s end. + RefPtr<nsRange> suffixRange = nsRange::Create( + potentialMatch->GetEndContainer(), potentialMatch->EndOffset(), + searchRange->GetEndContainer(), searchRange->EndOffset(), rv); + if (rv.Failed()) { + return nullptr; + } + // 2.5.5. Advance suffixRange's start to the next non-whitespace position. + AdvanceStartToNextNonWhitespacePosition(*suffixRange); + + // 2.5.6. Let suffixMatch be result of running the find a string in range + // steps with query parsedValue's suffix, searchRange suffixRange, + // wordStartBounded false, and wordEndBounded true. + RefPtr<nsRange> suffixMatch = + FindStringInRange(suffixRange, aTextDirective.suffix, false, true); + + // 2.5.7. If suffixMatch is null, return null. + // (If the suffix doesn't appear in the remaining text of the document, + // there's no possible way to make a match.) + if (!suffixMatch) { + return nullptr; + } + // 2.5.8. If suffixMatch's start is suffixRange's start, return + // potentialMatch. + if (suffixMatch->GetStartContainer() == + suffixRange->GetStartContainer() && + suffixMatch->StartOffset() == suffixRange->StartOffset()) { + return potentialMatch; + } + // 2.5.9. If parsedValue's end item is null then break; + // (If this is an exact match and the suffix doesn’t match, start + // searching for the next range start by breaking out of this loop without + // rangeEndSearchRange being collapsed. If we’re looking for a range + // match, we’ll continue iterating this inner loop since the range start + // will already be correct.) + if (aTextDirective.end.IsEmpty()) { + break; + } + // 2.5.10. Set rangeEndSearchRange's start to potentialMatch's end. + // (Otherwise, it is possible that we found the correct range start, but + // not the correct range end. Continue the inner loop to keep searching + // for another matching instance of rangeEnd.) + rangeEndSearchRange->SetStart(potentialMatch->GetEndContainer(), + potentialMatch->EndOffset()); + } + // 2.6. If rangeEndSearchRange is collapsed then: + if (rangeEndSearchRange->Collapsed()) { + // 2.6.1. Assert parsedValue's end item is non-null. + // (This can only happen for range matches due to the break for exact + // matches in step 9 of the above loop. If we couldn’t find a valid + // rangeEnd+suffix pair anywhere in the doc then there’s no possible way + // to make a match.) + // XXX(:jjaschke): should this really assert? + MOZ_ASSERT(!aTextDirective.end.IsEmpty()); + } + } + // 3. Return null. + return nullptr; +} + +/** + * @brief Convenience function that returns true if the given position in a + * string is a word boundary. + * + * This is a thin wrapper around the `WordBreaker::FindWord()` function. + * + * @param aText The text input. + * @param aPosition The position to check. + * @return true if there is a word boundary at `aPosition`. + * @return false otherwise. + */ +bool IsAtWordBoundary(const nsAString& aText, uint32_t aPosition) { + const intl::WordRange wordRange = + intl::WordBreaker::FindWord(aText, aPosition); + return wordRange.mBegin == aPosition || wordRange.mEnd == aPosition; +} + +enum class IsEndIndex : bool { No, Yes }; +RangeBoundary GetBoundaryPointAtIndex( + uint32_t aIndex, const nsTArray<RefPtr<Text>>& aTextNodeList, + IsEndIndex aIsEndIndex) { + // 1. Let counted be 0. + uint32_t counted = 0; + // 2. For each curNode of nodes: + for (Text* curNode : aTextNodeList) { + // 2.1. Let nodeEnd be counted + curNode’s length. + uint32_t nodeEnd = counted + curNode->Length(); + // 2.2. If isEnd is true, add 1 to nodeEnd. + if (aIsEndIndex == IsEndIndex::Yes) { + ++nodeEnd; + } + // 2.3. If nodeEnd is greater than index then: + if (nodeEnd > aIndex) { + // 2.3.1. Return the boundary point (curNode, index − counted). + return RangeBoundary(curNode->AsNode(), aIndex - counted); + } + // 2.4. Increment counted by curNode’s length. + counted += curNode->Length(); + } + return {}; +} + +RefPtr<nsRange> FindRangeFromNodeList( + nsRange* aSearchRange, const nsAString& aQuery, + const nsTArray<RefPtr<Text>>& aTextNodeList, bool aWordStartBounded, + bool aWordEndBounded) { + // 1. Let searchBuffer be the concatenation of the data of each item in nodes. + // XXX(:jjaschke): There's an open issue here that deals with what + // data is supposed to be (text data vs. rendered text) + // https://github.com/WICG/scroll-to-text-fragment/issues/98 + uint32_t bufferLength = 0; + for (const Text* text : aTextNodeList) { + bufferLength += text->Length(); + } + // bail out if the search query is longer than the text data. + if (bufferLength < aQuery.Length()) { + return nullptr; + } + nsAutoString searchBuffer; + searchBuffer.SetCapacity(bufferLength); + for (Text* text : aTextNodeList) { + text->AppendTextTo(searchBuffer); + } + // 2. Let searchStart be 0. + // 3. If the first item in nodes is searchRange’s start node then set + // searchStart to searchRange’s start offset. + uint32_t searchStart = + aTextNodeList.SafeElementAt(0) == aSearchRange->GetStartContainer() + ? aSearchRange->StartOffset() + : 0; + + // 4. Let start and end be boundary points, initially null. + RangeBoundary start, end; + // 5. Let matchIndex be null. + // "null" here doesn't mean 0, instead "not set". 0 would be a valid index. + // Therefore, "null" is represented by the value -1. + int32_t matchIndex = -1; + + // 6. While matchIndex is null + // As explained above, "null" == -1 in this algorithm. + while (matchIndex == -1) { + // 6.1. Set matchIndex to the index of the first instance of queryString in + // searchBuffer, starting at searchStart. The string search must be + // performed using a base character comparison, or the primary level, as + // defined in [UTS10]. + // [UTS10] + // Ken Whistler; Markus Scherer.Unicode Collation Algorithm.26 August 2022. + // Unicode Technical Standard #10. + // URL : https://www.unicode.org/reports/tr10/tr10-47.html + + // XXX(:jjaschke): For the initial implementation, a standard case-sensitive + // find-in-string is used. + // See: https://github.com/WICG/scroll-to-text-fragment/issues/233 + matchIndex = searchBuffer.Find(aQuery, searchStart); + // 6.2. If matchIndex is null, return null. + if (matchIndex == -1) { + return nullptr; + } + + // 6.3. Let endIx be matchIndex + queryString’s length. + // endIx is the index of the last character in the match + 1. + const uint32_t endIx = matchIndex + aQuery.Length(); + + // 6.4. Set start to the boundary point result of get boundary point at + // index matchIndex run over nodes with isEnd false. + start = GetBoundaryPointAtIndex(matchIndex, aTextNodeList, IsEndIndex::No); + // 6.5. Set end to the boundary point result of get boundary point at index + // endIx run over nodes with isEnd true. + end = GetBoundaryPointAtIndex(endIx, aTextNodeList, IsEndIndex::Yes); + + // 6.6. If wordStartBounded is true and matchIndex is not at a word boundary + // in searchBuffer, given the language from start’s node as the locale; or + // wordEndBounded is true and matchIndex + queryString’s length is not at a + // word boundary in searchBuffer, given the language from end’s node as the + // locale: + if ((aWordStartBounded && !IsAtWordBoundary(searchBuffer, matchIndex)) || + (aWordEndBounded && !IsAtWordBoundary(searchBuffer, endIx))) { + // 6.6.1. Set searchStart to matchIndex + 1. + searchStart = matchIndex + 1; + // 6.6.2. Set matchIndex to null. + matchIndex = -1; + } + } + // 7. Let endInset be 0. + // 8. If the last item in nodes is searchRange’s end node then set endInset + // to (searchRange’s end node's length − searchRange’s end offset) + // (endInset is the offset from the last position in the last node in the + // reverse direction. Alternatively, it is the length of the node that’s not + // included in the range.) + uint32_t endInset = + aTextNodeList.LastElement() == aSearchRange->GetEndContainer() + ? aSearchRange->GetEndContainer()->Length() - + aSearchRange->EndOffset() + : 0; + + // 9. If matchIndex + queryString’s length is greater than searchBuffer’s + // length − endInset return null. + // (If the match runs past the end of the search range, return null.) + if (matchIndex + aQuery.Length() > searchBuffer.Length() - endInset) { + return nullptr; + } + + // 10. Assert: start and end are non-null, valid boundary points in + // searchRange. + MOZ_ASSERT(start.IsSetAndValid()); + MOZ_ASSERT(end.IsSetAndValid()); + + // 11. Return a range with start start and end end. + ErrorResult rv; + RefPtr<nsRange> range = nsRange::Create(start, end, rv); + if (rv.Failed()) { + return nullptr; + } + + return range; +} + +RefPtr<nsRange> FragmentDirective::FindStringInRange(nsRange* aSearchRange, + const nsAString& aQuery, + bool aWordStartBounded, + bool aWordEndBounded) { + MOZ_ASSERT(aSearchRange); + RefPtr<nsRange> searchRange = aSearchRange->CloneRange(); + // 1. While searchRange is not collapsed + while (searchRange && !searchRange->Collapsed()) { + // 1.1. Let curNode be searchRange’s start node. + RefPtr<nsINode> curNode = searchRange->GetStartContainer(); + + // 1.2. If curNode is part of a non-searchable subtree: + if (NodeIsPartOfNonSearchableSubTree(*curNode)) { + // 1.2.1. Set searchRange’s start node to the next node, in + // shadow-including tree order, that isn’t a shadow-including descendant + // of curNode. + RefPtr<nsINode> next = curNode; + while ((next = next->GetNextNode())) { + if (!next->IsShadowIncludingInclusiveDescendantOf(curNode)) { + break; + } + } + if (!next) { + return nullptr; + } + // 1.2.2. Set `searchRange`s `start offset` to 0 + searchRange->SetStart(next, 0); + // 1.2.3. continue. + continue; + } + // 1.3. If curNode is not a visible TextNode: + if (!NodeIsVisibleTextNode(*curNode)) { + // 1.3.1. Set searchRange’s start node to the next node, in + // shadow-including tree order, that is not a doctype. + RefPtr<nsINode> next = curNode; + while ((next = next->GetNextNode())) { + if (next->NodeType() != Node_Binding::DOCUMENT_TYPE_NODE) { + break; + } + } + if (!next) { + return nullptr; + } + // 1.3.2. Set searchRange’s start offset to 0. + searchRange->SetStart(next, 0); + // 1.3.3. continue. + continue; + } + // 1.4. Let blockAncestor be the nearest block ancestor of `curNode` + RefPtr<nsINode> blockAncestor = GetBlockAncestorForNode(curNode); + + // 1.5. Let textNodeList be a list of Text nodes, initially empty. + nsTArray<RefPtr<Text>> textNodeList; + // 1.6. While curNode is a shadow-including descendant of blockAncestor and + // the position of the boundary point (curNode,0) is not after searchRange's + // end: + while (curNode && + curNode->IsShadowIncludingInclusiveDescendantOf(blockAncestor)) { + Maybe<int32_t> comp = nsContentUtils::ComparePoints( + curNode, 0, searchRange->GetEndContainer(), searchRange->EndOffset()); + if (comp) { + if (*comp >= 0) { + break; + } + } else { + // This means that the compared nodes are disconnected. + return nullptr; + } + // 1.6.1. If curNode has block-level display, then break. + if (NodeHasBlockLevelDisplay(*curNode)) { + break; + } + // 1.6.2. If curNode is search invisible: + if (NodeIsSearchInvisible(*curNode)) { + // 1.6.2.1. Set curNode to the next node, in shadow-including tree + // order, that isn't a shadow-including descendant of curNode. + curNode = curNode->GetNextNode(); + // 1.6.2.2. Continue. + continue; + } + // 1.6.3. If curNode is a visible text node then append it to + // textNodeList. + if (NodeIsVisibleTextNode(*curNode)) { + textNodeList.AppendElement(curNode->AsText()); + } + // 1.6.4. Set curNode to the next node in shadow-including + // tree order. + curNode = curNode->GetNextNode(); + } + // 1.7. Run the find a range from a node list steps given + // query, searchRange, textNodeList, wordStartBounded, wordEndBounded as + // input. If the resulting Range is not null, then return it. + if (RefPtr<nsRange> range = + FindRangeFromNodeList(searchRange, aQuery, textNodeList, + aWordStartBounded, aWordEndBounded)) { + return range; + } + + // 1.8. If curNode is null, then break. + if (!curNode) { + break; + } + + // 1.9. Assert: curNode follows searchRange's start node. + + // 1.10. Set searchRange's start to the boundary point (curNode,0). + searchRange->SetStart(curNode, 0); + } + + // 2. Return null. + return nullptr; +} +} // namespace mozilla::dom |