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;
   }