This is an automated email from the ASF dual-hosted git repository. cstamas pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/maven-resolver.git
The following commit(s) were added to refs/heads/master by this push: new 6bc4c211 [MRESOLVER-390] Customize graph visiting strategy (#322) 6bc4c211 is described below commit 6bc4c2115e2843e9bb64d1487b3efcb3401abd0c Author: Tamas Cservenak <ta...@cservenak.net> AuthorDate: Sat Oct 14 01:50:37 2023 +0200 [MRESOLVER-390] Customize graph visiting strategy (#322) Resolver (and thus Maven) had "wired in" strategy to flatten dependency graph into list, and it was always "preOrder", while there existed alternate solutions like "postOrder". This PR introduces "levelOrder" as asked by users, and also makes it configurable (via session config) which strategy should be used, and exposes helper classes and methods. This PR introduces new visitors that are able to perform the 3 visiting strategies and uses them, while the old ones are left in place (for binary compatibility) but are NOT used in Resolver and their use is discouraged. Now session can be configured to use following strategies to flatten the graph: * "preOrder" -- as before * "postOrder" -- was already present, but unused (unless some code used it directly) * "levelOrder" -- as asked by users, artifact list is ordered by their depth (distance from root) By default, this PR introduces NO behavior changes, but opens configuration that does allow to alter these. --- https://issues.apache.org/jira/browse/MRESOLVER-390 --- .../eclipse/aether/ConfigurationProperties.java | 17 +++ .../java/org/eclipse/aether/RepositorySystem.java | 12 ++ .../aether/resolution/DependencyResult.java | 29 ++++ .../maven/resolver/examples/resolver/Resolver.java | 7 +- .../internal/impl/DefaultRepositorySystem.java | 58 +++++++- .../AbstractDependencyNodeConsumerVisitor.java | 60 ++++++++ .../AbstractDepthFirstNodeListGenerator.java | 70 ++-------- .../util/graph/visitor/DependencyGraphDumper.java | 4 +- ...> LevelOrderDependencyNodeConsumerVisitor.java} | 38 ++++-- ...deListGenerator.java => NodeListGenerator.java} | 152 ++++++++++----------- ...=> PostorderDependencyNodeConsumerVisitor.java} | 26 ++-- .../graph/visitor/PostorderNodeListGenerator.java | 9 +- .../PreorderDependencyNodeConsumerVisitor.java | 41 +++--- .../graph/visitor/PreorderNodeListGenerator.java | 7 + .../util/graph/visitor/NodeListGeneratorTest.java | 113 +++++++++++++++ src/site/markdown/configuration.md | 1 + 16 files changed, 452 insertions(+), 192 deletions(-) diff --git a/maven-resolver-api/src/main/java/org/eclipse/aether/ConfigurationProperties.java b/maven-resolver-api/src/main/java/org/eclipse/aether/ConfigurationProperties.java index a5519514..c117c1d5 100644 --- a/maven-resolver-api/src/main/java/org/eclipse/aether/ConfigurationProperties.java +++ b/maven-resolver-api/src/main/java/org/eclipse/aether/ConfigurationProperties.java @@ -296,6 +296,23 @@ public final class ConfigurationProperties { */ public static final boolean DEFAULT_PERSISTED_CHECKSUMS = true; + /** + * A flag indicating which visitor should be used to "flatten" the dependency graph into list. Default is + * same as in older resolver versions "preOrder", while it can accept values like "postOrder" and "levelOrder". + * + * @see #DEFAULT_REPOSITORY_SYSTEM_RESOLVER_DEPENDENCIES_VISITOR + * @since TBD + */ + public static final String REPOSITORY_SYSTEM_RESOLVER_DEPENDENCIES_VISITOR = + PREFIX_AETHER + "system.resolveDependencies.visitor"; + + /** + * The default visitor strategy "preOrder". + * + * @since TBD + */ + public static final String DEFAULT_REPOSITORY_SYSTEM_RESOLVER_DEPENDENCIES_VISITOR = "preOrder"; + private ConfigurationProperties() { // hide constructor } diff --git a/maven-resolver-api/src/main/java/org/eclipse/aether/RepositorySystem.java b/maven-resolver-api/src/main/java/org/eclipse/aether/RepositorySystem.java index 61a612e2..a9d50765 100644 --- a/maven-resolver-api/src/main/java/org/eclipse/aether/RepositorySystem.java +++ b/maven-resolver-api/src/main/java/org/eclipse/aether/RepositorySystem.java @@ -28,6 +28,7 @@ import org.eclipse.aether.collection.DependencyCollectionException; import org.eclipse.aether.deployment.DeployRequest; import org.eclipse.aether.deployment.DeployResult; import org.eclipse.aether.deployment.DeploymentException; +import org.eclipse.aether.graph.DependencyNode; import org.eclipse.aether.installation.InstallRequest; import org.eclipse.aether.installation.InstallResult; import org.eclipse.aether.installation.InstallationException; @@ -145,6 +146,17 @@ public interface RepositorySystem { DependencyResult resolveDependencies(RepositorySystemSession session, DependencyRequest request) throws DependencyResolutionException; + /** + * Flattens the provided graph as {@link DependencyNode} into a {@link List<DependencyNode>} according to session + * configuration. + * + * @param session The repository session, must not be {@code null}. + * @param root The dependency node root of the graph, must not be {@code null}. + * @return The flattened list of dependency nodes, never {@code null}. + * @since TBD + */ + List<DependencyNode> flattenDependencyNodes(RepositorySystemSession session, DependencyNode root); + /** * Resolves the path for an artifact. The artifact will be downloaded to the local repository if necessary. An * artifact that is already resolved will be skipped and is not re-resolved. In general, callers must not assume any diff --git a/maven-resolver-api/src/main/java/org/eclipse/aether/resolution/DependencyResult.java b/maven-resolver-api/src/main/java/org/eclipse/aether/resolution/DependencyResult.java index 500c5b5e..be9f21e6 100644 --- a/maven-resolver-api/src/main/java/org/eclipse/aether/resolution/DependencyResult.java +++ b/maven-resolver-api/src/main/java/org/eclipse/aether/resolution/DependencyResult.java @@ -42,6 +42,8 @@ public final class DependencyResult { private List<Exception> collectExceptions; + private List<DependencyNode> dependencyNodeResults; + private List<ArtifactResult> artifactResults; /** @@ -54,6 +56,7 @@ public final class DependencyResult { root = request.getRoot(); cycles = Collections.emptyList(); collectExceptions = Collections.emptyList(); + this.dependencyNodeResults = Collections.emptyList(); artifactResults = Collections.emptyList(); } @@ -138,6 +141,32 @@ public final class DependencyResult { return this; } + /** + * Gets the resolution results for the dependency nodes that matched {@link DependencyRequest#getFilter()}. + * + * @return The resolution results for the dependency nodes, never {@code null}. + * @since TBD + */ + public List<DependencyNode> getDependencyNodeResults() { + return dependencyNodeResults; + } + + /** + * Sets the resolution results for the dependency nodes that matched {@link DependencyRequest#getFilter()}. + * + * @param results The resolution results for the dependency nodes, may be {@code null}. + * @return This result for chaining, never {@code null}. + * @since TBD + */ + public DependencyResult setDependencyNodeResults(List<DependencyNode> results) { + if (results == null) { + this.dependencyNodeResults = Collections.emptyList(); + } else { + this.dependencyNodeResults = results; + } + return this; + } + /** * Gets the resolution results for the dependency artifacts that matched {@link DependencyRequest#getFilter()}. * diff --git a/maven-resolver-demos/maven-resolver-demo-snippets/src/main/java/org/apache/maven/resolver/examples/resolver/Resolver.java b/maven-resolver-demos/maven-resolver-demo-snippets/src/main/java/org/apache/maven/resolver/examples/resolver/Resolver.java index bf1d3795..d5438872 100644 --- a/maven-resolver-demos/maven-resolver-demo-snippets/src/main/java/org/apache/maven/resolver/examples/resolver/Resolver.java +++ b/maven-resolver-demos/maven-resolver-demo-snippets/src/main/java/org/apache/maven/resolver/examples/resolver/Resolver.java @@ -42,7 +42,8 @@ import org.eclipse.aether.repository.RemoteRepository; import org.eclipse.aether.resolution.DependencyRequest; import org.eclipse.aether.resolution.DependencyResolutionException; import org.eclipse.aether.util.graph.visitor.DependencyGraphDumper; -import org.eclipse.aether.util.graph.visitor.PreorderNodeListGenerator; +import org.eclipse.aether.util.graph.visitor.NodeListGenerator; +import org.eclipse.aether.util.graph.visitor.PreorderDependencyNodeConsumerVisitor; import org.eclipse.aether.util.repository.AuthenticationBuilder; /** @@ -89,8 +90,8 @@ public class Resolver { System.out.println("Tree:"); System.out.println(dump); - PreorderNodeListGenerator nlg = new PreorderNodeListGenerator(); - rootNode.accept(nlg); + NodeListGenerator nlg = new NodeListGenerator(); + rootNode.accept(new PreorderDependencyNodeConsumerVisitor(nlg)); return new ResolverResult(rootNode, nlg.getFiles(), nlg.getClassPath()); } diff --git a/maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/DefaultRepositorySystem.java b/maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/DefaultRepositorySystem.java index d2ba9e0a..5ca614f5 100644 --- a/maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/DefaultRepositorySystem.java +++ b/maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/DefaultRepositorySystem.java @@ -25,8 +25,12 @@ import javax.inject.Singleton; import java.util.ArrayList; import java.util.Collection; import java.util.List; +import java.util.Objects; import java.util.concurrent.atomic.AtomicBoolean; +import java.util.function.Consumer; +import java.util.stream.Collectors; +import org.eclipse.aether.ConfigurationProperties; import org.eclipse.aether.RepositorySystem; import org.eclipse.aether.RepositorySystemSession; import org.eclipse.aether.RequestTrace; @@ -39,6 +43,7 @@ import org.eclipse.aether.deployment.DeployRequest; import org.eclipse.aether.deployment.DeployResult; import org.eclipse.aether.deployment.DeploymentException; import org.eclipse.aether.graph.DependencyFilter; +import org.eclipse.aether.graph.DependencyNode; import org.eclipse.aether.graph.DependencyVisitor; import org.eclipse.aether.impl.ArtifactDescriptorReader; import org.eclipse.aether.impl.ArtifactResolver; @@ -80,8 +85,11 @@ import org.eclipse.aether.resolution.VersionResult; import org.eclipse.aether.spi.locator.Service; import org.eclipse.aether.spi.locator.ServiceLocator; import org.eclipse.aether.spi.synccontext.SyncContextFactory; +import org.eclipse.aether.util.ConfigUtils; import org.eclipse.aether.util.graph.visitor.FilteringDependencyVisitor; -import org.eclipse.aether.util.graph.visitor.TreeDependencyVisitor; +import org.eclipse.aether.util.graph.visitor.LevelOrderDependencyNodeConsumerVisitor; +import org.eclipse.aether.util.graph.visitor.PostorderDependencyNodeConsumerVisitor; +import org.eclipse.aether.util.graph.visitor.PreorderDependencyNodeConsumerVisitor; import static java.util.Objects.requireNonNull; @@ -337,17 +345,26 @@ public class DefaultRepositorySystem implements RepositorySystem, Service { throw new NullPointerException("dependency node and collect request cannot be null"); } - ArtifactRequestBuilder builder = new ArtifactRequestBuilder(trace); + final ArrayList<DependencyNode> dependencyNodes = new ArrayList<>(); + DependencyVisitor builder = getDependencyVisitor(session, dependencyNodes::add); DependencyFilter filter = request.getFilter(); DependencyVisitor visitor = (filter != null) ? new FilteringDependencyVisitor(builder, filter) : builder; - visitor = new TreeDependencyVisitor(visitor); - if (result.getRoot() != null) { result.getRoot().accept(visitor); } - List<ArtifactRequest> requests = builder.getRequests(); - + final List<ArtifactRequest> requests = dependencyNodes.stream() + .map(n -> { + if (n.getDependency() != null) { + ArtifactRequest artifactRequest = new ArtifactRequest(n); + artifactRequest.setTrace(trace); + return artifactRequest; + } else { + return null; + } + }) + .filter(Objects::nonNull) + .collect(Collectors.toList()); List<ArtifactResult> results; try { results = artifactResolver.resolveArtifacts(session, requests); @@ -355,6 +372,7 @@ public class DefaultRepositorySystem implements RepositorySystem, Service { are = e; results = e.getResults(); } + result.setDependencyNodeResults(dependencyNodes); result.setArtifactResults(results); updateNodesWithResolvedArtifacts(results); @@ -368,6 +386,34 @@ public class DefaultRepositorySystem implements RepositorySystem, Service { return result; } + @Override + public List<DependencyNode> flattenDependencyNodes(RepositorySystemSession session, DependencyNode root) { + validateSession(session); + requireNonNull(root, "root cannot be null"); + + final ArrayList<DependencyNode> dependencyNodes = new ArrayList<>(); + root.accept(getDependencyVisitor(session, dependencyNodes::add)); + return dependencyNodes; + } + + private DependencyVisitor getDependencyVisitor( + RepositorySystemSession session, Consumer<DependencyNode> nodeConsumer) { + String strategy = ConfigUtils.getString( + session, + ConfigurationProperties.DEFAULT_REPOSITORY_SYSTEM_RESOLVER_DEPENDENCIES_VISITOR, + ConfigurationProperties.REPOSITORY_SYSTEM_RESOLVER_DEPENDENCIES_VISITOR); + switch (strategy) { + case PreorderDependencyNodeConsumerVisitor.NAME: + return new PreorderDependencyNodeConsumerVisitor(nodeConsumer); + case PostorderDependencyNodeConsumerVisitor.NAME: + return new PostorderDependencyNodeConsumerVisitor(nodeConsumer); + case LevelOrderDependencyNodeConsumerVisitor.NAME: + return new LevelOrderDependencyNodeConsumerVisitor(nodeConsumer); + default: + throw new IllegalArgumentException("Invalid dependency visitor strategy: " + strategy); + } + } + private void updateNodesWithResolvedArtifacts(List<ArtifactResult> results) { for (ArtifactResult result : results) { Artifact artifact = result.getArtifact(); diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDependencyNodeConsumerVisitor.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDependencyNodeConsumerVisitor.java new file mode 100644 index 00000000..c9828ea6 --- /dev/null +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDependencyNodeConsumerVisitor.java @@ -0,0 +1,60 @@ +/* + * 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. + */ +package org.eclipse.aether.util.graph.visitor; + +import java.util.IdentityHashMap; +import java.util.Map; +import java.util.function.Consumer; + +import org.eclipse.aether.graph.DependencyNode; +import org.eclipse.aether.graph.DependencyVisitor; + +import static java.util.Objects.requireNonNull; + +/** + * Abstract base class for dependency tree traverses that feed {@link Consumer<DependencyNode>}. + * + * @since TBD + */ +abstract class AbstractDependencyNodeConsumerVisitor implements DependencyVisitor { + protected final Consumer<DependencyNode> nodeConsumer; + + private final Map<DependencyNode, Object> visitedNodes; + + protected AbstractDependencyNodeConsumerVisitor(Consumer<DependencyNode> nodeConsumer) { + this.nodeConsumer = requireNonNull(nodeConsumer); + this.visitedNodes = new IdentityHashMap<>(512); + } + + /** + * Marks the specified node as being visited and determines whether the node has been visited before. + * + * @param node The node being visited, must not be {@code null}. + * @return {@code true} if the node has not been visited before, {@code false} if the node was already visited. + */ + protected boolean setVisited(DependencyNode node) { + return visitedNodes.put(node, Boolean.TRUE) == null; + } + + @Override + public abstract boolean visitEnter(DependencyNode node); + + @Override + public abstract boolean visitLeave(DependencyNode node); +} diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDepthFirstNodeListGenerator.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDepthFirstNodeListGenerator.java index 6293dda0..6a74994a 100644 --- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDepthFirstNodeListGenerator.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDepthFirstNodeListGenerator.java @@ -21,7 +21,6 @@ package org.eclipse.aether.util.graph.visitor; import java.io.File; import java.util.ArrayList; import java.util.IdentityHashMap; -import java.util.Iterator; import java.util.List; import java.util.Map; @@ -31,13 +30,22 @@ import org.eclipse.aether.graph.DependencyNode; import org.eclipse.aether.graph.DependencyVisitor; /** - * Abstract base class for depth first dependency tree traversers. Subclasses of this visitor will visit each node + * Abstract base class for depth first dependency tree traverses. Subclasses of this visitor will visit each node * exactly once regardless how many paths within the dependency graph lead to the node such that the resulting node * sequence is free of duplicates. * <p> * Actual vertex ordering (preorder, inorder, postorder) needs to be defined by subclasses through appropriate * implementations for {@link #visitEnter(org.eclipse.aether.graph.DependencyNode)} and - * {@link #visitLeave(org.eclipse.aether.graph.DependencyNode)} + * {@link #visitLeave(org.eclipse.aether.graph.DependencyNode)}. + * <p> + * Note: inorder vertex ordering is not provided out of the box, as resolver cannot partition (or does not know how to + * partition) the node children into "left" and "right" partitions. + * <p> + * The newer classes {@link AbstractDependencyNodeConsumerVisitor} and {@link NodeListGenerator} offer + * similar capabilities but are pluggable. Use of this class, while not deprecated, is discouraged. This class + * is not used in Resolver and is kept only for backward compatibility reasons. + * + * @see AbstractDependencyNodeConsumerVisitor */ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor { @@ -66,18 +74,7 @@ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor * @return The list of dependencies, never {@code null}. */ public List<Dependency> getDependencies(boolean includeUnresolved) { - List<Dependency> dependencies = new ArrayList<>(getNodes().size()); - - for (DependencyNode node : getNodes()) { - Dependency dependency = node.getDependency(); - if (dependency != null) { - if (includeUnresolved || dependency.getArtifact().getFile() != null) { - dependencies.add(dependency); - } - } - } - - return dependencies; + return NodeListGenerator.getDependencies(getNodes(), includeUnresolved); } /** @@ -87,18 +84,7 @@ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor * @return The list of artifacts, never {@code null}. */ public List<Artifact> getArtifacts(boolean includeUnresolved) { - List<Artifact> artifacts = new ArrayList<>(getNodes().size()); - - for (DependencyNode node : getNodes()) { - if (node.getDependency() != null) { - Artifact artifact = node.getDependency().getArtifact(); - if (includeUnresolved || artifact.getFile() != null) { - artifacts.add(artifact); - } - } - } - - return artifacts; + return NodeListGenerator.getArtifacts(getNodes(), includeUnresolved); } /** @@ -107,18 +93,7 @@ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor * @return The list of artifact files, never {@code null}. */ public List<File> getFiles() { - List<File> files = new ArrayList<>(getNodes().size()); - - for (DependencyNode node : getNodes()) { - if (node.getDependency() != null) { - File file = node.getDependency().getArtifact().getFile(); - if (file != null) { - files.add(file); - } - } - } - - return files; + return NodeListGenerator.getFiles(getNodes()); } /** @@ -128,22 +103,7 @@ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor * @return The class path, using the platform-specific path separator, never {@code null}. */ public String getClassPath() { - StringBuilder buffer = new StringBuilder(1024); - - for (Iterator<DependencyNode> it = getNodes().iterator(); it.hasNext(); ) { - DependencyNode node = it.next(); - if (node.getDependency() != null) { - Artifact artifact = node.getDependency().getArtifact(); - if (artifact.getFile() != null) { - buffer.append(artifact.getFile().getAbsolutePath()); - if (it.hasNext()) { - buffer.append(File.pathSeparatorChar); - } - } - } - } - - return buffer.toString(); + return NodeListGenerator.getClassPath(getNodes()); } /** diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/DependencyGraphDumper.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/DependencyGraphDumper.java index 60a12727..e3d4e8ee 100644 --- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/DependencyGraphDumper.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/DependencyGraphDumper.java @@ -69,7 +69,7 @@ public class DependencyGraphDumper implements DependencyVisitor { Artifact a = node.getArtifact(); Dependency d = node.getDependency(); buffer.append(a); - if (d != null && d.getScope().length() > 0) { + if (d != null && !d.getScope().isEmpty()) { buffer.append(" [").append(d.getScope()); if (d.isOptional()) { buffer.append(", optional"); @@ -82,7 +82,7 @@ public class DependencyGraphDumper implements DependencyVisitor { } premanaged = DependencyManagerUtils.getPremanagedScope(node); - if (premanaged != null && !premanaged.equals(d.getScope())) { + if (premanaged != null && d != null && !premanaged.equals(d.getScope())) { buffer.append(" (scope managed from ").append(premanaged).append(")"); } DependencyNode winner = (DependencyNode) node.getData().get(ConflictResolver.NODE_DATA_WINNER); diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/LevelOrderDependencyNodeConsumerVisitor.java similarity index 55% copy from maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java copy to maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/LevelOrderDependencyNodeConsumerVisitor.java index 09dad67c..697b0072 100644 --- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/LevelOrderDependencyNodeConsumerVisitor.java @@ -18,45 +18,57 @@ */ package org.eclipse.aether.util.graph.visitor; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.function.Consumer; + import org.eclipse.aether.graph.DependencyNode; /** - * Generates a sequence of dependency nodes from a dependeny graph by traversing the graph in postorder. This visitor - * visits each node exactly once regardless how many paths within the dependency graph lead to the node such that the - * resulting node sequence is free of duplicates. + * Processes dependency graph by traversing the graph in level order. This visitor visits each node exactly once + * regardless how many paths within the dependency graph lead to the node such that the resulting node sequence is + * free of duplicates. + * + * @since TBD */ -public final class PostorderNodeListGenerator extends AbstractDepthFirstNodeListGenerator { +public final class LevelOrderDependencyNodeConsumerVisitor extends AbstractDependencyNodeConsumerVisitor { + + public static final String NAME = "levelOrder"; + + private final HashMap<Integer, ArrayList<DependencyNode>> nodesPerLevel; private final Stack<Boolean> visits; /** - * Creates a new postorder list generator. + * Creates a new level order list generator. */ - public PostorderNodeListGenerator() { + public LevelOrderDependencyNodeConsumerVisitor(Consumer<DependencyNode> nodeConsumer) { + super(nodeConsumer); + nodesPerLevel = new HashMap<>(16); visits = new Stack<>(); } @Override public boolean visitEnter(DependencyNode node) { boolean visited = !setVisited(node); - visits.push(visited); - + if (!visited) { + nodesPerLevel.computeIfAbsent(visits.size(), k -> new ArrayList<>()).add(node); + } return !visited; } @Override public boolean visitLeave(DependencyNode node) { Boolean visited = visits.pop(); - if (visited) { return true; } - - if (node.getDependency() != null) { - nodes.add(node); + if (visits.isEmpty()) { + for (int l = 1; nodesPerLevel.containsKey(l); l++) { + nodesPerLevel.get(l).forEach(nodeConsumer); + } } - return true; } } diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDepthFirstNodeListGenerator.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/NodeListGenerator.java similarity index 51% copy from maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDepthFirstNodeListGenerator.java copy to maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/NodeListGenerator.java index 6293dda0..9bbe533f 100644 --- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/AbstractDepthFirstNodeListGenerator.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/NodeListGenerator.java @@ -20,34 +20,33 @@ package org.eclipse.aether.util.graph.visitor; import java.io.File; import java.util.ArrayList; -import java.util.IdentityHashMap; import java.util.Iterator; import java.util.List; -import java.util.Map; +import java.util.function.Consumer; import org.eclipse.aether.artifact.Artifact; import org.eclipse.aether.graph.Dependency; import org.eclipse.aether.graph.DependencyNode; -import org.eclipse.aether.graph.DependencyVisitor; + +import static java.util.stream.Collectors.toList; /** - * Abstract base class for depth first dependency tree traversers. Subclasses of this visitor will visit each node - * exactly once regardless how many paths within the dependency graph lead to the node such that the resulting node - * sequence is free of duplicates. - * <p> - * Actual vertex ordering (preorder, inorder, postorder) needs to be defined by subclasses through appropriate - * implementations for {@link #visitEnter(org.eclipse.aether.graph.DependencyNode)} and - * {@link #visitLeave(org.eclipse.aether.graph.DependencyNode)} + * Node list generator usable with different traversing strategies. It is wrapped {@link List<DependencyNode>} but + * offers several transformations, that are handy. + * + * @since TBD */ -abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor { +public final class NodeListGenerator implements Consumer<DependencyNode> { - private final Map<DependencyNode, Object> visitedNodes; + private final ArrayList<DependencyNode> nodes; - protected final List<DependencyNode> nodes; - - AbstractDepthFirstNodeListGenerator() { + public NodeListGenerator() { nodes = new ArrayList<>(128); - visitedNodes = new IdentityHashMap<>(512); + } + + @Override + public void accept(DependencyNode dependencyNode) { + nodes.add(dependencyNode); } /** @@ -59,6 +58,16 @@ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor return nodes; } + /** + * Gets the list of dependency nodes that was generated during the graph traversal and have {@code non-null} + * {@link DependencyNode#getDependency()}. + * + * @return The list of dependency nodes having dependency, never {@code null}. + */ + public List<DependencyNode> getNodesWithDependencies() { + return getNodesWithDependencies(getNodes()); + } + /** * Gets the dependencies seen during the graph traversal. * @@ -66,18 +75,7 @@ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor * @return The list of dependencies, never {@code null}. */ public List<Dependency> getDependencies(boolean includeUnresolved) { - List<Dependency> dependencies = new ArrayList<>(getNodes().size()); - - for (DependencyNode node : getNodes()) { - Dependency dependency = node.getDependency(); - if (dependency != null) { - if (includeUnresolved || dependency.getArtifact().getFile() != null) { - dependencies.add(dependency); - } - } - } - - return dependencies; + return getDependencies(getNodes(), includeUnresolved); } /** @@ -87,18 +85,7 @@ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor * @return The list of artifacts, never {@code null}. */ public List<Artifact> getArtifacts(boolean includeUnresolved) { - List<Artifact> artifacts = new ArrayList<>(getNodes().size()); - - for (DependencyNode node : getNodes()) { - if (node.getDependency() != null) { - Artifact artifact = node.getDependency().getArtifact(); - if (includeUnresolved || artifact.getFile() != null) { - artifacts.add(artifact); - } - } - } - - return artifacts; + return getArtifacts(getNodes(), includeUnresolved); } /** @@ -107,18 +94,7 @@ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor * @return The list of artifact files, never {@code null}. */ public List<File> getFiles() { - List<File> files = new ArrayList<>(getNodes().size()); - - for (DependencyNode node : getNodes()) { - if (node.getDependency() != null) { - File file = node.getDependency().getArtifact().getFile(); - if (file != null) { - files.add(file); - } - } - } - - return files; + return getFiles(getNodes()); } /** @@ -128,37 +104,59 @@ abstract class AbstractDepthFirstNodeListGenerator implements DependencyVisitor * @return The class path, using the platform-specific path separator, never {@code null}. */ public String getClassPath() { - StringBuilder buffer = new StringBuilder(1024); + return getClassPath(getNodes()); + } - for (Iterator<DependencyNode> it = getNodes().iterator(); it.hasNext(); ) { - DependencyNode node = it.next(); - if (node.getDependency() != null) { - Artifact artifact = node.getDependency().getArtifact(); - if (artifact.getFile() != null) { - buffer.append(artifact.getFile().getAbsolutePath()); - if (it.hasNext()) { - buffer.append(File.pathSeparatorChar); - } - } + static List<DependencyNode> getNodesWithDependencies(List<DependencyNode> nodes) { + return nodes.stream().filter(d -> d.getDependency() != null).collect(toList()); + } + + static List<Dependency> getDependencies(List<DependencyNode> nodes, boolean includeUnresolved) { + List<Dependency> dependencies = new ArrayList<>(nodes.size()); + for (DependencyNode node : getNodesWithDependencies(nodes)) { + Dependency dependency = node.getDependency(); + if (includeUnresolved || dependency.getArtifact().getFile() != null) { + dependencies.add(dependency); } } - - return buffer.toString(); + return dependencies; } - /** - * Marks the specified node as being visited and determines whether the node has been visited before. - * - * @param node The node being visited, must not be {@code null}. - * @return {@code true} if the node has not been visited before, {@code false} if the node was already visited. - */ - protected boolean setVisited(DependencyNode node) { - return visitedNodes.put(node, Boolean.TRUE) == null; + static List<Artifact> getArtifacts(List<DependencyNode> nodes, boolean includeUnresolved) { + List<Artifact> artifacts = new ArrayList<>(nodes.size()); + for (DependencyNode node : getNodesWithDependencies(nodes)) { + Artifact artifact = node.getDependency().getArtifact(); + if (includeUnresolved || artifact.getFile() != null) { + artifacts.add(artifact); + } + } + + return artifacts; } - @Override - public abstract boolean visitEnter(DependencyNode node); + static List<File> getFiles(List<DependencyNode> nodes) { + List<File> files = new ArrayList<>(nodes.size()); + for (DependencyNode node : getNodesWithDependencies(nodes)) { + File file = node.getDependency().getArtifact().getFile(); + if (file != null) { + files.add(file); + } + } + return files; + } - @Override - public abstract boolean visitLeave(DependencyNode node); + static String getClassPath(List<DependencyNode> nodes) { + StringBuilder buffer = new StringBuilder(1024); + for (Iterator<DependencyNode> it = getNodesWithDependencies(nodes).iterator(); it.hasNext(); ) { + DependencyNode node = it.next(); + Artifact artifact = node.getDependency().getArtifact(); + if (artifact.getFile() != null) { + buffer.append(artifact.getFile().getAbsolutePath()); + if (it.hasNext()) { + buffer.append(File.pathSeparatorChar); + } + } + } + return buffer.toString(); + } } diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderDependencyNodeConsumerVisitor.java similarity index 69% copy from maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java copy to maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderDependencyNodeConsumerVisitor.java index 09dad67c..7919a649 100644 --- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderDependencyNodeConsumerVisitor.java @@ -18,45 +18,45 @@ */ package org.eclipse.aether.util.graph.visitor; +import java.util.function.Consumer; + import org.eclipse.aether.graph.DependencyNode; /** - * Generates a sequence of dependency nodes from a dependeny graph by traversing the graph in postorder. This visitor - * visits each node exactly once regardless how many paths within the dependency graph lead to the node such that the - * resulting node sequence is free of duplicates. + * Processes dependency graph by traversing the graph in postorder. This visitor visits each node exactly once + * regardless how many paths within the dependency graph lead to the node such that the resulting node sequence is + * free of duplicates. + * + * @since TBD */ -public final class PostorderNodeListGenerator extends AbstractDepthFirstNodeListGenerator { +public final class PostorderDependencyNodeConsumerVisitor extends AbstractDependencyNodeConsumerVisitor { + + public static final String NAME = "postOrder"; private final Stack<Boolean> visits; /** * Creates a new postorder list generator. */ - public PostorderNodeListGenerator() { + public PostorderDependencyNodeConsumerVisitor(Consumer<DependencyNode> nodeConsumer) { + super(nodeConsumer); visits = new Stack<>(); } @Override public boolean visitEnter(DependencyNode node) { boolean visited = !setVisited(node); - visits.push(visited); - return !visited; } @Override public boolean visitLeave(DependencyNode node) { Boolean visited = visits.pop(); - if (visited) { return true; } - - if (node.getDependency() != null) { - nodes.add(node); - } - + nodeConsumer.accept(node); return true; } } diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java index 09dad67c..c910d4ec 100644 --- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PostorderNodeListGenerator.java @@ -21,9 +21,16 @@ package org.eclipse.aether.util.graph.visitor; import org.eclipse.aether.graph.DependencyNode; /** - * Generates a sequence of dependency nodes from a dependeny graph by traversing the graph in postorder. This visitor + * Generates a sequence of dependency nodes from a dependency graph by traversing the graph in postorder. This visitor * visits each node exactly once regardless how many paths within the dependency graph lead to the node such that the * resulting node sequence is free of duplicates. + * <p> + * The newer classes {@link AbstractDependencyNodeConsumerVisitor} and {@link NodeListGenerator} offer + * similar capabilities but are pluggable. Use of this class, while not deprecated, is discouraged. This class + * is not used in Resolver and is kept only for backward compatibility reasons. + * + * @see PostorderDependencyNodeConsumerVisitor + * @see NodeListGenerator */ public final class PostorderNodeListGenerator extends AbstractDepthFirstNodeListGenerator { diff --git a/maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/ArtifactRequestBuilder.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PreorderDependencyNodeConsumerVisitor.java similarity index 56% rename from maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/ArtifactRequestBuilder.java rename to maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PreorderDependencyNodeConsumerVisitor.java index e0e4d4b0..a5f364c8 100644 --- a/maven-resolver-impl/src/main/java/org/eclipse/aether/internal/impl/ArtifactRequestBuilder.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PreorderDependencyNodeConsumerVisitor.java @@ -16,43 +16,40 @@ * specific language governing permissions and limitations * under the License. */ -package org.eclipse.aether.internal.impl; +package org.eclipse.aether.util.graph.visitor; -import java.util.ArrayList; -import java.util.List; +import java.util.function.Consumer; -import org.eclipse.aether.RequestTrace; import org.eclipse.aether.graph.DependencyNode; -import org.eclipse.aether.graph.DependencyVisitor; -import org.eclipse.aether.resolution.ArtifactRequest; /** + * Processes dependency graph by traversing the graph in preorder. This visitor visits each node exactly once + * regardless how many paths within the dependency graph lead to the node such that the resulting node sequence is + * free of duplicates. + * + * @since TBD */ -class ArtifactRequestBuilder implements DependencyVisitor { - - private final RequestTrace trace; +public final class PreorderDependencyNodeConsumerVisitor extends AbstractDependencyNodeConsumerVisitor { - private final List<ArtifactRequest> requests; + public static final String NAME = "preOrder"; - ArtifactRequestBuilder(RequestTrace trace) { - this.trace = trace; - this.requests = new ArrayList<>(); - } - - public List<ArtifactRequest> getRequests() { - return requests; + /** + * Creates a new preorder list generator. + */ + public PreorderDependencyNodeConsumerVisitor(Consumer<DependencyNode> nodeConsumer) { + super(nodeConsumer); } + @Override public boolean visitEnter(DependencyNode node) { - if (node.getDependency() != null) { - ArtifactRequest request = new ArtifactRequest(node); - request.setTrace(trace); - requests.add(request); + if (!setVisited(node)) { + return false; } - + nodeConsumer.accept(node); return true; } + @Override public boolean visitLeave(DependencyNode node) { return true; } diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PreorderNodeListGenerator.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PreorderNodeListGenerator.java index 07841049..da2b6001 100644 --- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PreorderNodeListGenerator.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/visitor/PreorderNodeListGenerator.java @@ -24,6 +24,13 @@ import org.eclipse.aether.graph.DependencyNode; * Generates a sequence of dependency nodes from a dependency graph by traversing the graph in preorder. This visitor * visits each node exactly once regardless how many paths within the dependency graph lead to the node such that the * resulting node sequence is free of duplicates. + * <p> + * The newer classes {@link AbstractDependencyNodeConsumerVisitor} and {@link NodeListGenerator} offer + * similar capabilities but are pluggable. Use of this class, while not deprecated, is discouraged. This class + * is not used in Resolver and is kept only for backward compatibility reasons. + * + * @see PreorderDependencyNodeConsumerVisitor + * @see NodeListGenerator */ public final class PreorderNodeListGenerator extends AbstractDepthFirstNodeListGenerator { diff --git a/maven-resolver-util/src/test/java/org/eclipse/aether/util/graph/visitor/NodeListGeneratorTest.java b/maven-resolver-util/src/test/java/org/eclipse/aether/util/graph/visitor/NodeListGeneratorTest.java new file mode 100644 index 00000000..71946c3b --- /dev/null +++ b/maven-resolver-util/src/test/java/org/eclipse/aether/util/graph/visitor/NodeListGeneratorTest.java @@ -0,0 +1,113 @@ +/* + * 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. + */ +package org.eclipse.aether.util.graph.visitor; + +import java.util.List; + +import org.eclipse.aether.graph.DependencyNode; +import org.eclipse.aether.internal.test.util.DependencyGraphParser; +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +public class NodeListGeneratorTest { + + private DependencyNode parse(String resource) throws Exception { + return new DependencyGraphParser("visitor/ordered-list/").parseResource(resource); + } + + private void assertSequence(List<DependencyNode> actual, String... expected) { + assertEquals(actual.toString(), expected.length, actual.size()); + for (int i = 0; i < expected.length; i++) { + DependencyNode node = actual.get(i); + assertEquals( + actual.toString(), + expected[i], + node.getDependency().getArtifact().getArtifactId()); + } + } + + @Test + public void testPreOrder() throws Exception { + DependencyNode root = parse("simple.txt"); + + NodeListGenerator nodeListGenerator = new NodeListGenerator(); + PreorderDependencyNodeConsumerVisitor visitor = new PreorderDependencyNodeConsumerVisitor(nodeListGenerator); + root.accept(visitor); + + assertSequence(nodeListGenerator.getNodes(), "a", "b", "c", "d", "e"); + } + + @Test + public void testPreOrderDuplicateSuppression() throws Exception { + DependencyNode root = parse("cycles.txt"); + + NodeListGenerator nodeListGenerator = new NodeListGenerator(); + PreorderDependencyNodeConsumerVisitor visitor = new PreorderDependencyNodeConsumerVisitor(nodeListGenerator); + root.accept(visitor); + + assertSequence(nodeListGenerator.getNodes(), "a", "b", "c", "d", "e"); + } + + @Test + public void testPostOrder() throws Exception { + DependencyNode root = parse("simple.txt"); + + NodeListGenerator nodeListGenerator = new NodeListGenerator(); + PostorderDependencyNodeConsumerVisitor visitor = new PostorderDependencyNodeConsumerVisitor(nodeListGenerator); + root.accept(visitor); + + assertSequence(nodeListGenerator.getNodes(), "c", "b", "e", "d", "a"); + } + + @Test + public void testPostOrderDuplicateSuppression() throws Exception { + DependencyNode root = parse("cycles.txt"); + + NodeListGenerator nodeListGenerator = new NodeListGenerator(); + PostorderDependencyNodeConsumerVisitor visitor = new PostorderDependencyNodeConsumerVisitor(nodeListGenerator); + root.accept(visitor); + + assertSequence(nodeListGenerator.getNodes(), "c", "b", "e", "d", "a"); + } + + @Test + public void testLevelOrder() throws Exception { + DependencyNode root = parse("simple.txt"); + + NodeListGenerator nodeListGenerator = new NodeListGenerator(); + LevelOrderDependencyNodeConsumerVisitor visitor = + new LevelOrderDependencyNodeConsumerVisitor(nodeListGenerator); + root.accept(visitor); + + assertSequence(nodeListGenerator.getNodes(), "a", "b", "d", "c", "e"); + } + + @Test + public void testLevelOrderDuplicateSuppression() throws Exception { + DependencyNode root = parse("cycles.txt"); + + NodeListGenerator nodeListGenerator = new NodeListGenerator(); + LevelOrderDependencyNodeConsumerVisitor visitor = + new LevelOrderDependencyNodeConsumerVisitor(nodeListGenerator); + root.accept(visitor); + + assertSequence(nodeListGenerator.getNodes(), "a", "b", "d", "c", "e"); + } +} diff --git a/src/site/markdown/configuration.md b/src/site/markdown/configuration.md index de1e6070..9a36a816 100644 --- a/src/site/markdown/configuration.md +++ b/src/site/markdown/configuration.md @@ -105,6 +105,7 @@ Option | Type | Description | Default Value | Supports Repo ID Suffix `aether.syncContext.named.discriminating.discriminator` | String | A discriminator name prefix identifying a Resolver instance. | `"sha1('${hostname:-localhost}:${maven.repo.local}')"` or `"sha1('')"` if generation fails | no `aether.syncContext.named.discriminating.hostname` | String | The hostname to be used with discriminating mapper. | Detected with `InetAddress.getLocalHost().getHostName()` | no `aether.syncContext.named.redisson.configFile` | String | Path to a Redisson configuration file in YAML format. Read [official documentation](https://github.com/redisson/redisson/wiki/2.-Configuration) for details. | none or `"${maven.conf}/maven-resolver-redisson.yaml"` if present | no +`aether.system.resolveDependencies.visitor` | String | Name of the visitor to be used to "flatten" the dependency graph into list of Artifacts. Accepted values are "preOrder" (default, only possibility in Resolver 1.x), "levelOrder" and "postOrder". | `"preOrder"` | no `aether.trustedChecksumsSource.sparseDirectory` | boolean | Enable `sparseDirectory` trusted checksum source. | `false` | no `aether.trustedChecksumsSource.sparseDirectory.basedir` | String | The basedir path for `sparseDirectory` trusted checksum source. If relative, resolved against local repository root, if absolute, used as is. | `".checksums"` | no `aether.trustedChecksumsSource.sparseDirectory.originAware` | boolean | Is trusted checksum source origin aware (factors in Repository ID into path) or not. | `true` | no