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