compute subset of glyphs in SalLayoutGlyphsCache (tdf#139604)

When OutputDevice::ImplLayout() computes glyphs, the result
is always the same for the same string (and font etc.),
and if the function is asked to work on just a subset of the string,
the returned glyphs are often also a subset of glyphs for the full
string. Since e.g. EditEngine breaks text into lines by first
laying out a full string and then repeatedly calls the same function
for a subset of the string with increasing starting index. So if
the full result is cached, it's faster to just make a subset of that,
adjust it as necessary and return that, instead of doing a layout
again.

This requires support from harfbuzz to tell us if it's safe to break
at a given position, and HB_GLYPH_FLAG_UNSAFE_TO_BREAK is that
(https://harfbuzz.github.io/harfbuzz-hb-buffer.html#hb-glyph-flags-t).

I'm keeping the optimization for tdf#144515, as avoiding the extra
layout altogether is still useful.

Change-Id: I33f70f9af89be79056e464908eac0861f58d274a
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/132753
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

4 files changed, 174 insertions, 17 deletions

diff --git a/vcl/inc/impglyphitem.hxx b/vcl/inc/impglyphitem.hxx
index 7228911a3ed7..e86c2652100a 100644
--- a/vcl/inc/impglyphitem.hxx
+++ b/vcl/inc/impglyphitem.hxx
@@ -29,7 +29,7 @@
 #include "fontinstance.hxx"
 #include "glyphid.hxx"
 
-enum class GlyphItemFlags : sal_uInt8
+enum class GlyphItemFlags : sal_uInt16
 {
     NONE = 0,
     IS_IN_CLUSTER = 0x01,
@@ -39,11 +39,12 @@ enum class GlyphItemFlags : sal_uInt8
     IS_SPACING = 0x10,
     ALLOW_KASHIDA = 0x20,
     IS_DROPPED = 0x40,
-    IS_CLUSTER_START = 0x80
+    IS_CLUSTER_START = 0x80,
+    IS_UNSAFE_TO_BREAK = 0x100 // HB_GLYPH_FLAG_UNSAFE_TO_BREAK from harfbuzz
 };
 namespace o3tl
 {
-template <> struct typed_flags<GlyphItemFlags> : is_typed_flags<GlyphItemFlags, 0xff>
+template <> struct typed_flags<GlyphItemFlags> : is_typed_flags<GlyphItemFlags, 0x1ff>
 {
 };
 };
@@ -54,22 +55,24 @@ class VCL_DLLPUBLIC GlyphItem
     sal_Int32 m_nOrigWidth; // original glyph width
     sal_Int32 m_nCharPos; // index in string
     sal_Int32 m_nXOffset;
+    sal_Int32 m_nYOffset;
     sal_Int32 m_nNewWidth; // width after adjustments
     sal_GlyphId m_aGlyphId;
-    sal_Int8 m_nCharCount; // number of characters making up this glyph
     GlyphItemFlags m_nFlags;
+    sal_Int8 m_nCharCount; // number of characters making up this glyph
 
 public:
     GlyphItem(int nCharPos, int nCharCount, sal_GlyphId aGlyphId, const DevicePoint& rLinearPos,
-              GlyphItemFlags nFlags, int nOrigWidth, int nXOffset)
+              GlyphItemFlags nFlags, int nOrigWidth, int nXOffset, int nYOffset)
         : m_aLinearPos(rLinearPos)
         , m_nOrigWidth(nOrigWidth)
         , m_nCharPos(nCharPos)
         , m_nXOffset(nXOffset)
+        , m_nYOffset(nYOffset)
         , m_nNewWidth(nOrigWidth)
         , m_aGlyphId(aGlyphId)
-        , m_nCharCount(nCharCount)
         , m_nFlags(nFlags)
+        , m_nCharCount(nCharCount)
     {
     }
 
@@ -81,6 +84,7 @@ public:
     bool AllowKashida() const { return bool(m_nFlags & GlyphItemFlags::ALLOW_KASHIDA); }
     bool IsDropped() const { return bool(m_nFlags & GlyphItemFlags::IS_DROPPED); }
     bool IsClusterStart() const { return bool(m_nFlags & GlyphItemFlags::IS_CLUSTER_START); }
+    bool IsUnsafeToBreak() const { return bool(m_nFlags & GlyphItemFlags::IS_UNSAFE_TO_BREAK); }
 
     inline bool GetGlyphBoundRect(const LogicalFontInstance*, tools::Rectangle&) const;
     inline bool GetGlyphOutline(const LogicalFontInstance*, basegfx::B2DPolyPolygon&) const;
@@ -91,13 +95,26 @@ public:
     int origWidth() const { return m_nOrigWidth; }
     int charPos() const { return m_nCharPos; }
     int xOffset() const { return m_nXOffset; }
+    int yOffset() const { return m_nYOffset; }
     sal_Int32 newWidth() const { return m_nNewWidth; }
     const DevicePoint& linearPos() const { return m_aLinearPos; }
 
     void setNewWidth(sal_Int32 width) { m_nNewWidth = width; }
     void addNewWidth(sal_Int32 width) { m_nNewWidth += width; }
+    void setLinearPos(const DevicePoint& point) { m_aLinearPos = point; }
     void setLinearPosX(double x) { m_aLinearPos.setX(x); }
     void adjustLinearPosX(double diff) { m_aLinearPos.adjustX(diff); }
+#ifdef DBG_UTIL
+    bool operator==(const GlyphItem& other) const
+    {
+        return m_aLinearPos == other.m_aLinearPos && m_nOrigWidth == other.m_nOrigWidth
+               && m_nCharPos == other.m_nCharPos && m_nXOffset == other.m_nXOffset
+               && m_nYOffset == other.m_nYOffset && m_nNewWidth == other.m_nNewWidth
+               && m_aGlyphId == other.m_aGlyphId && m_nCharCount == other.m_nCharCount
+               && m_nFlags == other.m_nFlags;
+    }
+    bool operator!=(const GlyphItem& other) const { return !(*this == other); }
+#endif
 };
 
 bool GlyphItem::GetGlyphBoundRect(const LogicalFontInstance* pFontInstance,
@@ -126,10 +143,14 @@ public:
     {
     }
     SalLayoutGlyphsImpl* clone() const;
+    SalLayoutGlyphsImpl* cloneCharRange(sal_Int32 index, sal_Int32 length) const;
     const rtl::Reference<LogicalFontInstance>& GetFont() const { return m_rFontInstance; }
     bool IsValid() const;
     void SetFlags(SalLayoutFlags flags) { mnFlags = flags; }
     SalLayoutFlags GetFlags() const { return mnFlags; }
+#ifdef DBG_UTIL
+    bool isEqual(const SalLayoutGlyphsImpl* other) const;
+#endif
 
 private:
     rtl::Reference<LogicalFontInstance> m_rFontInstance;
diff --git a/vcl/source/gdi/CommonSalLayout.cxx b/vcl/source/gdi/CommonSalLayout.cxx
index 96db59fa048f..628938c5b123 100644
--- a/vcl/source/gdi/CommonSalLayout.cxx
+++ b/vcl/source/gdi/CommonSalLayout.cxx
@@ -585,6 +585,14 @@ bool GenericSalLayout::LayoutText(vcl::text::ImplLayoutArgs& rArgs, const SalLay
                     rArgs.mnFlags |= SalLayoutFlags::KashidaJustification;
                 }
 
+#if HB_VERSION_ATLEAST(1, 5, 0)
+                if (hb_glyph_info_get_glyph_flags(&pHbGlyphInfos[i]) & HB_GLYPH_FLAG_UNSAFE_TO_BREAK)
+                    nGlyphFlags |= GlyphItemFlags::IS_UNSAFE_TO_BREAK;
+#else
+                // If support is not present, then always prevent breaking.
+                nGlyphFlags |= GlyphItemFlags::IS_UNSAFE_TO_BREAK;
+#endif
+
                 DeviceCoordinate nAdvance, nXOffset, nYOffset;
                 if (aSubRun.maDirection == HB_DIRECTION_TTB)
                 {
@@ -620,7 +628,7 @@ bool GenericSalLayout::LayoutText(vcl::text::ImplLayoutArgs& rArgs, const SalLay
 
                 DevicePoint aNewPos(aCurrPos.getX() + nXOffset, aCurrPos.getY() + nYOffset);
                 const GlyphItem aGI(nCharPos, nCharCount, nGlyphIndex, aNewPos, nGlyphFlags,
-                                    nAdvance, nXOffset);
+                                    nAdvance, nXOffset, nYOffset);
                 m_GlyphItems.push_back(aGI);
 
                 aCurrPos.adjustX(nAdvance);
@@ -818,7 +826,7 @@ void GenericSalLayout::ApplyDXArray(const DC* pDXArray, SalLayoutFlags nLayoutFl
         GlyphItemFlags const nFlags = GlyphItemFlags::IS_IN_CLUSTER | GlyphItemFlags::IS_RTL_GLYPH;
         while (nCopies--)
         {
-            GlyphItem aKashida(nCharPos, 0, nKashidaIndex, aPos, nFlags, nKashidaWidth, 0);
+            GlyphItem aKashida(nCharPos, 0, nKashidaIndex, aPos, nFlags, nKashidaWidth, 0, 0);
             pGlyphIter = m_GlyphItems.insert(pGlyphIter, aKashida);
             aPos.adjustX(nKashidaWidth - nOverlap);
             ++pGlyphIter;
diff --git a/vcl/source/gdi/impglyphitem.cxx b/vcl/source/gdi/impglyphitem.cxx
index bd1138c8d68a..ab615ae270b0 100644
--- a/vcl/source/gdi/impglyphitem.cxx
+++ b/vcl/source/gdi/impglyphitem.cxx
@@ -89,6 +89,68 @@ void SalLayoutGlyphs::AppendImpl(SalLayoutGlyphsImpl* pImpl)
 
 SalLayoutGlyphsImpl* SalLayoutGlyphsImpl::clone() const { return new SalLayoutGlyphsImpl(*this); }
 
+// Clone, but only glyphs in the given range in the original text string.
+// It is possible the given range may not be cloned, in which case this returns nullptr.
+SalLayoutGlyphsImpl* SalLayoutGlyphsImpl::cloneCharRange(sal_Int32 index, sal_Int32 length) const
+{
+    std::unique_ptr<SalLayoutGlyphsImpl> copy(new SalLayoutGlyphsImpl(*GetFont()));
+    copy->SetFlags(GetFlags());
+    copy->reserve(std::min<size_t>(size(), length));
+    // Skip glyphs that are in the string before the given index (glyphs are sorted by charPos()).
+    const_iterator pos = std::partition_point(
+        begin(), end(), [index](const GlyphItem& it) { return it.charPos() < index; });
+    if (pos == end())
+        return nullptr;
+    // Require a start at the exact position given, otherwise bail out.
+    // TODO: This bails out also for RTL text.
+    if (pos->charPos() != index)
+        return nullptr;
+    // Don't create a subset if it's not safe to break at the beginning or end of the sequence
+    // (https://harfbuzz.github.io/harfbuzz-hb-buffer.html#hb-glyph-flags-t).
+    if (pos->IsUnsafeToBreak() || (pos->IsInCluster() && !pos->IsClusterStart()))
+        return nullptr;
+    // LinearPos needs adjusting to start at xOffset/yOffset for the first item,
+    // that's how it's computed in GenericSalLayout::LayoutText().
+    DevicePoint zeroPoint = pos->linearPos() - DevicePoint(pos->xOffset(), pos->yOffset());
+    // Add and adjust all glyphs until the given length.
+    while (pos != end() && pos->charPos() < index + length)
+    {
+        if (pos->IsRTLGlyph())
+            return nullptr; // Don't mix RTL and non-RTL runs.
+        copy->push_back(*pos);
+        copy->back().setLinearPos(copy->back().linearPos() - zeroPoint);
+        ++pos;
+    }
+    if (pos != end())
+    {
+        if (pos->charPos() != index + length)
+            return nullptr;
+        if (pos->IsUnsafeToBreak() || (pos->IsInCluster() && !pos->IsClusterStart()))
+            return nullptr;
+    }
+    return copy.release();
+}
+
+#ifdef DBG_UTIL
+bool SalLayoutGlyphsImpl::isEqual(const SalLayoutGlyphsImpl* other) const
+{
+    if (GetFont()->mxFontMetric != other->GetFont()->mxFontMetric)
+        return false;
+    if (GetFlags() != other->GetFlags())
+        return false;
+    if (empty() || other->empty())
+        return empty() == other->empty();
+    if (size() != other->size())
+        return false;
+    for (size_t pos = 0; pos < size(); ++pos)
+    {
+        if ((*this)[pos] != (*other)[pos])
+            return false;
+    }
+    return true;
+}
+#endif
+
 bool SalLayoutGlyphsImpl::IsValid() const
 {
     if (!m_rFontInstance.is())
@@ -102,15 +164,52 @@ SalLayoutGlyphsCache* SalLayoutGlyphsCache::self()
     return cache.get();
 }
 
+static SalLayoutGlyphs makeGlyphsSubset(const SalLayoutGlyphs& source, sal_Int32 index,
+                                        sal_Int32 len)
+{
+    SalLayoutGlyphs ret;
+    for (int level = 0;; ++level)
+    {
+        const SalLayoutGlyphsImpl* sourceLevel = source.Impl(level);
+        if (sourceLevel == nullptr)
+            break;
+        if (level > 0) // TODO: Fallbacks do not work reliably.
+            return SalLayoutGlyphs();
+        SalLayoutGlyphsImpl* cloned = sourceLevel->cloneCharRange(index, len);
+        // If the glyphs range cannot be cloned, bail out.
+        if (cloned == nullptr)
+            return SalLayoutGlyphs();
+        ret.AppendImpl(cloned);
+    }
+    return ret;
+}
+
+#ifdef DBG_UTIL
+static void checkGlyphsEqual(const SalLayoutGlyphs& g1, const SalLayoutGlyphs& g2)
+{
+    for (int level = 0;; ++level)
+    {
+        const SalLayoutGlyphsImpl* l1 = g1.Impl(level);
+        const SalLayoutGlyphsImpl* l2 = g2.Impl(level);
+        if (l1 == nullptr || l2 == nullptr)
+        {
+            assert(l1 == l2);
+            break;
+        }
+        assert(l1->isEqual(l2));
+    }
+}
+#endif
+
 const SalLayoutGlyphs*
 SalLayoutGlyphsCache::GetLayoutGlyphs(VclPtr<const OutputDevice> outputDevice, const OUString& text,
                                       sal_Int32 nIndex, sal_Int32 nLen, tools::Long nLogicWidth,
-                                      const vcl::text::TextLayoutCache* layoutCache) const
+                                      const vcl::text::TextLayoutCache* layoutCache)
 {
     if (nLen == 0)
         return nullptr;
     const CachedGlyphsKey key(outputDevice, text, nIndex, nLen, nLogicWidth);
-    auto it = mCachedGlyphs.find(key);
+    GlyphsCache::const_iterator it = mCachedGlyphs.find(key);
     if (it != mCachedGlyphs.end())
     {
         if (it->second.IsValid())
@@ -120,12 +219,6 @@ SalLayoutGlyphsCache::GetLayoutGlyphs(VclPtr<const OutputDevice> outputDevice, c
         // So in that case this is a cached failure.
         return nullptr;
     }
-    std::shared_ptr<const vcl::text::TextLayoutCache> tmpLayoutCache;
-    if (layoutCache == nullptr)
-    {
-        tmpLayoutCache = OutputDevice::CreateTextLayoutCache(text);
-        layoutCache = tmpLayoutCache.get();
-    }
 #if !ENABLE_FUZZERS
     const SalLayoutFlags glyphItemsOnlyLayout = SalLayoutFlags::GlyphItemsOnly;
 #else
@@ -133,6 +226,41 @@ SalLayoutGlyphsCache::GetLayoutGlyphs(VclPtr<const OutputDevice> outputDevice, c
     const SalLayoutFlags glyphItemsOnlyLayout
         = SalLayoutFlags::GlyphItemsOnly | SalLayoutFlags::BiDiStrong;
 #endif
+    if (nIndex != 0 || nLen != text.getLength())
+    {
+        // The glyphs functions are often called first for an entire string
+        // and then with an increasing starting index until the end of the string.
+        // Which means it's possible to get the glyphs faster by just copying
+        // a subset of the full glyphs and adjusting as necessary.
+        if (mLastTemporaryKey.has_value() && mLastTemporaryKey == key)
+            return &mLastTemporaryGlyphs;
+        const CachedGlyphsKey keyWhole(outputDevice, text, 0, text.getLength(), nLogicWidth);
+        GlyphsCache::const_iterator itWhole = mCachedGlyphs.find(keyWhole);
+        if (itWhole != mCachedGlyphs.end() && itWhole->second.IsValid())
+        {
+            mLastTemporaryGlyphs = makeGlyphsSubset(itWhole->second, nIndex, nLen);
+            if (mLastTemporaryGlyphs.IsValid())
+            {
+                mLastTemporaryKey = std::move(key);
+#ifdef DBG_UTIL
+                // Check if the subset result really matches what we would get normally,
+                // to make sure corner cases are handled well (see SalLayoutGlyphsImpl::cloneCharRange()).
+                std::unique_ptr<SalLayout> layout
+                    = outputDevice->ImplLayout(text, nIndex, nLen, Point(0, 0), nLogicWidth, {},
+                                               glyphItemsOnlyLayout, layoutCache);
+                assert(layout);
+                checkGlyphsEqual(mLastTemporaryGlyphs, layout->GetGlyphs());
+#endif
+                return &mLastTemporaryGlyphs;
+            }
+        }
+    }
+    std::shared_ptr<const vcl::text::TextLayoutCache> tmpLayoutCache;
+    if (layoutCache == nullptr)
+    {
+        tmpLayoutCache = OutputDevice::CreateTextLayoutCache(text);
+        layoutCache = tmpLayoutCache.get();
+    }
     std::unique_ptr<SalLayout> layout = outputDevice->ImplLayout(
         text, nIndex, nLen, Point(0, 0), nLogicWidth, {}, glyphItemsOnlyLayout, layoutCache);
     if (layout)
diff --git a/vcl/source/gdi/pdfwriter_impl.cxx b/vcl/source/gdi/pdfwriter_impl.cxx
index 8f9792acf54a..18f07651528b 100644
--- a/vcl/source/gdi/pdfwriter_impl.cxx
+++ b/vcl/source/gdi/pdfwriter_impl.cxx
@@ -3900,7 +3900,7 @@ void PDFWriterImpl::createDefaultCheckBoxAppearance( PDFWidget& rBox, const PDFW
     // make sure OpenSymbol is embedded, and includes our checkmark
     const sal_Unicode cMark=0x2713;
     const GlyphItem aItem(0, 0, pMap->GetGlyphIndex(cMark),
-                          DevicePoint(), GlyphItemFlags::NONE, 0, 0);
+                          DevicePoint(), GlyphItemFlags::NONE, 0, 0, 0);
     const std::vector<sal_Ucs> aCodeUnits={ cMark };
     sal_uInt8 nMappedGlyph;
     sal_Int32 nMappedFontObject;