tdf#147109: Optimize ScInterpreter::ScSubstitute

Avoid multiple reallocations, making it freeze for e.g.

=SUBSTITUTE(REPT(" ";1000000);" ";"")

Change-Id: I269c0b06a0b3cbf9369cc47f33c2eea026b12903
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/129252
Tested-by: Mike Kaganski <mike.kaganski@collabora.com>
Reviewed-by: Mike Kaganski <mike.kaganski@collabora.com>

1 files changed, 17 insertions, 22 deletions

diff --git a/sc/source/core/tool/interpr1.cxx b/sc/source/core/tool/interpr1.cxx
index a078fce13f59..450b70f264b9 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -9695,32 +9695,27 @@ void ScInterpreter::ScSubstitute()
     OUString sStr    = GetString().getString();
     sal_Int32 nPos = 0;
     sal_Int32 nCount = 0;
-    sal_Int32 nNewLen = sNewStr.getLength();
-    sal_Int32 nOldLen = sOldStr.getLength();
-    while( true )
+    std::optional<OUStringBuffer> oResult;
+    for (sal_Int32 nEnd = sStr.indexOf(sOldStr); nEnd >= 0; nEnd = sStr.indexOf(sOldStr, nEnd))
     {
-        nPos = sStr.indexOf( sOldStr, nPos );
-        if (nPos != -1)
+        if (nCnt == 0 || ++nCount == nCnt) // Found a replacement cite
         {
-            nCount++;
-            if( !nCnt || nCount == nCnt )
-            {
-                sStr = sStr.replaceAt(nPos,nOldLen, u"");
-                if ( CheckStringResultLen( sStr, sNewStr ) )
-                {
-                    sStr = sStr.replaceAt(nPos, 0, sNewStr);
-                    nPos = sal::static_int_cast<sal_Int32>( nPos + nNewLen );
-                }
-                else
-                    break;
-            }
-            else
-                nPos++;
+            if (!oResult) // Only allocate buffer when needed
+                oResult.emplace(sStr.getLength() + sNewStr.getLength() - sOldStr.getLength());
+
+            oResult->append(sStr.subView(nPos, nEnd - nPos)); // Copy leading unchanged text
+            if (!CheckStringResultLen(*oResult, sNewStr))
+                return PushError(GetError());
+            oResult->append(sNewStr); // Copy  the replacement
+            nPos = nEnd + sOldStr.getLength();
+            if (nCnt > 0) // Found the single replacement site - end the loop
+                break;
         }
-        else
-            break;
+        nEnd += sOldStr.getLength();
     }
-    PushString( sStr );
+    if (oResult) // If there were prior replacements, copy the rest, otherwise use original
+        oResult->append(sStr.subView(nPos, sStr.getLength() - nPos));
+    PushString(oResult ? oResult->makeStringAndClear() : sStr);
 }
 
 void ScInterpreter::ScRept()