accessible/base/TextRange.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=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 "TextRange-inl.h"
   8
   9 #include "LocalAccessible-inl.h"
  10 #include "HyperTextAccessible-inl.h"
  11 #include "mozilla/IntegerRange.h"
  12 #include "mozilla/dom/Selection.h"
  13 #include "nsAccUtils.h"
  14
  15 namespace mozilla {
  16 namespace a11y {
  17
  18 /**
  19  * Returns a text point for aAcc within aContainer.
  20  */
  21 static void ToTextPoint(Accessible* aAcc, Accessible** aContainer,
  22                         int32_t* aOffset, bool aIsBefore = true) {
  23   if (aAcc->IsHyperText()) {
  24     *aContainer = aAcc;
  25     *aOffset =
  26         aIsBefore
  27             ? 0
  28             : static_cast<int32_t>(aAcc->AsHyperTextBase()->CharacterCount());
  29     return;
  30   }
  31
  32   Accessible* child = nullptr;
  33   Accessible* parent = aAcc;
  34   do {
  35     child = parent;
  36     parent = parent->Parent();
  37   } while (parent && !parent->IsHyperText());
  38
  39   if (parent) {
  40     *aContainer = parent;
  41     *aOffset = parent->AsHyperTextBase()->GetChildOffset(
  42         child->IndexInParent() + static_cast<int32_t>(!aIsBefore));
  43   }
  44 }
  45
  46 ////////////////////////////////////////////////////////////////////////////////
  47 // TextPoint
  48
  49 bool TextPoint::operator<(const TextPoint& aPoint) const {
  50   if (mContainer == aPoint.mContainer) return mOffset < aPoint.mOffset;
  51
  52   // Build the chain of parents
  53   Accessible* p1 = mContainer;
  54   Accessible* p2 = aPoint.mContainer;
  55   AutoTArray<Accessible*, 30> parents1, parents2;
  56   do {
  57     parents1.AppendElement(p1);
  58     p1 = p1->Parent();
  59   } while (p1);
  60   do {
  61     parents2.AppendElement(p2);
  62     p2 = p2->Parent();
  63   } while (p2);
  64
  65   // Find where the parent chain differs
  66   uint32_t pos1 = parents1.Length(), pos2 = parents2.Length();
  67   for (uint32_t len = std::min(pos1, pos2); len > 0; --len) {
  68     Accessible* child1 = parents1.ElementAt(--pos1);
  69     Accessible* child2 = parents2.ElementAt(--pos2);
  70     if (child1 != child2) {
  71       return child1->IndexInParent() < child2->IndexInParent();
  72     }
  73   }
  74
  75   if (pos1 != 0) {
  76     // If parents1 is a superset of parents2 then mContainer is a
  77     // descendant of aPoint.mContainer. The next element down in parents1
  78     // is mContainer's ancestor that is the child of aPoint.mContainer.
  79     // We compare its end offset in aPoint.mContainer with aPoint.mOffset.
  80     Accessible* child = parents1.ElementAt(pos1 - 1);
  81     MOZ_ASSERT(child->Parent() == aPoint.mContainer);
  82     return child->EndOffset() < static_cast<uint32_t>(aPoint.mOffset);
  83   }
  84
  85   if (pos2 != 0) {
  86     // If parents2 is a superset of parents1 then aPoint.mContainer is a
  87     // descendant of mContainer. The next element down in parents2
  88     // is aPoint.mContainer's ancestor that is the child of mContainer.
  89     // We compare its start offset in mContainer with mOffset.
  90     Accessible* child = parents2.ElementAt(pos2 - 1);
  91     MOZ_ASSERT(child->Parent() == mContainer);
  92     return static_cast<uint32_t>(mOffset) < child->StartOffset();
  93   }
  94
  95   NS_ERROR("Broken tree?!");
  96   return false;
  97 }
  98
  99 ////////////////////////////////////////////////////////////////////////////////
 100 // TextRange
 101
 102 TextRange::TextRange(Accessible* aRoot, Accessible* aStartContainer,
 103                      int32_t aStartOffset, Accessible* aEndContainer,
 104                      int32_t aEndOffset)
 105     : mRoot(aRoot),
 106       mStartContainer(aStartContainer),
 107       mEndContainer(aEndContainer),
 108       mStartOffset(aStartOffset),
 109       mEndOffset(aEndOffset) {}
 110
 111 bool TextRange::Crop(Accessible* aContainer) {
 112   uint32_t boundaryPos = 0, containerPos = 0;
 113   AutoTArray<Accessible*, 30> boundaryParents, containerParents;
 114
 115   // Crop the start boundary.
 116   Accessible* container = nullptr;
 117   HyperTextAccessibleBase* startHyper = mStartContainer->AsHyperTextBase();
 118   Accessible* boundary = startHyper->GetChildAtOffset(mStartOffset);
 119   if (boundary != aContainer) {
 120     CommonParent(boundary, aContainer, &boundaryParents, &boundaryPos,
 121                  &containerParents, &containerPos);
 122
 123     if (boundaryPos == 0) {
 124       if (containerPos != 0) {
 125         // The container is contained by the start boundary, reduce the range to
 126         // the point starting at the container.
 127         ToTextPoint(aContainer, &mStartContainer, &mStartOffset);
 128       } else {
 129         // The start boundary and the container are siblings.
 130         container = aContainer;
 131       }
 132     } else {
 133       // The container does not contain the start boundary.
 134       boundary = boundaryParents[boundaryPos];
 135       container = containerParents[containerPos];
 136     }
 137
 138     if (container) {
 139       // If the range start is after the container, then make the range invalid.
 140       if (boundary->IndexInParent() > container->IndexInParent()) {
 141         return !!(mRoot = nullptr);
 142       }
 143
 144       // If the range starts before the container, then reduce the range to
 145       // the point starting at the container.
 146       if (boundary->IndexInParent() < container->IndexInParent()) {
 147         ToTextPoint(container, &mStartContainer, &mStartOffset);
 148       }
 149     }
 150
 151     boundaryParents.SetLengthAndRetainStorage(0);
 152     containerParents.SetLengthAndRetainStorage(0);
 153   }
 154
 155   HyperTextAccessibleBase* endHyper = mEndContainer->AsHyperTextBase();
 156   boundary = endHyper->GetChildAtOffset(mEndOffset);
 157   if (boundary == aContainer) {
 158     return true;
 159   }
 160
 161   // Crop the end boundary.
 162   container = nullptr;
 163   CommonParent(boundary, aContainer, &boundaryParents, &boundaryPos,
 164                &containerParents, &containerPos);
 165
 166   if (boundaryPos == 0) {
 167     if (containerPos != 0) {
 168       ToTextPoint(aContainer, &mEndContainer, &mEndOffset, false);
 169     } else {
 170       container = aContainer;
 171     }
 172   } else {
 173     boundary = boundaryParents[boundaryPos];
 174     container = containerParents[containerPos];
 175   }
 176
 177   if (!container) {
 178     return true;
 179   }
 180
 181   if (boundary->IndexInParent() < container->IndexInParent()) {
 182     return !!(mRoot = nullptr);
 183   }
 184
 185   if (boundary->IndexInParent() > container->IndexInParent()) {
 186     ToTextPoint(container, &mEndContainer, &mEndOffset, false);
 187   }
 188
 189   return true;
 190 }
 191
 192 /**
 193  * Convert the given DOM point to a DOM point in non-generated contents.
 194  *
 195  * If aDOMPoint is in ::before, the result is immediately after it.
 196  * If aDOMPoint is in ::after, the result is immediately before it.
 197  */
 198 static DOMPoint ClosestNotGeneratedDOMPoint(const DOMPoint& aDOMPoint,
 199                                             nsIContent* aElementContent) {
 200   MOZ_ASSERT(aDOMPoint.node, "The node must not be null");
 201
 202   // ::before pseudo element
 203   if (aElementContent &&
 204       aElementContent->IsGeneratedContentContainerForBefore()) {
 205     MOZ_ASSERT(aElementContent->GetParent(),
 206                "::before must have parent element");
 207     // The first child of its parent (i.e., immediately after the ::before) is
 208     // good point for a DOM range.
 209     return DOMPoint(aElementContent->GetParent(), 0);
 210   }
 211
 212   // ::after pseudo element
 213   if (aElementContent &&
 214       aElementContent->IsGeneratedContentContainerForAfter()) {
 215     MOZ_ASSERT(aElementContent->GetParent(),
 216                "::after must have parent element");
 217     // The end of its parent (i.e., immediately before the ::after) is good
 218     // point for a DOM range.
 219     return DOMPoint(aElementContent->GetParent(),
 220                     aElementContent->GetParent()->GetChildCount());
 221   }
 222
 223   return aDOMPoint;
 224 }
 225
 226 /**
 227  * GetElementAsContentOf() returns a content representing an element which is
 228  * or includes aNode.
 229  *
 230  * XXX This method is enough to retrieve ::before or ::after pseudo element.
 231  *     So, if you want to use this for other purpose, you might need to check
 232  *     ancestors too.
 233  */
 234 static nsIContent* GetElementAsContentOf(nsINode* aNode) {
 235   if (auto* element = dom::Element::FromNode(aNode)) {
 236     return element;
 237   }
 238   return aNode->GetParentElement();
 239 }
 240
 241 bool TextRange::AssignDOMRange(nsRange* aRange, bool* aReversed) const {
 242   MOZ_ASSERT(mRoot->IsLocal(), "Not supported for RemoteAccessible");
 243   bool reversed = EndPoint() < StartPoint();
 244   if (aReversed) {
 245     *aReversed = reversed;
 246   }
 247
 248   HyperTextAccessible* startHyper = mStartContainer->AsLocal()->AsHyperText();
 249   HyperTextAccessible* endHyper = mEndContainer->AsLocal()->AsHyperText();
 250   DOMPoint startPoint = reversed ? endHyper->OffsetToDOMPoint(mEndOffset)
 251                                  : startHyper->OffsetToDOMPoint(mStartOffset);
 252   if (!startPoint.node) {
 253     return false;
 254   }
 255
 256   // HyperTextAccessible manages pseudo elements generated by ::before or
 257   // ::after.  However, contents of them are not in the DOM tree normally.
 258   // Therefore, they are not selectable and editable.  So, when this creates
 259   // a DOM range, it should not start from nor end in any pseudo contents.
 260
 261   nsIContent* container = GetElementAsContentOf(startPoint.node);
 262   DOMPoint startPointForDOMRange =
 263       ClosestNotGeneratedDOMPoint(startPoint, container);
 264   aRange->SetStart(startPointForDOMRange.node, startPointForDOMRange.idx);
 265
 266   // If the caller wants collapsed range, let's collapse the range to its start.
 267   if (mEndContainer == mStartContainer && mEndOffset == mStartOffset) {
 268     aRange->Collapse(true);
 269     return true;
 270   }
 271
 272   DOMPoint endPoint = reversed ? startHyper->OffsetToDOMPoint(mStartOffset)
 273                                : endHyper->OffsetToDOMPoint(mEndOffset);
 274   if (!endPoint.node) {
 275     return false;
 276   }
 277
 278   if (startPoint.node != endPoint.node) {
 279     container = GetElementAsContentOf(endPoint.node);
 280   }
 281
 282   DOMPoint endPointForDOMRange =
 283       ClosestNotGeneratedDOMPoint(endPoint, container);
 284   aRange->SetEnd(endPointForDOMRange.node, endPointForDOMRange.idx);
 285   return true;
 286 }
 287
 288 void TextRange::TextRangesFromSelection(dom::Selection* aSelection,
 289                                         nsTArray<TextRange>* aRanges) {
 290   MOZ_ASSERT(aRanges->Length() == 0, "TextRange array supposed to be empty");
 291
 292   aRanges->SetCapacity(aSelection->RangeCount());
 293
 294   const uint32_t rangeCount = aSelection->RangeCount();
 295   for (const uint32_t idx : IntegerRange(rangeCount)) {
 296     MOZ_ASSERT(aSelection->RangeCount() == rangeCount);
 297     const nsRange* DOMRange = aSelection->GetRangeAt(idx);
 298     MOZ_ASSERT(DOMRange);
 299     HyperTextAccessible* startContainer =
 300         nsAccUtils::GetTextContainer(DOMRange->GetStartContainer());
 301     HyperTextAccessible* endContainer =
 302         nsAccUtils::GetTextContainer(DOMRange->GetEndContainer());
 303     HyperTextAccessible* commonAncestor = nsAccUtils::GetTextContainer(
 304         DOMRange->GetClosestCommonInclusiveAncestor());
 305     if (!startContainer || !endContainer) {
 306       continue;
 307     }
 308
 309     int32_t startOffset = startContainer->DOMPointToOffset(
 310         DOMRange->GetStartContainer(), DOMRange->StartOffset(), false);
 311     int32_t endOffset = endContainer->DOMPointToOffset(
 312         DOMRange->GetEndContainer(), DOMRange->EndOffset(), true);
 313
 314     TextRange tr(commonAncestor && commonAncestor->IsTextField()
 315                      ? commonAncestor
 316                      : startContainer->Document(),
 317                  startContainer, startOffset, endContainer, endOffset);
 318     *(aRanges->AppendElement()) = std::move(tr);
 319   }
 320 }
 321
 322 ////////////////////////////////////////////////////////////////////////////////
 323 // pivate
 324
 325 void TextRange::Set(Accessible* aRoot, Accessible* aStartContainer,
 326                     int32_t aStartOffset, Accessible* aEndContainer,
 327                     int32_t aEndOffset) {
 328   mRoot = aRoot;
 329   mStartContainer = aStartContainer;
 330   mEndContainer = aEndContainer;
 331   mStartOffset = aStartOffset;
 332   mEndOffset = aEndOffset;
 333 }
 334
 335 Accessible* TextRange::CommonParent(Accessible* aAcc1, Accessible* aAcc2,
 336                                     nsTArray<Accessible*>* aParents1,
 337                                     uint32_t* aPos1,
 338                                     nsTArray<Accessible*>* aParents2,
 339                                     uint32_t* aPos2) const {
 340   if (aAcc1 == aAcc2) {
 341     return aAcc1;
 342   }
 343
 344   MOZ_ASSERT(aParents1->Length() == 0 || aParents2->Length() == 0,
 345              "Wrong arguments");
 346
 347   // Build the chain of parents.
 348   Accessible* p1 = aAcc1;
 349   Accessible* p2 = aAcc2;
 350   do {
 351     aParents1->AppendElement(p1);
 352     p1 = p1->Parent();
 353   } while (p1);
 354   do {
 355     aParents2->AppendElement(p2);
 356     p2 = p2->Parent();
 357   } while (p2);
 358
 359   // Find where the parent chain differs
 360   *aPos1 = aParents1->Length();
 361   *aPos2 = aParents2->Length();
 362   Accessible* parent = nullptr;
 363   uint32_t len = 0;
 364   for (len = std::min(*aPos1, *aPos2); len > 0; --len) {
 365     Accessible* child1 = aParents1->ElementAt(--(*aPos1));
 366     Accessible* child2 = aParents2->ElementAt(--(*aPos2));
 367     if (child1 != child2) break;
 368
 369     parent = child1;
 370   }
 371
 372   return parent;
 373 }
 374
 375 }  // namespace a11y
 376 }  // namespace mozilla