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.Collection; 023import java.util.Collections; 024import java.util.HashMap; 025import java.util.HashSet; 026import java.util.IdentityHashMap; 027import java.util.Map; 028import java.util.Set; 029import static java.util.Objects.requireNonNull; 030 031import org.eclipse.aether.RepositoryException; 032import org.eclipse.aether.artifact.Artifact; 033import org.eclipse.aether.collection.DependencyGraphTransformationContext; 034import org.eclipse.aether.collection.DependencyGraphTransformer; 035import org.eclipse.aether.graph.Dependency; 036import org.eclipse.aether.graph.DependencyNode; 037 038/** 039 * A dependency graph transformer that identifies conflicting dependencies. When this transformer has executed, the 040 * transformation context holds a {@code Map<DependencyNode, Object>} where dependency nodes that belong to the same 041 * conflict group will have an equal conflict identifier. This map is stored using the key 042 * {@link TransformationContextKeys#CONFLICT_IDS}. 043 */ 044public final class ConflictMarker 045 implements DependencyGraphTransformer 046{ 047 048 /** 049 * After the execution of this method, every DependencyNode with an attached dependency is member of one conflict 050 * group. 051 * 052 * @see DependencyGraphTransformer#transformGraph(DependencyNode, DependencyGraphTransformationContext) 053 */ 054 public DependencyNode transformGraph( DependencyNode node, DependencyGraphTransformationContext context ) 055 throws RepositoryException 056 { 057 requireNonNull( node, "node cannot be null" ); 058 requireNonNull( context, "context cannot be null" ); 059 @SuppressWarnings( "unchecked" ) 060 Map<String, Object> stats = (Map<String, Object>) context.get( TransformationContextKeys.STATS ); 061 long time1 = System.nanoTime(); 062 063 Map<DependencyNode, Object> nodes = new IdentityHashMap<>( 1024 ); 064 Map<Object, ConflictGroup> groups = new HashMap<>( 1024 ); 065 066 analyze( node, nodes, groups, new int[] { 0 } ); 067 068 long time2 = System.nanoTime(); 069 070 Map<DependencyNode, Object> conflictIds = mark( nodes.keySet(), groups ); 071 072 context.put( TransformationContextKeys.CONFLICT_IDS, conflictIds ); 073 074 if ( stats != null ) 075 { 076 long time3 = System.nanoTime(); 077 stats.put( "ConflictMarker.analyzeTime", time2 - time1 ); 078 stats.put( "ConflictMarker.markTime", time3 - time2 ); 079 stats.put( "ConflictMarker.nodeCount", nodes.size() ); 080 } 081 082 return node; 083 } 084 085 private void analyze( DependencyNode node, Map<DependencyNode, Object> nodes, Map<Object, ConflictGroup> groups, 086 int[] counter ) 087 { 088 if ( nodes.put( node, Boolean.TRUE ) != null ) 089 { 090 return; 091 } 092 093 Set<Object> keys = getKeys( node ); 094 if ( !keys.isEmpty() ) 095 { 096 ConflictGroup group = null; 097 boolean fixMappings = false; 098 099 for ( Object key : keys ) 100 { 101 ConflictGroup g = groups.get( key ); 102 103 if ( group != g ) 104 { 105 if ( group == null ) 106 { 107 Set<Object> newKeys = merge( g.keys, keys ); 108 if ( newKeys == g.keys ) 109 { 110 group = g; 111 break; 112 } 113 else 114 { 115 group = new ConflictGroup( newKeys, counter[0]++ ); 116 fixMappings = true; 117 } 118 } 119 else if ( g == null ) 120 { 121 fixMappings = true; 122 } 123 else 124 { 125 Set<Object> newKeys = merge( g.keys, group.keys ); 126 if ( newKeys == g.keys ) 127 { 128 group = g; 129 fixMappings = false; 130 break; 131 } 132 else if ( newKeys != group.keys ) 133 { 134 group = new ConflictGroup( newKeys, counter[0]++ ); 135 fixMappings = true; 136 } 137 } 138 } 139 } 140 141 if ( group == null ) 142 { 143 group = new ConflictGroup( keys, counter[0]++ ); 144 fixMappings = true; 145 } 146 if ( fixMappings ) 147 { 148 for ( Object key : group.keys ) 149 { 150 groups.put( key, group ); 151 } 152 } 153 } 154 155 for ( DependencyNode child : node.getChildren() ) 156 { 157 analyze( child, nodes, groups, counter ); 158 } 159 } 160 161 private Set<Object> merge( Set<Object> keys1, Set<Object> keys2 ) 162 { 163 int size1 = keys1.size(); 164 int size2 = keys2.size(); 165 166 if ( size1 < size2 ) 167 { 168 if ( keys2.containsAll( keys1 ) ) 169 { 170 return keys2; 171 } 172 } 173 else 174 { 175 if ( keys1.containsAll( keys2 ) ) 176 { 177 return keys1; 178 } 179 } 180 181 Set<Object> keys = new HashSet<>(); 182 keys.addAll( keys1 ); 183 keys.addAll( keys2 ); 184 return keys; 185 } 186 187 private Set<Object> getKeys( DependencyNode node ) 188 { 189 Set<Object> keys; 190 191 Dependency dependency = node.getDependency(); 192 193 if ( dependency == null ) 194 { 195 keys = Collections.emptySet(); 196 } 197 else 198 { 199 Object key = toKey( dependency.getArtifact() ); 200 201 if ( node.getRelocations().isEmpty() && node.getAliases().isEmpty() ) 202 { 203 keys = Collections.singleton( key ); 204 } 205 else 206 { 207 keys = new HashSet<>(); 208 keys.add( key ); 209 210 for ( Artifact relocation : node.getRelocations() ) 211 { 212 key = toKey( relocation ); 213 keys.add( key ); 214 } 215 216 for ( Artifact alias : node.getAliases() ) 217 { 218 key = toKey( alias ); 219 keys.add( key ); 220 } 221 } 222 } 223 224 return keys; 225 } 226 227 private Map<DependencyNode, Object> mark( Collection<DependencyNode> nodes, Map<Object, ConflictGroup> groups ) 228 { 229 Map<DependencyNode, Object> conflictIds = new IdentityHashMap<>( nodes.size() + 1 ); 230 231 for ( DependencyNode node : nodes ) 232 { 233 Dependency dependency = node.getDependency(); 234 if ( dependency != null ) 235 { 236 Object key = toKey( dependency.getArtifact() ); 237 conflictIds.put( node, groups.get( key ).index ); 238 } 239 } 240 241 return conflictIds; 242 } 243 244 private static Object toKey( Artifact artifact ) 245 { 246 return new Key( artifact ); 247 } 248 249 static class ConflictGroup 250 { 251 252 final Set<Object> keys; 253 254 final int index; 255 256 ConflictGroup( Set<Object> keys, int index ) 257 { 258 this.keys = keys; 259 this.index = index; 260 } 261 262 @Override 263 public String toString() 264 { 265 return String.valueOf( keys ); 266 } 267 268 } 269 270 static class Key 271 { 272 273 private final Artifact artifact; 274 275 Key( Artifact artifact ) 276 { 277 this.artifact = artifact; 278 } 279 280 @Override 281 public boolean equals( Object obj ) 282 { 283 if ( obj == this ) 284 { 285 return true; 286 } 287 else if ( !( obj instanceof Key ) ) 288 { 289 return false; 290 } 291 Key that = (Key) obj; 292 return artifact.getArtifactId().equals( that.artifact.getArtifactId() ) 293 && artifact.getGroupId().equals( that.artifact.getGroupId() ) 294 && artifact.getExtension().equals( that.artifact.getExtension() ) 295 && artifact.getClassifier().equals( that.artifact.getClassifier() ); 296 } 297 298 @Override 299 public int hashCode() 300 { 301 int hash = 17; 302 hash = hash * 31 + artifact.getArtifactId().hashCode(); 303 hash = hash * 31 + artifact.getGroupId().hashCode(); 304 hash = hash * 31 + artifact.getClassifier().hashCode(); 305 hash = hash * 31 + artifact.getExtension().hashCode(); 306 return hash; 307 } 308 309 @Override 310 public String toString() 311 { 312 return artifact.getGroupId() + ':' + artifact.getArtifactId() + ':' + artifact.getClassifier() + ':' 313 + artifact.getExtension(); 314 } 315 316 } 317 318}