2016-03-02T18:53:01 LayoutPosition

third_party/WebKit/Source/core/editing/VisibleUnits.cpp

Index: third_party/WebKit/Source/core/editing/VisibleUnits.cpp
diff --git a/third_party/WebKit/Source/core/editing/VisibleUnits.cpp b/third_party/WebKit/Source/core/editing/VisibleUnits.cpp
index 5e86228f48fb302db78e693bf466c40359ae267e..b1d28e446cd60ea3c0c3962deb4ceeb411bf4f8d 100644
--- a/third_party/WebKit/Source/core/editing/VisibleUnits.cpp
+++ b/third_party/WebKit/Source/core/editing/VisibleUnits.cpp
@@ -33,6 +33,7 @@
 #include "core/dom/Text.h"
 #include "core/editing/EditingUtilities.h"
 #include "core/editing/FrameSelection.h"
+#include "core/editing/LayoutPosition.h"
 #include "core/editing/Position.h"
 #include "core/editing/PositionIterator.h"
 #include "core/editing/RenderedPosition.h"
@@ -74,7 +75,7 @@ static PositionType canonicalizeCandidate(const PositionType& candidate)
 {
     if (candidate.isNull())
         return PositionType();
-    DCHECK(isVisuallyEquivalentCandidate(candidate));
+    ASSERT(isVisuallyEquivalentCandidate(candidate));
     PositionType upstream = mostBackwardCaretPosition(candidate);
     if (isVisuallyEquivalentCandidate(upstream))
         return upstream;
@@ -104,7 +105,7 @@ static PositionType canonicalPosition(const PositionType& passedPosition)
     if (position.isNull())
         return PositionType();
 
-    DCHECK(position.document());
+    ASSERT(position.document());
     position.document()->updateLayoutIgnorePendingStylesheets();
 
     Node* node = position.computeContainerNode();
@@ -159,14 +160,278 @@ static PositionType canonicalPosition(const PositionType& passedPosition)
     return next;
 }
 
+template <typename Strategy>
+struct BackwardMovement {
+    using PositionType = PositionTemplate<Strategy>;
+
+    static LayoutPosition advance(const LayoutPosition& position)
+    {
+        return previousPositionOf(position);
+    }
+
+    // TODO(yosin): |previousPositionOf()| should be implemented as
+    // |BackwardMovement::advance()|.
+    static PositionTemplate<Strategy> advance(const PositionTemplate<Strategy>& position)
+    {
+        ASSERT(position.isNotNull());
+        Node* const anchorNode = position.anchorNode();
+        switch (position.anchorType()) {
+        case PositionAnchorType::AfterAnchor:
+            if (anchorNode->isTextNode())
+                return advance(PositionTemplate<Strategy>(anchorNode, toText(anchorNode)->length()));
+        // fallthrough
+        case PositionAnchorType::AfterChildren:
+            if (Node* lastChild = Strategy::lastChild(*anchorNode))
+                return PositionTemplate<Strategy>::afterNode(lastChild);
+            return PositionTemplate<Strategy>::beforeNode(anchorNode);
+        case PositionAnchorType::BeforeAnchor: {
+            Node* const previous = Strategy::previous(*anchorNode);
+            if (!previous || previous->isDocumentNode())
+                return PositionTemplate<Strategy>();
+            if (previous == Strategy::parent(*anchorNode))
+                return PositionTemplate<Strategy>::beforeNode(previous);
+            return PositionTemplate<Strategy>::afterNode(previous);
+        }
+        case PositionAnchorType::BeforeChildren:
+            return PositionTemplate<Strategy>::beforeNode(anchorNode);
+        case PositionAnchorType::OffsetInAnchor: {
+            const int offsetInAnchor = position.offsetInContainerNode();
+            if (anchorNode->isTextNode()) {
+                if (offsetInAnchor > 0) {
+                    // TODO(yosin): Should we check Unicode surrogate pair?
+                    return PositionTemplate<Strategy>(anchorNode, offsetInAnchor - 1);
+                }
+                return advance(PositionTemplate<Strategy>::beforeNode(anchorNode));
+            }
+            if (Node* child = Strategy::childAt(*anchorNode, offsetInAnchor))
+                return advance(PositionTemplate<Strategy>::beforeNode(child));
+            if (Node* lastChild = Strategy::lastChild(*anchorNode))
+                return advance(PositionTemplate<Strategy>::afterNode(lastChild));
+            if (anchorNode->isDocumentNode())
+                return PositionTemplate<Strategy>();
+            return PositionTemplate<Strategy>::beforeNode(anchorNode);
+        }
+        }
+        NOTREACHED() << position.anchorType();
+        return PositionTemplate<Strategy>();
+    }
+};
+
+template <typename Strategy>
+struct ForwardMovement {
+    using PositionType = PositionTemplate<Strategy>;
+
+    static LayoutPosition advance(const LayoutPosition& position)
+    {
+        return nextPositionOf(position);
+    }
+
+    // TODO(yosin): |nextPositionOf()| should be implemented as
+    // |ForwardMovement::advance()|.
+    static PositionTemplate<Strategy> advance(const PositionTemplate<Strategy>& position)
+    {
+        ASSERT(position.isNotNull());
+        Node* const anchorNode = position.anchorNode();
+        switch (position.anchorType()) {
+        case PositionAnchorType::AfterAnchor:
+        case PositionAnchorType::AfterChildren:
+            if (Node* nextNode = Strategy::nextSkippingChildren(*anchorNode))
+                return PositionTemplate<Strategy>::beforeNode(nextNode);
+            return PositionTemplate<Strategy>();
+        case PositionAnchorType::BeforeAnchor:
+            if (anchorNode->isTextNode())
+                return PositionTemplate<Strategy>(anchorNode, 0);
+        // fallthrough
+        case PositionAnchorType::BeforeChildren:
+            if (Node* nextNode = Strategy::next(*anchorNode))
+                return PositionTemplate<Strategy>::beforeNode(nextNode);
+            return PositionTemplate<Strategy>();
+        case PositionAnchorType::OffsetInAnchor: {
+            const int offsetInAnchor = position.offsetInContainerNode();
+            if (anchorNode->isTextNode()) {
+                if (offsetInAnchor < static_cast<int>(toText(anchorNode)->length())) {
+                    // TODO(yosin): Should we check Unicode surrogate pair?
+                    return PositionTemplate<Strategy>(anchorNode, offsetInAnchor + 1);
+                }
+                return advance(PositionTemplate<Strategy>::afterNode(anchorNode));
+            }
+            if (Node* child = Strategy::childAt(*anchorNode, offsetInAnchor)) {
+                if (child->isTextNode())
+                    return advance(PositionTemplate<Strategy>(child, 0));
+                return advance(PositionTemplate<Strategy>::beforeNode(child));
+            }
+            if (Node* lastChild = Strategy::lastChild(*anchorNode))
+                return advance(PositionTemplate<Strategy>::afterNode(lastChild));
+            if (anchorNode->isDocumentNode())
+                return PositionTemplate<Strategy>();
+            return PositionTemplate<Strategy>::afterNode(anchorNode);
+        }
+        }
+        NOTREACHED() << position.anchorType();
+        return PositionTemplate<Strategy>();
+    }
+};
+
+// |Direction| is specified tree traversal direction. There are
+//  - |BackwardMovement<Strategy>|
+//  - |ForwardMovement<Strategy>|
+//  for backward/forward with DOM tree/flat tree traversal.
+//
+// |Rule| corresponds to |enum EditingBoundaryCrossingRule|.
+// There are:
+//  - |CanCrossEditingBoundaryRule|,
+//  - |CannotCrossEditingBoundaryRule|
+//  - |CanSkipOverEditingBoundary|
+template <typename Direction, typename Rule>
+class CaretPositionFinder final {
+    STATIC_ONLY(CaretPositionFinder);
+
+public:
+    using PositionType = typename Direction::PositionType;
+
+    static LayoutPosition find(const PositionType&);
+
+private:
+    static LayoutPosition advance(const LayoutPosition& position)
+    {
+        return Direction::advance(position);
+    }
+
+    static PositionType advance(const PositionType& position)
+    {
+        return Direction::advance(position);
+    }
+    static LayoutPosition findStart(const PositionType&);
+    static LayoutPosition locate(const LayoutPosition&);
+};
+
+template <typename Direction, typename Rule>
+LayoutPosition CaretPositionFinder<Direction, Rule>::find(const PositionType& position)
+{
+    DCHECK(position.isNotNull());
+    const LayoutPosition& start = findStart(position);
+    if (start.isNull())
+        return LayoutPosition();
+    LayoutPosition candidate = locate(start);
+    if (candidate.isNull())
+        return LayoutPosition();
+    Rule rule(candidate);
+    for (LayoutPosition runner = advance(candidate); runner.isNotNull(); runner = advance(runner)) {
+        if (!runner.canBePosition())
+            continue;
+        if (!rule.satisfies(runner))
+            return candidate;
+        if (!candidate.isCaretEquivalent(runner))
+            return candidate;
+        candidate = runner;
+    }
+    return candidate;
+}
+
+template <typename Direction, typename Rule>
+LayoutPosition CaretPositionFinder<Direction, Rule>::findStart(const PositionType& position)
+{
+    Rule rule(position);
+    for (PositionType runner = position; runner.isNotNull(); runner = advance(runner)) {
+        const LayoutPosition& layoutPosition = LayoutPosition::create(runner);
+        if (!layoutPosition.canBePosition())
+            continue;
+        if (!rule.satisfies(runner))
+            return LayoutPosition();
+        if (layoutPosition.isNotNull())
+            return layoutPosition;
+    }
+    return LayoutPosition();
+}
+
+template <typename Direction, typename Rule>
+LayoutPosition CaretPositionFinder<Direction, Rule>::locate(const LayoutPosition& position)
+{
+    DCHECK(position.isNotNull());
+    Rule rule(position);
+    for (LayoutPosition runner = position; runner.isNotNull(); runner = advance(runner)) {
+        if (!runner.canBePosition())
+            continue;
+        if (!rule.satisfies(runner))
+            return LayoutPosition();
+        if (runner.canPlaceCaret())
+            return runner;
+    }
+    return LayoutPosition();
+}
+
+template <typename Strategy>
+class CannotCrossEditingBoundaryRule final {
+    WTF_MAKE_NONCOPYABLE(CannotCrossEditingBoundaryRule);
+    STACK_ALLOCATED();
+
+public:
+    explicit CannotCrossEditingBoundaryRule(const LayoutPosition& position)
+        : CannotCrossEditingBoundaryRule(position.toPosition(PositionTemplate<Strategy>()))
+    {
+    }
+
+    explicit CannotCrossEditingBoundaryRule(const PositionTemplate<Strategy>& position)
+        : m_rootEditableElement(rootEditableElementOf(position))
+    {
+    }
+
+    bool satisfies(const PositionTemplate<Strategy>& position) const
+    {
+        return m_rootEditableElement == rootEditableElementOf(position);
+    }
+
+    bool satisfies(const LayoutPosition& position) const
+    {
+        return satisfies(position.toPosition(PositionTemplate<Strategy>()));
+    }
+
+private:
+    Element* const m_rootEditableElement;
+};
+
+template <typename Strategy>
+static PositionTemplate<Strategy> caretPositionOfTemplate(const PositionTemplate<Strategy>& position)
+{
+    if (position.isNull())
+        return PositionTemplate<Strategy>();
+    position.document()->updateLayoutIgnorePendingStylesheets();
+    const auto& backwardCandidate = CaretPositionFinder<BackwardMovement<Strategy>, CannotCrossEditingBoundaryRule<Strategy>>::find(position);
+    if (backwardCandidate.isNotNull())
+        return backwardCandidate.toPosition(PositionTemplate<Strategy>());
+    const auto& forwardCandidate = CaretPositionFinder<ForwardMovement<Strategy>, CannotCrossEditingBoundaryRule<Strategy>>::find(position);
+    // |forwardCandidate| can be null if |position| in uneditable and parent
+    // is editable, e.g.
+    // <div contentEditable><span contentEditable=false>|</span></div>
+    return forwardCandidate.toPosition(PositionTemplate<Strategy>());
+}
+
+Position caretPositionOf(const Position& position)
+{
+    return caretPositionOfTemplate<EditingStrategy>(position);
+}
+
+PositionInFlatTree caretPositionOf(const PositionInFlatTree& position)
+{
+    return caretPositionOfTemplate<EditingInFlatTreeStrategy>(position);
+}
+
 Position canonicalPositionOf(const Position& position)
 {
-    return canonicalPosition(position);
+#if 0
+    const auto& expected = canonicalPosition(position);
+#endif
+    const auto& actual = caretPositionOf(position);
+    return actual;
 }
 
 PositionInFlatTree canonicalPositionOf(const PositionInFlatTree& position)
 {
-    return canonicalPosition(position);
+#if 0
+    const auto& expected = canonicalPosition(position);
+#endif
+    const auto& actual = caretPositionOf(position);
+    return actual;
 }
 
 template <typename Strategy>
@@ -726,7 +991,7 @@ static VisiblePositionTemplate<Strategy> previousBoundary(const VisiblePositionT
         // what's available.
         // TODO(xiaochengh): Do we have to search the whole string?
         next = searchFunction(string.data(), string.size(), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);
-        DCHECK(!needMoreContext);
+        ASSERT(!needMoreContext);
     }
 
     if (!next)
@@ -820,7 +1085,7 @@ static VisiblePositionTemplate<Strategy> nextBoundary(const VisiblePositionTempl
         // available.
         // TODO(xiaochengh): Do we still have to search the whole string?
         next = searchFunction(string.data(), string.size(), prefixLength, DontHaveMoreContext, needMoreContext);
-        DCHECK(!needMoreContext);
+        ASSERT(!needMoreContext);
     }
 
     if (it.atEnd() && next == string.size()) {
@@ -856,7 +1121,7 @@ static VisiblePositionTemplate<Strategy> nextBoundary(const VisiblePositionTempl
 static unsigned startWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 {
     TRACE_EVENT0("blink", "startWordBoundary");
-    DCHECK(offset);
+    ASSERT(offset);
     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(characters, offset)) {
         needMoreContext = true;
         return 0;
@@ -898,7 +1163,7 @@ VisiblePositionInFlatTree startOfWord(const VisiblePositionInFlatTree& c, EWordS
 
 static unsigned endWordBoundary(const UChar* characters, unsigned length, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
 {
-    DCHECK_LE(offset, length);
+    ASSERT(offset <= length);
     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(characters + offset, length - offset) == static_cast<int>(length - offset)) {
         needMoreContext = true;
         return length;
@@ -1286,7 +1551,7 @@ bool isLogicalEndOfLine(const VisiblePositionInFlatTree& p)
 
 static inline LayoutPoint absoluteLineDirectionPointToLocalPointInBlock(RootInlineBox* root, LayoutUnit lineDirectionPoint)
 {
-    DCHECK(root);
+    ASSERT(root);
     LineLayoutBlockFlow containingBlock = root->block();
     FloatPoint absoluteBlockPoint = containingBlock.localToAbsolute(FloatPoint());
     if (containingBlock.hasOverflowClip())
@@ -2220,13 +2485,13 @@ VisiblePosition visiblePositionForContentsPoint(const IntPoint& contentsPoint, L
 //  "(1)" are first-letter part and "ab" are remaining part.
 LayoutObject* associatedLayoutObjectOf(const Node& node, int offsetInNode)
 {
-    DCHECK_GE(offsetInNode, 0);
+    ASSERT(offsetInNode >= 0);
     LayoutObject* layoutObject = node.layoutObject();
     if (!node.isTextNode() || !layoutObject || !toLayoutText(layoutObject)->isTextFragment())
         return layoutObject;
     LayoutTextFragment* layoutTextFragment = toLayoutTextFragment(layoutObject);
     if (!layoutTextFragment->isRemainingTextLayoutObject()) {
-        DCHECK_LE(static_cast<unsigned>(offsetInNode), layoutTextFragment->start() + layoutTextFragment->fragmentLength());
+        ASSERT(static_cast<unsigned>(offsetInNode) <= layoutTextFragment->start() + layoutTextFragment->fragmentLength());
         return layoutTextFragment;
     }
     if (layoutTextFragment->fragmentLength() && static_cast<unsigned>(offsetInNode) >= layoutTextFragment->start())
@@ -2234,7 +2499,7 @@ LayoutObject* associatedLayoutObjectOf(const Node& node, int offsetInNode)
     LayoutObject* firstLetterLayoutObject = layoutTextFragment->firstLetterPseudoElement()->layoutObject();
     // TODO(yosin): We're not sure when |firstLetterLayoutObject| has
     // multiple child layout object.
-    DCHECK_EQ(firstLetterLayoutObject->slowFirstChild(), firstLetterLayoutObject->slowLastChild());
+    ASSERT(firstLetterLayoutObject->slowFirstChild() == firstLetterLayoutObject->slowLastChild());
     return firstLetterLayoutObject->slowFirstChild();
 }
 
@@ -2429,12 +2694,12 @@ static PositionTemplate<Strategy> mostBackwardCaretPosition(const PositionTempla
                 // of a mix-up between offsets in the text in the DOM tree with text in the
                 // layout tree which can have a different length due to case transformation.
                 // Until we resolve that, disable this so we can run the layout tests!
-                // DCHECK_GE(currentOffset, layoutObject->caretMaxOffset());
+                // ASSERT(currentOffset >= layoutObject->caretMaxOffset());
                 return PositionTemplate<Strategy>(currentNode, layoutObject->caretMaxOffset() + textStartOffset);
             }
 
             // Map offset in DOM node to offset in InlineBox.
-            DCHECK_GE(currentPos.offsetInLeafNode(), static_cast<int>(textStartOffset));
+            ASSERT(currentPos.offsetInLeafNode() >= static_cast<int>(textStartOffset));
             const unsigned textOffset = currentPos.offsetInLeafNode() - textStartOffset;
             InlineTextBox* lastTextBox = textLayoutObject->lastTextBox();
             for (InlineTextBox* box = textLayoutObject->firstTextBox(); box; box = box->nextTextBox()) {
@@ -2442,7 +2707,7 @@ static PositionTemplate<Strategy> mostBackwardCaretPosition(const PositionTempla
                     if (textLayoutObject->isTextFragment() && toLayoutTextFragment(layoutObject)->isRemainingTextLayoutObject()) {
                         // |currentPos| is at start of remaining text of
                         // |Text| node with :first-letter.
-                        DCHECK_GE(currentPos.offsetInLeafNode(), 1);
+                        ASSERT(currentPos.offsetInLeafNode() >= 1);
                         LayoutObject* firstLetterLayoutObject = toLayoutTextFragment(layoutObject)->firstLetterPseudoElement()->layoutObject();
                         if (firstLetterLayoutObject && firstLetterLayoutObject->style()->visibility() == VISIBLE)
                             return currentPos.computePosition();
@@ -2571,12 +2836,12 @@ PositionTemplate<Strategy> mostForwardCaretPosition(const PositionTemplate<Strat
             LayoutText* const textLayoutObject = toLayoutText(layoutObject);
             const unsigned textStartOffset = textLayoutObject->textStartOffset();
             if (currentNode != startNode) {
-                DCHECK(currentPos.atStartOfNode());
+                ASSERT(currentPos.atStartOfNode());
                 return PositionTemplate<Strategy>(currentNode, layoutObject->caretMinOffset() + textStartOffset);
             }
 
             // Map offset in DOM node to offset in InlineBox.
-            DCHECK_GE(currentPos.offsetInLeafNode(), static_cast<int>(textStartOffset));
+            ASSERT(currentPos.offsetInLeafNode() >= static_cast<int>(textStartOffset));
             const unsigned textOffset = currentPos.offsetInLeafNode() - textStartOffset;
             InlineTextBox* lastTextBox = textLayoutObject->lastTextBox();
             for (InlineTextBox* box = textLayoutObject->firstTextBox(); box; box = box->nextTextBox()) {
@@ -2769,7 +3034,7 @@ static VisiblePositionTemplate<Strategy> skipToEndOfEditingBoundary(const Visibl
 
     // That must mean that |pos| is not editable. Return the next position after
     // |pos| that is in the same editable region as this position
-    DCHECK(highestRoot);
+    ASSERT(highestRoot);
     return firstEditableVisiblePositionAfterPositionInRoot(pos.deepEquivalent(), *highestRoot);
 }
 
@@ -2821,169 +3086,34 @@ UChar32 characterBefore(const VisiblePositionInFlatTree& visiblePosition)
 }
 
 template <typename Strategy>
-static PositionTemplate<Strategy> leftVisuallyDistinctCandidate(const VisiblePositionTemplate<Strategy>& visiblePosition)
-{
-    const PositionTemplate<Strategy> deepPosition = visiblePosition.deepEquivalent();
-    PositionTemplate<Strategy> p = deepPosition;
-
-    if (p.isNull())
-        return PositionTemplate<Strategy>();
-
-    const PositionTemplate<Strategy> downstreamStart = mostForwardCaretPosition(p);
-    TextDirection primaryDirection = primaryDirectionOf(*p.anchorNode());
-    const TextAffinity affinity = visiblePosition.affinity();
-
-    while (true) {
-        InlineBoxPosition boxPosition = computeInlineBoxPosition(p, affinity, primaryDirection);
-        InlineBox* box = boxPosition.inlineBox;
-        int offset = boxPosition.offsetInBox;
-        if (!box)
-            return primaryDirection == LTR ? previousVisuallyDistinctCandidate(deepPosition) : nextVisuallyDistinctCandidate(deepPosition);
-
-        LineLayoutItem lineLayoutItem = box->getLineLayoutItem();
-
-        while (true) {
-            if ((lineLayoutItem.isAtomicInlineLevel() || lineLayoutItem.isBR()) && offset == box->caretRightmostOffset())
-                return box->isLeftToRightDirection() ? previousVisuallyDistinctCandidate(deepPosition) : nextVisuallyDistinctCandidate(deepPosition);
-
-            if (!lineLayoutItem.node()) {
-                box = box->prevLeafChild();
-                if (!box)
-                    return primaryDirection == LTR ? previousVisuallyDistinctCandidate(deepPosition) : nextVisuallyDistinctCandidate(deepPosition);
-                lineLayoutItem = box->getLineLayoutItem();
-                offset = box->caretRightmostOffset();
-                continue;
-            }
-
-            offset = box->isLeftToRightDirection() ? previousGraphemeBoundaryOf(lineLayoutItem.node(), offset) : nextGraphemeBoundaryOf(lineLayoutItem.node(), offset);
-
-            int caretMinOffset = box->caretMinOffset();
-            int caretMaxOffset = box->caretMaxOffset();
-
-            if (offset > caretMinOffset && offset < caretMaxOffset)
-                break;
-
-            if (box->isLeftToRightDirection() ? offset < caretMinOffset : offset > caretMaxOffset) {
-                // Overshot to the left.
-                InlineBox* prevBox = box->prevLeafChildIgnoringLineBreak();
-                if (!prevBox) {
-                    PositionTemplate<Strategy> positionOnLeft = primaryDirection == LTR ? previousVisuallyDistinctCandidate(visiblePosition.deepEquivalent()) : nextVisuallyDistinctCandidate(visiblePosition.deepEquivalent());
-                    if (positionOnLeft.isNull())
-                        return PositionTemplate<Strategy>();
-
-                    InlineBox* boxOnLeft = computeInlineBoxPosition(positionOnLeft, affinity, primaryDirection).inlineBox;
-                    if (boxOnLeft && boxOnLeft->root() == box->root())
-                        return PositionTemplate<Strategy>();
-                    return positionOnLeft;
-                }
-
-                // Reposition at the other logical position corresponding to our
-                // edge's visual position and go for another round.
-                box = prevBox;
-                lineLayoutItem = box->getLineLayoutItem();
-                offset = prevBox->caretRightmostOffset();
-                continue;
-            }
-
-            DCHECK_EQ(offset, box->caretLeftmostOffset());
-
-            unsigned char level = box->bidiLevel();
-            InlineBox* prevBox = box->prevLeafChild();
-
-            if (box->direction() == primaryDirection) {
-                if (!prevBox) {
-                    InlineBox* logicalStart = 0;
-                    if (primaryDirection == LTR ? box->root().getLogicalStartBoxWithNode(logicalStart) : box->root().getLogicalEndBoxWithNode(logicalStart)) {
-                        box = logicalStart;
-                        lineLayoutItem = box->getLineLayoutItem();
-                        offset = primaryDirection == LTR ? box->caretMinOffset() : box->caretMaxOffset();
-                    }
-                    break;
-                }
-                if (prevBox->bidiLevel() >= level)
-                    break;
-
-                level = prevBox->bidiLevel();
-
-                InlineBox* nextBox = box;
-                do {
-                    nextBox = nextBox->nextLeafChild();
-                } while (nextBox && nextBox->bidiLevel() > level);
-
-                if (nextBox && nextBox->bidiLevel() == level)
-                    break;
-
-                box = prevBox;
-                lineLayoutItem = box->getLineLayoutItem();
-                offset = box->caretRightmostOffset();
-                if (box->direction() == primaryDirection)
-                    break;
-                continue;
-            }
-
-            while (prevBox && !prevBox->getLineLayoutItem().node())
-                prevBox = prevBox->prevLeafChild();
-
-            if (prevBox) {
-                box = prevBox;
-                lineLayoutItem = box->getLineLayoutItem();
-                offset = box->caretRightmostOffset();
-                if (box->bidiLevel() > level) {
-                    do {
-                        prevBox = prevBox->prevLeafChild();
-                    } while (prevBox && prevBox->bidiLevel() > level);
-
-                    if (!prevBox || prevBox->bidiLevel() < level)
-                        continue;
-                }
-            } else {
-                // Trailing edge of a secondary run. Set to the leading edge of
-                // the entire run.
-                while (true) {
-                    while (InlineBox* nextBox = box->nextLeafChild()) {
-                        if (nextBox->bidiLevel() < level)
-                            break;
-                        box = nextBox;
-                    }
-                    if (box->bidiLevel() == level)
-                        break;
-                    level = box->bidiLevel();
-                    while (InlineBox* prevBox = box->prevLeafChild()) {
-                        if (prevBox->bidiLevel() < level)
-                            break;
-                        box = prevBox;
-                    }
-                    if (box->bidiLevel() == level)
-                        break;
-                    level = box->bidiLevel();
-                }
-                lineLayoutItem = box->getLineLayoutItem();
-                offset = primaryDirection == LTR ? box->caretMinOffset() : box->caretMaxOffset();
-            }
-            break;
-        }
-
-        p = PositionTemplate<Strategy>::editingPositionOf(lineLayoutItem.node(), offset);
-
-        if ((isVisuallyEquivalentCandidate(p) && mostForwardCaretPosition(p) != downstreamStart) || p.atStartOfTree() || p.atEndOfTree())
-            return p;
-
-        DCHECK_NE(p, deepPosition);
-    }
-}
-
-template <typename Strategy>
 VisiblePositionTemplate<Strategy> leftPositionOfAlgorithm(const VisiblePositionTemplate<Strategy>& visiblePosition)
 {
-    const PositionTemplate<Strategy> pos = leftVisuallyDistinctCandidate(visiblePosition);
-    // TODO(yosin) Why can't we move left from the last position in a tree?
-    if (pos.atStartOfTree() || pos.atEndOfTree())
+    if (visiblePosition.isNull())
         return VisiblePositionTemplate<Strategy>();
-
-    const VisiblePositionTemplate<Strategy> left = createVisiblePosition(pos);
-    DCHECK_NE(left.deepEquivalent(), visiblePosition.deepEquivalent());
-
-    return directionOfEnclosingBlock(left.deepEquivalent()) == LTR ? honorEditingBoundaryAtOrBefore(left, visiblePosition.deepEquivalent()) : honorEditingBoundaryAtOrAfter(left, visiblePosition.deepEquivalent());
+    const PositionTemplate<Strategy>& startPosition = visiblePosition.deepEquivalent();
+    const LayoutPosition& startLayoutPostion = LayoutPosition::create(startPosition);
+    for (LayoutPosition runner = leftPositionOf(startLayoutPostion);
+        runner.isNotNull();
+        runner = leftPositionOf(runner)) {
+        if (!runner.canPlaceCaret() || runner.isCaretEquivalent(startLayoutPostion))
+            continue;
+        const PositionTemplate<Strategy>& position = runner.toPosition(PositionTemplate<Strategy>());
+        // TODO(yosin): Why can't we move left from the last position in a tree?
+        if (position.atStartOfTree() || position.atEndOfTree())
+            return VisiblePositionTemplate<Strategy>();
+        const VisiblePositionTemplate<Strategy>& visibleLeft = createVisiblePosition(position);
+        if (visibleLeft.isNull())
+            return VisiblePositionTemplate<Strategy>();
+        const PositionTemplate<Strategy>& left = visibleLeft.deepEquivalent();
+        if (left == startPosition) {
+            // |runner| is a member of canonical position set of |startPosition|.
+            continue;
+        }
+        if (directionOfEnclosingBlock(left) == LTR)
+            return honorEditingBoundaryAtOrBefore(visibleLeft, startPosition);
+        return honorEditingBoundaryAtOrAfter(visibleLeft, startPosition);
+    }
+    return VisiblePositionTemplate<Strategy>();
 }
 
 VisiblePosition leftPositionOf(const VisiblePosition& visiblePosition)
@@ -2997,171 +3127,38 @@ VisiblePositionInFlatTree leftPositionOf(const VisiblePositionInFlatTree& visibl
 }
 
 template <typename Strategy>
-static PositionTemplate<Strategy> rightVisuallyDistinctCandidate(const VisiblePositionTemplate<Strategy>& visiblePosition)
-{
-    const PositionTemplate<Strategy> deepPosition = visiblePosition.deepEquivalent();
-    PositionTemplate<Strategy> p = deepPosition;
-    if (p.isNull())
-        return PositionTemplate<Strategy>();
-
-    const PositionTemplate<Strategy> downstreamStart = mostForwardCaretPosition(p);
-    TextDirection primaryDirection = primaryDirectionOf(*p.anchorNode());
-    const TextAffinity affinity = visiblePosition.affinity();
-
-    while (true) {
-        InlineBoxPosition boxPosition = computeInlineBoxPosition(p, affinity, primaryDirection);
-        InlineBox* box = boxPosition.inlineBox;
-        int offset = boxPosition.offsetInBox;
-        if (!box)
-            return primaryDirection == LTR ? nextVisuallyDistinctCandidate(deepPosition) : previousVisuallyDistinctCandidate(deepPosition);
-
-        LayoutObject* layoutObject = LineLayoutAPIShim::layoutObjectFrom(box->getLineLayoutItem());
-
-        while (true) {
-            if ((layoutObject->isAtomicInlineLevel() || layoutObject->isBR()) && offset == box->caretLeftmostOffset())
-                return box->isLeftToRightDirection() ? nextVisuallyDistinctCandidate(deepPosition) : previousVisuallyDistinctCandidate(deepPosition);
-
-            if (!layoutObject->node()) {
-                box = box->nextLeafChild();
-                if (!box)
-                    return primaryDirection == LTR ? nextVisuallyDistinctCandidate(deepPosition) : previousVisuallyDistinctCandidate(deepPosition);
-                layoutObject = LineLayoutAPIShim::layoutObjectFrom(box->getLineLayoutItem());
-                offset = box->caretLeftmostOffset();
-                continue;
-            }
-
-            offset = box->isLeftToRightDirection() ? nextGraphemeBoundaryOf(layoutObject->node(), offset) : previousGraphemeBoundaryOf(layoutObject->node(), offset);
-
-            int caretMinOffset = box->caretMinOffset();
-            int caretMaxOffset = box->caretMaxOffset();
-
-            if (offset > caretMinOffset && offset < caretMaxOffset)
-                break;
-
-            if (box->isLeftToRightDirection() ? offset > caretMaxOffset : offset < caretMinOffset) {
-                // Overshot to the right.
-                InlineBox* nextBox = box->nextLeafChildIgnoringLineBreak();
-                if (!nextBox) {
-                    PositionTemplate<Strategy> positionOnRight = primaryDirection == LTR ? nextVisuallyDistinctCandidate(deepPosition) : previousVisuallyDistinctCandidate(deepPosition);
-                    if (positionOnRight.isNull())
-                        return PositionTemplate<Strategy>();
-
-                    InlineBox* boxOnRight = computeInlineBoxPosition(positionOnRight, affinity, primaryDirection).inlineBox;
-                    if (boxOnRight && boxOnRight->root() == box->root())
-                        return PositionTemplate<Strategy>();
-                    return positionOnRight;
-                }
-
-                // Reposition at the other logical position corresponding to our
-                // edge's visual position and go for another round.
-                box = nextBox;
-                layoutObject = LineLayoutAPIShim::layoutObjectFrom(box->getLineLayoutItem());
-                offset = nextBox->caretLeftmostOffset();
-                continue;
-            }
-
-            DCHECK_EQ(offset, box->caretRightmostOffset());
-
-            unsigned char level = box->bidiLevel();
-            InlineBox* nextBox = box->nextLeafChild();
-
-            if (box->direction() == primaryDirection) {
-                if (!nextBox) {
-                    InlineBox* logicalEnd = 0;
-                    if (primaryDirection == LTR ? box->root().getLogicalEndBoxWithNode(logicalEnd) : box->root().getLogicalStartBoxWithNode(logicalEnd)) {
-                        box = logicalEnd;
-                        layoutObject = LineLayoutAPIShim::layoutObjectFrom(box->getLineLayoutItem());
-                        offset = primaryDirection == LTR ? box->caretMaxOffset() : box->caretMinOffset();
-                    }
-                    break;
-                }
-
-                if (nextBox->bidiLevel() >= level)
-                    break;
-
-                level = nextBox->bidiLevel();
-
-                InlineBox* prevBox = box;
-                do {
-                    prevBox = prevBox->prevLeafChild();
-                } while (prevBox && prevBox->bidiLevel() > level);
-
-                // For example, abc FED 123 ^ CBA
-                if (prevBox && prevBox->bidiLevel() == level)
-                    break;
-
-                // For example, abc 123 ^ CBA or 123 ^ CBA abc
-                box = nextBox;
-                layoutObject = LineLayoutAPIShim::layoutObjectFrom(box->getLineLayoutItem());
-                offset = box->caretLeftmostOffset();
-                if (box->direction() == primaryDirection)
-                    break;
-                continue;
-            }
-
-            while (nextBox && !nextBox->getLineLayoutItem().node())
-                nextBox = nextBox->nextLeafChild();
-
-            if (nextBox) {
-                box = nextBox;
-                layoutObject = LineLayoutAPIShim::layoutObjectFrom(box->getLineLayoutItem());
-                offset = box->caretLeftmostOffset();
-
-                if (box->bidiLevel() > level) {
-                    do {
-                        nextBox = nextBox->nextLeafChild();
-                    } while (nextBox && nextBox->bidiLevel() > level);
-
-                    if (!nextBox || nextBox->bidiLevel() < level)
-                        continue;
-                }
-            } else {
-                // Trailing edge of a secondary run. Set to the leading edge of the entire run.
-                while (true) {
-                    while (InlineBox* prevBox = box->prevLeafChild()) {
-                        if (prevBox->bidiLevel() < level)
-                            break;
-                        box = prevBox;
-                    }
-                    if (box->bidiLevel() == level)
-                        break;
-                    level = box->bidiLevel();
-                    while (InlineBox* nextBox = box->nextLeafChild()) {
-                        if (nextBox->bidiLevel() < level)
-                            break;
-                        box = nextBox;
-                    }
-                    if (box->bidiLevel() == level)
-                        break;
-                    level = box->bidiLevel();
-                }
-                layoutObject = LineLayoutAPIShim::layoutObjectFrom(box->getLineLayoutItem());
-                offset = primaryDirection == LTR ? box->caretMaxOffset() : box->caretMinOffset();
-            }
-            break;
-        }
-
-        p = PositionTemplate<Strategy>::editingPositionOf(layoutObject->node(), offset);
-
-        if ((isVisuallyEquivalentCandidate(p) && mostForwardCaretPosition(p) != downstreamStart) || p.atStartOfTree() || p.atEndOfTree())
-            return p;
-
-        DCHECK_NE(p, deepPosition);
-    }
-}
-
-template <typename Strategy>
 static VisiblePositionTemplate<Strategy> rightPositionOfAlgorithm(const VisiblePositionTemplate<Strategy>& visiblePosition)
 {
-    const PositionTemplate<Strategy> pos = rightVisuallyDistinctCandidate(visiblePosition);
-    // FIXME: Why can't we move left from the last position in a tree?
-    if (pos.atStartOfTree() || pos.atEndOfTree())
+    if (visiblePosition.isNull())
         return VisiblePositionTemplate<Strategy>();
-
-    const VisiblePositionTemplate<Strategy> right = createVisiblePosition(pos);
-    DCHECK_NE(right.deepEquivalent(), visiblePosition.deepEquivalent());
-
-    return directionOfEnclosingBlock(right.deepEquivalent()) == LTR ? honorEditingBoundaryAtOrAfter(right, visiblePosition.deepEquivalent()) : honorEditingBoundaryAtOrBefore(right, visiblePosition.deepEquivalent());
+    const PositionTemplate<Strategy>& startPosition = visiblePosition.deepEquivalent();
+    const LayoutPosition& startLayoutPostion = LayoutPosition::create(startPosition);
+    for (LayoutPosition runner = rightPositionOf(startLayoutPostion);
+        runner.isNotNull();
+        runner = rightPositionOf(runner)) {
+        if (!runner.canPlaceCaret() || runner.isCaretEquivalent(startLayoutPostion))
+            continue;
+        const PositionTemplate<Strategy>& position = runner.toPosition(PositionTemplate<Strategy>());
+        // TODO(yosin): Why can't we move left from the last position in a tree?
+        if (position.atStartOfTree() || position.atEndOfTree())
+            return VisiblePositionTemplate<Strategy>();
+        // We should always be able to make the affinity
+        // |TextAffinity::Downstream|, because going right from an
+        // |TextAffinity::Upstream| position can never yield another
+        // |TextAffinity::Upstream position| (unless line wrap length is 0).
+        const VisiblePositionTemplate<Strategy>& visibleRight = createVisiblePosition(position);
+        if (visibleRight.isNull())
+            return VisiblePositionTemplate<Strategy>();
+        const PositionTemplate<Strategy>& right = visibleRight.deepEquivalent();
+        if (right == startPosition) {
+            // |runner| is a member of canonical position set of |startPosition|.
+            continue;
+        }
+        if (directionOfEnclosingBlock(right) == LTR)
+            return honorEditingBoundaryAtOrAfter(visibleRight, startPosition);
+        return honorEditingBoundaryAtOrBefore(visibleRight, startPosition);
+    }
+    return VisiblePositionTemplate<Strategy>();
 }
 
 VisiblePosition rightPositionOf(const VisiblePosition& visiblePosition)
@@ -3177,18 +3174,36 @@ VisiblePositionInFlatTree rightPositionOf(const VisiblePositionInFlatTree& visib
 template <typename Strategy>
 static VisiblePositionTemplate<Strategy> nextPositionOfAlgorithm(const VisiblePositionTemplate<Strategy>& visiblePosition, EditingBoundaryCrossingRule rule)
 {
-    const VisiblePositionTemplate<Strategy> next = createVisiblePosition(nextVisuallyDistinctCandidate(visiblePosition.deepEquivalent()), visiblePosition.affinity());
+    if (visiblePosition.isNull())
+        return VisiblePositionTemplate<Strategy>();
+    const PositionTemplate<Strategy>& startPosition = visiblePosition.deepEquivalent();
+    const LayoutPosition& startLayoutPostion = LayoutPosition::create(startPosition);
+    for (LayoutPosition runner = nextPositionOf(startLayoutPostion);
+        runner.isNotNull();
+        runner = nextPositionOf(runner)) {
+        if (!runner.canPlaceCaret() || runner.isCaretEquivalent(startLayoutPostion))
+            continue;
+        const PositionTemplate<Strategy>& position = runner.toPosition(PositionTemplate<Strategy>());
+        const VisiblePositionTemplate<Strategy>& visibleNext = createVisiblePosition(position);
+        if (visibleNext.isNull())
+            return VisiblePositionTemplate<Strategy>();
+        if (visibleNext.deepEquivalent() == startPosition) {
+            // |runner| is a member of canonical position set of |startPosition|.
+            continue;
+        }
+        switch (rule) {
+        case CanCrossEditingBoundary:
+            return visibleNext;
+        case CannotCrossEditingBoundary:
+            return honorEditingBoundaryAtOrAfter(visibleNext, startPosition);
+        case CanSkipOverEditingBoundary:
+            return skipToEndOfEditingBoundary(visibleNext, startPosition);
+        }
 
-    switch (rule) {
-    case CanCrossEditingBoundary:
-        return next;
-    case CannotCrossEditingBoundary:
-        return honorEditingBoundaryAtOrAfter(next, visiblePosition.deepEquivalent());
-    case CanSkipOverEditingBoundary:
-        return skipToEndOfEditingBoundary(next, visiblePosition.deepEquivalent());
+        ASSERT_NOT_REACHED();
+        return honorEditingBoundaryAtOrAfter(visibleNext, startPosition);
     }
-    ASSERT_NOT_REACHED();
-    return honorEditingBoundaryAtOrAfter(next, visiblePosition.deepEquivalent());
+    return VisiblePositionTemplate<Strategy>();
 }
 
 VisiblePosition nextPositionOf(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
@@ -3221,37 +3236,49 @@ static VisiblePositionTemplate<Strategy> skipToStartOfEditingBoundary(const Visi
 
     // That must mean that |pos| is not editable. Return the last position
     // before |pos| that is in the same editable region as this position
-    DCHECK(highestRoot);
+    ASSERT(highestRoot);
     return lastEditableVisiblePositionBeforePositionInRoot(pos.deepEquivalent(), *highestRoot);
 }
 
 template <typename Strategy>
 static VisiblePositionTemplate<Strategy> previousPositionOfAlgorithm(const VisiblePositionTemplate<Strategy>& visiblePosition, EditingBoundaryCrossingRule rule)
 {
-    const PositionTemplate<Strategy> pos = previousVisuallyDistinctCandidate(visiblePosition.deepEquivalent());
-
-    // return null visible position if there is no previous visible position
-    if (pos.atStartOfTree())
+    if (visiblePosition.isNull())
         return VisiblePositionTemplate<Strategy>();
+    const PositionTemplate<Strategy>& startPosition = visiblePosition.deepEquivalent();
+    const LayoutPosition& startLayoutPosition = LayoutPosition::create(startPosition);
+    for (LayoutPosition runner = previousPositionOf(startLayoutPosition);
+        runner.isNotNull();
+        runner = previousPositionOf(runner)) {
+        if (!runner.canPlaceCaret() || runner.isCaretEquivalent(startLayoutPosition))
+            continue;
+        const PositionTemplate<Strategy>& position = runner.toPosition(PositionTemplate<Strategy>());
+        if (position.atStartOfTree())
+            return VisiblePositionTemplate<Strategy>();
+        // We should always be able to make the affinity
+        // |TextAffinity::Downstream|, because going previous from an
+        // |TextAffinity::Upstream| position can never yield another
+        // |TextAffinity::Upstream position| (unless line wrap length is 0).
+        const VisiblePositionTemplate<Strategy>& visiblePrevious = createVisiblePosition(position);
+        if (visiblePrevious.isNull())
+            return VisiblePositionTemplate<Strategy>();
+        if (visiblePrevious.deepEquivalent() == startPosition) {
+            // |runner| is a member of canonical position set of |startPosition|.
+            continue;
+        }
+        switch (rule) {
+        case CanCrossEditingBoundary:
+            return visiblePrevious;
+        case CannotCrossEditingBoundary:
+            return honorEditingBoundaryAtOrBefore(visiblePrevious, startPosition);
+        case CanSkipOverEditingBoundary:
+            return skipToStartOfEditingBoundary(visiblePrevious, startPosition);
+        }
 
-    // we should always be able to make the affinity |TextAffinity::Downstream|,
-    // because going previous from an |TextAffinity::Upstream| position can
-    // never yield another |TextAffinity::Upstream position| (unless line wrap
-    // length is 0!).
-    const VisiblePositionTemplate<Strategy> prev = createVisiblePosition(pos);
-    DCHECK_NE(prev.deepEquivalent(), visiblePosition.deepEquivalent());
-
-    switch (rule) {
-    case CanCrossEditingBoundary:
-        return prev;
-    case CannotCrossEditingBoundary:
-        return honorEditingBoundaryAtOrBefore(prev, visiblePosition.deepEquivalent());
-    case CanSkipOverEditingBoundary:
-        return skipToStartOfEditingBoundary(prev, visiblePosition.deepEquivalent());
+        ASSERT_NOT_REACHED();
+        return honorEditingBoundaryAtOrBefore(visiblePrevious, startPosition);
     }
-
-    ASSERT_NOT_REACHED();
-    return honorEditingBoundaryAtOrBefore(prev, visiblePosition.deepEquivalent());
+    return VisiblePositionTemplate<Strategy>();
 }
 
 VisiblePosition previousPositionOf(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)