Fix selection of text with negative right bearing

Selecting text with a negative right bearing (like italic text)
would cause clipping to occur at the edges of the characters.

The algorithm for drawing text and text selection tried to
divide the text into two: 1. Selected text, and 2. Unselected text.
However, the selected text might be drawn outside the selection
rect when it has a negative right bearing. Similarly, unselected
text before the selection might overlap with the selection rect
when it has a negative right bearing, or unselected text after
the selection might overlap if it has a negative left bearing.

See added test textinput_italic_selected.qml for an example.

To rectify this, we do drawing of selected text like this:
1. Draw all text with unselected color
2. Draw selection rects
3. Draw the following in the selection text color and clipped
   to the selection rect:
     A. The selected text
     B. The unselected text right before the selection
     C. The unselected text right after the selection

To avoid drawing the same text twice for extra boldness,
we check if 3B or 3C actually contain 3A, in which case we skip
3A.

[ChangeLog][Text] Fixed clipping when selecting text with negative
right bearing.

Task-number: QTBUG-34233
Change-Id: I3506b3a72a2d963c5f24c5b819bbb92769b9aee1
Reviewed-by: Samuel Nevala <samuel.nevala@digia.com>
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
Reviewed-by: Gunnar Sletta <gunnar@sletta.org>

8 files changed, 270 insertions, 63 deletions

diff --git a/src/quick/items/qquicktextnodeengine.cpp b/src/quick/items/qquicktextnodeengine.cpp
index 359d7256f2..f746fe8b1b 100644
--- a/src/quick/items/qquicktextnodeengine.cpp
+++ b/src/quick/items/qquicktextnodeengine.cpp
@@ -51,7 +51,7 @@ QT_BEGIN_NAMESPACE
 
 void QQuickTextNodeEngine::BinaryTreeNode::insert(QVarLengthArray<BinaryTreeNode, 16> *binaryTree, const QGlyphRun &glyphRun, SelectionState selectionState,
                                              QQuickTextNode::Decorations decorations, const QColor &textColor,
-                                             const QColor &backgroundColor, const QPointF &position)
+                                             const QColor &backgroundColor, const QPointF &position, int rangeStart, int rangeEnd)
 {
     QRectF searchRect = glyphRun.boundingRect();
     searchRect.translate(position);
@@ -66,7 +66,7 @@ void QQuickTextNodeEngine::BinaryTreeNode::insert(QVarLengthArray<BinaryTreeNode
 
     qreal ascent = glyphRun.rawFont().ascent();
     insert(binaryTree, BinaryTreeNode(glyphRun, selectionState, searchRect, decorations,
-                                      textColor, backgroundColor, position, ascent));
+                                      textColor, backgroundColor, position, ascent, rangeStart, rangeEnd));
 }
 
 void QQuickTextNodeEngine::BinaryTreeNode::insert(QVarLengthArray<BinaryTreeNode, 16> *binaryTree, const BinaryTreeNode &binaryTreeNode)
@@ -247,12 +247,9 @@ void QQuickTextNodeEngine::processCurrentLine()
             // selection rect to the graph, and we add decoration every time the
             // selection state changes, because that means the text color changes
             if (node == 0 || node->selectionState != currentSelectionState) {
-                if (node != 0)
-                    currentRect.setRight(node->boundingRect.left());
                 currentRect.setY(m_position.y() + m_currentLine.y());
                 currentRect.setHeight(m_currentLine.height());
 
-                // Draw selection all the way up to the left edge of the unselected item
                 if (currentSelectionState == Selected)
                     m_selectionRects.append(currentRect);
 
@@ -288,8 +285,10 @@ void QQuickTextNodeEngine::processCurrentLine()
             }
 
             if (node != 0) {
-                node->clipNode = currentClipNode;
-                currentClipNodeUsed = true;
+                if (node->selectionState == Selected) {
+                    node->clipNode = currentClipNode;
+                    currentClipNodeUsed = true;
+                }
 
                 decorationRect = node->boundingRect;
 
@@ -442,17 +441,19 @@ void QQuickTextNodeEngine::addTextObject(const QPointF &position, const QTextCha
     }
 }
 
-void QQuickTextNodeEngine::addUnselectedGlyphs(const QGlyphRun &glyphRun)
+void QQuickTextNodeEngine::addUnselectedGlyphs(const QGlyphRun &glyphRun, int rangeStart, int rangeEnd)
 {
     BinaryTreeNode::insert(&m_currentLineTree, glyphRun, Unselected,
-                           QQuickTextNode::NoDecoration, m_textColor, m_backgroundColor, m_position);
+                           QQuickTextNode::NoDecoration, m_textColor, m_backgroundColor, m_position,
+                           rangeStart, rangeEnd);
 }
 
-void QQuickTextNodeEngine::addSelectedGlyphs(const QGlyphRun &glyphRun)
+void QQuickTextNodeEngine::addSelectedGlyphs(const QGlyphRun &glyphRun, int rangeStart, int rangeEnd)
 {
     int currentSize = m_currentLineTree.size();
     BinaryTreeNode::insert(&m_currentLineTree, glyphRun, Selected,
-                           QQuickTextNode::NoDecoration, m_textColor, m_backgroundColor, m_position);
+                           QQuickTextNode::NoDecoration, m_textColor, m_backgroundColor, m_position,
+                           rangeStart, rangeEnd);
     m_hasSelection = m_hasSelection || m_currentLineTree.size() > currentSize;
 }
 
@@ -525,17 +526,15 @@ void QQuickTextNodeEngine::addGlyphsInRange(int rangeStart, int rangeLength,
         QList<QGlyphRun> glyphRuns = line.glyphRuns(rangeStart, rangeLength);
         for (int j=0; j<glyphRuns.size(); ++j) {
             const QGlyphRun &glyphRun = glyphRuns.at(j);
-            addUnselectedGlyphs(glyphRun);
+            addUnselectedGlyphs(glyphRun, rangeStart, rangeEnd - 1);
         }
     } else {
         if (rangeStart < selectionStart) {
-            QList<QGlyphRun> glyphRuns = line.glyphRuns(rangeStart,
-                                                        qMin(selectionStart - rangeStart,
-                                                             rangeLength));
-
+            int length = qMin(selectionStart - rangeStart, rangeLength);
+            QList<QGlyphRun> glyphRuns = line.glyphRuns(rangeStart, length);
             for (int j=0; j<glyphRuns.size(); ++j) {
                 const QGlyphRun &glyphRun = glyphRuns.at(j);
-                addUnselectedGlyphs(glyphRun);
+                addUnselectedGlyphs(glyphRun, rangeStart, rangeStart + length - 1);
             }
         }
 
@@ -546,15 +545,18 @@ void QQuickTextNodeEngine::addGlyphsInRange(int rangeStart, int rangeLength,
 
             for (int j=0; j<glyphRuns.size(); ++j) {
                 const QGlyphRun &glyphRun = glyphRuns.at(j);
-                addSelectedGlyphs(glyphRun);
+                addSelectedGlyphs(glyphRun, start, start + length - 1);
+                addUnselectedGlyphs(glyphRun, start, start + length - 1);
             }
         }
 
         if (selectionEnd >= rangeStart && selectionEnd < rangeEnd) {
-            QList<QGlyphRun> glyphRuns = line.glyphRuns(selectionEnd + 1, rangeEnd - selectionEnd - 1);
+            int start = selectionEnd + 1;
+            int length = rangeEnd - selectionEnd - 1;
+            QList<QGlyphRun> glyphRuns = line.glyphRuns(start, length);
             for (int j=0; j<glyphRuns.size(); ++j) {
                 const QGlyphRun &glyphRun = glyphRuns.at(j);
-                addUnselectedGlyphs(glyphRun);
+                addUnselectedGlyphs(glyphRun, start, start + length - 1);
             }
         }
     }
@@ -633,37 +635,12 @@ void  QQuickTextNodeEngine::addToSceneGraph(QQuickTextNode *parentNode,
     if (m_currentLine.isValid())
         processCurrentLine();
 
-
-    for (int i=0; i<m_backgrounds.size(); ++i) {
-        const QRectF &rect = m_backgrounds.at(i).first;
-        const QColor &color = m_backgrounds.at(i).second;
-
-        parentNode->addRectangleNode(rect, color);
-    }
-
-    // First, prepend all selection rectangles to the tree
-    for (int i=0; i<m_selectionRects.size(); ++i) {
-        const QRectF &rect = m_selectionRects.at(i);
-
-        parentNode->addRectangleNode(rect, m_selectionColor);
-    }
-
-    // Finally, add decorations for each node to the tree.
-    for (int i=0; i<m_lines.size(); ++i) {
-        const TextDecoration &textDecoration = m_lines.at(i);
-
-        QColor color = textDecoration.selectionState == Selected
-                ? m_selectedTextColor
-                : textDecoration.color;
-
-        parentNode->addRectangleNode(textDecoration.rect, color);
-    }
-
     // Then, go through all the nodes for all lines and combine all QGlyphRuns with a common
     // font, selection state and clip node.
     typedef QPair<QFontEngine *, QPair<QQuickDefaultClipNode *, QPair<QRgb, int> > > KeyType;
     QHash<KeyType, BinaryTreeNode *> map;
     QList<BinaryTreeNode *> nodes;
+    QList<BinaryTreeNode *> imageNodes;
     for (int i = 0; i < m_processedNodes.size(); ++i) {
         BinaryTreeNode *node = m_processedNodes.data() + i;
 
@@ -696,31 +673,137 @@ void  QQuickTextNodeEngine::addToSceneGraph(QQuickTextNode *parentNode,
                 otherGlyphRun.setGlyphIndexes(otherGlyphIndexes);
                 otherGlyphRun.setPositions(otherGlyphPositions);
 
+                otherNode->ranges += node->ranges;
+
             } else {
                 map.insert(key, node);
                 nodes.append(node);
             }
         } else {
-            parentNode->addImage(node->boundingRect, node->image);
-            if (node->selectionState == Selected) {
-                QColor color = m_selectionColor;
-                color.setAlpha(128);
-                parentNode->addRectangleNode(node->boundingRect, color);
-            }
+            imageNodes.append(node);
         }
     }
 
-    foreach (const BinaryTreeNode *node, nodes) {
+    for (int i = 0; i < m_backgrounds.size(); ++i) {
+        const QRectF &rect = m_backgrounds.at(i).first;
+        const QColor &color = m_backgrounds.at(i).second;
 
+        parentNode->addRectangleNode(rect, color);
+    }
+
+    // Add all unselected text first
+    for (int i = 0; i < nodes.size(); ++i) {
+        const BinaryTreeNode *node = nodes.at(i);
+        if (node->selectionState == Unselected)
+            parentNode->addGlyphs(node->position, node->glyphRun, node->color, style, styleColor, 0);
+    }
+
+    for (int i = 0; i < imageNodes.size(); ++i) {
+        const BinaryTreeNode *node = imageNodes.at(i);
+        if (node->selectionState == Unselected)
+            parentNode->addImage(node->boundingRect, node->image);
+    }
+
+    // Then, prepend all selection rectangles to the tree
+    for (int i = 0; i < m_selectionRects.size(); ++i) {
+        const QRectF &rect = m_selectionRects.at(i);
+
+        parentNode->addRectangleNode(rect, m_selectionColor);
+    }
+
+    // Add decorations for each node to the tree.
+    for (int i = 0; i < m_lines.size(); ++i) {
+        const TextDecoration &textDecoration = m_lines.at(i);
+
+        QColor color = textDecoration.selectionState == Selected
+                ? m_selectedTextColor
+                : textDecoration.color;
+
+        parentNode->addRectangleNode(textDecoration.rect, color);
+    }
+
+    // Finally add the selected text on top of everything
+    for (int i = 0; i < nodes.size(); ++i) {
+        const BinaryTreeNode *node = nodes.at(i);
         QQuickDefaultClipNode *clipNode = node->clipNode;
-        if (clipNode != 0 && clipNode->parent() == 0 )
+        if (clipNode != 0 && clipNode->parent() == 0)
             parentNode->appendChildNode(clipNode);
 
-        QColor color = node->selectionState == Selected
-                ? m_selectedTextColor
-                : node->color;
+        if (node->selectionState == Selected) {
+            QColor color = m_selectedTextColor;
+            int previousNodeIndex = i - 1;
+            int nextNodeIndex = i + 1;
+            const BinaryTreeNode *previousNode = previousNodeIndex < 0 ? 0 : nodes.at(previousNodeIndex);
+            while (previousNode != 0 && qFuzzyCompare(previousNode->boundingRect.left(), node->boundingRect.left()))
+                previousNode = --previousNodeIndex < 0 ? 0 : nodes.at(previousNodeIndex);
+
+            const BinaryTreeNode *nextNode = nextNodeIndex == nodes.size() ? 0 : nodes.at(nextNodeIndex);
+
+            if (previousNode != 0 && previousNode->selectionState == Unselected)
+                parentNode->addGlyphs(previousNode->position, previousNode->glyphRun, color, style, styleColor, clipNode);
+
+            if (nextNode != 0 && nextNode->selectionState == Unselected)
+                parentNode->addGlyphs(nextNode->position, nextNode->glyphRun, color, style, styleColor, clipNode);
+
+            // If the previous or next node completely overlaps this one, then we have already drawn the glyphs of
+            // this node
+            bool drawCurrent = false;
+            if (previousNode != 0 || nextNode != 0) {
+                for (int i = 0; i < node->ranges.size(); ++i) {
+                    const QPair<int, int> &range = node->ranges.at(i);
+
+                    int rangeLength = range.second - range.first + 1;
+                    if (previousNode != 0) {
+                        for (int j = 0; j < previousNode->ranges.size(); ++j) {
+                            const QPair<int, int> &otherRange = previousNode->ranges.at(j);
+                            if (range.first <= otherRange.second && range.second >= otherRange.first) {
+                                int start = qMax(range.first, otherRange.first);
+                                int end = qMin(range.second, otherRange.second);
+                                rangeLength -= end - start + 1;
+                                if (rangeLength == 0)
+                                    break;
+                            }
+                        }
+                    }
+
+                    if (nextNode != 0 && rangeLength > 0) {
+                        for (int j = 0; j < nextNode->ranges.size(); ++j) {
+                            const QPair<int, int> &otherRange = nextNode->ranges.at(j);
+
+                            if (range.first <= otherRange.second && range.second >= otherRange.first) {
+                                int start = qMax(range.first, otherRange.first);
+                                int end = qMin(range.second, otherRange.second);
+                                rangeLength -= end - start + 1;
+                                if (rangeLength == 0)
+                                    break;
+                            }
+                        }
+                    }
+
+                    if (rangeLength > 0) {
+                        drawCurrent = true;
+                        break;
+                    }
+                }
+            } else {
+                drawCurrent = true;
+            }
+
+            if (drawCurrent)
+                parentNode->addGlyphs(node->position, node->glyphRun, color, style, styleColor, clipNode);
+        }
+    }
 
-        parentNode->addGlyphs(node->position, node->glyphRun, color, style, styleColor, clipNode);
+    for (int i = 0; i < imageNodes.size(); ++i) {
+        const BinaryTreeNode *node = imageNodes.at(i);
+        if (node->selectionState == Selected) {
+            parentNode->addImage(node->boundingRect, node->image);
+            if (node->selectionState == Selected) {
+                QColor color = m_selectionColor;
+                color.setAlpha(128);
+                parentNode->addRectangleNode(node->boundingRect, color);
+            }
+        }
     }
 }
 
@@ -844,7 +927,7 @@ void QQuickTextNodeEngine::addTextBlock(QTextDocument *textDocument, const QText
 
             QList<QGlyphRun> glyphRuns = layout.glyphRuns();
             for (int i=0; i<glyphRuns.size(); ++i)
-                addUnselectedGlyphs(glyphRuns.at(i));
+                addUnselectedGlyphs(glyphRuns.at(i), 0, layout.text().length() - 1);
         }
     }
 
diff --git a/src/quick/items/qquicktextnodeengine_p.h b/src/quick/items/qquicktextnodeengine_p.h
index 9a64853dd3..142375b5a3 100644
--- a/src/quick/items/qquicktextnodeengine_p.h
+++ b/src/quick/items/qquicktextnodeengine_p.h
@@ -75,10 +75,11 @@ public:
 
         BinaryTreeNode(const QGlyphRun &g, SelectionState selState, const QRectF &brect,
                        const QQuickTextNode::Decorations &decs, const QColor &c, const QColor &bc,
-                       const QPointF &pos, qreal a)
+                       const QPointF &pos, qreal a, int rangeStart, int rangeEnd)
             : glyphRun(g), boundingRect(brect), selectionState(selState), clipNode(0), decorations(decs)
             , color(c), backgroundColor(bc), position(pos), ascent(a), leftChildIndex(-1), rightChildIndex(-1)
         {
+            ranges.append(qMakePair(rangeStart, rangeEnd));
         }
 
         QGlyphRun glyphRun;
@@ -95,11 +96,14 @@ public:
         int leftChildIndex;
         int rightChildIndex;
 
+        QList<QPair<int, int> > ranges;
+
         static void insert(QVarLengthArray<BinaryTreeNode, 16> *binaryTree, const QRectF &rect, const QImage &image, qreal ascent, SelectionState selectionState)
         { insert(binaryTree, BinaryTreeNode(rect, image, selectionState, ascent)); }
 
         static void insert(QVarLengthArray<BinaryTreeNode, 16> *binaryTree, const QGlyphRun &glyphRun, SelectionState selectionState,
-                           QQuickTextNode::Decorations decorations, const QColor &textColor, const QColor &backgroundColor, const QPointF &position);
+                           QQuickTextNode::Decorations decorations, const QColor &textColor, const QColor &backgroundColor, const QPointF &position,
+                           int rangeStart, int rangeEnd);
         static void insert(QVarLengthArray<BinaryTreeNode, 16> *binaryTree, const BinaryTreeNode &binaryTreeNode);
         static void inOrder(const QVarLengthArray<BinaryTreeNode, 16> &binaryTree, QVarLengthArray<int> *sortedIndexes, int currentIndex = 0);
     };
@@ -134,8 +138,8 @@ public:
                        SelectionState selectionState,
                        QTextDocument *textDocument, int pos,
                        QTextFrameFormat::Position layoutPosition = QTextFrameFormat::InFlow);
-    void addSelectedGlyphs(const QGlyphRun &glyphRun);
-    void addUnselectedGlyphs(const QGlyphRun &glyphRun);
+    void addSelectedGlyphs(const QGlyphRun &glyphRun, int rangeStart, int rangeEnd);
+    void addUnselectedGlyphs(const QGlyphRun &glyphRun, int rangeStart, int rangeEnd);
     void addGlyphsInRange(int rangeStart, int rangeEnd,
                           const QColor &color, const QColor &backgroundColor,
                           int selectionStart, int selectionEnd);
diff --git a/tests/manual/scenegraph_lancelot/data/text/textedit_bidi_selected_first.qml b/tests/manual/scenegraph_lancelot/data/text/textedit_bidi_selected_first.qml
new file mode 100644
index 0000000000..78451c0570
--- /dev/null
+++ b/tests/manual/scenegraph_lancelot/data/text/textedit_bidi_selected_first.qml
@@ -0,0 +1,17 @@
+import QtQuick 2.0
+
+Item {
+    width: 320
+    height: 480
+    TextEdit {
+        anchors.centerIn: parent
+        id: textEdit
+        font.family: "Arial"
+        font.pixelSize: 14
+        text: "Lorem ipsum لمّ استبدال dolor sit."
+
+        Component.onCompleted: {
+            textEdit.select(0, 1)
+        }
+    }
+}
diff --git a/tests/manual/scenegraph_lancelot/data/text/textedit_multiline_selected_first_line.qml b/tests/manual/scenegraph_lancelot/data/text/textedit_multiline_selected_first_line.qml
new file mode 100644
index 0000000000..b2eacee344
--- /dev/null
+++ b/tests/manual/scenegraph_lancelot/data/text/textedit_multiline_selected_first_line.qml
@@ -0,0 +1,22 @@
+import QtQuick 2.0
+
+Item {
+    width: 320
+    height: 480
+
+    TextEdit {
+        id: textEdit
+        anchors.centerIn: parent
+        font.family: "Arial"
+        font.pixelSize: 16
+        width: 200
+        textFormat: TextEdit.RichText
+        wrapMode: TextEdit.WrapAtWordBoundaryOrAnywhere
+        text: "Lorem<br /> ipsum dolor sit amet, consectetur adipiscing elit. In id diam vitae enim fringilla vestibulum. Pellentesque non leo justo, quis vestibulum augue"
+
+        Component.onCompleted: {
+            textEdit.select(0, 5)
+        }
+    }
+
+}
diff --git a/tests/manual/scenegraph_lancelot/data/text/textedit_multiline_selected_two_first_lines.qml b/tests/manual/scenegraph_lancelot/data/text/textedit_multiline_selected_two_first_lines.qml
new file mode 100644
index 0000000000..4df83b0203
--- /dev/null
+++ b/tests/manual/scenegraph_lancelot/data/text/textedit_multiline_selected_two_first_lines.qml
@@ -0,0 +1,22 @@
+import QtQuick 2.0
+
+Item {
+    width: 320
+    height: 480
+
+    TextEdit {
+        id: textEdit
+        anchors.centerIn: parent
+        font.family: "Arial"
+        font.pixelSize: 16
+        width: 200
+        textFormat: TextEdit.RichText
+        wrapMode: TextEdit.WrapAtWordBoundaryOrAnywhere
+        text: "Lorem<br />ipsum<br />dolor sit amet, consectetur adipiscing elit. In id diam vitae enim fringilla vestibulum. Pellentesque non leo justo, quis vestibulum augue"
+
+        Component.onCompleted: {
+            textEdit.select(0, 11)
+        }
+    }
+
+}
diff --git a/tests/manual/scenegraph_lancelot/data/text/textedit_selected_inline_image_selection_outside.qml b/tests/manual/scenegraph_lancelot/data/text/textedit_selected_inline_image_selection_outside.qml
new file mode 100644
index 0000000000..e6e54cb487
--- /dev/null
+++ b/tests/manual/scenegraph_lancelot/data/text/textedit_selected_inline_image_selection_outside.qml
@@ -0,0 +1,20 @@
+import QtQuick 2.0
+
+Item {
+    width: 320
+    height: 480
+
+    TextEdit {
+        id: textEdit
+        anchors.centerIn: parent
+        font.pixelSize: 16
+        width: parent.width
+        wrapMode: TextEdit.WrapAtWordBoundaryOrAnywhere
+        textFormat: Text.RichText
+        text: "This is selected from here and <img width=16 height=16 src=\"data/logo.png\" /> to here but not further"
+
+        Component.onCompleted: {
+            textEdit.select(2, 3)
+        }
+    }
+}
diff --git a/tests/manual/scenegraph_lancelot/data/text/textedit_selection_color_separate_item.qml b/tests/manual/scenegraph_lancelot/data/text/textedit_selection_color_separate_item.qml
new file mode 100644
index 0000000000..69679ed882
--- /dev/null
+++ b/tests/manual/scenegraph_lancelot/data/text/textedit_selection_color_separate_item.qml
@@ -0,0 +1,22 @@
+import QtQuick 2.0
+
+Item {
+    width: 320
+    height: 480
+
+    TextEdit {
+        id: textEdit
+        anchors.centerIn: parent
+        width: parent.width
+        font.pixelSize: 14
+        text: "Lorem ipsum dolor sit amet, э consectetur adipiscing elit. Maecenas nibh"
+        wrapMode: TextEdit.WrapAtWordBoundaryOrAnywhere
+
+        selectionColor: "red"
+        selectedTextColor: "blue"
+
+        Component.onCompleted: {
+            textEdit.select(28, 29)
+        }
+    }
+}
diff --git a/tests/manual/scenegraph_lancelot/data/text/textinput_italic_selected.qml b/tests/manual/scenegraph_lancelot/data/text/textinput_italic_selected.qml
new file mode 100644
index 0000000000..1df07e6269
--- /dev/null
+++ b/tests/manual/scenegraph_lancelot/data/text/textinput_italic_selected.qml
@@ -0,0 +1,17 @@
+import QtQuick 2.0
+
+Item {
+    width: 320
+    height: 480
+    TextInput {
+        anchors.centerIn: parent
+        id: textInput
+        font.pixelSize: 44
+        font.italic: true
+        text: "777"
+
+        Component.onCompleted: {
+            textInput.select(1, 2)
+        }
+    }
+}