001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 */ 019package org.eclipse.aether.util.graph.transformer; 020 021import java.util.ArrayList; 022import java.util.Collection; 023import java.util.Collections; 024import java.util.HashMap; 025import java.util.HashSet; 026import java.util.IdentityHashMap; 027import java.util.LinkedHashMap; 028import java.util.List; 029import java.util.Map; 030 031import org.eclipse.aether.RepositoryException; 032import org.eclipse.aether.collection.DependencyGraphTransformationContext; 033import org.eclipse.aether.collection.DependencyGraphTransformer; 034import org.eclipse.aether.graph.DependencyNode; 035 036import static java.util.Objects.requireNonNull; 037 038/** 039 * A dependency graph transformer that creates a topological sorting of the conflict ids which have been assigned to the 040 * dependency nodes. Conflict ids are sorted according to the dependency relation induced by the dependency graph. This 041 * transformer will query the key {@link TransformationContextKeys#CONFLICT_IDS} in the transformation context for an 042 * existing mapping of nodes to their conflicts ids. In absence of this map, the transformer will automatically invoke 043 * the {@link ConflictMarker} to calculate the conflict ids. When this transformer has executed, the transformation 044 * context holds a {@code List<Object>} that denotes the topologically sorted conflict ids. The list will be stored 045 * using the key {@link TransformationContextKeys#SORTED_CONFLICT_IDS}. In addition, the transformer will store a 046 * {@code Collection<Collection<Object>>} using the key {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} that 047 * describes cycles among conflict ids. 048 */ 049public final class ConflictIdSorter implements DependencyGraphTransformer { 050 051 public DependencyNode transformGraph(DependencyNode node, DependencyGraphTransformationContext context) 052 throws RepositoryException { 053 requireNonNull(node, "node cannot be null"); 054 requireNonNull(context, "context cannot be null"); 055 Map<?, ?> conflictIds = (Map<?, ?>) context.get(TransformationContextKeys.CONFLICT_IDS); 056 if (conflictIds == null) { 057 ConflictMarker marker = new ConflictMarker(); 058 marker.transformGraph(node, context); 059 060 conflictIds = (Map<?, ?>) context.get(TransformationContextKeys.CONFLICT_IDS); 061 } 062 063 @SuppressWarnings("unchecked") 064 Map<String, Object> stats = (Map<String, Object>) context.get(TransformationContextKeys.STATS); 065 long time1 = System.nanoTime(); 066 067 Map<Object, ConflictId> ids = new LinkedHashMap<>(256); 068 069 ConflictId id = null; 070 Object key = conflictIds.get(node); 071 if (key != null) { 072 id = new ConflictId(key, 0); 073 ids.put(key, id); 074 } 075 076 Map<DependencyNode, Object> visited = new IdentityHashMap<>(conflictIds.size()); 077 078 buildConflitIdDAG(ids, node, id, 0, visited, conflictIds); 079 080 long time2 = System.nanoTime(); 081 082 int cycles = topsortConflictIds(ids.values(), context); 083 084 if (stats != null) { 085 long time3 = System.nanoTime(); 086 stats.put("ConflictIdSorter.graphTime", time2 - time1); 087 stats.put("ConflictIdSorter.topsortTime", time3 - time2); 088 stats.put("ConflictIdSorter.conflictIdCount", ids.size()); 089 stats.put("ConflictIdSorter.conflictIdCycleCount", cycles); 090 } 091 092 return node; 093 } 094 095 private void buildConflitIdDAG( 096 Map<Object, ConflictId> ids, 097 DependencyNode node, 098 ConflictId id, 099 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 // cycle -> deal gracefully with nodes still having positive in-degree 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}