Remove PLATFORM(IOS) from WebCore/editing (Part 1).
[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 startNode->isTextNode() ? Position(toText(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() && endNode->isTextNode()) {
842         InlineTextBox* endTextBox = toInlineTextBox(endBox);
843         int endOffset = endTextBox->start();
844         if (!endTextBox->isLineBreak())
845             endOffset += endTextBox->len();
846         pos = Position(toText(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 static inline IntPoint absoluteLineDirectionPointToLocalPointInBlock(RootInlineBox& root, int lineDirectionPoint)
923 {
924     RenderBlockFlow& containingBlock = root.blockFlow();
925     FloatPoint absoluteBlockPoint = containingBlock.localToAbsolute(FloatPoint()) - containingBlock.scrolledContentOffset();
926
927     if (containingBlock.isHorizontalWritingMode())
928         return IntPoint(lineDirectionPoint - absoluteBlockPoint.x(), root.blockDirectionPointInLine());
929
930     return IntPoint(root.blockDirectionPointInLine(), lineDirectionPoint - absoluteBlockPoint.y());
931 }
932
933 VisiblePosition previousLinePosition(const VisiblePosition& visiblePosition, int lineDirectionPoint, EditableType editableType)
934 {
935     Position p = visiblePosition.deepEquivalent();
936     Node* node = p.deprecatedNode();
937
938     if (!node)
939         return VisiblePosition();
940     
941     node->document().updateLayoutIgnorePendingStylesheets();
942     
943     RenderObject* renderer = node->renderer();
944     if (!renderer)
945         return VisiblePosition();
946
947     RootInlineBox* root = 0;
948     InlineBox* box;
949     int ignoredCaretOffset;
950     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
951     if (box) {
952         root = box->root().prevRootBox();
953         // We want to skip zero height boxes.
954         // This could happen in case it is a TrailingFloatsRootInlineBox.
955         if (!root || !root->logicalHeight() || !root->firstLeafChild())
956             root = 0;
957     }
958
959     if (!root) {
960         Position position = previousRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
961         if (position.isNotNull()) {
962             RenderedPosition renderedPosition(position);
963             root = renderedPosition.rootBox();
964             if (!root)
965                 return position;
966         }
967     }
968     
969     if (root) {
970         // FIXME: Can be wrong for multi-column layout and with transforms.
971         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(*root, lineDirectionPoint);
972         RenderObject& renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
973         Node* node = renderer.node();
974         if (node && editingIgnoresContent(node))
975             return positionInParentBeforeNode(node);
976         return renderer.positionForPoint(pointInLine, nullptr);
977     }
978     
979     // Could not find a previous line. This means we must already be on the first line.
980     // Move to the start of the content in this block, which effectively moves us
981     // to the start of the line we're on.
982     Element* rootElement = node->hasEditableStyle(editableType) ? node->rootEditableElement(editableType) : node->document().documentElement();
983     if (!rootElement)
984         return VisiblePosition();
985     return VisiblePosition(firstPositionInNode(rootElement), DOWNSTREAM);
986 }
987
988 VisiblePosition nextLinePosition(const VisiblePosition& visiblePosition, int lineDirectionPoint, EditableType editableType)
989 {
990     Position p = visiblePosition.deepEquivalent();
991     Node* node = p.deprecatedNode();
992
993     if (!node)
994         return VisiblePosition();
995     
996     node->document().updateLayoutIgnorePendingStylesheets();
997
998     RenderObject* renderer = node->renderer();
999     if (!renderer)
1000         return VisiblePosition();
1001
1002     RootInlineBox* root = 0;
1003     InlineBox* box;
1004     int ignoredCaretOffset;
1005     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
1006     if (box) {
1007         root = box->root().nextRootBox();
1008         // We want to skip zero height boxes.
1009         // This could happen in case it is a TrailingFloatsRootInlineBox.
1010         if (!root || !root->logicalHeight() || !root->firstLeafChild())
1011             root = 0;
1012     }
1013
1014     if (!root) {
1015         // FIXME: We need do the same in previousLinePosition.
1016         Node* child = node->childNode(p.deprecatedEditingOffset());
1017         node = child ? child : node->lastDescendant();
1018         Position position = nextRootInlineBoxCandidatePosition(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 next line. This means we must already be on the last line.
1038     // Move to the end of the content in this block, which effectively moves us
1039     // to the end of the line we're on.
1040     Element* rootElement = node->hasEditableStyle(editableType) ? node->rootEditableElement(editableType) : node->document().documentElement();
1041     if (!rootElement)
1042         return VisiblePosition();
1043     return VisiblePosition(lastPositionInNode(rootElement), DOWNSTREAM);
1044 }
1045
1046 // ---------
1047
1048 static unsigned startSentenceBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1049 {
1050     // FIXME: The following function can return -1; we don't handle that.
1051     return textBreakPreceding(sentenceBreakIterator(text), text.length());
1052 }
1053
1054 VisiblePosition startOfSentence(const VisiblePosition& position)
1055 {
1056     return previousBoundary(position, startSentenceBoundary);
1057 }
1058
1059 static unsigned endSentenceBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1060 {
1061     return textBreakNext(sentenceBreakIterator(text));
1062 }
1063
1064 VisiblePosition endOfSentence(const VisiblePosition& position)
1065 {
1066     // FIXME: This includes the space after the punctuation that marks the end of the sentence.
1067     return nextBoundary(position, endSentenceBoundary);
1068 }
1069
1070 static unsigned previousSentencePositionBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1071 {
1072     // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
1073     // FIXME: The following function can return -1; we don't handle that.
1074     return textBreakPreceding(sentenceBreakIterator(text), text.length());
1075 }
1076
1077 VisiblePosition previousSentencePosition(const VisiblePosition& position)
1078 {
1079     return position.honorEditingBoundaryAtOrBefore(previousBoundary(position, previousSentencePositionBoundary));
1080 }
1081
1082 static unsigned nextSentencePositionBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1083 {
1084     // FIXME: This is identical to endSentenceBoundary.
1085     // That isn't right. This function needs to move to the equivalent position in the following sentence.
1086     return textBreakFollowing(sentenceBreakIterator(text), 0);
1087 }
1088
1089 VisiblePosition nextSentencePosition(const VisiblePosition& position)
1090 {
1091     return position.honorEditingBoundaryAtOrAfter(nextBoundary(position, nextSentencePositionBoundary));
1092 }
1093
1094 VisiblePosition startOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1095 {
1096     Position p = c.deepEquivalent();
1097     Node* startNode = p.deprecatedNode();
1098
1099     if (!startNode)
1100         return VisiblePosition();
1101     
1102     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1103         return positionBeforeNode(startNode);
1104
1105     Node* startBlock = enclosingBlock(startNode);
1106
1107     Node* node = startNode;
1108     Node* highestRoot = highestEditableRoot(p);
1109     int offset = p.deprecatedEditingOffset();
1110     Position::AnchorType type = p.anchorType();
1111
1112     Node* n = startNode;
1113     while (n) {
1114 #if ENABLE(USERSELECT_ALL)
1115         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNode->hasEditableStyle())
1116 #else
1117         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->hasEditableStyle() != startNode->hasEditableStyle())
1118 #endif
1119             break;
1120         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1121             while (n && n->hasEditableStyle() != startNode->hasEditableStyle())
1122                 n = NodeTraversal::previousPostOrder(n, startBlock);
1123             if (!n || !n->isDescendantOf(highestRoot))
1124                 break;
1125         }
1126         RenderObject* r = n->renderer();
1127         if (!r) {
1128             n = NodeTraversal::previousPostOrder(n, startBlock);
1129             continue;
1130         }
1131         const RenderStyle& style = r->style();
1132         if (style.visibility() != VISIBLE) {
1133             n = NodeTraversal::previousPostOrder(n, startBlock);
1134             continue;
1135         }
1136         
1137         if (r->isBR() || isBlock(n))
1138             break;
1139
1140         if (r->isText() && toRenderText(r)->hasRenderedText()) {
1141             ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1142             type = Position::PositionIsOffsetInAnchor;
1143             if (style.preserveNewline()) {
1144                 StringImpl& text = *toRenderText(r)->text();
1145                 int i = text.length();
1146                 int o = offset;
1147                 if (n == startNode && o < i)
1148                     i = std::max(0, o);
1149                 while (--i >= 0) {
1150                     if (text[i] == '\n')
1151                         return VisiblePosition(Position(toText(n), i + 1), DOWNSTREAM);
1152                 }
1153             }
1154             node = n;
1155             offset = 0;
1156             n = NodeTraversal::previousPostOrder(n, startBlock);
1157         } else if (editingIgnoresContent(n) || isRenderedTable(n)) {
1158             node = n;
1159             type = Position::PositionIsBeforeAnchor;
1160             n = n->previousSibling() ? n->previousSibling() : NodeTraversal::previousPostOrder(n, startBlock);
1161         } else
1162             n = NodeTraversal::previousPostOrder(n, startBlock);
1163     }
1164
1165     if (type == Position::PositionIsOffsetInAnchor) {
1166         ASSERT(type == Position::PositionIsOffsetInAnchor || !offset);
1167         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1168     }
1169
1170     return VisiblePosition(Position(node, type), DOWNSTREAM);
1171 }
1172
1173 VisiblePosition endOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1174 {    
1175     if (c.isNull())
1176         return VisiblePosition();
1177
1178     Position p = c.deepEquivalent();
1179     Node* startNode = p.deprecatedNode();
1180
1181     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1182         return positionAfterNode(startNode);
1183     
1184     Node* startBlock = enclosingBlock(startNode);
1185     Node* stayInsideBlock = startBlock;
1186     
1187     Node* node = startNode;
1188     Node* highestRoot = highestEditableRoot(p);
1189     int offset = p.deprecatedEditingOffset();
1190     Position::AnchorType type = p.anchorType();
1191
1192     Node* n = startNode;
1193     while (n) {
1194 #if ENABLE(USERSELECT_ALL)
1195         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNode->hasEditableStyle())
1196 #else
1197         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->hasEditableStyle() != startNode->hasEditableStyle())
1198 #endif
1199             break;
1200         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1201             while (n && n->hasEditableStyle() != startNode->hasEditableStyle())
1202                 n = NodeTraversal::next(n, stayInsideBlock);
1203             if (!n || !n->isDescendantOf(highestRoot))
1204                 break;
1205         }
1206
1207         RenderObject* r = n->renderer();
1208         if (!r) {
1209             n = NodeTraversal::next(n, stayInsideBlock);
1210             continue;
1211         }
1212         const RenderStyle& style = r->style();
1213         if (style.visibility() != VISIBLE) {
1214             n = NodeTraversal::next(n, stayInsideBlock);
1215             continue;
1216         }
1217         
1218         // FIXME: This is wrong when startNode is a block. We should return a position after the block.
1219         if (r->isBR() || isBlock(n))
1220             break;
1221
1222         // FIXME: We avoid returning a position where the renderer can't accept the caret.
1223         if (r->isText() && toRenderText(r)->hasRenderedText()) {
1224             ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1225             type = Position::PositionIsOffsetInAnchor;
1226             if (style.preserveNewline()) {
1227                 StringImpl& text = *toRenderText(r)->text();
1228                 int o = n == startNode ? offset : 0;
1229                 int length = text.length();
1230                 for (int i = o; i < length; ++i) {
1231                     if (text[i] == '\n')
1232                         return VisiblePosition(Position(toText(n), i), DOWNSTREAM);
1233                 }
1234             }
1235             node = n;
1236             offset = r->caretMaxOffset();
1237             n = NodeTraversal::next(n, stayInsideBlock);
1238         } else if (editingIgnoresContent(n) || isRenderedTable(n)) {
1239             node = n;
1240             type = Position::PositionIsAfterAnchor;
1241             n = NodeTraversal::nextSkippingChildren(n, stayInsideBlock);
1242         } else
1243             n = NodeTraversal::next(n, stayInsideBlock);
1244     }
1245
1246     if (type == Position::PositionIsOffsetInAnchor)
1247         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1248
1249     return VisiblePosition(Position(node, type), DOWNSTREAM);
1250 }
1251
1252 // FIXME: isStartOfParagraph(startOfNextParagraph(pos)) is not always true
1253 VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
1254 {
1255     VisiblePosition paragraphEnd(endOfParagraph(visiblePosition, CanSkipOverEditingBoundary));
1256     VisiblePosition afterParagraphEnd(paragraphEnd.next(CannotCrossEditingBoundary));
1257     // The position after the last position in the last cell of a table
1258     // is not the start of the next paragraph.
1259     if (isFirstPositionAfterTable(afterParagraphEnd))
1260         return afterParagraphEnd.next(CannotCrossEditingBoundary);
1261     return afterParagraphEnd;
1262 }
1263
1264 bool inSameParagraph(const VisiblePosition& a, const VisiblePosition& b, EditingBoundaryCrossingRule boundaryCrossingRule)
1265 {
1266     return a.isNotNull() && startOfParagraph(a, boundaryCrossingRule) == startOfParagraph(b, boundaryCrossingRule);
1267 }
1268
1269 bool isStartOfParagraph(const VisiblePosition& pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1270 {
1271     return pos.isNotNull() && pos == startOfParagraph(pos, boundaryCrossingRule);
1272 }
1273
1274 bool isEndOfParagraph(const VisiblePosition& pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1275 {
1276     return pos.isNotNull() && pos == endOfParagraph(pos, boundaryCrossingRule);
1277 }
1278
1279 VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
1280 {
1281     VisiblePosition pos = p;
1282     do {
1283         VisiblePosition n = previousLinePosition(pos, x);
1284         if (n.isNull() || n == pos)
1285             break;
1286         pos = n;
1287     } while (inSameParagraph(p, pos));
1288     return pos;
1289 }
1290
1291 VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
1292 {
1293     VisiblePosition pos = p;
1294     do {
1295         VisiblePosition n = nextLinePosition(pos, x);
1296         if (n.isNull() || n == pos)
1297             break;
1298         pos = n;
1299     } while (inSameParagraph(p, pos));
1300     return pos;
1301 }
1302
1303 // ---------
1304
1305 VisiblePosition startOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1306 {
1307     Position position = visiblePosition.deepEquivalent();
1308     Node* startBlock;
1309     if (!position.containerNode() || !(startBlock = enclosingBlock(position.containerNode(), rule)))
1310         return VisiblePosition();
1311     return firstPositionInNode(startBlock);
1312 }
1313
1314 VisiblePosition endOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1315 {
1316     Position position = visiblePosition.deepEquivalent();
1317     Node* endBlock;
1318     if (!position.containerNode() || !(endBlock = enclosingBlock(position.containerNode(), rule)))
1319         return VisiblePosition();
1320     return lastPositionInNode(endBlock);
1321 }
1322
1323 bool inSameBlock(const VisiblePosition& a, const VisiblePosition& b)
1324 {
1325     return !a.isNull() && enclosingBlock(a.deepEquivalent().containerNode()) == enclosingBlock(b.deepEquivalent().containerNode());
1326 }
1327
1328 bool isStartOfBlock(const VisiblePosition& pos)
1329 {
1330     return pos.isNotNull() && pos == startOfBlock(pos, CanCrossEditingBoundary);
1331 }
1332
1333 bool isEndOfBlock(const VisiblePosition& pos)
1334 {
1335     return pos.isNotNull() && pos == endOfBlock(pos, CanCrossEditingBoundary);
1336 }
1337
1338 // ---------
1339
1340 VisiblePosition startOfDocument(const Node* node)
1341 {
1342     if (!node || !node->document().documentElement())
1343         return VisiblePosition();
1344     
1345 #if PLATFORM(IOS)
1346     // The canonicalization of the position at (documentElement, 0) can turn the visible
1347     // position to null, even when there's a valid candidate to be had, because the root HTML element
1348     // is not content editable.  So we construct directly from the valid candidate.
1349     // FIXME: Do this for non-iOS platforms too. https://bugs.webkit.org/show_bug.cgi?id=56437
1350     Position firstCandidate = nextCandidate(createLegacyEditingPosition(node->document().documentElement(), 0));
1351     if (firstCandidate.isNull())
1352         return VisiblePosition();
1353     return VisiblePosition(firstCandidate);
1354 #else
1355     return VisiblePosition(firstPositionInNode(node->document().documentElement()), DOWNSTREAM);
1356 #endif
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 #if PLATFORM(IOS)
1370     // (As above, in startOfDocument.)  The canonicalization can reject valid visible positions
1371     // when descending from the root element, so we construct the visible position directly from a
1372     // valid candidate.
1373     // FIXME: Do this for non-iOS platforms too. https://bugs.webkit.org/show_bug.cgi?id=56437
1374     Position lastPosition = createLegacyEditingPosition(node->document().documentElement(), node->document().documentElement()->childNodeCount());
1375     Position lastCandidate = previousCandidate(lastPosition);
1376     if (lastCandidate.isNull())
1377         return VisiblePosition();
1378     return VisiblePosition(lastCandidate);
1379 #else
1380     return VisiblePosition(lastPositionInNode(node->document().documentElement()), DOWNSTREAM);
1381 #endif
1382 }
1383
1384 VisiblePosition endOfDocument(const VisiblePosition& c)
1385 {
1386     return endOfDocument(c.deepEquivalent().deprecatedNode());
1387 }
1388
1389 bool inSameDocument(const VisiblePosition& a, const VisiblePosition& b)
1390 {
1391     Position ap = a.deepEquivalent();
1392     Node* an = ap.deprecatedNode();
1393     if (!an)
1394         return false;
1395     Position bp = b.deepEquivalent();
1396     Node* bn = bp.deprecatedNode();
1397     if (an == bn)
1398         return true;
1399
1400     return &an->document() == &bn->document();
1401 }
1402
1403 bool isStartOfDocument(const VisiblePosition& p)
1404 {
1405     return p.isNotNull() && p.previous(CanCrossEditingBoundary).isNull();
1406 }
1407
1408 bool isEndOfDocument(const VisiblePosition& p)
1409 {
1410     return p.isNotNull() && p.next(CanCrossEditingBoundary).isNull();
1411 }
1412
1413 // ---------
1414
1415 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1416 {
1417     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1418     if (!highestRoot)
1419         return VisiblePosition();
1420
1421     return firstPositionInNode(highestRoot);
1422 }
1423
1424 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1425 {
1426     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1427     if (!highestRoot)
1428         return VisiblePosition();
1429
1430     return lastPositionInNode(highestRoot);
1431 }
1432
1433 bool isEndOfEditableOrNonEditableContent(const VisiblePosition& p)
1434 {
1435     return p.isNotNull() && p.next().isNull();
1436 }
1437
1438 VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1439 {
1440     return direction == LTR ? logicalStartOfLine(c) : logicalEndOfLine(c);
1441 }
1442
1443 VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1444 {
1445     return direction == LTR ? logicalEndOfLine(c) : logicalStartOfLine(c);
1446 }
1447
1448 static bool directionIsDownstream(SelectionDirection direction)
1449 {
1450     if (direction == DirectionBackward)
1451         return false;
1452     else if (direction == DirectionForward)
1453         return true;
1454
1455     // FIXME: this code doesn't take into account the original direction of the element.
1456     // I'm not fixing this now because I'm afraid there is some code in UIKit relying on
1457     // this wrong behavior.
1458     return direction == DirectionRight;
1459 }
1460
1461 bool atBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1462 {
1463     if (granularity == CharacterGranularity)
1464         return true;
1465
1466     VisiblePosition boundary;
1467
1468     bool useDownstream = directionIsDownstream(direction);
1469
1470     switch (granularity) {
1471     case WordGranularity:
1472         // visible_units claims erroneously that the start and the end
1473         // of a paragraph are the end and start of a word, respectively.
1474         if ((useDownstream && isStartOfParagraph(vp)) || (!useDownstream && isEndOfParagraph(vp)))
1475             return false;
1476
1477         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1478         boundary = useDownstream ? endOfWord(vp, LeftWordIfOnBoundary) : startOfWord(vp, RightWordIfOnBoundary);
1479         break;
1480
1481     case SentenceGranularity:
1482         boundary = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1483         break;
1484
1485     case LineGranularity:
1486         // Affinity has to be set to get right boundary of the line.
1487         boundary = vp;
1488         boundary.setAffinity(useDownstream ? VP_UPSTREAM_IF_POSSIBLE : DOWNSTREAM);
1489         boundary = useDownstream ? endOfLine(boundary) : startOfLine(boundary);
1490         break;
1491
1492     case ParagraphGranularity:
1493         boundary = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1494         break;
1495
1496     case DocumentGranularity:
1497         boundary = useDownstream ? endOfDocument(vp) : startOfDocument(vp);
1498         break;
1499
1500     default:
1501         ASSERT_NOT_REACHED();
1502         break;
1503     }
1504
1505     return vp == boundary;
1506 }
1507
1508 bool withinTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1509 {
1510     if (granularity == CharacterGranularity || granularity == DocumentGranularity)
1511         return true;
1512
1513     bool useDownstream = directionIsDownstream(direction);
1514
1515     VisiblePosition prevBoundary;
1516     VisiblePosition nextBoundary;
1517     
1518     switch (granularity) {
1519     case WordGranularity:
1520         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1521         prevBoundary = startOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1522         nextBoundary = endOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1523     
1524         // Workaround for <rdar://problem/7259611> Word boundary code on iPhone gives different results than desktop
1525         if (endOfWord(prevBoundary, RightWordIfOnBoundary) != nextBoundary)
1526             return false;
1527
1528         break;
1529
1530     case SentenceGranularity:
1531         prevBoundary = startOfSentence(vp);
1532         nextBoundary = endOfSentence(vp);
1533         break;
1534
1535     case LineGranularity:
1536         prevBoundary = startOfLine(vp);
1537         nextBoundary = endOfLine(vp);
1538
1539         if (prevBoundary == nextBoundary) {
1540             nextBoundary = nextLinePosition(nextBoundary, 0);
1541             nextBoundary.setAffinity(UPSTREAM);
1542             if (!inSameLine(prevBoundary, nextBoundary))
1543                 nextBoundary = vp.next();
1544         }
1545         break;
1546
1547     case ParagraphGranularity:
1548         prevBoundary = startOfParagraph(vp);
1549         nextBoundary = endOfParagraph(vp);
1550         break;
1551
1552     default:
1553         ASSERT_NOT_REACHED();
1554         break;
1555     }
1556
1557     if (prevBoundary == nextBoundary)
1558         return false;
1559
1560     if (vp == prevBoundary)
1561         return useDownstream;
1562
1563     if (vp == nextBoundary)
1564         return !useDownstream;
1565
1566     return (prevBoundary < vp && vp < nextBoundary);
1567 }
1568
1569 static VisiblePosition nextCharacterBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1570 {
1571     return directionIsDownstream(direction) ? vp.next() : vp.previous();
1572 }
1573
1574 static VisiblePosition nextWordBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1575 {
1576     bool useDownstream = directionIsDownstream(direction);
1577     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, WordGranularity, direction);
1578     VisiblePosition result;
1579     
1580     if (useDownstream) {
1581         if (withinUnitOfGranularity)
1582             result = endOfWord(vp, RightWordIfOnBoundary);
1583         else {
1584             VisiblePosition start = startOfWord(vp, RightWordIfOnBoundary);
1585             if (start > vp && start != endOfWord(start))
1586                 result = start;
1587             else {
1588                 // Do same thing as backwards traveling below.
1589                 start = vp;
1590                 while (true) {
1591                     result = startOfWord(nextWordPosition(start), RightWordIfOnBoundary);
1592
1593                     if (result == start)
1594                         break;
1595
1596                     // We failed to find a word boundary.
1597                     if (result.isNull() || result < start)
1598                         return VisiblePosition();
1599
1600                     // We consider successs also the case where start is before element and result is after.
1601                     // This covers moving past images like words.
1602                     if (result != endOfWord(result)
1603                         || (result.deepEquivalent().anchorNode() == start.deepEquivalent().anchorNode()
1604                             && result.deepEquivalent().anchorType() == Position::PositionIsAfterAnchor
1605                             && start.deepEquivalent().anchorType() == Position::PositionIsBeforeAnchor))
1606                         break;
1607
1608                     start = result;
1609                 }
1610             }
1611         }
1612     } else {
1613         if (withinUnitOfGranularity)
1614             result = startOfWord(vp, LeftWordIfOnBoundary);
1615         else {
1616             // This is complicated because:
1617             //   When given "Blah blah.|", endOfWord is "Blah blah|.", and previousWordPosition is "Blah| blah."
1618             //   When given "Blah blah. |", endOfWord is "Blah blah.| ", and previousWordPosition is "Blah |blah. ".
1619             VisiblePosition end = endOfWord(vp, LeftWordIfOnBoundary);
1620             if (end < vp && end != startOfWord(end))
1621                 result = end;
1622             else {
1623                 end = vp;
1624                 while (true) {
1625                     result = endOfWord(previousWordPosition(end), RightWordIfOnBoundary);
1626
1627                     if (result == end)
1628                         break;
1629
1630                     if (result.isNull() || result > end)
1631                         return VisiblePosition();
1632
1633                     if (result != startOfWord(result))
1634                         break;
1635
1636                     end = result;
1637                 }
1638             }
1639         }
1640     }
1641     
1642     if (result == vp)
1643         return VisiblePosition();
1644     
1645     return result;
1646 }
1647
1648 static VisiblePosition nextSentenceBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1649 {
1650     bool useDownstream = directionIsDownstream(direction);
1651     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, SentenceGranularity, direction);
1652     VisiblePosition result;
1653
1654     if (withinUnitOfGranularity)
1655         result = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1656     else {
1657         result = useDownstream ? nextSentencePosition(vp) : previousSentencePosition(vp);
1658         if (result.isNull() || result == vp)
1659             return VisiblePosition();
1660
1661         result = useDownstream ? startOfSentence(vp) : endOfSentence(vp);
1662     }
1663
1664     if (result == vp)
1665         return VisiblePosition();
1666
1667     ASSERT(useDownstream ? (result > vp) : (result < vp));
1668
1669     return result;
1670 }
1671
1672 static VisiblePosition nextLineBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1673 {
1674     bool useDownstream = directionIsDownstream(direction);
1675     VisiblePosition result = vp;
1676
1677     if (useDownstream) {
1678         result.setAffinity(DOWNSTREAM);
1679         result = isEndOfLine(result) ? startOfLine(nextLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : endOfLine(result);
1680     } else {
1681         result.setAffinity(VP_UPSTREAM_IF_POSSIBLE);
1682         result = isStartOfLine(result) ? endOfLine(previousLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : startOfLine(result);
1683     }
1684
1685     return result;
1686 }
1687
1688 static VisiblePosition nextParagraphBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1689 {
1690     bool useDownstream = directionIsDownstream(direction);
1691     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, ParagraphGranularity, direction);
1692     VisiblePosition result;
1693
1694     if (!withinUnitOfGranularity)
1695         result =  useDownstream ? startOfParagraph(nextParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation())) : endOfParagraph(previousParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation()));
1696     else
1697         result = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1698
1699     return result;
1700 }
1701
1702 static VisiblePosition nextDocumentBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1703 {
1704     return directionIsDownstream(direction) ? endOfDocument(vp) : startOfDocument(vp);
1705 }
1706
1707 VisiblePosition positionOfNextBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1708 {
1709     switch (granularity) {
1710     case CharacterGranularity:
1711         return nextCharacterBoundaryInDirection(vp, direction);
1712     case WordGranularity:
1713         return nextWordBoundaryInDirection(vp, direction);
1714     case SentenceGranularity:
1715         return nextSentenceBoundaryInDirection(vp, direction);
1716     case LineGranularity:
1717         return nextLineBoundaryInDirection(vp, direction);
1718     case ParagraphGranularity:
1719         return nextParagraphBoundaryInDirection(vp, direction);
1720     case DocumentGranularity:
1721         return nextDocumentBoundaryInDirection(vp, direction);
1722     default:
1723         ASSERT_NOT_REACHED();
1724         return VisiblePosition();
1725     }
1726 }
1727
1728 PassRefPtr<Range> enclosingTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1729 {
1730     // This is particularly inefficient.  We could easily obtain the answer with the boundaries computed below.
1731     if (!withinTextUnitOfGranularity(vp, granularity, direction))
1732         return 0;
1733
1734     VisiblePosition prevBoundary;
1735     VisiblePosition nextBoundary;
1736     bool useDownstream = directionIsDownstream(direction);
1737
1738     switch (granularity) {
1739         case CharacterGranularity:
1740             prevBoundary = vp;
1741             nextBoundary = prevBoundary.next();
1742             break;
1743
1744         case WordGranularity:
1745             // NB: "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1746             if (useDownstream) {
1747                 prevBoundary = startOfWord(vp, RightWordIfOnBoundary);
1748                 nextBoundary = endOfWord(vp, RightWordIfOnBoundary);
1749             } else {
1750                 prevBoundary = startOfWord(vp, LeftWordIfOnBoundary);
1751                 nextBoundary = endOfWord(vp, LeftWordIfOnBoundary);
1752             }
1753             break;
1754
1755         case SentenceGranularity:
1756             prevBoundary = startOfSentence(vp);
1757             nextBoundary = endOfSentence(vp);
1758             break;
1759
1760         case LineGranularity:
1761             prevBoundary = startOfLine(vp);
1762             nextBoundary = endOfLine(vp);
1763
1764             if (prevBoundary == nextBoundary) {
1765                 nextBoundary = nextLinePosition(nextBoundary, 0);
1766                 nextBoundary.setAffinity(UPSTREAM);
1767                 if (!inSameLine(prevBoundary, nextBoundary))
1768                     nextBoundary = vp.next();
1769             }
1770             break;
1771
1772         case ParagraphGranularity:
1773             prevBoundary = startOfParagraph(vp);
1774             nextBoundary = endOfParagraph(vp);
1775             break;
1776
1777         case DocumentGranularity:
1778             prevBoundary = startOfDocument(vp);
1779             nextBoundary = endOfDocument(vp);
1780             break;
1781
1782         default:
1783             ASSERT_NOT_REACHED();
1784             return 0;
1785     }
1786
1787     if (prevBoundary.isNull() || nextBoundary.isNull())
1788         return 0;
1789
1790     if (vp < prevBoundary || vp > nextBoundary)
1791         return 0;
1792
1793     RefPtr<Range> range = Range::create(prevBoundary.deepEquivalent().deprecatedNode()->document(), prevBoundary, nextBoundary);
1794
1795     return range;
1796 }
1797
1798 int distanceBetweenPositions(const VisiblePosition& vp, const VisiblePosition& other)
1799 {
1800     if (vp.isNull() || other.isNull())
1801         return 0;
1802
1803     bool thisIsStart = (vp < other);
1804
1805     // Start must come first in the Range constructor.
1806     RefPtr<Range> range = Range::create(vp.deepEquivalent().deprecatedNode()->document(),
1807                                         (thisIsStart ? vp : other),
1808                                         (thisIsStart ? other : vp));
1809     int distance = TextIterator::rangeLength(range.get());
1810
1811     return (thisIsStart ? -distance : distance);
1812 }
1813
1814 void charactersAroundPosition(const VisiblePosition& position, UChar32& oneAfter, UChar32& oneBefore, UChar32& twoBefore)
1815 {
1816     const int maxCharacters = 3;
1817     Vector<UChar32> characters(maxCharacters);
1818
1819     if (position.isNull() || isStartOfDocument(position))
1820         return;
1821
1822     VisiblePosition startPosition = position;
1823     VisiblePosition endPosition = position;
1824
1825     VisiblePosition nextPosition = nextCharacterBoundaryInDirection(position, DirectionForward);
1826     if (nextPosition.isNotNull())
1827         endPosition = nextPosition;
1828
1829     VisiblePosition previousPosition = nextCharacterBoundaryInDirection(position, DirectionBackward);
1830     if (previousPosition.isNotNull()) {
1831         startPosition = previousPosition;
1832         previousPosition = nextCharacterBoundaryInDirection(previousPosition, DirectionBackward);
1833         if (previousPosition.isNotNull())
1834             startPosition = previousPosition;
1835     }
1836
1837     if (startPosition != endPosition) {
1838         String characterString = plainText(Range::create(position.deepEquivalent().anchorNode()->document(), startPosition, endPosition).get()).replace(noBreakSpace, ' ');
1839         for (int i = characterString.length() - 1, index = 0; i >= 0 && index < maxCharacters; --i) {
1840             if (!index && nextPosition.isNull())
1841                 index++;
1842             characters[index++] = characterString[i];
1843         }
1844     }
1845     oneAfter = characters[0];
1846     oneBefore = characters[1];
1847     twoBefore = characters[2];
1848 }
1849
1850 PassRefPtr<Range> wordRangeFromPosition(const VisiblePosition& position)
1851 {
1852     // The selection could be in a non visible element and we don't have a VisiblePosition.
1853     if (position.isNull())
1854         return nullptr;
1855
1856     RefPtr<Range> range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionBackward);
1857
1858     if (!range) {
1859         // We could be at the start of a word, try forward.
1860         range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
1861     }
1862     if (range)
1863         return range;
1864
1865     VisiblePosition currentPosition = position;
1866     do {
1867         currentPosition = positionOfNextBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward);
1868     } while (currentPosition.isNotNull() && !atBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward));
1869
1870     // If the position is an empty paragraph and at the end of the document
1871     // the word iterator could not pass the paragraph boundary, therefore iterating to
1872     // the previous line is required.
1873     if (currentPosition.isNull() && isEndOfDocument(position)) {
1874         VisiblePosition previousLinePosition = positionOfNextBoundaryOfGranularity(position, LineGranularity, DirectionBackward);
1875         if (previousLinePosition.isNotNull()) {
1876             currentPosition = positionOfNextBoundaryOfGranularity(previousLinePosition, WordGranularity, DirectionBackward);
1877             if (currentPosition.isNull())
1878                 currentPosition = previousLinePosition;
1879         }
1880     }
1881
1882     if (currentPosition.isNull())
1883         currentPosition = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
1884
1885     if (currentPosition.isNotNull()) {
1886         range = Range::create(position.deepEquivalent().deprecatedNode()->document(), currentPosition, position);
1887         ASSERT(range);
1888     }
1889     return range;
1890 }
1891
1892 VisiblePosition closestWordBoundaryForPosition(const VisiblePosition& position)
1893 {
1894     VisiblePosition result;
1895
1896     // move the the position at the end of the word
1897     if (atBoundaryOfGranularity(position, LineGranularity, DirectionForward)) {
1898         // Don't cross line boundaries.
1899         result = position;
1900     } else if (withinTextUnitOfGranularity(position, WordGranularity, DirectionForward)) {
1901         // The position lies within a word.
1902         RefPtr<Range> wordRange = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
1903
1904         result = wordRange->startPosition();
1905         if (distanceBetweenPositions(position, result) > 1)
1906             result = wordRange->endPosition();
1907     } else if (atBoundaryOfGranularity(position, WordGranularity, DirectionBackward)) {
1908         // The position is at the end of a word.
1909         result = position;
1910     } else {
1911         // The position is not within a word.
1912         // Go to the next boundary.
1913         result = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
1914
1915         // If there is no such boundary we go to the end of the element.
1916         if (result.isNull())
1917             result = endOfEditableContent(position);
1918     }
1919     return result;
1920 }
1921
1922 }