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