Support visual cursor movement for BIDI text

Bidi input can in some contexts be more intuitive if the cursor
works in visual way: pressing left arrow key always make cursor
move one character to the left regardless the language of text,
pressing right arrow key always make cursor move to the right.
It is also the behavior of Mac OS X. Based on the above reason
and requests from Symbian we implemented this support for visual
movement in BIDI text. 3 public properties are added to
QTextDocument, QTextLayout and QLineEdit respectively:

- QTextDocument::defaultCursorMoveStyle can be used to control
  the cursor behavior in all widgets based on QTextDocument,
  like QTextEdit, QPlainTextEdit, etc. When set to QTextCursor::
  Visual, it will enable visual movement for all the cursors in
  the corresponding text edit. Default is QTextCursor::Logical.

- QTextLayout::cursorMoveStyle is used for low-level cursor
  manipulation. When set to Visual, it will enable visual movement
  behavior for all the cursor related methods, including cursorToX,
  xToCursor and drawCursor. Default is Logical.

- QLineEdit::cursorMoveStyle is used to control cursor movement
  behavior in QLineEdit. Default is Logical.:

Task-number: QTBUG-13859
Reviewed-by: Eskil
(cherry picked from commit c480dd641f5d22d1ee72cb27bf39e24c6df65658)

1 files changed, 138 insertions, 256 deletions

diff --git a/src/gui/text/qtextlayout.cpp b/src/gui/text/qtextlayout.cpp
index fe0c53a480..9fc4e7f470 100644
--- a/src/gui/text/qtextlayout.cpp
+++ b/src/gui/text/qtextlayout.cpp
@@ -72,23 +72,6 @@ QT_BEGIN_NAMESPACE
 #define SuppressText 0x5012
 #define SuppressBackground 0x513
 
-static QFixed alignLine(QTextEngine *eng, const QScriptLine &line)
-{
-    QFixed x = 0;
-    eng->justify(line);
-    // if width is QFIXED_MAX that means we used setNumColumns() and that implicitly makes this line left aligned.
-    if (!line.justified && line.width != QFIXED_MAX) {
-        int align = eng->option.alignment();
-        if (align & Qt::AlignJustify && eng->isRightToLeft())
-            align = Qt::AlignRight;
-        if (align & Qt::AlignRight)
-            x = line.width - (line.textAdvance + eng->leadingSpaceWidth(line));
-        else if (align & Qt::AlignHCenter)
-            x = (line.width - line.textAdvance)/2;
-    }
-    return x;
-}
-
 /*!
     \class QTextLayout::FormatRange
     \reentrant
@@ -596,6 +579,30 @@ bool QTextLayout::cacheEnabled() const
 }
 
 /*!
+    Set the visual cursor movement style. If the QTextLayout is backed by
+    a document, you can ignore this and use the option in QTextDocument,
+    this option is for widgets like QLineEdit or custom widgets without
+    a QTextDocument. Default value is QTextCursor::Logical.
+
+    \sa setCursorMoveStyle()
+*/
+void QTextLayout::setCursorMoveStyle(QTextCursor::MoveStyle style)
+{
+    d->visualMovement = style == QTextCursor::Visual ? true : false;
+}
+
+/*!
+    The cursor movement style of this QTextLayout. The default is
+    QTextCursor::Logical.
+
+    \sa setCursorMoveStyle()
+*/
+QTextCursor::MoveStyle QTextLayout::cursorMoveStyle() const
+{
+    return d->visualMovement ? QTextCursor::Visual : QTextCursor::Logical;
+}
+
+/*!
     Begins the layout process.
 
     \sa endLayout()
@@ -718,6 +725,34 @@ int QTextLayout::previousCursorPosition(int oldPos, CursorMode mode) const
 }
 
 /*!
+    Returns the cursor position to the right of \a oldPos, next to it.
+    It's dependent on the visual position of characters, after bi-directional
+    reordering.
+
+    \sa leftCursorPosition(), nextCursorPosition()
+*/
+int QTextLayout::rightCursorPosition(int oldPos) const
+{
+    int newPos = d->positionAfterVisualMovement(oldPos, QTextCursor::Right);
+//    qDebug("%d -> %d", oldPos, newPos);
+    return newPos;
+}
+
+/*!
+    Returns the cursor position to the left of \a oldPos, next to it.
+    It's dependent on the visual position of characters, after bi-directional
+    reordering.
+
+    \sa rightCursorPosition(), previousCursorPosition()
+*/
+int QTextLayout::leftCursorPosition(int oldPos) const
+{
+    int newPos = d->positionAfterVisualMovement(oldPos, QTextCursor::Left);
+//    qDebug("%d -> %d", oldPos, newPos);
+    return newPos;
+}
+
+/*!/
     Returns true if position \a pos is a valid cursor position.
 
     In a Unicode context some positions in the text are not valid
@@ -815,16 +850,8 @@ QTextLine QTextLayout::lineAt(int i) const
 */
 QTextLine QTextLayout::lineForTextPosition(int pos) const
 {
-    for (int i = 0; i < d->lines.size(); ++i) {
-        const QScriptLine& line = d->lines[i];
-        if (line.from + (int)line.length > pos)
-            return QTextLine(i, d);
-    }
-    if (!d->layoutData)
-        d->itemize();
-    if (pos == d->layoutData->string.length() && d->lines.size())
-        return QTextLine(d->lines.size()-1, d);
-    return QTextLine();
+    int lineNum = d->lineNumberForTextPosition(pos);
+    return lineNum >= 0 ? lineAt(lineNum) : QTextLine();
 }
 
 /*!
@@ -919,201 +946,6 @@ void QTextLayout::setFlags(int flags)
     }
 }
 
-struct QTextLineItemIterator
-{
-    QTextLineItemIterator(QTextEngine *eng, int lineNum, const QPointF &pos = QPointF(),
-                          const QTextLayout::FormatRange *_selection = 0);
-
-    inline bool atEnd() const { return logicalItem >= nItems - 1; }
-    QScriptItem &next();
-
-    bool getSelectionBounds(QFixed *selectionX, QFixed *selectionWidth) const;
-    inline bool isOutsideSelection() const {
-        QFixed tmp1, tmp2;
-        return !getSelectionBounds(&tmp1, &tmp2);
-    }
-
-    QTextEngine *eng;
-
-    QFixed x;
-    QFixed pos_x;
-    const QScriptLine &line;
-    QScriptItem *si;
-
-    int lineEnd;
-    int firstItem;
-    int lastItem;
-    int nItems;
-    int logicalItem;
-    int item;
-    int itemLength;
-
-    int glyphsStart;
-    int glyphsEnd;
-    int itemStart;
-    int itemEnd;
-
-    QFixed itemWidth;
-
-    QVarLengthArray<int> visualOrder;
-    QVarLengthArray<uchar> levels;
-
-    const QTextLayout::FormatRange *selection;
-};
-
-QTextLineItemIterator::QTextLineItemIterator(QTextEngine *_eng, int lineNum, const QPointF &pos,
-                                             const QTextLayout::FormatRange *_selection)
-    : eng(_eng),
-      line(eng->lines[lineNum]),
-      si(0),
-      lineEnd(line.from + line.length),
-      firstItem(eng->findItem(line.from)),
-      lastItem(eng->findItem(lineEnd - 1)),
-      nItems((firstItem >= 0 && lastItem >= firstItem)? (lastItem-firstItem+1) : 0),
-      logicalItem(-1),
-      item(-1),
-      visualOrder(nItems),
-      levels(nItems),
-      selection(_selection)
-{
-    pos_x = x = QFixed::fromReal(pos.x());
-
-    x += line.x;
-
-    x += alignLine(eng, line);
-
-    for (int i = 0; i < nItems; ++i)
-        levels[i] = eng->layoutData->items[i+firstItem].analysis.bidiLevel;
-    QTextEngine::bidiReorder(nItems, levels.data(), visualOrder.data());
-
-    eng->shapeLine(line);
-}
-
-QScriptItem &QTextLineItemIterator::next()
-{
-    x += itemWidth;
-
-    ++logicalItem;
-    item = visualOrder[logicalItem] + firstItem;
-    itemLength = eng->length(item);
-    si = &eng->layoutData->items[item];
-    if (!si->num_glyphs)
-        eng->shape(item);
-
-    if (si->analysis.flags >= QScriptAnalysis::TabOrObject) {
-        itemWidth = si->width;
-        return *si;
-    }
-
-    unsigned short *logClusters = eng->logClusters(si);
-    QGlyphLayout glyphs = eng->shapedGlyphs(si);
-
-    itemStart = qMax(line.from, si->position);
-    glyphsStart = logClusters[itemStart - si->position];
-    if (lineEnd < si->position + itemLength) {
-        itemEnd = lineEnd;
-        glyphsEnd = logClusters[itemEnd-si->position];
-    } else {
-        itemEnd = si->position + itemLength;
-        glyphsEnd = si->num_glyphs;
-    }
-    // show soft-hyphen at line-break
-    if (si->position + itemLength >= lineEnd
-        && eng->layoutData->string.at(lineEnd - 1) == 0x00ad)
-        glyphs.attributes[glyphsEnd - 1].dontPrint = false;
-
-    itemWidth = 0;
-    for (int g = glyphsStart; g < glyphsEnd; ++g)
-        itemWidth += glyphs.effectiveAdvance(g);
-
-    return *si;
-}
-
-static QFixed offsetInLigature(const unsigned short *logClusters,
-                               const QGlyphLayout &glyphs,
-                               int pos, int max, int glyph_pos)
-{
-    int offsetInCluster = 0;
-    for (int i = pos - 1; i >= 0; i--) {
-        if (logClusters[i] == glyph_pos)
-            offsetInCluster++;
-        else
-            break;
-    }
-
-    // in the case that the offset is inside a (multi-character) glyph,
-    // interpolate the position.
-    if (offsetInCluster > 0) {
-        int clusterLength = 0;
-        for (int i = pos - offsetInCluster; i < max; i++) {
-            if (logClusters[i] == glyph_pos)
-                clusterLength++;
-            else
-                break;
-        }
-        if (clusterLength)
-            return glyphs.advances_x[glyph_pos] * offsetInCluster / clusterLength;
-    }
-
-    return 0;
-}
-
-bool QTextLineItemIterator::getSelectionBounds(QFixed *selectionX, QFixed *selectionWidth) const
-{
-    *selectionX = *selectionWidth = 0;
-
-    if (!selection)
-        return false;
-
-    if (si->analysis.flags >= QScriptAnalysis::TabOrObject) {
-        if (si->position >= selection->start + selection->length
-            || si->position + itemLength <= selection->start)
-            return false;
-
-        *selectionX = x;
-        *selectionWidth = itemWidth;
-    } else {
-        unsigned short *logClusters = eng->logClusters(si);
-        QGlyphLayout glyphs = eng->shapedGlyphs(si);
-
-        int from = qMax(itemStart, selection->start) - si->position;
-        int to = qMin(itemEnd, selection->start + selection->length) - si->position;
-        if (from >= to)
-            return false;
-
-        int start_glyph = logClusters[from];
-        int end_glyph = (to == eng->length(item)) ? si->num_glyphs : logClusters[to];
-        QFixed soff;
-        QFixed swidth;
-        if (si->analysis.bidiLevel %2) {
-            for (int g = glyphsEnd - 1; g >= end_glyph; --g)
-                soff += glyphs.effectiveAdvance(g);
-            for (int g = end_glyph - 1; g >= start_glyph; --g)
-                swidth += glyphs.effectiveAdvance(g);
-        } else {
-            for (int g = glyphsStart; g < start_glyph; ++g)
-                soff += glyphs.effectiveAdvance(g);
-            for (int g = start_glyph; g < end_glyph; ++g)
-                swidth += glyphs.effectiveAdvance(g);
-        }
-
-        // If the starting character is in the middle of a ligature,
-        // selection should only contain the right part of that ligature
-        // glyph, so we need to get the width of the left part here and
-        // add it to *selectionX
-        QFixed leftOffsetInLigature = offsetInLigature(logClusters, glyphs, from,
-                                                       to, start_glyph);
-        *selectionX = x + soff + leftOffsetInLigature;
-        *selectionWidth = swidth - leftOffsetInLigature;
-        // If the ending character is also part of a ligature, swidth does
-        // not contain that part yet, we also need to find out the width of
-        // that left part
-        *selectionWidth += offsetInLigature(logClusters, glyphs, to,
-                                            eng->length(item), end_glyph);
-    }
-    return true;
-}
-
 static void addSelectedRegionsToPath(QTextEngine *eng, int lineNumber, const QPointF &pos, QTextLayout::FormatRange *selection,
                                      QPainterPath *region, QRectF boundingRect)
 {
@@ -1382,18 +1214,9 @@ void QTextLayout::drawCursor(QPainter *p, const QPointF &pos, int cursorPosition
     QFixed pos_y = QFixed::fromReal(position.y());
 
     cursorPosition = qBound(0, cursorPosition, d->layoutData->string.length());
-    int line = 0;
-    if (cursorPosition == d->layoutData->string.length()) {
-        line = d->lines.size() - 1;
-    } else {
-        // ### binary search
-        for (line = 0; line < d->lines.size(); line++) {
-            const QScriptLine &sl = d->lines[line];
-            if (sl.from <= cursorPosition && sl.from + (int)sl.length > cursorPosition)
-                break;
-        }
-    }
-
+    int line = d->lineNumberForTextPosition(cursorPosition);
+    if (line < 0)
+        line = 0;
     if (line >= d->lines.size())
         return;
 
@@ -1402,7 +1225,15 @@ void QTextLayout::drawCursor(QPainter *p, const QPointF &pos, int cursorPosition
 
     qreal x = position.x() + l.cursorToX(cursorPosition);
 
-    int itm = d->findItem(cursorPosition - 1);
+    int itm;
+
+    if (d->visualCursorMovement()) {
+        if (cursorPosition == sl.from + sl.length)
+            cursorPosition--;
+        itm = d->findItem(cursorPosition);
+    } else
+        itm = d->findItem(cursorPosition - 1);
+
     QFixed base = sl.base();
     QFixed descent = sl.descent;
     bool rightToLeft = d->isRightToLeft();
@@ -1512,7 +1343,7 @@ QRectF QTextLine::rect() const
 QRectF QTextLine::naturalTextRect() const
 {
     const QScriptLine& sl = eng->lines[i];
-    QFixed x = sl.x + alignLine(eng, sl);
+    QFixed x = sl.x + eng->alignLine(sl);
 
     QFixed width = sl.textWidth;
     if (sl.justified)
@@ -2635,9 +2466,10 @@ qreal QTextLine::cursorToX(int *cursorPos, Edge edge) const
         eng->itemize();
 
     const QScriptLine &line = eng->lines[i];
+    bool lastLine = i >= eng->lines.size() - 1;
 
     QFixed x = line.x;
-    x += alignLine(eng, line);
+    x += eng->alignLine(line);
 
     if (!i && !eng->layoutData->items.size()) {
         *cursorPos = 0;
@@ -2723,21 +2555,29 @@ qreal QTextLine::cursorToX(int *cursorPos, Edge edge) const
     logClusters = eng->logClusters(si);
     glyphs = eng->shapedGlyphs(si);
     if (si->analysis.flags >= QScriptAnalysis::TabOrObject) {
-        if(pos == l)
+        if (pos == (reverse ? 0 : l))
             x += si->width;
     } else {
+        bool rtl = eng->isRightToLeft();
+        bool visual = eng->visualCursorMovement();
         if (reverse) {
             int end = qMin(lineEnd, si->position + l) - si->position;
             int glyph_end = end == l ? si->num_glyphs : logClusters[end];
-            for (int i = glyph_end - 1; i >= glyph_pos; i--)
+            int glyph_start = glyph_pos;
+            if (visual && !rtl && !(lastLine && itm == (visualOrder[nItems - 1] + firstItem)))
+                glyph_start++;
+            for (int i = glyph_end - 1; i >= glyph_start; i--)
                 x += glyphs.effectiveAdvance(i);
         } else {
             int start = qMax(line.from - si->position, 0);
             int glyph_start = logClusters[start];
-            for (int i = glyph_start; i < glyph_pos; i++)
+            int glyph_end = glyph_pos;
+            if (!visual || !rtl || (lastLine && itm == visualOrder[0] + firstItem))
+                glyph_end--;
+            for (int i = glyph_start; i <= glyph_end; i++)
                 x += glyphs.effectiveAdvance(i);
         }
-        x += offsetInLigature(logClusters, glyphs, pos, line.length, glyph_pos);
+        x += eng->offsetInLigature(si, pos, line.length, glyph_pos);
     }
 
     *cursorPos = pos + si->position;
@@ -2756,6 +2596,8 @@ int QTextLine::xToCursor(qreal _x, CursorPosition cpos) const
 {
     QFixed x = QFixed::fromReal(_x);
     const QScriptLine &line = eng->lines[i];
+    bool lastLine = i >= eng->lines.size() - 1;
+    int lineNum = i;
 
     if (!eng->layoutData)
         eng->itemize();
@@ -2773,7 +2615,7 @@ int QTextLine::xToCursor(qreal _x, CursorPosition cpos) const
         return 0;
 
     x -= line.x;
-    x -= alignLine(eng, line);
+    x -= eng->alignLine(line);
 //     qDebug("xToCursor: x=%f, cpos=%d", x.toReal(), cpos);
 
     QVarLengthArray<int> visualOrder(nItems);
@@ -2782,6 +2624,7 @@ int QTextLine::xToCursor(qreal _x, CursorPosition cpos) const
         levels[i] = eng->layoutData->items[i+firstItem].analysis.bidiLevel;
     QTextEngine::bidiReorder(nItems, levels.data(), visualOrder.data());
 
+    bool visual = eng->visualCursorMovement();
     if (x <= 0) {
         // left of first item
         int item = visualOrder[0]+firstItem;
@@ -2798,8 +2641,13 @@ int QTextLine::xToCursor(qreal _x, CursorPosition cpos) const
                || (line.justified && x < line.width)) {
         // has to be in one of the runs
         QFixed pos;
+        bool rtl = eng->isRightToLeft();
 
         eng->shapeLine(line);
+        QVector<int> insertionPoints;
+        if (visual && rtl)
+            eng->insertionPointsForLine(lineNum, insertionPoints);
+        int nchars = 0;
         for (int i = 0; i < nItems; ++i) {
             int item = visualOrder[i]+firstItem;
             QScriptItem &si = eng->layoutData->items[item];
@@ -2829,6 +2677,7 @@ int QTextLine::xToCursor(qreal _x, CursorPosition cpos) const
 
             if (pos + item_width < x) {
                 pos += item_width;
+                nchars += end;
                 continue;
             }
 //             qDebug("      inside run");
@@ -2873,27 +2722,60 @@ int QTextLine::xToCursor(qreal _x, CursorPosition cpos) const
             } else {
                 QFixed dist = INT_MAX/256;
                 if (si.analysis.bidiLevel % 2) {
-                    pos += item_width;
-                    while (gs <= ge) {
-                        if (glyphs.attributes[gs].clusterStart && qAbs(x-pos) < dist) {
-                            glyph_pos = gs;
-                            dist = qAbs(x-pos);
+                    if (!visual || rtl || (lastLine && i == nItems - 1)) {
+                        pos += item_width;
+                        while (gs <= ge) {
+                            if (glyphs.attributes[gs].clusterStart && qAbs(x-pos) < dist) {
+                                glyph_pos = gs;
+                                dist = qAbs(x-pos);
+                            }
+                            pos -= glyphs.effectiveAdvance(gs);
+                            ++gs;
+                        }
+                    } else {
+                        while (ge >= gs) {
+                            if (glyphs.attributes[ge].clusterStart && qAbs(x-pos) < dist) {
+                                glyph_pos = ge;
+                                dist = qAbs(x-pos);
+                            }
+                            pos += glyphs.effectiveAdvance(ge);
+                            --ge;
                         }
-                        pos -= glyphs.effectiveAdvance(gs);
-                        ++gs;
                     }
                 } else {
-                    while (gs <= ge) {
-                        if (glyphs.attributes[gs].clusterStart && qAbs(x-pos) < dist) {
-                            glyph_pos = gs;
-                            dist = qAbs(x-pos);
+                    if (!visual || !rtl || (lastLine && i == 0)) {
+                        while (gs <= ge) {
+                            if (glyphs.attributes[gs].clusterStart && qAbs(x-pos) < dist) {
+                                glyph_pos = gs;
+                                dist = qAbs(x-pos);
+                            }
+                            pos += glyphs.effectiveAdvance(gs);
+                            ++gs;
                         }
-                        pos += glyphs.effectiveAdvance(gs);
-                        ++gs;
+                    } else {
+                        QFixed oldPos = pos;
+                        while (gs <= ge) {
+                            pos += glyphs.effectiveAdvance(gs);
+                            if (glyphs.attributes[gs].clusterStart && qAbs(x-pos) < dist) {
+                                glyph_pos = gs;
+                                dist = qAbs(x-pos);
+                            }
+                            ++gs;
+                        }
+                        pos = oldPos;
                     }
                 }
-                if (qAbs(x-pos) < dist)
+                if (qAbs(x-pos) < dist) {
+                    if (visual) {
+                        if (!rtl && i < nItems - 1) {
+                            nchars += end;
+                            continue;
+                        }
+                        if (rtl && nchars > 0)
+                            return insertionPoints[lastLine ? nchars : nchars - 1];
+                    }
                     return si.position + end;
+                }
             }
             Q_ASSERT(glyph_pos != -1);
             int j;