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
commit 581ce79c4d39571ac98db3e32b0d813540684324 Author: Gary Gregory <[email protected]> AuthorDate: Sun Jun 21 11:47:57 2026 +0000 [LANG-1824] Fix Strings.replace overflow on large replacements (#1716). - Add tests. - Javadoc - Better parameter names, internal method name. - Sort members. --- src/changes/changes.xml | 1 + .../java/org/apache/commons/lang3/Strings.java | 62 ++++++++++------------ .../java/org/apache/commons/lang3/StringsTest.java | 55 ++++++++++++++----- 3 files changed, 71 insertions(+), 47 deletions(-) diff --git a/src/changes/changes.xml b/src/changes/changes.xml index 2e2669c92..1770ce4a2 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -202,6 +202,7 @@ java.lang.NullPointerException: Cannot invoke <action type="fix" dev="ggregory" due-to="alhudz, Gary Gregory">Keep initials from splitting a supplementary code point (#1722).</action> <action type="fix" dev="ggregory" due-to="alhudz, Gary Gregory">Fix int overflow in DurationFormatUtils.formatPeriod (#1720).</action> <action type="fix" dev="ggregory" due-to="alhudz, Gary Gregory">Fix CsvUnescaper bounds error on a single quote field (#1723).</action> + <action issue="LANG-1824" type="fix" dev="ggregory" due-to="Dhruv Aggarwal, Gary Gregory">Fix Strings.replace overflow on large replacements (#1716).</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/Strings.java b/src/main/java/org/apache/commons/lang3/Strings.java index 8c552b561..213f4d1af 100644 --- a/src/main/java/org/apache/commons/lang3/Strings.java +++ b/src/main/java/org/apache/commons/lang3/Strings.java @@ -314,6 +314,30 @@ private static boolean eq(final Object o1, final Object o2) { return o1 == null ? o2 == null : o1.equals(o2); } + /** + * Computes a safe initial capacity for the {@link StringBuilder} used by {@link #replace(String, String, String, int)}. + * <p> + * Uses {@code long} arithmetic so that the estimated growth cannot overflow {@code int} when {@code replacementLength} is much greater than + * {@code searchLength}, and clamps the result to {@link ArrayUtils#SAFE_MAX_ARRAY_LENGTH} so that {@code new StringBuilder(int)} is never invoked with a + * value that exceeds the VM's array-size limit. + * </p> + * <p> + * The estimated number of matches is {@code 16} when {@code max} is negative (unbounded), otherwise {@code Math.min(max, 64)}. These multipliers preserve + * the historical behavior of the inlined estimate. + * </p> + * + * @param textLen The length of the input text, in characters. + * @param searchLen The length of the search string, in characters. + * @param replacementLen The length of the replacement string, in characters. + * @param max The maximum number of replacements, or {@code -1} for no maximum. + * @return A non-negative initial capacity, never greater than {@link ArrayUtils#SAFE_MAX_ARRAY_LENGTH}. + */ + static int initialCapacity(final int textLen, final int searchLen, final int replacementLen, final int max) { + final long perReplacementGrowth = Math.max((long) replacementLen - searchLen, 0L); + final long totalGrowth = perReplacementGrowth * (max < 0 ? 16 : Math.min(max, 64)); + return (int) Math.min((long) textLen + totalGrowth, ArrayUtils.SAFE_MAX_ARRAY_LENGTH); + } + /** * Ignores case when possible. */ @@ -1297,12 +1321,11 @@ public String replace(final String text, final String searchString, final String if (end == INDEX_NOT_FOUND) { return text; } - final int replLength = searchString.length(); - final int initialCapacity = computeInitialCapacity(text.length(), replLength, replacement.length(), max); - final StringBuilder buf = new StringBuilder(initialCapacity); + final int searchLen = searchString.length(); + final StringBuilder buf = new StringBuilder(initialCapacity(text.length(), searchLen, replacement.length(), max)); while (end != INDEX_NOT_FOUND) { buf.append(text, start, end).append(replacement); - start = end + replLength; + start = end + searchLen; if (--max == 0) { break; } @@ -1312,37 +1335,6 @@ public String replace(final String text, final String searchString, final String return buf.toString(); } - /** - * Computes a safe initial capacity for the {@link StringBuilder} used by - * {@link #replace(String, String, String, int)}. - * - * <p> - * Uses {@code long} arithmetic so that the estimated growth cannot overflow - * {@code int} when {@code replacementLength} is much greater than - * {@code searchLength}, and clamps the result to - * {@link ArrayUtils#SAFE_MAX_ARRAY_LENGTH} so that - * {@code new StringBuilder(int)} is never invoked with a value that exceeds - * the VM's array-size limit. - * </p> - * - * <p> - * The estimated number of matches is {@code 16} when {@code max} is negative - * (unbounded), otherwise {@code Math.min(max, 64)}. These multipliers - * preserve the historical behavior of the inlined estimate. - * </p> - * - * @param textLength the length of the input text, in characters. - * @param searchLength the length of the search string, in characters. - * @param replacementLength the length of the replacement string, in characters. - * @param max the maximum number of replacements, or {@code -1} for no maximum. - * @return a non-negative initial capacity, never greater than {@link ArrayUtils#SAFE_MAX_ARRAY_LENGTH}. - */ - static int computeInitialCapacity(final int textLength, final int searchLength, final int replacementLength, final int max) { - final long perReplacementGrowth = Math.max((long) replacementLength - searchLength, 0L); - final long totalGrowth = perReplacementGrowth * (max < 0 ? 16 : Math.min(max, 64)); - return (int) Math.min((long) textLength + totalGrowth, ArrayUtils.SAFE_MAX_ARRAY_LENGTH); - } - /** * Replaces a String with another String inside a larger String, once. * diff --git a/src/test/java/org/apache/commons/lang3/StringsTest.java b/src/test/java/org/apache/commons/lang3/StringsTest.java index 86cc467a3..db39ef8ee 100644 --- a/src/test/java/org/apache/commons/lang3/StringsTest.java +++ b/src/test/java/org/apache/commons/lang3/StringsTest.java @@ -72,18 +72,6 @@ void testCaseInsensitiveReplaceLengthChangingLowerCase() { assertEquals("X", Strings.CI.replaceOnce("İ", "İ", "X")); } - @Test - void testComputeInitialCapacityReplacementGrowthDoesNotOverflowInt() { - final int capacity = Strings.computeInitialCapacity(0, 0, 50_000_000, 64); - assertEquals(ArrayUtils.SAFE_MAX_ARRAY_LENGTH, capacity); - } - - @Test - void testComputeInitialCapacityNeverOverflowsForMaxValueInputs() { - final int capacity = Strings.computeInitialCapacity(Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 64); - assertEquals(ArrayUtils.SAFE_MAX_ARRAY_LENGTH, capacity); - } - /** * Expanding the existing test group {@link StringUtilsStartsEndsWithTest#testStartsWithAny()} to include case-insensitive cases */ @@ -111,6 +99,49 @@ void testCaseSensitiveConstant() { assertTrue(Strings.CS.isCaseSensitive()); } + @Test + void testComputeInitialCapacityDoesNotReturnSafeMaxDueToOverflow() { + final int textLength = 100; + final int searchLength = 0; + final int replacementLength = Integer.MAX_VALUE; + final int max = 1; + // Expected mathematical result: + // 100 + (2147483647 - 0) * 1 = 2147483747 + // which exceeds SAFE_MAX_ARRAY_LENGTH (2147483639) + final int expected = Integer.MAX_VALUE - 8; + assertEquals(expected, Strings.initialCapacity(textLength, searchLength, replacementLength, max)); + } + + @Test + void testComputeInitialCapacityLargeInputsDoNotIncorrectlyClampToSafeMax() { + final int result = Strings.initialCapacity(Integer.MAX_VALUE - 1000, Integer.MAX_VALUE - 500, Integer.MAX_VALUE, 1); + // Growth = 500 + // Expected = Integer.MAX_VALUE - 500 + assertEquals(Integer.MAX_VALUE - 500, result); + } + + @Test + void testComputeInitialCapacityNeverOverflowsForMaxValueInputs() { + final int capacity = Strings.initialCapacity(Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 64); + assertEquals(ArrayUtils.SAFE_MAX_ARRAY_LENGTH, capacity); + } + + @Test + void testComputeInitialCapacityReplacementGrowthDoesNotOverflowInt() { + final int capacity = Strings.initialCapacity(0, 0, 50_000_000, 64); + assertEquals(ArrayUtils.SAFE_MAX_ARRAY_LENGTH, capacity); + } + + @Test + void testComputeInitialCapacityReturnsSmallerValueWhenResultIsBelowSafeMax() { + final int textLength = 100; + final int searchLength = 0; + final int replacementLength = 1000; + final int max = 1; + final int expected = 1100; + assertEquals(expected, Strings.initialCapacity(textLength, searchLength, replacementLength, max)); + } + @ParameterizedTest @MethodSource("stringsFactory") void testEqualsCharSequence(final Strings strings) {
