1 package org.apache.maven.shared.dependency.graph.internal.maven30;
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.Collections;
25 import java.util.HashMap;
26 import java.util.HashSet;
27 import java.util.IdentityHashMap;
28 import java.util.LinkedHashMap;
29 import java.util.List;
30 import java.util.Map;
31
32 import org.sonatype.aether.RepositoryException;
33 import org.sonatype.aether.collection.DependencyGraphTransformationContext;
34 import org.sonatype.aether.collection.DependencyGraphTransformer;
35 import org.sonatype.aether.graph.DependencyNode;
36 import org.sonatype.aether.util.graph.transformer.ConflictMarker;
37 import org.sonatype.aether.util.graph.transformer.TransformationContextKeys;
38
39
40
41
42
43
44
45 public final class ConflictIdSorter
46 implements DependencyGraphTransformer
47 {
48
49 public DependencyNode transformGraph( DependencyNode node, DependencyGraphTransformationContext context )
50 throws RepositoryException
51 {
52 Map<?, ?> conflictIds = (Map<?, ?>) context.get( TransformationContextKeys.CONFLICT_IDS );
53 if ( conflictIds == null )
54 {
55 ConflictMarker marker = new ConflictMarker();
56 marker.transformGraph( node, context );
57
58 conflictIds = (Map<?, ?>) context.get( TransformationContextKeys.CONFLICT_IDS );
59 }
60
61
62
63
64
65 Map<Object, ConflictId> ids = new LinkedHashMap<>( 256 );
66
67
68 {
69 ConflictId id = null;
70 Object key = conflictIds.get( node );
71 if ( key != null )
72 {
73 id = new ConflictId( key, 0 );
74 ids.put( key, id );
75 }
76
77 Map<DependencyNode, Object> visited = new IdentityHashMap<>( conflictIds.size() );
78
79 buildConflitIdDAG( ids, node, id, 0, visited, conflictIds );
80 }
81
82
83
84
85 topsortConflictIds( ids.values(), context );
86
87
88
89
90
91
92
93
94
95
96
97 return node;
98 }
99
100 private void buildConflitIdDAG( Map<Object, ConflictId> ids, DependencyNode node, ConflictId id, int depth,
101 Map<DependencyNode, Object> visited, Map<?, ?> conflictIds )
102 {
103 if ( visited.put( node, Boolean.TRUE ) != null )
104 {
105 return;
106 }
107
108 depth++;
109
110 for ( DependencyNode child : node.getChildren() )
111 {
112 Object key = conflictIds.get( child );
113 ConflictId childId = ids.get( key );
114 if ( childId == null )
115 {
116 childId = new ConflictId( key, depth );
117 ids.put( key, childId );
118 }
119 else
120 {
121 childId.pullup( depth );
122 }
123
124 if ( id != null )
125 {
126 id.add( childId );
127 }
128
129 buildConflitIdDAG( ids, child, childId, depth, visited, conflictIds );
130 }
131 }
132
133 private int topsortConflictIds( Collection<ConflictId> conflictIds, DependencyGraphTransformationContext context )
134 {
135 List<Object> sorted = new ArrayList<>( conflictIds.size() );
136
137 RootQueue roots = new RootQueue( conflictIds.size() / 2 );
138 for ( ConflictId id : conflictIds )
139 {
140 if ( id.inDegree <= 0 )
141 {
142 roots.add( id );
143 }
144 }
145
146 processRoots( sorted, roots );
147
148 boolean cycle = sorted.size() < conflictIds.size();
149
150 while ( sorted.size() < conflictIds.size() )
151 {
152
153
154 ConflictId nearest = null;
155 for ( ConflictId id : conflictIds )
156 {
157 if ( id.inDegree <= 0 )
158 {
159 continue;
160 }
161 if ( nearest == null || id.minDepth < nearest.minDepth
162 || ( id.minDepth == nearest.minDepth && id.inDegree < nearest.inDegree ) )
163 {
164 nearest = id;
165 }
166 }
167
168 nearest.inDegree = 0;
169 roots.add( nearest );
170
171 processRoots( sorted, roots );
172 }
173
174 Collection<Collection<Object>> cycles = Collections.emptySet();
175 if ( cycle )
176 {
177 cycles = findCycles( conflictIds );
178 }
179
180 context.put( TransformationContextKeys.SORTED_CONFLICT_IDS, sorted );
181 context.put( TransformationContextKeys.CYCLIC_CONFLICT_IDS, cycles );
182
183 return cycles.size();
184 }
185
186 private void processRoots( List<Object> sorted, RootQueue roots )
187 {
188 while ( !roots.isEmpty() )
189 {
190 ConflictId root = roots.remove();
191
192 sorted.add( root.key );
193
194 for ( ConflictId child : root.children )
195 {
196 child.inDegree--;
197 if ( child.inDegree == 0 )
198 {
199 roots.add( child );
200 }
201 }
202 }
203 }
204
205 private Collection<Collection<Object>> findCycles( Collection<ConflictId> conflictIds )
206 {
207 Collection<Collection<Object>> cycles = new HashSet<>();
208
209 Map<Object, Integer> stack = new HashMap<>( 128 );
210 Map<ConflictId, Object> visited = new IdentityHashMap<>( conflictIds.size() );
211 for ( ConflictId id : conflictIds )
212 {
213 findCycles( id, visited, stack, cycles );
214 }
215
216 return cycles;
217 }
218
219 private void findCycles( ConflictId id, Map<ConflictId, Object> visited, Map<Object, Integer> stack,
220 Collection<Collection<Object>> cycles )
221 {
222 Integer depth = stack.put( id.key, stack.size() );
223 if ( depth != null )
224 {
225 stack.put( id.key, depth );
226 Collection<Object> cycle = new HashSet<>();
227 for ( Map.Entry<Object, Integer> entry : stack.entrySet() )
228 {
229 if ( entry.getValue() >= depth )
230 {
231 cycle.add( entry.getKey() );
232 }
233 }
234 cycles.add( cycle );
235 }
236 else
237 {
238 if ( visited.put( id, Boolean.TRUE ) == null )
239 {
240 for ( ConflictId childId : id.children )
241 {
242 findCycles( childId, visited, stack, cycles );
243 }
244 }
245 stack.remove( id.key );
246 }
247 }
248
249 static final class ConflictId
250 {
251
252 final Object key;
253
254 Collection<ConflictId> children = Collections.emptySet();
255
256 int inDegree;
257
258 int minDepth;
259
260 ConflictId( Object key, int depth )
261 {
262 this.key = key;
263 this.minDepth = depth;
264 }
265
266 public void add( ConflictId child )
267 {
268 if ( children.isEmpty() )
269 {
270 children = new HashSet<>();
271 }
272 if ( children.add( child ) )
273 {
274 child.inDegree++;
275 }
276 }
277
278 public void pullup( int depth )
279 {
280 if ( depth < minDepth )
281 {
282 minDepth = depth;
283 depth++;
284 for ( ConflictId child : children )
285 {
286 child.pullup( depth );
287 }
288 }
289 }
290
291 @Override
292 public boolean equals( Object obj )
293 {
294 if ( this == obj )
295 {
296 return true;
297 }
298 else if ( !( obj instanceof ConflictId ) )
299 {
300 return false;
301 }
302 ConflictId that = (ConflictId) obj;
303 return this.key.equals( that.key );
304 }
305
306 @Override
307 public int hashCode()
308 {
309 return key.hashCode();
310 }
311
312 @Override
313 public String toString()
314 {
315 return key + " @ " + minDepth + " <" + inDegree;
316 }
317
318 }
319
320 static final class RootQueue
321 {
322
323 private int nextOut;
324
325 private int nextIn;
326
327 private ConflictId[] ids;
328
329 RootQueue( int capacity )
330 {
331 ids = new ConflictId[capacity + 16];
332 }
333
334 boolean isEmpty()
335 {
336 return nextOut >= nextIn;
337 }
338
339 void add( ConflictId id )
340 {
341 if ( nextOut >= nextIn && nextOut > 0 )
342 {
343 nextIn -= nextOut;
344 nextOut = 0;
345 }
346 if ( nextIn >= ids.length )
347 {
348 ConflictId[] tmp = new ConflictId[ids.length + ids.length / 2 + 16];
349 System.arraycopy( ids, nextOut, tmp, 0, nextIn - nextOut );
350 ids = tmp;
351 nextIn -= nextOut;
352 nextOut = 0;
353 }
354 int i;
355 for ( i = nextIn - 1; i >= nextOut && id.minDepth < ids[i].minDepth; i-- )
356 {
357 ids[i + 1] = ids[i];
358 }
359 ids[i + 1] = id;
360 nextIn++;
361 }
362
363 ConflictId remove()
364 {
365 return ids[nextOut++];
366 }
367
368 }
369
370 }