You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@maven.apache.org by cs...@apache.org on 2026/10/12 16:50:34 UTC
(maven-resolver) branch master updated: Fix PathConflictResolver: use BFS to guarantee correct depth ordering in expandedNodes guard (#2175)
This is an automated email from the ASF dual-hosted git repository.
cstamas pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/maven-resolver.git
The following commit(s) were added to refs/heads/master by this push:
new 9add368cc Fix PathConflictResolver: use BFS to guarantee correct depth ordering in expandedNodes guard (#2175)
9add368cc is described below
commit 9add368cc96b0e2599ce4c0290cdb6b8bf8abceb
Author: Guillaume Nodet <gn...@gmail.com>
AuthorDate: Mon Oct 12 18:50:29 2026 +0200
Fix PathConflictResolver: use BFS to guarantee correct depth ordering in expandedNodes guard (#2175)
## Problem
`PathConflictResolver` introduced an OOM fix in #2153 (v2.0.24) using an `expandedNodes` guard to prevent exponential `Path` allocation on dense graphs. The guard tracks the minimum depth at which each `DependencyNode` instance was expanded. However, it used **DFS (LIFO stack)** traversal, which does not guarantee that a shared `DependencyNode` instance is first seen at its minimum depth.
In real Maven builds, the resolver's `DataPool` caches and reuses `List<DependencyNode>` children across multiple parent paths at different depths (via `getChildren`/`putChildren`). When the same `DependencyNode` instance appears at depth D and D' < D, DFS may process the deeper occurrence first — recording depth D in `expandedNodes`. When the shallower occurrence (depth D') is later encountered, the guard detects D' < D and **re-enqueues** the node, creating duplicate partition entri [...]
This caused the `MavenITmng0095ReactorFailureBehaviorTest` ITs to fail with Maven 4 after the 2.0.24 bump.
## Fix
Switch `gatherCRNodes` from **DFS (LIFO `ArrayList`)** to **BFS (FIFO `ArrayDeque`)**. BFS processes nodes level-by-level, guaranteeing the first dequeue of any `DependencyNode` is at its **minimum reachable depth**. The `expandedNodes` guard then correctly suppresses all deeper/equal occurrences without re-enqueueing — producing exactly one partition entry per child at the correct (shallowest) depth, matching `NearestVersionSelector` semantics.
The OOM prevention property is preserved: each `DependencyNode` instance is still expanded **exactly once**, keeping the total `Path` count at O(unique nodes × max-degree).
## Verification
- All 467 `maven-resolver-util` tests pass
- Built Maven 4.1.0-SNAPSHOT with `2.0.25-SNAPSHOT` resolver and ran `MavenITmng0095ReactorFailureBehaviorTest` locally: **3/3 pass** (`testitFailAtEnd`, `testitFailFast`, `testitFailNever`)
- Two new regression tests for shared `DependencyNode` correctness added to `ConflictResolverTest`
Fixes regression introduced in #2153 / v2.0.24.
---
.../graph/transformer/PathConflictResolver.java | 47 +++++----
.../graph/transformer/ConflictResolverTest.java | 105 +++++++++++++++++++++
2 files changed, 135 insertions(+), 17 deletions(-)
diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java
index 06396cc72..74cd91edc 100644
--- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java
+++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java
@@ -18,9 +18,11 @@
*/
package org.eclipse.aether.util.graph.transformer;
+import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
+import java.util.Deque;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.List;
@@ -304,11 +306,12 @@ public final class PathConflictResolver extends ConflictResolver {
* (i.e. its children visited) during {@link #gatherCRNodes(Path)}. Used to bound subtree
* re-traversal in highly connected graphs.
* <p>
- * When the same {@link DependencyNode} is reached again via a different parent path, a
- * {@link Path} entry is always created for it (so all occurrences appear in the conflict
- * partition for winner selection). The subtree is only re-expanded if the new occurrence
- * is at a strictly shallower depth than the recorded minimum — ensuring that the shallowest
- * reachable occurrence drives expansion, while deeper duplicates are skipped.
+ * Because {@link #gatherCRNodes(Path)} uses BFS, nodes are always dequeued in non-decreasing
+ * depth order. The first time a {@link DependencyNode} is dequeued, it is at its minimum
+ * reachable depth — that occurrence's subtree is expanded and recorded here. All subsequent
+ * encounters of the same {@link DependencyNode} instance (at equal or greater depth) are
+ * skipped: a {@link Path} entry is still created for them (so all occurrences appear in the
+ * conflict partition for winner selection), but their subtrees are not re-traversed.
* <p>
* Without this guard, a highly connected graph where node X is reachable via N different
* parents causes X's subtree to be expanded N times, leading to exponential {@link Path}
@@ -360,38 +363,48 @@ public final class PathConflictResolver extends ConflictResolver {
/**
* Iteratively builds {@link Path} graph by observing each node associated {@link DependencyNode}.
- * Uses an explicit stack instead of recursion to avoid {@link StackOverflowError} on very deep
+ * Uses an explicit queue (BFS) instead of recursion to avoid {@link StackOverflowError} on very deep
* dependency graphs (reported in large multi-module projects with 13+ levels of recursion).
* <p>
+ * BFS is essential for correctness of the subtree-deduplication guard: because BFS processes nodes
+ * level by level, the first time a {@link DependencyNode} instance is dequeued it is always at its
+ * minimum reachable depth. The {@code expandedNodes} guard can therefore safely skip re-expansion of
+ * the same {@link DependencyNode} at equal or deeper depth, knowing that the first expansion already
+ * captured the shallowest (and thus winning) path's subtree.
+ * <p>
+ * With DFS the same guarantee does not hold: a node can be pushed onto the stack at depth D from
+ * one parent, then pushed again at depth D'<D from a second parent before the first push is
+ * popped — causing the deeper occurrence to be expanded first, recording depth D in
+ * {@code expandedNodes}, and then incorrectly suppressing re-expansion at the shallower depth D'.
+ * <p>
* Subtree expansion of each {@link DependencyNode} instance is bounded: when the same node is
* reached again via a different parent path, a {@link Path} entry is still created for it (so
* all occurrences appear in the conflict partition for winner selection), but its subtree is only
- * re-traversed if reached at a strictly shallower depth than before. This prevents exponential
+ * traversed once — from the shallowest (earliest-seen by BFS) occurrence. This prevents exponential
* {@link Path} creation in highly connected graphs (e.g. a 813-module reactor where each module
* depends on ~9 others).
*/
private void gatherCRNodes(Path root) throws RepositoryException {
- ArrayList<Path> stack = new ArrayList<>();
- stack.add(root);
- while (!stack.isEmpty()) {
- Path node = stack.remove(stack.size() - 1);
+ Deque<Path> queue = new ArrayDeque<>();
+ queue.add(root);
+ while (!queue.isEmpty()) {
+ Path node = queue.remove();
List<DependencyNode> children = node.dn.getChildren();
if (!children.isEmpty()) {
// add children; we will get back those really added (not causing cycles)
List<Path> added = node.addChildren(children);
- // push in reverse order so first child is processed first (DFS order),
- // but only if this DependencyNode instance hasn't been expanded at a shallower depth
- for (int i = added.size() - 1; i >= 0; i--) {
- Path child = added.get(i);
+ // enqueue in natural order (BFS); skip subtree expansion if this DependencyNode
+ // instance was already expanded at an equal or shallower depth
+ for (Path child : added) {
Integer prevDepth = expandedNodes.get(child.dn);
if (prevDepth == null || child.depth < prevDepth) {
expandedNodes.put(child.dn, child.depth);
- stack.add(child);
+ queue.add(child);
}
// else: child.dn was already expanded at an equal or shallower depth;
// the Path is already in the partition (created by addChildren), but we
// skip re-expanding its subtree since the existing expansion already covered
- // all reachable descendants.
+ // all reachable descendants at the correct (nearest) depth.
}
}
}
diff --git a/maven-resolver-util/src/test/java/org/eclipse/aether/util/graph/transformer/ConflictResolverTest.java b/maven-resolver-util/src/test/java/org/eclipse/aether/util/graph/transformer/ConflictResolverTest.java
index ff52d3459..d0f6ccca5 100644
--- a/maven-resolver-util/src/test/java/org/eclipse/aether/util/graph/transformer/ConflictResolverTest.java
+++ b/maven-resolver-util/src/test/java/org/eclipse/aether/util/graph/transformer/ConflictResolverTest.java
@@ -860,6 +860,111 @@ public final class ConflictResolverTest extends AbstractConflictResolverTest {
assertSame(baz1Node, fooNode.getChildren().get(1));
}
+ /**
+ * Regression test: shared {@link DependencyNode} instance reachable at depth 1 and depth 2.
+ * With DFS traversal the depth-2 path was expanded first, causing {@code expandedNodes} to
+ * record depth 2 for the shared node. When the depth-1 path was later processed, the guard
+ * allowed re-expansion — but a subsequent loser {@code push()} on the depth-2 parent removed
+ * the shared node's children from the actual {@link DependencyNode} graph, corrupting the
+ * winner path's subtree.
+ * <p>
+ * Graph:
+ * <pre>
+ * root → A → shared (depth 2, same DependencyNode)
+ * root → shared (depth 1, same DependencyNode)
+ * shared → Z
+ * </pre>
+ * Expected result: shared and Z both reachable; shared nearest at depth 1 wins.
+ */
+ @ParameterizedTest
+ @MethodSource("conflictResolverSource")
+ void sharedNodeAtDifferentDepthsPreservesSubtree(ConflictResolver conflictResolver) throws RepositoryException {
+ DependencyNode root = makeDependencyNode("test", "root", "1.0");
+ DependencyNode a = makeDependencyNode("test", "a", "1.0");
+ DependencyNode shared = makeDependencyNode("test", "shared", "1.0");
+ DependencyNode z = makeDependencyNode("test", "z", "1.0");
+
+ // shared appears as root→A→shared (depth 2) AND root→shared (depth 1)
+ // Z is a child of shared — must survive in the resolved graph via the depth-1 path
+ shared.setChildren(mutableList(z));
+ a.setChildren(mutableList(shared)); // root → A → shared
+ root.setChildren(mutableList(a, shared)); // root → shared (depth 1, same instance)
+
+ DependencyNode result = transform(conflictResolver, root);
+
+ assertSame(root, result);
+ // root has 2 children: a and shared
+ assertEquals(2, result.getChildren().size());
+ assertSame(a, result.getChildren().get(0));
+ assertSame(shared, result.getChildren().get(1));
+ // shared at depth 1 wins; A's reference to shared is removed (loser)
+ assertEquals(0, a.getChildren().size(), "a's reference to shared (depth 2, loser) must be removed");
+ // shared's child Z must still be reachable — the loser removal must not corrupt winner's subtree
+ assertEquals(1, shared.getChildren().size(), "shared must retain its child Z");
+ assertSame(z, shared.getChildren().get(0));
+ }
+
+ /**
+ * Regression test: shared {@link DependencyNode} with children reachable via multiple parents at the same depth.
+ * With DFS, if the same node was reached via parent-B at depth 2 first (pushed before parent-A's child),
+ * and then via parent-A at depth 2, the guard would skip parent-A's expansion — but then a loser
+ * {@code push()} from parent-B's path would incorrectly remove the node's children from the shared
+ * {@link DependencyNode}, corrupting the resolved graph seen via parent-A.
+ * <p>
+ * Graph:
+ * <pre>
+ * root → A → shared (depth 2, same DependencyNode)
+ * root → B → shared (depth 2, same DependencyNode)
+ * shared → Z
+ * </pre>
+ * Expected: shared reachable via exactly one parent; Z still present as shared's child.
+ */
+ @ParameterizedTest
+ @MethodSource("conflictResolverSource")
+ void sharedNodeMultipleParentsSameDepthPreservesSubtree(ConflictResolver conflictResolver)
+ throws RepositoryException {
+ DependencyNode root = makeDependencyNode("test", "root", "1.0");
+ DependencyNode a = makeDependencyNode("test", "a", "1.0");
+ DependencyNode b = makeDependencyNode("test", "b", "1.0");
+ DependencyNode shared = makeDependencyNode("test", "shared", "1.0");
+ DependencyNode z = makeDependencyNode("test", "z", "1.0");
+
+ shared.setChildren(mutableList(z));
+ a.setChildren(mutableList(shared)); // root → A → shared (depth 2)
+ b.setChildren(mutableList(shared)); // root → B → shared (depth 2, same instance)
+ root.setChildren(mutableList(a, b));
+
+ DependencyNode result = transform(conflictResolver, root);
+
+ assertSame(root, result);
+ assertEquals(2, result.getChildren().size());
+
+ // shared wins on one path and is a loser on the other; check Z survives
+ AtomicInteger sharedCount = new AtomicInteger();
+ AtomicInteger zCount = new AtomicInteger();
+ result.accept(new TreeDependencyVisitor(new DependencyVisitor() {
+ @Override
+ public boolean visitEnter(DependencyNode node) {
+ if (node.getArtifact() != null) {
+ String id = node.getArtifact().getArtifactId();
+ if ("shared".equals(id)) {
+ sharedCount.incrementAndGet();
+ } else if ("z".equals(id)) {
+ zCount.incrementAndGet();
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public boolean visitLeave(DependencyNode node) {
+ return true;
+ }
+ }));
+ assertEquals(1, sharedCount.get(), "shared must appear exactly once in resolved graph");
+ assertEquals(1, zCount.get(), "z must appear exactly once as shared's child");
+ }
+
private static DependencyNode makeDependencyNode(String groupId, String artifactId, String version) {
return makeDependencyNode(groupId, artifactId, version, "compile");
}