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