008c05f74d7deb03d992743fb98879a3d825445a
[WebKit-https.git] / WebCore / editing / visible_units.cpp
1 /*
2  * Copyright (C) 2004 Apple Computer, 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 "htmlediting.h"
38
39 namespace WebCore {
40
41 using namespace HTMLNames;
42
43 static VisiblePosition previousBoundary(const VisiblePosition &c, unsigned (*searchFunction)(const UChar *, unsigned))
44 {
45     Position pos = c.deepEquivalent();
46     Node *n = pos.node();
47     if (!n)
48         return VisiblePosition();
49     Document *d = n->document();
50     Node *de = d->documentElement();
51     if (!de)
52         return VisiblePosition();
53     Node *boundary = n->enclosingBlockFlowElement();
54     if (!boundary)
55         return VisiblePosition();
56     bool isContentEditable = boundary->isContentEditable();
57     while (boundary && boundary != de && boundary->parentNode() && isContentEditable == boundary->parentNode()->isContentEditable())
58         boundary = boundary->parentNode();
59
60     Position start = rangeCompliantEquivalent(Position(boundary, 0));
61     Position end = rangeCompliantEquivalent(pos);
62     RefPtr<Range> searchRange = new Range(d);
63     
64     int exception = 0;
65     searchRange->setStart(start.node(), start.offset(), exception);
66     searchRange->setEnd(end.node(), end.offset(), exception);
67     
68     ASSERT(!exception);
69     if (exception)
70         return VisiblePosition();
71         
72     SimplifiedBackwardsTextIterator it(searchRange.get());
73     Vector<UChar, 1024> string;
74     unsigned next = 0;
75     bool inTextSecurityMode = start.node() && start.node()->renderer() && start.node()->renderer()->style()->textSecurity() != TSNONE;
76     while (!it.atEnd()) {
77         // iterate to get chunks until the searchFunction returns a non-zero value.
78         if (!inTextSecurityMode) 
79             string.prepend(it.characters(), it.length());
80         else {
81             // Treat bullets used in the text security mode as regular characters when looking for boundaries
82             String iteratorString(it.characters(), it.length());
83             iteratorString = iteratorString.impl()->secure('x');
84             string.prepend(iteratorString.characters(), iteratorString.length());
85         }
86         
87         next = searchFunction(string.data(), string.size());
88         if (next != 0)
89             break;
90         it.advance();
91     }
92     
93     if (it.atEnd() && next == 0) {
94         pos = it.range()->startPosition();
95     } else if (next != 0) {
96         Node *node = it.range()->startContainer(exception);
97         if (node->isTextNode() || (node->renderer() && node->renderer()->isBR()))
98             // The next variable contains a usable index into a text node
99             pos = Position(node, next);
100         else {
101             // Use the end of the found range, the start is not guaranteed to
102             // be correct.
103             Position end = it.range()->endPosition();
104             VisiblePosition boundary(end);
105             unsigned i = it.length() - next;
106             while (i--)
107                 boundary = boundary.previous();
108             return boundary;
109         }
110     }
111
112     return VisiblePosition(pos, DOWNSTREAM);
113 }
114
115 static VisiblePosition nextBoundary(const VisiblePosition &c, unsigned (*searchFunction)(const UChar *, unsigned))
116 {
117     Position pos = c.deepEquivalent();
118     Node *n = pos.node();
119     if (!n)
120         return VisiblePosition();
121     Document *d = n->document();
122     Node *de = d->documentElement();
123     if (!de)
124         return VisiblePosition();
125     Node *boundary = n->enclosingBlockFlowElement();
126     if (!boundary)
127         return VisiblePosition();
128     bool isContentEditable = boundary->isContentEditable();
129     while (boundary && boundary != de && boundary->parentNode() && isContentEditable == boundary->parentNode()->isContentEditable())
130         boundary = boundary->parentNode();
131
132     RefPtr<Range> searchRange(d->createRange());
133     Position start(rangeCompliantEquivalent(pos));
134     ExceptionCode ec = 0;
135     searchRange->selectNodeContents(boundary, ec);
136     searchRange->setStart(start.node(), start.offset(), ec);
137     TextIterator it(searchRange.get(), true);
138     Vector<UChar, 1024> string;
139     unsigned next = 0;
140     bool inTextSecurityMode = start.node() && start.node()->renderer() && start.node()->renderer()->style()->textSecurity() != TSNONE;
141     while (!it.atEnd()) {
142         // Keep asking the iterator for chunks until the search function
143         // returns an end value not equal to the length of the string passed to it.
144         if (!inTextSecurityMode)
145             string.append(it.characters(), it.length());
146         else {
147             // Treat bullets used in the text security mode as regular characters when looking for boundaries
148             String iteratorString(it.characters(), it.length());
149             iteratorString = iteratorString.impl()->secure('x');
150             string.append(iteratorString.characters(), iteratorString.length());
151         }
152
153         next = searchFunction(string.data(), string.size());
154         if (next != string.size())
155             break;
156         it.advance();
157     }
158     
159     if (it.atEnd() && next == string.size()) {
160         pos = it.range()->startPosition();
161     } else if (next != 0) {
162         // Use the character iterator to translate the next value into a DOM position.
163         CharacterIterator charIt(searchRange.get(), true);
164         charIt.advance(next - 1);
165         pos = charIt.range()->endPosition();
166         
167         // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)
168         VisiblePosition visPos = VisiblePosition(pos);
169         if (visPos == VisiblePosition(charIt.range()->startPosition()))
170             pos = visPos.next(true).deepEquivalent();
171     }
172
173     // generate VisiblePosition, use UPSTREAM affinity if possible
174     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
175 }
176
177 // ---------
178
179 static unsigned startWordBoundary(const UChar* characters, unsigned length)
180 {
181     int start, end;
182     findWordBoundary(characters, length, length, &start, &end);
183     return start;
184 }
185
186 VisiblePosition startOfWord(const VisiblePosition &c, EWordSide side)
187 {
188     // FIXME: This returns a null VP for c at the start of the document
189     // and side == LeftWordIfOnBoundary
190     VisiblePosition p = c;
191     if (side == RightWordIfOnBoundary) {
192         // at paragraph end, the startofWord is the current position
193         if (isEndOfParagraph(c))
194             return c;
195         
196         p = c.next();
197         if (p.isNull())
198             return c;
199     }
200     return previousBoundary(p, startWordBoundary);
201 }
202
203 static unsigned endWordBoundary(const UChar* characters, unsigned length)
204 {
205     int start, end;
206     findWordBoundary(characters, length, 0, &start, &end);
207     return end;
208 }
209
210 VisiblePosition endOfWord(const VisiblePosition &c, EWordSide side)
211 {
212     VisiblePosition p = c;
213     if (side == LeftWordIfOnBoundary) {
214         if (isStartOfParagraph(c))
215             return c;
216             
217         p = c.previous();
218         if (p.isNull())
219             return c;
220     } else {
221         // at paragraph end, the endOfWord is the start of next paragraph
222         if (isEndOfParagraph(c)) {
223             p = c.next();
224             return p.isNotNull() ? p : c;
225         }
226     }
227     
228     return nextBoundary(p, endWordBoundary);
229 }
230
231 static unsigned previousWordPositionBoundary(const UChar* characters, unsigned length)
232 {
233     return findNextWordFromIndex(characters, length, length, false);
234 }
235
236 VisiblePosition previousWordPosition(const VisiblePosition &c)
237 {
238     VisiblePosition prev = previousBoundary(c, previousWordPositionBoundary);
239     return c.firstEditablePositionAtOrAfter(prev);
240 }
241
242 static unsigned nextWordPositionBoundary(const UChar* characters, unsigned length)
243 {
244     return findNextWordFromIndex(characters, length, 0, true);
245 }
246
247 VisiblePosition nextWordPosition(const VisiblePosition &c)
248 {
249     VisiblePosition next = nextBoundary(c, nextWordPositionBoundary);    
250     return c.lastEditablePositionAtOrBefore(next);
251 }
252
253 // ---------
254
255 static RootInlineBox *rootBoxForLine(const VisiblePosition &c)
256 {
257     Position p = c.deepEquivalent();
258     Node *node = p.node();
259     if (!node)
260         return 0;
261
262     RenderObject *renderer = node->renderer();
263     if (!renderer)
264         return 0;
265     
266     InlineBox *box = renderer->inlineBox(p.offset(), c.affinity());
267     if (!box)
268         return 0;
269     
270     return box->root();
271 }
272
273
274 static VisiblePosition startPositionForLine(const VisiblePosition& c)
275 {
276     if (c.isNull())
277         return VisiblePosition();
278         
279     RootInlineBox *rootBox = rootBoxForLine(c);
280     if (!rootBox) {
281         // There are VisiblePositions at offset 0 in blocks without
282         // RootInlineBoxes, like empty editable blocks and bordered blocks.
283         Position p = c.deepEquivalent();
284         if (p.node()->renderer() && p.node()->renderer()->isRenderBlock() && p.offset() == 0)
285             return c;
286         return VisiblePosition();
287     }
288     
289     // Generated content (e.g. list markers and CSS :before and :after
290     // pseudoelements) have no corresponding DOM element, and so cannot be
291     // represented by a VisiblePosition.  Use whatever follows instead.
292     InlineBox *startBox = rootBox->firstLeafChild();
293     Node *startNode;
294     while (1) {
295         if (!startBox)
296             return VisiblePosition();
297
298         RenderObject *startRenderer = startBox->object();
299         if (!startRenderer)
300             return VisiblePosition();
301
302         startNode = startRenderer->element();
303         if (startNode)
304             break;
305         
306         startBox = startBox->nextLeafChild();
307     }
308     
309     int startOffset = 0;
310     if (startBox->isInlineTextBox()) {
311         InlineTextBox *startTextBox = static_cast<InlineTextBox *>(startBox);
312         startOffset = startTextBox->m_start;
313     }
314   
315     VisiblePosition visPos = VisiblePosition(startNode, startOffset, DOWNSTREAM);
316
317     // return table offset 0 instead of the first VisiblePosition inside the table
318     VisiblePosition visPrevious = visPos.previous();
319     if (isLastPositionBeforeTable(visPrevious))
320         visPos = visPrevious;
321
322     return visPos;
323 }
324
325 VisiblePosition startOfLine(const VisiblePosition& c)
326 {
327     VisiblePosition visPos = startPositionForLine(c);
328     
329     if (visPos.isNotNull()) {
330         // Make sure the start of line is not greater than the given input position.  Else use the previous position to 
331         // obtain start of line.  This condition happens when the input position is before the space character at the end 
332         // of a soft-wrapped non-editable line. In this scenario, startPositionForLine would incorrectly hand back a position
333         // greater than the input position.  This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space 
334         // style versus lines without that style, which would break before a space by default. 
335         Position p = visPos.deepEquivalent();
336         if (p.offset() > c.deepEquivalent().offset() && p.node()->isSameNode(c.deepEquivalent().node())) {
337             visPos = c.previous();
338             if (visPos.isNull())
339                 return VisiblePosition();
340             visPos = startPositionForLine(visPos);
341         }
342     }
343
344     return c.firstEditablePositionAtOrAfter(visPos);
345 }
346
347 static VisiblePosition endPositionForLine(const VisiblePosition& c)
348 {
349     if (c.isNull())
350         return VisiblePosition();
351         
352     RootInlineBox *rootBox = rootBoxForLine(c);
353     if (!rootBox) {
354         // There are VisiblePositions at offset 0 in blocks without
355         // RootInlineBoxes, like empty editable blocks and bordered blocks.
356         Position p = c.deepEquivalent();
357         if (p.node()->renderer() && p.node()->renderer()->isRenderBlock() && p.offset() == 0)
358             return c;
359         return VisiblePosition();
360     }
361     
362     // Generated content (e.g. list markers and CSS :before and :after
363     // pseudoelements) have no corresponding DOM element, and so cannot be
364     // represented by a VisiblePosition.  Use whatever precedes instead.
365     Node *endNode;
366     InlineBox *endBox = rootBox->lastLeafChild();
367     while (1) {
368         if (!endBox)
369             return VisiblePosition();
370
371         RenderObject *endRenderer = endBox->object();
372         if (!endRenderer)
373             return VisiblePosition();
374
375         endNode = endRenderer->element();
376         if (endNode)
377             break;
378         
379         endBox = endBox->prevLeafChild();
380     }
381     
382     int endOffset = 1;
383     if (endNode->hasTagName(brTag)) {
384         endOffset = 0;
385     } else if (endBox->isInlineTextBox()) {
386         InlineTextBox *endTextBox = static_cast<InlineTextBox *>(endBox);
387         endOffset = endTextBox->m_start;
388         if (!endTextBox->isLineBreak())
389             endOffset += endTextBox->m_len;
390     }
391     
392     return VisiblePosition(endNode, endOffset, VP_UPSTREAM_IF_POSSIBLE);
393 }
394
395 VisiblePosition endOfLine(const VisiblePosition& c)
396 {
397     VisiblePosition visPos = endPositionForLine(c);
398     
399     // Make sure the end of line is at the same line as the given input position.  Else use the previous position to 
400     // obtain end of line.  This condition happens when the input position is before the space character at the end 
401     // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position
402     // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style
403     // versus lines without that style, which would break before a space by default. 
404     if (!inSameLine(c, visPos)) {
405         visPos = c.previous();
406         if (visPos.isNull())
407             return VisiblePosition();
408         visPos = endPositionForLine(visPos);
409     }
410     
411     return c.lastEditablePositionAtOrBefore(visPos);
412 }
413
414 bool inSameLine(const VisiblePosition &a, const VisiblePosition &b)
415 {
416     return a.isNotNull() && startOfLine(a) == startOfLine(b);
417 }
418
419 bool isStartOfLine(const VisiblePosition &p)
420 {
421     return p.isNotNull() && p == startOfLine(p);
422 }
423
424 bool isEndOfLine(const VisiblePosition &p)
425 {
426     return p.isNotNull() && p == endOfLine(p);
427 }
428
429 VisiblePosition previousLinePosition(const VisiblePosition &visiblePosition, int x)
430 {
431     Position p = visiblePosition.deepEquivalent();
432     Node *node = p.node();
433     Node* highestRoot = highestEditableRoot(p);
434     if (!node)
435         return VisiblePosition();
436     
437     node->document()->updateLayoutIgnorePendingStylesheets();
438     
439     RenderObject *renderer = node->renderer();
440     if (!renderer)
441         return VisiblePosition();
442
443     RenderBlock *containingBlock = 0;
444     RootInlineBox *root = 0;
445     InlineBox *box = renderer->inlineBox(p.offset(), visiblePosition.affinity());
446     if (box) {
447         root = box->root()->prevRootBox();
448         if (root)
449             containingBlock = renderer->containingBlock();
450     }
451
452     if (!root) {
453         // This containing editable block does not have a previous line.
454         // Need to move back to previous containing editable block in this root editable
455         // block and find the last root line box in that block.
456         Node* startBlock = enclosingBlock(node);
457         Node *n = node->previousEditable();
458         while (n && startBlock == enclosingBlock(n))
459             n = n->previousEditable();
460         while (n) {
461             if (highestEditableRoot(Position(n, 0)) != highestRoot)
462                 break;
463             Position pos(n, n->caretMinOffset());
464             if (pos.isCandidate()) {
465                 ASSERT(n->renderer());
466                 box = n->renderer()->inlineBox(n->caretMaxOffset());
467                 if (box) {
468                     // previous root line box found
469                     root = box->root();
470                     containingBlock = n->renderer()->containingBlock();
471                     break;
472                 }
473
474                 return VisiblePosition(pos, DOWNSTREAM);
475             }
476             n = n->previousEditable();
477         }
478     }
479     
480     if (root) {
481         // FIXME: Can be wrong for multi-column layout.
482         int absx, absy;
483         containingBlock->absolutePositionForContent(absx, absy);
484         if (containingBlock->hasOverflowClip())
485             containingBlock->layer()->subtractScrollOffset(absx, absy);
486         RenderObject *renderer = root->closestLeafChildForXPos(x - absx, isEditablePosition(p))->object();
487         Node* node = renderer->element();
488         if (editingIgnoresContent(node))
489             return Position(node->parent(), node->nodeIndex());
490         return renderer->positionForCoordinates(x - absx, root->topOverflow());
491     }
492     
493     // Could not find a previous line. This means we must already be on the first line.
494     // Move to the start of the content in this block, which effectively moves us
495     // to the start of the line we're on.
496     return VisiblePosition(node->rootEditableElement(), 0, DOWNSTREAM);
497 }
498
499 VisiblePosition nextLinePosition(const VisiblePosition &visiblePosition, int x)
500 {
501     Position p = visiblePosition.deepEquivalent();
502     Node *node = p.node();
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 = renderer->inlineBox(p.offset(), visiblePosition.affinity());
516     if (box) {
517         root = box->root()->nextRootBox();
518         if (root)
519             containingBlock = renderer->containingBlock();
520     }
521
522     if (!root) {
523         // This containing editable block does not have a next line.
524         // Need to move forward to next containing editable block in this root editable
525         // block and find the first root line box in that block.
526         Node* startBlock = enclosingBlock(node);
527         Node *n = node->nextEditable(p.offset());
528         while (n && startBlock == enclosingBlock(n))
529             n = n->nextEditable();
530         while (n) {
531             if (highestEditableRoot(Position(n, 0)) != highestRoot)
532                 break;
533             Position pos(n, n->caretMinOffset());
534             if (pos.isCandidate()) {
535                 ASSERT(n->renderer());
536                 box = n->renderer()->inlineBox(n->caretMinOffset());
537                 if (box) {
538                     // next root line box found
539                     root = box->root();
540                     containingBlock = n->renderer()->containingBlock();
541                     break;
542                 }
543
544                 return VisiblePosition(pos, DOWNSTREAM);
545             }
546             n = n->nextEditable();
547         }
548     }
549     
550     if (root) {
551         // FIXME: Can be wrong for multi-column layout.
552         int absx, absy;
553         containingBlock->absolutePositionForContent(absx, absy);
554         if (containingBlock->hasOverflowClip())
555             containingBlock->layer()->subtractScrollOffset(absx, absy);
556         RenderObject *renderer = root->closestLeafChildForXPos(x - absx, isEditablePosition(p))->object();
557         Node* node = renderer->element();
558         if (editingIgnoresContent(node))
559             return Position(node->parent(), node->nodeIndex());
560         return renderer->positionForCoordinates(x - absx, root->topOverflow());
561     }    
562
563     // Could not find a next line. This means we must already be on the last line.
564     // Move to the end of the content in this block, which effectively moves us
565     // to the end of the line we're on.
566     Element *rootElement = node->rootEditableElement();
567     return VisiblePosition(rootElement, rootElement ? rootElement->childNodeCount() : 0, DOWNSTREAM);
568 }
569
570 // ---------
571
572 static unsigned startSentenceBoundary(const UChar* characters, unsigned length)
573 {
574     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
575     // FIXME: The following function can return -1; we don't handle that.
576     return textBreakPreceding(iterator, length);
577 }
578
579 VisiblePosition startOfSentence(const VisiblePosition &c)
580 {
581     return previousBoundary(c, startSentenceBoundary);
582 }
583
584 static unsigned endSentenceBoundary(const UChar* characters, unsigned length)
585 {
586     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
587     return textBreakNext(iterator);
588 }
589
590 // FIXME: This includes the space after the punctuation that marks the end of the sentence.
591 VisiblePosition endOfSentence(const VisiblePosition &c)
592 {
593     return nextBoundary(c, endSentenceBoundary);
594 }
595
596 static unsigned previousSentencePositionBoundary(const UChar* characters, unsigned length)
597 {
598     // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
599     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
600     // FIXME: The following function can return -1; we don't handle that.
601     return textBreakPreceding(iterator, length);
602 }
603
604 VisiblePosition previousSentencePosition(const VisiblePosition &c)
605 {
606     VisiblePosition prev = previousBoundary(c, previousSentencePositionBoundary);
607     return c.firstEditablePositionAtOrAfter(prev);
608 }
609
610 static unsigned nextSentencePositionBoundary(const UChar* characters, unsigned length)
611 {
612     // FIXME: This is identical to endSentenceBoundary.  This isn't right, it needs to 
613     // move to the equivlant position in the following sentence.
614     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
615     return textBreakFollowing(iterator, 0);
616 }
617
618 VisiblePosition nextSentencePosition(const VisiblePosition &c)
619 {
620     VisiblePosition next = nextBoundary(c, nextSentencePositionBoundary);    
621     return c.lastEditablePositionAtOrBefore(next);
622 }
623
624 // FIXME: Broken for positions before/after images that aren't inline (5027702)
625 VisiblePosition startOfParagraph(const VisiblePosition &c)
626 {
627     Position p = c.deepEquivalent();
628     Node *startNode = p.node();
629
630     if (!startNode)
631         return VisiblePosition();
632     
633     if (startNode->renderer()
634         && ((startNode->renderer()->isTable() && !startNode->renderer()->isInline())
635             || startNode->renderer()->isHR())
636         && p.offset() == maxDeepOffset(startNode))
637         return VisiblePosition(Position(startNode, 0));
638
639     Node* startBlock = enclosingBlock(startNode);
640
641     Node *node = startNode;
642     int offset = p.offset();
643
644     Node *n = startNode;
645     while (n) {
646         if (n->isContentEditable() != startNode->isContentEditable())
647             break;
648         RenderObject *r = n->renderer();
649         if (!r) {
650             n = n->traversePreviousNodePostOrder(startBlock);
651             continue;
652         }
653         RenderStyle *style = r->style();
654         if (style->visibility() != VISIBLE) {
655             n = n->traversePreviousNodePostOrder(startBlock);
656             continue;
657         }
658         
659         if (r->isBR() || isBlock(n))
660             break;
661             
662         if (r->isText()) {
663             if (style->preserveNewline()) {
664                 const UChar* chars = static_cast<RenderText*>(r)->characters();
665                 int i = static_cast<RenderText*>(r)->textLength();
666                 int o = offset;
667                 if (n == startNode && o < i)
668                     i = max(0, o);
669                 while (--i >= 0)
670                     if (chars[i] == '\n')
671                         return VisiblePosition(n, i + 1, DOWNSTREAM);
672             }
673             node = n;
674             offset = 0;
675             n = n->traversePreviousNodePostOrder(startBlock);
676         } else if (editingIgnoresContent(n) || isTableElement(n)) {
677             node = n;
678             offset = 0;
679             n = n->previousSibling() ? n->previousSibling() : n->traversePreviousNodePostOrder(startBlock);
680         } else
681             n = n->traversePreviousNodePostOrder(startBlock);
682     }
683
684     return VisiblePosition(node, offset, DOWNSTREAM);
685 }
686
687 // FIXME: Broken for positions before/after images that aren't inline (5027702)
688 VisiblePosition endOfParagraph(const VisiblePosition &c)
689 {    
690     if (c.isNull())
691         return VisiblePosition();
692
693     Position p = c.deepEquivalent();
694     Node* startNode = p.node();
695
696     if (startNode->renderer()
697         && ((startNode->renderer()->isTable() && !startNode->renderer()->isInline())
698             || startNode->renderer()->isHR())
699         && p.offset() == 0)
700         return VisiblePosition(Position(startNode, maxDeepOffset(startNode)));
701     
702     Node* startBlock = enclosingBlock(startNode);
703     Node *stayInsideBlock = startBlock;
704     
705     Node *node = startNode;
706     int offset = p.offset();
707
708     Node *n = startNode;
709     while (n) {
710         if (n->isContentEditable() != startNode->isContentEditable())
711             break;
712         RenderObject *r = n->renderer();
713         if (!r) {
714             n = n->traverseNextNode(stayInsideBlock);
715             continue;
716         }
717         RenderStyle *style = r->style();
718         if (style->visibility() != VISIBLE) {
719             n = n->traverseNextNode(stayInsideBlock);
720             continue;
721         }
722         
723         if (r->isBR() || isBlock(n))
724             break;
725             
726         // FIXME: We avoid returning a position where the renderer can't accept the caret.
727         // We should probably do this in other cases such as startOfParagraph.
728         if (r->isText() && r->caretMaxRenderedOffset() > 0) {
729             int length = static_cast<RenderText*>(r)->textLength();
730             if (style->preserveNewline()) {
731                 const UChar* chars = static_cast<RenderText*>(r)->characters();
732                 int o = n == startNode ? offset : 0;
733                 for (int i = o; i < length; ++i)
734                     if (chars[i] == '\n')
735                         return VisiblePosition(n, i, DOWNSTREAM);
736             }
737             node = n;
738             offset = r->caretMaxOffset();
739             n = n->traverseNextNode(stayInsideBlock);
740         } else if (editingIgnoresContent(n) || isTableElement(n)) {
741             node = n;
742             offset = maxDeepOffset(n);
743             n = n->traverseNextSibling(stayInsideBlock);
744         } else
745             n = n->traverseNextNode(stayInsideBlock);
746     }
747
748     return VisiblePosition(node, offset, DOWNSTREAM);
749 }
750
751 bool inSameParagraph(const VisiblePosition &a, const VisiblePosition &b)
752 {
753     return a.isNotNull() && startOfParagraph(a) == startOfParagraph(b);
754 }
755
756 bool isStartOfParagraph(const VisiblePosition &pos)
757 {
758     return pos.isNotNull() && pos == startOfParagraph(pos);
759 }
760
761 bool isEndOfParagraph(const VisiblePosition &pos)
762 {
763     return pos.isNotNull() && pos == endOfParagraph(pos);
764 }
765
766 VisiblePosition previousParagraphPosition(const VisiblePosition &p, int x)
767 {
768     VisiblePosition pos = p;
769     do {
770         VisiblePosition n = previousLinePosition(pos, x);
771         if (n.isNull() || n == pos)
772             return p;
773         pos = n;
774     } while (inSameParagraph(p, pos));
775     return pos;
776 }
777
778 VisiblePosition nextParagraphPosition(const VisiblePosition &p, int x)
779 {
780     VisiblePosition pos = p;
781     do {
782         VisiblePosition n = nextLinePosition(pos, x);
783         if (n.isNull() || n == pos)
784             return p;
785         pos = n;
786     } while (inSameParagraph(p, pos));
787     return pos;
788 }
789
790 // ---------
791
792 VisiblePosition startOfBlock(const VisiblePosition &c)
793 {
794     Position p = c.deepEquivalent();
795     Node *startNode = p.node();
796     if (!startNode)
797         return VisiblePosition();
798     return VisiblePosition(Position(startNode->enclosingBlockFlowElement(), 0), DOWNSTREAM);
799 }
800
801 VisiblePosition endOfBlock(const VisiblePosition &c)
802 {
803     Position p = c.deepEquivalent();
804
805     Node *startNode = p.node();
806     if (!startNode)
807         return VisiblePosition();
808
809     Node *startBlock = startNode->enclosingBlockFlowElement();
810     
811     return VisiblePosition(startBlock, startBlock->childNodeCount(), VP_DEFAULT_AFFINITY);   
812 }
813
814 bool inSameBlock(const VisiblePosition &a, const VisiblePosition &b)
815 {
816     return !a.isNull() && enclosingBlockFlowElement(a) == enclosingBlockFlowElement(b);
817 }
818
819 bool isStartOfBlock(const VisiblePosition &pos)
820 {
821     return pos.isNotNull() && pos == startOfBlock(pos);
822 }
823
824 bool isEndOfBlock(const VisiblePosition &pos)
825 {
826     return pos.isNotNull() && pos == endOfBlock(pos);
827 }
828
829 // ---------
830
831 VisiblePosition startOfDocument(const Node* node)
832 {
833     if (!node)
834         return VisiblePosition();
835     
836     return VisiblePosition(node->document()->documentElement(), 0, DOWNSTREAM);
837 }
838
839 VisiblePosition startOfDocument(const VisiblePosition &c)
840 {
841     return startOfDocument(c.deepEquivalent().node());
842 }
843
844 VisiblePosition endOfDocument(const Node* node)
845 {
846     if (!node || !node->document())
847         return VisiblePosition();
848     
849     Element* doc = node->document()->documentElement();
850     return VisiblePosition(doc, doc->childNodeCount(), DOWNSTREAM);
851 }
852
853 VisiblePosition endOfDocument(const VisiblePosition &c)
854 {
855     return endOfDocument(c.deepEquivalent().node());
856 }
857
858 bool inSameDocument(const VisiblePosition &a, const VisiblePosition &b)
859 {
860     Position ap = a.deepEquivalent();
861     Node *an = ap.node();
862     if (!an)
863         return false;
864     Position bp = b.deepEquivalent();
865     Node *bn = bp.node();
866     if (an == bn)
867         return true;
868
869     return an->document() == bn->document();
870 }
871
872 bool isStartOfDocument(const VisiblePosition &p)
873 {
874     return p.isNotNull() && p.previous().isNull();
875 }
876
877 bool isEndOfDocument(const VisiblePosition &p)
878 {
879     return p.isNotNull() && p.next().isNull();
880 }
881
882 // ---------
883
884 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
885 {
886     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
887     if (!highestRoot)
888         return VisiblePosition();
889
890     return VisiblePosition(highestRoot, 0, DOWNSTREAM);
891 }
892
893 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
894 {
895     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
896     if (!highestRoot)
897         return VisiblePosition();
898
899     return VisiblePosition(highestRoot, maxDeepOffset(highestRoot), DOWNSTREAM);
900 }
901
902 }