String: reimplement replace(CharSequence, CharSequence).
We're not using regexes any longer. Performance is now on par
with Android M.
This change also adds basic unit-tests, which we were lacking so far.
Android M
---------
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceNonExistent, vm=default, parameters={s=EMPTY}}
runtime(ns): min=33.49, 1st qu.=33.85, median=34.10, mean=34.22, 3rd qu.=34.55, max=35.09
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceNonExistent, vm=default, parameters={s=L_16}}
runtime(ns): min=48.58, 1st qu.=48.98, median=49.20, mean=49.51, 3rd qu.=49.83, max=51.75
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceNonExistent, vm=default, parameters={s=L_64}}
runtime(ns): min=236.04, 1st qu.=236.82, median=238.75, mean=239.42, 3rd qu.=241.72, max=243.95
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceNonExistent, vm=default, parameters={s=L_256}}
runtime(ns): min=921.01, 1st qu.=924.97, median=932.92, mean=934.84, 3rd qu.=940.41, max=964.41
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSingleSequence, vm=default, parameters={s=EMPTY}}
runtime(ns): min=33.87, 1st qu.=34.10, median=34.26, mean=34.33, 3rd qu.=34.51, max=35.00
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSingleSequence, vm=default, parameters={s=L_16}}
runtime(ns): min=695.64, 1st qu.=747.74, median=780.07, mean=792.92, 3rd qu.=860.18, max=860.55
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSingleSequence, vm=default, parameters={s=L_64}}
runtime(ns): min=2719.39, 1st qu.=2758.88, median=2778.37, mean=2901.49, 3rd qu.=2858.23, max=3782.71
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSingleSequence, vm=default, parameters={s=L_256}}
runtime(ns): min=12814.17, 1st qu.=12831.58, median=12938.24, mean=12973.31, 3rd qu.=13051.15, max=13359.51
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceRepeated, vm=default, parameters={s=EMPTY}}
runtime(ns): min=33.50, 1st qu.=33.65, median=34.00, mean=34.20, 3rd qu.=34.74, max=35.20
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceRepeated, vm=default, parameters={s=L_16}}
runtime(ns): min=48.51, 1st qu.=49.01, median=49.37, mean=49.41, 3rd qu.=49.86, max=50.25
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceRepeated, vm=default, parameters={s=L_64}}
runtime(ns): min=2536.89, 1st qu.=2687.66, median=2726.48, mean=2726.00, 3rd qu.=2774.11, max=2898.73
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceRepeated, vm=default, parameters={s=L_256}}
runtime(ns): min=9524.14, 1st qu.=9673.23, median=10163.81, mean=10062.96, 3rd qu.=10375.81, max=10594.24
Android N
---------
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceNonExistent, vm=default, parameters={s=EMPTY}}
runtime(ns): min=32.09, 1st qu.=32.33, median=32.53, mean=32.63, 3rd qu.=33.01, max=33.22
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceNonExistent, vm=default, parameters={s=L_16}}
runtime(ns): min=48.92, 1st qu.=49.12, median=50.11, mean=50.52, 3rd qu.=52.44, max=52.98
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceNonExistent, vm=default, parameters={s=L_64}}
runtime(ns): min=251.74, 1st qu.=253.67, median=255.06, mean=255.81, 3rd qu.=257.76, max=262.20
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceNonExistent, vm=default, parameters={s=L_256}}
runtime(ns): min=915.08, 1st qu.=923.41, median=926.69, mean=926.91, 3rd qu.=932.22, max=935.61
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceRepeated, vm=default, parameters={s=EMPTY}}
runtime(ns): min=32.09, 1st qu.=32.53, median=32.64, mean=32.73, 3rd qu.=33.03, max=33.16
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceRepeated, vm=default, parameters={s=L_16}}
runtime(ns): min=49.25, 1st qu.=51.35, median=51.91, mean=51.78, 3rd qu.=52.60, max=53.11
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceRepeated, vm=default, parameters={s=L_64}}
runtime(ns): min=2422.00, 1st qu.=2457.65, median=2536.93, mean=2534.74, 3rd qu.=2600.31, max=2662.56
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSequenceRepeated, vm=default, parameters={s=L_256}}
runtime(ns): min=9604.40, 1st qu.=9690.33, median=9935.53, mean=10176.73, 3rd qu.=10554.54, max=11774.79
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSingleSequence, vm=default, parameters={s=EMPTY}}
runtime(ns): min=31.97, 1st qu.=32.20, median=32.54, mean=32.58, 3rd qu.=32.90, max=33.40
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSingleSequence, vm=default, parameters={s=L_16}}
runtime(ns): min=657.99, 1st qu.=673.30, median=707.95, mean=717.83, 3rd qu.=752.64, max=794.76
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSingleSequence, vm=default, parameters={s=L_64}}
runtime(ns): min=2553.89, 1st qu.=2583.49, median=2675.01, mean=2698.93, 3rd qu.=2724.23, max=3105.93
Experiment {instrument=runtime, benchmarkMethod=timeReplaceSingleSequence, vm=default, parameters={s=L_256}}
runtime(ns): min=9669.46, 1st qu.=9958.64, median=10113.85, mean=10363.71, 3rd qu.=10331.31, max=12721.61
bug: 28060800
Change-Id: I98b73231af3df575840754fad68cbc5542f1b9ab
diff --git a/luni/src/test/java/libcore/java/lang/StringTest.java b/luni/src/test/java/libcore/java/lang/StringTest.java
index 63f991e..07f89c8 100644
--- a/luni/src/test/java/libcore/java/lang/StringTest.java
+++ b/luni/src/test/java/libcore/java/lang/StringTest.java
@@ -16,8 +16,6 @@
package libcore.java.lang;
-import java.lang.reflect.Field;
-import java.lang.reflect.Modifier;
import java.nio.ByteBuffer;
import java.nio.CharBuffer;
import java.nio.ReadOnlyBufferException;
@@ -317,6 +315,24 @@
assertEquals("-h-e-l-l-o- -w-o-r-l-d-", "hello world".replace("", "-"));
assertEquals("-w-o-r-l-d-", "hello world".substring(6).replace("", "-"));
assertEquals("-*-w-*-o-*-r-*-l-*-d-*-", "hello world".substring(6).replace("", "-*-"));
+
+ // Replace on an empty string with an empty target should insert the pattern
+ // precisely once.
+ assertEquals("", "".replace("", ""));
+ assertEquals("food", "".replace("", "food"));
+ }
+
+ public void test_replace() {
+ // Replace on an empty string is a no-op.
+ assertEquals("", "".replace("foo", "bar"));
+ // Replace on a string which doesn't contain the target sequence is a no-op.
+ assertEquals("baz", "baz".replace("foo", "bar"));
+ // Test that we iterate forward on the string.
+ assertEquals("mmmba", "bababa".replace("baba", "mmm"));
+ // Test replacements at the end of the string.
+ assertEquals("foodie", "foolish".replace("lish", "die"));
+ // Test a string that has multiple replacements.
+ assertEquals("hahahaha", "kkkk".replace("k", "ha"));
}
public void test_String_getBytes() throws Exception {
diff --git a/ojluni/src/main/java/java/lang/String.java b/ojluni/src/main/java/java/lang/String.java
index 5023da8..af87e28 100755
--- a/ojluni/src/main/java/java/lang/String.java
+++ b/ojluni/src/main/java/java/lang/String.java
@@ -1595,11 +1595,7 @@
* is the string being searched for.
*
* @param source the characters being searched.
- * @param sourceOffset offset of the source string.
- * @param sourceCount count of the source string.
* @param target the characters being searched for.
- * @param targetOffset offset of the target string.
- * @param targetCount count of the target string.
* @param fromIndex the index to begin searching from.
*/
static int indexOf(String source,
@@ -2167,8 +2163,64 @@
* @since 1.5
*/
public String replace(CharSequence target, CharSequence replacement) {
- return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
- this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
+ if (target == null) {
+ throw new NullPointerException("target == null");
+ }
+
+ if (replacement == null) {
+ throw new NullPointerException("replacement == null");
+ }
+
+ String replacementStr = replacement.toString();
+ String targetStr = target.toString();
+
+ // Special case when target == "". This is a pretty nonsensical transformation and nobody
+ // should be hitting this.
+ //
+ // See commit 870b23b3febc85 and http://code.google.com/p/android/issues/detail?id=8807
+ // An empty target is inserted at the start of the string, the end of the string and
+ // between all characters.
+ if (targetStr.isEmpty()) {
+ // Note that overallocates by |replacement.size()| if |this| is the empty string, but
+ // that should be a rare case within an already nonsensical case.
+ StringBuilder sb = new StringBuilder(replacementStr.length() * (count + 2) + count);
+ sb.append(replacementStr);
+ for (int i = 0; i < count; ++i) {
+ sb.append(charAt(i));
+ sb.append(replacementStr);
+ }
+
+ return sb.toString();
+ }
+
+ // This is the "regular" case.
+ int lastMatch = 0;
+ StringBuilder sb = null;
+ for (;;) {
+ int currentMatch = indexOf(this, targetStr, lastMatch);
+ if (currentMatch == -1) {
+ break;
+ }
+
+ if (sb == null) {
+ sb = new StringBuilder(count);
+ }
+
+ for (int i = lastMatch; i < currentMatch; ++i) {
+ sb.append(charAt(i));
+ }
+ sb.append(replacementStr);
+ lastMatch = currentMatch + targetStr.count;
+ }
+
+ if (sb != null) {
+ for (int i = lastMatch; i < count; ++i) {
+ sb.append(charAt(i));
+ }
+ return sb.toString();
+ } else {
+ return this;
+ }
}
/**
