Find actual data area inside the main-range...

and trim all ranges to match this actual data area. Don't do
this optimization for COUNTIFS where there is no main-range.
This optimization is also turned off if any of the parameter
ranges are not double-refs.

Benefits in cases like -
=SUMIFS(A:A, B:B, ">=20", C:C, "<=10") and the is data only
in say A1:A10000 and rest are empty. Range trimming in this
case saves lot of execution time and memory (for vConditions
and vRefArrayConditions).

Change-Id: I6b4ad91e23f89dc48603b98000bcef4dbdb03112
Reviewed-on: https://gerrit.libreoffice.org/64657
Tested-by: Jenkins
Reviewed-by: Eike Rathke <erack@redhat.com>
(cherry picked from commit cb52b112c0d44d7a6849f773fd1ee4e863ab91da)
Reviewed-on: https://gerrit.libreoffice.org/64833
Reviewed-by: Dennis Francis <dennis.francis@collabora.com>

7 files changed, 178 insertions, 0 deletions

diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 0a328f001ce4..b1e890a6347c 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -222,6 +222,7 @@ public:
                                 bool bConsiderCellDrawObjects=false ) const;
     bool        GetPrevDataPos(SCROW& rRow) const;
     bool        GetNextDataPos(SCROW& rRow) const;
+    bool        TrimEmptyBlocks(SCROW& rRowStart, SCROW& rRowEnd) const;
     void        FindDataAreaPos(SCROW& rRow, bool bDown) const; // (without Broadcaster)
     void        FindUsed( SCROW nStartRow, SCROW nEndRow, mdds::flat_segment_tree<SCROW, bool>& rUsed ) const;
 
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 04ff9a0c1319..31278f83798b 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -1385,6 +1385,15 @@ public:
                                              SCCOL& rEndCol, SCROW& rEndRow,
                                              bool bIncludeOld, bool bOnlyDown ) const;
 
+    /**
+     * Returns true if there is a non-empty subrange in the range given as input.
+     * In that case it also modifies rRange to largest subrange that does not
+     * have empty col/row inrange-segments in the beginning/end.
+     * It returns false if rRange is completely empty and in this case rRange is
+     * left unmodified.
+    */
+    bool                        GetDataAreaSubrange(ScRange& rRange) const;
+
     SC_DLLPUBLIC bool           GetCellArea( SCTAB nTab, SCCOL& rEndCol, SCROW& rEndRow ) const;
     SC_DLLPUBLIC bool           GetTableArea( SCTAB nTab, SCCOL& rEndCol, SCROW& rEndRow ) const;
     SC_DLLPUBLIC bool           GetPrintArea( SCTAB nTab, SCCOL& rEndCol, SCROW& rEndRow,
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index aae436ea8756..e804a1ca9cc2 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -576,6 +576,8 @@ public:
     void        GetDataArea( SCCOL& rStartCol, SCROW& rStartRow, SCCOL& rEndCol, SCROW& rEndRow,
                              bool bIncludeOld, bool bOnlyDown ) const;
 
+    bool        GetDataAreaSubrange( ScRange& rRange ) const;
+
     bool        ShrinkToUsedDataArea( bool& o_bShrunk, SCCOL& rStartCol, SCROW& rStartRow,
                                       SCCOL& rEndCol, SCROW& rEndRow, bool bColumnsOnly,
                                       bool bStickyTopRow, bool bStickyLeftCol, bool bConsiderCellNotes,
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index d2e81de5de3b..c46f1a70ce8b 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -1405,6 +1405,52 @@ bool ScColumn::GetNextDataPos(SCROW& rRow) const        // greater than rRow
     return true;
 }
 
+bool ScColumn::TrimEmptyBlocks(SCROW& rRowStart, SCROW& rRowEnd) const
+{
+    assert(rRowStart <= rRowEnd);
+    SCROW nRowStartNew = rRowStart, nRowEndNew = rRowEnd;
+
+    // Trim down rRowStart first
+    std::pair<sc::CellStoreType::const_iterator,size_t> aPos = maCells.position(rRowStart);
+    sc::CellStoreType::const_iterator it = aPos.first;
+    if (it == maCells.end())
+        return false;
+
+    if (it->type == sc::element_type_empty)
+    {
+        // This block is empty. Skip ahead to the next block (if exists).
+        nRowStartNew += it->size - aPos.second;
+        if (nRowStartNew > rRowEnd)
+            return false;
+        ++it;
+        if (it == maCells.end())
+            // No more next block.
+            return false;
+    }
+
+    // Trim up rRowEnd next
+    aPos = maCells.position(rRowEnd);
+    it = aPos.first;
+    if (it == maCells.end())
+    {
+        rRowStart = nRowStartNew;
+        return true; // Because trimming of rRowStart is ok
+    }
+
+    if (it->type == sc::element_type_empty)
+    {
+        // rRowEnd cannot be in the first block which is empty !
+        assert(it != maCells.begin());
+        // This block is empty. Skip to the previous block (it exists).
+        nRowEndNew -= aPos.second + 1; // Last row position of the previous block.
+        assert(nRowStartNew <= nRowEndNew);
+    }
+
+    rRowStart = nRowStartNew;
+    rRowEnd = nRowEndNew;
+    return true;
+}
+
 SCROW ScColumn::FindNextVisibleRow(SCROW nRow, bool bForward) const
 {
     if(bForward)
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index 9693edffda3e..dbba8a220748 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -1098,6 +1098,18 @@ void ScDocument::GetDataArea( SCTAB nTab, SCCOL& rStartCol, SCROW& rStartRow,
         maTabs[nTab]->GetDataArea( rStartCol, rStartRow, rEndCol, rEndRow, bIncludeOld, bOnlyDown );
 }
 
+bool ScDocument::GetDataAreaSubrange(ScRange& rRange) const
+{
+    SCTAB nTab = rRange.aStart.Tab();
+    if (nTab != rRange.aEnd.Tab())
+        return true;
+
+    if (ValidTab(nTab) && nTab < static_cast<SCTAB> (maTabs.size()) && maTabs[nTab])
+        return maTabs[nTab]->GetDataAreaSubrange(rRange);
+
+    return true;
+}
+
 void ScDocument::LimitChartArea( SCTAB nTab, SCCOL& rStartCol, SCROW& rStartRow,
                                     SCCOL& rEndCol, SCROW& rEndRow )
 {
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index ede4096b7f3d..cef056314e2e 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -904,6 +904,47 @@ void ScTable::GetDataArea( SCCOL& rStartCol, SCROW& rStartRow, SCCOL& rEndCol, S
     }
 }
 
+bool ScTable::GetDataAreaSubrange( ScRange& rRange ) const
+{
+    SCCOL nCol1 = rRange.aStart.Col(), nCol2 = rRange.aEnd.Col();
+
+    if ( nCol1 >= aCol.size() )
+        return false;
+
+    nCol2 = std::min<SCCOL>( nCol2, aCol.size()-1 );
+
+    SCROW nRow1 = rRange.aStart.Row(), nRow2 = rRange.aEnd.Row();
+
+    SCCOL nFirstNonEmptyCol = -1, nLastNonEmptyCol = -1;
+    SCROW nRowStart = nRow2, nRowEnd = nRow1;
+
+    for ( SCCOL nCol = nCol1; nCol <= nCol2; ++nCol )
+    {
+        SCROW nRowStartThis = nRow1, nRowEndThis = nRow2;
+        bool bTrimmed = aCol[nCol].TrimEmptyBlocks(nRowStartThis, nRowEndThis);
+        if ( bTrimmed )
+        {
+            if ( nFirstNonEmptyCol == -1 )
+                nFirstNonEmptyCol = nCol;
+            nLastNonEmptyCol = nCol;
+
+            nRowStart = std::min<SCROW>(nRowStart, nRowStartThis);
+            nRowEnd = std::max<SCROW>(nRowEnd, nRowEndThis);
+        }
+    }
+
+    if ( nFirstNonEmptyCol == -1 )
+        return false;
+
+    assert(nFirstNonEmptyCol <= nLastNonEmptyCol);
+    assert(nRowStart <= nRowEnd);
+
+    rRange.aStart.Set(nFirstNonEmptyCol, nRowStart, rRange.aStart.Tab());
+    rRange.aEnd.Set(nLastNonEmptyCol, nRowEnd, rRange.aEnd.Tab());
+
+    return true;
+}
+
 bool ScTable::ShrinkToUsedDataArea( bool& o_bShrunk, SCCOL& rStartCol, SCROW& rStartRow,
         SCCOL& rEndCol, SCROW& rEndRow, bool bColumnsOnly, bool bStickyTopRow, bool bStickyLeftCol,
         bool bConsiderCellNotes, bool bConsiderCellDrawObjects ) const
diff --git a/sc/source/core/tool/interpr1.cxx b/sc/source/core/tool/interpr1.cxx
index 9476c6407231..d7279c1188a7 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -5842,6 +5842,55 @@ void ScInterpreter::IterateParametersIfs( double(*ResultFunc)( const sc::ParamIf
     // with a single InterpretTail() call it results in evaluation of all the cells in the
     // matrix formula.
     vConditions.clear();
+
+    SCCOL nStartColDiff = 0;
+    SCCOL nEndColDiff = 0;
+    SCROW nStartRowDiff = 0;
+    SCROW nEndRowDiff = 0;
+    bool bRangeReduce = false;
+
+    // Range-reduce optimization
+    if (nParamCount % 2) // Not COUNTIFS
+    {
+        bool bHasDoubleRefCriteriaRanges = true;
+        // Do not attempt main-range reduce if any of the criteria-ranges are not double-refs.
+        for (sal_uInt16 nParamIdx = 2; nParamIdx < nParamCount; nParamIdx += 2 )
+        {
+            const formula::FormulaToken* pCriteriaRangeToken = pStack[ sp-nParamIdx ];
+            if (pCriteriaRangeToken->GetType() != svDoubleRef )
+            {
+                bHasDoubleRefCriteriaRanges = false;
+                break;
+            }
+        }
+
+        // Probe the main range token, and try if we can shrink the range without altering results.
+        const formula::FormulaToken* pMainRangeToken = pStack[ sp-nParamCount ];
+        if (pMainRangeToken->GetType() == svDoubleRef && bHasDoubleRefCriteriaRanges)
+        {
+            const ScComplexRefData* pRefData = pMainRangeToken->GetDoubleRef();
+            if (!pRefData->IsDeleted())
+            {
+                ScRange aMainRange, aSubRange;
+                DoubleRefToRange( *pRefData, aMainRange);
+
+                if (aMainRange.aStart.Tab() == aMainRange.aEnd.Tab())
+                {
+                    // Shrink the range to actual data content.
+                    aSubRange = aMainRange;
+                    pDok->GetDataAreaSubrange(aSubRange);
+
+                    nStartColDiff = aSubRange.aStart.Col() - aMainRange.aStart.Col();
+                    nStartRowDiff = aSubRange.aStart.Row() - aMainRange.aStart.Row();
+
+                    nEndColDiff = aSubRange.aEnd.Col() - aMainRange.aEnd.Col();
+                    nEndRowDiff = aSubRange.aEnd.Row() - aMainRange.aEnd.Row();
+                    bRangeReduce = nStartColDiff || nStartRowDiff || nEndColDiff || nEndRowDiff;
+                }
+            }
+        }
+    }
+
     double fVal = 0.0;
     SCCOL nDimensionCols = 0;
     SCROW nDimensionRows = 0;
@@ -6024,6 +6073,15 @@ void ScInterpreter::IterateParametersIfs( double(*ResultFunc)( const sc::ParamIf
                 return;
             }
 
+            if (bRangeReduce)
+            {
+                nCol1 += nStartColDiff;
+                nRow1 += nStartRowDiff;
+
+                nCol2 += nEndColDiff;
+                nRow2 += nEndRowDiff;
+            }
+
             // All reference ranges must be of same dimension and size.
             if (!nDimensionCols)
                 nDimensionCols = nCol2 - nCol1 + 1;
@@ -6262,6 +6320,15 @@ void ScInterpreter::IterateParametersIfs( double(*ResultFunc)( const sc::ParamIf
                 return;
             }
 
+            if (bRangeReduce)
+            {
+                nMainCol1 += nStartColDiff;
+                nMainRow1 += nStartRowDiff;
+
+                nMainCol2 += nEndColDiff;
+                nMainRow2 += nEndRowDiff;
+            }
+
             // All reference ranges must be of same dimension and size.
             if ((nDimensionCols != (nMainCol2 - nMainCol1 + 1)) || (nDimensionRows != (nMainRow2 - nMainRow1 + 1)))
             {