2016-03-02T18:53:01 LayoutPosition

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

 /*
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 15 matching lines @@
 #include "core/editing/VisibleUnits.h"
 
 #include "core/HTMLNames.h"
 #include "core/dom/Document.h"
 #include "core/dom/Element.h"
 #include "core/dom/FirstLetterPseudoElement.h"
 #include "core/dom/NodeTraversal.h"
 #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"
 #include "core/editing/TextAffinity.h"
 #include "core/editing/VisiblePosition.h"
 #include "core/editing/iterators/BackwardsCharacterIterator.h"
 #include "core/editing/iterators/BackwardsTextBuffer.h"
 #include "core/editing/iterators/CharacterIterator.h"
 #include "core/editing/iterators/ForwardsTextBuffer.h"
 #include "core/editing/iterators/SimplifiedBackwardsTextIterator.h"
@@ skipping 21 matching lines @@
 #include "platform/heap/Handle.h"
 #include "platform/text/TextBoundaries.h"
 
 namespace blink {
 
 template <typename PositionType>
 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;
     return candidate;
 }
 
 template <typename PositionType>
 static PositionType canonicalPosition(const PositionType& passedPosition)
 {
     // Sometimes updating selection positions can be extremely expensive and
     // occur frequently.  Often calling preventDefault on mousedown events can
     // avoid doing unnecessary text selection work.  http://crbug.com/472258.
     TRACE_EVENT0("input", "VisibleUnits::canonicalPosition");
 
     // The updateLayout call below can do so much that even the position passed
     // in to us might get changed as a side effect. Specifically, there are code
     // paths that pass selection endpoints, and updateLayout can change the
     // selection.
     PositionType position = passedPosition;
 
     // FIXME (9535):  Canonicalizing to the leftmost candidate means that if
     // we're at a line wrap, we will ask layoutObjects to paint downstream
     // carets for other layoutObjects. To fix this, we need to either a) add
     // code to all paintCarets to pass the responsibility off to the appropriate
     // layoutObject for VisiblePosition's like these, or b) canonicalize to the
     // rightmost candidate unless the affinity is upstream.
     if (position.isNull())
         return PositionType();
 
-    DCHECK(position.document());
+    ASSERT(position.document());
     position.document()->updateLayoutIgnorePendingStylesheets();
 
     Node* node = position.computeContainerNode();
 
     PositionType candidate = mostBackwardCaretPosition(position);
     if (isVisuallyEquivalentCandidate(candidate))
         return candidate;
     candidate = mostForwardCaretPosition(position);
     if (isVisuallyEquivalentCandidate(candidate))
         return candidate;
@@ skipping 34 matching lines @@
     // The new position should be in the same block flow element. Favor that.
     Element* originalBlock = node ? enclosingBlockFlowElement(*node) : 0;
     bool nextIsOutsideOriginalBlock = !nextNode->isDescendantOf(originalBlock) && nextNode != originalBlock;
     bool prevIsOutsideOriginalBlock = !prevNode->isDescendantOf(originalBlock) && prevNode != originalBlock;
     if (nextIsOutsideOriginalBlock && !prevIsOutsideOriginalBlock)
         return prev;
 
     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);
-}
-
-template <typename Strategy>
+#if 0
+    const auto& expected = canonicalPosition(position);
+#endif
+    const auto& actual = caretPositionOf(position);
+    return actual;
+}
+
+template <typename Strategy>
 static PositionWithAffinityTemplate<Strategy> honorEditingBoundaryAtOrBefore(const PositionWithAffinityTemplate<Strategy>& pos, const PositionTemplate<Strategy>& anchor)
 {
     if (pos.isNull())
         return pos;
 
     ContainerNode* highestRoot = highestEditableRoot(anchor);
 
     // Return empty position if |pos| is not somewhere inside the editable
     // region containing this position
     if (highestRoot && !pos.position().anchorNode()->isDescendantOf(highestRoot))
@@ skipping 536 matching lines @@
             next = 0;
         }
         it.advance();
     }
     if (needMoreContext) {
         // The last search returned the beginning of the buffer and asked for
         // more context, but there is no earlier text. Force a search with
         // 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)
         return createVisiblePosition(it.atEnd() ? it.startPosition() : pos);
 
     Node* node = it.startContainer();
     int boundaryOffset = remainingLength + next;
     if (node->isTextNode() && boundaryOffset <= node->maxCharacterOffset()) {
         // The next variable contains a usable index into a text node
         return createVisiblePosition(PositionTemplate<Strategy>(node, boundaryOffset));
@@ skipping 73 matching lines @@
             next = string.size();
         }
         it.advance();
     }
     if (needMoreContext) {
         // The last search returned the end of the buffer and asked for more
         // context, but there is no further text. Force a search with what's
         // 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()) {
         pos = it.startPositionInCurrentContainer();
     } else if (next != invalidOffset && next != prefixLength) {
         // TODO(dglazkov): The use of updateLayoutIgnorePendingStylesheets needs to be audited.
         // see http://crbug.com/590369 for more details.
         searchStart.document()->updateLayoutIgnorePendingStylesheets();
         // Use the character iterator to translate the next value into a DOM
         // position.
@@ skipping 15 matching lines @@
 
     // generate VisiblePosition, use TextAffinity::Upstream affinity if possible
     return createVisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
 }
 
 // ---------
 
 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;
     }
     needMoreContext = false;
     int start, end;
     U16_BACK_1(characters, 0, offset);
     findWordBoundary(characters, length, offset, &start, &end);
     return start;
 }
@@ skipping 21 matching lines @@
     return startOfWordAlgorithm<EditingStrategy>(c, side);
 }
 
 VisiblePositionInFlatTree startOfWord(const VisiblePositionInFlatTree& c, EWordSide side)
 {
     return startOfWordAlgorithm<EditingInFlatTreeStrategy>(c, side);
 }
 
 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;
     }
     needMoreContext = false;
     return findWordEndBoundary(characters, length, offset);
 }
 
 template <typename Strategy>
 static VisiblePositionTemplate<Strategy> endOfWordAlgorithm(const VisiblePositionTemplate<Strategy>& c, EWordSide side)
@@ skipping 367 matching lines @@
     return isLogicalEndOfLineAlgorithm<EditingStrategy>(p);
 }
 
 bool isLogicalEndOfLine(const VisiblePositionInFlatTree& p)
 {
     return isLogicalEndOfLineAlgorithm<EditingInFlatTreeStrategy>(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())
         absoluteBlockPoint -= FloatSize(containingBlock.scrolledContentOffset());
 
     if (root->block().isHorizontalWritingMode())
         return LayoutPoint(LayoutUnit(lineDirectionPoint - absoluteBlockPoint.x()), root->blockDirectionPointInLine());
 
     return LayoutPoint(root->blockDirectionPointInLine(), LayoutUnit(lineDirectionPoint - absoluteBlockPoint.y()));
 }
@@ skipping 913 matching lines @@
 //  appeared in layout tree.
 //
 //  When |Text| node contains only first-letter characters and whitespaces, e.g.
 //  "B\n", associated |LayoutTextFragment| is first-letter part instead of
 //  remaining part.
 //
 //  Punctuation characters are considered as first-letter. For "(1)ab",
 //  "(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())
         return layoutObject;
     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();
 }
 
 int caretMinOffset(const Node* node)
 {
     LayoutObject* layoutObject = associatedLayoutObjectOf(*node, 0);
     return layoutObject ? layoutObject->caretMinOffset() : 0;
 }
 
 int caretMaxOffset(const Node* n)
@@ skipping 174 matching lines @@
 
         // return current position if it is in laid out text
         if (layoutObject->isText() && toLayoutText(layoutObject)->firstTextBox()) {
             LayoutText* const textLayoutObject = toLayoutText(layoutObject);
             const unsigned textStartOffset = textLayoutObject->textStartOffset();
             if (currentNode != startNode) {
                 // This assertion fires in layout tests in the case-transform.html test because
                 // 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()) {
                 if (textOffset == box->start()) {
                     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();
                     }
                     continue;
                 }
                 if (textOffset <= box->start() + box->len()) {
                     if (textOffset > box->start())
                         return currentPos.computePosition();
                     continue;
@@ skipping 108 matching lines @@
             if (currentPos.offsetInLeafNode() <= layoutObject->caretMinOffset())
                 return PositionTemplate<Strategy>::editingPositionOf(currentNode, layoutObject->caretMinOffset());
             continue;
         }
 
         // return current position if it is in laid out text
         if (layoutObject->isText() && toLayoutText(layoutObject)->firstTextBox()) {
             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()) {
                 if (textOffset <= box->end()) {
                     if (textOffset >= box->start())
                         return currentPos.computePosition();
                     continue;
                 }
 
                 if (box == lastTextBox || textOffset != box->start() + box->len())
@@ skipping 172 matching lines @@
     // or both are non-editable.
     if (highestRootOfPos == highestRoot)
         return pos;
 
     // If this is not editable but |pos| has an editable root, skip to the end
     if (!highestRoot && highestRootOfPos)
         return createVisiblePosition(PositionTemplate<Strategy>(highestRootOfPos, PositionAnchorType::AfterAnchor).parentAnchoredEquivalent());
 
     // 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);
 }
 
 template <typename Strategy>
 static UChar32 characterAfterAlgorithm(const VisiblePositionTemplate<Strategy>& visiblePosition)
 {
     // We canonicalize to the first of two equivalent candidates, but the second
     // of the two candidates is the one that will be inside the text node
     // containing the character after this visible position.
     const PositionTemplate<Strategy> pos = mostForwardCaretPosition(visiblePosition.deepEquivalent());
@@ skipping 31 matching lines @@
 {
     return characterBeforeAlgorithm<EditingStrategy>(visiblePosition);
 }
 
 UChar32 characterBefore(const VisiblePositionInFlatTree& visiblePosition)
 {
     return characterBeforeAlgorithm<EditingInFlatTreeStrategy>(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)
 {
     return leftPositionOfAlgorithm<EditingStrategy>(visiblePosition);
 }
 
 VisiblePositionInFlatTree leftPositionOf(const VisiblePositionInFlatTree& visiblePosition)
 {
     return leftPositionOfAlgorithm<EditingInFlatTreeStrategy>(visiblePosition);
 }
 
 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)
 {
     return rightPositionOfAlgorithm<EditingStrategy>(visiblePosition);
 }
 
 VisiblePositionInFlatTree rightPositionOf(const VisiblePositionInFlatTree& visiblePosition)
 {
     return rightPositionOfAlgorithm<EditingInFlatTreeStrategy>(visiblePosition);
 }
 
 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)
 {
     return nextPositionOfAlgorithm<EditingStrategy>(visiblePosition, rule);
 }
 
 VisiblePositionInFlatTree nextPositionOf(const VisiblePositionInFlatTree& visiblePosition, EditingBoundaryCrossingRule rule)
 {
     return nextPositionOfAlgorithm<EditingInFlatTreeStrategy>(visiblePosition, rule);
@@ skipping 12 matching lines @@
     // both are non-editable.
     if (highestRootOfPos == highestRoot)
         return pos;
 
     // If this is not editable but |pos| has an editable root, skip to the start
     if (!highestRoot && highestRootOfPos)
         return createVisiblePosition(previousVisuallyDistinctCandidate(PositionTemplate<Strategy>(highestRootOfPos, PositionAnchorType::BeforeAnchor).parentAnchoredEquivalent()));
 
     // 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());
+    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);
+        }
 
-    // return null visible position if there is no previous visible position
-    if (pos.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> 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)
 {
     return previousPositionOfAlgorithm<EditingStrategy>(visiblePosition, rule);
 }
 
 VisiblePositionInFlatTree previousPositionOf(const VisiblePositionInFlatTree& visiblePosition, EditingBoundaryCrossingRule rule)
 {
     return previousPositionOfAlgorithm<EditingInFlatTreeStrategy>(visiblePosition, rule);
 }
 
 } // namespace blink