GoogleCloudPlatform · suztomo · Aug 17, 2021 · Aug 13, 2021 · Aug 13, 2021 · Aug 13, 2021
diff --git a/...alTest/groovy/com/google/cloud/tools/dependencies/gradle/BuildStatusFunctionalTest.groovy b/...alTest/groovy/com/google/cloud/tools/dependencies/gradle/BuildStatusFunctionalTest.groovy
@@ -111,6 +111,17 @@ class BuildStatusFunctionalTest extends Specification {
         |io.grpc:grpc-grpclb:1.28.1 is at:
         |  g:test-123:0.1.0-SNAPSHOT / com.google.cloud:google-cloud-logging:1.101.1 / com.google.api:gax-grpc:1.56.0 / io.grpc:grpc-alts:1.28.1 / io.grpc:grpc-grpclb:1.28.1
         |""".stripMargin())
+
+    // "(omitted for duplicate)" should come after the non-omitted items
+    result.output.contains("""
+        |io.grpc:grpc-alts:1.28.1 is at:
+        |  g:test-123:0.1.0-SNAPSHOT / com.google.cloud:google-cloud-logging:1.101.1 / com.google.api:gax-grpc:1.56.0 / io.grpc:grpc-alts:1.28.1
+        |""".stripMargin())
+
+    // Ensure the node closest to the root is printed
+    result.output.contains("g:test-123:0.1.0-SNAPSHOT / io.grpc:grpc-core:1.29.0")
+    // Ensure that the relationship between grpc-netty-shaded to grpc-core is only printed once
+    result.output.count("io.grpc:grpc-netty-shaded:1.28.1 / io.grpc:grpc-core:1.29.0") == 1
     result.task(":linkageCheck").outcome == TaskOutcome.FAILED
   }
 

diff --git a/gradle-plugin/src/main/java/com/google/cloud/tools/dependencies/gradle/DependencyNode.java b/gradle-plugin/src/main/java/com/google/cloud/tools/dependencies/gradle/DependencyNode.java
@@ -0,0 +1,86 @@
+/*
+ * Copyright 2021 Google LLC.
+ *
+ * Licensed 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 com.google.cloud.tools.dependencies.gradle;
+
+import com.google.common.base.MoreObjects;
+import com.google.common.collect.ImmutableList;
+import java.util.ArrayDeque;
+import java.util.Objects;
+import java.util.stream.Collectors;
+import org.gradle.api.artifacts.result.ResolvedComponentResult;
+
+/** Dependency nodes to record dependency paths while traversing the dependency tree */
+final class DependencyNode {
+  ResolvedComponentResult componentResult;
+
+  DependencyNode parent;
+
+  DependencyNode(ResolvedComponentResult componentResult, DependencyNode parent) {
+    this.componentResult = componentResult;
+    this.parent = parent;
+  }
+
+  boolean isDescendantOf(ResolvedComponentResult other) {
+    if (componentResult.equals(other)) {
+      return true;
+    }
+    if (parent == null) {
+      return false;
+    }
+    return parent.isDescendantOf(other);
+  }
+
+  String pathFromRoot() {
+    return fromRootToNode().stream()
+        .map(LinkageCheckTask::formatComponentResult)
+        .collect(Collectors.joining(" / "));
+  }
+
+  ImmutableList<ResolvedComponentResult> fromRootToNode() {
+    ArrayDeque<ResolvedComponentResult> nodes = new ArrayDeque<>();
+    for (DependencyNode iter = this; iter != null; iter = iter.parent) {
+      nodes.addFirst(iter.componentResult);
+    }
+    return ImmutableList.copyOf(nodes);
+  }
+
+  @Override
+  public String toString() {
+    return MoreObjects.toStringHelper(this)
+        .add("componentResult", componentResult)
+        .add("parent", parent)
+        .toString();
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (this == other) {
+      return true;
+    }
+    if (other == null || getClass() != other.getClass()) {
+      return false;
+    }
+    DependencyNode that = (DependencyNode) other;
+    return Objects.equals(componentResult, that.componentResult)
+        && Objects.equals(parent, that.parent);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(componentResult, parent);
+  }
+}
diff --git a/gradle-plugin/src/main/java/com/google/cloud/tools/dependencies/gradle/LinkageCheckTask.java b/gradle-plugin/src/main/java/com/google/cloud/tools/dependencies/gradle/LinkageCheckTask.java
@@ -31,15 +31,17 @@
 import com.google.cloud.tools.opensource.dependencies.DependencyPath;
 import com.google.cloud.tools.opensource.dependencies.PathToNode;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableListMultimap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ListMultimap;
+import com.google.common.collect.MultimapBuilder;
 import java.io.IOException;
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.ArrayDeque;
+import java.util.ArrayList;
 import java.util.HashSet;
+import java.util.List;
 import java.util.Set;
-import java.util.stream.Collectors;
 import org.eclipse.aether.artifact.Artifact;
 import org.eclipse.aether.artifact.DefaultArtifact;
 import org.eclipse.aether.graph.Dependency;
@@ -64,6 +66,9 @@
 public class LinkageCheckTask extends DefaultTask {
   private LinkageCheckerPluginExtension extension;
 
+  // A set to avoid printing the same circular dependency multiple times
+  private Set<ResolvedComponentResult> checkedCircularDependency = new HashSet<>();
+
   @TaskAction
   public void run() throws IOException {
     extension = getProject().getExtensions().findByType(LinkageCheckerPluginExtension.class);
@@ -191,46 +196,87 @@ private String dependencyPathsOfProblematicJars(
         + dependencyPathToArtifacts(componentResult, problematicJars.build());
   }
 
-  String formatComponentResult(ResolvedComponentResult componentResult) {
+  static String formatComponentResult(ResolvedComponentResult componentResult) {
     ModuleVersionIdentifier identifier = componentResult.getModuleVersion();
     return identifier.toString();
   }
 
-  private void recordDependencyPaths(
-      ImmutableListMultimap.Builder<String, String> output,
-      ArrayDeque<ResolvedComponentResult> stack,
-      ImmutableSet<String> targetCoordinates,
-      Set<ResolvedComponentResult> checkedCircularDependency) {
-    ResolvedComponentResult item = stack.getLast();
-    ModuleVersionIdentifier identifier = item.getModuleVersion();
-    String coordinates =
-        String.format(
-            "%s:%s:%s", identifier.getGroup(), identifier.getName(), identifier.getVersion());
-    if (targetCoordinates.contains(coordinates)) {
-      String dependencyPath =
-          stack.stream().map(this::formatComponentResult).collect(Collectors.joining(" / "));
-      output.put(coordinates, dependencyPath);
+  /**
+   * Returns mapping from Maven coordinates to their dependency paths appearing in the dependency
+   * graph. The output do not have duplicate dependency paths.
+   *
+   * @param rootProject The root project in the dependency graph
+   * @param targetCoordinatesSet The Maven coordinates to check their dependency paths
+   */
+  private ListMultimap<String, String> groupCoordinatesToDependencyPaths(
+      ResolvedComponentResult rootProject, Set<String> targetCoordinatesSet) {
+
+    ListMultimap<String, String> coordinatesToDependencyPaths =
+        MultimapBuilder.hashKeys().arrayListValues().build();
+
+    for (String targetCoordinates : targetCoordinatesSet) {
+      // Queue of dependency nodes. Each node knows its parent.
+      ArrayDeque<DependencyNode> queue = new ArrayDeque<>();
+      DependencyNode firstItem = new DependencyNode(rootProject, null);
+      queue.add(firstItem);
+
+      // A set of dependencies to omit duplicate dependency paths in the output.
+      Set<ResolvedComponentResult> nodesDependOnTarget = new HashSet<>();
+
+      while (!queue.isEmpty()) {
+        DependencyNode node = queue.poll();
+        ResolvedComponentResult item = node.componentResult;
+
+        ModuleVersionIdentifier identifier = item.getModuleVersion();
+        String coordinates =
+            String.format(
+                "%s:%s:%s", identifier.getGroup(), identifier.getName(), identifier.getVersion());
+        if (targetCoordinates.equals(coordinates)) {
+          String dependencyPath = node.pathFromRoot();
+          coordinatesToDependencyPaths.put(targetCoordinates, dependencyPath);
+
+          if (node.parent != null) {
+            nodesDependOnTarget.addAll(node.parent.fromRootToNode());
+          }
+        } else if (nodesDependOnTarget.contains(item)) {
+          // Omitting duplicate dependency paths when we already know this item depends on
+          // targetCoordinates, directly or transitively.
+          String dependencyPath = node.pathFromRoot() + " (omitted for duplicate)";
+          coordinatesToDependencyPaths.put(targetCoordinates, dependencyPath);
+
+          nodesDependOnTarget.addAll(node.fromRootToNode());
+        } else {
+          queue.addAll(findDependencies(node));
+        }
+      }
     }
 
+    return coordinatesToDependencyPaths;
+  }
+
+  private List<DependencyNode> findDependencies(DependencyNode node) {
+    ResolvedComponentResult item = node.componentResult;
+
+    List<DependencyNode> childNodes = new ArrayList<>();
     for (DependencyResult dependencyResult : item.getDependencies()) {
       if (dependencyResult instanceof ResolvedDependencyResult) {
         ResolvedDependencyResult resolvedDependencyResult =
             (ResolvedDependencyResult) dependencyResult;
         ResolvedComponentResult child = resolvedDependencyResult.getSelected();
 
-        if (stack.contains(child)) {
-          // Circular dependency check
+        if (node.isDescendantOf(child)) {
+          // The child appears in the descendants of the node. It's a circular dependency.
           if (checkedCircularDependency.add(child)) {
+            // No need to print the circular dependency information multiple times.
             getLogger()
                 .error(
                     "Circular dependency for: "
                         + resolvedDependencyResult
                         + "\n The stack is: "
-                        + stack);
+                        + node.pathFromRoot());
           }
         } else {
-          stack.add(child);
-          recordDependencyPaths(output, stack, targetCoordinates, checkedCircularDependency);
+          childNodes.add(new DependencyNode(child, node));
         }
       } else if (dependencyResult instanceof UnresolvedDependencyResult) {
         UnresolvedDependencyResult unresolvedResult = (UnresolvedDependencyResult) dependencyResult;
@@ -242,8 +288,7 @@ private void recordDependencyPaths(
         getLogger().error("Unexpected dependency result type: " + dependencyResult);
       }
     }
-
-    stack.removeLast();
+    return childNodes;
   }
 
   private String dependencyPathToArtifacts(
@@ -255,17 +300,10 @@ private String dependencyPathToArtifacts(
             .map(Artifacts::toCoordinates)
             .collect(toImmutableSet());
 
-    StringBuilder output = new StringBuilder();
-
-    ArrayDeque<ResolvedComponentResult> stack = new ArrayDeque<>();
-    stack.add(componentResult);
+    ListMultimap<String, String> dependencyPaths =
+        groupCoordinatesToDependencyPaths(componentResult, targetCoordinates);
 
-    ImmutableListMultimap.Builder<String, String> coordinatesToDependencyPaths =
-        ImmutableListMultimap.builder();
-
-    recordDependencyPaths(coordinatesToDependencyPaths, stack, targetCoordinates, new HashSet<>());
-
-    ImmutableListMultimap<String, String> dependencyPaths = coordinatesToDependencyPaths.build();
+    StringBuilder output = new StringBuilder();
     for (String coordinates : dependencyPaths.keySet()) {
       output.append(coordinates + " is at:\n");
       for (String dependencyPath : dependencyPaths.get(coordinates)) {