Deduplicate conditional formats loaded from .ods

If there are several separate conditional format elements that can be
represented as just one (with several ranges), try to do that.

A particular customer document used to take 3 minutes 20 seconds to
load, and it contained so many (tens of thousands) conditional formats
that the Format> Conditional Formatting> Manage... dialog was
practically impossible to use.

Now loading that document takes 15 seconds and there are just a
handful of separate conditional formats.

Also add a simple unit test to verify the deduplication.

Change-Id: I7c468af99956d4646ee5507390f1476caff52325
Reviewed-on: https://gerrit.libreoffice.org/45460
Tested-by: Jenkins <ci@libreoffice.org>
Reviewed-by: Tor Lillqvist <tml@collabora.com>

8 files changed, 542 insertions, 6 deletions

diff --git a/sc/CppunitTest_sc_cond_format_merge.mk b/sc/CppunitTest_sc_cond_format_merge.mk
new file mode 100644
index 000000000000..bfb7dc2bba3f
--- /dev/null
+++ b/sc/CppunitTest_sc_cond_format_merge.mk
@@ -0,0 +1,116 @@
+# -*- Mode: makefile-gmake; tab-width: 4; indent-tabs-mode: t -*-
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+
+$(eval $(call gb_CppunitTest_CppunitTest,sc_cond_format_merge))
+
+$(eval $(call gb_CppunitTest_add_exception_objects,sc_cond_format_merge, \
+    sc/qa/unit/cond_format_merge \
+))
+
+$(eval $(call gb_CppunitTest_use_externals,sc_cond_format_merge, \
+    boost_headers \
+))
+
+$(eval $(call gb_CppunitTest_use_libraries,sc_cond_format_merge, \
+    basegfx \
+    comphelper \
+    cppu \
+    cppuhelper \
+    drawinglayer \
+    editeng \
+    for \
+    forui \
+    i18nlangtag \
+    msfilter \
+    oox \
+    sal \
+    salhelper \
+    sax \
+    sb \
+    sc \
+    scqahelper \
+    sfx \
+    sot \
+    subsequenttest \
+    svl \
+    svt \
+    svx \
+    svxcore \
+    test \
+    tk \
+    tl \
+    ucbhelper \
+    unotest \
+    utl \
+    vbahelper \
+    vcl \
+    xo \
+))
+
+$(eval $(call gb_CppunitTest_set_include,sc_cond_format_merge,\
+    -I$(SRCDIR)/sc/source/ui/inc \
+    -I$(SRCDIR)/sc/inc \
+    $$(INCLUDE) \
+))
+
+$(eval $(call gb_CppunitTest_use_sdk_api,sc_cond_format_merge))
+
+$(eval $(call gb_CppunitTest_use_ure,sc_cond_format_merge))
+$(eval $(call gb_CppunitTest_use_vcl,sc_cond_format_merge))
+
+$(eval $(call gb_CppunitTest_use_components,sc_cond_format_merge,\
+    basic/util/sb \
+    chart2/source/chartcore \
+    chart2/source/controller/chartcontroller \
+    comphelper/util/comphelp \
+    configmgr/source/configmgr \
+    dbaccess/util/dba \
+    embeddedobj/util/embobj \
+    eventattacher/source/evtatt \
+    filter/source/config/cache/filterconfig1 \
+    filter/source/storagefilterdetect/storagefd \
+    forms/util/frm \
+    framework/util/fwk \
+    i18npool/util/i18npool \
+    oox/util/oox \
+    package/source/xstor/xstor \
+    package/util/package2 \
+    sax/source/expatwrap/expwrap \
+    scaddins/source/analysis/analysis \
+    scaddins/source/datefunc/date \
+    scripting/source/basprov/basprov \
+    scripting/util/scriptframe \
+    sc/util/sc \
+    sc/util/scd \
+    sc/util/scfilt \
+    $(call gb_Helper_optional,SCRIPTING, \
+        sc/util/vbaobj) \
+    sfx2/util/sfx \
+    sot/util/sot \
+    svl/source/fsstor/fsstorage \
+    svl/util/svl \
+    svtools/util/svt \
+    svx/util/svx \
+    svx/util/svxcore \
+    toolkit/util/tk \
+    ucb/source/core/ucb1 \
+    ucb/source/ucp/file/ucpfile1 \
+    ucb/source/ucp/tdoc/ucptdoc1 \
+    unotools/util/utl \
+    unoxml/source/rdf/unordf \
+    unoxml/source/service/unoxml \
+	uui/util/uui \
+    xmloff/util/xo \
+))
+
+$(eval $(call gb_CppunitTest_use_configuration,sc_cond_format_merge))
+
+$(eval $(call gb_CppunitTest_use_unittest_configuration,sc_cond_format_merge))
+
+# vim: set noet sw=4 ts=4:
diff --git a/sc/Module_sc.mk b/sc/Module_sc.mk
index 55f2dfd19b0b..6e30bd22c1f0 100644
--- a/sc/Module_sc.mk
+++ b/sc/Module_sc.mk
@@ -57,6 +57,7 @@ endif
 endif
 
 $(eval $(call gb_Module_add_slowcheck_targets,sc, \
+	CppunitTest_sc_cond_format_merge \
 	CppunitTest_sc_new_cond_format_api \
 	CppunitTest_sc_subsequent_filters_test \
 	CppunitTest_sc_subsequent_export_test \
diff --git a/sc/inc/conditio.hxx b/sc/inc/conditio.hxx
index dede939a9185..93481f202236 100644
--- a/sc/inc/conditio.hxx
+++ b/sc/inc/conditio.hxx
@@ -352,6 +352,8 @@ public:
 
     bool            operator== ( const ScConditionEntry& r ) const;
 
+    bool            EqualIgnoringSrcPos( const ScConditionEntry& r ) const;
+
     virtual void SetParent( ScConditionalFormat* pNew ) override;
 
     bool IsCellValid( ScRefCellValue& rCell, const ScAddress& rPos ) const;
@@ -360,6 +362,7 @@ public:
     void SetOperation(ScConditionMode eMode);
     bool            IsIgnoreBlank() const       { return ( nOptions & SC_COND_NOBLANKS ) == 0; }
     void            SetIgnoreBlank(bool bSet);
+    OUString        GetSrcString() const         { return aSrcString; }
     const ScAddress& GetSrcPos() const           { return aSrcPos; }
 
     ScAddress       GetValidSrcPos() const;     // adjusted to allow textual representation of expressions
diff --git a/sc/qa/extras/testdocuments/cond_format_merge.ods b/sc/qa/extras/testdocuments/cond_format_merge.ods
new file mode 100644
index 000000000000..43b676d22080
--- /dev/null
+++ b/sc/qa/extras/testdocuments/cond_format_merge.ods
diff --git a/sc/qa/unit/cond_format_merge.cxx b/sc/qa/unit/cond_format_merge.cxx
new file mode 100644
index 000000000000..0ce3f21909bd
--- /dev/null
+++ b/sc/qa/unit/cond_format_merge.cxx
@@ -0,0 +1,155 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; fill-column: 100 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include <sal/config.h>
+
+#include <com/sun/star/beans/XPropertySet.hpp>
+#include <com/sun/star/lang/XComponent.hpp>
+#include <com/sun/star/sheet/XConditionalFormats.hpp>
+#include <com/sun/star/sheet/XSpreadsheet.hpp>
+#include <test/bootstrapfixture.hxx>
+#include <test/calc_unoapi_test.hxx>
+
+#include <global.hxx>
+#include <document.hxx>
+
+#include "helper/qahelper.hxx"
+
+using namespace css;
+
+class ScCondFormatMergeTest : public CalcUnoApiTest
+{
+public:
+    ScCondFormatMergeTest();
+
+    void testCondFormatMerge();
+
+    CPPUNIT_TEST_SUITE(ScCondFormatMergeTest);
+    CPPUNIT_TEST(testCondFormatMerge);
+    CPPUNIT_TEST_SUITE_END();
+};
+
+ScCondFormatMergeTest::ScCondFormatMergeTest()
+    : CalcUnoApiTest("sc/qa/extras/testdocuments/")
+{
+}
+
+void ScCondFormatMergeTest::testCondFormatMerge()
+{
+    OUString aFileURL;
+    createFileURL("cond_format_merge.ods", aFileURL);
+    uno::Reference<lang::XComponent> mxComponent = loadFromDesktop(aFileURL);
+
+    CPPUNIT_ASSERT_MESSAGE("Component not loaded", mxComponent.is());
+
+    // get the first sheet
+    uno::Reference<sheet::XSpreadsheetDocument> xDoc(mxComponent, uno::UNO_QUERY_THROW);
+    uno::Reference<container::XIndexAccess> xIndex(xDoc->getSheets(), uno::UNO_QUERY_THROW);
+    uno::Reference<sheet::XSpreadsheet> xSheet(xIndex->getByIndex(0), uno::UNO_QUERY_THROW);
+
+    uno::Reference<beans::XPropertySet> xProps(xSheet, uno::UNO_QUERY_THROW);
+    uno::Any aAny = xProps->getPropertyValue("ConditionalFormats");
+    uno::Reference<sheet::XConditionalFormats> xCondFormats;
+
+    CPPUNIT_ASSERT(aAny >>= xCondFormats);
+    CPPUNIT_ASSERT(xCondFormats.is());
+
+    CPPUNIT_ASSERT_EQUAL(sal_Int32(5), xCondFormats->getLength());
+
+    uno::Sequence<uno::Reference<sheet::XConditionalFormat>> xCondFormatSeq
+        = xCondFormats->getConditionalFormats();
+    CPPUNIT_ASSERT_EQUAL(sal_Int32(5), xCondFormatSeq.getLength());
+
+    int nRanges = 0;
+    for (sal_Int32 i = 0, n = xCondFormatSeq.getLength(); i < n; ++i)
+    {
+        CPPUNIT_ASSERT(xCondFormatSeq[i].is());
+
+        uno::Reference<sheet::XConditionalFormat> xCondFormat = xCondFormatSeq[i];
+        CPPUNIT_ASSERT(xCondFormat.is());
+
+        uno::Reference<beans::XPropertySet> xPropSet(xCondFormat, uno::UNO_QUERY_THROW);
+
+        aAny = xPropSet->getPropertyValue("Range");
+        uno::Reference<sheet::XSheetCellRanges> xCellRanges;
+        CPPUNIT_ASSERT(aAny >>= xCellRanges);
+        CPPUNIT_ASSERT(xCellRanges.is());
+
+        uno::Sequence<table::CellRangeAddress> aRanges = xCellRanges->getRangeAddresses();
+        CPPUNIT_ASSERT_GREATEREQUAL(sal_Int32(1), aRanges.getLength());
+
+        table::CellRangeAddress aRange0 = aRanges[0];
+        CPPUNIT_ASSERT_EQUAL(sal_Int16(0), aRange0.Sheet);
+        CPPUNIT_ASSERT_EQUAL(aRange0.StartColumn, aRange0.EndColumn);
+
+        table::CellRangeAddress aRange1;
+
+        switch (aRange0.StartColumn)
+        {
+            case 3:
+                switch (aRange0.StartRow)
+                {
+                    case 0: // D1:D2,D5::D8
+                        nRanges++;
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(1), aRange0.EndRow);
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(2), aRanges.getLength());
+                        aRange1 = aRanges[1];
+                        CPPUNIT_ASSERT_EQUAL(sal_Int16(0), aRange1.Sheet);
+                        CPPUNIT_ASSERT_EQUAL(aRange1.StartColumn, aRange1.EndColumn);
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(3), aRange1.StartColumn);
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(4), aRange1.StartRow);
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(7), aRange1.EndRow);
+                        break;
+                    default:
+                        CPPUNIT_FAIL("Unexpected range in column D");
+                }
+                break;
+            case 5:
+                switch (aRange0.StartRow)
+                {
+                    case 0: // F1:F2
+                        nRanges++;
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(1), aRange0.EndRow);
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(1), aRanges.getLength());
+                        break;
+                    case 2: // F3
+                        nRanges++;
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(2), aRange0.EndRow);
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(1), aRanges.getLength());
+                        break;
+                    case 3: // F4
+                        nRanges++;
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(3), aRange0.EndRow);
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(1), aRanges.getLength());
+                        break;
+                    case 4: // F5
+                        nRanges++;
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(4), aRange0.EndRow);
+                        CPPUNIT_ASSERT_EQUAL(sal_Int32(1), aRanges.getLength());
+                        break;
+                    default:
+                        CPPUNIT_FAIL("Unexpected range in column F");
+                }
+                break;
+            default:
+                CPPUNIT_FAIL("Unexpected range");
+        }
+    }
+
+    CPPUNIT_ASSERT_EQUAL(5, nRanges);
+
+    closeDocument(mxComponent);
+    mxComponent.clear();
+}
+
+CPPUNIT_TEST_SUITE_REGISTRATION(ScCondFormatMergeTest);
+
+CPPUNIT_PLUGIN_IMPLEMENT();
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/conditio.cxx b/sc/source/core/data/conditio.cxx
index ca6b49f20a75..5be3688bfe6a 100644
--- a/sc/source/core/data/conditio.cxx
+++ b/sc/source/core/data/conditio.cxx
@@ -650,6 +650,25 @@ bool ScConditionEntry::operator== ( const ScConditionEntry& r ) const
     return bEq;
 }
 
+bool ScConditionEntry::EqualIgnoringSrcPos( const ScConditionEntry& r ) const
+{
+    bool bEq = (eOp == r.eOp && nOptions == r.nOptions &&
+                lcl_IsEqual( pFormula1, r.pFormula1 ) &&
+                lcl_IsEqual( pFormula2, r.pFormula2 ));
+    if (bEq)
+    {
+        // Here, ignore the aSrcPoses and aSrcStrings
+
+        // If not formulas, compare values
+        if ( !pFormula1 && ( nVal1 != r.nVal1 || aStrVal1 != r.aStrVal1 || bIsStr1 != r.bIsStr1 ) )
+            bEq = false;
+        if ( !pFormula2 && ( nVal2 != r.nVal2 || aStrVal2 != r.aStrVal2 || bIsStr2 != r.bIsStr2 ) )
+            bEq = false;
+    }
+
+    return bEq;
+}
+
 void ScConditionEntry::Interpret( const ScAddress& rPos )
 {
     // Create formula cells
diff --git a/sc/source/filter/xml/xmlcondformat.cxx b/sc/source/filter/xml/xmlcondformat.cxx
index 48af2921775a..2e8a2a66d1a3 100644
--- a/sc/source/filter/xml/xmlcondformat.cxx
+++ b/sc/source/filter/xml/xmlcondformat.cxx
@@ -21,6 +21,7 @@
 #include <docfunc.hxx>
 #include "XMLConverter.hxx"
 #include <stylehelper.hxx>
+#include <tokenarray.hxx>
 
 using namespace xmloff::token;
 
@@ -41,7 +42,7 @@ css::uno::Reference< css::xml::sax::XFastContextHandler > SAL_CALL ScXMLConditio
     switch (nElement)
     {
         case XML_ELEMENT( CALC_EXT, XML_CONDITIONAL_FORMAT ):
-            pContext = new ScXMLConditionalFormatContext( GetScImport(), pAttribList );
+            pContext = new ScXMLConditionalFormatContext( GetScImport(), pAttribList, *this );
             break;
     }
 
@@ -57,11 +58,18 @@ void SAL_CALL ScXMLConditionalFormatsContext::endFastElement( sal_Int32 /*nEleme
     bool bDeleted = !pCondFormatList->CheckAllEntries();
 
     SAL_WARN_IF(bDeleted, "sc", "conditional formats have been deleted because they contained empty range info");
+
+    for (const auto& i : mvCondFormatData)
+    {
+        pDoc->AddCondFormatData( i.mpFormat->GetRange(), i.mnTab, i.mpFormat->GetKey() );
+    }
 }
 
 ScXMLConditionalFormatContext::ScXMLConditionalFormatContext( ScXMLImport& rImport,
-                        const rtl::Reference<sax_fastparser::FastAttributeList>& rAttrList ):
-    ScXMLImportContext( rImport )
+                                                              const rtl::Reference<sax_fastparser::FastAttributeList>& rAttrList,
+                                                              ScXMLConditionalFormatsContext& rParent ):
+    ScXMLImportContext( rImport ),
+    mrParent( rParent )
 {
     OUString sRange;
 
@@ -118,16 +126,227 @@ css::uno::Reference< css::xml::sax::XFastContextHandler > SAL_CALL ScXMLConditio
     return pContext;
 }
 
+static bool HasRelRefIgnoringSheet0Relative( ScDocument* pDoc, const ScTokenArray* pTokens, sal_uInt16 nRecursion = 0 )
+{
+    if (pTokens)
+    {
+        formula::FormulaTokenArrayPlainIterator aIter( *pTokens );
+        formula::FormulaToken* t;
+        for( t = aIter.Next(); t; t = aIter.Next() )
+        {
+            switch( t->GetType() )
+            {
+                case formula::svDoubleRef:
+                {
+                    ScSingleRefData& rRef2 = t->GetDoubleRef()->Ref2;
+                    if ( rRef2.IsColRel() || rRef2.IsRowRel() || (rRef2.IsFlag3D() && rRef2.IsTabRel()) )
+                        return true;
+                    SAL_FALLTHROUGH;
+                }
+
+                case formula::svSingleRef:
+                {
+                    ScSingleRefData& rRef1 = *t->GetSingleRef();
+                    if ( rRef1.IsColRel() || rRef1.IsRowRel() || (rRef1.IsFlag3D() && rRef1.IsTabRel()) )
+                        return true;
+                }
+                break;
+
+                case formula::svIndex:
+                {
+                    if( t->GetOpCode() == ocName )      // DB areas always absolute
+                        if( ScRangeData* pRangeData = pDoc->FindRangeNameBySheetAndIndex( t->GetSheet(), t->GetIndex()) )
+                            if( (nRecursion < 42) && HasRelRefIgnoringSheet0Relative( pDoc, pRangeData->GetCode(), nRecursion + 1 ) )
+                                return true;
+                }
+                break;
+
+                // #i34474# function result dependent on cell position
+                case formula::svByte:
+                {
+                    switch( t->GetOpCode() )
+                    {
+                        case ocRow:     // ROW() returns own row index
+                        case ocColumn:  // COLUMN() returns own column index
+                        case ocSheet:   // SHEET() returns own sheet index
+                        case ocCell:    // CELL() may return own cell address
+                            return true;
+                        default:
+                            break;
+                    }
+                }
+                break;
+
+                default:
+                    break;
+            }
+        }
+    }
+    return false;
+}
+
+static bool HasOneSingleFullyRelativeReference( const ScTokenArray* pTokens, ScSingleRefData& rOffset )
+{
+    int nCount = 0;
+    if (pTokens)
+    {
+        formula::FormulaTokenArrayPlainIterator aIter( *pTokens );
+        formula::FormulaToken* t;
+        for( t = aIter.Next(); t; t = aIter.Next() )
+        {
+            switch( t->GetType() )
+            {
+                case formula::svSingleRef:
+                {
+                    ScSingleRefData& rRef1 = *t->GetSingleRef();
+                    if ( rRef1.IsColRel() && rRef1.IsRowRel() && !rRef1.IsFlag3D() && rRef1.IsTabRel() )
+                    {
+                        nCount++;
+                        if (nCount == 1)
+                        {
+                            rOffset = rRef1;
+                        }
+                    }
+                }
+                break;
+
+                default:
+                    break;
+            }
+        }
+    }
+    return nCount == 1;
+}
+
 void SAL_CALL ScXMLConditionalFormatContext::endFastElement( sal_Int32 /*nElement*/ )
 {
     ScDocument* pDoc = GetScImport().GetDocument();
 
     SCTAB nTab = GetScImport().GetTables().GetCurrentSheet();
     ScConditionalFormat* pFormat = mxFormat.release();
+
+    bool bEligibleForCache = true;
+    bool bSingleRelativeReference = false;
+    ScSingleRefData aOffsetForSingleRelRef;
+    const ScTokenArray* pTokens = nullptr;
+    for (size_t nFormatEntryIx = 0; nFormatEntryIx < pFormat->size(); ++nFormatEntryIx)
+    {
+        auto pFormatEntry = pFormat->GetEntry(nFormatEntryIx);
+        auto pCondFormatEntry = static_cast<const ScCondFormatEntry*>(pFormatEntry);
+
+        if (pCondFormatEntry->GetOperation() != ScConditionMode::Equal &&
+            pCondFormatEntry->GetOperation() != ScConditionMode::Direct)
+        {
+            bEligibleForCache = false;
+            break;
+        }
+
+        ScAddress aSrcPos;
+        OUString aSrcString = pCondFormatEntry->GetSrcString();
+        if ( !aSrcString.isEmpty() )
+            aSrcPos.Parse( aSrcString, pDoc );
+        ScCompiler aComp( pDoc, aSrcPos );
+        aComp.SetGrammar( formula::FormulaGrammar::GRAM_ODFF );
+        pTokens = aComp.CompileString( pCondFormatEntry->GetExpression(aSrcPos, 0), "" );
+        if (HasRelRefIgnoringSheet0Relative( pDoc, pTokens ))
+        {
+            // In general not eligible, but some might be. We handle one very special case: When the
+            // conditional format has one entry, the reference position is the first cell of the
+            // range, and with a single fully relative reference in its expression. (Possibly these
+            // conditions could be loosened, but I am too tired to think on that right now.)
+            if (pFormat->size() == 1 &&
+                pFormat->GetRange().size() == 1 &&
+                pFormat->GetRange()[0]->aStart == aSrcPos &&
+                HasOneSingleFullyRelativeReference( pTokens, aOffsetForSingleRelRef ))
+            {
+                bSingleRelativeReference = true;
+            }
+            else
+            {
+                bEligibleForCache = false;
+                break;
+            }
+        }
+    }
+
+    if (bEligibleForCache)
+    {
+        for (auto& aCacheEntry : mrParent.maCache)
+            if (aCacheEntry.mnAge < SAL_MAX_INT64)
+                aCacheEntry.mnAge++;
+
+        for (auto& aCacheEntry : mrParent.maCache)
+        {
+            if (!aCacheEntry.mpFormat)
+                continue;
+
+            if (aCacheEntry.mpFormat->size() != pFormat->size())
+                continue;
+
+            // Check if the conditional format is identical to an existing one (but with different range) and can be shared
+            for (size_t nFormatEntryIx = 0; nFormatEntryIx < pFormat->size(); ++nFormatEntryIx)
+            {
+                auto pCacheFormatEntry = aCacheEntry.mpFormat->GetEntry(nFormatEntryIx);
+                auto pFormatEntry = pFormat->GetEntry(nFormatEntryIx);
+                if (pCacheFormatEntry->GetType() != pFormatEntry->GetType() ||
+                    pFormatEntry->GetType() != ScFormatEntry::Type::Condition)
+                    break;
+
+                auto pCacheCondFormatEntry = static_cast<const ScCondFormatEntry*>(pCacheFormatEntry);
+                auto pCondFormatEntry = static_cast<const ScCondFormatEntry*>(pFormatEntry);
+
+                if (pCacheCondFormatEntry->GetStyle() != pCondFormatEntry->GetStyle())
+                    break;
+
+                // Note That comparing the formulas of the ScConditionEntry at this stage is
+                // comparing just the *strings* of the formulas. For the bSingleRelativeReference
+                // case we compare the tokenized ("compiled") formulas.
+                if (bSingleRelativeReference)
+                {
+                    if (aCacheEntry.mbSingleRelativeReference &&
+                        pTokens->EqualTokens(aCacheEntry.mpTokens.get()))
+                        ;
+                    else
+                        break;
+                }
+                else if (!pCacheCondFormatEntry->EqualIgnoringSrcPos(*pCondFormatEntry))
+                {
+                    break;
+                }
+                // If we get here on the last round through the for loop, we have a cache hit
+                if (nFormatEntryIx == pFormat->size() - 1)
+                {
+                    // Mark cache entry as fresh, do necessary mangling of it and just return
+                    aCacheEntry.mnAge = 0;
+                    for (size_t k = 0; k < pFormat->GetRange().size(); ++k)
+                        aCacheEntry.mpFormat->GetRangeList().Join(*(pFormat->GetRange()[k]));
+                    return;
+                }
+            }
+        }
+
+        // Not found in cache, replace oldest cache entry
+        sal_Int64 nOldestAge = -1;
+        size_t nIndexOfOldest = 0;
+        for (auto& aCacheEntry : mrParent.maCache)
+        {
+            if (aCacheEntry.mnAge > nOldestAge)
+            {
+                nOldestAge = aCacheEntry.mnAge;
+                nIndexOfOldest = (&aCacheEntry - &mrParent.maCache.front());
+            }
+        }
+        mrParent.maCache[nIndexOfOldest].mpFormat = pFormat;
+        mrParent.maCache[nIndexOfOldest].mbSingleRelativeReference = bSingleRelativeReference;
+        mrParent.maCache[nIndexOfOldest].mpTokens.reset(pTokens);
+        mrParent.maCache[nIndexOfOldest].mnAge = 0;
+    }
+
     sal_uLong nIndex = pDoc->AddCondFormat(pFormat, nTab);
-    pFormat->SetKey(nIndex);
+    (void) nIndex; // Avoid 'unused variable' warning when assert() expands to empty
+    assert(pFormat->GetKey() == nIndex);
 
-    pDoc->AddCondFormatData( pFormat->GetRange(), nTab, nIndex);
+    mrParent.mvCondFormatData.push_back( { pFormat, nTab } );
 }
 
 ScXMLConditionalFormatContext::~ScXMLConditionalFormatContext()
diff --git a/sc/source/filter/xml/xmlcondformat.hxx b/sc/source/filter/xml/xmlcondformat.hxx
index 6232bfc381af..fc253081ff0d 100644
--- a/sc/source/filter/xml/xmlcondformat.hxx
+++ b/sc/source/filter/xml/xmlcondformat.hxx
@@ -10,6 +10,7 @@
 #ifndef INCLUDED_SC_SOURCE_FILTER_XML_XMLCONDFORMAT_HXX
 #define INCLUDED_SC_SOURCE_FILTER_XML_XMLCONDFORMAT_HXX
 
+#include <array>
 #include <memory>
 #include <xmloff/xmlictxt.hxx>
 #include "xmlimprt.hxx"
@@ -25,6 +26,21 @@ struct ScIconSetFormatData;
 
 class ScXMLConditionalFormatsContext : public ScXMLImportContext
 {
+private:
+    struct CacheEntry
+    {
+        ScConditionalFormat* mpFormat = nullptr;
+        bool mbSingleRelativeReference;
+        std::unique_ptr<const ScTokenArray> mpTokens;
+        sal_Int64 mnAge = SAL_MAX_INT64;
+    };
+
+    struct CondFormatData
+    {
+        ScConditionalFormat* mpFormat;
+        SCTAB mnTab;
+    };
+
 public:
     ScXMLConditionalFormatsContext( ScXMLImport& rImport );
 
@@ -32,13 +48,18 @@ public:
         sal_Int32 nElement, const css::uno::Reference< css::xml::sax::XFastAttributeList >& xAttrList ) override;
 
     virtual void SAL_CALL endFastElement( sal_Int32 nElement ) override;
+
+    std::array<CacheEntry, 4> maCache;
+
+    std::vector<CondFormatData> mvCondFormatData;
 };
 
 class ScXMLConditionalFormatContext : public ScXMLImportContext
 {
 public:
     ScXMLConditionalFormatContext( ScXMLImport& rImport,
-                        const rtl::Reference<sax_fastparser::FastAttributeList>& rAttrList );
+                                   const rtl::Reference<sax_fastparser::FastAttributeList>& rAttrList,
+                                   ScXMLConditionalFormatsContext& rParent );
 
     virtual ~ScXMLConditionalFormatContext() override;
 
@@ -50,6 +71,8 @@ private:
 
     std::unique_ptr<ScConditionalFormat> mxFormat;
     ScRangeList maRange;
+
+    ScXMLConditionalFormatsContext& mrParent;
 };
 
 class ScXMLColorScaleFormatContext : public ScXMLImportContext