maven-core/src/main/java/org/apache/maven/project/ProjectSorter.java - maven - Git at Google

 package org.apache.maven.project;

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *  http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */

 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.stream.Collectors;

 import org.apache.maven.artifact.ArtifactUtils;
 import org.apache.maven.model.Dependency;
 import org.apache.maven.model.Extension;
 import org.apache.maven.model.Parent;
 import org.apache.maven.model.Plugin;
 import org.codehaus.plexus.util.StringUtils;
 import org.codehaus.plexus.util.dag.CycleDetectedException;
 import org.codehaus.plexus.util.dag.DAG;
 import org.codehaus.plexus.util.dag.TopologicalSorter;
 import org.codehaus.plexus.util.dag.Vertex;

 /**
  * ProjectSorter
  */
 public class ProjectSorter
 {
     private DAG dag;

     private List<MavenProject> sortedProjects;

     private Map<String, MavenProject> projectMap;

     /**
      * Sort a list of projects.
      * <ul>
      * <li>collect all the vertices for the projects that we want to build.</li>
      * <li>iterate through the deps of each project and if that dep is within
      * the set of projects we want to build then add an edge, otherwise throw
      * the edge away because that dependency is not within the set of projects
      * we are trying to build. we assume a closed set.</li>
      * <li>do a topo sort on the graph that remains.</li>
      * </ul>
      * @throws DuplicateProjectException if any projects are duplicated by id
      */
     // MAVENAPI FIXME: the DAG used is NOT only used to represent the dependency relation,
     // but also for <parent>, <build><plugin>, <reports>. We need multiple DAG's
     // since a DAG can only handle 1 type of relationship properly.
     // Usecase:  This is detected as a cycle:
     // org.apache.maven:maven-plugin-api                -(PARENT)->
     // org.apache.maven:maven                           -(inherited REPORTING)->
     // org.apache.maven.plugins:maven-checkstyle-plugin -(DEPENDENCY)->
     // org.apache.maven:maven-plugin-api
     // In this case, both the verify and the report goals are called
     // in a different lifecycle. Though the compiler-plugin has a valid usecase, although
     // that seems to work fine. We need to take versions and lifecycle into account.
     public ProjectSorter( Collection<MavenProject> projects )
         throws CycleDetectedException, DuplicateProjectException
     {
         dag = new DAG();

         // groupId:artifactId:version -> project
         projectMap = new HashMap<>( projects.size() * 2 );

         // groupId:artifactId -> (version -> vertex)
         Map<String, Map<String, Vertex>> vertexMap = new HashMap<>( projects.size() * 2 );

         for ( MavenProject project : projects )
         {
             String projectId = getId( project );

             MavenProject conflictingProject = projectMap.put( projectId, project );

             if ( conflictingProject != null )
             {
                 throw new DuplicateProjectException( projectId, conflictingProject.getFile(), project.getFile(),
                                                      "Project '" + projectId + "' is duplicated in the reactor" );
             }

             String projectKey = ArtifactUtils.versionlessKey( project.getGroupId(), project.getArtifactId() );

             Map<String, Vertex> vertices = vertexMap.computeIfAbsent( projectKey, k -> new HashMap<>( 2, 1 ) );

             vertices.put( project.getVersion(), dag.addVertex( projectId ) );
         }

         for ( Vertex projectVertex : dag.getVertices() )
         {
             String projectId = projectVertex.getLabel();

             MavenProject project = projectMap.get( projectId );

             for ( Dependency dependency : project.getDependencies() )
             {
                 addEdge( projectMap, vertexMap, project, projectVertex, dependency.getGroupId(),
                          dependency.getArtifactId(), dependency.getVersion(), false, false );
             }

             Parent parent = project.getModel().getParent();

             if ( parent != null )
             {
                 // Parent is added as an edge, but must not cause a cycle - so we remove any other edges it has
                 // in conflict
                 addEdge( projectMap, vertexMap, null, projectVertex, parent.getGroupId(), parent.getArtifactId(),
                          parent.getVersion(), true, false );
             }

             for ( Plugin plugin : project.getBuildPlugins() )
             {
                 addEdge( projectMap, vertexMap, project, projectVertex, plugin.getGroupId(),
                          plugin.getArtifactId(), plugin.getVersion(), false, true );

                 for ( Dependency dependency : plugin.getDependencies() )
                 {
                     addEdge( projectMap, vertexMap, project, projectVertex, dependency.getGroupId(),
                              dependency.getArtifactId(), dependency.getVersion(), false, true );
                 }
             }

             for ( Extension extension : project.getBuildExtensions() )
             {
                 addEdge( projectMap, vertexMap, project, projectVertex, extension.getGroupId(),
                          extension.getArtifactId(), extension.getVersion(), false, true );
             }
         }

         List<String> sortedProjectLabels = TopologicalSorter.sort( dag );

         this.sortedProjects = sortedProjectLabels.stream().map( id -> projectMap.get( id ) )
                 .collect( Collectors.collectingAndThen( Collectors.toList(), Collections::unmodifiableList ) );
     }
     @SuppressWarnings( "checkstyle:parameternumber" )
     private void addEdge( Map<String, MavenProject> projectMap, Map<String, Map<String, Vertex>> vertexMap,
                           MavenProject project, Vertex projectVertex, String groupId, String artifactId,
                           String version, boolean force, boolean safe )
         throws CycleDetectedException
     {
         String projectKey = ArtifactUtils.versionlessKey( groupId, artifactId );

         Map<String, Vertex> vertices = vertexMap.get( projectKey );

         if ( vertices != null )
         {
             if ( isSpecificVersion( version ) )
             {
                 Vertex vertex = vertices.get( version );
                 if ( vertex != null )
                 {
                     addEdge( projectVertex, vertex, project, projectMap, force, safe );
                 }
             }
             else
             {
                 for ( Vertex vertex : vertices.values() )
                 {
                     addEdge( projectVertex, vertex, project, projectMap, force, safe );
                 }
             }
         }
     }

     private void addEdge( Vertex fromVertex, Vertex toVertex, MavenProject fromProject,
                           Map<String, MavenProject> projectMap, boolean force, boolean safe )
         throws CycleDetectedException
     {
         if ( fromVertex.equals( toVertex ) )
         {
             return;
         }

         if ( fromProject != null )
         {
             MavenProject toProject = projectMap.get( toVertex.getLabel() );
             fromProject.addProjectReference( toProject );
         }

         if ( force && toVertex.getChildren().contains( fromVertex ) )
         {
             dag.removeEdge( toVertex, fromVertex );
         }

         try
         {
             dag.addEdge( fromVertex, toVertex );
         }
         catch ( CycleDetectedException e )
         {
             if ( !safe )
             {
                 throw e;
             }
         }
     }

     private boolean isSpecificVersion( String version )
     {
         return !( StringUtils.isEmpty( version ) || version.startsWith( "[" ) || version.startsWith( "(" ) );
     }

     // TODO !![jc; 28-jul-2005] check this; if we're using '-r' and there are aggregator tasks, this will result in weirdness.
     public MavenProject getTopLevelProject()
     {
         return sortedProjects.stream().filter( MavenProject::isExecutionRoot ).findFirst()
                 .orElse( null );
     }

     public List<MavenProject> getSortedProjects()
     {
         return sortedProjects;
     }

     public boolean hasMultipleProjects()
     {
         return sortedProjects.size() > 1;
     }

     public List<String> getDependents( String id )
     {
         return dag.getParentLabels( id );
     }

     public List<String> getDependencies( String id )
     {
         return dag.getChildLabels( id );
     }

     public static String getId( MavenProject project )
     {
         return ArtifactUtils.key( project.getGroupId(), project.getArtifactId(), project.getVersion() );
     }

     public DAG getDAG()
     {
         return dag;
     }

     public Map<String, MavenProject> getProjectMap()
     {
         return projectMap;
     }

 }
	package org.apache.maven.project;

	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*/

	import java.util.Collection;
	import java.util.Collections;
	import java.util.HashMap;
	import java.util.List;
	import java.util.Map;
	import java.util.stream.Collectors;

	import org.apache.maven.artifact.ArtifactUtils;
	import org.apache.maven.model.Dependency;
	import org.apache.maven.model.Extension;
	import org.apache.maven.model.Parent;
	import org.apache.maven.model.Plugin;
	import org.codehaus.plexus.util.StringUtils;
	import org.codehaus.plexus.util.dag.CycleDetectedException;
	import org.codehaus.plexus.util.dag.DAG;
	import org.codehaus.plexus.util.dag.TopologicalSorter;
	import org.codehaus.plexus.util.dag.Vertex;

	/**
	* ProjectSorter
	*/
	public class ProjectSorter
	{
	private DAG dag;

	private List<MavenProject> sortedProjects;

	private Map<String, MavenProject> projectMap;

	/**
	* Sort a list of projects.
	* <ul>
	* <li>collect all the vertices for the projects that we want to build.</li>
	* <li>iterate through the deps of each project and if that dep is within
	* the set of projects we want to build then add an edge, otherwise throw
	* the edge away because that dependency is not within the set of projects
	* we are trying to build. we assume a closed set.</li>
	* <li>do a topo sort on the graph that remains.</li>
	* </ul>
	* @throws DuplicateProjectException if any projects are duplicated by id
	*/
	// MAVENAPI FIXME: the DAG used is NOT only used to represent the dependency relation,
	// but also for <parent>, <build><plugin>, <reports>. We need multiple DAG's
	// since a DAG can only handle 1 type of relationship properly.
	// Usecase: This is detected as a cycle:
	// org.apache.maven:maven-plugin-api -(PARENT)->
	// org.apache.maven:maven -(inherited REPORTING)->
	// org.apache.maven.plugins:maven-checkstyle-plugin -(DEPENDENCY)->
	// org.apache.maven:maven-plugin-api
	// In this case, both the verify and the report goals are called
	// in a different lifecycle. Though the compiler-plugin has a valid usecase, although
	// that seems to work fine. We need to take versions and lifecycle into account.
	public ProjectSorter( Collection<MavenProject> projects )
	throws CycleDetectedException, DuplicateProjectException
	{
	dag = new DAG();

	// groupId:artifactId:version -> project
	projectMap = new HashMap<>( projects.size() * 2 );

	// groupId:artifactId -> (version -> vertex)
	Map<String, Map<String, Vertex>> vertexMap = new HashMap<>( projects.size() * 2 );

	for ( MavenProject project : projects )
	{
	String projectId = getId( project );

	MavenProject conflictingProject = projectMap.put( projectId, project );

	if ( conflictingProject != null )
	{
	throw new DuplicateProjectException( projectId, conflictingProject.getFile(), project.getFile(),
	"Project '" + projectId + "' is duplicated in the reactor" );
	}

	String projectKey = ArtifactUtils.versionlessKey( project.getGroupId(), project.getArtifactId() );

	Map<String, Vertex> vertices = vertexMap.computeIfAbsent( projectKey, k -> new HashMap<>( 2, 1 ) );

	vertices.put( project.getVersion(), dag.addVertex( projectId ) );
	}

	for ( Vertex projectVertex : dag.getVertices() )
	{
	String projectId = projectVertex.getLabel();

	MavenProject project = projectMap.get( projectId );

	for ( Dependency dependency : project.getDependencies() )
	{
	addEdge( projectMap, vertexMap, project, projectVertex, dependency.getGroupId(),
	dependency.getArtifactId(), dependency.getVersion(), false, false );
	}

	Parent parent = project.getModel().getParent();

	if ( parent != null )
	{
	// Parent is added as an edge, but must not cause a cycle - so we remove any other edges it has
	// in conflict
	addEdge( projectMap, vertexMap, null, projectVertex, parent.getGroupId(), parent.getArtifactId(),
	parent.getVersion(), true, false );
	}

	for ( Plugin plugin : project.getBuildPlugins() )
	{
	addEdge( projectMap, vertexMap, project, projectVertex, plugin.getGroupId(),
	plugin.getArtifactId(), plugin.getVersion(), false, true );

	for ( Dependency dependency : plugin.getDependencies() )
	{
	addEdge( projectMap, vertexMap, project, projectVertex, dependency.getGroupId(),
	dependency.getArtifactId(), dependency.getVersion(), false, true );
	}
	}

	for ( Extension extension : project.getBuildExtensions() )
	{
	addEdge( projectMap, vertexMap, project, projectVertex, extension.getGroupId(),
	extension.getArtifactId(), extension.getVersion(), false, true );
	}
	}

	List<String> sortedProjectLabels = TopologicalSorter.sort( dag );

	this.sortedProjects = sortedProjectLabels.stream().map( id -> projectMap.get( id ) )
	.collect( Collectors.collectingAndThen( Collectors.toList(), Collections::unmodifiableList ) );
	}
	@SuppressWarnings( "checkstyle:parameternumber" )
	private void addEdge( Map<String, MavenProject> projectMap, Map<String, Map<String, Vertex>> vertexMap,
	MavenProject project, Vertex projectVertex, String groupId, String artifactId,
	String version, boolean force, boolean safe )
	throws CycleDetectedException
	{
	String projectKey = ArtifactUtils.versionlessKey( groupId, artifactId );

	Map<String, Vertex> vertices = vertexMap.get( projectKey );

	if ( vertices != null )
	{
	if ( isSpecificVersion( version ) )
	{
	Vertex vertex = vertices.get( version );
	if ( vertex != null )
	{
	addEdge( projectVertex, vertex, project, projectMap, force, safe );
	}
	}
	else
	{
	for ( Vertex vertex : vertices.values() )
	{
	addEdge( projectVertex, vertex, project, projectMap, force, safe );
	}
	}
	}
	}

	private void addEdge( Vertex fromVertex, Vertex toVertex, MavenProject fromProject,
	Map<String, MavenProject> projectMap, boolean force, boolean safe )
	throws CycleDetectedException
	{
	if ( fromVertex.equals( toVertex ) )
	{
	return;
	}

	if ( fromProject != null )
	{
	MavenProject toProject = projectMap.get( toVertex.getLabel() );
	fromProject.addProjectReference( toProject );
	}

	if ( force && toVertex.getChildren().contains( fromVertex ) )
	{
	dag.removeEdge( toVertex, fromVertex );
	}

	try
	{
	dag.addEdge( fromVertex, toVertex );
	}
	catch ( CycleDetectedException e )
	{
	if ( !safe )
	{
	throw e;
	}
	}
	}

	private boolean isSpecificVersion( String version )
	{
	return !( StringUtils.isEmpty( version ) \|\| version.startsWith( "[" ) \|\| version.startsWith( "(" ) );
	}

	// TODO !![jc; 28-jul-2005] check this; if we're using '-r' and there are aggregator tasks, this will result in weirdness.
	public MavenProject getTopLevelProject()
	{
	return sortedProjects.stream().filter( MavenProject::isExecutionRoot ).findFirst()
	.orElse( null );
	}

	public List<MavenProject> getSortedProjects()
	{
	return sortedProjects;
	}

	public boolean hasMultipleProjects()
	{
	return sortedProjects.size() > 1;
	}

	public List<String> getDependents( String id )
	{
	return dag.getParentLabels( id );
	}

	public List<String> getDependencies( String id )
	{
	return dag.getChildLabels( id );
	}

	public static String getId( MavenProject project )
	{
	return ArtifactUtils.key( project.getGroupId(), project.getArtifactId(), project.getVersion() );
	}

	public DAG getDAG()
	{
	return dag;
	}

	public Map<String, MavenProject> getProjectMap()
	{
	return projectMap;
	}

	}