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