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