Source/WebCore/editing/visible_units.cpp

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