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