diff --git a/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java b/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java
index 1afcd70..be99bbd 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java
@@ -169,11 +169,19 @@
   /**
    * Optional materialization path.
    *
-   * <p>If present, this artifact is a copy of another artifact. It is still tracked as a
-   * non-symlink by Bazel, but materialized in the local filesystem as a symlink to the original
-   * artifact, whose contents live at this location. This is used by {@link
-   * com.google.devtools.build.lib.remote.AbstractActionInputPrefetcher} to implement zero-cost
-   * copies of remotely stored artifacts.
+   * <p>If present, this artifact is a copy of another artifact whose contents live at this path.
+   * This can happen when it is declared as a file and not as an unresolved symlink but the action
+   * that creates it materializes it in the filesystem as a symlink to another output artifact. This
+   * information is useful in two situations:
+   *
+   * <ol>
+   *   <li>When the symlink target is a remotely stored artifact, we can avoid downloading it
+   *       multiple times when building without the bytes (see AbstractActionInputPrefetcher).
+   *   <li>When the symlink target is inaccessible from the sandboxed environment an action runs
+   *       under, we can rewrite it accordingly (see SandboxHelpers).
+   * </ol>
+   *
+   * @see com.google.devtools.build.lib.skyframe.TreeArtifactValue#getMaterializationExecPath().
    */
   public Optional<PathFragment> getMaterializationExecPath() {
     return Optional.empty();
@@ -214,6 +222,12 @@
         xattrProvider);
   }
 
+  public static FileArtifactValue createForResolvedSymlink(
+      PathFragment realPath, FileArtifactValue metadata, @Nullable byte[] digest) {
+    return new ResolvedSymlinkFileArtifactValue(
+        realPath, digest, metadata.getContentsProxy(), metadata.getSize());
+  }
+
   public static FileArtifactValue createFromInjectedDigest(
       FileArtifactValue metadata, @Nullable byte[] digest) {
     return createForNormalFile(digest, metadata.getContentsProxy(), metadata.getSize());
@@ -439,7 +453,25 @@
     }
   }
 
-  private static final class RegularFileArtifactValue extends FileArtifactValue {
+  private static final class ResolvedSymlinkFileArtifactValue extends RegularFileArtifactValue {
+    private final PathFragment realPath;
+
+    private ResolvedSymlinkFileArtifactValue(
+        PathFragment realPath,
+        @Nullable byte[] digest,
+        @Nullable FileContentsProxy proxy,
+        long size) {
+      super(digest, proxy, size);
+      this.realPath = realPath;
+    }
+
+    @Override
+    public Optional<PathFragment> getMaterializationExecPath() {
+      return Optional.of(realPath);
+    }
+  }
+
+  private static class RegularFileArtifactValue extends FileArtifactValue {
     private final byte[] digest;
     @Nullable private final FileContentsProxy proxy;
     private final long size;
@@ -462,7 +494,8 @@
       RegularFileArtifactValue that = (RegularFileArtifactValue) o;
       return Arrays.equals(digest, that.digest)
           && Objects.equals(proxy, that.proxy)
-          && size == that.size;
+          && size == that.size
+          && Objects.equals(getMaterializationExecPath(), that.getMaterializationExecPath());
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/BUILD b/src/main/java/com/google/devtools/build/lib/sandbox/BUILD
index 091dc91..9e92eb4 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/BUILD
@@ -17,6 +17,7 @@
     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:file_metadata",
         "//src/main/java/com/google/devtools/build/lib/analysis:test/test_configuration",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
         "//src/main/java/com/google/devtools/build/lib/vfs",
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedSpawnRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedSpawnRunner.java
index 40cd349..3ad9c32 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedSpawnRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedSpawnRunner.java
@@ -228,6 +228,7 @@
     SandboxInputs inputs =
         helpers.processInputFiles(
             context.getInputMapping(PathFragment.EMPTY_FRAGMENT, /* willAccessRepeatedly= */ true),
+            context.getInputMetadataProvider(),
             execRoot,
             execRoot,
             packageRoots,
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/DockerSandboxedSpawnRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/DockerSandboxedSpawnRunner.java
index 3dacaea..971b05c 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/DockerSandboxedSpawnRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/DockerSandboxedSpawnRunner.java
@@ -226,6 +226,7 @@
     SandboxInputs inputs =
         helpers.processInputFiles(
             context.getInputMapping(PathFragment.EMPTY_FRAGMENT, /* willAccessRepeatedly= */ true),
+            context.getInputMetadataProvider(),
             execRoot,
             execRoot,
             packageRoots,
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedSpawnRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedSpawnRunner.java
index df6f5fb..5e5e0a8 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedSpawnRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedSpawnRunner.java
@@ -280,6 +280,7 @@
     SandboxInputs inputs =
         helpers.processInputFiles(
             context.getInputMapping(PathFragment.EMPTY_FRAGMENT, /* willAccessRepeatedly= */ true),
+            context.getInputMetadataProvider(),
             execRoot,
             withinSandboxExecRoot,
             packageRoots,
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/ProcessWrapperSandboxedSpawnRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/ProcessWrapperSandboxedSpawnRunner.java
index a01a4e6..14d2a63 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/ProcessWrapperSandboxedSpawnRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/ProcessWrapperSandboxedSpawnRunner.java
@@ -100,6 +100,7 @@
     SandboxInputs inputs =
         helpers.processInputFiles(
             context.getInputMapping(PathFragment.EMPTY_FRAGMENT, /* willAccessRepeatedly= */ true),
+            context.getInputMetadataProvider(),
             execRoot,
             execRoot,
             packageRoots,
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxHelpers.java b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxHelpers.java
index fb72d59..dfc18bd 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxHelpers.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxHelpers.java
@@ -20,6 +20,7 @@
 import static com.google.devtools.build.lib.vfs.Dirent.Type.SYMLINK;
 
 import com.google.auto.value.AutoValue;
+import com.google.common.base.Function;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -29,6 +30,8 @@
 import com.google.common.flogger.GoogleLogger;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.FileArtifactValue;
+import com.google.devtools.build.lib.actions.InputMetadataProvider;
 import com.google.devtools.build.lib.actions.Spawn;
 import com.google.devtools.build.lib.actions.UserExecException;
 import com.google.devtools.build.lib.actions.cache.VirtualActionInput;
@@ -444,6 +447,29 @@
             symlink.getPathString()));
   }
 
+  private static RootedPath processResolvedSymlink(
+      Root absoluteRoot,
+      PathFragment execRootRelativeSymlinkTarget,
+      Root execRootWithinSandbox,
+      PathFragment execRootFragment,
+      ImmutableList<Root> packageRoots,
+      Function<Root, Root> sourceRooWithinSandbox) {
+    PathFragment symlinkTarget = execRootFragment.getRelative(execRootRelativeSymlinkTarget);
+    for (Root packageRoot : packageRoots) {
+      if (packageRoot.contains(symlinkTarget)) {
+        return RootedPath.toRootedPath(
+            sourceRooWithinSandbox.apply(packageRoot), packageRoot.relativize(symlinkTarget));
+      }
+    }
+
+    if (symlinkTarget.startsWith(execRootFragment)) {
+      return RootedPath.toRootedPath(
+          execRootWithinSandbox, symlinkTarget.relativeTo(execRootFragment));
+    }
+
+    return RootedPath.toRootedPath(absoluteRoot, symlinkTarget);
+  }
+
   /**
    * Returns the inputs of a Spawn as a map of PathFragments relative to an execRoot to paths in the
    * host filesystem where the input files can be found.
@@ -458,6 +484,7 @@
    */
   public SandboxInputs processInputFiles(
       Map<PathFragment, ActionInput> inputMap,
+      InputMetadataProvider inputMetadataProvider,
       Path execRootPath,
       Path withinSandboxExecRootPath,
       ImmutableList<Root> packageRoots,
@@ -468,12 +495,24 @@
         withinSandboxExecRootPath.equals(execRootPath)
             ? withinSandboxExecRoot
             : Root.fromPath(execRootPath);
+    Root absoluteRoot = Root.absoluteRoot(execRootPath.getFileSystem());
 
     Map<PathFragment, RootedPath> inputFiles = new TreeMap<>();
     Map<PathFragment, PathFragment> inputSymlinks = new TreeMap<>();
     Map<VirtualActionInput, byte[]> virtualInputs = new HashMap<>();
     Map<Root, Root> sourceRootToSandboxSourceRoot = new TreeMap<>();
 
+    Function<Root, Root> sourceRootWithinSandbox =
+        r -> {
+          if (!sourceRootToSandboxSourceRoot.containsKey(r)) {
+            int next = sourceRootToSandboxSourceRoot.size();
+            sourceRootToSandboxSourceRoot.put(
+                r, Root.fromPath(sandboxSourceRoots.getRelative(Integer.toString(next))));
+          }
+
+          return sourceRootToSandboxSourceRoot.get(r);
+        };
+
     for (Map.Entry<PathFragment, ActionInput> e : inputMap.entrySet()) {
       if (Thread.interrupted()) {
         throw new InterruptedException();
@@ -503,23 +542,63 @@
 
         if (actionInput instanceof EmptyActionInput) {
           inputPath = null;
+        } else if (actionInput instanceof VirtualActionInput) {
+          inputPath = RootedPath.toRootedPath(withinSandboxExecRoot, actionInput.getExecPath());
         } else if (actionInput instanceof Artifact) {
           Artifact inputArtifact = (Artifact) actionInput;
-          if (inputArtifact.isSourceArtifact() && sandboxSourceRoots != null) {
-            Root sourceRoot = inputArtifact.getRoot().getRoot();
-            if (!sourceRootToSandboxSourceRoot.containsKey(sourceRoot)) {
-              int next = sourceRootToSandboxSourceRoot.size();
-              sourceRootToSandboxSourceRoot.put(
-                  sourceRoot,
-                  Root.fromPath(sandboxSourceRoots.getRelative(Integer.toString(next))));
-            }
-
-            inputPath =
-                RootedPath.toRootedPath(
-                    sourceRootToSandboxSourceRoot.get(sourceRoot),
-                    inputArtifact.getRootRelativePath());
-          } else {
+          if (sandboxSourceRoots == null) {
             inputPath = RootedPath.toRootedPath(withinSandboxExecRoot, inputArtifact.getExecPath());
+          } else {
+            if (inputArtifact.isSourceArtifact()) {
+              Root sourceRoot = inputArtifact.getRoot().getRoot();
+              inputPath =
+                  RootedPath.toRootedPath(
+                      sourceRootWithinSandbox.apply(sourceRoot),
+                      inputArtifact.getRootRelativePath());
+            } else {
+              PathFragment materializationExecPath = null;
+              if (inputArtifact.isChildOfDeclaredDirectory()) {
+                FileArtifactValue parentMetadata =
+                    inputMetadataProvider.getInputMetadata(inputArtifact.getParent());
+                if (parentMetadata.getMaterializationExecPath().isPresent()) {
+                  materializationExecPath =
+                      parentMetadata
+                          .getMaterializationExecPath()
+                          .get()
+                          .getRelative(inputArtifact.getParentRelativePath());
+                }
+              } else if (!inputArtifact.isTreeArtifact()) {
+                // Normally, one would not see tree artifacts here because they have already been
+                // expanded by the time the code gets here. However, there is one very special case:
+                // when an action has an archived tree artifact on its output and is executed on the
+                // local branch of the dynamic execution strategy, the tree artifact is zipped up
+                // in a little extra spawn, which has direct tree artifact on its inputs. Sadly,
+                // it's not easy to fix this because there isn't an easy way to inject this new
+                // tree artifact into the artifact expander being used.
+                //
+                // The best would be to not rely on spawn strategies for executing that little
+                // command: it's entirely under the control of Bazel so we can guarantee that it
+                // does not cause mischief.
+                FileArtifactValue metadata = inputMetadataProvider.getInputMetadata(actionInput);
+                if (metadata.getMaterializationExecPath().isPresent()) {
+                  materializationExecPath = metadata.getMaterializationExecPath().get();
+                }
+              }
+
+              if (materializationExecPath != null) {
+                inputPath =
+                    processResolvedSymlink(
+                        absoluteRoot,
+                        materializationExecPath,
+                        withinSandboxExecRoot,
+                        execRootPath.asFragment(),
+                        packageRoots,
+                        sourceRootWithinSandbox);
+              } else {
+                inputPath =
+                    RootedPath.toRootedPath(withinSandboxExecRoot, inputArtifact.getExecPath());
+              }
+            }
           }
         } else {
           PathFragment execPath = actionInput.getExecPath();
@@ -544,6 +623,7 @@
     return new SandboxInputs(inputFiles, virtualInputs, inputSymlinks, sandboxRootToSourceRoot);
   }
 
+
   /** The file and directory outputs of a sandboxed spawn. */
   @AutoValue
   public abstract static class SandboxOutputs {
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/WindowsSandboxedSpawnRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/WindowsSandboxedSpawnRunner.java
index c7996e3..505e241 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/WindowsSandboxedSpawnRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/WindowsSandboxedSpawnRunner.java
@@ -76,6 +76,7 @@
     SandboxInputs readablePaths =
         helpers.processInputFiles(
             context.getInputMapping(PathFragment.EMPTY_FRAGMENT, /* willAccessRepeatedly= */ true),
+            context.getInputMetadataProvider(),
             execRoot,
             execRoot,
             packageRoots,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionOutputMetadataStore.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionOutputMetadataStore.java
index a1b1a77..1bc2f4c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionOutputMetadataStore.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionOutputMetadataStore.java
@@ -264,7 +264,15 @@
     Path treeDir = artifactPathResolver.toPath(parent);
     boolean chmod = executionMode.get();
 
-    FileStatus stat = treeDir.statIfFound(Symlinks.FOLLOW);
+    FileStatus lstat = treeDir.statIfFound(Symlinks.NOFOLLOW);
+    FileStatus stat;
+    if (lstat == null) {
+      stat = null;
+    } else if (!lstat.isSymbolicLink()) {
+      stat = lstat;
+    } else {
+      stat = treeDir.statIfFound(Symlinks.FOLLOW);
+    }
 
     // Make sure the tree artifact root exists and is a regular directory. Note that this is how the
     // action is initialized, so this should hold unless the action itself has deleted the root.
@@ -332,12 +340,18 @@
     }
 
     // Same rationale as for constructFileArtifactValue.
-    if (anyRemote.get() && treeDir.isSymbolicLink() && stat instanceof FileStatusWithMetadata) {
-      FileArtifactValue metadata = ((FileStatusWithMetadata) stat).getMetadata();
-      tree.setMaterializationExecPath(
-          metadata
-              .getMaterializationExecPath()
-              .orElse(treeDir.resolveSymbolicLinks().asFragment().relativeTo(execRoot)));
+    if (lstat.isSymbolicLink()) {
+      PathFragment materializationExecPath = null;
+      if (stat instanceof FileStatusWithMetadata) {
+        materializationExecPath =
+            ((FileStatusWithMetadata) stat).getMetadata().getMaterializationExecPath().orElse(null);
+      }
+
+      if (materializationExecPath == null) {
+        materializationExecPath = treeDir.resolveSymbolicLinks().asFragment().relativeTo(execRoot);
+      }
+
+      tree.setMaterializationExecPath(materializationExecPath);
     }
 
     return tree.build();
@@ -509,7 +523,13 @@
       return value;
     }
 
-    if (type.isFile() && fileDigest != null) {
+    boolean isResolvedSymlink =
+        statAndValue.statNoFollow() != null
+            && statAndValue.statNoFollow().isSymbolicLink()
+            && statAndValue.realPath() != null
+            && !value.isRemote();
+
+    if (type.isFile() && !isResolvedSymlink && fileDigest != null) {
       // The digest is in the file value and that is all that is needed for this file's metadata.
       return value;
     }
@@ -525,22 +545,30 @@
           artifactPathResolver.toPath(artifact).getLastModifiedTime());
     }
 
-    if (injectedDigest == null && type.isFile()) {
+    byte[] actualDigest = fileDigest != null ? fileDigest : injectedDigest;
+
+    if (actualDigest == null && type.isFile()) {
       // We don't have an injected digest and there is no digest in the file value (which attempts a
       // fast digest). Manually compute the digest instead.
-      Path path = statAndValue.pathNoFollow();
-      if (statAndValue.statNoFollow() != null
-          && statAndValue.statNoFollow().isSymbolicLink()
-          && statAndValue.realPath() != null) {
-        // If the file is a symlink, we compute the digest using the target path so that it's
-        // possible to hit the digest cache - we probably already computed the digest for the
-        // target during previous action execution.
-        path = statAndValue.realPath();
-      }
 
-      injectedDigest = DigestUtils.manuallyComputeDigest(path, value.getSize());
+      // If the file is a symlink, we compute the digest using the target path so that it's
+      // possible to hit the digest cache - we probably already computed the digest for the
+      // target during previous action execution.
+      Path pathToDigest = isResolvedSymlink ? statAndValue.realPath() : statAndValue.pathNoFollow();
+      actualDigest = DigestUtils.manuallyComputeDigest(pathToDigest, value.getSize());
     }
-    return FileArtifactValue.createFromInjectedDigest(value, injectedDigest);
+
+    if (!isResolvedSymlink) {
+      return FileArtifactValue.createFromInjectedDigest(value, actualDigest);
+    }
+
+    PathFragment realPathAsFragment = statAndValue.realPath().asFragment();
+    PathFragment execRootRelativeRealPath =
+        realPathAsFragment.startsWith(execRoot)
+            ? realPathAsFragment.relativeTo(execRoot)
+            : realPathAsFragment;
+    return FileArtifactValue.createForResolvedSymlink(
+        execRootRelativeRealPath, value, actualDigest);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/worker/WorkerSpawnRunner.java b/src/main/java/com/google/devtools/build/lib/worker/WorkerSpawnRunner.java
index 6718b7e..c21eb8e 100644
--- a/src/main/java/com/google/devtools/build/lib/worker/WorkerSpawnRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/worker/WorkerSpawnRunner.java
@@ -188,6 +188,7 @@
             helpers.processInputFiles(
                 context.getInputMapping(
                     PathFragment.EMPTY_FRAGMENT, /* willAccessRepeatedly= */ true),
+                context.getInputMetadataProvider(),
                 execRoot,
                 execRoot,
                 packageRoots,
diff --git a/src/test/java/com/google/devtools/build/lib/sandbox/BUILD b/src/test/java/com/google/devtools/build/lib/sandbox/BUILD
index 74873ef..671997d 100644
--- a/src/test/java/com/google/devtools/build/lib/sandbox/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/sandbox/BUILD
@@ -59,12 +59,14 @@
     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:file_metadata",
         "//src/main/java/com/google/devtools/build/lib/exec:bin_tools",
         "//src/main/java/com/google/devtools/build/lib/exec:tree_deleter",
         "//src/main/java/com/google/devtools/build/lib/sandbox:sandbox_helpers",
         "//src/main/java/com/google/devtools/build/lib/sandbox:sandbox_options",
         "//src/main/java/com/google/devtools/build/lib/sandbox:sandboxed_spawns",
         "//src/main/java/com/google/devtools/build/lib/sandbox:tree_deleter",
+        "//src/main/java/com/google/devtools/build/lib/skyframe:tree_artifact_value",
         "//src/main/java/com/google/devtools/build/lib/vfs",
         "//src/main/java/com/google/devtools/build/lib/vfs:pathfragment",
         "//src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs",
diff --git a/src/test/java/com/google/devtools/build/lib/sandbox/SandboxHelpersTest.java b/src/test/java/com/google/devtools/build/lib/sandbox/SandboxHelpersTest.java
index 8df8447..78fe5c2 100644
--- a/src/test/java/com/google/devtools/build/lib/sandbox/SandboxHelpersTest.java
+++ b/src/test/java/com/google/devtools/build/lib/sandbox/SandboxHelpersTest.java
@@ -24,17 +24,23 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionInput;
+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.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.CommandLines.ParamFileActionInput;
+import com.google.devtools.build.lib.actions.FileArtifactValue;
 import com.google.devtools.build.lib.actions.ParameterFile.ParameterFileType;
 import com.google.devtools.build.lib.actions.PathMapper;
 import com.google.devtools.build.lib.actions.Spawn;
 import com.google.devtools.build.lib.actions.cache.VirtualActionInput;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.exec.BinTools;
+import com.google.devtools.build.lib.exec.util.FakeActionInputFileCache;
 import com.google.devtools.build.lib.exec.util.SpawnBuilder;
 import com.google.devtools.build.lib.sandbox.SandboxHelpers.SandboxInputs;
 import com.google.devtools.build.lib.sandbox.SandboxHelpers.SandboxOutputs;
+import com.google.devtools.build.lib.skyframe.TreeArtifactValue;
 import com.google.devtools.build.lib.testutil.Scratch;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import com.google.devtools.build.lib.vfs.DigestHashFunction;
@@ -68,6 +74,7 @@
 /** Tests for {@link SandboxHelpers}. */
 @RunWith(JUnit4.class)
 public class SandboxHelpersTest {
+  private static final byte[] FAKE_DIGEST = new byte[] {1};
 
   private final Scratch scratch = new Scratch();
   private Path execRootPath;
@@ -95,6 +102,79 @@
   }
 
   @Test
+  public void processInputFiles_resolvesMaterializationPath_fileArtifact() throws Exception {
+    ArtifactRoot outputRoot =
+        ArtifactRoot.asDerivedRoot(execRootPath, ArtifactRoot.RootType.Output, "outputs");
+    Path sandboxSourceRoot = scratch.dir("/faketmp/sandbox-source-roots");
+
+    Artifact input = ActionsTestUtil.createArtifact(outputRoot, "a/a");
+    FileArtifactValue symlinkTargetMetadata =
+        FileArtifactValue.createForNormalFile(FAKE_DIGEST, null, 0L);
+    FileArtifactValue inputMetadata =
+        FileArtifactValue.createForResolvedSymlink(
+            PathFragment.create("b/b"), symlinkTargetMetadata, FAKE_DIGEST);
+
+    FakeActionInputFileCache inputMetadataProvider = new FakeActionInputFileCache();
+    inputMetadataProvider.put(input, inputMetadata);
+
+    SandboxHelpers sandboxHelpers = new SandboxHelpers();
+    SandboxInputs inputs =
+        sandboxHelpers.processInputFiles(
+            inputMap(input),
+            inputMetadataProvider,
+            execRootPath,
+            execRootPath,
+            ImmutableList.of(),
+            sandboxSourceRoot);
+
+    assertThat(inputs.getFiles())
+        .containsEntry(
+            input.getExecPath(), RootedPath.toRootedPath(execRoot, PathFragment.create("b/b")));
+  }
+
+  @Test
+  public void processInputFiles_resolvesMaterializationPath_treeArtifact() throws Exception {
+    ArtifactRoot outputRoot =
+        ArtifactRoot.asDerivedRoot(execRootPath, ArtifactRoot.RootType.Output, "outputs");
+    Path sandboxSourceRoot = scratch.dir("/faketmp/sandbox-source-roots");
+    SpecialArtifact parent =
+        ActionsTestUtil.createTreeArtifactWithGeneratingAction(
+            outputRoot, "bin/config/other_dir/subdir");
+
+    TreeFileArtifact childA = TreeFileArtifact.createTreeOutput(parent, "a/a");
+    TreeFileArtifact childB = TreeFileArtifact.createTreeOutput(parent, "b/b");
+    FileArtifactValue childMetadata = FileArtifactValue.createForNormalFile(FAKE_DIGEST, null, 0L);
+    TreeArtifactValue parentMetadata =
+        TreeArtifactValue.newBuilder(parent)
+            .putChild(childA, childMetadata)
+            .putChild(childB, childMetadata)
+            .setMaterializationExecPath(PathFragment.create("materialized"))
+            .build();
+
+    FakeActionInputFileCache inputMetadataProvider = new FakeActionInputFileCache();
+    inputMetadataProvider.put(parent, parentMetadata.getMetadata());
+
+    SandboxHelpers sandboxHelpers = new SandboxHelpers();
+    SandboxInputs inputs =
+        sandboxHelpers.processInputFiles(
+            inputMap(childA, childB),
+            inputMetadataProvider,
+            execRootPath,
+            execRootPath,
+            ImmutableList.of(),
+            sandboxSourceRoot);
+
+    assertThat(inputs.getFiles())
+        .containsEntry(
+            childA.getExecPath(),
+            RootedPath.toRootedPath(execRoot, PathFragment.create("materialized/a/a")));
+    assertThat(inputs.getFiles())
+        .containsEntry(
+            childB.getExecPath(),
+            RootedPath.toRootedPath(execRoot, PathFragment.create("materialized/b/b")));
+  }
+
+  @Test
   public void processInputFiles_materializesParamFile() throws Exception {
     SandboxHelpers sandboxHelpers = new SandboxHelpers();
     ParamFileActionInput paramFile =
@@ -106,7 +186,12 @@
 
     SandboxInputs inputs =
         sandboxHelpers.processInputFiles(
-            inputMap(paramFile), execRootPath, execRootPath, ImmutableList.of(), null);
+            inputMap(paramFile),
+            new FakeActionInputFileCache(),
+            execRootPath,
+            execRootPath,
+            ImmutableList.of(),
+            null);
 
     assertThat(inputs.getFiles())
         .containsExactly(PathFragment.create("paramFile"), execRootedPath("paramFile"));
@@ -127,7 +212,12 @@
 
     SandboxInputs inputs =
         sandboxHelpers.processInputFiles(
-            inputMap(tool), execRootPath, execRootPath, ImmutableList.of(), null);
+            inputMap(tool),
+            new FakeActionInputFileCache(),
+            execRootPath,
+            execRootPath,
+            ImmutableList.of(),
+            null);
 
     assertThat(inputs.getFiles())
         .containsExactly(PathFragment.create("_bin/say_hello"), execRootedPath("_bin/say_hello"));
@@ -173,7 +263,12 @@
               try {
                 var unused =
                     sandboxHelpers.processInputFiles(
-                        inputMap(input), customExecRoot, customExecRoot, ImmutableList.of(), null);
+                        inputMap(input),
+                        new FakeActionInputFileCache(),
+                        customExecRoot,
+                        customExecRoot,
+                        ImmutableList.of(),
+                        null);
                 finishProcessingSemaphore.release();
               } catch (IOException | InterruptedException e) {
                 throw new IllegalArgumentException(e);
@@ -181,7 +276,12 @@
             });
     var unused =
         sandboxHelpers.processInputFiles(
-            inputMap(input), customExecRoot, customExecRoot, ImmutableList.of(), null);
+            inputMap(input),
+            new FakeActionInputFileCache(),
+            customExecRoot,
+            customExecRoot,
+            ImmutableList.of(),
+            null);
     finishProcessingSemaphore.release();
     future.get();
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionOutputMetadataStoreTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionOutputMetadataStoreTest.java
index 430e809..afcf828 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ActionOutputMetadataStoreTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionOutputMetadataStoreTest.java
@@ -82,10 +82,6 @@
     FULLY_LOCAL,
     FULLY_REMOTE,
     MIXED;
-
-    boolean isPartiallyRemote() {
-      return this == FULLY_REMOTE || this == MIXED;
-    }
   }
 
   private final Map<Path, Integer> chmodCalls = Maps.newConcurrentMap();
@@ -422,11 +418,10 @@
         .getPath(outputArtifact.getPath().getPathString())
         .createSymbolicLink(targetArtifact.getPath().asFragment());
 
-    PathFragment expectedMaterializationExecPath = null;
-    if (location == FileLocation.REMOTE) {
-      expectedMaterializationExecPath =
-          preexistingPath != null ? preexistingPath : targetArtifact.getExecPath();
-    }
+    PathFragment expectedMaterializationExecPath =
+        location == FileLocation.REMOTE && preexistingPath != null
+            ? preexistingPath
+            : targetArtifact.getExecPath();
 
     assertThat(store.getOutputMetadata(outputArtifact))
         .isEqualTo(createFileMetadataForSymlinkTest(location, expectedMaterializationExecPath));
@@ -436,7 +431,12 @@
       FileLocation location, @Nullable PathFragment materializationExecPath) {
     switch (location) {
       case LOCAL:
-        return FileArtifactValue.createForNormalFile(new byte[] {1, 2, 3}, /* proxy= */ null, 10);
+        FileArtifactValue target =
+            FileArtifactValue.createForNormalFile(new byte[] {1, 2, 3}, /* proxy= */ null, 10);
+        return materializationExecPath == null
+            ? target
+            : FileArtifactValue.createForResolvedSymlink(
+                materializationExecPath, target, target.getDigest());
       case REMOTE:
         return RemoteFileArtifactValue.create(
             new byte[] {1, 2, 3}, 10, 1, -1, materializationExecPath);
@@ -481,11 +481,8 @@
         .getPath(outputArtifact.getPath().getPathString())
         .createSymbolicLink(targetArtifact.getPath().asFragment());
 
-    PathFragment expectedMaterializationExecPath = null;
-    if (composition.isPartiallyRemote()) {
-      expectedMaterializationExecPath =
-          preexistingPath != null ? preexistingPath : targetArtifact.getExecPath();
-    }
+    PathFragment expectedMaterializationExecPath =
+        preexistingPath != null ? preexistingPath : targetArtifact.getExecPath();
 
     assertThat(store.getTreeArtifactValue(outputArtifact))
         .isEqualTo(
@@ -814,7 +811,7 @@
 
     var symlinkMetadata = store.getOutputMetadata(symlink);
 
-    assertThat(symlinkMetadata).isEqualTo(targetMetadata);
+    assertThat(symlinkMetadata.getDigest()).isEqualTo(targetMetadata.getDigest());
     assertThat(DigestUtils.getCacheStats().hitCount()).isEqualTo(1);
   }
 }
diff --git a/src/test/shell/bazel/bazel_sandboxing_test.sh b/src/test/shell/bazel/bazel_sandboxing_test.sh
index 3e65184..86fa7ad 100755
--- a/src/test/shell/bazel/bazel_sandboxing_test.sh
+++ b/src/test/shell/bazel/bazel_sandboxing_test.sh
@@ -334,6 +334,95 @@
   assert_contains GOOD bazel-bin/pkg/gen.txt
 }
 
+function test_symlink_with_output_base_under_tmp() {
+  if [[ "$PLATFORM" == "darwin" ]]; then
+    # Tests Linux-specific functionality
+    return 0
+  fi
+
+  create_workspace_with_default_repos WORKSPACE
+
+  sed -i.bak '/sandbox_tmpfs_path/d' $TEST_TMPDIR/bazelrc
+
+  mkdir -p pkg
+  cat > pkg/BUILD <<'EOF'
+load(":r.bzl", "symlink_rule")
+
+genrule(name="r1", srcs=[], outs=[":r1"], cmd="echo CONTENT > $@")
+symlink_rule(name="r2", input=":r1")
+genrule(name="r3", srcs=[":r2"], outs=[":r3"], cmd="cp $< $@")
+EOF
+
+  cat > pkg/r.bzl <<'EOF'
+def _symlink_impl(ctx):
+  output = ctx.actions.declare_file(ctx.label.name)
+  ctx.actions.symlink(output = output, target_file = ctx.file.input)
+  return [DefaultInfo(files = depset([output]))]
+
+symlink_rule = rule(
+  implementation = _symlink_impl,
+  attrs = {"input": attr.label(allow_single_file=True)})
+EOF
+
+  local tmp_output_base=$(mktemp -d "/tmp/bazel_output_base.XXXXXXXX")
+  trap "chmod -R u+w $tmp_output_base && rm -fr $tmp_output_base" EXIT
+
+  bazel --output_base="$tmp_output_base" build //pkg:r3
+  assert_contains CONTENT bazel-bin/pkg/r3
+  bazel --output_base="$tmp_output_base" shutdown
+}
+
+function test_symlink_to_directory_with_output_base_under_tmp() {
+  if [[ "$PLATFORM" == "darwin" ]]; then
+    # Tests Linux-specific functionality
+    return 0
+  fi
+
+  create_workspace_with_default_repos WORKSPACE
+
+  sed -i.bak '/sandbox_tmpfs_path/d' $TEST_TMPDIR/bazelrc
+
+  mkdir -p pkg
+  cat > pkg/BUILD <<'EOF'
+load(":r.bzl", "symlink_rule", "tree_rule")
+
+tree_rule(name="t1")
+symlink_rule(name="t2", input=":t1")
+genrule(name="t3", srcs=[":t2"], outs=[":t3"], cmd=";\n".join(
+    ["cat $(location :t2)/{a/a,b/b} > $@"]))
+EOF
+
+  cat > pkg/r.bzl <<'EOF'
+def _symlink_impl(ctx):
+  output = ctx.actions.declare_directory(ctx.label.name)
+  ctx.actions.symlink(output = output, target_file = ctx.file.input)
+  return [DefaultInfo(files = depset([output]))]
+
+symlink_rule = rule(
+  implementation = _symlink_impl,
+  attrs = {"input": attr.label(allow_single_file=True)})
+
+def _tree_impl(ctx):
+  output = ctx.actions.declare_directory(ctx.label.name)
+  ctx.actions.run_shell(
+    outputs = [output],
+    command = "export TREE=%s && mkdir $TREE/a $TREE/b && echo -n A > $TREE/a/a && echo -n B > $TREE/b/b" % output.path)
+  return [DefaultInfo(files = depset([output]))]
+
+tree_rule = rule(
+  implementation = _tree_impl,
+  attrs = {})
+
+EOF
+
+  local tmp_output_base=$(mktemp -d "/tmp/bazel_output_base.XXXXXXXX")
+  trap "chmod -R u+w $tmp_output_base && rm -fr $tmp_output_base" EXIT
+
+  bazel --output_base="$tmp_output_base" build //pkg:t3
+  assert_contains AB bazel-bin/pkg/t3
+  bazel --output_base="$tmp_output_base" shutdown
+}
+
 # The test shouldn't fail if the environment doesn't support running it.
 check_sandbox_allowed || exit 0