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