8058779: Faster implementation of String.replace(CharSequence, CharSequence)

[Peter Levart]

On 06/01/2015 10:32 AM, Ulf Zibis wrote:
> Hi,
>
> Am 31.05.2015 um 18:03 schrieb Ivan Gerasimov:
>>
>> On 31.05.2015 18:54, Ivan Gerasimov wrote:
>>>
>>> I fixed the code and added the case to the regression test in the 
>>> new webrev.
>>>
>> Which is right here:
>> http://cr.openjdk.java.net/~igerasim/8058779/05/webrev/
>
> Shoudn't the user be informed via javadoc about the risk of an 
> OutOfMemoryError, just from illegal arguments of this method?
> Example:
> this.value.length() = 100
> target.value.length() = 200
> replacement.value.length() = 50
> results in:

...no replacements made, since target.value.length() > 
this.value.length() and 1st indexOf returns -1...

if 1st indexOf returns >= 0, then this.value.length() >= 
target.value.length() and the only way to get negative newLenHint is via 
an overflow indicating that a String with length() > Integer.MAX_VALUE 
would be required to hold the result, which is impossible. We don't have 
a special StringTooBigException. OOME is the best approximation here. 
IllegalArgumentException is another option, but seems to be to general 
in this case. What happens when regexp based replace is fed with such 
huge strings?

I had to set the max. heap size to 14Gbytes to get the answer that was 
not an OOME caused by not enough heap space:

         char[] chars = new char[1 + (1 << 30)];
         chars[0] = 'a';
         String big = new String(chars);
         big.replace("a", big);

Exception in thread "main" java.lang.OutOfMemoryError
     at 
java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:137)
     at 
java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:124)
     at 
java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:517)
     at java.lang.StringBuilder.append(StringBuilder.java:175)
     at java.util.regex.Matcher.appendTail(Matcher.java:1122)
     at java.util.regex.Matcher.replaceAll(Matcher.java:1169)
     at TestReplace.replace(TestReplace.java:11)
     at TestReplace.main(TestReplace.java:18)
     at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
     at 
sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
     at 
sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
     at java.lang.reflect.Method.invoke(Method.java:502)
     at com.intellij.rt.execution.application.AppMain.main(AppMain.java:140)


Regards, Peter

> newLenHint = -500 --> OutOfMemoryError
> In other words, is this a good reason to throw such an Error?
>
> Little nit:
> Indentation for line continuation should be 8 spaces.
>
> -Ulf
>