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