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