001package org.apache.maven.project;
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.Iterator;
027import java.util.List;
028import java.util.Map;
029
030import org.apache.maven.artifact.ArtifactUtils;
031import org.apache.maven.model.Dependency;
032import org.apache.maven.model.Extension;
033import org.apache.maven.model.Parent;
034import org.apache.maven.model.Plugin;
035import org.codehaus.plexus.util.StringUtils;
036import org.codehaus.plexus.util.dag.CycleDetectedException;
037import org.codehaus.plexus.util.dag.DAG;
038import org.codehaus.plexus.util.dag.TopologicalSorter;
039import org.codehaus.plexus.util.dag.Vertex;
040
041public class ProjectSorter
042{
043    private DAG dag;
044
045    private List<MavenProject> sortedProjects;
046
047    private Map<String, MavenProject> projectMap;
048
049    private MavenProject topLevelProject;
050
051    /**
052     * Sort a list of projects.
053     * <ul>
054     * <li>collect all the vertices for the projects that we want to build.</li>
055     * <li>iterate through the deps of each project and if that dep is within
056     * the set of projects we want to build then add an edge, otherwise throw
057     * the edge away because that dependency is not within the set of projects
058     * we are trying to build. we assume a closed set.</li>
059     * <li>do a topo sort on the graph that remains.</li>
060     * </ul>
061     * @throws DuplicateProjectException if any projects are duplicated by id
062     */
063    // MAVENAPI FIXME: the DAG used is NOT only used to represent the dependency relation,
064    // but also for <parent>, <build><plugin>, <reports>. We need multiple DAG's
065    // since a DAG can only handle 1 type of relationship properly.
066    // Usecase:  This is detected as a cycle:
067    // org.apache.maven:maven-plugin-api                -(PARENT)->
068    // org.apache.maven:maven                           -(inherited REPORTING)->
069    // org.apache.maven.plugins:maven-checkstyle-plugin -(DEPENDENCY)->
070    // org.apache.maven:maven-plugin-api
071    // In this case, both the verify and the report goals are called
072    // in a different lifecycle. Though the compiler-plugin has a valid usecase, although
073    // that seems to work fine. We need to take versions and lifecycle into account.
074    public ProjectSorter( Collection<MavenProject> projects )
075        throws CycleDetectedException, DuplicateProjectException
076    {
077        dag = new DAG();
078
079        // groupId:artifactId:version -> project
080        projectMap = new HashMap<String, MavenProject>( projects.size() * 2 );
081
082        // groupId:artifactId -> (version -> vertex)
083        Map<String, Map<String, Vertex>> vertexMap = new HashMap<String, Map<String, Vertex>>( projects.size() * 2 );
084
085        for ( MavenProject project : projects )
086        {
087            String projectId = getId( project );
088
089            MavenProject conflictingProject = projectMap.put( projectId, project );
090
091            if ( conflictingProject != null )
092            {
093                throw new DuplicateProjectException( projectId, conflictingProject.getFile(), project.getFile(),
094                                                     "Project '" + projectId + "' is duplicated in the reactor" );
095            }
096
097            String projectKey = ArtifactUtils.versionlessKey( project.getGroupId(), project.getArtifactId() );
098
099            Map<String, Vertex> vertices = vertexMap.get( projectKey );
100            if ( vertices == null )
101            {
102                vertices = new HashMap<String, Vertex>( 2, 1 );
103                vertexMap.put( projectKey, vertices );
104            }
105            vertices.put( project.getVersion(), dag.addVertex( projectId ) );
106        }
107
108        for ( Vertex projectVertex : dag.getVerticies() )
109        {
110            String projectId = projectVertex.getLabel();
111
112            MavenProject project = projectMap.get( projectId );
113
114            for ( Dependency dependency : project.getDependencies() )
115            {
116                addEdge( projectMap, vertexMap, project, projectVertex, dependency.getGroupId(),
117                         dependency.getArtifactId(), dependency.getVersion(), false, false );
118            }
119
120            Parent parent = project.getModel().getParent();
121
122            if ( parent != null )
123            {
124                // Parent is added as an edge, but must not cause a cycle - so we remove any other edges it has
125                // in conflict
126                addEdge( projectMap, vertexMap, null, projectVertex, parent.getGroupId(), parent.getArtifactId(),
127                         parent.getVersion(), true, false );
128            }
129
130            List<Plugin> buildPlugins = project.getBuildPlugins();
131            if ( buildPlugins != null )
132            {
133                for ( Plugin plugin : buildPlugins )
134                {
135                    addEdge( projectMap, vertexMap, project, projectVertex, plugin.getGroupId(),
136                             plugin.getArtifactId(), plugin.getVersion(), false, true );
137
138                    for ( Dependency dependency : plugin.getDependencies() )
139                    {
140                        addEdge( projectMap, vertexMap, project, projectVertex, dependency.getGroupId(),
141                                 dependency.getArtifactId(), dependency.getVersion(), false, true );
142                    }
143                }
144            }
145
146            List<Extension> buildExtensions = project.getBuildExtensions();
147            if ( buildExtensions != null )
148            {
149                for ( Extension extension : buildExtensions )
150                {
151                    addEdge( projectMap, vertexMap, project, projectVertex, extension.getGroupId(),
152                             extension.getArtifactId(), extension.getVersion(), false, true );
153                }
154            }
155        }
156
157        List<MavenProject> sortedProjects = new ArrayList<MavenProject>( projects.size() );
158
159        List<String> sortedProjectLabels = TopologicalSorter.sort( dag );
160
161        for ( String id : sortedProjectLabels )
162        {
163            sortedProjects.add( projectMap.get( id ) );
164        }
165
166        this.sortedProjects = Collections.unmodifiableList( sortedProjects );
167    }
168
169    private void addEdge( Map<String, MavenProject> projectMap, Map<String, Map<String, Vertex>> vertexMap,
170                          MavenProject project, Vertex projectVertex, String groupId, String artifactId,
171                          String version, boolean force, boolean safe )
172        throws CycleDetectedException
173    {
174        String projectKey = ArtifactUtils.versionlessKey( groupId, artifactId );
175
176        Map<String, Vertex> vertices = vertexMap.get( projectKey );
177
178        if ( vertices != null )
179        {
180            if ( isSpecificVersion( version ) )
181            {
182                Vertex vertex = vertices.get( version );
183                if ( vertex != null )
184                {
185                    addEdge( projectVertex, vertex, project, projectMap, force, safe );
186                }
187            }
188            else
189            {
190                for ( Vertex vertex : vertices.values() )
191                {
192                    addEdge( projectVertex, vertex, project, projectMap, force, safe );
193                }
194            }
195        }
196    }
197
198    private void addEdge( Vertex fromVertex, Vertex toVertex, MavenProject fromProject,
199                          Map<String, MavenProject> projectMap, boolean force, boolean safe )
200        throws CycleDetectedException
201    {
202        if ( fromVertex.equals( toVertex ) )
203        {
204            return;
205        }
206
207        if ( fromProject != null )
208        {
209            MavenProject toProject = projectMap.get( toVertex.getLabel() );
210            fromProject.addProjectReference( toProject );
211        }
212
213        if ( force && toVertex.getChildren().contains( fromVertex ) )
214        {
215            dag.removeEdge( toVertex, fromVertex );
216        }
217
218        try
219        {
220            dag.addEdge( fromVertex, toVertex );
221        }
222        catch ( CycleDetectedException e )
223        {
224            if ( !safe )
225            {
226                throw e;
227            }
228        }
229    }
230
231    private boolean isSpecificVersion( String version )
232    {
233        return !( StringUtils.isEmpty( version ) || version.startsWith( "[" ) || version.startsWith( "(" ) );
234    }
235
236    // TODO: !![jc; 28-jul-2005] check this; if we're using '-r' and there are aggregator tasks, this will result in weirdness.
237    public MavenProject getTopLevelProject()
238    {
239        if ( topLevelProject == null )
240        {
241            for ( Iterator<MavenProject> i = sortedProjects.iterator(); i.hasNext() && ( topLevelProject == null ); )
242            {
243                MavenProject project = i.next();
244                if ( project.isExecutionRoot() )
245                {
246                    topLevelProject = project;
247                }
248            }
249        }
250
251        return topLevelProject;
252    }
253
254    public List<MavenProject> getSortedProjects()
255    {
256        return sortedProjects;
257    }
258
259    public boolean hasMultipleProjects()
260    {
261        return sortedProjects.size() > 1;
262    }
263
264    public List<String> getDependents( String id )
265    {
266        return dag.getParentLabels( id );
267    }
268
269    public List<String> getDependencies( String id )
270    {
271        return dag.getChildLabels( id );
272    }
273
274    public static String getId( MavenProject project )
275    {
276        return ArtifactUtils.key( project.getGroupId(), project.getArtifactId(), project.getVersion() );
277    }
278
279    public DAG getDAG()
280    {
281        return dag;
282    }
283
284    public Map<String, MavenProject> getProjectMap()
285    {
286        return projectMap;
287    }
288
289}