1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.eclipse.aether.util.graph.transformer;
20
21 import java.util.ArrayList;
22 import java.util.Collection;
23 import java.util.Collections;
24 import java.util.HashMap;
25 import java.util.HashSet;
26 import java.util.IdentityHashMap;
27 import java.util.LinkedHashMap;
28 import java.util.List;
29 import java.util.Map;
30
31 import org.eclipse.aether.RepositoryException;
32 import org.eclipse.aether.collection.DependencyGraphTransformationContext;
33 import org.eclipse.aether.collection.DependencyGraphTransformer;
34 import org.eclipse.aether.graph.DependencyNode;
35
36 import static java.util.Objects.requireNonNull;
37
38
39
40
41
42
43
44
45
46
47
48
49 public final class ConflictIdSorter implements DependencyGraphTransformer {
50
51 @Override
52 public DependencyNode transformGraph(DependencyNode node, DependencyGraphTransformationContext context)
53 throws RepositoryException {
54 requireNonNull(node, "node cannot be null");
55 requireNonNull(context, "context cannot be null");
56 Map<?, ?> conflictIds = (Map<?, ?>) context.get(TransformationContextKeys.CONFLICT_IDS);
57 if (conflictIds == null) {
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 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 long time2 = System.nanoTime();
82
83 int cycles = topsortConflictIds(ids.values(), context);
84
85 if (stats != null) {
86 long time3 = System.nanoTime();
87 stats.put("ConflictIdSorter.graphTime", time2 - time1);
88 stats.put("ConflictIdSorter.topsortTime", time3 - time2);
89 stats.put("ConflictIdSorter.conflictIdCount", ids.size());
90 stats.put("ConflictIdSorter.conflictIdCycleCount", cycles);
91 }
92
93 return node;
94 }
95
96 private void buildConflitIdDAG(
97 Map<Object, ConflictId> ids,
98 DependencyNode node,
99 ConflictId id,
100 int depth,
101 Map<DependencyNode, Object> visited,
102 Map<?, ?> conflictIds) {
103 if (visited.put(node, Boolean.TRUE) != null) {
104 return;
105 }
106
107 depth++;
108
109 for (DependencyNode child : node.getChildren()) {
110 Object key = conflictIds.get(child);
111 ConflictId childId = ids.get(key);
112 if (childId == null) {
113 childId = new ConflictId(key, depth);
114 ids.put(key, childId);
115 } else {
116 childId.pullup(depth);
117 }
118
119 if (id != null) {
120 id.add(childId);
121 }
122
123 buildConflitIdDAG(ids, child, childId, depth, visited, conflictIds);
124 }
125 }
126
127 private int topsortConflictIds(Collection<ConflictId> conflictIds, DependencyGraphTransformationContext context) {
128 List<Object> sorted = new ArrayList<>(conflictIds.size());
129
130 RootQueue roots = new RootQueue(conflictIds.size() / 2);
131 for (ConflictId id : conflictIds) {
132 if (id.inDegree <= 0) {
133 roots.add(id);
134 }
135 }
136
137 processRoots(sorted, roots);
138
139 boolean cycle = sorted.size() < conflictIds.size();
140
141 while (sorted.size() < conflictIds.size()) {
142
143
144 ConflictId nearest = null;
145 for (ConflictId id : conflictIds) {
146 if (id.inDegree <= 0) {
147 continue;
148 }
149 if (nearest == null
150 || id.minDepth < nearest.minDepth
151 || (id.minDepth == nearest.minDepth && id.inDegree < nearest.inDegree)) {
152 nearest = id;
153 }
154 }
155
156 nearest.inDegree = 0;
157 roots.add(nearest);
158
159 processRoots(sorted, roots);
160 }
161
162 Collection<Collection<Object>> cycles = Collections.emptySet();
163 if (cycle) {
164 cycles = findCycles(conflictIds);
165 }
166
167 context.put(TransformationContextKeys.SORTED_CONFLICT_IDS, sorted);
168 context.put(TransformationContextKeys.CYCLIC_CONFLICT_IDS, cycles);
169
170 return cycles.size();
171 }
172
173 private void processRoots(List<Object> sorted, RootQueue roots) {
174 while (!roots.isEmpty()) {
175 ConflictId root = roots.remove();
176
177 sorted.add(root.key);
178
179 for (ConflictId child : root.children) {
180 child.inDegree--;
181 if (child.inDegree == 0) {
182 roots.add(child);
183 }
184 }
185 }
186 }
187
188 private Collection<Collection<Object>> findCycles(Collection<ConflictId> conflictIds) {
189 Collection<Collection<Object>> cycles = new HashSet<>();
190
191 Map<Object, Integer> stack = new HashMap<>(128);
192 Map<ConflictId, Object> visited = new IdentityHashMap<>(conflictIds.size());
193 for (ConflictId id : conflictIds) {
194 findCycles(id, visited, stack, cycles);
195 }
196
197 return cycles;
198 }
199
200 private void findCycles(
201 ConflictId id,
202 Map<ConflictId, Object> visited,
203 Map<Object, Integer> stack,
204 Collection<Collection<Object>> cycles) {
205 Integer depth = stack.put(id.key, stack.size());
206 if (depth != null) {
207 stack.put(id.key, depth);
208 Collection<Object> cycle = new HashSet<>();
209 for (Map.Entry<Object, Integer> entry : stack.entrySet()) {
210 if (entry.getValue() >= depth) {
211 cycle.add(entry.getKey());
212 }
213 }
214 cycles.add(cycle);
215 } else {
216 if (visited.put(id, Boolean.TRUE) == null) {
217 for (ConflictId childId : id.children) {
218 findCycles(childId, visited, stack, cycles);
219 }
220 }
221 stack.remove(id.key);
222 }
223 }
224
225 static final class ConflictId {
226
227 final Object key;
228
229 Collection<ConflictId> children = Collections.emptySet();
230
231 int inDegree;
232
233 int minDepth;
234
235 ConflictId(Object key, int depth) {
236 this.key = key;
237 this.minDepth = depth;
238 }
239
240 public void add(ConflictId child) {
241 if (children.isEmpty()) {
242 children = new HashSet<>();
243 }
244 if (children.add(child)) {
245 child.inDegree++;
246 }
247 }
248
249 public void pullup(int depth) {
250 if (depth < minDepth) {
251 minDepth = depth;
252 depth++;
253 for (ConflictId child : children) {
254 child.pullup(depth);
255 }
256 }
257 }
258
259 @Override
260 public boolean equals(Object obj) {
261 if (this == obj) {
262 return true;
263 } else if (!(obj instanceof ConflictId)) {
264 return false;
265 }
266 ConflictId that = (ConflictId) obj;
267 return this.key.equals(that.key);
268 }
269
270 @Override
271 public int hashCode() {
272 return key.hashCode();
273 }
274
275 @Override
276 public String toString() {
277 return key + " @ " + minDepth + " <" + inDegree;
278 }
279 }
280
281 static final class RootQueue {
282
283 private int nextOut;
284
285 private int nextIn;
286
287 private ConflictId[] ids;
288
289 RootQueue(int capacity) {
290 ids = new ConflictId[capacity + 16];
291 }
292
293 boolean isEmpty() {
294 return nextOut >= nextIn;
295 }
296
297 void add(ConflictId id) {
298 if (nextOut >= nextIn && nextOut > 0) {
299 nextIn -= nextOut;
300 nextOut = 0;
301 }
302 if (nextIn >= ids.length) {
303 ConflictId[] tmp = new ConflictId[ids.length + ids.length / 2 + 16];
304 System.arraycopy(ids, nextOut, tmp, 0, nextIn - nextOut);
305 ids = tmp;
306 nextIn -= nextOut;
307 nextOut = 0;
308 }
309 int i;
310 for (i = nextIn - 1; i >= nextOut && id.minDepth < ids[i].minDepth; i--) {
311 ids[i + 1] = ids[i];
312 }
313 ids[i + 1] = id;
314 nextIn++;
315 }
316
317 ConflictId remove() {
318 return ids[nextOut++];
319 }
320 }
321 }