cache mdds positions during ScDocument::CopyBlockFromClip() (tdf#112000)

Make RefUpdateContext and ScColumn::UpdateReferenceOnCopy() use the same
sc::ColumnBlockPositionSet that CopyFromClipContext uses. Without it
pathological cases like in tdf#112000 trigger quadratic cost because
of repeated mdds searches from the start.
Includes also an mdds patch that allows it to search backwards
from a position hint. Without it, this would be very difficult to fix
otherwise, as CopyFromClip() in ScDocument::CopyBlockFromClip()
moves the position hint past the area that UpdateReferenceOnCopy()
would use. It also just plain makes sense to try to go backwards
in an std::vector.

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

6 files changed, 29 insertions, 4 deletions

diff --git a/sc/inc/clipcontext.hxx b/sc/inc/clipcontext.hxx
index f2a7af56818b..6752104fb34c 100644
--- a/sc/inc/clipcontext.hxx
+++ b/sc/inc/clipcontext.hxx
@@ -40,6 +40,7 @@ public:
     virtual ~ClipContextBase();
 
     ColumnBlockPosition* getBlockPosition(SCTAB nTab, SCCOL nCol);
+    ColumnBlockPositionSet* getBlockPositionSet() { return mpSet.get(); }
 };
 
 class CopyFromClipContext : public ClipContextBase
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 340b5628faf6..e7e40fd528bf 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -417,7 +417,7 @@ public:
 
     void        ResetChanged( SCROW nStartRow, SCROW nEndRow );
 
-    bool UpdateReferenceOnCopy( const sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc = nullptr );
+    bool UpdateReferenceOnCopy( sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc = nullptr );
 
     /**
      * Update reference addresses in formula cell in response to mass cell
diff --git a/sc/inc/refupdatecontext.hxx b/sc/inc/refupdatecontext.hxx
index 7b5afe926e1a..bc86cb9e1afe 100644
--- a/sc/inc/refupdatecontext.hxx
+++ b/sc/inc/refupdatecontext.hxx
@@ -21,6 +21,9 @@ class ScDocument;
 
 namespace sc {
 
+struct ColumnBlockPosition;
+class ColumnBlockPositionSet;
+
 /**
  * Keep track of all named expressions that have been updated during
  * reference update.
@@ -76,10 +79,15 @@ struct RefUpdateContext
     UpdatedRangeNames maUpdatedNames;
     ColumnSet maRegroupCols;
 
+    ColumnBlockPositionSet* mpBlockPos; // not owning
+
     RefUpdateContext(ScDocument& rDoc);
 
     bool isInserted() const;
     bool isDeleted() const;
+
+    void setBlockPositionReference( ColumnBlockPositionSet* blockPos );
+    ColumnBlockPosition* getBlockPosition(SCTAB nTab, SCCOL nCol);
 };
 
 struct RefUpdateResult
diff --git a/sc/source/core/data/column.cxx b/sc/source/core/data/column.cxx
index 548e6403cc8b..18132d2fc454 100644
--- a/sc/source/core/data/column.cxx
+++ b/sc/source/core/data/column.cxx
@@ -42,6 +42,7 @@
 #include <listenercontext.hxx>
 #include <formulagroup.hxx>
 #include <drwlayer.hxx>
+#include <mtvelements.hxx>
 
 #include <svl/poolcach.hxx>
 #include <svl/zforlist.hxx>
@@ -2424,14 +2425,17 @@ public:
 
 }
 
-bool ScColumn::UpdateReferenceOnCopy( const sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc )
+bool ScColumn::UpdateReferenceOnCopy( sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc )
 {
     // When copying, the range equals the destination range where cells
     // are pasted, and the dx, dy, dz refer to the distance from the
     // source range.
 
     UpdateRefOnCopy aHandler(rCxt, pUndoDoc);
-    sc::CellStoreType::position_type aPos = maCells.position(rCxt.maRange.aStart.Row());
+    sc::ColumnBlockPosition* blockPos = rCxt.getBlockPosition(nTab, nCol);
+    sc::CellStoreType::position_type aPos = blockPos
+        ? maCells.position(blockPos->miCellPos, rCxt.maRange.aStart.Row())
+        : maCells.position(rCxt.maRange.aStart.Row());
     sc::ProcessBlock(aPos.first, maCells, aHandler, rCxt.maRange.aStart.Row(), rCxt.maRange.aEnd.Row());
 
     // The formula groups at the top and bottom boundaries are expected to
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index 4e74fc8dbf56..106ca902534e 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -2675,6 +2675,7 @@ void ScDocument::CopyBlockFromClip(
                 aRefCxt.mnColDelta = nDx;
                 aRefCxt.mnRowDelta = nDy;
                 aRefCxt.mnTabDelta = nDz;
+                aRefCxt.setBlockPositionReference(rCxt.getBlockPositionSet()); // share mdds position caching
                 if (rCxt.getClipDoc()->GetClipParam().mbCutMode)
                 {
                     // Update references only if cut originates from the same
diff --git a/sc/source/core/data/refupdatecontext.cxx b/sc/source/core/data/refupdatecontext.cxx
index d4cce81dc680..c34ac6860ee1 100644
--- a/sc/source/core/data/refupdatecontext.cxx
+++ b/sc/source/core/data/refupdatecontext.cxx
@@ -9,6 +9,7 @@
 
 #include <refupdatecontext.hxx>
 #include <algorithm>
+#include <mtvelements.hxx>
 
 namespace sc {
 
@@ -64,7 +65,7 @@ bool UpdatedRangeNames::isEmpty(SCTAB nTab) const
 
 
 RefUpdateContext::RefUpdateContext(ScDocument& rDoc) :
-    mrDoc(rDoc), meMode(URM_INSDEL), mnColDelta(0), mnRowDelta(0), mnTabDelta(0) {}
+    mrDoc(rDoc), meMode(URM_INSDEL), mnColDelta(0), mnRowDelta(0), mnTabDelta(0), mpBlockPos( nullptr ) {}
 
 bool RefUpdateContext::isInserted() const
 {
@@ -76,6 +77,16 @@ bool RefUpdateContext::isDeleted() const
     return (meMode == URM_INSDEL) && (mnColDelta < 0 || mnRowDelta < 0 || mnTabDelta < 0);
 }
 
+void RefUpdateContext::setBlockPositionReference( ColumnBlockPositionSet* blockPos )
+{
+    mpBlockPos = blockPos;
+}
+
+ColumnBlockPosition* RefUpdateContext::getBlockPosition(SCTAB nTab, SCCOL nCol)
+{
+    return mpBlockPos ? mpBlockPos->getBlockPosition(nTab, nCol) : nullptr;
+}
+
 RefUpdateResult::RefUpdateResult() : mbValueChanged(false), mbReferenceModified(false), mbNameModified(false) {}
 
 RefUpdateInsertTabContext::RefUpdateInsertTabContext(ScDocument& rDoc, SCTAB nInsertPos, SCTAB nSheets) :