Source/WebCore/editing/visible_units.cpp

   1 /*
   2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "visible_units.h"
  28
  29 #include "Document.h"
  30 #include "Element.h"
  31 #include "HTMLNames.h"
  32 #include "Position.h"
  33 #include "RenderBlock.h"
  34 #include "RenderLayer.h"
  35 #include "RenderObject.h"
  36 #include "TextBoundaries.h"
  37 #include "TextBreakIterator.h"
  38 #include "TextIterator.h"
  39 #include "VisiblePosition.h"
  40 #include "htmlediting.h"
  41 #include <wtf/unicode/Unicode.h>
  42
  43 namespace WebCore {
  44
  45 using namespace HTMLNames;
  46 using namespace WTF::Unicode;
  47
  48 enum BoundarySearchContextAvailability { DontHaveMoreContext, MayHaveMoreContext };
  49
  50 typedef unsigned (*BoundarySearchFunction)(const UChar*, unsigned length, unsigned offset, BoundarySearchContextAvailability, bool& needMoreContext);
  51
  52 static VisiblePosition previousBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
  53 {
  54     Position pos = c.deepEquivalent();
  55     Node* boundary = pos.parentEditingBoundary();
  56     if (!boundary)
  57         return VisiblePosition();
  58
  59     Document* d = boundary->document();
  60     Position start = Position(boundary, 0).parentAnchoredEquivalent();
  61     Position end = pos.parentAnchoredEquivalent();
  62     RefPtr<Range> searchRange = Range::create(d);
  63
  64     Vector<UChar, 1024> string;
  65     unsigned suffixLength = 0;
  66
  67     ExceptionCode ec = 0;
  68     if (requiresContextForWordBoundary(c.characterBefore())) {
  69         RefPtr<Range> forwardsScanRange(d->createRange());
  70         forwardsScanRange->setEndAfter(boundary, ec);
  71         forwardsScanRange->setStart(end.deprecatedNode(), end.deprecatedEditingOffset(), ec);
  72         TextIterator forwardsIterator(forwardsScanRange.get());
  73         while (!forwardsIterator.atEnd()) {
  74             const UChar* characters = forwardsIterator.characters();
  75             int length = forwardsIterator.length();
  76             int i = endOfFirstWordBoundaryContext(characters, length);
  77             string.append(characters, i);
  78             suffixLength += i;
  79             if (i < length)
  80                 break;
  81             forwardsIterator.advance();
  82         }
  83     }
  84
  85     searchRange->setStart(start.deprecatedNode(), start.deprecatedEditingOffset(), ec);
  86     searchRange->setEnd(end.deprecatedNode(), end.deprecatedEditingOffset(), ec);
  87
  88     ASSERT(!ec);
  89     if (ec)
  90         return VisiblePosition();
  91
  92     SimplifiedBackwardsTextIterator it(searchRange.get());
  93     unsigned next = 0;
  94     bool inTextSecurityMode = start.deprecatedNode() && start.deprecatedNode()->renderer() && start.deprecatedNode()->renderer()->style()->textSecurity() != TSNONE;
  95     bool needMoreContext = false;
  96     while (!it.atEnd()) {
  97         // iterate to get chunks until the searchFunction returns a non-zero value.
  98         if (!inTextSecurityMode)
  99             string.prepend(it.characters(), it.length());
 100         else {
 101             // Treat bullets used in the text security mode as regular characters when looking for boundaries
 102             String iteratorString(it.characters(), it.length());
 103             iteratorString = iteratorString.impl()->secure('x');
 104             string.prepend(iteratorString.characters(), iteratorString.length());
 105         }
 106         next = searchFunction(string.data(), string.size(), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
 107         if (next != 0)
 108             break;
 109         it.advance();
 110     }
 111     if (needMoreContext) {
 112         // The last search returned the beginning of the buffer and asked for more context,
 113         // but there is no earlier text. Force a search with what's available.
 114         next = searchFunction(string.data(), string.size(), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);
 115         ASSERT(!needMoreContext);
 116     }
 117
 118     if (!next)
 119         return VisiblePosition(it.atEnd() ? it.range()->startPosition() : pos, DOWNSTREAM);
 120
 121     Node* node = it.range()->startContainer(ec);
 122     if ((node->isTextNode() && static_cast<int>(next) <= node->maxCharacterOffset()) || (node->renderer() && node->renderer()->isBR() && !next))
 123         // The next variable contains a usable index into a text node
 124         return VisiblePosition(Position(node, next), DOWNSTREAM);
 125
 126     // Use the character iterator to translate the next value into a DOM position.
 127     BackwardsCharacterIterator charIt(searchRange.get());
 128     charIt.advance(string.size() - suffixLength - next);
 129     // FIXME: charIt can get out of shadow host.
 130     return VisiblePosition(charIt.range()->endPosition(), DOWNSTREAM);
 131 }
 132
 133 static VisiblePosition nextBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
 134 {
 135     Position pos = c.deepEquivalent();
 136     Node* boundary = pos.parentEditingBoundary();
 137     if (!boundary)
 138         return VisiblePosition();
 139
 140     Document* d = boundary->document();
 141     RefPtr<Range> searchRange(d->createRange());
 142     Position start(pos.parentAnchoredEquivalent());
 143
 144     Vector<UChar, 1024> string;
 145     unsigned prefixLength = 0;
 146
 147     ExceptionCode ec = 0;
 148     if (requiresContextForWordBoundary(c.characterAfter())) {
 149         RefPtr<Range> backwardsScanRange(d->createRange());
 150         backwardsScanRange->setEnd(start.deprecatedNode(), start.deprecatedEditingOffset(), ec);
 151         SimplifiedBackwardsTextIterator backwardsIterator(backwardsScanRange.get());
 152         while (!backwardsIterator.atEnd()) {
 153             const UChar* characters = backwardsIterator.characters();
 154             int length = backwardsIterator.length();
 155             int i = startOfLastWordBoundaryContext(characters, length);
 156             string.prepend(characters + i, length - i);
 157             prefixLength += length - i;
 158             if (i > 0)
 159                 break;
 160             backwardsIterator.advance();
 161         }
 162     }
 163
 164     searchRange->selectNodeContents(boundary, ec);
 165     searchRange->setStart(start.deprecatedNode(), start.deprecatedEditingOffset(), ec);
 166     TextIterator it(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
 167     unsigned next = 0;
 168     bool inTextSecurityMode = start.deprecatedNode() && start.deprecatedNode()->renderer() && start.deprecatedNode()->renderer()->style()->textSecurity() != TSNONE;
 169     bool needMoreContext = false;
 170     while (!it.atEnd()) {
 171         // Keep asking the iterator for chunks until the search function
 172         // returns an end value not equal to the length of the string passed to it.
 173         if (!inTextSecurityMode)
 174             string.append(it.characters(), it.length());
 175         else {
 176             // Treat bullets used in the text security mode as regular characters when looking for boundaries
 177             String iteratorString(it.characters(), it.length());
 178             iteratorString = iteratorString.impl()->secure('x');
 179             string.append(iteratorString.characters(), iteratorString.length());
 180         }
 181         next = searchFunction(string.data(), string.size(), prefixLength, MayHaveMoreContext, needMoreContext);
 182         if (next != string.size())
 183             break;
 184         it.advance();
 185     }
 186     if (needMoreContext) {
 187         // The last search returned the end of the buffer and asked for more context,
 188         // but there is no further text. Force a search with what's available.
 189         next = searchFunction(string.data(), string.size(), prefixLength, DontHaveMoreContext, needMoreContext);
 190         ASSERT(!needMoreContext);
 191     }
 192
 193     if (it.atEnd() && next == string.size()) {
 194         pos = it.range()->startPosition();
 195     } else if (next != prefixLength) {
 196         // Use the character iterator to translate the next value into a DOM position.
 197         CharacterIterator charIt(searchRange.get(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
 198         charIt.advance(next - prefixLength - 1);
 199         RefPtr<Range> characterRange = charIt.range();
 200         pos = characterRange->endPosition();
 201
 202         if (*charIt.characters() == '\n') {
 203             // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)
 204             VisiblePosition visPos = VisiblePosition(pos);
 205             if (visPos == VisiblePosition(characterRange->startPosition())) {
 206                 charIt.advance(1);
 207                 pos = charIt.range()->startPosition();
 208             }
 209         }
 210     }
 211
 212     // generate VisiblePosition, use UPSTREAM affinity if possible
 213     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
 214 }
 215
 216 static bool canHaveCursor(RenderObject* o)
 217 {
 218     return (o->isText() && toRenderText(o)->linesBoundingBox().height())
 219         || (o->isBox() && toRenderBox(o)->borderBoundingBox().height());
 220 }
 221
 222 // ---------
 223
 224 static unsigned startWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 225 {
 226     ASSERT(offset);
 227     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
 228         needMoreContext = true;
 229         return 0;
 230     }
 231     needMoreContext = false;
 232     int start, end;
 233     findWordBoundary(characters, length, offset - 1, &start, &end);
 234     return start;
 235 }
 236
 237 VisiblePosition startOfWord(const VisiblePosition &c, EWordSide side)
 238 {
 239     // FIXME: This returns a null VP for c at the start of the document
 240     // and side == LeftWordIfOnBoundary
 241     VisiblePosition p = c;
 242     if (side == RightWordIfOnBoundary) {
 243         // at paragraph end, the startofWord is the current position
 244         if (isEndOfParagraph(c))
 245             return c;
 246
 247         p = c.next();
 248         if (p.isNull())
 249             return c;
 250     }
 251     return previousBoundary(p, startWordBoundary);
 252 }
 253
 254 static unsigned endWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 255 {
 256     ASSERT(offset <= length);
 257     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
 258         needMoreContext = true;
 259         return length;
 260     }
 261     needMoreContext = false;
 262     int start, end;
 263     findWordBoundary(characters, length, offset, &start, &end);
 264     return end;
 265 }
 266
 267 VisiblePosition endOfWord(const VisiblePosition &c, EWordSide side)
 268 {
 269     VisiblePosition p = c;
 270     if (side == LeftWordIfOnBoundary) {
 271         if (isStartOfParagraph(c))
 272             return c;
 273
 274         p = c.previous();
 275         if (p.isNull())
 276             return c;
 277     } else if (isEndOfParagraph(c))
 278         return c;
 279
 280     return nextBoundary(p, endWordBoundary);
 281 }
 282
 283 static unsigned previousWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 284 {
 285     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
 286         needMoreContext = true;
 287         return 0;
 288     }
 289     needMoreContext = false;
 290     return findNextWordFromIndex(characters, length, offset, false);
 291 }
 292
 293 VisiblePosition previousWordPosition(const VisiblePosition &c)
 294 {
 295     VisiblePosition prev = previousBoundary(c, previousWordPositionBoundary);
 296     return c.honorEditableBoundaryAtOrBefore(prev);
 297 }
 298
 299 static unsigned nextWordPositionBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 300 {
 301     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
 302         needMoreContext = true;
 303         return length;
 304     }
 305     needMoreContext = false;
 306     return findNextWordFromIndex(characters, length, offset, true);
 307 }
 308
 309 VisiblePosition nextWordPosition(const VisiblePosition &c)
 310 {
 311     VisiblePosition next = nextBoundary(c, nextWordPositionBoundary);
 312     return c.honorEditableBoundaryAtOrAfter(next);
 313 }
 314
 315 // ---------
 316
 317 static RootInlineBox *rootBoxForLine(const VisiblePosition &c)
 318 {
 319     Position p = c.deepEquivalent();
 320     Node* node = p.deprecatedNode();
 321     if (!node)
 322         return 0;
 323
 324     RenderObject *renderer = node->renderer();
 325     if (!renderer)
 326         return 0;
 327
 328     InlineBox* box;
 329     int offset;
 330     c.getInlineBoxAndOffset(box, offset);
 331
 332     return box ? box->root() : 0;
 333 }
 334
 335 static VisiblePosition positionAvoidingFirstPositionInTable(const VisiblePosition& c)
 336 {
 337     // return table offset 0 instead of the first VisiblePosition inside the table
 338     VisiblePosition previous = c.previous();
 339     if (isLastPositionBeforeTable(previous) && isEditablePosition(previous.deepEquivalent()))
 340         return previous;
 341
 342     return c;
 343 }
 344
 345 static VisiblePosition startPositionForLine(const VisiblePosition& c)
 346 {
 347     if (c.isNull())
 348         return VisiblePosition();
 349
 350     RootInlineBox *rootBox = rootBoxForLine(c);
 351     if (!rootBox) {
 352         // There are VisiblePositions at offset 0 in blocks without
 353         // RootInlineBoxes, like empty editable blocks and bordered blocks.
 354         Position p = c.deepEquivalent();
 355         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
 356             return positionAvoidingFirstPositionInTable(c);
 357
 358         return VisiblePosition();
 359     }
 360
 361     // Generated content (e.g. list markers and CSS :before and :after
 362     // pseudoelements) have no corresponding DOM element, and so cannot be
 363     // represented by a VisiblePosition.  Use whatever follows instead.
 364     InlineBox *startBox = rootBox->firstLeafChild();
 365     Node *startNode;
 366     while (1) {
 367         if (!startBox)
 368             return VisiblePosition();
 369
 370         RenderObject *startRenderer = startBox->renderer();
 371         if (!startRenderer)
 372             return VisiblePosition();
 373
 374         startNode = startRenderer->node();
 375         if (startNode)
 376             break;
 377
 378         startBox = startBox->nextLeafChild();
 379     }
 380
 381     VisiblePosition visPos = startNode->isTextNode() ? VisiblePosition(Position(startNode, static_cast<InlineTextBox *>(startBox)->start(), Position::PositionIsOffsetInAnchor), DOWNSTREAM)
 382                                                      : VisiblePosition(positionBeforeNode(startNode), DOWNSTREAM);
 383     return positionAvoidingFirstPositionInTable(visPos);
 384 }
 385
 386 VisiblePosition startOfLine(const VisiblePosition& c)
 387 {
 388     VisiblePosition visPos = startPositionForLine(c);
 389
 390     return c.honorEditableBoundaryAtOrBefore(visPos);
 391 }
 392
 393 static VisiblePosition endPositionForLine(const VisiblePosition& c)
 394 {
 395     if (c.isNull())
 396         return VisiblePosition();
 397
 398     RootInlineBox *rootBox = rootBoxForLine(c);
 399     if (!rootBox) {
 400         // There are VisiblePositions at offset 0 in blocks without
 401         // RootInlineBoxes, like empty editable blocks and bordered blocks.
 402         Position p = c.deepEquivalent();
 403         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
 404             return c;
 405         return VisiblePosition();
 406     }
 407
 408     // Generated content (e.g. list markers and CSS :before and :after
 409     // pseudoelements) have no corresponding DOM element, and so cannot be
 410     // represented by a VisiblePosition.  Use whatever precedes instead.
 411     Node *endNode;
 412     InlineBox *endBox = rootBox->lastLeafChild();
 413     while (1) {
 414         if (!endBox)
 415             return VisiblePosition();
 416
 417         RenderObject *endRenderer = endBox->renderer();
 418         if (!endRenderer)
 419             return VisiblePosition();
 420
 421         endNode = endRenderer->node();
 422         if (endNode)
 423             break;
 424
 425         endBox = endBox->prevLeafChild();
 426     }
 427
 428     Position pos;
 429     if (endNode->hasTagName(brTag)) {
 430         pos = positionBeforeNode(endNode);
 431     } else if (endBox->isInlineTextBox()) {
 432         InlineTextBox *endTextBox = static_cast<InlineTextBox *>(endBox);
 433         int endOffset = endTextBox->start();
 434         if (!endTextBox->isLineBreak())
 435             endOffset += endTextBox->len();
 436         pos = Position(endNode, endOffset, Position::PositionIsOffsetInAnchor);
 437     } else
 438         pos = positionAfterNode(endNode);
 439
 440     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
 441 }
 442
 443 VisiblePosition endOfLine(const VisiblePosition& c)
 444 {
 445     VisiblePosition visPos = endPositionForLine(c);
 446
 447     // Make sure the end of line is at the same line as the given input position.  Else use the previous position to
 448     // obtain end of line.  This condition happens when the input position is before the space character at the end
 449     // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position
 450     // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style
 451     // versus lines without that style, which would break before a space by default.
 452     if (!inSameLine(c, visPos)) {
 453         visPos = c.previous();
 454         if (visPos.isNull())
 455             return VisiblePosition();
 456         visPos = endPositionForLine(visPos);
 457     }
 458
 459     return c.honorEditableBoundaryAtOrAfter(visPos);
 460 }
 461
 462 bool inSameLine(const VisiblePosition &a, const VisiblePosition &b)
 463 {
 464     return a.isNotNull() && startOfLine(a) == startOfLine(b);
 465 }
 466
 467 bool isStartOfLine(const VisiblePosition &p)
 468 {
 469     return p.isNotNull() && p == startOfLine(p);
 470 }
 471
 472 bool isEndOfLine(const VisiblePosition &p)
 473 {
 474     return p.isNotNull() && p == endOfLine(p);
 475 }
 476
 477 // The first leaf before node that has the same editability as node.
 478 static Node* previousLeafWithSameEditability(Node* node)
 479 {
 480     bool editable = node->rendererIsEditable();
 481     Node* n = node->previousLeafNode();
 482     while (n) {
 483         if (editable == n->rendererIsEditable())
 484             return n;
 485         n = n->previousLeafNode();
 486     }
 487     return 0;
 488 }
 489
 490 static Node* enclosingNodeWithNonInlineRenderer(Node* n)
 491 {
 492     for (Node* p = n; p; p = p->parentNode()) {
 493         if (p->renderer() && !p->renderer()->isInline())
 494             return p;
 495     }
 496     return 0;
 497 }
 498
 499 VisiblePosition previousLinePosition(const VisiblePosition &visiblePosition, int x)
 500 {
 501     Position p = visiblePosition.deepEquivalent();
 502     Node* node = p.deprecatedNode();
 503     Node* highestRoot = highestEditableRoot(p);
 504     if (!node)
 505         return VisiblePosition();
 506
 507     node->document()->updateLayoutIgnorePendingStylesheets();
 508
 509     RenderObject *renderer = node->renderer();
 510     if (!renderer)
 511         return VisiblePosition();
 512
 513     RenderBlock *containingBlock = 0;
 514     RootInlineBox *root = 0;
 515     InlineBox* box;
 516     int ignoredCaretOffset;
 517     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
 518     if (box) {
 519         root = box->root()->prevRootBox();
 520         // We want to skip zero height boxes.
 521         // This could happen in case it is a TrailingFloatsRootInlineBox.
 522         if (root && root->logicalHeight())
 523             containingBlock = renderer->containingBlock();
 524         else
 525             root = 0;
 526     }
 527
 528     if (!root) {
 529         // This containing editable block does not have a previous line.
 530         // Need to move back to previous containing editable block in this root editable
 531         // block and find the last root line box in that block.
 532         Node* startBlock = enclosingNodeWithNonInlineRenderer(node);
 533         Node* n = previousLeafWithSameEditability(node);
 534         while (n && startBlock == enclosingNodeWithNonInlineRenderer(n))
 535             n = previousLeafWithSameEditability(n);
 536         while (n) {
 537             if (highestEditableRoot(firstPositionInOrBeforeNode(n)) != highestRoot)
 538                 break;
 539             Position pos(n, caretMinOffset(n));
 540             if (pos.isCandidate()) {
 541                 RenderObject* o = n->renderer();
 542                 ASSERT(o);
 543                 if (canHaveCursor(o)) {
 544                     Position maxPos(n, caretMaxOffset(n));
 545                     maxPos.getInlineBoxAndOffset(DOWNSTREAM, box, ignoredCaretOffset);
 546                     if (box) {
 547                         // previous root line box found
 548                         root = box->root();
 549                         containingBlock = n->renderer()->containingBlock();
 550                         break;
 551                     }
 552
 553                     return VisiblePosition(pos, DOWNSTREAM);
 554                 }
 555             }
 556             n = previousLeafWithSameEditability(n);
 557         }
 558     }
 559
 560     if (root) {
 561         // FIXME: Can be wrong for multi-column layout and with transforms.
 562         FloatPoint absPos = containingBlock->localToAbsolute(FloatPoint());
 563         if (containingBlock->hasOverflowClip())
 564             absPos -= containingBlock->layer()->scrolledContentOffset();
 565         RenderObject* renderer = root->closestLeafChildForLogicalLeftPosition(x - absPos.x(), isEditablePosition(p))->renderer();
 566         Node* node = renderer->node();
 567         if (node && editingIgnoresContent(node))
 568             return positionInParentBeforeNode(node);
 569         return renderer->positionForPoint(IntPoint(x - absPos.x(), root->lineTop()));
 570     }
 571
 572     // Could not find a previous line. This means we must already be on the first line.
 573     // Move to the start of the content in this block, which effectively moves us
 574     // to the start of the line we're on.
 575     Element* rootElement = node->rendererIsEditable() ? node->rootEditableElement() : node->document()->documentElement();
 576     if (!rootElement)
 577         return VisiblePosition();
 578     return VisiblePosition(firstPositionInNode(rootElement), DOWNSTREAM);
 579 }
 580
 581 static Node* nextLeafWithSameEditability(Node* node, int offset)
 582 {
 583     bool editable = node->rendererIsEditable();
 584     ASSERT(offset >= 0);
 585     Node* child = node->childNode(offset);
 586     Node* n = child ? child->nextLeafNode() : node->lastDescendant()->nextLeafNode();
 587     while (n) {
 588         if (editable == n->rendererIsEditable())
 589             return n;
 590         n = n->nextLeafNode();
 591     }
 592     return 0;
 593 }
 594
 595 static Node* nextLeafWithSameEditability(Node* node)
 596 {
 597     if (!node)
 598         return 0;
 599
 600     bool editable = node->rendererIsEditable();
 601     Node* n = node->nextLeafNode();
 602     while (n) {
 603         if (editable == n->rendererIsEditable())
 604             return n;
 605         n = n->nextLeafNode();
 606     }
 607     return 0;
 608 }
 609
 610 VisiblePosition nextLinePosition(const VisiblePosition &visiblePosition, int x)
 611 {
 612     Position p = visiblePosition.deepEquivalent();
 613     Node* node = p.deprecatedNode();
 614     Node* highestRoot = highestEditableRoot(p);
 615     if (!node)
 616         return VisiblePosition();
 617
 618     node->document()->updateLayoutIgnorePendingStylesheets();
 619
 620     RenderObject *renderer = node->renderer();
 621     if (!renderer)
 622         return VisiblePosition();
 623
 624     RenderBlock *containingBlock = 0;
 625     RootInlineBox *root = 0;
 626     InlineBox* box;
 627     int ignoredCaretOffset;
 628     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
 629     if (box) {
 630         root = box->root()->nextRootBox();
 631         // We want to skip zero height boxes.
 632         // This could happen in case it is a TrailingFloatsRootInlineBox.
 633         if (root && root->logicalHeight())
 634             containingBlock = renderer->containingBlock();
 635         else
 636             root = 0;
 637     }
 638
 639     if (!root) {
 640         // This containing editable block does not have a next line.
 641         // Need to move forward to next containing editable block in this root editable
 642         // block and find the first root line box in that block.
 643         Node* startBlock = enclosingNodeWithNonInlineRenderer(node);
 644         Node* n = nextLeafWithSameEditability(node, p.deprecatedEditingOffset());
 645         while (n && startBlock == enclosingNodeWithNonInlineRenderer(n))
 646             n = nextLeafWithSameEditability(n);
 647         while (n) {
 648             if (highestEditableRoot(firstPositionInOrBeforeNode(n)) != highestRoot)
 649                 break;
 650             Position pos(n, caretMinOffset(n));
 651             if (pos.isCandidate()) {
 652                 ASSERT(n->renderer());
 653                 pos.getInlineBoxAndOffset(DOWNSTREAM, box, ignoredCaretOffset);
 654                 if (box) {
 655                     // next root line box found
 656                     root = box->root();
 657                     containingBlock = n->renderer()->containingBlock();
 658                     break;
 659                 }
 660
 661                 return VisiblePosition(pos, DOWNSTREAM);
 662             }
 663             n = nextLeafWithSameEditability(n);
 664         }
 665     }
 666
 667     if (root) {
 668         // FIXME: Can be wrong for multi-column layout and with transforms.
 669         FloatPoint absPos = containingBlock->localToAbsolute(FloatPoint());
 670         if (containingBlock->hasOverflowClip())
 671             absPos -= containingBlock->layer()->scrolledContentOffset();
 672         RenderObject* renderer = root->closestLeafChildForLogicalLeftPosition(x - absPos.x(), isEditablePosition(p))->renderer();
 673         Node* node = renderer->node();
 674         if (node && editingIgnoresContent(node))
 675             return positionInParentBeforeNode(node);
 676         return renderer->positionForPoint(IntPoint(x - absPos.x(), root->lineTop()));
 677     }
 678
 679     // Could not find a next line. This means we must already be on the last line.
 680     // Move to the end of the content in this block, which effectively moves us
 681     // to the end of the line we're on.
 682     Element* rootElement = node->rendererIsEditable() ? node->rootEditableElement() : node->document()->documentElement();
 683     if (!rootElement)
 684         return VisiblePosition();
 685     return VisiblePosition(lastPositionInNode(rootElement), DOWNSTREAM);
 686 }
 687
 688 // ---------
 689
 690 static unsigned startSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
 691 {
 692     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
 693     // FIXME: The following function can return -1; we don't handle that.
 694     return textBreakPreceding(iterator, length);
 695 }
 696
 697 VisiblePosition startOfSentence(const VisiblePosition &c)
 698 {
 699     return previousBoundary(c, startSentenceBoundary);
 700 }
 701
 702 static unsigned endSentenceBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
 703 {
 704     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
 705     return textBreakNext(iterator);
 706 }
 707
 708 // FIXME: This includes the space after the punctuation that marks the end of the sentence.
 709 VisiblePosition endOfSentence(const VisiblePosition &c)
 710 {
 711     return nextBoundary(c, endSentenceBoundary);
 712 }
 713
 714 static unsigned previousSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
 715 {
 716     // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
 717     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
 718     // FIXME: The following function can return -1; we don't handle that.
 719     return textBreakPreceding(iterator, length);
 720 }
 721
 722 VisiblePosition previousSentencePosition(const VisiblePosition &c)
 723 {
 724     VisiblePosition prev = previousBoundary(c, previousSentencePositionBoundary);
 725     return c.honorEditableBoundaryAtOrBefore(prev);
 726 }
 727
 728 static unsigned nextSentencePositionBoundary(const UChar* characters, unsigned length, unsigned, BoundarySearchContextAvailability, bool&)
 729 {
 730     // FIXME: This is identical to endSentenceBoundary.  This isn't right, it needs to
 731     // move to the equivlant position in the following sentence.
 732     TextBreakIterator* iterator = sentenceBreakIterator(characters, length);
 733     return textBreakFollowing(iterator, 0);
 734 }
 735
 736 VisiblePosition nextSentencePosition(const VisiblePosition &c)
 737 {
 738     VisiblePosition next = nextBoundary(c, nextSentencePositionBoundary);
 739     return c.honorEditableBoundaryAtOrAfter(next);
 740 }
 741
 742 VisiblePosition startOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
 743 {
 744     Position p = c.deepEquivalent();
 745     Node* startNode = p.deprecatedNode();
 746
 747     if (!startNode)
 748         return VisiblePosition();
 749
 750     if (isRenderedAsNonInlineTableImageOrHR(startNode))
 751         return positionBeforeNode(startNode);
 752
 753     Node* startBlock = enclosingBlock(startNode);
 754
 755     Node* node = startNode;
 756     Node* highestRoot = highestEditableRoot(p);
 757     int offset = p.deprecatedEditingOffset();
 758     Position::AnchorType type = p.anchorType();
 759
 760     Node* n = startNode;
 761     while (n) {
 762         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->rendererIsEditable() != startNode->rendererIsEditable())
 763             break;
 764         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
 765             while (n && n->rendererIsEditable() != startNode->rendererIsEditable())
 766                 n = n->traversePreviousNodePostOrder(startBlock);
 767             if (!n || !n->isDescendantOf(highestRoot))
 768                 break;
 769         }
 770         RenderObject *r = n->renderer();
 771         if (!r) {
 772             n = n->traversePreviousNodePostOrder(startBlock);
 773             continue;
 774         }
 775         RenderStyle *style = r->style();
 776         if (style->visibility() != VISIBLE) {
 777             n = n->traversePreviousNodePostOrder(startBlock);
 778             continue;
 779         }
 780
 781         if (r->isBR() || isBlock(n))
 782             break;
 783
 784         if (r->isText() && r->caretMaxRenderedOffset() > 0) {
 785             type = Position::PositionIsOffsetInAnchor;
 786             if (style->preserveNewline()) {
 787                 const UChar* chars = toRenderText(r)->characters();
 788                 int i = toRenderText(r)->textLength();
 789                 int o = offset;
 790                 if (n == startNode && o < i)
 791                     i = max(0, o);
 792                 while (--i >= 0)
 793                     if (chars[i] == '\n')
 794                         return VisiblePosition(Position(n, i + 1, Position::PositionIsOffsetInAnchor), DOWNSTREAM);
 795             }
 796             node = n;
 797             offset = 0;
 798             n = n->traversePreviousNodePostOrder(startBlock);
 799         } else if (editingIgnoresContent(n) || isTableElement(n)) {
 800             node = n;
 801             type = Position::PositionIsBeforeAnchor;
 802             n = n->previousSibling() ? n->previousSibling() : n->traversePreviousNodePostOrder(startBlock);
 803         } else
 804             n = n->traversePreviousNodePostOrder(startBlock);
 805     }
 806
 807     if (type == Position::PositionIsOffsetInAnchor)
 808         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
 809
 810     return VisiblePosition(Position(node, type), DOWNSTREAM);
 811 }
 812
 813 VisiblePosition endOfParagraph(const VisiblePosition &c, EditingBoundaryCrossingRule boundaryCrossingRule)
 814 {
 815     if (c.isNull())
 816         return VisiblePosition();
 817
 818     Position p = c.deepEquivalent();
 819     Node* startNode = p.deprecatedNode();
 820
 821     if (isRenderedAsNonInlineTableImageOrHR(startNode))
 822         return positionAfterNode(startNode);
 823
 824     Node* startBlock = enclosingBlock(startNode);
 825     Node* stayInsideBlock = startBlock;
 826
 827     Node* node = startNode;
 828     Node* highestRoot = highestEditableRoot(p);
 829     int offset = p.deprecatedEditingOffset();
 830     Position::AnchorType type = p.anchorType();
 831
 832     Node* n = startNode;
 833     while (n) {
 834         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->rendererIsEditable() != startNode->rendererIsEditable())
 835             break;
 836         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
 837             while (n && n->rendererIsEditable() != startNode->rendererIsEditable())
 838                 n = n->traverseNextNode(stayInsideBlock);
 839             if (!n || !n->isDescendantOf(highestRoot))
 840                 break;
 841         }
 842
 843         RenderObject *r = n->renderer();
 844         if (!r) {
 845             n = n->traverseNextNode(stayInsideBlock);
 846             continue;
 847         }
 848         RenderStyle *style = r->style();
 849         if (style->visibility() != VISIBLE) {
 850             n = n->traverseNextNode(stayInsideBlock);
 851             continue;
 852         }
 853
 854         if (r->isBR() || isBlock(n))
 855             break;
 856
 857         // FIXME: We avoid returning a position where the renderer can't accept the caret.
 858         if (r->isText() && r->caretMaxRenderedOffset() > 0) {
 859             int length = toRenderText(r)->textLength();
 860             type = Position::PositionIsOffsetInAnchor;
 861             if (style->preserveNewline()) {
 862                 const UChar* chars = toRenderText(r)->characters();
 863                 int o = n == startNode ? offset : 0;
 864                 for (int i = o; i < length; ++i)
 865                     if (chars[i] == '\n')
 866                         return VisiblePosition(Position(n, i, Position::PositionIsOffsetInAnchor), DOWNSTREAM);
 867             }
 868             node = n;
 869             offset = r->caretMaxOffset();
 870             n = n->traverseNextNode(stayInsideBlock);
 871         } else if (editingIgnoresContent(n) || isTableElement(n)) {
 872             node = n;
 873             type = Position::PositionIsAfterAnchor;
 874             n = n->traverseNextSibling(stayInsideBlock);
 875         } else
 876             n = n->traverseNextNode(stayInsideBlock);
 877     }
 878
 879     if (type == Position::PositionIsOffsetInAnchor)
 880         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
 881
 882     return VisiblePosition(Position(node, type), DOWNSTREAM);
 883 }
 884
 885 // FIXME: isStartOfParagraph(startOfNextParagraph(pos)) is not always true
 886 VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
 887 {
 888     VisiblePosition paragraphEnd(endOfParagraph(visiblePosition, CanSkipOverEditingBoundary));
 889     VisiblePosition afterParagraphEnd(paragraphEnd.next(CannotCrossEditingBoundary));
 890     // The position after the last position in the last cell of a table
 891     // is not the start of the next paragraph.
 892     if (isFirstPositionAfterTable(afterParagraphEnd))
 893         return afterParagraphEnd.next(CannotCrossEditingBoundary);
 894     return afterParagraphEnd;
 895 }
 896
 897 bool inSameParagraph(const VisiblePosition &a, const VisiblePosition &b, EditingBoundaryCrossingRule boundaryCrossingRule)
 898 {
 899     return a.isNotNull() && startOfParagraph(a, boundaryCrossingRule) == startOfParagraph(b, boundaryCrossingRule);
 900 }
 901
 902 bool isStartOfParagraph(const VisiblePosition &pos, EditingBoundaryCrossingRule boundaryCrossingRule)
 903 {
 904     return pos.isNotNull() && pos == startOfParagraph(pos, boundaryCrossingRule);
 905 }
 906
 907 bool isEndOfParagraph(const VisiblePosition &pos, EditingBoundaryCrossingRule boundaryCrossingRule)
 908 {
 909     return pos.isNotNull() && pos == endOfParagraph(pos, boundaryCrossingRule);
 910 }
 911
 912 VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
 913 {
 914     VisiblePosition pos = p;
 915     do {
 916         VisiblePosition n = previousLinePosition(pos, x);
 917         if (n.isNull() || n == pos)
 918             break;
 919         pos = n;
 920     } while (inSameParagraph(p, pos));
 921     return pos;
 922 }
 923
 924 VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
 925 {
 926     VisiblePosition pos = p;
 927     do {
 928         VisiblePosition n = nextLinePosition(pos, x);
 929         if (n.isNull() || n == pos)
 930             break;
 931         pos = n;
 932     } while (inSameParagraph(p, pos));
 933     return pos;
 934 }
 935
 936 // ---------
 937
 938 VisiblePosition startOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
 939 {
 940     Position position = visiblePosition.deepEquivalent();
 941     Node* startBlock;
 942     if (!position.containerNode() || !(startBlock = enclosingBlock(position.containerNode(), rule)))
 943         return VisiblePosition();
 944     return firstPositionInNode(startBlock);
 945 }
 946
 947 VisiblePosition endOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
 948 {
 949     Position position = visiblePosition.deepEquivalent();
 950     Node* endBlock;
 951     if (!position.containerNode() || !(endBlock = enclosingBlock(position.containerNode(), rule)))
 952         return VisiblePosition();
 953     return lastPositionInNode(endBlock);
 954 }
 955
 956 bool inSameBlock(const VisiblePosition &a, const VisiblePosition &b)
 957 {
 958     return !a.isNull() && enclosingBlock(a.deepEquivalent().containerNode()) == enclosingBlock(b.deepEquivalent().containerNode());
 959 }
 960
 961 bool isStartOfBlock(const VisiblePosition &pos)
 962 {
 963     return pos.isNotNull() && pos == startOfBlock(pos, CanCrossEditingBoundary);
 964 }
 965
 966 bool isEndOfBlock(const VisiblePosition &pos)
 967 {
 968     return pos.isNotNull() && pos == endOfBlock(pos, CanCrossEditingBoundary);
 969 }
 970
 971 // ---------
 972
 973 VisiblePosition startOfDocument(const Node* node)
 974 {
 975     if (!node)
 976         return VisiblePosition();
 977
 978     return VisiblePosition(firstPositionInNode(node->document()->documentElement()), DOWNSTREAM);
 979 }
 980
 981 VisiblePosition startOfDocument(const VisiblePosition &c)
 982 {
 983     return startOfDocument(c.deepEquivalent().deprecatedNode());
 984 }
 985
 986 VisiblePosition endOfDocument(const Node* node)
 987 {
 988     if (!node || !node->document() || !node->document()->documentElement())
 989         return VisiblePosition();
 990
 991     Element* doc = node->document()->documentElement();
 992     return VisiblePosition(lastPositionInNode(doc), DOWNSTREAM);
 993 }
 994
 995 VisiblePosition endOfDocument(const VisiblePosition &c)
 996 {
 997     return endOfDocument(c.deepEquivalent().deprecatedNode());
 998 }
 999
1000 bool inSameDocument(const VisiblePosition &a, const VisiblePosition &b)
1001 {
1002     Position ap = a.deepEquivalent();
1003     Node* an = ap.deprecatedNode();
1004     if (!an)
1005         return false;
1006     Position bp = b.deepEquivalent();
1007     Node* bn = bp.deprecatedNode();
1008     if (an == bn)
1009         return true;
1010
1011     return an->document() == bn->document();
1012 }
1013
1014 bool isStartOfDocument(const VisiblePosition &p)
1015 {
1016     return p.isNotNull() && p.previous().isNull();
1017 }
1018
1019 bool isEndOfDocument(const VisiblePosition &p)
1020 {
1021     return p.isNotNull() && p.next().isNull();
1022 }
1023
1024 // ---------
1025
1026 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1027 {
1028     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1029     if (!highestRoot)
1030         return VisiblePosition();
1031
1032     return firstPositionInNode(highestRoot);
1033 }
1034
1035 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1036 {
1037     Node* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1038     if (!highestRoot)
1039         return VisiblePosition();
1040
1041     return lastPositionInNode(highestRoot);
1042 }
1043
1044 static VisiblePosition logicalStartPositionForLine(const VisiblePosition& c)
1045 {
1046     if (c.isNull())
1047         return VisiblePosition();
1048
1049     RootInlineBox* rootBox = rootBoxForLine(c);
1050     if (!rootBox) {
1051         // There are VisiblePositions at offset 0 in blocks without
1052         // RootInlineBoxes, like empty editable blocks and bordered blocks.
1053         Position p = c.deepEquivalent();
1054         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
1055             return positionAvoidingFirstPositionInTable(c);
1056
1057         return VisiblePosition();
1058     }
1059
1060     InlineBox* logicalStartBox;
1061     Node* logicalStartNode = rootBox->getLogicalStartBoxWithNode(logicalStartBox);
1062
1063     if (!logicalStartNode)
1064         return VisiblePosition();
1065
1066     VisiblePosition visPos = logicalStartNode->isTextNode() ? VisiblePosition(Position(logicalStartNode, logicalStartBox->caretMinOffset(), Position::PositionIsOffsetInAnchor), DOWNSTREAM)
1067                                                             : VisiblePosition(positionBeforeNode(logicalStartNode), DOWNSTREAM);
1068     return positionAvoidingFirstPositionInTable(visPos);
1069 }
1070
1071 VisiblePosition logicalStartOfLine(const VisiblePosition& c)
1072 {
1073     // TODO: this is the current behavior that might need to be fixed.
1074     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
1075     VisiblePosition visPos = logicalStartPositionForLine(c);
1076
1077     return c.honorEditableBoundaryAtOrBefore(visPos);
1078 }
1079
1080 static VisiblePosition logicalEndPositionForLine(const VisiblePosition& c)
1081 {
1082     if (c.isNull())
1083         return VisiblePosition();
1084
1085     RootInlineBox* rootBox = rootBoxForLine(c);
1086     if (!rootBox) {
1087         // There are VisiblePositions at offset 0 in blocks without
1088         // RootInlineBoxes, like empty editable blocks and bordered blocks.
1089         Position p = c.deepEquivalent();
1090         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
1091             return c;
1092         return VisiblePosition();
1093     }
1094
1095     InlineBox* logicalEndBox;
1096     Node* logicalEndNode = rootBox->getLogicalEndBoxWithNode(logicalEndBox);
1097
1098     if (!logicalEndNode)
1099         return VisiblePosition();
1100
1101     Position pos;
1102     if (logicalEndNode->hasTagName(brTag))
1103         pos = positionBeforeNode(logicalEndNode);
1104     else if (logicalEndBox->isInlineTextBox()) {
1105         InlineTextBox* endTextBox = static_cast<InlineTextBox*>(logicalEndBox);
1106         int endOffset = endTextBox->start();
1107         if (!endTextBox->isLineBreak())
1108             endOffset += endTextBox->len();
1109         pos = Position(logicalEndNode, endOffset, Position::PositionIsOffsetInAnchor);
1110     } else
1111         pos = positionAfterNode(logicalEndNode);
1112
1113     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
1114 }
1115
1116 bool inSameLogicalLine(const VisiblePosition& a, const VisiblePosition& b)
1117 {
1118     return a.isNotNull() && logicalStartOfLine(a) == logicalStartOfLine(b);
1119 }
1120
1121 VisiblePosition logicalEndOfLine(const VisiblePosition& c)
1122 {
1123     // TODO: this is the current behavior that might need to be fixed.
1124     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
1125
1126     VisiblePosition visPos = logicalEndPositionForLine(c);
1127
1128     // Make sure the end of line is at the same line as the given input position. For a wrapping line, the logical end
1129     // position for the not-last-2-lines might incorrectly hand back the logical beginning of the next line.
1130     // For example, <div contenteditable dir="rtl" style="line-break:before-white-space">abcdefg abcdefg abcdefg
1131     // a abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg </div>
1132     // In this case, use the previous position of the computed logical end position.
1133     if (!inSameLogicalLine(c, visPos))
1134         visPos = visPos.previous();
1135
1136     return c.honorEditableBoundaryAtOrAfter(visPos);
1137 }
1138
1139 VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1140 {
1141     return direction == LTR ? logicalStartOfLine(c) : logicalEndOfLine(c);
1142 }
1143
1144 VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction)
1145 {
1146     return direction == LTR ? logicalEndOfLine(c) : logicalStartOfLine(c);
1147 }
1148
1149 }