Rename WebCore/editing/visible_units.* to VisibleUnits.*
[WebKit-https.git] / Source / WebCore / editing / VisibleUnits.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 "VisibleUnits.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)
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     if (requiresContextForWordBoundary(c.characterAfter())) {
543         RefPtr<Range> backwardsScanRange(d->createRange());
544         backwardsScanRange->setEnd(start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
545         SimplifiedBackwardsTextIterator backwardsIterator(backwardsScanRange.get());
546         while (!backwardsIterator.atEnd()) {
547             const UChar* characters = backwardsIterator.characters();
548             int length = backwardsIterator.length();
549             int i = startOfLastWordBoundaryContext(characters, length);
550             string.prepend(characters + i, length - i);
551             prefixLength += length - i;
552             if (i > 0)
553                 break;
554             backwardsIterator.advance();
555         }
556     }
557
558     searchRange->selectNodeContents(boundary, IGNORE_EXCEPTION);
559     searchRange->setStart(start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
560     TextIterator it(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
561     unsigned next = 0;
562     bool inTextSecurityMode = start.deprecatedNode() && start.deprecatedNode()->renderer() && start.deprecatedNode()->renderer()->style()->textSecurity() != TSNONE;
563     bool needMoreContext = false;
564     while (!it.atEnd()) {
565         // Keep asking the iterator for chunks until the search function
566         // returns an end value not equal to the length of the string passed to it.
567         if (!inTextSecurityMode)
568             string.append(it.characters(), it.length());
569         else {
570             // Treat bullets used in the text security mode as regular characters when looking for boundaries
571             String iteratorString(it.characters(), it.length());
572             iteratorString.fill('x');
573             string.append(iteratorString.characters(), iteratorString.length());
574         }
575         next = searchFunction(string.data(), string.size(), prefixLength, MayHaveMoreContext, needMoreContext);
576         if (next != string.size())
577             break;
578         it.advance();
579     }
580     if (needMoreContext) {
581         // The last search returned the end of the buffer and asked for more context,
582         // but there is no further text. Force a search with what's available.
583         next = searchFunction(string.data(), string.size(), prefixLength, DontHaveMoreContext, needMoreContext);
584         ASSERT(!needMoreContext);
585     }
586     
587     if (it.atEnd() && next == string.size()) {
588         pos = it.range()->startPosition();
589     } else if (next != prefixLength) {
590         // Use the character iterator to translate the next value into a DOM position.
591         CharacterIterator charIt(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
592         charIt.advance(next - prefixLength - 1);
593         RefPtr<Range> characterRange = charIt.range();
594         pos = characterRange->endPosition();
595         
596         if (*charIt.characters() == '\n') {
597             // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)
598             VisiblePosition visPos = VisiblePosition(pos);
599             if (visPos == VisiblePosition(characterRange->startPosition())) {
600                 charIt.advance(1);
601                 pos = charIt.range()->startPosition();
602             }
603         }
604     }
605
606     // generate VisiblePosition, use UPSTREAM affinity if possible
607     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
608 }
609
610 // ---------
611
612 static unsigned startWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
613 {
614     ASSERT(offset);
615     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
616         needMoreContext = true;
617         return 0;
618     }
619     needMoreContext = false;
620     int start, end;
621     U16_BACK_1(characters, 0, offset);
622     findWordBoundary(characters, length, offset, &start, &end);
623     return start;
624 }
625
626 VisiblePosition startOfWord(const VisiblePosition &c, EWordSide side)
627 {
628     // FIXME: This returns a null VP for c at the start of the document
629     // and side == LeftWordIfOnBoundary
630     VisiblePosition p = c;
631     if (side == RightWordIfOnBoundary) {
632         // at paragraph end, the startofWord is the current position
633         if (isEndOfParagraph(c))
634             return c;
635         
636         p = c.next();
637         if (p.isNull())
638             return c;
639     }
640     return previousBoundary(p, startWordBoundary);
641 }
642
643 static unsigned endWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
644 {
645     ASSERT(offset <= length);
646     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
647         needMoreContext = true;
648         return length;
649     }
650     needMoreContext = false;
651     int start, end;
652     findWordBoundary(characters, length, offset, &start, &end);
653     return end;
654 }
655
656 VisiblePosition endOfWord(const VisiblePosition &c, EWordSide side)
657 {
658     VisiblePosition p = c;
659     if (side == LeftWordIfOnBoundary) {
660         if (isStartOfParagraph(c))
661             return c;
662             
663         p = c.previous();
664         if (p.isNull())
665             return c;
666     } else if (isEndOfParagraph(c))
667         return c;
668     
669     return nextBoundary(p, endWordBoundary);
670 }
671
672 static unsigned previousWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
673 {
674     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
675         needMoreContext = true;
676         return 0;
677     }
678     needMoreContext = false;
679     return findNextWordFromIndex(characters, length, offset, false);
680 }
681
682 VisiblePosition previousWordPosition(const VisiblePosition &c)
683 {
684     VisiblePosition prev = previousBoundary(c, previousWordPositionBoundary);
685     return c.honorEditingBoundaryAtOrBefore(prev);
686 }
687
688 static unsigned nextWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
689 {
690     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
691         needMoreContext = true;
692         return length;
693     }
694     needMoreContext = false;
695     return findNextWordFromIndex(characters, length, offset, true);
696 }
697
698 VisiblePosition nextWordPosition(const VisiblePosition &c)
699 {
700     VisiblePosition next = nextBoundary(c, nextWordPositionBoundary);    
701     return c.honorEditingBoundaryAtOrAfter(next);
702 }
703
704 bool isStartOfWord(const VisiblePosition& p)
705 {
706     return p.isNotNull() && p == startOfWord(p, RightWordIfOnBoundary);
707 }
708
709 // ---------
710
711 enum LineEndpointComputationMode { UseLogicalOrdering, UseInlineBoxOrdering };
712 static VisiblePosition startPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
713 {
714     if (c.isNull())
715         return VisiblePosition();
716
717     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
718     if (!rootBox) {
719         // There are VisiblePositions at offset 0 in blocks without
720         // RootInlineBoxes, like empty editable blocks and bordered blocks.
721         Position p = c.deepEquivalent();
722         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
723             return c;
724
725         return VisiblePosition();
726     }
727
728     Node* startNode;
729     InlineBox* startBox;
730     if (mode == UseLogicalOrdering) {
731         startNode = rootBox->getLogicalStartBoxWithNode(startBox);
732         if (!startNode)
733             return VisiblePosition();
734     } else {
735         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
736         // and so cannot be represented by a VisiblePosition. Use whatever follows instead.
737         startBox = rootBox->firstLeafChild();
738         while (true) {
739             if (!startBox)
740                 return VisiblePosition();
741
742             RenderObject* startRenderer = startBox->renderer();
743             if (!startRenderer)
744                 return VisiblePosition();
745
746             startNode = startRenderer->nonPseudoNode();
747             if (startNode)
748                 break;
749
750             startBox = startBox->nextLeafChild();
751         }
752     }
753
754     return startNode->isTextNode() ? Position(toText(startNode), toInlineTextBox(startBox)->start())
755         : positionBeforeNode(startNode);
756 }
757
758 static VisiblePosition startOfLine(const VisiblePosition& c, LineEndpointComputationMode mode)
759 {
760     // TODO: this is the current behavior that might need to be fixed.
761     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
762     VisiblePosition visPos = startPositionForLine(c, mode);
763
764     if (mode == UseLogicalOrdering) {
765         if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
766             if (!editableRoot->contains(visPos.deepEquivalent().containerNode()))
767                 return firstPositionInNode(editableRoot);
768         }
769     }
770
771     return c.honorEditingBoundaryAtOrBefore(visPos);
772 }
773
774 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
775 VisiblePosition startOfLine(const VisiblePosition& currentPosition)
776 {
777     return startOfLine(currentPosition, UseInlineBoxOrdering);
778 }
779
780 VisiblePosition logicalStartOfLine(const VisiblePosition& currentPosition)
781 {
782     return startOfLine(currentPosition, UseLogicalOrdering);
783 }
784
785 static VisiblePosition endPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
786 {
787     if (c.isNull())
788         return VisiblePosition();
789
790     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
791     if (!rootBox) {
792         // There are VisiblePositions at offset 0 in blocks without
793         // RootInlineBoxes, like empty editable blocks and bordered blocks.
794         Position p = c.deepEquivalent();
795         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
796             return c;
797         return VisiblePosition();
798     }
799
800     Node* endNode;
801     InlineBox* endBox;
802     if (mode == UseLogicalOrdering) {
803         endNode = rootBox->getLogicalEndBoxWithNode(endBox);
804         if (!endNode)
805             return VisiblePosition();
806     } else {
807         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
808         // and so cannot be represented by a VisiblePosition. Use whatever precedes instead.
809         endBox = rootBox->lastLeafChild();
810         while (true) {
811             if (!endBox)
812                 return VisiblePosition();
813
814             RenderObject* endRenderer = endBox->renderer();
815             if (!endRenderer)
816                 return VisiblePosition();
817
818             endNode = endRenderer->nonPseudoNode();
819             if (endNode)
820                 break;
821             
822             endBox = endBox->prevLeafChild();
823         }
824     }
825
826     Position pos;
827     if (endNode->hasTagName(brTag))
828         pos = positionBeforeNode(endNode);
829     else if (endBox->isInlineTextBox() && endNode->isTextNode()) {
830         InlineTextBox* endTextBox = toInlineTextBox(endBox);
831         int endOffset = endTextBox->start();
832         if (!endTextBox->isLineBreak())
833             endOffset += endTextBox->len();
834         pos = Position(toText(endNode), endOffset);
835     } else
836         pos = positionAfterNode(endNode);
837     
838     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
839 }
840
841 static bool inSameLogicalLine(const VisiblePosition& a, const VisiblePosition& b)
842 {
843     return a.isNotNull() && logicalStartOfLine(a) == logicalStartOfLine(b);
844 }
845
846 static VisiblePosition endOfLine(const VisiblePosition& c, LineEndpointComputationMode mode)
847 {
848     // TODO: this is the current behavior that might need to be fixed.
849     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
850     VisiblePosition visPos = endPositionForLine(c, mode);
851
852     if (mode == UseLogicalOrdering) {
853         // Make sure the end of line is at the same line as the given input position. For a wrapping line, the logical end
854         // position for the not-last-2-lines might incorrectly hand back the logical beginning of the next line. 
855         // For example, <div contenteditable dir="rtl" style="line-break:before-white-space">abcdefg abcdefg abcdefg
856         // a abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg </div>
857         // In this case, use the previous position of the computed logical end position.
858         if (!inSameLogicalLine(c, visPos))
859             visPos = visPos.previous();
860
861         if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
862             if (!editableRoot->contains(visPos.deepEquivalent().containerNode()))
863                 return lastPositionInNode(editableRoot);
864         }
865
866         return c.honorEditingBoundaryAtOrAfter(visPos);
867     }
868
869     // Make sure the end of line is at the same line as the given input position. Else use the previous position to 
870     // obtain end of line. This condition happens when the input position is before the space character at the end 
871     // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position
872     // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style
873     // versus lines without that style, which would break before a space by default. 
874     if (!inSameLine(c, visPos)) {
875         visPos = c.previous();
876         if (visPos.isNull())
877             return VisiblePosition();
878         visPos = endPositionForLine(visPos, UseInlineBoxOrdering);
879     }
880     
881     return c.honorEditingBoundaryAtOrAfter(visPos);
882 }
883
884 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
885 VisiblePosition endOfLine(const VisiblePosition& currentPosition)
886 {
887     return endOfLine(currentPosition, UseInlineBoxOrdering);
888 }
889
890 VisiblePosition logicalEndOfLine(const VisiblePosition& currentPosition)
891 {
892     return endOfLine(currentPosition, UseLogicalOrdering);
893 }
894
895 bool inSameLine(const VisiblePosition &a, const VisiblePosition &b)
896 {
897     return a.isNotNull() && startOfLine(a) == startOfLine(b);
898 }
899
900 bool isStartOfLine(const VisiblePosition &p)
901 {
902     return p.isNotNull() && p == startOfLine(p);
903 }
904
905 bool isEndOfLine(const VisiblePosition &p)
906 {
907     return p.isNotNull() && p == endOfLine(p);
908 }
909
910 static inline IntPoint absoluteLineDirectionPointToLocalPointInBlock(RootInlineBox* root, int lineDirectionPoint)
911 {
912     ASSERT(root);
913     RenderBlock* containingBlock = root->block();
914     FloatPoint absoluteBlockPoint = containingBlock->localToAbsolute(FloatPoint());
915     if (containingBlock->hasOverflowClip())
916         absoluteBlockPoint -= containingBlock->scrolledContentOffset();
917
918     if (root->block()->isHorizontalWritingMode())
919         return IntPoint(lineDirectionPoint - absoluteBlockPoint.x(), root->blockDirectionPointInLine());
920
921     return IntPoint(root->blockDirectionPointInLine(), lineDirectionPoint - absoluteBlockPoint.y());
922 }
923
924 VisiblePosition previousLinePosition(const VisiblePosition &visiblePosition, int lineDirectionPoint, EditableType editableType)
925 {
926     Position p = visiblePosition.deepEquivalent();
927     Node* node = p.deprecatedNode();
928
929     if (!node)
930         return VisiblePosition();
931     
932     node->document()->updateLayoutIgnorePendingStylesheets();
933     
934     RenderObject* renderer = node->renderer();
935     if (!renderer)
936         return VisiblePosition();
937
938     RootInlineBox* root = 0;
939     InlineBox* box;
940     int ignoredCaretOffset;
941     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
942     if (box) {
943         root = box->root()->prevRootBox();
944         // We want to skip zero height boxes.
945         // This could happen in case it is a TrailingFloatsRootInlineBox.
946         if (!root || !root->logicalHeight() || !root->firstLeafChild())
947             root = 0;
948     }
949
950     if (!root) {
951         Position position = previousRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
952         if (position.isNotNull()) {
953             RenderedPosition renderedPosition(position);
954             root = renderedPosition.rootBox();
955             if (!root)
956                 return position;
957         }
958     }
959     
960     if (root) {
961         // FIXME: Can be wrong for multi-column layout and with transforms.
962         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(root, lineDirectionPoint);
963         RenderObject* renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
964         Node* node = renderer->node();
965         if (node && editingIgnoresContent(node))
966             return positionInParentBeforeNode(node);
967         return renderer->positionForPoint(pointInLine);
968     }
969     
970     // Could not find a previous line. This means we must already be on the first line.
971     // Move to the start of the content in this block, which effectively moves us
972     // to the start of the line we're on.
973     Element* rootElement = node->rendererIsEditable(editableType) ? node->rootEditableElement(editableType) : node->document()->documentElement();
974     if (!rootElement)
975         return VisiblePosition();
976     return VisiblePosition(firstPositionInNode(rootElement), DOWNSTREAM);
977 }
978
979 VisiblePosition nextLinePosition(const VisiblePosition &visiblePosition, int lineDirectionPoint, EditableType editableType)
980 {
981     Position p = visiblePosition.deepEquivalent();
982     Node* node = p.deprecatedNode();
983
984     if (!node)
985         return VisiblePosition();
986     
987     node->document()->updateLayoutIgnorePendingStylesheets();
988
989     RenderObject* renderer = node->renderer();
990     if (!renderer)
991         return VisiblePosition();
992
993     RootInlineBox* root = 0;
994     InlineBox* box;
995     int ignoredCaretOffset;
996     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
997     if (box) {
998         root = box->root()->nextRootBox();
999         // We want to skip zero height boxes.
1000         // This could happen in case it is a TrailingFloatsRootInlineBox.
1001         if (!root || !root->logicalHeight() || !root->firstLeafChild())
1002             root = 0;
1003     }
1004
1005     if (!root) {
1006         // FIXME: We need do the same in previousLinePosition.
1007         Node* child = node->childNode(p.deprecatedEditingOffset());
1008         node = child ? child : node->lastDescendant();
1009         Position position = nextRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
1010         if (position.isNotNull()) {
1011             RenderedPosition renderedPosition(position);
1012             root = renderedPosition.rootBox();
1013             if (!root)
1014                 return position;
1015         }
1016     }
1017     
1018     if (root) {
1019         // FIXME: Can be wrong for multi-column layout and with transforms.
1020         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(root, lineDirectionPoint);
1021         RenderObject* renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
1022         Node* node = renderer->node();
1023         if (node && editingIgnoresContent(node))
1024             return positionInParentBeforeNode(node);
1025         return renderer->positionForPoint(pointInLine);
1026     }
1027
1028     // Could not find a next line. This means we must already be on the last line.
1029     // Move to the end of the content in this block, which effectively moves us
1030     // to the end of the line we're on.
1031     Element* rootElement = node->rendererIsEditable(editableType) ? node->rootEditableElement(editableType) : node->document()->documentElement();
1032     if (!rootElement)
1033         return VisiblePosition();
1034     return VisiblePosition(lastPositionInNode(rootElement), DOWNSTREAM);
1035 }
1036
1037 // ---------
1038
1039 static unsigned startSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1040 {
1041     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1042     // FIXME: The following function can return -1; we don't handle that.
1043     return textBreakPreceding(iterator, length);
1044 }
1045
1046 VisiblePosition startOfSentence(const VisiblePosition &c)
1047 {
1048     return previousBoundary(c, startSentenceBoundary);
1049 }
1050
1051 static unsigned endSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1052 {
1053     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1054     return textBreakNext(iterator);
1055 }
1056
1057 // FIXME: This includes the space after the punctuation that marks the end of the sentence.
1058 VisiblePosition endOfSentence(const VisiblePosition &c)
1059 {
1060     return nextBoundary(c, endSentenceBoundary);
1061 }
1062
1063 static unsigned previousSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1064 {
1065     // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
1066     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1067     // FIXME: The following function can return -1; we don't handle that.
1068     return textBreakPreceding(iterator, length);
1069 }
1070
1071 VisiblePosition previousSentencePosition(const VisiblePosition &c)
1072 {
1073     VisiblePosition prev = previousBoundary(c, previousSentencePositionBoundary);
1074     return c.honorEditingBoundaryAtOrBefore(prev);
1075 }
1076
1077 static unsigned nextSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1078 {
1079     // FIXME: This is identical to endSentenceBoundary. This isn't right, it needs to 
1080     // move to the equivlant position in the following sentence.
1081     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1082     return textBreakFollowing(iterator, 0);
1083 }
1084
1085 VisiblePosition nextSentencePosition(const VisiblePosition &c)
1086 {
1087     VisiblePosition next = nextBoundary(c, nextSentencePositionBoundary);    
1088     return c.honorEditingBoundaryAtOrAfter(next);
1089 }
1090
1091 VisiblePosition startOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1092 {
1093     Position p = c.deepEquivalent();
1094     Node* startNode = p.deprecatedNode();
1095
1096     if (!startNode)
1097         return VisiblePosition();
1098     
1099     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1100         return positionBeforeNode(startNode);
1101
1102     Node* startBlock = enclosingBlock(startNode);
1103
1104     Node* node = startNode;
1105     Node* highestRoot = highestEditableRoot(p);
1106     int offset = p.deprecatedEditingOffset();
1107     Position::AnchorType type = p.anchorType();
1108
1109     Node* n = startNode;
1110     while (n) {
1111 #if ENABLE(USERSELECT_ALL)
1112         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->rendererIsEditable() != startNode->rendererIsEditable())
1113 #else
1114         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->rendererIsEditable() != startNode->rendererIsEditable())
1115 #endif
1116             break;
1117         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1118             while (n && n->rendererIsEditable() != startNode->rendererIsEditable())
1119                 n = NodeTraversal::previousPostOrder(n, startBlock);
1120             if (!n || !n->isDescendantOf(highestRoot))
1121                 break;
1122         }
1123         RenderObject* r = n->renderer();
1124         if (!r) {
1125             n = NodeTraversal::previousPostOrder(n, startBlock);
1126             continue;
1127         }
1128         RenderStyle* style = r->style();
1129         if (style->visibility() != VISIBLE) {
1130             n = NodeTraversal::previousPostOrder(n, startBlock);
1131             continue;
1132         }
1133         
1134         if (r->isBR() || isBlock(n))
1135             break;
1136
1137         if (r->isText() && toRenderText(r)->renderedTextLength()) {
1138             ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1139             type = Position::PositionIsOffsetInAnchor;
1140             if (style->preserveNewline()) {
1141                 const UChar* chars = toRenderText(r)->characters();
1142                 int i = toRenderText(r)->textLength();
1143                 int o = offset;
1144                 if (n == startNode && o < i)
1145                     i = max(0, o);
1146                 while (--i >= 0) {
1147                     if (chars[i] == '\n')
1148                         return VisiblePosition(Position(toText(n), i + 1), DOWNSTREAM);
1149                 }
1150             }
1151             node = n;
1152             offset = 0;
1153             n = NodeTraversal::previousPostOrder(n, startBlock);
1154         } else if (editingIgnoresContent(n) || isTableElement(n)) {
1155             node = n;
1156             type = Position::PositionIsBeforeAnchor;
1157             n = n->previousSibling() ? n->previousSibling() : NodeTraversal::previousPostOrder(n, startBlock);
1158         } else
1159             n = NodeTraversal::previousPostOrder(n, startBlock);
1160     }
1161
1162     if (type == Position::PositionIsOffsetInAnchor) {
1163         ASSERT(type == Position::PositionIsOffsetInAnchor || !offset);
1164         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1165     }
1166
1167     return VisiblePosition(Position(node, type), DOWNSTREAM);
1168 }
1169
1170 VisiblePosition endOfParagraph(const VisiblePosition &c, EditingBoundaryCrossingRule boundaryCrossingRule)
1171 {    
1172     if (c.isNull())
1173         return VisiblePosition();
1174
1175     Position p = c.deepEquivalent();
1176     Node* startNode = p.deprecatedNode();
1177
1178     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1179         return positionAfterNode(startNode);
1180     
1181     Node* startBlock = enclosingBlock(startNode);
1182     Node* stayInsideBlock = startBlock;
1183     
1184     Node* node = startNode;
1185     Node* highestRoot = highestEditableRoot(p);
1186     int offset = p.deprecatedEditingOffset();
1187     Position::AnchorType type = p.anchorType();
1188
1189     Node* n = startNode;
1190     while (n) {
1191 #if ENABLE(USERSELECT_ALL)
1192         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->rendererIsEditable() != startNode->rendererIsEditable())
1193 #else
1194         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->rendererIsEditable() != startNode->rendererIsEditable())
1195 #endif
1196             break;
1197         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1198             while (n && n->rendererIsEditable() != startNode->rendererIsEditable())
1199                 n = NodeTraversal::next(n, stayInsideBlock);
1200             if (!n || !n->isDescendantOf(highestRoot))
1201                 break;
1202         }
1203
1204         RenderObject* r = n->renderer();
1205         if (!r) {
1206             n = NodeTraversal::next(n, stayInsideBlock);
1207             continue;
1208         }
1209         RenderStyle* style = r->style();
1210         if (style->visibility() != VISIBLE) {
1211             n = NodeTraversal::next(n, stayInsideBlock);
1212             continue;
1213         }
1214         
1215         if (r->isBR() || isBlock(n))
1216             break;
1217
1218         // FIXME: We avoid returning a position where the renderer can't accept the caret.
1219         if (r->isText() && toRenderText(r)->renderedTextLength()) {
1220             ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1221             int length = toRenderText(r)->textLength();
1222             type = Position::PositionIsOffsetInAnchor;
1223             if (style->preserveNewline()) {
1224                 const UChar* chars = toRenderText(r)->characters();
1225                 int o = n == startNode ? offset : 0;
1226                 for (int i = o; i < length; ++i) {
1227                     if (chars[i] == '\n')
1228                         return VisiblePosition(Position(toText(n), i), DOWNSTREAM);
1229                 }
1230             }
1231             node = n;
1232             offset = r->caretMaxOffset();
1233             n = NodeTraversal::next(n, stayInsideBlock);
1234         } else if (editingIgnoresContent(n) || isTableElement(n)) {
1235             node = n;
1236             type = Position::PositionIsAfterAnchor;
1237             n = NodeTraversal::nextSkippingChildren(n, stayInsideBlock);
1238         } else
1239             n = NodeTraversal::next(n, stayInsideBlock);
1240     }
1241
1242     if (type == Position::PositionIsOffsetInAnchor)
1243         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1244
1245     return VisiblePosition(Position(node, type), DOWNSTREAM);
1246 }
1247
1248 // FIXME: isStartOfParagraph(startOfNextParagraph(pos)) is not always true
1249 VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
1250 {
1251     VisiblePosition paragraphEnd(endOfParagraph(visiblePosition, CanSkipOverEditingBoundary));
1252     VisiblePosition afterParagraphEnd(paragraphEnd.next(CannotCrossEditingBoundary));
1253     // The position after the last position in the last cell of a table
1254     // is not the start of the next paragraph.
1255     if (isFirstPositionAfterTable(afterParagraphEnd))
1256         return afterParagraphEnd.next(CannotCrossEditingBoundary);
1257     return afterParagraphEnd;
1258 }
1259
1260 bool inSameParagraph(const VisiblePosition &a, const VisiblePosition &b, EditingBoundaryCrossingRule boundaryCrossingRule)
1261 {
1262     return a.isNotNull() && startOfParagraph(a, boundaryCrossingRule) == startOfParagraph(b, boundaryCrossingRule);
1263 }
1264
1265 bool isStartOfParagraph(const VisiblePosition &pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1266 {
1267     return pos.isNotNull() && pos == startOfParagraph(pos, boundaryCrossingRule);
1268 }
1269
1270 bool isEndOfParagraph(const VisiblePosition &pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1271 {
1272     return pos.isNotNull() && pos == endOfParagraph(pos, boundaryCrossingRule);
1273 }
1274
1275 VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
1276 {
1277     VisiblePosition pos = p;
1278     do {
1279         VisiblePosition n = previousLinePosition(pos, x);
1280         if (n.isNull() || n == pos)
1281             break;
1282         pos = n;
1283     } while (inSameParagraph(p, pos));
1284     return pos;
1285 }
1286
1287 VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
1288 {
1289     VisiblePosition pos = p;
1290     do {
1291         VisiblePosition n = nextLinePosition(pos, x);
1292         if (n.isNull() || n == pos)
1293             break;
1294         pos = n;
1295     } while (inSameParagraph(p, pos));
1296     return pos;
1297 }
1298
1299 // ---------
1300
1301 VisiblePosition startOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1302 {
1303     Position position = visiblePosition.deepEquivalent();
1304     Node* startBlock;
1305     if (!position.containerNode() || !(startBlock = enclosingBlock(position.containerNode(), rule)))
1306         return VisiblePosition();
1307     return firstPositionInNode(startBlock);
1308 }
1309
1310 VisiblePosition endOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1311 {
1312     Position position = visiblePosition.deepEquivalent();
1313     Node* endBlock;
1314     if (!position.containerNode() || !(endBlock = enclosingBlock(position.containerNode(), rule)))
1315         return VisiblePosition();
1316     return lastPositionInNode(endBlock);
1317 }
1318
1319 bool inSameBlock(const VisiblePosition &a, const VisiblePosition &b)
1320 {
1321     return !a.isNull() && enclosingBlock(a.deepEquivalent().containerNode()) == enclosingBlock(b.deepEquivalent().containerNode());
1322 }
1323
1324 bool isStartOfBlock(const VisiblePosition &pos)
1325 {
1326     return pos.isNotNull() && pos == startOfBlock(pos, CanCrossEditingBoundary);
1327 }
1328
1329 bool isEndOfBlock(const VisiblePosition &pos)
1330 {
1331     return pos.isNotNull() && pos == endOfBlock(pos, CanCrossEditingBoundary);
1332 }
1333
1334 // ---------
1335
1336 VisiblePosition startOfDocument(const Node* node)
1337 {
1338     if (!node || !node->document() || !node->document()->documentElement())
1339         return VisiblePosition();
1340     
1341     return VisiblePosition(firstPositionInNode(node->document()->documentElement()), DOWNSTREAM);
1342 }
1343
1344 VisiblePosition startOfDocument(const VisiblePosition &c)
1345 {
1346     return startOfDocument(c.deepEquivalent().deprecatedNode());
1347 }
1348
1349 VisiblePosition endOfDocument(const Node* node)
1350 {
1351     if (!node || !node->document() || !node->document()->documentElement())
1352         return VisiblePosition();
1353     
1354     Element* doc = node->document()->documentElement();
1355     return VisiblePosition(lastPositionInNode(doc), DOWNSTREAM);
1356 }
1357
1358 VisiblePosition endOfDocument(const VisiblePosition &c)
1359 {
1360     return endOfDocument(c.deepEquivalent().deprecatedNode());
1361 }
1362
1363 bool inSameDocument(const VisiblePosition &a, const VisiblePosition &b)
1364 {
1365     Position ap = a.deepEquivalent();
1366     Node* an = ap.deprecatedNode();
1367     if (!an)
1368         return false;
1369     Position bp = b.deepEquivalent();
1370     Node* bn = bp.deprecatedNode();
1371     if (an == bn)
1372         return true;
1373
1374     return an->document() == bn->document();
1375 }
1376
1377 bool isStartOfDocument(const VisiblePosition &p)
1378 {
1379     return p.isNotNull() && p.previous(CanCrossEditingBoundary).isNull();
1380 }
1381
1382 bool isEndOfDocument(const VisiblePosition &p)
1383 {
1384     return p.isNotNull() && p.next(CanCrossEditingBoundary).isNull();
1385 }
1386
1387 // ---------
1388
1389 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1390 {
1391     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1392     if (!highestRoot)
1393         return VisiblePosition();
1394
1395     return firstPositionInNode(highestRoot);
1396 }
1397
1398 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1399 {
1400     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1401     if (!highestRoot)
1402         return VisiblePosition();
1403
1404     return lastPositionInNode(highestRoot);
1405 }
1406
1407 bool isEndOfEditableOrNonEditableContent(const VisiblePosition &p)
1408 {
1409     return p.isNotNull() && p.next().isNull();
1410 }
1411
1412 VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1413 {
1414     return direction == LTR ? logicalStartOfLine(c) : logicalEndOfLine(c);
1415 }
1416
1417 VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1418 {
1419     return direction == LTR ? logicalEndOfLine(c) : logicalStartOfLine(c);
1420 }
1421
1422 }