gnodet-bot commented on code in PR #2153:
URL: https://github.com/apache/maven-resolver/pull/2153#discussion_r4071529122
##########
maven-resolver-util/src/test/java/org/eclipse/aether/util/graph/transformer/ConflictResolverTest.java:
##########
@@ -879,6 +879,75 @@ private static DependencyNode makeDependencyNode(
return node;
}
+ /**
+ * Regression test for exponential Path creation (OOM) in dense dependency
graphs.
+ * <p>
+ * Constructs a graph where N hub nodes 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 modules)
+ * </pre>
+ * Without the {@code expandedNodes} guard in {@link
PathConflictResolver}, each hub node
+ * would be expanded M times, causing exponential Path creation and
OutOfMemoryError.
+ * <p>
+ * The test also verifies that {@link PathConflictResolver} produces the
same resolution
+ * result as {@link ClassicConflictResolver} on this topology.
+ */
+ @ParameterizedTest
+ @MethodSource("conflictResolverSource")
+ void denseGraphDoesNotOom(ConflictResolver conflictResolver) throws
RepositoryException {
+ // 20 parents × 20 hubs = 400 edges; each hub reachable via 20 paths.
+ // Without the fix this creates ~20^20 Paths and OOMs instantly.
Review Comment:
⚠️ **Test topology does not exercise the `expandedNodes` guard**
The comment says "Without the fix this creates ~20^20 Paths and OOMs
instantly" but the math is wrong for this topology, and more importantly: **the
test would pass even if the `expandedNodes` guard were removed**.
The guard is inside `if (!children.isEmpty())`:
```java
if (!children.isEmpty()) {
List<Path> added = node.addChildren(children);
for (int i = added.size() - 1; i >= 0; i--) {
Path child = added.get(i);
Integer prevDepth = expandedNodes.get(child.dn);
if (prevDepth == null || child.depth < prevDepth) { // ← guard
expandedNodes.put(child.dn, child.depth);
stack.add(child);
}
}
}
```
Hub nodes (`hub-0` … `hub-19`) are leaf nodes — `getChildren()` returns
empty — so the `if (!children.isEmpty())` block is never entered for them. The
`expandedNodes` map is never consulted, and every hub Path is already in the
partition via `addChildren`. Without the fix, 20 parents × 20 hubs = 400 Path
objects (linear, not `20^20`), which would not OOM with any reasonable heap.
A test that actually validates the guard needs hub nodes that **have their
own shared children**. Example:
```java
// Add shared sub-hubs as children of each hub
List<DependencyNode> subHubs = new ArrayList<>(K);
for (int s = 0; s < K; s++) {
subHubs.add(makeDependencyNode("test", "sub-hub-" + s, "1.0"));
}
for (DependencyNode hub : hubs) {
hub.setChildren(new ArrayList<>(subHubs)); // shared instances
}
```
With M=20 parents, N=20 hubs, K=20 sub-hubs, each sharing instances:
- Without fix: 20 parents push 20 hubs → each hub pushes 20 sub-hubs →
20×20×20=8,000 sub-hub expansion entries on stack. The guard prevents
re-pushing hubs and sub-hubs at equal-or-deeper depth — demonstrating actual
exponential bounding.
Also fix the comment: with 2-level topology it is not `20^20` paths — that
would require 20 levels of shared recursion. With the proposed 3-level topology
above, without the fix you get 400 stack pushes for hubs and 8,000 for sub-hubs.
--
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]
