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 5ebe419f3 Keep RandomStringUtils.random rejection cap from failing
valid ranges (#1843)
5ebe419f3 is described below
commit 5ebe419f3bffd4e451bcdf737dfe3d56871af821
Author: Gary Gregory <[email protected]>
AuthorDate: Wed Oct 28 07:15:33 2026 -0400
Keep RandomStringUtils.random rejection cap from failing valid ranges
(#1843)
Clarify RandomStringUtils rejection-cap assumptions and strengthen
tests.
Document the independence, uniformity, and remaining-length assumptions
behind the probability bound. Add regression tests for sparse code-point
ranges, counter resets, and all four rejection paths.
---
src/changes/changes.xml | 1 +
.../apache/commons/lang3/RandomStringUtils.java | 13 ++-
.../commons/lang3/RandomStringUtilsTest.java | 109 ++++++++++++++++++---
3 files changed, 102 insertions(+), 21 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index b77ce6dc2..748865b51 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -78,6 +78,7 @@ The <action> type attribute can be add,update,fix,remove.
<action type="fix" dev="ggregory" due-to="alhuda, Gary
Gregory">Restrict LocaleUtils.toLocale to ASCII language, country, and numeric
area codes; previously accepted non-ASCII codes now cause
IllegalArgumentException (#1838).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">Deprecate ExceptionUtils.removeCommonFrames(), which is now used only
by tests. Root-cause stack trace generation compares StackTraceElement objects
directly.</action>
<action type="fix" dev="ggregory" due-to="alhuda, Gary
Gregory">Keep DateUtils.ceiling and round inside a DST overlap hour
(#1842).</action>
+ <action type="fix" dev="ggregory" due-to="alhuda, Gary
Gregory">Keep RandomStringUtils.random rejection cap from failing valid ranges
(#1843).</action>
<!-- ADD -->
<action issue="LANG-1790" type="add" dev="ggregory" due-to="Mert Kirpici,
Ivan Šarić, Gary Gregory">Add optional FIFO ordering for TimedSemaphore
blocking acquisitions.</action>
<!-- UPDATE -->
diff --git a/src/main/java/org/apache/commons/lang3/RandomStringUtils.java
b/src/main/java/org/apache/commons/lang3/RandomStringUtils.java
index 03ce42d71..6a3d43f01 100644
--- a/src/main/java/org/apache/commons/lang3/RandomStringUtils.java
+++ b/src/main/java/org/apache/commons/lang3/RandomStringUtils.java
@@ -393,13 +393,12 @@ public static String random(int count, int start, int
end, final boolean letters
final long desiredCacheSize = ((long) count * gapBits +
CACHE_PADDING_BITS) / BITS_TO_BYTES_DIVISOR + BASE_CACHE_SIZE_PADDING;
final int cacheSize = (int) Math.min(desiredCacheSize,
Integer.MAX_VALUE / BITS_TO_BYTES_DIVISOR + BASE_CACHE_SIZE_PADDING);
final CachedRandomBits arb = new CachedRandomBits(cacheSize, random);
- // Bound rejection retries so a range that rejects every sample
- // (for example, entirely UNASSIGNED/PRIVATE_USE/SURROGATE) raises an
- // IllegalArgumentException instead of looping indefinitely. Each draw
- // takes gapBits bits, so a range holding a single acceptable value
- // accepts a draw with probability 1 / 2^gapBits; scaling the cap by
- // that sample space keeps a valid request from exhausting it (chance
- // below e^-64 per character). The counter resets on every accepted
code point.
+ // Bound consecutive rejected draws so impossible requests eventually
fail.
+ // Assuming independent uniform draws and at least one value
acceptable for
+ // the remaining output length, the acceptance probability is at least
+ // 1 / 2^gapBits. A budget of 64 times that sample space makes the
probability
+ // of exhausting the budget less than exp(-64) per accepted code point.
+ // Reset the counter after each accepted code point.
final long maxRejections = 64L << gapBits;
long rejections = 0;
while (count-- != 0) {
diff --git a/src/test/java/org/apache/commons/lang3/RandomStringUtilsTest.java
b/src/test/java/org/apache/commons/lang3/RandomStringUtilsTest.java
index 1a9a87089..d342ca0d0 100644
--- a/src/test/java/org/apache/commons/lang3/RandomStringUtilsTest.java
+++ b/src/test/java/org/apache/commons/lang3/RandomStringUtilsTest.java
@@ -493,20 +493,6 @@ void testOnlyRejectedCodePoints() {
() -> assertThrows(IllegalArgumentException.class, () ->
RandomStringUtils.random(1, 0xE000, 0xF900, false, false, null, new
Random(42))));
}
- /**
- * A range with a single acceptable value is valid and must not trip the
rejection cap. Here 63 of the 64 chars are rejected by the letters filter and
- * each draw takes 7 bits, so a draw is accepted with probability 1/128.
- */
- @Test
- void testSparseAcceptableValuesDoNotTripRejectionCap() {
- final char[] chars = new char[64];
- Arrays.fill(chars, '-');
- chars[63] = 'x';
- for (int seed = 0; seed < 20; seed++) {
- assertEquals(StringUtils.repeat('x', 100),
RandomStringUtils.random(100, 0, 64, true, false, chars, new Random(seed)));
- }
- }
-
/**
* Make sure boundary alpha characters are generated by randomAlphabetic
This test will fail randomly with probability = 4 * (51/52)**1000 ~ 1.58E-8
*/
@@ -1003,4 +989,99 @@ void testRandomWithChars(final RandomStringUtils rsu) {
assertNotEquals(r1, r3);
assertNotEquals(r2, r3);
}
+
+ /**
+ * Checks that rejected Unicode types and supplementary characters that
cannot fit in the remaining UTF-16 unit exhaust the retry budget.
+ *
+ * @param codePoint the code point supplied by every draw.
+ */
+ @ParameterizedTest
+ @ValueSource(ints = { 0x0378, 0xD800, 0xE000, 0x10000 })
+ void testRejectedCodePointWithControlledRandom(final int codePoint) {
+ final Random random = new Random(0) {
+ private int bytesGenerated;
+
+ @Override
+ public void nextBytes(final byte[] bytes) {
+ bytesGenerated += bytes.length;
+ assertTrue(bytesGenerated < 1_024, "The rejection cap did not
terminate generation");
+ Arrays.fill(bytes, (byte) 0);
+ }
+ };
+ // Each draw selects the sole code point: unassigned, surrogate,
private use, or an assigned supplementary letter.
+ assertThrows(IllegalArgumentException.class, () ->
RandomStringUtils.random(1, codePoint, codePoint + 1, false, false, null,
random));
+ }
+
+ /**
+ * Checks that accepting a character resets the consecutive-rejection
counter.
+ */
+ @Test
+ void testRejectionCapResetsAfterAcceptance() {
+ final char[] chars = new char[255];
+ Arrays.fill(chars, '-');
+ chars[1] = 'x';
+ final Random random = new Random(0) {
+ private int bytesGenerated;
+
+ @Override
+ public void nextBytes(final byte[] bytes) {
+ // Each byte is one draw: reject 10,000 times, then accept,
and repeat.
+ // Each run is below the 16,384 cap, but their combined length
exceeds it.
+ for (int i = 0; i < bytes.length; i++) {
+ bytes[i] = (byte) (++bytesGenerated % 10_001 == 0 ? 1 : 0);
+ }
+ }
+ };
+ assertEquals("xx", RandomStringUtils.random(2, 0, chars.length, true,
false, chars, random));
+ }
+
+ /**
+ * Checks that both filtered and out-of-range draws exhaust the retry
budget even when an acceptable value exists.
+ *
+ * @param rejectedValue the value supplied by every draw.
+ */
+ @ParameterizedTest
+ @ValueSource(ints = { 0, 255 })
+ void testRejectionCapWithControlledRandom(final int rejectedValue) {
+ final char[] chars = new char[255];
+ Arrays.fill(chars, '-');
+ chars[1] = 'x';
+ final Random random = new Random(0) {
+ private int bytesGenerated;
+
+ @Override
+ public void nextBytes(final byte[] bytes) {
+ bytesGenerated += bytes.length;
+ // Eight bits per draw; allow cache read-ahead beyond the
16,384-rejection budget.
+ assertTrue(bytesGenerated < 20_000, "The rejection cap did not
terminate generation");
+ Arrays.fill(bytes, (byte) rejectedValue);
+ }
+ };
+ assertThrows(IllegalArgumentException.class, () ->
RandomStringUtils.random(1, 0, chars.length, true, false, chars, random));
+ }
+
+ /**
+ * Checks a sparse code-point range containing 64 private-use characters
followed by one letter.
+ */
+ @Test
+ void testSparseAcceptableCodePointsDoNotTripRejectionCap() {
+ assertEquals(StringUtils.repeat('\uF900', 100),
RandomStringUtils.random(100, 0xF8C0, 0xF901, true, false, null, new
Random(0)));
+ }
+
+ /**
+ * Checks that a sparse character array succeeds for fixed seeds.
+ *
+ * <p>
+ * Here 63 of the 64 chars are rejected by the letters filter and each
draw takes 7 bits, so a uniform draw is accepted with probability 1/128.
+ * </p>
+ */
+ @Test
+ void testSparseAcceptableValuesDoNotTripRejectionCap() {
+ final char[] chars = new char[64];
+ Arrays.fill(chars, '-');
+ chars[63] = 'x';
+ for (int seed = 0; seed < 20; seed++) {
+ assertEquals(StringUtils.repeat('x', 100),
RandomStringUtils.random(100, 0, 64, true, false, chars, new Random(seed)));
+ }
+ }
}
