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 "visible_units.h"
28
29#include "Document.h"
30#include "Element.h"
31#include "HTMLNames.h"
32#include "RenderBlock.h"
33#include "RenderLayer.h"
34#include "TextBoundaries.h"
35#include "TextBreakIterator.h"
36#include "TextIterator.h"
37#include "VisiblePosition.h"
38#include "htmlediting.h"
39#include <wtf/unicode/Unicode.h>
40
41namespace WebCore {
42
43using namespace HTMLNames;
44using namespace WTF::Unicode;
45
46static int endOfFirstWordBoundaryContext(const UChar* characters, int length)
47{
48    for (int i = 0; i < length; ) {
49        int first = i;
50        UChar32 ch;
51        U16_NEXT(characters, i, length, ch);
52        if (!requiresContextForWordBoundary(ch))
53            return first;
54    }
55    return length;
56}
57
58static int startOfLastWordBoundaryContext(const UChar* characters, int length)
59{
60    for (int i = length; i > 0; ) {
61        int last = i;
62        UChar32 ch;
63        U16_PREV(characters, 0, i, ch);
64        if (!requiresContextForWordBoundary(ch))
65            return last;
66    }
67    return 0;
68}
69
70enum BoundarySearchContextAvailability { DontHaveMoreContext, MayHaveMoreContext };
71
72typedef unsigned (*BoundarySearchFunction)(const UChar*, unsigned length, unsigned offset, BoundarySearchContextAvailability, bool& needMoreContext);
73
74static VisiblePosition previousBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
75{
76    Position pos = c.deepEquivalent();
77    Node *n = pos.node();
78    if (!n)
79        return VisiblePosition();
80    Document *d = n->document();
81    Node *de = d->documentElement();
82    if (!de)
83        return VisiblePosition();
84    Node *boundary = n->enclosingBlockFlowElement();
85    if (!boundary)
86        return VisiblePosition();
87    bool isContentEditable = boundary->isContentEditable();
88    while (boundary && boundary != de && boundary->parentNode() && isContentEditable == boundary->parentNode()->isContentEditable())
89        boundary = boundary->parentNode();
90
91    Position start = rangeCompliantEquivalent(Position(boundary, 0));
92    Position end = rangeCompliantEquivalent(pos);
93    RefPtr<Range> searchRange = Range::create(d);
94
95    Vector<UChar, 1024> string;
96    unsigned suffixLength = 0;
97
98    ExceptionCode ec = 0;
99    if (requiresContextForWordBoundary(c.characterBefore())) {
100        RefPtr<Range> forwardsScanRange(d->createRange());
101        forwardsScanRange->setEndAfter(boundary, ec);
102        forwardsScanRange->setStart(end.node(), end.deprecatedEditingOffset(), ec);
103        TextIterator forwardsIterator(forwardsScanRange.get());
104        while (!forwardsIterator.atEnd()) {
105            const UChar* characters = forwardsIterator.characters();
106            int length = forwardsIterator.length();
107            int i = endOfFirstWordBoundaryContext(characters, length);
108            string.append(characters, i);
109            suffixLength += i;
110            if (i < length)
111                break;
112            forwardsIterator.advance();
113        }
114    }
115
116    searchRange->setStart(start.node(), start.deprecatedEditingOffset(), ec);
117    searchRange->setEnd(end.node(), end.deprecatedEditingOffset(), ec);
118
119    ASSERT(!ec);
120    if (ec)
121        return VisiblePosition();
122
123    SimplifiedBackwardsTextIterator it(searchRange.get());
124    unsigned next = 0;
125    bool inTextSecurityMode = start.node() && start.node()->renderer() && start.node()->renderer()->style()->textSecurity() != TSNONE;
126    bool needMoreContext = false;
127    while (!it.atEnd()) {
128        // iterate to get chunks until the searchFunction returns a non-zero value.
129        if (!inTextSecurityMode)
130            string.prepend(it.characters(), it.length());
131        else {
132            // Treat bullets used in the text security mode as regular characters when looking for boundaries
133            String iteratorString(it.characters(), it.length());
134            iteratorString = iteratorString.impl()->secure('x');
135            string.prepend(iteratorString.characters(), iteratorString.length());
136        }
137        next = searchFunction(string.data(), string.size(), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
138        if (next != 0)
139            break;
140        it.advance();
141    }
142    if (needMoreContext) {
143        // The last search returned the beginning of the buffer and asked for more context,
144        // but there is no earlier text. Force a search with what's available.
145        next = searchFunction(string.data(), string.size(), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);
146        ASSERT(!needMoreContext);
147    }
148
149    if (it.atEnd() && next == 0) {
150        pos = it.range()->startPosition();
151    } else if (next != 0) {
152        Node *node = it.range()->startContainer(ec);
153        if ((node->isTextNode() && static_cast<int>(next) <= node->maxCharacterOffset()) || (node->renderer() && node->renderer()->isBR() && !next))
154            // The next variable contains a usable index into a text node
155            pos = Position(node, next);
156        else {
157            // Use the character iterator to translate the next value into a DOM position.
158            BackwardsCharacterIterator charIt(searchRange.get());
159            charIt.advance(string.size() - suffixLength - next);
160            pos = charIt.range()->endPosition();
161        }
162    }
163
164    return VisiblePosition(pos, DOWNSTREAM);
165}
166
167static VisiblePosition nextBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
168{
169    Position pos = c.deepEquivalent();
170    Node *n = pos.node();
171    if (!n)
172        return VisiblePosition();
173    Document *d = n->document();
174    Node *de = d->documentElement();
175    if (!de)
176        return VisiblePosition();
177    Node *boundary = n->enclosingBlockFlowElement();
178    if (!boundary)
179        return VisiblePosition();
180    bool isContentEditable = boundary->isContentEditable();
181    while (boundary && boundary != de && boundary->parentNode() && isContentEditable == boundary->parentNode()->isContentEditable())
182        boundary = boundary->parentNode();
183
184    RefPtr<Range> searchRange(d->createRange());
185    Position start(rangeCompliantEquivalent(pos));
186
187    Vector<UChar, 1024> string;
188    unsigned prefixLength = 0;
189
190    ExceptionCode ec = 0;
191    if (requiresContextForWordBoundary(c.characterAfter())) {
192        RefPtr<Range> backwardsScanRange(d->createRange());
193        backwardsScanRange->setEnd(start.node(), start.deprecatedEditingOffset(), ec);
194        SimplifiedBackwardsTextIterator backwardsIterator(backwardsScanRange.get());
195        while (!backwardsIterator.atEnd()) {
196            const UChar* characters = backwardsIterator.characters();
197            int length = backwardsIterator.length();
198            int i = startOfLastWordBoundaryContext(characters, length);
199            string.prepend(characters + i, length - i);
200            prefixLength += length - i;
201            if (i > 0)
202                break;
203            backwardsIterator.advance();
204        }
205    }
206
207    searchRange->selectNodeContents(boundary, ec);
208    searchRange->setStart(start.node(), start.deprecatedEditingOffset(), ec);
209    TextIterator it(searchRange.get(), true);
210    unsigned next = 0;
211    bool inTextSecurityMode = start.node() && start.node()->renderer() && start.node()->renderer()->style()->textSecurity() != TSNONE;
212    bool needMoreContext = false;
213    while (!it.atEnd()) {
214        // Keep asking the iterator for chunks until the search function
215        // returns an end value not equal to the length of the string passed to it.
216        if (!inTextSecurityMode)
217            string.append(it.characters(), it.length());
218        else {
219            // Treat bullets used in the text security mode as regular characters when looking for boundaries
220            String iteratorString(it.characters(), it.length());
221            iteratorString = iteratorString.impl()->secure('x');
222            string.append(iteratorString.characters(), iteratorString.length());
223        }
224        next = searchFunction(string.data(), string.size(), prefixLength, MayHaveMoreContext, needMoreContext);
225        if (next != string.size())
226            break;
227        it.advance();
228    }
229    if (needMoreContext) {
230        // The last search returned the end of the buffer and asked for more context,
231        // but there is no further text. Force a search with what's available.
232        next = searchFunction(string.data(), string.size(), prefixLength, DontHaveMoreContext, needMoreContext);
233        ASSERT(!needMoreContext);
234    }
235
236    if (it.atEnd() && next == string.size()) {
237        pos = it.range()->startPosition();
238    } else if (next != prefixLength) {
239        // Use the character iterator to translate the next value into a DOM position.
240        CharacterIterator charIt(searchRange.get(), true);
241        charIt.advance(next - prefixLength - 1);
242        pos = charIt.range()->endPosition();
243
244        if (*charIt.characters() == '\n') {
245            // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)
246            VisiblePosition visPos = VisiblePosition(pos);
247            if (visPos == VisiblePosition(charIt.range()->startPosition()))
248                pos = visPos.next(true).deepEquivalent();
249        }
250    }
251
252    // generate VisiblePosition, use UPSTREAM affinity if possible
253    return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
254}
255
256// ---------
257
258static unsigned startWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
259{
260    ASSERT(offset);
261    if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
262        needMoreContext = true;
263        return 0;
264    }
265    needMoreContext = false;
266    int start, end;
267    findWordBoundary(characters, length, offset - 1, &start, &end);
268    return start;
269}
270
271VisiblePosition startOfWord(const VisiblePosition &c, EWordSide side)
272{
273    // FIXME: This returns a null VP for c at the start of the document
274    // and side == LeftWordIfOnBoundary
275    VisiblePosition p = c;
276    if (side == RightWordIfOnBoundary) {
277        // at paragraph end, the startofWord is the current position
278        if (isEndOfParagraph(c))
279            return c;
280
281        p = c.next();
282        if (p.isNull())
283            return c;
284    }
285    return previousBoundary(p, startWordBoundary);
286}
287
288static unsigned endWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
289{
290    ASSERT(offset <= length);
291    if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
292        needMoreContext = true;
293        return length;
294    }
295    needMoreContext = false;
296    int start, end;
297    findWordBoundary(characters, length, offset, &start, &end);
298    return end;
299}
300
301VisiblePosition endOfWord(const VisiblePosition &c, EWordSide side)
302{
303    VisiblePosition p = c;
304    if (side == LeftWordIfOnBoundary) {
305        if (isStartOfParagraph(c))
306            return c;
307
308        p = c.previous();
309        if (p.isNull())
310            return c;
311    } else if (isEndOfParagraph(c))
312        return c;
313
314    return nextBoundary(p, endWordBoundary);
315}
316
317static unsigned previousWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
318{
319    if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
320        needMoreContext = true;
321        return 0;
322    }
323    needMoreContext = false;
324    return findNextWordFromIndex(characters, length, offset, false);
325}
326
327VisiblePosition previousWordPosition(const VisiblePosition &c)
328{
329    VisiblePosition prev = previousBoundary(c, previousWordPositionBoundary);
330    return c.honorEditableBoundaryAtOrAfter(prev);
331}
332
333static unsigned nextWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
334{
335    if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
336        needMoreContext = true;
337        return length;
338    }
339    needMoreContext = false;
340    return findNextWordFromIndex(characters, length, offset, true);
341}
342
343VisiblePosition nextWordPosition(const VisiblePosition &c)
344{
345    VisiblePosition next = nextBoundary(c, nextWordPositionBoundary);
346    return c.honorEditableBoundaryAtOrBefore(next);
347}
348
349// ---------
350
351static RootInlineBox *rootBoxForLine(const VisiblePosition &c)
352{
353    Position p = c.deepEquivalent();
354    Node *node = p.node();
355    if (!node)
356        return 0;
357
358    RenderObject *renderer = node->renderer();
359    if (!renderer)
360        return 0;
361
362    InlineBox* box;
363    int offset;
364    c.getInlineBoxAndOffset(box, offset);
365
366    return box ? box->root() : 0;
367}
368
369static VisiblePosition positionAvoidingFirstPositionInTable(const VisiblePosition& c)
370{
371    // return table offset 0 instead of the first VisiblePosition inside the table
372    VisiblePosition previous = c.previous();
373    if (isLastPositionBeforeTable(previous))
374        return previous;
375
376    return c;
377}
378
379static VisiblePosition startPositionForLine(const VisiblePosition& c)
380{
381    if (c.isNull())
382        return VisiblePosition();
383
384    RootInlineBox *rootBox = rootBoxForLine(c);
385    if (!rootBox) {
386        // There are VisiblePositions at offset 0 in blocks without
387        // RootInlineBoxes, like empty editable blocks and bordered blocks.
388        Position p = c.deepEquivalent();
389        if (p.node()->renderer() && p.node()->renderer()->isRenderBlock() && p.deprecatedEditingOffset() == 0)
390            return positionAvoidingFirstPositionInTable(c);
391
392        return VisiblePosition();
393    }
394
395    // Generated content (e.g. list markers and CSS :before and :after
396    // pseudoelements) have no corresponding DOM element, and so cannot be
397    // represented by a VisiblePosition.  Use whatever follows instead.
398    InlineBox *startBox = rootBox->firstLeafChild();
399    Node *startNode;
400    while (1) {
401        if (!startBox)
402            return VisiblePosition();
403
404        RenderObject *startRenderer = startBox->renderer();
405        if (!startRenderer)
406            return VisiblePosition();
407
408        startNode = startRenderer->node();
409        if (startNode)
410            break;
411
412        startBox = startBox->nextLeafChild();
413    }
414
415    int startOffset = 0;
416    if (startBox->isInlineTextBox()) {
417        InlineTextBox *startTextBox = static_cast<InlineTextBox *>(startBox);
418        startOffset = startTextBox->start();
419    }
420
421    VisiblePosition visPos = VisiblePosition(startNode, startOffset, DOWNSTREAM);
422    return positionAvoidingFirstPositionInTable(visPos);
423}
424
425VisiblePosition startOfLine(const VisiblePosition& c)
426{
427    VisiblePosition visPos = startPositionForLine(c);
428
429    if (visPos.isNotNull()) {
430        // Make sure the start of line is not greater than the given input position.  Else use the previous position to
431        // obtain start of line.  This condition happens when the input position is before the space character at the end
432        // of a soft-wrapped non-editable line. In this scenario, startPositionForLine would incorrectly hand back a position
433        // greater than the input position.  This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space
434        // style versus lines without that style, which would break before a space by default.
435        Position p = visPos.deepEquivalent();
436        if (p.deprecatedEditingOffset() > c.deepEquivalent().deprecatedEditingOffset() && p.node()->isSameNode(c.deepEquivalent().node())) {
437            visPos = c.previous();
438            if (visPos.isNull())
439                return VisiblePosition();
440            visPos = startPositionForLine(visPos);
441        }
442    }
443
444    return c.honorEditableBoundaryAtOrAfter(visPos);
445}
446
447static VisiblePosition endPositionForLine(const VisiblePosition& c)
448{
449    if (c.isNull())
450        return VisiblePosition();
451
452    RootInlineBox *rootBox = rootBoxForLine(c);
453    if (!rootBox) {
454        // There are VisiblePositions at offset 0 in blocks without
455        // RootInlineBoxes, like empty editable blocks and bordered blocks.
456        Position p = c.deepEquivalent();
457        if (p.node()->renderer() && p.node()->renderer()->isRenderBlock() && p.deprecatedEditingOffset() == 0)
458            return c;
459        return VisiblePosition();
460    }
461
462    // Generated content (e.g. list markers and CSS :before and :after
463    // pseudoelements) have no corresponding DOM element, and so cannot be
464    // represented by a VisiblePosition.  Use whatever precedes instead.
465    Node *endNode;
466    InlineBox *endBox = rootBox->lastLeafChild();
467    while (1) {
468        if (!endBox)
469            return VisiblePosition();
470
471        RenderObject *endRenderer = endBox->renderer();
472        if (!endRenderer)
473            return VisiblePosition();
474
475        endNode = endRenderer->node();
476        if (endNode)
477            break;
478
479        endBox = endBox->prevLeafChild();
480    }
481
482    int endOffset = 1;
483    if (endNode->hasTagName(brTag)) {
484        endOffset = 0;
485    } else if (endBox->isInlineTextBox()) {
486        InlineTextBox *endTextBox = static_cast<InlineTextBox *>(endBox);
487        endOffset = endTextBox->start();
488        if (!endTextBox->isLineBreak())
489            endOffset += endTextBox->len();
490    }
491
492    return VisiblePosition(endNode, endOffset, VP_UPSTREAM_IF_POSSIBLE);
493}
494
495VisiblePosition endOfLine(const VisiblePosition& c)
496{
497    VisiblePosition visPos = endPositionForLine(c);
498
499    // Make sure the end of line is at the same line as the given input position.  Else use the previous position to
500    // obtain end of line.  This condition happens when the input position is before the space character at the end
501    // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position
502    // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style
503    // versus lines without that style, which would break before a space by default.
504    if (!inSameLine(c, visPos)) {
505        visPos = c.previous();
506        if (visPos.isNull())
507            return VisiblePosition();
508        visPos = endPositionForLine(visPos);
509    }
510
511    return c.honorEditableBoundaryAtOrBefore(visPos);
512}
513
514bool inSameLine(const VisiblePosition &a, const VisiblePosition &b)
515{
516    return a.isNotNull() && startOfLine(a) == startOfLine(b);
517}
518
519bool isStartOfLine(const VisiblePosition &p)
520{
521    return p.isNotNull() && p == startOfLine(p);
522}
523
524bool isEndOfLine(const VisiblePosition &p)
525{
526    return p.isNotNull() && p == endOfLine(p);
527}
528
529// The first leaf before node that has the same editability as node.
530static Node* previousLeafWithSameEditability(Node* node)
531{
532    bool editable = node->isContentEditable();
533    Node* n = node->previousLeafNode();
534    while (n) {
535        if (editable == n->isContentEditable())
536            return n;
537        n = n->previousLeafNode();
538    }
539    return 0;
540}
541
542static Node* enclosingNodeWithNonInlineRenderer(Node* n)
543{
544    for (Node* p = n; p; p = p->parentNode()) {
545        if (p->renderer() && !p->renderer()->isInline())
546            return p;
547    }
548    return 0;
549}
550
551VisiblePosition previousLinePosition(const VisiblePosition &visiblePosition, int x)
552{
553    Position p = visiblePosition.deepEquivalent();
554    Node *node = p.node();
555    Node* highestRoot = highestEditableRoot(p);
556    if (!node)
557        return VisiblePosition();
558
559    node->document()->updateLayoutIgnorePendingStylesheets();
560
561    RenderObject *renderer = node->renderer();
562    if (!renderer)
563        return VisiblePosition();
564
565    RenderBlock *containingBlock = 0;
566    RootInlineBox *root = 0;
567    InlineBox* box;
568    int ignoredCaretOffset;
569    visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
570    if (box) {
571        root = box->root()->prevRootBox();
572        if (root)
573            containingBlock = renderer->containingBlock();
574    }
575
576    if (!root) {
577        // This containing editable block does not have a previous line.
578        // Need to move back to previous containing editable block in this root editable
579        // block and find the last root line box in that block.
580        Node* startBlock = enclosingNodeWithNonInlineRenderer(node);
581        Node* n = previousLeafWithSameEditability(node);
582        while (n && startBlock == enclosingNodeWithNonInlineRenderer(n))
583            n = previousLeafWithSameEditability(n);
584        while (n) {
585            if (highestEditableRoot(Position(n, 0)) != highestRoot)
586                break;
587            Position pos(n, caretMinOffset(n));
588            if (pos.isCandidate()) {
589                ASSERT(n->renderer());
590                Position maxPos(n, caretMaxOffset(n));
591                maxPos.getInlineBoxAndOffset(DOWNSTREAM, box, ignoredCaretOffset);
592                if (box) {
593                    // previous root line box found
594                    root = box->root();
595                    containingBlock = n->renderer()->containingBlock();
596                    break;
597                }
598
599                return VisiblePosition(pos, DOWNSTREAM);
600            }
601            n = previousLeafWithSameEditability(n);
602        }
603    }
604
605    if (root) {
606        // FIXME: Can be wrong for multi-column layout and with transforms.
607        FloatPoint absPos = containingBlock->localToAbsolute(FloatPoint());
608        if (containingBlock->hasOverflowClip())
609            absPos -= containingBlock->layer()->scrolledContentOffset();
610        RenderObject* renderer = root->closestLeafChildForXPos(x - absPos.x(), isEditablePosition(p))->renderer();
611        Node* node = renderer->node();
612        if (node && editingIgnoresContent(node))
613            return Position(node->parent(), node->nodeIndex());
614        return renderer->positionForPoint(IntPoint(x - absPos.x(), root->lineTop()));
615    }
616
617    // Could not find a previous line. This means we must already be on the first line.
618    // Move to the start of the content in this block, which effectively moves us
619    // to the start of the line we're on.
620    Element* rootElement = node->isContentEditable() ? node->rootEditableElement() : node->document()->documentElement();
621    return VisiblePosition(rootElement, 0, DOWNSTREAM);
622}
623
624static Node* nextLeafWithSameEditability(Node* node, int offset)
625{
626    bool editable = node->isContentEditable();
627    ASSERT(offset >= 0);
628    Node* child = node->childNode(offset);
629    Node* n = child ? child->nextLeafNode() : node->nextLeafNode();
630    while (n) {
631        if (editable == n->isContentEditable())
632            return n;
633        n = n->nextLeafNode();
634    }
635    return 0;
636}
637
638static Node* nextLeafWithSameEditability(Node* node)
639{
640    if (!node)
641        return 0;
642
643    bool editable = node->isContentEditable();
644    Node* n = node->nextLeafNode();
645    while (n) {
646        if (editable == n->isContentEditable())
647            return n;
648        n = n->nextLeafNode();
649    }
650    return 0;
651}
652
653VisiblePosition nextLinePosition(const VisiblePosition &visiblePosition, int x)
654{
655    Position p = visiblePosition.deepEquivalent();
656    Node *node = p.node();
657    Node* highestRoot = highestEditableRoot(p);
658    if (!node)
659        return VisiblePosition();
660
661    node->document()->updateLayoutIgnorePendingStylesheets();
662
663    RenderObject *renderer = node->renderer();
664    if (!renderer)
665        return VisiblePosition();
666
667    RenderBlock *containingBlock = 0;
668    RootInlineBox *root = 0;
669    InlineBox* box;
670    int ignoredCaretOffset;
671    visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
672    if (box) {
673        root = box->root()->nextRootBox();
674        if (root)
675            containingBlock = renderer->containingBlock();
676    }
677
678    if (!root) {
679        // This containing editable block does not have a next line.
680        // Need to move forward to next containing editable block in this root editable
681        // block and find the first root line box in that block.
682        Node* startBlock = enclosingNodeWithNonInlineRenderer(node);
683        Node* n = nextLeafWithSameEditability(node, p.deprecatedEditingOffset());
684        while (n && startBlock == enclosingNodeWithNonInlineRenderer(n))
685            n = nextLeafWithSameEditability(n);
686        while (n) {
687            if (highestEditableRoot(Position(n, 0)) != highestRoot)
688                break;
689            Position pos(n, caretMinOffset(n));
690            if (pos.isCandidate()) {
691                ASSERT(n->renderer());
692                pos.getInlineBoxAndOffset(DOWNSTREAM, box, ignoredCaretOffset);
693                if (box) {
694                    // next root line box found
695                    root = box->root();
696                    containingBlock = n->renderer()->containingBlock();
697                    break;
698                }
699
700                return VisiblePosition(pos, DOWNSTREAM);
701            }
702            n = nextLeafWithSameEditability(n);
703        }
704    }
705
706    if (root) {
707        // FIXME: Can be wrong for multi-column layout and with transforms.
708        FloatPoint absPos = containingBlock->localToAbsolute(FloatPoint());
709        if (containingBlock->hasOverflowClip())
710            absPos -= containingBlock->layer()->scrolledContentOffset();
711        RenderObject* renderer = root->closestLeafChildForXPos(x - absPos.x(), isEditablePosition(p))->renderer();
712        Node* node = renderer->node();
713        if (node && editingIgnoresContent(node))
714            return Position(node->parent(), node->nodeIndex());
715        return renderer->positionForPoint(IntPoint(x - absPos.x(), root->lineTop()));
716    }
717
718    // Could not find a next line. This means we must already be on the last line.
719    // Move to the end of the content in this block, which effectively moves us
720    // to the end of the line we're on.
721    Element* rootElement = node->isContentEditable() ? node->rootEditableElement() : node->document()->documentElement();
722    return VisiblePosition(rootElement, rootElement ? rootElement->childNodeCount() : 0, DOWNSTREAM);
723}
724
725// ---------
726
727static unsigned startSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
728{
729    TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
730    // FIXME: The following function can return -1; we don't handle that.
731    return textBreakPreceding(iterator, length);
732}
733
734VisiblePosition startOfSentence(const VisiblePosition &c)
735{
736    return previousBoundary(c, startSentenceBoundary);
737}
738
739static unsigned endSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
740{
741    TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
742    return textBreakNext(iterator);
743}
744
745// FIXME: This includes the space after the punctuation that marks the end of the sentence.
746VisiblePosition endOfSentence(const VisiblePosition &c)
747{
748    return nextBoundary(c, endSentenceBoundary);
749}
750
751static unsigned previousSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
752{
753    // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
754    TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
755    // FIXME: The following function can return -1; we don't handle that.
756    return textBreakPreceding(iterator, length);
757}
758
759VisiblePosition previousSentencePosition(const VisiblePosition &c)
760{
761    VisiblePosition prev = previousBoundary(c, previousSentencePositionBoundary);
762    return c.honorEditableBoundaryAtOrAfter(prev);
763}
764
765static unsigned nextSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
766{
767    // FIXME: This is identical to endSentenceBoundary.  This isn't right, it needs to
768    // move to the equivlant position in the following sentence.
769    TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
770    return textBreakFollowing(iterator, 0);
771}
772
773VisiblePosition nextSentencePosition(const VisiblePosition &c)
774{
775    VisiblePosition next = nextBoundary(c, nextSentencePositionBoundary);
776    return c.honorEditableBoundaryAtOrBefore(next);
777}
778
779VisiblePosition startOfParagraph(const VisiblePosition& c)
780{
781    Position p = c.deepEquivalent();
782    Node *startNode = p.node();
783
784    if (!startNode)
785        return VisiblePosition();
786
787    if (isRenderedAsNonInlineTableImageOrHR(startNode))
788        return firstDeepEditingPositionForNode(startNode);
789
790    Node* startBlock = enclosingBlock(startNode);
791
792    Node *node = startNode;
793    int offset = p.deprecatedEditingOffset();
794
795    Node *n = startNode;
796    while (n) {
797        if (n->isContentEditable() != startNode->isContentEditable())
798            break;
799        RenderObject *r = n->renderer();
800        if (!r) {
801            n = n->traversePreviousNodePostOrder(startBlock);
802            continue;
803        }
804        RenderStyle *style = r->style();
805        if (style->visibility() != VISIBLE) {
806            n = n->traversePreviousNodePostOrder(startBlock);
807            continue;
808        }
809
810        if (r->isBR() || isBlock(n))
811            break;
812
813        if (r->isText()) {
814            if (style->preserveNewline()) {
815                const UChar* chars = toRenderText(r)->characters();
816                int i = toRenderText(r)->textLength();
817                int o = offset;
818                if (n == startNode && o < i)
819                    i = max(0, o);
820                while (--i >= 0)
821                    if (chars[i] == '\n')
822                        return VisiblePosition(n, i + 1, DOWNSTREAM);
823            }
824            node = n;
825            offset = 0;
826            n = n->traversePreviousNodePostOrder(startBlock);
827        } else if (editingIgnoresContent(n) || isTableElement(n)) {
828            node = n;
829            offset = 0;
830            n = n->previousSibling() ? n->previousSibling() : n->traversePreviousNodePostOrder(startBlock);
831        } else
832            n = n->traversePreviousNodePostOrder(startBlock);
833    }
834
835    return VisiblePosition(node, offset, DOWNSTREAM);
836}
837
838VisiblePosition endOfParagraph(const VisiblePosition &c)
839{
840    if (c.isNull())
841        return VisiblePosition();
842
843    Position p = c.deepEquivalent();
844    Node* startNode = p.node();
845
846    if (isRenderedAsNonInlineTableImageOrHR(startNode))
847        return lastDeepEditingPositionForNode(startNode);
848
849    Node* startBlock = enclosingBlock(startNode);
850    Node *stayInsideBlock = startBlock;
851
852    Node *node = startNode;
853    int offset = p.deprecatedEditingOffset();
854
855    Node *n = startNode;
856    while (n) {
857        if (n->isContentEditable() != startNode->isContentEditable())
858            break;
859        RenderObject *r = n->renderer();
860        if (!r) {
861            n = n->traverseNextNode(stayInsideBlock);
862            continue;
863        }
864        RenderStyle *style = r->style();
865        if (style->visibility() != VISIBLE) {
866            n = n->traverseNextNode(stayInsideBlock);
867            continue;
868        }
869
870        if (r->isBR() || isBlock(n))
871            break;
872
873        // FIXME: We avoid returning a position where the renderer can't accept the caret.
874        // We should probably do this in other cases such as startOfParagraph.
875        if (r->isText() && r->caretMaxRenderedOffset() > 0) {
876            int length = toRenderText(r)->textLength();
877            if (style->preserveNewline()) {
878                const UChar* chars = toRenderText(r)->characters();
879                int o = n == startNode ? offset : 0;
880                for (int i = o; i < length; ++i)
881                    if (chars[i] == '\n')
882                        return VisiblePosition(n, i, DOWNSTREAM);
883            }
884            node = n;
885            offset = r->caretMaxOffset();
886            n = n->traverseNextNode(stayInsideBlock);
887        } else if (editingIgnoresContent(n) || isTableElement(n)) {
888            node = n;
889            offset = lastOffsetForEditing(n);
890            n = n->traverseNextSibling(stayInsideBlock);
891        } else
892            n = n->traverseNextNode(stayInsideBlock);
893    }
894
895    return VisiblePosition(node, offset, DOWNSTREAM);
896}
897
898VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
899{
900    VisiblePosition paragraphEnd(endOfParagraph(visiblePosition));
901    VisiblePosition afterParagraphEnd(paragraphEnd.next(true));
902    // The position after the last position in the last cell of a table
903    // is not the start of the next paragraph.
904    if (isFirstPositionAfterTable(afterParagraphEnd))
905        return afterParagraphEnd.next(true);
906    return afterParagraphEnd;
907}
908
909bool inSameParagraph(const VisiblePosition &a, const VisiblePosition &b)
910{
911    return a.isNotNull() && startOfParagraph(a) == startOfParagraph(b);
912}
913
914bool isStartOfParagraph(const VisiblePosition &pos)
915{
916    return pos.isNotNull() && pos == startOfParagraph(pos);
917}
918
919bool isEndOfParagraph(const VisiblePosition &pos)
920{
921    return pos.isNotNull() && pos == endOfParagraph(pos);
922}
923
924VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
925{
926    VisiblePosition pos = p;
927    do {
928        VisiblePosition n = previousLinePosition(pos, x);
929        if (n.isNull() || n == pos)
930            break;
931        pos = n;
932    } while (inSameParagraph(p, pos));
933    return pos;
934}
935
936VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
937{
938    VisiblePosition pos = p;
939    do {
940        VisiblePosition n = nextLinePosition(pos, x);
941        if (n.isNull() || n == pos)
942            break;
943        pos = n;
944    } while (inSameParagraph(p, pos));
945    return pos;
946}
947
948// ---------
949
950VisiblePosition startOfBlock(const VisiblePosition &c)
951{
952    Position p = c.deepEquivalent();
953    Node *startNode = p.node();
954    if (!startNode)
955        return VisiblePosition();
956    return VisiblePosition(Position(startNode->enclosingBlockFlowElement(), 0), DOWNSTREAM);
957}
958
959VisiblePosition endOfBlock(const VisiblePosition &c)
960{
961    Position p = c.deepEquivalent();
962
963    Node *startNode = p.node();
964    if (!startNode)
965        return VisiblePosition();
966
967    Node *startBlock = startNode->enclosingBlockFlowElement();
968
969    return VisiblePosition(startBlock, startBlock->childNodeCount(), VP_DEFAULT_AFFINITY);
970}
971
972bool inSameBlock(const VisiblePosition &a, const VisiblePosition &b)
973{
974    return !a.isNull() && enclosingBlockFlowElement(a) == enclosingBlockFlowElement(b);
975}
976
977bool isStartOfBlock(const VisiblePosition &pos)
978{
979    return pos.isNotNull() && pos == startOfBlock(pos);
980}
981
982bool isEndOfBlock(const VisiblePosition &pos)
983{
984    return pos.isNotNull() && pos == endOfBlock(pos);
985}
986
987// ---------
988
989VisiblePosition startOfDocument(const Node* node)
990{
991    if (!node)
992        return VisiblePosition();
993
994    return VisiblePosition(node->document()->documentElement(), 0, DOWNSTREAM);
995}
996
997VisiblePosition startOfDocument(const VisiblePosition &c)
998{
999    return startOfDocument(c.deepEquivalent().node());
1000}
1001
1002VisiblePosition endOfDocument(const Node* node)
1003{
1004    if (!node || !node->document())
1005        return VisiblePosition();
1006
1007    Element* doc = node->document()->documentElement();
1008    return VisiblePosition(doc, doc->childNodeCount(), DOWNSTREAM);
1009}
1010
1011VisiblePosition endOfDocument(const VisiblePosition &c)
1012{
1013    return endOfDocument(c.deepEquivalent().node());
1014}
1015
1016bool inSameDocument(const VisiblePosition &a, const VisiblePosition &b)
1017{
1018    Position ap = a.deepEquivalent();
1019    Node *an = ap.node();
1020    if (!an)
1021        return false;
1022    Position bp = b.deepEquivalent();
1023    Node *bn = bp.node();
1024    if (an == bn)
1025        return true;
1026
1027    return an->document() == bn->document();
1028}
1029
1030bool isStartOfDocument(const VisiblePosition &p)
1031{
1032    return p.isNotNull() && p.previous().isNull();
1033}
1034
1035bool isEndOfDocument(const VisiblePosition &p)
1036{
1037    return p.isNotNull() && p.next().isNull();
1038}
1039
1040// ---------
1041
1042VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1043{
1044    Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1045    if (!highestRoot)
1046        return VisiblePosition();
1047
1048    return firstDeepEditingPositionForNode(highestRoot);
1049}
1050
1051VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1052{
1053    Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1054    if (!highestRoot)
1055        return VisiblePosition();
1056
1057    return lastDeepEditingPositionForNode(highestRoot);
1058}
1059
1060static void getLeafBoxesInLogicalOrder(RootInlineBox* rootBox, Vector<InlineBox*>& leafBoxesInLogicalOrder)
1061{
1062    unsigned char minLevel = 128;
1063    unsigned char maxLevel = 0;
1064    unsigned count = 0;
1065    InlineBox* r = rootBox->firstLeafChild();
1066    // First find highest and lowest levels,
1067    // and initialize leafBoxesInLogicalOrder with the leaf boxes in visual order.
1068    while (r) {
1069        if (r->bidiLevel() > maxLevel)
1070            maxLevel = r->bidiLevel();
1071        if (r->bidiLevel() < minLevel)
1072            minLevel = r->bidiLevel();
1073        leafBoxesInLogicalOrder.append(r);
1074        r = r->nextLeafChild();
1075        ++count;
1076    }
1077
1078    if (rootBox->renderer()->style()->visuallyOrdered())
1079        return;
1080    // Reverse of reordering of the line (L2 according to Bidi spec):
1081    // L2. From the highest level found in the text to the lowest odd level on each line,
1082    // reverse any contiguous sequence of characters that are at that level or higher.
1083
1084    // Reversing the reordering of the line is only done up to the lowest odd level.
1085    if (!(minLevel % 2))
1086        minLevel++;
1087
1088    InlineBox** end = leafBoxesInLogicalOrder.end();
1089    while (minLevel <= maxLevel) {
1090        InlineBox** iter = leafBoxesInLogicalOrder.begin();
1091        while (iter != end) {
1092            while (iter != end) {
1093                if ((*iter)->bidiLevel() >= minLevel)
1094                    break;
1095                ++iter;
1096            }
1097            InlineBox** first = iter;
1098            while (iter != end) {
1099                if ((*iter)->bidiLevel() < minLevel)
1100                    break;
1101                ++iter;
1102            }
1103            InlineBox** last = iter;
1104            std::reverse(first, last);
1105        }
1106        ++minLevel;
1107    }
1108}
1109
1110static void getLogicalStartBoxAndNode(RootInlineBox* rootBox, InlineBox*& startBox, Node*& startNode)
1111{
1112    Vector<InlineBox*> leafBoxesInLogicalOrder;
1113    getLeafBoxesInLogicalOrder(rootBox, leafBoxesInLogicalOrder);
1114    startBox = 0;
1115    startNode = 0;
1116    for (size_t i = 0; i < leafBoxesInLogicalOrder.size(); ++i) {
1117        startBox = leafBoxesInLogicalOrder[i];
1118        startNode = startBox->renderer()->node();
1119        if (startNode)
1120            return;
1121    }
1122}
1123
1124static void getLogicalEndBoxAndNode(RootInlineBox* rootBox, InlineBox*& endBox, Node*& endNode)
1125{
1126    Vector<InlineBox*> leafBoxesInLogicalOrder;
1127    getLeafBoxesInLogicalOrder(rootBox, leafBoxesInLogicalOrder);
1128    endBox = 0;
1129    endNode = 0;
1130    // Generated content (e.g. list markers and CSS :before and :after
1131    // pseudoelements) have no corresponding DOM element, and so cannot be
1132    // represented by a VisiblePosition.  Use whatever precedes instead.
1133    for (size_t i = leafBoxesInLogicalOrder.size(); i > 0; --i) {
1134        endBox = leafBoxesInLogicalOrder[i - 1];
1135        endNode = endBox->renderer()->node();
1136        if (endNode)
1137            return;
1138    }
1139}
1140
1141static VisiblePosition logicalStartPositionForLine(const VisiblePosition& c)
1142{
1143    if (c.isNull())
1144        return VisiblePosition();
1145
1146    RootInlineBox* rootBox = rootBoxForLine(c);
1147    if (!rootBox) {
1148        // There are VisiblePositions at offset 0 in blocks without
1149        // RootInlineBoxes, like empty editable blocks and bordered blocks.
1150        Position p = c.deepEquivalent();
1151        if (p.node()->renderer() && p.node()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
1152            return positionAvoidingFirstPositionInTable(c);
1153
1154        return VisiblePosition();
1155    }
1156
1157    InlineBox* logicalStartBox;
1158    Node* logicalStartNode;
1159    getLogicalStartBoxAndNode(rootBox, logicalStartBox, logicalStartNode);
1160
1161    if (!logicalStartNode)
1162        return VisiblePosition();
1163
1164    int startOffset = logicalStartBox->caretMinOffset();
1165
1166    VisiblePosition visPos = VisiblePosition(logicalStartNode, startOffset, DOWNSTREAM);
1167    return positionAvoidingFirstPositionInTable(visPos);
1168}
1169
1170VisiblePosition logicalStartOfLine(const VisiblePosition& c)
1171{
1172    VisiblePosition visPos = logicalStartPositionForLine(c);
1173
1174    return c.honorEditableBoundaryAtOrAfter(visPos);
1175}
1176
1177static VisiblePosition logicalEndPositionForLine(const VisiblePosition& c)
1178{
1179    if (c.isNull())
1180        return VisiblePosition();
1181
1182    RootInlineBox* rootBox = rootBoxForLine(c);
1183    if (!rootBox) {
1184        // There are VisiblePositions at offset 0 in blocks without
1185        // RootInlineBoxes, like empty editable blocks and bordered blocks.
1186        Position p = c.deepEquivalent();
1187        if (p.node()->renderer() && p.node()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
1188            return c;
1189        return VisiblePosition();
1190    }
1191
1192    InlineBox* logicalEndBox;
1193    Node* logicalEndNode;
1194    getLogicalEndBoxAndNode(rootBox, logicalEndBox, logicalEndNode);
1195    if (!logicalEndNode)
1196        return VisiblePosition();
1197
1198    int endOffset = 1;
1199    if (logicalEndNode->hasTagName(brTag))
1200        endOffset = 0;
1201    else if (logicalEndBox->isInlineTextBox()) {
1202        InlineTextBox* endTextBox = static_cast<InlineTextBox*>(logicalEndBox);
1203        endOffset = endTextBox->start();
1204        if (!endTextBox->isLineBreak())
1205            endOffset += endTextBox->len();
1206    }
1207
1208    return VisiblePosition(logicalEndNode, endOffset, VP_UPSTREAM_IF_POSSIBLE);
1209}
1210
1211bool inSameLogicalLine(const VisiblePosition& a, const VisiblePosition& b)
1212{
1213    return a.isNotNull() && logicalStartOfLine(a) == logicalStartOfLine(b);
1214}
1215
1216VisiblePosition logicalEndOfLine(const VisiblePosition& c)
1217{
1218    VisiblePosition visPos = logicalEndPositionForLine(c);
1219
1220    // Make sure the end of line is at the same line as the given input position. For a wrapping line, the logical end
1221    // position for the not-last-2-lines might incorrectly hand back the logical beginning of the next line.
1222    // For example, <div contenteditable dir="rtl" style="line-break:before-white-space">abcdefg abcdefg abcdefg
1223    // a abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg </div>
1224    // In this case, use the previous position of the computed logical end position.
1225    if (!inSameLogicalLine(c, visPos))
1226        visPos = visPos.previous();
1227
1228    return c.honorEditableBoundaryAtOrBefore(visPos);
1229}
1230
1231}
1232