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