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  
26  import org.eclipse.aether.RepositoryException;
27  import org.eclipse.aether.collection.UnsolvableVersionConflictException;
28  import org.eclipse.aether.graph.DependencyFilter;
29  import org.eclipse.aether.graph.DependencyNode;
30  import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictContext;
31  import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictItem;
32  import org.eclipse.aether.util.graph.transformer.ConflictResolver.VersionSelector;
33  import org.eclipse.aether.util.graph.visitor.PathRecordingDependencyVisitor;
34  import org.eclipse.aether.util.graph.visitor.TreeDependencyVisitor;
35  import org.eclipse.aether.version.Version;
36  import org.eclipse.aether.version.VersionConstraint;
37  
38  import static java.util.Objects.requireNonNull;
39  
40  /**
41   * A version selector for use with {@link ConflictResolver} that resolves version conflicts using a nearest-wins
42   * strategy. If there is no single node that satisfies all encountered version ranges, the selector will fail.
43   */
44  public final class NearestVersionSelector extends VersionSelector {
45  
46      /**
47       * Creates a new instance of this version selector.
48       */
49      public NearestVersionSelector() {}
50  
51      @Override
52      public void selectVersion(ConflictContext context) throws RepositoryException {
53          ConflictGroup group = new ConflictGroup();
54          for (ConflictItem item : context.getItems()) {
55              DependencyNode node = item.getNode();
56              VersionConstraint constraint = node.getVersionConstraint();
57  
58              boolean backtrack = false;
59              boolean hardConstraint = constraint.getRange() != null;
60  
61              if (hardConstraint) {
62                  if (group.constraints.add(constraint)) {
63                      if (group.winner != null
64                              && !constraint.containsVersion(
65                                      group.winner.getNode().getVersion())) {
66                          backtrack = true;
67                      }
68                  }
69              }
70  
71              if (isAcceptable(group, node.getVersion())) {
72                  group.candidates.add(item);
73  
74                  if (backtrack) {
75                      backtrack(group, context);
76                  } else if (group.winner == null || isNearer(item, group.winner)) {
77                      group.winner = item;
78                  }
79              } else if (backtrack) {
80                  backtrack(group, context);
81              }
82          }
83          context.setWinner(group.winner);
84      }
85  
86      private void backtrack(ConflictGroup group, ConflictContext context) throws UnsolvableVersionConflictException {
87          group.winner = null;
88  
89          for (Iterator<ConflictItem> it = group.candidates.iterator(); it.hasNext(); ) {
90              ConflictItem candidate = it.next();
91  
92              if (!isAcceptable(group, candidate.getNode().getVersion())) {
93                  it.remove();
94              } else if (group.winner == null || isNearer(candidate, group.winner)) {
95                  group.winner = candidate;
96              }
97          }
98  
99          if (group.winner == null) {
100             throw newFailure(context);
101         }
102     }
103 
104     private boolean isAcceptable(ConflictGroup group, Version version) {
105         for (VersionConstraint constraint : group.constraints) {
106             if (!constraint.containsVersion(version)) {
107                 return false;
108             }
109         }
110         return true;
111     }
112 
113     private boolean isNearer(ConflictItem item1, ConflictItem item2) {
114         if (item1.isSibling(item2)) {
115             return item1.getNode().getVersion().compareTo(item2.getNode().getVersion()) > 0;
116         } else {
117             return item1.getDepth() < item2.getDepth();
118         }
119     }
120 
121     private UnsolvableVersionConflictException newFailure(final ConflictContext context) {
122         DependencyFilter filter = (node, parents) -> {
123             requireNonNull(node, "node cannot be null");
124             requireNonNull(parents, "parents cannot be null");
125             return context.isIncluded(node);
126         };
127         PathRecordingDependencyVisitor visitor = new PathRecordingDependencyVisitor(filter);
128         context.getRoot().accept(new TreeDependencyVisitor(visitor));
129         return new UnsolvableVersionConflictException(visitor.getPaths());
130     }
131 
132     static final class ConflictGroup {
133 
134         final Collection<VersionConstraint> constraints;
135 
136         final Collection<ConflictItem> candidates;
137 
138         ConflictItem winner;
139 
140         ConflictGroup() {
141             constraints = new HashSet<>();
142             candidates = new ArrayList<>(64);
143         }
144 
145         @Override
146         public String toString() {
147             return String.valueOf(winner);
148         }
149     }
150 }