optimize ScHTMLExport::WriteTables() with large columns

Again, unless given a hint, mdds always starts a search from the beginning
of the container, so iterating over a column becomes quadratic.
Shows when selecting (the title of) a large column with different value types,
e.g. in tdf#120558, which triggers setting the selection from
VclQt5Clipboard::setContents(), which calls this.

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

12 files changed, 88 insertions, 19 deletions

diff --git a/sc/inc/cellvalue.hxx b/sc/inc/cellvalue.hxx
index 7b6e3aad5794..281612d8874e 100644
--- a/sc/inc/cellvalue.hxx
+++ b/sc/inc/cellvalue.hxx
@@ -18,6 +18,10 @@ class EditTextObject;
 class ScColumn;
 struct ScRefCellValue;
 
+namespace sc {
+struct ColumnBlockPosition;
+}
+
 namespace svl {
 
 class SharedString;
@@ -117,6 +121,7 @@ struct SC_DLLPUBLIC ScRefCellValue
      * Take cell value from specified position in specified document.
      */
     ScRefCellValue( ScDocument& rDoc, const ScAddress& rPos );
+    ScRefCellValue( ScDocument& rDoc, const ScAddress& rPos, sc::ColumnBlockPosition& rBlockPos );
 
     void clear();
 
@@ -124,6 +129,7 @@ struct SC_DLLPUBLIC ScRefCellValue
      * Take cell value from specified position in specified document.
      */
     void assign( ScDocument& rDoc, const ScAddress& rPos );
+    void assign( ScDocument& rDoc, const ScAddress& rPos, sc::ColumnBlockPosition& rBlockPos );
 
     /**
      * Set cell value at specified position in specified document.
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 9a4d22a3e664..340b5628faf6 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -189,6 +189,7 @@ public:
     const sc::CellNoteStoreType& GetCellNoteStore() const { return maCellNotes; }
 
     ScRefCellValue GetCellValue( SCROW nRow ) const;
+    ScRefCellValue GetCellValue( sc::ColumnBlockPosition& rBlockPos, SCROW nRow );
     ScRefCellValue GetCellValue( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const;
     static ScRefCellValue GetCellValue( const sc::CellStoreType::const_iterator& itPos, size_t nOffset );
 
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index dd59a74c44e4..af372c270675 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -1550,7 +1550,7 @@ public:
     void CopyTabToClip( SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
                         SCTAB nTab, ScDocument* pClipDoc);
 
-    bool InitColumnBlockPosition( sc::ColumnBlockPosition& rBlockPos, SCTAB nTab, SCCOL nCol );
+    SC_DLLPUBLIC bool InitColumnBlockPosition( sc::ColumnBlockPosition& rBlockPos, SCTAB nTab, SCCOL nCol );
 
     void DeleteBeforeCopyFromClip( sc::CopyFromClipContext& rCxt, const ScMarkData& rMark,
                                    sc::ColumnSpanSet& rBroadcastSpans );
@@ -1692,7 +1692,9 @@ public:
     void                                    RemoveCondFormatData( const ScRangeList& rRange, SCTAB nTab, sal_uInt32 nIndex );
 
     SC_DLLPUBLIC ScConditionalFormat*       GetCondFormat( SCCOL nCol, SCROW nRow, SCTAB nTab ) const;
-    SC_DLLPUBLIC const SfxItemSet*          GetCondResult( SCCOL nCol, SCROW nRow, SCTAB nTab ) const;
+    // pCell is an optimization, must point to rPos
+    SC_DLLPUBLIC const SfxItemSet*          GetCondResult( SCCOL nCol, SCROW nRow, SCTAB nTab,
+                                                           ScRefCellValue* pCell = nullptr ) const;
     const SfxItemSet*                       GetCondResult( ScRefCellValue& rCell, const ScAddress& rPos,
                                                            const ScConditionalFormatList& rList,
                                                            const ScCondFormatIndexes& rIndex ) const;
@@ -1705,8 +1707,12 @@ public:
     SC_DLLPUBLIC const css::uno::Reference< css::i18n::XBreakIterator >& GetBreakIterator();
     bool                        HasStringWeakCharacters( const OUString& rString );
     SC_DLLPUBLIC SvtScriptType  GetStringScriptType( const OUString& rString );
-    SC_DLLPUBLIC SvtScriptType  GetCellScriptType( const ScAddress& rPos, sal_uInt32 nNumberFormat );
-    SC_DLLPUBLIC SvtScriptType  GetScriptType( SCCOL nCol, SCROW nRow, SCTAB nTab );
+    // pCell is an optimization, must point to rPos
+    SC_DLLPUBLIC SvtScriptType  GetCellScriptType( const ScAddress& rPos, sal_uInt32 nNumberFormat,
+                                                   ScRefCellValue* pCell = nullptr );
+    // pCell is an optimization, must point to nCol,nRow,nTab
+    SC_DLLPUBLIC SvtScriptType  GetScriptType( SCCOL nCol, SCROW nRow, SCTAB nTab,
+                                               ScRefCellValue* pCell = nullptr );
     SvtScriptType               GetRangeScriptType( sc::ColumnBlockPosition& rBlockPos, const ScAddress& rPos, SCROW nLength );
     SvtScriptType               GetRangeScriptType( const ScRangeList& rRanges );
 
@@ -2527,6 +2533,7 @@ private:
     bool    HasPartOfMerged( const ScRange& rRange );
 
     ScRefCellValue GetRefCellValue( const ScAddress& rPos );
+    ScRefCellValue GetRefCellValue( const ScAddress& rPos, sc::ColumnBlockPosition& rBlockPos );
 
     std::map< SCTAB, ScSortParam > mSheetSortParams;
 
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 59dc2bbfd7dc..29a7b28fe635 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -998,6 +998,7 @@ public:
     void RegroupFormulaCells( SCCOL nCol );
 
     ScRefCellValue GetRefCellValue( SCCOL nCol, SCROW nRow );
+    ScRefCellValue GetRefCellValue( SCCOL nCol, SCROW nRow, sc::ColumnBlockPosition& rBlockPos );
 
     SvtBroadcaster* GetBroadcaster( SCCOL nCol, SCROW nRow );
     const SvtBroadcaster* GetBroadcaster( SCCOL nCol, SCROW nRow ) const;
diff --git a/sc/source/core/data/cellvalue.cxx b/sc/source/core/data/cellvalue.cxx
index 7fffc669ee6c..ef662c4818f7 100644
--- a/sc/source/core/data/cellvalue.cxx
+++ b/sc/source/core/data/cellvalue.cxx
@@ -567,6 +567,11 @@ ScRefCellValue::ScRefCellValue( ScDocument& rDoc, const ScAddress& rPos )
     assign( rDoc, rPos);
 }
 
+ScRefCellValue::ScRefCellValue( ScDocument& rDoc, const ScAddress& rPos, sc::ColumnBlockPosition& rBlockPos )
+{
+    assign( rDoc, rPos, rBlockPos );
+}
+
 void ScRefCellValue::clear()
 {
     // Reset to empty value.
@@ -579,6 +584,11 @@ void ScRefCellValue::assign( ScDocument& rDoc, const ScAddress& rPos )
     *this = rDoc.GetRefCellValue(rPos);
 }
 
+void ScRefCellValue::assign( ScDocument& rDoc, const ScAddress& rPos, sc::ColumnBlockPosition& rBlockPos )
+{
+    *this = rDoc.GetRefCellValue(rPos, rBlockPos);
+}
+
 void ScRefCellValue::commit( ScDocument& rDoc, const ScAddress& rPos ) const
 {
     switch (meType)
diff --git a/sc/source/core/data/column.cxx b/sc/source/core/data/column.cxx
index 70ee70b8e1f4..548e6403cc8b 100644
--- a/sc/source/core/data/column.cxx
+++ b/sc/source/core/data/column.cxx
@@ -726,6 +726,16 @@ ScRefCellValue ScColumn::GetCellValue( SCROW nRow ) const
     return GetCellValue(aPos.first, aPos.second);
 }
 
+ScRefCellValue ScColumn::GetCellValue( sc::ColumnBlockPosition& rBlockPos, SCROW nRow )
+{
+    std::pair<sc::CellStoreType::iterator,size_t> aPos = maCells.position(rBlockPos.miCellPos, nRow);
+    if (aPos.first == maCells.end())
+        return ScRefCellValue();
+
+    rBlockPos.miCellPos = aPos.first; // Store this for next call.
+    return GetCellValue(aPos.first, aPos.second);
+}
+
 ScRefCellValue ScColumn::GetCellValue( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const
 {
     std::pair<sc::CellStoreType::const_iterator,size_t> aPos = maCells.position(rBlockPos.miCellPos, nRow);
diff --git a/sc/source/core/data/documen2.cxx b/sc/source/core/data/documen2.cxx
index 2ffbd7806549..56506490ec5d 100644
--- a/sc/source/core/data/documen2.cxx
+++ b/sc/source/core/data/documen2.cxx
@@ -529,6 +529,14 @@ ScRefCellValue ScDocument::GetRefCellValue( const ScAddress& rPos )
     return maTabs[rPos.Tab()]->GetRefCellValue(rPos.Col(), rPos.Row());
 }
 
+ScRefCellValue ScDocument::GetRefCellValue( const ScAddress& rPos, sc::ColumnBlockPosition& rBlockPos )
+{
+    if (!TableExists(rPos.Tab()))
+        return ScRefCellValue(); // empty
+
+    return maTabs[rPos.Tab()]->GetRefCellValue(rPos.Col(), rPos.Row(), rBlockPos);
+}
+
 svl::SharedStringPool& ScDocument::GetSharedStringPool()
 {
     return *mpCellStringPool;
diff --git a/sc/source/core/data/documen4.cxx b/sc/source/core/data/documen4.cxx
index a1f5a6861db2..1d36d52e3bfb 100644
--- a/sc/source/core/data/documen4.cxx
+++ b/sc/source/core/data/documen4.cxx
@@ -782,19 +782,24 @@ const SfxPoolItem* ScDocument::GetEffItem(
     return nullptr;
 }
 
-const SfxItemSet* ScDocument::GetCondResult( SCCOL nCol, SCROW nRow, SCTAB nTab ) const
+const SfxItemSet* ScDocument::GetCondResult( SCCOL nCol, SCROW nRow, SCTAB nTab, ScRefCellValue* pCell ) const
 {
     ScConditionalFormatList* pFormatList = GetCondFormList(nTab);
     if (!pFormatList)
         return nullptr;
 
     ScAddress aPos(nCol, nRow, nTab);
-    ScRefCellValue aCell(const_cast<ScDocument&>(*this), aPos);
+    ScRefCellValue aCell;
+    if( pCell == nullptr )
+    {
+        aCell.assign(const_cast<ScDocument&>(*this), aPos);
+        pCell = &aCell;
+    }
     const ScPatternAttr* pPattern = GetPattern( nCol, nRow, nTab );
     const ScCondFormatIndexes& rIndex =
         pPattern->GetItem(ATTR_CONDITIONAL).GetCondFormatData();
 
-    return GetCondResult(aCell, aPos, *pFormatList, rIndex);
+    return GetCondResult(*pCell, aPos, *pFormatList, rIndex);
 }
 
 const SfxItemSet* ScDocument::GetCondResult(
diff --git a/sc/source/core/data/documen6.cxx b/sc/source/core/data/documen6.cxx
index 4076cef8a2f4..9dd1f8b523a3 100644
--- a/sc/source/core/data/documen6.cxx
+++ b/sc/source/core/data/documen6.cxx
@@ -108,14 +108,19 @@ SvtScriptType ScDocument::GetStringScriptType( const OUString& rString )
     return nRet;
 }
 
-SvtScriptType ScDocument::GetCellScriptType( const ScAddress& rPos, sal_uInt32 nNumberFormat )
+SvtScriptType ScDocument::GetCellScriptType( const ScAddress& rPos, sal_uInt32 nNumberFormat,
+                                             ScRefCellValue* pCell )
 {
     SvtScriptType nStored = GetScriptType(rPos);
     if ( nStored != SvtScriptType::UNKNOWN )         // stored value valid?
         return nStored;                             // use stored value
 
     Color* pColor;
-    OUString aStr = ScCellFormat::GetString(*this, rPos, nNumberFormat, &pColor, *mxPoolHelper->GetFormTable());
+    OUString aStr;
+    if( pCell )
+        ScCellFormat::GetString(*pCell, nNumberFormat, aStr, &pColor, *mxPoolHelper->GetFormTable(), this);
+    else
+        ScCellFormat::GetString(*this, rPos, nNumberFormat, &pColor, *mxPoolHelper->GetFormTable());
 
     SvtScriptType nRet = GetStringScriptType( aStr );
 
@@ -124,7 +129,7 @@ SvtScriptType ScDocument::GetCellScriptType( const ScAddress& rPos, sal_uInt32 n
     return nRet;
 }
 
-SvtScriptType ScDocument::GetScriptType( SCCOL nCol, SCROW nRow, SCTAB nTab )
+SvtScriptType ScDocument::GetScriptType( SCCOL nCol, SCROW nRow, SCTAB nTab, ScRefCellValue* pCell )
 {
     // if script type is set, don't have to get number formats
 
@@ -143,7 +148,7 @@ SvtScriptType ScDocument::GetScriptType( SCCOL nCol, SCROW nRow, SCTAB nTab )
 
     sal_uInt32 nFormat = pPattern->GetNumberFormat( mxPoolHelper->GetFormTable(), pCondSet );
 
-    return GetCellScriptType(aPos, nFormat);
+    return GetCellScriptType(aPos, nFormat, pCell);
 }
 
 namespace {
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index c18c039c46db..be7d12b50150 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -2421,6 +2421,14 @@ ScRefCellValue ScTable::GetRefCellValue( SCCOL nCol, SCROW nRow )
     return aCol[nCol].GetCellValue(nRow);
 }
 
+ScRefCellValue ScTable::GetRefCellValue( SCCOL nCol, SCROW nRow, sc::ColumnBlockPosition& rBlockPos )
+{
+    if ( !IsColRowValid( nCol, nRow ) )
+        return ScRefCellValue();
+
+    return aCol[nCol].GetCellValue(rBlockPos, nRow);
+}
+
 SvtBroadcaster* ScTable::GetBroadcaster( SCCOL nCol, SCROW nRow )
 {
     if ( !IsColRowValid( nCol, nRow ) )
diff --git a/sc/source/filter/html/htmlexp.cxx b/sc/source/filter/html/htmlexp.cxx
index ea7ae4c025da..8b9a5ade838b 100644
--- a/sc/source/filter/html/htmlexp.cxx
+++ b/sc/source/filter/html/htmlexp.cxx
@@ -59,6 +59,7 @@
 #include <editutil.hxx>
 #include <ftools.hxx>
 #include <cellvalue.hxx>
+#include <mtvelements.hxx>
 
 #include <editeng/flditem.hxx>
 #include <editeng/borderline.hxx>
@@ -764,6 +765,10 @@ void ScHTMLExport::WriteTables()
         // At least old (3.x, 4.x?) Netscape doesn't follow <TABLE COLS=n> and
         // <COL WIDTH=x> specified, but needs a width at every column.
         bool bHasHiddenRows = pDoc->HasHiddenRows(nStartRow, nEndRow, nTab);
+        // We need to cache sc::ColumnBlockPosition per each column.
+        std::vector< sc::ColumnBlockPosition > blockPos( nEndCol - nStartCol + 1 );
+        for( SCCOL i = nStartCol; i <= nEndCol; ++i )
+            pDoc->InitColumnBlockPosition( blockPos[ i - nStartCol ], nTab, i );
         for ( SCROW nRow=nStartRow; nRow<=nEndRow; nRow++ )
         {
             if ( bHasHiddenRows && pDoc->RowHidden(nRow, nTab) )
@@ -782,7 +787,7 @@ void ScHTMLExport::WriteTables()
 
                 if ( nCol2 == nEndCol )
                     IncIndent(-1);
-                WriteCell( nCol2, nRow, nTab );
+                WriteCell( blockPos[ nCol2 - nStartCol ], nCol2, nRow, nTab );
                 bTableDataHeight = false;
             }
 
@@ -822,16 +827,17 @@ void ScHTMLExport::WriteTables()
     }
 }
 
-void ScHTMLExport::WriteCell( SCCOL nCol, SCROW nRow, SCTAB nTab )
+void ScHTMLExport::WriteCell( sc::ColumnBlockPosition& rBlockPos, SCCOL nCol, SCROW nRow, SCTAB nTab )
 {
+    ScAddress aPos( nCol, nRow, nTab );
+    ScRefCellValue aCell(*pDoc, aPos, rBlockPos);
     const ScPatternAttr* pAttr = pDoc->GetPattern( nCol, nRow, nTab );
-    const SfxItemSet* pCondItemSet = pDoc->GetCondResult( nCol, nRow, nTab );
+    const SfxItemSet* pCondItemSet = pDoc->GetCondResult( nCol, nRow, nTab, &aCell );
 
     const ScMergeFlagAttr& rMergeFlagAttr = pAttr->GetItem( ATTR_MERGE_FLAG, pCondItemSet );
     if ( rMergeFlagAttr.IsOverlapped() )
         return ;
 
-    ScAddress aPos( nCol, nRow, nTab );
     ScHTMLGraphEntry* pGraphEntry = nullptr;
     if ( bTabHasGraphics && !mbSkipImages )
     {
@@ -852,13 +858,11 @@ void ScHTMLExport::WriteCell( SCCOL nCol, SCROW nRow, SCTAB nTab )
         }
     }
 
-    ScRefCellValue aCell(*pDoc, aPos);
-
     sal_uInt32 nFormat = pAttr->GetNumberFormat( pFormatter );
     bool bValueData = aCell.hasNumeric();
     SvtScriptType nScriptType = SvtScriptType::NONE;
     if (!aCell.isEmpty())
-        nScriptType = pDoc->GetScriptType(nCol, nRow, nTab);
+        nScriptType = pDoc->GetScriptType(nCol, nRow, nTab, &aCell);
 
     if ( nScriptType == SvtScriptType::NONE )
         nScriptType = aHTMLStyle.nDefaultScriptType;
diff --git a/sc/source/filter/inc/htmlexp.hxx b/sc/source/filter/inc/htmlexp.hxx
index f0507cc1738d..8642795baa8a 100644
--- a/sc/source/filter/inc/htmlexp.hxx
+++ b/sc/source/filter/inc/htmlexp.hxx
@@ -42,6 +42,10 @@ class EditTextObject;
 enum class SvtScriptType;
 namespace editeng { class SvxBorderLine; }
 
+namespace sc {
+struct ColumnBlockPosition;
+}
+
 struct ScHTMLStyle
 {   // Defaults from stylesheet
     Color               aBackgroundColor;
@@ -133,7 +137,7 @@ class ScHTMLExport : public ScExportBase
     void WriteHeader();
     void WriteOverview();
     void WriteTables();
-    void WriteCell( SCCOL nCol, SCROW nRow, SCTAB nTab );
+    void WriteCell( sc::ColumnBlockPosition& rBlockPos, SCCOL nCol, SCROW nRow, SCTAB nTab );
     void WriteGraphEntry( ScHTMLGraphEntry* );
     void WriteImage( OUString& rLinkName,
                      const Graphic&, const OString& rImgOptions,