Flatten ScRangeList::Join() and ScRangePairList::Join() recursion

 This is a combination of 2 commits.

Flatten ScRangeList::Join() recursion

Joining an existing list of identical ranges could end up in a
very deep (but not infinite) recursion which could lead to stack
exhaustion. Recursion is unnecessary if we re-enter the loop with
the picked range. Continuing the loop as it was done after
recursion isn't necessary either, to the contrary, as long as
there is one join try the entire list again.

Commit f6eefd96cb16a9b5607fe59bdbf9b1121c9b56e8 pointed this out
as the UBSan build runs with ulimit -s 8192

Reviewed-on: https://gerrit.libreoffice.org/48360
Reviewed-by: Eike Rathke <erack@redhat.com>
Tested-by: Jenkins <ci@libreoffice.org>
(cherry picked from commit 03f429665b4d57f63b8e2862a55e5c4273bc7a2b)

Flatten ScRangePairList::Join() recursion

Similar to ScRangeList::Join() done before.

Reviewed-on: https://gerrit.libreoffice.org/48361
Reviewed-by: Eike Rathke <erack@redhat.com>
Tested-by: Jenkins <ci@libreoffice.org>
(cherry picked from commit 73049e5dbf9430df077dd26bed9d01435f745544)

e513b4c72bc211c196e13761b63446174321a389

Change-Id: Ibbc542fc8ae6d1509744aa731771eb6e32a38841
Reviewed-on: https://gerrit.libreoffice.org/48404
Tested-by: Jenkins <ci@libreoffice.org>
Reviewed-by: Caolán McNamara <caolanm@redhat.com>
Tested-by: Caolán McNamara <caolanm@redhat.com>

1 files changed, 89 insertions, 75 deletions

diff --git a/sc/source/core/tool/rangelst.cxx b/sc/source/core/tool/rangelst.cxx
index ae9ebd2b5d67..cb042885a160 100644
--- a/sc/source/core/tool/rangelst.cxx
+++ b/sc/source/core/tool/rangelst.cxx
@@ -207,12 +207,6 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
         Append( r );
         return ;
     }
-    SCCOL nCol1 = r.aStart.Col();
-    SCROW nRow1 = r.aStart.Row();
-    SCTAB nTab1 = r.aStart.Tab();
-    SCCOL nCol2 = r.aEnd.Col();
-    SCROW nRow2 = r.aEnd.Row();
-    SCTAB nTab2 = r.aEnd.Tab();
 
     // One common usage is to join ranges that actually are top to bottom
     // appends but the caller doesn't exactly know about it, e.g. when invoked
@@ -225,6 +219,7 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
 
     if (!bIsInList)
     {
+        const SCROW nRow1 = r.aStart.Row();
         if (nRow1 > mnMaxRowUsed + 1)
         {
             Append( r );
@@ -235,9 +230,10 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
             // Check if we can simply enlarge the last range.
             ScRange* p = maRanges.back();
             if (p->aEnd.Row() + 1 == nRow1 &&
-                    p->aStart.Col() == nCol1 && p->aEnd.Col() == nCol2 &&
-                    p->aStart.Tab() == nTab1 && p->aEnd.Tab() == nTab2)
+                    p->aStart.Col() == r.aStart.Col() && p->aEnd.Col() == r.aEnd.Col() &&
+                    p->aStart.Tab() == r.aStart.Tab() && p->aEnd.Tab() == r.aEnd.Tab())
             {
+                const SCROW nRow2 = r.aEnd.Row();
                 p->aEnd.SetRow( nRow2 );
                 mnMaxRowUsed = nRow2;
                 return;
@@ -245,43 +241,45 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
         }
     }
 
-    ScRange* pOver = const_cast<ScRange*>(&r);     // nasty but true when bInList
-    size_t nOldPos = 0;
-    if ( bIsInList )
-    {
-        // Find the current position of this range.
-        for ( size_t i = 0, nRanges = maRanges.size(); i < nRanges; ++i )
-        {
-            if ( maRanges[i] == pOver )
-            {
-                nOldPos = i;
-                break;
-            }
-        }
-    }
     bool bJoinedInput = false;
+    const ScRange* pOver = &r;
+
+Label_Range_Join:
 
-    // We need to query the size of the container dynamically since its size
-    // may change during the loop.
-    for ( size_t i = 0; i < maRanges.size() && pOver; ++i )
+    assert(pOver);
+    const SCCOL nCol1 = pOver->aStart.Col();
+    const SCROW nRow1 = pOver->aStart.Row();
+    const SCCOL nTab1 = pOver->aStart.Tab();
+    const SCCOL nCol2 = pOver->aEnd.Col();
+    const SCROW nRow2 = pOver->aEnd.Row();
+    const SCCOL nTab2 = pOver->aEnd.Tab();
+
+    size_t nOverPos = std::numeric_limits<size_t>::max();
+    for (size_t i = 0; i < maRanges.size(); ++i)
     {
         ScRange* p = maRanges[i];
         if ( p == pOver )
+        {
+            nOverPos = i;
             continue;           // the same one, continue with the next
+        }
         bool bJoined = false;
-        if ( p->In( r ) )
-        {   //range r included in or identical to range p
+        if ( p->In( *pOver ) )
+        {   // range pOver included in or identical to range p
+            // XXX if we never used Append() before Join() we could remove
+            // pOver and end processing, but it is not guranteed and there can
+            // be duplicates.
             if ( bIsInList )
-                bJoined = true;     // do away with range r
+                bJoined = true;     // do away with range pOver
             else
             {   // that was all then
-                bJoinedInput = true;    // don't attach
+                bJoinedInput = true;    // don't append
                 break;  // for
             }
         }
-        else if ( r.In( *p ) )
-        {   // range p included in range r, make r the new range
-            *p = r;
+        else if ( pOver->In( *p ) )
+        {   // range p included in range pOver, make pOver the new range
+            *p = *pOver;
             bJoined = true;
         }
         if ( !bJoined && p->aStart.Tab() == nTab1 && p->aEnd.Tab() == nTab2 )
@@ -320,15 +318,25 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
         if ( bJoined )
         {
             if ( bIsInList )
-            {   // delete range within the list
-                Remove(nOldPos);
-                i--;
-                pOver = nullptr;
-                if ( nOldPos )
-                    nOldPos--;          // configure seek correctly
+            {   // delete range pOver within the list
+                if (nOverPos != std::numeric_limits<size_t>::max())
+                    Remove(nOverPos);
+                else
+                {
+                    for (size_t nOver = 0, nRanges = maRanges.size(); nOver < nRanges; ++nOver)
+                    {
+                        if (maRanges[nOver] == pOver)
+                        {
+                            Remove(nOver);
+                            break;
+                        }
+                    }
+                }
             }
             bJoinedInput = true;
-            Join( *p, true );           // recursive!
+            pOver = p;
+            bIsInList = true;
+            goto Label_Range_Join;
         }
     }
     if (  !bIsInList && !bJoinedInput )
@@ -1432,53 +1440,49 @@ void ScRangePairList::Join( const ScRangePair& r, bool bIsInList )
         Append( r );
         return ;
     }
-    const ScRange& r1 = r.GetRange(0);
-    const ScRange& r2 = r.GetRange(1);
-    SCCOL nCol1 = r1.aStart.Col();
-    SCROW nRow1 = r1.aStart.Row();
-    SCTAB nTab1 = r1.aStart.Tab();
-    SCCOL nCol2 = r1.aEnd.Col();
-    SCROW nRow2 = r1.aEnd.Row();
-    SCTAB nTab2 = r1.aEnd.Tab();
-    ScRangePair* pOver = const_cast<ScRangePair*>(&r);     // nasty but true when bInList
-    size_t nOldPos = 0;
-    if ( bIsInList )
-    {
-        // Find the current position of this range.
-        for ( size_t i = 0, nPairs = maPairs.size(); i < nPairs; ++i )
-        {
-            if ( maPairs[i] == pOver )
-            {
-                nOldPos = i;
-                break;
-            }
-        }
-    }
-    bool bJoinedInput = false;
 
-    for ( size_t i = 0; i < maPairs.size() && pOver; ++i )
+    bool bJoinedInput = false;
+    const ScRangePair* pOver = &r;
+
+Label_RangePair_Join:
+
+    assert(pOver);
+    const ScRange& r1 = pOver->GetRange(0);
+    const ScRange& r2 = pOver->GetRange(1);
+    const SCCOL nCol1 = r1.aStart.Col();
+    const SCROW nRow1 = r1.aStart.Row();
+    const SCTAB nTab1 = r1.aStart.Tab();
+    const SCCOL nCol2 = r1.aEnd.Col();
+    const SCROW nRow2 = r1.aEnd.Row();
+    const SCTAB nTab2 = r1.aEnd.Tab();
+
+    size_t nOverPos = std::numeric_limits<size_t>::max();
+    for (size_t i = 0; i < maPairs.size(); ++i)
     {
         ScRangePair* p = maPairs[ i ];
         if ( p == pOver )
+        {
+            nOverPos = i;
             continue;           // the same one, continue with the next
+        }
         bool bJoined = false;
         ScRange& rp1 = p->GetRange(0);
         ScRange& rp2 = p->GetRange(1);
         if ( rp2 == r2 )
         {   // only if Range2 is equal
             if ( rp1.In( r1 ) )
-            {   // RangePair r included in or identical to RangePair p
+            {   // RangePair pOver included in or identical to RangePair p
                 if ( bIsInList )
-                    bJoined = true;     // do away with RangePair r
+                    bJoined = true;     // do away with RangePair pOver
                 else
                 {   // that was all then
-                    bJoinedInput = true;    // don't attach
+                    bJoinedInput = true;    // don't append
                     break;  // for
                 }
             }
             else if ( r1.In( rp1 ) )
-            {   // RangePair p included in RangePair r, make r the new RangePair
-                *p = r;
+            {   // RangePair p included in RangePair pOver, make pOver the new RangePair
+                *p = *pOver;
                 bJoined = true;
             }
         }
@@ -1528,15 +1532,25 @@ void ScRangePairList::Join( const ScRangePair& r, bool bIsInList )
         if ( bJoined )
         {
             if ( bIsInList )
-            {   // delete RangePair within the list
-                Remove( nOldPos );
-                i--;
-                pOver = nullptr;
-                if ( nOldPos )
-                    nOldPos--;          // configure seek correctly
+            {   // delete RangePair pOver within the list
+                if (nOverPos != std::numeric_limits<size_t>::max())
+                    Remove(nOverPos);
+                else
+                {
+                    for (size_t nOver = 0, nPairs = maPairs.size(); nOver < nPairs; ++nOver)
+                    {
+                        if (maPairs[nOver] == pOver)
+                        {
+                            Remove(nOver);
+                            break;
+                        }
+                    }
+                }
             }
             bJoinedInput = true;
-            Join( *p, true );           // recursive!
+            pOver = p;
+            bIsInList = true;
+            goto Label_RangePair_Join;
         }
     }
     if ( !bIsInList && !bJoinedInput )