From f513e88403b66c4a5efe4c62c160dfce151efb33 Mon Sep 17 00:00:00 2001
From: Pierre Rossi <pierre.rossi@digia.com>
Date: Mon, 18 Mar 2013 16:25:59 +0100
Subject: Optimize QQuickTextEdit for larger documents.

The rationale is to not end up re-processing the whole document on each update
Since we know where the editing takes place, we can break down the text edit's
contents in several text nodes and only re-create the affected text nodes upon
editing.

This requires ripping out the SelectionEngine helper class from QQuickTextNode
so that QQuickTextEdit can tap into its functionality directly.

A positive side-effect of this exercise is that it should be much harder to
to come across GlyphNodes packing more than 16300 glyphs or so.

Task-number: QTBUG-29596
Change-Id: Id29b0709baa43f5b29c44ab02398ba996be3e28a
Reviewed-by: Yoann Lopes <yoann.lopes@digia.com>
---
 src/quick/items/qquicktextnodeengine.cpp | 935 +++++++++++++++++++++++++++++++
 1 file changed, 935 insertions(+)
 create mode 100644 src/quick/items/qquicktextnodeengine.cpp

(limited to 'src/quick/items/qquicktextnodeengine.cpp')

diff --git a/src/quick/items/qquicktextnodeengine.cpp b/src/quick/items/qquicktextnodeengine.cpp
new file mode 100644
index 0000000000..7bbfd1bcda
--- /dev/null
+++ b/src/quick/items/qquicktextnodeengine.cpp
@@ -0,0 +1,935 @@
+/****************************************************************************
+**
+** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of the QtQml module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qquicktextnodeengine_p.h"
+
+#include <QtCore/qpoint.h>
+#include <QtGui/qabstracttextdocumentlayout.h>
+#include <QtGui/qrawfont.h>
+#include <QtGui/qtextdocument.h>
+#include <QtGui/qtextlayout.h>
+#include <QtGui/qtextobject.h>
+#include <QtGui/qtexttable.h>
+#include <QtGui/qtextlist.h>
+#include <QtQuick/qsgsimplerectnode.h>
+
+#include <private/qquicktext_p_p.h>
+#include <private/qtextdocumentlayout_p.h>
+#include <private/qtextimagehandler_p.h>
+#include <private/qrawfont_p.h>
+
+QT_BEGIN_NAMESPACE
+
+void QQuickTextNodeEngine::BinaryTreeNode::insert(QVarLengthArray<BinaryTreeNode> *binaryTree, const QGlyphRun &glyphRun, SelectionState selectionState,
+                                             QQuickTextNode::Decorations decorations, const QColor &textColor,
+                                             const QColor &backgroundColor, const QPointF &position)
+{
+    QRectF searchRect = glyphRun.boundingRect();
+    searchRect.translate(position);
+
+    if (qFuzzyIsNull(searchRect.width()) || qFuzzyIsNull(searchRect.height()))
+        return;
+
+    decorations |= (glyphRun.underline() ? QQuickTextNode::Underline : QQuickTextNode::NoDecoration);
+    decorations |= (glyphRun.overline()  ? QQuickTextNode::Overline  : QQuickTextNode::NoDecoration);
+    decorations |= (glyphRun.strikeOut() ? QQuickTextNode::StrikeOut : QQuickTextNode::NoDecoration);
+    decorations |= (backgroundColor.isValid() ? QQuickTextNode::Background : QQuickTextNode::NoDecoration);
+
+    qreal ascent = glyphRun.rawFont().ascent();
+    insert(binaryTree, BinaryTreeNode(glyphRun, selectionState, searchRect, decorations,
+                                      textColor, backgroundColor, position, ascent));
+}
+
+void QQuickTextNodeEngine::BinaryTreeNode::insert(QVarLengthArray<BinaryTreeNode> *binaryTree, const BinaryTreeNode &binaryTreeNode)
+{
+    int newIndex = binaryTree->size();
+    binaryTree->append(binaryTreeNode);
+    if (newIndex == 0)
+        return;
+
+    int searchIndex = 0;
+    forever {
+        BinaryTreeNode *node = binaryTree->data() + searchIndex;
+        if (binaryTreeNode.boundingRect.left() < node->boundingRect.left()) {
+            if (node->leftChildIndex < 0) {
+                node->leftChildIndex = newIndex;
+                break;
+            } else {
+                searchIndex = node->leftChildIndex;
+            }
+        } else {
+            if (node->rightChildIndex < 0) {
+                node->rightChildIndex = newIndex;
+                break;
+            } else {
+                searchIndex = node->rightChildIndex;
+            }
+        }
+    }
+}
+
+void QQuickTextNodeEngine::BinaryTreeNode::inOrder(const QVarLengthArray<BinaryTreeNode> &binaryTree,
+                                              QVarLengthArray<int> *sortedIndexes, int currentIndex)
+{
+    Q_ASSERT(currentIndex < binaryTree.size());
+
+    const BinaryTreeNode *node = binaryTree.data() + currentIndex;
+    if (node->leftChildIndex >= 0)
+        inOrder(binaryTree, sortedIndexes, node->leftChildIndex);
+
+    sortedIndexes->append(currentIndex);
+
+    if (node->rightChildIndex >= 0)
+        inOrder(binaryTree, sortedIndexes, node->rightChildIndex);
+}
+
+
+int QQuickTextNodeEngine::addText(const QTextBlock &block,
+                                  const QTextCharFormat &charFormat,
+                                  const QColor &textColor,
+                                  const QVarLengthArray<QTextLayout::FormatRange> &colorChanges,
+                                  int textPos, int fragmentEnd,
+                                  int selectionStart, int selectionEnd)
+{
+    if (charFormat.foreground().style() != Qt::NoBrush)
+        setTextColor(charFormat.foreground().color());
+    else
+        setTextColor(textColor);
+
+    while (textPos < fragmentEnd) {
+        int blockRelativePosition = textPos - block.position();
+        QTextLine line = block.layout()->lineForTextPosition(blockRelativePosition);
+        if (!currentLine().isValid()
+                || line.lineNumber() != currentLine().lineNumber()) {
+            setCurrentLine(line);
+        }
+
+        Q_ASSERT(line.textLength() > 0);
+        int lineEnd = line.textStart() + block.position() + line.textLength();
+
+        int len = qMin(lineEnd - textPos, fragmentEnd - textPos);
+        Q_ASSERT(len > 0);
+
+        int currentStepEnd = textPos + len;
+
+        addGlyphsForRanges(colorChanges,
+                           textPos - block.position(),
+                           currentStepEnd - block.position(),
+                           selectionStart - block.position(),
+                           selectionEnd - block.position());
+
+        textPos = currentStepEnd;
+    }
+    return textPos;
+}
+
+void QQuickTextNodeEngine::addTextDecorations(const QVarLengthArray<TextDecoration> &textDecorations,
+                                              qreal offset, qreal thickness)
+{
+    for (int i=0; i<textDecorations.size(); ++i) {
+        TextDecoration textDecoration = textDecorations.at(i);
+
+        {
+            QRectF &rect = textDecoration.rect;
+            rect.setY(qRound(rect.y() + m_currentLine.ascent() + offset));
+            rect.setHeight(thickness);
+        }
+
+        m_lines.append(textDecoration);
+    }
+}
+
+void QQuickTextNodeEngine::processCurrentLine()
+{
+    // No glyphs, do nothing
+    if (m_currentLineTree.isEmpty())
+        return;
+
+    // 1. Go through current line and get correct decoration position for each node based on
+    // neighbouring decorations. Add decoration to global list
+    // 2. Create clip nodes for all selected text. Try to merge as many as possible within
+    // the line.
+    // 3. Add QRects to a list of selection rects.
+    // 4. Add all nodes to a global processed list
+    QVarLengthArray<int> sortedIndexes; // Indexes in tree sorted by x position
+    BinaryTreeNode::inOrder(m_currentLineTree, &sortedIndexes);
+
+    Q_ASSERT(sortedIndexes.size() == m_currentLineTree.size());
+
+    SelectionState currentSelectionState = Unselected;
+    QRectF currentRect;
+
+    QQuickTextNode::Decorations currentDecorations = QQuickTextNode::NoDecoration;
+    qreal underlineOffset = 0.0;
+    qreal underlineThickness = 0.0;
+
+    qreal overlineOffset = 0.0;
+    qreal overlineThickness = 0.0;
+
+    qreal strikeOutOffset = 0.0;
+    qreal strikeOutThickness = 0.0;
+
+    QRectF decorationRect = currentRect;
+
+    QColor lastColor;
+    QColor lastBackgroundColor;
+
+    QVarLengthArray<TextDecoration> pendingUnderlines;
+    QVarLengthArray<TextDecoration> pendingOverlines;
+    QVarLengthArray<TextDecoration> pendingStrikeOuts;
+    if (!sortedIndexes.isEmpty()) {
+        QQuickDefaultClipNode *currentClipNode = m_hasSelection ? new QQuickDefaultClipNode(QRectF()) : 0;
+        bool currentClipNodeUsed = false;
+        for (int i=0; i<=sortedIndexes.size(); ++i) {
+            BinaryTreeNode *node = 0;
+            if (i < sortedIndexes.size()) {
+                int sortedIndex = sortedIndexes.at(i);
+                Q_ASSERT(sortedIndex < m_currentLineTree.size());
+
+                node = m_currentLineTree.data() + sortedIndex;
+            }
+
+            if (i == 0)
+                currentSelectionState = node->selectionState;
+
+            // Update decorations
+            if (currentDecorations != QQuickTextNode::NoDecoration) {
+                decorationRect.setY(m_position.y() + m_currentLine.y());
+                decorationRect.setHeight(m_currentLine.height());
+
+                if (node != 0)
+                    decorationRect.setRight(node->boundingRect.left());
+
+                TextDecoration textDecoration(currentSelectionState, decorationRect, lastColor);
+                if (currentDecorations & QQuickTextNode::Underline)
+                    pendingUnderlines.append(textDecoration);
+
+                if (currentDecorations & QQuickTextNode::Overline)
+                    pendingOverlines.append(textDecoration);
+
+                if (currentDecorations & QQuickTextNode::StrikeOut)
+                    pendingStrikeOuts.append(textDecoration);
+
+                if (currentDecorations & QQuickTextNode::Background)
+                    m_backgrounds.append(qMakePair(decorationRect, lastBackgroundColor));
+            }
+
+            // If we've reached an unselected node from a selected node, we add the
+            // 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);
+
+                if (currentClipNode != 0) {
+                    if (!currentClipNodeUsed) {
+                        delete currentClipNode;
+                    } else {
+                        currentClipNode->setIsRectangular(true);
+                        currentClipNode->setRect(currentRect);
+                        currentClipNode->update();
+                    }
+                }
+
+                if (node != 0 && m_hasSelection)
+                    currentClipNode = new QQuickDefaultClipNode(QRectF());
+                else
+                    currentClipNode = 0;
+                currentClipNodeUsed = false;
+
+                if (node != 0) {
+                    currentSelectionState = node->selectionState;
+                    currentRect = node->boundingRect;
+
+                    // Make sure currentRect is valid, otherwise the unite won't work
+                    if (currentRect.isNull())
+                        currentRect.setSize(QSizeF(1, 1));
+                }
+            } else {
+                if (currentRect.isNull())
+                    currentRect = node->boundingRect;
+                else
+                    currentRect = currentRect.united(node->boundingRect);
+            }
+
+            if (node != 0) {
+                node->clipNode = currentClipNode;
+                currentClipNodeUsed = true;
+
+                decorationRect = node->boundingRect;
+
+                // If previous item(s) had underline and current does not, then we add the
+                // pending lines to the lists and likewise for overlines and strikeouts
+                if (!pendingUnderlines.isEmpty()
+                        && !(node->decorations & QQuickTextNode::Underline)) {
+                    addTextDecorations(pendingUnderlines, underlineOffset, underlineThickness);
+
+                    pendingUnderlines.clear();
+
+                    underlineOffset = 0.0;
+                    underlineThickness = 0.0;
+                }
+
+                // ### Add pending when overlineOffset/thickness changes to minimize number of
+                // nodes
+                if (!pendingOverlines.isEmpty()) {
+                    addTextDecorations(pendingOverlines, overlineOffset, overlineThickness);
+
+                    pendingOverlines.clear();
+
+                    overlineOffset = 0.0;
+                    overlineThickness = 0.0;
+                }
+
+                // ### Add pending when overlineOffset/thickness changes to minimize number of
+                // nodes
+                if (!pendingStrikeOuts.isEmpty()) {
+                    addTextDecorations(pendingStrikeOuts, strikeOutOffset, strikeOutThickness);
+
+                    pendingStrikeOuts.clear();
+
+                    strikeOutOffset = 0.0;
+                    strikeOutThickness = 0.0;
+                }
+
+                // Merge current values with previous. Prefer greatest thickness
+                QRawFont rawFont = node->glyphRun.rawFont();
+                if (node->decorations & QQuickTextNode::Underline) {
+                    if (rawFont.lineThickness() > underlineThickness) {
+                        underlineThickness = rawFont.lineThickness();
+                        underlineOffset = rawFont.underlinePosition();
+                    }
+                }
+
+                if (node->decorations & QQuickTextNode::Overline) {
+                    overlineOffset = -rawFont.ascent();
+                    overlineThickness = rawFont.lineThickness();
+                }
+
+                if (node->decorations & QQuickTextNode::StrikeOut) {
+                    strikeOutThickness = rawFont.lineThickness();
+                    strikeOutOffset = rawFont.ascent() / -3.0;
+                }
+
+                currentDecorations = node->decorations;
+                lastColor = node->color;
+                lastBackgroundColor = node->backgroundColor;
+                m_processedNodes.append(*node);
+            }
+        }
+
+        if (!pendingUnderlines.isEmpty())
+            addTextDecorations(pendingUnderlines, underlineOffset, underlineThickness);
+
+        if (!pendingOverlines.isEmpty())
+            addTextDecorations(pendingOverlines, overlineOffset, overlineThickness);
+
+        if (!pendingStrikeOuts.isEmpty())
+            addTextDecorations(pendingStrikeOuts, strikeOutOffset, strikeOutThickness);
+    }
+
+    m_currentLineTree.clear();
+    m_currentLine = QTextLine();
+    m_hasSelection = false;
+}
+
+void QQuickTextNodeEngine::addImage(const QRectF &rect, const QImage &image, qreal ascent,
+                                    SelectionState selectionState,
+                                    QTextFrameFormat::Position layoutPosition)
+{
+    QRectF searchRect = rect;
+    if (layoutPosition == QTextFrameFormat::InFlow) {
+        if (m_currentLineTree.isEmpty()) {
+            searchRect.moveTopLeft(m_position + m_currentLine.position());
+        } else {
+            const BinaryTreeNode *lastNode = m_currentLineTree.data() + m_currentLineTree.size() - 1;
+            if (lastNode->glyphRun.isRightToLeft()) {
+                QPointF lastPos = lastNode->boundingRect.topLeft();
+                searchRect.moveTopRight(lastPos - QPointF(0, ascent - lastNode->ascent));
+            } else {
+                QPointF lastPos = lastNode->boundingRect.topRight();
+                searchRect.moveTopLeft(lastPos - QPointF(0, ascent - lastNode->ascent));
+            }
+        }
+    }
+
+    BinaryTreeNode::insert(&m_currentLineTree, searchRect, image, ascent, selectionState);
+    m_hasContents = true;
+}
+
+void QQuickTextNodeEngine::addTextObject(const QPointF &position, const QTextCharFormat &format,
+                                         SelectionState selectionState,
+                                         QTextDocument *textDocument, int pos,
+                                         QTextFrameFormat::Position layoutPosition)
+{
+    QTextObjectInterface *handler = textDocument->documentLayout()->handlerForObject(format.objectType());
+    if (handler != 0) {
+        QImage image;
+        QSizeF size = handler->intrinsicSize(textDocument, pos, format);
+
+        if (format.objectType() == QTextFormat::ImageObject) {
+            QTextImageFormat imageFormat = format.toImageFormat();
+            if (QQuickTextDocumentWithImageResources *imageDoc = qobject_cast<QQuickTextDocumentWithImageResources *>(textDocument)) {
+                image = imageDoc->image(imageFormat);
+
+                if (image.isNull())
+                    return;
+            } else {
+                QTextImageHandler *imageHandler = static_cast<QTextImageHandler *>(handler);
+                image = imageHandler->image(textDocument, imageFormat);
+            }
+        }
+
+        if (image.isNull()) {
+            image = QImage(size.toSize(), QImage::Format_ARGB32_Premultiplied);
+            image.fill(Qt::transparent);
+            {
+                QPainter painter(&image);
+                handler->drawObject(&painter, image.rect(), textDocument, pos, format);
+            }
+        }
+
+        qreal ascent;
+        QFontMetrics m(format.font());
+        switch (format.verticalAlignment())
+        {
+        case QTextCharFormat::AlignMiddle:
+            ascent = size.height() / 2 - 1;
+            break;
+        case QTextCharFormat::AlignBaseline:
+            ascent = size.height() - m.descent() - 1;
+            break;
+        default:
+            ascent = size.height() - 1;
+        }
+
+        addImage(QRectF(position, size), image, ascent, selectionState, layoutPosition);
+    }
+}
+
+void QQuickTextNodeEngine::addUnselectedGlyphs(const QGlyphRun &glyphRun)
+{
+    BinaryTreeNode::insert(&m_currentLineTree, glyphRun, Unselected,
+                           QQuickTextNode::NoDecoration, m_textColor, m_backgroundColor, m_position);
+}
+
+void QQuickTextNodeEngine::addSelectedGlyphs(const QGlyphRun &glyphRun)
+{
+    int currentSize = m_currentLineTree.size();
+    BinaryTreeNode::insert(&m_currentLineTree, glyphRun, Selected,
+                           QQuickTextNode::NoDecoration, m_textColor, m_backgroundColor, m_position);
+    m_hasSelection = m_hasSelection || m_currentLineTree.size() > currentSize;
+}
+
+void QQuickTextNodeEngine::addGlyphsForRanges(const QVarLengthArray<QTextLayout::FormatRange> &ranges,
+                                              int start, int end,
+                                              int selectionStart, int selectionEnd)
+{
+    int currentPosition = start;
+    int remainingLength = end - start;
+    for (int j=0; j<ranges.size(); ++j) {
+        const QTextLayout::FormatRange &range = ranges.at(j);
+        if (range.start + range.length >= currentPosition
+                && range.start < currentPosition + remainingLength) {
+
+            if (range.start > currentPosition) {
+                addGlyphsInRange(currentPosition, range.start - currentPosition,
+                                 QColor(), QColor(), selectionStart, selectionEnd);
+            }
+            int rangeEnd = qMin(range.start + range.length, currentPosition + remainingLength);
+            QColor rangeColor;
+            if (range.format.hasProperty(QTextFormat::ForegroundBrush))
+                rangeColor = range.format.foreground().color();
+            else if (range.format.isAnchor())
+                rangeColor = m_anchorColor;
+            QColor rangeBackgroundColor = range.format.hasProperty(QTextFormat::BackgroundBrush)
+                    ? range.format.background().color()
+                    : QColor();
+
+            addGlyphsInRange(range.start, rangeEnd - range.start,
+                             rangeColor, rangeBackgroundColor,
+                             selectionStart, selectionEnd);
+
+            currentPosition = range.start + range.length;
+            remainingLength = end - currentPosition;
+
+        } else if (range.start > currentPosition + remainingLength || remainingLength <= 0) {
+            break;
+        }
+    }
+
+    if (remainingLength > 0) {
+        addGlyphsInRange(currentPosition, remainingLength, QColor(), QColor(),
+                         selectionStart, selectionEnd);
+    }
+
+}
+
+void QQuickTextNodeEngine::addGlyphsInRange(int rangeStart, int rangeLength,
+                                            const QColor &color, const QColor &backgroundColor,
+                                            int selectionStart, int selectionEnd)
+{
+    QColor oldColor;
+    if (color.isValid()) {
+        oldColor = m_textColor;
+        m_textColor = color;
+    }
+
+    QColor oldBackgroundColor = m_backgroundColor;
+    if (backgroundColor.isValid()) {
+        oldBackgroundColor = m_backgroundColor;
+        m_backgroundColor = backgroundColor;
+    }
+
+    bool hasSelection = selectionEnd >= 0
+            && selectionStart <= selectionEnd;
+
+    QTextLine &line = m_currentLine;
+    int rangeEnd = rangeStart + rangeLength;
+    if (!hasSelection || (selectionStart > rangeEnd || selectionEnd < rangeStart)) {
+        QList<QGlyphRun> glyphRuns = line.glyphRuns(rangeStart, rangeLength);
+        for (int j=0; j<glyphRuns.size(); ++j) {
+            const QGlyphRun &glyphRun = glyphRuns.at(j);
+            addUnselectedGlyphs(glyphRun);
+        }
+    } else {
+        if (rangeStart < selectionStart) {
+            QList<QGlyphRun> glyphRuns = line.glyphRuns(rangeStart,
+                                                        qMin(selectionStart - rangeStart,
+                                                             rangeLength));
+
+            for (int j=0; j<glyphRuns.size(); ++j) {
+                const QGlyphRun &glyphRun = glyphRuns.at(j);
+                addUnselectedGlyphs(glyphRun);
+            }
+        }
+
+        if (rangeEnd > selectionStart) {
+            int start = qMax(selectionStart, rangeStart);
+            int length = qMin(selectionEnd - start + 1, rangeEnd - start);
+            QList<QGlyphRun> glyphRuns = line.glyphRuns(start, length);
+
+            for (int j=0; j<glyphRuns.size(); ++j) {
+                const QGlyphRun &glyphRun = glyphRuns.at(j);
+                addSelectedGlyphs(glyphRun);
+            }
+        }
+
+        if (selectionEnd >= rangeStart && selectionEnd < rangeEnd) {
+            QList<QGlyphRun> glyphRuns = line.glyphRuns(selectionEnd + 1, rangeEnd - selectionEnd - 1);
+            for (int j=0; j<glyphRuns.size(); ++j) {
+                const QGlyphRun &glyphRun = glyphRuns.at(j);
+                addUnselectedGlyphs(glyphRun);
+            }
+        }
+    }
+
+    if (backgroundColor.isValid())
+        m_backgroundColor = oldBackgroundColor;
+
+    if (oldColor.isValid())
+        m_textColor = oldColor;
+}
+
+void QQuickTextNodeEngine::addBorder(const QRectF &rect, qreal border,
+                                     QTextFrameFormat::BorderStyle borderStyle,
+                                     const QBrush &borderBrush)
+{
+    QColor color = borderBrush.color();
+
+    // Currently we don't support other styles than solid
+    Q_UNUSED(borderStyle);
+
+    m_backgrounds.append(qMakePair(QRectF(rect.left(), rect.top(), border, rect.height() + border), color));
+    m_backgrounds.append(qMakePair(QRectF(rect.left() + border, rect.top(), rect.width(), border), color));
+    m_backgrounds.append(qMakePair(QRectF(rect.right(), rect.top() + border, border, rect.height() - border), color));
+    m_backgrounds.append(qMakePair(QRectF(rect.left() + border, rect.bottom(), rect.width(), border), color));
+}
+
+void QQuickTextNodeEngine::addFrameDecorations(QTextDocument *document, QTextFrame *frame)
+{
+    QTextDocumentLayout *documentLayout = qobject_cast<QTextDocumentLayout *>(document->documentLayout());
+    QTextFrameFormat frameFormat = frame->format().toFrameFormat();
+
+    QTextTable *table = qobject_cast<QTextTable *>(frame);
+    QRectF boundingRect = table == 0
+            ? documentLayout->frameBoundingRect(frame)
+            : documentLayout->tableBoundingRect(table);
+
+    QBrush bg = frame->frameFormat().background();
+    if (bg.style() != Qt::NoBrush)
+        m_backgrounds.append(qMakePair(boundingRect, bg.color()));
+
+    if (!frameFormat.hasProperty(QTextFormat::FrameBorder))
+        return;
+
+    qreal borderWidth = frameFormat.border();
+    if (qFuzzyIsNull(borderWidth))
+        return;
+
+    QBrush borderBrush = frameFormat.borderBrush();
+    QTextFrameFormat::BorderStyle borderStyle = frameFormat.borderStyle();
+    if (borderStyle == QTextFrameFormat::BorderStyle_None)
+        return;
+
+    addBorder(boundingRect.adjusted(frameFormat.leftMargin(), frameFormat.topMargin(),
+                                    -frameFormat.rightMargin(), -frameFormat.bottomMargin()),
+              borderWidth, borderStyle, borderBrush);
+    if (table != 0) {
+        int rows = table->rows();
+        int columns = table->columns();
+
+        for (int row=0; row<rows; ++row) {
+            for (int column=0; column<columns; ++column) {
+                QTextTableCell cell = table->cellAt(row, column);
+
+                QRectF cellRect = documentLayout->tableCellBoundingRect(table, cell);
+                addBorder(cellRect.adjusted(-borderWidth, -borderWidth, 0, 0), borderWidth,
+                          borderStyle, borderBrush);
+            }
+        }
+    }
+}
+
+void  QQuickTextNodeEngine::addToSceneGraph(QQuickTextNode *parentNode,
+                                            QQuickText::TextStyle style,
+                                            const QColor &styleColor)
+{
+    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->appendChildNode(new QSGSimpleRectNode(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->appendChildNode(new QSGSimpleRectNode(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->appendChildNode(new QSGSimpleRectNode(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;
+    for (int i = 0; i < m_processedNodes.size(); ++i) {
+        BinaryTreeNode *node = m_processedNodes.data() + i;
+
+        if (node->image.isNull()) {
+            QGlyphRun glyphRun = node->glyphRun;
+            QRawFont rawFont = glyphRun.rawFont();
+            QRawFontPrivate *rawFontD = QRawFontPrivate::get(rawFont);
+
+            QFontEngine *fontEngine = rawFontD->fontEngine;
+
+            KeyType key(qMakePair(fontEngine,
+                                  qMakePair(node->clipNode,
+                                            qMakePair(node->color.rgba(), int(node->selectionState)))));
+
+            BinaryTreeNode *otherNode = map.value(key, 0);
+            if (otherNode != 0) {
+                QGlyphRun &otherGlyphRun = otherNode->glyphRun;
+
+                QVector<quint32> otherGlyphIndexes = otherGlyphRun.glyphIndexes();
+                QVector<QPointF> otherGlyphPositions = otherGlyphRun.positions();
+
+                otherGlyphIndexes += glyphRun.glyphIndexes();
+
+                QVector<QPointF> glyphPositions = glyphRun.positions();
+                otherGlyphPositions.reserve(otherGlyphPositions.size() + glyphPositions.size());
+                for (int j = 0; j < glyphPositions.size(); ++j) {
+                    otherGlyphPositions += glyphPositions.at(j) + (node->position - otherNode->position);
+                }
+
+                otherGlyphRun.setGlyphIndexes(otherGlyphIndexes);
+                otherGlyphRun.setPositions(otherGlyphPositions);
+
+            } 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->appendChildNode(new QSGSimpleRectNode(node->boundingRect, color));
+            }
+        }
+    }
+
+    foreach (const BinaryTreeNode *node, nodes) {
+
+        QQuickDefaultClipNode *clipNode = node->clipNode;
+        if (clipNode != 0 && clipNode->parent() == 0 )
+            parentNode->appendChildNode(clipNode);
+
+        QColor color = node->selectionState == Selected
+                ? m_selectedTextColor
+                : node->color;
+
+        parentNode->addGlyphs(node->position, node->glyphRun, color, style, styleColor, clipNode);
+    }
+}
+
+void QQuickTextNodeEngine::mergeFormats(QTextLayout *textLayout, QVarLengthArray<QTextLayout::FormatRange> *mergedFormats)
+{
+    Q_ASSERT(mergedFormats != 0);
+    if (textLayout == 0)
+        return;
+
+    QList<QTextLayout::FormatRange> additionalFormats = textLayout->additionalFormats();
+    for (int i=0; i<additionalFormats.size(); ++i) {
+        QTextLayout::FormatRange additionalFormat = additionalFormats.at(i);
+        if (additionalFormat.format.hasProperty(QTextFormat::ForegroundBrush)
+         || additionalFormat.format.hasProperty(QTextFormat::BackgroundBrush)
+         || additionalFormat.format.isAnchor()) {
+            // Merge overlapping formats
+            if (!mergedFormats->isEmpty()) {
+                QTextLayout::FormatRange *lastFormat = mergedFormats->data() + mergedFormats->size() - 1;
+
+                if (additionalFormat.start < lastFormat->start + lastFormat->length) {
+                    QTextLayout::FormatRange *mergedRange = 0;
+
+                    int length = additionalFormat.length;
+                    if (additionalFormat.start > lastFormat->start) {
+                        lastFormat->length = additionalFormat.start - lastFormat->start;
+                        length -= lastFormat->length;
+
+                        mergedFormats->append(QTextLayout::FormatRange());
+                        mergedRange = mergedFormats->data() + mergedFormats->size() - 1;
+                        lastFormat = mergedFormats->data() + mergedFormats->size() - 2;
+                    } else {
+                        mergedRange = lastFormat;
+                    }
+
+                    mergedRange->format = lastFormat->format;
+                    mergedRange->format.merge(additionalFormat.format);
+                    mergedRange->start = additionalFormat.start;
+
+                    int end = qMin(additionalFormat.start + additionalFormat.length,
+                                   lastFormat->start + lastFormat->length);
+
+                    mergedRange->length = end - mergedRange->start;
+                    length -= mergedRange->length;
+
+                    additionalFormat.start = end;
+                    additionalFormat.length = length;
+                }
+            }
+
+            if (additionalFormat.length > 0)
+                mergedFormats->append(additionalFormat);
+        }
+    }
+
+}
+
+void QQuickTextNodeEngine::addTextBlock(QTextDocument *textDocument, const QTextBlock &block, const QPointF &position, const QColor &textColor, const QColor &anchorColor, int selectionStart, int selectionEnd)
+{
+    Q_ASSERT(textDocument);
+#ifndef QT_NO_IM
+    int preeditLength = block.isValid() ? block.layout()->preeditAreaText().length() : 0;
+    int preeditPosition = block.isValid() ? block.layout()->preeditAreaPosition() : -1;
+#endif
+
+    QVarLengthArray<QTextLayout::FormatRange> colorChanges;
+    mergeFormats(block.layout(), &colorChanges);
+
+    QPointF blockPosition = textDocument->documentLayout()->blockBoundingRect(block).topLeft() + position;
+    if (QTextList *textList = block.textList()) {
+        QPointF pos = blockPosition;
+        QTextLayout *layout = block.layout();
+        if (layout->lineCount() > 0) {
+            QTextLine firstLine = layout->lineAt(0);
+            Q_ASSERT(firstLine.isValid());
+
+            setCurrentLine(firstLine);
+
+            QRectF textRect = firstLine.naturalTextRect();
+            pos += textRect.topLeft();
+            if (block.textDirection() == Qt::RightToLeft)
+                pos.rx() += textRect.width();
+
+            const QTextCharFormat charFormat = block.charFormat();
+            QFont font(charFormat.font());
+            QFontMetricsF fontMetrics(font);
+            QTextListFormat listFormat = textList->format();
+
+            QString listItemBullet;
+            switch (listFormat.style()) {
+            case QTextListFormat::ListCircle:
+                listItemBullet = QChar(0x25E6); // White bullet
+                break;
+            case QTextListFormat::ListSquare:
+                listItemBullet = QChar(0x25AA); // Black small square
+                break;
+            case QTextListFormat::ListDecimal:
+            case QTextListFormat::ListLowerAlpha:
+            case QTextListFormat::ListUpperAlpha:
+            case QTextListFormat::ListLowerRoman:
+            case QTextListFormat::ListUpperRoman:
+                listItemBullet = textList->itemText(block);
+                break;
+            default:
+                listItemBullet = QChar(0x2022); // Black bullet
+                break;
+            };
+
+            QSizeF size(fontMetrics.width(listItemBullet), fontMetrics.height());
+            qreal xoff = fontMetrics.width(QLatin1Char(' '));
+            if (block.textDirection() == Qt::LeftToRight)
+                xoff = -xoff - size.width();
+            setPosition(pos + QPointF(xoff, 0));
+
+            QTextLayout layout;
+            layout.setFont(font);
+            layout.setText(listItemBullet); // Bullet
+            layout.beginLayout();
+            QTextLine line = layout.createLine();
+            line.setPosition(QPointF(0, 0));
+            layout.endLayout();
+
+            QList<QGlyphRun> glyphRuns = layout.glyphRuns();
+            for (int i=0; i<glyphRuns.size(); ++i)
+                addUnselectedGlyphs(glyphRuns.at(i));
+        }
+    }
+
+    int textPos = block.position();
+    QTextBlock::iterator blockIterator = block.begin();
+
+    while (!blockIterator.atEnd()) {
+        QTextFragment fragment = blockIterator.fragment();
+        QString text = fragment.text();
+        if (text.isEmpty())
+            continue;
+
+        QTextCharFormat charFormat = fragment.charFormat();
+        setPosition(blockPosition);
+        if (text.contains(QChar::ObjectReplacementCharacter)) {
+            QTextFrame *frame = qobject_cast<QTextFrame *>(textDocument->objectForFormat(charFormat));
+            if (frame && frame->frameFormat().position() == QTextFrameFormat::InFlow) {
+                int blockRelativePosition = textPos - block.position();
+                QTextLine line = block.layout()->lineForTextPosition(blockRelativePosition);
+                if (!currentLine().isValid()
+                        || line.lineNumber() != currentLine().lineNumber()) {
+                    setCurrentLine(line);
+                }
+
+                QQuickTextNodeEngine::SelectionState selectionState =
+                        (selectionStart < textPos + text.length()
+                         && selectionEnd >= textPos)
+                        ? QQuickTextNodeEngine::Selected
+                        : QQuickTextNodeEngine::Unselected;
+
+                addTextObject(QPointF(), charFormat, selectionState, textDocument, textPos);
+            }
+            textPos += text.length();
+        } else {
+            if (charFormat.foreground().style() != Qt::NoBrush)
+                setTextColor(charFormat.foreground().color());
+            else if (charFormat.isAnchor())
+                setTextColor(anchorColor);
+            else
+                setTextColor(textColor);
+
+            int fragmentEnd = textPos + fragment.length();
+#ifndef QT_NO_IM
+            if (preeditPosition >= 0
+                    && preeditPosition >= textPos
+                    && preeditPosition <= fragmentEnd) {
+                fragmentEnd += preeditLength;
+            }
+#endif
+
+            textPos = addText(block, charFormat, textColor, colorChanges, textPos, fragmentEnd,
+                                                 selectionStart, selectionEnd);
+        }
+
+        ++blockIterator;
+    }
+
+#ifndef QT_NO_IM
+    if (preeditLength >= 0 && textPos <= block.position() + preeditPosition) {
+        setPosition(blockPosition);
+        textPos = block.position() + preeditPosition;
+        QTextLine line = block.layout()->lineForTextPosition(preeditPosition);
+        if (!currentLine().isValid()
+                || line.lineNumber() != currentLine().lineNumber()) {
+            setCurrentLine(line);
+        }
+        textPos = addText(block, block.charFormat(), textColor, colorChanges,
+                                             textPos, textPos + preeditLength,
+                                             selectionStart, selectionEnd);
+    }
+#endif
+
+    setCurrentLine(QTextLine()); // Reset current line because the text layout changed
+    m_hasContents = true;
+}
+
+
+QT_END_NAMESPACE
+
-- 
cgit v1.2.3