WebCore:
[WebKit-https.git] / 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 "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
41 namespace WebCore {
42
43 using namespace HTMLNames;
44 using namespace WTF::Unicode;
45
46 static 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
58 static 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
70 enum BoundarySearchContextAvailability { DontHaveMoreContext, MayHaveMoreContext };
71
72 typedef unsigned (*BoundarySearchFunction)(const UChar*, unsigned length, unsigned offset, BoundarySearchContextAvailability, bool& needMoreContext);
73
74 static 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.m_offset, 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.m_offset, ec);
117     searchRange->setEnd(end.node(), end.m_offset, 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
167 static 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.m_offset, 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.m_offset, 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
258 static 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
271 VisiblePosition 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
288 static 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
301 VisiblePosition 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
317 static 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
327 VisiblePosition previousWordPosition(const VisiblePosition &c)
328 {
329     VisiblePosition prev = previousBoundary(c, previousWordPositionBoundary);
330     return c.honorEditableBoundaryAtOrAfter(prev);
331 }
332
333 static 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
343 VisiblePosition nextWordPosition(const VisiblePosition &c)
344 {
345     VisiblePosition next = nextBoundary(c, nextWordPositionBoundary);    
346     return c.honorEditableBoundaryAtOrBefore(next);
347 }
348
349 // ---------
350
351 static 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
369 static 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
379 static 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.m_offset == 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
425 VisiblePosition 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.m_offset > c.deepEquivalent().m_offset && 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
447 static 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.m_offset == 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
495 VisiblePosition 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
514 bool inSameLine(const VisiblePosition &a, const VisiblePosition &b)
515 {
516     return a.isNotNull() && startOfLine(a) == startOfLine(b);
517 }
518
519 bool isStartOfLine(const VisiblePosition &p)
520 {
521     return p.isNotNull() && p == startOfLine(p);
522 }
523
524 bool 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.
530 static 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
542 VisiblePosition previousLinePosition(const VisiblePosition &visiblePosition, int x)
543 {
544     Position p = visiblePosition.deepEquivalent();
545     Node *node = p.node();
546     Node* highestRoot = highestEditableRoot(p);
547     if (!node)
548         return VisiblePosition();
549     
550     node->document()->updateLayoutIgnorePendingStylesheets();
551     
552     RenderObject *renderer = node->renderer();
553     if (!renderer)
554         return VisiblePosition();
555
556     RenderBlock *containingBlock = 0;
557     RootInlineBox *root = 0;
558     InlineBox* box;
559     int ignoredCaretOffset;
560     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
561     if (box) {
562         root = box->root()->prevRootBox();
563         if (root)
564             containingBlock = renderer->containingBlock();
565     }
566
567     if (!root) {
568         // This containing editable block does not have a previous line.
569         // Need to move back to previous containing editable block in this root editable
570         // block and find the last root line box in that block.
571         Node* startBlock = enclosingBlock(node);
572         Node* n = previousLeafWithSameEditability(node);
573         while (n && startBlock == enclosingBlock(n))
574             n = previousLeafWithSameEditability(n);
575         while (n) {
576             if (highestEditableRoot(Position(n, 0)) != highestRoot)
577                 break;
578             Position pos(n, caretMinOffset(n));
579             if (pos.isCandidate()) {
580                 ASSERT(n->renderer());
581                 Position maxPos(n, caretMaxOffset(n));
582                 maxPos.getInlineBoxAndOffset(DOWNSTREAM, box, ignoredCaretOffset);
583                 if (box) {
584                     // previous root line box found
585                     root = box->root();
586                     containingBlock = n->renderer()->containingBlock();
587                     break;
588                 }
589
590                 return VisiblePosition(pos, DOWNSTREAM);
591             }
592             n = previousLeafWithSameEditability(n);
593         }
594     }
595     
596     if (root) {
597         // FIXME: Can be wrong for multi-column layout and with transforms.
598         FloatPoint absPos = containingBlock->localToAbsolute(FloatPoint());
599         if (containingBlock->hasOverflowClip())
600             absPos -= containingBlock->layer()->scrolledContentOffset();
601         RenderObject* renderer = root->closestLeafChildForXPos(x - absPos.x(), isEditablePosition(p))->renderer();
602         Node* node = renderer->node();
603         if (node && editingIgnoresContent(node))
604             return Position(node->parent(), node->nodeIndex());
605         return renderer->positionForPoint(IntPoint(x - absPos.x(), root->topOverflow()));
606     }
607     
608     // Could not find a previous line. This means we must already be on the first line.
609     // Move to the start of the content in this block, which effectively moves us
610     // to the start of the line we're on.
611     Element* rootElement = node->isContentEditable() ? node->rootEditableElement() : node->document()->documentElement();
612     return VisiblePosition(rootElement, 0, DOWNSTREAM);
613 }
614
615 static Node* nextLeafWithSameEditability(Node* node, int offset)
616 {
617     bool editable = node->isContentEditable();
618     ASSERT(offset >= 0);
619     Node* child = node->childNode(offset);
620     Node* n = child ? child->nextLeafNode() : node->nextLeafNode();
621     while (n) {
622         if (editable == n->isContentEditable())
623             return n;
624         n = n->nextLeafNode();
625     }
626     return 0;
627 }
628
629 static Node* nextLeafWithSameEditability(Node* node)
630 {
631     if (!node)
632         return 0;
633     
634     bool editable = node->isContentEditable();
635     Node* n = node->nextLeafNode();
636     while (n) {
637         if (editable == n->isContentEditable())
638             return n;
639         n = n->nextLeafNode();
640     }
641     return 0;
642 }
643
644 VisiblePosition nextLinePosition(const VisiblePosition &visiblePosition, int x)
645 {
646     Position p = visiblePosition.deepEquivalent();
647     Node *node = p.node();
648     Node* highestRoot = highestEditableRoot(p);
649     if (!node)
650         return VisiblePosition();
651     
652     node->document()->updateLayoutIgnorePendingStylesheets();
653
654     RenderObject *renderer = node->renderer();
655     if (!renderer)
656         return VisiblePosition();
657
658     RenderBlock *containingBlock = 0;
659     RootInlineBox *root = 0;
660     InlineBox* box;
661     int ignoredCaretOffset;
662     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
663     if (box) {
664         root = box->root()->nextRootBox();
665         if (root)
666             containingBlock = renderer->containingBlock();
667     }
668
669     if (!root) {
670         // This containing editable block does not have a next line.
671         // Need to move forward to next containing editable block in this root editable
672         // block and find the first root line box in that block.
673         Node* startBlock = enclosingBlock(node);
674         Node* n = nextLeafWithSameEditability(node, p.m_offset);
675         while (n && startBlock == enclosingBlock(n))
676             n = nextLeafWithSameEditability(n);
677         while (n) {
678             if (highestEditableRoot(Position(n, 0)) != highestRoot)
679                 break;
680             Position pos(n, caretMinOffset(n));
681             if (pos.isCandidate()) {
682                 ASSERT(n->renderer());
683                 pos.getInlineBoxAndOffset(DOWNSTREAM, box, ignoredCaretOffset);
684                 if (box) {
685                     // next root line box found
686                     root = box->root();
687                     containingBlock = n->renderer()->containingBlock();
688                     break;
689                 }
690
691                 return VisiblePosition(pos, DOWNSTREAM);
692             }
693             n = nextLeafWithSameEditability(n);
694         }
695     }
696     
697     if (root) {
698         // FIXME: Can be wrong for multi-column layout and with transforms.
699         FloatPoint absPos = containingBlock->localToAbsolute(FloatPoint());
700         if (containingBlock->hasOverflowClip())
701             absPos -= containingBlock->layer()->scrolledContentOffset();
702         RenderObject* renderer = root->closestLeafChildForXPos(x - absPos.x(), isEditablePosition(p))->renderer();
703         Node* node = renderer->node();
704         if (node && editingIgnoresContent(node))
705             return Position(node->parent(), node->nodeIndex());
706         return renderer->positionForPoint(IntPoint(x - absPos.x(), root->topOverflow()));
707     }    
708
709     // Could not find a next line. This means we must already be on the last line.
710     // Move to the end of the content in this block, which effectively moves us
711     // to the end of the line we're on.
712     Element* rootElement = node->isContentEditable() ? node->rootEditableElement() : node->document()->documentElement();
713     return VisiblePosition(rootElement, rootElement ? rootElement->childNodeCount() : 0, DOWNSTREAM);
714 }
715
716 // ---------
717
718 static unsigned startSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
719 {
720     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
721     // FIXME: The following function can return -1; we don't handle that.
722     return textBreakPreceding(iterator, length);
723 }
724
725 VisiblePosition startOfSentence(const VisiblePosition &c)
726 {
727     return previousBoundary(c, startSentenceBoundary);
728 }
729
730 static unsigned endSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
731 {
732     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
733     return textBreakNext(iterator);
734 }
735
736 // FIXME: This includes the space after the punctuation that marks the end of the sentence.
737 VisiblePosition endOfSentence(const VisiblePosition &c)
738 {
739     return nextBoundary(c, endSentenceBoundary);
740 }
741
742 static unsigned previousSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
743 {
744     // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
745     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
746     // FIXME: The following function can return -1; we don't handle that.
747     return textBreakPreceding(iterator, length);
748 }
749
750 VisiblePosition previousSentencePosition(const VisiblePosition &c)
751 {
752     VisiblePosition prev = previousBoundary(c, previousSentencePositionBoundary);
753     return c.honorEditableBoundaryAtOrAfter(prev);
754 }
755
756 static unsigned nextSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
757 {
758     // FIXME: This is identical to endSentenceBoundary.  This isn't right, it needs to 
759     // move to the equivlant position in the following sentence.
760     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
761     return textBreakFollowing(iterator, 0);
762 }
763
764 VisiblePosition nextSentencePosition(const VisiblePosition &c)
765 {
766     VisiblePosition next = nextBoundary(c, nextSentencePositionBoundary);    
767     return c.honorEditableBoundaryAtOrBefore(next);
768 }
769
770 static bool renderedAsNonInlineTableOrHR(RenderObject* renderer)
771 {
772     return renderer && ((renderer->isTable() && !renderer->isInline()) || renderer->isHR());
773 }
774
775 // FIXME: Broken for positions before/after images that aren't inline (5027702)
776 VisiblePosition startOfParagraph(const VisiblePosition& c)
777 {
778     Position p = c.deepEquivalent();
779     Node *startNode = p.node();
780
781     if (!startNode)
782         return VisiblePosition();
783     
784     if (renderedAsNonInlineTableOrHR(startNode->renderer()) && p.atLastEditingPositionForNode())
785         return firstDeepEditingPositionForNode(startNode);
786
787     Node* startBlock = enclosingBlock(startNode);
788
789     Node *node = startNode;
790     int offset = p.m_offset;
791
792     Node *n = startNode;
793     while (n) {
794         if (n->isContentEditable() != startNode->isContentEditable())
795             break;
796         RenderObject *r = n->renderer();
797         if (!r) {
798             n = n->traversePreviousNodePostOrder(startBlock);
799             continue;
800         }
801         RenderStyle *style = r->style();
802         if (style->visibility() != VISIBLE) {
803             n = n->traversePreviousNodePostOrder(startBlock);
804             continue;
805         }
806         
807         if (r->isBR() || isBlock(n))
808             break;
809             
810         if (r->isText()) {
811             if (style->preserveNewline()) {
812                 const UChar* chars = toRenderText(r)->characters();
813                 int i = toRenderText(r)->textLength();
814                 int o = offset;
815                 if (n == startNode && o < i)
816                     i = max(0, o);
817                 while (--i >= 0)
818                     if (chars[i] == '\n')
819                         return VisiblePosition(n, i + 1, DOWNSTREAM);
820             }
821             node = n;
822             offset = 0;
823             n = n->traversePreviousNodePostOrder(startBlock);
824         } else if (editingIgnoresContent(n) || isTableElement(n)) {
825             node = n;
826             offset = 0;
827             n = n->previousSibling() ? n->previousSibling() : n->traversePreviousNodePostOrder(startBlock);
828         } else
829             n = n->traversePreviousNodePostOrder(startBlock);
830     }
831
832     return VisiblePosition(node, offset, DOWNSTREAM);
833 }
834
835 // FIXME: Broken for positions before/after images that aren't inline (5027702)
836 VisiblePosition endOfParagraph(const VisiblePosition &c)
837 {    
838     if (c.isNull())
839         return VisiblePosition();
840
841     Position p = c.deepEquivalent();
842     Node* startNode = p.node();
843
844     if (renderedAsNonInlineTableOrHR(startNode->renderer()) && p.atFirstEditingPositionForNode())
845         return lastDeepEditingPositionForNode(startNode);
846     
847     Node* startBlock = enclosingBlock(startNode);
848     Node *stayInsideBlock = startBlock;
849     
850     Node *node = startNode;
851     int offset = p.m_offset;
852
853     Node *n = startNode;
854     while (n) {
855         if (n->isContentEditable() != startNode->isContentEditable())
856             break;
857         RenderObject *r = n->renderer();
858         if (!r) {
859             n = n->traverseNextNode(stayInsideBlock);
860             continue;
861         }
862         RenderStyle *style = r->style();
863         if (style->visibility() != VISIBLE) {
864             n = n->traverseNextNode(stayInsideBlock);
865             continue;
866         }
867         
868         if (r->isBR() || isBlock(n))
869             break;
870             
871         // FIXME: We avoid returning a position where the renderer can't accept the caret.
872         // We should probably do this in other cases such as startOfParagraph.
873         if (r->isText() && r->caretMaxRenderedOffset() > 0) {
874             int length = toRenderText(r)->textLength();
875             if (style->preserveNewline()) {
876                 const UChar* chars = toRenderText(r)->characters();
877                 int o = n == startNode ? offset : 0;
878                 for (int i = o; i < length; ++i)
879                     if (chars[i] == '\n')
880                         return VisiblePosition(n, i, DOWNSTREAM);
881             }
882             node = n;
883             offset = r->caretMaxOffset();
884             n = n->traverseNextNode(stayInsideBlock);
885         } else if (editingIgnoresContent(n) || isTableElement(n)) {
886             node = n;
887             offset = lastOffsetForEditing(n);
888             n = n->traverseNextSibling(stayInsideBlock);
889         } else
890             n = n->traverseNextNode(stayInsideBlock);
891     }
892
893     return VisiblePosition(node, offset, DOWNSTREAM);
894 }
895
896 VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
897 {
898     VisiblePosition paragraphEnd(endOfParagraph(visiblePosition));
899     VisiblePosition afterParagraphEnd(paragraphEnd.next(true));
900     // The position after the last position in the last cell of a table
901     // is not the start of the next paragraph.
902     if (isFirstPositionAfterTable(afterParagraphEnd))
903         return afterParagraphEnd.next(true);
904     return afterParagraphEnd;
905 }
906
907 bool inSameParagraph(const VisiblePosition &a, const VisiblePosition &b)
908 {
909     return a.isNotNull() && startOfParagraph(a) == startOfParagraph(b);
910 }
911
912 bool isStartOfParagraph(const VisiblePosition &pos)
913 {
914     return pos.isNotNull() && pos == startOfParagraph(pos);
915 }
916
917 bool isEndOfParagraph(const VisiblePosition &pos)
918 {
919     return pos.isNotNull() && pos == endOfParagraph(pos);
920 }
921
922 VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
923 {
924     VisiblePosition pos = p;
925     do {
926         VisiblePosition n = previousLinePosition(pos, x);
927         if (n.isNull() || n == pos)
928             break;
929         pos = n;
930     } while (inSameParagraph(p, pos));
931     return pos;
932 }
933
934 VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
935 {
936     VisiblePosition pos = p;
937     do {
938         VisiblePosition n = nextLinePosition(pos, x);
939         if (n.isNull() || n == pos)
940             break;
941         pos = n;
942     } while (inSameParagraph(p, pos));
943     return pos;
944 }
945
946 // ---------
947
948 VisiblePosition startOfBlock(const VisiblePosition &c)
949 {
950     Position p = c.deepEquivalent();
951     Node *startNode = p.node();
952     if (!startNode)
953         return VisiblePosition();
954     return VisiblePosition(Position(startNode->enclosingBlockFlowElement(), 0), DOWNSTREAM);
955 }
956
957 VisiblePosition endOfBlock(const VisiblePosition &c)
958 {
959     Position p = c.deepEquivalent();
960
961     Node *startNode = p.node();
962     if (!startNode)
963         return VisiblePosition();
964
965     Node *startBlock = startNode->enclosingBlockFlowElement();
966     
967     return VisiblePosition(startBlock, startBlock->childNodeCount(), VP_DEFAULT_AFFINITY);   
968 }
969
970 bool inSameBlock(const VisiblePosition &a, const VisiblePosition &b)
971 {
972     return !a.isNull() && enclosingBlockFlowElement(a) == enclosingBlockFlowElement(b);
973 }
974
975 bool isStartOfBlock(const VisiblePosition &pos)
976 {
977     return pos.isNotNull() && pos == startOfBlock(pos);
978 }
979
980 bool isEndOfBlock(const VisiblePosition &pos)
981 {
982     return pos.isNotNull() && pos == endOfBlock(pos);
983 }
984
985 // ---------
986
987 VisiblePosition startOfDocument(const Node* node)
988 {
989     if (!node)
990         return VisiblePosition();
991     
992     return VisiblePosition(node->document()->documentElement(), 0, DOWNSTREAM);
993 }
994
995 VisiblePosition startOfDocument(const VisiblePosition &c)
996 {
997     return startOfDocument(c.deepEquivalent().node());
998 }
999
1000 VisiblePosition endOfDocument(const Node* node)
1001 {
1002     if (!node || !node->document())
1003         return VisiblePosition();
1004     
1005     Element* doc = node->document()->documentElement();
1006     return VisiblePosition(doc, doc->childNodeCount(), DOWNSTREAM);
1007 }
1008
1009 VisiblePosition endOfDocument(const VisiblePosition &c)
1010 {
1011     return endOfDocument(c.deepEquivalent().node());
1012 }
1013
1014 bool inSameDocument(const VisiblePosition &a, const VisiblePosition &b)
1015 {
1016     Position ap = a.deepEquivalent();
1017     Node *an = ap.node();
1018     if (!an)
1019         return false;
1020     Position bp = b.deepEquivalent();
1021     Node *bn = bp.node();
1022     if (an == bn)
1023         return true;
1024
1025     return an->document() == bn->document();
1026 }
1027
1028 bool isStartOfDocument(const VisiblePosition &p)
1029 {
1030     return p.isNotNull() && p.previous().isNull();
1031 }
1032
1033 bool isEndOfDocument(const VisiblePosition &p)
1034 {
1035     return p.isNotNull() && p.next().isNull();
1036 }
1037
1038 // ---------
1039
1040 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1041 {
1042     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1043     if (!highestRoot)
1044         return VisiblePosition();
1045
1046     return firstDeepEditingPositionForNode(highestRoot);
1047 }
1048
1049 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1050 {
1051     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1052     if (!highestRoot)
1053         return VisiblePosition();
1054
1055     return lastDeepEditingPositionForNode(highestRoot);
1056 }
1057
1058 }