View Javadoc
1   package org.apache.maven.project;
2   
3   /*
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *  http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing,
15   * software distributed under the License is distributed on an
16   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17   * KIND, either express or implied.  See the License for the
18   * specific language governing permissions and limitations
19   * under the License.
20   */
21  
22  import java.util.ArrayList;
23  import java.util.Collection;
24  import java.util.Collections;
25  import java.util.HashMap;
26  import java.util.Iterator;
27  import java.util.List;
28  import java.util.Map;
29  
30  import org.apache.maven.artifact.ArtifactUtils;
31  import org.apache.maven.model.Dependency;
32  import org.apache.maven.model.Extension;
33  import org.apache.maven.model.Parent;
34  import org.apache.maven.model.Plugin;
35  import org.codehaus.plexus.util.StringUtils;
36  import org.codehaus.plexus.util.dag.CycleDetectedException;
37  import org.codehaus.plexus.util.dag.DAG;
38  import org.codehaus.plexus.util.dag.TopologicalSorter;
39  import org.codehaus.plexus.util.dag.Vertex;
40  
41  /**
42   * ProjectSorter
43   */
44  public class ProjectSorter
45  {
46      private DAG dag;
47  
48      private List<MavenProject> sortedProjects;
49  
50      private Map<String, MavenProject> projectMap;
51  
52      private MavenProject topLevelProject;
53  
54      /**
55       * Sort a list of projects.
56       * <ul>
57       * <li>collect all the vertices for the projects that we want to build.</li>
58       * <li>iterate through the deps of each project and if that dep is within
59       * the set of projects we want to build then add an edge, otherwise throw
60       * the edge away because that dependency is not within the set of projects
61       * we are trying to build. we assume a closed set.</li>
62       * <li>do a topo sort on the graph that remains.</li>
63       * </ul>
64       * @throws DuplicateProjectException if any projects are duplicated by id
65       */
66      // MAVENAPI FIXME: the DAG used is NOT only used to represent the dependency relation,
67      // but also for <parent>, <build><plugin>, <reports>. We need multiple DAG's
68      // since a DAG can only handle 1 type of relationship properly.
69      // Usecase:  This is detected as a cycle:
70      // org.apache.maven:maven-plugin-api                -(PARENT)->
71      // org.apache.maven:maven                           -(inherited REPORTING)->
72      // org.apache.maven.plugins:maven-checkstyle-plugin -(DEPENDENCY)->
73      // org.apache.maven:maven-plugin-api
74      // In this case, both the verify and the report goals are called
75      // in a different lifecycle. Though the compiler-plugin has a valid usecase, although
76      // that seems to work fine. We need to take versions and lifecycle into account.
77      public ProjectSorter( Collection<MavenProject> projects )
78          throws CycleDetectedException, DuplicateProjectException
79      {
80          dag = new DAG();
81  
82          // groupId:artifactId:version -> project
83          projectMap = new HashMap<>( projects.size() * 2 );
84  
85          // groupId:artifactId -> (version -> vertex)
86          Map<String, Map<String, Vertex>> vertexMap = new HashMap<>( projects.size() * 2 );
87  
88          for ( MavenProject project : projects )
89          {
90              String projectId = getId( project );
91  
92              MavenProject conflictingProject = projectMap.put( projectId, project );
93  
94              if ( conflictingProject != null )
95              {
96                  throw new DuplicateProjectException( projectId, conflictingProject.getFile(), project.getFile(),
97                                                       "Project '" + projectId + "' is duplicated in the reactor" );
98              }
99  
100             String projectKey = ArtifactUtils.versionlessKey( project.getGroupId(), project.getArtifactId() );
101 
102             Map<String, Vertex> vertices = vertexMap.get( projectKey );
103             if ( vertices == null )
104             {
105                 vertices = new HashMap<>( 2, 1 );
106                 vertexMap.put( projectKey, vertices );
107             }
108             vertices.put( project.getVersion(), dag.addVertex( projectId ) );
109         }
110 
111         for ( Vertex projectVertex : dag.getVertices() )
112         {
113             String projectId = projectVertex.getLabel();
114 
115             MavenProject project = projectMap.get( projectId );
116 
117             for ( Dependency dependency : project.getDependencies() )
118             {
119                 addEdge( projectMap, vertexMap, project, projectVertex, dependency.getGroupId(),
120                          dependency.getArtifactId(), dependency.getVersion(), false, false );
121             }
122 
123             Parent parent = project.getModel().getParent();
124 
125             if ( parent != null )
126             {
127                 // Parent is added as an edge, but must not cause a cycle - so we remove any other edges it has
128                 // in conflict
129                 addEdge( projectMap, vertexMap, null, projectVertex, parent.getGroupId(), parent.getArtifactId(),
130                          parent.getVersion(), true, false );
131             }
132 
133             List<Plugin> buildPlugins = project.getBuildPlugins();
134             if ( buildPlugins != null )
135             {
136                 for ( Plugin plugin : buildPlugins )
137                 {
138                     addEdge( projectMap, vertexMap, project, projectVertex, plugin.getGroupId(),
139                              plugin.getArtifactId(), plugin.getVersion(), false, true );
140 
141                     for ( Dependency dependency : plugin.getDependencies() )
142                     {
143                         addEdge( projectMap, vertexMap, project, projectVertex, dependency.getGroupId(),
144                                  dependency.getArtifactId(), dependency.getVersion(), false, true );
145                     }
146                 }
147             }
148 
149             List<Extension> buildExtensions = project.getBuildExtensions();
150             if ( buildExtensions != null )
151             {
152                 for ( Extension extension : buildExtensions )
153                 {
154                     addEdge( projectMap, vertexMap, project, projectVertex, extension.getGroupId(),
155                              extension.getArtifactId(), extension.getVersion(), false, true );
156                 }
157             }
158         }
159 
160         List<MavenProject> sortedProjects = new ArrayList<>( projects.size() );
161 
162         List<String> sortedProjectLabels = TopologicalSorter.sort( dag );
163 
164         for ( String id : sortedProjectLabels )
165         {
166             sortedProjects.add( projectMap.get( id ) );
167         }
168 
169         this.sortedProjects = Collections.unmodifiableList( sortedProjects );
170     }
171     @SuppressWarnings( "checkstyle:parameternumber" )
172     private void addEdge( Map<String, MavenProject> projectMap, Map<String, Map<String, Vertex>> vertexMap,
173                           MavenProject project, Vertex projectVertex, String groupId, String artifactId,
174                           String version, boolean force, boolean safe )
175         throws CycleDetectedException
176     {
177         String projectKey = ArtifactUtils.versionlessKey( groupId, artifactId );
178 
179         Map<String, Vertex> vertices = vertexMap.get( projectKey );
180 
181         if ( vertices != null )
182         {
183             if ( isSpecificVersion( version ) )
184             {
185                 Vertex vertex = vertices.get( version );
186                 if ( vertex != null )
187                 {
188                     addEdge( projectVertex, vertex, project, projectMap, force, safe );
189                 }
190             }
191             else
192             {
193                 for ( Vertex vertex : vertices.values() )
194                 {
195                     addEdge( projectVertex, vertex, project, projectMap, force, safe );
196                 }
197             }
198         }
199     }
200 
201     private void addEdge( Vertex fromVertex, Vertex toVertex, MavenProject fromProject,
202                           Map<String, MavenProject> projectMap, boolean force, boolean safe )
203         throws CycleDetectedException
204     {
205         if ( fromVertex.equals( toVertex ) )
206         {
207             return;
208         }
209 
210         if ( fromProject != null )
211         {
212             MavenProject toProject = projectMap.get( toVertex.getLabel() );
213             fromProject.addProjectReference( toProject );
214         }
215 
216         if ( force && toVertex.getChildren().contains( fromVertex ) )
217         {
218             dag.removeEdge( toVertex, fromVertex );
219         }
220 
221         try
222         {
223             dag.addEdge( fromVertex, toVertex );
224         }
225         catch ( CycleDetectedException e )
226         {
227             if ( !safe )
228             {
229                 throw e;
230             }
231         }
232     }
233 
234     private boolean isSpecificVersion( String version )
235     {
236         return !( StringUtils.isEmpty( version ) || version.startsWith( "[" ) || version.startsWith( "(" ) );
237     }
238 
239     // TODO !![jc; 28-jul-2005] check this; if we're using '-r' and there are aggregator tasks, this will result in weirdness.
240     public MavenProject getTopLevelProject()
241     {
242         if ( topLevelProject == null )
243         {
244             for ( Iterator<MavenProject> i = sortedProjects.iterator(); i.hasNext() && ( topLevelProject == null ); )
245             {
246                 MavenProject project = i.next();
247                 if ( project.isExecutionRoot() )
248                 {
249                     topLevelProject = project;
250                 }
251             }
252         }
253 
254         return topLevelProject;
255     }
256 
257     public List<MavenProject> getSortedProjects()
258     {
259         return sortedProjects;
260     }
261 
262     public boolean hasMultipleProjects()
263     {
264         return sortedProjects.size() > 1;
265     }
266 
267     public List<String> getDependents( String id )
268     {
269         return dag.getParentLabels( id );
270     }
271 
272     public List<String> getDependencies( String id )
273     {
274         return dag.getChildLabels( id );
275     }
276 
277     public static String getId( MavenProject project )
278     {
279         return ArtifactUtils.key( project.getGroupId(), project.getArtifactId(), project.getVersion() );
280     }
281 
282     public DAG getDAG()
283     {
284         return dag;
285     }
286 
287     public Map<String, MavenProject> getProjectMap()
288     {
289         return projectMap;
290     }
291 
292 }