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, 297 insertions, 0 deletions

diff --git a/src/gui/text/qtextengine.cpp b/src/gui/text/qtextengine.cpp
index 08d0eca7ac..0e649f0c2d 100644
--- a/src/gui/text/qtextengine.cpp
+++ b/src/gui/text/qtextengine.cpp
@@ -1304,6 +1304,7 @@ static void init(QTextEngine *e)
     e->ignoreBidi = false;
     e->cacheGlyphs = false;
     e->forceJustification = false;
+    e->visualMovement = false;
 
     e->layoutData = 0;
 
@@ -2737,6 +2738,180 @@ QFixed QTextEngine::leadingSpaceWidth(const QScriptLine &line)
     return width(line.from + pos, line.length - pos);
 }
 
+QFixed QTextEngine::alignLine(const QScriptLine &line)
+{
+    QFixed x = 0;
+    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 = option.alignment();
+        if (align & Qt::AlignJustify && isRightToLeft())
+            align = Qt::AlignRight;
+        if (align & Qt::AlignRight)
+            x = line.width - (line.textAdvance + leadingSpaceWidth(line));
+        else if (align & Qt::AlignHCenter)
+            x = (line.width - line.textAdvance)/2;
+    }
+    return x;
+}
+
+QFixed QTextEngine::offsetInLigature(const QScriptItem *si, int pos, int max, int glyph_pos)
+{
+    unsigned short *logClusters = this->logClusters(si);
+    const QGlyphLayout &glyphs = shapedGlyphs(si);
+
+    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;
+}
+
+int QTextEngine::previousLogicalPosition(int oldPos) const
+{
+    const HB_CharAttributes *attrs = attributes();
+    if (!attrs || oldPos < 0)
+        return oldPos;
+
+    if (oldPos <= 0)
+        return 0;
+    oldPos--;
+    while (oldPos && !attrs[oldPos].charStop)
+        oldPos--;
+    return oldPos;
+}
+
+int QTextEngine::nextLogicalPosition(int oldPos) const
+{
+    const HB_CharAttributes *attrs = attributes();
+    int len = block.isValid() ? block.length() - 1
+                              : layoutData->string.length();
+    Q_ASSERT(len <= layoutData->string.length());
+    if (!attrs || oldPos < 0 || oldPos >= len)
+        return oldPos;
+
+    oldPos++;
+    while (oldPos < len && !attrs[oldPos].charStop)
+        oldPos++;
+    return oldPos;
+}
+
+int QTextEngine::lineNumberForTextPosition(int pos)
+{
+    if (!layoutData)
+        itemize();
+    if (pos == layoutData->string.length() && lines.size())
+        return lines.size() - 1;
+    for (int i = 0; i < lines.size(); ++i) {
+        const QScriptLine& line = lines[i];
+        if (line.from + line.length > pos)
+            return i;
+    }
+    return -1;
+}
+
+void QTextEngine::insertionPointsForLine(int lineNum, QVector<int> &insertionPoints)
+{
+    QTextLineItemIterator iterator(this, lineNum);
+    bool rtl = isRightToLeft();
+    bool lastLine = lineNum >= lines.size() - 1;
+
+    while (!iterator.atEnd()) {
+        iterator.next();
+        const QScriptItem *si = &layoutData->items[iterator.item];
+        if (si->analysis.bidiLevel % 2) {
+            int i = iterator.itemEnd - 1, min = iterator.itemStart;
+            if (lastLine && (rtl ? iterator.atBeginning() : iterator.atEnd()))
+                i++;
+            for (; i >= min; i--)
+                insertionPoints.push_back(i);
+        } else {
+            int i = iterator.itemStart, max = iterator.itemEnd;
+            if (lastLine && (rtl ? iterator.atBeginning() : iterator.atEnd()))
+                max++;
+            for (; i < max; i++)
+                insertionPoints.push_back(i);
+        }
+    }
+}
+
+int QTextEngine::endOfLine(int lineNum)
+{
+    QVector<int> insertionPoints;
+    insertionPointsForLine(lineNum, insertionPoints);
+
+    if (insertionPoints.size() > 0)
+        return insertionPoints.last();
+    return 0;
+}
+
+int QTextEngine::beginningOfLine(int lineNum)
+{
+    QVector<int> insertionPoints;
+    insertionPointsForLine(lineNum, insertionPoints);
+
+    if (insertionPoints.size() > 0)
+        return insertionPoints.first();
+    return 0;
+}
+
+int QTextEngine::positionAfterVisualMovement(int pos, QTextCursor::MoveOperation op)
+{
+    if (!layoutData)
+        itemize();
+
+    bool moveRight = (op == QTextCursor::Right);
+    bool alignRight = isRightToLeft();
+    if (!layoutData->hasBidi)
+        return moveRight ^ alignRight ? nextLogicalPosition(pos) : previousLogicalPosition(pos);
+
+    int lineNum = lineNumberForTextPosition(pos);
+    Q_ASSERT(lineNum >= 0);
+
+    QVector<int> insertionPoints;
+    insertionPointsForLine(lineNum, insertionPoints);
+    int i, max = insertionPoints.size();
+    for (i = 0; i < max; i++)
+        if (pos == insertionPoints[i]) {
+            if (moveRight) {
+                if (i + 1 < max)
+                    return insertionPoints[i + 1];
+            } else {
+                if (i > 0)
+                    return insertionPoints[i - 1];
+            }
+
+            if (moveRight ^ alignRight) {
+                if (lineNum + 1 < lines.size())
+                    return alignRight ? endOfLine(lineNum + 1) : beginningOfLine(lineNum + 1);
+            }
+            else {
+                if (lineNum > 0)
+                    return alignRight ? beginningOfLine(lineNum - 1) : endOfLine(lineNum - 1);
+            }
+        }
+
+    return pos;
+}
+
 QStackTextEngine::QStackTextEngine(const QString &string, const QFont &f)
     : QTextEngine(string, f),
       _layoutData(string, _memory, MemSize)
@@ -2841,5 +3016,127 @@ glyph_metrics_t glyph_metrics_t::transformed(const QTransform &matrix) const
     return m;
 }
 
+QTextLineItemIterator::QTextLineItemIterator(QTextEngine *_eng, int _lineNum, const QPointF &pos,
+                                             const QTextLayout::FormatRange *_selection)
+    : eng(_eng),
+      line(eng->lines[_lineNum]),
+      si(0),
+      lineNum(_lineNum),
+      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 += eng->alignLine(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;
+}
+
+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 = eng->offsetInLigature(si, 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 += eng->offsetInLigature(si, to, eng->length(item), end_glyph);
+    }
+    return true;
+}
 
 QT_END_NAMESPACE