Resolves: tdf#144135 Rework Sort with area extras

Since

    commit 774a61afa9fc281290e7bfad4e28c05978b82d73
    CommitDate: Wed Apr 14 08:46:03 2021 +0200

        tdf#126678 - Consider "Include formats" option during sort

a sheet formatted with visible attributes like cell background
colour up to the end if for Sort all columns and/or rows are
selected lead to an excessive memory allocation and slow execution
time if it didn't get killed by the operating system before due to
memory exhaustion.

The same could had happened already before if graphics or comments
were to be included that could had resulted in a similar large
range. However, cell formats across sheets are more likely.

This changes the strategy how the to be sorted data range is
determined (range only with data) and additional area extras
ranges without data that are only to be rearranged. Those are then
processed in chunks (limited to ~512MB per chunk).

Cell formats that are identical within one column's rows range do
not even need to be covered as they are not rearranged, in the
best case leading to all trailing formats' ranges being excluded
from the sort.

Additionally optimize the cell gathering of formats, graphics and
comments such that for the area extras they are only collected if
actually requested.

The overall performance gain is in an order of magnitudes even if
some extras are to be collected.

Change-Id: If3abbaeaa615aaff7d88a82a5b3fc7ac633d770d
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/122013
Reviewed-by: Eike Rathke <erack@redhat.com>
Tested-by: Jenkins

4 files changed, 99 insertions, 34 deletions

diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 01cf0da1f404..6300fe70bca1 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -219,19 +219,16 @@ public:
                 // data only:
     bool        IsEmptyBlock(SCROW nStartRow, SCROW nEndRow) const;
     SCSIZE      GetEmptyLinesInBlock( SCROW nStartRow, SCROW nEndRow, ScDirection eDir ) const;
-    bool        HasDataAt(SCROW nRow, bool bConsiderCellNotes = false,
-                   bool bConsiderCellDrawObjects = false, bool bConsiderCellFormats = false) const;
-    bool        HasDataAt(sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow,
-                   bool bConsiderCellNotes = false, bool bConsiderCellDrawObjects = false,
-                   bool bConsiderCellFormats = false) const;
-    bool        HasDataAt(sc::ColumnBlockPosition& rBlockPos, SCROW nRow, bool bConsiderCellNotes = false,
-                   bool bConsiderCellDrawObjects = false, bool bConsiderCellFormats = false);
+    bool        HasDataAt( SCROW nRow, ScDataAreaExtras* pDataAreaExtras = nullptr ) const;
+    bool        HasDataAt( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow,
+                           ScDataAreaExtras* pDataAreaExtras = nullptr ) const;
+    bool        HasDataAt( sc::ColumnBlockPosition& rBlockPos, SCROW nRow,
+                           ScDataAreaExtras* pDataAreaExtras = nullptr );
+    void        GetDataExtrasAt( SCROW nRow, ScDataAreaExtras& rDataAreaExtras ) const;
     bool        HasVisibleDataAt(SCROW nRow) const;
     SCROW       GetFirstDataPos() const;
     SCROW       GetLastDataPos() const;
-    SCROW       GetLastDataPos(SCROW nLastRow, bool bConsiderCellNotes = false,
-                         bool bConsiderCellDrawObjects = false,
-                         bool bConsiderCellFormats = false) const;
+    SCROW       GetLastDataPos( SCROW nLastRow, ScDataAreaExtras* pDataAreaExtras = nullptr ) const;
     bool        GetPrevDataPos(SCROW& rRow) const;
     bool        GetNextDataPos(SCROW& rRow) const;
     bool        TrimEmptyBlocks(SCROW& rRowStart, SCROW& rRowEnd) const;
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 2038e9d59725..5f41d1878db1 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -201,6 +201,7 @@ class ScColumnsRange;
 struct ScFilterEntries;
 typedef o3tl::sorted_vector<sal_uInt32> ScCondFormatIndexes;
 struct ScSheetLimits;
+struct ScDataAreaExtras;
 
 namespace sc {
 
@@ -1398,18 +1399,20 @@ public:
 
                     /** Shrink a range to only include used data area.
 
-                        @param o_bShrunk
-                               Out parameter, true if area was shrunk, false if not.
+                        @param  o_bShrunk
+                                Out parameter, true if area was shrunk, false if not.
+                        @param  bColumnsOnly
+                                If TRUE, shrink only by columns, not rows.
                         @param  bStickyTopRow
                                 If TRUE, do not adjust the top row.
                         @param  bStickyLeftCol
                                 If TRUE, do not adjust the left column.
-                        @param  bConsiderCellNotes
-                                If TRUE, consider the presence of cell notes besides data.
-                        @param  bConsiderCellDrawObjects
-                                If TRUE, consider the presence of draw objects anchored to the cell.
-                        @param bConsiderCellFormats
-                                If TRUE, consider the presence of cell formats.
+                        @param  pDataAreaExtras
+                                Consider additional area attributes like cell
+                                formatting, cell notes and draw objects. The
+                                possibly larger area than the actual cell
+                                content data area is returned within the
+                                struct.
 
                         @returns true if there is any data, false if not.
                      */
@@ -1417,9 +1420,7 @@ public:
                                           SCTAB nTab, SCCOL& rStartCol, SCROW& rStartRow,
                                           SCCOL& rEndCol, SCROW& rEndRow, bool bColumnsOnly,
                                           bool bStickyTopRow = false, bool bStickyLeftCol = false,
-                                          bool bConsiderCellNotes = false,
-                                          bool bConsiderCellDrawObjects = false,
-                                          bool bConsiderCellFormats = false ) const;
+                                          ScDataAreaExtras* pDataAreaExtras = nullptr ) const;
 
     /**
      * Return the last non-empty row position in given columns that's no
diff --git a/sc/inc/sortparam.hxx b/sc/inc/sortparam.hxx
index 365151cf2bec..d9047f873b1e 100644
--- a/sc/inc/sortparam.hxx
+++ b/sc/inc/sortparam.hxx
@@ -37,21 +37,82 @@ struct ScSortKeyState
     bool     bAscending;
 };
 
+/** Struct to hold non-data extended area, used with
+    ScDocument::ShrinkToUsedDataArea().
+*/
+struct ScDataAreaExtras
+{
+    /// If TRUE, consider the presence of cell notes besides data.
+    bool    mbCellNotes = false;
+    /// If TRUE, consider the presence of draw objects anchored to the cell.
+    bool    mbCellDrawObjects = false;
+    /// If TRUE, consider the presence of cell formats.
+    bool    mbCellFormats = false;
+    SCCOL   mnStartCol = SCCOL_MAX;
+    SCROW   mnStartRow = SCROW_MAX;
+    SCCOL   mnEndCol = -1;
+    SCROW   mnEndRow = -1;
+
+    bool anyExtrasWanted() const { return mbCellNotes || mbCellDrawObjects || mbCellFormats; }
+    void resetArea() { mnStartCol = SCCOL_MAX; mnStartRow = SCROW_MAX; mnEndCol = -1; mnEndRow = -1; }
+
+    bool operator==( const ScDataAreaExtras& rOther ) const
+    {
+        // Ignore area range, this is used in ScSortParam::operator==().
+        return mbCellNotes       == rOther.mbCellNotes
+            && mbCellDrawObjects == rOther.mbCellDrawObjects
+            && mbCellFormats     == rOther.mbCellFormats;
+    }
+
+    enum class Clip
+    {
+        None,
+        Col,
+        Row
+    };
+
+    /// Obtain the overall range if area extras are larger.
+    void GetOverallRange( SCCOL& nCol1, SCROW& nRow1, SCCOL& nCol2, SCROW& nRow2, Clip eClip = Clip::None ) const
+    {
+        if (eClip != Clip::Col)
+        {
+            if (nCol1 > mnStartCol)
+                nCol1 = mnStartCol;
+            if (nCol2 < mnEndCol)
+                nCol2 = mnEndCol;
+        }
+        if (eClip != Clip::Row)
+        {
+            if (nRow1 > mnStartRow)
+                nRow1 = mnStartRow;
+            if (nRow2 < mnEndRow)
+                nRow2 = mnEndRow;
+        }
+    }
+
+    /// Set the overall range.
+    void SetOverallRange( SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 )
+    {
+        mnStartCol = nCol1;
+        mnStartRow = nRow1;
+        mnEndCol   = nCol2;
+        mnEndRow   = nRow2;
+    }
+};
+
 struct SC_DLLPUBLIC ScSortParam
 {
     SCCOL       nCol1;
     SCROW       nRow1;
     SCCOL       nCol2;
     SCROW       nRow2;
+    ScDataAreaExtras aDataAreaExtras;
     sal_uInt16  nUserIndex;
     bool        bHasHeader;
     bool        bByRow;
     bool        bCaseSens;
     bool        bNaturalSort;
-    bool        bIncludeComments;
-    bool        bIncludeGraphicObjects;
     bool        bUserDef;
-    bool        bIncludePattern;
     bool        bInplace;
     SCTAB       nDestTab;
     SCCOL       nDestCol;
@@ -88,13 +149,13 @@ struct ReorderParam
      * excludes that row / column.
      */
     ScRange maSortRange;
+    ScDataAreaExtras maDataAreaExtras;
 
     /**
      * List of original column / row positions after reordering.
      */
     std::vector<SCCOLROW> maOrderIndices;
     bool mbByRow;
-    bool mbPattern;
     bool mbHiddenFiltered;
     bool mbUpdateRefs;
     bool mbHasHeaders;
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 4c1a96e7f901..c31fd065cc43 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -599,12 +599,11 @@ public:
 
     bool        ShrinkToUsedDataArea( bool& o_bShrunk, SCCOL& rStartCol, SCROW& rStartRow,
                                       SCCOL& rEndCol, SCROW& rEndRow, bool bColumnsOnly,
-                                      bool bStickyTopRow, bool bStickyLeftCol, bool bConsiderCellNotes,
-                                      bool bConsiderCellDrawObjects, bool bConsiderCellPatterns ) const;
+                                      bool bStickyTopRow, bool bStickyLeftCol,
+                                      ScDataAreaExtras* pDataAreaExtras ) const;
 
-    SCROW       GetLastDataRow( SCCOL nCol1, SCCOL nCol2, SCROW nLastRow, bool bConsiderCellNotes = false,
-                                bool bConsiderCellDrawObjects = false,
-                                bool bConsiderCellPatterns = false ) const;
+    SCROW       GetLastDataRow( SCCOL nCol1, SCCOL nCol2, SCROW nLastRow,
+                                ScDataAreaExtras* pDataAreaExtras = nullptr ) const;
 
     SCSIZE      GetEmptyLinesInBlock( SCCOL nStartCol, SCROW nStartRow,
                                         SCCOL nEndCol, SCROW nEndRow, ScDirection eDir ) const;
@@ -1197,10 +1196,17 @@ private:
         const ScSortParam& rSortParam, SCCOLROW nInd1, SCCOLROW nInd2,
         bool bKeepQuery, bool bUpdateRefs );
     void        QuickSort( ScSortInfoArray*, SCCOLROW nLo, SCCOLROW nHi);
-    void SortReorderByColumn( const ScSortInfoArray* pArray, SCROW nRow1, SCROW nRow2, bool bPattern, ScProgress* pProgress );
-
-    void SortReorderByRow( ScSortInfoArray* pArray, SCCOL nCol1, SCCOL nCol2, ScProgress* pProgress );
-    void SortReorderByRowRefUpdate( ScSortInfoArray* pArray, SCCOL nCol1, SCCOL nCol2, ScProgress* pProgress );
+    void        SortReorderByColumn( const ScSortInfoArray* pArray, SCROW nRow1, SCROW nRow2,
+                                     bool bPattern, ScProgress* pProgress );
+    void        SortReorderAreaExtrasByColumn( const ScSortInfoArray* pArray, SCROW nDataRow1, SCROW nDataRow2,
+                                               const ScDataAreaExtras& rDataAreaExtras, ScProgress* pProgress );
+
+    void        SortReorderByRow( ScSortInfoArray* pArray, SCCOL nCol1, SCCOL nCol2,
+                                  ScProgress* pProgress, bool bOnlyDataAreaExtras );
+    void        SortReorderByRowRefUpdate( ScSortInfoArray* pArray, SCCOL nCol1, SCCOL nCol2,
+                                           ScProgress* pProgress );
+    void        SortReorderAreaExtrasByRow( ScSortInfoArray* pArray, SCCOL nDataCol1, SCCOL nDataCol2,
+                                            const ScDataAreaExtras& rDataAreaExtras, ScProgress* pProgress );
 
     bool        CreateExcelQuery(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, ScQueryParam& rQueryParam);
     bool        CreateStarQuery(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, ScQueryParam& rQueryParam);