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