Improving direction-based selection strategy.

Source/core/editing/GranularityStrategy.cpp

Index: Source/core/editing/GranularityStrategy.cpp
diff --git a/Source/core/editing/GranularityStrategy.cpp b/Source/core/editing/GranularityStrategy.cpp
index 5a5fd9ee30330abf12efdd949c68fff152dc0636..abdb17659e94154a0f3db97b000ea10bb27ee7eb 100644
--- a/Source/core/editing/GranularityStrategy.cpp
+++ b/Source/core/editing/GranularityStrategy.cpp
@@ -5,6 +5,7 @@
 #include "config.h"
 #include "core/editing/GranularityStrategy.h"
 
+#include "core/editing/FrameSelection.h"
 #include "core/editing/htmlediting.h"
 
 namespace blink {
@@ -24,14 +25,19 @@ SelectionStrategy CharacterGranularityStrategy::GetType() const
 
 void CharacterGranularityStrategy::Clear() { };
 
-VisibleSelection CharacterGranularityStrategy::updateExtent(const VisiblePosition& extentPosition, const VisibleSelection& selection)
+VisibleSelection CharacterGranularityStrategy::updateExtent(const IntPoint& extentPoint, LocalFrame* frame)
 {
+    const VisiblePosition& extentPosition = visiblePositionForContentsPoint(extentPoint, frame);
+    const VisibleSelection& selection = frame->selection().selection();
+    if (selection.visibleBase() == extentPosition)
+        return selection;
     return VisibleSelection(selection.visibleBase(), extentPosition);
 }
 
 DirectionGranularityStrategy::DirectionGranularityStrategy()
-    : m_granularity(CharacterGranularity)
-    , m_lastMoveShrunkSelection(false) { }
+    : m_state(StrategyState::Cleared)
+    , m_granularity(CharacterGranularity)
+    , m_offset(0) { }
 
 DirectionGranularityStrategy::~DirectionGranularityStrategy() { }
 
@@ -42,10 +48,25 @@ SelectionStrategy DirectionGranularityStrategy::GetType() const
 
 void DirectionGranularityStrategy::Clear()
 {
+    m_state = StrategyState::Cleared;
     m_granularity = CharacterGranularity;
-    m_lastMoveShrunkSelection = false;
+    m_offset = 0;
+    m_subPositionCorrection.setWidth(0);
+    m_subPositionCorrection.setHeight(0);

[leviw_travelin_and_unemployed, 2015/05/26 20:25:50]

m_subPositionCorrection = IntSize();

[mfomitchev, 2015/05/26 22:32:47]

Acknowledged.

[mfomitchev, 2015/06/03 18:57:54]

Done.

+}
+
+bool DirectionGranularityStrategy::arePositionsInSpecifiedOrder(
+    const VisiblePosition& vp1,
+    const VisiblePosition& vp2,
+    int specifiedOrder)
+{
+    int positionOrder = comparePositions(vp1, vp2);
+    if (specifiedOrder == 0)
+        return positionOrder == 0;
+    return specifiedOrder > 0 ? positionOrder > 0 : positionOrder < 0;
 }
 
+
 VisiblePosition DirectionGranularityStrategy::nextWordBound(
     const VisiblePosition& pos,
     SearchDirection direction,
@@ -60,68 +81,138 @@ VisiblePosition DirectionGranularityStrategy::nextWordBound(
     return startOfWord(pos, wordSide);
 }
 
-VisibleSelection DirectionGranularityStrategy::updateExtent(const VisiblePosition& extentPosition, const VisibleSelection& selection)
+VisibleSelection DirectionGranularityStrategy::updateExtent(const IntPoint& extentPoint, LocalFrame* frame)
 {
-    if (extentPosition == selection.visibleExtent())
-        return selection;
+    const VisibleSelection& selection = frame->selection().selection();
+
+    if (m_state == StrategyState::Cleared)
+        m_state = StrategyState::Expanding;
+
+    VisiblePosition oldOffsetExtentPosition = selection.visibleExtent();
+    IntRect oldExtentCaretBounds = oldOffsetExtentPosition.absoluteCaretBounds();
+    IntPoint oldOffsetExtentPoint = oldExtentCaretBounds.minXMaxYCorner() + m_subPositionCorrection;

[leviw_travelin_and_unemployed, 2015/05/26 20:25:50]

There are subtle reasons for why you're using minXMaxYCorner. They should be
documented. Perhaps a static inline method with a handy name that just returns
minXMaxYCorner() but supplies context?

[mfomitchev, 2015/05/26 22:32:47]

Acknowledged.

[mfomitchev, 2015/06/03 18:57:54]

Done.

+    IntPoint oldExtentPoint = IntPoint(oldOffsetExtentPoint.x() - m_offset, oldOffsetExtentPoint.y());
+
+    // Apply the offset.
+    IntPoint newOffsetExtentPoint = extentPoint;
+    int dx = extentPoint.x() - oldExtentPoint.x();
+    if (m_offset != 0) {
+        if (m_offset > 0 && dx > 0)
+            m_offset = std::max(0, m_offset - dx);
+        else if (m_offset < 0 && dx < 0)
+            m_offset = std::min(0, m_offset - dx);
+        newOffsetExtentPoint.move(m_offset, 0);
+    }
+
+    VisiblePosition newOffsetExtentPosition = visiblePositionForContentsPoint(newOffsetExtentPoint, frame);
+    IntRect newOffsetExtentCaretBounds = newOffsetExtentPosition.absoluteCaretBounds();
+
+    // Reset the offset in case of a line change. Also reset it if we detect a y
+    // component to the vector between the old and the new positions which would
+    // happen if the text is rotated. The offset feature doesn't work for
+    // non-horizontal text.
+    if (!inSameLine(newOffsetExtentPosition, oldOffsetExtentPosition)
+        || (newOffsetExtentCaretBounds.maxY() - oldExtentCaretBounds.maxY()) != 0) {

[leviw_travelin_and_unemployed, 2015/05/26 20:25:50]

(newOffsetExtentCaretBounds.maxY() - oldExtentCaretBounds.maxY()) != 0 is the
same as newOffsetExtentCaretBounds.maxY() != oldExtentCaretBounds.maxY().

You should swap the order of these conditions since the common case is the 2nd
part will be true if the 1st is, and checking it is much cheaper.

[mfomitchev, 2015/05/26 22:32:47]

Acknowledged.

[mfomitchev, 2015/06/03 18:57:54]

Done.

+        m_offset = 0;
+        newOffsetExtentPoint = extentPoint;
+        newOffsetExtentPosition = visiblePositionForContentsPoint(extentPoint, frame);
+    }
 
     const VisiblePosition base = selection.visibleBase();
-    const VisiblePosition oldExtentWithGranularity = selection.isBaseFirst() ? selection.visibleEnd() : selection.visibleStart();
-
-    int extentBaseOrder = comparePositions(extentPosition, base);
-    int oldExtentBaseOrder = comparePositions(oldExtentWithGranularity, base);
-
-    bool extentBaseOrderSwitched = (extentBaseOrder > 0 && oldExtentBaseOrder < 0)
-        || (extentBaseOrder < 0 && oldExtentBaseOrder > 0);
-
-    // Determine the boundary of the 'current word', i.e. the boundary extending
-    // beyond which should change the granularity to WordGranularity.
-    // If the last move has shrunk the selection and is now exactly on the word
-    // boundary - we need to take the next bound as the bound of the "current
-    // word".
-    VisiblePosition currentWordBoundary = nextWordBound(
-        oldExtentWithGranularity,
-        oldExtentBaseOrder > 0 ? SearchDirection::SearchForward : SearchDirection::SearchBackwards,
-        m_lastMoveShrunkSelection ? BoundAdjust::NextBoundIfOnBound : BoundAdjust::CurrentPosIfOnBound);
-
-    bool thisMoveShrunkSelection = (extentBaseOrder > 0 && comparePositions(extentPosition, selection.visibleExtent()) < 0)
-        || (extentBaseOrder < 0 && comparePositions(extentPosition, selection.visibleExtent()) > 0);
-    // If the extent-base order was switched, then the selection is now
-    // expanding in a different direction than before. Therefore we need to
-    // calculate the boundary of the 'current word' in this new direction in
-    // order to be able to tell if the selection expanded beyond it.
-    if (extentBaseOrderSwitched) {
-        currentWordBoundary = nextWordBound(
-            base,
-            extentBaseOrder > 0 ? SearchDirection::SearchForward : SearchDirection::SearchBackwards,
-            BoundAdjust::NextBoundIfOnBound);
-        m_granularity = CharacterGranularity;
-        // When the base/extent order switches it doesn't count as shrinking selection.
+
+    // Do not allow selection and extent to be at the same position

[leviw_travelin_and_unemployed, 2015/05/26 20:25:50]

I'm a little confused by this statement. Are you not allowing them to be the
same position, or are you just not running the rest of this algorithm if they
are?

[mfomitchev, 2015/05/26 22:32:46]

This should read "base and extent", not "selection and extent". How about I
change it to:
// Do not allow empty selection
The idea is basically that if extentPoint corresponds to the same position as
the base, we just leave the selection the way it was. Note this functionality
was always there.  CharacterGranularityStrategy::updateExtent behaves this way
as well.

[leviw_travelin_and_unemployed, 2015/05/26 22:47:49]

SGTM.

[mfomitchev, 2015/06/03 18:57:54]

Done.

+    if (newOffsetExtentPosition == base)
+        return selection;
+
+    int oldExtentBaseOrder = selection.isBaseFirst() ? 1 : -1;
+
+    int newExtentBaseOrder;
+    bool thisMoveShrunkSelection;
+    if (newOffsetExtentPosition == oldOffsetExtentPosition) {
+        if (m_granularity == CharacterGranularity)
+            return selection;
+
+        // If we are in Word granularity, we cannot exit here, since we may pass
+        // the middle of the word without changing the position (in which case
+        // the selection needs to expand).
         thisMoveShrunkSelection = false;
-    }
+        newExtentBaseOrder = oldExtentBaseOrder;
+    } else {
+        bool selectionExpanded = arePositionsInSpecifiedOrder(newOffsetExtentPosition, oldOffsetExtentPosition, oldExtentBaseOrder);
+        bool extentBaseOrderSwitched = selectionExpanded ? false : !arePositionsInSpecifiedOrder(newOffsetExtentPosition, base, oldExtentBaseOrder);
+        newExtentBaseOrder = extentBaseOrderSwitched ? -oldExtentBaseOrder : oldExtentBaseOrder;
+
+        // Determine the word boundary, i.e. the boundary extending beyond which
+        // should change the granularity to WordGranularity.
+        VisiblePosition wordBoundary;
+        if (extentBaseOrderSwitched) {
+            // Special case.
+            // If the extent-base order was switched, then the selection is now
+            // expanding in a different direction than before. Therefore we
+            // calculate the word boundary in this new direction and based on
+            // the |base| position.
+            wordBoundary = nextWordBound(
+                base,
+                newExtentBaseOrder > 0 ? SearchDirection::SearchForward : SearchDirection::SearchBackwards,
+                BoundAdjust::NextBoundIfOnBound);
+            m_granularity = CharacterGranularity;
+        } else {
+            // Calculate the word boundary based on |oldExtentWithGranularity|.
+            // If selection was shrunk in the last update and the extent is now
+            // exactly on the word boundary - we need to take the next bound as
+            // the bound of the current word.
+            wordBoundary = nextWordBound(
+                oldOffsetExtentPosition,
+                oldExtentBaseOrder > 0 ? SearchDirection::SearchForward : SearchDirection::SearchBackwards,
+                m_state == StrategyState::Shrinking ? BoundAdjust::NextBoundIfOnBound : BoundAdjust::CurrentPosIfOnBound);
+        }
+
+        bool expandedBeyondWordBoundary;
+        if (selectionExpanded)
+            expandedBeyondWordBoundary = arePositionsInSpecifiedOrder(newOffsetExtentPosition, wordBoundary, newExtentBaseOrder);
+        else if (extentBaseOrderSwitched)
+            expandedBeyondWordBoundary = arePositionsInSpecifiedOrder(newOffsetExtentPosition, wordBoundary, newExtentBaseOrder);

[leviw_travelin_and_unemployed, 2015/05/26 20:25:50]

So worst case we have to do 3 calls to comparePositions?

Ideally we'd have some performance tests so that we're not just divining whether
this sort of thing is acceptable.

[mfomitchev, 2015/05/26 22:32:47]

Right. Typically we will have two tests. We will only have 3 tests if the update
moves the extent to the other side of the base, i.e. when the handles get
crossed, to use Android's terminology. We will only have one 3-test update per
each crossing of the handles. 

Native Android intentionally doesn't support handle crossing, and they want us
to remove support for it as well, so this case may even go away. 

Note the current code actually does four comparePositions..

Either way, doing a perf test sounds like a good idea, considering we are also
sometimes doing more hit testing. Would you be okay with me landing this without
the perf test initially and working on the test afterwards?

[leviw_travelin_and_unemployed, 2015/05/26 22:47:49]

This function can at most call it three times, right? line 174 and 172 are
mutually exclusive.
The issue with putting this change before a perf test is that we won't have a
baseline before, so we just simply won't know what if any regression in
performance this test is causing (unless we have 2 different versions and the
capability to turn this functionality on and off at runtime).

[mfomitchev, 2015/05/27 17:24:29]

I didn't word this very well. When I said "current code" I meant current code in
Blink, i.e. before this CL. As for this CL - yes, three times at most, but
typically two as I explained above.
We can control which selection strategy is used by using
kTouchTextSelectionStrategy Chrome flag or SelectionStrategyType Blink
WebSetting. The "character" selection strategy is basically the old behavior
which can provide the baseline.

+        else
+            expandedBeyondWordBoundary = false;
 
-    bool expandedBeyondWordBoundary;
-    if (extentBaseOrder > 0)
-        expandedBeyondWordBoundary = comparePositions(extentPosition, currentWordBoundary) > 0;
-    else
-        expandedBeyondWordBoundary = comparePositions(extentPosition, currentWordBoundary) < 0;
-    if (expandedBeyondWordBoundary) {
-        m_granularity = WordGranularity;
-    } else if (thisMoveShrunkSelection) {
-        m_granularity = CharacterGranularity;
-        m_lastMoveShrunkSelection = true;
+        // The selection is shrunk if the extent changes position to be closer to
+        // the base, and the extent/base order wasn't switched.
+        thisMoveShrunkSelection = !extentBaseOrderSwitched && !selectionExpanded;
+
+        if (expandedBeyondWordBoundary)
+            m_granularity = WordGranularity;
+        else if (thisMoveShrunkSelection)
+            m_granularity = CharacterGranularity;
     }
 
-    m_lastMoveShrunkSelection = thisMoveShrunkSelection;
-    VisibleSelection newSelection = selection;
-    newSelection.setExtent(extentPosition);
+    VisiblePosition newSelectionExtent = newOffsetExtentPosition;
     if (m_granularity == WordGranularity) {
-        if (extentBaseOrder > 0)
-            newSelection.setEndRespectingGranularity(m_granularity, LeftWordIfOnBoundary);
-        else
-            newSelection.setStartRespectingGranularity(m_granularity, RightWordIfOnBoundary);
+        // Determine the bounds of the word where the extent is located.
+        // Set the selection extent to one of the two bounds depending on
+        // whether the extent is passed the middle of the word.
+        VisiblePosition boundBeforeExtent = nextWordBound(newOffsetExtentPosition, SearchDirection::SearchBackwards, BoundAdjust::CurrentPosIfOnBound);
+        VisiblePosition boundAfterExtent = nextWordBound(newOffsetExtentPosition, SearchDirection::SearchForward, BoundAdjust::CurrentPosIfOnBound);
+        int xMiddleBetweenBounds = (boundAfterExtent.absoluteCaretBounds().x() + boundBeforeExtent.absoluteCaretBounds().x()) / 2;
+        bool offsetExtentBeforeMiddle = newOffsetExtentPoint.x() < xMiddleBetweenBounds;
+
+        newSelectionExtent = offsetExtentBeforeMiddle ? boundBeforeExtent : boundAfterExtent;
+        // Update the offset if needed.
+        if (!inSameLine(newSelectionExtent, selection.visibleExtent())) {
+            m_offset = 0;
+        } else if (newSelectionExtent != selection.visibleExtent()
+            && ((newExtentBaseOrder > 0 && !offsetExtentBeforeMiddle) || (newExtentBaseOrder < 0 && offsetExtentBeforeMiddle))) {
+            m_offset = newSelectionExtent.absoluteCaretBounds().x() - extentPoint.x();
+        }
     }
 
+    // Only update the state if the selection actually changed as a result of
+    // this move.
+    if (newSelectionExtent != selection.visibleExtent())
+        m_state = thisMoveShrunkSelection ? StrategyState::Shrinking : StrategyState::Expanding;
+
+    m_subPositionCorrection = extentPoint + IntSize(m_offset, 0) - newSelectionExtent.absoluteCaretBounds().minXMaxYCorner();

[leviw_travelin_and_unemployed, 2015/05/26 20:25:50]

This is super magical and needs some explanation.

It'd be nice if instead of storing m_offset as an int, we stored it as an
IntSize so we could assert we didn't operate on caret positions that vary in Y
position.

[mfomitchev, 2015/05/26 22:32:47]

I like storing the offset as an int since it makes it explicit from the
definition that it is along a single axis. (Perhaps I should call it m_offset_x
though). We can do an assert either way. We can use a temp local IntSize
variable for that.

+    VisibleSelection newSelection = selection;
+    newSelection.setExtent(newSelectionExtent);
     return newSelection;
 }