2011-04-20 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     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     // Given RTL box "ABC DEF" either follows a LTR box or is the first visual box in an LTR block as an example,
1279     // 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)",
1280     // where the number in parenthesis represents offset in visiblePosition. 
1281     // 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.
1282     // But nextWordPosition() of offset 7 is offset 11, which should be ignored, 
1283     // and the position at offset 0 should be manually added as the last word break within the box.
1284     if (wordBreak != previousWordBreak && positionIsVisuallyOrderedInBoxInBlockWithDifferentDirectionality(wordBreak, box, offsetOfWordBreak)) {
1285         isLastWordBreakInBox = false;
1286         return wordBreak;
1287     }
1288     
1289     isLastWordBreakInBox = true;
1290     return lastWordBreakInBox(box, offsetOfWordBreak);
1291 }
1292
1293 struct WordBoundaryEntry {
1294     WordBoundaryEntry()
1295         : offsetInInlineBox(invalidOffset) 
1296     { 
1297     }
1298
1299     WordBoundaryEntry(const VisiblePosition& position, int offset)
1300         : visiblePosition(position)
1301         , offsetInInlineBox(offset) 
1302     { 
1303     }
1304
1305     VisiblePosition visiblePosition;
1306     int offsetInInlineBox;
1307 };
1308     
1309 typedef Vector<WordBoundaryEntry, 50> WordBoundaryVector;
1310     
1311 static void collectWordBreaksInBoxInsideBlockWithSameDirectionality(const InlineBox* box, WordBoundaryVector& orderedWordBoundaries)
1312 {
1313     orderedWordBoundaries.clear();
1314     
1315     VisiblePosition wordBreak;
1316     int offsetOfWordBreak = invalidOffset;
1317     while (1) {
1318         wordBreak = previousWordBreakInBoxInsideBlockWithSameDirectionality(box, wordBreak, offsetOfWordBreak);
1319         if (wordBreak.isNull())
1320             break;
1321         WordBoundaryEntry wordBoundaryEntry(wordBreak, offsetOfWordBreak);
1322         orderedWordBoundaries.append(wordBoundaryEntry);
1323     }
1324 }
1325
1326 static void collectWordBreaksInBoxInsideBlockWithDifferntDirectionality(const InlineBox* box, WordBoundaryVector& orderedWordBoundaries)
1327 {
1328     orderedWordBoundaries.clear();
1329     
1330     VisiblePosition wordBreak;
1331     int offsetOfWordBreak = invalidOffset;
1332     while (1) {
1333         bool isLastWordBreakInBox = false;
1334         wordBreak = nextWordBreakInBoxInsideBlockWithDifferentDirectionality(box, wordBreak, offsetOfWordBreak, isLastWordBreakInBox);
1335         if (wordBreak.isNotNull()) {
1336             WordBoundaryEntry wordBoundaryEntry(wordBreak, offsetOfWordBreak);
1337             orderedWordBoundaries.append(wordBoundaryEntry);
1338         }
1339         if (isLastWordBreakInBox)
1340             break;
1341     }
1342 }
1343
1344 static void collectWordBreaksInBox(const InlineBox* box, WordBoundaryVector& orderedWordBoundaries, TextDirection blockDirection)
1345 {
1346     if (box->direction() == blockDirection)
1347         collectWordBreaksInBoxInsideBlockWithSameDirectionality(box, orderedWordBoundaries);
1348     else
1349         collectWordBreaksInBoxInsideBlockWithDifferntDirectionality(box, orderedWordBoundaries);        
1350 }
1351     
1352 static VisiblePosition previousWordBoundaryInBox(const InlineBox* box, int offset)
1353 {
1354     int offsetOfWordBreak = 0;
1355     VisiblePosition wordBreak;
1356     while (true) {
1357         wordBreak = previousWordBreakInBoxInsideBlockWithSameDirectionality(box, wordBreak, offsetOfWordBreak);
1358         if (wordBreak.isNull())
1359             break;
1360         if (offset == invalidOffset || offsetOfWordBreak != offset)
1361             return wordBreak;
1362     }        
1363     return VisiblePosition();
1364 }
1365
1366 static VisiblePosition nextWordBoundaryInBox(const InlineBox* box, int offset)
1367 {
1368     int offsetOfWordBreak = 0;
1369     VisiblePosition wordBreak;
1370     bool isLastWordBreakInBox = false;
1371     do {
1372         wordBreak = nextWordBreakInBoxInsideBlockWithDifferentDirectionality(box, wordBreak, offsetOfWordBreak, isLastWordBreakInBox);
1373         if (wordBreak.isNotNull() && (offset == invalidOffset || offsetOfWordBreak != offset))
1374             return wordBreak;
1375     } while (!isLastWordBreakInBox);       
1376     return VisiblePosition();
1377 }
1378     
1379 static VisiblePosition visuallyLastWordBoundaryInBox(const InlineBox* box, int offset, TextDirection blockDirection)
1380 {
1381     WordBoundaryVector orderedWordBoundaries;
1382     collectWordBreaksInBox(box, orderedWordBoundaries, blockDirection);
1383     if (!orderedWordBoundaries.size()) 
1384         return VisiblePosition();
1385     if (offset == invalidOffset || orderedWordBoundaries[orderedWordBoundaries.size() - 1].offsetInInlineBox != offset)
1386         return orderedWordBoundaries[orderedWordBoundaries.size() - 1].visiblePosition;
1387     if (orderedWordBoundaries.size() > 1)
1388         return orderedWordBoundaries[orderedWordBoundaries.size() - 2].visiblePosition;
1389     return VisiblePosition();
1390 }
1391         
1392 static int greatestValueUnder(int offset, bool boxAndBlockAreInSameDirection, const WordBoundaryVector& orderedWordBoundaries)
1393 {
1394     if (!orderedWordBoundaries.size())
1395         return invalidOffset;
1396     // FIXME: binary search.
1397     if (boxAndBlockAreInSameDirection) {
1398         for (unsigned i = 0; i < orderedWordBoundaries.size(); ++i) {
1399             if (orderedWordBoundaries[i].offsetInInlineBox < offset)
1400                 return i;
1401         }
1402         return invalidOffset;
1403     }
1404     for (int i = orderedWordBoundaries.size() - 1; i >= 0; --i) {
1405         if (orderedWordBoundaries[i].offsetInInlineBox < offset)
1406             return i;
1407     }
1408     return invalidOffset;
1409 }
1410
1411 static int smallestOffsetAbove(int offset, bool boxAndBlockAreInSameDirection, const WordBoundaryVector& orderedWordBoundaries)
1412 {
1413     if (!orderedWordBoundaries.size())
1414         return invalidOffset;
1415     // FIXME: binary search.
1416     if (boxAndBlockAreInSameDirection) {
1417         for (int i = orderedWordBoundaries.size() - 1; i >= 0; --i) {
1418             if (orderedWordBoundaries[i].offsetInInlineBox > offset)
1419                 return i;
1420         }
1421         return invalidOffset;
1422     }
1423     for (unsigned i = 0; i < orderedWordBoundaries.size(); ++i) {
1424         if (orderedWordBoundaries[i].offsetInInlineBox > offset)
1425             return i;
1426     }
1427     return invalidOffset;
1428 }
1429
1430 static VisiblePosition leftWordBoundary(const InlineBox* box, int offset, TextDirection blockDirection)
1431 {
1432     VisiblePosition wordBreak;
1433     for  (const InlineBox* adjacentBox = box; adjacentBox; adjacentBox = adjacentBox->prevLeafChild()) {
1434         if (blockDirection == LTR) {
1435             if (box->isLeftToRightDirection()) 
1436                 wordBreak = previousWordBoundaryInBox(adjacentBox, adjacentBox == box ? offset : invalidOffset);
1437             else
1438                 wordBreak = nextWordBoundaryInBox(adjacentBox, adjacentBox == box ? offset : invalidOffset);
1439         } else 
1440             wordBreak = visuallyLastWordBoundaryInBox(adjacentBox, adjacentBox == box ? offset : invalidOffset, blockDirection);            
1441         if (wordBreak.isNotNull())
1442             return wordBreak;
1443     }
1444     return VisiblePosition();
1445 }
1446  
1447 static VisiblePosition rightWordBoundary(const InlineBox* box, int offset, TextDirection blockDirection)
1448 {
1449     
1450     VisiblePosition wordBreak;
1451     for (const InlineBox* adjacentBox = box; adjacentBox; adjacentBox = adjacentBox->nextLeafChild()) {
1452         if (blockDirection == RTL) {
1453             if (box->isLeftToRightDirection())
1454                 wordBreak = nextWordBoundaryInBox(adjacentBox, adjacentBox == box ? offset : invalidOffset);
1455             else
1456                 wordBreak = previousWordBoundaryInBox(adjacentBox, adjacentBox == box ? offset : invalidOffset);
1457         } else 
1458             wordBreak = visuallyLastWordBoundaryInBox(adjacentBox, adjacentBox == box ? offset : invalidOffset, blockDirection);            
1459         if (!wordBreak.isNull())
1460             return wordBreak;
1461     }
1462     return VisiblePosition();
1463 }
1464     
1465 static bool positionIsInsideBox(const VisiblePosition& wordBreak, const InlineBox* box)
1466 {
1467     InlineBox* boxOfWordBreak;
1468     int offsetOfWordBreak;
1469     wordBreak.getInlineBoxAndOffset(boxOfWordBreak, offsetOfWordBreak);
1470     return box == boxOfWordBreak && offsetOfWordBreak != box->caretMaxOffset() && offsetOfWordBreak != box->caretMinOffset();
1471 }
1472
1473 static VisiblePosition positionBeforeNextWord(const VisiblePosition& position)
1474 {
1475     VisiblePosition positionAfterCurrentWord = nextWordPosition(position);
1476     VisiblePosition positionAfterNextWord = nextWordPosition(positionAfterCurrentWord);
1477     if (positionAfterCurrentWord == positionAfterNextWord)
1478         return positionAfterCurrentWord;
1479     return previousWordPosition(positionAfterNextWord);
1480 }
1481
1482 static VisiblePosition positionAfterPreviousWord(const VisiblePosition& position)
1483 {
1484     VisiblePosition positionBeforeCurrentWord = previousWordPosition(position);
1485     VisiblePosition positionBeforePreviousWord = previousWordPosition(positionBeforeCurrentWord);
1486     if (positionBeforeCurrentWord == positionBeforePreviousWord)
1487         return positionBeforeCurrentWord;
1488     return nextWordPosition(positionBeforePreviousWord);
1489 }
1490     
1491 VisiblePosition leftWordPosition(const VisiblePosition& visiblePosition)
1492 {
1493     InlineBox* box;
1494     int offset;
1495     visiblePosition.getInlineBoxAndOffset(box, offset);
1496     TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
1497     
1498     // FIXME: If the box's directionality is the same as that of the enclosing block, when the offset is at the box boundary
1499     // 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,
1500     // when offset is at box's caretMinOffset and the direction is DirectionRight, should it be taken care as a general case?
1501     if (offset == box->caretLeftmostOffset())
1502         return leftWordBoundary(box->prevLeafChild(), invalidOffset, blockDirection);
1503     if (offset == box->caretRightmostOffset())
1504         return leftWordBoundary(box, offset, blockDirection);
1505     
1506     
1507     VisiblePosition wordBreak;
1508     if (box->direction() == blockDirection) {
1509         if (blockDirection == RTL)
1510             wordBreak = positionBeforeNextWord(visiblePosition);
1511         else
1512             wordBreak = previousWordPosition(visiblePosition);
1513     } else {
1514         if (blockDirection == RTL)
1515             wordBreak = positionAfterPreviousWord(visiblePosition);
1516         else
1517             wordBreak = nextWordPosition(visiblePosition);
1518     }
1519     if (positionIsInsideBox(wordBreak, box))
1520         return wordBreak;
1521     
1522     WordBoundaryVector orderedWordBoundaries;
1523     collectWordBreaksInBox(box, orderedWordBoundaries, blockDirection);
1524
1525     int index = box->isLeftToRightDirection() ? greatestValueUnder(offset, blockDirection == LTR, orderedWordBoundaries) :
1526         smallestOffsetAbove(offset, blockDirection == RTL, orderedWordBoundaries);
1527     if (index != invalidOffset)
1528         return orderedWordBoundaries[index].visiblePosition;
1529     
1530     return leftWordBoundary(box->prevLeafChild(), invalidOffset, blockDirection);
1531 }
1532
1533 VisiblePosition rightWordPosition(const VisiblePosition& visiblePosition)
1534 {
1535     InlineBox* box;
1536     int offset;
1537     visiblePosition.getInlineBoxAndOffset(box, offset);
1538     TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
1539     
1540     if (offset == box->caretLeftmostOffset())
1541         return rightWordBoundary(box, offset, blockDirection);
1542     if (offset == box->caretRightmostOffset())
1543         return rightWordBoundary(box->nextLeafChild(), invalidOffset, blockDirection);
1544  
1545     VisiblePosition wordBreak;
1546     if (box->direction() == blockDirection) {
1547         if (blockDirection == LTR)
1548             wordBreak = positionBeforeNextWord(visiblePosition);
1549         else
1550             wordBreak = previousWordPosition(visiblePosition);
1551     } else {
1552         if (blockDirection == LTR)
1553             wordBreak = positionAfterPreviousWord(visiblePosition);
1554         else
1555             wordBreak = nextWordPosition(visiblePosition);
1556     } 
1557     if (positionIsInsideBox(wordBreak, box))
1558         return wordBreak;
1559     
1560     WordBoundaryVector orderedWordBoundaries;
1561     collectWordBreaksInBox(box, orderedWordBoundaries, blockDirection);
1562     
1563     int index = box->isLeftToRightDirection() ? smallestOffsetAbove(offset, blockDirection == LTR, orderedWordBoundaries) :
1564         greatestValueUnder(offset, blockDirection == RTL, orderedWordBoundaries);
1565     if (index != invalidOffset)
1566         return orderedWordBoundaries[index].visiblePosition;
1567     
1568     return rightWordBoundary(box->nextLeafChild(), invalidOffset, blockDirection);
1569 }
1570
1571 }