1/* clang-format off */
2/* -*- Mode: Objective-C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
3/* clang-format on */
4/* This Source Code Form is subject to the terms of the Mozilla Public
5 * License, v. 2.0. If a copy of the MPL was not distributed with this
6 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7
8#include "HyperTextAccessibleWrap.h"
9
10#include "LocalAccessible-inl.h"
11#include "HTMLListAccessible.h"
12#include "nsAccUtils.h"
13#include "nsFrameSelection.h"
14#include "TextRange.h"
15#include "TreeWalker.h"
16
17using namespace mozilla;
18using namespace mozilla::a11y;
19
20// HyperTextIterator
21
22class HyperTextIterator {
23 public:
24  HyperTextIterator(HyperTextAccessible* aStartContainer, int32_t aStartOffset,
25                    HyperTextAccessible* aEndContainer, int32_t aEndOffset)
26      : mCurrentContainer(aStartContainer),
27        mCurrentStartOffset(0),
28        mCurrentEndOffset(0),
29        mEndContainer(aEndContainer),
30        mEndOffset(0) {
31    mCurrentStartOffset =
32        std::min(aStartOffset,
33                 static_cast<int32_t>(mCurrentContainer->CharacterCount()));
34    mCurrentEndOffset = mCurrentStartOffset;
35    mEndOffset = std::min(
36        aEndOffset, static_cast<int32_t>(mEndContainer->CharacterCount()));
37  }
38
39  bool Next();
40
41  int32_t SegmentLength();
42
43  // If offset is set to a child hyperlink, adjust it so it set on the first
44  // offset in the deepest link. Or, if the offset to the last character, set it
45  // to the outermost end offset in an ancestor. Returns true if iterator was
46  // mutated.
47  bool NormalizeForward();
48
49  // If offset is set right after child hyperlink, adjust it so it set on the
50  // last offset in the deepest link. Or, if the offset is on the first
51  // character of a link, set it to the outermost start offset in an ancestor.
52  // Returns true if iterator was mutated.
53  bool NormalizeBackward();
54
55  HyperTextAccessible* mCurrentContainer;
56  int32_t mCurrentStartOffset;
57  int32_t mCurrentEndOffset;
58
59 private:
60  int32_t NextLinkOffset();
61
62  HyperTextAccessible* mEndContainer;
63  int32_t mEndOffset;
64};
65
66bool HyperTextIterator::NormalizeForward() {
67  if (mCurrentStartOffset == nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT ||
68      mCurrentStartOffset >=
69          static_cast<int32_t>(mCurrentContainer->CharacterCount())) {
70    // If this is the end of the current container, mutate to its parent's
71    // end offset.
72    if (!mCurrentContainer->IsLink()) {
73      // If we are not a link, it is a root hypertext accessible.
74      return false;
75    }
76    if (!mCurrentContainer->LocalParent() ||
77        !mCurrentContainer->LocalParent()->IsHyperText()) {
78      // If we are a link, but our parent is not a hypertext accessible
79      // treat the current container as the root hypertext accessible.
80      // This can be the case with some XUL containers that are not
81      // hypertext accessibles.
82      return false;
83    }
84    uint32_t endOffset = mCurrentContainer->EndOffset();
85    if (endOffset != 0) {
86      mCurrentContainer = mCurrentContainer->LocalParent()->AsHyperText();
87      mCurrentStartOffset = endOffset;
88
89      if (mCurrentContainer == mEndContainer &&
90          mCurrentStartOffset >= mEndOffset) {
91        // Reached end boundary.
92        return false;
93      }
94
95      // Call NormalizeForward recursively to get top-most link if at the end of
96      // one, or innermost link if at the beginning.
97      NormalizeForward();
98      return true;
99    }
100  } else {
101    LocalAccessible* link = mCurrentContainer->LinkAt(
102        mCurrentContainer->LinkIndexAtOffset(mCurrentStartOffset));
103
104    // If there is a link at this offset, mutate into it.
105    if (link && link->IsHyperText()) {
106      if (mCurrentStartOffset > 0 &&
107          mCurrentContainer->LinkIndexAtOffset(mCurrentStartOffset) ==
108              mCurrentContainer->LinkIndexAtOffset(mCurrentStartOffset - 1)) {
109        MOZ_ASSERT_UNREACHABLE("Same link for previous offset");
110        return false;
111      }
112
113      mCurrentContainer = link->AsHyperText();
114      if (link->IsHTMLListItem()) {
115        LocalAccessible* bullet = link->AsHTMLListItem()->Bullet();
116        mCurrentStartOffset = bullet ? nsAccUtils::TextLength(bullet) : 0;
117      } else {
118        mCurrentStartOffset = 0;
119      }
120
121      if (mCurrentContainer == mEndContainer &&
122          mCurrentStartOffset >= mEndOffset) {
123        // Reached end boundary.
124        return false;
125      }
126
127      // Call NormalizeForward recursively to get top-most embedding ancestor
128      // if at the end of one, or innermost link if at the beginning.
129      NormalizeForward();
130      return true;
131    }
132  }
133
134  return false;
135}
136
137bool HyperTextIterator::NormalizeBackward() {
138  if (mCurrentStartOffset == 0) {
139    // If this is the start of the current container, mutate to its parent's
140    // start offset.
141    if (!mCurrentContainer->IsLink()) {
142      // If we are not a link, it is a root hypertext accessible.
143      return false;
144    }
145    if (!mCurrentContainer->LocalParent() ||
146        !mCurrentContainer->LocalParent()->IsHyperText()) {
147      // If we are a link, but our parent is not a hypertext accessible
148      // treat the current container as the root hypertext accessible.
149      // This can be the case with some XUL containers that are not
150      // hypertext accessibles.
151      return false;
152    }
153
154    uint32_t startOffset = mCurrentContainer->StartOffset();
155    mCurrentContainer = mCurrentContainer->LocalParent()->AsHyperText();
156    mCurrentStartOffset = startOffset;
157
158    // Call NormalizeBackward recursively to get top-most link if at the
159    // beginning of one, or innermost link if at the end.
160    NormalizeBackward();
161    return true;
162  } else {
163    LocalAccessible* link =
164        mCurrentContainer->GetChildAtOffset(mCurrentStartOffset - 1);
165
166    // If there is a link before this offset, mutate into it,
167    // and set the offset to its last character.
168    if (link && link->IsHyperText()) {
169      mCurrentContainer = link->AsHyperText();
170      mCurrentStartOffset = mCurrentContainer->CharacterCount();
171
172      // Call NormalizeBackward recursively to get top-most top-most embedding
173      // ancestor if at the beginning of one, or innermost link if at the end.
174      NormalizeBackward();
175      return true;
176    }
177
178    if (mCurrentContainer->IsHTMLListItem() &&
179        mCurrentContainer->AsHTMLListItem()->Bullet() == link) {
180      mCurrentStartOffset = 0;
181      NormalizeBackward();
182      return true;
183    }
184  }
185
186  return false;
187}
188
189int32_t HyperTextIterator::SegmentLength() {
190  int32_t endOffset = mCurrentEndOffset < 0
191                          ? mCurrentContainer->CharacterCount()
192                          : mCurrentEndOffset;
193
194  return endOffset - mCurrentStartOffset;
195}
196
197int32_t HyperTextIterator::NextLinkOffset() {
198  int32_t linkCount = mCurrentContainer->LinkCount();
199  for (int32_t i = 0; i < linkCount; i++) {
200    LocalAccessible* link = mCurrentContainer->LinkAt(i);
201    MOZ_ASSERT(link);
202    int32_t linkStartOffset = link->StartOffset();
203    if (mCurrentStartOffset < linkStartOffset) {
204      return linkStartOffset;
205    }
206  }
207
208  return -1;
209}
210
211bool HyperTextIterator::Next() {
212  if (!mCurrentContainer->Document()->HasLoadState(
213          DocAccessible::eTreeConstructed)) {
214    // If the accessible tree is still being constructed the text tree
215    // is not in a traversable state yet.
216    return false;
217  }
218
219  if (mCurrentContainer == mEndContainer &&
220      (mCurrentEndOffset == -1 || mEndOffset <= mCurrentEndOffset)) {
221    return false;
222  } else {
223    mCurrentStartOffset = mCurrentEndOffset;
224    NormalizeForward();
225  }
226
227  int32_t nextLinkOffset = NextLinkOffset();
228  if (mCurrentContainer == mEndContainer &&
229      (nextLinkOffset == -1 || nextLinkOffset > mEndOffset)) {
230    mCurrentEndOffset =
231        mEndOffset < 0 ? mEndContainer->CharacterCount() : mEndOffset;
232  } else {
233    mCurrentEndOffset = nextLinkOffset < 0 ? mCurrentContainer->CharacterCount()
234                                           : nextLinkOffset;
235  }
236
237  return mCurrentStartOffset != mCurrentEndOffset;
238}
239
240void HyperTextAccessibleWrap::TextForRange(nsAString& aText,
241                                           int32_t aStartOffset,
242                                           HyperTextAccessible* aEndContainer,
243                                           int32_t aEndOffset) {
244  if (IsHTMLListItem()) {
245    LocalAccessible* maybeBullet = GetChildAtOffset(aStartOffset - 1);
246    if (maybeBullet) {
247      LocalAccessible* bullet = AsHTMLListItem()->Bullet();
248      if (maybeBullet == bullet) {
249        TextSubstring(0, nsAccUtils::TextLength(bullet), aText);
250      }
251    }
252  }
253
254  HyperTextIterator iter(this, aStartOffset, aEndContainer, aEndOffset);
255  while (iter.Next()) {
256    nsAutoString text;
257    iter.mCurrentContainer->TextSubstring(iter.mCurrentStartOffset,
258                                          iter.mCurrentEndOffset, text);
259    aText.Append(text);
260  }
261}
262
263void HyperTextAccessibleWrap::AttributedTextForRange(
264    nsTArray<nsString>& aStrings, nsTArray<RefPtr<AccAttributes>>& aProperties,
265    nsTArray<LocalAccessible*>& aContainers, int32_t aStartOffset,
266    HyperTextAccessible* aEndContainer, int32_t aEndOffset) {
267  if (IsHTMLListItem()) {
268    LocalAccessible* maybeBullet = GetChildAtOffset(aStartOffset - 1);
269    if (maybeBullet) {
270      LocalAccessible* bullet = AsHTMLListItem()->Bullet();
271      if (maybeBullet == bullet) {
272        nsAutoString text;
273        TextSubstring(0, nsAccUtils::TextLength(bullet), text);
274
275        int32_t unusedAttrStartOffset, unusedAttrEndOffset;
276        RefPtr<AccAttributes> props =
277            TextAttributes(true, aStartOffset - 1, &unusedAttrStartOffset,
278                           &unusedAttrEndOffset);
279
280        aStrings.AppendElement(text);
281        aProperties.AppendElement(props);
282        aContainers.AppendElement(this);
283      }
284    }
285  }
286
287  HyperTextIterator iter(this, aStartOffset, aEndContainer, aEndOffset);
288  while (iter.Next()) {
289    int32_t attrStartOffset = 0;
290    int32_t attrEndOffset = iter.mCurrentStartOffset;
291    do {
292      int32_t oldEndOffset = attrEndOffset;
293      RefPtr<AccAttributes> props = iter.mCurrentContainer->TextAttributes(
294          true, attrEndOffset, &attrStartOffset, &attrEndOffset);
295
296      if (oldEndOffset == attrEndOffset) {
297        MOZ_ASSERT_UNREACHABLE("new attribute end offset should be different");
298        break;
299      }
300
301      nsAutoString text;
302      iter.mCurrentContainer->TextSubstring(
303          attrStartOffset < iter.mCurrentStartOffset ? iter.mCurrentStartOffset
304                                                     : attrStartOffset,
305          attrEndOffset < iter.mCurrentEndOffset ? attrEndOffset
306                                                 : iter.mCurrentEndOffset,
307          text);
308
309      aStrings.AppendElement(text);
310      aProperties.AppendElement(props);
311      aContainers.AppendElement(iter.mCurrentContainer);
312    } while (attrEndOffset < iter.mCurrentEndOffset);
313  }
314}
315
316nsIntRect HyperTextAccessibleWrap::BoundsForRange(
317    int32_t aStartOffset, HyperTextAccessible* aEndContainer,
318    int32_t aEndOffset) {
319  nsIntRect rect;
320  HyperTextIterator iter(this, aStartOffset, aEndContainer, aEndOffset);
321  while (iter.Next()) {
322    nsIntRect stringRect = iter.mCurrentContainer->TextBounds(
323        iter.mCurrentStartOffset, iter.mCurrentEndOffset);
324    rect.UnionRect(rect, stringRect);
325  }
326
327  return rect;
328}
329
330int32_t HyperTextAccessibleWrap::LengthForRange(
331    int32_t aStartOffset, HyperTextAccessible* aEndContainer,
332    int32_t aEndOffset) {
333  int32_t length = 0;
334  HyperTextIterator iter(this, aStartOffset, aEndContainer, aEndOffset);
335  while (iter.Next()) {
336    length += iter.SegmentLength();
337  }
338
339  return length;
340}
341
342void HyperTextAccessibleWrap::OffsetAtIndex(int32_t aIndex,
343                                            HyperTextAccessible** aContainer,
344                                            int32_t* aOffset) {
345  int32_t index = aIndex;
346  HyperTextIterator iter(this, 0, this, CharacterCount());
347  while (iter.Next()) {
348    int32_t segmentLength = iter.SegmentLength();
349    if (index <= segmentLength) {
350      *aContainer = iter.mCurrentContainer;
351      *aOffset = iter.mCurrentStartOffset + index;
352      break;
353    }
354    index -= segmentLength;
355  }
356}
357
358void HyperTextAccessibleWrap::RangeAt(int32_t aOffset, EWhichRange aRangeType,
359                                      HyperTextAccessible** aStartContainer,
360                                      int32_t* aStartOffset,
361                                      HyperTextAccessible** aEndContainer,
362                                      int32_t* aEndOffset) {
363  switch (aRangeType) {
364    case EWhichRange::eLeftWord:
365      LeftWordAt(aOffset, aStartContainer, aStartOffset, aEndContainer,
366                 aEndOffset);
367      break;
368    case EWhichRange::eRightWord:
369      RightWordAt(aOffset, aStartContainer, aStartOffset, aEndContainer,
370                  aEndOffset);
371      break;
372    case EWhichRange::eLine:
373    case EWhichRange::eLeftLine:
374      LineAt(aOffset, false, aStartContainer, aStartOffset, aEndContainer,
375             aEndOffset);
376      break;
377    case EWhichRange::eRightLine:
378      LineAt(aOffset, true, aStartContainer, aStartOffset, aEndContainer,
379             aEndOffset);
380      break;
381    case EWhichRange::eParagraph:
382      ParagraphAt(aOffset, aStartContainer, aStartOffset, aEndContainer,
383                  aEndOffset);
384      break;
385    case EWhichRange::eStyle:
386      StyleAt(aOffset, aStartContainer, aStartOffset, aEndContainer,
387              aEndOffset);
388      break;
389    default:
390      break;
391  }
392}
393
394void HyperTextAccessibleWrap::LeftWordAt(int32_t aOffset,
395                                         HyperTextAccessible** aStartContainer,
396                                         int32_t* aStartOffset,
397                                         HyperTextAccessible** aEndContainer,
398                                         int32_t* aEndOffset) {
399  TextPoint here(this, aOffset);
400  TextPoint start =
401      FindTextPoint(aOffset, eDirPrevious, eSelectWord, eStartWord);
402  if (!start.mContainer) {
403    return;
404  }
405
406  if ((NativeState() & states::EDITABLE) &&
407      !(start.mContainer->NativeState() & states::EDITABLE)) {
408    // The word search crossed an editable boundary. Return the first word of
409    // the editable root.
410    return EditableRoot()->RightWordAt(0, aStartContainer, aStartOffset,
411                                       aEndContainer, aEndOffset);
412  }
413
414  TextPoint end =
415      static_cast<HyperTextAccessibleWrap*>(start.mContainer)
416          ->FindTextPoint(start.mOffset, eDirNext, eSelectWord, eEndWord);
417  if (end < here) {
418    *aStartContainer = end.mContainer;
419    *aEndContainer = here.mContainer;
420    *aStartOffset = end.mOffset;
421    *aEndOffset = here.mOffset;
422  } else {
423    *aStartContainer = start.mContainer;
424    *aEndContainer = end.mContainer;
425    *aStartOffset = start.mOffset;
426    *aEndOffset = end.mOffset;
427  }
428}
429
430void HyperTextAccessibleWrap::RightWordAt(int32_t aOffset,
431                                          HyperTextAccessible** aStartContainer,
432                                          int32_t* aStartOffset,
433                                          HyperTextAccessible** aEndContainer,
434                                          int32_t* aEndOffset) {
435  TextPoint here(this, aOffset);
436  TextPoint end = FindTextPoint(aOffset, eDirNext, eSelectWord, eEndWord);
437  if (!end.mContainer || end < here || here == end) {
438    // If we didn't find a word end, or if we wrapped around (bug 1652833),
439    // return with no result.
440    return;
441  }
442
443  if ((NativeState() & states::EDITABLE) &&
444      !(end.mContainer->NativeState() & states::EDITABLE)) {
445    // The word search crossed an editable boundary. Return with no result.
446    return;
447  }
448
449  TextPoint start =
450      static_cast<HyperTextAccessibleWrap*>(end.mContainer)
451          ->FindTextPoint(end.mOffset, eDirPrevious, eSelectWord, eStartWord);
452
453  if (here < start) {
454    *aStartContainer = here.mContainer;
455    *aEndContainer = start.mContainer;
456    *aStartOffset = here.mOffset;
457    *aEndOffset = start.mOffset;
458  } else {
459    *aStartContainer = start.mContainer;
460    *aEndContainer = end.mContainer;
461    *aStartOffset = start.mOffset;
462    *aEndOffset = end.mOffset;
463  }
464}
465
466void HyperTextAccessibleWrap::LineAt(int32_t aOffset, bool aNextLine,
467                                     HyperTextAccessible** aStartContainer,
468                                     int32_t* aStartOffset,
469                                     HyperTextAccessible** aEndContainer,
470                                     int32_t* aEndOffset) {
471  TextPoint here(this, aOffset);
472  TextPoint end =
473      FindTextPoint(aOffset, eDirNext, eSelectEndLine, eDefaultBehavior);
474  if (!end.mContainer || end < here) {
475    // If we didn't find a word end, or if we wrapped around (bug 1652833),
476    // return with no result.
477    return;
478  }
479
480  TextPoint start = static_cast<HyperTextAccessibleWrap*>(end.mContainer)
481                        ->FindTextPoint(end.mOffset, eDirPrevious,
482                                        eSelectBeginLine, eDefaultBehavior);
483
484  if (!aNextLine && here < start) {
485    start = FindTextPoint(aOffset, eDirPrevious, eSelectBeginLine,
486                          eDefaultBehavior);
487    if (!start.mContainer) {
488      return;
489    }
490
491    end = static_cast<HyperTextAccessibleWrap*>(start.mContainer)
492              ->FindTextPoint(start.mOffset, eDirNext, eSelectEndLine,
493                              eDefaultBehavior);
494  }
495
496  *aStartContainer = start.mContainer;
497  *aEndContainer = end.mContainer;
498  *aStartOffset = start.mOffset;
499  *aEndOffset = end.mOffset;
500}
501
502void HyperTextAccessibleWrap::ParagraphAt(int32_t aOffset,
503                                          HyperTextAccessible** aStartContainer,
504                                          int32_t* aStartOffset,
505                                          HyperTextAccessible** aEndContainer,
506                                          int32_t* aEndOffset) {
507  TextPoint here(this, aOffset);
508  TextPoint end =
509      FindTextPoint(aOffset, eDirNext, eSelectParagraph, eDefaultBehavior);
510
511  if (!end.mContainer || end < here) {
512    // If we didn't find a word end, or if we wrapped around (bug 1652833),
513    // return with no result.
514    return;
515  }
516
517  if (end.mOffset == -1 && LocalParent() && LocalParent()->IsHyperText()) {
518    // If end offset is -1 we didn't find a paragraph boundary.
519    // This must be an inline container, go to its parent to
520    // retrieve paragraph boundaries.
521    static_cast<HyperTextAccessibleWrap*>(LocalParent()->AsHyperText())
522        ->ParagraphAt(StartOffset(), aStartContainer, aStartOffset,
523                      aEndContainer, aEndOffset);
524    return;
525  }
526
527  TextPoint start = static_cast<HyperTextAccessibleWrap*>(end.mContainer)
528                        ->FindTextPoint(end.mOffset, eDirPrevious,
529                                        eSelectParagraph, eDefaultBehavior);
530
531  *aStartContainer = start.mContainer;
532  *aEndContainer = end.mContainer;
533  *aStartOffset = start.mOffset;
534  *aEndOffset = end.mOffset;
535}
536
537void HyperTextAccessibleWrap::StyleAt(int32_t aOffset,
538                                      HyperTextAccessible** aStartContainer,
539                                      int32_t* aStartOffset,
540                                      HyperTextAccessible** aEndContainer,
541                                      int32_t* aEndOffset) {
542  // Get the range of the text leaf at this offset.
543  // A text leaf represents a stretch of like-styled text.
544  auto leaf = LeafAtOffset(aOffset);
545  if (!leaf) {
546    return;
547  }
548
549  MOZ_ASSERT(leaf->LocalParent()->IsHyperText());
550  HyperTextAccessibleWrap* container =
551      static_cast<HyperTextAccessibleWrap*>(leaf->LocalParent()->AsHyperText());
552  if (!container) {
553    return;
554  }
555
556  *aStartContainer = *aEndContainer = container;
557  container->RangeOfChild(leaf, aStartOffset, aEndOffset);
558}
559
560void HyperTextAccessibleWrap::NextClusterAt(
561    int32_t aOffset, HyperTextAccessible** aNextContainer,
562    int32_t* aNextOffset) {
563  TextPoint here(this, aOffset);
564  TextPoint next =
565      FindTextPoint(aOffset, eDirNext, eSelectCluster, eDefaultBehavior);
566
567  if ((next.mOffset == nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT &&
568       next.mContainer == Document()) ||
569      (next < here)) {
570    // If we reached the end of the doc, or if we wrapped to the start of the
571    // doc return given offset as-is.
572    *aNextContainer = this;
573    *aNextOffset = aOffset;
574  } else {
575    *aNextContainer = next.mContainer;
576    *aNextOffset = next.mOffset;
577  }
578}
579
580void HyperTextAccessibleWrap::PreviousClusterAt(
581    int32_t aOffset, HyperTextAccessible** aPrevContainer,
582    int32_t* aPrevOffset) {
583  TextPoint prev =
584      FindTextPoint(aOffset, eDirPrevious, eSelectCluster, eDefaultBehavior);
585  *aPrevContainer = prev.mContainer;
586  *aPrevOffset = prev.mOffset;
587}
588
589void HyperTextAccessibleWrap::RangeOfChild(LocalAccessible* aChild,
590                                           int32_t* aStartOffset,
591                                           int32_t* aEndOffset) {
592  MOZ_ASSERT(aChild->LocalParent() == this);
593  *aStartOffset = *aEndOffset = -1;
594  int32_t index = GetIndexOf(aChild);
595  if (index != -1) {
596    *aStartOffset = GetChildOffset(index);
597    // If this is the last child index + 1 will return the total
598    // chracter count.
599    *aEndOffset = GetChildOffset(index + 1);
600  }
601}
602
603LocalAccessible* HyperTextAccessibleWrap::LeafAtOffset(int32_t aOffset) {
604  HyperTextAccessible* text = this;
605  LocalAccessible* child = nullptr;
606  // The offset needed should "attach" the previous accessible if
607  // in between two accessibles.
608  int32_t innerOffset = aOffset > 0 ? aOffset - 1 : aOffset;
609  do {
610    int32_t childIdx = text->GetChildIndexAtOffset(innerOffset);
611    if (childIdx == -1) {
612      return text;
613    }
614
615    child = text->LocalChildAt(childIdx);
616    if (!child || nsAccUtils::MustPrune(text)) {
617      return text;
618    }
619
620    innerOffset -= text->GetChildOffset(childIdx);
621
622    text = child->AsHyperText();
623  } while (text);
624
625  return child;
626}
627
628void HyperTextAccessibleWrap::SelectRange(int32_t aStartOffset,
629                                          HyperTextAccessible* aEndContainer,
630                                          int32_t aEndOffset) {
631  TextRange range(this, this, aStartOffset, aEndContainer, aEndOffset);
632  range.SetSelectionAt(0);
633}
634
635TextPoint HyperTextAccessibleWrap::FindTextPoint(
636    int32_t aOffset, nsDirection aDirection, nsSelectionAmount aAmount,
637    EWordMovementType aWordMovementType) {
638  // Layout can remain trapped in an editable. We normalize out of
639  // it if we are in its last offset.
640  HyperTextIterator iter(this, aOffset, this, CharacterCount());
641  if (aDirection == eDirNext) {
642    iter.NormalizeForward();
643  } else {
644    iter.NormalizeBackward();
645  }
646
647  // Find a leaf accessible frame to start with. PeekOffset wants this.
648  HyperTextAccessible* text = iter.mCurrentContainer;
649  LocalAccessible* child = nullptr;
650  int32_t innerOffset = iter.mCurrentStartOffset;
651
652  do {
653    int32_t childIdx = text->GetChildIndexAtOffset(innerOffset);
654
655    // We can have an empty text leaf as our only child. Since empty text
656    // leaves are not accessible we then have no children, but 0 is a valid
657    // innerOffset.
658    if (childIdx == -1) {
659      NS_ASSERTION(innerOffset == 0 && !text->ChildCount(), "No childIdx?");
660      return TextPoint(text, 0);
661    }
662
663    child = text->LocalChildAt(childIdx);
664    if (child->IsHyperText() && !child->ChildCount()) {
665      // If this is a childless hypertext, jump to its
666      // previous or next sibling, depending on
667      // direction.
668      if (aDirection == eDirPrevious && childIdx > 0) {
669        child = text->LocalChildAt(--childIdx);
670      } else if (aDirection == eDirNext &&
671                 childIdx + 1 < static_cast<int32_t>(text->ChildCount())) {
672        child = text->LocalChildAt(++childIdx);
673      }
674    }
675
676    int32_t childOffset = text->GetChildOffset(childIdx);
677
678    if (child->IsHyperText() && aDirection == eDirPrevious && childIdx > 0 &&
679        innerOffset - childOffset == 0) {
680      // If we are searching backwards, and this is the begining of a
681      // segment, get the previous sibling so that layout will start
682      // its search there.
683      childIdx--;
684      innerOffset -= text->GetChildOffset(childIdx);
685      child = text->LocalChildAt(childIdx);
686    } else {
687      innerOffset -= childOffset;
688    }
689
690    text = child->AsHyperText();
691  } while (text);
692
693  nsIFrame* childFrame = child->GetFrame();
694  if (!childFrame) {
695    NS_ERROR("No child frame");
696    return TextPoint(this, aOffset);
697  }
698
699  int32_t innerContentOffset = innerOffset;
700  if (child->IsTextLeaf()) {
701    NS_ASSERTION(childFrame->IsTextFrame(), "Wrong frame!");
702    RenderedToContentOffset(childFrame, innerOffset, &innerContentOffset);
703  }
704
705  nsIFrame* frameAtOffset = childFrame;
706  int32_t offsetInFrame = 0;
707  childFrame->GetChildFrameContainingOffset(innerContentOffset, true,
708                                            &offsetInFrame, &frameAtOffset);
709  if (aDirection == eDirPrevious && offsetInFrame == 0) {
710    // If we are searching backwards, and we are at the start of a frame,
711    // get the previous continuation frame.
712    if (nsIFrame* prevInContinuation = frameAtOffset->GetPrevContinuation()) {
713      frameAtOffset = prevInContinuation;
714    }
715  }
716
717  const bool kIsJumpLinesOk = true;       // okay to jump lines
718  const bool kIsScrollViewAStop = false;  // do not stop at scroll views
719  const bool kIsKeyboardSelect = true;    // is keyboard selection
720  const bool kIsVisualBidi = false;       // use visual order for bidi text
721  nsPeekOffsetStruct pos(
722      aAmount, aDirection, innerContentOffset, nsPoint(0, 0), kIsJumpLinesOk,
723      kIsScrollViewAStop, kIsKeyboardSelect, kIsVisualBidi, false,
724      nsPeekOffsetStruct::ForceEditableRegion::No, aWordMovementType, false);
725  nsresult rv = frameAtOffset->PeekOffset(&pos);
726
727  // PeekOffset fails on last/first lines of the text in certain cases.
728  if (NS_FAILED(rv) && aAmount == eSelectLine) {
729    pos.mAmount = aDirection == eDirNext ? eSelectEndLine : eSelectBeginLine;
730    frameAtOffset->PeekOffset(&pos);
731  }
732  if (!pos.mResultContent) {
733    NS_ERROR("No result content!");
734    return TextPoint(this, aOffset);
735  }
736
737  if (aDirection == eDirNext &&
738      nsContentUtils::PositionIsBefore(pos.mResultContent, mContent, nullptr,
739                                       nullptr)) {
740    // Bug 1652833 makes us sometimes return the first element on the doc.
741    return TextPoint(Document(), nsIAccessibleText::TEXT_OFFSET_END_OF_TEXT);
742  }
743
744  HyperTextAccessible* container =
745      nsAccUtils::GetTextContainer(pos.mResultContent);
746  int32_t offset = container ? container->DOMPointToOffset(
747                                   pos.mResultContent, pos.mContentOffset,
748                                   aDirection == eDirNext)
749                             : 0;
750  return TextPoint(container, offset);
751}
752
753HyperTextAccessibleWrap* HyperTextAccessibleWrap::EditableRoot() {
754  LocalAccessible* editable = nullptr;
755  for (LocalAccessible* acc = this; acc && acc != Document();
756       acc = acc->LocalParent()) {
757    if (acc->NativeState() & states::EDITABLE) {
758      editable = acc;
759    } else {
760      break;
761    }
762  }
763
764  return static_cast<HyperTextAccessibleWrap*>(editable->AsHyperText());
765}
766