/*
 * 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 java.util.stream.Collectors;

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();

        @SuppressWarnings("unchecked")
        Collection<Collection<String>> conflictIdCycles =
                (Collection<Collection<String>>) context.get(TransformationContextKeys.CYCLIC_CONFLICT_IDS);
        if (conflictIdCycles == null) {
            throw new RepositoryException("conflict id cycles have not been identified");
        }

        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);

        state.build(node);

        // loop over topographically sorted conflictIds
        for (String conflictId : sortedConflictIds) {
            // paths in given conflict group to consider
            List<Path> paths = state.partitions.get(conflictId);
            if (paths.isEmpty()) {
                // this means that whole group "fall out of scope" (are all on loser branches); skip
                continue;
            }

            // create conflict context for given conflictId
            ConflictContext ctx = new ConflictContext(
                    node,
                    state.conflictIds,
                    paths.stream().map(ConflictItem::new).collect(Collectors.toList()),
                    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 " + ctx.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; note: node may remove itself from iterated list
            for (Path path : new ArrayList<>(paths)) {
                // 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
                path.children.forEach(c -> 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",
                    state.partitions.values().stream().map(List::size).reduce(0, Integer::sum));
        }

        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.
         */
        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;

        @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) {
            this.verbosity = verbosity;
            this.showCyclesInStandardVerbosity = showCyclesInStandardVerbosity;
            this.versionSelector = versionSelector;
            this.scopeSelector = scopeSelector;
            this.scopeDeriver = scopeDeriver;
            this.optionalitySelector = optionalitySelector;
            this.conflictIds = conflictIds;
            this.partitions = new HashMap<>();
            this.resolvedIds = new HashMap<>();
        }

        /**
         * 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 void build(DependencyNode node) throws RepositoryException {
            Path root = new Path(this, node, null, false);
            gatherCRNodes(root);
        }

        /**
         * Recursively builds {@link Path} graph by observing each node associated {@link DependencyNode}.
         */
        private void gatherCRNodes(Path node) throws RepositoryException {
            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);
                for (Path child : added) {
                    if (!child.cycle) {
                        gatherCRNodes(child);
                    }
                }
            }
        }
    }

    /**
     * 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 {
        private final State state;
        private DependencyNode dn;
        private final String conflictId;
        private final Path parent;
        private final boolean cycle;
        private final int depth;
        private final List<Path> children;
        private String scope;
        private boolean optional;

        private Path(State state, DependencyNode dn, Path parent, boolean cycle) {
            this.state = state;
            this.dn = dn;
            this.conflictId = state.conflictIds.get(dn);
            this.parent = parent;
            this.cycle = cycle;
            this.depth = parent != null ? parent.depth + 1 : 0;
            this.children = new ArrayList<>();
            pull(0);

            this.state
                    .partitions
                    .computeIfAbsent(this.conflictId, k -> new ArrayList<>())
                    .add(this);
        }

        /**
         * 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) {
                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) {
                        ScopeContext context = new ScopeContext(this.parent.scope, this.scope);
                        state.scopeDeriver.deriveScope(context);
                        this.scope = context.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) {
                for (Path child : 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
                            this.parent.children.remove(this);
                            this.parent.dn.setChildren(new ArrayList<>(this.parent.dn.getChildren()));
                            this.parent.dn.getChildren().remove(this.dn);
                            this.children.clear();
                            break;
                        case STANDARD:
                            String artifactId = ArtifactIdUtils.toId(this.dn.getArtifact());
                            String winnerArtifactId = ArtifactIdUtils.toId(winner.dn.getArtifact());
                            // 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 = (!Objects.equals(artifactId, winnerArtifactId)
                                    && 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
                                this.parent.children.remove(this);
                                this.parent.dn.setChildren(new ArrayList<>(this.parent.dn.getChildren()));
                                this.parent.dn.getChildren().remove(this.dn);
                                this.children.clear();
                            } 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.clear();
                                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);
                    }
                }
            }

            int newLevels = levels - 1;
            if (newLevels >= 0 && !this.children.isEmpty()) {
                // child may remove itself from iterated list
                for (Path child : new ArrayList<>(children)) {
                    child.push(newLevels);
                }
            }
        }

        /**
         * Returns {@code true} if given artifactId is direct dependency on the path leading from this toward root.
         * For some reason "classic" conflict resolver removes these.
         * <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) {
            if (this.depth == 1
                    && ArtifactIdUtils.toVersionlessId(this.dn.getArtifact())
                            .equals(ArtifactIdUtils.toVersionlessId(artifact))) {
                return true;
            } else if (this.parent != null) {
                return parent.isDirectDependencyOnPathToRoot(artifact);
            } else {
                return false;
            }
        }

        /**
         * 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) {
            String ga = artifact.getGroupId() + ":" + artifact.getArtifactId();
            return Math.toIntExact(parent.children.stream()
                    .map(n -> n.dn.getArtifact())
                    .filter(a -> ga.equals(a.getGroupId() + ":" + a.getArtifactId()))
                    .count());
        }

        /**
         * Removes this and all child {@link Path} nodes from winner selection scope; essentially marks whole subtree
         * from "this and below" as loser, to not be considered in subsequent winner selections.
         */
        private void moveOutOfScope() {
            this.state.partitions.get(this.conflictId).remove(this);
            for (Path child : this.children) {
                child.moveOutOfScope();
            }
        }

        /**
         * Adds node children: this method should be "batch" used, as all (potential) children should be added at once.
         * Method will return really added ones, as this class avoids cycles.
         */
        private List<Path> addChildren(List<DependencyNode> children) throws RepositoryException {
            ArrayList<Path> added = new ArrayList<>(children.size());
            for (DependencyNode child : children) {
                String childConflictId = this.state.conflictIds.get(child);
                boolean cycle = this.state.partitions.getOrDefault(childConflictId, Collections.emptyList()).stream()
                        .anyMatch(p -> p.dn.equals(child));
                Path c = new Path(this.state, child, this, cycle);
                this.children.add(c);
                c.derive(0, false);
                added.add(c);
            }
            return added;
        }

        /**
         * Dump for debug.
         */
        private void dump(String padding) {
            System.out.println(padding + this.dn + ": " + this.scope + "/" + this.optional);
            for (Path child : 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 final String parentScope;
        private final 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 : "";
        }

        /**
         * 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;
        }
    }
}