1 package org.eclipse.aether.util.graph.transformer;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 import java.util.ArrayList;
23 import java.util.Collection;
24 import java.util.HashSet;
25 import java.util.Iterator;
26 import java.util.List;
27
28 import org.eclipse.aether.RepositoryException;
29 import org.eclipse.aether.collection.UnsolvableVersionConflictException;
30 import org.eclipse.aether.graph.DependencyFilter;
31 import org.eclipse.aether.graph.DependencyNode;
32 import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictContext;
33 import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictItem;
34 import org.eclipse.aether.util.graph.transformer.ConflictResolver.VersionSelector;
35 import org.eclipse.aether.util.graph.visitor.PathRecordingDependencyVisitor;
36 import org.eclipse.aether.version.Version;
37 import org.eclipse.aether.version.VersionConstraint;
38
39
40
41
42
43 public final class NearestVersionSelector
44 extends VersionSelector
45 {
46
47
48
49
50 public NearestVersionSelector()
51 {
52 }
53
54 @Override
55 public void selectVersion( ConflictContext context )
56 throws RepositoryException
57 {
58 ConflictGroup group = new ConflictGroup();
59 for ( ConflictItem item : context.getItems() )
60 {
61 DependencyNode node = item.getNode();
62 VersionConstraint constraint = node.getVersionConstraint();
63
64 boolean backtrack = false;
65 boolean hardConstraint = constraint.getRange() != null;
66
67 if ( hardConstraint )
68 {
69 if ( group.constraints.add( constraint ) )
70 {
71 if ( group.winner != null && !constraint.containsVersion( group.winner.getNode().getVersion() ) )
72 {
73 backtrack = true;
74 }
75 }
76 }
77
78 if ( isAcceptable( group, node.getVersion() ) )
79 {
80 group.candidates.add( item );
81
82 if ( backtrack )
83 {
84 backtrack( group, context );
85 }
86 else if ( group.winner == null || isNearer( item, group.winner ) )
87 {
88 group.winner = item;
89 }
90 }
91 else if ( backtrack )
92 {
93 backtrack( group, context );
94 }
95 }
96 context.setWinner( group.winner );
97 }
98
99 private void backtrack( ConflictGroup group, ConflictContext context )
100 throws UnsolvableVersionConflictException
101 {
102 group.winner = null;
103
104 for ( Iterator<ConflictItem> it = group.candidates.iterator(); it.hasNext(); )
105 {
106 ConflictItem candidate = it.next();
107
108 if ( !isAcceptable( group, candidate.getNode().getVersion() ) )
109 {
110 it.remove();
111 }
112 else if ( group.winner == null || isNearer( candidate, group.winner ) )
113 {
114 group.winner = candidate;
115 }
116 }
117
118 if ( group.winner == null )
119 {
120 throw newFailure( context );
121 }
122 }
123
124 private boolean isAcceptable( ConflictGroup group, Version version )
125 {
126 for ( VersionConstraint constraint : group.constraints )
127 {
128 if ( !constraint.containsVersion( version ) )
129 {
130 return false;
131 }
132 }
133 return true;
134 }
135
136 private boolean isNearer( ConflictItem item1, ConflictItem item2 )
137 {
138 if ( item1.isSibling( item2 ) )
139 {
140 return item1.getNode().getVersion().compareTo( item2.getNode().getVersion() ) > 0;
141 }
142 else
143 {
144 return item1.getDepth() < item2.getDepth();
145 }
146 }
147
148 private UnsolvableVersionConflictException newFailure( final ConflictContext context )
149 {
150 DependencyFilter filter = new DependencyFilter()
151 {
152 public boolean accept( DependencyNode node, List<DependencyNode> parents )
153 {
154 return context.isIncluded( node );
155 }
156 };
157 PathRecordingDependencyVisitor visitor = new PathRecordingDependencyVisitor( filter );
158 context.getRoot().accept( visitor );
159 return new UnsolvableVersionConflictException( visitor.getPaths() );
160 }
161
162 static final class ConflictGroup
163 {
164
165 final Collection<VersionConstraint> constraints;
166
167 final Collection<ConflictItem> candidates;
168
169 ConflictItem winner;
170
171 ConflictGroup()
172 {
173 constraints = new HashSet<>();
174 candidates = new ArrayList<>( 64 );
175 }
176
177 @Override
178 public String toString()
179 {
180 return String.valueOf( winner );
181 }
182
183 }
184
185 }