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<>( 256 ); 069 070 ConflictId id = null; 071 Object key = conflictIds.get( node ); 072 if ( key != null ) 073 { 074 id = new ConflictId( key, 0 ); 075 ids.put( key, id ); 076 } 077 078 Map<DependencyNode, Object> visited = new IdentityHashMap<>( conflictIds.size() ); 079 080 buildConflitIdDAG( ids, node, id, 0, visited, conflictIds ); 081 082 long time2 = System.nanoTime(); 083 084 int cycles = topsortConflictIds( ids.values(), context ); 085 086 if ( stats != null ) 087 { 088 long time3 = System.nanoTime(); 089 stats.put( "ConflictIdSorter.graphTime", time2 - time1 ); 090 stats.put( "ConflictIdSorter.topsortTime", time3 - time2 ); 091 stats.put( "ConflictIdSorter.conflictIdCount", ids.size() ); 092 stats.put( "ConflictIdSorter.conflictIdCycleCount", cycles ); 093 } 094 095 return node; 096 } 097 098 private void buildConflitIdDAG( Map<Object, ConflictId> ids, DependencyNode node, ConflictId id, int depth, 099 Map<DependencyNode, Object> visited, Map<?, ?> conflictIds ) 100 { 101 if ( visited.put( node, Boolean.TRUE ) != null ) 102 { 103 return; 104 } 105 106 depth++; 107 108 for ( DependencyNode child : node.getChildren() ) 109 { 110 Object key = conflictIds.get( child ); 111 ConflictId childId = ids.get( key ); 112 if ( childId == null ) 113 { 114 childId = new ConflictId( key, depth ); 115 ids.put( key, childId ); 116 } 117 else 118 { 119 childId.pullup( depth ); 120 } 121 122 if ( id != null ) 123 { 124 id.add( childId ); 125 } 126 127 buildConflitIdDAG( ids, child, childId, depth, visited, conflictIds ); 128 } 129 } 130 131 private int topsortConflictIds( Collection<ConflictId> conflictIds, DependencyGraphTransformationContext context ) 132 { 133 List<Object> sorted = new ArrayList<>( conflictIds.size() ); 134 135 RootQueue roots = new RootQueue( conflictIds.size() / 2 ); 136 for ( ConflictId id : conflictIds ) 137 { 138 if ( id.inDegree <= 0 ) 139 { 140 roots.add( id ); 141 } 142 } 143 144 processRoots( sorted, roots ); 145 146 boolean cycle = sorted.size() < conflictIds.size(); 147 148 while ( sorted.size() < conflictIds.size() ) 149 { 150 // cycle -> deal gracefully with nodes still having positive in-degree 151 152 ConflictId nearest = null; 153 for ( ConflictId id : conflictIds ) 154 { 155 if ( id.inDegree <= 0 ) 156 { 157 continue; 158 } 159 if ( nearest == null || id.minDepth < nearest.minDepth 160 || ( id.minDepth == nearest.minDepth && id.inDegree < nearest.inDegree ) ) 161 { 162 nearest = id; 163 } 164 } 165 166 nearest.inDegree = 0; 167 roots.add( nearest ); 168 169 processRoots( sorted, roots ); 170 } 171 172 Collection<Collection<Object>> cycles = Collections.emptySet(); 173 if ( cycle ) 174 { 175 cycles = findCycles( conflictIds ); 176 } 177 178 context.put( TransformationContextKeys.SORTED_CONFLICT_IDS, sorted ); 179 context.put( TransformationContextKeys.CYCLIC_CONFLICT_IDS, cycles ); 180 181 return cycles.size(); 182 } 183 184 private void processRoots( List<Object> sorted, RootQueue roots ) 185 { 186 while ( !roots.isEmpty() ) 187 { 188 ConflictId root = roots.remove(); 189 190 sorted.add( root.key ); 191 192 for ( ConflictId child : root.children ) 193 { 194 child.inDegree--; 195 if ( child.inDegree == 0 ) 196 { 197 roots.add( child ); 198 } 199 } 200 } 201 } 202 203 private Collection<Collection<Object>> findCycles( Collection<ConflictId> conflictIds ) 204 { 205 Collection<Collection<Object>> cycles = new HashSet<>(); 206 207 Map<Object, Integer> stack = new HashMap<>( 128 ); 208 Map<ConflictId, Object> visited = new IdentityHashMap<>( conflictIds.size() ); 209 for ( ConflictId id : conflictIds ) 210 { 211 findCycles( id, visited, stack, cycles ); 212 } 213 214 return cycles; 215 } 216 217 private void findCycles( ConflictId id, Map<ConflictId, Object> visited, Map<Object, Integer> stack, 218 Collection<Collection<Object>> cycles ) 219 { 220 Integer depth = stack.put( id.key, stack.size() ); 221 if ( depth != null ) 222 { 223 stack.put( id.key, depth ); 224 Collection<Object> cycle = new HashSet<>(); 225 for ( Map.Entry<Object, Integer> entry : stack.entrySet() ) 226 { 227 if ( entry.getValue() >= depth ) 228 { 229 cycle.add( entry.getKey() ); 230 } 231 } 232 cycles.add( cycle ); 233 } 234 else 235 { 236 if ( visited.put( id, Boolean.TRUE ) == null ) 237 { 238 for ( ConflictId childId : id.children ) 239 { 240 findCycles( childId, visited, stack, cycles ); 241 } 242 } 243 stack.remove( id.key ); 244 } 245 } 246 247 static final class ConflictId 248 { 249 250 final Object key; 251 252 Collection<ConflictId> children = Collections.emptySet(); 253 254 int inDegree; 255 256 int minDepth; 257 258 ConflictId( Object key, int depth ) 259 { 260 this.key = key; 261 this.minDepth = depth; 262 } 263 264 public void add( ConflictId child ) 265 { 266 if ( children.isEmpty() ) 267 { 268 children = new HashSet<>(); 269 } 270 if ( children.add( child ) ) 271 { 272 child.inDegree++; 273 } 274 } 275 276 public void pullup( int depth ) 277 { 278 if ( depth < minDepth ) 279 { 280 minDepth = depth; 281 depth++; 282 for ( ConflictId child : children ) 283 { 284 child.pullup( depth ); 285 } 286 } 287 } 288 289 @Override 290 public boolean equals( Object obj ) 291 { 292 if ( this == obj ) 293 { 294 return true; 295 } 296 else if ( !( obj instanceof ConflictId ) ) 297 { 298 return false; 299 } 300 ConflictId that = (ConflictId) obj; 301 return this.key.equals( that.key ); 302 } 303 304 @Override 305 public int hashCode() 306 { 307 return key.hashCode(); 308 } 309 310 @Override 311 public String toString() 312 { 313 return key + " @ " + minDepth + " <" + inDegree; 314 } 315 316 } 317 318 static final class RootQueue 319 { 320 321 private int nextOut; 322 323 private int nextIn; 324 325 private ConflictId[] ids; 326 327 RootQueue( int capacity ) 328 { 329 ids = new ConflictId[capacity + 16]; 330 } 331 332 boolean isEmpty() 333 { 334 return nextOut >= nextIn; 335 } 336 337 void add( ConflictId id ) 338 { 339 if ( nextOut >= nextIn && nextOut > 0 ) 340 { 341 nextIn -= nextOut; 342 nextOut = 0; 343 } 344 if ( nextIn >= ids.length ) 345 { 346 ConflictId[] tmp = new ConflictId[ids.length + ids.length / 2 + 16]; 347 System.arraycopy( ids, nextOut, tmp, 0, nextIn - nextOut ); 348 ids = tmp; 349 nextIn -= nextOut; 350 nextOut = 0; 351 } 352 int i; 353 for ( i = nextIn - 1; i >= nextOut && id.minDepth < ids[i].minDepth; i-- ) 354 { 355 ids[i + 1] = ids[i]; 356 } 357 ids[i + 1] = id; 358 nextIn++; 359 } 360 361 ConflictId remove() 362 { 363 return ids[nextOut++]; 364 } 365 366 } 367 368}