diff --git a/src/main/java/com/google/devtools/build/lib/actions/AbstractAction.java b/src/main/java/com/google/devtools/build/lib/actions/AbstractAction.java
index d1d805f..04f7458 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/AbstractAction.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/AbstractAction.java
@@ -295,16 +295,17 @@
 
   /**
    * See the javadoc for {@link com.google.devtools.build.lib.actions.Action} and {@link
-   * com.google.devtools.build.lib.actions.ActionExecutionMetadata#getKey()} for the contract for
-   * {@link #computeKey()}.
+   * ActionExecutionMetadata#getKey(ActionKeyContext)} for the contract for {@link
+   * #computeKey(ActionKeyContext)}.
    */
-  protected abstract String computeKey() throws CommandLineExpansionException;
+  protected abstract String computeKey(ActionKeyContext actionKeyContext)
+      throws CommandLineExpansionException;
 
   @Override
-  public final synchronized String getKey() {
+  public final synchronized String getKey(ActionKeyContext actionKeyContext) {
     if (cachedKey == null) {
       try {
-        cachedKey = computeKey();
+        cachedKey = computeKey(actionKeyContext);
       } catch (CommandLineExpansionException e) {
         cachedKey = KEY_ERROR;
       }
@@ -481,12 +482,13 @@
   }
 
   @Override
-  public ExtraActionInfo.Builder getExtraActionInfo() throws CommandLineExpansionException {
+  public ExtraActionInfo.Builder getExtraActionInfo(ActionKeyContext actionKeyContext)
+      throws CommandLineExpansionException {
     ActionOwner owner = getOwner();
     ExtraActionInfo.Builder result =
         ExtraActionInfo.newBuilder()
             .setOwner(owner.getLabel().toString())
-            .setId(getKey())
+            .setId(getKey(actionKeyContext))
             .setMnemonic(getMnemonic());
     Iterable<AspectDescriptor> aspectDescriptors = owner.getAspectDescriptors();
     AspectDescriptor lastAspect = null;
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Action.java b/src/main/java/com/google/devtools/build/lib/actions/Action.java
index e1c1b35..217ce5d 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Action.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Action.java
@@ -192,5 +192,6 @@
    * <p>As this method is called from the ExtraAction, make sure it is ok to call this method from a
    * different thread than the one this action is executed on.
    */
-  ExtraActionInfo.Builder getExtraActionInfo() throws CommandLineExpansionException;
+  ExtraActionInfo.Builder getExtraActionInfo(ActionKeyContext actionKeyContext)
+      throws CommandLineExpansionException;
 }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
index 8a49c9c..8e4dc88 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
@@ -74,6 +74,7 @@
   };
 
   private final ActionCache actionCache;
+  private final ActionKeyContext actionKeyContext;
   private final Predicate<? super Action> executionFilter;
   private final ArtifactResolver artifactResolver;
   private final CacheConfig cacheConfig;
@@ -103,10 +104,12 @@
   public ActionCacheChecker(
       ActionCache actionCache,
       ArtifactResolver artifactResolver,
+      ActionKeyContext actionKeyContext,
       Predicate<? super Action> executionFilter,
       @Nullable CacheConfig cacheConfig) {
     this.actionCache = actionCache;
     this.executionFilter = executionFilter;
+    this.actionKeyContext = actionKeyContext;
     this.artifactResolver = artifactResolver;
     this.cacheConfig =
         cacheConfig != null
@@ -303,7 +306,7 @@
       reportChanged(handler, action);
       actionCache.accountMiss(MissReason.DIFFERENT_FILES);
       return true;
-    } else if (!entry.getActionKey().equals(action.getKey())) {
+    } else if (!entry.getActionKey().equals(action.getKey(actionKeyContext))) {
       reportCommand(handler, action);
       actionCache.accountMiss(MissReason.DIFFERENT_ACTION_KEY);
       return true;
@@ -356,7 +359,8 @@
     }
     Map<String, String> usedClientEnv = computeUsedClientEnv(action, clientEnv);
     ActionCache.Entry entry =
-        new ActionCache.Entry(action.getKey(), usedClientEnv, action.discoversInputs());
+        new ActionCache.Entry(
+            action.getKey(actionKeyContext), usedClientEnv, action.discoversInputs());
     for (Artifact output : action.getOutputs()) {
       // Remove old records from the cache if they used different key.
       String execPath = output.getExecPathString();
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContext.java b/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContext.java
index fc8a6bf..f356559 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContext.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContext.java
@@ -43,6 +43,7 @@
   private final Executor executor;
   private final ActionInputFileCache actionInputFileCache;
   private final ActionInputPrefetcher actionInputPrefetcher;
+  private final ActionKeyContext actionKeyContext;
   private final MetadataHandler metadataHandler;
   private final FileOutErr fileOutErr;
   private final ImmutableMap<String, String> clientEnv;
@@ -54,6 +55,7 @@
       Executor executor,
       ActionInputFileCache actionInputFileCache,
       ActionInputPrefetcher actionInputPrefetcher,
+      ActionKeyContext actionKeyContext,
       MetadataHandler metadataHandler,
       FileOutErr fileOutErr,
       Map<String, String> clientEnv,
@@ -61,6 +63,7 @@
       @Nullable SkyFunction.Environment env) {
     this.actionInputFileCache = actionInputFileCache;
     this.actionInputPrefetcher = actionInputPrefetcher;
+    this.actionKeyContext = actionKeyContext;
     this.metadataHandler = metadataHandler;
     this.fileOutErr = fileOutErr;
     this.clientEnv = ImmutableMap.copyOf(clientEnv);
@@ -73,6 +76,7 @@
       Executor executor,
       ActionInputFileCache actionInputFileCache,
       ActionInputPrefetcher actionInputPrefetcher,
+      ActionKeyContext actionKeyContext,
       MetadataHandler metadataHandler,
       FileOutErr fileOutErr,
       Map<String, String> clientEnv,
@@ -81,6 +85,7 @@
         executor,
         actionInputFileCache,
         actionInputPrefetcher,
+        actionKeyContext,
         metadataHandler,
         fileOutErr,
         clientEnv,
@@ -92,6 +97,7 @@
       Executor executor,
       ActionInputFileCache actionInputFileCache,
       ActionInputPrefetcher actionInputPrefetcher,
+      ActionKeyContext actionKeyContext,
       MetadataHandler metadataHandler,
       FileOutErr fileOutErr,
       Map<String, String> clientEnv,
@@ -100,6 +106,7 @@
         executor,
         actionInputFileCache,
         actionInputPrefetcher,
+        actionKeyContext,
         metadataHandler,
         fileOutErr,
         clientEnv,
@@ -216,6 +223,10 @@
     return Preconditions.checkNotNull(env);
   }
 
+  public ActionKeyContext getActionKeyContext() {
+    return actionKeyContext;
+  }
+
   @Override
   public void close() throws IOException {
     fileOutErr.close();
@@ -230,6 +241,7 @@
         executor,
         actionInputFileCache,
         actionInputPrefetcher,
+        actionKeyContext,
         metadataHandler,
         fileOutErr,
         clientEnv,
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionMetadata.java b/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionMetadata.java
index 7f4b569..ec94b6c 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionMetadata.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionMetadata.java
@@ -59,35 +59,36 @@
    * <p>Examples of changes that should affect the key are:
    *
    * <ul>
-   * <li>Changes to the BUILD file that materially affect the rule which gave rise to this Action.
-   * <li>Changes to the command-line options, environment, or other global configuration resources
-   *     which affect the behaviour of this kind of Action (other than changes to the names of the
-   *     input/output files, which are handled externally).
-   * <li>An upgrade to the build tools which changes the program logic of this kind of Action
-   *     (typically this is achieved by incorporating a UUID into the key, which is changed each
-   *     time the program logic of this action changes).
+   *   <li>Changes to the BUILD file that materially affect the rule which gave rise to this Action.
+   *   <li>Changes to the command-line options, environment, or other global configuration resources
+   *       which affect the behaviour of this kind of Action (other than changes to the names of the
+   *       input/output files, which are handled externally).
+   *   <li>An upgrade to the build tools which changes the program logic of this kind of Action
+   *       (typically this is achieved by incorporating a UUID into the key, which is changed each
+   *       time the program logic of this action changes).
    * </ul>
    */
-  String getKey();
+  String getKey(ActionKeyContext actionKeyContext);
 
   /**
-   * Returns a human-readable description of the inputs to {@link #getKey()}.
-   * Used in the output from '--explain', and in error messages for
-   * '--check_up_to_date' and '--check_tests_up_to_date'.
-   * May return null, meaning no extra information is available.
+   * Returns a human-readable description of the inputs to {@link #getKey(ActionKeyContext)}. Used
+   * in the output from '--explain', and in error messages for '--check_up_to_date' and
+   * '--check_tests_up_to_date'. May return null, meaning no extra information is available.
    *
    * <p>If the return value is non-null, for consistency it should be a multiline message of the
    * form:
+   *
    * <pre>
    *   <var>Summary</var>
    *     <var>Fieldname</var>: <var>value</var>
    *     <var>Fieldname</var>: <var>value</var>
    *     ...
    * </pre>
+   *
    * where each line after the first one is intended two spaces, and where any fields that might
    * contain newlines or other funny characters are escaped using {@link
-   * com.google.devtools.build.lib.shell.ShellUtils#shellEscape}.
-   * For example:
+   * com.google.devtools.build.lib.shell.ShellUtils#shellEscape}. For example:
+   *
    * <pre>
    *   Compiling foo.cc
    *     Command: /usr/bin/gcc
@@ -97,7 +98,8 @@
    *     Argument: foo.o
    * </pre>
    */
-  @Nullable String describeKey();
+  @Nullable
+  String describeKey();
 
   /**
    * Get the {@link RunfilesSupplier} providing runfiles needed by this action.
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionKeyContext.java b/src/main/java/com/google/devtools/build/lib/actions/ActionKeyContext.java
new file mode 100644
index 0000000..6ba29a7
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionKeyContext.java
@@ -0,0 +1,41 @@
+// 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.actions;
+
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetFingerprintCache;
+import com.google.devtools.build.lib.util.Fingerprint;
+
+/** Contains state that aids in action key computation via {@link AbstractAction#computeKey}. */
+public class ActionKeyContext {
+  private static final class ArtifactNestedSetFingerprintCache
+      extends NestedSetFingerprintCache<Artifact> {
+    @Override
+    protected void addItemFingerprint(Fingerprint fingerprint, Artifact item) {
+      fingerprint.addPath(item.getExecPath());
+    }
+  }
+
+  private final ArtifactNestedSetFingerprintCache artifactNestedSetFingerprintCache =
+      new ArtifactNestedSetFingerprintCache();
+
+  public void addArtifactsToFingerprint(Fingerprint fingerprint, NestedSet<Artifact> artifacts) {
+    artifactNestedSetFingerprintCache.addNestedSetToFingerprint(fingerprint, artifacts);
+  }
+
+  public void clear() {
+    artifactNestedSetFingerprintCache.clear();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java
index bf6e3a0..ffe650a 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java
@@ -42,9 +42,9 @@
   private final ImmutableMap<Artifact, Integer> generatingActionIndex;
 
   private static Actions.GeneratingActions filterSharedActionsAndThrowRuntimeIfConflict(
-      List<ActionAnalysisMetadata> actions) {
+      ActionKeyContext actionKeyContext, List<ActionAnalysisMetadata> actions) {
     try {
-      return Actions.filterSharedActionsAndThrowActionConflict(actions);
+      return Actions.filterSharedActionsAndThrowActionConflict(actionKeyContext, actions);
     } catch (ActionConflictException e) {
       // Programming bug.
       throw new IllegalStateException(e);
@@ -53,12 +53,19 @@
 
   @VisibleForTesting
   public ActionLookupValue(
-      List<ActionAnalysisMetadata> actions, boolean removeActionsAfterEvaluation) {
-    this(filterSharedActionsAndThrowRuntimeIfConflict(actions), removeActionsAfterEvaluation);
+      ActionKeyContext actionKeyContext,
+      List<ActionAnalysisMetadata> actions,
+      boolean removeActionsAfterEvaluation) {
+    this(
+        filterSharedActionsAndThrowRuntimeIfConflict(actionKeyContext, actions),
+        removeActionsAfterEvaluation);
   }
 
-  protected ActionLookupValue(ActionAnalysisMetadata action, boolean removeActionAfterEvaluation) {
-    this(ImmutableList.of(action), removeActionAfterEvaluation);
+  protected ActionLookupValue(
+      ActionKeyContext actionKeyContext,
+      ActionAnalysisMetadata action,
+      boolean removeActionAfterEvaluation) {
+    this(actionKeyContext, ImmutableList.of(action), removeActionAfterEvaluation);
   }
 
   protected ActionLookupValue(
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Actions.java b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
index 4acd7fe..9143826 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Actions.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
@@ -54,7 +54,8 @@
    * <p>This method implements an equivalence relationship across actions, based on the action
    * class, the key, and the list of inputs and outputs.
    */
-  public static boolean canBeShared(ActionAnalysisMetadata a, ActionAnalysisMetadata b) {
+  public static boolean canBeShared(
+      ActionKeyContext actionKeyContext, ActionAnalysisMetadata a, ActionAnalysisMetadata b) {
     if (!a.getMnemonic().equals(b.getMnemonic())) {
       return false;
     }
@@ -66,7 +67,7 @@
 
     Action actionA = (Action) a;
     Action actionB = (Action) b;
-    if (!actionA.getKey().equals(actionB.getKey())) {
+    if (!actionA.getKey(actionKeyContext).equals(actionB.getKey(actionKeyContext))) {
       return false;
     }
     // Don't bother to check input and output counts first; the expected result for these tests is
@@ -89,10 +90,11 @@
    *     of indirection.
    * @throws ActionConflictException iff there are two actions generate the same output
    */
-  public static GeneratingActions findAndThrowActionConflict(List<ActionAnalysisMetadata> actions)
+  public static GeneratingActions findAndThrowActionConflict(
+      ActionKeyContext actionKeyContext, List<ActionAnalysisMetadata> actions)
       throws ActionConflictException {
     return Actions.maybeFilterSharedActionsAndThrowIfConflict(
-        actions, /*allowSharedAction=*/ false);
+        actionKeyContext, actions, /*allowSharedAction=*/ false);
   }
 
   /**
@@ -106,13 +108,16 @@
    *     output
    */
   public static GeneratingActions filterSharedActionsAndThrowActionConflict(
-      List<ActionAnalysisMetadata> actions) throws ActionConflictException {
+      ActionKeyContext actionKeyContext, List<ActionAnalysisMetadata> actions)
+      throws ActionConflictException {
     return Actions.maybeFilterSharedActionsAndThrowIfConflict(
-        actions, /*allowSharedAction=*/ true);
+        actionKeyContext, actions, /*allowSharedAction=*/ true);
   }
 
   private static GeneratingActions maybeFilterSharedActionsAndThrowIfConflict(
-      List<ActionAnalysisMetadata> actions, boolean allowSharedAction)
+      ActionKeyContext actionKeyContext,
+      List<ActionAnalysisMetadata> actions,
+      boolean allowSharedAction)
       throws ActionConflictException {
     Map<Artifact, Integer> generatingActions = new HashMap<>();
     int actionIndex = 0;
@@ -120,8 +125,10 @@
       for (Artifact artifact : action.getOutputs()) {
         Integer previousIndex = generatingActions.put(artifact, actionIndex);
         if (previousIndex != null && previousIndex != actionIndex) {
-          if (!allowSharedAction || !Actions.canBeShared(actions.get(previousIndex), action)) {
-            throw new ActionConflictException(artifact, actions.get(previousIndex), action);
+          if (!allowSharedAction
+              || !Actions.canBeShared(actionKeyContext, actions.get(previousIndex), action)) {
+            throw new ActionConflictException(
+                actionKeyContext, artifact, actions.get(previousIndex), action);
           }
         }
       }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/BUILD b/src/main/java/com/google/devtools/build/lib/actions/BUILD
index f481e5f..9b8d8bc 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/actions/BUILD
@@ -28,6 +28,7 @@
         "//src/main/java/com/google/devtools/build/lib/causes",
         "//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/concurrent",
         "//src/main/java/com/google/devtools/build/lib/profiler",
         "//src/main/java/com/google/devtools/build/lib/shell",
diff --git a/src/main/java/com/google/devtools/build/lib/actions/FailAction.java b/src/main/java/com/google/devtools/build/lib/actions/FailAction.java
index 7f21740..86c22e0 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FailAction.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FailAction.java
@@ -45,7 +45,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     return GUID;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/actions/MapBasedActionGraph.java b/src/main/java/com/google/devtools/build/lib/actions/MapBasedActionGraph.java
index 9b27881..f35f963 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/MapBasedActionGraph.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/MapBasedActionGraph.java
@@ -23,9 +23,14 @@
  */
 @ThreadSafe
 public final class MapBasedActionGraph implements MutableActionGraph {
+  private final ActionKeyContext actionKeyContext;
   private final ConcurrentMultimapWithHeadElement<Artifact, ActionAnalysisMetadata>
       generatingActionMap = new ConcurrentMultimapWithHeadElement<>();
 
+  public MapBasedActionGraph(ActionKeyContext actionKeyContext) {
+    this.actionKeyContext = actionKeyContext;
+  }
+
   @Override
   @Nullable
   public ActionAnalysisMetadata getGeneratingAction(Artifact artifact) {
@@ -36,10 +41,11 @@
   public void registerAction(ActionAnalysisMetadata action) throws ActionConflictException {
     for (Artifact artifact : action.getOutputs()) {
       ActionAnalysisMetadata previousAction = generatingActionMap.putAndGet(artifact, action);
-      if (previousAction != null && previousAction != action
-          && !Actions.canBeShared(action, previousAction)) {
+      if (previousAction != null
+          && previousAction != action
+          && !Actions.canBeShared(actionKeyContext, action, previousAction)) {
         generatingActionMap.remove(artifact, action);
-        throw new ActionConflictException(artifact, previousAction, action);
+        throw new ActionConflictException(actionKeyContext, artifact, previousAction, action);
       }
     }
   }
@@ -49,9 +55,13 @@
     for (Artifact artifact : action.getOutputs()) {
       generatingActionMap.remove(artifact, action);
       ActionAnalysisMetadata otherAction = generatingActionMap.get(artifact);
-      Preconditions.checkState(otherAction == null
-          || (otherAction != action && Actions.canBeShared(action, otherAction)),
-          "%s %s", action, otherAction);
+      Preconditions.checkState(
+          otherAction == null
+              || (otherAction != action
+                  && Actions.canBeShared(actionKeyContext, action, otherAction)),
+          "%s %s",
+          action,
+          otherAction);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/actions/MiddlemanAction.java b/src/main/java/com/google/devtools/build/lib/actions/MiddlemanAction.java
index f0c5972..787f052 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/MiddlemanAction.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/MiddlemanAction.java
@@ -56,7 +56,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     // TODO(bazel-team): Need to take middlemanType into account here.
     // Only the set of inputs matters, and the dependency checker is
     // responsible for considering those.
diff --git a/src/main/java/com/google/devtools/build/lib/actions/MutableActionGraph.java b/src/main/java/com/google/devtools/build/lib/actions/MutableActionGraph.java
index 1b1955a..24a74ad 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/MutableActionGraph.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/MutableActionGraph.java
@@ -61,15 +61,19 @@
    * about the artifact for which the conflict is found, and data about the two conflicting actions
    * and their owners.
    */
-  public static final class ActionConflictException extends Exception {
+  final class ActionConflictException extends Exception {
 
+    private final ActionKeyContext actionKeyContext;
     private final Artifact artifact;
     private final ActionAnalysisMetadata previousAction;
     private final ActionAnalysisMetadata attemptedAction;
     
     private static final int MAX_DIFF_ARTIFACTS_TO_REPORT = 5;
 
-    public ActionConflictException(Artifact artifact, ActionAnalysisMetadata previousAction,
+    public ActionConflictException(
+        ActionKeyContext actionKeyContext,
+        Artifact artifact,
+        ActionAnalysisMetadata previousAction,
         ActionAnalysisMetadata attemptedAction) {
       super(
           String.format(
@@ -77,6 +81,7 @@
               artifact.prettyPrint(),
               previousAction.prettyPrint(),
               attemptedAction.prettyPrint()));
+      this.actionKeyContext = actionKeyContext;
       this.artifact = artifact;
       this.previousAction = previousAction;
       this.attemptedAction = attemptedAction;
@@ -91,7 +96,7 @@
           "file '"
               + artifact.prettyPrint()
               + "' is generated by these conflicting actions:\n"
-              + suffix(attemptedAction, previousAction);
+              + suffix(actionKeyContext, attemptedAction, previousAction);
       eventListener.handle(Event.error(msg));
     }
 
@@ -143,14 +148,13 @@
       }
     }
 
-    private static String getKey(ActionAnalysisMetadata action) {
-      return action instanceof Action
-          ? ((Action) action).getKey()
-          : null;
+    private static String getKey(ActionKeyContext actionKeyContext, ActionAnalysisMetadata action) {
+      return action instanceof Action ? ((Action) action).getKey(actionKeyContext) : null;
     }
 
     // See also Actions.canBeShared()
-    private static String suffix(ActionAnalysisMetadata a, ActionAnalysisMetadata b) {
+    private static String suffix(
+        ActionKeyContext actionKeyContext, ActionAnalysisMetadata a, ActionAnalysisMetadata b) {
       // Note: the error message reveals to users the names of intermediate files that are not
       // documented in the BUILD language.  This error-reporting logic is rather elaborate but it
       // does help to diagnose some tricky situations.
@@ -167,7 +171,7 @@
       addStringDetail(sb, "Configuration", aNull ? null : aOwner.getConfigurationChecksum(),
           bNull ? null : bOwner.getConfigurationChecksum());
       addStringDetail(sb, "Mnemonic", a.getMnemonic(), b.getMnemonic());
-      addStringDetail(sb, "Action key", getKey(a), getKey(b));
+      addStringDetail(sb, "Action key", getKey(actionKeyContext, a), getKey(actionKeyContext, b));
 
       if ((a instanceof ActionExecutionMetadata) && (b instanceof ActionExecutionMetadata)) {
         addStringDetail(
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java
index a121e55..2d7466d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionRegistry;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.MiddlemanFactory;
@@ -151,4 +152,6 @@
    * called after the ConfiguredTarget is created.
    */
   ImmutableSet<Artifact> getOrphanArtifacts();
+
+  ActionKeyContext getActionKeyContext();
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index a846022..dca8074 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -1099,10 +1099,15 @@
           InconsistentAspectOrderException, ToolchainContextException {
     BuildConfiguration targetConfig = target.getConfiguration();
     CachingAnalysisEnvironment env =
-        new CachingAnalysisEnvironment(getArtifactFactory(),
+        new CachingAnalysisEnvironment(
+            getArtifactFactory(),
+            skyframeExecutor.getActionKeyContext(),
             new ConfiguredTargetKey(target.getLabel(), targetConfig),
-            /*isSystemEnv=*/false, targetConfig.extendedSanityChecks(), eventHandler,
-            /*env=*/null, targetConfig.isActionsEnabled());
+            /*isSystemEnv=*/ false,
+            targetConfig.extendedSanityChecks(),
+            eventHandler,
+            /*env=*/ null,
+            targetConfig.isActionsEnabled());
     return getRuleContextForTesting(eventHandler, target, env, configurations);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java b/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java
index 3d3dfb7..7d17950 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -77,6 +78,8 @@
    */
   private final boolean allowRegisteringActions;
 
+  private final ActionKeyContext actionKeyContext;
+
   private boolean enabled = true;
   private MiddlemanFactory middlemanFactory;
   private ExtendedEventHandler errorEventListener;
@@ -91,6 +94,7 @@
 
   public CachingAnalysisEnvironment(
       ArtifactFactory artifactFactory,
+      ActionKeyContext actionKeyContext,
       ArtifactOwner owner,
       boolean isSystemEnv,
       boolean extendedSanityChecks,
@@ -98,6 +102,7 @@
       SkyFunction.Environment env,
       boolean allowRegisteringActions) {
     this.artifactFactory = artifactFactory;
+    this.actionKeyContext = actionKeyContext;
     this.owner = Preconditions.checkNotNull(owner);
     this.isSystemEnv = isSystemEnv;
     this.extendedSanityChecks = extendedSanityChecks;
@@ -191,6 +196,11 @@
   }
 
   @Override
+  public ActionKeyContext getActionKeyContext() {
+    return actionKeyContext;
+  }
+
+  @Override
   public boolean hasErrors() {
     // The system analysis environment never has errors.
     if (isSystemEnv) {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java b/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java
index 4c85dc0..3f704d2 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java
@@ -17,6 +17,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.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -63,7 +64,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     return new Fingerprint().addUUID(uuid).addBytes(getInfo().toByteArray()).hexDigestAndReset();
   }
 
@@ -72,9 +73,9 @@
   }
 
   @Override
-  public ExtraActionInfo.Builder getExtraActionInfo() {
+  public ExtraActionInfo.Builder getExtraActionInfo(ActionKeyContext actionKeyContext) {
     try {
-      return super.getExtraActionInfo().setExtension(infoExtension, getInfo());
+      return super.getExtraActionInfo(actionKeyContext).setExtension(infoExtension, getInfo());
     } catch (CommandLineExpansionException e) {
       throw new AssertionError("PsedoAction command line expansion cannot fail");
     }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
index 0fe1ba7..3d9d547 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
@@ -18,6 +18,7 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.analysis.actions.AbstractFileWriteAction;
@@ -192,7 +193,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addBoolean(runfiles.getLegacyExternalRunfiles());
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java b/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java
index e6ea990..85fd697 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java
@@ -17,6 +17,7 @@
 import com.google.common.base.Objects;
 import com.google.common.base.Verify;
 import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -71,6 +72,10 @@
     return env;
   }
 
+  public ActionKeyContext getActionKeyContext() {
+    return env.getActionKeyContext();
+  }
+
   public Target getTarget() {
     return target;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/BinaryFileWriteAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/BinaryFileWriteAction.java
index a11ce1f..0df7abe 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/BinaryFileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/BinaryFileWriteAction.java
@@ -19,6 +19,7 @@
 import com.google.common.io.ByteSource;
 import com.google.common.io.ByteStreams;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.concurrent.ThreadSafety.Immutable;
@@ -70,7 +71,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addString(String.valueOf(makeExecutable));
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java
index c7aa4cb..8fcb74a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java
@@ -18,6 +18,7 @@
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.analysis.RuleContext;
@@ -224,12 +225,9 @@
     };
   }
 
-  /**
-   * Computes the Action key for this action by computing the fingerprint for
-   * the file contents.
-   */
+  /** Computes the Action key for this action by computing the fingerprint for the file contents. */
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addString(String.valueOf(makeExecutable));
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/LauncherFileWriteAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/LauncherFileWriteAction.java
index ccb045f..d674852 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/LauncherFileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/LauncherFileWriteAction.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.io.ByteStreams;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.analysis.RuleContext;
@@ -86,7 +87,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     try {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParameterFileWriteAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParameterFileWriteAction.java
index 82fef53..df2b889 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParameterFileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParameterFileWriteAction.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.Artifact.ArtifactExpander;
@@ -164,7 +165,8 @@
   }
 
   @Override
-  protected String computeKey() throws CommandLineExpansionException {
+  protected String computeKey(ActionKeyContext actionKeyContext)
+      throws CommandLineExpansionException {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addString(String.valueOf(makeExecutable));
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/PopulateTreeArtifactAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/PopulateTreeArtifactAction.java
index 3c73955..5ba555f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/PopulateTreeArtifactAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/PopulateTreeArtifactAction.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.actions.ActionExecutionMetadata;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
+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.Actions;
@@ -209,7 +210,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addString(getMnemonic());
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
index 0c91168..74bd33a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
@@ -30,6 +30,7 @@
 import com.google.devtools.build.lib.actions.ActionExecutionException;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
+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;
@@ -332,7 +333,8 @@
   }
 
   @Override
-  protected String computeKey() throws CommandLineExpansionException {
+  protected String computeKey(ActionKeyContext actionKeyContext)
+      throws CommandLineExpansionException {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addStrings(argv.arguments());
@@ -397,8 +399,9 @@
   }
 
   @Override
-  public ExtraActionInfo.Builder getExtraActionInfo() throws CommandLineExpansionException {
-    ExtraActionInfo.Builder builder = super.getExtraActionInfo();
+  public ExtraActionInfo.Builder getExtraActionInfo(ActionKeyContext actionKeyContext)
+      throws CommandLineExpansionException {
+    ExtraActionInfo.Builder builder = super.getExtraActionInfo(actionKeyContext);
     if (extraActionInfoSupplier == null) {
       SpawnInfo spawnInfo = getExtraActionSpawnInfo();
       return builder
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkAction.java
index 819c0c1..645cd6f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkAction.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.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -128,7 +129,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     // We don't normally need to add inputs to the key. In this case, however, the inputPath can be
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkTreeAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkTreeAction.java
index d066586..d0600db 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkTreeAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/SymlinkTreeAction.java
@@ -19,6 +19,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.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -109,7 +110,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addInt(filesetTree ? 1 : 0);
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionAction.java
index 4be2446..6441291 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionAction.java
@@ -21,6 +21,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.cmdline.Label;
@@ -438,7 +439,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addString(String.valueOf(makeExecutable));
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/extra/ExtraActionInfoFileWriteAction.java b/src/main/java/com/google/devtools/build/lib/analysis/extra/ExtraActionInfoFileWriteAction.java
index c82cf95..5267e7d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/extra/ExtraActionInfoFileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/extra/ExtraActionInfoFileWriteAction.java
@@ -17,6 +17,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.CommandLineExpansionException;
@@ -50,18 +51,20 @@
   public DeterministicWriter newDeterministicWriter(ActionExecutionContext ctx)
       throws IOException, InterruptedException, ExecException {
     try {
-      return new ProtoDeterministicWriter(shadowedAction.getExtraActionInfo().build());
+      return new ProtoDeterministicWriter(
+          shadowedAction.getExtraActionInfo(ctx.getActionKeyContext()).build());
     } catch (CommandLineExpansionException e) {
       throw new UserExecException(e);
     }
   }
 
   @Override
-  protected String computeKey() throws CommandLineExpansionException {
+  protected String computeKey(ActionKeyContext actionKeyContext)
+      throws CommandLineExpansionException {
     Fingerprint f = new Fingerprint();
     f.addString(UUID);
-    f.addString(shadowedAction.getKey());
-    f.addBytes(shadowedAction.getExtraActionInfo().build().toByteArray());
+    f.addString(shadowedAction.getKey(actionKeyContext));
+    f.addBytes(shadowedAction.getExtraActionInfo(actionKeyContext).build().toByteArray());
     return f.hexDigestAndReset();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/extra/ExtraActionSpec.java b/src/main/java/com/google/devtools/build/lib/analysis/extra/ExtraActionSpec.java
index c613ec5..3d737a1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/extra/ExtraActionSpec.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/extra/ExtraActionSpec.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.Action;
+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;
@@ -127,8 +128,10 @@
 
     // Multiple actions in the same configured target need to have different names for the artifact
     // that might be created here, so we append something that should be unique for each action.
-    String actionUniquifier = actionToShadow.getPrimaryOutput().getExecPath().getBaseName() + "."
-        + actionToShadow.getKey();
+    String actionUniquifier =
+        actionToShadow.getPrimaryOutput().getExecPath().getBaseName()
+            + "."
+            + actionToShadow.getKey(owningRule.getActionKeyContext());
     List<String> argv = commandHelper.buildCommandLine(command, extraActionInputs,
         "." + actionUniquifier + ".extra_action_script.sh", executionInfo);
 
@@ -188,7 +191,8 @@
    */
   private Artifact getExtraActionOutputArtifact(
       RuleContext ruleContext, Action action, String template) {
-    String actionId = getActionId(ruleContext.getActionOwner(), action);
+    String actionId =
+        getActionId(ruleContext.getActionKeyContext(), ruleContext.getActionOwner(), action);
 
     template = template.replace("$(ACTION_ID)", actionId);
     template = template.replace("$(OWNER_LABEL_DIGEST)", getOwnerDigest(ruleContext));
@@ -224,14 +228,14 @@
   /**
    * Creates a unique id for the action shadowed by this extra_action.
    *
-   * We need to have a unique id for the extra_action to use. We build this
-   * from the owner's  label and the shadowed action id (which is only
-   * guaranteed to be unique per target). Together with the subfolder
-   * matching the original target's package name, we believe this is enough
-   * of a uniqueness guarantee.
+   * <p>We need to have a unique id for the extra_action to use. We build this from the owner's
+   * label and the shadowed action id (which is only guaranteed to be unique per target). Together
+   * with the subfolder matching the original target's package name, we believe this is enough of a
+   * uniqueness guarantee.
    */
   @VisibleForTesting
-  public static String getActionId(ActionOwner owner, Action action) {
+  public static String getActionId(
+      ActionKeyContext actionKeyContext, ActionOwner owner, Action action) {
     Fingerprint f = new Fingerprint();
     f.addString(owner.getLabel().toString());
     ImmutableList<AspectDescriptor> aspectDescriptors = owner.getAspectDescriptors();
@@ -239,7 +243,7 @@
     for (AspectDescriptor aspectDescriptor : aspectDescriptors) {
       f.addString(aspectDescriptor.getDescription());
     }
-    f.addString(action.getKey());
+    f.addString(action.getKey(actionKeyContext));
     return f.hexDigestAndReset();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/BaselineCoverageAction.java b/src/main/java/com/google/devtools/build/lib/analysis/test/BaselineCoverageAction.java
index 2953ed6..172d5b2 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/BaselineCoverageAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/BaselineCoverageAction.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.Iterables;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.NotifyOnActionCacheHit;
@@ -58,7 +59,7 @@
   }
 
   @Override
-  public String computeKey() {
+  public String computeKey(ActionKeyContext actionKeyContext) {
     return new Fingerprint()
         .addStrings(getInstrumentedFilePathStrings())
         .hexDigestAndReset();
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFileManifestAction.java b/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFileManifestAction.java
index 35350f0..628be6c 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFileManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFileManifestAction.java
@@ -21,6 +21,7 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.analysis.RuleContext;
@@ -77,7 +78,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     // Not sorting here is probably cheaper, though it might lead to unnecessary re-execution.
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/TestRunnerAction.java b/src/main/java/com/google/devtools/build/lib/analysis/test/TestRunnerAction.java
index 0ea1f92..34e4311 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/TestRunnerAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/TestRunnerAction.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.actions.ActionExecutionException;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
+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;
@@ -229,7 +230,8 @@
   }
 
   @Override
-  protected String computeKey() throws CommandLineExpansionException {
+  protected String computeKey(ActionKeyContext actionKeyContext)
+      throws CommandLineExpansionException {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addStrings(executionSettings.getArgs().arguments());
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/BazelWorkspaceStatusModule.java b/src/main/java/com/google/devtools/build/lib/bazel/BazelWorkspaceStatusModule.java
index 363b282..e3e405b 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/BazelWorkspaceStatusModule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/BazelWorkspaceStatusModule.java
@@ -24,6 +24,7 @@
 import com.google.common.eventbus.Subscribe;
 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;
@@ -267,7 +268,7 @@
     }
 
     @Override
-    protected String computeKey() {
+    protected String computeKey(ActionKeyContext actionKeyContext) {
       return "";
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
index e878b6f..9f20f76 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
@@ -702,6 +702,7 @@
         new ActionCacheChecker(
             actionCache,
             artifactFactory,
+            skyframeExecutor.getActionKeyContext(),
             executionFilter,
             ActionCacheChecker.CacheConfig.builder()
                 .setEnabled(options.useActionCache)
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/BUILD b/src/main/java/com/google/devtools/build/lib/collect/nestedset/BUILD
index 6c6ef3e..4de0059 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/BUILD
@@ -34,3 +34,12 @@
         "//third_party/protobuf:protobuf_java",
     ],
 )
+
+java_library(
+    name = "fingerprint_cache",
+    srcs = ["NestedSetFingerprintCache.java"],
+    deps = [
+        ":nestedset",
+        "//src/main/java/com/google/devtools/build/lib:util",
+    ],
+)
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
index b9e4308..30d5805 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
@@ -37,7 +37,7 @@
 public final class NestedSet<E> implements Iterable<E> {
 
   private final Order order;
-  final Object children;
+  private final Object children;
   private byte[] memo;
 
   private static final byte[] LEAF_MEMO = {};
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodec.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodec.java
index eee5edc..e11d790 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodec.java
@@ -179,7 +179,7 @@
   private static Collection<Object> getTopologicallySortedChildren(
       NestedSet<?> nestedSet) {
     LinkedHashSet<Object> result = new LinkedHashSet<>();
-    dfs(result, nestedSet.children);
+    dfs(result, nestedSet.rawChildren());
     return result;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
new file mode 100644
index 0000000..8e56d55
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
@@ -0,0 +1,78 @@
+// 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 com.google.devtools.build.lib.util.Fingerprint;
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
+
+/** Computes fingerprints for nested sets, reusing sub-computations from children. */
+public abstract class NestedSetFingerprintCache<T> {
+  private static final byte[] EMPTY_SET_BYTES = new byte[] {};
+  private Map<Object, byte[]> fingerprints = createMap();
+
+  public void addNestedSetToFingerprint(Fingerprint fingerprint, NestedSet<T> nestedSet) {
+    fingerprint.addInt(nestedSet.getOrder().ordinal());
+    Object children = nestedSet.rawChildren();
+    byte[] bytes = getBytes(children);
+    fingerprint.addBytes(bytes);
+  }
+
+  public void clear() {
+    fingerprints = createMap();
+  }
+
+  private byte[] getBytes(Object children) {
+    byte[] bytes = fingerprints.get(children);
+    if (bytes == null) {
+      if (children instanceof Object[]) {
+        Fingerprint fingerprint = new Fingerprint();
+        for (Object child : (Object[]) children) {
+          if (child instanceof Object[]) {
+            fingerprint.addBytes(getBytes(child));
+          } else {
+            addItemFingerprint(fingerprint, cast(child));
+          }
+        }
+        bytes = fingerprint.digestAndReset();
+
+        // There is no point memoizing anything except the multi-item case,
+        // since the single-item case gets inlined into its parents anyway,
+        // and the empty set is a singleton
+        fingerprints.put(children, bytes);
+      } else if (children != NestedSet.EMPTY_CHILDREN) {
+        // Single item
+        Fingerprint fingerprint = new Fingerprint();
+        addItemFingerprint(fingerprint, cast(children));
+        bytes = fingerprint.digestAndReset();
+      } else {
+        // Empty nested set
+        bytes = EMPTY_SET_BYTES;
+      }
+    }
+    return bytes;
+  }
+
+  @SuppressWarnings("unchecked")
+  private T cast(Object item) {
+    return (T) item;
+  }
+
+  private static Map<Object, byte[]> createMap() {
+    return new ConcurrentHashMap<>();
+  }
+
+  protected abstract void addItemFingerprint(Fingerprint fingerprint, T item);
+}
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeployInfoAction.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeployInfoAction.java
index 8fb0b4c..ef2a4c9 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeployInfoAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeployInfoAction.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.analysis.RuleContext;
@@ -105,7 +106,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint()
         .addString(GUID);
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/WriteAdbArgsAction.java b/src/main/java/com/google/devtools/build/lib/rules/android/WriteAdbArgsAction.java
index 868d6ee..87ef7e7 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/WriteAdbArgsAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/WriteAdbArgsAction.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.ExecException;
@@ -185,7 +186,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     return new Fingerprint()
         .addString(GUID)
         .hexDigestAndReset();
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
index 8d35075..667ef4d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
@@ -25,6 +25,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.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.ActionOwner;
@@ -704,7 +705,7 @@
   }
 
   @Override
-  public ExtraActionInfo.Builder getExtraActionInfo() {
+  public ExtraActionInfo.Builder getExtraActionInfo(ActionKeyContext actionKeyContext) {
     CppCompileInfo.Builder info = CppCompileInfo.newBuilder();
     info.setTool(gccToolPath.getPathString());
     for (String option : getCompilerOptions()) {
@@ -728,7 +729,8 @@
     }
 
     try {
-      return super.getExtraActionInfo().setExtension(CppCompileInfo.cppCompileInfo, info.build());
+      return super.getExtraActionInfo(actionKeyContext)
+          .setExtension(CppCompileInfo.cppCompileInfo, info.build());
     } catch (CommandLineExpansionException e) {
       throw new AssertionError("CppCompileAction command line expansion cannot fail.");
     }
@@ -1051,7 +1053,7 @@
   }
 
   @Override
-  public String computeKey() {
+  public String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addUUID(actionClassId);
     f.addStringMap(getEnvironment());
@@ -1075,17 +1077,11 @@
      */
     f.addPaths(context.getDeclaredIncludeDirs());
     f.addPaths(context.getDeclaredIncludeWarnDirs());
-    for (Artifact declaredIncludeSrc : context.getDeclaredIncludeSrcs()) {
-      f.addPath(declaredIncludeSrc.getExecPath());
-    }
+    actionKeyContext.addArtifactsToFingerprint(f, context.getDeclaredIncludeSrcs());
     f.addInt(0);  // mark the boundary between input types
-    for (Artifact input : getMandatoryInputs()) {
-      f.addPath(input.getExecPath());
-    }
+    actionKeyContext.addArtifactsToFingerprint(f, getMandatoryInputs());
     f.addInt(0);
-    for (Artifact input : prunableInputs) {
-      f.addPath(input.getExecPath());
-    }
+    actionKeyContext.addArtifactsToFingerprint(f, prunableInputs);
     return f.hexDigestAndReset();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkAction.java
index a9d0558..644a1b3 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkAction.java
@@ -25,6 +25,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.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -416,7 +417,7 @@
   }
 
   @Override
-  public ExtraActionInfo.Builder getExtraActionInfo() {
+  public ExtraActionInfo.Builder getExtraActionInfo(ActionKeyContext actionKeyContext) {
     // The uses of getLinkConfiguration in this method may not be consistent with the computed key.
     // I.e., this may be incrementally incorrect.
     CppLinkInfo.Builder info = CppLinkInfo.newBuilder();
@@ -435,7 +436,8 @@
     info.addAllLinkOpt(getLinkCommandLine().getRawLinkArgv());
 
     try {
-      return super.getExtraActionInfo().setExtension(CppLinkInfo.cppLinkInfo, info.build());
+      return super.getExtraActionInfo(actionKeyContext)
+          .setExtension(CppLinkInfo.cppLinkInfo, info.build());
     } catch (CommandLineExpansionException e) {
       throw new AssertionError("CppLinkAction command line expansion cannot fail.");
     }
@@ -447,7 +449,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(fake ? FAKE_LINK_GUID : LINK_GUID);
     f.addString(ldExecutable.getPathString());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMapAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMapAction.java
index 8df91f4..a51da6d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMapAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMapAction.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.Artifact.ArtifactExpander;
@@ -225,7 +226,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addInt(privateHeaders.size());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CreateIncSymlinkAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CreateIncSymlinkAction.java
index 4ef9677..d284948 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CreateIncSymlinkAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CreateIncSymlinkAction.java
@@ -21,6 +21,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.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -83,7 +84,7 @@
   }
 
   @Override
-  public String computeKey() {
+  public String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint key = new Fingerprint();
     for (Map.Entry<Artifact, Artifact> entry : symlinks.entrySet()) {
       key.addPath(entry.getKey().getPath());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/ExtractInclusionAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/ExtractInclusionAction.java
index 1bd76c2..c76ef3d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/ExtractInclusionAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/ExtractInclusionAction.java
@@ -18,6 +18,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.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -50,7 +51,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     return GUID;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoStubAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoStubAction.java
index 2c014f9..3997c51 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoStubAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoStubAction.java
@@ -16,6 +16,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.AbstractAction;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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;
@@ -55,7 +56,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     return "fdoStubAction";
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/LtoBackendAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/LtoBackendAction.java
index 10029ab..70586b8 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/LtoBackendAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/LtoBackendAction.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.actions.ActionEnvironment;
 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.Artifact;
 import com.google.devtools.build.lib.actions.CommandLineExpansionException;
@@ -165,7 +166,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     try {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/SolibSymlinkAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/SolibSymlinkAction.java
index df3a3bf..7f14ee2 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/SolibSymlinkAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/SolibSymlinkAction.java
@@ -20,6 +20,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.Actions;
@@ -67,9 +68,8 @@
     return ActionResult.EMPTY;
   }
 
-
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addPath(symlink.getPath());
     f.addPath(target);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/UmbrellaHeaderAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/UmbrellaHeaderAction.java
index eada861..a77e644 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/UmbrellaHeaderAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/UmbrellaHeaderAction.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Streams;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.Artifact.ArtifactExpander;
@@ -109,7 +110,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addPath(umbrellaHeader.getExecPath());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/WriteBuildInfoHeaderAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/WriteBuildInfoHeaderAction.java
index acbed8e..03a3594 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/WriteBuildInfoHeaderAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/WriteBuildInfoHeaderAction.java
@@ -20,6 +20,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.analysis.WorkspaceStatusAction;
@@ -135,7 +136,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addBoolean(writeStableInfo);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index d4938d5..f14db5a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -23,6 +23,7 @@
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.analysis.ConfiguredTarget;
@@ -375,7 +376,7 @@
     }
 
     @Override
-    protected String computeKey() {
+    protected String computeKey(ActionKeyContext actionKeyContext) {
       Fingerprint f = new Fingerprint();
       f.addBytes(result.toByteArray());
       return f.hexDigestAndReset();
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/BuildInfoPropertiesTranslator.java b/src/main/java/com/google/devtools/build/lib/rules/java/BuildInfoPropertiesTranslator.java
index 3f7b088..a476aae 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/BuildInfoPropertiesTranslator.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/BuildInfoPropertiesTranslator.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.rules.java;
 
+import com.google.devtools.build.lib.actions.ActionExecutionMetadata;
 import java.util.Map;
 import java.util.Properties;
 
@@ -26,8 +27,8 @@
   public void translate(Map<String, String> buildInfo, Properties properties);
 
   /**
-   * Returns a unique key for this translator to be used by the
-   * {@link com.google.devtools.build.lib.actions.Action#getKey()} method
+   * Returns a unique key for this translator to be used by the {@link
+   * ActionExecutionMetadata#getKey(com.google.devtools.build.lib.actions.ActionKeyContext)} method.
    */
   public String computeKey();
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
index 20324ac..f9d6349 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
@@ -30,6 +30,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionEnvironment;
+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.ArtifactOwner;
@@ -359,7 +360,7 @@
   }
 
   @Override
-  public ExtraActionInfo.Builder getExtraActionInfo() {
+  public ExtraActionInfo.Builder getExtraActionInfo(ActionKeyContext actionKeyContext) {
     JavaCompileInfo.Builder info = JavaCompileInfo.newBuilder();
     info.addAllSourceFile(Artifact.toExecPaths(getSourceFiles()));
     info.addAllClasspath(Artifact.toExecPaths(getClasspath()));
@@ -371,7 +372,8 @@
     info.setOutputjar(getOutputJar().getExecPathString());
 
     try {
-      return super.getExtraActionInfo().setExtension(JavaCompileInfo.javaCompileInfo, info.build());
+      return super.getExtraActionInfo(actionKeyContext)
+          .setExtension(JavaCompileInfo.javaCompileInfo, info.build());
     } catch (CommandLineExpansionException e) {
       throw new AssertionError("JavaCompileAction command line expansion cannot fail");
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileAction.java
index 1d42721..90975ad 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileAction.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.ActionInput;
+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.BaseSpawn;
@@ -124,10 +125,10 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint().addString(GUID);
     try {
-      f.addString(super.computeKey());
+      f.addString(super.computeKey(actionKeyContext));
       f.addStrings(directCommandLine.arguments());
     } catch (CommandLineExpansionException e) {
       throw new AssertionError("JavaHeaderCompileAction command line expansion cannot fail");
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/WriteBuildInfoPropertiesAction.java b/src/main/java/com/google/devtools/build/lib/rules/java/WriteBuildInfoPropertiesAction.java
index 26be2ab..7480361 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/WriteBuildInfoPropertiesAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/WriteBuildInfoPropertiesAction.java
@@ -20,6 +20,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+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.analysis.BuildInfo;
@@ -190,7 +191,7 @@
   }
 
   @Override
-  protected String computeKey() {
+  protected String computeKey(ActionKeyContext actionKeyContext) {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
     f.addString(keyTranslations.computeKey());
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
index 5483581..1ad13c1 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
@@ -23,6 +23,7 @@
 import com.google.common.eventbus.SubscriberExceptionHandler;
 import com.google.common.util.concurrent.Futures;
 import com.google.common.util.concurrent.Uninterruptibles;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.BlazeVersionInfo;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
@@ -149,6 +150,7 @@
   private final SubscriberExceptionHandler eventBusExceptionHandler;
   private final String productName;
   private final PathConverter pathToUriConverter;
+  private final ActionKeyContext actionKeyContext;
 
   // Workspace state (currently exactly one workspace per server)
   private BlazeWorkspace workspace;
@@ -162,6 +164,7 @@
       ConfiguredRuleClassProvider ruleClassProvider,
       ImmutableList<ConfigurationFragmentFactory> configurationFragmentFactories,
       ImmutableMap<String, InfoItem> infoItems,
+      ActionKeyContext actionKeyContext,
       Clock clock,
       Runnable abruptShutdownHandler,
       OptionsProvider startupOptionsProvider,
@@ -184,6 +187,7 @@
     this.ruleClassProvider = ruleClassProvider;
     this.configurationFragmentFactories = configurationFragmentFactories;
     this.infoItems = infoItems;
+    this.actionKeyContext = actionKeyContext;
     this.clock = clock;
     this.abruptShutdownHandler = abruptShutdownHandler;
     this.startupOptionsProvider = startupOptionsProvider;
@@ -294,6 +298,10 @@
     return workspace;
   }
 
+  public ActionKeyContext getActionKeyContext() {
+    return actionKeyContext;
+  }
+
   /**
    * The directory in which blaze stores the server state - that is, the socket
    * file and a log.
@@ -440,6 +448,8 @@
       env.getReporter().handle(Event.error("Error while writing profile file: " + e.getMessage()));
     }
     env.getReporter().clearEventBus();
+
+    actionKeyContext.clear();
   }
 
   // Make sure we keep a strong reference to this logger, so that the
@@ -971,6 +981,7 @@
             .setProductName(productName)
             .setFileSystem(fs)
             .setServerDirectories(serverDirectories)
+            .setActionKeyContext(new ActionKeyContext())
             .setStartupOptionsProvider(options)
             .setClock(clock)
             .setAbruptShutdownHandler(abruptShutdownHandler)
@@ -1122,11 +1133,14 @@
     private SubscriberExceptionHandler eventBusExceptionHandler = new RemoteExceptionHandler();
     private UUID instanceId;
     private String productName;
+    private ActionKeyContext actionKeyContext;
 
     public BlazeRuntime build() throws AbruptExitException {
       Preconditions.checkNotNull(productName);
       Preconditions.checkNotNull(serverDirectories);
       Preconditions.checkNotNull(startupOptionsProvider);
+      ActionKeyContext actionKeyContext =
+          this.actionKeyContext != null ? this.actionKeyContext : new ActionKeyContext();
       Clock clock = (this.clock == null) ? BlazeClock.instance() : this.clock;
       UUID instanceId =  (this.instanceId == null) ? UUID.randomUUID() : this.instanceId;
 
@@ -1197,6 +1211,7 @@
           ruleClassProvider,
           ruleClassProvider.getConfigurationFragments(),
           serverBuilder.getInfoItems(),
+          actionKeyContext,
           clock,
           abruptShutdownHandler,
           startupOptionsProvider,
@@ -1255,5 +1270,10 @@
       this.eventBusExceptionHandler = eventBusExceptionHandler;
       return this;
     }
+
+    public Builder setActionKeyContext(ActionKeyContext actionKeyContext) {
+      this.actionKeyContext = actionKeyContext;
+      return this;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BuildSummaryStatsModule.java b/src/main/java/com/google/devtools/build/lib/runtime/BuildSummaryStatsModule.java
index b5ea61d..6423f94 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BuildSummaryStatsModule.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BuildSummaryStatsModule.java
@@ -17,6 +17,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.eventbus.EventBus;
 import com.google.common.eventbus.Subscribe;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.buildeventstream.BuildToolLogs;
 import com.google.devtools.build.lib.buildtool.BuildRequest;
 import com.google.devtools.build.lib.buildtool.buildevent.BuildCompleteEvent;
@@ -41,6 +42,7 @@
 
   private static final Logger logger = Logger.getLogger(BuildSummaryStatsModule.class.getName());
 
+  private ActionKeyContext actionKeyContext;
   private SimpleCriticalPathComputer criticalPathComputer;
   private EventBus eventBus;
   private Reporter reporter;
@@ -51,6 +53,7 @@
   public void beforeCommand(CommandEnvironment env) {
     this.reporter = env.getReporter();
     this.eventBus = env.getEventBus();
+    this.actionKeyContext = env.getSkyframeExecutor().getActionKeyContext();
     eventBus.register(this);
   }
 
@@ -70,7 +73,8 @@
   @Subscribe
   public void executionPhaseStarting(ExecutionStartingEvent event) {
     if (enabled) {
-      criticalPathComputer = new SimpleCriticalPathComputer(BlazeClock.instance(), discardActions);
+      criticalPathComputer =
+          new SimpleCriticalPathComputer(actionKeyContext, BlazeClock.instance(), discardActions);
       eventBus.register(criticalPathComputer);
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/CriticalPathComputer.java b/src/main/java/com/google/devtools/build/lib/runtime/CriticalPathComputer.java
index 0b83b50..1c6ce03 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/CriticalPathComputer.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/CriticalPathComputer.java
@@ -21,6 +21,7 @@
 import com.google.common.eventbus.Subscribe;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionCompletionEvent;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionMiddlemanEvent;
 import com.google.devtools.build.lib.actions.ActionStartedEvent;
 import com.google.devtools.build.lib.actions.Actions;
@@ -48,6 +49,7 @@
   static final int SLOWEST_COMPONENTS_SIZE = 30;
   // outputArtifactToComponent is accessed from multiple event handlers.
   protected final ConcurrentMap<Artifact, C> outputArtifactToComponent = Maps.newConcurrentMap();
+  private final ActionKeyContext actionKeyContext;
 
   /** Maximum critical path found. */
   private C maxCriticalPath;
@@ -71,7 +73,9 @@
 
   private final Object lock = new Object();
 
-  protected CriticalPathComputer(Clock clock, boolean discardActions) {
+  protected CriticalPathComputer(
+      ActionKeyContext actionKeyContext, Clock clock, boolean discardActions) {
+    this.actionKeyContext = actionKeyContext;
     this.clock = clock;
     this.discardActions = discardActions;
     maxCriticalPath = null;
@@ -134,7 +138,7 @@
     if (storedComponent != null) {
       Action oldAction = storedComponent.maybeGetAction();
       if (oldAction != null) {
-        if (!Actions.canBeShared(newAction, oldAction)) {
+        if (!Actions.canBeShared(actionKeyContext, newAction, oldAction)) {
           throw new IllegalStateException(
               "Duplicate output artifact found for unsharable actions."
                   + "This can happen if a previous event registered the action.\n"
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/SimpleCriticalPathComputer.java b/src/main/java/com/google/devtools/build/lib/runtime/SimpleCriticalPathComputer.java
index bb855ed..482c55f 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/SimpleCriticalPathComputer.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/SimpleCriticalPathComputer.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.clock.Clock;
 
 /**
@@ -24,8 +25,9 @@
     extends CriticalPathComputer<SimpleCriticalPathComponent,
         AggregatedCriticalPath<SimpleCriticalPathComponent>> {
 
-  SimpleCriticalPathComputer(Clock clock, boolean discardActions) {
-    super(clock, discardActions);
+  SimpleCriticalPathComputer(
+      ActionKeyContext actionKeyContext, Clock clock, boolean discardActions) {
+    super(actionKeyContext, clock, discardActions);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/WorkspaceBuilder.java b/src/main/java/com/google/devtools/build/lib/runtime/WorkspaceBuilder.java
index 4ae356d..c0460af 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/WorkspaceBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/WorkspaceBuilder.java
@@ -73,6 +73,7 @@
             packageFactory,
             runtime.getFileSystem(),
             directories,
+            runtime.getActionKeyContext(),
             workspaceStatusActionFactory,
             ruleClassProvider.getBuildInfoFactories(),
             diffAwarenessFactories.build(),
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/commands/PrintActionCommand.java b/src/main/java/com/google/devtools/build/lib/runtime/commands/PrintActionCommand.java
index f9bbde4..465f29e 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/commands/PrintActionCommand.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/commands/PrintActionCommand.java
@@ -19,6 +19,7 @@
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
 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.actions.CommandLineExpansionException;
 import com.google.devtools.build.lib.actions.extra.DetailedExtraActionInfo;
@@ -179,9 +180,14 @@
         if (!filesToCompile.isEmpty()) {
           try {
             if (compileOneDependency) {
-              gatherActionsForFiles(configuredTarget, actionGraph, targets);
+              gatherActionsForFiles(
+                  configuredTarget,
+                  actionGraph,
+                  env.getSkyframeExecutor().getActionKeyContext(),
+                  targets);
             } else {
-              gatherActionsForTarget(configuredTarget, actionGraph);
+              gatherActionsForTarget(
+                  configuredTarget, actionGraph, env.getSkyframeExecutor().getActionKeyContext());
             }
           } catch (CommandLineExpansionException e) {
             env.getReporter().handle(Event.error(null, "Error expanding command line: " + e));
@@ -199,16 +205,22 @@
     }
 
     private BuildResult gatherActionsForFiles(
-        ConfiguredTarget configuredTarget, ActionGraph actionGraph, List<String> files)
+        ConfiguredTarget configuredTarget,
+        ActionGraph actionGraph,
+        ActionKeyContext actionKeyContext,
+        List<String> files)
         throws CommandLineExpansionException {
       Set<String> filesDesired = new LinkedHashSet<>(files);
       ActionFilter filter = new DefaultActionFilter(filesDesired, actionMnemonicMatcher);
 
-      gatherActionsForFile(configuredTarget, filter, actionGraph);
+      gatherActionsForFile(configuredTarget, filter, actionGraph, actionKeyContext);
       return null;
     }
 
-    private void gatherActionsForTarget(ConfiguredTarget configuredTarget, ActionGraph actionGraph)
+    private void gatherActionsForTarget(
+        ConfiguredTarget configuredTarget,
+        ActionGraph actionGraph,
+        ActionKeyContext actionKeyContext)
         throws CommandLineExpansionException {
       if (!(configuredTarget.getTarget() instanceof Rule)) {
         return;
@@ -227,7 +239,7 @@
       for (ActionAnalysisMetadata action : actions) {
         if (action instanceof Action) {
           DetailedExtraActionInfo.Builder detail = DetailedExtraActionInfo.newBuilder();
-          detail.setAction(((Action) action).getExtraActionInfo());
+          detail.setAction(((Action) action).getExtraActionInfo(actionKeyContext));
           summaryBuilder.addAction(detail);
         }
       }
@@ -238,7 +250,10 @@
      * extra_action if the filter evaluates to {@code true}.
      */
     private void gatherActionsForFile(
-        ConfiguredTarget configuredTarget, ActionFilter filter, ActionGraph actionGraph)
+        ConfiguredTarget configuredTarget,
+        ActionFilter filter,
+        ActionGraph actionGraph,
+        ActionKeyContext actionKeyContext)
         throws CommandLineExpansionException {
       NestedSet<Artifact> artifacts = OutputGroupProvider.get(configuredTarget)
           .getOutputGroup(OutputGroupProvider.FILES_TO_COMPILE);
@@ -252,7 +267,7 @@
         if (filter.shouldOutput(action, configuredTarget, actionGraph)) {
           if (action instanceof Action) {
             DetailedExtraActionInfo.Builder detail = DetailedExtraActionInfo.newBuilder();
-            detail.setAction(((Action) action).getExtraActionInfo());
+            detail.setAction(((Action) action).getExtraActionInfo(actionKeyContext));
             summaryBuilder.addAction(detail);
           }
         }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
index eb7d267..6822daf 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Actions.GeneratingActions;
@@ -43,9 +44,12 @@
  * input TreeArtifact.
  */
 public class ActionTemplateExpansionFunction implements SkyFunction {
+  private final ActionKeyContext actionKeyContext;
   private final Supplier<Boolean> removeActionsAfterEvaluation;
 
-  ActionTemplateExpansionFunction(Supplier<Boolean> removeActionsAfterEvaluation) {
+  ActionTemplateExpansionFunction(
+      ActionKeyContext actionKeyContext, Supplier<Boolean> removeActionsAfterEvaluation) {
+    this.actionKeyContext = actionKeyContext;
     this.removeActionsAfterEvaluation = Preconditions.checkNotNull(removeActionsAfterEvaluation);
   }
 
@@ -83,7 +87,8 @@
       throw new ActionTemplateExpansionFunctionException(e);
     }
 
-    return new ActionTemplateExpansionValue(expandedActions, removeActionsAfterEvaluation.get());
+    return new ActionTemplateExpansionValue(
+        actionKeyContext, expandedActions, removeActionsAfterEvaluation.get());
   }
 
   /** Exception thrown by {@link ActionTemplateExpansionFunction}. */
@@ -104,7 +109,7 @@
   private void checkActionAndArtifactConflicts(Iterable<Action> actions)
       throws ActionConflictException, ArtifactPrefixConflictException {
     GeneratingActions generatingActions =
-        Actions.findAndThrowActionConflict(ImmutableList.<ActionAnalysisMetadata>copyOf(actions));
+        Actions.findAndThrowActionConflict(actionKeyContext, ImmutableList.copyOf(actions));
     Map<ActionAnalysisMetadata, ArtifactPrefixConflictException> artifactPrefixConflictMap =
         Actions.findArtifactPrefixConflicts(
             ActionLookupValue.getMapForConsistencyCheck(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
index e2c0249..7771e08 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
@@ -16,7 +16,7 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.Action;
-import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.actions.ActionTemplate;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -30,10 +30,10 @@
 public final class ActionTemplateExpansionValue extends ActionLookupValue {
 
   ActionTemplateExpansionValue(
-      Iterable<Action> expandedActions, boolean removeActionsAfterEvaluation) {
-    super(
-        ImmutableList.<ActionAnalysisMetadata>copyOf(expandedActions),
-        removeActionsAfterEvaluation);
+      ActionKeyContext actionKeyContext,
+      Iterable<Action> expandedActions,
+      boolean removeActionsAfterEvaluation) {
+    super(actionKeyContext, ImmutableList.copyOf(expandedActions), removeActionsAfterEvaluation);
   }
 
   static SkyKey key(ActionTemplate<?> actionTemplate) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index d70683c..dab170e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -19,7 +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.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.AliasProvider;
 import com.google.devtools.build.lib.analysis.AspectResolver;
@@ -217,7 +217,12 @@
     Target target = associatedTarget.getTarget();
 
     if (configuredTargetValue.getConfiguredTarget().getProvider(AliasProvider.class) != null) {
-      return createAliasAspect(env, target, aspect, key,
+      return createAliasAspect(
+          env,
+          view.getActionKeyContext(),
+          target,
+          aspect,
+          key,
           configuredTargetValue.getConfiguredTarget());
     }
 
@@ -322,6 +327,7 @@
 
       return createAspect(
           env,
+          view.getActionKeyContext(),
           key,
           aspectPath,
           aspect,
@@ -407,6 +413,7 @@
 
   private SkyValue createAliasAspect(
       Environment env,
+      ActionKeyContext actionKeyContext,
       Target originalTarget,
       Aspect aspect,
       AspectKey originalKey,
@@ -438,7 +445,8 @@
         originalTarget.getLabel(),
         originalTarget.getLocation(),
         ConfiguredAspect.forAlias(real.getConfiguredAspect()),
-        ImmutableList.<ActionAnalysisMetadata>of(),
+        actionKeyContext,
+        ImmutableList.of(),
         transitivePackages,
         removeActionsAfterEvaluation.get());
   }
@@ -446,6 +454,7 @@
   @Nullable
   private AspectValue createAspect(
       Environment env,
+      ActionKeyContext actionKeyContext,
       AspectKey key,
       ImmutableList<Aspect> aspectPath,
       Aspect aspect,
@@ -513,6 +522,7 @@
         associatedTarget.getLabel(),
         associatedTarget.getTarget().getLocation(),
         configuredAspect,
+        actionKeyContext,
         ImmutableList.copyOf(analysisEnvironment.getRegisteredActions()),
         transitivePackages.build(),
         removeActionsAfterEvaluation.get());
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
index 8a80192..fb81622 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
@@ -18,6 +18,7 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
@@ -323,10 +324,11 @@
       Label label,
       Location location,
       ConfiguredAspect configuredAspect,
+      ActionKeyContext actionKeyContext,
       List<ActionAnalysisMetadata> actions,
       NestedSet<Package> transitivePackages,
       boolean removeActionsAfterEvaluation) {
-    super(actions, removeActionsAfterEvaluation);
+    super(actionKeyContext, actions, removeActionsAfterEvaluation);
     this.label = Preconditions.checkNotNull(label, actions);
     this.aspect = Preconditions.checkNotNull(aspect, label);
     this.location = Preconditions.checkNotNull(location, label);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java
index e7796b4..62878a5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java
@@ -16,6 +16,7 @@
 import com.google.common.base.Preconditions;
 import com.google.common.base.Supplier;
 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.ArtifactFactory;
 import com.google.devtools.build.lib.actions.Root;
@@ -36,15 +37,18 @@
  * injected value.
  */
 public class BuildInfoCollectionFunction implements SkyFunction {
+  private final ActionKeyContext actionKeyContext;
   // Supplier only because the artifact factory has not yet been created at constructor time.
   private final Supplier<ArtifactFactory> artifactFactory;
   private final Supplier<Boolean> removeActionsAfterEvaluation;
   private final ImmutableMap<BuildInfoKey, BuildInfoFactory> buildInfoFactories;
 
   BuildInfoCollectionFunction(
+      ActionKeyContext actionKeyContext,
       Supplier<ArtifactFactory> artifactFactory,
       ImmutableMap<BuildInfoKey, BuildInfoFactory> buildInfoFactories,
       Supplier<Boolean> removeActionsAfterEvaluation) {
+    this.actionKeyContext = actionKeyContext;
     this.artifactFactory = artifactFactory;
     this.buildInfoFactories = buildInfoFactories;
     this.removeActionsAfterEvaluation = Preconditions.checkNotNull(removeActionsAfterEvaluation);
@@ -77,6 +81,7 @@
     };
 
     return new BuildInfoCollectionValue(
+        actionKeyContext,
         buildInfoFactories
             .get(keyAndConfig.getInfoKey())
             .create(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java
index 6c81ca1..6486939 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoCollection;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory;
@@ -29,8 +30,11 @@
 public class BuildInfoCollectionValue extends ActionLookupValue {
   private final BuildInfoCollection collection;
 
-  BuildInfoCollectionValue(BuildInfoCollection collection, boolean removeActionsAfterEvaluation) {
-    super(collection.getActions(), removeActionsAfterEvaluation);
+  BuildInfoCollectionValue(
+      ActionKeyContext actionKeyContext,
+      BuildInfoCollection collection,
+      boolean removeActionsAfterEvaluation) {
+    super(actionKeyContext, collection.getActions(), removeActionsAfterEvaluation);
     this.collection = collection;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index 7622f43..8a34fdd 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -614,8 +614,10 @@
     // Check for conflicting actions within this configured target (that indicates a bug in the
     // rule implementation).
     try {
-      generatingActions = Actions.filterSharedActionsAndThrowActionConflict(
-          analysisEnvironment.getRegisteredActions());
+      generatingActions =
+          Actions.filterSharedActionsAndThrowActionConflict(
+              analysisEnvironment.getActionKeyContext(),
+              analysisEnvironment.getRegisteredActions());
     } catch (ActionConflictException e) {
       throw new ConfiguredTargetFunctionException(e);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java
index 45a1a45..64fdcc4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -28,9 +29,12 @@
  * A Skyframe function to calculate the coverage report Action and Artifacts.
  */
 public class CoverageReportFunction implements SkyFunction {
+  private final ActionKeyContext actionKeyContext;
   private final Supplier<Boolean> removeActionsAfterEvaluation;
 
-  CoverageReportFunction(Supplier<Boolean> removeActionsAfterEvaluation) {
+  CoverageReportFunction(
+      ActionKeyContext actionKeyContext, Supplier<Boolean> removeActionsAfterEvaluation) {
+    this.actionKeyContext = actionKeyContext;
     this.removeActionsAfterEvaluation = Preconditions.checkNotNull(removeActionsAfterEvaluation);
   }
 
@@ -51,7 +55,7 @@
       outputs.addAll(action.getOutputs());
     }
 
-    return new CoverageReportValue(actions, removeActionsAfterEvaluation.get());
+    return new CoverageReportValue(actionKeyContext, actions, removeActionsAfterEvaluation.get());
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
index 3f9c8d8..fde0599 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
@@ -16,6 +16,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.skyframe.LegacySkyKey;
@@ -32,9 +33,10 @@
   static final SkyKey SKY_KEY = LegacySkyKey.create(SkyFunctions.COVERAGE_REPORT, ARTIFACT_OWNER);
 
   CoverageReportValue(
+      ActionKeyContext actionKeyContext,
       ImmutableList<ActionAnalysisMetadata> coverageReportActions,
       boolean removeActionsAfterEvaluation) {
-    super(coverageReportActions, removeActionsAfterEvaluation);
+    super(actionKeyContext, coverageReportActions, removeActionsAfterEvaluation);
   }
 
   private static class CoverageReportKey extends ActionLookupKey {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index 7ae1bca..f93c96e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -26,6 +26,7 @@
 import com.google.common.collect.Maps;
 import com.google.common.collect.Range;
 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.BuildView;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
@@ -133,6 +134,7 @@
       PackageFactory pkgFactory,
       FileSystem fileSystem,
       BlazeDirectories directories,
+      ActionKeyContext actionKeyContext,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
       Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories,
@@ -147,6 +149,7 @@
         pkgFactory,
         fileSystem,
         directories,
+        actionKeyContext,
         workspaceStatusActionFactory,
         buildInfoFactories,
         extraSkyFunctions,
@@ -163,6 +166,7 @@
       PackageFactory pkgFactory,
       FileSystem fileSystem,
       BlazeDirectories directories,
+      ActionKeyContext actionKeyContext,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
       Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories,
@@ -178,6 +182,7 @@
             pkgFactory,
             fileSystem,
             directories,
+            actionKeyContext,
             workspaceStatusActionFactory,
             buildInfoFactories,
             diffAwarenessFactories,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutorFactory.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutorFactory.java
index 6e5c409..c56469f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutorFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutorFactory.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction.Factory;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory;
@@ -34,6 +35,7 @@
       PackageFactory pkgFactory,
       FileSystem fileSystem,
       BlazeDirectories directories,
+      ActionKeyContext actionKeyContext,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
       Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories,
@@ -43,6 +45,7 @@
         pkgFactory,
         fileSystem,
         directories,
+        actionKeyContext,
         workspaceStatusActionFactory,
         buildInfoFactories,
         diffAwarenessFactories,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
index 82a8f6b..60af800 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
@@ -38,6 +38,7 @@
 import com.google.devtools.build.lib.actions.ActionInput;
 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;
@@ -113,6 +114,7 @@
   // more detail.
   private static final Striped<Lock> outputDirectoryDeletionLock = Striped.lock(64);
 
+  private final ActionKeyContext actionKeyContext;
   private Reporter reporter;
   private final AtomicReference<EventBus> eventBus;
   private Map<String, String> clientEnv = ImmutableMap.of();
@@ -154,8 +156,10 @@
   private OutputService outputService;
 
   SkyframeActionExecutor(
+      ActionKeyContext actionKeyContext,
       AtomicReference<EventBus> eventBus,
       AtomicReference<ActionExecutionStatusReporter> statusReporterRef) {
+    this.actionKeyContext = actionKeyContext;
     this.eventBus = eventBus;
     this.statusReporterRef = statusReporterRef;
   }
@@ -235,7 +239,8 @@
     ConcurrentMap<ActionAnalysisMetadata, ConflictException> temporaryBadActionMap =
         new ConcurrentHashMap<>();
     Pair<ActionGraph, SortedMap<PathFragment, Artifact>> result;
-    result = constructActionGraphAndPathMap(actionLookupValues, temporaryBadActionMap);
+    result =
+        constructActionGraphAndPathMap(actionKeyContext, actionLookupValues, temporaryBadActionMap);
     ActionGraph actionGraph = result.first;
     SortedMap<PathFragment, Artifact> artifactPathMap = result.second;
 
@@ -251,16 +256,17 @@
   }
 
   /**
-   * Simultaneously construct an action graph for all the actions in Skyframe and a map from
-   * {@link PathFragment}s to their respective {@link Artifact}s. We do this in a threadpool to save
-   * around 1.5 seconds on a mid-sized build versus a single-threaded operation.
+   * Simultaneously construct an action graph for all the actions in Skyframe and a map from {@link
+   * PathFragment}s to their respective {@link Artifact}s. We do this in a threadpool to save around
+   * 1.5 seconds on a mid-sized build versus a single-threaded operation.
    */
   private static Pair<ActionGraph, SortedMap<PathFragment, Artifact>>
       constructActionGraphAndPathMap(
+          ActionKeyContext actionKeyContext,
           Iterable<ActionLookupValue> values,
           ConcurrentMap<ActionAnalysisMetadata, ConflictException> badActionMap)
-      throws InterruptedException {
-    MutableActionGraph actionGraph = new MapBasedActionGraph();
+          throws InterruptedException {
+    MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     ConcurrentNavigableMap<PathFragment, Artifact> artifactPathMap = new ConcurrentSkipListMap<>();
     // Action graph construction is CPU-bound.
     int numJobs = Runtime.getRuntime().availableProcessors();
@@ -309,8 +315,8 @@
                 actionGraph.registerAction(action);
               } catch (ActionConflictException e) {
                 Exception oldException = badActionMap.put(action, new ConflictException(e));
-                Preconditions.checkState(oldException == null,
-                  "%s | %s | %s", action, e, oldException);
+                Preconditions.checkState(
+                    oldException == null, "%s | %s | %s", action, e, oldException);
                 // We skip the rest of the loop, and do not add the path->artifact mapping for this
                 // artifact below -- we don't need to check it since this action is already in
                 // error.
@@ -468,6 +474,7 @@
         executorEngine,
         new DelegatingPairFileCache(graphFileCache, perBuildFileCache),
         actionInputPrefetcher,
+        actionKeyContext,
         metadataHandler,
         fileOutErr,
         clientEnv,
@@ -577,6 +584,7 @@
             executorEngine,
             new DelegatingPairFileCache(graphFileCache, perBuildFileCache),
             actionInputPrefetcher,
+            actionKeyContext,
             metadataHandler,
             actionLogBufferPathGenerator.generate(),
             clientEnv,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
index aa48b30..a1ba4e5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
@@ -25,6 +25,7 @@
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -472,7 +473,13 @@
     boolean extendedSanityChecks = config != null && config.extendedSanityChecks();
     boolean allowRegisteringActions = config == null || config.isActionsEnabled();
     return new CachingAnalysisEnvironment(
-        artifactFactory, owner, isSystemEnv, extendedSanityChecks, eventHandler, env,
+        artifactFactory,
+        skyframeExecutor.getActionKeyContext(),
+        owner,
+        isSystemEnv,
+        extendedSanityChecks,
+        eventHandler,
+        env,
         allowRegisteringActions);
   }
 
@@ -618,6 +625,10 @@
     this.enableAnalysis = enable;
   }
 
+  public ActionKeyContext getActionKeyContext() {
+    return skyframeExecutor.getActionKeyContext();
+  }
+
   private class ConfiguredTargetValueProgressReceiver
       extends EvaluationProgressReceiver.NullEvaluationProgressReceiver {
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index d233aab..6ab30a3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -42,6 +42,7 @@
 import com.google.devtools.build.lib.actions.ActionGraph;
 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.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -244,6 +245,7 @@
   // Having the BuildInfoFunction own the supplier is currently not possible either, because then
   // it would be invalidated on every build, since it would depend on the build id value.
   private MutableSupplier<UUID> buildId = new MutableSupplier<>();
+  private final ActionKeyContext actionKeyContext;
 
   protected boolean active = true;
   private final SkyframePackageManager packageManager;
@@ -293,6 +295,7 @@
       PackageFactory pkgFactory,
       FileSystem fileSystem,
       BlazeDirectories directories,
+      ActionKeyContext actionKeyContext,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
       ImmutableMap<SkyFunctionName, SkyFunction> extraSkyFunctions,
@@ -311,9 +314,11 @@
         new SkyframePackageLoader(), new SkyframeTransitivePackageLoader(),
         syscalls, cyclesReporter, pkgLocator, numPackagesLoaded, this);
     this.resourceManager = ResourceManager.instance();
-    this.skyframeActionExecutor = new SkyframeActionExecutor(eventBus, statusReporterRef);
+    this.skyframeActionExecutor =
+        new SkyframeActionExecutor(actionKeyContext, eventBus, statusReporterRef);
     this.fileSystem = fileSystem;
     this.directories = Preconditions.checkNotNull(directories);
+    this.actionKeyContext = Preconditions.checkNotNull(actionKeyContext);
     ImmutableMap.Builder<BuildInfoKey, BuildInfoFactory> factoryMapBuilder = ImmutableMap.builder();
     for (BuildInfoFactory factory : buildInfoFactories) {
       factoryMapBuilder.put(factory.getKey(), factory);
@@ -431,11 +436,14 @@
     map.put(
         SkyFunctions.BUILD_INFO_COLLECTION,
         new BuildInfoCollectionFunction(
-            artifactFactory, buildInfoFactories, removeActionsAfterEvaluation));
+            actionKeyContext, artifactFactory, buildInfoFactories, removeActionsAfterEvaluation));
     map.put(
         SkyFunctions.BUILD_INFO,
-        new WorkspaceStatusFunction(removeActionsAfterEvaluation, this::makeWorkspaceStatusAction));
-    map.put(SkyFunctions.COVERAGE_REPORT, new CoverageReportFunction(removeActionsAfterEvaluation));
+        new WorkspaceStatusFunction(
+            actionKeyContext, removeActionsAfterEvaluation, this::makeWorkspaceStatusAction));
+    map.put(
+        SkyFunctions.COVERAGE_REPORT,
+        new CoverageReportFunction(actionKeyContext, removeActionsAfterEvaluation));
     ActionExecutionFunction actionExecutionFunction =
         new ActionExecutionFunction(skyframeActionExecutor, tsgm);
     map.put(SkyFunctions.ACTION_EXECUTION, actionExecutionFunction);
@@ -445,7 +453,7 @@
     map.put(SkyFunctions.FILESET_ENTRY, new FilesetEntryFunction());
     map.put(
         SkyFunctions.ACTION_TEMPLATE_EXPANSION,
-        new ActionTemplateExpansionFunction(removeActionsAfterEvaluation));
+        new ActionTemplateExpansionFunction(actionKeyContext, removeActionsAfterEvaluation));
     map.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
     map.put(SkyFunctions.REGISTERED_TOOLCHAINS, new RegisteredToolchainsFunction());
     map.put(SkyFunctions.TOOLCHAIN_RESOLUTION, new ToolchainResolutionFunction());
@@ -1781,6 +1789,10 @@
     return packageManager;
   }
 
+  public ActionKeyContext getActionKeyContext() {
+    return actionKeyContext;
+  }
+
   class SkyframePackageLoader {
     /**
      * Looks up a particular package (mostly used after the loading phase, so packages should
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorFactory.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorFactory.java
index e27182f..3cb5d11 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorFactory.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction.Factory;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory;
@@ -48,6 +49,7 @@
       PackageFactory pkgFactory,
       FileSystem fileSystem,
       BlazeDirectories directories,
+      ActionKeyContext actionKeyContext,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
       Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusFunction.java
index 8d927f1..817c2fa 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusFunction.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -26,12 +27,15 @@
     WorkspaceStatusAction create(String workspaceName);
   }
 
+  private final ActionKeyContext actionKeyContext;
   private final Supplier<Boolean> removeActionAfterEvaluation;
   private final WorkspaceStatusActionFactory workspaceStatusActionFactory;
 
   WorkspaceStatusFunction(
+      ActionKeyContext actionKeyContext,
       Supplier<Boolean> removeActionAfterEvaluation,
       WorkspaceStatusActionFactory workspaceStatusActionFactory) {
+    this.actionKeyContext = actionKeyContext;
     this.removeActionAfterEvaluation = Preconditions.checkNotNull(removeActionAfterEvaluation);
     this.workspaceStatusActionFactory = workspaceStatusActionFactory;
   }
@@ -50,6 +54,7 @@
         workspaceStatusActionFactory.create(workspaceNameValue.getName());
 
     return new WorkspaceStatusValue(
+        actionKeyContext,
         action.getStableStatus(),
         action.getVolatileStatus(),
         action,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
index 7ee1d93..78ff03d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+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;
@@ -36,11 +37,12 @@
   public static final SkyKey SKY_KEY = LegacySkyKey.create(SkyFunctions.BUILD_INFO, ARTIFACT_OWNER);
 
   WorkspaceStatusValue(
+      ActionKeyContext actionKeyContext,
       Artifact stableArtifact,
       Artifact volatileArtifact,
       WorkspaceStatusAction action,
       boolean removeActionAfterEvaluation) {
-    super(action, removeActionAfterEvaluation);
+    super(actionKeyContext, action, removeActionAfterEvaluation);
     this.stableArtifact = stableArtifact;
     this.volatileArtifact = volatileArtifact;
   }
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(),