001package org.eclipse.aether.util.graph.transformer; 002 003/* 004 * Licensed to the Apache Software Foundation (ASF) under one 005 * or more contributor license agreements. See the NOTICE file 006 * distributed with this work for additional information 007 * regarding copyright ownership. The ASF licenses this file 008 * to you under the Apache License, Version 2.0 (the 009 * "License"); you may not use this file except in compliance 010 * with the License. You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, 015 * software distributed under the License is distributed on an 016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 017 * KIND, either express or implied. See the License for the 018 * specific language governing permissions and limitations 019 * under the License. 020 */ 021 022import java.util.ArrayList; 023import java.util.Arrays; 024import java.util.Collection; 025import java.util.Collections; 026import java.util.HashMap; 027import java.util.HashSet; 028import java.util.IdentityHashMap; 029import java.util.Iterator; 030import java.util.List; 031import java.util.ListIterator; 032import java.util.Map; 033import static java.util.Objects.requireNonNull; 034 035import org.eclipse.aether.RepositoryException; 036import org.eclipse.aether.artifact.Artifact; 037import org.eclipse.aether.collection.DependencyGraphTransformationContext; 038import org.eclipse.aether.collection.DependencyGraphTransformer; 039import org.eclipse.aether.graph.DefaultDependencyNode; 040import org.eclipse.aether.graph.Dependency; 041import org.eclipse.aether.graph.DependencyNode; 042import org.eclipse.aether.util.ConfigUtils; 043 044/** 045 * A dependency graph transformer that resolves version and scope conflicts among dependencies. For a given set of 046 * conflicting nodes, one node will be chosen as the winner and the other nodes are removed from the dependency graph. 047 * The exact rules by which a winning node and its effective scope are determined are controlled by user-supplied 048 * implementations of {@link VersionSelector}, {@link ScopeSelector}, {@link OptionalitySelector} and 049 * {@link ScopeDeriver}. 050 * <p> 051 * By default, this graph transformer will turn the dependency graph into a tree without duplicate artifacts. Using the 052 * configuration property {@link #CONFIG_PROP_VERBOSE}, a verbose mode can be enabled where the graph is still turned 053 * into a tree but all nodes participating in a conflict are retained. The nodes that were rejected during conflict 054 * resolution have no children and link back to the winner node via the {@link #NODE_DATA_WINNER} key in their custom 055 * data. Additionally, the keys {@link #NODE_DATA_ORIGINAL_SCOPE} and {@link #NODE_DATA_ORIGINAL_OPTIONALITY} are used 056 * to store the original scope and optionality of each node. Obviously, the resulting dependency tree is not suitable 057 * for artifact resolution unless a filter is employed to exclude the duplicate dependencies. 058 * <p> 059 * This transformer will query the keys {@link TransformationContextKeys#CONFLICT_IDS}, 060 * {@link TransformationContextKeys#SORTED_CONFLICT_IDS}, {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} for 061 * existing information about conflict ids. In absence of this information, it will automatically invoke the 062 * {@link ConflictIdSorter} to calculate it. 063 */ 064public final class ConflictResolver 065 implements DependencyGraphTransformer 066{ 067 068 /** 069 * The key in the repository session's {@link org.eclipse.aether.RepositorySystemSession#getConfigProperties() 070 * configuration properties} used to store a {@link Boolean} flag controlling the transformer's verbose mode. 071 */ 072 public static final String CONFIG_PROP_VERBOSE = "aether.conflictResolver.verbose"; 073 074 /** 075 * The key in the dependency node's {@link DependencyNode#getData() custom data} under which a reference to the 076 * {@link DependencyNode} which has won the conflict is stored. 077 */ 078 public static final String NODE_DATA_WINNER = "conflict.winner"; 079 080 /** 081 * The key in the dependency node's {@link DependencyNode#getData() custom data} under which the scope of the 082 * dependency before scope derivation and conflict resolution is stored. 083 */ 084 public static final String NODE_DATA_ORIGINAL_SCOPE = "conflict.originalScope"; 085 086 /** 087 * The key in the dependency node's {@link DependencyNode#getData() custom data} under which the optional flag of 088 * the dependency before derivation and conflict resolution is stored. 089 */ 090 public static final String NODE_DATA_ORIGINAL_OPTIONALITY = "conflict.originalOptionality"; 091 092 private final VersionSelector versionSelector; 093 094 private final ScopeSelector scopeSelector; 095 096 private final ScopeDeriver scopeDeriver; 097 098 private final OptionalitySelector optionalitySelector; 099 100 /** 101 * Creates a new conflict resolver instance with the specified hooks. 102 * 103 * @param versionSelector The version selector to use, must not be {@code null}. 104 * @param scopeSelector The scope selector to use, must not be {@code null}. 105 * @param optionalitySelector The optionality selector ot use, must not be {@code null}. 106 * @param scopeDeriver The scope deriver to use, must not be {@code null}. 107 */ 108 public ConflictResolver( VersionSelector versionSelector, ScopeSelector scopeSelector, 109 OptionalitySelector optionalitySelector, ScopeDeriver scopeDeriver ) 110 { 111 this.versionSelector = requireNonNull( versionSelector, "version selector cannot be null" ); 112 this.scopeSelector = requireNonNull( scopeSelector, "scope selector cannot be null" ); 113 this.optionalitySelector = requireNonNull( optionalitySelector, "optionality selector cannot be null" ); 114 this.scopeDeriver = requireNonNull( scopeDeriver, "scope deriver cannot be null" ); 115 } 116 117 public DependencyNode transformGraph( DependencyNode node, DependencyGraphTransformationContext context ) 118 throws RepositoryException 119 { 120 List<?> sortedConflictIds = (List<?>) context.get( TransformationContextKeys.SORTED_CONFLICT_IDS ); 121 if ( sortedConflictIds == null ) 122 { 123 ConflictIdSorter sorter = new ConflictIdSorter(); 124 sorter.transformGraph( node, context ); 125 126 sortedConflictIds = (List<?>) context.get( TransformationContextKeys.SORTED_CONFLICT_IDS ); 127 } 128 129 @SuppressWarnings( "unchecked" ) 130 Map<String, Object> stats = (Map<String, Object>) context.get( TransformationContextKeys.STATS ); 131 long time1 = System.nanoTime(); 132 133 @SuppressWarnings( "unchecked" ) 134 Collection<Collection<?>> conflictIdCycles = 135 (Collection<Collection<?>>) context.get( TransformationContextKeys.CYCLIC_CONFLICT_IDS ); 136 if ( conflictIdCycles == null ) 137 { 138 throw new RepositoryException( "conflict id cycles have not been identified" ); 139 } 140 141 Map<?, ?> conflictIds = (Map<?, ?>) context.get( TransformationContextKeys.CONFLICT_IDS ); 142 if ( conflictIds == null ) 143 { 144 throw new RepositoryException( "conflict groups have not been identified" ); 145 } 146 147 Map<Object, Collection<Object>> cyclicPredecessors = new HashMap<>(); 148 for ( Collection<?> cycle : conflictIdCycles ) 149 { 150 for ( Object conflictId : cycle ) 151 { 152 Collection<Object> predecessors = cyclicPredecessors.get( conflictId ); 153 if ( predecessors == null ) 154 { 155 predecessors = new HashSet<>(); 156 cyclicPredecessors.put( conflictId, predecessors ); 157 } 158 predecessors.addAll( cycle ); 159 } 160 } 161 162 State state = new State( node, conflictIds, sortedConflictIds.size(), context ); 163 for ( Iterator<?> it = sortedConflictIds.iterator(); it.hasNext(); ) 164 { 165 Object conflictId = it.next(); 166 167 // reset data structures for next graph walk 168 state.prepare( conflictId, cyclicPredecessors.get( conflictId ) ); 169 170 // find nodes with the current conflict id and while walking the graph (more deeply), nuke leftover losers 171 gatherConflictItems( node, state ); 172 173 // now that we know the min depth of the parents, update depth of conflict items 174 state.finish(); 175 176 // earlier runs might have nuked all parents of the current conflict id, so it might not exist anymore 177 if ( !state.items.isEmpty() ) 178 { 179 ConflictContext ctx = state.conflictCtx; 180 state.versionSelector.selectVersion( ctx ); 181 if ( ctx.winner == null ) 182 { 183 throw new RepositoryException( "conflict resolver did not select winner among " + state.items ); 184 } 185 DependencyNode winner = ctx.winner.node; 186 187 state.scopeSelector.selectScope( ctx ); 188 if ( state.verbose ) 189 { 190 winner.setData( NODE_DATA_ORIGINAL_SCOPE, winner.getDependency().getScope() ); 191 } 192 winner.setScope( ctx.scope ); 193 194 state.optionalitySelector.selectOptionality( ctx ); 195 if ( state.verbose ) 196 { 197 winner.setData( NODE_DATA_ORIGINAL_OPTIONALITY, winner.getDependency().isOptional() ); 198 } 199 winner.setOptional( ctx.optional ); 200 201 removeLosers( state ); 202 } 203 204 // record the winner so we can detect leftover losers during future graph walks 205 state.winner(); 206 207 // in case of cycles, trigger final graph walk to ensure all leftover losers are gone 208 if ( !it.hasNext() && !conflictIdCycles.isEmpty() && state.conflictCtx.winner != null ) 209 { 210 DependencyNode winner = state.conflictCtx.winner.node; 211 state.prepare( state, null ); 212 gatherConflictItems( winner, state ); 213 } 214 } 215 216 if ( stats != null ) 217 { 218 long time2 = System.nanoTime(); 219 stats.put( "ConflictResolver.totalTime", time2 - time1 ); 220 stats.put( "ConflictResolver.conflictItemCount", state.totalConflictItems ); 221 } 222 223 return node; 224 } 225 226 private boolean gatherConflictItems( DependencyNode node, State state ) 227 throws RepositoryException 228 { 229 Object conflictId = state.conflictIds.get( node ); 230 if ( state.currentId.equals( conflictId ) ) 231 { 232 // found it, add conflict item (if not already done earlier by another path) 233 state.add( node ); 234 // we don't recurse here so we might miss losers beneath us, those will be nuked during future walks below 235 } 236 else if ( state.loser( node, conflictId ) ) 237 { 238 // found a leftover loser (likely in a cycle) of an already processed conflict id, tell caller to nuke it 239 return false; 240 } 241 else if ( state.push( node, conflictId ) ) 242 { 243 // found potential parent, no cycle and not visisted before with the same derived scope, so recurse 244 for ( Iterator<DependencyNode> it = node.getChildren().iterator(); it.hasNext(); ) 245 { 246 DependencyNode child = it.next(); 247 if ( !gatherConflictItems( child, state ) ) 248 { 249 it.remove(); 250 } 251 } 252 state.pop(); 253 } 254 return true; 255 } 256 257 private void removeLosers( State state ) 258 { 259 ConflictItem winner = state.conflictCtx.winner; 260 List<DependencyNode> previousParent = null; 261 ListIterator<DependencyNode> childIt = null; 262 boolean conflictVisualized = false; 263 for ( ConflictItem item : state.items ) 264 { 265 if ( item == winner ) 266 { 267 continue; 268 } 269 if ( item.parent != previousParent ) 270 { 271 childIt = item.parent.listIterator(); 272 previousParent = item.parent; 273 conflictVisualized = false; 274 } 275 while ( childIt.hasNext() ) 276 { 277 DependencyNode child = childIt.next(); 278 if ( child == item.node ) 279 { 280 if ( state.verbose && !conflictVisualized && item.parent != winner.parent ) 281 { 282 conflictVisualized = true; 283 DependencyNode loser = new DefaultDependencyNode( child ); 284 loser.setData( NODE_DATA_WINNER, winner.node ); 285 loser.setData( NODE_DATA_ORIGINAL_SCOPE, loser.getDependency().getScope() ); 286 loser.setData( NODE_DATA_ORIGINAL_OPTIONALITY, loser.getDependency().isOptional() ); 287 loser.setScope( item.getScopes().iterator().next() ); 288 loser.setChildren( Collections.<DependencyNode>emptyList() ); 289 childIt.set( loser ); 290 } 291 else 292 { 293 childIt.remove(); 294 } 295 break; 296 } 297 } 298 } 299 // there might still be losers beneath the winner (e.g. in case of cycles) 300 // those will be nuked during future graph walks when we include the winner in the recursion 301 } 302 303 static final class NodeInfo 304 { 305 306 /** 307 * The smallest depth at which the node was seen, used for "the" depth of its conflict items. 308 */ 309 int minDepth; 310 311 /** 312 * The set of derived scopes the node was visited with, used to check whether an already seen node needs to be 313 * revisited again in context of another scope. To conserve memory, we start with {@code String} and update to 314 * {@code Set<String>} if needed. 315 */ 316 Object derivedScopes; 317 318 /** 319 * The set of derived optionalities the node was visited with, used to check whether an already seen node needs 320 * to be revisited again in context of another optionality. To conserve memory, encoded as bit field (bit 0 -> 321 * optional=false, bit 1 -> optional=true). 322 */ 323 int derivedOptionalities; 324 325 /** 326 * The conflict items which are immediate children of the node, used to easily update those conflict items after 327 * a new parent scope/optionality was encountered. 328 */ 329 List<ConflictItem> children; 330 331 static final int CHANGE_SCOPE = 0x01; 332 333 static final int CHANGE_OPTIONAL = 0x02; 334 335 private static final int OPT_FALSE = 0x01; 336 337 private static final int OPT_TRUE = 0x02; 338 339 NodeInfo( int depth, String derivedScope, boolean optional ) 340 { 341 minDepth = depth; 342 derivedScopes = derivedScope; 343 derivedOptionalities = optional ? OPT_TRUE : OPT_FALSE; 344 } 345 346 @SuppressWarnings( "unchecked" ) 347 int update( int depth, String derivedScope, boolean optional ) 348 { 349 if ( depth < minDepth ) 350 { 351 minDepth = depth; 352 } 353 int changes; 354 if ( derivedScopes.equals( derivedScope ) ) 355 { 356 changes = 0; 357 } 358 else if ( derivedScopes instanceof Collection ) 359 { 360 changes = ( (Collection<String>) derivedScopes ).add( derivedScope ) ? CHANGE_SCOPE : 0; 361 } 362 else 363 { 364 Collection<String> scopes = new HashSet<>(); 365 scopes.add( (String) derivedScopes ); 366 scopes.add( derivedScope ); 367 derivedScopes = scopes; 368 changes = CHANGE_SCOPE; 369 } 370 int bit = optional ? OPT_TRUE : OPT_FALSE; 371 if ( ( derivedOptionalities & bit ) == 0 ) 372 { 373 derivedOptionalities |= bit; 374 changes |= CHANGE_OPTIONAL; 375 } 376 return changes; 377 } 378 379 void add( ConflictItem item ) 380 { 381 if ( children == null ) 382 { 383 children = new ArrayList<>( 1 ); 384 } 385 children.add( item ); 386 } 387 388 } 389 390 final class State 391 { 392 393 /** 394 * The conflict id currently processed. 395 */ 396 Object currentId; 397 398 /** 399 * Stats counter. 400 */ 401 int totalConflictItems; 402 403 /** 404 * Flag whether we should keep losers in the graph to enable visualization/troubleshooting of conflicts. 405 */ 406 final boolean verbose; 407 408 /** 409 * A mapping from conflict id to winner node, helps to recognize nodes that have their effective 410 * scope&optionality set or are leftovers from previous removals. 411 */ 412 final Map<Object, DependencyNode> resolvedIds; 413 414 /** 415 * The set of conflict ids which could apply to ancestors of nodes with the current conflict id, used to avoid 416 * recursion early on. This is basically a superset of the key set of resolvedIds, the additional ids account 417 * for cyclic dependencies. 418 */ 419 final Collection<Object> potentialAncestorIds; 420 421 /** 422 * The output from the conflict marker 423 */ 424 final Map<?, ?> conflictIds; 425 426 /** 427 * The conflict items we have gathered so far for the current conflict id. 428 */ 429 final List<ConflictItem> items; 430 431 /** 432 * The (conceptual) mapping from nodes to extra infos, technically keyed by the node's child list which better 433 * captures the identity of a node since we're basically concerned with effects towards children. 434 */ 435 final Map<List<DependencyNode>, NodeInfo> infos; 436 437 /** 438 * The set of nodes on the DFS stack to detect cycles, technically keyed by the node's child list to match the 439 * dirty graph structure produced by the dependency collector for cycles. 440 */ 441 final Map<List<DependencyNode>, Object> stack; 442 443 /** 444 * The stack of parent nodes. 445 */ 446 final List<DependencyNode> parentNodes; 447 448 /** 449 * The stack of derived scopes for parent nodes. 450 */ 451 final List<String> parentScopes; 452 453 /** 454 * The stack of derived optional flags for parent nodes. 455 */ 456 final List<Boolean> parentOptionals; 457 458 /** 459 * The stack of node infos for parent nodes, may contain {@code null} which is used to disable creating new 460 * conflict items when visiting their parent again (conflict items are meant to be unique by parent-node combo). 461 */ 462 final List<NodeInfo> parentInfos; 463 464 /** 465 * The conflict context passed to the version/scope/optionality selectors, updated as we move along rather than 466 * recreated to avoid tmp objects. 467 */ 468 final ConflictContext conflictCtx; 469 470 /** 471 * The scope context passed to the scope deriver, updated as we move along rather than recreated to avoid tmp 472 * objects. 473 */ 474 final ScopeContext scopeCtx; 475 476 /** 477 * The effective version selector, i.e. after initialization. 478 */ 479 final VersionSelector versionSelector; 480 481 /** 482 * The effective scope selector, i.e. after initialization. 483 */ 484 final ScopeSelector scopeSelector; 485 486 /** 487 * The effective scope deriver, i.e. after initialization. 488 */ 489 final ScopeDeriver scopeDeriver; 490 491 /** 492 * The effective optionality selector, i.e. after initialization. 493 */ 494 final OptionalitySelector optionalitySelector; 495 496 State( DependencyNode root, Map<?, ?> conflictIds, int conflictIdCount, 497 DependencyGraphTransformationContext context ) 498 throws RepositoryException 499 { 500 this.conflictIds = conflictIds; 501 verbose = ConfigUtils.getBoolean( context.getSession(), false, CONFIG_PROP_VERBOSE ); 502 potentialAncestorIds = new HashSet<>( conflictIdCount * 2 ); 503 resolvedIds = new HashMap<>( conflictIdCount * 2 ); 504 items = new ArrayList<>( 256 ); 505 infos = new IdentityHashMap<>( 64 ); 506 stack = new IdentityHashMap<>( 64 ); 507 parentNodes = new ArrayList<>( 64 ); 508 parentScopes = new ArrayList<>( 64 ); 509 parentOptionals = new ArrayList<>( 64 ); 510 parentInfos = new ArrayList<>( 64 ); 511 conflictCtx = new ConflictContext( root, conflictIds, items ); 512 scopeCtx = new ScopeContext( null, null ); 513 versionSelector = ConflictResolver.this.versionSelector.getInstance( root, context ); 514 scopeSelector = ConflictResolver.this.scopeSelector.getInstance( root, context ); 515 scopeDeriver = ConflictResolver.this.scopeDeriver.getInstance( root, context ); 516 optionalitySelector = ConflictResolver.this.optionalitySelector.getInstance( root, context ); 517 } 518 519 void prepare( Object conflictId, Collection<Object> cyclicPredecessors ) 520 { 521 currentId = conflictId; 522 conflictCtx.conflictId = conflictId; 523 conflictCtx.winner = null; 524 conflictCtx.scope = null; 525 conflictCtx.optional = null; 526 items.clear(); 527 infos.clear(); 528 if ( cyclicPredecessors != null ) 529 { 530 potentialAncestorIds.addAll( cyclicPredecessors ); 531 } 532 } 533 534 void finish() 535 { 536 List<DependencyNode> previousParent = null; 537 int previousDepth = 0; 538 totalConflictItems += items.size(); 539 for ( ListIterator<ConflictItem> iterator = items.listIterator( items.size() ); iterator.hasPrevious(); ) 540 { 541 ConflictItem item = iterator.previous(); 542 if ( item.parent == previousParent ) 543 { 544 item.depth = previousDepth; 545 } 546 else if ( item.parent != null ) 547 { 548 previousParent = item.parent; 549 NodeInfo info = infos.get( previousParent ); 550 previousDepth = info.minDepth + 1; 551 item.depth = previousDepth; 552 } 553 } 554 potentialAncestorIds.add( currentId ); 555 } 556 557 void winner() 558 { 559 resolvedIds.put( currentId, ( conflictCtx.winner != null ) ? conflictCtx.winner.node : null ); 560 } 561 562 boolean loser( DependencyNode node, Object conflictId ) 563 { 564 DependencyNode winner = resolvedIds.get( conflictId ); 565 return winner != null && winner != node; 566 } 567 568 boolean push( DependencyNode node, Object conflictId ) 569 throws RepositoryException 570 { 571 if ( conflictId == null ) 572 { 573 if ( node.getDependency() != null ) 574 { 575 if ( node.getData().get( NODE_DATA_WINNER ) != null ) 576 { 577 return false; 578 } 579 throw new RepositoryException( "missing conflict id for node " + node ); 580 } 581 } 582 else if ( !potentialAncestorIds.contains( conflictId ) ) 583 { 584 return false; 585 } 586 587 List<DependencyNode> graphNode = node.getChildren(); 588 if ( stack.put( graphNode, Boolean.TRUE ) != null ) 589 { 590 return false; 591 } 592 593 int depth = depth(); 594 String scope = deriveScope( node, conflictId ); 595 boolean optional = deriveOptional( node, conflictId ); 596 NodeInfo info = infos.get( graphNode ); 597 if ( info == null ) 598 { 599 info = new NodeInfo( depth, scope, optional ); 600 infos.put( graphNode, info ); 601 parentInfos.add( info ); 602 parentNodes.add( node ); 603 parentScopes.add( scope ); 604 parentOptionals.add( optional ); 605 } 606 else 607 { 608 int changes = info.update( depth, scope, optional ); 609 if ( changes == 0 ) 610 { 611 stack.remove( graphNode ); 612 return false; 613 } 614 parentInfos.add( null ); // disable creating new conflict items, we update the existing ones below 615 parentNodes.add( node ); 616 parentScopes.add( scope ); 617 parentOptionals.add( optional ); 618 if ( info.children != null ) 619 { 620 if ( ( changes & NodeInfo.CHANGE_SCOPE ) != 0 ) 621 { 622 ListIterator<ConflictItem> itemIterator = info.children.listIterator( info.children.size() ); 623 while ( itemIterator.hasPrevious() ) 624 { 625 ConflictItem item = itemIterator.previous(); 626 String childScope = deriveScope( item.node, null ); 627 item.addScope( childScope ); 628 } 629 } 630 if ( ( changes & NodeInfo.CHANGE_OPTIONAL ) != 0 ) 631 { 632 ListIterator<ConflictItem> itemIterator = info.children.listIterator( info.children.size() ); 633 while ( itemIterator.hasPrevious() ) 634 { 635 ConflictItem item = itemIterator.previous(); 636 boolean childOptional = deriveOptional( item.node, null ); 637 item.addOptional( childOptional ); 638 } 639 } 640 } 641 } 642 643 return true; 644 } 645 646 void pop() 647 { 648 int last = parentInfos.size() - 1; 649 parentInfos.remove( last ); 650 parentScopes.remove( last ); 651 parentOptionals.remove( last ); 652 DependencyNode node = parentNodes.remove( last ); 653 stack.remove( node.getChildren() ); 654 } 655 656 void add( DependencyNode node ) 657 throws RepositoryException 658 { 659 DependencyNode parent = parent(); 660 if ( parent == null ) 661 { 662 ConflictItem item = newConflictItem( parent, node ); 663 items.add( item ); 664 } 665 else 666 { 667 NodeInfo info = parentInfos.get( parentInfos.size() - 1 ); 668 if ( info != null ) 669 { 670 ConflictItem item = newConflictItem( parent, node ); 671 info.add( item ); 672 items.add( item ); 673 } 674 } 675 } 676 677 private ConflictItem newConflictItem( DependencyNode parent, DependencyNode node ) 678 throws RepositoryException 679 { 680 return new ConflictItem( parent, node, deriveScope( node, null ), deriveOptional( node, null ) ); 681 } 682 683 private int depth() 684 { 685 return parentNodes.size(); 686 } 687 688 private DependencyNode parent() 689 { 690 int size = parentNodes.size(); 691 return ( size <= 0 ) ? null : parentNodes.get( size - 1 ); 692 } 693 694 private String deriveScope( DependencyNode node, Object conflictId ) 695 throws RepositoryException 696 { 697 if ( ( node.getManagedBits() & DependencyNode.MANAGED_SCOPE ) != 0 698 || ( conflictId != null && resolvedIds.containsKey( conflictId ) ) ) 699 { 700 return scope( node.getDependency() ); 701 } 702 703 int depth = parentNodes.size(); 704 scopes( depth, node.getDependency() ); 705 if ( depth > 0 ) 706 { 707 scopeDeriver.deriveScope( scopeCtx ); 708 } 709 return scopeCtx.derivedScope; 710 } 711 712 private void scopes( int parent, Dependency child ) 713 { 714 scopeCtx.parentScope = ( parent > 0 ) ? parentScopes.get( parent - 1 ) : null; 715 scopeCtx.derivedScope = scope( child ); 716 scopeCtx.childScope = scope( child ); 717 } 718 719 private String scope( Dependency dependency ) 720 { 721 return ( dependency != null ) ? dependency.getScope() : null; 722 } 723 724 private boolean deriveOptional( DependencyNode node, Object conflictId ) 725 { 726 Dependency dep = node.getDependency(); 727 boolean optional = ( dep != null ) && dep.isOptional(); 728 if ( optional || ( node.getManagedBits() & DependencyNode.MANAGED_OPTIONAL ) != 0 729 || ( conflictId != null && resolvedIds.containsKey( conflictId ) ) ) 730 { 731 return optional; 732 } 733 int depth = parentNodes.size(); 734 return ( depth > 0 ) ? parentOptionals.get( depth - 1 ) : false; 735 } 736 737 } 738 739 /** 740 * A context used to hold information that is relevant for deriving the scope of a child dependency. 741 * 742 * @see ScopeDeriver 743 * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may 744 * change without notice and only exists to enable unit testing. 745 */ 746 public static final class ScopeContext 747 { 748 749 String parentScope; 750 751 String childScope; 752 753 String derivedScope; 754 755 /** 756 * Creates a new scope context with the specified properties. 757 * 758 * @param parentScope The scope of the parent dependency, may be {@code null}. 759 * @param childScope The scope of the child dependency, may be {@code null}. 760 * @noreference This class is not intended to be instantiated by clients in production code, the constructor may 761 * change without notice and only exists to enable unit testing. 762 */ 763 public ScopeContext( String parentScope, String childScope ) 764 { 765 this.parentScope = ( parentScope != null ) ? parentScope : ""; 766 derivedScope = ( childScope != null ) ? childScope : ""; 767 this.childScope = ( childScope != null ) ? childScope : ""; 768 } 769 770 /** 771 * Gets the scope of the parent dependency. This is usually the scope that was derived by earlier invocations of 772 * the scope deriver. 773 * 774 * @return The scope of the parent dependency, never {@code null}. 775 */ 776 public String getParentScope() 777 { 778 return parentScope; 779 } 780 781 /** 782 * Gets the original scope of the child dependency. This is the scope that was declared in the artifact 783 * descriptor of the parent dependency. 784 * 785 * @return The original scope of the child dependency, never {@code null}. 786 */ 787 public String getChildScope() 788 { 789 return childScope; 790 } 791 792 /** 793 * Gets the derived scope of the child dependency. This is initially equal to {@link #getChildScope()} until the 794 * scope deriver makes changes. 795 * 796 * @return The derived scope of the child dependency, never {@code null}. 797 */ 798 public String getDerivedScope() 799 { 800 return derivedScope; 801 } 802 803 /** 804 * Sets the derived scope of the child dependency. 805 * 806 * @param derivedScope The derived scope of the dependency, may be {@code null}. 807 */ 808 public void setDerivedScope( String derivedScope ) 809 { 810 this.derivedScope = ( derivedScope != null ) ? derivedScope : ""; 811 } 812 813 } 814 815 /** 816 * A conflicting dependency. 817 * 818 * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may 819 * change without notice and only exists to enable unit testing. 820 */ 821 public static final class ConflictItem 822 { 823 824 // nodes can share child lists, we care about the unique owner of a child node which is the child list 825 final List<DependencyNode> parent; 826 827 // only for debugging/toString() to help identify the parent node(s) 828 final Artifact artifact; 829 830 final DependencyNode node; 831 832 int depth; 833 834 // we start with String and update to Set<String> if needed 835 Object scopes; 836 837 // bit field of OPTIONAL_FALSE and OPTIONAL_TRUE 838 int optionalities; 839 840 /** 841 * Bit flag indicating whether one or more paths consider the dependency non-optional. 842 */ 843 public static final int OPTIONAL_FALSE = 0x01; 844 845 /** 846 * Bit flag indicating whether one or more paths consider the dependency optional. 847 */ 848 public static final int OPTIONAL_TRUE = 0x02; 849 850 ConflictItem( DependencyNode parent, DependencyNode node, String scope, boolean optional ) 851 { 852 if ( parent != null ) 853 { 854 this.parent = parent.getChildren(); 855 this.artifact = parent.getArtifact(); 856 } 857 else 858 { 859 this.parent = null; 860 this.artifact = null; 861 } 862 this.node = node; 863 this.scopes = scope; 864 this.optionalities = optional ? OPTIONAL_TRUE : OPTIONAL_FALSE; 865 } 866 867 /** 868 * Creates a new conflict item with the specified properties. 869 * 870 * @param parent The parent node of the conflicting dependency, may be {@code null}. 871 * @param node The conflicting dependency, must not be {@code null}. 872 * @param depth The zero-based depth of the conflicting dependency. 873 * @param optionalities The optionalities the dependency was encountered with, encoded as a bit field consisting 874 * of {@link ConflictResolver.ConflictItem#OPTIONAL_TRUE} and 875 * {@link ConflictResolver.ConflictItem#OPTIONAL_FALSE}. 876 * @param scopes The derived scopes of the conflicting dependency, must not be {@code null}. 877 * @noreference This class is not intended to be instantiated by clients in production code, the constructor may 878 * change without notice and only exists to enable unit testing. 879 */ 880 public ConflictItem( DependencyNode parent, DependencyNode node, int depth, int optionalities, 881 String... scopes ) 882 { 883 this.parent = ( parent != null ) ? parent.getChildren() : null; 884 this.artifact = ( parent != null ) ? parent.getArtifact() : null; 885 this.node = node; 886 this.depth = depth; 887 this.optionalities = optionalities; 888 this.scopes = Arrays.asList( scopes ); 889 } 890 891 /** 892 * Determines whether the specified conflict item is a sibling of this item. 893 * 894 * @param item The other conflict item, must not be {@code null}. 895 * @return {@code true} if the given item has the same parent as this item, {@code false} otherwise. 896 */ 897 public boolean isSibling( ConflictItem item ) 898 { 899 return parent == item.parent; 900 } 901 902 /** 903 * Gets the dependency node involved in the conflict. 904 * 905 * @return The involved dependency node, never {@code null}. 906 */ 907 public DependencyNode getNode() 908 { 909 return node; 910 } 911 912 /** 913 * Gets the dependency involved in the conflict, short for {@code getNode.getDependency()}. 914 * 915 * @return The involved dependency, never {@code null}. 916 */ 917 public Dependency getDependency() 918 { 919 return node.getDependency(); 920 } 921 922 /** 923 * Gets the zero-based depth at which the conflicting node occurs in the graph. As such, the depth denotes the 924 * number of parent nodes. If actually multiple paths lead to the node, the return value denotes the smallest 925 * possible depth. 926 * 927 * @return The zero-based depth of the node in the graph. 928 */ 929 public int getDepth() 930 { 931 return depth; 932 } 933 934 /** 935 * Gets the derived scopes of the dependency. In general, the same dependency node could be reached via 936 * different paths and each path might result in a different derived scope. 937 * 938 * @see ScopeDeriver 939 * @return The (read-only) set of derived scopes of the dependency, never {@code null}. 940 */ 941 @SuppressWarnings( "unchecked" ) 942 public Collection<String> getScopes() 943 { 944 if ( scopes instanceof String ) 945 { 946 return Collections.singleton( (String) scopes ); 947 } 948 return (Collection<String>) scopes; 949 } 950 951 @SuppressWarnings( "unchecked" ) 952 void addScope( String scope ) 953 { 954 if ( scopes instanceof Collection ) 955 { 956 ( (Collection<String>) scopes ).add( scope ); 957 } 958 else if ( !scopes.equals( scope ) ) 959 { 960 Collection<Object> set = new HashSet<>(); 961 set.add( scopes ); 962 set.add( scope ); 963 scopes = set; 964 } 965 } 966 967 /** 968 * Gets the derived optionalities of the dependency. In general, the same dependency node could be reached via 969 * different paths and each path might result in a different derived optionality. 970 * 971 * @return A bit field consisting of {@link ConflictResolver.ConflictItem#OPTIONAL_FALSE} and/or 972 * {@link ConflictResolver.ConflictItem#OPTIONAL_TRUE} indicating the derived optionalities the 973 * dependency was encountered with. 974 */ 975 public int getOptionalities() 976 { 977 return optionalities; 978 } 979 980 void addOptional( boolean optional ) 981 { 982 optionalities |= optional ? OPTIONAL_TRUE : OPTIONAL_FALSE; 983 } 984 985 @Override 986 public String toString() 987 { 988 return node + " @ " + depth + " < " + artifact; 989 } 990 991 } 992 993 /** 994 * A context used to hold information that is relevant for resolving version and scope conflicts. 995 * 996 * @see VersionSelector 997 * @see ScopeSelector 998 * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may 999 * change without notice and only exists to enable unit testing. 1000 */ 1001 public static final class ConflictContext 1002 { 1003 1004 final DependencyNode root; 1005 1006 final Map<?, ?> conflictIds; 1007 1008 final Collection<ConflictItem> items; 1009 1010 Object conflictId; 1011 1012 ConflictItem winner; 1013 1014 String scope; 1015 1016 Boolean optional; 1017 1018 ConflictContext( DependencyNode root, Map<?, ?> conflictIds, Collection<ConflictItem> items ) 1019 { 1020 this.root = root; 1021 this.conflictIds = conflictIds; 1022 this.items = Collections.unmodifiableCollection( items ); 1023 } 1024 1025 /** 1026 * Creates a new conflict context. 1027 * 1028 * @param root The root node of the dependency graph, must not be {@code null}. 1029 * @param conflictId The conflict id for the set of conflicting dependencies in this context, must not be 1030 * {@code null}. 1031 * @param conflictIds The mapping from dependency node to conflict id, must not be {@code null}. 1032 * @param items The conflict items in this context, must not be {@code null}. 1033 * @noreference This class is not intended to be instantiated by clients in production code, the constructor may 1034 * change without notice and only exists to enable unit testing. 1035 */ 1036 public ConflictContext( DependencyNode root, Object conflictId, Map<DependencyNode, Object> conflictIds, 1037 Collection<ConflictItem> items ) 1038 { 1039 this( root, conflictIds, items ); 1040 this.conflictId = conflictId; 1041 } 1042 1043 /** 1044 * Gets the root node of the dependency graph being transformed. 1045 * 1046 * @return The root node of the dependeny graph, never {@code null}. 1047 */ 1048 public DependencyNode getRoot() 1049 { 1050 return root; 1051 } 1052 1053 /** 1054 * Determines whether the specified dependency node belongs to this conflict context. 1055 * 1056 * @param node The dependency node to check, must not be {@code null}. 1057 * @return {@code true} if the given node belongs to this conflict context, {@code false} otherwise. 1058 */ 1059 public boolean isIncluded( DependencyNode node ) 1060 { 1061 return conflictId.equals( conflictIds.get( node ) ); 1062 } 1063 1064 /** 1065 * Gets the collection of conflict items in this context. 1066 * 1067 * @return The (read-only) collection of conflict items in this context, never {@code null}. 1068 */ 1069 public Collection<ConflictItem> getItems() 1070 { 1071 return items; 1072 } 1073 1074 /** 1075 * Gets the conflict item which has been selected as the winner among the conflicting dependencies. 1076 * 1077 * @return The winning conflict item or {@code null} if not set yet. 1078 */ 1079 public ConflictItem getWinner() 1080 { 1081 return winner; 1082 } 1083 1084 /** 1085 * Sets the conflict item which has been selected as the winner among the conflicting dependencies. 1086 * 1087 * @param winner The winning conflict item, may be {@code null}. 1088 */ 1089 public void setWinner( ConflictItem winner ) 1090 { 1091 this.winner = winner; 1092 } 1093 1094 /** 1095 * Gets the effective scope of the winning dependency. 1096 * 1097 * @return The effective scope of the winning dependency or {@code null} if none. 1098 */ 1099 public String getScope() 1100 { 1101 return scope; 1102 } 1103 1104 /** 1105 * Sets the effective scope of the winning dependency. 1106 * 1107 * @param scope The effective scope, may be {@code null}. 1108 */ 1109 public void setScope( String scope ) 1110 { 1111 this.scope = scope; 1112 } 1113 1114 /** 1115 * Gets the effective optional flag of the winning dependency. 1116 * 1117 * @return The effective optional flag or {@code null} if none. 1118 */ 1119 public Boolean getOptional() 1120 { 1121 return optional; 1122 } 1123 1124 /** 1125 * Sets the effective optional flag of the winning dependency. 1126 * 1127 * @param optional The effective optional flag, may be {@code null}. 1128 */ 1129 public void setOptional( Boolean optional ) 1130 { 1131 this.optional = optional; 1132 } 1133 1134 @Override 1135 public String toString() 1136 { 1137 return winner + " @ " + scope + " < " + items; 1138 } 1139 1140 } 1141 1142 /** 1143 * An extension point of {@link ConflictResolver} that determines the winner among conflicting dependencies. The 1144 * winning node (and its children) will be retained in the dependency graph, the other nodes will get removed. The 1145 * version selector does not need to deal with potential scope conflicts, these will be addressed afterwards by the 1146 * {@link ScopeSelector}. 1147 * <p> 1148 * <strong>Note:</strong> Implementations must be stateless. 1149 */ 1150 public abstract static class VersionSelector 1151 { 1152 1153 /** 1154 * Retrieves the version selector for use during the specified graph transformation. The conflict resolver calls 1155 * this method once per 1156 * {@link ConflictResolver#transformGraph(DependencyNode, DependencyGraphTransformationContext)} invocation to 1157 * allow implementations to prepare any auxiliary data that is needed for their operation. Given that 1158 * implementations must be stateless, a new instance needs to be returned to hold such auxiliary data. The 1159 * default implementation simply returns the current instance which is appropriate for implementations which do 1160 * not require auxiliary data. 1161 * 1162 * @param root The root node of the (possibly cyclic!) graph to transform, must not be {@code null}. 1163 * @param context The graph transformation context, must not be {@code null}. 1164 * @return The scope deriver to use for the given graph transformation, never {@code null}. 1165 * @throws RepositoryException If the instance could not be retrieved. 1166 */ 1167 public VersionSelector getInstance( DependencyNode root, DependencyGraphTransformationContext context ) 1168 throws RepositoryException 1169 { 1170 return this; 1171 } 1172 1173 /** 1174 * Determines the winning node among conflicting dependencies. Implementations will usually iterate 1175 * {@link ConflictContext#getItems()}, inspect {@link ConflictItem#getNode()} and eventually call 1176 * {@link ConflictContext#setWinner(ConflictResolver.ConflictItem)} to deliver the winner. Failure to select a 1177 * winner will automatically fail the entire conflict resolution. 1178 * 1179 * @param context The conflict context, must not be {@code null}. 1180 * @throws RepositoryException If the version selection failed. 1181 */ 1182 public abstract void selectVersion( ConflictContext context ) 1183 throws RepositoryException; 1184 1185 } 1186 1187 /** 1188 * An extension point of {@link ConflictResolver} that determines the effective scope of a dependency from a 1189 * potentially conflicting set of {@link ScopeDeriver derived scopes}. The scope selector gets invoked after the 1190 * {@link VersionSelector} has picked the winning node. 1191 * <p> 1192 * <strong>Note:</strong> Implementations must be stateless. 1193 */ 1194 public abstract static class ScopeSelector 1195 { 1196 1197 /** 1198 * Retrieves the scope selector for use during the specified graph transformation. The conflict resolver calls 1199 * this method once per 1200 * {@link ConflictResolver#transformGraph(DependencyNode, DependencyGraphTransformationContext)} invocation to 1201 * allow implementations to prepare any auxiliary data that is needed for their operation. Given that 1202 * implementations must be stateless, a new instance needs to be returned to hold such auxiliary data. The 1203 * default implementation simply returns the current instance which is appropriate for implementations which do 1204 * not require auxiliary data. 1205 * 1206 * @param root The root node of the (possibly cyclic!) graph to transform, must not be {@code null}. 1207 * @param context The graph transformation context, must not be {@code null}. 1208 * @return The scope selector to use for the given graph transformation, never {@code null}. 1209 * @throws RepositoryException If the instance could not be retrieved. 1210 */ 1211 public ScopeSelector getInstance( DependencyNode root, DependencyGraphTransformationContext context ) 1212 throws RepositoryException 1213 { 1214 return this; 1215 } 1216 1217 /** 1218 * Determines the effective scope of the dependency given by {@link ConflictContext#getWinner()}. 1219 * Implementations will usually iterate {@link ConflictContext#getItems()}, inspect 1220 * {@link ConflictItem#getScopes()} and eventually call {@link ConflictContext#setScope(String)} to deliver the 1221 * effective scope. 1222 * 1223 * @param context The conflict context, must not be {@code null}. 1224 * @throws RepositoryException If the scope selection failed. 1225 */ 1226 public abstract void selectScope( ConflictContext context ) 1227 throws RepositoryException; 1228 1229 } 1230 1231 /** 1232 * An extension point of {@link ConflictResolver} that determines the scope of a dependency in relation to the scope 1233 * of its parent. 1234 * <p> 1235 * <strong>Note:</strong> Implementations must be stateless. 1236 */ 1237 public abstract static class ScopeDeriver 1238 { 1239 1240 /** 1241 * Retrieves the scope deriver for use during the specified graph transformation. The conflict resolver calls 1242 * this method once per 1243 * {@link ConflictResolver#transformGraph(DependencyNode, DependencyGraphTransformationContext)} invocation to 1244 * allow implementations to prepare any auxiliary data that is needed for their operation. Given that 1245 * implementations must be stateless, a new instance needs to be returned to hold such auxiliary data. The 1246 * default implementation simply returns the current instance which is appropriate for implementations which do 1247 * not require auxiliary data. 1248 * 1249 * @param root The root node of the (possibly cyclic!) graph to transform, must not be {@code null}. 1250 * @param context The graph transformation context, must not be {@code null}. 1251 * @return The scope deriver to use for the given graph transformation, never {@code null}. 1252 * @throws RepositoryException If the instance could not be retrieved. 1253 */ 1254 public ScopeDeriver getInstance( DependencyNode root, DependencyGraphTransformationContext context ) 1255 throws RepositoryException 1256 { 1257 return this; 1258 } 1259 1260 /** 1261 * Determines the scope of a dependency in relation to the scope of its parent. Implementors need to call 1262 * {@link ScopeContext#setDerivedScope(String)} to deliver the result of their calculation. If said method is 1263 * not invoked, the conflict resolver will assume the scope of the child dependency remains unchanged. 1264 * 1265 * @param context The scope context, must not be {@code null}. 1266 * @throws RepositoryException If the scope deriviation failed. 1267 */ 1268 public abstract void deriveScope( ScopeContext context ) 1269 throws RepositoryException; 1270 1271 } 1272 1273 /** 1274 * An extension point of {@link ConflictResolver} that determines the effective optional flag of a dependency from a 1275 * potentially conflicting set of derived optionalities. The optionality selector gets invoked after the 1276 * {@link VersionSelector} has picked the winning node. 1277 * <p> 1278 * <strong>Note:</strong> Implementations must be stateless. 1279 */ 1280 public abstract static class OptionalitySelector 1281 { 1282 1283 /** 1284 * Retrieves the optionality selector for use during the specified graph transformation. The conflict resolver 1285 * calls this method once per 1286 * {@link ConflictResolver#transformGraph(DependencyNode, DependencyGraphTransformationContext)} invocation to 1287 * allow implementations to prepare any auxiliary data that is needed for their operation. Given that 1288 * implementations must be stateless, a new instance needs to be returned to hold such auxiliary data. The 1289 * default implementation simply returns the current instance which is appropriate for implementations which do 1290 * not require auxiliary data. 1291 * 1292 * @param root The root node of the (possibly cyclic!) graph to transform, must not be {@code null}. 1293 * @param context The graph transformation context, must not be {@code null}. 1294 * @return The optionality selector to use for the given graph transformation, never {@code null}. 1295 * @throws RepositoryException If the instance could not be retrieved. 1296 */ 1297 public OptionalitySelector getInstance( DependencyNode root, DependencyGraphTransformationContext context ) 1298 throws RepositoryException 1299 { 1300 return this; 1301 } 1302 1303 /** 1304 * Determines the effective optional flag of the dependency given by {@link ConflictContext#getWinner()}. 1305 * Implementations will usually iterate {@link ConflictContext#getItems()}, inspect 1306 * {@link ConflictItem#getOptionalities()} and eventually call {@link ConflictContext#setOptional(Boolean)} to 1307 * deliver the effective optional flag. 1308 * 1309 * @param context The conflict context, must not be {@code null}. 1310 * @throws RepositoryException If the optionality selection failed. 1311 */ 1312 public abstract void selectOptionality( ConflictContext context ) 1313 throws RepositoryException; 1314 1315 } 1316 1317}