Improving efficiency of fileset builds by using previously stat'd FileStatus, reducing the number of file system calls.

RELNOTES: None.
PiperOrigin-RevId: 277502268
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 0ca74a6..2b76b3f 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
@@ -102,7 +102,6 @@
     return null;
   }
 
-
   /**
    * Index used to resolve remote files.
    *
@@ -279,6 +278,15 @@
         : new UnshareableRegularFileArtifactValue(digest, proxy, size);
   }
 
+  /**
+   * Create a FileArtifactValue using the {@link Path} and size. FileArtifactValue#create will
+   * handle getting the digest using the Path and size values.
+   */
+  public static FileArtifactValue createForNormalFileUsingPath(Path path, long size)
+      throws IOException {
+    return create(path, true, size, null, null, true);
+  }
+
   public static FileArtifactValue createForDirectoryWithHash(byte[] digest) {
     return new HashedDirectoryArtifactValue(digest);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index 18d79e9..6ab70fc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -268,7 +268,8 @@
       Preconditions.checkState(!state.hasArtifactData(), "%s %s", state, action);
       state.inputArtifactData = checkedInputs.actionInputMap;
       state.expandedArtifacts = checkedInputs.expandedArtifacts;
-      state.expandedFilesets = checkedInputs.expandedFilesets;
+      state.filesetsInsideRunfiles = checkedInputs.filesetsInsideRunfiles;
+      state.topLevelFilesets = checkedInputs.topLevelFilesets;
       if (skyframeActionExecutor.actionFileSystemType().isEnabled()) {
         state.actionFileSystem =
             skyframeActionExecutor.createActionFileSystem(
@@ -675,6 +676,17 @@
           skyframeActionExecutor.getSharedActionCallback(
               env.getListener(), state.discoveredInputs != null, action, actionLookupData));
     }
+
+    ImmutableMap<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets;
+    if (state.topLevelFilesets == null || state.topLevelFilesets.isEmpty()) {
+      expandedFilesets = ImmutableMap.copyOf(state.filesetsInsideRunfiles);
+    } else {
+      Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetsMap =
+          new HashMap<>(state.filesetsInsideRunfiles);
+      filesetsMap.putAll(state.topLevelFilesets);
+      expandedFilesets = ImmutableMap.copyOf(filesetsMap);
+    }
+
     // The metadataHandler may be recreated if we discover inputs.
     ArtifactPathResolver pathResolver =
         ArtifactPathResolver.createPathResolver(
@@ -682,11 +694,13 @@
     ActionMetadataHandler metadataHandler =
         new ActionMetadataHandler(
             state.inputArtifactData,
+            expandedFilesets,
             /* missingArtifactsAllowed= */ action.discoversInputs(),
             action.getOutputs(),
             tsgm.get(),
             pathResolver,
-            newOutputStore(state));
+            newOutputStore(state),
+            skyframeActionExecutor.getExecRoot());
     // We only need to check the action cache if we haven't done it on a previous run.
     if (!state.hasCheckedActionCache()) {
       state.token =
@@ -773,40 +787,18 @@
           metadataHandler =
               new ActionMetadataHandler(
                   state.inputArtifactData,
+                  expandedFilesets,
                   /*missingArtifactsAllowed=*/ false,
                   action.getOutputs(),
                   tsgm.get(),
                   pathResolver,
-                  newOutputStore(state));
+                  newOutputStore(state),
+                  skyframeActionExecutor.getExecRoot());
           // Set the MetadataHandler to accept output information.
           metadataHandler.discardOutputMetadata();
       }
     }
 
-    // Make sure this is a regular HashMap rather than ImmutableMapBuilder so that we are safe
-    // in case of collisions.
-    Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetMappings = new HashMap<>();
-    for (Artifact actionInput : action.getInputs()) {
-      if (!actionInput.isFileset()) {
-        continue;
-      }
-
-      ImmutableList<FilesetOutputSymlink> mapping =
-          ActionInputMapHelper.getFilesets(env, (Artifact.SpecialArtifact) actionInput);
-      if (mapping == null) {
-        return null;
-      }
-      filesetMappings.put(actionInput, mapping);
-    }
-
-    ImmutableMap<Artifact, ImmutableList<FilesetOutputSymlink>> topLevelFilesets =
-        ImmutableMap.copyOf(filesetMappings);
-
-    // Aggregate top-level Filesets with Filesets nested in Runfiles. Both should be used to update
-    // the FileSystem context.
-    state.expandedFilesets.forEach(filesetMappings::put);
-    ImmutableMap<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets =
-        ImmutableMap.copyOf(filesetMappings);
     try {
       state.updateFileSystemContext(skyframeActionExecutor, env, metadataHandler, expandedFilesets);
     } catch (IOException e) {
@@ -826,7 +818,7 @@
                 : SkyframeActionExecutor.ProgressEventBehavior.EMIT,
             Collections.unmodifiableMap(state.expandedArtifacts),
             expandedFilesets,
-            topLevelFilesets,
+            ImmutableMap.copyOf(state.topLevelFilesets),
             state.actionFileSystem,
             skyframeDepsResult)) {
       return skyframeActionExecutor.executeAction(
@@ -884,14 +876,19 @@
             // We are in the interesting case of an action that discovered its inputs during
             // execution, and found some new ones, but the new ones were already present in the
             // graph. We must therefore cache the metadata for those new ones.
+            Map<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets =
+                new HashMap<>(state.filesetsInsideRunfiles);
+            expandedFilesets.putAll(state.topLevelFilesets);
             metadataHandler =
                 new ActionMetadataHandler(
                     state.inputArtifactData,
+                    expandedFilesets,
                     /*missingArtifactsAllowed=*/ false,
                     action.getOutputs(),
                     tsgm.get(),
                     metadataHandler.getArtifactPathResolver(),
-                    metadataHandler.getOutputStore());
+                    metadataHandler.getOutputStore(),
+                    skyframeActionExecutor.getExecRoot());
         }
       }
       Preconditions.checkState(!env.valuesMissing(), action);
@@ -990,15 +987,19 @@
     /** Artifact expansion mapping for Runfiles tree and tree artifacts. */
     private final Map<Artifact, Collection<Artifact>> expandedArtifacts;
     /** Artifact expansion mapping for Filesets embedded in Runfiles. */
-    private final Map<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets;
+    private final Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetsInsideRunfiles;
+    /** Artifact expansion mapping for top level filesets. */
+    private final Map<Artifact, ImmutableList<FilesetOutputSymlink>> topLevelFilesets;
 
     public CheckInputResults(
         ActionInputMap actionInputMap,
         Map<Artifact, Collection<Artifact>> expandedArtifacts,
-        Map<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets) {
+        Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetsInsideRunfiles,
+        Map<Artifact, ImmutableList<FilesetOutputSymlink>> topLevelFilesets) {
       this.actionInputMap = actionInputMap;
       this.expandedArtifacts = expandedArtifacts;
-      this.expandedFilesets = expandedFilesets;
+      this.filesetsInsideRunfiles = filesetsInsideRunfiles;
+      this.topLevelFilesets = topLevelFilesets;
     }
   }
 
@@ -1006,7 +1007,8 @@
     R create(
         S actionInputMapSink,
         Map<Artifact, Collection<Artifact>> expandedArtifacts,
-        Map<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets);
+        Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetsInsideRunfiles,
+        Map<Artifact, ImmutableList<FilesetOutputSymlink>> topLevelFilesets);
   }
 
   /**
@@ -1048,7 +1050,8 @@
         allInputs,
         mandatoryInputs,
         ignoredInputDepsSize -> new ActionInputDepOwnerMap(lostInputs),
-        (actionInputMapSink, expandedArtifacts, expandedFilesets) -> actionInputMapSink);
+        (actionInputMapSink, expandedArtifacts, filesetsInsideRunfiles, topLevelFilesets) ->
+            actionInputMapSink);
   }
 
   private static <S extends ActionInputMapSink, R> R accumulateInputs(
@@ -1071,7 +1074,8 @@
     S inputArtifactData = actionInputMapSinkFactory.apply(populateInputData ? inputDeps.size() : 0);
     Map<Artifact, Collection<Artifact>> expandedArtifacts =
         new HashMap<>(populateInputData ? 128 : 0);
-    Map<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets = new HashMap<>();
+    Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetsInsideRunfiles = new HashMap<>();
+    Map<Artifact, ImmutableList<FilesetOutputSymlink>> topLevelFilesets = new HashMap<>();
 
     ActionExecutionException firstActionExecutionException = null;
     for (Artifact input : allInputs) {
@@ -1140,7 +1144,13 @@
 
       if (populateInputData) {
         ActionInputMapHelper.addToMap(
-            inputArtifactData, expandedArtifacts, expandedFilesets, input, value, env);
+            inputArtifactData,
+            expandedArtifacts,
+            filesetsInsideRunfiles,
+            topLevelFilesets,
+            input,
+            value,
+            env);
       }
     }
 
@@ -1177,7 +1187,7 @@
           /*catastrophe=*/ false);
     }
     return accumulateInputResultsFactory.create(
-        inputArtifactData, expandedArtifacts, expandedFilesets);
+        inputArtifactData, expandedArtifacts, filesetsInsideRunfiles, topLevelFilesets);
   }
 
   private static Iterable<Artifact> filterKnownInputs(
@@ -1243,7 +1253,8 @@
     ActionInputMap inputArtifactData = null;
 
     Map<Artifact, Collection<Artifact>> expandedArtifacts = null;
-    Map<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets = null;
+    Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetsInsideRunfiles = null;
+    Map<Artifact, ImmutableList<FilesetOutputSymlink>> topLevelFilesets = null;
     Token token = null;
     Iterable<Artifact> discoveredInputs = null;
     FileSystem actionFileSystem = null;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionInputMapHelper.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionInputMapHelper.java
index be4cc99..ed08925 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionInputMapHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionInputMapHelper.java
@@ -39,7 +39,8 @@
   static void addToMap(
       ActionInputMapSink inputMap,
       Map<Artifact, Collection<Artifact>> expandedArtifacts,
-      Map<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets,
+      Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetsInsideRunfiles,
+      Map<Artifact, ImmutableList<FilesetOutputSymlink>> topLevelFilesets,
       Artifact key,
       SkyValue value,
       Environment env)
@@ -53,7 +54,7 @@
           ImmutableList<FilesetOutputSymlink> expandedFileset =
               getFilesets(env, (Artifact.SpecialArtifact) artifact);
           if (expandedFileset != null) {
-            expandedFilesets.put(artifact, expandedFileset);
+            filesetsInsideRunfiles.put(artifact, expandedFileset);
           }
         }
       }
@@ -90,6 +91,9 @@
           ArtifactFunction.createSimpleFileArtifactValue(
               (Artifact.DerivedArtifact) key, (ActionExecutionValue) value),
           key);
+      if (key.isFileset()) {
+        topLevelFilesets.put(key, getFilesets(env, (Artifact.SpecialArtifact) key));
+      }
     } else {
       Preconditions.checkState(value instanceof FileArtifactValue);
       inputMap.put(key, (FileArtifactValue) value, /*depOwner=*/ key);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
index 55840fb..3c1a85d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
@@ -32,6 +32,9 @@
 import com.google.devtools.build.lib.actions.FileArtifactValue.RemoteFileArtifactValue;
 import com.google.devtools.build.lib.actions.FileStateType;
 import com.google.devtools.build.lib.actions.FileStateValue;
+import com.google.devtools.build.lib.actions.FilesetManifest;
+import com.google.devtools.build.lib.actions.FilesetManifest.RelativeSymlinkBehavior;
+import com.google.devtools.build.lib.actions.FilesetOutputSymlink;
 import com.google.devtools.build.lib.actions.cache.DigestUtils;
 import com.google.devtools.build.lib.actions.cache.MetadataHandler;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
@@ -48,9 +51,11 @@
 import java.io.IOException;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.logging.Logger;
 import javax.annotation.Nullable;
 
 /**
@@ -75,6 +80,8 @@
 @VisibleForTesting
 public final class ActionMetadataHandler implements MetadataHandler {
 
+  private static final Logger logger = Logger.getLogger(ActionMetadataHandler.class.getName());
+
   /**
    * Data for input artifacts. Immutable.
    *
@@ -82,6 +89,7 @@
    */
   private final ActionInputMap inputArtifactData;
   private final boolean missingArtifactsAllowed;
+  private final ImmutableMap<PathFragment, FileArtifactValue> filesetMapping;
 
   /** Outputs that are to be omitted. */
   private final Set<Artifact> omittedOutputs = Sets.newConcurrentHashSet();
@@ -95,10 +103,11 @@
   @Nullable
   private final TimestampGranularityMonitor tsgm;
   private final ArtifactPathResolver artifactPathResolver;
+  private final Path execRoot;
 
   /**
-   * Whether the action is being executed or not; this flag is set to true in
-   * {@link #discardOutputMetadata}.
+   * Whether the action is being executed or not; this flag is set to true in {@link
+   * #discardOutputMetadata}.
    */
   private final AtomicBoolean executionMode = new AtomicBoolean(false);
 
@@ -107,16 +116,20 @@
   @VisibleForTesting
   public ActionMetadataHandler(
       ActionInputMap inputArtifactData,
+      Map<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets,
       boolean missingArtifactsAllowed,
       Iterable<Artifact> outputs,
       @Nullable TimestampGranularityMonitor tsgm,
       ArtifactPathResolver artifactPathResolver,
-      OutputStore store)  {
+      OutputStore store,
+      Path execRoot) {
     this.inputArtifactData = Preconditions.checkNotNull(inputArtifactData);
     this.missingArtifactsAllowed = missingArtifactsAllowed;
     this.outputs = ImmutableSet.copyOf(outputs);
     this.tsgm = tsgm;
     this.artifactPathResolver = artifactPathResolver;
+    this.execRoot = execRoot;
+    this.filesetMapping = expandFilesetMapping(Preconditions.checkNotNull(expandedFilesets));
     this.store = store;
   }
 
@@ -143,6 +156,34 @@
     return value;
   }
 
+  private ImmutableMap<PathFragment, FileArtifactValue> expandFilesetMapping(
+      Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesets) {
+    if (execRoot == null) {
+      return ImmutableMap.of();
+    }
+
+    Map<PathFragment, FileArtifactValue> filesetMap = new HashMap<>();
+    for (Map.Entry<Artifact, ImmutableList<FilesetOutputSymlink>> entry : filesets.entrySet()) {
+      try {
+        FilesetManifest fileset =
+            FilesetManifest.constructFilesetManifest(
+                entry.getValue(), execRoot.asFragment(), RelativeSymlinkBehavior.RESOLVE);
+        for (Map.Entry<String, FileArtifactValue> favEntry :
+            fileset.getArtifactValues().entrySet()) {
+          if (favEntry.getValue().getDigest() != null) {
+            filesetMap.put(PathFragment.create(favEntry.getKey()), favEntry.getValue());
+          }
+        }
+      } catch (IOException e) {
+        // If we cannot get the FileArtifactValue, then we will make a FileSystem call to get the
+        // digest, so it is okay to skip and continue here.
+        logger.warning("Could not properly get digest for " + entry.getKey().getExecPath());
+        continue;
+      }
+    }
+    return ImmutableMap.copyOf(filesetMap);
+  }
+
   public ArtifactPathResolver getArtifactPathResolver() {
     return artifactPathResolver;
   }
@@ -162,9 +203,13 @@
 
   @Override
   public FileArtifactValue getMetadata(ActionInput actionInput) throws IOException {
-    // TODO(shahan): is this bypass needed?
     if (!(actionInput instanceof Artifact)) {
-      return null;
+      PathFragment inputPath = actionInput.getExecPath();
+      PathFragment filesetKeyPath =
+          inputPath.startsWith(execRoot.asFragment())
+              ? inputPath.relativeTo(execRoot.asFragment())
+              : inputPath;
+      return filesetMapping.get(filesetKeyPath);
     }
 
     Artifact artifact = (Artifact) actionInput;
@@ -193,7 +238,7 @@
       return metadataFromValue(value);
     } else if (artifact.isTreeArtifact()) {
       TreeArtifactValue setValue = getTreeArtifactValue((SpecialArtifact) artifact);
-      if (setValue != null && setValue != TreeArtifactValue.MISSING_TREE_ARTIFACT) {
+      if (setValue != null && !setValue.equals(TreeArtifactValue.MISSING_TREE_ARTIFACT)) {
         return setValue.getMetadata();
       }
       // We use FileNotFoundExceptions to determine if an Artifact was or wasn't found.
@@ -342,15 +387,20 @@
           // Currently it's hard to report this error without refactoring, since checkOutputs()
           // likes to substitute its own error messages upon catching IOException, and falls
           // through to unrecoverable error behavior on any other exception.
-          throw new IOException("Output file " + missingFiles.iterator().next()
-              + " was registered, but not present on disk");
+          throw new IOException(
+              "Output file "
+                  + missingFiles.iterator().next()
+                  + " was registered, but not present on disk");
         }
 
         Set<TreeFileArtifact> extraFiles = Sets.difference(diskFiles, registeredContents);
         // extraFiles cannot be empty
         throw new IOException(
-            "File " + extraFiles.iterator().next().getParentRelativePath()
-            + ", present in TreeArtifact " + artifact + ", was not registered");
+            "File "
+                + extraFiles.iterator().next().getParentRelativePath()
+                + ", present in TreeArtifact "
+                + artifact
+                + ", was not registered");
       }
 
       value = constructTreeArtifactValue(registeredContents);
@@ -414,7 +464,9 @@
     Object previousContents = store.getTreeArtifactContents(artifact);
     Preconditions.checkState(
         previousContents == null,
-        "Race condition while constructing TreeArtifactValue: %s, %s", artifact, previousContents);
+        "Race condition while constructing TreeArtifactValue: %s, %s",
+        artifact,
+        previousContents);
     return constructTreeArtifactValue(ActionInputHelper.asTreeFileArtifacts(artifact, paths));
   }
 
@@ -539,10 +591,14 @@
   public void discardOutputMetadata() {
     boolean wasExecutionMode = executionMode.getAndSet(true);
     Preconditions.checkState(!wasExecutionMode);
-    Preconditions.checkState(store.injectedFiles().isEmpty(),
-        "Files cannot be injected before action execution: %s", store.injectedFiles());
-    Preconditions.checkState(omittedOutputs.isEmpty(),
-        "Artifacts cannot be marked omitted before action execution: %s", omittedOutputs);
+    Preconditions.checkState(
+        store.injectedFiles().isEmpty(),
+        "Files cannot be injected before action execution: %s",
+        store.injectedFiles());
+    Preconditions.checkState(
+        omittedOutputs.isEmpty(),
+        "Artifacts cannot be marked omitted before action execution: %s",
+        omittedOutputs);
     store.clear();
   }
 
@@ -604,6 +660,11 @@
   }
 
   @VisibleForTesting
+  ImmutableMap<PathFragment, FileArtifactValue> getFilesetMapping() {
+    return filesetMapping;
+  }
+
+  @VisibleForTesting
   static FileArtifactValue fileArtifactValueFromArtifact(
       Artifact artifact,
       @Nullable FileStatusWithDigest statNoFollow,
@@ -671,7 +732,7 @@
     if (path.isFile(Symlinks.NOFOLLOW)) { // i.e. regular files only.
       // We trust the files created by the execution engine to be non symlinks with expected
       // chmod() settings already applied.
-      path.chmod(0555);  // Sets the file read-only and executable.
+      path.chmod(0555); // Sets the file read-only and executable.
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java
index 04df6fd..bda2c1f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java
@@ -373,6 +373,7 @@
     ActionInputMap inputMap = new ActionInputMap(inputDeps.size());
     Map<Artifact, Collection<Artifact>> expandedArtifacts = new HashMap<>();
     Map<Artifact, ImmutableList<FilesetOutputSymlink>> expandedFilesets = new HashMap<>();
+    Map<Artifact, ImmutableList<FilesetOutputSymlink>> topLevelFilesets = new HashMap<>();
 
     int missingCount = 0;
     ActionExecutionException firstActionExecutionException = null;
@@ -395,11 +396,13 @@
             }
           } else {
             ActionInputMapHelper.addToMap(
-                inputMap, expandedArtifacts, expandedFilesets, input, artifactValue, env);
-            if (input.isFileset()) {
-              expandedFilesets.put(
-                  input, ActionInputMapHelper.getFilesets(env, (Artifact.SpecialArtifact) input));
-            }
+                inputMap,
+                expandedArtifacts,
+                expandedFilesets,
+                topLevelFilesets,
+                input,
+                artifactValue,
+                env);
           }
         }
       } catch (ActionExecutionException e) {
@@ -411,6 +414,7 @@
         }
       }
     }
+    expandedFilesets.putAll(topLevelFilesets);
 
     if (missingCount > 0) {
       missingInputException = completor.getMissingFilesException(value, missingCount, env);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunction.java
index 3ada580..9e9e1ac 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunction.java
@@ -16,6 +16,7 @@
 import static com.google.devtools.build.lib.vfs.UnixGlob.DEFAULT_SYSCALLS;
 import static java.nio.charset.StandardCharsets.UTF_8;
 
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
 import com.google.common.base.Verify;
 import com.google.common.collect.Collections2;
@@ -25,6 +26,7 @@
 import com.google.devtools.build.lib.actions.FileArtifactValue;
 import com.google.devtools.build.lib.actions.FileStateType;
 import com.google.devtools.build.lib.actions.FileStateValue;
+import com.google.devtools.build.lib.actions.FileStateValue.RegularFileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.HasDigest;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -320,7 +322,7 @@
         if (fsVal == null) {
           fsVal = fileState;
         }
-        return new FileInfo(type, withDigest(fsVal), realPath, unresolvedLinkTarget);
+        return new FileInfo(type, withDigest(fsVal, path), realPath, unresolvedLinkTarget);
       }
     } else {
       // Stat the file.
@@ -341,31 +343,60 @@
         } else {
           type = fileValue.isDirectory() ? FileType.DIRECTORY : FileType.FILE;
         }
+        Path path = traversal.root.asRootedPath().asPath();
         return new FileInfo(
             type,
-            withDigest(fileValue.realFileStateValue()),
+            withDigest(fileValue.realFileStateValue(), path),
             fileValue.realRootedPath(),
             unresolvedLinkTarget);
       } else {
         // If it doesn't exist, or it's a dangling symlink, we still want to handle that gracefully.
         return new FileInfo(
             fileValue.isSymlink() ? FileType.DANGLING_SYMLINK : FileType.NONEXISTENT,
-            withDigest(fileValue.realFileStateValue()),
+            withDigest(fileValue.realFileStateValue(), null),
             null,
             fileValue.isSymlink() ? fileValue.getUnresolvedLinkTarget() : null);
       }
     }
   }
 
-  private static HasDigest withDigest(HasDigest fsVal) {
+  /**
+   * Transform the HasDigest to the appropriate type based on the current state of the digest. If
+   * fsVal is type RegularFileStateValue or FileArtifactValue and has a valid digest value, then we
+   * want to convert it to a new FileArtifactValue type. Otherwise if they are of the two
+   * forementioned types but do not have a digest, then we will create a FileArtifactValue using its
+   * {@link Path}. Otherwise we will fingerprint the digest and return it as a new {@link
+   * HasDigest.ByteStringDigest} object.
+   *
+   * @param fsVal - the HasDigest value that was in the graph.
+   * @param path - the Path of the digest.
+   * @return transformed HasDigest value based on the digest field and object type.
+   */
+  @VisibleForTesting
+  static HasDigest withDigest(HasDigest fsVal, Path path) throws IOException {
     if (fsVal instanceof FileStateValue) {
-      return new HasDigest.ByteStringDigest(
-          ((FileStateValue) fsVal).getValueFingerprint().toByteArray());
+      FileStateValue fsv = (FileStateValue) fsVal;
+      if (fsv instanceof RegularFileStateValue) {
+        RegularFileStateValue rfsv = (RegularFileStateValue) fsv;
+        return rfsv.getDigest() != null
+            // If we have the digest, then simply convert it with the digest value.
+            ? FileArtifactValue.createForVirtualActionInput(rfsv.getDigest(), rfsv.getSize())
+            // Otherwise, create a file FileArtifactValue (RegularFileArtifactValue) based on the
+            // path and size.
+            : FileArtifactValue.createForNormalFileUsingPath(path, rfsv.getSize());
+      }
+      return new HasDigest.ByteStringDigest(fsv.getValueFingerprint().toByteArray());
     } else if (fsVal instanceof FileArtifactValue) {
-      FileArtifactValue artifactValue = (FileArtifactValue) fsVal;
-      // Transforming the FileArtifactValue to fingerprint the digests and retain other values
-      return FileArtifactValue.createForVirtualActionInput(
-          artifactValue.getValueFingerprint().toByteArray(), artifactValue.getSize());
+      FileArtifactValue fav = ((FileArtifactValue) fsVal);
+      if (fav.getDigest() != null) {
+        return fav;
+      }
+
+      // In the case there is a directory, the HasDigest value should not be converted. Otherwise,
+      // if the HasDigest value is a file, convert it using the Path and size values.
+      return fav.getType().isFile()
+          ? FileArtifactValue.createForNormalFileUsingPath(path, fav.getSize())
+          : new HasDigest.ByteStringDigest(fav.getValueFingerprint().toByteArray());
     }
     return fsVal;
   }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandlerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandlerTest.java
index 22cdf98..1cf4552 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandlerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandlerTest.java
@@ -29,11 +29,16 @@
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.FileArtifactValue;
 import com.google.devtools.build.lib.actions.FileArtifactValue.RemoteFileArtifactValue;
+import com.google.devtools.build.lib.actions.FilesetOutputSymlink;
+import com.google.devtools.build.lib.actions.HasDigest;
+import com.google.devtools.build.lib.actions.HasDigest.ByteStringDigest;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.testutil.Scratch;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import java.io.FileNotFoundException;
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Map;
 import org.junit.Before;
 import org.junit.Test;
@@ -63,13 +68,16 @@
     ActionInputMap map = new ActionInputMap(1);
     map.putWithNoDepOwner(input, metadata);
     assertThat(map.getMetadata(input)).isEqualTo(metadata);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ false,
-        /* outputs= */ ImmutableList.of(),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThat(handler.getMetadata(input)).isNull();
   }
 
@@ -82,13 +90,16 @@
             new byte[] {1, 2, 3}, /*proxy=*/ null, 10L, /*isShareable=*/ true);
     ActionInputMap map = new ActionInputMap(1);
     map.putWithNoDepOwner(artifact, metadata);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ false,
-        /* outputs= */ ImmutableList.of(),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThat(handler.getMetadata(artifact)).isEqualTo(metadata);
   }
 
@@ -97,13 +108,16 @@
     PathFragment path = PathFragment.create("src/a");
     Artifact artifact = ActionsTestUtil.createArtifactWithRootRelativePath(sourceRoot, path);
     ActionInputMap map = new ActionInputMap(1);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ false,
-        /* outputs= */ ImmutableList.of(),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     IllegalStateException expected =
         assertThrows(IllegalStateException.class, () -> handler.getMetadata(artifact));
     assertThat(expected).hasMessageThat().contains("null for ");
@@ -114,13 +128,16 @@
     PathFragment path = PathFragment.create("src/a");
     Artifact artifact = ActionsTestUtil.createArtifactWithRootRelativePath(sourceRoot, path);
     ActionInputMap map = new ActionInputMap(1);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ true,
-        /* outputs= */ ImmutableList.of(),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ true,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThat(handler.getMetadata(artifact)).isNull();
   }
 
@@ -129,13 +146,16 @@
     PathFragment path = PathFragment.create("foo/bar");
     Artifact artifact = ActionsTestUtil.createArtifactWithRootRelativePath(outputRoot, path);
     ActionInputMap map = new ActionInputMap(1);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ true,
-        /* outputs= */ ImmutableList.of(),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ true,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThat(handler.getMetadata(artifact)).isNull();
   }
 
@@ -145,13 +165,16 @@
     Artifact artifact = ActionsTestUtil.createArtifact(outputRoot, "foo/bar");
     assertThat(artifact.getPath().exists()).isTrue();
     ActionInputMap map = new ActionInputMap(1);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ false,
-        /* outputs= */ ImmutableList.of(artifact),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(artifact),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThat(handler.getMetadata(artifact)).isNotNull();
   }
 
@@ -160,13 +183,16 @@
     Artifact artifact = ActionsTestUtil.createArtifact(outputRoot, "foo/bar");
     assertThat(artifact.getPath().exists()).isFalse();
     ActionInputMap map = new ActionInputMap(1);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ false,
-        /* outputs= */ ImmutableList.of(artifact),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(artifact),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThrows(FileNotFoundException.class, () -> handler.getMetadata(artifact));
   }
 
@@ -175,13 +201,16 @@
     PathFragment path = PathFragment.create("foo/bar");
     Artifact artifact = ActionsTestUtil.createArtifactWithRootRelativePath(outputRoot, path);
     ActionInputMap map = new ActionInputMap(1);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ false,
-        /* outputs= */ ImmutableList.of(),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThrows(IllegalStateException.class, () -> handler.getMetadata(artifact));
   }
 
@@ -193,13 +222,16 @@
             outputRoot, path, ActionsTestUtil.NULL_ARTIFACT_OWNER, SpecialArtifactType.TREE);
     Artifact artifact = new TreeFileArtifact(treeArtifact, PathFragment.create("baz"));
     ActionInputMap map = new ActionInputMap(1);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ true,
-        /* outputs= */ ImmutableList.of(),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ true,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThat(handler.getMetadata(artifact)).isNull();
   }
 
@@ -213,13 +245,16 @@
     Artifact artifact = new TreeFileArtifact(treeArtifact, PathFragment.create("baz"));
     assertThat(artifact.getPath().exists()).isTrue();
     ActionInputMap map = new ActionInputMap(1);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ false,
-        /* outputs= */ ImmutableList.of(treeArtifact),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(treeArtifact),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThat(handler.getMetadata(artifact)).isNotNull();
   }
 
@@ -231,17 +266,50 @@
             outputRoot, path, ActionsTestUtil.NULL_ARTIFACT_OWNER, SpecialArtifactType.TREE);
     Artifact artifact = new TreeFileArtifact(treeArtifact, PathFragment.create("baz"));
     ActionInputMap map = new ActionInputMap(1);
-    ActionMetadataHandler handler = new ActionMetadataHandler(
-        map,
-        /* missingArtifactsAllowed= */ false,
-        /* outputs= */ ImmutableList.of(),
-        /* tsgm= */ null,
-        ArtifactPathResolver.IDENTITY,
-        new MinimalOutputStore());
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            map,
+            ImmutableMap.of(),
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.IDENTITY,
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     assertThrows(IllegalStateException.class, () -> handler.getMetadata(artifact));
   }
 
   @Test
+  public void withFilesetInput() throws Exception {
+    // This value should be mapped
+    FileArtifactValue directoryFav = FileArtifactValue.createForDirectoryWithMtime(10L);
+    // This value should not be mapped
+    FileArtifactValue regularFav =
+        FileArtifactValue.createForVirtualActionInput(new byte[] {1, 2, 3, 4}, 10L);
+    // This value should not be mapped
+    HasDigest.ByteStringDigest byteStringDigest = new ByteStringDigest(new byte[] {2, 3, 4});
+
+    ImmutableMap<Artifact, ImmutableList<FilesetOutputSymlink>> filesetMap =
+        createFilesetOutputSymlinkMap(directoryFav, regularFav, byteStringDigest);
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            new ActionInputMap(0),
+            filesetMap,
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.forExecRoot(outputRoot.getRoot().asPath()),
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
+
+    ImmutableMap<PathFragment, FileArtifactValue> filesetMapping = handler.getFilesetMapping();
+    assertThat(filesetMapping).hasSize(1);
+    PathFragment filesetPathFragment = filesetMapping.keySet().iterator().next();
+    assertThat(filesetPathFragment.getPathString()).isEqualTo("target/bytestring2");
+    assertThat(filesetMapping.get(filesetPathFragment)).isEqualTo(regularFav);
+  }
+
+  @Test
   public void resettingOutputs() throws Exception {
     scratch.file("/output/bin/foo/bar", "not empty");
     PathFragment path = PathFragment.create("foo/bar");
@@ -250,11 +318,13 @@
     ActionMetadataHandler handler =
         new ActionMetadataHandler(
             map,
+            ImmutableMap.of(),
             /* missingArtifactsAllowed= */ true,
             /* outputs= */ ImmutableList.of(artifact),
             /* tsgm= */ null,
             ArtifactPathResolver.IDENTITY,
-            new MinimalOutputStore());
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
     handler.discardOutputMetadata();
 
     // The handler doesn't have any info. It'll stat the file and discover that it's 10 bytes long.
@@ -276,11 +346,13 @@
     ActionMetadataHandler handler =
         new ActionMetadataHandler(
             /* inputArtifactData= */ new ActionInputMap(0),
+            ImmutableMap.of(),
             /* missingArtifactsAllowed= */ false,
             /* outputs= */ ImmutableList.of(artifact),
             /* tsgm= */ null,
             ArtifactPathResolver.IDENTITY,
-            new OutputStore());
+            new OutputStore(),
+            outputRoot.getRoot().asPath());
     handler.discardOutputMetadata();
 
     byte[] digest = new byte[] {1, 2, 3};
@@ -304,11 +376,13 @@
     ActionMetadataHandler handler =
         new ActionMetadataHandler(
             /* inputArtifactData= */ new ActionInputMap(0),
+            ImmutableMap.of(),
             /* missingArtifactsAllowed= */ false,
             /* outputs= */ ImmutableList.of(treeArtifact),
             /* tsgm= */ null,
             ArtifactPathResolver.IDENTITY,
-            store);
+            store,
+            outputRoot.getRoot().asPath());
     handler.discardOutputMetadata();
 
     RemoteFileArtifactValue fooValue = new RemoteFileArtifactValue(new byte[] {1, 2, 3}, 5, 1);
@@ -331,4 +405,54 @@
         .containsExactly(PathFragment.create("foo"), PathFragment.create("bar"));
     assertThat(treeValue.getChildValues().values()).containsExactly(fooValue, barValue);
   }
+
+  @Test
+  public void getMetadataFromFilesetMapping() throws Exception {
+    FileArtifactValue directoryFav = FileArtifactValue.createForDirectoryWithMtime(10L);
+    FileArtifactValue regularFav =
+        FileArtifactValue.createForVirtualActionInput(new byte[] {1, 2, 3, 4}, 10L);
+    HasDigest.ByteStringDigest byteStringDigest = new ByteStringDigest(new byte[] {2, 3, 4});
+
+    ImmutableMap<Artifact, ImmutableList<FilesetOutputSymlink>> filesetMap =
+        createFilesetOutputSymlinkMap(directoryFav, regularFav, byteStringDigest);
+
+    ActionMetadataHandler handler =
+        new ActionMetadataHandler(
+            new ActionInputMap(0),
+            filesetMap,
+            /* missingArtifactsAllowed= */ false,
+            /* outputs= */ ImmutableList.of(),
+            /* tsgm= */ null,
+            ArtifactPathResolver.forExecRoot(outputRoot.getRoot().asPath()),
+            new MinimalOutputStore(),
+            outputRoot.getRoot().asPath());
+
+    assertThat(handler.getMetadata(ActionInputHelper.fromPath("/output/bin/target/bytestring1")))
+        .isNull();
+    assertThat(handler.getMetadata(ActionInputHelper.fromPath("/output/bin/target/bytestring2")))
+        .isEqualTo(regularFav);
+    assertThat(handler.getMetadata(ActionInputHelper.fromPath("/output/bin/target/bytestring3")))
+        .isNull();
+    assertThat(handler.getMetadata(ActionInputHelper.fromPath("/does/not/exist"))).isNull();
+  }
+
+  private ImmutableMap<Artifact, ImmutableList<FilesetOutputSymlink>> createFilesetOutputSymlinkMap(
+      HasDigest... digests) {
+    int index = 1;
+    PathFragment execRoot = outputRoot.getExecPath();
+    List<FilesetOutputSymlink> symlinks = new ArrayList<>();
+    for (HasDigest digest : digests) {
+      symlinks.add(
+          FilesetOutputSymlink.create(
+              PathFragment.create("test/bytestring" + index),
+              PathFragment.create("target/bytestring" + index++),
+              digest,
+              true,
+              execRoot));
+    }
+
+    PathFragment path = PathFragment.create("foo/bar");
+    Artifact artifact = ActionsTestUtil.createArtifactWithRootRelativePath(outputRoot, path);
+    return ImmutableMap.of(artifact, ImmutableList.copyOf(symlinks));
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
index 09e8005..6fef6c8 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
@@ -36,7 +36,9 @@
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.FileArtifactValue;
+import com.google.devtools.build.lib.actions.FileContentsProxy;
 import com.google.devtools.build.lib.actions.FileStateValue;
+import com.google.devtools.build.lib.actions.FileStateValue.RegularFileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.FilesetTraversalParams.DirectTraversalRoot;
 import com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode;
@@ -59,6 +61,7 @@
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.testutil.TimestampGranularityUtils;
 import com.google.devtools.build.lib.util.io.OutErr;
+import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
@@ -1090,6 +1093,68 @@
     assertThat(strictResolvedFile.getMetadata()).isInstanceOf(FileArtifactValue.class);
   }
 
+  @Test
+  public void testWithDigestFileArtifactValue() throws Exception {
+    // file artifacts will return the same bytes as it was initialized with
+    byte[] expectedBytes = new byte[] {1, 2, 3};
+    FileArtifactValue fav = FileArtifactValue.createForVirtualActionInput(expectedBytes, 10L);
+    HasDigest result = RecursiveFilesystemTraversalFunction.withDigest(fav, null);
+    assertThat(result).isInstanceOf(FileArtifactValue.class);
+    assertThat(result.getDigest()).isEqualTo(expectedBytes);
+
+    // Directories do not have digest but the result will have a fingerprinted digest
+    FileArtifactValue directoryFav = FileArtifactValue.createForDirectoryWithMtime(10L);
+    HasDigest directoryResult = RecursiveFilesystemTraversalFunction.withDigest(directoryFav, null);
+    assertThat(directoryResult).isInstanceOf(HasDigest.ByteStringDigest.class);
+    assertThat(directoryResult.getDigest()).isNotNull();
+  }
+
+  @Test
+  public void testWithDigestFileStateValue() throws Exception {
+    // RegularFileStateValue with actual digest will be transformed with the same digest
+    byte[] expectedBytes = new byte[] {1, 2, 3};
+    RegularFileStateValue withDigest =
+        new RegularFileStateValue(10L, expectedBytes, /* contentsProxy */ null);
+    HasDigest result = RecursiveFilesystemTraversalFunction.withDigest(withDigest, null);
+    assertThat(result).isInstanceOf(FileArtifactValue.class);
+    assertThat(result.getDigest()).isEqualTo(expectedBytes);
+
+    // FileStateValue will be transformed with fingerprinted digest
+    RootedPath rootedPath = rootedPath("bar", "foo");
+    FileStateValue fsv = FileStateValue.create(rootedPath, null);
+    HasDigest fsvResult = RecursiveFilesystemTraversalFunction.withDigest(fsv, null);
+    assertThat(fsvResult).isInstanceOf(HasDigest.ByteStringDigest.class);
+    assertThat(fsvResult.getDigest()).isNotNull();
+  }
+
+  @Test
+  public void testRegularFileStateValueWithoutDigest() throws Exception {
+    Artifact artifact = derivedArtifact("foo/fooy.txt");
+    RootedPath rootedPath = rootedPath(artifact);
+    createFile(rootedPath, "fooy-content");
+    FileStatus status = rootedPath.asPath().stat();
+
+    RegularFileStateValue withoutDigest =
+        new RegularFileStateValue(
+            status.getSize(), /* digest */
+            null, /* contentsProxy */
+            FileContentsProxy.create(status));
+    HasDigest withoutDigestResult =
+        RecursiveFilesystemTraversalFunction.withDigest(withoutDigest, rootedPath.asPath());
+    // withDigest will construct a FileArtifactValue using the Path
+    assertThat(withoutDigestResult).isInstanceOf(FileArtifactValue.class);
+    assertThat(withoutDigestResult.getDigest()).isNotNull();
+  }
+
+  @Test
+  public void testWithDigestByteStringDigest() throws Exception {
+    byte[] expectedBytes = new byte[] {1, 2, 3};
+    HasDigest.ByteStringDigest byteStringDigest = new HasDigest.ByteStringDigest(expectedBytes);
+    HasDigest result = RecursiveFilesystemTraversalFunction.withDigest(byteStringDigest, null);
+    assertThat(result).isInstanceOf(HasDigest.ByteStringDigest.class);
+    assertThat(result.getDigest()).isEqualTo(expectedBytes);
+  }
+
   private static class NonHermeticArtifactSkyKey extends AbstractSkyKey<SkyKey> {
     private NonHermeticArtifactSkyKey(SkyKey arg) {
       super(arg);