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.io.File;
23  import java.util.ArrayList;
24  import java.util.Arrays;
25  import java.util.Collections;
26  import java.util.HashMap;
27  import java.util.HashSet;
28  import java.util.Iterator;
29  import java.util.List;
30  import java.util.Map;
31  import java.util.Set;
32  
33  import org.apache.maven.artifact.ArtifactUtils;
34  import org.apache.maven.model.Dependency;
35  import org.apache.maven.model.Extension;
36  import org.apache.maven.model.Plugin;
37  import org.apache.maven.model.ReportPlugin;
38  import org.codehaus.plexus.util.dag.CycleDetectedException;
39  import org.codehaus.plexus.util.dag.DAG;
40  import org.codehaus.plexus.util.dag.TopologicalSorter;
41  import org.codehaus.plexus.util.dag.Vertex;
42  
43  /**
44   * Sort projects by dependencies.
45   *
46   * @author <a href="mailto:brett@apache.org">Brett Porter</a>
47   * @version $Id: ProjectSorter.java 752622 2009-03-11 21:15:51Z jdcasey $
48   */
49  public class ProjectSorter
50  {
51      private final DAG dag;
52      
53      private final Map projectMap;
54  
55      private final List sortedProjects;
56  
57      private MavenProject topLevelProject;
58  
59      /**
60       * Sort a list of projects.
61       * <ul>
62       * <li>collect all the vertices for the projects that we want to build.</li>
63       * <li>iterate through the deps of each project and if that dep is within
64       * the set of projects we want to build then add an edge, otherwise throw
65       * the edge away because that dependency is not within the set of projects
66       * we are trying to build. we assume a closed set.</li>
67       * <li>do a topo sort on the graph that remains.</li>
68       * </ul>
69       * @throws DuplicateProjectException if any projects are duplicated by id
70       * @throws MissingProjectException 
71       */
72      public ProjectSorter( List projects )
73          throws CycleDetectedException, DuplicateProjectException, MissingProjectException
74      {
75          this( projects, null, null, false, false );
76      }
77      
78      public ProjectSorter( List projects, List selectedProjectNames, String resumeFrom, boolean make, boolean makeDependents )
79          throws CycleDetectedException, DuplicateProjectException, MissingProjectException
80      {
81          dag = new DAG();
82  
83          projectMap = new HashMap();
84  
85          for ( Iterator i = projects.iterator(); i.hasNext(); )
86          {
87              MavenProject project = (MavenProject) i.next();
88  
89              String id = ArtifactUtils.versionlessKey( project.getGroupId(), project.getArtifactId() );
90  
91              if ( dag.getVertex( id ) != null )
92              {
93                  throw new DuplicateProjectException( "Project '" + id + "' is duplicated in the reactor" );
94              }
95  
96              dag.addVertex( id );
97  
98              projectMap.put( id, project );
99          }
100 
101         for ( Iterator i = projects.iterator(); i.hasNext(); )
102         {
103             MavenProject project = (MavenProject) i.next();
104 
105             String id = ArtifactUtils.versionlessKey( project.getGroupId(), project.getArtifactId() );
106 
107             for ( Iterator j = project.getDependencies().iterator(); j.hasNext(); )
108             {
109                 Dependency dependency = (Dependency) j.next();
110 
111                 String dependencyId = ArtifactUtils
112                     .versionlessKey( dependency.getGroupId(), dependency.getArtifactId() );
113 
114                 if ( dag.getVertex( dependencyId ) != null )
115                 {
116                     project.addProjectReference( (MavenProject) projectMap.get( dependencyId ) );
117 
118                     dag.addEdge( id, dependencyId );
119                 }
120             }
121 
122             MavenProject parent = project.getParent();
123             if ( parent != null )
124             {
125                 String parentId = ArtifactUtils.versionlessKey( parent.getGroupId(), parent.getArtifactId() );
126                 if ( dag.getVertex( parentId ) != null )
127                 {
128                     // Parent is added as an edge, but must not cause a cycle - so we remove any other edges it has in conflict
129                     if ( dag.hasEdge( parentId, id ) )
130                     {
131                         dag.removeEdge( parentId, id );
132                     }
133                     dag.addEdge( id, parentId );
134                 }
135             }
136 
137             List buildPlugins = project.getBuildPlugins();
138             if ( buildPlugins != null )
139             {
140                 for ( Iterator j = buildPlugins.iterator(); j.hasNext(); )
141                 {
142                     Plugin plugin = (Plugin) j.next();
143                     String pluginId = ArtifactUtils.versionlessKey( plugin.getGroupId(), plugin.getArtifactId() );
144                     if ( dag.getVertex( pluginId ) != null && !pluginId.equals( id ) )
145                     {
146                         addEdgeWithParentCheck( projectMap, pluginId, project, id );
147                     }
148 
149                     if ( !pluginId.equals( id ) ) {
150                         for ( Iterator k = plugin.getDependencies().iterator(); k.hasNext(); )
151                         {
152                           Dependency dependency = (Dependency) k.next();
153 
154                           String dependencyId = ArtifactUtils
155                               .versionlessKey( dependency.getGroupId(), dependency.getArtifactId() );
156 
157                           if ( dag.getVertex( dependencyId ) != null )
158                           {
159                               project.addProjectReference( (MavenProject) projectMap.get( dependencyId ) );
160 
161                               addEdgeWithParentCheck( projectMap, dependencyId, project, id );
162                               
163                               // TODO: Shouldn't we add an edge between the plugin and its dependency?
164                               // Note that doing this may result in cycles...run 
165                               // ProjectSorterTest.testPluginDependenciesInfluenceSorting_DeclarationInParent() 
166                               // for more information, if you change this:
167                               
168                               // dag.addEdge( pluginId, dependencyId );
169                           }
170                        }
171                     }
172                 }
173             }
174 
175             List reportPlugins = project.getReportPlugins();
176             if ( reportPlugins != null )
177             {
178                 for ( Iterator j = reportPlugins.iterator(); j.hasNext(); )
179                 {
180                     ReportPlugin plugin = (ReportPlugin) j.next();
181                     String pluginId = ArtifactUtils.versionlessKey( plugin.getGroupId(), plugin.getArtifactId() );
182                     if ( dag.getVertex( pluginId ) != null && !pluginId.equals( id ) )
183                     {
184                         addEdgeWithParentCheck( projectMap, pluginId, project, id );
185                     }
186                 }
187             }
188 
189             for ( Iterator j = project.getBuildExtensions().iterator(); j.hasNext(); )
190             {
191                 Extension extension = (Extension) j.next();
192                 String extensionId = ArtifactUtils.versionlessKey( extension.getGroupId(), extension.getArtifactId() );
193                 if ( dag.getVertex( extensionId ) != null )
194                 {
195                     addEdgeWithParentCheck( projectMap, extensionId, project, id );
196                 }
197             }
198         }
199 
200         List sortedProjects = new ArrayList();
201 
202         for ( Iterator i = TopologicalSorter.sort( dag ).iterator(); i.hasNext(); )
203         {
204             String id = (String) i.next();
205 
206             sortedProjects.add( projectMap.get( id ) );
207         }
208         
209         // TODO: !![jc; 28-jul-2005] check this; if we're using '-r' and there are aggregator tasks, this will result in weirdness.
210         for ( Iterator i = sortedProjects.iterator(); i.hasNext() && topLevelProject == null; )
211         {
212             MavenProject project = (MavenProject) i.next();
213             if ( project.isExecutionRoot() )
214             {
215                 topLevelProject = project;
216             }
217         }
218         
219         sortedProjects = applyMakeFilter( sortedProjects, dag, projectMap, topLevelProject, selectedProjectNames, make, makeDependents );
220         
221         resumeFrom( resumeFrom, sortedProjects, projectMap, topLevelProject );
222 
223         this.sortedProjects = Collections.unmodifiableList( sortedProjects );
224     }
225 
226     // make selected projects and possibly projects they depend on, or projects that depend on them 
227     private static List applyMakeFilter( List sortedProjects, DAG dag, Map projectMap, MavenProject topLevelProject, List selectedProjectNames, boolean make, boolean makeDependents ) throws MissingProjectException
228     {
229         if ( selectedProjectNames == null ) return sortedProjects;
230         
231         MavenProject[] selectedProjects = new MavenProject[selectedProjectNames.size()];
232         for ( int i = 0; i < selectedProjects.length; i++ )
233         {
234             selectedProjects[i] = findProject( (String) selectedProjectNames.get( i ), projectMap, topLevelProject );
235         }
236         Set projectsToMake = new HashSet( Arrays.asList( selectedProjects ) );
237         for ( int i = 0; i < selectedProjects.length; i++ )
238         {
239             MavenProject project = selectedProjects[i];
240             String id = ArtifactUtils.versionlessKey( project.getGroupId(), project.getArtifactId() );
241             Vertex v = dag.getVertex( id );
242             if ( make )
243             {
244                 gatherDescendents ( v, projectMap, projectsToMake, new HashSet() );
245             }
246             if ( makeDependents )
247             {
248                 gatherAncestors ( v, projectMap, projectsToMake, new HashSet() );
249             }
250         }
251         for ( Iterator i = sortedProjects.iterator(); i.hasNext(); )
252         {
253             MavenProject project = (MavenProject) i.next();
254             if ( !projectsToMake.contains( project ) )
255             {
256                 i.remove();
257             }
258         }
259         return sortedProjects;
260     }
261     
262     private static void resumeFrom( String resumeFrom, List sortedProjects, Map projectMap, MavenProject topLevelProject ) throws MissingProjectException
263     {
264         if ( resumeFrom == null ) return;
265         MavenProject resumeFromProject = findProject( resumeFrom, projectMap, topLevelProject );
266         for ( Iterator i = sortedProjects.iterator(); i.hasNext(); )
267         {
268             MavenProject project = (MavenProject) i.next();
269             if ( resumeFromProject.equals( project ) ) break;
270             i.remove();
271         }
272         if ( sortedProjects.isEmpty() )
273         {
274             throw new MissingProjectException( "Couldn't resume, project was not scheduled to run: " + resumeFrom );
275         }
276     }
277     
278     private static MavenProject findProject( String projectName, Map projectMap, MavenProject topLevelProject ) throws MissingProjectException
279     {
280         MavenProject project = (MavenProject) projectMap.get( projectName );
281         if ( project != null ) return project;
282         // in that case, it must be a file path
283         File baseDir;
284         if ( topLevelProject == null ) {
285             baseDir = new File( System.getProperty( "user.dir" ) );
286         } else {
287             baseDir = topLevelProject.getBasedir();
288             // or should this be .getFile().getParentFile() ?
289         }
290         
291         File projectDir = new File( baseDir, projectName );
292         if ( !projectDir.exists() ) {
293             throw new MissingProjectException( "Couldn't find specified project dir: " + projectDir.getAbsolutePath() );
294         }
295         if ( !projectDir.isDirectory() ) {
296             throw new MissingProjectException( "Couldn't find specified project dir (not a directory): " + projectDir.getAbsolutePath() );
297         }
298         
299         for ( Iterator i = projectMap.values().iterator(); i.hasNext(); )
300         {
301             project = (MavenProject) i.next();
302             if ( projectDir.equals( project.getFile().getParentFile() ) ) return project;
303         }
304         
305         throw new MissingProjectException( "Couldn't find specified project in module list: " + projectDir.getAbsolutePath() );
306     }
307     
308     private static void gatherDescendents ( Vertex v, Map projectMap, Set out, Set visited )
309     {
310         if ( visited.contains( v ) ) return;
311         visited.add( v );
312         out.add( projectMap.get( v.getLabel() ) );
313         for ( Iterator i = v.getChildren().iterator(); i.hasNext(); )
314         {
315             Vertex child = (Vertex) i.next();
316             gatherDescendents( child, projectMap, out, visited );
317         }
318     }
319     
320     private static void gatherAncestors ( Vertex v, Map projectMap, Set out, Set visited )
321     {
322         if ( visited.contains( v ) ) return;
323         visited.add( v );
324         out.add( projectMap.get( v.getLabel() ) );
325         for ( Iterator i = v.getParents().iterator(); i.hasNext(); )
326         {
327             Vertex parent = (Vertex) i.next();
328             gatherAncestors( parent, projectMap, out, visited );
329         }
330     }
331     
332     private void addEdgeWithParentCheck( Map projectMap, String projectRefId, MavenProject project, String id )
333         throws CycleDetectedException
334     {
335         MavenProject extProject = (MavenProject) projectMap.get( projectRefId );
336         
337         if ( extProject == null )
338         {
339             return;
340         }
341 
342         project.addProjectReference( extProject );
343 
344         MavenProject extParent = extProject.getParent();
345         if ( extParent != null )
346         {
347             String parentId = ArtifactUtils.versionlessKey( extParent.getGroupId(), extParent.getArtifactId() );
348             // Don't add edge from parent to extension if a reverse edge already exists
349             if ( !dag.hasEdge( projectRefId, id ) || !parentId.equals( id ) )
350             {
351                 dag.addEdge( id, projectRefId );
352             }
353         }
354     }
355 
356     public MavenProject getTopLevelProject()
357     {
358         return topLevelProject;
359     }
360 
361     public List getSortedProjects()
362     {
363         return sortedProjects;
364     }
365 
366     public boolean hasMultipleProjects()
367     {
368         return sortedProjects.size() > 1;
369     }
370 
371     public List getDependents( String id )
372     {
373         return dag.getParentLabels( id );
374     }
375     
376     public DAG getDAG()
377     {
378         return dag;
379     }
380     
381     public Map getProjectMap()
382     {
383         return projectMap;
384     }
385 }