Use a 1-byte enum class for TextDirection
[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     std::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 VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
1382 {
1383     VisiblePosition pos = p;
1384     do {
1385         VisiblePosition n = previousLinePosition(pos, x);
1386         if (n.isNull() || n == pos)
1387             break;
1388         pos = n;
1389     } while (inSameParagraph(p, pos));
1390     return pos;
1391 }
1392
1393 VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
1394 {
1395     VisiblePosition pos = p;
1396     do {
1397         VisiblePosition n = nextLinePosition(pos, x);
1398         if (n.isNull() || n == pos)
1399             break;
1400         pos = n;
1401     } while (inSameParagraph(p, pos));
1402     return pos;
1403 }
1404
1405 // ---------
1406
1407 VisiblePosition startOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1408 {
1409     Position position = visiblePosition.deepEquivalent();
1410     Node* startBlock;
1411     if (!position.containerNode() || !(startBlock = enclosingBlock(position.containerNode(), rule)))
1412         return VisiblePosition();
1413     return firstPositionInNode(startBlock);
1414 }
1415
1416 VisiblePosition endOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1417 {
1418     Position position = visiblePosition.deepEquivalent();
1419     Node* endBlock;
1420     if (!position.containerNode() || !(endBlock = enclosingBlock(position.containerNode(), rule)))
1421         return VisiblePosition();
1422     return lastPositionInNode(endBlock);
1423 }
1424
1425 bool inSameBlock(const VisiblePosition& a, const VisiblePosition& b)
1426 {
1427     return !a.isNull() && enclosingBlock(a.deepEquivalent().containerNode()) == enclosingBlock(b.deepEquivalent().containerNode());
1428 }
1429
1430 bool isStartOfBlock(const VisiblePosition& pos)
1431 {
1432     return pos.isNotNull() && pos == startOfBlock(pos, CanCrossEditingBoundary);
1433 }
1434
1435 bool isEndOfBlock(const VisiblePosition& pos)
1436 {
1437     return pos.isNotNull() && pos == endOfBlock(pos, CanCrossEditingBoundary);
1438 }
1439
1440 // ---------
1441
1442 VisiblePosition startOfDocument(const Node* node)
1443 {
1444     if (!node || !node->document().documentElement())
1445         return VisiblePosition();
1446     
1447     // The canonicalization of the position at (documentElement, 0) can turn the visible
1448     // position to null, even when there's a valid candidate to be had, because the root HTML element
1449     // is not content editable.  So we construct directly from the valid candidate.
1450     Position firstCandidate = nextCandidate(createLegacyEditingPosition(node->document().documentElement(), 0));
1451     if (firstCandidate.isNull())
1452         return VisiblePosition();
1453     return VisiblePosition(firstCandidate);
1454 }
1455
1456 VisiblePosition startOfDocument(const VisiblePosition& c)
1457 {
1458     return startOfDocument(c.deepEquivalent().deprecatedNode());
1459 }
1460
1461 VisiblePosition endOfDocument(const Node* node)
1462 {
1463     if (!node || !node->document().documentElement())
1464         return VisiblePosition();
1465     
1466     // (As above, in startOfDocument.)  The canonicalization can reject valid visible positions
1467     // when descending from the root element, so we construct the visible position directly from a
1468     // valid candidate.
1469     Position lastPosition = createLegacyEditingPosition(node->document().documentElement(), node->document().documentElement()->countChildNodes());
1470     Position lastCandidate = previousCandidate(lastPosition);
1471     if (lastCandidate.isNull())
1472         return VisiblePosition();
1473     return VisiblePosition(lastCandidate);
1474 }
1475
1476 VisiblePosition endOfDocument(const VisiblePosition& c)
1477 {
1478     return endOfDocument(c.deepEquivalent().deprecatedNode());
1479 }
1480
1481 bool inSameDocument(const VisiblePosition& a, const VisiblePosition& b)
1482 {
1483     Position ap = a.deepEquivalent();
1484     Node* an = ap.deprecatedNode();
1485     if (!an)
1486         return false;
1487     Position bp = b.deepEquivalent();
1488     Node* bn = bp.deprecatedNode();
1489     if (an == bn)
1490         return true;
1491
1492     return &an->document() == &bn->document();
1493 }
1494
1495 bool isStartOfDocument(const VisiblePosition& p)
1496 {
1497     return p.isNotNull() && p.previous(CanCrossEditingBoundary).isNull();
1498 }
1499
1500 bool isEndOfDocument(const VisiblePosition& p)
1501 {
1502     return p.isNotNull() && p.next(CanCrossEditingBoundary).isNull();
1503 }
1504
1505 // ---------
1506
1507 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1508 {
1509     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1510     if (!highestRoot)
1511         return { };
1512
1513     return firstPositionInNode(highestRoot);
1514 }
1515
1516 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1517 {
1518     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1519     if (!highestRoot)
1520         return { };
1521
1522     return lastPositionInNode(highestRoot);
1523 }
1524
1525 bool isEndOfEditableOrNonEditableContent(const VisiblePosition& p)
1526 {
1527     return p.isNotNull() && p.next().isNull();
1528 }
1529
1530 VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction, bool* reachedBoundary)
1531 {
1532     return direction == TextDirection::LTR ? logicalStartOfLine(c, reachedBoundary) : logicalEndOfLine(c, reachedBoundary);
1533 }
1534
1535 VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction, bool* reachedBoundary)
1536 {
1537     return direction == TextDirection::LTR ? logicalEndOfLine(c, reachedBoundary) : logicalStartOfLine(c, reachedBoundary);
1538 }
1539
1540 static bool directionIsDownstream(SelectionDirection direction)
1541 {
1542     if (direction == DirectionBackward)
1543         return false;
1544     else if (direction == DirectionForward)
1545         return true;
1546
1547     // FIXME: this code doesn't take into account the original direction of the element.
1548     // I'm not fixing this now because I'm afraid there is some code in UIKit relying on
1549     // this wrong behavior.
1550     return direction == DirectionRight;
1551 }
1552
1553 bool atBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1554 {
1555     if (granularity == CharacterGranularity)
1556         return true;
1557
1558     VisiblePosition boundary;
1559
1560     bool useDownstream = directionIsDownstream(direction);
1561
1562     switch (granularity) {
1563     case WordGranularity:
1564         // visible_units claims erroneously that the start and the end
1565         // of a paragraph are the end and start of a word, respectively.
1566         if ((useDownstream && isStartOfParagraph(vp)) || (!useDownstream && isEndOfParagraph(vp)))
1567             return false;
1568
1569         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1570         boundary = useDownstream ? endOfWord(vp, LeftWordIfOnBoundary) : startOfWord(vp, RightWordIfOnBoundary);
1571         break;
1572
1573     case SentenceGranularity:
1574         boundary = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1575         break;
1576
1577     case LineGranularity:
1578         // Affinity has to be set to get right boundary of the line.
1579         boundary = vp;
1580         boundary.setAffinity(useDownstream ? VP_UPSTREAM_IF_POSSIBLE : DOWNSTREAM);
1581         boundary = useDownstream ? endOfLine(boundary) : startOfLine(boundary);
1582         break;
1583
1584     case ParagraphGranularity:
1585         boundary = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1586         break;
1587
1588     case DocumentGranularity:
1589         boundary = useDownstream ? endOfDocument(vp) : startOfDocument(vp);
1590         break;
1591
1592     default:
1593         ASSERT_NOT_REACHED();
1594         break;
1595     }
1596
1597     return vp == boundary;
1598 }
1599
1600 bool withinTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1601 {
1602     if (granularity == CharacterGranularity || granularity == DocumentGranularity)
1603         return true;
1604
1605     bool useDownstream = directionIsDownstream(direction);
1606
1607     VisiblePosition prevBoundary;
1608     VisiblePosition nextBoundary;
1609     
1610     switch (granularity) {
1611     case WordGranularity:
1612         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1613         prevBoundary = startOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1614         nextBoundary = endOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1615     
1616         // Workaround for <rdar://problem/7259611> Word boundary code on iPhone gives different results than desktop
1617         if (endOfWord(prevBoundary, RightWordIfOnBoundary) != nextBoundary)
1618             return false;
1619
1620         break;
1621
1622     case SentenceGranularity:
1623         prevBoundary = startOfSentence(vp);
1624         nextBoundary = endOfSentence(vp);
1625         break;
1626
1627     case LineGranularity:
1628         prevBoundary = startOfLine(vp);
1629         nextBoundary = endOfLine(vp);
1630
1631         if (prevBoundary == nextBoundary) {
1632             nextBoundary = nextLinePosition(nextBoundary, 0);
1633             nextBoundary.setAffinity(UPSTREAM);
1634             if (!inSameLine(prevBoundary, nextBoundary))
1635                 nextBoundary = vp.next();
1636         }
1637         break;
1638
1639     case ParagraphGranularity:
1640         prevBoundary = startOfParagraph(vp);
1641         nextBoundary = endOfParagraph(vp);
1642         break;
1643
1644     default:
1645         ASSERT_NOT_REACHED();
1646         break;
1647     }
1648
1649     if (prevBoundary == nextBoundary)
1650         return false;
1651
1652     if (vp == prevBoundary)
1653         return useDownstream;
1654
1655     if (vp == nextBoundary)
1656         return !useDownstream;
1657
1658     return (prevBoundary < vp && vp < nextBoundary);
1659 }
1660
1661 static VisiblePosition nextCharacterBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction, EditingBoundaryCrossingRule rule)
1662 {
1663     return directionIsDownstream(direction) ? vp.next(rule) : vp.previous(rule);
1664 }
1665
1666 static VisiblePosition nextWordBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1667 {
1668     bool useDownstream = directionIsDownstream(direction);
1669     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, WordGranularity, direction);
1670     VisiblePosition result;
1671     
1672     if (useDownstream) {
1673         if (withinUnitOfGranularity)
1674             result = endOfWord(vp, RightWordIfOnBoundary);
1675         else {
1676             VisiblePosition start = startOfWord(vp, RightWordIfOnBoundary);
1677             if (start > vp && start != endOfWord(start))
1678                 result = start;
1679             else {
1680                 // Do same thing as backwards traveling below.
1681                 start = vp;
1682                 while (true) {
1683                     result = startOfWord(nextWordPosition(start), RightWordIfOnBoundary);
1684
1685                     if (result == start)
1686                         break;
1687
1688                     // We failed to find a word boundary.
1689                     if (result.isNull() || result < start)
1690                         return VisiblePosition();
1691
1692                     // We consider successs also the case where start is before element and result is after.
1693                     // This covers moving past images like words.
1694                     if (result != endOfWord(result)
1695                         || (result.deepEquivalent().anchorNode() == start.deepEquivalent().anchorNode()
1696                             && result.deepEquivalent().anchorType() == Position::PositionIsAfterAnchor
1697                             && start.deepEquivalent().anchorType() == Position::PositionIsBeforeAnchor))
1698                         break;
1699
1700                     start = result;
1701                 }
1702             }
1703         }
1704     } else {
1705         if (withinUnitOfGranularity)
1706             result = startOfWord(vp, LeftWordIfOnBoundary);
1707         else {
1708             // This is complicated because:
1709             //   When given "Blah blah.|", endOfWord is "Blah blah|.", and previousWordPosition is "Blah| blah."
1710             //   When given "Blah blah. |", endOfWord is "Blah blah.| ", and previousWordPosition is "Blah |blah. ".
1711             VisiblePosition end = endOfWord(vp, LeftWordIfOnBoundary);
1712             if (end < vp && end != startOfWord(end))
1713                 result = end;
1714             else {
1715                 end = vp;
1716                 while (true) {
1717                     result = endOfWord(previousWordPosition(end), RightWordIfOnBoundary);
1718
1719                     if (result == end)
1720                         break;
1721
1722                     if (result.isNull() || result > end)
1723                         return VisiblePosition();
1724
1725                     if (result != startOfWord(result))
1726                         break;
1727
1728                     end = result;
1729                 }
1730             }
1731         }
1732     }
1733     
1734     if (result == vp)
1735         return VisiblePosition();
1736     
1737     return result;
1738 }
1739
1740 static VisiblePosition nextSentenceBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1741 {
1742     bool useDownstream = directionIsDownstream(direction);
1743     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, SentenceGranularity, direction);
1744     VisiblePosition result;
1745
1746     if (withinUnitOfGranularity)
1747         result = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1748     else {
1749         result = useDownstream ? nextSentencePosition(vp) : previousSentencePosition(vp);
1750         if (result.isNull() || result == vp)
1751             return VisiblePosition();
1752
1753         result = useDownstream ? startOfSentence(vp) : endOfSentence(vp);
1754     }
1755
1756     if (result == vp)
1757         return VisiblePosition();
1758
1759     ASSERT(useDownstream ? (result > vp) : (result < vp));
1760
1761     return result;
1762 }
1763
1764 static VisiblePosition nextLineBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1765 {
1766     bool useDownstream = directionIsDownstream(direction);
1767     VisiblePosition result = vp;
1768
1769     if (useDownstream) {
1770         result.setAffinity(DOWNSTREAM);
1771         result = isEndOfLine(result) ? startOfLine(nextLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : endOfLine(result);
1772     } else {
1773         result.setAffinity(VP_UPSTREAM_IF_POSSIBLE);
1774         result = isStartOfLine(result) ? endOfLine(previousLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : startOfLine(result);
1775     }
1776
1777     return result;
1778 }
1779
1780 static VisiblePosition nextParagraphBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1781 {
1782     bool useDownstream = directionIsDownstream(direction);
1783     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, ParagraphGranularity, direction);
1784     VisiblePosition result;
1785
1786     if (!withinUnitOfGranularity)
1787         result =  useDownstream ? startOfParagraph(nextParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation())) : endOfParagraph(previousParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation()));
1788     else
1789         result = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1790
1791     return result;
1792 }
1793
1794 static VisiblePosition nextDocumentBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1795 {
1796     return directionIsDownstream(direction) ? endOfDocument(vp) : startOfDocument(vp);
1797 }
1798
1799 VisiblePosition positionOfNextBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1800 {
1801     switch (granularity) {
1802     case CharacterGranularity:
1803         return nextCharacterBoundaryInDirection(vp, direction, CanCrossEditingBoundary);
1804     case WordGranularity:
1805         return nextWordBoundaryInDirection(vp, direction);
1806     case SentenceGranularity:
1807         return nextSentenceBoundaryInDirection(vp, direction);
1808     case LineGranularity:
1809         return nextLineBoundaryInDirection(vp, direction);
1810     case ParagraphGranularity:
1811         return nextParagraphBoundaryInDirection(vp, direction);
1812     case DocumentGranularity:
1813         return nextDocumentBoundaryInDirection(vp, direction);
1814     default:
1815         ASSERT_NOT_REACHED();
1816         return VisiblePosition();
1817     }
1818 }
1819
1820 RefPtr<Range> enclosingTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1821 {
1822     // This is particularly inefficient.  We could easily obtain the answer with the boundaries computed below.
1823     if (!withinTextUnitOfGranularity(vp, granularity, direction))
1824         return nullptr;
1825
1826     VisiblePosition prevBoundary;
1827     VisiblePosition nextBoundary;
1828     bool useDownstream = directionIsDownstream(direction);
1829
1830     switch (granularity) {
1831         case CharacterGranularity:
1832             prevBoundary = vp;
1833             nextBoundary = prevBoundary.next();
1834             break;
1835
1836         case WordGranularity:
1837             // NB: "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1838             if (useDownstream) {
1839                 prevBoundary = startOfWord(vp, RightWordIfOnBoundary);
1840                 nextBoundary = endOfWord(vp, RightWordIfOnBoundary);
1841             } else {
1842                 prevBoundary = startOfWord(vp, LeftWordIfOnBoundary);
1843                 nextBoundary = endOfWord(vp, LeftWordIfOnBoundary);
1844             }
1845             break;
1846
1847         case SentenceGranularity:
1848             prevBoundary = startOfSentence(vp);
1849             nextBoundary = endOfSentence(vp);
1850             break;
1851
1852         case LineGranularity:
1853             prevBoundary = startOfLine(vp);
1854             nextBoundary = endOfLine(vp);
1855
1856             if (prevBoundary == nextBoundary) {
1857                 nextBoundary = nextLinePosition(nextBoundary, 0);
1858                 nextBoundary.setAffinity(UPSTREAM);
1859                 if (!inSameLine(prevBoundary, nextBoundary))
1860                     nextBoundary = vp.next();
1861             }
1862             break;
1863
1864         case ParagraphGranularity:
1865             prevBoundary = startOfParagraph(vp);
1866             nextBoundary = endOfParagraph(vp);
1867             break;
1868
1869         case DocumentGranularity:
1870             prevBoundary = startOfDocument(vp);
1871             nextBoundary = endOfDocument(vp);
1872             break;
1873
1874         default:
1875             ASSERT_NOT_REACHED();
1876             return nullptr;
1877     }
1878
1879     if (prevBoundary.isNull() || nextBoundary.isNull())
1880         return nullptr;
1881
1882     if (vp < prevBoundary || vp > nextBoundary)
1883         return nullptr;
1884
1885     return Range::create(prevBoundary.deepEquivalent().deprecatedNode()->document(), prevBoundary, nextBoundary);
1886 }
1887
1888 int distanceBetweenPositions(const VisiblePosition& vp, const VisiblePosition& other)
1889 {
1890     if (vp.isNull() || other.isNull())
1891         return 0;
1892
1893     bool thisIsStart = (vp < other);
1894
1895     // Start must come first in the Range constructor.
1896     RefPtr<Range> range = Range::create(vp.deepEquivalent().deprecatedNode()->document(),
1897                                         (thisIsStart ? vp : other),
1898                                         (thisIsStart ? other : vp));
1899     int distance = TextIterator::rangeLength(range.get());
1900
1901     return (thisIsStart ? -distance : distance);
1902 }
1903
1904 void charactersAroundPosition(const VisiblePosition& position, UChar32& oneAfter, UChar32& oneBefore, UChar32& twoBefore)
1905 {
1906     const int maxCharacters = 3;
1907     UChar32 characters[maxCharacters] = { 0 };
1908
1909     if (position.isNull() || isStartOfDocument(position))
1910         return;
1911
1912     VisiblePosition startPosition = position;
1913     VisiblePosition endPosition = position;
1914
1915     VisiblePosition nextPosition = nextCharacterBoundaryInDirection(position, DirectionForward, CannotCrossEditingBoundary);
1916     if (nextPosition.isNotNull())
1917         endPosition = nextPosition;
1918
1919     VisiblePosition previousPosition = nextCharacterBoundaryInDirection(position, DirectionBackward, CannotCrossEditingBoundary);
1920     if (previousPosition.isNotNull()) {
1921         startPosition = previousPosition;
1922         previousPosition = nextCharacterBoundaryInDirection(previousPosition, DirectionBackward, CannotCrossEditingBoundary);
1923         if (previousPosition.isNotNull())
1924             startPosition = previousPosition;
1925     }
1926
1927     if (startPosition != endPosition) {
1928         String characterString = plainText(Range::create(position.deepEquivalent().anchorNode()->document(), startPosition, endPosition).ptr()).replace(noBreakSpace, ' ');
1929         for (int i = characterString.length() - 1, index = 0; i >= 0 && index < maxCharacters; --i) {
1930             if (!index && nextPosition.isNull())
1931                 index++;
1932             characters[index++] = characterString[i];
1933         }
1934     }
1935     oneAfter = characters[0];
1936     oneBefore = characters[1];
1937     twoBefore = characters[2];
1938 }
1939
1940 RefPtr<Range> wordRangeFromPosition(const VisiblePosition& position)
1941 {
1942     // The selection could be in a non visible element and we don't have a VisiblePosition.
1943     if (position.isNull())
1944         return nullptr;
1945
1946     RefPtr<Range> range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionBackward);
1947
1948     if (!range) {
1949         // We could be at the start of a word, try forward.
1950         range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
1951     }
1952     if (range)
1953         return range;
1954
1955     VisiblePosition currentPosition = position;
1956     do {
1957         currentPosition = positionOfNextBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward);
1958     } while (currentPosition.isNotNull() && !atBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward));
1959
1960     // If the position is an empty paragraph and at the end of the document
1961     // the word iterator could not pass the paragraph boundary, therefore iterating to
1962     // the previous line is required.
1963     if (currentPosition.isNull() && isEndOfDocument(position)) {
1964         VisiblePosition previousLinePosition = positionOfNextBoundaryOfGranularity(position, LineGranularity, DirectionBackward);
1965         if (previousLinePosition.isNotNull()) {
1966             currentPosition = positionOfNextBoundaryOfGranularity(previousLinePosition, WordGranularity, DirectionBackward);
1967             if (currentPosition.isNull())
1968                 currentPosition = previousLinePosition;
1969         }
1970     }
1971
1972     if (currentPosition.isNull())
1973         currentPosition = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
1974
1975     if (currentPosition.isNotNull()) {
1976         range = Range::create(position.deepEquivalent().deprecatedNode()->document(), currentPosition, position);
1977         ASSERT(range);
1978     }
1979     return range;
1980 }
1981
1982 VisiblePosition closestWordBoundaryForPosition(const VisiblePosition& position)
1983 {
1984     VisiblePosition result;
1985
1986     // move the position at the end of the word
1987     if (atBoundaryOfGranularity(position, LineGranularity, DirectionForward)) {
1988         // Don't cross line boundaries.
1989         result = position;
1990     } else if (withinTextUnitOfGranularity(position, WordGranularity, DirectionForward)) {
1991         // The position lies within a word.
1992         RefPtr<Range> wordRange = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
1993
1994         result = wordRange->startPosition();
1995         if (distanceBetweenPositions(position, result) > 1)
1996             result = wordRange->endPosition();
1997     } else if (atBoundaryOfGranularity(position, WordGranularity, DirectionBackward)) {
1998         // The position is at the end of a word.
1999         result = position;
2000     } else {
2001         // The position is not within a word.
2002         // Go to the next boundary.
2003         result = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
2004
2005         // If there is no such boundary we go to the end of the element.
2006         if (result.isNull())
2007             result = endOfEditableContent(position);
2008     }
2009     return result;
2010 }
2011
2012 RefPtr<Range> rangeExpandedByCharactersInDirectionAtWordBoundary(const VisiblePosition& position, int numberOfCharactersToExpand, SelectionDirection direction)
2013 {
2014     Position start = position.deepEquivalent();
2015     Position end = position.deepEquivalent();
2016     for (int i = 0; i < numberOfCharactersToExpand; ++i) {
2017         if (direction == DirectionBackward)
2018             start = start.previous(Character);
2019         else
2020             end = end.next(Character);
2021     }
2022     
2023     if (direction == DirectionBackward && !atBoundaryOfGranularity(start, WordGranularity, DirectionBackward))
2024         start = startOfWord(start).deepEquivalent();
2025     if (direction == DirectionForward && !atBoundaryOfGranularity(end, WordGranularity, DirectionForward))
2026         end = endOfWord(end).deepEquivalent();
2027
2028     return makeRange(start, end);
2029 }    
2030
2031 RefPtr<Range> rangeExpandedAroundPositionByCharacters(const VisiblePosition& position, int numberOfCharactersToExpand)
2032 {
2033     Position start = position.deepEquivalent();
2034     Position end = position.deepEquivalent();
2035     for (int i = 0; i < numberOfCharactersToExpand; ++i) {
2036         start = start.previous(Character);
2037         end = end.next(Character);
2038     }
2039     
2040     return makeRange(start, end);
2041 }    
2042
2043 }