Gradle is overzealous in excluding transitive dependencies when one dependency excludes, but another does not. It appears this is due to a cache hit that should've been a cache miss. The only way I caught this is because when the lockfile is present, it shuffles the resolver's dependency node queue just enough that the cache miss triggers correctly, and Gradle reports an error that the dependency tree no longer matches the lockfile.

It appears that a combination of having a platform dependency with a large amount of constraints, combined with a dependency on maven-embedder, creates just the right ordering, in which exclusions can be inherited early by a transitive of a transitive, and never updated when edges change the outcome of the exclusions.

Expected Behavior

The dependency tree should show all transitives in the dependency tree that ought to be present, with or without a lockfile present.

Current Behavior

Gradle, depending on the order which dependency nodes are queued for processing, excludes dependencies that ought not to have been excluded.

Context

This affects our ability to create reproducible builds, because the lockfile triggers a failure in release testing. It also creates some anxiety that transitives, which should be present, will be missing, simply due to internal details.

Steps to Reproduce

Reproducer: https://github.com/jskillin-idt/gradle-gradle-issues-22525

1. Run ./gradlew dependencies --configuration runtimeClasspath and notice that Gradle includes the dependencies in the graph, but they are not in the lockfile. To be clear, the error_prone_annotations and j2objc-annotations dependencies ought to be present in both the lockfile and the tree.

runtimeClasspath - Runtime classpath of source set 'main'.
 ...
+--- org.apache.maven:maven-embedder:3.8.6
 ...
|    +--- org.apache.maven:maven-core:3.8.6
 ...
|    |    +--- com.google.inject:guice:4.2.2
|    |    |    +--- aopalliance:aopalliance:1.0
|    |    |    \--- com.google.guava:guava:25.1-android -> 31.1-jre
|    |    |         +--- com.google.guava:failureaccess:1.0.1
|    |    |         +--- com.google.errorprone:error_prone_annotations:2.11.0 -> 2.14.0
|    |    |         \--- com.google.j2objc:j2objc-annotations:1.3
 ...
     +--- com.google.inject:guice:4.2.2 (*)
 ...
+--- com.google.guava:guava:{strictly 31.1-jre} -> 31.1-jre (c)
+--- com.google.guava:failureaccess:{strictly 1.0.1} -> 1.0.1 (c)
+--- com.google.errorprone:error_prone_annotations:2.14.0 FAILED
\--- com.google.j2objc:j2objc-annotations:1.3 FAILED

2. Remove gradle.lockfile and run ./gradlew dependencies --configuration runtimeClasspath again. Notice that the dependency tree is missing dependencies that ought to be there:

runtimeClasspath - Runtime classpath of source set 'main'.
 ...
\--- org.apache.maven:maven-embedder:3.8.6
 ...
     +--- org.apache.maven:maven-core:3.8.6
 ...
     |    +--- com.google.inject:guice:4.2.2
     |    |    +--- aopalliance:aopalliance:1.0
     |    |    \--- com.google.guava:guava:25.1-android -> 31.1-jre
     |    |         \--- com.google.guava:failureaccess:1.0.1
 ...
     +--- com.google.inject:guice:4.2.2 (*)

3. Run ./gradlew dependencies --write-locks and you will be back at step 1 again, with the missing dependencies back where they should be, but now mismatching with the lockfile.

Initial Investigation

I've done as much debugging as I can do, and it appears to me that the bug comes down to this line:

The comment here, in context, gave me a chuckle:

    private boolean sameIncomingEdgesAsPreviousPass(int incomingEdgeCount) {
        // This is a heuristic, more than truth: it is possible that the 2 long hashs
        // are identical AND that the sizes of collections are identical, but it's
        // extremely unlikely (never happened on test cases even on large dependency graph)
        return cachedModuleResolutionFilter != null
            && previousIncomingHash == incomingHash
            && previousIncomingEdgeCount == incomingEdgeCount;
    }

The issue is that guava (see reproducer output) has a chance of being processed by the loop in DependencyGraphBuilder#traverseGraph before guice has all of its edges attached.

In one case, when the lockfile isn't present, only the maven-embedder -> guice edge is the only one present on guice when guava queries for excludes. This edge is extremely harsh about the excludes that should be applied, so at this point in the traversal, guava's dependencies are almost entirely excluded.

Later, the maven-core -> guice edge is processed and the guava node is properly requeued when guice gets new incoming edges. However, when it's guava's time to be reprocessed, guava's incoming edge identities or counts haven't changed, and the cache hits when it ought not to hit. As a result, guava retains the harsh exclusions and does not have as many dependencies as it should have to satisfy maven-core.

When the lockfile is present, the two edges are queued earlier, and so guava retrieves the correct exclusion filter, and the correct dependencies are added to the graph.

Your Environment

$ ./gradlew --version
------------------------------------------------------------
Gradle 7.5.1
------------------------------------------------------------

Build time:   2022-08-05 21:17:56 UTC
Revision:     d1daa0cbf1a0103000b71484e1dbfe096e095918

Kotlin:       1.6.21
Groovy:       3.0.10
Ant:          Apache Ant(TM) version 1.10.11 compiled on July 10 2021
JVM:          11.0.16 (Ubuntu 11.0.16+8-post-Ubuntu-0ubuntu122.04)
OS:           Linux 5.15.0-52-generic amd64

$ java --version
openjdk 11.0.16 2022-07-19
OpenJDK Runtime Environment (build 11.0.16+8-post-Ubuntu-0ubuntu122.04)
OpenJDK 64-Bit Server VM (build 11.0.16+8-post-Ubuntu-0ubuntu122.04, mixed mode, sharing)