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  public class ProjectSorter
42  {
43      private DAG dag;
44  
45      private List<MavenProject> sortedProjects;
46  
47      private Map<String, MavenProject> projectMap;
48  
49      private MavenProject topLevelProject;
50  
51      /**
52       * Sort a list of projects.
53       * <ul>
54       * <li>collect all the vertices for the projects that we want to build.</li>
55       * <li>iterate through the deps of each project and if that dep is within
56       * the set of projects we want to build then add an edge, otherwise throw
57       * the edge away because that dependency is not within the set of projects
58       * we are trying to build. we assume a closed set.</li>
59       * <li>do a topo sort on the graph that remains.</li>
60       * </ul>
61       * @throws DuplicateProjectException if any projects are duplicated by id
62       */
63      // MAVENAPI FIXME: the DAG used is NOT only used to represent the dependency relation,
64      // but also for <parent>, <build><plugin>, <reports>. We need multiple DAG's
65      // since a DAG can only handle 1 type of relationship properly.
66      // Usecase:  This is detected as a cycle:
67      // org.apache.maven:maven-plugin-api                -(PARENT)->
68      // org.apache.maven:maven                           -(inherited REPORTING)->
69      // org.apache.maven.plugins:maven-checkstyle-plugin -(DEPENDENCY)->
70      // org.apache.maven:maven-plugin-api
71      // In this case, both the verify and the report goals are called
72      // in a different lifecycle. Though the compiler-plugin has a valid usecase, although
73      // that seems to work fine. We need to take versions and lifecycle into account.
74      public ProjectSorter( Collection<MavenProject> projects )
75          throws CycleDetectedException, DuplicateProjectException
76      {
77          dag = new DAG();
78  
79          // groupId:artifactId:version -> project
80          projectMap = new HashMap<String, MavenProject>( projects.size() * 2 );
81  
82          // groupId:artifactId -> (version -> vertex)
83          Map<String, Map<String, Vertex>> vertexMap = new HashMap<String, Map<String, Vertex>>( projects.size() * 2 );
84  
85          for ( MavenProject project : projects )
86          {
87              String projectId = getId( project );
88  
89              MavenProject conflictingProject = projectMap.put( projectId, project );
90  
91              if ( conflictingProject != null )
92              {
93                  throw new DuplicateProjectException( projectId, conflictingProject.getFile(), project.getFile(),
94                                                       "Project '" + projectId + "' is duplicated in the reactor" );
95              }
96  
97              String projectKey = ArtifactUtils.versionlessKey( project.getGroupId(), project.getArtifactId() );
98  
99              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 }