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