Bug 63940: Avoid endless loop/out of memory on string-replace with empty search string

git-svn-id: https://svn.apache.org/repos/asf/poi/trunk@1872145 13f79535-47bb-0310-9956-ffa450edef68

4 files changed, 120 insertions, 24 deletions

diff --git a/src/java/org/apache/poi/ss/formula/functions/Substitute.java b/src/java/org/apache/poi/ss/formula/functions/Substitute.java
index 3f17557c99..69d5cf5ec8 100644
--- a/src/java/org/apache/poi/ss/formula/functions/Substitute.java
+++ b/src/java/org/apache/poi/ss/formula/functions/Substitute.java
@@ -64,11 +64,15 @@ public final class Substitute extends Var3or4ArgFunction {
 	}
 
 	private static String replaceAllOccurrences(String oldStr, String searchStr, String newStr) {
+		// avoid endless loop when searching for nothing
+		if (searchStr.length() < 1) {
+			return oldStr;
+		}
+
 		StringBuilder sb = new StringBuilder();
 		int startIndex = 0;
-		int nextMatch;
 		while (true) {
-			nextMatch = oldStr.indexOf(searchStr, startIndex);
+			int nextMatch = oldStr.indexOf(searchStr, startIndex);
 			if (nextMatch < 0) {
 				// store everything from end of last match to end of string
 				sb.append(oldStr.substring(startIndex));
@@ -82,25 +86,23 @@ public final class Substitute extends Var3or4ArgFunction {
 	}
 
 	private static String replaceOneOccurrence(String oldStr, String searchStr, String newStr, int instanceNumber) {
+		// avoid endless loop when searching for nothing
 		if (searchStr.length() < 1) {
 			return oldStr;
 		}
 		int startIndex = 0;
-		int nextMatch = -1;
 		int count=0;
 		while (true) {
-			nextMatch = oldStr.indexOf(searchStr, startIndex);
+			int nextMatch = oldStr.indexOf(searchStr, startIndex);
 			if (nextMatch < 0) {
 				// not enough occurrences found - leave unchanged
 				return oldStr;
 			}
 			count++;
 			if (count == instanceNumber) {
-				StringBuilder sb = new StringBuilder(oldStr.length() + newStr.length());
-				sb.append(oldStr, 0, nextMatch);
-				sb.append(newStr);
-				sb.append(oldStr.substring(nextMatch + searchStr.length()));
-				return sb.toString();
+				return oldStr.substring(0, nextMatch) +
+						newStr +
+						oldStr.substring(nextMatch + searchStr.length());
 			}
 			startIndex = nextMatch + searchStr.length();
 		}
diff --git a/src/testcases/org/apache/poi/hssf/usermodel/TestBugs.java b/src/testcases/org/apache/poi/hssf/usermodel/TestBugs.java
index b0aa06cb4e..29f6e22f19 100644
--- a/src/testcases/org/apache/poi/hssf/usermodel/TestBugs.java
+++ b/src/testcases/org/apache/poi/hssf/usermodel/TestBugs.java
@@ -2879,7 +2879,7 @@ public final class TestBugs extends BaseTestBugzillaIssues {
         FormulaEvaluator eval = wb.getCreationHelper().createFormulaEvaluator();
 
         eval.evaluateAll();
-        
+
         /*OutputStream out = new FileOutputStream("C:\\temp\\48043.xls");
         try {
           wb.write(out);
@@ -3119,20 +3119,25 @@ public final class TestBugs extends BaseTestBugzillaIssues {
 
     @Test
     public void test60460() throws IOException {
-        final Workbook wb = HSSFTestDataSamples.openSampleWorkbook("60460.xls");
-
-        assertEquals(2, wb.getAllNames().size());
-
-        Name rangedName = wb.getAllNames().get(0);
-        assertFalse(rangedName.isFunctionName());
-        assertEquals("'[\\\\HEPPC3\\gt$\\Teaching\\Syn\\physyn.xls]#REF'!$AK$70:$AL$70",
-                // replace '/' to make test work equally on Windows and Linux
-                rangedName.getRefersToFormula().replace("/", "\\"));
-
-        rangedName = wb.getAllNames().get(1);
-        assertFalse(rangedName.isFunctionName());
-        assertEquals("Questionnaire!$A$1:$L$65", rangedName.getRefersToFormula());
+        try (final Workbook wb = HSSFTestDataSamples.openSampleWorkbook("60460.xls")) {
+            assertEquals(2, wb.getAllNames().size());
+
+            Name rangedName = wb.getAllNames().get(0);
+            assertFalse(rangedName.isFunctionName());
+            assertEquals("'[\\\\HEPPC3\\gt$\\Teaching\\Syn\\physyn.xls]#REF'!$AK$70:$AL$70",
+                    // replace '/' to make test work equally on Windows and Linux
+                    rangedName.getRefersToFormula().replace("/", "\\"));
+
+            rangedName = wb.getAllNames().get(1);
+            assertFalse(rangedName.isFunctionName());
+            assertEquals("Questionnaire!$A$1:$L$65", rangedName.getRefersToFormula());
+        }
+    }
 
-        wb.close();
+    @Test
+    public void test63940() throws IOException {
+        try (final Workbook wb = HSSFTestDataSamples.openSampleWorkbook("SUBSTITUTE.xls")) {
+            wb.getCreationHelper().createFormulaEvaluator().evaluateAll();
+        }
     }
 }
diff --git a/src/testcases/org/apache/poi/ss/formula/functions/TestSubstitute.java b/src/testcases/org/apache/poi/ss/formula/functions/TestSubstitute.java
new file mode 100644
index 0000000000..68c868865b
--- /dev/null
+++ b/src/testcases/org/apache/poi/ss/formula/functions/TestSubstitute.java
@@ -0,0 +1,89 @@
+/* ====================================================================
+   Licensed to the Apache Software Foundation (ASF) under one or more
+   contributor license agreements.  See the NOTICE file distributed with
+   this work for additional information regarding copyright ownership.
+   The ASF licenses this file to You under the Apache License, Version 2.0
+   (the "License"); you may not use this file except in compliance with
+   the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+==================================================================== */
+
+package org.apache.poi.ss.formula.functions;
+
+import org.apache.poi.ss.formula.eval.ErrorEval;
+import org.apache.poi.ss.formula.eval.NumberEval;
+import org.apache.poi.ss.formula.eval.StringEval;
+import org.apache.poi.ss.formula.eval.StringValueEval;
+import org.apache.poi.ss.usermodel.FormulaError;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class TestSubstitute {
+    @Test
+    public void testSubstitute() {
+        Substitute fun = new Substitute();
+        assertEquals("ADEFC", ((StringValueEval)fun.evaluate(0, 1,
+                new StringEval("ABC"), new StringEval("B"), new StringEval("DEF"))).getStringValue());
+
+        assertEquals("ACDEC", ((StringValueEval)fun.evaluate(0, 1,
+                new StringEval("ABC"), new StringEval("B"), new StringEval("CDE"))).getStringValue());
+
+        assertEquals("ACDECCDEA", ((StringValueEval)fun.evaluate(0, 1,
+                new StringEval("ABCBA"), new StringEval("B"), new StringEval("CDE"))).getStringValue());
+    }
+
+    @Test
+    public void testSubstituteInvalidArg() {
+        Substitute fun = new Substitute();
+        assertEquals(ErrorEval.valueOf(FormulaError.VALUE.getLongCode()),
+                fun.evaluate(0, 1,
+                ErrorEval.valueOf(FormulaError.VALUE.getLongCode()), new StringEval("B"), new StringEval("DEF")));
+
+        assertEquals(ErrorEval.valueOf(FormulaError.VALUE.getLongCode()),
+                fun.evaluate(0, 1,
+                ErrorEval.valueOf(FormulaError.VALUE.getLongCode()), new StringEval("B"), new StringEval("DEF"),
+                        new NumberEval(1)));
+
+        // fails on occurrence below 1
+        assertEquals(ErrorEval.valueOf(FormulaError.VALUE.getLongCode()),
+                fun.evaluate(0, 1,
+                new StringEval("ABC"), new StringEval("B"), new StringEval("CDE"), new NumberEval(0)));
+    }
+
+    @Test
+    public void testSubstituteOne() {
+        Substitute fun = new Substitute();
+        assertEquals("ADEFC", ((StringValueEval)fun.evaluate(0, 1,
+                new StringEval("ABC"), new StringEval("B"), new StringEval("DEF"), new NumberEval(1))).getStringValue());
+
+        assertEquals("ACDEC", ((StringValueEval)fun.evaluate(0, 1,
+                new StringEval("ABC"), new StringEval("B"), new StringEval("CDE"), new NumberEval(1))).getStringValue());
+    }
+
+    @Test
+    public void testSubstituteNotFound() {
+        Substitute fun = new Substitute();
+        assertEquals("ABC", ((StringValueEval)fun.evaluate(0, 1,
+                new StringEval("ABC"), new StringEval("B"), new StringEval("DEF"), new NumberEval(12))).getStringValue());
+
+        assertEquals("ABC", ((StringValueEval)fun.evaluate(0, 1,
+                new StringEval("ABC"), new StringEval("B"), new StringEval("CDE"), new NumberEval(2))).getStringValue());
+    }
+
+    @Test
+    public void testSearchEmpty() {
+        Substitute fun = new Substitute();
+        assertEquals("ABC", ((StringValueEval)fun.evaluate(0, 1,
+                new StringEval("ABC"), new StringEval(""), new StringEval("CDE"))).getStringValue());
+        assertEquals("ABC", ((StringValueEval)fun.evaluate(0, 1,
+                new StringEval("ABC"), new StringEval(""), new StringEval("CDE"), new NumberEval(1))).getStringValue());
+    }
+}
\ No newline at end of file
diff --git a/test-data/spreadsheet/SUBSTITUTE.xls b/test-data/spreadsheet/SUBSTITUTE.xls
new file mode 100644
index 0000000000..b479e15be8
--- /dev/null
+++ b/test-data/spreadsheet/SUBSTITUTE.xls