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