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.Collection;
23 import java.util.Collections;
24 import java.util.HashMap;
25 import java.util.List;
26 import java.util.Map;
27 import java.util.Objects;
28 import java.util.stream.Collectors;
29
30 import org.eclipse.aether.ConfigurationProperties;
31 import org.eclipse.aether.RepositoryException;
32 import org.eclipse.aether.RepositorySystemSession;
33 import org.eclipse.aether.artifact.Artifact;
34 import org.eclipse.aether.collection.DependencyGraphTransformationContext;
35 import org.eclipse.aether.graph.DefaultDependencyNode;
36 import org.eclipse.aether.graph.Dependency;
37 import org.eclipse.aether.graph.DependencyNode;
38 import org.eclipse.aether.util.ConfigUtils;
39 import org.eclipse.aether.util.artifact.ArtifactIdUtils;
40
41 import static java.util.Objects.requireNonNull;
42
43 /**
44 * A high-performance dependency graph transformer that resolves version and scope conflicts among dependencies.
45 * This is the recommended conflict resolver implementation that provides O(N) performance characteristics,
46 * significantly improving upon the O(N²) worst-case performance of {@link ClassicConflictResolver}.
47 * <p>
48 * For a given set of conflicting nodes, one node will be chosen as the winner. How losing nodes are handled
49 * depends on the configured verbosity level: they may be removed entirely, have their children removed, or
50 * be left in place with conflict information. The exact rules by which a winning node and its effective scope
51 * are determined are controlled by user-supplied implementations of {@link ConflictResolver.VersionSelector}, {@link ConflictResolver.ScopeSelector},
52 * {@link ConflictResolver.OptionalitySelector} and {@link ConflictResolver.ScopeDeriver}.
53 * <p>
54 * <strong>Performance Characteristics:</strong>
55 * <ul>
56 * <li><strong>Time Complexity:</strong> O(N) where N is the number of dependency nodes</li>
57 * <li><strong>Memory Usage:</strong> Creates a parallel tree structure for conflict-free processing</li>
58 * <li><strong>Scalability:</strong> Excellent performance on large multi-module projects</li>
59 * </ul>
60 * <p>
61 * <strong>Algorithm Overview:</strong>
62 * <ol>
63 * <li><strong>Path Tree Construction:</strong> Builds a cycle-free parallel tree structure from the input
64 * dependency graph, where each {@code Path} represents a unique route to a dependency node</li>
65 * <li><strong>Conflict Partitioning:</strong> Groups paths by conflict ID (based on groupId:artifactId:classifier:extension coordinates)</li>
66 * <li><strong>Topological Processing:</strong> Processes conflict groups in topologically sorted order</li>
67 * <li><strong>Winner Selection:</strong> Uses provided selectors to choose winners within each conflict group</li>
68 * <li><strong>Graph Transformation:</strong> Applies changes back to the original dependency graph</li>
69 * </ol>
70 * <p>
71 * <strong>Key Differences from {@link ClassicConflictResolver}:</strong>
72 * <ul>
73 * <li><strong>Performance:</strong> O(N) vs O(N²) time complexity</li>
74 * <li><strong>Memory Strategy:</strong> Uses parallel tree structure vs in-place graph modification</li>
75 * <li><strong>Cycle Handling:</strong> Explicitly breaks cycles during tree construction</li>
76 * <li><strong>Processing Order:</strong> Level-by-level from root vs depth-first traversal</li>
77 * </ul>
78 * <p>
79 * <strong>When to Use:</strong>
80 * <ul>
81 * <li>Default choice for all new projects and Maven 4+ installations</li>
82 * <li>Large multi-module projects with many dependencies</li>
83 * <li>Performance-critical build environments</li>
84 * <li>Any scenario where {@link ClassicConflictResolver} shows performance bottlenecks</li>
85 * </ul>
86 * <p>
87 * <strong>Implementation Note:</strong> This conflict resolver builds a cycle-free "parallel" structure based on the
88 * passed-in dependency graph, and applies operations level by level starting from the root. The parallel {@code Path}
89 * tree ensures that cycles in the original graph don't affect the conflict resolution algorithm's performance.
90 *
91 * @see ClassicConflictResolver
92 * @since 2.0.11
93 */
94 public final class PathConflictResolver extends ConflictResolver {
95 /**
96 * This implementation of conflict resolver is able to show more precise information regarding cycles in standard
97 * verbose mode. But, to make it really drop-in-replacement, we "tame down" this information. Still, users needing it
98 * may want to enable this for easier cycle detection, but in that case this conflict resolver will provide "extra nodes"
99 * not present on "standard verbosity level" with "classic" conflict resolver, that may lead to IT issues down the
100 * stream. Hence, the default is to provide as much information as much verbose "classic" does.
101 *
102 * @since 2.0.12
103 * @configurationSource {@link RepositorySystemSession#getConfigProperties()}
104 * @configurationType {@link java.lang.Boolean}
105 * @configurationDefaultValue {@link #DEFAULT_SHOW_CYCLES_IN_STANDARD_VERBOSITY}
106 */
107 public static final String CONFIG_PROP_SHOW_CYCLES_IN_STANDARD_VERBOSITY = ConfigurationProperties.PREFIX_AETHER
108 + "conflictResolver." + ConflictResolver.PATH_CONFLICT_RESOLVER + ".showCyclesInStandardVerbosity";
109
110 public static final boolean DEFAULT_SHOW_CYCLES_IN_STANDARD_VERBOSITY = false;
111
112 private final ConflictResolver.VersionSelector versionSelector;
113 private final ConflictResolver.ScopeSelector scopeSelector;
114 private final ConflictResolver.ScopeDeriver scopeDeriver;
115 private final ConflictResolver.OptionalitySelector optionalitySelector;
116
117 /**
118 * Creates a new conflict resolver instance with the specified hooks.
119 *
120 * @param versionSelector the version selector to use, must not be {@code null}
121 * @param scopeSelector the scope selector to use, must not be {@code null}
122 * @param optionalitySelector the optionality selector ot use, must not be {@code null}
123 * @param scopeDeriver the scope deriver to use, must not be {@code null}
124 */
125 public PathConflictResolver(
126 ConflictResolver.VersionSelector versionSelector,
127 ConflictResolver.ScopeSelector scopeSelector,
128 ConflictResolver.OptionalitySelector optionalitySelector,
129 ConflictResolver.ScopeDeriver scopeDeriver) {
130 this.versionSelector = requireNonNull(versionSelector, "version selector cannot be null");
131 this.scopeSelector = requireNonNull(scopeSelector, "scope selector cannot be null");
132 this.optionalitySelector = requireNonNull(optionalitySelector, "optionality selector cannot be null");
133 this.scopeDeriver = requireNonNull(scopeDeriver, "scope deriver cannot be null");
134 }
135
136 @SuppressWarnings("unchecked")
137 @Override
138 public DependencyNode transformGraph(DependencyNode node, DependencyGraphTransformationContext context)
139 throws RepositoryException {
140 requireNonNull(node, "node cannot be null");
141 requireNonNull(context, "context cannot be null");
142 List<String> sortedConflictIds = (List<String>) context.get(TransformationContextKeys.SORTED_CONFLICT_IDS);
143 if (sortedConflictIds == null) {
144 ConflictIdSorter sorter = new ConflictIdSorter();
145 sorter.transformGraph(node, context);
146
147 sortedConflictIds = (List<String>) context.get(TransformationContextKeys.SORTED_CONFLICT_IDS);
148 }
149
150 @SuppressWarnings("unchecked")
151 Map<String, Object> stats = (Map<String, Object>) context.get(TransformationContextKeys.STATS);
152 long time1 = System.nanoTime();
153
154 @SuppressWarnings("unchecked")
155 Collection<Collection<String>> conflictIdCycles =
156 (Collection<Collection<String>>) context.get(TransformationContextKeys.CYCLIC_CONFLICT_IDS);
157 if (conflictIdCycles == null) {
158 throw new RepositoryException("conflict id cycles have not been identified");
159 }
160
161 Map<DependencyNode, String> conflictIds =
162 (Map<DependencyNode, String>) context.get(TransformationContextKeys.CONFLICT_IDS);
163 if (conflictIds == null) {
164 throw new RepositoryException("conflict groups have not been identified");
165 }
166
167 State state = new State(
168 ConflictResolver.getVerbosity(context.getSession()),
169 ConfigUtils.getBoolean(
170 context.getSession(),
171 DEFAULT_SHOW_CYCLES_IN_STANDARD_VERBOSITY,
172 CONFIG_PROP_SHOW_CYCLES_IN_STANDARD_VERBOSITY),
173 versionSelector.getInstance(node, context),
174 scopeSelector.getInstance(node, context),
175 scopeDeriver.getInstance(node, context),
176 optionalitySelector.getInstance(node, context),
177 conflictIds);
178
179 state.build(node);
180
181 // loop over topographically sorted conflictIds
182 for (String conflictId : sortedConflictIds) {
183 // paths in given conflict group to consider
184 List<Path> paths = state.partitions.get(conflictId);
185 if (paths.isEmpty()) {
186 // this means that whole group "fall out of scope" (are all on loser branches); skip
187 continue;
188 }
189
190 // create conflict context for given conflictId
191 ConflictContext ctx = new ConflictContext(
192 node,
193 state.conflictIds,
194 paths.stream().map(ConflictItem::new).collect(Collectors.toList()),
195 conflictId);
196
197 // select winner (is done by VersionSelector)
198 state.versionSelector.selectVersion(ctx);
199 if (ctx.winner == null) {
200 throw new RepositoryException("conflict resolver did not select winner among " + ctx.items);
201 }
202 // select scope (no side effect between this and above operations)
203 state.scopeSelector.selectScope(ctx);
204 // select optionality (no side effect between this and above operations)
205 state.optionalitySelector.selectOptionality(ctx);
206
207 // we have a winner path
208 Path winnerPath = ctx.winner.path;
209
210 // mark conflictId as resolved with winner; sanity check
211 if (state.resolvedIds.containsKey(conflictId)) {
212 throw new RepositoryException("conflict resolver already have winner for conflictId=" + conflictId
213 + ": " + state.resolvedIds);
214 }
215 state.resolvedIds.put(conflictId, winnerPath);
216
217 // loop over considered paths and apply selection results; note: node may remove itself from iterated list
218 for (Path path : new ArrayList<>(paths)) {
219 // apply selected properties scope/optional to winner (winner carries version; others are losers)
220 if (path == winnerPath) {
221 path.scope = ctx.scope;
222 path.optional = ctx.optional;
223 }
224
225 // reset children as inheritance may be affected by this node scope/optionality change
226 path.children.forEach(c -> c.pull(0));
227 // derive with new values from this to children only; observe winner flag
228 path.derive(1, path == winnerPath);
229 // push this node full level changes to DN graph
230 path.push(0);
231 }
232 }
233
234 if (stats != null) {
235 long time2 = System.nanoTime();
236 stats.put("ConflictResolver.totalTime", time2 - time1);
237 stats.put(
238 "ConflictResolver.conflictItemCount",
239 state.partitions.values().stream().map(List::size).reduce(0, Integer::sum));
240 }
241
242 return node;
243 }
244
245 /**
246 * State of conflict resolution processing, to make this component (held in session) re-entrant by multiple threads.
247 */
248 private static class State {
249 /**
250 * Verbosity to be applied, see {@link ConflictResolver.Verbosity}.
251 */
252 private final ConflictResolver.Verbosity verbosity;
253
254 /**
255 * Whether to show nodes entering cycles, for easier identification. If this is enabled, this implementation
256 * of conflict resolver will show more data than classic.
257 */
258 private final boolean showCyclesInStandardVerbosity;
259
260 /**
261 * The {@link ConflictResolver.VersionSelector} to use.
262 */
263 private final ConflictResolver.VersionSelector versionSelector;
264
265 /**
266 * The {@link ConflictResolver.ScopeSelector} to use.
267 */
268 private final ConflictResolver.ScopeSelector scopeSelector;
269
270 /**
271 * The {@link ConflictResolver.ScopeDeriver} to use.
272 */
273 private final ConflictResolver.ScopeDeriver scopeDeriver;
274
275 /**
276 * The {@link ConflictResolver.OptionalitySelector} to use/
277 */
278 private final ConflictResolver.OptionalitySelector optionalitySelector;
279
280 /**
281 * The node to conflictId mapping from {@link ConflictMarker}.
282 */
283 private final Map<DependencyNode, String> conflictIds;
284
285 /**
286 * A mapping from conflictId to paths represented as {@link Path}s that exist for each conflictId. In other
287 * words all paths to each {@link DependencyNode} that are member of same conflictId group.
288 */
289 private final Map<String, List<Path>> partitions;
290
291 /**
292 * A mapping from conflictIds to winner {@link Path}, hence {@link DependencyNode} for given conflictId.
293 */
294 private final Map<String, Path> resolvedIds;
295
296 @SuppressWarnings("checkstyle:ParameterNumber")
297 private State(
298 ConflictResolver.Verbosity verbosity,
299 boolean showCyclesInStandardVerbosity,
300 ConflictResolver.VersionSelector versionSelector,
301 ConflictResolver.ScopeSelector scopeSelector,
302 ConflictResolver.ScopeDeriver scopeDeriver,
303 ConflictResolver.OptionalitySelector optionalitySelector,
304 Map<DependencyNode, String> conflictIds) {
305 this.verbosity = verbosity;
306 this.showCyclesInStandardVerbosity = showCyclesInStandardVerbosity;
307 this.versionSelector = versionSelector;
308 this.scopeSelector = scopeSelector;
309 this.scopeDeriver = scopeDeriver;
310 this.optionalitySelector = optionalitySelector;
311 this.conflictIds = conflictIds;
312 this.partitions = new HashMap<>();
313 this.resolvedIds = new HashMap<>();
314 }
315
316 /**
317 * Consumes the dirty graph and builds internal structures out of {@link Path} instances that is always a
318 * tree. As a side effect, {@link #partitions} are being filled up as well, that combined with topo
319 * sorted conflictIds can serve as a starting to point to walk the graph.
320 */
321 private void build(DependencyNode node) throws RepositoryException {
322 Path root = new Path(this, node, null, false);
323 gatherCRNodes(root);
324 }
325
326 /**
327 * Recursively builds {@link Path} graph by observing each node associated {@link DependencyNode}.
328 */
329 private void gatherCRNodes(Path node) throws RepositoryException {
330 List<DependencyNode> children = node.dn.getChildren();
331 if (!children.isEmpty()) {
332 // add children; we will get back those really added (not causing cycles)
333 List<Path> added = node.addChildren(children);
334 for (Path child : added) {
335 if (!child.cycle) {
336 gatherCRNodes(child);
337 }
338 }
339 }
340 }
341 }
342
343 /**
344 * Represents a unique path within the dependency graph from the root to a specific {@link DependencyNode}.
345 * This is the core data structure that enables the O(N) performance of {@link PathConflictResolver}.
346 * <p>
347 * <strong>Key Concepts:</strong>
348 * <ul>
349 * <li><strong>Path Uniqueness:</strong> Each {@code Path} instance represents a distinct route through
350 * the dependency graph, even if multiple paths lead to the same {@code DependencyNode}</li>
351 * <li><strong>Cycle-Free Structure:</strong> The {@code Path} tree is guaranteed to be acyclic, even
352 * when the original dependency graph contains cycles</li>
353 * <li><strong>Parallel Structure:</strong> This creates a "clean" tree alongside the original "dirty"
354 * graph for efficient processing</li>
355 * </ul>
356 * <p>
357 * <strong>Example:</strong> If dependency A appears in the graph via two different routes:
358 * <pre>
359 * Root → B → A (path 1)
360 * Root → C → A (path 2)
361 * </pre>
362 * Two separate {@code Path} instances will be created, both pointing to the same {@code DependencyNode} A,
363 * but representing different paths through the dependency tree.
364 * <p>
365 * <strong>Memory Optimization:</strong> While this creates additional objects, it enables the algorithm
366 * to process conflicts in O(N) time rather than O(N²), making it much more efficient for large graphs.
367 * <p>
368 * <strong>Conflict Resolution:</strong> Paths are grouped by conflict ID (based on groupId:artifactId:classifier:extension coordinates),
369 * and the conflict resolution algorithm can efficiently process each group independently.
370 */
371 private static class Path {
372 private final State state;
373 private DependencyNode dn;
374 private final String conflictId;
375 private final Path parent;
376 private final boolean cycle;
377 private final int depth;
378 private final List<Path> children;
379 private String scope;
380 private boolean optional;
381
382 private Path(State state, DependencyNode dn, Path parent, boolean cycle) {
383 this.state = state;
384 this.dn = dn;
385 this.conflictId = state.conflictIds.get(dn);
386 this.parent = parent;
387 this.cycle = cycle;
388 this.depth = parent != null ? parent.depth + 1 : 0;
389 this.children = new ArrayList<>();
390 pull(0);
391
392 this.state
393 .partitions
394 .computeIfAbsent(this.conflictId, k -> new ArrayList<>())
395 .add(this);
396 }
397
398 /**
399 * Pulls (possibly updated) scope and optional values from associated {@link DependencyNode} to this instance,
400 * going down toward children recursively the required count of levels.
401 */
402 private void pull(int levels) {
403 Dependency d = dn.getDependency();
404 if (d != null) {
405 this.scope = d.getScope();
406 this.optional = d.isOptional();
407 } else {
408 this.scope = "";
409 this.optional = false;
410 }
411 int newLevels = levels - 1;
412 if (newLevels >= 0) {
413 for (Path child : this.children) {
414 child.pull(newLevels);
415 }
416 }
417 }
418
419 /**
420 * Derives (from this to children direction) values that are "inherited" in tree: scope and optionality in the tree
421 * recursively going down required count of "levels".
422 */
423 private void derive(int levels, boolean winner) throws RepositoryException {
424 if (!winner) {
425 if (this.parent != null) {
426 if ((dn.getManagedBits() & DependencyNode.MANAGED_SCOPE) == 0) {
427 ScopeContext context = new ScopeContext(this.parent.scope, this.scope);
428 state.scopeDeriver.deriveScope(context);
429 this.scope = context.derivedScope;
430 }
431 if ((dn.getManagedBits() & DependencyNode.MANAGED_OPTIONAL) == 0) {
432 if (!this.optional && this.parent.optional) {
433 this.optional = true;
434 }
435 }
436 } else {
437 this.scope = "";
438 this.optional = false;
439 }
440 }
441 int newLevels = levels - 1;
442 if (newLevels >= 0) {
443 for (Path child : children) {
444 child.derive(newLevels, false);
445 }
446 }
447 }
448
449 /**
450 * Pushes (applies) the scope and optional and structural changes to associated {@link DependencyNode} modifying
451 * the graph of it. Verbosity is observed, and depending on it the conflicting/loser nodes are removed, or
452 * just their children is removed (with special care for version ranges, see {@link #relatedSiblingsCount(Artifact, Path)}
453 * or by just doing nothing with them only marking losers in full verbosity mode.
454 */
455 private void push(int levels) {
456 if (this.parent != null) {
457 Path winner = this.state.resolvedIds.get(this.conflictId);
458 if (winner == null) {
459 throw new IllegalStateException(
460 "Winner selection did not happen for conflictId=" + this.conflictId);
461 }
462 if (!Objects.equals(winner.conflictId, this.conflictId)) {
463 throw new IllegalStateException(
464 "ConflictId mix-up: this=" + this.conflictId + " winner=" + winner.conflictId);
465 }
466
467 if (winner == this) {
468 // copy onto dn; if applicable
469 if (this.dn.getDependency() != null) {
470 this.dn.setData(
471 ConflictResolver.NODE_DATA_ORIGINAL_SCOPE,
472 this.dn.getDependency().getScope());
473 this.dn.setData(
474 ConflictResolver.NODE_DATA_ORIGINAL_OPTIONALITY,
475 this.dn.getDependency().getOptional());
476 this.dn.setScope(this.scope);
477 this.dn.setOptional(this.optional);
478 }
479 } else {
480 // loser; move out of scope
481 moveOutOfScope();
482 boolean markLoser = false;
483 switch (state.verbosity) {
484 case NONE:
485 // remove loser dn
486 this.parent.children.remove(this);
487 this.parent.dn.setChildren(new ArrayList<>(this.parent.dn.getChildren()));
488 this.parent.dn.getChildren().remove(this.dn);
489 this.children.clear();
490 break;
491 case STANDARD:
492 String artifactId = ArtifactIdUtils.toId(this.dn.getArtifact());
493 String winnerArtifactId = ArtifactIdUtils.toId(winner.dn.getArtifact());
494 // is redundant if:
495 // - is not same as winner, and has related siblings (version range)
496 // - same instance of DN is direct dependency on path leading here
497 boolean isRedundant = (!Objects.equals(artifactId, winnerArtifactId)
498 && relatedSiblingsCount(this.dn.getArtifact(), this.parent) > 1);
499 if (!this.state.showCyclesInStandardVerbosity) {
500 isRedundant = isRedundant
501 || this.parent.isDirectDependencyOnPathToRoot(this.dn.getArtifact());
502 }
503 if (isRedundant) {
504 // is redundant dn; remove dn
505 this.parent.children.remove(this);
506 this.parent.dn.setChildren(new ArrayList<>(this.parent.dn.getChildren()));
507 this.parent.dn.getChildren().remove(this.dn);
508 this.children.clear();
509 } else {
510 // copy loser dn; without children
511 DependencyNode dnCopy = new DefaultDependencyNode(this.dn);
512 dnCopy.setChildren(Collections.emptyList());
513
514 // swap it out in DN graph; in case of cycles this may happen more than once
515 int idx = this.parent.dn.getChildren().indexOf(this.dn);
516 if (idx >= 0) {
517 this.parent.dn.getChildren().set(idx, dnCopy);
518 }
519 this.dn = dnCopy;
520
521 this.children.clear();
522 markLoser = true;
523 }
524 break;
525 case FULL:
526 // copy loser dn; with children
527 DependencyNode dnCopy = new DefaultDependencyNode(this.dn);
528 dnCopy.setChildren(new ArrayList<>(this.dn.getChildren()));
529
530 // swap it out in DN graph; in case of cycles this may happen more than once
531 int idx = this.parent.dn.getChildren().indexOf(this.dn);
532 if (idx >= 0) {
533 this.parent.dn.getChildren().set(idx, dnCopy);
534 }
535 this.dn = dnCopy;
536
537 markLoser = true;
538 break;
539 default:
540 throw new IllegalArgumentException("Unknown " + state.verbosity);
541 }
542 if (markLoser) {
543 this.dn.setData(ConflictResolver.NODE_DATA_WINNER, winner.dn);
544 this.dn.setData(
545 ConflictResolver.NODE_DATA_ORIGINAL_SCOPE,
546 this.dn.getDependency().getScope());
547 this.dn.setData(
548 ConflictResolver.NODE_DATA_ORIGINAL_OPTIONALITY,
549 this.dn.getDependency().getOptional());
550 this.dn.setScope(this.scope);
551 this.dn.setOptional(this.optional);
552 }
553 }
554 }
555
556 int newLevels = levels - 1;
557 if (newLevels >= 0 && !this.children.isEmpty()) {
558 // child may remove itself from iterated list
559 for (Path child : new ArrayList<>(children)) {
560 child.push(newLevels);
561 }
562 }
563 }
564
565 /**
566 * Returns {@code true} if given artifactId is direct dependency on the path leading from this toward root.
567 * For some reason "classic" conflict resolver removes these.
568 * <p>
569 * Note: this check and use of this method is ONLY present to make this conflict resolver produce SAME output
570 * as {@link ClassicConflictResolver} does, but IMHO this rule here is very arbitrary, moreover, in "standard"
571 * (where it is only used) verbosity it in facts HIDES the trace of possible cycles.
572 *
573 * @see #CONFIG_PROP_SHOW_CYCLES_IN_STANDARD_VERBOSITY
574 */
575 private boolean isDirectDependencyOnPathToRoot(Artifact artifact) {
576 if (this.depth == 1
577 && ArtifactIdUtils.toVersionlessId(this.dn.getArtifact())
578 .equals(ArtifactIdUtils.toVersionlessId(artifact))) {
579 return true;
580 } else if (this.parent != null) {
581 return parent.isDirectDependencyOnPathToRoot(artifact);
582 } else {
583 return false;
584 }
585 }
586
587 /**
588 * Counts "relatives" (GACE equal) artifacts under same parent; this is for cleaning up redundant nodes in
589 * case of version ranges, where same GACE is resolved into multiple GACEV as range is resolved. In {@link ConflictResolver.Verbosity#STANDARD}
590 * verbosity mode we remove "redundant" nodes (of a range) leaving only "winner equal" loser, that have same GACEV as winner.
591 */
592 private int relatedSiblingsCount(Artifact artifact, Path parent) {
593 String ga = artifact.getGroupId() + ":" + artifact.getArtifactId();
594 return Math.toIntExact(parent.children.stream()
595 .map(n -> n.dn.getArtifact())
596 .filter(a -> ga.equals(a.getGroupId() + ":" + a.getArtifactId()))
597 .count());
598 }
599
600 /**
601 * Removes this and all child {@link Path} nodes from winner selection scope; essentially marks whole subtree
602 * from "this and below" as loser, to not be considered in subsequent winner selections.
603 */
604 private void moveOutOfScope() {
605 this.state.partitions.get(this.conflictId).remove(this);
606 for (Path child : this.children) {
607 child.moveOutOfScope();
608 }
609 }
610
611 /**
612 * Adds node children: this method should be "batch" used, as all (potential) children should be added at once.
613 * Method will return really added ones, as this class avoids cycles.
614 */
615 private List<Path> addChildren(List<DependencyNode> children) throws RepositoryException {
616 ArrayList<Path> added = new ArrayList<>(children.size());
617 for (DependencyNode child : children) {
618 String childConflictId = this.state.conflictIds.get(child);
619 boolean cycle = this.state.partitions.getOrDefault(childConflictId, Collections.emptyList()).stream()
620 .anyMatch(p -> p.dn.equals(child));
621 Path c = new Path(this.state, child, this, cycle);
622 this.children.add(c);
623 c.derive(0, false);
624 added.add(c);
625 }
626 return added;
627 }
628
629 /**
630 * Dump for debug.
631 */
632 private void dump(String padding) {
633 System.out.println(padding + this.dn + ": " + this.scope + "/" + this.optional);
634 for (Path child : children) {
635 child.dump(padding + " ");
636 }
637 }
638
639 /**
640 * For easier debug.
641 */
642 @Override
643 public String toString() {
644 return this.dn.toString();
645 }
646 }
647
648 /**
649 * A context used to hold information that is relevant for deriving the scope of a child dependency.
650 *
651 * @see ConflictResolver.ScopeDeriver
652 * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may
653 * change without notice and only exists to enable unit testing
654 */
655 private static final class ScopeContext extends ConflictResolver.ScopeContext {
656 private final String parentScope;
657 private final String childScope;
658 private String derivedScope;
659
660 /**
661 * Creates a new scope context with the specified properties.
662 *
663 * @param parentScope the scope of the parent dependency, may be {@code null}
664 * @param childScope the scope of the child dependency, may be {@code null}
665 * @noreference This class is not intended to be instantiated by clients in production code, the constructor may
666 * change without notice and only exists to enable unit testing
667 */
668 private ScopeContext(String parentScope, String childScope) {
669 this.parentScope = (parentScope != null) ? parentScope : "";
670 this.derivedScope = (childScope != null) ? childScope : "";
671 this.childScope = (childScope != null) ? childScope : "";
672 }
673
674 /**
675 * Gets the scope of the parent dependency. This is usually the scope that was derived by earlier invocations of
676 * the scope deriver.
677 *
678 * @return the scope of the parent dependency, never {@code null}
679 */
680 public String getParentScope() {
681 return parentScope;
682 }
683
684 /**
685 * Gets the original scope of the child dependency. This is the scope that was declared in the artifact
686 * descriptor of the parent dependency.
687 *
688 * @return the original scope of the child dependency, never {@code null}
689 */
690 public String getChildScope() {
691 return childScope;
692 }
693
694 /**
695 * Gets the derived scope of the child dependency. This is initially equal to {@link #getChildScope()} until the
696 * scope deriver makes changes.
697 *
698 * @return the derived scope of the child dependency, never {@code null}
699 */
700 public String getDerivedScope() {
701 return derivedScope;
702 }
703
704 /**
705 * Sets the derived scope of the child dependency.
706 *
707 * @param derivedScope the derived scope of the dependency, may be {@code null}
708 */
709 public void setDerivedScope(String derivedScope) {
710 this.derivedScope = (derivedScope != null) ? derivedScope : "";
711 }
712 }
713
714 /**
715 * A conflicting dependency.
716 *
717 * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may
718 * change without notice and only exists to enable unit testing
719 */
720 private static final class ConflictItem extends ConflictResolver.ConflictItem {
721 private final Path path;
722 private final List<DependencyNode> parent;
723 private final Artifact artifact;
724 private final DependencyNode node;
725 private final int depth;
726 private final String scope;
727 private final int optionalities;
728
729 private ConflictItem(Path path) {
730 this.path = path;
731 if (path.parent != null) {
732 DependencyNode parent = path.parent.dn;
733 this.parent = parent.getChildren();
734 this.artifact = parent.getArtifact();
735 } else {
736 this.parent = null;
737 this.artifact = null;
738 }
739 this.node = path.dn;
740 this.depth = path.depth;
741 this.scope = path.scope;
742 this.optionalities = path.optional ? OPTIONAL_TRUE : OPTIONAL_FALSE;
743 }
744
745 /**
746 * Determines whether the specified conflict item is a sibling of this item.
747 *
748 * @param item the other conflict item, must not be {@code null}
749 * @return {@code true} if the given item has the same parent as this item, {@code false} otherwise
750 */
751 @Override
752 public boolean isSibling(ConflictResolver.ConflictItem item) {
753 return parent == ((ConflictItem) item).parent;
754 }
755
756 /**
757 * Gets the dependency node involved in the conflict.
758 *
759 * @return the involved dependency node, never {@code null}
760 */
761 @Override
762 public DependencyNode getNode() {
763 return node;
764 }
765
766 /**
767 * Gets the dependency involved in the conflict, short for {@code getNode.getDependency()}.
768 *
769 * @return the involved dependency, never {@code null}
770 */
771 @Override
772 public Dependency getDependency() {
773 return node.getDependency();
774 }
775
776 /**
777 * Gets the zero-based depth at which the conflicting node occurs in the graph. As such, the depth denotes the
778 * number of parent nodes. If actually multiple paths lead to the node, the return value denotes the smallest
779 * possible depth.
780 *
781 * @return the zero-based depth of the node in the graph
782 */
783 @Override
784 public int getDepth() {
785 return depth;
786 }
787
788 /**
789 * Gets the derived scopes of the dependency. In general, the same dependency node could be reached via
790 * different paths and each path might result in a different derived scope.
791 *
792 * @return the (read-only) set of derived scopes of the dependency, never {@code null}
793 * @see ConflictResolver.ScopeDeriver
794 */
795 @Override
796 public Collection<String> getScopes() {
797 return Collections.singleton(scope);
798 }
799
800 /**
801 * Gets the derived optionalities of the dependency. In general, the same dependency node could be reached via
802 * different paths and each path might result in a different derived optionality.
803 *
804 * @return a bit field consisting of {@link PathConflictResolver.ConflictItem#OPTIONAL_FALSE} and/or
805 * {@link PathConflictResolver.ConflictItem#OPTIONAL_TRUE} indicating the derived optionalities the
806 * dependency was encountered with
807 */
808 @Override
809 public int getOptionalities() {
810 return optionalities;
811 }
812
813 @Override
814 public String toString() {
815 return node + " @ " + depth + " < " + artifact;
816 }
817 }
818
819 /**
820 * A context used to hold information that is relevant for resolving version and scope conflicts.
821 *
822 * @see ConflictResolver.VersionSelector
823 * @see ConflictResolver.ScopeSelector
824 * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may
825 * change without notice and only exists to enable unit testing
826 */
827 private static final class ConflictContext extends ConflictResolver.ConflictContext {
828 private final DependencyNode root;
829 private final Map<DependencyNode, String> conflictIds;
830 private final Collection<ConflictResolver.ConflictItem> items;
831 private final String conflictId;
832
833 // elected properties
834 private ConflictItem winner;
835 private String scope;
836 private Boolean optional;
837
838 private ConflictContext(
839 DependencyNode root,
840 Map<DependencyNode, String> conflictIds,
841 Collection<ConflictItem> items,
842 String conflictId) {
843 this.root = root;
844 this.conflictIds = conflictIds;
845 this.items = Collections.unmodifiableCollection(items);
846 this.conflictId = conflictId;
847 }
848
849 /**
850 * Gets the root node of the dependency graph being transformed.
851 *
852 * @return the root node of the dependency graph, never {@code null}
853 */
854 @Override
855 public DependencyNode getRoot() {
856 return root;
857 }
858
859 /**
860 * Determines whether the specified dependency node belongs to this conflict context.
861 *
862 * @param node the dependency node to check, must not be {@code null}
863 * @return {@code true} if the given node belongs to this conflict context, {@code false} otherwise
864 */
865 @Override
866 public boolean isIncluded(DependencyNode node) {
867 return conflictId.equals(conflictIds.get(node));
868 }
869
870 /**
871 * Gets the collection of conflict items in this context.
872 *
873 * @return the (read-only) collection of conflict items in this context, never {@code null}
874 */
875 @Override
876 public Collection<ConflictResolver.ConflictItem> getItems() {
877 return items;
878 }
879
880 /**
881 * Gets the conflict item which has been selected as the winner among the conflicting dependencies.
882 *
883 * @return the winning conflict item or {@code null} if not set yet
884 */
885 @Override
886 public ConflictResolver.ConflictItem getWinner() {
887 return winner;
888 }
889
890 /**
891 * Sets the conflict item which has been selected as the winner among the conflicting dependencies.
892 *
893 * @param winner the winning conflict item, may be {@code null}
894 */
895 @Override
896 public void setWinner(ConflictResolver.ConflictItem winner) {
897 this.winner = (ConflictItem) winner;
898 }
899
900 /**
901 * Gets the effective scope of the winning dependency.
902 *
903 * @return the effective scope of the winning dependency or {@code null} if none
904 */
905 @Override
906 public String getScope() {
907 return scope;
908 }
909
910 /**
911 * Sets the effective scope of the winning dependency.
912 *
913 * @param scope the effective scope, may be {@code null}
914 */
915 @Override
916 public void setScope(String scope) {
917 this.scope = scope;
918 }
919
920 /**
921 * Gets the effective optional flag of the winning dependency.
922 *
923 * @return the effective optional flag or {@code null} if none
924 */
925 @Override
926 public Boolean getOptional() {
927 return optional;
928 }
929
930 /**
931 * Sets the effective optional flag of the winning dependency.
932 *
933 * @param optional the effective optional flag, may be {@code null}
934 */
935 @Override
936 public void setOptional(Boolean optional) {
937 this.optional = optional;
938 }
939
940 @Override
941 public String toString() {
942 return winner + " @ " + scope + " < " + items;
943 }
944 }
945 }