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