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