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