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