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 }