Introduce QGlyphRun::stringIndexes()

This introduces a way to trace each entry in the glyph index
array to a specific index in the original text passed to
QTextLayout, as well as a convenience function to access
the original string from the QGlyphRun.

The index information is stored in the logClusters array internally
in Qt, but it contains the inverse information: For each
character in the output string, it contains an index into the
glyph array. In order to get the string indexes for each glyph,
which makes a lot more sense in the context of the QGlyphRun
API, we need to do a little search to construct the data.

To avoid adding unnecessary allocations, we make the new APIs
opt-in. If you do not specify anything, you will only get the
glyph indexes and glyph positions as before. However, you
can now specify exactly which parts of the layout to extract
using an optional flags parameter.

This also adds a manual test which can be very handy to
visualize QTextLayouts and how they are split into QGlyphRuns.

Fixes: QTBUG-103932
Change-Id: Ie4288fff338b9482aba0aba29fc7e1e59fa60900
Reviewed-by: Lars Knoll <lars@knoll.priv.no>

5 files changed, 250 insertions, 15 deletions

diff --git a/src/gui/text/qglyphrun.cpp b/src/gui/text/qglyphrun.cpp
index 371dd26637..389b7403fd 100644
--- a/src/gui/text/qglyphrun.cpp
+++ b/src/gui/text/qglyphrun.cpp
@@ -465,7 +465,72 @@ QRectF QGlyphRun::boundingRect() const
 */
 bool QGlyphRun::isEmpty() const
 {
-    return d->glyphIndexDataSize == 0;
+    return d->glyphIndexDataSize == 0
+            && d->glyphPositionDataSize == 0
+            && d->stringIndexes.isEmpty()
+            && d->sourceString.isEmpty();
+}
+
+/*!
+    Returns the string indexes corresponding to each glyph index, if the glyph run has been
+    constructed from a string and string indexes have been requested from the layout. In this case,
+    the length of the returned vector will correspond to the length of glyphIndexes(). In other
+    cases, it will be empty.
+
+    Since a single glyph may correspond to multiple characters in the source string, there may be
+    gaps in the list of string indexes. For instance, if the string "first" is processed by a font
+    which contains a ligature for the character pair "fi", then the five character string will
+    generate a glyph run consisting of only four glyphs. Then the glyph indexes may in this case be
+    (1, 2, 3, 4) (four arbitrary glyph indexes) whereas the string indexes would be (0, 2, 3, 4).
+    The glyphs are in the logical order of the string, thus it is implied that the first glyphs
+    spans characters 0 and 1 in this case.
+
+    Inversely, a single character may also generate multiple glyphs, in which case there will be
+    duplicate entries in the list of string indexes.
+
+    The string indexes correspond to the string, optionally available through sourceString().
+
+    \sa setStringIndexes(), sourceString(), QTextLayout::glyphRuns()
+*/
+QList<qsizetype> QGlyphRun::stringIndexes() const
+{
+    return d->stringIndexes;
+}
+
+/*!
+   Sets the list of string indexes corresponding to the glyph indexes to \a stringIndexes
+
+   See stringIndexes() for more details on the conventions of this list.
+
+   \sa sourceString()
+ */
+void QGlyphRun::setStringIndexes(const QList<qsizetype> &stringIndexes)
+{
+    detach();
+    d->stringIndexes = stringIndexes;
+}
+
+/*!
+    Returns the string corresponding to the glyph run, if the glyph run has been created from
+    a string and the string has been requested from the layout.
+
+    \sa setSourceString(), stringIndexes(), QTextLayout::glyphRuns()
+ */
+QString QGlyphRun::sourceString() const
+{
+    return d->sourceString;
+}
+
+/*!
+    Set the string corresponding to the glyph run to \a sourceString. If set, the indexes returned
+    by stringIndexes() should be indexes into this string.
+
+    \sa sourceString(), stringIndexes()
+ */
+void QGlyphRun::setSourceString(const QString &sourceString)
+{
+    detach();
+    d->sourceString = sourceString;
 }
 
 QT_END_NAMESPACE
diff --git a/src/gui/text/qglyphrun.h b/src/gui/text/qglyphrun.h
index 47c41d849d..a338a35bc1 100644
--- a/src/gui/text/qglyphrun.h
+++ b/src/gui/text/qglyphrun.h
@@ -74,6 +74,12 @@ public:
     void setBoundingRect(const QRectF &boundingRect);
     QRectF boundingRect() const;
 
+    QList<qsizetype> stringIndexes() const;
+    void setStringIndexes(const QList<qsizetype> &stringIndexes);
+
+    void setSourceString(const QString &sourceString);
+    QString sourceString() const;
+
     bool isEmpty() const;
 
 private:
diff --git a/src/gui/text/qglyphrun_p.h b/src/gui/text/qglyphrun_p.h
index 75bc832f77..c95ec8ab7f 100644
--- a/src/gui/text/qglyphrun_p.h
+++ b/src/gui/text/qglyphrun_p.h
@@ -42,8 +42,10 @@ public:
       : QSharedData(other)
       , glyphIndexes(other.glyphIndexes)
       , glyphPositions(other.glyphPositions)
+      , stringIndexes(other.stringIndexes)
       , rawFont(other.rawFont)
       , boundingRect(other.boundingRect)
+      , sourceString(other.sourceString)
       , flags(other.flags)
       , glyphIndexData(other.glyphIndexData)
       , glyphIndexDataSize(other.glyphIndexDataSize)
@@ -56,8 +58,10 @@ public:
 
     QList<quint32> glyphIndexes;
     QList<QPointF> glyphPositions;
+    QList<qsizetype> stringIndexes;
     QRawFont rawFont;
     QRectF boundingRect;
+    QString sourceString;
 
     QGlyphRun::GlyphRunFlags flags;
 
diff --git a/src/gui/text/qtextlayout.cpp b/src/gui/text/qtextlayout.cpp
index 9cf5d8963b..43236eec91 100644
--- a/src/gui/text/qtextlayout.cpp
+++ b/src/gui/text/qtextlayout.cpp
@@ -282,6 +282,25 @@ Qt::LayoutDirection QTextInlineObject::textDirection() const
 */
 
 /*!
+    \enum QTextLayout::GlyphRunRetrievalFlag
+
+    GlyphRunRetrievalFlag specifies flags passed to the glyphRuns() functions to determine
+    which properties of the layout are returned in the QGlyphRun objects. Since each property
+    will consume memory and may require additional allocations, it is a good practice to only
+    request the properties you will need to access later.
+
+    \value RetrieveGlyphIndexes Retrieves the indexes in the font which correspond to the glyphs.
+    \value RetrieveGlyphPositions Retrieves the relative positions of the glyphs in the layout.
+    \value RetrieveStringIndexes Retrieves the indexes in the original string that correspond to
+           each of the glyphs.
+    \value RetrieveString Retrieves the original source string from the layout.
+    \value RetrieveAll Retrieves all available properties of the layout.
+    \omitvalue DefaultRetrievalFlags
+
+    \sa glyphRuns(), QTextLine::glyphRuns()
+*/
+
+/*!
     \fn QTextEngine *QTextLayout::engine() const
     \internal
 
@@ -961,7 +980,9 @@ static inline QRectF clipIfValid(const QRectF &rect, const QRectF &clip)
 }
 
 
+#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
 /*!
+    \overload
     Returns the glyph indexes and positions for all glyphs corresponding to the \a length characters
     starting at the position \a from in this QTextLayout. This is an expensive function, and should
     not be called in a time sensitive context.
@@ -969,13 +990,45 @@ static inline QRectF clipIfValid(const QRectF &rect, const QRectF &clip)
     If \a from is less than zero, then the glyph run will begin at the first character in the
     layout. If \a length is less than zero, it will span the entire string from the start position.
 
+    \note This is equivalent to calling
+    glyphRuns(from,
+              length,
+              QTextLayout::GlyphRunRetrievalFlag::GlyphIndexes |
+                QTextLayout::GlyphRunRetrievalFlag::GlyphPositions).
+
     \since 4.8
 
     \sa draw(), QPainter::drawGlyphRun()
 */
-#if !defined(QT_NO_RAWFONT)
+#  if !defined(QT_NO_RAWFONT)
 QList<QGlyphRun> QTextLayout::glyphRuns(int from, int length) const
 {
+    return glyphRuns(from, length, QTextLayout::GlyphRunRetrievalFlag::DefaultRetrievalFlags);
+}
+#  endif
+#endif
+
+/*!
+    \overload
+    Returns the glyph indexes and positions for all glyphs corresponding to the \a length characters
+    starting at the position \a from in this QTextLayout. This is an expensive function, and should
+    not be called in a time sensitive context.
+
+    If \a from is less than zero, then the glyph run will begin at the first character in the
+    layout. If \a length is less than zero, it will span the entire string from the start position.
+
+    The \a retrievalFlags specifies which properties of the QGlyphRun will be retrieved from the
+    layout. To minimize allocations and memory consumption, this should be set to include only the
+    properties that you need to access later.
+
+    \since 6.5
+    \sa draw(), QPainter::drawGlyphRun()
+*/
+#if !defined(QT_NO_RAWFONT)
+QList<QGlyphRun> QTextLayout::glyphRuns(int from,
+                                        int length,
+                                        QTextLayout::GlyphRunRetrievalFlags retrievalFlags) const
+{
     if (from < 0)
         from = 0;
     if (length < 0)
@@ -986,10 +1039,11 @@ QList<QGlyphRun> QTextLayout::glyphRuns(int from, int length) const
         if (d->lines.at(i).from > from + length)
             break;
         else if (d->lines.at(i).from + d->lines[i].length >= from) {
-            QList<QGlyphRun> glyphRuns = QTextLine(i, d).glyphRuns(from, length);
+            QList<QGlyphRun> glyphRuns = QTextLine(i, d).glyphRuns(from, length, retrievalFlags);
 
             for (int j = 0; j < glyphRuns.size(); j++) {
                 const QGlyphRun &glyphRun = glyphRuns.at(j);
+
                 QRawFont rawFont = glyphRun.rawFont();
 
                 QFontEngine *fontEngine = rawFont.d->fontEngine;
@@ -1002,14 +1056,17 @@ QList<QGlyphRun> QTextLayout::glyphRuns(int from, int length) const
                 } else {
                     QList<quint32> indexes = oldGlyphRun.glyphIndexes();
                     QList<QPointF> positions = oldGlyphRun.positions();
+                    QList<qsizetype> stringIndexes = oldGlyphRun.stringIndexes();
                     QRectF boundingRect = oldGlyphRun.boundingRect();
 
                     indexes += glyphRun.glyphIndexes();
                     positions += glyphRun.positions();
+                    stringIndexes += glyphRun.stringIndexes();
                     boundingRect = boundingRect.united(glyphRun.boundingRect());
 
                     oldGlyphRun.setGlyphIndexes(indexes);
                     oldGlyphRun.setPositions(positions);
+                    oldGlyphRun.setStringIndexes(stringIndexes);
                     oldGlyphRun.setBoundingRect(boundingRect);
                 }
             }
@@ -2186,9 +2243,11 @@ static void setPenAndDrawBackground(QPainter *p, const QPen &defaultPen, const Q
 
 #if !defined(QT_NO_RAWFONT)
 static QGlyphRun glyphRunWithInfo(QFontEngine *fontEngine,
+                                  const QString &text,
                                   const QGlyphLayout &glyphLayout,
                                   const QPointF &pos,
                                   const QGlyphRun::GlyphRunFlags &flags,
+                                  QTextLayout::GlyphRunRetrievalFlags retrievalFlags,
                                   QFixed selectionX,
                                   QFixed selectionWidth,
                                   int glyphsStart,
@@ -2204,14 +2263,15 @@ static QGlyphRun glyphRunWithInfo(QFontEngine *fontEngine,
     QGlyphRunPrivate *d = QGlyphRunPrivate::get(glyphRun);
 
     int rangeStart = textPosition;
-    while (*logClusters != glyphsStart && rangeStart < textPosition + textLength) {
-        ++logClusters;
+    int logClusterIndex = 0;
+    while (logClusters[logClusterIndex] != glyphsStart && rangeStart < textPosition + textLength) {
+        ++logClusterIndex;
         ++rangeStart;
     }
 
     int rangeEnd = rangeStart;
-    while (*logClusters != glyphsEnd && rangeEnd < textPosition + textLength) {
-        ++logClusters;
+    while (logClusters[logClusterIndex] != glyphsEnd && rangeEnd < textPosition + textLength) {
+        ++logClusterIndex;
         ++rangeEnd;
     }
 
@@ -2244,14 +2304,43 @@ static QGlyphRun glyphRunWithInfo(QFontEngine *fontEngine,
     qreal minY = 0;
     qreal maxY = 0;
     QList<quint32> glyphs;
-    glyphs.reserve(glyphsArray.size());
+    if (retrievalFlags & QTextLayout::RetrieveGlyphIndexes)
+        glyphs.reserve(glyphsArray.size());
     QList<QPointF> positions;
-    positions.reserve(glyphsArray.size());
-    for (int i=0; i<glyphsArray.size(); ++i) {
-        glyphs.append(glyphsArray.at(i) & 0xffffff);
+    if (retrievalFlags & QTextLayout::RetrieveGlyphPositions)
+        positions.reserve(glyphsArray.size());
+    QList<qsizetype> stringIndexes;
+    if (retrievalFlags & QTextLayout::RetrieveStringIndexes)
+        stringIndexes.reserve(glyphsArray.size());
+
+    int nextClusterIndex = 0;
+    int currentClusterIndex = 0;
+    for (int i = 0; i < glyphsArray.size(); ++i) {
+        const int glyphArrayIndex = i + glyphsStart;
+        // Search for the next cluster in the string (or the end of string if there are no
+        // more clusters)
+        if (retrievalFlags & QTextLayout::RetrieveStringIndexes) {
+            if (nextClusterIndex < textLength && logClusters[nextClusterIndex] == glyphArrayIndex) {
+                currentClusterIndex = nextClusterIndex; // Store current cluster
+                while (logClusters[nextClusterIndex] == glyphArrayIndex && nextClusterIndex < textLength)
+                    ++nextClusterIndex;
+            }
+
+            // We are now either at end of string (no more clusters) or we are not yet at the
+            // next cluster in glyph array. We fill in current cluster so that there is always one
+            // entry in stringIndexes for each glyph.
+            Q_ASSERT(nextClusterIndex == textLength || logClusters[nextClusterIndex] != glyphArrayIndex);
+            stringIndexes.append(textPosition + currentClusterIndex);
+        }
+
+        if (retrievalFlags & QTextLayout::RetrieveGlyphIndexes) {
+            glyph_t glyphIndex = glyphsArray.at(i) & 0xffffff;
+            glyphs.append(glyphIndex);
+        }
 
         QPointF position = positionsArray.at(i).toPointF() + pos;
-        positions.append(position);
+        if (retrievalFlags & QTextLayout::RetrieveGlyphPositions)
+            positions.append(position);
 
         if (i == 0) {
             maxY = minY = position.y();
@@ -2263,8 +2352,14 @@ static QGlyphRun glyphRunWithInfo(QFontEngine *fontEngine,
 
     qreal height = maxY + fontHeight - minY;
 
-    glyphRun.setGlyphIndexes(glyphs);
-    glyphRun.setPositions(positions);
+    if (retrievalFlags & QTextLayout::RetrieveGlyphIndexes)
+        glyphRun.setGlyphIndexes(glyphs);
+    if (retrievalFlags & QTextLayout::RetrieveGlyphPositions)
+        glyphRun.setPositions(positions);
+    if (retrievalFlags & QTextLayout::RetrieveStringIndexes)
+        glyphRun.setStringIndexes(stringIndexes);
+    if (retrievalFlags & QTextLayout::RetrieveString)
+        glyphRun.setSourceString(text);
     glyphRun.setFlags(flags);
     glyphRun.setRawFont(font);
 
@@ -2274,7 +2369,9 @@ static QGlyphRun glyphRunWithInfo(QFontEngine *fontEngine,
     return glyphRun;
 }
 
+#  if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
 /*!
+    \overload
     Returns the glyph indexes and positions for all glyphs in this QTextLine for characters
     in the range defined by \a from and \a length. The \a from index is relative to the beginning
     of the text in the containing QTextLayout, and the range must be within the range of QTextLine
@@ -2283,12 +2380,43 @@ static QGlyphRun glyphRunWithInfo(QFontEngine *fontEngine,
     If \a from is negative, it will default to textStart(), and if \a length is negative it will
     default to the return value of textLength().
 
+    \note This is equivalent to calling
+    glyphRuns(from,
+              length,
+              QTextLayout::GlyphRunRetrievalFlag::GlyphIndexes |
+                QTextLayout::GlyphRunRetrievalFlag::GlyphPositions).
+
     \since 5.0
 
     \sa QTextLayout::glyphRuns()
 */
 QList<QGlyphRun> QTextLine::glyphRuns(int from, int length) const
 {
+    return glyphRuns(from, length, QTextLayout::GlyphRunRetrievalFlag::DefaultRetrievalFlags);
+}
+#  endif
+
+/*!
+    Returns the glyph indexes and positions for all glyphs in this QTextLine for characters
+    in the range defined by \a from and \a length. The \a from index is relative to the beginning
+    of the text in the containing QTextLayout, and the range must be within the range of QTextLine
+    as given by functions textStart() and textLength().
+
+    The \a retrievalFlags specifies which properties of the QGlyphRun will be retrieved from the
+    layout. To minimize allocations and memory consumption, this should be set to include only the
+    properties that you need to access later.
+
+    If \a from is negative, it will default to textStart(), and if \a length is negative it will
+    default to the return value of textLength().
+
+    \since 6.5
+
+    \sa QTextLayout::glyphRuns()
+*/
+QList<QGlyphRun> QTextLine::glyphRuns(int from,
+                                      int length,
+                                      QTextLayout::GlyphRunRetrievalFlags retrievalFlags) const
+{
     const QScriptLine &line = eng->lines.at(index);
 
     if (line.length == 0)
@@ -2405,9 +2533,11 @@ QList<QGlyphRun> QTextLine::glyphRuns(int from, int length) const
                         subFlags |= QGlyphRun::SplitLigature;
 
                     glyphRuns.append(glyphRunWithInfo(multiFontEngine->engine(which),
+                                                      eng->text,
                                                       subLayout,
                                                       pos,
                                                       subFlags,
+                                                      retrievalFlags,
                                                       x,
                                                       width,
                                                       glyphsStart + start,
@@ -2435,9 +2565,11 @@ QList<QGlyphRun> QTextLine::glyphRuns(int from, int length) const
                     subFlags |= QGlyphRun::SplitLigature;
 
                 QGlyphRun glyphRun = glyphRunWithInfo(multiFontEngine->engine(which),
+                                                      eng->text,
                                                       subLayout,
                                                       pos,
                                                       subFlags,
+                                                      retrievalFlags,
                                                       x,
                                                       width,
                                                       glyphsStart + start,
@@ -2451,9 +2583,11 @@ QList<QGlyphRun> QTextLine::glyphRuns(int from, int length) const
                 if (startsInsideLigature || endsInsideLigature)
                     flags |= QGlyphRun::SplitLigature;
                 QGlyphRun glyphRun = glyphRunWithInfo(mainFontEngine,
+                                                      eng->text,
                                                       glyphLayout,
                                                       pos,
                                                       flags,
+                                                      retrievalFlags,
                                                       x,
                                                       width,
                                                       glyphsStart,
diff --git a/src/gui/text/qtextlayout.h b/src/gui/text/qtextlayout.h
index 98054b8902..60ccb2ef27 100644
--- a/src/gui/text/qtextlayout.h
+++ b/src/gui/text/qtextlayout.h
@@ -69,6 +69,17 @@ class QTextOption;
 class Q_GUI_EXPORT QTextLayout
 {
 public:
+    enum GlyphRunRetrievalFlag {
+        RetrieveGlyphIndexes    = 0x1,
+        RetrieveGlyphPositions  = 0x2,
+        RetrieveStringIndexes   = 0x4,
+        RetrieveString          = 0x8,
+
+        DefaultRetrievalFlags   = RetrieveGlyphIndexes | RetrieveGlyphPositions,
+        RetrieveAll             = 0xffff
+    };
+    Q_DECLARE_FLAGS(GlyphRunRetrievalFlags, GlyphRunRetrievalFlag)
+
     // does itemization
     QTextLayout();
     QTextLayout(const QString& text);
@@ -148,7 +159,15 @@ public:
     qreal maximumWidth() const;
 
 #if !defined(QT_NO_RAWFONT)
+
+#  if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
+    QList<QGlyphRun> glyphRuns(int from, int length, GlyphRunRetrievalFlags flags) const;
     QList<QGlyphRun> glyphRuns(int from = -1, int length = -1) const;
+#  else
+    QList<QGlyphRun> glyphRuns(int from = -1,
+                               int length = -1,
+                               GlyphRunRetrievalFlags flags = GlyphRunRetrievalFlag::DefaultRetrievalFlags) const;
+#  endif
 #endif
 
     QTextEngine *engine() const { return d; }
@@ -166,7 +185,7 @@ private:
     QTextEngine *d;
 };
 Q_DECLARE_TYPEINFO(QTextLayout::FormatRange, Q_RELOCATABLE_TYPE);
-
+Q_DECLARE_OPERATORS_FOR_FLAGS(QTextLayout::GlyphRunRetrievalFlags)
 
 class Q_GUI_EXPORT QTextLine
 {
@@ -219,7 +238,14 @@ public:
     void draw(QPainter *painter, const QPointF &position) const;
 
 #if !defined(QT_NO_RAWFONT)
+#  if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
+    QList<QGlyphRun> glyphRuns(int from, int length, QTextLayout::GlyphRunRetrievalFlags flags) const;
     QList<QGlyphRun> glyphRuns(int from = -1, int length = -1) const;
+#  else
+    QList<QGlyphRun> glyphRuns(int from = -1,
+                               int length = -1,
+                               QTextLayout::GlyphRunRetrievalFlags flags = QTextLayout::GlyphRunRetrievalFlag::Default) const;
+#  endif
 #endif
 
 private: