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