From 9f35db4f516a9309f3db2104d41cdcf9f6dc86b5 Mon Sep 17 00:00:00 2001 From: Dominik Stadler Date: Tue, 31 Dec 2019 16:52:55 +0000 Subject: [PATCH] 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 --- .../poi/ss/formula/functions/Substitute.java | 20 ++-- .../apache/poi/hssf/usermodel/TestBugs.java | 35 ++++--- .../ss/formula/functions/TestSubstitute.java | 89 ++++++++++++++++++ test-data/spreadsheet/SUBSTITUTE.xls | Bin 0 -> 23552 bytes 4 files changed, 120 insertions(+), 24 deletions(-) create mode 100644 src/testcases/org/apache/poi/ss/formula/functions/TestSubstitute.java create mode 100644 test-data/spreadsheet/SUBSTITUTE.xls 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 0000000000000000000000000000000000000000..b479e15be8c0767eb100dd4bcfe3616607150c68 GIT binary patch literal 23552 zcmeG^2Urx>)^}!?-36p0ASf(VI!i}IQNczLL}Q5sMVd&^5NnhNqDE1o*lS`?iHaR8 zv7^|<-hv%t?;4FI>i*}uA#QMk&mZM-ISV8NZvRgIMHct~x_Ut42_Oq0>p;df7ekgn z)`hGGSs!u($Oe!NAsayk7a%5(O(B~>Hiz60vIS&I$X1XWLAHi$1GzEeCXj6*+d-B> zwukHh*%7i6WM{}Okefnwg^a$1*^_hsUu53DysGhJ2z-V?TeKsY@SR0QgQe@AEWl%w zm85}8D#0ru<;<0|$FGl0H{zofou|rUdLB<&a-MPrST2i3dVusSGMFSXdJJZ%{=n6g z&=mTuQiuAGqUf8^ET#_WN`{j!;4^@!dnd3$3ZoN3hLJ&VpUK1273AX>i2Vn3;6YU> znyh%zArT;9AfrPv(*l1?pAe9*tb2XsqrF}#;FfSlk;MQt0bLLZEe}^S=DME2+sRy8LP?e=OH_~)8xjH-I7juQTQhjy zGFJ!YY6w?~Y-MOJF%VxEu?_>igcLGOn)^mbRm+yk9>_{$|E{u8AWxq2&&kuRQ%@I? z2HFSJl<89;nVV!=WfijZGAW4$k4`0N;Mr`AC>Y^)q9Fx!)i$(-i>4(4c*@MRmQf^t zN1mP*I#1|hL0ag9JY`p)g|*QghBAp3o>&&9wTy<@O?!*A;wdw!qs&%l1!E}8pAN+i zj-HN=vKDaD$BVhO6*hs{80OKMvflB@NqxBpwlG!0B&$U5mT~Ff$yVqH)r2XRi=oDa zK?^4C#E*~!DImH_8Sx3y7K%rOKD7V`F9+tKb%NAZ=nYFjSPUjexpeMQE|I%bg(8f2 zlIE(yK#5xR3Q`pqFbE5)6&gf5z=vyvDsgM%)&kTht)cy3ozlmNt)yFvKCX)UK5n)` zJFqvbSZYfdW2vA>!Q!x>QJ|n44i9)lHqO9As)nP=Nr5OK8*ui3%G(OP$VOO2QN3X) z)EBxbev*j;8P?AMCMX9YNp&De@O?YkfwUm4iLKC|ltN_~0x#%UzVKlQ`N=#;8F(B= z4j=jrW?@IjD>*Lsl&M^ba9k?>4gd4(fYzm$g|))Yw3?kaDd55-s`jseuh#<4*8*Rt z1-?iNyhICpjTX2zedcPxU#$hMjlVYhjavBpyY<<|$Q45~G5w;ZU3P1MZ`K0ess&!A z1|j|qZf_NEDQsF`CRT&1>4RHg1^xg+TGjB! z?J)zNZDPXOnXQ+(60XKaL_{pUM!h6;!g1TJlT^>f^cGw@AtgGtEtU%X|;8QcqC zf^lZ7#GH&pN2y6+M7O=YW46SVWUIgtfr3zgIkWA-wX$+j(!|Bm`r_g`w7$5w;i@k# zR z!wpsQU+nF4o&GCid^$M=JtjfQt~RqJ>hw4&@YACgX{X0gf}b8eOFKP|Cj9j1ZQAK^ z)ZwQ`57bVNqYXbjdZl)H9F_R!E2H`CkHJNLdVc%EF#ZX8e*0rklV3i+{b3sX1U^@VE?bI=i{;7&6Dwe0VPSG*1XNN7OqT;=c)~@m4w&Wy zgb{SM1EB21J&0UgANj+@HTq~S$~=Hd+hnO;cl_n0w(i`;p0e(8d1Z|(W!+0lOEv1w zg(>TfFc82bW!fWEdraP`lY#Ho!1 z!GJ5M84I}m0oz)=uH5=7#{$jqB?NfZ`V@{E>ixMcpZfF07j=6ytFZ_A6ytx2sH3J& zK^T`~JFY!6aa-`4*TY^5d;|}~dsG-lnr`&Nv-KMRy z)_oRj2O&QLLirIH`~WT`UXYi<&ow(_zse5Fq!84dDd`9qI4BY&w3Qn`xLzARs!G8R z_F`djN>%j>xenelZA0WJ&V)~#UmfBcc*NmIp%AB&obvwG1r2egeB%7;5a+@pjvZ{6 z+KG}=9zTApAa`oYB z4RHcp zb$O;Ek2tPpRz|-$wpK%&6`#1eJhLf}IId?_Mqj>sSwmbSK5=z55VMsY!Zz%!*FPCI_B zXZrb1Tcz1{P58vs<(W=A;<%pa=l^oU1dZC+@`2Xp6TZ=uS(GnC*>1YmuJd&#Bn{-&wtUrI~wBb`NY-bnE^cFxSr|fzv|R9HF0LJ zcoP#!eFhJOp;O6Nwg z7@a_M@E)TVvuGjl$kmb0lt@*prK1CQr)BRIOJOwKELs;1kHDIxT6Plz_fsXH_2e|c z5jb!mRI)&wlqSLbU9CyjC#6Z)C#6Z)r&+WrA&?NHYs@~{646nKdmnp z5Vj1rhDwpx?%2@2xguz2TU8nz5%h#MY0bNeu|)Qw~FRsMTc1E>mcRVGx%g4zy}k6PR%r z;vmbmi&8`MreO4@gL5TQW=h(s*{czF6P94)gV95=l|&CxT8i}`9hDWqxCKKqm$|PXR+P817D8axoljIP^ha;B|sKy`0 z2TCj;D~jODLUBuzxsrqib2%jj1vH6^5(x1)8G`M}{cA>hz%fZNr4oy3>bZq(I1x^-6elA_{ z+3&BT&va|MQfiUmS>^xw`xd`s?XnYZu9&}gMdbPyZ9SYG+H~k!d_6d}YHj!Yan@F$ z1B#92zudlir)%(}+)numv_h{wY_D3w*dLP}^^p*E= zkNl$Jz4mo`+i1hRe#wES16N*?zR)i)t=P~YKjCDmw2{}HJuSY^e{}gmuZ*2nrBL>*PiJ>IQ(@&i!l$?}+-F%fsdmjtbFjH=^YC))A(7q=$%N%kU$1KUaoyCn z)wAzPEf$uDDsF~{9ZRbo(Q;2t-jRvRS2#<0j~e>TvN4x8C+v(ny)5*&uT62sEwVYL zMw6>zcgC-4n{@h!@tMeWmje==a#qavGU1}#{O=px2#P-Y$|C+^aQ}7FS00g4#^!CCBsETGq2ald>F&-)iBQo<^ z&9JoOFOq#Y*O&pB15%T-&_fzj#^_Z@jaye|7mX~e3Ldz_wOwNAv2{CsBjJm!+Z_7g z%#zC&Z~rnr_{4Sd^NXSkdU-Au8%#+)?mcf7K=1@qFRLwVSU>FKqTWZ~xTuYQJqx=`E*r=yC7tYqy*29(uUw(IIs!zu#tr zW^Qhy`*d2p zWAksB)345HvTKf&UbdV0nKSd|?tWD?TV$Q)I`O0LHxq(BI5ywW^y=ft)o%n{&m`&> zWWHLo;QEQmo8={4Uwc^iJZV>zVZSffLNAg3?mezkjb$?ocJE$zF6M$A6& z)1BCj&z@%HyxH4ilXH0E0Yx?<0g@BVRj$Vr1uu08XMSPo)XLpAgh0nr|``io5`QrBz)|VFQcG=eULgCgTjQ-|;BvT%Sw z+`IEdJ9>SQY3{YNC}&{)ubq2kd+rn!zl(}`GhzqTZ__jD**A|xy~)ZhySC}o;J7L4 zJ*!tw{4Qlx`u&SP6wVyAbAtD551Vh_X8IqVe7bMbv1NVIdt6LC`jvT7_}son_fI~M z_1U_1_a;9NBIbn-of2a^n}xO&9KI!5y8LAR)(&~brao9a}S=2=2^)iLlDcKHdsL?7 zfpKoHf1BhZ|M*+ir|T1T=luSD^|_Z0{pP<34$J;{XKUECV%rgmcien+(dXLEvCrQv z^7;7w`L^)i4Lf9;U2`TZeC6GI$$dI_b7}KoZrW;B@m}I*UW&wlpw$?egV~pc749p4hiN z8@W9qtoe{rcv;?z6#?KVbG(>A_5HzcEAGPv^o^krI;O`Fg`>xByb&KBo+{lu`B8k_Hg^GP6xfe z8#CG0tSaf3_LG6vS6(8pJ_qcM`GOt5i zpP0zec`FlKu9zGfGr!l{%io|?s(ZDI4PZ-xPp;}`dH%z}~cew?&2SsFXvHjk?KEVIpiy&UhQ?@BBdh1_ocTg;+K zl*n=Lwfv4_pFAs*{We?v-Nr*-9_xFu{Fm+-bJj#nYrZ=2=#zc9WqPme8V_EWW@?vs z&*@m;!<3S33)0`qKXfa5&~NvG=OEyc3IKnzT5Ox zzvg$heOn+Y?%S+*RP4R3c2sOYMUba^v+P^>Wsc=e6V{g;A4ln14qcucdg4~oh;ObM zI}Z)$_Hxe5)|K7F`=aLOnmO)zbZ+glVWz`>mbJX^X>op4%B5a9Gv9t)w0LcW+nngr zbJG9u^}JOVGX&X3n>YO-$tQfDEM?ZuLkm})u$(jN54u@kK3f*4k+1r z{lLwVjiPM_F0~$57JusJ7OURQ`POfFC2CaS+6LtI@DUt2YxB{4 zj&pU}pc#^`lO8Ue)qVWrj+HGVmo8ktWy!>G2e*HdmU&>ftK_NIwis8Br#8(b+nXeX zT33$?sK{L78oOd%T=m({tKWY%HKEBGrz+vTs|J&r_FK~VO}Nml`#Os`f=LnOQ^zMh zIBq{Kct9`vW4{h5@;!cZ-COs_yK&p6rI{}6)xme_XuXTYq05%7_p`I=QPy&NxWT+i z>j7bL1{a2voR2A6HzTWO)$o&+@!$JTNx9~~wq)t{A9qaYWpU?={(I;382m!CdfU{Z z9~U%f<#lzc^T@CIJ+!zpVNFzSg}=Pn_9r^ld2PIcQ@V65n0IVLNmbcrJ4RLpk22gm zH9&XSgC2L%E#J?5C0Ws|=g#=M;%x`kOe{V7{T-oEp*44X#IT6}6s zx3{_LLY7VMe#>Fmk8KX`IMwm>@a!L+FQUdCaN3nA}hyj*Cj7g-3gD-@gBPP1Pyd3w|Tlwz>s0PO4+A8yBU@Kz+GaODzL? zau$E;gzC$uTEa%KuH-g?y7|>Psjp>fIbEoW6SJ~W=b`QdwLGff91~X?9+!xV(!oPp zuw~I9eWCVO@USmg1e=~koGk_vkOF`eaA1gs$n2}2#wxFZ>eJ>}%p|0}8%0P~G`v=eN+yTW%*hAAr>;+CYLKm_VgNtA%51Og$gLyM9q3hs@B#voJ7eUJ!rDLqP` zZa^E*hP07@=wT@>pcyh+OiO58WP}h33u)j(2`L>t;3=lX0x=*$5E!;^8id3=i87$U zaRrctkaeUYsTh7pVi+m}P{dHlpVpy7!d$ViwM5vO7$H<56-cB)6+s}_P)tb##F!;R zT__O+Ac?6iylf0w5Yr?|BBcey4Am7n2qX?9ISK4hD~J}+Ktb!$dNkBsU_cpCMgn8n zgfgYfD08|YZ9!YoR)R*fHElyTrkl{Vv>h#_?P&+vk#?e;X&1UF?Ml1R?z9KxNqJG; zln*7Nd?`Q5p9-J?sURwt4xyUS&FL0&DBY57MTgO?={8hbDx8j>+esiGMx#0+#?nFu z&<9N|)Dwa}!qx@?LxB-xOqmEwX*1fKQYb_-3JDtvn+V~(M-eDQIZ%$2LLthPa--ZS zP>A+Q@=o$elF=#(Q6V&=kRX(5NwuQFsMZuHM2AzLkf=S~f$m6mq9cV-bTl19ccx<{ z4smoBI-Vv1)Rb*@*3=Z^G*knMF&yg28cx(uWFfK?S&18ottlI-G1Y{!rR)SrHHuQ^ z&Xlb-YvTjQONMbJ%iA55T zu1HU$FKQq%5TWZr^UVJh_a*!{5xLzcnP3Iw*$;3C%yHj|0y+|0OKbH>vZ~@1Z`iuWhV`96(L=MZp z|FkB58TnbzeAnQ2%%4a9^D6x-v?#TsLbOUpGE8Zb`p>A8o10rh_Uw7htr%7eVi+D^ z8m&hHqui98fL|FO%YK*HcTSx5JN)jsR(4yq6e8_^%|yY7g-aqBM_>%Y$})-lOAnI~2Xz9T51@%L?v8bz`| z$_T=9ZVU`xSir8waQb4Tug`9>61Ss5!d|(1fH1jWk z5R_n^gz$tiE`orskS}RPo02U^LR#Ym628Pe74~aWRVt+i{~BndSP(EQ5cMgr(IJ8G zqkF2v5;DTr1OqoNKLns769ZGi|NgGS0@xzhVemf|F`-jnli)fIVK~Pr%NT^eFaJ{( z_y~JaJ;no|p*act;>N@!FW$zc8LyrpAs$W3s&Es6!9gKpEXQX&;ev0k;omwyhht8u z#KE^Rp>HjRb9Jo|@Y(YlMVaR*=6=<|H2hCUC}L8_PBF3FV#kHYv%I;`)0$k->a{#Z{OvCt;?mjp?WF*=h0*%
    =Q&&Ub?-~