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