[MRESOLVER-240] Using breadth-first approach to resolve Maven dependencies

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.7.3
• Fix Version/s: 1.8.0
• Component/s: Resolver
• Assignee: Michael Osipov
• Reporter: wei cai
• Created: 21/Feb/22 08:37
• Updated: 16/Feb/23 10:26
• Resolved: 05/Mar/22 22:21

Description

There was discussions about the DFS or BFS algorithm for maven resolver in MRESOLVER-228, Changing to BFS would make MRESOLVER-228 & MRESOLVER-7 much easier to implement. Here is the plan for multiple changes requested recently:

• DFS > BFS - preparation for parallel download
• Skip & Reconcile - avoid unnecessary version resolution (MRESOLVER-228)
• Download descriptors in parallel (MRESOLVER-7)

This Jira would focus on DFS -> BFS.

Basically maven would:

• Go through all nodes and their dependencies starting from the root node to form a dependency graph.
• Resolve the version conflicts by a nearest first approach (close to BFS) based on above graph and determine the effective dependencies.

Changing DFS to BFS is just a sequence change (depth first -> width first), all nodes and their dependencies are still traversed to build the graph, thus it won't affect
the dependency resolve result.

 PR (co-authored by @ibabiankou) is fired. The basic idea of this PR is:

• Use queue instead of stack as required by BFS algorithm.
• When comes to a node, iterate its children, create DependencyProcessingContext for each child and put into the queue.
  The DependencyProcessingContext stores the objects such as current child node, DependencySelector, DependencyManager and so on.
  Here classes such as DependencySelector, DependencyManager is for exclusions and dependency management that inherited from parent nodes.
• Process the next node from queue.

Issue Links

• Blocked: MRESOLVER-247 Avoid unnecessary dependency resolution by a Skip solution based on BFS
• fixes: MRESOLVER-133 Improve resolver performance by using breadth-first search