View Javadoc

1   package org.apache.continuum.utils;
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 org.apache.maven.continuum.model.project.Project;
23  import org.apache.maven.continuum.model.project.ProjectDependency;
24  import org.codehaus.plexus.util.dag.CycleDetectedException;
25  import org.codehaus.plexus.util.dag.DAG;
26  import org.codehaus.plexus.util.dag.TopologicalSorter;
27  import org.slf4j.Logger;
28  
29  import java.util.ArrayList;
30  import java.util.Collection;
31  import java.util.HashMap;
32  import java.util.List;
33  import java.util.Map;
34  
35  /**
36   * Sort projects by dependencies.
37   *
38   * @author <a href="mailto:brett@apache.org">Brett Porter</a>
39   * @version $Id: ProjectSorter.java 777411 2009-05-22 07:13:37Z ctan $
40   */
41  public class ProjectSorter
42  {
43      private ProjectSorter()
44      {
45          // no touchy...
46      }
47  
48      /**
49       * Sort a list of projects.
50       * <ul>
51       * <li>collect all the vertices for the projects that we want to build.</li>
52       * <li>iterate through the deps of each project and if that dep is within
53       * the set of projects we want to build then add an edge, otherwise throw
54       * the edge away because that dependency is not within the set of projects
55       * we are trying to build. we assume a closed set.</li>
56       * <li>do a topo sort on the graph that remains.</li>
57       * </ul>
58       */
59      public static List<Project> getSortedProjects( Collection<Project> projects, Logger logger )
60      {
61          DAG dag = new DAG();
62  
63          Map<String, Project> projectMap = new HashMap<String, Project>();
64  
65          for ( Project project : projects )
66          {
67              String id = getProjectId( project );
68  
69              if ( dag.getVertex( id ) != null )
70              {
71                  logger.warn( "Project '" + id + "' is duplicated in the reactor." );
72              }
73  
74              dag.addVertex( id );
75  
76              projectMap.put( id, project );
77          }
78  
79          for ( Project project : projects )
80          {
81              String id = getProjectId( project );
82  
83              String projectGroupId = "[" + project.getProjectGroup().getId() + "]";
84  
85              // Dependencies
86              for ( Object o : project.getDependencies() )
87              {
88                  ProjectDependency dependency = (ProjectDependency) o;
89  
90                  String dependencyId = projectGroupId + ":" + getDependencyId( dependency );
91  
92                  if ( dag.getVertex( dependencyId ) != null )
93                  {
94                      try
95                      {
96                          dag.addEdge( id, dependencyId );
97                      }
98                      catch ( CycleDetectedException e )
99                      {
100                         logger.warn( "Ignore cycle detected in project dependencies: " + e.getMessage() );
101                     }
102                 }
103             }
104 
105             // Parent
106             ProjectDependency parent = project.getParent();
107 
108             if ( parent != null )
109             {
110                 String parentId = projectGroupId + ":" + getDependencyId( parent );
111 
112                 if ( dag.getVertex( parentId ) != null )
113                 {
114                     // Parent is added as an edge, but must not cause a cycle - so we remove any other edges it has in conflict
115                     if ( dag.hasEdge( parentId, id ) )
116                     {
117                         dag.removeEdge( parentId, id );
118                     }
119                     try
120                     {
121                         dag.addEdge( id, parentId );
122                     }
123                     catch ( CycleDetectedException e )
124                     {
125                         logger.warn( "Ignore cycle detected in project parent: " + e.getMessage() );
126                     }
127                 }
128             }
129         }
130 
131         List<Project> sortedProjects = new ArrayList<Project>();
132 
133         for ( Object o : TopologicalSorter.sort( dag ) )
134         {
135             String id = (String) o;
136 
137             sortedProjects.add( projectMap.get( id ) );
138         }
139 
140         return sortedProjects;
141     }
142 
143     private static String getProjectId( Project project )
144     {
145         String groupId;
146 
147         String artifactId;
148 
149         if ( project.getGroupId() == null )
150         {
151             groupId = project.getName();
152         }
153         else
154         {
155             groupId = project.getGroupId();
156         }
157 
158         if ( project.getArtifactId() == null )
159         {
160             artifactId = project.getName();
161         }
162         else
163         {
164             artifactId = project.getArtifactId();
165         }
166 
167         String projectGroupId = "[" + project.getProjectGroup().getId() + "]";
168 
169         return projectGroupId + ":" + groupId + ":" + artifactId + ":" + project.getVersion();
170     }
171 
172     private static String getDependencyId( ProjectDependency project )
173     {
174         return project.getGroupId() + ":" + project.getArtifactId() + ":" + project.getVersion();
175     }
176 }