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