Replace LegacySkyKey by AbstractSkyKey or custom SkyKeys. AbstractSkyKey doesn't save memory in the 32-bit case, but makes it easier for people to see how many SkyKeys we have.

There's some unnecessary interning in tests, but it was easier to copypasta and doesn't harm anything, I think.

PiperOrigin-RevId: 187694309

14 files changed, 193 insertions, 89 deletions

diff --git a/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java b/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java
index 44808dee10..8d07983cd5 100644
--- a/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java
+++ b/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java
@@ -52,9 +52,9 @@ import com.google.devtools.build.lib.skyframe.WorkspaceFileFunction;
 import com.google.devtools.build.lib.syntax.SkylarkSemantics;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.Root;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
 import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
@@ -214,8 +214,8 @@ public class ExternalPackageUtilTest extends BuildViewTestCase {
   // HELPER SKYFUNCTIONS
 
   // GetRuleByName.
-  SkyKey getRuleByNameKey(String ruleName) {
-    return LegacySkyKey.create(GET_RULE_BY_NAME_FUNCTION, ruleName);
+  private static SkyKey getRuleByNameKey(String ruleName) {
+    return new Key(ruleName);
   }
 
   EvaluationResult<GetRuleByNameValue> getRuleByName(SkyKey key) throws InterruptedException {
@@ -261,8 +261,8 @@ public class ExternalPackageUtilTest extends BuildViewTestCase {
   }
 
   // GetRegisteredToolchains.
-  SkyKey getRegisteredToolchainsKey() {
-    return LegacySkyKey.create(GET_REGISTERED_TOOLCHAINS_FUNCTION, "singleton");
+  private static SkyKey getRegisteredToolchainsKey() {
+    return () -> GET_REGISTERED_TOOLCHAINS_FUNCTION;
   }
 
   EvaluationResult<GetRegisteredToolchainsValue> getRegisteredToolchains(SkyKey key)
@@ -309,8 +309,8 @@ public class ExternalPackageUtilTest extends BuildViewTestCase {
   }
 
   // GetRegisteredExecutionPlatforms.
-  SkyKey getRegisteredExecutionPlatformsKey() {
-    return LegacySkyKey.create(GET_REGISTERED_EXECUTION_PLATFORMS_FUNCTION, "singleton");
+  private static SkyKey getRegisteredExecutionPlatformsKey() {
+    return () -> GET_REGISTERED_EXECUTION_PLATFORMS_FUNCTION;
   }
 
   EvaluationResult<GetRegisteredExecutionPlatformsValue> getRegisteredExecutionPlatforms(SkyKey key)
@@ -356,4 +356,15 @@ public class ExternalPackageUtilTest extends BuildViewTestCase {
       return null;
     }
   }
+
+  static class Key extends AbstractSkyKey<String> {
+    private Key(String arg) {
+      super(arg);
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return GET_RULE_BY_NAME_FUNCTION;
+    }
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
index e8632b45e4..bc0d3ec083 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
@@ -48,8 +48,8 @@ import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
 import com.google.devtools.build.lib.testutil.Suite;
 import com.google.devtools.build.lib.testutil.TestSpec;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.EvaluationResult;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -98,11 +98,20 @@ public class ConfigurationsForTargetsTest extends AnalysisTestCase {
       this.stateProvider = lateBoundStateProvider;
     }
 
-    /**
-     * Returns a {@link SkyKey} for a given <Target, BuildConfiguration> pair.
-     */
-    static SkyKey key(Target target, BuildConfiguration config) {
-      return LegacySkyKey.create(SKYFUNCTION_NAME, new TargetAndConfiguration(target, config));
+    /** Returns a {@link SkyKey} for a given <Target, BuildConfiguration> pair. */
+    private static Key key(Target target, BuildConfiguration config) {
+      return new Key(new TargetAndConfiguration(target, config));
+    }
+
+    private static class Key extends AbstractSkyKey<TargetAndConfiguration> {
+      private Key(TargetAndConfiguration arg) {
+        super(arg);
+      }
+
+      @Override
+      public SkyFunctionName functionName() {
+        return SKYFUNCTION_NAME;
+      }
     }
 
     /**
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 0da51f8f50..719195dbc5 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
@@ -233,14 +233,18 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
   }
 
   private static TraversalRequest fileLikeRoot(Artifact file, PackageBoundaryMode pkgBoundaryMode) {
-    return new TraversalRequest(DirectTraversalRoot.forFileOrDirectory(file),
-        !file.isSourceArtifact(), pkgBoundaryMode, false, null);
+    return TraversalRequest.create(
+        DirectTraversalRoot.forFileOrDirectory(file),
+        !file.isSourceArtifact(),
+        pkgBoundaryMode,
+        false,
+        null);
   }
 
   private static TraversalRequest pkgRoot(
       RootedPath pkgDirectory, PackageBoundaryMode pkgBoundaryMode) {
-    return new TraversalRequest(DirectTraversalRoot.forRootedPath(pkgDirectory), false,
-        pkgBoundaryMode, true, null);
+    return TraversalRequest.create(
+        DirectTraversalRoot.forRootedPath(pkgDirectory), false, pkgBoundaryMode, true, null);
   }
 
   private <T extends SkyValue> EvaluationResult<T> eval(SkyKey key) throws Exception {
@@ -253,14 +257,9 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
 
   private RecursiveFilesystemTraversalValue evalTraversalRequest(TraversalRequest params)
       throws Exception {
-    SkyKey key = rftvSkyKey(params);
-    EvaluationResult<RecursiveFilesystemTraversalValue> result = eval(key);
+    EvaluationResult<RecursiveFilesystemTraversalValue> result = eval(params);
     assertThat(result.hasError()).isFalse();
-    return result.get(key);
-  }
-
-  private static SkyKey rftvSkyKey(TraversalRequest params) {
-    return RecursiveFilesystemTraversalValue.key(params);
+    return result.get(params);
   }
 
   /**
@@ -388,7 +387,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     // Edit the file and verify that the value is rebuilt.
     appendToFile(rootArtifact, "bar");
     RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(traversalRoot, expected);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v2);
     assertThat(v2).isNotEqualTo(v1);
     assertTraversalRootHashesAreNotEqual(v1, v2);
@@ -428,7 +427,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     // Edit the target of the symlink and verify that the value is rebuilt.
     appendToFile(linkTargetArtifact, "bar");
     RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(traversalRoot, expected);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v2);
     assertThat(v2).isNotEqualTo(v1);
     assertTraversalRootHashesAreNotEqual(v1, v2);
@@ -490,7 +489,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     ResolvedFile expected3 = regularFileForTesting(file3);
     RecursiveFilesystemTraversalValue v2 =
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v2);
     // Directories always have the same hash code, but that is fine because their contents are also
     // part of the RecursiveFilesystemTraversalValue, so v1 and v2 are unequal.
@@ -504,7 +503,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
       SkyKey toInvalidate = FileStateValue.key(file1);
       appendToFile(file1, toInvalidate, "bar");
       v3 = traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
-      assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+      assertThat(progressReceiver.invalidations).contains(traversalRoot);
       assertThat(progressReceiver.evaluations).contains(v3);
       assertThat(v3).isNotEqualTo(v2);
       // Directories always have the same hash code, but that is fine because their contents are
@@ -525,7 +524,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
     assertThat(v4).isEqualTo(v3);
     assertTraversalRootHashesAreEqual(v3, v4);
-    assertThat(progressReceiver.invalidations).doesNotContain(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).doesNotContain(traversalRoot);
   }
 
   @Test
@@ -609,7 +608,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     ResolvedFile expected4 = regularFileForTesting(childOf(linkNameArtifact, "file.3"));
     RecursiveFilesystemTraversalValue v2 =
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3, expected4);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v2);
     assertThat(v2).isNotEqualTo(v1);
     assertTraversalRootHashesAreNotEqual(v1, v2);
@@ -619,7 +618,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     appendToFile(file1, "bar");
     RecursiveFilesystemTraversalValue v3 =
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3, expected4);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v3);
     assertThat(v3).isNotEqualTo(v2);
     assertTraversalRootHashesAreNotEqual(v2, v3);
@@ -633,7 +632,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3, expected4);
     assertThat(v4).isEqualTo(v3);
     assertTraversalRootHashesAreEqual(v3, v4);
-    assertThat(progressReceiver.invalidations).doesNotContain(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).doesNotContain(traversalRoot);
   }
 
   @Test
@@ -683,7 +682,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
         traverseAndAssertFiles(traversalRoot, expected1);
         break;
       case REPORT_ERROR:
-        SkyKey key = rftvSkyKey(traversalRoot);
+        SkyKey key = traversalRoot;
         EvaluationResult<SkyValue> result = eval(key);
         assertThat(result.hasError()).isTrue();
         assertThat(result.getError().getException())
@@ -809,7 +808,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     // Change the digest of the file. See that the value is rebuilt.
     appendToFile(path, "world");
     RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(params, expected);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(params));
+    assertThat(progressReceiver.invalidations).contains(params);
     assertThat(v2).isNotEqualTo(v1);
     assertTraversalRootHashesAreNotEqual(v1, v2);
   }
@@ -843,7 +842,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     createFile(rootedPath(derivedArtifact("a/b/c/file.fake")));
     createFile(sourceArtifact("a/b/c/BUILD"));
 
-    SkyKey key = rftvSkyKey(fileLikeRoot(genDir, CROSS));
+    SkyKey key = fileLikeRoot(genDir, CROSS);
     EvaluationResult<SkyValue> result = eval(key);
     assertThat(result.hasError()).isTrue();
     ErrorInfo error = result.getError(key);
@@ -858,7 +857,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     Artifact bazLink = sourceArtifact("foo/baz.sym");
     Path parentDir = scratch.dir("foo");
     bazLink.getPath().createSymbolicLink(parentDir);
-    SkyKey key = rftvSkyKey(pkgRoot(parentOf(rootedPath(bazLink)), DONT_CROSS));
+    SkyKey key = pkgRoot(parentOf(rootedPath(bazLink)), DONT_CROSS);
     EvaluationResult<SkyValue> result = eval(key);
     assertThat(result.hasError()).isTrue();
     ErrorInfo error = result.getError(key);
@@ -876,7 +875,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     barLink.getPath().createSymbolicLink(bazLink.getPath());
     bazLink.getPath().createSymbolicLink(fooLink.getPath());
 
-    SkyKey key = rftvSkyKey(pkgRoot(parentOf(rootedPath(bazLink)), DONT_CROSS));
+    SkyKey key = pkgRoot(parentOf(rootedPath(bazLink)), DONT_CROSS);
     EvaluationResult<SkyValue> result = eval(key);
     assertThat(result.hasError()).isTrue();
     ErrorInfo error = result.getError(key);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java
index b6bd39494b..158d6e2942 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java
@@ -18,7 +18,6 @@ import static org.junit.Assert.fail;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
-import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.RootedPath;
diff --git a/src/test/java/com/google/devtools/build/skyframe/BUILD b/src/test/java/com/google/devtools/build/skyframe/BUILD
index f213c16110..712dc503f4 100644
--- a/src/test/java/com/google/devtools/build/skyframe/BUILD
+++ b/src/test/java/com/google/devtools/build/skyframe/BUILD
@@ -31,6 +31,7 @@ java_library(
         "//src/main/java/com/google/devtools/build/lib:util",
         "//src/main/java/com/google/devtools/build/lib/collect",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
         "//src/main/java/com/google/devtools/build/skyframe",
         "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
         "//src/test/java/com/google/devtools/build/lib:testutil",
@@ -52,7 +53,6 @@ java_test(
         ":testutil",
         "//src/main/java/com/google/devtools/build/lib:events",
         "//src/main/java/com/google/devtools/build/lib:util",
-        "//src/main/java/com/google/devtools/build/lib/collect",
         "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/skyframe",
diff --git a/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java b/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
index 06dd49b97c..7cac95f273 100644
--- a/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
@@ -27,8 +27,7 @@ import org.junit.runners.JUnit4;
 @RunWith(JUnit4.class)
 public class CyclesReporterTest {
 
-  private static final SkyKey DUMMY_KEY =
-      LegacySkyKey.create(SkyFunctionName.create("func"), "key");
+  private static final SkyKey DUMMY_KEY = () -> SkyFunctionName.create("func");
 
   @Test
   public void nullEventHandler() {
diff --git a/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java b/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
index a00391481a..9c9d00ee6f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
@@ -47,7 +47,7 @@ public class ErrorInfoTest {
 
   private void runTestFromException(boolean isDirectlyTransient, boolean isTransitivelyTransient) {
     Exception exception = new IOException("ehhhhh");
-    SkyKey causeOfException = LegacySkyKey.create(SkyFunctionName.create("CAUSE"), 1234);
+    SkyKey causeOfException = GraphTester.toSkyKey("CAUSE, 1234");
     DummySkyFunctionException dummyException =
         new DummySkyFunctionException(exception, isDirectlyTransient, /*isCatastrophic=*/ false);
 
@@ -89,8 +89,8 @@ public class ErrorInfoTest {
   public void testFromCycle() {
     CycleInfo cycle =
         new CycleInfo(
-            ImmutableList.of(LegacySkyKey.create(SkyFunctionName.create("PATH"), 1234)),
-            ImmutableList.of(LegacySkyKey.create(SkyFunctionName.create("CYCLE"), 4321)));
+            ImmutableList.of(GraphTester.toSkyKey("PATH, 1234")),
+            ImmutableList.of(GraphTester.toSkyKey("CYCLE, 4321")));
 
     ErrorInfo errorInfo = ErrorInfo.fromCycle(cycle);
 
@@ -105,12 +105,12 @@ public class ErrorInfoTest {
   public void testFromChildErrors() {
     CycleInfo cycle =
         new CycleInfo(
-            ImmutableList.of(LegacySkyKey.create(SkyFunctionName.create("PATH"), 1234)),
-            ImmutableList.of(LegacySkyKey.create(SkyFunctionName.create("CYCLE"), 4321)));
+            ImmutableList.of(GraphTester.toSkyKey("PATH, 1234")),
+            ImmutableList.of(GraphTester.toSkyKey("CYCLE, 4321")));
     ErrorInfo cycleErrorInfo = ErrorInfo.fromCycle(cycle);
 
     Exception exception1 = new IOException("ehhhhh");
-    SkyKey causeOfException1 = LegacySkyKey.create(SkyFunctionName.create("CAUSE1"), 1234);
+    SkyKey causeOfException1 = GraphTester.toSkyKey("CAUSE1, 1234");
     DummySkyFunctionException dummyException1 =
         new DummySkyFunctionException(exception1, /*isTransient=*/ true, /*isCatastrophic=*/ false);
     ErrorInfo exceptionErrorInfo1 = ErrorInfo.fromException(
@@ -119,14 +119,14 @@ public class ErrorInfoTest {
 
     // N.B this ErrorInfo will be catastrophic.
     Exception exception2 = new IOException("blahhhhh");
-    SkyKey causeOfException2 = LegacySkyKey.create(SkyFunctionName.create("CAUSE2"), 5678);
+    SkyKey causeOfException2 = GraphTester.toSkyKey("CAUSE2, 5678");
     DummySkyFunctionException dummyException2 =
         new DummySkyFunctionException(exception2, /*isTransient=*/ false, /*isCatastrophic=*/ true);
     ErrorInfo exceptionErrorInfo2 = ErrorInfo.fromException(
         new ReifiedSkyFunctionException(dummyException2, causeOfException2),
         /*isTransitivelyTransient=*/ false);
 
-    SkyKey currentKey = LegacySkyKey.create(SkyFunctionName.create("CURRENT"), 9876);
+    SkyKey currentKey = GraphTester.toSkyKey("CURRENT, 9876");
 
     ErrorInfo errorInfo = ErrorInfo.fromChildErrors(
         currentKey, ImmutableList.of(cycleErrorInfo, exceptionErrorInfo1, exceptionErrorInfo2));
@@ -184,4 +184,3 @@ public class ErrorInfoTest {
     }
   }
 }
-
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
index a864f48201..378f58c81e 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
@@ -41,8 +41,6 @@ import org.junit.Test;
 
 /** Base class for sanity tests on {@link EvaluableGraph} implementations. */
 public abstract class GraphTest {
-
-  private static final SkyFunctionName SKY_FUNCTION_NAME = SkyFunctionName.FOR_TESTING;
   protected ProcessableGraph graph;
   protected TestRunnableWrapper wrapper;
   private final Version startingVersion = getStartingVersion();
@@ -71,7 +69,7 @@ public abstract class GraphTest {
   }
 
   protected SkyKey key(String name) {
-    return LegacySkyKey.create(SKY_FUNCTION_NAME, name);
+    return GraphTester.toSkyKey(name);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
index 657dd00e4a..a30af1c5c0 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
@@ -19,9 +19,12 @@ import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Interner;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler.Postable;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
@@ -161,7 +164,7 @@ public class GraphTester {
   }
 
   public static SkyKey skyKey(String key) {
-    return LegacySkyKey.create(NODE_TYPE, key);
+    return Key.create(key);
   }
 
   /** A value in the testing graph that is constructed in the tester. */
@@ -276,8 +279,8 @@ public class GraphTester {
 
   public static ImmutableList<SkyKey> toSkyKeys(String... names) {
     ImmutableList.Builder<SkyKey> result = ImmutableList.builder();
-    for (int i = 0; i < names.length; i++) {
-      result.add(LegacySkyKey.create(GraphTester.NODE_TYPE, names[i]));
+    for (String element : names) {
+      result.add(Key.create(element));
     }
     return result.build();
   }
@@ -400,4 +403,24 @@ public class GraphTester {
       }
     };
   }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<String> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    @AutoCodec.VisibleForSerialization
+    Key(String arg) {
+      super(arg);
+    }
+
+    static Key create(String arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctionName.FOR_TESTING;
+    }
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 00969da7c4..b16206cd6b 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -43,15 +43,13 @@ import org.junit.runners.JUnit4;
  */
 @RunWith(JUnit4.class)
 public class InMemoryNodeEntryTest {
-
-  private static final SkyFunctionName NODE_TYPE = SkyFunctionName.create("Type");
   private static final NestedSet<TaggedEvents> NO_EVENTS =
       NestedSetBuilder.<TaggedEvents>emptySet(Order.STABLE_ORDER);
   private static final NestedSet<Postable> NO_POSTS =
       NestedSetBuilder.<Postable>emptySet(Order.STABLE_ORDER);
 
   private static SkyKey key(String name) {
-    return LegacySkyKey.create(NODE_TYPE, name);
+    return GraphTester.toSkyKey(name);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index 7521dd3ea6..d2a5bfc6a6 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -142,7 +142,7 @@ public class MemoizingEvaluatorTest {
   }
 
   private static SkyKey toSkyKey(String name) {
-    return LegacySkyKey.create(NODE_TYPE, name);
+    return GraphTester.toSkyKey(name);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index d0d7b9729f..19c78138f4 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -25,11 +25,13 @@ import com.google.common.base.Supplier;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Interner;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
 import com.google.common.util.concurrent.Uninterruptibles;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.EventKind;
@@ -65,6 +67,9 @@ import org.junit.runners.JUnit4;
  */
 @RunWith(JUnit4.class)
 public class ParallelEvaluatorTest {
+  private static final SkyFunctionName CHILD_TYPE = SkyFunctionName.create("child");
+  private static final SkyFunctionName PARENT_TYPE = SkyFunctionName.create("parent");
+
   protected ProcessableGraph graph;
   protected IntVersion graphVersion = IntVersion.of(0);
   protected GraphTester tester = new GraphTester();
@@ -1548,8 +1553,6 @@ public class ParallelEvaluatorTest {
 
   @Test
   public void testFunctionCrashTrace() throws Exception {
-    final SkyFunctionName childType = SkyFunctionName.create("child");
-    final SkyFunctionName parentType = SkyFunctionName.create("parent");
 
     class ChildFunction implements SkyFunction {
       @Override
@@ -1563,7 +1566,7 @@ public class ParallelEvaluatorTest {
     class ParentFunction implements SkyFunction {
       @Override
       public SkyValue compute(SkyKey skyKey, Environment env) throws InterruptedException {
-        SkyValue dep = env.getValue(LegacySkyKey.create(childType, "billy the kid"));
+        SkyValue dep = env.getValue(ChildKey.create("billy the kid"));
         if (dep == null) {
           return null;
         }
@@ -1573,13 +1576,14 @@ public class ParallelEvaluatorTest {
       @Override public String extractTag(SkyKey skyKey) { return null; }
     }
 
-    ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions = ImmutableMap.of(
-        childType, new ChildFunction(),
-        parentType, new ParentFunction());
+    ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions =
+        ImmutableMap.of(
+            CHILD_TYPE, new ChildFunction(),
+            PARENT_TYPE, new ParentFunction());
     ParallelEvaluator evaluator = makeEvaluator(new InMemoryGraphImpl(), skyFunctions, false);
 
     try {
-      evaluator.eval(ImmutableList.of(LegacySkyKey.create(parentType, "octodad")));
+      evaluator.eval(ImmutableList.of(ParentKey.create("octodad")));
       fail();
     } catch (RuntimeException e) {
       assertThat(e).hasCauseThat().hasMessageThat().isEqualTo("I WANT A PONY!!!");
@@ -2318,4 +2322,38 @@ public class ParallelEvaluatorTest {
       throws Exception {
     runUnhandledTransitiveErrors(/*keepGoing=*/true, /*explicitlyPropagateError=*/true);
   }
+
+  private static class ChildKey extends AbstractSkyKey<String> {
+    private static final Interner<ChildKey> interner = BlazeInterners.newWeakInterner();
+
+    private ChildKey(String arg) {
+      super(arg);
+    }
+
+    static ChildKey create(String arg) {
+      return interner.intern(new ChildKey(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return CHILD_TYPE;
+    }
+  }
+
+  private static class ParentKey extends AbstractSkyKey<String> {
+    private static final Interner<ParentKey> interner = BlazeInterners.newWeakInterner();
+
+    private ParentKey(String arg) {
+      super(arg);
+    }
+
+    private static ParentKey create(String arg) {
+      return interner.intern(new ParentKey(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return PARENT_TYPE;
+    }
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
index 3a603998a8..8d79965842 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
@@ -17,6 +17,8 @@ import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
@@ -28,8 +30,6 @@ import org.junit.runners.Parameterized.Parameters;
 /** Test for {@code ReverseDepsUtility}. */
 @RunWith(Parameterized.class)
 public class ReverseDepsUtilityTest {
-
-  private static final SkyFunctionName NODE_TYPE = SkyFunctionName.create("Type");
   private final int numElements;
 
   @Parameters(name = "numElements-{0}")
@@ -50,14 +50,13 @@ public class ReverseDepsUtilityTest {
     for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) {
       InMemoryNodeEntry example = new InMemoryNodeEntry();
       for (int j = 0; j < numElements; j++) {
-        ReverseDepsUtility.addReverseDeps(
-            example, Collections.singleton(LegacySkyKey.create(NODE_TYPE, j)));
+        ReverseDepsUtility.addReverseDeps(example, Collections.singleton(Key.create(j)));
       }
       // Not a big test but at least check that it does not blow up.
       assertThat(ReverseDepsUtility.toString(example)).isNotEmpty();
       assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
-        ReverseDepsUtility.removeReverseDep(example, LegacySkyKey.create(NODE_TYPE, i));
+        ReverseDepsUtility.removeReverseDep(example, Key.create(i));
       }
       assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
       assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
@@ -71,12 +70,12 @@ public class ReverseDepsUtilityTest {
       InMemoryNodeEntry example = new InMemoryNodeEntry();
       List<SkyKey> toAdd = new ArrayList<>();
       for (int j = 0; j < numElements; j++) {
-        toAdd.add(LegacySkyKey.create(NODE_TYPE, j));
+        toAdd.add(Key.create(j));
       }
       ReverseDepsUtility.addReverseDeps(example, toAdd);
       assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
-        ReverseDepsUtility.removeReverseDep(example, LegacySkyKey.create(NODE_TYPE, i));
+        ReverseDepsUtility.removeReverseDep(example, Key.create(i));
       }
       assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
       assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
@@ -87,12 +86,10 @@ public class ReverseDepsUtilityTest {
   public void testDuplicateCheckOnGetReverseDeps() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
     for (int i = 0; i < numElements; i++) {
-      ReverseDepsUtility.addReverseDeps(
-          example, Collections.singleton(LegacySkyKey.create(NODE_TYPE, i)));
+      ReverseDepsUtility.addReverseDeps(example, Collections.singleton(Key.create(i)));
     }
     // Should only fail when we call getReverseDeps().
-    ReverseDepsUtility.addReverseDeps(
-        example, Collections.singleton(LegacySkyKey.create(NODE_TYPE, 0)));
+    ReverseDepsUtility.addReverseDeps(example, Collections.singleton(Key.create(0)));
     try {
       ReverseDepsUtility.getReverseDeps(example);
       assertThat(numElements).isEqualTo(0);
@@ -103,7 +100,7 @@ public class ReverseDepsUtilityTest {
   @Test
   public void doubleAddThenRemove() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
-    SkyKey key = LegacySkyKey.create(NODE_TYPE, 0);
+    SkyKey key = Key.create(0);
     ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
     // Should only fail when we call getReverseDeps().
     ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
@@ -118,8 +115,8 @@ public class ReverseDepsUtilityTest {
   @Test
   public void doubleAddThenRemoveCheckedOnSize() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
-    SkyKey fixedKey = LegacySkyKey.create(NODE_TYPE, 0);
-    SkyKey key = LegacySkyKey.create(NODE_TYPE, 1);
+    SkyKey fixedKey = Key.create(0);
+    SkyKey key = Key.create(1);
     ReverseDepsUtility.addReverseDeps(example, ImmutableList.of(fixedKey, key));
     // Should only fail when we reach the limit.
     ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
@@ -135,8 +132,8 @@ public class ReverseDepsUtilityTest {
   @Test
   public void addRemoveAdd() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
-    SkyKey fixedKey = LegacySkyKey.create(NODE_TYPE, 0);
-    SkyKey key = LegacySkyKey.create(NODE_TYPE, 1);
+    SkyKey fixedKey = Key.create(0);
+    SkyKey key = Key.create(1);
     ReverseDepsUtility.addReverseDeps(example, ImmutableList.of(fixedKey, key));
     ReverseDepsUtility.removeReverseDep(example, key);
     ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
@@ -147,18 +144,33 @@ public class ReverseDepsUtilityTest {
   public void testMaybeCheck() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
     for (int i = 0; i < numElements; i++) {
-      ReverseDepsUtility.addReverseDeps(
-          example, Collections.singleton(LegacySkyKey.create(NODE_TYPE, i)));
+      ReverseDepsUtility.addReverseDeps(example, Collections.singleton(Key.create(i)));
       // This should always succeed, since the next element is still not present.
-      ReverseDepsUtility.maybeCheckReverseDepNotPresent(
-          example, LegacySkyKey.create(NODE_TYPE, i + 1));
+      ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, Key.create(i + 1));
     }
     try {
-      ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, LegacySkyKey.create(NODE_TYPE, 0));
+      ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, Key.create(0));
       // Should only fail if empty or above the checking threshold.
       assertThat(numElements == 0 || numElements >= ReverseDepsUtility.MAYBE_CHECK_THRESHOLD)
           .isTrue();
     } catch (Exception expected) {
     }
   }
+
+  private static class Key extends AbstractSkyKey<Integer> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(Integer arg) {
+      super(arg);
+    }
+
+    private static Key create(Integer arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctionName.FOR_TESTING;
+    }
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java b/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
index fc3cb3faa4..d589a7c2d0 100644
--- a/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
@@ -15,6 +15,8 @@ package com.google.devtools.build.skyframe;
 
 import static com.google.common.truth.Truth.assertThat;
 
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import java.io.Serializable;
 import org.junit.Test;
@@ -34,7 +36,7 @@ public class SkyKeyTest {
     assertThat(hashCodeSpy.getNumberOfTimesHashCodeCalled()).isEqualTo(0);
 
     // When a SkyKey is constructed with that HashCodeSpy as its argument,
-    SkyKey originalKey = LegacySkyKey.create(SkyFunctionName.create("TEMP"), hashCodeSpy);
+    SkyKey originalKey = Key.create(hashCodeSpy);
 
     // Then the HashCodeSpy reports that its hashcode method was called once.
     assertThat(hashCodeSpy.getNumberOfTimesHashCodeCalled()).isEqualTo(1);
@@ -83,4 +85,21 @@ public class SkyKeyTest {
       return 42;
     }
   }
+
+  private static class Key extends AbstractSkyKey<HashCodeSpy> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(HashCodeSpy arg) {
+      super(arg);
+    }
+
+    private static Key create(HashCodeSpy arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctionName.FOR_TESTING;
+    }
+  }
 }