gui/text/qtextengine_p.h

/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtGui 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 The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/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 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/

#ifndef QTEXTENGINE_P_H
#define QTEXTENGINE_P_H

//
//  W A R N I N G
//  -------------
//
// This file is not part of the Qt API.  It exists for the convenience
// of other Qt classes.  This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//

#include <QtGui/private/qtguiglobal_p.h>
#include "QtCore/qstring.h"
#include "QtCore/qvarlengtharray.h"
#include "QtCore/qnamespace.h"
#include "QtGui/qtextlayout.h"
#include "private/qtextformat_p.h"
#include "private/qfont_p.h"
#include "QtCore/qvector.h"
#include "QtGui/qpaintengine.h"
#include "QtGui/qtextobject.h"
#include "QtGui/qtextoption.h"
#include "QtGui/qtextcursor.h"
#include "QtCore/qset.h"
#include "QtCore/qdebug.h"
#ifndef QT_BUILD_COMPAT_LIB
#include "private/qtextdocument_p.h"
#endif

#include "private/qfixed_p.h"

#include <private/qunicodetools_p.h>

#include <stdlib.h>
#include <vector>

QT_BEGIN_NAMESPACE

class QFontPrivate;
class QFontEngine;

class QString;
class QPainter;

class QAbstractTextDocumentLayout;

typedef quint32 glyph_t;

// this uses the same coordinate system as Qt, but a different one to freetype.
// * y is usually negative, and is equal to the ascent.
// * negative yoff means the following stuff is drawn higher up.
// the characters bounding rect is given by QRect(x,y,width,height), its advance by
// xoo and yoff
struct Q_GUI_EXPORT glyph_metrics_t
{
    inline glyph_metrics_t()
        : x(100000),  y(100000) {}
    inline glyph_metrics_t(QFixed _x, QFixed _y, QFixed _width, QFixed _height, QFixed _xoff, QFixed _yoff)
        : x(_x),
          y(_y),
          width(_width),
          height(_height),
          xoff(_xoff),
          yoff(_yoff)
        {}
    QFixed x;
    QFixed y;
    QFixed width;
    QFixed height;
    QFixed xoff;
    QFixed yoff;

    glyph_metrics_t transformed(const QTransform &xform) const;
    inline bool isValid() const {return x != 100000 && y != 100000;}

    inline QFixed leftBearing() const
    {
        if (!isValid())
            return QFixed();

        return x;
    }

    inline QFixed rightBearing() const
    {
        if (!isValid())
            return QFixed();

        return xoff - x - width;
    }
};
Q_DECLARE_TYPEINFO(glyph_metrics_t, Q_PRIMITIVE_TYPE);

struct Q_AUTOTEST_EXPORT QScriptAnalysis
{
    enum Flags {
        None = 0,
        Lowercase = 1,
        Uppercase = 2,
        SmallCaps = 3,
        LineOrParagraphSeparator = 4,
        Space = 5,
        SpaceTabOrObject = Space,
        Nbsp = 6,
        Tab = 7,
        TabOrObject = Tab,
        Object = 8
    };
    enum BidiFlags {
        BidiBN = 1,
        BidiMaybeResetToParagraphLevel = 2,
        BidiResetToParagraphLevel = 4,
        BidiMirrored = 8
    };
    unsigned short script    : 8;
    unsigned short flags     : 4;
    unsigned short bidiFlags : 4;
    unsigned short bidiLevel : 8;  // Unicode Bidi algorithm embedding level (0-125)
    QChar::Direction bidiDirection : 8; // used when running the bidi algorithm
    inline bool operator == (const QScriptAnalysis &other) const {
        return script == other.script && bidiLevel == other.bidiLevel && flags == other.flags;
    }
};
Q_DECLARE_TYPEINFO(QScriptAnalysis, Q_PRIMITIVE_TYPE);

struct QGlyphJustification
{
    inline QGlyphJustification()
        : type(0), nKashidas(0), space_18d6(0)
    {}

    enum JustificationType {
        JustifyNone,
        JustifySpace,
        JustifyKashida
    };

    uint type :2;
    uint nKashidas : 6; // more do not make sense...
    uint space_18d6 : 24;
};
Q_DECLARE_TYPEINFO(QGlyphJustification, Q_PRIMITIVE_TYPE);

struct QGlyphAttributes {
    uchar clusterStart  : 1;
    uchar dontPrint     : 1;
    uchar justification : 4;
    uchar reserved      : 2;
};
Q_STATIC_ASSERT(sizeof(QGlyphAttributes) == 1);
Q_DECLARE_TYPEINFO(QGlyphAttributes, Q_PRIMITIVE_TYPE);

struct QGlyphLayout
{
    enum {
        SpaceNeeded = sizeof(glyph_t) + sizeof(QFixed) + sizeof(QFixedPoint)
                    + sizeof(QGlyphAttributes) + sizeof(QGlyphJustification)
    };

    // init to 0 not needed, done when shaping
    QFixedPoint *offsets; // 8 bytes per element
    glyph_t *glyphs; // 4 bytes per element
    QFixed *advances; // 4 bytes per element
    QGlyphJustification *justifications; // 4 bytes per element
    QGlyphAttributes *attributes; // 1 byte per element

    int numGlyphs;

    inline QGlyphLayout() : numGlyphs(0) {}

    inline explicit QGlyphLayout(char *address, int totalGlyphs)
    {
        offsets = reinterpret_cast<QFixedPoint *>(address);
        int offset = totalGlyphs * sizeof(QFixedPoint);
        glyphs = reinterpret_cast<glyph_t *>(address + offset);
        offset += totalGlyphs * sizeof(glyph_t);
        advances = reinterpret_cast<QFixed *>(address + offset);
        offset += totalGlyphs * sizeof(QFixed);
        justifications = reinterpret_cast<QGlyphJustification *>(address + offset);
        offset += totalGlyphs * sizeof(QGlyphJustification);
        attributes = reinterpret_cast<QGlyphAttributes *>(address + offset);
        numGlyphs = totalGlyphs;
    }

    inline QGlyphLayout mid(int position, int n = -1) const {
        QGlyphLayout copy = *this;
        copy.glyphs += position;
        copy.advances += position;
        copy.offsets += position;
        copy.justifications += position;
        copy.attributes += position;
        if (n == -1)
            copy.numGlyphs -= position;
        else
            copy.numGlyphs = n;
        return copy;
    }

    inline QFixed effectiveAdvance(int item) const
    { return (advances[item] + QFixed::fromFixed(justifications[item].space_18d6)) * !attributes[item].dontPrint; }

    inline void clear(int first = 0, int last = -1) {
        if (last == -1)
            last = numGlyphs;
        if (first == 0 && last == numGlyphs
            && reinterpret_cast<char *>(offsets + numGlyphs) == reinterpret_cast<char *>(glyphs)) {
            memset(static_cast<void *>(offsets), 0, (numGlyphs * SpaceNeeded));
        } else {
            const int num = last - first;
            memset(static_cast<void *>(offsets + first), 0, num * sizeof(QFixedPoint));
            memset(glyphs + first, 0, num * sizeof(glyph_t));
            memset(static_cast<void *>(advances + first), 0, num * sizeof(QFixed));
            memset(static_cast<void *>(justifications + first), 0, num * sizeof(QGlyphJustification));
            memset(attributes + first, 0, num * sizeof(QGlyphAttributes));
        }
    }

    inline char *data() {
        return reinterpret_cast<char *>(offsets);
    }

    void grow(char *address, int totalGlyphs);
};

class QVarLengthGlyphLayoutArray : private QVarLengthArray<void *>, public QGlyphLayout
{
private:
    typedef QVarLengthArray<void *> Array;
public:
    QVarLengthGlyphLayoutArray(int totalGlyphs)
        : Array((totalGlyphs * SpaceNeeded) / sizeof(void *) + 1)
        , QGlyphLayout(reinterpret_cast<char *>(Array::data()), totalGlyphs)
    {
        memset(Array::data(), 0, Array::size() * sizeof(void *));
    }

    void resize(int totalGlyphs)
    {
        Array::resize((totalGlyphs * SpaceNeeded) / sizeof(void *) + 1);

        *((QGlyphLayout *)this) = QGlyphLayout(reinterpret_cast<char *>(Array::data()), totalGlyphs);
        memset(Array::data(), 0, Array::size() * sizeof(void *));
    }
};

template <int N> struct QGlyphLayoutArray : public QGlyphLayout
{
public:
    QGlyphLayoutArray()
        : QGlyphLayout(reinterpret_cast<char *>(buffer), N)
    {
        memset(buffer, 0, sizeof(buffer));
    }

private:
    void *buffer[(N * SpaceNeeded) / sizeof(void *) + 1];
};

struct QScriptItem;
/// Internal QTextItem
class QTextItemInt : public QTextItem
{
public:
    inline QTextItemInt() = default;
    QTextItemInt(const QScriptItem &si, QFont *font, const QTextCharFormat &format = QTextCharFormat());
    QTextItemInt(const QGlyphLayout &g, QFont *font, const QChar *chars, int numChars, QFontEngine *fe,
                 const QTextCharFormat &format = QTextCharFormat());

    /// copy the structure items, adjusting the glyphs arrays to the right subarrays.
    /// the width of the returned QTextItemInt is not adjusted, for speed reasons
    QTextItemInt midItem(QFontEngine *fontEngine, int firstGlyphIndex, int numGlyphs) const;
    void initWithScriptItem(const QScriptItem &si);

    QFixed descent;
    QFixed ascent;
    QFixed width;

    RenderFlags flags;
    bool justified = false;
    QTextCharFormat::UnderlineStyle underlineStyle = QTextCharFormat::NoUnderline;
    const QTextCharFormat charFormat;
    int num_chars = 0;
    const QChar *chars = nullptr;
    const unsigned short *logClusters = nullptr;
    const QFont *f = nullptr;

    QGlyphLayout glyphs;
    QFontEngine *fontEngine = nullptr;
};

struct QScriptItem
{
    Q_DECL_CONSTEXPR QScriptItem(int p, QScriptAnalysis a) noexcept
        : position(p), analysis(a),
          num_glyphs(0), descent(-1), ascent(-1), leading(-1), width(-1),
          glyph_data_offset(0) {}

    int position;
    QScriptAnalysis analysis;
    unsigned short num_glyphs;
    QFixed descent;
    QFixed ascent;
    QFixed leading;
    QFixed width;
    int glyph_data_offset;
    Q_DECL_CONSTEXPR QFixed height() const noexcept { return ascent + descent; }
private:
    friend class QVector<QScriptItem>;
    QScriptItem() {} // for QVector, don't use
};
Q_DECLARE_TYPEINFO(QScriptItem, Q_PRIMITIVE_TYPE);

typedef QVector<QScriptItem> QScriptItemArray;

struct Q_AUTOTEST_EXPORT QScriptLine
{
    // created and filled in QTextLine::layout_helper
    QScriptLine()
        : from(0), trailingSpaces(0), length(0),
        justified(0), gridfitted(0),
        hasTrailingSpaces(0), leadingIncluded(0) {}
    QFixed descent;
    QFixed ascent;
    QFixed leading;
    QFixed x;
    QFixed y;
    QFixed width;
    QFixed textWidth;
    QFixed textAdvance;
    int from;
    unsigned short trailingSpaces;
    signed int length : 28;
    mutable uint justified : 1;
    mutable uint gridfitted : 1;
    uint hasTrailingSpaces : 1;
    uint leadingIncluded : 1;
    QFixed height() const { return ascent + descent
                            + (leadingIncluded?  qMax(QFixed(),leading) : QFixed()); }
    QFixed base() const { return ascent; }
    void setDefaultHeight(QTextEngine *eng);
    void operator+=(const QScriptLine &other);
};
Q_DECLARE_TYPEINFO(QScriptLine, Q_PRIMITIVE_TYPE);


inline void QScriptLine::operator+=(const QScriptLine &other)
{
    leading= qMax(leading + ascent, other.leading + other.ascent) - qMax(ascent, other.ascent);
    descent = qMax(descent, other.descent);
    ascent = qMax(ascent, other.ascent);
    textWidth += other.textWidth;
    length += other.length;
}

typedef QVector<QScriptLine> QScriptLineArray;

class QFontPrivate;
class QTextFormatCollection;

class Q_GUI_EXPORT QTextEngine {
public:
    enum LayoutState {
        LayoutEmpty,
        InLayout,
        LayoutFailed
    };
    struct Q_GUI_EXPORT LayoutData {
        LayoutData(const QString &str, void **stack_memory, int mem_size);
        LayoutData();
        ~LayoutData();
        mutable QScriptItemArray items;
        int allocated;
        int available_glyphs;
        void **memory;
        unsigned short *logClustersPtr;
        QGlyphLayout glyphLayout;
        mutable int used;
        uint hasBidi : 1;
        uint layoutState : 2;
        uint memory_on_stack : 1;
        uint haveCharAttributes : 1;
        QString string;
        bool reallocate(int totalGlyphs);
    };

    struct ItemDecoration {
        ItemDecoration() {} // for QVector, don't use
        ItemDecoration(qreal x1, qreal x2, qreal y, const QPen &pen):
            x1(x1), x2(x2), y(y), pen(pen) {}

        qreal x1;
        qreal x2;
        qreal y;
        QPen pen;
    };

    typedef QVector<ItemDecoration> ItemDecorationList;

    QTextEngine();
    QTextEngine(const QString &str, const QFont &f);
    ~QTextEngine();

    enum Mode {
        WidthOnly = 0x07
    };

    void invalidate();
    void clearLineData();

    void validate() const;
    void itemize() const;

    bool isRightToLeft() const;
    static void bidiReorder(int numRuns, const quint8 *levels, int *visualOrder);

    const QCharAttributes *attributes() const;

    void shape(int item) const;

    void justify(const QScriptLine &si);
    QFixed alignLine(const QScriptLine &line);

    QFixed width(int charFrom, int numChars) const;
    glyph_metrics_t boundingBox(int from,  int len) const;
    glyph_metrics_t tightBoundingBox(int from,  int len) const;

    int length(int item) const {
        const QScriptItem &si = layoutData->items[item];
        int from = si.position;
        item++;
        return (item < layoutData->items.size() ? layoutData->items[item].position : layoutData->string.length()) - from;
    }
    int length(const QScriptItem *si) const {
        int end;
        if (si + 1 < layoutData->items.constData()+ layoutData->items.size())
            end = (si+1)->position;
        else
            end = layoutData->string.length();
        return end - si->position;
    }

    QFontEngine *fontEngine(const QScriptItem &si, QFixed *ascent = nullptr, QFixed *descent = nullptr, QFixed *leading = nullptr) const;
    QFont font(const QScriptItem &si) const;
    inline QFont font() const { return fnt; }

    /**
     * Returns a pointer to an array of log clusters, offset at the script item.
     * Each item in the array is a unsigned short.  For each character in the original string there is an entry in the table
     * so there is a one to one correlation in indexes between the original text and the index in the logcluster.
     * The value of each item is the position in the glyphs array. Multiple similar pointers in the logclusters array imply
     * that one glyph is used for more than one character.
     * \sa glyphs()
     */
    inline unsigned short *logClusters(const QScriptItem *si) const
        { return layoutData->logClustersPtr+si->position; }
    /**
     * Returns an array of QGlyphLayout items, offset at the script item.
     * Each item in the array matches one glyph in the text, storing the advance, position etc.
     * The returned item's length equals to the number of available glyphs. This may be more
     * than what was actually shaped.
     * \sa logClusters()
     */
    inline QGlyphLayout availableGlyphs(const QScriptItem *si) const {
        return layoutData->glyphLayout.mid(si->glyph_data_offset);
    }
    /**
     * Returns an array of QGlyphLayout items, offset at the script item.
     * Each item in the array matches one glyph in the text, storing the advance, position etc.
     * The returned item's length equals to the number of shaped glyphs.
     * \sa logClusters()
     */
    inline QGlyphLayout shapedGlyphs(const QScriptItem *si) const {
        return layoutData->glyphLayout.mid(si->glyph_data_offset, si->num_glyphs);
    }

    inline bool ensureSpace(int nGlyphs) const {
        if (layoutData->glyphLayout.numGlyphs - layoutData->used < nGlyphs)
            return layoutData->reallocate((((layoutData->used + nGlyphs)*3/2 + 15) >> 4) << 4);
        return true;
    }

    void freeMemory();

    int findItem(int strPos, int firstItem = 0) const;
    inline QTextFormatCollection *formatCollection() const {
        if (block.docHandle())
            return block.docHandle()->formatCollection();
        return specialData ? specialData->formatCollection.data() : nullptr;
    }
    QTextCharFormat format(const QScriptItem *si) const;
    inline QAbstractTextDocumentLayout *docLayout() const {
        Q_ASSERT(block.docHandle());
        return block.docHandle()->document()->documentLayout();
    }
    int formatIndex(const QScriptItem *si) const;

    /// returns the width of tab at index (in the tabs array) with the tab-start at position x
    QFixed calculateTabWidth(int index, QFixed x) const;

    mutable QScriptLineArray lines;

private:
    struct FontEngineCache {
        FontEngineCache();
        mutable QFontEngine *prevFontEngine;
        mutable QFontEngine *prevScaledFontEngine;
        mutable int prevScript;
        mutable int prevPosition;
        mutable int prevLength;
        inline void reset() {
            prevFontEngine = nullptr;
            prevScaledFontEngine = nullptr;
            prevScript = -1;
            prevPosition = -1;
            prevLength = -1;
        }
    };
    mutable FontEngineCache feCache;

public:
    QString text;
    mutable QFont fnt;
#ifndef QT_NO_RAWFONT
    QRawFont rawFont;
#endif
    QTextBlock block;

    QTextOption option;

    QFixed minWidth;
    QFixed maxWidth;
    QPointF position;
    uint ignoreBidi : 1;
    uint cacheGlyphs : 1;
    uint stackEngine : 1;
    uint forceJustification : 1;
    uint visualMovement : 1;
    uint delayDecorations: 1;
#ifndef QT_NO_RAWFONT
    uint useRawFont : 1;
#endif

    mutable LayoutData *layoutData;

    ItemDecorationList underlineList;
    ItemDecorationList strikeOutList;
    ItemDecorationList overlineList;

    inline bool visualCursorMovement() const
    { return visualMovement || (block.docHandle() && block.docHandle()->defaultCursorMoveStyle == Qt::VisualMoveStyle); }

    inline int preeditAreaPosition() const { return specialData ? specialData->preeditPosition : -1; }
    inline QString preeditAreaText() const { return specialData ? specialData->preeditText : QString(); }
    void setPreeditArea(int position, const QString &text);

    inline bool hasFormats() const
    { return block.docHandle() || (specialData && !specialData->formats.isEmpty()); }
    inline QVector<QTextLayout::FormatRange> formats() const
    { return specialData ? specialData->formats : QVector<QTextLayout::FormatRange>(); }
    void setFormats(const QVector<QTextLayout::FormatRange> &formats);

private:
    static void init(QTextEngine *e);

    struct SpecialData {
        int preeditPosition;
        QString preeditText;
        QVector<QTextLayout::FormatRange> formats;
        QVector<QTextCharFormat> resolvedFormats;
        // only used when no docHandle is available
        QScopedPointer<QTextFormatCollection> formatCollection;
    };
    SpecialData *specialData;

    void indexFormats();
    void resolveFormats() const;

public:
    bool atWordSeparator(int position) const;

    QString elidedText(Qt::TextElideMode mode, const QFixed &width, int flags = 0, int from = 0, int count = -1) const;

    void shapeLine(const QScriptLine &line);
    QFixed leadingSpaceWidth(const QScriptLine &line);

    QFixed offsetInLigature(const QScriptItem *si, int pos, int max, int glyph_pos);
    int positionInLigature(const QScriptItem *si, int end, QFixed x, QFixed edge, int glyph_pos, bool cursorOnCharacter);
    int previousLogicalPosition(int oldPos) const;
    int nextLogicalPosition(int oldPos) const;
    int lineNumberForTextPosition(int pos);
    int positionAfterVisualMovement(int oldPos, QTextCursor::MoveOperation op);
    std::vector<int> insertionPointsForLine(int lineNum);
    void resetFontEngineCache();

    void enableDelayDecorations(bool enable = true) { delayDecorations = enable; }

    void addUnderline(QPainter *painter, const QLineF &line);
    void addStrikeOut(QPainter *painter, const QLineF &line);
    void addOverline(QPainter *painter, const QLineF &line);

    void drawDecorations(QPainter *painter);
    void clearDecorations();
    void adjustUnderlines();

private:
    void addItemDecoration(QPainter *painter, const QLineF &line, ItemDecorationList *decorationList);
    void adjustUnderlines(ItemDecorationList::iterator start,
                          ItemDecorationList::iterator end,
                          qreal underlinePos, qreal penWidth);
    void drawItemDecorationList(QPainter *painter, const ItemDecorationList &decorationList);
    void setBoundary(int strPos) const;
    void addRequiredBoundaries() const;
    void shapeText(int item) const;
#if QT_CONFIG(harfbuzz)
    int shapeTextWithHarfbuzzNG(const QScriptItem &si,
                                const ushort *string,
                                int itemLength,
                                QFontEngine *fontEngine,
                                const QVector<uint> &itemBoundaries,
                                bool kerningEnabled,
                                bool hasLetterSpacing) const;
#endif
    int shapeTextWithHarfbuzz(const QScriptItem &si, const ushort *string, int itemLength, QFontEngine *fontEngine, const QVector<uint> &itemBoundaries, bool kerningEnabled) const;

    int endOfLine(int lineNum);
    int beginningOfLine(int lineNum);
    int getClusterLength(unsigned short *logClusters, const QCharAttributes *attributes, int from, int to, int glyph_pos, int *start);
};

class Q_GUI_EXPORT QStackTextEngine : public QTextEngine {
public:
    enum { MemSize = 256*40/sizeof(void *) };
    QStackTextEngine(const QString &string, const QFont &f);
    LayoutData _layoutData;
    void *_memory[MemSize];
};
Q_DECLARE_TYPEINFO(QTextEngine::ItemDecoration, Q_MOVABLE_TYPE);

struct QTextLineItemIterator
{
    QTextLineItemIterator(QTextEngine *eng, int lineNum, const QPointF &pos = QPointF(),
                          const QTextLayout::FormatRange *_selection = nullptr);

    inline bool atEnd() const { return logicalItem >= nItems - 1; }
    inline bool atBeginning() const { return logicalItem <= 0; }
    QScriptItem &next();

    bool getSelectionBounds(QFixed *selectionX, QFixed *selectionWidth) const;
    inline bool isOutsideSelection() const {
        QFixed tmp1, tmp2;
        return !getSelectionBounds(&tmp1, &tmp2);
    }

    QTextEngine *eng;

    QFixed x;
    const QScriptLine &line;
    QScriptItem *si;

    const int lineNum;
    const int lineEnd;
    const int firstItem;
    const int lastItem;
    const int nItems;
    int logicalItem;
    int item;
    int itemLength;

    int glyphsStart;
    int glyphsEnd;
    int itemStart;
    int itemEnd;

    QFixed itemWidth;

    QVarLengthArray<int> visualOrder;

    const QTextLayout::FormatRange *selection;
};

QT_END_NAMESPACE

#endif // QTEXTENGINE_P_H