WebCore/dom/Position.cpp

   1 /*
   2  * Copyright (C) 2004, 2005, 2006 Apple Computer, 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 "Position.h"
  28
  29 #include "CSSComputedStyleDeclaration.h"
  30 #include "CString.h"
  31 #include "CharacterNames.h"
  32 #include "Document.h"
  33 #include "Element.h"
  34 #include "HTMLNames.h"
  35 #include "Logging.h"
  36 #include "PositionIterator.h"
  37 #include "Text.h"
  38 #include "TextIterator.h"
  39 #include "htmlediting.h"
  40 #include "visible_units.h"
  41 #include <stdio.h>
  42
  43 namespace WebCore {
  44
  45 using namespace HTMLNames;
  46
  47 static Node *nextRenderedEditable(Node *node)
  48 {
  49     while (1) {
  50         node = node->nextEditable();
  51         if (!node)
  52             return 0;
  53         RenderObject* renderer = node->renderer();
  54         if (!renderer)
  55             continue;
  56         if (renderer->inlineBoxWrapper() || renderer->isText() && static_cast<RenderText*>(renderer)->firstTextBox())
  57             return node;
  58     }
  59     return 0;
  60 }
  61
  62 static Node *previousRenderedEditable(Node *node)
  63 {
  64     while (1) {
  65         node = node->previousEditable();
  66         if (!node)
  67             return 0;
  68         RenderObject* renderer = node->renderer();
  69         if (!renderer)
  70             continue;
  71         if (renderer->inlineBoxWrapper() || renderer->isText() && static_cast<RenderText*>(renderer)->firstTextBox())
  72             return node;
  73     }
  74     return 0;
  75 }
  76
  77 Element* Position::documentElement() const
  78 {
  79     if (Node* n = node())
  80         if (Element* e = n->document()->documentElement())
  81             return e;
  82     return 0;
  83 }
  84
  85 Element *Position::element() const
  86 {
  87     Node *n;
  88     for (n = node(); n && !n->isElementNode(); n = n->parentNode())
  89         ; // empty loop body
  90     return static_cast<Element *>(n);
  91 }
  92
  93 PassRefPtr<CSSComputedStyleDeclaration> Position::computedStyle() const
  94 {
  95     Element* elem = element();
  96     if (!elem)
  97         return 0;
  98     return WebCore::computedStyle(elem);
  99 }
 100
 101 Position Position::previous(EUsingComposedCharacters usingComposedCharacters) const
 102 {
 103     Node *n = node();
 104     if (!n)
 105         return *this;
 106
 107     int o = offset();
 108     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
 109     ASSERT(o >= 0);
 110
 111     if (o > 0) {
 112         Node *child = n->childNode(o - 1);
 113         if (child) {
 114             return Position(child, maxDeepOffset(child));
 115         }
 116         // There are two reasons child might be 0:
 117         //   1) The node is node like a text node that is not an element, and therefore has no children.
 118         //      Going backward one character at a time is correct.
 119         //   2) The old offset was a bogus offset like (<br>, 1), and there is no child.
 120         //      Going from 1 to 0 is correct.
 121         return Position(n, usingComposedCharacters ? uncheckedPreviousOffset(n, o) : o - 1);
 122     }
 123
 124     Node *parent = n->parentNode();
 125     if (!parent)
 126         return *this;
 127
 128     return Position(parent, n->nodeIndex());
 129 }
 130
 131 Position Position::next(EUsingComposedCharacters usingComposedCharacters) const
 132 {
 133     Node *n = node();
 134     if (!n)
 135         return *this;
 136
 137     int o = offset();
 138     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
 139     ASSERT(o >= 0);
 140
 141     Node* child = n->childNode(o);
 142     if (child || !n->hasChildNodes() && o < maxDeepOffset(n)) {
 143         if (child)
 144             return Position(child, 0);
 145
 146         // There are two reasons child might be 0:
 147         //   1) The node is node like a text node that is not an element, and therefore has no children.
 148         //      Going forward one character at a time is correct.
 149         //   2) The new offset is a bogus offset like (<br>, 1), and there is no child.
 150         //      Going from 0 to 1 is correct.
 151         return Position(n, usingComposedCharacters ? uncheckedNextOffset(n, o) : o + 1);
 152     }
 153
 154     Node *parent = n->parentNode();
 155     if (!parent)
 156         return *this;
 157
 158     return Position(parent, n->nodeIndex() + 1);
 159 }
 160
 161 int Position::uncheckedPreviousOffset(const Node* n, int current)
 162 {
 163     return n->renderer() ? n->renderer()->previousOffset(current) : current - 1;
 164 }
 165
 166 int Position::uncheckedNextOffset(const Node* n, int current)
 167 {
 168     return n->renderer() ? n->renderer()->nextOffset(current) : current + 1;
 169 }
 170
 171 bool Position::atStart() const
 172 {
 173     Node *n = node();
 174     if (!n)
 175         return true;
 176
 177     return offset() <= 0 && n->parent() == 0;
 178 }
 179
 180 bool Position::atEnd() const
 181 {
 182     Node *n = node();
 183     if (!n)
 184         return true;
 185
 186     return n->parent() == 0 && offset() >= maxDeepOffset(n);
 187 }
 188
 189 int Position::renderedOffset() const
 190 {
 191     if (!node()->isTextNode())
 192         return offset();
 193
 194     if (!node()->renderer())
 195         return offset();
 196
 197     int result = 0;
 198     RenderText *textRenderer = static_cast<RenderText *>(node()->renderer());
 199     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 200         int start = box->m_start;
 201         int end = box->m_start + box->m_len;
 202         if (offset() < start)
 203             return result;
 204         if (offset() <= end) {
 205             result += offset() - start;
 206             return result;
 207         }
 208         result += box->m_len;
 209     }
 210     return result;
 211 }
 212
 213 // return first preceding DOM position rendered at a different location, or "this"
 214 Position Position::previousCharacterPosition(EAffinity affinity) const
 215 {
 216     if (isNull())
 217         return Position();
 218
 219     Node *fromRootEditableElement = node()->rootEditableElement();
 220
 221     bool atStartOfLine = isStartOfLine(VisiblePosition(*this, affinity));
 222     bool rendered = isCandidate();
 223
 224     Position currentPos = *this;
 225     while (!currentPos.atStart()) {
 226         currentPos = currentPos.previous();
 227
 228         if (currentPos.node()->rootEditableElement() != fromRootEditableElement)
 229             return *this;
 230
 231         if (atStartOfLine || !rendered) {
 232             if (currentPos.isCandidate())
 233                 return currentPos;
 234         } else if (rendersInDifferentPosition(currentPos))
 235             return currentPos;
 236     }
 237
 238     return *this;
 239 }
 240
 241 // return first following position rendered at a different location, or "this"
 242 Position Position::nextCharacterPosition(EAffinity affinity) const
 243 {
 244     if (isNull())
 245         return Position();
 246
 247     Node *fromRootEditableElement = node()->rootEditableElement();
 248
 249     bool atEndOfLine = isEndOfLine(VisiblePosition(*this, affinity));
 250     bool rendered = isCandidate();
 251
 252     Position currentPos = *this;
 253     while (!currentPos.atEnd()) {
 254         currentPos = currentPos.next();
 255
 256         if (currentPos.node()->rootEditableElement() != fromRootEditableElement)
 257             return *this;
 258
 259         if (atEndOfLine || !rendered) {
 260             if (currentPos.isCandidate())
 261                 return currentPos;
 262         } else if (rendersInDifferentPosition(currentPos))
 263             return currentPos;
 264     }
 265
 266     return *this;
 267 }
 268
 269 // Whether or not [node, 0] and [node, maxDeepOffset(node)] are their own VisiblePositions.
 270 // If true, adjacent candidates are visually distinct.
 271 // FIXME: Disregard nodes with renderers that have no height, as we do in isCandidate.
 272 // FIXME: Share code with isCandidate, if possible.
 273 static bool endsOfNodeAreVisuallyDistinctPositions(Node* node)
 274 {
 275     if (!node || !node->renderer())
 276         return false;
 277
 278     if (!node->renderer()->isInline())
 279         return true;
 280
 281     // Don't include inline tables.
 282     if (node->hasTagName(tableTag))
 283         return false;
 284
 285     // There is a VisiblePosition inside an empty inline-block container.
 286     return node->renderer()->isReplaced() && canHaveChildrenForEditing(node) && node->renderer()->height() != 0 && !node->firstChild();
 287 }
 288
 289 static Node* enclosingVisualBoundary(Node* node)
 290 {
 291     while (node && !endsOfNodeAreVisuallyDistinctPositions(node))
 292         node = node->parentNode();
 293
 294     return node;
 295 }
 296
 297 // upstream() and downstream() want to return positions that are either in a
 298 // text node or at just before a non-text node.  This method checks for that.
 299 static bool isStreamer(const PositionIterator& pos)
 300 {
 301     if (!pos.node())
 302         return true;
 303
 304     if (isAtomicNode(pos.node()))
 305         return true;
 306
 307     return pos.atStartOfNode();
 308 }
 309
 310 // This function and downstream() are used for moving back and forth between visually equivalent candidates.
 311 // For example, for the text node "foo     bar" where whitespace is collapsible, there are two candidates
 312 // that map to the VisiblePosition between 'b' and the space.  This function will return the left candidate
 313 // and downstream() will return the right one.
 314 // Also, upstream() will return [boundary, 0] for any of the positions from [boundary, 0] to the first candidate
 315 // in boundary, where endsOfNodeAreVisuallyDistinctPositions(boundary) is true.
 316 Position Position::upstream() const
 317 {
 318     Node* startNode = node();
 319     if (!startNode)
 320         return Position();
 321
 322     // iterate backward from there, looking for a qualified position
 323     Node* boundary = enclosingVisualBoundary(startNode);
 324     PositionIterator lastVisible = *this;
 325     PositionIterator currentPos = lastVisible;
 326     bool startEditable = startNode->isContentEditable();
 327     Node* lastNode = startNode;
 328     for (; !currentPos.atStart(); currentPos.decrement()) {
 329         Node* currentNode = currentPos.node();
 330
 331         // Don't check for an editability change if we haven't moved to a different node,
 332         // to avoid the expense of computing isContentEditable().
 333         if (currentNode != lastNode) {
 334             // Don't change editability.
 335             bool currentEditable = currentNode->isContentEditable();
 336             if (startEditable != currentEditable)
 337                 break;
 338             lastNode = currentNode;
 339         }
 340
 341         // If we've moved to a position that is visually disinct, return the last saved position. There
 342         // is code below that terminates early if we're *about* to move to a visually distinct position.
 343         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentNode != boundary)
 344             return lastVisible;
 345
 346         // skip position in unrendered or invisible node
 347         RenderObject* renderer = currentNode->renderer();
 348         if (!renderer || renderer->style()->visibility() != VISIBLE)
 349             continue;
 350
 351         // track last visible streamer position
 352         if (isStreamer(currentPos))
 353             lastVisible = currentPos;
 354
 355         // Don't move past a position that is visually distinct.  We could rely on code above to terminate and
 356         // return lastVisible on the next iteration, but we terminate early to avoid doing a nodeIndex() call.
 357         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentPos.atStartOfNode())
 358             return lastVisible;
 359
 360         // Return position after tables and nodes which have content that can be ignored.
 361         if (editingIgnoresContent(currentNode) || isTableElement(currentNode)) {
 362             if (currentPos.atEndOfNode())
 363                 return Position(currentNode, maxDeepOffset(currentNode));
 364             continue;
 365         }
 366
 367         // return current position if it is in rendered text
 368         if (renderer->isText() && static_cast<RenderText*>(renderer)->firstTextBox()) {
 369             if (currentNode != startNode) {
 370                 // This assertion fires in layout tests in the case-transform.html test because
 371                 // of a mix-up between offsets in the text in the DOM tree with text in the
 372                 // render tree which can have a different length due to case transformation.
 373                 // Until we resolve that, disable this so we can run the layout tests!
 374                 //ASSERT(currentOffset >= renderer->caretMaxOffset());
 375                 return Position(currentNode, renderer->caretMaxOffset());
 376             }
 377
 378             unsigned textOffset = currentPos.offsetInLeafNode();
 379             RenderText* textRenderer = static_cast<RenderText*>(renderer);
 380             InlineTextBox* lastTextBox = textRenderer->lastTextBox();
 381             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 382                 if (textOffset <= box->start() + box->len()) {
 383                     if (textOffset > box->start())
 384                         return currentPos;
 385                     continue;
 386                 }
 387
 388                 if (box == lastTextBox || textOffset != box->start() + box->len() + 1)
 389                     continue;
 390
 391                 // The text continues on the next line only if the last text box is not on this line and
 392                 // none of the boxes on this line have a larger start offset.
 393
 394                 bool continuesOnNextLine = true;
 395                 InlineBox* otherBox = box;
 396                 while (continuesOnNextLine) {
 397                     otherBox = otherBox->nextLeafChild();
 398                     if (!otherBox)
 399                         break;
 400                     if (otherBox == lastTextBox || otherBox->object() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() > textOffset)
 401                         continuesOnNextLine = false;
 402                 }
 403
 404                 otherBox = box;
 405                 while (continuesOnNextLine) {
 406                     otherBox = otherBox->prevLeafChild();
 407                     if (!otherBox)
 408                         break;
 409                     if (otherBox == lastTextBox || otherBox->object() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() > textOffset)
 410                         continuesOnNextLine = false;
 411                 }
 412
 413                 if (continuesOnNextLine)
 414                     return currentPos;
 415             }
 416         }
 417     }
 418
 419     return lastVisible;
 420 }
 421
 422 // This function and upstream() are used for moving back and forth between visually equivalent candidates.
 423 // For example, for the text node "foo     bar" where whitespace is collapsible, there are two candidates
 424 // that map to the VisiblePosition between 'b' and the space.  This function will return the right candidate
 425 // and upstream() will return the left one.
 426 // Also, downstream() will return the last position in the last atomic node in boundary for all of the positions
 427 // in boundary after the last candidate, where endsOfNodeAreVisuallyDistinctPositions(boundary).
 428 Position Position::downstream() const
 429 {
 430     Node* startNode = node();
 431     if (!startNode)
 432         return Position();
 433
 434     // iterate forward from there, looking for a qualified position
 435     Node* boundary = enclosingVisualBoundary(startNode);
 436     PositionIterator lastVisible = *this;
 437     PositionIterator currentPos = lastVisible;
 438     bool startEditable = startNode->isContentEditable();
 439     Node* lastNode = startNode;
 440     for (; !currentPos.atEnd(); currentPos.increment()) {
 441         Node* currentNode = currentPos.node();
 442
 443         // Don't check for an editability change if we haven't moved to a different node,
 444         // to avoid the expense of computing isContentEditable().
 445         if (currentNode != lastNode) {
 446             // Don't change editability.
 447             bool currentEditable = currentNode->isContentEditable();
 448             if (startEditable != currentEditable)
 449                 break;
 450             lastNode = currentNode;
 451         }
 452
 453         // stop before going above the body, up into the head
 454         // return the last visible streamer position
 455         if (currentNode->hasTagName(bodyTag) && currentPos.atEndOfNode())
 456             break;
 457
 458         // Do not move to a visually distinct position.
 459         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentNode != boundary)
 460             return lastVisible;
 461         // Do not move past a visually disinct position.
 462         // Note: The first position after the last in a node whose ends are visually distinct
 463         // positions will be [boundary->parentNode(), originalBlock->nodeIndex() + 1].
 464         if (boundary && boundary->parentNode() == currentNode)
 465             return lastVisible;
 466
 467         // skip position in unrendered or invisible node
 468         RenderObject* renderer = currentNode->renderer();
 469         if (!renderer || renderer->style()->visibility() != VISIBLE)
 470             continue;
 471
 472         // track last visible streamer position
 473         if (isStreamer(currentPos))
 474             lastVisible = currentPos;
 475
 476         // Return position before tables and nodes which have content that can be ignored.
 477         if (editingIgnoresContent(currentNode) || isTableElement(currentNode)) {
 478             if (currentPos.offsetInLeafNode() <= renderer->caretMinOffset())
 479                 return Position(currentNode, renderer->caretMinOffset());
 480             continue;
 481         }
 482
 483         // return current position if it is in rendered text
 484         if (renderer->isText() && static_cast<RenderText*>(renderer)->firstTextBox()) {
 485             if (currentNode != startNode) {
 486                 ASSERT(currentPos.atStartOfNode());
 487                 return Position(currentNode, renderer->caretMinOffset());
 488             }
 489
 490             unsigned textOffset = currentPos.offsetInLeafNode();
 491             RenderText* textRenderer = static_cast<RenderText*>(renderer);
 492             InlineTextBox* lastTextBox = textRenderer->lastTextBox();
 493             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 494                 if (textOffset <= box->end()) {
 495                     if (textOffset >= box->start())
 496                         return currentPos;
 497                     continue;
 498                 }
 499
 500                 if (box == lastTextBox || textOffset != box->start() + box->len())
 501                     continue;
 502
 503                 // The text continues on the next line only if the last text box is not on this line and
 504                 // none of the boxes on this line have a larger start offset.
 505
 506                 bool continuesOnNextLine = true;
 507                 InlineBox* otherBox = box;
 508                 while (continuesOnNextLine) {
 509                     otherBox = otherBox->nextLeafChild();
 510                     if (!otherBox)
 511                         break;
 512                     if (otherBox == lastTextBox || otherBox->object() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() >= textOffset)
 513                         continuesOnNextLine = false;
 514                 }
 515
 516                 otherBox = box;
 517                 while (continuesOnNextLine) {
 518                     otherBox = otherBox->prevLeafChild();
 519                     if (!otherBox)
 520                         break;
 521                     if (otherBox == lastTextBox || otherBox->object() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() >= textOffset)
 522                         continuesOnNextLine = false;
 523                 }
 524
 525                 if (continuesOnNextLine)
 526                     return currentPos;
 527             }
 528         }
 529     }
 530
 531     return lastVisible;
 532 }
 533
 534 bool Position::hasRenderedNonAnonymousDescendantsWithHeight(RenderObject* renderer)
 535 {
 536     RenderObject* stop = renderer->nextInPreOrderAfterChildren();
 537     for (RenderObject *o = renderer->firstChild(); o && o != stop; o = o->nextInPreOrder())
 538         if (o->element() && o->height())
 539             return true;
 540
 541     return false;
 542 }
 543
 544 bool Position::nodeIsUserSelectNone(Node* node)
 545 {
 546     return node && node->renderer() && node->renderer()->style()->userSelect() == SELECT_NONE;
 547 }
 548
 549 bool Position::isCandidate() const
 550 {
 551     if (isNull())
 552         return false;
 553
 554     RenderObject *renderer = node()->renderer();
 555     if (!renderer)
 556         return false;
 557
 558     if (renderer->style()->visibility() != VISIBLE)
 559         return false;
 560
 561     if (renderer->isBR())
 562         return offset() == 0 && !nodeIsUserSelectNone(node()->parent());
 563
 564     if (renderer->isText())
 565         return inRenderedText() && !nodeIsUserSelectNone(node());
 566
 567     if (isTableElement(node()) || editingIgnoresContent(node()))
 568         return (offset() == 0 || offset() == maxDeepOffset(node())) && !nodeIsUserSelectNone(node()->parent());
 569
 570     if (!node()->hasTagName(htmlTag) && renderer->isBlockFlow() && !hasRenderedNonAnonymousDescendantsWithHeight(renderer) &&
 571        (renderer->height() || node()->hasTagName(bodyTag)))
 572         return offset() == 0 && !nodeIsUserSelectNone(node());
 573
 574     return false;
 575 }
 576
 577 bool Position::inRenderedText() const
 578 {
 579     if (isNull() || !node()->isTextNode())
 580         return false;
 581
 582     RenderObject *renderer = node()->renderer();
 583     if (!renderer)
 584         return false;
 585
 586     RenderText *textRenderer = static_cast<RenderText *>(renderer);
 587     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 588         if (offset() < box->m_start && !textRenderer->containsReversedText()) {
 589             // The offset we're looking for is before this node
 590             // this means the offset must be in content that is
 591             // not rendered. Return false.
 592             return false;
 593         }
 594         if (box->containsCaretOffset(offset()))
 595             // Return false for offsets inside composed characters.
 596             return offset() == 0 || offset() == textRenderer->nextOffset(textRenderer->previousOffset(offset()));
 597     }
 598
 599     return false;
 600 }
 601
 602 static unsigned caretMaxRenderedOffset(const Node* n)
 603 {
 604     RenderObject* r = n->renderer();
 605     if (r)
 606         return r->caretMaxRenderedOffset();
 607
 608     if (n->isCharacterDataNode())
 609         return static_cast<const CharacterData*>(n)->length();
 610     return 1;
 611 }
 612
 613 bool Position::isRenderedCharacter() const
 614 {
 615     if (isNull() || !node()->isTextNode())
 616         return false;
 617
 618     RenderObject *renderer = node()->renderer();
 619     if (!renderer)
 620         return false;
 621
 622     RenderText *textRenderer = static_cast<RenderText *>(renderer);
 623     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 624         if (offset() < box->m_start && !textRenderer->containsReversedText()) {
 625             // The offset we're looking for is before this node
 626             // this means the offset must be in content that is
 627             // not rendered. Return false.
 628             return false;
 629         }
 630         if (offset() >= box->m_start && offset() < box->m_start + box->m_len)
 631             return true;
 632     }
 633
 634     return false;
 635 }
 636
 637 bool Position::rendersInDifferentPosition(const Position &pos) const
 638 {
 639     if (isNull() || pos.isNull())
 640         return false;
 641
 642     RenderObject *renderer = node()->renderer();
 643     if (!renderer)
 644         return false;
 645
 646     RenderObject *posRenderer = pos.node()->renderer();
 647     if (!posRenderer)
 648         return false;
 649
 650     if (renderer->style()->visibility() != VISIBLE ||
 651         posRenderer->style()->visibility() != VISIBLE)
 652         return false;
 653
 654     if (node() == pos.node()) {
 655         if (node()->hasTagName(brTag))
 656             return false;
 657
 658         if (offset() == pos.offset())
 659             return false;
 660
 661         if (!node()->isTextNode() && !pos.node()->isTextNode()) {
 662             if (offset() != pos.offset())
 663                 return true;
 664         }
 665     }
 666
 667     if (node()->hasTagName(brTag) && pos.isCandidate())
 668         return true;
 669
 670     if (pos.node()->hasTagName(brTag) && isCandidate())
 671         return true;
 672
 673     if (node()->enclosingBlockFlowElement() != pos.node()->enclosingBlockFlowElement())
 674         return true;
 675
 676     if (node()->isTextNode() && !inRenderedText())
 677         return false;
 678
 679     if (pos.node()->isTextNode() && !pos.inRenderedText())
 680         return false;
 681
 682     int thisRenderedOffset = renderedOffset();
 683     int posRenderedOffset = pos.renderedOffset();
 684
 685     if (renderer == posRenderer && thisRenderedOffset == posRenderedOffset)
 686         return false;
 687
 688     int ignoredCaretOffset;
 689     InlineBox* b1;
 690     getInlineBoxAndOffset(DOWNSTREAM, b1, ignoredCaretOffset);
 691     InlineBox* b2;
 692     pos.getInlineBoxAndOffset(DOWNSTREAM, b2, ignoredCaretOffset);
 693
 694     LOG(Editing, "renderer:               %p [%p]\n", renderer, b1);
 695     LOG(Editing, "thisRenderedOffset:         %d\n", thisRenderedOffset);
 696     LOG(Editing, "posRenderer:            %p [%p]\n", posRenderer, b2);
 697     LOG(Editing, "posRenderedOffset:      %d\n", posRenderedOffset);
 698     LOG(Editing, "node min/max:           %d:%d\n", caretMinOffset(node()), caretMaxRenderedOffset(node()));
 699     LOG(Editing, "pos node min/max:       %d:%d\n", caretMinOffset(pos.node()), caretMaxRenderedOffset(pos.node()));
 700     LOG(Editing, "----------------------------------------------------------------------\n");
 701
 702     if (!b1 || !b2) {
 703         return false;
 704     }
 705
 706     if (b1->root() != b2->root()) {
 707         return true;
 708     }
 709
 710     if (nextRenderedEditable(node()) == pos.node() &&
 711         thisRenderedOffset == (int)caretMaxRenderedOffset(node()) && posRenderedOffset == 0) {
 712         return false;
 713     }
 714
 715     if (previousRenderedEditable(node()) == pos.node() &&
 716         thisRenderedOffset == 0 && posRenderedOffset == (int)caretMaxRenderedOffset(pos.node())) {
 717         return false;
 718     }
 719
 720     return true;
 721 }
 722
 723 // This assumes that it starts in editable content.
 724 Position Position::leadingWhitespacePosition(EAffinity affinity, bool considerNonCollapsibleWhitespace) const
 725 {
 726     ASSERT(isEditablePosition(*this));
 727     if (isNull())
 728         return Position();
 729
 730     if (upstream().node()->hasTagName(brTag))
 731         return Position();
 732
 733     Position prev = previousCharacterPosition(affinity);
 734     if (prev != *this && prev.node()->inSameContainingBlockFlowElement(node()) && prev.node()->isTextNode()) {
 735         String string = static_cast<Text *>(prev.node())->data();
 736         UChar c = string[prev.offset()];
 737         if (considerNonCollapsibleWhitespace ? (isSpaceOrNewline(c) || c == noBreakSpace) : isCollapsibleWhitespace(c))
 738             if (isEditablePosition(prev))
 739                 return prev;
 740     }
 741
 742     return Position();
 743 }
 744
 745 // This assumes that it starts in editable content.
 746 Position Position::trailingWhitespacePosition(EAffinity affinity, bool considerNonCollapsibleWhitespace) const
 747 {
 748     ASSERT(isEditablePosition(*this));
 749     if (isNull())
 750         return Position();
 751
 752     VisiblePosition v(*this);
 753     UChar c = v.characterAfter();
 754     // The space must not be in another paragraph and it must be editable.
 755     if (!isEndOfParagraph(v) && v.next(true).isNotNull())
 756         if (considerNonCollapsibleWhitespace ? (isSpaceOrNewline(c) || c == noBreakSpace) : isCollapsibleWhitespace(c))
 757             return *this;
 758
 759     return Position();
 760 }
 761
 762 void Position::getInlineBoxAndOffset(EAffinity affinity, InlineBox*& inlineBox, int& caretOffset) const
 763 {
 764     TextDirection primaryDirection = LTR;
 765     for (RenderObject* r = node()->renderer(); r; r = r->parent()) {
 766         if (r->isBlockFlow()) {
 767             primaryDirection = r->style()->direction();
 768             break;
 769         }
 770     }
 771     getInlineBoxAndOffset(affinity, primaryDirection, inlineBox, caretOffset);
 772 }
 773
 774 void Position::getInlineBoxAndOffset(EAffinity affinity, TextDirection primaryDirection, InlineBox*& inlineBox, int& caretOffset) const
 775 {
 776     caretOffset = offset();
 777     RenderObject* renderer = node()->renderer();
 778     if (!renderer->isText()) {
 779         inlineBox = renderer->inlineBoxWrapper();
 780         if (!inlineBox || caretOffset > inlineBox->caretMinOffset() && caretOffset < inlineBox->caretMaxOffset())
 781             return;
 782     } else {
 783         RenderText* textRenderer = static_cast<RenderText*>(renderer);
 784
 785         InlineTextBox* box;
 786         InlineTextBox* candidate = 0;
 787
 788         for (box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 789             int caretMinOffset = box->caretMinOffset();
 790             int caretMaxOffset = box->caretMaxOffset();
 791
 792             if (caretOffset < caretMinOffset || caretOffset > caretMaxOffset || caretOffset == caretMaxOffset && box->isLineBreak())
 793                 continue;
 794
 795             if (caretOffset > caretMinOffset && caretOffset < caretMaxOffset) {
 796                 inlineBox = box;
 797                 return;
 798             }
 799
 800             if ((caretOffset == caretMinOffset) ^ (affinity == UPSTREAM))
 801                 break;
 802
 803             candidate = box;
 804         }
 805         inlineBox = box ? box : candidate;
 806     }
 807
 808     if (!inlineBox)
 809         return;
 810
 811     unsigned char level = inlineBox->bidiLevel();
 812
 813     if (inlineBox->direction() == primaryDirection) {
 814         if (caretOffset == inlineBox->caretRightmostOffset()) {
 815             InlineBox* nextBox = inlineBox->nextLeafChild();
 816             if (!nextBox || nextBox->bidiLevel() >= level)
 817                 return;
 818
 819             level = nextBox->bidiLevel();
 820             InlineBox* prevBox = inlineBox;
 821             do {
 822                 prevBox = prevBox->prevLeafChild();
 823             } while (prevBox && prevBox->bidiLevel() > level);
 824
 825             if (prevBox && prevBox->bidiLevel() == level)   // For example, abc FED 123 ^ CBA
 826                 return;
 827
 828             // For example, abc 123 ^ CBA
 829             while (InlineBox* nextBox = inlineBox->nextLeafChild()) {
 830                 if (nextBox->bidiLevel() < level)
 831                     break;
 832                 inlineBox = nextBox;
 833             }
 834             caretOffset = inlineBox->caretRightmostOffset();
 835         } else {
 836             InlineBox* prevBox = inlineBox->prevLeafChild();
 837             if (!prevBox || prevBox->bidiLevel() >= level)
 838                 return;
 839
 840             level = prevBox->bidiLevel();
 841             InlineBox* nextBox = inlineBox;
 842             do {
 843                 nextBox = nextBox->nextLeafChild();
 844             } while (nextBox && nextBox->bidiLevel() > level);
 845
 846             if (nextBox && nextBox->bidiLevel() == level)
 847                 return;
 848
 849             while (InlineBox* prevBox = inlineBox->prevLeafChild()) {
 850                 if (prevBox->bidiLevel() < level)
 851                     break;
 852                 inlineBox = prevBox;
 853             }
 854             caretOffset = inlineBox->caretLeftmostOffset();
 855         }
 856         return;
 857     }
 858
 859     if (caretOffset == inlineBox->caretLeftmostOffset()) {
 860         InlineBox* prevBox = inlineBox->prevLeafChild();
 861         if (!prevBox || prevBox->bidiLevel() < level) {
 862             // Left edge of a secondary run. Set to the right edge of the entire run.
 863             while (InlineBox* nextBox = inlineBox->nextLeafChild()) {
 864                 if (nextBox->bidiLevel() < level)
 865                     break;
 866                 inlineBox = nextBox;
 867             }
 868             caretOffset = inlineBox->caretRightmostOffset();
 869         } else if (prevBox->bidiLevel() > level) {
 870             // Right edge of a "tertiary" run. Set to the left edge of that run.
 871             while (InlineBox* tertiaryBox = inlineBox->prevLeafChild()) {
 872                 if (tertiaryBox->bidiLevel() <= level)
 873                     break;
 874                 inlineBox = tertiaryBox;
 875             }
 876             caretOffset = inlineBox->caretLeftmostOffset();
 877         }
 878     } else {
 879         InlineBox* nextBox = inlineBox->nextLeafChild();
 880         if (!nextBox || nextBox->bidiLevel() < level) {
 881             // Right edge of a secondary run. Set to the left edge of the entire run.
 882             while (InlineBox* prevBox = inlineBox->prevLeafChild()) {
 883                 if (prevBox->bidiLevel() < level)
 884                     break;
 885                 inlineBox = prevBox;
 886             }
 887             caretOffset = inlineBox->caretLeftmostOffset();
 888         } else if (nextBox->bidiLevel() > level) {
 889             // Left edge of a "tertiary" run. Set to the right edge of that run.
 890             while (InlineBox* tertiaryBox = inlineBox->nextLeafChild()) {
 891                 if (tertiaryBox->bidiLevel() <= level)
 892                     break;
 893                 inlineBox = tertiaryBox;
 894             }
 895             caretOffset = inlineBox->caretRightmostOffset();
 896         }
 897     }
 898 }
 899
 900 void Position::debugPosition(const char* msg) const
 901 {
 902     if (isNull())
 903         fprintf(stderr, "Position [%s]: null\n", msg);
 904     else
 905         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, node()->nodeName().utf8().data(), node(), offset());
 906 }
 907
 908 #ifndef NDEBUG
 909
 910 void Position::formatForDebugger(char* buffer, unsigned length) const
 911 {
 912     String result;
 913
 914     if (isNull())
 915         result = "<null>";
 916     else {
 917         char s[1024];
 918         result += "offset ";
 919         result += String::number(offset());
 920         result += " of ";
 921         node()->formatForDebugger(s, sizeof(s));
 922         result += s;
 923     }
 924
 925     strncpy(buffer, result.utf8().data(), length - 1);
 926 }
 927
 928 void Position::showTreeForThis() const
 929 {
 930     if (node())
 931         node()->showTreeForThis();
 932 }
 933
 934 #endif
 935
 936 Position startPosition(const Range* r)
 937 {
 938     return r ? r->startPosition() : Position();
 939 }
 940
 941 Position endPosition(const Range* r)
 942 {
 943     return r ? r->endPosition() : Position();
 944 }
 945
 946 } // namespace WebCore
 947
 948 #ifndef NDEBUG
 949
 950 void showTree(const WebCore::Position& pos)
 951 {
 952     pos.showTreeForThis();
 953 }
 954
 955 void showTree(const WebCore::Position* pos)
 956 {
 957     if (pos)
 958         pos->showTreeForThis();
 959 }
 960
 961 #endif