gnodet-bot commented on code in PR #2153:
URL: https://github.com/apache/maven-resolver/pull/2153#discussion_r4071394904
##########
maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java:
##########
@@ -42,27 +41,24 @@
import static java.util.Objects.requireNonNull;
/**
- * A high-performance dependency graph transformer that resolves version and
scope conflicts among dependencies.
- * This is the recommended conflict resolver implementation that provides O(N)
performance characteristics,
- * significantly improving upon the O(N²) worst-case performance of {@link
ClassicConflictResolver}.
+ * A dependency graph transformer that resolves version and scope conflicts
among dependencies.
+ * This resolver builds a cycle-free parallel path tree from the dependency
graph, then processes
+ * conflict groups in topologically sorted order to select winners.
* <p>
* For a given set of conflicting nodes, one node will be chosen as the
winner. How losing nodes are handled
* depends on the configured verbosity level: they may be removed entirely,
have their children removed, or
* be left in place with conflict information. The exact rules by which a
winning node and its effective scope
* are determined are controlled by user-supplied implementations of {@link
ConflictResolver.VersionSelector}, {@link ConflictResolver.ScopeSelector},
* {@link ConflictResolver.OptionalitySelector} and {@link
ConflictResolver.ScopeDeriver}.
* <p>
- * <strong>Performance Characteristics:</strong>
- * <ul>
- * <li><strong>Time Complexity:</strong> O(N) where N is the number of
dependency nodes</li>
- * <li><strong>Memory Usage:</strong> Creates a parallel tree structure for
conflict-free processing</li>
- * <li><strong>Scalability:</strong> Excellent performance on large
multi-module projects</li>
- * </ul>
- * <p>
* <strong>Algorithm Overview:</strong>
* <ol>
* <li><strong>Path Tree Construction:</strong> Builds a cycle-free parallel
tree structure from the input
- * dependency graph, where each {@code Path} represents a unique route to
a dependency node</li>
+ * dependency graph, where each {@code Path} represents a unique route to
a dependency node.
+ * To avoid exponential memory use in highly connected graphs, each {@link
DependencyNode} instance
+ * is expanded (its children recursively visited) at most once: when the
same node is reached again
Review Comment:
⚠️ **Inaccurate Javadoc — 'at most once' is not guaranteed**
The claim is wrong for DFS order. With an iterative DFS, consider:
```
root → A → B → X (depth 3) [A is processed first]
root → C → X (depth 2) [C is processed later]
```
In DFS, `X@depth3` is pushed and fully expanded (its children go on the
stack) _before_ the DFS backtracks to process `C`. When `C → X@depth2` is
discovered, `child.depth (2) < prevDepth (3)` is true, so X is pushed again and
expanded a second time. Its subtree is traversed twice.
The algorithm guarantees that the total number of expansions is bounded
(proportional to graph edges, not exponential), but a single `DependencyNode`
instance **can** be expanded more than once when a shallower occurrence is
discovered after a deeper one. The same inaccuracy appears at line 359 (same
phrase in `gatherCRNodes` Javadoc) and in the `expandedNodes` field Javadoc.
Suggested fix: replace "at most once" with language that accurately
describes the bound:
```suggestion
* To avoid exponential memory use in highly connected graphs, subtree
expansion of each
* {@link DependencyNode} instance is bounded: when the same node is
reached again via a
* different parent path, a {@code Path} entry is still created for it
(so all occurrences
* appear in the conflict partition), but its subtree is only
re-traversed if reached at a
* strictly shallower depth than before.
```
##########
maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java:
##########
@@ -334,6 +335,7 @@ private State(
this.partitions = new HashMap<>(conflictIdCount * 4 / 3 + 1);
this.resolvedIds = new HashMap<>(conflictIdCount * 4 / 3 + 1);
this.scopeContext = new ScopeContext(null, null);
+ this.expandedNodes = new IdentityHashMap<>(conflictIdCount * 4 / 3
+ 1);
Review Comment:
⚠️ **Wrong initial capacity hint for `expandedNodes`**
`conflictIdCount` is the number of unique conflict IDs (unique
`groupId:artifactId:classifier:extension` tuples). `expandedNodes` stores one
entry per unique `DependencyNode` **instance**, which in a dense reactor (the
exact scenario this PR fixes) can be 5–50× larger than the number of distinct
artifacts. This causes repeated resizes of the `IdentityHashMap` precisely on
the large-graph inputs you're trying to optimize.
For `partitions` and `resolvedIds`, `conflictIdCount` is the right hint (one
entry per conflict ID). For `expandedNodes`, consider using the actual node
count or simply the default capacity — the resize cost is minor compared to the
OOM it prevents, but the comment on line 334 (`"conflictIdCount gives exact
number of partitions and resolved entries"`) makes the intent clear and
`expandedNodes` should not reuse it.
```suggestion
this.expandedNodes = new IdentityHashMap<>();
```
##########
maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java:
##########
@@ -353,6 +355,12 @@ private Path build(DependencyNode node) throws
RepositoryException {
* 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
* dependency graphs (reported in large multi-module projects with 13+
levels of recursion).
+ * <p>
+ * Each {@link DependencyNode} instance is expanded (its children
visited) at most once.
+ * 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 the subtree below it is not re-traversed. This prevents
exponential {@link Path} creation
+ * in highly connected graphs (e.g. a 813-module reactor where each
module depends on ~9 others).
Review Comment:
⚠️ **Missing regression test for the dense-graph OOM scenario**
The PR body describes a concrete reproducer (813-module reactor,
`OutOfMemoryError` with `-Xmx512m`) but no test is added. Without a test, this
can silently regress — the condition that triggered the OOM is a specific graph
topology that the existing 452 tests don't cover.
A parameterised JUnit test that constructs a dense diamond graph (e.g., N
hub nodes each reachable via M parent paths) and asserts both that it completes
without error and that it produces the same resolution result as
`ClassicConflictResolver` would lock in this fix.
--
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]
