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