001package org.apache.maven.repository.metadata;
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.List;
024import java.util.TreeSet;
025
026import org.apache.maven.artifact.ArtifactScopeEnum;
027import org.codehaus.plexus.component.annotations.Component;
028import org.codehaus.plexus.component.annotations.Requirement;
029
030/**
031 * Default conflict resolver.Implements closer newer first policy by default, but could be configured via plexus
032 *
033 * @author <a href="mailto:oleg@codehaus.org">Oleg Gusakov</a>
034 */
035@Component( role = GraphConflictResolver.class )
036public class DefaultGraphConflictResolver
037    implements GraphConflictResolver
038{
039    /**
040     * artifact, closer to the entry point, is selected
041     */
042    @Requirement( role = GraphConflictResolutionPolicy.class )
043    protected GraphConflictResolutionPolicy policy;
044
045    // -------------------------------------------------------------------------------------
046    // -------------------------------------------------------------------------------------
047    public MetadataGraph resolveConflicts( MetadataGraph graph, ArtifactScopeEnum scope )
048        throws GraphConflictResolutionException
049    {
050        if ( policy == null )
051        {
052            throw new GraphConflictResolutionException( "no GraphConflictResolutionPolicy injected" );
053        }
054
055        if ( graph == null )
056        {
057            return null;
058        }
059
060        final MetadataGraphVertex entry = graph.getEntry();
061        if ( entry == null )
062        {
063            return null;
064        }
065
066        if ( graph.isEmpty() )
067        {
068            throw new GraphConflictResolutionException( "graph with an entry, but not vertices do not exist" );
069        }
070
071        if ( graph.isEmptyEdges() )
072        {
073            return null; // no edges - nothing to worry about
074        }
075
076        final TreeSet<MetadataGraphVertex> vertices = graph.getVertices();
077
078        try
079        {
080            // edge case - single vertex graph
081            if ( vertices.size() == 1 )
082            {
083                return new MetadataGraph( entry );
084            }
085
086            final ArtifactScopeEnum requestedScope = ArtifactScopeEnum.checkScope( scope );
087
088            MetadataGraph res = new MetadataGraph( vertices.size() );
089            res.setVersionedVertices( false );
090            res.setScopedVertices( false );
091
092            MetadataGraphVertex resEntry = res.addVertex( entry.getMd() );
093            res.setEntry( resEntry );
094
095            res.setScope( requestedScope );
096
097            for ( MetadataGraphVertex v : vertices )
098            {
099                final List<MetadataGraphEdge> ins = graph.getIncidentEdges( v );
100                final MetadataGraphEdge edge = cleanEdges( v, ins, requestedScope );
101
102                if ( edge == null )
103                { // no edges - don't need this vertex any more
104                    if ( entry.equals( v ) )
105                    { // unless it's an entry point.
106                        // currently processing the entry point - it should not have any entry incident edges
107                        res.getEntry().getMd().setWhy( "This is a graph entry point. No links." );
108                    }
109                    else
110                    {
111                        // System.out.println("--->"+v.getMd().toDomainString()
112                        // +" has been terminated on this entry set\n-------------------\n"
113                        // +ins
114                        // +"\n-------------------\n"
115                        // );
116                    }
117                }
118                else
119                {
120                    // System.out.println("+++>"+v.getMd().toDomainString()+" still has "+edge.toString() );
121                    // fill in domain md with actual version data
122                    ArtifactMetadata md = v.getMd();
123                    ArtifactMetadata newMd =
124                        new ArtifactMetadata( md.getGroupId(), md.getArtifactId(), edge.getVersion(), md.getType(),
125                                              md.getScopeAsEnum(), md.getClassifier(), edge.getArtifactUri(),
126                                              edge.getSource() == null ? "" : edge.getSource().getMd().toString(),
127                                              edge.isResolved(), edge.getTarget() == null ? null
128                                                              : edge.getTarget().getMd().getError() );
129                    MetadataGraphVertex newV = res.addVertex( newMd );
130                    MetadataGraphVertex sourceV = res.addVertex( edge.getSource().getMd() );
131
132                    res.addEdge( sourceV, newV, edge );
133                }
134            }
135            MetadataGraph linkedRes = findLinkedSubgraph( res );
136            // System.err.println("Original graph("+graph.getVertices().size()+"):\n"+graph.toString());
137            // System.err.println("Cleaned("+requestedScope+") graph("+res.getVertices().size()+"):\n"+res.toString());
138            // System.err.println("Linked("+requestedScope+")
139            // subgraph("+linkedRes.getVertices().size()+"):\n"+linkedRes.toString());
140            return linkedRes;
141        }
142        catch ( MetadataResolutionException e )
143        {
144            throw new GraphConflictResolutionException( e );
145        }
146    }
147
148    // -------------------------------------------------------------------------------------
149    private MetadataGraph findLinkedSubgraph( MetadataGraph g )
150    {
151        if ( g.getVertices().size() == 1 )
152        {
153            return g;
154        }
155
156        List<MetadataGraphVertex> visited = new ArrayList<MetadataGraphVertex>( g.getVertices().size() );
157        visit( g.getEntry(), visited, g );
158
159        List<MetadataGraphVertex> dropList = new ArrayList<MetadataGraphVertex>( g.getVertices().size() );
160
161        // collect drop list
162        for ( MetadataGraphVertex v : g.getVertices() )
163        {
164            if ( !visited.contains( v ) )
165            {
166                dropList.add( v );
167            }
168        }
169
170        if ( dropList.size() < 1 )
171        {
172            return g;
173        }
174
175        // now - drop vertices
176        TreeSet<MetadataGraphVertex> vertices = g.getVertices();
177        for ( MetadataGraphVertex v : dropList )
178        {
179            vertices.remove( v );
180        }
181
182        return g;
183    }
184
185    // -------------------------------------------------------------------------------------
186    private void visit( MetadataGraphVertex from, List<MetadataGraphVertex> visited, MetadataGraph graph )
187    {
188        if ( visited.contains( from ) )
189        {
190            return;
191        }
192
193        visited.add( from );
194
195        List<MetadataGraphEdge> exitList = graph.getExcidentEdges( from );
196        // String s = "|---> "+from.getMd().toString()+" - "+(exitList == null ? -1 : exitList.size()) + " exit links";
197        if ( exitList != null && exitList.size() > 0 )
198        {
199            for ( MetadataGraphEdge e : graph.getExcidentEdges( from ) )
200            {
201                visit( e.getTarget(), visited, graph );
202            }
203        }
204    }
205
206    // -------------------------------------------------------------------------------------
207    private MetadataGraphEdge cleanEdges( MetadataGraphVertex v, List<MetadataGraphEdge> edges,
208                                          ArtifactScopeEnum scope )
209    {
210        if ( edges == null || edges.isEmpty() )
211        {
212            return null;
213        }
214
215        if ( edges.size() == 1 )
216        {
217            MetadataGraphEdge e = edges.get( 0 );
218            if ( scope.encloses( e.getScope() ) )
219            {
220                return e;
221            }
222
223            return null;
224        }
225
226        MetadataGraphEdge res = null;
227
228        for ( MetadataGraphEdge e : edges )
229        {
230            if ( !scope.encloses( e.getScope() ) )
231            {
232                continue;
233            }
234
235            if ( res == null )
236            {
237                res = e;
238            }
239            else
240            {
241                res = policy.apply( e, res );
242            }
243        }
244
245        return res;
246    }
247    // -------------------------------------------------------------------------------------
248    // -------------------------------------------------------------------------------------
249}