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 793745 2009-07-13 23:24:10Z jdcasey $
48   */
49  public class ProjectSorter
50  {
51      private final DAG dag;
52      
53      private final Map projectMap;
54  
55      private final List<MavenProject> 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                               // If the plugin in which this dependency is listed is actually used here,
160                               // it will probably be stuck using an older version of this project that
161                               // already exists in the local repository. If not yet installed, it is
162                               // likely that we'll get an ArtifactNotFoundException when this plugin
163                               // is executed to build this project.
164                               //
165                               // If the plugin is NOT actually used here, it may actually belong in the
166                               // pluginManagement section.
167                               if ( !id.equals( dependencyId ) )
168                               {
169                                   project.addProjectReference( (MavenProject) projectMap.get( dependencyId ) );
170 
171                                   addEdgeWithParentCheck( projectMap, dependencyId, project, id );
172                                   
173                                   // TODO: Shouldn't we add an edge between the plugin and its dependency?
174                                   // Note that doing this may result in cycles...run 
175                                   // ProjectSorterTest.testPluginDependenciesInfluenceSorting_DeclarationInParent() 
176                                   // for more information, if you change this:
177                                   
178                                   // dag.addEdge( pluginId, dependencyId );
179                               }
180                           }
181                        }
182                     }
183                 }
184             }
185 
186             List reportPlugins = project.getReportPlugins();
187             if ( reportPlugins != null )
188             {
189                 for ( Iterator j = reportPlugins.iterator(); j.hasNext(); )
190                 {
191                     ReportPlugin plugin = (ReportPlugin) j.next();
192                     String pluginId = ArtifactUtils.versionlessKey( plugin.getGroupId(), plugin.getArtifactId() );
193                     if ( dag.getVertex( pluginId ) != null && !pluginId.equals( id ) )
194                     {
195                         addEdgeWithParentCheck( projectMap, pluginId, project, id );
196                     }
197                 }
198             }
199 
200             for ( Iterator j = project.getBuildExtensions().iterator(); j.hasNext(); )
201             {
202                 Extension extension = (Extension) j.next();
203                 String extensionId = ArtifactUtils.versionlessKey( extension.getGroupId(), extension.getArtifactId() );
204                 if ( dag.getVertex( extensionId ) != null )
205                 {
206                     addEdgeWithParentCheck( projectMap, extensionId, project, id );
207                 }
208             }
209         }
210 
211         List sortedProjects = new ArrayList();
212 
213         for ( Iterator i = TopologicalSorter.sort( dag ).iterator(); i.hasNext(); )
214         {
215             String id = (String) i.next();
216 
217             sortedProjects.add( projectMap.get( id ) );
218         }
219         
220         // TODO: !![jc; 28-jul-2005] check this; if we're using '-r' and there are aggregator tasks, this will result in weirdness.
221         for ( Iterator i = sortedProjects.iterator(); i.hasNext() && topLevelProject == null; )
222         {
223             MavenProject project = (MavenProject) i.next();
224             if ( project.isExecutionRoot() )
225             {
226                 topLevelProject = project;
227             }
228         }
229         
230         sortedProjects = applyMakeFilter( sortedProjects, dag, projectMap, topLevelProject, selectedProjectNames, make, makeDependents );
231         
232         resumeFrom( resumeFrom, sortedProjects, projectMap, topLevelProject );
233 
234         this.sortedProjects = Collections.unmodifiableList( sortedProjects );
235     }
236 
237     // make selected projects and possibly projects they depend on, or projects that depend on them 
238     private static List applyMakeFilter( List sortedProjects, DAG dag, Map projectMap, MavenProject topLevelProject, List selectedProjectNames, boolean make, boolean makeDependents ) throws MissingProjectException
239     {
240         if ( selectedProjectNames == null ) return sortedProjects;
241         
242         MavenProject[] selectedProjects = new MavenProject[selectedProjectNames.size()];
243         for ( int i = 0; i < selectedProjects.length; i++ )
244         {
245             selectedProjects[i] = findProject( (String) selectedProjectNames.get( i ), projectMap, topLevelProject );
246         }
247         Set projectsToMake = new HashSet( Arrays.asList( selectedProjects ) );
248         for ( int i = 0; i < selectedProjects.length; i++ )
249         {
250             MavenProject project = selectedProjects[i];
251             String id = ArtifactUtils.versionlessKey( project.getGroupId(), project.getArtifactId() );
252             Vertex v = dag.getVertex( id );
253             if ( make )
254             {
255                 gatherDescendents ( v, projectMap, projectsToMake, new HashSet() );
256             }
257             if ( makeDependents )
258             {
259                 gatherAncestors ( v, projectMap, projectsToMake, new HashSet() );
260             }
261         }
262         for ( Iterator i = sortedProjects.iterator(); i.hasNext(); )
263         {
264             MavenProject project = (MavenProject) i.next();
265             if ( !projectsToMake.contains( project ) )
266             {
267                 i.remove();
268             }
269         }
270         return sortedProjects;
271     }
272     
273     private static void resumeFrom( String resumeFrom, List sortedProjects, Map projectMap, MavenProject topLevelProject ) throws MissingProjectException
274     {
275         if ( resumeFrom == null ) return;
276         MavenProject resumeFromProject = findProject( resumeFrom, projectMap, topLevelProject );
277         for ( Iterator i = sortedProjects.iterator(); i.hasNext(); )
278         {
279             MavenProject project = (MavenProject) i.next();
280             if ( resumeFromProject.equals( project ) ) break;
281             i.remove();
282         }
283         if ( sortedProjects.isEmpty() )
284         {
285             throw new MissingProjectException( "Couldn't resume, project was not scheduled to run: " + resumeFrom );
286         }
287     }
288     
289     private static MavenProject findProject( String projectName, Map projectMap, MavenProject topLevelProject ) throws MissingProjectException
290     {
291         MavenProject project = (MavenProject) projectMap.get( projectName );
292         if ( project != null ) return project;
293         // in that case, it must be a file path
294         File baseDir;
295         if ( topLevelProject == null ) {
296             baseDir = new File( System.getProperty( "user.dir" ) );
297         } else {
298             baseDir = topLevelProject.getBasedir();
299             // or should this be .getFile().getParentFile() ?
300         }
301         
302         File projectDir = new File( baseDir, projectName );
303         if ( !projectDir.exists() ) {
304             throw new MissingProjectException( "Couldn't find specified project dir: " + projectDir.getAbsolutePath() );
305         }
306         if ( !projectDir.isDirectory() ) {
307             throw new MissingProjectException( "Couldn't find specified project dir (not a directory): " + projectDir.getAbsolutePath() );
308         }
309         
310         for ( Iterator i = projectMap.values().iterator(); i.hasNext(); )
311         {
312             project = (MavenProject) i.next();
313             if ( projectDir.equals( project.getFile().getParentFile() ) ) return project;
314         }
315         
316         throw new MissingProjectException( "Couldn't find specified project in module list: " + projectDir.getAbsolutePath() );
317     }
318     
319     private static void gatherDescendents ( Vertex v, Map projectMap, Set out, Set visited )
320     {
321         if ( visited.contains( v ) ) return;
322         visited.add( v );
323         out.add( projectMap.get( v.getLabel() ) );
324         for ( Iterator i = v.getChildren().iterator(); i.hasNext(); )
325         {
326             Vertex child = (Vertex) i.next();
327             gatherDescendents( child, projectMap, out, visited );
328         }
329     }
330     
331     private static void gatherAncestors ( Vertex v, Map projectMap, Set out, Set visited )
332     {
333         if ( visited.contains( v ) ) return;
334         visited.add( v );
335         out.add( projectMap.get( v.getLabel() ) );
336         for ( Iterator i = v.getParents().iterator(); i.hasNext(); )
337         {
338             Vertex parent = (Vertex) i.next();
339             gatherAncestors( parent, projectMap, out, visited );
340         }
341     }
342     
343     private void addEdgeWithParentCheck( Map projectMap, String projectRefId, MavenProject project, String id )
344         throws CycleDetectedException
345     {
346         MavenProject extProject = (MavenProject) projectMap.get( projectRefId );
347         
348         if ( extProject == null )
349         {
350             return;
351         }
352 
353         project.addProjectReference( extProject );
354 
355         MavenProject extParent = extProject.getParent();
356         if ( extParent != null )
357         {
358             String parentId = ArtifactUtils.versionlessKey( extParent.getGroupId(), extParent.getArtifactId() );
359             // Don't add edge from parent to extension if a reverse edge already exists
360             if ( !dag.hasEdge( projectRefId, id ) || !parentId.equals( id ) )
361             {
362                 dag.addEdge( id, projectRefId );
363             }
364         }
365     }
366 
367     public MavenProject getTopLevelProject()
368     {
369         return topLevelProject;
370     }
371 
372     public List<MavenProject> getSortedProjects()
373     {
374         return sortedProjects;
375     }
376 
377     public boolean hasMultipleProjects()
378     {
379         return sortedProjects.size() > 1;
380     }
381 
382     public List getDependents( String id )
383     {
384         return dag.getParentLabels( id );
385     }
386     
387     public DAG getDAG()
388     {
389         return dag;
390     }
391     
392     public Map getProjectMap()
393     {
394         return projectMap;
395     }
396 }