tdf#161397 Fix incorrect glyphs for RTL font fallback

This change fixes an issue causing incorrect font fallback for certain
RTL grapheme clusters.

Change-Id: I6cff7f175b766d40c4faf204d1d65c8c366eb3e3
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/168410
Tested-by: Jenkins
Reviewed-by: Jonathan Clark <jonathan@libreoffice.org>

4 files changed, 275 insertions, 24 deletions

diff --git a/vcl/inc/ImplLayoutRuns.hxx b/vcl/inc/ImplLayoutRuns.hxx
index fecf1957d5f2..33f9048924fd 100644
--- a/vcl/inc/ImplLayoutRuns.hxx
+++ b/vcl/inc/ImplLayoutRuns.hxx
@@ -25,17 +25,29 @@
 // used for managing runs e.g. for BiDi, glyph and script fallback
 class VCL_DLLPUBLIC ImplLayoutRuns
 {
-private:
+public:
     struct Run
     {
         int m_nMinRunPos;
         int m_nEndRunPos;
         bool m_bRTL;
 
-        Run(int nMinRunPos, int nEndRunPos, bool bRTL);
-        bool Contains(int nCharPos) const;
+        Run(int nMinRunPos, int nEndRunPos, bool bRTL)
+            : m_nMinRunPos(nMinRunPos)
+            , m_nEndRunPos(nEndRunPos)
+            , m_bRTL(bRTL)
+        {
+        }
+
+        inline bool Contains(int nCharPos) const
+        {
+            return (m_nMinRunPos <= nCharPos) && (nCharPos < m_nEndRunPos);
+        }
+
+        bool operator==(const Run&) const = default;
     };
 
+private:
     int mnRunIndex;
     boost::container::small_vector<Run, 8> maRuns;
 
@@ -46,6 +58,9 @@ public:
     void AddPos(int nCharPos, bool bRTL);
     void AddRun(int nMinRunPos, int nEndRunPos, bool bRTL);
 
+    void Normalize();
+    void ReverseTail(size_t nTailIndex);
+
     bool IsEmpty() const { return maRuns.empty(); }
     void ResetPos() { mnRunIndex = 0; }
     void NextRun() { ++mnRunIndex; }
@@ -56,6 +71,10 @@ public:
 
     inline auto begin() const { return maRuns.begin(); }
     inline auto end() const { return maRuns.end(); }
+    inline const auto& at(size_t nIndex) const { return maRuns.at(nIndex); }
+    inline auto size() const { return maRuns.size(); }
+
+    static void PrepareFallbackRuns(ImplLayoutRuns* paRuns, ImplLayoutRuns* paFallbackRuns);
 };
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/vcl/qa/cppunit/text.cxx b/vcl/qa/cppunit/text.cxx
index 4ff62b0b8137..b8847f5c6247 100644
--- a/vcl/qa/cppunit/text.cxx
+++ b/vcl/qa/cppunit/text.cxx
@@ -53,6 +53,11 @@ public:
     }
 };
 
+static std::ostream& operator<<(std::ostream& s, const ImplLayoutRuns::Run& rRun)
+{
+    return s << "{" << rRun.m_nMinRunPos << ", " << rRun.m_nEndRunPos << ", " << rRun.m_bRTL << "}";
+}
+
 // Avoid issues when colorized antialiasing generates slightly tinted rather than truly black
 // pixels:
 static bool isBlack(Color col)
@@ -520,6 +525,174 @@ CPPUNIT_TEST_FIXTURE(VclTextTest, testImplLayoutRuns_PosIsInAnyRun)
     CPPUNIT_ASSERT(!aRuns.PosIsInAnyRun(7));
 }
 
+CPPUNIT_TEST_FIXTURE(VclTextTest, testImplLayoutRuns_Normalize)
+{
+    ImplLayoutRuns aRuns;
+    aRuns.AddRun(8, 10, true);
+    aRuns.AddRun(5, 8, false);
+    aRuns.AddRun(2, 5, false);
+    aRuns.AddRun(1, 3, false);
+    aRuns.AddRun(14, 15, false);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(5), aRuns.size());
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(8, 10, true), aRuns.at(0));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(5, 8, false), aRuns.at(1));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(2, 5, false), aRuns.at(2));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(1, 3, false), aRuns.at(3));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(14, 15, false), aRuns.at(4));
+
+    aRuns.Normalize();
+
+    CPPUNIT_ASSERT_EQUAL(size_t(2), aRuns.size());
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(1, 10, false), aRuns.at(0));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(14, 15, false), aRuns.at(1));
+}
+
+CPPUNIT_TEST_FIXTURE(VclTextTest, testImplLayoutRuns_PrepareFallbackRuns_LTR)
+{
+    ImplLayoutRuns aRuns;
+    aRuns.AddRun(0, 10, false); // First 5 characters excluded
+    aRuns.AddRun(11, 15, false); // Entire run included
+    aRuns.AddRun(16, 25, false); // First 4 characters included
+    aRuns.AddRun(26, 30, false); // Entire run excluded
+    aRuns.AddRun(31, 35, false); // Exact match
+
+    CPPUNIT_ASSERT_EQUAL(size_t(5), aRuns.size());
+
+    ImplLayoutRuns aFallbackRuns;
+    aFallbackRuns.AddRun(5, 20, false);
+    aFallbackRuns.AddRun(31, 35, false);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(2), aFallbackRuns.size());
+
+    ImplLayoutRuns::PrepareFallbackRuns(&aRuns, &aFallbackRuns);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(0), aFallbackRuns.size());
+
+    CPPUNIT_ASSERT_EQUAL(size_t(4), aRuns.size());
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(5, 10, false), aRuns.at(0));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(11, 15, false), aRuns.at(1));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(16, 20, false), aRuns.at(2));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(31, 35, false), aRuns.at(3));
+}
+
+CPPUNIT_TEST_FIXTURE(VclTextTest, testImplLayoutRuns_PrepareFallbackRuns_LTR_PreservesOrder)
+{
+    ImplLayoutRuns aRuns;
+    aRuns.AddRun(16, 25, false); // First 4 characters included
+    aRuns.AddRun(31, 35, false); // Exact match
+    aRuns.AddRun(0, 10, false); // First 5 characters excluded
+    aRuns.AddRun(26, 30, false); // Entire run excluded
+    aRuns.AddRun(11, 15, false); // Entire run included
+
+    CPPUNIT_ASSERT_EQUAL(size_t(5), aRuns.size());
+
+    ImplLayoutRuns aFallbackRuns;
+    aFallbackRuns.AddRun(5, 20, false);
+    aFallbackRuns.AddRun(31, 35, false);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(2), aFallbackRuns.size());
+
+    ImplLayoutRuns::PrepareFallbackRuns(&aRuns, &aFallbackRuns);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(0), aFallbackRuns.size());
+
+    CPPUNIT_ASSERT_EQUAL(size_t(4), aRuns.size());
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(16, 20, false), aRuns.at(0));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(31, 35, false), aRuns.at(1));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(5, 10, false), aRuns.at(2));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(11, 15, false), aRuns.at(3));
+}
+
+CPPUNIT_TEST_FIXTURE(VclTextTest, testImplLayoutRuns_PrepareFallbackRuns_RTL)
+{
+    ImplLayoutRuns aRuns;
+    aRuns.AddRun(0, 10, false);
+    aRuns.AddRun(10, 90, true);
+    aRuns.AddRun(90, 100, false);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(3), aRuns.size());
+
+    ImplLayoutRuns aFallbackRuns;
+    aFallbackRuns.AddRun(0, 5, false);
+    aFallbackRuns.AddRun(6, 10, false);
+    aFallbackRuns.AddRun(10, 20, true);
+    aFallbackRuns.AddRun(21, 30, true);
+    aFallbackRuns.AddRun(31, 40, true);
+    aFallbackRuns.AddRun(41, 50, true);
+    aFallbackRuns.AddRun(92, 95, false);
+    aFallbackRuns.AddRun(96, 98, false);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(8), aFallbackRuns.size());
+
+    ImplLayoutRuns::PrepareFallbackRuns(&aRuns, &aFallbackRuns);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(0), aFallbackRuns.size());
+
+    CPPUNIT_ASSERT_EQUAL(size_t(8), aRuns.size());
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(0, 5, false), aRuns.at(0));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(6, 10, false), aRuns.at(1));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(41, 50, true), aRuns.at(2));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(31, 40, true), aRuns.at(3));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(21, 30, true), aRuns.at(4));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(10, 20, true), aRuns.at(5));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(92, 95, false), aRuns.at(6));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(96, 98, false), aRuns.at(7));
+}
+
+CPPUNIT_TEST_FIXTURE(VclTextTest, testImplLayoutRuns_tdf161397)
+{
+    // Fallback run characteristic test from a particular case
+
+    ImplLayoutRuns aRuns;
+    aRuns.AddRun(0, 13, true);
+
+    ImplLayoutRuns aFallbackRuns;
+    aFallbackRuns.AddRun(12, 13, true);
+    aFallbackRuns.AddRun(7, 12, true);
+    aFallbackRuns.AddRun(5, 6, true);
+    aFallbackRuns.AddRun(0, 5, true);
+
+    ImplLayoutRuns::PrepareFallbackRuns(&aRuns, &aFallbackRuns);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(2), aRuns.size());
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(7, 13, true), aRuns.at(0));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(0, 6, true), aRuns.at(1));
+}
+
+CPPUNIT_TEST_FIXTURE(VclTextTest, testImplLayoutRuns_GrowBidirectional)
+{
+    ImplLayoutRuns aRuns;
+    aRuns.AddPos(16, true);
+    aRuns.AddPos(17, true);
+    aRuns.AddPos(18, true);
+    aRuns.AddPos(15, true);
+    aRuns.AddPos(19, true);
+    aRuns.AddPos(14, true);
+
+    CPPUNIT_ASSERT_EQUAL(size_t(1), aRuns.size());
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(14, 20, true), aRuns.at(0));
+}
+
+CPPUNIT_TEST_FIXTURE(VclTextTest, testImplLayoutRuns_ReverseTail)
+{
+    ImplLayoutRuns aRuns;
+    aRuns.AddRun(10, 20, true);
+    aRuns.AddRun(30, 40, false);
+    aRuns.AddRun(50, 60, true);
+    aRuns.AddRun(70, 80, true);
+    aRuns.AddRun(90, 100, false);
+
+    aRuns.ReverseTail(size_t(2));
+
+    CPPUNIT_ASSERT_EQUAL(size_t(5), aRuns.size());
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(10, 20, true), aRuns.at(0));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(30, 40, false), aRuns.at(1));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(90, 100, false), aRuns.at(2));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(70, 80, true), aRuns.at(3));
+    CPPUNIT_ASSERT_EQUAL(ImplLayoutRuns::Run(50, 60, true), aRuns.at(4));
+}
+
 CPPUNIT_TEST_FIXTURE(VclTextTest, testImplLayoutArgsBiDiStrong)
 {
     OUString sTestString = u"The quick brown fox\n jumped over the lazy dog"
diff --git a/vcl/source/text/ImplLayoutArgs.cxx b/vcl/source/text/ImplLayoutArgs.cxx
index 0b6199ac0e40..73e470ecfe0c 100644
--- a/vcl/source/text/ImplLayoutArgs.cxx
+++ b/vcl/source/text/ImplLayoutArgs.cxx
@@ -189,11 +189,7 @@ bool ImplLayoutArgs::PrepareFallback(const SalLayoutGlyphsImpl* pGlyphsImpl)
         return false;
     }
 
-    // the fallback runs already have the same order and limits of the original runs
-    std::swap(maRuns, maFallbackRuns);
-    maFallbackRuns.Clear();
-    maFallbackRuns.ResetPos();
-    maRuns.ResetPos();
+    ImplLayoutRuns::PrepareFallbackRuns(&maRuns, &maFallbackRuns);
 
     return true;
 }
diff --git a/vcl/source/text/ImplLayoutRuns.cxx b/vcl/source/text/ImplLayoutRuns.cxx
index ab1597b56449..f7bbd161650a 100644
--- a/vcl/source/text/ImplLayoutRuns.cxx
+++ b/vcl/source/text/ImplLayoutRuns.cxx
@@ -19,18 +19,7 @@
 
 #include <ImplLayoutRuns.hxx>
 #include <algorithm>
-
-ImplLayoutRuns::Run::Run(int nMinRunPos, int nEndRunPos, bool bRTL)
-    : m_nMinRunPos(nMinRunPos)
-    , m_nEndRunPos(nEndRunPos)
-    , m_bRTL(bRTL)
-{
-}
-
-bool ImplLayoutRuns::Run::Contains(int nCharPos) const
-{
-    return (m_nMinRunPos <= nCharPos) && (nCharPos < m_nEndRunPos);
-}
+#include <tuple>
 
 void ImplLayoutRuns::AddPos( int nCharPos, bool bRTL )
 {
@@ -38,12 +27,21 @@ void ImplLayoutRuns::AddPos( int nCharPos, bool bRTL )
     if (!maRuns.empty())
     {
         auto& rLastRun = maRuns.back();
-        if (bRTL == rLastRun.m_bRTL && nCharPos == rLastRun.m_nEndRunPos)
+        if (bRTL == rLastRun.m_bRTL)
         {
-            // extend current run by new charpos
-            ++rLastRun.m_nEndRunPos;
-            return;
+            if (nCharPos + 1 == rLastRun.m_nMinRunPos)
+            {
+                // extend current run by new charpos
+                rLastRun.m_nMinRunPos = nCharPos;
+            }
+
+            if (nCharPos == rLastRun.m_nEndRunPos)
+            {
+                // extend current run by new charpos
+                ++rLastRun.m_nEndRunPos;
+            }
         }
+
         // ignore new charpos when it is in current run
         if ((rLastRun.m_nMinRunPos <= nCharPos) && (nCharPos < rLastRun.m_nEndRunPos))
         {
@@ -79,6 +77,29 @@ void ImplLayoutRuns::AddRun( int nCharPos0, int nCharPos1, bool bRTL )
     maRuns.emplace_back(nOrderedCharPos0, nOrderedCharPos1, bRTL);
 }
 
+void ImplLayoutRuns::Normalize()
+{
+    boost::container::small_vector<Run, 8> aOldRuns;
+    std::swap(aOldRuns, maRuns);
+
+    std::sort(aOldRuns.begin(), aOldRuns.end(),
+              [](const Run& rA, const Run& rB)
+              {
+                  return std::tie(rA.m_nMinRunPos, rA.m_nEndRunPos)
+                         < std::tie(rB.m_nMinRunPos, rB.m_nEndRunPos);
+              });
+
+    for (const auto& rRun : aOldRuns)
+    {
+        AddRun(rRun.m_nMinRunPos, rRun.m_nEndRunPos, false);
+    }
+}
+
+void ImplLayoutRuns::ReverseTail(size_t nTailIndex)
+{
+    std::reverse(maRuns.begin() + nTailIndex, maRuns.end());
+}
+
 bool ImplLayoutRuns::PosIsInRun( int nCharPos ) const
 {
     if( mnRunIndex >= static_cast<int>(maRuns.size()) )
@@ -145,4 +166,46 @@ bool ImplLayoutRuns::GetRun( int* nMinRunPos, int* nEndRunPos, bool* bRightToLef
     return true;
 }
 
+void ImplLayoutRuns::PrepareFallbackRuns(ImplLayoutRuns* paRuns, ImplLayoutRuns* paFallbackRuns)
+{
+    // Normalize the input fallback runs. This is required for efficient lookup.
+    paFallbackRuns->Normalize();
+
+    // Adjust fallback runs to have the same order and limits of the original runs.
+    ImplLayoutRuns aNewRuns;
+    for (const auto& rRun : *paRuns)
+    {
+        auto nTailIndex = aNewRuns.size();
+
+        // Search for the first fallback run intersecting this run
+        auto it = std::lower_bound(paFallbackRuns->begin(), paFallbackRuns->end(),
+                                   rRun.m_nMinRunPos, [](const auto& rCompRun, int nValue)
+                                   { return rCompRun.m_nEndRunPos < nValue; });
+        for (; it != paFallbackRuns->end(); ++it)
+        {
+            if (rRun.m_nEndRunPos <= it->m_nMinRunPos)
+            {
+                break;
+            }
+
+            int nSubMin = std::max(rRun.m_nMinRunPos, it->m_nMinRunPos);
+            int nSubMax = std::min(rRun.m_nEndRunPos, it->m_nEndRunPos);
+
+            aNewRuns.AddRun(nSubMin, nSubMax, rRun.m_bRTL);
+        }
+
+        // RTL subruns must be added in reverse order
+        if (rRun.m_bRTL)
+        {
+            aNewRuns.ReverseTail(nTailIndex);
+        }
+    }
+
+    *paRuns = aNewRuns;
+    paRuns->ResetPos();
+
+    paFallbackRuns->Clear();
+    paFallbackRuns->ResetPos();
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */