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