Fix and optimize `Runfiles#fingerprint`

The fingerprint did not include the conflict policy and some of the collections' sizes. It also didn't use the cache for fingerprints of `NestedSet`s and instead always flattened the sets.

The new `fingerprint` method on `EmptyFilesSupplier` makes it possible to drop the call to `Runfiles#getEmptyFilenames`, which would still end up flattening the sets.

See https://groups.google.com/g/bazel-discuss/c/KrUg6ZPky80

Closes #18384.

PiperOrigin-RevId: 534724771
Change-Id: I7b39a1fa2c7c5904b186cc2d343b2b6432b05ad4
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionKeyContext.java b/src/main/java/com/google/devtools/build/lib/actions/ActionKeyContext.java
index 8be622d..24ba5cb 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionKeyContext.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionKeyContext.java
@@ -35,6 +35,18 @@
     nestedSetFingerprintCache.addNestedSetToFingerprint(mapFn, fingerprint, nestedSet);
   }
 
+  public <T> void addNestedSetToFingerprint(
+      CommandLineItem.ExceptionlessMapFn<? super T> mapFn,
+      Fingerprint fingerprint,
+      NestedSet<T> nestedSet) {
+    nestedSetFingerprintCache.addNestedSetToFingerprint(mapFn, fingerprint, nestedSet);
+  }
+
+  public static <T> String describeNestedSetFingerprint(
+      CommandLineItem.ExceptionlessMapFn<? super T> mapFn, NestedSet<T> nestedSet) {
+    return NestedSetFingerprintCache.describedNestedSetFingerprint(mapFn, nestedSet);
+  }
+
   public void clear() {
     nestedSetFingerprintCache.clear();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/CommandLineItem.java b/src/main/java/com/google/devtools/build/lib/actions/CommandLineItem.java
index 5580b1c..153adcf 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/CommandLineItem.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/CommandLineItem.java
@@ -29,6 +29,12 @@
         throws CommandLineExpansionException, InterruptedException;
   }
 
+  /** A {@link CommandLineItem.MapFn} that does not throw. */
+  interface ExceptionlessMapFn<T> extends CommandLineItem.MapFn<T> {
+    @Override
+    void expandToCommandLine(T object, Consumer<String> args);
+  }
+
   /**
    * Use this map function when parametrizing over a limited set of values.
    *
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java b/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java
index 54ad5a0..f48c350 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java
@@ -14,6 +14,8 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import static com.google.devtools.build.lib.actions.ActionKeyContext.describeNestedSetFingerprint;
+
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Function;
 import com.google.common.base.Preconditions;
@@ -22,7 +24,9 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Streams;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.CommandLineItem;
 import com.google.devtools.build.lib.cmdline.LabelConstants;
 import com.google.devtools.build.lib.collect.nestedset.Depset;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -49,6 +53,7 @@
 import java.util.Map;
 import java.util.Objects;
 import java.util.Set;
+import java.util.UUID;
 import javax.annotation.Nullable;
 import net.starlark.java.eval.EvalException;
 import net.starlark.java.eval.Printer;
@@ -70,12 +75,19 @@
 public final class Runfiles implements RunfilesApi {
 
   private static class DummyEmptyFilesSupplier implements EmptyFilesSupplier {
+    private static final UUID GUID = UUID.fromString("36437db7-820b-4386-85b4-f7205a2018ae");
+
     private DummyEmptyFilesSupplier() {}
 
     @Override
     public Iterable<PathFragment> getExtraPaths(Set<PathFragment> manifestPaths) {
       return ImmutableList.of();
     }
+
+    @Override
+    public void fingerprint(Fingerprint fp) {
+      fp.addUUID(GUID);
+    }
   }
 
   @SerializationConstant @AutoCodec.VisibleForSerialization
@@ -151,6 +163,18 @@
   // It is important to declare this *after* the DUMMY_SYMLINK_EXPANDER to avoid NPEs
   public static final Runfiles EMPTY = new Builder().build();
 
+  private static final CommandLineItem.ExceptionlessMapFn<SymlinkEntry> SYMLINK_ENTRY_MAP_FN =
+      (symlink, args) -> {
+        args.accept(symlink.getPathString());
+        args.accept(symlink.getArtifact().getExecPathString());
+      };
+
+  private static final CommandLineItem.ExceptionlessMapFn<Artifact> RUNFILES_AND_EXEC_PATH_MAP_FN =
+      (artifact, args) -> {
+        args.accept(artifact.getRunfilesPathString());
+        args.accept(artifact.getExecPathString());
+      };
+
   /**
    * The directory to put all runfiles under.
    *
@@ -198,6 +222,8 @@
   public interface EmptyFilesSupplier {
     /** Calculate additional empty files to add based on the existing manifest paths. */
     Iterable<PathFragment> getExtraPaths(Set<PathFragment> manifestPaths);
+
+    void fingerprint(Fingerprint fingerprint);
   }
 
   /** Generates extra (empty file) inputs. */
@@ -1155,65 +1181,34 @@
     }
   }
 
-  /**
-   * Fingerprint this {@link Runfiles} tree.
-   */
-  public void fingerprint(Fingerprint fp) {
+  /** Fingerprint this {@link Runfiles} tree. */
+  public void fingerprint(ActionKeyContext actionKeyContext, Fingerprint fp) {
+    fp.addInt(conflictPolicy.ordinal());
     fp.addBoolean(legacyExternalRunfiles);
     fp.addPath(suffix);
-    Map<PathFragment, Artifact> symlinks = getSymlinksAsMap(null);
-    fp.addInt(symlinks.size());
-    for (Map.Entry<PathFragment, Artifact> symlink : symlinks.entrySet()) {
-      fp.addPath(symlink.getKey());
-      fp.addPath(symlink.getValue().getExecPath());
-    }
-    Map<PathFragment, Artifact> rootSymlinks = getRootSymlinksAsMap(null);
-    fp.addInt(rootSymlinks.size());
-    for (Map.Entry<PathFragment, Artifact> rootSymlink : rootSymlinks.entrySet()) {
-      fp.addPath(rootSymlink.getKey());
-      fp.addPath(rootSymlink.getValue().getExecPath());
-    }
 
-    for (Artifact artifact : artifacts.toList()) {
-      fp.addPath(artifact.getRunfilesPath());
-      fp.addPath(artifact.getExecPath());
-    }
+    actionKeyContext.addNestedSetToFingerprint(SYMLINK_ENTRY_MAP_FN, fp, symlinks);
+    actionKeyContext.addNestedSetToFingerprint(SYMLINK_ENTRY_MAP_FN, fp, rootSymlinks);
+    actionKeyContext.addNestedSetToFingerprint(RUNFILES_AND_EXEC_PATH_MAP_FN, fp, artifacts);
 
-    for (String name : getEmptyFilenames().toList()) {
-      fp.addString(name);
-    }
+    emptyFilesSupplier.fingerprint(fp);
+
+    // extraMiddlemen does not affect the shape of the runfiles tree described by this instance and
+    // thus does not need to be fingerprinted.
   }
-  /** Describes the inputs {@link fingerprint} uses to aid describeKey() descriptions. */
+
+  /** Describes the inputs {@link #fingerprint} uses to aid describeKey() descriptions. */
   public String describeFingerprint() {
-    StringBuilder sb = new StringBuilder();
-    sb.append(String.format("legacyExternalRunfiles: %s\n", legacyExternalRunfiles));
-    sb.append(String.format("suffix: %s\n", suffix));
-
-    var symlinks = getSymlinksAsMap(null);
-    sb.append(String.format("symlinksSize: %s\n", symlinks.size()));
-    for (var symlink : symlinks.entrySet()) {
-      sb.append(
-          String.format(
-              "symlink: '%s' to '%s'\n", symlink.getKey(), symlink.getValue().getExecPath()));
-    }
-
-    var rootSymlinks = getRootSymlinksAsMap(null);
-    sb.append(String.format("rootSymlinksSize: %s\n", rootSymlinks.size()));
-    for (var symlink : rootSymlinks.entrySet()) {
-      sb.append(
-          String.format(
-              "rootSymlink: '%s' to '%s'\n", symlink.getKey(), symlink.getValue().getExecPath()));
-    }
-
-    for (Artifact artifact : artifacts.toList()) {
-      sb.append(
-          String.format(
-              "artifact: '%s' '%s'\n", artifact.getRunfilesPath(), artifact.getExecPath()));
-    }
-
-    for (String name : getEmptyFilenames().toList()) {
-      sb.append(String.format("emptyFilename: '%s'\n", name));
-    }
-    return sb.toString();
+    return String.format("conflictPolicy: %s\n", conflictPolicy)
+        + String.format("legacyExternalRunfiles: %s\n", legacyExternalRunfiles)
+        + String.format("suffix: %s\n", suffix)
+        + String.format(
+            "symlinks: %s\n", describeNestedSetFingerprint(SYMLINK_ENTRY_MAP_FN, symlinks))
+        + String.format(
+            "rootSymlinks: %s\n", describeNestedSetFingerprint(SYMLINK_ENTRY_MAP_FN, rootSymlinks))
+        + String.format(
+            "artifacts: %s\n",
+            describeNestedSetFingerprint(RUNFILES_AND_EXEC_PATH_MAP_FN, artifacts))
+        + String.format("emptyFilesSupplier: %s\n", emptyFilesSupplier.getClass().getName());
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
index 6feb2b9..89827c5 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
@@ -252,7 +252,7 @@
       Fingerprint fp) {
     fp.addString(GUID);
     fp.addBoolean(remotableSourceManifestActions);
-    runfiles.fingerprint(fp);
+    runfiles.fingerprint(actionKeyContext, fp);
     fp.addBoolean(repoMappingManifest != null);
     if (repoMappingManifest != null) {
       fp.addPath(repoMappingManifest.getExecPath());
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkTreeAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkTreeAction.java
index 3242595..76cee12 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkTreeAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkTreeAction.java
@@ -224,7 +224,7 @@
     // safe to add more fields in the future.
     fp.addBoolean(runfiles != null);
     if (runfiles != null) {
-      runfiles.fingerprint(fp);
+      runfiles.fingerprint(actionKeyContext, fp);
     }
     fp.addBoolean(repoMappingManifest != null);
     if (repoMappingManifest != null) {
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
index 70cbbaa..8c80851 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
@@ -19,13 +19,16 @@
 import com.google.devtools.build.lib.rules.python.PythonUtils;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.io.Serializable;
+import java.util.UUID;
 import java.util.function.Predicate;
 
 /** Functionality specific to the Python rules in Bazel. */
 public class BazelPythonSemantics implements PythonSemantics {
 
+  private static final UUID GUID = UUID.fromString("0211a192-1b1e-40e6-80e9-7352360b12b1");
   public static final Runfiles.EmptyFilesSupplier GET_INIT_PY_FILES =
-      new PythonUtils.GetInitPyFiles((Predicate<PathFragment> & Serializable) source -> false);
+      new PythonUtils.GetInitPyFiles(
+          (Predicate<PathFragment> & Serializable) source -> false, GUID);
 
   @Override
   public Runfiles.EmptyFilesSupplier getEmptyRunfilesSupplier() {
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
index 29c0284..15d9eae 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
@@ -16,6 +16,7 @@
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.HashMultiset;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Multiset;
 import com.google.devtools.build.lib.actions.CommandLineExpansionException;
 import com.google.devtools.build.lib.actions.CommandLineItem;
@@ -43,6 +44,18 @@
   }
 
   public <T> void addNestedSetToFingerprint(
+      CommandLineItem.ExceptionlessMapFn<? super T> mapFn,
+      Fingerprint fingerprint,
+      NestedSet<T> nestedSet) {
+    try {
+      addNestedSetToFingerprint((CommandLineItem.MapFn<? super T>) mapFn, fingerprint, nestedSet);
+    } catch (CommandLineExpansionException | InterruptedException e) {
+      // addNestedSetToFingerprint only throws these exceptions if mapFn does.
+      throw new IllegalStateException(e);
+    }
+  }
+
+  public <T> void addNestedSetToFingerprint(
       CommandLineItem.MapFn<? super T> mapFn, Fingerprint fingerprint, NestedSet<T> nestedSet)
       throws CommandLineExpansionException, InterruptedException {
     if (mapFn instanceof CommandLineItem.CapturingMapFn) {
@@ -60,6 +73,23 @@
     addToFingerprint(mapFn, fingerprint, digestMap, children);
   }
 
+  public static <T> String describedNestedSetFingerprint(
+      CommandLineItem.ExceptionlessMapFn<? super T> mapFn, NestedSet<T> nestedSet) {
+    if (nestedSet.isEmpty()) {
+      return "<empty>";
+    }
+    StringBuilder sb = new StringBuilder();
+    sb.append("order: ").append(nestedSet.getOrder()).append('\n');
+    ImmutableList<T> list = nestedSet.toList();
+    sb.append("size: ").append(list.size()).append('\n');
+    for (T item : list) {
+      sb.append("  ");
+      mapFn.expandToCommandLine(item, s -> sb.append(sb).append(", "));
+      sb.append('\n');
+    }
+    return sb.toString();
+  }
+
   private <T> void addNestedSetToFingerprintSlow(
       MapFn<? super T> mapFn, Fingerprint fingerprint, NestedSet<T> nestedSet)
       throws CommandLineExpansionException, InterruptedException {
diff --git a/src/main/java/com/google/devtools/build/lib/exec/SymlinkTreeStrategy.java b/src/main/java/com/google/devtools/build/lib/exec/SymlinkTreeStrategy.java
index 5d2e437..610ccab 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/SymlinkTreeStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/SymlinkTreeStrategy.java
@@ -163,7 +163,7 @@
       // If we don't have an input manifest, then create a file containing a fingerprint of
       // the runfiles object.
       Fingerprint fp = new Fingerprint();
-      action.getRunfiles().fingerprint(fp);
+      action.getRunfiles().fingerprint(actionExecutionContext.getActionKeyContext(), fp);
       String hexDigest = fp.hexDigestAndReset();
       try {
         FileSystemUtils.writeContentAsLatin1(outputManifest, hexDigest);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/python/PythonUtils.java b/src/main/java/com/google/devtools/build/lib/rules/python/PythonUtils.java
index 1956dbc..11a6250 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/python/PythonUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/python/PythonUtils.java
@@ -16,9 +16,11 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.Runfiles;
 import com.google.devtools.build.lib.util.FileType;
+import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.HashSet;
 import java.util.Set;
+import java.util.UUID;
 import java.util.function.Predicate;
 
 /** Various utility methods for Python support. */
@@ -37,14 +39,19 @@
    */
   public static class GetInitPyFiles implements Runfiles.EmptyFilesSupplier {
     private final Predicate<PathFragment> isPackageInit;
+    private final UUID guid;
 
     /**
      * The Predicate isPackageInit's .test(source) should be true when a given source is known to be
      * a valid __init__.py file equivalent, meaning no empty __init__.py file need be created.
      * Useful for custom Python runtimes that may have non-standard Python package import logic.
+     *
+     * @param guid a UUID that uniquely identifies the particular isPackageInit predicate for the
+     *     purpose of fingerprinting this {@link Runfiles.EmptyFilesSupplier} instance
      */
-    public GetInitPyFiles(Predicate<PathFragment> isPackageInit) {
+    public GetInitPyFiles(Predicate<PathFragment> isPackageInit, UUID guid) {
       this.isPackageInit = isPackageInit;
+      this.guid = guid;
     }
 
     @Override
@@ -52,6 +59,11 @@
       return getInitPyFiles(manifestPaths);
     }
 
+    @Override
+    public void fingerprint(Fingerprint fp) {
+      fp.addUUID(guid);
+    }
+
     /**
      * Returns the set of empty __init__.py(c) files to be added to a given set of files to allow
      * the Python runtime to find the <code>.py</code> and <code>.so</code> files present in the
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/BUILD b/src/test/java/com/google/devtools/build/lib/analysis/BUILD
index 4b5a805..6699942 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/analysis/BUILD
@@ -334,8 +334,8 @@
     name = "SourceManifestActionTest",
     srcs = ["SourceManifestActionTest.java"],
     deps = [
-        "//src/main/java/com/google/devtools/build/lib/actions",
         "//src/main/java/com/google/devtools/build/lib/actions:artifacts",
+        "//src/main/java/com/google/devtools/build/lib/actions:commandline_item",
         "//src/main/java/com/google/devtools/build/lib/analysis:analysis_cluster",
         "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
         "//src/main/java/com/google/devtools/build/lib/util",
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java b/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java
index 9bbb4bf..e5e468d 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java
@@ -33,6 +33,7 @@
 import com.google.devtools.build.lib.packages.semantics.BuildLanguageOptions;
 import com.google.devtools.build.lib.skyframe.BuildConfigurationKey;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -41,6 +42,7 @@
 import java.util.HashMap;
 import java.util.LinkedHashMap;
 import java.util.Map;
+import java.util.Set;
 import javax.annotation.Nullable;
 import net.starlark.java.eval.EvalException;
 import net.starlark.java.eval.Mutability;
@@ -634,11 +636,18 @@
             .addSymlink(PathFragment.create("my-symlink"), artifact)
             .addRootSymlink(PathFragment.create("my-root-symlink"), artifact)
             .setEmptyFilesSupplier(
-                (manifestPaths) ->
-                    manifestPaths
-                        .stream()
+                new Runfiles.EmptyFilesSupplier() {
+                  @Override
+                  public ImmutableList<PathFragment> getExtraPaths(
+                      Set<PathFragment> manifestPaths) {
+                    return manifestPaths.stream()
                         .map((f) -> f.replaceName(f.getBaseName() + "-empty"))
-                        .collect(ImmutableList.toImmutableList()))
+                        .collect(ImmutableList.toImmutableList());
+                  }
+
+                  @Override
+                  public void fingerprint(Fingerprint fingerprint) {}
+                })
             .build();
     assertThat(runfiles.getEmptyFilenames().toList())
         .containsExactly("my-artifact-empty", "my-symlink-empty");
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/SourceManifestActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/SourceManifestActionTest.java
index 4da17e6..a8aa13b 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/SourceManifestActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/SourceManifestActionTest.java
@@ -13,16 +13,19 @@
 // limitations under the License.
 package com.google.devtools.build.lib.analysis;
 
+import static com.google.common.collect.ImmutableSet.toImmutableSet;
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.common.truth.Truth.assertWithMessage;
 import static com.google.devtools.build.lib.actions.util.ActionsTestUtil.NULL_ACTION_OWNER;
 
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.ArtifactRoot.RootType;
+import com.google.devtools.build.lib.actions.CommandLineExpansionException;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.analysis.SourceManifestAction.ManifestType;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
@@ -37,7 +40,7 @@
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
-import java.util.stream.Collectors;
+import java.util.Set;
 import javax.annotation.Nullable;
 import org.junit.Before;
 import org.junit.Test;
@@ -299,10 +302,20 @@
             new Runfiles.Builder("TESTING", false)
                 .addSymlink(PathFragment.create("a"), buildFile)
                 .setEmptyFilesSupplier(
-                    paths ->
-                        paths.stream()
+                    new Runfiles.EmptyFilesSupplier() {
+                      @Override
+                      public ImmutableSet<PathFragment> getExtraPaths(
+                          Set<PathFragment> manifestPaths) {
+                        return manifestPaths.stream()
                             .map(p -> p.replaceName(p.getBaseName() + "~"))
-                            .collect(Collectors.toSet()))
+                            .collect(toImmutableSet());
+                      }
+
+                      @Override
+                      public void fingerprint(Fingerprint fingerprint) {
+                        fingerprint.addInt(1);
+                      }
+                    })
                 .build());
 
     SourceManifestAction action2 =
@@ -313,10 +326,20 @@
             new Runfiles.Builder("TESTING", false)
                 .addSymlink(PathFragment.create("a"), buildFile)
                 .setEmptyFilesSupplier(
-                    paths ->
-                        paths.stream()
+                    new Runfiles.EmptyFilesSupplier() {
+                      @Override
+                      public ImmutableSet<PathFragment> getExtraPaths(
+                          Set<PathFragment> manifestPaths) {
+                        return manifestPaths.stream()
                             .map(p -> p.replaceName(p.getBaseName() + "~~"))
-                            .collect(Collectors.toSet()))
+                            .collect(toImmutableSet());
+                      }
+
+                      @Override
+                      public void fingerprint(Fingerprint fingerprint) {
+                        fingerprint.addInt(2);
+                      }
+                    })
                 .build());
 
     assertThat(computeKey(action2)).isNotEqualTo(computeKey(action1));
@@ -351,7 +374,8 @@
                 + "TESTING/relative_symlink ../some/relative/path\n");
   }
 
-  private String computeKey(SourceManifestAction action) {
+  private String computeKey(SourceManifestAction action)
+      throws CommandLineExpansionException, InterruptedException {
     Fingerprint fp = new Fingerprint();
     action.computeKey(actionKeyContext, /*artifactExpander=*/ null, fp);
     return fp.hexDigestAndReset();
diff --git a/src/test/java/com/google/devtools/build/lib/exec/SymlinkTreeStrategyTest.java b/src/test/java/com/google/devtools/build/lib/exec/SymlinkTreeStrategyTest.java
index ad7a7a5..b95a8f3 100644
--- a/src/test/java/com/google/devtools/build/lib/exec/SymlinkTreeStrategyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/exec/SymlinkTreeStrategyTest.java
@@ -35,12 +35,14 @@
 import com.google.devtools.build.lib.analysis.actions.SymlinkTreeActionContext;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.events.StoredEventHandler;
+import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.OutputService;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Symlinks;
 import java.util.Map;
+import java.util.Set;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -83,7 +85,17 @@
 
     Runfiles runfiles =
         new Runfiles.Builder("TESTING", false)
-            .setEmptyFilesSupplier((paths) -> ImmutableList.of(PathFragment.create("dir/empty")))
+            .setEmptyFilesSupplier(
+                new Runfiles.EmptyFilesSupplier() {
+                  @Override
+                  public ImmutableList<PathFragment> getExtraPaths(
+                      Set<PathFragment> manifestPaths) {
+                    return ImmutableList.of(PathFragment.create("dir/empty"));
+                  }
+
+                  @Override
+                  public void fingerprint(Fingerprint fingerprint) {}
+                })
             .addArtifact(runfile)
             .build();
     SymlinkTreeAction action =
@@ -130,7 +142,17 @@
 
     Runfiles runfiles =
         new Runfiles.Builder("TESTING", false)
-            .setEmptyFilesSupplier((paths) -> ImmutableList.of(PathFragment.create("dir/empty")))
+            .setEmptyFilesSupplier(
+                new Runfiles.EmptyFilesSupplier() {
+                  @Override
+                  public ImmutableList<PathFragment> getExtraPaths(
+                      Set<PathFragment> manifestPaths) {
+                    return ImmutableList.of(PathFragment.create("dir/empty"));
+                  }
+
+                  @Override
+                  public void fingerprint(Fingerprint fingerprint) {}
+                })
             .addArtifact(runfile)
             .build();
     SymlinkTreeAction action =
@@ -139,12 +161,12 @@
             inputManifest,
             runfiles,
             outputManifest,
-            /*repoMappingManifest=*/ null,
-            /*filesetRoot=*/ null,
+            /* repoMappingManifest= */ null,
+            /* filesetRoot= */ null,
             ActionEnvironment.EMPTY,
-            /*enableRunfiles=*/ true,
-            /*inprocessSymlinkCreation=*/ true,
-            /*skipRunfilesManifests*/ false);
+            /* enableRunfiles= */ true,
+            /* inprocessSymlinkCreation= */ true,
+            /* skipRunfilesManifests= */ false);
 
     action.execute(context);
     // Check that the OutputService is not used.