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