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