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