This is an automated email from the ASF dual-hosted git repository.
garydgregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-lang.git
The following commit(s) were added to refs/heads/master by this push:
new 4d053dc89 StrBuilder.indexOf materializes the whole builder as a
String per call; deleteAll/replaceAll multiply it into ~750 GB churn on a 1 MB
builder (f026).
4d053dc89 is described below
commit 4d053dc896df7c1165673637607fcc86a146eb10
Author: Gary Gregory <[email protected]>
AuthorDate: Sat Sep 5 15:34:08 2026 -0400
StrBuilder.indexOf materializes the whole builder as a String per call;
deleteAll/replaceAll multiply it into ~750 GB churn on a 1 MB builder
(f026).
---
src/changes/changes.xml | 1 +
.../apache/commons/lang3/CharSequenceUtils.java | 33 +++++++++-----
.../commons/lang3/CharSequenceUtilsTest.java | 52 ++++++++++++++++++++++
3 files changed, 76 insertions(+), 10 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 5f075851e..70dc9d021 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -275,6 +275,7 @@ java.lang.NullPointerException: Cannot invoke
<action type="fix" dev="ggregory" due-to="Gary
Gregory">ArrayUtils.addAll/insert length arithmetic overflows (undeclared
NegativeArraySizeException) while sibling concat is overflow-checked
(f023).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">FormattableUtils.append pads right-justified output with insert(0) per
char; O(width^2); '%500000s' costs ~1.25e11 char moves (f024).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">Attacker-controlled exception message forges frames in
getRootCauseStackTrace output AND suppresses all real frames, beyond cosmetic
log spoofing (f025).</action>
+ <action type="fix" dev="ggregory" due-to="Gary
Gregory">StrBuilder.indexOf materializes the whole builder as a String per
call; deleteAll/replaceAll multiply it into ~750 GB churn on a 1 MB builder
(f026).</action>
<!-- ADD -->
<action type="add" dev="ggregory" due-to="Gary
Gregory">Add JavaVersion.JAVA_27.</action>
<action type="add" dev="ggregory" due-to="Gary
Gregory">Add SystemUtils.IS_JAVA_27.</action>
diff --git a/src/main/java/org/apache/commons/lang3/CharSequenceUtils.java
b/src/main/java/org/apache/commons/lang3/CharSequenceUtils.java
index c86ed6f6e..2d07f55bb 100644
--- a/src/main/java/org/apache/commons/lang3/CharSequenceUtils.java
+++ b/src/main/java/org/apache/commons/lang3/CharSequenceUtils.java
@@ -63,6 +63,11 @@ private static boolean equalsIgnoreCase(final int cp1, final
int cp2) {
/**
* Used by the indexOf(CharSequence methods) as a green implementation of
indexOf.
+ * <p>
+ * {@link CharSequence} types without a dedicated branch are scanned in
place rather than materialized with {@code toString()}: for builder
+ * types (for example {@code org.apache.commons.lang3.text.StrBuilder}),
{@code toString()} copies the whole buffer, and callers that invoke
+ * this method once per occurrence (such as {@code deleteAll}/{@code
replaceAll}) would multiply that copy into allocation-quadratic churn.
+ * </p>
*
* @param cs The {@link CharSequence} to be processed.
* @param searchChar The {@link CharSequence} to be searched for.
@@ -82,16 +87,24 @@ static int indexOf(final CharSequence cs, final
CharSequence searchChar, final i
if (cs instanceof StringBuffer) {
return ((StringBuffer) cs).indexOf(searchChar.toString(), start);
}
- return cs.toString().indexOf(searchChar.toString(), start);
-// if (cs instanceof String && searchChar instanceof String) {
-// // TODO: Do we assume searchChar is usually relatively small;
-// // If so then calling toString() on it is better than
reverting to
-// // the green implementation in the else block
-// return ((String) cs).indexOf((String) searchChar, start);
-// } else {
-// // TODO: Implement rather than convert to String
-// return cs.toString().indexOf(searchChar.toString(), start);
-// }
+ // Direct scan without copying cs; matches the semantics of
String.indexOf(String, int).
+ final int len1 = cs.length();
+ final int len2 = searchChar.length();
+ final int from = Math.max(start, 0);
+ if (len2 == 0) {
+ return Math.min(from, len1);
+ }
+ if (len2 > len1 - from) {
+ return StringUtils.INDEX_NOT_FOUND;
+ }
+ final char char0 = searchChar.charAt(0);
+ final int max = len1 - len2;
+ for (int i = from; i <= max; i++) {
+ if (cs.charAt(i) == char0 && checkLaterThan1(cs, searchChar, len2,
i)) {
+ return i;
+ }
+ }
+ return StringUtils.INDEX_NOT_FOUND;
}
/**
diff --git a/src/test/java/org/apache/commons/lang3/CharSequenceUtilsTest.java
b/src/test/java/org/apache/commons/lang3/CharSequenceUtilsTest.java
index b45892533..e2b666572 100644
--- a/src/test/java/org/apache/commons/lang3/CharSequenceUtilsTest.java
+++ b/src/test/java/org/apache/commons/lang3/CharSequenceUtilsTest.java
@@ -206,6 +206,58 @@ void testLastIndexOfWithDifferentCharSequences(final
CharSequence cs, final Char
assertEquals(expected, CharSequenceUtils.lastIndexOf(cs, search,
start));
}
+ /**
+ * Tests that the direct-scan fallback in {@link
CharSequenceUtils#indexOf(CharSequence, CharSequence, int)} (taken by
CharSequence
+ * types without a dedicated dispatch branch, such as {@code
org.apache.commons.lang3.text.StrBuilder}) matches
+ * {@link String#indexOf(String, int)} semantics exactly and never
materializes the searched sequence via {@code toString()}.
+ */
+ @Test
+ void testNewIndexOf() {
+
testNewIndexOfSingle("808087847-1321060740-635567660180086727-925755305",
"-1321060740-635567660");
+ testNewIndexOfSingle("", "");
+ testNewIndexOfSingle("1", "");
+ testNewIndexOfSingle("", "1");
+ testNewIndexOfSingle("1", "1");
+ testNewIndexOfSingle("11", "1");
+ testNewIndexOfSingle("1", "11");
+ testNewIndexOfSingle("apache", "a");
+ testNewIndexOfSingle("apache", "p");
+ testNewIndexOfSingle("apache", "e");
+ testNewIndexOfSingle("apache", "x");
+ testNewIndexOfSingle("oraoraoraora", "r");
+ testNewIndexOfSingle("mudamudamudamuda", "d");
+ testNewIndexOfSingle("junk-ststarting", "starting");
+ // The searched sequence must not be copied by the fallback.
+ final CharSequence noToString = new WrapperString("hello world") {
+ @Override
+ public String toString() {
+ throw new AssertionError("cs.toString() must not be called by
indexOf");
+ }
+ };
+ assertEquals(6, CharSequenceUtils.indexOf(noToString, "world", 0));
+ assertEquals(-1, CharSequenceUtils.indexOf(noToString, "worlds", 0));
+ }
+
+ private void testNewIndexOfSingle(final CharSequence a, final CharSequence
b) {
+ final int maxa = Math.max(a.length(), b.length());
+ for (int i = -maxa - 10; i <= maxa + 10; i++) {
+ testNewIndexOfSingle(a, b, i);
+ }
+ testNewIndexOfSingle(a, b, Integer.MIN_VALUE);
+ testNewIndexOfSingle(a, b, Integer.MAX_VALUE);
+ }
+
+ private void testNewIndexOfSingle(final CharSequence a, final CharSequence
b, final int start) {
+ testNewIndexOfSingleSingle(a, b, start);
+ testNewIndexOfSingleSingle(b, a, start);
+ }
+
+ private void testNewIndexOfSingleSingle(final CharSequence a, final
CharSequence b, final int start) {
+ assertEquals(a.toString().indexOf(b.toString(), start),
+ CharSequenceUtils.indexOf(new WrapperString(a.toString()), new
WrapperString(b.toString()), start),
+ "testNewIndexOf fails! original : " + a + " seg : " + b + "
start : " + start);
+ }
+
@Test
void testNewLastIndexOf() {
testNewLastIndexOfSingle("808087847-1321060740-635567660180086727-925755305",
"-1321060740-635567660", 21);
