/*
    * Licensed to the Apache Software Foundation (ASF) under one
    * or more contributor license agreements.  See the NOTICE file
    * distributed with this work for additional information
    * regarding copyright ownership.  The ASF licenses this file
    * to you under the Apache License, Version 2.0 (the
    * "License"); you may not use this file except in compliance
    * with the License.  You may obtain a copy of the License at
    *
   *   http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing,
   * software distributed under the License is distributed on an
   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   * KIND, either express or implied.  See the License for the
   * specific language governing permissions and limitations
   * under the License.
   */
  package org.eclipse.aether.util.graph.transformer;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  import java.util.Objects;
  
  import org.eclipse.aether.ConfigurationProperties;
  import org.eclipse.aether.RepositoryException;
  import org.eclipse.aether.RepositorySystemSession;
  import org.eclipse.aether.artifact.Artifact;
  import org.eclipse.aether.collection.DependencyGraphTransformationContext;
  import org.eclipse.aether.graph.DefaultDependencyNode;
  import org.eclipse.aether.graph.Dependency;
  import org.eclipse.aether.graph.DependencyNode;
  import org.eclipse.aether.util.ConfigUtils;
  import org.eclipse.aether.util.artifact.ArtifactIdUtils;
  
  import static java.util.Objects.requireNonNull;
  
  /**
   * A high-performance dependency graph transformer that resolves version and scope conflicts among dependencies.
   * This is the recommended conflict resolver implementation that provides O(N) performance characteristics,
   * significantly improving upon the O(N²) worst-case performance of {@link ClassicConflictResolver}.
   * <p>
   * For a given set of conflicting nodes, one node will be chosen as the winner. How losing nodes are handled
   * depends on the configured verbosity level: they may be removed entirely, have their children removed, or
   * be left in place with conflict information. The exact rules by which a winning node and its effective scope
   * are determined are controlled by user-supplied implementations of {@link ConflictResolver.VersionSelector}, {@link ConflictResolver.ScopeSelector},
   * {@link ConflictResolver.OptionalitySelector} and {@link ConflictResolver.ScopeDeriver}.
   * <p>
   * <strong>Performance Characteristics:</strong>
   * <ul>
   * <li><strong>Time Complexity:</strong> O(N) where N is the number of dependency nodes</li>
   * <li><strong>Memory Usage:</strong> Creates a parallel tree structure for conflict-free processing</li>
   * <li><strong>Scalability:</strong> Excellent performance on large multi-module projects</li>
   * </ul>
   * <p>
   * <strong>Algorithm Overview:</strong>
   * <ol>
   * <li><strong>Path Tree Construction:</strong> Builds a cycle-free parallel tree structure from the input
   *     dependency graph, where each {@code Path} represents a unique route to a dependency node</li>
   * <li><strong>Conflict Partitioning:</strong> Groups paths by conflict ID (based on groupId:artifactId:classifier:extension coordinates)</li>
   * <li><strong>Topological Processing:</strong> Processes conflict groups in topologically sorted order</li>
   * <li><strong>Winner Selection:</strong> Uses provided selectors to choose winners within each conflict group</li>
   * <li><strong>Graph Transformation:</strong> Applies changes back to the original dependency graph</li>
   * </ol>
   * <p>
   * <strong>Key Differences from {@link ClassicConflictResolver}:</strong>
   * <ul>
   * <li><strong>Performance:</strong> O(N) vs O(N²) time complexity</li>
   * <li><strong>Memory Strategy:</strong> Uses parallel tree structure vs in-place graph modification</li>
   * <li><strong>Cycle Handling:</strong> Explicitly breaks cycles during tree construction</li>
   * <li><strong>Processing Order:</strong> Level-by-level from root vs depth-first traversal</li>
   * </ul>
   * <p>
   * <strong>When to Use:</strong>
   * <ul>
   * <li>Default choice for all new projects and Maven 4+ installations</li>
   * <li>Large multi-module projects with many dependencies</li>
   * <li>Performance-critical build environments</li>
   * <li>Any scenario where {@link ClassicConflictResolver} shows performance bottlenecks</li>
   * </ul>
   * <p>
   * <strong>Implementation Note:</strong> This conflict resolver builds a cycle-free "parallel" structure based on the
   * passed-in dependency graph, and applies operations level by level starting from the root. The parallel {@code Path}
   * tree ensures that cycles in the original graph don't affect the conflict resolution algorithm's performance.
   *
   * @see ClassicConflictResolver
   * @since 2.0.11
   */
  public final class PathConflictResolver extends ConflictResolver {
      /**
       * This implementation of conflict resolver is able to show more precise information regarding cycles in standard
       * verbose mode. But, to make it really drop-in-replacement, we "tame down" this information. Still, users needing it
       * may want to enable this for easier cycle detection, but in that case this conflict resolver will provide "extra nodes"
       * not present on "standard verbosity level" with "classic" conflict resolver, that may lead to IT issues down the
       * stream. Hence, the default is to provide as much information as much verbose "classic" does.
      *
      * @since 2.0.12
      * @configurationSource {@link RepositorySystemSession#getConfigProperties()}
      * @configurationType {@link java.lang.Boolean}
      * @configurationDefaultValue {@link #DEFAULT_SHOW_CYCLES_IN_STANDARD_VERBOSITY}
      */
     public static final String CONFIG_PROP_SHOW_CYCLES_IN_STANDARD_VERBOSITY = ConfigurationProperties.PREFIX_AETHER
             + "conflictResolver." + ConflictResolver.PATH_CONFLICT_RESOLVER + ".showCyclesInStandardVerbosity";
 
     public static final boolean DEFAULT_SHOW_CYCLES_IN_STANDARD_VERBOSITY = false;
 
     private final ConflictResolver.VersionSelector versionSelector;
     private final ConflictResolver.ScopeSelector scopeSelector;
     private final ConflictResolver.ScopeDeriver scopeDeriver;
     private final ConflictResolver.OptionalitySelector optionalitySelector;
 
     /**
      * Creates a new conflict resolver instance with the specified hooks.
      *
      * @param versionSelector the version selector to use, must not be {@code null}
      * @param scopeSelector the scope selector to use, must not be {@code null}
      * @param optionalitySelector the optionality selector ot use, must not be {@code null}
      * @param scopeDeriver the scope deriver to use, must not be {@code null}
      */
     public PathConflictResolver(
             ConflictResolver.VersionSelector versionSelector,
             ConflictResolver.ScopeSelector scopeSelector,
             ConflictResolver.OptionalitySelector optionalitySelector,
             ConflictResolver.ScopeDeriver scopeDeriver) {
         this.versionSelector = requireNonNull(versionSelector, "version selector cannot be null");
         this.scopeSelector = requireNonNull(scopeSelector, "scope selector cannot be null");
         this.optionalitySelector = requireNonNull(optionalitySelector, "optionality selector cannot be null");
         this.scopeDeriver = requireNonNull(scopeDeriver, "scope deriver cannot be null");
     }
 
     @SuppressWarnings("unchecked")
     @Override
     public DependencyNode transformGraph(DependencyNode node, DependencyGraphTransformationContext context)
             throws RepositoryException {
         requireNonNull(node, "node cannot be null");
         requireNonNull(context, "context cannot be null");
         List<String> sortedConflictIds = (List<String>) context.get(TransformationContextKeys.SORTED_CONFLICT_IDS);
         if (sortedConflictIds == null) {
             ConflictIdSorter sorter = new ConflictIdSorter();
             sorter.transformGraph(node, context);
 
             sortedConflictIds = (List<String>) context.get(TransformationContextKeys.SORTED_CONFLICT_IDS);
         }
 
         @SuppressWarnings("unchecked")
         Map<String, Object> stats = (Map<String, Object>) context.get(TransformationContextKeys.STATS);
         long time1 = System.nanoTime();
 
         Map<DependencyNode, String> conflictIds =
                 (Map<DependencyNode, String>) context.get(TransformationContextKeys.CONFLICT_IDS);
         if (conflictIds == null) {
             throw new RepositoryException("conflict groups have not been identified");
         }
 
         State state = new State(
                 ConflictResolver.getVerbosity(context.getSession()),
                 ConfigUtils.getBoolean(
                         context.getSession(),
                         DEFAULT_SHOW_CYCLES_IN_STANDARD_VERBOSITY,
                         CONFIG_PROP_SHOW_CYCLES_IN_STANDARD_VERBOSITY),
                 versionSelector.getInstance(node, context),
                 scopeSelector.getInstance(node, context),
                 scopeDeriver.getInstance(node, context),
                 optionalitySelector.getInstance(node, context),
                 conflictIds,
                 sortedConflictIds.size(),
                 node);
 
         // loop over topographically sorted conflictIds
         int conflictItemCount = 0;
         for (String conflictId : sortedConflictIds) {
             // paths in given conflict group to consider; filter out those moved out of scope
             List<Path> allPaths = state.partitions.get(conflictId);
             List<Path> activePaths = new ArrayList<>(allPaths.size());
             List<ConflictItem> items = new ArrayList<>(allPaths.size());
             for (Path p : allPaths) {
                 if (!p.outOfScope) {
                     activePaths.add(p);
                     items.add(new ConflictItem(p));
                 }
             }
             // Replace partition entry with filtered list to release references to out-of-scope
             // paths (and their detached subtrees), allowing GC during resolution
             state.partitions.put(conflictId, activePaths);
             if (activePaths.isEmpty()) {
                 // this means that whole group "fall out of scope" (are all on loser branches); skip
                 continue;
             }
             conflictItemCount += activePaths.size();
 
             // create conflict context for given conflictId
             ConflictContext ctx = new ConflictContext(node, state.conflictIds, items, conflictId);
 
             // select winner (is done by VersionSelector)
             state.versionSelector.selectVersion(ctx);
             if (ctx.winner == null) {
                 throw new RepositoryException("conflict resolver did not select winner among " + items);
             }
             // select scope (no side effect between this and above operations)
             state.scopeSelector.selectScope(ctx);
             // select optionality (no side effect between this and above operations)
             state.optionalitySelector.selectOptionality(ctx);
 
             // we have a winner path
             Path winnerPath = ctx.winner.path;
 
             // mark conflictId as resolved with winner; sanity check
             if (state.resolvedIds.containsKey(conflictId)) {
                 throw new RepositoryException("conflict resolver already have winner for conflictId=" + conflictId
                         + ": " + state.resolvedIds);
             }
             state.resolvedIds.put(conflictId, winnerPath);
 
             // loop over considered paths and apply selection results
             for (Path path : activePaths) {
                 // apply selected properties scope/optional to winner (winner carries version; others are losers)
                 if (path == winnerPath) {
                     path.scope = ctx.scope;
                     path.optional = ctx.optional;
                 }
 
                 // reset children as inheritance may be affected by this node scope/optionality change
                 if (path.children != null) {
                     for (Path c : path.children) {
                         c.pull(0);
                     }
                 }
                 // derive with new values from this to children only; observe winner flag
                 path.derive(1, path == winnerPath);
                 // push this node full level changes to DN graph
                 path.push(0);
             }
         }
 
         if (stats != null) {
             long time2 = System.nanoTime();
             stats.put("ConflictResolver.totalTime", time2 - time1);
             stats.put("ConflictResolver.conflictItemCount", conflictItemCount);
         }
 
         return node;
     }
 
     /**
      * State of conflict resolution processing, to make this component (held in session) re-entrant by multiple threads.
      */
     private static class State {
         /**
          * Verbosity to be applied, see {@link ConflictResolver.Verbosity}.
          */
         private final ConflictResolver.Verbosity verbosity;
 
         /**
          * Whether to show nodes entering cycles, for easier identification. If this is enabled, this implementation
          * of conflict resolver will show more data than classic.
          */
         private final boolean showCyclesInStandardVerbosity;
 
         /**
          * The {@link ConflictResolver.VersionSelector} to use.
          */
         private final ConflictResolver.VersionSelector versionSelector;
 
         /**
          * The {@link ConflictResolver.ScopeSelector} to use.
          */
         private final ConflictResolver.ScopeSelector scopeSelector;
 
         /**
          * The {@link ConflictResolver.ScopeDeriver} to use.
          */
         private final ConflictResolver.ScopeDeriver scopeDeriver;
 
         /**
          * The {@link ConflictResolver.OptionalitySelector} to use/
          */
         private final ConflictResolver.OptionalitySelector optionalitySelector;
 
         /**
          * The node to conflictId mapping from {@link ConflictMarker}.
          */
         private final Map<DependencyNode, String> conflictIds;
 
         /**
          * A mapping from conflictId to paths represented as {@link Path}s that exist for each conflictId. In other
          * words all paths to each {@link DependencyNode} that are member of same conflictId group.
          * Uses {@link ArrayList} per partition; out-of-scope paths are marked via {@link Path#outOfScope} flag
          * and filtered at query time, avoiding the per-entry overhead of LinkedHashSet/HashMap.Node.
          */
         private final Map<String, List<Path>> partitions;
 
         /**
          * A mapping from conflictIds to winner {@link Path}, hence {@link DependencyNode}  for given conflictId.
          */
         private final Map<String, Path> resolvedIds;
 
         /**
          * The root {@link Path}.
          */
         private final Path root;
 
         /**
          * Pooled {@link ScopeContext} instance reused across derive() calls to avoid allocating a new
          * object per node. Reset via {@link ScopeContext#reset(String, String)} before each use.
          */
         private final ScopeContext scopeContext;
 
         @SuppressWarnings("checkstyle:ParameterNumber")
         private State(
                 ConflictResolver.Verbosity verbosity,
                 boolean showCyclesInStandardVerbosity,
                 ConflictResolver.VersionSelector versionSelector,
                 ConflictResolver.ScopeSelector scopeSelector,
                 ConflictResolver.ScopeDeriver scopeDeriver,
                 ConflictResolver.OptionalitySelector optionalitySelector,
                 Map<DependencyNode, String> conflictIds,
                 int conflictIdCount,
                 DependencyNode node)
                 throws RepositoryException {
             this.verbosity = verbosity;
             this.showCyclesInStandardVerbosity = showCyclesInStandardVerbosity;
             this.versionSelector = versionSelector;
             this.scopeSelector = scopeSelector;
             this.scopeDeriver = scopeDeriver;
             this.optionalitySelector = optionalitySelector;
             this.conflictIds = conflictIds;
             // Right-size maps: conflictIdCount gives exact number of partitions and resolved entries
             this.partitions = new HashMap<>(conflictIdCount * 4 / 3 + 1);
             this.resolvedIds = new HashMap<>(conflictIdCount * 4 / 3 + 1);
             this.scopeContext = new ScopeContext(null, null);
             this.root = build(node);
         }
 
         /**
          * Consumes the dirty graph and builds internal structures out of {@link Path} instances that is always a
          * tree. As a side effect, {@link #partitions} are being filled up as well, that combined with topo
          * sorted conflictIds can serve as a starting to point to walk the graph.
          */
         private Path build(DependencyNode node) throws RepositoryException {
             String nodeConflictId = this.conflictIds.get(node);
             Path root = new Path(this, node, nodeConflictId, null);
             gatherCRNodes(root);
             return root;
         }
 
         /**
          * Iteratively builds {@link Path} graph by observing each node associated {@link DependencyNode}.
          * Uses an explicit stack instead of recursion to avoid {@link StackOverflowError} on very deep
          * dependency graphs (reported in large multi-module projects with 13+ levels of recursion).
          */
         private void gatherCRNodes(Path root) throws RepositoryException {
             ArrayList<Path> stack = new ArrayList<>();
             stack.add(root);
             while (!stack.isEmpty()) {
                 Path node = stack.remove(stack.size() - 1);
                 List<DependencyNode> children = node.dn.getChildren();
                 if (!children.isEmpty()) {
                     // add children; we will get back those really added (not causing cycles)
                     List<Path> added = node.addChildren(children);
                     // push in reverse order so first child is processed first (DFS order)
                     for (int i = added.size() - 1; i >= 0; i--) {
                         stack.add(added.get(i));
                     }
                 }
             }
         }
     }
 
     /**
      * Represents a unique path within the dependency graph from the root to a specific {@link DependencyNode}.
      * This is the core data structure that enables the O(N) performance of {@link PathConflictResolver}.
      * <p>
      * <strong>Key Concepts:</strong>
      * <ul>
      * <li><strong>Path Uniqueness:</strong> Each {@code Path} instance represents a distinct route through
      *     the dependency graph, even if multiple paths lead to the same {@code DependencyNode}</li>
      * <li><strong>Cycle-Free Structure:</strong> The {@code Path} tree is guaranteed to be acyclic, even
      *     when the original dependency graph contains cycles</li>
      * <li><strong>Parallel Structure:</strong> This creates a "clean" tree alongside the original "dirty"
      *     graph for efficient processing</li>
      * </ul>
      * <p>
      * <strong>Example:</strong> If dependency A appears in the graph via two different routes:
      * <pre>
      * Root → B → A (path 1)
      * Root → C → A (path 2)
      * </pre>
      * Two separate {@code Path} instances will be created, both pointing to the same {@code DependencyNode} A,
      * but representing different paths through the dependency tree.
      * <p>
      * <strong>Memory Optimization:</strong> While this creates additional objects, it enables the algorithm
      * to process conflicts in O(N) time rather than O(N²), making it much more efficient for large graphs.
      * <p>
      * <strong>Conflict Resolution:</strong> Paths are grouped by conflict ID (based on groupId:artifactId:classifier:extension coordinates),
      * and the conflict resolution algorithm can efficiently process each group independently.
      */
     private static class Path {
         // given
         private final State state;
         private DependencyNode dn;
         private final String conflictId;
         private final Path parent;
         // derived
         private final int depth;
         // Lazy: null for leaf nodes (never populated by addChildren), right-sized for non-leaves.
         // This avoids allocating an ArrayList + backing array for every leaf node in the tree
         // (typically 60-70% of all nodes), saving ~40 bytes per leaf.
         private List<Path> children;
         // mutated
         private String scope;
         private boolean optional;
         // Flag used instead of removing from partition sets; avoids LinkedHashSet overhead (~48 bytes/entry)
         private boolean outOfScope;
 
         private Path(State state, DependencyNode dn, String conflictId, Path parent) {
             this.state = state;
             this.dn = dn;
             this.conflictId = conflictId;
             this.parent = parent;
             this.depth = parent != null ? parent.depth + 1 : 0;
             pull(0);
 
             this.state
                     .partitions
                     .computeIfAbsent(this.conflictId, k -> new ArrayList<>())
                     .add(this);
         }
 
         /**
          * Checks whether the given conflictId appears on the path from this node to the root.
          * This replaces the previous approach of copying a HashSet at every child, which was the
          * dominant source of memory consumption (millions of HashMap.Node objects for large graphs).
          */
         private boolean hasConflictIdOnPathToRoot(String targetConflictId) {
             Path current = this;
             while (current != null) {
                 if (Objects.equals(current.conflictId, targetConflictId)) {
                     return true;
                 }
                 current = current.parent;
             }
             return false;
         }
 
         /**
          * Pulls (possibly updated) scope and optional values from associated {@link DependencyNode} to this instance,
          * going down toward children recursively the required count of levels.
          */
         private void pull(int levels) {
             Dependency d = dn.getDependency();
             if (d != null) {
                 this.scope = d.getScope();
                 this.optional = d.isOptional();
             } else {
                 this.scope = "";
                 this.optional = false;
             }
             int newLevels = levels - 1;
             if (newLevels >= 0 && this.children != null) {
                 for (Path child : this.children) {
                     child.pull(newLevels);
                 }
             }
         }
 
         /**
          * Derives (from this to children direction) values that are "inherited" in tree: scope and optionality in the tree
          * recursively going down required count of "levels".
          */
         private void derive(int levels, boolean winner) throws RepositoryException {
             if (!winner) {
                 if (this.parent != null) {
                     if ((dn.getManagedBits() & DependencyNode.MANAGED_SCOPE) == 0) {
                         state.scopeContext.reset(this.parent.scope, this.scope);
                         state.scopeDeriver.deriveScope(state.scopeContext);
                         this.scope = state.scopeContext.derivedScope;
                     }
                     if ((dn.getManagedBits() & DependencyNode.MANAGED_OPTIONAL) == 0) {
                         if (!this.optional && this.parent.optional) {
                             this.optional = true;
                         }
                     }
                 } else {
                     this.scope = "";
                     this.optional = false;
                 }
             }
             int newLevels = levels - 1;
             if (newLevels >= 0 && this.children != null) {
                 for (Path child : this.children) {
                     child.derive(newLevels, false);
                 }
             }
         }
 
         /**
          * Pushes (applies) the scope and optional and structural changes to associated {@link DependencyNode} modifying
          * the graph of it. Verbosity is observed, and depending on it the conflicting/loser nodes are removed, or
          * just their children is removed (with special care for version ranges, see {@link #relatedSiblingsCount(Artifact, Path)}
          * or by just doing nothing with them only marking losers in full verbosity mode.
          */
         private void push(int levels) {
             if (this.parent != null) {
                 Path winner = this.state.resolvedIds.get(this.conflictId);
                 if (winner == null) {
                     throw new IllegalStateException(
                             "Winner selection did not happen for conflictId=" + this.conflictId);
                 }
                 if (!Objects.equals(winner.conflictId, this.conflictId)) {
                     throw new IllegalStateException(
                             "ConflictId mix-up: this=" + this.conflictId + " winner=" + winner.conflictId);
                 }
 
                 if (winner == this) {
                     // copy onto dn; if applicable
                     if (this.dn.getDependency() != null) {
                         this.dn.setData(
                                 ConflictResolver.NODE_DATA_ORIGINAL_SCOPE,
                                 this.dn.getDependency().getScope());
                         this.dn.setData(
                                 ConflictResolver.NODE_DATA_ORIGINAL_OPTIONALITY,
                                 this.dn.getDependency().getOptional());
                         this.dn.setScope(this.scope);
                         this.dn.setOptional(this.optional);
                     }
                 } else {
                     // loser; move out of scope
                     moveOutOfScope();
                     boolean markLoser = false;
                     switch (state.verbosity) {
                         case NONE:
                             // remove loser dn
                             if (this.parent.children != null) {
                                 this.parent.children.remove(this);
                             }
                             this.parent.dn.setChildren(new ArrayList<>(this.parent.dn.getChildren()));
                             this.parent.dn.getChildren().remove(this.dn);
                             this.children = null;
                             break;
                         case STANDARD:
                             // is redundant if:
                             // - is not same as winner, and has related siblings (version range)
                             // - same instance of DN is direct dependency on path leading here
                             boolean isRedundant =
                                     (!ArtifactIdUtils.equalsId(this.dn.getArtifact(), winner.dn.getArtifact())
                                             && relatedSiblingsCount(this.dn.getArtifact(), this.parent) > 1);
                             if (!this.state.showCyclesInStandardVerbosity) {
                                 isRedundant = isRedundant
                                         || this.parent.isDirectDependencyOnPathToRoot(this.dn.getArtifact());
                             }
                             if (isRedundant) {
                                 // is redundant dn; remove dn
                                 if (this.parent.children != null) {
                                     this.parent.children.remove(this);
                                 }
                                 this.parent.dn.setChildren(new ArrayList<>(this.parent.dn.getChildren()));
                                 this.parent.dn.getChildren().remove(this.dn);
                                 this.children = null;
                             } else {
                                 // copy loser dn; without children
                                 DependencyNode dnCopy = new DefaultDependencyNode(this.dn);
                                 dnCopy.setChildren(Collections.emptyList());
 
                                 // swap it out in DN graph; in case of cycles this may happen more than once
                                 int idx = this.parent.dn.getChildren().indexOf(this.dn);
                                 if (idx >= 0) {
                                     this.parent.dn.getChildren().set(idx, dnCopy);
                                 }
                                 this.dn = dnCopy;
 
                                 this.children = null;
                                 markLoser = true;
                             }
                             break;
                         case FULL:
                             // copy loser dn; with children
                             DependencyNode dnCopy = new DefaultDependencyNode(this.dn);
                             dnCopy.setChildren(new ArrayList<>(this.dn.getChildren()));
 
                             // swap it out in DN graph; in case of cycles this may happen more than once
                             int idx = this.parent.dn.getChildren().indexOf(this.dn);
                             if (idx >= 0) {
                                 this.parent.dn.getChildren().set(idx, dnCopy);
                             }
                             this.dn = dnCopy;
 
                             markLoser = true;
                             break;
                         default:
                             throw new IllegalArgumentException("Unknown " + state.verbosity);
                     }
                     if (markLoser) {
                         this.dn.setData(ConflictResolver.NODE_DATA_WINNER, winner.dn);
                         this.dn.setData(
                                 ConflictResolver.NODE_DATA_ORIGINAL_SCOPE,
                                 this.dn.getDependency().getScope());
                         this.dn.setData(
                                 ConflictResolver.NODE_DATA_ORIGINAL_OPTIONALITY,
                                 this.dn.getDependency().getOptional());
                         this.dn.setScope(this.scope);
                         this.dn.setOptional(this.optional);
                     }
                 }
             }
 
             // Note: push() is always called with levels=0, so newLevels would be -1
             // and the recursive block would never execute. The recursive structure is
             // intentionally not present; all push() calls happen from the main loop.
         }
 
         /**
          * Returns {@code true} if given artifact is a direct dependency on the path leading from this toward root.
          * A "direct dependency" is one at depth 1 (immediate child of root). Rather than recursing through every
          * ancestor, this walks directly to the depth-1 node and performs one allocation-free comparison.
          * <p>
          * Note: this check and use of this method is ONLY present to make this conflict resolver produce SAME output
          * as {@link ClassicConflictResolver} does, but IMHO this rule here is very arbitrary, moreover, in "standard"
          * (where it is only used) verbosity it in facts HIDES the trace of possible cycles.
          *
          * @see #CONFIG_PROP_SHOW_CYCLES_IN_STANDARD_VERBOSITY
          */
         private boolean isDirectDependencyOnPathToRoot(Artifact artifact) {
             // Walk up to depth-1 ancestor (direct dependency of root) instead of recursing every level
             Path current = this;
             while (current != null && current.depth > 1) {
                 current = current.parent;
             }
             return current != null
                     && current.depth == 1
                     && ArtifactIdUtils.equalsVersionlessId(current.dn.getArtifact(), artifact);
         }
 
         /**
          * Counts "relatives" (GACE equal) artifacts under same parent; this is for cleaning up redundant nodes in
          * case of version ranges, where same GACE is resolved into multiple GACEV as range is resolved. In {@link ConflictResolver.Verbosity#STANDARD}
          * verbosity mode we remove "redundant" nodes (of a range) leaving only "winner equal" loser, that have same GACEV as winner.
          */
         private int relatedSiblingsCount(Artifact artifact, Path parent) {
             if (parent.children == null) {
                 return 0;
             }
             String groupId = artifact.getGroupId();
             String artifactId = artifact.getArtifactId();
             int count = 0;
             for (Path n : parent.children) {
                 Artifact a = n.dn.getArtifact();
                 if (Objects.equals(groupId, a.getGroupId()) && Objects.equals(artifactId, a.getArtifactId())) {
                     count++;
                 }
             }
             return count;
         }
 
         /**
          * Marks this and all child {@link Path} nodes as out of scope; essentially marks whole subtree
          * from "this and below" as loser, to not be considered in subsequent winner selections.
          * Uses a boolean flag instead of removing from partition collections, avoiding the per-entry
          * overhead of LinkedHashSet (~48 bytes/entry). Out-of-scope paths are filtered at query time.
          * <p>
          * Uses an explicit stack instead of recursion to avoid {@link StackOverflowError} on deep
          * dependency graphs, consistent with the iterative approach in
          * {@link State#gatherCRNodes(Path)}. Also nulls children references on out-of-scope nodes
          * to allow GC of detached subtrees during resolution.
          */
         private void moveOutOfScope() {
             ArrayList<Path> stack = new ArrayList<>();
             stack.add(this);
             while (!stack.isEmpty()) {
                 Path node = stack.remove(stack.size() - 1);
                 node.outOfScope = true;
                 if (node.children != null) {
                     stack.addAll(node.children);
                     node.children = null;
                 }
             }
         }
 
         /**
          * Adds node children: this method should be "batch" used, as all (potential) children should be added at once.
          * Method will return really added {@link Path} instances, as this class avoids cycles. Those forming a cycle
          * are not recursed (not returned in list), keeping {@link Path} cycle free.
          * <p>
          * Cycle detection is performed by walking up the parent chain via
          * {@link #hasConflictIdOnPathToRoot(String)} instead of maintaining a per-node set, trading O(depth) per
          * check for dramatically reduced memory allocation on large dependency graphs.
          * This implies that this conflict resolver, by its nature "redoes" the
          * {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} calculated by {@link ConflictIdSorter}.
          */
         private List<Path> addChildren(List<DependencyNode> children) throws RepositoryException {
             // Right-size the children list to avoid ArrayList default capacity waste
             this.children = new ArrayList<>(children.size());
             ArrayList<Path> added = new ArrayList<>(children.size());
             for (DependencyNode child : children) {
                 String childConflictId = this.state.conflictIds.get(child);
                 boolean cycle = hasConflictIdOnPathToRoot(childConflictId);
                 Path c = new Path(this.state, child, childConflictId, this);
                 this.children.add(c);
                 c.derive(0, false);
                 if (!cycle) {
                     added.add(c);
                 }
             }
             return added;
         }
 
         /**
          * Dump for debug.
          */
         private void dump(String padding) {
             System.out.println(padding + this.dn + ": " + this.scope + "/" + this.optional);
             if (this.children != null) {
                 for (Path child : this.children) {
                     child.dump(padding + "  ");
                 }
             }
         }
 
         /**
          * For easier debug.
          */
         @Override
         public String toString() {
             return this.dn.toString();
         }
     }
 
     /**
      * A context used to hold information that is relevant for deriving the scope of a child dependency.
      *
      * @see ConflictResolver.ScopeDeriver
      * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may
      *                change without notice and only exists to enable unit testing
      */
     private static final class ScopeContext extends ConflictResolver.ScopeContext {
         private String parentScope;
         private String childScope;
         private String derivedScope;
 
         /**
          * Creates a new scope context with the specified properties.
          *
          * @param parentScope the scope of the parent dependency, may be {@code null}
          * @param childScope the scope of the child dependency, may be {@code null}
          * @noreference This class is not intended to be instantiated by clients in production code, the constructor may
          *              change without notice and only exists to enable unit testing
          */
         private ScopeContext(String parentScope, String childScope) {
             this.parentScope = (parentScope != null) ? parentScope : "";
             this.derivedScope = (childScope != null) ? childScope : "";
             this.childScope = (childScope != null) ? childScope : "";
         }
 
         /**
          * Resets this context for reuse, avoiding allocation of a new instance per derive() call.
          */
         private void reset(String parentScope, String childScope) {
             this.parentScope = (parentScope != null) ? parentScope : "";
             this.derivedScope = (childScope != null) ? childScope : "";
             this.childScope = (childScope != null) ? childScope : "";
         }
 
         /**
          * Gets the scope of the parent dependency. This is usually the scope that was derived by earlier invocations of
          * the scope deriver.
          *
          * @return the scope of the parent dependency, never {@code null}
          */
         public String getParentScope() {
             return parentScope;
         }
 
         /**
          * Gets the original scope of the child dependency. This is the scope that was declared in the artifact
          * descriptor of the parent dependency.
          *
          * @return the original scope of the child dependency, never {@code null}
          */
         public String getChildScope() {
             return childScope;
         }
 
         /**
          * Gets the derived scope of the child dependency. This is initially equal to {@link #getChildScope()} until the
          * scope deriver makes changes.
          *
          * @return the derived scope of the child dependency, never {@code null}
          */
         public String getDerivedScope() {
             return derivedScope;
         }
 
         /**
          * Sets the derived scope of the child dependency.
          *
          * @param derivedScope the derived scope of the dependency, may be {@code null}
          */
         public void setDerivedScope(String derivedScope) {
             this.derivedScope = (derivedScope != null) ? derivedScope : "";
         }
     }
 
     /**
      * A conflicting dependency.
      *
      * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may
      *                change without notice and only exists to enable unit testing
      */
     private static final class ConflictItem extends ConflictResolver.ConflictItem {
         private final Path path;
         private final List<DependencyNode> parent;
         private final Artifact artifact;
         private final DependencyNode node;
         private final int depth;
         private final String scope;
         private final int optionalities;
 
         private ConflictItem(Path path) {
             this.path = path;
             if (path.parent != null) {
                 DependencyNode parent = path.parent.dn;
                 this.parent = parent.getChildren();
                 this.artifact = parent.getArtifact();
             } else {
                 this.parent = null;
                 this.artifact = null;
             }
             this.node = path.dn;
             this.depth = path.depth;
             this.scope = path.scope;
             this.optionalities = path.optional ? OPTIONAL_TRUE : OPTIONAL_FALSE;
         }
 
         /**
          * Determines whether the specified conflict item is a sibling of this item.
          *
          * @param item the other conflict item, must not be {@code null}
          * @return {@code true} if the given item has the same parent as this item, {@code false} otherwise
          */
         @Override
         public boolean isSibling(ConflictResolver.ConflictItem item) {
             return parent == ((ConflictItem) item).parent;
         }
 
         /**
          * Gets the dependency node involved in the conflict.
          *
          * @return the involved dependency node, never {@code null}
          */
         @Override
         public DependencyNode getNode() {
             return node;
         }
 
         /**
          * Gets the dependency involved in the conflict, short for {@code getNode.getDependency()}.
          *
          * @return the involved dependency, never {@code null}
          */
         @Override
         public Dependency getDependency() {
             return node.getDependency();
         }
 
         /**
          * Gets the zero-based depth at which the conflicting node occurs in the graph. As such, the depth denotes the
          * number of parent nodes. If actually multiple paths lead to the node, the return value denotes the smallest
          * possible depth.
          *
          * @return the zero-based depth of the node in the graph
          */
         @Override
         public int getDepth() {
             return depth;
         }
 
         /**
          * Gets the derived scopes of the dependency. In general, the same dependency node could be reached via
          * different paths and each path might result in a different derived scope.
          *
          * @return the (read-only) set of derived scopes of the dependency, never {@code null}
          * @see ConflictResolver.ScopeDeriver
          */
         @Override
         public Collection<String> getScopes() {
             return Collections.singleton(scope);
         }
 
         /**
          * Gets the derived optionalities of the dependency. In general, the same dependency node could be reached via
          * different paths and each path might result in a different derived optionality.
          *
          * @return a bit field consisting of {@link PathConflictResolver.ConflictItem#OPTIONAL_FALSE} and/or
          *         {@link PathConflictResolver.ConflictItem#OPTIONAL_TRUE} indicating the derived optionalities the
          *         dependency was encountered with
          */
         @Override
         public int getOptionalities() {
             return optionalities;
         }
 
         @Override
         public String toString() {
             return node + " @ " + depth + " < " + artifact;
         }
     }
 
     /**
      * A context used to hold information that is relevant for resolving version and scope conflicts.
      *
      * @see ConflictResolver.VersionSelector
      * @see ConflictResolver.ScopeSelector
      * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may
      *                change without notice and only exists to enable unit testing
      */
     private static final class ConflictContext extends ConflictResolver.ConflictContext {
         private final DependencyNode root;
         private final Map<DependencyNode, String> conflictIds;
         private final Collection<ConflictResolver.ConflictItem> items;
         private final String conflictId;
 
         // elected properties
         private ConflictItem winner;
         private String scope;
         private Boolean optional;
 
         private ConflictContext(
                 DependencyNode root,
                 Map<DependencyNode, String> conflictIds,
                 Collection<ConflictItem> items,
                 String conflictId) {
             this.root = root;
             this.conflictIds = conflictIds;
             this.items = Collections.unmodifiableCollection(items);
             this.conflictId = conflictId;
         }
 
         /**
          * Gets the root node of the dependency graph being transformed.
          *
          * @return the root node of the dependency graph, never {@code null}
          */
         @Override
         public DependencyNode getRoot() {
             return root;
         }
 
         /**
          * Determines whether the specified dependency node belongs to this conflict context.
          *
          * @param node the dependency node to check, must not be {@code null}
          * @return {@code true} if the given node belongs to this conflict context, {@code false} otherwise
          */
         @Override
         public boolean isIncluded(DependencyNode node) {
             return conflictId.equals(conflictIds.get(node));
         }
 
         /**
          * Gets the collection of conflict items in this context.
          *
          * @return the (read-only) collection of conflict items in this context, never {@code null}
          */
         @Override
         public Collection<ConflictResolver.ConflictItem> getItems() {
             return items;
         }
 
         /**
          * Gets the conflict item which has been selected as the winner among the conflicting dependencies.
          *
          * @return the winning conflict item or {@code null} if not set yet
          */
         @Override
         public ConflictResolver.ConflictItem getWinner() {
             return winner;
         }
 
         /**
          * Sets the conflict item which has been selected as the winner among the conflicting dependencies.
          *
          * @param winner the winning conflict item, may be {@code null}
          */
         @Override
         public void setWinner(ConflictResolver.ConflictItem winner) {
             this.winner = (ConflictItem) winner;
         }
 
         /**
          * Gets the effective scope of the winning dependency.
          *
          * @return the effective scope of the winning dependency or {@code null} if none
          */
         @Override
         public String getScope() {
             return scope;
         }
 
         /**
          * Sets the effective scope of the winning dependency.
          *
          * @param scope the effective scope, may be {@code null}
          */
         @Override
         public void setScope(String scope) {
             this.scope = scope;
         }
 
         /**
          * Gets the effective optional flag of the winning dependency.
          *
          * @return the effective optional flag or {@code null} if none
          */
         @Override
         public Boolean getOptional() {
             return optional;
         }
 
         /**
          * Sets the effective optional flag of the winning dependency.
          *
          * @param optional the effective optional flag, may be {@code null}
          */
         @Override
         public void setOptional(Boolean optional) {
             this.optional = optional;
         }
 
         @Override
         public String toString() {
             return winner + " @ " + scope + " < " + items;
         }
     }
 }