You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@maven.apache.org by GitBox <gi...@apache.org> on 2022/01/16 16:29:05 UTC
[GitHub] [maven-resolver] ibabiankou commented on a change in pull request #144: Use BFS approach
ibabiankou commented on a change in pull request #144:
URL: https://github.com/apache/maven-resolver/pull/144#discussion_r785445022
##########
File path: maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/collect/NodeQueue.java
##########
@@ -19,58 +19,53 @@
* under the License.
*/
-import java.util.Arrays;
-
import org.eclipse.aether.artifact.Artifact;
import org.eclipse.aether.graph.DependencyNode;
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Queue;
+
+
/**
* @see DefaultDependencyCollector
*/
-final class NodeStack
+final class NodeQueue
{
-
- @SuppressWarnings( {"unchecked", "checkstyle:magicnumber" } )
- // CHECKSTYLE_OFF: MagicNumber
- private DependencyNode[] nodes = new DependencyNode[96];
- // CHECKSTYLE_ON: MagicNumber
-
- private int size;
+ Queue<DependencyNode> queue = new ArrayDeque<>();
public DependencyNode top()
{
- if ( size <= 0 )
- {
- throw new IllegalStateException( "stack empty" );
- }
- return nodes[size - 1];
+ return queue.element();
}
public void push( DependencyNode node )
{
- if ( size >= nodes.length )
- {
- DependencyNode[] tmp = new DependencyNode[size + 64];
- System.arraycopy( nodes, 0, tmp, 0, nodes.length );
- nodes = tmp;
- }
- nodes[size++] = node;
+ queue.add( node );
}
- public void pop()
+ public DependencyNode remove()
{
- if ( size <= 0 )
- {
- throw new IllegalStateException( "stack empty" );
- }
- size--;
+ return queue.remove();
+ }
+
+ public DependencyNode poll()
Review comment:
Method seems to be unused.
##########
File path: maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/collect/DefaultDependencyCollector.java
##########
@@ -253,13 +253,28 @@ public CollectResult collectDependencies( RepositorySystemSession session, Colle
DefaultVersionFilterContext versionContext = new DefaultVersionFilterContext( session );
Args args = new Args( session, trace, pool, nodes, context, versionContext, request );
- Results results = new Results( result, session );
- process( args, results, dependencies, repositories,
- depSelector != null ? depSelector.deriveChildSelector( context ) : null,
- depManager != null ? depManager.deriveChildManager( context ) : null,
- depTraverser != null ? depTraverser.deriveChildTraverser( context ) : null,
- verFilter != null ? verFilter.deriveChildFilter( context ) : null );
+ DataPool.DependencyNodeTraceContext rootTraceContext =
+ new DataPool.DependencyNodeTraceContext(
+ depSelector != null ? depSelector.deriveChildSelector( context ) : null,
+ depManager != null ? depManager.deriveChildManager( context ) : null,
+ depTraverser != null ? depTraverser.deriveChildTraverser( context ) : null,
+ verFilter != null ? verFilter.deriveChildFilter( context ) : null, repositories,
+ dependencies,
+ managedDependencies, args.pool.getAllNodes( node ), traverse );
+ rootTraceContext.isRoot = true;
+ args.pool.putTraceContext( node, rootTraceContext );
+
+ Results results = new Results( result, session );
+ while ( !args.nodes.isEmpty() )
+ {
+ DependencyNode current = args.nodes.top();
+ if ( current != null )
+ {
+ processNode( args, results, current );
+ args.nodes.remove();
+ }
+ }
Review comment:
This `null` check seems to be redundant here. We never put `null` into the queue and `top()` would throw an exception if the queue is empty, which should never be the case according to the while loop.
```suggestion
while ( !args.nodes.isEmpty() )
{
processNode( args, results, args.nodes.remove() );
}
```
##########
File path: maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/collect/DefaultDependencyCollector.java
##########
@@ -343,36 +358,75 @@ private static String getId( Artifact a )
return a.getGroupId() + ':' + a.getArtifactId() + ':' + a.getClassifier() + ':' + a.getExtension();
}
+ private void processNode( Args args, Results results, DependencyNode current )
+ {
+ DataPool.DependencyNodeTraceContext traceContext = args.pool.getTraceContext( current );
+ if ( traceContext == null || !traceContext.recursive )
+ {
+ return;
+ }
+
+ DependencySelector selector = traceContext.depSelector;
+ DependencyManager manager = traceContext.depManager;
+ DependencyTraverser traverser = traceContext.depTraverser;
+ VersionFilter filter = traceContext.verFilter;
+
+ if ( traceContext.isRoot )
+ {
+ //Should not cache the children of root node just like original DFS solution
Review comment:
Let's try to figure out why this is important and add a comment explaining why it should not be cached (rather than referencing old logic that is not easily available). Otherwise, let's drop this part, I don't see how caching might harm here.
##########
File path: maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/collect/NodeQueue.java
##########
@@ -19,58 +19,53 @@
* under the License.
*/
-import java.util.Arrays;
-
import org.eclipse.aether.artifact.Artifact;
import org.eclipse.aether.graph.DependencyNode;
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Queue;
+
+
/**
* @see DefaultDependencyCollector
*/
-final class NodeStack
+final class NodeQueue
Review comment:
This class is merely a wrapper around the queue now and the `find` method has little to do with the queue.
I would move the find method to `DefaultDependencyCycle` (It also can be a static utility method) and delete this class in favor of using Queue directly.
##########
File path: maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/collect/DefaultDependencyCollector.java
##########
@@ -343,36 +358,75 @@ private static String getId( Artifact a )
return a.getGroupId() + ':' + a.getArtifactId() + ':' + a.getClassifier() + ':' + a.getExtension();
}
+ private void processNode( Args args, Results results, DependencyNode current )
+ {
+ DataPool.DependencyNodeTraceContext traceContext = args.pool.getTraceContext( current );
+ if ( traceContext == null || !traceContext.recursive )
+ {
+ return;
+ }
+
+ DependencySelector selector = traceContext.depSelector;
+ DependencyManager manager = traceContext.depManager;
+ DependencyTraverser traverser = traceContext.depTraverser;
+ VersionFilter filter = traceContext.verFilter;
+
+ if ( traceContext.isRoot )
+ {
+ //Should not cache the children of root node just like original DFS solution
+ process( args, results, traceContext );
+ return;
+ }
+
+ Object key =
+ args.pool.toKey( current.getArtifact(), traceContext.repositories, selector, manager, traverser,
+ filter );
+
+ if ( args.pool.getChildren( key ) != null )
+ {
+ current.setChildren( args.pool.getChildren( key ) );
+ }
+ else
+ {
+ process( args, results, traceContext );
+ args.pool.putChildren( key, current.getChildren() );
+ }
+ }
+
@SuppressWarnings( "checkstyle:parameternumber" )
- private void process( final Args args, Results results, List<Dependency> dependencies,
- List<RemoteRepository> repositories, DependencySelector depSelector,
- DependencyManager depManager, DependencyTraverser depTraverser, VersionFilter verFilter )
+ private void process( final Args args, Results results, DataPool.DependencyNodeTraceContext traceContext )
{
- for ( Dependency dependency : dependencies )
+
+ for ( Dependency dependency : traceContext.dependencies )
{
- processDependency( args, results, repositories, depSelector, depManager, depTraverser, verFilter,
- dependency );
+ processDependency( args, results, traceContext,
+ dependency );
Review comment:
nit: this should be on the same line now (same holds for a few other places).
```suggestion
processDependency( args, results, traceContext, dependency );
```
##########
File path: maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/collect/DataPool.java
##########
@@ -182,6 +187,89 @@ public void putChildren( Object key, List<DependencyNode> children )
nodes.put( key, children );
}
+ public DependencyNodeTraceContext getTraceContext( DependencyNode node )
+ {
+ return nodeTraceContexts.get( node );
+ }
+
+ public void putTraceContext( DependencyNode node, DependencyNodeTraceContext context )
+ {
+ nodeTraceContexts.put( node, context );
+ }
+
+ public void putParent( DependencyNode node, DependencyNode parent )
+ {
+ nodeParents.put( node, parent );
+ }
+
+
+ /**
+ * Get all parents of current node (including current node) following the top-down sequence (parent -> child)
+ *
+ * @return
+ */
+ public List<DependencyNode> getAllNodes( DependencyNode current )
+ {
+ return getAllNodes( current, true );
+ }
+
+ public List<DependencyNode> getAllNodes( DependencyNode current, boolean reverse )
+ {
+ List<DependencyNode> nodes = new ArrayList<>();
+ nodes.add( current );
+
+ DependencyNode parent = nodeParents.get( current );
+ while ( parent != null )
+ {
+ nodes.add( parent );
+ parent = nodeParents.get( parent );
+ }
+
+ if ( reverse )
+ {
+ Collections.reverse( nodes );
+ }
+ return nodes;
+ }
+
+ /**
+ * Trace the objects required for inheritance
+ */
+ static final class DependencyNodeTraceContext
+ {
+ DependencySelector depSelector;
+ DependencyManager depManager;
+ DependencyTraverser depTraverser;
+ VersionFilter verFilter;
+ List<RemoteRepository> repositories;
+ List<Dependency> dependencies;
+ List<Dependency> managedDependencies;
+ List<DependencyNode> allNodes;
+ boolean isRoot;
+ boolean recursive;
+
+ @SuppressWarnings( "checkstyle:parameternumber" )
+ DependencyNodeTraceContext( DependencySelector depSelector,
+ DependencyManager depManager,
+ DependencyTraverser depTraverser,
+ VersionFilter verFilter,
+ List<RemoteRepository> repositories,
+ List<Dependency> dependencies,
+ List<Dependency> managedDependencies, List<DependencyNode> allNodes,
+ boolean recursive )
Review comment:
It looks like this parameter is always `true`, therefore can be deleted.
##########
File path: maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/collect/DefaultDependencyCollector.java
##########
@@ -343,36 +358,75 @@ private static String getId( Artifact a )
return a.getGroupId() + ':' + a.getArtifactId() + ':' + a.getClassifier() + ':' + a.getExtension();
}
+ private void processNode( Args args, Results results, DependencyNode current )
+ {
+ DataPool.DependencyNodeTraceContext traceContext = args.pool.getTraceContext( current );
+ if ( traceContext == null || !traceContext.recursive )
+ {
+ return;
+ }
+
+ DependencySelector selector = traceContext.depSelector;
+ DependencyManager manager = traceContext.depManager;
+ DependencyTraverser traverser = traceContext.depTraverser;
+ VersionFilter filter = traceContext.verFilter;
+
+ if ( traceContext.isRoot )
+ {
+ //Should not cache the children of root node just like original DFS solution
+ process( args, results, traceContext );
+ return;
+ }
+
+ Object key =
+ args.pool.toKey( current.getArtifact(), traceContext.repositories, selector, manager, traverser,
+ filter );
+
+ if ( args.pool.getChildren( key ) != null )
+ {
+ current.setChildren( args.pool.getChildren( key ) );
+ }
+ else
+ {
+ process( args, results, traceContext );
+ args.pool.putChildren( key, current.getChildren() );
+ }
+ }
+
@SuppressWarnings( "checkstyle:parameternumber" )
- private void process( final Args args, Results results, List<Dependency> dependencies,
- List<RemoteRepository> repositories, DependencySelector depSelector,
- DependencyManager depManager, DependencyTraverser depTraverser, VersionFilter verFilter )
+ private void process( final Args args, Results results, DataPool.DependencyNodeTraceContext traceContext )
{
- for ( Dependency dependency : dependencies )
+
+ for ( Dependency dependency : traceContext.dependencies )
{
- processDependency( args, results, repositories, depSelector, depManager, depTraverser, verFilter,
- dependency );
+ processDependency( args, results, traceContext,
+ dependency );
}
}
@SuppressWarnings( "checkstyle:parameternumber" )
- private void processDependency( Args args, Results results, List<RemoteRepository> repositories,
- DependencySelector depSelector, DependencyManager depManager,
- DependencyTraverser depTraverser, VersionFilter verFilter, Dependency dependency )
+ private void processDependency( Args args, Results results, DataPool.DependencyNodeTraceContext traceContext,
+ Dependency dependency )
{
List<Artifact> relocations = Collections.emptyList();
- processDependency( args, results, repositories, depSelector, depManager, depTraverser, verFilter, dependency,
- relocations, false );
+ boolean disableVersionManagement = false;
+ processDependency( args, results, traceContext, dependency,
+ relocations, disableVersionManagement );
Review comment:
`disableVersionManagement` was inlined in the previous commit, why change it back?
The method itself is used in one place only, I would drop it entirely.
##########
File path: maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/collect/DataPool.java
##########
@@ -71,6 +72,10 @@
private final Map<Object, List<DependencyNode>> nodes = new HashMap<>( 256 );
+ private Map<DependencyNode, DependencyNodeTraceContext> nodeTraceContexts = new HashMap<>( 256 );
+
+ private Map<DependencyNode, DependencyNode> nodeParents = new HashMap<>( 256 );
+
Review comment:
It looks like we can avoid having these two maps:
1. `nodeTraceContexts` : Trace context already has the dependency node in it, so by keeping these contexts in the queue instead of the nodes we can drop this map.
2. `nodeParents` : The context already has all the parents of the node, so if we merely add there the node of the next level, we can drop this map.
##########
File path: maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/collect/DefaultDependencyCollector.java
##########
@@ -343,36 +358,75 @@ private static String getId( Artifact a )
return a.getGroupId() + ':' + a.getArtifactId() + ':' + a.getClassifier() + ':' + a.getExtension();
}
+ private void processNode( Args args, Results results, DependencyNode current )
+ {
+ DataPool.DependencyNodeTraceContext traceContext = args.pool.getTraceContext( current );
+ if ( traceContext == null || !traceContext.recursive )
+ {
+ return;
+ }
Review comment:
IIUC this can not happen.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org