diff --git a/src/test/java/com/google/devtools/build/lib/BUILD b/src/test/java/com/google/devtools/build/lib/BUILD
index b5305a2..48f7f27 100644
--- a/src/test/java/com/google/devtools/build/lib/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/BUILD
@@ -184,6 +184,7 @@
         "//src/main/java/com/google/devtools/build/lib/clock",
         "//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/collect/nestedset:fingerprint_cache",
         "//src/main/java/com/google/devtools/build/lib/collect/nestedset:serialization",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/shell",
@@ -705,6 +706,7 @@
         "//src/main/java/com/google/devtools/build/lib:build-base",
         "//src/main/java/com/google/devtools/build/lib:io",
         "//src/main/java/com/google/devtools/build/lib:packages",
+        "//src/main/java/com/google/devtools/build/lib/actions",
         "//src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs",
         "//src/main/java/com/google/devtools/build/skyframe",
         "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ActionCacheCheckerTest.java b/src/test/java/com/google/devtools/build/lib/actions/ActionCacheCheckerTest.java
index 4da84f8..c6de334 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ActionCacheCheckerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ActionCacheCheckerTest.java
@@ -62,7 +62,9 @@
     ArtifactResolver artifactResolver = new FakeArtifactResolverBase();
 
     cache = new CorruptibleCompactPersistentActionCache(scratch.resolve("/cache/test.dat"), clock);
-    cacheChecker = new ActionCacheChecker(cache, artifactResolver, Predicates.alwaysTrue(), null);
+    cacheChecker =
+        new ActionCacheChecker(
+            cache, artifactResolver, new ActionKeyContext(), Predicates.alwaysTrue(), null);
   }
 
   @Before
@@ -167,19 +169,21 @@
 
   @Test
   public void testDifferentActionKey() throws Exception {
-    Action action = new NullAction() {
-      @Override
-      protected String computeKey() {
-        return "key1";
-      }
-    };
+    Action action =
+        new NullAction() {
+          @Override
+          protected String computeKey(ActionKeyContext actionKeyContext) {
+            return "key1";
+          }
+        };
     runAction(action);
-    action = new NullAction() {
-      @Override
-      protected String computeKey() {
-        return "key2";
-      }
-    };
+    action =
+        new NullAction() {
+          @Override
+          protected String computeKey(ActionKeyContext actionKeyContext) {
+            return "key2";
+          }
+        };
     runAction(action);
 
     assertStatistics(
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ActionLookupValueTest.java b/src/test/java/com/google/devtools/build/lib/actions/ActionLookupValueTest.java
index 10126b1..3bcf87b 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ActionLookupValueTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ActionLookupValueTest.java
@@ -33,6 +33,7 @@
 public class ActionLookupValueTest {
 
   private FileSystem fs;
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public void setUp() {
@@ -45,7 +46,7 @@
     Artifact artifact = mock(Artifact.class);
     when(action.getOutputs()).thenReturn(ImmutableSet.of(artifact));
     when(action.canRemoveAfterExecution()).thenReturn(true);
-    ActionLookupValue underTest = new ActionLookupValue(action, false);
+    ActionLookupValue underTest = new ActionLookupValue(actionKeyContext, action, false);
     assertThat(underTest.getGeneratingActionIndex(artifact)).isEqualTo(0);
     assertThat(underTest.getAction(0)).isSameAs(action);
     underTest.actionEvaluated(0, action);
@@ -65,7 +66,7 @@
     when(persistentAction.canRemoveAfterExecution()).thenReturn(false);
     ActionLookupValue underTest =
         new ActionLookupValue(
-            ImmutableList.<ActionAnalysisMetadata>of(normalAction, persistentAction), true);
+            actionKeyContext, ImmutableList.of(normalAction, persistentAction), true);
     assertThat(underTest.getGeneratingActionIndex(normalArtifact)).isEqualTo(0);
     assertThat(underTest.getAction(0)).isSameAs(normalAction);
     assertThat(underTest.getGeneratingActionIndex(persistentOutput)).isEqualTo(1);
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java b/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java
index 1132cce..a3b6f6c 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java
@@ -68,6 +68,7 @@
   private PathFragment alienRelative;
 
   private ArtifactFactory artifactFactory;
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public final void createFiles() throws Exception  {
@@ -194,7 +195,7 @@
   public void testSetGeneratingActionIdempotenceNewActionGraph() throws Exception {
     Artifact a = artifactFactory.getDerivedArtifact(fooRelative, outRoot, NULL_ARTIFACT_OWNER);
     Artifact b = artifactFactory.getDerivedArtifact(barRelative, outRoot, NULL_ARTIFACT_OWNER);
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     Action originalAction = new ActionsTestUtil.NullAction(NULL_ACTION_OWNER, a);
     actionGraph.registerAction(originalAction);
 
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
index 296703e..7c92958 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
@@ -41,6 +41,7 @@
   private Scratch scratch;
   private Path execDir;
   private Root rootDir;
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public final void setRootDir() throws Exception  {
@@ -169,7 +170,7 @@
   @Test
   public void testAddExecPaths() throws Exception {
     List<String> paths = new ArrayList<>();
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     Artifact.addExecPaths(getFooBarArtifacts(actionGraph, false), paths);
     assertThat(paths).containsExactly("bar1.h", "bar2.h");
   }
@@ -177,7 +178,7 @@
   @Test
   public void testAddExpandedExecPathStrings() throws Exception {
     List<String> paths = new ArrayList<>();
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     Artifact.addExpandedExecPathStrings(getFooBarArtifacts(actionGraph, true), paths,
         ActionInputHelper.actionGraphArtifactExpander(actionGraph));
     assertThat(paths).containsExactly("bar1.h", "bar1.h", "bar2.h", "bar3.h");
@@ -186,7 +187,7 @@
   @Test
   public void testAddExpandedExecPaths() throws Exception {
     List<PathFragment> paths = new ArrayList<>();
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     Artifact.addExpandedExecPaths(getFooBarArtifacts(actionGraph, true), paths,
         ActionInputHelper.actionGraphArtifactExpander(actionGraph));
     assertThat(paths).containsExactly(
@@ -199,7 +200,7 @@
   @Test
   public void testAddExpandedArtifacts() throws Exception {
     List<Artifact> expanded = new ArrayList<>();
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     List<Artifact> original = getFooBarArtifacts(actionGraph, true);
     Artifact.addExpandedArtifacts(original, expanded,
         ActionInputHelper.actionGraphArtifactExpander(actionGraph));
@@ -219,7 +220,7 @@
   @Test
   public void testAddExecPathsNewActionGraph() throws Exception {
     List<String> paths = new ArrayList<>();
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     Artifact.addExecPaths(getFooBarArtifacts(actionGraph, false), paths);
     assertThat(paths).containsExactly("bar1.h", "bar2.h");
   }
@@ -227,7 +228,7 @@
   @Test
   public void testAddExpandedExecPathStringsNewActionGraph() throws Exception {
     List<String> paths = new ArrayList<>();
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     Artifact.addExpandedExecPathStrings(getFooBarArtifacts(actionGraph, true), paths,
         ActionInputHelper.actionGraphArtifactExpander(actionGraph));
     assertThat(paths).containsExactly("bar1.h", "bar1.h", "bar2.h", "bar3.h");
@@ -236,7 +237,7 @@
   @Test
   public void testAddExpandedExecPathsNewActionGraph() throws Exception {
     List<PathFragment> paths = new ArrayList<>();
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     Artifact.addExpandedExecPaths(getFooBarArtifacts(actionGraph, true), paths,
         ActionInputHelper.actionGraphArtifactExpander(actionGraph));
     assertThat(paths).containsExactly(
@@ -250,7 +251,7 @@
   @Test
   public void testAddExpandedArtifactsNewActionGraph() throws Exception {
     List<Artifact> expanded = new ArrayList<>();
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     List<Artifact> original = getFooBarArtifacts(actionGraph, true);
     Artifact.addExpandedArtifacts(original, expanded,
         ActionInputHelper.actionGraphArtifactExpander(actionGraph));
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java b/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java
index 7b73cf3..f6f9a52 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java
@@ -39,6 +39,7 @@
   private Root outputRoot;
   TestFileOutErr outErr;
   private Executor executor;
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public final void createExecutor() throws Exception  {
@@ -55,7 +56,11 @@
         executor,
         new SingleBuildFileCache(execRoot.getPathString(), execRoot.getFileSystem()),
         ActionInputPrefetcher.NONE,
-        null, outErr, ImmutableMap.<String, String>of(), null);
+        actionKeyContext,
+        null,
+        outErr,
+        ImmutableMap.<String, String>of(),
+        null);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/actions/FailActionTest.java b/src/test/java/com/google/devtools/build/lib/actions/FailActionTest.java
index f339519..5b39c35 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/FailActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/FailActionTest.java
@@ -35,8 +35,9 @@
   private Artifact anOutput;
   private Collection<Artifact> outputs;
   private FailAction failAction;
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
-  protected MutableActionGraph actionGraph = new MapBasedActionGraph();
+  protected MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
 
   @Before
   public final void setUp() throws Exception  {
diff --git a/src/test/java/com/google/devtools/build/lib/actions/MapBasedActionGraphTest.java b/src/test/java/com/google/devtools/build/lib/actions/MapBasedActionGraphTest.java
index b3c8cb2..9d65341 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/MapBasedActionGraphTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/MapBasedActionGraphTest.java
@@ -37,9 +37,11 @@
  */
 @RunWith(JUnit4.class)
 public class MapBasedActionGraphTest {
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
+
   @Test
   public void testSmoke() throws Exception {
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     FileSystem fileSystem = new InMemoryFileSystem(BlazeClock.instance());
     Path path = fileSystem.getPath("/root/foo");
     Artifact output = new Artifact(path, Root.asDerivedRoot(path));
@@ -58,7 +60,7 @@
 
   @Test
   public void testNoActionConflictWhenUnregisteringSharedAction() throws Exception {
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     FileSystem fileSystem = new InMemoryFileSystem(BlazeClock.instance());
     Path path = fileSystem.getPath("/root/foo");
     Artifact output = new Artifact(path, Root.asDerivedRoot(path));
@@ -72,7 +74,7 @@
   }
 
   private static class ActionRegisterer extends AbstractQueueVisitor {
-    private final MutableActionGraph graph = new MapBasedActionGraph();
+    private final MutableActionGraph graph = new MapBasedActionGraph(new ActionKeyContext());
     private final Artifact output;
     // Just to occasionally add actions that were already present.
     private final Set<Action> allActions = Sets.newConcurrentHashSet();
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ResourceManagerTest.java b/src/test/java/com/google/devtools/build/lib/actions/ResourceManagerTest.java
index 2357dc2..947b557 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ResourceManagerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ResourceManagerTest.java
@@ -549,7 +549,7 @@
   }
 
     @Override
-    public String getKey() {
+    public String getKey(ActionKeyContext actionKeyContext) {
       throw new IllegalStateException();
     }
 
diff --git a/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java b/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java
index 7b20c50..f344242 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java
@@ -34,6 +34,7 @@
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.ActionInputPrefetcher;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -103,38 +104,59 @@
 
   private static final Label NULL_LABEL = Label.parseAbsoluteUnchecked("//null/action:owner");
 
-  public static ActionExecutionContext createContext(Executor executor, FileOutErr fileOutErr,
-      Path execRoot, MetadataHandler metadataHandler, @Nullable ActionGraph actionGraph) {
+  public static ActionExecutionContext createContext(
+      Executor executor,
+      ActionKeyContext actionKeyContext,
+      FileOutErr fileOutErr,
+      Path execRoot,
+      MetadataHandler metadataHandler,
+      @Nullable ActionGraph actionGraph) {
     return createContext(
-        executor, fileOutErr, execRoot, metadataHandler, ImmutableMap.<String, String>of(),
+        executor,
+        actionKeyContext,
+        fileOutErr,
+        execRoot,
+        metadataHandler,
+        ImmutableMap.of(),
         actionGraph);
   }
 
-  public static ActionExecutionContext createContext(Executor executor, FileOutErr fileOutErr,
-      Path execRoot, MetadataHandler metadataHandler, Map<String, String> clientEnv,
+  public static ActionExecutionContext createContext(
+      Executor executor,
+      ActionKeyContext actionKeyContext,
+      FileOutErr fileOutErr,
+      Path execRoot,
+      MetadataHandler metadataHandler,
+      Map<String, String> clientEnv,
       @Nullable ActionGraph actionGraph) {
     return new ActionExecutionContext(
         executor,
         new SingleBuildFileCache(execRoot.getPathString(), execRoot.getFileSystem()),
         ActionInputPrefetcher.NONE,
+        actionKeyContext,
         metadataHandler,
         fileOutErr,
-        ImmutableMap.<String, String>copyOf(clientEnv),
+        ImmutableMap.copyOf(clientEnv),
         actionGraph == null
             ? createDummyArtifactExpander()
             : ActionInputHelper.actionGraphArtifactExpander(actionGraph));
   }
 
-  public static ActionExecutionContext createContextForInputDiscovery(Executor executor,
-      FileOutErr fileOutErr, Path execRoot, MetadataHandler metadataHandler,
+  public static ActionExecutionContext createContextForInputDiscovery(
+      Executor executor,
+      ActionKeyContext actionKeyContext,
+      FileOutErr fileOutErr,
+      Path execRoot,
+      MetadataHandler metadataHandler,
       BuildDriver buildDriver) {
     return ActionExecutionContext.forInputDiscovery(
         executor,
         new SingleBuildFileCache(execRoot.getPathString(), execRoot.getFileSystem()),
         ActionInputPrefetcher.NONE,
+        actionKeyContext,
         metadataHandler,
         fileOutErr,
-        ImmutableMap.<String, String>of(),
+        ImmutableMap.of(),
         new BlockingSkyFunctionEnvironment(
             buildDriver, executor == null ? null : executor.getEventHandler()));
   }
@@ -142,8 +164,14 @@
   public static ActionExecutionContext createContext(EventHandler eventHandler) {
     DummyExecutor dummyExecutor = new DummyExecutor(eventHandler);
     return new ActionExecutionContext(
-        dummyExecutor, null, ActionInputPrefetcher.NONE, null, null,
-        ImmutableMap.<String, String>of(), createDummyArtifactExpander());
+        dummyExecutor,
+        null,
+        ActionInputPrefetcher.NONE,
+        new ActionKeyContext(),
+        null,
+        null,
+        ImmutableMap.of(),
+        createDummyArtifactExpander());
   }
 
   private static ArtifactExpander createDummyArtifactExpander() {
@@ -271,7 +299,8 @@
       return ActionResult.EMPTY;
     }
 
-    @Override protected String computeKey() {
+    @Override
+    protected String computeKey(ActionKeyContext actionKeyContext) {
       return "action";
     }
 
diff --git a/src/test/java/com/google/devtools/build/lib/actions/util/TestAction.java b/src/test/java/com/google/devtools/build/lib/actions/util/TestAction.java
index d8b23f1..82867ba 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/util/TestAction.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/util/TestAction.java
@@ -20,6 +20,7 @@
 import com.google.devtools.build.lib.actions.AbstractAction;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.util.Fingerprint;
@@ -126,7 +127,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addPaths(Artifact.asSortedPathFragments(getOutputs()));
     f.addPaths(Artifact.asSortedPathFragments(getMandatoryInputs()));
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java b/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java
index b0a5585..50307b0 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java
@@ -595,7 +595,7 @@
         "        outs=['a.out'])");
     update("//pkg:a.out");
     assertWithMessage("Actions should not be compatible")
-        .that(Actions.canBeShared(action, getGeneratingAction(outputArtifact)))
+        .that(Actions.canBeShared(actionKeyContext, action, getGeneratingAction(outputArtifact)))
         .isFalse();
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/FileWriteActionTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/FileWriteActionTestCase.java
index be8da53..b5be2e4 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/FileWriteActionTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/FileWriteActionTestCase.java
@@ -55,8 +55,16 @@
   @Before
   public final void createExecutorAndContext() throws Exception {
     executor = new TestExecutorBuilder(fileSystem, directories, binTools).build();
-    context = new ActionExecutionContext(executor, null, ActionInputPrefetcher.NONE, null,
-        new FileOutErr(), ImmutableMap.<String, String>of(), null);
+    context =
+        new ActionExecutionContext(
+            executor,
+            null,
+            ActionInputPrefetcher.NONE,
+            actionKeyContext,
+            null,
+            new FileOutErr(),
+            ImmutableMap.<String, String>of(),
+            null);
   }
 
   protected abstract Action createAction(
@@ -109,6 +117,7 @@
                 attributesToFlip.contains(KeyAttributes.DATA) ? "0" : "1",
                 attributesToFlip.contains(KeyAttributes.MAKE_EXECUTABLE));
           }
-        });
+        },
+        actionKeyContext);
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/ParamFileWriteActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/ParamFileWriteActionTest.java
index 8cae433..63397f9 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/ParamFileWriteActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/ParamFileWriteActionTest.java
@@ -166,8 +166,15 @@
     };
 
     Executor executor = new TestExecutorBuilder(fileSystem, directories, binTools).build();
-    return new ActionExecutionContext(executor, null, ActionInputPrefetcher.NONE, null,
-        new FileOutErr(), ImmutableMap.<String, String>of(), artifactExpander);
+    return new ActionExecutionContext(
+        executor,
+        null,
+        ActionInputPrefetcher.NONE,
+        actionKeyContext,
+        null,
+        new FileOutErr(),
+        ImmutableMap.<String, String>of(),
+        artifactExpander);
   }
 
   private enum KeyAttributes {
@@ -198,6 +205,7 @@
               commandLine,
               parameterFileType,
               charset);
-        });
+        },
+        actionKeyContext);
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/PopulateTreeArtifactActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/PopulateTreeArtifactActionTest.java
index 7a9c035..5465e02 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/PopulateTreeArtifactActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/PopulateTreeArtifactActionTest.java
@@ -293,7 +293,8 @@
                 treeArtifactToPopulate,
                 zipper);
           }
-        });
+        },
+        actionKeyContext);
   }
 
   private PopulateTreeArtifactAction createPopulateTreeArtifactAction() throws Exception {
@@ -328,6 +329,7 @@
         executor,
         null,
         ActionInputPrefetcher.NONE,
+        actionKeyContext,
         new TestMetadataHandler(storingExpandedTreeFileArtifacts),
         null,
         ImmutableMap.<String, String>of(),
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTest.java
index 0e5e33d..b40c0d6 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTest.java
@@ -413,7 +413,7 @@
   @Test
   public void testExtraActionInfo() throws Exception {
     SpawnAction action = createCopyFromWelcomeToDestination(ImmutableMap.<String, String>of());
-    ExtraActionInfo info = action.getExtraActionInfo().build();
+    ExtraActionInfo info = action.getExtraActionInfo(actionKeyContext).build();
     assertThat(info.getMnemonic()).isEqualTo("Dummy");
 
     SpawnInfo spawnInfo = info.getExtension(SpawnInfo.spawnInfo);
@@ -450,8 +450,11 @@
         "NONSENSE VARIABLE", "value"
     );
 
-    SpawnInfo spawnInfo = createCopyFromWelcomeToDestination(env).getExtraActionInfo().build()
-        .getExtension(SpawnInfo.spawnInfo);
+    SpawnInfo spawnInfo =
+        createCopyFromWelcomeToDestination(env)
+            .getExtraActionInfo(actionKeyContext)
+            .build()
+            .getExtension(SpawnInfo.spawnInfo);
     assertThat(env).hasSize(spawnInfo.getVariableCount());
     for (EnvironmentVariable variable : spawnInfo.getVariableList()) {
       assertThat(env).containsEntry(variable.getName(), variable.getValue());
@@ -534,7 +537,8 @@
             collectingAnalysisEnvironment.registerAction(actions);
             return actions[0];
           }
-        });
+        },
+        actionKeyContext);
   }
 
   @Test
@@ -587,7 +591,8 @@
         new EventBus());
 
     Artifact artifact = getOnlyElement(getFilesToBuild(getConfiguredTarget("//a:a")));
-    ExtraActionInfo.Builder extraActionInfo = getGeneratingAction(artifact).getExtraActionInfo();
+    ExtraActionInfo.Builder extraActionInfo =
+        getGeneratingAction(artifact).getExtraActionInfo(actionKeyContext);
     assertThat(extraActionInfo.getAspectName()).isEqualTo("//a:def.bzl%aspect1");
     assertThat(extraActionInfo.getAspectParametersMap())
         .containsExactly(
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java
index 1114663..d29e533 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java
@@ -80,6 +80,7 @@
                 executor,
                 null,
                 ActionInputPrefetcher.NONE,
+                actionKeyContext,
                 null,
                 null,
                 ImmutableMap.<String, String>of(),
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionActionTest.java
index 497ed2d..2528e3b 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionActionTest.java
@@ -22,6 +22,7 @@
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionInputPrefetcher;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Executor;
 import com.google.devtools.build.lib.actions.Root;
@@ -58,6 +59,7 @@
   private List<Substitution> substitutions;
   private BlazeDirectories directories;
   private BinTools binTools;
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public final void createDirectoriesAndTools() throws Exception {
@@ -118,7 +120,7 @@
     TemplateExpansionAction b = new TemplateExpansionAction(NULL_ACTION_OWNER,
          outputArtifact2, Template.forString(TEMPLATE),
          ImmutableList.of(Substitution.of("%key%", "foo")), false);
-    assertThat(b.computeKey()).isEqualTo(a.computeKey());
+    assertThat(b.computeKey(actionKeyContext)).isEqualTo(a.computeKey(actionKeyContext));
   }
 
   @Test
@@ -131,7 +133,7 @@
     TemplateExpansionAction b = new TemplateExpansionAction(NULL_ACTION_OWNER,
          outputArtifact2, Template.forString(TEMPLATE),
          ImmutableList.of(Substitution.of("%key%", "foo2")), false);
-    assertThat(a.computeKey().equals(b.computeKey())).isFalse();
+    assertThat(a.computeKey(actionKeyContext).equals(b.computeKey(actionKeyContext))).isFalse();
   }
 
   @Test
@@ -144,7 +146,7 @@
     TemplateExpansionAction b = new TemplateExpansionAction(NULL_ACTION_OWNER,
          outputArtifact2, Template.forString(TEMPLATE),
          ImmutableList.of(Substitution.of("%key%", "foo")), true);
-    assertThat(a.computeKey().equals(b.computeKey())).isFalse();
+    assertThat(a.computeKey(actionKeyContext).equals(b.computeKey(actionKeyContext))).isFalse();
   }
 
   @Test
@@ -157,7 +159,7 @@
     TemplateExpansionAction b = new TemplateExpansionAction(NULL_ACTION_OWNER,
          outputArtifact2, Template.forString(TEMPLATE + " "),
          ImmutableList.of(Substitution.of("%key%", "foo")), false);
-    assertThat(a.computeKey().equals(b.computeKey())).isFalse();
+    assertThat(a.computeKey(actionKeyContext).equals(b.computeKey(actionKeyContext))).isFalse();
   }
 
   private TemplateExpansionAction createWithArtifact() {
@@ -171,8 +173,15 @@
   }
 
   private ActionExecutionContext createContext(Executor executor) {
-    return new ActionExecutionContext(executor, null, ActionInputPrefetcher.NONE, null,
-        new FileOutErr(), ImmutableMap.<String, String>of(), null);
+    return new ActionExecutionContext(
+        executor,
+        null,
+        ActionInputPrefetcher.NONE,
+        actionKeyContext,
+        null,
+        new FileOutErr(),
+        ImmutableMap.<String, String>of(),
+        null);
   }
 
   private void executeTemplateExpansion(String expected) throws Exception {
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/ActionTester.java b/src/test/java/com/google/devtools/build/lib/analysis/util/ActionTester.java
index 7935505..71877d1 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/ActionTester.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/ActionTester.java
@@ -20,6 +20,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Actions;
 import java.util.BitSet;
 import java.util.EnumSet;
@@ -63,7 +64,10 @@
    * different permutations the {@link ActionCombinationFactory} should generate.
    */
   public static <E extends Enum<E>> void runTest(
-      Class<E> attributeClass, ActionCombinationFactory<E> factory) throws Exception {
+      Class<E> attributeClass,
+      ActionCombinationFactory<E> factory,
+      ActionKeyContext actionKeyContext)
+      throws Exception {
     int attributesCount = attributeClass.getEnumConstants().length;
     Preconditions.checkArgument(
         attributesCount <= 30,
@@ -76,16 +80,21 @@
     // Sanity check that the count is correct.
     assertThat(
             Actions.canBeShared(
-                actions[0], factory.generate(makeEnumSetInitializedTo(attributeClass, count))))
+                actionKeyContext,
+                actions[0],
+                factory.generate(makeEnumSetInitializedTo(attributeClass, count))))
         .isTrue();
 
     for (int i = 0; i < actions.length; i++) {
       assertThat(
               Actions.canBeShared(
-                  actions[i], factory.generate(makeEnumSetInitializedTo(attributeClass, i))))
+                  actionKeyContext,
+                  actions[i],
+                  factory.generate(makeEnumSetInitializedTo(attributeClass, i))))
           .isTrue();
       for (int j = i + 1; j < actions.length; j++) {
-        assertWithMessage(i + " and " + j).that(Actions.canBeShared(actions[i], actions[j]))
+        assertWithMessage(i + " and " + j)
+            .that(Actions.canBeShared(actionKeyContext, actions[i], actions[j]))
             .isFalse();
       }
     }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
index 0262305..5b81290 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
@@ -22,6 +22,7 @@
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionGraph;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.BuildView;
@@ -127,6 +128,7 @@
   protected PackageManager packageManager;
   private LoadingPhaseRunner loadingPhaseRunner;
   private BuildView buildView;
+  protected final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   // Note that these configurations are virtual (they use only VFS)
   private BuildConfigurationCollection masterConfig;
@@ -167,6 +169,7 @@
         pkgFactory,
         fileSystem,
         directories,
+        actionKeyContext,
         workspaceStatusActionFactory,
         buildInfoFactories,
         ImmutableList.of(),
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestUtil.java b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestUtil.java
index b36f924..cb6048b 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestUtil.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestUtil.java
@@ -23,6 +23,7 @@
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -189,6 +190,11 @@
     public ImmutableSet<Artifact> getOrphanArtifacts() {
       return original.getOrphanArtifacts();
     }
+
+    @Override
+    public ActionKeyContext getActionKeyContext() {
+      return original.getActionKeyContext();
+    }
   }
 
   /** A dummy WorkspaceStatusAction. */
@@ -227,7 +233,7 @@
     }
 
     @Override
-    public String computeKey() {
+    public String computeKey(ActionKeyContext actionKeyContext) {
       return "";
     }
 
@@ -394,6 +400,11 @@
     public ImmutableSet<Artifact> getOrphanArtifacts() {
       return ImmutableSet.<Artifact>of();
     }
+
+    @Override
+    public ActionKeyContext getActionKeyContext() {
+      return null;
+    }
   };
 
   /**
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index 3345d71..571fe23 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
@@ -33,6 +33,7 @@
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionGraph;
 import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -177,6 +178,7 @@
 
   protected TimestampGranularityMonitor tsgm;
   protected BlazeDirectories directories;
+  protected ActionKeyContext actionKeyContext;
   protected BinTools binTools;
 
   // Note that these configurations are virtual (they use only VFS)
@@ -204,6 +206,7 @@
             new ServerDirectories(outputBase, outputBase),
             rootDirectory,
             analysisMock.getProductName());
+    actionKeyContext = new ActionKeyContext();
     binTools = BinTools.forUnitTesting(directories, analysisMock.getEmbeddedTools());
     mockToolsConfig = new MockToolsConfig(rootDirectory, false);
     analysisMock.setupMockClient(mockToolsConfig);
@@ -213,7 +216,7 @@
     skylarkSemanticsOptions = parseSkylarkSemanticsOptions();
     workspaceStatusActionFactory =
         new AnalysisTestUtil.DummyWorkspaceStatusActionFactory(directories);
-    mutableActionGraph = new MapBasedActionGraph();
+    mutableActionGraph = new MapBasedActionGraph(actionKeyContext);
     ruleClassProvider = getRuleClassProvider();
 
     ImmutableList<PrecomputedValue.Injected> extraPrecomputedValues = ImmutableList.of(
@@ -233,6 +236,7 @@
             pkgFactory,
             fileSystem,
             directories,
+            actionKeyContext,
             workspaceStatusActionFactory,
             ruleClassProvider.getBuildInfoFactories(),
             ImmutableList.<DiffAwareness.Factory>of(),
@@ -493,6 +497,7 @@
   protected CachingAnalysisEnvironment getTestAnalysisEnvironment() {
     return new CachingAnalysisEnvironment(
         view.getArtifactFactory(),
+        actionKeyContext,
         ArtifactOwner.NULL_OWNER,
         /*isSystemEnv=*/ true, /*extendedSanityChecks*/
         false,
@@ -1758,6 +1763,11 @@
     public ImmutableSet<Artifact> getOrphanArtifacts() {
       throw new UnsupportedOperationException();
     }
+
+    @Override
+    public ActionKeyContext getActionKeyContext() {
+      return actionKeyContext;
+    }
   }
 
   protected Iterable<String> baselineCoverageArtifactBasenames(ConfiguredTarget target)
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java
index 5693b37..0e94a10 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
@@ -89,6 +90,7 @@
   protected SequencedSkyframeExecutor skyframeExecutor;
   protected List<ConfigurationFragmentFactory> configurationFragmentFactories;
   protected ImmutableList<Class<? extends FragmentOptions>> buildOptionClasses;
+  protected final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public final void initializeSkyframeExecutor() throws Exception {
@@ -118,6 +120,7 @@
             pkgFactory,
             fileSystem,
             directories,
+            actionKeyContext,
             workspaceStatusActionFactory,
             ruleClassProvider.getBuildInfoFactories(),
             ImmutableList.<DiffAwareness.Factory>of(),
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java
index b0f4f8e..f459808 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java
@@ -64,7 +64,7 @@
     NestedSet<String> other = (NestedSet<String>) deserialized;
     assertThat(subject.getOrder()).isEqualTo(other.getOrder());
     assertThat(subject.toSet()).isEqualTo(other.toSet());
-    verifyStructure(subject.children, other.children);
+    verifyStructure(subject.rawChildren(), other.rawChildren());
   }
 
   private static void verifyStructure(Object lhs, Object rhs) {
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCacheTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCacheTest.java
new file mode 100644
index 0000000..fd8cf96
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCacheTest.java
@@ -0,0 +1,86 @@
+// Copyright 2017 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.collect.nestedset;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.collect.HashMultiset;
+import com.google.common.collect.Multiset;
+import com.google.devtools.build.lib.util.Fingerprint;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@link NestedSetFingerprintCache}. */
+@RunWith(JUnit4.class)
+public class NestedSetFingerprintCacheTest {
+  private static class StringCache extends NestedSetFingerprintCache<String> {
+    private final Multiset<String> fingerprinted = HashMultiset.create();
+
+    @Override
+    protected void addItemFingerprint(Fingerprint fingerprint, String item) {
+      fingerprint.addString(item);
+      fingerprinted.add(item);
+    }
+  }
+
+  private StringCache stringCache;
+
+  @Before
+  public void setup() {
+    stringCache = new StringCache();
+  }
+
+  @Test
+  public void testBasic() {
+    NestedSet<String> nestedSet = NestedSetBuilder.<String>stableOrder().add("a").add("b").build();
+
+    // This test does reimplement the inner algorithm of the cache, but serves
+    // as a simple check that the basic operations do something sensible
+    Fingerprint fingerprint = new Fingerprint();
+    fingerprint.addInt(nestedSet.getOrder().ordinal());
+    Fingerprint subFingerprint = new Fingerprint();
+    subFingerprint.addString("a");
+    subFingerprint.addString("b");
+    fingerprint.addBytes(subFingerprint.digestAndReset());
+    String controlDigest = fingerprint.hexDigestAndReset();
+
+    Fingerprint nestedSetFingerprint = new Fingerprint();
+    stringCache.addNestedSetToFingerprint(nestedSetFingerprint, nestedSet);
+    String nestedSetDigest = nestedSetFingerprint.hexDigestAndReset();
+
+    assertThat(controlDigest).isEqualTo(nestedSetDigest);
+  }
+
+  @Test
+  public void testOnlyFingerprintedOncePerString() {
+    // Leaving leaf nodes with a single item will defeat this check
+    // The nested set builder will effectively inline single-item objects into their parent,
+    // meaning they will get hashed multiple times.
+    NestedSet<String> a = NestedSetBuilder.<String>stableOrder().add("a0").add("a1").build();
+    NestedSet<String> b = NestedSetBuilder.<String>stableOrder().add("b0").add("b1").build();
+    NestedSet<String> c =
+        NestedSetBuilder.<String>stableOrder().add("c").addTransitive(a).addTransitive(b).build();
+    NestedSet<String> d =
+        NestedSetBuilder.<String>stableOrder().add("d").addTransitive(a).addTransitive(b).build();
+    NestedSet<String> e =
+        NestedSetBuilder.<String>stableOrder().add("e").addTransitive(c).addTransitive(d).build();
+    stringCache.addNestedSetToFingerprint(new Fingerprint(), e);
+    assertThat(stringCache.fingerprinted).containsExactly("a0", "a1", "b0", "b1", "c", "d", "e");
+    for (Multiset.Entry<String> entry : stringCache.fingerprinted.entrySet()) {
+      assertThat(entry.getCount()).isEqualTo(1);
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/exec/util/FakeOwner.java b/src/test/java/com/google/devtools/build/lib/exec/util/FakeOwner.java
index cf17e08..37e4515 100644
--- a/src/test/java/com/google/devtools/build/lib/exec/util/FakeOwner.java
+++ b/src/test/java/com/google/devtools/build/lib/exec/util/FakeOwner.java
@@ -18,6 +18,7 @@
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.RunfilesSupplier;
@@ -117,7 +118,7 @@
   }
 
   @Override
-  public String getKey() {
+  public String getKey(ActionKeyContext actionKeyContext) {
     return "MockOwner.getKey";
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java b/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java
index 5dbaa3b..3f199e9 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java
@@ -17,6 +17,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.RuleDefinition;
@@ -71,6 +72,7 @@
   protected PackageFactory packageFactory;
   protected SkyframeExecutor skyframeExecutor;
   protected BlazeDirectories directories;
+  protected final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public final void initializeSkyframeExecutor() throws Exception {
@@ -113,6 +115,7 @@
             packageFactory,
             fileSystem,
             directories,
+            actionKeyContext,
             null, /* workspaceStatusActionFactory */
             ruleClassProvider.getBuildInfoFactories(),
             ImmutableList.<DiffAwareness.Factory>of(),
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/BuildFileModificationTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/BuildFileModificationTest.java
index 3e55ca4..22a55ec 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/BuildFileModificationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/BuildFileModificationTest.java
@@ -18,6 +18,7 @@
 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.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.ServerDirectories;
@@ -61,6 +62,7 @@
   private AnalysisMock analysisMock;
   private ConfiguredRuleClassProvider ruleClassProvider;
   private SkyframeExecutor skyframeExecutor;
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public final void disableLogging() throws Exception {
@@ -83,6 +85,7 @@
                 .build(ruleClassProvider, scratch.getFileSystem()),
             fileSystem,
             directories,
+            actionKeyContext,
             null, /* workspaceStatusActionFactory */
             ruleClassProvider.getBuildInfoFactories(),
             ImmutableList.<DiffAwareness.Factory>of(),
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/IncrementalLoadingTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/IncrementalLoadingTest.java
index 41f48cd..4aac924 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/IncrementalLoadingTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/IncrementalLoadingTest.java
@@ -21,6 +21,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.eventbus.EventBus;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ServerDirectories;
 import com.google.devtools.build.lib.clock.BlazeClock;
@@ -452,6 +453,7 @@
     private final List<Path> changes = new ArrayList<>();
     private boolean everythingModified = false;
     private ModifiedFileSet modifiedFileSet;
+    private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
     public PackageCacheTester(FileSystem fs, ManualClock clock) throws IOException {
       this.clock = clock;
@@ -474,6 +476,7 @@
                   .build(loadingMock.createRuleClassProvider(), fs),
               fs,
               directories,
+              actionKeyContext,
               null, /* workspaceStatusActionFactory */
               loadingMock.createRuleClassProvider().getBuildInfoFactories(),
               ImmutableList.of(new ManualDiffAwarenessFactory()),
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunnerTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunnerTest.java
index ad94d7b..a368664 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunnerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunnerTest.java
@@ -24,6 +24,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.BuildView;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
@@ -588,6 +589,7 @@
     private final List<Path> changes = new ArrayList<>();
     private final LoadingPhaseRunner loadingPhaseRunner;
     private final BlazeDirectories directories;
+    private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
     private LoadingOptions options;
     private final StoredEventHandler storedErrors;
@@ -622,6 +624,7 @@
               pkgFactory,
               fs,
               directories,
+              actionKeyContext,
               null, /* workspaceStatusActionFactory -- not used */
               ruleClassProvider.getBuildInfoFactories(),
               ImmutableList.<DiffAwareness.Factory>of(),
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
index d1dc5fb..22f71b5 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
@@ -19,6 +19,7 @@
 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.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.ServerDirectories;
@@ -68,6 +69,7 @@
   private AnalysisMock analysisMock;
   private ConfiguredRuleClassProvider ruleClassProvider;
   private SkyframeExecutor skyframeExecutor;
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public final void initializeSkyframeExecutor() throws Exception {
@@ -92,6 +94,7 @@
             packageFactoryBuilder.build(ruleClassProvider, fileSystem),
             fileSystem,
             directories,
+            actionKeyContext,
             null, /* workspaceStatusActionFactory */
             ruleClassProvider.getBuildInfoFactories(),
             ImmutableList.<DiffAwareness.Factory>of(),
diff --git a/src/test/java/com/google/devtools/build/lib/rules/android/AndroidDataBindingTest.java b/src/test/java/com/google/devtools/build/lib/rules/android/AndroidDataBindingTest.java
index e8c4115..9fb2cbc 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/android/AndroidDataBindingTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/android/AndroidDataBindingTest.java
@@ -198,7 +198,9 @@
 
     // Regression test for b/63134122
     JavaCompileInfo javaCompileInfo =
-        binCompileAction.getExtraActionInfo().getExtension(JavaCompileInfo.javaCompileInfo);
+        binCompileAction
+            .getExtraActionInfo(actionKeyContext)
+            .getExtension(JavaCompileInfo.javaCompileInfo);
     assertThat(javaCompileInfo.getJavacOptList()).containsAllIn(expectedJavacopts);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcLibraryConfiguredTargetTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcLibraryConfiguredTargetTest.java
index 2ac8d43..c65fe22 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcLibraryConfiguredTargetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcLibraryConfiguredTargetTest.java
@@ -265,7 +265,7 @@
         CppFileTypes.SHARED_LIBRARY));
     CppLinkAction action = (CppLinkAction) getGeneratingAction(sharedObject);
 
-    ExtraActionInfo.Builder builder = action.getExtraActionInfo();
+    ExtraActionInfo.Builder builder = action.getExtraActionInfo(actionKeyContext);
     ExtraActionInfo info = builder.build();
     assertThat(info.getMnemonic()).isEqualTo("CppLink");
 
@@ -299,7 +299,7 @@
         FileType.filter(getFilesToBuild(hello), CppFileTypes.SHARED_LIBRARY).iterator().next();
     CppLinkAction action = (CppLinkAction) getGeneratingAction(sharedObject);
 
-    ExtraActionInfo.Builder builder = action.getExtraActionInfo();
+    ExtraActionInfo.Builder builder = action.getExtraActionInfo(actionKeyContext);
     ExtraActionInfo info = builder.build();
     assertThat(info.getMnemonic()).isEqualTo("CppLink");
 
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
index f3de8b2..a0154f0 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
@@ -344,7 +344,8 @@
 
             return builder.build();
           }
-        });
+        },
+        actionKeyContext);
   }
 
   private enum StaticKeyAttributes {
@@ -395,7 +396,8 @@
             builder.setLibraryIdentifier("foo");
             return builder.build();
           }
-        });
+        },
+        actionKeyContext);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CreateIncSymlinkActionTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CreateIncSymlinkActionTest.java
index 038ed7a..c33115e 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CreateIncSymlinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CreateIncSymlinkActionTest.java
@@ -18,6 +18,7 @@
 import static com.google.devtools.build.lib.actions.util.ActionsTestUtil.NULL_ACTION_OWNER;
 
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
@@ -37,6 +38,8 @@
 @RunWith(JUnit4.class)
 public class CreateIncSymlinkActionTest extends FoundationTestCase {
 
+  private final ActionKeyContext actionKeyContext = new ActionKeyContext();
+
   @Test
   public void testDifferentOrderSameActionKey() throws Exception {
     Root root = Root.asDerivedRoot(rootDirectory, rootDirectory.getRelative("out"));
@@ -53,7 +56,8 @@
     d = new Artifact(PathFragment.create("d"), root);
     CreateIncSymlinkAction action2 = new CreateIncSymlinkAction(NULL_ACTION_OWNER,
         ImmutableMap.of(c, d, a, b), root.getPath());
-    assertThat(action2.computeKey()).isEqualTo(action1.computeKey());
+    assertThat(action2.computeKey(actionKeyContext))
+        .isEqualTo(action1.computeKey(actionKeyContext));
   }
 
   @Test
@@ -68,7 +72,8 @@
     b = new Artifact(PathFragment.create("c"), root);
     CreateIncSymlinkAction action2 = new CreateIncSymlinkAction(NULL_ACTION_OWNER,
         ImmutableMap.of(a, b), root.getPath());
-    assertThat(action2.computeKey()).isNotEqualTo(action1.computeKey());
+    assertThat(action2.computeKey(actionKeyContext))
+        .isNotEqualTo(action1.computeKey(actionKeyContext));
   }
 
   @Test
@@ -83,7 +88,8 @@
     b = new Artifact(PathFragment.create("b"), root);
     CreateIncSymlinkAction action2 = new CreateIncSymlinkAction(NULL_ACTION_OWNER,
         ImmutableMap.of(a, b), root.getPath());
-    assertThat(action2.computeKey()).isNotEqualTo(action1.computeKey());
+    assertThat(action2.computeKey(actionKeyContext))
+        .isNotEqualTo(action1.computeKey(actionKeyContext));
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/LtoBackendActionTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/LtoBackendActionTest.java
index 483c349..7751cb1 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/LtoBackendActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/LtoBackendActionTest.java
@@ -76,8 +76,16 @@
   @Before
   public final void createExecutorAndContext() throws Exception {
     executor = new TestExecutorBuilder(fileSystem, directories, binTools).build();
-    context = new ActionExecutionContext(executor, null, ActionInputPrefetcher.NONE, null,
-        new FileOutErr(), ImmutableMap.<String, String>of(), null);
+    context =
+        new ActionExecutionContext(
+            executor,
+            null,
+            ActionInputPrefetcher.NONE,
+            actionKeyContext,
+            null,
+            new FileOutErr(),
+            ImmutableMap.<String, String>of(),
+            null);
   }
 
   @Test
@@ -203,6 +211,7 @@
             collectingAnalysisEnvironment.registerAction(actions);
             return actions[0];
           }
-        });
+        },
+        actionKeyContext);
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/rules/objc/BazelJ2ObjcLibraryTest.java b/src/test/java/com/google/devtools/build/lib/rules/objc/BazelJ2ObjcLibraryTest.java
index 978b08f..07cab81 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/objc/BazelJ2ObjcLibraryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/objc/BazelJ2ObjcLibraryTest.java
@@ -662,7 +662,13 @@
 
     ActionExecutionContext dummyActionExecutionContext =
         new ActionExecutionContext(
-            null, null, ActionInputPrefetcher.NONE, null, null, ImmutableMap.<String, String>of(),
+            null,
+            null,
+            ActionInputPrefetcher.NONE,
+            actionKeyContext,
+            null,
+            null,
+            ImmutableMap.<String, String>of(),
             DUMMY_ARTIFACT_EXPANDER);
     ByteArrayOutputStream moduleMapStream = new ByteArrayOutputStream();
     ByteArrayOutputStream umbrellaHeaderStream = new ByteArrayOutputStream();
@@ -705,7 +711,13 @@
 
     ActionExecutionContext dummyActionExecutionContext =
         new ActionExecutionContext(
-            null, null, ActionInputPrefetcher.NONE, null, null, ImmutableMap.<String, String>of(),
+            null,
+            null,
+            ActionInputPrefetcher.NONE,
+            actionKeyContext,
+            null,
+            null,
+            ImmutableMap.<String, String>of(),
             DUMMY_ARTIFACT_EXPANDER);
 
     ByteArrayOutputStream moduleMapStream = new ByteArrayOutputStream();
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
index fecdcca..3fdb7a0 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
@@ -23,6 +23,7 @@
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
@@ -83,7 +84,8 @@
                 .put(SkyFunctions.ARTIFACT, new DummyArtifactFunction(artifactValueMap))
                 .put(
                     SkyFunctions.ACTION_TEMPLATE_EXPANSION,
-                    new ActionTemplateExpansionFunction(Suppliers.ofInstance(false)))
+                    new ActionTemplateExpansionFunction(
+                        new ActionKeyContext(), Suppliers.ofInstance(false)))
                 .build(),
             differencer);
     driver = new SequentialBuildDriver(evaluator);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
index 0ab2a6b..4004e85 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
@@ -436,7 +436,8 @@
       differencer.inject(
           ImmutableMap.of(
               OWNER_KEY,
-              new ActionLookupValue(ImmutableList.<ActionAnalysisMetadata>copyOf(actions), false)));
+              new ActionLookupValue(
+                  actionKeyContext, ImmutableList.<ActionAnalysisMetadata>copyOf(actions), false)));
     }
   }
 
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 dd504a5..ff83c4a 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
@@ -17,6 +17,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ServerDirectories;
@@ -59,6 +60,7 @@
   protected MemoizingEvaluator evaluator;
   protected Path root;
   protected Path middlemanPath;
+  protected final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   /**
    * The test action execution function. The Skyframe evaluator's action execution function
@@ -116,7 +118,8 @@
                 .put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction())
                 .put(
                     SkyFunctions.ACTION_TEMPLATE_EXPANSION,
-                    new ActionTemplateExpansionFunction(Suppliers.ofInstance(false)))
+                    new ActionTemplateExpansionFunction(
+                        actionKeyContext, Suppliers.ofInstance(false)))
                 .build(),
             differencer);
     driver = new SequentialBuildDriver(evaluator);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
index db441e7..015b1f3 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
@@ -26,6 +26,7 @@
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Executor;
@@ -207,7 +208,7 @@
     }
 
     @Override
-    protected String computeKey() {
+    protected String computeKey(ActionKeyContext actionKeyContext) {
       return getPrimaryOutput().getExecPathString() + executionCounter.get();
     }
   }
@@ -651,7 +652,7 @@
     }
 
     @Override
-    protected String computeKey() {
+    protected String computeKey(ActionKeyContext actionKeyContext) {
       return new Fingerprint().addInt(42).hexDigestAndReset();
     }
   }
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 0969d5f..a6b2483 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
@@ -34,6 +34,7 @@
 import com.google.devtools.build.lib.actions.ActionExecutionStatusReporter;
 import com.google.devtools.build.lib.actions.ActionInputFileCache;
 import com.google.devtools.build.lib.actions.ActionInputPrefetcher;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLogBufferPathGenerator;
 import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
@@ -121,6 +122,7 @@
   private Set<ActionAnalysisMetadata> actions;
 
   protected AtomicReference<EventBus> eventBusRef = new AtomicReference<>();
+  protected final ActionKeyContext actionKeyContext = new ActionKeyContext();
 
   @Before
   public final void initialize() throws Exception  {
@@ -129,7 +131,7 @@
     ResourceManager.instance().setAvailableResources(ResourceSet.createWithRamCpuIo(100, 1, 1));
     actions = new HashSet<>();
     actionTemplateExpansionFunction =
-        new ActionTemplateExpansionFunction(Suppliers.ofInstance(false));
+        new ActionTemplateExpansionFunction(actionKeyContext, Suppliers.ofInstance(false));
   }
 
   protected void clearActions() {
@@ -180,7 +182,8 @@
     ActionExecutionStatusReporter statusReporter =
         ActionExecutionStatusReporter.create(new StoredEventHandler());
     final SkyframeActionExecutor skyframeActionExecutor =
-        new SkyframeActionExecutor(eventBusRef, new AtomicReference<>(statusReporter));
+        new SkyframeActionExecutor(
+            actionKeyContext, eventBusRef, new AtomicReference<>(statusReporter));
 
     Path actionOutputBase = scratch.dir("/usr/local/google/_blaze_jrluser/FAKEMD5/action_out/");
     skyframeActionExecutor.setActionLogBufferPathGenerator(
@@ -238,7 +241,8 @@
         if (evaluator.getExistingValue(OWNER_KEY) == null) {
           differencer.inject(
               ImmutableMap.of(
-                  OWNER_KEY, new ActionLookupValue(ImmutableList.copyOf(actions), false)));
+                  OWNER_KEY,
+                  new ActionLookupValue(actionKeyContext, ImmutableList.copyOf(actions), false)));
         }
       }
 
@@ -263,7 +267,8 @@
             executor,
             keepGoing,
             /*explain=*/ false,
-            new ActionCacheChecker(actionCache, null, ALWAYS_EXECUTE_FILTER, null),
+            new ActionCacheChecker(
+                actionCache, null, actionKeyContext, ALWAYS_EXECUTE_FILTER, null),
             null);
         skyframeActionExecutor.setActionExecutionProgressReportingObjects(
             EMPTY_PROGRESS_SUPPLIER, EMPTY_COMPLETION_RECEIVER);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
index fac36eb..6c15a1f 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
@@ -34,6 +34,7 @@
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputFileCache;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
@@ -742,10 +743,12 @@
     Action noGenerateOutputAction = new DummyAction(
         ImmutableList.<Artifact>of(treeFileArtifactB), expectedOutputTreeFileArtifact2);
 
-    actionTemplateExpansionFunction = new DummyActionTemplateExpansionFunction(
-        ImmutableMultimap.<ActionTemplate<?>, Action>of(
-            actionTemplate, generateOutputAction,
-            actionTemplate, noGenerateOutputAction));
+    actionTemplateExpansionFunction =
+        new DummyActionTemplateExpansionFunction(
+            actionKeyContext,
+            ImmutableMultimap.<ActionTemplate<?>, Action>of(
+                actionTemplate, generateOutputAction,
+                actionTemplate, noGenerateOutputAction));
 
     buildArtifact(artifact2);
   }
@@ -782,10 +785,12 @@
         ImmutableList.<Artifact>of(treeFileArtifactB),
         ImmutableList.<Artifact>of(expectedOutputTreeFileArtifact2));
 
-    actionTemplateExpansionFunction = new DummyActionTemplateExpansionFunction(
-        ImmutableMultimap.<ActionTemplate<?>, Action>of(
-            actionTemplate, generateOutputAction,
-            actionTemplate, noGenerateOutputAction));
+    actionTemplateExpansionFunction =
+        new DummyActionTemplateExpansionFunction(
+            actionKeyContext,
+            ImmutableMultimap.<ActionTemplate<?>, Action>of(
+                actionTemplate, generateOutputAction,
+                actionTemplate, noGenerateOutputAction));
 
     try {
       buildArtifact(artifact2);
@@ -826,11 +831,13 @@
     Action throwingAction = new ThrowingDummyAction(
         ImmutableList.<Artifact>of(treeFileArtifactB),
         ImmutableList.<Artifact>of(expectedOutputTreeFileArtifact2));
-    
-    actionTemplateExpansionFunction = new DummyActionTemplateExpansionFunction(
-        ImmutableMultimap.<ActionTemplate<?>, Action>of(
-            actionTemplate, generateOutputAction,
-            actionTemplate, throwingAction));
+
+    actionTemplateExpansionFunction =
+        new DummyActionTemplateExpansionFunction(
+            actionKeyContext,
+            ImmutableMultimap.<ActionTemplate<?>, Action>of(
+                actionTemplate, generateOutputAction,
+                actionTemplate, throwingAction));
 
     try {
       buildArtifact(artifact2);
@@ -870,11 +877,13 @@
     Action anotherThrowingAction = new ThrowingDummyAction(
         ImmutableList.<Artifact>of(treeFileArtifactB),
         ImmutableList.<Artifact>of(expectedOutputTreeFileArtifact2));
-    
-    actionTemplateExpansionFunction = new DummyActionTemplateExpansionFunction(
-        ImmutableMultimap.<ActionTemplate<?>, Action>of(
-            actionTemplate, throwingAction,
-            actionTemplate, anotherThrowingAction));
+
+    actionTemplateExpansionFunction =
+        new DummyActionTemplateExpansionFunction(
+            actionKeyContext,
+            ImmutableMultimap.<ActionTemplate<?>, Action>of(
+                actionTemplate, throwingAction,
+                actionTemplate, anotherThrowingAction));
 
     try {
       buildArtifact(artifact2);
@@ -1217,10 +1226,13 @@
 
   /** A dummy action template expansion function that just returns the injected actions */
   private static class DummyActionTemplateExpansionFunction implements SkyFunction {
+    private final ActionKeyContext actionKeyContext;
     private final Multimap<ActionTemplate<?>, Action> actionTemplateToActionMap;
 
     DummyActionTemplateExpansionFunction(
+        ActionKeyContext actionKeyContext,
         Multimap<ActionTemplate<?>, Action> actionTemplateToActionMap) {
+      this.actionKeyContext = actionKeyContext;
       this.actionTemplateToActionMap = actionTemplateToActionMap;
     }
 
@@ -1229,7 +1241,9 @@
       ActionTemplateExpansionKey key = (ActionTemplateExpansionKey) skyKey.argument();
       ActionTemplate<?> actionTemplate = key.getActionTemplate();
       return new ActionTemplateExpansionValue(
-          Preconditions.checkNotNull(actionTemplateToActionMap.get(actionTemplate)), false);
+          actionKeyContext,
+          Preconditions.checkNotNull(actionTemplateToActionMap.get(actionTemplate)),
+          false);
     }
 
     @Override
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
index 54b4e48..3e156be 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
@@ -228,7 +228,8 @@
       differencer.inject(
           ImmutableMap.of(
               OWNER_KEY,
-              new ActionLookupValue(ImmutableList.<ActionAnalysisMetadata>copyOf(actions), false)));
+              new ActionLookupValue(
+                  actionKeyContext, ImmutableList.<ActionAnalysisMetadata>copyOf(actions), false)));
     }
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/standalone/StandaloneSpawnStrategyTest.java b/src/test/java/com/google/devtools/build/lib/standalone/StandaloneSpawnStrategyTest.java
index d2497ff..5dc7d9b 100644
--- a/src/test/java/com/google/devtools/build/lib/standalone/StandaloneSpawnStrategyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/standalone/StandaloneSpawnStrategyTest.java
@@ -24,6 +24,7 @@
 import com.google.devtools.build.lib.actions.ActionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionInputPrefetcher;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
 import com.google.devtools.build.lib.actions.ExecException;
@@ -183,6 +184,7 @@
         executor,
         new SingleBuildFileCache(execRoot.getPathString(), execRoot.getFileSystem()),
         ActionInputPrefetcher.NONE,
+        new ActionKeyContext(),
         null,
         outErr,
         ImmutableMap.<String, String>of(),