gnodet-bot commented on code in PR #2153:
URL: https://github.com/apache/maven-resolver/pull/2153#discussion_r4071726157
##########
maven-resolver-util/src/test/java/org/eclipse/aether/util/graph/transformer/ConflictResolverTest.java:
##########
@@ -879,6 +879,88 @@ private static DependencyNode makeDependencyNode(
return node;
}
+ /**
+ * Regression test for exponential Path creation (OOM) in dense dependency
graphs.
+ * <p>
+ * Constructs a 3-level graph where hub nodes (which have their own shared
children)
+ * are each reachable via M distinct parent paths:
+ * <pre>
+ * root → p0, p1, … p(M-1) (M parent modules)
+ * each pi → hub0, hub1, … hub(N-1) (N shared hub nodes, with
children)
+ * each hub → sub0, sub1, … sub(K-1) (K shared sub-hub leaf nodes)
+ * </pre>
+ * Without the {@code expandedNodes} guard in {@link
PathConflictResolver#gatherCRNodes},
+ * each hub node would be pushed onto the expansion stack M times (once
per parent),
+ * causing its K sub-hubs to be expanded M times each — M×N×K stack
entries instead of N+K.
+ * With M=N=K=20 that is 20×20×20=8,000 redundant expansions for sub-hubs
alone, and
+ * grows polynomially with more levels. The guard prevents this by
skipping re-expansion
+ * of a node already expanded at the same or shallower depth.
+ */
+ @ParameterizedTest
+ @MethodSource("conflictResolverSource")
+ void denseGraphDoesNotOom(ConflictResolver conflictResolver) throws
RepositoryException {
Review Comment:
⚠️ **Test parameters too small to detect OOM regression**
The 3-level topology is now correct — hubs have children, so the
`expandedNodes` guard is actually exercised. But with `M=N=K=20`, the
pathological case without the guard produces at most `M×N = 400` hub-expansion
stack entries and `M×N×K = 8,000` sub-hub entries. That's trivially fast and
uses negligible memory. If someone removes the `expandedNodes` guard tomorrow,
this test still passes — it only validates correctness (all nodes survive), not
the memory bound.
To make this a genuine regression guard, either bump the parameters so the
un-fixed path is slow/OOM on CI heap, or assert on a proxy for expansion count
(e.g. a counter injected into `gatherCRNodes`, or a `@Timeout` that would
expire on the pathological case). A practical approach:
```suggestion
int M = 50; // parent modules
int N = 50; // hub modules (shared, each with children)
int K = 50; // sub-hub leaf modules (shared across hubs)
```
With `M=N=K=50`, without the fix: `50×50 = 2,500` hub expansions and
`50×50×50 = 125,000` sub-hub stack entries — still not an OOM, but slow enough
that adding a `@Timeout(value = 5, unit = TimeUnit.SECONDS)` would fail
reliably. Alternatively, use a counter that asserts the fix's O(N+K) expansion
bound:
```java
// Assert expansion is bounded — without the fix this would be M*N*K
assertTrue(expandedNodes.size() <= N + K, "expandedNodes grew beyond
O(N+K)");
```
(The `expandedNodes` field is `private` so this requires either
package-private test access or a subclass hook — but the intent is clear.)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
