View Javadoc
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 }