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