001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *   http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing,
013 * software distributed under the License is distributed on an
014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 * KIND, either express or implied.  See the License for the
016 * specific language governing permissions and limitations
017 * under the License.
018 */
019package org.eclipse.aether.util.graph.transformer;
020
021import java.util.ArrayList;
022import java.util.Arrays;
023import java.util.Collection;
024import java.util.HashSet;
025import java.util.Iterator;
026import java.util.Objects;
027import java.util.Set;
028import java.util.stream.Collectors;
029
030import org.eclipse.aether.ConfigurationProperties;
031import org.eclipse.aether.RepositoryException;
032import org.eclipse.aether.RepositorySystemSession;
033import org.eclipse.aether.collection.DependencyGraphTransformationContext;
034import org.eclipse.aether.collection.UnsolvableVersionConflictException;
035import org.eclipse.aether.graph.DependencyFilter;
036import org.eclipse.aether.graph.DependencyNode;
037import org.eclipse.aether.util.ConfigUtils;
038import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictContext;
039import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictItem;
040import org.eclipse.aether.util.graph.transformer.ConflictResolver.VersionSelector;
041import org.eclipse.aether.util.graph.visitor.PathRecordingDependencyVisitor;
042import org.eclipse.aether.util.graph.visitor.TreeDependencyVisitor;
043import org.eclipse.aether.version.Version;
044import org.eclipse.aether.version.VersionConstraint;
045
046import static java.util.Objects.requireNonNull;
047
048/**
049 * A configurable version selector for use with {@link ConflictResolver} that resolves version conflicts using a
050 * specified strategy. If there is no single node that satisfies all encountered version ranges, the selector will fail.
051 * Based on configuration, this selector may fail for other reasons as well.
052 *
053 * @since 2.0.0
054 */
055public class ConfigurableVersionSelector extends VersionSelector {
056    /**
057     * The name of the version selection strategy to use in conflict resolution: "nearest" (default) or "highest".
058     *
059     * @since 2.0.11
060     * @configurationSource {@link RepositorySystemSession#getConfigProperties()}
061     * @configurationType {@link java.lang.String}
062     * @configurationDefaultValue {@link #DEFAULT_SELECTION_STRATEGY}
063     */
064    public static final String CONFIG_PROP_SELECTION_STRATEGY =
065            ConfigurationProperties.PREFIX_AETHER + "conflictResolver.versionSelector.selectionStrategy";
066
067    public static final String NEAREST_SELECTION_STRATEGY = "nearest";
068    public static final String HIGHEST_SELECTION_STRATEGY = "highest";
069
070    public static final String DEFAULT_SELECTION_STRATEGY = NEAREST_SELECTION_STRATEGY;
071
072    /**
073     * The strategy how "winner" is being selected.
074     */
075    public interface SelectionStrategy {
076        /**
077         * Invoked for every "candidate" when winner is already set (very first candidate is set as winner).
078         * <p>
079         * This method should determine is candidate "better" or not and should replace current winner. This method
080         * is invoked whenever {@code candidate} is "considered" (fits any constraint in effect, if any).
081         */
082        boolean isBetter(ConflictItem candidate, ConflictItem winner);
083        /**
084         * Method invoked at version selection end, just before version selector returns. Note: {@code winner} may
085         * be {@code null}, while the rest of parameters cannot. The parameter {@code candidates} contains all the
086         * "considered candidates", dependencies that fulfil all constraints, if present. The {@code context} on the
087         * other hand contains all items participating in conflict.
088         * <p>
089         * This method by default just returns the passed in {@code winner}, but can do much more.
090         */
091        default ConflictItem winnerSelected(
092                ConflictItem winner, Collection<ConflictItem> candidates, ConflictContext context)
093                throws UnsolvableVersionConflictException {
094            return winner;
095        }
096    }
097
098    /**
099     * The strategy of winner selection, never {@code null}.
100     */
101    protected final SelectionStrategy selectionStrategy;
102
103    /**
104     * Creates a new instance of this version selector that will use configured selection strategy dynamically.
105     */
106    public ConfigurableVersionSelector() {
107        this.selectionStrategy = null;
108    }
109
110    /**
111     * Creates a new instance of this version selector using passed in selection strategy always.
112     *
113     * @param selectionStrategy The winner selection strategy, must not be {@code null}. Maven3
114     *                          used {@link Nearest} strategy.
115     */
116    public ConfigurableVersionSelector(SelectionStrategy selectionStrategy) {
117        this.selectionStrategy = requireNonNull(selectionStrategy, "selectionStrategy");
118    }
119
120    @Override
121    public VersionSelector getInstance(DependencyNode root, DependencyGraphTransformationContext context)
122            throws RepositoryException {
123        if (selectionStrategy == null) {
124            String ss = ConfigUtils.getString(
125                    context.getSession(), DEFAULT_SELECTION_STRATEGY, CONFIG_PROP_SELECTION_STRATEGY);
126            SelectionStrategy strategy;
127            if (NEAREST_SELECTION_STRATEGY.equals(ss)) {
128                strategy = new Nearest();
129            } else if (HIGHEST_SELECTION_STRATEGY.equals(ss)) {
130                strategy = new Highest();
131            } else {
132                throw new IllegalArgumentException("Unknown selection strategy: " + ss + "; known are "
133                        + Arrays.asList(NEAREST_SELECTION_STRATEGY, HIGHEST_SELECTION_STRATEGY));
134            }
135            return new ConfigurableVersionSelector(strategy);
136        } else {
137            return this;
138        }
139    }
140
141    @Override
142    public void selectVersion(ConflictContext context) throws RepositoryException {
143        ConflictGroup group = new ConflictGroup();
144        for (ConflictItem candidate : context.getItems()) {
145            DependencyNode node = candidate.getNode();
146            VersionConstraint constraint = node.getVersionConstraint();
147
148            boolean backtrack = false;
149            boolean hardConstraint = constraint.getRange() != null;
150
151            if (hardConstraint) {
152                if (group.constraints.add(constraint)) {
153                    if (group.winner != null
154                            && !constraint.containsVersion(
155                                    group.winner.getNode().getVersion())) {
156                        backtrack = true;
157                    }
158                }
159            }
160
161            if (isAcceptableByConstraints(group, node.getVersion())) {
162                group.candidates.add(candidate);
163
164                if (backtrack) {
165                    backtrack(group, context);
166                } else if (group.winner == null || selectionStrategy.isBetter(candidate, group.winner)) {
167                    group.winner = candidate;
168                }
169            } else if (backtrack) {
170                backtrack(group, context);
171            }
172        }
173        context.setWinner(selectionStrategy.winnerSelected(group.winner, group.candidates, context));
174    }
175
176    protected void backtrack(ConflictGroup group, ConflictContext context) throws UnsolvableVersionConflictException {
177        group.winner = null;
178
179        for (Iterator<ConflictItem> it = group.candidates.iterator(); it.hasNext(); ) {
180            ConflictItem candidate = it.next();
181
182            if (!isAcceptableByConstraints(group, candidate.getNode().getVersion())) {
183                it.remove();
184            } else if (group.winner == null || selectionStrategy.isBetter(candidate, group.winner)) {
185                group.winner = candidate;
186            }
187        }
188
189        if (group.winner == null) {
190            throw newFailure("Unsolvable hard constraint combination", context);
191        }
192    }
193
194    protected boolean isAcceptableByConstraints(ConflictGroup group, Version version) {
195        for (VersionConstraint constraint : group.constraints) {
196            if (!constraint.containsVersion(version)) {
197                return false;
198            }
199        }
200        return true;
201    }
202
203    @Override
204    public String toString() {
205        return getClass().getSimpleName() + "("
206                + (selectionStrategy != null ? selectionStrategy.getClass().getSimpleName() : "not inited") + ")";
207    }
208
209    /**
210     * Helper method to create failure, creates instance of {@link UnsolvableVersionConflictException}.
211     */
212    public static UnsolvableVersionConflictException newFailure(String message, ConflictContext context) {
213        DependencyFilter filter = (node, parents) -> {
214            requireNonNull(node, "node cannot be null");
215            requireNonNull(parents, "parents cannot be null");
216            return context.isIncluded(node);
217        };
218        PathRecordingDependencyVisitor visitor = new PathRecordingDependencyVisitor(filter);
219        context.getRoot().accept(new TreeDependencyVisitor(visitor));
220        return new UnsolvableVersionConflictException(message, visitor.getPaths());
221    }
222
223    protected static class ConflictGroup {
224
225        final Collection<VersionConstraint> constraints;
226
227        final Collection<ConflictItem> candidates;
228
229        ConflictItem winner;
230
231        ConflictGroup() {
232            constraints = new HashSet<>();
233            candidates = new ArrayList<>(64);
234        }
235
236        @Override
237        public String toString() {
238            return String.valueOf(winner);
239        }
240    }
241
242    /**
243     * Selection strategy that selects "nearest" (to the root) version.
244     * <p>
245     * This is the "classic" Maven strategy.
246     * <p>
247     * If candidates are siblings, it will select higher version (ie version ranges), otherwise item with smaller
248     * depth is selected.
249     */
250    public static class Nearest implements SelectionStrategy {
251        @Override
252        public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
253            if (candidate.isSibling(winner)) {
254                return candidate
255                                .getNode()
256                                .getVersion()
257                                .compareTo(winner.getNode().getVersion())
258                        > 0;
259            } else {
260                return candidate.getDepth() < winner.getDepth();
261            }
262        }
263    }
264
265    /**
266     * Selection strategy that selects "highest" version.
267     * <p>
268     * If winner is level 1 or less (is direct dependency of root), it is kept as winner (as in "real life" it means
269     * dependency is enlisted in POM). Then candidate is checked for same thing, and selected if it is direct dependency.
270     * Then if both, candidate and winner carries same version (so are same GACEV, same artifact) then "nearest" is selected.
271     * Finally, if none of above, higher version is selected out of two.
272     */
273    public static class Highest implements SelectionStrategy {
274        @Override
275        public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
276            if (winner.getDepth() <= 1) {
277                return false;
278            } else if (candidate.getDepth() <= 1) {
279                return true;
280            } else if (candidate.getNode().getVersion().equals(winner.getNode().getVersion())) {
281                return candidate.getDepth() < winner.getDepth();
282            } else {
283                return candidate
284                                .getNode()
285                                .getVersion()
286                                .compareTo(winner.getNode().getVersion())
287                        > 0;
288            }
289        }
290    }
291
292    /**
293     * Example selection strategy (used in tests and demos), is not recommended to be used in production.
294     * <p>
295     * Selection strategy that delegates to another selection strategy, and at the end enforces dependency convergence
296     * among candidates.
297     */
298    public static class VersionConvergence implements SelectionStrategy {
299        private final SelectionStrategy delegate;
300
301        public VersionConvergence(SelectionStrategy delegate) {
302            this.delegate = requireNonNull(delegate, "delegate");
303        }
304
305        @Override
306        public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
307            return delegate.isBetter(candidate, winner);
308        }
309
310        @Override
311        public ConflictItem winnerSelected(
312                ConflictItem winner, Collection<ConflictItem> candidates, ConflictContext context)
313                throws UnsolvableVersionConflictException {
314            if (winner != null && winner.getNode().getVersionConstraint().getRange() == null) {
315                Set<String> versions = candidates.stream()
316                        .map(c -> c.getDependency().getArtifact().getVersion())
317                        .collect(Collectors.toSet());
318                if (versions.size() > 1) {
319                    throw newFailure(
320                            "Convergence violated for "
321                                    + winner.getDependency().getArtifact().getGroupId() + ":"
322                                    + winner.getDependency().getArtifact().getArtifactId() + ", versions present: "
323                                    + versions,
324                            context);
325                }
326            }
327            return winner;
328        }
329    }
330
331    /**
332     * Example selection strategy (used in tests and demos), is not recommended to be used in production.
333     * <p>
334     * Selection strategy that delegates to another selection strategy, and at end enforces aligned "major versions"
335     * among candidates.
336     */
337    public static class MajorVersionConvergence implements SelectionStrategy {
338        private final SelectionStrategy delegate;
339
340        public MajorVersionConvergence(SelectionStrategy delegate) {
341            this.delegate = requireNonNull(delegate, "delegate");
342        }
343
344        @Override
345        public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
346            return delegate.isBetter(candidate, winner);
347        }
348
349        @Override
350        public ConflictItem winnerSelected(
351                ConflictItem winner, Collection<ConflictItem> candidates, ConflictContext context)
352                throws UnsolvableVersionConflictException {
353            if (winner != null && !candidates.isEmpty()) {
354                Set<String> incompatibleVersions = candidates.stream()
355                        .filter(c -> !sameMajor(c, winner))
356                        .map(c -> c.getDependency().getArtifact().getVersion())
357                        .collect(Collectors.toSet());
358                if (!incompatibleVersions.isEmpty()) {
359                    Set<String> allVersions = candidates.stream()
360                            .map(c -> c.getDependency().getArtifact().getVersion())
361                            .collect(Collectors.toSet());
362                    throw newFailure(
363                            "Incompatible versions for "
364                                    + winner.getDependency().getArtifact().getGroupId() + ":"
365                                    + winner.getDependency().getArtifact().getArtifactId() + ", incompatible versions: "
366                                    + incompatibleVersions + ", all versions " + allVersions,
367                            context);
368                }
369            }
370            return winner;
371        }
372
373        private boolean sameMajor(ConflictItem candidate, ConflictItem winner) {
374            String candidateVersion = candidate.getDependency().getArtifact().getVersion();
375            String winnerVersion = winner.getDependency().getArtifact().getVersion();
376            // for now a naive check: major versions should be same
377            if (candidateVersion.contains(".") && winnerVersion.contains(".")) {
378                String candidateMajor = candidateVersion.substring(0, candidateVersion.indexOf('.'));
379                String winnerMajor = winnerVersion.substring(0, winnerVersion.indexOf('.'));
380                return Objects.equals(candidateMajor, winnerMajor);
381            }
382            return true; // cannot determine, so just leave it
383        }
384    }
385}