src/third_party/WebKit/Source/core/dom/Position.cpp

   1 /*
   2  * Copyright (C) 2004, 2005, 2006, 2009 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "core/dom/Position.h"
  28
  29 #include "core/HTMLNames.h"
  30 #include "core/css/CSSComputedStyleDeclaration.h"
  31 #include "core/dom/PositionIterator.h"
  32 #include "core/dom/Text.h"
  33 #include "core/editing/TextIterator.h"
  34 #include "core/editing/VisiblePosition.h"
  35 #include "core/editing/VisibleUnits.h"
  36 #include "core/editing/htmlediting.h"
  37 #include "core/frame/LocalFrame.h"
  38 #include "core/frame/Settings.h"
  39 #include "core/html/HTMLTableElement.h"
  40 #include "core/rendering/InlineIterator.h"
  41 #include "core/rendering/InlineTextBox.h"
  42 #include "core/rendering/RenderBlock.h"
  43 #include "core/rendering/RenderInline.h"
  44 #include "core/rendering/RenderText.h"
  45 #include "platform/Logging.h"
  46 #include "wtf/text/CString.h"
  47 #include "wtf/unicode/CharacterNames.h"
  48 #include <stdio.h>
  49
  50 namespace WebCore {
  51
  52 using namespace HTMLNames;
  53
  54 static Node* nextRenderedEditable(Node* node)
  55 {
  56     while ((node = node->nextLeafNode())) {
  57         RenderObject* renderer = node->renderer();
  58         if (!renderer)
  59             continue;
  60         if (!node->rendererIsEditable())
  61             continue;
  62         if ((renderer->isBox() && toRenderBox(renderer)->inlineBoxWrapper()) || (renderer->isText() && toRenderText(renderer)->firstTextBox()))
  63             return node;
  64     }
  65     return 0;
  66 }
  67
  68 static Node* previousRenderedEditable(Node* node)
  69 {
  70     while ((node = node->previousLeafNode())) {
  71         RenderObject* renderer = node->renderer();
  72         if (!renderer)
  73             continue;
  74         if (!node->rendererIsEditable())
  75             continue;
  76         if ((renderer->isBox() && toRenderBox(renderer)->inlineBoxWrapper()) || (renderer->isText() && toRenderText(renderer)->firstTextBox()))
  77             return node;
  78     }
  79     return 0;
  80 }
  81
  82 Position::Position(PassRefPtrWillBeRawPtr<Node> anchorNode, LegacyEditingOffset offset)
  83     : m_anchorNode(anchorNode)
  84     , m_offset(offset.value())
  85     , m_anchorType(anchorTypeForLegacyEditingPosition(m_anchorNode.get(), m_offset))
  86     , m_isLegacyEditingPosition(true)
  87 {
  88     ASSERT(!m_anchorNode || !m_anchorNode->isPseudoElement());
  89 }
  90
  91 Position::Position(PassRefPtrWillBeRawPtr<Node> anchorNode, AnchorType anchorType)
  92     : m_anchorNode(anchorNode)
  93     , m_offset(0)
  94     , m_anchorType(anchorType)
  95     , m_isLegacyEditingPosition(false)
  96 {
  97     ASSERT(!m_anchorNode || !m_anchorNode->isPseudoElement());
  98
  99     ASSERT(anchorType != PositionIsOffsetInAnchor);
 100     ASSERT(!((anchorType == PositionIsBeforeChildren || anchorType == PositionIsAfterChildren)
 101         && (m_anchorNode->isTextNode() || editingIgnoresContent(m_anchorNode.get()))));
 102 }
 103
 104 Position::Position(PassRefPtrWillBeRawPtr<Node> anchorNode, int offset, AnchorType anchorType)
 105     : m_anchorNode(anchorNode)
 106     , m_offset(offset)
 107     , m_anchorType(anchorType)
 108     , m_isLegacyEditingPosition(false)
 109 {
 110     ASSERT(!m_anchorNode || !m_anchorNode->isPseudoElement());
 111
 112     ASSERT(anchorType == PositionIsOffsetInAnchor);
 113 }
 114
 115 Position::Position(PassRefPtrWillBeRawPtr<Text> textNode, unsigned offset)
 116     : m_anchorNode(textNode)
 117     , m_offset(static_cast<int>(offset))
 118     , m_anchorType(PositionIsOffsetInAnchor)
 119     , m_isLegacyEditingPosition(false)
 120 {
 121     ASSERT(m_anchorNode);
 122 }
 123
 124 void Position::moveToPosition(PassRefPtrWillBeRawPtr<Node> node, int offset)
 125 {
 126     ASSERT(!editingIgnoresContent(node.get()));
 127     ASSERT(anchorType() == PositionIsOffsetInAnchor || m_isLegacyEditingPosition);
 128     m_anchorNode = node;
 129     m_offset = offset;
 130     if (m_isLegacyEditingPosition)
 131         m_anchorType = anchorTypeForLegacyEditingPosition(m_anchorNode.get(), m_offset);
 132 }
 133 void Position::moveToOffset(int offset)
 134 {
 135     ASSERT(anchorType() == PositionIsOffsetInAnchor || m_isLegacyEditingPosition);
 136     m_offset = offset;
 137     if (m_isLegacyEditingPosition)
 138         m_anchorType = anchorTypeForLegacyEditingPosition(m_anchorNode.get(), m_offset);
 139 }
 140
 141 Node* Position::containerNode() const
 142 {
 143     if (!m_anchorNode)
 144         return 0;
 145
 146     switch (anchorType()) {
 147     case PositionIsBeforeChildren:
 148     case PositionIsAfterChildren:
 149     case PositionIsOffsetInAnchor:
 150         return m_anchorNode.get();
 151     case PositionIsBeforeAnchor:
 152     case PositionIsAfterAnchor:
 153         return m_anchorNode->parentNode();
 154     }
 155     ASSERT_NOT_REACHED();
 156     return 0;
 157 }
 158
 159 Text* Position::containerText() const
 160 {
 161     switch (anchorType()) {
 162     case PositionIsOffsetInAnchor:
 163         return m_anchorNode && m_anchorNode->isTextNode() ? toText(m_anchorNode) : 0;
 164     case PositionIsBeforeAnchor:
 165     case PositionIsAfterAnchor:
 166         return 0;
 167     case PositionIsBeforeChildren:
 168     case PositionIsAfterChildren:
 169         ASSERT(!m_anchorNode || !m_anchorNode->isTextNode());
 170         return 0;
 171     }
 172     ASSERT_NOT_REACHED();
 173     return 0;
 174 }
 175
 176 int Position::computeOffsetInContainerNode() const
 177 {
 178     if (!m_anchorNode)
 179         return 0;
 180
 181     switch (anchorType()) {
 182     case PositionIsBeforeChildren:
 183         return 0;
 184     case PositionIsAfterChildren:
 185         return lastOffsetInNode(m_anchorNode.get());
 186     case PositionIsOffsetInAnchor:
 187         return minOffsetForNode(m_anchorNode.get(), m_offset);
 188     case PositionIsBeforeAnchor:
 189         return m_anchorNode->nodeIndex();
 190     case PositionIsAfterAnchor:
 191         return m_anchorNode->nodeIndex() + 1;
 192     }
 193     ASSERT_NOT_REACHED();
 194     return 0;
 195 }
 196
 197 int Position::offsetForPositionAfterAnchor() const
 198 {
 199     ASSERT(m_anchorType == PositionIsAfterAnchor || m_anchorType == PositionIsAfterChildren);
 200     ASSERT(!m_isLegacyEditingPosition);
 201     return lastOffsetForEditing(m_anchorNode.get());
 202 }
 203
 204 // Neighbor-anchored positions are invalid DOM positions, so they need to be
 205 // fixed up before handing them off to the Range object.
 206 Position Position::parentAnchoredEquivalent() const
 207 {
 208     if (!m_anchorNode)
 209         return Position();
 210
 211     // FIXME: This should only be necessary for legacy positions, but is also needed for positions before and after Tables
 212     if (m_offset <= 0 && (m_anchorType != PositionIsAfterAnchor && m_anchorType != PositionIsAfterChildren)) {
 213         if (m_anchorNode->parentNode() && (editingIgnoresContent(m_anchorNode.get()) || isRenderedTableElement(m_anchorNode.get())))
 214             return positionInParentBeforeNode(*m_anchorNode);
 215         return Position(m_anchorNode.get(), 0, PositionIsOffsetInAnchor);
 216     }
 217     if (!m_anchorNode->offsetInCharacters()
 218         && (m_anchorType == PositionIsAfterAnchor || m_anchorType == PositionIsAfterChildren || static_cast<unsigned>(m_offset) == m_anchorNode->countChildren())
 219         && (editingIgnoresContent(m_anchorNode.get()) || isRenderedTableElement(m_anchorNode.get()))
 220         && containerNode()) {
 221         return positionInParentAfterNode(*m_anchorNode);
 222     }
 223
 224     return Position(containerNode(), computeOffsetInContainerNode(), PositionIsOffsetInAnchor);
 225 }
 226
 227 Node* Position::computeNodeBeforePosition() const
 228 {
 229     if (!m_anchorNode)
 230         return 0;
 231     switch (anchorType()) {
 232     case PositionIsBeforeChildren:
 233         return 0;
 234     case PositionIsAfterChildren:
 235         return m_anchorNode->lastChild();
 236     case PositionIsOffsetInAnchor:
 237         return m_anchorNode->traverseToChildAt(m_offset - 1); // -1 converts to traverseToChildAt((unsigned)-1) and returns null.
 238     case PositionIsBeforeAnchor:
 239         return m_anchorNode->previousSibling();
 240     case PositionIsAfterAnchor:
 241         return m_anchorNode.get();
 242     }
 243     ASSERT_NOT_REACHED();
 244     return 0;
 245 }
 246
 247 Node* Position::computeNodeAfterPosition() const
 248 {
 249     if (!m_anchorNode)
 250         return 0;
 251
 252     switch (anchorType()) {
 253     case PositionIsBeforeChildren:
 254         return m_anchorNode->firstChild();
 255     case PositionIsAfterChildren:
 256         return 0;
 257     case PositionIsOffsetInAnchor:
 258         return m_anchorNode->traverseToChildAt(m_offset);
 259     case PositionIsBeforeAnchor:
 260         return m_anchorNode.get();
 261     case PositionIsAfterAnchor:
 262         return m_anchorNode->nextSibling();
 263     }
 264     ASSERT_NOT_REACHED();
 265     return 0;
 266 }
 267
 268 Position::AnchorType Position::anchorTypeForLegacyEditingPosition(Node* anchorNode, int offset)
 269 {
 270     if (anchorNode && editingIgnoresContent(anchorNode)) {
 271         if (offset == 0)
 272             return Position::PositionIsBeforeAnchor;
 273         return Position::PositionIsAfterAnchor;
 274     }
 275     return Position::PositionIsOffsetInAnchor;
 276 }
 277
 278 // FIXME: This method is confusing (does it return anchorNode() or containerNode()?) and should be renamed or removed
 279 Element* Position::element() const
 280 {
 281     Node* n = anchorNode();
 282     while (n && !n->isElementNode())
 283         n = n->parentNode();
 284     return toElement(n);
 285 }
 286
 287 PassRefPtrWillBeRawPtr<CSSComputedStyleDeclaration> Position::computedStyle() const
 288 {
 289     Element* elem = element();
 290     if (!elem)
 291         return nullptr;
 292     return CSSComputedStyleDeclaration::create(elem);
 293 }
 294
 295 Position Position::previous(PositionMoveType moveType) const
 296 {
 297     Node* node = deprecatedNode();
 298     if (!node)
 299         return *this;
 300
 301     int offset = deprecatedEditingOffset();
 302     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
 303     ASSERT(offset >= 0);
 304
 305     if (offset > 0) {
 306         if (Node* child = node->traverseToChildAt(offset - 1))
 307             return lastPositionInOrAfterNode(child);
 308
 309         // There are two reasons child might be 0:
 310         //   1) The node is node like a text node that is not an element, and therefore has no children.
 311         //      Going backward one character at a time is correct.
 312         //   2) The old offset was a bogus offset like (<br>, 1), and there is no child.
 313         //      Going from 1 to 0 is correct.
 314         switch (moveType) {
 315         case CodePoint:
 316             return createLegacyEditingPosition(node, offset - 1);
 317         case Character:
 318             return createLegacyEditingPosition(node, uncheckedPreviousOffset(node, offset));
 319         case BackwardDeletion:
 320             return createLegacyEditingPosition(node, uncheckedPreviousOffsetForBackwardDeletion(node, offset));
 321         }
 322     }
 323
 324     if (ContainerNode* parent = node->parentNode())
 325         return createLegacyEditingPosition(parent, node->nodeIndex());
 326     return *this;
 327 }
 328
 329 Position Position::next(PositionMoveType moveType) const
 330 {
 331     ASSERT(moveType != BackwardDeletion);
 332
 333     Node* node = deprecatedNode();
 334     if (!node)
 335         return *this;
 336
 337     int offset = deprecatedEditingOffset();
 338     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
 339     ASSERT(offset >= 0);
 340
 341     if (Node* child = node->traverseToChildAt(offset))
 342         return firstPositionInOrBeforeNode(child);
 343
 344     if (!node->hasChildren() && offset < lastOffsetForEditing(node)) {
 345         // There are two reasons child might be 0:
 346         //   1) The node is node like a text node that is not an element, and therefore has no children.
 347         //      Going forward one character at a time is correct.
 348         //   2) The new offset is a bogus offset like (<br>, 1), and there is no child.
 349         //      Going from 0 to 1 is correct.
 350         return createLegacyEditingPosition(node, (moveType == Character) ? uncheckedNextOffset(node, offset) : offset + 1);
 351     }
 352
 353     if (ContainerNode* parent = node->parentNode())
 354         return createLegacyEditingPosition(parent, node->nodeIndex() + 1);
 355     return *this;
 356 }
 357
 358 int Position::uncheckedPreviousOffset(const Node* n, int current)
 359 {
 360     return n->renderer() ? n->renderer()->previousOffset(current) : current - 1;
 361 }
 362
 363 int Position::uncheckedPreviousOffsetForBackwardDeletion(const Node* n, int current)
 364 {
 365     return n->renderer() ? n->renderer()->previousOffsetForBackwardDeletion(current) : current - 1;
 366 }
 367
 368 int Position::uncheckedNextOffset(const Node* n, int current)
 369 {
 370     return n->renderer() ? n->renderer()->nextOffset(current) : current + 1;
 371 }
 372
 373 bool Position::atFirstEditingPositionForNode() const
 374 {
 375     if (isNull())
 376         return true;
 377     // FIXME: Position before anchor shouldn't be considered as at the first editing position for node
 378     // since that position resides outside of the node.
 379     switch (m_anchorType) {
 380     case PositionIsOffsetInAnchor:
 381         return m_offset <= 0;
 382     case PositionIsBeforeChildren:
 383     case PositionIsBeforeAnchor:
 384         return true;
 385     case PositionIsAfterChildren:
 386     case PositionIsAfterAnchor:
 387         return !lastOffsetForEditing(deprecatedNode());
 388     }
 389     ASSERT_NOT_REACHED();
 390     return false;
 391 }
 392
 393 bool Position::atLastEditingPositionForNode() const
 394 {
 395     if (isNull())
 396         return true;
 397     // FIXME: Position after anchor shouldn't be considered as at the first editing position for node
 398     // since that position resides outside of the node.
 399     return m_anchorType == PositionIsAfterAnchor || m_anchorType == PositionIsAfterChildren || m_offset >= lastOffsetForEditing(deprecatedNode());
 400 }
 401
 402 // A position is considered at editing boundary if one of the following is true:
 403 // 1. It is the first position in the node and the next visually equivalent position
 404 //    is non editable.
 405 // 2. It is the last position in the node and the previous visually equivalent position
 406 //    is non editable.
 407 // 3. It is an editable position and both the next and previous visually equivalent
 408 //    positions are both non editable.
 409 bool Position::atEditingBoundary() const
 410 {
 411     Position nextPosition = downstream(CanCrossEditingBoundary);
 412     if (atFirstEditingPositionForNode() && nextPosition.isNotNull() && !nextPosition.deprecatedNode()->rendererIsEditable())
 413         return true;
 414
 415     Position prevPosition = upstream(CanCrossEditingBoundary);
 416     if (atLastEditingPositionForNode() && prevPosition.isNotNull() && !prevPosition.deprecatedNode()->rendererIsEditable())
 417         return true;
 418
 419     return nextPosition.isNotNull() && !nextPosition.deprecatedNode()->rendererIsEditable()
 420         && prevPosition.isNotNull() && !prevPosition.deprecatedNode()->rendererIsEditable();
 421 }
 422
 423 Node* Position::parentEditingBoundary() const
 424 {
 425     if (!m_anchorNode)
 426         return 0;
 427
 428     Node* documentElement = m_anchorNode->document().documentElement();
 429     if (!documentElement)
 430         return 0;
 431
 432     Node* boundary = m_anchorNode.get();
 433     while (boundary != documentElement && boundary->nonShadowBoundaryParentNode() && m_anchorNode->rendererIsEditable() == boundary->parentNode()->rendererIsEditable())
 434         boundary = boundary->nonShadowBoundaryParentNode();
 435
 436     return boundary;
 437 }
 438
 439
 440 bool Position::atStartOfTree() const
 441 {
 442     if (isNull())
 443         return true;
 444     return !deprecatedNode()->parentNode() && m_offset <= 0;
 445 }
 446
 447 bool Position::atEndOfTree() const
 448 {
 449     if (isNull())
 450         return true;
 451     return !deprecatedNode()->parentNode() && m_offset >= lastOffsetForEditing(deprecatedNode());
 452 }
 453
 454 int Position::renderedOffset() const
 455 {
 456     if (!deprecatedNode()->isTextNode())
 457         return m_offset;
 458
 459     if (!deprecatedNode()->renderer())
 460         return m_offset;
 461
 462     int result = 0;
 463     RenderText* textRenderer = toRenderText(deprecatedNode()->renderer());
 464     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 465         int start = box->start();
 466         int end = box->start() + box->len();
 467         if (m_offset < start)
 468             return result;
 469         if (m_offset <= end) {
 470             result += m_offset - start;
 471             return result;
 472         }
 473         result += box->len();
 474     }
 475     return result;
 476 }
 477
 478 // return first preceding DOM position rendered at a different location, or "this"
 479 Position Position::previousCharacterPosition(EAffinity affinity) const
 480 {
 481     if (isNull())
 482         return Position();
 483
 484     Node* fromRootEditableElement = deprecatedNode()->rootEditableElement();
 485
 486     bool atStartOfLine = isStartOfLine(VisiblePosition(*this, affinity));
 487     bool rendered = isCandidate();
 488
 489     Position currentPos = *this;
 490     while (!currentPos.atStartOfTree()) {
 491         currentPos = currentPos.previous();
 492
 493         if (currentPos.deprecatedNode()->rootEditableElement() != fromRootEditableElement)
 494             return *this;
 495
 496         if (atStartOfLine || !rendered) {
 497             if (currentPos.isCandidate())
 498                 return currentPos;
 499         } else if (rendersInDifferentPosition(currentPos))
 500             return currentPos;
 501     }
 502
 503     return *this;
 504 }
 505
 506 // Whether or not [node, 0] and [node, lastOffsetForEditing(node)] are their own VisiblePositions.
 507 // If true, adjacent candidates are visually distinct.
 508 // FIXME: Disregard nodes with renderers that have no height, as we do in isCandidate.
 509 // FIXME: Share code with isCandidate, if possible.
 510 static bool endsOfNodeAreVisuallyDistinctPositions(Node* node)
 511 {
 512     if (!node || !node->renderer())
 513         return false;
 514
 515     if (!node->renderer()->isInline())
 516         return true;
 517
 518     // Don't include inline tables.
 519     if (isHTMLTableElement(*node))
 520         return false;
 521
 522     // A Marquee elements are moving so we should assume their ends are always
 523     // visibily distinct.
 524     if (isHTMLMarqueeElement(*node))
 525         return true;
 526
 527     // There is a VisiblePosition inside an empty inline-block container.
 528     return node->renderer()->isReplaced() && canHaveChildrenForEditing(node) && toRenderBox(node->renderer())->height() != 0 && !node->firstChild();
 529 }
 530
 531 static Node* enclosingVisualBoundary(Node* node)
 532 {
 533     while (node && !endsOfNodeAreVisuallyDistinctPositions(node))
 534         node = node->parentNode();
 535
 536     return node;
 537 }
 538
 539 // upstream() and downstream() want to return positions that are either in a
 540 // text node or at just before a non-text node.  This method checks for that.
 541 static bool isStreamer(const PositionIterator& pos)
 542 {
 543     if (!pos.node())
 544         return true;
 545
 546     if (isAtomicNode(pos.node()))
 547         return true;
 548
 549     return pos.atStartOfNode();
 550 }
 551
 552 // This function and downstream() are used for moving back and forth between visually equivalent candidates.
 553 // For example, for the text node "foo     bar" where whitespace is collapsible, there are two candidates
 554 // that map to the VisiblePosition between 'b' and the space.  This function will return the left candidate
 555 // and downstream() will return the right one.
 556 // Also, upstream() will return [boundary, 0] for any of the positions from [boundary, 0] to the first candidate
 557 // in boundary, where endsOfNodeAreVisuallyDistinctPositions(boundary) is true.
 558 Position Position::upstream(EditingBoundaryCrossingRule rule) const
 559 {
 560     Node* startNode = deprecatedNode();
 561     if (!startNode)
 562         return Position();
 563
 564     // iterate backward from there, looking for a qualified position
 565     Node* boundary = enclosingVisualBoundary(startNode);
 566     // FIXME: PositionIterator should respect Before and After positions.
 567     PositionIterator lastVisible = m_anchorType == PositionIsAfterAnchor ? createLegacyEditingPosition(m_anchorNode.get(), caretMaxOffset(m_anchorNode.get())) : *this;
 568     PositionIterator currentPos = lastVisible;
 569     bool startEditable = startNode->rendererIsEditable();
 570     Node* lastNode = startNode;
 571     bool boundaryCrossed = false;
 572     for (; !currentPos.atStart(); currentPos.decrement()) {
 573         Node* currentNode = currentPos.node();
 574
 575         // Don't check for an editability change if we haven't moved to a different node,
 576         // to avoid the expense of computing rendererIsEditable().
 577         if (currentNode != lastNode) {
 578             // Don't change editability.
 579             bool currentEditable = currentNode->rendererIsEditable();
 580             if (startEditable != currentEditable) {
 581                 if (rule == CannotCrossEditingBoundary)
 582                     break;
 583                 boundaryCrossed = true;
 584             }
 585             lastNode = currentNode;
 586         }
 587
 588         // If we've moved to a position that is visually distinct, return the last saved position. There
 589         // is code below that terminates early if we're *about* to move to a visually distinct position.
 590         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentNode != boundary)
 591             return lastVisible;
 592
 593         // skip position in unrendered or invisible node
 594         RenderObject* renderer = currentNode->renderer();
 595         if (!renderer || renderer->style()->visibility() != VISIBLE)
 596             continue;
 597
 598         if (rule == CanCrossEditingBoundary && boundaryCrossed) {
 599             lastVisible = currentPos;
 600             break;
 601         }
 602
 603         // track last visible streamer position
 604         if (isStreamer(currentPos))
 605             lastVisible = currentPos;
 606
 607         // Don't move past a position that is visually distinct.  We could rely on code above to terminate and
 608         // return lastVisible on the next iteration, but we terminate early to avoid doing a nodeIndex() call.
 609         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentPos.atStartOfNode())
 610             return lastVisible;
 611
 612         // Return position after tables and nodes which have content that can be ignored.
 613         if (editingIgnoresContent(currentNode) || isRenderedTableElement(currentNode)) {
 614             if (currentPos.atEndOfNode())
 615                 return positionAfterNode(currentNode);
 616             continue;
 617         }
 618
 619         // return current position if it is in rendered text
 620         if (renderer->isText() && toRenderText(renderer)->firstTextBox()) {
 621             if (currentNode != startNode) {
 622                 // This assertion fires in layout tests in the case-transform.html test because
 623                 // of a mix-up between offsets in the text in the DOM tree with text in the
 624                 // render tree which can have a different length due to case transformation.
 625                 // Until we resolve that, disable this so we can run the layout tests!
 626                 //ASSERT(currentOffset >= renderer->caretMaxOffset());
 627                 return createLegacyEditingPosition(currentNode, renderer->caretMaxOffset());
 628             }
 629
 630             unsigned textOffset = currentPos.offsetInLeafNode();
 631             RenderText* textRenderer = toRenderText(renderer);
 632             InlineTextBox* lastTextBox = textRenderer->lastTextBox();
 633             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 634                 if (textOffset <= box->start() + box->len()) {
 635                     if (textOffset > box->start())
 636                         return currentPos;
 637                     continue;
 638                 }
 639
 640                 if (box == lastTextBox || textOffset != box->start() + box->len() + 1)
 641                     continue;
 642
 643                 // The text continues on the next line only if the last text box is not on this line and
 644                 // none of the boxes on this line have a larger start offset.
 645
 646                 bool continuesOnNextLine = true;
 647                 InlineBox* otherBox = box;
 648                 while (continuesOnNextLine) {
 649                     otherBox = otherBox->nextLeafChild();
 650                     if (!otherBox)
 651                         break;
 652                     if (otherBox == lastTextBox || (otherBox->renderer() == textRenderer && toInlineTextBox(otherBox)->start() > textOffset))
 653                         continuesOnNextLine = false;
 654                 }
 655
 656                 otherBox = box;
 657                 while (continuesOnNextLine) {
 658                     otherBox = otherBox->prevLeafChild();
 659                     if (!otherBox)
 660                         break;
 661                     if (otherBox == lastTextBox || (otherBox->renderer() == textRenderer && toInlineTextBox(otherBox)->start() > textOffset))
 662                         continuesOnNextLine = false;
 663                 }
 664
 665                 if (continuesOnNextLine)
 666                     return currentPos;
 667             }
 668         }
 669     }
 670
 671     return lastVisible;
 672 }
 673
 674 // This function and upstream() are used for moving back and forth between visually equivalent candidates.
 675 // For example, for the text node "foo     bar" where whitespace is collapsible, there are two candidates
 676 // that map to the VisiblePosition between 'b' and the space.  This function will return the right candidate
 677 // and upstream() will return the left one.
 678 // Also, downstream() will return the last position in the last atomic node in boundary for all of the positions
 679 // in boundary after the last candidate, where endsOfNodeAreVisuallyDistinctPositions(boundary).
 680 // FIXME: This function should never be called when the line box tree is dirty. See https://bugs.webkit.org/show_bug.cgi?id=97264
 681 Position Position::downstream(EditingBoundaryCrossingRule rule) const
 682 {
 683     Node* startNode = deprecatedNode();
 684     if (!startNode)
 685         return Position();
 686
 687     // iterate forward from there, looking for a qualified position
 688     Node* boundary = enclosingVisualBoundary(startNode);
 689     // FIXME: PositionIterator should respect Before and After positions.
 690     PositionIterator lastVisible = m_anchorType == PositionIsAfterAnchor ? createLegacyEditingPosition(m_anchorNode.get(), caretMaxOffset(m_anchorNode.get())) : *this;
 691     PositionIterator currentPos = lastVisible;
 692     bool startEditable = startNode->rendererIsEditable();
 693     Node* lastNode = startNode;
 694     bool boundaryCrossed = false;
 695     for (; !currentPos.atEnd(); currentPos.increment()) {
 696         Node* currentNode = currentPos.node();
 697
 698         // Don't check for an editability change if we haven't moved to a different node,
 699         // to avoid the expense of computing rendererIsEditable().
 700         if (currentNode != lastNode) {
 701             // Don't change editability.
 702             bool currentEditable = currentNode->rendererIsEditable();
 703             if (startEditable != currentEditable) {
 704                 if (rule == CannotCrossEditingBoundary)
 705                     break;
 706                 boundaryCrossed = true;
 707             }
 708
 709             lastNode = currentNode;
 710         }
 711
 712         // stop before going above the body, up into the head
 713         // return the last visible streamer position
 714         if (isHTMLBodyElement(*currentNode) && currentPos.atEndOfNode())
 715             break;
 716
 717         // Do not move to a visually distinct position.
 718         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentNode != boundary)
 719             return lastVisible;
 720         // Do not move past a visually disinct position.
 721         // Note: The first position after the last in a node whose ends are visually distinct
 722         // positions will be [boundary->parentNode(), originalBlock->nodeIndex() + 1].
 723         if (boundary && boundary->parentNode() == currentNode)
 724             return lastVisible;
 725
 726         // skip position in unrendered or invisible node
 727         RenderObject* renderer = currentNode->renderer();
 728         if (!renderer || renderer->style()->visibility() != VISIBLE)
 729             continue;
 730
 731         if (rule == CanCrossEditingBoundary && boundaryCrossed) {
 732             lastVisible = currentPos;
 733             break;
 734         }
 735
 736         // track last visible streamer position
 737         if (isStreamer(currentPos))
 738             lastVisible = currentPos;
 739
 740         // Return position before tables and nodes which have content that can be ignored.
 741         if (editingIgnoresContent(currentNode) || isRenderedTableElement(currentNode)) {
 742             if (currentPos.offsetInLeafNode() <= renderer->caretMinOffset())
 743                 return createLegacyEditingPosition(currentNode, renderer->caretMinOffset());
 744             continue;
 745         }
 746
 747         // return current position if it is in rendered text
 748         if (renderer->isText() && toRenderText(renderer)->firstTextBox()) {
 749             if (currentNode != startNode) {
 750                 ASSERT(currentPos.atStartOfNode());
 751                 return createLegacyEditingPosition(currentNode, renderer->caretMinOffset());
 752             }
 753
 754             unsigned textOffset = currentPos.offsetInLeafNode();
 755             RenderText* textRenderer = toRenderText(renderer);
 756             InlineTextBox* lastTextBox = textRenderer->lastTextBox();
 757             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 758                 if (textOffset <= box->end()) {
 759                     if (textOffset >= box->start())
 760                         return currentPos;
 761                     continue;
 762                 }
 763
 764                 if (box == lastTextBox || textOffset != box->start() + box->len())
 765                     continue;
 766
 767                 // The text continues on the next line only if the last text box is not on this line and
 768                 // none of the boxes on this line have a larger start offset.
 769
 770                 bool continuesOnNextLine = true;
 771                 InlineBox* otherBox = box;
 772                 while (continuesOnNextLine) {
 773                     otherBox = otherBox->nextLeafChild();
 774                     if (!otherBox)
 775                         break;
 776                     if (otherBox == lastTextBox || (otherBox->renderer() == textRenderer && toInlineTextBox(otherBox)->start() >= textOffset))
 777                         continuesOnNextLine = false;
 778                 }
 779
 780                 otherBox = box;
 781                 while (continuesOnNextLine) {
 782                     otherBox = otherBox->prevLeafChild();
 783                     if (!otherBox)
 784                         break;
 785                     if (otherBox == lastTextBox || (otherBox->renderer() == textRenderer && toInlineTextBox(otherBox)->start() >= textOffset))
 786                         continuesOnNextLine = false;
 787                 }
 788
 789                 if (continuesOnNextLine)
 790                     return currentPos;
 791             }
 792         }
 793     }
 794
 795     return lastVisible;
 796 }
 797
 798 static int boundingBoxLogicalHeight(RenderObject *o, const IntRect &rect)
 799 {
 800     return o->style()->isHorizontalWritingMode() ? rect.height() : rect.width();
 801 }
 802
 803 bool Position::hasRenderedNonAnonymousDescendantsWithHeight(RenderObject* renderer)
 804 {
 805     RenderObject* stop = renderer->nextInPreOrderAfterChildren();
 806     for (RenderObject *o = renderer->slowFirstChild(); o && o != stop; o = o->nextInPreOrder())
 807         if (o->nonPseudoNode()) {
 808             if ((o->isText() && boundingBoxLogicalHeight(o, toRenderText(o)->linesBoundingBox()))
 809                 || (o->isBox() && toRenderBox(o)->pixelSnappedLogicalHeight())
 810                 || (o->isRenderInline() && isEmptyInline(o) && boundingBoxLogicalHeight(o, toRenderInline(o)->linesBoundingBox())))
 811                 return true;
 812         }
 813     return false;
 814 }
 815
 816 bool Position::nodeIsUserSelectNone(Node* node)
 817 {
 818     return node && node->renderer() && !node->renderer()->isSelectable();
 819 }
 820
 821 bool Position::nodeIsUserSelectAll(const Node* node)
 822 {
 823     return RuntimeEnabledFeatures::userSelectAllEnabled() && node && node->renderer() && node->renderer()->style()->userSelect() == SELECT_ALL;
 824 }
 825
 826 Node* Position::rootUserSelectAllForNode(Node* node)
 827 {
 828     if (!node || !nodeIsUserSelectAll(node))
 829         return 0;
 830     Node* parent = node->parentNode();
 831     if (!parent)
 832         return node;
 833
 834     Node* candidateRoot = node;
 835     while (parent) {
 836         if (!parent->renderer()) {
 837             parent = parent->parentNode();
 838             continue;
 839         }
 840         if (!nodeIsUserSelectAll(parent))
 841             break;
 842         candidateRoot = parent;
 843         parent = candidateRoot->parentNode();
 844     }
 845     return candidateRoot;
 846 }
 847
 848 bool Position::isCandidate() const
 849 {
 850     if (isNull())
 851         return false;
 852
 853     RenderObject* renderer = deprecatedNode()->renderer();
 854     if (!renderer)
 855         return false;
 856
 857     if (renderer->style()->visibility() != VISIBLE)
 858         return false;
 859
 860     if (renderer->isBR())
 861         // FIXME: The condition should be m_anchorType == PositionIsBeforeAnchor, but for now we still need to support legacy positions.
 862         return !m_offset && m_anchorType != PositionIsAfterAnchor && !nodeIsUserSelectNone(deprecatedNode()->parentNode());
 863
 864     if (renderer->isText())
 865         return !nodeIsUserSelectNone(deprecatedNode()) && inRenderedText();
 866
 867     if (renderer->isSVG()) {
 868         // We don't consider SVG elements are contenteditable except for
 869         // associated renderer returns isText() true, e.g. RenderSVGInlineText.
 870         return false;
 871     }
 872
 873     if (isRenderedTableElement(deprecatedNode()) || editingIgnoresContent(deprecatedNode()))
 874         return (atFirstEditingPositionForNode() || atLastEditingPositionForNode()) && !nodeIsUserSelectNone(deprecatedNode()->parentNode());
 875
 876     if (isHTMLHtmlElement(*m_anchorNode))
 877         return false;
 878
 879     if (renderer->isRenderBlockFlow()) {
 880         if (toRenderBlock(renderer)->logicalHeight() || isHTMLBodyElement(*m_anchorNode)) {
 881             if (!Position::hasRenderedNonAnonymousDescendantsWithHeight(renderer))
 882                 return atFirstEditingPositionForNode() && !Position::nodeIsUserSelectNone(deprecatedNode());
 883             return m_anchorNode->rendererIsEditable() && !Position::nodeIsUserSelectNone(deprecatedNode()) && atEditingBoundary();
 884         }
 885     } else {
 886         LocalFrame* frame = m_anchorNode->document().frame();
 887         bool caretBrowsing = frame->settings() && frame->settings()->caretBrowsingEnabled();
 888         return (caretBrowsing || m_anchorNode->rendererIsEditable()) && !Position::nodeIsUserSelectNone(deprecatedNode()) && atEditingBoundary();
 889     }
 890
 891     return false;
 892 }
 893
 894 bool Position::inRenderedText() const
 895 {
 896     if (isNull() || !deprecatedNode()->isTextNode())
 897         return false;
 898
 899     RenderObject* renderer = deprecatedNode()->renderer();
 900     if (!renderer)
 901         return false;
 902
 903     RenderText *textRenderer = toRenderText(renderer);
 904     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 905         if (m_offset < static_cast<int>(box->start()) && !textRenderer->containsReversedText()) {
 906             // The offset we're looking for is before this node
 907             // this means the offset must be in content that is
 908             // not rendered. Return false.
 909             return false;
 910         }
 911         if (box->containsCaretOffset(m_offset))
 912             // Return false for offsets inside composed characters.
 913             return m_offset == 0 || m_offset == textRenderer->nextOffset(textRenderer->previousOffset(m_offset));
 914     }
 915
 916     return false;
 917 }
 918
 919 bool Position::isRenderedCharacter() const
 920 {
 921     if (isNull() || !deprecatedNode()->isTextNode())
 922         return false;
 923
 924     RenderObject* renderer = deprecatedNode()->renderer();
 925     if (!renderer)
 926         return false;
 927
 928     RenderText* textRenderer = toRenderText(renderer);
 929     for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 930         if (m_offset < static_cast<int>(box->start()) && !textRenderer->containsReversedText()) {
 931             // The offset we're looking for is before this node
 932             // this means the offset must be in content that is
 933             // not rendered. Return false.
 934             return false;
 935         }
 936         if (m_offset >= static_cast<int>(box->start()) && m_offset < static_cast<int>(box->start() + box->len()))
 937             return true;
 938     }
 939
 940     return false;
 941 }
 942
 943 bool Position::rendersInDifferentPosition(const Position &pos) const
 944 {
 945     if (isNull() || pos.isNull())
 946         return false;
 947
 948     RenderObject* renderer = deprecatedNode()->renderer();
 949     if (!renderer)
 950         return false;
 951
 952     RenderObject* posRenderer = pos.deprecatedNode()->renderer();
 953     if (!posRenderer)
 954         return false;
 955
 956     if (renderer->style()->visibility() != VISIBLE ||
 957         posRenderer->style()->visibility() != VISIBLE)
 958         return false;
 959
 960     if (deprecatedNode() == pos.deprecatedNode()) {
 961         if (isHTMLBRElement(*deprecatedNode()))
 962             return false;
 963
 964         if (m_offset == pos.deprecatedEditingOffset())
 965             return false;
 966
 967         if (!deprecatedNode()->isTextNode() && !pos.deprecatedNode()->isTextNode()) {
 968             if (m_offset != pos.deprecatedEditingOffset())
 969                 return true;
 970         }
 971     }
 972
 973     if (isHTMLBRElement(*deprecatedNode()) && pos.isCandidate())
 974         return true;
 975
 976     if (isHTMLBRElement(*pos.deprecatedNode()) && isCandidate())
 977         return true;
 978
 979     if (deprecatedNode()->enclosingBlockFlowElement() != pos.deprecatedNode()->enclosingBlockFlowElement())
 980         return true;
 981
 982     if (deprecatedNode()->isTextNode() && !inRenderedText())
 983         return false;
 984
 985     if (pos.deprecatedNode()->isTextNode() && !pos.inRenderedText())
 986         return false;
 987
 988     int thisRenderedOffset = renderedOffset();
 989     int posRenderedOffset = pos.renderedOffset();
 990
 991     if (renderer == posRenderer && thisRenderedOffset == posRenderedOffset)
 992         return false;
 993
 994     int ignoredCaretOffset;
 995     InlineBox* b1;
 996     getInlineBoxAndOffset(DOWNSTREAM, b1, ignoredCaretOffset);
 997     InlineBox* b2;
 998     pos.getInlineBoxAndOffset(DOWNSTREAM, b2, ignoredCaretOffset);
 999
1000     WTF_LOG(Editing, "renderer:               %p [%p]\n", renderer, b1);
1001     WTF_LOG(Editing, "thisRenderedOffset:         %d\n", thisRenderedOffset);
1002     WTF_LOG(Editing, "posRenderer:            %p [%p]\n", posRenderer, b2);
1003     WTF_LOG(Editing, "posRenderedOffset:      %d\n", posRenderedOffset);
1004     WTF_LOG(Editing, "node min/max:           %d:%d\n", caretMinOffset(deprecatedNode()), caretMaxOffset(deprecatedNode()));
1005     WTF_LOG(Editing, "pos node min/max:       %d:%d\n", caretMinOffset(pos.deprecatedNode()), caretMaxOffset(pos.deprecatedNode()));
1006     WTF_LOG(Editing, "----------------------------------------------------------------------\n");
1007
1008     if (!b1 || !b2) {
1009         return false;
1010     }
1011
1012     if (b1->root() != b2->root()) {
1013         return true;
1014     }
1015
1016     if (nextRenderedEditable(deprecatedNode()) == pos.deprecatedNode()
1017         && thisRenderedOffset == caretMaxOffset(deprecatedNode()) && !posRenderedOffset) {
1018         return false;
1019     }
1020
1021     if (previousRenderedEditable(deprecatedNode()) == pos.deprecatedNode()
1022         && !thisRenderedOffset && posRenderedOffset == caretMaxOffset(pos.deprecatedNode())) {
1023         return false;
1024     }
1025
1026     return true;
1027 }
1028
1029 // This assumes that it starts in editable content.
1030 Position Position::leadingWhitespacePosition(EAffinity affinity, bool considerNonCollapsibleWhitespace) const
1031 {
1032     ASSERT(isEditablePosition(*this, ContentIsEditable, DoNotUpdateStyle));
1033     if (isNull())
1034         return Position();
1035
1036     if (isHTMLBRElement(*upstream().deprecatedNode()))
1037         return Position();
1038
1039     Position prev = previousCharacterPosition(affinity);
1040     if (prev != *this && prev.deprecatedNode()->inSameContainingBlockFlowElement(deprecatedNode()) && prev.deprecatedNode()->isTextNode()) {
1041         String string = toText(prev.deprecatedNode())->data();
1042         UChar c = string[prev.deprecatedEditingOffset()];
1043         if (considerNonCollapsibleWhitespace ? (isSpaceOrNewline(c) || c == noBreakSpace) : isCollapsibleWhitespace(c))
1044             if (isEditablePosition(prev))
1045                 return prev;
1046     }
1047
1048     return Position();
1049 }
1050
1051 // This assumes that it starts in editable content.
1052 Position Position::trailingWhitespacePosition(EAffinity, bool considerNonCollapsibleWhitespace) const
1053 {
1054     ASSERT(isEditablePosition(*this, ContentIsEditable, DoNotUpdateStyle));
1055     if (isNull())
1056         return Position();
1057
1058     VisiblePosition v(*this);
1059     UChar c = v.characterAfter();
1060     // The space must not be in another paragraph and it must be editable.
1061     if (!isEndOfParagraph(v) && v.next(CannotCrossEditingBoundary).isNotNull())
1062         if (considerNonCollapsibleWhitespace ? (isSpaceOrNewline(c) || c == noBreakSpace) : isCollapsibleWhitespace(c))
1063             return *this;
1064
1065     return Position();
1066 }
1067
1068 void Position::getInlineBoxAndOffset(EAffinity affinity, InlineBox*& inlineBox, int& caretOffset) const
1069 {
1070     getInlineBoxAndOffset(affinity, primaryDirection(), inlineBox, caretOffset);
1071 }
1072
1073 static bool isNonTextLeafChild(RenderObject* object)
1074 {
1075     if (object->slowFirstChild())
1076         return false;
1077     if (object->isText())
1078         return false;
1079     return true;
1080 }
1081
1082 static InlineTextBox* searchAheadForBetterMatch(RenderObject* renderer)
1083 {
1084     RenderBlock* container = renderer->containingBlock();
1085     RenderObject* next = renderer;
1086     while ((next = next->nextInPreOrder(container))) {
1087         if (next->isRenderBlock())
1088             return 0;
1089         if (next->isBR())
1090             return 0;
1091         if (isNonTextLeafChild(next))
1092             return 0;
1093         if (next->isText()) {
1094             InlineTextBox* match = 0;
1095             int minOffset = INT_MAX;
1096             for (InlineTextBox* box = toRenderText(next)->firstTextBox(); box; box = box->nextTextBox()) {
1097                 int caretMinOffset = box->caretMinOffset();
1098                 if (caretMinOffset < minOffset) {
1099                     match = box;
1100                     minOffset = caretMinOffset;
1101                 }
1102             }
1103             if (match)
1104                 return match;
1105         }
1106     }
1107     return 0;
1108 }
1109
1110 static Position downstreamIgnoringEditingBoundaries(Position position)
1111 {
1112     Position lastPosition;
1113     while (position != lastPosition) {
1114         lastPosition = position;
1115         position = position.downstream(CanCrossEditingBoundary);
1116     }
1117     return position;
1118 }
1119
1120 static Position upstreamIgnoringEditingBoundaries(Position position)
1121 {
1122     Position lastPosition;
1123     while (position != lastPosition) {
1124         lastPosition = position;
1125         position = position.upstream(CanCrossEditingBoundary);
1126     }
1127     return position;
1128 }
1129
1130 void Position::getInlineBoxAndOffset(EAffinity affinity, TextDirection primaryDirection, InlineBox*& inlineBox, int& caretOffset) const
1131 {
1132     caretOffset = deprecatedEditingOffset();
1133     RenderObject* renderer = deprecatedNode()->renderer();
1134
1135     if (!renderer->isText()) {
1136         inlineBox = 0;
1137         if (canHaveChildrenForEditing(deprecatedNode()) && renderer->isRenderBlockFlow() && hasRenderedNonAnonymousDescendantsWithHeight(renderer)) {
1138             // Try a visually equivalent position with possibly opposite editability. This helps in case |this| is in
1139             // an editable block but surrounded by non-editable positions. It acts to negate the logic at the beginning
1140             // of RenderObject::createVisiblePosition().
1141             Position equivalent = downstreamIgnoringEditingBoundaries(*this);
1142             if (equivalent == *this) {
1143                 equivalent = upstreamIgnoringEditingBoundaries(*this);
1144                 if (equivalent == *this || downstreamIgnoringEditingBoundaries(equivalent) == *this)
1145                     return;
1146             }
1147
1148             equivalent.getInlineBoxAndOffset(UPSTREAM, primaryDirection, inlineBox, caretOffset);
1149             return;
1150         }
1151         if (renderer->isBox()) {
1152             inlineBox = toRenderBox(renderer)->inlineBoxWrapper();
1153             if (!inlineBox || (caretOffset > inlineBox->caretMinOffset() && caretOffset < inlineBox->caretMaxOffset()))
1154                 return;
1155         }
1156     } else {
1157         RenderText* textRenderer = toRenderText(renderer);
1158
1159         InlineTextBox* box;
1160         InlineTextBox* candidate = 0;
1161
1162         for (box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
1163             int caretMinOffset = box->caretMinOffset();
1164             int caretMaxOffset = box->caretMaxOffset();
1165
1166             if (caretOffset < caretMinOffset || caretOffset > caretMaxOffset || (caretOffset == caretMaxOffset && box->isLineBreak()))
1167                 continue;
1168
1169             if (caretOffset > caretMinOffset && caretOffset < caretMaxOffset) {
1170                 inlineBox = box;
1171                 return;
1172             }
1173
1174             if (((caretOffset == caretMaxOffset) ^ (affinity == DOWNSTREAM))
1175                 || ((caretOffset == caretMinOffset) ^ (affinity == UPSTREAM))
1176                 || (caretOffset == caretMaxOffset && box->nextLeafChild() && box->nextLeafChild()->isLineBreak()))
1177                 break;
1178
1179             candidate = box;
1180         }
1181         if (candidate && candidate == textRenderer->lastTextBox() && affinity == DOWNSTREAM) {
1182             box = searchAheadForBetterMatch(textRenderer);
1183             if (box)
1184                 caretOffset = box->caretMinOffset();
1185         }
1186         inlineBox = box ? box : candidate;
1187     }
1188
1189     if (!inlineBox)
1190         return;
1191
1192     unsigned char level = inlineBox->bidiLevel();
1193
1194     if (inlineBox->direction() == primaryDirection) {
1195         if (caretOffset == inlineBox->caretRightmostOffset()) {
1196             InlineBox* nextBox = inlineBox->nextLeafChild();
1197             if (!nextBox || nextBox->bidiLevel() >= level)
1198                 return;
1199
1200             level = nextBox->bidiLevel();
1201             InlineBox* prevBox = inlineBox;
1202             do {
1203                 prevBox = prevBox->prevLeafChild();
1204             } while (prevBox && prevBox->bidiLevel() > level);
1205
1206             if (prevBox && prevBox->bidiLevel() == level)   // For example, abc FED 123 ^ CBA
1207                 return;
1208
1209             // For example, abc 123 ^ CBA
1210             while (InlineBox* nextBox = inlineBox->nextLeafChild()) {
1211                 if (nextBox->bidiLevel() < level)
1212                     break;
1213                 inlineBox = nextBox;
1214             }
1215             caretOffset = inlineBox->caretRightmostOffset();
1216         } else {
1217             InlineBox* prevBox = inlineBox->prevLeafChild();
1218             if (!prevBox || prevBox->bidiLevel() >= level)
1219                 return;
1220
1221             level = prevBox->bidiLevel();
1222             InlineBox* nextBox = inlineBox;
1223             do {
1224                 nextBox = nextBox->nextLeafChild();
1225             } while (nextBox && nextBox->bidiLevel() > level);
1226
1227             if (nextBox && nextBox->bidiLevel() == level)
1228                 return;
1229
1230             while (InlineBox* prevBox = inlineBox->prevLeafChild()) {
1231                 if (prevBox->bidiLevel() < level)
1232                     break;
1233                 inlineBox = prevBox;
1234             }
1235             caretOffset = inlineBox->caretLeftmostOffset();
1236         }
1237         return;
1238     }
1239
1240     if (caretOffset == inlineBox->caretLeftmostOffset()) {
1241         InlineBox* prevBox = inlineBox->prevLeafChildIgnoringLineBreak();
1242         if (!prevBox || prevBox->bidiLevel() < level) {
1243             // Left edge of a secondary run. Set to the right edge of the entire run.
1244             while (InlineBox* nextBox = inlineBox->nextLeafChildIgnoringLineBreak()) {
1245                 if (nextBox->bidiLevel() < level)
1246                     break;
1247                 inlineBox = nextBox;
1248             }
1249             caretOffset = inlineBox->caretRightmostOffset();
1250         } else if (prevBox->bidiLevel() > level) {
1251             // Right edge of a "tertiary" run. Set to the left edge of that run.
1252             while (InlineBox* tertiaryBox = inlineBox->prevLeafChildIgnoringLineBreak()) {
1253                 if (tertiaryBox->bidiLevel() <= level)
1254                     break;
1255                 inlineBox = tertiaryBox;
1256             }
1257             caretOffset = inlineBox->caretLeftmostOffset();
1258         }
1259     } else {
1260         InlineBox* nextBox = inlineBox->nextLeafChildIgnoringLineBreak();
1261         if (!nextBox || nextBox->bidiLevel() < level) {
1262             // Right edge of a secondary run. Set to the left edge of the entire run.
1263             while (InlineBox* prevBox = inlineBox->prevLeafChildIgnoringLineBreak()) {
1264                 if (prevBox->bidiLevel() < level)
1265                     break;
1266                 inlineBox = prevBox;
1267             }
1268             if (m_anchorNode->selfOrAncestorHasDirAutoAttribute())
1269                 caretOffset = inlineBox->bidiLevel() < level ? inlineBox->caretLeftmostOffset() : inlineBox->caretRightmostOffset();
1270             else
1271                 caretOffset = inlineBox->caretLeftmostOffset();
1272         } else if (nextBox->bidiLevel() > level) {
1273             // Left edge of a "tertiary" run. Set to the right edge of that run.
1274             while (InlineBox* tertiaryBox = inlineBox->nextLeafChildIgnoringLineBreak()) {
1275                 if (tertiaryBox->bidiLevel() <= level)
1276                     break;
1277                 inlineBox = tertiaryBox;
1278             }
1279             caretOffset = inlineBox->caretRightmostOffset();
1280         }
1281     }
1282 }
1283
1284 TextDirection Position::primaryDirection() const
1285 {
1286     TextDirection primaryDirection = LTR;
1287     for (const RenderObject* r = m_anchorNode->renderer(); r; r = r->parent()) {
1288         if (r->isRenderBlockFlow()) {
1289             primaryDirection = r->style()->direction();
1290             break;
1291         }
1292     }
1293
1294     return primaryDirection;
1295 }
1296
1297 void Position::trace(Visitor* visitor)
1298 {
1299     visitor->trace(m_anchorNode);
1300 }
1301
1302 void Position::debugPosition(const char* msg) const
1303 {
1304     if (isNull())
1305         fprintf(stderr, "Position [%s]: null\n", msg);
1306     else
1307         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, deprecatedNode()->nodeName().utf8().data(), deprecatedNode(), m_offset);
1308 }
1309
1310 #ifndef NDEBUG
1311
1312 void Position::formatForDebugger(char* buffer, unsigned length) const
1313 {
1314     StringBuilder result;
1315
1316     if (isNull())
1317         result.appendLiteral("<null>");
1318     else {
1319         char s[1024];
1320         result.appendLiteral("offset ");
1321         result.appendNumber(m_offset);
1322         result.appendLiteral(" of ");
1323         deprecatedNode()->formatForDebugger(s, sizeof(s));
1324         result.append(s);
1325     }
1326
1327     strncpy(buffer, result.toString().utf8().data(), length - 1);
1328 }
1329
1330 void Position::showAnchorTypeAndOffset() const
1331 {
1332     if (m_isLegacyEditingPosition)
1333         fputs("legacy, ", stderr);
1334     switch (anchorType()) {
1335     case PositionIsOffsetInAnchor:
1336         fputs("offset", stderr);
1337         break;
1338     case PositionIsBeforeChildren:
1339         fputs("beforeChildren", stderr);
1340         break;
1341     case PositionIsAfterChildren:
1342         fputs("afterChildren", stderr);
1343         break;
1344     case PositionIsBeforeAnchor:
1345         fputs("before", stderr);
1346         break;
1347     case PositionIsAfterAnchor:
1348         fputs("after", stderr);
1349         break;
1350     }
1351     fprintf(stderr, ", offset:%d\n", m_offset);
1352 }
1353
1354 void Position::showTreeForThis() const
1355 {
1356     if (anchorNode()) {
1357         anchorNode()->showTreeForThis();
1358         showAnchorTypeAndOffset();
1359     }
1360 }
1361
1362 #endif
1363
1364
1365
1366 } // namespace WebCore
1367
1368 #ifndef NDEBUG
1369
1370 void showTree(const WebCore::Position& pos)
1371 {
1372     pos.showTreeForThis();
1373 }
1374
1375 void showTree(const WebCore::Position* pos)
1376 {
1377     if (pos)
1378         pos->showTreeForThis();
1379 }
1380
1381 #endif