/*
 * 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.HashSet;
import java.util.Iterator;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;

import org.eclipse.aether.RepositoryException;
import org.eclipse.aether.collection.UnsolvableVersionConflictException;
import org.eclipse.aether.graph.DependencyFilter;
import org.eclipse.aether.graph.DependencyNode;
import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictContext;
import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictItem;
import org.eclipse.aether.util.graph.transformer.ConflictResolver.VersionSelector;
import org.eclipse.aether.util.graph.visitor.PathRecordingDependencyVisitor;
import org.eclipse.aether.util.graph.visitor.TreeDependencyVisitor;
import org.eclipse.aether.version.Version;
import org.eclipse.aether.version.VersionConstraint;

import static java.util.Objects.requireNonNull;

/**
 * A configurable version selector for use with {@link ConflictResolver} that resolves version conflicts using a
 * specified strategy. If there is no single node that satisfies all encountered version ranges, the selector will fail.
 * Based on configuration, this selector may fail for other reasons as well.
 *
 * @since 2.0.0
 */
public class ConfigurableVersionSelector extends VersionSelector {
    /**
     * The strategy how "winner" is being selected.
     */
    public interface SelectionStrategy {
        /**
         * Invoked for every "candidate" when winner is already set (very first candidate is set as winner).
         * <p>
         * This method should determine is candidate "better" or not and should replace current winner. This method
         * is invoked whenever {@code candidate} is "considered" (fits any constraint in effect, if any).
         */
        boolean isBetter(ConflictItem candidate, ConflictItem winner);
        /**
         * Method invoked at version selection end, just before version selector returns. Note: {@code winner} may
         * be {@code null}, while the rest of parameters cannot. The parameter {@code candidates} contains all the
         * "considered candidates", dependencies that fulfil all constraints, if present. The {@code context} on the
         * other hand contains all items participating in conflict.
         * <p>
         * This method by default just returns the passed in {@code winner}, but can do much more.
         */
        default ConflictItem winnerSelected(
                ConflictItem winner, Collection<ConflictItem> candidates, ConflictContext context)
                throws UnsolvableVersionConflictException {
            return winner;
        }
    }
    /**
     * The strategy of winner selection, never {@code null}.
     */
    protected final SelectionStrategy selectionStrategy;

    /**
     * Creates a new instance of this version selector that works "as Maven did so far".
     */
    public ConfigurableVersionSelector() {
        this(new Nearest());
    }

    /**
     * Creates a new instance of this version selector.
     *
     * @param selectionStrategy The winner selection strategy, must not be {@code null}. Maven3
     *                          used {@link Nearest} strategy.
     */
    public ConfigurableVersionSelector(SelectionStrategy selectionStrategy) {
        this.selectionStrategy = requireNonNull(selectionStrategy, "selectionStrategy");
    }

    @Override
    public void selectVersion(ConflictContext context) throws RepositoryException {
        ConflictGroup group = new ConflictGroup();
        for (ConflictItem candidate : context.getItems()) {
            DependencyNode node = candidate.getNode();
            VersionConstraint constraint = node.getVersionConstraint();

            boolean backtrack = false;
            boolean hardConstraint = constraint.getRange() != null;

            if (hardConstraint) {
                if (group.constraints.add(constraint)) {
                    if (group.winner != null
                            && !constraint.containsVersion(
                                    group.winner.getNode().getVersion())) {
                        backtrack = true;
                    }
                }
            }

            if (isAcceptableByConstraints(group, node.getVersion())) {
                group.candidates.add(candidate);

                if (backtrack) {
                    backtrack(group, context);
                } else if (group.winner == null || selectionStrategy.isBetter(candidate, group.winner)) {
                    group.winner = candidate;
                }
            } else if (backtrack) {
                backtrack(group, context);
            }
        }
        context.setWinner(selectionStrategy.winnerSelected(group.winner, group.candidates, context));
    }

    protected void backtrack(ConflictGroup group, ConflictContext context) throws UnsolvableVersionConflictException {
        group.winner = null;

        for (Iterator<ConflictItem> it = group.candidates.iterator(); it.hasNext(); ) {
            ConflictItem candidate = it.next();

            if (!isAcceptableByConstraints(group, candidate.getNode().getVersion())) {
                it.remove();
            } else if (group.winner == null || selectionStrategy.isBetter(candidate, group.winner)) {
                group.winner = candidate;
            }
        }

        if (group.winner == null) {
            throw newFailure("Unsolvable hard constraint combination", context);
        }
    }

    protected boolean isAcceptableByConstraints(ConflictGroup group, Version version) {
        for (VersionConstraint constraint : group.constraints) {
            if (!constraint.containsVersion(version)) {
                return false;
            }
        }
        return true;
    }

    /**
     * Helper method to create failure, creates instance of {@link UnsolvableVersionConflictException}.
     */
    public static UnsolvableVersionConflictException newFailure(String message, ConflictContext context) {
        DependencyFilter filter = (node, parents) -> {
            requireNonNull(node, "node cannot be null");
            requireNonNull(parents, "parents cannot be null");
            return context.isIncluded(node);
        };
        PathRecordingDependencyVisitor visitor = new PathRecordingDependencyVisitor(filter);
        context.getRoot().accept(new TreeDependencyVisitor(visitor));
        return new UnsolvableVersionConflictException(message, visitor.getPaths());
    }

    protected static class ConflictGroup {

        final Collection<VersionConstraint> constraints;

        final Collection<ConflictItem> candidates;

        ConflictItem winner;

        ConflictGroup() {
            constraints = new HashSet<>();
            candidates = new ArrayList<>(64);
        }

        @Override
        public String toString() {
            return String.valueOf(winner);
        }
    }

    /**
     * Selection strategy that selects "nearest" (to the root) version.
     * <p>
     * This is the "classic" Maven strategy.
     */
    public static class Nearest implements SelectionStrategy {
        @Override
        public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
            if (candidate.isSibling(winner)) {
                return candidate
                                .getNode()
                                .getVersion()
                                .compareTo(winner.getNode().getVersion())
                        > 0;
            } else {
                return candidate.getDepth() < winner.getDepth();
            }
        }
    }

    /**
     * Selection strategy that selects "highest" version.
     */
    public static class Highest implements SelectionStrategy {
        @Override
        public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
            return candidate.getNode().getVersion().compareTo(winner.getNode().getVersion()) > 0;
        }
    }

    /**
     * Example selection strategy (used in tests and demos), is not recommended to be used in production.
     * <p>
     * Selection strategy that delegates to another selection strategy, and at the end enforces dependency convergence
     * among candidates.
     */
    public static class VersionConvergence implements SelectionStrategy {
        private final SelectionStrategy delegate;

        public VersionConvergence(SelectionStrategy delegate) {
            this.delegate = requireNonNull(delegate, "delegate");
        }

        @Override
        public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
            return delegate.isBetter(candidate, winner);
        }

        @Override
        public ConflictItem winnerSelected(
                ConflictItem winner, Collection<ConflictItem> candidates, ConflictContext context)
                throws UnsolvableVersionConflictException {
            if (winner != null && winner.getNode().getVersionConstraint().getRange() == null) {
                Set<String> versions = candidates.stream()
                        .map(c -> c.getDependency().getArtifact().getVersion())
                        .collect(Collectors.toSet());
                if (versions.size() > 1) {
                    throw newFailure(
                            "Convergence violated for "
                                    + winner.getDependency().getArtifact().getGroupId() + ":"
                                    + winner.getDependency().getArtifact().getArtifactId() + ", versions present: "
                                    + versions,
                            context);
                }
            }
            return winner;
        }
    }

    /**
     * Example selection strategy (used in tests and demos), is not recommended to be used in production.
     * <p>
     * Selection strategy that delegates to another selection strategy, and at end enforces aligned "major versions"
     * among candidates.
     */
    public static class MajorVersionConvergence implements SelectionStrategy {
        private final SelectionStrategy delegate;

        public MajorVersionConvergence(SelectionStrategy delegate) {
            this.delegate = requireNonNull(delegate, "delegate");
        }

        @Override
        public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
            return delegate.isBetter(candidate, winner);
        }

        @Override
        public ConflictItem winnerSelected(
                ConflictItem winner, Collection<ConflictItem> candidates, ConflictContext context)
                throws UnsolvableVersionConflictException {
            if (winner != null && !candidates.isEmpty()) {
                Set<String> incompatibleVersions = candidates.stream()
                        .filter(c -> !sameMajor(c, winner))
                        .map(c -> c.getDependency().getArtifact().getVersion())
                        .collect(Collectors.toSet());
                if (!incompatibleVersions.isEmpty()) {
                    Set<String> allVersions = candidates.stream()
                            .map(c -> c.getDependency().getArtifact().getVersion())
                            .collect(Collectors.toSet());
                    throw newFailure(
                            "Incompatible versions for "
                                    + winner.getDependency().getArtifact().getGroupId() + ":"
                                    + winner.getDependency().getArtifact().getArtifactId() + ", incompatible versions: "
                                    + incompatibleVersions + ", all versions " + allVersions,
                            context);
                }
            }
            return winner;
        }

        private boolean sameMajor(ConflictItem candidate, ConflictItem winner) {
            String candidateVersion = candidate.getDependency().getArtifact().getVersion();
            String winnerVersion = winner.getDependency().getArtifact().getVersion();
            // for now a naive check: major versions should be same
            if (candidateVersion.contains(".") && winnerVersion.contains(".")) {
                String candidateMajor = candidateVersion.substring(0, candidateVersion.indexOf('.'));
                String winnerMajor = winnerVersion.substring(0, winnerVersion.indexOf('.'));
                return Objects.equals(candidateMajor, winnerMajor);
            }
            return true; // cannot determine, so just leave it
        }
    }
}