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