You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@maven.apache.org by "wei cai (Jira)" <ji...@apache.org> on 2022/02/21 08:56:00 UTC
[jira] [Updated] (MRESOLVER-240) Using breadth-first approach to resolve maven dependencies
[ https://issues.apache.org/jira/browse/MRESOLVER-240?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
wei cai updated MRESOLVER-240:
------------------------------
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.
When changing to BFS, we cannot break below rules:
* Exclusions and dependency management can be inherited from parent nodes.
[PR|https://github.com/apache/maven-resolver/pull/144] (co-authored by @ibabiankou) is fired.
The basic idea of this PR is:
* Use queue instead of stack as required by BFS algorithm.
* Track the objects such as DependencySelector, DependencyManager in DependencyProcessingContext and put into the queue, this means inheritance of Exclusions and dependency management won't break.
was:
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) 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, thus it won't change the dependency resolve result.
When changing to BFS, we cannot break below rules:
* Exclusions and dependency management can be inherited from parent node.
[PR|https://github.com/apache/maven-resolver/pull/144] (co-authored by @ibabiankou) is fired. The basic idea of this PR is:
* Use queue instead of stack as required by BFS algorithm.
* Track the objects such as DependencySelector, DependencyManager in DependencyProcessingContext and put into the queue, so inheritance of Exclusions and dependency management won't break.
> Using breadth-first approach to resolve maven dependencies
> ----------------------------------------------------------
>
> Key: MRESOLVER-240
> URL: https://issues.apache.org/jira/browse/MRESOLVER-240
> Project: Maven Resolver
> Issue Type: Improvement
> Components: Resolver
> Affects Versions: 1.7.3
> Reporter: wei cai
> Priority: Major
>
> 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.
> When changing to BFS, we cannot break below rules:
> * Exclusions and dependency management can be inherited from parent nodes.
> [PR|https://github.com/apache/maven-resolver/pull/144] (co-authored by @ibabiankou) is fired.
> The basic idea of this PR is:
> * Use queue instead of stack as required by BFS algorithm.
> * Track the objects such as DependencySelector, DependencyManager in DependencyProcessingContext and put into the queue, this means inheritance of Exclusions and dependency management won't break.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)