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