diff options
Diffstat (limited to '')
| -rw-r--r-- | accessible/base/TextRange.cpp | 483 |
1 files changed, 483 insertions, 0 deletions
diff --git a/accessible/base/TextRange.cpp b/accessible/base/TextRange.cpp new file mode 100644 index 0000000000..9a62a61712 --- /dev/null +++ b/accessible/base/TextRange.cpp @@ -0,0 +1,483 @@ +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=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/. */ + +#include "TextRange-inl.h" + +#include "LocalAccessible-inl.h" +#include "HyperTextAccessible-inl.h" +#include "mozilla/IntegerRange.h" +#include "mozilla/dom/Selection.h" +#include "nsAccUtils.h" + +namespace mozilla { +namespace a11y { + +/** + * Returns a text point for aAcc within aContainer. + */ +static void ToTextPoint(Accessible* aAcc, Accessible** aContainer, + int32_t* aOffset, bool aIsBefore = true) { + if (aAcc->IsHyperText()) { + *aContainer = aAcc; + *aOffset = + aIsBefore + ? 0 + : static_cast<int32_t>(aAcc->AsHyperTextBase()->CharacterCount()); + return; + } + + Accessible* child = nullptr; + Accessible* parent = aAcc; + do { + child = parent; + parent = parent->Parent(); + } while (parent && !parent->IsHyperText()); + + if (parent) { + *aContainer = parent; + *aOffset = parent->AsHyperTextBase()->GetChildOffset( + child->IndexInParent() + static_cast<int32_t>(!aIsBefore)); + } +} + +//////////////////////////////////////////////////////////////////////////////// +// TextPoint + +bool TextPoint::operator<(const TextPoint& aPoint) const { + if (mContainer == aPoint.mContainer) return mOffset < aPoint.mOffset; + + // Build the chain of parents + Accessible* p1 = mContainer; + Accessible* p2 = aPoint.mContainer; + AutoTArray<Accessible*, 30> parents1, parents2; + do { + parents1.AppendElement(p1); + p1 = p1->Parent(); + } while (p1); + do { + parents2.AppendElement(p2); + p2 = p2->Parent(); + } while (p2); + + // Find where the parent chain differs + uint32_t pos1 = parents1.Length(), pos2 = parents2.Length(); + for (uint32_t len = std::min(pos1, pos2); len > 0; --len) { + Accessible* child1 = parents1.ElementAt(--pos1); + Accessible* child2 = parents2.ElementAt(--pos2); + if (child1 != child2) { + return child1->IndexInParent() < child2->IndexInParent(); + } + } + + if (pos1 != 0) { + // If parents1 is a superset of parents2 then mContainer is a + // descendant of aPoint.mContainer. The next element down in parents1 + // is mContainer's ancestor that is the child of aPoint.mContainer. + // We compare its end offset in aPoint.mContainer with aPoint.mOffset. + Accessible* child = parents1.ElementAt(pos1 - 1); + MOZ_ASSERT(child->Parent() == aPoint.mContainer); + return child->EndOffset() < static_cast<uint32_t>(aPoint.mOffset); + } + + if (pos2 != 0) { + // If parents2 is a superset of parents1 then aPoint.mContainer is a + // descendant of mContainer. The next element down in parents2 + // is aPoint.mContainer's ancestor that is the child of mContainer. + // We compare its start offset in mContainer with mOffset. + Accessible* child = parents2.ElementAt(pos2 - 1); + MOZ_ASSERT(child->Parent() == mContainer); + return static_cast<uint32_t>(mOffset) < child->StartOffset(); + } + + NS_ERROR("Broken tree?!"); + return false; +} + +//////////////////////////////////////////////////////////////////////////////// +// TextRange + +TextRange::TextRange(Accessible* aRoot, Accessible* aStartContainer, + int32_t aStartOffset, Accessible* aEndContainer, + int32_t aEndOffset) + : mRoot(aRoot), + mStartContainer(aStartContainer), + mEndContainer(aEndContainer), + mStartOffset(aStartOffset), + mEndOffset(aEndOffset) {} + +void TextRange::EmbeddedChildren(nsTArray<Accessible*>* aChildren) const { + HyperTextAccessibleBase* startHyper = mStartContainer->AsHyperTextBase(); + if (mStartContainer == mEndContainer) { + int32_t startIdx = startHyper->GetChildIndexAtOffset(mStartOffset); + int32_t endIdx = startHyper->GetChildIndexAtOffset(mEndOffset); + for (int32_t idx = startIdx; idx <= endIdx; idx++) { + Accessible* child = mStartContainer->ChildAt(idx); + if (!child->IsText()) { + aChildren->AppendElement(child); + } + } + return; + } + + Accessible* p1 = startHyper->GetChildAtOffset(mStartOffset); + HyperTextAccessibleBase* endHyper = mEndContainer->AsHyperTextBase(); + Accessible* p2 = endHyper->GetChildAtOffset(mEndOffset); + + uint32_t pos1 = 0, pos2 = 0; + AutoTArray<Accessible*, 30> parents1, parents2; + Accessible* container = + CommonParent(p1, p2, &parents1, &pos1, &parents2, &pos2); + + // Traverse the tree up to the container and collect embedded objects. + for (uint32_t idx = 0; idx < pos1 - 1; idx++) { + Accessible* parent = parents1[idx + 1]; + Accessible* child = parents1[idx]; + uint32_t childCount = parent->ChildCount(); + for (uint32_t childIdx = child->IndexInParent(); childIdx < childCount; + childIdx++) { + Accessible* next = parent->ChildAt(childIdx); + if (!next->IsText()) { + aChildren->AppendElement(next); + } + } + } + + // Traverse through direct children in the container. + int32_t endIdx = parents2[pos2 - 1]->IndexInParent(); + int32_t childIdx = parents1[pos1 - 1]->IndexInParent() + 1; + for (; childIdx < endIdx; childIdx++) { + Accessible* next = container->ChildAt(childIdx); + if (!next->IsText()) { + aChildren->AppendElement(next); + } + } + + // Traverse down from the container to end point. + for (int32_t idx = pos2 - 2; idx > 0; idx--) { + Accessible* parent = parents2[idx]; + Accessible* child = parents2[idx - 1]; + int32_t endIdx = child->IndexInParent(); + for (int32_t childIdx = 0; childIdx < endIdx; childIdx++) { + Accessible* next = parent->ChildAt(childIdx); + if (!next->IsText()) { + aChildren->AppendElement(next); + } + } + } +} + +void TextRange::Text(nsAString& aText) const { + HyperTextAccessibleBase* startHyper = mStartContainer->AsHyperTextBase(); + Accessible* current = startHyper->GetChildAtOffset(mStartOffset); + uint32_t startIntlOffset = mStartOffset - startHyper->GetChildOffset(current); + + while (current && TextInternal(aText, current, startIntlOffset)) { + current = current->Parent(); + if (!current) break; + + current = current->NextSibling(); + } +} + +bool TextRange::Crop(Accessible* aContainer) { + uint32_t boundaryPos = 0, containerPos = 0; + AutoTArray<Accessible*, 30> boundaryParents, containerParents; + + // Crop the start boundary. + Accessible* container = nullptr; + HyperTextAccessibleBase* startHyper = mStartContainer->AsHyperTextBase(); + Accessible* boundary = startHyper->GetChildAtOffset(mStartOffset); + if (boundary != aContainer) { + CommonParent(boundary, aContainer, &boundaryParents, &boundaryPos, + &containerParents, &containerPos); + + if (boundaryPos == 0) { + if (containerPos != 0) { + // The container is contained by the start boundary, reduce the range to + // the point starting at the container. + ToTextPoint(aContainer, &mStartContainer, &mStartOffset); + } else { + // The start boundary and the container are siblings. + container = aContainer; + } + } else { + // The container does not contain the start boundary. + boundary = boundaryParents[boundaryPos]; + container = containerParents[containerPos]; + } + + if (container) { + // If the range start is after the container, then make the range invalid. + if (boundary->IndexInParent() > container->IndexInParent()) { + return !!(mRoot = nullptr); + } + + // If the range starts before the container, then reduce the range to + // the point starting at the container. + if (boundary->IndexInParent() < container->IndexInParent()) { + ToTextPoint(container, &mStartContainer, &mStartOffset); + } + } + + boundaryParents.SetLengthAndRetainStorage(0); + containerParents.SetLengthAndRetainStorage(0); + } + + HyperTextAccessibleBase* endHyper = mEndContainer->AsHyperTextBase(); + boundary = endHyper->GetChildAtOffset(mEndOffset); + if (boundary == aContainer) { + return true; + } + + // Crop the end boundary. + container = nullptr; + CommonParent(boundary, aContainer, &boundaryParents, &boundaryPos, + &containerParents, &containerPos); + + if (boundaryPos == 0) { + if (containerPos != 0) { + ToTextPoint(aContainer, &mEndContainer, &mEndOffset, false); + } else { + container = aContainer; + } + } else { + boundary = boundaryParents[boundaryPos]; + container = containerParents[containerPos]; + } + + if (!container) { + return true; + } + + if (boundary->IndexInParent() < container->IndexInParent()) { + return !!(mRoot = nullptr); + } + + if (boundary->IndexInParent() > container->IndexInParent()) { + ToTextPoint(container, &mEndContainer, &mEndOffset, false); + } + + return true; +} + +/** + * Convert the given DOM point to a DOM point in non-generated contents. + * + * If aDOMPoint is in ::before, the result is immediately after it. + * If aDOMPoint is in ::after, the result is immediately before it. + */ +static DOMPoint ClosestNotGeneratedDOMPoint(const DOMPoint& aDOMPoint, + nsIContent* aElementContent) { + MOZ_ASSERT(aDOMPoint.node, "The node must not be null"); + + // ::before pseudo element + if (aElementContent && + aElementContent->IsGeneratedContentContainerForBefore()) { + MOZ_ASSERT(aElementContent->GetParent(), + "::before must have parent element"); + // The first child of its parent (i.e., immediately after the ::before) is + // good point for a DOM range. + return DOMPoint(aElementContent->GetParent(), 0); + } + + // ::after pseudo element + if (aElementContent && + aElementContent->IsGeneratedContentContainerForAfter()) { + MOZ_ASSERT(aElementContent->GetParent(), + "::after must have parent element"); + // The end of its parent (i.e., immediately before the ::after) is good + // point for a DOM range. + return DOMPoint(aElementContent->GetParent(), + aElementContent->GetParent()->GetChildCount()); + } + + return aDOMPoint; +} + +/** + * GetElementAsContentOf() returns a content representing an element which is + * or includes aNode. + * + * XXX This method is enough to retrieve ::before or ::after pseudo element. + * So, if you want to use this for other purpose, you might need to check + * ancestors too. + */ +static nsIContent* GetElementAsContentOf(nsINode* aNode) { + if (auto* element = dom::Element::FromNode(aNode)) { + return element; + } + return aNode->GetParentElement(); +} + +bool TextRange::AssignDOMRange(nsRange* aRange, bool* aReversed) const { + MOZ_ASSERT(mRoot->IsLocal(), "Not supported for RemoteAccessible"); + bool reversed = EndPoint() < StartPoint(); + if (aReversed) { + *aReversed = reversed; + } + + HyperTextAccessible* startHyper = mStartContainer->AsLocal()->AsHyperText(); + HyperTextAccessible* endHyper = mEndContainer->AsLocal()->AsHyperText(); + DOMPoint startPoint = reversed ? endHyper->OffsetToDOMPoint(mEndOffset) + : startHyper->OffsetToDOMPoint(mStartOffset); + if (!startPoint.node) { + return false; + } + + // HyperTextAccessible manages pseudo elements generated by ::before or + // ::after. However, contents of them are not in the DOM tree normally. + // Therefore, they are not selectable and editable. So, when this creates + // a DOM range, it should not start from nor end in any pseudo contents. + + nsIContent* container = GetElementAsContentOf(startPoint.node); + DOMPoint startPointForDOMRange = + ClosestNotGeneratedDOMPoint(startPoint, container); + aRange->SetStart(startPointForDOMRange.node, startPointForDOMRange.idx); + + // If the caller wants collapsed range, let's collapse the range to its start. + if (mEndContainer == mStartContainer && mEndOffset == mStartOffset) { + aRange->Collapse(true); + return true; + } + + DOMPoint endPoint = reversed ? startHyper->OffsetToDOMPoint(mStartOffset) + : endHyper->OffsetToDOMPoint(mEndOffset); + if (!endPoint.node) { + return false; + } + + if (startPoint.node != endPoint.node) { + container = GetElementAsContentOf(endPoint.node); + } + + DOMPoint endPointForDOMRange = + ClosestNotGeneratedDOMPoint(endPoint, container); + aRange->SetEnd(endPointForDOMRange.node, endPointForDOMRange.idx); + return true; +} + +void TextRange::TextRangesFromSelection(dom::Selection* aSelection, + nsTArray<TextRange>* aRanges) { + MOZ_ASSERT(aRanges->Length() == 0, "TextRange array supposed to be empty"); + + aRanges->SetCapacity(aSelection->RangeCount()); + + const uint32_t rangeCount = aSelection->RangeCount(); + for (const uint32_t idx : IntegerRange(rangeCount)) { + MOZ_ASSERT(aSelection->RangeCount() == rangeCount); + const nsRange* DOMRange = aSelection->GetRangeAt(idx); + MOZ_ASSERT(DOMRange); + HyperTextAccessible* startContainer = + nsAccUtils::GetTextContainer(DOMRange->GetStartContainer()); + HyperTextAccessible* endContainer = + nsAccUtils::GetTextContainer(DOMRange->GetEndContainer()); + HyperTextAccessible* commonAncestor = nsAccUtils::GetTextContainer( + DOMRange->GetClosestCommonInclusiveAncestor()); + if (!startContainer || !endContainer) { + continue; + } + + int32_t startOffset = startContainer->DOMPointToOffset( + DOMRange->GetStartContainer(), DOMRange->StartOffset(), false); + int32_t endOffset = endContainer->DOMPointToOffset( + DOMRange->GetEndContainer(), DOMRange->EndOffset(), true); + + TextRange tr(commonAncestor && commonAncestor->IsTextField() + ? commonAncestor + : startContainer->Document(), + startContainer, startOffset, endContainer, endOffset); + *(aRanges->AppendElement()) = std::move(tr); + } +} + +//////////////////////////////////////////////////////////////////////////////// +// pivate + +void TextRange::Set(Accessible* aRoot, Accessible* aStartContainer, + int32_t aStartOffset, Accessible* aEndContainer, + int32_t aEndOffset) { + mRoot = aRoot; + mStartContainer = aStartContainer; + mEndContainer = aEndContainer; + mStartOffset = aStartOffset; + mEndOffset = aEndOffset; +} + +bool TextRange::TextInternal(nsAString& aText, Accessible* aCurrent, + uint32_t aStartIntlOffset) const { + bool moveNext = true; + int32_t endIntlOffset = -1; + HyperTextAccessibleBase* endHyper = mEndContainer->AsHyperTextBase(); + if (aCurrent->Parent() == mEndContainer && + endHyper->GetChildAtOffset(mEndOffset) == aCurrent) { + uint32_t currentStartOffset = endHyper->GetChildOffset(aCurrent); + endIntlOffset = mEndOffset - currentStartOffset; + if (endIntlOffset == 0) return false; + + moveNext = false; + } + + if (aCurrent->IsTextLeaf()) { + aCurrent->AppendTextTo(aText, aStartIntlOffset, + endIntlOffset - aStartIntlOffset); + if (!moveNext) return false; + } + + Accessible* next = aCurrent->FirstChild(); + if (next) { + if (!TextInternal(aText, next, 0)) return false; + } + + next = aCurrent->NextSibling(); + if (next) { + if (!TextInternal(aText, next, 0)) return false; + } + + return moveNext; +} + +Accessible* TextRange::CommonParent(Accessible* aAcc1, Accessible* aAcc2, + nsTArray<Accessible*>* aParents1, + uint32_t* aPos1, + nsTArray<Accessible*>* aParents2, + uint32_t* aPos2) const { + if (aAcc1 == aAcc2) { + return aAcc1; + } + + MOZ_ASSERT(aParents1->Length() == 0 || aParents2->Length() == 0, + "Wrong arguments"); + + // Build the chain of parents. + Accessible* p1 = aAcc1; + Accessible* p2 = aAcc2; + do { + aParents1->AppendElement(p1); + p1 = p1->Parent(); + } while (p1); + do { + aParents2->AppendElement(p2); + p2 = p2->Parent(); + } while (p2); + + // Find where the parent chain differs + *aPos1 = aParents1->Length(); + *aPos2 = aParents2->Length(); + Accessible* parent = nullptr; + uint32_t len = 0; + for (len = std::min(*aPos1, *aPos2); len > 0; --len) { + Accessible* child1 = aParents1->ElementAt(--(*aPos1)); + Accessible* child2 = aParents2->ElementAt(--(*aPos2)); + if (child1 != child2) break; + + parent = child1; + } + + return parent; +} + +} // namespace a11y +} // namespace mozilla |