avoid possible expensive repetitive formula group changes (tdf#102364)

The testcase from tdf#102364 is actually a rather pathological case,
the document having a full 1M cells column with the same formula, and doing
undo in this case essentially pastes the column over itself (I think
a column is first deleted, which moves this column, and then ScUndoInsertCells
will trigger ScMoveUndo::UndoRef(), which will paste the column in that place
again. And since this is done cell by cell, removing old cell first splits
the large formula group and then adding a new cell with the same formula
rejoins the formula group, and setting these formula group changes for all
the cells over and over actually takes a long time.
Avoid that by delaying the formula grouping operation and do it just once
at the end. I'm not sure if this is that good way of handling this, given
the testcase is very specific, but I can imagine something similar happening
in other possible cases (manual copy&paste of a large column over itself
or moving it slightly up or down).

Change-Id: Ie4241197103a039c232150333250f78175b1c2c7
Reviewed-on: https://gerrit.libreoffice.org/64782
Tested-by: Jenkins
Reviewed-by: Kohei Yoshida <libreoffice@kohei.us>
Reviewed-by: Eike Rathke <erack@redhat.com>

8 files changed, 90 insertions, 0 deletions

diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index f5f8fdbd594d..bb7a4f01fa2b 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -502,6 +502,9 @@ private:
     bool                bExpandRefs;
     // for detective update, is set for each change of a formula
     bool                bDetectiveDirty;
+    // If the pointer is set, formula cells will not be automatically grouped into shared formula groups,
+    // instead the range will be extended to contain all such cells.
+    std::unique_ptr< ScRange > pDelayedFormulaGrouping;
 
     bool                bLinkFormulaNeedingCheck; // valid only after loading, for ocDde and ocWebservice
 
@@ -1317,6 +1320,12 @@ public:
     bool            IsForcedFormulaPending() const { return bForcedFormulaPending; }
                     // if CalcFormulaTree() is currently running
     bool            IsCalculatingFormulaTree() { return bCalculatingFormulaTree; }
+    /// If set, joining cells into shared formula groups will be delayed until reset again
+    /// (RegroupFormulaCells() will be called as needed).
+    void            DelayFormulaGrouping( bool delay );
+    bool            IsDelayedFormulaGrouping() const { return pDelayedFormulaGrouping.get() != nullptr; }
+    /// To be used only by SharedFormulaUtil::joinFormulaCells().
+    void            AddDelayedFormulaGroupingCell( ScFormulaCell* cell );
 
     FormulaError    GetErrCode( const ScAddress& ) const;
 
@@ -2399,6 +2408,7 @@ public:
      */
     void UnshareFormulaCells( SCTAB nTab, SCCOL nCol, std::vector<SCROW>& rRows );
     void RegroupFormulaCells( SCTAB nTab, SCCOL nCol );
+    void RegroupFormulaCells( const ScRange& range );
 
     ScFormulaVectorState GetFormulaVectorState( const ScAddress& rPos ) const;
 
diff --git a/sc/inc/scopetools.hxx b/sc/inc/scopetools.hxx
index f49c077dd588..7789d9645b8a 100644
--- a/sc/inc/scopetools.hxx
+++ b/sc/inc/scopetools.hxx
@@ -65,6 +65,17 @@ public:
     ~WaitPointerSwitch();
 };
 
+/// Wrapper for ScDocument::DelayFormulaGrouping()
+class SC_DLLPUBLIC DelayFormulaGroupingSwitch
+{
+    ScDocument& mrDoc;
+    bool const mbOldValue;
+public:
+    DelayFormulaGroupingSwitch(ScDocument& rDoc, bool delay);
+    ~DelayFormulaGroupingSwitch();
+    void reset();
+};
+
 }
 
 #endif
diff --git a/sc/qa/unit/ucalc_sharedformula.cxx b/sc/qa/unit/ucalc_sharedformula.cxx
index b54216b413d4..46ced2ce21c4 100644
--- a/sc/qa/unit/ucalc_sharedformula.cxx
+++ b/sc/qa/unit/ucalc_sharedformula.cxx
@@ -708,6 +708,17 @@ void Test::testSharedFormulasRefUpdateRangeDeleteRow()
     // Undo the deletion of row 3.
     pUndoMgr->Undo();
 
+    // Make sure that C1:C2 and C4:C5 are formula groups again.
+    pFC = m_pDoc->GetFormulaCell(ScAddress(2,0,0));
+    CPPUNIT_ASSERT(pFC);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCROW>(0), pFC->GetSharedTopRow());
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCROW>(2), pFC->GetSharedLength());
+
+    pFC = m_pDoc->GetFormulaCell(ScAddress(2,3,0));
+    CPPUNIT_ASSERT(pFC);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCROW>(3), pFC->GetSharedTopRow());
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCROW>(2), pFC->GetSharedLength());
+
     // Check the values of formula cells again.
     CPPUNIT_ASSERT_EQUAL( 3.0, m_pDoc->GetValue(ScAddress(2,0,0)));
     CPPUNIT_ASSERT_EQUAL( 7.0, m_pDoc->GetValue(ScAddress(2,1,0)));
diff --git a/sc/source/core/data/bcaslot.cxx b/sc/source/core/data/bcaslot.cxx
index f63e116cc083..14555512fd35 100644
--- a/sc/source/core/data/bcaslot.cxx
+++ b/sc/source/core/data/bcaslot.cxx
@@ -157,6 +157,7 @@ bool ScBroadcastAreaSlot::StartListeningArea(
 {
     bool bNewArea = false;
     OSL_ENSURE(pListener, "StartListeningArea: pListener Null");
+    assert(!pDoc->IsDelayedFormulaGrouping()); // otherwise the group size might be incorrect
     if (CheckHardRecalcStateCondition() == ScDocument::HardRecalcState::ETERNAL)
         return false;
     if ( !rpArea )
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index dbba8a220748..749a15f37fae 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -2123,6 +2123,11 @@ void ScDocument::CopyToDocument(const ScRange& rRange,
 
     sc::AutoCalcSwitch aACSwitch(rDestDoc, false); // avoid multiple calculations
 
+    // tdf#102364 - in some pathological cases CopyToDocument() replacing cells with new cells
+    // can lead to repetitive splitting and rejoining of the same formula group, which can get
+    // quadratically expensive with large groups. So do the grouping just once at the end.
+    sc::DelayFormulaGroupingSwitch delayGrouping( rDestDoc, true );
+
     sc::CopyToDocContext aCxt(rDestDoc);
     aCxt.setStartListening(false);
 
@@ -2140,6 +2145,7 @@ void ScDocument::CopyToDocument(const ScRange& rRange,
             /*bGlobalNamesToLocal*/false, /*bCopyCaptions*/true);
     }
 
+    delayGrouping.reset(); // groups need to be updated before setting up listeners
     rDestDoc.StartAllListeners(aNewRange);
 }
 
diff --git a/sc/source/core/data/document10.cxx b/sc/source/core/data/document10.cxx
index 0f49dc63c756..b688c1db80e5 100644
--- a/sc/source/core/data/document10.cxx
+++ b/sc/source/core/data/document10.cxx
@@ -374,6 +374,34 @@ void ScDocument::RegroupFormulaCells( SCTAB nTab, SCCOL nCol )
     pTab->RegroupFormulaCells(nCol);
 }
 
+void ScDocument::RegroupFormulaCells( const ScRange& rRange )
+{
+    for( SCTAB tab = rRange.aStart.Tab(); tab <= rRange.aEnd.Tab(); ++tab )
+        for( SCCOL col = rRange.aStart.Col(); col <= rRange.aEnd.Col(); ++col )
+            RegroupFormulaCells( tab, col );
+}
+
+void ScDocument::DelayFormulaGrouping( bool delay )
+{
+    if( delay )
+    {
+        if( pDelayedFormulaGrouping.get() == nullptr )
+            pDelayedFormulaGrouping.reset( new ScRange( ScAddress::INITIALIZE_INVALID ));
+    }
+    else
+    {
+        if( pDelayedFormulaGrouping.get() != nullptr && pDelayedFormulaGrouping->IsValid())
+            RegroupFormulaCells( *pDelayedFormulaGrouping );
+        pDelayedFormulaGrouping.reset();
+    }
+}
+
+void ScDocument::AddDelayedFormulaGroupingCell( ScFormulaCell* cell )
+{
+    if( !pDelayedFormulaGrouping->In( cell->aPos ))
+        pDelayedFormulaGrouping->ExtendTo( cell->aPos );
+}
+
 void ScDocument::CollectAllAreaListeners(
     std::vector<SvtListener*>& rListener, const ScRange& rRange, sc::AreaOverlapType eType )
 {
diff --git a/sc/source/core/tool/scopetools.cxx b/sc/source/core/tool/scopetools.cxx
index 74c370a4f379..185a44fc65ca 100644
--- a/sc/source/core/tool/scopetools.cxx
+++ b/sc/source/core/tool/scopetools.cxx
@@ -70,6 +70,22 @@ WaitPointerSwitch::~WaitPointerSwitch()
         mpFrameWin->LeaveWait();
 }
 
+DelayFormulaGroupingSwitch::DelayFormulaGroupingSwitch(ScDocument& rDoc, bool delay) :
+    mrDoc(rDoc), mbOldValue(rDoc.IsDelayedFormulaGrouping())
+{
+    mrDoc.DelayFormulaGrouping(delay);
+}
+
+DelayFormulaGroupingSwitch::~DelayFormulaGroupingSwitch()
+{
+    mrDoc.DelayFormulaGrouping(mbOldValue);
+}
+
+void DelayFormulaGroupingSwitch::reset()
+{
+    mrDoc.DelayFormulaGrouping(mbOldValue);
+}
+
 }
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/tool/sharedformula.cxx b/sc/source/core/tool/sharedformula.cxx
index 913b2fe48bb9..6d53cb9fa513 100644
--- a/sc/source/core/tool/sharedformula.cxx
+++ b/sc/source/core/tool/sharedformula.cxx
@@ -133,6 +133,13 @@ void SharedFormulaUtil::splitFormulaCellGroups(CellStoreType& rCells, std::vecto
 bool SharedFormulaUtil::joinFormulaCells(
     const CellStoreType::position_type& rPos, ScFormulaCell& rCell1, ScFormulaCell& rCell2 )
 {
+    if( rCell1.GetDocument()->IsDelayedFormulaGrouping())
+    {
+        rCell1.GetDocument()->AddDelayedFormulaGroupingCell( &rCell1 );
+        rCell1.GetDocument()->AddDelayedFormulaGroupingCell( &rCell2 );
+        return false;
+    }
+
     ScFormulaCell::CompareState eState = rCell1.CompareByTokenArray(rCell2);
     if (eState == ScFormulaCell::NotEqual)
         return false;