View Javadoc
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 }