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>

8 files changed, 80 insertions, 4 deletions

diff --git a/external/mdds/UnpackedTarball_mdds.mk b/external/mdds/UnpackedTarball_mdds.mk
index c015f4c13f5a..625204d29619 100644
--- a/external/mdds/UnpackedTarball_mdds.mk
+++ b/external/mdds/UnpackedTarball_mdds.mk
@@ -14,6 +14,7 @@ $(eval $(call gb_UnpackedTarball_set_tarball,mdds,$(MDDS_TARBALL)))
 $(eval $(call gb_UnpackedTarball_set_patchlevel,mdds,0))
 
 $(eval $(call gb_UnpackedTarball_add_patches,mdds,\
+	external/mdds/use-position-hint-also-back.patch \
 ))
 
 # vim: set noet sw=4 ts=4:
diff --git a/external/mdds/use-position-hint-also-back.patch b/external/mdds/use-position-hint-also-back.patch
new file mode 100644
index 000000000000..0b38c38d5536
--- /dev/null
+++ b/external/mdds/use-position-hint-also-back.patch
@@ -0,0 +1,50 @@
+From 726e2f02d14833bde2f7eef9677f5564c485a992 Mon Sep 17 00:00:00 2001
+From: =?UTF-8?q?Lubo=C5=A1=20Lu=C5=88=C3=A1k?= <l.lunak@centrum.cz>
+Date: Fri, 17 May 2019 13:55:20 +0200
+Subject: [PATCH] use position hint also when it is past the actual position
+
+The m_blocks data structure is a vector. It means that it can be
+also walked back, instead of resetting and starting from the very
+start.
+
+Allows a noticeable performance improvement in
+https://gerrit.libreoffice.org/#/c/72424/ .
+---
+ include/mdds/multi_type_vector_def.inl | 21 ++++++++++++++++++++-
+ 1 file changed, 20 insertions(+), 1 deletion(-)
+
+diff --git a/include/mdds/multi_type_vector_def.inl b/include/mdds/multi_type_vector_def.inl
+index 22a0ee2..09894e6 100644
+--- include/mdds/multi_type_vector_def.inl
++++ include/mdds/multi_type_vector_def.inl
+@@ -861,7 +861,26 @@ void multi_type_vector<_CellBlockFunc, _EventFunc>::get_block_position(
+ 
+     if (pos < start_row)
+     {
+-        // Position hint is past the insertion position. Reset.
++        // Position hint is past the insertion position.
++        // Walk back if that seems efficient.
++        if (pos > start_row / 2)
++        {
++            for (size_type i = block_index; i > 0;)
++            {
++                --i;
++                const block& blk = m_blocks[i];
++                start_row -= blk.m_size;
++                if (pos >= start_row)
++                {
++                    // Row is in this block.
++                    block_index = i;
++                    return;
++                }
++                // Specified row is not in this block.
++            }
++            assert(start_row == 0);
++        }
++        // Otherwise reset.
+         start_row = 0;
+         block_index = 0;
+     }
+-- 
+2.16.4
+
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) :