Revert "use std::vector in BigPtrArray"

which is causing crashes in the crashtesting in
ooo119635-3.docx and ooo119568-2.docx

It is definitely some kind of use-after-free error, but the
compress and delete logic for BigPtrArray is too hairy for me
to debug right now.

This reverts commit 1eee0abd459a508a6dcf9e71cbf2c1be3725faa7.

Also revert commit 4f743419a04375160437a910254c45dea396f70d
"gdb pretty-printers: fix BigPtrArrayPrinter after recent std::isation"

Change-Id: Id870876432a060f9347aafb43bf0df692ea24464
Reviewed-on: https://gerrit.libreoffice.org/39684
Tested-by: Jenkins <ci@libreoffice.org>
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

3 files changed, 77 insertions, 45 deletions

diff --git a/sw/inc/bparr.hxx b/sw/inc/bparr.hxx
index 04b77eb16dee..962736c49ce3 100644
--- a/sw/inc/bparr.hxx
+++ b/sw/inc/bparr.hxx
@@ -25,7 +25,6 @@
 #include <tools/solar.h>
 #include <swdllapi.h>
 #include <array>
-#include <vector>
 
 struct BlockInfo;
 class BigPtrArray;
@@ -64,14 +63,16 @@ struct BlockInfo final
 class SW_DLLPUBLIC BigPtrArray
 {
 protected:
-    std::vector<BlockInfo*>
-                    m_vpInf;              ///< block info
+    BlockInfo**     m_ppInf;              ///< block info
     sal_uLong       m_nSize;              ///< number of elements
+    sal_uInt16      m_nMaxBlock;          ///< current max. number of blocks
+    sal_uInt16      m_nBlock;             ///< number of blocks
     mutable
         sal_uInt16  m_nCur;               ///< last used block
 
     sal_uInt16  Index2Block( sal_uLong ) const; ///< block search
     BlockInfo*  InsBlock( sal_uInt16 );         ///< insert block
+    void        BlockDel( sal_uInt16 );         ///< some blocks were deleted
     void        UpdIndex( sal_uInt16 );         ///< recalculate indices
 
     // fill all blocks
diff --git a/sw/source/core/bastyp/bparr.cxx b/sw/source/core/bastyp/bparr.cxx
index 8d7124a470ac..446d22ef154c 100644
--- a/sw/source/core/bastyp/bparr.cxx
+++ b/sw/source/core/bastyp/bparr.cxx
@@ -21,7 +21,6 @@
 
 #include <limits.h>
 #include <string.h>
-#include <algorithm>
 
 /** Resize block management by this constant.
     As a result there are approx. 20 * MAXENTRY == 20000 entries available */
@@ -48,21 +47,23 @@ void CheckIdx( BlockInfo** ppInf, sal_uInt16 nBlock, sal_uLong nSize, sal_uInt16
 
 BigPtrArray::BigPtrArray()
 {
-    m_nCur = 0;
+    m_nBlock = m_nCur = 0;
     m_nSize = 0;
-    m_vpInf.reserve( nBlockGrowSize );
+    m_nMaxBlock = nBlockGrowSize;
+    m_ppInf = new BlockInfo* [ m_nMaxBlock ];
 }
 
 BigPtrArray::~BigPtrArray()
 {
-    if( m_vpInf.size() )
+    if( m_nBlock )
     {
-        BlockInfo** pp = m_vpInf.data();
-        for( sal_uInt16 n = 0; n < sal_uInt16(m_vpInf.size()); ++n, ++pp )
+        BlockInfo** pp = m_ppInf;
+        for( sal_uInt16 n = 0; n < m_nBlock; ++n, ++pp )
         {
             delete *pp;
         }
     }
+    delete[] m_ppInf;
 }
 
 // Also moving is done simply here. Optimization is useless because of the
@@ -72,7 +73,7 @@ void BigPtrArray::Move( sal_uLong from, sal_uLong to )
     if (from != to)
     {
         sal_uInt16 cur = Index2Block( from );
-        BlockInfo* p = m_vpInf[ cur ];
+        BlockInfo* p = m_ppInf[ cur ];
         BigPtrEntry* pElem = p->mvData[ from - p->nStart ];
         Insert( pElem, to ); // insert first, then delete!
         Remove( ( to < from ) ? ( from + 1 ) : from );
@@ -83,7 +84,7 @@ BigPtrEntry* BigPtrArray::operator[]( sal_uLong idx ) const
 {
     assert(idx < m_nSize); // operator[]: Index out of bounds
     m_nCur = Index2Block( idx );
-    BlockInfo* p = m_vpInf[ m_nCur ];
+    BlockInfo* p = m_ppInf[ m_nCur ];
     return p->mvData[ idx - p->nStart ];
 }
 
@@ -91,7 +92,7 @@ BigPtrEntry* BigPtrArray::operator[]( sal_uLong idx ) const
 sal_uInt16 BigPtrArray::Index2Block( sal_uLong pos ) const
 {
     // last used block?
-    BlockInfo* p = m_vpInf[ m_nCur ];
+    BlockInfo* p = m_ppInf[ m_nCur ];
     if( p->nStart <= pos && p->nEnd >= pos )
         return m_nCur;
     // Index = 0?
@@ -99,28 +100,28 @@ sal_uInt16 BigPtrArray::Index2Block( sal_uLong pos ) const
         return 0;
 
     // following one?
-    if( m_nCur < ( m_vpInf.size() - 1 ) )
+    if( m_nCur < ( m_nBlock - 1 ) )
     {
-        p = m_vpInf[ m_nCur+1 ];
+        p = m_ppInf[ m_nCur+1 ];
         if( p->nStart <= pos && p->nEnd >= pos )
             return m_nCur+1;
     }
     // previous one?
     else if( pos < p->nStart && m_nCur > 0 )
     {
-        p = m_vpInf[ m_nCur-1 ];
+        p = m_ppInf[ m_nCur-1 ];
         if( p->nStart <= pos && p->nEnd >= pos )
             return m_nCur-1;
     }
 
     // binary search: always successful
-    sal_uInt16 lower = 0, upper = m_vpInf.size() - 1;
+    sal_uInt16 lower = 0, upper = m_nBlock - 1;
     sal_uInt16 cur = 0;
     for(;;)
     {
         sal_uInt16 n = lower + ( upper - lower ) / 2;
         cur = ( n == cur ) ? n+1 : n;
-        p = m_vpInf[ cur ];
+        p = m_ppInf[ cur ];
         if( p->nStart <= pos && p->nEnd >= pos )
             return cur;
 
@@ -137,9 +138,9 @@ sal_uInt16 BigPtrArray::Index2Block( sal_uLong pos ) const
 */
 void BigPtrArray::UpdIndex( sal_uInt16 pos )
 {
-    BlockInfo** pp = m_vpInf.data() + pos;
+    BlockInfo** pp = m_ppInf + pos;
     sal_uLong idx = (*pp)->nEnd + 1;
-    while( ++pos < m_vpInf.size() )
+    while( ++pos < m_nBlock )
     {
         BlockInfo* p = *++pp;
         p->nStart = idx;
@@ -156,11 +157,26 @@ void BigPtrArray::UpdIndex( sal_uInt16 pos )
 */
 BlockInfo* BigPtrArray::InsBlock( sal_uInt16 pos )
 {
+    if( m_nBlock == m_nMaxBlock )
+    {
+        // than extend the array first
+        BlockInfo** ppNew = new BlockInfo* [ m_nMaxBlock + nBlockGrowSize ];
+        memcpy( ppNew, m_ppInf, m_nMaxBlock * sizeof( BlockInfo* ));
+        delete[] m_ppInf;
+        m_nMaxBlock += nBlockGrowSize;
+        m_ppInf = ppNew;
+    }
+    if( pos != m_nBlock )
+    {
+        memmove( m_ppInf + pos+1, m_ppInf + pos,
+                 ( m_nBlock - pos ) * sizeof( BlockInfo* ));
+    }
+    ++m_nBlock;
     BlockInfo* p = new BlockInfo;
-    m_vpInf.insert( m_vpInf.begin() + pos, p );
+    m_ppInf[ pos ] = p;
 
     if( pos )
-        p->nStart = p->nEnd = m_vpInf[ pos-1 ]->nEnd + 1;
+        p->nStart = p->nEnd = m_ppInf[ pos-1 ]->nEnd + 1;
     else
         p->nStart = p->nEnd = 0;
 
@@ -170,6 +186,21 @@ BlockInfo* BigPtrArray::InsBlock( sal_uInt16 pos )
     return p;
 }
 
+void BigPtrArray::BlockDel( sal_uInt16 nDel )
+{
+    m_nBlock = m_nBlock - nDel;
+    if( m_nMaxBlock - m_nBlock > nBlockGrowSize )
+    {
+        // than shrink array
+        nDel = (( m_nBlock / nBlockGrowSize ) + 1 ) * nBlockGrowSize;
+        BlockInfo** ppNew = new BlockInfo* [ nDel ];
+        memcpy( ppNew, m_ppInf, m_nBlock * sizeof( BlockInfo* ));
+        delete[] m_ppInf;
+        m_ppInf = ppNew;
+        m_nMaxBlock = nDel;
+    }
+}
+
 void BigPtrArray::Insert( BigPtrEntry* pElem, sal_uLong pos )
 {
     CHECKIDX( ppInf, nBlock, nSize, nCur );
@@ -184,8 +215,8 @@ void BigPtrArray::Insert( BigPtrEntry* pElem, sal_uLong pos )
     else if( pos == m_nSize )
     {
         // special case: insert at end
-        cur = m_vpInf.size() - 1;
-        p = m_vpInf[ cur ];
+        cur = m_nBlock - 1;
+        p = m_ppInf[ cur ];
         if( p->nElem == MAXENTRY )
             // the last block is full, create a new one
             p = InsBlock( ++cur );
@@ -194,16 +225,16 @@ void BigPtrArray::Insert( BigPtrEntry* pElem, sal_uLong pos )
     {
         // standard case:
         cur = Index2Block( pos );
-        p = m_vpInf[ cur ];
+        p = m_ppInf[ cur ];
     }
 
     if( p->nElem == MAXENTRY )
     {
         // does the last entry fit into the next block?
         BlockInfo* q;
-        if( cur < ( m_vpInf.size() - 1 ) && m_vpInf[ cur+1 ]->nElem < MAXENTRY )
+        if( cur < ( m_nBlock - 1 ) && m_ppInf[ cur+1 ]->nElem < MAXENTRY )
         {
-            q = m_vpInf[ cur+1 ];
+            q = m_ppInf[ cur+1 ];
             if( q->nElem )
             {
                 int nCount = q->nElem;
@@ -220,7 +251,7 @@ void BigPtrArray::Insert( BigPtrEntry* pElem, sal_uLong pos )
             // If it does not fit, then insert a new block. But if there is more
             // than 50% space in the array then compress first.
             if( /*nBlock == nMaxBlock &&*/
-                m_vpInf.size() > ( m_nSize / ( MAXENTRY / 2 ) ) &&
+                m_nBlock > ( m_nSize / ( MAXENTRY / 2 ) ) &&
                 cur >= Compress() )
             {
                 // Something was moved before the current position and all
@@ -262,7 +293,7 @@ void BigPtrArray::Insert( BigPtrEntry* pElem, sal_uLong pos )
     p->nEnd++;
     p->nElem++;
     m_nSize++;
-    if( cur != ( m_vpInf.size() - 1 ) ) UpdIndex( cur );
+    if( cur != ( m_nBlock - 1 ) ) UpdIndex( cur );
     m_nCur = cur;
 
     CHECKIDX( ppInf, nBlock, nSize, nCur );
@@ -276,7 +307,7 @@ void BigPtrArray::Remove( sal_uLong pos, sal_uLong n )
     sal_uInt16 cur = Index2Block( pos ); // current block number
     sal_uInt16 nBlk1 = cur;              // 1st treated block
     sal_uInt16 nBlk1del = USHRT_MAX;     // 1st deleted block
-    BlockInfo* p = m_vpInf[ cur ];
+    BlockInfo* p = m_ppInf[ cur ];
     pos -= p->nStart;
 
     sal_uLong nElem = n;
@@ -310,7 +341,7 @@ void BigPtrArray::Remove( sal_uLong pos, sal_uLong n )
         nElem -= nel;
         if( !nElem )
             break;
-        p = m_vpInf[ ++cur ];
+        p = m_ppInf[ ++cur ];
         pos = 0;
     }
 
@@ -318,16 +349,17 @@ void BigPtrArray::Remove( sal_uLong pos, sal_uLong n )
     if( nBlkdel )
     {
         for( sal_uInt16 i = nBlk1del; i < ( nBlk1del + nBlkdel ); i++ )
-            delete m_vpInf[ i ];
+            delete m_ppInf[ i ];
 
-        m_vpInf.erase( m_vpInf.begin() + nBlk1del, m_vpInf.begin() + nBlk1del + nBlkdel );
-
-        if( ( nBlk1del + nBlkdel ) < sal_uInt16(m_vpInf.size()) )
+        if( ( nBlk1del + nBlkdel ) < m_nBlock )
         {
+            memmove( m_ppInf + nBlk1del, m_ppInf + nBlk1del + nBlkdel,
+                     ( m_nBlock - nBlkdel - nBlk1del ) * sizeof( BlockInfo* ) );
+
             // UpdateIdx updates the successor thus start before first elem
             if( !nBlk1 )
             {
-                p = m_vpInf[ 0 ];
+                p = m_ppInf[ 0 ];
                 p->nStart = 0;
                 p->nEnd = p->nElem-1;
             }
@@ -336,15 +368,16 @@ void BigPtrArray::Remove( sal_uLong pos, sal_uLong n )
                 --nBlk1;
             }
         }
+        BlockDel( nBlkdel ); // blocks were deleted
     }
 
     m_nSize -= n;
-    if( nBlk1 != ( m_vpInf.size() - 1 ) && m_nSize )
+    if( nBlk1 != ( m_nBlock - 1 ) && m_nSize )
         UpdIndex( nBlk1 );
     m_nCur = nBlk1;
 
     // call Compress() if there is more than 50% space in the array
-    if( m_vpInf.size() > ( m_nSize / ( MAXENTRY / 2 ) ) )
+    if( m_nBlock > ( m_nSize / ( MAXENTRY / 2 ) ) )
         Compress();
 
     CHECKIDX( ppInf, nBlock, nSize, nCur );
@@ -354,7 +387,7 @@ void BigPtrArray::Replace( sal_uLong idx, BigPtrEntry* pElem)
 {
     assert(idx < m_nSize); // Index out of bounds
     m_nCur = Index2Block( idx );
-    BlockInfo* p = m_vpInf[ m_nCur ];
+    BlockInfo* p = m_ppInf[ m_nCur ];
     pElem->m_nOffset = sal_uInt16(idx - p->nStart);
     pElem->m_pBlock = p;
     p->mvData[ idx - p->nStart ] = pElem;
@@ -368,7 +401,7 @@ sal_uInt16 BigPtrArray::Compress()
     // Iterate over InfoBlock array from beginning to end. If there is a deleted
     // block in between so move all following ones accordingly. The pointer <pp>
     // represents the "old" and <qq> the "new" array.
-    BlockInfo** pp = m_vpInf.data(), **qq = pp;
+    BlockInfo** pp = m_ppInf, **qq = pp;
     BlockInfo* p;
     BlockInfo* pLast(nullptr);                 // last empty block
     sal_uInt16 nLast = 0;                // missing elements
@@ -378,7 +411,7 @@ sal_uInt16 BigPtrArray::Compress()
     // convert fill percentage into number of remaining elements
     short const nMax = MAXENTRY - (long) MAXENTRY * COMPRESSLVL / 100;
 
-    for( sal_uInt16 cur = 0; cur < sal_uInt16(m_vpInf.size()); ++cur )
+    for( sal_uInt16 cur = 0; cur < m_nBlock; ++cur )
     {
         p = *pp++;
         sal_uInt16 n = p->nElem;
@@ -419,7 +452,6 @@ sal_uInt16 BigPtrArray::Compress()
                 // than remove
                 delete   p;
                 p = nullptr;
-                *(pp-1) = nullptr;
                 ++nBlkdel;
             }
             else
@@ -451,11 +483,10 @@ sal_uInt16 BigPtrArray::Compress()
 
     // if blocks were deleted shrink BlockInfo array if needed
     if( nBlkdel )
-        m_vpInf.erase( std::remove_if(m_vpInf.begin(), m_vpInf.end(), [](BlockInfo* bi) { return !bi; }),
-                       m_vpInf.end() );
+        BlockDel( nBlkdel );
 
     // and re-index
-    p = m_vpInf[ 0 ];
+    p = m_ppInf[ 0 ];
     p->nEnd = p->nElem - 1;
     UpdIndex( 0 );
 
diff --git a/sw/source/core/docnode/nodes.cxx b/sw/source/core/docnode/nodes.cxx
index 0657f0962138..d4facd6f46bd 100644
--- a/sw/source/core/docnode/nodes.cxx
+++ b/sw/source/core/docnode/nodes.cxx
@@ -2184,7 +2184,7 @@ void SwNodes::ForEach( sal_uLong nStart, sal_uLong nEnd,
     if( nStart < nEnd )
     {
         sal_uInt16 cur = Index2Block( nStart );
-        BlockInfo** pp = m_vpInf.data() + cur;
+        BlockInfo** pp = m_ppInf + cur;
         BlockInfo* p = *pp;
         sal_uInt16 nElem = sal_uInt16( nStart - p->nStart );
         auto pElem = p->mvData.begin() + nElem;