001package org.eclipse.aether.util.graph.transformer; 002 003/* 004 * Licensed to the Apache Software Foundation (ASF) under one 005 * or more contributor license agreements. See the NOTICE file 006 * distributed with this work for additional information 007 * regarding copyright ownership. The ASF licenses this file 008 * to you under the Apache License, Version 2.0 (the 009 * "License"); you may not use this file except in compliance 010 * with the License. You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, 015 * software distributed under the License is distributed on an 016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 017 * KIND, either express or implied. See the License for the 018 * specific language governing permissions and limitations 019 * under the License. 020 */ 021 022import java.util.ArrayList; 023import java.util.Collection; 024import java.util.Collections; 025import java.util.HashMap; 026import java.util.HashSet; 027import java.util.IdentityHashMap; 028import java.util.LinkedHashMap; 029import java.util.List; 030import java.util.Map; 031 032import org.eclipse.aether.RepositoryException; 033import org.eclipse.aether.collection.DependencyGraphTransformationContext; 034import org.eclipse.aether.collection.DependencyGraphTransformer; 035import org.eclipse.aether.graph.DependencyNode; 036 037/** 038 * A dependency graph transformer that creates a topological sorting of the conflict ids which have been assigned to the 039 * dependency nodes. Conflict ids are sorted according to the dependency relation induced by the dependency graph. This 040 * transformer will query the key {@link TransformationContextKeys#CONFLICT_IDS} in the transformation context for an 041 * existing mapping of nodes to their conflicts ids. In absence of this map, the transformer will automatically invoke 042 * the {@link ConflictMarker} to calculate the conflict ids. When this transformer has executed, the transformation 043 * context holds a {@code List<Object>} that denotes the topologically sorted conflict ids. The list will be stored 044 * using the key {@link TransformationContextKeys#SORTED_CONFLICT_IDS}. In addition, the transformer will store a 045 * {@code Collection<Collection<Object>>} using the key {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} that 046 * describes cycles among conflict ids. 047 */ 048public final class ConflictIdSorter 049 implements DependencyGraphTransformer 050{ 051 052 public DependencyNode transformGraph( DependencyNode node, DependencyGraphTransformationContext context ) 053 throws RepositoryException 054 { 055 Map<?, ?> conflictIds = (Map<?, ?>) context.get( TransformationContextKeys.CONFLICT_IDS ); 056 if ( conflictIds == null ) 057 { 058 ConflictMarker marker = new ConflictMarker(); 059 marker.transformGraph( node, context ); 060 061 conflictIds = (Map<?, ?>) context.get( TransformationContextKeys.CONFLICT_IDS ); 062 } 063 064 @SuppressWarnings( "unchecked" ) 065 Map<String, Object> stats = (Map<String, Object>) context.get( TransformationContextKeys.STATS ); 066 long time1 = System.nanoTime(); 067 068 Map<Object, ConflictId> ids = new LinkedHashMap<Object, ConflictId>( 256 ); 069 070 { 071 ConflictId id = null; 072 Object key = conflictIds.get( node ); 073 if ( key != null ) 074 { 075 id = new ConflictId( key, 0 ); 076 ids.put( key, id ); 077 } 078 079 Map<DependencyNode, Object> visited = new IdentityHashMap<DependencyNode, Object>( conflictIds.size() ); 080 081 buildConflitIdDAG( ids, node, id, 0, visited, conflictIds ); 082 } 083 084 long time2 = System.nanoTime(); 085 086 int cycles = topsortConflictIds( ids.values(), context ); 087 088 if ( stats != null ) 089 { 090 long time3 = System.nanoTime(); 091 stats.put( "ConflictIdSorter.graphTime", time2 - time1 ); 092 stats.put( "ConflictIdSorter.topsortTime", time3 - time2 ); 093 stats.put( "ConflictIdSorter.conflictIdCount", ids.size() ); 094 stats.put( "ConflictIdSorter.conflictIdCycleCount", cycles ); 095 } 096 097 return node; 098 } 099 100 private void buildConflitIdDAG( Map<Object, ConflictId> ids, DependencyNode node, ConflictId id, int depth, 101 Map<DependencyNode, Object> visited, Map<?, ?> conflictIds ) 102 { 103 if ( visited.put( node, Boolean.TRUE ) != null ) 104 { 105 return; 106 } 107 108 depth++; 109 110 for ( DependencyNode child : node.getChildren() ) 111 { 112 Object key = conflictIds.get( child ); 113 ConflictId childId = ids.get( key ); 114 if ( childId == null ) 115 { 116 childId = new ConflictId( key, depth ); 117 ids.put( key, childId ); 118 } 119 else 120 { 121 childId.pullup( depth ); 122 } 123 124 if ( id != null ) 125 { 126 id.add( childId ); 127 } 128 129 buildConflitIdDAG( ids, child, childId, depth, visited, conflictIds ); 130 } 131 } 132 133 private int topsortConflictIds( Collection<ConflictId> conflictIds, DependencyGraphTransformationContext context ) 134 { 135 List<Object> sorted = new ArrayList<Object>( conflictIds.size() ); 136 137 RootQueue roots = new RootQueue( conflictIds.size() / 2 ); 138 for ( ConflictId id : conflictIds ) 139 { 140 if ( id.inDegree <= 0 ) 141 { 142 roots.add( id ); 143 } 144 } 145 146 processRoots( sorted, roots ); 147 148 boolean cycle = sorted.size() < conflictIds.size(); 149 150 while ( sorted.size() < conflictIds.size() ) 151 { 152 // cycle -> deal gracefully with nodes still having positive in-degree 153 154 ConflictId nearest = null; 155 for ( ConflictId id : conflictIds ) 156 { 157 if ( id.inDegree <= 0 ) 158 { 159 continue; 160 } 161 if ( nearest == null || id.minDepth < nearest.minDepth 162 || ( id.minDepth == nearest.minDepth && id.inDegree < nearest.inDegree ) ) 163 { 164 nearest = id; 165 } 166 } 167 168 nearest.inDegree = 0; 169 roots.add( nearest ); 170 171 processRoots( sorted, roots ); 172 } 173 174 Collection<Collection<Object>> cycles = Collections.emptySet(); 175 if ( cycle ) 176 { 177 cycles = findCycles( conflictIds ); 178 } 179 180 context.put( TransformationContextKeys.SORTED_CONFLICT_IDS, sorted ); 181 context.put( TransformationContextKeys.CYCLIC_CONFLICT_IDS, cycles ); 182 183 return cycles.size(); 184 } 185 186 private void processRoots( List<Object> sorted, RootQueue roots ) 187 { 188 while ( !roots.isEmpty() ) 189 { 190 ConflictId root = roots.remove(); 191 192 sorted.add( root.key ); 193 194 for ( ConflictId child : root.children ) 195 { 196 child.inDegree--; 197 if ( child.inDegree == 0 ) 198 { 199 roots.add( child ); 200 } 201 } 202 } 203 } 204 205 private Collection<Collection<Object>> findCycles( Collection<ConflictId> conflictIds ) 206 { 207 Collection<Collection<Object>> cycles = new HashSet<Collection<Object>>(); 208 209 Map<Object, Integer> stack = new HashMap<Object, Integer>( 128 ); 210 Map<ConflictId, Object> visited = new IdentityHashMap<ConflictId, Object>( conflictIds.size() ); 211 for ( ConflictId id : conflictIds ) 212 { 213 findCycles( id, visited, stack, cycles ); 214 } 215 216 return cycles; 217 } 218 219 private void findCycles( ConflictId id, Map<ConflictId, Object> visited, Map<Object, Integer> stack, 220 Collection<Collection<Object>> cycles ) 221 { 222 Integer depth = stack.put( id.key, stack.size() ); 223 if ( depth != null ) 224 { 225 stack.put( id.key, depth ); 226 Collection<Object> cycle = new HashSet<Object>(); 227 for ( Map.Entry<Object, Integer> entry : stack.entrySet() ) 228 { 229 if ( entry.getValue() >= depth ) 230 { 231 cycle.add( entry.getKey() ); 232 } 233 } 234 cycles.add( cycle ); 235 } 236 else 237 { 238 if ( visited.put( id, Boolean.TRUE ) == null ) 239 { 240 for ( ConflictId childId : id.children ) 241 { 242 findCycles( childId, visited, stack, cycles ); 243 } 244 } 245 stack.remove( id.key ); 246 } 247 } 248 249 static final class ConflictId 250 { 251 252 final Object key; 253 254 Collection<ConflictId> children = Collections.emptySet(); 255 256 int inDegree; 257 258 int minDepth; 259 260 ConflictId( Object key, int depth ) 261 { 262 this.key = key; 263 this.minDepth = depth; 264 } 265 266 public void add( ConflictId child ) 267 { 268 if ( children.isEmpty() ) 269 { 270 children = new HashSet<ConflictId>(); 271 } 272 if ( children.add( child ) ) 273 { 274 child.inDegree++; 275 } 276 } 277 278 public void pullup( int depth ) 279 { 280 if ( depth < minDepth ) 281 { 282 minDepth = depth; 283 depth++; 284 for ( ConflictId child : children ) 285 { 286 child.pullup( depth ); 287 } 288 } 289 } 290 291 @Override 292 public boolean equals( Object obj ) 293 { 294 if ( this == obj ) 295 { 296 return true; 297 } 298 else if ( !( obj instanceof ConflictId ) ) 299 { 300 return false; 301 } 302 ConflictId that = (ConflictId) obj; 303 return this.key.equals( that.key ); 304 } 305 306 @Override 307 public int hashCode() 308 { 309 return key.hashCode(); 310 } 311 312 @Override 313 public String toString() 314 { 315 return key + " @ " + minDepth + " <" + inDegree; 316 } 317 318 } 319 320 static final class RootQueue 321 { 322 323 private int nextOut; 324 325 private int nextIn; 326 327 private ConflictId[] ids; 328 329 RootQueue( int capacity ) 330 { 331 ids = new ConflictId[capacity + 16]; 332 } 333 334 boolean isEmpty() 335 { 336 return nextOut >= nextIn; 337 } 338 339 void add( ConflictId id ) 340 { 341 if ( nextOut >= nextIn && nextOut > 0 ) 342 { 343 nextIn -= nextOut; 344 nextOut = 0; 345 } 346 if ( nextIn >= ids.length ) 347 { 348 ConflictId[] tmp = new ConflictId[ids.length + ids.length / 2 + 16]; 349 System.arraycopy( ids, nextOut, tmp, 0, nextIn - nextOut ); 350 ids = tmp; 351 nextIn -= nextOut; 352 nextOut = 0; 353 } 354 int i; 355 for ( i = nextIn - 1; i >= nextOut && id.minDepth < ids[i].minDepth; i-- ) 356 { 357 ids[i + 1] = ids[i]; 358 } 359 ids[i + 1] = id; 360 nextIn++; 361 } 362 363 ConflictId remove() 364 { 365 return ids[nextOut++]; 366 } 367 368 } 369 370}