Source/WebCore/editing/VisibleUnits.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 "VisibleUnits.h"
  28
  29 #include "Document.h"
  30 #include "Element.h"
  31 #include "HTMLNames.h"
  32 #include "InlineTextBox.h"
  33 #include "NodeTraversal.h"
  34 #include "RenderBlockFlow.h"
  35 #include "RenderObject.h"
  36 #include "RenderedPosition.h"
  37 #include "Text.h"
  38 #include "TextBoundaries.h"
  39 #include "TextBreakIterator.h"
  40 #include "TextIterator.h"
  41 #include "VisibleSelection.h"
  42 #include "htmlediting.h"
  43
  44 namespace WebCore {
  45
  46 using namespace HTMLNames;
  47 using namespace WTF::Unicode;
  48
  49 static Node* previousLeafWithSameEditability(Node* node, EditableType editableType)
  50 {
  51     bool editable = node->hasEditableStyle(editableType);
  52     node = previousLeafNode(node);
  53     while (node) {
  54         if (editable == node->hasEditableStyle(editableType))
  55             return node;
  56         node = previousLeafNode(node);
  57     }
  58     return nullptr;
  59 }
  60
  61 static Node* nextLeafWithSameEditability(Node* node, EditableType editableType = ContentIsEditable)
  62 {
  63     if (!node)
  64         return nullptr;
  65
  66     bool editable = node->hasEditableStyle(editableType);
  67     node = nextLeafNode(node);
  68     while (node) {
  69         if (editable == node->hasEditableStyle(editableType))
  70             return node;
  71         node = nextLeafNode(node);
  72     }
  73     return nullptr;
  74 }
  75
  76 // FIXME: consolidate with code in previousLinePosition.
  77 static Position previousRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
  78 {
  79     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
  80     Node* previousNode = previousLeafWithSameEditability(node, editableType);
  81
  82     while (previousNode && (!previousNode->renderer() || inSameLine(firstPositionInOrBeforeNode(previousNode), visiblePosition)))
  83         previousNode = previousLeafWithSameEditability(previousNode, editableType);
  84
  85     while (previousNode && !previousNode->isShadowRoot()) {
  86         if (highestEditableRoot(firstPositionInOrBeforeNode(previousNode), editableType) != highestRoot)
  87             break;
  88
  89         Position pos = previousNode->hasTagName(brTag) ? positionBeforeNode(previousNode) :
  90             createLegacyEditingPosition(previousNode, caretMaxOffset(previousNode));
  91
  92         if (pos.isCandidate())
  93             return pos;
  94
  95         previousNode = previousLeafWithSameEditability(previousNode, editableType);
  96     }
  97     return Position();
  98 }
  99
 100 static Position nextRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
 101 {
 102     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
 103     Node* nextNode = nextLeafWithSameEditability(node, editableType);
 104     while (nextNode && (!nextNode->renderer() || inSameLine(firstPositionInOrBeforeNode(nextNode), visiblePosition)))
 105         nextNode = nextLeafWithSameEditability(nextNode, ContentIsEditable);
 106
 107     while (nextNode && !nextNode->isShadowRoot()) {
 108         if (highestEditableRoot(firstPositionInOrBeforeNode(nextNode), editableType) != highestRoot)
 109             break;
 110
 111         Position pos;
 112         pos = createLegacyEditingPosition(nextNode, caretMinOffset(nextNode));
 113
 114         if (pos.isCandidate())
 115             return pos;
 116
 117         nextNode = nextLeafWithSameEditability(nextNode, editableType);
 118     }
 119     return Position();
 120 }
 121
 122 class CachedLogicallyOrderedLeafBoxes {
 123 public:
 124     CachedLogicallyOrderedLeafBoxes();
 125
 126     const InlineBox* previousTextOrLineBreakBox(const RootInlineBox*, const InlineTextBox*);
 127     const InlineBox* nextTextOrLineBreakBox(const RootInlineBox*, const InlineTextBox*);
 128
 129     size_t size() const { return m_leafBoxes.size(); }
 130     const InlineBox* firstBox() const { return m_leafBoxes[0]; }
 131
 132 private:
 133     const Vector<InlineBox*>& collectBoxes(const RootInlineBox*);
 134     int boxIndexInLeaves(const InlineTextBox*) const;
 135
 136     const RootInlineBox* m_rootInlineBox;
 137     Vector<InlineBox*> m_leafBoxes;
 138 };
 139
 140 CachedLogicallyOrderedLeafBoxes::CachedLogicallyOrderedLeafBoxes() : m_rootInlineBox(0) { };
 141
 142 const InlineBox* CachedLogicallyOrderedLeafBoxes::previousTextOrLineBreakBox(const RootInlineBox* root, const InlineTextBox* box)
 143 {
 144     if (!root)
 145         return nullptr;
 146
 147     collectBoxes(root);
 148
 149     // If box is null, root is box's previous RootInlineBox, and previousBox is the last logical box in root.
 150     int boxIndex = m_leafBoxes.size() - 1;
 151     if (box)
 152         boxIndex = boxIndexInLeaves(box) - 1;
 153
 154     for (int i = boxIndex; i >= 0; --i) {
 155         InlineBox* box = m_leafBoxes[i];
 156         if (box->isInlineTextBox() || box->renderer().isBR())
 157             return box;
 158     }
 159
 160     return nullptr;
 161 }
 162
 163 const InlineBox* CachedLogicallyOrderedLeafBoxes::nextTextOrLineBreakBox(const RootInlineBox* root, const InlineTextBox* box)
 164 {
 165     if (!root)
 166         return nullptr;
 167
 168     collectBoxes(root);
 169
 170     // If box is null, root is box's next RootInlineBox, and nextBox is the first logical box in root.
 171     // Otherwise, root is box's RootInlineBox, and nextBox is the next logical box in the same line.
 172     size_t nextBoxIndex = 0;
 173     if (box)
 174         nextBoxIndex = boxIndexInLeaves(box) + 1;
 175
 176     for (size_t i = nextBoxIndex; i < m_leafBoxes.size(); ++i) {
 177         InlineBox* box = m_leafBoxes[i];
 178         if (box->isInlineTextBox() || box->renderer().isBR())
 179             return box;
 180     }
 181
 182     return nullptr;
 183 }
 184
 185 const Vector<InlineBox*>& CachedLogicallyOrderedLeafBoxes::collectBoxes(const RootInlineBox* root)
 186 {
 187     if (m_rootInlineBox != root) {
 188         m_rootInlineBox = root;
 189         m_leafBoxes.clear();
 190         root->collectLeafBoxesInLogicalOrder(m_leafBoxes);
 191     }
 192     return m_leafBoxes;
 193 }
 194
 195 int CachedLogicallyOrderedLeafBoxes::boxIndexInLeaves(const InlineTextBox* box) const
 196 {
 197     for (size_t i = 0; i < m_leafBoxes.size(); ++i) {
 198         if (box == m_leafBoxes[i])
 199             return i;
 200     }
 201     return 0;
 202 }
 203
 204 static const InlineBox* logicallyPreviousBox(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
 205     bool& previousBoxInDifferentBlock, CachedLogicallyOrderedLeafBoxes& leafBoxes)
 206 {
 207     const InlineBox* startBox = textBox;
 208
 209     const InlineBox* previousBox = leafBoxes.previousTextOrLineBreakBox(&startBox->root(), textBox);
 210     if (previousBox)
 211         return previousBox;
 212
 213     previousBox = leafBoxes.previousTextOrLineBreakBox(startBox->root().prevRootBox(), 0);
 214     if (previousBox)
 215         return previousBox;
 216
 217     while (1) {
 218         Node* startNode = startBox->renderer().nonPseudoNode();
 219         if (!startNode)
 220             break;
 221
 222         Position position = previousRootInlineBoxCandidatePosition(startNode, visiblePosition, ContentIsEditable);
 223         if (position.isNull())
 224             break;
 225
 226         RenderedPosition renderedPosition(position, DOWNSTREAM);
 227         RootInlineBox* previousRoot = renderedPosition.rootBox();
 228         if (!previousRoot)
 229             break;
 230
 231         previousBox = leafBoxes.previousTextOrLineBreakBox(previousRoot, 0);
 232         if (previousBox) {
 233             previousBoxInDifferentBlock = true;
 234             return previousBox;
 235         }
 236
 237         if (!leafBoxes.size())
 238             break;
 239         startBox = leafBoxes.firstBox();
 240     }
 241     return 0;
 242 }
 243
 244
 245 static const InlineBox* logicallyNextBox(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
 246     bool& nextBoxInDifferentBlock, CachedLogicallyOrderedLeafBoxes& leafBoxes)
 247 {
 248     const InlineBox* startBox = textBox;
 249
 250     const InlineBox* nextBox = leafBoxes.nextTextOrLineBreakBox(&startBox->root(), textBox);
 251     if (nextBox)
 252         return nextBox;
 253
 254     nextBox = leafBoxes.nextTextOrLineBreakBox(startBox->root().nextRootBox(), 0);
 255     if (nextBox)
 256         return nextBox;
 257
 258     while (1) {
 259         Node* startNode = startBox->renderer().nonPseudoNode();
 260         if (!startNode)
 261             break;
 262
 263         Position position = nextRootInlineBoxCandidatePosition(startNode, visiblePosition, ContentIsEditable);
 264         if (position.isNull())
 265             break;
 266
 267         RenderedPosition renderedPosition(position, DOWNSTREAM);
 268         RootInlineBox* nextRoot = renderedPosition.rootBox();
 269         if (!nextRoot)
 270             break;
 271
 272         nextBox = leafBoxes.nextTextOrLineBreakBox(nextRoot, 0);
 273         if (nextBox) {
 274             nextBoxInDifferentBlock = true;
 275             return nextBox;
 276         }
 277
 278         if (!leafBoxes.size())
 279             break;
 280         startBox = leafBoxes.firstBox();
 281     }
 282     return 0;
 283 }
 284
 285 static TextBreakIterator* wordBreakIteratorForMinOffsetBoundary(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
 286     int& previousBoxLength, bool& previousBoxInDifferentBlock, Vector<UChar, 1024>& string, CachedLogicallyOrderedLeafBoxes& leafBoxes)
 287 {
 288     previousBoxInDifferentBlock = false;
 289
 290     // FIXME: Handle the case when we don't have an inline text box.
 291     const InlineBox* previousBox = logicallyPreviousBox(visiblePosition, textBox, previousBoxInDifferentBlock, leafBoxes);
 292
 293     int len = 0;
 294     string.clear();
 295     if (previousBox && previousBox->isInlineTextBox()) {
 296         const InlineTextBox* previousTextBox = toInlineTextBox(previousBox);
 297         previousBoxLength = previousTextBox->len();
 298         string.append(previousTextBox->renderer().text()->deprecatedCharacters() + previousTextBox->start(), previousBoxLength);
 299         len += previousBoxLength;
 300     }
 301     string.append(textBox->renderer().text()->deprecatedCharacters() + textBox->start(), textBox->len());
 302     len += textBox->len();
 303
 304     return wordBreakIterator(StringView(string.data(), len));
 305 }
 306
 307 static TextBreakIterator* wordBreakIteratorForMaxOffsetBoundary(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
 308     bool& nextBoxInDifferentBlock, Vector<UChar, 1024>& string, CachedLogicallyOrderedLeafBoxes& leafBoxes)
 309 {
 310     nextBoxInDifferentBlock = false;
 311
 312     // FIXME: Handle the case when we don't have an inline text box.
 313     const InlineBox* nextBox = logicallyNextBox(visiblePosition, textBox, nextBoxInDifferentBlock, leafBoxes);
 314
 315     int len = 0;
 316     string.clear();
 317     string.append(textBox->renderer().text()->deprecatedCharacters() + textBox->start(), textBox->len());
 318     len += textBox->len();
 319     if (nextBox && nextBox->isInlineTextBox()) {
 320         const InlineTextBox* nextTextBox = toInlineTextBox(nextBox);
 321         string.append(nextTextBox->renderer().text()->deprecatedCharacters() + nextTextBox->start(), nextTextBox->len());
 322         len += nextTextBox->len();
 323     }
 324
 325     return wordBreakIterator(StringView(string.data(), len));
 326 }
 327
 328 static bool isLogicalStartOfWord(TextBreakIterator* iter, int position, bool hardLineBreak)
 329 {
 330     bool boundary = hardLineBreak ? true : isTextBreak(iter, position);
 331     if (!boundary)
 332         return false;
 333
 334     textBreakFollowing(iter, position);
 335     // isWordTextBreak returns true after moving across a word and false after moving across a punctuation/space.
 336     return isWordTextBreak(iter);
 337 }
 338
 339 static bool islogicalEndOfWord(TextBreakIterator* iter, int position, bool hardLineBreak)
 340 {
 341     bool boundary = isTextBreak(iter, position);
 342     return (hardLineBreak || boundary) && isWordTextBreak(iter);
 343 }
 344
 345 enum CursorMovementDirection { MoveLeft, MoveRight };
 346
 347 static VisiblePosition visualWordPosition(const VisiblePosition& visiblePosition, CursorMovementDirection direction,
 348     bool skipsSpaceWhenMovingRight)
 349 {
 350     if (visiblePosition.isNull())
 351         return VisiblePosition();
 352
 353     TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
 354     InlineBox* previouslyVisitedBox = 0;
 355     VisiblePosition current = visiblePosition;
 356     TextBreakIterator* iter = 0;
 357
 358     CachedLogicallyOrderedLeafBoxes leafBoxes;
 359     Vector<UChar, 1024> string;
 360
 361     while (1) {
 362         VisiblePosition adjacentCharacterPosition = direction == MoveRight ? current.right(true) : current.left(true);
 363         if (adjacentCharacterPosition == current || adjacentCharacterPosition.isNull())
 364             return VisiblePosition();
 365
 366         InlineBox* box;
 367         int offsetInBox;
 368         adjacentCharacterPosition.deepEquivalent().getInlineBoxAndOffset(UPSTREAM, box, offsetInBox);
 369
 370         if (!box)
 371             break;
 372         if (!box->isInlineTextBox()) {
 373             current = adjacentCharacterPosition;
 374             continue;
 375         }
 376
 377         InlineTextBox* textBox = toInlineTextBox(box);
 378         int previousBoxLength = 0;
 379         bool previousBoxInDifferentBlock = false;
 380         bool nextBoxInDifferentBlock = false;
 381         bool movingIntoNewBox = previouslyVisitedBox != box;
 382
 383         if (offsetInBox == box->caretMinOffset())
 384             iter = wordBreakIteratorForMinOffsetBoundary(visiblePosition, textBox, previousBoxLength, previousBoxInDifferentBlock, string, leafBoxes);
 385         else if (offsetInBox == box->caretMaxOffset())
 386             iter = wordBreakIteratorForMaxOffsetBoundary(visiblePosition, textBox, nextBoxInDifferentBlock, string, leafBoxes);
 387         else if (movingIntoNewBox) {
 388             iter = wordBreakIterator(StringView(textBox->renderer().text()).substring(textBox->start(), textBox->len()));
 389             previouslyVisitedBox = box;
 390         }
 391
 392         if (!iter)
 393             break;
 394
 395         textBreakFirst(iter);
 396         int offsetInIterator = offsetInBox - textBox->start() + previousBoxLength;
 397
 398         bool isWordBreak;
 399         bool boxHasSameDirectionalityAsBlock = box->direction() == blockDirection;
 400         bool movingBackward = (direction == MoveLeft && box->direction() == LTR) || (direction == MoveRight && box->direction() == RTL);
 401         if ((skipsSpaceWhenMovingRight && boxHasSameDirectionalityAsBlock)
 402             || (!skipsSpaceWhenMovingRight && movingBackward)) {
 403             bool logicalStartInRenderer = offsetInBox == static_cast<int>(textBox->start()) && previousBoxInDifferentBlock;
 404             isWordBreak = isLogicalStartOfWord(iter, offsetInIterator, logicalStartInRenderer);
 405         } else {
 406             bool logicalEndInRenderer = offsetInBox == static_cast<int>(textBox->start() + textBox->len()) && nextBoxInDifferentBlock;
 407             isWordBreak = islogicalEndOfWord(iter, offsetInIterator, logicalEndInRenderer);
 408         }
 409
 410         if (isWordBreak)
 411             return adjacentCharacterPosition;
 412
 413         current = adjacentCharacterPosition;
 414     }
 415     return VisiblePosition();
 416 }
 417
 418 VisiblePosition leftWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
 419 {
 420     VisiblePosition leftWordBreak = visualWordPosition(visiblePosition, MoveLeft, skipsSpaceWhenMovingRight);
 421     leftWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(leftWordBreak);
 422
 423     // FIXME: How should we handle a non-editable position?
 424     if (leftWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
 425         TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
 426         leftWordBreak = blockDirection == LTR ? startOfEditableContent(visiblePosition) : endOfEditableContent(visiblePosition);
 427     }
 428     return leftWordBreak;
 429 }
 430
 431 VisiblePosition rightWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
 432 {
 433     VisiblePosition rightWordBreak = visualWordPosition(visiblePosition, MoveRight, skipsSpaceWhenMovingRight);
 434     rightWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(rightWordBreak);
 435
 436     // FIXME: How should we handle a non-editable position?
 437     if (rightWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
 438         TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
 439         rightWordBreak = blockDirection == LTR ? endOfEditableContent(visiblePosition) : startOfEditableContent(visiblePosition);
 440     }
 441     return rightWordBreak;
 442 }
 443
 444
 445 enum BoundarySearchContextAvailability { DontHaveMoreContext, MayHaveMoreContext };
 446
 447 typedef unsigned (*BoundarySearchFunction)(StringView, unsigned offset, BoundarySearchContextAvailability, bool& needMoreContext);
 448
 449 static void prepend(Vector<UChar, 1024>& buffer, StringView string)
 450 {
 451     unsigned oldSize = buffer.size();
 452     unsigned length = string.length();
 453     buffer.grow(oldSize + length);
 454     memmove(buffer.data() + length, buffer.data(), oldSize * sizeof(UChar));
 455     for (unsigned i = 0; i < length; ++i)
 456         buffer[i] = string[i];
 457 }
 458
 459 static void prependRepeatedCharacter(Vector<UChar, 1024>& buffer, UChar character, unsigned count)
 460 {
 461     unsigned oldSize = buffer.size();
 462     buffer.grow(oldSize + count);
 463     memmove(buffer.data() + count, buffer.data(), oldSize * sizeof(UChar));
 464     for (unsigned i = 0; i < count; ++i)
 465         buffer[i] = character;
 466 }
 467
 468 static void append(Vector<UChar, 1024>& buffer, StringView string)
 469 {
 470     unsigned oldSize = buffer.size();
 471     unsigned length = string.length();
 472     buffer.grow(oldSize + length);
 473     for (unsigned i = 0; i < length; ++i)
 474         buffer[oldSize + i] = string[i];
 475 }
 476
 477 static void appendRepeatedCharacter(Vector<UChar, 1024>& buffer, UChar character, unsigned count)
 478 {
 479     unsigned oldSize = buffer.size();
 480     buffer.grow(oldSize + count);
 481     for (unsigned i = 0; i < count; ++i)
 482         buffer[oldSize + i] = character;
 483 }
 484
 485 static VisiblePosition previousBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
 486 {
 487     Position pos = c.deepEquivalent();
 488     Node* boundary = pos.parentEditingBoundary();
 489     if (!boundary)
 490         return VisiblePosition();
 491
 492     Document& boundaryDocument = boundary->document();
 493     Position start = createLegacyEditingPosition(boundary, 0).parentAnchoredEquivalent();
 494     Position end = pos.parentAnchoredEquivalent();
 495     RefPtr<Range> searchRange = Range::create(boundaryDocument);
 496
 497     Vector<UChar, 1024> string;
 498     unsigned suffixLength = 0;
 499
 500     ExceptionCode ec = 0;
 501     if (requiresContextForWordBoundary(c.characterBefore())) {
 502         RefPtr<Range> forwardsScanRange(boundaryDocument.createRange());
 503         forwardsScanRange->setEndAfter(boundary, ec);
 504         forwardsScanRange->setStart(end.deprecatedNode(), end.deprecatedEditingOffset(), ec);
 505         TextIterator forwardsIterator(forwardsScanRange.get());
 506         while (!forwardsIterator.atEnd()) {
 507             StringView text = forwardsIterator.text();
 508             unsigned i = endOfFirstWordBoundaryContext(text);
 509             append(string, text.substring(0, i));
 510             suffixLength += i;
 511             if (i < text.length())
 512                 break;
 513             forwardsIterator.advance();
 514         }
 515     }
 516
 517     searchRange->setStart(start.deprecatedNode(), start.deprecatedEditingOffset(), ec);
 518     searchRange->setEnd(end.deprecatedNode(), end.deprecatedEditingOffset(), ec);
 519
 520     ASSERT(!ec);
 521     if (ec)
 522         return VisiblePosition();
 523
 524     SimplifiedBackwardsTextIterator it(searchRange.get());
 525     unsigned next = 0;
 526     bool needMoreContext = false;
 527     while (!it.atEnd()) {
 528         bool inTextSecurityMode = it.node() && it.node()->renderer() && it.node()->renderer()->style().textSecurity() != TSNONE;
 529         // iterate to get chunks until the searchFunction returns a non-zero value.
 530         if (!inTextSecurityMode)
 531             prepend(string, it.text());
 532         else {
 533             // Treat bullets used in the text security mode as regular characters when looking for boundaries
 534             prependRepeatedCharacter(string, 'x', it.text().length());
 535         }
 536         if (string.size() > suffixLength) {
 537             next = searchFunction(StringView(string.data(), string.size()), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
 538             if (next > 1) // FIXME: This is a work around for https://webkit.org/b/115070. We need to provide more contexts in general case.
 539                 break;
 540         }
 541         it.advance();
 542     }
 543     if (needMoreContext && string.size() > suffixLength) {
 544         // The last search returned the beginning of the buffer and asked for more context,
 545         // but there is no earlier text. Force a search with what's available.
 546         next = searchFunction(StringView(string.data(), string.size()), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);
 547         ASSERT(!needMoreContext);
 548     }
 549
 550     if (!next)
 551         return VisiblePosition(it.atEnd() ? it.range()->startPosition() : pos, DOWNSTREAM);
 552
 553     Node* node = it.range()->startContainer();
 554     if ((node->isTextNode() && static_cast<int>(next) <= node->maxCharacterOffset()) || (node->renderer() && node->renderer()->isBR() && !next))
 555         // The next variable contains a usable index into a text node
 556         return VisiblePosition(createLegacyEditingPosition(node, next), DOWNSTREAM);
 557
 558     // Use the character iterator to translate the next value into a DOM position.
 559     BackwardsCharacterIterator charIt(searchRange.get());
 560     charIt.advance(string.size() - suffixLength - next);
 561     // FIXME: charIt can get out of shadow host.
 562     return VisiblePosition(charIt.range()->endPosition(), DOWNSTREAM);
 563 }
 564
 565 static VisiblePosition nextBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
 566 {
 567     Position pos = c.deepEquivalent();
 568     Node* boundary = pos.parentEditingBoundary();
 569     if (!boundary)
 570         return VisiblePosition();
 571
 572     Document& boundaryDocument = boundary->document();
 573     RefPtr<Range> searchRange(boundaryDocument.createRange());
 574     Position start(pos.parentAnchoredEquivalent());
 575
 576     Vector<UChar, 1024> string;
 577     unsigned prefixLength = 0;
 578
 579     if (requiresContextForWordBoundary(c.characterAfter())) {
 580         RefPtr<Range> backwardsScanRange(boundaryDocument.createRange());
 581         backwardsScanRange->setEnd(start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
 582         SimplifiedBackwardsTextIterator backwardsIterator(backwardsScanRange.get());
 583         while (!backwardsIterator.atEnd()) {
 584             StringView text = backwardsIterator.text();
 585             int i = startOfLastWordBoundaryContext(text);
 586             prepend(string, text.substring(i));
 587             prefixLength += text.length() - i;
 588             if (i > 0)
 589                 break;
 590             backwardsIterator.advance();
 591         }
 592     }
 593
 594     searchRange->selectNodeContents(boundary, IGNORE_EXCEPTION);
 595     searchRange->setStart(start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
 596     TextIterator it(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
 597     unsigned next = 0;
 598     bool needMoreContext = false;
 599     while (!it.atEnd()) {
 600         bool inTextSecurityMode = it.node() && it.node()->renderer() && it.node()->renderer()->style().textSecurity() != TSNONE;
 601         // Keep asking the iterator for chunks until the search function
 602         // returns an end value not equal to the length of the string passed to it.
 603         if (!inTextSecurityMode)
 604             append(string, it.text());
 605         else {
 606             // Treat bullets used in the text security mode as regular characters when looking for boundaries
 607             appendRepeatedCharacter(string, 'x', it.text().length());
 608         }
 609         if (string.size() > prefixLength) {
 610             next = searchFunction(StringView(string.data(), string.size()), prefixLength, MayHaveMoreContext, needMoreContext);
 611             if (next != string.size())
 612                 break;
 613         }
 614         it.advance();
 615     }
 616     if (needMoreContext && string.size() > prefixLength) {
 617         // The last search returned the end of the buffer and asked for more context,
 618         // but there is no further text. Force a search with what's available.
 619         next = searchFunction(StringView(string.data(), string.size()), prefixLength, DontHaveMoreContext, needMoreContext);
 620         ASSERT(!needMoreContext);
 621     }
 622
 623     if (it.atEnd() && next == string.size())
 624         pos = it.range()->startPosition();
 625     else if (next > prefixLength) {
 626         // Use the character iterator to translate the next value into a DOM position.
 627         CharacterIterator charIt(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
 628         charIt.advance(next - prefixLength - 1);
 629         RefPtr<Range> characterRange = charIt.range();
 630         pos = characterRange->endPosition();
 631
 632         if (charIt.text()[0] == '\n') {
 633             // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)
 634             VisiblePosition visPos = VisiblePosition(pos);
 635             if (visPos == VisiblePosition(characterRange->startPosition())) {
 636                 charIt.advance(1);
 637                 pos = charIt.range()->startPosition();
 638             }
 639         }
 640     }
 641
 642     // generate VisiblePosition, use UPSTREAM affinity if possible
 643     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
 644 }
 645
 646 // ---------
 647
 648 static unsigned startWordBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 649 {
 650     ASSERT(offset);
 651     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(text.substring(0, offset))) {
 652         needMoreContext = true;
 653         return 0;
 654     }
 655     needMoreContext = false;
 656     int start, end;
 657     U16_BACK_1(text, 0, offset);
 658     findWordBoundary(text, offset, &start, &end);
 659     return start;
 660 }
 661
 662 VisiblePosition startOfWord(const VisiblePosition& c, EWordSide side)
 663 {
 664     // FIXME: This returns a null VP for c at the start of the document
 665     // and side == LeftWordIfOnBoundary
 666     VisiblePosition p = c;
 667     if (side == RightWordIfOnBoundary) {
 668         // at paragraph end, the startofWord is the current position
 669         if (isEndOfParagraph(c))
 670             return c;
 671
 672         p = c.next();
 673         if (p.isNull())
 674             return c;
 675     }
 676     return previousBoundary(p, startWordBoundary);
 677 }
 678
 679 static unsigned endWordBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 680 {
 681     ASSERT(offset <= text.length());
 682     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(text.substring(offset)) == text.length() - offset) {
 683         needMoreContext = true;
 684         return text.length();
 685     }
 686     needMoreContext = false;
 687     int end;
 688     findEndWordBoundary(text, offset, &end);
 689     return end;
 690 }
 691
 692 VisiblePosition endOfWord(const VisiblePosition& c, EWordSide side)
 693 {
 694     VisiblePosition p = c;
 695     if (side == LeftWordIfOnBoundary) {
 696         if (isStartOfParagraph(c))
 697             return c;
 698
 699         p = c.previous();
 700         if (p.isNull())
 701             return c;
 702     } else if (isEndOfParagraph(c))
 703         return c;
 704
 705     return nextBoundary(p, endWordBoundary);
 706 }
 707
 708 static unsigned previousWordPositionBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 709 {
 710     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(text.substring(0, offset))) {
 711         needMoreContext = true;
 712         return 0;
 713     }
 714     needMoreContext = false;
 715     return findNextWordFromIndex(text, offset, false);
 716 }
 717
 718 VisiblePosition previousWordPosition(const VisiblePosition& position)
 719 {
 720     return position.honorEditingBoundaryAtOrBefore(previousBoundary(position, previousWordPositionBoundary));
 721 }
 722
 723 static unsigned nextWordPositionBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 724 {
 725     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(text.substring(offset)) == text.length() - offset) {
 726         needMoreContext = true;
 727         return text.length();
 728     }
 729     needMoreContext = false;
 730     return findNextWordFromIndex(text, offset, true);
 731 }
 732
 733 VisiblePosition nextWordPosition(const VisiblePosition& position)
 734 {
 735     return position.honorEditingBoundaryAtOrAfter(nextBoundary(position, nextWordPositionBoundary));
 736 }
 737
 738 bool isStartOfWord(const VisiblePosition& p)
 739 {
 740     return p.isNotNull() && p == startOfWord(p, RightWordIfOnBoundary);
 741 }
 742
 743 // ---------
 744
 745 enum LineEndpointComputationMode { UseLogicalOrdering, UseInlineBoxOrdering };
 746 static VisiblePosition startPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
 747 {
 748     if (c.isNull())
 749         return VisiblePosition();
 750
 751     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
 752     if (!rootBox) {
 753         // There are VisiblePositions at offset 0 in blocks without
 754         // RootInlineBoxes, like empty editable blocks and bordered blocks.
 755         Position p = c.deepEquivalent();
 756         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
 757             return c;
 758
 759         return VisiblePosition();
 760     }
 761
 762     Node* startNode;
 763     InlineBox* startBox;
 764     if (mode == UseLogicalOrdering) {
 765         startNode = rootBox->getLogicalStartBoxWithNode(startBox);
 766         if (!startNode)
 767             return VisiblePosition();
 768     } else {
 769         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
 770         // and so cannot be represented by a VisiblePosition. Use whatever follows instead.
 771         startBox = rootBox->firstLeafChild();
 772         while (true) {
 773             if (!startBox)
 774                 return VisiblePosition();
 775
 776             startNode = startBox->renderer().nonPseudoNode();
 777             if (startNode)
 778                 break;
 779
 780             startBox = startBox->nextLeafChild();
 781         }
 782     }
 783
 784     return startNode->isTextNode() ? Position(toText(startNode), toInlineTextBox(startBox)->start())
 785         : positionBeforeNode(startNode);
 786 }
 787
 788 static VisiblePosition startOfLine(const VisiblePosition& c, LineEndpointComputationMode mode)
 789 {
 790     // TODO: this is the current behavior that might need to be fixed.
 791     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
 792     VisiblePosition visPos = startPositionForLine(c, mode);
 793
 794     if (mode == UseLogicalOrdering) {
 795         if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
 796             if (!editableRoot->contains(visPos.deepEquivalent().containerNode()))
 797                 return firstPositionInNode(editableRoot);
 798         }
 799     }
 800
 801     return c.honorEditingBoundaryAtOrBefore(visPos);
 802 }
 803
 804 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
 805 VisiblePosition startOfLine(const VisiblePosition& currentPosition)
 806 {
 807     return startOfLine(currentPosition, UseInlineBoxOrdering);
 808 }
 809
 810 VisiblePosition logicalStartOfLine(const VisiblePosition& currentPosition)
 811 {
 812     return startOfLine(currentPosition, UseLogicalOrdering);
 813 }
 814
 815 static VisiblePosition endPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
 816 {
 817     if (c.isNull())
 818         return VisiblePosition();
 819
 820     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
 821     if (!rootBox) {
 822         // There are VisiblePositions at offset 0 in blocks without
 823         // RootInlineBoxes, like empty editable blocks and bordered blocks.
 824         Position p = c.deepEquivalent();
 825         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
 826             return c;
 827         return VisiblePosition();
 828     }
 829
 830     Node* endNode;
 831     InlineBox* endBox;
 832     if (mode == UseLogicalOrdering) {
 833         endNode = rootBox->getLogicalEndBoxWithNode(endBox);
 834         if (!endNode)
 835             return VisiblePosition();
 836     } else {
 837         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
 838         // and so cannot be represented by a VisiblePosition. Use whatever precedes instead.
 839         endBox = rootBox->lastLeafChild();
 840         while (true) {
 841             if (!endBox)
 842                 return VisiblePosition();
 843
 844             endNode = endBox->renderer().nonPseudoNode();
 845             if (endNode)
 846                 break;
 847
 848             endBox = endBox->prevLeafChild();
 849         }
 850     }
 851
 852     Position pos;
 853     if (endNode->hasTagName(brTag))
 854         pos = positionBeforeNode(endNode);
 855     else if (endBox->isInlineTextBox() && endNode->isTextNode()) {
 856         InlineTextBox* endTextBox = toInlineTextBox(endBox);
 857         int endOffset = endTextBox->start();
 858         if (!endTextBox->isLineBreak())
 859             endOffset += endTextBox->len();
 860         pos = Position(toText(endNode), endOffset);
 861     } else
 862         pos = positionAfterNode(endNode);
 863
 864     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
 865 }
 866
 867 static bool inSameLogicalLine(const VisiblePosition& a, const VisiblePosition& b)
 868 {
 869     return a.isNotNull() && logicalStartOfLine(a) == logicalStartOfLine(b);
 870 }
 871
 872 static VisiblePosition endOfLine(const VisiblePosition& c, LineEndpointComputationMode mode)
 873 {
 874     // TODO: this is the current behavior that might need to be fixed.
 875     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
 876     VisiblePosition visPos = endPositionForLine(c, mode);
 877
 878     if (mode == UseLogicalOrdering) {
 879         // Make sure the end of line is at the same line as the given input position. For a wrapping line, the logical end
 880         // position for the not-last-2-lines might incorrectly hand back the logical beginning of the next line.
 881         // For example, <div contenteditable dir="rtl" style="line-break:before-white-space">abcdefg abcdefg abcdefg
 882         // a abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg </div>
 883         // In this case, use the previous position of the computed logical end position.
 884         if (!inSameLogicalLine(c, visPos))
 885             visPos = visPos.previous();
 886
 887         if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
 888             if (!editableRoot->contains(visPos.deepEquivalent().containerNode()))
 889                 return lastPositionInNode(editableRoot);
 890         }
 891
 892         return c.honorEditingBoundaryAtOrAfter(visPos);
 893     }
 894
 895     // Make sure the end of line is at the same line as the given input position. Else use the previous position to
 896     // obtain end of line. This condition happens when the input position is before the space character at the end
 897     // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position
 898     // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style
 899     // versus lines without that style, which would break before a space by default.
 900     if (!inSameLine(c, visPos)) {
 901         visPos = c.previous();
 902         if (visPos.isNull())
 903             return VisiblePosition();
 904         visPos = endPositionForLine(visPos, UseInlineBoxOrdering);
 905     }
 906
 907     return c.honorEditingBoundaryAtOrAfter(visPos);
 908 }
 909
 910 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
 911 VisiblePosition endOfLine(const VisiblePosition& currentPosition)
 912 {
 913     return endOfLine(currentPosition, UseInlineBoxOrdering);
 914 }
 915
 916 VisiblePosition logicalEndOfLine(const VisiblePosition& currentPosition)
 917 {
 918     return endOfLine(currentPosition, UseLogicalOrdering);
 919 }
 920
 921 bool inSameLine(const VisiblePosition& a, const VisiblePosition& b)
 922 {
 923     return a.isNotNull() && startOfLine(a) == startOfLine(b);
 924 }
 925
 926 bool isStartOfLine(const VisiblePosition& p)
 927 {
 928     return p.isNotNull() && p == startOfLine(p);
 929 }
 930
 931 bool isEndOfLine(const VisiblePosition& p)
 932 {
 933     return p.isNotNull() && p == endOfLine(p);
 934 }
 935
 936 static inline IntPoint absoluteLineDirectionPointToLocalPointInBlock(RootInlineBox& root, int lineDirectionPoint)
 937 {
 938     RenderBlockFlow& containingBlock = root.blockFlow();
 939     FloatPoint absoluteBlockPoint = containingBlock.localToAbsolute(FloatPoint());
 940     if (containingBlock.hasOverflowClip())
 941         absoluteBlockPoint -= containingBlock.scrolledContentOffset();
 942
 943     if (containingBlock.isHorizontalWritingMode())
 944         return IntPoint(lineDirectionPoint - absoluteBlockPoint.x(), root.blockDirectionPointInLine());
 945
 946     return IntPoint(root.blockDirectionPointInLine(), lineDirectionPoint - absoluteBlockPoint.y());
 947 }
 948
 949 VisiblePosition previousLinePosition(const VisiblePosition& visiblePosition, int lineDirectionPoint, EditableType editableType)
 950 {
 951     Position p = visiblePosition.deepEquivalent();
 952     Node* node = p.deprecatedNode();
 953
 954     if (!node)
 955         return VisiblePosition();
 956
 957     node->document().updateLayoutIgnorePendingStylesheets();
 958
 959     RenderObject* renderer = node->renderer();
 960     if (!renderer)
 961         return VisiblePosition();
 962
 963     RootInlineBox* root = 0;
 964     InlineBox* box;
 965     int ignoredCaretOffset;
 966     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
 967     if (box) {
 968         root = box->root().prevRootBox();
 969         // We want to skip zero height boxes.
 970         // This could happen in case it is a TrailingFloatsRootInlineBox.
 971         if (!root || !root->logicalHeight() || !root->firstLeafChild())
 972             root = 0;
 973     }
 974
 975     if (!root) {
 976         Position position = previousRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
 977         if (position.isNotNull()) {
 978             RenderedPosition renderedPosition(position);
 979             root = renderedPosition.rootBox();
 980             if (!root)
 981                 return position;
 982         }
 983     }
 984
 985     if (root) {
 986         // FIXME: Can be wrong for multi-column layout and with transforms.
 987         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(*root, lineDirectionPoint);
 988         RenderObject& renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
 989         Node* node = renderer.node();
 990         if (node && editingIgnoresContent(node))
 991             return positionInParentBeforeNode(node);
 992         return renderer.positionForPoint(pointInLine);
 993     }
 994
 995     // Could not find a previous line. This means we must already be on the first line.
 996     // Move to the start of the content in this block, which effectively moves us
 997     // to the start of the line we're on.
 998     Element* rootElement = node->hasEditableStyle(editableType) ? node->rootEditableElement(editableType) : node->document().documentElement();
 999     if (!rootElement)
1000         return VisiblePosition();
1001     return VisiblePosition(firstPositionInNode(rootElement), DOWNSTREAM);
1002 }
1003
1004 VisiblePosition nextLinePosition(const VisiblePosition& visiblePosition, int lineDirectionPoint, EditableType editableType)
1005 {
1006     Position p = visiblePosition.deepEquivalent();
1007     Node* node = p.deprecatedNode();
1008
1009     if (!node)
1010         return VisiblePosition();
1011
1012     node->document().updateLayoutIgnorePendingStylesheets();
1013
1014     RenderObject* renderer = node->renderer();
1015     if (!renderer)
1016         return VisiblePosition();
1017
1018     RootInlineBox* root = 0;
1019     InlineBox* box;
1020     int ignoredCaretOffset;
1021     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
1022     if (box) {
1023         root = box->root().nextRootBox();
1024         // We want to skip zero height boxes.
1025         // This could happen in case it is a TrailingFloatsRootInlineBox.
1026         if (!root || !root->logicalHeight() || !root->firstLeafChild())
1027             root = 0;
1028     }
1029
1030     if (!root) {
1031         // FIXME: We need do the same in previousLinePosition.
1032         Node* child = node->childNode(p.deprecatedEditingOffset());
1033         node = child ? child : node->lastDescendant();
1034         Position position = nextRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
1035         if (position.isNotNull()) {
1036             RenderedPosition renderedPosition(position);
1037             root = renderedPosition.rootBox();
1038             if (!root)
1039                 return position;
1040         }
1041     }
1042
1043     if (root) {
1044         // FIXME: Can be wrong for multi-column layout and with transforms.
1045         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(*root, lineDirectionPoint);
1046         RenderObject& renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
1047         Node* node = renderer.node();
1048         if (node && editingIgnoresContent(node))
1049             return positionInParentBeforeNode(node);
1050         return renderer.positionForPoint(pointInLine);
1051     }
1052
1053     // Could not find a next line. This means we must already be on the last line.
1054     // Move to the end of the content in this block, which effectively moves us
1055     // to the end of the line we're on.
1056     Element* rootElement = node->hasEditableStyle(editableType) ? node->rootEditableElement(editableType) : node->document().documentElement();
1057     if (!rootElement)
1058         return VisiblePosition();
1059     return VisiblePosition(lastPositionInNode(rootElement), DOWNSTREAM);
1060 }
1061
1062 // ---------
1063
1064 static unsigned startSentenceBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1065 {
1066     // FIXME: The following function can return -1; we don't handle that.
1067     return textBreakPreceding(sentenceBreakIterator(text), text.length());
1068 }
1069
1070 VisiblePosition startOfSentence(const VisiblePosition& position)
1071 {
1072     return previousBoundary(position, startSentenceBoundary);
1073 }
1074
1075 static unsigned endSentenceBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1076 {
1077     return textBreakNext(sentenceBreakIterator(text));
1078 }
1079
1080 VisiblePosition endOfSentence(const VisiblePosition& position)
1081 {
1082     // FIXME: This includes the space after the punctuation that marks the end of the sentence.
1083     return nextBoundary(position, endSentenceBoundary);
1084 }
1085
1086 static unsigned previousSentencePositionBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1087 {
1088     // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
1089     // FIXME: The following function can return -1; we don't handle that.
1090     return textBreakPreceding(sentenceBreakIterator(text), text.length());
1091 }
1092
1093 VisiblePosition previousSentencePosition(const VisiblePosition& position)
1094 {
1095     return position.honorEditingBoundaryAtOrBefore(previousBoundary(position, previousSentencePositionBoundary));
1096 }
1097
1098 static unsigned nextSentencePositionBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1099 {
1100     // FIXME: This is identical to endSentenceBoundary.
1101     // That isn't right. This function needs to move to the equivalent position in the following sentence.
1102     return textBreakFollowing(sentenceBreakIterator(text), 0);
1103 }
1104
1105 VisiblePosition nextSentencePosition(const VisiblePosition& position)
1106 {
1107     return position.honorEditingBoundaryAtOrAfter(nextBoundary(position, nextSentencePositionBoundary));
1108 }
1109
1110 VisiblePosition startOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1111 {
1112     Position p = c.deepEquivalent();
1113     Node* startNode = p.deprecatedNode();
1114
1115     if (!startNode)
1116         return VisiblePosition();
1117
1118     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1119         return positionBeforeNode(startNode);
1120
1121     Node* startBlock = enclosingBlock(startNode);
1122
1123     Node* node = startNode;
1124     Node* highestRoot = highestEditableRoot(p);
1125     int offset = p.deprecatedEditingOffset();
1126     Position::AnchorType type = p.anchorType();
1127
1128     Node* n = startNode;
1129     while (n) {
1130 #if ENABLE(USERSELECT_ALL)
1131         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNode->hasEditableStyle())
1132 #else
1133         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->hasEditableStyle() != startNode->hasEditableStyle())
1134 #endif
1135             break;
1136         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1137             while (n && n->hasEditableStyle() != startNode->hasEditableStyle())
1138                 n = NodeTraversal::previousPostOrder(n, startBlock);
1139             if (!n || !n->isDescendantOf(highestRoot))
1140                 break;
1141         }
1142         RenderObject* r = n->renderer();
1143         if (!r) {
1144             n = NodeTraversal::previousPostOrder(n, startBlock);
1145             continue;
1146         }
1147         const RenderStyle& style = r->style();
1148         if (style.visibility() != VISIBLE) {
1149             n = NodeTraversal::previousPostOrder(n, startBlock);
1150             continue;
1151         }
1152
1153         if (r->isBR() || isBlock(n))
1154             break;
1155
1156         if (r->isText() && toRenderText(r)->hasRenderedText()) {
1157             ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1158             type = Position::PositionIsOffsetInAnchor;
1159             if (style.preserveNewline()) {
1160                 const UChar* chars = toRenderText(r)->deprecatedCharacters();
1161                 int i = toRenderText(r)->textLength();
1162                 int o = offset;
1163                 if (n == startNode && o < i)
1164                     i = std::max(0, o);
1165                 while (--i >= 0) {
1166                     if (chars[i] == '\n')
1167                         return VisiblePosition(Position(toText(n), i + 1), DOWNSTREAM);
1168                 }
1169             }
1170             node = n;
1171             offset = 0;
1172             n = NodeTraversal::previousPostOrder(n, startBlock);
1173         } else if (editingIgnoresContent(n) || isRenderedTable(n)) {
1174             node = n;
1175             type = Position::PositionIsBeforeAnchor;
1176             n = n->previousSibling() ? n->previousSibling() : NodeTraversal::previousPostOrder(n, startBlock);
1177         } else
1178             n = NodeTraversal::previousPostOrder(n, startBlock);
1179     }
1180
1181     if (type == Position::PositionIsOffsetInAnchor) {
1182         ASSERT(type == Position::PositionIsOffsetInAnchor || !offset);
1183         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1184     }
1185
1186     return VisiblePosition(Position(node, type), DOWNSTREAM);
1187 }
1188
1189 VisiblePosition endOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1190 {
1191     if (c.isNull())
1192         return VisiblePosition();
1193
1194     Position p = c.deepEquivalent();
1195     Node* startNode = p.deprecatedNode();
1196
1197     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1198         return positionAfterNode(startNode);
1199
1200     Node* startBlock = enclosingBlock(startNode);
1201     Node* stayInsideBlock = startBlock;
1202
1203     Node* node = startNode;
1204     Node* highestRoot = highestEditableRoot(p);
1205     int offset = p.deprecatedEditingOffset();
1206     Position::AnchorType type = p.anchorType();
1207
1208     Node* n = startNode;
1209     while (n) {
1210 #if ENABLE(USERSELECT_ALL)
1211         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNode->hasEditableStyle())
1212 #else
1213         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->hasEditableStyle() != startNode->hasEditableStyle())
1214 #endif
1215             break;
1216         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1217             while (n && n->hasEditableStyle() != startNode->hasEditableStyle())
1218                 n = NodeTraversal::next(n, stayInsideBlock);
1219             if (!n || !n->isDescendantOf(highestRoot))
1220                 break;
1221         }
1222
1223         RenderObject* r = n->renderer();
1224         if (!r) {
1225             n = NodeTraversal::next(n, stayInsideBlock);
1226             continue;
1227         }
1228         const RenderStyle& style = r->style();
1229         if (style.visibility() != VISIBLE) {
1230             n = NodeTraversal::next(n, stayInsideBlock);
1231             continue;
1232         }
1233
1234         // FIXME: This is wrong when startNode is a block. We should return a position after the block.
1235         if (r->isBR() || isBlock(n))
1236             break;
1237
1238         // FIXME: We avoid returning a position where the renderer can't accept the caret.
1239         if (r->isText() && toRenderText(r)->hasRenderedText()) {
1240             ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1241             int length = toRenderText(r)->textLength();
1242             type = Position::PositionIsOffsetInAnchor;
1243             if (style.preserveNewline()) {
1244                 const UChar* chars = toRenderText(r)->deprecatedCharacters();
1245                 int o = n == startNode ? offset : 0;
1246                 for (int i = o; i < length; ++i) {
1247                     if (chars[i] == '\n')
1248                         return VisiblePosition(Position(toText(n), i), DOWNSTREAM);
1249                 }
1250             }
1251             node = n;
1252             offset = r->caretMaxOffset();
1253             n = NodeTraversal::next(n, stayInsideBlock);
1254         } else if (editingIgnoresContent(n) || isRenderedTable(n)) {
1255             node = n;
1256             type = Position::PositionIsAfterAnchor;
1257             n = NodeTraversal::nextSkippingChildren(n, stayInsideBlock);
1258         } else
1259             n = NodeTraversal::next(n, stayInsideBlock);
1260     }
1261
1262     if (type == Position::PositionIsOffsetInAnchor)
1263         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1264
1265     return VisiblePosition(Position(node, type), DOWNSTREAM);
1266 }
1267
1268 // FIXME: isStartOfParagraph(startOfNextParagraph(pos)) is not always true
1269 VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
1270 {
1271     VisiblePosition paragraphEnd(endOfParagraph(visiblePosition, CanSkipOverEditingBoundary));
1272     VisiblePosition afterParagraphEnd(paragraphEnd.next(CannotCrossEditingBoundary));
1273     // The position after the last position in the last cell of a table
1274     // is not the start of the next paragraph.
1275     if (isFirstPositionAfterTable(afterParagraphEnd))
1276         return afterParagraphEnd.next(CannotCrossEditingBoundary);
1277     return afterParagraphEnd;
1278 }
1279
1280 bool inSameParagraph(const VisiblePosition& a, const VisiblePosition& b, EditingBoundaryCrossingRule boundaryCrossingRule)
1281 {
1282     return a.isNotNull() && startOfParagraph(a, boundaryCrossingRule) == startOfParagraph(b, boundaryCrossingRule);
1283 }
1284
1285 bool isStartOfParagraph(const VisiblePosition& pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1286 {
1287     return pos.isNotNull() && pos == startOfParagraph(pos, boundaryCrossingRule);
1288 }
1289
1290 bool isEndOfParagraph(const VisiblePosition& pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1291 {
1292     return pos.isNotNull() && pos == endOfParagraph(pos, boundaryCrossingRule);
1293 }
1294
1295 VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
1296 {
1297     VisiblePosition pos = p;
1298     do {
1299         VisiblePosition n = previousLinePosition(pos, x);
1300         if (n.isNull() || n == pos)
1301             break;
1302         pos = n;
1303     } while (inSameParagraph(p, pos));
1304     return pos;
1305 }
1306
1307 VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
1308 {
1309     VisiblePosition pos = p;
1310     do {
1311         VisiblePosition n = nextLinePosition(pos, x);
1312         if (n.isNull() || n == pos)
1313             break;
1314         pos = n;
1315     } while (inSameParagraph(p, pos));
1316     return pos;
1317 }
1318
1319 // ---------
1320
1321 VisiblePosition startOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1322 {
1323     Position position = visiblePosition.deepEquivalent();
1324     Node* startBlock;
1325     if (!position.containerNode() || !(startBlock = enclosingBlock(position.containerNode(), rule)))
1326         return VisiblePosition();
1327     return firstPositionInNode(startBlock);
1328 }
1329
1330 VisiblePosition endOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1331 {
1332     Position position = visiblePosition.deepEquivalent();
1333     Node* endBlock;
1334     if (!position.containerNode() || !(endBlock = enclosingBlock(position.containerNode(), rule)))
1335         return VisiblePosition();
1336     return lastPositionInNode(endBlock);
1337 }
1338
1339 bool inSameBlock(const VisiblePosition& a, const VisiblePosition& b)
1340 {
1341     return !a.isNull() && enclosingBlock(a.deepEquivalent().containerNode()) == enclosingBlock(b.deepEquivalent().containerNode());
1342 }
1343
1344 bool isStartOfBlock(const VisiblePosition& pos)
1345 {
1346     return pos.isNotNull() && pos == startOfBlock(pos, CanCrossEditingBoundary);
1347 }
1348
1349 bool isEndOfBlock(const VisiblePosition& pos)
1350 {
1351     return pos.isNotNull() && pos == endOfBlock(pos, CanCrossEditingBoundary);
1352 }
1353
1354 // ---------
1355
1356 VisiblePosition startOfDocument(const Node* node)
1357 {
1358     if (!node || !node->document().documentElement())
1359         return VisiblePosition();
1360
1361 #if PLATFORM(IOS)
1362     // The canonicalization of the position at (documentElement, 0) can turn the visible
1363     // position to null, even when there's a valid candidate to be had, because the root HTML element
1364     // is not content editable.  So we construct directly from the valid candidate.
1365     // FIXME: Do this for non-iOS platforms too. https://bugs.webkit.org/show_bug.cgi?id=56437
1366     Position firstCandidate = nextCandidate(createLegacyEditingPosition(node->document().documentElement(), 0));
1367     if (firstCandidate.isNull())
1368         return VisiblePosition();
1369     return VisiblePosition(firstCandidate);
1370 #else
1371     return VisiblePosition(firstPositionInNode(node->document().documentElement()), DOWNSTREAM);
1372 #endif
1373 }
1374
1375 VisiblePosition startOfDocument(const VisiblePosition& c)
1376 {
1377     return startOfDocument(c.deepEquivalent().deprecatedNode());
1378 }
1379
1380 VisiblePosition endOfDocument(const Node* node)
1381 {
1382     if (!node || !node->document().documentElement())
1383         return VisiblePosition();
1384
1385 #if PLATFORM(IOS)
1386     // (As above, in startOfDocument.)  The canonicalization can reject valid visible positions
1387     // when descending from the root element, so we construct the visible position directly from a
1388     // valid candidate.
1389     // FIXME: Do this for non-iOS platforms too. https://bugs.webkit.org/show_bug.cgi?id=56437
1390     Position lastPosition = createLegacyEditingPosition(node->document().documentElement(), node->document().documentElement()->childNodeCount());
1391     Position lastCandidate = previousCandidate(lastPosition);
1392     if (lastCandidate.isNull())
1393         return VisiblePosition();
1394     return VisiblePosition(lastCandidate);
1395 #else
1396     return VisiblePosition(lastPositionInNode(node->document().documentElement()), DOWNSTREAM);
1397 #endif
1398 }
1399
1400 VisiblePosition endOfDocument(const VisiblePosition& c)
1401 {
1402     return endOfDocument(c.deepEquivalent().deprecatedNode());
1403 }
1404
1405 bool inSameDocument(const VisiblePosition& a, const VisiblePosition& b)
1406 {
1407     Position ap = a.deepEquivalent();
1408     Node* an = ap.deprecatedNode();
1409     if (!an)
1410         return false;
1411     Position bp = b.deepEquivalent();
1412     Node* bn = bp.deprecatedNode();
1413     if (an == bn)
1414         return true;
1415
1416     return &an->document() == &bn->document();
1417 }
1418
1419 bool isStartOfDocument(const VisiblePosition& p)
1420 {
1421     return p.isNotNull() && p.previous(CanCrossEditingBoundary).isNull();
1422 }
1423
1424 bool isEndOfDocument(const VisiblePosition& p)
1425 {
1426     return p.isNotNull() && p.next(CanCrossEditingBoundary).isNull();
1427 }
1428
1429 // ---------
1430
1431 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1432 {
1433     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1434     if (!highestRoot)
1435         return VisiblePosition();
1436
1437     return firstPositionInNode(highestRoot);
1438 }
1439
1440 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1441 {
1442     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1443     if (!highestRoot)
1444         return VisiblePosition();
1445
1446     return lastPositionInNode(highestRoot);
1447 }
1448
1449 bool isEndOfEditableOrNonEditableContent(const VisiblePosition& p)
1450 {
1451     return p.isNotNull() && p.next().isNull();
1452 }
1453
1454 VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1455 {
1456     return direction == LTR ? logicalStartOfLine(c) : logicalEndOfLine(c);
1457 }
1458
1459 VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1460 {
1461     return direction == LTR ? logicalEndOfLine(c) : logicalStartOfLine(c);
1462 }
1463
1464 #if PLATFORM(IOS)
1465
1466 static bool directionIsDownstream(SelectionDirection direction)
1467 {
1468     if (direction == DirectionBackward)
1469         return false;
1470     else if (direction == DirectionForward)
1471         return true;
1472
1473     // FIXME: this code doesn't take into account the original direction of the element.
1474     // I'm not fixing this now because I'm afraid there is some code in UIKit relying on
1475     // this wrong behavior.
1476     return direction == DirectionRight;
1477 }
1478
1479 bool atBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1480 {
1481     if (granularity == CharacterGranularity)
1482         return true;
1483
1484     VisiblePosition boundary;
1485
1486     bool useDownstream = directionIsDownstream(direction);
1487
1488     switch (granularity) {
1489     case WordGranularity:
1490         // visible_units claims erroneously that the start and the end
1491         // of a paragraph are the end and start of a word, respectively.
1492         if ((useDownstream && isStartOfParagraph(vp)) || (!useDownstream && isEndOfParagraph(vp)))
1493             return false;
1494
1495         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1496         boundary = useDownstream ? endOfWord(vp, LeftWordIfOnBoundary) : startOfWord(vp, RightWordIfOnBoundary);
1497         break;
1498
1499     case SentenceGranularity:
1500         boundary = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1501         break;
1502
1503     case LineGranularity:
1504         // Affinity has to be set to get right boundary of the line.
1505         boundary = vp;
1506         boundary.setAffinity(useDownstream ? VP_UPSTREAM_IF_POSSIBLE : DOWNSTREAM);
1507         boundary = useDownstream ? endOfLine(boundary) : startOfLine(boundary);
1508         break;
1509
1510     case ParagraphGranularity:
1511         boundary = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1512         break;
1513
1514     case DocumentGranularity:
1515         boundary = useDownstream ? endOfDocument(vp) : startOfDocument(vp);
1516         break;
1517
1518     default:
1519         ASSERT_NOT_REACHED();
1520         break;
1521     }
1522
1523     return vp == boundary;
1524 }
1525
1526 bool withinTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1527 {
1528     if (granularity == CharacterGranularity || granularity == DocumentGranularity)
1529         return true;
1530
1531     bool useDownstream = directionIsDownstream(direction);
1532
1533     VisiblePosition prevBoundary;
1534     VisiblePosition nextBoundary;
1535
1536     switch (granularity) {
1537     case WordGranularity:
1538         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1539         prevBoundary = startOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1540         nextBoundary = endOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1541
1542         // Workaround for <rdar://problem/7259611> Word boundary code on iPhone gives different results than desktop
1543         if (endOfWord(prevBoundary, RightWordIfOnBoundary) != nextBoundary)
1544             return false;
1545
1546         break;
1547
1548     case SentenceGranularity:
1549         prevBoundary = startOfSentence(vp);
1550         nextBoundary = endOfSentence(vp);
1551         break;
1552
1553     case LineGranularity:
1554         prevBoundary = startOfLine(vp);
1555         nextBoundary = endOfLine(vp);
1556
1557         if (prevBoundary == nextBoundary) {
1558             nextBoundary = nextLinePosition(nextBoundary, 0);
1559             nextBoundary.setAffinity(UPSTREAM);
1560             if (!inSameLine(prevBoundary, nextBoundary))
1561                 nextBoundary = vp.next();
1562         }
1563         break;
1564
1565     case ParagraphGranularity:
1566         prevBoundary = startOfParagraph(vp);
1567         nextBoundary = endOfParagraph(vp);
1568         break;
1569
1570     default:
1571         ASSERT_NOT_REACHED();
1572         break;
1573     }
1574
1575     if (prevBoundary == nextBoundary)
1576         return false;
1577
1578     if (vp == prevBoundary)
1579         return useDownstream;
1580
1581     if (vp == nextBoundary)
1582         return !useDownstream;
1583
1584     return (prevBoundary < vp && vp < nextBoundary);
1585 }
1586
1587 static VisiblePosition nextCharacterBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1588 {
1589     return directionIsDownstream(direction) ? vp.next() : vp.previous();
1590 }
1591
1592 static VisiblePosition nextWordBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1593 {
1594     bool useDownstream = directionIsDownstream(direction);
1595     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, WordGranularity, direction);
1596     VisiblePosition result;
1597
1598     if (useDownstream) {
1599         if (withinUnitOfGranularity)
1600             result = endOfWord(vp, RightWordIfOnBoundary);
1601         else {
1602             VisiblePosition start = startOfWord(vp, RightWordIfOnBoundary);
1603             if (start > vp && start != endOfWord(start))
1604                 result = start;
1605             else {
1606                 // Do same thing as backwards traveling below.
1607                 start = vp;
1608                 while (true) {
1609                     result = startOfWord(nextWordPosition(start), RightWordIfOnBoundary);
1610
1611                     if (result == start)
1612                         break;
1613
1614                     // We failed to find a word boundary.
1615                     if (result.isNull() || result < start)
1616                         return VisiblePosition();
1617
1618                     // We consider successs also the case where start is before element and result is after.
1619                     // This covers moving past images like words.
1620                     if (result != endOfWord(result)
1621                         || (result.deepEquivalent().anchorNode() == start.deepEquivalent().anchorNode()
1622                             && result.deepEquivalent().anchorType() == Position::PositionIsAfterAnchor
1623                             && start.deepEquivalent().anchorType() == Position::PositionIsBeforeAnchor))
1624                         break;
1625
1626                     start = result;
1627                 }
1628             }
1629         }
1630     } else {
1631         if (withinUnitOfGranularity)
1632             result = startOfWord(vp, LeftWordIfOnBoundary);
1633         else {
1634             // This is complicated because:
1635             //   When given "Blah blah.|", endOfWord is "Blah blah|.", and previousWordPosition is "Blah| blah."
1636             //   When given "Blah blah. |", endOfWord is "Blah blah.| ", and previousWordPosition is "Blah |blah. ".
1637             VisiblePosition end = endOfWord(vp, LeftWordIfOnBoundary);
1638             if (end < vp && end != startOfWord(end))
1639                 result = end;
1640             else {
1641                 end = vp;
1642                 while (true) {
1643                     result = endOfWord(previousWordPosition(end), RightWordIfOnBoundary);
1644
1645                     if (result == end)
1646                         break;
1647
1648                     if (result.isNull() || result > end)
1649                         return VisiblePosition();
1650
1651                     if (result != startOfWord(result))
1652                         break;
1653
1654                     end = result;
1655                 }
1656             }
1657         }
1658     }
1659
1660     if (result == vp)
1661         return VisiblePosition();
1662
1663     return result;
1664 }
1665
1666 static VisiblePosition nextSentenceBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1667 {
1668     bool useDownstream = directionIsDownstream(direction);
1669     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, SentenceGranularity, direction);
1670     VisiblePosition result;
1671
1672     if (withinUnitOfGranularity)
1673         result = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1674     else {
1675         result = useDownstream ? nextSentencePosition(vp) : previousSentencePosition(vp);
1676         if (result.isNull() || result == vp)
1677             return VisiblePosition();
1678
1679         result = useDownstream ? startOfSentence(vp) : endOfSentence(vp);
1680     }
1681
1682     if (result == vp)
1683         return VisiblePosition();
1684
1685     ASSERT(useDownstream ? (result > vp) : (result < vp));
1686
1687     return result;
1688 }
1689
1690 static VisiblePosition nextLineBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1691 {
1692     bool useDownstream = directionIsDownstream(direction);
1693     VisiblePosition result = vp;
1694
1695     if (useDownstream) {
1696         result.setAffinity(DOWNSTREAM);
1697         result = isEndOfLine(result) ? startOfLine(nextLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : endOfLine(result);
1698     } else {
1699         result.setAffinity(VP_UPSTREAM_IF_POSSIBLE);
1700         result = isStartOfLine(result) ? endOfLine(previousLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : startOfLine(result);
1701     }
1702
1703     return result;
1704 }
1705
1706 static VisiblePosition nextParagraphBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1707 {
1708     bool useDownstream = directionIsDownstream(direction);
1709     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, ParagraphGranularity, direction);
1710     VisiblePosition result;
1711
1712     if (!withinUnitOfGranularity)
1713         result =  useDownstream ? startOfParagraph(nextParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation())) : endOfParagraph(previousParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation()));
1714     else
1715         result = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1716
1717     return result;
1718 }
1719
1720 static VisiblePosition nextDocumentBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1721 {
1722     return directionIsDownstream(direction) ? endOfDocument(vp) : startOfDocument(vp);
1723 }
1724
1725 VisiblePosition positionOfNextBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1726 {
1727     switch (granularity) {
1728     case CharacterGranularity:
1729         return nextCharacterBoundaryInDirection(vp, direction);
1730     case WordGranularity:
1731         return nextWordBoundaryInDirection(vp, direction);
1732     case SentenceGranularity:
1733         return nextSentenceBoundaryInDirection(vp, direction);
1734     case LineGranularity:
1735         return nextLineBoundaryInDirection(vp, direction);
1736     case ParagraphGranularity:
1737         return nextParagraphBoundaryInDirection(vp, direction);
1738     case DocumentGranularity:
1739         return nextDocumentBoundaryInDirection(vp, direction);
1740     default:
1741         ASSERT_NOT_REACHED();
1742         return VisiblePosition();
1743     }
1744 }
1745
1746 PassRefPtr<Range> enclosingTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1747 {
1748     // This is particularly inefficient.  We could easily obtain the answer with the boundaries computed below.
1749     if (!withinTextUnitOfGranularity(vp, granularity, direction))
1750         return 0;
1751
1752     VisiblePosition prevBoundary;
1753     VisiblePosition nextBoundary;
1754     bool useDownstream = directionIsDownstream(direction);
1755
1756     switch (granularity) {
1757         case CharacterGranularity:
1758             prevBoundary = vp;
1759             nextBoundary = prevBoundary.next();
1760             break;
1761
1762         case WordGranularity:
1763             // NB: "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1764             if (useDownstream) {
1765                 prevBoundary = startOfWord(vp, RightWordIfOnBoundary);
1766                 nextBoundary = endOfWord(vp, RightWordIfOnBoundary);
1767             } else {
1768                 prevBoundary = startOfWord(vp, LeftWordIfOnBoundary);
1769                 nextBoundary = endOfWord(vp, LeftWordIfOnBoundary);
1770             }
1771             break;
1772
1773         case SentenceGranularity:
1774             prevBoundary = startOfSentence(vp);
1775             nextBoundary = endOfSentence(vp);
1776             break;
1777
1778         case LineGranularity:
1779             prevBoundary = startOfLine(vp);
1780             nextBoundary = endOfLine(vp);
1781
1782             if (prevBoundary == nextBoundary) {
1783                 nextBoundary = nextLinePosition(nextBoundary, 0);
1784                 nextBoundary.setAffinity(UPSTREAM);
1785                 if (!inSameLine(prevBoundary, nextBoundary))
1786                     nextBoundary = vp.next();
1787             }
1788             break;
1789
1790         case ParagraphGranularity:
1791             prevBoundary = startOfParagraph(vp);
1792             nextBoundary = endOfParagraph(vp);
1793             break;
1794
1795         case DocumentGranularity:
1796             prevBoundary = startOfDocument(vp);
1797             nextBoundary = endOfDocument(vp);
1798             break;
1799
1800         default:
1801             ASSERT_NOT_REACHED();
1802             return 0;
1803     }
1804
1805     if (prevBoundary.isNull() || nextBoundary.isNull())
1806         return 0;
1807
1808     if (vp < prevBoundary || vp > nextBoundary)
1809         return 0;
1810
1811     RefPtr<Range> range = Range::create(prevBoundary.deepEquivalent().deprecatedNode()->document(), prevBoundary, nextBoundary);
1812
1813     return range;
1814 }
1815
1816 int distanceBetweenPositions(const VisiblePosition& vp, const VisiblePosition& other)
1817 {
1818     if (vp.isNull() || other.isNull())
1819         return 0;
1820
1821     bool thisIsStart = (vp < other);
1822
1823     // Start must come first in the Range constructor.
1824     RefPtr<Range> range = Range::create(vp.deepEquivalent().deprecatedNode()->document(),
1825                                         (thisIsStart ? vp : other),
1826                                         (thisIsStart ? other : vp));
1827     int distance = TextIterator::rangeLength(range.get());
1828
1829     return (thisIsStart ? -distance : distance);
1830 }
1831
1832 PassRefPtr<Range> wordRangeFromPosition(const VisiblePosition& position)
1833 {
1834     ASSERT(position.isNotNull());
1835
1836     RefPtr<Range> range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionBackward);
1837
1838     if (!range) {
1839         // We could be at the start of a word, try forward.
1840         range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
1841     }
1842     if (range)
1843         return range;
1844
1845     VisiblePosition currentPosition = position;
1846     do {
1847         currentPosition = positionOfNextBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward);
1848     } while (currentPosition.isNotNull() && !atBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward));
1849
1850     // If the position is an empty paragraph and at the end of the document
1851     // the word iterator could not pass the paragraph boundary, therefore iterating to
1852     // the previous line is required.
1853     if (currentPosition.isNull() && isEndOfDocument(position)) {
1854         VisiblePosition previousLinePosition = positionOfNextBoundaryOfGranularity(position, LineGranularity, DirectionBackward);
1855         if (previousLinePosition.isNotNull()) {
1856             currentPosition = positionOfNextBoundaryOfGranularity(previousLinePosition, WordGranularity, DirectionBackward);
1857             if (currentPosition.isNull())
1858                 currentPosition = previousLinePosition;
1859         }
1860     }
1861
1862     if (currentPosition.isNull())
1863         currentPosition = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
1864
1865     if (currentPosition.isNotNull()) {
1866         range = Range::create(position.deepEquivalent().deprecatedNode()->document(), currentPosition, position);
1867         ASSERT(range);
1868     }
1869     return range;
1870 }
1871
1872 VisiblePosition closestWordBoundaryForPosition(const VisiblePosition& position)
1873 {
1874     VisiblePosition result;
1875
1876     // move the the position at the end of the word
1877     if (atBoundaryOfGranularity(position, LineGranularity, DirectionForward)) {
1878         // Don't cross line boundaries.
1879         result = position;
1880     } else if (withinTextUnitOfGranularity(position, WordGranularity, DirectionForward)) {
1881         // The position lies within a word.
1882         RefPtr<Range> wordRange = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
1883
1884         result = wordRange->startPosition();
1885         if (distanceBetweenPositions(position, result) > 1)
1886             result = wordRange->endPosition();
1887     } else if (atBoundaryOfGranularity(position, WordGranularity, DirectionBackward)) {
1888         // The position is at the end of a word.
1889         result = position;
1890     } else {
1891         // The position is not within a word.
1892         // Go to the next boundary.
1893         result = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
1894
1895         // If there is no such boundary we go to the end of the element.
1896         if (result.isNull())
1897             result = endOfEditableContent(position);
1898     }
1899     return result;
1900 }
1901
1902 #endif
1903
1904 }