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 11e2dad29 Reflection builders' cycle registry unregisters per-visit:
cycle-SAFE but DAG-exponential, a 40-level reference diamond drives ~2^40
traversals and unbounded output (f032).
11e2dad29 is described below
commit 11e2dad29e2ae58d3bd604233af55183ccee1d17
Author: Gary Gregory <[email protected]>
AuthorDate: Sun Sep 6 16:48:51 2026 -0400
Reflection builders' cycle registry unregisters per-visit: cycle-SAFE
but DAG-exponential, a 40-level reference diamond drives ~2^40
traversals and unbounded output (f032).
---
src/changes/changes.xml | 1 +
.../commons/lang3/builder/EqualsBuilder.java | 12 +++
.../lang3/builder/RecursiveToStringStyle.java | 117 +++++++++++++++++++--
.../commons/lang3/builder/ToStringStyle.java | 39 +++++++
.../lang3/builder/RecursiveToStringStyleTest.java | 49 +++++++++
5 files changed, 212 insertions(+), 6 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 710f73ca3..ff1854cc8 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -278,6 +278,7 @@ java.lang.NullPointerException: Cannot invoke
<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>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">ThresholdCircuitBreaker accepts negative increments and overflows its
accumulator, silently keeping the breaker closed (f027).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">ExceptionUtils.getThrowableList() cycle check is O(n^2) over deep
cause chains; all chain-walking consumers inherit it (f031).</action>
+ <action type="fix" dev="ggregory" due-to="Gary
Gregory">Reflection builders' cycle registry unregisters per-visit: cycle-SAFE
but DAG-exponential, a 40-level reference diamond drives ~2^40 traversals and
unbounded output (f032).</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/builder/EqualsBuilder.java
b/src/main/java/org/apache/commons/lang3/builder/EqualsBuilder.java
index 0f726f518..075ea59c1 100644
--- a/src/main/java/org/apache/commons/lang3/builder/EqualsBuilder.java
+++ b/src/main/java/org/apache/commons/lang3/builder/EqualsBuilder.java
@@ -216,6 +216,14 @@ public static boolean reflectionEquals(final Object lhs,
final Object rhs, final
* {@link EqualsBuilder} recursively instead of invoking their
* {@code equals()} method. Leading to a deep reflection equals test.
*
+ * <p>Note on graph shape: the internal registry that prevents infinite
recursion on
+ * cyclic object graphs is a visit stack, not a visited set - object pairs
reachable
+ * more than once through shared (acyclic) references are re-compared on
every path.
+ * On deeply nested graphs with many shared references (reference
"diamonds"), the
+ * comparison cost can grow exponentially with nesting depth. Do not use
recursive
+ * reflection equality on object graphs built from untrusted input (for
example,
+ * graphs materialized by an identity-preserving deserializer).</p>
+ *
* @param lhs {@code this} object
* @param rhs The other object
* @param testTransients whether to include transient fields
@@ -1031,6 +1039,10 @@ public EqualsBuilder setReflectUpToClass(final Class<?>
reflectUpToClass) {
* String objects, which cache a hash value, are automatically excluded
from recursive testing.
* You may specify other exceptions by calling {@link
#setBypassReflectionClasses(List)}.
*
+ * <p>Cycle protection is a visit stack, not a visited set: shared
(acyclic) references are
+ * re-compared on every path, so deeply nested graphs with many shared
references can be
+ * exponentially expensive to compare. Avoid on object graphs built from
untrusted input.</p>
+ *
* @param testRecursive whether to do a recursive test
* @return {@code this} instance.
* @see #setBypassReflectionClasses(List)
diff --git
a/src/main/java/org/apache/commons/lang3/builder/RecursiveToStringStyle.java
b/src/main/java/org/apache/commons/lang3/builder/RecursiveToStringStyle.java
index 95695079a..6eb7854a5 100644
--- a/src/main/java/org/apache/commons/lang3/builder/RecursiveToStringStyle.java
+++ b/src/main/java/org/apache/commons/lang3/builder/RecursiveToStringStyle.java
@@ -18,14 +18,16 @@
import java.util.Collection;
import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.function.Supplier;
import org.apache.commons.lang3.ClassUtils;
import org.apache.commons.lang3.mutable.MutableBoolean;
/**
* Works with {@link ToStringBuilder} to create a "deep" {@code toString}.
- *
- * <p>To use this class write code as follows:</p>
+ * <p>
+ * To use this class write code as follows:
+ * </p>
*
* <pre>
* public class Job {
@@ -46,14 +48,51 @@
* }
* }
* </pre>
- *
- * <p>This will produce a toString of the format:
- * {@code
Person@7f54[name=Stephen,age=29,smoker=false,job=Job@43cd2[title=Manager]]}</p>
+ * <p>
+ * This will produce a toString of the format: {@code
Person@7f54[name=Stephen,age=29,smoker=false,job=Job@43cd2[title=Manager]]}
+ * </p>
+ * <p>
+ * Graph safety: within one top-level {@code toString()} call, each object is
rendered in detail at most once. A second (identity-equal) occurrence of an
object
+ * (whether through a true cycle or through a shared (acyclic) reference) is
rendered in the abbreviated {@code Object.toString()} format instead of being
+ * re-traversed. This keeps traversal cost linear in the size of the object
graph; without it, shared references (reference "diamonds") would be
re-traversed
+ * exponentially. An optional output-length limit can be set via {@link
RecursiveToStringStyle.Builder#setMaxOutputLength(int)}; once the produced
string
+ * reaches the limit, further nested objects are replaced by a {@code
"...<truncated>"} marker.
+ * </p>
*
* @since 3.2
*/
public class RecursiveToStringStyle extends ToStringStyle {
+ /**
+ * Builder for {@link RecursiveToStringStyle} instances.
+ */
+ public static class Builder implements Supplier<RecursiveToStringStyle> {
+
+ private int maxOutputLength;
+
+ private Builder() {
+ this.maxOutputLength = 0;
+ }
+
+ @Override
+ public RecursiveToStringStyle get() {
+ return new RecursiveToStringStyle(this);
+ }
+
+ /**
+ * Sets the maximum length the output buffer may reach before nested
objects are elided with {@link #TRUNCATED_TEXT}; {@code 0} (the default) means
+ * unlimited. This is a throttle, not an exact bound: objects already
being rendered may still append their shallow content.
+ *
+ * @param maxOutputLength once the produced string reaches this
length, further nested objects are replaced by a {@code "...<truncated>"}
marker;
+ * {@code 0} means unlimited.
+ * @return this builder for chaining.
+ */
+ public Builder setMaxOutputLength(final int maxOutputLength) {
+ this.maxOutputLength = maxOutputLength;
+ return this;
+ }
+ }
+
/**
* Required for serialization support.
*
@@ -62,9 +101,46 @@ public class RecursiveToStringStyle extends ToStringStyle {
private static final long serialVersionUID = 1L;
/**
- * Constructs a new instance.
+ * Marker appended in place of a nested object once {@link
#maxOutputLength} is reached.
+ */
+ private static final String TRUNCATED_TEXT = "...<truncated>";
+
+ /**
+ * Creates a new {@link Builder} for {@link RecursiveToStringStyle}
instances.
+ *
+ * @return a new {@link Builder} for {@link RecursiveToStringStyle}
instances.
+ */
+ public static Builder builder() {
+ return new Builder();
+ }
+
+ /**
+ * Maximum length the output buffer may reach before nested objects are
elided with
+ * {@link #TRUNCATED_TEXT}; {@code 0} (the default) means unlimited. This
is a throttle,
+ * not an exact bound: objects already being rendered may still append
their shallow content.
+ */
+ private final int maxOutputLength;
+
+ /**
+ * Constructs a new instance with no output-length limit.
*/
public RecursiveToStringStyle() {
+ this(RecursiveToStringStyle.builder());
+ }
+
+ private RecursiveToStringStyle(final Builder builder) {
+ this.maxOutputLength = builder.maxOutputLength;
+ }
+
+ /**
+ * Constructs a new instance with an output-length limit.
+ *
+ * @param maxOutputLength once the produced string reaches this length,
further nested
+ * objects are replaced by a {@code "...<truncated>"} marker;
{@code 0} means unlimited.
+ * @since 3.21.0
+ */
+ public RecursiveToStringStyle(final int maxOutputLength) {
+ this.maxOutputLength = maxOutputLength;
}
/**
@@ -108,4 +184,33 @@ public void appendDetail(final StringBuffer buffer, final
String fieldName, fina
super.appendDetail(buffer, fieldName, value);
}
}
+
+ /**
+ * {@inheritDoc}
+ *
+ * <p>In addition to the cycle check performed by the superclass, this
implementation keeps a
+ * per-thread set of objects already rendered in detail during the current
top-level call.
+ * Values that this style would traverse structurally (see {@link
#accept(Class)}) are rendered
+ * in detail at most once; later identity-equal occurrences are appended
in the abbreviated
+ * {@code Object.toString()} format. This bounds the traversal to one
visit per object, so
+ * shared (acyclic) references cannot cause exponential re-traversal. If
an output-length limit
+ * was configured and the buffer has reached it, a {@code
"...<truncated>"} marker is appended
+ * instead of the value.</p>
+ */
+ @Override
+ protected void appendInternal(final StringBuffer buffer, final String
fieldName, final Object value, final boolean detail) {
+ if (detail && value != null && accept(value.getClass())
+ && !(value instanceof Number || value instanceof Boolean ||
value instanceof Character)) {
+ if (isVisited(value)) {
+ appendCyclicObject(buffer, fieldName, value);
+ return;
+ }
+ if (maxOutputLength > 0 && buffer.length() >= maxOutputLength) {
+ buffer.append(TRUNCATED_TEXT);
+ return;
+ }
+ markVisited(value);
+ }
+ super.appendInternal(buffer, fieldName, value, detail);
+ }
}
diff --git a/src/main/java/org/apache/commons/lang3/builder/ToStringStyle.java
b/src/main/java/org/apache/commons/lang3/builder/ToStringStyle.java
index 703387f39..cef7745d4 100644
--- a/src/main/java/org/apache/commons/lang3/builder/ToStringStyle.java
+++ b/src/main/java/org/apache/commons/lang3/builder/ToStringStyle.java
@@ -589,6 +589,18 @@ private Object readResolve() {
* See LANG-792
*/
+ /**
+ * A per-thread set of objects already rendered in detail during the
current top-level
+ * {@code reflectionToString} call. Unlike {@link #REGISTRY}, which is a
depth-first visit
+ * <em>stack</em> (entries are removed when a visit completes) and
therefore only detects
+ * cycles, this set is only cleared when the top-level call completes.
Styles that recurse
+ * into arbitrary object graphs (see {@link RecursiveToStringStyle})
consult it so that shared
+ * (acyclic) references are detailed at most once per top-level call,
keeping traversal cost
+ * linear in the size of the object graph instead of exponential on
reference diamonds.
+ * Identity-based for the same reason as {@link #REGISTRY}. Empty unless
such a style is in use.
+ */
+ private static final ThreadLocal<IdentityHashMap<Object, Object>> VISITED
= ThreadLocal.withInitial(IdentityHashMap::new);
+
/**
* Gets the registry of objects being traversed by the {@code
reflectionToString} methods in the current thread.
*
@@ -608,6 +620,31 @@ static boolean isRegistered(final Object value) {
return getRegistry().containsKey(value);
}
+ /**
+ * Tests whether the given object has already been rendered in detail
during the current
+ * top-level {@code reflectionToString} call. Used by graph-recursing
styles to avoid
+ * exponential re-traversal of shared (acyclic) references.
+ *
+ * @param value The object to look up in the visited set.
+ * @return {@code true} if the object was already visited in this
top-level call.
+ */
+ static boolean isVisited(final Object value) {
+ return VISITED.get().containsKey(value);
+ }
+
+ /**
+ * Marks the given object as rendered in detail for the current top-level
+ * {@code reflectionToString} call. The mark is cleared when the top-level
call completes
+ * (when the visit stack in {@link #REGISTRY} empties).
+ *
+ * @param value The object to mark as visited.
+ */
+ static void markVisited(final Object value) {
+ if (value != null) {
+ VISITED.get().put(value, null);
+ }
+ }
+
/**
* Registers the given object. Used by the reflection methods to avoid
infinite loops.
*
@@ -634,6 +671,8 @@ static void unregister(final Object value) {
m.remove(value);
if (m.isEmpty()) {
REGISTRY.remove();
+ // The top-level reflectionToString call is complete: clear
the visited set as well.
+ VISITED.remove();
}
}
}
diff --git
a/src/test/java/org/apache/commons/lang3/builder/RecursiveToStringStyleTest.java
b/src/test/java/org/apache/commons/lang3/builder/RecursiveToStringStyleTest.java
index a1238623d..77a3599d0 100644
---
a/src/test/java/org/apache/commons/lang3/builder/RecursiveToStringStyleTest.java
+++
b/src/test/java/org/apache/commons/lang3/builder/RecursiveToStringStyleTest.java
@@ -17,11 +17,14 @@
package org.apache.commons.lang3.builder;
import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.HashMap;
+import java.util.List;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
@@ -154,6 +157,21 @@ void testLongArrayArray() {
assertEquals(baseStr + "[<null>]", new
ToStringBuilder(base).append((Object) array).toString());
}
+ /**
+ * With an output-length limit configured, nested objects past the limit
are elided with a
+ * clear truncation marker.
+ */
+ @Test
+ void testMaxOutputLengthTruncates() {
+ final List<Object> list = new ArrayList<>();
+ for (int i = 0; i < 100; i++) {
+ list.add(new ArrayList<>(Collections.singletonList("item" + i)));
+ }
+ final String s = new ToStringBuilder(base,
RecursiveToStringStyle.builder().setMaxOutputLength(200).get()).append("g",
list, true).toString();
+ assertTrue(s.contains("...<truncated>"), "Truncation marker expected:
" + s);
+ assertTrue(s.length() < 10_000, "Output must be throttled, was " +
s.length());
+ }
+
@Test
void testMutableWrapperArray() {
assertEquals(baseStr + "[{<null>,5,{3,6}}]",
@@ -231,4 +249,35 @@ void testPrimitiveWrapperArray() {
assertEquals(baseStr + "[{<null>,5,{true,false}}]",
new ToStringBuilder(base).append(new Object[] { null, base,
new Boolean[] { true, false } }).toString());
}
+
+ /**
+ * A shared (acyclic) reference is detailed once per top-level call; the
second occurrence
+ * is rendered in the abbreviated {@code Object.toString()} format instead
of re-traversed.
+ */
+ @Test
+ void testSharedReferenceDetailedOnce() {
+ final ArrayList<Object> shared = new
ArrayList<>(Collections.singletonList("x"));
+ final String sharedStr = "java.util.ArrayList@" +
Integer.toHexString(System.identityHashCode(shared));
+ assertEquals(baseStr + "[a=" + sharedStr + "{x},b=" + sharedStr + "]",
+ new ToStringBuilder(base).append("a", shared,
true).append("b", shared, true).toString());
+ }
+
+ /**
+ * A deep reference diamond (each level holding two references to the same
child) must be
+ * traversed in linear time and produce linear output. Without the
per-call visited set,
+ * this 40-level diamond would require ~2^40 traversals.
+ */
+ @Test
+ void testSharedReferenceDiamondIsLinear() {
+ List<Object> child = new
ArrayList<>(Collections.singletonList("leaf"));
+ for (int i = 0; i < 40; i++) {
+ final List<Object> parent = new ArrayList<>();
+ parent.add(child);
+ parent.add(child);
+ child = parent;
+ }
+ final String s = new ToStringBuilder(base).append("g", child,
true).toString();
+ assertTrue(s.contains("leaf"), "The graph content must still be
rendered");
+ assertTrue(s.length() < 100_000, "Output must be linear in graph size,
was " + s.length());
+ }
}
