Uploaded image for project: 'Maven Resolver'
  1. Maven Resolver
  2. MRESOLVER-240

Using breadth-first approach to resolve Maven dependencies



    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • 1.7.3
    • 1.8.0
    • Resolver
    • None


      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



              michael-o Michael Osipov
              wecai wei cai
              0 Vote for this issue
              3 Start watching this issue