maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/ConflictIdSorter.java - maven-resolver - Git at Google

 package org.eclipse.aether.util.graph.transformer;

 /*
  * 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.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;

 import org.eclipse.aether.RepositoryException;
 import org.eclipse.aether.collection.DependencyGraphTransformationContext;
 import org.eclipse.aether.collection.DependencyGraphTransformer;
 import org.eclipse.aether.graph.DependencyNode;

 /**
  * A dependency graph transformer that creates a topological sorting of the conflict ids which have been assigned to the
  * dependency nodes. Conflict ids are sorted according to the dependency relation induced by the dependency graph. This
  * transformer will query the key {@link TransformationContextKeys#CONFLICT_IDS} in the transformation context for an
  * existing mapping of nodes to their conflicts ids. In absence of this map, the transformer will automatically invoke
  * the {@link ConflictMarker} to calculate the conflict ids. When this transformer has executed, the transformation
  * context holds a {@code List<Object>} that denotes the topologically sorted conflict ids. The list will be stored
  * using the key {@link TransformationContextKeys#SORTED_CONFLICT_IDS}. In addition, the transformer will store a
  * {@code Collection<Collection<Object>>} using the key {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} that
  * describes cycles among conflict ids.
  */
 public final class ConflictIdSorter
     implements DependencyGraphTransformer
 {

     public DependencyNode transformGraph( DependencyNode node, DependencyGraphTransformationContext context )
         throws RepositoryException
     {
         Map<?, ?> conflictIds = (Map<?, ?>) context.get( TransformationContextKeys.CONFLICT_IDS );
         if ( conflictIds == null )
         {
             ConflictMarker marker = new ConflictMarker();
             marker.transformGraph( node, context );

             conflictIds = (Map<?, ?>) context.get( TransformationContextKeys.CONFLICT_IDS );
         }

         @SuppressWarnings( "unchecked" )
         Map<String, Object> stats = (Map<String, Object>) context.get( TransformationContextKeys.STATS );
         long time1 = System.nanoTime();

         Map<Object, ConflictId> ids = new LinkedHashMap<Object, ConflictId>( 256 );

         {
             ConflictId id = null;
             Object key = conflictIds.get( node );
             if ( key != null )
             {
                 id = new ConflictId( key, 0 );
                 ids.put( key, id );
             }

             Map<DependencyNode, Object> visited = new IdentityHashMap<DependencyNode, Object>( conflictIds.size() );

             buildConflitIdDAG( ids, node, id, 0, visited, conflictIds );
         }

         long time2 = System.nanoTime();

         int cycles = topsortConflictIds( ids.values(), context );

         if ( stats != null )
         {
             long time3 = System.nanoTime();
             stats.put( "ConflictIdSorter.graphTime", time2 - time1 );
             stats.put( "ConflictIdSorter.topsortTime", time3 - time2 );
             stats.put( "ConflictIdSorter.conflictIdCount", ids.size() );
             stats.put( "ConflictIdSorter.conflictIdCycleCount", cycles );
         }

         return node;
     }

     private void buildConflitIdDAG( Map<Object, ConflictId> ids, DependencyNode node, ConflictId id, int depth,
                                     Map<DependencyNode, Object> visited, Map<?, ?> conflictIds )
     {
         if ( visited.put( node, Boolean.TRUE ) != null )
         {
             return;
         }

         depth++;

         for ( DependencyNode child : node.getChildren() )
         {
             Object key = conflictIds.get( child );
             ConflictId childId = ids.get( key );
             if ( childId == null )
             {
                 childId = new ConflictId( key, depth );
                 ids.put( key, childId );
             }
             else
             {
                 childId.pullup( depth );
             }

             if ( id != null )
             {
                 id.add( childId );
             }

             buildConflitIdDAG( ids, child, childId, depth, visited, conflictIds );
         }
     }

     private int topsortConflictIds( Collection<ConflictId> conflictIds, DependencyGraphTransformationContext context )
     {
         List<Object> sorted = new ArrayList<Object>( conflictIds.size() );

         RootQueue roots = new RootQueue( conflictIds.size() / 2 );
         for ( ConflictId id : conflictIds )
         {
             if ( id.inDegree <= 0 )
             {
                 roots.add( id );
             }
         }

         processRoots( sorted, roots );

         boolean cycle = sorted.size() < conflictIds.size();

         while ( sorted.size() < conflictIds.size() )
         {
             // cycle -> deal gracefully with nodes still having positive in-degree

             ConflictId nearest = null;
             for ( ConflictId id : conflictIds )
             {
                 if ( id.inDegree <= 0 )
                 {
                     continue;
                 }
                 if ( nearest == null || id.minDepth < nearest.minDepth
                     || ( id.minDepth == nearest.minDepth && id.inDegree < nearest.inDegree ) )
                 {
                     nearest = id;
                 }
             }

             nearest.inDegree = 0;
             roots.add( nearest );

             processRoots( sorted, roots );
         }

         Collection<Collection<Object>> cycles = Collections.emptySet();
         if ( cycle )
         {
             cycles = findCycles( conflictIds );
         }

         context.put( TransformationContextKeys.SORTED_CONFLICT_IDS, sorted );
         context.put( TransformationContextKeys.CYCLIC_CONFLICT_IDS, cycles );

         return cycles.size();
     }

     private void processRoots( List<Object> sorted, RootQueue roots )
     {
         while ( !roots.isEmpty() )
         {
             ConflictId root = roots.remove();

             sorted.add( root.key );

             for ( ConflictId child : root.children )
             {
                 child.inDegree--;
                 if ( child.inDegree == 0 )
                 {
                     roots.add( child );
                 }
             }
         }
     }

     private Collection<Collection<Object>> findCycles( Collection<ConflictId> conflictIds )
     {
         Collection<Collection<Object>> cycles = new HashSet<Collection<Object>>();

         Map<Object, Integer> stack = new HashMap<Object, Integer>( 128 );
         Map<ConflictId, Object> visited = new IdentityHashMap<ConflictId, Object>( conflictIds.size() );
         for ( ConflictId id : conflictIds )
         {
             findCycles( id, visited, stack, cycles );
         }

         return cycles;
     }

     private void findCycles( ConflictId id, Map<ConflictId, Object> visited, Map<Object, Integer> stack,
                              Collection<Collection<Object>> cycles )
     {
         Integer depth = stack.put( id.key, stack.size() );
         if ( depth != null )
         {
             stack.put( id.key, depth );
             Collection<Object> cycle = new HashSet<Object>();
             for ( Map.Entry<Object, Integer> entry : stack.entrySet() )
             {
                 if ( entry.getValue() >= depth )
                 {
                     cycle.add( entry.getKey() );
                 }
             }
             cycles.add( cycle );
         }
         else
         {
             if ( visited.put( id, Boolean.TRUE ) == null )
             {
                 for ( ConflictId childId : id.children )
                 {
                     findCycles( childId, visited, stack, cycles );
                 }
             }
             stack.remove( id.key );
         }
     }

     static final class ConflictId
     {

         final Object key;

         Collection<ConflictId> children = Collections.emptySet();

         int inDegree;

         int minDepth;

         ConflictId( Object key, int depth )
         {
             this.key = key;
             this.minDepth = depth;
         }

         public void add( ConflictId child )
         {
             if ( children.isEmpty() )
             {
                 children = new HashSet<ConflictId>();
             }
             if ( children.add( child ) )
             {
                 child.inDegree++;
             }
         }

         public void pullup( int depth )
         {
             if ( depth < minDepth )
             {
                 minDepth = depth;
                 depth++;
                 for ( ConflictId child : children )
                 {
                     child.pullup( depth );
                 }
             }
         }

         @Override
         public boolean equals( Object obj )
         {
             if ( this == obj )
             {
                 return true;
             }
             else if ( !( obj instanceof ConflictId ) )
             {
                 return false;
             }
             ConflictId that = (ConflictId) obj;
             return this.key.equals( that.key );
         }

         @Override
         public int hashCode()
         {
             return key.hashCode();
         }

         @Override
         public String toString()
         {
             return key + " @ " + minDepth + " <" + inDegree;
         }

     }

     static final class RootQueue
     {

         private int nextOut;

         private int nextIn;

         private ConflictId[] ids;

         RootQueue( int capacity )
         {
             ids = new ConflictId[capacity + 16];
         }

         boolean isEmpty()
         {
             return nextOut >= nextIn;
         }

         void add( ConflictId id )
         {
             if ( nextOut >= nextIn && nextOut > 0 )
             {
                 nextIn -= nextOut;
                 nextOut = 0;
             }
             if ( nextIn >= ids.length )
             {
                 ConflictId[] tmp = new ConflictId[ids.length + ids.length / 2 + 16];
                 System.arraycopy( ids, nextOut, tmp, 0, nextIn - nextOut );
                 ids = tmp;
                 nextIn -= nextOut;
                 nextOut = 0;
             }
             int i;
             for ( i = nextIn - 1; i >= nextOut && id.minDepth < ids[i].minDepth; i-- )
             {
                 ids[i + 1] = ids[i];
             }
             ids[i + 1] = id;
             nextIn++;
         }

         ConflictId remove()
         {
             return ids[nextOut++];
         }

     }

 }
	package org.eclipse.aether.util.graph.transformer;

	/*
	* 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.ArrayList;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.IdentityHashMap;
	import java.util.LinkedHashMap;
	import java.util.List;
	import java.util.Map;

	import org.eclipse.aether.RepositoryException;
	import org.eclipse.aether.collection.DependencyGraphTransformationContext;
	import org.eclipse.aether.collection.DependencyGraphTransformer;
	import org.eclipse.aether.graph.DependencyNode;

	/**
	* A dependency graph transformer that creates a topological sorting of the conflict ids which have been assigned to the
	* dependency nodes. Conflict ids are sorted according to the dependency relation induced by the dependency graph. This
	* transformer will query the key {@link TransformationContextKeys#CONFLICT_IDS} in the transformation context for an
	* existing mapping of nodes to their conflicts ids. In absence of this map, the transformer will automatically invoke
	* the {@link ConflictMarker} to calculate the conflict ids. When this transformer has executed, the transformation
	* context holds a {@code List<Object>} that denotes the topologically sorted conflict ids. The list will be stored
	* using the key {@link TransformationContextKeys#SORTED_CONFLICT_IDS}. In addition, the transformer will store a
	* {@code Collection<Collection<Object>>} using the key {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} that
	* describes cycles among conflict ids.
	*/
	public final class ConflictIdSorter
	implements DependencyGraphTransformer
	{

	public DependencyNode transformGraph( DependencyNode node, DependencyGraphTransformationContext context )
	throws RepositoryException
	{
	Map<?, ?> conflictIds = (Map<?, ?>) context.get( TransformationContextKeys.CONFLICT_IDS );
	if ( conflictIds == null )
	{
	ConflictMarker marker = new ConflictMarker();
	marker.transformGraph( node, context );

	conflictIds = (Map<?, ?>) context.get( TransformationContextKeys.CONFLICT_IDS );
	}

	@SuppressWarnings( "unchecked" )
	Map<String, Object> stats = (Map<String, Object>) context.get( TransformationContextKeys.STATS );
	long time1 = System.nanoTime();

	Map<Object, ConflictId> ids = new LinkedHashMap<Object, ConflictId>( 256 );

	{
	ConflictId id = null;
	Object key = conflictIds.get( node );
	if ( key != null )
	{
	id = new ConflictId( key, 0 );
	ids.put( key, id );
	}

	Map<DependencyNode, Object> visited = new IdentityHashMap<DependencyNode, Object>( conflictIds.size() );

	buildConflitIdDAG( ids, node, id, 0, visited, conflictIds );
	}

	long time2 = System.nanoTime();

	int cycles = topsortConflictIds( ids.values(), context );

	if ( stats != null )
	{
	long time3 = System.nanoTime();
	stats.put( "ConflictIdSorter.graphTime", time2 - time1 );
	stats.put( "ConflictIdSorter.topsortTime", time3 - time2 );
	stats.put( "ConflictIdSorter.conflictIdCount", ids.size() );
	stats.put( "ConflictIdSorter.conflictIdCycleCount", cycles );
	}

	return node;
	}

	private void buildConflitIdDAG( Map<Object, ConflictId> ids, DependencyNode node, ConflictId id, int depth,
	Map<DependencyNode, Object> visited, Map<?, ?> conflictIds )
	{
	if ( visited.put( node, Boolean.TRUE ) != null )
	{
	return;
	}

	depth++;

	for ( DependencyNode child : node.getChildren() )
	{
	Object key = conflictIds.get( child );
	ConflictId childId = ids.get( key );
	if ( childId == null )
	{
	childId = new ConflictId( key, depth );
	ids.put( key, childId );
	}
	else
	{
	childId.pullup( depth );
	}

	if ( id != null )
	{
	id.add( childId );
	}

	buildConflitIdDAG( ids, child, childId, depth, visited, conflictIds );
	}
	}

	private int topsortConflictIds( Collection<ConflictId> conflictIds, DependencyGraphTransformationContext context )
	{
	List<Object> sorted = new ArrayList<Object>( conflictIds.size() );

	RootQueue roots = new RootQueue( conflictIds.size() / 2 );
	for ( ConflictId id : conflictIds )
	{
	if ( id.inDegree <= 0 )
	{
	roots.add( id );
	}
	}

	processRoots( sorted, roots );

	boolean cycle = sorted.size() < conflictIds.size();

	while ( sorted.size() < conflictIds.size() )
	{
	// cycle -> deal gracefully with nodes still having positive in-degree

	ConflictId nearest = null;
	for ( ConflictId id : conflictIds )
	{
	if ( id.inDegree <= 0 )
	{
	continue;
	}
	if ( nearest == null \|\| id.minDepth < nearest.minDepth
	\|\| ( id.minDepth == nearest.minDepth && id.inDegree < nearest.inDegree ) )
	{
	nearest = id;
	}
	}

	nearest.inDegree = 0;
	roots.add( nearest );

	processRoots( sorted, roots );
	}

	Collection<Collection<Object>> cycles = Collections.emptySet();
	if ( cycle )
	{
	cycles = findCycles( conflictIds );
	}

	context.put( TransformationContextKeys.SORTED_CONFLICT_IDS, sorted );
	context.put( TransformationContextKeys.CYCLIC_CONFLICT_IDS, cycles );

	return cycles.size();
	}

	private void processRoots( List<Object> sorted, RootQueue roots )
	{
	while ( !roots.isEmpty() )
	{
	ConflictId root = roots.remove();

	sorted.add( root.key );

	for ( ConflictId child : root.children )
	{
	child.inDegree--;
	if ( child.inDegree == 0 )
	{
	roots.add( child );
	}
	}
	}
	}

	private Collection<Collection<Object>> findCycles( Collection<ConflictId> conflictIds )
	{
	Collection<Collection<Object>> cycles = new HashSet<Collection<Object>>();

	Map<Object, Integer> stack = new HashMap<Object, Integer>( 128 );
	Map<ConflictId, Object> visited = new IdentityHashMap<ConflictId, Object>( conflictIds.size() );
	for ( ConflictId id : conflictIds )
	{
	findCycles( id, visited, stack, cycles );
	}

	return cycles;
	}

	private void findCycles( ConflictId id, Map<ConflictId, Object> visited, Map<Object, Integer> stack,
	Collection<Collection<Object>> cycles )
	{
	Integer depth = stack.put( id.key, stack.size() );
	if ( depth != null )
	{
	stack.put( id.key, depth );
	Collection<Object> cycle = new HashSet<Object>();
	for ( Map.Entry<Object, Integer> entry : stack.entrySet() )
	{
	if ( entry.getValue() >= depth )
	{
	cycle.add( entry.getKey() );
	}
	}
	cycles.add( cycle );
	}
	else
	{
	if ( visited.put( id, Boolean.TRUE ) == null )
	{
	for ( ConflictId childId : id.children )
	{
	findCycles( childId, visited, stack, cycles );
	}
	}
	stack.remove( id.key );
	}
	}

	static final class ConflictId
	{

	final Object key;

	Collection<ConflictId> children = Collections.emptySet();

	int inDegree;

	int minDepth;

	ConflictId( Object key, int depth )
	{
	this.key = key;
	this.minDepth = depth;
	}

	public void add( ConflictId child )
	{
	if ( children.isEmpty() )
	{
	children = new HashSet<ConflictId>();
	}
	if ( children.add( child ) )
	{
	child.inDegree++;
	}
	}

	public void pullup( int depth )
	{
	if ( depth < minDepth )
	{
	minDepth = depth;
	depth++;
	for ( ConflictId child : children )
	{
	child.pullup( depth );
	}
	}
	}

	@Override
	public boolean equals( Object obj )
	{
	if ( this == obj )
	{
	return true;
	}
	else if ( !( obj instanceof ConflictId ) )
	{
	return false;
	}
	ConflictId that = (ConflictId) obj;
	return this.key.equals( that.key );
	}

	@Override
	public int hashCode()
	{
	return key.hashCode();
	}

	@Override
	public String toString()
	{
	return key + " @ " + minDepth + " <" + inDegree;
	}

	}

	static final class RootQueue
	{

	private int nextOut;

	private int nextIn;

	private ConflictId[] ids;

	RootQueue( int capacity )
	{
	ids = new ConflictId[capacity + 16];
	}

	boolean isEmpty()
	{
	return nextOut >= nextIn;
	}

	void add( ConflictId id )
	{
	if ( nextOut >= nextIn && nextOut > 0 )
	{
	nextIn -= nextOut;
	nextOut = 0;
	}
	if ( nextIn >= ids.length )
	{
	ConflictId[] tmp = new ConflictId[ids.length + ids.length / 2 + 16];
	System.arraycopy( ids, nextOut, tmp, 0, nextIn - nextOut );
	ids = tmp;
	nextIn -= nextOut;
	nextOut = 0;
	}
	int i;
	for ( i = nextIn - 1; i >= nextOut && id.minDepth < ids[i].minDepth; i-- )
	{
	ids[i + 1] = ids[i];
	}
	ids[i + 1] = id;
	nextIn++;
	}

	ConflictId remove()
	{
	return ids[nextOut++];
	}

	}

	}