[
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.
[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.
* 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.
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)
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|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.
* 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 DependencyProcessingContext queue.
> 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
> Assignee: Michael Osipov
> Priority: Major
> Fix For: 1.8.0
>
>
> 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|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.
> * 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.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
