src/third_party/WebKit/Source/core/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 "core/editing/VisibleUnits.h"
  28
  29 #include "bindings/core/v8/ExceptionState.h"
  30 #include "bindings/core/v8/ExceptionStatePlaceholder.h"
  31 #include "core/HTMLNames.h"
  32 #include "core/dom/Document.h"
  33 #include "core/dom/Element.h"
  34 #include "core/dom/NodeTraversal.h"
  35 #include "core/dom/Position.h"
  36 #include "core/dom/Text.h"
  37 #include "core/editing/RenderedPosition.h"
  38 #include "core/editing/TextIterator.h"
  39 #include "core/editing/VisiblePosition.h"
  40 #include "core/editing/htmlediting.h"
  41 #include "core/html/HTMLBRElement.h"
  42 #include "core/rendering/InlineTextBox.h"
  43 #include "core/rendering/RenderBlockFlow.h"
  44 #include "core/rendering/RenderObject.h"
  45 #include "platform/RuntimeEnabledFeatures.h"
  46 #include "platform/heap/Handle.h"
  47 #include "platform/text/TextBoundaries.h"
  48
  49 namespace blink {
  50
  51 using namespace HTMLNames;
  52 using namespace WTF::Unicode;
  53
  54 static Node* previousLeafWithSameEditability(Node* node, EditableType editableType)
  55 {
  56     bool editable = node->hasEditableStyle(editableType);
  57     node = node->previousLeafNode();
  58     while (node) {
  59         if (editable == node->hasEditableStyle(editableType))
  60             return node;
  61         node = node->previousLeafNode();
  62     }
  63     return 0;
  64 }
  65
  66 static Node* nextLeafWithSameEditability(Node* node, EditableType editableType = ContentIsEditable)
  67 {
  68     if (!node)
  69         return 0;
  70
  71     bool editable = node->hasEditableStyle(editableType);
  72     node = node->nextLeafNode();
  73     while (node) {
  74         if (editable == node->hasEditableStyle(editableType))
  75             return node;
  76         node = node->nextLeafNode();
  77     }
  78     return 0;
  79 }
  80
  81 // FIXME: consolidate with code in previousLinePosition.
  82 static Position previousRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
  83 {
  84     ContainerNode* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
  85     Node* previousNode = previousLeafWithSameEditability(node, editableType);
  86
  87     while (previousNode && (!previousNode->renderer() || inSameLine(VisiblePosition(firstPositionInOrBeforeNode(previousNode)), visiblePosition)))
  88         previousNode = previousLeafWithSameEditability(previousNode, editableType);
  89
  90     while (previousNode && !previousNode->isShadowRoot()) {
  91         if (highestEditableRoot(firstPositionInOrBeforeNode(previousNode), editableType) != highestRoot)
  92             break;
  93
  94         Position pos = isHTMLBRElement(*previousNode) ? positionBeforeNode(previousNode) :
  95             createLegacyEditingPosition(previousNode, caretMaxOffset(previousNode));
  96
  97         if (pos.isCandidate())
  98             return pos;
  99
 100         previousNode = previousLeafWithSameEditability(previousNode, editableType);
 101     }
 102     return Position();
 103 }
 104
 105 static Position nextRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
 106 {
 107     ContainerNode* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
 108     Node* nextNode = nextLeafWithSameEditability(node, editableType);
 109     while (nextNode && (!nextNode->renderer() || inSameLine(VisiblePosition(firstPositionInOrBeforeNode(nextNode)), visiblePosition)))
 110         nextNode = nextLeafWithSameEditability(nextNode, ContentIsEditable);
 111
 112     while (nextNode && !nextNode->isShadowRoot()) {
 113         if (highestEditableRoot(firstPositionInOrBeforeNode(nextNode), editableType) != highestRoot)
 114             break;
 115
 116         Position pos;
 117         pos = createLegacyEditingPosition(nextNode, caretMinOffset(nextNode));
 118
 119         if (pos.isCandidate())
 120             return pos;
 121
 122         nextNode = nextLeafWithSameEditability(nextNode, editableType);
 123     }
 124     return Position();
 125 }
 126
 127 class CachedLogicallyOrderedLeafBoxes {
 128 public:
 129     CachedLogicallyOrderedLeafBoxes();
 130
 131     const InlineTextBox* previousTextBox(const RootInlineBox*, const InlineTextBox*);
 132     const InlineTextBox* nextTextBox(const RootInlineBox*, const InlineTextBox*);
 133
 134     size_t size() const { return m_leafBoxes.size(); }
 135     const InlineBox* firstBox() const { return m_leafBoxes[0]; }
 136
 137 private:
 138     const Vector<InlineBox*>& collectBoxes(const RootInlineBox*);
 139     int boxIndexInLeaves(const InlineTextBox*) const;
 140
 141     const RootInlineBox* m_rootInlineBox;
 142     Vector<InlineBox*> m_leafBoxes;
 143 };
 144
 145 CachedLogicallyOrderedLeafBoxes::CachedLogicallyOrderedLeafBoxes() : m_rootInlineBox(0) { };
 146
 147 const InlineTextBox* CachedLogicallyOrderedLeafBoxes::previousTextBox(const RootInlineBox* root, const InlineTextBox* box)
 148 {
 149     if (!root)
 150         return 0;
 151
 152     collectBoxes(root);
 153
 154     // If box is null, root is box's previous RootInlineBox, and previousBox is the last logical box in root.
 155     int boxIndex = m_leafBoxes.size() - 1;
 156     if (box)
 157         boxIndex = boxIndexInLeaves(box) - 1;
 158
 159     for (int i = boxIndex; i >= 0; --i) {
 160         if (m_leafBoxes[i]->isInlineTextBox())
 161             return toInlineTextBox(m_leafBoxes[i]);
 162     }
 163
 164     return 0;
 165 }
 166
 167 const InlineTextBox* CachedLogicallyOrderedLeafBoxes::nextTextBox(const RootInlineBox* root, const InlineTextBox* box)
 168 {
 169     if (!root)
 170         return 0;
 171
 172     collectBoxes(root);
 173
 174     // If box is null, root is box's next RootInlineBox, and nextBox is the first logical box in root.
 175     // Otherwise, root is box's RootInlineBox, and nextBox is the next logical box in the same line.
 176     size_t nextBoxIndex = 0;
 177     if (box)
 178         nextBoxIndex = boxIndexInLeaves(box) + 1;
 179
 180     for (size_t i = nextBoxIndex; i < m_leafBoxes.size(); ++i) {
 181         if (m_leafBoxes[i]->isInlineTextBox())
 182             return toInlineTextBox(m_leafBoxes[i]);
 183     }
 184
 185     return 0;
 186 }
 187
 188 const Vector<InlineBox*>& CachedLogicallyOrderedLeafBoxes::collectBoxes(const RootInlineBox* root)
 189 {
 190     if (m_rootInlineBox != root) {
 191         m_rootInlineBox = root;
 192         m_leafBoxes.clear();
 193         root->collectLeafBoxesInLogicalOrder(m_leafBoxes);
 194     }
 195     return m_leafBoxes;
 196 }
 197
 198 int CachedLogicallyOrderedLeafBoxes::boxIndexInLeaves(const InlineTextBox* box) const
 199 {
 200     for (size_t i = 0; i < m_leafBoxes.size(); ++i) {
 201         if (box == m_leafBoxes[i])
 202             return i;
 203     }
 204     return 0;
 205 }
 206
 207 static const InlineTextBox* logicallyPreviousBox(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
 208     bool& previousBoxInDifferentBlock, CachedLogicallyOrderedLeafBoxes& leafBoxes)
 209 {
 210     const InlineBox* startBox = textBox;
 211
 212     const InlineTextBox* previousBox = leafBoxes.previousTextBox(&startBox->root(), textBox);
 213     if (previousBox)
 214         return previousBox;
 215
 216     previousBox = leafBoxes.previousTextBox(startBox->root().prevRootBox(), 0);
 217     if (previousBox)
 218         return previousBox;
 219
 220     while (1) {
 221         Node* startNode = startBox->renderer().nonPseudoNode();
 222         if (!startNode)
 223             break;
 224
 225         Position position = previousRootInlineBoxCandidatePosition(startNode, visiblePosition, ContentIsEditable);
 226         if (position.isNull())
 227             break;
 228
 229         RenderedPosition renderedPosition(position, DOWNSTREAM);
 230         RootInlineBox* previousRoot = renderedPosition.rootBox();
 231         if (!previousRoot)
 232             break;
 233
 234         previousBox = leafBoxes.previousTextBox(previousRoot, 0);
 235         if (previousBox) {
 236             previousBoxInDifferentBlock = true;
 237             return previousBox;
 238         }
 239
 240         if (!leafBoxes.size())
 241             break;
 242         startBox = leafBoxes.firstBox();
 243     }
 244     return 0;
 245 }
 246
 247
 248 static const InlineTextBox* logicallyNextBox(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
 249     bool& nextBoxInDifferentBlock, CachedLogicallyOrderedLeafBoxes& leafBoxes)
 250 {
 251     const InlineBox* startBox = textBox;
 252
 253     const InlineTextBox* nextBox = leafBoxes.nextTextBox(&startBox->root(), textBox);
 254     if (nextBox)
 255         return nextBox;
 256
 257     nextBox = leafBoxes.nextTextBox(startBox->root().nextRootBox(), 0);
 258     if (nextBox)
 259         return nextBox;
 260
 261     while (1) {
 262         Node* startNode =startBox->renderer().nonPseudoNode();
 263         if (!startNode)
 264             break;
 265
 266         Position position = nextRootInlineBoxCandidatePosition(startNode, visiblePosition, ContentIsEditable);
 267         if (position.isNull())
 268             break;
 269
 270         RenderedPosition renderedPosition(position, DOWNSTREAM);
 271         RootInlineBox* nextRoot = renderedPosition.rootBox();
 272         if (!nextRoot)
 273             break;
 274
 275         nextBox = leafBoxes.nextTextBox(nextRoot, 0);
 276         if (nextBox) {
 277             nextBoxInDifferentBlock = true;
 278             return nextBox;
 279         }
 280
 281         if (!leafBoxes.size())
 282             break;
 283         startBox = leafBoxes.firstBox();
 284     }
 285     return 0;
 286 }
 287
 288 static TextBreakIterator* wordBreakIteratorForMinOffsetBoundary(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
 289     int& previousBoxLength, bool& previousBoxInDifferentBlock, Vector<UChar, 1024>& string, CachedLogicallyOrderedLeafBoxes& leafBoxes)
 290 {
 291     previousBoxInDifferentBlock = false;
 292
 293     // FIXME: Handle the case when we don't have an inline text box.
 294     const InlineTextBox* previousBox = logicallyPreviousBox(visiblePosition, textBox, previousBoxInDifferentBlock, leafBoxes);
 295
 296     int len = 0;
 297     string.clear();
 298     if (previousBox) {
 299         previousBoxLength = previousBox->len();
 300         previousBox->renderer().text().appendTo(string, previousBox->start(), previousBoxLength);
 301         len += previousBoxLength;
 302     }
 303     textBox->renderer().text().appendTo(string, textBox->start(), textBox->len());
 304     len += textBox->len();
 305
 306     return wordBreakIterator(string.data(), len);
 307 }
 308
 309 static TextBreakIterator* wordBreakIteratorForMaxOffsetBoundary(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
 310     bool& nextBoxInDifferentBlock, Vector<UChar, 1024>& string, CachedLogicallyOrderedLeafBoxes& leafBoxes)
 311 {
 312     nextBoxInDifferentBlock = false;
 313
 314     // FIXME: Handle the case when we don't have an inline text box.
 315     const InlineTextBox* nextBox = logicallyNextBox(visiblePosition, textBox, nextBoxInDifferentBlock, leafBoxes);
 316
 317     int len = 0;
 318     string.clear();
 319     textBox->renderer().text().appendTo(string, textBox->start(), textBox->len());
 320     len += textBox->len();
 321     if (nextBox) {
 322         nextBox->renderer().text().appendTo(string, nextBox->start(), nextBox->len());
 323         len += nextBox->len();
 324     }
 325
 326     return wordBreakIterator(string.data(), len);
 327 }
 328
 329 static bool isLogicalStartOfWord(TextBreakIterator* iter, int position, bool hardLineBreak)
 330 {
 331     bool boundary = hardLineBreak ? true : iter->isBoundary(position);
 332     if (!boundary)
 333         return false;
 334
 335     iter->following(position);
 336     // isWordTextBreak returns true after moving across a word and false after moving across a punctuation/space.
 337     return isWordTextBreak(iter);
 338 }
 339
 340 static bool islogicalEndOfWord(TextBreakIterator* iter, int position, bool hardLineBreak)
 341 {
 342     bool boundary = iter->isBoundary(position);
 343     return (hardLineBreak || boundary) && isWordTextBreak(iter);
 344 }
 345
 346 enum CursorMovementDirection { MoveLeft, MoveRight };
 347
 348 static VisiblePosition visualWordPosition(const VisiblePosition& visiblePosition, CursorMovementDirection direction,
 349     bool skipsSpaceWhenMovingRight)
 350 {
 351     if (visiblePosition.isNull())
 352         return VisiblePosition();
 353
 354     TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
 355     InlineBox* previouslyVisitedBox = 0;
 356     VisiblePosition current = visiblePosition;
 357     TextBreakIterator* iter = 0;
 358
 359     CachedLogicallyOrderedLeafBoxes leafBoxes;
 360     Vector<UChar, 1024> string;
 361
 362     while (1) {
 363         VisiblePosition adjacentCharacterPosition = direction == MoveRight ? current.right(true) : current.left(true);
 364         if (adjacentCharacterPosition == current || adjacentCharacterPosition.isNull())
 365             return VisiblePosition();
 366
 367         InlineBox* box;
 368         int offsetInBox;
 369         adjacentCharacterPosition.deepEquivalent().getInlineBoxAndOffset(UPSTREAM, box, offsetInBox);
 370
 371         if (!box)
 372             break;
 373         if (!box->isInlineTextBox()) {
 374             current = adjacentCharacterPosition;
 375             continue;
 376         }
 377
 378         InlineTextBox* textBox = toInlineTextBox(box);
 379         int previousBoxLength = 0;
 380         bool previousBoxInDifferentBlock = false;
 381         bool nextBoxInDifferentBlock = false;
 382         bool movingIntoNewBox = previouslyVisitedBox != box;
 383
 384         if (offsetInBox == box->caretMinOffset())
 385             iter = wordBreakIteratorForMinOffsetBoundary(visiblePosition, textBox, previousBoxLength, previousBoxInDifferentBlock, string, leafBoxes);
 386         else if (offsetInBox == box->caretMaxOffset())
 387             iter = wordBreakIteratorForMaxOffsetBoundary(visiblePosition, textBox, nextBoxInDifferentBlock, string, leafBoxes);
 388         else if (movingIntoNewBox) {
 389             iter = wordBreakIterator(textBox->renderer().text(), textBox->start(), textBox->len());
 390             previouslyVisitedBox = box;
 391         }
 392
 393         if (!iter)
 394             break;
 395
 396         iter->first();
 397         int offsetInIterator = offsetInBox - textBox->start() + previousBoxLength;
 398
 399         bool isWordBreak;
 400         bool boxHasSameDirectionalityAsBlock = box->direction() == blockDirection;
 401         bool movingBackward = (direction == MoveLeft && box->direction() == LTR) || (direction == MoveRight && box->direction() == RTL);
 402         if ((skipsSpaceWhenMovingRight && boxHasSameDirectionalityAsBlock)
 403             || (!skipsSpaceWhenMovingRight && movingBackward)) {
 404             bool logicalStartInRenderer = offsetInBox == static_cast<int>(textBox->start()) && previousBoxInDifferentBlock;
 405             isWordBreak = isLogicalStartOfWord(iter, offsetInIterator, logicalStartInRenderer);
 406         } else {
 407             bool logicalEndInRenderer = offsetInBox == static_cast<int>(textBox->start() + textBox->len()) && nextBoxInDifferentBlock;
 408             isWordBreak = islogicalEndOfWord(iter, offsetInIterator, logicalEndInRenderer);
 409         }
 410
 411         if (isWordBreak)
 412             return adjacentCharacterPosition;
 413
 414         current = adjacentCharacterPosition;
 415     }
 416     return VisiblePosition();
 417 }
 418
 419 VisiblePosition leftWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
 420 {
 421     VisiblePosition leftWordBreak = visualWordPosition(visiblePosition, MoveLeft, skipsSpaceWhenMovingRight);
 422     leftWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(leftWordBreak);
 423
 424     // FIXME: How should we handle a non-editable position?
 425     if (leftWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
 426         TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
 427         leftWordBreak = blockDirection == LTR ? startOfEditableContent(visiblePosition) : endOfEditableContent(visiblePosition);
 428     }
 429     return leftWordBreak;
 430 }
 431
 432 VisiblePosition rightWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
 433 {
 434     VisiblePosition rightWordBreak = visualWordPosition(visiblePosition, MoveRight, skipsSpaceWhenMovingRight);
 435     rightWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(rightWordBreak);
 436
 437     // FIXME: How should we handle a non-editable position?
 438     if (rightWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
 439         TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
 440         rightWordBreak = blockDirection == LTR ? endOfEditableContent(visiblePosition) : startOfEditableContent(visiblePosition);
 441     }
 442     return rightWordBreak;
 443 }
 444
 445
 446 enum BoundarySearchContextAvailability { DontHaveMoreContext, MayHaveMoreContext };
 447
 448 typedef unsigned (*BoundarySearchFunction)(const UChar*, unsigned length, unsigned offset, BoundarySearchContextAvailability, bool& needMoreContext);
 449
 450 static VisiblePosition previousBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
 451 {
 452     Position pos = c.deepEquivalent();
 453     Node* boundary = pos.parentEditingBoundary();
 454     if (!boundary)
 455         return VisiblePosition();
 456
 457     Document& d = boundary->document();
 458     Position start = createLegacyEditingPosition(boundary, 0).parentAnchoredEquivalent();
 459     Position end = pos.parentAnchoredEquivalent();
 460     RefPtrWillBeRawPtr<Range> searchRange = Range::create(d);
 461
 462     Vector<UChar, 1024> string;
 463     unsigned suffixLength = 0;
 464
 465     TrackExceptionState exceptionState;
 466     if (requiresContextForWordBoundary(c.characterBefore())) {
 467         RefPtrWillBeRawPtr<Range> forwardsScanRange(d.createRange());
 468         forwardsScanRange->setEndAfter(boundary, exceptionState);
 469         forwardsScanRange->setStart(end.deprecatedNode(), end.deprecatedEditingOffset(), exceptionState);
 470         TextIterator forwardsIterator(forwardsScanRange.get());
 471         while (!forwardsIterator.atEnd()) {
 472             Vector<UChar, 1024> characters;
 473             forwardsIterator.appendTextTo(characters);
 474             int i = endOfFirstWordBoundaryContext(characters.data(), characters.size());
 475             string.append(characters.data(), i);
 476             suffixLength += i;
 477             if (static_cast<unsigned>(i) < characters.size())
 478                 break;
 479             forwardsIterator.advance();
 480         }
 481     }
 482
 483     searchRange->setStart(start.deprecatedNode(), start.deprecatedEditingOffset(), exceptionState);
 484     searchRange->setEnd(end.deprecatedNode(), end.deprecatedEditingOffset(), exceptionState);
 485
 486     ASSERT(!exceptionState.hadException());
 487     if (exceptionState.hadException())
 488         return VisiblePosition();
 489
 490     SimplifiedBackwardsTextIterator it(searchRange.get());
 491     unsigned next = 0;
 492     bool needMoreContext = false;
 493     while (!it.atEnd()) {
 494         bool inTextSecurityMode = it.node() && it.node()->renderer() && it.node()->renderer()->style()->textSecurity() != TSNONE;
 495         // iterate to get chunks until the searchFunction returns a non-zero value.
 496         if (!inTextSecurityMode)
 497             it.prependTextTo(string);
 498         else {
 499             // Treat bullets used in the text security mode as regular characters when looking for boundaries
 500             Vector<UChar, 1024> iteratorString;
 501             iteratorString.fill('x', it.length());
 502             string.prepend(iteratorString.data(), iteratorString.size());
 503         }
 504         next = searchFunction(string.data(), string.size(), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
 505         if (next)
 506             break;
 507         it.advance();
 508     }
 509     if (needMoreContext) {
 510         // The last search returned the beginning of the buffer and asked for more context,
 511         // but there is no earlier text. Force a search with what's available.
 512         next = searchFunction(string.data(), string.size(), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);
 513         ASSERT(!needMoreContext);
 514     }
 515
 516     if (!next)
 517         return VisiblePosition(it.atEnd() ? it.range()->startPosition() : pos, DOWNSTREAM);
 518
 519     Node* node = it.range()->startContainer();
 520     if ((node->isTextNode() && static_cast<int>(next) <= node->maxCharacterOffset()) || (node->renderer() && node->renderer()->isBR() && !next))
 521         // The next variable contains a usable index into a text node
 522         return VisiblePosition(createLegacyEditingPosition(node, next), DOWNSTREAM);
 523
 524     // Use the character iterator to translate the next value into a DOM position.
 525     BackwardsCharacterIterator charIt(searchRange.get());
 526     charIt.advance(string.size() - suffixLength - next);
 527     // FIXME: charIt can get out of shadow host.
 528     return VisiblePosition(charIt.range()->endPosition(), DOWNSTREAM);
 529 }
 530
 531 static VisiblePosition nextBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
 532 {
 533     Position pos = c.deepEquivalent();
 534     Node* boundary = pos.parentEditingBoundary();
 535     if (!boundary)
 536         return VisiblePosition();
 537
 538     Document& d = boundary->document();
 539     RefPtrWillBeRawPtr<Range> searchRange(d.createRange());
 540     Position start(pos.parentAnchoredEquivalent());
 541
 542     Vector<UChar, 1024> string;
 543     unsigned prefixLength = 0;
 544
 545     if (requiresContextForWordBoundary(c.characterAfter())) {
 546         RefPtrWillBeRawPtr<Range> backwardsScanRange(d.createRange());
 547         backwardsScanRange->setEnd(start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
 548         SimplifiedBackwardsTextIterator backwardsIterator(backwardsScanRange.get());
 549         while (!backwardsIterator.atEnd()) {
 550             Vector<UChar, 1024> characters;
 551             backwardsIterator.prependTextTo(characters);
 552             int length = characters.size();
 553             int i = startOfLastWordBoundaryContext(characters.data(), length);
 554             string.prepend(characters.data() + i, length - i);
 555             prefixLength += length - i;
 556             if (i > 0)
 557                 break;
 558             backwardsIterator.advance();
 559         }
 560     }
 561
 562     searchRange->selectNodeContents(boundary, IGNORE_EXCEPTION);
 563     searchRange->setStart(start.deprecatedNode(), start.deprecatedEditingOffset(), IGNORE_EXCEPTION);
 564     TextIterator it(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
 565     const unsigned invalidOffset = static_cast<unsigned>(-1);
 566     unsigned next = invalidOffset;
 567     bool needMoreContext = false;
 568     while (!it.atEnd()) {
 569         // Keep asking the iterator for chunks until the search function
 570         // returns an end value not equal to the length of the string passed to it.
 571         bool inTextSecurityMode = it.node() && it.node()->renderer() && it.node()->renderer()->style()->textSecurity() != TSNONE;
 572         if (!inTextSecurityMode)
 573             it.appendTextTo(string);
 574         else {
 575             // Treat bullets used in the text security mode as regular characters when looking for boundaries
 576             Vector<UChar, 1024> iteratorString;
 577             iteratorString.fill('x', it.length());
 578             string.append(iteratorString.data(), iteratorString.size());
 579         }
 580         next = searchFunction(string.data(), string.size(), prefixLength, MayHaveMoreContext, needMoreContext);
 581         if (next != string.size())
 582             break;
 583         it.advance();
 584     }
 585     if (needMoreContext) {
 586         // The last search returned the end of the buffer and asked for more context,
 587         // but there is no further text. Force a search with what's available.
 588         next = searchFunction(string.data(), string.size(), prefixLength, DontHaveMoreContext, needMoreContext);
 589         ASSERT(!needMoreContext);
 590     }
 591
 592     if (it.atEnd() && next == string.size()) {
 593         pos = it.range()->startPosition();
 594     } else if (next != invalidOffset && next != prefixLength) {
 595         // Use the character iterator to translate the next value into a DOM position.
 596         CharacterIterator charIt(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
 597         charIt.advance(next - prefixLength - 1);
 598         RefPtrWillBeRawPtr<Range> characterRange = charIt.range();
 599         pos = characterRange->endPosition();
 600
 601         if (charIt.characterAt(0) == '\n') {
 602             // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)
 603             VisiblePosition visPos = VisiblePosition(pos);
 604             if (visPos == VisiblePosition(characterRange->startPosition())) {
 605                 charIt.advance(1);
 606                 pos = charIt.range()->startPosition();
 607             }
 608         }
 609     }
 610
 611     // generate VisiblePosition, use UPSTREAM affinity if possible
 612     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
 613 }
 614
 615 // ---------
 616
 617 static unsigned startWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 618 {
 619     ASSERT(offset);
 620     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
 621         needMoreContext = true;
 622         return 0;
 623     }
 624     needMoreContext = false;
 625     int start, end;
 626     U16_BACK_1(characters, 0, offset);
 627     findWordBoundary(characters, length, offset, &start, &end);
 628     return start;
 629 }
 630
 631 VisiblePosition startOfWord(const VisiblePosition &c, EWordSide side)
 632 {
 633     // FIXME: This returns a null VP for c at the start of the document
 634     // and side == LeftWordIfOnBoundary
 635     VisiblePosition p = c;
 636     if (side == RightWordIfOnBoundary) {
 637         // at paragraph end, the startofWord is the current position
 638         if (isEndOfParagraph(c))
 639             return c;
 640
 641         p = c.next();
 642         if (p.isNull())
 643             return c;
 644     }
 645     return previousBoundary(p, startWordBoundary);
 646 }
 647
 648 static unsigned endWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 649 {
 650     ASSERT(offset <= length);
 651     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
 652         needMoreContext = true;
 653         return length;
 654     }
 655     needMoreContext = false;
 656     return findWordEndBoundary(characters, length, offset);
 657 }
 658
 659 VisiblePosition endOfWord(const VisiblePosition &c, EWordSide side)
 660 {
 661     VisiblePosition p = c;
 662     if (side == LeftWordIfOnBoundary) {
 663         if (isStartOfParagraph(c))
 664             return c;
 665
 666         p = c.previous();
 667         if (p.isNull())
 668             return c;
 669     } else if (isEndOfParagraph(c))
 670         return c;
 671
 672     return nextBoundary(p, endWordBoundary);
 673 }
 674
 675 static unsigned previousWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 676 {
 677     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
 678         needMoreContext = true;
 679         return 0;
 680     }
 681     needMoreContext = false;
 682     return findNextWordFromIndex(characters, length, offset, false);
 683 }
 684
 685 VisiblePosition previousWordPosition(const VisiblePosition &c)
 686 {
 687     VisiblePosition prev = previousBoundary(c, previousWordPositionBoundary);
 688     return c.honorEditingBoundaryAtOrBefore(prev);
 689 }
 690
 691 static unsigned nextWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 692 {
 693     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
 694         needMoreContext = true;
 695         return length;
 696     }
 697     needMoreContext = false;
 698     return findNextWordFromIndex(characters, length, offset, true);
 699 }
 700
 701 VisiblePosition nextWordPosition(const VisiblePosition &c)
 702 {
 703     VisiblePosition next = nextBoundary(c, nextWordPositionBoundary);
 704     return c.honorEditingBoundaryAtOrAfter(next);
 705 }
 706
 707 // ---------
 708
 709 enum LineEndpointComputationMode { UseLogicalOrdering, UseInlineBoxOrdering };
 710 static VisiblePosition startPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
 711 {
 712     if (c.isNull())
 713         return VisiblePosition();
 714
 715     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
 716     if (!rootBox) {
 717         // There are VisiblePositions at offset 0 in blocks without
 718         // RootInlineBoxes, like empty editable blocks and bordered blocks.
 719         Position p = c.deepEquivalent();
 720         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
 721             return c;
 722
 723         return VisiblePosition();
 724     }
 725
 726     Node* startNode;
 727     InlineBox* startBox;
 728     if (mode == UseLogicalOrdering) {
 729         startNode = rootBox->getLogicalStartBoxWithNode(startBox);
 730         if (!startNode)
 731             return VisiblePosition();
 732     } else {
 733         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
 734         // and so cannot be represented by a VisiblePosition. Use whatever follows instead.
 735         startBox = rootBox->firstLeafChild();
 736         while (true) {
 737             if (!startBox)
 738                 return VisiblePosition();
 739
 740             startNode = startBox->renderer().nonPseudoNode();
 741             if (startNode)
 742                 break;
 743
 744             startBox = startBox->nextLeafChild();
 745         }
 746     }
 747
 748     return VisiblePosition(startNode->isTextNode() ? Position(toText(startNode), toInlineTextBox(startBox)->start()) : positionBeforeNode(startNode));
 749 }
 750
 751 static VisiblePosition startOfLine(const VisiblePosition& c, LineEndpointComputationMode mode)
 752 {
 753     // TODO: this is the current behavior that might need to be fixed.
 754     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
 755     VisiblePosition visPos = startPositionForLine(c, mode);
 756
 757     if (mode == UseLogicalOrdering) {
 758         if (ContainerNode* editableRoot = highestEditableRoot(c.deepEquivalent())) {
 759             if (!editableRoot->contains(visPos.deepEquivalent().containerNode()))
 760                 return VisiblePosition(firstPositionInNode(editableRoot));
 761         }
 762     }
 763
 764     return c.honorEditingBoundaryAtOrBefore(visPos);
 765 }
 766
 767 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
 768 VisiblePosition startOfLine(const VisiblePosition& currentPosition)
 769 {
 770     return startOfLine(currentPosition, UseInlineBoxOrdering);
 771 }
 772
 773 VisiblePosition logicalStartOfLine(const VisiblePosition& currentPosition)
 774 {
 775     return startOfLine(currentPosition, UseLogicalOrdering);
 776 }
 777
 778 static VisiblePosition endPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
 779 {
 780     if (c.isNull())
 781         return VisiblePosition();
 782
 783     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
 784     if (!rootBox) {
 785         // There are VisiblePositions at offset 0 in blocks without
 786         // RootInlineBoxes, like empty editable blocks and bordered blocks.
 787         Position p = c.deepEquivalent();
 788         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
 789             return c;
 790         return VisiblePosition();
 791     }
 792
 793     Node* endNode;
 794     InlineBox* endBox;
 795     if (mode == UseLogicalOrdering) {
 796         endNode = rootBox->getLogicalEndBoxWithNode(endBox);
 797         if (!endNode)
 798             return VisiblePosition();
 799     } else {
 800         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
 801         // and so cannot be represented by a VisiblePosition. Use whatever precedes instead.
 802         endBox = rootBox->lastLeafChild();
 803         while (true) {
 804             if (!endBox)
 805                 return VisiblePosition();
 806
 807             endNode = endBox->renderer().nonPseudoNode();
 808             if (endNode)
 809                 break;
 810
 811             endBox = endBox->prevLeafChild();
 812         }
 813     }
 814
 815     Position pos;
 816     if (isHTMLBRElement(*endNode))
 817         pos = positionBeforeNode(endNode);
 818     else if (endBox->isInlineTextBox() && endNode->isTextNode()) {
 819         InlineTextBox* endTextBox = toInlineTextBox(endBox);
 820         int endOffset = endTextBox->start();
 821         if (!endTextBox->isLineBreak())
 822             endOffset += endTextBox->len();
 823         pos = Position(toText(endNode), endOffset);
 824     } else
 825         pos = positionAfterNode(endNode);
 826
 827     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
 828 }
 829
 830 static bool inSameLogicalLine(const VisiblePosition& a, const VisiblePosition& b)
 831 {
 832     return a.isNotNull() && logicalStartOfLine(a) == logicalStartOfLine(b);
 833 }
 834
 835 static VisiblePosition endOfLine(const VisiblePosition& c, LineEndpointComputationMode mode)
 836 {
 837     // TODO: this is the current behavior that might need to be fixed.
 838     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
 839     VisiblePosition visPos = endPositionForLine(c, mode);
 840
 841     if (mode == UseLogicalOrdering) {
 842         // Make sure the end of line is at the same line as the given input position. For a wrapping line, the logical end
 843         // position for the not-last-2-lines might incorrectly hand back the logical beginning of the next line.
 844         // For example, <div contenteditable dir="rtl" style="line-break:before-white-space">abcdefg abcdefg abcdefg
 845         // a abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg </div>
 846         // In this case, use the previous position of the computed logical end position.
 847         if (!inSameLogicalLine(c, visPos))
 848             visPos = visPos.previous();
 849
 850         if (ContainerNode* editableRoot = highestEditableRoot(c.deepEquivalent())) {
 851             if (!editableRoot->contains(visPos.deepEquivalent().containerNode()))
 852                 return VisiblePosition(lastPositionInNode(editableRoot));
 853         }
 854
 855         return c.honorEditingBoundaryAtOrAfter(visPos);
 856     }
 857
 858     // Make sure the end of line is at the same line as the given input position. Else use the previous position to
 859     // obtain end of line. This condition happens when the input position is before the space character at the end
 860     // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position
 861     // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style
 862     // versus lines without that style, which would break before a space by default.
 863     if (!inSameLine(c, visPos)) {
 864         visPos = c.previous();
 865         if (visPos.isNull())
 866             return VisiblePosition();
 867         visPos = endPositionForLine(visPos, UseInlineBoxOrdering);
 868     }
 869
 870     return c.honorEditingBoundaryAtOrAfter(visPos);
 871 }
 872
 873 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
 874 VisiblePosition endOfLine(const VisiblePosition& currentPosition)
 875 {
 876     return endOfLine(currentPosition, UseInlineBoxOrdering);
 877 }
 878
 879 VisiblePosition logicalEndOfLine(const VisiblePosition& currentPosition)
 880 {
 881     return endOfLine(currentPosition, UseLogicalOrdering);
 882 }
 883
 884 bool inSameLine(const VisiblePosition &a, const VisiblePosition &b)
 885 {
 886     return a.isNotNull() && startOfLine(a) == startOfLine(b);
 887 }
 888
 889 bool isStartOfLine(const VisiblePosition &p)
 890 {
 891     return p.isNotNull() && p == startOfLine(p);
 892 }
 893
 894 bool isEndOfLine(const VisiblePosition &p)
 895 {
 896     return p.isNotNull() && p == endOfLine(p);
 897 }
 898
 899 bool isLogicalEndOfLine(const VisiblePosition &p)
 900 {
 901     return p.isNotNull() && p == logicalEndOfLine(p);
 902 }
 903
 904 static inline IntPoint absoluteLineDirectionPointToLocalPointInBlock(RootInlineBox* root, int lineDirectionPoint)
 905 {
 906     ASSERT(root);
 907     RenderBlockFlow& containingBlock = root->block();
 908     FloatPoint absoluteBlockPoint = containingBlock.localToAbsolute(FloatPoint());
 909     if (containingBlock.hasOverflowClip())
 910         absoluteBlockPoint -= containingBlock.scrolledContentOffset();
 911
 912     if (root->block().isHorizontalWritingMode())
 913         return IntPoint(lineDirectionPoint - absoluteBlockPoint.x(), root->blockDirectionPointInLine());
 914
 915     return IntPoint(root->blockDirectionPointInLine(), lineDirectionPoint - absoluteBlockPoint.y());
 916 }
 917
 918 VisiblePosition previousLinePosition(const VisiblePosition &visiblePosition, int lineDirectionPoint, EditableType editableType)
 919 {
 920     Position p = visiblePosition.deepEquivalent();
 921     Node* node = p.deprecatedNode();
 922
 923     if (!node)
 924         return VisiblePosition();
 925
 926     node->document().updateLayoutIgnorePendingStylesheets();
 927
 928     RenderObject* renderer = node->renderer();
 929     if (!renderer)
 930         return VisiblePosition();
 931
 932     RootInlineBox* root = 0;
 933     InlineBox* box;
 934     int ignoredCaretOffset;
 935     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
 936     if (box) {
 937         root = box->root().prevRootBox();
 938         // We want to skip zero height boxes.
 939         // This could happen in case it is a TrailingFloatsRootInlineBox.
 940         if (!root || !root->logicalHeight() || !root->firstLeafChild())
 941             root = 0;
 942     }
 943
 944     if (!root) {
 945         Position position = previousRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
 946         if (position.isNotNull()) {
 947             RenderedPosition renderedPosition((VisiblePosition(position)));
 948             root = renderedPosition.rootBox();
 949             if (!root)
 950                 return VisiblePosition(position);
 951         }
 952     }
 953
 954     if (root) {
 955         // FIXME: Can be wrong for multi-column layout and with transforms.
 956         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(root, lineDirectionPoint);
 957         RenderObject& renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
 958         Node* node = renderer.node();
 959         if (node && editingIgnoresContent(node))
 960             return VisiblePosition(positionInParentBeforeNode(*node));
 961         return VisiblePosition(renderer.positionForPoint(pointInLine));
 962     }
 963
 964     // Could not find a previous line. This means we must already be on the first line.
 965     // Move to the start of the content in this block, which effectively moves us
 966     // to the start of the line we're on.
 967     Element* rootElement = node->hasEditableStyle(editableType) ? node->rootEditableElement(editableType) : node->document().documentElement();
 968     if (!rootElement)
 969         return VisiblePosition();
 970     return VisiblePosition(firstPositionInNode(rootElement), DOWNSTREAM);
 971 }
 972
 973 VisiblePosition nextLinePosition(const VisiblePosition &visiblePosition, int lineDirectionPoint, EditableType editableType)
 974 {
 975     Position p = visiblePosition.deepEquivalent();
 976     Node* node = p.deprecatedNode();
 977
 978     if (!node)
 979         return VisiblePosition();
 980
 981     node->document().updateLayoutIgnorePendingStylesheets();
 982
 983     RenderObject* renderer = node->renderer();
 984     if (!renderer)
 985         return VisiblePosition();
 986
 987     RootInlineBox* root = 0;
 988     InlineBox* box;
 989     int ignoredCaretOffset;
 990     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
 991     if (box) {
 992         root = box->root().nextRootBox();
 993         // We want to skip zero height boxes.
 994         // This could happen in case it is a TrailingFloatsRootInlineBox.
 995         if (!root || !root->logicalHeight() || !root->firstLeafChild())
 996             root = 0;
 997     }
 998
 999     if (!root) {
1000         // FIXME: We need do the same in previousLinePosition.
1001         Node* child = NodeTraversal::childAt(*node, p.deprecatedEditingOffset());
1002         node = child ? child : &NodeTraversal::lastWithinOrSelf(*node);
1003         Position position = nextRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
1004         if (position.isNotNull()) {
1005             RenderedPosition renderedPosition((VisiblePosition(position)));
1006             root = renderedPosition.rootBox();
1007             if (!root)
1008                 return VisiblePosition(position);
1009         }
1010     }
1011
1012     if (root) {
1013         // FIXME: Can be wrong for multi-column layout and with transforms.
1014         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(root, lineDirectionPoint);
1015         RenderObject& renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
1016         Node* node = renderer.node();
1017         if (node && editingIgnoresContent(node))
1018             return VisiblePosition(positionInParentBeforeNode(*node));
1019         return VisiblePosition(renderer.positionForPoint(pointInLine));
1020     }
1021
1022     // Could not find a next line. This means we must already be on the last line.
1023     // Move to the end of the content in this block, which effectively moves us
1024     // to the end of the line we're on.
1025     Element* rootElement = node->hasEditableStyle(editableType) ? node->rootEditableElement(editableType) : node->document().documentElement();
1026     if (!rootElement)
1027         return VisiblePosition();
1028     return VisiblePosition(lastPositionInNode(rootElement), DOWNSTREAM);
1029 }
1030
1031 // ---------
1032
1033 static unsigned startSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1034 {
1035     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1036     // FIXME: The following function can return -1; we don't handle that.
1037     return iterator->preceding(length);
1038 }
1039
1040 VisiblePosition startOfSentence(const VisiblePosition &c)
1041 {
1042     return previousBoundary(c, startSentenceBoundary);
1043 }
1044
1045 static unsigned endSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1046 {
1047     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1048     return iterator->next();
1049 }
1050
1051 // FIXME: This includes the space after the punctuation that marks the end of the sentence.
1052 VisiblePosition endOfSentence(const VisiblePosition &c)
1053 {
1054     return nextBoundary(c, endSentenceBoundary);
1055 }
1056
1057 static unsigned previousSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1058 {
1059     // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
1060     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1061     // FIXME: The following function can return -1; we don't handle that.
1062     return iterator->preceding(length);
1063 }
1064
1065 VisiblePosition previousSentencePosition(const VisiblePosition &c)
1066 {
1067     VisiblePosition prev = previousBoundary(c, previousSentencePositionBoundary);
1068     return c.honorEditingBoundaryAtOrBefore(prev);
1069 }
1070
1071 static unsigned nextSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
1072 {
1073     // FIXME: This is identical to endSentenceBoundary. This isn't right, it needs to
1074     // move to the equivlant position in the following sentence.
1075     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
1076     return iterator->following(0);
1077 }
1078
1079 VisiblePosition nextSentencePosition(const VisiblePosition &c)
1080 {
1081     VisiblePosition next = nextBoundary(c, nextSentencePositionBoundary);
1082     return c.honorEditingBoundaryAtOrAfter(next);
1083 }
1084
1085 VisiblePosition startOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1086 {
1087     Position p = c.deepEquivalent();
1088     Node* startNode = p.deprecatedNode();
1089
1090     if (!startNode)
1091         return VisiblePosition();
1092
1093     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1094         return VisiblePosition(positionBeforeNode(startNode));
1095
1096     Element* startBlock = enclosingBlock(startNode);
1097
1098     Node* node = startNode;
1099     ContainerNode* highestRoot = highestEditableRoot(p);
1100     int offset = p.deprecatedEditingOffset();
1101     Position::AnchorType type = p.anchorType();
1102
1103     Node* n = startNode;
1104     bool startNodeIsEditable = startNode->hasEditableStyle();
1105     while (n) {
1106         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNodeIsEditable)
1107             break;
1108         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1109             while (n && n->hasEditableStyle() != startNodeIsEditable)
1110                 n = NodeTraversal::previousPostOrder(*n, startBlock);
1111             if (!n || !n->isDescendantOf(highestRoot))
1112                 break;
1113         }
1114         RenderObject* r = n->renderer();
1115         if (!r) {
1116             n = NodeTraversal::previousPostOrder(*n, startBlock);
1117             continue;
1118         }
1119         RenderStyle* style = r->style();
1120         if (style->visibility() != VISIBLE) {
1121             n = NodeTraversal::previousPostOrder(*n, startBlock);
1122             continue;
1123         }
1124
1125         if (r->isBR() || isBlock(n))
1126             break;
1127
1128         if (r->isText() && toRenderText(r)->renderedTextLength()) {
1129             ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1130             type = Position::PositionIsOffsetInAnchor;
1131             if (style->preserveNewline()) {
1132                 RenderText* text = toRenderText(r);
1133                 int i = text->textLength();
1134                 int o = offset;
1135                 if (n == startNode && o < i)
1136                     i = max(0, o);
1137                 while (--i >= 0) {
1138                     if ((*text)[i] == '\n')
1139                         return VisiblePosition(Position(toText(n), i + 1), DOWNSTREAM);
1140                 }
1141             }
1142             node = n;
1143             offset = 0;
1144             n = NodeTraversal::previousPostOrder(*n, startBlock);
1145         } else if (editingIgnoresContent(n) || isRenderedTableElement(n)) {
1146             node = n;
1147             type = Position::PositionIsBeforeAnchor;
1148             n = n->previousSibling() ? n->previousSibling() : NodeTraversal::previousPostOrder(*n, startBlock);
1149         } else {
1150             n = NodeTraversal::previousPostOrder(*n, startBlock);
1151         }
1152     }
1153
1154     if (type == Position::PositionIsOffsetInAnchor) {
1155         ASSERT(type == Position::PositionIsOffsetInAnchor || !offset);
1156         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1157     }
1158
1159     return VisiblePosition(Position(node, type), DOWNSTREAM);
1160 }
1161
1162 VisiblePosition endOfParagraph(const VisiblePosition &c, EditingBoundaryCrossingRule boundaryCrossingRule)
1163 {
1164     if (c.isNull())
1165         return VisiblePosition();
1166
1167     Position p = c.deepEquivalent();
1168     Node* startNode = p.deprecatedNode();
1169
1170     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1171         return VisiblePosition(positionAfterNode(startNode));
1172
1173     Element* startBlock = enclosingBlock(startNode);
1174     Element* stayInsideBlock = startBlock;
1175
1176     Node* node = startNode;
1177     ContainerNode* highestRoot = highestEditableRoot(p);
1178     int offset = p.deprecatedEditingOffset();
1179     Position::AnchorType type = p.anchorType();
1180
1181     Node* n = startNode;
1182     bool startNodeIsEditable = startNode->hasEditableStyle();
1183     while (n) {
1184         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNodeIsEditable)
1185             break;
1186         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1187             while (n && n->hasEditableStyle() != startNodeIsEditable)
1188                 n = NodeTraversal::next(*n, stayInsideBlock);
1189             if (!n || !n->isDescendantOf(highestRoot))
1190                 break;
1191         }
1192
1193         RenderObject* r = n->renderer();
1194         if (!r) {
1195             n = NodeTraversal::next(*n, stayInsideBlock);
1196             continue;
1197         }
1198         RenderStyle* style = r->style();
1199         if (style->visibility() != VISIBLE) {
1200             n = NodeTraversal::next(*n, stayInsideBlock);
1201             continue;
1202         }
1203
1204         if (r->isBR() || isBlock(n))
1205             break;
1206
1207         // FIXME: We avoid returning a position where the renderer can't accept the caret.
1208         if (r->isText() && toRenderText(r)->renderedTextLength()) {
1209             ASSERT_WITH_SECURITY_IMPLICATION(n->isTextNode());
1210             int length = toRenderText(r)->textLength();
1211             type = Position::PositionIsOffsetInAnchor;
1212             if (style->preserveNewline()) {
1213                 RenderText* text = toRenderText(r);
1214                 int o = n == startNode ? offset : 0;
1215                 for (int i = o; i < length; ++i) {
1216                     if ((*text)[i] == '\n')
1217                         return VisiblePosition(Position(toText(n), i), DOWNSTREAM);
1218                 }
1219             }
1220             node = n;
1221             offset = r->caretMaxOffset();
1222             n = NodeTraversal::next(*n, stayInsideBlock);
1223         } else if (editingIgnoresContent(n) || isRenderedTableElement(n)) {
1224             node = n;
1225             type = Position::PositionIsAfterAnchor;
1226             n = NodeTraversal::nextSkippingChildren(*n, stayInsideBlock);
1227         } else {
1228             n = NodeTraversal::next(*n, stayInsideBlock);
1229         }
1230     }
1231
1232     if (type == Position::PositionIsOffsetInAnchor)
1233         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1234
1235     return VisiblePosition(Position(node, type), DOWNSTREAM);
1236 }
1237
1238 // FIXME: isStartOfParagraph(startOfNextParagraph(pos)) is not always true
1239 VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
1240 {
1241     VisiblePosition paragraphEnd(endOfParagraph(visiblePosition, CanSkipOverEditingBoundary));
1242     VisiblePosition afterParagraphEnd(paragraphEnd.next(CannotCrossEditingBoundary));
1243     // The position after the last position in the last cell of a table
1244     // is not the start of the next paragraph.
1245     if (isFirstPositionAfterTable(afterParagraphEnd))
1246         return afterParagraphEnd.next(CannotCrossEditingBoundary);
1247     return afterParagraphEnd;
1248 }
1249
1250 bool inSameParagraph(const VisiblePosition &a, const VisiblePosition &b, EditingBoundaryCrossingRule boundaryCrossingRule)
1251 {
1252     return a.isNotNull() && startOfParagraph(a, boundaryCrossingRule) == startOfParagraph(b, boundaryCrossingRule);
1253 }
1254
1255 bool isStartOfParagraph(const VisiblePosition &pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1256 {
1257     return pos.isNotNull() && pos == startOfParagraph(pos, boundaryCrossingRule);
1258 }
1259
1260 bool isEndOfParagraph(const VisiblePosition &pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1261 {
1262     return pos.isNotNull() && pos == endOfParagraph(pos, boundaryCrossingRule);
1263 }
1264
1265 VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
1266 {
1267     VisiblePosition pos = p;
1268     do {
1269         VisiblePosition n = previousLinePosition(pos, x);
1270         if (n.isNull() || n == pos)
1271             break;
1272         pos = n;
1273     } while (inSameParagraph(p, pos));
1274     return pos;
1275 }
1276
1277 VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
1278 {
1279     VisiblePosition pos = p;
1280     do {
1281         VisiblePosition n = nextLinePosition(pos, x);
1282         if (n.isNull() || n == pos)
1283             break;
1284         pos = n;
1285     } while (inSameParagraph(p, pos));
1286     return pos;
1287 }
1288
1289 // ---------
1290
1291 VisiblePosition startOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1292 {
1293     Position position = visiblePosition.deepEquivalent();
1294     Element* startBlock = position.containerNode() ? enclosingBlock(position.containerNode(), rule) : 0;
1295     return startBlock ? VisiblePosition(firstPositionInNode(startBlock)) : VisiblePosition();
1296 }
1297
1298 VisiblePosition endOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1299 {
1300     Position position = visiblePosition.deepEquivalent();
1301     Element* endBlock = position.containerNode() ? enclosingBlock(position.containerNode(), rule) : 0;
1302     return endBlock ? VisiblePosition(lastPositionInNode(endBlock)) : VisiblePosition();
1303 }
1304
1305 bool inSameBlock(const VisiblePosition &a, const VisiblePosition &b)
1306 {
1307     return !a.isNull() && enclosingBlock(a.deepEquivalent().containerNode()) == enclosingBlock(b.deepEquivalent().containerNode());
1308 }
1309
1310 bool isStartOfBlock(const VisiblePosition &pos)
1311 {
1312     return pos.isNotNull() && pos == startOfBlock(pos, CanCrossEditingBoundary);
1313 }
1314
1315 bool isEndOfBlock(const VisiblePosition &pos)
1316 {
1317     return pos.isNotNull() && pos == endOfBlock(pos, CanCrossEditingBoundary);
1318 }
1319
1320 // ---------
1321
1322 VisiblePosition startOfDocument(const Node* node)
1323 {
1324     if (!node || !node->document().documentElement())
1325         return VisiblePosition();
1326
1327     return VisiblePosition(firstPositionInNode(node->document().documentElement()), DOWNSTREAM);
1328 }
1329
1330 VisiblePosition startOfDocument(const VisiblePosition &c)
1331 {
1332     return startOfDocument(c.deepEquivalent().deprecatedNode());
1333 }
1334
1335 VisiblePosition endOfDocument(const Node* node)
1336 {
1337     if (!node || !node->document().documentElement())
1338         return VisiblePosition();
1339
1340     Element* doc = node->document().documentElement();
1341     return VisiblePosition(lastPositionInNode(doc), DOWNSTREAM);
1342 }
1343
1344 VisiblePosition endOfDocument(const VisiblePosition &c)
1345 {
1346     return endOfDocument(c.deepEquivalent().deprecatedNode());
1347 }
1348
1349 bool isStartOfDocument(const VisiblePosition &p)
1350 {
1351     return p.isNotNull() && p.previous(CanCrossEditingBoundary).isNull();
1352 }
1353
1354 bool isEndOfDocument(const VisiblePosition &p)
1355 {
1356     return p.isNotNull() && p.next(CanCrossEditingBoundary).isNull();
1357 }
1358
1359 // ---------
1360
1361 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1362 {
1363     ContainerNode* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1364     if (!highestRoot)
1365         return VisiblePosition();
1366
1367     return VisiblePosition(firstPositionInNode(highestRoot));
1368 }
1369
1370 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1371 {
1372     ContainerNode* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1373     if (!highestRoot)
1374         return VisiblePosition();
1375
1376     return VisiblePosition(lastPositionInNode(highestRoot));
1377 }
1378
1379 bool isEndOfEditableOrNonEditableContent(const VisiblePosition &p)
1380 {
1381     return p.isNotNull() && p.next().isNull();
1382 }
1383
1384 VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1385 {
1386     return direction == LTR ? logicalStartOfLine(c) : logicalEndOfLine(c);
1387 }
1388
1389 VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1390 {
1391     return direction == LTR ? logicalEndOfLine(c) : logicalStartOfLine(c);
1392 }
1393
1394 LayoutRect localCaretRectOfPosition(const PositionWithAffinity& position, RenderObject*& renderer)
1395 {
1396     if (position.position().isNull()) {
1397         renderer = nullptr;
1398         return IntRect();
1399     }
1400     Node* node = position.position().anchorNode();
1401
1402     renderer = node->renderer();
1403     if (!renderer)
1404         return LayoutRect();
1405
1406     InlineBox* inlineBox;
1407     int caretOffset;
1408     position.position().getInlineBoxAndOffset(position.affinity(), inlineBox, caretOffset);
1409
1410     if (inlineBox)
1411         renderer = &inlineBox->renderer();
1412
1413     return renderer->localCaretRect(inlineBox, caretOffset);
1414 }
1415
1416 }