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