View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *   http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.eclipse.aether.util.graph.transformer;
20  
21  import java.util.ArrayList;
22  import java.util.Collection;
23  import java.util.HashSet;
24  import java.util.Iterator;
25  import java.util.Objects;
26  import java.util.Set;
27  import java.util.stream.Collectors;
28  
29  import org.eclipse.aether.RepositoryException;
30  import org.eclipse.aether.collection.UnsolvableVersionConflictException;
31  import org.eclipse.aether.graph.DependencyFilter;
32  import org.eclipse.aether.graph.DependencyNode;
33  import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictContext;
34  import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictItem;
35  import org.eclipse.aether.util.graph.transformer.ConflictResolver.VersionSelector;
36  import org.eclipse.aether.util.graph.visitor.PathRecordingDependencyVisitor;
37  import org.eclipse.aether.util.graph.visitor.TreeDependencyVisitor;
38  import org.eclipse.aether.version.Version;
39  import org.eclipse.aether.version.VersionConstraint;
40  
41  import static java.util.Objects.requireNonNull;
42  
43  /**
44   * A configurable version selector for use with {@link ConflictResolver} that resolves version conflicts using a
45   * specified strategy. If there is no single node that satisfies all encountered version ranges, the selector will fail.
46   * Based on configuration, this selector may fail for other reasons as well.
47   *
48   * @since 2.0.0
49   */
50  public class ConfigurableVersionSelector extends VersionSelector {
51      /**
52       * The strategy how "winner" is being selected.
53       */
54      public interface SelectionStrategy {
55          /**
56           * Invoked for every "candidate" when winner is already set (very first candidate is set as winner).
57           * <p>
58           * This method should determine is candidate "better" or not and should replace current winner. This method
59           * is invoked whenever {@code candidate} is "considered" (fits any constraint in effect, if any).
60           */
61          boolean isBetter(ConflictItem candidate, ConflictItem winner);
62          /**
63           * Method invoked at version selection end, just before version selector returns. Note: {@code winner} may
64           * be {@code null}, while the rest of parameters cannot. The parameter {@code candidates} contains all the
65           * "considered candidates", dependencies that fulfil all constraints, if present. The {@code context} on the
66           * other hand contains all items participating in conflict.
67           * <p>
68           * This method by default just returns the passed in {@code winner}, but can do much more.
69           */
70          default ConflictItem winnerSelected(
71                  ConflictItem winner, Collection<ConflictItem> candidates, ConflictContext context)
72                  throws UnsolvableVersionConflictException {
73              return winner;
74          }
75      }
76      /**
77       * The strategy of winner selection, never {@code null}.
78       */
79      protected final SelectionStrategy selectionStrategy;
80  
81      /**
82       * Creates a new instance of this version selector that works "as Maven did so far".
83       */
84      public ConfigurableVersionSelector() {
85          this(new Nearest());
86      }
87  
88      /**
89       * Creates a new instance of this version selector.
90       *
91       * @param selectionStrategy The winner selection strategy, must not be {@code null}. Maven3
92       *                          used {@link Nearest} strategy.
93       */
94      public ConfigurableVersionSelector(SelectionStrategy selectionStrategy) {
95          this.selectionStrategy = requireNonNull(selectionStrategy, "selectionStrategy");
96      }
97  
98      @Override
99      public void selectVersion(ConflictContext context) throws RepositoryException {
100         ConflictGroup group = new ConflictGroup();
101         for (ConflictItem candidate : context.getItems()) {
102             DependencyNode node = candidate.getNode();
103             VersionConstraint constraint = node.getVersionConstraint();
104 
105             boolean backtrack = false;
106             boolean hardConstraint = constraint.getRange() != null;
107 
108             if (hardConstraint) {
109                 if (group.constraints.add(constraint)) {
110                     if (group.winner != null
111                             && !constraint.containsVersion(
112                                     group.winner.getNode().getVersion())) {
113                         backtrack = true;
114                     }
115                 }
116             }
117 
118             if (isAcceptableByConstraints(group, node.getVersion())) {
119                 group.candidates.add(candidate);
120 
121                 if (backtrack) {
122                     backtrack(group, context);
123                 } else if (group.winner == null || selectionStrategy.isBetter(candidate, group.winner)) {
124                     group.winner = candidate;
125                 }
126             } else if (backtrack) {
127                 backtrack(group, context);
128             }
129         }
130         context.setWinner(selectionStrategy.winnerSelected(group.winner, group.candidates, context));
131     }
132 
133     protected void backtrack(ConflictGroup group, ConflictContext context) throws UnsolvableVersionConflictException {
134         group.winner = null;
135 
136         for (Iterator<ConflictItem> it = group.candidates.iterator(); it.hasNext(); ) {
137             ConflictItem candidate = it.next();
138 
139             if (!isAcceptableByConstraints(group, candidate.getNode().getVersion())) {
140                 it.remove();
141             } else if (group.winner == null || selectionStrategy.isBetter(candidate, group.winner)) {
142                 group.winner = candidate;
143             }
144         }
145 
146         if (group.winner == null) {
147             throw newFailure("Unsolvable hard constraint combination", context);
148         }
149     }
150 
151     protected boolean isAcceptableByConstraints(ConflictGroup group, Version version) {
152         for (VersionConstraint constraint : group.constraints) {
153             if (!constraint.containsVersion(version)) {
154                 return false;
155             }
156         }
157         return true;
158     }
159 
160     /**
161      * Helper method to create failure, creates instance of {@link UnsolvableVersionConflictException}.
162      */
163     public static UnsolvableVersionConflictException newFailure(String message, ConflictContext context) {
164         DependencyFilter filter = (node, parents) -> {
165             requireNonNull(node, "node cannot be null");
166             requireNonNull(parents, "parents cannot be null");
167             return context.isIncluded(node);
168         };
169         PathRecordingDependencyVisitor visitor = new PathRecordingDependencyVisitor(filter);
170         context.getRoot().accept(new TreeDependencyVisitor(visitor));
171         return new UnsolvableVersionConflictException(message, visitor.getPaths());
172     }
173 
174     protected static class ConflictGroup {
175 
176         final Collection<VersionConstraint> constraints;
177 
178         final Collection<ConflictItem> candidates;
179 
180         ConflictItem winner;
181 
182         ConflictGroup() {
183             constraints = new HashSet<>();
184             candidates = new ArrayList<>(64);
185         }
186 
187         @Override
188         public String toString() {
189             return String.valueOf(winner);
190         }
191     }
192 
193     /**
194      * Selection strategy that selects "nearest" (to the root) version.
195      * <p>
196      * This is the "classic" Maven strategy.
197      */
198     public static class Nearest implements SelectionStrategy {
199         @Override
200         public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
201             if (candidate.isSibling(winner)) {
202                 return candidate
203                                 .getNode()
204                                 .getVersion()
205                                 .compareTo(winner.getNode().getVersion())
206                         > 0;
207             } else {
208                 return candidate.getDepth() < winner.getDepth();
209             }
210         }
211     }
212 
213     /**
214      * Selection strategy that selects "highest" version.
215      */
216     public static class Highest implements SelectionStrategy {
217         @Override
218         public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
219             return candidate.getNode().getVersion().compareTo(winner.getNode().getVersion()) > 0;
220         }
221     }
222 
223     /**
224      * Example selection strategy (used in tests and demos), is not recommended to be used in production.
225      * <p>
226      * Selection strategy that delegates to another selection strategy, and at the end enforces dependency convergence
227      * among candidates.
228      */
229     public static class VersionConvergence implements SelectionStrategy {
230         private final SelectionStrategy delegate;
231 
232         public VersionConvergence(SelectionStrategy delegate) {
233             this.delegate = requireNonNull(delegate, "delegate");
234         }
235 
236         @Override
237         public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
238             return delegate.isBetter(candidate, winner);
239         }
240 
241         @Override
242         public ConflictItem winnerSelected(
243                 ConflictItem winner, Collection<ConflictItem> candidates, ConflictContext context)
244                 throws UnsolvableVersionConflictException {
245             if (winner != null && winner.getNode().getVersionConstraint().getRange() == null) {
246                 Set<String> versions = candidates.stream()
247                         .map(c -> c.getDependency().getArtifact().getVersion())
248                         .collect(Collectors.toSet());
249                 if (versions.size() > 1) {
250                     throw newFailure(
251                             "Convergence violated for "
252                                     + winner.getDependency().getArtifact().getGroupId() + ":"
253                                     + winner.getDependency().getArtifact().getArtifactId() + ", versions present: "
254                                     + versions,
255                             context);
256                 }
257             }
258             return winner;
259         }
260     }
261 
262     /**
263      * Example selection strategy (used in tests and demos), is not recommended to be used in production.
264      * <p>
265      * Selection strategy that delegates to another selection strategy, and at end enforces aligned "major versions"
266      * among candidates.
267      */
268     public static class MajorVersionConvergence implements SelectionStrategy {
269         private final SelectionStrategy delegate;
270 
271         public MajorVersionConvergence(SelectionStrategy delegate) {
272             this.delegate = requireNonNull(delegate, "delegate");
273         }
274 
275         @Override
276         public boolean isBetter(ConflictItem candidate, ConflictItem winner) {
277             return delegate.isBetter(candidate, winner);
278         }
279 
280         @Override
281         public ConflictItem winnerSelected(
282                 ConflictItem winner, Collection<ConflictItem> candidates, ConflictContext context)
283                 throws UnsolvableVersionConflictException {
284             if (winner != null && !candidates.isEmpty()) {
285                 Set<String> incompatibleVersions = candidates.stream()
286                         .filter(c -> !sameMajor(c, winner))
287                         .map(c -> c.getDependency().getArtifact().getVersion())
288                         .collect(Collectors.toSet());
289                 if (!incompatibleVersions.isEmpty()) {
290                     Set<String> allVersions = candidates.stream()
291                             .map(c -> c.getDependency().getArtifact().getVersion())
292                             .collect(Collectors.toSet());
293                     throw newFailure(
294                             "Incompatible versions for "
295                                     + winner.getDependency().getArtifact().getGroupId() + ":"
296                                     + winner.getDependency().getArtifact().getArtifactId() + ", incompatible versions: "
297                                     + incompatibleVersions + ", all versions " + allVersions,
298                             context);
299                 }
300             }
301             return winner;
302         }
303 
304         private boolean sameMajor(ConflictItem candidate, ConflictItem winner) {
305             String candidateVersion = candidate.getDependency().getArtifact().getVersion();
306             String winnerVersion = winner.getDependency().getArtifact().getVersion();
307             // for now a naive check: major versions should be same
308             if (candidateVersion.contains(".") && winnerVersion.contains(".")) {
309                 String candidateMajor = candidateVersion.substring(0, candidateVersion.indexOf('.'));
310                 String winnerMajor = winnerVersion.substring(0, winnerVersion.indexOf('.'));
311                 return Objects.equals(candidateMajor, winnerMajor);
312             }
313             return true; // cannot determine, so just leave it
314         }
315     }
316 }