Make `RootedPath` implement `SkyKey`, and make it the key type for `FileStateValue`.

By doing this, we no longer need the `FileState.Key` wrapper around `RootedPath`. The prior https://github.com/bazelbuild/bazel/commit/ab31f74f509c2af593b783e86d76c8b6188c9aaa already reduced the shallow heap size of that wrapper from 24 bytes to 16 bytes, but "0 bytes" is better. Kudos to janakr@ for the suggestion.

To achieve this refactor and still maintain readability, I introduced a `FileStateKey` interface so that it will be obvious to a caller of `FileStateValue#key` that the returned type is a `SkyKey` whose `#argument` returns `RootedPath`. I then made one slight improvement to one part of the codebase (no need to make an intermediate collection to transform some `RootedPath` instances to some `SkyKey` instances), but there may be other improvements along these lines we can make in the future.

PiperOrigin-RevId: 428094803
diff --git a/src/main/java/com/google/devtools/build/lib/actions/FileStateValue.java b/src/main/java/com/google/devtools/build/lib/actions/FileStateValue.java
index e4b57d6..2d0ca46 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FileStateValue.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FileStateValue.java
@@ -32,8 +32,6 @@
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.lib.vfs.Symlinks;
 import com.google.devtools.build.lib.vfs.SyscallCache;
-import com.google.devtools.build.skyframe.SkyFunctionName;
-import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.io.IOException;
 import java.util.Arrays;
@@ -60,8 +58,6 @@
  * <p>All subclasses must implement {@link #equals} and {@link #hashCode} properly.
  */
 public abstract class FileStateValue implements HasDigest, SkyValue {
-  public static final SkyFunctionName FILE_STATE = SkyFunctionName.createNonHermetic("FILE_STATE");
-
   @SerializationConstant
   public static final DirectoryFileStateValue DIRECTORY_FILE_STATE_NODE =
       new DirectoryFileStateValue();
@@ -135,15 +131,11 @@
   }
 
   @ThreadSafe
-  public static Key key(RootedPath rootedPath) {
-    return new Key(rootedPath);
-  }
-
-  /** Key type for FileStateValue. */
-  public static final class Key implements SkyKey {
-    private final RootedPath rootedPath;
-
-    // We used to weakly intern all Key instances but no longer do so after concluding the data
+  public static RootedPath key(RootedPath rootedPath) {
+    // RootedPath is already the SkyKey we want; see FileStateKey. This method and that interface
+    // are provided as readability aids.
+    //
+    // We used to weakly intern all key instances but no longer do so after concluding the data
     // structure overhead of the intern was a net negative wrt retained heap. The current approach
     // of interning nothing is instead a net positive (saved ~0.1% when implemented in Feb 2022).
     //
@@ -151,62 +143,24 @@
     //   * FileFunction computing a specific FileValue (FV) node, declaring a Skyframe dep on a
     //     specific FileStateValue (FSV) node. There are two things to consider:
     //     * A specific FSV node will have exactly one rdep so there's no business-logic reason
-    //       interning of Key would be productive. One exception to this reasoning is symlinks: if
-    //       paths `a` and `b` are both symlinks to `c` and Blaze needs to consider `a` and `b`,
-    //       then it'll have nodes FV(a); FV(b); FSV(a); FSV(b); FSV(c) and forward edge sets
-    //       FV(a)->{FSV(a); FSV(c)}; FV(b)->{FSV(b); FSV(c)}. So our current non-interning
-    //       approach will mean we have different Key instances for right endpoints of edges
-    //       FV(a)->FSV(c); FV(b)->FSV(c). This is an acceptable inefficiency because this situation
-    //       is not common and not worth optimizing for.
+    //       interning of the RootedPath here would be productive. One exception to this reasoning
+    //       is symlinks: if paths `a` and `b` are both symlinks to `c` and Blaze needs to consider
+    //       `a` and `b`, then it'll have nodes FV(a); FV(b); FSV(a); FSV(b); FSV(c) and forward
+    //       edge sets FV(a)->{FSV(a); FSV(c)}; FV(b)->{FSV(b); FSV(c)}. So our current
+    //       non-interning approach will mean we have different RootedPath instances for right
+    //       endpoints of edges FV(a)->FSV(c); FV(b)->FSV(c). This is an acceptable inefficiency
+    //       because this situation is not common and not worth optimizing for.
     //     * The Skyframe engine implementation effectively deduplicates the set of Skyframe deps of
     //       a node declared by a skyFunction.compute(k, env), across all Skyframe restarts. So
-    //       there's no concern about a specific FV node causing many equivalent Key instances to be
-    //       retained, due to Skyframe restarts of FileFunction.
+    //       there's no concern about a specific FV node causing many equivalent RootedPath
+    //       instances to be retained, due to Skyframe restarts of FileFunction.
     //   * SkyQuery's RBuildFilesVisitor, creating a root node for a graph traversal for query
     //     evaluation. The set of RootedPaths used for these roots is both low in number and also
-    //     deduped, so interning Key here isn't productive. Also, these objects are not retained for
-    //     long anyway so it's fine to have some garbage churn.
+    //     deduped, so interning RootedPath here isn't productive. Also, these objects are not
+    //     retained for long anyway so it's fine to have some garbage churn.
     //   * SkyframeExecutor, creating a root node for an invalidation traversal. Same reasoning as
     //     above.
-    //
-    // Then, since we're not interning, using AbstractSkyKey is unproductive since the assumption
-    // about the #hashCode field is wrong. By not extending AbstractSkyKey, we save 8 bytes of
-    // shallow heap per Key instance.
-    private Key(RootedPath rootedPath) {
-      this.rootedPath = rootedPath;
-    }
-
-    @Override
-    public SkyFunctionName functionName() {
-      return FILE_STATE;
-    }
-
-    @Override
-    public RootedPath argument() {
-      return rootedPath;
-    }
-
-    @Override
-    public int hashCode() {
-      return rootedPath.hashCode();
-    }
-
-    @Override
-    public boolean equals(Object obj) {
-      if (this == obj) {
-        return true;
-      }
-      if (!(obj instanceof Key)) {
-        return false;
-      }
-      Key other = (Key) obj;
-      return rootedPath.equals(other.rootedPath);
-    }
-
-    @Override
-    public String toString() {
-      return FILE_STATE + ":" + rootedPath;
-    }
+    return rootedPath;
   }
 
   public abstract FileStateType getType();
diff --git a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java
index c42f01a..b6a4239 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java
@@ -42,6 +42,7 @@
 import com.google.devtools.build.lib.skyframe.PackageValue;
 import com.google.devtools.build.lib.skyframe.SkyFunctions;
 import com.google.devtools.build.lib.skyframe.WorkspaceNameValue;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -53,7 +54,6 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
-import java.util.stream.Collectors;
 import javax.annotation.Nullable;
 
 /**
@@ -302,30 +302,24 @@
   }
 
   private static void includeAncestorKeysInResult(
-      WalkableGraph graph, Set<SkyKey> result, Set<RootedPath> pathsToCheckForNewlyAddedDirectories)
+      WalkableGraph graph, Set<SkyKey> result, Set<? extends FileStateKey> fileStateKeysToFetch)
       throws InterruptedException {
     // Do a single batch fetch of all FileState's corresponding to directories with
     // failed package lookups.
-    Set<SkyKey> fileStateKeysToFetch =
-        pathsToCheckForNewlyAddedDirectories.stream()
-            .map(FileStateValue::key)
-            .collect(Collectors.toSet());
     Map<SkyKey, SkyValue> fileStateValues = graph.getSuccessfulValues(fileStateKeysToFetch);
-
     for (SkyKey fileStateKey : fileStateKeysToFetch) {
       if (fileStateValues.containsKey(fileStateKey)) {
         FileStateValue fsv = (FileStateValue) fileStateValues.get(fileStateKey);
         if (!fsv.getType().exists() && !fsv.getType().isDirectory()) {
-          processFileStateKeyForMissingDirectory(result, (FileStateValue.Key) fileStateKey);
+          processFileStateKeyForMissingDirectory(result, (FileStateKey) fileStateKey);
         }
       } else {
-        processFileStateKeyForMissingDirectory(result, (FileStateValue.Key) fileStateKey);
+        processFileStateKeyForMissingDirectory(result, (FileStateKey) fileStateKey);
       }
     }
   }
 
-  private static void processFileStateKeyForMissingDirectory(
-      Set<SkyKey> result, FileStateValue.Key key) {
+  private static void processFileStateKeyForMissingDirectory(Set<SkyKey> result, FileStateKey key) {
     RootedPath rootedPath = key.argument();
     result.add(key);
     result.add(FileValue.key(rootedPath));
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/DirtinessCheckerUtils.java b/src/main/java/com/google/devtools/build/lib/skyframe/DirtinessCheckerUtils.java
index daaefcb..e7be3b2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/DirtinessCheckerUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/DirtinessCheckerUtils.java
@@ -13,8 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import static com.google.devtools.build.lib.actions.FileStateValue.FILE_STATE;
 import static com.google.devtools.build.lib.skyframe.SkyFunctions.DIRECTORY_LISTING_STATE;
+import static com.google.devtools.build.lib.vfs.FileStateKey.FILE_STATE;
 
 import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSystemValueCheckerInferringAncestors.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSystemValueCheckerInferringAncestors.java
index 5ae36ad..543bba2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileSystemValueCheckerInferringAncestors.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSystemValueCheckerInferringAncestors.java
@@ -29,6 +29,7 @@
 import com.google.devtools.build.lib.util.DetailedExitCode;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.Dirent;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.ImmutableDiff;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -125,12 +126,12 @@
       @Nullable TimestampGranularityMonitor tsgm,
       Map<SkyKey, SkyValue> graphValues,
       Map<SkyKey, SkyValue> graphDoneValues,
-      Iterable<SkyKey> modifiedKeys,
+      Iterable<FileStateKey> modifiedKeys,
       int nThreads)
       throws InterruptedException, AbruptExitException {
     Map<RootedPath, NodeVisitState> nodeStates = new HashMap<>();
-    for (SkyKey key : modifiedKeys) {
-      RootedPath top = ((FileStateValue.Key) key).argument();
+    for (FileStateKey fileStateKey : modifiedKeys) {
+      RootedPath top = fileStateKey.argument();
       // Start with false since the reported diff does not mean we are adding a child.
       boolean lastCreated = false;
       for (RootedPath path = top; path != null; path = path.getParentDirectory()) {
@@ -241,7 +242,7 @@
       @Nullable Set<String> maybeDeletedChildren,
       NodeVisitState parentState)
       throws StatFailedException {
-    FileStateValue.Key key = FileStateValue.key(path);
+    FileStateKey key = FileStateValue.key(path);
     @Nullable FileStateValue fsv = (FileStateValue) graphValues.get(key);
     if (fsv == null) {
       visitUnknownEntry(key, isInferredDirectory, parentState);
@@ -281,7 +282,7 @@
   }
 
   private void visitUnknownEntry(
-      FileStateValue.Key key, boolean isInferredDirectory, NodeVisitState parentState)
+      FileStateKey key, boolean isInferredDirectory, NodeVisitState parentState)
       throws StatFailedException {
     RootedPath path = key.argument();
     // Run stats on unknown files in order to preserve the parent listing if present unless we
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index 570808d..7596352 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -86,6 +86,7 @@
 import com.google.devtools.build.lib.util.ResourceUsage;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.BatchStat;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.ModifiedFileSet;
 import com.google.devtools.build.lib.vfs.Root;
@@ -299,7 +300,7 @@
    */
   private static final ImmutableSet<SkyFunctionName> PACKAGE_LOCATOR_DEPENDENT_VALUES =
       ImmutableSet.of(
-          FileStateValue.FILE_STATE,
+          FileStateKey.FILE_STATE,
           FileValue.FILE,
           SkyFunctions.DIRECTORY_LISTING_STATE,
           SkyFunctions.PREPARE_DEPS_OF_PATTERN,
@@ -696,7 +697,7 @@
     // We are searching only for changed files, DirectoryListingValues don't depend on
     // child values, that's why they are invalidated separately
     return Iterables.size(
-        Iterables.filter(modifiedValues, SkyFunctionName.functionIs(FileStateValue.FILE_STATE)));
+        Iterables.filter(modifiedValues, SkyFunctionName.functionIs(FileStateKey.FILE_STATE)));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index b9a16a9..bf91e7e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -177,6 +177,7 @@
 import com.google.devtools.build.lib.util.TestType;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.DigestHashFunction;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.ModifiedFileSet;
 import com.google.devtools.build.lib.vfs.OutputService;
@@ -480,7 +481,7 @@
     map.put(SkyFunctions.PRECOMPUTED, new PrecomputedFunction());
     map.put(SkyFunctions.CLIENT_ENVIRONMENT_VARIABLE, new ClientEnvironmentFunction(clientEnv));
     map.put(SkyFunctions.ACTION_ENVIRONMENT_VARIABLE, new ActionEnvironmentFunction());
-    map.put(FileStateValue.FILE_STATE, newFileStateFunction());
+    map.put(FileStateKey.FILE_STATE, newFileStateFunction());
     map.put(SkyFunctions.DIRECTORY_LISTING_STATE, newDirectoryListingStateFunction());
     map.put(FileSymlinkCycleUniquenessFunction.NAME, new FileSymlinkCycleUniquenessFunction());
     map.put(
@@ -1283,7 +1284,7 @@
     }
 
     // TODO(bazel-team): change ModifiedFileSet to work with RootedPaths instead of PathFragments.
-    Collection<SkyKey> dirtyFileStateSkyKeys =
+    Collection<FileStateKey> dirtyFileStateSkyKeys =
         Collections2.transform(
             modifiedFileSet.modifiedSourceFiles(),
             pathFragment -> {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeIncrementalBuildMonitor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeIncrementalBuildMonitor.java
index d55fc6d7..50e7911 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeIncrementalBuildMonitor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeIncrementalBuildMonitor.java
@@ -16,8 +16,8 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.ChangedFilesMessage;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.concurrent.ThreadSafety;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -40,7 +40,7 @@
 
   public void accrue(Iterable<SkyKey> invalidatedValues) {
     for (SkyKey skyKey : invalidatedValues) {
-      if (skyKey.functionName().equals(FileStateValue.FILE_STATE)) {
+      if (skyKey.functionName().equals(FileStateKey.FILE_STATE)) {
         RootedPath file = (RootedPath) skyKey.argument();
         maybeAddFile(file.getRootRelativePath());
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java b/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
index 62b9fe2..89ea161 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
@@ -24,7 +24,6 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.eventbus.EventBus;
 import com.google.common.hash.HashFunction;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.ThreadStateReceiver;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
@@ -83,6 +82,7 @@
 import com.google.devtools.build.lib.skyframe.WorkspaceFileFunction;
 import com.google.devtools.build.lib.skyframe.WorkspaceNameFunction;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
@@ -458,7 +458,7 @@
     builder
         .put(SkyFunctions.PRECOMPUTED, new PrecomputedFunction())
         .put(
-            FileStateValue.FILE_STATE,
+            FileStateKey.FILE_STATE,
             new FileStateFunction(() -> tsgm, syscallCache, externalFilesHelper))
         .put(FileSymlinkCycleUniquenessFunction.NAME, new FileSymlinkCycleUniquenessFunction())
         .put(
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/BUILD b/src/main/java/com/google/devtools/build/lib/vfs/BUILD
index 7f78c60..ea6df17 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/vfs/BUILD
@@ -66,6 +66,7 @@
         "//src/main/java/com/google/devtools/build/lib/profiler",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
         "//src/main/java/com/google/devtools/build/lib/util:filetype",
+        "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
         "//src/main/java/com/google/devtools/common/options",
         "//third_party:caffeine",
         "//third_party:error_prone_annotations",
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/FileStateKey.java b/src/main/java/com/google/devtools/build/lib/vfs/FileStateKey.java
new file mode 100644
index 0000000..a71f82b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/vfs/FileStateKey.java
@@ -0,0 +1,35 @@
+// Copyright 2022 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.vfs;
+
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+
+/**
+ * The SkyKey for FileStateValue.
+ *
+ * <p>This interface exists to allow {@link RootedPath} to implement {@link SkyKey} in such a way
+ * that makes it obvious that {@link RootedPath} is the {@link SkyKey} for FileStateValue.
+ */
+public interface FileStateKey extends SkyKey {
+  SkyFunctionName FILE_STATE = SkyFunctionName.createNonHermetic("FILE_STATE");
+
+  @Override
+  default SkyFunctionName functionName() {
+    return FILE_STATE;
+  }
+
+  @Override
+  RootedPath argument();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/RootedPath.java b/src/main/java/com/google/devtools/build/lib/vfs/RootedPath.java
index f346402..ecb9c76 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/RootedPath.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/RootedPath.java
@@ -30,7 +30,7 @@
  * clients via #asPath or #getRoot.
  */
 @AutoCodec
-public class RootedPath implements Comparable<RootedPath> {
+public class RootedPath implements Comparable<RootedPath>, FileStateKey {
   private final Root root;
   private final PathFragment rootRelativePath;
 
@@ -140,4 +140,9 @@
 
   private static final Comparator<RootedPath> COMPARATOR =
       Comparator.comparing(RootedPath::getRoot).thenComparing(RootedPath::getRootRelativePath);
+
+  @Override
+  public RootedPath argument() {
+    return this;
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
index 2b37bee..a188d19 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
@@ -50,7 +50,7 @@
   }
 
   @Override
-  public Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys)
+  public Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<? extends SkyKey> keys)
       throws InterruptedException {
     Map<SkyKey, ? extends NodeEntry> batchGet = getBatch(null, Reason.WALKABLE_GRAPH_VALUE, keys);
     Map<SkyKey, SkyValue> result = Maps.newHashMapWithExpectedSize(batchGet.size());
diff --git a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
index bbec641..5735db1 100644
--- a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
@@ -50,7 +50,8 @@
    * computed. Or in other words, it filters out non-existent nodes, pending nodes and nodes that
    * produced an exception.
    */
-  Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys) throws InterruptedException;
+  Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<? extends SkyKey> keys)
+      throws InterruptedException;
 
   /**
    * Returns a map giving exceptions associated to the given keys for done keys. Keys not present in
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodRepoRuleFunctionTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodRepoRuleFunctionTest.java
index e00093a..033e7a0 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodRepoRuleFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodRepoRuleFunctionTest.java
@@ -25,7 +25,6 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.hash.HashFunction;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.ThreadStateReceiver;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
@@ -61,6 +60,7 @@
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.SyscallCache;
@@ -130,7 +130,7 @@
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
                 .put(FileValue.FILE, new FileFunction(packageLocator))
                 .put(
-                    FileStateValue.FILE_STATE,
+                    FileStateKey.FILE_STATE,
                     new FileStateFunction(
                         Suppliers.ofInstance(
                             new TimestampGranularityMonitor(BlazeClock.instance())),
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodRepoRuleHelperTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodRepoRuleHelperTest.java
index c42af74..2c696c7 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodRepoRuleHelperTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodRepoRuleHelperTest.java
@@ -23,7 +23,6 @@
 import com.google.common.base.Suppliers;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ServerDirectories;
@@ -41,6 +40,7 @@
 import com.google.devtools.build.lib.skyframe.SkyFunctions;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.SyscallCache;
@@ -107,7 +107,7 @@
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
                 .put(FileValue.FILE, new FileFunction(packageLocator))
                 .put(
-                    FileStateValue.FILE_STATE,
+                    FileStateKey.FILE_STATE,
                     new FileStateFunction(
                         Suppliers.ofInstance(
                             new TimestampGranularityMonitor(BlazeClock.instance())),
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/DiscoveryTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/DiscoveryTest.java
index 90977d2..80732e0 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/DiscoveryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/DiscoveryTest.java
@@ -24,7 +24,6 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
@@ -53,6 +52,7 @@
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.SyscallCache;
@@ -155,7 +155,7 @@
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
                 .put(FileValue.FILE, new FileFunction(packageLocator))
                 .put(
-                    FileStateValue.FILE_STATE,
+                    FileStateKey.FILE_STATE,
                     new FileStateFunction(
                         Suppliers.ofInstance(
                             new TimestampGranularityMonitor(BlazeClock.instance())),
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleExtensionResolutionTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleExtensionResolutionTest.java
index 5a0532d..37bbb9a 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleExtensionResolutionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleExtensionResolutionTest.java
@@ -23,7 +23,6 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.hash.HashFunction;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.ThreadStateReceiver;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
@@ -71,6 +70,7 @@
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
@@ -158,7 +158,7 @@
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
                 .put(FileValue.FILE, new FileFunction(packageLocator))
                 .put(
-                    FileStateValue.FILE_STATE,
+                    FileStateKey.FILE_STATE,
                     new FileStateFunction(
                         Suppliers.ofInstance(
                             new TimestampGranularityMonitor(BlazeClock.instance())),
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileFunctionTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileFunctionTest.java
index b5fe926..7555381 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileFunctionTest.java
@@ -24,7 +24,6 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
@@ -53,6 +52,7 @@
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.SyscallCache;
 import com.google.devtools.build.skyframe.EvaluationContext;
@@ -126,7 +126,7 @@
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
                 .put(FileValue.FILE, new FileFunction(packageLocator))
                 .put(
-                    FileStateValue.FILE_STATE,
+                    FileStateKey.FILE_STATE,
                     new FileStateFunction(
                         Suppliers.ofInstance(
                             new TimestampGranularityMonitor(BlazeClock.instance())),
diff --git a/src/test/java/com/google/devtools/build/lib/buildtool/QueryIntegrationTest.java b/src/test/java/com/google/devtools/build/lib/buildtool/QueryIntegrationTest.java
index dabf47d..c9c51a3 100644
--- a/src/test/java/com/google/devtools/build/lib/buildtool/QueryIntegrationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/buildtool/QueryIntegrationTest.java
@@ -21,7 +21,6 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.buildtool.util.BuildIntegrationTestCase;
 import com.google.devtools.build.lib.events.EventKind;
@@ -44,6 +43,7 @@
 import com.google.devtools.build.lib.unix.UnixFileSystem;
 import com.google.devtools.build.lib.util.ExitCode;
 import com.google.devtools.build.lib.vfs.DigestHashFunction;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.Path;
@@ -816,7 +816,7 @@
             NotifyingHelper.makeNotifyingTransformer(
                 (key, type, order, context) -> {
                   if (NotifyingHelper.EventType.IS_READY.equals(type)
-                      && FileStateValue.FILE_STATE.equals(key.functionName())
+                      && FileStateKey.FILE_STATE.equals(key.functionName())
                       && barFile.equals(((RootedPath) key.argument()).getRootRelativePath())) {
                     TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions(
                         directoryListingLatch, "Directory never listed");
diff --git a/src/test/java/com/google/devtools/build/lib/query2/RBuildFilesVisitorTest.java b/src/test/java/com/google/devtools/build/lib/query2/RBuildFilesVisitorTest.java
index ce2bf6d..887a40b 100644
--- a/src/test/java/com/google/devtools/build/lib/query2/RBuildFilesVisitorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/query2/RBuildFilesVisitorTest.java
@@ -15,8 +15,8 @@
 
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.devtools.build.lib.actions.FileStateValue.DIRECTORY_FILE_STATE_NODE;
-import static com.google.devtools.build.lib.actions.FileStateValue.FILE_STATE;
 import static com.google.devtools.build.lib.skyframe.SkyFunctions.PACKAGE_LOOKUP;
+import static com.google.devtools.build.lib.vfs.FileStateKey.FILE_STATE;
 import static org.mockito.ArgumentMatchers.any;
 import static org.mockito.Mockito.mock;
 import static org.mockito.Mockito.times;
diff --git a/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageHelperTest.java b/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageHelperTest.java
index a07ec04..f9b0cc8 100644
--- a/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageHelperTest.java
+++ b/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageHelperTest.java
@@ -24,7 +24,6 @@
 import com.google.common.base.Suppliers;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.ThreadStateReceiver;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
@@ -58,6 +57,7 @@
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
 import com.google.devtools.build.lib.skyframe.WorkspaceFileFunction;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.RootedPath;
@@ -139,7 +139,7 @@
             BazelSkyframeExecutorConstants.BUILD_FILES_BY_PRIORITY,
             BazelSkyframeExecutorConstants.EXTERNAL_PACKAGE_HELPER));
     skyFunctions.put(
-        FileStateValue.FILE_STATE,
+        FileStateKey.FILE_STATE,
         new FileStateFunction(
             Suppliers.ofInstance(new TimestampGranularityMonitor(BlazeClock.instance())),
             SyscallCache.NO_CACHE,
diff --git a/src/test/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorTest.java b/src/test/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorTest.java
index 28ee40a..7d92432 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorTest.java
@@ -26,7 +26,6 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.hash.HashFunction;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.ThreadStateReceiver;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
@@ -78,6 +77,7 @@
 import com.google.devtools.build.lib.testutil.TestConstants;
 import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
@@ -177,7 +177,7 @@
         new InMemoryMemoizingEvaluator(
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
                 .put(
-                    FileStateValue.FILE_STATE,
+                    FileStateKey.FILE_STATE,
                     new FileStateFunction(
                         Suppliers.ofInstance(
                             new TimestampGranularityMonitor(BlazeClock.instance())),
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
index ac3e591..ee39f2c 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
@@ -20,7 +20,6 @@
 import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.ThreadStateReceiver;
 import com.google.devtools.build.lib.actions.util.InjectedActionLookupKey;
@@ -37,6 +36,7 @@
 import com.google.devtools.build.lib.testutil.TestUtils;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.DigestHashFunction;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -101,7 +101,7 @@
         new InMemoryMemoizingEvaluator(
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
                 .put(
-                    FileStateValue.FILE_STATE,
+                    FileStateKey.FILE_STATE,
                     new FileStateFunction(
                         Suppliers.ofInstance(
                             new TimestampGranularityMonitor(BlazeClock.instance())),
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
index 99e4e39..b03e815 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
@@ -20,7 +20,6 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.testing.EqualsTester;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.ThreadStateReceiver;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
@@ -45,6 +44,7 @@
 import com.google.devtools.build.lib.skyframe.PackageLookupValue.ErrorReason;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.SyscallCache;
@@ -125,7 +125,7 @@
         new IgnoredPackagePrefixesFunction(
             /*ignoredPackagePrefixesFile=*/ PathFragment.EMPTY_FRAGMENT));
     skyFunctions.put(
-        FileStateValue.FILE_STATE,
+        FileStateKey.FILE_STATE,
         new FileStateFunction(
             Suppliers.ofInstance(new TimestampGranularityMonitor(BlazeClock.instance())),
             SyscallCache.NO_CACHE,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
index ced01a7..408fe0e 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
@@ -68,6 +68,7 @@
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.DigestHashFunction;
 import com.google.devtools.build.lib.vfs.FileAccessException;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
@@ -166,7 +167,7 @@
         new InMemoryMemoizingEvaluator(
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
                 .put(
-                    FileStateValue.FILE_STATE,
+                    FileStateKey.FILE_STATE,
                     new FileStateFunction(
                         Suppliers.ofInstance(
                             new TimestampGranularityMonitor(BlazeClock.instance())),
@@ -852,7 +853,7 @@
 
   private static Set<RootedPath> filesSeen(MemoizingEvaluator graph) {
     return graph.getValues().keySet().stream()
-        .filter(SkyFunctionName.functionIs(FileStateValue.FILE_STATE))
+        .filter(SkyFunctionName.functionIs(FileStateKey.FILE_STATE))
         .map(SkyKey::argument)
         .map(RootedPath.class::cast)
         .collect(toImmutableSet());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FileSystemValueCheckerInferringAncestorsTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FileSystemValueCheckerInferringAncestorsTest.java
index d86ba3d..367e534 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FileSystemValueCheckerInferringAncestorsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FileSystemValueCheckerInferringAncestorsTest.java
@@ -36,6 +36,7 @@
 import com.google.devtools.build.lib.util.AbruptExitException;
 import com.google.devtools.build.lib.vfs.DelegateFileSystem;
 import com.google.devtools.build.lib.vfs.Dirent;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.Path;
@@ -124,7 +125,7 @@
   @Test
   public void getDiffWithInferredAncestors_fileModified_returnsFileWithValues() throws Exception {
     scratch.file("file", "hello");
-    FileStateValue.Key key = fileStateValueKey("file");
+    FileStateKey key = fileStateValueKey("file");
     FileStateValue value = fileStateValue("file");
     scratch.overwriteFile("file", "there");
 
@@ -145,7 +146,7 @@
   @Test
   public void getDiffWithInferredAncestors_fileAdded_returnsFileAndDirListing() throws Exception {
     scratch.file("file");
-    FileStateValue.Key key = fileStateValueKey("file");
+    FileStateKey key = fileStateValueKey("file");
 
     ImmutableDiff diff =
         FileSystemValueCheckerInferringAncestors.getDiffWithInferredAncestors(
@@ -167,7 +168,7 @@
   public void getDiffWithInferredAncestors_fileWithDirsAdded_returnsFileAndInjectsDirs()
       throws Exception {
     scratch.file("a/b/file");
-    FileStateValue.Key fileKey = fileStateValueKey("a/b/file");
+    FileStateKey fileKey = fileStateValueKey("a/b/file");
 
     ImmutableDiff diff =
         FileSystemValueCheckerInferringAncestors.getDiffWithInferredAncestors(
@@ -206,7 +207,7 @@
   public void getDiffWithInferredAncestors_addedFileWithReportedDirs_returnsFileAndInjectsDirs()
       throws Exception {
     scratch.file("a/b/file");
-    FileStateValue.Key fileKey = fileStateValueKey("a/b/file");
+    FileStateKey fileKey = fileStateValueKey("a/b/file");
 
     ImmutableDiff diff =
         FileSystemValueCheckerInferringAncestors.getDiffWithInferredAncestors(
@@ -280,7 +281,7 @@
   public void getDiffWithInferredAncestors_addEmptyDir_returnsDirAndParentListing()
       throws Exception {
     scratch.dir("dir");
-    FileStateValue.Key key = fileStateValueKey("dir");
+    FileStateKey key = fileStateValueKey("dir");
     FileStateValue value = fileStateValue("dir");
 
     ImmutableDiff diff =
@@ -302,7 +303,7 @@
   public void getDiffWithInferredAncestors_deleteFile_returnsFileParentListing() throws Exception {
     Path file = scratch.file("dir/file1");
     scratch.file("dir/file2");
-    FileStateValue.Key key = fileStateValueKey("dir/file1");
+    FileStateKey key = fileStateValueKey("dir/file1");
     FileStateValue oldValue = fileStateValue("dir/file1");
     file.delete();
 
@@ -325,7 +326,7 @@
   public void getDiffWithInferredAncestors_deleteFileFromDirWithListing_skipsDirStat()
       throws Exception {
     Path file1 = scratch.file("dir/file1");
-    FileStateValue.Key key = fileStateValueKey("dir/file1");
+    FileStateKey key = fileStateValueKey("dir/file1");
     FileStateValue oldValue = fileStateValue("dir/file1");
     file1.delete();
 
@@ -350,7 +351,7 @@
   public void getDiffWithInferredAncestors_deleteLastFileFromDir_ignoresInvalidatedListing()
       throws Exception {
     Path file1 = scratch.file("dir/file1");
-    FileStateValue.Key key = fileStateValueKey("dir/file1");
+    FileStateKey key = fileStateValueKey("dir/file1");
     FileStateValue oldValue = fileStateValue("dir/file1");
     file1.delete();
 
@@ -381,8 +382,8 @@
     file.getParentDirectory()
         .getRelative("symlink")
         .createSymbolicLink(PathFragment.create("file"));
-    FileStateValue.Key fileKey = fileStateValueKey("dir/file");
-    FileStateValue.Key symlinkKey = fileStateValueKey("dir/symlink");
+    FileStateKey fileKey = fileStateValueKey("dir/file");
+    FileStateKey symlinkKey = fileStateValueKey("dir/symlink");
 
     ImmutableDiff diff =
         FileSystemValueCheckerInferringAncestors.getDiffWithInferredAncestors(
@@ -406,8 +407,8 @@
       throws Exception {
     scratch.dir("dir/file1");
     scratch.dir("dir/file2");
-    FileStateValue.Key file1Key = fileStateValueKey("dir/file1");
-    FileStateValue.Key file2Key = fileStateValueKey("dir/file2");
+    FileStateKey file1Key = fileStateValueKey("dir/file1");
+    FileStateKey file2Key = fileStateValueKey("dir/file2");
     DirectoryListingStateValue.Key dirKey = directoryListingStateValueKey("dir");
 
     ImmutableDiff diff =
@@ -446,11 +447,11 @@
     Path file1 = scratch.file("dir/file1");
     Path file2 = scratch.file("dir/file2");
     Path file3 = scratch.file("dir/file3");
-    FileStateValue.Key key1 = fileStateValueKey("dir/file1");
+    FileStateKey key1 = fileStateValueKey("dir/file1");
     FileStateValue oldValue1 = fileStateValue("dir/file1");
-    FileStateValue.Key key2 = fileStateValueKey("dir/file2");
+    FileStateKey key2 = fileStateValueKey("dir/file2");
     FileStateValue oldValue2 = fileStateValue("dir/file2");
-    FileStateValue.Key key3 = fileStateValueKey("dir/file3");
+    FileStateKey key3 = fileStateValueKey("dir/file3");
     FileStateValue oldValue3 = fileStateValue("dir/file3");
     file1.delete();
     file2.delete();
@@ -486,11 +487,11 @@
   public void getDiffWithInferredAncestors_deleteFileWithDirs_returnsFileAndDirs()
       throws Exception {
     scratch.file("a/b/c/file");
-    FileStateValue.Key abKey = fileStateValueKey("a/b");
+    FileStateKey abKey = fileStateValueKey("a/b");
     FileStateValue abValue = fileStateValue("a/b");
-    FileStateValue.Key abcKey = fileStateValueKey("a/b/c");
+    FileStateKey abcKey = fileStateValueKey("a/b/c");
     FileStateValue abcValue = fileStateValue("a/b/c");
-    FileStateValue.Key abcFileKey = fileStateValueKey("a/b/c/file");
+    FileStateKey abcFileKey = fileStateValueKey("a/b/c/file");
     FileStateValue abcFileValue = fileStateValue("a/b/c/file");
     scratch.dir("a/b").deleteTree();
 
@@ -527,11 +528,11 @@
   public void getDiffWithInferredAncestors_deleteFileWithReportedDirs_returnsFileAndDirListings()
       throws Exception {
     scratch.file("a/b/c/file");
-    FileStateValue.Key abKey = fileStateValueKey("a/b");
+    FileStateKey abKey = fileStateValueKey("a/b");
     FileStateValue abValue = fileStateValue("a/b");
-    FileStateValue.Key abcKey = fileStateValueKey("a/b/c");
+    FileStateKey abcKey = fileStateValueKey("a/b/c");
     FileStateValue abcValue = fileStateValue("a/b/c");
-    FileStateValue.Key abcFileKey = fileStateValueKey("a/b/c/file");
+    FileStateKey abcFileKey = fileStateValueKey("a/b/c/file");
     FileStateValue abcFileValue = fileStateValue("a/b/c/file");
     scratch.dir("a/b").deleteTree();
 
@@ -569,9 +570,9 @@
       throws Exception {
     Path file1 = scratch.file("dir/file1");
     scratch.file("dir/file2", "1");
-    FileStateValue.Key file1Key = fileStateValueKey("dir/file1");
+    FileStateKey file1Key = fileStateValueKey("dir/file1");
     FileStateValue file1Value = fileStateValue("dir/file1");
-    FileStateValue.Key file2Key = fileStateValueKey("dir/file2");
+    FileStateKey file2Key = fileStateValueKey("dir/file2");
     FileStateValue file2Value = fileStateValue("dir/file2");
     file1.delete();
     scratch.overwriteFile("dir/file2", "12");
@@ -602,11 +603,11 @@
   public void getDiffWithInferredAncestors_deleteDirReportDirOnly_returnsDir() throws Exception {
     Path file1 = scratch.file("dir/file1");
     scratch.file("dir/file2");
-    FileStateValue.Key file1Key = fileStateValueKey("dir/file1");
+    FileStateKey file1Key = fileStateValueKey("dir/file1");
     FileStateValue file1Value = fileStateValue("dir/file1");
-    FileStateValue.Key file2Key = fileStateValueKey("dir/file2");
+    FileStateKey file2Key = fileStateValueKey("dir/file2");
     FileStateValue file2Value = fileStateValue("dir/file2");
-    FileStateValue.Key dirKey = fileStateValueKey("dir");
+    FileStateKey dirKey = fileStateValueKey("dir");
     FileStateValue dirValue = fileStateValue("dir");
     file1.getParentDirectory().deleteTree();
 
@@ -655,7 +656,7 @@
     throwOnStat = new IOException("oh no");
     ImmutableMap<SkyKey, SkyValue> graphValues =
         ImmutableMap.of(fileStateValueKey("file"), NONEXISTENT_FILE_STATE_NODE);
-    ImmutableSet<SkyKey> modifiedKeys = ImmutableSet.of(fileStateValueKey("file"));
+    ImmutableSet<FileStateKey> modifiedKeys = ImmutableSet.of(fileStateValueKey("file"));
 
     AbruptExitException e =
         assertThrows(
@@ -679,7 +680,7 @@
     throwOnStat = new RuntimeException("oh no");
     ImmutableMap<SkyKey, SkyValue> graphValues =
         ImmutableMap.of(fileStateValueKey("file"), NONEXISTENT_FILE_STATE_NODE);
-    ImmutableSet<SkyKey> modifiedKeys = ImmutableSet.of(fileStateValueKey("file"));
+    ImmutableSet<FileStateKey> modifiedKeys = ImmutableSet.of(fileStateValueKey("file"));
 
     assertThrows(
         IllegalStateException.class,
@@ -699,7 +700,7 @@
         .containsAtLeastElementsIn(list);
   }
 
-  private FileStateValue.Key fileStateValueKey(String relativePath) {
+  private FileStateKey fileStateValueKey(String relativePath) {
     return FileStateValue.key(
         RootedPath.toRootedPath(root, root.asPath().getRelative(relativePath)));
   }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
index 60df6c6..6d56894 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
@@ -47,6 +47,7 @@
 import com.google.devtools.build.lib.testutil.TestConstants;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
@@ -103,7 +104,7 @@
     Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
 
     skyFunctions.put(
-        FileStateValue.FILE_STATE,
+        FileStateKey.FILE_STATE,
         new FileStateFunction(
             Suppliers.ofInstance(new TimestampGranularityMonitor(BlazeClock.instance())),
             SyscallCache.NO_CACHE,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
index c0155de..166484f 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
@@ -64,6 +64,7 @@
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.BatchStat;
 import com.google.devtools.build.lib.vfs.DigestHashFunction;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.FileStatusWithDigest;
 import com.google.devtools.build.lib.vfs.FileStatusWithDigestAdapter;
@@ -282,7 +283,7 @@
     ExternalFilesHelper externalFilesHelper = ExternalFilesHelper.createForTesting(
         pkgLocator, ExternalFileAction.DEPEND_ON_EXTERNAL_PKG_FOR_EXTERNAL_REPO_PATHS, directories);
     skyFunctions.put(
-        FileStateValue.FILE_STATE,
+        FileStateKey.FILE_STATE,
         new FileStateFunction(
             Suppliers.ofInstance(new TimestampGranularityMonitor(BlazeClock.instance())),
             SyscallCache.NO_CACHE,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
index 0345f5f..7550b10 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
@@ -47,6 +47,7 @@
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.DigestHashFunction;
 import com.google.devtools.build.lib.vfs.Dirent;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
@@ -175,7 +176,7 @@
         SkyFunctions.IGNORED_PACKAGE_PREFIXES,
         BazelSkyframeExecutorConstants.IGNORED_PACKAGE_PREFIXES_FUNCTION);
     skyFunctions.put(
-        FileStateValue.FILE_STATE,
+        FileStateKey.FILE_STATE,
         new FileStateFunction(
             Suppliers.ofInstance(new TimestampGranularityMonitor(BlazeClock.instance())),
             SyscallCache.NO_CACHE,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java
index 13a7e94..a35da59 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java
@@ -18,7 +18,6 @@
 
 import com.google.common.base.Suppliers;
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ServerDirectories;
@@ -35,6 +34,7 @@
 import com.google.devtools.build.lib.skyframe.PackageLookupFunction.CrossRepositoryLabelViolationStrategy;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
@@ -95,7 +95,7 @@
             BazelSkyframeExecutorConstants.BUILD_FILES_BY_PRIORITY,
             BazelSkyframeExecutorConstants.EXTERNAL_PACKAGE_HELPER));
     skyFunctions.put(
-        FileStateValue.FILE_STATE,
+        FileStateKey.FILE_STATE,
         new FileStateFunction(
             Suppliers.ofInstance(new TimestampGranularityMonitor(BlazeClock.instance())),
             SyscallCache.NO_CACHE,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
index ba2df2e..7237ab6 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
@@ -47,6 +47,7 @@
 import com.google.devtools.build.lib.skyframe.PackageLookupValue.IncorrectRepositoryReferencePackageLookupValue;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
@@ -130,7 +131,7 @@
             PackageFunction.IncrementalityIntent.INCREMENTAL,
             k -> ThreadStateReceiver.NULL_INSTANCE));
     skyFunctions.put(
-        FileStateValue.FILE_STATE,
+        FileStateKey.FILE_STATE,
         new FileStateFunction(
             Suppliers.ofInstance(new TimestampGranularityMonitor(BlazeClock.instance())),
             SyscallCache.NO_CACHE,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PathCasingLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PathCasingLookupFunctionTest.java
index 1096d4f..ac0c336 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PathCasingLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PathCasingLookupFunctionTest.java
@@ -28,6 +28,7 @@
 import com.google.devtools.build.lib.skyframe.ExternalFilesHelper.ExternalFileAction;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
@@ -81,7 +82,7 @@
 
     Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
     skyFunctions.put(
-        FileStateValue.FILE_STATE,
+        FileStateKey.FILE_STATE,
         new FileStateFunction(
             Suppliers.ofInstance(new TimestampGranularityMonitor(BlazeClock.instance())),
             SyscallCache.NO_CACHE,
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 2526d5b..a03bce8 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
@@ -67,6 +67,7 @@
 import com.google.devtools.build.lib.testutil.TimestampGranularityUtils;
 import com.google.devtools.build.lib.util.io.OutErr;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -143,7 +144,7 @@
     ConfiguredRuleClassProvider ruleClassProvider = analysisMock.createRuleClassProvider();
     Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
     skyFunctions.put(
-        FileStateValue.FILE_STATE,
+        FileStateKey.FILE_STATE,
         new FileStateFunction(
             Suppliers.ofInstance(new TimestampGranularityMonitor(BlazeClock.instance())),
             SyscallCache.NO_CACHE,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
index 595b758..713ebfd 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -46,7 +46,6 @@
 import com.google.devtools.build.lib.actions.BuildFailedException;
 import com.google.devtools.build.lib.actions.DiscoveredModulesPruner;
 import com.google.devtools.build.lib.actions.Executor;
-import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.actions.MetadataProvider;
 import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
@@ -94,6 +93,7 @@
 import com.google.devtools.build.lib.util.AbruptExitException;
 import com.google.devtools.build.lib.util.DetailedExitCode;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileStateKey;
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
@@ -254,7 +254,7 @@
         new InMemoryMemoizingEvaluator(
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
                 .put(
-                    FileStateValue.FILE_STATE,
+                    FileStateKey.FILE_STATE,
                     new FileStateFunction(() -> tsgm, SyscallCache.NO_CACHE, externalFilesHelper))
                 .put(FileValue.FILE, new FileFunction(pkgLocator))
                 .put(