optimize ScTabView::SkipCursorVertical() for many rows

Just like already done for RowHidden(), avoid repeated calls
to HasAttrib() and IsVerOverlapped() that would return the same
value because it's the same underlying attribute range.

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

8 files changed, 169 insertions, 34 deletions

diff --git a/sc/inc/attarray.hxx b/sc/inc/attarray.hxx
index f55a4ee8206e..34d1403bcc91 100644
--- a/sc/inc/attarray.hxx
+++ b/sc/inc/attarray.hxx
@@ -182,6 +182,7 @@ public:
     bool    Search( SCROW nRow, SCSIZE& nIndex ) const;
 
     bool    HasAttrib( SCROW nRow1, SCROW nRow2, HasAttrFlags nMask ) const;
+    bool    HasAttrib( SCROW nRow, HasAttrFlags nMask, SCROW* nStartRow = nullptr, SCROW* nEndRow = nullptr ) const;
     bool    IsMerged( SCROW nRow ) const;
     bool    ExtendMerge( SCCOL nThisCol, SCROW nStartRow, SCROW nEndRow,
                                 SCCOL& rPaintCol, SCROW& rPaintRow,
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 69b80ed00830..6cb2311de112 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -133,6 +133,11 @@ public:
     {
         return static_cast<const T&>(GetAttr(nRow, sal_uInt16(nWhich)));
     }
+    const SfxPoolItem&      GetAttr( SCROW nRow, sal_uInt16 nWhich, SCROW& nStartRow, SCROW& nEndRow ) const;
+    template<class T> const T&  GetAttr( SCROW nRow, TypedWhichId<T> nWhich, SCROW& nStartRow, SCROW& nEndRow ) const
+    {
+        return static_cast<const T&>(GetAttr(nRow, sal_uInt16(nWhich), nStartRow, nEndRow));
+    }
 
     const ScPatternAttr*    GetPattern( SCROW nRow ) const;
     const ScPatternAttr*    GetMostUsedPattern( SCROW nStartRow, SCROW nEndRow ) const;
@@ -153,6 +158,7 @@ public:
     void        ApplyStyleArea( SCROW nStartRow, SCROW nEndRow, const ScStyleSheet& rStyle );
 
     bool        HasAttrib( SCROW nRow1, SCROW nRow2, HasAttrFlags nMask ) const;
+    bool        HasAttrib( SCROW nRow, HasAttrFlags nMask, SCROW* nStartRow = nullptr, SCROW* nEndRow = nullptr ) const;
 
     void        ClearSelectionItems( const sal_uInt16* pWhich, const ScMarkData& rMark, SCCOL nCol );
     void        ChangeSelectionIndent( bool bIncrement, const ScMarkData& rMark, SCCOL nCol );
@@ -881,6 +887,11 @@ inline bool ScColumnData::HasAttrib( SCROW nRow1, SCROW nRow2, HasAttrFlags nMas
     return pAttrArray->HasAttrib( nRow1, nRow2, nMask );
 }
 
+inline bool ScColumnData::HasAttrib( SCROW nRow, HasAttrFlags nMask, SCROW* nStartRow, SCROW* nEndRow ) const
+{
+    return pAttrArray->HasAttrib( nRow, nMask, nStartRow, nEndRow );
+}
+
 inline bool ScColumn::ExtendMerge( SCCOL nThisCol, SCROW nStartRow, SCROW nEndRow,
                             SCCOL& rPaintCol, SCROW& rPaintRow,
                             bool bRefresh )
@@ -916,6 +927,11 @@ inline const SfxPoolItem& ScColumnData::GetAttr( SCROW nRow, sal_uInt16 nWhich )
     return pAttrArray->GetPattern( nRow )->GetItemSet().Get(nWhich);
 }
 
+inline const SfxPoolItem& ScColumnData::GetAttr( SCROW nRow, sal_uInt16 nWhich, SCROW& nStartRow, SCROW& nEndRow ) const
+{
+    return pAttrArray->GetPatternRange( nStartRow, nEndRow, nRow )->GetItemSet().Get(nWhich);
+}
+
 inline sal_uInt32 ScColumnData::GetNumberFormat( const ScInterpreterContext& rContext, SCROW nRow ) const
 {
     return pAttrArray->GetPattern( nRow )->GetNumberFormat( rContext.GetFormatTable() );
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 44cedc482e01..963b4d48edad 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -1308,11 +1308,14 @@ public:
 
     void            SkipOverlapped( SCCOL& rCol, SCROW& rRow, SCTAB nTab ) const;
     bool            IsHorOverlapped( SCCOL nCol, SCROW nRow, SCTAB nTab ) const;
-    bool            IsVerOverlapped( SCCOL nCol, SCROW nRow, SCTAB nTab ) const;
+    bool            IsVerOverlapped( SCCOL nCol, SCROW nRow, SCTAB nTab,
+                                     SCROW* nStartRow = nullptr, SCROW* nEndRow = nullptr ) const;
 
     SC_DLLPUBLIC bool HasAttrib( SCCOL nCol1, SCROW nRow1, SCTAB nTab1,
                                  SCCOL nCol2, SCROW nRow2, SCTAB nTab2, HasAttrFlags nMask ) const;
     SC_DLLPUBLIC bool HasAttrib( const ScRange& rRange, HasAttrFlags nMask ) const;
+    bool              HasAttrib( SCCOL nCol, SCROW nRow, SCTAB nTab, HasAttrFlags nMask,
+                                 SCROW* nStartRow = nullptr, SCROW* nEndRow = nullptr ) const;
 
     SC_DLLPUBLIC void GetBorderLines( SCCOL nCol, SCROW nRow, SCTAB nTab,
                                     const ::editeng::SvxBorderLine** ppLeft,
@@ -1747,6 +1750,13 @@ public:
     {
         return static_cast<const T*>(GetAttr(nCol, nRow, nTab, sal_uInt16(nWhich)));
     }
+    SC_DLLPUBLIC const SfxPoolItem*         GetAttr( SCCOL nCol, SCROW nRow, SCTAB nTab, sal_uInt16 nWhich,
+                                                     SCROW& nStartRow, SCROW& nEndRow ) const;
+    template<class T> const T*              GetAttr( SCCOL nCol, SCROW nRow, SCTAB nTab, TypedWhichId<T> nWhich,
+                                                     SCROW& nStartRow, SCROW& nEndRow ) const
+    {
+        return static_cast<const T*>(GetAttr(nCol, nRow, nTab, sal_uInt16(nWhich), nStartRow, nEndRow));
+    }
     SC_DLLPUBLIC const SfxPoolItem*         GetAttr( const ScAddress& rPos, sal_uInt16 nWhich ) const;
     template<class T> const T*              GetAttr( const ScAddress& rPos, TypedWhichId<T> nWhich ) const
     {
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 7405d5fb90f3..bcde540de65b 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -694,6 +694,8 @@ public:
 
     bool        HasAttrib( SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, HasAttrFlags nMask ) const;
     bool        HasAttribSelection( const ScMarkData& rMark, HasAttrFlags nMask ) const;
+    bool        HasAttrib( SCCOL nCol, SCROW nRow, HasAttrFlags nMask,
+                           SCROW* nStartRow = nullptr, SCROW* nEndRow = nullptr ) const;
     bool IsMerged( SCCOL nCol, SCROW nRow ) const;
     bool        ExtendMerge( SCCOL nStartCol, SCROW nStartRow,
                                 SCCOL& rEndCol, SCROW& rEndRow,
@@ -705,6 +707,11 @@ public:
     {
         return static_cast<const T*>(GetAttr(nCol, nRow, sal_uInt16(nWhich)));
     }
+    const SfxPoolItem*      GetAttr( SCCOL nCol, SCROW nRow, sal_uInt16 nWhich, SCROW& nStartRow, SCROW& nEndRow ) const;
+    template<class T> const T* GetAttr( SCCOL nCol, SCROW nRow, TypedWhichId<T> nWhich, SCROW& nStartRow, SCROW& nEndRow ) const
+    {
+        return static_cast<const T*>(GetAttr(nCol, nRow, sal_uInt16(nWhich), nStartRow, nEndRow));
+    }
     const ScPatternAttr*    GetPattern( SCCOL nCol, SCROW nRow ) const;
     const ScPatternAttr*    GetMostUsedPattern( SCCOL nCol, SCROW nStartRow, SCROW nEndRow ) const;
 
diff --git a/sc/source/core/data/attarray.cxx b/sc/source/core/data/attarray.cxx
index 599a80251602..5af0e3b3609d 100644
--- a/sc/source/core/data/attarray.cxx
+++ b/sc/source/core/data/attarray.cxx
@@ -1420,6 +1420,27 @@ bool ScAttrArray::HasAttrib( SCROW nRow1, SCROW nRow2, HasAttrFlags nMask ) cons
     return bFound;
 }
 
+bool ScAttrArray::HasAttrib( SCROW nRow, HasAttrFlags nMask, SCROW* nStartRow, SCROW* nEndRow ) const
+{
+    if (mvData.empty())
+    {
+        if( nStartRow )
+            *nStartRow = 0;
+        if( nEndRow )
+            *nEndRow = rDocument.MaxRow();
+        return HasAttrib_Impl(rDocument.GetDefPattern(), nMask, 0, rDocument.MaxRow(), 0);
+    }
+
+    SCSIZE nIndex;
+    Search( nRow, nIndex );
+    if( nStartRow )
+        *nStartRow = nIndex > 0 ? mvData[nIndex-1].nEndRow+1 : 0;
+    if( nEndRow )
+        *nEndRow = mvData[nIndex].nEndRow;
+    const ScPatternAttr* pPattern = mvData[nIndex].pPattern;
+    return HasAttrib_Impl(pPattern, nMask, nRow, nRow, nIndex);
+}
+
 bool ScAttrArray::IsMerged( SCROW nRow ) const
 {
     if ( !mvData.empty() )
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index 361a51abc9bb..ec39169c9192 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -4737,6 +4737,21 @@ const SfxPoolItem* ScDocument::GetAttr( SCCOL nCol, SCROW nRow, SCTAB nTab, sal_
     return &mxPoolHelper->GetDocPool()->GetDefaultItem( nWhich );
 }
 
+const SfxPoolItem* ScDocument::GetAttr( SCCOL nCol, SCROW nRow, SCTAB nTab, sal_uInt16 nWhich, SCROW& nStartRow, SCROW& nEndRow ) const
+{
+    if ( ValidTab(nTab) && nTab < static_cast<SCTAB>(maTabs.size()) && maTabs[nTab] )
+    {
+        const SfxPoolItem* pTemp = maTabs[nTab]->GetAttr( nCol, nRow, nWhich, nStartRow, nEndRow );
+        if (pTemp)
+            return pTemp;
+        else
+        {
+            OSL_FAIL( "Attribute Null" );
+        }
+    }
+    return &mxPoolHelper->GetDocPool()->GetDefaultItem( nWhich );
+}
+
 const SfxPoolItem* ScDocument::GetAttr( const ScAddress& rPos, sal_uInt16 nWhich ) const
 {
     return GetAttr(rPos.Col(), rPos.Row(), rPos.Tab(), nWhich);
@@ -5177,16 +5192,13 @@ void ScDocument::GetSelectionFrame( const ScMarkData& rMark,
     rLineInner.SetValid( SvxBoxInfoItemValidFlags::VERT,   ( aFlags.nVert != SC_LINE_DONTCARE ) );
 }
 
-bool ScDocument::HasAttrib( SCCOL nCol1, SCROW nRow1, SCTAB nTab1,
-                            SCCOL nCol2, SCROW nRow2, SCTAB nTab2, HasAttrFlags nMask ) const
+static HasAttrFlags OptimizeHasAttrib( HasAttrFlags nMask, ScDocumentPool* pPool )
 {
     if ( nMask & HasAttrFlags::Rotate )
     {
         //  Is attribute used in document?
         //  (as in fillinfo)
 
-        ScDocumentPool* pPool = mxPoolHelper->GetDocPool();
-
         bool bAnyItem = false;
         for (const SfxPoolItem* pItem : pPool->GetItemSurrogates(ATTR_ROTATE_VALUE))
         {
@@ -5202,12 +5214,18 @@ bool ScDocument::HasAttrib( SCCOL nCol1, SCROW nRow1, SCTAB nTab1,
         if (!bAnyItem)
             nMask &= ~HasAttrFlags::Rotate;
     }
+    return nMask;
+}
+
+bool ScDocument::HasAttrib( SCCOL nCol1, SCROW nRow1, SCTAB nTab1,
+                            SCCOL nCol2, SCROW nRow2, SCTAB nTab2, HasAttrFlags nMask ) const
+{
+    nMask = OptimizeHasAttrib( nMask, mxPoolHelper->GetDocPool());
 
     if (nMask == HasAttrFlags::NONE)
         return false;
 
-    bool bFound = false;
-    for (SCTAB i=nTab1; i<=nTab2 && !bFound && i < static_cast<SCTAB>(maTabs.size()); i++)
+    for (SCTAB i=nTab1; i<=nTab2 && i < static_cast<SCTAB>(maTabs.size()); i++)
         if (maTabs[i])
         {
             if ( nMask & HasAttrFlags::RightOrCenter )
@@ -5217,14 +5235,46 @@ bool ScDocument::HasAttrib( SCCOL nCol1, SCROW nRow1, SCTAB nTab1,
                 //  That way, ScAttrArray::HasAttrib doesn't have to handle RTL sheets.
 
                 if ( IsLayoutRTL(i) )
-                    bFound = true;
+                    return true;
             }
 
-            if ( !bFound )
-                bFound = maTabs[i]->HasAttrib( nCol1, nRow1, nCol2, nRow2, nMask );
+            if( maTabs[i]->HasAttrib( nCol1, nRow1, nCol2, nRow2, nMask ))
+                return true;
         }
 
-    return bFound;
+    return false;
+}
+
+bool ScDocument::HasAttrib( SCCOL nCol, SCROW nRow, SCTAB nTab, HasAttrFlags nMask, SCROW* nStartRow, SCROW* nEndRow ) const
+{
+    nMask = OptimizeHasAttrib( nMask, mxPoolHelper->GetDocPool());
+
+    if (nMask == HasAttrFlags::NONE || nTab >= static_cast<SCTAB>(maTabs.size()))
+    {
+        if( nStartRow )
+            *nStartRow = 0;
+        if( nEndRow )
+            *nEndRow = MaxRow();
+        return false;
+    }
+
+    if ( nMask & HasAttrFlags::RightOrCenter )
+    {
+        //  On a RTL sheet, don't start to look for the default left value
+        //  (which is then logically right), instead always assume true.
+        //  That way, ScAttrArray::HasAttrib doesn't have to handle RTL sheets.
+
+        if ( IsLayoutRTL(nTab) )
+        {
+            if( nStartRow )
+                *nStartRow = 0;
+            if( nEndRow )
+                *nEndRow = MaxRow();
+            return true;
+        }
+    }
+
+    return maTabs[nTab]->HasAttrib( nCol, nRow, nMask, nStartRow, nEndRow );
 }
 
 bool ScDocument::HasAttrib( const ScRange& rRange, HasAttrFlags nMask ) const
@@ -5738,9 +5788,11 @@ bool ScDocument::IsHorOverlapped( SCCOL nCol, SCROW nRow, SCTAB nTab ) const
     }
 }
 
-bool ScDocument::IsVerOverlapped( SCCOL nCol, SCROW nRow, SCTAB nTab ) const
+bool ScDocument::IsVerOverlapped( SCCOL nCol, SCROW nRow, SCTAB nTab, SCROW* nStartRow, SCROW* nEndRow ) const
 {
-    const ScMergeFlagAttr* pAttr = GetAttr( nCol, nRow, nTab, ATTR_MERGE_FLAG );
+    SCROW dummy;
+    const ScMergeFlagAttr* pAttr = GetAttr( nCol, nRow, nTab, ATTR_MERGE_FLAG,
+                                            nStartRow ? *nStartRow : dummy, nEndRow ? *nEndRow : dummy );
     if (pAttr)
         return pAttr->IsVerOverlapped();
     else
diff --git a/sc/source/core/data/table2.cxx b/sc/source/core/data/table2.cxx
index bd3fd74200c2..f606fdd44902 100644
--- a/sc/source/core/data/table2.cxx
+++ b/sc/source/core/data/table2.cxx
@@ -2174,6 +2174,15 @@ const SfxPoolItem* ScTable::GetAttr( SCCOL nCol, SCROW nRow, sal_uInt16 nWhich )
     return &aDefaultColData.GetAttr( nRow, nWhich );
 }
 
+const SfxPoolItem* ScTable::GetAttr( SCCOL nCol, SCROW nRow, sal_uInt16 nWhich, SCROW& nStartRow, SCROW& nEndRow ) const
+{
+    if (!ValidColRow(nCol, nRow))
+        return nullptr;
+    if (nCol < GetAllocatedColumnsCount())
+        return &aCol[nCol].GetAttr( nRow, nWhich, nStartRow, nEndRow );
+    return &aDefaultColData.GetAttr( nRow, nWhich, nStartRow, nEndRow );
+}
+
 sal_uInt32 ScTable::GetNumberFormat( const ScInterpreterContext& rContext, const ScAddress& rPos ) const
 {
     if (ValidColRow(rPos.Col(), rPos.Row()))
@@ -2235,6 +2244,13 @@ bool ScTable::HasAttrib( SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, Has
     return false;
 }
 
+bool ScTable::HasAttrib( SCCOL nCol, SCROW nRow, HasAttrFlags nMask, SCROW* nStartRow, SCROW* nEndRow ) const
+{
+    if( nCol < aCol.size())
+        return aCol[nCol].HasAttrib( nRow, nMask, nStartRow, nEndRow );
+    return aDefaultColData.HasAttrib( nRow, nMask, nStartRow, nEndRow );
+}
+
 bool ScTable::HasAttribSelection( const ScMarkData& rMark, HasAttrFlags nMask ) const
 {
     std::vector<sc::ColRowSpan> aSpans = rMark.GetMarkedColSpans();
diff --git a/sc/source/ui/view/tabview2.cxx b/sc/source/ui/view/tabview2.cxx
index 111b27477247..49167895a182 100644
--- a/sc/source/ui/view/tabview2.cxx
+++ b/sc/source/ui/view/tabview2.cxx
@@ -739,7 +739,8 @@ void ScTabView::SkipCursorHorizontal(SCCOL& rCurX, SCROW& rCurY, SCCOL nOldX, SC
 
     bool bSkipCell = false;
     bool bHFlip = false;
-    auto nMaxCol = rDoc.MaxCol();
+    // search also the first unallocated column (all unallocated columns share a set of attrs)
+    SCCOL nMaxCol = std::min<SCCOL>( rDoc.GetAllocatedColumnsCount(nTab) + 1, rDoc.MaxCol());
     do
     {
         bSkipCell = rDoc.ColHidden(rCurX, nTab) || rDoc.IsHorOverlapped(rCurX, rCurY, nTab);
@@ -799,20 +800,41 @@ void ScTabView::SkipCursorVertical(SCCOL& rCurX, SCROW& rCurY, SCROW nOldY, SCRO
 
     bool bSkipCell = false;
     bool bVFlip = false;
+    // Avoid repeated calls to RowHidden(), IsVerOverlapped() and HasAttrib().
+    SCROW nFirstSameHiddenRow = -1;
+    SCROW nLastSameHiddenRow = -1;
+    bool bRowHidden = false;
+    SCROW nFirstSameIsVerOverlapped = -1;
+    SCROW nLastSameIsVerOverlapped = -1;
+    bool bIsVerOverlapped = false;
+    SCROW nFirstSameHasAttribRow = -1;
+    SCROW nLastSameHasAttribRow = -1;
+    bool bHasAttribProtected = false;
     do
     {
-        SCROW nFirstHiddenRow = -1;
-        SCROW nLastHiddenRow = -1;
-        bSkipCell = rDoc.RowHidden(rCurY, nTab, &nFirstHiddenRow, &nLastHiddenRow);
-        if (!bSkipCell)
+        if( rCurY < nFirstSameHiddenRow || rCurY > nLastSameHiddenRow )
+            bRowHidden = rDoc.RowHidden(rCurY, nTab, &nFirstSameHiddenRow, &nLastSameHiddenRow);
+        bSkipCell = bRowHidden;
+        if( !bSkipCell )
         {
-            nFirstHiddenRow = nLastHiddenRow = -1;
-            bSkipCell = rDoc.IsVerOverlapped( rCurX, rCurY, nTab );
+            if( rCurY < nFirstSameIsVerOverlapped || rCurY > nLastSameIsVerOverlapped )
+                bIsVerOverlapped = rDoc.IsVerOverlapped(rCurX, rCurY, nTab, &nFirstSameIsVerOverlapped, &nLastSameIsVerOverlapped);
+            bSkipCell = bIsVerOverlapped;
         }
         if (bSkipProtected && !bSkipCell)
-            bSkipCell = rDoc.HasAttrib(rCurX, rCurY, nTab, rCurX, rCurY, nTab, HasAttrFlags::Protected);
+        {
+            if( rCurY < nFirstSameHasAttribRow || rCurY > nLastSameHasAttribRow )
+                bHasAttribProtected = rDoc.HasAttrib(rCurX, rCurY, nTab, HasAttrFlags::Protected,
+                                                     &nFirstSameHasAttribRow, &nLastSameHasAttribRow);
+            bSkipCell = bHasAttribProtected;
+        }
         if (bSkipUnprotected && !bSkipCell)
-            bSkipCell = !rDoc.HasAttrib(rCurX, rCurY, nTab, rCurX, rCurY, nTab, HasAttrFlags::Protected);
+        {
+            if( rCurY < nFirstSameHasAttribRow || rCurY > nLastSameHasAttribRow )
+                bHasAttribProtected = rDoc.HasAttrib(rCurX, rCurY, nTab, HasAttrFlags::Protected,
+                                                     &nFirstSameHasAttribRow, &nLastSameHasAttribRow);
+            bSkipCell = !bHasAttribProtected;
+        }
 
         if (bSkipCell)
         {
@@ -834,20 +856,10 @@ void ScTabView::SkipCursorVertical(SCCOL& rCurX, SCROW& rCurY, SCROW nOldY, SCRO
                 }
             }
             else
-            {
-                // nFirstRow/nLastRow are set only if the row is hidden, in which case we always skip,
-                // so as an optimization skip to the first row after the hidden range
                 if (nMovY > 0)
-                    if (nLastHiddenRow >= 0)
-                        rCurY = std::min<SCROW>(nLastHiddenRow + 1, rDoc.MaxRow());
-                    else
-                        ++rCurY;
+                    ++rCurY;
                 else
-                    if (nFirstHiddenRow >= 0)
-                        rCurY = std::max<SCROW>(nFirstHiddenRow - 1, 0);
-                    else
-                        --rCurY;
-            }
+                    --rCurY;
         }
     }
     while (bSkipCell);