1/*
2 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "VisibleUnits.h"
28
29#include "Document.h"
30#include "Element.h"
31#include "HTMLNames.h"
32#include "InlineTextBox.h"
33#include "NodeTraversal.h"
34#include "Position.h"
35#include "RenderBlock.h"
36#include "RenderObject.h"
37#include "RenderedPosition.h"
38#include "Text.h"
39#include "TextBoundaries.h"
40#include "TextIterator.h"
41#include "VisiblePosition.h"
42#include "VisibleSelection.h"
43#include "htmlediting.h"
44#include <wtf/unicode/Unicode.h>
45
46namespace WebCore {
47
48using namespace HTMLNames;
49using namespace WTF::Unicode;
50
51static Node* previousLeafWithSameEditability(Node* node, EditableType editableType)
52{
53    bool editable = node->rendererIsEditable(editableType);
54    node = previousLeafNode(node);
55    while (node) {
56        if (editable == node->rendererIsEditable(editableType))
57            return node;
58        node = previousLeafNode(node);
59    }
60    return 0;
61}
62
63static Node* nextLeafWithSameEditability(Node* node, EditableType editableType = ContentIsEditable)
64{
65    if (!node)
66        return 0;
67
68    bool editable = node->rendererIsEditable(editableType);
69    node = nextLeafNode(node);
70    while (node) {
71        if (editable == node->rendererIsEditable(editableType))
72            return node;
73        node = nextLeafNode(node);
74    }
75    return 0;
76}
77
78// FIXME: consolidate with code in previousLinePosition.
79static Position previousRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
80{
81    Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
82    Node* previousNode = previousLeafWithSameEditability(node, editableType);
83
84    while (previousNode && inSameLine(firstPositionInOrBeforeNode(previousNode), visiblePosition))
85        previousNode = previousLeafWithSameEditability(previousNode, editableType);
86
87    while (previousNode && !previousNode->isShadowRoot()) {
88        if (highestEditableRoot(firstPositionInOrBeforeNode(previousNode), editableType) != highestRoot)
89            break;
90
91        Position pos = previousNode->hasTagName(brTag) ? positionBeforeNode(previousNode) :
92            createLegacyEditingPosition(previousNode, caretMaxOffset(previousNode));
93
94        if (pos.isCandidate())
95            return pos;
96
97        previousNode = previousLeafWithSameEditability(previousNode, editableType);
98    }
99    return Position();
100}
101
102static Position nextRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
103{
104    Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
105    Node* nextNode = nextLeafWithSameEditability(node, editableType);
106    while (nextNode && inSameLine(firstPositionInOrBeforeNode(nextNode), visiblePosition))
107        nextNode = nextLeafWithSameEditability(nextNode, ContentIsEditable);
108
109    while (nextNode && !nextNode->isShadowRoot()) {
110        if (highestEditableRoot(firstPositionInOrBeforeNode(nextNode), editableType) != highestRoot)
111            break;
112
113        Position pos;
114        pos = createLegacyEditingPosition(nextNode, caretMinOffset(nextNode));
115
116        if (pos.isCandidate())
117            return pos;
118
119        nextNode = nextLeafWithSameEditability(nextNode, editableType);
120    }
121    return Position();
122}
123
124class CachedLogicallyOrderedLeafBoxes {
125public:
126    CachedLogicallyOrderedLeafBoxes();
127
128    const InlineTextBox* previousTextBox(const RootInlineBox*, const InlineTextBox*);
129    const InlineTextBox* nextTextBox(const RootInlineBox*, const InlineTextBox*);
130
131    size_t size() const { return m_leafBoxes.size(); }
132    const InlineBox* firstBox() const { return m_leafBoxes[0]; }
133
134private:
135    const Vector<InlineBox*>& collectBoxes(const RootInlineBox*);
136    int boxIndexInLeaves(const InlineTextBox*) const;
137
138    const RootInlineBox* m_rootInlineBox;
139    Vector<InlineBox*> m_leafBoxes;
140};
141
142CachedLogicallyOrderedLeafBoxes::CachedLogicallyOrderedLeafBoxes() : m_rootInlineBox(0) { };
143
144const InlineTextBox* CachedLogicallyOrderedLeafBoxes::previousTextBox(const RootInlineBox* root, const InlineTextBox* box)
145{
146    if (!root)
147        return 0;
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        if (m_leafBoxes[i]->isInlineTextBox())
158            return toInlineTextBox(m_leafBoxes[i]);
159    }
160
161    return 0;
162}
163
164const InlineTextBox* CachedLogicallyOrderedLeafBoxes::nextTextBox(const RootInlineBox* root, const InlineTextBox* box)
165{
166    if (!root)
167        return 0;
168
169    collectBoxes(root);
170
171    // If box is null, root is box's next RootInlineBox, and nextBox is the first logical box in root.
172    // Otherwise, root is box's RootInlineBox, and nextBox is the next logical box in the same line.
173    size_t nextBoxIndex = 0;
174    if (box)
175        nextBoxIndex = boxIndexInLeaves(box) + 1;
176
177    for (size_t i = nextBoxIndex; i < m_leafBoxes.size(); ++i) {
178        if (m_leafBoxes[i]->isInlineTextBox())
179            return toInlineTextBox(m_leafBoxes[i]);
180    }
181
182    return 0;
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 InlineTextBox* logicallyPreviousBox(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
205    bool& previousBoxInDifferentBlock, CachedLogicallyOrderedLeafBoxes& leafBoxes)
206{
207    const InlineBox* startBox = textBox;
208
209    const InlineTextBox* previousBox = leafBoxes.previousTextBox(startBox->root(), textBox);
210    if (previousBox)
211        return previousBox;
212
213    previousBox = leafBoxes.previousTextBox(startBox->root()->prevRootBox(), 0);
214    if (previousBox)
215        return previousBox;
216
217    while (1) {
218        Node* startNode = startBox->renderer() ? startBox->renderer()->nonPseudoNode() : 0;
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.previousTextBox(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 InlineTextBox* logicallyNextBox(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
246    bool& nextBoxInDifferentBlock, CachedLogicallyOrderedLeafBoxes& leafBoxes)
247{
248    const InlineBox* startBox = textBox;
249
250    const InlineTextBox* nextBox = leafBoxes.nextTextBox(startBox->root(), textBox);
251    if (nextBox)
252        return nextBox;
253
254    nextBox = leafBoxes.nextTextBox(startBox->root()->nextRootBox(), 0);
255    if (nextBox)
256        return nextBox;
257
258    while (1) {
259        Node* startNode = startBox->renderer() ? startBox->renderer()->nonPseudoNode() : 0;
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.nextTextBox(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 InlineTextBox* previousBox = logicallyPreviousBox(visiblePosition, textBox, previousBoxInDifferentBlock, leafBoxes);
292
293    int len = 0;
294    string.clear();
295    if (previousBox) {
296        previousBoxLength = previousBox->len();
297        string.append(previousBox->textRenderer()->text()->characters() + previousBox->start(), previousBoxLength);
298        len += previousBoxLength;
299    }
300    string.append(textBox->textRenderer()->text()->characters() + textBox->start(), textBox->len());
301    len += textBox->len();
302
303    return wordBreakIterator(string.data(), len);
304}
305
306static TextBreakIterator* wordBreakIteratorForMaxOffsetBoundary(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
307    bool& nextBoxInDifferentBlock, Vector<UChar, 1024>& string, CachedLogicallyOrderedLeafBoxes& leafBoxes)
308{
309    nextBoxInDifferentBlock = false;
310
311    // FIXME: Handle the case when we don't have an inline text box.
312    const InlineTextBox* nextBox = logicallyNextBox(visiblePosition, textBox, nextBoxInDifferentBlock, leafBoxes);
313
314    int len = 0;
315    string.clear();
316    string.append(textBox->textRenderer()->text()->characters() + textBox->start(), textBox->len());
317    len += textBox->len();
318    if (nextBox) {
319        string.append(nextBox->textRenderer()->text()->characters() + nextBox->start(), nextBox->len());
320        len += nextBox->len();
321    }
322
323    return wordBreakIterator(string.data(), len);
324}
325
326static bool isLogicalStartOfWord(TextBreakIterator* iter, int position, bool hardLineBreak)
327{
328    bool boundary = hardLineBreak ? true : isTextBreak(iter, position);
329    if (!boundary)
330        return false;
331
332    textBreakFollowing(iter, position);
333    // isWordTextBreak returns true after moving across a word and false after moving across a punctuation/space.
334    return isWordTextBreak(iter);
335}
336
337static bool islogicalEndOfWord(TextBreakIterator* iter, int position, bool hardLineBreak)
338{
339    bool boundary = isTextBreak(iter, position);
340    return (hardLineBreak || boundary) && isWordTextBreak(iter);
341}
342
343enum CursorMovementDirection { MoveLeft, MoveRight };
344
345static VisiblePosition visualWordPosition(const VisiblePosition& visiblePosition, CursorMovementDirection direction,
346    bool skipsSpaceWhenMovingRight)
347{
348    if (visiblePosition.isNull())
349        return VisiblePosition();
350
351    TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
352    InlineBox* previouslyVisitedBox = 0;
353    VisiblePosition current = visiblePosition;
354    TextBreakIterator* iter = 0;
355
356    CachedLogicallyOrderedLeafBoxes leafBoxes;
357    Vector<UChar, 1024> string;
358
359    while (1) {
360        VisiblePosition adjacentCharacterPosition = direction == MoveRight ? current.right(true) : current.left(true);
361        if (adjacentCharacterPosition == current || adjacentCharacterPosition.isNull())
362            return VisiblePosition();
363
364        InlineBox* box;
365        int offsetInBox;
366        adjacentCharacterPosition.deepEquivalent().getInlineBoxAndOffset(UPSTREAM, box, offsetInBox);
367
368        if (!box)
369            break;
370        if (!box->isInlineTextBox()) {
371            current = adjacentCharacterPosition;
372            continue;
373        }
374
375        InlineTextBox* textBox = toInlineTextBox(box);
376        int previousBoxLength = 0;
377        bool previousBoxInDifferentBlock = false;
378        bool nextBoxInDifferentBlock = false;
379        bool movingIntoNewBox = previouslyVisitedBox != box;
380
381        if (offsetInBox == box->caretMinOffset())
382            iter = wordBreakIteratorForMinOffsetBoundary(visiblePosition, textBox, previousBoxLength, previousBoxInDifferentBlock, string, leafBoxes);
383        else if (offsetInBox == box->caretMaxOffset())
384            iter = wordBreakIteratorForMaxOffsetBoundary(visiblePosition, textBox, nextBoxInDifferentBlock, string, leafBoxes);
385        else if (movingIntoNewBox) {
386            iter = wordBreakIterator(textBox->textRenderer()->text()->characters() + textBox->start(), textBox->len());
387            previouslyVisitedBox = box;
388        }
389
390        if (!iter)
391            break;
392
393        textBreakFirst(iter);
394        int offsetInIterator = offsetInBox - textBox->start() + previousBoxLength;
395
396        bool isWordBreak;
397        bool boxHasSameDirectionalityAsBlock = box->direction() == blockDirection;
398        bool movingBackward = (direction == MoveLeft && box->direction() == LTR) || (direction == MoveRight && box->direction() == RTL);
399        if ((skipsSpaceWhenMovingRight && boxHasSameDirectionalityAsBlock)
400            || (!skipsSpaceWhenMovingRight && movingBackward)) {
401            bool logicalStartInRenderer = offsetInBox == static_cast<int>(textBox->start()) && previousBoxInDifferentBlock;
402            isWordBreak = isLogicalStartOfWord(iter, offsetInIterator, logicalStartInRenderer);
403        } else {
404            bool logicalEndInRenderer = offsetInBox == static_cast<int>(textBox->start() + textBox->len()) && nextBoxInDifferentBlock;
405            isWordBreak = islogicalEndOfWord(iter, offsetInIterator, logicalEndInRenderer);
406        }
407
408        if (isWordBreak)
409            return adjacentCharacterPosition;
410
411        current = adjacentCharacterPosition;
412    }
413    return VisiblePosition();
414}
415
416VisiblePosition leftWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
417{
418    VisiblePosition leftWordBreak = visualWordPosition(visiblePosition, MoveLeft, skipsSpaceWhenMovingRight);
419    leftWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(leftWordBreak);
420
421    // FIXME: How should we handle a non-editable position?
422    if (leftWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
423        TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
424        leftWordBreak = blockDirection == LTR ? startOfEditableContent(visiblePosition) : endOfEditableContent(visiblePosition);
425    }
426    return leftWordBreak;
427}
428
429VisiblePosition rightWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
430{
431    VisiblePosition rightWordBreak = visualWordPosition(visiblePosition, MoveRight, skipsSpaceWhenMovingRight);
432    rightWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(rightWordBreak);
433
434    // FIXME: How should we handle a non-editable position?
435    if (rightWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
436        TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
437        rightWordBreak = blockDirection == LTR ? endOfEditableContent(visiblePosition) : startOfEditableContent(visiblePosition);
438    }
439    return rightWordBreak;
440}
441
442
443enum BoundarySearchContextAvailability { DontHaveMoreContext, MayHaveMoreContext };
444
445typedef unsigned (*BoundarySearchFunction)(const UChar*, unsigned length, unsigned offset, BoundarySearchContextAvailability, bool& needMoreContext);
446
447static VisiblePosition previousBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
448{
449    Position pos = c.deepEquivalent();
450    Node* boundary = pos.parentEditingBoundary();
451    if (!boundary)
452        return VisiblePosition();
453
454    Document* d = boundary->document();
455    Position start = createLegacyEditingPosition(boundary, 0).parentAnchoredEquivalent();
456    Position end = pos.parentAnchoredEquivalent();
457    RefPtr<Range> searchRange = Range::create(d);
458
459    Vector<UChar, 1024> string;
460    unsigned suffixLength = 0;
461
462    ExceptionCode ec = 0;
463    if (requiresContextForWordBoundary(c.characterBefore())) {
464        RefPtr<Range> forwardsScanRange(d->createRange());
465        forwardsScanRange->setEndAfter(boundary, ec);
466        forwardsScanRange->setStart(end.deprecatedNode(), end.deprecatedEditingOffset(), ec);
467        TextIterator forwardsIterator(forwardsScanRange.get());
468        while (!forwardsIterator.atEnd()) {
469            const UChar* characters = forwardsIterator.characters();
470            int length = forwardsIterator.length();
471            int i = endOfFirstWordBoundaryContext(characters, length);
472            string.append(characters, i);
473            suffixLength += i;
474            if (i < length)
475                break;
476            forwardsIterator.advance();
477        }
478    }
479
480    searchRange->setStart(start.deprecatedNode(), start.deprecatedEditingOffset(), ec);
481    searchRange->setEnd(end.deprecatedNode(), end.deprecatedEditingOffset(), ec);
482
483    ASSERT(!ec);
484    if (ec)
485        return VisiblePosition();
486
487    SimplifiedBackwardsTextIterator it(searchRange.get());
488    unsigned next = 0;
489    bool inTextSecurityMode = start.deprecatedNode() && start.deprecatedNode()->renderer() && start.deprecatedNode()->renderer()->style()->textSecurity() != TSNONE;
490    bool needMoreContext = false;
491    while (!it.atEnd()) {
492        // iterate to get chunks until the searchFunction returns a non-zero value.
493        if (!inTextSecurityMode)
494            string.insert(0, it.characters(), it.length());
495        else {
496            // Treat bullets used in the text security mode as regular characters when looking for boundaries
497            String iteratorString(it.characters(), it.length());
498            iteratorString.fill('x');
499            string.insert(0, iteratorString.characters(), iteratorString.length());
500        }
501        next = searchFunction(string.data(), string.size(), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
502        if (next > 1) // FIXME: This is a work around for https://webkit.org/b/115070. We need to provide more contexts in general case.
503            break;
504        it.advance();
505    }
506    if (needMoreContext) {
507        // The last search returned the beginning of the buffer and asked for more context,
508        // but there is no earlier text. Force a search with what's available.
509        next = searchFunction(string.data(), string.size(), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);
510        ASSERT(!needMoreContext);
511    }
512
513    if (!next)
514        return VisiblePosition(it.atEnd() ? it.range()->startPosition() : pos, DOWNSTREAM);
515
516    Node* node = it.range()->startContainer();
517    if ((node->isTextNode() && static_cast<int>(next) <= node->maxCharacterOffset()) || (node->renderer() && node->renderer()->isBR() && !next))
518        // The next variable contains a usable index into a text node
519        return VisiblePosition(createLegacyEditingPosition(node, next), DOWNSTREAM);
520
521    // Use the character iterator to translate the next value into a DOM position.
522    BackwardsCharacterIterator charIt(searchRange.get());
523    charIt.advance(string.size() - suffixLength - next);
524    // FIXME: charIt can get out of shadow host.
525    return VisiblePosition(charIt.range()->endPosition(), DOWNSTREAM);
526}
527
528static VisiblePosition nextBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
529{
530    Position pos = c.deepEquivalent();
531    Node* boundary = pos.parentEditingBoundary();
532    if (!boundary)
533        return VisiblePosition();
534
535    Document* d = boundary->document();
536    RefPtr<Range> searchRange(d->createRange());
537    Position start(pos.parentAnchoredEquivalent());
538
539    Vector<UChar, 1024> string;
540    unsigned prefixLength = 0;
541
542    if (requiresContextForWordBoundary(c.characterAfter())) {
543        RefPtr<Range> backwardsScanRange(d->createRange());
544        backwardsScanRange->setEnd(start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
545        SimplifiedBackwardsTextIterator backwardsIterator(backwardsScanRange.get());
546        while (!backwardsIterator.atEnd()) {
547            const UChar* characters = backwardsIterator.characters();
548            int length = backwardsIterator.length();
549            int i = startOfLastWordBoundaryContext(characters, length);
550            string.insert(0, characters + i, length - i);
551            prefixLength += length - i;
552            if (i > 0)
553                break;
554            backwardsIterator.advance();
555        }
556    }
557
558    searchRange->selectNodeContents(boundary, IGNORE_EXCEPTION);
559    searchRange->setStart(start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
560    TextIterator it(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
561    unsigned next = 0;
562    bool inTextSecurityMode = start.deprecatedNode() && start.deprecatedNode()->renderer() && start.deprecatedNode()->renderer()->style()->textSecurity() != TSNONE;
563    bool needMoreContext = false;
564    while (!it.atEnd()) {
565        // Keep asking the iterator for chunks until the search function
566        // returns an end value not equal to the length of the string passed to it.
567        if (!inTextSecurityMode)
568            string.append(it.characters(), it.length());
569        else {
570            // Treat bullets used in the text security mode as regular characters when looking for boundaries
571            String iteratorString(it.characters(), it.length());
572            iteratorString.fill('x');
573            string.append(iteratorString.characters(), iteratorString.length());
574        }
575        next = searchFunction(string.data(), string.size(), prefixLength, MayHaveMoreContext, needMoreContext);
576        if (next != string.size())
577            break;
578        it.advance();
579    }
580    if (needMoreContext) {
581        // The last search returned the end of the buffer and asked for more context,
582        // but there is no further text. Force a search with what's available.
583        next = searchFunction(string.data(), string.size(), prefixLength, DontHaveMoreContext, needMoreContext);
584        ASSERT(!needMoreContext);
585    }
586
587    if (it.atEnd() && next == string.size()) {
588        pos = it.range()->startPosition();
589    } else if (next != prefixLength) {
590        // Use the character iterator to translate the next value into a DOM position.
591        CharacterIterator charIt(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
592        charIt.advance(next - prefixLength - 1);
593        RefPtr<Range> characterRange = charIt.range();
594        pos = characterRange->endPosition();
595
596        if (*charIt.characters() == '\n') {
597            // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)
598            VisiblePosition visPos = VisiblePosition(pos);
599            if (visPos == VisiblePosition(characterRange->startPosition())) {
600                charIt.advance(1);
601                pos = charIt.range()->startPosition();
602            }
603        }
604    }
605
606    // generate VisiblePosition, use UPSTREAM affinity if possible
607    return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
608}
609
610// ---------
611
612static unsigned startWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
613{
614    ASSERT(offset);
615    if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
616        needMoreContext = true;
617        return 0;
618    }
619    needMoreContext = false;
620    int start, end;
621    U16_BACK_1(characters, 0, offset);
622    findWordBoundary(characters, length, offset, &start, &end);
623    return start;
624}
625
626VisiblePosition startOfWord(const VisiblePosition &c, EWordSide side)
627{
628    // FIXME: This returns a null VP for c at the start of the document
629    // and side == LeftWordIfOnBoundary
630    VisiblePosition p = c;
631    if (side == RightWordIfOnBoundary) {
632        // at paragraph end, the startofWord is the current position
633        if (isEndOfParagraph(c))
634            return c;
635
636        p = c.next();
637        if (p.isNull())
638            return c;
639    }
640    return previousBoundary(p, startWordBoundary);
641}
642
643static unsigned endWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
644{
645    ASSERT(offset <= length);
646    if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
647        needMoreContext = true;
648        return length;
649    }
650    needMoreContext = false;
651    int start, end;
652    findWordBoundary(characters, length, offset, &start, &end);
653    return end;
654}
655
656VisiblePosition endOfWord(const VisiblePosition &c, EWordSide side)
657{
658    VisiblePosition p = c;
659    if (side == LeftWordIfOnBoundary) {
660        if (isStartOfParagraph(c))
661            return c;
662
663        p = c.previous();
664        if (p.isNull())
665            return c;
666    } else if (isEndOfParagraph(c))
667        return c;
668
669    return nextBoundary(p, endWordBoundary);
670}
671
672static unsigned previousWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
673{
674    if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
675        needMoreContext = true;
676        return 0;
677    }
678    needMoreContext = false;
679    return findNextWordFromIndex(characters, length, offset, false);
680}
681
682VisiblePosition previousWordPosition(const VisiblePosition &c)
683{
684    VisiblePosition prev = previousBoundary(c, previousWordPositionBoundary);
685    return c.honorEditingBoundaryAtOrBefore(prev);
686}
687
688static unsigned nextWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
689{
690    if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
691        needMoreContext = true;
692        return length;
693    }
694    needMoreContext = false;
695    return findNextWordFromIndex(characters, length, offset, true);
696}
697
698VisiblePosition nextWordPosition(const VisiblePosition &c)
699{
700    VisiblePosition next = nextBoundary(c, nextWordPositionBoundary);
701    return c.honorEditingBoundaryAtOrAfter(next);
702}
703
704bool isStartOfWord(const VisiblePosition& p)
705{
706    return p.isNotNull() && p == startOfWord(p, RightWordIfOnBoundary);
707}
708
709// ---------
710
711enum LineEndpointComputationMode { UseLogicalOrdering, UseInlineBoxOrdering };
712static VisiblePosition startPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
713{
714    if (c.isNull())
715        return VisiblePosition();
716
717    RootInlineBox* rootBox = RenderedPosition(c).rootBox();
718    if (!rootBox) {
719        // There are VisiblePositions at offset 0 in blocks without
720        // RootInlineBoxes, like empty editable blocks and bordered blocks.
721        Position p = c.deepEquivalent();
722        if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
723            return c;
724
725        return VisiblePosition();
726    }
727
728    Node* startNode;
729    InlineBox* startBox;
730    if (mode == UseLogicalOrdering) {
731        startNode = rootBox->getLogicalStartBoxWithNode(startBox);
732        if (!startNode)
733            return VisiblePosition();
734    } else {
735        // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
736        // and so cannot be represented by a VisiblePosition. Use whatever follows instead.
737        startBox = rootBox->firstLeafChild();
738        while (true) {
739            if (!startBox)
740                return VisiblePosition();
741
742            RenderObject* startRenderer = startBox->renderer();
743            if (!startRenderer)
744                return VisiblePosition();
745
746            startNode = startRenderer->nonPseudoNode();
747            if (startNode)
748                break;
749
750            startBox = startBox->nextLeafChild();
751        }
752    }
753
754    return startNode->isTextNode() ? Position(toText(startNode), toInlineTextBox(startBox)->start())
755        : positionBeforeNode(startNode);
756}
757
758static VisiblePosition startOfLine(const VisiblePosition& c, LineEndpointComputationMode mode)
759{
760    // TODO: this is the current behavior that might need to be fixed.
761    // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
762    VisiblePosition visPos = startPositionForLine(c, mode);
763
764    if (mode == UseLogicalOrdering) {
765        if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
766            if (!editableRoot->contains(visPos.deepEquivalent().containerNode()))
767                return firstPositionInNode(editableRoot);
768        }
769    }
770
771    return c.honorEditingBoundaryAtOrBefore(visPos);
772}
773
774// FIXME: Rename this function to reflect the fact it ignores bidi levels.
775VisiblePosition startOfLine(const VisiblePosition& currentPosition)
776{
777    return startOfLine(currentPosition, UseInlineBoxOrdering);
778}
779
780VisiblePosition logicalStartOfLine(const VisiblePosition& currentPosition)
781{
782    return startOfLine(currentPosition, UseLogicalOrdering);
783}
784
785static VisiblePosition endPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
786{
787    if (c.isNull())
788        return VisiblePosition();
789
790    RootInlineBox* rootBox = RenderedPosition(c).rootBox();
791    if (!rootBox) {
792        // There are VisiblePositions at offset 0 in blocks without
793        // RootInlineBoxes, like empty editable blocks and bordered blocks.
794        Position p = c.deepEquivalent();
795        if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
796            return c;
797        return VisiblePosition();
798    }
799
800    Node* endNode;
801    InlineBox* endBox;
802    if (mode == UseLogicalOrdering) {
803        endNode = rootBox->getLogicalEndBoxWithNode(endBox);
804        if (!endNode)
805            return VisiblePosition();
806    } else {
807        // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
808        // and so cannot be represented by a VisiblePosition. Use whatever precedes instead.
809        endBox = rootBox->lastLeafChild();
810        while (true) {
811            if (!endBox)
812                return VisiblePosition();
813
814            RenderObject* endRenderer = endBox->renderer();
815            if (!endRenderer)
816                return VisiblePosition();
817
818            endNode = endRenderer->nonPseudoNode();
819            if (endNode)
820                break;
821
822            endBox = endBox->prevLeafChild();
823        }
824    }
825
826    Position pos;
827    if (endNode->hasTagName(brTag))
828        pos = positionBeforeNode(endNode);
829    else if (endBox->isInlineTextBox() && endNode->isTextNode()) {
830        InlineTextBox* endTextBox = toInlineTextBox(endBox);
831        int endOffset = endTextBox->start();
832        if (!endTextBox->isLineBreak())
833            endOffset += endTextBox->len();
834        pos = Position(toText(endNode), endOffset);
835    } else
836        pos = positionAfterNode(endNode);
837
838    return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
839}
840
841static bool inSameLogicalLine(const VisiblePosition& a, const VisiblePosition& b)
842{
843    return a.isNotNull() && logicalStartOfLine(a) == logicalStartOfLine(b);
844}
845
846static VisiblePosition endOfLine(const VisiblePosition& c, LineEndpointComputationMode mode)
847{
848    // TODO: this is the current behavior that might need to be fixed.
849    // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
850    VisiblePosition visPos = endPositionForLine(c, mode);
851
852    if (mode == UseLogicalOrdering) {
853        // Make sure the end of line is at the same line as the given input position. For a wrapping line, the logical end
854        // position for the not-last-2-lines might incorrectly hand back the logical beginning of the next line.
855        // For example, <div contenteditable dir="rtl" style="line-break:before-white-space">abcdefg abcdefg abcdefg
856        // a abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg </div>
857        // In this case, use the previous position of the computed logical end position.
858        if (!inSameLogicalLine(c, visPos))
859            visPos = visPos.previous();
860
861        if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
862            if (!editableRoot->contains(visPos.deepEquivalent().containerNode()))
863                return lastPositionInNode(editableRoot);
864        }
865
866        return c.honorEditingBoundaryAtOrAfter(visPos);
867    }
868
869    // Make sure the end of line is at the same line as the given input position. Else use the previous position to
870    // obtain end of line. This condition happens when the input position is before the space character at the end
871    // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position
872    // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style
873    // versus lines without that style, which would break before a space by default.
874    if (!inSameLine(c, visPos)) {
875        visPos = c.previous();
876        if (visPos.isNull())
877            return VisiblePosition();
878        visPos = endPositionForLine(visPos, UseInlineBoxOrdering);
879    }
880
881    return c.honorEditingBoundaryAtOrAfter(visPos);
882}
883
884// FIXME: Rename this function to reflect the fact it ignores bidi levels.
885VisiblePosition endOfLine(const VisiblePosition& currentPosition)
886{
887    return endOfLine(currentPosition, UseInlineBoxOrdering);
888}
889
890VisiblePosition logicalEndOfLine(const VisiblePosition& currentPosition)
891{
892    return endOfLine(currentPosition, UseLogicalOrdering);
893}
894
895bool inSameLine(const VisiblePosition &a, const VisiblePosition &b)
896{
897    return a.isNotNull() && startOfLine(a) == startOfLine(b);
898}
899
900bool isStartOfLine(const VisiblePosition &p)
901{
902    return p.isNotNull() && p == startOfLine(p);
903}
904
905bool isEndOfLine(const VisiblePosition &p)
906{
907    return p.isNotNull() && p == endOfLine(p);
908}
909
910static inline IntPoint absoluteLineDirectionPointToLocalPointInBlock(RootInlineBox* root, int lineDirectionPoint)
911{
912    ASSERT(root);
913    RenderBlock* containingBlock = root->block();
914    FloatPoint absoluteBlockPoint = containingBlock->localToAbsolute(FloatPoint());
915    if (containingBlock->hasOverflowClip())
916        absoluteBlockPoint -= containingBlock->scrolledContentOffset();
917
918    if (root->block()->isHorizontalWritingMode())
919        return IntPoint(lineDirectionPoint - absoluteBlockPoint.x(), root->blockDirectionPointInLine());
920
921    return IntPoint(root->blockDirectionPointInLine(), lineDirectionPoint - absoluteBlockPoint.y());
922}
923
924VisiblePosition previousLinePosition(const VisiblePosition &visiblePosition, int lineDirectionPoint, EditableType editableType)
925{
926    Position p = visiblePosition.deepEquivalent();
927    Node* node = p.deprecatedNode();
928
929    if (!node)
930        return VisiblePosition();
931
932    node->document()->updateLayoutIgnorePendingStylesheets();
933
934    RenderObject* renderer = node->renderer();
935    if (!renderer)
936        return VisiblePosition();
937
938    RootInlineBox* root = 0;
939    InlineBox* box;
940    int ignoredCaretOffset;
941    visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
942    if (box) {
943        root = box->root()->prevRootBox();
944        // We want to skip zero height boxes.
945        // This could happen in case it is a TrailingFloatsRootInlineBox.
946        if (!root || !root->logicalHeight() || !root->firstLeafChild())
947            root = 0;
948    }
949
950    if (!root) {
951        Position position = previousRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
952        if (position.isNotNull()) {
953            RenderedPosition renderedPosition(position);
954            root = renderedPosition.rootBox();
955            if (!root)
956                return position;
957        }
958    }
959
960    if (root) {
961        // FIXME: Can be wrong for multi-column layout and with transforms.
962        IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(root, lineDirectionPoint);
963        RenderObject* renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
964        Node* node = renderer->node();
965        if (node && editingIgnoresContent(node))
966            return positionInParentBeforeNode(node);
967        return renderer->positionForPoint(pointInLine);
968    }
969
970    // Could not find a previous line. This means we must already be on the first line.
971    // Move to the start of the content in this block, which effectively moves us
972    // to the start of the line we're on.
973    Element* rootElement = node->rendererIsEditable(editableType) ? node->rootEditableElement(editableType) : node->document()->documentElement();
974    if (!rootElement)
975        return VisiblePosition();
976    return VisiblePosition(firstPositionInNode(rootElement), DOWNSTREAM);
977}
978
979VisiblePosition nextLinePosition(const VisiblePosition &visiblePosition, int lineDirectionPoint, EditableType editableType)
980{
981    Position p = visiblePosition.deepEquivalent();
982    Node* node = p.deprecatedNode();
983
984    if (!node)
985        return VisiblePosition();
986
987    node->document()->updateLayoutIgnorePendingStylesheets();
988
989    RenderObject* renderer = node->renderer();
990    if (!renderer)
991        return VisiblePosition();
992
993    RootInlineBox* root = 0;
994    InlineBox* box;
995    int ignoredCaretOffset;
996    visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
997    if (box) {
998        root = box->root()->nextRootBox();
999        // We want to skip zero height boxes.
1000        // This could happen in case it is a TrailingFloatsRootInlineBox.
1001        if (!root || !root->logicalHeight() || !root->firstLeafChild())
1002            root = 0;
1003    }
1004
1005    if (!root) {
1006        // FIXME: We need do the same in previousLinePosition.
1007        Node* child = node->childNode(p.deprecatedEditingOffset());
1008        node = child ? child : node->lastDescendant();
1009        Position position = nextRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
1010        if (position.isNotNull()) {
1011            RenderedPosition renderedPosition(position);
1012            root = renderedPosition.rootBox();
1013            if (!root)
1014                return position;
1015        }
1016    }
1017
1018    if (root) {
1019        // FIXME: Can be wrong for multi-column layout and with transforms.
1020        IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(root, lineDirectionPoint);
1021        RenderObject* renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
1022        Node* node = renderer->node();
1023        if (node && editingIgnoresContent(node))
1024            return positionInParentBeforeNode(node);
1025        return renderer->positionForPoint(pointInLine);
1026    }
1027
1028    // Could not find a next line. This means we must already be on the last line.
1029    // Move to the end of the content in this block, which effectively moves us
1030    // to the end of the line we're on.
1031    Element* rootElement = node->rendererIsEditable(editableType) ? node->rootEditableElement(editableType) : node->document()->documentElement();
1032    if (!rootElement)
1033        return VisiblePosition();
1034    return VisiblePosition(lastPositionInNode(rootElement), DOWNSTREAM);
1035}
1036
1037// ---------
1038
1039static unsigned startSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1040{
1041    TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1042    // FIXME: The following function can return -1; we don't handle that.
1043    return textBreakPreceding(iterator, length);
1044}
1045
1046VisiblePosition startOfSentence(const VisiblePosition &c)
1047{
1048    return previousBoundary(c, startSentenceBoundary);
1049}
1050
1051static unsigned endSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1052{
1053    TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1054    return textBreakNext(iterator);
1055}
1056
1057// FIXME: This includes the space after the punctuation that marks the end of the sentence.
1058VisiblePosition endOfSentence(const VisiblePosition &c)
1059{
1060    return nextBoundary(c, endSentenceBoundary);
1061}
1062
1063static unsigned previousSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1064{
1065    // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
1066    TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1067    // FIXME: The following function can return -1; we don't handle that.
1068    return textBreakPreceding(iterator, length);
1069}
1070
1071VisiblePosition previousSentencePosition(const VisiblePosition &c)
1072{
1073    VisiblePosition prev = previousBoundary(c, previousSentencePositionBoundary);
1074    return c.honorEditingBoundaryAtOrBefore(prev);
1075}
1076
1077static unsigned nextSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1078{
1079    // FIXME: This is identical to endSentenceBoundary. This isn't right, it needs to
1080    // move to the equivlant position in the following sentence.
1081    TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1082    return textBreakFollowing(iterator, 0);
1083}
1084
1085VisiblePosition nextSentencePosition(const VisiblePosition &c)
1086{
1087    VisiblePosition next = nextBoundary(c, nextSentencePositionBoundary);
1088    return c.honorEditingBoundaryAtOrAfter(next);
1089}
1090
1091VisiblePosition startOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1092{
1093    Position p = c.deepEquivalent();
1094    Node* startNode = p.deprecatedNode();
1095
1096    if (!startNode)
1097        return VisiblePosition();
1098
1099    if (isRenderedAsNonInlineTableImageOrHR(startNode))
1100        return positionBeforeNode(startNode);
1101
1102    Node* startBlock = enclosingBlock(startNode);
1103
1104    Node* node = startNode;
1105    Node* highestRoot = highestEditableRoot(p);
1106    int offset = p.deprecatedEditingOffset();
1107    Position::AnchorType type = p.anchorType();
1108
1109    Node* n = startNode;
1110    while (n) {
1111#if ENABLE(USERSELECT_ALL)
1112        if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->rendererIsEditable() != startNode->rendererIsEditable())
1113#else
1114        if (boundaryCrossingRule == CannotCrossEditingBoundary && n->rendererIsEditable() != startNode->rendererIsEditable())
1115#endif
1116            break;
1117        if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1118            while (n && n->rendererIsEditable() != startNode->rendererIsEditable())
1119                n = NodeTraversal::previousPostOrder(n, startBlock);
1120            if (!n || !n->isDescendantOf(highestRoot))
1121                break;
1122        }
1123        RenderObject* r = n->renderer();
1124        if (!r) {
1125            n = NodeTraversal::previousPostOrder(n, startBlock);
1126            continue;
1127        }
1128        RenderStyle* style = r->style();
1129        if (style->visibility() != VISIBLE) {
1130            n = NodeTraversal::previousPostOrder(n, startBlock);
1131            continue;
1132        }
1133
1134        if (r->isBR() || isBlock(n))
1135            break;
1136
1137        if (r->isText() && toRenderText(r)->renderedTextLength()) {
1138            ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1139            type = Position::PositionIsOffsetInAnchor;
1140            if (style->preserveNewline()) {
1141                const UChar* chars = toRenderText(r)->characters();
1142                int i = toRenderText(r)->textLength();
1143                int o = offset;
1144                if (n == startNode && o < i)
1145                    i = max(0, o);
1146                while (--i >= 0) {
1147                    if (chars[i] == '\n')
1148                        return VisiblePosition(Position(toText(n), i + 1), DOWNSTREAM);
1149                }
1150            }
1151            node = n;
1152            offset = 0;
1153            n = NodeTraversal::previousPostOrder(n, startBlock);
1154        } else if (editingIgnoresContent(n) || isTableElement(n)) {
1155            node = n;
1156            type = Position::PositionIsBeforeAnchor;
1157            n = n->previousSibling() ? n->previousSibling() : NodeTraversal::previousPostOrder(n, startBlock);
1158        } else
1159            n = NodeTraversal::previousPostOrder(n, startBlock);
1160    }
1161
1162    if (type == Position::PositionIsOffsetInAnchor) {
1163        ASSERT(type == Position::PositionIsOffsetInAnchor || !offset);
1164        return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1165    }
1166
1167    return VisiblePosition(Position(node, type), DOWNSTREAM);
1168}
1169
1170VisiblePosition endOfParagraph(const VisiblePosition &c, EditingBoundaryCrossingRule boundaryCrossingRule)
1171{
1172    if (c.isNull())
1173        return VisiblePosition();
1174
1175    Position p = c.deepEquivalent();
1176    Node* startNode = p.deprecatedNode();
1177
1178    if (isRenderedAsNonInlineTableImageOrHR(startNode))
1179        return positionAfterNode(startNode);
1180
1181    Node* startBlock = enclosingBlock(startNode);
1182    Node* stayInsideBlock = startBlock;
1183
1184    Node* node = startNode;
1185    Node* highestRoot = highestEditableRoot(p);
1186    int offset = p.deprecatedEditingOffset();
1187    Position::AnchorType type = p.anchorType();
1188
1189    Node* n = startNode;
1190    while (n) {
1191#if ENABLE(USERSELECT_ALL)
1192        if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->rendererIsEditable() != startNode->rendererIsEditable())
1193#else
1194        if (boundaryCrossingRule == CannotCrossEditingBoundary && n->rendererIsEditable() != startNode->rendererIsEditable())
1195#endif
1196            break;
1197        if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1198            while (n && n->rendererIsEditable() != startNode->rendererIsEditable())
1199                n = NodeTraversal::next(n, stayInsideBlock);
1200            if (!n || !n->isDescendantOf(highestRoot))
1201                break;
1202        }
1203
1204        RenderObject* r = n->renderer();
1205        if (!r) {
1206            n = NodeTraversal::next(n, stayInsideBlock);
1207            continue;
1208        }
1209        RenderStyle* style = r->style();
1210        if (style->visibility() != VISIBLE) {
1211            n = NodeTraversal::next(n, stayInsideBlock);
1212            continue;
1213        }
1214
1215        if (r->isBR() || isBlock(n))
1216            break;
1217
1218        // FIXME: We avoid returning a position where the renderer can't accept the caret.
1219        if (r->isText() && toRenderText(r)->renderedTextLength()) {
1220            ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1221            int length = toRenderText(r)->textLength();
1222            type = Position::PositionIsOffsetInAnchor;
1223            if (style->preserveNewline()) {
1224                const UChar* chars = toRenderText(r)->characters();
1225                int o = n == startNode ? offset : 0;
1226                for (int i = o; i < length; ++i) {
1227                    if (chars[i] == '\n')
1228                        return VisiblePosition(Position(toText(n), i), DOWNSTREAM);
1229                }
1230            }
1231            node = n;
1232            offset = r->caretMaxOffset();
1233            n = NodeTraversal::next(n, stayInsideBlock);
1234        } else if (editingIgnoresContent(n) || isTableElement(n)) {
1235            node = n;
1236            type = Position::PositionIsAfterAnchor;
1237            n = NodeTraversal::nextSkippingChildren(n, stayInsideBlock);
1238        } else
1239            n = NodeTraversal::next(n, stayInsideBlock);
1240    }
1241
1242    if (type == Position::PositionIsOffsetInAnchor)
1243        return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1244
1245    return VisiblePosition(Position(node, type), DOWNSTREAM);
1246}
1247
1248// FIXME: isStartOfParagraph(startOfNextParagraph(pos)) is not always true
1249VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
1250{
1251    VisiblePosition paragraphEnd(endOfParagraph(visiblePosition, CanSkipOverEditingBoundary));
1252    VisiblePosition afterParagraphEnd(paragraphEnd.next(CannotCrossEditingBoundary));
1253    // The position after the last position in the last cell of a table
1254    // is not the start of the next paragraph.
1255    if (isFirstPositionAfterTable(afterParagraphEnd))
1256        return afterParagraphEnd.next(CannotCrossEditingBoundary);
1257    return afterParagraphEnd;
1258}
1259
1260bool inSameParagraph(const VisiblePosition &a, const VisiblePosition &b, EditingBoundaryCrossingRule boundaryCrossingRule)
1261{
1262    return a.isNotNull() && startOfParagraph(a, boundaryCrossingRule) == startOfParagraph(b, boundaryCrossingRule);
1263}
1264
1265bool isStartOfParagraph(const VisiblePosition &pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1266{
1267    return pos.isNotNull() && pos == startOfParagraph(pos, boundaryCrossingRule);
1268}
1269
1270bool isEndOfParagraph(const VisiblePosition &pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1271{
1272    return pos.isNotNull() && pos == endOfParagraph(pos, boundaryCrossingRule);
1273}
1274
1275VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
1276{
1277    VisiblePosition pos = p;
1278    do {
1279        VisiblePosition n = previousLinePosition(pos, x);
1280        if (n.isNull() || n == pos)
1281            break;
1282        pos = n;
1283    } while (inSameParagraph(p, pos));
1284    return pos;
1285}
1286
1287VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
1288{
1289    VisiblePosition pos = p;
1290    do {
1291        VisiblePosition n = nextLinePosition(pos, x);
1292        if (n.isNull() || n == pos)
1293            break;
1294        pos = n;
1295    } while (inSameParagraph(p, pos));
1296    return pos;
1297}
1298
1299// ---------
1300
1301VisiblePosition startOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1302{
1303    Position position = visiblePosition.deepEquivalent();
1304    Node* startBlock;
1305    if (!position.containerNode() || !(startBlock = enclosingBlock(position.containerNode(), rule)))
1306        return VisiblePosition();
1307    return firstPositionInNode(startBlock);
1308}
1309
1310VisiblePosition endOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1311{
1312    Position position = visiblePosition.deepEquivalent();
1313    Node* endBlock;
1314    if (!position.containerNode() || !(endBlock = enclosingBlock(position.containerNode(), rule)))
1315        return VisiblePosition();
1316    return lastPositionInNode(endBlock);
1317}
1318
1319bool inSameBlock(const VisiblePosition &a, const VisiblePosition &b)
1320{
1321    return !a.isNull() && enclosingBlock(a.deepEquivalent().containerNode()) == enclosingBlock(b.deepEquivalent().containerNode());
1322}
1323
1324bool isStartOfBlock(const VisiblePosition &pos)
1325{
1326    return pos.isNotNull() && pos == startOfBlock(pos, CanCrossEditingBoundary);
1327}
1328
1329bool isEndOfBlock(const VisiblePosition &pos)
1330{
1331    return pos.isNotNull() && pos == endOfBlock(pos, CanCrossEditingBoundary);
1332}
1333
1334// ---------
1335
1336VisiblePosition startOfDocument(const Node* node)
1337{
1338    if (!node || !node->document() || !node->document()->documentElement())
1339        return VisiblePosition();
1340
1341    return VisiblePosition(firstPositionInNode(node->document()->documentElement()), DOWNSTREAM);
1342}
1343
1344VisiblePosition startOfDocument(const VisiblePosition &c)
1345{
1346    return startOfDocument(c.deepEquivalent().deprecatedNode());
1347}
1348
1349VisiblePosition endOfDocument(const Node* node)
1350{
1351    if (!node || !node->document() || !node->document()->documentElement())
1352        return VisiblePosition();
1353
1354    Element* doc = node->document()->documentElement();
1355    return VisiblePosition(lastPositionInNode(doc), DOWNSTREAM);
1356}
1357
1358VisiblePosition endOfDocument(const VisiblePosition &c)
1359{
1360    return endOfDocument(c.deepEquivalent().deprecatedNode());
1361}
1362
1363bool inSameDocument(const VisiblePosition &a, const VisiblePosition &b)
1364{
1365    Position ap = a.deepEquivalent();
1366    Node* an = ap.deprecatedNode();
1367    if (!an)
1368        return false;
1369    Position bp = b.deepEquivalent();
1370    Node* bn = bp.deprecatedNode();
1371    if (an == bn)
1372        return true;
1373
1374    return an->document() == bn->document();
1375}
1376
1377bool isStartOfDocument(const VisiblePosition &p)
1378{
1379    return p.isNotNull() && p.previous(CanCrossEditingBoundary).isNull();
1380}
1381
1382bool isEndOfDocument(const VisiblePosition &p)
1383{
1384    return p.isNotNull() && p.next(CanCrossEditingBoundary).isNull();
1385}
1386
1387// ---------
1388
1389VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1390{
1391    Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1392    if (!highestRoot)
1393        return VisiblePosition();
1394
1395    return firstPositionInNode(highestRoot);
1396}
1397
1398VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1399{
1400    Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1401    if (!highestRoot)
1402        return VisiblePosition();
1403
1404    return lastPositionInNode(highestRoot);
1405}
1406
1407bool isEndOfEditableOrNonEditableContent(const VisiblePosition &p)
1408{
1409    return p.isNotNull() && p.next().isNull();
1410}
1411
1412VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1413{
1414    return direction == LTR ? logicalStartOfLine(c) : logicalEndOfLine(c);
1415}
1416
1417VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1418{
1419    return direction == LTR ? logicalEndOfLine(c) : logicalStartOfLine(c);
1420}
1421
1422}
1423