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