1 package org.eclipse.aether.util.graph.transformer;
2
3 /*
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "License"); you may not use this file except in compliance
10 * with the License. You may obtain a copy of the License at
11 *
12 * http://www.apache.org/licenses/LICENSE-2.0
13 *
14 * Unless required by applicable law or agreed to in writing,
15 * software distributed under the License is distributed on an
16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 * KIND, either express or implied. See the License for the
18 * specific language governing permissions and limitations
19 * under the License.
20 */
21
22 import java.util.ArrayList;
23 import java.util.Arrays;
24 import java.util.Collection;
25 import java.util.Collections;
26 import java.util.HashMap;
27 import java.util.HashSet;
28 import java.util.IdentityHashMap;
29 import java.util.Iterator;
30 import java.util.List;
31 import java.util.ListIterator;
32 import java.util.Map;
33 import static java.util.Objects.requireNonNull;
34
35 import org.eclipse.aether.RepositoryException;
36 import org.eclipse.aether.RepositorySystemSession;
37 import org.eclipse.aether.artifact.Artifact;
38 import org.eclipse.aether.collection.DependencyGraphTransformationContext;
39 import org.eclipse.aether.collection.DependencyGraphTransformer;
40 import org.eclipse.aether.graph.DefaultDependencyNode;
41 import org.eclipse.aether.graph.Dependency;
42 import org.eclipse.aether.graph.DependencyNode;
43 import org.eclipse.aether.util.ConfigUtils;
44
45 /**
46 * A dependency graph transformer that resolves version and scope conflicts among dependencies. For a given set of
47 * conflicting nodes, one node will be chosen as the winner and the other nodes are removed from the dependency graph.
48 * The exact rules by which a winning node and its effective scope are determined are controlled by user-supplied
49 * implementations of {@link VersionSelector}, {@link ScopeSelector}, {@link OptionalitySelector} and
50 * {@link ScopeDeriver}.
51 * <p>
52 * By default, this graph transformer will turn the dependency graph into a tree without duplicate artifacts. Using the
53 * configuration property {@link #CONFIG_PROP_VERBOSE}, a verbose mode can be enabled where the graph is still turned
54 * into a tree but all nodes participating in a conflict are retained. The nodes that were rejected during conflict
55 * resolution have no children and link back to the winner node via the {@link #NODE_DATA_WINNER} key in their custom
56 * data. Additionally, the keys {@link #NODE_DATA_ORIGINAL_SCOPE} and {@link #NODE_DATA_ORIGINAL_OPTIONALITY} are used
57 * to store the original scope and optionality of each node. Obviously, the resulting dependency tree is not suitable
58 * for artifact resolution unless a filter is employed to exclude the duplicate dependencies.
59 * <p>
60 * This transformer will query the keys {@link TransformationContextKeys#CONFLICT_IDS},
61 * {@link TransformationContextKeys#SORTED_CONFLICT_IDS}, {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} for
62 * existing information about conflict ids. In absence of this information, it will automatically invoke the
63 * {@link ConflictIdSorter} to calculate it.
64 */
65 public final class ConflictResolver
66 implements DependencyGraphTransformer
67 {
68
69 /**
70 * The key in the repository session's {@link RepositorySystemSession#getConfigProperties() configuration
71 * properties} used to store a {@link Boolean} flag controlling the transformer's verbose mode.
72 */
73 public static final String CONFIG_PROP_VERBOSE = "aether.conflictResolver.verbose";
74
75 /**
76 * The key in the dependency node's {@link DependencyNode#getData() custom data} under which a reference to the
77 * {@link DependencyNode} which has won the conflict is stored.
78 */
79 public static final String NODE_DATA_WINNER = "conflict.winner";
80
81 /**
82 * The key in the dependency node's {@link DependencyNode#getData() custom data} under which the scope of the
83 * dependency before scope derivation and conflict resolution is stored.
84 */
85 public static final String NODE_DATA_ORIGINAL_SCOPE = "conflict.originalScope";
86
87 /**
88 * The key in the dependency node's {@link DependencyNode#getData() custom data} under which the optional flag of
89 * the dependency before derivation and conflict resolution is stored.
90 */
91 public static final String NODE_DATA_ORIGINAL_OPTIONALITY = "conflict.originalOptionality";
92
93 private final VersionSelector versionSelector;
94
95 private final ScopeSelector scopeSelector;
96
97 private final ScopeDeriver scopeDeriver;
98
99 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 }