3645fe11287ce26be7e203a72aaa67654ec91208
[WebKit-https.git] / Source / WebCore / editing / VisibleUnits.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "VisibleUnits.h"
28
29 #include "Document.h"
30 #include "HTMLElement.h"
31 #include "HTMLNames.h"
32 #include "InlineTextBox.h"
33 #include "NodeTraversal.h"
34 #include "RenderBlockFlow.h"
35 #include "RenderObject.h"
36 #include "RenderedPosition.h"
37 #include "Text.h"
38 #include "TextBoundaries.h"
39 #include "TextBreakIterator.h"
40 #include "TextIterator.h"
41 #include "VisibleSelection.h"
42 #include "htmlediting.h"
43
44 namespace WebCore {
45
46 using namespace HTMLNames;
47 using namespace WTF::Unicode;
48
49 static Node* previousLeafWithSameEditability(Node* node, EditableType editableType)
50 {
51     bool editable = hasEditableStyle(*node, editableType);
52     node = previousLeafNode(node);
53     while (node) {
54         if (editable == hasEditableStyle(*node, editableType))
55             return node;
56         node = previousLeafNode(node);
57     }
58     return nullptr;
59 }
60
61 static Node* nextLeafWithSameEditability(Node* node, EditableType editableType)
62 {
63     if (!node)
64         return nullptr;
65     
66     bool editable = hasEditableStyle(*node, editableType);
67     node = nextLeafNode(node);
68     while (node) {
69         if (editable == hasEditableStyle(*node, editableType))
70             return node;
71         node = nextLeafNode(node);
72     }
73     return nullptr;
74 }
75
76 // FIXME: consolidate with code in previousLinePosition.
77 static Position previousRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
78 {
79     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
80     Node* previousNode = previousLeafWithSameEditability(node, editableType);
81
82     while (previousNode && (!previousNode->renderer() || inSameLine(firstPositionInOrBeforeNode(previousNode), visiblePosition)))
83         previousNode = previousLeafWithSameEditability(previousNode, editableType);
84
85     while (previousNode && !previousNode->isShadowRoot()) {
86         if (highestEditableRoot(firstPositionInOrBeforeNode(previousNode), editableType) != highestRoot)
87             break;
88
89         Position pos = previousNode->hasTagName(brTag) ? positionBeforeNode(previousNode) :
90             createLegacyEditingPosition(previousNode, caretMaxOffset(*previousNode));
91         
92         if (pos.isCandidate())
93             return pos;
94
95         previousNode = previousLeafWithSameEditability(previousNode, editableType);
96     }
97     return Position();
98 }
99
100 static Position nextRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
101 {
102     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
103     Node* nextNode = nextLeafWithSameEditability(node, editableType);
104     while (nextNode && (!nextNode->renderer() || inSameLine(firstPositionInOrBeforeNode(nextNode), visiblePosition)))
105         nextNode = nextLeafWithSameEditability(nextNode, ContentIsEditable);
106
107     while (nextNode && !nextNode->isShadowRoot()) {
108         if (highestEditableRoot(firstPositionInOrBeforeNode(nextNode), editableType) != highestRoot)
109             break;
110
111         Position pos;
112         pos = createLegacyEditingPosition(nextNode, caretMinOffset(*nextNode));
113         
114         if (pos.isCandidate())
115             return pos;
116
117         nextNode = nextLeafWithSameEditability(nextNode, editableType);
118     }
119     return Position();
120 }
121
122 class CachedLogicallyOrderedLeafBoxes {
123 public:
124     CachedLogicallyOrderedLeafBoxes();
125
126     const InlineBox* previousTextOrLineBreakBox(const RootInlineBox*, const InlineTextBox*);
127     const InlineBox* nextTextOrLineBreakBox(const RootInlineBox*, const InlineTextBox*);
128
129     size_t size() const { return m_leafBoxes.size(); }
130     const InlineBox* firstBox() const { return m_leafBoxes[0]; }
131
132 private:
133     const Vector<InlineBox*>& collectBoxes(const RootInlineBox*);
134     int boxIndexInLeaves(const InlineTextBox*) const;
135
136     const RootInlineBox* m_rootInlineBox { nullptr };
137     Vector<InlineBox*> m_leafBoxes;
138 };
139
140 CachedLogicallyOrderedLeafBoxes::CachedLogicallyOrderedLeafBoxes()
141 {
142 }
143
144 const InlineBox* CachedLogicallyOrderedLeafBoxes::previousTextOrLineBreakBox(const RootInlineBox* root, const InlineTextBox* box)
145 {
146     if (!root)
147         return nullptr;
148
149     collectBoxes(root);
150
151     // If box is null, root is box's previous RootInlineBox, and previousBox is the last logical box in root.
152     int boxIndex = m_leafBoxes.size() - 1;
153     if (box)
154         boxIndex = boxIndexInLeaves(box) - 1;
155
156     for (int i = boxIndex; i >= 0; --i) {
157         InlineBox* box = m_leafBoxes[i];
158         if (box->isInlineTextBox() || box->renderer().isBR())
159             return box;
160     }
161
162     return nullptr;
163 }
164
165 const InlineBox* CachedLogicallyOrderedLeafBoxes::nextTextOrLineBreakBox(const RootInlineBox* root, const InlineTextBox* box)
166 {
167     if (!root)
168         return nullptr;
169
170     collectBoxes(root);
171
172     // If box is null, root is box's next RootInlineBox, and nextBox is the first logical box in root.
173     // Otherwise, root is box's RootInlineBox, and nextBox is the next logical box in the same line.
174     size_t nextBoxIndex = 0;
175     if (box)
176         nextBoxIndex = boxIndexInLeaves(box) + 1;
177
178     for (size_t i = nextBoxIndex; i < m_leafBoxes.size(); ++i) {
179         InlineBox* box = m_leafBoxes[i];
180         if (box->isInlineTextBox() || box->renderer().isBR())
181             return box;
182     }
183
184     return nullptr;
185 }
186
187 const Vector<InlineBox*>& CachedLogicallyOrderedLeafBoxes::collectBoxes(const RootInlineBox* root)
188 {
189     if (m_rootInlineBox != root) {
190         m_rootInlineBox = root;
191         m_leafBoxes.clear();
192         root->collectLeafBoxesInLogicalOrder(m_leafBoxes);
193     }
194     return m_leafBoxes;
195 }
196
197 int CachedLogicallyOrderedLeafBoxes::boxIndexInLeaves(const InlineTextBox* box) const
198 {
199     for (size_t i = 0; i < m_leafBoxes.size(); ++i) {
200         if (box == m_leafBoxes[i])
201             return i;
202     }
203     return 0;
204 }
205
206 static const InlineBox* logicallyPreviousBox(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
207     bool& previousBoxInDifferentBlock, CachedLogicallyOrderedLeafBoxes& leafBoxes)
208 {
209     const InlineBox* startBox = textBox;
210
211     const InlineBox* previousBox = leafBoxes.previousTextOrLineBreakBox(&startBox->root(), textBox);
212     if (previousBox)
213         return previousBox;
214
215     previousBox = leafBoxes.previousTextOrLineBreakBox(startBox->root().prevRootBox(), 0);
216     if (previousBox)
217         return previousBox;
218
219     while (1) {
220         Node* startNode = startBox->renderer().nonPseudoNode();
221         if (!startNode)
222             break;
223
224         Position position = previousRootInlineBoxCandidatePosition(startNode, visiblePosition, ContentIsEditable);
225         if (position.isNull())
226             break;
227
228         RenderedPosition renderedPosition(position, DOWNSTREAM);
229         RootInlineBox* previousRoot = renderedPosition.rootBox();
230         if (!previousRoot)
231             break;
232
233         previousBox = leafBoxes.previousTextOrLineBreakBox(previousRoot, 0);
234         if (previousBox) {
235             previousBoxInDifferentBlock = true;
236             return previousBox;
237         }
238
239         if (!leafBoxes.size())
240             break;
241         startBox = leafBoxes.firstBox();
242     }
243     return 0;
244 }
245
246
247 static const InlineBox* logicallyNextBox(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
248     bool& nextBoxInDifferentBlock, CachedLogicallyOrderedLeafBoxes& leafBoxes)
249 {
250     const InlineBox* startBox = textBox;
251
252     const InlineBox* nextBox = leafBoxes.nextTextOrLineBreakBox(&startBox->root(), textBox);
253     if (nextBox)
254         return nextBox;
255
256     nextBox = leafBoxes.nextTextOrLineBreakBox(startBox->root().nextRootBox(), 0);
257     if (nextBox)
258         return nextBox;
259
260     while (1) {
261         Node* startNode = startBox->renderer().nonPseudoNode();
262         if (!startNode)
263             break;
264
265         Position position = nextRootInlineBoxCandidatePosition(startNode, visiblePosition, ContentIsEditable);
266         if (position.isNull())
267             break;
268
269         RenderedPosition renderedPosition(position, DOWNSTREAM);
270         RootInlineBox* nextRoot = renderedPosition.rootBox();
271         if (!nextRoot)
272             break;
273
274         nextBox = leafBoxes.nextTextOrLineBreakBox(nextRoot, 0);
275         if (nextBox) {
276             nextBoxInDifferentBlock = true;
277             return nextBox;
278         }
279
280         if (!leafBoxes.size())
281             break;
282         startBox = leafBoxes.firstBox();
283     }
284     return 0;
285 }
286
287 static TextBreakIterator* wordBreakIteratorForMinOffsetBoundary(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
288     int& previousBoxLength, bool& previousBoxInDifferentBlock, Vector<UChar, 1024>& string, CachedLogicallyOrderedLeafBoxes& leafBoxes)
289 {
290     previousBoxInDifferentBlock = false;
291
292     // FIXME: Handle the case when we don't have an inline text box.
293     const InlineBox* previousBox = logicallyPreviousBox(visiblePosition, textBox, previousBoxInDifferentBlock, leafBoxes);
294
295     string.clear();
296
297     if (is<InlineTextBox>(previousBox)) {
298         const auto& previousTextBox = downcast<InlineTextBox>(*previousBox);
299         previousBoxLength = previousTextBox.len();
300         append(string, StringView(previousTextBox.renderer().text()).substring(previousTextBox.start(), previousBoxLength));
301     }
302     append(string, StringView(textBox->renderer().text()).substring(textBox->start(), textBox->len()));
303
304     return wordBreakIterator(StringView(string.data(), string.size()));
305 }
306
307 static TextBreakIterator* wordBreakIteratorForMaxOffsetBoundary(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
308     bool& nextBoxInDifferentBlock, Vector<UChar, 1024>& string, CachedLogicallyOrderedLeafBoxes& leafBoxes)
309 {
310     nextBoxInDifferentBlock = false;
311
312     // FIXME: Handle the case when we don't have an inline text box.
313     const InlineBox* nextBox = logicallyNextBox(visiblePosition, textBox, nextBoxInDifferentBlock, leafBoxes);
314
315     string.clear();
316     append(string, StringView(textBox->renderer().text()).substring(textBox->start(), textBox->len()));
317     if (is<InlineTextBox>(nextBox)) {
318         const auto& nextTextBox = downcast<InlineTextBox>(*nextBox);
319         append(string, StringView(nextTextBox.renderer().text()).substring(nextTextBox.start(), nextTextBox.len()));
320     }
321
322     return wordBreakIterator(StringView(string.data(), string.size()));
323 }
324
325 static bool isLogicalStartOfWord(TextBreakIterator* iter, int position, bool hardLineBreak)
326 {
327     bool boundary = hardLineBreak ? true : isTextBreak(iter, position);
328     if (!boundary)
329         return false;
330
331     textBreakFollowing(iter, position);
332     // isWordTextBreak returns true after moving across a word and false after moving across a punctuation/space.
333     return isWordTextBreak(iter);
334 }
335
336 static bool islogicalEndOfWord(TextBreakIterator* iter, int position, bool hardLineBreak)
337 {
338     bool boundary = isTextBreak(iter, position);
339     return (hardLineBreak || boundary) && isWordTextBreak(iter);
340 }
341
342 enum CursorMovementDirection { MoveLeft, MoveRight };
343
344 static VisiblePosition visualWordPosition(const VisiblePosition& visiblePosition, CursorMovementDirection direction, 
345     bool skipsSpaceWhenMovingRight)
346 {
347     if (visiblePosition.isNull())
348         return VisiblePosition();
349
350     TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
351     InlineBox* previouslyVisitedBox = nullptr;
352     VisiblePosition current = visiblePosition;
353     TextBreakIterator* iter = nullptr;
354
355     CachedLogicallyOrderedLeafBoxes leafBoxes;
356     Vector<UChar, 1024> string;
357
358     while (1) {
359         VisiblePosition adjacentCharacterPosition = direction == MoveRight ? current.right(true) : current.left(true); 
360         if (adjacentCharacterPosition == current || adjacentCharacterPosition.isNull())
361             return VisiblePosition();
362     
363         InlineBox* box;
364         int offsetInBox;
365         adjacentCharacterPosition.deepEquivalent().getInlineBoxAndOffset(UPSTREAM, box, offsetInBox);
366     
367         if (!box)
368             break;
369         if (!is<InlineTextBox>(*box)) {
370             current = adjacentCharacterPosition;
371             continue;
372         }
373
374         InlineTextBox& textBox = downcast<InlineTextBox>(*box);
375         int previousBoxLength = 0;
376         bool previousBoxInDifferentBlock = false;
377         bool nextBoxInDifferentBlock = false;
378         bool movingIntoNewBox = previouslyVisitedBox != box;
379
380         if (offsetInBox == box->caretMinOffset())
381             iter = wordBreakIteratorForMinOffsetBoundary(visiblePosition, &textBox, previousBoxLength, previousBoxInDifferentBlock, string, leafBoxes);
382         else if (offsetInBox == box->caretMaxOffset())
383             iter = wordBreakIteratorForMaxOffsetBoundary(visiblePosition, &textBox, nextBoxInDifferentBlock, string, leafBoxes);
384         else if (movingIntoNewBox) {
385             iter = wordBreakIterator(StringView(textBox.renderer().text()).substring(textBox.start(), textBox.len()));
386             previouslyVisitedBox = box;
387         }
388
389         if (!iter)
390             break;
391
392         textBreakFirst(iter);
393         int offsetInIterator = offsetInBox - textBox.start() + previousBoxLength;
394
395         bool isWordBreak;
396         bool boxHasSameDirectionalityAsBlock = box->direction() == blockDirection;
397         bool movingBackward = (direction == MoveLeft && box->direction() == LTR) || (direction == MoveRight && box->direction() == RTL);
398         if ((skipsSpaceWhenMovingRight && boxHasSameDirectionalityAsBlock)
399             || (!skipsSpaceWhenMovingRight && movingBackward)) {
400             bool logicalStartInRenderer = offsetInBox == static_cast<int>(textBox.start()) && previousBoxInDifferentBlock;
401             isWordBreak = isLogicalStartOfWord(iter, offsetInIterator, logicalStartInRenderer);
402         } else {
403             bool logicalEndInRenderer = offsetInBox == static_cast<int>(textBox.start() + textBox.len()) && nextBoxInDifferentBlock;
404             isWordBreak = islogicalEndOfWord(iter, offsetInIterator, logicalEndInRenderer);
405         }      
406
407         if (isWordBreak)
408             return adjacentCharacterPosition;
409     
410         current = adjacentCharacterPosition;
411     }
412     return VisiblePosition();
413 }
414
415 VisiblePosition leftWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
416 {
417     VisiblePosition leftWordBreak = visualWordPosition(visiblePosition, MoveLeft, skipsSpaceWhenMovingRight);
418     leftWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(leftWordBreak);
419     
420     // FIXME: How should we handle a non-editable position?
421     if (leftWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
422         TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
423         leftWordBreak = blockDirection == LTR ? startOfEditableContent(visiblePosition) : endOfEditableContent(visiblePosition);
424     }
425     return leftWordBreak;
426 }
427
428 VisiblePosition rightWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
429 {
430     VisiblePosition rightWordBreak = visualWordPosition(visiblePosition, MoveRight, skipsSpaceWhenMovingRight);
431     rightWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(rightWordBreak);
432
433     // FIXME: How should we handle a non-editable position?
434     if (rightWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
435         TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
436         rightWordBreak = blockDirection == LTR ? endOfEditableContent(visiblePosition) : startOfEditableContent(visiblePosition);
437     }
438     return rightWordBreak;
439 }
440
441
442 static void prepend(Vector<UChar, 1024>& buffer, StringView string)
443 {
444     unsigned oldSize = buffer.size();
445     unsigned length = string.length();
446     buffer.grow(oldSize + length);
447     memmove(buffer.data() + length, buffer.data(), oldSize * sizeof(UChar));
448     for (unsigned i = 0; i < length; ++i)
449         buffer[i] = string[i];
450 }
451
452 static void prependRepeatedCharacter(Vector<UChar, 1024>& buffer, UChar character, unsigned count)
453 {
454     unsigned oldSize = buffer.size();
455     buffer.grow(oldSize + count);
456     memmove(buffer.data() + count, buffer.data(), oldSize * sizeof(UChar));
457     for (unsigned i = 0; i < count; ++i)
458         buffer[i] = character;
459 }
460
461 static void appendRepeatedCharacter(Vector<UChar, 1024>& buffer, UChar character, unsigned count)
462 {
463     unsigned oldSize = buffer.size();
464     buffer.grow(oldSize + count);
465     for (unsigned i = 0; i < count; ++i)
466         buffer[oldSize + i] = character;
467 }
468
469 unsigned suffixLengthForRange(RefPtr<Range> forwardsScanRange, Vector<UChar, 1024>& string)
470 {
471     unsigned suffixLength = 0;
472     TextIterator forwardsIterator(forwardsScanRange.get());
473     while (!forwardsIterator.atEnd()) {
474         StringView text = forwardsIterator.text();
475         unsigned i = endOfFirstWordBoundaryContext(text);
476         append(string, text.substring(0, i));
477         suffixLength += i;
478         if (i < text.length())
479             break;
480         forwardsIterator.advance();
481     }
482     return suffixLength;
483 }
484
485 unsigned prefixLengthForRange(RefPtr<Range> backwardsScanRange, Vector<UChar, 1024>& string)
486 {
487     unsigned prefixLength = 0;
488     SimplifiedBackwardsTextIterator backwardsIterator(*backwardsScanRange);
489     while (!backwardsIterator.atEnd()) {
490         StringView text = backwardsIterator.text();
491         int i = startOfLastWordBoundaryContext(text);
492         prepend(string, text.substring(i));
493         prefixLength += text.length() - i;
494         if (i > 0)
495             break;
496         backwardsIterator.advance();
497     }
498     return prefixLength;
499 }
500
501 unsigned backwardSearchForBoundaryWithTextIterator(SimplifiedBackwardsTextIterator& it, Vector<UChar, 1024>& string, unsigned suffixLength, BoundarySearchFunction searchFunction)
502 {
503     unsigned next = 0;
504     bool needMoreContext = false;
505     while (!it.atEnd()) {
506         bool inTextSecurityMode = it.node() && it.node()->renderer() && it.node()->renderer()->style().textSecurity() != TSNONE;
507         // iterate to get chunks until the searchFunction returns a non-zero value.
508         if (!inTextSecurityMode)
509             prepend(string, it.text());
510         else {
511             // Treat bullets used in the text security mode as regular characters when looking for boundaries
512             prependRepeatedCharacter(string, 'x', it.text().length());
513         }
514         if (string.size() > suffixLength) {
515             next = searchFunction(StringView(string.data(), string.size()), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
516             if (next > 1) // FIXME: This is a work around for https://webkit.org/b/115070. We need to provide more contexts in general case.
517                 break;
518         }
519         it.advance();
520     }
521     if (needMoreContext && string.size() > suffixLength) {
522         // The last search returned the beginning of the buffer and asked for more context,
523         // but there is no earlier text. Force a search with what's available.
524         next = searchFunction(StringView(string.data(), string.size()), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);
525         ASSERT(!needMoreContext);
526     }
527     
528     return next;
529 }
530
531 unsigned forwardSearchForBoundaryWithTextIterator(TextIterator& it, Vector<UChar, 1024>& string, unsigned prefixLength, BoundarySearchFunction searchFunction)
532 {
533     unsigned next = 0;
534     bool needMoreContext = false;
535     while (!it.atEnd()) {
536         bool inTextSecurityMode = it.node() && it.node()->renderer() && it.node()->renderer()->style().textSecurity() != TSNONE;
537         // Keep asking the iterator for chunks until the search function
538         // returns an end value not equal to the length of the string passed to it.
539         if (!inTextSecurityMode)
540             append(string, it.text());
541         else {
542             // Treat bullets used in the text security mode as regular characters when looking for boundaries
543             appendRepeatedCharacter(string, 'x', it.text().length());
544         }
545         if (string.size() > prefixLength) {
546             next = searchFunction(StringView(string.data(), string.size()), prefixLength, MayHaveMoreContext, needMoreContext);
547             if (next != string.size())
548                 break;
549         }
550         it.advance();
551     }
552     if (needMoreContext && string.size() > prefixLength) {
553         // The last search returned the end of the buffer and asked for more context,
554         // but there is no further text. Force a search with what's available.
555         next = searchFunction(StringView(string.data(), string.size()), prefixLength, DontHaveMoreContext, needMoreContext);
556         ASSERT(!needMoreContext);
557     }
558     
559     return next;
560 }
561
562 static VisiblePosition previousBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
563 {
564     Position pos = c.deepEquivalent();
565     Node* boundary = pos.parentEditingBoundary();
566     if (!boundary)
567         return VisiblePosition();
568
569     Document& boundaryDocument = boundary->document();
570     Position start = createLegacyEditingPosition(boundary, 0).parentAnchoredEquivalent();
571     Position end = pos.parentAnchoredEquivalent();
572
573     if (start.isNull() || end.isNull())
574         return VisiblePosition();
575
576     Ref<Range> searchRange = Range::create(boundaryDocument);
577     
578     Vector<UChar, 1024> string;
579     unsigned suffixLength = 0;
580
581     ExceptionCode ec = 0;
582     if (requiresContextForWordBoundary(c.characterBefore())) {
583         RefPtr<Range> forwardsScanRange(boundaryDocument.createRange());
584         forwardsScanRange->setEndAfter(*boundary, ec);
585         forwardsScanRange->setStart(*end.deprecatedNode(), end.deprecatedEditingOffset(), ec);
586         suffixLength = suffixLengthForRange(forwardsScanRange, string);
587     }
588
589     searchRange->setStart(*start.deprecatedNode(), start.deprecatedEditingOffset(), ec);
590     searchRange->setEnd(*end.deprecatedNode(), end.deprecatedEditingOffset(), ec);
591
592     ASSERT(!ec);
593     if (ec)
594         return VisiblePosition();
595
596     SimplifiedBackwardsTextIterator it(searchRange);
597     unsigned next = backwardSearchForBoundaryWithTextIterator(it, string, suffixLength, searchFunction);
598
599     if (!next)
600         return VisiblePosition(it.atEnd() ? searchRange->startPosition() : pos, DOWNSTREAM);
601
602     Node& node = it.atEnd() ? searchRange->startContainer() : it.range()->startContainer();
603     if ((node.isTextNode() && static_cast<int>(next) <= node.maxCharacterOffset()) || (node.renderer() && node.renderer()->isBR() && !next)) {
604         // The next variable contains a usable index into a text node
605         return VisiblePosition(createLegacyEditingPosition(&node, next), DOWNSTREAM);
606     }
607
608     // Use the character iterator to translate the next value into a DOM position.
609     BackwardsCharacterIterator charIt(searchRange);
610     charIt.advance(string.size() - suffixLength - next);
611     // FIXME: charIt can get out of shadow host.
612     return VisiblePosition(charIt.range()->endPosition(), DOWNSTREAM);
613 }
614
615 static VisiblePosition nextBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
616 {
617     Position pos = c.deepEquivalent();
618     Node* boundary = pos.parentEditingBoundary();
619     if (!boundary)
620         return VisiblePosition();
621
622     Document& boundaryDocument = boundary->document();
623     Ref<Range> searchRange = boundaryDocument.createRange();
624     Position start(pos.parentAnchoredEquivalent());
625
626     Vector<UChar, 1024> string;
627     unsigned prefixLength = 0;
628
629     if (requiresContextForWordBoundary(c.characterAfter())) {
630         RefPtr<Range> backwardsScanRange(boundaryDocument.createRange());
631         if (start.deprecatedNode())
632             backwardsScanRange->setEnd(*start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
633         prefixLength = prefixLengthForRange(backwardsScanRange, string);
634     }
635
636     searchRange->selectNodeContents(*boundary, IGNORE_EXCEPTION);
637     if (start.deprecatedNode())
638         searchRange->setStart(*start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
639     TextIterator it(searchRange.ptr(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
640     unsigned next = forwardSearchForBoundaryWithTextIterator(it, string, prefixLength, searchFunction);
641     
642     if (it.atEnd() && next == string.size())
643         pos = searchRange->endPosition();
644     else if (next > prefixLength) {
645         // Use the character iterator to translate the next value into a DOM position.
646         CharacterIterator charIt(searchRange, TextIteratorEmitsCharactersBetweenAllVisiblePositions);
647         charIt.advance(next - prefixLength - 1);
648         RefPtr<Range> characterRange = charIt.range();
649         pos = characterRange->endPosition();
650         
651         if (charIt.text()[0] == '\n') {
652             // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)
653             VisiblePosition visPos = VisiblePosition(pos);
654             if (visPos == VisiblePosition(characterRange->startPosition())) {
655                 charIt.advance(1);
656                 pos = charIt.range()->startPosition();
657             }
658         }
659     }
660
661     // generate VisiblePosition, use UPSTREAM affinity if possible
662     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
663 }
664
665 // ---------
666
667 unsigned startWordBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
668 {
669     ASSERT(offset);
670     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(text.substring(0, offset))) {
671         needMoreContext = true;
672         return 0;
673     }
674     needMoreContext = false;
675     int start, end;
676     U16_BACK_1(text, 0, offset);
677     findWordBoundary(text, offset, &start, &end);
678     return start;
679 }
680
681 VisiblePosition startOfWord(const VisiblePosition& c, EWordSide side)
682 {
683     // FIXME: This returns a null VP for c at the start of the document
684     // and side == LeftWordIfOnBoundary
685     VisiblePosition p = c;
686     if (side == RightWordIfOnBoundary) {
687         // at paragraph end, the startofWord is the current position
688         if (isEndOfParagraph(c))
689             return c;
690         
691         p = c.next();
692         if (p.isNull())
693             return c;
694     }
695     return previousBoundary(p, startWordBoundary);
696 }
697
698 unsigned endWordBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
699 {
700     ASSERT(offset <= text.length());
701     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(text.substring(offset)) == text.length() - offset) {
702         needMoreContext = true;
703         return text.length();
704     }
705     needMoreContext = false;
706     int end;
707     findEndWordBoundary(text, offset, &end);
708     return end;
709 }
710
711 VisiblePosition endOfWord(const VisiblePosition& c, EWordSide side)
712 {
713     VisiblePosition p = c;
714     if (side == LeftWordIfOnBoundary) {
715         if (isStartOfParagraph(c))
716             return c;
717             
718         p = c.previous();
719         if (p.isNull())
720             return c;
721     } else if (isEndOfParagraph(c))
722         return c;
723     
724     return nextBoundary(p, endWordBoundary);
725 }
726
727 static unsigned previousWordPositionBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
728 {
729     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(text.substring(0, offset))) {
730         needMoreContext = true;
731         return 0;
732     }
733     needMoreContext = false;
734     return findNextWordFromIndex(text, offset, false);
735 }
736
737 VisiblePosition previousWordPosition(const VisiblePosition& position)
738 {
739     return position.honorEditingBoundaryAtOrBefore(previousBoundary(position, previousWordPositionBoundary));
740 }
741
742 static unsigned nextWordPositionBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
743 {
744     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(text.substring(offset)) == text.length() - offset) {
745         needMoreContext = true;
746         return text.length();
747     }
748     needMoreContext = false;
749     return findNextWordFromIndex(text, offset, true);
750 }
751
752 VisiblePosition nextWordPosition(const VisiblePosition& position)
753 {
754     return position.honorEditingBoundaryAtOrAfter(nextBoundary(position, nextWordPositionBoundary));
755 }
756
757 bool isStartOfWord(const VisiblePosition& p)
758 {
759     return p.isNotNull() && p == startOfWord(p, RightWordIfOnBoundary);
760 }
761
762 // ---------
763
764 enum LineEndpointComputationMode { UseLogicalOrdering, UseInlineBoxOrdering };
765 static VisiblePosition startPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
766 {
767     if (c.isNull())
768         return VisiblePosition();
769
770     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
771     if (!rootBox) {
772         // There are VisiblePositions at offset 0 in blocks without
773         // RootInlineBoxes, like empty editable blocks and bordered blocks.
774         Position p = c.deepEquivalent();
775         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
776             return c;
777
778         return VisiblePosition();
779     }
780
781     Node* startNode;
782     InlineBox* startBox;
783     if (mode == UseLogicalOrdering) {
784         startNode = rootBox->getLogicalStartBoxWithNode(startBox);
785         if (!startNode)
786             return VisiblePosition();
787     } else {
788         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
789         // and so cannot be represented by a VisiblePosition. Use whatever follows instead.
790         startBox = rootBox->firstLeafChild();
791         while (true) {
792             if (!startBox)
793                 return VisiblePosition();
794
795             startNode = startBox->renderer().nonPseudoNode();
796             if (startNode)
797                 break;
798
799             startBox = startBox->nextLeafChild();
800         }
801     }
802
803     return is<Text>(*startNode) ? Position(downcast<Text>(startNode), downcast<InlineTextBox>(*startBox).start())
804         : positionBeforeNode(startNode);
805 }
806
807 static VisiblePosition startOfLine(const VisiblePosition& c, LineEndpointComputationMode mode, bool* reachedBoundary)
808 {
809     if (reachedBoundary)
810         *reachedBoundary = false;
811     // TODO: this is the current behavior that might need to be fixed.
812     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
813     VisiblePosition visPos = startPositionForLine(c, mode);
814
815     if (mode == UseLogicalOrdering) {
816         if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
817             if (!editableRoot->contains(visPos.deepEquivalent().containerNode())) {
818                 VisiblePosition newPosition = firstPositionInNode(editableRoot);
819                 if (reachedBoundary)
820                     *reachedBoundary = c == newPosition;
821                 return newPosition;
822             }
823         }
824     }
825
826     return c.honorEditingBoundaryAtOrBefore(visPos, reachedBoundary);
827 }
828
829 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
830 VisiblePosition startOfLine(const VisiblePosition& currentPosition)
831 {
832     return startOfLine(currentPosition, UseInlineBoxOrdering, nullptr);
833 }
834
835 VisiblePosition logicalStartOfLine(const VisiblePosition& currentPosition, bool* reachedBoundary)
836 {
837     return startOfLine(currentPosition, UseLogicalOrdering, reachedBoundary);
838 }
839
840 static VisiblePosition endPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
841 {
842     if (c.isNull())
843         return VisiblePosition();
844
845     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
846     if (!rootBox) {
847         // There are VisiblePositions at offset 0 in blocks without
848         // RootInlineBoxes, like empty editable blocks and bordered blocks.
849         Position p = c.deepEquivalent();
850         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
851             return c;
852         return VisiblePosition();
853     }
854
855     Node* endNode;
856     InlineBox* endBox;
857     if (mode == UseLogicalOrdering) {
858         endNode = rootBox->getLogicalEndBoxWithNode(endBox);
859         if (!endNode)
860             return VisiblePosition();
861     } else {
862         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
863         // and so cannot be represented by a VisiblePosition. Use whatever precedes instead.
864         endBox = rootBox->lastLeafChild();
865         while (true) {
866             if (!endBox)
867                 return VisiblePosition();
868
869             endNode = endBox->renderer().nonPseudoNode();
870             if (endNode)
871                 break;
872             
873             endBox = endBox->prevLeafChild();
874         }
875     }
876
877     Position pos;
878     if (is<HTMLBRElement>(*endNode))
879         pos = positionBeforeNode(endNode);
880     else if (is<InlineTextBox>(*endBox) && is<Text>(*endNode)) {
881         auto& endTextBox = downcast<InlineTextBox>(*endBox);
882         int endOffset = endTextBox.start();
883         if (!endTextBox.isLineBreak())
884             endOffset += endTextBox.len();
885         pos = Position(downcast<Text>(endNode), endOffset);
886     } else
887         pos = positionAfterNode(endNode);
888     
889     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
890 }
891
892 static bool inSameLogicalLine(const VisiblePosition& a, const VisiblePosition& b)
893 {
894     return a.isNotNull() && logicalStartOfLine(a) == logicalStartOfLine(b);
895 }
896
897 static VisiblePosition endOfLine(const VisiblePosition& c, LineEndpointComputationMode mode, bool* reachedBoundary)
898 {
899     if (reachedBoundary)
900         *reachedBoundary = false;
901     // TODO: this is the current behavior that might need to be fixed.
902     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
903     VisiblePosition visPos = endPositionForLine(c, mode);
904
905     if (mode == UseLogicalOrdering) {
906         // Make sure the end of line is at the same line as the given input position. For a wrapping line, the logical end
907         // position for the not-last-2-lines might incorrectly hand back the logical beginning of the next line. 
908         // For example, <div contenteditable dir="rtl" style="line-break:before-white-space">abcdefg abcdefg abcdefg
909         // a abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg </div>
910         // In this case, use the previous position of the computed logical end position.
911         if (!inSameLogicalLine(c, visPos))
912             visPos = visPos.previous();
913
914         if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
915             if (!editableRoot->contains(visPos.deepEquivalent().containerNode())) {
916                 VisiblePosition newPosition = lastPositionInNode(editableRoot);
917                 if (reachedBoundary)
918                     *reachedBoundary = c == newPosition;
919                 return newPosition;
920             }
921         }
922
923         return c.honorEditingBoundaryAtOrAfter(visPos, reachedBoundary);
924     }
925
926     // Make sure the end of line is at the same line as the given input position. Else use the previous position to 
927     // obtain end of line. This condition happens when the input position is before the space character at the end 
928     // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position
929     // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style
930     // versus lines without that style, which would break before a space by default. 
931     if (!inSameLine(c, visPos)) {
932         visPos = c.previous();
933         if (visPos.isNull())
934             return VisiblePosition();
935         visPos = endPositionForLine(visPos, UseInlineBoxOrdering);
936     }
937     
938     return c.honorEditingBoundaryAtOrAfter(visPos, reachedBoundary);
939 }
940
941 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
942 VisiblePosition endOfLine(const VisiblePosition& currentPosition)
943 {
944     return endOfLine(currentPosition, UseInlineBoxOrdering, nullptr);
945 }
946
947 VisiblePosition logicalEndOfLine(const VisiblePosition& currentPosition, bool* reachedBoundary)
948 {
949     return endOfLine(currentPosition, UseLogicalOrdering, reachedBoundary);
950 }
951
952 bool inSameLine(const VisiblePosition& a, const VisiblePosition& b)
953 {
954     return a.isNotNull() && startOfLine(a) == startOfLine(b);
955 }
956
957 bool isStartOfLine(const VisiblePosition& p)
958 {
959     return p.isNotNull() && p == startOfLine(p);
960 }
961
962 bool isEndOfLine(const VisiblePosition& p)
963 {
964     return p.isNotNull() && p == endOfLine(p);
965 }
966
967 bool isLogicalEndOfLine(const VisiblePosition &p)
968 {
969     return p.isNotNull() && p == logicalEndOfLine(p);
970 }
971
972 static inline IntPoint absoluteLineDirectionPointToLocalPointInBlock(RootInlineBox& root, int lineDirectionPoint)
973 {
974     RenderBlockFlow& containingBlock = root.blockFlow();
975     FloatPoint absoluteBlockPoint = containingBlock.localToAbsolute(FloatPoint()) - toFloatSize(containingBlock.scrollPosition());
976
977     if (containingBlock.isHorizontalWritingMode())
978         return IntPoint(lineDirectionPoint - absoluteBlockPoint.x(), root.blockDirectionPointInLine());
979
980     return IntPoint(root.blockDirectionPointInLine(), lineDirectionPoint - absoluteBlockPoint.y());
981 }
982
983 static Element* rootEditableOrDocumentElement(Node& node, EditableType editableType)
984 {
985     if (hasEditableStyle(node, editableType))
986         return editableRootForPosition(firstPositionInOrBeforeNode(&node), editableType);
987     return node.document().documentElement();
988 }
989
990 VisiblePosition previousLinePosition(const VisiblePosition& visiblePosition, int lineDirectionPoint, EditableType editableType)
991 {
992     Position p = visiblePosition.deepEquivalent();
993     Node* node = p.deprecatedNode();
994
995     if (!node)
996         return VisiblePosition();
997     
998     node->document().updateLayoutIgnorePendingStylesheets();
999     
1000     RenderObject* renderer = node->renderer();
1001     if (!renderer)
1002         return VisiblePosition();
1003
1004     RootInlineBox* root = nullptr;
1005     InlineBox* box;
1006     int ignoredCaretOffset;
1007     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
1008     if (box) {
1009         root = box->root().prevRootBox();
1010         // We want to skip zero height boxes.
1011         // This could happen in case it is a TrailingFloatsRootInlineBox.
1012         if (!root || !root->logicalHeight() || !root->firstLeafChild())
1013             root = nullptr;
1014     }
1015
1016     if (!root) {
1017         Position position = previousRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
1018         if (position.isNotNull()) {
1019             RenderedPosition renderedPosition(position);
1020             root = renderedPosition.rootBox();
1021             if (!root)
1022                 return position;
1023         }
1024     }
1025     
1026     if (root) {
1027         // FIXME: Can be wrong for multi-column layout and with transforms.
1028         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(*root, lineDirectionPoint);
1029         RenderObject& renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
1030         Node* node = renderer.node();
1031         if (node && editingIgnoresContent(node))
1032             return positionInParentBeforeNode(node);
1033         return renderer.positionForPoint(pointInLine, nullptr);
1034     }
1035     
1036     // Could not find a previous line. This means we must already be on the first line.
1037     // Move to the start of the content in this block, which effectively moves us
1038     // to the start of the line we're on.
1039     Element* rootElement = rootEditableOrDocumentElement(*node, editableType);
1040     if (!rootElement)
1041         return VisiblePosition();
1042     return VisiblePosition(firstPositionInNode(rootElement), DOWNSTREAM);
1043 }
1044
1045 VisiblePosition nextLinePosition(const VisiblePosition& visiblePosition, int lineDirectionPoint, EditableType editableType)
1046 {
1047     Position p = visiblePosition.deepEquivalent();
1048     Node* node = p.deprecatedNode();
1049
1050     if (!node)
1051         return VisiblePosition();
1052     
1053     node->document().updateLayoutIgnorePendingStylesheets();
1054
1055     RenderObject* renderer = node->renderer();
1056     if (!renderer)
1057         return VisiblePosition();
1058
1059     RootInlineBox* root = nullptr;
1060     InlineBox* box;
1061     int ignoredCaretOffset;
1062     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
1063     if (box) {
1064         root = box->root().nextRootBox();
1065         // We want to skip zero height boxes.
1066         // This could happen in case it is a TrailingFloatsRootInlineBox.
1067         if (!root || !root->logicalHeight() || !root->firstLeafChild())
1068             root = nullptr;
1069     }
1070
1071     if (!root) {
1072         // FIXME: We need do the same in previousLinePosition.
1073         Node* child = node->traverseToChildAt(p.deprecatedEditingOffset());
1074         node = child ? child : node->lastDescendant();
1075         Position position = nextRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
1076         if (position.isNotNull()) {
1077             RenderedPosition renderedPosition(position);
1078             root = renderedPosition.rootBox();
1079             if (!root)
1080                 return position;
1081         }
1082     }
1083     
1084     if (root) {
1085         // FIXME: Can be wrong for multi-column layout and with transforms.
1086         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(*root, lineDirectionPoint);
1087         RenderObject& renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
1088         Node* node = renderer.node();
1089         if (node && editingIgnoresContent(node))
1090             return positionInParentBeforeNode(node);
1091         return renderer.positionForPoint(pointInLine, nullptr);
1092     }
1093
1094     // Could not find a next line. This means we must already be on the last line.
1095     // Move to the end of the content in this block, which effectively moves us
1096     // to the end of the line we're on.
1097     Element* rootElement = rootEditableOrDocumentElement(*node, editableType);
1098     if (!rootElement)
1099         return VisiblePosition();
1100     return VisiblePosition(lastPositionInNode(rootElement), DOWNSTREAM);
1101 }
1102
1103 // ---------
1104
1105 unsigned startSentenceBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1106 {
1107     // FIXME: The following function can return -1; we don't handle that.
1108     return textBreakPreceding(sentenceBreakIterator(text), text.length());
1109 }
1110
1111 VisiblePosition startOfSentence(const VisiblePosition& position)
1112 {
1113     return previousBoundary(position, startSentenceBoundary);
1114 }
1115
1116 unsigned endSentenceBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1117 {
1118     return textBreakNext(sentenceBreakIterator(text));
1119 }
1120
1121 VisiblePosition endOfSentence(const VisiblePosition& position)
1122 {
1123     // FIXME: This includes the space after the punctuation that marks the end of the sentence.
1124     return nextBoundary(position, endSentenceBoundary);
1125 }
1126
1127 static unsigned previousSentencePositionBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1128 {
1129     // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
1130     // FIXME: The following function can return -1; we don't handle that.
1131     return textBreakPreceding(sentenceBreakIterator(text), text.length());
1132 }
1133
1134 VisiblePosition previousSentencePosition(const VisiblePosition& position)
1135 {
1136     return position.honorEditingBoundaryAtOrBefore(previousBoundary(position, previousSentencePositionBoundary));
1137 }
1138
1139 static unsigned nextSentencePositionBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1140 {
1141     // FIXME: This is identical to endSentenceBoundary.
1142     // That isn't right. This function needs to move to the equivalent position in the following sentence.
1143     return textBreakFollowing(sentenceBreakIterator(text), 0);
1144 }
1145
1146 VisiblePosition nextSentencePosition(const VisiblePosition& position)
1147 {
1148     return position.honorEditingBoundaryAtOrAfter(nextBoundary(position, nextSentencePositionBoundary));
1149 }
1150
1151 Node* findStartOfParagraph(Node* startNode, Node* highestRoot, Node* startBlock, int& offset, Position::AnchorType& type, EditingBoundaryCrossingRule boundaryCrossingRule)
1152 {
1153     Node* node = startNode;
1154     Node* n = startNode;
1155     while (n) {
1156 #if ENABLE(USERSELECT_ALL)
1157         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNode->hasEditableStyle())
1158 #else
1159         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->hasEditableStyle() != startNode->hasEditableStyle())
1160 #endif
1161             break;
1162         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1163             while (n && n->hasEditableStyle() != startNode->hasEditableStyle())
1164                 n = NodeTraversal::previousPostOrder(*n, startBlock);
1165             if (!n || !n->isDescendantOf(highestRoot))
1166                 break;
1167         }
1168         RenderObject* r = n->renderer();
1169         if (!r) {
1170             n = NodeTraversal::previousPostOrder(*n, startBlock);
1171             continue;
1172         }
1173         const RenderStyle& style = r->style();
1174         if (style.visibility() != VISIBLE) {
1175             n = NodeTraversal::previousPostOrder(*n, startBlock);
1176             continue;
1177         }
1178         
1179         if (r->isBR() || isBlock(n))
1180             break;
1181
1182         if (is<RenderText>(*r) && downcast<RenderText>(*r).hasRenderedText()) {
1183             ASSERT_WITH_SECURITY_IMPLICATION(is<Text>(*n));
1184             type = Position::PositionIsOffsetInAnchor;
1185             if (style.preserveNewline()) {
1186                 StringImpl& text = *downcast<RenderText>(*r).text();
1187                 int i = text.length();
1188                 int o = offset;
1189                 if (n == startNode && o < i)
1190                     i = std::max(0, o);
1191                 while (--i >= 0) {
1192                     if (text[i] == '\n') {
1193                         offset = i + 1;
1194                         return n;
1195                     }
1196                 }
1197             }
1198             node = n;
1199             offset = 0;
1200             n = NodeTraversal::previousPostOrder(*n, startBlock);
1201         } else if (editingIgnoresContent(n) || isRenderedTable(n)) {
1202             node = n;
1203             type = Position::PositionIsBeforeAnchor;
1204             n = n->previousSibling() ? n->previousSibling() : NodeTraversal::previousPostOrder(*n, startBlock);
1205         } else
1206             n = NodeTraversal::previousPostOrder(*n, startBlock);
1207     }
1208
1209     return node;
1210 }
1211
1212 Node* findEndOfParagraph(Node* startNode, Node* highestRoot, Node* stayInsideBlock, int& offset, Position::AnchorType& type, EditingBoundaryCrossingRule boundaryCrossingRule)
1213 {
1214     Node* node = startNode;
1215     Node* n = startNode;
1216     while (n) {
1217 #if ENABLE(USERSELECT_ALL)
1218         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNode->hasEditableStyle())
1219 #else
1220         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->hasEditableStyle() != startNode->hasEditableStyle())
1221 #endif
1222             break;
1223         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1224             while (n && n->hasEditableStyle() != startNode->hasEditableStyle())
1225                 n = NodeTraversal::next(*n, stayInsideBlock);
1226             if (!n || !n->isDescendantOf(highestRoot))
1227                 break;
1228         }
1229
1230         RenderObject* r = n->renderer();
1231         if (!r) {
1232             n = NodeTraversal::next(*n, stayInsideBlock);
1233             continue;
1234         }
1235         const RenderStyle& style = r->style();
1236         if (style.visibility() != VISIBLE) {
1237             n = NodeTraversal::next(*n, stayInsideBlock);
1238             continue;
1239         }
1240         
1241         // FIXME: This is wrong when startNode is a block. We should return a position after the block.
1242         if (r->isBR() || isBlock(n))
1243             break;
1244
1245         // FIXME: We avoid returning a position where the renderer can't accept the caret.
1246         if (is<RenderText>(*r) && downcast<RenderText>(*r).hasRenderedText()) {
1247             ASSERT_WITH_SECURITY_IMPLICATION(is<Text>(*n));
1248             type = Position::PositionIsOffsetInAnchor;
1249             if (style.preserveNewline()) {
1250                 StringImpl& text = *downcast<RenderText>(*r).text();
1251                 int o = n == startNode ? offset : 0;
1252                 int length = text.length();
1253                 for (int i = o; i < length; ++i) {
1254                     if (text[i] == '\n') {
1255                         offset = i;
1256                         return n;
1257                     }
1258                 }
1259             }
1260             node = n;
1261             offset = r->caretMaxOffset();
1262             n = NodeTraversal::next(*n, stayInsideBlock);
1263         } else if (editingIgnoresContent(n) || isRenderedTable(n)) {
1264             node = n;
1265             type = Position::PositionIsAfterAnchor;
1266             n = NodeTraversal::nextSkippingChildren(*n, stayInsideBlock);
1267         } else
1268             n = NodeTraversal::next(*n, stayInsideBlock);
1269     }
1270     return node;
1271 }
1272
1273 VisiblePosition startOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1274 {
1275     Position p = c.deepEquivalent();
1276     auto* startNode = p.deprecatedNode();
1277     
1278     if (!startNode)
1279         return VisiblePosition();
1280     
1281     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1282         return positionBeforeNode(startNode);
1283     
1284     Node* startBlock = enclosingBlock(startNode);
1285     
1286     auto* highestRoot = highestEditableRoot(p);
1287     int offset = p.deprecatedEditingOffset();
1288     Position::AnchorType type = p.anchorType();
1289     
1290     auto* node = findStartOfParagraph(startNode, highestRoot, startBlock, offset, type, boundaryCrossingRule);
1291     
1292     if (is<Text>(node))
1293         return VisiblePosition(Position(downcast<Text>(node), offset), DOWNSTREAM);
1294     
1295     if (type == Position::PositionIsOffsetInAnchor) {
1296         ASSERT(type == Position::PositionIsOffsetInAnchor || !offset);
1297         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1298     }
1299     
1300     return VisiblePosition(Position(node, type), DOWNSTREAM);
1301 }
1302
1303 VisiblePosition endOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1304 {    
1305     if (c.isNull())
1306         return VisiblePosition();
1307     
1308     Position p = c.deepEquivalent();
1309     auto* startNode = p.deprecatedNode();
1310     
1311     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1312         return positionAfterNode(startNode);
1313     
1314     auto* startBlock = enclosingBlock(startNode);
1315     auto* stayInsideBlock = startBlock;
1316     
1317     auto* highestRoot = highestEditableRoot(p);
1318     int offset = p.deprecatedEditingOffset();
1319     Position::AnchorType type = p.anchorType();
1320     
1321     auto* node = findEndOfParagraph(startNode, highestRoot, stayInsideBlock, offset, type, boundaryCrossingRule);
1322     
1323     if (is<Text>(node))
1324         return VisiblePosition(Position(downcast<Text>(node), offset), DOWNSTREAM);
1325     
1326     if (type == Position::PositionIsOffsetInAnchor)
1327         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1328
1329     return VisiblePosition(Position(node, type), DOWNSTREAM);
1330 }
1331
1332 // FIXME: isStartOfParagraph(startOfNextParagraph(pos)) is not always true
1333 VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
1334 {
1335     VisiblePosition paragraphEnd(endOfParagraph(visiblePosition, CanSkipOverEditingBoundary));
1336     VisiblePosition afterParagraphEnd(paragraphEnd.next(CannotCrossEditingBoundary));
1337     // The position after the last position in the last cell of a table
1338     // is not the start of the next paragraph.
1339     if (isFirstPositionAfterTable(afterParagraphEnd))
1340         return afterParagraphEnd.next(CannotCrossEditingBoundary);
1341     return afterParagraphEnd;
1342 }
1343
1344 bool inSameParagraph(const VisiblePosition& a, const VisiblePosition& b, EditingBoundaryCrossingRule boundaryCrossingRule)
1345 {
1346     return a.isNotNull() && startOfParagraph(a, boundaryCrossingRule) == startOfParagraph(b, boundaryCrossingRule);
1347 }
1348
1349 bool isStartOfParagraph(const VisiblePosition& pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1350 {
1351     return pos.isNotNull() && pos == startOfParagraph(pos, boundaryCrossingRule);
1352 }
1353
1354 bool isEndOfParagraph(const VisiblePosition& pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1355 {
1356     return pos.isNotNull() && pos == endOfParagraph(pos, boundaryCrossingRule);
1357 }
1358
1359 VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
1360 {
1361     VisiblePosition pos = p;
1362     do {
1363         VisiblePosition n = previousLinePosition(pos, x);
1364         if (n.isNull() || n == pos)
1365             break;
1366         pos = n;
1367     } while (inSameParagraph(p, pos));
1368     return pos;
1369 }
1370
1371 VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
1372 {
1373     VisiblePosition pos = p;
1374     do {
1375         VisiblePosition n = nextLinePosition(pos, x);
1376         if (n.isNull() || n == pos)
1377             break;
1378         pos = n;
1379     } while (inSameParagraph(p, pos));
1380     return pos;
1381 }
1382
1383 // ---------
1384
1385 VisiblePosition startOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1386 {
1387     Position position = visiblePosition.deepEquivalent();
1388     Node* startBlock;
1389     if (!position.containerNode() || !(startBlock = enclosingBlock(position.containerNode(), rule)))
1390         return VisiblePosition();
1391     return firstPositionInNode(startBlock);
1392 }
1393
1394 VisiblePosition endOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1395 {
1396     Position position = visiblePosition.deepEquivalent();
1397     Node* endBlock;
1398     if (!position.containerNode() || !(endBlock = enclosingBlock(position.containerNode(), rule)))
1399         return VisiblePosition();
1400     return lastPositionInNode(endBlock);
1401 }
1402
1403 bool inSameBlock(const VisiblePosition& a, const VisiblePosition& b)
1404 {
1405     return !a.isNull() && enclosingBlock(a.deepEquivalent().containerNode()) == enclosingBlock(b.deepEquivalent().containerNode());
1406 }
1407
1408 bool isStartOfBlock(const VisiblePosition& pos)
1409 {
1410     return pos.isNotNull() && pos == startOfBlock(pos, CanCrossEditingBoundary);
1411 }
1412
1413 bool isEndOfBlock(const VisiblePosition& pos)
1414 {
1415     return pos.isNotNull() && pos == endOfBlock(pos, CanCrossEditingBoundary);
1416 }
1417
1418 // ---------
1419
1420 VisiblePosition startOfDocument(const Node* node)
1421 {
1422     if (!node || !node->document().documentElement())
1423         return VisiblePosition();
1424     
1425     // The canonicalization of the position at (documentElement, 0) can turn the visible
1426     // position to null, even when there's a valid candidate to be had, because the root HTML element
1427     // is not content editable.  So we construct directly from the valid candidate.
1428     Position firstCandidate = nextCandidate(createLegacyEditingPosition(node->document().documentElement(), 0));
1429     if (firstCandidate.isNull())
1430         return VisiblePosition();
1431     return VisiblePosition(firstCandidate);
1432 }
1433
1434 VisiblePosition startOfDocument(const VisiblePosition& c)
1435 {
1436     return startOfDocument(c.deepEquivalent().deprecatedNode());
1437 }
1438
1439 VisiblePosition endOfDocument(const Node* node)
1440 {
1441     if (!node || !node->document().documentElement())
1442         return VisiblePosition();
1443     
1444     // (As above, in startOfDocument.)  The canonicalization can reject valid visible positions
1445     // when descending from the root element, so we construct the visible position directly from a
1446     // valid candidate.
1447     Position lastPosition = createLegacyEditingPosition(node->document().documentElement(), node->document().documentElement()->countChildNodes());
1448     Position lastCandidate = previousCandidate(lastPosition);
1449     if (lastCandidate.isNull())
1450         return VisiblePosition();
1451     return VisiblePosition(lastCandidate);
1452 }
1453
1454 VisiblePosition endOfDocument(const VisiblePosition& c)
1455 {
1456     return endOfDocument(c.deepEquivalent().deprecatedNode());
1457 }
1458
1459 bool inSameDocument(const VisiblePosition& a, const VisiblePosition& b)
1460 {
1461     Position ap = a.deepEquivalent();
1462     Node* an = ap.deprecatedNode();
1463     if (!an)
1464         return false;
1465     Position bp = b.deepEquivalent();
1466     Node* bn = bp.deprecatedNode();
1467     if (an == bn)
1468         return true;
1469
1470     return &an->document() == &bn->document();
1471 }
1472
1473 bool isStartOfDocument(const VisiblePosition& p)
1474 {
1475     return p.isNotNull() && p.previous(CanCrossEditingBoundary).isNull();
1476 }
1477
1478 bool isEndOfDocument(const VisiblePosition& p)
1479 {
1480     return p.isNotNull() && p.next(CanCrossEditingBoundary).isNull();
1481 }
1482
1483 // ---------
1484
1485 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1486 {
1487     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1488     if (!highestRoot)
1489         return { };
1490
1491     return firstPositionInNode(highestRoot);
1492 }
1493
1494 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1495 {
1496     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1497     if (!highestRoot)
1498         return { };
1499
1500     return lastPositionInNode(highestRoot);
1501 }
1502
1503 bool isEndOfEditableOrNonEditableContent(const VisiblePosition& p)
1504 {
1505     return p.isNotNull() && p.next().isNull();
1506 }
1507
1508 VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction, bool* reachedBoundary)
1509 {
1510     return direction == LTR ? logicalStartOfLine(c, reachedBoundary) : logicalEndOfLine(c, reachedBoundary);
1511 }
1512
1513 VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction, bool* reachedBoundary)
1514 {
1515     return direction == LTR ? logicalEndOfLine(c, reachedBoundary) : logicalStartOfLine(c, reachedBoundary);
1516 }
1517
1518 static bool directionIsDownstream(SelectionDirection direction)
1519 {
1520     if (direction == DirectionBackward)
1521         return false;
1522     else if (direction == DirectionForward)
1523         return true;
1524
1525     // FIXME: this code doesn't take into account the original direction of the element.
1526     // I'm not fixing this now because I'm afraid there is some code in UIKit relying on
1527     // this wrong behavior.
1528     return direction == DirectionRight;
1529 }
1530
1531 bool atBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1532 {
1533     if (granularity == CharacterGranularity)
1534         return true;
1535
1536     VisiblePosition boundary;
1537
1538     bool useDownstream = directionIsDownstream(direction);
1539
1540     switch (granularity) {
1541     case WordGranularity:
1542         // visible_units claims erroneously that the start and the end
1543         // of a paragraph are the end and start of a word, respectively.
1544         if ((useDownstream && isStartOfParagraph(vp)) || (!useDownstream && isEndOfParagraph(vp)))
1545             return false;
1546
1547         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1548         boundary = useDownstream ? endOfWord(vp, LeftWordIfOnBoundary) : startOfWord(vp, RightWordIfOnBoundary);
1549         break;
1550
1551     case SentenceGranularity:
1552         boundary = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1553         break;
1554
1555     case LineGranularity:
1556         // Affinity has to be set to get right boundary of the line.
1557         boundary = vp;
1558         boundary.setAffinity(useDownstream ? VP_UPSTREAM_IF_POSSIBLE : DOWNSTREAM);
1559         boundary = useDownstream ? endOfLine(boundary) : startOfLine(boundary);
1560         break;
1561
1562     case ParagraphGranularity:
1563         boundary = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1564         break;
1565
1566     case DocumentGranularity:
1567         boundary = useDownstream ? endOfDocument(vp) : startOfDocument(vp);
1568         break;
1569
1570     default:
1571         ASSERT_NOT_REACHED();
1572         break;
1573     }
1574
1575     return vp == boundary;
1576 }
1577
1578 bool withinTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1579 {
1580     if (granularity == CharacterGranularity || granularity == DocumentGranularity)
1581         return true;
1582
1583     bool useDownstream = directionIsDownstream(direction);
1584
1585     VisiblePosition prevBoundary;
1586     VisiblePosition nextBoundary;
1587     
1588     switch (granularity) {
1589     case WordGranularity:
1590         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1591         prevBoundary = startOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1592         nextBoundary = endOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1593     
1594         // Workaround for <rdar://problem/7259611> Word boundary code on iPhone gives different results than desktop
1595         if (endOfWord(prevBoundary, RightWordIfOnBoundary) != nextBoundary)
1596             return false;
1597
1598         break;
1599
1600     case SentenceGranularity:
1601         prevBoundary = startOfSentence(vp);
1602         nextBoundary = endOfSentence(vp);
1603         break;
1604
1605     case LineGranularity:
1606         prevBoundary = startOfLine(vp);
1607         nextBoundary = endOfLine(vp);
1608
1609         if (prevBoundary == nextBoundary) {
1610             nextBoundary = nextLinePosition(nextBoundary, 0);
1611             nextBoundary.setAffinity(UPSTREAM);
1612             if (!inSameLine(prevBoundary, nextBoundary))
1613                 nextBoundary = vp.next();
1614         }
1615         break;
1616
1617     case ParagraphGranularity:
1618         prevBoundary = startOfParagraph(vp);
1619         nextBoundary = endOfParagraph(vp);
1620         break;
1621
1622     default:
1623         ASSERT_NOT_REACHED();
1624         break;
1625     }
1626
1627     if (prevBoundary == nextBoundary)
1628         return false;
1629
1630     if (vp == prevBoundary)
1631         return useDownstream;
1632
1633     if (vp == nextBoundary)
1634         return !useDownstream;
1635
1636     return (prevBoundary < vp && vp < nextBoundary);
1637 }
1638
1639 static VisiblePosition nextCharacterBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1640 {
1641     return directionIsDownstream(direction) ? vp.next() : vp.previous();
1642 }
1643
1644 static VisiblePosition nextWordBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1645 {
1646     bool useDownstream = directionIsDownstream(direction);
1647     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, WordGranularity, direction);
1648     VisiblePosition result;
1649     
1650     if (useDownstream) {
1651         if (withinUnitOfGranularity)
1652             result = endOfWord(vp, RightWordIfOnBoundary);
1653         else {
1654             VisiblePosition start = startOfWord(vp, RightWordIfOnBoundary);
1655             if (start > vp && start != endOfWord(start))
1656                 result = start;
1657             else {
1658                 // Do same thing as backwards traveling below.
1659                 start = vp;
1660                 while (true) {
1661                     result = startOfWord(nextWordPosition(start), RightWordIfOnBoundary);
1662
1663                     if (result == start)
1664                         break;
1665
1666                     // We failed to find a word boundary.
1667                     if (result.isNull() || result < start)
1668                         return VisiblePosition();
1669
1670                     // We consider successs also the case where start is before element and result is after.
1671                     // This covers moving past images like words.
1672                     if (result != endOfWord(result)
1673                         || (result.deepEquivalent().anchorNode() == start.deepEquivalent().anchorNode()
1674                             && result.deepEquivalent().anchorType() == Position::PositionIsAfterAnchor
1675                             && start.deepEquivalent().anchorType() == Position::PositionIsBeforeAnchor))
1676                         break;
1677
1678                     start = result;
1679                 }
1680             }
1681         }
1682     } else {
1683         if (withinUnitOfGranularity)
1684             result = startOfWord(vp, LeftWordIfOnBoundary);
1685         else {
1686             // This is complicated because:
1687             //   When given "Blah blah.|", endOfWord is "Blah blah|.", and previousWordPosition is "Blah| blah."
1688             //   When given "Blah blah. |", endOfWord is "Blah blah.| ", and previousWordPosition is "Blah |blah. ".
1689             VisiblePosition end = endOfWord(vp, LeftWordIfOnBoundary);
1690             if (end < vp && end != startOfWord(end))
1691                 result = end;
1692             else {
1693                 end = vp;
1694                 while (true) {
1695                     result = endOfWord(previousWordPosition(end), RightWordIfOnBoundary);
1696
1697                     if (result == end)
1698                         break;
1699
1700                     if (result.isNull() || result > end)
1701                         return VisiblePosition();
1702
1703                     if (result != startOfWord(result))
1704                         break;
1705
1706                     end = result;
1707                 }
1708             }
1709         }
1710     }
1711     
1712     if (result == vp)
1713         return VisiblePosition();
1714     
1715     return result;
1716 }
1717
1718 static VisiblePosition nextSentenceBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1719 {
1720     bool useDownstream = directionIsDownstream(direction);
1721     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, SentenceGranularity, direction);
1722     VisiblePosition result;
1723
1724     if (withinUnitOfGranularity)
1725         result = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1726     else {
1727         result = useDownstream ? nextSentencePosition(vp) : previousSentencePosition(vp);
1728         if (result.isNull() || result == vp)
1729             return VisiblePosition();
1730
1731         result = useDownstream ? startOfSentence(vp) : endOfSentence(vp);
1732     }
1733
1734     if (result == vp)
1735         return VisiblePosition();
1736
1737     ASSERT(useDownstream ? (result > vp) : (result < vp));
1738
1739     return result;
1740 }
1741
1742 static VisiblePosition nextLineBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1743 {
1744     bool useDownstream = directionIsDownstream(direction);
1745     VisiblePosition result = vp;
1746
1747     if (useDownstream) {
1748         result.setAffinity(DOWNSTREAM);
1749         result = isEndOfLine(result) ? startOfLine(nextLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : endOfLine(result);
1750     } else {
1751         result.setAffinity(VP_UPSTREAM_IF_POSSIBLE);
1752         result = isStartOfLine(result) ? endOfLine(previousLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : startOfLine(result);
1753     }
1754
1755     return result;
1756 }
1757
1758 static VisiblePosition nextParagraphBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1759 {
1760     bool useDownstream = directionIsDownstream(direction);
1761     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, ParagraphGranularity, direction);
1762     VisiblePosition result;
1763
1764     if (!withinUnitOfGranularity)
1765         result =  useDownstream ? startOfParagraph(nextParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation())) : endOfParagraph(previousParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation()));
1766     else
1767         result = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1768
1769     return result;
1770 }
1771
1772 static VisiblePosition nextDocumentBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1773 {
1774     return directionIsDownstream(direction) ? endOfDocument(vp) : startOfDocument(vp);
1775 }
1776
1777 VisiblePosition positionOfNextBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1778 {
1779     switch (granularity) {
1780     case CharacterGranularity:
1781         return nextCharacterBoundaryInDirection(vp, direction);
1782     case WordGranularity:
1783         return nextWordBoundaryInDirection(vp, direction);
1784     case SentenceGranularity:
1785         return nextSentenceBoundaryInDirection(vp, direction);
1786     case LineGranularity:
1787         return nextLineBoundaryInDirection(vp, direction);
1788     case ParagraphGranularity:
1789         return nextParagraphBoundaryInDirection(vp, direction);
1790     case DocumentGranularity:
1791         return nextDocumentBoundaryInDirection(vp, direction);
1792     default:
1793         ASSERT_NOT_REACHED();
1794         return VisiblePosition();
1795     }
1796 }
1797
1798 RefPtr<Range> enclosingTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1799 {
1800     // This is particularly inefficient.  We could easily obtain the answer with the boundaries computed below.
1801     if (!withinTextUnitOfGranularity(vp, granularity, direction))
1802         return nullptr;
1803
1804     VisiblePosition prevBoundary;
1805     VisiblePosition nextBoundary;
1806     bool useDownstream = directionIsDownstream(direction);
1807
1808     switch (granularity) {
1809         case CharacterGranularity:
1810             prevBoundary = vp;
1811             nextBoundary = prevBoundary.next();
1812             break;
1813
1814         case WordGranularity:
1815             // NB: "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1816             if (useDownstream) {
1817                 prevBoundary = startOfWord(vp, RightWordIfOnBoundary);
1818                 nextBoundary = endOfWord(vp, RightWordIfOnBoundary);
1819             } else {
1820                 prevBoundary = startOfWord(vp, LeftWordIfOnBoundary);
1821                 nextBoundary = endOfWord(vp, LeftWordIfOnBoundary);
1822             }
1823             break;
1824
1825         case SentenceGranularity:
1826             prevBoundary = startOfSentence(vp);
1827             nextBoundary = endOfSentence(vp);
1828             break;
1829
1830         case LineGranularity:
1831             prevBoundary = startOfLine(vp);
1832             nextBoundary = endOfLine(vp);
1833
1834             if (prevBoundary == nextBoundary) {
1835                 nextBoundary = nextLinePosition(nextBoundary, 0);
1836                 nextBoundary.setAffinity(UPSTREAM);
1837                 if (!inSameLine(prevBoundary, nextBoundary))
1838                     nextBoundary = vp.next();
1839             }
1840             break;
1841
1842         case ParagraphGranularity:
1843             prevBoundary = startOfParagraph(vp);
1844             nextBoundary = endOfParagraph(vp);
1845             break;
1846
1847         case DocumentGranularity:
1848             prevBoundary = startOfDocument(vp);
1849             nextBoundary = endOfDocument(vp);
1850             break;
1851
1852         default:
1853             ASSERT_NOT_REACHED();
1854             return nullptr;
1855     }
1856
1857     if (prevBoundary.isNull() || nextBoundary.isNull())
1858         return nullptr;
1859
1860     if (vp < prevBoundary || vp > nextBoundary)
1861         return nullptr;
1862
1863     return Range::create(prevBoundary.deepEquivalent().deprecatedNode()->document(), prevBoundary, nextBoundary);
1864 }
1865
1866 int distanceBetweenPositions(const VisiblePosition& vp, const VisiblePosition& other)
1867 {
1868     if (vp.isNull() || other.isNull())
1869         return 0;
1870
1871     bool thisIsStart = (vp < other);
1872
1873     // Start must come first in the Range constructor.
1874     RefPtr<Range> range = Range::create(vp.deepEquivalent().deprecatedNode()->document(),
1875                                         (thisIsStart ? vp : other),
1876                                         (thisIsStart ? other : vp));
1877     int distance = TextIterator::rangeLength(range.get());
1878
1879     return (thisIsStart ? -distance : distance);
1880 }
1881
1882 void charactersAroundPosition(const VisiblePosition& position, UChar32& oneAfter, UChar32& oneBefore, UChar32& twoBefore)
1883 {
1884     const int maxCharacters = 3;
1885     Vector<UChar32> characters(maxCharacters);
1886
1887     if (position.isNull() || isStartOfDocument(position))
1888         return;
1889
1890     VisiblePosition startPosition = position;
1891     VisiblePosition endPosition = position;
1892
1893     VisiblePosition nextPosition = nextCharacterBoundaryInDirection(position, DirectionForward);
1894     if (nextPosition.isNotNull())
1895         endPosition = nextPosition;
1896
1897     VisiblePosition previousPosition = nextCharacterBoundaryInDirection(position, DirectionBackward);
1898     if (previousPosition.isNotNull()) {
1899         startPosition = previousPosition;
1900         previousPosition = nextCharacterBoundaryInDirection(previousPosition, DirectionBackward);
1901         if (previousPosition.isNotNull())
1902             startPosition = previousPosition;
1903     }
1904
1905     if (startPosition != endPosition) {
1906         String characterString = plainText(Range::create(position.deepEquivalent().anchorNode()->document(), startPosition, endPosition).ptr()).replace(noBreakSpace, ' ');
1907         for (int i = characterString.length() - 1, index = 0; i >= 0 && index < maxCharacters; --i) {
1908             if (!index && nextPosition.isNull())
1909                 index++;
1910             characters[index++] = characterString[i];
1911         }
1912     }
1913     oneAfter = characters[0];
1914     oneBefore = characters[1];
1915     twoBefore = characters[2];
1916 }
1917
1918 RefPtr<Range> wordRangeFromPosition(const VisiblePosition& position)
1919 {
1920     // The selection could be in a non visible element and we don't have a VisiblePosition.
1921     if (position.isNull())
1922         return nullptr;
1923
1924     RefPtr<Range> range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionBackward);
1925
1926     if (!range) {
1927         // We could be at the start of a word, try forward.
1928         range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
1929     }
1930     if (range)
1931         return range;
1932
1933     VisiblePosition currentPosition = position;
1934     do {
1935         currentPosition = positionOfNextBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward);
1936     } while (currentPosition.isNotNull() && !atBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward));
1937
1938     // If the position is an empty paragraph and at the end of the document
1939     // the word iterator could not pass the paragraph boundary, therefore iterating to
1940     // the previous line is required.
1941     if (currentPosition.isNull() && isEndOfDocument(position)) {
1942         VisiblePosition previousLinePosition = positionOfNextBoundaryOfGranularity(position, LineGranularity, DirectionBackward);
1943         if (previousLinePosition.isNotNull()) {
1944             currentPosition = positionOfNextBoundaryOfGranularity(previousLinePosition, WordGranularity, DirectionBackward);
1945             if (currentPosition.isNull())
1946                 currentPosition = previousLinePosition;
1947         }
1948     }
1949
1950     if (currentPosition.isNull())
1951         currentPosition = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
1952
1953     if (currentPosition.isNotNull()) {
1954         range = Range::create(position.deepEquivalent().deprecatedNode()->document(), currentPosition, position);
1955         ASSERT(range);
1956     }
1957     return range;
1958 }
1959
1960 VisiblePosition closestWordBoundaryForPosition(const VisiblePosition& position)
1961 {
1962     VisiblePosition result;
1963
1964     // move the the position at the end of the word
1965     if (atBoundaryOfGranularity(position, LineGranularity, DirectionForward)) {
1966         // Don't cross line boundaries.
1967         result = position;
1968     } else if (withinTextUnitOfGranularity(position, WordGranularity, DirectionForward)) {
1969         // The position lies within a word.
1970         RefPtr<Range> wordRange = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
1971
1972         result = wordRange->startPosition();
1973         if (distanceBetweenPositions(position, result) > 1)
1974             result = wordRange->endPosition();
1975     } else if (atBoundaryOfGranularity(position, WordGranularity, DirectionBackward)) {
1976         // The position is at the end of a word.
1977         result = position;
1978     } else {
1979         // The position is not within a word.
1980         // Go to the next boundary.
1981         result = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
1982
1983         // If there is no such boundary we go to the end of the element.
1984         if (result.isNull())
1985             result = endOfEditableContent(position);
1986     }
1987     return result;
1988 }
1989
1990 RefPtr<Range> rangeExpandedByCharactersInDirectionAtWordBoundary(const VisiblePosition& position, int numberOfCharactersToExpand, SelectionDirection direction)
1991 {
1992     Position start = position.deepEquivalent();
1993     Position end = position.deepEquivalent();
1994     for (int i = 0; i < numberOfCharactersToExpand; ++i) {
1995         if (direction == DirectionBackward)
1996             start = start.previous(Character);
1997         else
1998             end = end.next(Character);
1999     }
2000     
2001     if (direction == DirectionBackward && !atBoundaryOfGranularity(start, WordGranularity, DirectionBackward))
2002         start = startOfWord(start).deepEquivalent();
2003     if (direction == DirectionForward && !atBoundaryOfGranularity(end, WordGranularity, DirectionForward))
2004         end = endOfWord(end).deepEquivalent();
2005
2006     return makeRange(start, end);
2007 }    
2008
2009 RefPtr<Range> rangeExpandedAroundPositionByCharacters(const VisiblePosition& position, int numberOfCharactersToExpand)
2010 {
2011     Position start = position.deepEquivalent();
2012     Position end = position.deepEquivalent();
2013     for (int i = 0; i < numberOfCharactersToExpand; ++i) {
2014         start = start.previous(Character);
2015         end = end.next(Character);
2016     }
2017     
2018     return makeRange(start, end);
2019 }    
2020
2021 }