001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *   http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing,
013 * software distributed under the License is distributed on an
014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 * KIND, either express or implied.  See the License for the
016 * specific language governing permissions and limitations
017 * under the License.
018 */
019package org.eclipse.aether.util.graph.transformer;
020
021import java.util.Collection;
022import java.util.Collections;
023import java.util.HashMap;
024import java.util.HashSet;
025import java.util.IdentityHashMap;
026import java.util.Map;
027import java.util.Set;
028
029import org.eclipse.aether.RepositoryException;
030import org.eclipse.aether.artifact.Artifact;
031import org.eclipse.aether.collection.DependencyGraphTransformationContext;
032import org.eclipse.aether.collection.DependencyGraphTransformer;
033import org.eclipse.aether.graph.Dependency;
034import org.eclipse.aether.graph.DependencyNode;
035
036import static java.util.Objects.requireNonNull;
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 implements DependencyGraphTransformer {
045
046    /**
047     * After the execution of this method, every DependencyNode with an attached dependency is member of one conflict
048     * group.
049     *
050     * @see DependencyGraphTransformer#transformGraph(DependencyNode, DependencyGraphTransformationContext)
051     */
052    public DependencyNode transformGraph(DependencyNode node, DependencyGraphTransformationContext context)
053            throws RepositoryException {
054        requireNonNull(node, "node cannot be null");
055        requireNonNull(context, "context cannot be null");
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            long time3 = System.nanoTime();
073            stats.put("ConflictMarker.analyzeTime", time2 - time1);
074            stats.put("ConflictMarker.markTime", time3 - time2);
075            stats.put("ConflictMarker.nodeCount", nodes.size());
076        }
077
078        return node;
079    }
080
081    private void analyze(
082            DependencyNode node, Map<DependencyNode, Object> nodes, Map<Object, ConflictGroup> groups, int[] counter) {
083        if (nodes.put(node, Boolean.TRUE) != null) {
084            return;
085        }
086
087        Set<Object> keys = getKeys(node);
088        if (!keys.isEmpty()) {
089            ConflictGroup group = null;
090            boolean fixMappings = false;
091
092            for (Object key : keys) {
093                ConflictGroup g = groups.get(key);
094
095                if (group != g) {
096                    if (group == null) {
097                        Set<Object> newKeys = merge(g.keys, keys);
098                        if (newKeys == g.keys) {
099                            group = g;
100                            break;
101                        } else {
102                            group = new ConflictGroup(newKeys, counter[0]++);
103                            fixMappings = true;
104                        }
105                    } else if (g == null) {
106                        fixMappings = true;
107                    } else {
108                        Set<Object> newKeys = merge(g.keys, group.keys);
109                        if (newKeys == g.keys) {
110                            group = g;
111                            fixMappings = false;
112                            break;
113                        } else if (newKeys != group.keys) {
114                            group = new ConflictGroup(newKeys, counter[0]++);
115                            fixMappings = true;
116                        }
117                    }
118                }
119            }
120
121            if (group == null) {
122                group = new ConflictGroup(keys, counter[0]++);
123                fixMappings = true;
124            }
125            if (fixMappings) {
126                for (Object key : group.keys) {
127                    groups.put(key, group);
128                }
129            }
130        }
131
132        for (DependencyNode child : node.getChildren()) {
133            analyze(child, nodes, groups, counter);
134        }
135    }
136
137    private Set<Object> merge(Set<Object> keys1, Set<Object> keys2) {
138        int size1 = keys1.size();
139        int size2 = keys2.size();
140
141        if (size1 < size2) {
142            if (keys2.containsAll(keys1)) {
143                return keys2;
144            }
145        } else {
146            if (keys1.containsAll(keys2)) {
147                return keys1;
148            }
149        }
150
151        Set<Object> keys = new HashSet<>();
152        keys.addAll(keys1);
153        keys.addAll(keys2);
154        return keys;
155    }
156
157    private Set<Object> getKeys(DependencyNode node) {
158        Set<Object> keys;
159
160        Dependency dependency = node.getDependency();
161
162        if (dependency == null) {
163            keys = Collections.emptySet();
164        } else {
165            Object key = toKey(dependency.getArtifact());
166
167            if (node.getRelocations().isEmpty() && node.getAliases().isEmpty()) {
168                keys = Collections.singleton(key);
169            } else {
170                keys = new HashSet<>();
171                keys.add(key);
172
173                for (Artifact relocation : node.getRelocations()) {
174                    key = toKey(relocation);
175                    keys.add(key);
176                }
177
178                for (Artifact alias : node.getAliases()) {
179                    key = toKey(alias);
180                    keys.add(key);
181                }
182            }
183        }
184
185        return keys;
186    }
187
188    private Map<DependencyNode, Object> mark(Collection<DependencyNode> nodes, Map<Object, ConflictGroup> groups) {
189        Map<DependencyNode, Object> conflictIds = new IdentityHashMap<>(nodes.size() + 1);
190
191        for (DependencyNode node : nodes) {
192            Dependency dependency = node.getDependency();
193            if (dependency != null) {
194                Object key = toKey(dependency.getArtifact());
195                conflictIds.put(node, groups.get(key).index);
196            }
197        }
198
199        return conflictIds;
200    }
201
202    private static Object toKey(Artifact artifact) {
203        return new Key(artifact);
204    }
205
206    static class ConflictGroup {
207
208        final Set<Object> keys;
209
210        final int index;
211
212        ConflictGroup(Set<Object> keys, int index) {
213            this.keys = keys;
214            this.index = index;
215        }
216
217        @Override
218        public String toString() {
219            return String.valueOf(keys);
220        }
221    }
222
223    static class Key {
224
225        private final Artifact artifact;
226
227        Key(Artifact artifact) {
228            this.artifact = artifact;
229        }
230
231        @Override
232        public boolean equals(Object obj) {
233            if (obj == this) {
234                return true;
235            } else if (!(obj instanceof Key)) {
236                return false;
237            }
238            Key that = (Key) obj;
239            return artifact.getArtifactId().equals(that.artifact.getArtifactId())
240                    && artifact.getGroupId().equals(that.artifact.getGroupId())
241                    && artifact.getExtension().equals(that.artifact.getExtension())
242                    && artifact.getClassifier().equals(that.artifact.getClassifier());
243        }
244
245        @Override
246        public int hashCode() {
247            int hash = 17;
248            hash = hash * 31 + artifact.getArtifactId().hashCode();
249            hash = hash * 31 + artifact.getGroupId().hashCode();
250            hash = hash * 31 + artifact.getClassifier().hashCode();
251            hash = hash * 31 + artifact.getExtension().hashCode();
252            return hash;
253        }
254
255        @Override
256        public String toString() {
257            return artifact.getGroupId()
258                    + ':'
259                    + artifact.getArtifactId()
260                    + ':'
261                    + artifact.getClassifier()
262                    + ':'
263                    + artifact.getExtension();
264        }
265    }
266}