caiwei-ebay edited a comment on pull request #136: URL: https://github.com/apache/maven-resolver/pull/136#issuecomment-998529747
@michael-o @cstamas Squashed the commits. Simplified the algorithm a lot. I have verified this approach by dry-run 2000+ apps in our company. Compared with previous approach: 1. Use a simpler approach to find out the nodes to reconcile. [Here](https://github.com/apache/maven-resolver/pull/136/files#diff-acdb4a279ff4d0407eaa7ee1767897eb62fbd0def455e06701f5ff81f8d3e938R281) The overall idea is: `Skip -> Reconcile (Transform rehearsal) -> Transform graph ` **Skip:** Skip resolving the node if a node with the same GAV and lower (or equal) depth has been calculated before. [Here](https://github.com/apache/maven-resolver/pull/136/files#diff-36be580aa73363c9aa07eb3954c331fb94da0906d7d0b4585bd18ab7c1305632R579) Sample: - A -> B -> C (C calculated and cached with depth==3) - A -> E -> F -> C (C will be skipped and children is not set, record this C has been skipped by above C node) - A -> C (C re-calculated and cached with depth==2) - A -> K -> C (C will be skipped, record this C has been skipped by the C node with path A -> C) With skip step only, the "mvn dependency:tree -Dverbose" is already guaranteed to be identical, however the "mvn dependency:tree" or "mvn dependency:list" result might be impacted as there would be dependency conflicts. At the very first, I just implemented the Skip strategy and tested with 500+ apps, 99%+ apps were having identical "mvn dependency:tree" or "mvn dependency:list" result, only 4 apps failed as there are dependency version conflicts. This is why we need the reconcile strategy as below. **Reconcile (Transform rehearsal):** `Clone the root node recursively -> Call transformer to transform the cloned root node -> Get the conflicts & the nodes to reconcile -> house sweeping for the NodesWithDepth cache -> reconcile the nodes` > 99%+ of apps don't need to a reconcile as the node needs to be reconcile is empty. Sample: - A -> B -> C 3.0 -> D -> Z (D of C 3.0 calculated and cached with depth==4) - A -> E -> F -> G -> D -> Z (D will be skipped and children is not set because depth 5 is deeper, record this D has been skipped by above D node) - A -> C 2.0 -> H (C 2.0 comes to resolve and maven will pick C 2.0 as depth is lower. The D of C3.0 in step 1 is no longer valid, need reconcile the skipped D node in step 2) Here is the flow: 1. Get the cloned root node A by deep cloning the original root node, the original root node has already been applied above skip strategy. [Here](https://github.com/apache/maven-resolver/pull/136/files#diff-acdb4a279ff4d0407eaa7ee1767897eb62fbd0def455e06701f5ff81f8d3e938R151) ``` A -> B -> C 3.0 -> D -> Z A -> E -> F -> G -> D (D has no children as skipped) A -> C 2.0 -> H ``` 2. Call Session's transformer to transform the cloned root node A with verbose mode, note transformer will set children as empty for conflict losers (ConflictResolver.removeLosers). [Here](https://github.com/apache/maven-resolver/pull/136/files#diff-acdb4a279ff4d0407eaa7ee1767897eb62fbd0def455e06701f5ff81f8d3e938R158) ``` A -> B -> C 3.0 (C 3.0 has no children as chopped by transformer, marked as conflict resolver) A -> E -> F -> G -> D (D has no children as skipped) A -> C 2.0 -> H ``` 3. Use ReconclingClonedGraphVisitor to iterate the transformed cloned root node. When visitor comes to a node without children, it can either a skipped node with no children set or chopped by transformer in step 2. [Here](https://github.com/apache/maven-resolver/pull/136/files#diff-acdb4a279ff4d0407eaa7ee1767897eb62fbd0def455e06701f5ff81f8d3e938R175) We just need to reconcile all skipped nodes (the node has no children and children of original node before transform is also empty). `D (parent path A -> E -> F -> G) needs to be reconciled` The visitor also record the dependency conflicts according to the ConflictResolver.NODE_DATA_WINNER property. `C 2.0 conflicts with C 3.0` 4. Remove cached items from nodesWithDepth if the parent paths of current node includes any above conflict loser: C 2.0. [Here](https://github.com/apache/maven-resolver/pull/136/files#diff-acdb4a279ff4d0407eaa7ee1767897eb62fbd0def455e06701f5ff81f8d3e938R201) ``` remove D (children Z， parent path A -> B -> C3.0) from nodesWithDepth remove Z (parent path A -> B -> C3.0 -> D) from nodesWithDepth ``` 5. Reconcile the nodes (recalculate their children) found in step 3. [Here](https://github.com/apache/maven-resolver/pull/136/files#diff-36be580aa73363c9aa07eb3954c331fb94da0906d7d0b4585bd18ab7c1305632R292) `recalculate D (parent path A -> E -> F -> G, skipped by A -> B -> C3.0 -> D)` -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
