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