1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.lang3.builder;
19
20 import static org.junit.jupiter.api.Assertions.assertEquals;
21 import static org.junit.jupiter.api.Assertions.assertFalse;
22 import static org.junit.jupiter.api.Assertions.assertNull;
23 import static org.junit.jupiter.api.Assertions.assertTrue;
24
25 import java.util.ArrayList;
26 import java.util.LinkedHashMap;
27 import java.util.List;
28 import java.util.Map;
29 import java.util.function.BiFunction;
30 import java.util.function.Consumer;
31 import java.util.function.Supplier;
32 import java.util.stream.Stream;
33
34 import org.apache.commons.lang3.AbstractLangTest;
35 import org.apache.commons.lang3.ObjectUtils;
36 import org.apache.commons.lang3.StringUtils;
37 import org.junit.jupiter.api.AfterEach;
38 import org.junit.jupiter.params.ParameterizedTest;
39 import org.junit.jupiter.params.provider.Arguments;
40 import org.junit.jupiter.params.provider.MethodSource;
41
42 /**
43 * Tests cycle detection and repeated-reference abbreviation across complete outputs.
44 *
45 * <p>
46 * Detecting a reference to an object currently being rendered prevents infinite recursion, but does not prevent expanding a shared object again after its first
47 * rendering finishes. Recursive styles must retain visited state across nested builders and appends so each object is detailed at most once per output. The
48 * tests combine cycles with shared branches to exercise both requirements through reflection builders, manual builders, and direct style calls.
49 * </p>
50 *
51 * <p>
52 * Each graph is rendered twice with the same style to detect visited state leaking into a later output. Some cases leave an unrelated builder's root
53 * registered: completing the current output must release its state without waiting for the entire root registry to become empty.
54 * </p>
55 */
56 class ToStringBuilderCycleTest extends AbstractLangTest {
57
58 /**
59 * Supplies fields that reflection can render to distinguish a cycle edge from a shared branch.
60 *
61 * <p>
62 * The unique {@code id} lets tests count detailed renderings independently of identity hash codes and whitespace. The {@code next} and {@code shared}
63 * fields are read reflectively, so they do not need accessors or a custom {@code toString()} implementation.
64 * </p>
65 */
66 private static final class Node {
67
68 @SuppressWarnings("unused")
69 private final int id;
70 @SuppressWarnings("unused")
71 private Node next;
72 @SuppressWarnings("unused")
73 private Node shared;
74
75 /**
76 * Creates a node whose edges will be connected by the test.
77 *
78 * @param id the identifier used to count this node's detailed renderings.
79 */
80 private Node(final int id) {
81 this.id = id;
82 }
83 }
84
85 /**
86 * Selects the API that owns the output and must release its traversal state.
87 *
88 * <p>
89 * Reflection uses the graph itself as the root. Manual builders and direct calls use a separate root and append the graph as a named field. This difference
90 * accounts for the additional graph identity in a reflection output's prefix.
91 * </p>
92 */
93 private enum RenderMode {
94
95 REFLECTION((value, style) -> complete(new ReflectionToStringBuilder(value, style))),
96 MANUAL((value, style) -> complete(new ToStringBuilder(new Object(), style).append("graph", value))), DIRECT(ToStringBuilderCycleTest::renderDirect);
97
98 private final BiFunction<Object, ToStringStyle, String> renderer;
99
100 /**
101 * Associates an entry point with its rendering and completion checks.
102 *
103 * @param renderer the operation that completes one output for a graph and style.
104 */
105 RenderMode(final BiFunction<Object, ToStringStyle, String> renderer) {
106 this.renderer = renderer;
107 }
108 }
109
110 /**
111 * Supplies the recursive styles under test and the default style as a control for container cycle detection.
112 */
113 private enum Style {
114
115 DEFAULT(() -> ToStringStyle.DEFAULT_STYLE), RECURSIVE(RecursiveToStringStyle::new), MULTILINE(MultilineRecursiveToStringStyle::new);
116
117 private final Supplier<ToStringStyle> factory;
118
119 /**
120 * Associates a style with a supplier so mutable recursive styles are not shared between test cases.
121 *
122 * @param factory the style supplier; the default style can use its shared instance.
123 */
124 Style(final Supplier<ToStringStyle> factory) {
125 this.factory = factory;
126 }
127 }
128
129 /**
130 * Renders a graph twice and checks that each completed output releases its traversal state.
131 *
132 * <p>
133 * An optional abandoned builder leaves an unrelated root registered throughout both renderings. This exposes cleanup that incorrectly depends on an empty
134 * root registry. Repeating the same graph also exposes stale visited marks that would abbreviate its first occurrence in the next output.
135 * </p>
136 *
137 * @param graph the graph to render on both passes.
138 * @param kind the style to create and reuse.
139 * @param mode the rendering entry point.
140 * @param abandoned whether to keep an unrelated abandoned builder's root registered.
141 * @param assertions the output assertions to apply on each pass.
142 */
143 private static void assertRepeatedOutput(final Object graph, final Style kind, final RenderMode mode, final boolean abandoned,
144 final Consumer<String> assertions) {
145 final Object orphan = new Object();
146 if (abandoned) {
147 new ReflectionToStringBuilder(orphan, new RecursiveToStringStyle());
148 }
149 try {
150 final ToStringStyle style = kind.factory.get();
151 for (int repeat = 0; repeat < 2; repeat++) {
152 assertions.accept(mode.renderer.apply(graph, style));
153 // A completed output must release its state even when an unrelated root remains registered.
154 assertState(orphan, abandoned);
155 }
156 } finally {
157 ToStringStyle.unregister(orphan);
158 }
159 }
160
161 /**
162 * Checks that completed outputs leave no active or direct traversal and only the deliberately abandoned root, if any.
163 *
164 * @param orphan the unrelated registered root, ignored when {@code abandoned} is {@code false} and may then be {@code null}.
165 * @param abandoned whether the unrelated root should remain registered.
166 */
167 private static void assertState(final Object orphan, final boolean abandoned) {
168 assertNull(ToStringStyle.getActiveTraversal());
169 final Map<?, ?> direct = ToStringStyle.getDirectTraversals().get();
170 assertTrue(direct == null || direct.isEmpty(), "Completed direct output must release its traversal");
171 assertEquals(abandoned ? 1 : 0, ToStringStyle.getRegistry().size());
172 if (abandoned) {
173 assertTrue(ToStringStyle.getRegistry().containsKey(orphan));
174 }
175 }
176
177 /**
178 * Completes a builder and checks that both its visited state and root registration have been released.
179 *
180 * <p>
181 * The final unregister operation prevents a failed assertion from leaving the test root behind; the assertions run before that fallback cleanup.
182 * </p>
183 *
184 * @param builder the builder whose output is ready to complete.
185 * @return the completed output.
186 */
187 private static String complete(final ToStringBuilder builder) {
188 try {
189 final String output = builder.toString();
190 assertNull(builder.getTraversal().getVisited());
191 assertFalse(ToStringStyle.getRegistry().containsKey(builder.getObject()));
192 return output;
193 } finally {
194 ToStringStyle.unregister(builder.getObject());
195 }
196 }
197
198 /**
199 * Supplies long cycles that close at the root or at an interior node through each rendering entry point.
200 *
201 * @return combinations of both recursive styles, all entry points, depths of 32 and 64, cycle targets, and unrelated root registration.
202 */
203 static Stream<Arguments> longCycles() {
204 final List<Arguments> arguments = new ArrayList<>();
205 for (final Style style : new Style[] { Style.RECURSIVE, Style.MULTILINE }) {
206 for (final RenderMode mode : RenderMode.values()) {
207 for (final int depth : new int[] { 32, 64 }) {
208 for (final int backEdge : new int[] { 0, depth / 2 }) {
209 for (final boolean abandoned : new boolean[] { false, true }) {
210 arguments.add(Arguments.of(style, mode, depth, backEdge, abandoned));
211 }
212 }
213 }
214 }
215 }
216 return arguments.stream();
217 }
218
219 /**
220 * Supplies mixed container cycles for both recursive styles and the default style.
221 *
222 * @return combinations of styles, rendering entry points, and unrelated root registration.
223 */
224 static Stream<Arguments> mixedCycles() {
225 final List<Arguments> arguments = new ArrayList<>();
226 for (final Style style : Style.values()) {
227 for (final RenderMode mode : RenderMode.values()) {
228 for (final boolean abandoned : new boolean[] { false, true }) {
229 arguments.add(Arguments.of(style, mode, abandoned));
230 }
231 }
232 }
233 return arguments.stream();
234 }
235
236 /**
237 * Renders a graph using the direct style lifecycle and checks that {@code appendEnd()} unregisters its root.
238 *
239 * <p>
240 * These calls have no builder to own the traversal. They exercise the state associated with the output buffer between {@code appendStart()},
241 * {@code append()}, and {@code appendEnd()}.
242 * </p>
243 *
244 * @param graph the graph to append as a field of a separate root.
245 * @param style the style that manages the direct traversal.
246 * @return the completed output.
247 */
248 private static String renderDirect(final Object graph, final ToStringStyle style) {
249 final Object root = new Object();
250 final StringBuffer buffer = new StringBuffer();
251 try {
252 style.appendStart(buffer, root);
253 style.append(buffer, "graph", graph, Boolean.TRUE);
254 style.appendEnd(buffer, root);
255 assertFalse(ToStringStyle.getRegistry().containsKey(root));
256 return buffer.toString();
257 } finally {
258 ToStringStyle.unregister(root);
259 }
260 }
261
262 /**
263 * Checks for leaked state before clearing root registrations and active and direct traversal state for subsequent tests.
264 */
265 @AfterEach
266 void tearDown() {
267 try {
268 assertState(null, false);
269 } finally {
270 // Keep a failed cycle assertion from contaminating subsequent tests on this thread.
271 new ArrayList<>(ToStringStyle.getRegistry().keySet()).forEach(ToStringStyle::unregister);
272 ToStringStyle.endStyleTraversal(true);
273 ToStringStyle.getDirectTraversals().remove();
274 }
275 }
276
277 /**
278 * Tests a long chain whose final edge closes a cycle and whose nodes all share a reference to the middle node.
279 *
280 * <p>
281 * Each identifier must occur in detail exactly once. Cycle-closing edges and subsequent shared references must be abbreviated; merely terminating without a
282 * stack overflow would not detect redundant expansion of the shared branch. Both renderings must satisfy the same assertions and release their traversal
283 * state, including when an unrelated root remains registered.
284 * </p>
285 *
286 * @param style the recursive style to exercise.
287 * @param mode the rendering entry point.
288 * @param depth the number of distinct nodes in the chain.
289 * @param backEdge the index targeted by the final node's {@code next} reference.
290 * @param abandoned whether an unrelated abandoned builder's root remains registered.
291 */
292 @ParameterizedTest(name = "{0}, {1}, depth={2}, backEdge={3}, abandoned={4}")
293 @MethodSource("longCycles")
294 void testLongCycleWithSharedBranches(final Style style, final RenderMode mode, final int depth, final int backEdge, final boolean abandoned) {
295 final Node[] nodes = new Node[depth];
296 for (int i = 0; i < depth; i++) {
297 nodes[i] = new Node(i);
298 }
299 for (int i = 0; i < depth - 1; i++) {
300 nodes[i].next = nodes[i + 1];
301 }
302 nodes[depth - 1].next = nodes[backEdge];
303 for (final Node node : nodes) {
304 node.shared = nodes[depth / 2];
305 }
306 assertRepeatedOutput(nodes[0], style, mode, abandoned, output -> {
307 // Every node is detailed once. Closing the cycle and following shared branches must use abbreviated references.
308 for (int i = 0; i < depth; i++) {
309 assertEquals(1, StringUtils.countMatches(output, "id=" + i + ","), "Node " + i + " must be detailed exactly once");
310 }
311 assertTrue(output.contains("next=" + ObjectUtils.identityToString(nodes[backEdge])));
312 assertTrue(output.length() < 1_000_000, "Cycle output must remain bounded");
313 });
314 }
315
316 /**
317 * Tests an {@code array -> list -> map -> array} cycle with a child shared by the list and map.
318 *
319 * <p>
320 * The cycle must close with one reference to the array's identity; reflection adds a second occurrence in the root prefix. The shared child's identity must
321 * occur twice. Recursive styles must detail that child only once, while the default style uses its inherited {@code Object.toString()} on both occurrences.
322 * These assertions check that cycle detection and visited state survive transitions between container types.
323 * </p>
324 *
325 * @param style the style to exercise, including the default style as a control.
326 * @param mode the rendering entry point.
327 * @param abandoned whether an unrelated abandoned builder's root remains registered.
328 */
329 @ParameterizedTest(name = "{0}, {1}, abandoned={2}")
330 @MethodSource("mixedCycles")
331 void testMixedArrayCollectionMapCycle(final Style style, final RenderMode mode, final boolean abandoned) {
332 final Object[] graph = new Object[1];
333 final List<Object> list = new ArrayList<>();
334 final Map<String, Object> map = new LinkedHashMap<>();
335 final Node shared = new Node(999);
336 graph[0] = list;
337 list.add(map);
338 list.add(shared);
339 map.put("back", graph);
340 map.put("shared", shared);
341 assertRepeatedOutput(graph, style, mode, abandoned, output -> {
342 // The array -> list -> map -> array cycle closes with an identity reference, not another expansion.
343 final String graphIdentity = ObjectUtils.identityToString(graph);
344 assertEquals(mode == RenderMode.REFLECTION ? 2 : 1, StringUtils.countMatches(output, graphIdentity));
345 final String childIdentity = ObjectUtils.identityToString(shared);
346 assertEquals(2, StringUtils.countMatches(output, childIdentity));
347 // Recursive styles detail the shared child once; the default style uses its own Object.toString() both times.
348 assertEquals(style == Style.DEFAULT ? 0 : 1, StringUtils.countMatches(output, childIdentity + "["));
349 assertTrue(output.length() < 10_000, "Mixed cycle output must remain bounded");
350 });
351 }
352 }