[PR] fix: PathConflictResolver uses BFS to guarantee correct depth ordering for shared DependencyNode instances [maven-resolver]

["gnodet (via GitHub)" <gi...@apache.org>]

gnodet opened a new pull request, #2175:
URL: https://github.com/apache/maven-resolver/pull/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 entries for its children at both D+1 and D'+1 depths. These extra loser paths produce spurious `push()` calls that execute `parent.dn.getChildren().remove(child.dn)` on shared `DependencyNode` objects, corrupting the resolved dependency graph.
   
   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.


-- 
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: issues-unsubscribe@maven.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] fix: PathConflictResolver uses BFS to guarantee correct depth ordering for shared DependencyNode instances [maven-resolver]

["gnodet (via GitHub)" <gi...@apache.org>]

gnodet commented on PR #2175:
URL: https://github.com/apache/maven-resolver/pull/2175#issuecomment-6061963193

   No, `PathConflictResolver` is independent of how the collector traverses the graph. The BFS here refers exclusively to the traversal order **inside** `gatherCRNodes` — the internal method that walks the already-collected dependency graph to build the set of conflict-resolution nodes.
   
   The issue was that `gatherCRNodes` used a LIFO stack (DFS), which does not guarantee that a shared `DependencyNode` instance is first encountered at its minimum reachable depth. When the resolver's `DataPool` reuses the same `DependencyNode` instance across multiple parent paths at different depths, DFS can process a deeper occurrence first — recording the wrong depth in the `expandedNodes` guard — which then causes duplicate partition entries and corrupts the resolved graph.
   
   Switching to a FIFO queue (BFS) inside `gatherCRNodes` guarantees that the first time any `DependencyNode` is dequeued it is at its minimum reachable depth, so the guard correctly suppresses all deeper/equal occurrences without re-enqueueing.
   
   The DependencyCollector (which assembles the graph in the first place) is a separate concern and its traversal strategy is unaffected.
   


-- 
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: issues-unsubscribe@maven.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] fix: PathConflictResolver uses BFS to guarantee correct depth ordering for shared DependencyNode instances [maven-resolver]

["cstamas (via GitHub)" <gi...@apache.org>]

cstamas commented on PR #2175:
URL: https://github.com/apache/maven-resolver/pull/2175#issuecomment-6059745525

   Does that means that Path CR is compatible only with BFS collector?


-- 
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: issues-unsubscribe@maven.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] fix: PathConflictResolver uses BFS to guarantee correct depth ordering for shared DependencyNode instances [maven-resolver]

["cstamas (via GitHub)" <gi...@apache.org>]

cstamas merged PR #2175:
URL: https://github.com/apache/maven-resolver/pull/2175


-- 
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: issues-unsubscribe@maven.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org