e4a84bab335b944b5b8d8532e25721018dd3bbf9
[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     return c.honorEditableBoundaryAtOrBefore(visPos);
1079 }
1080
1081 static VisiblePosition logicalEndPositionForLine(const VisiblePosition& c)
1082 {
1083     if (c.isNull())
1084         return VisiblePosition();
1085
1086     RootInlineBox* rootBox = rootBoxForLine(c);
1087     if (!rootBox) {
1088         // There are VisiblePositions at offset 0 in blocks without
1089         // RootInlineBoxes, like empty editable blocks and bordered blocks.
1090         Position p = c.deepEquivalent();
1091         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
1092             return c;
1093         return VisiblePosition();
1094     }
1095     
1096     InlineBox* logicalEndBox;
1097     Node* logicalEndNode = rootBox->getLogicalEndBoxWithNode(logicalEndBox);
1098
1099     if (!logicalEndNode)
1100         return VisiblePosition();
1101     
1102     Position pos;
1103     if (logicalEndNode->hasTagName(brTag))
1104         pos = positionBeforeNode(logicalEndNode);
1105     else if (logicalEndBox->isInlineTextBox()) {
1106         InlineTextBox* endTextBox = static_cast<InlineTextBox*>(logicalEndBox);
1107         int endOffset = endTextBox->start();
1108         if (!endTextBox->isLineBreak())
1109             endOffset += endTextBox->len();
1110         pos = Position(logicalEndNode, endOffset, Position::PositionIsOffsetInAnchor);
1111     } else
1112         pos = positionAfterNode(logicalEndNode);
1113     
1114     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
1115 }
1116
1117 bool inSameLogicalLine(const VisiblePosition& a, const VisiblePosition& b)
1118 {
1119     return a.isNotNull() && logicalStartOfLine(a) == logicalStartOfLine(b);
1120 }
1121
1122 VisiblePosition logicalEndOfLine(const VisiblePosition& c)
1123 {
1124     // TODO: this is the current behavior that might need to be fixed.
1125     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
1126
1127     VisiblePosition visPos = logicalEndPositionForLine(c);
1128     
1129     // Make sure the end of line is at the same line as the given input position. For a wrapping line, the logical end
1130     // position for the not-last-2-lines might incorrectly hand back the logical beginning of the next line. 
1131     // For example, <div contenteditable dir="rtl" style="line-break:before-white-space">abcdefg abcdefg abcdefg
1132     // a abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg </div>
1133     // In this case, use the previous position of the computed logical end position.
1134     if (!inSameLogicalLine(c, visPos))
1135         visPos = visPos.previous();
1136     
1137     return c.honorEditableBoundaryAtOrAfter(visPos);
1138 }
1139
1140 VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1141 {
1142     return direction == LTR ? logicalStartOfLine(c) : logicalEndOfLine(c);
1143 }
1144
1145 VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1146 {
1147     return direction == LTR ? logicalEndOfLine(c) : logicalStartOfLine(c);
1148 }
1149
1150 static const int invalidOffset = -1;
1151     
1152 static VisiblePosition previousWordBreakInBoxInsideBlockWithSameDirectionality(const InlineBox* box, const VisiblePosition& previousWordBreak, int& offsetOfWordBreak)
1153 {
1154     bool hasSeenWordBreakInThisBox = previousWordBreak.isNotNull();
1155     // In a LTR block, the word break should be on the left boundary of a word.
1156     // In a RTL block, the word break should be on the right boundary of a word.
1157     // Because nextWordPosition() returns the word break on the right boundary of the word for LTR text,
1158     // we need to use previousWordPosition() to traverse words within the inline boxes from right to left
1159     // to find the previous word break (i.e. the first word break on the left). The same applies to RTL text.
1160     
1161     VisiblePosition wordBreak = hasSeenWordBreakInThisBox ? previousWordBreak : Position(box->renderer()->node(), box->caretMaxOffset(), Position::PositionIsOffsetInAnchor);
1162
1163     // FIXME: handle multi-spaces (http://webkit.org/b/57543).
1164     
1165     wordBreak = previousWordPosition(wordBreak);
1166     if (previousWordBreak == wordBreak)
1167         return VisiblePosition();
1168
1169     InlineBox* boxContainingPreviousWordBreak;
1170     wordBreak.getInlineBoxAndOffset(boxContainingPreviousWordBreak, offsetOfWordBreak);
1171     if (boxContainingPreviousWordBreak != box)
1172         return VisiblePosition();
1173     return wordBreak;
1174 }
1175
1176 static VisiblePosition leftmostPositionInRTLBoxInLTRBlock(const InlineBox* box)
1177 {
1178     // FIXME: Probably need to take care of bidi level too.
1179     Node* node = box->renderer()->node();
1180     InlineBox* previousLeaf = box->prevLeafChild();
1181     InlineBox* nextLeaf = box->nextLeafChild();   
1182     
1183     if (previousLeaf && !previousLeaf->isLeftToRightDirection())
1184         return Position(node, box->caretMaxOffset(), Position::PositionIsOffsetInAnchor);
1185
1186     if (nextLeaf && !nextLeaf->isLeftToRightDirection()) {
1187         if (previousLeaf)
1188             return Position(previousLeaf->renderer()->node(), previousLeaf->caretMaxOffset(), Position::PositionIsOffsetInAnchor);
1189
1190         InlineBox* lastRTLLeaf;
1191         do {
1192             lastRTLLeaf = nextLeaf;
1193             nextLeaf = nextLeaf->nextLeafChild();
1194         } while (nextLeaf && !nextLeaf->isLeftToRightDirection());
1195         return Position(lastRTLLeaf->renderer()->node(), lastRTLLeaf->caretMinOffset(), Position::PositionIsOffsetInAnchor);
1196     }
1197
1198     return Position(node, box->caretMinOffset(), Position::PositionIsOffsetInAnchor);
1199 }
1200
1201 static VisiblePosition rightmostPositionInLTRBoxInRTLBlock(const InlineBox* box)
1202 {
1203     // FIXME: Probably need to take care of bidi level too.
1204     Node* node = box->renderer()->node();
1205     InlineBox* previousLeaf = box->prevLeafChild();
1206     InlineBox* nextLeaf = box->nextLeafChild();   
1207     
1208     if (nextLeaf && nextLeaf->isLeftToRightDirection())    
1209         return Position(node, box->caretMaxOffset(), Position::PositionIsOffsetInAnchor);
1210
1211     if (previousLeaf && previousLeaf->isLeftToRightDirection()) {
1212         if (nextLeaf)
1213             return Position(nextLeaf->renderer()->node(), nextLeaf->caretMaxOffset(), Position::PositionIsOffsetInAnchor);
1214
1215         InlineBox* firstLTRLeaf;
1216         do {
1217             firstLTRLeaf = previousLeaf;
1218             previousLeaf = previousLeaf->prevLeafChild();
1219         } while (previousLeaf && previousLeaf->isLeftToRightDirection());
1220         return Position(firstLTRLeaf->renderer()->node(), firstLTRLeaf->caretMinOffset(), Position::PositionIsOffsetInAnchor);
1221     }
1222
1223     return Position(node, box->caretMinOffset(), Position::PositionIsOffsetInAnchor);
1224 }
1225     
1226 static VisiblePosition lastWordBreakInBox(const InlineBox* box, int& offsetOfWordBreak)
1227 {
1228     // Add the leftmost word break for RTL box or rightmost word break for LTR box.
1229     InlineBox* previousLeaf = box->prevLeafChild();
1230     InlineBox* nextLeaf = box->nextLeafChild();
1231     VisiblePosition boundaryPosition;
1232     if (box->direction() == RTL && (!previousLeaf || previousLeaf->isLeftToRightDirection()))
1233         boundaryPosition = leftmostPositionInRTLBoxInLTRBlock(box);
1234     else if (box->direction() == LTR && (!nextLeaf || !nextLeaf->isLeftToRightDirection()))
1235         boundaryPosition = rightmostPositionInLTRBoxInRTLBlock(box);
1236
1237     if (boundaryPosition.isNull())
1238         return VisiblePosition();            
1239
1240     VisiblePosition wordBreak = nextWordPosition(boundaryPosition);
1241     if (wordBreak != boundaryPosition)
1242         wordBreak = previousWordPosition(wordBreak);
1243
1244     InlineBox* boxOfWordBreak;
1245     wordBreak.getInlineBoxAndOffset(boxOfWordBreak, offsetOfWordBreak);
1246     if (boxOfWordBreak == box)
1247         return wordBreak;
1248     return VisiblePosition();    
1249 }
1250
1251 static bool positionIsVisuallyOrderedInBoxInBlockWithDifferentDirectionality(const VisiblePosition& wordBreak, const InlineBox* box, int& offsetOfWordBreak)
1252 {
1253     int previousOffset = offsetOfWordBreak;
1254     InlineBox* boxOfWordBreak;
1255     wordBreak.getInlineBoxAndOffset(boxOfWordBreak, offsetOfWordBreak);
1256     if (boxOfWordBreak == box && (previousOffset == invalidOffset || previousOffset < offsetOfWordBreak))
1257         return true;
1258     return false;
1259 }
1260     
1261 static VisiblePosition nextWordBreakInBoxInsideBlockWithDifferentDirectionality(
1262     const InlineBox* box, const VisiblePosition& previousWordBreak, int& offsetOfWordBreak, bool& isLastWordBreakInBox)
1263 {
1264     // FIXME: Probably need to take care of bidi level too.
1265     
1266     // In a LTR block, the word break should be on the left boundary of a word.
1267     // In a RTL block, the word break should be on the right boundary of a word.
1268     // Because previousWordPosition() returns the word break on the right boundary of the word for RTL text,
1269     // we need to use nextWordPosition() to traverse words within the inline boxes from right to left to find the next word break.
1270     // The same applies to LTR text, in which words are traversed within the inline boxes from left to right.
1271     
1272     // FIXME: handle multi-spaces (http://webkit.org/b/57543).
1273     
1274     bool hasSeenWordBreakInThisBox = previousWordBreak.isNotNull();
1275     VisiblePosition wordBreak = hasSeenWordBreakInThisBox ? previousWordBreak : Position(box->renderer()->node(), box->caretMinOffset(), Position::PositionIsOffsetInAnchor);
1276     wordBreak = nextWordPosition(wordBreak);
1277     
1278     if (wordBreak == previousWordBreak) {
1279         isLastWordBreakInBox = true;
1280         return VisiblePosition();
1281     }
1282
1283
1284     // Given RTL box "ABC DEF" either follows a LTR box or is the first visual box in an LTR block as an example,
1285     // 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)",
1286     // where the number in parenthesis represents offset in visiblePosition. 
1287     // 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.
1288     // But nextWordPosition() of offset 7 is offset 11, which should be ignored, 
1289     // and the position at offset 0 should be manually added as the last word break within the box.
1290     if (positionIsVisuallyOrderedInBoxInBlockWithDifferentDirectionality(wordBreak, box, offsetOfWordBreak)) {
1291         isLastWordBreakInBox = false;
1292         return wordBreak;
1293     }
1294     
1295     isLastWordBreakInBox = true;
1296     return lastWordBreakInBox(box, offsetOfWordBreak);
1297 }
1298
1299 struct WordBoundaryEntry {
1300     WordBoundaryEntry()
1301         : offsetInInlineBox(invalidOffset) 
1302     { 
1303     }
1304
1305     WordBoundaryEntry(const VisiblePosition& position, int offset)
1306         : visiblePosition(position)
1307         , offsetInInlineBox(offset) 
1308     { 
1309     }
1310
1311     VisiblePosition visiblePosition;
1312     int offsetInInlineBox;
1313 };
1314     
1315 typedef Vector<WordBoundaryEntry, 50> WordBoundaryVector;
1316     
1317 static void collectWordBreaksInBoxInsideBlockWithSameDirectionality(const InlineBox* box, WordBoundaryVector& orderedWordBoundaries)
1318 {
1319     orderedWordBoundaries.clear();
1320     
1321     VisiblePosition wordBreak;
1322     int offsetOfWordBreak = invalidOffset;
1323     while (1) {
1324         wordBreak = previousWordBreakInBoxInsideBlockWithSameDirectionality(box, wordBreak, offsetOfWordBreak);
1325         if (wordBreak.isNull())
1326             break;
1327         WordBoundaryEntry wordBoundaryEntry(wordBreak, offsetOfWordBreak);
1328         orderedWordBoundaries.append(wordBoundaryEntry);
1329     }
1330 }
1331
1332 static void collectWordBreaksInBoxInsideBlockWithDifferntDirectionality(const InlineBox* box, WordBoundaryVector& orderedWordBoundaries)
1333 {
1334     orderedWordBoundaries.clear();
1335     
1336     VisiblePosition wordBreak;
1337     int offsetOfWordBreak = invalidOffset;
1338     while (1) {
1339         bool isLastWordBreakInBox = false;
1340         wordBreak = nextWordBreakInBoxInsideBlockWithDifferentDirectionality(box, wordBreak, offsetOfWordBreak, isLastWordBreakInBox);
1341         if (wordBreak.isNotNull()) {
1342             WordBoundaryEntry wordBoundaryEntry(wordBreak, offsetOfWordBreak);
1343             orderedWordBoundaries.append(wordBoundaryEntry);
1344         }
1345         if (isLastWordBreakInBox)
1346             break;
1347     }
1348 }
1349     
1350 static VisiblePosition previousWordBreakInBox(const InlineBox* box, int offset, TextDirection blockDirection)
1351 {
1352     int offsetOfWordBreak = 0;
1353     VisiblePosition wordBreak;
1354     while (true) {
1355         if (box->direction() == blockDirection)
1356             wordBreak = previousWordBreakInBoxInsideBlockWithSameDirectionality(box, wordBreak, offsetOfWordBreak);
1357         // FIXME: Implement the 'else' case when the box direction is not equal to the block direction.
1358         if (wordBreak.isNull())
1359             break;
1360         if (offset == invalidOffset || offsetOfWordBreak != offset)
1361             return wordBreak;
1362     }        
1363     return VisiblePosition();
1364 }
1365
1366 static int greatestValueUnder(int offset, bool boxAndBlockAreInSameDirection, const WordBoundaryVector& orderedWordBoundaries)
1367 {
1368     if (!orderedWordBoundaries.size())
1369         return invalidOffset;
1370     // FIXME: binary search.
1371     if (boxAndBlockAreInSameDirection) {
1372         for (unsigned i = 0; i < orderedWordBoundaries.size(); ++i) {
1373             if (orderedWordBoundaries[i].offsetInInlineBox < offset)
1374                 return i;
1375         }
1376         return invalidOffset;
1377     }
1378     for (int i = orderedWordBoundaries.size() - 1; i >= 0; --i) {
1379         if (orderedWordBoundaries[i].offsetInInlineBox < offset)
1380             return i;
1381     }
1382     return invalidOffset;
1383 }
1384
1385 static int smallestOffsetAbove(int offset, bool boxAndBlockAreInSameDirection, const WordBoundaryVector& orderedWordBoundaries)
1386 {
1387     if (!orderedWordBoundaries.size())
1388         return invalidOffset;
1389     // FIXME: binary search.
1390     if (boxAndBlockAreInSameDirection) {
1391         for (int i = orderedWordBoundaries.size() - 1; i >= 0; --i) {
1392             if (orderedWordBoundaries[i].offsetInInlineBox > offset)
1393                 return i;
1394         }
1395         return invalidOffset;
1396     }
1397     for (unsigned i = 0; i < orderedWordBoundaries.size(); ++i) {
1398         if (orderedWordBoundaries[i].offsetInInlineBox > offset)
1399             return i;
1400     }
1401     return invalidOffset;
1402 }
1403  
1404 static VisiblePosition leftWordBoundary(const InlineBox* box, int offset, TextDirection blockDirection)
1405 {
1406     VisiblePosition wordBreak;
1407     for  (const InlineBox* adjacentBox = box; adjacentBox; adjacentBox = adjacentBox->prevLeafChild()) {
1408         if (blockDirection == LTR) 
1409             wordBreak = previousWordBreakInBox(adjacentBox, adjacentBox == box ? offset : invalidOffset, blockDirection);
1410         // FIXME: Implement the "else" case.
1411         if (wordBreak.isNotNull())
1412             return wordBreak;
1413     }
1414     return VisiblePosition();
1415 }
1416  
1417 static VisiblePosition rightWordBoundary(const InlineBox* box, int offset, TextDirection blockDirection)
1418 {
1419     
1420     VisiblePosition wordBreak;
1421     for (const InlineBox* adjacentBox = box; adjacentBox; adjacentBox = adjacentBox->nextLeafChild()) {
1422         if (blockDirection == RTL)
1423             wordBreak = previousWordBreakInBox(adjacentBox, adjacentBox == box ? offset : invalidOffset, blockDirection);
1424         // FIXME: Implement the "else" case.
1425         if (!wordBreak.isNull())
1426             return wordBreak;
1427     }
1428     return VisiblePosition();
1429 }
1430     
1431 static bool positionIsInsideBox(const VisiblePosition& wordBreak, const InlineBox* box)
1432 {
1433     InlineBox* boxOfWordBreak;
1434     int offsetOfWordBreak;
1435     wordBreak.getInlineBoxAndOffset(boxOfWordBreak, offsetOfWordBreak);
1436     return box == boxOfWordBreak && offsetOfWordBreak != box->caretMaxOffset() && offsetOfWordBreak != box->caretMinOffset();
1437 }
1438
1439 static VisiblePosition positionBeforeNextWord(const VisiblePosition& position)
1440 {
1441     VisiblePosition positionAfterCurrentWord = nextWordPosition(position);
1442     VisiblePosition positionAfterNextWord = nextWordPosition(positionAfterCurrentWord);
1443     if (positionAfterCurrentWord == positionAfterNextWord)
1444         return positionAfterCurrentWord;
1445     return previousWordPosition(positionAfterNextWord);
1446 }
1447
1448 static VisiblePosition positionAfterPreviousWord(const VisiblePosition& position)
1449 {
1450     VisiblePosition positionBeforeCurrentWord = previousWordPosition(position);
1451     VisiblePosition positionBeforePreviousWord = previousWordPosition(positionBeforeCurrentWord);
1452     if (positionBeforeCurrentWord == positionBeforePreviousWord)
1453         return positionBeforeCurrentWord;
1454     return nextWordPosition(positionBeforePreviousWord);
1455 }
1456     
1457 VisiblePosition leftWordPosition(const VisiblePosition& visiblePosition)
1458 {
1459     InlineBox* box;
1460     int offset;
1461     visiblePosition.getInlineBoxAndOffset(box, offset);
1462     TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
1463     
1464     // FIXME: If the box's directionality is the same as that of the enclosing block, when the offset is at the box boundary
1465     // 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,
1466     // when offset is at box's caretMinOffset and the direction is DirectionRight, should it be taken care as a general case?
1467     if (offset == box->caretLeftmostOffset())
1468         return leftWordBoundary(box->prevLeafChild(), invalidOffset, blockDirection);
1469     if (offset == box->caretRightmostOffset())
1470         return leftWordBoundary(box, offset, blockDirection);
1471     
1472     
1473     VisiblePosition wordBreak;
1474     if (box->direction() == blockDirection) {
1475         if (blockDirection == RTL)
1476             wordBreak = positionBeforeNextWord(visiblePosition);
1477         else
1478             wordBreak = previousWordPosition(visiblePosition);
1479     } else {
1480         if (blockDirection == RTL)
1481             wordBreak = positionAfterPreviousWord(visiblePosition);
1482         else
1483             wordBreak = nextWordPosition(visiblePosition);
1484     }
1485     if (positionIsInsideBox(wordBreak, box))
1486         return wordBreak;
1487     
1488     WordBoundaryVector orderedWordBoundaries;
1489     if (box->direction() == blockDirection)
1490         collectWordBreaksInBoxInsideBlockWithSameDirectionality(box, orderedWordBoundaries);
1491     else
1492         collectWordBreaksInBoxInsideBlockWithDifferntDirectionality(box, orderedWordBoundaries);
1493
1494     int index = box->isLeftToRightDirection() ? greatestValueUnder(offset, blockDirection == LTR, orderedWordBoundaries) :
1495         smallestOffsetAbove(offset, blockDirection == RTL, orderedWordBoundaries);
1496     if (index != invalidOffset)
1497         return orderedWordBoundaries[index].visiblePosition;
1498     
1499     return leftWordBoundary(box->prevLeafChild(), invalidOffset, blockDirection);
1500 }
1501
1502 VisiblePosition rightWordPosition(const VisiblePosition& visiblePosition)
1503 {
1504     InlineBox* box;
1505     int offset;
1506     visiblePosition.getInlineBoxAndOffset(box, offset);
1507     TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
1508     
1509     if (offset == box->caretLeftmostOffset())
1510         return rightWordBoundary(box, offset, blockDirection);
1511     if (offset == box->caretRightmostOffset())
1512         return rightWordBoundary(box->nextLeafChild(), invalidOffset, blockDirection);
1513  
1514     VisiblePosition wordBreak;
1515     if (box->direction() == blockDirection) {
1516         if (blockDirection == LTR)
1517             wordBreak = positionBeforeNextWord(visiblePosition);
1518         else
1519             wordBreak = previousWordPosition(visiblePosition);
1520     } else {
1521         if (blockDirection == LTR)
1522             wordBreak = positionAfterPreviousWord(visiblePosition);
1523         else
1524             wordBreak = nextWordPosition(visiblePosition);
1525     } 
1526     if (positionIsInsideBox(wordBreak, box))
1527         return wordBreak;
1528     
1529     WordBoundaryVector orderedWordBoundaries;
1530     if (box->direction() == blockDirection)
1531         collectWordBreaksInBoxInsideBlockWithSameDirectionality(box, orderedWordBoundaries);
1532     else
1533         collectWordBreaksInBoxInsideBlockWithDifferntDirectionality(box, orderedWordBoundaries);
1534     int index = box->isLeftToRightDirection() ? smallestOffsetAbove(offset, blockDirection == LTR, orderedWordBoundaries) :
1535         greatestValueUnder(offset, blockDirection == RTL, orderedWordBoundaries);
1536     if (index != invalidOffset)
1537         return orderedWordBoundaries[index].visiblePosition;
1538     
1539     return rightWordBoundary(box->nextLeafChild(), invalidOffset, blockDirection);
1540 }
1541
1542 }