tdf#150749 Find and replace on very large sheet

This requires 2 fixes

(*) First, we are deleting from the front of a block in the mdds
storage, so apply a similar patch to mdds to the previous improvement,

(*) Then, we end up with an O(n^2) situation in ScRangesList::Join.
But we are only displaying this data, and in fact, we only display the
first 1000 ranges anyway, so just clamp the list to 1000 entries, and
pass a flag up to the dialog so that we can report that we stopped
counting.

(*) I had to tweak the testSharedStringPool unit test, since
we are not actually clearing the underlying mdds storage, the
reference counts do not drop until we have removed all the
elements in that block of mdds storage (because then the entire
block is destructed, including the not-yet destructed elements)

Change-Id: I2c998f81dfb46453a48fce1254fd253d299d12b8
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/139400
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

6 files changed, 42 insertions, 21 deletions

diff --git a/sc/source/core/data/documen3.cxx b/sc/source/core/data/documen3.cxx
index c0b6984008b7..87f4dfec813b 100644
--- a/sc/source/core/data/documen3.cxx
+++ b/sc/source/core/data/documen3.cxx
@@ -1316,7 +1316,7 @@ bool ScDocument::IsEmptyCellSearch( const SvxSearchItem& rSearchItem )
 bool ScDocument::SearchAndReplace(
     const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow, SCTAB& rTab,
     const ScMarkData& rMark, ScRangeList& rMatchedRanges,
-    OUString& rUndoStr, ScDocument* pUndoDoc)
+    OUString& rUndoStr, ScDocument* pUndoDoc, bool& bMatchedRangesWereClamped)
 {
     // FIXME: Manage separated marks per table!
     bool bFound = false;
@@ -1341,7 +1341,7 @@ bool ScDocument::SearchAndReplace(
                     nCol = 0;
                     nRow = 0;
                     bFound |= maTabs[rMarkedTab]->SearchAndReplace(
-                        rSearchItem, nCol, nRow, rMark, rMatchedRanges, rUndoStr, pUndoDoc);
+                        rSearchItem, nCol, nRow, rMark, rMatchedRanges, rUndoStr, pUndoDoc, bMatchedRangesWereClamped);
                 }
             }
 
@@ -1359,7 +1359,7 @@ bool ScDocument::SearchAndReplace(
                         if (rMark.GetTableSelect(nTab))
                         {
                             bFound = maTabs[nTab]->SearchAndReplace(
-                                rSearchItem, nCol, nRow, rMark, rMatchedRanges, rUndoStr, pUndoDoc);
+                                rSearchItem, nCol, nRow, rMark, rMatchedRanges, rUndoStr, pUndoDoc, bMatchedRangesWereClamped);
                             if (bFound)
                             {
                                 rCol = nCol;
@@ -1390,7 +1390,7 @@ bool ScDocument::SearchAndReplace(
                         if (rMark.GetTableSelect(nTab))
                         {
                             bFound = maTabs[nTab]->SearchAndReplace(
-                                rSearchItem, nCol, nRow, rMark, rMatchedRanges, rUndoStr, pUndoDoc);
+                                rSearchItem, nCol, nRow, rMark, rMatchedRanges, rUndoStr, pUndoDoc, bMatchedRangesWereClamped);
                             if (bFound)
                             {
                                 rCol = nCol;
diff --git a/sc/source/core/data/table6.cxx b/sc/source/core/data/table6.cxx
index f7446ee73a32..1915ad7c1588 100644
--- a/sc/source/core/data/table6.cxx
+++ b/sc/source/core/data/table6.cxx
@@ -585,7 +585,7 @@ bool ScTable::Replace(const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow
 
 bool ScTable::ReplaceAll(
     const SvxSearchItem& rSearchItem, const ScMarkData& rMark, ScRangeList& rMatchedRanges,
-    OUString& rUndoStr, ScDocument* pUndoDoc)
+    OUString& rUndoStr, ScDocument* pUndoDoc, bool& bMatchedRangesWereClamped)
 {
     SCCOL nCol = 0;
     SCROW nRow = -1;
@@ -610,7 +610,12 @@ bool ScTable::ReplaceAll(
         if (bFound)
         {
             bEverFound = true;
-            rMatchedRanges.Join(ScRange(nCol, nRow, nTab));
+            // The combination of this loop and the Join() algorithm is O(n^2),
+            // so just give up if the list gets too big.
+            if (rMatchedRanges.size() < 1000)
+                rMatchedRanges.Join(ScRange(nCol, nRow, nTab));
+            else
+                bMatchedRangesWereClamped = true;
         }
         else
             break;
@@ -796,7 +801,7 @@ bool ScTable::ReplaceAllStyle(
 
 bool ScTable::SearchAndReplace(
     const SvxSearchItem& rSearchItem, SCCOL& rCol, SCROW& rRow, const ScMarkData& rMark,
-    ScRangeList& rMatchedRanges, OUString& rUndoStr, ScDocument* pUndoDoc)
+    ScRangeList& rMatchedRanges, OUString& rUndoStr, ScDocument* pUndoDoc, bool& bMatchedRangesWereClamped)
 {
     SvxSearchCmd nCommand = rSearchItem.GetCommand();
     bool bFound = false;
@@ -848,7 +853,7 @@ bool ScTable::SearchAndReplace(
             else if (nCommand == SvxSearchCmd::REPLACE)
                 bFound = Replace(rSearchItem, rCol, rRow, rMark, rUndoStr, pUndoDoc);
             else if (nCommand == SvxSearchCmd::REPLACE_ALL)
-                bFound = ReplaceAll(rSearchItem, rMark, rMatchedRanges, rUndoStr, pUndoDoc);
+                bFound = ReplaceAll(rSearchItem, rMark, rMatchedRanges, rUndoStr, pUndoDoc, bMatchedRangesWereClamped);
 
             pSearchText.reset();
         }
diff --git a/sc/source/ui/dialogs/searchresults.cxx b/sc/source/ui/dialogs/searchresults.cxx
index ab0e5790705b..4ea08c1d49cb 100644
--- a/sc/source/ui/dialogs/searchresults.cxx
+++ b/sc/source/ui/dialogs/searchresults.cxx
@@ -96,7 +96,7 @@ namespace
 }
 
 void SearchResultsDlg::FillResults( ScDocument& rDoc, const ScRangeList &rMatchedRanges, bool bCellNotes,
-        bool bEmptyCells )
+        bool bEmptyCells, bool bMatchedRangesWereClamped )
 {
     ListWrapper aList(*mxList);
     std::vector<OUString> aTabNames = rDoc.GetAllTableNames();
@@ -161,11 +161,20 @@ void SearchResultsDlg::FillResults( ScDocument& rDoc, const ScRangeList &rMatche
         }
     }
 
-    OUString aTotal(ScResId(SCSTR_TOTAL, aList.mnCount));
-    OUString aSearchResults = aTotal.replaceFirst("%1", OUString::number(aList.mnCount));
-    if (aList.mnCount > ListWrapper::mnMaximum)
-        aSearchResults += " " + ScGlobal::ReplaceOrAppend( aSkipped, u"%1", OUString::number( ListWrapper::mnMaximum ) );
-    mxSearchResults->set_label(aSearchResults);
+    OUString aSearchResultsMsg;
+    if (bMatchedRangesWereClamped)
+    {
+        aSearchResultsMsg = ScResId(SCSTR_RESULTS_CLAMPED);
+        aSearchResultsMsg = aSearchResultsMsg.replaceFirst("%1", OUString::number(1000));
+    }
+    else
+    {
+        OUString aTotal(ScResId(SCSTR_TOTAL, aList.mnCount));
+        aSearchResultsMsg = aTotal.replaceFirst("%1", OUString::number(aList.mnCount));
+        if (aList.mnCount > ListWrapper::mnMaximum)
+            aSearchResultsMsg += " " + ScGlobal::ReplaceOrAppend( aSkipped, u"%1", OUString::number( ListWrapper::mnMaximum ) );
+    }
+    mxSearchResults->set_label(aSearchResultsMsg);
 
     mpDoc = &rDoc;
 }
diff --git a/sc/source/ui/inc/searchresults.hxx b/sc/source/ui/inc/searchresults.hxx
index c10e6014342a..61cfc520b4ff 100644
--- a/sc/source/ui/inc/searchresults.hxx
+++ b/sc/source/ui/inc/searchresults.hxx
@@ -37,7 +37,9 @@ public:
 
     virtual void Close() override;
 
-    void FillResults( ScDocument& rDoc, const ScRangeList& rMatchedRanges, bool bCellNotes, bool bEmptyCells );
+    void FillResults( ScDocument& rDoc, const ScRangeList& rMatchedRanges,
+            bool bCellNotes, bool bEmptyCells,
+            bool bMatchedRangesWereClamped);
 };
 
 class SearchResultsDlgWrapper : public SfxChildWindow
diff --git a/sc/source/ui/unoobj/cellsuno.cxx b/sc/source/ui/unoobj/cellsuno.cxx
index 03ff6d9a62b9..119486d79768 100644
--- a/sc/source/ui/unoobj/cellsuno.cxx
+++ b/sc/source/ui/unoobj/cellsuno.cxx
@@ -3776,8 +3776,9 @@ uno::Reference<container::XIndexAccess> SAL_CALL ScCellRangesBase::findAll(
                 SCCOL nCol = 0;
                 SCROW nRow = 0;
                 SCTAB nTab = 0;
+                bool bMatchedRangesWereClamped = false;
                 bool bFound = rDoc.SearchAndReplace(
-                    *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges, aDummyUndo);
+                    *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges, aDummyUndo, nullptr, bMatchedRangesWereClamped);
                 if (bFound)
                 {
                     //  on findAll always CellRanges no matter how much has been found
@@ -3822,8 +3823,9 @@ uno::Reference<uno::XInterface> ScCellRangesBase::Find_Impl(
 
                 OUString aDummyUndo;
                 ScRangeList aMatchedRanges;
+                bool bMatchedRangesWereClamped;
                 bool bFound = rDoc.SearchAndReplace(
-                    *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges, aDummyUndo);
+                    *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges, aDummyUndo, nullptr, bMatchedRangesWereClamped);
                 if (bFound)
                 {
                     ScAddress aFoundPos( nCol, nRow, nTab );
@@ -3931,8 +3933,9 @@ sal_Int32 SAL_CALL ScCellRangesBase::replaceAll( const uno::Reference<util::XSea
                     if (bUndo)
                     {
                         ScRangeList aMatchedRanges;
+                        bool bMatchedRangesWereClamped;
                         bFound = rDoc.SearchAndReplace(
-                            *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges, aUndoStr, pUndoDoc.get() );
+                            *pSearchItem, nCol, nRow, nTab, aMark, aMatchedRanges, aUndoStr, pUndoDoc.get(), bMatchedRangesWereClamped );
                     }
                     if (bFound)
                     {
diff --git a/sc/source/ui/view/viewfun2.cxx b/sc/source/ui/view/viewfun2.cxx
index d05ddad12c24..634d41f4df17 100644
--- a/sc/source/ui/view/viewfun2.cxx
+++ b/sc/source/ui/view/viewfun2.cxx
@@ -2031,7 +2031,8 @@ bool ScViewFunc::SearchAndReplace( const SvxSearchItem* pSearchItem,
     {
         GetFrameWin()->EnterWait();
         ScRangeList aMatchedRanges;
-        if (rDoc.SearchAndReplace(*pSearchItem, nCol, nRow, nTab, rMark, aMatchedRanges, aUndoStr, pUndoDoc.get()))
+        bool bMatchedRangesWereClamped;
+        if (rDoc.SearchAndReplace(*pSearchItem, nCol, nRow, nTab, rMark, aMatchedRanges, aUndoStr, pUndoDoc.get(), bMatchedRangesWereClamped))
         {
             bFound = true;
             if (bAddUndo)
@@ -2064,7 +2065,7 @@ bool ScViewFunc::SearchAndReplace( const SvxSearchItem* pSearchItem,
                                             && ScDocument::IsEmptyCellSearch(*pSearchItem))
                                         || (nCommand == SvxSearchCmd::REPLACE_ALL
                                             && pSearchItem->GetReplaceString().isEmpty())));
-                            pDlg->FillResults(rDoc, aMatchedRanges, bCellNotes, bEmptyCells);
+                            pDlg->FillResults(rDoc, aMatchedRanges, bCellNotes, bEmptyCells, bMatchedRangesWereClamped);
                         }
                     }
                 }
@@ -2219,8 +2220,9 @@ bool ScViewFunc::SearchAndReplace( const SvxSearchItem* pSearchItem,
                     aSearchItem.SetWhich(SID_SEARCH_ITEM);
 
                     ScRangeList aMatchedRanges;
+                    bool bMatchedRangesWereClamped;
                     ScTable::UpdateSearchItemAddressForReplace( aSearchItem, nCol, nRow );
-                    if ( rDoc.SearchAndReplace( aSearchItem, nCol, nRow, nTab, rMark, aMatchedRanges, aUndoStr ) &&
+                    if ( rDoc.SearchAndReplace( aSearchItem, nCol, nRow, nTab, rMark, aMatchedRanges, aUndoStr, nullptr, bMatchedRangesWereClamped ) &&
                             ( nTab == nOldTab ) &&
                             ( nCol != nOldCol || nRow != nOldRow ) )
                     {