Implementing directional selection strategy in Blink.

Source/core/editing/FrameSelection.cpp

 /*
  * Copyright (C) 2004, 2008, 2009, 2010 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 74 matching lines @@
 static inline LayoutUnit NoXPosForVerticalArrowNavigation()
 {
     return LayoutUnit::min();
 }
 
 static inline bool shouldAlwaysUseDirectionalSelection(LocalFrame* frame)
 {
     return !frame || frame->editor().behavior().shouldConsiderSelectionAsDirectional();
 }
 
+class GranularityStrategy {
+public:
+    virtual ~GranularityStrategy() { };
+    virtual void Clear();
+    // Returns the selection extent based on the strategy.
+    virtual VisiblePosition moveRangeSelectionExtent(const VisiblePosition&, const VisibleSelection&);

[yosin_UTC9, 2015/03/18 03:44:54]

Since, |moveRangeSelectionExtent()| returns position rather than changing
position in selection. We could name |granularExtent()| or better explaining
return value.

[mfomitchev, 2015/03/19 01:24:39]

Renamed and expanded on the comment. I wanted to capture the fact that this also
updates the internal state of the strategy, so I opted for |updateExtent|. I can
change to getGranularExtent or calculateGranularExtent if you prefer.

+protected:
+    GranularityStrategy() { };
+};
+
+class DefaultGranularityStrategy : public GranularityStrategy {
+public:
+    DefaultGranularityStrategy() { };
+    ~DefaultGranularityStrategy() override { };
+
+    void Clear() override { };
+    VisiblePosition moveRangeSelectionExtent(const VisiblePosition& extentPosition, const VisibleSelection&) override
+    {
+        return extentPosition;
+    };
+};
+
+// "Expand by word, shrink by character" selection strategy.
+// Uses character granularity when selection is shrinking. If the selection is expanding,
+// granularity doesn't change until the word boundary is passed, after which the granularity
+// switches to "word".
+class DirectionGranularityStrategy : public GranularityStrategy {
+public:
+    DirectionGranularityStrategy();
+    ~DirectionGranularityStrategy() override { };
+
+    void Clear() override;
+    VisiblePosition moveRangeSelectionExtent(const VisiblePosition&, const VisibleSelection&) override;
+private:
+    // Returns the next word boundary starting from |pos|. |direction| specifies the direction
+    // in which to search for the next bound. nextIfOnBound controls whether |pos| or the next boundary
+    // is returned when |pos| is located exactly on word boundary.
+    VisiblePosition nextWordBound(const VisiblePosition& /*pos*/, int /*direction*/, bool /*nextIfOnBound*/);
+
+    // Current selection granularity being used
+    TextGranularity m_granularity;
+    // Marks the boundary of the "current word". If the selection extent is extended
+    // beyond this threshold - the granularity will be changed to WordGranularity.
+    VisiblePosition m_wordBoundary;

[yosin_UTC9, 2015/03/18 03:44:54]

|VisiblePosition| isn't update at DOM mutation or style updates. It is dangerous
to keep it in object. I recommend to calculate it every time we need to compute
extent position.

Other options are:
 - Update |m_wordBoundary| and |m_extentPosition| every DOM mutation and style
updates. Note: |m_selection| updates for DOM mutation, see
didUpdateCharacterData(), didMergeTextNode(), etc. But, not for style
 - Use |Range| object.

Since, |VisiblePostion| depends on DOM position and Layout tree, it is fragile.
We don't recommend to keep in heap.

[mfomitchev, 2015/03/19 01:24:39]

Ok. I really only need m_wordBoundary to determine the "current word" when
oldExtent is on word boundary. Instead of saving m_wordBoundary I could save
whether the "current word" is on the right or on the left of the extent (when
extent is on the boundary). Does that sound okay?

For m_extentPosition perhaps we can use yoichio's suggestion and add a new
function setWithoutValidation(base, extent, start, end) to VisibleSelection and
save user extent there, while setting the start/end where we want them to be. I
had concerns about doing that since such a selection may not satisfy any of the
granularity invariants, but yoichio suggested that may be okay (see the top part
of comment #18). What do you think? If we leverage m_selection instead of saving
m_extentPosition - are we safe? You mention that m_selection doesn't update for
style changes, but if m_selection gets corrupted we are screwed anyway, right?

Also, to put this into perspective, it's probably not a big deal if we apply the
strategy incorrectly in some weird rare edge case. The  worst thing that can
happen is that we'll expand the selection with the wrong granularity, which is
not the end of the world. And the error should get corrected easily - typically
when the user moves the handle again.

[yosin_UTC9, 2015/03/23 07:20:39]

Saving |Position|, |VisibleSelection|, |VisiblePosition| is unsafe. Only |Range|
object is safe after mutation.

If you want to remember |VisiblePosition|, using |Range| then compute
|VisiblePosition| at use.

Or, relocate |VisiblePosition| in strategy object for each mutation.

+    // Cached extentPosition passed in moveRangeSelectionExtent
+    VisiblePosition m_extentPosition;
+};
+
+DirectionGranularityStrategy::DirectionGranularityStrategy()
+    : m_granularity(CharacterGranularity) { }
+
+void DirectionGranularityStrategy::Clear()
+{
+    m_wordBoundary.clear();
+    m_extentPosition.clear();
+    m_granularity = CharacterGranularity;
+}
+
+VisiblePosition DirectionGranularityStrategy::nextWordBound(
+    const VisiblePosition& pos,
+    int direction,
+    bool nextIfOnBound)
+{
+    return direction > 0 ? endOfWord(pos, nextIfOnBound ? RightWordIfOnBoundary : LeftWordIfOnBoundary)
+        : startOfWord(pos, nextIfOnBound ? LeftWordIfOnBoundary : RightWordIfOnBoundary);
+}
+
+VisiblePosition DirectionGranularityStrategy::moveRangeSelectionExtent(const VisiblePosition& extentPosition, const VisibleSelection& selection)
+{
+    const VisiblePosition& base = selection.visibleBase();
+    const VisiblePosition& oldExtent = selection.visibleExtent();
+
+    int extentBaseOrder = comparePositions(extentPosition, base);

[yoichio, 2015/03/17 05:54:41]

I wonder why this function looks procedural.
It is hard to catch full order of each position in this code.
First, you can use VisibleSelection::isBaseFirst() to detect current direction.
Let me assume direction is right.
If we have string "abc_def_hgi", we should have "ab|c_d>ef\_hgi" ('|' is base,
'>' is old extent and '\' is m_wordBoundary).
Then we have 4 cases
- |extentPosition| is before base
- |extentPosition| is between base and oldExtent
- |extentPosition| is between oldExtent and m_wordBoundary
- |extentPosition| is after m_wordBoundary
I miss on-boundary condition but it can be 4 cases. Does it make sense?

[mfomitchev, 2015/03/17 17:01:16]

Ok, lets enumerate your cases one to four from top to bottom. 
In case (1) (extentPosition is before base) we also need to recalculate the word
boundary, i.e. calculate the word boundary on the "other" side of the base. This
is the case when extentBaseOrderSwitched == true (lines 184-187). Then this
breaks up into two subcases: when extentPosition crosses the updated word
boundary, and when it doesn't. Lets call this 1.1 and 1.2 respectively. Now, we
don't actually handle these two subcases separately: once the word boundary is
recalculated and the granularity is reset to char (lines 184-187), handling of
(1.1) and (1.2) is merged with handling of cases cases (2) and (4) as we'll see
below.

Cases (4) and (1.1) are handled in lines 194-197. Cases (2) and (1.2) is lines
198-204. Note that 1.2 is basically a no-op - we've already reset the
granularity to char, so we don't need to do anything.

The remaining case is case (3) - we don't need to change anything other than
save the new extent position (which is always done in line 207), so no special
code for it.

Makes sense?

[yosin_UTC9, 2015/03/18 03:44:54]

It is better to ask |VisibleSelection| for DOM order of base/extent.

VisibleSelection newSelection(selection);
newSelection.setExtent(extentPosition);

Then you can use |newSelection.isBaseFirst()|

+    int oldExtentBaseOrder = comparePositions(oldExtent, base);
+    ASSERT(extentBaseOrder != 0);
+
+    bool extentBaseOrderSwitched = extentBaseOrder * oldExtentBaseOrder < 0;
+    VisiblePosition prevWordBoundary = m_wordBoundary;
+
+    // If the previous word boundary is empty, this must be the first call to moveRangeSelectionExtent()
+    // after a Clear(). Initialize prevWordBoundary based on the current selection.
+    if (prevWordBoundary.isNull()) {

[yoichio, 2015/03/17 05:54:41]

We can early return in this case.

[mfomitchev, 2015/03/17 17:01:16]

We can't actually. extentPosition can still be anywhere relative to
prevWordBoundary and oldExtent, so we need to do the full analysis as always.

+        ASSERT(m_extentPosition.isNull());
+        ASSERT(m_granularity == CharacterGranularity);
+        prevWordBoundary = nextWordBound(oldExtent, extentBaseOrder, false);

[yosin_UTC9, 2015/03/18 03:44:54]

How about factor out |FrameSelection::modifyXXX()| function to return position
rather than modifying selection? Then use here?

+    }
+    // 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) {
+        prevWordBoundary = nextWordBound(base, extentBaseOrder, true);
+        m_granularity = CharacterGranularity;
+    }
+
+    VisiblePosition newWordBoundary = prevWordBoundary;
+    bool expandedBeyondWordBoundary = extentBaseOrder > 0 ? comparePositions(extentPosition, prevWordBoundary) > 0
+        : comparePositions(extentPosition, prevWordBoundary) < 0;
+    // If the selection expanded beyond the word boundary - switch to word granularity and calculate
+    // the boundary of the new 'current word'.
+    if (expandedBeyondWordBoundary) {
+        if (m_granularity == CharacterGranularity)
+            m_granularity = WordGranularity;
+        newWordBoundary = nextWordBound(extentPosition, extentBaseOrder, true);
+    } else if (!extentBaseOrderSwitched) {
+        // If selection was shrunk - switch to character granularity and recalculate the boundary
+        // of the 'current word' in case the selection was shrunk beyond the old 'current word'.
+        if (!m_extentPosition.isNull() && extentBaseOrder * comparePositions(extentPosition, m_extentPosition) < 0) {
+            m_granularity = CharacterGranularity;
+            newWordBoundary = nextWordBound(extentPosition, extentBaseOrder, true);
+        }
+    }
+    m_wordBoundary = newWordBoundary;
+    m_extentPosition = extentPosition;
+
+    VisiblePosition visibleExtent = extentPosition;
+    if (m_granularity == WordGranularity)
+        visibleExtent = nextWordBound(extentPosition, extentBaseOrder, false);
+
+    return visibleExtent;
+}
+
 FrameSelection::FrameSelection(LocalFrame* frame)
     : m_frame(frame)
     , m_xPosForVerticalArrowNavigation(NoXPosForVerticalArrowNavigation())
     , m_observingVisibleSelection(false)
     , m_granularity(CharacterGranularity)
     , m_caretBlinkTimer(this, &FrameSelection::caretBlinkTimerFired)
     , m_caretRectDirty(true)
     , m_shouldPaintCaret(true)
     , m_isCaretBlinkingSuspended(false)
     , m_focused(frame && frame->page() && frame->page()->focusController().focusedFrame() == frame)
@@ skipping 109 matching lines @@
 
     newSelection.setIsDirectional(isDirectional); // Adjusting base and extent will make newSelection always directional
     if (m_selection == newSelection)
         return;
 
     setSelection(newSelection, granularity);
 }
 
 void FrameSelection::setSelection(const VisibleSelection& newSelection, SetSelectionOptions options, CursorAlignOnScroll align, TextGranularity granularity)
 {
+    if ((options & FrameSelection::DoNotClearStrategy) == 0)
+        granularityStrategy().Clear();
     bool closeTyping = options & CloseTyping;
     bool shouldClearTypingStyle = options & ClearTypingStyle;
     EUserTriggered userTriggered = selectionOptionsToUserTriggered(options);
 
     VisibleSelection s = validateSelection(newSelection);
     if (shouldAlwaysUseDirectionalSelection(m_frame))
         s.setIsDirectional(true);
 
     if (!m_frame) {
         m_selection = s;
@@ skipping 932 matching lines @@
         m_xPosForVerticalArrowNavigation = x;
     } else
         x = m_xPosForVerticalArrowNavigation;
 
     return x;
 }
 
 void FrameSelection::clear()
 {
     m_granularity = CharacterGranularity;
+    granularityStrategy().Clear();
     setSelection(VisibleSelection());
 }
 
 void FrameSelection::prepareForDestruction()
 {
     m_granularity = CharacterGranularity;
 
     m_caretBlinkTimer.stop();
 
     LayoutView* view = m_frame->contentRenderer();
@@ skipping 719 matching lines @@
         String text = plainText(start.deepEquivalent(), end.deepEquivalent());
         if (!text.isEmpty() && !isSeparator(text.characterStartingAt(0))) {
             setSelection(VisibleSelection(start, end), WordGranularity);
             return true;
         }
     }
 
     return false;
 }
 
-void FrameSelection::moveRangeSelectionExtent(const VisiblePosition& extentPosition, TextGranularity granularity)
+GranularityStrategy& FrameSelection::granularityStrategy()
 {
-    if (isNone())
+    if (m_granularityStrategy)
+        return *m_granularityStrategy;
+    // We do lazy initalization for m_granularityStrategy, because if we initialize it
+    // right in the constructor - the correct settings may not be set yet.
+    Settings* settings = m_frame ? m_frame->settings() : 0;
+    if (settings && settings->selectionStrategy() == StrategyDirection)
+        m_granularityStrategy = adoptPtr(new DirectionGranularityStrategy());
+    else
+        m_granularityStrategy = adoptPtr(new DefaultGranularityStrategy());
+    return *m_granularityStrategy;
+}
+
+void FrameSelection::moveRangeSelectionExtent(const VisiblePosition& extentPosition)
+{
+    const VisiblePosition base = m_selection.visibleBase();
+
+    if (isNone() || comparePositions(base, extentPosition) == 0)

[yosin_UTC9, 2015/03/18 03:44:54]

nit: |base == extentPosision|

[mfomitchev, 2015/03/19 01:24:39]

Done.

         return;
 
-    const VisiblePosition basePosition = m_selection.isBaseFirst() ?
-        m_selection.visibleStart() : m_selection.visibleEnd();
-
-    int order = comparePositions(basePosition, extentPosition);
-    if (!order)
-        return;
-
-    // Currently we support only CharaterGranularity and WordGranurarity.
-    // If |granurarity| is not of them, we fall back it to
-    // CharacterGranularity.
-    VisiblePosition newExtentPosition = extentPosition;
-    if (granularity == WordGranularity)
-        newExtentPosition = order < 0 ? endOfWord(extentPosition) : startOfWord(extentPosition);
-
-    VisibleSelection newSelection = VisibleSelection(basePosition, newExtentPosition);
-    setSelection(newSelection, FrameSelection::CloseTyping | FrameSelection::ClearTypingStyle | UserTriggered, FrameSelection::AlignCursorOnScrollIfNeeded, granularity);
+    VisiblePosition newExtentPosition = granularityStrategy().moveRangeSelectionExtent(extentPosition, selection());
+    VisibleSelection newSelection(base, newExtentPosition);
+    setSelection(
+        newSelection,
+        FrameSelection::CloseTyping | FrameSelection::ClearTypingStyle | FrameSelection::DoNotClearStrategy | UserTriggered,
+        FrameSelection::AlignCursorOnScrollIfNeeded,
+        CharacterGranularity);
 }
 
 void FrameSelection::moveRangeSelection(const VisiblePosition& basePosition, const VisiblePosition& extentPosition, TextGranularity granularity)
 {
     VisibleSelection newSelection(basePosition, extentPosition);
     newSelection.expandUsingGranularity(granularity);
 
     if (newSelection.isNone())
         return;
 
     setSelection(newSelection, granularity);
 }
 
 }
 
 #ifndef NDEBUG
 
 void showTree(const blink::FrameSelection& sel)
 {
     sel.showTreeForThis();
 }
 
 void showTree(const blink::FrameSelection* sel)
 {
     if (sel)
         sel->showTreeForThis();
 }
 
 #endif