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