Consolidate action rewinding tests into BuildWithoutTheBytesIntegrationTestBase.

Move action rewinding integration tests from `BuildWithoutTheBytesIntegrationTest` to `BuildWithoutTheBytesIntegrationTestBase` to make them reusable across test subclasses, and dynamically configure spawn strategies during eviction steps.

PiperOrigin-RevId: 970521193
Change-Id: Iee61664fd995ab003f3293aedfb91a974b7d8160
diff --git a/src/test/java/com/google/devtools/build/lib/remote/BUILD b/src/test/java/com/google/devtools/build/lib/remote/BUILD
index 82d9fc4..b61243e 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/remote/BUILD
@@ -354,7 +354,6 @@
         "//src/main/java/com/google/devtools/build/lib/dynamic",
         "//src/main/java/com/google/devtools/build/lib/remote:remote_module",
         "//src/main/java/com/google/devtools/build/lib/remote/options",
-        "//src/main/java/com/google/devtools/build/lib/remote/util:digest_util",
         "//src/main/java/com/google/devtools/build/lib/runtime:blaze_command_cluster",
         "//src/main/java/com/google/devtools/build/lib/runtime:block_waiting_module",
         "//src/main/java/com/google/devtools/build/lib/runtime:build_summary_stats_module",
diff --git a/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTest.java b/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTest.java
index d4327a5..ef444e4 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTest.java
@@ -425,470 +425,6 @@
     assertOutputsDoNotExist("//a:hello");
   }
 
-  @Test
-  public void remoteCacheEvictBlobs_whenPrefetchingInput(@TestParameter boolean actionRewinding)
-      throws Exception {
-    // Arrange: Prepare workspace and populate remote cache
-    write(
-        "a/BUILD",
-        """
-        genrule(
-            name = "foo",
-            srcs = ["foo.in"],
-            outs = ["foo.out"],
-            cmd = "cat $(SRCS) > $@",
-        )
-
-        genrule(
-            name = "bar",
-            srcs = [
-                "foo.out",
-                "bar.in",
-            ],
-            outs = ["bar.out"],
-            cmd = "cat $(SRCS) > $@",
-            tags = ["no-remote-exec"],
-        )
-        """);
-    write("a/foo.in", "foo");
-    write("a/bar.in", "bar");
-
-    // Populate remote cache
-    buildTarget("//a:bar");
-    var bytes = readContent(getOutputPath("a/foo.out"));
-    var hashCode = getDigestHashFunction().getHashFunction().hashBytes(bytes);
-    getOutputPath("a/foo.out").delete();
-    getOutputPath("a/bar.out").delete();
-    getOutputBase().getRelative("action_cache").deleteTreesBelow();
-    restartServer();
-
-    // Clean build, foo.out isn't downloaded
-    buildTarget("//a:bar");
-    assertOutputDoesNotExist("a/foo.out");
-
-    // Act: Evict blobs from remote cache and do an incremental build
-    evictAllBlobs();
-    write("a/bar.in", "updated bar");
-
-    if (actionRewinding) {
-      // Assert: the lost input's generating action is rewound and the build succeeds
-      enableActionRewinding();
-      buildTarget("//a:bar");
-      assertValidOutputFile("a/bar.out", "foo\nupdated bar\n");
-    } else {
-      // Assert: the build fails with exit code 39
-      disableActionRewinding();
-      var error = assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
-      assertThat(error).hasMessageThat().contains("Lost inputs no longer available remotely");
-      assertThat(error).hasMessageThat().contains("a/foo.out");
-      assertThat(error).hasMessageThat().contains(String.format("%s/%s", hashCode, bytes.length));
-      assertThat(error.getDetailedExitCode().getExitCode().getNumericExitCode()).isEqualTo(39);
-    }
-  }
-
-  @Test
-  public void remoteCacheEvictBlobs_whenPrefetchingSymlinkedInput(
-      @TestParameter boolean actionRewinding) throws Exception {
-    // Arrange: Prepare workspace and populate remote cache
-    writeSymlinkRule();
-    write(
-        "a/BUILD",
-        """
-        load("//:symlink.bzl", "symlink")
-
-        genrule(
-            name = "foo",
-            srcs = ["foo.in"],
-            outs = ["foo.out"],
-            cmd = "cat $(SRCS) > $@",
-        )
-
-        symlink(
-            name = "symlinked_foo",
-            target_artifact = ":foo.out",
-        )
-
-        genrule(
-            name = "bar",
-            srcs = [
-                ":symlinked_foo",
-                "bar.in",
-            ],
-            outs = ["bar.out"],
-            cmd = "cat $(SRCS) > $@",
-            tags = ["no-remote-exec"],
-        )
-        """);
-    write("a/foo.in", "foo");
-    write("a/bar.in", "bar");
-
-    // Populate remote cache
-    buildTarget("//a:bar");
-    var bytes = readContent(getOutputPath("a/foo.out"));
-    var hashCode = getDigestHashFunction().getHashFunction().hashBytes(bytes);
-    getOnlyElement(getArtifacts("//a:symlinked_foo")).getPath().delete();
-    getOutputPath("a/foo.out").delete();
-    getOutputPath("a/bar.out").delete();
-    getOutputBase().getRelative("action_cache").deleteTreesBelow();
-    restartServer();
-
-    // Clean build, foo.out isn't downloaded
-    buildTarget("//a:bar");
-    assertOutputDoesNotExist("a/foo.out");
-    assertOutputsDoNotExist("//a:symlinked_foo");
-
-    // Act: Evict blobs from remote cache and do an incremental build
-    evictAllBlobs();
-    write("a/bar.in", "updated bar");
-
-    if (actionRewinding) {
-      // Assert: the lost input's generating action is rewound and the build succeeds
-      enableActionRewinding();
-      buildTarget("//a:bar");
-      assertValidOutputFile("a/bar.out", "foo\nupdated bar\n");
-    } else {
-      // Assert: the build fails with exit code 39
-      disableActionRewinding();
-      var error = assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
-      assertThat(error).hasMessageThat().contains("Lost inputs no longer available remotely");
-      assertThat(error).hasMessageThat().contains("a/symlinked_foo");
-      assertThat(error).hasMessageThat().contains(String.format("%s/%s", hashCode, bytes.length));
-      assertThat(error.getDetailedExitCode().getExitCode().getNumericExitCode()).isEqualTo(39);
-    }
-  }
-
-  @Test
-  public void remoteCacheEvictBlobs_whenUploadingInput(@TestParameter boolean actionRewinding)
-      throws Exception {
-    // Arrange: Prepare workspace and populate remote cache
-    write(
-        "a/BUILD",
-        """
-        genrule(
-            name = "foo",
-            srcs = ["foo.in"],
-            outs = ["foo.out"],
-            cmd = "cat $(SRCS) > $@",
-        )
-
-        genrule(
-            name = "bar",
-            srcs = [
-                "foo.out",
-                "bar.in",
-            ],
-            outs = ["bar.out"],
-            cmd = "cat $(SRCS) > $@",
-        )
-        """);
-    write("a/foo.in", "foo");
-    write("a/bar.in", "bar");
-
-    // Populate remote cache
-    setDownloadAll();
-    buildTarget("//a:bar");
-    waitDownloads();
-    var bytes = readContent(getOutputPath("a/foo.out"));
-    var hashCode = getDigestHashFunction().getHashFunction().hashBytes(bytes);
-    getOutputPath("a/foo.out").delete();
-    getOutputPath("a/bar.out").delete();
-    getOutputBase().getRelative("action_cache").deleteTreesBelow();
-    restartServer();
-
-    // Clean build, foo.out isn't downloaded
-    buildTarget("//a:bar");
-    assertOutputDoesNotExist("a/foo.out");
-
-    // Act: Evict blobs from remote cache and do an incremental build
-    evictAllBlobs();
-    write("a/bar.in", "updated bar");
-
-    if (actionRewinding) {
-      // Assert: the lost input's generating action is rewound and the build succeeds
-      enableActionRewinding();
-      buildTarget("//a:bar");
-      assertOutputsDoNotExist("//a:bar");
-      assertOnlyOutputRemoteContent("//a:bar", "bar.out", "foo\nupdated bar\n");
-    } else {
-      // Assert: the build fails with exit code 39
-      disableActionRewinding();
-      var error = assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
-      assertThat(error).hasMessageThat().contains(String.format("%s/%s", hashCode, bytes.length));
-      assertThat(error.getDetailedExitCode().getExitCode().getNumericExitCode()).isEqualTo(39);
-    }
-  }
-
-  @Test
-  public void remoteCacheEvictBlobs_whenUploadingInputFile(@TestParameter boolean actionRewinding)
-      throws Exception {
-    // Arrange: Prepare workspace and populate remote cache
-    write(
-        "a/BUILD",
-        """
-        genrule(
-            name = "foo",
-            srcs = ["foo.in"],
-            outs = ["foo.out"],
-            cmd = "cat $(SRCS) > $@",
-        )
-
-        genrule(
-            name = "bar",
-            srcs = [
-                "foo.out",
-                "bar.in",
-            ],
-            outs = ["bar.out"],
-            cmd = "cat $(SRCS) > $@",
-        )
-        """);
-    write("a/foo.in", "foo");
-    write("a/bar.in", "bar");
-
-    // Populate remote cache
-    buildTarget("//a:bar");
-    getOutputPath("a/foo.out").delete();
-    getOutputPath("a/bar.out").delete();
-    getOutputBase().getRelative("action_cache").deleteTreesBelow();
-    restartServer();
-
-    // Clean build, foo.out isn't downloaded
-    setDownloadToplevel();
-    buildTarget("//a:bar");
-    assertOutputDoesNotExist("a/foo.out");
-
-    // Evict blobs from remote cache
-    evictAllBlobs();
-
-    write("a/bar.in", "updated bar");
-    if (actionRewinding) {
-      // The lost input's generating action is rewound within the next build.
-      enableActionRewinding();
-    } else {
-      // The build fails because of remote cache eviction, but an incremental build without
-      // "clean" or "shutdown" can continue.
-      disableActionRewinding();
-      assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
-    }
-
-    // Act: Do an incremental build without "clean" or "shutdown"
-    buildTarget("//a:bar");
-    waitDownloads();
-
-    // Assert: target was successfully built
-    assertValidOutputFile("a/bar.out", "foo\nupdated bar\n");
-  }
-
-  @Test
-  public void remoteCacheEvictBlobs_whenUploadingInputTree(@TestParameter boolean actionRewinding)
-      throws Exception {
-    // Arrange: Prepare workspace and populate remote cache
-    write("BUILD");
-    writeOutputDirRule();
-    write(
-        "a/BUILD",
-        """
-        load("//:output_dir.bzl", "output_dir")
-
-        output_dir(
-            name = "foo.out",
-            content_map = {"file-inside": "hello world"},
-        )
-
-        genrule(
-            name = "bar",
-            srcs = [
-                "foo.out",
-                "bar.in",
-            ],
-            outs = ["bar.out"],
-            cmd = "( ls $(location :foo.out); cat $(location :bar.in) ) > $@",
-        )
-        """);
-    write("a/bar.in", "bar");
-
-    // Populate remote cache
-    buildTarget("//a:bar");
-    getOutputPath("a/foo.out").deleteTreesBelow();
-    getOutputPath("a/bar.out").delete();
-    getOutputBase().getRelative("action_cache").deleteTreesBelow();
-    restartServer();
-
-    // Clean build, foo.out isn't downloaded
-    setDownloadToplevel();
-    buildTarget("//a:bar");
-    assertOutputDoesNotExist("a/foo.out/file-inside");
-
-    // Evict blobs from remote cache
-    evictAllBlobs();
-
-    write("a/bar.in", "updated bar");
-    if (actionRewinding) {
-      // The lost input's generating action is rewound within the next build.
-      enableActionRewinding();
-    } else {
-      // The build fails because of remote cache eviction, but an incremental build without
-      // "clean" or "shutdown" can continue.
-      disableActionRewinding();
-      assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
-    }
-
-    // Act: Do an incremental build without "clean" or "shutdown"
-    buildTarget("//a:bar");
-    waitDownloads();
-
-    // Assert: target was successfully built
-    assertValidOutputFile("a/bar.out", "file-inside\nupdated bar\n");
-  }
-
-  @Test
-  public void remoteCacheEvictBlobs_whenTopLevelRequested_succeedsWithActionRewinding()
-      throws Exception {
-    // Arrange: Prepare workspace and populate remote cache
-    write("BUILD");
-    writeOutputDirRule();
-    write(
-        "a/BUILD",
-        """
-        load("//:output_dir.bzl", "output_dir")
-
-        output_dir(
-            name = "foo.out",
-            content_map = {"file-inside": "hello world"},
-        )
-
-        genrule(
-            name = "bar",
-            srcs = [
-                "foo.out",
-                "bar.in",
-            ],
-            outs = ["bar.out"],
-            cmd = "( ls $(location :foo.out); cat $(location :bar.in) ) > $@",
-        )
-        """);
-    write("a/bar.in", "bar");
-
-    // Populate remote cache
-    buildTarget("//a:bar", "//a:foo.out");
-    getOutputPath("a/foo.out").deleteTreesBelow();
-    getOutputPath("a/bar.out").delete();
-    getOutputBase().getRelative("action_cache").deleteTreesBelow();
-    restartServer();
-
-    // Clean build, bar.out and foo.out aren't downloaded
-    buildTarget("//a:bar", "//a:foo.out");
-    assertOutputDoesNotExist("a/bar.out");
-    assertOutputDoesNotExist("a/foo.out/file-inside");
-
-    // Act: Do an incremental build without "clean" or "shutdown" after clearing the cache and
-    // switching to download toplevel
-    evictAllBlobs();
-    setDownloadToplevel();
-    enableActionRewinding();
-    buildTarget("//a:bar", "//a:foo.out");
-
-    // Assert: all outputs were downloaded
-    assertValidOutputFile("a/bar.out", "file-inside\nbar\n");
-    assertValidOutputFile("a/foo.out/file-inside", "hello world");
-  }
-
-  @Test
-  public void remoteCacheEvictBlobs_whenRunfilesRequested_succeedsWithActionRewinding()
-      throws Exception {
-    // Arrange: Prepare workspace and populate remote cache
-    write("BUILD");
-    writeOutputDirRule();
-    write(
-        "native_binary.bzl",
-        """
-        def _native_binary_impl(ctx):
-            runfiles = ctx.runfiles(
-                transitive_files = depset(
-                    transitive = [target[DefaultInfo].files for target in ctx.attr.data],
-                ),
-            )
-            runfiles = runfiles.merge_all(
-                [target[DefaultInfo].default_runfiles for target in ctx.attr.data],
-            )
-            executable = ctx.actions.declare_file(ctx.label.name)
-            ctx.actions.symlink(
-                output = executable,
-                target_file = ctx.file.executable,
-            )
-            return [
-                DefaultInfo(
-                    executable = executable,
-                    runfiles = runfiles,
-                ),
-            ]
-
-        native_binary = rule(
-            implementation = _native_binary_impl,
-            attrs = {
-                "executable": attr.label(allow_single_file = True),
-                "data": attr.label_list(),
-            },
-            executable = True,
-        )
-        """);
-    write(
-        "a/BUILD",
-        """
-        load("//:native_binary.bzl", "native_binary")
-        load("//:output_dir.bzl", "output_dir")
-
-        output_dir(
-            name = "foo.out",
-            content_map = {"file-inside": "hello world"},
-        )
-
-        genrule(
-            name = "bar",
-            srcs = [
-                "foo.out",
-                "bar.in",
-            ],
-            outs = ["bar.out"],
-            cmd = "( ls $(location :foo.out); cat $(location :bar.in) ) > $@",
-        )
-
-        native_binary(
-            name = "bin",
-            executable = "bin.sh",
-            data = [
-                ":foo.out",
-                ":bar",
-            ],
-        )
-        """);
-    write("a/bar.in", "bar");
-    write("a/bin.sh");
-
-    // Populate remote cache
-    buildTarget("//a:bin");
-    getOutputPath("a/foo.out").deleteTreesBelow();
-    getOutputPath("a/bar.out").delete();
-    getOutputBase().getRelative("action_cache").deleteTreesBelow();
-    restartServer();
-
-    // Clean build, runfiles aren't downloaded
-    buildTarget("//a:bin");
-    assertThat(getOutputPath("a/bin.runfiles").isDirectory()).isTrue();
-    assertOutputDoesNotExist("a/bar.out");
-    assertOutputDoesNotExist("a/foo.out/file-inside");
-
-    // Act: Do an incremental build without "clean" or "shutdown" after clearing the cache and
-    // switching to download toplevel
-    evictAllBlobs();
-    setDownloadToplevel();
-    enableActionRewinding();
-    buildTarget("//a:bin");
-
-    // Assert: all runfiles were downloaded
-    assertValidOutputFile("a/bar.out", "file-inside\nbar\n");
-    assertValidOutputFile("a/foo.out/file-inside", "hello world");
-  }
 
   @Test
   public void leaseExtension() throws Exception {
@@ -1163,6 +699,7 @@
     buildTarget("//:gen");
   }
 
+
   @Test
   public void remoteFilesExpiredBetweenBuilds(@TestParameter boolean actionRewinding)
       throws Exception {
diff --git a/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTestBase.java b/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTestBase.java
index c50206e..d7afa23 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTestBase.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTestBase.java
@@ -16,6 +16,7 @@
 import static com.google.common.collect.Iterables.getOnlyElement;
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.common.truth.Truth.assertWithMessage;
+import static com.google.devtools.build.lib.vfs.FileSystemUtils.readContent;
 import static com.google.devtools.build.lib.vfs.FileSystemUtils.writeContent;
 import static java.nio.charset.StandardCharsets.UTF_8;
 import static org.junit.Assert.assertThrows;
@@ -2046,6 +2047,478 @@
     }
   }
 
+  @Test
+  public void remoteCacheEvictBlobs_whenPrefetchingInput(@TestParameter boolean actionRewinding)
+      throws Exception {
+    // Arrange: Prepare workspace and populate remote cache
+    write(
+        "a/BUILD",
+        """
+        genrule(
+            name = "foo",
+            srcs = ["foo.in"],
+            outs = ["foo.out"],
+            cmd = "cat $(SRCS) > $@",
+        )
+
+        genrule(
+            name = "bar",
+            srcs = [
+                "foo.out",
+                "bar.in",
+            ],
+            outs = ["bar.out"],
+            cmd = "cat $(SRCS) > $@",
+        )
+        """);
+    write("a/foo.in", "foo");
+    write("a/bar.in", "bar");
+
+    // Populate remote cache
+    setDownloadAll();
+    buildTarget("//a:bar");
+    waitDownloads();
+    var bytes = readContent(getOutputPath("a/foo.out"));
+    var hashCode = getDigestHashFunction().getHashFunction().hashBytes(bytes);
+    getOutputPath("a/foo.out").delete();
+    getOutputPath("a/bar.out").delete();
+    getOutputBase().getRelative("action_cache").deleteTreesBelow();
+    restartServer();
+
+    // Clean build, foo.out isn't downloaded
+    buildTarget("//a:bar");
+    assertOutputDoesNotExist("a/foo.out");
+
+    // Act: Evict blobs from remote cache and do an incremental build
+    evictAllBlobs();
+    write("a/bar.in", "updated bar");
+    addOptions("--strategy_regexp=.*bar=local");
+
+    if (actionRewinding) {
+      // Assert: the lost input's generating action is rewound and the build succeeds
+      enableActionRewinding();
+      buildTarget("//a:bar");
+      assertValidOutputFile("a/bar.out", "foo\nupdated bar\n");
+    } else {
+      // Assert: the build fails with exit code 39
+      disableActionRewinding();
+      var error = assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
+      assertThat(error).hasMessageThat().contains("Lost inputs no longer available remotely");
+      assertThat(error).hasMessageThat().contains("a/foo.out");
+      assertThat(error).hasMessageThat().contains(String.format("%s/%s", hashCode, bytes.length));
+      assertThat(error.getDetailedExitCode().getExitCode().getNumericExitCode()).isEqualTo(39);
+    }
+  }
+
+  @Test
+  public void remoteCacheEvictBlobs_whenPrefetchingSymlinkedInput(
+      @TestParameter boolean actionRewinding) throws Exception {
+    // Arrange: Prepare workspace and populate remote cache
+    writeSymlinkRule();
+    write(
+        "a/BUILD",
+        """
+        load("//:symlink.bzl", "symlink")
+
+        genrule(
+            name = "foo",
+            srcs = ["foo.in"],
+            outs = ["foo.out"],
+            cmd = "cat $(SRCS) > $@",
+        )
+
+        symlink(
+            name = "symlinked_foo",
+            target_artifact = ":foo.out",
+        )
+
+        genrule(
+            name = "bar",
+            srcs = [
+                ":symlinked_foo",
+                "bar.in",
+            ],
+            outs = ["bar.out"],
+            cmd = "cat $(SRCS) > $@",
+        )
+        """);
+    write("a/foo.in", "foo");
+    write("a/bar.in", "bar");
+
+    // Populate remote cache
+    setDownloadAll();
+    buildTarget("//a:bar");
+    waitDownloads();
+    var bytes = readContent(getOutputPath("a/foo.out"));
+    var hashCode = getDigestHashFunction().getHashFunction().hashBytes(bytes);
+    getOnlyElement(getArtifacts("//a:symlinked_foo")).getPath().delete();
+    getOutputPath("a/foo.out").delete();
+    getOutputPath("a/bar.out").delete();
+    getOutputBase().getRelative("action_cache").deleteTreesBelow();
+    restartServer();
+
+    // Clean build, foo.out isn't downloaded
+    buildTarget("//a:bar");
+    assertOutputDoesNotExist("a/foo.out");
+    assertOutputsDoNotExist("//a:symlinked_foo");
+
+    // Act: Evict blobs from remote cache and do an incremental build
+    evictAllBlobs();
+    write("a/bar.in", "updated bar");
+    addOptions("--strategy_regexp=.*bar=local");
+
+    if (actionRewinding) {
+      // Assert: the lost input's generating action is rewound and the build succeeds
+      enableActionRewinding();
+      buildTarget("//a:bar");
+      assertValidOutputFile("a/bar.out", "foo\nupdated bar\n");
+    } else {
+      // Assert: the build fails with exit code 39
+      disableActionRewinding();
+      var error = assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
+      assertThat(error).hasMessageThat().contains("Lost inputs no longer available remotely");
+      assertThat(error).hasMessageThat().contains("a/symlinked_foo");
+      assertThat(error).hasMessageThat().contains(String.format("%s/%s", hashCode, bytes.length));
+      assertThat(error.getDetailedExitCode().getExitCode().getNumericExitCode()).isEqualTo(39);
+    }
+  }
+
+  @Test
+  public void remoteCacheEvictBlobs_whenUploadingInput(@TestParameter boolean actionRewinding)
+      throws Exception {
+    // Arrange: Prepare workspace and populate remote cache
+    write(
+        "a/BUILD",
+        """
+        genrule(
+            name = "foo",
+            srcs = ["foo.in"],
+            outs = ["foo.out"],
+            cmd = "cat $(SRCS) > $@",
+        )
+
+        genrule(
+            name = "bar",
+            srcs = [
+                "foo.out",
+                "bar.in",
+            ],
+            outs = ["bar.out"],
+            cmd = "cat $(SRCS) > $@",
+        )
+        """);
+    write("a/foo.in", "foo");
+    write("a/bar.in", "bar");
+
+    // Populate remote cache
+    setDownloadAll();
+    buildTarget("//a:bar");
+    waitDownloads();
+    var bytes = readContent(getOutputPath("a/foo.out"));
+    var hashCode = getDigestHashFunction().getHashFunction().hashBytes(bytes);
+    getOutputPath("a/foo.out").delete();
+    getOutputPath("a/bar.out").delete();
+    getOutputBase().getRelative("action_cache").deleteTreesBelow();
+    restartServer();
+
+    // Clean build, foo.out isn't downloaded
+    buildTarget("//a:bar");
+    assertOutputDoesNotExist("a/foo.out");
+
+    // Act: Evict blobs from remote cache and do an incremental build
+    evictAllBlobs();
+    write("a/bar.in", "updated bar");
+
+    if (actionRewinding) {
+      // Assert: the lost input's generating action is rewound and the build succeeds
+      enableActionRewinding();
+      buildTarget("//a:bar");
+      assertOutputsDoNotExist("//a:bar");
+      assertOnlyOutputRemoteContent("//a:bar", "bar.out", "foo\nupdated bar\n");
+    } else {
+      // Assert: the build fails with exit code 39
+      disableActionRewinding();
+      addOptions("--strategy_regexp=.*bar=local");
+      var error = assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
+      assertThat(error).hasMessageThat().contains(String.format("%s/%s", hashCode, bytes.length));
+      assertThat(error.getDetailedExitCode().getExitCode().getNumericExitCode()).isEqualTo(39);
+    }
+  }
+
+  @Test
+  public void remoteCacheEvictBlobs_whenUploadingInputFile(@TestParameter boolean actionRewinding)
+      throws Exception {
+    // Arrange: Prepare workspace and populate remote cache
+    write(
+        "a/BUILD",
+        """
+        genrule(
+            name = "foo",
+            srcs = ["foo.in"],
+            outs = ["foo.out"],
+            cmd = "cat $(SRCS) > $@",
+        )
+
+        genrule(
+            name = "bar",
+            srcs = [
+                "foo.out",
+                "bar.in",
+            ],
+            outs = ["bar.out"],
+            cmd = "cat $(SRCS) > $@",
+        )
+        """);
+    write("a/foo.in", "foo");
+    write("a/bar.in", "bar");
+
+    // Populate remote cache
+    buildTarget("//a:bar");
+    getOutputPath("a/foo.out").delete();
+    getOutputPath("a/bar.out").delete();
+    getOutputBase().getRelative("action_cache").deleteTreesBelow();
+    restartServer();
+
+    // Clean build, foo.out isn't downloaded
+    setDownloadToplevel();
+    buildTarget("//a:bar");
+    assertOutputDoesNotExist("a/foo.out");
+
+    // Evict blobs from remote cache
+    evictAllBlobs();
+
+    write("a/bar.in", "updated bar");
+    if (actionRewinding) {
+      // The lost input's generating action is rewound within the next build.
+      enableActionRewinding();
+    } else {
+      // The build fails because of remote cache eviction, but an incremental build without
+      // "clean" or "shutdown" can continue.
+      disableActionRewinding();
+      addOptions("--strategy_regexp=.*bar=local");
+      assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
+    }
+
+    // Act: Do an incremental build without "clean" or "shutdown"
+    buildTarget("//a:bar");
+    waitDownloads();
+
+    // Assert: target was successfully built
+    assertValidOutputFile("a/bar.out", "foo\nupdated bar\n");
+  }
+
+  @Test
+  public void remoteCacheEvictBlobs_whenUploadingInputTree(@TestParameter boolean actionRewinding)
+      throws Exception {
+    // Arrange: Prepare workspace and populate remote cache
+    write("BUILD");
+    writeOutputDirRule();
+    write(
+        "a/BUILD",
+        """
+        load("//:output_dir.bzl", "output_dir")
+
+        output_dir(
+            name = "foo.out",
+            content_map = {"file-inside": "hello world"},
+        )
+
+        genrule(
+            name = "bar",
+            srcs = [
+                "foo.out",
+                "bar.in",
+            ],
+            outs = ["bar.out"],
+            cmd = "( ls $(location :foo.out); cat $(location :bar.in) ) > $@",
+        )
+        """);
+    write("a/bar.in", "bar");
+
+    // Populate remote cache
+    buildTarget("//a:bar");
+    getOutputPath("a/foo.out").deleteTreesBelow();
+    getOutputPath("a/bar.out").delete();
+    getOutputBase().getRelative("action_cache").deleteTreesBelow();
+    restartServer();
+
+    // Clean build, foo.out isn't downloaded
+    setDownloadToplevel();
+    buildTarget("//a:bar");
+    assertOutputDoesNotExist("a/foo.out/file-inside");
+
+    // Evict blobs from remote cache
+    evictAllBlobs();
+
+    write("a/bar.in", "updated bar");
+    if (actionRewinding) {
+      // The lost input's generating action is rewound within the next build.
+      enableActionRewinding();
+    } else {
+      // The build fails because of remote cache eviction, but an incremental build without
+      // "clean" or "shutdown" can continue.
+      disableActionRewinding();
+      addOptions("--strategy_regexp=.*bar=local");
+      assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
+    }
+
+    // Act: Do an incremental build without "clean" or "shutdown"
+    buildTarget("//a:bar");
+    waitDownloads();
+
+    // Assert: target was successfully built
+    assertValidOutputFile("a/bar.out", "file-inside\nupdated bar\n");
+  }
+
+  @Test
+  public void remoteCacheEvictBlobs_whenTopLevelRequested_succeedsWithActionRewinding()
+      throws Exception {
+    // Arrange: Prepare workspace and populate remote cache
+    write("BUILD");
+    writeOutputDirRule();
+    write(
+        "a/BUILD",
+        """
+        load("//:output_dir.bzl", "output_dir")
+
+        output_dir(
+            name = "foo.out",
+            content_map = {"file-inside": "hello world"},
+        )
+
+        genrule(
+            name = "bar",
+            srcs = [
+                "foo.out",
+                "bar.in",
+            ],
+            outs = ["bar.out"],
+            cmd = "( ls $(location :foo.out); cat $(location :bar.in) ) > $@",
+        )
+        """);
+    write("a/bar.in", "bar");
+
+    // Populate remote cache
+    buildTarget("//a:bar", "//a:foo.out");
+    getOutputPath("a/foo.out").deleteTreesBelow();
+    getOutputPath("a/bar.out").delete();
+    getOutputBase().getRelative("action_cache").deleteTreesBelow();
+    restartServer();
+
+    // Clean build, bar.out and foo.out aren't downloaded
+    buildTarget("//a:bar", "//a:foo.out");
+    assertOutputDoesNotExist("a/bar.out");
+    assertOutputDoesNotExist("a/foo.out/file-inside");
+
+    // Act: Do an incremental build without "clean" or "shutdown" after clearing the cache and
+    // switching to download toplevel
+    evictAllBlobs();
+    setDownloadToplevel();
+    enableActionRewinding();
+    buildTarget("//a:bar", "//a:foo.out");
+
+    // Assert: all outputs were downloaded
+    assertValidOutputFile("a/bar.out", "file-inside\nbar\n");
+    assertValidOutputFile("a/foo.out/file-inside", "hello world");
+  }
+
+  @Test
+  public void remoteCacheEvictBlobs_whenRunfilesRequested_succeedsWithActionRewinding()
+      throws Exception {
+    // Arrange: Prepare workspace and populate remote cache
+    write("BUILD");
+    writeOutputDirRule();
+    write(
+        "native_binary.bzl",
+        """
+        def _native_binary_impl(ctx):
+            runfiles = ctx.runfiles(
+                transitive_files = depset(
+                    transitive = [target[DefaultInfo].files for target in ctx.attr.data],
+                ),
+            )
+            runfiles = runfiles.merge_all(
+                [target[DefaultInfo].default_runfiles for target in ctx.attr.data],
+            )
+            executable = ctx.actions.declare_file(ctx.label.name)
+            ctx.actions.symlink(
+                output = executable,
+                target_file = ctx.file.executable,
+            )
+            return [
+                DefaultInfo(
+                    executable = executable,
+                    runfiles = runfiles,
+                ),
+            ]
+
+        native_binary = rule(
+            implementation = _native_binary_impl,
+            attrs = {
+                "executable": attr.label(allow_single_file = True),
+                "data": attr.label_list(),
+            },
+            executable = True,
+        )
+        """);
+    write(
+        "a/BUILD",
+        """
+        load("//:native_binary.bzl", "native_binary")
+        load("//:output_dir.bzl", "output_dir")
+
+        output_dir(
+            name = "foo.out",
+            content_map = {"file-inside": "hello world"},
+        )
+
+        genrule(
+            name = "bar",
+            srcs = [
+                "foo.out",
+                "bar.in",
+            ],
+            outs = ["bar.out"],
+            cmd = "( ls $(location :foo.out); cat $(location :bar.in) ) > $@",
+        )
+
+        native_binary(
+            name = "bin",
+            executable = "bin.sh",
+            data = [
+                ":foo.out",
+                ":bar",
+            ],
+        )
+        """);
+    write("a/bar.in", "bar");
+    write("a/bin.sh");
+
+    // Populate remote cache
+    buildTarget("//a:bin");
+    getOutputPath("a/foo.out").deleteTreesBelow();
+    getOutputPath("a/bar.out").delete();
+    getOutputBase().getRelative("action_cache").deleteTreesBelow();
+    restartServer();
+
+    // Clean build, runfiles aren't downloaded
+    buildTarget("//a:bin");
+    assertThat(getOutputPath("a/bin.runfiles").isDirectory()).isTrue();
+    assertOutputDoesNotExist("a/bar.out");
+    assertOutputDoesNotExist("a/foo.out/file-inside");
+
+    // Act: Do an incremental build without "clean" or "shutdown" after clearing the cache and
+    // switching to download toplevel
+    evictAllBlobs();
+    setDownloadToplevel();
+    enableActionRewinding();
+    buildTarget("//a:bin");
+
+    // Assert: all runfiles were downloaded
+    assertValidOutputFile("a/bar.out", "file-inside\nbar\n");
+    assertValidOutputFile("a/foo.out/file-inside", "hello world");
+  }
+
   protected void restartServer() throws Exception {
     // Simulates a server restart
     createRuntimeWrapper();